DragonFly kernel List (threaded) for 2008-02
DragonFly BSD
DragonFly kernel List (threaded) for 2008-02
[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]

Re: Patch for inode SLIST conversion


From: Michael Neumann <mneumann@xxxxxxxx>
Date: Tue, 05 Feb 2008 14:56:19 +0100
Cc: Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxx>

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



[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]