>Number:         26208
>Category:       lib
>Synopsis:       pthread_mutex possible deadlock
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    lib-bug-people
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Thu Jul 08 19:08:00 UTC 2004
>Closed-Date:
>Last-Modified:
>Originator:     Arne H Juul
>Release:        NetBSD 2.0G
>Organization:
 	disorganized
>Environment:

System: NetBSD usikkert.trondheim.corp.yahoo.com 2.0G NetBSD 2.0G (USIKKERT.MP) #0: Sun Jul 4 16:05:06 UTC 2004 arnej@usikkert.trondheim.corp.yahoo.com:/usr/obj/sys/arch/i386/compile/USIKKERT.MP i386

 	src/lib/libpthread/pthread_mutex.c version 1.18.

Architecture: i386
Machine: i386
>Description:

 	Trying out a threaded application on a SMP system with
 	PTHREAD_CONCURRENCY=9 to see how well actual multi-threading
 	works now, I soon got a deadlock in my test application.
 	Using gdb and attach() didn't work but "gcore" gave a
 	core file that worked well with gdb thread debugging.

 	I found that one thread was stuck waiting for a mutex:

#0  0x4820e007 in pthread__locked_switch () from /usr/lib/libpthread.so.0
#1  0x48211d1d in pthread__block (self=0x4b000000, queuelock=0x4835c774)
     at /usr/src/lib/libpthread/pthread_run.c:107
#2  0x482128ea in pthread_mutex_lock_slow (mutex=0x4835c76c)
     at /usr/src/lib/libpthread/pthread_mutex.c:260
#3  0x482127ab in pthread_mutex_lock (mutex=0x4835c76c)
     at /usr/src/lib/libpthread/pthread_mutex.c:169
#4  0x4834ba27 in malloc (size=1024) at /usr/src/lib/libc/stdlib/malloc.c:1118
#5  0x4827279e in operator new(unsigned) () from /usr/lib/libstdc++.so.5
 	etc.

 	however, the mutex in question (the malloc/free mutex) wasn't
 	actually locked:

(gdb) print mutex[0]
$3 = {ptm_magic = 858980355, ptm_lock = 0, ptm_interlock = 0, ptm_owner = 0x0,
   ptm_blocked = {ptqh_first = 0x4b000000, ptqh_last = 0x4b000048},
   ptm_private = 0x482171b0}

 	So it seems one thread has blocked on this mutex at
 	the same time as another thread released it, causing
 	a deadlock. Some code snips from pthread_mutex_lock_slow:

 	if (pthread__simple_lock_try(&mutex->ptm_lock))
 		break; /* got it! */
 	/* Okay, didn't look free. Get the interlock... */
 	pthread_spinlock(self, &mutex->ptm_interlock);
         /*
          * The mutex_unlock routine will get the interlock
          * before looking at the list of sleepers, so if the
          * lock is held we can safely put ourselves on the
          * sleep queue. If it's not held, we can try taking it
          * again.
          */
 	PTQ_INSERT_HEAD(&mutex->ptm_blocked, self, pt_sleep);
 	if (mutex->ptm_lock == __SIMPLELOCK_LOCKED) {
 		...
 		pthread__block(self, &mutex->ptm_interlock);

 	It looks like there isn't any barrier between
 	adding us to the ptm_blocked list and checking the
 	ptm_lock value; the comment describes what pthread_mutex_unlock
 	*should* do, but unfortunately that isn't actually the case:

 	pthread__simple_unlock(&mutex->ptm_lock);
 	if (!PTQ_EMPTY(&mutex->ptm_blocked)) {
 		self = pthread__self();
 		pthread_spinlock(self, &mutex->ptm_interlock);
 		...

 	here the interlock is taken *after* looking at the
 	"list of sleepers" (which I assume refers to ptm_blocked).
 	So I guess it is possible for thread A to:
 		see the mutex is locked
 		take the interlock
 		insert A on ptm_blocked
 		see that ptm_lock == __SIMPLELOCK_LOCKED
 	while thread B does:
 		release the lock
 		see that mutex->ptm_blocked is empty.
 	all at the same time (on the two different CPUs).

>How-To-Repeat:
 	I don't have any simple test program for this, sorry.
 	I would imagine most multithreaded programs that
 	use malloc/free could trigger this problem if
 	run on SMP machine with PTHREAD_CONCURRENCY though.

>Fix:
 	I have two suggestions for fix.  The first one is to implement
 	what the comment says and take the interlock before
 	looking at the ptm_blocked queue.  This introduces
 	spinlock/spinunlock overhead in pthread_mutex_unlock()
 	even when there is no contention on the mutex.

 	The other variant is to change the check for whether
 	the lock is still held to actually try to grab it again.
 	This gives more overhead when there's contention on
 	the mutex (we go from 2 to 3 uses of pthread__simple_lock_try
 	before blocking), but it's easy to reduce this again down to 2
 	if needed.
 	So this variant is probably better :-)

 	I also think it *might* be a good idea to change the ptm_blocked
 	queue to FIFO order (with PTQ_INSERT_TAIL and PTQ_FIRST), but
 	I'm not sure if it matters for real-world programs.

Index: lib/libpthread/pthread_mutex.c
===================================================================
RCS file: /usr/cvs/src/lib/libpthread/pthread_mutex.c,v
retrieving revision 1.18
diff -u -r1.18 pthread_mutex.c
--- lib/libpthread/pthread_mutex.c	14 Mar 2004 01:19:42 -0000	1.18
+++ lib/libpthread/pthread_mutex.c	8 Jul 2004 18:16:55 -0000
@@ -320,12 +320,13 @@

  	GET_MUTEX_PRIVATE(mutex, mp);

+	self = pthread__self();
  	/*
  	 * These tests can be performed without holding the
  	 * interlock because these fields are only modified
  	 * if we know we own the mutex.
  	 */
-	weown = (pthread__id(mutex->ptm_owner) == pthread__self());
+	weown = (pthread__id(mutex->ptm_owner) == self);
  	switch (mp->type) {
  	case PTHREAD_MUTEX_RECURSIVE:
  		if (!weown)
@@ -361,9 +362,8 @@
  	 * examination of the queue; if so, no harm is done, as the
  	 * waiter will loop and see that the mutex is still locked.
  	 */
+	pthread_spinlock(self, &mutex->ptm_interlock);
  	if (!PTQ_EMPTY(&mutex->ptm_blocked)) {
-		self = pthread__self();
-		pthread_spinlock(self, &mutex->ptm_interlock);
  		blocked = PTQ_FIRST(&mutex->ptm_blocked);
  		if (blocked) {
  			PTQ_REMOVE(&mutex->ptm_blocked, blocked, pt_sleep);
@@ -371,8 +371,8 @@
  			/* Give the head of the blocked queue another try. */
  			pthread__sched(self, blocked);
  		}
-		pthread_spinunlock(self, &mutex->ptm_interlock);
  	}
+	pthread_spinunlock(self, &mutex->ptm_interlock);
  	return 0;
  }

Index: lib/libpthread/pthread_mutex.c
===================================================================
RCS file: /usr/cvs/src/lib/libpthread/pthread_mutex.c,v
retrieving revision 1.18
diff -u -r1.18 pthread_mutex.c
--- lib/libpthread/pthread_mutex.c	14 Mar 2004 01:19:42 -0000	1.18
+++ lib/libpthread/pthread_mutex.c	8 Jul 2004 14:15:49 -0000
@@ -203,14 +203,16 @@
  		/* Okay, didn't look free. Get the interlock... */
  		pthread_spinlock(self, &mutex->ptm_interlock);
  		/*
-		 * The mutex_unlock routine will get the interlock
-		 * before looking at the list of sleepers, so if the
-		 * lock is held we can safely put ourselves on the
-		 * sleep queue. If it's not held, we can try taking it
-		 * again.
+		 * Put ourselves on the sleep queue.
+		 * Check if somebody released the lock in the meantime.
  		 */
-		PTQ_INSERT_HEAD(&mutex->ptm_blocked, self, pt_sleep);
-		if (mutex->ptm_lock == __SIMPLELOCK_LOCKED) {
+		PTQ_INSERT_TAIL(&mutex->ptm_blocked, self, pt_sleep);
+		if (pthread__simple_lock_try(&mutex->ptm_lock)) {
+			/* got it! undo sleep queue and interlock */
+			PTQ_REMOVE(&mutex->ptm_blocked, self, pt_sleep);
+			pthread_spinunlock(self, &mutex->ptm_interlock);
+			break;
+		} else {
  			struct mutex_private *mp;

  			GET_MUTEX_PRIVATE(mutex, mp);
@@ -259,9 +261,6 @@

  			pthread__block(self, &mutex->ptm_interlock);
  			/* interlock is not held when we return */
-		} else {
-			PTQ_REMOVE(&mutex->ptm_blocked, self, pt_sleep);
-			pthread_spinunlock(self, &mutex->ptm_interlock);
  		}
  		/* Go around for another try. */
  	}
>Release-Note:
>Audit-Trail:
>Unformatted:
  	cvsup'ed Jul 7, 2004