[glib/gvariant: 1/116] Bug 548967 – single bit mutex locks

[Ryan Lortie <ryanl src gnome org>]

commit 15af02e9cec37ec1716d4b61d8bde9129818a1e8
Author: Ryan Lortie <desrt desrt ca>
Date:   Sun Apr 5 22:40:06 2009 -0400

    Bug 548967 â?? single bit mutex locks
    
    Add g_bit_lock and g_bit_unlock functions that allow using a single bit
    of an integer as a lock.  Document the new functions.

 configure.in                          |   26 ++++
 docs/reference/glib/glib-sections.txt |    4 +
 glib/glib.symbols                     |    2 +
 glib/gthread.c                        |  217 +++++++++++++++++++++++++++++++++
 glib/gthread.h                        |    5 +
 5 files changed, 254 insertions(+), 0 deletions(-)
---
diff --git a/configure.in b/configure.in
index 5e409c6..9b17a63 100644
--- a/configure.in
+++ b/configure.in
@@ -2505,6 +2505,32 @@ else
   fi
 fi
 
+dnl ************************
+dnl ** Check for futex(2) **
+dnl ************************
+AC_MSG_CHECKING([for futex(2) system call])
+AC_COMPILE_IFELSE([ 
+#include <linux/futex.h>
+#include <syscall.h>
+#include <unistd.h>
+
+int
+main (void)
+{
+  /* it's not like this actually runs or anything... */
+  syscall (SYS_futex, NULL, FUTEX_WAKE, FUTEX_WAIT);
+  return 0;
+}
+],
+[
+  AC_MSG_RESULT(yes)
+  AC_DEFINE(HAVE_FUTEX, [test "$have_futex" = "yes"],
+            [we have the futex(2) system call])
+],
+[
+  AC_MSG_RESULT(no)
+])
+
 dnl ****************************************
 dnl *** GLib POLL* compatibility defines ***
 dnl ****************************************
diff --git a/docs/reference/glib/glib-sections.txt b/docs/reference/glib/glib-sections.txt
index d78fa4b..9cb6c00 100644
--- a/docs/reference/glib/glib-sections.txt
+++ b/docs/reference/glib/glib-sections.txt
@@ -648,6 +648,10 @@ g_once
 g_once_init_enter
 g_once_init_leave
 
+<SUBSECTION>
+g_bit_lock
+g_bit_unlock
+
 <SUBSECTION Private>
 G_THREAD_ECF
 G_THREAD_CF
diff --git a/glib/glib.symbols b/glib/glib.symbols
index 6e3a63b..4929ad6 100644
--- a/glib/glib.symbols
+++ b/glib/glib.symbols
@@ -1269,6 +1269,8 @@ g_str_hash
 g_once_impl
 g_once_init_enter_impl
 g_once_init_leave
+g_bit_lock
+g_bit_unlock
 #ifdef INCLUDE_INTERNAL_SYMBOLS
 g_thread_init_glib
 g_once_init_enter
diff --git a/glib/gthread.c b/glib/gthread.c
index 0903c7e..38c8472 100644
--- a/glib/gthread.c
+++ b/glib/gthread.c
@@ -4,6 +4,7 @@
  * gthread.c: MT safety related functions
  * Copyright 1998 Sebastian Wilhelmi; University of Karlsruhe
  *                Owen Taylor
+ * Copyright © 2008 Ryan Lortie <desrt desrt ca>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -126,6 +127,10 @@ static GPrivate *g_thread_specific_private = NULL;
 static GRealThread *g_thread_all_threads = NULL;
 static GSList   *g_thread_free_indeces = NULL;
 static GSList*   g_once_init_list = NULL;
+#ifndef HAVE_FUTEX
+static GSList   *g_futex_address_list = NULL;
+static GMutex   *g_futex_mutex = NULL;
+#endif
 
 G_LOCK_DEFINE_STATIC (g_thread);
 
@@ -144,6 +149,9 @@ g_thread_init_glib (void)
   /* mutex and cond creation works without g_threads_got_initialized */
   g_once_mutex = g_mutex_new ();
   g_once_cond = g_cond_new ();
+#ifndef HAVE_FUTEX
+  g_futex_mutex = g_mutex_new ();
+#endif
 
   /* we may only create mutex and cond in here */
   _g_mem_thread_init_noprivate_nomessage ();
@@ -989,5 +997,214 @@ g_thread_get_initialized ()
   return g_thread_supported ();
 }
 
+#ifdef HAVE_FUTEX
+/*
+ * We have headers for futex(2) on the build machine.  This does not
+ * imply that every system that ever runs the resulting glib will have
+ * kernel support for futex, but you'd have to have a pretty old
+ * kernel in order for that not to be the case.
+ * 
+ * If anyone actually gets bit by this, please file a bug. :)
+ */
+#include <linux/futex.h>
+#include <syscall.h>
+#include <unistd.h>
+
+/* < private >
+ * g_futex_wait:
+ * @address: a pointer to an integer
+ * @value: the value that should be at @address
+ *
+ * Atomically checks that the value stored at @address is equal to
+ * @value and then blocks.  If the value stored at @address is not
+ * equal to @value then this function returns immediately.
+ *
+ * To unblock, call g_futex_wake() on @address.
+ *
+ * This call may spuriously unblock (for example, in response to the
+ * process receiving a signal) but this is not guaranteed.  Unlike the
+ * Linux system call of a similar name, there is no guarantee that a
+ * waiting process will unblock due to a g_futex_wake() call in a
+ * separate process.
+ */
+static void
+g_futex_wait (const volatile gint *address,
+              gint                 value)
+{
+  syscall (SYS_futex, address, (gsize) FUTEX_WAIT, (gsize) value, NULL);
+}
+
+/* < private >
+ * g_futex_wake:
+ * @address: a pointer to an integer
+ *
+ * Nominally, wakes one thread that is blocked in g_futex_wait() on
+ * @address (if any thread is currently waiting).
+ *
+ * As mentioned in the documention for g_futex_wait(), spurious
+ * wakeups may occur.  As such, this call may result in more than one
+ * thread being woken up.
+ */
+static void
+g_futex_wake (const volatile gint *address)
+{
+  syscall (SYS_futex, address, (gsize) FUTEX_WAKE, (gsize) 1, NULL);
+}
+
+#else
+
+/* emulate futex(2) */
+typedef struct
+{
+  const volatile gint *address;
+  gint                 ref_count;
+  GCond               *wait_queue;
+} WaitAddress;
+
+static GSList *g_futex_address_list;
+static GMutex *g_futex_mutex;
+
+static WaitAddress *
+g_futex_find_address (const volatile gint *address)
+{
+  GSList *node;
+
+  for (node = g_futex_address_list; node; node = node->next)
+    {
+      WaitAddress *waiter = node->data;
+
+      if (waiter->address == address)
+        return waiter;
+    }
+
+  return NULL;
+}
+
+static void
+g_futex_wait (const volatile gint *address,
+              gint                 value)
+{
+  g_mutex_lock (g_futex_mutex);
+  if G_LIKELY (g_atomic_int_get (address) == value)
+    {
+      WaitAddress *waiter;
+
+      if ((waiter = g_futex_find_address (address)) == NULL)
+        {
+          waiter = g_slice_new (WaitAddress);
+          waiter->address = address;
+          waiter->wait_queue = g_cond_new ();
+          waiter->ref_count = 0;
+          g_futex_address_list =
+            g_slist_prepend (g_futex_address_list, waiter);
+        }
+
+      waiter->ref_count++;
+      g_cond_wait (waiter->wait_queue, g_futex_mutex);
+
+      if (!--waiter->ref_count)
+        {
+          g_futex_address_list =
+            g_slist_remove (g_futex_address_list, waiter);
+          g_cond_free (waiter->wait_queue);
+          g_slice_free (WaitAddress, waiter);
+        }
+    }
+  g_mutex_unlock (g_futex_mutex);
+}
+
+static void
+g_futex_wake (const volatile gint *address)
+{
+  WaitAddress *waiter;
+
+  /* need to lock here for two reasons:
+   *   1) need to acquire/release lock to ensure waiter is not in
+   *      the process of registering a wait
+   *   2) need to -stay- locked until the end to ensure a wake()
+   *      in another thread doesn't cause 'waiter' to stop existing
+   */
+  g_mutex_lock (g_futex_mutex);
+  if ((waiter = g_futex_find_address (address)))
+    g_cond_signal (waiter->wait_queue);
+  g_mutex_unlock (g_futex_mutex);
+}
+#endif
+
+#define CONTENTION_CLASSES 11
+static volatile gint g_bit_lock_contended[CONTENTION_CLASSES];
+
+/**
+ * g_bit_lock:
+ * @address: a pointer to an integer
+ * @bit: a bit value between 0 and 31
+ *
+ * Sets the indicated @lock_bit in @address.  If the bit is already
+ * set, this call will block until g_bit_unlock() unsets the
+ * corresponding bit.
+ *
+ * Attempting to lock on two different bits within the same integer is
+ * not supported and will very probably cause deadlocks.
+ *
+ * The value of the bit that is set is (1u << @bit).  If @bit is not
+ * between 0 and 31 then the result is undefined.
+ *
+ * This function accesses @address atomically.  All other accesses to
+ * @address must be atomic in order for this function to work
+ * reliably.
+ **/
+void
+g_bit_lock (volatile gint *address,
+            gint           lock_bit)
+{
+  guint v;
+
+ retry:
+  v = g_atomic_int_get (address);
+  if (v & (1u << lock_bit))
+    /* 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 (address, v);
+      g_atomic_int_add (&g_bit_lock_contended[class], -1);
+
+      goto retry;
+    }
+
+  if (!g_atomic_int_compare_and_exchange (address, v, v | (1u << lock_bit)))
+    goto retry;
+}
+
+/**
+ * g_bit_unlock:
+ * @address: a pointer to an integer
+ * @bit: a bit value between 0 and 31
+ *
+ * Clears the indicated @lock_bit in @address.  If another thread is
+ * currently blocked in g_bit_lock() on this same bit then it will be
+ * woken up.
+ *
+ * This function accesses @address atomically.  All other accesses to
+ * @address must be atomic in order for this function to work
+ * reliably.
+ **/
+void
+g_bit_unlock (volatile gint *address,
+              gint           lock_bit)
+{
+  guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
+  guint v;
+
+ retry:
+  v = g_atomic_int_get (address);
+  if (!g_atomic_int_compare_and_exchange (address, v, v & ~(1u << lock_bit)))
+    goto retry;
+
+  if (g_bit_lock_contended[class])
+    g_futex_wake (address);
+}
+
 #define __G_THREAD_C__
 #include "galiasdef.c"
diff --git a/glib/gthread.h b/glib/gthread.h
index 019d0db..bd4b4d7 100644
--- a/glib/gthread.h
+++ b/glib/gthread.h
@@ -305,6 +305,11 @@ void      g_static_rw_lock_free           (GStaticRWLock* lock);
 void	  g_thread_foreach         	  (GFunc    	  thread_func,
 					   gpointer 	  user_data);
 
+void      g_bit_lock                      (volatile gint *address,
+                                           gint           lock_bit);
+void      g_bit_unlock                    (volatile gint *address,
+                                           gint           lock_bit);
+
 typedef enum
 {
   G_ONCE_STATUS_NOTCALLED,