LWN: Comments on "KHB: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services"

KHB: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

xoddam — 2009-07-27T08:27:43+00:00

Any concurrency primitive for shared-memory multiprocessors on commodity hardware must for performance reasons be implemented at the cache-coherency level, using message passing (rather than having to hit the underlying slow, shared RAM on every synchronous operation) and is therefore several orders of magnitude more complex in silicon than anything that can be done "with 1 bit".

See http://lwn.net/Articles/252125/ (scroll down to section 3.3.4, Multi-processor support).

CAS and the spicier double-word CAS are obviously 'trickier' in some sense than LL/SC but both must be implemented by grabbing exclusive access over a cache line (maybe two in the case of double-word, I suppose). The underlying mechanics are the same.

KHB: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

asdlfiui788b — 2009-07-26T16:28:12+00:00

Perhaps this is trolling but... I used to think that lock free algorithms based on CAS were a good idea, until I saw how the Alpha handled this. Load-Linked / Store-Conditional is more natural for hardware and also a damn sight more useful as it prevents the ABA problem (I've played with some quiescence algorithms for memory allocators to get round this but it's still ugly and difficult to implement). If you're interested in this sort of thing I'd strongly recommend looking up LL/SC and this kind of problem. While you're at it, look at Hans Boehm's paper on implementing LL/SC with 1 bit and a trivial amount of circuitry; it's so much easier that CAS and pretty much trivial to implement.

re: Synthesis: Operating system of the future?

olecom — 2008-05-24T03:23:03+00:00

As a matter of fact eight-year developer of PowerPC Linux port Cort Dougan has citations of
Massalin's work in his research and application publications.

Bottom line, as far as i can see, can be read here:

Cort Dougan: Good Programmers are not Lazy. unpublished draft.
http://hq.fsmlabs.com/~cort/papers/lazy/lazy.nohead.html

A must read.

Ouch, fsmlabs and software patents? Microsoft has patent on double-click, so what? Now Novel,
RH and others have all that protecting-patents dance. Thus, sw patents in this case are
irrelevant. About sw freedom and money, please read the article.

Great writeup!

PaulMcKenney — 2008-04-03T19:50:14+00:00

Let's see, page 139:123...

Fully coherent instruction caches do exist on some systems. Replicated registers for fast
interrupt handling were present in some 8080-based CPUs back in the late 70s and early 80s,
but have fallen out of favor, though one might get the same effect on modern multithreaded
hardware by reserving one thread to process interrupts on behalf of the other, but not sure
that this would be worthwhile. Double-compare-and-swap is indeed useful, but doesn't exist on
the systems I have access to, despite its appearing in the 68K line quite some time ago.
Large caches, large cacheline sizes, and very high memory bandwidths have reduced the urgency
of partial-register saving, and again, in some cases you could assign processes to hardware
threads -- but perhaps this will become more compelling in the future. Some CPUs have vector
operations that do some of the multi-byte operations (e.g., SSE, 3DNow, Altivec, ...), and
perhaps compilers will become more aggressive about implementing them. Some of the fancier
bitwise operations are indeed useful in some contexts, so who knows.

But I do apologize for my extreme bigotry in favor of hardware features that I can use today
across a wide variety of CPU types. ;-)

The operating systems I work with -do- have priorities, so I don't get to ignore them.
Perhaps more sophisticated scheduling policies will come into vogue. There are certainly
people working on this. In any case, stock Linux running on commodity microprocessors does
context switches orders of magnitude faster than the one-millisecond figure called out on page
142:126 -- old-style Moore's law at work.

Hardware cache-coherence protocols coupled with high software memory contention really can
result in priority-inversion-like effects. I have seen this, logic analyzer and everything.
Would you care to outline your objections in more detail?

Great writeup!

olecom — 2008-03-20T19:24:02+00:00

> NBS algorithms rely heavily on hardware arbitration, which is usually
> unaware of process priorities.

There are no priorities and scheduler is I/O rate-based, PLL-managed.
On pdf.page 139 (123) find some ideas for hardware and open yor eyes
(pdf.page 142 (126).

> This can result in priority-inversion-like effects when the hardware
> gives the contended cache line to the low-priority process.

Oh, read whole dissertation, please.
_____

KHB: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

nix — 2008-02-28T20:59:02+00:00

Insane?

Oh.

So, er, I should be ashamed that I did almost exactly that (via a custom 
allocator layered atop big mmap()ed hunks) in C about a year ago? (Well, 
it was more like a twisted sort of RCU: I'd construct a new instance that 
was a copy of the old one with a zero reference count, then changing 
pointers in the new instance's VMT-analogue, translating the object's data 
into a new representation at the same time. The old instance got 
reference-zapped when nobody was executing methods via those pointers 
anymore.)

(yes, there were pressing reasons. It was a bundle of fun, as well. :) )

The Kernel Hacker's Bookshelf: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

renox — 2008-02-28T19:11:43+00:00

>> When the callback for queue empty happens, the code to operate on the queue is switched to
use the lock-free synchronization code. When the quaject's queue-not-empty callback is
invoked, the quajects switch back to the synchronization-free code.
>
>Whoa...  that ran shivers down my spine.  What an outrageously cool idea.

Uh? I don't think that it's a particulary original idea..
But implementing this efficiently on the other hand, this seems quite hard to do!
I have some difficulties downloading the PDF, so I cannot read the paper yet..

Lock-free operations

forthy — 2008-02-28T11:48:46+00:00

There are a number of ways to do efficient lock-free operations even without resorting to a locked operation in some circumstances. Take e.g. the single-writer, single-reader queue with a finite size: All you need is a circular buffer and two pointers. The writer only writes to the end of the queue and updates only the high pointer after writing. The reader reads from the start of the queue and updates the low pointer after reading.

Or allocation/freeing of objects in a multi-processor system: Each core frees only those objects it allocated itself. Other cores can post "free this object" into a single-writer, single-reader queue, or mark objects as free and have them scanned while idle. You can even use a linked list if you keep at least one deleted object alive to avoid the empty-linked-list queue condition.

Another point is certainly serialization and deferring actions. One thing that comes in mind here is the user-kernel communication. In Linux, the user invokes a context switch into the kernel for every system call, and to make this context switch light-weight, the system call uses the user process, so in fact there are many kernel threads, which will require synchronization (in early Linux days, there was the BKL, so the kernel was serialized). If you change the syscall interface to a command queue (think of the X server), you can probably afford a more heavy-weight context switch, and less kernel threads. This however significantly changes the interface paradigm to the kernel - Unix-like syscalls do not fit well. Even the X server has too many functions which require round-trips. The upside of this change is that a network transparent kernel interface becomes feasible - and performance in clusters would improve significantly.

KHB: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

pphaneuf — 2008-02-27T22:51:02+00:00

My way is ugly. That way is insane.

Still, I wish it was possible to manipulate vptrs and vtbls more in C++. Things like having two different implementations of a virtual method with the same signature inherited from two parents would make sense, for example (say, the "draw" methods you get while deriving from both Drawable and Cowboy).

KHB: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

zlynx — 2008-02-27T21:58:34+00:00

Your solution is not as ugly as another I've seen in C++ where the programmer used placement
new to reconstruct the object with a different derived type (but the same base type) in-place.

Now, that was scary.

KHB: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

pphaneuf — 2008-02-27T17:30:08+00:00

The trick of changing between two algorithms is pretty awesome, and something more or less like that could easily be done with many pieces of code in the kernel. I did similar things in user-space C++ code, by using callbacks for some things, where I basically encoded part of the state in the function pointer itself (in state A, point at do_state_A, in state B, point at do_state_B, something like that), which was kind of ugly in C++, as it basically was hand-coded virtual methods, so that I could change them at runtime (and per object).

But in the kernel, we're already implementing virtual methods by hand, and on top of it, we don't use per-class virtual method tables, but rather embed them in each objects already, which is exactly what we need! It's just that they are usually initialized once at object creation, we'd just need to use some atomic CAS to update a function pointer when some algorithm changes.

The trick part is when more than one method needs to change. Damn, I actually expect this would be common, too. Argh.

Oh well, it's pretty cool!

Callbacks and quajects

pdc — 2008-02-26T16:55:25+00:00

I think you would need to come up with some new programming language syntax that encapsulates
the special conventions of quajects and the locking primitives (sort of how Occam encapsulates
the CSP-style synchronization primitives of the Transputer), doing all the bookkeeping and
self-modifying code invisibly for you. Without a higher-level language to write programs in
you presumably are left with hand-edited and fragile assembly-language code...

The Kernel Hacker's Bookshelf: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

nix — 2008-02-24T13:42:31+00:00

Ah, but with Synthesis, the kernel can recompile iself! :)

Great writeup!

PaulMcKenney — 2008-02-22T18:06:59+00:00

Having this write-up, to say nothing of an online copy of Massalin's dissertation, would have
saved me much time back when I was doing my own dissertation.  ;-)  Good to see both now
available!!!

One of the key strengths of Massalin's work is the focus on determining what techniques work
well in given situations, and then matching up techniques with the corresponding situations.
"Use the right tool for the job!"

Although lock-free techniques can be quite valuable for situations requiring real-time
response, as can other non-blocking-synchronization (NBS) techniques, these techniques are not
a panacea.  NBS algorithms rely heavily on hardware arbitration, which is usually unaware of
process priorities.  This can result in priority-inversion-like effects when the hardware
gives the contended cache line to the low-priority process.

The Kernel Hacker's Bookshelf: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

mingo — 2008-02-22T10:46:20+00:00

Yes. Especially as today's CPUs move towards annotating cache lines and doing certain
optimizations of the generic functions by observing their usage and annotating specific
instructions. Creating _more_ code goes into the opposite direction.

The Kernel Hacker's Bookshelf: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

tcoppi — 2008-02-22T02:30:35+00:00

Thanks for this very insightful writeup, now I have yet another thing to read and become
immersed in instead of doing real work :P

The Kernel Hacker's Bookshelf: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

vaurora — 2008-02-21T21:42:30+00:00

> After realizing they were anything but maintainable, I chucked lock-free algorithms on my
> shelf of stuff that is academically fascinating but unrealistic for the real world.  Should
I
> take them back down and re-examine them?

My personal opinion is that lock-free algorithms are not a good generic synchronization
technique, and are definitely very very complex and difficult to understand.  However, in
certain specific cases, lock-free can be simple, elegant, and a huge performance advantage
over traditional approaches.  It's much like RCU - you wouldn't want to use RCU for every
synchronization problem, but when it comes to highly-shared read-mostly data in the hot path
(e.g., the dcache), it's worth the trouble.

It's kind of like my advice on choosing a file system: Use ext3 unless it's not
fast/big/whatever enough for you, in which case use XFS.  My recommendation is use locks
unless they have too much contention/complexity/whatever, in which case look into lock-free.

> > When the callback for queue empty happens, the code to operate on the queue is switched to
> > use the lock-free synchronization code. When the quaject's queue-not-empty callback is
> > invoked, the quajects switch back to the synchronization-free code.
> 
> Whoa...  that ran shivers down my spine.  What an outrageously cool idea.

I know... The whole damn dissertation is like that.

Advanced reading

vaurora — 2008-02-21T21:26:32+00:00

For people who want to get into detailed analysis of the applicability of the ideas in Synthesis, a good place to start is Section 7.5, "Objections." It's organized around the following questions:

"How much of the performance improvement is due to my ideas, and how much is due to writing in assembler, and tuning the hell out of the thing?"
"Self-modifying data structures are troublesome on pipelined machines, and code generation has problems with machines that don't allow finegrained control of the instruction cache. In other words, Synthesis techniques are dependent on hardware features that aren't present in all machines, and, worse, are becoming increasingly scarce."
"Does this matter? Hardware is getting faster, and anything that is slow today will probably be fast enough in two years." [*snicker* - Ed.]
"Why is Synthesis written in assembler? How much of the reason is that you wanted no extraneous instructions? How much of the reason is that code synthesis requires assembler? How much of Synthesis could be re-written in a high-level language?"

Code size and cache thrash

vaurora — 2008-02-21T21:18:42+00:00

The issue of code size and instruction cache usage is a very important one - one I didn't have space to talk about in this article, but which is addressed in the original paper/dissertation/book. The executive summary is that if you only do inline code generation when it makes sense and share code otherwise, the code size is fine. In fact, for certain types of functions, the code size is reduced by inlining the code directly instead of setting up all the arguments and calling the shared function code. (gcc can do this statically at compile time, Synthesis can do it at run-time too.)

For more detail, see section 3.4.1. I feel like I read another section addressing this but I can't find it right now...

The Kernel Hacker's Bookshelf: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

ikm — 2008-02-21T19:33:53+00:00

The bubble sort vs. quicksort would be an incorrect analogy. The idea here is to inject
several optimized versions of the same code. My arguing was that one generic version might
perform better than a multitude of specialized copies of the same code.

The Kernel Hacker's Bookshelf: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

bronson — 2008-02-21T19:10:39+00:00

More code does not imply slower.  Think bubble sort vs. quicksort.

Besides, it sounds like the recompilations only happen at exceptional times.  I highly doubt
that they result in the sort of cache thrashing that you imply.

The Kernel Hacker's Bookshelf: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

bronson — 2008-02-21T19:03:45+00:00

I played around with lock-free algorithms a year ago and came away with a rather dim view of
them.  It's easy to write a provably correct lock-free queue when you assume infinite memory
(something that most papers seem to do).  It's a lot messier when you need to ensure the safe
disposal of list items when you're done with them.

You mention he's using an atomic CAS.  Does he explicitly solve CAS's ABBA problem?  It's
easily solved if you assume infinite memory of course.  If you're on a real-world system, if
you're not careful, you can easily open yourself up to situations where CAS assures you that a
value is unchanged when in reality you lost out a long time ago and the ring has just wrapped.
(yes, it's not hard to solve if you're watching for it, but always having to worry about this
sort of subtlety is what makes working lock-free such a pain)

After realizing they were anything but maintainable, I chucked lock-free algorithms on my
shelf of stuff that is academically fascinating but unrealistic for the real world.  Should I
take them back down and re-examine them?

> When the callback for queue empty happens, the code to operate on the queue is switched to
use the lock-free synchronization code. When the quaject's queue-not-empty callback is
invoked, the quajects switch back to the synchronization-free code.

Whoa...  that ran shivers down my spine.  What an outrageously cool idea.

The Kernel Hacker's Bookshelf: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

ikm — 2008-02-21T18:06:59+00:00

The approaches described here seem to completely ignore the fact that the increased amount of
code would result in increased cache misses, possibly penalizing the program more than
benefiting it. Instead of using the special-case function f(p) for p == 1, it might be faster
to just call the generic one, just because it's in the cache already. Cache is everything
nowadays, so the algorithms should be tailored for cache efficiency. Having more code hardly
helps here.

Furthermore, it seems to be unclear when to optimize and for what data  the time spent
creating new code, the memory consumed to hold it, and, once again, the cache penalties
resulting from having it executed once in a while should all be worth it. The whole approach
feels like it can be simplified to the idea of 'having a compiler inside of the running
program used to recompile its parts in runtime', but somehow I fail to see too many benefits
in that. To my understanding, if one wants to optimize, the better way to do is to think more
about caches/cpus interactions. The "network channels" apporach is one nice example of that.

The Kernel Hacker's Bookshelf: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

nix — 2008-02-21T13:54:21+00:00

I'm not sure whether to thank you or curse you for posting this fascinating article (and
linking to the thesis). I've been infected now. I'm not going to be able to write hardly
anything in future without borrowing ideas from this.

I shall have to spread the pain by telling everyone I have ever met about it. :)

Mine too..

nix — 2008-02-21T13:51:16+00:00

It's definitely more elegant. It's more like the Emacs hooks-everywhere scheme than exception
handling, though.

(I've seen one program that approaches things in the same way as this does with its quaject
callbacks, and that's the ERC IRC client, which has a fairly conventional server core, but all
the actual processing is done by invoking hooks with names constructed from the type of the
server response; said hooks can then send messages back again, or whatever. Of course ERC
doesn't have all the *other* nifty stuff in Synthesis.)

(btw, isn't the cartoon at the end a picture of a quala, not a koala? --- sorry.)

Mine too..

deleteme — 2008-02-21T11:39:11+00:00

But I like those quaject callbacks I think it's more beautiful than doing exception throwing
and signal passing. But again maybe that's just my ignorance showing.. ;-)

The Kernel Hacker's Bookshelf: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

leighbb — 2008-02-21T11:09:20+00:00

Ow, my brain hurts.  I'll stick to the occasional kernel recompile.