Re: Another LinuxThreads bug.

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

On Mon, 10 Jan 2000, Xavier Leroy wrote:

> That's an interesting twist!  I have no solution to offer right now,
> but I believe Butenhof's book contains an implementation of RW locks
> in terms of basic POSIX primitives.  That could give us some clues
> (although it could be that he simply doesn't implement writer
> preferencing).

I have hacked something up already.

The idea is this. With each thread, associate a linked list of read locks that
it owns.  Each list entry holds a pointer to a pthread_rwlock_t for which the
thread owns a read lock, and a counter representing how many readlocks that
thread owns.  The list entries are dynamically allocated, and cached on a free
list.  Each thread has its own free list, so there is no additional locking
required at all, which should minimize the impact on SMP performance.  

When a thread wants to place a read lock, it is first determined whether
it has a lock already by scanning through the list. So the Unix98 requirements
for recursive read locks can be met.

When a thread makes a read lock for the first time, a lock info structure
is added to its list. If the structure cannot be allocated, then a
special counter within the thread context is incremented; this counter
is called the ``untracked read lock count''.

A thread whose untracked lock count is positive has one or more read locks
whose identities are not tracked in the list. Whenever such a thread wants to
place a read lock, it is given priority over waiting writers, because it cannot
be proven that it doesn't already have a read lock on the same object (except
in the case that the lock object itself has a read lock count of zero, which
isn't worth bothering with).

This untracked lock count only comes into play when a memory allocation failure
occurs; the theory is that in that case, the application has more important
problems than some reader getting priority that it normally should not have.

This read-write lock implementation is geared toward good performance with
applications that don't allow thread to make a large number of simultaneous
read locks. The lists are scanned linearly, and a thread's list is proportional
to how many distinct pthread_rwlock_t objects it has readlocked.

Another thing: I added a new attribute called
PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP.  The application developer can
use this attribute, which will turn off the use of all these extra data
structures and counters, at the cost of sacrificing the ability to do recursive
read locks.

I'm not ready to put the patch out yet, because I just finished coding it,
and I think I'm just about ready to fall flat on my face.