diff options
-rw-r--r-- | src/pack.c | 71 | ||||
-rw-r--r-- | src/pack.h | 7 |
2 files changed, 60 insertions, 18 deletions
diff --git a/src/pack.c b/src/pack.c index de038a45c..e36052978 100644 --- a/src/pack.c +++ b/src/pack.c @@ -50,17 +50,25 @@ static int packfile_error(const char *message) * Delta base cache ********************/ -static git_pack_cache_entry *new_cache_object(git_rawobj *source) +static git_pack_cache_entry *new_cache_object(git_rawobj *source, git_off_t offset) { git_pack_cache_entry *e = git__calloc(1, sizeof(git_pack_cache_entry)); if (!e) return NULL; memcpy(&e->raw, source, sizeof(git_rawobj)); + e->next = e->prev = e; + e->offset = offset; return e; } +static void remove_entry(git_pack_cache_entry *entry) +{ + entry->prev->next = entry->next; + entry->next->prev = entry->prev; +} + static void free_cache_object(void *o) { git_pack_cache_entry *e = (git_pack_cache_entry *)o; @@ -74,12 +82,16 @@ static void free_cache_object(void *o) static void cache_free(git_pack_cache *cache) { - khiter_t k; + git_pack_cache_entry *entry, *next; + /* this works as a proxy for an initialized cache */ if (cache->entries) { - for (k = kh_begin(cache->entries); k != kh_end(cache->entries); k++) { - if (kh_exist(cache->entries, k)) - free_cache_object(kh_value(cache->entries, k)); + entry = cache->sentinel.next; + while (entry != &cache->sentinel) { + next = entry->next; + remove_entry(entry); + free_cache_object(entry); + entry = next; } git_offmap_free(cache->entries); @@ -107,9 +119,30 @@ static int cache_init(git_pack_cache *cache) return -1; } + cache->sentinel.prev = &cache->sentinel; + cache->sentinel.next = &cache->sentinel; + return 0; } +/* call with the cache lock held */ +static void move_to_front(git_pack_cache *cache, git_pack_cache_entry *entry) +{ + git_pack_cache_entry *next = NULL, *latest = NULL; + + /* remove the entry from the current position */ + next = entry->next; + entry->prev->next = entry->next; + next->prev = entry->prev; + + /* and put ourselves at the top of the list */ + latest = cache->sentinel.prev; + entry->next = latest->next; + latest->next = entry; + entry->prev = latest; + entry->next->prev = entry; +} + static git_pack_cache_entry *cache_get(git_pack_cache *cache, git_off_t offset) { khiter_t k; @@ -122,7 +155,7 @@ static git_pack_cache_entry *cache_get(git_pack_cache *cache, git_off_t offset) if (k != kh_end(cache->entries)) { /* found it */ entry = kh_value(cache->entries, k); git_atomic_inc(&entry->refcount); - entry->last_usage = cache->use_ctr++; + move_to_front(cache, entry); } git_mutex_unlock(&cache->lock); @@ -130,23 +163,27 @@ static git_pack_cache_entry *cache_get(git_pack_cache *cache, git_off_t offset) } /* Run with the cache lock held */ -static void free_lowest_entry(git_pack_cache *cache) +static int free_lowest_entry(git_pack_cache *cache) { git_pack_cache_entry *entry; khiter_t k; + int error = 0; - for (k = kh_begin(cache->entries); k != kh_end(cache->entries); k++) { - if (!kh_exist(cache->entries, k)) - continue; - - entry = kh_value(cache->entries, k); - - if (entry && entry->refcount.val == 0) { + entry = cache->sentinel.next; + while (entry != &cache->sentinel) { + if (entry->refcount.val == 0) { cache->memory_used -= entry->raw.len; + cache->nentries--; + k = kh_get(off, cache->entries, entry->offset); kh_del(off, cache->entries, k); + remove_entry(entry); free_cache_object(entry); + break; } + entry = entry->next; } + + return error; } static int cache_add(git_pack_cache *cache, git_rawobj *base, git_off_t offset) @@ -158,7 +195,7 @@ static int cache_add(git_pack_cache *cache, git_rawobj *base, git_off_t offset) if (base->len > GIT_PACK_CACHE_SIZE_LIMIT) return -1; - entry = new_cache_object(base); + entry = new_cache_object(base, offset); if (entry) { if (git_mutex_lock(&cache->lock) < 0) { giterr_set(GITERR_OS, "failed to lock cache"); @@ -167,13 +204,15 @@ static int cache_add(git_pack_cache *cache, git_rawobj *base, git_off_t offset) /* Add it to the cache if nobody else has */ exists = kh_get(off, cache->entries, offset) != kh_end(cache->entries); if (!exists) { - while (cache->memory_used + base->len > cache->memory_limit) + while (cache->nentries > 256) free_lowest_entry(cache); k = kh_put(off, cache->entries, offset, &error); assert(error != 0); kh_value(cache->entries, k) = entry; cache->memory_used += entry->raw.len; + cache->nentries++; + move_to_front(cache, entry); } git_mutex_unlock(&cache->lock); /* Somebody beat us to adding it into the cache */ diff --git a/src/pack.h b/src/pack.h index 58f81e2f0..2985c8ec9 100644 --- a/src/pack.h +++ b/src/pack.h @@ -55,8 +55,10 @@ struct git_pack_idx_header { }; typedef struct git_pack_cache_entry { - size_t last_usage; /* enough? */ + struct git_pack_cache_entry *prev; + struct git_pack_cache_entry *next; git_atomic refcount; + git_off_t offset; git_rawobj raw; } git_pack_cache_entry; @@ -71,9 +73,10 @@ GIT__USE_OIDMAP; typedef struct { size_t memory_used; size_t memory_limit; - size_t use_ctr; + git_pack_cache_entry sentinel; git_mutex lock; git_offmap *entries; + size_t nentries; } git_pack_cache; struct git_pack_file { |