serializing token

[Matthew Dillon]

:...
:> 	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.

: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.

:>     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.

:>     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.

    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.

					-Matt
					Matthew Dillon 
					<dillon at xxxxxxxxxxxxx>