OS-tans

So, today I first encountered something... odd. An interesting little bit of culture (or perhaps cultural train wreck) that you really need to see for yourself (descriptions don't do it justice).

http://upload.wikimedia.org/wikipedia/en/b/b6/Ostans.jpg
http://www.wired.com/culture/design/multimedia/2007/04/gallery_mascots?slide=10&slideView=2
http://en.wikipedia.org/wiki/Os-tans

What one person has to say about things like this: http://www.doitlater.com/pic.php?121

The Lord's Prayer - Trique

Here is the version of the Lord's Prayer in Chicahuaxtla Trique, a Mexican indian language only spoken by a couple thousand now (and may be extinct soon, as Spanish is adopted), from a 1966 Trique Bible. I've added a couple annotations indicating what some words are, but I know very little of the language, and everything I do know has come from studying this Trique Bible "studying" for a few hours) and asking my grandpa questions. Those numbers indicate tones (there are five tones in Trique, and syllables can be glides from one tone to another).

Drej³ [father of] nej³ yunj² [us] huuin² re'⁵ [you are] nne² re'⁵ [you sit] xata'⁴a [heaven].
Ni⁴ [and] ga'mi⁴ [will speak] nej³ yunj² [us] sisi⁴ [if] hua³⁴ sa'⁵ [be good] nï'⁵ man'an² re'⁵ [your body].
Ni⁴ [and] ga'na'⁵ [will arrive] re'⁵ [you] gui4nicaj³⁴ re'⁵ son³⁴ rian³⁴ [on?] nej³ yunj² [us] ruhua²³ nej³ yunj² [us].
Ni⁴ [and] gui⁴'yaj³ [will do] nej³ yunj² [us] si³ [him?] garan'⁵ ruhua²³ re'⁵ gui⁴'yaj³ nej³ yunj².
Ro'² 'yaj³ nej³ si¹ nne³ xata'⁴a hue² daj⁴ gui⁴'yaj³ [will do] nej³ yunj² [us] ruhua²³ xumigüi⁵ nanj³.
Ni⁴ yyaj⁵⁴ a'yoj³ riqui⁴ re'⁵ si³ xa²³ nej³ yunj² nda'⁴³ ngo'ngo⁴ güi³.
Ni⁴ nicaj⁵ re'⁵ 'ngo⁴ niman²³ nico³ nga⁴ rian³⁴ si-gaquïn'⁴ nej³ yunj².
Dadin'³⁴ si³ hue² daj⁴ nicaj³⁴ nej³ yunj² 'ngo⁴ niman²³ nico³ nga⁴ rian³⁴ nej³ si¹ 'yaj³ gaquïn'⁴in rian³⁴ nej³ yunj².
Ni⁴ si⁴ ga'ui'² re'⁵ permiso si³ gadsïj³ siche³ niman²³ nej³ yunj².
Sani⁴ nacaj⁴ re'⁵ nej³ yunj² rian³⁴ si¹ danj³.
Dadin'³⁴ [because] nicaj³⁴ niganj⁵ nï'⁵ re'⁵ son³⁴.
Ni⁴ hua³⁴ [there is] nucua¹ re'⁵ [you are strong] nej³ [also].
Ni⁴ hua³⁴ [there is] hue'e² [be good] nï'⁵ re'⁵ nej³ [also].
Ni⁴ hue² [yes] daj⁴ gahuin² re'⁵ [you were] niganj⁵ nï'⁵.
Amén.

Super Shiny!

Well, Q has a new shiny thing to show off, and this one's a whopper (at least if you're a linguist): http://www.prayer.su/. It's a database of the Lord's Prayer in what looks like a couple hundred different languages. Some interesting samples for those not that interested in linguistics:
Classical Arabic (font required); also Arabic in Roman alphabet
Classical Armenian (font required)
Greek (font required); also Greek in Roman alphabet
Latin
Classical Chinese (font required)
Georgian (font required)
German
Hindi (font required)
Japanese (font required); also Japanese in Roman alphabet
Korean (font required)
Telugu (someone at our company speaks this; font required)
Klingon (different site)
Quenya in Roman alphabet
Sindarin in Roman alphabet
ce1000 AD Old English (not sure about font)
1384 AD Middle English
1559 AD Early Modern English

I don't really see a version of the prayer in Modern English that sounds exactly like how we actually talk. The 1963 version seems the best of the ones on that site. I'd probably write it like this:
Our Father in heaven
May Your name be honored
May Your kingdom be established
May Your will be done
On Earth as in heaven
Give us what we need for now
And forgive our sins as we forgive those who sin against us
Do not test our faith, but protect us from evil
For the kingdom, and the power, and the glory are Yours (this line was actually not present in the original version of the prayer; it was added later on)

I'm working on getting a Trique version from my grandpa, and I should be able to write a Tengwar (elven alphabet) version of the Quenya and Sindarin language versions on the site. Does anyone know Finnish? :P

Incompetence Weekend Extravaganza!

Well, it was a relatively uneventful weekend. Too little work, too little school, too little World of Warcraft. But there was plenty of incompetence to go around.

It's been a couple weeks since my program at work shipped (I'm a contract worker), and I haven't logged onto the company VPN after that until yesterday. I have a new project to work on, so it's about time I get started on it. I put in my user name and password into the VPN client; several seconds later, my cell phone begins to ring. It's an out of state number, although I recognized the area code as being the same area as my work. I answered it, and got a recording saying something like "please enter your PIN". The fact that my VPN login failed immediately after I hung up (having no idea what PIN they were talking about, or why I was supposed to enter it) made it seem likely that my work had switched to two-factor authentication; that is, after you enter your password, it calls your phone and asks for a second password.

So, I go into the company IRC channel (yes, it is a private, encrypted channel) and start bitching; you know, stuff like "What the **** is this PIN I'm supposed to be entering?" The reply was just as disturbing as the fact that I'd never set, nor been told, my PIN: it was e-mailed to me (in fact, it was the same for everybody)... through the company e-mail system, which is only accessible from the building or through the VPN. Brilliant, Einstein.

The solution ended up being simple and easy, though just as depressing: it appears that everyone in the company had the same default PIN (a trivial number), so it was trivial to find somebody to tell me what theirs is, and get back on the VPN. So, I log on to the VPN, and try to get to work, only to find that the VPN is totally not working, and back to World of Warcraft I went.

So today, I try again. After some more bitching in the IRC channel, Skywing helps me debug the problem. The specific problem was that the routes to the company resources were missing from my computer. Further investigation on my computer and by Skywing on the backend reveal that somebody or something (it actually turned out to be a misbehaving SQL script) had wiped the routes settings for a significant number of people (including all of the development team) on the pre-production server (the one the company uses for testing new versions not yet released to customers), which would have been propagated in turn to the computers of VPN users.

So, Skywing fixed that, and for the first time in a couple weeks I update my CVS checkout and start coding. My latest project relies on a certain third-party library which deals with routers, so I spent quite some time playing with the thing to figure out all the stuff I needed to know that wasn't in the SDK. One of the more puzzling things (when I was first starting out) was that most functions took an "encryption password" parameter. I supposed that that was the key to encrypt the router data it stores in the registry, but at the time it seemed unimportant, as the default value was NULL (suggesting it was optional).

The very first function I called returned an error code indicating invalid key. After some time of tweaking the parameters, trying to fix a variety of things that had the highest probability of being what the error was referring to, I had no luck. Naturally, the next thing I did was get out a debugger and disassembler, and started looking for the cause of the problem in the library. A number of calls to Microsoft CryptoAPI, revolving around that very encryption password, and ultimately resulting in failure, let me to the (correct) conclusion that that value was actually a password to use the library at all. While I haven't spent the time to investigate to certainty, it appears that this password is hard-coded into the library, and the library functions will fail if the proper password is not supplied. As far as I can tell, this password is unique to the copy of the library given to each company that licenses the library. That's pretty much a textbook case of putting a vault door on a straw hut, right there.

I periodically check Slashdot throughout the day, and today was no exception. Much to my continuing dismay, I find Sony doing something so phenomenally stupid that it just blows away any dumb things they've done before (rootkits, anyone?). Of course I'm talking about Sony Strikes Again. In short, Sony has rolled out a new form of DVD DRM that requires old players to receive upgraded firmware to be able to play it; of course, Sony won't have updated firmware for their own players for a few weeks after the new DVDs have already hit stores. I don't know about the real people, but if I were the CEO of Sony, I'd find the person responsible for shipping DVDs that my own players won't be able to play for weeks, fire him, and then call every single media company in Japan to tell them what he had done, ensuring that he would never work in that industry ever again.

My final piece of stupidity, if no further incidents appear while I'm writing this post (it's already happened once today - this very incident occurred while I was telling someone about the Sony incident), involved my further work with the third-party library. To it's credit, however, this wasn't a problem with the library; I merely discovered this while observing it map ports in my router. That is, I discovered that I can view ports mapped with UPnP in the web interface to my router, as well as what programs opened them. This discovery showed me that Windows Live Messenger, for the purpose of direct file sends (of which I've not made any since Messenger was started today), had mapped 39,538 ports to my computer, and was holding them until it was closed. I think that really speaks for itself, so I won't comment additionally on it.

Why CDDL?

So, for those of you who aren't on the modding community sites I used to frequent (and now visit every so often), I've decided to open-source the legendary MPQDraft (yes, it was an April Fools' prank - that nobody would believe it when they saw the announcement). This will require that I get the whole thing cleaned up and commented, so that I can get it uploaded to SourceForge. After that I really should finish the rather large changes I'm in the middle of making to LibQ, and put it up on SourceForge, as well. Both of these are/will be licensed under the Sun Common Development and Distribution License, so I thought I should explain why I chose this license, as opposed to the more common ones.

There are really only two rules motivating my selection of license. First, as I'm making my code available for public use and reuse, I want to make it available and useful to as many people as possible. Obviously, this means placing as few restrictions on use as possible. I didn't want to limit it to eyes only or noncommercial use only projects. I want people to be able to use the code in open source, closed source, and commercial programs alike.

However, it also implies something else. By open-sourcing my code I can ensure that other people have access to that code. But what if somebody takes my code and improves it? Of course, I'd want others to be able to make use of those improvements as well, or perhaps even merge it back into my original project. This means that, regardless of what programs people use my code in, they have to play by the rules of the code itself. I want a guarantee that any improvements or modifications people make to my open source code are also released as open source. This covers just my code and any additions/modifications that are a functional part of the code I wrote; it doesn't have anything to do with any code developed entirely separately, which just happens to be compiled along with my code in the same program.

Second, I want credit to be given for the use of my code. If not to me, then at least to the project itself. Besides the obvious reason of attribution, this serves to promote the project and increase exposure to it, bringing more potential users. This connects back to wanting as many people as possible to be able to benefit from my code. And, importantly, this is an entirely unrestrictive requirement (can you imagine somebody who would rather not use something that would be useful to them than to put one line in the credits?)

So, those are the basic principles. Next, let me point out why I didn't choose some of the more common licenses. First up is the Do What the Fuck You Want To Public License. It should be obvious why this one fails: it meets neither of my two objectives. There is no guarantee that credit will be given for the use of the code, or that changes will be made available to the public. I actually had never heard of this license (which might as well not be a license at all) before today; I'm just mentioning it because it illustrates why I wanted a license :P

Next is the overly popular General Public License. In my opinion, this is a rather obnoxious license, for the reason that it's as much about politics as it is about legality. While it guarantees that the code will remain free for use, it also guarantees that any programs using the code be free, and publicly available under the GPL itself. This is obnoxious because it means that only free/open source software (FOSS) may make use of GPL code. However, for a rather intimidating majority of the market, FOSS is not a feasible business model, and as such a majority of potential users are promptly excluded. This makes the GPL an extremely restrictive license, and completely at odds with my goals.

Next up is the Lesser General Public License (LGPL). This one came pretty close to meeting my requirements, but not quite close enough. The LGPL lacks the more draconian of restrictions in the GPL, allowing you to link it to code not licensed under the LGPL. While this might leave hope for it being useful to commercial software writers, there were two specific clauses that prompted me to reject it. First, some restrictions on linking to LGPL code make it impractical for closed source programs (and commercial programs even more so) to use LGPL code, if the LGPL code is not completely self-contained (e.g. a DLL that the program links to). This means that the LGPL only could satisfy my requirements if I were releasing a stand-alone library, and not an executable, as I am with MPQDraft.

Second, the LGPL allows modifications to the code to be released not under the LGPL, but under the GPL itself, which would further restrict the use of the code. This means that someone modifying my code would be able prevent people who can use my code from using their modifications to my code. This directly contradicts my ideal of maximum collective benefit from my code.

Finally, there's the BSD license. While this license guarantees attribution (if perhaps to a controversially strong degree) and allows anyone to use my code, it offers no guarantee that modifications or improvements to my code will also be made publicly available. As such, it violates my principle of maximum collective benefit in exactly the opposite way the GPL does; just the same, the BSD license is out.

Lastly, let me give a brief summary of the CDDL, as I intend it:
- You may use the licensed code in whole (the entire program) or in part (individual source files, functions, or methods) in any program you desire, regardless of the license of the program as a whole (or rather, as excluding the code you are borrowing). The program itself may be open or closed source, free or commercial.
- However, in all cases, any modifications, improvements, or additions to the CDDL code (any code that is referenced in direct modifications to the CDDL code is considered an addition to the CDDL code, and so is bound by this requirement; e.g. a modification of a math function to use a fast lookup table makes that table itself an addition to the CDDL code, regardless of whether it's in a source code file of its own) must be made publicly and freely available in source, under the CDDL license itself.
- In any program (source or binary) that uses CDDL code, recognition must be given to the source (either project or author) of the CDDL code. As well, modifications to the CDDL code (which must be distributed as source) may not remove notices indicating the ancestry of the code.

Man that turned out to be a long post.

Work, Work

Well, I appear to be in the fairly enviable position of having too many job offers (all but one of which being unsolicited - kind of) for the summer (and beyond). There are (if no more drop in by then) four "possibilities" (loose usage of the word).

The first of which is a summer internship at City of Hope. This would make a great resume-buff-upper, and may be educational, doing real research at a real medical research facility. However, I'm betting it wouldn't at all be like some of the classes I actually enjoyed going to at school (microbiology and immunology come readily to mind; I actually would enjoy being in class, though not so much the labs, homework, and tests), and I suspect it'd probably be nothing more than some mind-numbingly boring thing like running gels all day long for somebody or other's experiment (a typical entry-level biology job). Ultimately, I decided against this, based on the presence of more interesting possibilities, and the fact that, unlike all the others, I'd actually have to formally apply (and competition is fierce - only like 1 in 50 applicants get internships).

Next is the company I worked for last summer, and have been working a little bit for over the school year. As far as I'm aware, they still want me back, next summer and/or full time in the future. It's a really nice place to work for, though it's either the #2 or #3 spot on the list for most interesting/appealing work.

Next is... let's call them Company X (saying which would only incite replies of "WTF liar!" and "Bastard, I want to work there!"). As that implies, this is undoubtedly the most interesting and potentially fun job prospect (although I have no idea what the work environment is like). Last summer I got an "invitation" to work for this company, when I was sending my semi-regular research to a friend there, who is a programmer (thus, it wasn't a formal invitation, though as he has some sway, I would surely have a much better chance of getting hired than the average applicant). Unfortunately, it took almost a month to get an interview set up for me (it's not his fault, either. I sent him ping e-mails once or twice a week, and all he could tell me was that they haven't responded to him yet), and by that time I'd given up waiting, and was already in Kansas, working for my current company (the main reason I didn't wait longer was because I'd already told my company that I'd work for them, if the thing with Company X didn't work out, and I didn't want to make them wait any longer than I already had). This is probably my #1 consideration for what to do when I finish college; however, I'll probably put off trying again until I finish college, and just apply for a full-time position (rather than just summer work).

Finally, tonight my computer architecture II (senior-level class) teacher scouted me out for a future project somehow relating to him. He hasn't told me much yet, just that it involves something about computer simulation of neuro-something or other (maybe neural networks, or some such). This one could really disturb my plans of going back to Kansas this summer, if the project turns out to be interesting (when I learn more about it) and there's a monetary advantage to doing it, instead (since I wouldn't need to pay rent out of my earnings, like I would in Kansas).

So... I'm not at all sure what I'm gonna do this summer. As of right now I'm planning on going back to Kansas; but if there's a monetary advantage to taking the job with my teacher (and the job is interesting), I might be inclined to do that, instead. Time will tell...

Identity Theft?

This is a bit disturbing. I just received a registered survey from the Democratic National Committee. A few assorted lines from the thing:

"You have been selected to represent your city in the 2007 Grassroots Survey of Democratic Leaders. Survey documents registered in your name are enclosed."

"Dear Fellow Democrat,
...
I am asking you to take part in this survey because, as a Democratic leader in your community, your insights about the critical issues facing our nation are important to us."

This is disturbing because, in fact, I am not registered with any party, am not a political leader of any kind, and am not even registered to vote right now. It makes me wonder who's been voting under my name...

The Rules of Slashdot

Saw this post on Slashdot, and thought it was humorous:

1. We love Apple (especially when they do something just like Microsoft, and even more if their product is vaporware).
2. We hate Microsoft (especially when they do something just like Apple, and even more when their product is vaporware).
3. Steve Jobs can do no wrong (especially when he does the same as Bill Gates).
4. Bill Gates can do no right (especially when he does the same as Steve Jobs).
5. Any story that is positive about Bill Gates or Microsoft will get tagged "fud" or "troll".
6. Any story that is negative about Steve Jobs or Apple will get tagged "fud" or "troll".
7. "One Laptop Per Child" is the second coming of Christ.
8. Nicholas Negroponte is Christ.
9. We ignore Sun (especially when they dominate any specific industry).
10. We adore Java (even though it was developed by Sun).
11. It has been "The Year That Linux Takes Over the Desktop" for about 8 years.
12. It has been "The Year That Microsoft Dies" for about 15 years.
13. It has been "The Year That Apple Overtakes Microsoft" for about 10 years.
14. Ubuntu is God's chosen Linux distribution.
15. All other distributions of Linux are wannabes...especially the ones that have been around longer than Ubuntu.

I Win

So, yesterday my program at work (a configuration tool for their server product) went into official Q/A, and I've acquired a list of bugs (six so far). Some of these are absolutely hysterical. Take this one, for instance:

On two of the different servers we were setting up for our test networks, the computers froze after clicking finish with the connect now checkbox checked. This happened on both servers that made it that far.

One of the servers that froze seems to have completely screwed up the subnet it was on until it was unplugged from that router. In other words, workstations on the same subnet could not pass traffic through the router or renew their IP address from the dhcp server until the computer was unplugged from the router.

I was laughing out loud for about 20 minutes straight after I read that bug report. Besides the obvious hilarity of a single computer downing an entire subnet, my program runs entirely in user mode, and it would be a huge security hole in the OS if a user-mode program could wreck this kind of havoc. I suspect this is actually a bug in the server (which has a driver component) or the backend (which feeds instructions to the server), though I haven't started investigating, yet.

Tricks of the Trade - Collocation

Way, way back I explained what "fast" is, with regards to synchronization objects. Briefly, a fast object is one that executes entirely in user mode, save for two times: when a thread needs to go to sleep, and when a thread needs to be woken up.

But that isn't fast enough for some people. As discussed previously, fast objects work by using atomic instructions and/or memory barriers. While atomic instructions in and of themselves aren't THAT bad, speed-wise (in the best case taking only about 20 cycles), on some architectures (like x86) they imply either a write barrier or a full barrier. By definition these are constriction points, which bring the various parts of the system into sync, and require waiting for all pending writes/operations to complete. In the best case (no queued I/O) this may be almost instant. In the worst case (many queued I/O accesses), it may take hundreds of cycles. Even though this only applies to one CPU/core, that's a pretty large amount of dead time (for example, you might be able to call malloc in that time).

But is it possible to avoid the use of atomic operations altogether? Well, yes and no. It's impossible to have a multiprocessing system that shares resources completely without atomic operations (well, I suppose you could, but it would be hideously ugly and slow). There must be some way to synchronize code or data between threads and processors - atomic operations provide this ability.

However, in very specialized circumstances (and only from some threads), we can get around using atomic operations. One way to achieve this is called collocation. Collocation is the storage of two (or more) pieces of data - one accessed by one thread, the other accessed by another thread - inside a single word. The thread's data is written to using a small write, then the entire word is read at once.

Collocation relies on data dependency to cause a partial processor stall without the need to perform a full memory barrier. Most processors are always self-consistent and have instruction ordering rules that state that a write to a memory location smaller than a word must be committed to memory (actually, cache, but CPU caches are typically coherent, meaning all CPUs will see modifications to the cache of one CPU) before a larger read from that same location. This can be done using nonatomic operations, and does not require a memory barrier - it forces ordering only on two instructions, while allowing the processor to optimally reorder and buffer all other instructions. In the worst case, this causes a full pipeline flush (20-30 cycles), and may take less - significantly faster than a full memory barrier, in the worst case.

However, this method is not an exact substitute for atomic instructions. It only ensures that both writing and reading threads will see the writes made by each other - it does not provide a way for either thread to know in what order the writes occurred, the way atomic instructions can. So, what use is it? Well, if you apply some creativity, it's still useful in some cases. To be able to take advantage of collocation, the threads sharing data must be fundamentally asymmetric - each thread must write to a separate fields in the word, and only one thread may use collocation to avoid atomic operations (the other threads must use atomic operations). This implies where collocation is useful: when one thread performs a large portion of the writes, and other threads only make occasional writes.

This is just an introduction to collocation as a lock-free structure tool; the posts on super-fast mutexes and condition variables with timeout will give some real-world examples of how atomic operations can be avoided using collocation.

Tools of the Trade - Atomic Primitives

In the wake of the recent memory barriers series, today we continue looking at topics related to multiprogramming, by taking a survey of the various atomic primitives. This particular topic is more for informational value than practical use (at least as far as LibQ is concerned, which does not support all of theseso you do not need to know the differences).

Atomic primitives are arguably the most important tool in programming that requires coordination between multiple threads and/or processors/cores. There are four basic types of atomic primitives: swap, fetch and phi, compare and swap, and load linked/store conditional. Usually these operations are performed on values the same size as or smaller than a word (the size of the processor's registers), though sometimes consecutive (single address) multiword versions are provided.

The most primitive (pun not intended) is the swap operation. This operation exchanges a value in memory with a value in a register, atomically setting the value in memory and returning the original value in memory. This is not actually very useful, in terms of multiprogramming, with only a single practical use: the construction of test and set (TAS; or test and test and set - TATAS) spinlocks. In these spinlocks, each thread attempting to enter the spinlock spins, exchanging 1 into the spinlock value in each iteration. If 0 is returned, the spinlock was free, and the thread now owns the spinlock; if 1 is returned, the spinlock was already owned by another thread, and the thread attempting to enter the spinlock must keep spinning. Ultimately, the owning thread leaves the spinlock by setting the spinlock value to 0.

C/C++ - Code

1. ATOMIC word swap(volatile word &value, word newValue)
2. {
3. word oldValue = value;
4. value = newValue;
6. return oldValue;
7. }
9. void EnterSpinlock(volatile word &value)
10. {
11. // Test and test and set spinlock
12. while (value == 1 || swap(value, 1) == 1) {}
13. }
15. void LeaveSpinlock(volatile word &value)
16. {
17. value = 0;
18. }

This makes for an extremely crude spinlock. The fact that there is only a single value all threads share means that spinning can create a lot of cache coherency traffic, as all spinning processors will be writing to the same address, continually invalidating each other's caches. Furthermore, this mechanism precludes any kind of order preservation, as it's impossible to distinguish when a given thread began waiting; threads may enter the spinlock in any order, regardless of how long any thread has been waiting to enter the spinlock.

Next up the power scale is the fetch and phi family. All members of this family follow the same basic process: a value is atomically read from memory, modified by the processor, and written back, with the original value returned to the program. The modification performed can be almost anything; one of the most useful modifications is the add operation (in this case it's called fetch and add). The fetch and add operation is notably more useful than the swap operation, but is still less than ideal; in addition to test and set spinlocks, fetch and add can be used to create thread-safe counters, and spinlocks that both preserve order and (potentially) greatly reduce cache coherency traffic.

1. ATOMIC word fetch_and_add(volatile word &value, word addend)
2. {
3. word oldValue = value;
4. value += addend;
6. return oldValue;
7. }
9. void EnterSpinlock (volatile word &seq, volatile word &cur)
10. {
11. word mySeq = fetch_and_add(seq, 1);
12. while (cur != mySeq) {}
13. }
15. void LeaveSpinlock(volatile word &cur)
16. {
17. cur++;
18. }

Next is the almost ubiquitous compare and swap (CAS) operation. In this operation, a value is read from memory, and if it matches a comparison value in the processor, a third value in the processor is atomically written in the memory location, and ultimately the original value in memory is returned to the program. This operation is very popular because it allows you to perform almost any operation on a single memory location atomically, by reading the value, modifying it, and then compare-and-swapping it back to memory. For this reason, it is considered to be a universal atomic primitive.

1. ATOMIC word compare_and_swap(volatile word &value, word newValue, word comparand)
2. {
3. word oldValue = value;
4. if (oldValue == comparand)
5. value = newValue;
7. return oldValue;
8. }

Some architectures (such as the x86) support double-width compare and swap (atomic compare and swap of two consecutive words). While this is convenient, it should not be relied upon in portable software, as many architectures do not support it. Note that double-width compare and swap is NOT the same as double compare and swap (which we'll look at soon).

Another universal atomic primitive is the load linked/store conditional (LL/SC) pair of instructions. In this model, when a value is loaded linked into a register, a reservation is placed on that memory address. If that reservation still exists when the store conditional operation is performed, the store will be performed. If another thread writes to the memory location between a load linked and store conditional, the reservation is cleared, and any other threads will fail their store conditional (resulting in skipping the store altogether). If the store conditional fails, the program must loop back and try the operation again, beginning with the load linked.

In theory, the load linked/store conditional primitive is superior to the compare and swap operation. As any access to the memory address will clear the reservations of other processors, the total number of reads is 1, in contrast to the 2 reads with compare and swap (1 read to get the value initially, and a second read to verify the value is unchanged). Furthermore, the LL/SC operation may distinguish whether a write has occurred, regardless of whether the value was changed by the write (we'll come back to why this is a good thing when we discuss hazard pointers). Unfortunately, my research indicates that most implementations of LL/SC do not guarantee that a write will be distinguished if the written value is the same as the value at the time of the reserve.

Finally, the wild card: the double compare and swap (DCAS). In a double compare and swap, the compare and swap operation is performed simultaneously on the values in two memory addresses. Obviously this provides dramatically more power than any previous operation, which only operate on single addresses. Unfortunately, support for this primitive is extremely rare in real-world processors, and it is typically only used by lock-free algorithm designers that are unable to reduce their algorithm to single-address compare and swap operations.

1. ATOMIC void double_compare_and_swap(volatile word &value1, word newValue1, word comparand1, word &oldValue1, volatile word &value2, word newValue2, word comparand2, word &oldValue2)
2. {
3. oldValue1 = value1;
4. oldValue2 = value2;
6. if (oldValue1 == comparand1 && oldValue2 == comparand2)
7. {
8. value1 = newValue1;
9. value2 = newValue2;
10. }
11. }

Lastly, note that I'm using rather loose classification of these primitives. Technically, you could place the swap (fetch and store) operations in the fetch and phi family, as well, but it seemed more intuitive to me to separate them.

Philosophers at a Table

Creating a deadlock-free semaphore-based implementation of the dining philosopher problem isn't particularly difficult. All you need to do is implement a chopstick pickup order that does not allow deadlock. The method we used (although you could just as easily do the opposite) is to have each philosopher pick up their even-numbered chopstick first, then their odd-numbered chopstick afterwards. This guarantees that, regardless of the number of philosophers n at the table (as long as there're two chopsticks, smartass), at least one will be able to eat at any point, with a maximum of n / 2 (rounded down) being able to eat at once.

I initially thought (and indeed said in my report) that the condition we were seeing, where only one of five philosophers was able to eat, was a consequence of there being an odd number of philosophers. While I was correct that the odd number had an important part in what we were seeing, the problem was more general than I thought. This diagram of an eight-philosopher table shows the worst case scenario for an even number of philosophers:



What's happening here is as follows:
1. Philosopher 0 picks up chopsticks 0 and 1, and begins eating
2. Philosopher 1 picks up chopstick 2, and blocks on chopstick 1
3. Philosopher 2 blocks on chopstick 2
4. Philosopher 7 blocks on chopstick 0

In this order (or a few variations of it), one philosopher has managed to prevent three others in a cluster from eating. The exact same method can be used to block three others, while a total of two philosophers eat; this is the worst-case scenario for this table.

You can draw it out for yourself (I drew it on paper, along with several other sizes, but don't feel like making more diagrams online) and prove that it's possible for a minimum of two philosophers to eat at a table with only six philosophers. This is logical: one philosopher can only block three others, leaving three chopsticks available; one of the last two philosophers will be able to eat.

So, four philosophers is too few (for two philosophers to eat), six is enough, but what about five? This was the classic case, and the one we implemented. What happened is this, shown in words and figure:



1. Philosopher 1 picks up chopsticks 2 and 1, and begins eating
2. Philosopher 2 blocks on chopstick 2
3. Philosopher 0 picks up chopstick 0, and blocks on chopstick 1
4. Philosopher 4 picks up chopstick 4, and blocks on chopstick 0
5. Philosopher 3 blocks on chopstick 4

As you can see, the problem is that one philosopher (#4) has two even-numbered chopsticks (#4 and #0), meaning that regardless of the order in which he tries to pick them up, it's gonna screw up the ordering. In fact, what happens is that this allows an additional philosopher to block on one eating philosopher, bringing the total in the cluster to five - the number of philosophers at the table.

Oh, and for those keeping score, the minimum number of philosophers that are able to eat at any time appears to be (n + 2) / 4.

Moshikashite Kore Sugoku Warui

Be afraid. Be very afraid. Q has just learned about Starfish. Even if it's old as dirt, this can't possibly be a good thing. Some of the stuff it generated:



















Oh, and for the curious, that phrase is from Azumanga Daioh, one of my favorite mangas. Naturally translated, it means "This could be really bad": もしかして [possibly] これ [this] 凄く [terribly] 悪い [is bad].

Memory Barriers 3 - The LibQ Way

Okay, so those are the constraints within which LibQ must work. This brings me to my first critical design decision regarding memory barriers: LibQ will use hand-coded assembly functions, and client programs will call these functions through pointers (well, the functions will indeed be called through pointers, but this is transparent to the client program), allowing the fastest option to be chosen at run time based on the system.

Okay, that was fairly easy. This second decision took a lot more thinking through to reach a conclusion: what to do with respect to atomic functions? There are at least three options that are fairly obvious. The first is to provide the weakest possible guarantee: that all atomic functions are not memory barriers. This ensures that users will use memory barriers manually, and even on architectures where atomic instructions are not memory barriers the correct behavior is achieved.

However, evaluation of this possibility suggests that it is not a good option. While non-barrier atomic operations will run at maximum speed, particularly on weak architectures like PowerPC, adding in additional memory barriers on architectures like the x86 quickly kills performance. Consider the worst case scenario: an atomic operation that must have a full sandwich barrier, on a Pentium 3 (which has no full memory barrier instruction, and so must use a serializing instruction) - perhaps 100 cycles for the LOCK, another maybe 150 cycles to flush buffer contents, and two CPUID instructions at about 65 cycles each; all together, that's 385 cycles. This could be reduced by about 1/3 by leaving out the CPUIDs, as LOCK instructions are full barriers on the Pentium 3.

Alternately, we could provide the strongest possible guarantee: that all atomic instructions are full sandwich barriers. This means that users don't need to worry about putting memory barriers around atomic instructions at all, and ensures barrier safety.

However, this also is not a particularly good solution for a cross-platform library like LibQ. This strategy is optimal for the Pentium 3, where that's exactly how atomic instructions work. On Pentium 4 it's only slightly worse, as two MFENCE (or LFENCE) instructions would only add only a couple dozen cycles to the atomic operation and memory flush. However, this could be bad on weaker architectures like PowerPC. Memory barrier instructions there are comparable to the cost of a CPUID, and at least one is unnecessary most of the time (not often do you need a full sandwich barrier around an atomic operation).

The third option is to make special versions of LibQ atomic functions for each variation. While this has the advantage of providing maximum speed on all architectures (and removing function call overhead wherever possible), it would be a huge pain in the ass for me and anyone else who writes all the functions. Let's think about this: 3 types of memory barriers, 3 barrier configurations, times how many atomic function? That's like 50 or 100 different functions for each platform. Mr. Flibbles doesn't much care for that.

So, what should I do? Fortunately, there's a variation on one of these (or perhaps a hybrid of two of them) that is both easy for me to code and efficient with respect to CPU cycles (not 100% optimal, but tolerably close): option number one. Atomic instructions are not guaranteed to be memory barriers of any kind. HOWEVER, there are special memory barrier functions used to promote atomic instructions to memory barriers.

This requires only 6 functions - 3 different types of barriers, 2 configurations (sandwich is just top + bottom barriers). Using this system, these functions may function as necessary, and be no-oped as necessary, to provide (almost) maximum speed. The only waste is the overhead of one or two functions calls; my benchmarks suggest that this is a minimal increase, not taking more than 10 cycles per function - 4 to 12% waste for two barriers, when neither are necessary.

Another Exercise for the Reader

Something I'm currently coding in LibQ (*shock and awe*) is the capacity for timeouts in waits on a condition variable, a feature that was left out of LibQ originally, because of an insurmountable race condition which would be created by the way LibQ emulated condition variables on Windows. This challenge is very succinct: how is it possible to create a fast (remember the definition of fast, with regard to synchronization objects) condition variable that supports timeout, and what constraint(s) would exist on the semantics of this condition variable? Ready, set, go!

Oh, one more thing: if you find that challenge too easy, you can try to do it without the use of atomic operations (the way LibQ does it).

Memory Barriers 2

Subtitle: Speeding Up, Slowing Up, Maybe Even Blowing Up

It has always been my intention to fully support memory barriers in LibQ. However, as LibQ is mainly something I work on when I'm feeling inspired, it shouldn't be too surprising that some features take a while to get implemented (especially at the times when I don't feel like coding anything for a few months). But while lack of interest on my part may have been the biggest factor, there was also the fact that I hadn't, until recently, decided on the semantics of LibQ memory barriers.

Stand-alone memory barriers (memory barriers in the middle of a sequence of normal code) are (mostly) straightforward, both in concept and in implementation. However, the exact method of achieving a memory barrier differs drastically by architecture. For example, the x86 guarantees that stores will be performed in order. As such, write barriers are not needed at all (or you could use an SFENCE instruction, if you want to play it safe and assume that this guarantee of write ordering won't be around forever). However, the x86 has no read barrier or full barrier instructions prior to the Pentium 4 (LFENCE and MFENCE instructions, respectively); the conventional wisdom has been to use a serializing instruction whenever these functions are needed (CPUID seems like a fairly good candidate on Pentium 4, while LOCK CMPXCHG seems faster on other CPUs).

The Alpha deserves special mention, as it does something that, as best I and the Linux people know, is truly novel (thank God). For reasons that appear to be a consequence of the split cache model (having multiple cache banks per core, which may be locked separately to avoid memory stalls), the Alpha does not have true memory barriers. While its memory barriers will order instructions for that CPU, there are no guarantees that the access order will hold on other processors. Amazingly (and not in a good way), this even applies to pointer dereferences; that is, if you set a shared pointer after initializing the structure, it's possible that another CPU could get the new pointer, yet pull uninitialized data through the pointer. This means that not only must you have a write barrier between two writes if they must appear in order, but you must also have a read barrier between the reads of those two variables; the read barrier will ensure that the caches will be brought into sync on the reading CPU.

Moving tangentially, different architectures have different semantics for their atomic functions. On a Pentium 3 (and other Intel CPUs before Pentium 4), LOCKed atomic operations (required to be truly atomic with multiple cores and/or CPUs) are synchronizing instructions (effectively full barriers). However, in Pentium 4 they have been demoted to simply being write barriers. As best as I can tell, on the PowerPC atomic instructions aren't memory barriers at all. Nor are atomic x86 instructions that do not use LOCK (not using LOCK is much faster, but only atomic with respect to a single core/CPU).

This is made even more complicated by the fact that there are three possible configurations for a memory barrier to be in, with respect to an atomic operation. In the acquire configuration (think of acquiring a mutex), the memory barrier appears to be just after the atomic operation - the atomic operation can be executed earlier than where it appears, but no I/O after it (inside the mutex) may be executed before it. In the release configuration, the barrier appears to be just before the atomic instruction - I/O after the atomic operation may be executed before the atomic operation, but the atomic operation cannot occur before any I/O in front of it (inside the mutex). Finally, there's the sandwich configuration, where instructions are serialized around the atomic operation, as if there was one barrier before the operation, and one after - the atomic operation cannot be executed before any preceding I/O, and no subsequent I/O may be executed before the atomic operation.

Exercise for the Reader

So, in one class I'm writing implementations of the dining philosophers problem (note that a variation uses chopsticks and rice) using both semaphores (it is possible to prevent deadlock if you're careful) and mutex/conditions. Running tests on it, I noticed something odd - a semi-deadlock state in the semaphore version; that is, a single philosopher was taking his time eating, while none of the others could eat (they couldn't get a hold of a pair of chopsticks). It took me a little bit to figure out what was going on (because I knew that if the teacher saw that he'd ask me if it was broken).

So, here are the questions for you:
1. How do you implement a deadlock-free dining philosophers system using semaphores?
2. How could a single philosopher block all four others all by himself?

Memory Barriers

Well, I felt like writing something; however, this post might not turn out that great, as I've got a lot of material to cover, which I may or may not be able to elegantly separate into multiple topics (as it's too much to cover in one post).

Conceptually, computers execute instructions in single file. An instruction and its parameters (if applicable) are read from memory, the instruction is executed, and the results are written back to memory (if applicable). For some CPUs (that's all I can say, due to my indiverse knowledge of various CPUs), such as the x86, that's exactly how they originally worked. However, the x86 has gotten dramatically more complex over the last ten years or so. The 486 (I'm giving these milestones to the best of my memory, but I can't say for certain they're all correct) added support for multiple x86 microprocessors to run in parallel in the same system. With the Pentium, a second arithmetic logic unit was added, allowing the processor to execute two instructions in parallel. The Pentium Pro added support for speculative memory reads (prefetching of data used by instructions not yet executed), and added a memory write buffer that stores memory writes before they even make it to the processor's internal cache. The Pentium 4 allows two threads to be executed on a single processor, by means of instruction stream interleaving. With the Pentium D, CPUs began to contain two cores in a single chip, and Intel is about to launch a Core 2 CPU containing four cores on a single chip.

What all this comes down to is that it is no longer possible for a programmer to know the exact order instructions will be executed in a program. Thanks to speculative reads and the uncertainty of exactly what is in the cache at any point, execution is nondeterministic, and it is even impossible for a nerd with a calculator and an x86 optimization manual to calculate exactly what order a set of assembly language instructions would be executed in (at least not in the general case; in highly serialized code it might be possible). Moreover, even implementations of x86, such as the Pentium 4, Core 2, and Athlon 64, differ in implementation details, such as execution time of particular instructions.

However, as the processor (actually core) is always self-consistent, this is normally completely transparent to the programmer. The result of a calculation will always be deterministic, and strictly dictated by instruction order, even if the actual order of events inside the processor to arrive at the end result differs wildly. The only time when a programmer must be concerned with such details is when processor self-consistency is not sufficient - that is, when they are writing a program that much synchronize execution with something outside the core, such as a piece of hardware, another chip or processor on the motherboard, or even another core. While largely irrelevant for everyone else, writers of hardware-interface code (drivers) and of core operating system parts must be able to ensure that the internal state of the processor remains consistent with the world outside the processor. At least, those that don't work for Creative Labs.

There are many ways of accomplishing different aspects of this requirement, and the methods often vary by processor. Main memory is one of the things most commonly shared by the the processor and other hardware, so it is necessary that the hardware hear exactly what the processor is trying to tell it. The x86 processor orders its memory accesses relatively strongly. The Pentium 4 guarantees that writes will be performed in the order they appear in the program; however, writes may be buffered before being committed to the processor's cache, and there may be further delays before the data is written to main memory. Furthermore, it makes no guarantees about the order of reads from memory (and, remember, reads can be performed even before the instruction to perform the read is executed). It could be disastrous for another processor (including processors on hardware devices) to mix in its own data with what one processor is writing, or read data that one processor is still in the process of writing.

Memory barriers (also called fences) are used to prevent this. They instruct the processor to create a memory bottleneck at the memory barrier instruction, which some class of memory accesses may not cross. A read barrier in between two reads will ensure that the second read (or any later reads) may not be executed before the first; the same goes for write barriers and full barriers.

Serializing instructions take this one step further, not only guaranteeing the order of memory access with relation to the serializing instructions, but also preventing ALL execution of subsequent instructions until the preceding instructions have entirely finished executing and the results have been written to memory. This is something you want to avoid whenever possible, as it's a major performance killer, with the potential to soak up hundreds of cycles in dead time (although, to be fair, fences also a performance hazard, though not as large of one, as other instructions and some types of memory accesses may still execute across the fence).

Interrim

While you're waiting for the my next big post (whenever that'll be, although I do have one I'm "working on"), you need to go watch Death Note. Really. Even if you don't like anime. No ecchi (breasts, panties, etc.), no giant robots, no DBZish fighting scenes, no ridiculous comedy, no shooting machine guns out of Ferraris at 150 MPH; just pure brainpower and sometimes adrenaline-pumping suspense. Unless the quality drops off steeply before the end of the series (less than one third of the series has aired so far), it'll definitely make my list of best animes ever.

Go! Watch! Now!

Oh yeah, and the manga (graphic novel) version is out in English (well, about 2/3 of it, so far), if you prefer to read (Amazon carries it, and local book stores probably do, as well). I'll probably buy that around Christmas.

& Bad Teacher Tricks

Warning: Rant ahead.

So, I just got my grade on my first test in operating systems class, and it was a three-fold disappointment (for three different reasons). The score itself was a 69% - an abysmal score for somebody whose straight-A record wasn't broken until the third semester of college. However, next to the score was a letter grade - an A. That's right, an A. To add insult to double-injury, the teacher showed the grade distribution. Out of the whole class, there were two As. That means that my grade of 69 was either the best or the second best grade in the entire class.

It shouldn't take much effort at all to realize that something is very, very wrong with this situation. How could a 69% possibly be even the second highest score in the class? There appears to be a certain mentality to it - the teacher seems to believe that curving the scores makes up for abysmal test writing.

Another example of a test I had with this teacher was a problem involving B+ trees, using variable length name fields. I can't remember what the exact problem was, but after looking at it for a couple minutes I called the teacher over to ask about it. The conversation went something like this:
Me: Is it just me, or is it theoretically impossible to solve this problem?
Teacher: It's possible
Me: How? This buffer is too small to store this much data
Teacher: Just assume that the average length will be less than [some number I don't remember] [note that this could - in theory - work because if the average name length was small enough it would fit]
Me: That assumption isn't realistic at all, and is never suggested anywhere in the problem. In fact the problem kind of suggests that it wouldn't be true...

A similar incident (actually more than one) occurred on this test, only it was after the test had already been graded. He had built an implementation-specific algorithm assumption into the answer he counted as correct (without ever mentioning this assumption in the problem). If, like I did, you gave a more general answer that would be true regardless of implementation, you got a 0. His excuse for this was that the typical implementation allows this assumption, never mind the fact that we also discussed in class an alternate implementation which violates this assumption. This annoyed me all the more because I got a later problem wrong for making an "invalid" assumption about the problem, based on the fact that that's typically how it's done in practice.

Then there are the enjoyable classes where the teacher thinks that they can get away with bad tests without curving, simply by making homework weigh more in the class total, relying on the homework grade to bring up the overall scores to acceptable levels.

Let me state it very clearly: if your first or second highest score in the class is a 69%, there is something wrong with your tests. If you consider the ability to ask the teacher questions to be a good alternative to making your questions clear, there is something wrong with your tests. If you have to make non-test things have a very high weight to compensate for very low test scores, there is something wrong with your tests.