pthread_rwlockattr_setkind_np.3: Remove bug notes.

The notes in pthread_rwlockattr_setkind_np.3 imply there is a bug
in glibc's implementation of PTHREAD_RWLOCK_PREFER_WRITER_NP (a
non-portable constant anyway), but this is not true. The implementation
of PTHREAD_RWLOCK_PREFER_WRITER_NP is made almost impossible by the
POSIX standard requirement that reader locks be allowed to be recursive,
and that requirement makes writer preference deadlock without an impossibly
complex requirement that we track all reader locks. Therefore the only
sensible solution was to add PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP
and disallow recursive reader locks if you want writer preference.

This patch removes the bug description and documents the current state
and recommendations for glibc. I have also updated bug 7057 with this
information, answering Steven Munroe's almost 10 year old question :-)
I hope Steven is enjoying his much earned retirement.

Tested on master.

Please apply to master.

Should we move the glibc discussion to some footnote? Some libc may be
able to implement the requirement to avoid deadlocks in the future, but
I doubt it (fundamental CS stuff).

---

Cheers,
Carlos.

At 2018-11-15T10:03:41-0500, Carlos O'Donell wrote:
> diff --git a/man3/pthread_rwlockattr_setkind_np.3 b/man3/pthread_rwlockattr_setkind_np.3
> index 3cca7d864..6b2b8db39 100644
> --- a/man3/pthread_rwlockattr_setkind_np.3
> +++ b/man3/pthread_rwlockattr_setkind_np.3
[...]
> +.\" 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.
              ^
This period is not in the original quotation and grammatically doesn't
belong there.

Is the Austin Group aware of the larger issue?  It seems reasonable to
assume that they don't intend to mandate that system implementors
resolve an unsolved problem in computer science.

On 11/15/18 10:21 AM, G. Branden Robinson wrote:
> At 2018-11-15T10:03:41-0500, Carlos O'Donell wrote:
>> diff --git a/man3/pthread_rwlockattr_setkind_np.3 b/man3/pthread_rwlockattr_setkind_np.3
>> index 3cca7d864..6b2b8db39 100644
>> --- a/man3/pthread_rwlockattr_setkind_np.3
>> +++ b/man3/pthread_rwlockattr_setkind_np.3
> [...]
>> +.\" 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.
>               ^
> This period is not in the original quotation and grammatically doesn't
> belong there.

My mistake. It should not be there, I must have added it by accident when
I wrapped the text from the email.

> Is the Austin Group aware of the larger issue?  It seems reasonable to
> assume that they don't intend to mandate that system implementors
> resolve an unsolved problem in computer science. 

In a sense this isn't an Austin Group issue.

The POSIX interfaces do not allow you to specify a writer preference,
and by default can lead to writer starvation.

You might consider TPS with priority scheduling to allow such writers
of higher priority to have preference, but we don't implement that in
glibc (see issue #1111 below).

The writer preference was added by glibc to mirror the reader preference.
The writer preference defaults to doing nothing, because it is believed
that doing anything *and* supporting recursive readlocks leads to deadlock.
Therefore to make it clear to developers that you *must* never use
recursive read locks a 3rd constant was provided for the rwlock kind.

At a high level the Austin Group *is* aware of the issue.

http://austingroupbugs.net/view.php?id=720
In issue #720 it was ruled that read locks are recursive, and write
locks are not recursive.

http://austingroupbugs.net/view.php?id=1111
In issue #1111 it is discussed that only through TPS can you achieve
writer preference at the cost of never allowing recursive read locks
on that lock. See "Description" for the bug, item (2).

Thus the most directly applicable issue was #1111, since it involved
TPS and writer threads that can preempt reader threads, but even
there the consideration was that the deadlocks caused by the recursive
reader locks were a program bug.

In glibc we took the position that we would simply not allow the
deadlocks to occur. Your choices in glibc are:

(a) PTHREAD_RWLOCK_PREFER_READER_NP
- Prefer readers.
- Support recursive read locks.

(b) PTHREAD_RWLOCK_PREFER_WRITER_NP (misleading)
- Prefer readers.
- Support recursive read locks.
- Results in writer starvation but *not* deadlocks.

(c) PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP
- Prefer writers.
- Ban recursive read locks.
- Results in reader starvation.

Does that answer your question?

At 2018-11-15T16:57:15-0500, Carlos O'Donell wrote:
> In a sense this isn't an Austin Group issue.
[...]
> Does that answer your question?

Eminently so!  Thank you.

Regards,
Branden

Hello Carlos,

On 11/15/18 4:03 PM, Carlos O'Donell wrote:
> The notes in pthread_rwlockattr_setkind_np.3 imply there is a bug
> in glibc's implementation of PTHREAD_RWLOCK_PREFER_WRITER_NP (a
> non-portable constant anyway), but this is not true. The implementation
> of PTHREAD_RWLOCK_PREFER_WRITER_NP is made almost impossible by the
> POSIX standard requirement that reader locks be allowed to be recursive,
> and that requirement makes writer preference deadlock without an impossibly
> complex requirement that we track all reader locks. Therefore the only
> sensible solution was to add PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP
> and disallow recursive reader locks if you want writer preference.
> 
> This patch removes the bug description and documents the current state
> and recommendations for glibc. I have also updated bug 7057 with this
> information, answering Steven Munroe's almost 10 year old question :-)
> I hope Steven is enjoying his much earned retirement.
> 
> Tested on master.
> 
> Please apply to master.

Thanks. Patch applied.

> Should we move the glibc discussion to some footnote? Some libc may be
> able to implement the requirement to avoid deadlocks in the future, but
> I doubt it (fundamental CS stuff).

I think the text is okay as is.

Cheers,

Michael

> diff --git a/man3/pthread_rwlockattr_setkind_np.3 b/man3/pthread_rwlockattr_setkind_np.3
> index 3cca7d864..6b2b8db39 100644
> --- a/man3/pthread_rwlockattr_setkind_np.3
> +++ b/man3/pthread_rwlockattr_setkind_np.3
> @@ -79,7 +79,31 @@ starved.
>  .B PTHREAD_RWLOCK_PREFER_WRITER_NP
>  This is intended as the write lock analog of
>  .BR PTHREAD_RWLOCK_PREFER_READER_NP .
> -But see BUGS.
> +This is ignored by glibc because the POSIX requirement to support
> +recursive writer locks would cause this option to create trivial
> +deadlocks; instead use
> +.B PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP
> +which ensures the application developer will not take recursive
> +read locks thus avoiding deadlocks.
> +.\" ---
> +.\" 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.
> +.\" ---
> +.\" http://sources.redhat.com/ml/libc-alpha/2000-01/msg00055.html
> +.\" https://sourceware.org/bugzilla/show_bug.cgi?id=7057
>  .TP
>  .B PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP
>  Setting the lock kind to this
> @@ -115,17 +139,5 @@ functions first appeared in glibc 2.1.
>  .SH CONFORMING TO
>  These functions are non-standard GNU extensions;
>  hence the suffix "_np" (nonportable) in the names.
> -.SH BUGS
> -Setting the value read-write lock kind to
> -.BR  PTHREAD_RWLOCK_PREFER_WRITER_NP
> -results in the same behavior as setting the value to
> -.BR PTHREAD_RWLOCK_PREFER_READER_NP .
> -As long as a reader thread holds the lock, the thread holding a
> -write lock will be starved.
> -Setting the lock kind to
> -.BR PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP
> -allows writers to run, but, as the name implies a writer
> -may not lock recursively.
> -.\" http://sourceware.org/bugzilla/show_bug.cgi?id=7057
>  .SH SEE ALSO
>  .BR pthreads (7)
> ---
> 
> Cheers,
> Carlos.
>

On 11/15/18 4:21 PM, G. Branden Robinson wrote:
> At 2018-11-15T10:03:41-0500, Carlos O'Donell wrote:
>> diff --git a/man3/pthread_rwlockattr_setkind_np.3 b/man3/pthread_rwlockattr_setkind_np.3
>> index 3cca7d864..6b2b8db39 100644
>> --- a/man3/pthread_rwlockattr_setkind_np.3
>> +++ b/man3/pthread_rwlockattr_setkind_np.3
> [...]
>> +.\" 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.
>               ^
> This period is not in the original quotation and grammatically doesn't
> belong there.

Fixed.

Thanks, Branden.

Cheers,

Michael