Looks pretty good.  It's almost ready for commit.  I see one bug and
    two implementation issues in lwkt_getalltokens().

    The 'if (tok->t_lastref != refs) tok->t_lastref = NULL' case should
    only occur inside the 'if (tok->t_owner != td)' conditional.  That 
    is, if the same thread has acquired the same token several times
    (each with its own ref), only the most recent acquisition (the first
    one found on the td_toks list) should have the t_lastref logic.
    Otherwise the remaining acquisitions will cause it to be NULL'd out
    every time.

    The first implementation issue is the UP version.  The non-SMP code
    does not have a lwkt_getalltokens() procedure so the staleness is
    not being tracked at all.  We need to create a UP lwkt_getalltokens()
    procedure as well whos only job is to run through and check t_lastref.
    We may have to implement t_owner for UP too.

    The second implementation issue has to do with recursive acquisition
    of the same token.  The current t_lastref implementation will cause
    the deeper acquisition to 'stale-out' the higher level acquisition.
    It could be argued that if you have procedure A acquire a token and
    it calls procedure B which, unknown to procedure A also needs the token,
    then procedure A should detect the temporary loss of control over
    the structures represented by the token by seeing that it has become
    stale.  Your current implementation has this effect.

    Alternatively we might want to allow recursive acquisition to NOT
    indicate staleness.  To do this we would have to augment lwkt_reltoken()
    to detect that t_count != 0 and run the rest of the td_toks list to
    find the next higher level up on the stack.  If t_lastref was pointing
    at the ref being released, it would be repointed at the next ref in the
    recursion instead of being NULL'd out.

    This would mean that we would have to implement a getalltokens/relalltokens
    procedure for the UP case ...
[ message continues ]

A patch is appended.

lwkt_token_is_stale(lwkt_tokref_t) detects if the token was acquired by
another thread while the thread was sleeping. I don't care about
tokrefs, instead the granularity is a thread, so that recursive calls to
acquire a token within the same thread DO NOT stale out a token.
Furthermore the code for UP and SMP is now basically the same, except
for spin-locks or preemption issues. That is, I keep a per-thread count
instead of the globalcount on UP and maintain thread ownership as well.
I noticed that _lwkt_trytokref and _lwkt_gettokref were basically using
the same code (it was copy & pasted), so I unified that as well.

Regards,

   Michael

I'm unsure if this is a common usage scenario. If we call a function we 
  usually know their side-effects.

So it's a decision if we want staleness based on thread granularity (a 
token gets stale whenever a distinct thread acquires the token) or on a 
tokref granularity (each distinct tokref will stale out the token).
I find the thread granularity more natural, just because tokrefs confuse 
my mind more than threads.



I might have discovered a race in the UP version. lwkt_reltoken removes 
the tokref from the thread's token list:

     for (scanp = &td->td_toks; *scanp != ref;
       scanp = &((*scanp)->tr_next))
         ;
     *scanp = ref->tr_next;

Afterwards it modifies it's globalcount:

     --tok->t_globalcount;

Okay it's very unlikely that the decrement operation is preempted, but 
imagine it's preempted after reading the current t_globalcount into a 
register, right before decrementing it and storing it back to memory. 
Imagine the preempting thread now calls lwkt_gettokref and executes this:

     while ((td = td->td_preempted) != NULL) {
         for (scan = td->td_toks; scan; scan = scan->tr_next) {
             if (scan->tr_tok == tok) {
                 lwkt_yield();
                 return;
             }
         }
     }

As the token was removed from the preempted thread before, the 
preempting thread won't find the token in the list and thinks "I can 
safely acquire it, as no preempted thread helds it". It then
goes on and increments the globalcount:

     /* NOTE: 'td' invalid after loop */
     ++tok->t_globalcount;

Bang! We lost an incrementation when the preempted thread resumes. This 
is no problem as t_globalcount is purely for debugging, but it's 
dangerous when additional code (like the staleness code) is added.

Disclaimer: Please prove that I'm am completely wrong here ;-)

A solution is to move the code that removes the token from the thread's 
list (in lwkt_reltoken) after any token modif...
[ message continues ]

Before you do it, I prove myself wrong :)

The lwkt thread scheduler takes care of this and doesn't allow to
preempt a thread that holds any tokens. I got confused because we're
testing for preemption in lwkt_gettokref as well. Hm, if the scheduler
really disallows to preempt a thread that has any tokens, then I don't
understand the test for preemption in lwkt_gettokref. Can this every 
happen?

Ah I think it is the other way round. A thread holding tokens
cannot preempt another thread. So, a thread that holds tokens can be 
preempted by a thread, but only if the new thread has no tokens
(initially). The preempting thread can then acquire further tokens, that
is why we need the tests for preemption in lwkt_gettokref.

I think in this case it's possible that a race occurs!

Regards,

   Michael

>

Definitively :)

I am working on it. I had to become familiar with the LWKT scheduling 
code first. I like it's conceptual simplicity/elegance. While reading 
the code I noticed that one thing that makes the whole code harder to 
read is all those "#if SMP" lines. Everytime you have to flip a switch 
in your mind (my changes won't change that).

Regards,

   Michael