[Mesa-dev] [PATCH 3/5] util/disk_cache: use LRU eviction rather than random eviction
Timothy Arceri
tarceri at itsqueeze.com
Tue Mar 14 02:08:10 UTC 2017
From: Alan Swanson <reiver at improbability.net>
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 <notasas at gmail.com>
Reviewed-by: Timothy Arceri <tarceri at itsqueeze.com>
---
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
More information about the mesa-dev
mailing list