util: Use persistent array of index entries

Instead of allocating separate memory for each index entry in the hash
table, use a single array (backed by a mapping of anonymous memory
pages, which allows efficient array resizes) which holds a copy of the
index file contents.

The hash table now references each entry via its offset in the index
file, so that the array address can change on resize.

This eliminates some index file reads and reduces memory management
overhead for the hash table entries. It should be more efficient in
general.

Reviewed-by: Dmitry Osipenko <dmitry.osipenko@collabora.com>
Tested-by: Dmitry Osipenko <dmitry.osipenko@collabora.com>
Acked-by: Timothy Arceri <tarceri@itsqueeze.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/30988>

2 files changed, 177 insertions, 117 deletions

diff --git a/src/util/mesa_cache_db.c b/src/util/mesa_cache_db.c
index c79ccf0e367..356fbce4697 100644
--- a/src/util/mesa_cache_db.c
+++ b/src/util/mesa_cache_db.c
@@ -16,6 +16,7 @@
 #include <stdlib.h>
 #include <string.h>
 #include <sys/file.h>
+#include <sys/mman.h>
 #include <unistd.h>
 
 #include "crc32.h"
@@ -50,14 +51,6 @@ struct PACKED mesa_index_db_file_entry {
    uint64_t cache_db_file_offset;
 };
 
-struct mesa_index_db_hash_entry {
-   uint64_t cache_db_file_offset;
-   uint64_t index_db_file_offset;
-   uint64_t last_access_time;
-   uint32_t size;
-   bool evicted;
-};
-
 static inline bool mesa_db_seek_end(FILE *file)
 {
    return !fseek(file, 0, SEEK_END);
@@ -245,6 +238,34 @@ mesa_db_zap(struct mesa_cache_db *db)
    return true;
 }
 
+static struct mesa_index_db_file_entry *
+mesa_db_index_entry_get(struct mesa_cache_db *db, size_t offset)
+{
+   return (struct mesa_index_db_file_entry *)
+      ((char*)db->index_entries + offset);
+}
+
+static void
+mesa_db_index_entry_insert(struct mesa_cache_db *db,
+                           struct mesa_index_db_file_entry *index_entry)
+{
+   size_t offset = (char*)index_entry - (char*)db->index_entries;
+
+   offset += sizeof(struct mesa_db_file_header);
+   _mesa_hash_table_u64_insert(db->index_db, index_entry->hash, (char*)(intptr_t)offset);
+}
+
+static struct mesa_index_db_file_entry *
+mesa_db_index_entry_search(struct mesa_cache_db *db, uint64_t key)
+{
+   size_t index_offset = (intptr_t)_mesa_hash_table_u64_search(db->index_db, key);
+
+   if (!index_offset)
+      return NULL;
+
+   return mesa_db_index_entry_get(db, index_offset - sizeof(struct mesa_db_file_header));
+}
+
 static bool
 mesa_db_index_entry_valid(struct mesa_index_db_file_entry *entry)
 {
@@ -259,14 +280,65 @@ mesa_db_cache_entry_valid(struct mesa_cache_db_file_entry *entry)
 }
 
 static bool
+mesa_db_resize_index_entries(struct mesa_cache_db *db, off_t size)
+{
+   int page_size = getpagesize();
+   size_t page_mask = page_size - 1;
+   off_t old_num_pages, new_num_pages;
+
+   if (db->index_entries_size == size)
+      return true;
+
+   new_num_pages = (size + page_mask) / page_size;
+
+   if (size) {
+      if (db->index_entries_size) {
+         old_num_pages = (db->index_entries_size + page_mask) / page_size;
+
+         if (new_num_pages != old_num_pages) {
+            db->index_entries = mremap(db->index_entries, old_num_pages * page_size,
+                                       new_num_pages * page_size, MREMAP_MAYMOVE);
+            if (db->index_entries == MAP_FAILED) {
+               fprintf(stderr, "%s: mremap failed with error %d (%s)\n",
+                       __func__, errno, strerror(errno));
+               goto error;
+            }
+         }
+      } else {
+         db->index_entries = mmap(NULL, new_num_pages * page_size, PROT_READ | PROT_WRITE,
+                                  MAP_PRIVATE | MAP_ANONYMOUS | MAP_POPULATE, -1, 0);
+         if (db->index_entries == MAP_FAILED) {
+            fprintf(stderr, "%s: mmap failed with error %d (%s)\n",
+                    __func__, errno, strerror(errno));
+            goto error;
+         }
+      }
+   } else {
+      if (db->index_entries_size) {
+         old_num_pages = (db->index_entries_size + page_mask) / page_size;
+
+         munmap(db->index_entries, old_num_pages * page_size);
+      }
+
+      db->index_entries = NULL;
+   }
+
+   db->index_entries_size = size;
+   return true;
+
+error:
+   _mesa_hash_table_u64_clear(db->index_db);
+   db->index_entries = NULL;
+   db->index_entries_size = 0;
+   return false;
+}
+
+static bool
 mesa_db_update_index(struct mesa_cache_db *db)
 {
-   struct mesa_index_db_hash_entry *hash_entry;
-   struct mesa_index_db_file_entry *index_entries, *index_entry;
+   struct mesa_index_db_file_entry *index_entry;
    size_t file_length;
    size_t old_entries, new_entries;
-   size_t new_index_size;
-   bool ret = false;
    int i;
 
    if (!mesa_db_seek_end(db->index.file))
@@ -279,41 +351,33 @@ mesa_db_update_index(struct mesa_cache_db *db)
    if (!mesa_db_seek(db->index.file, db->index.offset))
       return false;
 
-   old_entries = _mesa_hash_table_num_entries(db->index_db->table);
-   new_entries = (file_length - db->index.offset) / sizeof(*index_entries);
+   new_entries = (file_length - db->index.offset) / sizeof(*index_entry);
+   if (!new_entries)
+      return true;
+
+   old_entries = db->index_entries_size / sizeof(*index_entry);
+
+   if (!mesa_db_resize_index_entries(db, (old_entries + new_entries) * sizeof(*index_entry)))
+      return false;
+
    _mesa_hash_table_reserve(db->index_db->table, old_entries + new_entries);
 
-   new_index_size = new_entries * sizeof(*index_entries);
-   index_entries = malloc(new_index_size);
-   if (!mesa_db_read_data(db->index.file, index_entries, new_index_size))
-      goto error;
+   index_entry = mesa_db_index_entry_get(db, old_entries * sizeof(*index_entry));
+   if (!mesa_db_read_data(db->index.file, index_entry, new_entries * sizeof(*index_entry)))
+      return false;
 
-   for (i = 0, index_entry = index_entries; i < new_entries; i++, index_entry++) {
+   for (i = 0; i < new_entries; i++, index_entry++) {
       /* Check whether the index entry looks valid or we have a corrupted DB */
       if (!mesa_db_index_entry_valid(index_entry))
          break;
 
-      hash_entry = ralloc(db->mem_ctx, struct mesa_index_db_hash_entry);
-      if (!hash_entry)
-         break;
-
-      hash_entry->cache_db_file_offset = index_entry->cache_db_file_offset;
-      hash_entry->index_db_file_offset = db->index.offset;
-      hash_entry->last_access_time = index_entry->last_access_time;
-      hash_entry->size = index_entry->size;
-
-      _mesa_hash_table_u64_insert(db->index_db, index_entry->hash, hash_entry);
+      mesa_db_index_entry_insert(db, index_entry);
 
       db->index.offset += sizeof(*index_entry);
    }
 
-   if (mesa_db_seek(db->index.file, db->index.offset) &&
-       db->index.offset == file_length)
-      ret = true;
-
-error:
-   free(index_entries);
-   return ret;
+   return mesa_db_seek(db->index.file, db->index.offset) &&
+      db->index.offset == file_length;
 }
 
 static void
@@ -322,6 +386,8 @@ mesa_db_hash_table_reset(struct mesa_cache_db *db)
    _mesa_hash_table_u64_clear(db->index_db);
    ralloc_free(db->mem_ctx);
    db->mem_ctx = ralloc_context(NULL);
+
+   mesa_db_resize_index_entries(db, 0);
 }
 
 static bool
@@ -443,11 +509,16 @@ mesa_db_remove_file(struct mesa_cache_db_file *db_file,
    return true;
 }
 
+struct sort_entry {
+   struct mesa_index_db_file_entry *index_entry;
+   bool evicted;
+};
+
 static int
 entry_sort_lru(const void *_a, const void *_b, void *arg)
 {
-   const struct mesa_index_db_hash_entry *a = *((const struct mesa_index_db_hash_entry **)_a);
-   const struct mesa_index_db_hash_entry *b = *((const struct mesa_index_db_hash_entry **)_b);
+   const struct mesa_index_db_file_entry *a = ((const struct sort_entry *)_a)->index_entry;
+   const struct mesa_index_db_file_entry *b = ((const struct sort_entry *)_b)->index_entry;
 
    /* In practice it's unlikely that we will get two entries with the
     * same timestamp, but technically it's possible to happen if OS
@@ -461,8 +532,8 @@ entry_sort_lru(const void *_a, const void *_b, void *arg)
 static int
 entry_sort_offset(const void *_a, const void *_b, void *arg)
 {
-   const struct mesa_index_db_hash_entry *a = *((const struct mesa_index_db_hash_entry **)_a);
-   const struct mesa_index_db_hash_entry *b = *((const struct mesa_index_db_hash_entry **)_b);
+   const struct mesa_index_db_file_entry *a = ((const struct sort_entry *)_a)->index_entry;
+   const struct mesa_index_db_file_entry *b = ((const struct sort_entry *)_b)->index_entry;
    struct mesa_cache_db *db = arg;
 
    /* Two entries will never have the identical offset, otherwise DB is
@@ -480,13 +551,13 @@ static uint32_t blob_file_size(uint32_t blob_size)
 
 static bool
 mesa_db_compact(struct mesa_cache_db *db, int64_t blob_size,
-                struct mesa_index_db_hash_entry *remove_entry)
+                struct mesa_index_db_file_entry *remove_entry)
 {
    uint32_t num_entries, buffer_size = sizeof(struct mesa_index_db_file_entry);
    struct mesa_db_file_header cache_header, index_header;
    FILE *compacted_cache = NULL, *compacted_index = NULL;
-   struct mesa_index_db_file_entry index_entry;
-   struct mesa_index_db_hash_entry **entries;
+   struct mesa_index_db_file_entry *index_entry;
+   struct sort_entry *entries;
    bool success = false, compact = false;
    void *buffer = NULL;
    unsigned int i = 0;
@@ -513,19 +584,18 @@ mesa_db_compact(struct mesa_cache_db *db, int64_t blob_size,
        index_header.uuid != db->uuid)
       goto cleanup;
 
-   hash_table_foreach(db->index_db->table, entry) {
-      entries[i] = entry->data;
-      entries[i]->evicted = (entries[i] == remove_entry);
-      buffer_size = MAX2(buffer_size, blob_file_size(entries[i]->size));
-      i++;
+   for (i = 0, index_entry = db->index_entries; i < num_entries; i++, index_entry++) {
+      entries[i].index_entry = index_entry;
+      entries[i].evicted = index_entry == remove_entry;
+      buffer_size = MAX2(buffer_size, blob_file_size(index_entry->size));
    }
 
    util_qsort_r(entries, num_entries, sizeof(*entries),
                 entry_sort_lru, db);
 
    for (i = 0; blob_size > 0 && i < num_entries; i++) {
-      blob_size -= blob_file_size(entries[i]->size);
-      entries[i]->evicted = true;
+      blob_size -= blob_file_size(entries[i].index_entry->size);
+      entries[i].evicted = true;
    }
 
    util_qsort_r(entries, num_entries, sizeof(*entries),
@@ -552,16 +622,17 @@ mesa_db_compact(struct mesa_cache_db *db, int64_t blob_size,
 
    /* Do the compaction */
    for (i = 0; i < num_entries; i++) {
-      blob_size = blob_file_size(entries[i]->size);
+      struct mesa_index_db_file_entry *index_entry = entries[i].index_entry;
+
+      blob_size = blob_file_size(index_entry->size);
 
       /* Sanity-check the cache-read offset */
-      if (ftell(db->cache.file) != entries[i]->cache_db_file_offset)
+      if (ftell(db->cache.file) != index_entry->cache_db_file_offset)
          goto cleanup;
 
-      if (entries[i]->evicted) {
+      if (entries[i].evicted) {
          /* Jump over the evicted entry */
-         if (!mesa_db_seek_cur(db->cache.file, blob_size) ||
-             !mesa_db_seek_cur(db->index.file, sizeof(index_entry)))
+         if (!mesa_db_seek_cur(db->cache.file, blob_size))
             goto cleanup;
 
          compact = true;
@@ -575,25 +646,17 @@ mesa_db_compact(struct mesa_cache_db *db, int64_t blob_size,
              !mesa_db_write_data(compacted_cache, buffer, blob_size))
             goto cleanup;
 
-         /* Compact the index file */
-         if (!mesa_db_read(db->index.file, &index_entry) ||
-             !mesa_db_index_entry_valid(&index_entry) ||
-             index_entry.cache_db_file_offset != entries[i]->cache_db_file_offset ||
-             index_entry.size != entries[i]->size)
-            goto cleanup;
-
-         index_entry.cache_db_file_offset = ftell(compacted_cache) - blob_size;
+         index_entry->cache_db_file_offset = ftell(compacted_cache) - blob_size;
 
-         if (!mesa_db_write(compacted_index, &index_entry))
+         if (!mesa_db_write(compacted_index, index_entry))
             goto cleanup;
       } else {
          /* Sanity-check the cache-write offset */
-         if (ftell(compacted_cache) != entries[i]->cache_db_file_offset)
+         if (ftell(compacted_cache) != index_entry->cache_db_file_offset)
             goto cleanup;
 
          /* Jump over the unchanged entry */
-         if (!mesa_db_seek_cur(db->index.file,  sizeof(index_entry)) ||
-             !mesa_db_seek_cur(compacted_index, sizeof(index_entry)) ||
+         if (!mesa_db_seek_cur(compacted_index, sizeof(*index_entry)) ||
              !mesa_db_seek_cur(db->cache.file,  blob_size) ||
              !mesa_db_seek_cur(compacted_cache, blob_size))
             goto cleanup;
@@ -693,6 +756,12 @@ mesa_cache_db_close(struct mesa_cache_db *db)
    simple_mtx_destroy(&db->flock_mtx);
    ralloc_free(db->mem_ctx);
 
+   mesa_db_resize_index_entries(db, 0);
+   if (db->index_entries) {
+      munmap(db->index_entries, 0);
+      db->index_entries = NULL;
+   }
+
    mesa_db_close_file(&db->index);
    mesa_db_close_file(&db->cache);
 }
@@ -717,8 +786,8 @@ mesa_cache_db_read_entry(struct mesa_cache_db *db,
 {
    uint64_t hash = to_mesa_cache_db_hash(cache_key_160bit);
    struct mesa_cache_db_file_entry cache_entry;
-   struct mesa_index_db_file_entry index_entry;
-   struct mesa_index_db_hash_entry *hash_entry;
+   struct mesa_index_db_file_entry *index_entry;
+   long seek_pos;
    void *data = NULL;
 
    if (!mesa_db_lock(db))
@@ -733,11 +802,11 @@ mesa_cache_db_read_entry(struct mesa_cache_db *db,
    if (!mesa_db_update_index(db))
       goto fail_fatal;
 
-   hash_entry = _mesa_hash_table_u64_search(db->index_db, hash);
-   if (!hash_entry)
+   index_entry = mesa_db_index_entry_search(db, hash);
+   if (!index_entry)
       goto fail;
 
-   if (!mesa_db_seek(db->cache.file, hash_entry->cache_db_file_offset) ||
+   if (!mesa_db_seek(db->cache.file, index_entry->cache_db_file_offset) ||
        !mesa_db_read(db->cache.file, &cache_entry) ||
        !mesa_db_cache_entry_valid(&cache_entry))
       goto fail_fatal;
@@ -753,18 +822,13 @@ mesa_cache_db_read_entry(struct mesa_cache_db *db,
        util_hash_crc32(data, cache_entry.size) != cache_entry.crc)
       goto fail_fatal;
 
-   if (!mesa_db_seek(db->index.file, hash_entry->index_db_file_offset) ||
-       !mesa_db_read(db->index.file, &index_entry) ||
-       !mesa_db_index_entry_valid(&index_entry) ||
-       index_entry.cache_db_file_offset != hash_entry->cache_db_file_offset ||
-       index_entry.size != hash_entry->size)
-      goto fail_fatal;
+   index_entry->last_access_time = os_time_get_nano();
 
-   index_entry.last_access_time = os_time_get_nano();
-   hash_entry->last_access_time = index_entry.last_access_time;
+   seek_pos = ((char*)index_entry - (char*)db->index_entries) +
+      sizeof(struct mesa_db_file_header);
 
-   if (!mesa_db_seek(db->index.file, hash_entry->index_db_file_offset) ||
-       !mesa_db_write(db->index.file, &index_entry))
+   if (!mesa_db_seek(db->index.file, seek_pos) ||
+       !mesa_db_write(db->index.file, index_entry))
       goto fail_fatal;
 
    fflush(db->index.file);
@@ -804,9 +868,9 @@ mesa_cache_db_entry_write(struct mesa_cache_db *db,
                           const void *blob, size_t blob_size)
 {
    uint64_t hash = to_mesa_cache_db_hash(cache_key_160bit);
-   struct mesa_index_db_hash_entry *hash_entry = NULL;
    struct mesa_cache_db_file_entry cache_entry;
-   struct mesa_index_db_file_entry index_entry;
+   struct mesa_index_db_file_entry *index_entry;
+   off_t index_offset;
 
    if (!mesa_db_lock(db))
       return false;
@@ -829,45 +893,40 @@ mesa_cache_db_entry_write(struct mesa_cache_db *db,
          goto fail_fatal;
    }
 
-   hash_entry = _mesa_hash_table_u64_search(db->index_db, hash);
-   if (hash_entry) {
-      hash_entry = NULL;
+   index_entry = mesa_db_index_entry_search(db, hash);
+   if (index_entry)
       goto fail;
-   }
 
    if (!mesa_db_seek_end(db->cache.file) ||
        !mesa_db_seek_end(db->index.file))
       goto fail_fatal;
 
+   index_offset = db->index_entries_size;
+   if (!mesa_db_resize_index_entries(db, index_offset + sizeof(*index_entry)))
+      goto fail;
+
+   index_entry = mesa_db_index_entry_get(db, index_offset);
+
    memcpy(cache_entry.key, cache_key_160bit, sizeof(cache_entry.key));
    cache_entry.crc = util_hash_crc32(blob, blob_size);
    cache_entry.size = blob_size;
 
-   index_entry.hash = hash;
-   index_entry.size = blob_size;
-   index_entry.last_access_time = os_time_get_nano();
-   index_entry.cache_db_file_offset = ftell(db->cache.file);
-
-   hash_entry = ralloc(db->mem_ctx, struct mesa_index_db_hash_entry);
-   if (!hash_entry)
-      goto fail;
-
-   hash_entry->cache_db_file_offset = index_entry.cache_db_file_offset;
-   hash_entry->index_db_file_offset = ftell(db->index.file);
-   hash_entry->last_access_time = index_entry.last_access_time;
-   hash_entry->size = index_entry.size;
+   index_entry->hash = hash;
+   index_entry->size = blob_size;
+   index_entry->last_access_time = os_time_get_nano();
+   index_entry->cache_db_file_offset = ftell(db->cache.file);
 
    if (!mesa_db_write(db->cache.file, &cache_entry) ||
        !mesa_db_write_data(db->cache.file, blob, blob_size) ||
-       !mesa_db_write(db->index.file, &index_entry))
+       !mesa_db_write(db->index.file, index_entry))
       goto fail_fatal;
 
    fflush(db->cache.file);
    fflush(db->index.file);
 
-   db->index.offset = ftell(db->index.file);
+   mesa_db_index_entry_insert(db, index_entry);
 
-   _mesa_hash_table_u64_insert(db->index_db, hash, hash_entry);
+   db->index.offset = ftell(db->index.file);
 
    mesa_db_unlock(db);
 
@@ -878,9 +937,6 @@ fail_fatal:
 fail:
    mesa_db_unlock(db);
 
-   if (hash_entry)
-      ralloc_free(hash_entry);
-
    return false;
 }
 
@@ -890,7 +946,7 @@ mesa_cache_db_entry_remove(struct mesa_cache_db *db,
 {
    uint64_t hash = to_mesa_cache_db_hash(cache_key_160bit);
    struct mesa_cache_db_file_entry cache_entry;
-   struct mesa_index_db_hash_entry *hash_entry;
+   struct mesa_index_db_file_entry *index_entry;
 
    if (!mesa_db_lock(db))
       return NULL;
@@ -904,11 +960,11 @@ mesa_cache_db_entry_remove(struct mesa_cache_db *db,
    if (!mesa_db_update_index(db))
       goto fail_fatal;
 
-   hash_entry = _mesa_hash_table_u64_search(db->index_db, hash);
-   if (!hash_entry)
+   index_entry = mesa_db_index_entry_search(db, hash);
+   if (!index_entry)
       goto fail;
 
-   if (!mesa_db_seek(db->cache.file, hash_entry->cache_db_file_offset) ||
+   if (!mesa_db_seek(db->cache.file, index_entry->cache_db_file_offset) ||
        !mesa_db_read(db->cache.file, &cache_entry) ||
        !mesa_db_cache_entry_valid(&cache_entry))
       goto fail_fatal;
@@ -916,7 +972,7 @@ mesa_cache_db_entry_remove(struct mesa_cache_db *db,
    if (memcmp(cache_entry.key, cache_key_160bit, sizeof(cache_entry.key)))
       goto fail;
 
-   if (!mesa_db_compact(db, 0, hash_entry))
+   if (!mesa_db_compact(db, 0, index_entry))
       goto fail_fatal;
 
    mesa_db_unlock(db);
@@ -974,7 +1030,8 @@ double
 mesa_cache_db_eviction_score(struct mesa_cache_db *db)
 {
    int64_t eviction_size = mesa_cache_db_eviction_size(db);
-   struct mesa_index_db_hash_entry **entries;
+   struct mesa_index_db_file_entry *index_entry;
+   struct sort_entry *entries;
    unsigned num_entries, i = 0;
    double eviction_score = 0;
 
@@ -992,15 +1049,16 @@ mesa_cache_db_eviction_score(struct mesa_cache_db *db)
    if (!entries)
       goto fail;
 
-   hash_table_foreach(db->index_db->table, entry)
-      entries[i++] = entry->data;
+   for (i = 0, index_entry = db->index_entries; i < num_entries; i++)
+      entries[i].index_entry = index_entry++;
 
    util_qsort_r(entries, num_entries, sizeof(*entries),
                 entry_sort_lru, db);
 
    for (i = 0; eviction_size > 0 && i < num_entries; i++) {
-      uint64_t entry_age = os_time_get_nano() - entries[i]->last_access_time;
-      unsigned entry_size = blob_file_size(entries[i]->size);
+      index_entry = entries[i].index_entry;
+      uint64_t entry_age = os_time_get_nano() - index_entry->last_access_time;
+      unsigned entry_size = blob_file_size(index_entry->size);
 
       /* Eviction score is a sum of weighted cache entry sizes,
        * where weight doubles for each month of entry's age.
diff --git a/src/util/mesa_cache_db.h b/src/util/mesa_cache_db.h
index f6097d81271..caa3ab2b404 100644
--- a/src/util/mesa_cache_db.h
+++ b/src/util/mesa_cache_db.h
@@ -32,6 +32,8 @@ struct mesa_cache_db {
    struct hash_table_u64 *index_db;
    struct mesa_cache_db_file cache;
    struct mesa_cache_db_file index;
+   void *index_entries;
+   size_t index_entries_size;
    uint64_t max_cache_size;
    simple_mtx_t flock_mtx;
    void *mem_ctx;