From 669b0f2d6b5ef3a4924a1402d569c4e38e4fb41c Mon Sep 17 00:00:00 2001 From: Ryan Lortie Date: Thu, 28 Jan 2010 11:32:07 -0500 Subject: [PATCH] Bug 548967 - 1 bit mutex lock Add support for a mutex lock that consumes only one bit of storage inside of an integer on systems that support futexes. Futex is emulated (at a higher cost) on systems that don't have it -- but only in the contended case. --- configure.in | 26 +++ docs/reference/glib/glib-sections.txt | 5 + glib/Makefile.am | 2 + glib/gbitlock.c | 292 ++++++++++++++++++++++++++++++++++ glib/gbitlock.h | 43 +++++ glib/glib.h | 1 + glib/glib.symbols | 8 + glib/gthread.c | 1 + glib/gthreadprivate.h | 1 + 9 files changed, 379 insertions(+) create mode 100644 glib/gbitlock.c create mode 100644 glib/gbitlock.h diff --git a/configure.in b/configure.in index ad7b6c3..bda92e8 100644 --- a/configure.in +++ b/configure.in @@ -2544,6 +2544,32 @@ fi AM_CONDITIONAL(HAVE_GCC_BUILTINS_FOR_ATOMIC_OPERATIONS, [test $glib_cv_gcc_has_builtin_atomic_operations = yes]) +dnl ************************ +dnl ** Check for futex(2) ** +dnl ************************ +AC_MSG_CHECKING([for futex(2) system call]) +AC_COMPILE_IFELSE([ +#include +#include +#include + +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 4393fa9..881eb18 100644 --- a/docs/reference/glib/glib-sections.txt +++ b/docs/reference/glib/glib-sections.txt @@ -660,6 +660,11 @@ g_once g_once_init_enter g_once_init_leave + +g_bit_lock +g_bit_trylock +g_bit_unlock + G_THREAD_ECF G_THREAD_CF diff --git a/glib/Makefile.am b/glib/Makefile.am index d285ffd..79f0b56 100644 --- a/glib/Makefile.am +++ b/glib/Makefile.am @@ -109,6 +109,7 @@ libglib_2_0_la_SOURCES = \ $(gatomic_c) \ gbacktrace.c \ gbase64.c \ + gbitlock.c \ gbookmarkfile.c \ gbsearcharray.h \ gcache.c \ @@ -196,6 +197,7 @@ glibsubinclude_HEADERS = \ gatomic.h \ gbacktrace.h \ gbase64.h \ + gbitlock.h \ gbookmarkfile.h \ gcache.h \ gchecksum.h \ diff --git a/glib/gbitlock.c b/glib/gbitlock.c new file mode 100644 index 0000000..5181b11 --- /dev/null +++ b/glib/gbitlock.c @@ -0,0 +1,292 @@ +/* + * Copyright © 2008 Ryan Lortie + * Copyright © 2010 Codethink Limited + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2 of the licence, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + * + * Author: Ryan Lortie + */ + +#include "gbitlock.h" + +#include +#include +#include + +#include "gthreadprivate.h" +#include "config.h" + +#include "galias.h" + +#ifndef HAVE_FUTEX +static GSList *g_futex_address_list = NULL; +static GMutex *g_futex_mutex = NULL; +#endif + +void +_g_futex_thread_init (void) { +#ifndef HAVE_FUTEX + g_futex_mutex = g_mutex_new (); +#endif +} + +#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 +#include +#include + +/* < 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 + * @lock_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_trylock: + * @address: a pointer to an integer + * @lock_bit: a bit value between 0 and 31 + * + * Sets the indicated @lock_bit in @address, returning %TRUE if + * successful. If the bit is already set, returns %FALSE immediately. + * + * Attempting to lock on two different bits within the same integer is + * not supported. + * + * 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. + **/ +gboolean +g_bit_trylock (volatile gint *address, + gint lock_bit) +{ + guint v; + + retry: + v = g_atomic_int_get (address); + if (v & (1u << lock_bit)) + /* already locked */ + return FALSE; + + if (!g_atomic_int_compare_and_exchange (address, v, v | (1u << lock_bit))) + goto retry; + + return TRUE; +} + +/** + * g_bit_unlock: + * @address: a pointer to an integer + * @lock_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_atomic_int_get (&g_bit_lock_contended[class])) + g_futex_wake (address); +} + +#define __G_BITLOCK_C__ +#include "galiasdef.c" diff --git a/glib/gbitlock.h b/glib/gbitlock.h new file mode 100644 index 0000000..15ee0e2 --- /dev/null +++ b/glib/gbitlock.h @@ -0,0 +1,43 @@ +/* + * Copyright © 2008 Ryan Lortie + * Copyright © 2010 Codethink Limited + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2 of the licence, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + * + * Author: Ryan Lortie + */ + +#ifndef __G_BITLOCK_H__ +#define __G_BITLOCK_H__ + +#include + +#if defined(G_DISABLE_SINGLE_INCLUDES) && !defined (__GLIB_H_INSIDE__) && !defined (GLIB_COMPILATION) +#error "Only can be included directly." +#endif + +G_BEGIN_DECLS + +void g_bit_lock (volatile gint *lock, + gint lock_bit); +gboolean g_bit_trylock (volatile gint *lock, + gint lock_bit); +void g_bit_unlock (volatile gint *lock, + gint lock_bit); + +G_END_DECLS + +#endif /* __G_BITLOCK_H_ */ diff --git a/glib/glib.h b/glib/glib.h index 209971d..35f1617 100644 --- a/glib/glib.h +++ b/glib/glib.h @@ -35,6 +35,7 @@ #include #include #include +#include #include #include #include diff --git a/glib/glib.symbols b/glib/glib.symbols index ad2b509..ddf7a2e 100644 --- a/glib/glib.symbols +++ b/glib/glib.symbols @@ -1264,6 +1264,14 @@ g_str_hash #endif #endif +#if IN_HEADER(__G_BITLOCK_H__) +#if IN_FILE(__G_BITLOCK_C__) +g_bit_lock +g_bit_trylock +g_bit_unlock +#endif +#endif + #if IN_HEADER(__G_THREAD_H__) #if IN_FILE(__G_THREAD_C__) g_once_impl diff --git a/glib/gthread.c b/glib/gthread.c index 0903c7e..0fe367b 100644 --- a/glib/gthread.c +++ b/glib/gthread.c @@ -166,6 +166,7 @@ g_thread_init_glib (void) _g_rand_thread_init (); _g_main_thread_init (); _g_utils_thread_init (); + _g_futex_thread_init (); #ifdef G_OS_WIN32 _g_win32_thread_init (); #endif diff --git a/glib/gthreadprivate.h b/glib/gthreadprivate.h index c9b5fa5..c75924c 100644 --- a/glib/gthreadprivate.h +++ b/glib/gthreadprivate.h @@ -58,6 +58,7 @@ G_GNUC_INTERNAL void _g_rand_thread_init (void); G_GNUC_INTERNAL void _g_main_thread_init (void); G_GNUC_INTERNAL void _g_atomic_thread_init (void); G_GNUC_INTERNAL void _g_utils_thread_init (void); +G_GNUC_INTERNAL void _g_futex_thread_init (void); #ifdef G_OS_WIN32 G_GNUC_INTERNAL void _g_win32_thread_init (void); -- 2.7.4