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
19void __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
54void __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}