• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright © 2022 Collabora, Ltd.
3  *
4  * Based on Fossilize DB:
5  * Copyright © 2020 Valve Corporation
6  *
7  * SPDX-License-Identifier: MIT
8  */
9 
10 #include "detect_os.h"
11 
12 #if DETECT_OS_WINDOWS == 0
13 
14 #include <fcntl.h>
15 #include <stddef.h>
16 #include <stdlib.h>
17 #include <string.h>
18 #include <sys/file.h>
19 #include <unistd.h>
20 
21 #include "crc32.h"
22 #include "disk_cache.h"
23 #include "hash_table.h"
24 #include "mesa-sha1.h"
25 #include "mesa_cache_db.h"
26 #include "os_time.h"
27 #include "ralloc.h"
28 #include "u_debug.h"
29 #include "u_qsort.h"
30 
31 #define MESA_CACHE_DB_VERSION          1
32 #define MESA_CACHE_DB_MAGIC            "MESA_DB"
33 
34 struct PACKED mesa_db_file_header {
35    char magic[8];
36    uint32_t version;
37    uint64_t uuid;
38 };
39 
40 struct PACKED mesa_cache_db_file_entry {
41    cache_key key;
42    uint32_t crc;
43    uint32_t size;
44 };
45 
46 struct PACKED mesa_index_db_file_entry {
47    uint64_t hash;
48    uint32_t size;
49    uint64_t last_access_time;
50    uint64_t cache_db_file_offset;
51 };
52 
53 struct mesa_index_db_hash_entry {
54    uint64_t cache_db_file_offset;
55    uint64_t index_db_file_offset;
56    uint64_t last_access_time;
57    uint32_t size;
58    bool evicted;
59 };
60 
mesa_db_seek_end(FILE * file)61 static inline bool mesa_db_seek_end(FILE *file)
62 {
63    return !fseek(file, 0, SEEK_END);
64 }
65 
mesa_db_seek(FILE * file,long pos)66 static inline bool mesa_db_seek(FILE *file, long pos)
67 {
68    return !fseek(file, pos, SEEK_SET);
69 }
70 
mesa_db_seek_cur(FILE * file,long pos)71 static inline bool mesa_db_seek_cur(FILE *file, long pos)
72 {
73    return !fseek(file, pos, SEEK_CUR);
74 }
75 
mesa_db_read_data(FILE * file,void * data,size_t size)76 static inline bool mesa_db_read_data(FILE *file, void *data, size_t size)
77 {
78    return fread(data, 1, size, file) == size;
79 }
80 #define mesa_db_read(file, var) mesa_db_read_data(file, var, sizeof(*(var)))
81 
mesa_db_write_data(FILE * file,const void * data,size_t size)82 static inline bool mesa_db_write_data(FILE *file, const void *data, size_t size)
83 {
84    return fwrite(data, 1, size, file) == size;
85 }
86 #define mesa_db_write(file, var) mesa_db_write_data(file, var, sizeof(*(var)))
87 
mesa_db_truncate(FILE * file,long pos)88 static inline bool mesa_db_truncate(FILE *file, long pos)
89 {
90    return !ftruncate(fileno(file), pos);
91 }
92 
93 static bool
94 mesa_db_reopen_file(struct mesa_cache_db_file *db_file);
95 
96 static void
97 mesa_db_close_file(struct mesa_cache_db_file *db_file);
98 
99 static int
mesa_db_flock(FILE * file,int op)100 mesa_db_flock(FILE *file, int op)
101 {
102    int ret;
103 
104    do {
105       ret = flock(fileno(file), op);
106    } while (ret < 0 && errno == EINTR);
107 
108    return ret;
109 }
110 
111 static bool
mesa_db_lock(struct mesa_cache_db * db)112 mesa_db_lock(struct mesa_cache_db *db)
113 {
114    simple_mtx_lock(&db->flock_mtx);
115 
116    if (!mesa_db_reopen_file(&db->index) ||
117        !mesa_db_reopen_file(&db->cache))
118       goto close_files;
119 
120    if (mesa_db_flock(db->cache.file, LOCK_EX) < 0)
121       goto close_files;
122 
123    if (mesa_db_flock(db->index.file, LOCK_EX) < 0)
124       goto unlock_cache;
125 
126    return true;
127 
128 unlock_cache:
129    mesa_db_flock(db->cache.file, LOCK_UN);
130 close_files:
131    mesa_db_close_file(&db->index);
132    mesa_db_close_file(&db->cache);
133 
134    simple_mtx_unlock(&db->flock_mtx);
135 
136    return false;
137 }
138 
139 static void
mesa_db_unlock(struct mesa_cache_db * db)140 mesa_db_unlock(struct mesa_cache_db *db)
141 {
142    mesa_db_flock(db->index.file, LOCK_UN);
143    mesa_db_flock(db->cache.file, LOCK_UN);
144 
145    mesa_db_close_file(&db->index);
146    mesa_db_close_file(&db->cache);
147 
148    simple_mtx_unlock(&db->flock_mtx);
149 }
150 
to_mesa_cache_db_hash(const uint8_t * cache_key_160bit)151 static uint64_t to_mesa_cache_db_hash(const uint8_t *cache_key_160bit)
152 {
153    uint64_t hash = 0;
154 
155    for (unsigned i = 0; i < 8; i++)
156       hash |= ((uint64_t)cache_key_160bit[i]) << i * 8;
157 
158    return hash;
159 }
160 
161 static uint64_t
mesa_db_generate_uuid(void)162 mesa_db_generate_uuid(void)
163 {
164    /* This simple UUID implementation is sufficient for our needs
165     * because UUID is updated rarely. It's nice to make UUID meaningful
166     * and incremental by adding the timestamp to it, which also prevents
167     * the potential collisions. */
168    return ((os_time_get() / 1000000) << 32) | rand();
169 }
170 
171 static bool
mesa_db_read_header(FILE * file,struct mesa_db_file_header * header)172 mesa_db_read_header(FILE *file, struct mesa_db_file_header *header)
173 {
174    rewind(file);
175    fflush(file);
176 
177    if (!mesa_db_read(file, header))
178       return false;
179 
180    if (strncmp(header->magic, MESA_CACHE_DB_MAGIC, sizeof(header->magic)) ||
181        header->version != MESA_CACHE_DB_VERSION || !header->uuid)
182       return false;
183 
184    return true;
185 }
186 
187 static bool
mesa_db_load_header(struct mesa_cache_db_file * db_file)188 mesa_db_load_header(struct mesa_cache_db_file *db_file)
189 {
190    struct mesa_db_file_header header;
191 
192    if (!mesa_db_read_header(db_file->file, &header))
193       return false;
194 
195    db_file->uuid = header.uuid;
196 
197    return true;
198 }
199 
mesa_db_uuid_changed(struct mesa_cache_db * db)200 static bool mesa_db_uuid_changed(struct mesa_cache_db *db)
201 {
202    struct mesa_db_file_header cache_header;
203    struct mesa_db_file_header index_header;
204 
205    if (!mesa_db_read_header(db->cache.file, &cache_header) ||
206        !mesa_db_read_header(db->index.file, &index_header) ||
207        cache_header.uuid != index_header.uuid ||
208        cache_header.uuid != db->uuid)
209       return true;
210 
211    return false;
212 }
213 
214 static bool
mesa_db_write_header(struct mesa_cache_db_file * db_file,uint64_t uuid,bool reset)215 mesa_db_write_header(struct mesa_cache_db_file *db_file,
216                      uint64_t uuid, bool reset)
217 {
218    struct mesa_db_file_header header;
219 
220    rewind(db_file->file);
221 
222    sprintf(header.magic, "MESA_DB");
223    header.version = MESA_CACHE_DB_VERSION;
224    header.uuid = uuid;
225 
226    if (!mesa_db_write(db_file->file, &header))
227       return false;
228 
229    if (reset) {
230       if (!mesa_db_truncate(db_file->file, ftell(db_file->file)))
231          return false;
232    }
233 
234    fflush(db_file->file);
235 
236    return true;
237 }
238 
239 /* Wipe out all database cache files.
240  *
241  * Whenever we get an unmanageable error on reading or writing to the
242  * database file, wipe out the whole database and start over. All the
243  * cached entries will be lost, but the broken cache will be auto-repaired
244  * reliably. Normally cache shall never get corrupted and losing cache
245  * entries is acceptable, hence it's more practical to repair DB using
246  * the simplest method.
247  */
248 static bool
mesa_db_zap(struct mesa_cache_db * db)249 mesa_db_zap(struct mesa_cache_db *db)
250 {
251    /* Disable cache to prevent the recurring faults */
252    db->alive = false;
253 
254    /* Zap corrupted database files to start over from a clean slate */
255    if (!mesa_db_truncate(db->cache.file, 0) ||
256        !mesa_db_truncate(db->index.file, 0))
257       return false;
258 
259    fflush(db->cache.file);
260    fflush(db->index.file);
261 
262    return true;
263 }
264 
265 static bool
mesa_db_index_entry_valid(struct mesa_index_db_file_entry * entry)266 mesa_db_index_entry_valid(struct mesa_index_db_file_entry *entry)
267 {
268    return entry->size && entry->hash &&
269           (int64_t)entry->cache_db_file_offset >= sizeof(struct mesa_db_file_header);
270 }
271 
272 static bool
mesa_db_cache_entry_valid(struct mesa_cache_db_file_entry * entry)273 mesa_db_cache_entry_valid(struct mesa_cache_db_file_entry *entry)
274 {
275    return entry->size && entry->crc;
276 }
277 
278 static bool
mesa_db_update_index(struct mesa_cache_db * db)279 mesa_db_update_index(struct mesa_cache_db *db)
280 {
281    struct mesa_index_db_hash_entry *hash_entry;
282    struct mesa_index_db_file_entry *index_entries, *index_entry;
283    size_t file_length;
284    size_t old_entries, new_entries;
285    size_t new_index_size;
286    bool ret = false;
287    int i;
288 
289    if (!mesa_db_seek_end(db->index.file))
290       return false;
291 
292    file_length = ftell(db->index.file);
293    if (file_length < db->index.offset)
294       return false;
295 
296    if (!mesa_db_seek(db->index.file, db->index.offset))
297       return false;
298 
299    old_entries = _mesa_hash_table_num_entries(db->index_db->table);
300    new_entries = (file_length - db->index.offset) / sizeof(*index_entries);
301    _mesa_hash_table_reserve(db->index_db->table, old_entries + new_entries);
302 
303    new_index_size = new_entries * sizeof(*index_entries);
304    index_entries = malloc(new_index_size);
305    if (!mesa_db_read_data(db->index.file, index_entries, new_index_size))
306       goto error;
307 
308    for (i = 0, index_entry = index_entries; i < new_entries; i++, index_entry++) {
309       /* Check whether the index entry looks valid or we have a corrupted DB */
310       if (!mesa_db_index_entry_valid(index_entry))
311          break;
312 
313       hash_entry = ralloc(db->mem_ctx, struct mesa_index_db_hash_entry);
314       if (!hash_entry)
315          break;
316 
317       hash_entry->cache_db_file_offset = index_entry->cache_db_file_offset;
318       hash_entry->index_db_file_offset = db->index.offset;
319       hash_entry->last_access_time = index_entry->last_access_time;
320       hash_entry->size = index_entry->size;
321 
322       _mesa_hash_table_u64_insert(db->index_db, index_entry->hash, hash_entry);
323 
324       db->index.offset += sizeof(*index_entry);
325    }
326 
327    if (mesa_db_seek(db->index.file, db->index.offset) &&
328        db->index.offset == file_length)
329       ret = true;
330 
331 error:
332    free(index_entries);
333    return ret;
334 }
335 
336 static void
mesa_db_hash_table_reset(struct mesa_cache_db * db)337 mesa_db_hash_table_reset(struct mesa_cache_db *db)
338 {
339    _mesa_hash_table_u64_clear(db->index_db);
340    ralloc_free(db->mem_ctx);
341    db->mem_ctx = ralloc_context(NULL);
342 }
343 
344 static bool
mesa_db_recreate_files(struct mesa_cache_db * db)345 mesa_db_recreate_files(struct mesa_cache_db *db)
346 {
347    db->uuid = mesa_db_generate_uuid();
348 
349    if (!mesa_db_write_header(&db->cache, db->uuid, true) ||
350        !mesa_db_write_header(&db->index, db->uuid, true))
351          return false;
352 
353    return true;
354 }
355 
356 static bool
mesa_db_load(struct mesa_cache_db * db,bool reload)357 mesa_db_load(struct mesa_cache_db *db, bool reload)
358 {
359    /* reloading must be done under the held lock */
360    if (!reload) {
361       if (!mesa_db_lock(db))
362          return false;
363    }
364 
365    /* If file headers are invalid, then zap database files and start over */
366    if (!mesa_db_load_header(&db->cache) ||
367        !mesa_db_load_header(&db->index) ||
368        db->cache.uuid != db->index.uuid) {
369 
370       if (!mesa_db_recreate_files(db))
371          goto fail;
372    } else {
373       db->uuid = db->cache.uuid;
374    }
375 
376    db->index.offset = ftell(db->index.file);
377 
378    if (reload)
379       mesa_db_hash_table_reset(db);
380 
381    /* The update failed so we assume the files are corrupt and
382     * recreate them.
383     */
384    if (!mesa_db_update_index(db)) {
385       mesa_db_recreate_files(db);
386       db->index.offset = ftell(db->index.file);
387 
388       if (!mesa_db_update_index(db))
389          goto fail;
390    }
391 
392    if (!reload)
393       mesa_db_unlock(db);
394 
395    db->alive = true;
396 
397    return true;
398 
399 fail:
400    if (!reload)
401       mesa_db_unlock(db);
402 
403    return false;
404 }
405 
406 static bool
mesa_db_reload(struct mesa_cache_db * db)407 mesa_db_reload(struct mesa_cache_db *db)
408 {
409    fflush(db->cache.file);
410    fflush(db->index.file);
411 
412    return mesa_db_load(db, true);
413 }
414 
415 static FILE *
mesa_db_fopen(const char * path)416 mesa_db_fopen(const char *path)
417 {
418    /* The fopen("r+b") mode doesn't auto-create new file, hence we need to
419     * explicitly create the file first.
420     */
421    int fd = open(path, O_CREAT | O_CLOEXEC | O_RDWR, 0644);
422    if (fd < 0)
423       return NULL;
424 
425    FILE *f = fdopen(fd, "r+b");
426    if (!f)
427       close(fd);
428 
429    return f;
430 }
431 
432 static bool
mesa_db_open_file(struct mesa_cache_db_file * db_file,const char * cache_path,const char * filename)433 mesa_db_open_file(struct mesa_cache_db_file *db_file,
434                   const char *cache_path,
435                   const char *filename)
436 {
437    if (asprintf(&db_file->path, "%s/%s", cache_path, filename) == -1)
438       return false;
439 
440    db_file->file = mesa_db_fopen(db_file->path);
441    if (!db_file->file) {
442       free(db_file->path);
443       return false;
444    }
445 
446    return true;
447 }
448 
449 static bool
mesa_db_reopen_file(struct mesa_cache_db_file * db_file)450 mesa_db_reopen_file(struct mesa_cache_db_file *db_file)
451 {
452    if (db_file->file)
453       return true;
454 
455    db_file->file = mesa_db_fopen(db_file->path);
456    if (!db_file->file)
457       return false;
458 
459    return true;
460 }
461 
462 static void
mesa_db_close_file(struct mesa_cache_db_file * db_file)463 mesa_db_close_file(struct mesa_cache_db_file *db_file)
464 {
465    if (db_file->file) {
466       fclose(db_file->file);
467       db_file->file = NULL;
468    }
469 }
470 
471 static void
mesa_db_free_file(struct mesa_cache_db_file * db_file)472 mesa_db_free_file(struct mesa_cache_db_file *db_file)
473 {
474    if (db_file->file)
475       fclose(db_file->file);
476 
477    free(db_file->path);
478 }
479 
480 static bool
mesa_db_remove_file(struct mesa_cache_db_file * db_file,const char * cache_path,const char * filename)481 mesa_db_remove_file(struct mesa_cache_db_file *db_file,
482                   const char *cache_path,
483                   const char *filename)
484 {
485    if (asprintf(&db_file->path, "%s/%s", cache_path, filename) == -1)
486       return false;
487 
488    unlink(db_file->path);
489 
490    return true;
491 }
492 
493 static int
entry_sort_lru(const void * _a,const void * _b,void * arg)494 entry_sort_lru(const void *_a, const void *_b, void *arg)
495 {
496    const struct mesa_index_db_hash_entry *a = *((const struct mesa_index_db_hash_entry **)_a);
497    const struct mesa_index_db_hash_entry *b = *((const struct mesa_index_db_hash_entry **)_b);
498 
499    /* In practice it's unlikely that we will get two entries with the
500     * same timestamp, but technically it's possible to happen if OS
501     * timer's resolution is low. */
502    if (a->last_access_time == b->last_access_time)
503       return 0;
504 
505    return a->last_access_time > b->last_access_time ? 1 : -1;
506 }
507 
508 static int
entry_sort_offset(const void * _a,const void * _b,void * arg)509 entry_sort_offset(const void *_a, const void *_b, void *arg)
510 {
511    const struct mesa_index_db_hash_entry *a = *((const struct mesa_index_db_hash_entry **)_a);
512    const struct mesa_index_db_hash_entry *b = *((const struct mesa_index_db_hash_entry **)_b);
513    struct mesa_cache_db *db = arg;
514 
515    /* Two entries will never have the identical offset, otherwise DB is
516     * corrupted. */
517    if (a->cache_db_file_offset == b->cache_db_file_offset)
518       mesa_db_zap(db);
519 
520    return a->cache_db_file_offset > b->cache_db_file_offset ? 1 : -1;
521 }
522 
blob_file_size(uint32_t blob_size)523 static uint32_t blob_file_size(uint32_t blob_size)
524 {
525    return sizeof(struct mesa_cache_db_file_entry) + blob_size;
526 }
527 
528 static bool
mesa_db_compact(struct mesa_cache_db * db,int64_t blob_size,struct mesa_index_db_hash_entry * remove_entry)529 mesa_db_compact(struct mesa_cache_db *db, int64_t blob_size,
530                 struct mesa_index_db_hash_entry *remove_entry)
531 {
532    uint32_t num_entries, buffer_size = sizeof(struct mesa_index_db_file_entry);
533    struct mesa_db_file_header cache_header, index_header;
534    FILE *compacted_cache = NULL, *compacted_index = NULL;
535    struct mesa_index_db_file_entry index_entry;
536    struct mesa_index_db_hash_entry **entries;
537    bool success = false, compact = false;
538    void *buffer = NULL;
539    unsigned int i = 0;
540 
541    /* reload index to sync the last access times */
542    if (!remove_entry && !mesa_db_reload(db))
543       return false;
544 
545    num_entries = _mesa_hash_table_num_entries(db->index_db->table);
546    if (!num_entries)
547       return true;
548 
549    entries = calloc(num_entries, sizeof(*entries));
550    if (!entries)
551       return false;
552 
553    compacted_cache = mesa_db_fopen(db->cache.path);
554    compacted_index = mesa_db_fopen(db->index.path);
555    if (!compacted_cache || !compacted_index)
556       goto cleanup;
557 
558    /* The database file has been replaced if UUID changed. We opened
559     * some other cache, stop processing this database. */
560    if (!mesa_db_read_header(compacted_cache, &cache_header) ||
561        !mesa_db_read_header(compacted_index, &index_header) ||
562        cache_header.uuid != db->uuid ||
563        index_header.uuid != db->uuid)
564       goto cleanup;
565 
566    hash_table_foreach(db->index_db->table, entry) {
567       entries[i] = entry->data;
568       entries[i]->evicted = (entries[i] == remove_entry);
569       buffer_size = MAX2(buffer_size, blob_file_size(entries[i]->size));
570       i++;
571    }
572 
573    util_qsort_r(entries, num_entries, sizeof(*entries),
574                 entry_sort_lru, db);
575 
576    for (i = 0; blob_size > 0 && i < num_entries; i++) {
577       blob_size -= blob_file_size(entries[i]->size);
578       entries[i]->evicted = true;
579    }
580 
581    util_qsort_r(entries, num_entries, sizeof(*entries),
582                 entry_sort_offset, db);
583 
584    /* entry_sort_offset() may zap the database */
585    if (!db->alive)
586       goto cleanup;
587 
588    buffer = malloc(buffer_size);
589    if (!buffer)
590       goto cleanup;
591 
592    /* Mark cache file invalid by writing zero-UUID header. If compaction will
593     * fail, then the file will remain to be invalid since we can't repair it. */
594    if (!mesa_db_write_header(&db->cache, 0, false) ||
595        !mesa_db_write_header(&db->index, 0, false))
596       goto cleanup;
597 
598    /* Sync the file pointers */
599    if (!mesa_db_seek(compacted_cache, ftell(db->cache.file)) ||
600        !mesa_db_seek(compacted_index, ftell(db->index.file)))
601       goto cleanup;
602 
603    /* Do the compaction */
604    for (i = 0; i < num_entries; i++) {
605       blob_size = blob_file_size(entries[i]->size);
606 
607       /* Sanity-check the cache-read offset */
608       if (ftell(db->cache.file) != entries[i]->cache_db_file_offset)
609          goto cleanup;
610 
611       if (entries[i]->evicted) {
612          /* Jump over the evicted entry */
613          if (!mesa_db_seek_cur(db->cache.file, blob_size) ||
614              !mesa_db_seek_cur(db->index.file, sizeof(index_entry)))
615             goto cleanup;
616 
617          compact = true;
618          continue;
619       }
620 
621       if (compact) {
622          /* Compact the cache file */
623          if (!mesa_db_read_data(db->cache.file,   buffer, blob_size) ||
624              !mesa_db_cache_entry_valid(buffer) ||
625              !mesa_db_write_data(compacted_cache, buffer, blob_size))
626             goto cleanup;
627 
628          /* Compact the index file */
629          if (!mesa_db_read(db->index.file, &index_entry) ||
630              !mesa_db_index_entry_valid(&index_entry) ||
631              index_entry.cache_db_file_offset != entries[i]->cache_db_file_offset ||
632              index_entry.size != entries[i]->size)
633             goto cleanup;
634 
635          index_entry.cache_db_file_offset = ftell(compacted_cache) - blob_size;
636 
637          if (!mesa_db_write(compacted_index, &index_entry))
638             goto cleanup;
639       } else {
640          /* Sanity-check the cache-write offset */
641          if (ftell(compacted_cache) != entries[i]->cache_db_file_offset)
642             goto cleanup;
643 
644          /* Jump over the unchanged entry */
645          if (!mesa_db_seek_cur(db->index.file,  sizeof(index_entry)) ||
646              !mesa_db_seek_cur(compacted_index, sizeof(index_entry)) ||
647              !mesa_db_seek_cur(db->cache.file,  blob_size) ||
648              !mesa_db_seek_cur(compacted_cache, blob_size))
649             goto cleanup;
650       }
651    }
652 
653    fflush(compacted_cache);
654    fflush(compacted_index);
655 
656    /* Cut off the the freed space left after compaction */
657    if (!mesa_db_truncate(db->cache.file, ftell(compacted_cache)) ||
658        !mesa_db_truncate(db->index.file, ftell(compacted_index)))
659       goto cleanup;
660 
661    /* Set the new UUID to let all cache readers know that the cache was changed */
662    db->uuid = mesa_db_generate_uuid();
663 
664    if (!mesa_db_write_header(&db->cache, db->uuid, false) ||
665        !mesa_db_write_header(&db->index, db->uuid, false))
666       goto cleanup;
667 
668    success = true;
669 
670 cleanup:
671    free(buffer);
672    if (compacted_index)
673       fclose(compacted_index);
674    if (compacted_cache)
675       fclose(compacted_cache);
676    free(entries);
677 
678    /* reload compacted index */
679    if (success && !mesa_db_reload(db))
680       success = false;
681 
682    return success;
683 }
684 
685 bool
mesa_cache_db_open(struct mesa_cache_db * db,const char * cache_path)686 mesa_cache_db_open(struct mesa_cache_db *db, const char *cache_path)
687 {
688    if (!mesa_db_open_file(&db->cache, cache_path, "mesa_cache.db"))
689       return false;
690 
691    if (!mesa_db_open_file(&db->index, cache_path, "mesa_cache.idx"))
692       goto close_cache;
693 
694    db->mem_ctx = ralloc_context(NULL);
695    if (!db->mem_ctx)
696       goto close_index;
697 
698    simple_mtx_init(&db->flock_mtx, mtx_plain);
699 
700    db->index_db = _mesa_hash_table_u64_create(NULL);
701    if (!db->index_db)
702       goto destroy_mtx;
703 
704    if (!mesa_db_load(db, false))
705       goto destroy_hash;
706 
707    return true;
708 
709 destroy_hash:
710    _mesa_hash_table_u64_destroy(db->index_db);
711 destroy_mtx:
712    simple_mtx_destroy(&db->flock_mtx);
713 
714    ralloc_free(db->mem_ctx);
715 close_index:
716    mesa_db_free_file(&db->index);
717 close_cache:
718    mesa_db_free_file(&db->cache);
719 
720    return false;
721 }
722 
723 bool
mesa_db_wipe_path(const char * cache_path)724 mesa_db_wipe_path(const char *cache_path)
725 {
726    struct mesa_cache_db db = {0};
727    bool success = true;
728 
729    if (!mesa_db_remove_file(&db.cache, cache_path, "mesa_cache.db") ||
730        !mesa_db_remove_file(&db.index, cache_path, "mesa_cache.idx"))
731       success = false;
732 
733    free(db.cache.path);
734    free(db.index.path);
735 
736    return success;
737 }
738 
739 void
mesa_cache_db_close(struct mesa_cache_db * db)740 mesa_cache_db_close(struct mesa_cache_db *db)
741 {
742    _mesa_hash_table_u64_destroy(db->index_db);
743    simple_mtx_destroy(&db->flock_mtx);
744    ralloc_free(db->mem_ctx);
745 
746    mesa_db_free_file(&db->index);
747    mesa_db_free_file(&db->cache);
748 }
749 
750 void
mesa_cache_db_set_size_limit(struct mesa_cache_db * db,uint64_t max_cache_size)751 mesa_cache_db_set_size_limit(struct mesa_cache_db *db,
752                              uint64_t max_cache_size)
753 {
754    db->max_cache_size = max_cache_size;
755 }
756 
757 unsigned int
mesa_cache_db_file_entry_size(void)758 mesa_cache_db_file_entry_size(void)
759 {
760    return sizeof(struct mesa_cache_db_file_entry);
761 }
762 
763 void *
mesa_cache_db_read_entry(struct mesa_cache_db * db,const uint8_t * cache_key_160bit,size_t * size)764 mesa_cache_db_read_entry(struct mesa_cache_db *db,
765                          const uint8_t *cache_key_160bit,
766                          size_t *size)
767 {
768    uint64_t hash = to_mesa_cache_db_hash(cache_key_160bit);
769    struct mesa_cache_db_file_entry cache_entry;
770    struct mesa_index_db_file_entry index_entry;
771    struct mesa_index_db_hash_entry *hash_entry;
772    void *data = NULL;
773 
774    if (!mesa_db_lock(db))
775       return NULL;
776 
777    if (!db->alive)
778       goto fail;
779 
780    if (mesa_db_uuid_changed(db) && !mesa_db_reload(db))
781       goto fail_fatal;
782 
783    if (!mesa_db_update_index(db))
784       goto fail_fatal;
785 
786    hash_entry = _mesa_hash_table_u64_search(db->index_db, hash);
787    if (!hash_entry)
788       goto fail;
789 
790    if (!mesa_db_seek(db->cache.file, hash_entry->cache_db_file_offset) ||
791        !mesa_db_read(db->cache.file, &cache_entry) ||
792        !mesa_db_cache_entry_valid(&cache_entry))
793       goto fail_fatal;
794 
795    if (memcmp(cache_entry.key, cache_key_160bit, sizeof(cache_entry.key)))
796       goto fail;
797 
798    data = malloc(cache_entry.size);
799    if (!data)
800       goto fail;
801 
802    if (!mesa_db_read_data(db->cache.file, data, cache_entry.size) ||
803        util_hash_crc32(data, cache_entry.size) != cache_entry.crc)
804       goto fail_fatal;
805 
806    if (!mesa_db_seek(db->index.file, hash_entry->index_db_file_offset) ||
807        !mesa_db_read(db->index.file, &index_entry) ||
808        !mesa_db_index_entry_valid(&index_entry) ||
809        index_entry.cache_db_file_offset != hash_entry->cache_db_file_offset ||
810        index_entry.size != hash_entry->size)
811       goto fail_fatal;
812 
813    index_entry.last_access_time = os_time_get_nano();
814    hash_entry->last_access_time = index_entry.last_access_time;
815 
816    if (!mesa_db_seek(db->index.file, hash_entry->index_db_file_offset) ||
817        !mesa_db_write(db->index.file, &index_entry))
818       goto fail_fatal;
819 
820    fflush(db->index.file);
821 
822    mesa_db_unlock(db);
823 
824    *size = cache_entry.size;
825 
826    return data;
827 
828 fail_fatal:
829    mesa_db_zap(db);
830 fail:
831    free(data);
832 
833    mesa_db_unlock(db);
834 
835    return NULL;
836 }
837 
838 static bool
mesa_cache_db_has_space_locked(struct mesa_cache_db * db,size_t blob_size)839 mesa_cache_db_has_space_locked(struct mesa_cache_db *db, size_t blob_size)
840 {
841    return ftell(db->cache.file) + blob_file_size(blob_size) -
842           sizeof(struct mesa_db_file_header) <= db->max_cache_size;
843 }
844 
845 static size_t
mesa_cache_db_eviction_size(struct mesa_cache_db * db)846 mesa_cache_db_eviction_size(struct mesa_cache_db *db)
847 {
848    return db->max_cache_size / 2 - sizeof(struct mesa_db_file_header);
849 }
850 
851 bool
mesa_cache_db_entry_write(struct mesa_cache_db * db,const uint8_t * cache_key_160bit,const void * blob,size_t blob_size)852 mesa_cache_db_entry_write(struct mesa_cache_db *db,
853                           const uint8_t *cache_key_160bit,
854                           const void *blob, size_t blob_size)
855 {
856    uint64_t hash = to_mesa_cache_db_hash(cache_key_160bit);
857    struct mesa_index_db_hash_entry *hash_entry = NULL;
858    struct mesa_cache_db_file_entry cache_entry;
859    struct mesa_index_db_file_entry index_entry;
860 
861    if (!mesa_db_lock(db))
862       return false;
863 
864    if (!db->alive)
865       goto fail;
866 
867    if (mesa_db_uuid_changed(db) && !mesa_db_reload(db))
868       goto fail_fatal;
869 
870    if (!mesa_db_seek_end(db->cache.file))
871       goto fail_fatal;
872 
873    if (!mesa_cache_db_has_space_locked(db, blob_size)) {
874       if (!mesa_db_compact(db, MAX2(blob_size, mesa_cache_db_eviction_size(db)),
875                            NULL))
876          goto fail_fatal;
877    } else {
878       if (!mesa_db_update_index(db))
879          goto fail_fatal;
880    }
881 
882    hash_entry = _mesa_hash_table_u64_search(db->index_db, hash);
883    if (hash_entry) {
884       hash_entry = NULL;
885       goto fail;
886    }
887 
888    if (!mesa_db_seek_end(db->cache.file) ||
889        !mesa_db_seek_end(db->index.file))
890       goto fail_fatal;
891 
892    memcpy(cache_entry.key, cache_key_160bit, sizeof(cache_entry.key));
893    cache_entry.crc = util_hash_crc32(blob, blob_size);
894    cache_entry.size = blob_size;
895 
896    index_entry.hash = hash;
897    index_entry.size = blob_size;
898    index_entry.last_access_time = os_time_get_nano();
899    index_entry.cache_db_file_offset = ftell(db->cache.file);
900 
901    hash_entry = ralloc(db->mem_ctx, struct mesa_index_db_hash_entry);
902    if (!hash_entry)
903       goto fail;
904 
905    hash_entry->cache_db_file_offset = index_entry.cache_db_file_offset;
906    hash_entry->index_db_file_offset = ftell(db->index.file);
907    hash_entry->last_access_time = index_entry.last_access_time;
908    hash_entry->size = index_entry.size;
909 
910    if (!mesa_db_write(db->cache.file, &cache_entry) ||
911        !mesa_db_write_data(db->cache.file, blob, blob_size) ||
912        !mesa_db_write(db->index.file, &index_entry))
913       goto fail_fatal;
914 
915    fflush(db->cache.file);
916    fflush(db->index.file);
917 
918    db->index.offset = ftell(db->index.file);
919 
920    _mesa_hash_table_u64_insert(db->index_db, hash, hash_entry);
921 
922    mesa_db_unlock(db);
923 
924    return true;
925 
926 fail_fatal:
927    mesa_db_zap(db);
928 fail:
929    mesa_db_unlock(db);
930 
931    if (hash_entry)
932       ralloc_free(hash_entry);
933 
934    return false;
935 }
936 
937 bool
mesa_cache_db_entry_remove(struct mesa_cache_db * db,const uint8_t * cache_key_160bit)938 mesa_cache_db_entry_remove(struct mesa_cache_db *db,
939                            const uint8_t *cache_key_160bit)
940 {
941    uint64_t hash = to_mesa_cache_db_hash(cache_key_160bit);
942    struct mesa_cache_db_file_entry cache_entry;
943    struct mesa_index_db_hash_entry *hash_entry;
944 
945    if (!mesa_db_lock(db))
946       return NULL;
947 
948    if (!db->alive)
949       goto fail;
950 
951    if (mesa_db_uuid_changed(db) && !mesa_db_reload(db))
952       goto fail_fatal;
953 
954    if (!mesa_db_update_index(db))
955       goto fail_fatal;
956 
957    hash_entry = _mesa_hash_table_u64_search(db->index_db, hash);
958    if (!hash_entry)
959       goto fail;
960 
961    if (!mesa_db_seek(db->cache.file, hash_entry->cache_db_file_offset) ||
962        !mesa_db_read(db->cache.file, &cache_entry) ||
963        !mesa_db_cache_entry_valid(&cache_entry))
964       goto fail_fatal;
965 
966    if (memcmp(cache_entry.key, cache_key_160bit, sizeof(cache_entry.key)))
967       goto fail;
968 
969    if (!mesa_db_compact(db, 0, hash_entry))
970       goto fail_fatal;
971 
972    mesa_db_unlock(db);
973 
974    return true;
975 
976 fail_fatal:
977    mesa_db_zap(db);
978 fail:
979    mesa_db_unlock(db);
980 
981    return false;
982 }
983 
984 bool
mesa_cache_db_has_space(struct mesa_cache_db * db,size_t blob_size)985 mesa_cache_db_has_space(struct mesa_cache_db *db, size_t blob_size)
986 {
987    bool has_space;
988 
989    if (!mesa_db_lock(db))
990       return false;
991 
992    if (!mesa_db_seek_end(db->cache.file))
993       goto fail_fatal;
994 
995    has_space = mesa_cache_db_has_space_locked(db, blob_size);
996 
997    mesa_db_unlock(db);
998 
999    return has_space;
1000 
1001 fail_fatal:
1002    mesa_db_zap(db);
1003    mesa_db_unlock(db);
1004 
1005    return false;
1006 }
1007 
1008 static uint64_t
mesa_cache_db_eviction_2x_score_period(void)1009 mesa_cache_db_eviction_2x_score_period(void)
1010 {
1011    const uint64_t nsec_per_sec = 1000000000ull;
1012    static uint64_t period = 0;
1013 
1014    if (period)
1015       return period;
1016 
1017    period = debug_get_num_option("MESA_DISK_CACHE_DATABASE_EVICTION_SCORE_2X_PERIOD",
1018                                  30 * 24 * 60 * 60) * nsec_per_sec;
1019 
1020    return period;
1021 }
1022 
1023 double
mesa_cache_db_eviction_score(struct mesa_cache_db * db)1024 mesa_cache_db_eviction_score(struct mesa_cache_db *db)
1025 {
1026    int64_t eviction_size = mesa_cache_db_eviction_size(db);
1027    struct mesa_index_db_hash_entry **entries;
1028    unsigned num_entries, i = 0;
1029    double eviction_score = 0;
1030 
1031    if (!mesa_db_lock(db))
1032       return 0;
1033 
1034    if (!db->alive)
1035       goto fail;
1036 
1037    if (!mesa_db_reload(db))
1038       goto fail_fatal;
1039 
1040    num_entries = _mesa_hash_table_num_entries(db->index_db->table);
1041    entries = calloc(num_entries, sizeof(*entries));
1042    if (!entries)
1043       goto fail;
1044 
1045    hash_table_foreach(db->index_db->table, entry)
1046       entries[i++] = entry->data;
1047 
1048    util_qsort_r(entries, num_entries, sizeof(*entries),
1049                 entry_sort_lru, db);
1050 
1051    for (i = 0; eviction_size > 0 && i < num_entries; i++) {
1052       uint64_t entry_age = os_time_get_nano() - entries[i]->last_access_time;
1053       unsigned entry_size = blob_file_size(entries[i]->size);
1054 
1055       /* Eviction score is a sum of weighted cache entry sizes,
1056        * where weight doubles for each month of entry's age.
1057        */
1058       uint64_t period = mesa_cache_db_eviction_2x_score_period();
1059       double entry_scale = 1 + (double)entry_age / period;
1060       double entry_score = entry_size * entry_scale;
1061 
1062       eviction_score += entry_score;
1063       eviction_size -= entry_size;
1064    }
1065 
1066    free(entries);
1067 
1068    mesa_db_unlock(db);
1069 
1070    return eviction_score;
1071 
1072 fail_fatal:
1073    mesa_db_zap(db);
1074 fail:
1075    mesa_db_unlock(db);
1076 
1077    return 0;
1078 }
1079 
1080 #endif /* DETECT_OS_WINDOWS */
1081