80dc7881d591cbef46b1a39fe782f2f447b0e8a2
[mesa.git] / src / util / disk_cache.c
1 /*
2 * Copyright © 2014 Intel Corporation
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21 * IN THE SOFTWARE.
22 */
23
24 #ifdef ENABLE_SHADER_CACHE
25
26 #include <ctype.h>
27 #include <string.h>
28 #include <stdlib.h>
29 #include <stdio.h>
30 #include <sys/file.h>
31 #include <sys/types.h>
32 #include <sys/stat.h>
33 #include <sys/mman.h>
34 #include <unistd.h>
35 #include <fcntl.h>
36 #include <pwd.h>
37 #include <errno.h>
38 #include <dirent.h>
39
40 #include "util/u_atomic.h"
41 #include "util/mesa-sha1.h"
42 #include "util/ralloc.h"
43 #include "main/errors.h"
44
45 #include "disk_cache.h"
46
47 /* Number of bits to mask off from a cache key to get an index. */
48 #define CACHE_INDEX_KEY_BITS 16
49
50 /* Mask for computing an index from a key. */
51 #define CACHE_INDEX_KEY_MASK ((1 << CACHE_INDEX_KEY_BITS) - 1)
52
53 /* The number of keys that can be stored in the index. */
54 #define CACHE_INDEX_MAX_KEYS (1 << CACHE_INDEX_KEY_BITS)
55
56 struct disk_cache {
57 /* The path to the cache directory. */
58 char *path;
59
60 /* A pointer to the mmapped index file within the cache directory. */
61 uint8_t *index_mmap;
62 size_t index_mmap_size;
63
64 /* Pointer to total size of all objects in cache (within index_mmap) */
65 uint64_t *size;
66
67 /* Pointer to stored keys, (within index_mmap). */
68 uint8_t *stored_keys;
69
70 /* Maximum size of all cached objects (in bytes). */
71 uint64_t max_size;
72 };
73
74 /* Create a directory named 'path' if it does not already exist.
75 *
76 * Returns: 0 if path already exists as a directory or if created.
77 * -1 in all other cases.
78 */
79 static int
80 mkdir_if_needed(char *path)
81 {
82 struct stat sb;
83
84 /* If the path exists already, then our work is done if it's a
85 * directory, but it's an error if it is not.
86 */
87 if (stat(path, &sb) == 0) {
88 if (S_ISDIR(sb.st_mode)) {
89 return 0;
90 } else {
91 fprintf(stderr, "Cannot use %s for shader cache (not a directory)"
92 "---disabling.\n", path);
93 return -1;
94 }
95 }
96
97 int ret = mkdir(path, 0755);
98 if (ret == 0 || (ret == -1 && errno == EEXIST))
99 return 0;
100
101 fprintf(stderr, "Failed to create %s for shader cache (%s)---disabling.\n",
102 path, strerror(errno));
103
104 return -1;
105 }
106
107 /* Concatenate an existing path and a new name to form a new path. If the new
108 * path does not exist as a directory, create it then return the resulting
109 * name of the new path (ralloc'ed off of 'ctx').
110 *
111 * Returns NULL on any error, such as:
112 *
113 * <path> does not exist or is not a directory
114 * <path>/<name> exists but is not a directory
115 * <path>/<name> cannot be created as a directory
116 */
117 static char *
118 concatenate_and_mkdir(void *ctx, char *path, char *name)
119 {
120 char *new_path;
121 struct stat sb;
122
123 if (stat(path, &sb) != 0 || ! S_ISDIR(sb.st_mode))
124 return NULL;
125
126 new_path = ralloc_asprintf(ctx, "%s/%s", path, name);
127
128 if (mkdir_if_needed(new_path) == 0)
129 return new_path;
130 else
131 return NULL;
132 }
133
134 struct disk_cache *
135 disk_cache_create(void)
136 {
137 void *local;
138 struct disk_cache *cache = NULL;
139 char *path, *max_size_str;
140 uint64_t max_size;
141 int fd = -1;
142 struct stat sb;
143 size_t size;
144
145 /* A ralloc context for transient data during this invocation. */
146 local = ralloc_context(NULL);
147 if (local == NULL)
148 goto fail;
149
150 /* At user request, disable shader cache entirely. */
151 if (getenv("MESA_GLSL_CACHE_DISABLE"))
152 goto fail;
153
154 /* Determine path for cache based on the first defined name as follows:
155 *
156 * $MESA_GLSL_CACHE_DIR
157 * $XDG_CACHE_HOME/mesa
158 * <pwd.pw_dir>/.cache/mesa
159 */
160 path = getenv("MESA_GLSL_CACHE_DIR");
161 if (path && mkdir_if_needed(path) == -1) {
162 goto fail;
163 }
164
165 if (path == NULL) {
166 char *xdg_cache_home = getenv("XDG_CACHE_HOME");
167
168 if (xdg_cache_home) {
169 if (mkdir_if_needed(xdg_cache_home) == -1)
170 goto fail;
171
172 path = concatenate_and_mkdir(local, xdg_cache_home, "mesa");
173 if (path == NULL)
174 goto fail;
175 }
176 }
177
178 if (path == NULL) {
179 char *buf;
180 size_t buf_size;
181 struct passwd pwd, *result;
182
183 buf_size = sysconf(_SC_GETPW_R_SIZE_MAX);
184 if (buf_size == -1)
185 buf_size = 512;
186
187 /* Loop until buf_size is large enough to query the directory */
188 while (1) {
189 buf = ralloc_size(local, buf_size);
190
191 getpwuid_r(getuid(), &pwd, buf, buf_size, &result);
192 if (result)
193 break;
194
195 if (errno == ERANGE) {
196 ralloc_free(buf);
197 buf = NULL;
198 buf_size *= 2;
199 } else {
200 goto fail;
201 }
202 }
203
204 path = concatenate_and_mkdir(local, pwd.pw_dir, ".cache");
205 if (path == NULL)
206 goto fail;
207
208 path = concatenate_and_mkdir(local, path, "mesa");
209 if (path == NULL)
210 goto fail;
211 }
212
213 cache = ralloc(NULL, struct disk_cache);
214 if (cache == NULL)
215 goto fail;
216
217 cache->path = ralloc_strdup(cache, path);
218 if (cache->path == NULL)
219 goto fail;
220
221 path = ralloc_asprintf(local, "%s/index", cache->path);
222 if (path == NULL)
223 goto fail;
224
225 fd = open(path, O_RDWR | O_CREAT | O_CLOEXEC, 0644);
226 if (fd == -1)
227 goto fail;
228
229 if (fstat(fd, &sb) == -1)
230 goto fail;
231
232 /* Force the index file to be the expected size. */
233 size = sizeof(*cache->size) + CACHE_INDEX_MAX_KEYS * CACHE_KEY_SIZE;
234 if (sb.st_size != size) {
235 if (ftruncate(fd, size) == -1)
236 goto fail;
237 }
238
239 /* We map this shared so that other processes see updates that we
240 * make.
241 *
242 * Note: We do use atomic addition to ensure that multiple
243 * processes don't scramble the cache size recorded in the
244 * index. But we don't use any locking to prevent multiple
245 * processes from updating the same entry simultaneously. The idea
246 * is that if either result lands entirely in the index, then
247 * that's equivalent to a well-ordered write followed by an
248 * eviction and a write. On the other hand, if the simultaneous
249 * writes result in a corrupt entry, that's not really any
250 * different than both entries being evicted, (since within the
251 * guarantees of the cryptographic hash, a corrupt entry is
252 * unlikely to ever match a real cache key).
253 */
254 cache->index_mmap = mmap(NULL, size, PROT_READ | PROT_WRITE,
255 MAP_SHARED, fd, 0);
256 if (cache->index_mmap == MAP_FAILED)
257 goto fail;
258 cache->index_mmap_size = size;
259
260 close(fd);
261
262 cache->size = (uint64_t *) cache->index_mmap;
263 cache->stored_keys = cache->index_mmap + sizeof(uint64_t);
264
265 max_size = 0;
266
267 max_size_str = getenv("MESA_GLSL_CACHE_MAX_SIZE");
268 if (max_size_str) {
269 char *end;
270 max_size = strtoul(max_size_str, &end, 10);
271 if (end == max_size_str) {
272 max_size = 0;
273 } else {
274 while (*end && isspace(*end))
275 end++;
276 switch (*end) {
277 case 'K':
278 case 'k':
279 max_size *= 1024;
280 break;
281 case 'M':
282 case 'm':
283 max_size *= 1024*1024;
284 break;
285 case '\0':
286 case 'G':
287 case 'g':
288 default:
289 max_size *= 1024*1024*1024;
290 break;
291 }
292 }
293 }
294
295 /* Default to 1GB for maximum cache size. */
296 if (max_size == 0)
297 max_size = 1024*1024*1024;
298
299 cache->max_size = max_size;
300
301 ralloc_free(local);
302
303 return cache;
304
305 fail:
306 if (fd != -1)
307 close(fd);
308 if (cache)
309 ralloc_free(cache);
310 ralloc_free(local);
311
312 return NULL;
313 }
314
315 void
316 disk_cache_destroy(struct disk_cache *cache)
317 {
318 munmap(cache->index_mmap, cache->index_mmap_size);
319
320 ralloc_free(cache);
321 }
322
323 /* Return a filename within the cache's directory corresponding to 'key'. The
324 * returned filename is ralloced with 'cache' as the parent context.
325 *
326 * Returns NULL if out of memory.
327 */
328 static char *
329 get_cache_file(struct disk_cache *cache, cache_key key)
330 {
331 char buf[41];
332
333 _mesa_sha1_format(buf, key);
334
335 return ralloc_asprintf(cache, "%s/%c%c/%s",
336 cache->path, buf[0], buf[1], buf + 2);
337 }
338
339 /* Create the directory that will be needed for the cache file for \key.
340 *
341 * Obviously, the implementation here must closely match
342 * _get_cache_file above.
343 */
344 static void
345 make_cache_file_directory(struct disk_cache *cache, cache_key key)
346 {
347 char *dir;
348 char buf[41];
349
350 _mesa_sha1_format(buf, key);
351
352 dir = ralloc_asprintf(cache, "%s/%c%c", cache->path, buf[0], buf[1]);
353
354 mkdir_if_needed(dir);
355
356 ralloc_free(dir);
357 }
358
359 /* Given a directory path and predicate function, count all entries in
360 * that directory for which the predicate returns true. Then choose a
361 * random entry from among those counted.
362 *
363 * Returns: A malloc'ed string for the path to the chosen file, (or
364 * NULL on any error). The caller should free the string when
365 * finished.
366 */
367 static char *
368 choose_random_file_matching(const char *dir_path,
369 bool (*predicate)(struct dirent *))
370 {
371 DIR *dir;
372 struct dirent *entry;
373 unsigned int count, victim;
374 char *filename;
375
376 dir = opendir(dir_path);
377 if (dir == NULL)
378 return NULL;
379
380 count = 0;
381
382 while (1) {
383 entry = readdir(dir);
384 if (entry == NULL)
385 break;
386 if (! predicate(entry))
387 continue;
388
389 count++;
390 }
391
392 if (count == 0) {
393 closedir(dir);
394 return NULL;
395 }
396
397 victim = rand() % count;
398
399 rewinddir(dir);
400 count = 0;
401
402 while (1) {
403 entry = readdir(dir);
404 if (entry == NULL)
405 break;
406 if (! predicate(entry))
407 continue;
408 if (count == victim)
409 break;
410
411 count++;
412 }
413
414 if (entry == NULL) {
415 closedir(dir);
416 return NULL;
417 }
418
419 if (asprintf(&filename, "%s/%s", dir_path, entry->d_name) < 0)
420 filename = NULL;
421
422 closedir(dir);
423
424 return filename;
425 }
426
427 /* Is entry a regular file, and not having a name with a trailing
428 * ".tmp"
429 */
430 static bool
431 is_regular_non_tmp_file(struct dirent *entry)
432 {
433 size_t len;
434
435 if (entry->d_type != DT_REG)
436 return false;
437
438 len = strlen (entry->d_name);
439 if (len >= 4 && strcmp(&entry->d_name[len-4], ".tmp") == 0)
440 return false;
441
442 return true;
443 }
444
445 /* Returns the size of the deleted file, (or 0 on any error). */
446 static size_t
447 unlink_random_file_from_directory(const char *path)
448 {
449 struct stat sb;
450 char *filename;
451
452 filename = choose_random_file_matching(path, is_regular_non_tmp_file);
453 if (filename == NULL)
454 return 0;
455
456 if (stat(filename, &sb) == -1) {
457 free (filename);
458 return 0;
459 }
460
461 unlink(filename);
462
463 free (filename);
464
465 return sb.st_size;
466 }
467
468 /* Is entry a directory with a two-character name, (and not the
469 * special name of "..")
470 */
471 static bool
472 is_two_character_sub_directory(struct dirent *entry)
473 {
474 if (entry->d_type != DT_DIR)
475 return false;
476
477 if (strlen(entry->d_name) != 2)
478 return false;
479
480 if (strcmp(entry->d_name, "..") == 0)
481 return false;
482
483 return true;
484 }
485
486 static void
487 evict_random_item(struct disk_cache *cache)
488 {
489 const char hex[] = "0123456789abcde";
490 char *dir_path;
491 int a, b;
492 size_t size;
493
494 /* With a reasonably-sized, full cache, (and with keys generated
495 * from a cryptographic hash), we can choose two random hex digits
496 * and reasonably expect the directory to exist with a file in it.
497 */
498 a = rand() % 16;
499 b = rand() % 16;
500
501 if (asprintf(&dir_path, "%s/%c%c", cache->path, hex[a], hex[b]) < 0)
502 return;
503
504 size = unlink_random_file_from_directory(dir_path);
505
506 free(dir_path);
507
508 if (size) {
509 p_atomic_add(cache->size, - size);
510 return;
511 }
512
513 /* In the case where the random choice of directory didn't find
514 * something, we choose randomly from the existing directories.
515 *
516 * Really, the only reason this code exists is to allow the unit
517 * tests to work, (which use an artificially-small cache to be able
518 * to force a single cached item to be evicted).
519 */
520 dir_path = choose_random_file_matching(cache->path,
521 is_two_character_sub_directory);
522 if (dir_path == NULL)
523 return;
524
525 size = unlink_random_file_from_directory(dir_path);
526
527 free(dir_path);
528
529 if (size)
530 p_atomic_add(cache->size, - size);
531 }
532
533 void
534 disk_cache_put(struct disk_cache *cache,
535 cache_key key,
536 const void *data,
537 size_t size)
538 {
539 int fd = -1, fd_final = -1, err, ret;
540 size_t len;
541 char *filename = NULL, *filename_tmp = NULL;
542 const char *p = data;
543
544 filename = get_cache_file(cache, key);
545 if (filename == NULL)
546 goto done;
547
548 /* Write to a temporary file to allow for an atomic rename to the
549 * final destination filename, (to prevent any readers from seeing
550 * a partially written file).
551 */
552 filename_tmp = ralloc_asprintf(cache, "%s.tmp", filename);
553 if (filename_tmp == NULL)
554 goto done;
555
556 fd = open(filename_tmp, O_WRONLY | O_CLOEXEC | O_CREAT, 0644);
557
558 /* Make the two-character subdirectory within the cache as needed. */
559 if (fd == -1) {
560 if (errno != ENOENT)
561 goto done;
562
563 make_cache_file_directory(cache, key);
564
565 fd = open(filename_tmp, O_WRONLY | O_CLOEXEC | O_CREAT, 0644);
566 if (fd == -1)
567 goto done;
568 }
569
570 /* With the temporary file open, we take an exclusive flock on
571 * it. If the flock fails, then another process still has the file
572 * open with the flock held. So just let that file be responsible
573 * for writing the file.
574 */
575 err = flock(fd, LOCK_EX | LOCK_NB);
576 if (err == -1)
577 goto done;
578
579 /* Now that we have the lock on the open temporary file, we can
580 * check to see if the destination file already exists. If so,
581 * another process won the race between when we saw that the file
582 * didn't exist and now. In this case, we don't do anything more,
583 * (to ensure the size accounting of the cache doesn't get off).
584 */
585 fd_final = open(filename, O_RDONLY | O_CLOEXEC);
586 if (fd_final != -1)
587 goto done;
588
589 /* OK, we're now on the hook to write out a file that we know is
590 * not in the cache, and is also not being written out to the cache
591 * by some other process.
592 *
593 * Before we do that, if the cache is too large, evict something
594 * else first.
595 */
596 if (*cache->size + size > cache->max_size)
597 evict_random_item(cache);
598
599 /* Now, finally, write out the contents to the temporary file, then
600 * rename them atomically to the destination filename, and also
601 * perform an atomic increment of the total cache size.
602 */
603 for (len = 0; len < size; len += ret) {
604 ret = write(fd, p + len, size - len);
605 if (ret == -1) {
606 unlink(filename_tmp);
607 goto done;
608 }
609 }
610
611 rename(filename_tmp, filename);
612
613 p_atomic_add(cache->size, size);
614
615 done:
616 if (fd_final != -1)
617 close(fd_final);
618 /* This close finally releases the flock, (now that the final dile
619 * has been renamed into place and the size has been added).
620 */
621 if (fd != -1)
622 close(fd);
623 if (filename_tmp)
624 ralloc_free(filename_tmp);
625 if (filename)
626 ralloc_free(filename);
627 }
628
629 void *
630 disk_cache_get(struct disk_cache *cache, cache_key key, size_t *size)
631 {
632 int fd = -1, ret, len;
633 struct stat sb;
634 char *filename = NULL;
635 uint8_t *data = NULL;
636
637 if (size)
638 *size = 0;
639
640 filename = get_cache_file(cache, key);
641 if (filename == NULL)
642 goto fail;
643
644 fd = open(filename, O_RDONLY | O_CLOEXEC);
645 if (fd == -1)
646 goto fail;
647
648 if (fstat(fd, &sb) == -1)
649 goto fail;
650
651 data = malloc(sb.st_size);
652 if (data == NULL)
653 goto fail;
654
655 for (len = 0; len < sb.st_size; len += ret) {
656 ret = read(fd, data + len, sb.st_size - len);
657 if (ret == -1)
658 goto fail;
659 }
660
661 ralloc_free(filename);
662 close(fd);
663
664 if (size)
665 *size = sb.st_size;
666
667 return data;
668
669 fail:
670 if (data)
671 free(data);
672 if (filename)
673 ralloc_free(filename);
674 if (fd != -1)
675 close(fd);
676
677 return NULL;
678 }
679
680 void
681 disk_cache_put_key(struct disk_cache *cache, cache_key key)
682 {
683 uint32_t *key_chunk = (uint32_t *) key;
684 int i = *key_chunk & CACHE_INDEX_KEY_MASK;
685 unsigned char *entry;
686
687 entry = &cache->stored_keys[i + CACHE_KEY_SIZE];
688
689 memcpy(entry, key, CACHE_KEY_SIZE);
690 }
691
692 /* This function lets us test whether a given key was previously
693 * stored in the cache with disk_cache_put_key(). The implement is
694 * efficient by not using syscalls or hitting the disk. It's not
695 * race-free, but the races are benign. If we race with someone else
696 * calling disk_cache_put_key, then that's just an extra cache miss and an
697 * extra recompile.
698 */
699 bool
700 disk_cache_has_key(struct disk_cache *cache, cache_key key)
701 {
702 uint32_t *key_chunk = (uint32_t *) key;
703 int i = *key_chunk & CACHE_INDEX_KEY_MASK;
704 unsigned char *entry;
705
706 entry = &cache->stored_keys[i + CACHE_KEY_SIZE];
707
708 return memcmp(entry, key, CACHE_KEY_SIZE) == 0;
709 }
710
711 #endif