DragonFly kernel List (threaded) for 2006-11
Re: Lockless algorithms [was Re: splxxx replacements?]
:What's going on with DragonFly ? It might be a good thing to have some
:technical discusssion on commit be summarized here as well. Apparently
:you folks decided to move away from tokens in favor of straight
:spinlocks since they were a pain in the ass to use and there was no public
:mention about this.
:Another thing I've heard is that your route table stuff went lockless,
:which is a significant change and worth noting as well as discussing. And
:fron IRC discussions, RCU is starting to be pushed by various people,
:What's going on with you folks and lockless algorithms ?
The route table work is rather significant, though it won't really
shine until Giant is removed from the protocol threads. Basically
the route table is now replicated across all cpus and thus can be
accessed by any given cpu with only a critical section for
We still use tokens in several major areas, but we have been shifting
the ones that were only being used to lock short codepaths over to
Basically DragonFly has five locking primitives:
* Critical Sections
Prevents preemption, Interrupts, and IPIs from occuring on the
current cpu only. Automatically released if the thread switches
away and is reacquired when the thread switches back. Typically
used to interlock operations local to the cpu.
Critical section calls are, for all intents and purposes, free.
They are implemented with just a small handful of instructions and
no locked bus cycle instructions. Overhead is less then 5 nS.
May only be used to lock very short code paths. Severe restrictions
on use. May not block while holding a spinlock. Automatically
enters a critical section. Deadlocks automatically detected and
will panic the system.
Spinlocks do not block or cause a thread switch to occur and can
be used in code paths that are not allowed to block.
It should be noted that spinlocks are NOT in any way similar to
FreeBSD's mutexes. In DragonFly spinlocks are considered to be
very, very low level mechanisms that are not to be held across
complex code paths.
May be used to lock long code paths. May be nested. Automatically
released if a thread blocks or switches away (not released on
preemption, only on explicit switches), and is reacquired when the
thread resumes. That is, guarentees atomicy within the code domain
the token was acquired for only while the thread is running. If
the code domain blocks the token is released and reacquired on
Tokens may block and may cause a thread switch to occur and can
only be used in code paths where blocking is ok.
* LockMgr Locks
May be used to lock long code paths. May be nested. NOT released
when a thread blocks. Has a fairly heavy-weight API (but I have
simplified it enormously over this development cycle).
* Serializing locks
Serializing locks are basically a simplified version of exclusive
lockmgr locks. They are allowed to block on aquisition and are
held across thread switches and blockages. The interrupt subsystem
tightly integrates serializing locks to efficiently manage
interlocks between mainline code running for a driver and the
interrupt handler for that same driver.
These effectively replace spl's, but only from the point of view
of any particular driver. Most spl's in the system are unrelated
to drivers and are more appropriately turned into critical sections.
I may remove serializing locks in favor of LockMgr locks due to
the simplification that has occured in the LockMgr API over the
RCU is interesting but I personally prefer replication and
cpu-localization instead of RCU. So far nothing has come up that really
needs an RCU implementation. RCU suffers from a level of complexity
that makes it somewhat difficult to understand the code using it, and
I don't like that aspect of it.
The use of tokens in the system is primarily being relegated to situations
that actually need the above characteristics. A very good example of
this is the traversal of system structures such as the system mountlist.
An example of incorrect use would be in, say, kern_objcache.c, where we
really ought to be using a spinlock there instead.