diff mbox

libatomic: Acquire locks in increasing order to avoid deadlocks

Message ID 1410697315-19214-1-git-send-email-cederman@gaisler.com
State New
Headers show

Commit Message

Daniel Cederman Sept. 14, 2014, 12:21 p.m. UTC 
libat_lock_n acquires a set of locks from an array of locks. As done now,
locks might be acquired first from the end of the array and then from the
start of the array. Consider the scenario of two threads each trying to
acquire all locks. Thread 1 starts by taking lock 1 and thread 2 starts by
taking lock 0. Since both threads need a lock taken by the other we have
a deadlock. This patch changes the order in which locks are taken so that
it is always increasing. This way at least one thread will always make
progress.

As the cache line size is normally a power of two the div and mod operation
will be compiled to bit operations.

2014-09-14  Daniel Cederman  <cederman@gaisler.com>

	* libatomic/config/posix/lock.c (libat_lock_n): Acquire
	locks in increasing order to avoid deadlocks
---
 libatomic/config/posix/lock.c | 19 +++++++++++++------
 1 file changed, 13 insertions(+), 6 deletions(-)
diff mbox

Patch

diff --git a/libatomic/config/posix/lock.c b/libatomic/config/posix/lock.c
index a214c45..a13830f 100644
--- a/libatomic/config/posix/lock.c
+++ b/libatomic/config/posix/lock.c
@@ -81,19 +81,26 @@  libat_lock_n (void *ptr, size_t n)
 {
   uintptr_t h = addr_hash (ptr);
   size_t i = 0;
+  size_t l;
 
   /* Don't lock more than all the locks we have.  */
   if (n > PAGE_SIZE)
     n = PAGE_SIZE;
 
-  do
+  l = n / CACHLINE_SIZE + h;
+
+  if (n % CACHLINE_SIZE)
+    l++;
+
+  if (l >= NLOCKS)
     {
-      pthread_mutex_lock (&locks[h].mutex);
-      if (++h == NLOCKS)
-	h = 0;
-      i += WATCH_SIZE;
+      for (i=0; i < l - NLOCKS; i++)
+        pthread_mutex_lock (&locks[i].mutex);
+      l = NLOCKS;
     }
-  while (i < n);
+
+  for (i=h; i < l; i++)
+    pthread_mutex_lock (&locks[i].mutex);
 }
 
 void