[PATCH] private futex support

[PATCH] private futex support

[Rich Felker]

[-- Attachment #1: Type: text/plain, Size: 503 bytes --]

Here is a semi-proposed patch for private futex support, one of the
items on the roadmap for the next release cycle. However I've been
unable to demonstrate it yielding better performance than non-private
futex, and since it adds (small, but nonzero) complexity and worse
behavior on outdated (pre-2.6.22) kernels, I'm a bit hesitant to
actually commit it. If anyone is interested in this feature, please
see if you can find some examples that demonstrate that it measurably
improves performance.

Rich

[-- Attachment #2: priv_futex_v1.diff --]
[-- Type: text/plain, Size: 14118 bytes --]

diff --git a/src/internal/pthread_impl.h b/src/internal/pthread_impl.h
index 650e811..826191c 100644
--- a/src/internal/pthread_impl.h
+++ b/src/internal/pthread_impl.h
@@ -76,6 +76,7 @@ struct __timer {
 #define _c_destroy __u.__i[8]
 #define _rw_lock __u.__i[0]
 #define _rw_waiters __u.__i[1]
+#define _rw_shared __u.__i[2]
 #define _b_lock __u.__i[0]
 #define _b_waiters __u.__i[1]
 #define _b_limit __u.__i[2]
@@ -108,8 +109,13 @@ void __unmapself(void *, size_t);
 
 int __timedwait(volatile int *, int, clockid_t, const struct timespec *, void (*)(void *), void *, int);
 void __wait(volatile int *, volatile int *, int, int);
-#define __wake(addr, cnt, priv) \
-	__syscall(SYS_futex, addr, FUTEX_WAKE, (cnt)<0?INT_MAX:(cnt))
+static inline void __wake(volatile void *addr, int cnt, int priv)
+{
+	if (priv) priv = 128;
+	if (cnt<0) cnt = INT_MAX;
+	__syscall(SYS_futex, addr, FUTEX_WAKE|priv, cnt) != -EINVAL ||
+	__syscall(SYS_futex, addr, FUTEX_WAKE, cnt);
+}
 
 void __acquire_ptc();
 void __release_ptc();
diff --git a/src/thread/__timedwait.c b/src/thread/__timedwait.c
index 302273a..39eb996 100644
--- a/src/thread/__timedwait.c
+++ b/src/thread/__timedwait.c
@@ -4,12 +4,15 @@
 #include "futex.h"
 #include "syscall.h"
 
-static int do_wait(volatile int *addr, int val,
-	clockid_t clk, const struct timespec *at, int priv)
+int __timedwait(volatile int *addr, int val,
+	clockid_t clk, const struct timespec *at,
+	void (*cleanup)(void *), void *arg, int priv)
 {
-	int r;
+	int r, cs;
 	struct timespec to, *top=0;
 
+	if (priv) priv = 128;
+
 	if (at) {
 		if (at->tv_nsec >= 1000000000UL) return EINVAL;
 		if (clock_gettime(clk, &to)) return EINVAL;
@@ -22,21 +25,12 @@ static int do_wait(volatile int *addr, int val,
 		top = &to;
 	}
 
-	r = -__syscall_cp(SYS_futex, addr, FUTEX_WAIT, val, top);
-	if (r == EINTR || r == EINVAL || r == ETIMEDOUT) return r;
-	return 0;
-}
-
-int __timedwait(volatile int *addr, int val,
-	clockid_t clk, const struct timespec *at,
-	void (*cleanup)(void *), void *arg, int priv)
-{
-	int r, cs;
-
 	if (!cleanup) pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &cs);
 	pthread_cleanup_push(cleanup, arg);
 
-	r = do_wait(addr, val, clk, at, priv);
+	r = -__syscall_cp(SYS_futex, addr, FUTEX_WAIT|priv, val, top);
+	if (r == EINVAL) r = -__syscall_cp(SYS_futex, addr, FUTEX_WAIT, val, top);
+	if (r != EINTR && r != ETIMEDOUT) r = 0;
 
 	pthread_cleanup_pop(0);
 	if (!cleanup) pthread_setcancelstate(cs, 0);
diff --git a/src/thread/__wait.c b/src/thread/__wait.c
index a1e4780..ec1e820 100644
--- a/src/thread/__wait.c
+++ b/src/thread/__wait.c
@@ -3,13 +3,15 @@
 void __wait(volatile int *addr, volatile int *waiters, int val, int priv)
 {
 	int spins=10000;
-	if (priv) priv = 128; priv=0;
+	if (priv) priv = 128;
 	while (spins--) {
 		if (*addr==val) a_spin();
 		else return;
 	}
 	if (waiters) a_inc(waiters);
-	while (*addr==val)
-		__syscall(SYS_futex, addr, FUTEX_WAIT|priv, val, 0);
+	while (*addr==val) {
+		__syscall(SYS_futex, addr, FUTEX_WAIT|priv, val, 0) != -EINVAL
+		|| __syscall(SYS_futex, addr, FUTEX_WAIT, val, 0);
+	}
 	if (waiters) a_dec(waiters);
 }
diff --git a/src/thread/pthread_attr_get.c b/src/thread/pthread_attr_get.c
index 03fc91e..3d296bf 100644
--- a/src/thread/pthread_attr_get.c
+++ b/src/thread/pthread_attr_get.c
@@ -75,7 +75,7 @@ int pthread_mutexattr_getprotocol(const pthread_mutexattr_t *restrict a, int *re
 }
 int pthread_mutexattr_getpshared(const pthread_mutexattr_t *restrict a, int *restrict pshared)
 {
-	*pshared = a->__attr>>31;
+	*pshared = a->__attr / 128U % 2;
 	return 0;
 }
 
diff --git a/src/thread/pthread_cond_broadcast.c b/src/thread/pthread_cond_broadcast.c
index 0901daf..f445646 100644
--- a/src/thread/pthread_cond_broadcast.c
+++ b/src/thread/pthread_cond_broadcast.c
@@ -33,7 +33,7 @@ int pthread_cond_broadcast(pthread_cond_t *c)
 
 out:
 	a_store(&c->_c_lock, 0);
-	if (c->_c_lockwait) __wake(&c->_c_lock, 1, 0);
+	if (c->_c_lockwait) __wake(&c->_c_lock, 1, 1);
 
 	return 0;
 }
diff --git a/src/thread/pthread_cond_signal.c b/src/thread/pthread_cond_signal.c
index 71bcdcd..5fd72f9 100644
--- a/src/thread/pthread_cond_signal.c
+++ b/src/thread/pthread_cond_signal.c
@@ -4,6 +4,6 @@ int pthread_cond_signal(pthread_cond_t *c)
 {
 	if (!c->_c_waiters) return 0;
 	a_inc(&c->_c_seq);
-	if (c->_c_waiters) __wake(&c->_c_seq, 1, 0);
+	if (c->_c_waiters) __wake(&c->_c_seq, 1, c->_c_mutex!=(void*)-1);
 	return 0;
 }
diff --git a/src/thread/pthread_cond_timedwait.c b/src/thread/pthread_cond_timedwait.c
index 99d62cc..a51a46c 100644
--- a/src/thread/pthread_cond_timedwait.c
+++ b/src/thread/pthread_cond_timedwait.c
@@ -41,7 +41,7 @@ int pthread_cond_timedwait(pthread_cond_t *restrict c, pthread_mutex_t *restrict
 	struct cm cm = { .c=c, .m=m };
 	int r, e=0, seq;
 
-	if (m->_m_type && (m->_m_lock&INT_MAX) != __pthread_self()->tid)
+	if ((m->_m_type&15) && (m->_m_lock&INT_MAX) != __pthread_self()->tid)
 		return EPERM;
 
 	if (ts && ts->tv_nsec >= 1000000000UL)
diff --git a/src/thread/pthread_mutex_init.c b/src/thread/pthread_mutex_init.c
index 9d85a35..acf45a7 100644
--- a/src/thread/pthread_mutex_init.c
+++ b/src/thread/pthread_mutex_init.c
@@ -3,6 +3,6 @@
 int pthread_mutex_init(pthread_mutex_t *restrict m, const pthread_mutexattr_t *restrict a)
 {
 	*m = (pthread_mutex_t){0};
-	if (a) m->_m_type = a->__attr & 7;
+	if (a) m->_m_type = a->__attr;
 	return 0;
 }
diff --git a/src/thread/pthread_mutex_timedlock.c b/src/thread/pthread_mutex_timedlock.c
index 7b1afc0..849febb 100644
--- a/src/thread/pthread_mutex_timedlock.c
+++ b/src/thread/pthread_mutex_timedlock.c
@@ -2,11 +2,12 @@
 
 int pthread_mutex_timedlock(pthread_mutex_t *restrict m, const struct timespec *restrict at)
 {
-	int r, t;
-
-	if (m->_m_type == PTHREAD_MUTEX_NORMAL && !a_cas(&m->_m_lock, 0, EBUSY))
+	if ((m->_m_type&15) == PTHREAD_MUTEX_NORMAL
+	    && !a_cas(&m->_m_lock, 0, EBUSY))
 		return 0;
 
+	int r, t, priv = (m->_m_type & 128) ^ 128;
+
 	while ((r=pthread_mutex_trylock(m)) == EBUSY) {
 		if (!(r=m->_m_lock) || (r&0x40000000)) continue;
 		if ((m->_m_type&3) == PTHREAD_MUTEX_ERRORCHECK
@@ -16,7 +17,7 @@ int pthread_mutex_timedlock(pthread_mutex_t *restrict m, const struct timespec *
 		a_inc(&m->_m_waiters);
 		t = r | 0x80000000;
 		a_cas(&m->_m_lock, r, t);
-		r = __timedwait(&m->_m_lock, t, CLOCK_REALTIME, at, 0, 0, 0);
+		r = __timedwait(&m->_m_lock, t, CLOCK_REALTIME, at, 0, 0, priv);
 		a_dec(&m->_m_waiters);
 		if (r && r != EINTR) break;
 	}
diff --git a/src/thread/pthread_mutex_trylock.c b/src/thread/pthread_mutex_trylock.c
index 00ad65d..850fcb9 100644
--- a/src/thread/pthread_mutex_trylock.c
+++ b/src/thread/pthread_mutex_trylock.c
@@ -1,17 +1,13 @@
 #include "pthread_impl.h"
 
-int pthread_mutex_trylock(pthread_mutex_t *m)
+int __pthread_mutex_trylock_owner(pthread_mutex_t *m)
 {
-	int tid, old, own;
-	pthread_t self;
-
-	if (m->_m_type == PTHREAD_MUTEX_NORMAL)
-		return a_cas(&m->_m_lock, 0, EBUSY) & EBUSY;
+	int old, own;
+	int type = m->_m_type & 15;
+	pthread_t self = __pthread_self();
+	int tid = self->tid;
 
-	self = __pthread_self();
-	tid = self->tid;
-
-	if (m->_m_type >= 4) {
+	if (type >= 4) {
 		if (!self->robust_list.off)
 			__syscall(SYS_set_robust_list,
 				&self->robust_list, 3*sizeof(long));
@@ -21,7 +17,7 @@ int pthread_mutex_trylock(pthread_mutex_t *m)
 
 	old = m->_m_lock;
 	own = old & 0x7fffffff;
-	if (own == tid && (m->_m_type&3) == PTHREAD_MUTEX_RECURSIVE) {
+	if (own == tid && (type&3) == PTHREAD_MUTEX_RECURSIVE) {
 		if ((unsigned)m->_m_count >= INT_MAX) return EAGAIN;
 		m->_m_count++;
 		return 0;
@@ -30,9 +26,9 @@ int pthread_mutex_trylock(pthread_mutex_t *m)
 	if ((own && !(own & 0x40000000)) || a_cas(&m->_m_lock, old, tid)!=old)
 		return EBUSY;
 
-	if (m->_m_type < 4) return 0;
+	if (type < 4) return 0;
 
-	if (m->_m_type >= 8) {
+	if (type >= 8) {
 		m->_m_lock = 0;
 		return ENOTRECOVERABLE;
 	}
@@ -50,3 +46,10 @@ int pthread_mutex_trylock(pthread_mutex_t *m)
 
 	return 0;
 }
+
+int pthread_mutex_trylock(pthread_mutex_t *m)
+{
+	if ((m->_m_type&15) == PTHREAD_MUTEX_NORMAL)
+		return a_cas(&m->_m_lock, 0, EBUSY) & EBUSY;
+	return __pthread_mutex_trylock_owner(m);
+}
diff --git a/src/thread/pthread_mutex_unlock.c b/src/thread/pthread_mutex_unlock.c
index b4bd74b..769d6e5 100644
--- a/src/thread/pthread_mutex_unlock.c
+++ b/src/thread/pthread_mutex_unlock.c
@@ -9,16 +9,18 @@ int pthread_mutex_unlock(pthread_mutex_t *m)
 	int waiters = m->_m_waiters;
 	int cont;
 	int robust = 0;
+	int type = m->_m_type & 15;
+	int priv = (m->_m_type & 128) ^ 128;
 
-	if (m->_m_type != PTHREAD_MUTEX_NORMAL) {
+	if (type != PTHREAD_MUTEX_NORMAL) {
 		if (!m->_m_lock)
 			return EPERM;
 		self = __pthread_self();
 		if ((m->_m_lock&0x1fffffff) != self->tid)
 			return EPERM;
-		if ((m->_m_type&3) == PTHREAD_MUTEX_RECURSIVE && m->_m_count)
+		if ((type&3) == PTHREAD_MUTEX_RECURSIVE && m->_m_count)
 			return m->_m_count--, 0;
-		if (m->_m_type >= 4) {
+		if (type >= 4) {
 			robust = 1;
 			self->robust_list.pending = &m->_m_next;
 			*(void **)m->_m_prev = m->_m_next;
@@ -32,6 +34,6 @@ int pthread_mutex_unlock(pthread_mutex_t *m)
 		__vm_unlock_impl();
 	}
 	if (waiters || cont<0)
-		__wake(&m->_m_lock, 1, 0);
+		__wake(&m->_m_lock, 1, priv);
 	return 0;
 }
diff --git a/src/thread/pthread_mutexattr_setpshared.c b/src/thread/pthread_mutexattr_setpshared.c
index 8c7a1e2..100f6ff 100644
--- a/src/thread/pthread_mutexattr_setpshared.c
+++ b/src/thread/pthread_mutexattr_setpshared.c
@@ -3,7 +3,7 @@
 int pthread_mutexattr_setpshared(pthread_mutexattr_t *a, int pshared)
 {
 	if (pshared > 1U) return EINVAL;
-	a->__attr &= 0x7fffffff;
-	a->__attr |= pshared<<31;
+	a->__attr &= ~128U;
+	a->__attr |= pshared<<7;
 	return 0;
 }
diff --git a/src/thread/pthread_once.c b/src/thread/pthread_once.c
index e01f6d4..2eb0f93 100644
--- a/src/thread/pthread_once.c
+++ b/src/thread/pthread_once.c
@@ -3,7 +3,7 @@
 static void undo(void *control)
 {
 	a_store(control, 0);
-	__wake(control, 1, 0);
+	__wake(control, 1, 1);
 }
 
 int pthread_once(pthread_once_t *control, void (*init)(void))
@@ -25,10 +25,10 @@ int pthread_once(pthread_once_t *control, void (*init)(void))
 		pthread_cleanup_pop(0);
 
 		a_store(control, 2);
-		if (waiters) __wake(control, -1, 0);
+		if (waiters) __wake(control, -1, 1);
 		return 0;
 	case 1:
-		__wait(control, &waiters, 1, 0);
+		__wait(control, &waiters, 1, 1);
 		continue;
 	case 2:
 		return 0;
diff --git a/src/thread/pthread_rwlock_init.c b/src/thread/pthread_rwlock_init.c
index 82df52e..a2c0b47 100644
--- a/src/thread/pthread_rwlock_init.c
+++ b/src/thread/pthread_rwlock_init.c
@@ -3,7 +3,6 @@
 int pthread_rwlock_init(pthread_rwlock_t *restrict rw, const pthread_rwlockattr_t *restrict a)
 {
 	*rw = (pthread_rwlock_t){0};
-	if (a) {
-	}
+	if (a) rw->_rw_shared = a->__attr[0]*128;
 	return 0;
 }
diff --git a/src/thread/pthread_rwlock_timedrdlock.c b/src/thread/pthread_rwlock_timedrdlock.c
index c0c94c9..a2b4d44 100644
--- a/src/thread/pthread_rwlock_timedrdlock.c
+++ b/src/thread/pthread_rwlock_timedrdlock.c
@@ -8,7 +8,7 @@ int pthread_rwlock_timedrdlock(pthread_rwlock_t *restrict rw, const struct times
 		t = r | 0x80000000;
 		a_inc(&rw->_rw_waiters);
 		a_cas(&rw->_rw_lock, r, t);
-		r = __timedwait(&rw->_rw_lock, t, CLOCK_REALTIME, at, 0, 0, 0);
+		r = __timedwait(&rw->_rw_lock, t, CLOCK_REALTIME, at, 0, 0, rw->_rw_shared^128);
 		a_dec(&rw->_rw_waiters);
 		if (r && r != EINTR) return r;
 	}
diff --git a/src/thread/pthread_rwlock_timedwrlock.c b/src/thread/pthread_rwlock_timedwrlock.c
index 339a167..63a32ec 100644
--- a/src/thread/pthread_rwlock_timedwrlock.c
+++ b/src/thread/pthread_rwlock_timedwrlock.c
@@ -8,7 +8,7 @@ int pthread_rwlock_timedwrlock(pthread_rwlock_t *restrict rw, const struct times
 		t = r | 0x80000000;
 		a_inc(&rw->_rw_waiters);
 		a_cas(&rw->_rw_lock, r, t);
-		r = __timedwait(&rw->_rw_lock, t, CLOCK_REALTIME, at, 0, 0, 0);
+		r = __timedwait(&rw->_rw_lock, t, CLOCK_REALTIME, at, 0, 0, rw->_rw_shared^128);
 		a_dec(&rw->_rw_waiters);
 		if (r && r != EINTR) return r;
 	}
diff --git a/src/thread/pthread_rwlock_unlock.c b/src/thread/pthread_rwlock_unlock.c
index a6d2085..7b5eec8 100644
--- a/src/thread/pthread_rwlock_unlock.c
+++ b/src/thread/pthread_rwlock_unlock.c
@@ -2,7 +2,7 @@
 
 int pthread_rwlock_unlock(pthread_rwlock_t *rw)
 {
-	int val, cnt, waiters, new;
+	int val, cnt, waiters, new, priv = rw->_rw_shared^128;
 
 	do {
 		val = rw->_rw_lock;
@@ -12,7 +12,7 @@ int pthread_rwlock_unlock(pthread_rwlock_t *rw)
 	} while (a_cas(&rw->_rw_lock, val, new) != val);
 
 	if (!new && (waiters || val<0))
-		__wake(&rw->_rw_lock, cnt, 0);
+		__wake(&rw->_rw_lock, cnt, priv);
 
 	return 0;
 }
diff --git a/src/thread/sem_init.c b/src/thread/sem_init.c
index e8e419c..5509243 100644
--- a/src/thread/sem_init.c
+++ b/src/thread/sem_init.c
@@ -10,5 +10,6 @@ int sem_init(sem_t *sem, int pshared, unsigned value)
 	}
 	sem->__val[0] = value;
 	sem->__val[1] = 0;
+	sem->__val[2] = pshared ? 0 : 128;
 	return 0;
 }
diff --git a/src/thread/sem_post.c b/src/thread/sem_post.c
index 14a2dfe..31e3293 100644
--- a/src/thread/sem_post.c
+++ b/src/thread/sem_post.c
@@ -3,7 +3,7 @@
 
 int sem_post(sem_t *sem)
 {
-	int val, waiters;
+	int val, waiters, priv = sem->__val[2];
 	do {
 		val = sem->__val[0];
 		waiters = sem->__val[1];
@@ -12,6 +12,6 @@ int sem_post(sem_t *sem)
 			return -1;
 		}
 	} while (a_cas(sem->__val, val, val+1+(val<0)) != val);
-	if (val<0 || waiters) __wake(sem->__val, 1, 0);
+	if (val<0 || waiters) __wake(sem->__val, 1, priv);
 	return 0;
 }
diff --git a/src/thread/sem_timedwait.c b/src/thread/sem_timedwait.c
index 6d0d011..bfcb6dc 100644
--- a/src/thread/sem_timedwait.c
+++ b/src/thread/sem_timedwait.c
@@ -12,7 +12,7 @@ int sem_timedwait(sem_t *restrict sem, const struct timespec *restrict at)
 		int r;
 		a_inc(sem->__val+1);
 		a_cas(sem->__val, 0, -1);
-		r = __timedwait(sem->__val, -1, CLOCK_REALTIME, at, cleanup, sem->__val+1, 0);
+		r = __timedwait(sem->__val, -1, CLOCK_REALTIME, at, cleanup, sem->__val+1, sem->__val[2]);
 		a_dec(sem->__val+1);
 		if (r) {
 			errno = r;

Re: [PATCH] private futex support

[Timo Teras]

On Thu, 26 Jun 2014 14:48:03 -0400
Rich Felker <dalias@libc.org> wrote:

> Here is a semi-proposed patch for private futex support, one of the
> items on the roadmap for the next release cycle. However I've been
> unable to demonstrate it yielding better performance than non-private
> futex, and since it adds (small, but nonzero) complexity and worse
> behavior on outdated (pre-2.6.22) kernels, I'm a bit hesitant to

Seems the patch is not fully complete. At least pthread_cond_t is not
fully using private-futexes yet.

Before testing, I did add the private flag in:

1) pthread_cond_broadcast.c for the FUTEX_REQUEUE call (can likely be
unconditionally added, as pshared conditions have separate code path)

2) pthread_cond_timedwait.c for the __timedwait call (though this
probably needs to be based on the pshared attribute)

My changes being:

diff --git a/src/thread/pthread_cond_broadcast.c b/src/thread/pthread_cond_broadcast.c
index 0901daf..4327a0e 100644
--- a/src/thread/pthread_cond_broadcast.c
+++ b/src/thread/pthread_cond_broadcast.c
@@ -27,7 +27,7 @@ int pthread_cond_broadcast(pthread_cond_t *c)
 
 	/* Perform the futex requeue, waking one waiter unless we know
 	 * that the calling thread holds the mutex. */
-	__syscall(SYS_futex, &c->_c_seq, FUTEX_REQUEUE,
+	__syscall(SYS_futex, &c->_c_seq, 128 | FUTEX_REQUEUE,
 		!m->_m_type || (m->_m_lock&INT_MAX)!=__pthread_self()->tid,
 		INT_MAX, &m->_m_lock);
 
diff --git a/src/thread/pthread_cond_timedwait.c b/src/thread/pthread_cond_timedwait.c
index 99d62cc..73c1781 100644
--- a/src/thread/pthread_cond_timedwait.c
+++ b/src/thread/pthread_cond_timedwait.c
@@ -64,7 +64,7 @@ int pthread_cond_timedwait(pthread_cond_t *restrict c, pthread_mutex_t *restrict
 
 	pthread_mutex_unlock(m);
 
-	do e = __timedwait(&c->_c_seq, seq, c->_c_clock, ts, cleanup, &cm, 0);
+	do e = __timedwait(&c->_c_seq, seq, c->_c_clock, ts, cleanup, &cm, 1);
 	while (c->_c_seq == seq && (!e || e==EINTR));
 	if (e == EINTR) e = 0;
 
It seems that things worked even without these changes, but everything
was a lot slower. Not sure why. But the code sounds buggy anyway,
because FUTEX_REQUEUE was transferring waiters to &m->_m_lock which was
already treated as private address in other futex calls causing a
mismatch.

> actually commit it. If anyone is interested in this feature, please
> see if you can find some examples that demonstrate that it measurably
> improves performance.

And running my simple test-case of having two threads wake up each
other using a condition variable, seems to yield noticeable performance
speed up from private futexes. See at the end of mail for the code.

The low and high numbers from few test runs are as follows from musl 
git 4fe57cad709fdfb377060 without and with the futex patch are as
follows:

~/privfutex $ time ~/oss/musl/lib/libc.so  ./test
count=2516417
real	0m 2.00s
user	0m 1.68s
sys	0m 2.30s

~/privfutex $ time ~/oss/musl/lib/libc.so  ./test
count=2679381
real	0m 2.00s
user	0m 1.59s
sys	0m 2.39s

Private futexes:

~/privfutex $ time ~/oss/musl/lib/libc.so  ./test
count=3839470
real	0m 2.00s
user	0m 1.68s
sys	0m 1.98s

~/privfutex $ time ~/oss/musl/lib/libc.so  ./test
count=5350852
real	0m 2.00s
user	0m 1.66s
sys	0m 2.32s


You can see essentially lowered sys time use, and up to doubled
throughput of wait/wake operations.

So I suspect your test case was not measuring right thing. Private
futexes speed up only specific loads, and this type of pthread_cond_t
usage would probably be the pattern benefiting most.

Please reconsidering adding this after addressing the found
deficiencies stated in the beginning.

Thanks,
Timo

And the test case code:

#include <stdio.h>
#include <unistd.h>
#include <pthread.h>

static pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
static volatile long run = 1, count = 0;

static void *func(void *arg)
{
	long my_id = (long) arg;

	do {
		pthread_mutex_lock(&mtx);
		while (run == my_id)
			pthread_cond_wait(&cond, &mtx);
		count++;
		if (run) run = (my_id == 1) ? 2 : 1;
		pthread_cond_broadcast(&cond);
		pthread_mutex_unlock(&mtx);
	} while (run);

	return NULL;
}

int main(void)
{
	void *ret;
	pthread_t t1, t2;

	pthread_create(&t1, NULL, func, (void*) 1);
	pthread_create(&t2, NULL, func, (void*) 2);

	sleep(2);

	pthread_mutex_lock(&mtx);
	run = 0;
	pthread_cond_broadcast(&cond);
	pthread_mutex_unlock(&mtx);

	pthread_join(t1, &ret);
	pthread_join(t2, &ret);

	printf("count=%ld\n", count);

	return 0;
}

Re: [PATCH] private futex support

[Rich Felker]

Just a quick explanation for some unexpected behavior you saw:

On Fri, Aug 08, 2014 at 11:38:57AM +0300, Timo Teras wrote:
> diff --git a/src/thread/pthread_cond_broadcast.c b/src/thread/pthread_cond_broadcast.c
> index 0901daf..4327a0e 100644
> --- a/src/thread/pthread_cond_broadcast.c
> +++ b/src/thread/pthread_cond_broadcast.c
> @@ -27,7 +27,7 @@ int pthread_cond_broadcast(pthread_cond_t *c)
>  
>  	/* Perform the futex requeue, waking one waiter unless we know
>  	 * that the calling thread holds the mutex. */
> -	__syscall(SYS_futex, &c->_c_seq, FUTEX_REQUEUE,
> +	__syscall(SYS_futex, &c->_c_seq, 128 | FUTEX_REQUEUE,
>  		!m->_m_type || (m->_m_lock&INT_MAX)!=__pthread_self()->tid,
>  		INT_MAX, &m->_m_lock);
>  
> diff --git a/src/thread/pthread_cond_timedwait.c b/src/thread/pthread_cond_timedwait.c
> index 99d62cc..73c1781 100644
> --- a/src/thread/pthread_cond_timedwait.c
> +++ b/src/thread/pthread_cond_timedwait.c
> @@ -64,7 +64,7 @@ int pthread_cond_timedwait(pthread_cond_t *restrict c, pthread_mutex_t *restrict
>  
>  	pthread_mutex_unlock(m);
>  
> -	do e = __timedwait(&c->_c_seq, seq, c->_c_clock, ts, cleanup, &cm, 0);
> +	do e = __timedwait(&c->_c_seq, seq, c->_c_clock, ts, cleanup, &cm, 1);
>  	while (c->_c_seq == seq && (!e || e==EINTR));
>  	if (e == EINTR) e = 0;
>  
> It seems that things worked even without these changes, but everything
> was a lot slower. Not sure why. But the code sounds buggy anyway,

Both the wait and wake (requeue) operations for this futex were
wrongly shared rather than private, so since they still matched it
makes sense that it didn't fail. The requeue was wrongly requeuing as
shared on a mutex that would only receive a wake as private, but since
there was only one waiter and the requeue requested one wake, I guess
no requeue ever happened.

Rich

Re: [PATCH] private futex support

[Rich Felker]

[-- Attachment #1: Type: text/plain, Size: 2347 bytes --]

On Fri, Aug 08, 2014 at 11:38:57AM +0300, Timo Teras wrote:
> > actually commit it. If anyone is interested in this feature, please
> > see if you can find some examples that demonstrate that it measurably
> > improves performance.
> 
> And running my simple test-case of having two threads wake up each
> other using a condition variable, seems to yield noticeable performance
> speed up from private futexes. See at the end of mail for the code.
> 
> The low and high numbers from few test runs are as follows from musl 
> git 4fe57cad709fdfb377060 without and with the futex patch are as
> follows:
> 
> ~/privfutex $ time ~/oss/musl/lib/libc.so  ./test
> count=2516417
> real	0m 2.00s
> user	0m 1.68s
> sys	0m 2.30s
> 
> ~/privfutex $ time ~/oss/musl/lib/libc.so  ./test
> count=2679381
> real	0m 2.00s
> user	0m 1.59s
> sys	0m 2.39s
> 
> Private futexes:
> 
> ~/privfutex $ time ~/oss/musl/lib/libc.so  ./test
> count=3839470
> real	0m 2.00s
> user	0m 1.68s
> sys	0m 1.98s
> 
> ~/privfutex $ time ~/oss/musl/lib/libc.so  ./test
> count=5350852
> real	0m 2.00s
> user	0m 1.66s
> sys	0m 2.32s
> 
> 
> You can see essentially lowered sys time use, and up to doubled
> throughput of wait/wake operations.

I was able to match the relative difference (albeit at about 10% of
the total throughput you got for both versions) on my atom.

I also dug up an old test of mine that shows some difference (1.9s vs
2.2s to run). The original point of this test was to demonstrate that
glibc's non-process-shared condvars are 2-2.5x slower than their
process-shared ones (yes, the opposite of what you would expect; see
bug 13234). The code is attached.

> So I suspect your test case was not measuring right thing. Private
> futexes speed up only specific loads, and this type of pthread_cond_t
> usage would probably be the pattern benefiting most.
> 
> Please reconsidering adding this after addressing the found
> deficiencies stated in the beginning.

Yes, I think you've succeeded in establishing that private futex
support is useful. So now I just need to check for more stupid
mistakes, get it into a form that's ready to commit, and do some
testing between now and the next release. We should do at least one
test with private futexes hard-wired to fail (or just find an old
kernel to test on) to make sure the fallback code is working, too.

Rich

[-- Attachment #2: cvb2.c --]
[-- Type: text/plain, Size: 1142 bytes --]

#include <stdio.h>
#include <pthread.h>

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t c = PTHREAD_COND_INITIALIZER;
volatile int p;

int left[5], avail[5], wakes;

void *tf(void *arg)
{
	int i = (long)arg;
	pthread_mutex_lock(&m);
	while (left[i]) {
		while (!avail[i]) pthread_cond_wait(&c, &m), wakes++;
		left[i]--; avail[i]--;
	}
	pthread_mutex_unlock(&m);
}

int main()
{
	pthread_t td[5];
	int i, total;
	pthread_mutexattr_t ma;
	pthread_mutexattr_init(&ma);
	pthread_mutexattr_settype(&ma, PTHREAD_MUTEX_ERRORCHECK);
	pthread_condattr_t ca;
	pthread_condattr_init(&ca);
	pthread_condattr_setpshared(&ca, PTHREAD_PROCESS_SHARED);
	//pthread_cond_init(&c, &ca);
	//pthread_mutex_init(&m, &ma);
	for (i=0; i<5; i++) left[i] = 100000;
	for (i=0; i<5; i++) pthread_create(td+i, 0, tf, (void*)(long)i);
	pthread_mutex_lock(&m);
	for (;;) {
		for (total=i=0; i<5; i++) total+=left[i];
		if (!total) break;
		for (i=0; i<5; i++) avail[i]=1;
		pthread_cond_broadcast(&c);
		pthread_mutex_unlock(&m);
		pthread_mutex_lock(&m);
	}
	pthread_mutex_unlock(&m);
	for (i=0; i<5; i++) pthread_join(td[i], 0);
	printf("%d\n", wakes);
}