--rwEMma7ioTxnRzrJ
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

One of the remaining issues I'm working on with the SA libpthread is=20
cleaning up the locking. Turns out there hasn't been that much at issue,=20
but I need help with one item.

The four things I found are:

1) Locking ordering was undocumented. I think I figured it out, and I have=
=20
written down what I think it is. I think I've got it right as there are=20
only a few issues where the code doesn't agree. The plan is to make the=20
code and documentation agree, one way or the other.

2) Way too much stuff ignores pt_flag_lock, but it all has XXX on it so=20
it's a recognized bug. Easy to fix.

3) There was one lock ordering issue in join w.r.t. pt_flag_lock (or it
used to be that flag lock was higher up in the ordering - I now have it at
the bottom). Fixed.

And now for the one I need help with:

4) I am confused as to what is the best way to handle pt_state_lock and
the run queue lock. As you might expect, pt_state_lock locks the state of
a thread and the runqueue lock locks the queue. The question though is how
best to handle the locking order. Do you lock the state lock or the run
queue lock first?

Right now, the state lock is at a higher priority than the runqueue lock.

The deal is that some of the time you need to lock one first, and other=20
times you need to lock the other first. When you're going to sleep, it's=20
easiest to lock your own state lock, the put yourself on the right sleep=20
queue. Likewise when you're "killing" (pthread_kill()) something, it's=20
easiest to lock its state lock and inspect it to see what to do.

The big problem comes when taking something off of the work queue,=20
especially when you're getting the next thread to run as you're going to=20
sleep. You've got the run queue locked, so you can find what exactly is=20
the thread to switch to. But you need to mark it as RUNNING not RUNABLE,=20
and that requires the state lock, which we can't take since we are holding=
=20
the run queue lock.

The case I keep in mind when thinking about this is a case where thread A=
=20
is going to sleep for some reason, thread B is RUNNABLE and at the head of=
=20
the run queue, and thread C has, for whatever reason, decided to muck w/=20
thread B's state. As a concrete example, let thread C be wanting to send a=
=20
signal to thread B.

So any suggestions on how to handle this?

Things I can see are:

1) Make pthread_next() users, which are right around=20
pthread__locked_switch() and the upcall variant, restartable sequences.=20
Pull the thread off of the run queue in pthread_next(), then if it's not=20
RUNNABLE when we lock its state, try again. Problems I see with this are=20
a) we put fixup code in the fast path, and b) any time we detect this=20
problem, we just had two things take the thread off of the run queue.=20
Hello queue corruption!

2) Something similar to (1) but use a lock lower on the hierarchy than=20
either the state lock or run queue lock. Say the flag lock. When something=
=20
gets pulled off of the run queue, grab that lock (which we can always do)=
=20
and note that we've pulled this off the run queue. Then if we ever get to=
=20
where we want to pull something off of the run queue and this "already=20
done" flag is set, (a) don't pull it off the queue, and (b) try again,=20
with the run queue still locked.

May well work, but puts "restart" code ('try again' above) in the fast=20
path. May be fine as the goals for SA aren't supper-concurrency.

3) Switch the hierarchy of run queue and state queue, and require that all=
=20
the operations that MAY pull something off of the run queue, like=20
pthread__kill() (the internal helper for pthread_kill()), lock it early.=20
This may be the best way to go. It'll mean things like pthread_kill() are=
=20
concurrency killers, but so be it. This will also impact things that wake=
=20
threads up (change state and muck w/ run queue), but I don't think that'll=
=20
be bad.


Suggestions? I know there's a world of experience out there I haven't read=
=20
about yet. This problem has to be quite old.... :-)

Take care,

Bill

--rwEMma7ioTxnRzrJ
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (NetBSD)

iD8DBQFHG67gWz+3JHUci9cRAkgXAJ9aMFB6Pf3zzow4S+nomem+xff2GACfWGub
V2KthRk4ZkJrq79tiV+MDUk=
=k7AK
-----END PGP SIGNATURE-----

--rwEMma7ioTxnRzrJ--