Implement pthread_rwlock functions for NaCl newlib.

src/untrusted/pthread/nc_rwlock.c

Index: src/untrusted/pthread/nc_rwlock.c
diff --git a/src/untrusted/pthread/nc_rwlock.c b/src/untrusted/pthread/nc_rwlock.c
new file mode 100644
index 0000000000000000000000000000000000000000..1590806eeda8aed4f0831d208b161ea3ef53b9f0
--- /dev/null
+++ b/src/untrusted/pthread/nc_rwlock.c
@@ -0,0 +1,283 @@
+/*
+ * Copyright 2014 The Native Client Authors. All rights reserved.
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+/*
+ * Native Client rwlock implementation
+ *
+ * This implementation is a 'write-preferring' reader-writer lock which
+ * avoids writer starvation by preventing readers from acquiring the lock
+ * while there are waiting writers. See:
+ * http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock
+ *
+ * The thundering herd problem is avoided by only waking a single
+ * waiter (either a single writer or a single reader) when the
+ * lock is released.
+ */
+
+#include <errno.h>
+
+#include "native_client/src/untrusted/pthread/pthread.h"
+#include "native_client/src/untrusted/pthread/pthread_internal.h"
+#include "native_client/src/untrusted/pthread/pthread_types.h"
+
+int pthread_rwlockattr_init(pthread_rwlockattr_t *attr) {
+  attr->type = PTHREAD_PROCESS_PRIVATE;
+  return 0;
+}
+
+int pthread_rwlockattr_destroy(pthread_rwlockattr_t *attr) {
+  return 0;
+}
+
+int pthread_rwlockattr_getpshared(const pthread_rwlockattr_t *attr,
+                                  int *pshared) {
+  *pshared = attr->type;
+  return 0;
+}
+
+int pthread_rwlockattr_setpshared(pthread_rwlockattr_t *attr, int pshared) {
+  if (pshared != PTHREAD_PROCESS_PRIVATE && pshared != PTHREAD_PROCESS_SHARED)
+    return EINVAL;
+  attr->type = pshared;
+  return 0;
+}
+
+int pthread_rwlock_init(pthread_rwlock_t *rwlock,
+                        const pthread_rwlockattr_t *attr) {
+  if (attr != NULL && attr->type != PTHREAD_PROCESS_PRIVATE)
+    return EINVAL;
+  rwlock->writer_thread_id = NACL_PTHREAD_ILLEGAL_THREAD_ID;
+  rwlock->writers_waiting = 0;
+  rwlock->reader_count = 0;
+  int rc = pthread_mutex_init(&rwlock->mutex, NULL);
+  if (rc != 0)
+    return rc;
+  rc = pthread_cond_init(&rwlock->write_possible, NULL);
+  if (rc != 0)
+    return rc;
+  return pthread_cond_init(&rwlock->read_possible, NULL);
+}
+
+/*
+ * Helper function used by waiting writers to determine if they can take
+ * the lock. The rwlock->mutex must be held when calling this function.
+ * Returns 1 if the write lock can be taken, 0 if it can't.
+ */
+static inline int write_lock_available(pthread_rwlock_t *rwlock) {
+  /*
+   * Write lock is available if there is no current writer and no current
+   * readers.
+   */
+  if (rwlock->writer_thread_id != NACL_PTHREAD_ILLEGAL_THREAD_ID)
+    return 0;
+  if (rwlock->reader_count > 0)
+    return 0;
+  return 1;
+}
+
+/*
+ * Helper function used by waiting readers to determine if they can take
+ * the lock. The rwlock->mutex must be held when calling this function.
+ * Returns 1 if the write lock can be taken, 0 if it can't.
+ */
+static inline int read_lock_available(pthread_rwlock_t *rwlock) {
+  /*
+   * Read lock is available if there is no current writer and no *waiting*
+   * writers.
+   */
+  if (rwlock->writer_thread_id != NACL_PTHREAD_ILLEGAL_THREAD_ID)
+    return 0;
+  if (rwlock->writers_waiting > 0)

[Mark Seaborn, 2015/01/29 00:40:37]

I was ready to LG this when I noticed a potentially-blocking problem.  Plus I
have a comment about a non-blocking issue.  (Puns about blocking not intended.
:-) )

1) What happens if one thread claims a write lock while another thread
recursively claims a read lock?

For example:

 * Thread 1 calls pthread_rwlock_rdlock(): Claims read lock.
 * Thread 2 calls pthread_rwlock_rwlock(): It blocks.  There is now a waiting
writer.
 * Thread 1 calls pthread_rwlock_rdlock(): It blocks because there is a waiting
writer.  This causes a deadlock.

Thread 1's recursive use of the lock is valid according to
http://pubs.opengroup.org/onlinepubs/7908799/xsh/pthread_rwlock_rdlock.html: "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)."

I think this is why people usually don't implement pthread_rwlock_rdlock() as
blocking when there are waiting writers.

e.g. See this:
http://stackoverflow.com/questions/2190090/how-to-prevent-writer-starvation-i...
-- glibc provides PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP as an extension
for programs that don't need recursive read locks.

I expect this can be tweaked by changing read_lock_available() to return true if
the read lock is currently held?

2) Non-blocker: The test coverage doesn't check correctness in some important
cases.  e.g. It doesn't check for the "zero timeout" problem I noticed earlier. 
I expect you probably don't want to add more tests at this stage, and this
doesn't block committing this change.  But I can give you some pointers on how
to test properties like this, if you want.

+    return 0;
+  return 1;
+}
+
+/*
+ * Internal function used to acquire the read lock.
+ * This operates in three different ways in order to implement the three public
+ * functions:
+ *  pthread_rwlock_rdlock
+ *  pthread_rwlock_tryrdlock
+ *  pthread_rwlock_timedrdlock
+ */
+static int rdlock_internal(pthread_rwlock_t *rwlock,
+                           const struct timespec *abs_timeout,
+                           int try_only) {
+  int rc2;
+  int rc = pthread_mutex_lock(&rwlock->mutex);
+  if (rc != 0)
+    return rc;
+
+  /*
+   * Wait repeatedly until the write preconditions are met.
+   * In theory this loop should only execute once because the preconditions
+   * should always be true when the condition is signaled.
+   */
+  while (!read_lock_available(rwlock)) {
+    if (try_only) {
+      rc = EBUSY;
+    } else if (abs_timeout != NULL) {
+      rc = pthread_cond_timedwait(&rwlock->read_possible,
+                                  &rwlock->mutex,
+                                  abs_timeout);
+    } else {
+      rc = pthread_cond_wait(&rwlock->read_possible, &rwlock->mutex);
+    }
+    if (rc != 0)
+      goto done;
+  }
+
+  /* Acquire the read lock. */
+  rwlock->reader_count++;
+done:
+  rc2 = pthread_mutex_unlock(&rwlock->mutex);
+  return rc == 0 ? rc2 : rc;
+}
+
+/*
+ * Internal function used to acquire the write lock.
+ * This operates in three different ways in order to implement the three public
+ * functions:
+ *  pthread_rwlock_wrlock
+ *  pthread_rwlock_trywrlock
+ *  pthread_rwlock_timedwrlock
+ */
+static int rwlock_internal(pthread_rwlock_t *rwlock,
+                           const struct timespec *abs_timeout,
+                           int try_only) {
+  int rc2;
+  int rc = pthread_mutex_lock(&rwlock->mutex);
+  if (rc != 0)
+    return rc;
+
+  /* Wait repeatedly until the write preconditions are met */
+  while (!write_lock_available(rwlock)) {
+    if (try_only) {
+      rc = EBUSY;
+    } else {
+      /*
+       * Before waiting (and releasing the lock) we increment the
+       * waiting_writers count so the unlocking code knows to wake
+       * a writer first (before any waiting readers).
+       */
+      rwlock->writers_waiting++;
+      if (abs_timeout != NULL) {
+        rc = pthread_cond_timedwait(&rwlock->write_possible,
+                                    &rwlock->mutex,
+                                    abs_timeout);
+      } else {
+        rc = pthread_cond_wait(&rwlock->write_possible,
+                               &rwlock->mutex);
+      }
+      rwlock->writers_waiting--;
+    }
+    if (rc != 0)
+      goto done;
+  }
+
+  /* Acquire the write lock. */
+  rwlock->writer_thread_id = pthread_self();
+done:
+  rc2 = pthread_mutex_unlock(&rwlock->mutex);
+  return rc == 0 ? rc2 : rc;
+}
+
+int pthread_rwlock_timedrdlock(pthread_rwlock_t *rwlock,
+                               const struct timespec *abs_timeout) {
+  return rdlock_internal(rwlock, abs_timeout, 0);
+}
+
+int pthread_rwlock_rdlock(pthread_rwlock_t *rwlock) {
+  return rdlock_internal(rwlock, NULL, 0);
+}
+
+int pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock) {
+  return rdlock_internal(rwlock, NULL, 1);
+}
+
+int pthread_rwlock_wrlock(pthread_rwlock_t *rwlock) {
+  return rwlock_internal(rwlock, NULL, 0);
+}
+
+int pthread_rwlock_timedwrlock(pthread_rwlock_t *rwlock,
+                               const struct timespec *abs_timeout) {
+  return rwlock_internal(rwlock, abs_timeout, 0);
+}
+
+int pthread_rwlock_trywrlock(pthread_rwlock_t *rwlock) {
+  return rwlock_internal(rwlock, NULL, 1);
+}
+
+int pthread_rwlock_unlock(pthread_rwlock_t *rwlock) {
+  int rc2;
+  int rc = pthread_mutex_lock(&rwlock->mutex);
+  if (rc != 0)
+    return rc;
+
+  if (rwlock->writer_thread_id != NACL_PTHREAD_ILLEGAL_THREAD_ID) {
+    /* The write lock is held. Ensure it's the current thread that holds it. */
+    if (rwlock->writer_thread_id != pthread_self()) {
+      rc = EPERM;
+      goto done;
+    }
+
+    /* Release write lock. */
+    rwlock->writer_thread_id = NACL_PTHREAD_ILLEGAL_THREAD_ID;
+    if (rwlock->writers_waiting > 0) {
+      /* Wake a waiting writer if there is one. */
+      rc = pthread_cond_signal(&rwlock->write_possible);
+    } else {
+      /* Otherwise wake a waiting reader. */
+      rc = pthread_cond_signal(&rwlock->read_possible);
+    }
+  } else {
+    if (rwlock->reader_count == 0) {
+      rc = EPERM;
+      goto done;
+    }
+
+    /* Release read lock. */
+    rwlock->reader_count--;
+    if (rwlock->reader_count == 0 && rwlock->writers_waiting > 0) {
+      /* Wake a waiting writer. */
+      rc = pthread_cond_signal(&rwlock->write_possible);
+    }
+  }
+
+done:
+  rc2 = pthread_mutex_unlock(&rwlock->mutex);
+  return rc == 0 ? rc2 : rc;
+}
+
+int pthread_rwlock_destroy(pthread_rwlock_t *rwlock) {
+  /* Return EBUSY if another thread holds the mutex. */
+  int rc = pthread_mutex_trylock(&rwlock->mutex);
+  if (rc != 0) {
+    return rc;
+  }
+
+  /* Return EBUSY if there are active readers or an active writer. */
+  if (rwlock->reader_count != 0) {
+    pthread_mutex_unlock(&rwlock->mutex);
+    return EBUSY;
+  }
+  if (rwlock->writer_thread_id != NACL_PTHREAD_ILLEGAL_THREAD_ID) {
+    pthread_mutex_unlock(&rwlock->mutex);
+    return EBUSY;
+  }
+
+  int rc1 = pthread_cond_destroy(&rwlock->write_possible);
+  int rc2 = pthread_cond_destroy(&rwlock->read_possible);
+
+  /* Finally unlock the mutex and destroy it. */
+  pthread_mutex_unlock(&rwlock->mutex);
+  int rc3 = pthread_mutex_destroy(&rwlock->mutex);
+  if (rc1 != 0)
+    return rc1;
+  if (rc2 != 0)
+    return rc2;
+  return rc3;
+}