1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
|
; Under MIT license, see /LICENSE.txt
; Cheat sheet for Linux' x86_64 calling convention:
;
; - free to overwrite (caller should save them):
; rax, rcx, rdx, rsi, rdi, r8-r11, xmm0-xmm15
; - caller expects be kept (callee should save them):
; rbx, rbp, r12-r15
;
; - for passing paramters to functions:
; rdi, rsi, rdx, rcx, r8, r9, xmm0-xmm7
; - for getting return values from functions:
; rax, rdx, xmm0
;
; - for passing parameters to syscalls:
; rax, rdi, rsi, rdx, r10, r8, r9
; - for getting return values from syscalls:
; rax, rdx
; - overwritten by syscalls (all others preserved):
; rcx, r11
section .text
; Relevant system call IDs
%define SYS_GETTID 186
%define SYS_FUTEX 202
; Relevant operations for futex
%define FUTEX_LOCK_PI 6
%define FUTEX_PRIVATE_FLAG 0x80
; Relevant bits for futex dword
%define FUTEX_TID_MASK 0x3fffffff
%define FUTEX_OWNER_DIED 0x40000000
%define FUTEX_WAITERS 0x80000000
; Acquire a lock if possible, or wait until it gets released. Argument:
; rdi: struct{u32,u32,u32}* = handle of lock to acquire
; Returns zero on success, or a standard error code.
global linen_lock_acquire
linen_lock_acquire:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;; Check validity of argument ;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Return EINVAL if rdi is NULL or otherwise invalid
mov eax, -22 ; (EINVAL = -22)
test rdi, rdi
jz acquire_return ; rdi is NULL
; rdi is nonzero, so let's just assume it's a valid pointer;
; if that assumption is wrong we'll get a segmentation fault.
; But we don't yet trust that [rdi] is a valid lock handle!
; To verify this we check the canary value stored at [rdi + 8].
mov ecx, [rdi + 8]
cmp ecx, 0xCAFEBABE
jnz acquire_return
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;; Check ownership of lock ;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Lock owners are identified by their TID; let's find ours.
; The gettid system call simply returns our Linux thread ID.
; See: man 2 gettid
; gettid: rax = system call ID
mov eax, SYS_GETTID
; gettid: rax = gettid()
syscall
; Save a copy of our TID (no need for an error check)
mov edx, eax
; There are four possible ownership situations for the lock,
; which we can distinguish based on the dword value at [rdi]:
; - Case 1: if [rdi] contains zero, then the lock is available.
; - Case 2: if [rdi] has any of its highest 2 bits set, then the
; lock isn't free, and kernel intervention is required.
; - Case 3: if the lower 30 bits of [rdi] contain our TID,
; then we already own it (recursive acquisition).
; - Case 4: if the lower 30 bits of [rdi] contain another TID
; and the high-bit flags aren't set, then we just wait
; until we can acquire the lock using atomic operations
; or, optionally, a futex call (usually more efficient).
; Atomically check whether the lock is owned by another thread,
; and if not, try to take ownership by writing our TID to [rdi].
; if ([rdi] == 0) { [rdi] = edx; goto acquire_success; } else { eax = [rdi]; }
xor eax, eax
lock cmpxchg [rdi], edx
jz acquire_success ; case 1
; The lock isn't free, so let's check how "clean" its state is.
; The following flags are set by the kernel (see futex below):
; - FUTEX_OWNER_DIED: the lock's owner died, so it's actually free
; (but first the kernel needs to clean up)
; - FUTEX_WAITERS: we aren't the only one waiting for this lock
; (so let's sleep until the kernel wakes us up)
; Either way, we need the kernel's help, so jump to the futex call.
test eax, (FUTEX_OWNER_DIED | FUTEX_WAITERS)
jnz acquire_futex ; case 2
; It seems someone has the lock, check who: it may already be us.
; If so, this is a recursive acquisition, good, let's continue.
and eax, FUTEX_TID_MASK
cmp eax, edx
je acquire_success ; case 3
; Someone else has the lock, but we're the only one waiting for it.
; System calls are expensive, so let's try a short spin loop first,
; hoping it'll get released soon. This is arguably unnecessary, as
; it's only beneficial when two threads are more or less "in sync",
; so in most real-world cases you can delete this with no downside.
; Loop counter
mov ecx, 10
acquire_spinloop:
; The "pause" instruction is specially designed for loops like this
; and conserves power. It causes a small delay (makes sense here).
pause
; Atomically check whether the lock is owned by another thread,
; and if not, try to take ownership by writing our TID to [rdi].
; if ([rdi] == 0) { [rdi] = edx; goto acquire_success; } else { eax = [rdi]; }
xor eax, eax
lock cmpxchg [rdi], edx
jz acquire_success
; Decrement loop counter until zero
dec ecx
jnz acquire_spinloop
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;; Let the kernel handle it ;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
acquire_futex:
; The futex system call waits for the dword at an address (rdi)
; changes in a certain way, as described above and in the futex
; manual's section on so-called "priority-inheritance futexes".
; See: man 2 futex
; futex: rdi = uaddr: address of the dword to watch
; futex: rsi = futex_op: which futex operation we want:
; - FUTEX_LOCK_PI: block until lock's owner uses FUTEX_UNLOCK_PI
; - FUTEX_PRIVATE_FLAG: this lock isn't shared with another process
mov esi, (FUTEX_LOCK_PI | FUTEX_PRIVATE_FLAG)
; futex: r10 = timeout: in case we had a deadline (we don't)
xor r10, r10
; futex: rdx = val: ignored when FUTEX_LOCK_PI is used
; futex: r8 = uaddr2: ignored when FUTEX_LOCK_PI is used
; futex: r9 = val3: ignored when FUTEX_LOCK_PI is used
; futex: rax = system call ID
mov eax, SYS_FUTEX
; futex: rax = futex(rdi, rsi, (rdx), r10, (r8), (r9))
syscall
; Sometimes the lock is released after the "lock cmpxchg" instruction
; but just before the futex call. In that case, futex returns EAGAIN.
cmp rax, -11 ; (-EAGAIN)
je acquire_futex
; Any other negative return value means failure
test rax, rax
jnz acquire_return
; Indicate that we made a futex call (see below for why)
xor edx, edx
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;; Update the recursion counter ;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
acquire_success:
; Read the recursion counter (we have the lock: no need for atomics)
mov ecx, [rdi + 4]
; The value in edx depends on how we came to the acquire_success label:
; 1) We jumped here after a successful "lock cmpxchg": edx has our TID
; 2) We finished a successful futex call: edx was set to 0 (see above)
test edx, edx
; Why do we care? Well, in the latter case, the futex call may have been
; necessary because there was a problem (i.e. FUTEX_OWNER_DIED was set),
; in which case the recursion counter is stale and hence must be reset.
; In any other case, whoever released the lock should've reset it already.
cmovz ecx, edx ; ecx = 0
; Increment the recursion counter and write it back to memory
; (if the lock is being used non-recursively, it should be 1)
inc ecx
mov [rdi + 4], ecx
; Lock acquisition was successful, so we'll return 0. In most cases
; eax is already 0; we only need this if the recursion counter > 1.
xor eax, eax
acquire_return:
ret
|
