Add implementation of pthread_rwlock based on NaCl futexs

Add implementation of pthread_rwlock based on NaCl futexs

This implementation almost completely based on the
implementation within bionic (libc/bionic/pthread_rwlock.cpp)

BUG= https://code.google.com/p/nativeclient/issues/detail?id=3960
TEST= run_rwlock_test

[Sam Clegg, 2014-09-29 21:33:16]

sbc@chromium.org changed reviewers:
+ mseaborn@chromium.org

[Sam Clegg, 2014-09-29 21:33:16]

Sending out for initial review to get early feedback on basic approach.

Mark, do you think this implementation based on atomic
builts combined with IRT futex calls makes sense? There is an older version in
the android repo that simply uses a mutex and cond var (as did my own initial
impl).

[Sam Clegg, 2014-10-02 19:41:18]

Ping.  Can you take a quick look.  If this looks about right I'll write some
more tests and try to get this landed.

[Mark Seaborn, 2014-10-02 19:58:51]

On 2014/10/02 19:41:18, Sam Clegg wrote:
> Ping.  Can you take a quick look.  If this looks about right I'll write some
> more tests and try to get this landed.

This does definitely need more test coverage.  I'd ideally like to see all of
the wakeup and non-wakeup cases covered.

For an example of how to do that, see tests/futexes/futex_test.c.  See
create_waiting_thread() and assert_thread_woken()/assert_thread_not_woken().

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
File src/untrusted/pthread/nc_rwlock.c (right):

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:20: * This implemtation is based on the one
found in the bionic C library
typo

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:26: *  - remove unsuppored features such as
PTHREAD_PROCESS_PRIVATE/SHARED.
typo

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:117: * This is actually a race read as there's
nothing that guarantees the
This is not true with PNaCl, where "volatile" makes this an atomic read.

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:122: int32_t cur_state = rwlock->state;  /*
C++11 relaxed atomic read */
This isn't in C++. :-)

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:123: if (__predict_true(cur_state >= 0)) {
I don't know if nacl-gcc has __predict.  Please run trybots.

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:140: if (ret == -ETIMEDOUT) {
"ret == ETIMEDOUT".  Please add test coverage.

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:168: * should be sequentially consistent.
(currently enforced by
Capitalise as "Currently" and add "."

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:210: return
__pthread_rwlock_timedwrlock(rwlock, abs_timeout);
pthread_rwlock_timedwrlock() and __pthread_rwlock_timedwrlock() do the same
thing, so you might as well merge the two.

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:267: if
(__predict_false(rwlock->pending_readers > 0
I can't see any distinction between pending_readers and pending_writers. 
Presumably you might as well merge the two and have a single "pending_waiters"
field?

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:269:
__libnacl_irt_futex.futex_wake(&rwlock->state, INT_MAX, NULL);
Waking all the waiters doesn't seem very efficient...

It's not very fair, either.  If there are many readers, I imagine it could lead
to starvation of writers.

Do you know what the difference is between the two algorithms that Bionic
has/had?  How much more efficient is the direct-futex-based one over the
pthread_mutex+cond-based one?  Any idea how it compares with glibc's algorithm?

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/pt...
File src/untrusted/pthread/pthread.h (right):

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/pt...
src/untrusted/pthread/pthread.h:147: pthread_rwlockattr_t attr;
Not actually read, so you can omit this field.

https://codereview.chromium.org/609363003/diff/20001/tests/threads/rwlock_test.c
File tests/threads/rwlock_test.c (right):

https://codereview.chromium.org/609363003/diff/20001/tests/threads/rwlock_tes...
tests/threads/rwlock_test.c:65: rc = pthread_create(&thread, NULL,
locking_thread, NULL);
AFAICT you don't synchronise with this thread, so effectively it's not testing
for anything reliably.

[Sam Clegg, 2014-10-02 23:12:01]

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
File src/untrusted/pthread/nc_rwlock.c (right):

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:20: * This implemtation is based on the one
found in the bionic C library
On 2014/10/02 19:58:51, Mark Seaborn wrote:
> typo

Done.

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:26: *  - remove unsuppored features such as
PTHREAD_PROCESS_PRIVATE/SHARED.
On 2014/10/02 19:58:51, Mark Seaborn wrote:
> typo

Done.

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:117: * This is actually a race read as there's
nothing that guarantees the
On 2014/10/02 19:58:51, Mark Seaborn wrote:
> This is not true with PNaCl, where "volatile" makes this an atomic read.

Acknowledged.

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:122: int32_t cur_state = rwlock->state;  /*
C++11 relaxed atomic read */
On 2014/10/02 19:58:51, Mark Seaborn wrote:
> This isn't in C++. :-)

Acknowledged.

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:123: if (__predict_true(cur_state >= 0)) {
On 2014/10/02 19:58:51, Mark Seaborn wrote:
> I don't know if nacl-gcc has __predict.  Please run trybots.

Acknowledged.

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:140: if (ret == -ETIMEDOUT) {
On 2014/10/02 19:58:50, Mark Seaborn wrote:
> "ret == ETIMEDOUT".  Please add test coverage.

Done.

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:140: if (ret == -ETIMEDOUT) {
On 2014/10/02 19:58:50, Mark Seaborn wrote:
> "ret == ETIMEDOUT".  Please add test coverage.

Done.

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:168: * should be sequentially consistent.
(currently enforced by
On 2014/10/02 19:58:51, Mark Seaborn wrote:
> Capitalise as "Currently" and add "."

Done.

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:210: return
__pthread_rwlock_timedwrlock(rwlock, abs_timeout);
On 2014/10/02 19:58:51, Mark Seaborn wrote:
> pthread_rwlock_timedwrlock() and __pthread_rwlock_timedwrlock() do the same
> thing, so you might as well merge the two.

Done.

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:267: if
(__predict_false(rwlock->pending_readers > 0
On 2014/10/02 19:58:51, Mark Seaborn wrote:
> I can't see any distinction between pending_readers and pending_writers. 
> Presumably you might as well merge the two and have a single "pending_waiters"
> field?

Thats what Hans Boehm said too :)
https://android-review.googlesource.com/#/c/95031/

https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
src/untrusted/pthread/nc_rwlock.c:269:
__libnacl_irt_futex.futex_wake(&rwlock->state, INT_MAX, NULL);
On 2014/10/02 19:58:51, Mark Seaborn wrote:
> Waking all the waiters doesn't seem very efficient...
> 
> It's not very fair, either.  If there are many readers, I imagine it could
lead
> to starvation of writers.
> 
> Do you know what the difference is between the two algorithms that Bionic
> has/had?  How much more efficient is the direct-futex-based one over the
> pthread_mutex+cond-based one?  Any idea how it compares with glibc's
algorithm?

The change is here:
https://android-review.googlesource.com/#/c/95031/

Its not clear to me what was wrong with the old one or why they changed. It also
seems that they lost the writer starvation logic in the transition...  but the
code was reviewed by Hans Boehm.

Also, it loos like the previous implementation, while reducing writer
starvation, still wakes up all waiters with pthread_cond_broadcast each
time anyone unlocks.

[Sam Clegg, 2014-10-03 15:48:03]

On 2014/10/02 23:12:01, Sam Clegg wrote:
>
https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
> File src/untrusted/pthread/nc_rwlock.c (right):
> 
>
https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
> src/untrusted/pthread/nc_rwlock.c:20: * This implemtation is based on the one
> found in the bionic C library
> On 2014/10/02 19:58:51, Mark Seaborn wrote:
> > typo
> 
> Done.
> 
>
https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
> src/untrusted/pthread/nc_rwlock.c:26: *  - remove unsuppored features such as
> PTHREAD_PROCESS_PRIVATE/SHARED.
> On 2014/10/02 19:58:51, Mark Seaborn wrote:
> > typo
> 
> Done.
> 
>
https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
> src/untrusted/pthread/nc_rwlock.c:117: * This is actually a race read as
there's
> nothing that guarantees the
> On 2014/10/02 19:58:51, Mark Seaborn wrote:
> > This is not true with PNaCl, where "volatile" makes this an atomic read.
> 
> Acknowledged.
> 
>
https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
> src/untrusted/pthread/nc_rwlock.c:122: int32_t cur_state = rwlock->state;  /*
> C++11 relaxed atomic read */
> On 2014/10/02 19:58:51, Mark Seaborn wrote:
> > This isn't in C++. :-)
> 
> Acknowledged.
> 
>
https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
> src/untrusted/pthread/nc_rwlock.c:123: if (__predict_true(cur_state >= 0)) {
> On 2014/10/02 19:58:51, Mark Seaborn wrote:
> > I don't know if nacl-gcc has __predict.  Please run trybots.
> 
> Acknowledged.
> 
>
https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
> src/untrusted/pthread/nc_rwlock.c:140: if (ret == -ETIMEDOUT) {
> On 2014/10/02 19:58:50, Mark Seaborn wrote:
> > "ret == ETIMEDOUT".  Please add test coverage.
> 
> Done.
> 
>
https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
> src/untrusted/pthread/nc_rwlock.c:140: if (ret == -ETIMEDOUT) {
> On 2014/10/02 19:58:50, Mark Seaborn wrote:
> > "ret == ETIMEDOUT".  Please add test coverage.
> 
> Done.
> 
>
https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
> src/untrusted/pthread/nc_rwlock.c:168: * should be sequentially consistent.
> (currently enforced by
> On 2014/10/02 19:58:51, Mark Seaborn wrote:
> > Capitalise as "Currently" and add "."
> 
> Done.
> 
>
https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
> src/untrusted/pthread/nc_rwlock.c:210: return
> __pthread_rwlock_timedwrlock(rwlock, abs_timeout);
> On 2014/10/02 19:58:51, Mark Seaborn wrote:
> > pthread_rwlock_timedwrlock() and __pthread_rwlock_timedwrlock() do the same
> > thing, so you might as well merge the two.
> 
> Done.
> 
>
https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
> src/untrusted/pthread/nc_rwlock.c:267: if
> (__predict_false(rwlock->pending_readers > 0
> On 2014/10/02 19:58:51, Mark Seaborn wrote:
> > I can't see any distinction between pending_readers and pending_writers. 
> > Presumably you might as well merge the two and have a single
"pending_waiters"
> > field?
> 
> Thats what Hans Boehm said too :)
> https://android-review.googlesource.com/#/c/95031/
> 
>
https://codereview.chromium.org/609363003/diff/20001/src/untrusted/pthread/nc...
> src/untrusted/pthread/nc_rwlock.c:269:
> __libnacl_irt_futex.futex_wake(&rwlock->state, INT_MAX, NULL);
> On 2014/10/02 19:58:51, Mark Seaborn wrote:
> > Waking all the waiters doesn't seem very efficient...
> > 
> > It's not very fair, either.  If there are many readers, I imagine it could
> lead
> > to starvation of writers.
> > 
> > Do you know what the difference is between the two algorithms that Bionic
> > has/had?  How much more efficient is the direct-futex-based one over the
> > pthread_mutex+cond-based one?  Any idea how it compares with glibc's
> algorithm?
> 
> The change is here:
> https://android-review.googlesource.com/#/c/95031/
> 
> Its not clear to me what was wrong with the old one or why they changed. It
also
> seems that they lost the writer starvation logic in the transition...  but the
> code was reviewed by Hans Boehm.
> 
> Also, it loos like the previous implementation, while reducing writer
> starvation, still wakes up all waiters with pthread_cond_broadcast each
> time anyone unlocks.

I decided to keep things simple I go with my own implementation based on pthread
mutex and condvar: https://codereview.chromium.org/623863002/.
My implementation deals with writer starvation as well as the thundering hurd
problem, but is slightly more expensive in terms of the number of low level
operations in each call.