use a LRU eviction policy for the delta base cache

[thirdparty/git.git] / sha1_file.c

diff --git a/sha1_file.c b/sha1_file.c
index f11ca3fbacd5de159129c3311d7915d56aff79e4..9fe2bd69a1edbaf1103de79d5e9d857939470d4f 100644 (file)
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1352,16 +1352,108 @@ static void *unpack_compressed_entry(struct packed_git *p,
        return buffer;
 }
 
+#define MAX_DELTA_CACHE (256)
+
+static size_t delta_base_cached;
+
+static struct delta_base_cache_lru_list {
+       struct delta_base_cache_lru_list *prev;
+       struct delta_base_cache_lru_list *next;
+} delta_base_cache_lru = { &delta_base_cache_lru, &delta_base_cache_lru };
+
+static struct delta_base_cache_entry {
+       struct delta_base_cache_lru_list lru;
+       void *data;
+       struct packed_git *p;
+       off_t base_offset;
+       unsigned long size;
+       enum object_type type;
+} delta_base_cache[MAX_DELTA_CACHE];
+
+static unsigned long pack_entry_hash(struct packed_git *p, off_t base_offset)
+{
+       unsigned long hash;
+
+       hash = (unsigned long)p + (unsigned long)base_offset;
+       hash += (hash >> 8) + (hash >> 16);
+       return hash % MAX_DELTA_CACHE;
+}
+
 static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,
-       unsigned long *base_size, enum object_type *type)
+       unsigned long *base_size, enum object_type *type, int keep_cache)
 {
+       void *ret;
+       unsigned long hash = pack_entry_hash(p, base_offset);
+       struct delta_base_cache_entry *ent = delta_base_cache + hash;
+
+       ret = ent->data;
+       if (ret && ent->p == p && ent->base_offset == base_offset)
+               goto found_cache_entry;
        return unpack_entry(p, base_offset, type, base_size);
+
+found_cache_entry:
+       if (!keep_cache) {
+               ent->data = NULL;
+               ent->lru.next->prev = ent->lru.prev;
+               ent->lru.prev->next = ent->lru.next;
+               delta_base_cached -= ent->size;
+       }
+       else {
+               ret = xmalloc(ent->size + 1);
+               memcpy(ret, ent->data, ent->size);
+               ((char *)ret)[ent->size] = 0;
+       }
+       *type = ent->type;
+       *base_size = ent->size;
+       return ret;
+}
+
+static inline void release_delta_base_cache(struct delta_base_cache_entry *ent)
+{
+       if (ent->data) {
+               free(ent->data);
+               ent->data = NULL;
+               ent->lru.next->prev = ent->lru.prev;
+               ent->lru.prev->next = ent->lru.next;
+               delta_base_cached -= ent->size;
+       }
 }
 
 static void add_delta_base_cache(struct packed_git *p, off_t base_offset,
        void *base, unsigned long base_size, enum object_type type)
 {
-       free(base);
+       unsigned long hash = pack_entry_hash(p, base_offset);
+       struct delta_base_cache_entry *ent = delta_base_cache + hash;
+       struct delta_base_cache_lru_list *lru;
+
+       release_delta_base_cache(ent);
+       delta_base_cached += base_size;
+
+       for (lru = delta_base_cache_lru.next;
+            delta_base_cached > delta_base_cache_limit
+            && lru != &delta_base_cache_lru;
+            lru = lru->next) {
+               struct delta_base_cache_entry *f = (void *)lru;
+               if (f->type == OBJ_BLOB)
+                       release_delta_base_cache(f);
+       }
+       for (lru = delta_base_cache_lru.next;
+            delta_base_cached > delta_base_cache_limit
+            && lru != &delta_base_cache_lru;
+            lru = lru->next) {
+               struct delta_base_cache_entry *f = (void *)lru;
+               release_delta_base_cache(f);
+       }
+
+       ent->p = p;
+       ent->base_offset = base_offset;
+       ent->type = type;
+       ent->data = base;
+       ent->size = base_size;
+       ent->lru.next = &delta_base_cache_lru;
+       ent->lru.prev = delta_base_cache_lru.prev;
+       delta_base_cache_lru.prev->next = &ent->lru;
+       delta_base_cache_lru.prev = &ent->lru;
 }
 
 static void *unpack_delta_entry(struct packed_git *p,
@@ -1377,7 +1469,7 @@ static void *unpack_delta_entry(struct packed_git *p,
        off_t base_offset;
 
        base_offset = get_delta_base(p, w_curs, &curpos, *type, obj_offset);
-       base = cache_or_unpack_entry(p, base_offset, &base_size, type);
+       base = cache_or_unpack_entry(p, base_offset, &base_size, type, 0);
        if (!base)
                die("failed to read delta base object"
                    " at %"PRIuMAX" from %s",
@@ -1574,7 +1666,7 @@ static void *read_packed_sha1(const unsigned char *sha1,
        if (!find_pack_entry(sha1, &e, NULL))
                return NULL;
        else
-               return unpack_entry(e.p, e.offset, type, size);
+               return cache_or_unpack_entry(e.p, e.offset, size, type, 1);
 }
 
 /*