include/sa/sa_hash.h

filter: Statementstmt 88.2% 196 / 222 Branchbran 67.5% 123 / 182 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 78.9% 319 / 404 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/rate.xs ↑ Summary include/sa/sa_cuckoo.h »
1 #ifndef SA_HASH_H
2 #define SA_HASH_H
3  
4 /* sa_hash.h - a fixed-capacity map several processes share. Perl-free.
5 *
6 * Open addressing with linear probing, in one carved region. Readers take no
7 * lock at all; writers take one of a stripe of spinlocks, so two writers
8 * touching different keys almost never meet.
9 *
10 * ---- fixed capacity, and no growth ------------------------------------------
11 *
12 * The table is sized once and never rehashes. That is not a simplification to
13 * be fixed later: growing a table several processes are reading means moving
14 * entries other processes are mid-probe on, and the only safe ways to do that
15 * are to stop the world or to keep both tables alive until every reader has
16 * left. Neither belongs in something whose whole point is that a read is a hash
17 * and a compare.
18 *
19 * So a full table REFUSES a new key. `used` and `capacity` are in the stats,
20 * and a caller that reaches the ceiling wanted a bigger table.
21 *
22 * ---- tombstones, and what deleting costs -----------------------------------
23 *
24 * A deleted entry becomes a tombstone rather than empty, because an empty slot
25 * stops a probe and a probe that stops early cannot find a key that was placed
26 * past it. Tombstones are reused by the next insert that probes over them, but
27 * they are never swept: a workload that deletes constantly will fill the table
28 * with them and start refusing keys while `used` looks low. `tombstones` is in
29 * the stats so that is visible rather than mysterious.
30 *
31 * ---- reading without a lock -------------------------------------------------
32 *
33 * A value is read while another process may be replacing it, so each slot
34 * carries a VERSION: odd while being written, even when settled, and a reader
35 * takes it before and after copying. Same discipline as the ring's two
36 * sequence words and for the same reason - and, as there, a release store is
37 * not enough on its own. It orders what came before it and says nothing about
38 * the writes that follow, so the barriers are explicit. Getting that wrong
39 * produces whole, plausible values that belong to neither the old entry nor the
40 * new one, which is the hardest kind of bug to see.
41 *
42 * A reader that keeps losing the race gives up after a bounded number of tries
43 * and counts a `busy`. It does NOT report the key as missing: absent and
44 * could-not-read are different answers, and conflating them is how a caller
45 * ends up believing a key was deleted when a writer was simply mid-update.
46 *
47 * ---- expiry is per key, lazy, and by a wall clock ---------------------------
48 *
49 * A slot carries a deadline: 0 for never, otherwise a millisecond on the same
50 * clock the cache uses (sa_now_ms). A WALL clock rather than a monotonic one,
51 * because the deadline is written by one process and read by another, and the
52 * only clock two processes certainly agree on is the machine's. A step in it
53 * moves every deadline together, which costs at worst one round of early or
54 * late expiry.
55 *
56 * LAZY, not swept. A read that lands on an expired entry treats it as absent
57 * and turns it into a tombstone in passing, so the space comes back without a
58 * background sweeper and without a lock on the read path for the common case.
59 * An expiry a caller never reads again sits until an insert probes over it,
60 * exactly as a delete does. `expired` counts the ones collected this way, so a
61 * table full of stale keys is visible rather than mysterious.
62 *
63 * A TOMBSTONE ON EXPIRY IS A WRITE, so the reader takes the stripe lock to do
64 * it - and only to do it. A live-but-current entry is still read with no lock
65 * at all; the lock is paid once, by whoever first notices a key has died.
66 *
67 * The point of all this is the case a plain map handles wrong: a denylist, a
68 * nonce store, a dedup window. Without a deadline every caller writes its own
69 * `> time` check and its own delete, and the failure is always the same one -
70 * forgetting the check, which turns every ban permanent.
71 *
72 * Needs sa_arena.h.
73 */
74  
75 #include "sa/sa_arena.h"
76 #include "sa/sa_time.h"
77  
78 #define SA_HASH_MAGIC 0x5048534Du /* 'M','S','H','P' little-endian */
79  
80 /* slot states. EMPTY stops a probe; DEAD does not. */
81 #define SA_H_EMPTY 0u
82 #define SA_H_LIVE 1u
83 #define SA_H_DEAD 2u
84  
85 /* what a lookup answers */
86 #define SA_H_HIT 0
87 #define SA_H_MISS 1
88 #define SA_H_BUSY 2
89  
90 /* what a store answers */
91 #define SA_H_OK 1
92 #define SA_H_FULL 0
93 #define SA_H_TOOBIG (-1)
94 #define SA_H_NOTNUM (-2) /* incr on an entry that is not a counter */
95 #define SA_H_WBUSY (-3) /* the stripe stayed held: try again */
96  
97 /* FULL MEANS STOP AND BUSY MEANS TRY AGAIN, and a writer refused for a held
98 * stripe is the second one. Until 0.14 it answered SA_H_FULL, so "the table
99 * has no room for this key" and "somebody else was mid-write on this stripe
100 * and I gave up" arrived as the same value. A caller cannot act on that: the
101 * first says the table is too small, the second says do it again.
102 *
103 * AND IT WAS COUNTED NOWHERE. `full` is incremented where the probe finds no
104 * slot, which this refusal never reached, so `stats` showed a clean map while
105 * writes went missing. The only evidence was a total that came up short, which
106 * is how both of these were found and neither was diagnosed from the stats: a
107 * FreeBSD smoker read 38 where it asked for 40, an Alpine one 999 of a
108 * thousand, in a table of 64 slots holding six keys. Nothing was full, and
109 * nothing said so.
110 *
111 * `incr` returns the new value or undef, so a refusal there is a count that
112 * did not happen. It is reported now - the return value, and `busy` - because
113 * a bounded wait can always be beaten by enough contenders, and a library that
114 * cannot promise "never refused" must promise "never silently". */
115  
116 /* How many times a reader retries a slot whose writer is mid-update before it
117 * gives up and counts a busy. A writer holds a slot odd for one memcpy, so
118 * this is generous by orders of magnitude; the bound exists so a writer that
119 * died mid-update cannot wedge a reader for ever. */
120 #define SA_HASH_SPIN 10000
121  
122 typedef struct {
123 volatile uint32_t state; /* SA_H_* */
124 volatile uint32_t version; /* odd = being written */
125 volatile uint32_t klen;
126 volatile uint32_t vlen;
127 volatile uint64_t tag; /* the hash, so most probes skip the memcmp */
128 volatile uint64_t expires; /* ms wall clock; 0 = never */
129 char bytes[1]; /* key then value, slot_size in total */
130 } sa_hash_slot;
131  
132 typedef struct {
133 volatile uint32_t magic; /* published LAST at init */
134 uint32_t slot_size;
135 uint64_t nslots;
136 uint64_t slots_off; /* from the MAP's base */
137 volatile uint64_t used; /* live entries */
138 volatile uint64_t tombstones;
139 volatile uint64_t busy; /* gave up: a read mid-update, or a write
140 * whose stripe stayed held */
141 volatile uint64_t full; /* stores refused for want of room */
142 volatile uint64_t expired; /* entries collected because they lapsed */
143 uint32_t serialise; /* values are Struct::Codec's encoding */
144 uint32_t pad;
145 volatile unsigned char locks[SA_LOCK_STRIPES];
146 } sa_hash_hdr;
147  
148 #ifndef SA_HASH_FWD
149 #define SA_HASH_FWD
150 typedef struct sa_hash sa_hash;
151 #endif
152 struct sa_hash {
153 sa_region *arena;
154 sa_hash_hdr *hdr;
155 char *slots;
156 uint32_t slot_size;
157 uint64_t nslots;
158 uint64_t pair_max; /* key + value that fits one slot */
159 uint32_t serialise; /* copied out of the header at bind */
160 };
161  
162 #define SA_HSLOT_AT(m, i) \
163 ((sa_hash_slot *)((m)->slots + (size_t)((i) % (m)->nslots) * (m)->slot_size))
164  
165 930 static uint64_t sa_hash_capacity(uint32_t slot_size) {
166 930 uint64_t hdr = (uint64_t)sizeof(sa_hash_slot) - 1;
167 930 ▶ return slot_size > hdr ? (uint64_t)slot_size - hdr : 0;
Branch: 1 branch
BranchTrueFalseTotal
return slot_size > hdr ? (uint64_t)slot_size - hdr : 0; 930 0 930
168 }
169  
170 622 static uint64_t sa_hash_bytes(uint64_t nslots, uint32_t slot_size) {
171 622 return sa_align_up((uint64_t)sizeof(sa_hash_hdr))
172 622 + nslots * (uint64_t)slot_size;
173 }
174  
175 /* Attach to a map in a carved region, initialising it if nobody has yet. The
176 * init race takes the same answer as everywhere else: whoever finds magic unset
177 * writes the header and stores magic last, and the rest wait bounded. */
178 /* `serialise` is 0, 1 or SA_SER_ANY; see sa_format.h. */
179 312 static sa_hash *sa_hash_bind(sa_region *arena, sa_reg *e,
180 uint64_t nslots, uint32_t slot_size,
181 int serialise, int *err)
182 {
183 #if !SA_HAVE_ATOMICS
184 (void)arena; (void)e; (void)nslots; (void)slot_size; (void)serialise;
185 if (err) *err = SA_E_NOATOMICS;
186 return NULL;
187 #else
188 sa_hash *m;
189 sa_hash_hdr *h;
190 uint64_t hash;
191  
192 312 ▶ if (err) *err = SA_E_OK;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_OK; 312 0 312
193 312 ▶ if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; }
Branch: 3 branches
BranchTrueFalseTotal
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 312 0 312
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 312 312
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
194  
195 312 h = (sa_hash_hdr *)sa_ptr_len(arena, e->off, sizeof(sa_hash_hdr));
196 312 ▶ if (!h) { if (err) *err = SA_E_NOENT; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!h) { if (err) *err = SA_E_NOENT; return NULL; } 0 312 312
if (!h) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
197  
198 312 ▶ if (sa_at_load32_acq(&h->magic) != SA_HASH_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&h->magic) != SA_HASH_MAGIC) { 310 2 312
199 310 hash = sa_at_fnv(e->name, strlen(e->name));
200 310 ▶ if (sa_at_lock(h->locks, hash)) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_lock(h->locks, hash)) { 310 0 310
201 310 ▶ if (sa_at_load32_acq(&h->magic) != SA_HASH_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&h->magic) != SA_HASH_MAGIC) { 310 0 310
202 310 ▶ if (!nslots || !slot_size
Branch: 2 branches
BranchTrueFalseTotal
if (!nslots || !slot_size 310 0 310
if (!nslots || !slot_size 310 0 310
203 310 ▶ || sa_hash_capacity(slot_size) == 0
Branch: 1 branch
BranchTrueFalseTotal
|| sa_hash_capacity(slot_size) == 0 310 0 310
204 310 ▶ || sa_hash_bytes(nslots, slot_size) > e->len) {
Branch: 1 branch
BranchTrueFalseTotal
|| sa_hash_bytes(nslots, slot_size) > e->len) { 0 310 310
205 0 sa_at_unlock(h->locks, hash);
206 0 ▶ if (err) *err = SA_E_FULL;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_FULL; 0 0 0
207 0 return NULL;
208 }
209 310 memset((void *)h, 0, (size_t)sizeof(sa_hash_hdr));
210 310 h->slot_size = slot_size;
211 310 h->nslots = nslots;
212 310 ▶ h->serialise = serialise > 0 ? 1u : 0u;
Branch: 1 branch
BranchTrueFalseTotal
h->serialise = serialise > 0 ? 1u : 0u; 2 308 310
213 310 h->slots_off = sa_align_up((uint64_t)sizeof(sa_hash_hdr));
214 310 sa_at_store32_rel(&h->magic, SA_HASH_MAGIC);
215 }
216 310 sa_at_unlock(h->locks, hash);
217 }
218 310 ▶ if (!sa_wait_magic32(&h->magic, SA_HASH_MAGIC)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_wait_magic32(&h->magic, SA_HASH_MAGIC)) { 0 310 310
219 0 ▶ if (err) *err = SA_E_MAGIC;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_MAGIC; 0 0 0
220 0 return NULL;
221 }
222 }
223  
224 /* THE GEOMETRY IN THE HEADER IS ALSO SOMEBODY ELSE'S NUMBER.
225 *
226 * The branch above only checks a size when this process is the one doing
227 * the INITIALISING. A process that finds the magic already set reads the
228 * shape out of the shared header and believed it, so a header claiming
229 * four billion slots put every later read past the end of the mapping.
230 * sa_reg_ok makes `len` trustworthy; this makes the shape trustworthy. */
231  
232 312 ▶ if ((nslots && h->nslots != nslots)
Branch: 2 branches
BranchTrueFalseTotal
if ((nslots && h->nslots != nslots) 312 0 312
if ((nslots && h->nslots != nslots) 312 0 312
233 312 ▶ || (slot_size && h->slot_size != slot_size)) {
Branch: 2 branches
BranchTrueFalseTotal
|| (slot_size && h->slot_size != slot_size)) { 312 0 312
|| (slot_size && h->slot_size != slot_size)) { 0 312 312
234 0 ▶ if (err) *err = SA_E_NAME;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_NAME; 0 0 0
235 0 return NULL;
236 }
237 312 ▶ if (serialise >= 0 && h->serialise != (serialise ? 1u : 0u)) {
Branch: 3 branches
BranchTrueFalseTotal
if (serialise >= 0 && h->serialise != (serialise ? 1u : 0u)) { 309 3 312
if (serialise >= 0 && h->serialise != (serialise ? 1u : 0u)) { 3 306 309
if (serialise >= 0 && h->serialise != (serialise ? 1u : 0u)) { 1 308 309
238 1 ▶ if (err) *err = SA_E_SHAPE;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_SHAPE; 1 0 1
239 1 return NULL;
240 }
241  
242 311 m = (sa_hash *)calloc(1, sizeof(sa_hash));
243 311 ▶ if (!m) { if (err) *err = SA_E_NOMEM; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!m) { if (err) *err = SA_E_NOMEM; return NULL; } 0 311 311
if (!m) { if (err) *err = SA_E_NOMEM; return NULL; } 0 0 0
244 311 m->arena = arena;
245 311 m->hdr = h;
246 311 m->slots = (char *)h + (size_t)h->slots_off;
247 311 m->slot_size = h->slot_size;
248 311 m->nslots = h->nslots;
249 311 m->pair_max = sa_hash_capacity(h->slot_size);
250 311 m->serialise = h->serialise;
251 311 return m;
252 #endif
253 }
254  
255 311 static void sa_hash_free(sa_hash *m) { free(m); }
256  
257 /* ---- reading, without a lock ----------------------------------------------- */
258  
259 /* Look `key` up and copy its value into `out`.
260 *
261 * SA_H_HIT with *vlen set, SA_H_MISS, or SA_H_BUSY when a writer held the slot
262 * odd for longer than a reader was willing to wait. BUSY is deliberately not
263 * MISS: telling a caller a key is absent when it is merely being rewritten is
264 * how a cache turns an update into a delete.
265 */
266 /* A live slot's deadline has passed. `now` of 0 means "do not check", which is
267 * how a caller that never set a TTL avoids reading the clock at all. */
268 #define SA_H_EXPIRED(s, now) \
269 ((now) && (s)->expires && (now) >= (s)->expires)
270  
271 /* Find the slot this key belongs in, under the caller's lock. Returns the slot
272 * to use, or NULL when the table is full.
273 *
274 * `*found` is 0 for a fresh slot (empty or tombstone, not counted in `used`),
275 * 1 for a live current match, and 2 for a live match whose deadline has passed
276 * - which is still counted in `used` but is logically absent, so the caller
277 * refreshes it in place rather than allocating, and never increments `used`. */
278 2697 static sa_hash_slot *sa_hash_place(sa_hash *m, const char *key, uint32_t klen,
279 uint64_t tag, uint64_t now, int *found)
280 {
281 #if !SA_HAVE_ATOMICS
282 (void)m; (void)key; (void)klen; (void)tag; (void)now; (void)found;
283 return NULL;
284 #else
285 2697 uint64_t i, start = tag % m->nslots;
286 2697 sa_hash_slot *reuse = NULL;
287  
288 2697 *found = 0;
289 3007 ▶ for (i = 0; i < m->nslots; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < m->nslots; i++) { 2989 18 3007
290 2989 sa_hash_slot *s = SA_HSLOT_AT(m, start + i);
291 2989 uint32_t st = sa_at_load32_acq(&s->state);
292  
293 2989 ▶ if (st == SA_H_EMPTY) return reuse ? reuse : s;
Branch: 2 branches
BranchTrueFalseTotal
if (st == SA_H_EMPTY) return reuse ? reuse : s; 878 2111 2989
if (st == SA_H_EMPTY) return reuse ? reuse : s; 11 867 878
294 2111 ▶ if (st == SA_H_DEAD) {
Branch: 1 branch
BranchTrueFalseTotal
if (st == SA_H_DEAD) { 12 2099 2111
295 /* Remember the first tombstone, but keep probing: the key may be
296 * live further along, and inserting a second copy of it here would
297 * leave two entries that disagree. */
298 12 ▶ if (!reuse) reuse = s;
Branch: 1 branch
BranchTrueFalseTotal
if (!reuse) reuse = s; 11 1 12
299 12 continue;
300 }
301 2099 ▶ if (sa_at_load64_acq(&s->tag) == tag
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load64_acq(&s->tag) == tag 1801 298 2099
302 1801 ▶ && s->klen == klen
Branch: 1 branch
BranchTrueFalseTotal
&& s->klen == klen 1801 0 1801
303 1801 ▶ && memcmp(s->bytes, key, klen) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
&& memcmp(s->bytes, key, klen) == 0) { 1801 0 1801
304 1801 ▶ *found = SA_H_EXPIRED(s, now) ? 2 : 1;
Branch: 3 branches
BranchTrueFalseTotal
*found = SA_H_EXPIRED(s, now) ? 2 : 1; 705 1096 1801
*found = SA_H_EXPIRED(s, now) ? 2 : 1; 705 0 705
*found = SA_H_EXPIRED(s, now) ? 2 : 1; 705 0 705
305 1801 return s;
306 }
307 }
308 18 return reuse;
309 #endif
310 }
311  
312 /* Store, with an optional deadline. `ttl_ms` of 0 is "never expires"; anything
313 * else is a lifetime in milliseconds from now, and the clock is read only when
314 * one is asked for. */
315 /* Collect an entry a reader found expired: tombstone it under the stripe lock,
316 * but only if it is STILL the same expired key - a writer may have refreshed it
317 * between the lock-free read and this lock. Best effort: if the lock is
318 * contended it is left for the next reader to notice, never waited on. */
319 705 static void sa_hash_reap(sa_hash *m, const char *key, uint32_t klen,
320 uint64_t tag, uint64_t now)
321 {
322 #if SA_HAVE_ATOMICS
323 705 sa_hash_hdr *h = m->hdr;
324 sa_hash_slot *s;
325 705 int found = 0;
326  
327 705 ▶ if (!sa_at_lock(h->locks, tag)) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_at_lock(h->locks, tag)) return; 0 705 705
328 705 s = sa_hash_place(m, key, klen, tag, now, &found);
329 705 ▶ if (s && found == 2) {
Branch: 2 branches
BranchTrueFalseTotal
if (s && found == 2) { 705 0 705
if (s && found == 2) { 705 0 705
330 705 sa_at_store32_rel(&s->state, SA_H_DEAD);
331 705 sa_at_store32_rel(&s->vlen, 0);
332 705 sa_at_fetch_add64(&h->used, (uint64_t)-1);
333 705 sa_at_fetch_add64(&h->tombstones, 1);
334 705 sa_at_fetch_add64(&h->expired, 1);
335 }
336 705 sa_at_unlock(h->locks, tag);
337 #else
338 (void)m; (void)key; (void)klen; (void)tag; (void)now;
339 #endif
340 }
341  
342 1146 static int sa_hash_fetch(sa_hash *m, const char *key, uint32_t klen,
343 char *out, uint32_t outmax, uint32_t *vlen)
344 {
345 #if !SA_HAVE_ATOMICS
346 (void)m; (void)key; (void)klen; (void)out; (void)outmax; (void)vlen;
347 return SA_H_MISS;
348 #else
349 1146 uint64_t tag = sa_at_fnv(key, klen);
350 1146 uint64_t i, start = tag % m->nslots;
351  
352 1194 ▶ for (i = 0; i < m->nslots; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < m->nslots; i++) { 1194 0 1194
353 1194 sa_hash_slot *s = SA_HSLOT_AT(m, start + i);
354 1194 uint32_t st = sa_at_load32_acq(&s->state);
355 1194 long spin = 0;
356  
357 1194 ▶ if (st == SA_H_EMPTY) return SA_H_MISS; /* a probe stops here */
Branch: 1 branch
BranchTrueFalseTotal
if (st == SA_H_EMPTY) return SA_H_MISS; /* a probe stops here */ 58 1136 1194
358 1136 ▶ if (st == SA_H_DEAD) continue; /* but never here */
Branch: 1 branch
BranchTrueFalseTotal
if (st == SA_H_DEAD) continue; /* but never here */ 45 1091 1136
359 1091 ▶ if (sa_at_load64_acq(&s->tag) != tag) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load64_acq(&s->tag) != tag) continue; 3 1088 1091
360  
361 0 for (;;) {
362 1088 uint32_t v1 = sa_at_load32_acq(&s->version);
363 uint32_t kl, vl;
364 uint64_t exp;
365  
366 1088 ▶ if (v1 & 1u) { /* mid-update: wait */
Branch: 1 branch
BranchTrueFalseTotal
if (v1 & 1u) { /* mid-update: wait */ 0 1088 1088
367 0 ▶ if (++spin >= SA_HASH_SPIN) {
Branch: 1 branch
BranchTrueFalseTotal
if (++spin >= SA_HASH_SPIN) { 0 0 0
368 0 sa_at_fetch_add64(&m->hdr->busy, 1);
369 0 return SA_H_BUSY;
370 }
371 0 continue;
372 }
373  
374 1088 kl = sa_at_load32_acq(&s->klen);
375 1088 vl = sa_at_load32_acq(&s->vlen);
376 1088 exp = sa_at_load64_acq(&s->expires);
377 1088 ▶ if (kl != klen || (uint64_t)kl + vl > m->pair_max) break;
Branch: 2 branches
BranchTrueFalseTotal
if (kl != klen || (uint64_t)kl + vl > m->pair_max) break; 1088 0 1088
if (kl != klen || (uint64_t)kl + vl > m->pair_max) break; 1088 0 1088
378 1088 ▶ if (memcmp(s->bytes, key, klen) != 0) break;
Branch: 1 branch
BranchTrueFalseTotal
if (memcmp(s->bytes, key, klen) != 0) break; 0 1088 1088
379  
380 /* THE EXPIRY CHECK COMES BEFORE THE too-big-for-buffer EARLY OUT.
381 * exists() passes a zero-length buffer, so a non-empty value takes
382 * the BUSY branch below - and an expired key returning BUSY reads
383 * as present, which is the exact bug this whole thing exists to
384 * prevent. The clock is only read when a deadline is set, so a map
385 * with no TTL still pays nothing. The reap re-verifies under the
386 * lock, so acting here on an `exp` that a concurrent refresh has
387 * already moved is harmless: a refreshed key is not collected. */
388 1088 ▶ if (exp) {
Branch: 1 branch
BranchTrueFalseTotal
if (exp) { 959 129 1088
389 959 uint64_t nowms = sa_now_ms();
390 959 ▶ if (nowms >= exp) {
Branch: 1 branch
BranchTrueFalseTotal
if (nowms >= exp) { 705 254 959
391 705 sa_hash_reap(m, key, klen, tag, nowms);
392 705 return SA_H_MISS;
393 }
394 }
395  
396 383 ▶ if (vl > outmax) { if (vlen) *vlen = vl; return SA_H_BUSY; }
Branch: 2 branches
BranchTrueFalseTotal
if (vl > outmax) { if (vlen) *vlen = vl; return SA_H_BUSY; } 89 294 383
if (vl > outmax) { if (vlen) *vlen = vl; return SA_H_BUSY; } 89 0 89
397  
398 294 memcpy(out, s->bytes + kl, (size_t)vl);
399 294 sa_at_fence_acq();
400  
401 /* Unchanged either side of the copy? If not, what is in `out` may
402 * be half of one value and half of another. */
403 294 ▶ if (sa_at_load32_acq(&s->version) != v1) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&s->version) != v1) { 0 294 294
404 0 ▶ if (++spin >= SA_HASH_SPIN) {
Branch: 1 branch
BranchTrueFalseTotal
if (++spin >= SA_HASH_SPIN) { 0 0 0
405 0 sa_at_fetch_add64(&m->hdr->busy, 1);
406 0 return SA_H_BUSY;
407 }
408 0 continue;
409 }
410 294 ▶ if (vlen) *vlen = vl;
Branch: 1 branch
BranchTrueFalseTotal
if (vlen) *vlen = vl; 294 0 294
411 294 return SA_H_HIT;
412 }
413 /* fell out of the seqlock loop: this slot is not our key */
414 }
415 0 return SA_H_MISS;
416 #endif
417 }
418  
419 /* ---- writing, under a stripe lock ------------------------------------------ */
420  
421 /* A WRITE PATH'S WAIT IS A GUESS ABOUT THE SCHEDULER TOO, and sa_at_lock's
422 * hundred thousand test-and-sets is the same guess sa_arena.h's sa_lock_wait
423 * was written to stop making. It burns about five milliseconds on a cache line
424 * whose owner is NOT RUNNING, then refuses - so a writer loses its write for
425 * being unlucky, not for anything being full. On a box running a dozen builds,
426 * not being scheduled for five milliseconds is ordinary.
427 *
428 * So the wait escalates, exactly as the carve path's does: a spin first,
429 * because the usual holder really is about to finish its one memcpy, then
430 * sleeps doubling from 50us. The retries after the first are a single
431 * test-and-set and never another spin - hammering the lock byte from several
432 * waiters is what keeps the HOLDER from reaching its own unlock.
433 *
434 * MUCH SHORTER THAN THE CARVE PATH'S TWO SECONDS, and deliberately. A carve is
435 * a rare operation whose caller can afford to wait; a store or an incr is on a
436 * per-request path, and a rate limiter that stalls two seconds behind a
437 * descheduled holder has done more damage than the lost count it prevented.
438 * About ten milliseconds covers an ordinary preemption, which is all that was
439 * ever wrong here, and still bounded because a process that died holding the
440 * stripe must not wedge everybody after it. That refusal is SA_H_WBUSY, so a
441 * caller that does want to insist can, and knows it is worth insisting. The
442 * loop is sa_arena.h's sa_lock_wait_brief, the same one the lease takes. */
443 1992 static int sa_hash_wait(volatile unsigned char *locks, uint64_t h) {
444 1992 return sa_lock_wait_brief(locks, h);
445 }
446  
447 796 static int sa_hash_store_ttl(sa_hash *m, const char *key, uint32_t klen,
448 const char *val, uint32_t vlen, uint64_t ttl_ms)
449 {
450 #if !SA_HAVE_ATOMICS
451 (void)m; (void)key; (void)klen; (void)val; (void)vlen; (void)ttl_ms;
452 return SA_H_FULL;
453 #else
454 796 sa_hash_hdr *h = m->hdr;
455 uint64_t tag, exp;
456 sa_hash_slot *s;
457 796 int found = 0, rc = SA_H_OK;
458  
459 796 ▶ if ((uint64_t)klen + vlen > m->pair_max) return SA_H_TOOBIG;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)klen + vlen > m->pair_max) return SA_H_TOOBIG; 1 795 796
460 795 ▶ if (!klen) return SA_H_TOOBIG;
Branch: 1 branch
BranchTrueFalseTotal
if (!klen) return SA_H_TOOBIG; 1 794 795
461  
462 794 ▶ exp = ttl_ms ? sa_now_ms() + ttl_ms : 0;
Branch: 1 branch
BranchTrueFalseTotal
exp = ttl_ms ? sa_now_ms() + ttl_ms : 0; 633 161 794
463  
464 794 tag = sa_at_fnv(key, klen);
465 794 ▶ if (!sa_hash_wait(h->locks, tag)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_hash_wait(h->locks, tag)) { 0 794 794
466 0 sa_at_fetch_add64(&h->busy, 1);
467 0 return SA_H_WBUSY;
468 }
469  
470 /* now = 0: store overwrites the value and sets the new deadline whether the
471 * old entry was current or expired, so it need not tell the two apart -
472 * only whether the slot was already counted in `used`, which is found!=0. */
473 794 s = sa_hash_place(m, key, klen, tag, 0, &found);
474 794 ▶ if (!s) {
Branch: 1 branch
BranchTrueFalseTotal
if (!s) { 18 776 794
475 18 sa_at_unlock(h->locks, tag);
476 18 sa_at_fetch_add64(&h->full, 1);
477 18 return SA_H_FULL;
478 }
479  
480 /* Odd while writing, even when settled, with a barrier either side. The
481 * barriers are the protocol: without the first, the bytes below can reach
482 * another CPU before the odd version does, and a reader then sees new bytes
483 * under an old version and calls them whole. */
484 776 sa_at_store32_rel(&s->version, sa_at_load32_acq(&s->version) | 1u);
485 776 sa_at_fence_rel();
486  
487 776 ▶ if (!found) {
Branch: 1 branch
BranchTrueFalseTotal
if (!found) { 731 45 776
488 731 uint32_t was = sa_at_load32_acq(&s->state);
489 731 memcpy(s->bytes, key, klen);
490 731 s->klen = klen;
491 731 sa_at_store64_rel(&s->tag, tag);
492 731 ▶ if (was == SA_H_DEAD) sa_at_fetch_add64(&h->tombstones, (uint64_t)-1);
Branch: 1 branch
BranchTrueFalseTotal
if (was == SA_H_DEAD) sa_at_fetch_add64(&h->tombstones, (uint64_t)-1); 4 727 731
493 731 sa_at_fetch_add64(&h->used, 1);
494 }
495 776 memcpy(s->bytes + klen, val, vlen);
496 776 s->vlen = vlen;
497 776 sa_at_store64_rel(&s->expires, exp);
498  
499 776 sa_at_fence_rel();
500 776 sa_at_store32_rel(&s->version, (sa_at_load32_acq(&s->version) + 1u) | 0u);
501 776 sa_at_store32_rel(&s->state, SA_H_LIVE);
502  
503 776 sa_at_unlock(h->locks, tag);
504 776 return rc;
505 #endif
506 }
507  
508 161 static int sa_hash_store(sa_hash *m, const char *key, uint32_t klen,
509 const char *val, uint32_t vlen)
510 {
511 161 return sa_hash_store_ttl(m, key, klen, val, vlen, 0);
512 }
513  
514 7 static int sa_hash_delete(sa_hash *m, const char *key, uint32_t klen)
515 {
516 #if !SA_HAVE_ATOMICS
517 (void)m; (void)key; (void)klen;
518 return 0;
519 #else
520 7 sa_hash_hdr *h = m->hdr;
521 uint64_t tag;
522 sa_hash_slot *s;
523 7 int found = 0;
524  
525 7 ▶ if (!klen) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!klen) return 0; 0 7 7
526 7 tag = sa_at_fnv(key, klen);
527 /* NOT 0: that is what "the key was not there" answers, and a caller that
528 * deletes in order to rely on the key being gone - resetting a window
529 * counter before a fresh burst, say - would read a refusal as success and
530 * then count the old window's hits into the new one. */
531 7 ▶ if (!sa_hash_wait(h->locks, tag)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_hash_wait(h->locks, tag)) { 0 7 7
532 0 sa_at_fetch_add64(&h->busy, 1);
533 0 return SA_H_WBUSY;
534 }
535  
536 /* now = 0: delete removes the entry whether current or expired, so it need
537 * not read the clock to classify it. */
538 7 s = sa_hash_place(m, key, klen, tag, 0, &found);
539 7 ▶ if (!s || !found) { sa_at_unlock(h->locks, tag); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (!s || !found) { sa_at_unlock(h->locks, tag); return 0; } 7 0 7
if (!s || !found) { sa_at_unlock(h->locks, tag); return 0; } 2 5 7
540  
541 /* A TOMBSTONE, not an empty slot. An empty slot stops a probe, and a probe
542 * that stops early cannot find a key placed past this one. */
543 5 sa_at_store32_rel(&s->state, SA_H_DEAD);
544 5 sa_at_store32_rel(&s->vlen, 0);
545 5 sa_at_fetch_add64(&h->used, (uint64_t)-1);
546 5 sa_at_fetch_add64(&h->tombstones, 1);
547  
548 5 sa_at_unlock(h->locks, tag);
549 5 return 1;
550 #endif
551 }
552  
553 /* Add to a counter, creating it at `by` when it is not there.
554 *
555 * A counter is an entry whose value is exactly eight bytes, and this is the one
556 * operation that does not go through the seqlock: the value IS a single aligned
557 * word, so the add is one atomic and a reader can never see it half-written.
558 * That is what makes a shared rate limiter or a request count cost the same as
559 * incrementing a variable.
560 *
561 * An entry that exists and is not eight bytes is left alone and refused, rather
562 * than reinterpreted: a caller that stored a string and then counted on it has
563 * a bug, and silently overwriting it would hide the bug and the string. */
564 /* `ttl_ms` is set only when the increment CREATES the counter or RESETS an
565 * expired one: a live counter keeps the deadline it has, so a window does not
566 * slide. 0 means no deadline, which is what sa_hash_incr passes.
567 *
568 * `now_ms` is the caller's reading of the wall clock, or 0 to read it here.
569 * A caller that has just read the clock to compute the deadline it passes -
570 * a fixed-window rate limiter does exactly that - hands the reading in, so
571 * a hit on a counter with a deadline costs one clock read and not two. The
572 * clock is read at most once on this path, and only when a deadline is
573 * involved. */
574 1191 static int sa_hash_incr_at(sa_hash *m, const char *key, uint32_t klen,
575 int64_t by, uint64_t ttl_ms, uint64_t now_ms,
576 uint64_t *now)
577 {
578 #if !SA_HAVE_ATOMICS
579 (void)m; (void)key; (void)klen; (void)by; (void)ttl_ms; (void)now_ms;
580 (void)now;
581 return SA_H_FULL;
582 #else
583 1191 sa_hash_hdr *h = m->hdr;
584 uint64_t tag;
585 sa_hash_slot *s;
586 1191 int found = 0;
587  
588 1191 ▶ if (!klen) return SA_H_TOOBIG;
Branch: 1 branch
BranchTrueFalseTotal
if (!klen) return SA_H_TOOBIG; 0 1191 1191
589 1191 ▶ if ((uint64_t)klen + 8 > m->pair_max) return SA_H_TOOBIG;
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)klen + 8 > m->pair_max) return SA_H_TOOBIG; 0 1191 1191
590  
591 1191 tag = sa_at_fnv(key, klen);
592 1191 ▶ if (!sa_hash_wait(h->locks, tag)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_hash_wait(h->locks, tag)) { 0 1191 1191
593 0 sa_at_fetch_add64(&h->busy, 1);
594 0 return SA_H_WBUSY;
595 }
596  
597 /* now = 0: find any live match, then check its own deadline below. Reading
598 * the clock only for a match that actually carries one keeps a counter
599 * with no TTL - the rate-limit hot path - free of a clock call. */
600 1191 s = sa_hash_place(m, key, klen, tag, 0, &found);
601 1191 ▶ if (!s) {
Branch: 1 branch
BranchTrueFalseTotal
if (!s) { 0 1191 1191
602 0 sa_at_unlock(h->locks, tag);
603 0 sa_at_fetch_add64(&h->full, 1);
604 0 return SA_H_FULL;
605 }
606 {
607 /* An EXPIRED counter is logically gone, so it is reset to zero rather
608 * than added to a stale value - the one thing a plain "found" flag
609 * would get wrong. A non-counter that has expired is likewise gone, so
610 * the deadline is checked before the not-a-counter refusal. */
611 1191 int reset = 0;
612 1191 ▶ if (found && sa_at_load64_acq(&s->expires)) {
Branch: 2 branches
BranchTrueFalseTotal
if (found && sa_at_load64_acq(&s->expires)) { 1046 145 1191
if (found && sa_at_load64_acq(&s->expires)) { 990 56 1046
613 990 ▶ if (!now_ms) now_ms = sa_now_ms();
Branch: 1 branch
BranchTrueFalseTotal
if (!now_ms) now_ms = sa_now_ms(); 986 4 990
614 990 ▶ if (now_ms >= sa_at_load64_acq(&s->expires)) reset = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (now_ms >= sa_at_load64_acq(&s->expires)) reset = 1; 129 861 990
615 }
616  
617 1191 ▶ if (found && !reset && sa_at_load32_acq(&s->vlen) != 8) {
Branch: 3 branches
BranchTrueFalseTotal
if (found && !reset && sa_at_load32_acq(&s->vlen) != 8) { 1046 145 1191
if (found && !reset && sa_at_load32_acq(&s->vlen) != 8) { 917 129 1046
if (found && !reset && sa_at_load32_acq(&s->vlen) != 8) { 2 915 917
618 2 sa_at_unlock(h->locks, tag);
619 2 return SA_H_NOTNUM;
620 }
621  
622 1189 ▶ if (!found || reset) {
Branch: 2 branches
BranchTrueFalseTotal
if (!found || reset) { 1044 145 1189
if (!found || reset) { 129 915 1044
623 274 uint32_t was = sa_at_load32_acq(&s->state);
624 274 uint64_t zero = 0;
625 274 sa_at_store32_rel(&s->version, sa_at_load32_acq(&s->version) | 1u);
626 274 sa_at_fence_rel();
627 274 memcpy(s->bytes, key, klen);
628 274 s->klen = klen;
629 274 memcpy(s->bytes + klen, &zero, 8);
630 274 s->vlen = 8;
631 274 sa_at_store64_rel(&s->tag, tag);
632 /* A fresh counter's deadline, or none: a reset one starts its
633 * window now, never inherits the old deadline. */
634 274 ▶ if (ttl_ms && !now_ms) now_ms = sa_now_ms();
Branch: 2 branches
BranchTrueFalseTotal
if (ttl_ms && !now_ms) now_ms = sa_now_ms(); 183 91 274
if (ttl_ms && !now_ms) now_ms = sa_now_ms(); 95 88 183
635 274 ▶ sa_at_store64_rel(&s->expires, ttl_ms ? now_ms + ttl_ms : 0);
Branch: 1 branch
BranchTrueFalseTotal
sa_at_store64_rel(&s->expires, ttl_ms ? now_ms + ttl_ms : 0); 183 91 274
636 274 sa_at_fence_rel();
637 274 sa_at_store32_rel(&s->version, sa_at_load32_acq(&s->version) + 1u);
638 274 sa_at_store32_rel(&s->state, SA_H_LIVE);
639 274 ▶ if (was == SA_H_DEAD) sa_at_fetch_add64(&h->tombstones, (uint64_t)-1);
Branch: 1 branch
BranchTrueFalseTotal
if (was == SA_H_DEAD) sa_at_fetch_add64(&h->tombstones, (uint64_t)-1); 5 269 274
640 /* reset reuses a slot already counted in `used`; only a genuinely
641 * new key adds to it. */
642 274 ▶ if (!found) sa_at_fetch_add64(&h->used, 1);
Branch: 1 branch
BranchTrueFalseTotal
if (!found) sa_at_fetch_add64(&h->used, 1); 145 129 274
643 }
644 }
645  
646 /* The counter itself, aligned inside the slot only if the key length says
647 * so - so it is read and written through a copy when it is not. The
648 * stripe lock is held, so no other writer can be here: a load and a
649 * release store of the aligned word, never a read-modify-write, which
650 * costs a locked instruction the lock has already paid for. A reader
651 * (`counter`, `fetch`) sees the old whole word or the new one, since an
652 * aligned 64-bit store cannot tear on any target with 64-bit atomics. */
653 {
654 1189 char *p = s->bytes + s->klen;
655 1189 ▶ if (((size_t)p & 7u) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (((size_t)p & 7u) == 0) { 3 1186 1189
656 3 volatile uint64_t *w = (volatile uint64_t *)p;
657 3 uint64_t v = sa_at_load64_acq(w) + (uint64_t)by;
658 3 sa_at_store64_rel(w, v);
659 3 ▶ if (now) *now = v;
Branch: 1 branch
BranchTrueFalseTotal
if (now) *now = v; 3 0 3
660 }
661 else {
662 uint64_t v;
663 1186 memcpy(&v, p, 8);
664 1186 v += (uint64_t)by;
665 1186 memcpy(p, &v, 8);
666 1186 ▶ if (now) *now = v;
Branch: 1 branch
BranchTrueFalseTotal
if (now) *now = v; 1186 0 1186
667 }
668 }
669  
670 1189 sa_at_unlock(h->locks, tag);
671 1189 return SA_H_OK;
672 #endif
673 }
674  
675 959 static int sa_hash_incr_ttl(sa_hash *m, const char *key, uint32_t klen,
676 int64_t by, uint64_t ttl_ms, uint64_t *now)
677 {
678 959 return sa_hash_incr_at(m, key, klen, by, ttl_ms, 0, now);
679 }
680  
681 225 static int sa_hash_incr(sa_hash *m, const char *key, uint32_t klen,
682 int64_t by, uint64_t *now)
683 {
684 225 return sa_hash_incr_at(m, key, klen, by, 0, 0, now);
685 }
686  
687 #endif /* SA_HASH_H */
« xs/rate.xs ↑ Summary include/sa/sa_cuckoo.h »