Re: Patch for inode SLIST conversion

[Michael Neumann <mneumann@xxxxxxxx>]

Michael Neumann wrote:
> Matthew Dillon wrote:
> > :That's the perfect solution!
> > :
> > :Patch appended. _lwkt_trytokref needs the same change, as it might 
> > :acquire the token as well. I think setting lastref = NULL in 
> > :lwkt_reltoken is also not absolutely neccessary, but it's not wrong
> > :either, so I did it.
> > :
> > :Regards,
> > :
> > :   Michael
> >
> >     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.
>
> 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 ;-)

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