More ksem fun with the beos-native threading system... (fwd)

[alanlb at rrinc.com]

Odd... I sent this to the ML a couple of weeks ago, but it doesn't seem to
have made it out...

Alan

------------------------------ 

Hello, all.

As previously reported, I've been trying to track down
a deadlock condition in the ThreadState regression test (among others)
whereby one or more threads attempt to acquire a ksem that they  already
hold.  I develop and test on a dual-processor machine (although I can
reproduce the problem with one of the processors turned off).

As implemented, the ksem functions are trivially implemented
as described in FAQ.locks, using BeOS's native counting semaphores.
I added some DBG calls to the ksem funcs,  ran ThreadState with
arguments "-v 2", and obtained the following (annotations are mine,
and "Kaffe main thread" is that thread which is "created" by
jthread_createfirst()):

==================================================================

main thread has id 261a
Kaffe main thread: created sem 94431  /* object lock */
Kaffe main thread: created sem 94435  /* finMan */
created thread finaliser, daemon=1
Kaffe main thread: created sem 94439  /* gcMan */
start_me_up: setting up for finaliser
start_me_up: calling t-func for finaliser
finaliser: attempting to acquire sem 94435
created thread gc, daemon=1
start_me_up: setting up for gc
start_me_up: calling t-func for gc
gc: attempting to acquire sem 94439
Kaffe main thread: created sem 94443
created thread Thread-0, daemon=0
start_me_up: setting up for Thread-0
start_me_up: calling t-func for Thread-0
Thread-0: attempting to acquire sem 94443
Kaffe main thread: releasing sem 94443
Thread-0: acquired sem 94443
Kaffe main thread: releasing sem 94443
Kaffe main thread: created sem 94447
created thread Thread-1, daemon=0
Thread-0: attempting to acquire sem 94443
Thread-0: acquired sem 94443               /* OK, 94443 belongs to T-0 */
start_me_up: setting up for Thread-1
start_me_up: calling t-func for Thread-1
Thread-1: attempting to acquire sem 94447
Kaffe main thread: releasing sem 94447
Thread-1: acquired sem 94447
Thread-1: attempting to acquire sem 94447
Kaffe main thread: attempting to acquire sem 94431
Thread-0: attempting to acquire sem 94443  /* T-0 wants 94443 again?! */
Thread-0: releasing sem 94431
Kaffe main thread: acquired sem 94431
Thread-0: releasing sem 94447
Thread-1: acquired sem 94447
Thread-1: attempting to acquire sem 94447
Thread-0: attempting to acquire sem 94443
Kaffe main thread: releasing sem 94443
Thread-0: acquired sem 94443
Thread-0: releasing sem 94447
Thread-1: acquired sem 94447
Thread-0: attempting to acquire sem 94443
Thread-1: attempting to acquire sem 94447
Kaffe main thread: releasing sem 94447
Thread-1: acquired sem 94447
Kaffe main thread: attempting to acquire sem 94431
Thread-1: releasing sem 94443
Thread-0: acquired sem 94443
Thread-0: created sem 94451
created thread Thread-2, daemon=0
Thread-1: created sem 94455
Thread-1: attempting to acquire sem 94447
start_me_up: setting up for Thread-2
start_me_up: calling t-func for Thread-2
Thread-2: attempting to acquire sem 94451
Thread-0: releasing sem 94451
Thread-2: acquired sem 94451
Thread-2: releasing sem 94447
Thread-1: acquired sem 94447
created thread Thread-3, daemon=0
Thread-2: attempting to acquire sem 94451
Thread-0: releasing sem 94451
start_me_up: setting up for Thread-3
start_me_up: calling t-func for Thread-3
Thread-3: attempting to acquire sem 94455
Thread-1: releasing sem 94455
Thread-2: acquired sem 94451
Thread-3: acquired sem 94455
Thread-3: attempting to acquire sem 94455
Thread-1: attempting to acquire sem 94447
Thread-2: destroyed sem 94451
jthread_exit called by Thread-2
Removing entry for thread Thread-2
Thread-2: attempting to acquire sem 94451
Thread-2: failed to acquire sem 94451
Thread-2: attempting to acquire sem 94451
Thread-2: failed to acquire sem 94451
Thread-2: attempting to acquire sem 94451
Thread-2: failed to acquire sem 94451
Thread-2: attempting to acquire sem 94451
Thread-2: failed to acquire sem 94451    /* T-2 failed to get 94451 */
Thread-2: releasing sem 94451            /* so why is it releasing it */
Thread-2: at the point of no return in jthread_exit
Thread-0: releasing sem 94451
Success.
Thread-0: releasing sem 94431
Kaffe main thread: acquired sem 94431
Kaffe main thread: attempting to acquire sem 94431
Thread-0: destroyed sem 94443
jthread_exit called by Thread-0
Removing entry for thread Thread-0
Thread-0: at the point of no return in jthread_exit

==================================================================

/boot/usr/kaffe/libexec/Kaffe -vmdebug JTHREAD ThreadState 2 (team 6787) (uid 0) (gid 0)
   9754    Kaffe main thread  sem  11     809    1469 Ksem(94431)
   9759            finaliser  sem  20       0       0 Ksem(94435)
   9760                   gc  sem  20       0       0 Ksem(94439)
   9762             Thread-1  sem  11       1       2 Ksem(94447)
   9764             Thread-3  sem  11       0       0 Ksem(94455)        

Kaffe main thread in java_lang_Object_wait0:waitCond(o, timeout);
Thread-1 in gc_heap_malloc:lockStaticMutex(&gc_lock);
Thread-3 in gcFree:lockStaticMutex(&gc_lock);

Sem 94431 last held by Kaffe main thread
Sem 94447 last held by Thread-1
Sem 94455 last held by Thread-3

==================================================================

The last portion shows the relative portions from 'ps', plus some info
garnered from a debugger.  As the comments indicate, you can see one or
more threads either attempt to acquire a ksem they already hold, or
release a ksem that they don't hold.

The weird thing is that the debugger tells me that both Thread-1 and Thread-3
are contending for gc_lock via different paths, even through they are
each blocked on two different semaphores (94447 and 94455, respectively).
I've had trouble with the debugger not showing the proper line numbers,
so perhaps I'm misinterpreting something.

It seems to me that one or more of the following are true:

1) A trivial mapping of the ksem interface to BeOS counting semaphores doesn't
   implement the correct ksem semantics.  At the very least, the following
   are unclear to me:

     - If ksemGet is interrupted by a system call (as opposed to
       timing out), is it supposed to keep trying to acquire the
       ksem, or just return "false" ?  Does the value of the timeout
       argument matter in determining this (i.e., 0 means keep trying
       until the ksem is acquired, no matter what; non-zero means
       try once until the ksem is acquired, or the attempt times out,
       whichever comes first) ?

     - If ksemGet's timeout argument is non-zero, what is the
       unit of measurement ?

     - Does ksemPut always decrement the ksem's count even if no
       threads are blocked on the ksem ?

2) The scheme whereby Kaffe determines whether a lock is being contended
   or not fails for some reason under certain circumstances.

The second one is mere speculation on my part; I'd like to be able to test
it using a different OS/threading system, but it looks like only my
beos-native threading system has ksems at all (a conclusion arrived at
by grepping for "THREAD_SYSTEM_HAS_KSEM") ...

I apologize for the long message......

Alan