Lockless algorithms [was Re: splxxx replacements?]

[Matthew Dillon]

:Ok, so you're still using tokens for larger subsystems that have long execution
:paths if I understand you, right ?
:
:One of the claims about dfBSD that I found interesting was that the your use of
:token to break up long kernel paths was an incremental way of MPing the kernel.
:This is in contrast to the complete removal of Giant in a lock path for a kernel
:syscall. The question here that I've been wondering if tokens are living up to
:its claim or not ?
:
:That's really the main question I have using it as a general mechanism for MP
:work in a legacy kernel (I'm thinking about using it for another system that is
:already using a code path protection scheme).
:
:bill

    Tokens have worked out very well for long code paths such as 
    traversing a mountlist in order to perform a filesystem sync.  There
    is virtually no knowledge pollution verses the mutex model where you
    have to pass the held mutex down any code path that might potentially
    block.

    That said, we are having even MORE success with cpu localization, 
    allowing us to code lockless algorithms.  So much success, in fact,
    that many of the things I originally envisioned as using tokens now
    don't use any locks at all.

    Also, standard lockmgr locks have been simplified considerably and
    they also now leak into some of the areas where I originally envisioned
    using tokens.

    The areas which still need solutions are primarily tree topology lookups
    and updates.  The VM page hash table, the buffer cache, and the 
    name cache.  I am not at all convinced that RCU is the answer I 
    am looking for.  What I do want to do is to find a general solution
    that can be implemented by the red-black tree module itself rather
    than by all the code that uses RB trees.

					-Matt
					Matthew Dillon 
					<dillon at xxxxxxxxxxxxx>