From: Alan Swanson <[email protected]> Still using fast random selection of two-character subdirectory in which to check cache files rather than scanning entire cache.
v2: Factor out double strlen call v3: C99 declaration of variables where used Reviewed-by: Grazvydas Ignotas <[email protected]> Reviewed-by: Timothy Arceri <[email protected]> --- src/util/disk_cache.c | 77 +++++++++++++++++++++++---------------------------- 1 file changed, 34 insertions(+), 43 deletions(-) diff --git a/src/util/disk_cache.c b/src/util/disk_cache.c index 5b4f12b..2ab236a 100644 --- a/src/util/disk_cache.c +++ b/src/util/disk_cache.c @@ -467,84 +467,73 @@ make_cache_file_directory(struct disk_cache *cache, const cache_key key) char buf[41]; _mesa_sha1_format(buf, key); if (asprintf(&dir, "%s/%c%c", cache->path, buf[0], buf[1]) == -1) return; mkdir_if_needed(dir); free(dir); } -/* Given a directory path and predicate function, count all entries in - * that directory for which the predicate returns true. Then choose a - * random entry from among those counted. +/* Given a directory path and predicate function, find the entry with + * the oldest access time in that directory for which the predicate + * returns true. * * Returns: A malloc'ed string for the path to the chosen file, (or * NULL on any error). The caller should free the string when * finished. */ static char * -choose_random_file_matching(const char *dir_path, - bool (*predicate)(const struct dirent *, - const char *dir_path)) +choose_lru_file_matching(const char *dir_path, + bool (*predicate)(const struct dirent *, + const char *dir_path)) { DIR *dir; struct dirent *entry; - unsigned int count, victim; char *filename; + char *lru_name = NULL; + time_t lru_atime = 0; dir = opendir(dir_path); if (dir == NULL) return NULL; - count = 0; - while (1) { entry = readdir(dir); if (entry == NULL) break; if (!predicate(entry, dir_path)) continue; - count++; - } - - if (count == 0) { - closedir(dir); - return NULL; - } - - victim = rand() % count; - - rewinddir(dir); - count = 0; - - while (1) { - entry = readdir(dir); - if (entry == NULL) - break; - if (!predicate(entry, dir_path)) - continue; - if (count == victim) - break; - - count++; + struct stat sb; + if (fstatat(dirfd(dir), entry->d_name, &sb, 0) == 0) { + if (!lru_atime || (sb.st_atime < lru_atime)) { + size_t len = strlen(entry->d_name) + 1; + char *tmp = realloc(lru_name, len); + if (tmp) { + lru_name = tmp; + memcpy(lru_name, entry->d_name, len); + lru_atime = sb.st_atime; + } + } + } } - if (entry == NULL) { + if (lru_name == NULL) { closedir(dir); return NULL; } - if (asprintf(&filename, "%s/%s", dir_path, entry->d_name) < 0) + if (asprintf(&filename, "%s/%s", dir_path, lru_name) < 0) filename = NULL; + free(lru_name); closedir(dir); return filename; } /* Is entry a regular file, and not having a name with a trailing * ".tmp" */ static bool is_regular_non_tmp_file(const struct dirent *entry, const char *path) @@ -562,26 +551,26 @@ is_regular_non_tmp_file(const struct dirent *entry, const char *path) size_t len = strlen (entry->d_name); if (len >= 4 && strcmp(&entry->d_name[len-4], ".tmp") == 0) return false; return true; } /* Returns the size of the deleted file, (or 0 on any error). */ static size_t -unlink_random_file_from_directory(const char *path) +unlink_lru_file_from_directory(const char *path) { struct stat sb; char *filename; - filename = choose_random_file_matching(path, is_regular_non_tmp_file); + filename = choose_lru_file_matching(path, is_regular_non_tmp_file); if (filename == NULL) return 0; if (stat(filename, &sb) == -1) { free (filename); return 0; } unlink(filename); free (filename); @@ -631,59 +620,61 @@ is_two_character_sub_directory(const struct dirent *entry, const char *path) closedir(dir); /* If dir only contains '.' and '..' it must be empty */ if (subdir_entries <= 2) return false; return true; } static void -evict_random_item(struct disk_cache *cache) +evict_lru_item(struct disk_cache *cache) { const char hex[] = "0123456789abcde"; char *dir_path; int a, b; size_t size; /* With a reasonably-sized, full cache, (and with keys generated * from a cryptographic hash), we can choose two random hex digits * and reasonably expect the directory to exist with a file in it. + * Provides pseudo-LRU eviction to reduce checking all cache files. */ a = rand() % 16; b = rand() % 16; if (asprintf(&dir_path, "%s/%c%c", cache->path, hex[a], hex[b]) < 0) return; - size = unlink_random_file_from_directory(dir_path); + size = unlink_lru_file_from_directory(dir_path); free(dir_path); if (size) { p_atomic_add(cache->size, - (uint64_t)size); return; } /* In the case where the random choice of directory didn't find - * something, we choose randomly from the existing directories. + * something, we choose the least recently accessed from the + * existing directories. * * Really, the only reason this code exists is to allow the unit * tests to work, (which use an artificially-small cache to be able * to force a single cached item to be evicted). */ - dir_path = choose_random_file_matching(cache->path, - is_two_character_sub_directory); + dir_path = choose_lru_file_matching(cache->path, + is_two_character_sub_directory); if (dir_path == NULL) return; - size = unlink_random_file_from_directory(dir_path); + size = unlink_lru_file_from_directory(dir_path); free(dir_path); if (size) p_atomic_add(cache->size, - (uint64_t)size); } void disk_cache_remove(struct disk_cache *cache, const cache_key key) { @@ -866,21 +857,21 @@ cache_put(void *job, int thread_index) goto done; /* OK, we're now on the hook to write out a file that we know is * not in the cache, and is also not being written out to the cache * by some other process. * * Before we do that, if the cache is too large, evict something * else first. */ if (*dc_job->cache->size + dc_job->size > dc_job->cache->max_size) - evict_random_item(dc_job->cache); + evict_lru_item(dc_job->cache); /* Create CRC of the data and store at the start of the file. We will * read this when restoring the cache and use it to check for corruption. */ struct cache_entry_file_data cf_data; cf_data.crc32 = util_hash_crc32(dc_job->data, dc_job->size); cf_data.uncompressed_size = dc_job->size; size_t cf_data_size = sizeof(cf_data); for (len = 0; len < cf_data_size; len += ret) { -- 2.9.3 _______________________________________________ mesa-dev mailing list [email protected] https://lists.freedesktop.org/mailman/listinfo/mesa-dev
