lwkt_token progress

Matthew Dillon dillon at apollo.backplane.com
Sat Feb 21 12:32:38 PST 2004


    Well, after much hair pulling trying to fit the new Token serialization
    code into the same API I had before, I finally gave up and decided to
    change the API.

    The issue comes down to how to record the tokens that a thread has
    acquired.  Since tokens are simply serializing entities multiple
    threads can own the same token (they just can't be running at the
    same time when they do), so we can't just use a linked list
    embedded in the token's structure.

    I tried creating a fixed array of pointers in the thread structure.
    I tried creating a cache of token-referencing structures in the
    globaldata structure.  I was not happy with either method.

    What I finally came up with is to have the caller pass a token reference
    structure that must remain valid for the duration of the hold.  This
    allows the caller to declare the reference structure on the stack
    and allows the token API code to avoid using a critical section, making
    it very fast code.  This means I have to make a bunch of changes to
    all the existing code that calls into the API, since the argument to
    the API functions is now a reference structure pointer rather then a 
    token pointer.

    On the bright side, the new serializing token API is shaping up to be
    a very powerful tool.  So powerful, in fact, that I believe it will
    help us get out from under the BGL much more quickly then I
    originally anticipated.  While the old token code was only 'similar'
    to mutexes, the new serializing tokens are going to be much, much more
    powerful then mutexes.  The new serializing tokens are going to make
    mutexes look like a poor country cousin!

    I'm hoping to have a patch set ready for testing tonight.

    Here is my current notion of the rules:

				     ----
				Serializing Tokens

    A serializing token may be held by any number of threads simultaniously.
    A thread holding a token is guarenteed that no other thread also
    holding that same token will be running at the same time.

    A thread may hold any number of serializing tokens.

    A thread may hold serializing tokens through a thread yield or blocking
    condition, but must understand that another thread holding those tokens
    may be allowed to run while the first thread is not running (blocked or
    yielded away).

    There are theoretically no unresolvable deadlock situations that can
    arise with the serializing token mechanism.  However, the initial
    implementation can potentially get into livelock issues with multiply
    held tokens.

    Serializing tokens may also be used to protect threads from preempting
    interrupts that attempt to obtain the same token.  This is a slightly
    different effect from the Big Giant Lock (also known as the MP lock),
    which does not interlock against interrupts on the same cpu.

    Holding a serializing token does NOT prevent preemptive interrupts
    from occuring, though it might cause some of those interrupts to 
    block-reschedule.

						-Matt






More information about the Kernel mailing list