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
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 #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 */
77 static void
g_futex_wait(const volatile gint * address,gint value)78 g_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 */
95 static void
g_futex_wake(const volatile gint * address)96 g_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) */
104 typedef struct
105 {
106 const volatile gint *address;
107 gint ref_count;
108 GCond wait_queue;
109 } WaitAddress;
110
111 static WaitAddress *
g_futex_find_address(const volatile gint * address)112 g_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
127 static void
g_futex_wait(const volatile gint * address,gint value)128 g_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
160 static void
g_futex_wake(const volatile gint * address)161 g_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
179 static 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 **/
208 void
g_bit_lock(volatile gint * address,gint lock_bit)209 g_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, 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 **/
280 gboolean
g_bit_trylock(volatile gint * address,gint lock_bit)281 g_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 **/
320 void
g_bit_unlock(volatile gint * address,gint lock_bit)321 g_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 */
368 static const volatile gint *
g_futex_int_address(const volatile void * address)369 g_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 **/
399 void
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 (g_futex_int_address (address), (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 **/
gboolean(g_pointer_bit_trylock)470 gboolean
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 **/
515 void
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 (g_futex_int_address (address));
538 }
539 }
540 }
541