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 "config.h"
  24
  25 #include "gbitlock.h"
  26
  27 #include <glib/gmessages.h>
  28 #include <glib/gatomic.h>
  29 #include <glib/gslist.h>
  30 #include <glib/gthread.h>
  31 #include <glib/gslice.h>
  32
  33 #include "gthreadprivate.h"
  34
  35 #ifdef G_BIT_LOCK_FORCE_FUTEX_EMULATION
  36 #undef HAVE_FUTEX
  37 #endif
  38
  39 #ifndef HAVE_FUTEX
  40 static GMutex g_futex_mutex;
  41 static GSList *g_futex_address_list = NULL;
  42 #endif
  43
  44 #ifdef HAVE_FUTEX
  45 /*
  46  * We have headers for futex(2) on the build machine.  This does not
  47  * imply that every system that ever runs the resulting glib will have
  48  * kernel support for futex, but you'd have to have a pretty old
  49  * kernel in order for that not to be the case.
  50  *
  51  * If anyone actually gets bit by this, please file a bug. :)
  52  */
  53 #include <linux/futex.h>
  54 #include <sys/syscall.h>
  55 #include <unistd.h>
  56
  57 /* < private >
  58  * g_futex_wait:
  59  * @address: a pointer to an integer
  60  * @value: the value that should be at @address
  61  *
  62  * Atomically checks that the value stored at @address is equal to
  63  * @value and then blocks.  If the value stored at @address is not
  64  * equal to @value then this function returns immediately.
  65  *
  66  * To unblock, call g_futex_wake() on @address.
  67  *
  68  * This call may spuriously unblock (for example, in response to the
  69  * process receiving a signal) but this is not guaranteed.  Unlike the
  70  * Linux system call of a similar name, there is no guarantee that a
  71  * waiting process will unblock due to a g_futex_wake() call in a
  72  * separate process.
  73  */
  74 static void
  75 g_futex_wait (const volatile gint *address,
  76               gint                 value)
  77 {
  78   syscall (__NR_futex, address, (gsize) FUTEX_WAIT, (gsize) value, NULL);
  79 }
  80
  81 /* < private >
  82  * g_futex_wake:
  83  * @address: a pointer to an integer
  84  *
  85  * Nominally, wakes one thread that is blocked in g_futex_wait() on
  86  * @address (if any thread is currently waiting).
  87  *
  88  * As mentioned in the documention for g_futex_wait(), spurious
  89  * wakeups may occur.  As such, this call may result in more than one
  90  * thread being woken up.
  91  */
  92 static void
  93 g_futex_wake (const volatile gint *address)
  94 {
  95   syscall (__NR_futex, address, (gsize) FUTEX_WAKE, (gsize) 1, NULL);
  96 }
  97
  98 #else
  99
 100 /* emulate futex(2) */
 101 typedef struct
 102 {
 103   const volatile gint *address;
 104   gint                 ref_count;
 105   GCond                wait_queue;
 106 } WaitAddress;
 107
 108 static WaitAddress *
 109 g_futex_find_address (const volatile gint *address)
 110 {
 111   GSList *node;
 112
 113   for (node = g_futex_address_list; node; node = node->next)
 114     {
 115       WaitAddress *waiter = node->data;
 116
 117       if (waiter->address == address)
 118         return waiter;
 119     }
 120
 121   return NULL;
 122 }
 123
 124 static void
 125 g_futex_wait (const volatile gint *address,
 126               gint                 value)
 127 {
 128   g_mutex_lock (&g_futex_mutex);
 129   if G_LIKELY (g_atomic_int_get (address) == value)
 130     {
 131       WaitAddress *waiter;
 132
 133       if ((waiter = g_futex_find_address (address)) == NULL)
 134         {
 135           waiter = g_slice_new (WaitAddress);
 136           waiter->address = address;
 137           g_cond_init (&waiter->wait_queue);
 138           waiter->ref_count = 0;
 139           g_futex_address_list =
 140             g_slist_prepend (g_futex_address_list, waiter);
 141         }
 142
 143       waiter->ref_count++;
 144       g_cond_wait (&waiter->wait_queue, &g_futex_mutex);
 145
 146       if (!--waiter->ref_count)
 147         {
 148           g_futex_address_list =
 149             g_slist_remove (g_futex_address_list, waiter);
 150           g_cond_clear (&waiter->wait_queue);
 151           g_slice_free (WaitAddress, waiter);
 152         }
 153     }
 154   g_mutex_unlock (&g_futex_mutex);
 155 }
 156
 157 static void
 158 g_futex_wake (const volatile gint *address)
 159 {
 160   WaitAddress *waiter;
 161
 162   /* need to lock here for two reasons:
 163    *   1) need to acquire/release lock to ensure waiter is not in
 164    *      the process of registering a wait
 165    *   2) need to -stay- locked until the end to ensure a wake()
 166    *      in another thread doesn't cause 'waiter' to stop existing
 167    */
 168   g_mutex_lock (&g_futex_mutex);
 169   if ((waiter = g_futex_find_address (address)))
 170     g_cond_signal (&waiter->wait_queue);
 171   g_mutex_unlock (&g_futex_mutex);
 172 }
 173 #endif
 174
 175 #define CONTENTION_CLASSES 11
 176 static volatile gint g_bit_lock_contended[CONTENTION_CLASSES];
 177
 178 #if (defined (i386) || defined (__amd64__))
 179   #if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 5)
 180     #define USE_ASM_GOTO 1
 181   #endif
 182 #endif
 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 #ifdef USE_ASM_GOTO
 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  *
 260  * Sets the indicated @lock_bit in @address, returning %TRUE if
 261  * successful.  If the bit is already set, returns %FALSE immediately.
 262  *
 263  * Attempting to lock on two different bits within the same integer is
 264  * not supported.
 265  *
 266  * The value of the bit that is set is (1u << @bit).  If @bit is not
 267  * between 0 and 31 then the result is undefined.
 268  *
 269  * This function accesses @address atomically.  All other accesses to
 270  * @address must be atomic in order for this function to work
 271  * reliably.
 272  *
 273  * Returns: %TRUE if the lock was acquired
 274  *
 275  * Since: 2.24
 276  **/
 277 gboolean
 278 g_bit_trylock (volatile gint *address,
 279                gint           lock_bit)
 280 {
 281 #ifdef USE_ASM_GOTO
 282   gboolean result;
 283
 284   asm volatile ("lock bts %2, (%1)\n"
 285                 "setnc %%al\n"
 286                 "movzx %%al, %0"
 287                 : "=r" (result)
 288                 : "r" (address), "r" (lock_bit)
 289                 : "cc", "memory");
 290
 291   return result;
 292 #else
 293   guint mask = 1u << lock_bit;
 294   guint v;
 295
 296   v = g_atomic_int_or (address, mask);
 297
 298   return ~v & mask;
 299 #endif
 300 }
 301
 302 /**
 303  * g_bit_unlock:
 304  * @address: a pointer to an integer
 305  * @lock_bit: a bit value between 0 and 31
 306  *
 307  * Clears the indicated @lock_bit in @address.  If another thread is
 308  * currently blocked in g_bit_lock() on this same bit then it will be
 309  * woken up.
 310  *
 311  * This function accesses @address atomically.  All other accesses to
 312  * @address must be atomic in order for this function to work
 313  * reliably.
 314  *
 315  * Since: 2.24
 316  **/
 317 void
 318 g_bit_unlock (volatile gint *address,
 319               gint           lock_bit)
 320 {
 321 #ifdef USE_ASM_GOTO
 322   asm volatile ("lock btr %1, (%0)"
 323                 : /* no output */
 324                 : "r" (address), "r" (lock_bit)
 325                 : "cc", "memory");
 326 #else
 327   guint mask = 1u << lock_bit;
 328
 329   g_atomic_int_and (address, ~mask);
 330 #endif
 331
 332   {
 333     guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
 334
 335     if (g_atomic_int_get (&g_bit_lock_contended[class]))
 336       g_futex_wake (address);
 337   }
 338 }
 339
 340
 341 /* We emulate pointer-sized futex(2) because the kernel API only
 342  * supports integers.
 343  *
 344  * We assume that the 'interesting' part is always the lower order bits.
 345  * This assumption holds because pointer bitlocks are restricted to
 346  * using the low order bits of the pointer as the lock.
 347  *
 348  * On 32 bits, there is nothing to do since the pointer size is equal to
 349  * the integer size.  On little endian the lower-order bits don't move,
 350  * so do nothing.  Only on 64bit big endian do we need to do a bit of
 351  * pointer arithmetic: the low order bits are shifted by 4 bytes.  We
 352  * have a helper function that always does the right thing here.
 353  *
 354  * Since we always consider the low-order bits of the integer value, a
 355  * simple cast from (gsize) to (guint) always takes care of that.
 356  *
 357  * After that, pointer-sized futex becomes as simple as:
 358  *
 359  *   g_futex_wait (g_futex_int_address (address), (guint) value);
 360  *
 361  * and
 362  *
 363  *   g_futex_wake (g_futex_int_address (int_address));
 364  */
 365 static const volatile gint *
 366 g_futex_int_address (const volatile void *address)
 367 {
 368   const volatile gint *int_address = address;
 369
 370   /* this implementation makes these (reasonable) assumptions: */
 371   G_STATIC_ASSERT (G_BYTE_ORDER == G_LITTLE_ENDIAN ||
 372       (G_BYTE_ORDER == G_BIG_ENDIAN &&
 373        sizeof (int) == 4 &&
 374        (sizeof (gpointer) == 4 || sizeof (gpointer) == 8)));
 375
 376 #if G_BYTE_ORDER == G_BIG_ENDIAN && GLIB_SIZEOF_VOID_P == 8
 377   int_address++;
 378 #endif
 379
 380   return int_address;
 381 }
 382
 383 /**
 384  * g_pointer_bit_lock:
 385  * @address: a pointer to a #gpointer-sized value
 386  * @lock_bit: a bit value between 0 and 31
 387  *
 388  * This is equivalent to g_bit_lock, but working on pointers (or other
 389  * pointer-sized values).
 390  *
 391  * For portability reasons, you may only lock on the bottom 32 bits of
 392  * the pointer.
 393  *
 394  * Since: 2.30
 395  **/
 396 void
 397 (g_pointer_bit_lock) (volatile void *address,
 398                       gint           lock_bit)
 399 {
 400   g_return_if_fail (lock_bit < 32);
 401
 402   {
 403 #ifdef USE_ASM_GOTO
 404  retry:
 405     asm volatile goto ("lock bts %1, (%0)\n"
 406                        "jc %l[contended]"
 407                        : /* no output */
 408                        : "r" (address), "r" ((gsize) lock_bit)
 409                        : "cc", "memory"
 410                        : contended);
 411     return;
 412
 413  contended:
 414     {
 415       volatile gsize *pointer_address = address;
 416       gsize mask = 1u << lock_bit;
 417       gsize v;
 418
 419       v = (gsize) g_atomic_pointer_get (pointer_address);
 420       if (v & mask)
 421         {
 422           guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
 423
 424           g_atomic_int_add (&g_bit_lock_contended[class], +1);
 425           g_futex_wait (g_futex_int_address (address), v);
 426           g_atomic_int_add (&g_bit_lock_contended[class], -1);
 427         }
 428     }
 429     goto retry;
 430 #else
 431   volatile gsize *pointer_address = address;
 432   gsize mask = 1u << lock_bit;
 433   gsize v;
 434
 435  retry:
 436   v = g_atomic_pointer_or (pointer_address, mask);
 437   if (v & mask)
 438     /* already locked */
 439     {
 440       guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
 441
 442       g_atomic_int_add (&g_bit_lock_contended[class], +1);
 443       g_futex_wait (g_futex_int_address (address), (guint) v);
 444       g_atomic_int_add (&g_bit_lock_contended[class], -1);
 445
 446       goto retry;
 447     }
 448 #endif
 449   }
 450 }
 451
 452 /**
 453  * g_pointer_bit_trylock:
 454  * @address: a pointer to a #gpointer-sized value
 455  * @lock_bit: a bit value between 0 and 31
 456  *
 457  * This is equivalent to g_bit_trylock, but working on pointers (or
 458  * other pointer-sized values).
 459  *
 460  * For portability reasons, you may only lock on the bottom 32 bits of
 461  * the pointer.
 462  *
 463  * Returns: %TRUE if the lock was acquired
 464  *
 465  * Since: 2.30
 466  **/
 467 gboolean
 468 (g_pointer_bit_trylock) (volatile void *address,
 469                          gint           lock_bit)
 470 {
 471   g_return_val_if_fail (lock_bit < 32, FALSE);
 472
 473   {
 474 #ifdef USE_ASM_GOTO
 475     gboolean result;
 476
 477     asm volatile ("lock bts %2, (%1)\n"
 478                   "setnc %%al\n"
 479                   "movzx %%al, %0"
 480                   : "=r" (result)
 481                   : "r" (address), "r" ((gsize) lock_bit)
 482                   : "cc", "memory");
 483
 484     return result;
 485 #else
 486     volatile gsize *pointer_address = address;
 487     gsize mask = 1u << lock_bit;
 488     gsize v;
 489
 490     g_return_val_if_fail (lock_bit < 32, FALSE);
 491
 492     v = g_atomic_pointer_or (pointer_address, mask);
 493
 494     return ~v & mask;
 495 #endif
 496   }
 497 }
 498
 499 /**
 500  * g_pointer_bit_unlock:
 501  * @address: a pointer to a #gpointer-sized value
 502  * @lock_bit: a bit value between 0 and 31
 503  *
 504  * This is equivalent to g_bit_unlock, but working on pointers (or other
 505  * pointer-sized values).
 506  *
 507  * For portability reasons, you may only lock on the bottom 32 bits of
 508  * the pointer.
 509  *
 510  * Since: 2.30
 511  **/
 512 void
 513 (g_pointer_bit_unlock) (volatile void *address,
 514                         gint           lock_bit)
 515 {
 516   g_return_if_fail (lock_bit < 32);
 517
 518   {
 519 #ifdef USE_ASM_GOTO
 520     asm volatile ("lock btr %1, (%0)"
 521                   : /* no output */
 522                   : "r" (address), "r" ((gsize) lock_bit)
 523                   : "cc", "memory");
 524 #else
 525     volatile gsize *pointer_address = address;
 526     gsize mask = 1u << lock_bit;
 527
 528     g_atomic_pointer_and (pointer_address, ~mask);
 529 #endif
 530
 531     {
 532       guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
 533       if (g_atomic_int_get (&g_bit_lock_contended[class]))
 534         g_futex_wake (g_futex_int_address (address));
 535     }
 536   }
 537 }