include/punk/punk_cachefile.h

filter: Statementstmt 89.8% 222 / 247 Branchbran 63.1% 159 / 252 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 76.3% 381 / 499 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/scope.xs ↑ Summary xs/conditionalget.xs »
1 /* punk_cachefile.h - the file cache store.
2 *
3 * WHY THIS IS THE DEFAULT.
4 *
5 * An in-memory store lives in one process, so under a prefork server every
6 * worker keeps its own: `workers => 8` with a 512M cap is four gigabytes of
7 * RSS, and every worker caches the same things separately. The filesystem is
8 * already shared, so this is ONE copy for the whole pool - and it survives a
9 * restart, which memory does not.
10 *
11 * It costs about six microseconds a hit against five nanoseconds for memory.
12 * That ratio sounds decisive and is not: six microseconds is nothing beside a
13 * request about to render a template or query a database.
14 *
15 * THE READ SHAPE, WHICH WAS MEASURED RATHER THAN GUESSED.
16 *
17 * One `read` for the header and key, then `pread` for the value straight into
18 * the caller's buffer. Two syscalls, zero copies.
19 *
20 * The first design read header, key and value separately - three syscalls,
21 * and at 1KB the syscalls ARE the cost, so it lost to a plain stat+read. The
22 * obvious correction, one big read plus a memmove to strip the header, is
23 * worse still at 1MB (41.4us against 28.6): stripping a header off a megabyte
24 * means moving a megabyte, and the copy costs more than the syscall it
25 * saves.
26 *
27 * THE KEY NEVER BECOMES A PATH.
28 *
29 * A cache key is application data and often user data: `../../etc/passwd` is a
30 * valid key, so is one with a NUL, so is a four-kilobyte one. The key is
31 * hashed and the hex sharded two levels deep, and the key itself is stored in
32 * the header and compared on read - so a hash collision is a MISS rather than
33 * a silently wrong value, which makes the hash width a performance question
34 * instead of a correctness one.
35 *
36 * ATOMICITY.
37 *
38 * Write a temp file in the DESTINATION directory and rename. Same directory
39 * because a cross-filesystem rename is not atomic and /tmp is very often
40 * another filesystem. Rename is also why no checksum is needed: a reader
41 * never sees a partial entry, so there is no torn state to detect. A crash
42 * mid-write leaves a temp file, which the sweep removes.
43 */
44  
45 #ifndef PUNK_CACHEFILE_H
46 #define PUNK_CACHEFILE_H
47  
48 #include <stdio.h>
49 #include <stdlib.h>
50 #include <string.h>
51 #include <stdint.h>
52 #include <fcntl.h>
53 #include <unistd.h>
54 #include <dirent.h>
55 #include <errno.h>
56 #include <sys/stat.h>
57 #include <sys/time.h>
58  
59 #define PCF_MAGIC 0x504b4331u /* "PKC1" */
60 #define PCF_PATHMAX 1024
61  
62 /* a snprintf that fit its buffer: a truncated path names some other file */
63 #define PCF_FITS(r, buf) ((r) >= 0 && (size_t)(r) < sizeof (buf))
64 #ifdef O_NOFOLLOW
65 # define PCF_O_NOFOLLOW O_NOFOLLOW
66 #else
67 # define PCF_O_NOFOLLOW 0
68 #endif
69 #define PCF_HEADMAX 4352 /* header + a 4096-byte key */
70  
71 /* On disk: magic, expiry, key length, value length, then key, then value.
72 *
73 * The expiry lives HERE and not in mtime: an expiry stamped in the file
74 * survives a cache-wide default changing, and does not lose to a filesystem
75 * with coarse or lazily updated timestamps. */
76 typedef struct {
77 uint32_t magic;
78 double expiry; /* epoch seconds; 0 = never */
79 uint32_t klen;
80 uint32_t vlen;
81 } pcf_hdr;
82  
83 typedef struct {
84 char dir[PCF_PATHMAX];
85 size_t dirlen;
86 size_t max_bytes;
87 double lock_wait; /* single-flight budget, seconds */
88  
89 /* Amortised eviction. A sweep is a full scan - 273ms for 100k entries -
90 * so it must never run on a write. Instead each process counts what IT
91 * has written and sweeps once that passes a slice of the budget, which
92 * bounds how often the scan happens without putting it in the hot path. */
93 size_t written_since_sweep;
94  
95 uint64_t hits, misses, evictions, refused, expired;
96 /* single-flight locks that could not be attempted - a path that would
97 * not form. Every caller is then told to compute, so a non-zero count
98 * is the herd running unprotected and is worth seeing in the stats. */
99 uint64_t lock_errors;
100 IV owner_pid;
101 } punk_cachefile;
102  
103 512 static double pcf_now(void) {
104 struct timeval tv;
105 512 gettimeofday(&tv, NULL);
106 512 return (double)tv.tv_sec + (double)tv.tv_usec / 1e6;
107 }
108  
109 /* A file's mtime as epoch seconds, to the best resolution this platform
110 * spells - and PCF_MTIME_SLACK, how wrong that can be.
111 *
112 * The lock below judges its holder dead by the age of the lock file. With
113 * whole-second st_mtime a file written at 100.9 reports 100, so at 101.0 its
114 * age reads as 1.0 when it is really 0.1: an age that is too LARGE by up to
115 * a second, which steals a live lock and lets two callers compute at once.
116 * The slack is added to the budget rather than subtracted from the age,
117 * because erring the other way only delays a steal by a second, and a
118 * request that waits a second longer is cheaper than work done twice.
119 *
120 * THE SLACK IS A WHOLE SECOND EVEN WHERE A NANOSECOND FIELD EXISTS. That a
121 * struct stat HAS st_mtim.tv_nsec says the libc spells it, not that the
122 * filesystem fills it: GNU/Hurd's ext2fs has the field and stores zero in it
123 * (CPAN Testers, Punk 0.67, t/0803 on two perls), so the configure probe
124 * that found the field reported sub-second mtime on a box with none. The
125 * lock therefore no longer judges its age by mtime at all - see
126 * pcf_lock_age - and this is only the fallback for a lock file that has no
127 * stamp in it yet. */
128 #if defined(PUNK_STAT_MTIM)
129 # define PCF_MTIME(st) ((double)(st).st_mtime + (double)(st).st_mtim.tv_nsec / 1e9)
130 #elif defined(PUNK_STAT_MTIMESPEC)
131 # define PCF_MTIME(st) ((double)(st).st_mtime + (double)(st).st_mtimespec.tv_nsec / 1e9)
132 #elif defined(PUNK_STAT_MTIMENSEC)
133 # define PCF_MTIME(st) ((double)(st).st_mtime + (double)(st).st_mtimensec / 1e9)
134 #else
135 # define PCF_MTIME(st) ((double)(st).st_mtime)
136 #endif
137 #define PCF_MTIME_SLACK 1.0
138  
139 /* ---- paths --------------------------------------------------------------- */
140  
141 1380 static void pcf_hex16(uint64_t h, char *out) {
142 static const char *H = "0123456789abcdef";
143 int i;
144 23460 ▶ for (i = 15; i >= 0; i--) { out[i] = H[h & 0xF]; h >>= 4; }
Branch: 1 branch
BranchTrueFalseTotal
for (i = 15; i >= 0; i--) { out[i] = H[h & 0xF]; h >>= 4; } 22080 1380 23460
145 1380 out[16] = '\0';
146 1380 }
147  
148 /* <dir>/<h0h1>/<h2h3>/<hex>. Two shard levels, because one directory holding
149 * 100k entries is slow to scan on more filesystems than not. */
150 1380 static int pcf_path(punk_cachefile *c, const char *key, uint32_t klen,
151 char *out, size_t outn, int mkdirs) {
152 char hex[17];
153 1380 pcf_hex16(pc_hash(key, klen), hex);
154 1380 ▶ if (mkdirs) {
Branch: 1 branch
BranchTrueFalseTotal
if (mkdirs) { 989 391 1380
155 char d[PCF_PATHMAX];
156 989 int n = snprintf(d, sizeof d, "%s/%c%c", c->dir, hex[0], hex[1]);
157 989 ▶ if (n < 0 || (size_t)n >= sizeof d) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (n < 0 || (size_t)n >= sizeof d) return -1; 989 0 989
if (n < 0 || (size_t)n >= sizeof d) return -1; 0 989 989
158 989 ▶ if (mkdir(d, 0700) != 0 && errno != EEXIST) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (mkdir(d, 0700) != 0 && errno != EEXIST) return -1; 893 96 989
if (mkdir(d, 0700) != 0 && errno != EEXIST) return -1; 0 893 893
159 989 n = snprintf(d, sizeof d, "%s/%c%c/%c%c", c->dir, hex[0], hex[1],
160 989 hex[2], hex[3]);
161 989 ▶ if (n < 0 || (size_t)n >= sizeof d) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (n < 0 || (size_t)n >= sizeof d) return -1; 989 0 989
if (n < 0 || (size_t)n >= sizeof d) return -1; 0 989 989
162 989 ▶ if (mkdir(d, 0700) != 0 && errno != EEXIST) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (mkdir(d, 0700) != 0 && errno != EEXIST) return -1; 842 147 989
if (mkdir(d, 0700) != 0 && errno != EEXIST) return -1; 0 842 842
163 }
164 {
165 1380 int n = snprintf(out, outn, "%s/%c%c/%c%c/%s", c->dir,
166 1380 hex[0], hex[1], hex[2], hex[3], hex);
167 1380 ▶ if (n < 0 || (size_t)n >= (int)outn) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (n < 0 || (size_t)n >= (int)outn) return -1; 1380 0 1380
if (n < 0 || (size_t)n >= (int)outn) return -1; 0 1380 1380
168 }
169 1380 return 0;
170 }
171  
172 /* ---- lifecycle ----------------------------------------------------------- */
173  
174 71 static punk_cachefile *punk_cachefile_new(pTHX_ const char *dir, size_t dirlen,
175 size_t max_bytes, double lock_wait) {
176 punk_cachefile *c;
177 71 ▶ if (dirlen >= PCF_PATHMAX - 64) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (dirlen >= PCF_PATHMAX - 64) return NULL; 0 71 71
178 71 Newxz(c, 1, punk_cachefile);
179 71 memcpy(c->dir, dir, dirlen);
180 71 c->dir[dirlen] = '\0';
181 71 c->dirlen = dirlen;
182 71 c->max_bytes = max_bytes;
183 71 c->lock_wait = lock_wait;
184 71 c->owner_pid = (IV)PerlProc_getpid();
185 71 return c;
186 }
187  
188 71 static void punk_cachefile_free(pTHX_ punk_cachefile *c) {
189 71 ▶ if (c) Safefree(c);
Branch: 1 branch
BranchTrueFalseTotal
if (c) Safefree(c); 71 0 71
190 71 }
191  
192 /* The entries are on disk and shared, so a fork changes nothing about them.
193 * The COUNTERS are this process's: a child reporting its parent's hit rate is
194 * reporting a number about a different process. */
195 1086 static void punk_cachefile_check_fork(pTHX_ punk_cachefile *c) {
196 1086 IV me = (IV)PerlProc_getpid();
197 1086 ▶ if (c->owner_pid == me) return;
Branch: 1 branch
BranchTrueFalseTotal
if (c->owner_pid == me) return; 1086 0 1086
198 0 c->hits = c->misses = c->evictions = c->refused = c->expired = 0;
199 0 c->lock_errors = 0;
200 0 c->written_since_sweep = 0;
201 0 c->owner_pid = me;
202 }
203  
204 /* ---- reading ------------------------------------------------------------- */
205  
206 /* The value as a new SV (+1), or NULL for absent, expired, or a collision.
207 *
208 * An SV rather than a malloc'd buffer the caller copies out of, because the
209 * caller ALWAYS wanted an SV and the copy was pure loss: a 64K value was
210 * allocated twice, copied twice and freed once on the way to a scalar that
211 * could have been filled directly. On the large path the value is now pread
212 * straight into the SV's own buffer, so there is no copy at all.
213 *
214 * `expiry`, when not NULL, is filled with the entry's own absolute expiry
215 * (0 = never). A memory tier in front of this store has to hold the entry to
216 * the expiry the STORE recorded rather than one counted from the moment it
217 * was faulted in, or the tier serves a value the store considers gone. */
218 347 static SV *punk_cachefile_get_sv(pTHX_ punk_cachefile *c, const char *key,
219 uint32_t klen, double *expiry) {
220 char path[PCF_PATHMAX];
221 char head[PCF_HEADMAX];
222 pcf_hdr h;
223 int fd;
224 ssize_t n;
225 SV *sv;
226  
227 347 punk_cachefile_check_fork(aTHX_ c);
228 347 ▶ if (pcf_path(c, key, klen, path, sizeof path, 0) != 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (pcf_path(c, key, klen, path, sizeof path, 0) != 0) { 0 347 347
229 0 c->misses++;
230 0 return NULL;
231 }
232 347 fd = open(path, O_RDONLY);
233 347 ▶ if (fd < 0) { c->misses++; return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) { c->misses++; return NULL; } 269 78 347
234  
235 78 n = read(fd, head, sizeof head);
236 78 ▶ if (n < (ssize_t)sizeof h) { close(fd); c->misses++; return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (n < (ssize_t)sizeof h) { close(fd); c->misses++; return NULL; } 0 78 78
237 78 memcpy(&h, head, sizeof h);
238  
239 78 ▶ if (h.magic != PCF_MAGIC || h.klen != klen
Branch: 2 branches
BranchTrueFalseTotal
if (h.magic != PCF_MAGIC || h.klen != klen 78 0 78
if (h.magic != PCF_MAGIC || h.klen != klen 78 0 78
240 78 ▶ || (size_t)n < sizeof h + h.klen) {
Branch: 1 branch
BranchTrueFalseTotal
|| (size_t)n < sizeof h + h.klen) { 0 78 78
241 0 close(fd); c->misses++; return NULL;
242 }
243 /* The stored key decides it. A hash collision is a MISS, never a wrong
244 * value handed back as if it were the right one. */
245 78 ▶ if (memcmp(head + sizeof h, key, klen)) {
Branch: 1 branch
BranchTrueFalseTotal
if (memcmp(head + sizeof h, key, klen)) { 1 77 78
246 1 close(fd); c->misses++; return NULL;
247 }
248 77 ▶ if (h.expiry && h.expiry <= pcf_now()) {
Branch: 2 branches
BranchTrueFalseTotal
if (h.expiry && h.expiry <= pcf_now()) { 26 51 77
if (h.expiry && h.expiry <= pcf_now()) { 4 22 26
249 /* Lazy expiry, noticed on the read - of the file that was READ. A
250 * writer renames a fresh entry over this path whenever it likes, and
251 * unlinking by name after that would delete the new value because
252 * the old one had run out. */
253 struct stat held, now;
254 8 ▶ int same = fstat(fd, &held) == 0 && stat(path, &now) == 0
Branch: 1 branch
BranchTrueFalseTotal
int same = fstat(fd, &held) == 0 && stat(path, &now) == 0 4 0 4
255 8 ▶ && held.st_dev == now.st_dev && held.st_ino == now.st_ino;
Branch: 3 branches
BranchTrueFalseTotal
&& held.st_dev == now.st_dev && held.st_ino == now.st_ino; 4 0 4
&& held.st_dev == now.st_dev && held.st_ino == now.st_ino; 4 0 4
&& held.st_dev == now.st_dev && held.st_ino == now.st_ino; 4 0 4
256 4 close(fd);
257 4 ▶ if (same) unlink(path);
Branch: 1 branch
BranchTrueFalseTotal
if (same) unlink(path); 4 0 4
258 4 c->expired++;
259 4 c->misses++;
260 4 return NULL;
261 }
262  
263 73 ▶ if (expiry) *expiry = h.expiry;
Branch: 1 branch
BranchTrueFalseTotal
if (expiry) *expiry = h.expiry; 28 45 73
264  
265 73 ▶ if ((size_t)n >= sizeof h + h.klen + h.vlen) {
Branch: 1 branch
BranchTrueFalseTotal
if ((size_t)n >= sizeof h + h.klen + h.vlen) { 66 7 73
266 /* a small entry arrived whole in the first read */
267 66 sv = newSVpvn(head + sizeof h + h.klen, h.vlen);
268 }
269 else {
270 /* pread straight into the scalar: no copy, and no memmove to strip a
271 * header off a megabyte */
272 ssize_t got;
273 7 sv = newSV(h.vlen + 1);
274 7 SvPOK_only(sv);
275 7 got = pread(fd, SvPVX(sv), h.vlen, (off_t)(sizeof h + h.klen));
276 7 ▶ if (got != (ssize_t)h.vlen) {
Branch: 1 branch
BranchTrueFalseTotal
if (got != (ssize_t)h.vlen) { 0 7 7
277 0 close(fd); SvREFCNT_dec(sv); c->misses++; return NULL;
278 }
279 7 SvCUR_set(sv, (STRLEN)h.vlen);
280 7 *SvEND(sv) = '\0';
281 }
282 73 close(fd);
283 73 c->hits++;
284 73 return sv;
285 }
286  
287 /* ---- eviction ------------------------------------------------------------ */
288  
289 typedef struct { char path[PCF_PATHMAX]; double atime; off_t size; } pcf_ent;
290  
291 /* Walk the cache, dropping expired entries and orphaned temp files, and
292 * evicting the coldest until the budget is met.
293 *
294 * A full scan, deliberately kept OFF the write path: 273ms for 100k entries
295 * is not something a request may pay, and it grows with the cache. */
296 155 static void pcf_sweep(pTHX_ punk_cachefile *c) {
297 155 pcf_ent *ents = NULL;
298 155 size_t n = 0, cap = 0;
299 155 uint64_t total = 0;
300 char l1[PCF_PATHMAX];
301 DIR *d1;
302 struct dirent *e1;
303 155 double now = pcf_now();
304  
305 155 d1 = opendir(c->dir);
306 155 ▶ if (!d1) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!d1) return; 0 155 155
307 856 ▶ while ((e1 = readdir(d1))) {
Branch: 1 branch
BranchTrueFalseTotal
while ((e1 = readdir(d1))) { 701 155 856
308 DIR *d2;
309 struct dirent *e2;
310 701 ▶ if (e1->d_name[0] == '.') continue;
Branch: 1 branch
BranchTrueFalseTotal
if (e1->d_name[0] == '.') continue; 310 391 701
311 391 ▶ if (!PCF_FITS(snprintf(l1, sizeof l1, "%s/%s", c->dir, e1->d_name), l1))
Branch: 2 branches
BranchTrueFalseTotal
if (!PCF_FITS(snprintf(l1, sizeof l1, "%s/%s", c->dir, e1->d_name), l1)) 391 0 391
if (!PCF_FITS(snprintf(l1, sizeof l1, "%s/%s", c->dir, e1->d_name), l1)) 0 391 391
312 0 continue;
313 391 d2 = opendir(l1);
314 391 ▶ if (!d2) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!d2) continue; 0 391 391
315 2860 ▶ while ((e2 = readdir(d2))) {
Branch: 1 branch
BranchTrueFalseTotal
while ((e2 = readdir(d2))) { 2469 391 2860
316 char l2[PCF_PATHMAX];
317 DIR *d3;
318 struct dirent *e3;
319 2469 ▶ if (e2->d_name[0] == '.') continue;
Branch: 1 branch
BranchTrueFalseTotal
if (e2->d_name[0] == '.') continue; 782 1687 2469
320 1687 ▶ if (!PCF_FITS(snprintf(l2, sizeof l2, "%s/%s", l1, e2->d_name), l2))
Branch: 2 branches
BranchTrueFalseTotal
if (!PCF_FITS(snprintf(l2, sizeof l2, "%s/%s", l1, e2->d_name), l2)) 1687 0 1687
if (!PCF_FITS(snprintf(l2, sizeof l2, "%s/%s", l1, e2->d_name), l2)) 0 1687 1687
321 0 continue;
322 1687 d3 = opendir(l2);
323 1687 ▶ if (!d3) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!d3) continue; 0 1687 1687
324 10002 ▶ while ((e3 = readdir(d3))) {
Branch: 1 branch
BranchTrueFalseTotal
while ((e3 = readdir(d3))) { 8315 1687 10002
325 char p[PCF_PATHMAX];
326 struct stat st;
327 8315 ▶ if (e3->d_name[0] == '.') continue;
Branch: 1 branch
BranchTrueFalseTotal
if (e3->d_name[0] == '.') continue; 3374 4941 8315
328 4941 ▶ if (!PCF_FITS(snprintf(p, sizeof p, "%s/%s", l2, e3->d_name), p))
Branch: 2 branches
BranchTrueFalseTotal
if (!PCF_FITS(snprintf(p, sizeof p, "%s/%s", l2, e3->d_name), p)) 4941 0 4941
if (!PCF_FITS(snprintf(p, sizeof p, "%s/%s", l2, e3->d_name), p)) 0 4941 4941
329 0 continue;
330 4941 ▶ if (stat(p, &st) != 0 || !S_ISREG(st.st_mode)) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (stat(p, &st) != 0 || !S_ISREG(st.st_mode)) continue; 4941 0 4941
if (stat(p, &st) != 0 || !S_ISREG(st.st_mode)) continue; 0 4941 4941
331  
332 /* an orphan from a writer that died between create and
333 * rename, or a lock whose holder never came back */
334 4941 ▶ if (strstr(e3->d_name, ".tmp") || strstr(e3->d_name, ".lock")) {
Branch: 2 branches
BranchTrueFalseTotal
if (strstr(e3->d_name, ".tmp") || strstr(e3->d_name, ".lock")) { 4941 0 4941
if (strstr(e3->d_name, ".tmp") || strstr(e3->d_name, ".lock")) { 0 4941 4941
335 0 ▶ if (now - (double)st.st_mtime > 60.0) unlink(p);
Branch: 1 branch
BranchTrueFalseTotal
if (now - (double)st.st_mtime > 60.0) unlink(p); 0 0 0
336 0 continue;
337 }
338 /* expired entries go now rather than waiting to be read */
339 {
340 4941 int fd = open(p, O_RDONLY);
341 pcf_hdr h;
342 4941 ▶ if (fd >= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { 4941 0 4941
343 4941 ssize_t got = read(fd, &h, sizeof h);
344 4941 close(fd);
345 4941 ▶ if (got == (ssize_t)sizeof h && h.magic == PCF_MAGIC
Branch: 2 branches
BranchTrueFalseTotal
if (got == (ssize_t)sizeof h && h.magic == PCF_MAGIC 4941 0 4941
if (got == (ssize_t)sizeof h && h.magic == PCF_MAGIC 4941 0 4941
346 4941 ▶ && h.expiry && h.expiry <= now) {
Branch: 2 branches
BranchTrueFalseTotal
&& h.expiry && h.expiry <= now) { 0 4941 4941
&& h.expiry && h.expiry <= now) { 0 0 0
347 0 unlink(p);
348 0 c->expired++;
349 0 continue;
350 }
351 }
352 }
353 4941 ▶ if (n == cap) {
Branch: 1 branch
BranchTrueFalseTotal
if (n == cap) { 155 4786 4941
354 155 ▶ cap = cap ? cap * 2 : 256;
Branch: 1 branch
BranchTrueFalseTotal
cap = cap ? cap * 2 : 256; 0 155 155
355 155 ▶ Renew(ents, cap, pcf_ent);
Branch: 1 branch
BranchTrueFalseTotal
Renew(ents, cap, pcf_ent); 0 155 155
356 }
357 4941 strncpy(ents[n].path, p, PCF_PATHMAX - 1);
358 4941 ents[n].path[PCF_PATHMAX - 1] = '\0';
359 4941 ents[n].atime = (double)st.st_atime;
360 4941 ents[n].size = st.st_size;
361 4941 total += (uint64_t)st.st_size;
362 4941 n++;
363 }
364 1687 closedir(d3);
365 }
366 391 closedir(d2);
367 }
368 155 closedir(d1);
369  
370 /* Evict coldest-first until the budget is met. A selection pass rather
371 * than a sort: eviction is rare and n can be large, and repeatedly
372 * picking the minimum costs less than ordering everything when only a
373 * few need to go. */
374 662 ▶ while (total > c->max_bytes && n > 0) {
Branch: 2 branches
BranchTrueFalseTotal
while (total > c->max_bytes && n > 0) { 507 155 662
while (total > c->max_bytes && n > 0) { 507 0 507
375 507 size_t i, oldest = 0;
376 16980 ▶ for (i = 1; i < n; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 1; i < n; i++) 16473 507 16980
377 16473 ▶ if (ents[i].atime < ents[oldest].atime) oldest = i;
Branch: 1 branch
BranchTrueFalseTotal
if (ents[i].atime < ents[oldest].atime) oldest = i; 0 16473 16473
378 507 unlink(ents[oldest].path);
379 507 total -= (uint64_t)ents[oldest].size;
380 507 c->evictions++;
381 507 ents[oldest] = ents[n - 1];
382 507 n--;
383 }
384 155 ▶ if (ents) Safefree(ents);
Branch: 1 branch
BranchTrueFalseTotal
if (ents) Safefree(ents); 155 0 155
385 155 c->written_since_sweep = 0;
386 }
387  
388 /* ---- writing ------------------------------------------------------------- */
389  
390 /* Returns 1 stored, 0 refused. */
391 693 static int punk_cachefile_set(pTHX_ punk_cachefile *c, const char *key,
392 uint32_t klen, const char *val, uint32_t vlen,
393 double expiry) {
394 char path[PCF_PATHMAX], tmp[PCF_PATHMAX];
395 pcf_hdr h;
396 693 int fd, ok = 0;
397  
398 693 punk_cachefile_check_fork(aTHX_ c);
399  
400 /* A value that cannot fit the budget even in an empty cache is refused:
401 * making room would evict everything else and still not fit. */
402 693 ▶ if ((size_t)sizeof h + klen + vlen > c->max_bytes) { c->refused++; return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if ((size_t)sizeof h + klen + vlen > c->max_bytes) { c->refused++; return 0; } 3 690 693
403  
404 690 ▶ if (pcf_path(c, key, klen, path, sizeof path, 1) != 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (pcf_path(c, key, klen, path, sizeof path, 1) != 0) return 0; 0 690 690
405 690 ▶ if (!PCF_FITS(snprintf(tmp, sizeof tmp, "%s.tmp%ld", path,
Branch: 2 branches
BranchTrueFalseTotal
if (!PCF_FITS(snprintf(tmp, sizeof tmp, "%s.tmp%ld", path, 690 0 690
if (!PCF_FITS(snprintf(tmp, sizeof tmp, "%s.tmp%ld", path, 0 690 690
406 0 (long)PerlProc_getpid()), tmp)) return 0;
407  
408 /* Exclusive and never through a symlink: a name somebody planted in
409 * the directory must not become a file this writes to. A leftover from
410 * a writer of this pid that died mid-write is unlinked and retried. */
411 690 fd = open(tmp, O_WRONLY | O_CREAT | O_EXCL | PCF_O_NOFOLLOW, 0600);
412 690 ▶ if (fd < 0 && errno == EEXIST) {
Branch: 2 branches
BranchTrueFalseTotal
if (fd < 0 && errno == EEXIST) { 0 690 690
if (fd < 0 && errno == EEXIST) { 0 0 0
413 0 unlink(tmp);
414 0 fd = open(tmp, O_WRONLY | O_CREAT | O_EXCL | PCF_O_NOFOLLOW, 0600);
415 }
416 690 ▶ if (fd < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return 0; 0 690 690
417  
418 690 h.magic = PCF_MAGIC; h.expiry = expiry; h.klen = klen; h.vlen = vlen;
419 690 ▶ if (write(fd, &h, sizeof h) == (ssize_t)sizeof h
Branch: 1 branch
BranchTrueFalseTotal
if (write(fd, &h, sizeof h) == (ssize_t)sizeof h 690 0 690
420 690 ▶ && (!klen || write(fd, key, klen) == (ssize_t)klen)
Branch: 2 branches
BranchTrueFalseTotal
&& (!klen || write(fd, key, klen) == (ssize_t)klen) 690 0 690
&& (!klen || write(fd, key, klen) == (ssize_t)klen) 690 0 690
421 690 ▶ && (!vlen || write(fd, val, vlen) == (ssize_t)vlen))
Branch: 2 branches
BranchTrueFalseTotal
&& (!vlen || write(fd, val, vlen) == (ssize_t)vlen)) 688 2 690
&& (!vlen || write(fd, val, vlen) == (ssize_t)vlen)) 688 0 688
422 690 ok = 1;
423 690 close(fd);
424  
425 690 ▶ if (!ok || rename(tmp, path) != 0) { unlink(tmp); return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (!ok || rename(tmp, path) != 0) { unlink(tmp); return 0; } 690 0 690
if (!ok || rename(tmp, path) != 0) { unlink(tmp); return 0; } 0 690 690
426  
427 /* Amortised: a sweep is a full scan, so it runs once this process has
428 * written a slice of the budget rather than on every set. */
429 690 c->written_since_sweep += sizeof h + klen + vlen;
430 690 ▶ if (c->written_since_sweep > c->max_bytes / 8)
Branch: 1 branch
BranchTrueFalseTotal
if (c->written_since_sweep > c->max_bytes / 8) 152 538 690
431 152 pcf_sweep(aTHX_ c);
432 690 return 1;
433 }
434  
435 9 static int punk_cachefile_delete(pTHX_ punk_cachefile *c, const char *key,
436 uint32_t klen) {
437 char path[PCF_PATHMAX];
438 9 punk_cachefile_check_fork(aTHX_ c);
439 9 ▶ if (pcf_path(c, key, klen, path, sizeof path, 0) != 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (pcf_path(c, key, klen, path, sizeof path, 0) != 0) return 0; 0 9 9
440 9 return unlink(path) == 0 ? 1 : 0;
441 }
442  
443 6 static void pcf_rmtree(const char *dir, int depth) {
444 6 DIR *d = opendir(dir);
445 struct dirent *e;
446 6 ▶ if (!d) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!d) return; 0 6 6
447 32 ▶ while ((e = readdir(d))) {
Branch: 1 branch
BranchTrueFalseTotal
while ((e = readdir(d))) { 26 6 32
448 char p[PCF_PATHMAX];
449 struct stat st;
450 26 ▶ if (e->d_name[0] == '.') continue;
Branch: 1 branch
BranchTrueFalseTotal
if (e->d_name[0] == '.') continue; 12 14 26
451 14 ▶ if (!PCF_FITS(snprintf(p, sizeof p, "%s/%s", dir, e->d_name), p))
Branch: 2 branches
BranchTrueFalseTotal
if (!PCF_FITS(snprintf(p, sizeof p, "%s/%s", dir, e->d_name), p)) 14 0 14
if (!PCF_FITS(snprintf(p, sizeof p, "%s/%s", dir, e->d_name), p)) 0 14 14
452 0 continue;
453 /* lstat: a symlink to a directory elsewhere is unlinked as the
454 * link it is, never descended into */
455 14 ▶ if (lstat(p, &st) != 0) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (lstat(p, &st) != 0) continue; 0 14 14
456 14 ▶ if (S_ISDIR(st.st_mode)) {
Branch: 1 branch
BranchTrueFalseTotal
if (S_ISDIR(st.st_mode)) { 4 10 14
457 4 ▶ if (depth > 0) { pcf_rmtree(p, depth - 1); rmdir(p); }
Branch: 1 branch
BranchTrueFalseTotal
if (depth > 0) { pcf_rmtree(p, depth - 1); rmdir(p); } 4 0 4
458 }
459 10 else unlink(p);
460 }
461 6 closedir(d);
462 }
463  
464 /* Empty the cache. Bounded to the two shard levels this store creates, so a
465 * misconfigured `dir` cannot turn a clear into a recursive delete of
466 * somebody's home directory. */
467 2 static void punk_cachefile_clear(pTHX_ punk_cachefile *c) {
468 2 punk_cachefile_check_fork(aTHX_ c);
469 2 pcf_rmtree(c->dir, 2);
470 2 c->written_since_sweep = 0;
471 2 }
472  
473 /* Current bytes held, for stats. A full scan, so it is asked for rather than
474 * maintained - `stats` is an operator action, not a hot path. */
475 35 static void punk_cachefile_usage(punk_cachefile *c, uint64_t *bytes,
476 uint64_t *entries) {
477 char l1[PCF_PATHMAX];
478 35 DIR *d1 = opendir(c->dir);
479 struct dirent *e1;
480 35 *bytes = *entries = 0;
481 35 ▶ if (!d1) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!d1) return; 0 35 35
482 156 ▶ while ((e1 = readdir(d1))) {
Branch: 1 branch
BranchTrueFalseTotal
while ((e1 = readdir(d1))) { 121 35 156
483 DIR *d2;
484 struct dirent *e2;
485 121 ▶ if (e1->d_name[0] == '.') continue;
Branch: 1 branch
BranchTrueFalseTotal
if (e1->d_name[0] == '.') continue; 70 51 121
486 51 ▶ if (!PCF_FITS(snprintf(l1, sizeof l1, "%s/%s", c->dir, e1->d_name), l1))
Branch: 2 branches
BranchTrueFalseTotal
if (!PCF_FITS(snprintf(l1, sizeof l1, "%s/%s", c->dir, e1->d_name), l1)) 51 0 51
if (!PCF_FITS(snprintf(l1, sizeof l1, "%s/%s", c->dir, e1->d_name), l1)) 0 51 51
487 0 continue;
488 51 d2 = opendir(l1);
489 51 ▶ if (!d2) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!d2) continue; 0 51 51
490 255 ▶ while ((e2 = readdir(d2))) {
Branch: 1 branch
BranchTrueFalseTotal
while ((e2 = readdir(d2))) { 204 51 255
491 char l2[PCF_PATHMAX];
492 DIR *d3;
493 struct dirent *e3;
494 204 ▶ if (e2->d_name[0] == '.') continue;
Branch: 1 branch
BranchTrueFalseTotal
if (e2->d_name[0] == '.') continue; 102 102 204
495 102 ▶ if (!PCF_FITS(snprintf(l2, sizeof l2, "%s/%s", l1, e2->d_name), l2))
Branch: 2 branches
BranchTrueFalseTotal
if (!PCF_FITS(snprintf(l2, sizeof l2, "%s/%s", l1, e2->d_name), l2)) 102 0 102
if (!PCF_FITS(snprintf(l2, sizeof l2, "%s/%s", l1, e2->d_name), l2)) 0 102 102
496 0 continue;
497 102 d3 = opendir(l2);
498 102 ▶ if (!d3) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!d3) continue; 0 102 102
499 434 ▶ while ((e3 = readdir(d3))) {
Branch: 1 branch
BranchTrueFalseTotal
while ((e3 = readdir(d3))) { 332 102 434
500 char p[PCF_PATHMAX];
501 struct stat st;
502 333 ▶ if (e3->d_name[0] == '.') continue;
Branch: 1 branch
BranchTrueFalseTotal
if (e3->d_name[0] == '.') continue; 204 128 332
503 128 ▶ if (strstr(e3->d_name, ".tmp") || strstr(e3->d_name, ".lock"))
Branch: 2 branches
BranchTrueFalseTotal
if (strstr(e3->d_name, ".tmp") || strstr(e3->d_name, ".lock")) 128 0 128
if (strstr(e3->d_name, ".tmp") || strstr(e3->d_name, ".lock")) 1 127 128
504 1 continue;
505 127 ▶ if (!PCF_FITS(snprintf(p, sizeof p, "%s/%s", l2, e3->d_name), p))
Branch: 2 branches
BranchTrueFalseTotal
if (!PCF_FITS(snprintf(p, sizeof p, "%s/%s", l2, e3->d_name), p)) 127 0 127
if (!PCF_FITS(snprintf(p, sizeof p, "%s/%s", l2, e3->d_name), p)) 0 127 127
506 0 continue;
507 127 ▶ if (stat(p, &st) != 0 || !S_ISREG(st.st_mode)) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (stat(p, &st) != 0 || !S_ISREG(st.st_mode)) continue; 127 0 127
if (stat(p, &st) != 0 || !S_ISREG(st.st_mode)) continue; 0 127 127
508 127 *bytes += (uint64_t)st.st_size;
509 127 (*entries)++;
510 }
511 102 closedir(d3);
512 }
513 51 closedir(d2);
514 }
515 35 closedir(d1);
516 }
517  
518 /* ---- single-flight ------------------------------------------------------- *
519 *
520 * When a hot key expires under load every worker misses at once and every one
521 * of them recomputes - the moment a cache is most valuable is the moment it
522 * stops helping.
523 *
524 * O_EXCL makes the winner. Three rules stop it becoming a new way to hang:
525 *
526 * - a loser that waits out its budget COMPUTES ANYWAY. Correctness never
527 * depends on the lock: duplicated work is a cost, a stalled request is an
528 * outage, and a request hanging because another worker died holding the
529 * lock is the worst of the three;
530 * - a STALE lock is stolen, not respected, or one crash poisons a key until
531 * somebody notices;
532 * - the lock covers one compute and nothing unbounded.
533 *
534 * So it is best effort: it collapses the herd in the common case and degrades
535 * to today's behaviour in every unusual one.
536 */
537  
538 /* 1 if this caller won and should compute; 0 if it should look again;
539 * PCF_LOCK_UNAVAILABLE if no lock could be attempted at all.
540 *
541 * The third answer used to be spelled 1, which reads as "you won" and is a
542 * lie: a path that cannot be formed means EVERY caller is told it won, so
543 * the herd this exists to collapse all computes at once, silently. It is
544 * still the caller's business to decide what to do about it - the store is
545 * unusable for this key either way, so computing is the right degradation -
546 * but it is counted now, and it is no longer indistinguishable from
547 * actually holding the lock. */
548 #define PCF_LOCK_UNAVAILABLE (-1)
549  
550 /* The lock file carries its own birth time: the holder's clock, in whole
551 * microseconds, as decimal text. A later caller judges the lock's age with
552 * the SAME clock, so the judgement owes nothing to the filesystem's idea of
553 * time - neither its resolution nor how lazily it stamps a new inode. The
554 * stamp is an integer rather than a "%f" because a perl inside `use locale`
555 * can leave LC_NUMERIC set to a comma, and strtod would then read "1.5" as 1.
556 *
557 * Create and stamp are two steps, and a reader can land between them, so an
558 * EMPTY lock file is read as one being written this instant - unless its
559 * mtime, with the full second of slack, says the writer died in that gap. */
560 302 static int pcf_lock_create(const char *lock) {
561 char buf[32];
562 int n, fd;
563  
564 302 fd = open(lock, O_WRONLY | O_CREAT | O_EXCL, 0600);
565 302 ▶ if (fd < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) return 0; 268 34 302
566 34 n = snprintf(buf, sizeof buf, "%llu",
567 34 (unsigned long long)(pcf_now() * 1e6));
568 34 ▶ if (n > 0 && (size_t)n < sizeof buf) {
Branch: 2 branches
BranchTrueFalseTotal
if (n > 0 && (size_t)n < sizeof buf) { 34 0 34
if (n > 0 && (size_t)n < sizeof buf) { 34 0 34
569 34 ssize_t w = write(fd, buf, (size_t)n);
570 (void)w; /* an unwritten stamp falls back to mtime below */
571 }
572 34 close(fd);
573 34 return 1;
574 }
575  
576 /* How long ago the lock at `lock` was taken, or a negative number when there
577 * is no lock there to judge (it was released between the caller's failed
578 * create and now). */
579 268 static double pcf_lock_age(const char *lock) {
580 char buf[32];
581 struct stat st;
582 268 ssize_t got = -1;
583 268 double now = pcf_now();
584 int fd;
585  
586 268 fd = open(lock, O_RDONLY | PCF_O_NOFOLLOW);
587 268 ▶ if (fd >= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (fd >= 0) { 268 0 268
588 268 got = read(fd, buf, sizeof buf - 1);
589 268 close(fd);
590 }
591 268 ▶ if (got > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (got > 0) { 266 2 268
592 char *end;
593 unsigned long long us;
594 266 buf[got] = '\0';
595 266 errno = 0;
596 266 us = strtoull(buf, &end, 10);
597 266 ▶ if (end != buf && errno == 0) return now - (double)us / 1e6;
Branch: 2 branches
BranchTrueFalseTotal
if (end != buf && errno == 0) return now - (double)us / 1e6; 266 0 266
if (end != buf && errno == 0) return now - (double)us / 1e6; 266 0 266
598 }
599 2 ▶ if (stat(lock, &st) != 0) return -1.0;
Branch: 1 branch
BranchTrueFalseTotal
if (stat(lock, &st) != 0) return -1.0; 0 2 2
600 2 return now - PCF_MTIME(st) - PCF_MTIME_SLACK;
601 }
602  
603 /* `stale` is how old a held lock may be before it is taken for abandoned
604 * and stolen; negative means the store's own lock_wait. */
605 299 static int punk_cachefile_lock_for(pTHX_ punk_cachefile *c, const char *key,
606 uint32_t klen, double stale) {
607 char path[PCF_PATHMAX], lock[PCF_PATHMAX];
608  
609 299 ▶ if (pcf_path(c, key, klen, path, sizeof path, 1) != 0
Branch: 1 branch
BranchTrueFalseTotal
if (pcf_path(c, key, klen, path, sizeof path, 1) != 0 299 0 299
610 299 ▶ || !PCF_FITS(snprintf(lock, sizeof lock, "%s.lock", path), lock)) {
Branch: 2 branches
BranchTrueFalseTotal
|| !PCF_FITS(snprintf(lock, sizeof lock, "%s.lock", path), lock)) { 299 0 299
|| !PCF_FITS(snprintf(lock, sizeof lock, "%s.lock", path), lock)) { 0 299 299
611 0 c->lock_errors++;
612 0 return PCF_LOCK_UNAVAILABLE;
613 }
614  
615 299 ▶ if (pcf_lock_create(lock)) return 1; /* won */
Branch: 1 branch
BranchTrueFalseTotal
if (pcf_lock_create(lock)) return 1; /* won */ 31 268 299
616  
617 /* Somebody holds it. If it is older than the wait budget its holder is
618 * not coming back - steal it rather than obey it. */
619 268 ▶ if (pcf_lock_age(lock) > (stale < 0 ? c->lock_wait : stale)) {
Branch: 2 branches
BranchTrueFalseTotal
if (pcf_lock_age(lock) > (stale < 0 ? c->lock_wait : stale)) { 268 0 268
if (pcf_lock_age(lock) > (stale < 0 ? c->lock_wait : stale)) { 3 265 268
620 3 unlink(lock);
621 3 ▶ if (pcf_lock_create(lock)) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (pcf_lock_create(lock)) return 1; 3 0 3
622 }
623 265 return 0;
624 }
625  
626 64 static int punk_cachefile_lock(pTHX_ punk_cachefile *c, const char *key,
627 uint32_t klen) {
628 64 return punk_cachefile_lock_for(aTHX_ c, key, klen, -1.0);
629 }
630  
631 35 static void punk_cachefile_unlock(pTHX_ punk_cachefile *c, const char *key,
632 uint32_t klen) {
633 char path[PCF_PATHMAX], lock[PCF_PATHMAX];
634 35 ▶ if (pcf_path(c, key, klen, path, sizeof path, 0) != 0) return;
Branch: 1 branch
BranchTrueFalseTotal
if (pcf_path(c, key, klen, path, sizeof path, 0) != 0) return; 0 35 35
635 35 ▶ if (!PCF_FITS(snprintf(lock, sizeof lock, "%s.lock", path), lock)) return;
Branch: 2 branches
BranchTrueFalseTotal
if (!PCF_FITS(snprintf(lock, sizeof lock, "%s.lock", path), lock)) return; 35 0 35
if (!PCF_FITS(snprintf(lock, sizeof lock, "%s.lock", path), lock)) return; 0 35 35
636 35 unlink(lock);
637 }
638  
639 #endif /* PUNK_CACHEFILE_H */
« xs/scope.xs ↑ Summary xs/conditionalget.xs »