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