glib/gbitlock.c

   1 /*
   2  * Copyright © 2008 Ryan Lortie
   3  * Copyright © 2010 Codethink Limited
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2 of the licence, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public
  16  * License along with this library; if not, write to the
  17  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18  * Boston, MA 02111-1307, USA.
  19  *
  20  * Author: Ryan Lortie <desrt@desrt.ca>
  21  */
  22
  23 #include "gbitlock.h"
  24
  25 #include <glib/gatomic.h>
  26 #include <glib/gslist.h>
  27 #include <glib/gthread.h>
  28
  29 #include "gthreadprivate.h"
  30 #include "config.h"
  31
  32 #include "galias.h"
  33
  34 #ifdef G_BIT_LOCK_FORCE_FUTEX_EMULATION
  35 #undef HAVE_FUTEX
  36 #endif
  37
  38 #ifndef HAVE_FUTEX
  39 static GSList *g_futex_address_list = NULL;
  40 static GMutex *g_futex_mutex = NULL;
  41 #endif
  42
  43 void
  44 _g_futex_thread_init (void) {
  45 #ifndef HAVE_FUTEX
  46   g_futex_mutex = g_mutex_new ();
  47 #endif
  48 }
  49
  50 #ifdef HAVE_FUTEX
  51 /*
  52  * We have headers for futex(2) on the build machine.  This does not
  53  * imply that every system that ever runs the resulting glib will have
  54  * kernel support for futex, but you'd have to have a pretty old
  55  * kernel in order for that not to be the case.
  56  *
  57  * If anyone actually gets bit by this, please file a bug. :)
  58  */
  59 #include <linux/futex.h>
  60 #include <syscall.h>
  61 #include <unistd.h>
  62
  63 /* < private >
  64  * g_futex_wait:
  65  * @address: a pointer to an integer
  66  * @value: the value that should be at @address
  67  *
  68  * Atomically checks that the value stored at @address is equal to
  69  * @value and then blocks.  If the value stored at @address is not
  70  * equal to @value then this function returns immediately.
  71  *
  72  * To unblock, call g_futex_wake() on @address.
  73  *
  74  * This call may spuriously unblock (for example, in response to the
  75  * process receiving a signal) but this is not guaranteed.  Unlike the
  76  * Linux system call of a similar name, there is no guarantee that a
  77  * waiting process will unblock due to a g_futex_wake() call in a
  78  * separate process.
  79  */
  80 static void
  81 g_futex_wait (const volatile gint *address,
  82               gint                 value)
  83 {
  84   syscall (SYS_futex, address, (gsize) FUTEX_WAIT, (gsize) value, NULL);
  85 }
  86
  87 /* < private >
  88  * g_futex_wake:
  89  * @address: a pointer to an integer
  90  *
  91  * Nominally, wakes one thread that is blocked in g_futex_wait() on
  92  * @address (if any thread is currently waiting).
  93  *
  94  * As mentioned in the documention for g_futex_wait(), spurious
  95  * wakeups may occur.  As such, this call may result in more than one
  96  * thread being woken up.
  97  */
  98 static void
  99 g_futex_wake (const volatile gint *address)
 100 {
 101   syscall (SYS_futex, address, (gsize) FUTEX_WAKE, (gsize) 1, NULL);
 102 }
 103
 104 #else
 105
 106 /* emulate futex(2) */
 107 typedef struct
 108 {
 109   const volatile gint *address;
 110   gint                 ref_count;
 111   GCond               *wait_queue;
 112 } WaitAddress;
 113
 114 static GSList *g_futex_address_list;
 115 static GMutex *g_futex_mutex;
 116
 117 static WaitAddress *
 118 g_futex_find_address (const volatile gint *address)
 119 {
 120   GSList *node;
 121
 122   for (node = g_futex_address_list; node; node = node->next)
 123     {
 124       WaitAddress *waiter = node->data;
 125
 126       if (waiter->address == address)
 127         return waiter;
 128     }
 129
 130   return NULL;
 131 }
 132
 133 static void
 134 g_futex_wait (const volatile gint *address,
 135               gint                 value)
 136 {
 137   g_mutex_lock (g_futex_mutex);
 138   if G_LIKELY (g_atomic_int_get (address) == value)
 139     {
 140       WaitAddress *waiter;
 141
 142       if ((waiter = g_futex_find_address (address)) == NULL)
 143         {
 144           waiter = g_slice_new (WaitAddress);
 145           waiter->address = address;
 146           waiter->wait_queue = g_cond_new ();
 147           waiter->ref_count = 0;
 148           g_futex_address_list =
 149             g_slist_prepend (g_futex_address_list, waiter);
 150         }
 151
 152       waiter->ref_count++;
 153       g_cond_wait (waiter->wait_queue, g_futex_mutex);
 154
 155       if (!--waiter->ref_count)
 156         {
 157           g_futex_address_list =
 158             g_slist_remove (g_futex_address_list, waiter);
 159           g_cond_free (waiter->wait_queue);
 160           g_slice_free (WaitAddress, waiter);
 161         }
 162     }
 163   g_mutex_unlock (g_futex_mutex);
 164 }
 165
 166 static void
 167 g_futex_wake (const volatile gint *address)
 168 {
 169   WaitAddress *waiter;
 170
 171   /* need to lock here for two reasons:
 172    *   1) need to acquire/release lock to ensure waiter is not in
 173    *      the process of registering a wait
 174    *   2) need to -stay- locked until the end to ensure a wake()
 175    *      in another thread doesn't cause 'waiter' to stop existing
 176    */
 177   g_mutex_lock (g_futex_mutex);
 178   if ((waiter = g_futex_find_address (address)))
 179     g_cond_signal (waiter->wait_queue);
 180   g_mutex_unlock (g_futex_mutex);
 181 }
 182 #endif
 183
 184 #define CONTENTION_CLASSES 11
 185 static volatile gint g_bit_lock_contended[CONTENTION_CLASSES];
 186
 187 /**
 188  * g_bit_lock:
 189  * @address: a pointer to an integer
 190  * @lock_bit: a bit value between 0 and 31
 191  *
 192  * Sets the indicated @lock_bit in @address.  If the bit is already
 193  * set, this call will block until g_bit_unlock() unsets the
 194  * corresponding bit.
 195  *
 196  * Attempting to lock on two different bits within the same integer is
 197  * not supported and will very probably cause deadlocks.
 198  *
 199  * The value of the bit that is set is (1u << @bit).  If @bit is not
 200  * between 0 and 31 then the result is undefined.
 201  *
 202  * This function accesses @address atomically.  All other accesses to
 203  * @address must be atomic in order for this function to work
 204  * reliably.
 205  *
 206  * Since: 2.24
 207  **/
 208 void
 209 g_bit_lock (volatile gint *address,
 210             gint           lock_bit)
 211 {
 212   guint v;
 213
 214  retry:
 215   v = g_atomic_int_get (address);
 216   if (v & (1u << lock_bit))
 217     /* already locked */
 218     {
 219       guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
 220
 221       g_atomic_int_add (&g_bit_lock_contended[class], +1);
 222       g_futex_wait (address, v);
 223       g_atomic_int_add (&g_bit_lock_contended[class], -1);
 224
 225       goto retry;
 226     }
 227
 228   if (!g_atomic_int_compare_and_exchange (address, v, v | (1u << lock_bit)))
 229     goto retry;
 230 }
 231
 232 /**
 233  * g_bit_trylock:
 234  * @address: a pointer to an integer
 235  * @lock_bit: a bit value between 0 and 31
 236  * @returns: %TRUE if the lock was acquired
 237  *
 238  * Sets the indicated @lock_bit in @address, returning %TRUE if
 239  * successful.  If the bit is already set, returns %FALSE immediately.
 240  *
 241  * Attempting to lock on two different bits within the same integer is
 242  * not supported.
 243  *
 244  * The value of the bit that is set is (1u << @bit).  If @bit is not
 245  * between 0 and 31 then the result is undefined.
 246  *
 247  * This function accesses @address atomically.  All other accesses to
 248  * @address must be atomic in order for this function to work
 249  * reliably.
 250  *
 251  * Since: 2.24
 252  **/
 253 gboolean
 254 g_bit_trylock (volatile gint *address,
 255                gint           lock_bit)
 256 {
 257   guint v;
 258
 259  retry:
 260   v = g_atomic_int_get (address);
 261   if (v & (1u << lock_bit))
 262     /* already locked */
 263     return FALSE;
 264
 265   if (!g_atomic_int_compare_and_exchange (address, v, v | (1u << lock_bit)))
 266     goto retry;
 267
 268   return TRUE;
 269 }
 270
 271 /**
 272  * g_bit_unlock:
 273  * @address: a pointer to an integer
 274  * @lock_bit: a bit value between 0 and 31
 275  *
 276  * Clears the indicated @lock_bit in @address.  If another thread is
 277  * currently blocked in g_bit_lock() on this same bit then it will be
 278  * woken up.
 279  *
 280  * This function accesses @address atomically.  All other accesses to
 281  * @address must be atomic in order for this function to work
 282  * reliably.
 283  *
 284  * Since: 2.24
 285  **/
 286 void
 287 g_bit_unlock (volatile gint *address,
 288               gint           lock_bit)
 289 {
 290   guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
 291   guint v;
 292
 293  retry:
 294   v = g_atomic_int_get (address);
 295   if (!g_atomic_int_compare_and_exchange (address, v, v & ~(1u << lock_bit)))
 296     goto retry;
 297
 298   if (g_atomic_int_get (&g_bit_lock_contended[class]))
 299     g_futex_wake (address);
 300 }
 301
 302 #define __G_BITLOCK_C__
 303 #include "galiasdef.c"