[glib] Implement pointer sized bitlocks

[Matthias Clasen <matthiasc src gnome org>]

commit df0b208831a797f402d9f86263e6fa5378da47cc
Author: Ryan Lortie <desrt desrt ca>
Date:   Wed May 25 11:08:20 2011 +0200

    Implement pointer sized bitlocks
    
    Based on a patch from Alexander Larsson.
    
    https://bugzilla.gnome.org/show_bug.cgi?id=651467

 glib/gbitlock.c            |  193 ++++++++++++++++++++++++++++++++++++++++++++
 glib/gbitlock.h            |   29 +++++++
 glib/glib.symbols          |    3 +
 gthread/tests/1bit-mutex.c |   50 +++++++++---
 4 files changed, 265 insertions(+), 10 deletions(-)
---
diff --git a/glib/gbitlock.c b/glib/gbitlock.c
index 75e045c..72ee96c 100644
--- a/glib/gbitlock.c
+++ b/glib/gbitlock.c
@@ -22,6 +22,7 @@
 
 #include "gbitlock.h"
 
+#include <glib/gmessages.h>
 #include <glib/gatomic.h>
 #include <glib/gslist.h>
 #include <glib/gthread.h>
@@ -334,3 +335,195 @@ g_bit_unlock (volatile gint *address,
       g_futex_wake (address);
   }
 }
+
+
+/* We emulate pointer-sized futex(2) because the kernel API only
+ * supports integers.
+ *
+ * We assume that the 'interesting' part is always the lower order bits.
+ * This assumption holds because pointer bitlocks are restricted to
+ * using the low order bits of the pointer as the lock.
+ *
+ * On 32 bits, there is nothing to do since the pointer size is equal to
+ * the integer size.  On little endian the lower-order bits don't move,
+ * so do nothing.  Only on 64bit big endian do we need to do a bit of
+ * pointer arithmetic: the low order bits are shifted by 4 bytes.  We
+ * have a helper function that always does the right thing here.
+ *
+ * Since we always consider the low-order bits of the integer value, a
+ * simple cast from (gsize) to (guint) always takes care of that.
+ *
+ * After that, pointer-sized futex becomes as simple as:
+ *
+ *   g_futex_wait (g_futex_int_address (address), (guint) value);
+ *
+ * and
+ *
+ *   g_futex_wake (g_futex_int_address (int_address));
+ */
+static const volatile gint *
+g_futex_int_address (const volatile void *address)
+{
+  const volatile gint *int_address = address;
+
+#if G_BYTE_ORDER == G_BIG_ENDIAN && GLIB_SIZEOF_VOID_P == 8
+  int_address++;
+#endif
+
+  return int_address;
+}
+
+/**
+ * g_pointer_bit_lock:
+ * @address: a pointer to a #gpointer-sized value
+ * @lock_bit: a bit value between 0 and 31
+ *
+ * This is equivalent to g_bit_lock, but working on pointers (or other
+ * pointer-sized values).
+ *
+ * For portability reasons, you may only lock on the bottom 32 bits of
+ * the pointer.
+ *
+ * Since: 2.30
+ **/
+void
+(g_pointer_bit_lock) (volatile void *address,
+                      gint           lock_bit)
+{
+  g_return_if_fail (lock_bit < 32);
+
+  {
+#if defined (__GNUC__) && (defined (i386) || defined (__amd64__))
+ retry:
+    asm volatile goto ("lock bts %1, (%0)\n"
+                       "jc %l[contended]"
+                       : /* no output */
+                       : "r" (address), "r" ((gsize) lock_bit)
+                       : "cc", "memory"
+                       : contended);
+    return;
+
+ contended:
+    {
+      volatile gsize *pointer_address = address;
+      gsize mask = 1u << lock_bit;
+      gsize v;
+
+      v = (gsize) g_atomic_pointer_get (pointer_address);
+      if (v & mask)
+        {
+          guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
+
+          g_atomic_int_add (&g_bit_lock_contended[class], +1);
+          g_futex_wait (g_futex_int_address (address), v);
+          g_atomic_int_add (&g_bit_lock_contended[class], -1);
+        }
+    }
+    goto retry;
+#else
+  volatile gsize *pointer_address = address;
+  gsize mask = 1u << lock_bit;
+  gsize v;
+
+ retry:
+  v = g_atomic_pointer_or (pointer_address, mask);
+  if (v & mask)
+    /* already locked */
+    {
+      guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
+
+      g_atomic_int_add (&g_bit_lock_contended[class], +1);
+      g_futex_wait (g_futex_int_address (address), (guint) v);
+      g_atomic_int_add (&g_bit_lock_contended[class], -1);
+
+      goto retry;
+    }
+#endif
+  }
+}
+
+/**
+ * g_pointer_bit_trylock:
+ * @address: a pointer to a #gpointer-sized value
+ * @lock_bit: a bit value between 0 and 31
+ * @returns: %TRUE if the lock was acquired
+ *
+ * This is equivalent to g_bit_trylock, but working on pointers (or
+ * other pointer-sized values).
+ *
+ * For portability reasons, you may only lock on the bottom 32 bits of
+ * the pointer.
+ *
+ * Since: 2.30
+ **/
+gboolean
+(g_pointer_bit_trylock) (volatile void *address,
+                         gint           lock_bit)
+{
+  g_return_val_if_fail (lock_bit < 32, FALSE);
+
+  {
+#if defined (__GNUC__) && (defined (i386) || defined (__amd64__))
+    gboolean result;
+
+    asm volatile ("lock bts %2, (%1)\n"
+                  "setnc %%al\n"
+                  "movzx %%al, %0"
+                  : "=r" (result)
+                  : "r" (address), "r" ((gsize) lock_bit)
+                  : "cc", "memory");
+
+    return result;
+#else
+    volatile gsize *pointer_address = address;
+    gsize mask = 1u << lock_bit;
+    gsize v;
+
+    g_return_val_if_fail (lock_bit < 32, FALSE);
+
+    v = g_atomic_pointer_or (pointer_address, mask);
+
+    return ~v & mask;
+#endif
+  }
+}
+
+/**
+ * g_pointer_bit_unlock:
+ * @address: a pointer to a #gpointer-sized value
+ * @lock_bit: a bit value between 0 and 31
+ *
+ * This is equivalent to g_bit_unlock, but working on pointers (or other
+ * pointer-sized values).
+ *
+ * For portability reasons, you may only lock on the bottom 32 bits of
+ * the pointer.
+ *
+ * Since: 2.30
+ **/
+void
+(g_pointer_bit_unlock) (volatile void *address,
+                        gint           lock_bit)
+{
+  g_return_if_fail (lock_bit < 32);
+
+  {
+#if defined (__GNUC__) && (defined (i386) || defined (__amd64__))
+    asm volatile ("lock btr %1, (%0)"
+                  : /* no output */
+                  : "r" (address), "r" ((gsize) lock_bit)
+                  : "cc", "memory");
+#else
+    volatile gsize *pointer_address = address;
+    gsize mask = 1u << lock_bit;
+
+    g_atomic_pointer_and (pointer_address, ~mask);
+#endif
+
+    {
+      guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
+      if (g_atomic_int_get (&g_bit_lock_contended[class]))
+        g_futex_wake (g_futex_int_address (address));
+    }
+  }
+}
diff --git a/glib/gbitlock.h b/glib/gbitlock.h
index 5f6a67f..ea9cb41 100644
--- a/glib/gbitlock.h
+++ b/glib/gbitlock.h
@@ -38,6 +38,35 @@ gboolean  g_bit_trylock                   (volatile gint *address,
 void      g_bit_unlock                    (volatile gint *address,
                                            gint           lock_bit);
 
+void      g_pointer_bit_lock              (volatile void *address,
+                                           gint           lock_bit);
+gboolean  g_pointer_bit_trylock           (volatile void *address,
+                                           gint           lock_bit);
+void      g_pointer_bit_unlock            (volatile void *address,
+                                           gint           lock_bit);
+
+#ifdef __GNUC__
+
+#define g_pointer_bit_lock(address, lock_bit) \
+  (G_GNUC_EXTENSION ({                                                       \
+    G_STATIC_ASSERT (sizeof *(address) == sizeof (gpointer));                \
+    g_pointer_bit_lock ((address), (lock_bit));                              \
+  }))
+
+#define g_pointer_bit_trylock(address, lock_bit) \
+  (G_GNUC_EXTENSION ({                                                       \
+    G_STATIC_ASSERT (sizeof *(address) == sizeof (gpointer));                \
+    g_pointer_bit_trylock ((address), (lock_bit));                           \
+  }))
+
+#define g_pointer_bit_unlock(address, lock_bit) \
+  (G_GNUC_EXTENSION ({                                                       \
+    G_STATIC_ASSERT (sizeof *(address) == sizeof (gpointer));                \
+    g_pointer_bit_unlock ((address), (lock_bit));                            \
+  }))
+
+#endif
+
 G_END_DECLS
 
 #endif /* __G_BITLOCK_H_ */
diff --git a/glib/glib.symbols b/glib/glib.symbols
index c26bd91..d38450d 100644
--- a/glib/glib.symbols
+++ b/glib/glib.symbols
@@ -1065,6 +1065,9 @@ g_string_append_c
 g_bit_lock
 g_bit_trylock
 g_bit_unlock
+g_pointer_bit_lock
+g_pointer_bit_trylock
+g_pointer_bit_unlock
 g_once_impl
 g_once_init_enter_impl
 g_once_init_leave
diff --git a/gthread/tests/1bit-mutex.c b/gthread/tests/1bit-mutex.c
index 4b405f4..0bfce91 100644
--- a/gthread/tests/1bit-mutex.c
+++ b/gthread/tests/1bit-mutex.c
@@ -18,6 +18,7 @@
 #define ITERATIONS 10000
 #define THREADS    100
 
+#include <glib.h>
 
 #if TEST_EMULATED_FUTEX
   /* this is defined for the 1bit-mutex-emufutex test.
@@ -31,9 +32,16 @@
   /* rebuild gbitlock.c without futex support,
      defining our own version of the g_bit_*lock symbols
    */
+  #undef g_pointer_bit_lock
+  #undef g_pointer_bit_trylock
+  #undef g_pointer_bit_unlock
+
   #define g_bit_lock            _emufutex_g_bit_lock
   #define g_bit_trylock         _emufutex_g_bit_trylock
   #define g_bit_unlock          _emufutex_g_bit_unlock
+  #define g_pointer_bit_lock    _emufutex_g_pointer_bit_lock
+  #define g_pointer_bit_trylock _emufutex_g_pointer_bit_trylock
+  #define g_pointer_bit_unlock  _emufutex_g_pointer_bit_unlock
   #define _g_futex_thread_init  _emufutex_g_futex_thread_init
 
   #define G_BIT_LOCK_FORCE_FUTEX_EMULATION
@@ -41,24 +49,32 @@
   #include <glib/gbitlock.c>
 #endif
 
-#include <glib.h>
-
 volatile GThread *owners[LOCKS];
 volatile gint     locks[LOCKS];
+volatile gpointer ptrs[LOCKS];
 volatile gint     bits[LOCKS];
 
 static void
-acquire (int nr)
+acquire (int      nr,
+         gboolean use_pointers)
 {
   GThread *self;
 
   self = g_thread_self ();
 
-  if (!g_bit_trylock (&locks[nr], bits[nr]))
+  g_assert_cmpint (((gsize) ptrs) % 8, ==, 0);
+
+  if (!(use_pointers ?
+          g_pointer_bit_trylock (&ptrs[nr], bits[nr])
+        : g_bit_trylock (&locks[nr], bits[nr])))
     {
       if (g_test_verbose ())
         g_print ("thread %p going to block on lock %d\n", self, nr);
-      g_bit_lock (&locks[nr], bits[nr]);
+
+      if (use_pointers)
+        g_pointer_bit_lock (&ptrs[nr], bits[nr]);
+      else
+        g_bit_lock (&locks[nr], bits[nr]);
     }
 
   g_assert (owners[nr] == NULL);   /* hopefully nobody else is here */
@@ -71,23 +87,34 @@ acquire (int nr)
 
   g_assert (owners[nr] == self);   /* hopefully this is still us... */
   owners[nr] = NULL;               /* make way for the next guy */
-  g_bit_unlock (&locks[nr], bits[nr]);
+
+  if (use_pointers)
+    g_pointer_bit_unlock (&ptrs[nr], bits[nr]);
+  else
+    g_bit_unlock (&locks[nr], bits[nr]);
 }
 
 static gpointer
 thread_func (gpointer data)
 {
+  gboolean use_pointers = GPOINTER_TO_INT (data);
   gint i;
+  GRand *rand;
+
+  rand = g_rand_new ();
 
   for (i = 0; i < ITERATIONS; i++)
-    acquire (g_random_int () % LOCKS);
+    acquire (g_rand_int_range (rand, 0, LOCKS), use_pointers);
+
+  g_rand_free (rand);
 
   return NULL;
 }
 
 static void
-testcase (void)
+testcase (gconstpointer data)
 {
+  gboolean use_pointers = GPOINTER_TO_INT (data);
   GThread *threads[THREADS];
   int i;
 
@@ -109,7 +136,9 @@ testcase (void)
     bits[i] = g_random_int () % 32;
 
   for (i = 0; i < THREADS; i++)
-    threads[i] = g_thread_create (thread_func, NULL, TRUE, NULL);
+    threads[i] = g_thread_create (thread_func,
+                                  GINT_TO_POINTER (use_pointers),
+                                  TRUE, NULL);
 
   for (i = 0; i < THREADS; i++)
     g_thread_join (threads[i]);
@@ -126,7 +155,8 @@ main (int argc, char **argv)
 {
   g_test_init (&argc, &argv, NULL);
 
-  g_test_add_func ("/glib/1bit-mutex" SUFFIX, testcase);
+  g_test_add_data_func ("/glib/1bit-mutex" SUFFIX "/int", (gpointer) 0, testcase);
+  g_test_add_data_func ("/glib/1bit-mutex" SUFFIX "/pointer", (gpointer) 1, testcase);
 
   return g_test_run ();
 }