Hi,
Here is a third reroll of my series to introduce an on-disk format for the
reverse index. Since the first series (to introduce a new API) has been merged
to 'next', this series has been rebased onto 'next', too.
This version is largely unchanged from the previous, with the following
exceptions:
- Some commit messages and documentation have been clarified to address
reviewer questions (including why we don't want to store offsets in the .rev
file, and that all four-byte numbers are in network order, etc.).
- A few more things are done on opening the revindex file, namely checking
that the version/hash ID are known.
- The idiom "load in memory" has been removed.
- Other minor changes.
A range diff is below.
Thanks in advance for your review.
Taylor Blau (10):
packfile: prepare for the existence of '*.rev' files
pack-write.c: prepare to write 'pack-*.rev' files
builtin/index-pack.c: allow stripping arbitrary extensions
builtin/index-pack.c: write reverse indexes
builtin/pack-objects.c: respect 'pack.writeReverseIndex'
Documentation/config/pack.txt: advertise 'pack.writeReverseIndex'
t: prepare for GIT_TEST_WRITE_REV_INDEX
t: support GIT_TEST_WRITE_REV_INDEX
pack-revindex: ensure that on-disk reverse indexes are given
precedence
t5325: check both on-disk and in-memory reverse index
Documentation/config/pack.txt | 7 ++
Documentation/git-index-pack.txt | 18 ++-
Documentation/technical/pack-format.txt | 20 ++++
builtin/index-pack.c | 69 +++++++++--
builtin/pack-objects.c | 9 ++
builtin/repack.c | 1 +
ci/run-build-and-tests.sh | 1 +
object-store.h | 3 +
pack-revindex.c | 148 ++++++++++++++++++++++--
pack-revindex.h | 14 ++-
pack-write.c | 120 ++++++++++++++++++-
pack.h | 4 +
packfile.c | 13 ++-
packfile.h | 1 +
t/README | 3 +
t/t5319-multi-pack-index.sh | 5 +-
t/t5325-reverse-index.sh | 142 +++++++++++++++++++++++
t/t5604-clone-reference.sh | 2 +-
t/t5702-protocol-v2.sh | 12 +-
t/t6500-gc.sh | 6 +-
t/t9300-fast-import.sh | 5 +-
tmp-objdir.c | 6 +-
22 files changed, 567 insertions(+), 42 deletions(-)
create mode 100755 t/t5325-reverse-index.sh
Range-diff against v2:
21: 6742c15c84 ! 1: 6f8b70ab27 packfile: prepare for the existence of '*.rev' files
@@ Commit message
is versioned, so we are free to pursue these in the future.) But, cold
cache performance likely isn't interesting outside of one-off cases like
asking for the size of an object directly. In real-world usage, Git is
- often performing many operations in the revindex,
+ often performing many operations in the revindex (i.e., asking about
+ many objects rather than a single one).
The trade-off is worth it, since we will avoid the vast majority of the
cost of generating the revindex that the extra pointer chase will look
@@ Documentation/technical/pack-format.txt: Pack file entry: <+
+
+ - A 4-byte magic number '0x52494458' ('RIDX').
+
-+ - A 4-byte version identifier (= 1)
++ - A 4-byte version identifier (= 1).
+
-+ - A 4-byte hash function identifier (= 1 for SHA-1, 2 for SHA-256)
++ - A 4-byte hash function identifier (= 1 for SHA-1, 2 for SHA-256).
+
-+ - A table of index positions, sorted by their corresponding offsets in the
-+ packfile.
++ - A table of index positions (one per packed object, num_objects in
++ total, each a 4-byte unsigned integer in network order), sorted by
++ their corresponding offsets in the packfile.
+
+ - A trailer, containing a:
+
+ checksum of the corresponding packfile, and
+
+ a checksum of all of the above.
++
++All 4-byte numbers are in network order.
+
== multi-pack-index (MIDX) files have the following format:
@@ object-store.h: struct packed_git {
multi_pack_index:1;
unsigned char hash[GIT_MAX_RAWSZ];
struct revindex_entry *revindex;
-+ const void *revindex_data;
-+ const void *revindex_map;
++ const uint32_t *revindex_data;
++ const uint32_t *revindex_map;
+ size_t revindex_size;
/* something like ".git/objects/pack/xxxxx.pack" */
char pack_name[FLEX_ARRAY]; /* more */
@@ pack-revindex.c: static void create_pack_revindex(struct packed_git *p)
}
-int load_pack_revindex(struct packed_git *p)
-+static int load_pack_revindex_from_memory(struct packed_git *p)
++static int create_pack_revindex_in_memory(struct packed_git *p)
{
- if (!p->revindex) {
- if (open_pack_index(p))
@@ pack-revindex.c: static void create_pack_revindex(struct packed_git *p)
+ return xstrfmt("%.*s.rev", (int)len, p->pack_name);
+}
+
-+#define RIDX_MIN_SIZE (12 + (2 * the_hash_algo->rawsz))
++#define RIDX_HEADER_SIZE (12)
++#define RIDX_MIN_SIZE (RIDX_HEADER_SIZE + (2 * the_hash_algo->rawsz))
++
++struct revindex_header {
++ uint32_t signature;
++ uint32_t version;
++ uint32_t hash_id;
++};
+
+static int load_revindex_from_disk(char *revindex_name,
+ uint32_t num_objects,
-+ const void **data, size_t *len)
++ const uint32_t **data_p, size_t *len_p)
+{
+ int fd, ret = 0;
+ struct stat st;
++ void *data = NULL;
+ size_t revindex_size;
++ struct revindex_header *hdr;
+
+ fd = git_open(revindex_name);
+
@@ pack-revindex.c: static void create_pack_revindex(struct packed_git *p)
+ goto cleanup;
+ }
+
-+ *len = revindex_size;
-+ *data = xmmap(NULL, revindex_size, PROT_READ, MAP_PRIVATE, fd, 0);
++ data = xmmap(NULL, revindex_size, PROT_READ, MAP_PRIVATE, fd, 0);
++ hdr = data;
++
++ if (ntohl(hdr->signature) != RIDX_SIGNATURE) {
++ ret = error(_("reverse-index file %s has unknown signature"), revindex_name);
++ goto cleanup;
++ }
++ if (ntohl(hdr->version) != 1) {
++ ret = error(_("reverse-index file %s has unsupported version %"PRIu32),
++ revindex_name, ntohl(hdr->version));
++ goto cleanup;
++ }
++ if (!(ntohl(hdr->hash_id) == 1 || ntohl(hdr->hash_id) == 2)) {
++ ret = error(_("reverse-index file %s has unsupported hash id %"PRIu32),
++ revindex_name, ntohl(hdr->hash_id));
++ goto cleanup;
++ }
+
+cleanup:
++ if (ret) {
++ if (data)
++ munmap(data, revindex_size);
++ } else {
++ *len_p = revindex_size;
++ *data_p = (const uint32_t *)data;
++ }
++
+ close(fd);
+ return ret;
+}
@@ pack-revindex.c: static void create_pack_revindex(struct packed_git *p)
+ if (ret)
+ goto cleanup;
+
-+ p->revindex_data = (char *)p->revindex_map + 12;
++ p->revindex_data = (const uint32_t *)((const char *)p->revindex_map + RIDX_HEADER_SIZE);
+
+cleanup:
+ free(revindex_name);
@@ pack-revindex.c: static void create_pack_revindex(struct packed_git *p)
+
+ if (!load_pack_revindex_from_disk(p))
+ return 0;
-+ else if (!load_pack_revindex_from_memory(p))
++ else if (!create_pack_revindex_in_memory(p))
+ return 0;
+ return -1;
+}
@@ pack-revindex.c: int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_
+ if (p->revindex)
+ return p->revindex[pos].nr;
+ else
-+ return get_be32((char *)p->revindex_data + (pos * sizeof(uint32_t)));
++ return get_be32(p->revindex_data + pos);
}
off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos)
@@ pack-revindex.c: int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_
}
## pack-revindex.h ##
-@@ pack-revindex.h: struct packed_git;
+@@
+ * can be found
+ */
+
++#define RIDX_SIGNATURE 0x52494458 /* "RIDX" */
++#define RIDX_VERSION 1
++
+ struct packed_git;
+
/*
* load_pack_revindex populates the revindex's internal data-structures for the
* given pack, returning zero on success and a negative value otherwise.
+ *
-+ * If a '.rev' file is present, it is checked for consistency, mmap'd, and
-+ * pointers are assigned into it (instead of using the in-memory variant).
++ * If a '.rev' file is present it is mmap'd, and pointers are assigned into it
++ * (instead of using the in-memory variant).
*/
int load_pack_revindex(struct packed_git *p);
@@ packfile.h: uint32_t get_pack_fanout(struct packed_git *p, uint32_t value);
## tmp-objdir.c ##
@@ tmp-objdir.c: static int pack_copy_priority(const char *name)
+ return 1;
+ if (ends_with(name, ".pack"))
return 2;
- if (ends_with(name, ".idx"))
+- if (ends_with(name, ".idx"))
++ if (ends_with(name, ".rev"))
return 3;
- return 4;
-+ if (ends_with(name, ".rev"))
++ if (ends_with(name, ".idx"))
+ return 4;
+ return 5;
}
22: 8648c87fa7 ! 2: 5efc870742 pack-write.c: prepare to write 'pack-*.rev' files
@@ Commit message
from within 'write_rev_file()', which is called from
'finish_tmp_packfile()'.
+ Similar to the process by which the reverse index is computed in memory,
+ these new paths also have to sort a list of objects by their offsets
+ within a packfile. These new paths use a qsort() (as opposed to a radix
+ sort), since our specialized radix sort requires a full revindex_entry
+ struct per object, which is more memory than we need to allocate.
+
+ The qsort is obviously slower, but the theoretical slowdown would
+ require a repository with a large amount of objects, likely implying
+ that the time spent in, say, pack-objects during a repack would dominate
+ the overall runtime.
+
Signed-off-by: Taylor Blau <me@xxxxxxxxxxxx>
## pack-write.c ##
@@ pack-write.c: const char *write_idx_file(const char *index_name, struct pack_idx
+ return 0;
+}
+
-+#define RIDX_SIGNATURE 0x52494458 /* "RIDX" */
-+#define RIDX_VERSION 1
-+
+static void write_rev_header(struct hashfile *f)
+{
+ uint32_t oid_version;
@@ pack-write.c: void finish_tmp_packfile(struct strbuf *name_buffer,
+
free((void *)idx_tmp_name);
}
+
## pack.h ##
@@ pack.h: struct pack_idx_option {
@@ pack.h: struct pack_idx_option {
uint32_t version;
uint32_t off32_limit;
-@@ pack.h: off_t write_pack_header(struct hashfile *f, uint32_t);
- void fixup_pack_header_footer(int, unsigned char *, const char *, uint32_t, unsigned char *, off_t);
- char *index_pack_lockfile(int fd);
+@@ pack.h: struct ref;
+
+ void write_promisor_file(const char *promisor_name, struct ref **sought, int nr_sought);
+const char *write_rev_file(const char *rev_name, struct pack_idx_entry **objects, uint32_t nr_objects, const unsigned char *hash, unsigned flags);
+
-: ---------- > 3: 8a3e70454b builtin/index-pack.c: allow stripping arbitrary extensions
23: 5b18ada611 ! 4: a8ee59fccf builtin/index-pack.c: write reverse indexes
@@ Documentation/git-index-pack.txt: git-index-pack - Build pack index file for an
OPTIONS
@@ Documentation/git-index-pack.txt: OPTIONS
- file is constructed from the name of packed archive
- file by replacing .pack with .idx (and the program
fails if the name of packed archive does not end
-- with .pack).
-+ with .pack). Incompatible with `--rev-index`.
-+
+ with .pack).
+
+--[no-]rev-index::
+ When this flag is provided, generate a reverse index
+ (a `.rev` file) corresponding to the given pack. If
+ `--verify` is given, ensure that the existing
+ reverse index is correct. Takes precedence over
+ `pack.writeReverseIndex`.
-
++
--stdin::
When this flag is provided, the pack is read from stdin
+ instead and a copy is then written to <pack-file>. If
## builtin/index-pack.c ##
@@
@@ builtin/index-pack.c
struct object_entry {
struct pack_idx_entry idx;
-@@ builtin/index-pack.c: static void fix_unresolved_deltas(struct hashfile *f)
- free(sorted_by_pos);
- }
-
--static const char *derive_filename(const char *pack_name, const char *suffix,
-- struct strbuf *buf)
-+static const char *derive_filename(const char *pack_name, const char *strip,
-+ const char *suffix, struct strbuf *buf)
- {
- size_t len;
-- if (!strip_suffix(pack_name, ".pack", &len))
-- die(_("packfile name '%s' does not end with '.pack'"),
-- pack_name);
-+ if (!strip_suffix(pack_name, strip, &len))
-+ die(_("packfile name '%s' does not end with '%s'"),
-+ pack_name, strip);
- strbuf_add(buf, pack_name, len);
- strbuf_addch(buf, '.');
- strbuf_addstr(buf, suffix);
-@@ builtin/index-pack.c: static void write_special_file(const char *suffix, const char *msg,
- int msg_len = strlen(msg);
-
- if (pack_name)
-- filename = derive_filename(pack_name, suffix, &name_buf);
-+ filename = derive_filename(pack_name, ".pack", suffix, &name_buf);
- else
- filename = odb_pack_name(&name_buf, hash, suffix);
-
@@ builtin/index-pack.c: static void write_special_file(const char *suffix, const char *msg,
static void final(const char *final_pack_name, const char *curr_pack_name,
@@ builtin/index-pack.c: int cmd_index_pack(int argc, const char **argv, const char
usage(index_pack_usage);
continue;
@@ builtin/index-pack.c: int cmd_index_pack(int argc, const char **argv, const char *prefix)
- if (from_stdin && hash_algo)
- die(_("--object-format cannot be used with --stdin"));
if (!index_name && pack_name)
-- index_name = derive_filename(pack_name, "idx", &index_name_buf);
-+ index_name = derive_filename(pack_name, ".pack", "idx", &index_name_buf);
-+
+ index_name = derive_filename(pack_name, "pack", "idx", &index_name_buf);
+
+ opts.flags &= ~(WRITE_REV | WRITE_REV_VERIFY);
+ if (rev_index) {
+ opts.flags |= verify ? WRITE_REV_VERIFY : WRITE_REV;
+ if (index_name)
+ rev_index_name = derive_filename(index_name,
-+ ".idx", "rev",
++ "idx", "rev",
+ &rev_index_name_buf);
+ }
-
++
if (verify) {
if (!index_name)
+ die(_("--verify with no packfile name given"));
@@ builtin/index-pack.c: int cmd_index_pack(int argc, const char **argv, const char *prefix)
for (i = 0; i < nr_objects; i++)
idx_objects[i] = &objects[i].idx;
24: 68bde3ea97 = 5: 5bebe05a16 builtin/pack-objects.c: respect 'pack.writeReverseIndex'
25: 38a253d0ce = 6: 7e29f2d3a0 Documentation/config/pack.txt: advertise 'pack.writeReverseIndex'
26: 12cdf2d67a = 7: 7cf16485cc t: prepare for GIT_TEST_WRITE_REV_INDEX
27: 6b647d9775 ! 8: 02550a251d t: support GIT_TEST_WRITE_REV_INDEX
@@ builtin/pack-objects.c: int cmd_pack_objects(int argc, const char **argv, const
## ci/run-build-and-tests.sh ##
@@ ci/run-build-and-tests.sh: linux-gcc)
- export GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=1
export GIT_TEST_MULTI_PACK_INDEX=1
export GIT_TEST_ADD_I_USE_BUILTIN=1
+ export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=master
+ export GIT_TEST_WRITE_REV_INDEX=1
make test
;;
@@ pack-revindex.h
* can be found
*/
++
+ #define RIDX_SIGNATURE 0x52494458 /* "RIDX" */
+ #define RIDX_VERSION 1
+
+#define GIT_TEST_WRITE_REV_INDEX "GIT_TEST_WRITE_REV_INDEX"
+
struct packed_git;
28: 48926ae182 ! 9: a66d2f9f7c pack-revindex: ensure that on-disk reverse indexes are given precedence
@@ pack-revindex.c
off_t offset;
@@ pack-revindex.c: static void create_pack_revindex(struct packed_git *p)
- static int load_pack_revindex_from_memory(struct packed_git *p)
+ static int create_pack_revindex_in_memory(struct packed_git *p)
{
+ if (git_env_bool(GIT_TEST_REV_INDEX_DIE_IN_MEMORY, 0))
+ die("dying as requested by '%s'",
@@ pack-revindex.c: static void create_pack_revindex(struct packed_git *p)
## pack-revindex.h ##
@@
- */
+ #define RIDX_VERSION 1
#define GIT_TEST_WRITE_REV_INDEX "GIT_TEST_WRITE_REV_INDEX"
+#define GIT_TEST_REV_INDEX_DIE_IN_MEMORY "GIT_TEST_REV_INDEX_DIE_IN_MEMORY"
-: ---------- > 10: 38c8afabf2 t5325: check both on-disk and in-memory reverse index
--
2.30.0.138.g6d7191ea01
