serializing token

David Leimbach leimy2k at mac.com
Sun Apr 25 06:59:28 PDT 2004


On Apr 25, 2004, at 1:17 AM, Matthew Dillon wrote:

:...
:> 	lwkt_gettoken(..)
:> 	while (someglobal) {
:> 	    someglobal &= ~someotherprocedurethatmightbloc();
:> 	    call procedure that might block()
:> 	}
:> 	lwkt_reltoken(..)
:>     }
:
:Let's assume for a minute that the above code is a consumer on a 
work-queue
:and that the "if (someglobal)" evaluates true if there is work to be 
done.
:
:Would this "gettoken" "reltoken" usage be suitable to support a 
consumer on
:a work queue?

    It would be suitable for manipulating the work queue to pull 
something
    off of it, as long as you intend to allow other consumers to also
    pull things off the work queue while your consume is potentially
    blocked in the midst of doing the work that it had pulled off.

I think I am getting it now...  basically the token is subtly different 
from a mutex
in that it will only allow the *scheduler to run* one of the threads 
that has the
token at a time.  This may not give you as strong a guarantee as a 
mutex but
it does give you some knowledge about how things are going to be run by
the OS.  This knowledge is a lot like the RCU stuff being done in linux 
to
avoid using a lock and to improve SMP performance.

Is that pretty close?  It seems that RCU uses knowledge of how the 
scheduler
works and tokens actually tell the scheduler how it is allowed to work.

:Clearly the ability to call blocking functions while holding the lock 
is a
:nice feature :).

    This is what the above code would like with mutexes:

 	lwkt_getmutex(&mutex)
 	while (someglobal) {
 	    someglobal &= ~someotherprocedurethatmightbloc();
 	    call procedure that might block(&mutex)
 	}
 	lwkt_relmutex(&mutex)
    You would have to pass the mutex down into the procedure that might
    block so the procedure can release the mutex prior to blocking, and
    reacquire it after waking up again, before it returns to the 
caller.

    == Major code pollution.  In my world, 
procedure-that-might-block() has
    no business knowing the locking state of its caller, and with 
tokens
    it doesn't have to.

Right I think I understand now :).  Since a token can't starve another 
thread
who has/wants it like a mutex can there is no need to do complex 
unlocking
and relocking code.  You just have to program with them as if you have 
a token
not a mutex which requires a slightly different way of thinking about 
your
code.

:>     This code snippit above is using a token to protect a global 
variable.
:>     It is able to optimize itself by not bothering to get the token 
unless
:>     it thinks it has work to do, and then integrating the recheck 
case in
:>     the while().  The token is protecting against preemptive 
modifications
:>     to the global variable rather then protecting against changes 
made to
:>     the global variable by the called procedures or as a side 
effect if
:>     either procedure blocks.
:>
:
:What would be a change to the global variable that the token doesn't 
protect
:if th thread does block on one of those procedures?

    What changes are allowed by the algorithm.  Lets say the global
    represents a bitmap.  A possible change might be that another bit 
in the
    global might be set or cleared while we are blocked.

    There is an example of this exact mechanism in the codebase, but
    protected by a critical section rather then a token.  It's the
    DORETI code in /usr/src/sys/i386/isa/ipl.s.  This code looks at
    interrupt pending bits and interrupt-adjusted request flags and
    processing them.  At the same time new interrupts may set new bits
    in the same flags fields.
:What does the scheduler do when another thread tries to get the token 
and
:the original token holder is blocked?  I think the answer to this 
question
:may clarify to me how this works better.

    The second thread will successfully acquire the token if the first
    thread is blocked, and the first thread will not be allowed to 
wakeup
    until the second thread has released the token or has blocked 
itself.

So on a UP system a token really only locks out interrupts that try to 
acquire
a token already held by the pre-empted thread.  On an SMP system the 
tokens
tell the scheduler not to schedule more than one thread holding a token 
at a time.

In either case [SMP or UP] if a thread blocks while holding a token the 
scheduler
is free to run another thread that also has the token, but no more than 
one other
thread holding the token can run.

If a thread blocks while holding a token, and it is the only thread 
with the token,
can an interrupt which also wants the token then run as a normal thread 
would?

:>     pointers such as unreferenced vnode pointers, vm_page's, and so 
forth.
:>     There are plenty of ways to protect such structures.  The vnode 
case is
:>     probably the most complex (and it is just as complex or even 
more complex
:>     when implemented with mutexes), most of the rest of the 
structures can be
:>     prevented from moving around with a ref count.
:
:Is the reference count protected by tokens or mutexes? :)

    In DragonFly there are no mutexes, but we still have the Big Giant 
Lock.
    Most of our major structures are still protected by the BGL and 
only
    need a critical section to safely increment/decrement a reference 
count.

I need to learn more about critical sections in dragonfly too then it 
seems.  My
understanding is they only allow one thread in a section at a time... 
this sounds
a little like tokens but I am not sure how they are different yet.

    As we remove the BGL we have to decide how to protect such 
operations...
    a token is certainly reasonable (it is in fact exactly how 
lockmgr()
    locks protect fields in the struct lock data structure while 
executing
    the higher level lockmgr functions).

    Another solution is to make the code in question lockless.. with no
    locking requirements at all.  This is accomplished by guarenteeing 
that
    all potential conflicts occur on the same cpu.

    For example, Jeff's work on the TCP stack is moving all protocol 
processing
    for a particulr PCB to a particular cpu.  Since only one cpu is 
working
    on a particular PCB, the protocol code can access that PCB without
    acquiring any locks, mutexes, or tokens of any sort.

That sounds really cool too.

Thanks for taking the time to discuss this with me.  I think I 
understand these
a bit better now.

					-Matt
					Matthew Dillon
					<dillon at xxxxxxxxxxxxx>






More information about the Kernel mailing list