Evolution of the Unix System Architecture: An Exploratory Case Study

Proprietary UNIXes had already gone through this, and scaled up to pretty big machines like the Sun E10K. Although none were aimed at small desktop machines, and they tended to have a reputation (deserved or not) for being weighted down by, among other things, locking ("Slowaris"). Complex layers of locks, which open source developers feared would result in a complexity explosion that would sink their kernels.

Linux famously was granted the use of the patented RCU algorithm by IBM, and that's the way they went. Linux does have a lot of locks and locking complexity, but RCU massively helped on that front. The free BSDs did trail in scalability but they ended up developing other similar techniques and lock management and debugging facilities that has seemed to hold them in pretty good stead despite the huge developer-hours advantage Linux has.

All this stuff was pretty interesting to me so when OpenSolaris was released later, I had to take a look and see what they did. And it was a big clunky looking thing. They had big hash tables of locks, layers of them. Hashes of locks is a simple trick for scalability which can work very well, but it also constrains your data structures significantly. A nice salable and cache-friendly tree can't (so easily) be used with hashed locks, hash tables are the more natural structure you're steered to. Which can be great and simple for some cases, but are not very cache friendly in most accesses with locality (even cache friendly hashes are a bit hacky or at least come with tradeoffs, not that I remember seeing any of those).

I went back and looked at it again -- like a page cache page lookup in Solaris was layers locks, recursive locks etc.

inode->i_contents rwlock(R) (may be recursed)

page pse mutex (protects page selock)

page selock (shared/exclusive, custom lock)

page hash lock (hash of locks protecting page cache hash table)

4 locks, they all nest, recurse, etc, and they tend to be these complex boutique special lock functions -- the page se mutex and hash locks are taken and released by special locking functions (usr/src/uts/common/vm/page_lock.c) hundreds of lines of special lock beahvior.

It looks like the hash lock can be avoided in the fast path, but I list it because the nature of it means the page cache structure is a global hash table (which doesn't scale in terms of memory usage, and has poor cache locality, and problematic collision QoS issues, possibly DoS type attacks between privilege domains, etc. Just a poor, clunky data structure for the job.

The equivalent path in Linux has no locks: lock-free lookup of a tree attached to the inode to find the page and increment its refcount.

It really is quite amazing the leaps and bounds this type of scalable programming techniques have come since the turn of the century contrasting Linux and Solaris (today now Linux is much more scalable than Solaris ever was). I can absolutely see why people were so worried these things would end in a complexity death spiral.