Re: POSIX rwlocks vs. glib2 rwlocks

[Sebastian Wilhelmi <wilhelmi ira uka de>]

Hi Kaz,

> > 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.

Yeah, that's what I meant with "our documentation is wrong". We do not support
reader lock recursion.

> 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. :)

Oh, that's indeed a bit of a relief for me, that even the good guys at glibc
got it wrong in the first try ;-)

> > 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.

Yes, indeed. I thought about adding a thread private (AFAICT thread privates
are only very slightly slower than pthread_self) counter "num_of_readers" and
"num_of_writers" and only changing the "num_of_readers" counter, when the
thread private "num_of_readers" changes to or from 0. That would allow to
easily release the read lock and as an extra benefit would make locking
unnessesary for recusrive read locking.

> 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.

Ah, clever trick. I looked at the implementation, but not in that great
detail. My solution could of course consume quite some memory: It would cost
(Num of threads) * (Num of recursive reader-writer-locks) * (6 Bytes +
overhead for one allocation), even if no lock is ever called recursivly.

For the time being I'll only change the doc. If later someone want recursive
reader/writer-locks, I'll reconsider.

Thanks for the tip anyway,
Sebastian
-- 
Sebastian Wilhelmi
mailto:wilhelmi ira uka de
http://goethe.ira.uka.de/~wilhelmi