include/sa/sa_cache.h

filter: Statementstmt 93.4% 201 / 215 Branchbran 69.7% 134 / 192 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 82.3% 335 / 407 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/hist.xs ↑ Summary xs/cuckoo.xs »
1 #ifndef SA_CACHE_H
2 #define SA_CACHE_H
3  
4 /* sa_cache.h - a shared cache, which is a map that throws something away
5 * instead of saying no. Perl-free.
6 *
7 * ---- why this is not the map with a policy on top ---------------------------
8 *
9 * The map refuses when it is full, which is right for a table of things that
10 * must be there and wrong for a cache. A cache must choose a victim and take
11 * its place, and that choice cannot be made from Perl: picking a victim and
12 * replacing it has to be one operation as far as a reader is concerned, or two
13 * processes evict each other's entries and a reader sees a key that is briefly
14 * neither the old value nor the new one.
15 *
16 * ---- set-associative, because a probe chain cannot be evicted from ----------
17 *
18 * An open-addressed table with one long probe chain has nowhere to put a new
19 * key when it is full: the slot a victim frees is almost never the slot the new
20 * key hashes to. So the table is divided into small BUCKETS of `ways` entries,
21 * a key belongs to exactly one bucket, and a victim is chosen from inside it.
22 * That is how a CPU cache is arranged, for the same reason.
23 *
24 * It also makes the work bounded. A lookup touches `ways` entries and stops; an
25 * eviction considers `ways` candidates and stops. Neither degrades as the cache
26 * fills, which is the failure mode of a full open-addressed table.
27 *
28 * The cost is that a bucket can fill while the cache as a whole has room, so a
29 * hot bucket evicts sooner than a perfect cache would. With eight ways that is
30 * a small effect and it buys a bounded probe; with two it would not be.
31 *
32 * ---- CLOCK, not LRU ---------------------------------------------------------
33 *
34 * True LRU reorders a list on every READ, which makes every reader a writer and
35 * throws away the property that makes this worth sharing. CLOCK sets one bit on
36 * a hit and sweeps a hand round the bucket at eviction time, clearing bits and
37 * taking the first entry whose bit was already clear. A reader writes one bit
38 * with one atomic and takes no lock.
39 *
40 * It approximates LRU well enough that the difference is hard to measure, and
41 * it is the standard answer for exactly this reason.
42 *
43 * ---- expiry is lazy ---------------------------------------------------------
44 *
45 * An entry with a deadline is not swept when it passes; it is noticed when
46 * somebody looks, and preferred as a victim when somebody needs room. Sweeping
47 * would mean a process whose job is to walk the whole cache on a timer, which
48 * is work nobody asked for at a moment nobody chose.
49 *
50 * Needs sa_arena.h.
51 */
52  
53 #include "sa/sa_arena.h"
54 #include "sa/sa_peer.h" /* sa_getpid, for the batched counts */
55  
56 #ifdef _WIN32
57 # include <windows.h>
58 #else
59 # include <sys/time.h>
60 #endif
61  
62 #define SA_CACHE_MAGIC 0x45484341u /* 'A','C','H','E' little-endian */
63  
64 #define SA_CACHE_MIN_WAYS 1
65 #define SA_CACHE_MAX_WAYS 64
66  
67 /* what a set answers */
68 #define SA_C_OK 1
69 #define SA_C_TOOBIG (-1)
70  
71 /* what a get answers */
72 #define SA_C_HIT 0
73 #define SA_C_MISS 1
74 #define SA_C_BUSY 2
75  
76 typedef struct {
77 volatile uint32_t state; /* 0 empty, 1 live */
78 volatile uint32_t version; /* odd while being written */
79 volatile uint32_t klen;
80 volatile uint32_t vlen;
81 volatile uint64_t tag;
82 volatile uint64_t expires; /* ms since the epoch; 0 = never */
83 volatile uint32_t used; /* CLOCK's reference bit */
84 uint32_t pad;
85 char bytes[1]; /* key then value, way_size in total */
86 } sa_cache_way;
87  
88 typedef struct {
89 volatile uint32_t magic; /* published LAST at init */
90 uint32_t way_size;
91 uint32_t ways;
92 uint32_t serialise; /* values are Struct::Codec's encoding */
93 uint64_t nbuckets;
94 uint64_t ways_off; /* from the CACHE's base */
95 uint64_t hands_off; /* one CLOCK hand per bucket */
96 volatile uint64_t hits;
97 volatile uint64_t misses;
98 volatile uint64_t evictions;
99 volatile uint64_t expired; /* found dead, by a reader or a victim hunt */
100 volatile uint64_t used; /* live entries */
101 volatile unsigned char locks[SA_LOCK_STRIPES];
102 } sa_cache_hdr;
103  
104 #ifndef SA_CACHE_FWD
105 #define SA_CACHE_FWD
106 typedef struct sa_cache sa_cache;
107 #endif
108 struct sa_cache {
109 sa_region *arena;
110 sa_cache_hdr *hdr;
111 char *ways;
112 volatile uint32_t *hands;
113 uint32_t way_size;
114 uint32_t nways;
115 uint64_t nbuckets;
116 uint64_t pair_max;
117 uint32_t serialise; /* copied out of the header at bind */
118 /* Counted in this process and published in batches: see sa_cache_count. */
119 uint64_t pend_pid;
120 uint32_t pend_hits;
121 uint32_t pend_misses;
122 };
123  
124 #define SA_CWAY_AT(c, b, w) \
125 ((sa_cache_way *)((c)->ways + \
126 ((size_t)((b) * (c)->nways + (w))) * (c)->way_size))
127  
128 52 static uint64_t sa_cache_capacity(uint32_t way_size) {
129 52 uint64_t hdr = (uint64_t)sizeof(sa_cache_way) - 1;
130 52 ▶ return way_size > hdr ? (uint64_t)way_size - hdr : 0;
Branch: 1 branch
BranchTrueFalseTotal
return way_size > hdr ? (uint64_t)way_size - hdr : 0; 52 0 52
131 }
132  
133 52 static uint64_t sa_cache_bytes(uint64_t nbuckets, uint32_t nways,
134 uint32_t way_size) {
135 52 return sa_align_up((uint64_t)sizeof(sa_cache_hdr))
136 52 + sa_align_up(nbuckets * nways * (uint64_t)way_size)
137 52 + sa_align_up(nbuckets * 4u);
138 }
139  
140 /* sa_now_ms moved to sa_time.h, so the map's TTL and this cache read the one
141 * shared wall clock rather than each keeping their own. */
142  
143 /* `serialise` is 0, 1 or SA_SER_ANY; see sa_format.h. */
144 20 static sa_cache *sa_cache_bind(sa_region *arena, sa_reg *e, uint64_t nbuckets,
145 uint32_t nways, uint32_t way_size,
146 int serialise, int *err)
147 {
148 #if !SA_HAVE_ATOMICS
149 (void)arena; (void)e; (void)nbuckets; (void)nways; (void)way_size;
150 (void)serialise;
151 if (err) *err = SA_E_NOATOMICS;
152 return NULL;
153 #else
154 sa_cache *c;
155 sa_cache_hdr *h;
156 uint64_t hash;
157  
158 20 ▶ if (err) *err = SA_E_OK;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_OK; 20 0 20
159 20 ▶ 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; } 20 0 20
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 20 20
if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
160  
161 20 h = (sa_cache_hdr *)sa_ptr_len(arena, e->off, sizeof(sa_cache_hdr));
162 20 ▶ 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 20 20
if (!h) { if (err) *err = SA_E_NOENT; return NULL; } 0 0 0
163  
164 20 ▶ if (sa_at_load32_acq(&h->magic) != SA_CACHE_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&h->magic) != SA_CACHE_MAGIC) { 16 4 20
165 16 hash = sa_at_fnv(e->name, strlen(e->name));
166 16 ▶ if (sa_at_lock(h->locks, hash)) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_lock(h->locks, hash)) { 16 0 16
167 16 ▶ if (sa_at_load32_acq(&h->magic) != SA_CACHE_MAGIC) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&h->magic) != SA_CACHE_MAGIC) { 16 0 16
168 16 ▶ if (!nbuckets || !nways || sa_cache_capacity(way_size) == 0
Branch: 3 branches
BranchTrueFalseTotal
if (!nbuckets || !nways || sa_cache_capacity(way_size) == 0 16 0 16
if (!nbuckets || !nways || sa_cache_capacity(way_size) == 0 16 0 16
if (!nbuckets || !nways || sa_cache_capacity(way_size) == 0 16 0 16
169 16 ▶ || sa_cache_bytes(nbuckets, nways, way_size) > e->len) {
Branch: 1 branch
BranchTrueFalseTotal
|| sa_cache_bytes(nbuckets, nways, way_size) > e->len) { 0 16 16
170 0 sa_at_unlock(h->locks, hash);
171 0 ▶ if (err) *err = SA_E_FULL;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_FULL; 0 0 0
172 0 return NULL;
173 }
174 16 memset((void *)h, 0,
175 16 (size_t)sa_cache_bytes(nbuckets, nways, way_size));
176 16 h->way_size = way_size;
177 16 h->ways = nways;
178 16 ▶ h->serialise = serialise > 0 ? 1u : 0u;
Branch: 1 branch
BranchTrueFalseTotal
h->serialise = serialise > 0 ? 1u : 0u; 2 14 16
179 16 h->nbuckets = nbuckets;
180 16 h->ways_off = sa_align_up((uint64_t)sizeof(sa_cache_hdr));
181 32 h->hands_off = h->ways_off
182 16 + sa_align_up(nbuckets * nways * (uint64_t)way_size);
183 16 sa_at_store32_rel(&h->magic, SA_CACHE_MAGIC);
184 }
185 16 sa_at_unlock(h->locks, hash);
186 }
187 16 ▶ if (!sa_wait_magic32(&h->magic, SA_CACHE_MAGIC)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_wait_magic32(&h->magic, SA_CACHE_MAGIC)) { 0 16 16
188 0 ▶ if (err) *err = SA_E_MAGIC;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_MAGIC; 0 0 0
189 0 return NULL;
190 }
191 }
192  
193 /* THE GEOMETRY IN THE HEADER IS ALSO SOMEBODY ELSE'S NUMBER.
194 *
195 * The branch above only checks a size when this process is the one doing
196 * the INITIALISING. A process that finds the magic already set reads the
197 * shape out of the shared header and believed it, so a header claiming
198 * four billion slots put every later read past the end of the mapping.
199 * sa_reg_ok makes `len` trustworthy; this makes the shape trustworthy. */
200  
201 20 ▶ if ((nbuckets && h->nbuckets != nbuckets) || (nways && h->ways != nways)
Branch: 4 branches
BranchTrueFalseTotal
if ((nbuckets && h->nbuckets != nbuckets) || (nways && h->ways != nways) 20 0 20
if ((nbuckets && h->nbuckets != nbuckets) || (nways && h->ways != nways) 20 0 20
if ((nbuckets && h->nbuckets != nbuckets) || (nways && h->ways != nways) 20 0 20
if ((nbuckets && h->nbuckets != nbuckets) || (nways && h->ways != nways) 20 0 20
202 20 ▶ || (way_size && h->way_size != way_size)) {
Branch: 2 branches
BranchTrueFalseTotal
|| (way_size && h->way_size != way_size)) { 20 0 20
|| (way_size && h->way_size != way_size)) { 0 20 20
203 0 ▶ if (err) *err = SA_E_NAME;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_NAME; 0 0 0
204 0 return NULL;
205 }
206 20 ▶ if (serialise >= 0 && h->serialise != (serialise ? 1u : 0u)) {
Branch: 3 branches
BranchTrueFalseTotal
if (serialise >= 0 && h->serialise != (serialise ? 1u : 0u)) { 19 1 20
if (serialise >= 0 && h->serialise != (serialise ? 1u : 0u)) { 4 15 19
if (serialise >= 0 && h->serialise != (serialise ? 1u : 0u)) { 3 16 19
207 3 ▶ if (err) *err = SA_E_SHAPE;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = SA_E_SHAPE; 3 0 3
208 3 return NULL;
209 }
210  
211 17 c = (sa_cache *)calloc(1, sizeof(sa_cache));
212 17 ▶ if (!c) { if (err) *err = SA_E_NOMEM; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!c) { if (err) *err = SA_E_NOMEM; return NULL; } 0 17 17
if (!c) { if (err) *err = SA_E_NOMEM; return NULL; } 0 0 0
213 17 c->arena = arena;
214 17 c->hdr = h;
215 17 c->ways = (char *)h + (size_t)h->ways_off;
216 17 c->hands = (volatile uint32_t *)((char *)h + (size_t)h->hands_off);
217 17 c->way_size = h->way_size;
218 17 c->nways = h->ways;
219 17 c->nbuckets = h->nbuckets;
220 17 c->pair_max = sa_cache_capacity(h->way_size);
221 17 c->serialise = h->serialise;
222 17 return c;
223 #endif
224 }
225  
226 /* ---- THE HIT AND MISS COUNTS ARE BATCHED PER PROCESS -----------------------
227 *
228 * A hit used to add to hdr->hits, a line every process shares, so every read
229 * in every process was an atomic write to one place. Measured with K forked
230 * readers on one hot key, ns per get per process at K = 1 / 2 / 4 / 8:
231 *
232 * counted per hit, CLOCK bit stored per hit 56 / 140 / 189 / 530
233 * the bit stored only when it reads clear 57 / 101 / 157 / 440
234 * and the hit not counted at all 57 / 63 / 62 / 112
235 *
236 * So a process counts in its own handle and publishes every SA_CACHE_BATCH.
237 * Its own stats are exact, because asking for them publishes first. Another
238 * process's reading can trail by up to SA_CACHE_BATCH - 1 of each per process,
239 * and a process that exits without releasing its handle takes that many with
240 * it.
241 *
242 * A FORK COPIES THE PENDING COUNTS, and the parent publishes its own copy. So
243 * the counts carry the pid they were made under, and a child that finds a
244 * different one discards them before counting its own. sa_getpid is a cached
245 * load where pthread_atfork exists to invalidate it; where it does not, the
246 * check would be a syscall per read, so those builds count every hit directly
247 * as before. */
248 #if defined(SA_HAVE_ATFORK) && !defined(_WIN32)
249 # define SA_CACHE_BATCH 64u
250 #else
251 # define SA_CACHE_BATCH 1u
252 #endif
253  
254 /* Publish what this process has counted and not yet published. */
255 29 static void sa_cache_flush(sa_cache *c) {
256 #if SA_HAVE_ATOMICS
257 uint64_t me;
258 29 ▶ if (!c) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!c) return; 0 29 29
259 29 me = sa_getpid();
260 29 ▶ if (c->pend_pid != me) {
Branch: 1 branch
BranchTrueFalseTotal
if (c->pend_pid != me) { 7 22 29
261 /* inherited across a fork: the parent's, and the parent's to publish */
262 7 c->pend_pid = me;
263 7 c->pend_hits = c->pend_misses = 0;
264 7 return;
265 }
266 22 ▶ if (c->pend_hits) sa_at_fetch_add64(&c->hdr->hits, c->pend_hits);
Branch: 1 branch
BranchTrueFalseTotal
if (c->pend_hits) sa_at_fetch_add64(&c->hdr->hits, c->pend_hits); 15 7 22
267 22 ▶ if (c->pend_misses) sa_at_fetch_add64(&c->hdr->misses, c->pend_misses);
Branch: 1 branch
BranchTrueFalseTotal
if (c->pend_misses) sa_at_fetch_add64(&c->hdr->misses, c->pend_misses); 10 12 22
268 22 c->pend_hits = c->pend_misses = 0;
269 #else
270 (void)c;
271 #endif
272 }
273  
274 290 static void sa_cache_count(sa_cache *c, int hit) {
275 #if SA_HAVE_ATOMICS
276 # if SA_CACHE_BATCH > 1
277 290 uint64_t me = sa_getpid();
278 290 ▶ uint32_t *n = hit ? &c->pend_hits : &c->pend_misses;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t *n = hit ? &c->pend_hits : &c->pend_misses; 264 26 290
279 290 ▶ if (c->pend_pid != me) {
Branch: 1 branch
BranchTrueFalseTotal
if (c->pend_pid != me) { 10 280 290
280 10 c->pend_pid = me;
281 10 c->pend_hits = c->pend_misses = 0;
282 }
283 290 ▶ if (++*n >= SA_CACHE_BATCH) {
Branch: 1 branch
BranchTrueFalseTotal
if (++*n >= SA_CACHE_BATCH) { 3 287 290
284 3 ▶ sa_at_fetch_add64(hit ? &c->hdr->hits : &c->hdr->misses, (uint64_t)*n);
Branch: 1 branch
BranchTrueFalseTotal
sa_at_fetch_add64(hit ? &c->hdr->hits : &c->hdr->misses, (uint64_t)*n); 3 0 3
285 3 *n = 0;
286 }
287 # else
288 sa_at_fetch_add64(hit ? &c->hdr->hits : &c->hdr->misses, 1);
289 # endif
290 #else
291 (void)c; (void)hit;
292 #endif
293 290 }
294  
295 /* Published before the handle goes, so a process that releases it leaves
296 * nothing uncounted. */
297 17 static void sa_cache_free(sa_cache *c) {
298 17 sa_cache_flush(c);
299 17 free(c);
300 17 }
301  
302 /* Has this entry's deadline passed? A zero deadline never does. */
303 631 static int sa_cache_dead(sa_cache_way *w, uint64_t now) {
304 631 uint64_t e = sa_at_load64_acq(&w->expires);
305 631 ▶ return e && e <= now;
Branch: 2 branches
BranchTrueFalseTotal
return e && e <= now; 8 623 631
return e && e <= now; 8 0 8
306 }
307  
308 /* ---- reading, without a lock ----------------------------------------------- */
309  
310 290 static int sa_cache_get(sa_cache *c, const char *key, uint32_t klen,
311 char *out, uint32_t outmax, uint32_t *vlen)
312 {
313 #if !SA_HAVE_ATOMICS
314 (void)c; (void)key; (void)klen; (void)out; (void)outmax; (void)vlen;
315 return SA_C_MISS;
316 #else
317 290 uint64_t tag = sa_at_fnv(key, klen);
318 290 uint64_t b = tag % c->nbuckets;
319 uint32_t w;
320  
321 558 ▶ for (w = 0; w < c->nways; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (w = 0; w < c->nways; w++) { 534 24 558
322 534 sa_cache_way *e = SA_CWAY_AT(c, b, w);
323 534 long spin = 0;
324  
325 534 ▶ if (sa_at_load32_acq(&e->state) != 1) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&e->state) != 1) continue; 100 434 534
326 434 ▶ if (sa_at_load64_acq(&e->tag) != tag) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load64_acq(&e->tag) != tag) continue; 168 266 434
327  
328 0 for (;;) {
329 266 uint32_t v1 = sa_at_load32_acq(&e->version);
330 uint32_t kl, vl;
331 uint64_t exp;
332  
333 266 ▶ if (v1 & 1u) {
Branch: 1 branch
BranchTrueFalseTotal
if (v1 & 1u) { 0 266 266
334 0 ▶ if (++spin >= SA_HASH_SPIN) return SA_C_BUSY;
Branch: 1 branch
BranchTrueFalseTotal
if (++spin >= SA_HASH_SPIN) return SA_C_BUSY; 0 0 0
335 0 continue;
336 }
337 266 kl = sa_at_load32_acq(&e->klen);
338 266 vl = sa_at_load32_acq(&e->vlen);
339 266 exp = sa_at_load64_acq(&e->expires);
340 266 ▶ if (kl != klen || (uint64_t)kl + vl > c->pair_max) break;
Branch: 2 branches
BranchTrueFalseTotal
if (kl != klen || (uint64_t)kl + vl > c->pair_max) break; 266 0 266
if (kl != klen || (uint64_t)kl + vl > c->pair_max) break; 266 0 266
341 266 ▶ if (memcmp(e->bytes, key, klen) != 0) break;
Branch: 1 branch
BranchTrueFalseTotal
if (memcmp(e->bytes, key, klen) != 0) break; 0 266 266
342  
343 /* The clock is read only when this entry has a deadline. It is
344 * 11ns, and a cache that never set a ttl used to pay it on every
345 * get, a miss included. */
346 266 ▶ if (exp && exp <= sa_now_ms()) {
Branch: 2 branches
BranchTrueFalseTotal
if (exp && exp <= sa_now_ms()) { 6 260 266
if (exp && exp <= sa_now_ms()) { 2 4 6
347 /* Expired, and noticed rather than swept. It stays where it is
348 * and becomes the first thing evicted when this bucket needs
349 * room, which costs nothing until then. */
350 2 sa_at_fetch_add64(&c->hdr->expired, 1);
351 2 sa_cache_count(c, 0);
352 2 return SA_C_MISS;
353 }
354 264 ▶ if (vl > outmax) { if (vlen) *vlen = vl; return SA_C_BUSY; }
Branch: 2 branches
BranchTrueFalseTotal
if (vl > outmax) { if (vlen) *vlen = vl; return SA_C_BUSY; } 0 264 264
if (vl > outmax) { if (vlen) *vlen = vl; return SA_C_BUSY; } 0 0 0
355  
356 264 memcpy(out, e->bytes + kl, (size_t)vl);
357 264 sa_at_fence_acq();
358 264 ▶ if (sa_at_load32_acq(&e->version) != v1) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&e->version) != v1) { 0 264 264
359 0 ▶ if (++spin >= SA_HASH_SPIN) return SA_C_BUSY;
Branch: 1 branch
BranchTrueFalseTotal
if (++spin >= SA_HASH_SPIN) return SA_C_BUSY; 0 0 0
360 0 continue;
361 }
362  
363 /* CLOCK's reference bit, stored only when it reads clear. Storing
364 * it on every hit made every reader of a hot key write the line
365 * they all load the entry from; the note above sa_cache_flush has
366 * what that cost. */
367 264 ▶ if (!sa_at_load32_acq(&e->used)) sa_at_store32_rel(&e->used, 1);
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_at_load32_acq(&e->used)) sa_at_store32_rel(&e->used, 1); 55 209 264
368 264 sa_cache_count(c, 1);
369 264 ▶ if (vlen) *vlen = vl;
Branch: 1 branch
BranchTrueFalseTotal
if (vlen) *vlen = vl; 264 0 264
370 264 return SA_C_HIT;
371 }
372 }
373 24 sa_cache_count(c, 0);
374 24 return SA_C_MISS;
375 #endif
376 }
377  
378 /* ---- choosing a victim ----------------------------------------------------- */
379  
380 /* The way this key should occupy, under the caller's lock.
381 *
382 * In order of preference: the key itself, an empty way, an expired one, and
383 * only then a victim chosen by sweeping CLOCK's hand. `*evicted` says whether
384 * something live was thrown out, and `*was_dead` whether it had already
385 * expired - which is not an eviction, it is a collection. */
386 1064 static sa_cache_way *sa_cache_place(sa_cache *c, uint64_t b, const char *key,
387 uint32_t klen, uint64_t tag, uint64_t *now,
388 int *found, int *evicted, int *was_dead)
389 {
390 #if !SA_HAVE_ATOMICS
391 (void)c; (void)b; (void)key; (void)klen; (void)tag; (void)now;
392 (void)found; (void)evicted; (void)was_dead;
393 return NULL;
394 #else
395 1064 sa_cache_way *empty = NULL, *dead = NULL;
396 uint32_t w, steps;
397  
398 1064 *found = *evicted = *was_dead = 0;
399  
400 11176 ▶ for (w = 0; w < c->nways; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (w = 0; w < c->nways; w++) { 10113 1063 11176
401 10113 sa_cache_way *e = SA_CWAY_AT(c, b, w);
402 10113 ▶ if (sa_at_load32_acq(&e->state) != 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&e->state) != 1) { 891 9222 10113
403 891 ▶ if (!empty) empty = e;
Branch: 1 branch
BranchTrueFalseTotal
if (!empty) empty = e; 155 736 891
404 891 continue;
405 }
406 9222 ▶ if (sa_at_load64_acq(&e->tag) == tag
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load64_acq(&e->tag) == tag 1 9221 9222
407 1 ▶ && sa_at_load32_acq(&e->klen) == klen
Branch: 1 branch
BranchTrueFalseTotal
&& sa_at_load32_acq(&e->klen) == klen 1 0 1
408 1 ▶ && memcmp(e->bytes, key, klen) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
&& memcmp(e->bytes, key, klen) == 0) { 1 0 1
409 1 *found = 1;
410 1 return e;
411 }
412 9221 ▶ if (!dead) {
Branch: 1 branch
BranchTrueFalseTotal
if (!dead) { 9186 35 9221
413 /* `*now` is 0 until something needs it: the clock is read for the
414 * first entry that has a deadline, and never for a bucket where
415 * none does. */
416 9186 uint64_t exp = sa_at_load64_acq(&e->expires);
417 9186 ▶ if (exp) {
Branch: 1 branch
BranchTrueFalseTotal
if (exp) { 33 9153 9186
418 33 ▶ if (!*now) *now = sa_now_ms();
Branch: 1 branch
BranchTrueFalseTotal
if (!*now) *now = sa_now_ms(); 14 19 33
419 33 ▶ if (exp <= *now) dead = e;
Branch: 1 branch
BranchTrueFalseTotal
if (exp <= *now) dead = e; 10 23 33
420 }
421 }
422 }
423  
424 1063 ▶ if (empty) return empty;
Branch: 1 branch
BranchTrueFalseTotal
if (empty) return empty; 155 908 1063
425 908 ▶ if (dead) { *was_dead = 1; return dead; }
Branch: 1 branch
BranchTrueFalseTotal
if (dead) { *was_dead = 1; return dead; } 2 906 908
426  
427 /* Every way is live: sweep. Bounded at two passes, because one pass may
428 * clear every bit and the second is then guaranteed to find one clear. */
429 920 ▶ for (steps = 0; steps < c->nways * 2u; steps++) {
Branch: 1 branch
BranchTrueFalseTotal
for (steps = 0; steps < c->nways * 2u; steps++) { 920 0 920
430 920 uint32_t hand = sa_at_load32_acq(&c->hands[b]) % c->nways;
431 920 sa_cache_way *e = SA_CWAY_AT(c, b, hand);
432 920 sa_at_store32_rel(&c->hands[b], (hand + 1u) % c->nways);
433 920 ▶ if (sa_at_load32_acq(&e->used)) {
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&e->used)) { 14 906 920
434 14 sa_at_store32_rel(&e->used, 0); /* a second chance */
435 14 continue;
436 }
437 906 *evicted = 1;
438 906 return e;
439 }
440  
441 /* Every bit was set and stayed set, which means the whole bucket was hit
442 * during the sweep. Take where the hand stands rather than looping. */
443 0 *evicted = 1;
444 0 return SA_CWAY_AT(c, b, sa_at_load32_acq(&c->hands[b]) % c->nways);
445 #endif
446 }
447  
448 1067 static int sa_cache_set(sa_cache *c, const char *key, uint32_t klen,
449 const char *val, uint32_t vlen, uint64_t ttl_ms)
450 {
451 #if !SA_HAVE_ATOMICS
452 (void)c; (void)key; (void)klen; (void)val; (void)vlen; (void)ttl_ms;
453 return SA_C_TOOBIG;
454 #else
455 1067 sa_cache_hdr *h = c->hdr;
456 uint64_t tag, b, now;
457 sa_cache_way *e;
458 1067 int found = 0, evicted = 0, was_dead = 0;
459  
460 1067 ▶ if (!klen || (uint64_t)klen + vlen > c->pair_max) return SA_C_TOOBIG;
Branch: 2 branches
BranchTrueFalseTotal
if (!klen || (uint64_t)klen + vlen > c->pair_max) return SA_C_TOOBIG; 1066 1 1067
if (!klen || (uint64_t)klen + vlen > c->pair_max) return SA_C_TOOBIG; 2 1064 1066
461  
462 1064 tag = sa_at_fnv(key, klen);
463 1064 b = tag % c->nbuckets;
464 /* Only a ttl needs the clock up front. Otherwise place reads it if it
465 * meets an entry with a deadline, and a cache that never sets one never
466 * reads it at all. */
467 1064 ▶ now = ttl_ms ? sa_now_ms() : 0;
Branch: 1 branch
BranchTrueFalseTotal
now = ttl_ms ? sa_now_ms() : 0; 11 1053 1064
468  
469 /* The lock is on the BUCKET rather than the key, because a victim hunt
470 * touches every way in it. */
471 1064 ▶ if (!sa_at_lock(h->locks, b)) return SA_C_TOOBIG;
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_at_lock(h->locks, b)) return SA_C_TOOBIG; 0 1064 1064
472  
473 1064 e = sa_cache_place(c, b, key, klen, tag, &now, &found, &evicted, &was_dead);
474 1064 ▶ if (!e) { sa_at_unlock(h->locks, b); return SA_C_TOOBIG; }
Branch: 1 branch
BranchTrueFalseTotal
if (!e) { sa_at_unlock(h->locks, b); return SA_C_TOOBIG; } 0 1064 1064
475  
476 1064 sa_at_store32_rel(&e->version, sa_at_load32_acq(&e->version) | 1u);
477 1064 sa_at_fence_rel();
478  
479 1064 ▶ if (!found) {
Branch: 1 branch
BranchTrueFalseTotal
if (!found) { 1063 1 1064
480 1063 memcpy(e->bytes, key, klen);
481 1063 sa_at_store32_rel(&e->klen, klen);
482 1063 sa_at_store64_rel(&e->tag, tag);
483 1063 ▶ if (evicted) sa_at_fetch_add64(&h->evictions, 1);
Branch: 1 branch
BranchTrueFalseTotal
if (evicted) sa_at_fetch_add64(&h->evictions, 1); 906 157 1063
484 157 ▶ else if (was_dead) sa_at_fetch_add64(&h->expired, 1);
Branch: 1 branch
BranchTrueFalseTotal
else if (was_dead) sa_at_fetch_add64(&h->expired, 1); 2 155 157
485 1063 ▶ if (!evicted && !was_dead) sa_at_fetch_add64(&h->used, 1);
Branch: 2 branches
BranchTrueFalseTotal
if (!evicted && !was_dead) sa_at_fetch_add64(&h->used, 1); 157 906 1063
if (!evicted && !was_dead) sa_at_fetch_add64(&h->used, 1); 155 2 157
486 }
487 1064 memcpy(e->bytes + klen, val, vlen);
488 1064 sa_at_store32_rel(&e->vlen, vlen);
489 1064 ▶ sa_at_store64_rel(&e->expires, ttl_ms ? now + ttl_ms : 0);
Branch: 1 branch
BranchTrueFalseTotal
sa_at_store64_rel(&e->expires, ttl_ms ? now + ttl_ms : 0); 11 1053 1064
490 /* A new entry starts with its bit clear, so it is a candidate on the next
491 * sweep unless somebody reads it. Setting it here would give every write a
492 * free pass and turn the policy into "evict whatever was written longest
493 * ago", which is not what a cache wants. */
494 1064 sa_at_store32_rel(&e->used, 0);
495  
496 1064 sa_at_fence_rel();
497 1064 sa_at_store32_rel(&e->version, sa_at_load32_acq(&e->version) + 1u);
498 1064 sa_at_store32_rel(&e->state, 1);
499  
500 1064 sa_at_unlock(h->locks, b);
501 1064 return SA_C_OK;
502 #endif
503 }
504  
505 3 static int sa_cache_remove(sa_cache *c, const char *key, uint32_t klen) {
506 #if !SA_HAVE_ATOMICS
507 (void)c; (void)key; (void)klen;
508 return 0;
509 #else
510 3 uint64_t tag = sa_at_fnv(key, klen);
511 3 uint64_t b = tag % c->nbuckets;
512 uint32_t w;
513 3 int gone = 0;
514  
515 3 ▶ if (!klen) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!klen) return 0; 0 3 3
516 3 ▶ if (!sa_at_lock(c->hdr->locks, b)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_at_lock(c->hdr->locks, b)) return 0; 0 3 3
517  
518 18 ▶ for (w = 0; w < c->nways; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (w = 0; w < c->nways; w++) { 17 1 18
519 17 sa_cache_way *e = SA_CWAY_AT(c, b, w);
520 17 ▶ if (sa_at_load32_acq(&e->state) != 1) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&e->state) != 1) continue; 8 9 17
521 9 ▶ if (sa_at_load64_acq(&e->tag) != tag) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load64_acq(&e->tag) != tag) continue; 7 2 9
522 2 ▶ if (sa_at_load32_acq(&e->klen) != klen) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&e->klen) != klen) continue; 0 2 2
523 2 ▶ if (memcmp(e->bytes, key, klen) != 0) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (memcmp(e->bytes, key, klen) != 0) continue; 0 2 2
524 /* A way, unlike an open-addressed slot, can simply become empty: a
525 * bucket is scanned whole, so there is no probe chain to break and no
526 * tombstone to leave. */
527 2 sa_at_store32_rel(&e->state, 0);
528 2 sa_at_store32_rel(&e->used, 0);
529 2 sa_at_store64_rel(&e->expires, 0);
530 2 sa_at_fetch_add64(&c->hdr->used, (uint64_t)-1);
531 2 gone = 1;
532 2 break;
533 }
534 3 sa_at_unlock(c->hdr->locks, b);
535 3 return gone;
536 #endif
537 }
538  
539 /* Drop everything. */
540 2 static void sa_cache_clear(sa_cache *c) {
541 #if SA_HAVE_ATOMICS
542 uint64_t b;
543 8 ▶ for (b = 0; b < c->nbuckets; b++) {
Branch: 1 branch
BranchTrueFalseTotal
for (b = 0; b < c->nbuckets; b++) { 6 2 8
544 uint32_t w;
545 6 ▶ if (!sa_at_lock(c->hdr->locks, b)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!sa_at_lock(c->hdr->locks, b)) continue; 0 6 6
546 54 ▶ for (w = 0; w < c->nways; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (w = 0; w < c->nways; w++) { 48 6 54
547 48 sa_cache_way *e = SA_CWAY_AT(c, b, w);
548 48 sa_at_store32_rel(&e->state, 0);
549 48 sa_at_store32_rel(&e->used, 0);
550 48 sa_at_store64_rel(&e->expires, 0);
551 }
552 6 sa_at_store32_rel(&c->hands[b], 0);
553 6 sa_at_unlock(c->hdr->locks, b);
554 }
555 2 sa_at_store64_rel(&c->hdr->used, 0);
556 #else
557 (void)c;
558 #endif
559 2 }
560  
561 /* Live entries that have not expired. Walks everything, so it is a status
562 * question rather than one for a request path. */
563 12 static uint64_t sa_cache_live(sa_cache *c) {
564 #if SA_HAVE_ATOMICS
565 12 uint64_t b, n = 0, now = sa_now_ms();
566 126 ▶ for (b = 0; b < c->nbuckets; b++) {
Branch: 1 branch
BranchTrueFalseTotal
for (b = 0; b < c->nbuckets; b++) { 114 12 126
567 uint32_t w;
568 1026 ▶ for (w = 0; w < c->nways; w++) {
Branch: 1 branch
BranchTrueFalseTotal
for (w = 0; w < c->nways; w++) { 912 114 1026
569 912 sa_cache_way *e = SA_CWAY_AT(c, b, w);
570 912 ▶ if (sa_at_load32_acq(&e->state) != 1) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_at_load32_acq(&e->state) != 1) continue; 281 631 912
571 631 ▶ if (sa_cache_dead(e, now)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (sa_cache_dead(e, now)) continue; 8 623 631
572 623 n++;
573 }
574 }
575 12 return n;
576 #else
577 (void)c;
578 return 0;
579 #endif
580 }
581  
582 #endif /* SA_CACHE_H */
« xs/hist.xs ↑ Summary xs/cuckoo.xs »