{"thread":{"id":"8349","subject":"[RFC] super indexes to span multiple packfiles","startedAt":"2007-05-29T07:16:22Z","lastAt":"2007-05-30T09:40:35Z","messageCount":7,"participants":["Shawn O. Pearce","Jon Smirl","Nicolas Pitre","Avi Kivity","Geert Bosch"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"43544","messageId":"20070529071622.GA8905@spearce.org","threadId":"8349","inReplyTo":null,"subject":"[RFC] super indexes to span multiple packfiles","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-05-29T07:16:22Z","receivedAt":"2007-05-29T07:16:22Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Dana talking about some sort of global index that spans all packfiles\ngot me thinking.  Could we build a \"super index\" that covered all\nknown packfiles at the time it was created, but that doesn't really\nhurt us when the packfiles are repacked?  Or that doesn't have to\nbe repacked every single time a packfile is added to the repository.\n\nThis patch introduces a new command `git super-index` which reads\nall known pack-*.idx files and merges them together into a single\nsuper-index.sdx file, located in $GIT_OBJECT_DIRECTORY/pack.\nAt runtime we load the first super-index.sdx file we come across\nduring our packfile scanning.  Using a single super-index works\nbecause the super-index.sdx should contain data for this repository's\npacks, and for all of its alternate's packs.\n\nA super-index holds a list of packfile names that it will match at\nthe start of its data file.  A super-index can only be used for\nthe pack(s) mentioned there.  At runtime we try to lazily match\nthese pack SHA-1 names up to the struct packed_git.sha1 field,\ngiving us the struct packed_git* for direct index access.\n\nThe super-index does not hold the object offsets; instead it holds\nan array of percentage shifts within the index fan-out ranges.\nThe shifts are normalized into the range 1-65535.\n\nThe basic idea is:\n\n 1) Use the first byte of the input SHA-1 to index into the\n    fan-out table of the super-index.sdx.\n\n 2) Use the next sdx_prefix bytes of the SHA-1 to binary search\n    through that region of the sdx file.  Since we are working\n    only with the abbreviated prefix the memcmp() has less data to\n    wade through.  We've also eliminated the common first byte,\n    thanks to the fan-out table.\n\n 3) The matching record in the sdx table holds sdx_packs uint16_t\n    values.  The indexes in that list corresponding to the index\n    of the pack SHA-1 names in the header of the sdx file; hence\n    the first uint16_t goes to the first packfile, the second to\n    the second, etc.  I call these \"shifts\".  I don't know why.\n\n 4) If the shift value for a pack is 0 then that pack does not\n    contain any objects that start with that prefix.  So a 0 shift\n    means we do not need to scan the corresponding pack's .idx file\n    for an object.\n\n 5) If the shift is non-zero then there is at least one object in\n    the corresponding packfile starting with the prefix and further\n    searching in the specific packfile is required.  The shift is\n    actually the percentage within the range of [lo, hi) in the\n    pack's .idx of where the middle of that prefix's block appears.\n    We use this as a seed value for mi, rather than (lo+hi)/2, as it\n    gets us much much closer to the interesting SHA-1s in the .idx.\n\n 6) We binary search the .idx in a traditional way, once we have\n    selected a reasonable guess for the starting position.\n\n 7) If a packfile cannot be found at runtime (e.g. it has been\n    repacked away) we treat it's shift as though it were 0;\n    the object is not in that packfile (since the packfile does\n    not exist).\n\n 8) If the sdx cannot give us the object, we fallback to standard\n    packfile scanning.\n\nIn the single packfile case (everything repacked into one) this\nis not faster; its actually slightly slower.  With a handful of\nsmaller recent packfiles (such as immediately after a git-fetch)\nit breaks even with the stock code.  I haven't tested it yet with\na high number of packfiles (e.g. 20).  I suspect it won't gain us\na lot up there either...\n\nSo in short this shouldn't be applied, because its not any faster,\nand is sometimes slower.  But I'm tossing it out here for discussion.\nI'm also not documenting the new super-index command line program,\nbecause I don't think this should be applied.  ;-)\n\n----\n .gitignore             |    1 +\n Makefile               |    1 +\n builtin-pack-objects.c |    2 +-\n builtin-super-index.c  |  226 ++++++++++++++++++++++++++++++++++++++++++++++++\n builtin.h              |    1 +\n cache.h                |    2 +-\n git.c                  |    1 +\n pack-check.c           |    4 +-\n pack.h                 |   17 ++++\n sha1_file.c            |  208 ++++++++++++++++++++++++++++++++++++--------\n 10 files changed, 423 insertions(+), 40 deletions(-)\n create mode 100644 builtin-super-index.c\n\ndiff --git a/.gitignore b/.gitignore\nindex 4dc0c39..3cd1b2c 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -126,6 +126,7 @@ git-ssh-push\n git-ssh-upload\n git-status\n git-stripspace\n+git-super-index\n git-svn\n git-svnimport\n git-symbolic-ref\ndiff --git a/Makefile b/Makefile\nindex 29243c6..26ac766 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -371,6 +371,7 @@ BUILTIN_OBJS = \\\n \tbuiltin-shortlog.o \\\n \tbuiltin-show-branch.o \\\n \tbuiltin-stripspace.o \\\n+\tbuiltin-super-index.o \\\n \tbuiltin-symbolic-ref.o \\\n \tbuiltin-tar-tree.o \\\n \tbuiltin-unpack-objects.o \\\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex d165f10..3b49336 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -756,7 +756,7 @@ static int add_object_entry(const unsigned char *sha1, enum object_type type,\n \t}\n \n \tfor (p = packed_git; p; p = p->next) {\n-\t\toff_t offset = find_pack_entry_one(sha1, p);\n+\t\toff_t offset = find_pack_entry_one(sha1, p, 0);\n \t\tif (offset) {\n \t\t\tif (!found_pack) {\n \t\t\t\tfound_offset = offset;\ndiff --git a/builtin-super-index.c b/builtin-super-index.c\nnew file mode 100644\nindex 0000000..9f47760\n--- /dev/null\n+++ b/builtin-super-index.c\n@@ -0,0 +1,226 @@\n+#include \"cache.h\"\n+#include \"pack.h\"\n+#include \"csum-file.h\"\n+\n+struct sdx_entry {\n+\tunsigned char prefix[20];\n+\tuint16_t *splits;\n+};\n+\n+static unsigned pack_cnt;\n+static unsigned entry_cnt;\n+static unsigned avail_cnt;\n+static unsigned prefix_len = 5;\n+static uint32_t *current;\n+static struct packed_git **packs;\n+static struct sdx_entry *entries;\n+\n+static unsigned split_avail;\n+static uint16_t *split_free;\n+\n+static void select_packs()\n+{\n+\tstruct packed_git *p;\n+\tunsigned i;\n+\n+\tprepare_packed_git();\n+\tfor (p = packed_git; p; p = p->next)\n+\t\tpack_cnt++;\n+\n+\tpacks = xmalloc(pack_cnt * sizeof(packs[0]));\n+\tcurrent = xcalloc(pack_cnt, sizeof(current[0]));\n+\tfor (p = packed_git, i = 0; p; p = p->next, i++) {\n+\t\tpacks[i] = p;\n+\t\topen_pack_index(p);\n+\t}\n+}\n+\n+static void compute_pack(struct sdx_entry *ent, unsigned pack_idx)\n+{\n+\tstruct packed_git *p = packs[pack_idx];\n+\tconst uint32_t *level1_ofs = p->index_data;\n+\tuint32_t hi, lo, mi, n = current[pack_idx];\n+\n+\t/* Determine the end of the range that matches */\n+\twhile (n < p->num_objects) {\n+\t\tconst unsigned char *c = nth_packed_object_sha1(p, n);\n+\t\tif (memcmp(c, ent->prefix, prefix_len) > 0)\n+\t\t\tbreak;\n+\t\tn++;\n+\t}\n+\tif (n == current[pack_idx])\n+\t\treturn;\n+\n+\t/* Determine the position within the fan-out subrange */\n+\tif (p->index_version > 1)\n+\t\tlevel1_ofs += 2;\n+\thi = ntohl(level1_ofs[*ent->prefix]);\n+\tlo = *ent->prefix ? ntohl(level1_ofs[*ent->prefix - 1]) : 0;\n+\tmi = (current[pack_idx] + n) / 2;\n+\tent->splits[pack_idx] = (mi - lo) * 65535 / (hi - lo) + 1;\n+\n+\tcurrent[pack_idx] = n;\n+}\n+\n+static int compute_next_entry()\n+{\n+\tunsigned i;\n+\tconst unsigned char *min = NULL;\n+\tstruct sdx_entry *ent;\n+\n+\t/* locate the minimum hash */\n+\tfor (i = 0; i < pack_cnt; i++) {\n+\t\tstruct packed_git *p = packs[i];\n+\t\tuint32_t n = current[i];\n+\t\tif (n < p->num_objects) {\n+\t\t\tconst unsigned char *c = nth_packed_object_sha1(p, n);\n+\t\t\tif (!min || memcmp(c, min, prefix_len) < 0)\n+\t\t\t\tmin = c;\n+\t\t}\n+\t}\n+\tif (!min)\n+\t\treturn 0;\n+\n+\tif (entry_cnt == avail_cnt) {\n+\t\tavail_cnt = avail_cnt * 3 / 2 + 128;\n+\t\tentries = xrealloc(entries, avail_cnt * sizeof(entries[0]));\n+\t}\n+\tif (split_avail < pack_cnt) {\n+\t\tsplit_avail = pack_cnt * (avail_cnt - entry_cnt);\n+\t\tsplit_free = xcalloc(split_avail, sizeof(split_free[0]));\n+\t}\n+\n+\tent = &entries[entry_cnt++];\n+\thashcpy(ent->prefix, min);\n+\n+\tent->splits = split_free;\n+\tsplit_free += pack_cnt;\n+\tsplit_avail -= pack_cnt;\n+\n+\t/* determine which packs match this entry */\n+\tfor (i = 0; i < pack_cnt; i++)\n+\t\tcompute_pack(ent, i);\n+\n+\treturn 1;\n+}\n+\n+static int read_only(const char *path)\n+{\n+\tmode_t mode = umask(0);\n+\n+\tumask(mode);\n+\tmode = 0444 & ~mode;\n+\tif (chmod(path, mode))\n+\t\treturn -1;\n+\treturn adjust_shared_perm(path);\n+}\n+\n+static void write_super_index()\n+{\n+\tchar tmpname[PATH_MAX];\n+\tstruct sha1file *f;\n+\tuint32_t i, array[256];\n+\tint fd;\n+\tstruct pack_sdx_header hdr;\n+\tstruct sdx_entry *curr = entries, *last = entries + entry_cnt;\n+\n+\tsnprintf(tmpname, sizeof(tmpname), \"%s/%s\",\n+\t\tget_object_directory(),\n+\t\t\"tmp_sdx_XXXXXX\");\n+\tfd = mkstemp(tmpname);\n+\tif (fd < 0)\n+\t\tdie(\"unable to create %s: %s\\n\", tmpname, strerror(errno));\n+\tf = sha1fd(fd, tmpname);\n+\n+\t/* Our file header, for once we plan ahead! */\n+\tmemset(&hdr, 0, sizeof(hdr));\n+\thdr.sdx_signature = htonl(PACK_SDX_SIGNATURE);\n+\thdr.sdx_version = htonl(1);\n+\thdr.sdx_packs = htons(pack_cnt);\n+\thdr.sdx_prefix = prefix_len - 1;\n+\tsha1write(f, &hdr, sizeof(hdr));\n+\n+\t/* Immediately after is the pack SHA-1 names */\n+\tfor (i = 0; i < pack_cnt; i++)\n+\t\tsha1write(f, packs[i]->sha1, sizeof(packs[i]->sha1));\n+\n+\t/*\n+\t * Write the first-level table (the list is sorted,\n+\t * but we use a 256-entry lookup to be able to avoid\n+\t * having to do eight extra binary search iterations).\n+\t */\n+\tfor (i = 0; i < 256; i++) {\n+\t\twhile (curr < last && curr->prefix[0] == i)\n+\t\t\tcurr++;\n+\t\tarray[i] = htonl(curr - entries);\n+\t}\n+\tsha1write(f, array, 256 * 4);\n+\n+\t/* Write the entries */\n+\tfor (curr = entries; curr < last; curr++) {\n+\t\tsha1write(f, curr->prefix + 1, prefix_len - 1);\n+\t\tsha1write(f, curr->splits, pack_cnt);\n+\t}\n+\n+\tsha1close(f, NULL, 1);\n+\tif (read_only(tmpname))\n+\t\tdie(\"cannot make file readable: %s\", strerror(errno));\n+\n+\tif (move_temp_to_file(tmpname,\n+\t\tmkpath(\"%s/pack/super-index.sdx\", get_object_directory())))\n+\t\tdie(\"cannot save super-index.sdx\");\n+}\n+\n+static void show_super_index()\n+{\n+\tunsigned i, j, multi_pack = 0;\n+\n+\tfor (i = 0; i < pack_cnt; i++)\n+\t\tprintf(\"pack %s\\n\", sha1_to_hex(packs[i]->sha1));\n+\n+\tfor (i = 0; i < entry_cnt; i++) {\n+\t\tstruct sdx_entry *ent = &entries[i];\n+\t\tchar *prefix_str = sha1_to_hex(ent->prefix);\n+\t\tunsigned matches = 0;\n+\n+\t\tprefix_str[2 * prefix_len] = 0;\n+\n+\t\tprintf(\"%s:\", prefix_str);\n+\t\tfor (j = 0; j < pack_cnt; j++) {\n+\t\t\tif (ent->splits[j]) {\n+\t\t\t\tmatches++;\n+\t\t\t\tprintf(\" %3u\", (int)ent->splits[j]);\n+\t\t\t} else\n+\t\t\t\tprintf(\" ----\");\n+\t\t}\n+\t\tprintf(\"\\n\");\n+\n+\t\tif (matches > 1)\n+\t\t\tmulti_pack++;\n+\t}\n+\n+\tprintf(\"%u packs, %u entries, %u%% unique\\n\",\n+\t\tpack_cnt, entry_cnt,\n+\t\t(entry_cnt - multi_pack) * 100 / entry_cnt);\n+}\n+\n+static const char super_index_usage[] =\n+\"git-super-index\";\n+\n+int cmd_super_index(int argc, char **argv, const char *prefix)\n+{\n+\tselect_packs();\n+\tif (!pack_cnt)\n+\t\tdie(\"no packfiles to super-index\");\n+\tif (pack_cnt == 1)\n+\t\twarning(\"only one packfile; a super-index is unnecessary\");\n+\n+\twhile (compute_next_entry())\n+\t\t/* nothing */;\n+\twrite_super_index();\n+\n+\tif (0)\n+\t\tshow_super_index();\n+\n+\treturn 0;\n+}\ndiff --git a/builtin.h b/builtin.h\nindex d3f3a74..2a11187 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -71,6 +71,7 @@ extern int cmd_shortlog(int argc, const char **argv, const char *prefix);\n extern int cmd_show(int argc, const char **argv, const char *prefix);\n extern int cmd_show_branch(int argc, const char **argv, const char *prefix);\n extern int cmd_stripspace(int argc, const char **argv, const char *prefix);\n+extern int cmd_super_index(int argc, const char **argv, const char *prefix);\n extern int cmd_symbolic_ref(int argc, const char **argv, const char *prefix);\n extern int cmd_tar_tree(int argc, const char **argv, const char *prefix);\n extern int cmd_unpack_objects(int argc, const char **argv, const char *prefix);\ndiff --git a/cache.h b/cache.h\nindex 0f4a05b..3c8a41d 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -490,7 +490,7 @@ extern unsigned char* use_pack(struct packed_git *, struct pack_window **, off_t\n extern void unuse_pack(struct pack_window **);\n extern struct packed_git *add_packed_git(const char *, int, int);\n extern const unsigned char *nth_packed_object_sha1(struct packed_git *, uint32_t);\n-extern off_t find_pack_entry_one(const unsigned char *, struct packed_git *);\n+extern off_t find_pack_entry_one(const unsigned char *, struct packed_git *, unsigned);\n extern void *unpack_entry(struct packed_git *, off_t, enum object_type *, unsigned long *);\n extern unsigned long unpack_object_header_gently(const unsigned char *buf, unsigned long len, enum object_type *type, unsigned long *sizep);\n extern unsigned long get_size_from_delta(struct packed_git *, struct pack_window **, off_t);\ndiff --git a/git.c b/git.c\nindex 29b55a1..c323479 100644\n--- a/git.c\n+++ b/git.c\n@@ -284,6 +284,7 @@ static void handle_internal_command(int argc, const char **argv, char **envp)\n \t\t{ \"show-branch\", cmd_show_branch, RUN_SETUP },\n \t\t{ \"show\", cmd_show, RUN_SETUP | USE_PAGER },\n \t\t{ \"stripspace\", cmd_stripspace },\n+\t\t{ \"super-index\", cmd_super_index, RUN_SETUP },\n \t\t{ \"symbolic-ref\", cmd_symbolic_ref, RUN_SETUP },\n \t\t{ \"tar-tree\", cmd_tar_tree },\n \t\t{ \"unpack-objects\", cmd_unpack_objects, RUN_SETUP },\ndiff --git a/pack-check.c b/pack-check.c\nindex 7475348..ec61592 100644\n--- a/pack-check.c\n+++ b/pack-check.c\n@@ -51,7 +51,7 @@ static int verify_packfile(struct packed_git *p,\n \t\tsha1 = nth_packed_object_sha1(p, i);\n \t\tif (!sha1)\n \t\t\tdie(\"internal error pack-check nth-packed-object\");\n-\t\toffset = find_pack_entry_one(sha1, p);\n+\t\toffset = find_pack_entry_one(sha1, p, 0);\n \t\tif (!offset)\n \t\t\tdie(\"internal error pack-check find-pack-entry-one\");\n \t\tdata = unpack_entry(p, offset, &type, &size);\n@@ -94,7 +94,7 @@ static void show_pack_info(struct packed_git *p)\n \t\tsha1 = nth_packed_object_sha1(p, i);\n \t\tif (!sha1)\n \t\t\tdie(\"internal error pack-check nth-packed-object\");\n-\t\toffset = find_pack_entry_one(sha1, p);\n+\t\toffset = find_pack_entry_one(sha1, p, 0);\n \t\tif (!offset)\n \t\t\tdie(\"internal error pack-check find-pack-entry-one\");\n \ndiff --git a/pack.h b/pack.h\nindex d667fb8..b660833 100644\n--- a/pack.h\n+++ b/pack.h\n@@ -43,6 +43,23 @@ struct pack_idx_header {\n };\n \n \n+/*\n+ * Super-pack index header\n+ *\n+ * This file points to multiple packfiles by name and provides a\n+ * hint to tell us if it is likely that a given packfile contains\n+ * a particular object.  This file is not an index file replacement,\n+ * it is only a performance optimization hint.\n+ */\n+#define PACK_SDX_SIGNATURE 0x50534458\t/* \"PSDX\" */\n+struct pack_sdx_header {\n+\tuint32_t sdx_signature;\n+\tuint32_t sdx_version;\n+\tuint16_t sdx_packs;\n+\tuint8_t  sdx_prefix;\n+\tuint8_t  _unused_padding;\n+};\n+\n extern int verify_pack(struct packed_git *, int);\n extern void fixup_pack_header_footer(int, unsigned char *, const char *, uint32_t);\n \ndiff --git a/sha1_file.c b/sha1_file.c\nindex a3637d7..d296b32 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -405,6 +405,15 @@ static char *find_sha1_file(const unsigned char *sha1, struct stat *st)\n \treturn NULL;\n }\n \n+struct super_index {\n+\tstruct pack_sdx_header *sdx_header;\n+\tvoid *sdx_data;\n+\tunsigned char *sdx_pack_names;\n+\tstruct packed_git **packs;\n+\tunsigned pack_cnt;\n+};\n+\n+static struct super_index *super_idx;\n static unsigned int pack_used_ctr;\n static unsigned int pack_mmap_calls;\n static unsigned int peak_pack_open_windows;\n@@ -831,6 +840,64 @@ void install_packed_git(struct packed_git *pack)\n \tpacked_git = pack;\n }\n \n+static int open_super_index(const char *path)\n+{\n+\tint fd = open(path, O_RDONLY);\n+\tstruct stat st;\n+\tsize_t sdx_size;\n+\tvoid *sdx_map;\n+\tstruct pack_sdx_header *hdr;\n+\tunsigned char *sdx_data;\n+\tunsigned pack_cnt;\n+\n+\tif (fd < 0)\n+\t\treturn -1;\n+\tif (fstat(fd, &st)) {\n+\t\tclose(fd);\n+\t\treturn -1;\n+\t}\n+\n+\tsdx_size = xsize_t(st.st_size);\n+\tif (sdx_size < 4 * 256 + 20) {\n+\t\tclose(fd);\n+\t\treturn error(\"super-index %s is too small\", path);\n+\t}\n+\tsdx_map = mmap(NULL, sdx_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tif (sdx_map == MAP_FAILED) {\n+\t\trelease_pack_memory(sdx_size, fd);\n+\t\tsdx_map = mmap(NULL, sdx_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\t\tif (sdx_map == MAP_FAILED) {\n+\t\t\tclose(fd);\n+\t\t\treturn -1;\n+\t\t}\n+\t}\n+\tclose(fd);\n+\n+\thdr = sdx_map;\n+\tif (hdr->sdx_signature != htonl(PACK_SDX_SIGNATURE)) {\n+\t\tmunmap(sdx_map, sdx_size);\n+\t\treturn error(\"super-index %s has incorrect signature\", path);\n+\t}\n+\tif (hdr->sdx_version != htonl(1)) {\n+\t\tmunmap(sdx_map, sdx_size);\n+\t\treturn error(\"super-index file %s is version %u\"\n+\t\t\t\t \" and is not supported by this binary\"\n+\t\t\t\t \" (try upgrading GIT to a newer version)\",\n+\t\t\t\t path, ntohl(hdr->sdx_version));\n+\t}\n+\n+\tpack_cnt = ntohs(hdr->sdx_packs);\n+\tsdx_data = (unsigned char*)(hdr + 1);\n+\n+\tsuper_idx = xmalloc(sizeof(*super_idx));\n+\tsuper_idx->sdx_header = hdr;\n+\tsuper_idx->sdx_pack_names = sdx_data;\n+\tsuper_idx->sdx_data = sdx_data + pack_cnt * 20;\n+\tsuper_idx->pack_cnt = pack_cnt;\n+\tsuper_idx->packs = xcalloc(pack_cnt, sizeof(*super_idx->packs));\n+\treturn 0;\n+}\n+\n static void prepare_packed_git_one(char *objdir, int local)\n {\n \tchar path[PATH_MAX];\n@@ -852,6 +919,12 @@ static void prepare_packed_git_one(char *objdir, int local)\n \t\tint namelen = strlen(de->d_name);\n \t\tstruct packed_git *p;\n \n+\t\tif (!super_idx && !strcmp(de->d_name, \"super-index.sdx\")) {\n+\t\t\tstrcpy(path + len, de->d_name);\n+\t\t\topen_super_index(path);\n+\t\t\tcontinue;\n+\t\t}\n+\n \t\tif (!has_extension(de->d_name, \".idx\"))\n \t\t\tcontinue;\n \n@@ -1260,7 +1333,7 @@ static off_t get_delta_base(struct packed_git *p,\n \t\t*curpos += used;\n \t} else if (type == OBJ_REF_DELTA) {\n \t\t/* The base entry _must_ be in the same pack */\n-\t\tbase_offset = find_pack_entry_one(base_info, p);\n+\t\tbase_offset = find_pack_entry_one(base_info, p, 0);\n \t\tif (!base_offset)\n \t\t\tdie(\"failed to find delta-pack base object %s\",\n \t\t\t\tsha1_to_hex(base_info));\n@@ -1362,7 +1435,7 @@ const char *packed_object_info_detail(struct packed_git *p,\n \t\t\tnext_sha1 = use_pack(p, &w_curs, curpos, NULL);\n \t\t\tif (*delta_chain_length == 0)\n \t\t\t\thashcpy(base_sha1, next_sha1);\n-\t\t\tobj_offset = find_pack_entry_one(next_sha1, p);\n+\t\t\tobj_offset = find_pack_entry_one(next_sha1, p, 0);\n \t\t\tbreak;\n \t\t}\n \t\t(*delta_chain_length)++;\n@@ -1633,11 +1706,12 @@ static off_t nth_packed_object_offset(const struct packed_git *p, uint32_t n)\n }\n \n off_t find_pack_entry_one(const unsigned char *sha1,\n-\t\t\t\t  struct packed_git *p)\n+\t\t\t\t  struct packed_git *p,\n+\t\t\t\t  unsigned shift)\n {\n \tconst uint32_t *level1_ofs = p->index_data;\n \tconst unsigned char *index = p->index_data;\n-\tunsigned hi, lo;\n+\tunsigned hi, lo, mi;\n \n \tif (!index) {\n \t\tif (open_pack_index(p))\n@@ -1652,9 +1726,12 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \tindex += 4 * 256;\n \thi = ntohl(level1_ofs[*sha1]);\n \tlo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));\n+\tif (shift)\n+\t\tmi = lo + (hi - lo) * (shift - 1) / 65535;\n+\telse\n+\t\tmi = (lo + hi) / 2;\n \n \tdo {\n-\t\tunsigned mi = (lo + hi) / 2;\n \t\tunsigned x = (p->index_version > 1) ? (mi * 20) : (mi * 24 + 4);\n \t\tint cmp = hashcmp(index + x, sha1);\n \t\tif (!cmp)\n@@ -1663,6 +1740,7 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \t\t\thi = mi;\n \t\telse\n \t\t\tlo = mi+1;\n+\t\tmi = (lo + hi) / 2;\n \t} while (lo < hi);\n \treturn 0;\n }\n@@ -1685,42 +1763,100 @@ static int matches_pack_name(struct packed_git *p, const char *ig)\n \treturn 1;\n }\n \n-static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e, const char **ignore_packed)\n+static int find_in_pack(struct packed_git *p, unsigned shift, const unsigned char *sha1, struct pack_entry *e, const char **ignore_packed)\n {\n-\tstruct packed_git *p;\n \toff_t offset;\n \n-\tprepare_packed_git();\n+\tif (ignore_packed) {\n+\t\tconst char **ig;\n+\t\tfor (ig = ignore_packed; *ig; ig++)\n+\t\t\tif (!matches_pack_name(p, *ig))\n+\t\t\t\tbreak;\n+\t\tif (*ig)\n+\t\t\treturn 0;\n+\t}\n \n-\tfor (p = packed_git; p; p = p->next) {\n-\t\tif (ignore_packed) {\n-\t\t\tconst char **ig;\n-\t\t\tfor (ig = ignore_packed; *ig; ig++)\n-\t\t\t\tif (!matches_pack_name(p, *ig))\n-\t\t\t\t\tbreak;\n-\t\t\tif (*ig)\n-\t\t\t\tcontinue;\n-\t\t}\n-\t\toffset = find_pack_entry_one(sha1, p);\n-\t\tif (offset) {\n-\t\t\t/*\n-\t\t\t * We are about to tell the caller where they can\n-\t\t\t * locate the requested object.  We better make\n-\t\t\t * sure the packfile is still here and can be\n-\t\t\t * accessed before supplying that answer, as\n-\t\t\t * it may have been deleted since the index\n-\t\t\t * was loaded!\n-\t\t\t */\n-\t\t\tif (p->pack_fd == -1 && open_packed_git(p)) {\n-\t\t\t\terror(\"packfile %s cannot be accessed\", p->pack_name);\n-\t\t\t\tcontinue;\n+\toffset = find_pack_entry_one(sha1, p, shift);\n+\tif (!offset)\n+\t\treturn 0;\n+\n+\t/*\n+\t * We are about to tell the caller where they can\n+\t * locate the requested object.  We better make\n+\t * sure the packfile is still here and can be\n+\t * accessed before supplying that answer, as\n+\t * it may have been deleted since the index\n+\t * was loaded!\n+\t */\n+\tif (p->pack_fd == -1 && open_packed_git(p)) {\n+\t\terror(\"packfile %s cannot be accessed\", p->pack_name);\n+\t\treturn 0;\n+\t}\n+\te->offset = offset;\n+\te->p = p;\n+\thashcpy(e->sha1, sha1);\n+\treturn 1;\n+}\n+\n+static int find_superindex_entry(const unsigned char *sha1, struct pack_entry *e, const char **ignore_packed)\n+{\n+\tconst uint32_t *level1_ofs = super_idx->sdx_data;\n+\tconst unsigned char *index = super_idx->sdx_data;\n+\tconst unsigned pfx_len = super_idx->sdx_header->sdx_prefix;\n+\tconst unsigned packs = super_idx->pack_cnt;\n+\tunsigned hi, lo;\n+\n+\tindex += 4 * 256;\n+\thi = ntohl(level1_ofs[*sha1]);\n+\tlo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));\n+\n+\tdo {\n+\t\tunsigned mi = (lo + hi) / 2;\n+\t\tunsigned x = mi * (pfx_len + packs);\n+\t\tint cmp = memcmp(index + x, sha1 + 1, pfx_len);\n+\t\tif (!cmp) {\n+\t\t\tindex += x + pfx_len;\n+\t\t\tfor (x = 0; x < packs; x++, index += 2) {\n+\t\t\t\tunsigned shift = (*index << 8) | index[1];\n+\t\t\t\tstruct packed_git *p;\n+\t\t\t\tif (!shift)\n+\t\t\t\t\tcontinue;\n+\t\t\t\tp = super_idx->packs[x];\n+\t\t\t\tif (!p) {\n+\t\t\t\t\tfor (p = packed_git; p; p = p->next) {\n+\t\t\t\t\t\tif (!hashcmp(p->sha1,\n+\t\t\t\t\t\t\tsuper_idx->sdx_pack_names + x * 20))\n+\t\t\t\t\t\t\tbreak;\n+\t\t\t\t\t}\n+\t\t\t\t\tif (!p)\n+\t\t\t\t\t\tp = MAP_FAILED;\n+\t\t\t\t\tsuper_idx->packs[x] = p;\n+\t\t\t\t}\n+\t\t\t\tif (p == MAP_FAILED)\n+\t\t\t\t\tcontinue;\n+\t\t\t\tif (find_in_pack(p, shift, sha1, e, ignore_packed))\n+\t\t\t\t\treturn 1;\n \t\t\t}\n-\t\t\te->offset = offset;\n-\t\t\te->p = p;\n-\t\t\thashcpy(e->sha1, sha1);\n-\t\t\treturn 1;\n+\t\t\treturn 0;\n \t\t}\n-\t}\n+\t\tif (cmp > 0)\n+\t\t\thi = mi;\n+\t\telse\n+\t\t\tlo = mi + 1;\n+\t} while (lo < hi);\n+\treturn 0;\n+}\n+\n+static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e, const char **ignore_packed)\n+{\n+\tstruct packed_git *p;\n+\n+\tprepare_packed_git();\n+\tif (super_idx && find_superindex_entry(sha1, e, ignore_packed))\n+\t\treturn 1;\n+\tfor (p = packed_git; p; p = p->next)\n+\t\tif (find_in_pack(p, 0, sha1, e, ignore_packed))\n+\t\t\treturn 1;\n \treturn 0;\n }\n \n@@ -1730,7 +1866,7 @@ struct packed_git *find_sha1_pack(const unsigned char *sha1,\n \tstruct packed_git *p;\n \n \tfor (p = packs; p; p = p->next) {\n-\t\tif (find_pack_entry_one(sha1, p))\n+\t\tif (find_pack_entry_one(sha1, p, 0))\n \t\t\treturn p;\n \t}\n \treturn NULL;\n-- \n1.5.2.838.g8a923\n"},{"id":"43574","messageId":"9e4733910705290905m66dd3081ubda9b92a707fc903@mail.gmail.com","threadId":"8349","inReplyTo":"20070529071622.GA8905@spearce.org","subject":"Re: [RFC] super indexes to span multiple packfiles","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-05-29T16:05:59Z","receivedAt":"2007-05-29T16:05:59Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"Object's are not accessed in random order with git. Once an object\nreference hits a pack file it is very likely that following references\nwill hit the same pack file. That's because you always find object\nSHA's by following the chains.\n\nSo first place to look for an object is the same place the previous\nobject was found. If it isn't there order the search of the pack files\nby creation data (just a heuristic). Make this list a circle and start\nthe search in the pack where the previous object was found. This can\nall be done with the existing indexes.\n\nI haven't been reading all of the messages on this subject, but is\nthis strategy enough to eliminate the need for a super index?\n\nIf you still need a super index, note that it may be good enough for\nit to only contain the SHA's for objects that are externally\nreferenced. This index would be small and simply point to the correct\npack file index to find the object in. You could add a list of\ndangling links to each packfile index to assist with building this\nsuper index.\n\nMy work with databases leads me to believe that figuring out how to\npack everything into a smaller space always beats efforts put into\nincrementally improving the indexing scheme. Packing into a smaller\nspace reduces the total IO needs and that's always a winner.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"43575","messageId":"alpine.LFD.0.99.0705291210130.11491@xanadu.home","threadId":"8349","inReplyTo":"9e4733910705290905m66dd3081ubda9b92a707fc903@mail.gmail.com","subject":"Re: [RFC] super indexes to span multiple packfiles","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-29T16:19:13Z","receivedAt":"2007-05-29T16:19:13Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 29 May 2007, Jon Smirl wrote:\n\n> Object's are not accessed in random order with git. Once an object\n> reference hits a pack file it is very likely that following references\n> will hit the same pack file. That's because you always find object\n> SHA's by following the chains.\n> \n> So first place to look for an object is the same place the previous\n> object was found. If it isn't there order the search of the pack files\n> by creation data (just a heuristic). Make this list a circle and start\n> the search in the pack where the previous object was found. This can\n> all be done with the existing indexes.\n> \n> I haven't been reading all of the messages on this subject, but is\n> this strategy enough to eliminate the need for a super index?\n\nI think it could.\n\nPersonally I'm not a big fan of the super index notion.  It needs extra \nmaintenance to keep in synch, and when it is not in synch it requires \nextra work at run time to fall back to traditional lookup.  And Shawn's \ntesting didn't provide significant performance gains either.\n\nBut a simple heuristic like the presumption that the next object is \nlikely to be in the same pack as the previous is the kind of thing that \ncould provide significant improvements with really little effort.\n\n\nNicolas\n"},{"id":"43577","messageId":"465C52D3.3010605@qumranet.com","threadId":"8349","inReplyTo":"9e4733910705290905m66dd3081ubda9b92a707fc903@mail.gmail.com","subject":"Re: [RFC] super indexes to span multiple packfiles","fromName":"Avi Kivity","fromEmail":"avi@qumranet.com","sentAt":"2007-05-29T16:20:35Z","receivedAt":"2007-05-29T16:20:35Z","isPatch":false,"sender":{"key":"avi@qumranet.com","avatar":null},"body":"Jon Smirl wrote:\n>\n> My work with databases leads me to believe that figuring out how to\n> pack everything into a smaller space always beats efforts put into\n> incrementally improving the indexing scheme. Packing into a smaller\n> space reduces the total IO needs and that's always a winner.\n>\n\nAnother way to achieve that is to place objects that are accessed \ntogether nearby, and issue a larger read so as to bring them into \ncache.  I imagine that placing commit objects and associated tree and \nblobs in history order should help here (but maybe git already does \nthat, I'm not familiar with the internals).\n\n-- \nerror compiling committee.c: too many arguments to function\n"},{"id":"43576","messageId":"alpine.LFD.0.99.0705291227010.11491@xanadu.home","threadId":"8349","inReplyTo":"465C52D3.3010605@qumranet.com","subject":"Re: [RFC] super indexes to span multiple packfiles","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-29T16:31:54Z","receivedAt":"2007-05-29T16:31:54Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 29 May 2007, Avi Kivity wrote:\n\n> Jon Smirl wrote:\n> > \n> > My work with databases leads me to believe that figuring out how to\n> > pack everything into a smaller space always beats efforts put into\n> > incrementally improving the indexing scheme. Packing into a smaller\n> > space reduces the total IO needs and that's always a winner.\n> > \n> \n> Another way to achieve that is to place objects that are accessed together\n> nearby, and issue a larger read so as to bring them into cache.  I imagine\n> that placing commit objects and associated tree and blobs in history order\n> should help here (but maybe git already does that, I'm not familiar with the\n> internals).\n\nGIT already does that indeed, except for commit objects which are all \ntogether for better performances on history traversal operations.\n\nAfter a fresh repack, the checkout of the latest revision should produce \na nearly perfect linear and contigous access into the early portion of \nthe same pack.  Things will get more random with access to objects \nfurther back in history of course, but those objects are less likely to \nbe accessed as often.\n\n\nNicolas\n"},{"id":"43579","messageId":"E393F294-9159-4824-8874-69FB836F4B59@adacore.com","threadId":"8349","inReplyTo":"20070529071622.GA8905@spearce.org","subject":"Re: [RFC] super indexes to span multiple packfiles","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2007-05-29T17:54:30Z","receivedAt":"2007-05-29T17:54:30Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"[resent, my email client doesn't like Shawn's name :( ]\nOn May 29, 2007, at 03:16, Shawn O. Pearce wrote:\n\n> In the single packfile case (everything repacked into one) this\n> is not faster; its actually slightly slower.  With a handful of\n> smaller recent packfiles (such as immediately after a git-fetch)\n> it breaks even with the stock code.  I haven't tested it yet with\n> a high number of packfiles (e.g. 20).  I suspect it won't gain us\n> a lot up there either...\n>\n> So in short this shouldn't be applied, because its not any faster,\n> and is sometimes slower.  But I'm tossing it out here for discussion.\n> I'm also not documenting the new super-index command line program,\n> because I don't think this should be applied.  ;-)\n\nA super-index should have a fan-out factor dependent on the number\nof entries in the index. So an index with 2^20 entries would have\n2^16 fan-outs. So there will be about 2^4 entries per fanout slot.\nEach slot only contains the next byte of the key, so in this case\nbit 16 through 23 (numbering bits starting at zero).\n\nThe format would look like:\n   * Header\n   * Fan-out table (approx 2 bits/object)\n   * Next key-byte table (1 byte/object)\n   * Object info (offset into packfile(s) and/or rest of object name)\n\nSo, after a single lookup to get to about the right entry, only\nan expected 16 single-byte comparisons are necessary to find the\nentry that is needed or return a \"entry doesn't exist\".\n\nBelow I repeat a previous suggestion for a new pack file index.\nI'm happy to implement this, although it seems that there are\nso many pending index/pack file format changes that this may\nbe premature. If the pack file itself will have the full SHA-1,\nthe\n\n(snipped from <http://article.gmane.org/gmane.comp.version- \ncontrol.git/43545>)\n\nMultiple Pack Index\n\nThe linear search through packs is very inefficient\nwith large numbers of packs. Having packs much larger\nthan a GB is also problematic, due to this as repacking\nand otherwise modifying packs gets very expensive.\n\nAnother issue is that binary search requires many\nsemi-random accesses spread over the index. Finally,\nmost of the information actually read consists of\nSHA1's that are never needed.\n\nThis proposed pack index format does not focus on reducing\nused disk space, but instead aims to reduce the number\nof blocks that needs to be read to perform lookups.\nThis is done using three techniques:\n   1) scale the number of fan-out bins with the number\n      of objects in the index, keeping the expected\n      number of objects in each bin constant\n   2) take advantage of 1) by only storing a few bits\n      following the common prefix in the main lookup table\n      as a discriminant. Store the rest of the SHA1 and\n      the pack offest in a separate, parallel, object table.\n   3) Instead of repeating the variable-length common prefix\n      and the discriminant, use the space for the prefix\n      for a pack identifier and omit the discriminant altogether.\n\nFor a repository with N objects and highest PACK_NR P,\nthe total space used for the index is bounded by\n24 * (N + P) bytes, if N is at least 512 and N >= 512 * P.\n\nLimits:\n    - Maximum number of packs: 2^27\n    - Maximum number of objects: 2^40\n    - Maximum repository size: 2^48 bytes\n\n<PACK_INDEX>\n    :   <IDX_PACK_LIST>\n        <IDX_FANOUT_BITS>\n        <IDX_FANOUT_TABLE>\n        <IDX_LOOKUP_TABLE>\n        <IDX_OBJECT_TABLE>\n        <IDX_CHECKSUM>\n    ;\n\n<IDX_PACK_LIST>\n    :   <IDX_PACK_LIST_ENTRIES>\n        <ZERO_32> <IDX_PACK_LIST_CHECKSUM>\n    ;\n<IDX_PACK_LIST_ENTRIES>\n    # List of packs sorted by ascending PACK_ID\n    :  ( <IDX_PACK_NR> <PACK_ID> ) *\n    ;\n\n<PACK_ID>\n    # 20-byte binary representation of the 40 hex-digit\n    # value PACK_ID_HEX, such that pack-${PACK_ID_HEX}.pack\n    # is the name of the pack file\n    ;\n\n<IDX_PACK_NR>\n    # 32-bit unsigned integer in network order, with the same\n    # value as the preceding <IDX_PACK_NR> (or zero for the\n    # first entry), increased by the size of the pack file in\n    # bytes, divided by 2^32 and rounded up.\n    ;\n\n<ZERO_32>\n    # 32-bit zero\n    ;\n\n<IDX_PACK_LIST_CHECKSUM>\n    # 20-byte SHA1 of <IDX_PACK_LIST_ENTRIES>\n    ;\n\n<IDX_FANOUT_BITS>\n    # 1 byte with the smallest value N between 8 and 35,\n    # such that 2^(N - 8) greater than or equal to the\n    # largest IDX_PACK_NR in the IDX_PACK_LIST, and such that\n    # 2^(N+5) is greater than or equal to the total number\n    # of objects in all packs.\n    ;\n\n<IDX_FANOUT_TABLE>\n    # Table of 2^${IDX_FANOUT_BITS} entries\n    :   ( <IDX_PARTIAL_COUNT> ) *\n    ;\n\n<IDX_PARTIAL_COUNT>\n    # 40 bit, network byte order, binary integer of the count of\n    # objects in the pack file with the high IDX_FANOUT_BITS bits of\n    # the object ID less than or equal to the index of the count,\n    # starting from zero.\n    ;\n\n<IDX_LOOKUP_TABLE>\n    # One 8-bit key per object indexed by the pack\n    :   ( <IDX_LOOKUP_KEY> ) *\n    ;\n\n<IDX_LOOKUP_KEY>\n    # Bits IDX_FANOUT_BITS through IDX_FANOUT_BITS + 7 of the\n    # object ID.\n    ;\n\n<IDX_OBJECT_ENTRY>\n    # The total width of each entry is 22 bytes\n    :   ( <IDX_PACK_REF> <IDX_OBJECT_ID> <IDX_OFFSET> ) *\n    ;\n\n<IDX_PACK_REF>\n    # A IDX_FANOUT_BITS - 8 bit wide integer value, equal to\n    # PACK_NR of pack preceding the one containing the object\n    # (or zero, if object is in first pack) increased with the\n    # pack offset divided by 2^32.\n    ;\n\n<IDX_OBJECT_ID>\n    # Bits IDX_FANOUT_BITS + 8 .. 159 of the object ID\n    ;\n\n<IDX_OFFSET>\n    # 32-bits offset in network byte order\n    ;\n"},{"id":"43626","messageId":"465D4693.5070006@qumranet.com","threadId":"8349","inReplyTo":"alpine.LFD.0.99.0705291227010.11491@xanadu.home","subject":"Re: [RFC] super indexes to span multiple packfiles","fromName":"Avi Kivity","fromEmail":"avi@qumranet.com","sentAt":"2007-05-30T09:40:35Z","receivedAt":"2007-05-30T09:40:35Z","isPatch":false,"sender":{"key":"avi@qumranet.com","avatar":null},"body":"Nicolas Pitre wrote:\n>>\n>> Another way to achieve that is to place objects that are accessed together\n>> nearby, and issue a larger read so as to bring them into cache.  I imagine\n>> that placing commit objects and associated tree and blobs in history order\n>> should help here (but maybe git already does that, I'm not familiar with the\n>> internals).\n>>     \n>\n> GIT already does that indeed, except for commit objects which are all \n> together for better performances on history traversal operations.\n>\n> After a fresh repack, the checkout of the latest revision should produce \n> a nearly perfect linear and contigous access into the early portion of \n> the same pack.  Things will get more random with access to objects \n> further back in history of course, but those objects are less likely to \n> be accessed as often.\n>\n>   \n\nThanks.  Actually I should have deduced this from the speed of 'git log' ;-)\n\n-- \nerror compiling committee.c: too many arguments to function\n"}]}