git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH 19/19] pack-bitmap: implement optional name_hash cache

From
Jeff King <peff@peff.net>
Date
Oct 24, 2013, 18:08 UTC
Message-ID
<20131024180850.GS24180@sigill.intra.peff.net>
In-Reply-To
<20131024175915.GA23398@sigill.intra.peff.net>
From: Vicent Marti <tanoku@gmail.com>

When we use pack bitmaps rather than walking the object graph, we end up with the list of objects to include in the packfile, but we do not know the path at which any tree or blob objects would be found.

In a recently packed repository, this is fine. A fetch would use the paths only as a heuristic in the delta compression phase, and a fully packed repository should not need to do much delta compression.

As time passes, though, we may acquire more objects on top of our large bitmapped pack. If clients fetch frequently, then they never even look at the bitmapped history, and all works as usual. However, a client who has not fetched since the last bitmap repack will have "have" tips in the bitmapped history, but "want" newer objects.

The bitmaps themselves degrade gracefully in this circumstance. We manually walk the more recent bits of history, and then use bitmaps when we hit them.

But we would also like to perform delta compression between the newer objects and the bitmapped objects (both to delta against what we know the user already has, but also between "new" and "old" objects that the user is fetching). The lack of pathnames makes our delta heuristics much less effective.

This patch adds an optional cache of the 32-bit name_hash values to the end of the bitmap file. If present, a reader can use it to match bitmapped and non-bitmapped names during delta compression.

Signed-off-by: Vicent Marti <tanoku@gmail.com>
Signed-off-by: Jeff King <peff@peff.net>
---
 Documentation/technical/bitmap-format.txt | 33 +++++++++++++++++++++++++++++++
 pack-bitmap-write.c                       | 18 ++++++++++++++++-
 pack-bitmap.c                             | 11 +++++++++++
 pack-bitmap.h                             |  1 +
 4 files changed, 62 insertions(+), 1 deletion(-)
diff --git a/Documentation/technical/bitmap-format.txt b/Documentation/technical/bitmap-format.txt
index c686dd1..36a511c 100644
--- a/Documentation/technical/bitmap-format.txt
+++ b/Documentation/technical/bitmap-format.txt
@@ -21,6 +21,12 @@ GIT bitmap v1 format
 			requirement for the bitmap index format, also present in JGit,
 			that greatly reduces the complexity of the implementation.
 
+			- BITMAP_OPT_HASH_CACHE (0x4)
+			If present, the end of the bitmap file contains
+			`N` 32-bit name-hash values, one per object in the
+			pack. The format and meaning of the name-hash is
+			described below.
+
 		4-byte entry count (network byte order)
 
 			The total count of entries (bitmapped commits) in this bitmap index.
@@ -129,3 +135,30 @@ The bitstream represented by the above chunk is then:
 The next word after `L_M` (if any) must again be a RLW, for the next
 chunk.  For efficient appending to the bitstream, the EWAH stores a
 pointer to the last RLW in the stream.
+
+
+== Appendix B: Optional Bitmap Sections
+
+These sections may or may not be present in the `.bitmap` file; their
+presence is indicated by the header flags section described above.
+
+Name-hash cache
+---------------
+
+If the BITMAP_OPT_HASH_CACHE flag is set, the end of the bitmap contains
+a cache of 32-bit values, one per object in the pack. The value at
+position `i` is the hash of the pathname at which the `i`th object
+(counting in index order) in the pack can be found.  This can be fed
+into the delta heuristics to compare objects with similar pathnames.
+
+The hash algorithm used is:
+
+    hash = 0;
+    while ((c = *name++))
+	    if (!isspace(c))
+		    hash = (hash >> 2) + (c << 24);
+
+Note that this hashing scheme is tied to the BITMAP_OPT_HASH_CACHE flag.
+If implementations want to choose a different hashing scheme, they are
+free to do so, but MUST allocate a new header flag (because comparing
+hashes made under two different schemes would be pointless).
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index 6a589c3..c44874a 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -492,6 +492,19 @@ static void write_selected_commits_v1(struct sha1file *f,
 	}
 }
 
+static void write_hash_cache(struct sha1file *f,
+			     struct pack_idx_entry **index,
+			     uint32_t index_nr)
+{
+	uint32_t i;
+
+	for (i = 0; i < index_nr; ++i) {
+		struct object_entry *entry = (struct object_entry *)index[i];
+		uint32_t hash_value = htonl(entry->hash);
+		sha1write(f, &hash_value, sizeof(hash_value));
+	}
+}
+
 void bitmap_writer_set_checksum(unsigned char *sha1)
 {
 	hashcpy(writer.pack_checksum, sha1);
@@ -503,7 +516,7 @@ void bitmap_writer_finish(struct pack_idx_entry **index,
 {
 	static char tmp_file[PATH_MAX];
 	static uint16_t default_version = 1;
-	static uint16_t flags = BITMAP_OPT_FULL_DAG;
+	static uint16_t flags = BITMAP_OPT_FULL_DAG | BITMAP_OPT_HASH_CACHE;
 	struct sha1file *f;
 
 	struct bitmap_disk_header header;
@@ -527,6 +540,9 @@ void bitmap_writer_finish(struct pack_idx_entry **index,
 	dump_bitmap(f, writer.tags);
 	write_selected_commits_v1(f, index, index_nr);
 
+	if (flags & BITMAP_OPT_HASH_CACHE)
+		write_hash_cache(f, index, index_nr);
+
 	sha1close(f, NULL, CSUM_FSYNC);
 
 	if (adjust_shared_perm(tmp_file))
diff --git a/pack-bitmap.c b/pack-bitmap.c
index 86ce677..a7c553d 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -68,6 +68,9 @@ static struct bitmap_index {
 	/* Number of bitmapped commits */
 	uint32_t entry_count;
 
+	/* Name-hash cache (or NULL if not present). */
+	uint32_t *hashes;
+
 	/*
 	 * Extended index.
 	 *
@@ -154,6 +157,11 @@ static int load_bitmap_header(struct bitmap_index *index)
 		if ((flags & BITMAP_OPT_FULL_DAG) == 0)
 			return error("Unsupported options for bitmap index file "
 				"(Git requires BITMAP_OPT_FULL_DAG)");
+
+		if (flags & BITMAP_OPT_HASH_CACHE) {
+			index->hashes = index->map + index->map_size - 20 -
+				(sizeof(uint32_t) * index->pack->num_objects);
+		}
 	}
 
 	index->entry_count = ntohl(header->entry_count);
@@ -621,6 +629,9 @@ static void show_objects_for_type(
 			entry = &bitmap_git.reverse_index->revindex[pos + offset];
 			sha1 = nth_packed_object_sha1(bitmap_git.pack, entry->nr);
 
+			if (bitmap_git.hashes)
+				hash = ntohl(bitmap_git.hashes[entry->nr]);
+
 			show_reach(sha1, object_type, 0, hash, bitmap_git.pack, entry->offset);
 		}
 
diff --git a/pack-bitmap.h b/pack-bitmap.h
index 18f4d4c..6053453 100644
--- a/pack-bitmap.h
+++ b/pack-bitmap.h
@@ -28,6 +28,7 @@ static const char BITMAP_IDX_SIGNATURE[] = {'B', 'I', 'T', 'M'};;
 
 enum pack_bitmap_opts {
 	BITMAP_OPT_FULL_DAG = 1,
+	BITMAP_OPT_HASH_CACHE = 4,
 };
 
 enum pack_bitmap_flags {

-- 
1.8.4.1.898.g8bf8a41.dirty
Previous: Jeff KingNext: Junio C Hamano
Message 48 of 87 in “pack bitmaps”
  1. 0/19 pack bitmapsJeff King, Oct 24, 2013
  2. 01/19 sha1write: make buffer const-correctJeff King, Oct 24, 2013
  3. 02/19 revindex: Export new APIsJeff King, Oct 24, 2013
  4. 03/19 pack-objects: Refactor the packing listJeff King, Oct 24, 2013
  5. 04/19 pack-objects: factor out name_hashJeff King, Oct 24, 2013
  6. 05/19 revision: allow setting custom limiter functionJeff King, Oct 24, 2013
  7. 06/19 sha1_file: export `git_open_noatime`Jeff King, Oct 24, 2013
  8. 07/19 compat: add endianness helpersJeff King, Oct 24, 2013
  9. Thomas RastOct 26, 2013
  10. Jeff KingOct 30, 2013
  11. Vicent MartíOct 30, 2013
  12. 08/19 ewah: compressed bitmap implementationJeff King, Oct 24, 2013
  13. Junio C HamanoOct 24, 2013
  14. Jeff KingOct 25, 2013
  15. Thomas RastOct 26, 2013
  16. 09/19 documentation: add documentation for the bitmap formatJeff King, Oct 24, 2013
  17. Duy NguyenOct 25, 2013
  18. Jeff KingOct 25, 2013
  19. Duy NguyenOct 25, 2013
  20. Shawn PearceOct 25, 2013
  21. Jeff KingOct 30, 2013
  22. Shawn PearceOct 30, 2013
  23. Vicent MartiOct 30, 2013
  24. Vicent MartiOct 30, 2013
  25. 10/19 pack-bitmap: add support for bitmap indexesJeff King, Oct 24, 2013
  26. Shawn PearceOct 25, 2013
  27. Jeff KingOct 30, 2013
  28. Shawn PearceOct 30, 2013
  29. Vicent MartiOct 30, 2013
  30. Shawn PearceOct 30, 2013
  31. Jeff KingOct 30, 2013
  32. 11/19 pack-objects: use bitmaps when packing objectsJeff King, Oct 24, 2013
  33. Shawn PearceOct 25, 2013
  34. Jeff KingOct 30, 2013
  35. Shawn PearceOct 30, 2013
  36. Vicent MartiOct 30, 2013
  37. 12/19 rev-list: add bitmap mode to speed up object listsJeff King, Oct 24, 2013
  38. Shawn PearceOct 25, 2013
  39. Jeff KingOct 30, 2013
  40. 13/19 pack-objects: implement bitmap writingJeff King, Oct 24, 2013
  41. Duy NguyenOct 25, 2013
  42. Jeff KingOct 25, 2013
  43. 14/19 repack: stop using magic number for ARRAY_SIZE(exts)Jeff King, Oct 24, 2013
  44. 15/19 repack: turn exts array into array-of-structJeff King, Oct 24, 2013
  45. 16/19 repack: handle optional files created by pack-objectsJeff King, Oct 24, 2013
  46. 17/19 repack: consider bitmaps when performing repacksJeff King, Oct 24, 2013
  47. 18/19 t: add basic bitmap functionality testsJeff King, Oct 24, 2013
  48. 19/19 pack-bitmap: implement optional name_hash cacheJeff King, Oct 24, 2013
  49. Junio C HamanoOct 24, 2013
  50. Junio C HamanoOct 25, 2013
  51. 0/19 pack bitmapsJeff King, Oct 25, 2013
  52. 01/19 sha1write: make buffer const-correctJeff King, Oct 25, 2013
  53. 02/19 revindex: Export new APIsJeff King, Oct 25, 2013
  54. 03/19 pack-objects: Refactor the packing listJeff King, Oct 25, 2013
  55. 04/19 pack-objects: factor out name_hashJeff King, Oct 25, 2013
  56. 05/19 revision: allow setting custom limiter functionJeff King, Oct 25, 2013
  57. 06/19 sha1_file: export `git_open_noatime`Jeff King, Oct 25, 2013
  58. 07/19 compat: add endianness helpersJeff King, Oct 25, 2013
  59. 08/19 ewah: compressed bitmap implementationJeff King, Oct 25, 2013
  60. 09/19 documentation: add documentation for the bitmap formatJeff King, Oct 25, 2013
  61. 10/19 pack-bitmap: add support for bitmap indexesJeff King, Oct 25, 2013
  62. Junio C HamanoOct 25, 2013
  63. Jeff KingOct 26, 2013
  64. Jeff KingOct 26, 2013
  65. Junio C HamanoOct 28, 2013
  66. Jeff KingOct 30, 2013
  67. Duy NguyenOct 26, 2013
  68. Jeff KingOct 30, 2013
  69. 11/19 pack-objects: use bitmaps when packing objectsJeff King, Oct 25, 2013
  70. Duy NguyenOct 26, 2013
  71. Jeff KingOct 30, 2013
  72. Duy NguyenOct 30, 2013
  73. Jeff KingOct 30, 2013
  74. Duy NguyenOct 31, 2013
  75. 12/19 rev-list: add bitmap mode to speed up object listsJeff King, Oct 25, 2013
  76. 13/19 pack-objects: implement bitmap writingJeff King, Oct 25, 2013
  77. 14/19 repack: stop using magic number for ARRAY_SIZE(exts)Jeff King, Oct 25, 2013
  78. 15/19 repack: turn exts array into array-of-structJeff King, Oct 25, 2013
  79. 16/19 repack: handle optional files created by pack-objectsJeff King, Oct 25, 2013
  80. 17/19 repack: consider bitmaps when performing repacksJeff King, Oct 25, 2013
  81. 18/19 t: add basic bitmap functionality testsJeff King, Oct 25, 2013
  82. SZEDER GáborOct 28, 2013
  83. Jeff KingOct 30, 2013
  84. 19/19 pack-bitmap: implement optional name_hash cacheJeff King, Oct 25, 2013
  85. 20/19 count-objects: consider .bitmap without .pack/.idx pair garbageNguyễn Thái Ngọc Duy, Oct 26, 2013
  86. Jeff KingOct 30, 2013
  87. Junio C HamanoOct 30, 2013

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.