Re: read-write locks

[Kamil Dudka]

On Thursday, January 05, 2017 21:13:07 Bruno Haible wrote:
> Torvald Riegel wrote:
> > IMO, users of reader-writer locks should treat them as a
> > mutual-exclusion mechanism.  That is, a mechanism that just ensures that
> > two critical sections will not execute concurrently (except if both are
> > readers, of course), so at the same time.  It is also important to
> > understand what this does not mean, for example any prioritization of
> > threads attempting to acquire a reader-writer lock.  Claiming that
> > prefering writers is required for reader-writer locks to be usable is
> > wrong.  If a program needs a particular sort of fairness or
> > starvation-freedom, there are several ways to ensure that, and this does
> > not require to be the same mechanism as the mutual exclusion mechanism.
> > 
> > Please also do note that you seem to be getting along fine with
> > exclusive mutexes that are not guaranteed to be fair or starvation-free.
> > 
> > If glibc is making a certain decision about semantics, it might be
> > worthwhile to consider (see http://austingroupbugs.net/view.php?id=1111
> > and https://sourceware.org/bugzilla/show_bug.cgi?id=13701).
> 
> Some background about the thinking and methodology that drives gnulib:
> 
> * Gnulib tries to makes POSIX (and other) APIs usable in an easy way.
>   We work around not only outright bugs, but also usability problems
>   that get in the way, such as:
>   * gnulib overrides the printf() function if this function crashes on
>     random data (the crash would be standards compliant, some people say,
>     but the data can be read from external files and we don't want our
>     programs to crash).
>   * gnulib overrides the fmal() function if it produces mathematically
>     incorrect values.
>   * gnulib overrides the iconv_open() function so that it will never report
>     that it cannot convert from "ISO-8859-1" to "UTF-8".
>   * gnulib overrides the re_search() function so that it understands
>     the most important parts of GNU regex syntax.
> 
> * Gnulib favours reliability over efficiency. For example:
>   * "cp --help > /dev/full" fails with an error message. Thanks to gnulib.
>   * Its date parser prints warnings when there are ambiguities.
>   * It makes it easy to check all memory allocations (module 'xalloc'),
>     all size_t computations (module 'xsize'), and to not overlook failures
>     of POSIX function such as freopen, getcwd, readlink, setenv, strtol,
>     vasprintf etc.
> 
> If it costs an allocation of a couple of memory words, or a couple of
> extra instruction, to achieve these goals, we just don't care.

Unfortunately, it is not the only cost.  Please take into consideration also 
the manpower spent on debugging random build hangs in each single GNU project 
that happened to pull in gnulib's lock module.  When you run tests in parallel 
and have no direct access to build machines, it is not even obvious which of 
the tests hangs.  Additionally, I guess that most of the projects whose builds 
hanged for no apparent reason do not care about rwlocks at all.

> You as a libc implementor are under pressure of delivering something
> optimized for speed, because glibc will [probably] be compared against
> competitors on the basis of some benchmarks. (Well, at least Ulrich Drepper
> was most proud of the speed of his NPTL.)
> 
> Whereas each of the gnulib maintainers is maintaining some programs.
> And as application programmers the worst case for us is not that our
> program got 20% slower, but that it crashes or - worse - hangs.
> 
> > Claiming that prefering writers is required for reader-writer locks
> > to be usable is wrong.
> 
> With the background above, you will understand why I claim that a gnulib
> 'lock' module is not reliable when its own unit test hangs on some
> platforms and not on others.

Exactly.  Even worse when it hangs only occasionally on remote builders.

> We want a lock facility that can EASILY achieve
>   - no writer starvation, and
>   - no reader starvation.

Which gnulib-based projects have the above requirements (besides the test)?

> > If a program needs a particular sort of fairness or
> > starvation-freedom, there are several ways to ensure that, and this does
> > not require to be the same mechanism as the mutual exclusion mechanism.
> 
> "If you want API A to be reliable, you need also to use API B and API C."

Reliable with regards to what?  Are the fairness guarantees supposedly 
provided by gnulib's rwlock implementation documented anywhere?

Kamil

> OK, we learned the hard way that
>   - in order to use stdout reliably, we need the 'closeout' module.
>   - in order to copy files reliably, we need the 'acl' module.
>   - and so on.
> 
> So, what is the fairness-ensuring mechanism that will make use of locks
> starvation-free? Can it be *easily* and *portably* put in place?
> 
> As far as I understood, for rwlocks, one can
>   * avoid writer starvation through "prefer writers" in
> pthread_rwlock_rdlock, AND, at the same time,
>   * avoid reader starvation through "prefer readers during unlock from a
> writer" in pthread_rwlock_unlock [1].
> 
> Bruno
> 
> [1] http://www.doc.ic.ac.uk/~jnm/concurrency/online/monitors/sld026.htm