include/punk/punk_cache.h

filter: Statementstmt 98.7% 159 / 161 Branchbran 80.2% 61 / 76 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 92.8% 220 / 237 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/csrf.xs ↑ Summary blib/lib/Punk/Plugin.pm »
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 1418 static size_t pc_entry_cost(uint32_t klen, uint32_t vlen) {
84 1418 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 1049 static double pc_now(pTHX) {
99 struct timeval tv;
100 PERL_UNUSED_CONTEXT;
101 1049 gettimeofday(&tv, NULL);
102 1049 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;
Branch: 1 branch
BranchTrueFalseTotal
if (e->next) e->next->prev = e->prev; else c->tail = e->prev; 0 639 639
110 639 e->prev = e->next = NULL;
111 639 }
112  
113 796 static void pc_push_front(punk_cache *c, pc_entry *e) {
114 796 e->prev = NULL;
115 796 e->next = c->head;
116 796 ▶ if (c->head) c->head->prev = e;
Branch: 1 branch
BranchTrueFalseTotal
if (c->head) c->head->prev = e; 745 51 796
117 796 c->head = e;
118 796 ▶ if (!c->tail) c->tail = e;
Branch: 1 branch
BranchTrueFalseTotal
if (!c->tail) c->tail = e; 51 745 796
119 796 }
120  
121 58 static void pc_touch(punk_cache *c, pc_entry *e) {
122 58 ▶ if (c->head == e) return;
Branch: 1 branch
BranchTrueFalseTotal
if (c->head == e) return; 44 14 58
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 1380 static uint64_t pc_hash(const char *k, size_t n) {
141 1380 const unsigned char *p = (const unsigned char *)k;
142 1380 uint64_t h = 1469598103934665603ULL;
143 size_t i;
144 39848 ▶ 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; } 38468 1380 39848
145 1380 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 1142 static uint64_t pc_hash_seeded(const punk_cache *c, const char *k, size_t n) {
153 1142 const unsigned char *p = (const unsigned char *)k;
154 1142 uint64_t h = 1469598103934665603ULL ^ c->seed;
155 size_t i;
156 27614 ▶ 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; } 26472 1142 27614
157 1142 return h;
158 }
159  
160 72 static void pc_table_alloc(pTHX_ punk_cache *c, uint32_t n) {
161 72 Newxz(c->buckets, n, pc_entry *);
162 72 c->nbuckets = n;
163 72 }
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;
Branch: 1 branch
BranchTrueFalseTotal
uint32_t old_n = c->nbuckets, i, n = old_n ? old_n * 2 : PC_BUCKETS_MIN; 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 1 ▶ if (old) Safefree(old);
Branch: 1 branch
BranchTrueFalseTotal
if (old) Safefree(old); 1 0 1
180 1 }
181  
182 1765 static pc_entry *pc_find(punk_cache *c, const char *k, uint32_t klen,
183 uint64_t h, pc_entry ***slot) {
184 1765 uint32_t b = (uint32_t)(h % c->nbuckets);
185 1765 pc_entry **pp = &c->buckets[b], *e;
186 2238 ▶ for (e = *pp; e; pp = &e->hnext, e = e->hnext) {
Branch: 1 branch
BranchTrueFalseTotal
for (e = *pp; e; pp = &e->hnext, e = e->hnext) { 1169 1069 2238
187 1169 ▶ 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)) { 696 473 1169
if (e->hash == h && e->klen == klen && !memcmp(e->key, k, klen)) { 696 0 696
if (e->hash == h && e->klen == klen && !memcmp(e->key, k, klen)) { 696 0 696
188 696 ▶ if (slot) *slot = pp;
Branch: 1 branch
BranchTrueFalseTotal
if (slot) *slot = pp; 625 71 696
189 696 return e;
190 }
191 }
192 1069 ▶ if (slot) *slot = pp;
Branch: 1 branch
BranchTrueFalseTotal
if (slot) *slot = pp; 0 1069 1069
193 1069 return NULL;
194 }
195  
196 625 static void pc_free_entry(pTHX_ punk_cache *c, pc_entry *e) {
197 625 c->bytes -= pc_entry_cost(e->klen, e->vlen);
198 625 c->entries--;
199 625 Safefree(e->key);
200 625 Safefree(e->val);
201 625 Safefree(e);
202 625 }
203  
204 /* Remove an entry that is known to be in the table. */
205 625 static void pc_remove(pTHX_ punk_cache *c, pc_entry *e) {
206 pc_entry **pp;
207 625 (void)pc_find(c, e->key, e->klen, e->hash, &pp);
208 625 ▶ if (*pp == e) *pp = e->hnext;
Branch: 1 branch
BranchTrueFalseTotal
if (*pp == e) *pp = e->hnext; 625 0 625
209 625 pc_unlink(c, e);
210 625 pc_free_entry(aTHX_ c, e);
211 625 }
212  
213 /* ---- lifecycle ----------------------------------------------------------- */
214  
215 71 static punk_cache *punk_cache_new(pTHX_ size_t max_bytes) {
216 punk_cache *c;
217 71 Newxz(c, 1, punk_cache);
218 71 c->max_bytes = max_bytes;
219 71 c->owner_pid = (IV)PerlProc_getpid();
220 71 pk_ent_take(aTHX_ (unsigned char *)&c->seed, sizeof c->seed);
221 71 pc_table_alloc(aTHX_ c, PC_BUCKETS_MIN);
222 71 return c;
223 }
224  
225 74 static void punk_cache_clear(pTHX_ punk_cache *c) {
226 74 pc_entry *e = c->head;
227 231 ▶ while (e) {
Branch: 1 branch
BranchTrueFalseTotal
while (e) { 157 74 231
228 157 pc_entry *nx = e->next;
229 157 Safefree(e->key);
230 157 Safefree(e->val);
231 157 Safefree(e);
232 157 e = nx;
233 }
234 74 c->head = c->tail = NULL;
235 74 c->entries = 0;
236 74 c->bytes = 0;
237 74 ▶ if (c->buckets) Zero(c->buckets, c->nbuckets, pc_entry *);
Branch: 1 branch
BranchTrueFalseTotal
if (c->buckets) Zero(c->buckets, c->nbuckets, pc_entry *); 74 0 74
238 74 }
239  
240 71 static void punk_cache_free(pTHX_ punk_cache *c) {
241 71 ▶ if (!c) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!c) return; 0 71 71
242 71 punk_cache_clear(aTHX_ c);
243 71 ▶ if (c->buckets) Safefree(c->buckets);
Branch: 1 branch
BranchTrueFalseTotal
if (c->buckets) Safefree(c->buckets); 71 0 71
244 71 Safefree(c);
245 }
246  
247 /* A worker inherits the parent's entries across a fork, and that is fine -
248 * they are still correct, and re-reading them costs nothing.
249 *
250 * The STATISTICS are not fine. A child reporting the parent's hit count is
251 * reporting a number about a process that is not this one, and an operator
252 * cannot act on it. Same discipline as otel_tracer.h's owner_pid check, for
253 * the same reason: a statistic that silently belongs to someone else is worse
254 * than no statistic. */
255 1188 static void punk_cache_check_fork(pTHX_ punk_cache *c) {
256 1188 IV me = (IV)PerlProc_getpid();
257 1188 ▶ if (c->owner_pid == me) return;
Branch: 1 branch
BranchTrueFalseTotal
if (c->owner_pid == me) return; 1188 0 1188
258 0 c->hits = c->misses = c->evictions = c->refused = c->expired = 0;
259 0 c->owner_pid = me;
260 }
261  
262 /* ---- get / set / delete -------------------------------------------------- */
263  
264 /* The value, or NULL for absent OR expired - a caller does not need to know
265 * which, and a store that distinguished them would leak its expiry policy
266 * into every call site. */
267 110 static const char *punk_cache_get(pTHX_ punk_cache *c, const char *k,
268 uint32_t klen, double now, uint32_t *vlen) {
269 110 uint64_t h = pc_hash_seeded(c, k, klen);
270 pc_entry *e;
271  
272 110 punk_cache_check_fork(aTHX_ c);
273 110 e = pc_find(c, k, klen, h, NULL);
274 110 ▶ if (!e) { c->misses++; return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (!e) { c->misses++; return NULL; } 50 60 110
275  
276 60 ▶ if (e->expiry && e->expiry <= now) {
Branch: 2 branches
BranchTrueFalseTotal
if (e->expiry && e->expiry <= now) { 18 42 60
if (e->expiry && e->expiry <= now) { 5 13 18
277 5 pc_remove(aTHX_ c, e); /* lazy expiry: noticed on the read */
278 5 c->expired++;
279 5 c->misses++;
280 5 return NULL;
281 }
282  
283 55 pc_touch(c, e);
284 55 c->hits++;
285 55 *vlen = e->vlen;
286 55 return e->val;
287 }
288  
289 /* Evict from the tail until the budget is met. O(1) per eviction. */
290 785 static void pc_make_room(pTHX_ punk_cache *c, size_t need) {
291 1397 ▶ while (c->tail && c->bytes + need > c->max_bytes) {
Branch: 2 branches
BranchTrueFalseTotal
while (c->tail && c->bytes + need > c->max_bytes) { 1346 51 1397
while (c->tail && c->bytes + need > c->max_bytes) { 612 734 1346
292 612 pc_remove(aTHX_ c, c->tail);
293 612 c->evictions++;
294 }
295 785 }
296  
297 /* Returns 1 stored, 0 refused.
298 *
299 * A value that cannot fit the budget even in an empty cache is REFUSED, not
300 * stored: making room for it would evict everything else first and then still
301 * be over. Counted, because silently dropping a write is the sort of thing
302 * that is only ever discovered from the outside. */
303 787 static int punk_cache_set(pTHX_ punk_cache *c, const char *k, uint32_t klen,
304 const char *v, uint32_t vlen, double expiry) {
305 787 uint64_t h = pc_hash_seeded(c, k, klen);
306 787 size_t cost = pc_entry_cost(klen, vlen);
307 pc_entry *e;
308  
309 787 punk_cache_check_fork(aTHX_ c);
310 787 ▶ if (cost > c->max_bytes) { c->refused++; return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (cost > c->max_bytes) { c->refused++; return 0; } 2 785 787
311  
312 785 e = pc_find(c, k, klen, h, NULL);
313 785 ▶ if (e) {
Branch: 1 branch
BranchTrueFalseTotal
if (e) { 3 782 785
314 /* OVERWRITE. The total moves by the DIFFERENCE - the case that gets
315 * missed, and the one that turns a bounded cache into an unbounded
316 * one when a key is replaced by something much larger. */
317 /* Always allocate, even for a zero-length value. NULL is how this
318 * store spells ABSENT, so an empty value that allocated nothing would
319 * be indistinguishable from a miss - and an empty string is a value
320 * somebody deliberately cached. The length carries the emptiness. */
321 char *nv;
322 3 ▶ Newx(nv, vlen ? vlen : 1, char);
Branch: 1 branch
BranchTrueFalseTotal
Newx(nv, vlen ? vlen : 1, char); 3 0 3
323 3 ▶ if (vlen) Copy(v, nv, vlen, char);
Branch: 1 branch
BranchTrueFalseTotal
if (vlen) Copy(v, nv, vlen, char); 3 0 3
324 3 c->bytes -= pc_entry_cost(e->klen, e->vlen);
325 3 Safefree(e->val);
326 3 e->val = nv;
327 3 e->vlen = vlen;
328 3 e->expiry = expiry;
329 3 c->bytes += pc_entry_cost(e->klen, e->vlen);
330 3 pc_touch(c, e);
331 3 pc_make_room(aTHX_ c, 0);
332 3 return 1;
333 }
334  
335 782 pc_make_room(aTHX_ c, cost);
336  
337 782 Newxz(e, 1, pc_entry);
338 782 ▶ Newx(e->key, klen ? klen : 1, char);
Branch: 1 branch
BranchTrueFalseTotal
Newx(e->key, klen ? klen : 1, char); 782 0 782
339 782 ▶ if (klen) Copy(k, e->key, klen, char);
Branch: 1 branch
BranchTrueFalseTotal
if (klen) Copy(k, e->key, klen, char); 782 0 782
340 782 ▶ 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 */ 779 3 782
341 782 ▶ if (vlen) Copy(v, e->val, vlen, char);
Branch: 1 branch
BranchTrueFalseTotal
if (vlen) Copy(v, e->val, vlen, char); 779 3 782
342 782 e->hash = h; e->klen = klen; e->vlen = vlen; e->expiry = expiry;
343  
344 {
345 782 uint32_t b = (uint32_t)(h % c->nbuckets);
346 782 e->hnext = c->buckets[b];
347 782 c->buckets[b] = e;
348 }
349 782 pc_push_front(c, e);
350 782 c->entries++;
351 782 c->bytes += cost;
352  
353 782 ▶ 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 781 782
354 1 pc_rehash(aTHX_ c);
355 782 return 1;
356 }
357  
358 245 static int punk_cache_delete(pTHX_ punk_cache *c, const char *k,
359 uint32_t klen) {
360 245 uint64_t h = pc_hash_seeded(c, k, klen);
361 pc_entry *e;
362 245 punk_cache_check_fork(aTHX_ c);
363 245 e = pc_find(c, k, klen, h, NULL);
364 245 ▶ if (!e) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!e) return 0; 237 8 245
365 8 pc_remove(aTHX_ c, e);
366 8 return 1;
367 }
368  
369 #endif /* PUNK_CACHE_H */
« xs/csrf.xs ↑ Summary blib/lib/Punk/Plugin.pm »