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/gmessages.h>
  26 #include <glib/gatomic.h>
  27 #include <glib/gslist.h>
  28 #include <glib/gthread.h>
  29
  30 #include "gthreadprivate.h"
  31 #include "config.h"
  32
  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 <sys/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 (__NR_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 (__NR_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 WaitAddress *
 115 g_futex_find_address (const volatile gint *address)
 116 {
 117   GSList *node;
 118
 119   for (node = g_futex_address_list; node; node = node->next)
 120     {
 121       WaitAddress *waiter = node->data;
 122
 123       if (waiter->address == address)
 124         return waiter;
 125     }
 126
 127   return NULL;
 128 }
 129
 130 static void
 131 g_futex_wait (const volatile gint *address,
 132               gint                 value)
 133 {
 134   g_mutex_lock (g_futex_mutex);
 135   if G_LIKELY (g_atomic_int_get (address) == value)
 136     {
 137       WaitAddress *waiter;
 138
 139       if ((waiter = g_futex_find_address (address)) == NULL)
 140         {
 141           waiter = g_slice_new (WaitAddress);
 142           waiter->address = address;
 143           waiter->wait_queue = g_cond_new ();
 144           waiter->ref_count = 0;
 145           g_futex_address_list =
 146             g_slist_prepend (g_futex_address_list, waiter);
 147         }
 148
 149       waiter->ref_count++;
 150       g_cond_wait (waiter->wait_queue, g_futex_mutex);
 151
 152       if (!--waiter->ref_count)
 153         {
 154           g_futex_address_list =
 155             g_slist_remove (g_futex_address_list, waiter);
 156           g_cond_free (waiter->wait_queue);
 157           g_slice_free (WaitAddress, waiter);
 158         }
 159     }
 160   g_mutex_unlock (g_futex_mutex);
 161 }
 162
 163 static void
 164 g_futex_wake (const volatile gint *address)
 165 {
 166   WaitAddress *waiter;
 167
 168   /* need to lock here for two reasons:
 169    *   1) need to acquire/release lock to ensure waiter is not in
 170    *      the process of registering a wait
 171    *   2) need to -stay- locked until the end to ensure a wake()
 172    *      in another thread doesn't cause 'waiter' to stop existing
 173    */
 174   g_mutex_lock (g_futex_mutex);
 175   if ((waiter = g_futex_find_address (address)))
 176     g_cond_signal (waiter->wait_queue);
 177   g_mutex_unlock (g_futex_mutex);
 178 }
 179 #endif
 180
 181 #define CONTENTION_CLASSES 11
 182 static volatile gint g_bit_lock_contended[CONTENTION_CLASSES];
 183
 184 /**
 185  * g_bit_lock:
 186  * @address: a pointer to an integer
 187  * @lock_bit: a bit value between 0 and 31
 188  *
 189  * Sets the indicated @lock_bit in @address.  If the bit is already
 190  * set, this call will block until g_bit_unlock() unsets the
 191  * corresponding bit.
 192  *
 193  * Attempting to lock on two different bits within the same integer is
 194  * not supported and will very probably cause deadlocks.
 195  *
 196  * The value of the bit that is set is (1u << @bit).  If @bit is not
 197  * between 0 and 31 then the result is undefined.
 198  *
 199  * This function accesses @address atomically.  All other accesses to
 200  * @address must be atomic in order for this function to work
 201  * reliably.
 202  *
 203  * Since: 2.24
 204  **/
 205 void
 206 g_bit_lock (volatile gint *address,
 207             gint           lock_bit)
 208 {
 209 #if defined (__GNUC__) && (defined (i386) || defined (__amd64__))
 210  retry:
 211   asm volatile goto ("lock bts %1, (%0)\n"
 212                      "jc %l[contended]"
 213                      : /* no output */
 214                      : "r" (address), "r" (lock_bit)
 215                      : "cc", "memory"
 216                      : contended);
 217   return;
 218
 219  contended:
 220   {
 221     guint mask = 1u << lock_bit;
 222     guint v;
 223
 224     v = g_atomic_int_get (address);
 225     if (v & mask)
 226       {
 227         guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
 228
 229         g_atomic_int_add (&g_bit_lock_contended[class], +1);
 230         g_futex_wait (address, v);
 231         g_atomic_int_add (&g_bit_lock_contended[class], -1);
 232       }
 233   }
 234   goto retry;
 235 #else
 236   guint mask = 1u << lock_bit;
 237   guint v;
 238
 239  retry:
 240   v = g_atomic_int_or (address, mask);
 241   if (v & mask)
 242     /* already locked */
 243     {
 244       guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
 245
 246       g_atomic_int_add (&g_bit_lock_contended[class], +1);
 247       g_futex_wait (address, v);
 248       g_atomic_int_add (&g_bit_lock_contended[class], -1);
 249
 250       goto retry;
 251     }
 252 #endif
 253 }
 254
 255 /**
 256  * g_bit_trylock:
 257  * @address: a pointer to an integer
 258  * @lock_bit: a bit value between 0 and 31
 259  * @returns: %TRUE if the lock was acquired
 260  *
 261  * Sets the indicated @lock_bit in @address, returning %TRUE if
 262  * successful.  If the bit is already set, returns %FALSE immediately.
 263  *
 264  * Attempting to lock on two different bits within the same integer is
 265  * not supported.
 266  *
 267  * The value of the bit that is set is (1u << @bit).  If @bit is not
 268  * between 0 and 31 then the result is undefined.
 269  *
 270  * This function accesses @address atomically.  All other accesses to
 271  * @address must be atomic in order for this function to work
 272  * reliably.
 273  *
 274  * Since: 2.24
 275  **/
 276 gboolean
 277 g_bit_trylock (volatile gint *address,
 278                gint           lock_bit)
 279 {
 280 #if defined (__GNUC__) && (defined (i386) || defined (__amd64__))
 281   gboolean result;
 282
 283   asm volatile ("lock bts %2, (%1)\n"
 284                 "setnc %%al\n"
 285                 "movzx %%al, %0"
 286                 : "=r" (result)
 287                 : "r" (address), "r" (lock_bit)
 288                 : "cc", "memory");
 289
 290   return result;
 291 #else
 292   guint mask = 1u << lock_bit;
 293   guint v;
 294
 295   v = g_atomic_int_or (address, mask);
 296
 297   return ~v & mask;
 298 #endif
 299 }
 300
 301 /**
 302  * g_bit_unlock:
 303  * @address: a pointer to an integer
 304  * @lock_bit: a bit value between 0 and 31
 305  *
 306  * Clears the indicated @lock_bit in @address.  If another thread is
 307  * currently blocked in g_bit_lock() on this same bit then it will be
 308  * woken up.
 309  *
 310  * This function accesses @address atomically.  All other accesses to
 311  * @address must be atomic in order for this function to work
 312  * reliably.
 313  *
 314  * Since: 2.24
 315  **/
 316 void
 317 g_bit_unlock (volatile gint *address,
 318               gint           lock_bit)
 319 {
 320 #if defined (__GNUC__) && (defined (i386) || defined (__amd64__))
 321   asm volatile ("lock btr %1, (%0)"
 322                 : /* no output */
 323                 : "r" (address), "r" (lock_bit)
 324                 : "cc", "memory");
 325 #else
 326   guint mask = 1u << lock_bit;
 327
 328   g_atomic_int_and (address, ~mask);
 329 #endif
 330
 331   {
 332     guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
 333
 334     if (g_atomic_int_get (&g_bit_lock_contended[class]))
 335       g_futex_wake (address);
 336   }
 337 }
 338
 339
 340 /* We emulate pointer-sized futex(2) because the kernel API only
 341  * supports integers.
 342  *
 343  * We assume that the 'interesting' part is always the lower order bits.
 344  * This assumption holds because pointer bitlocks are restricted to
 345  * using the low order bits of the pointer as the lock.
 346  *
 347  * On 32 bits, there is nothing to do since the pointer size is equal to
 348  * the integer size.  On little endian the lower-order bits don't move,
 349  * so do nothing.  Only on 64bit big endian do we need to do a bit of
 350  * pointer arithmetic: the low order bits are shifted by 4 bytes.  We
 351  * have a helper function that always does the right thing here.
 352  *
 353  * Since we always consider the low-order bits of the integer value, a
 354  * simple cast from (gsize) to (guint) always takes care of that.
 355  *
 356  * After that, pointer-sized futex becomes as simple as:
 357  *
 358  *   g_futex_wait (g_futex_int_address (address), (guint) value);
 359  *
 360  * and
 361  *
 362  *   g_futex_wake (g_futex_int_address (int_address));
 363  */
 364 static const volatile gint *
 365 g_futex_int_address (const volatile void *address)
 366 {
 367   const volatile gint *int_address = address;
 368
 369 #if G_BYTE_ORDER == G_BIG_ENDIAN && GLIB_SIZEOF_VOID_P == 8
 370   int_address++;
 371 #endif
 372
 373   return int_address;
 374 }
 375
 376 /**
 377  * g_pointer_bit_lock:
 378  * @address: a pointer to a #gpointer-sized value
 379  * @lock_bit: a bit value between 0 and 31
 380  *
 381  * This is equivalent to g_bit_lock, but working on pointers (or other
 382  * pointer-sized values).
 383  *
 384  * For portability reasons, you may only lock on the bottom 32 bits of
 385  * the pointer.
 386  *
 387  * Since: 2.30
 388  **/
 389 void
 390 (g_pointer_bit_lock) (volatile void *address,
 391                       gint           lock_bit)
 392 {
 393   g_return_if_fail (lock_bit < 32);
 394
 395   {
 396 #if defined (__GNUC__) && (defined (i386) || defined (__amd64__))
 397  retry:
 398     asm volatile goto ("lock bts %1, (%0)\n"
 399                        "jc %l[contended]"
 400                        : /* no output */
 401                        : "r" (address), "r" ((gsize) lock_bit)
 402                        : "cc", "memory"
 403                        : contended);
 404     return;
 405
 406  contended:
 407     {
 408       volatile gsize *pointer_address = address;
 409       gsize mask = 1u << lock_bit;
 410       gsize v;
 411
 412       v = (gsize) g_atomic_pointer_get (pointer_address);
 413       if (v & mask)
 414         {
 415           guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
 416
 417           g_atomic_int_add (&g_bit_lock_contended[class], +1);
 418           g_futex_wait (g_futex_int_address (address), v);
 419           g_atomic_int_add (&g_bit_lock_contended[class], -1);
 420         }
 421     }
 422     goto retry;
 423 #else
 424   volatile gsize *pointer_address = address;
 425   gsize mask = 1u << lock_bit;
 426   gsize v;
 427
 428  retry:
 429   v = g_atomic_pointer_or (pointer_address, mask);
 430   if (v & mask)
 431     /* already locked */
 432     {
 433       guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
 434
 435       g_atomic_int_add (&g_bit_lock_contended[class], +1);
 436       g_futex_wait (g_futex_int_address (address), (guint) v);
 437       g_atomic_int_add (&g_bit_lock_contended[class], -1);
 438
 439       goto retry;
 440     }
 441 #endif
 442   }
 443 }
 444
 445 /**
 446  * g_pointer_bit_trylock:
 447  * @address: a pointer to a #gpointer-sized value
 448  * @lock_bit: a bit value between 0 and 31
 449  * @returns: %TRUE if the lock was acquired
 450  *
 451  * This is equivalent to g_bit_trylock, but working on pointers (or
 452  * other pointer-sized values).
 453  *
 454  * For portability reasons, you may only lock on the bottom 32 bits of
 455  * the pointer.
 456  *
 457  * Since: 2.30
 458  **/
 459 gboolean
 460 (g_pointer_bit_trylock) (volatile void *address,
 461                          gint           lock_bit)
 462 {
 463   g_return_val_if_fail (lock_bit < 32, FALSE);
 464
 465   {
 466 #if defined (__GNUC__) && (defined (i386) || defined (__amd64__))
 467     gboolean result;
 468
 469     asm volatile ("lock bts %2, (%1)\n"
 470                   "setnc %%al\n"
 471                   "movzx %%al, %0"
 472                   : "=r" (result)
 473                   : "r" (address), "r" ((gsize) lock_bit)
 474                   : "cc", "memory");
 475
 476     return result;
 477 #else
 478     volatile gsize *pointer_address = address;
 479     gsize mask = 1u << lock_bit;
 480     gsize v;
 481
 482     g_return_val_if_fail (lock_bit < 32, FALSE);
 483
 484     v = g_atomic_pointer_or (pointer_address, mask);
 485
 486     return ~v & mask;
 487 #endif
 488   }
 489 }
 490
 491 /**
 492  * g_pointer_bit_unlock:
 493  * @address: a pointer to a #gpointer-sized value
 494  * @lock_bit: a bit value between 0 and 31
 495  *
 496  * This is equivalent to g_bit_unlock, but working on pointers (or other
 497  * pointer-sized values).
 498  *
 499  * For portability reasons, you may only lock on the bottom 32 bits of
 500  * the pointer.
 501  *
 502  * Since: 2.30
 503  **/
 504 void
 505 (g_pointer_bit_unlock) (volatile void *address,
 506                         gint           lock_bit)
 507 {
 508   g_return_if_fail (lock_bit < 32);
 509
 510   {
 511 #if defined (__GNUC__) && (defined (i386) || defined (__amd64__))
 512     asm volatile ("lock btr %1, (%0)"
 513                   : /* no output */
 514                   : "r" (address), "r" ((gsize) lock_bit)
 515                   : "cc", "memory");
 516 #else
 517     volatile gsize *pointer_address = address;
 518     gsize mask = 1u << lock_bit;
 519
 520     g_atomic_pointer_and (pointer_address, ~mask);
 521 #endif
 522
 523     {
 524       guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
 525       if (g_atomic_int_get (&g_bit_lock_contended[class]))
 526         g_futex_wake (g_futex_int_address (address));
 527     }
 528   }
 529 }