include/punk/punk_cache.h

filter: Statementstmt 98.7% 159 / 161 Branchbran 92.1% 61 / 76 (9 uncoverable) Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 96.6% 220 / 237 (9 uncoverable) CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/punk/punk_dbiobs.h ↑ Summary include/punk/punk_ws.h »
1 /* punk_cache.h - the in-memory cache store, bounded by BYTES.
2 *
3 * WHY BYTES AND NOT ENTRIES.
4 *
5 * The obvious LRU caps the number of entries, and LRU::Cache in this
6 * workspace is exactly that: XS, O(1), and excellent. But a thousand entries
7 * of ten megabytes is ten gigabytes, so an entry cap does not bound the thing
8 * that runs out. A cache that promises a bound has to bound memory.
9 *
10 * The second reason this matters is less obvious and worse: a per-worker
11 * cache is multiplied by the pool. Under `workers => 8` a 500MB cap is 4GB of
12 * RSS, and every worker caches the same things separately. That is why the
13 * FILE backend is Punk::Cache's default and this one is the opt-in - see
14 * Punk::Cache's documentation, which spells the arithmetic out.
15 *
16 * THE SHAPE.
17 *
18 * A hash table for lookup and an intrusive doubly-linked list for recency:
19 * O(1) get, O(1) set, O(1) eviction. Chained buckets rather than open
20 * addressing, because deletion is a normal operation here (delete, expiry,
21 * eviction) and tombstones in an open table are a slow leak.
22 *
23 * `bytes` is maintained INCREMENTALLY on every insert, overwrite, delete and
24 * eviction. Recomputing it would make set O(n), and a budget checked
25 * occasionally is not a budget. The case that gets missed is the overwrite: a
26 * key replaced from 1KB by 1MB must move the total by the difference, or a
27 * bounded cache quietly stops being bounded.
28 *
29 * Expiry is LAZY - noticed on read. A sweep on the request path is a stall
30 * that grows with the cache.
31 */
32  
33 #ifndef PUNK_CACHE_H
34 #define PUNK_CACHE_H
35  
36 #include <string.h>
37 #include <stdint.h>
38 #include <sys/time.h> /* gettimeofday - expiry needs sub-second */
39  
40 #define PC_BUCKETS_MIN 64
41 #define PC_LOAD_NUM 3 /* grow at 3/4 load */
42 #define PC_LOAD_DEN 4
43  
44 typedef struct pc_entry {
45 struct pc_entry *hnext; /* bucket chain */
46 struct pc_entry *prev, *next; /* recency list; head is newest */
47 uint64_t hash;
48 double expiry; /* epoch seconds; 0 = never */
49 uint32_t klen;
50 uint32_t vlen;
51 char *key;
52 char *val;
53 } pc_entry;
54  
55 typedef struct {
56 pc_entry **buckets;
57 uint32_t nbuckets;
58 uint32_t entries;
59  
60 pc_entry *head, *tail; /* newest .. oldest */
61  
62 size_t bytes; /* held, incrementally maintained */
63 size_t max_bytes;
64  
65 /* cumulative, and reset in a forked child - see punk_cache_check_fork */
66 uint64_t hits, misses, evictions, refused, expired;
67  
68 IV owner_pid;
69  
70 /* mixed into every key's hash, drawn at construction: a table whose
71 * bucket an outsider can compute is a table they can fill one chain of */
72 uint64_t seed;
73 } punk_cache;
74  
75 /* The per-entry overhead counted against the budget.
76 *
77 * Counting only the value would let a million one-byte keys sit under a
78 * "1MB" cap while costing tens of megabytes of structs and allocator
79 * headers - the budget would be honest about the payload and useless about
80 * the memory, which is the failure this whole store exists to avoid. */
81 #define PC_ENTRY_OVERHEAD (sizeof(pc_entry) + 32)
82  
83 1419 static size_t pc_entry_cost(uint32_t klen, uint32_t vlen) {
84 1419 return PC_ENTRY_OVERHEAD + (size_t)klen + (size_t)vlen;
85 }
86  
87 /* Wall clock, for expiry.
88 *
89 * The WALL clock and not a monotonic one, deliberately: a TTL is a promise
90 * about calendar time ("this is good for five minutes"), and it has to survive
91 * being written by one process and read by another - which a monotonic clock,
92 * whose zero is arbitrary per boot, cannot do. The cost is that a large clock
93 * step expires things early or late, and for a cache that is a miss rather
94 * than a fault.
95 *
96 * Sub-second, because a one-second TTL rounded to whole seconds is either
97 * zero or two. */
98 1106 static double pc_now(pTHX) {
99 struct timeval tv;
100 PERL_UNUSED_CONTEXT;
101 1106 gettimeofday(&tv, NULL);
102 1106 return (double)tv.tv_sec + (double)tv.tv_usec / 1e6;
103 }
104  
105 /* ---- the recency list ---------------------------------------------------- */
106  
107 639 static void pc_unlink(punk_cache *c, pc_entry *e) {
108 639 ▶ if (e->prev) e->prev->next = e->next; else c->head = e->next;
Branch: 1 branch
BranchTrueFalseTotal
if (e->prev) e->prev->next = e->next; else c->head = e->next; 629 10 639
109 639 ▶ if (e->next) e->next->prev = e->prev; else c->tail = e->prev; /* # uncoverable condition left count:1 class:ignore_covered_err */
Branch: 1 branch
BranchTrueFalseTotal
if (e->next) e->next->prev = e->prev; else c->tail = e->prev; /* # uncoverable condition left count:1 class:ignore_covered_err */ 0 639 639
110 639 e->prev = e->next = NULL;
111 639 }
112  
113 797 static void pc_push_front(punk_cache *c, pc_entry *e) {
114 797 e->prev = NULL;
115 797 e->next = c->head;
116 797 ▶ if (c->head) c->head->prev = e;
Branch: 1 branch
BranchTrueFalseTotal
if (c->head) c->head->prev = e; 745 52 797
117 797 c->head = e;
118 797 ▶ if (!c->tail) c->tail = e;
Branch: 1 branch
BranchTrueFalseTotal
if (!c->tail) c->tail = e; 52 745 797
119 797 }
120  
121 59 static void pc_touch(punk_cache *c, pc_entry *e) {
122 59 ▶ if (c->head == e) return;
Branch: 1 branch
BranchTrueFalseTotal
if (c->head == e) return; 45 14 59
123 14 pc_unlink(c, e);
124 14 pc_push_front(c, e);
125 }
126  
127 /* ---- the table ----------------------------------------------------------- */
128  
129 /* FNV-1a 64.
130 *
131 * Punk's own, not Hyperman's. hm_atomic.h has the same four lines, but it is
132 * INTERNAL to Hyperman - only hm_abi.h is published through EU::Depends - and
133 * reaching into another dist's private header is precisely the coupling the
134 * ABI pattern exists to prevent. Four lines is a cheaper price than a
135 * dependency on somebody else's internals.
136 *
137 * Not cryptographic and not meant to be: it indexes a bucket, and the file
138 * backend compares the stored key on read so a collision is a miss rather
139 * than a wrong answer. */
140 1497 static uint64_t pc_hash(const char *k, size_t n) {
141 1497 const unsigned char *p = (const unsigned char *)k;
142 1497 uint64_t h = 1469598103934665603ULL;
143 size_t i;
144 46801 ▶ for (i = 0; i < n; i++) { h ^= p[i]; h *= 1099511628211ULL; }
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { h ^= p[i]; h *= 1099511628211ULL; } 45304 1497 46801
145 1497 return h;
146 }
147  
148 /* the table's own hash: the same function over a per-table seed, so the
149 * bucket a key lands in is not something a key's author can arrange. The
150 * file store keeps the unseeded one - its paths must be stable across
151 * processes and restarts. */
152 1147 static uint64_t pc_hash_seeded(const punk_cache *c, const char *k, size_t n) {
153 1147 const unsigned char *p = (const unsigned char *)k;
154 1147 uint64_t h = 1469598103934665603ULL ^ c->seed;
155 size_t i;
156 27630 ▶ for (i = 0; i < n; i++) { h ^= p[i]; h *= 1099511628211ULL; }
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { h ^= p[i]; h *= 1099511628211ULL; } 26483 1147 27630
157 1147 return h;
158 }
159  
160 81 static void pc_table_alloc(pTHX_ punk_cache *c, uint32_t n) {
161 81 Newxz(c->buckets, n, pc_entry *);
162 81 c->nbuckets = n;
163 81 }
164  
165 1 static void pc_rehash(pTHX_ punk_cache *c) {
166 1 ▶ uint32_t old_n = c->nbuckets, i, n = old_n ? old_n * 2 : PC_BUCKETS_MIN; /* # uncoverable condition right count:1 class:ignore_covered_err */
Branch: 1 branch
BranchTrueFalseTotal
uint32_t old_n = c->nbuckets, i, n = old_n ? old_n * 2 : PC_BUCKETS_MIN; /* # uncoverable condition right count:1 class:ignore_covered_err */ 1 0 1
167 1 pc_entry **old = c->buckets;
168 1 pc_table_alloc(aTHX_ c, n);
169 65 ▶ for (i = 0; i < old_n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < old_n; i++) { 64 1 65
170 64 pc_entry *e = old[i];
171 113 ▶ while (e) {
Branch: 1 branch
BranchTrueFalseTotal
while (e) { 49 64 113
172 49 pc_entry *nx = e->hnext;
173 49 uint32_t b = (uint32_t)(e->hash % n);
174 49 e->hnext = c->buckets[b];
175 49 c->buckets[b] = e;
176 49 e = nx;
177 }
178 }
179 /*
180 # uncoverable branch false
181 # uncoverable condition right count:1 class:ignore_covered_err */
182 1 ▶ if (old) Safefree(old);
Branch: 1 branch
BranchTrueFalseTotal
if (old) Safefree(old); 1 0 1
183 1 }
184  
185 1770 static pc_entry *pc_find(punk_cache *c, const char *k, uint32_t klen,
186 uint64_t h, pc_entry ***slot) {
187 1770 uint32_t b = (uint32_t)(h % c->nbuckets);
188 1770 pc_entry **pp = &c->buckets[b], *e;
189 2271 ▶ for (e = *pp; e; pp = &e->hnext, e = e->hnext) {
Branch: 1 branch
BranchTrueFalseTotal
for (e = *pp; e; pp = &e->hnext, e = e->hnext) { 1198 1073 2271
190 /*
191 # uncoverable condition right count:2 class:ignore_covered_err
192 # uncoverable condition right count:3 class:ignore_covered_err */
193 1198 ▶ if (e->hash == h && e->klen == klen && !memcmp(e->key, k, klen)) {
Branch: 3 branches
BranchTrueFalseTotal
if (e->hash == h && e->klen == klen && !memcmp(e->key, k, klen)) { 697 501 1198
if (e->hash == h && e->klen == klen && !memcmp(e->key, k, klen)) { 697 0 697
if (e->hash == h && e->klen == klen && !memcmp(e->key, k, klen)) { 697 0 697
194 697 ▶ if (slot) *slot = pp;
Branch: 1 branch
BranchTrueFalseTotal
if (slot) *slot = pp; 625 72 697
195 697 return e;
196 }
197 }
198 /*
199 # uncoverable branch true
200 # uncoverable condition left count:1 class:ignore_covered_err */
201 1073 ▶ if (slot) *slot = pp;
Branch: 1 branch
BranchTrueFalseTotal
if (slot) *slot = pp; 0 1073 1073
202 1073 return NULL;
203 }
204  
205 625 static void pc_free_entry(pTHX_ punk_cache *c, pc_entry *e) {
206 625 c->bytes -= pc_entry_cost(e->klen, e->vlen);
207 625 c->entries--;
208 625 Safefree(e->key);
209 625 Safefree(e->val);
210 625 Safefree(e);
211 625 }
212  
213 /* Remove an entry that is known to be in the table. */
214 625 static void pc_remove(pTHX_ punk_cache *c, pc_entry *e) {
215 pc_entry **pp;
216 625 (void)pc_find(c, e->key, e->klen, e->hash, &pp);
217 /*
218 # uncoverable branch false
219 # uncoverable condition right count:1 class:ignore_covered_err */
220 625 ▶ if (*pp == e) *pp = e->hnext;
Branch: 1 branch
BranchTrueFalseTotal
if (*pp == e) *pp = e->hnext; 625 0 625
221 625 pc_unlink(c, e);
222 625 pc_free_entry(aTHX_ c, e);
223 625 }
224  
225 /* ---- lifecycle ----------------------------------------------------------- */
226  
227 80 static punk_cache *punk_cache_new(pTHX_ size_t max_bytes) {
228 punk_cache *c;
229 80 Newxz(c, 1, punk_cache);
230 80 c->max_bytes = max_bytes;
231 80 c->owner_pid = (IV)PerlProc_getpid();
232 80 pk_ent_take(aTHX_ (unsigned char *)&c->seed, sizeof c->seed);
233 80 pc_table_alloc(aTHX_ c, PC_BUCKETS_MIN);
234 80 return c;
235 }
236  
237 83 static void punk_cache_clear(pTHX_ punk_cache *c) {
238 83 pc_entry *e = c->head;
239 241 ▶ while (e) {
Branch: 1 branch
BranchTrueFalseTotal
while (e) { 158 83 241
240 158 pc_entry *nx = e->next;
241 158 Safefree(e->key);
242 158 Safefree(e->val);
243 158 Safefree(e);
244 158 e = nx;
245 }
246 83 c->head = c->tail = NULL;
247 83 c->entries = 0;
248 83 c->bytes = 0;
249 /*
250 # uncoverable branch false
251 # uncoverable condition right count:1 class:ignore_covered_err */
252 83 ▶ if (c->buckets) Zero(c->buckets, c->nbuckets, pc_entry *);
Branch: 1 branch
BranchTrueFalseTotal
if (c->buckets) Zero(c->buckets, c->nbuckets, pc_entry *); 83 0 83
253 83 }
254  
255 80 static void punk_cache_free(pTHX_ punk_cache *c) {
256 /*
257 # uncoverable branch true
258 # uncoverable condition left count:1 class:ignore_covered_err */
259 80 ▶ if (!c) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!c) return; 0 80 80
260 80 punk_cache_clear(aTHX_ c);
261 /*
262 # uncoverable branch false
263 # uncoverable condition right count:1 class:ignore_covered_err */
264 80 ▶ if (c->buckets) Safefree(c->buckets);
Branch: 1 branch
BranchTrueFalseTotal
if (c->buckets) Safefree(c->buckets); 80 0 80
265 80 Safefree(c);
266 }
267  
268 /* A worker inherits the parent's entries across a fork, and that is fine -
269 * they are still correct, and re-reading them costs nothing.
270 *
271 * The STATISTICS are not fine. A child reporting the parent's hit count is
272 * reporting a number about a process that is not this one, and an operator
273 * cannot act on it. Same discipline as otel_tracer.h's owner_pid check, for
274 * the same reason: a statistic that silently belongs to someone else is worse
275 * than no statistic. */
276 1193 static void punk_cache_check_fork(pTHX_ punk_cache *c) {
277 1193 IV me = (IV)PerlProc_getpid();
278 /*
279 # uncoverable branch false
280 # uncoverable condition right count:1 class:ignore_covered_err */
281 1193 ▶ if (c->owner_pid == me) return;
Branch: 1 branch
BranchTrueFalseTotal
if (c->owner_pid == me) return; 1193 0 1193
282 0 c->hits = c->misses = c->evictions = c->refused = c->expired = 0; /* # uncoverable statement */
283 0 c->owner_pid = me; /* # uncoverable statement */
284 }
285  
286 /* ---- get / set / delete -------------------------------------------------- */
287  
288 /* The value, or NULL for absent OR expired - a caller does not need to know
289 * which, and a store that distinguished them would leak its expiry policy
290 * into every call site. */
291 114 static const char *punk_cache_get(pTHX_ punk_cache *c, const char *k,
292 uint32_t klen, double now, uint32_t *vlen) {
293 114 uint64_t h = pc_hash_seeded(c, k, klen);
294 pc_entry *e;
295  
296 114 punk_cache_check_fork(aTHX_ c);
297 114 e = pc_find(c, k, klen, h, NULL);
298 114 ▶ if (!e) { c->misses++; return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (!e) { c->misses++; return NULL; } 53 61 114
299  
300 61 ▶ if (e->expiry && e->expiry <= now) {
Branch: 2 branches
BranchTrueFalseTotal
if (e->expiry && e->expiry <= now) { 19 42 61
if (e->expiry && e->expiry <= now) { 5 14 19
301 5 pc_remove(aTHX_ c, e); /* lazy expiry: noticed on the read */
302 5 c->expired++;
303 5 c->misses++;
304 5 return NULL;
305 }
306  
307 56 pc_touch(c, e);
308 56 c->hits++;
309 56 *vlen = e->vlen;
310 56 return e->val;
311 }
312  
313 /* Evict from the tail until the budget is met. O(1) per eviction. */
314 786 static void pc_make_room(pTHX_ punk_cache *c, size_t need) {
315 1398 ▶ while (c->tail && c->bytes + need > c->max_bytes) {
Branch: 2 branches
BranchTrueFalseTotal
while (c->tail && c->bytes + need > c->max_bytes) { 1346 52 1398
while (c->tail && c->bytes + need > c->max_bytes) { 612 734 1346
316 612 pc_remove(aTHX_ c, c->tail);
317 612 c->evictions++;
318 }
319 786 }
320  
321 /* Returns 1 stored, 0 refused.
322 *
323 * A value that cannot fit the budget even in an empty cache is REFUSED, not
324 * stored: making room for it would evict everything else first and then still
325 * be over. Counted, because silently dropping a write is the sort of thing
326 * that is only ever discovered from the outside. */
327 788 static int punk_cache_set(pTHX_ punk_cache *c, const char *k, uint32_t klen,
328 const char *v, uint32_t vlen, double expiry) {
329 788 uint64_t h = pc_hash_seeded(c, k, klen);
330 788 size_t cost = pc_entry_cost(klen, vlen);
331 pc_entry *e;
332  
333 788 punk_cache_check_fork(aTHX_ c);
334 788 ▶ if (cost > c->max_bytes) { c->refused++; return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (cost > c->max_bytes) { c->refused++; return 0; } 2 786 788
335  
336 786 e = pc_find(c, k, klen, h, NULL);
337 786 ▶ if (e) {
Branch: 1 branch
BranchTrueFalseTotal
if (e) { 3 783 786
338 /* OVERWRITE. The total moves by the DIFFERENCE - the case that gets
339 * missed, and the one that turns a bounded cache into an unbounded
340 * one when a key is replaced by something much larger. */
341 /* Always allocate, even for a zero-length value. NULL is how this
342 * store spells ABSENT, so an empty value that allocated nothing would
343 * be indistinguishable from a miss - and an empty string is a value
344 * somebody deliberately cached. The length carries the emptiness. */
345 char *nv;
346 3 ▶ Newx(nv, vlen ? vlen : 1, char); /* # uncoverable condition right count:1 class:ignore_covered_err */
Branch: 1 branch
BranchTrueFalseTotal
Newx(nv, vlen ? vlen : 1, char); /* # uncoverable condition right count:1 class:ignore_covered_err */ 3 0 3
347 /*
348 # uncoverable branch false
349 # uncoverable condition right count:1 class:ignore_covered_err */
350 3 ▶ if (vlen) Copy(v, nv, vlen, char);
Branch: 1 branch
BranchTrueFalseTotal
if (vlen) Copy(v, nv, vlen, char); 3 0 3
351 3 c->bytes -= pc_entry_cost(e->klen, e->vlen);
352 3 Safefree(e->val);
353 3 e->val = nv;
354 3 e->vlen = vlen;
355 3 e->expiry = expiry;
356 3 c->bytes += pc_entry_cost(e->klen, e->vlen);
357 3 pc_touch(c, e);
358 3 pc_make_room(aTHX_ c, 0);
359 3 return 1;
360 }
361  
362 783 pc_make_room(aTHX_ c, cost);
363  
364 783 Newxz(e, 1, pc_entry);
365 783 ▶ Newx(e->key, klen ? klen : 1, char); /* # uncoverable condition right count:1 class:ignore_covered_err */
Branch: 1 branch
BranchTrueFalseTotal
Newx(e->key, klen ? klen : 1, char); /* # uncoverable condition right count:1 class:ignore_covered_err */ 783 0 783
366 /*
367 # uncoverable branch false
368 # uncoverable condition right count:1 class:ignore_covered_err */
369 783 ▶ if (klen) Copy(k, e->key, klen, char);
Branch: 1 branch
BranchTrueFalseTotal
if (klen) Copy(k, e->key, klen, char); 783 0 783
370 783 ▶ Newx(e->val, vlen ? vlen : 1, char); /* never NULL: NULL means absent */
Branch: 1 branch
BranchTrueFalseTotal
Newx(e->val, vlen ? vlen : 1, char); /* never NULL: NULL means absent */ 780 3 783
371 783 ▶ if (vlen) Copy(v, e->val, vlen, char);
Branch: 1 branch
BranchTrueFalseTotal
if (vlen) Copy(v, e->val, vlen, char); 780 3 783
372 783 e->hash = h; e->klen = klen; e->vlen = vlen; e->expiry = expiry;
373  
374 {
375 783 uint32_t b = (uint32_t)(h % c->nbuckets);
376 783 e->hnext = c->buckets[b];
377 783 c->buckets[b] = e;
378 }
379 783 pc_push_front(c, e);
380 783 c->entries++;
381 783 c->bytes += cost;
382  
383 783 ▶ if (c->entries > c->nbuckets / PC_LOAD_DEN * PC_LOAD_NUM)
Branch: 1 branch
BranchTrueFalseTotal
if (c->entries > c->nbuckets / PC_LOAD_DEN * PC_LOAD_NUM) 1 782 783
384 1 pc_rehash(aTHX_ c);
385 783 return 1;
386 }
387  
388 245 static int punk_cache_delete(pTHX_ punk_cache *c, const char *k,
389 uint32_t klen) {
390 245 uint64_t h = pc_hash_seeded(c, k, klen);
391 pc_entry *e;
392 245 punk_cache_check_fork(aTHX_ c);
393 245 e = pc_find(c, k, klen, h, NULL);
394 245 ▶ if (!e) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!e) return 0; 237 8 245
395 8 pc_remove(aTHX_ c, e);
396 8 return 1;
397 }
398  
399 #endif /* PUNK_CACHE_H */
« include/punk/punk_dbiobs.h ↑ Summary include/punk/punk_ws.h »