[musl] Simple question regarding read-write locks precedence

[musl] Simple question regarding read-write locks precedence

[Koen Vandeputte]

Hi All,

I've written a user app which make use of reader-writer locks.

Topology is pretty simple:

- 1 writer

- 4 readers


Writes only occur once in a while.

Readers are heavy users of the lock.


The default behavior in musl is Reader precedence.

In my usecase, it means that a writer never aquires the lock causing 
writer starvation.

Debugging nicely shows that readers also "jump over" the waiting writer 
as there is always at least 1 reader present in the critical section at 
any time.

Going through the source code shows that there is no support for 
specifying lock attributes which give writers precedence over readers.


Is there an update scheduled to add the required attribute types which 
allow writer precedence to avoid starvation?


Thanks,

Koen

Re: [musl] Simple question regarding read-write locks precedence

[Rich Felker]

On Tue, Mar 31, 2020 at 05:05:27PM +0200, Koen Vandeputte wrote:
> Hi All,
> 
> I've written a user app which make use of reader-writer locks.
> 
> Topology is pretty simple:
> 
> - 1 writer
> 
> - 4 readers
> 
> 
> Writes only occur once in a while.
> 
> Readers are heavy users of the lock.
> 
> 
> The default behavior in musl is Reader precedence.
> 
> In my usecase, it means that a writer never aquires the lock causing
> writer starvation.
> 
> Debugging nicely shows that readers also "jump over" the waiting
> writer as there is always at least 1 reader present in the critical
> section at any time.
> 
> Going through the source code shows that there is no support for
> specifying lock attributes which give writers precedence over
> readers.
> 
> 
> Is there an update scheduled to add the required attribute types
> which allow writer precedence to avoid starvation?

The POSIX model of allowing recursive read locks fundamentally doesn't
admit writer preference -- there's no way to distinguish the case of
new reader vs an additional recursive lock by an existing reader
without O(n) space. If you disallow the latter (recursive locks while
a writer is waiting) you get deadlocks all over the place in intended
usage model.

Do you have any suggested approaches for making this better?

Rich

Re: [musl] Simple question regarding read-write locks precedence

[Koen Vandeputte]

On 31.03.20 17:09, Rich Felker wrote:
> On Tue, Mar 31, 2020 at 05:05:27PM +0200, Koen Vandeputte wrote:
>> Hi All,
>>
>> I've written a user app which make use of reader-writer locks.
>>
>> Topology is pretty simple:
>>
>> - 1 writer
>>
>> - 4 readers
>>
>>
>> Writes only occur once in a while.
>>
>> Readers are heavy users of the lock.
>>
>>
>> The default behavior in musl is Reader precedence.
>>
>> In my usecase, it means that a writer never aquires the lock causing
>> writer starvation.
>>
>> Debugging nicely shows that readers also "jump over" the waiting
>> writer as there is always at least 1 reader present in the critical
>> section at any time.
>>
>> Going through the source code shows that there is no support for
>> specifying lock attributes which give writers precedence over
>> readers.
>>
>>
>> Is there an update scheduled to add the required attribute types
>> which allow writer precedence to avoid starvation?
> The POSIX model of allowing recursive read locks fundamentally doesn't
> admit writer preference -- there's no way to distinguish the case of
> new reader vs an additional recursive lock by an existing reader
> without O(n) space. If you disallow the latter (recursive locks while
> a writer is waiting) you get deadlocks all over the place in intended
> usage model.

Hi Rich,

Thanks for the very fast reply.

I've red about the trivial deadlocks, but isn't this the reason why 
*PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP* exists?

It's the user's responsibility to avoid recursive reading here .. but at 
least it allows preferred writes.


See description in: 
http://man7.org/linux/man-pages/man3/pthread_rwlockattr_setkind_np.3.html

>
> Do you have any suggested approaches for making this better?
I'll definitely take a look at it.
>
> Rich

Re: [musl] Simple question regarding read-write locks precedence

[Rich Felker]

On Tue, Mar 31, 2020 at 05:21:06PM +0200, Koen Vandeputte wrote:
> 
> On 31.03.20 17:09, Rich Felker wrote:
> >On Tue, Mar 31, 2020 at 05:05:27PM +0200, Koen Vandeputte wrote:
> >>Hi All,
> >>
> >>I've written a user app which make use of reader-writer locks.
> >>
> >>Topology is pretty simple:
> >>
> >>- 1 writer
> >>
> >>- 4 readers
> >>
> >>
> >>Writes only occur once in a while.
> >>
> >>Readers are heavy users of the lock.
> >>
> >>
> >>The default behavior in musl is Reader precedence.
> >>
> >>In my usecase, it means that a writer never aquires the lock causing
> >>writer starvation.
> >>
> >>Debugging nicely shows that readers also "jump over" the waiting
> >>writer as there is always at least 1 reader present in the critical
> >>section at any time.
> >>
> >>Going through the source code shows that there is no support for
> >>specifying lock attributes which give writers precedence over
> >>readers.
> >>
> >>
> >>Is there an update scheduled to add the required attribute types
> >>which allow writer precedence to avoid starvation?
> >The POSIX model of allowing recursive read locks fundamentally doesn't
> >admit writer preference -- there's no way to distinguish the case of
> >new reader vs an additional recursive lock by an existing reader
> >without O(n) space. If you disallow the latter (recursive locks while
> >a writer is waiting) you get deadlocks all over the place in intended
> >usage model.
> 
> Hi Rich,
> 
> Thanks for the very fast reply.
> 
> I've red about the trivial deadlocks, but isn't this the reason why
> *PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP* exists?
> 
> It's the user's responsibility to avoid recursive reading here ..
> but at least it allows preferred writes.
> 
> 
> See description in: http://man7.org/linux/man-pages/man3/pthread_rwlockattr_setkind_np.3.html

Thanks. While I specifically did not implement (or define a macro for)
PTHREAD_RWLOCK_PREFER_WRITER_NP because it's misleading to advertise
support for it when it fundamentally can't work,
PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP seems like a viable
extension to support. Anyone else see potential problems supporting it
that I might be missing?

Rich

Re: [musl] Simple question regarding read-write locks precedence

[Markus Wichmann]

On Tue, Mar 31, 2020 at 11:26:46AM -0400, Rich Felker wrote:
> Thanks. While I specifically did not implement (or define a macro for)
> PTHREAD_RWLOCK_PREFER_WRITER_NP because it's misleading to advertise
> support for it when it fundamentally can't work,
> PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP seems like a viable
> extension to support. Anyone else see potential problems supporting it
> that I might be missing?
>
> Rich

I do see one problem: The manpage (the only spec available) contradicts
itself. In the Description section, it says (of the new option):

|Setting the lock kind to this avoids writer starvation as long as any
|read locking is not done in a recursive fashion.

OK, but in the Bugs section:

|Setting the lock kind to PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP
|allows writers to run, but, as the name implies a writer may not lock
|recursively.

Well, which is it? Are writers or readers not supposed to recurse? I
thought writers aren't supposed to recurse, anyway. Or is it possible we
need to file a bug report to Michael Kerrisk? Maybe it was supposed to
say "reader" here, then it would make sense. As it stands, though, the
spec is unclear.

Ciao,
Markus

Re: [musl] Simple question regarding read-write locks precedence

[Rich Felker]

On Tue, Mar 31, 2020 at 07:21:20PM +0200, Markus Wichmann wrote:
> On Tue, Mar 31, 2020 at 11:26:46AM -0400, Rich Felker wrote:
> > Thanks. While I specifically did not implement (or define a macro for)
> > PTHREAD_RWLOCK_PREFER_WRITER_NP because it's misleading to advertise
> > support for it when it fundamentally can't work,
> > PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP seems like a viable
> > extension to support. Anyone else see potential problems supporting it
> > that I might be missing?
> >
> > Rich
> 
> I do see one problem: The manpage (the only spec available) contradicts
> itself. In the Description section, it says (of the new option):
> 
> |Setting the lock kind to this avoids writer starvation as long as any
> |read locking is not done in a recursive fashion.
> 
> OK, but in the Bugs section:
> 
> |Setting the lock kind to PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP
> |allows writers to run, but, as the name implies a writer may not lock
> |recursively.
> 
> Well, which is it? Are writers or readers not supposed to recurse? I
> thought writers aren't supposed to recurse, anyway. Or is it possible we
> need to file a bug report to Michael Kerrisk? Maybe it was supposed to
> say "reader" here, then it would make sense. As it stands, though, the
> spec is unclear.

I think that's pretty clearly just a mistake in the man page that
should be reported. CC'ing.

Rich

Re: [musl] Simple question regarding read-write locks precedence

[Markus Wichmann]

On Tue, Mar 31, 2020 at 01:37:24PM -0400, Rich Felker wrote:
> I think that's pretty clearly just a mistake in the man page that
> should be reported. CC'ing.
>
> Rich

Well, nevermind. I just realized that I only checked my local manpages,
which are version 4.15, whereas the online version is 5.05, and the
online release no longer has a Bugs section, instead inlining the
information into the Description section. The only mention of writer
recursion in the online version is in the description of
PTHREAD_RWLOCK_PREFER_WRITER_NP. That also probably means to say reader.

Ciao,
Markus

Re: [musl] Simple question regarding read-write locks precedence

[Michael Kerrisk (man-pages)]

On 3/31/20 8:38 PM, Markus Wichmann wrote:
> On Tue, Mar 31, 2020 at 01:37:24PM -0400, Rich Felker wrote:
>> I think that's pretty clearly just a mistake in the man page that
>> should be reported. CC'ing.
>>
>> Rich
> 
> Well, nevermind. I just realized that I only checked my local manpages,
> which are version 4.15, whereas the online version is 5.05, and the
> online release no longer has a Bugs section, instead inlining the
> information into the Description section. 

Yes. See https://git.kernel.org/pub/scm/docs/man-pages/man-pages.git/commit/?id=0d255e74c098dd2ad420367503398ad7f8f82024

> The only mention of writer
> recursion in the online version is in the description of
> PTHREAD_RWLOCK_PREFER_WRITER_NP. That also probably means to say reader.

So, is there still something you think needs fixing in the page?

Thanks,

Michael


-- 
Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Linux/UNIX System Programming Training: http://man7.org/training/

Re: [musl] Simple question regarding read-write locks precedence

[Markus Wichmann]

On Tue, Mar 31, 2020 at 09:02:24PM +0200, Michael Kerrisk (man-pages) wrote:
> So, is there still something you think needs fixing in the page?
>

Yes.

|This is ignored by glibc because the POSIX requirement to support
|recursive writer locks would cause this option to create trivial
|deadlocks;[...]

There is no POSIX requirement to support recursive writer locks. I think
this is meant to say "recursive reader locks".

Ciao,
Markus

Re: [musl] Simple question regarding read-write locks precedence

[Michael Kerrisk (man-pages)]

Hi Carlos,

Can you comment on this note about your text[1] in the 
pthread_rwlockattr_setkind_np.3 manual page:

On 3/31/20 9:45 PM, Markus Wichmann wrote:
> On Tue, Mar 31, 2020 at 09:02:24PM +0200, Michael Kerrisk (man-pages) wrote:
>> So, is there still something you think needs fixing in the page?
>>
> 
> Yes.
> 
> |This is ignored by glibc because the POSIX requirement to support
> |recursive writer locks would cause this option to create trivial
> |deadlocks;[...]
> 
> There is no POSIX requirement to support recursive writer locks. I think
> this is meant to say "recursive reader locks".

Thanks,

Michael

[1] https://git.kernel.org/pub/scm/docs/man-pages/man-pages.git/commit/?id=0d255e74c098dd2ad420367503398ad7f8f82024


-- 
Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Linux/UNIX System Programming Training: http://man7.org/training/