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