[PATCH 1/2] pack-revindex: drop hash table

[PATCH 1/2] pack-revindex: drop hash table

[Jeff King]

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` is running. 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 <peff@peff.net>
---
The race was added in v2.0.0. I doubt it comes up much in practice,
because not much code uses the revidx. We started seeing it at GitHub
when we added a frequent automated job that uses "git cat-file" as
above. So probably something for 'maint', but not urgent.

 cache.h         |  2 ++
 pack-revindex.c | 60 ++++++---------------------------------------------------
 2 files changed, 8 insertions(+), 54 deletions(-)

diff --git a/cache.h b/cache.h
index 5ab6cb5..de4ef88 100644
--- a/cache.h
+++ b/cache.h
@@ -9,6 +9,7 @@
 #include "convert.h"
 #include "trace.h"
 #include "string-list.h"
+#include "pack-revindex.h"
 
 #include SHA1_HEADER
 #ifndef platform_SHA_CTX
@@ -1298,6 +1299,7 @@ extern struct packed_git {
 		 freshened:1,
 		 do_not_close:1;
 	unsigned char sha1[20];
+	struct pack_revindex reverse_index;
 	/* something like ".git/objects/pack/xxxxx.pack" */
 	char pack_name[FLEX_ARRAY]; /* more */
 } *packed_git;
diff --git a/pack-revindex.c b/pack-revindex.c
index e542ea7..8e63dbc 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)(intptr_t)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(pack_revindex_hashsz, sizeof(*pack_revindex));
-	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;
 }
 
-- 
2.7.0.rc1.350.g9acc0f4

[PATCH 2/2] pack-revindex: store entries directly in packed_git

[Jeff King]

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 <peff@peff.net>
---
This one is optional, but I think it is a nice cleanup on top of 1/2.

 cache.h         |  2 +-
 pack-bitmap.c   | 13 +++++--------
 pack-revindex.c | 47 ++++++++++++++++++++++-------------------------
 pack-revindex.h | 11 ++++-------
 4 files changed, 32 insertions(+), 41 deletions(-)

diff --git a/cache.h b/cache.h
index de4ef88..565937e 100644
--- a/cache.h
+++ b/cache.h
@@ -1299,7 +1299,7 @@ extern struct packed_git {
 		 freshened:1,
 		 do_not_close:1;
 	unsigned char sha1[20];
-	struct pack_revindex reverse_index;
+	struct revindex_entry *revindex;
 	/* something like ".git/objects/pack/xxxxx.pack" */
 	char pack_name[FLEX_ARRAY]; /* more */
 } *packed_git;
diff --git a/pack-bitmap.c b/pack-bitmap.c
index cb9c622..dd8dc16 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -33,9 +33,6 @@ static struct bitmap_index {
 	/* Packfile to which this bitmap index belongs to */
 	struct packed_git *pack;
 
-	/* reverse index for the packfile */
-	struct pack_revindex *reverse_index;
-
 	/*
 	 * Mark the first `reuse_objects` in the packfile as reused:
 	 * they will be sent as-is without using them for repacking
@@ -308,7 +305,7 @@ static int load_pack_bitmap(void)
 
 	bitmap_git.bitmaps = kh_init_sha1();
 	bitmap_git.ext_index.positions = kh_init_sha1_pos();
-	bitmap_git.reverse_index = revindex_for_pack(bitmap_git.pack);
+	load_pack_revindex(bitmap_git.pack);
 
 	if (!(bitmap_git.commits = read_bitmap_1(&bitmap_git)) ||
 		!(bitmap_git.trees = read_bitmap_1(&bitmap_git)) ||
@@ -380,7 +377,7 @@ static inline int bitmap_position_packfile(const unsigned char *sha1)
 	if (!offset)
 		return -1;
 
-	return find_revindex_position(bitmap_git.reverse_index, offset);
+	return find_revindex_position(bitmap_git.pack, offset);
 }
 
 static int bitmap_position(const unsigned char *sha1)
@@ -630,7 +627,7 @@ static void show_objects_for_type(
 			if (pos + offset < bitmap_git.reuse_objects)
 				continue;
 
-			entry = &bitmap_git.reverse_index->revindex[pos + offset];
+			entry = &bitmap_git.pack->revindex[pos + offset];
 			sha1 = nth_packed_object_sha1(bitmap_git.pack, entry->nr);
 
 			if (bitmap_git.hashes)
@@ -804,7 +801,7 @@ int reuse_partial_packfile_from_bitmap(struct packed_git **packfile,
 		return -1;
 
 	bitmap_git.reuse_objects = *entries = reuse_objects;
-	*up_to = bitmap_git.reverse_index->revindex[reuse_objects].offset;
+	*up_to = bitmap_git.pack->revindex[reuse_objects].offset;
 	*packfile = bitmap_git.pack;
 
 	return 0;
@@ -1038,7 +1035,7 @@ int rebuild_existing_bitmaps(struct packing_data *mapping,
 		struct revindex_entry *entry;
 		struct object_entry *oe;
 
-		entry = &bitmap_git.reverse_index->revindex[i];
+		entry = &bitmap_git.pack->revindex[i];
 		sha1 = nth_packed_object_sha1(bitmap_git.pack, entry->nr);
 		oe = packlist_find(mapping, sha1, NULL);
 
diff --git a/pack-revindex.c b/pack-revindex.c
index 8e63dbc..155a8a3 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;
 }
diff --git a/pack-revindex.h b/pack-revindex.h
index d737f98..e262f3e 100644
--- a/pack-revindex.h
+++ b/pack-revindex.h
@@ -1,18 +1,15 @@
 #ifndef PACK_REVINDEX_H
 #define PACK_REVINDEX_H
 
+struct packed_git;
+
 struct revindex_entry {
 	off_t offset;
 	unsigned int nr;
 };
 
-struct pack_revindex {
-	struct packed_git *p;
-	struct revindex_entry *revindex;
-};
-
-struct pack_revindex *revindex_for_pack(struct packed_git *p);
-int find_revindex_position(struct pack_revindex *pridx, off_t ofs);
+void load_pack_revindex(struct packed_git *p);
+int find_revindex_position(struct packed_git *p, off_t ofs);
 
 struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs);
 
-- 
2.7.0.rc1.350.g9acc0f4

Re: [PATCH 1/2] pack-revindex: drop hash table

[Eric Sunshine]

On Mon, Dec 21, 2015 at 1:19 AM, Jeff King <peff@peff.net> wrote:
> 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` is running. We
> might hit a sequence like:

Probably want to drop one of the "is running"s...

Re: [PATCH 1/2] pack-revindex: drop hash table

[Jeff King]

On Mon, Dec 21, 2015 at 02:06:59AM -0500, Eric Sunshine wrote:

> On Mon, Dec 21, 2015 at 1:19 AM, Jeff King <peff@peff.net> wrote:
> > 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` is running. We
> > might hit a sequence like:
> 
> Probably want to drop one of the "is running"s...

Whoops. Not matter how many times I read it over...

It should be:

  Simultaneously, git-gc is running, which is doing a `git repack -ad`.

-Peff