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 GStaticMutex g_futex_mutex = G_STATIC_MUTEX_INIT;
  40 static GSList *g_futex_address_list = NULL;
  41 #endif
  42
  43 #ifdef HAVE_FUTEX
  44 /*
  45  * We have headers for futex(2) on the build machine.  This does not
  46  * imply that every system that ever runs the resulting glib will have
  47  * kernel support for futex, but you'd have to have a pretty old
  48  * kernel in order for that not to be the case.
  49  *
  50  * If anyone actually gets bit by this, please file a bug. :)
  51  */
  52 #include <linux/futex.h>
  53 #include <sys/syscall.h>
  54 #include <unistd.h>
  55
  56 /* < private >
  57  * g_futex_wait:
  58  * @address: a pointer to an integer
  59  * @value: the value that should be at @address
  60  *
  61  * Atomically checks that the value stored at @address is equal to
  62  * @value and then blocks.  If the value stored at @address is not
  63  * equal to @value then this function returns immediately.
  64  *
  65  * To unblock, call g_futex_wake() on @address.
  66  *
  67  * This call may spuriously unblock (for example, in response to the
  68  * process receiving a signal) but this is not guaranteed.  Unlike the
  69  * Linux system call of a similar name, there is no guarantee that a
  70  * waiting process will unblock due to a g_futex_wake() call in a
  71  * separate process.
  72  */
  73 static void
  74 g_futex_wait (const volatile gint *address,
  75               gint                 value)
  76 {
  77   syscall (__NR_futex, address, (gsize) FUTEX_WAIT, (gsize) value, NULL);
  78 }
  79
  80 /* < private >
  81  * g_futex_wake:
  82  * @address: a pointer to an integer
  83  *
  84  * Nominally, wakes one thread that is blocked in g_futex_wait() on
  85  * @address (if any thread is currently waiting).
  86  *
  87  * As mentioned in the documention for g_futex_wait(), spurious
  88  * wakeups may occur.  As such, this call may result in more than one
  89  * thread being woken up.
  90  */
  91 static void
  92 g_futex_wake (const volatile gint *address)
  93 {
  94   syscall (__NR_futex, address, (gsize) FUTEX_WAKE, (gsize) 1, NULL);
  95 }
  96
  97 #else
  98
  99 /* emulate futex(2) */
 100 typedef struct
 101 {
 102   const volatile gint *address;
 103   gint                 ref_count;
 104   GCond               *wait_queue;
 105 } WaitAddress;
 106
 107 static WaitAddress *
 108 g_futex_find_address (const volatile gint *address)
 109 {
 110   GSList *node;
 111
 112   for (node = g_futex_address_list; node; node = node->next)
 113     {
 114       WaitAddress *waiter = node->data;
 115
 116       if (waiter->address == address)
 117         return waiter;
 118     }
 119
 120   return NULL;
 121 }
 122
 123 static void
 124 g_futex_wait (const volatile gint *address,
 125               gint                 value)
 126 {
 127   g_static_mutex_lock (&g_futex_mutex);
 128   if G_LIKELY (g_atomic_int_get (address) == value)
 129     {
 130       WaitAddress *waiter;
 131
 132       if ((waiter = g_futex_find_address (address)) == NULL)
 133         {
 134           waiter = g_slice_new (WaitAddress);
 135           waiter->address = address;
 136           waiter->wait_queue = g_cond_new ();
 137           waiter->ref_count = 0;
 138           g_futex_address_list =
 139             g_slist_prepend (g_futex_address_list, waiter);
 140         }
 141
 142       waiter->ref_count++;
 143       g_cond_wait (waiter->wait_queue, g_static_mutex_get_mutex (&g_futex_mutex));
 144
 145       if (!--waiter->ref_count)
 146         {
 147           g_futex_address_list =
 148             g_slist_remove (g_futex_address_list, waiter);
 149           g_cond_free (waiter->wait_queue);
 150           g_slice_free (WaitAddress, waiter);
 151         }
 152     }
 153   g_static_mutex_unlock (&g_futex_mutex);
 154 }
 155
 156 static void
 157 g_futex_wake (const volatile gint *address)
 158 {
 159   WaitAddress *waiter;
 160
 161   /* need to lock here for two reasons:
 162    *   1) need to acquire/release lock to ensure waiter is not in
 163    *      the process of registering a wait
 164    *   2) need to -stay- locked until the end to ensure a wake()
 165    *      in another thread doesn't cause 'waiter' to stop existing
 166    */
 167   g_static_mutex_lock (&g_futex_mutex);
 168   if ((waiter = g_futex_find_address (address)))
 169     g_cond_signal (waiter->wait_queue);
 170   g_static_mutex_unlock (&g_futex_mutex);
 171 }
 172 #endif
 173
 174 #define CONTENTION_CLASSES 11
 175 static volatile gint g_bit_lock_contended[CONTENTION_CLASSES];
 176
 177 #if (defined (i386) || defined (__amd64__))
 178   #if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 5)
 179     #define USE_ASM_GOTO 1
 180   #endif
 181 #endif
 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 #ifdef USE_ASM_GOTO
 209  retry:
 210   asm volatile goto ("lock bts %1, (%0)\n"
 211                      "jc %l[contended]"
 212                      : /* no output */
 213                      : "r" (address), "r" (lock_bit)
 214                      : "cc", "memory"
 215                      : contended);
 216   return;
 217
 218  contended:
 219   {
 220     guint mask = 1u << lock_bit;
 221     guint v;
 222
 223     v = g_atomic_int_get (address);
 224     if (v & mask)
 225       {
 226         guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
 227
 228         g_atomic_int_add (&g_bit_lock_contended[class], +1);
 229         g_futex_wait (address, v);
 230         g_atomic_int_add (&g_bit_lock_contended[class], -1);
 231       }
 232   }
 233   goto retry;
 234 #else
 235   guint mask = 1u << lock_bit;
 236   guint v;
 237
 238  retry:
 239   v = g_atomic_int_or (address, mask);
 240   if (v & mask)
 241     /* already locked */
 242     {
 243       guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
 244
 245       g_atomic_int_add (&g_bit_lock_contended[class], +1);
 246       g_futex_wait (address, v);
 247       g_atomic_int_add (&g_bit_lock_contended[class], -1);
 248
 249       goto retry;
 250     }
 251 #endif
 252 }
 253
 254 /**
 255  * g_bit_trylock:
 256  * @address: a pointer to an integer
 257  * @lock_bit: a bit value between 0 and 31
 258  * @returns: %TRUE if the lock was acquired
 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  * 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 #if G_BYTE_ORDER == G_BIG_ENDIAN && GLIB_SIZEOF_VOID_P == 8
 369   int_address++;
 370 #endif
 371
 372   return int_address;
 373 }
 374
 375 /**
 376  * g_pointer_bit_lock:
 377  * @address: a pointer to a #gpointer-sized value
 378  * @lock_bit: a bit value between 0 and 31
 379  *
 380  * This is equivalent to g_bit_lock, but working on pointers (or other
 381  * pointer-sized values).
 382  *
 383  * For portability reasons, you may only lock on the bottom 32 bits of
 384  * the pointer.
 385  *
 386  * Since: 2.30
 387  **/
 388 void
 389 (g_pointer_bit_lock) (volatile void *address,
 390                       gint           lock_bit)
 391 {
 392   g_return_if_fail (lock_bit < 32);
 393
 394   {
 395 #ifdef USE_ASM_GOTO
 396  retry:
 397     asm volatile goto ("lock bts %1, (%0)\n"
 398                        "jc %l[contended]"
 399                        : /* no output */
 400                        : "r" (address), "r" ((gsize) lock_bit)
 401                        : "cc", "memory"
 402                        : contended);
 403     return;
 404
 405  contended:
 406     {
 407       volatile gsize *pointer_address = address;
 408       gsize mask = 1u << lock_bit;
 409       gsize v;
 410
 411       v = (gsize) g_atomic_pointer_get (pointer_address);
 412       if (v & mask)
 413         {
 414           guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
 415
 416           g_atomic_int_add (&g_bit_lock_contended[class], +1);
 417           g_futex_wait (g_futex_int_address (address), v);
 418           g_atomic_int_add (&g_bit_lock_contended[class], -1);
 419         }
 420     }
 421     goto retry;
 422 #else
 423   volatile gsize *pointer_address = address;
 424   gsize mask = 1u << lock_bit;
 425   gsize v;
 426
 427  retry:
 428   v = g_atomic_pointer_or (pointer_address, mask);
 429   if (v & mask)
 430     /* already locked */
 431     {
 432       guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
 433
 434       g_atomic_int_add (&g_bit_lock_contended[class], +1);
 435       g_futex_wait (g_futex_int_address (address), (guint) v);
 436       g_atomic_int_add (&g_bit_lock_contended[class], -1);
 437
 438       goto retry;
 439     }
 440 #endif
 441   }
 442 }
 443
 444 /**
 445  * g_pointer_bit_trylock:
 446  * @address: a pointer to a #gpointer-sized value
 447  * @lock_bit: a bit value between 0 and 31
 448  * @returns: %TRUE if the lock was acquired
 449  *
 450  * This is equivalent to g_bit_trylock, but working on pointers (or
 451  * other pointer-sized values).
 452  *
 453  * For portability reasons, you may only lock on the bottom 32 bits of
 454  * the pointer.
 455  *
 456  * Since: 2.30
 457  **/
 458 gboolean
 459 (g_pointer_bit_trylock) (volatile void *address,
 460                          gint           lock_bit)
 461 {
 462   g_return_val_if_fail (lock_bit < 32, FALSE);
 463
 464   {
 465 #ifdef USE_ASM_GOTO
 466     gboolean result;
 467
 468     asm volatile ("lock bts %2, (%1)\n"
 469                   "setnc %%al\n"
 470                   "movzx %%al, %0"
 471                   : "=r" (result)
 472                   : "r" (address), "r" ((gsize) lock_bit)
 473                   : "cc", "memory");
 474
 475     return result;
 476 #else
 477     volatile gsize *pointer_address = address;
 478     gsize mask = 1u << lock_bit;
 479     gsize v;
 480
 481     g_return_val_if_fail (lock_bit < 32, FALSE);
 482
 483     v = g_atomic_pointer_or (pointer_address, mask);
 484
 485     return ~v & mask;
 486 #endif
 487   }
 488 }
 489
 490 /**
 491  * g_pointer_bit_unlock:
 492  * @address: a pointer to a #gpointer-sized value
 493  * @lock_bit: a bit value between 0 and 31
 494  *
 495  * This is equivalent to g_bit_unlock, but working on pointers (or other
 496  * pointer-sized values).
 497  *
 498  * For portability reasons, you may only lock on the bottom 32 bits of
 499  * the pointer.
 500  *
 501  * Since: 2.30
 502  **/
 503 void
 504 (g_pointer_bit_unlock) (volatile void *address,
 505                         gint           lock_bit)
 506 {
 507   g_return_if_fail (lock_bit < 32);
 508
 509   {
 510 #ifdef USE_ASM_GOTO
 511     asm volatile ("lock btr %1, (%0)"
 512                   : /* no output */
 513                   : "r" (address), "r" ((gsize) lock_bit)
 514                   : "cc", "memory");
 515 #else
 516     volatile gsize *pointer_address = address;
 517     gsize mask = 1u << lock_bit;
 518
 519     g_atomic_pointer_and (pointer_address, ~mask);
 520 #endif
 521
 522     {
 523       guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
 524       if (g_atomic_int_get (&g_bit_lock_contended[class]))
 525         g_futex_wake (g_futex_int_address (address));
 526     }
 527   }
 528 }