From df0b208831a797f402d9f86263e6fa5378da47cc Mon Sep 17 00:00:00 2001 From: Ryan Lortie Date: Wed, 25 May 2011 11:08:20 +0200 Subject: [PATCH] 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 #include #include #include @@ -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 #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 #endif -#include - 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 (); } -- 2.7.4