Re: Another LinuxThreads bug.

[Kaz Kylheku <kaz at ashi dot footprints dot net>]

On Mon, 10 Jan 2000, Xavier Leroy wrote:

> Date: Mon, 10 Jan 2000 13:27:20 +0100
> From: Xavier Leroy <Xavier.Leroy@inria.fr>
> To: Kaz Kylheku <kaz@ashi.footprints.net>
> Cc: Ulrich Drepper <drepper@cygnus.com>, Andreas Jaeger <aj@suse.de>
> Subject: Re: Another LinuxThreads bug.
> 
> > The problem is that the condition ``there is no write lock'' is
> > taken as sufficient for placing another read lock. To correctly give
> > precedence to writers, the condition should be ``there is no write
> > lock, and there are no waiting writers''.
> > 
> > The count of existing read locks need not be consulted at all, even
> > if the lock prefers readers. A lock that prefers readers simply
> > allows a read lock to be placed whenever there is no write lock, and
> > ignores any waiting writers.  This is reflected in the new logic,
> > which tests the lock's type and breaks the loop.
> 
> Right.  The patch looks good.  I think we can put it in 2.1.3.

Unfortunately, upon reading the Single Unix Specification's description
of pthread_rwlock_rdlock, I have uncovered a problem.

*
* The patch should *not* be applied, because it gives rise to another bug.
*

Here is the relevant wording:

    A thread may hold multiple concurrent read locks on rwlock (that is,
    successfully call the pthread_rwlock_rdlock() function n times). If
    so, the thread must perform matching unlocks (that is, it must call
    the pthread_rwlock_unlock() function n times).

By making write-priority work correctly, I broke the above requirement, because
I had no clue that recursive read locks are permissible.

If a thread which holds a read lock tries to acquire another read lock, and now
one or more writers is waiting for a write lock, then the algorithm will lead
to an obvious deadlock. The reader will be suspended, waiting for the writers
to acquire and release the lock, and the writers will be suspended waiting
for every existing read lock to be released.

Correctly implementing write-priority locks in LinuxThreads in the face of the
above requirement doesn't seem easy.  The read lock function must distinguish
whether the calling thread owns a read lock. Since many threads can own a read
lock, and one thread can own read locks on many objects, it appears that be
that a structure of size O(M * N) is needed track the ownership.

The alternatives are:

    1. Abandon support for writer-priority. Make this decision visible to the
       programmer, so that they aren't led into false expectation.

    2. Get it working somehow. This requires a much more sophisticated change
       than my naive patch which does more harm then good.

I suspect that it may be necessary to go with option 1 for release 2.1.3. 

However read-write locks that avoid writer starvation are nice to have, so
research on 2 should begin immediately.  Perhaps an elegant solution for this
exists already that can be adapted for LinuxThreads.

A compromise might be to make read-priority locking default, and guide users to
use the non-portable attribute for writer-priority if they want it, on the
condition that they can't use recursive read locks (which are brain-damaged
anyway!) In that case, the patch *can* be applied, with the additional change
that the  text in pthread.h which reads:

    #ifdef __USE_UNIX98
    enum
    {
      PTHREAD_RWLOCK_PREFER_READER_NP,
      PTHREAD_RWLOCK_PREFER_WRITER_NP,
      PTHREAD_RWLOCK_DEFAULT_NP = PTHREAD_RWLOCK_PREFER_WRITER_NP
    };
    #endif	/* Unix98 */

is changed to

      PTHREAD_RWLOCK_DEFAULT_NP = PTHREAD_RWLOCK_PREFER_READER_NP

According to The Single Unix Specification, the behavior is unspecified when a
reader tries to place a lock, and there is no write lock but writers are
waiting. That is, there is no requirement that priority be given to writers.
(But the unspecified behavior does not extend to permitting deadlock,
I presume!!!).

URL:

http://www.opengroup.org/onlinepubs/007908799/xsh/pthread_rwlock_rdlock.html