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