1 #include "usr_lib_define.h"
2 #include "pthread_impl.h"
3
4 /* This lock primitive combines a flag (in the sign bit) and a
5 * congestion count (= threads inside the critical section, CS) in a
6 * single int that is accessed through atomic operations. The states
7 * of the int for value x are:
8 *
9 * x == 0: unlocked and no thread inside the critical section
10 *
11 * x < 0: locked with a congestion of x-INT_MIN, including the thread
12 * that holds the lock
13 *
14 * x > 0: unlocked with a congestion of x
15 *
16 * or in an equivalent formulation x is the congestion count or'ed
17 * with INT_MIN as a lock flag.
18 */
19
__lock(volatile int * l)20 _LIBC_TEXT_SECTION void __lock(volatile int *l)
21 {
22 /* fast path: INT_MIN for the lock, +1 for the congestion */
23 int current = a_cas(l, 0, INT_MIN + 1);
24 if (!current) return;
25 /* A first spin loop, for medium congestion. */
26 for (unsigned i = 0; i < 10; ++i) {
27 if (current < 0) current -= INT_MIN + 1;
28 // assertion: current >= 0
29 int val = a_cas(l, current, INT_MIN + (current + 1));
30 if (val == current) return;
31 current = val;
32 }
33 // Spinning failed, so mark ourselves as being inside the CS.
34 current = a_fetch_add(l, 1) + 1;
35 /* The main lock acquisition loop for heavy congestion. The only
36 * change to the value performed inside that loop is a successful
37 * lock via the CAS that acquires the lock. */
38 for (;;) {
39 /* We can only go into wait, if we know that somebody holds the
40 * lock and will eventually wake us up, again. */
41 if (current < 0) {
42 __futexwait(l, current, 1);
43 current -= INT_MIN + 1;
44 }
45 /* assertion: current > 0, the count includes us already. */
46 int val = a_cas(l, current, INT_MIN + current);
47 if (val == current) return;
48 current = val;
49 }
50 }
51
__unlock(volatile int * l)52 _LIBC_TEXT_SECTION void __unlock(volatile int *l)
53 {
54 /* Check l[0] to see if we are multi-threaded. */
55 if (l[0] < 0) {
56 if (a_fetch_add(l, -(INT_MIN + 1)) != (INT_MIN + 1)) {
57 __wake(l, 1, 1);
58 }
59 }
60 }
61