disk_cache: move evict_lru_item() to an OS specific helper

Reviewed-by: Bas Nieuwenhuizen <bas@basnieuwenhuizen.nl>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/6197>

1 files changed, 187 insertions, 0 deletions

diff --git a/src/util/disk_cache_os.c b/src/util/disk_cache_os.c
index 48b79ac570c..3a146125fbb 100644
--- a/src/util/disk_cache_os.c
+++ b/src/util/disk_cache_os.c
@@ -28,7 +28,9 @@
 
 #else
 
+#include <dirent.h>
 #include <errno.h>
+#include <inttypes.h>
 #include <pwd.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -43,6 +45,7 @@
 #include "util/disk_cache.h"
 #include "util/disk_cache_os.h"
 #include "util/ralloc.h"
+#include "util/rand_xor.h"
 
 /* Create a directory named 'path' if it does not already exist.
  *
@@ -104,6 +107,190 @@ concatenate_and_mkdir(void *ctx, const char *path, const char *name)
       return NULL;
 }
 
+/* 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_lru_file_matching(const char *dir_path,
+                         bool (*predicate)(const char *dir_path,
+                                           const struct stat *,
+                                           const char *, const size_t))
+{
+   DIR *dir;
+   struct dirent *entry;
+   char *filename;
+   char *lru_name = NULL;
+   time_t lru_atime = 0;
+
+   dir = opendir(dir_path);
+   if (dir == NULL)
+      return NULL;
+
+   while (1) {
+      entry = readdir(dir);
+      if (entry == NULL)
+         break;
+
+      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);
+
+            if (!predicate(dir_path, &sb, entry->d_name, len))
+               continue;
+
+            char *tmp = realloc(lru_name, len + 1);
+            if (tmp) {
+               lru_name = tmp;
+               memcpy(lru_name, entry->d_name, len + 1);
+               lru_atime = sb.st_atime;
+            }
+         }
+      }
+   }
+
+   if (lru_name == NULL) {
+      closedir(dir);
+      return NULL;
+   }
+
+   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 char *path, const struct stat *sb,
+                        const char *d_name, const size_t len)
+{
+   if (!S_ISREG(sb->st_mode))
+      return false;
+
+   if (len >= 4 && strcmp(&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_lru_file_from_directory(const char *path)
+{
+   struct stat sb;
+   char *filename;
+
+   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);
+
+   return sb.st_blocks * 512;
+}
+
+/* Is entry a directory with a two-character name, (and not the
+ * special name of ".."). We also return false if the dir is empty.
+ */
+static bool
+is_two_character_sub_directory(const char *path, const struct stat *sb,
+                               const char *d_name, const size_t len)
+{
+   if (!S_ISDIR(sb->st_mode))
+      return false;
+
+   if (len != 2)
+      return false;
+
+   if (strcmp(d_name, "..") == 0)
+      return false;
+
+   char *subdir;
+   if (asprintf(&subdir, "%s/%s", path, d_name) == -1)
+      return false;
+   DIR *dir = opendir(subdir);
+   free(subdir);
+
+   if (dir == NULL)
+     return false;
+
+   unsigned subdir_entries = 0;
+   struct dirent *d;
+   while ((d = readdir(dir)) != NULL) {
+      if(++subdir_entries > 2)
+         break;
+   }
+   closedir(dir);
+
+   /* If dir only contains '.' and '..' it must be empty */
+   if (subdir_entries <= 2)
+      return false;
+
+   return true;
+}
+
+/* Evict least recently used cache item */
+void
+disk_cache_evict_lru_item(struct disk_cache *cache)
+{
+   char *dir_path;
+
+   /* 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.
+    */
+   uint64_t rand64 = rand_xorshift128plus(cache->seed_xorshift128plus);
+   if (asprintf(&dir_path, "%s/%02" PRIx64 , cache->path, rand64 & 0xff) < 0)
+      return;
+
+   size_t 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 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_lru_file_matching(cache->path,
+                                       is_two_character_sub_directory);
+   if (dir_path == NULL)
+      return;
+
+   size = unlink_lru_file_from_directory(dir_path);
+
+   free(dir_path);
+
+   if (size)
+      p_atomic_add(cache->size, - (uint64_t)size);
+}
+
 /* Determine path for cache based on the first defined name as follows:
  *
  *   $MESA_GLSL_CACHE_DIR