Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <1409133335.4476.30.camel@eris.loria.fr>
Date: Wed, 27 Aug 2014 11:57:47 +0200
From: Jens Gustedt <Jens.Gustedt@...ia.fr>
To: musl@...ts.openwall.com
Subject: [PATCH 2/2] avoid taking _c_lock if we know it isn't necessary

This avoids calls to __wait for both, the signaler and the waiter, by
eventually adding a __wake to the waiter. Since __wait may unschedule the
calling thread and a private __wake is just a not too expensive syscall,
this is considered being an advantage.

The additional __wake call could be avoided by tracing the fact that the
signaler is inside the "ref" count, making it a win-win.
---
 src/thread/pthread_cond_timedwait.c |   33 +++++++++++++++++++++++++++------
 1 file changed, 27 insertions(+), 6 deletions(-)

diff --git a/src/thread/pthread_cond_timedwait.c b/src/thread/pthread_cond_timedwait.c
index 52b1026..9790c84 100644
--- a/src/thread/pthread_cond_timedwait.c
+++ b/src/thread/pthread_cond_timedwait.c
@@ -25,7 +25,7 @@
 struct waiter {
 	struct waiter *prev, *next;
 	int state, barrier, mutex_ret;
-	int *notify;
+	int *volatile notify;
 	pthread_mutex_t *mutex;
 	pthread_cond_t *cond;
 	int shared;
@@ -42,6 +42,19 @@ static inline void lock(volatile int *l)
 	}
 }
 
+/* Avoid taking the lock if we know it isn't necessary. */
+static inline int lockRace(volatile int *l, int*volatile* notifier)
+{
+	int ret = 1;
+	if (!*notifier && (ret = a_cas(l, 0, 1))) {
+		a_cas(l, 1, 2);
+		do __wait(l, 0, 2, 1);
+		while (!*notifier && (ret = a_cas(l, 0, 2)));
+	}
+	return ret;
+}
+
+
 static inline void unlock(volatile int *l)
 {
 	if (a_swap(l, 0)==2)
@@ -86,21 +99,29 @@ static void unwait(void *arg)
 		pthread_cond_t *c = node->cond;
 		int * ref;
 
-		lock(&c->_c_lock);
+		int locked = lockRace(&c->_c_lock, &node->notify);
 		/* Our membership to the list may have changed while waiting for the lock. */
-		/* Ensure that the notify field is only read while we hold the lock. */
+		/* This field is written with an atomic op, so we don't need the lock to be taken. */
+		/* But it might also have changed while we were waiting, so reload it, again. */
 		ref = node->notify;
 
 		/* If there has been no race with a signaler, splice us out of the list. */
 		/* Otherwise, the signaler has already taken care of it. */
 		if (!ref) {
+			/* In this case locked is always 0 and the lock is acquired. */
 			if (c->_c_head == node) c->_c_head = node->next;
 			else if (node->prev) node->prev->next = node->next;
 			if (c->_c_tail == node) c->_c_tail = node->prev;
 			else if (node->next) node->next->prev = node->prev;
 		}
-		unlock(&c->_c_lock);
+		if (!locked) unlock(&c->_c_lock);
+
 
+		/* Since this leaving waiter might not have held the _c_lock, the following       */
+		/* __wake might be issued when the signaler is still inside its CS.               */
+		/* But if so, this avoids a __wait of the signaler, which more important.         */
+		/* This should not target any spurious wake up in any other thread:               */
+		/* ref is on the stack of the signaler, and that signaler is still alive.         */
 		if (ref) {
 			if (a_fetch_add(ref, -1)==1)
 				__wake(ref, 1, 1);
@@ -178,8 +199,8 @@ int __private_cond_signal(pthread_cond_t *c, int n)
 	lock(&c->_c_lock);
 	for (p=c->_c_tail; n && p; p=p->prev) {
 		if (a_cas(&p->state, WAITING, SIGNALED) != WAITING) {
-			ref++;
-			p->notify = &ref;
+			a_fetch_add(&ref, 1);
+			a_cas_p(&p->notify, 0, &ref);
 			/* Let the signaler do all work concerning consistency of the list. */
 			if (c->_c_head == p) c->_c_head = p->next;
 			else if (p->prev) p->prev->next = p->next;
-- 
1.7.10.4

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.