{"thread":{"id":"7578","subject":"support for large packs and 64-bit offsets","startedAt":"2007-04-09T05:06:27Z","lastAt":"2007-04-09T20:18:05Z","messageCount":24,"participants":["Nicolas Pitre","Junio C Hamano","Linus Torvalds","Shawn O. Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"38906","messageId":"11760951973172-git-send-email-nico@cam.org","threadId":"7578","inReplyTo":null,"subject":"support for large packs and 64-bit offsets","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-09T05:06:27Z","receivedAt":"2007-04-09T05:06:27Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This patch series adds support for large packs to GIT.  It creates a new\nindex format to accommodate both larger offsets and to store a checksum\nfor each raw object in a pack.  More details is provided in each patch\ncommit message.\n\nThis is not a replacement for the pack size limiting feature.  I think that\nGIT should support both: large packs and split packs.\n\nNicolas\n"},{"id":"38911","messageId":"11760951973319-git-send-email-nico@cam.org","threadId":"7578","inReplyTo":"11760951973172-git-send-email-nico@cam.org","subject":"[PATCH 01/10] get rid of num_packed_objects()","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-09T05:06:28Z","receivedAt":"2007-04-09T05:06:28Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"The coming index format change doesn't allow for the number of objects\nto be determined from the size of the index file directly.  Instead, Let's\ninitialize a field in the packed_git structure with the object count when\nthe index is validated since the count is always known at that point.\n\nWhile at it let's reorder some struct packed_git fields to avoid padding\ndue to needed 64-bit alignment for some of them.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n builtin-count-objects.c |    2 +-\n builtin-fsck.c          |    2 +-\n builtin-pack-objects.c  |    4 ++--\n cache.h                 |    8 ++++----\n pack-check.c            |    4 ++--\n sha1_file.c             |   17 ++++++-----------\n sha1_name.c             |    2 +-\n 7 files changed, 17 insertions(+), 22 deletions(-)\n\ndiff --git a/builtin-count-objects.c b/builtin-count-objects.c\nindex 6263d8a..ff90ebd 100644\n--- a/builtin-count-objects.c\n+++ b/builtin-count-objects.c\n@@ -111,7 +111,7 @@ int cmd_count_objects(int ac, const char **av, const char *prefix)\n \t\tfor (p = packed_git; p; p = p->next) {\n \t\t\tif (!p->pack_local)\n \t\t\t\tcontinue;\n-\t\t\tpacked += num_packed_objects(p);\n+\t\t\tpacked += p->num_objects;\n \t\t\tnum_pack++;\n \t\t}\n \t\tprintf(\"count: %lu\\n\", loose);\ndiff --git a/builtin-fsck.c b/builtin-fsck.c\nindex 4d8b66c..44a02d3 100644\n--- a/builtin-fsck.c\n+++ b/builtin-fsck.c\n@@ -653,7 +653,7 @@ int cmd_fsck(int argc, char **argv, const char *prefix)\n \t\t\tverify_pack(p, 0);\n \n \t\tfor (p = packed_git; p; p = p->next) {\n-\t\t\tuint32_t i, num = num_packed_objects(p);\n+\t\t\tuint32_t i, num = p->num_objects;\n \t\t\tfor (i = 0; i < num; i++)\n \t\t\t\tfsck_sha1(nth_packed_object_sha1(p, i));\n \t\t}\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 45ac3e4..6bff17b 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -164,7 +164,7 @@ static int cmp_offset(const void *a_, const void *b_)\n static void prepare_pack_revindex(struct pack_revindex *rix)\n {\n \tstruct packed_git *p = rix->p;\n-\tint num_ent = num_packed_objects(p);\n+\tint num_ent = p->num_objects;\n \tint i;\n \tconst char *index = p->index_data;\n \n@@ -198,7 +198,7 @@ static struct revindex_entry * find_packed_object(struct packed_git *p,\n \t\tprepare_pack_revindex(rix);\n \trevindex = rix->revindex;\n \tlo = 0;\n-\thi = num_packed_objects(p) + 1;\n+\thi = p->num_objects + 1;\n \tdo {\n \t\tint mi = (lo + hi) / 2;\n \t\tif (revindex[mi].offset == ofs) {\ndiff --git a/cache.h b/cache.h\nindex c15daa8..73d8e63 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -378,11 +378,12 @@ struct pack_window {\n extern struct packed_git {\n \tstruct packed_git *next;\n \tstruct pack_window *windows;\n-\tconst void *index_data;\n-\toff_t index_size;\n \toff_t pack_size;\n-\ttime_t mtime;\n+\tconst void *index_data;\n+\tsize_t index_size;\n+\tuint32_t num_objects;\n \tint index_version;\n+\ttime_t mtime;\n \tint pack_fd;\n \tint pack_local;\n \tunsigned char sha1[20];\n@@ -433,7 +434,6 @@ extern void pack_report(void);\n extern unsigned char* use_pack(struct packed_git *, struct pack_window **, off_t, unsigned int *);\n extern void unuse_pack(struct pack_window **);\n extern struct packed_git *add_packed_git(const char *, int, int);\n-extern uint32_t num_packed_objects(const struct packed_git *p);\n extern const unsigned char *nth_packed_object_sha1(const struct packed_git *, uint32_t);\n extern off_t find_pack_entry_one(const unsigned char *, struct packed_git *);\n extern void *unpack_entry(struct packed_git *, off_t, enum object_type *, unsigned long *);\ndiff --git a/pack-check.c b/pack-check.c\nindex f58083d..d04536b 100644\n--- a/pack-check.c\n+++ b/pack-check.c\n@@ -40,7 +40,7 @@ static int verify_packfile(struct packed_git *p,\n \t * have verified that nr_objects matches between idx and pack,\n \t * we do not do scan-streaming check on the pack file.\n \t */\n-\tnr_objects = num_packed_objects(p);\n+\tnr_objects = p->num_objects;\n \tfor (i = 0, err = 0; i < nr_objects; i++) {\n \t\tconst unsigned char *sha1;\n \t\tvoid *data;\n@@ -79,7 +79,7 @@ static void show_pack_info(struct packed_git *p)\n {\n \tuint32_t nr_objects, i, chain_histogram[MAX_CHAIN];\n \n-\tnr_objects = num_packed_objects(p);\n+\tnr_objects = p->num_objects;\n \tmemset(chain_histogram, 0, sizeof(chain_histogram));\n \n \tfor (i = 0; i < nr_objects; i++) {\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 4304fe9..d9ca69a 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -494,6 +494,7 @@ static int check_packed_git_idx(const char *path,  struct packed_git *p)\n \tp->index_version = 1;\n \tp->index_data = idx_map;\n \tp->index_size = idx_size;\n+\tp->num_objects = nr;\n \treturn 0;\n }\n \n@@ -605,11 +606,11 @@ static int open_packed_git_1(struct packed_git *p)\n \t\t\tp->pack_name, ntohl(hdr.hdr_version));\n \n \t/* Verify the pack matches its index. */\n-\tif (num_packed_objects(p) != ntohl(hdr.hdr_entries))\n+\tif (p->num_objects != ntohl(hdr.hdr_entries))\n \t\treturn error(\"packfile %s claims to have %u objects\"\n-\t\t\t\" while index size indicates %u objects\",\n-\t\t\tp->pack_name, ntohl(hdr.hdr_entries),\n-\t\t\tnum_packed_objects(p));\n+\t\t\t     \" while index indicates %u objects\",\n+\t\t\t     p->pack_name, ntohl(hdr.hdr_entries),\n+\t\t\t     p->num_objects);\n \tif (lseek(p->pack_fd, p->pack_size - sizeof(sha1), SEEK_SET) == -1)\n \t\treturn error(\"end of packfile %s is unavailable\", p->pack_name);\n \tif (read_in_full(p->pack_fd, sha1, sizeof(sha1)) != sizeof(sha1))\n@@ -1526,18 +1527,12 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n \treturn data;\n }\n \n-uint32_t num_packed_objects(const struct packed_git *p)\n-{\n-\t/* See check_packed_git_idx() */\n-\treturn (uint32_t)((p->index_size - 20 - 20 - 4*256) / 24);\n-}\n-\n const unsigned char *nth_packed_object_sha1(const struct packed_git *p,\n \t\t\t\t\t    uint32_t n)\n {\n \tconst unsigned char *index = p->index_data;\n \tindex += 4 * 256;\n-\tif (num_packed_objects(p) <= n)\n+\tif (n >= p->num_objects)\n \t\treturn NULL;\n \treturn index + 24 * n + 4;\n }\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 267ea3f..b0b12bb 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -76,7 +76,7 @@ static int find_short_packed_object(int len, const unsigned char *match, unsigne\n \n \tprepare_packed_git();\n \tfor (p = packed_git; p && found < 2; p = p->next) {\n-\t\tuint32_t num = num_packed_objects(p);\n+\t\tuint32_t num = p->num_objects;\n \t\tuint32_t first = 0, last = num;\n \t\twhile (first < last) {\n \t\t\tuint32_t mid = (first + last) / 2;\n-- \n1.5.1.696.g6d352-dirty\n"},{"id":"38915","messageId":"11760951993458-git-send-email-nico@cam.org","threadId":"7578","inReplyTo":"11760951973319-git-send-email-nico@cam.org","subject":"[PATCH 02/10] make overflow test on delta base offset work regardless of variable size","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-09T05:06:29Z","receivedAt":"2007-04-09T05:06:29Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This patch introduces the MSB() macro to obtain the desired number of\nmost significant bits from a given variable independently of the variable\ntype.\n\nIt is then used to better implement the overflow test on the OBJ_OFS_DELTA\nbase offset variable with the property of always working correctly\nregardless of the type/size of that variable.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n builtin-pack-objects.c   |    2 +-\n builtin-unpack-objects.c |    2 +-\n git-compat-util.h        |    8 ++++++++\n index-pack.c             |    2 +-\n sha1_file.c              |    2 +-\n 5 files changed, 12 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 6bff17b..ee607a0 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -1014,7 +1014,7 @@ static void check_object(struct object_entry *entry)\n \t\t\t\tofs = c & 127;\n \t\t\t\twhile (c & 128) {\n \t\t\t\t\tofs += 1;\n-\t\t\t\t\tif (!ofs || ofs & ~(~0UL >> 7))\n+\t\t\t\t\tif (!ofs || MSB(ofs, 7))\n \t\t\t\t\t\tdie(\"delta base offset overflow in pack for %s\",\n \t\t\t\t\t\t    sha1_to_hex(entry->sha1));\n \t\t\t\t\tc = buf[used_0++];\ndiff --git a/builtin-unpack-objects.c b/builtin-unpack-objects.c\nindex 3956c56..63f7db6 100644\n--- a/builtin-unpack-objects.c\n+++ b/builtin-unpack-objects.c\n@@ -209,7 +209,7 @@ static void unpack_delta_entry(enum object_type type, unsigned long delta_size,\n \t\tbase_offset = c & 127;\n \t\twhile (c & 128) {\n \t\t\tbase_offset += 1;\n-\t\t\tif (!base_offset || base_offset & ~(~0UL >> 7))\n+\t\t\tif (!base_offset || MSB(base_offset, 7))\n \t\t\t\tdie(\"offset value overflow for delta base object\");\n \t\t\tpack = fill(1);\n \t\t\tc = *pack;\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 139fc19..bcfcb35 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -13,6 +13,14 @@\n \n #define ARRAY_SIZE(x) (sizeof(x)/sizeof(x[0]))\n \n+#ifdef __GNUC__\n+#define TYPEOF(x) (__typeof__(x))\n+#else\n+#define TYPEOF(x)\n+#endif\n+\n+#define MSB(x, bits) ((x) & TYPEOF(x)(~0ULL << (sizeof(x) * 8 - (bits))))\n+\n #if !defined(__APPLE__) && !defined(__FreeBSD__)\n #define _XOPEN_SOURCE 600 /* glibc2 and AIX 5.3L need 500, OpenBSD needs 600 for S_ISLNK() */\n #define _XOPEN_SOURCE_EXTENDED 1 /* AIX 5.3L needs this */\ndiff --git a/index-pack.c b/index-pack.c\nindex 3c768fb..0e54aa6 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -249,7 +249,7 @@ static void *unpack_raw_entry(struct object_entry *obj, union delta_base *delta_\n \t\tbase_offset = c & 127;\n \t\twhile (c & 128) {\n \t\t\tbase_offset += 1;\n-\t\t\tif (!base_offset || base_offset & ~(~0UL >> 7))\n+\t\t\tif (!base_offset || MSB(base_offset, 7))\n \t\t\t\tbad_object(obj->offset, \"offset value overflow for delta base object\");\n \t\t\tp = fill(1);\n \t\t\tc = *p;\ndiff --git a/sha1_file.c b/sha1_file.c\nindex d9ca69a..ebdd497 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1150,7 +1150,7 @@ static off_t get_delta_base(struct packed_git *p,\n \t\tbase_offset = c & 127;\n \t\twhile (c & 128) {\n \t\t\tbase_offset += 1;\n-\t\t\tif (!base_offset || base_offset & ~(~0UL >> 7))\n+\t\t\tif (!base_offset || MSB(base_offset, 7))\n \t\t\t\tdie(\"offset value overflow for delta base object\");\n \t\t\tc = base_info[used++];\n \t\t\tbase_offset = (base_offset << 7) + (c & 127);\n-- \n1.5.1.696.g6d352-dirty\n"},{"id":"38914","messageId":"11760951993225-git-send-email-nico@cam.org","threadId":"7578","inReplyTo":"11760951993458-git-send-email-nico@cam.org","subject":"[PATCH 03/10] add overflow tests on pack offset variables","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-09T05:06:30Z","receivedAt":"2007-04-09T05:06:30Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Change a few size and offset variables to more appropriate type, then\nadd overflow tests on those offsets.  This prevents any bad data to be\ngenerated/processed if off_t happens to not be large enough to handle\nsome big packs.\n\nBetter be safe than sorry.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n builtin-pack-objects.c   |   19 +++++++++++++------\n builtin-unpack-objects.c |   17 +++++++++++------\n index-pack.c             |   14 ++++++++++----\n 3 files changed, 34 insertions(+), 16 deletions(-)\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex ee607a0..d0be879 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -369,7 +369,7 @@ static int revalidate_loose_object(struct object_entry *entry,\n \treturn check_loose_inflate(map, mapsize, size);\n }\n \n-static off_t write_object(struct sha1file *f,\n+static unsigned long write_object(struct sha1file *f,\n \t\t\t\t  struct object_entry *entry)\n {\n \tunsigned long size;\n@@ -503,16 +503,23 @@ static off_t write_one(struct sha1file *f,\n \t\t\t       struct object_entry *e,\n \t\t\t       off_t offset)\n {\n+\tunsigned long size;\n+\n+\t/* offset is non zero if object is written already. */\n \tif (e->offset || e->preferred_base)\n-\t\t/* offset starts from header size and cannot be zero\n-\t\t * if it is written already.\n-\t\t */\n \t\treturn offset;\n-\t/* if we are deltified, write out its base object first. */\n+\n+\t/* if we are deltified, write out base object first. */\n \tif (e->delta)\n \t\toffset = write_one(f, e->delta, offset);\n+\n \te->offset = offset;\n-\treturn offset + write_object(f, e);\n+\tsize = write_object(f, e);\n+\n+\t/* make sure off_t is sufficiently large not to wrap */\n+\tif (offset > offset + size)\n+\t\tdie(\"pack too large for current definition of off_t\");\n+\treturn offset + size;\n }\n \n static void write_pack_file(void)\ndiff --git a/builtin-unpack-objects.c b/builtin-unpack-objects.c\nindex 63f7db6..f821906 100644\n--- a/builtin-unpack-objects.c\n+++ b/builtin-unpack-objects.c\n@@ -13,7 +13,8 @@ static const char unpack_usage[] = \"git-unpack-objects [-n] [-q] [-r] < pack-fil\n \n /* We always read in 4kB chunks. */\n static unsigned char buffer[4096];\n-static unsigned long offset, len, consumed_bytes;\n+static unsigned int offset, len;\n+static off_t consumed_bytes;\n static SHA_CTX ctx;\n \n /*\n@@ -49,6 +50,10 @@ static void use(int bytes)\n \t\tdie(\"used more bytes than were available\");\n \tlen -= bytes;\n \toffset += bytes;\n+\n+\t/* make sure off_t is sufficiently large not to wrap */\n+\tif (consumed_bytes > consumed_bytes + bytes)\n+\t\tdie(\"pack too large for current definition of off_t\");\n \tconsumed_bytes += bytes;\n }\n \n@@ -88,17 +93,17 @@ static void *get_data(unsigned long size)\n \n struct delta_info {\n \tunsigned char base_sha1[20];\n-\tunsigned long base_offset;\n+\tunsigned nr;\n+\toff_t base_offset;\n \tunsigned long size;\n \tvoid *delta;\n-\tunsigned nr;\n \tstruct delta_info *next;\n };\n \n static struct delta_info *delta_list;\n \n static void add_delta_to_list(unsigned nr, unsigned const char *base_sha1,\n-\t\t\t      unsigned long base_offset,\n+\t\t\t      off_t base_offset,\n \t\t\t      void *delta, unsigned long size)\n {\n \tstruct delta_info *info = xmalloc(sizeof(*info));\n@@ -113,7 +118,7 @@ static void add_delta_to_list(unsigned nr, unsigned const char *base_sha1,\n }\n \n struct obj_info {\n-\tunsigned long offset;\n+\toff_t offset;\n \tunsigned char sha1[20];\n };\n \n@@ -200,7 +205,7 @@ static void unpack_delta_entry(enum object_type type, unsigned long delta_size,\n \t} else {\n \t\tunsigned base_found = 0;\n \t\tunsigned char *pack, c;\n-\t\tunsigned long base_offset;\n+\t\toff_t base_offset;\n \t\tunsigned lo, mid, hi;\n \n \t\tpack = fill(1);\ndiff --git a/index-pack.c b/index-pack.c\nindex 0e54aa6..66fb0bc 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -12,7 +12,7 @@ static const char index_pack_usage[] =\n \n struct object_entry\n {\n-\tunsigned long offset;\n+\toff_t offset;\n \tunsigned long size;\n \tunsigned int hdr_size;\n \tenum object_type type;\n@@ -22,7 +22,7 @@ struct object_entry\n \n union delta_base {\n \tunsigned char sha1[20];\n-\tunsigned long offset;\n+\toff_t offset;\n };\n \n /*\n@@ -83,7 +83,8 @@ static unsigned display_progress(unsigned n, unsigned total, unsigned last_pc)\n \n /* We always read in 4kB chunks. */\n static unsigned char input_buffer[4096];\n-static unsigned long input_offset, input_len, consumed_bytes;\n+static unsigned int input_offset, input_len;\n+static off_t consumed_bytes;\n static SHA_CTX input_ctx;\n static int input_fd, output_fd, pack_fd;\n \n@@ -129,6 +130,10 @@ static void use(int bytes)\n \t\tdie(\"used more bytes than were available\");\n \tinput_len -= bytes;\n \tinput_offset += bytes;\n+\n+\t/* make sure off_t is sufficiently large not to wrap */\n+\tif (consumed_bytes > consumed_bytes + bytes)\n+\t\tdie(\"pack too large for current definition of off_t\");\n \tconsumed_bytes += bytes;\n }\n \n@@ -216,7 +221,8 @@ static void *unpack_entry_data(unsigned long offset, unsigned long size)\n static void *unpack_raw_entry(struct object_entry *obj, union delta_base *delta_base)\n {\n \tunsigned char *p, c;\n-\tunsigned long size, base_offset;\n+\tunsigned long size;\n+\toff_t base_offset;\n \tunsigned shift;\n \n \tobj->offset = consumed_bytes;\n-- \n1.5.1.696.g6d352-dirty\n"},{"id":"38907","messageId":"11760951993409-git-send-email-nico@cam.org","threadId":"7578","inReplyTo":"11760951993225-git-send-email-nico@cam.org","subject":"[PATCH 04/10] compute a CRC32 for each object as stored in a pack","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-09T05:06:31Z","receivedAt":"2007-04-09T05:06:31Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"The most important optimization for performance when repacking is the\nability to reuse data from a previous pack as is and bypass any delta\nor even SHA1 computation by simply copying the raw data from one pack\nto another directly.\n\nThe problem with  this is that any data corruption within a copied object\nwould go unnoticed and the new (repacked) pack would be self-consistent\nwith its own checksum despite containing a corrupted object.  This is a\nreal issue that already happened at least once in the past.\n\nIn some attempt to prevent this, we validate the copied data by inflating\nit and making sure no error is signaled by zlib.  But this is still not\nperfect as a significant portion of a pack content is made of object\nheaders and references to delta base objects which are not deflated and\ntherefore not validated when repacking actually making the pack data reuse\nstill not as safe as it could be.\n\nOf course a full SHA1 validation could be performed, but that implies\nfull data inflating and delta replaying which is extremely costly, which\ncost the data reuse optimization was designed to avoid in the first place.\n\nSo the best solution to this is simply to store a CRC32 of the raw pack\ndata for each object in the pack index.  This way any object in a pack can\nbe validated before being copied as is in another pack, including header\nand any other non deflated data.\n\nWhy CRC32 instead of a faster checksum like Adler32?  Quoting Wikipedia:\n\n   Jonathan Stone discovered in 2001 that Adler-32 has a weakness for very\n   short messages. He wrote \"Briefly, the problem is that, for very short\n   packets, Adler32 is guaranteed to give poor coverage of the available\n   bits. Don't take my word for it, ask Mark Adler. :-)\" The problem is\n   that sum A does not wrap for short messages. The maximum value of A for\n   a 128-byte message is 32640, which is below the value 65521 used by the\n   modulo operation. An extended explanation can be found in RFC 3309,\n   which mandates the use of CRC32 instead of Adler-32 for SCTP, the\n   Stream Control Transmission Protocol.\n\nIn the context of a GIT pack, we have lots of small objects, especially\ndeltas, which are likely to be quite small and in a size range for which\nAdler32 is dimed not to be sufficient.  Another advantage of CRC32 is the\npossibility for recovery from certain types of small corruptions like\nsingle bit errors which are the most probable type of corruptions.\n\nOK what this patch does is to compute the CRC32 of each object written to\na pack within pack-objects.  It is not written to the index yet and it is\nobviously not validated when reusing pack data yet either.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n builtin-pack-objects.c |    6 ++++++\n csum-file.c            |   14 ++++++++++++++\n csum-file.h            |    4 ++++\n 3 files changed, 24 insertions(+), 0 deletions(-)\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex d0be879..03e36f0 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -44,6 +44,7 @@ struct object_entry {\n \t\t\t\t * be used as the base objectto delta huge\n \t\t\t\t * objects against.\n \t\t\t\t */\n+\tuint32_t crc32;\t\t/* crc of raw pack data for this object */\n };\n \n /*\n@@ -381,6 +382,9 @@ static unsigned long write_object(struct sha1file *f,\n \tenum object_type obj_type;\n \tint to_reuse = 0;\n \n+\tif (!pack_to_stdout)\n+\t\tcrc32_begin(f);\n+\n \tobj_type = entry->type;\n \tif (! entry->in_pack)\n \t\tto_reuse = 0;\t/* can't reuse what we don't have */\n@@ -496,6 +500,8 @@ static unsigned long write_object(struct sha1file *f,\n \tif (entry->delta)\n \t\twritten_delta++;\n \twritten++;\n+\tif (!pack_to_stdout)\n+\t\tentry->crc32 = crc32_end(f);\n \treturn hdrlen + datalen;\n }\n \ndiff --git a/csum-file.c b/csum-file.c\nindex b7174c6..7c806ad 100644\n--- a/csum-file.c\n+++ b/csum-file.c\n@@ -49,6 +49,8 @@ int sha1close(struct sha1file *f, unsigned char *result, int update)\n \n int sha1write(struct sha1file *f, void *buf, unsigned int count)\n {\n+\tif (f->do_crc)\n+\t\tf->crc32 = crc32(f->crc32, buf, count);\n \twhile (count) {\n \t\tunsigned offset = f->offset;\n \t\tunsigned left = sizeof(f->buffer) - offset;\n@@ -91,6 +93,7 @@ struct sha1file *sha1create(const char *fmt, ...)\n \tf->fd = fd;\n \tf->error = 0;\n \tf->offset = 0;\n+\tf->do_crc = 0;\n \tSHA1_Init(&f->ctx);\n \treturn f;\n }\n@@ -111,6 +114,7 @@ struct sha1file *sha1fd(int fd, const char *name)\n \tf->fd = fd;\n \tf->error = 0;\n \tf->offset = 0;\n+\tf->do_crc = 0;\n \tSHA1_Init(&f->ctx);\n \treturn f;\n }\n@@ -143,4 +147,14 @@ int sha1write_compressed(struct sha1file *f, void *in, unsigned int size)\n \treturn size;\n }\n \n+void crc32_begin(struct sha1file *f)\n+{\n+\tf->crc32 = crc32(0, Z_NULL, 0);\n+\tf->do_crc = 1;\n+}\n \n+uint32_t crc32_end(struct sha1file *f)\n+{\n+\tf->do_crc = 0;\n+\treturn f->crc32;\n+}\ndiff --git a/csum-file.h b/csum-file.h\nindex 3ad1a99..7e13391 100644\n--- a/csum-file.h\n+++ b/csum-file.h\n@@ -7,6 +7,8 @@ struct sha1file {\n \tunsigned int offset, namelen;\n \tSHA_CTX ctx;\n \tchar name[PATH_MAX];\n+\tint do_crc;\n+\tuint32_t crc32;\n \tunsigned char buffer[8192];\n };\n \n@@ -15,5 +17,7 @@ extern struct sha1file *sha1create(const char *fmt, ...) __attribute__((format (\n extern int sha1close(struct sha1file *, unsigned char *, int);\n extern int sha1write(struct sha1file *, void *, unsigned int);\n extern int sha1write_compressed(struct sha1file *, void *, unsigned int);\n+extern void crc32_begin(struct sha1file *);\n+extern uint32_t crc32_end(struct sha1file *);\n \n #endif\n-- \n1.5.1.696.g6d352-dirty\n"},{"id":"38916","messageId":"11760952002687-git-send-email-nico@cam.org","threadId":"7578","inReplyTo":"11760951993409-git-send-email-nico@cam.org","subject":"[PATCH 05/10] compute object CRC32 with index-pack","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-09T05:06:32Z","receivedAt":"2007-04-09T05:06:32Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Same as previous patch but for index-pack.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n index-pack.c |   16 +++++++++++++---\n 1 files changed, 13 insertions(+), 3 deletions(-)\n\ndiff --git a/index-pack.c b/index-pack.c\nindex 66fb0bc..d33f723 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -15,6 +15,7 @@ struct object_entry\n \toff_t offset;\n \tunsigned long size;\n \tunsigned int hdr_size;\n+\tuint32_t crc32;\n \tenum object_type type;\n \tenum object_type real_type;\n \tunsigned char sha1[20];\n@@ -86,6 +87,7 @@ static unsigned char input_buffer[4096];\n static unsigned int input_offset, input_len;\n static off_t consumed_bytes;\n static SHA_CTX input_ctx;\n+static uint32_t input_crc32;\n static int input_fd, output_fd, pack_fd;\n \n /* Discard current buffer used content. */\n@@ -128,6 +130,7 @@ static void use(int bytes)\n {\n \tif (bytes > input_len)\n \t\tdie(\"used more bytes than were available\");\n+\tinput_crc32 = crc32(input_crc32, input_buffer + input_offset, bytes);\n \tinput_len -= bytes;\n \tinput_offset += bytes;\n \n@@ -224,8 +227,10 @@ static void *unpack_raw_entry(struct object_entry *obj, union delta_base *delta_\n \tunsigned long size;\n \toff_t base_offset;\n \tunsigned shift;\n+\tvoid *data;\n \n \tobj->offset = consumed_bytes;\n+\tinput_crc32 = crc32(0, Z_NULL, 0);\n \n \tp = fill(1);\n \tc = *p;\n@@ -276,7 +281,9 @@ static void *unpack_raw_entry(struct object_entry *obj, union delta_base *delta_\n \t}\n \tobj->hdr_size = consumed_bytes - obj->offset;\n \n-\treturn unpack_entry_data(obj->offset, obj->size);\n+\tdata = unpack_entry_data(obj->offset, obj->size);\n+\tobj->crc32 = input_crc32;\n+\treturn data;\n }\n \n static void *get_data_from_pack(struct object_entry *obj)\n@@ -521,7 +528,7 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\tfputc('\\n', stderr);\n }\n \n-static int write_compressed(int fd, void *in, unsigned int size)\n+static int write_compressed(int fd, void *in, unsigned int size, uint32_t *obj_crc)\n {\n \tz_stream stream;\n \tunsigned long maxsize;\n@@ -542,6 +549,7 @@ static int write_compressed(int fd, void *in, unsigned int size)\n \n \tsize = stream.total_out;\n \twrite_or_die(fd, out, size);\n+\t*obj_crc = crc32(*obj_crc, out, size);\n \tfree(out);\n \treturn size;\n }\n@@ -562,8 +570,10 @@ static void append_obj_to_pack(const unsigned char *sha1, void *buf,\n \t}\n \theader[n++] = c;\n \twrite_or_die(output_fd, header, n);\n+\tobj[0].crc32 = crc32(0, Z_NULL, 0);\n+\tobj[0].crc32 = crc32(obj[0].crc32, header, n);\n \tobj[1].offset = obj[0].offset + n;\n-\tobj[1].offset += write_compressed(output_fd, buf, size);\n+\tobj[1].offset += write_compressed(output_fd, buf, size, &obj[0].crc32);\n \thashcpy(obj->sha1, sha1);\n }\n \n-- \n1.5.1.696.g6d352-dirty\n"},{"id":"38910","messageId":"11760952002410-git-send-email-nico@cam.org","threadId":"7578","inReplyTo":"11760952002687-git-send-email-nico@cam.org","subject":"[PATCH 06/10] pack-objects: learn about pack index version 2","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-09T05:06:33Z","receivedAt":"2007-04-09T05:06:33Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Pack index version 2 goes as follows:\n\n - 8 bytes of header with signature and version.\n\n - 256 entries of 4-byte first-level fan-out table.\n\n - Table of sorted 20-byte SHA1 records for each object in pack.\n\n - Table of 4-byte CRC32 entries for raw pack object data.\n\n - Table of 4-byte offset entries for objects in the pack if offset is\n   representable with 31 bits or less, otherwise it is an index in the next\n   table with top bit set.\n\n - Table of 8-byte offset entries indexed from previous table for offsets\n   which are 32 bits or more (optional).\n\n - 20-byte SHA1 checksum of sorted object names.\n\n - 20-byte SHA1 checksum of the above.\n\nThe object SHA1 table is all contiguous so future pack format that would\ncontain this table directly won't require big changes to the code. It is\nalso tighter for slightly better cache locality when looking up entries.\n\nSupport for large packs exceeding 31 bits in size won't impose an index\nsize bloat for packs within that range that don't need a 64-bit offset.\nAnd because newer objects which are likely to be the most frequently used\nare located at the beginning of the pack, they won't pay the 64-bit offset\nlookup at run time either even if the pack is large.\n\nRight now an index version 2 is created only when the biggest offset in a\npack reaches 31 bits.  It might be a good idea to always use index version\n2 eventually to benefit from the CRC32 it contains when reusing pack data\nwhile repacking.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n builtin-pack-objects.c |   85 ++++++++++++++++++++++++++++++++++++++++++++----\n 1 files changed, 78 insertions(+), 7 deletions(-)\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 03e36f0..c7e0a42 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -169,13 +169,33 @@ static void prepare_pack_revindex(struct pack_revindex *rix)\n \tint i;\n \tconst char *index = p->index_data;\n \n-\tindex += 4 * 256;\n \trix->revindex = xmalloc(sizeof(*rix->revindex) * (num_ent + 1));\n-\tfor (i = 0; i < num_ent; i++) {\n-\t\tuint32_t hl = *((uint32_t *)(index + 24 * i));\n-\t\trix->revindex[i].offset = ntohl(hl);\n-\t\trix->revindex[i].nr = i;\n+\tindex += 4 * 256;\n+\n+\tif (p->index_version > 1) {\n+\t\tconst uint32_t *off_32 =\n+\t\t\t(uint32_t *)(index + 8 + p->num_objects * (20 + 4));\n+\t\tconst uint32_t *off_64 = off_32 + p->num_objects;\n+\t\tfor (i = 0; i < num_ent; i++) {\n+\t\t\tuint32_t off = ntohl(*off_32++);\n+\t\t\tif (!(off & 0x80000000)) {\n+\t\t\t\trix->revindex[i].offset = off;\n+\t\t\t} else {\n+\t\t\t\trix->revindex[i].offset =\n+\t\t\t\t\t((uint64_t)ntohl(*off_64++)) << 32;\n+\t\t\t\trix->revindex[i].offset |=\n+\t\t\t\t\tntohl(*off_64++);\n+\t\t\t}\n+\t\t\trix->revindex[i].nr = i;\n+\t\t}\n+\t} else {\n+\t\tfor (i = 0; i < num_ent; i++) {\n+\t\t\tuint32_t hl = *((uint32_t *)(index + 24 * i));\n+\t\t\trix->revindex[i].offset = ntohl(hl);\n+\t\t\trix->revindex[i].nr = i;\n+\t\t}\n \t}\n+\n \t/* This knows the pack format -- the 20-byte trailer\n \t * follows immediately after the last object data.\n \t */\n@@ -582,6 +602,18 @@ static void write_index_file(void)\n \tstruct object_entry **list = sorted_by_sha;\n \tstruct object_entry **last = list + nr_result;\n \tuint32_t array[256];\n+\tuint32_t index_version;\n+\n+\t/* if last object's offset is >= 2^31 we should use index V2 */\n+\tindex_version = (objects[nr_result-1].offset >> 31) ? 2 : 1;\n+\n+\t/* index versions 2 and above need a header */\n+\tif (index_version >= 2) {\n+\t\tstruct pack_idx_header hdr;\n+\t\thdr.idx_signature = htonl(PACK_IDX_SIGNATURE);\n+\t\thdr.idx_version = htonl(index_version);\n+\t\tsha1write(f, &hdr, sizeof(hdr));\n+\t}\n \n \t/*\n \t * Write the first-level table (the list is sorted,\n@@ -607,10 +639,49 @@ static void write_index_file(void)\n \tlist = sorted_by_sha;\n \tfor (i = 0; i < nr_result; i++) {\n \t\tstruct object_entry *entry = *list++;\n-\t\tuint32_t offset = htonl(entry->offset);\n-\t\tsha1write(f, &offset, 4);\n+\t\tif (index_version < 2) {\n+\t\t\tuint32_t offset = htonl(entry->offset);\n+\t\t\tsha1write(f, &offset, 4);\n+\t\t}\n \t\tsha1write(f, entry->sha1, 20);\n \t}\n+\n+\tif (index_version >= 2) {\n+\t\tunsigned int nr_large_offset = 0;\n+\n+\t\t/* write the crc32 table */\n+\t\tlist = sorted_by_sha;\n+\t\tfor (i = 0; i < nr_objects; i++) {\n+\t\t\tstruct object_entry *entry = *list++;\n+\t\t\tuint32_t crc32_val = htonl(entry->crc32);\n+\t\t\tsha1write(f, &crc32_val, 4);\n+\t\t}\n+\n+\t\t/* write the 32-bit offset table */\n+\t\tlist = sorted_by_sha;\n+\t\tfor (i = 0; i < nr_objects; i++) {\n+\t\t\tstruct object_entry *entry = *list++;\n+\t\t\tuint32_t offset = (entry->offset <= 0x7fffffff) ?\n+\t\t\t\tentry->offset : (0x80000000 | nr_large_offset++);\n+\t\t\toffset = htonl(offset);\n+\t\t\tsha1write(f, &offset, 4);\n+\t\t}\n+\n+\t\t/* write the large offset table */\n+\t\tlist = sorted_by_sha;\n+\t\twhile (nr_large_offset) {\n+\t\t\tstruct object_entry *entry = *list++;\n+\t\t\tuint64_t offset = entry->offset;\n+\t\t\tif (offset > 0x7fffffff) {\n+\t\t\t\tuint32_t split[2];\n+\t\t\t\tsplit[0]        = htonl(offset >> 32);\n+\t\t\t\tsplit[1] = htonl(offset & 0xffffffff);\n+\t\t\t\tsha1write(f, split, 8);\n+\t\t\t\tnr_large_offset--;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n \tsha1write(f, pack_file_sha1, 20);\n \tsha1close(f, NULL, 1);\n }\n-- \n1.5.1.696.g6d352-dirty\n"},{"id":"38913","messageId":"117609520190-git-send-email-nico@cam.org","threadId":"7578","inReplyTo":"11760952002410-git-send-email-nico@cam.org","subject":"[PATCH 07/10] index-pack: learn about pack index version 2","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-09T05:06:34Z","receivedAt":"2007-04-09T05:06:34Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Like previous patch but for index-pack.\n\n[ There is quite some code duplication between pack-objects and index-pack\n  for generating a pack index (and fast-import as well I suppose).  This\n  should be reworked into a common function eventually. But not now. ]\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n index-pack.c |   66 ++++++++++++++++++++++++++++++++++++++++++++++++++--------\n 1 files changed, 57 insertions(+), 9 deletions(-)\n\ndiff --git a/index-pack.c b/index-pack.c\nindex d33f723..a833f64 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -686,9 +686,10 @@ static const char *write_index_file(const char *index_name, unsigned char *sha1)\n {\n \tstruct sha1file *f;\n \tstruct object_entry **sorted_by_sha, **list, **last;\n-\tunsigned int array[256];\n+\tuint32_t array[256];\n \tint i, fd;\n \tSHA_CTX ctx;\n+\tuint32_t index_version;\n \n \tif (nr_objects) {\n \t\tsorted_by_sha =\n@@ -699,7 +700,6 @@ static const char *write_index_file(const char *index_name, unsigned char *sha1)\n \t\t\tsorted_by_sha[i] = &objects[i];\n \t\tqsort(sorted_by_sha, nr_objects, sizeof(sorted_by_sha[0]),\n \t\t      sha1_compare);\n-\n \t}\n \telse\n \t\tsorted_by_sha = list = last = NULL;\n@@ -718,6 +718,17 @@ static const char *write_index_file(const char *index_name, unsigned char *sha1)\n \t\tdie(\"unable to create %s: %s\", index_name, strerror(errno));\n \tf = sha1fd(fd, index_name);\n \n+\t/* if last object's offset is >= 2^31 we should use index V2 */\n+\tindex_version = (objects[nr_objects-1].offset >> 31) ? 2 : 1;\n+\n+\t/* index versions 2 and above need a header */\n+\tif (index_version >= 2) {\n+\t\tstruct pack_idx_header hdr;\n+\t\thdr.idx_signature = htonl(PACK_IDX_SIGNATURE);\n+\t\thdr.idx_version = htonl(index_version);\n+\t\tsha1write(f, &hdr, sizeof(hdr));\n+\t}\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@@ -734,24 +745,61 @@ static const char *write_index_file(const char *index_name, unsigned char *sha1)\n \t\tarray[i] = htonl(next - sorted_by_sha);\n \t\tlist = next;\n \t}\n-\tsha1write(f, array, 256 * sizeof(int));\n+\tsha1write(f, array, 256 * 4);\n \n-\t/* recompute the SHA1 hash of sorted object names.\n-\t * currently pack-objects does not do this, but that\n-\t * can be fixed.\n-\t */\n+\t/* compute the SHA1 hash of sorted object names. */\n \tSHA1_Init(&ctx);\n+\n \t/*\n \t * Write the actual SHA1 entries..\n \t */\n \tlist = sorted_by_sha;\n \tfor (i = 0; i < nr_objects; i++) {\n \t\tstruct object_entry *obj = *list++;\n-\t\tunsigned int offset = htonl(obj->offset);\n-\t\tsha1write(f, &offset, 4);\n+\t\tif (index_version < 2) {\n+\t\t\tuint32_t offset = htonl(obj->offset);\n+\t\t\tsha1write(f, &offset, 4);\n+\t\t}\n \t\tsha1write(f, obj->sha1, 20);\n \t\tSHA1_Update(&ctx, obj->sha1, 20);\n \t}\n+\n+\tif (index_version >= 2) {\n+\t\tunsigned int nr_large_offset = 0;\n+\n+\t\t/* write the crc32 table */\n+\t\tlist = sorted_by_sha;\n+\t\tfor (i = 0; i < nr_objects; i++) {\n+\t\t\tstruct object_entry *obj = *list++;\n+\t\t\tuint32_t crc32_val = htonl(obj->crc32);\n+\t\t\tsha1write(f, &crc32_val, 4);\n+\t\t}\n+\n+\t\t/* write the 32-bit offset table */\n+\t\tlist = sorted_by_sha;\n+\t\tfor (i = 0; i < nr_objects; i++) {\n+\t\t\tstruct object_entry *obj = *list++;\n+\t\t\tuint32_t offset = (obj->offset <= 0x7fffffff) ?\n+\t\t\t\tobj->offset : (0x80000000 | nr_large_offset++);\n+\t\t\toffset = htonl(offset);\n+\t\t\tsha1write(f, &offset, 4);\n+\t\t}\n+\n+\t\t/* write the large offset table */\n+\t\tlist = sorted_by_sha;\n+\t\twhile (nr_large_offset) {\n+\t\t\tstruct object_entry *obj = *list++;\n+\t\t\tuint64_t offset = obj->offset;\n+\t\t\tif (offset > 0x7fffffff) {\n+\t\t\t\tuint32_t split[2];\n+\t\t\t\tsplit[0]\t= htonl(offset >> 32);\n+\t\t\t\tsplit[1] = htonl(offset & 0xffffffff);\n+\t\t\t\tsha1write(f, split, 8);\n+\t\t\t\tnr_large_offset--;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n \tsha1write(f, sha1, 20);\n \tsha1close(f, NULL, 1);\n \tfree(sorted_by_sha);\n-- \n1.5.1.696.g6d352-dirty\n"},{"id":"38908","messageId":"11760952023952-git-send-email-nico@cam.org","threadId":"7578","inReplyTo":"117609520190-git-send-email-nico@cam.org","subject":"[PATCH 08/10] sha1_file.c: learn about index version 2","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-09T05:06:35Z","receivedAt":"2007-04-09T05:06:35Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"With this patch, packs larger than 4GB are usable, even on a 32-bit machine\n(at least on Linux).  If off_t is not large enough to deal with a large\npack then die() is called instead of attempting to use the pack and\nproducing garbage.\n\nThis was tested with a 8GB pack specially created for the occasion on\na 32-bit machine.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n sha1_file.c |  118 ++++++++++++++++++++++++++++++++++++++++++++--------------\n 1 files changed, 89 insertions(+), 29 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex ebdd497..5f3a15d 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -437,7 +437,7 @@ static int check_packed_git_idx(const char *path,  struct packed_git *p)\n \tvoid *idx_map;\n \tstruct pack_idx_header *hdr;\n \tsize_t idx_size;\n-\tuint32_t nr, i, *index;\n+\tuint32_t version, nr, i, *index;\n \tint fd = open(path, O_RDONLY);\n \tstruct stat st;\n \n@@ -455,21 +455,23 @@ static int check_packed_git_idx(const char *path,  struct packed_git *p)\n \tidx_map = xmmap(NULL, idx_size, PROT_READ, MAP_PRIVATE, fd, 0);\n \tclose(fd);\n \n-\t/* a future index format would start with this, as older git\n-\t * binaries would fail the non-monotonic index check below.\n-\t * give a nicer warning to the user if we can.\n-\t */\n \thdr = idx_map;\n \tif (hdr->idx_signature == htonl(PACK_IDX_SIGNATURE)) {\n-\t\tmunmap(idx_map, idx_size);\n-\t\treturn error(\"index file %s is a newer version\"\n-\t\t\t\" and is not supported by this binary\"\n-\t\t\t\" (try upgrading GIT to a newer version)\",\n-\t\t\tpath);\n-\t}\n+\t\tversion = ntohl(hdr->idx_version);\n+\t\tif (version < 2 || version > 2) {\n+\t\t\tmunmap(idx_map, idx_size);\n+\t\t\treturn error(\"index file %s is version %d\"\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, version);\n+\t\t}\n+\t} else\n+\t\tversion = 1;\n \n \tnr = 0;\n \tindex = idx_map;\n+\tif (version > 1)\n+\t\tindex += 2;  /* skip index header */\n \tfor (i = 0; i < 256; i++) {\n \t\tuint32_t n = ntohl(index[i]);\n \t\tif (n < nr) {\n@@ -479,19 +481,48 @@ static int check_packed_git_idx(const char *path,  struct packed_git *p)\n \t\tnr = n;\n \t}\n \n-\t/*\n-\t * Total size:\n-\t *  - 256 index entries 4 bytes each\n-\t *  - 24-byte entries * nr (20-byte sha1 + 4-byte offset)\n-\t *  - 20-byte SHA1 of the packfile\n-\t *  - 20-byte SHA1 file checksum\n-\t */\n-\tif (idx_size != 4*256 + nr * 24 + 20 + 20) {\n-\t\tmunmap(idx_map, idx_size);\n-\t\treturn error(\"wrong index file size in %s\", path);\n+\tif (version == 1) {\n+\t\t/*\n+\t\t * Total size:\n+\t\t *  - 256 index entries 4 bytes each\n+\t\t *  - 24-byte entries * nr (20-byte sha1 + 4-byte offset)\n+\t\t *  - 20-byte SHA1 of the packfile\n+\t\t *  - 20-byte SHA1 file checksum\n+\t\t */\n+\t\tif (idx_size != 4*256 + nr * 24 + 20 + 20) {\n+\t\t\tmunmap(idx_map, idx_size);\n+\t\t\treturn error(\"wrong index file size in %s\", path);\n+\t\t}\n+\t} else if (version == 2) {\n+\t\t/*\n+\t\t * Minimum size:\n+\t\t *  - 8 bytes of header\n+\t\t *  - 256 index entries 4 bytes each\n+\t\t *  - 20-byte sha1 entry * nr\n+\t\t *  - 4-byte crc entry * nr\n+\t\t *  - 4-byte offset entry * nr\n+\t\t *  - 20-byte SHA1 of the packfile\n+\t\t *  - 20-byte SHA1 file checksum\n+\t\t * And after the 4-byte offset table might be a \n+\t\t * variable sized table containing 8-byte entries\n+\t\t * for offsets larger than 2^31.\n+\t\t */\n+\t\tunsigned long min_size = 8 + 4*256 + nr*(20 + 4 + 4) + 20 + 20;\n+\t\tif (idx_size < min_size || idx_size > min_size + (nr - 1)*8) {\n+\t\t\tmunmap(idx_map, idx_size);\n+\t\t\treturn error(\"wrong index file size in %s\", path);\n+\t\t}\n+\t\tif (idx_size != min_size) {\n+\t\t\t/* make sure we can deal with large pack offsets */\n+\t\t\toff_t x = 0x7fffffffUL, y = 0xffffffffUL;\n+\t\t\tif (x > (x + 1) || y > (y + 1)) {\n+\t\t\t\tmunmap(idx_map, idx_size);\n+\t\t\t\treturn error(\"pack too large for current definition of off_t in %s\", path);\n+\t\t\t}\n+\t\t}\n \t}\n \n-\tp->index_version = 1;\n+\tp->index_version = version;\n \tp->index_data = idx_map;\n \tp->index_size = idx_size;\n \tp->num_objects = nr;\n@@ -1531,27 +1562,56 @@ const unsigned char *nth_packed_object_sha1(const struct packed_git *p,\n \t\t\t\t\t    uint32_t n)\n {\n \tconst unsigned char *index = p->index_data;\n-\tindex += 4 * 256;\n \tif (n >= p->num_objects)\n \t\treturn NULL;\n-\treturn index + 24 * n + 4;\n+\tindex += 4 * 256;\n+\tif (p->index_version == 1) {\n+\t\treturn index + 24 * n + 4;\n+\t} else {\n+\t\tindex += 8;\n+\t\treturn index + 20 * n;\n+\t}\n+}\n+\n+static off_t nth_packed_object_offset(const struct packed_git *p, uint32_t n)\n+{\n+\tconst unsigned char *index = p->index_data;\n+\tindex += 4 * 256;\n+\tif (p->index_version == 1) {\n+\t\treturn ntohl(*((uint32_t *)(index + 24 * n)));\n+\t} else {\n+\t\tuint32_t off;\n+\t\tindex += 8 + p->num_objects * (20 + 4);\n+\t\toff = ntohl(*((uint32_t *)(index + 4 * n)));\n+\t\tif (!(off & 0x80000000))\n+\t\t\treturn off;\n+\t\tindex += p->num_objects * 4 + (off & 0x7fffffff) * 8;\n+\t\treturn (((uint64_t)ntohl(*((uint32_t *)(index + 0)))) << 32) |\n+\t\t\t\t   ntohl(*((uint32_t *)(index + 4)));\n+\t}\n }\n \n off_t find_pack_entry_one(const unsigned char *sha1,\n \t\t\t\t  struct packed_git *p)\n {\n \tconst uint32_t *level1_ofs = p->index_data;\n-\tint hi = ntohl(level1_ofs[*sha1]);\n-\tint lo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));\n \tconst unsigned char *index = p->index_data;\n+\tunsigned hi, lo;\n \n+\tif (p->index_version > 1) {\n+\t\tlevel1_ofs += 2;\n+\t\tindex += 8;\n+\t}\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\tint mi = (lo + hi) / 2;\n-\t\tint cmp = hashcmp(index + 24 * mi + 4, sha1);\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-\t\t\treturn ntohl(*((uint32_t *)((char *)index + (24 * mi))));\n+\t\t\treturn nth_packed_object_offset(p, mi);\n \t\tif (cmp > 0)\n \t\t\thi = mi;\n \t\telse\n-- \n1.5.1.696.g6d352-dirty\n"},{"id":"38909","messageId":"11760952021074-git-send-email-nico@cam.org","threadId":"7578","inReplyTo":"11760952023952-git-send-email-nico@cam.org","subject":"[PATCH 09/10] show-index.c: learn about index v2","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-09T05:06:36Z","receivedAt":"2007-04-09T05:06:36Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"When index v2 is encountered, the CRC32 of each object is also displayed\nin parenthesis at the end of the line.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n show-index.c |   67 ++++++++++++++++++++++++++++++++++++++++++++++++++-------\n 1 files changed, 58 insertions(+), 9 deletions(-)\n\ndiff --git a/show-index.c b/show-index.c\nindex a30a2de..cae1f7d 100644\n--- a/show-index.c\n+++ b/show-index.c\n@@ -1,14 +1,26 @@\n #include \"cache.h\"\n+#include \"pack.h\"\n \n int main(int argc, char **argv)\n {\n \tint i;\n \tunsigned nr;\n-\tunsigned int entry[6];\n+\tunsigned int version;\n \tstatic unsigned int top_index[256];\n \n-\tif (fread(top_index, sizeof(top_index), 1, stdin) != 1)\n-\t\tdie(\"unable to read index\");\n+\tif (fread(top_index, 2 * 4, 1, stdin) != 1)\n+\t\tdie(\"unable to read header\");\n+\tif (top_index[0] == htonl(PACK_IDX_SIGNATURE)) {\n+\t\tversion = ntohl(top_index[1]);\n+\t\tif (version < 2 || version > 2)\n+\t\t\tdie(\"unknown index version\");\n+\t\tif (fread(top_index, 256 * 4, 1, stdin) != 1)\n+\t\t\tdie(\"unable to read index\");\n+\t} else {\n+\t\tversion = 1;\n+\t\tif (fread(&top_index[2], 254 * 4, 1, stdin) != 1)\n+\t\t\tdie(\"unable to read index\");\n+\t}\n \tnr = 0;\n \tfor (i = 0; i < 256; i++) {\n \t\tunsigned n = ntohl(top_index[i]);\n@@ -16,13 +28,50 @@ int main(int argc, char **argv)\n \t\t\tdie(\"corrupt index file\");\n \t\tnr = n;\n \t}\n-\tfor (i = 0; i < nr; i++) {\n-\t\tunsigned offset;\n+\tif (version == 1) {\n+\t\tfor (i = 0; i < nr; i++) {\n+\t\t\tunsigned int offset, entry[6];\n \n-\t\tif (fread(entry, 24, 1, stdin) != 1)\n-\t\t\tdie(\"unable to read entry %u/%u\", i, nr);\n-\t\toffset = ntohl(entry[0]);\n-\t\tprintf(\"%u %s\\n\", offset, sha1_to_hex((void *)(entry+1)));\n+\t\t\tif (fread(entry, 4 + 20, 1, stdin) != 1)\n+\t\t\t\tdie(\"unable to read entry %u/%u\", i, nr);\n+\t\t\toffset = ntohl(entry[0]);\n+\t\t\tprintf(\"%u %s\\n\", offset, sha1_to_hex((void *)(entry+1)));\n+\t\t}\n+\t} else {\n+\t\tunsigned off64_nr = 0;\n+\t\tstruct {\n+\t\t\tunsigned char sha1[20];\n+\t\t\tuint32_t crc;\n+\t\t\tuint32_t off;\n+\t\t} *entries = xmalloc(nr * sizeof(entries[0]));\n+\t\tfor (i = 0; i < nr; i++)\n+\t\t\tif (fread(entries[i].sha1, 20, 1, stdin) != 1)\n+\t\t\t\tdie(\"unable to read sha1 %u/%u\", i, nr);\n+\t\tfor (i = 0; i < nr; i++)\n+\t\t\tif (fread(&entries[i].crc, 4, 1, stdin) != 1)\n+\t\t\t\tdie(\"unable to read crc %u/%u\", i, nr);\n+\t\tfor (i = 0; i < nr; i++)\n+\t\t\tif (fread(&entries[i].off, 4, 1, stdin) != 1)\n+\t\t\t\tdie(\"unable to read 32b offset %u/%u\", i, nr);\n+\t\tfor (i = 0; i < nr; i++) {\n+\t\t\tuint64_t offset;\n+\t\t\tuint32_t off = ntohl(entries[i].off);\n+\t\t\tif (!(off & 0x80000000)) {\n+\t\t\t\toffset = off;\n+\t\t\t} else {\n+\t\t\t\tuint32_t off64[2];\n+\t\t\t\tif ((off & 0x7fffffff) != off64_nr)\n+\t\t\t\t\tdie(\"inconsistent 64b offset index\");\n+\t\t\t\tif (fread(off64, 8, 1, stdin) != 1)\n+\t\t\t\t\tdie(\"unable to read 64b offset %u\", off64_nr);\n+\t\t\t\toffset = (((uint64_t)ntohl(off64[0])) << 32) |\n+\t\t\t\t\t\t     ntohl(off64[1]);\n+\t\t\t\toff64_nr++;\n+\t\t\t}\n+\t\t\tprintf(\"%llu %s (%08x)\\n\", offset,\n+\t\t\t       sha1_to_hex(entries[i].sha1), ntohl(entries[i].crc));\n+\t\t}\n+\t\tfree(entries);\n \t}\n \treturn 0;\n }\n-- \n1.5.1.696.g6d352-dirty\n"},{"id":"38912","messageId":"11760952033684-git-send-email-nico@cam.org","threadId":"7578","inReplyTo":"11760952021074-git-send-email-nico@cam.org","subject":"[PATCH 10/10] pack-redundant.c: learn about index v2","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-09T05:06:37Z","receivedAt":"2007-04-09T05:06:37Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Initially the conversion was made using nth_packed_object_sha1() which\nmade this file completely index version agnostic. Unfortunately the\noverhead was quite significant so I went back to raw index walking but\nwith selectable base and step values which brought back similar\nperformances as the original.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n pack-redundant.c |   47 +++++++++++++++++++++++++++--------------------\n 1 files changed, 27 insertions(+), 20 deletions(-)\n\ndiff --git a/pack-redundant.c b/pack-redundant.c\nindex 40e579b..87077e1 100644\n--- a/pack-redundant.c\n+++ b/pack-redundant.c\n@@ -247,16 +247,19 @@ static struct pack_list * pack_list_difference(const struct pack_list *A,\n \n static void cmp_two_packs(struct pack_list *p1, struct pack_list *p2)\n {\n-\tint p1_off, p2_off;\n+\tunsigned long p1_off = 0, p2_off = 0, p1_step, p2_step;\n \tconst unsigned char *p1_base, *p2_base;\n \tstruct llist_item *p1_hint = NULL, *p2_hint = NULL;\n \n-\tp1_off = p2_off = 256 * 4 + 4;\n \tp1_base = p1->pack->index_data;\n \tp2_base = p2->pack->index_data;\n+\tp1_base += 256 * 4 + ((p1->pack->index_version < 2) ? 4 : 8);\n+\tp2_base += 256 * 4 + ((p2->pack->index_version < 2) ? 4 : 8);\n+\tp1_step = (p1->pack->index_version < 2) ? 24 : 20;\n+\tp2_step = (p2->pack->index_version < 2) ? 24 : 20;\n \n-\twhile (p1_off <= p1->pack->index_size - 3 * 20 &&\n-\t       p2_off <= p2->pack->index_size - 3 * 20)\n+\twhile (p1_off < p1->pack->num_objects * p1_step &&\n+\t       p2_off < p2->pack->num_objects * p2_step)\n \t{\n \t\tint cmp = hashcmp(p1_base + p1_off, p2_base + p2_off);\n \t\t/* cmp ~ p1 - p2 */\n@@ -265,14 +268,14 @@ static void cmp_two_packs(struct pack_list *p1, struct pack_list *p2)\n \t\t\t\t\tp1_base + p1_off, p1_hint);\n \t\t\tp2_hint = llist_sorted_remove(p2->unique_objects,\n \t\t\t\t\tp1_base + p1_off, p2_hint);\n-\t\t\tp1_off+=24;\n-\t\t\tp2_off+=24;\n+\t\t\tp1_off += p1_step;\n+\t\t\tp2_off += p2_step;\n \t\t\tcontinue;\n \t\t}\n \t\tif (cmp < 0) { /* p1 has the object, p2 doesn't */\n-\t\t\tp1_off+=24;\n+\t\t\tp1_off += p1_step;\n \t\t} else { /* p2 has the object, p1 doesn't */\n-\t\t\tp2_off+=24;\n+\t\t\tp2_off += p2_step;\n \t\t}\n \t}\n }\n@@ -352,28 +355,31 @@ static int is_superset(struct pack_list *pl, struct llist *list)\n static size_t sizeof_union(struct packed_git *p1, struct packed_git *p2)\n {\n \tsize_t ret = 0;\n-\tint p1_off, p2_off;\n+\tunsigned long p1_off = 0, p2_off = 0, p1_step, p2_step;\n \tconst unsigned char *p1_base, *p2_base;\n \n-\tp1_off = p2_off = 256 * 4 + 4;\n \tp1_base = p1->index_data;\n \tp2_base = p2->index_data;\n+\tp1_base += 256 * 4 + ((p1->index_version < 2) ? 4 : 8);\n+\tp2_base += 256 * 4 + ((p2->index_version < 2) ? 4 : 8);\n+\tp1_step = (p1->index_version < 2) ? 24 : 20;\n+\tp2_step = (p2->index_version < 2) ? 24 : 20;\n \n-\twhile (p1_off <= p1->index_size - 3 * 20 &&\n-\t       p2_off <= p2->index_size - 3 * 20)\n+\twhile (p1_off < p1->num_objects * p1_step &&\n+\t       p2_off < p2->num_objects * p2_step)\n \t{\n \t\tint cmp = hashcmp(p1_base + p1_off, p2_base + p2_off);\n \t\t/* cmp ~ p1 - p2 */\n \t\tif (cmp == 0) {\n \t\t\tret++;\n-\t\t\tp1_off+=24;\n-\t\t\tp2_off+=24;\n+\t\t\tp1_off += p1_step;\n+\t\t\tp2_off += p2_step;\n \t\t\tcontinue;\n \t\t}\n \t\tif (cmp < 0) { /* p1 has the object, p2 doesn't */\n-\t\t\tp1_off+=24;\n+\t\t\tp1_off += p1_step;\n \t\t} else { /* p2 has the object, p1 doesn't */\n-\t\t\tp2_off+=24;\n+\t\t\tp2_off += p2_step;\n \t\t}\n \t}\n \treturn ret;\n@@ -535,7 +541,7 @@ static void scan_alt_odb_packs(void)\n static struct pack_list * add_pack(struct packed_git *p)\n {\n \tstruct pack_list l;\n-\tsize_t off;\n+\tunsigned long off = 0, step;\n \tconst unsigned char *base;\n \n \tif (!p->pack_local && !(alt_odb || verbose))\n@@ -544,11 +550,12 @@ static struct pack_list * add_pack(struct packed_git *p)\n \tl.pack = p;\n \tllist_init(&l.all_objects);\n \n-\toff = 256 * 4 + 4;\n \tbase = p->index_data;\n-\twhile (off <= p->index_size - 3 * 20) {\n+\tbase += 256 * 4 + ((p->index_version < 2) ? 4 : 8);\n+\tstep = (p->index_version < 2) ? 24 : 20;\n+\twhile (off < p->num_objects * step) {\n \t\tllist_insert_back(l.all_objects, base + off);\n-\t\toff += 24;\n+\t\toff += step;\n \t}\n \t/* this list will be pruned in cmp_two_packs later */\n \tl.unique_objects = llist_copy(l.all_objects);\n-- \n1.5.1.696.g6d352-dirty\n"},{"id":"38918","messageId":"7vabxi6rkv.fsf@assigned-by-dhcp.cox.net","threadId":"7578","inReplyTo":"11760952002410-git-send-email-nico@cam.org","subject":"Re: [PATCH 06/10] pack-objects: learn about pack index version 2","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-04-09T05:32:16Z","receivedAt":"2007-04-09T05:32:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n> Support for large packs exceeding 31 bits in size won't impose an index\n> size bloat for packs within that range that don't need a 64-bit offset.\n> And because newer objects which are likely to be the most frequently used\n> are located at the beginning of the pack, they won't pay the 64-bit offset\n> lookup at run time either even if the pack is large.\n>\n> Right now an index version 2 is created only when the biggest offset in a\n> pack reaches 31 bits.  It might be a good idea to always use index version\n> 2 eventually to benefit from the CRC32 it contains when reusing pack data\n> while repacking.\n> ...\n> @@ -582,6 +602,18 @@ static void write_index_file(void)\n>  \tstruct object_entry **list = sorted_by_sha;\n>  \tstruct object_entry **last = list + nr_result;\n>  \tuint32_t array[256];\n> +\tuint32_t index_version;\n> +\n> +\t/* if last object's offset is >= 2^31 we should use index V2 */\n> +\tindex_version = (objects[nr_result-1].offset >> 31) ? 2 : 1;\n\nAlthough write_pack_file() iterates objects[] array in the\nascending order of index and calls write_one() for each of them,\nin the presense of \"we write base object before delta\" rule, is\nit always true that the last object in the objects[] array has\nthe largest offset?\n"},{"id":"38931","messageId":"alpine.LFD.0.98.0704091051430.28181@xanadu.home","threadId":"7578","inReplyTo":"7vabxi6rkv.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 06/10] pack-objects: learn about pack index version 2","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-09T14:54:57Z","receivedAt":"2007-04-09T14:54:57Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 8 Apr 2007, Junio C Hamano wrote:\n\n> Nicolas Pitre <nico@cam.org> writes:\n> \n> > Support for large packs exceeding 31 bits in size won't impose an index\n> > size bloat for packs within that range that don't need a 64-bit offset.\n> > And because newer objects which are likely to be the most frequently used\n> > are located at the beginning of the pack, they won't pay the 64-bit offset\n> > lookup at run time either even if the pack is large.\n> >\n> > Right now an index version 2 is created only when the biggest offset in a\n> > pack reaches 31 bits.  It might be a good idea to always use index version\n> > 2 eventually to benefit from the CRC32 it contains when reusing pack data\n> > while repacking.\n> > ...\n> > @@ -582,6 +602,18 @@ static void write_index_file(void)\n> >  \tstruct object_entry **list = sorted_by_sha;\n> >  \tstruct object_entry **last = list + nr_result;\n> >  \tuint32_t array[256];\n> > +\tuint32_t index_version;\n> > +\n> > +\t/* if last object's offset is >= 2^31 we should use index V2 */\n> > +\tindex_version = (objects[nr_result-1].offset >> 31) ? 2 : 1;\n> \n> Although write_pack_file() iterates objects[] array in the\n> ascending order of index and calls write_one() for each of them,\n> in the presense of \"we write base object before delta\" rule, is\n> it always true that the last object in the objects[] array has\n> the largest offset?\n\nOops, indeed it is not.  It is true in the index-pack but not here.\n\nPlease could you amend this patch with the following:\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex c7e0a42..8cf2871 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -548,11 +548,11 @@ static off_t write_one(struct sha1file *f,\n \treturn offset + size;\n }\n \n-static void write_pack_file(void)\n+static off_t write_pack_file(void)\n {\n \tuint32_t i;\n \tstruct sha1file *f;\n-\toff_t offset;\n+\toff_t offset, last_obj_offset = 0;\n \tstruct pack_header hdr;\n \tunsigned last_percent = 999;\n \tint do_progress = progress;\n@@ -575,6 +575,7 @@ static void write_pack_file(void)\n \tif (!nr_result)\n \t\tgoto done;\n \tfor (i = 0; i < nr_objects; i++) {\n+\t\tlast_obj_offset = offset;\n \t\toffset = write_one(f, objects + i, offset);\n \t\tif (do_progress) {\n \t\t\tunsigned percent = written * 100 / nr_result;\n@@ -592,9 +593,11 @@ static void write_pack_file(void)\n \tif (written != nr_result)\n \t\tdie(\"wrote %u objects while expecting %u\", written, nr_result);\n \tsha1close(f, pack_file_sha1, 1);\n+\n+\treturn last_obj_offset;\n }\n \n-static void write_index_file(void)\n+static void write_index_file(off_t last_obj_offset)\n {\n \tuint32_t i;\n \tstruct sha1file *f = sha1create(\"%s-%s.%s\", base_name,\n@@ -605,7 +608,7 @@ static void write_index_file(void)\n \tuint32_t index_version;\n \n \t/* if last object's offset is >= 2^31 we should use index V2 */\n-\tindex_version = (objects[nr_result-1].offset >> 31) ? 2 : 1;\n+\tindex_version = (last_obj_offset >> 31) ? 2 : 1;\n \n \t/* index versions 2 and above need a header */\n \tif (index_version >= 2) {\n@@ -1769,6 +1772,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \tif (reuse_cached_pack(object_list_sha1))\n \t\t;\n \telse {\n+\t\toff_t last_obj_offset;\n \t\tif (nr_result)\n \t\t\tprepare_pack(window, depth);\n \t\tif (progress == 1 && pack_to_stdout) {\n@@ -1778,9 +1782,9 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\t\tsignal(SIGALRM, SIG_IGN );\n \t\t\tprogress_update = 0;\n \t\t}\n-\t\twrite_pack_file();\n+\t\tlast_obj_offset = write_pack_file();\n \t\tif (!pack_to_stdout) {\n-\t\t\twrite_index_file();\n+\t\t\twrite_index_file(last_obj_offset);\n \t\t\tputs(sha1_to_hex(object_list_sha1));\n \t\t}\n \t}\n\nNicolas\n"},{"id":"38944","messageId":"20070409171925.GS5436@spearce.org","threadId":"7578","inReplyTo":"11760951973172-git-send-email-nico@cam.org","subject":"Re: support for large packs and 64-bit offsets","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-04-09T17:19:25Z","receivedAt":"2007-04-09T17:19:25Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre <nico@cam.org> wrote:\n> This patch series adds support for large packs to GIT.  It creates a new\n> index format to accommodate both larger offsets and to store a checksum\n> for each raw object in a pack.  More details is provided in each patch\n> commit message.\n> \n> This is not a replacement for the pack size limiting feature.  I think that\n> GIT should support both: large packs and split packs.\n\nI like this series.  I haven't had time to test it myself yet,\nand probably won't be able to do so before Junio merges it into a\npu or next release.  But it looks OK on a first read.\n\nIt is unfortunate that we are changing the index file format without\nalso bringing in packv4 support at the same time.  I have just been\ntoo swamped in useless bulls**t in day-job work to spend time on\nGit lately.\n\n-- \nShawn.\n"},{"id":"38939","messageId":"alpine.LFD.0.98.0704091328130.28181@xanadu.home","threadId":"7578","inReplyTo":"20070409171925.GS5436@spearce.org","subject":"Re: support for large packs and 64-bit offsets","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-09T17:32:26Z","receivedAt":"2007-04-09T17:32:26Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 9 Apr 2007, Shawn O. Pearce wrote:\n\n> It is unfortunate that we are changing the index file format without\n> also bringing in packv4 support at the same time.  I have just been\n> too swamped in useless bulls**t in day-job work to spend time on\n> Git lately.\n\nWell... I still did index v2 with pack v4 in mind.  The diference \nbetween index v2 and v3 would be minimal.\n\nPack v4 is coming along.  Slowly but still coming.\n\n\nNicolas\n"},{"id":"38945","messageId":"20070409174305.GU5436@spearce.org","threadId":"7578","inReplyTo":"alpine.LFD.0.98.0704091328130.28181@xanadu.home","subject":"Re: support for large packs and 64-bit offsets","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-04-09T17:43:05Z","receivedAt":"2007-04-09T17:43:05Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre <nico@cam.org> wrote:\n> On Mon, 9 Apr 2007, Shawn O. Pearce wrote:\n> \n> > It is unfortunate that we are changing the index file format without\n> > also bringing in packv4 support at the same time.  I have just been\n> > too swamped in useless bulls**t in day-job work to spend time on\n> > Git lately.\n> \n> Well... I still did index v2 with pack v4 in mind.  The diference \n> between index v2 and v3 would be minimal.\n> \n> Pack v4 is coming along.  Slowly but still coming.\n\nI take it you are working on it alone at this point?  I'd love\nto get back into it, but I don't think I've got the cycles for at\nleast a couple of weeks.\n\n\nHere's something we didn't think about, but that occurred to me today\nwhen reading this series: If we move the SHA-1 table out of the index\nand into the packfile (like we are planning) dumb commit-walkers\n(http-fetch) will have problems.  Right now they download the\nindexes of every available packfile to determine if they need to\ndownload the corresponding packfile to obtain a needed object.\n\nMoving the SHA-1 table from the index into the packfile will mean\nthe client cannot do this `optimization'.  Instead it will need to\nperform a byte-range request for part of the packfile to decide\nif it needs to fetch the remainder of that packfile; or it must\ndownload the entire packfile.  Since not all HTTP servers support\nbyte-range requests the former may not always be viable and the\nlatter is obviously not a good idea.\n\n-- \nShawn.\n"},{"id":"38937","messageId":"Pine.LNX.4.64.0704091059240.6730@woody.linux-foundation.org","threadId":"7578","inReplyTo":"20070409171925.GS5436@spearce.org","subject":"Re: support for large packs and 64-bit offsets","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-04-09T18:02:49Z","receivedAt":"2007-04-09T18:02:49Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 9 Apr 2007, Shawn O. Pearce wrote:\n> \n> I like this series.  I haven't had time to test it myself yet,\n> and probably won't be able to do so before Junio merges it into a\n> pu or next release.  But it looks OK on a first read.\n\nMe too.. I just wonder whether it should have some more test coverage:\n - force v2 index by default\n - force a mode where a random smattering of index entries are done using \n   64-bit notation (even if they obviously won't need the high 33 bits)\n\nAs it is, nobody would normally even *use* the new format, much less the \nnew capabilities.. And if it's not used, it's not tested, and it's going \nto have bugs.\n\n\t\tLinus\n"},{"id":"38938","messageId":"alpine.LFD.0.98.0704091417490.28181@xanadu.home","threadId":"7578","inReplyTo":"Pine.LNX.4.64.0704091059240.6730@woody.linux-foundation.org","subject":"Re: support for large packs and 64-bit offsets","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-09T18:26:41Z","receivedAt":"2007-04-09T18:26:41Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 9 Apr 2007, Linus Torvalds wrote:\n\n> \n> \n> On Mon, 9 Apr 2007, Shawn O. Pearce wrote:\n> > \n> > I like this series.  I haven't had time to test it myself yet,\n> > and probably won't be able to do so before Junio merges it into a\n> > pu or next release.  But it looks OK on a first read.\n> \n> Me too.. I just wonder whether it should have some more test coverage:\n>  - force v2 index by default\n\nEasy enough.  That's what I did for testing of course.  And I'd hope it \nwould be always on by default eventually.  The only reason why it is not \non by default is because of old clients with dumb protocols.\n\n>  - force a mode where a random smattering of index entries are done using \n>    64-bit notation (even if they obviously won't need the high 33 bits)\n\nThat could be achieved with an additional criteria, like the offset's \nLSB value which should be pretty random.\n\nOnce Junio merges the series in a branch of its own, we could have a \nseparate patch not in that branch that simply forces those features on \nin branch 'next'.  People would only need to remenber not publishing \nrepos with that version using dumb protocols.\n\n\nNicolas\n"},{"id":"38948","messageId":"20070409183412.GY5436@spearce.org","threadId":"7578","inReplyTo":"alpine.LFD.0.98.0704091417490.28181@xanadu.home","subject":"Re: support for large packs and 64-bit offsets","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-04-09T18:34:12Z","receivedAt":"2007-04-09T18:34:12Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre <nico@cam.org> wrote:\n> Once Junio merges the series in a branch of its own, we could have a \n> separate patch not in that branch that simply forces those features on \n> in branch 'next'.  People would only need to remenber not publishing \n> repos with that version using dumb protocols.\n\nBetter to force features by config file option or command line\noption, then by code hacked into a branch.  This way we can enable\nthe feature all of the time in a test case, and push it.  E.g. the\nsliding window controls; nobody really uses them in practice (I\ndon't think anyway) but they are handy in the test cases to force\nparticular conditions, without creating huge temporary packfiles.\n\n-- \nShawn.\n"},{"id":"38969","messageId":"alpine.LFD.0.98.0704091542400.28181@xanadu.home","threadId":"7578","inReplyTo":"alpine.LFD.0.98.0704091417490.28181@xanadu.home","subject":"Re: support for large packs and 64-bit offsets","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-09T19:46:38Z","receivedAt":"2007-04-09T19:46:38Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 9 Apr 2007, Nicolas Pitre wrote:\n\n> >  - force a mode where a random smattering of index entries are done using \n> >    64-bit notation (even if they obviously won't need the high 33 bits)\n> \n> That could be achieved with an additional criteria, like the offset's \n> LSB value which should be pretty random.\n> \n> Once Junio merges the series in a branch of its own, we could have a \n> separate patch not in that branch that simply forces those features on \n> in branch 'next'.\n\nSomething like this, although I suppose this might require a more \npermanent solution for the test suite:\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 8cf2871..8d20ea9 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -607,8 +607,12 @@ static void write_index_file(off_t last_obj_offset)\n \tuint32_t array[256];\n \tuint32_t index_version;\n \n+#if 0\n \t/* if last object's offset is >= 2^31 we should use index V2 */\n \tindex_version = (last_obj_offset >> 31) ? 2 : 1;\n+#else\n+\tindex_version = 2;\n+#endif\n \n \t/* index versions 2 and above need a header */\n \tif (index_version >= 2) {\n@@ -664,8 +668,15 @@ static void write_index_file(off_t last_obj_offset)\n \t\tlist = sorted_by_sha;\n \t\tfor (i = 0; i < nr_objects; i++) {\n \t\t\tstruct object_entry *entry = *list++;\n+#if 0\n \t\t\tuint32_t offset = (entry->offset <= 0x7fffffff) ?\n \t\t\t\tentry->offset : (0x80000000 | nr_large_offset++);\n+#else\n+\t\t\t/* force some offsets to the 64-bit table for testing */\n+\t\t\tuint32_t offset =\n+\t\t\t\t(!(entry->offset & 1) && entry->offset <= 0x7fffffff) ?\n+\t\t\t\tentry->offset : (0x80000000 | nr_large_offset++);\n+#endif\n \t\t\toffset = htonl(offset);\n \t\t\tsha1write(f, &offset, 4);\n \t\t}\n@@ -675,7 +686,11 @@ static void write_index_file(off_t last_obj_offset)\n \t\twhile (nr_large_offset) {\n \t\t\tstruct object_entry *entry = *list++;\n \t\t\tuint64_t offset = entry->offset;\n+#if 0\n \t\t\tif (offset > 0x7fffffff) {\n+#else\n+\t\t\tif (offset & 1 || offset > 0x7fffffff) {\n+#endif\n \t\t\t\tuint32_t split[2];\n \t\t\t\tsplit[0]        = htonl(offset >> 32);\n \t\t\t\tsplit[1] = htonl(offset & 0xffffffff);\ndiff --git a/index-pack.c b/index-pack.c\nindex a833f64..1e6db2b 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -718,8 +718,13 @@ static const char *write_index_file(const char *index_name, unsigned char *sha1)\n \t\tdie(\"unable to create %s: %s\", index_name, strerror(errno));\n \tf = sha1fd(fd, index_name);\n \n+#if 0\n \t/* if last object's offset is >= 2^31 we should use index V2 */\n \tindex_version = (objects[nr_objects-1].offset >> 31) ? 2 : 1;\n+#else\n+\t/* force v2 always on for testing */\n+\tindex_version = 2;\n+#endif\n \n \t/* index versions 2 and above need a header */\n \tif (index_version >= 2) {\n@@ -779,8 +784,15 @@ static const char *write_index_file(const char *index_name, unsigned char *sha1)\n \t\tlist = sorted_by_sha;\n \t\tfor (i = 0; i < nr_objects; i++) {\n \t\t\tstruct object_entry *obj = *list++;\n+#if 0\n \t\t\tuint32_t offset = (obj->offset <= 0x7fffffff) ?\n \t\t\t\tobj->offset : (0x80000000 | nr_large_offset++);\n+#else\n+\t\t\t/* force some offsets to the 64-bit table for testing */\n+\t\t\tuint32_t offset =\n+\t\t\t\t(!(obj->offset & 1) && obj->offset <= 0x7fffffff) ?\n+\t\t\t\tobj->offset : (0x80000000 | nr_large_offset++);\n+#endif\n \t\t\toffset = htonl(offset);\n \t\t\tsha1write(f, &offset, 4);\n \t\t}\n@@ -790,7 +802,11 @@ static const char *write_index_file(const char *index_name, unsigned char *sha1)\n \t\twhile (nr_large_offset) {\n \t\t\tstruct object_entry *obj = *list++;\n \t\t\tuint64_t offset = obj->offset;\n+#if 0\n \t\t\tif (offset > 0x7fffffff) {\n+#else\n+\t\t\tif (offset & 1 || offset > 0x7fffffff) {\n+#endif\n \t\t\t\tuint32_t split[2];\n \t\t\t\tsplit[0]\t= htonl(offset >> 32);\n \t\t\t\tsplit[1] = htonl(offset & 0xffffffff);\n"},{"id":"38970","messageId":"7vtzvpz5tu.fsf@assigned-by-dhcp.cox.net","threadId":"7578","inReplyTo":"20070409174305.GU5436@spearce.org","subject":"Re: support for large packs and 64-bit offsets","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-04-09T19:49:17Z","receivedAt":"2007-04-09T19:49:17Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" <spearce@spearce.org> writes:\n\n> Nicolas Pitre <nico@cam.org> wrote:\n> ...\n> Here's something we didn't think about, but that occurred to me today\n> when reading this series: If we move the SHA-1 table out of the index\n> and into the packfile (like we are planning) dumb commit-walkers\n> (http-fetch) will have problems.  Right now they download the\n> indexes of every available packfile to determine if they need to\n> download the corresponding packfile to obtain a needed object.\n\nIf we really care about older dumb clients, one option is to\ngenerate not .idx but .idx2, and have a corresponding .idx only\nto support them.  But at that point, it's probably cleaner to\nhave an explicit option to produce .idx file of a particular\nversion, and tell people to pack public repositories they expect\nolder dumb clients to access with that option to keep things\nbackward compatible.\n"},{"id":"38958","messageId":"20070409195322.GB5436@spearce.org","threadId":"7578","inReplyTo":"7vtzvpz5tu.fsf@assigned-by-dhcp.cox.net","subject":"Re: support for large packs and 64-bit offsets","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-04-09T19:53:22Z","receivedAt":"2007-04-09T19:53:22Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano <junkio@cox.net> wrote:\n> \"Shawn O. Pearce\" <spearce@spearce.org> writes:\n> \n> > Nicolas Pitre <nico@cam.org> wrote:\n> > ...\n> > Here's something we didn't think about, but that occurred to me today\n> > when reading this series: If we move the SHA-1 table out of the index\n> > and into the packfile (like we are planning) dumb commit-walkers\n> > (http-fetch) will have problems.  Right now they download the\n> > indexes of every available packfile to determine if they need to\n> > download the corresponding packfile to obtain a needed object.\n> \n> If we really care about older dumb clients, one option is to\n> generate not .idx but .idx2, and have a corresponding .idx only\n> to support them.  But at that point, it's probably cleaner to\n> have an explicit option to produce .idx file of a particular\n> version, and tell people to pack public repositories they expect\n> older dumb clients to access with that option to keep things\n> backward compatible.\n\nSure, fine.  But I think you missed my point above - right now if\nwe move the SHA-1 table out of the .idx file I'm not sure we know\nhow to support the dumb clients *at all*.  Even if they understand\nthe latest-and-greatest file formats...\n\n-- \nShawn.\n"},{"id":"38957","messageId":"alpine.LFD.0.98.0704091601470.28181@xanadu.home","threadId":"7578","inReplyTo":"20070409195322.GB5436@spearce.org","subject":"Re: support for large packs and 64-bit offsets","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-09T20:02:37Z","receivedAt":"2007-04-09T20:02:37Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 9 Apr 2007, Shawn O. Pearce wrote:\n\n> Junio C Hamano <junkio@cox.net> wrote:\n> > \"Shawn O. Pearce\" <spearce@spearce.org> writes:\n> > \n> > > Nicolas Pitre <nico@cam.org> wrote:\n> > > ...\n> > > Here's something we didn't think about, but that occurred to me today\n> > > when reading this series: If we move the SHA-1 table out of the index\n> > > and into the packfile (like we are planning) dumb commit-walkers\n> > > (http-fetch) will have problems.  Right now they download the\n> > > indexes of every available packfile to determine if they need to\n> > > download the corresponding packfile to obtain a needed object.\n> > \n> > If we really care about older dumb clients, one option is to\n> > generate not .idx but .idx2, and have a corresponding .idx only\n> > to support them.  But at that point, it's probably cleaner to\n> > have an explicit option to produce .idx file of a particular\n> > version, and tell people to pack public repositories they expect\n> > older dumb clients to access with that option to keep things\n> > backward compatible.\n> \n> Sure, fine.  But I think you missed my point above - right now if\n> we move the SHA-1 table out of the .idx file I'm not sure we know\n> how to support the dumb clients *at all*.  Even if they understand\n> the latest-and-greatest file formats...\n\nThe table could live in both the pack and the index for those repos \nexpected to be exportable through dumb protocols.\n\n\nNicolas\n"},{"id":"38960","messageId":"7vwt0lxpxe.fsf@assigned-by-dhcp.cox.net","threadId":"7578","inReplyTo":"20070409195322.GB5436@spearce.org","subject":"Re: support for large packs and 64-bit offsets","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-04-09T20:18:05Z","receivedAt":"2007-04-09T20:18:05Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" <spearce@spearce.org> writes:\n\n> Sure, fine.  But I think you missed my point above - right now if\n> we move the SHA-1 table out of the .idx file I'm not sure we know\n> how to support the dumb clients *at all*.  Even if they understand\n> the latest-and-greatest file formats...\n\nWe do an incremental .keep pack for packs 100 objects or more.\nIf .idx omits SHA-1 values but keeps the crc and offset, that\nwould be around 12 bytes per object (but you may need an index\ninto the real SHA-1 table in the .pack file, I dunno) so that\nwould be 1200 bytes.  If we duplicate SHA-1 table also in .idx\nthat would make it 32-byte per object, totalling 3200 bytes,\nwhich admittedly is near 3-fold increase, but it may be worth if\nwe want to avoid the hassle.\n"}]}