Re: POSIX rwlocks vs. glib2 rwlocks

[Kaz Kylheku <kaz ashi footprints net>]

On Wed, 20 Jun 2001, Sebastian Wilhelmi wrote:

> Date: Wed, 20 Jun 2001 10:59:37 +0200
> From: Sebastian Wilhelmi <wilhelmi ira uka de>
> To: Kaz Kylheku <kaz ashi footprints net>
> Cc: Erik Walthinsen <omega temple-baptist com>,
>      gtk-devel-list <gtk-devel-list gnome org>
> Subject: Re: POSIX rwlocks vs. glib2 rwlocks
>
> Hi Kaz,
>
> > Read-write locks are functional, and also provide several flavors of
> > lock: writer preference, reader preference, and writer preference
> > without recursive read locking.
> >
> > Writer precedence is the default type, and supports recursive read
> > locking as well, which is tricky (what if a thread which owns a read
> > lock wants to get another read on the same lock, but writers have
> > queued up in the meanwhile? POSIX requires that the reader is granted
> > the additional lock, and the glibc2 implementation makes it work
> > correctly).
>
> This indeed is tricky. Actually I haven't thought of that yet. So actually our
> documentation is wrong in saying:
>
> GStaticRWLock in general is not recursive, but as there may be unlimited
> concurrent locks for reading, it effectively is for recursive for reading, but
> for reading only. Locking for writing after locking for reading will deadlock,
> the same holds true for the opposite order.

I think that this has limited utility. Recursive locks in general are a
bad idea; recursive read locks can sometimes be useful however; e.g.
for reentrant iteration over lists.

The problem I described is not in supporting a write lock by a thread
which already owns a read lock, or vice versa,  but in supporting
recursive read locks under writer preference. Writer preference means
that a read lock request is suspended if writers are waiting for the
lock, until all the writers have had their turn. Unless this is
specially handled, it is bad news if a reader is trying to make a
recursive read lock, and writers have lined up already. The writers
will wait forever for the read locks to be released, but the holder of
one of the read locks is waiting forever for the writers to go in and
out.  On the other hand, recursive read locking is trivial under reader
preference.

glibc 2.1.2 claimed to have writer preference, but due to a mistake in
a test expression, it was actually doing reader preference. This was
fortunate, because the implementation didn't have special handling for
the recursive reads under writer preference anyway, so one bug avoided
another. :)

> That has to be fixed. On the other hand a fully recursive rwlock might be nice
> to have. I suppose the work you have to invest to enable read lock recursion
> is enough to also enbable full (mixed read/write) recursion.

I think that this kind of mixing is a troublesome idea.  To allow a
reader to obtain a write lock means that all the other readers have to
give up their read locks first.  Once the only read locks that remain
belong to the caller who wants a write lock, that write lock can
proceed.

The problem is that two threads can do this, and then you have a
deadlock situation, unless you do something a little more clever.  Each
thread will wait for the other's read locks to be released so that it
can grab the write lock. One obvious way to prevent the deadlock would
be to to release the thread's reads over that lock, and then reacquire
them again when the write lock is acquired.

To force a thread to give up its read locks means that you have to
have a complete list of the thread's read-write locks. In the glibc
implementation, we don't quite have that; rather, a less complete
representation is used which supports some weaker predicates
that are good enough.  Specifically, a read lock request is granted
even if writers are waiting, if it cannot be proven that the caller
doesn't already have the read lock (rather than, if it can be
proven that the caller has the read lock).  A thread has a list of read
locks that is owns, and a flag which indicates whether that list is
incomplete (the ``untracked read locks'' flag).  A list might be
incomplete because no memory was available to allocate a node to it. Or
an implementation could choose to impose a maximum length, to save
space, or allow for a simple fixed-size-array-based implementation.

This representation is good enough to support recursive read locks,
because you simply fall back on reader preference in some rare cases
when you can't prove that write preference won't cause a deadlock.

However, this incomplete representation doesn't give you enough
information to release a caller's read locks and reacquire them later;
you need complete information.