{"thread":{"id":"7318","subject":"[PATCH 2/2] use a LRU eviction policy for the delta base cache","startedAt":"2007-03-19T20:31:04Z","lastAt":"2007-03-19T20:31:04Z","messageCount":1,"participants":["Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"37548","messageId":"alpine.LFD.0.83.0703191628570.18328@xanadu.home","threadId":"7318","inReplyTo":null,"subject":"[PATCH 2/2] use a LRU eviction policy for the delta base cache","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-19T20:31:04Z","receivedAt":"2007-03-19T20:31:04Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This provides a smoother degradation in performance when the cache\ngets trashed due to the delta_base_cache_limit being reached.  Limited\ntesting with really small delta_base_cache_limit values appears to confirm\nthis.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n sha1_file.c |   39 +++++++++++++++++++++++++++++++--------\n 1 files changed, 31 insertions(+), 8 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 8a19d7e..9fe2bd6 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1355,11 +1355,18 @@ static void *unpack_compressed_entry(struct packed_git *p,\n #define MAX_DELTA_CACHE (256)\n \n static size_t delta_base_cached;\n+\n+static struct delta_base_cache_lru_list {\n+\tstruct delta_base_cache_lru_list *prev;\n+\tstruct delta_base_cache_lru_list *next;\n+} delta_base_cache_lru = { &delta_base_cache_lru, &delta_base_cache_lru };\n+\n static struct delta_base_cache_entry {\n+\tstruct delta_base_cache_lru_list lru;\n+\tvoid *data;\n \tstruct packed_git *p;\n \toff_t base_offset;\n \tunsigned long size;\n-\tvoid *data;\n \tenum object_type type;\n } delta_base_cache[MAX_DELTA_CACHE];\n \n@@ -1387,6 +1394,8 @@ static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,\n found_cache_entry:\n \tif (!keep_cache) {\n \t\tent->data = NULL;\n+\t\tent->lru.next->prev = ent->lru.prev;\n+\t\tent->lru.prev->next = ent->lru.next;\n \t\tdelta_base_cached -= ent->size;\n \t}\n \telse {\n@@ -1404,6 +1413,8 @@ static inline void release_delta_base_cache(struct delta_base_cache_entry *ent)\n \tif (ent->data) {\n \t\tfree(ent->data);\n \t\tent->data = NULL;\n+\t\tent->lru.next->prev = ent->lru.prev;\n+\t\tent->lru.prev->next = ent->lru.next;\n \t\tdelta_base_cached -= ent->size;\n \t}\n }\n@@ -1411,26 +1422,38 @@ static inline void release_delta_base_cache(struct delta_base_cache_entry *ent)\n static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \tvoid *base, unsigned long base_size, enum object_type type)\n {\n-\tunsigned long i, hash = pack_entry_hash(p, base_offset);\n+\tunsigned long hash = pack_entry_hash(p, base_offset);\n \tstruct delta_base_cache_entry *ent = delta_base_cache + hash;\n+\tstruct delta_base_cache_lru_list *lru;\n \n \trelease_delta_base_cache(ent);\n \tdelta_base_cached += base_size;\n-\tfor (i = 0; delta_base_cached > delta_base_cache_limit\n-\t\t    && i < MAX_DELTA_CACHE ; i++) {\n-\t\tstruct delta_base_cache_entry *f = delta_base_cache + i;\n+\n+\tfor (lru = delta_base_cache_lru.next;\n+\t     delta_base_cached > delta_base_cache_limit\n+\t     && lru != &delta_base_cache_lru;\n+\t     lru = lru->next) {\n+\t\tstruct delta_base_cache_entry *f = (void *)lru;\n \t\tif (f->type == OBJ_BLOB)\n \t\t\trelease_delta_base_cache(f);\n \t}\n-\tfor (i = 0; delta_base_cached > delta_base_cache_limit\n-\t\t    && i < MAX_DELTA_CACHE ; i++)\n-\t\trelease_delta_base_cache(delta_base_cache + i);\n+\tfor (lru = delta_base_cache_lru.next;\n+\t     delta_base_cached > delta_base_cache_limit\n+\t     && lru != &delta_base_cache_lru;\n+\t     lru = lru->next) {\n+\t\tstruct delta_base_cache_entry *f = (void *)lru;\n+\t\trelease_delta_base_cache(f);\n+\t}\n \n \tent->p = p;\n \tent->base_offset = base_offset;\n \tent->type = type;\n \tent->data = base;\n \tent->size = base_size;\n+\tent->lru.next = &delta_base_cache_lru;\n+\tent->lru.prev = delta_base_cache_lru.prev;\n+\tdelta_base_cache_lru.prev->next = &ent->lru;\n+\tdelta_base_cache_lru.prev = &ent->lru;\n }\n \n static void *unpack_delta_entry(struct packed_git *p,\n-- \n1.5.1.rc1.596.ge11e-dirty\n"}]}