new futex-requeue-based pthread_cond_broadcast implementation

this avoids the "stampede effect" where pthread_cond_broadcast would
result in all waiters waking up simultaneously, only to immediately
contend for the mutex and go back to sleep.

1 files changed, 40 insertions, 1 deletions

diff --git a/src/thread/pthread_cond_broadcast.c b/src/thread/pthread_cond_broadcast.c
index dec91164..3daa7817 100644
--- a/src/thread/pthread_cond_broadcast.c
+++ b/src/thread/pthread_cond_broadcast.c
@@ -1,8 +1,47 @@
 #include "pthread_impl.h"
 
+static void unlock(pthread_cond_t *c)
+{
+	a_dec(&c->_c_bcast);
+	if (c->_c_leavers) __wake(&c->_c_bcast, -1, 0);
+}
+
 int pthread_cond_broadcast(pthread_cond_t *c)
 {
+	pthread_mutex_t *m;
+	int w;
+
+	if (!c->_c_waiters) return 0;
+	a_inc(&c->_c_bcast);
+	if (!c->_c_waiters) {
+		unlock(c);
+		return 0;
+	}
+
 	a_store(&c->_c_block, 0);
-	if (c->_c_waiters) __wake(&c->_c_block, -1, 0);
+
+	m = c->_c_mutex;
+
+	/* If mutex ptr is not available, simply wake all waiters. */
+	if (m == (void *)-1) {
+		unlock(c);
+		__wake(&c->_c_block, -1, 0);
+		return 0;
+	}
+
+	/* Move waiter count to the mutex */
+	for (;;) {
+		w = c->_c_waiters;
+		a_fetch_add(&m->_m_waiters, w);
+		if (a_cas(&c->_c_waiters, w, 0) == w) break;
+		a_fetch_add(&m->_m_waiters, -w);
+	}
+
+	/* Perform the futex requeue, waking one waiter if and only if
+	 * the calling thread does not hold the mutex. */
+	__syscall(SYS_futex, &c->_c_block, FUTEX_REQUEUE,
+		m->_m_lock!=pthread_self()->tid, INT_MAX, &m->_m_lock);
+
+	unlock(c);
 	return 0;
 }