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
_g_futex_thread_init(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
g_futex_wait(const volatile gint * address,gint value)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
g_futex_wake(const volatile gint * address)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 *
g_futex_find_address(const volatile gint * address)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
g_futex_wait(const volatile gint * address,gint value)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
g_futex_wake(const volatile gint * address)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 #if (defined (i386) || defined (__amd64__))
185 #if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 5)
186 #define USE_ASM_GOTO 1
187 #endif
188 #endif
189
190 /**
191 * g_bit_lock:
192 * @address: a pointer to an integer
193 * @lock_bit: a bit value between 0 and 31
194 *
195 * Sets the indicated @lock_bit in @address. If the bit is already
196 * set, this call will block until g_bit_unlock() unsets the
197 * corresponding bit.
198 *
199 * Attempting to lock on two different bits within the same integer is
200 * not supported and will very probably cause deadlocks.
201 *
202 * The value of the bit that is set is (1u << @bit). If @bit is not
203 * between 0 and 31 then the result is undefined.
204 *
205 * This function accesses @address atomically. All other accesses to
206 * @address must be atomic in order for this function to work
207 * reliably.
208 *
209 * Since: 2.24
210 **/
211 void
g_bit_lock(volatile gint * address,gint lock_bit)212 g_bit_lock (volatile gint *address,
213 gint lock_bit)
214 {
215 #ifdef USE_ASM_GOTO
216 retry:
217 asm volatile goto ("lock bts %1, (%0)\n"
218 "jc %l[contended]"
219 : /* no output */
220 : "r" (address), "r" (lock_bit)
221 : "cc", "memory"
222 : contended);
223 return;
224
225 contended:
226 {
227 guint mask = 1u << lock_bit;
228 guint v;
229
230 v = g_atomic_int_get (address);
231 if (v & mask)
232 {
233 guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
234
235 g_atomic_int_add (&g_bit_lock_contended[class], +1);
236 g_futex_wait (address, v);
237 g_atomic_int_add (&g_bit_lock_contended[class], -1);
238 }
239 }
240 goto retry;
241 #else
242 guint mask = 1u << lock_bit;
243 guint v;
244
245 retry:
246 v = g_atomic_int_or (address, mask);
247 if (v & mask)
248 /* already locked */
249 {
250 guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
251
252 g_atomic_int_add (&g_bit_lock_contended[class], +1);
253 g_futex_wait (address, v);
254 g_atomic_int_add (&g_bit_lock_contended[class], -1);
255
256 goto retry;
257 }
258 #endif
259 }
260
261 /**
262 * g_bit_trylock:
263 * @address: a pointer to an integer
264 * @lock_bit: a bit value between 0 and 31
265 * @returns: %TRUE if the lock was acquired
266 *
267 * Sets the indicated @lock_bit in @address, returning %TRUE if
268 * successful. If the bit is already set, returns %FALSE immediately.
269 *
270 * Attempting to lock on two different bits within the same integer is
271 * not supported.
272 *
273 * The value of the bit that is set is (1u << @bit). If @bit is not
274 * between 0 and 31 then the result is undefined.
275 *
276 * This function accesses @address atomically. All other accesses to
277 * @address must be atomic in order for this function to work
278 * reliably.
279 *
280 * Since: 2.24
281 **/
282 gboolean
g_bit_trylock(volatile gint * address,gint lock_bit)283 g_bit_trylock (volatile gint *address,
284 gint lock_bit)
285 {
286 #ifdef USE_ASM_GOTO
287 gboolean result;
288
289 asm volatile ("lock bts %2, (%1)\n"
290 "setnc %%al\n"
291 "movzx %%al, %0"
292 : "=r" (result)
293 : "r" (address), "r" (lock_bit)
294 : "cc", "memory");
295
296 return result;
297 #else
298 guint mask = 1u << lock_bit;
299 guint v;
300
301 v = g_atomic_int_or (address, mask);
302
303 return ~v & mask;
304 #endif
305 }
306
307 /**
308 * g_bit_unlock:
309 * @address: a pointer to an integer
310 * @lock_bit: a bit value between 0 and 31
311 *
312 * Clears the indicated @lock_bit in @address. If another thread is
313 * currently blocked in g_bit_lock() on this same bit then it will be
314 * woken up.
315 *
316 * This function accesses @address atomically. All other accesses to
317 * @address must be atomic in order for this function to work
318 * reliably.
319 *
320 * Since: 2.24
321 **/
322 void
g_bit_unlock(volatile gint * address,gint lock_bit)323 g_bit_unlock (volatile gint *address,
324 gint lock_bit)
325 {
326 #ifdef USE_ASM_GOTO
327 asm volatile ("lock btr %1, (%0)"
328 : /* no output */
329 : "r" (address), "r" (lock_bit)
330 : "cc", "memory");
331 #else
332 guint mask = 1u << lock_bit;
333
334 g_atomic_int_and (address, ~mask);
335 #endif
336
337 {
338 guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
339
340 if (g_atomic_int_get (&g_bit_lock_contended[class]))
341 g_futex_wake (address);
342 }
343 }
344
345
346 /* We emulate pointer-sized futex(2) because the kernel API only
347 * supports integers.
348 *
349 * We assume that the 'interesting' part is always the lower order bits.
350 * This assumption holds because pointer bitlocks are restricted to
351 * using the low order bits of the pointer as the lock.
352 *
353 * On 32 bits, there is nothing to do since the pointer size is equal to
354 * the integer size. On little endian the lower-order bits don't move,
355 * so do nothing. Only on 64bit big endian do we need to do a bit of
356 * pointer arithmetic: the low order bits are shifted by 4 bytes. We
357 * have a helper function that always does the right thing here.
358 *
359 * Since we always consider the low-order bits of the integer value, a
360 * simple cast from (gsize) to (guint) always takes care of that.
361 *
362 * After that, pointer-sized futex becomes as simple as:
363 *
364 * g_futex_wait (g_futex_int_address (address), (guint) value);
365 *
366 * and
367 *
368 * g_futex_wake (g_futex_int_address (int_address));
369 */
370 static const volatile gint *
g_futex_int_address(const volatile void * address)371 g_futex_int_address (const volatile void *address)
372 {
373 const volatile gint *int_address = address;
374
375 #if G_BYTE_ORDER == G_BIG_ENDIAN && GLIB_SIZEOF_VOID_P == 8
376 int_address++;
377 #endif
378
379 return int_address;
380 }
381
382 /**
383 * g_pointer_bit_lock:
384 * @address: a pointer to a #gpointer-sized value
385 * @lock_bit: a bit value between 0 and 31
386 *
387 * This is equivalent to g_bit_lock, but working on pointers (or other
388 * pointer-sized values).
389 *
390 * For portability reasons, you may only lock on the bottom 32 bits of
391 * the pointer.
392 *
393 * Since: 2.30
394 **/
395 void
396 (g_pointer_bit_lock) (volatile void *address,
397 gint lock_bit)
398 {
399 g_return_if_fail (lock_bit < 32);
400
401 {
402 #ifdef USE_ASM_GOTO
403 retry:
404 asm volatile goto ("lock bts %1, (%0)\n"
405 "jc %l[contended]"
406 : /* no output */
407 : "r" (address), "r" ((gsize) lock_bit)
408 : "cc", "memory"
409 : contended);
410 return;
411
412 contended:
413 {
414 volatile gsize *pointer_address = address;
415 gsize mask = 1u << lock_bit;
416 gsize v;
417
418 v = (gsize) g_atomic_pointer_get (pointer_address);
419 if (v & mask)
420 {
421 guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
422
423 g_atomic_int_add (&g_bit_lock_contended[class], +1);
424 g_futex_wait (g_futex_int_address (address), v);
425 g_atomic_int_add (&g_bit_lock_contended[class], -1);
426 }
427 }
428 goto retry;
429 #else
430 volatile gsize *pointer_address = address;
431 gsize mask = 1u << lock_bit;
432 gsize v;
433
434 retry:
435 v = g_atomic_pointer_or (pointer_address, mask);
436 if (v & mask)
437 /* already locked */
438 {
439 guint class = ((gsize) address) % G_N_ELEMENTS (g_bit_lock_contended);
440
441 g_atomic_int_add (&g_bit_lock_contended[class], +1);
442 g_futex_wait (g_futex_int_address (address), (guint) v);
443 g_atomic_int_add (&g_bit_lock_contended[class], -1);
444
445 goto retry;
446 }
447 #endif
448 }
449 }
450
451 /**
452 * g_pointer_bit_trylock:
453 * @address: a pointer to a #gpointer-sized value
454 * @lock_bit: a bit value between 0 and 31
455 * @returns: %TRUE if the lock was acquired
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 * Since: 2.30
464 **/
gboolean(g_pointer_bit_trylock)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 }
536