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

source code of gtk/subprojects/glib/glib/gbitlock.c