Re: read-write locks

[Torvald Riegel]

On Thu, 2017-01-05 at 21:13 +0100, 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.
> 
> 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.)

This is not about benchmark competitions.   Efficiency matters, at the
very least regarding energy usage.  Data centers use a lot of energy,
and when things can't be computed fast enough, people buy more machines.

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

That's the optimistic perspective.  But if you slow down
synchronization, you will likely decrease exploitable parallelism in
your program; this means this isn't linear anymore, but bounds total
achievable speedup.

> > 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. We want a lock facility that can EASILY
> achieve
>   - no writer starvation, and
>   - no reader starvation.

Prefering writers conflicts with wanting to have no reader starvation.

Also, "easy to use" does not mean enabling misuse of a tool, or trying
to make a tool be usable outside it's intended purpose.  In such cases,
it's often easier to use the tool as intended.

This isn't changed by the fact that misuse of the tool can be
demonstrated (ie, the unit test).

I'd claim that it is not that hard to understand when a program needs
fairness.  Simplified, whenever you have a bounded amount of parallel
work, you don't care what gets executed first.

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

You control the incoming work.  The rwlock itself is not the best
mechanism for that.  It gives you just mutual exclusion, and that is
okay.

Look at your unit test, for example.  Typically, the transactions would
be the result of some input operation, not spawned as fast as possible.
Programs have a choice to not read input, typically.  If you really have
potentially more work to do than you can compute fast enough, you have
much bigger problems than no fairness.
If you want to spawn random work, then you can easily throttle that, for
example with a mutex/condvar combination.

If gnulib really wants to make concurrency simpler, than it should look
at higher-level abstractions first.  Especially parallelism.  But maybe
it should then just wait for what C++ specifies, or contribute to that
(look at ISO C++ Study Group 1's work, in particular).