include/sa/sa_peer.h

filter: Statementstmt 94.1% 81 / 86 Branchbran 60.4% 52 / 86 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 77.3% 133 / 172 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/region.xs ↑ Summary xs/rate.xs »
1 #ifndef SA_PEER_H
2 #define SA_PEER_H
3  
4 /* sa_peer.h - who is using this region, and how a reader proves one of them
5 * has died. Perl-free.
6 *
7 * ---- the problem a timeout cannot solve -------------------------------------
8 *
9 * A publisher reserves a sequence and dies before committing it. Every reader
10 * that reaches that sequence is now stuck: it cannot deliver a record that was
11 * never written, and it must not skip one that is merely late, because a live
12 * publisher on a loaded machine can lose the CPU for longer than any bound
13 * worth setting. Wait too little and live records are thrown away; wait too
14 * much and one dead process stalls every reader.
15 *
16 * A timeout picks one of those and is wrong the rest of the time. So this asks
17 * a different question - not "has it been long enough" but "is that process
18 * still there" - and it takes TWO answers, both of which must agree.
19 *
20 * ---- proof one: the process is gone ----------------------------------------
21 *
22 * kill(pid, 0) asks without signalling. ESRCH is the ONLY answer that means
23 * gone. EPERM means the process exists and belongs to somebody else, and
24 * reading "not mine" as "dead" is how a live publisher's record gets discarded.
25 * Where there is no kill at all - Windows - the answer is ALIVE, conservatively,
26 * which pushes the whole decision onto proof two. That is the safe direction:
27 * it costs latency on one record, never data.
28 *
29 * ---- proof two: it has made no progress ------------------------------------
30 *
31 * A pid check cannot see a process that is alive but wedged - deadlocked,
32 * stopped, or stuck in the kernel - and such a process passes kill(0) for ever
33 * while never finishing its record. So a peer also carries a heartbeat, bumped
34 * on publishes AND on drains so an idle-but-live peer still ticks, and a reader
35 * requires it to have stood still for the grace period.
36 *
37 * Both must hold. A recycled pid therefore makes this SKIP a hole it could have
38 * filled, which costs one stalled record, where the reverse would cost a live
39 * one. The asymmetry is deliberate.
40 *
41 * ---- the epoch, which answers most cases with no syscall at all ------------
42 *
43 * A peer slot is reused. A claim naming slot 7 means nothing unless it also
44 * says WHICH occupant of slot 7, so every claim carries the epoch, and an epoch
45 * that no longer matches is a claim from a process that has already gone -
46 * known dead immediately, with no kill and no waiting.
47 *
48 * Needs sa_arena.h.
49 */
50  
51 #include "sa/sa_arena.h"
52  
53 #ifdef _WIN32
54 # include <windows.h>
55 #else
56 # include <signal.h>
57 # include <errno.h>
58 # include <unistd.h>
59 # include <time.h>
60 #endif
61  
62 /* A claim packs the peer slot and its epoch into one word, so a publisher
63 * announces its identity with a single store and a reader reads it with a
64 * single load. Zero is "nobody", which is what an untouched slot holds. */
65 #define SA_CLAIM(peer, epoch) \
66 (((uint64_t)((peer) + 1) << 32) | (uint64_t)(epoch))
67 #define SA_CLAIM_PEER(c) ((uint32_t)(((c) >> 32) - 1))
68 #define SA_CLAIM_EPOCH(c) ((uint32_t)((c) & 0xFFFFFFFFu))
69  
70 /* ---- getpid IS A SYSCALL, AND THIS IS ON THE PUBLISH PATH -------------------
71 *
72 * `sa_peer_join` runs on every published record, and its fast path has to know
73 * which process it is before it can decide it has nothing to do. glibc cached
74 * getpid until 2.25 and does not any more, so on Linux that fast path was a
75 * syscall per record - in a dist whose first line is "without a syscall".
76 *
77 * So the pid is cached, and the cache is invalidated by the one event that can
78 * make it wrong: a fork. pthread_atfork is what says so, and Makefile.PL probes
79 * for it rather than assuming - where it is missing the cache is simply not
80 * used and every call is the real thing, which is slower and always correct.
81 */
82 #if defined(SA_HAVE_ATFORK) && !defined(_WIN32)
83 # include <pthread.h>
84 static volatile uint64_t sa_pid_cache = 0;
85 27 static void sa_pid_forgot(void) { sa_pid_cache = 0; }
86 static int sa_pid_armed = 0;
87  
88 827554 static uint64_t sa_getpid(void) {
89 827554 uint64_t p = sa_pid_cache;
90 827554 ▶ if (p) return p;
Branch: 1 branch
BranchTrueFalseTotal
if (p) return p; 827482 72 827554
91 72 ▶ if (!sa_pid_armed) {
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_pid_armed) { 45 27 72
92 45 sa_pid_armed = 1;
93 /* The CHILD handler, and only that one: the parent's pid is unchanged
94 * by a fork, so clearing it there would throw the cache away on every
95 * fork for nothing. */
96 45 (void)pthread_atfork(NULL, NULL, sa_pid_forgot);
97 }
98 72 p = (uint64_t)getpid();
99 72 sa_pid_cache = p;
100 72 return p;
101 }
102 #else
103 static uint64_t sa_getpid(void) {
104 #ifdef _WIN32
105 return (uint64_t)GetCurrentProcessId();
106 #else
107 return (uint64_t)getpid();
108 #endif
109 }
110 #endif
111  
112 /* Is that process still running?
113 *
114 * ESRCH is the only answer that means gone. On Windows a pid that cannot be
115 * opened is answered ALIVE rather than dead, because OpenProcess fails for
116 * reasons that have nothing to do with the process existing, and the staleness
117 * proof is the one that has to carry it there. */
118 165145 static int sa_pid_alive(uint64_t pid) {
119 #ifdef _WIN32
120 HANDLE h;
121 DWORD code = 0;
122 if (!pid) return 0;
123 h = OpenProcess(PROCESS_QUERY_LIMITED_INFORMATION, FALSE, (DWORD)pid);
124 if (!h) return 1; /* conservatively alive */
125 if (GetExitCodeProcess(h, &code)) {
126 CloseHandle(h);
127 return code == STILL_ACTIVE ? 1 : 0;
128 }
129 CloseHandle(h);
130 return 1;
131 #else
132 165145 ▶ if (!pid) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!pid) return 0; 0 165145 165145
133 165145 ▶ if (kill((pid_t)pid, 0) == 0) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (kill((pid_t)pid, 0) == 0) return 1; 165129 16 165145
134 16 return (errno == ESRCH) ? 0 : 1; /* EPERM means ALIVE */
135 #endif
136 }
137  
138 /* Take a peer slot for this process. Idempotent per pid: a fork child calls it
139 * again and gets its OWN slot, because it is a different process and a claim
140 * naming its parent would be attributed to the wrong one.
141 *
142 * Returns 1 when this process has a slot, 0 when the table is full - in which
143 * case publishing still works and only the crash attribution is lost, which is
144 * the right thing to degrade. */
145 3455 static int sa_peer_join(sa_region *r) {
146 #if !SA_HAVE_ATOMICS
147 (void)r;
148 return 0;
149 #else
150 sa_header *h;
151 sa_peer *peers;
152 3455 uint64_t me = sa_getpid();
153 uint32_t i;
154  
155 3455 ▶ if (!r || !r->map.base) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!r || !r->map.base) return 0; 3455 0 3455
if (!r || !r->map.base) return 0; 0 3455 3455
156 3455 ▶ if (r->peer_pid == me && r->peer_idx >= 0) return 1;
Branch: 2 branches
BranchTrueFalseTotal
if (r->peer_pid == me && r->peer_idx >= 0) return 1; 3424 31 3455
if (r->peer_pid == me && r->peer_idx >= 0) return 1; 3424 0 3424
157  
158 31 h = r->hdr;
159 31 peers = SA_PEERS(r->map.base, h);
160  
161 50 ▶ for (i = 0; i < h->peers_max; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < h->peers_max; i++) { 50 0 50
162 50 uint32_t st = sa_at_load32_acq(&peers[i].state);
163 50 ▶ if (st == SA_P_LIVE) {
Branch: 1 branch
BranchTrueFalseTotal
if (st == SA_P_LIVE) { 19 31 50
164 /* Already ours from a previous join in this same process? */
165 19 ▶ if (sa_at_load64_acq(&peers[i].pid) == me) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load64_acq(&peers[i].pid) == me) { 0 19 19
166 0 r->peer_idx = (int)i;
167 0 r->peer_epoch = sa_at_load32_acq(&peers[i].epoch);
168 0 r->peer_pid = me;
169 0 return 1;
170 }
171 19 continue;
172 }
173 /* FREE or REAPED. Winning the CAS is what makes the slot ours. */
174 31 ▶ if (!sa_at_cas32(&peers[i].state, st, SA_P_LIVE)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_at_cas32(&peers[i].state, st, SA_P_LIVE)) continue; 0 31 31
175  
176 31 sa_at_store64_rel(&peers[i].want, 0);
177 31 sa_at_store64_rel(&peers[i].heartbeat, 1);
178 31 sa_at_store64_rel(&peers[i].pid, me);
179 /* The epoch is bumped LAST and is what a claim is validated against, so
180 * a claim written by the previous occupant can never be mistaken for
181 * one of ours. */
182 31 sa_at_store32_rel(&peers[i].epoch,
183 31 sa_at_load32_acq(&peers[i].epoch) + 1);
184  
185 31 r->peer_idx = (int)i;
186 31 r->peer_epoch = sa_at_load32_acq(&peers[i].epoch);
187 31 r->peer_pid = me;
188 31 ▶ if (i + 1 > sa_at_load32_acq(&h->peers_used))
Branch: 1 branch
BranchTrueFalseTotal
if (i + 1 > sa_at_load32_acq(&h->peers_used)) 31 0 31
189 31 sa_at_store32_rel(&h->peers_used, i + 1);
190 31 return 1;
191 }
192 0 return 0;
193 #endif
194 }
195  
196 464 static void sa_peer_beat(sa_region *r) {
197 #if SA_HAVE_ATOMICS
198 464 ▶ if (r && r->peer_idx >= 0 && r->map.base) {
Branch: 3 branches
BranchTrueFalseTotal
if (r && r->peer_idx >= 0 && r->map.base) { 464 0 464
if (r && r->peer_idx >= 0 && r->map.base) { 464 0 464
if (r && r->peer_idx >= 0 && r->map.base) { 464 0 464
199 464 sa_peer *p = &SA_PEERS(r->map.base, r->hdr)[r->peer_idx];
200 /* One writer per row, so a load and a release store: a reader only
201 * ever asks whether it MOVED. */
202 464 sa_at_store64_rel(&p->heartbeat, sa_at_load64_acq(&p->heartbeat) + 1);
203 }
204 #else
205 (void)r;
206 #endif
207 464 }
208  
209 1 static void sa_peer_leave(sa_region *r) {
210 #if SA_HAVE_ATOMICS
211 1 ▶ if (r && r->peer_idx >= 0 && r->map.base
Branch: 3 branches
BranchTrueFalseTotal
if (r && r->peer_idx >= 0 && r->map.base 1 0 1
if (r && r->peer_idx >= 0 && r->map.base 1 0 1
if (r && r->peer_idx >= 0 && r->map.base 1 0 1
212 1 ▶ && r->peer_pid == sa_getpid()) {
Branch: 1 branch
BranchTrueFalseTotal
&& r->peer_pid == sa_getpid()) { 1 0 1
213 1 sa_peer *p = &SA_PEERS(r->map.base, r->hdr)[r->peer_idx];
214 1 sa_at_store32_rel(&p->state, SA_P_FREE);
215 1 r->peer_idx = -1;
216 }
217 #else
218 (void)r;
219 #endif
220 1 }
221  
222 /* THE DECISION. Is the peer named by this claim dead, and has it stopped?
223 *
224 * `hb0` is the heartbeat read when the wait began; the caller has already
225 * waited the grace period. Returns 1 when both proofs hold and the caller may
226 * fill the hole.
227 */
228 2 static int sa_peer_is_dead(sa_region *r, uint64_t claim, uint64_t hb0) {
229 #if !SA_HAVE_ATOMICS
230 (void)r; (void)claim; (void)hb0;
231 return 0;
232 #else
233 sa_peer *peers;
234 uint32_t idx, epoch;
235  
236 2 ▶ if (!r || !r->map.base) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!r || !r->map.base) return 0; 2 0 2
if (!r || !r->map.base) return 0; 0 2 2
237 2 ▶ if (!claim) return 0; /* nobody claimed it */
Branch: 1 branch
BranchTrueFalseTotal
if (!claim) return 0; /* nobody claimed it */ 0 2 2
238  
239 2 idx = SA_CLAIM_PEER(claim);
240 2 epoch = SA_CLAIM_EPOCH(claim);
241 2 ▶ if (idx >= r->hdr->peers_max) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (idx >= r->hdr->peers_max) return 0; 0 2 2
242  
243 2 peers = SA_PEERS(r->map.base, r->hdr);
244  
245 /* The cheap proof first, and it needs no syscall: a slot whose epoch has
246 * moved on belongs to a different process than the one that wrote this
247 * claim, so the writer is already gone. */
248 2 ▶ if (sa_at_load32_acq(&peers[idx].epoch) != epoch) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&peers[idx].epoch) != epoch) return 1; 0 2 2
249 2 ▶ if (sa_at_load32_acq(&peers[idx].state) != SA_P_LIVE) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&peers[idx].state) != SA_P_LIVE) return 1; 0 2 2
250  
251 /* Both of the expensive ones, and BOTH must hold. */
252 2 ▶ if (sa_at_load64_acq(&peers[idx].heartbeat) != hb0) return 0; /* moved */
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load64_acq(&peers[idx].heartbeat) != hb0) return 0; /* moved */ 0 2 2
253 2 ▶ if (sa_pid_alive(sa_at_load64_acq(&peers[idx].pid))) return 0; /* there */
Branch: 1 branch
BranchTrueFalseTotal
if (sa_pid_alive(sa_at_load64_acq(&peers[idx].pid))) return 0; /* there */ 1 1 2
254 1 return 1;
255 #endif
256 }
257  
258 /* The heartbeat of the peer a claim names, for the caller to compare later. */
259 5 static uint64_t sa_peer_hb(sa_region *r, uint64_t claim) {
260 #if !SA_HAVE_ATOMICS
261 (void)r; (void)claim;
262 return 0;
263 #else
264 uint32_t idx;
265 5 ▶ if (!r || !r->map.base || !claim) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (!r || !r->map.base || !claim) return 0; 5 0 5
if (!r || !r->map.base || !claim) return 0; 5 0 5
if (!r || !r->map.base || !claim) return 0; 1 4 5
266 4 idx = SA_CLAIM_PEER(claim);
267 4 ▶ if (idx >= r->hdr->peers_max) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (idx >= r->hdr->peers_max) return 0; 0 4 4
268 4 return sa_at_load64_acq(&SA_PEERS(r->map.base, r->hdr)[idx].heartbeat);
269 #endif
270 }
271  
272 /* Mark a proven-dead peer reaped. Exactly one caller wins, which is what keeps
273 * the accounting exact when two readers reach the same hole together. */
274 1 static int sa_peer_reap(sa_region *r, uint64_t claim) {
275 #if !SA_HAVE_ATOMICS
276 (void)r; (void)claim;
277 return 0;
278 #else
279 uint32_t idx;
280 1 ▶ if (!r || !r->map.base || !claim) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (!r || !r->map.base || !claim) return 0; 1 0 1
if (!r || !r->map.base || !claim) return 0; 1 0 1
if (!r || !r->map.base || !claim) return 0; 0 1 1
281 1 idx = SA_CLAIM_PEER(claim);
282 1 ▶ if (idx >= r->hdr->peers_max) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (idx >= r->hdr->peers_max) return 0; 0 1 1
283 1 return sa_at_cas32(&SA_PEERS(r->map.base, r->hdr)[idx].state,
284 SA_P_LIVE, SA_P_REAPED);
285 #endif
286 }
287  
288 /* Does any DEAD peer have a reservation it never committed?
289 *
290 * The residual window: a publisher that died between taking a sequence and
291 * announcing which peer it was leaves a hole with no usable claim. This cannot
292 * say WHICH sequence such a peer was writing, only that one of them was, which
293 * is enough to stop waiting for a record nobody will ever finish. */
294 1 static int sa_peer_any_dead_pending(sa_region *r) {
295 #if !SA_HAVE_ATOMICS
296 (void)r;
297 return 0;
298 #else
299 sa_peer *peers;
300 uint32_t i, used;
301 1 ▶ if (!r || !r->map.base) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!r || !r->map.base) return 0; 1 0 1
if (!r || !r->map.base) return 0; 0 1 1
302 1 peers = SA_PEERS(r->map.base, r->hdr);
303 1 used = sa_at_load32_acq(&r->hdr->peers_used);
304 1 ▶ if (used > r->hdr->peers_max) used = r->hdr->peers_max;
Branch: 1 branch
BranchTrueFalseTotal
if (used > r->hdr->peers_max) used = r->hdr->peers_max; 0 1 1
305 3 ▶ for (i = 0; i < used; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < used; i++) { 2 1 3
306 2 ▶ if (sa_at_load32_acq(&peers[i].state) != SA_P_LIVE) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&peers[i].state) != SA_P_LIVE) continue; 0 2 2
307 2 ▶ if (!sa_at_load64_acq(&peers[i].want)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_at_load64_acq(&peers[i].want)) continue; 1 1 2
308 1 ▶ if (!sa_pid_alive(sa_at_load64_acq(&peers[i].pid))) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_pid_alive(sa_at_load64_acq(&peers[i].pid))) return 1; 0 1 1
309 }
310 1 return 0;
311 #endif
312 }
313  
314 #endif /* SA_PEER_H */
« xs/region.xs ↑ Summary xs/rate.xs »