Multiple locks and missing wakeup.

[John Baldwin]

On Tuesday, April 08, 2014 2:34:30 am Edward Tomasz Napierała wrote:
> Let's say I have a kernel thread processing elements from a queue,
> sleeping until there is work to do; something like this:
> 
> mtx_lock(&mtx1);
> for (;;) {
> 	while (!LIST_EMPTY(&list1)) {
> 		elt = LIST_FIRST(&list1);
> 		do_stuff(elt);
> 		LIST_REMOVE(&list1, elt);
> 	}
> 	sleep(&list1, &mtx1);
> }
> mtx_unlock(&mtx1);
> 
> Now, is there some way to make it work with two lists, protected
> by different mutexes?  The mutex part is crucial here; the whole
> point of this is to reduce lock contention on one of the lists.  The
> following code would result in a missing wakeup:

All our sleep primitives in the kernel only accept a single wait channel.
It sounds like you want something more like select() or poll() where you
can specify multiple wait channels.  There isn't a good way to do that
currently.  You could write one, but it would be a bit hard to do
correctly.  In practice you'd end up implementing something that boiled
down to having a single wait channel with a common lock that protected
it so you could do something like:

for (;;) {
		mtx_lock(&combo_lock);
		while (LIST_EMPTY(&list1) && LIST_EMPTY(&list2))
			sleep(&shared_cv, &combo_lock);
		mtx_unlock(&combo_lock);

		/* Drain each list */
}

The code to queue an item would then need to do something like:

	mtx_lock(&mtx1);
	mtx_lock(&combo_lock);
	LIST_INSERT(&list1, ...);
	wakeup(&shared_cv);
	mtx_unlock(&combo_lock);
	wakeup(&list1);		/* If other waiters */
	mtx_unlock(&mtx1);

Another way to do this would be to be a bit more poll-like (e.g. if
you wanted a generic mechanism for this) where you have some sort of
'poller' structure and you set a flag before starting a scan of all
your backends.  Any wakeup that occurs while scanning clears the
flag, and you only sleep if the flag is still set at the end of the
scan, etc.

-- 
John Baldwin