From f4015337daf130944393296550dd7d8a9c172325 Mon Sep 17 00:00:00 2001 From: Jeff King Date: Mon, 21 Dec 2015 01:19:49 -0500 Subject: pack-revindex: drop hash table The main entry point to the pack-revindex code is find_pack_revindex(). This calls revindex_for_pack(), which lazily computes and caches the revindex for the pack. We store the cache in a very simple hash table. It's created by init_pack_revindex(), which inserts an entry for every packfile we know about, and we never grow or shrink the hash. If we ever need the revindex for a pack that isn't in the hash, we die() with an internal error. This can lead to a race, because we may load more packs after having called init_pack_revindex(). For example, imagine we have one process which needs to look at the revindex for a variety of objects (e.g., cat-file's "%(objectsize:disk)" format). Simultaneously, git-gc is running, which is doing a `git repack -ad`. We might hit a sequence like: 1. We need the revidx for some packed object. We call find_pack_revindex() and end up in init_pack_revindex() to create the hash table for all packs we know about. 2. We look up another object and can't find it, because the repack has removed the pack it's in. We re-scan the pack directory and find a new pack containing the object. It gets added to our packed_git list. 3. We call find_pack_revindex() for the new object, which hits revindex_for_pack() for our new pack. It can't find the packed_git in the revindex hash, and dies. You could also replace the `repack` above with a push or fetch to create a new pack, though these are less likely (you would have to somehow learn about the new objects to look them up). Prior to 1a6d8b9 (do not discard revindex when re-preparing packfiles, 2014-01-15), this was safe, as we threw away the revindex whenever we re-scanned the pack directory (and thus re-created the revindex hash on the fly). However, we don't want to simply revert that commit, as it was solving a different race. So we have a few options: - We can fix the race in 1a6d8b9 differently, by having the bitmap code look in the revindex hash instead of caching the pointer. But this would introduce a lot of extra hash lookups for common bitmap operations. - We could teach the revindex to dynamically add new packs to the hash table. This would perform the same, but would mean adding extra code to the revindex hash (which currently cannot be resized at all). - We can get rid of the hash table entirely. There is exactly one revindex per pack, so we can just store it in the packed_git struct. Since it's initialized lazily, it does not add to the startup cost. This is the best of both worlds: less code and fewer hash table lookups. The original code likely avoided this in the name of encapsulation. But the packed_git and reverse_index code are fairly intimate already, so it's not much of a loss. This patch implements the final option. It's a minimal conversion that retains the pack_revindex struct. No callers need to change, and we can do further cleanup in a follow-on patch. Signed-off-by: Jeff King Signed-off-by: Junio C Hamano --- pack-revindex.c | 60 ++++++--------------------------------------------------- 1 file changed, 6 insertions(+), 54 deletions(-) (limited to 'pack-revindex.c') diff --git a/pack-revindex.c b/pack-revindex.c index 5bd7c6198..8e63dbcf4 100644 --- a/pack-revindex.c +++ b/pack-revindex.c @@ -8,52 +8,13 @@ * size is easily available by examining the pack entry header). It is * also rather expensive to find the sha1 for an object given its offset. * - * We build a hashtable of existing packs (pack_revindex), and keep reverse - * index here -- pack index file is sorted by object name mapping to offset; - * this pack_revindex[].revindex array is a list of offset/index_nr pairs + * The pack index file is sorted by object name mapping to offset; + * this revindex array is a list of offset/index_nr pairs * ordered by offset, so if you know the offset of an object, next offset * is where its packed representation ends and the index_nr can be used to * get the object sha1 from the main index. */ -static struct pack_revindex *pack_revindex; -static int pack_revindex_hashsz; - -static int pack_revindex_ix(struct packed_git *p) -{ - unsigned long ui = (unsigned long)p; - int i; - - ui = ui ^ (ui >> 16); /* defeat structure alignment */ - i = (int)(ui % pack_revindex_hashsz); - while (pack_revindex[i].p) { - if (pack_revindex[i].p == p) - return i; - if (++i == pack_revindex_hashsz) - i = 0; - } - return -1 - i; -} - -static void init_pack_revindex(void) -{ - int num; - struct packed_git *p; - - for (num = 0, p = packed_git; p; p = p->next) - num++; - if (!num) - return; - pack_revindex_hashsz = num * 11; - pack_revindex = xcalloc(sizeof(*pack_revindex), pack_revindex_hashsz); - for (p = packed_git; p; p = p->next) { - num = pack_revindex_ix(p); - num = - 1 - num; - pack_revindex[num].p = p; - } - /* revindex elements are lazily initialized */ -} - /* * This is a least-significant-digit radix sort. * @@ -198,20 +159,11 @@ static void create_pack_revindex(struct pack_revindex *rix) struct pack_revindex *revindex_for_pack(struct packed_git *p) { - int num; - struct pack_revindex *rix; - - if (!pack_revindex_hashsz) - init_pack_revindex(); - - num = pack_revindex_ix(p); - if (num < 0) - die("internal error: pack revindex fubar"); - - rix = &pack_revindex[num]; - if (!rix->revindex) + struct pack_revindex *rix = &p->reverse_index; + if (!rix->revindex) { + rix->p = p; create_pack_revindex(rix); - + } return rix; } -- cgit v1.2.1 From 9d98bbf5785708da4effc9b8f34ba6e18d726625 Mon Sep 17 00:00:00 2001 From: Jeff King Date: Mon, 21 Dec 2015 01:20:33 -0500 Subject: pack-revindex: store entries directly in packed_git A pack_revindex struct has two elements: the revindex entries themselves, and a pointer to the packed_git. We need both to do lookups, because only the latter knows things like the number of objects in the pack. Now that packed_git contains the pack_revindex struct it's just as easy to pass around the packed_git itself, and we do not need the extra back-pointer. We can instead just store the entries directly in the pack. All functions which took a pack_revindex now just take a packed_git. We still lazy-load in find_pack_revindex, so most callers are unaffected. The exception is the bitmap code, which computes the revindex and caches the pointer when we load the bitmaps. We can continue to load, drop the extra cache pointer, and just access bitmap_git.pack.revindex directly. Signed-off-by: Jeff King Signed-off-by: Junio C Hamano --- pack-revindex.c | 47 ++++++++++++++++++++++------------------------- 1 file changed, 22 insertions(+), 25 deletions(-) (limited to 'pack-revindex.c') diff --git a/pack-revindex.c b/pack-revindex.c index 8e63dbcf4..155a8a3d6 100644 --- a/pack-revindex.c +++ b/pack-revindex.c @@ -115,14 +115,13 @@ static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max) /* * Ordered list of offsets of objects in the pack. */ -static void create_pack_revindex(struct pack_revindex *rix) +static void create_pack_revindex(struct packed_git *p) { - struct packed_git *p = rix->p; unsigned num_ent = p->num_objects; unsigned i; const char *index = p->index_data; - rix->revindex = xmalloc(sizeof(*rix->revindex) * (num_ent + 1)); + p->revindex = xmalloc(sizeof(*p->revindex) * (num_ent + 1)); index += 4 * 256; if (p->index_version > 1) { @@ -132,46 +131,42 @@ static void create_pack_revindex(struct pack_revindex *rix) for (i = 0; i < num_ent; i++) { uint32_t off = ntohl(*off_32++); if (!(off & 0x80000000)) { - rix->revindex[i].offset = off; + p->revindex[i].offset = off; } else { - rix->revindex[i].offset = + p->revindex[i].offset = ((uint64_t)ntohl(*off_64++)) << 32; - rix->revindex[i].offset |= + p->revindex[i].offset |= ntohl(*off_64++); } - rix->revindex[i].nr = i; + p->revindex[i].nr = i; } } else { for (i = 0; i < num_ent; i++) { uint32_t hl = *((uint32_t *)(index + 24 * i)); - rix->revindex[i].offset = ntohl(hl); - rix->revindex[i].nr = i; + p->revindex[i].offset = ntohl(hl); + p->revindex[i].nr = i; } } /* This knows the pack format -- the 20-byte trailer * follows immediately after the last object data. */ - rix->revindex[num_ent].offset = p->pack_size - 20; - rix->revindex[num_ent].nr = -1; - sort_revindex(rix->revindex, num_ent, p->pack_size); + p->revindex[num_ent].offset = p->pack_size - 20; + p->revindex[num_ent].nr = -1; + sort_revindex(p->revindex, num_ent, p->pack_size); } -struct pack_revindex *revindex_for_pack(struct packed_git *p) +void load_pack_revindex(struct packed_git *p) { - struct pack_revindex *rix = &p->reverse_index; - if (!rix->revindex) { - rix->p = p; - create_pack_revindex(rix); - } - return rix; + if (!p->revindex) + create_pack_revindex(p); } -int find_revindex_position(struct pack_revindex *pridx, off_t ofs) +int find_revindex_position(struct packed_git *p, off_t ofs) { int lo = 0; - int hi = pridx->p->num_objects + 1; - struct revindex_entry *revindex = pridx->revindex; + int hi = p->num_objects + 1; + struct revindex_entry *revindex = p->revindex; do { unsigned mi = lo + (hi - lo) / 2; @@ -189,11 +184,13 @@ int find_revindex_position(struct pack_revindex *pridx, off_t ofs) struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs) { - struct pack_revindex *pridx = revindex_for_pack(p); - int pos = find_revindex_position(pridx, ofs); + int pos; + + load_pack_revindex(p); + pos = find_revindex_position(p, ofs); if (pos < 0) return NULL; - return pridx->revindex + pos; + return p->revindex + pos; } -- cgit v1.2.1