{"thread":{"id":"29050","subject":"[PATCH 3/3] Implement fast hash-collision detection","startedAt":"2011-11-30T06:30:21Z","lastAt":"2011-11-30T06:30:21Z","messageCount":1,"participants":["Bill Zaumen"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"180135","messageId":"1322634621.1728.349.camel@yos","threadId":"29050","inReplyTo":null,"subject":"[PATCH 3/3] Implement fast hash-collision detection","fromName":"Bill Zaumen","fromEmail":"bill.zaumen@gmail.com","sentAt":"2011-11-30T06:30:21Z","receivedAt":"2011-11-30T06:30:21Z","isPatch":true,"sender":{"key":"bill.zaumen@gmail.com","avatar":null},"body":"Maintains a database of CRCs of Git objects to allow SHA-1 hash\ncollisions to be detected with high probability (1 - 1/2^32) and with\nlittle computational overhead. The CRCs cover the content of Git\nobjects, but not the header. For loose objects, these are stored in\nsubdirectories of GIT_DIRECTORY/objects/crcs, with each subdirectory's\nname consisting of the first two hexadecimal digits of the\ncorresponding object's SHA-1 hash. For each pack file, FILE.pack, the\nCRCs are stored in a FILE.mds, in the same order as the SHA-1 hashes\nthat appear in FILE.idx. Checks for hash collisions are made whenever\na new loose object is created.\n\nA new capability, \"mds-check\" has been added to git-fetch-pack,\ngit-upload-pack, git-send-pack, and git-receive-pack to allow a CRC to\nbe used in addition to SHA-1 hash values. For commits, a CRC of the\nCRCs of each blob reachable from a commit's tree is also used. The\nresult is that hash collisions can be detected during fetch, pull, and\npush operations.\n\nA few git commands had additional command-line arguments added:\ncount-objects, index-pack, and verify-pack. Please read\nDocumentation/technical/collision-detect.txt for further details\nand the documentation for each command for details on the new\narguments.\n\nSigned-off-by: Bill Zaumen \n---\n Makefile | 32 +++\n builtin/count-objects.c | 92 +++++++++-\n builtin/fetch-pack.c | 42 ++++-\n builtin/index-pack.c | 140 +++++++++++++--\n builtin/init-db.c | 17 ++-\n builtin/pack-objects.c | 57 ++++++-\n builtin/pack-redundant.c | 14 +-\n builtin/prune-packed.c | 21 ++-\n builtin/prune.c | 1 +\n builtin/receive-pack.c | 120 +++++++++++-\n builtin/send-pack.c | 45 +++++-\n builtin/verify-pack.c | 14 ++-\n cache.h | 61 ++++++-\n commit.c | 109 +++++++++++\n commit.h | 8 +\n environment.c | 57 ++++++-\n fast-import.c | 74 +++++++-\n git-repack.sh | 12 +-\n git.c | 15 ++-\n hex.c | 58 ++++++-\n http.c | 19 ++-\n pack-write.c | 95 +++++++++\n pack.h | 3 +\n sha1_file.c | 461 ++++++++++++++++++++++++++++++++++++++++-----\n t/t0000-basic.sh | 13 +-\n t/t5300-pack-object.sh | 17 ++-\n t/t5301-sliding-window.sh | 14 +-\n t/t5302-pack-index.sh | 6 +-\n t/t5304-prune.sh | 13 +-\n t/t5500-fetch-pack.sh | 10 +-\n t/t5510-fetch.sh | 12 +-\n t/t9300-fast-import.sh | 8 +-\n upload-pack.c | 28 +++-\n 33 files changed, 1550 insertions(+), 138 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex b1c80a6..3dda96b 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -260,6 +260,19 @@ all::\n # dependency rules.\n #\n # Define NATIVE_CRLF if your platform uses CRLF for line endings.\n+#\n+# Define CRCDB to indicate the database type for the DB mapping SHA1\n+# values to the CRCs of the objects git stores. Valid values are 0\n+# for storing each local-object crc in its own file, and 1 for storing\n+# each local-object crc in its own file and additionally using a\n+# GDBM implementation of packdb to store CRCs that are not in their\n+# on files as an aid for generating pack mds files. [more to be added\n+# as needed].\n+#\n+# Note: the values for CRCDB are determined by preprocessor directives\n+# defined in crcdb.h\n+#\n+CRCDB = 0\n \n GIT-VERSION-FILE: FORCE\n \t@$(SHELL_PATH) ./GIT-VERSION-GEN\n@@ -513,6 +526,7 @@ LIB_H += blob.h\n LIB_H += builtin.h\n LIB_H += cache.h\n LIB_H += cache-tree.h\n+LIB_H += crcdb.h\n LIB_H += color.h\n LIB_H += commit.h\n LIB_H += compat/bswap.h\n@@ -805,6 +819,7 @@ BUILTIN_OBJS += builtin/write-tree.o\n GITLIBS = $(LIB_FILE) $(XDIFF_LIB)\n EXTLIBS =\n \n+\n #\n # Platform specific tweaks\n #\n@@ -1662,6 +1677,23 @@ ifeq ($(PYTHON_PATH),)\n NO_PYTHON=NoThanks\n endif\n \n+ifdef CRCDB\n+BASIC_CFLAGS += -DBLOB_MDS_CHECK\n+endif\n+\n+ifeq ($(CRCDB), 0)\n+BASIC_CFLAGS += -DCRCDB=$(CRCDB)\n+CRCDB_SRC = objd-crcdb.c\n+LIB_OBJS += objd-crcdb.o\n+endif\n+\n+ifeq ($(CRCDB), 1)\n+BASIC_CFLAGS += -DCRCDB=$(CRCDB) -DPACKDB\n+CRCDB_SRC = objd-crcdb.c gdbm-packdb.c\n+LIB_OBJS += objd-crcdb.o gdbm-packdb.o\n+EXTLIBS += -lgdbm\n+endif\n+\n QUIET_SUBDIR0 = +$(MAKE) -C # space to separate -C and subdir\n QUIET_SUBDIR1 =\n \ndiff --git a/builtin/count-objects.c b/builtin/count-objects.c\nindex c37cb98..898d970 100644\n--- a/builtin/count-objects.c\n+++ b/builtin/count-objects.c\n@@ -8,6 +8,12 @@\n #include \"dir.h\"\n #include \"builtin.h\"\n #include \"parse-options.h\"\n+#include \"crcdb.h\"\n+\n+int mdsmode = 0;\n+unsigned long has_loose_mds = 0;\n+unsigned long loose_mds_missing = 0;\n+\n \n static void count_objects(DIR *d, char *path, int len, int verbose,\n \t\t\t unsigned long *loose,\n@@ -53,20 +59,37 @@ static void count_objects(DIR *d, char *path, int len, int verbose,\n \t\t\tcontinue;\n \t\t}\n \t\t(*loose)++;\n-\t\tif (!verbose)\n+\t\tif (!verbose) {\n+\t\t\tif (mdsmode) {\n+\t\t\t\tif (get_sha1_hex(hex, sha1)) {\n+\t\t\t\t\tdie(\"internal error\");\n+\t\t\t\t} else if (crcdb_lookup(NULL, sha1, NULL) > 0) {\n+\t\t\t\t\thas_loose_mds++;\n+\t\t\t\t} else {\n+\t\t\t\t\tloose_mds_missing++;\n+\t\t\t\t}\n+\t\t\t}\n \t\t\tcontinue;\n+\t\t}\n \t\tmemcpy(hex, path+len, 2);\n \t\tmemcpy(hex+2, ent->d_name, 38);\n \t\thex[40] = 0;\n \t\tif (get_sha1_hex(hex, sha1))\n \t\t\tdie(\"internal error\");\n+\t\tif (mdsmode) {\n+\t\t\tif (crcdb_lookup(NULL, sha1, NULL) > 0) {\n+\t\t\t\thas_loose_mds++;\n+\t\t\t} else {\n+\t\t\t\tloose_mds_missing++;\n+\t\t\t}\n+\t\t}\n \t\tif (has_sha1_pack(sha1))\n \t\t\t(*packed_loose)++;\n \t}\n }\n \n static char const * const count_objects_usage[] = {\n-\t\"git count-objects [-v]\",\n+\t\"git count-objects [-v] [-M]\",\n \tNULL\n };\n \n@@ -80,6 +103,8 @@ int cmd_count_objects(int argc, const char **argv, const char *prefix)\n \toff_t loose_size = 0;\n \tstruct option opts[] = {\n \t\tOPT__VERBOSE(&verbose, \"be verbose\"),\n+\t\tOPT_BOOLEAN('M', \"count-md\", &mdsmode,\n+\t\t\t \"count MDs (Message Digests)\"),\n \t\tOPT_END(),\n \t};\n \n@@ -90,6 +115,7 @@ int cmd_count_objects(int argc, const char **argv, const char *prefix)\n \tmemcpy(path, objdir, len);\n \tif (len && objdir[len-1] != '/')\n \t\tpath[len++] = '/';\n+\tcrcdb_open(NULL);\n \tfor (i = 0; i < 256; i++) {\n \t\tDIR *d;\n \t\tsprintf(path + len, \"%02x\", i);\n@@ -100,10 +126,16 @@ int cmd_count_objects(int argc, const char **argv, const char *prefix)\n \t\t\t &loose, &loose_size, &packed_loose, &garbage);\n \t\tclosedir(d);\n \t}\n+\tcrcdb_close(NULL);\n \tif (verbose) {\n \t\tstruct packed_git *p;\n \t\tunsigned long num_pack = 0;\n \t\toff_t size_pack = 0;\n+\t\tunsigned long mds_mismatched = 0;\n+\t\tunsigned long missing_mdsfile_count = 0;\n+\t\tunsigned long mds_count = 0;\n+\t\tint wsize = 0;\n+\t\tuint32_t crc;\n \t\tif (!packed_git)\n \t\t\tprepare_packed_git();\n \t\tfor (p = packed_git; p; p = p->next) {\n@@ -114,6 +146,40 @@ int cmd_count_objects(int argc, const char **argv, const char *prefix)\n \t\t\tpacked += p->num_objects;\n \t\t\tsize_pack += p->pack_size + p->index_size;\n \t\t\tnum_pack++;\n+\t\t\tif (!mdsmode)\n+\t\t\t\tcontinue;\n+\t\t\tif (open_pack_mds(p)) {\n+\t\t\t\tmissing_mdsfile_count++;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\t/*\n+\t\t\t * Assume mds version 1 for now. We check that\n+\t\t\t * the mds file has the right size and record if it\n+\t\t\t * doesn't. If it is the right size, we go through\n+\t\t\t * all the entries and count the number of sha1 hashes\n+\t\t\t * for which there is a recorded CRC. We do not\n+\t\t\t * check if the CRC is the right one for the\n+\t\t\t * corresponding object: run git pack-verify to do\n+\t\t\t * that.\n+\t\t\t */\n+\t\t\tif (p->mds_size > 7) {\n+\t\t\t wsize = ((unsigned char *)(p->mds_data))[7] * 4;\n+\t\t\t}\n+\t\t\tif (p->mds_size == (size_t)8 +\n+\t\t\t (((size_t)\n+\t\t\t ((p->num_objects)/4 + (p->num_objects % 4 != 0))\n+\t\t\t * (size_t)4 * (size_t)(1 + wsize)) +\n+\t\t\t (size_t)(20 * 2))) {\n+\t\t\t\tfor (i = 0; i < p->num_objects; i++) {\n+\t\t\t\t\tmds_count +=\n+\t\t\t\t\t (nth_packed_object_objcrc32(p,\n+\t\t\t\t\t\t\t\t i,\n+\t\t\t\t\t\t\t\t &crc)\n+\t\t\t\t\t == 1);\n+\t\t\t\t}\n+\t\t\t} else {\n+\t\t\t mds_mismatched++;\n+\t\t\t}\n \t\t}\n \t\tprintf(\"count: %lu\\n\", loose);\n \t\tprintf(\"size: %lu\\n\", (unsigned long) (loose_size / 1024));\n@@ -122,9 +188,31 @@ int cmd_count_objects(int argc, const char **argv, const char *prefix)\n \t\tprintf(\"size-pack: %lu\\n\", (unsigned long) (size_pack / 1024));\n \t\tprintf(\"prune-packable: %lu\\n\", packed_loose);\n \t\tprintf(\"garbage: %lu\\n\", garbage);\n+\t\tif (mdsmode) {\n+\t\t\tif (missing_mdsfile_count) {\n+\t\t\t\tprintf(\"missing MD (Message Digest) \"\n+\t\t\t\t \"files: %lu\\n\",\n+\t\t\t\t\tmissing_mdsfile_count);\n+\t\t\t}\n+\t\t\tif (mds_mismatched)\n+\t\t\t\tprintf(\"MD (Message Digest) files with\"\n+\t\t\t\t \" wrong size: %lu \"\n+\t\t\t\t \"(file extension = .mds)\\n\",\n+\t\t\t\t\tmds_mismatched);\n+\t\t\tif (packed != mds_count) {\n+\t\t\t\tprintf(\"missing MD (Message Digest)\"\n+\t\t\t\t \" count: %lu\\n\",\n+\t\t\t\t packed - mds_count);\n+\t\t\t}\n+\t\t}\n \t}\n \telse\n \t\tprintf(\"%lu objects, %lu kilobytes\\n\",\n \t\t loose, (unsigned long) (loose_size / 1024));\n+\tif (mdsmode && loose_mds_missing) {\n+\t\tassert(loose == (loose_mds_missing + has_loose_mds));\n+\t\tprintf(\"%lu loose objects with no MD (Message Digest)\\n\",\n+\t\t loose_mds_missing);\n+\t}\n \treturn 0;\n }\ndiff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c\nindex c6bc8eb..7472021 100644\n--- a/builtin/fetch-pack.c\n+++ b/builtin/fetch-pack.c\n@@ -18,6 +18,8 @@ static int prefer_ofs_delta = 1;\n static int no_done;\n static int fetch_fsck_objects = -1;\n static int transfer_fsck_objects = -1;\n+static int mds_check = 0;\n+\n static struct fetch_pack_args args = {\n \t/* .uploadpack = */ \"git-upload-pack\",\n };\n@@ -390,9 +392,38 @@ static int find_common(int fd[2], unsigned char *result_sha1,\n \tflushes = 0;\n \tretval = -1;\n \twhile ((sha1 = get_rev())) {\n-\t\tpacket_buf_write(&req_buf, \"have %s\\n\", sha1_to_hex(sha1));\n-\t\tif (args.verbose)\n-\t\t\tfprintf(stderr, \"have %s\\n\", sha1_to_hex(sha1));\n+\t\tif (mds_check) {\n+\t\t\tuint32_t objcrc;\n+\t\t\tif (has_sha1_file_crc(sha1, &objcrc)) {\n+\t\t\t\tuint32_t blobs_crc;\n+\t\t\t\tint has_blobs_crc = !get_blob_mds(sha1,\n+\t\t\t\t\t\t\t\t &blobs_crc);\n+\t\t\t\tif (has_blobs_crc)\n+\t\t\t\t\tpacket_buf_write(&req_buf,\n+\t\t\t\t\t\t\t \"have \"\n+\t\t\t\t\t\t\t \"%s-%8.8x-%8.8x\\n\",\n+\t\t\t\t\t\t\t sha1_to_hex(sha1),\n+\t\t\t\t\t\t\t ntohl(objcrc),\n+\t\t\t\t\t\t\t ntohl(blobs_crc));\n+\t\t\t\telse\n+\t\t\t\t\tpacket_buf_write(&req_buf,\n+\t\t\t\t\t\t\t \"have \"\n+\t\t\t\t\t\t\t \"%s-%8.8x\\n\",\n+\t\t\t\t\t\t\t sha1_to_hex(sha1),\n+\t\t\t\t\t\t\t ntohl(objcrc));\n+\n+\t\t\t} else {\n+\t\t\t\tpacket_buf_write(&req_buf, \"have %s\\n\",\n+\t\t\t\t\t\t sha1_to_hex(sha1));\n+\t\t\t}\n+\t\t\tif (args.verbose)\n+\t\t\t\tfprintf(stderr, \"have %s\\n\", sha1_to_hex(sha1));\n+\t\t} else {\n+\t\t\tpacket_buf_write(&req_buf, \"have %s\\n\",\n+\t\t\t\t\t sha1_to_hex(sha1));\n+\t\t\tif (args.verbose)\n+\t\t\t\tfprintf(stderr, \"have %s\\n\", sha1_to_hex(sha1));\n+\t\t}\n \t\tin_vain++;\n \t\tif (flush_at <= ++count) {\n \t\t\tint ack;\n@@ -802,6 +833,11 @@ static struct ref *do_fetch_pack(int fd[2],\n \t\t\tfprintf(stderr, \"Server supports ofs-delta\\n\");\n \t} else\n \t\tprefer_ofs_delta = 0;\n+\tif (server_supports(\"mds-check\")) {\n+\t\tif (args.verbose)\n+\t\t\tfprintf(stderr, \"Server supports mds-check\\n\");\n+\t\tmds_check = 1;\n+\t}\n \tif (everything_local(&ref, nr_match, match)) {\n \t\tpacket_flush(fd[1]);\n \t\tgoto all_done;\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 0945adb..b49f6ee 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1,3 +1,4 @@\n+#include \n #include \"builtin.h\"\n #include \"delta.h\"\n #include \"pack.h\"\n@@ -23,6 +24,14 @@ struct object_entry {\n \tint base_object_no;\n };\n \n+static int sha1_compare(const void *_a, const void *_b)\n+{\n+\tstruct object_entry *a = (struct object_entry *)_a;\n+\tstruct object_entry *b = (struct object_entry *)_b;\n+\treturn hashcmp(a->idx.sha1, b->idx.sha1);\n+}\n+\n+\n union delta_base {\n \tunsigned char sha1[20];\n \toff_t offset;\n@@ -447,9 +456,10 @@ static void find_delta_children(const union delta_base *base,\n }\n \n static void sha1_object(const void *data, unsigned long size,\n-\t\t\tenum object_type type, unsigned char *sha1)\n+\t\t\tenum object_type type, unsigned char *sha1,\n+\t\t\tuint32_t *objcrc32p)\n {\n-\thash_sha1_file(data, size, typename(type), sha1);\n+\thash_sha1_file_extended(data, size, typename(type), sha1, objcrc32p);\n \tif (has_sha1_file(sha1)) {\n \t\tvoid *has_data;\n \t\tenum object_type has_type;\n@@ -549,7 +559,8 @@ static void resolve_delta(struct object_entry *delta_obj,\n \tif (!result->data)\n \t\tbad_object(delta_obj->idx.offset, \"failed to apply delta\");\n \tsha1_object(result->data, result->size, delta_obj->real_type,\n-\t\t delta_obj->idx.sha1);\n+\t\t delta_obj->idx.sha1, &(delta_obj->idx.objcrc32));\n+\tdelta_obj->idx.has_objcrc32 = 1;\n \tnr_resolved_deltas++;\n }\n \n@@ -643,8 +654,12 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\t\tnr_deltas++;\n \t\t\tdelta->obj_no = i;\n \t\t\tdelta++;\n-\t\t} else\n-\t\t\tsha1_object(data, obj->size, obj->type, obj->idx.sha1);\n+\t\t} else {\n+\t\t sha1_object(data, obj->size, obj->type, obj->idx.sha1,\n+\t\t\t &(obj->idx.objcrc32));\n+\t\t obj->idx.has_objcrc32 = 1;\n+\t\t}\n+\n \t\tfree(data);\n \t\tdisplay_progress(progress, i+1);\n \t}\n@@ -804,6 +819,7 @@ static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n \n static void final(const char *final_pack_name, const char *curr_pack_name,\n \t\t const char *final_index_name, const char *curr_index_name,\n+\t\t const char *final_mds_name, const char *curr_mds_name,\n \t\t const char *keep_name, const char *keep_msg,\n \t\t unsigned char *sha1)\n {\n@@ -866,6 +882,18 @@ static void final(const char *final_pack_name, const char *curr_pack_name,\n \t} else\n \t\tchmod(final_index_name, 0444);\n \n+\tif (final_mds_name != curr_mds_name) {\n+\t\tif (!final_mds_name) {\n+\t\t\tsnprintf(name, sizeof(name), \"%s/pack/pack-%s.mds\",\n+\t\t\t\t get_object_directory(), sha1_to_hex(sha1));\n+\t\t\tfinal_mds_name = name;\n+\t\t}\n+\t\tif (move_temp_to_file(curr_mds_name, final_mds_name))\n+\t\t\tdie(\"cannot store mds file\");\n+\t} else\n+\t\tchmod(final_mds_name, 0444);\n+\n+\n \tif (!from_stdin) {\n \t\tprintf(\"%s\\n\", sha1_to_hex(sha1));\n \t} else {\n@@ -972,18 +1000,46 @@ static void read_idx_option(struct pack_idx_option *opts, const char *pack_name)\n \tfree(p);\n }\n \n-static void show_pack_info(int stat_only)\n+static void show_pack_info(int stat, int stat_only, int show_mds,\n+\t\t\t int mds_file_exists, const char *path)\n {\n \tint i, baseobjects = nr_objects - nr_deltas;\n \tunsigned long *chain_histogram = NULL;\n+\tvoid *data = NULL;\n+\tsize_t mds_size = 0;\n+\tstruct packed_git pg;\n+\n+\tif (mds_file_exists) {\n+\t\tint fd = git_open_noatime(path);\n+\t\tsize_t required_size = 0;\n+\t\tstruct stat st;\n+\t\tif (fd >= 0) {\n+\t\t\tif (fstat(fd, &st)) {\n+\t\t\t\tclose(fd);\n+\t\t\t} else {\n+\t\t\t\tmds_size = xsize_t(st.st_size);\n+\t\t\t\tdata = xmmap(NULL, mds_size,\n+\t\t\t\t\t\tPROT_READ, MAP_PRIVATE, fd, 0);\n+\t\t\t\tclose(fd);\n+\t\t\t\trequired_size = required_git_packed_mds_size\n+\t\t\t\t\t(path, data, nr_objects, mds_size);\n+\t\t\t\tif (required_size == 0) {\n+\t\t\t\t\tmunmap(data, mds_size);\n+\t\t\t\t\tdata = NULL;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\t\tif (data == NULL) mds_file_exists = 0;\n+\t\tpg.mds_data = data;\n+\t}\n \n-\tif (deepest_delta)\n+\n+\tif (stat && deepest_delta)\n \t\tchain_histogram = xcalloc(deepest_delta, sizeof(unsigned long));\n \n \tfor (i = 0; i < nr_objects; i++) {\n \t\tstruct object_entry *obj = &objects[i];\n-\n-\t\tif (is_delta_type(obj->type))\n+\t\tif (chain_histogram && is_delta_type(obj->type))\n \t\t\tchain_histogram[obj->delta_depth - 1]++;\n \t\tif (stat_only)\n \t\t\tcontinue;\n@@ -992,12 +1048,40 @@ static void show_pack_info(int stat_only)\n \t\t typename(obj->real_type), obj->size,\n \t\t (unsigned long)(obj[1].idx.offset - obj->idx.offset),\n \t\t (uintmax_t)obj->idx.offset);\n+\t\tif (show_mds) {\n+\t\t\tif (mds_file_exists) {\n+\t\t\t\tuint32_t crc;\n+\t\t\t\tint has_crc = nth_packed_object_objcrc32\n+\t\t\t\t\t(&pg, i, &crc);\n+\t\t\t\tcrc = ntohl(crc);\n+\t\t\t\tif (has_crc) {\n+\t\t\t\t\tprintf(\" md=0x%8.8x\", crc);\n+\t\t\t\t\tif (obj->idx.has_objcrc32) {\n+\t\t\t\t\t\tuint32_t ecrc =\n+\t\t\t\t\t\t ntohl(obj->idx.objcrc32);\n+\t\t\t\t\t\tif (ecrc != crc) {\n+\t\t\t\t\t\t\tprintf(\" (should \"\n+\t\t\t\t\t\t\t \"be 0x%x) \",\n+\t\t\t\t\t\t\t ecrc);\n+\n+\t\t\t\t\t\t}\n+\t\t\t\t\t}\n+\t\t\t\t} else {\n+\t\t\t\t\tprintf(\" \");\n+\t\t\t\t}\n+\t\t\t} else {\n+\t\t\t\tprintf(\" \");\n+\t\t\t}\n+\t\t}\n \t\tif (is_delta_type(obj->type)) {\n \t\t\tstruct object_entry *bobj = &objects[obj->base_object_no];\n \t\t\tprintf(\" %u %s\", obj->delta_depth, sha1_to_hex(bobj->idx.sha1));\n \t\t}\n \t\tputchar('\\n');\n \t}\n+\tif (data) munmap(data, mds_size);\n+\tif (!stat)\n+\t\treturn;\n \n \tif (baseobjects)\n \t\tprintf(\"non delta: %d object%s\\n\",\n@@ -1015,10 +1099,12 @@ static void show_pack_info(int stat_only)\n int cmd_index_pack(int argc, const char **argv, const char *prefix)\n {\n \tint i, fix_thin_pack = 0, verify = 0, stat_only = 0, stat = 0;\n-\tconst char *curr_pack, *curr_index;\n-\tconst char *index_name = NULL, *pack_name = NULL;\n+\tint show_mds = 0;\n+\tconst char *curr_pack, *curr_index, *curr_mds;\n+\tconst char *index_name = NULL, *pack_name = NULL, *mds_name = NULL;;\n \tconst char *keep_name = NULL, *keep_msg = NULL;\n \tchar *index_name_buf = NULL, *keep_name_buf = NULL;\n+\tchar *mds_name_buf = NULL;\n \tstruct pack_idx_entry **idx_objects;\n \tstruct pack_idx_option opts;\n \tunsigned char pack_sha1[20];\n@@ -1052,6 +1138,10 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \t\t\t\tverify = 1;\n \t\t\t\tstat = 1;\n \t\t\t\tstat_only = 1;\n+\t\t\t} else if (!strcmp(arg, \"-M\") ||\n+\t\t\t\t !strcmp(arg, \"--show-mds\")) {\n+\t\t\t\tverify = 1;\n+\t\t\t\tshow_mds = 1;\n \t\t\t} else if (!strcmp(arg, \"--keep\")) {\n \t\t\t\tkeep_msg = \"\";\n \t\t\t} else if (!prefixcmp(arg, \"--keep=\")) {\n@@ -1075,6 +1165,10 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \t\t\t\tif (index_name || (i+1) >= argc)\n \t\t\t\t\tusage(index_pack_usage);\n \t\t\t\tindex_name = argv[++i];\n+\t\t\t} else if (!strcmp(arg, \"-m\")) {\n+\t\t\t\tif (mds_name || (i+1) >= argc)\n+\t\t\t\t\tusage(index_pack_usage);\n+\t\t\t\tmds_name = argv[++i];\n \t\t\t} else if (!prefixcmp(arg, \"--index-version=\")) {\n \t\t\t\tchar *c;\n \t\t\t\topts.version = strtoul(arg + 16, &c, 10);\n@@ -1108,6 +1202,16 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \t\tstrcpy(index_name_buf + len - 5, \".idx\");\n \t\tindex_name = index_name_buf;\n \t}\n+\tif (!mds_name && pack_name) {\n+\t\tint len = strlen(pack_name);\n+\t\tif (!has_extension(pack_name, \".pack\"))\n+\t\t\tdie(\"packfile name '%s' does not end with '.pack'\",\n+\t\t\t pack_name);\n+\t\tmds_name_buf = xmalloc(len);\n+\t\tmemcpy(mds_name_buf, pack_name, len - 5);\n+\t\tstrcpy(mds_name_buf + len - 5, \".mds\");\n+\t\tmds_name = mds_name_buf;\n+\t}\n \tif (keep_msg && !keep_name && pack_name) {\n \t\tint len = strlen(pack_name);\n \t\tif (!has_extension(pack_name, \".pack\"))\n@@ -1168,24 +1272,34 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \tif (strict)\n \t\tcheck_objects();\n \n-\tif (stat)\n-\t\tshow_pack_info(stat_only);\n+\tif (stat || show_mds) {\n+\t\tint mds_file_exists = !access(mds_name, R_OK);\n+\t\tif (mds_file_exists && show_mds) {\n+\t\t qsort (objects, nr_objects, sizeof (struct object_entry),\n+\t\t\t sha1_compare);\n+\t\t}\n+\t\tshow_pack_info(stat, stat_only, show_mds, mds_file_exists,\n+\t\t\t mds_name);\n+\t}\n \n \tidx_objects = xmalloc((nr_objects) * sizeof(struct pack_idx_entry *));\n \tfor (i = 0; i < nr_objects; i++)\n \t\tidx_objects[i] = &objects[i].idx;\n \tcurr_index = write_idx_file(index_name, idx_objects, nr_objects, &opts, pack_sha1);\n+\tcurr_mds = write_mds_file(mds_name, idx_objects, nr_objects, &opts,pack_sha1);\n \tfree(idx_objects);\n \n \tif (!verify)\n \t\tfinal(pack_name, curr_pack,\n \t\t index_name, curr_index,\n+\t\t mds_name, curr_mds,\n \t\t keep_name, keep_msg,\n \t\t pack_sha1);\n \telse\n \t\tclose(input_fd);\n \tfree(objects);\n \tfree(index_name_buf);\n+\tfree(mds_name_buf);\n \tfree(keep_name_buf);\n \tif (pack_name == NULL)\n \t\tfree((void *) curr_pack);\ndiff --git a/builtin/init-db.c b/builtin/init-db.c\nindex d07554c..9ff2e88 100644\n--- a/builtin/init-db.c\n+++ b/builtin/init-db.c\n@@ -7,6 +7,10 @@\n #include \"builtin.h\"\n #include \"exec_cmd.h\"\n #include \"parse-options.h\"\n+#include \"crcdb.h\"\n+#ifdef PACKDB\n+#include \"packdb.h\"\n+#endif\n \n #ifndef DEFAULT_GIT_TEMPLATE_DIR\n #define DEFAULT_GIT_TEMPLATE_DIR \"/usr/share/git-core/templates\"\n@@ -308,7 +312,18 @@ static void create_object_directory(void)\n \tsafe_create_dir(path, 1);\n \tstrcpy(path+len, \"/info\");\n \tsafe_create_dir(path, 1);\n-\n+#if (CRCDB == 0) || (CRCDB == 1)\n+\tstrcpy(path+len, \"/crcs\");\n+\tsafe_create_dir(path, 1);\n+#endif\n+\t/*\n+\t * In case the call in environent.c failed to initialize\n+\t * (missing directory?) or somehow wasn't called at all.\n+\t */\n+\tcrcdb_init();\n+#ifdef PACKDB\n+\tpackdb_init();\n+#endif\n \tfree(path);\n }\n \ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 824ecee..3ed1e71 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -17,6 +17,7 @@\n #include \"progress.h\"\n #include \"refs.h\"\n #include \"thread-utils.h\"\n+#include \"crcdb.h\"\n \n static const char pack_usage[] =\n \"git pack-objects [ -q | --progress | --all-progress ]\\n\"\n@@ -529,6 +530,8 @@ static struct object_entry **compute_write_order(void)\n \t\tobjects[i].filled = 0;\n \t\tobjects[i].delta_child = NULL;\n \t\tobjects[i].delta_sibling = NULL;\n+\t\tobjects[i].idx.has_objcrc32 = 0;\n+\t\tobjects[i].idx.objcrc32 = 0;\n \t}\n \n \t/*\n@@ -663,10 +666,13 @@ static void write_pack_file(void)\n \t\tif (!pack_to_stdout) {\n \t\t\tstruct stat st;\n \t\t\tconst char *idx_tmp_name;\n+\t\t\tconst char *mds_tmp_name;\n \t\t\tchar tmpname[PATH_MAX];\n \n \t\t\tidx_tmp_name = write_idx_file(NULL, written_list, nr_written,\n \t\t\t\t\t\t &pack_idx_opts, sha1);\n+\t\t\tmds_tmp_name = write_mds_file(NULL, written_list, nr_written,\n+\t\t\t\t\t\t &pack_idx_opts, sha1);\n \n \t\t\tsnprintf(tmpname, sizeof(tmpname), \"%s-%s.pack\",\n \t\t\t\t base_name, sha1_to_hex(sha1));\n@@ -704,7 +710,16 @@ static void write_pack_file(void)\n \t\t\tif (rename(idx_tmp_name, tmpname))\n \t\t\t\tdie_errno(\"unable to rename temporary index file\");\n \n+\t\t\tsnprintf(tmpname, sizeof(tmpname), \"%s-%s.mds\",\n+\t\t\t\t base_name, sha1_to_hex(sha1));\n+\t\t\tif (adjust_shared_perm(mds_tmp_name))\n+\t\t\t\tdie_errno(\"unable to make temporary mds file readable\");\n+\t\t\tif (rename(mds_tmp_name, tmpname))\n+\t\t\t\tdie_errno(\"unable to rename temporary mds file\");\n+\n+\n \t\t\tfree((void *) idx_tmp_name);\n+\t\t\tfree((void *) mds_tmp_name);\n \t\t\tfree(pack_tmp_name);\n \t\t\tputs(sha1_to_hex(sha1));\n \t\t}\n@@ -821,6 +836,8 @@ static int add_object_entry(const unsigned char *sha1, enum object_type type,\n \toff_t found_offset = 0;\n \tint ix;\n \tunsigned hash = name_hash(name);\n+\tint hasobjcrc32;\n+\tuint32_t objcrc32;\n \n \tix = nr_objects ? locate_object_entry_hash(sha1) : -1;\n \tif (ix >= 0) {\n@@ -837,7 +854,10 @@ static int add_object_entry(const unsigned char *sha1, enum object_type type,\n \t\treturn 0;\n \n \tfor (p = packed_git; p; p = p->next) {\n-\t\toff_t offset = find_pack_entry_one(sha1, p);\n+\t\thasobjcrc32 = 0;\n+\t\tobjcrc32 = 0;\n+\t\toff_t offset = find_pack_entry_one_extended(sha1, p,\n+\t\t\t\t\t\t &hasobjcrc32, &objcrc32);\n \t\tif (offset) {\n \t\t\tif (!found_pack) {\n \t\t\t\tif (!is_pack_valid(p)) {\n@@ -865,7 +885,37 @@ static int add_object_entry(const unsigned char *sha1, enum object_type type,\n \n \tentry = objects + nr_objects++;\n \tmemset(entry, 0, sizeof(*entry));\n+\tif (hasobjcrc32 == 0) {\n+\t\t/*\n+\t\t * We pick up CRCs for local objects (we already checked the\n+\t\t * pack files). If that doesn't work, we compute it from\n+\t\t * scratch (which should occur rarely if at all).\n+\t\t */\n+\t\tcrcdb_open(NULL);\n+\t\tswitch (crcdb_lookup(NULL, sha1, &objcrc32)) {\n+\t\tcase 1:\n+\t\t\thasobjcrc32 = 1;\n+\t\t\tbreak;\n+\t\tdefault:\n+\t\t\thasobjcrc32 = 0;\n+\t\t}\n+\t\tcrcdb_close(NULL);\n+\t\tif (!hasobjcrc32) {\n+\t\t enum object_type type;\n+\t\t unsigned long size;\n+\t\t unsigned char sbuf[20];\n+\t\t void *buf = read_sha1_file(sha1, &type, &size);\n+\t\t if (buf) {\n+\t\t\tconst char *stype = typename(type);\n+\t\t\thash_sha1_file_extended(buf, size, stype, sbuf,\n+\t\t\t\t\t\t&objcrc32);\n+\t\t\thasobjcrc32 = 1;\n+\t\t }\n+\t\t}\n+\t}\n \thashcpy(entry->idx.sha1, sha1);\n+\tentry->idx.has_objcrc32 = hasobjcrc32;\n+\tentry->idx.objcrc32 = objcrc32;\n \tentry->hash = hash;\n \tif (type)\n \t\tentry->type = type;\n@@ -2148,7 +2198,8 @@ struct in_pack {\n \n static void mark_in_pack_object(struct object *object, struct packed_git *p, struct in_pack *in_pack)\n {\n-\tin_pack->array[in_pack->nr].offset = find_pack_entry_one(object->sha1, p);\n+\tin_pack->array[in_pack->nr].offset =\n+\t\tfind_pack_entry_one(object->sha1, p);\n \tin_pack->array[in_pack->nr].object = object;\n \tin_pack->nr++;\n }\n@@ -2220,7 +2271,7 @@ static int has_sha1_pack_kept_or_nonlocal(const unsigned char *sha1)\n \n \twhile (p) {\n \t\tif ((!p->pack_local || p->pack_keep) &&\n-\t\t\tfind_pack_entry_one(sha1, p)) {\n+\t\t find_pack_entry_one(sha1, p)) {\n \t\t\tlast_found = p;\n \t\t\treturn 1;\n \t\t}\ndiff --git a/builtin/pack-redundant.c b/builtin/pack-redundant.c\nindex f5c6afc..c09397c 100644\n--- a/builtin/pack-redundant.c\n+++ b/builtin/pack-redundant.c\n@@ -6,6 +6,7 @@\n *\n */\n \n+#include \n #include \"builtin.h\"\n \n #define BLKSIZE 512\n@@ -682,9 +683,16 @@ int cmd_pack_redundant(int argc, const char **argv, const char *prefix)\n \t}\n \tpl = red = pack_list_difference(local_packs, min);\n \twhile (pl) {\n-\t\tprintf(\"%s\\n%s\\n\",\n-\t\t sha1_pack_index_name(pl->pack->sha1),\n-\t\t pl->pack->pack_name);\n+\t\tchar *mdsfile = sha1_pack_mds_name(pl->pack->sha1);\n+\t\tif (!access(mdsfile, F_OK)) {\n+\t\t printf(\"%s\\n%s\\n%s\\n\", mdsfile,\n+\t\t\t sha1_pack_index_name(pl->pack->sha1),\n+\t\t\t pl->pack->pack_name);\n+\t\t} else {\n+\t\t\tprintf(\"%s\\n%s\\n\",\n+\t\t\t sha1_pack_index_name(pl->pack->sha1),\n+\t\t\t pl->pack->pack_name);\n+\t\t}\n \t\tpl = pl->next;\n \t}\n \tif (verbose)\ndiff --git a/builtin/prune-packed.c b/builtin/prune-packed.c\nindex f9463de..5c682dd 100644\n--- a/builtin/prune-packed.c\n+++ b/builtin/prune-packed.c\n@@ -43,8 +43,11 @@ void prune_packed_objects(int opts)\n {\n \tint i;\n \tstatic char pathname[PATH_MAX];\n+\tstatic char mds_pathname[PATH_MAX];\n \tconst char *dir = get_object_directory();\n+\tconst char *mdsdir = get_object_crc_node();\n \tint len = strlen(dir);\n+\tint mdslen = strlen(mdsdir);\n \n \tif (opts == VERBOSE)\n \t\tprogress = start_progress_delay(\"Removing duplicate objects\",\n@@ -55,16 +58,26 @@ void prune_packed_objects(int opts)\n \tmemcpy(pathname, dir, len);\n \tif (len && pathname[len-1] != '/')\n \t\tpathname[len++] = '/';\n+\tmemcpy(mds_pathname, mdsdir, mdslen);\n+\tif (mdslen && mds_pathname[mdslen-1] != '/')\n+\t\tmds_pathname[mdslen++] = '/';\n \tfor (i = 0; i < 256; i++) {\n \t\tDIR *d;\n+\t\tDIR *mds_d;\n \n \t\tdisplay_progress(progress, i + 1);\n \t\tsprintf(pathname + len, \"%02x/\", i);\n \t\td = opendir(pathname);\n-\t\tif (!d)\n-\t\t\tcontinue;\n-\t\tprune_dir(i, d, pathname, len + 3, opts);\n-\t\tclosedir(d);\n+\t\tsprintf(mds_pathname + len, \"%02x/\", i);\n+\t\tmds_d = opendir(mds_pathname);\n+\t\tif (d) {\n+\t\t\tprune_dir(i, d, pathname, len + 3, opts);\n+\t\t\tclosedir(d);\n+\t\t}\n+\t\tif (mds_d) {\n+\t\t\tprune_dir(i, mds_d, mds_pathname, mdslen + 3, opts);\n+\t\t\tclosedir(mds_d);\n+\t\t}\n \t}\n \tstop_progress(&progress);\n }\ndiff --git a/builtin/prune.c b/builtin/prune.c\nindex e65690b..e9fbc99 100644\n--- a/builtin/prune.c\n+++ b/builtin/prune.c\n@@ -154,6 +154,7 @@ int cmd_prune(int argc, const char **argv, const char *prefix)\n \t}\n \tmark_reachable_objects(&revs, 1);\n \tprune_object_dir(get_object_directory());\n+\tprune_object_dir(get_object_crc_node());\n \n \tprune_packed_objects(show_only);\n \tremove_temporary_files(get_object_directory());\ndiff --git a/builtin/receive-pack.c b/builtin/receive-pack.c\nindex 7ec68a1..a7b6474 100644\n--- a/builtin/receive-pack.c\n+++ b/builtin/receive-pack.c\n@@ -121,7 +121,8 @@ static int show_ref(const char *path, const unsigned char *sha1, int flag, void\n \telse\n \t\tpacket_write(1, \"%s %s%c%s%s\\n\",\n \t\t\t sha1_to_hex(sha1), path, 0,\n-\t\t\t \" report-status delete-refs side-band-64k\",\n+\t\t\t \" report-status delete-refs side-band-64k\"\n+\t\t\t \" mds-check\",\n \t\t\t prefer_ofs_delta ? \" ofs-delta\" : \"\");\n \tsent_capabilities = 1;\n \treturn 0;\n@@ -712,32 +713,128 @@ static struct command *read_head_info(void)\n \t\tstruct command *cmd;\n \t\tchar *refname;\n \t\tint len, reflen;\n+\t\tint has_old_sha1_crc = 0;\n+\t\tint has_new_sha1_crc = 0;\n+\t\tint has_old_blob_crc = 0;\n+\t\tint has_new_blob_crc = 0;\n+\t\tuint32_t old_sha1_crc = 0;\n+\t\tuint32_t new_sha1_crc = 0;\n+\t\tuint32_t new_blob_crc = 0;\n+\t\tuint32_t old_blob_crc = 0;\n+\t\tuint32_t objcrc32;\n+\t\tint old_hashlen = 40;\n+\t\tint new_hashlen = 40;\n+\t\tint hashlen = 80;\n+\t\tstatic const int crc_field_len = 9;\n \n \t\tlen = packet_read_line(0, line, sizeof(line));\n \t\tif (!len)\n \t\t\tbreak;\n \t\tif (line[len-1] == '\\n')\n \t\t\tline[--len] = 0;\n-\t\tif (len < 83 ||\n-\t\t line[40] != ' ' ||\n-\t\t line[81] != ' ' ||\n-\t\t get_sha1_hex(line, old_sha1) ||\n-\t\t get_sha1_hex(line + 41, new_sha1))\n+\t\tif (len > (old_hashlen + crc_field_len) &&\n+\t\t line[old_hashlen] == '-') {\n+\t\t\told_hashlen += crc_field_len;\n+\t\t\thashlen += crc_field_len;\n+\t\t}\n+\t\tif (len > (old_hashlen + crc_field_len) &&\n+\t\t line[old_hashlen] == '-') {\n+\t\t\told_hashlen += crc_field_len;\n+\t\t\thashlen += crc_field_len;\n+\t\t}\n+\t\tif (len > (hashlen + crc_field_len + 1) &&\n+\t\t line[hashlen+1] == '-') {\n+\t\t\tnew_hashlen += crc_field_len;\n+\t\t\thashlen += crc_field_len;\n+\t\t}\n+\t\tif (len > (hashlen + crc_field_len + 1) &&\n+\t\t line[hashlen+1] == '-') {\n+\t\t\tnew_hashlen += crc_field_len;\n+\t\t\thashlen += crc_field_len;\n+\t\t}\n+\n+\t\tif (old_hashlen != 40 && old_hashlen != 49\n+\t\t && old_hashlen != 58) {\n+\t\t\tdie(\"protocol error: expected old/new/ref, got '%s'\",\n+\t\t\t line);\n+\t\t}\n+\n+\t\tif (new_hashlen != 40 && new_hashlen != 49 &&\n+\t\t new_hashlen != 58) {\n+\t\t\tdie(\"protocol error: expected old/new/ref, got '%s'\",\n+\t\t\t line);\n+\t\t}\n+\n+\t\tif (len < hashlen + 3 ||\n+\t\t line[old_hashlen] != ' ' ||\n+\t\t line[hashlen + 1] != ' ' ||\n+\t\t get_sha1_hex_crc(line, old_sha1,\n+\t\t\t\t &has_old_sha1_crc, &old_sha1_crc,\n+\t\t\t\t &has_old_blob_crc,\n+\t\t\t\t &old_blob_crc) ||\n+\t\t get_sha1_hex_crc(line + old_hashlen + 1, new_sha1,\n+\t\t\t\t &has_new_sha1_crc, &new_sha1_crc,\n+\t\t\t\t &has_new_blob_crc,\n+\t\t\t\t &new_blob_crc))\n \t\t\tdie(\"protocol error: expected old/new/ref, got '%s'\",\n \t\t\t line);\n \n-\t\trefname = line + 82;\n+\t\tif (has_old_sha1_crc &&\n+\t\t has_sha1_file_crc(old_sha1, &objcrc32)) {\n+\t\t\tif (old_sha1_crc != objcrc32) {\n+\t\t\t\tdie(\"hash collision for %s\",\n+\t\t\t\t sha1_to_hex(old_sha1));\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (has_old_sha1_crc && has_old_blob_crc) {\n+\t\t\tuint32_t blobcrc;\n+\t\t\tint has_blob_crc = !get_blob_mds(old_sha1, &blobcrc);\n+\t\t\tif (has_blob_crc) {\n+\t\t\t\tif (old_blob_crc != blobcrc)\n+\t\t\t\t\tdie(\"hash collision for %s\",\n+\t\t\t\t\t sha1_to_hex(old_sha1));\n+\t\t\t} else {\n+#ifdef BLOB_MDS_CHECK\n+\t\t\t\tpush_mds_check(old_sha1, old_blob_crc);\n+#endif\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (has_new_sha1_crc &&\n+\t\t has_sha1_file_crc(new_sha1, &objcrc32)) {\n+\t\t\tif (new_sha1_crc != objcrc32) {\n+\t\t\t\tdie(\"hash collision for %s\",\n+\t\t\t\t sha1_to_hex(new_sha1));\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (has_new_sha1_crc && has_new_blob_crc) {\n+\t\t\tuint32_t blobcrc;\n+\t\t\tint has_blob_crc = !get_blob_mds(new_sha1, &blobcrc);\n+\t\t\tif (has_blob_crc) {\n+\t\t\t\tif (new_blob_crc != blobcrc)\n+\t\t\t\t\tdie(\"hash collision for %s\",\n+\t\t\t\t\t sha1_to_hex(new_sha1));\n+\t\t\t} else {\n+#ifdef BLOB_MDS_CHECK\n+\t\t\t\tpush_mds_check(new_sha1, new_blob_crc);\n+#endif\n+\t\t\t}\n+\t\t}\n+\n+\t\trefname = line + hashlen + 2;\n \t\treflen = strlen(refname);\n-\t\tif (reflen + 82 < len) {\n+\t\tif (reflen + hashlen + 2 < len) {\n \t\t\tif (strstr(refname + reflen + 1, \"report-status\"))\n \t\t\t\treport_status = 1;\n \t\t\tif (strstr(refname + reflen + 1, \"side-band-64k\"))\n \t\t\t\tuse_sideband = LARGE_PACKET_MAX;\n \t\t}\n-\t\tcmd = xcalloc(1, sizeof(struct command) + len - 80);\n+\t\tcmd = xcalloc(1, sizeof(struct command) + len - hashlen);\n \t\thashcpy(cmd->old_sha1, old_sha1);\n \t\thashcpy(cmd->new_sha1, new_sha1);\n-\t\tmemcpy(cmd->ref_name, line + 82, len - 81);\n+\t\tmemcpy(cmd->ref_name, line + hashlen + 2, len - (hashlen +1));\n \t\t*p = cmd;\n \t\tp = &cmd->next;\n \t}\n@@ -966,6 +1063,9 @@ int cmd_receive_pack(int argc, const char **argv, const char *prefix)\n \t\tif (auto_update_server_info)\n \t\t\tupdate_server_info(0);\n \t}\n+#ifdef BLOB_MDS_CHECK\n+\tprocess_mds_checks(rp_warning);\n+#endif\n \tif (use_sideband)\n \t\tpacket_flush(1);\n \treturn 0;\ndiff --git a/builtin/send-pack.c b/builtin/send-pack.c\nindex e0b8030..a3ce108 100644\n--- a/builtin/send-pack.c\n+++ b/builtin/send-pack.c\n@@ -250,6 +250,7 @@ int send_pack(struct send_pack_args *args,\n \tint allow_deleting_refs = 0;\n \tint status_report = 0;\n \tint use_sideband = 0;\n+\tint mds_check = 0;\n \tunsigned cmds_sent = 0;\n \tint ret;\n \tstruct async demux;\n@@ -263,6 +264,8 @@ int send_pack(struct send_pack_args *args,\n \t\targs->use_ofs_delta = 1;\n \tif (server_supports(\"side-band-64k\"))\n \t\tuse_sideband = 1;\n+\tif (server_supports(\"mds-check\"))\n+\t\tmds_check = 1;\n \n \tif (!remote_refs) {\n \t\tfprintf(stderr, \"No refs in common and none specified; doing nothing.\\n\"\n@@ -298,8 +301,46 @@ int send_pack(struct send_pack_args *args,\n \t\tif (args->dry_run) {\n \t\t\tref->status = REF_STATUS_OK;\n \t\t} else {\n-\t\t\tchar *old_hex = sha1_to_hex(ref->old_sha1);\n-\t\t\tchar *new_hex = sha1_to_hex(ref->new_sha1);\n+\t\t\tchar *old_hex, *new_hex;\n+\t\t\tif (mds_check) {\n+\t\t\t\tuint32_t objcrc32;\n+\t\t\t\tuint32_t blobcrc;\n+\t\t\t\tif (has_sha1_file_crc(ref->old_sha1,\n+\t\t\t\t\t\t &objcrc32)) {\n+\t\t\t\t\tif (get_blob_mds(ref->old_sha1,\n+\t\t\t\t\t\t\t &blobcrc)) {\n+\t\t\t\t\t\told_hex =\n+\t\t\t\t\t\t sha1_to_hex_crc(ref->old_sha1,\n+\t\t\t\t\t\t\t\t objcrc32);\n+\t\t\t\t\t} else {\n+\t\t\t\t\t\told_hex =\n+\t\t\t\t\t\t sha1_to_hex_crc2\n+\t\t\t\t\t\t (ref->old_sha1, objcrc32,\n+\t\t\t\t\t\t blobcrc);\n+\t\t\t\t\t}\n+\t\t\t\t} else {\n+\t\t\t\t\told_hex = sha1_to_hex(ref->old_sha1);\n+\t\t\t\t}\n+\t\t\t\tif (has_sha1_file_crc(ref->new_sha1,\n+\t\t\t\t\t\t &objcrc32)) {\n+\t\t\t\t\tif (get_blob_mds(ref->new_sha1,\n+\t\t\t\t\t\t &objcrc32)) {\n+\t\t\t\t\t\tnew_hex =\n+\t\t\t\t\t\t sha1_to_hex_crc(ref->new_sha1,\n+\t\t\t\t\t\t\t\t objcrc32);\n+\t\t\t\t\t} else {\n+\t\t\t\t\t\tnew_hex =\n+\t\t\t\t\t\t sha1_to_hex_crc2\n+\t\t\t\t\t\t (ref->new_sha1, objcrc32,\n+\t\t\t\t\t\t blobcrc);\n+\t\t\t\t\t}\n+\t\t\t\t} else {\n+\t\t\t\t\tnew_hex = sha1_to_hex(ref->new_sha1);\n+\t\t\t\t}\n+\t\t\t} else {\n+\t\t\t\told_hex = sha1_to_hex(ref->old_sha1);\n+\t\t\t\tnew_hex = sha1_to_hex(ref->new_sha1);\n+\t\t\t}\n \n \t\t\tif (!cmds_sent && (status_report || use_sideband)) {\n \t\t\t\tpacket_buf_write(&req_buf, \"%s %s %s%c%s%s\",\ndiff --git a/builtin/verify-pack.c b/builtin/verify-pack.c\nindex e841b4a..b94a11e 100644\n--- a/builtin/verify-pack.c\n+++ b/builtin/verify-pack.c\n@@ -5,14 +5,16 @@\n \n #define VERIFY_PACK_VERBOSE 01\n #define VERIFY_PACK_STAT_ONLY 02\n+#define SHOW_MDS 04\n \n static int verify_one_pack(const char *path, unsigned int flags)\n {\n \tstruct child_process index_pack;\n-\tconst char *argv[] = {\"index-pack\", NULL, NULL, NULL };\n+\tconst char *argv[] = {\"index-pack\", NULL, NULL, NULL, NULL };\n \tstruct strbuf arg = STRBUF_INIT;\n \tint verbose = flags & VERIFY_PACK_VERBOSE;\n \tint stat_only = flags & VERIFY_PACK_STAT_ONLY;\n+\tint show_mds = ((flags & SHOW_MDS) != 0) && !stat_only;\n \tint err;\n \n \tif (stat_only)\n@@ -22,6 +24,8 @@ static int verify_one_pack(const char *path, unsigned int flags)\n \telse\n \t\targv[1] = \"--verify\";\n \n+\tif (show_mds) argv[2] = \"-M\";\n+\n \t/*\n \t * In addition to \"foo.pack\" we accept \"foo.idx\" and \"foo\";\n \t * normalize these forms to \"foo.pack\" for \"index-pack --verify\".\n@@ -31,7 +35,7 @@ static int verify_one_pack(const char *path, unsigned int flags)\n \t\tstrbuf_splice(&arg, arg.len - 3, 3, \"pack\", 4);\n \telse if (!has_extension(arg.buf, \".pack\"))\n \t\tstrbuf_add(&arg, \".pack\", 5);\n-\targv[2] = arg.buf;\n+\targv[2 + show_mds] = arg.buf;\n \n \tmemset(&index_pack, 0, sizeof(index_pack));\n \tindex_pack.argv = argv;\n@@ -46,6 +50,10 @@ static int verify_one_pack(const char *path, unsigned int flags)\n \t\t\tif (!stat_only)\n \t\t\t\tprintf(\"%s: ok\\n\", arg.buf);\n \t\t}\n+\t} else if (show_mds) {\n+\t\tprintf(\"%s: listed (%s)\\n-----------------\\n\", arg.buf,\n+\t\t (err? \"bad\": \"ok\"));\n+\n \t}\n \tstrbuf_release(&arg);\n \n@@ -67,6 +75,8 @@ int cmd_verify_pack(int argc, const char **argv, const char *prefix)\n \t\t\tVERIFY_PACK_VERBOSE),\n \t\tOPT_BIT('s', \"stat-only\", &flags, \"show statistics only\",\n \t\t\tVERIFY_PACK_STAT_ONLY),\n+\t\tOPT_BIT('M', \"show-mds\", &flags, \"show message digests / CRCs\",\n+\t\t\tSHOW_MDS),\n \t\tOPT_END()\n \t};\n \ndiff --git a/cache.h b/cache.h\nindex 2e6ad36..85ecff2 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -433,6 +433,10 @@ extern int is_inside_work_tree(void);\n extern int have_git_dir(void);\n extern const char *get_git_dir(void);\n extern char *get_object_directory(void);\n+extern char *get_object_crc_node(void);\n+#ifdef PACKDB\n+extern char *get_object_packdb_node(void);\n+#endif\n extern char *get_index_file(void);\n extern char *get_graft_file(void);\n extern int set_git_dir(const char *path);\n@@ -541,8 +545,15 @@ extern int ce_path_match(const struct cache_entry *ce, const struct pathspec *pa\n \n #define HASH_WRITE_OBJECT 1\n #define HASH_FORMAT_CHECK 2\n-extern int index_fd(unsigned char *sha1, int fd, struct stat *st, enum object_type type, const char *path, unsigned flags);\n-extern int index_path(unsigned char *sha1, const char *path, struct stat *st, unsigned flags);\n+\n+#define index_fd(sha1,fd,st,type,path,flags)\t\t\t\\\n+\tindex_fd_extended((sha1), NULL, (fd), (st), (type), (path), (flags))\n+extern int index_fd_extended(unsigned char *sha1, uint32_t *objcrc32p, int fd, struct stat *st, enum object_type type, const char *path, unsigned flags);\n+\n+#define index_path(sha1, path, st, flags) \\\n+\tindex_path_extended((sha1), NULL, (path), (st), (flags))\n+extern int index_path_extended(unsigned char *sha1, uint32_t *objcrc32p, const char *path\n+, struct stat *st, unsigned flags);\n extern void fill_stat_cache_info(struct cache_entry *ce, struct stat *st);\n \n #define REFRESH_REALLY\t\t0x0001\t/* ignore_valid */\n@@ -669,6 +680,7 @@ extern char *git_path_submodule(const char *path, const char *fmt, ...)\n extern char *sha1_file_name(const unsigned char *sha1);\n extern char *sha1_pack_name(const unsigned char *sha1);\n extern char *sha1_pack_index_name(const unsigned char *sha1);\n+extern char *sha1_pack_mds_name(const unsigned char *sha1);\n extern const char *find_unique_abbrev(const unsigned char *sha1, int);\n extern const unsigned char null_sha1[20];\n \n@@ -768,9 +780,18 @@ static inline const unsigned char *lookup_replace_object(const unsigned char *sh\n \n /* Read and unpack a sha1 file into memory, write memory to a sha1 file */\n extern int sha1_object_info(const unsigned char *, unsigned long *);\n-extern int hash_sha1_file(const void *buf, unsigned long len, const char *type, unsigned char *sha1);\n-extern int write_sha1_file(const void *buf, unsigned long len, const char *type, unsigned char *return_sha1);\n-extern int pretend_sha1_file(void *, unsigned long, enum object_type, unsigned char *);\n+\n+#define hash_sha1_file(buf,len,type,sha1) \\\n+\thash_sha1_file_extended((buf), (len), (type), (sha1), NULL)\n+extern int hash_sha1_file_extended(const void *buf, unsigned long len, const char *type, unsigned char *sha1, uint32_t *objcrc32p);\n+\n+#define write_sha1_file(buf,len,type,return_sha1) \\\n+\twrite_sha1_file_extended((buf), (len), (type), (return_sha1), NULL)\n+extern int write_sha1_file_extended(const void *buf, unsigned long len, const char *type, unsigned char *return_sha1, uint32_t *objcrc32p);\n+\n+#define pretend_sha1_file(buf,len,type,sha1) \\\n+\tpretend_sha1_file_extended((buf), (len), (type), (sha1), NULL)\n+extern int pretend_sha1_file_extended(void *, unsigned long, enum object_type, unsigned char *, uint32_t *objcrc32p);\n extern int force_object_loose(const unsigned char *sha1, time_t mtime);\n extern void *map_sha1_file(const unsigned char *sha1, unsigned long *size);\n extern int unpack_sha1_header(git_zstream *stream, unsigned char *map, unsigned long mapsize, void *buffer, unsigned long bufsiz);\n@@ -782,13 +803,17 @@ extern int do_check_packed_object_crc;\n /* for development: log offset of pack access */\n extern const char *log_pack_access;\n \n-extern int check_sha1_signature(const unsigned char *sha1, void *buf, unsigned long size, const char *type);\n+#define check_sha1_signature(sha1,buf,size,type) \\\n+\tcheck_sha1_signature_extended((sha1), NULL, (buf), (size), (type))\n+extern int check_sha1_signature_extended(const unsigned char *sha1, uint32_t *objcrc32p, void *buf, unsigned long size, const char *type);\n \n extern int move_temp_to_file(const char *tmpfile, const char *filename);\n \n extern int has_sha1_pack(const unsigned char *sha1);\n extern int has_sha1_file(const unsigned char *sha1);\n+extern int has_sha1_file_crc(const unsigned char *sha1, uint32_t *objcrc32p);\n extern int has_loose_object_nonlocal(const unsigned char *sha1);\n+extern int has_loose_object_nonlocal_crc(const unsigned char *sha1, uint32_t *objcrc32p);\n \n extern int has_pack_index(const unsigned char *sha1);\n \n@@ -830,8 +855,12 @@ static inline int get_sha1_with_context(const char *str, unsigned char *sha1, st\n * null-terminated string.\n */\n extern int get_sha1_hex(const char *hex, unsigned char *sha1);\n+extern int get_sha1_hex_crc(const char *hex, unsigned char *sha1, int *hascrc, uint32_t *crc, int *hasblobmdsp, uint32_t *blobmdsp);\n \n extern char *sha1_to_hex(const unsigned char *sha1);\t/* static buffer result! */\n+extern char *sha1_to_hex_crc(const unsigned char *sha1, const uint32_t objcrc);\t/* static buffer result! */\n+extern char *sha1_to_hex_crc2(const unsigned char *sha1, const uint32_t objcrc,\n+\t\t\t const uint32_t blobcrc);\t/* static buffer result! */\n extern int read_ref(const char *filename, unsigned char *sha1);\n \n /*\n@@ -974,10 +1003,13 @@ extern struct packed_git {\n \toff_t pack_size;\n \tconst void *index_data;\n \tsize_t index_size;\n+\tconst void *mds_data; /*objcrc32 table*/\n+\tsize_t mds_size;\n \tuint32_t num_objects;\n \tuint32_t num_bad_objects;\n \tunsigned char *bad_object_sha1;\n \tint index_version;\n+\tint mds_version;\n \ttime_t mtime;\n \tint pack_fd;\n \tunsigned pack_local:1,\n@@ -992,6 +1024,8 @@ struct pack_entry {\n \toff_t offset;\n \tunsigned char sha1[20];\n \tstruct packed_git *p;\n+\tint has_objcrc32;\n+\tuint32_t objcrc32;\n };\n \n struct ref {\n@@ -1047,6 +1081,11 @@ extern struct packed_git *find_sha1_pack(const unsigned char *sha1,\n \n extern void pack_report(void);\n extern int open_pack_index(struct packed_git *);\n+extern int open_pack_mds(struct packed_git *p);\n+extern int git_open_noatime(const char *name);\n+extern size_t required_git_packed_mds_size(const char *path,\n+\t\t\t\t\t void *data, uint32_t nobjects,\n+\t\t\t\t\t size_t actual_size);\n extern void close_pack_index(struct packed_git *);\n extern unsigned char *use_pack(struct packed_git *, struct pack_window **, off_t, unsigned long *);\n extern void close_pack_windows(struct packed_git *);\n@@ -1055,8 +1094,16 @@ extern void free_pack_by_name(const char *);\n extern void clear_delta_base_cache(void);\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 int nth_packed_object_objcrc32(const struct packed_git *p, uint32_t n,\n+\t\t\t\t uint32_t *objcrc32p);\n extern off_t nth_packed_object_offset(const struct packed_git *, uint32_t);\n-extern off_t find_pack_entry_one(const unsigned char *, struct packed_git *);\n+\n+#define find_pack_entry_one(sha1,p) find_pack_entry_one_extended((sha1),(p), NULL, NULL)\n+extern off_t find_pack_entry_one_extended(const unsigned char *,\n+\t\t\t\t\t struct packed_git *,\n+\t\t\t\t\t int *hasojb32crcp,\n+\t\t\t\t\t uint32_t *objcrc32p);\n+\n extern int is_pack_valid(struct packed_git *);\n extern void *unpack_entry(struct packed_git *, off_t, enum object_type *, unsigned long *);\n extern unsigned long unpack_object_header_buffer(const unsigned char *buf, unsigned long len, enum object_type *type, unsigned long *sizep);\ndiff --git a/commit.c b/commit.c\nindex 73b7e00..815f4a0 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -11,6 +11,115 @@ int save_commit_buffer = 1;\n \n const char *commit_type = \"commit\";\n \n+struct blob_mds_context {\n+ unsigned long missing;\n+ uint32_t crc;\n+};\n+\n+static int get_blob_mds_f(const unsigned char *sha1,\n+\t\t\t const char *basebuf, int baselen,\n+\t\t\t const char *path, unsigned int mode, int stage,\n+\t\t\t void *context)\n+{\n+\tstruct blob_mds_context *c = (struct blob_mds_context *)context;\n+\tuint32_t crc;\n+\tunsigned long size;\n+\tint type;\n+\n+\tif (!has_sha1_file(sha1)) {\n+\t\tc->missing++;\n+\t\treturn -1;\n+\t}\n+\ttype = sha1_object_info(sha1, &size);\n+\tswitch(type) {\n+\tcase OBJ_TREE:\n+\t return ((mode) == 0040000)? READ_TREE_RECURSIVE: 0;\n+\tcase OBJ_BLOB:\n+\t\tif (has_sha1_file_crc(sha1, &crc)) {\n+\t\t\tcrc = ntohl(crc);\n+\t\t\tc->crc = crc32(c->crc, (unsigned char *)&crc,\n+\t\t\t\t\t sizeof (uint32_t));\n+\t\t} else {\n+\t\t\tc->missing++;\n+\t\t}\n+\t\treturn 0;\n+\tdefault:\n+\t\tif (type <= OBJ_NONE) {\n+\t\t c->missing++;\n+\t\t}\n+\t\treturn 0;\n+\t}\n+}\n+\n+/*\n+ * Works with a tree or a commit sha1 - recursively traverses the trees\n+ * and computes the CRC of each blob's CRC.\n+ */\n+int get_blob_mds(const unsigned char *sha1, uint32_t *blobcrcp)\n+{\n+\tstruct blob_mds_context context;\n+\tcontext.crc = crc32(0, NULL, 0);\n+\tcontext.missing = 0;\n+\tstruct tree *tree = parse_tree_indirect(sha1);\n+\tstruct pathspec ps;\n+\tif (tree == NULL) {\n+\t\treturn -1;\n+\t} else {\n+\t\tinit_pathspec(&ps, NULL);\n+\t\tparse_tree(tree);\n+\t\tread_tree_recursive(tree, \"\", 0, 0, &ps, get_blob_mds_f,\n+\t\t\t\t &context);\n+\t\tif (blobcrcp) (*blobcrcp) = htonl(context.crc);\n+\t\treturn ((context.missing == 0)? 0: -1);\n+\t}\n+}\n+\n+#ifdef BLOB_MDS_CHECK\n+/*\n+ * Used to check the values returned by get_mds_blob in cases involving\n+ * a transfer protocol where a commit is transferred and processed\n+ * before all of the objects associated with it are accessible.\n+ */\n+\n+struct mds_check {\n+ struct mds_check *next;\n+ unsigned char sha1[20];\n+ uint32_t blobcrc;\n+} *mds_check_list = NULL;\n+\n+void push_mds_check(unsigned char *sha1, uint32_t crc) {\n+\tstruct mds_check *ptr = (struct mds_check *)\n+\t xmalloc(sizeof (struct mds_check));\n+\thashcpy(ptr->sha1, sha1);\n+\tptr->blobcrc = crc;\n+\tptr->next = mds_check_list;\n+\tmds_check_list = ptr;\n+}\n+\n+/*\n+ * Must be called after the uploaded data is entered in the repository -\n+ * otherwise we won't be able to get the CRCs needed by get_blob_mds,\n+ * which will result in get_blob_mds returning -1 instead of 0.\n+ */\n+\n+void process_mds_checks(rp_warning_f rp_warning) {\n+\twhile (mds_check_list) {\n+\t\tuint32_t sha1_blobcrc;\n+\t\tint has_sha1_blobcrc = !get_blob_mds(mds_check_list->sha1,\n+\t\t\t\t\t\t &sha1_blobcrc);\n+\t\tif (has_sha1_blobcrc &&\n+\t\t mds_check_list->blobcrc != sha1_blobcrc) {\n+\t\t\trp_warning(\"hash collision for %s\",\n+\t\t\t\t sha1_to_hex(mds_check_list->sha1));\n+\t\t}\n+\t\tmds_check_list = mds_check_list->next;\n+\t}\n+}\n+\n+#endif /* BLOB_MDS_CHECK */\n+\n+\n+\n static struct commit *check_commit(struct object *obj,\n \t\t\t\t const unsigned char *sha1,\n \t\t\t\t int quiet)\ndiff --git a/commit.h b/commit.h\nindex 009b113..65f2bd5 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -185,4 +185,12 @@ extern int commit_tree(const char *msg, unsigned char *tree,\n \t\tstruct commit_list *parents, unsigned char *ret,\n \t\tconst char *author);\n \n+extern int get_blob_mds(const unsigned char *sha1, uint32_t *blobcrcp);\n+\n+#ifdef BLOB_MDS_CHECK\n+extern void push_mds_check(unsigned char *sha1, uint32_t crc);\n+typedef void (*rp_warning_f)(const char *err, ...) __attribute__((format (printf, 1, 2))\n+);\n+extern void process_mds_checks(rp_warning_f rp_warning);\n+#endif /* BLOB_MDS_CHECK */\n #endif /* COMMIT_H */\ndiff --git a/environment.c b/environment.c\nindex 0bee6a7..8a45c82 100644\n--- a/environment.c\n+++ b/environment.c\n@@ -9,6 +9,10 @@\n */\n #include \"cache.h\"\n #include \"refs.h\"\n+#include \"crcdb.h\"\n+#ifdef PACKDB\n+#include \"packdb.h\"\n+#endif\n \n char git_default_email[MAX_GITNAME];\n char git_default_name[MAX_GITNAME];\n@@ -73,7 +77,10 @@ static size_t namespace_len;\n \n static const char *git_dir;\n static char *git_object_dir, *git_index_file, *git_graft_file;\n-\n+static char *git_object_crc_node;\n+#ifdef PACKDB\n+static char *git_object_packdb_node;\n+#endif\n /*\n * Repository-local GIT_* environment variables\n * Remember to update local_repo_env_size in cache.h when\n@@ -115,6 +122,11 @@ static char *expand_namespace(const char *raw_namespace)\n \n static void setup_git_env(void)\n {\n+\tstatic char cwdbuf[PATH_MAX];\n+\tint ocn_len;\n+#ifdef PACKDB\n+\tint opn_len;\n+#endif\n \tgit_dir = getenv(GIT_DIR_ENVIRONMENT);\n \tgit_dir = git_dir ? xstrdup(git_dir) : NULL;\n \tif (!git_dir) {\n@@ -128,6 +140,31 @@ static void setup_git_env(void)\n \t\tgit_object_dir = xmalloc(strlen(git_dir) + 9);\n \t\tsprintf(git_object_dir, \"%s/objects\", git_dir);\n \t}\n+\tocn_len = strlen(git_object_dir) + 8 + strlen(getcwd(cwdbuf, PATH_MAX));\n+\tgit_object_crc_node = xmalloc(ocn_len);\n+\tmemset(git_object_crc_node, 0, ocn_len);\n+\tsprintf(git_object_crc_node, \"%s/crcs\", git_object_dir);\n+\tif (git_object_crc_node[0] != '/') {\n+\t\tint ocn_offset = (git_object_crc_node[0] == '.' &&\n+\t\t\t\t git_object_crc_node[1] == '/')? 2:0;\n+\t\tmemset(git_object_crc_node, 0, ocn_len);\n+\t\tsprintf(git_object_crc_node, \"%s/%s/crcs\",\n+\t\t\tgetcwd(cwdbuf, PATH_MAX), git_object_dir + ocn_offset);\n+\t}\n+#ifdef PACKDB\n+\topn_len = strlen(git_object_dir)\n+\t\t+ 10 + strlen(getcwd(cwdbuf, PATH_MAX));\n+\tgit_object_packdb_node = xmalloc(opn_len);\n+\tmemset(git_object_packdb_node, 0, opn_len);\n+\tsprintf(git_object_packdb_node, \"%s/packdb\", git_object_dir);\n+\tif (git_object_packdb_node[0] != '/') {\n+\t\tint opn_offset = (git_object_crc_node[0] == '.' &&\n+\t\t\t\t git_object_crc_node[1] == '/')? 2:0;\n+\t\tmemset(git_object_packdb_node, 0, opn_len);\n+\t\tsprintf(git_object_packdb_node, \"%s/%s/packdb\",\n+\t\t\tgetcwd(cwdbuf, PATH_MAX), git_object_dir + opn_offset);\n+\t}\n+#endif\n \tgit_index_file = getenv(INDEX_ENVIRONMENT);\n \tif (!git_index_file) {\n \t\tgit_index_file = xmalloc(strlen(git_dir) + 7);\n@@ -140,6 +177,10 @@ static void setup_git_env(void)\n \t\tread_replace_refs = 0;\n \tnamespace = expand_namespace(getenv(GIT_NAMESPACE_ENVIRONMENT));\n \tnamespace_len = strlen(namespace);\n+\tcrcdb_init();\n+#ifdef PACKDB\n+\tpackdb_init();\n+#endif\n }\n \n int is_bare_repository(void)\n@@ -207,6 +248,20 @@ char *get_object_directory(void)\n \treturn git_object_dir;\n }\n \n+char *get_object_crc_node(void) {\n+\tif (!git_object_crc_node)\n+\t\tsetup_git_env();\n+\treturn git_object_crc_node;\n+}\n+\n+#ifdef PACKDB\n+char *get_object_packdb_node(void) {\n+\tif (!git_object_packdb_node)\n+\t\tsetup_git_env();\n+\treturn git_object_packdb_node;\n+}\n+#endif\n+\n int odb_mkstemp(char *template, size_t limit, const char *pattern)\n {\n \tint fd;\ndiff --git a/fast-import.c b/fast-import.c\nindex 8d8ea3c..62a675c 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -165,6 +165,11 @@ Format of STDIN stream:\n #include \"exec_cmd.h\"\n #include \"dir.h\"\n \n+#ifdef PACKDB\n+#include \"packdb.h\"\n+#endif\n+\n+\n #define PACK_ID_BITS 16\n #define MAX_PACK_ID ((1<next_free++;\n \thashcpy(e->idx.sha1, sha1);\n+\te->idx.has_objcrc32 = 0;\n+\te->idx.objcrc32 = 0;\n \treturn e;\n }\n \n@@ -904,9 +911,34 @@ static const char *create_index(void)\n \treturn tmpfile;\n }\n \n-static char *keep_pack(const char *curr_index_name)\n+static const char *create_mds(void)\n+{\n+\tconst char *tmpfile;\n+\tstruct pack_idx_entry **mds, **c, **last;\n+\tstruct object_entry *e;\n+\tstruct object_entry_pool *o;\n+\n+\t/* Build the table of object IDs. */\n+\tmds = xmalloc(object_count * sizeof(*mds));\n+\tc = mds;\n+\tfor (o = blocks; o; o = o->next_pool)\n+\t\tfor (e = o->next_free; e-- != o->entries;)\n+\t\t\tif (pack_id == e->pack_id)\n+\t\t\t\t*c++ = &e->idx;\n+\tlast = mds + object_count;\n+\tif (c != last)\n+\t\tdie(\"internal consistency error creating the mds file\");\n+\n+\ttmpfile = write_mds_file(NULL, mds, object_count, &pack_idx_opts, pack_data->sha1);\n+\tfree(mds);\n+\treturn tmpfile;\n+}\n+\n+\n+static char *keep_pack(const char *curr_index_name, const char *curr_mds_name)\n {\n \tstatic char name[PATH_MAX];\n+\tstatic char rname[PATH_MAX];\n \tstatic const char *keep_msg = \"fast-import\";\n \tint keep_fd;\n \n@@ -927,6 +959,13 @@ static char *keep_pack(const char *curr_index_name)\n \tif (move_temp_to_file(curr_index_name, name))\n \t\tdie(\"cannot store index file\");\n \tfree((void *)curr_index_name);\n+\n+\tsnprintf(rname, sizeof(rname), \"%s/pack/pack-%s.mds\",\n+\t\t get_object_directory(), sha1_to_hex(pack_data->sha1));\n+\tif (move_temp_to_file(curr_mds_name, rname))\n+\t\tdie(\"cannot store index file\");\n+\tfree((void *)curr_mds_name);\n+\n \treturn name;\n }\n \n@@ -951,6 +990,7 @@ static void end_packfile(void)\n \tif (object_count) {\n \t\tunsigned char cur_pack_sha1[20];\n \t\tchar *idx_name;\n+\t\tconst char *n1, *n2;\n \t\tint i;\n \t\tstruct branch *b;\n \t\tstruct tag *t;\n@@ -961,7 +1001,9 @@ static void end_packfile(void)\n \t\t\t\t pack_data->pack_name, object_count,\n \t\t\t\t cur_pack_sha1, pack_size);\n \t\tclose(pack_data->pack_fd);\n-\t\tidx_name = keep_pack(create_index());\n+\t\tn1 = create_index();\n+\t\tn2 = create_mds();\n+\t\tidx_name = keep_pack(n1, n2);\n \n \t\t/* Register the packfile with core git's machinery. */\n \t\tnew_p = add_packed_git(idx_name, strlen(idx_name), 1);\n@@ -1021,6 +1063,7 @@ static int store_object(\n \tunsigned long hdrlen, deltalen;\n \tgit_SHA_CTX c;\n \tgit_zstream s;\n+\tuint32_t objcrc;\n \n \thdrlen = sprintf((char *)hdr,\"%s %lu\", typename(type),\n \t\t(unsigned long)dat->len) + 1;\n@@ -1028,10 +1071,27 @@ static int store_object(\n \tgit_SHA1_Update(&c, hdr, hdrlen);\n \tgit_SHA1_Update(&c, dat->buf, dat->len);\n \tgit_SHA1_Final(sha1, &c);\n+\tobjcrc = crc32(0, NULL, 0);\n+\tobjcrc = htonl(crc32(objcrc, (unsigned char *)(dat->buf), dat->len));\n+\n+\tif (has_sha1_file(sha1)) {\n+\t\tuint32_t oldcrc;\n+\t\tif (has_sha1_file_crc(sha1, &oldcrc)) {\n+\t\t\tif (objcrc != oldcrc) {\n+\t\t\t\tdie(\"hash collision on %s [fast-import]\",\n+\t\t\t\t sha1_to_hex(sha1));\n+\t\t\t}\n+\t\t}\n+\t}\n \tif (sha1out)\n \t\thashcpy(sha1out, sha1);\n \n \te = insert_object(sha1);\n+\te->idx.has_objcrc32 = 1;\n+\te->idx.objcrc32 = objcrc;\n+#ifdef PACKDB\n+\tpackdb_process(sha1, objcrc);\n+#endif\n \tif (mark)\n \t\tinsert_mark(mark, e);\n \tif (e->idx.offset) {\n@@ -1163,6 +1223,7 @@ static void stream_blob(uintmax_t len, unsigned char *sha1out, uintmax_t mark)\n \tunsigned char *out_buf = xmalloc(out_sz);\n \tstruct object_entry *e;\n \tunsigned char sha1[20];\n+\tuint32_t objcrc;\n \tunsigned long hdrlen;\n \toff_t offset;\n \tgit_SHA_CTX c;\n@@ -1186,6 +1247,7 @@ static void stream_blob(uintmax_t len, unsigned char *sha1out, uintmax_t mark)\n \t\tdie(\"impossibly large object header\");\n \n \tgit_SHA1_Init(&c);\n+\tobjcrc = crc32(0, NULL, 0);\n \tgit_SHA1_Update(&c, out_buf, hdrlen);\n \n \tcrc32_begin(pack_file);\n@@ -1208,6 +1270,7 @@ static void stream_blob(uintmax_t len, unsigned char *sha1out, uintmax_t mark)\n \t\t\t\tdie(\"EOF in data (%\" PRIuMAX \" bytes remaining)\", len);\n \n \t\t\tgit_SHA1_Update(&c, in_buf, n);\n+\t\t\tobjcrc = crc32(objcrc, in_buf, n);\n \t\t\ts.next_in = in_buf;\n \t\t\ts.avail_in = n;\n \t\t\tlen -= n;\n@@ -1234,11 +1297,14 @@ static void stream_blob(uintmax_t len, unsigned char *sha1out, uintmax_t mark)\n \t}\n \tgit_deflate_end(&s);\n \tgit_SHA1_Final(sha1, &c);\n+\tobjcrc = htonl(objcrc);\n \n \tif (sha1out)\n \t\thashcpy(sha1out, sha1);\n \n \te = insert_object(sha1);\n+\te->idx.has_objcrc32 = 1;\n+\te->idx.objcrc32 = objcrc;\n \n \tif (mark)\n \t\tinsert_mark(mark, e);\n@@ -1837,6 +1903,8 @@ static void read_marks(void)\n \t\t\tif (type < 0)\n \t\t\t\tdie(\"object not found: %s\", sha1_to_hex(sha1));\n \t\t\te = insert_object(sha1);\n+\t\t\te->idx.has_objcrc32 =\n+\t\t\t\thas_sha1_file_crc(sha1, &e->idx.objcrc32);\n \t\t\te->type = type;\n \t\t\te->pack_id = MAX_PACK_ID;\n \t\t\te->idx.offset = 1; /* just not zero! */\n@@ -2883,6 +2951,8 @@ static struct object_entry *dereference(struct object_entry *oe,\n \t\t\tdie(\"object not found: %s\", sha1_to_hex(sha1));\n \t\t/* cache it! */\n \t\toe = insert_object(sha1);\n+\t\toe->idx.has_objcrc32 =\n+\t\t\thas_sha1_file_crc(sha1, &oe->idx.objcrc32);\n \t\toe->type = type;\n \t\toe->pack_id = MAX_PACK_ID;\n \t\toe->idx.offset = 1;\ndiff --git a/git-repack.sh b/git-repack.sh\nindex 624feec..7602853 100755\n--- a/git-repack.sh\n+++ b/git-repack.sh\n@@ -91,6 +91,7 @@ if [ -z \"$names\" ]; then\n \tsay Nothing new to pack.\n fi\n \n+\n # Ok we have prepared all new packfiles.\n \n # First see if there are packs of the same name and if so\n@@ -100,7 +101,7 @@ rollback=\n failed=\n for name in $names\n do\n-\tfor sfx in pack idx\n+\tfor sfx in pack idx mds\n \tdo\n \t\tfile=pack-$name.$sfx\n \t\ttest -f \"$PACKDIR/$file\" || continue\n@@ -148,15 +149,22 @@ do\n \tfullbases=\"$fullbases pack-$name\"\n \tchmod a-w \"$PACKTMP-$name.pack\"\n \tchmod a-w \"$PACKTMP-$name.idx\"\n+\t(chmod a-w \"$PACKTMP-$name.mds\" 2>/dev/null || exit 0 )\n \tmv -f \"$PACKTMP-$name.pack\" \"$PACKDIR/pack-$name.pack\" &&\n \tmv -f \"$PACKTMP-$name.idx\" \"$PACKDIR/pack-$name.idx\" ||\n \texit\n+\tif test -f \"$PACKTMP-$name.mds\"\n+\tthen\n+\t\tmv -f \"$PACKTMP-$name.mds\" \"$PACKDIR/pack-$name.mds\" \\\n+\t\t 2>/dev/null || exit\n+\tfi\n done\n \n # Remove the \"old-\" files\n for name in $names\n do\n \trm -f \"$PACKDIR/old-pack-$name.idx\"\n+\trm -f \"$PACKDIR/old-pack-$name.mds\"\n \trm -f \"$PACKDIR/old-pack-$name.pack\"\n done\n \n@@ -172,7 +180,7 @@ then\n \t\t do\n \t\t\tcase \" $fullbases \" in\n \t\t\t*\" $e \"*) ;;\n-\t\t\t*)\trm -f \"$e.pack\" \"$e.idx\" \"$e.keep\" ;;\n+\t\t\t*)\trm -f \"$e.pack\" \"$e.idx\" \"$e.mds\" \"$e.keep\" ;;\n \t\t\tesac\n \t\t done\n \t\t)\ndiff --git a/git.c b/git.c\nindex 8e34903..c6924f0 100644\n--- a/git.c\n+++ b/git.c\n@@ -4,7 +4,10 @@\n #include \"help.h\"\n #include \"quote.h\"\n #include \"run-command.h\"\n-\n+#include \"crcdb.h\"\n+#ifdef PACKDB\n+#include \"packdb.h\"\n+#endif\n const char git_usage_string[] =\n \t\"git [--version] [--exec-path[=]] [--html-path] [--man-path] [--info-path]\\n\"\n \t\" [-p|--paginate|--no-pager] [--no-replace-objects] [--bare]\\n\"\n@@ -278,7 +281,15 @@ static int run_builtin(struct cmd_struct *p, int argc, const char **argv)\n \tint status, help;\n \tstruct stat st;\n \tconst char *prefix;\n-\n+\tstatic int crcdb_need_atexit = 1;\n+\n+\tif (crcdb_need_atexit) {\n+#ifdef PACKDB\n+\t\tatexit(packdb_finish);\n+#endif\n+\t\tatexit(crcdb_finish);\n+\t\tcrcdb_need_atexit = 0;\n+\t}\n \tprefix = NULL;\n \thelp = argc == 2 && !strcmp(argv[1], \"-h\");\n \tif (!help) {\ndiff --git a/hex.c b/hex.c\nindex 9ebc050..73c88fa 100644\n--- a/hex.c\n+++ b/hex.c\n@@ -56,10 +56,50 @@ int get_sha1_hex(const char *hex, unsigned char *sha1)\n \treturn 0;\n }\n \n+static int get_crc_hex(const char *hex, unsigned char *crc) {\n+\tint i;\n+\tfor (i = 0; i < 4; i++) {\n+\t\tunsigned int val = (hexval(hex[0]) << 4) | hexval(hex[1]);\n+\t\tif (val & ~0xff)\n+\t\t\treturn -1;\n+\t\t*crc++ = val;\n+\t\thex += 2;\n+\t}\n+\treturn 0;\n+}\n+\n+int get_sha1_hex_crc(const char *hex, unsigned char *sha1, int *hascrc,\n+\t\t uint32_t *crc, int *hasblobmds, uint32_t *blobmds)\n+{\n+\tint result = get_sha1_hex(hex, sha1);\n+\tif (result) return result;\n+\tif (hex[20] == '-') {\n+\t\tunsigned char *ptr = (unsigned char *)crc;\n+\t\tif (!get_crc_hex(hex+21, ptr))\n+\t\t\treturn -1;\n+\t\t*hascrc = 1;\n+\t\tif (hex[25] == '-') {\n+\t\t\tptr = (unsigned char *)blobmds;\n+\t\t\tif (!get_crc_hex(hex+26, ptr)) {\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t\t*hasblobmds = 1;\n+\t\t} else {\n+\t\t\t*hasblobmds = 0;\n+\t\t}\n+\t} else {\n+\t\t*hascrc = 0;\n+\t\t*hasblobmds = 0;\n+\t\t*crc = 0;\n+\t\t*blobmds = 0;\n+\t}\n+\treturn 0;\n+}\n+\n char *sha1_to_hex(const unsigned char *sha1)\n {\n \tstatic int bufno;\n-\tstatic char hexbuffer[4][50];\n+\tstatic char hexbuffer[4][59];\n \tstatic const char hex[] = \"0123456789abcdef\";\n \tchar *buffer = hexbuffer[3 & ++bufno], *buf = buffer;\n \tint i;\n@@ -73,3 +113,19 @@ char *sha1_to_hex(const unsigned char *sha1)\n \n \treturn buffer;\n }\n+\n+char *sha1_to_hex_crc(const unsigned char *sha1, const uint32_t objcrc32)\n+{\n+\tchar *result = sha1_to_hex(sha1);\n+\tsprintf(result+40, \"-%8.8x\", ntohl(objcrc32));\n+\treturn result;\n+}\n+\n+char *sha1_to_hex_crc2(const unsigned char *sha1, const uint32_t objcrc32,\n+\t\t const uint32_t blobcrc32)\n+{\n+\tchar *result = sha1_to_hex(sha1);\n+\tsprintf(result+40, \"-%8.8x-%8.8x\", ntohl(objcrc32),\n+\t\tntohl(blobcrc32));\n+\treturn result;\n+}\ndiff --git a/http.c b/http.c\nindex e6c7597..a92fd9f 100644\n--- a/http.c\n+++ b/http.c\n@@ -1072,8 +1072,9 @@ int finish_http_pack_request(struct http_pack_request *preq)\n \tstruct packed_git **lst;\n \tstruct packed_git *p = preq->target;\n \tchar *tmp_idx;\n+\tchar *tmp_mds;\n \tstruct child_process ip;\n-\tconst char *ip_argv[8];\n+\tconst char *ip_argv[10];\n \n \tclose_pack_index(p);\n \n@@ -1087,14 +1088,20 @@ int finish_http_pack_request(struct http_pack_request *preq)\n \t*lst = (*lst)->next;\n \n \ttmp_idx = xstrdup(preq->tmpfile);\n+\ttmp_mds = xstrdup(preq->tmpfile);\n \tstrcpy(tmp_idx + strlen(tmp_idx) - strlen(\".pack.temp\"),\n \t \".idx.temp\");\n+\tstrcpy(tmp_mds + strlen(tmp_mds) - strlen(\".pack.temp\"),\n+\t \".mds.temp\");\n+\n \n \tip_argv[0] = \"index-pack\";\n \tip_argv[1] = \"-o\";\n \tip_argv[2] = tmp_idx;\n-\tip_argv[3] = preq->tmpfile;\n-\tip_argv[4] = NULL;\n+\tip_argv[3] = \"-m\";\n+\tip_argv[4] = tmp_mds;\n+\tip_argv[5] = preq->tmpfile;\n+\tip_argv[6] = NULL;\n \n \tmemset(&ip, 0, sizeof(ip));\n \tip.argv = ip_argv;\n@@ -1105,20 +1112,24 @@ int finish_http_pack_request(struct http_pack_request *preq)\n \tif (run_command(&ip)) {\n \t\tunlink(preq->tmpfile);\n \t\tunlink(tmp_idx);\n+\t\tunlink(tmp_mds);\n \t\tfree(tmp_idx);\n+\t\tfree(tmp_mds);\n \t\treturn -1;\n \t}\n \n \tunlink(sha1_pack_index_name(p->sha1));\n \n \tif (move_temp_to_file(preq->tmpfile, sha1_pack_name(p->sha1))\n-\t || move_temp_to_file(tmp_idx, sha1_pack_index_name(p->sha1))) {\n+\t || move_temp_to_file(tmp_idx, sha1_pack_index_name(p->sha1))\n+\t || move_temp_to_file(tmp_mds, sha1_pack_mds_name(p->sha1))) {\n \t\tfree(tmp_idx);\n \t\treturn -1;\n \t}\n \n \tinstall_packed_git(p);\n \tfree(tmp_idx);\n+\tfree(tmp_mds);\n \treturn 0;\n }\n \ndiff --git a/pack-write.c b/pack-write.c\nindex 9cd3bfb..1c8fb72 100644\n--- a/pack-write.c\n+++ b/pack-write.c\n@@ -178,6 +178,101 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec\n \treturn index_name;\n }\n \n+\n+const char *write_mds_file(const char *crc_name,\n+\t\t\t struct pack_idx_entry **objects,\n+\t\t\t int nr,\n+\t\t\t const struct pack_idx_option *opts,\n+\t\t\t unsigned char *sha1)\n+{\n+\tstatic unsigned char buffer[20];\n+\tunsigned char *base = buffer;\n+\tint i, j, fd;\n+\tstruct sha1file *f;\n+\n+\tif (nr) {\n+\t\t/*\n+\t\t * Sort just in case objects not already sorted.\n+\t\t */\n+\t\tqsort(objects, nr, sizeof(objects[0]), sha1_compare);\n+\t}\n+\n+\tif (opts->flags & WRITE_IDX_VERIFY) {\n+\t\tassert(crc_name);\n+\t\tf = sha1fd_check(crc_name);\n+\t\tif (f == NULL) {\n+\t\t\t/*\n+\t\t\t * For backwards-compatability, assume a missing\n+\t\t\t * mds file is OK.\n+\t\t\t */\n+\t\t\treturn crc_name;\n+\t\t}\n+\t} else {\n+\t if (!crc_name) {\n+\t static char tmpfile[PATH_MAX];\n+\t fd = odb_mkstemp(tmpfile, sizeof(tmpfile),\n+\t\t\t \"pack/tmp_mds_XXXXXX\");\n+\t crc_name = xstrdup(tmpfile);\n+\t } else {\n+\t unlink(crc_name);\n+\t fd = open(crc_name, O_CREAT|O_EXCL|O_WRONLY, 0600);\n+\t }\n+\t if (fd < 0)\n+\t die_errno(\"unable to create '%s'\", crc_name);\n+\t f = sha1fd(fd, crc_name);\n+\t}\n+\n+\t*(base++) = 'P';\n+\t*(base++) = 'K';\n+\t*(base++) = 'M';\n+\t*(base++) = 'D';\n+\t*(base++) = 'S';\n+\t*(base++) = 0;\n+\t*(base++) = 1; /* version number */\n+\t*(base++) = 1; /* wsize */\n+\tsha1write(f, buffer, base - buffer);\n+\tbase = buffer;\n+\n+\tfor (i = 0; i < nr; i += 4) {\n+\t\tint lim = ((nr-i) > 3)? 4: nr-i;\n+\t\tint has[4];\n+\t\tuint32_t crc[4];\n+\t\tfor (j = 0; j < lim; j++) {\n+\t\t\tif (objects[i+j]->has_objcrc32) {\n+\t\t\t\thas[j] = 1;\n+\t\t\t\tcrc[j] = objects[i+j]->objcrc32;\n+\t\t\t} else {\n+\t\t\t\thas[j] =\n+\t\t\t\t (has_sha1_file_crc(objects[i + j]->sha1,\n+\t\t\t\t\t\t &crc[j]) == 1);\n+\t\t\t}\n+\t\t}\n+\t\tfor (j = 0; j < 4; j++) {\n+\t\t\tif (j < lim) {\n+\t\t\t\t*(base)++ = has[j];\n+\t\t\t} else {\n+\t\t\t\thas[j] = 0;\n+\t\t\t\tcrc[j] = 0;\n+\t\t\t\t*(base++) = 0;\n+\t\t\t}\n+\t\t}\n+\t\tfor (j = 0; j < 4; j += 1) {\n+\t\t if (j < lim) {\n+\t\t\t*((uint32_t *)base) = has[j]? crc[j]: 0;\n+\t\t } else {\n+\t\t\t*((uint32_t *)base) = 0;\n+\t\t }\n+\t\t base += 4;\n+\t\t}\n+\t\tsha1write(f, buffer, base - buffer);\n+\t\tbase = buffer;\n+\t}\n+\tsha1write(f, sha1, 20);\n+\tsha1close(f, NULL, ((opts->flags & WRITE_IDX_VERIFY)\n+\t\t\t ? CSUM_CLOSE : CSUM_FSYNC));\n+\treturn crc_name;\n+}\n+\n /*\n * Update pack header with object_count and compute new SHA1 for pack data\n * associated to pack_fd, and write that SHA1 at the end. That new SHA1\ndiff --git a/pack.h b/pack.h\nindex 722a54e..62f5d41 100644\n--- a/pack.h\n+++ b/pack.h\n@@ -68,9 +68,12 @@ struct pack_idx_entry {\n \tunsigned char sha1[20];\n \tuint32_t crc32;\n \toff_t offset;\n+\tint has_objcrc32;\n+\tuint32_t objcrc32;\n };\n \n extern const char *write_idx_file(const char *index_name, struct pack_idx_entry **objects, int nr_objects, const struct pack_idx_option *, unsigned char *sha1);\n+extern const char *write_mds_file(const char *mds_name, struct pack_idx_entry **objects, int nr_objects, const struct pack_idx_option *, unsigned char *sha1);\n extern int check_pack_crc(struct packed_git *p, struct pack_window **w_curs, off_t offset, off_t len, unsigned int nr);\n extern int verify_pack_index(struct packed_git *);\n extern int verify_pack(struct packed_git *);\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 6dcae38..da51b40 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -18,6 +18,10 @@\n #include \"refs.h\"\n #include \"pack-revindex.h\"\n #include \"sha1-lookup.h\"\n+#include \"crcdb.h\"\n+#ifdef PACKDB\n+#include \"packdb.h\"\n+#endif\n \n #ifndef O_NOATIME\n #if defined(__linux__) && (defined(__i386__) || defined(__PPC__))\n@@ -40,6 +44,7 @@ const unsigned char null_sha1[20];\n */\n static struct cached_object {\n \tunsigned char sha1[20];\n+\tuint32_t objcrc32;\n \tenum object_type type;\n \tvoid *buf;\n \tunsigned long size;\n@@ -48,6 +53,7 @@ static int cached_object_nr, cached_object_alloc;\n \n static struct cached_object empty_tree = {\n \tEMPTY_TREE_SHA1_BIN_LITERAL,\n+\t0u,\n \tOBJ_TREE,\n \t\"\",\n \t0\n@@ -222,11 +228,18 @@ char *sha1_pack_index_name(const unsigned char *sha1)\n \treturn sha1_get_pack_name(sha1, &name, &base, \"idx\");\n }\n \n+char *sha1_pack_mds_name(const unsigned char *sha1)\n+{\n+\tstatic char *name, *base;\n+\n+\treturn sha1_get_pack_name(sha1, &name, &base, \"mds\");\n+}\n+\n+\n struct alternate_object_database *alt_odb_list;\n static struct alternate_object_database **alt_odb_tail;\n \n static void read_info_alternates(const char * alternates, int depth);\n-static int git_open_noatime(const char *name);\n \n /*\n * Prepare alternate object database registry.\n@@ -415,6 +428,7 @@ void prepare_alt_odb(void)\n \tlink_alt_odb_entries(alt, alt + strlen(alt), PATH_SEP, NULL, 0);\n \n \tread_info_alternates(get_object_directory(), 0);\n+\tcrcdb_init_alts();\n }\n \n static int has_loose_object_local(const unsigned char *sha1)\n@@ -441,6 +455,52 @@ static int has_loose_object(const unsigned char *sha1)\n \t has_loose_object_nonlocal(sha1);\n }\n \n+static int has_loose_object_local_crc(const unsigned char *sha1,\n+\t\t\t\t uint32_t *objcrc32p)\n+{\n+\tint status;\n+\tcrcdb_open(NULL);\n+\tstatus = crcdb_lookup(NULL, sha1, objcrc32p) > 0;\n+\tcrcdb_close(NULL);\n+\treturn status;\n+}\n+\n+int has_loose_object_nonlocal_crc(const unsigned char *sha1,\n+\t\t\t\t uint32_t *objcrc32p)\n+{\n+\tstruct alternate_object_database *alt;\n+\tif (objcrc32p == NULL) return 0;\n+\t/* memset(buffer, 0, PATH_MAX); */\n+\tprepare_alt_odb();\n+\tfor (alt = alt_odb_list; alt; alt = alt->next) {\n+\t\tfill_sha1_path(alt->name, sha1);\n+\t\tif (!access(alt->base, F_OK)) {\n+\t\t\tuint32_t xcrc;\n+\t\t\t/* Use the crc corresponding to the hash */\n+\t\t\tcrcdb_t dbf;\n+\t\t\tint status;\n+\t\t\tdbf = crcdb_open_alt(alt);\n+\t\t\tstatus = crcdb_lookup(dbf, sha1,\n+\t\t\t\t\t (objcrc32p? objcrc32p: &xcrc));\n+\t\t\tcrcdb_close(dbf);\n+\t\t\tswitch (status) {\n+\t\t\tcase 0: return 0;\n+\t\t\tcase 1: return 1;\n+\t\t\tcase -1:\n+\t\t\tdefault:\n+\t\t\t\treturn 0;\n+\t\t\t}\n+\t\t}\n+\t}\n+\treturn 0;\n+}\n+\n+static int has_loose_object_crc(const unsigned char *sha1, uint32_t *objcrc32p)\n+{\n+\treturn has_loose_object_local_crc(sha1, objcrc32p) ||\n+\t has_loose_object_nonlocal_crc(sha1, objcrc32p);\n+}\n+\n static unsigned int pack_used_ctr;\n static unsigned int pack_mmap_calls;\n static unsigned int peak_pack_open_windows;\n@@ -574,6 +634,87 @@ static int check_packed_git_idx(const char *path, struct packed_git *p)\n \treturn 0;\n }\n \n+size_t required_git_packed_mds_size(const char *path, void *data,\n+\t\t\t\t uint32_t nobjects,\n+\t\t\t\t size_t actual_size) {\n+\tunsigned char *base;\n+\tint wsize, version;\n+\tsize_t required_size;\n+\tif (actual_size < 8) {\n+\t\terror(\"mds/crc file %s is too small\", path);\n+\t\treturn 0;\n+\t}\n+\n+\tbase = data;\n+\tif ((*(base++) != 'P')\n+\t || (*(base++) != 'K')\n+\t || (*(base++) != 'M')\n+\t || (*(base++) != 'D')\n+\t || (*(base++) != 'S')\n+\t || (*(base++) != 0)) {\n+\t\terror(\"mds/crc file %s corrupted (bad header)\",\n+\t\t\t path);\n+\t\treturn 0;\n+\n+\t}\n+\tif ((version = *(base++)) != 1) {\n+\t\terror(\"mds/crc file %s uses an unrecognized version %d\",\n+\t\t path, version);\n+\t\treturn 0;\n+\t}\n+\twsize = (*(base++)) * 4;\n+\tif (wsize != 4) {\n+\t\t/* other values not defined currently. */\n+\t\terror(\"mds/crc file %s corrupted (bad wsize field)\",\n+\t\t\t path);\n+\t\treturn 0;\n+\t}\n+\trequired_size = (size_t)8 +\n+\t ((size_t)((nobjects)/4 + (nobjects % 4 != 0))\n+\t * (size_t)(4 * (1 + wsize))) + (size_t)(20 * 2);\n+\tif (required_size != actual_size) {\n+\t\terror(\"mds/crc file %s not the right size: %ld != %ld\",\n+\t\t path, (long)actual_size, (long)required_size);\n+\t\treturn 0;\n+\t}\n+\treturn required_size;\n+}\n+\n+static int check_packed_git_mds(const char *path, struct packed_git *p)\n+{\n+\tvoid *mds_map;\n+\tsize_t mds_size, required_size;\n+\tunsigned char *base;\n+\tint fd = git_open_noatime(path);\n+\tint version;\n+\tstruct stat st;\n+\tif (fd < 0)\n+\t\treturn -1;\n+\tif (fstat(fd, &st)) {\n+\t\tclose(fd);\n+\t\treturn -1;\n+\t}\n+\tmds_size = xsize_t(st.st_size);\n+\tif (mds_size < 8 + 20 + 20) {\n+\t\tclose(fd);\n+\t\treturn error(\"mds/crc file %s is too small\", path);\n+\t}\n+\tmds_map = xmmap(NULL, mds_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tclose(fd);\n+\tbase = mds_map;\n+\trequired_size = required_git_packed_mds_size(path, mds_map,\n+\t\t\t\t\t\t p->num_objects,\n+\t\t\t\t\t\t mds_size);\n+\tif (required_size == 0) {\n+\t\tmunmap(mds_map, mds_size);\n+\t\treturn -1;\n+\t}\n+\tp->mds_data = mds_map;\n+\tp->mds_size = mds_size;\n+\tp->mds_version = version;\n+\treturn 0;\n+}\n+\n int open_pack_index(struct packed_git *p)\n {\n \tchar *idx_name;\n@@ -589,6 +730,20 @@ int open_pack_index(struct packed_git *p)\n \treturn ret;\n }\n \n+int open_pack_mds(struct packed_git *p) {\n+\tchar *crc_name;\n+\tint ret;\n+\n+\tif (p->mds_data)\n+\t\treturn 0;\n+\n+\tcrc_name = xstrdup(p->pack_name);\n+\tstrcpy(crc_name + strlen(crc_name) - strlen(\".pack\"), \".mds\");\n+\tret = check_packed_git_mds(crc_name, p);\n+\tfree(crc_name);\n+\treturn ret;\n+}\n+\n static void scan_windows(struct packed_git *p,\n \tstruct packed_git **lru_p,\n \tstruct pack_window **lru_w,\n@@ -690,6 +845,15 @@ void close_pack_index(struct packed_git *p)\n \tif (p->index_data) {\n \t\tmunmap((void *)p->index_data, p->index_size);\n \t\tp->index_data = NULL;\n+\t\tp->index_size = 0;\n+\t}\n+}\n+\n+void close_pack_mds(struct packed_git *p) {\n+\tif (p->mds_data) {\n+\t\tmunmap((void *)p->mds_data, p->mds_size);\n+\t\tp->mds_data = NULL;\n+\t\tp->mds_size = 0;\n \t}\n }\n \n@@ -717,6 +881,7 @@ void free_pack_by_name(const char *pack_name)\n \t\t\t\tpack_open_fds--;\n \t\t\t}\n \t\t\tclose_pack_index(p);\n+\t\t\tclose_pack_mds(p);\n \t\t\tfree(p->bad_object_sha1);\n \t\t\t*pp = p->next;\n \t\t\tfree(p);\n@@ -740,6 +905,10 @@ static int open_packed_git_1(struct packed_git *p)\n \n \tif (!p->index_data && open_pack_index(p))\n \t\treturn error(\"packfile %s index unavailable\", p->pack_name);\n+\t/*\n+\t * Assume an mds file might not be available - backwards compatibility\n+\t */\n+\tif (!p->mds_data) open_pack_mds(p);\n \n \tif (!pack_max_fds) {\n \t\tstruct rlimit lim;\n@@ -1141,14 +1310,23 @@ static const struct packed_git *has_packed_and_bad(const unsigned char *sha1)\n \treturn NULL;\n }\n \n-int check_sha1_signature(const unsigned char *sha1, void *map, unsigned long size, const char *type)\n+int check_sha1_signature_extended(const unsigned char *sha1,\n+\t\t\t\t uint32_t *objcrc32p,\n+\t\t\t\t void *map, unsigned long size,\n+\t\t\t\t const char *type)\n {\n \tunsigned char real_sha1[20];\n-\thash_sha1_file(map, size, type, real_sha1);\n-\treturn hashcmp(sha1, real_sha1) ? -1 : 0;\n+\tuint32_t realcrc;\n+\thash_sha1_file_extended(map, size, type, real_sha1,\n+\t\t\t\t((objcrc32p == NULL)? NULL: &realcrc));\n+\tint ret = hashcmp(sha1, real_sha1) ? -1 : 0;\n+\tif (objcrc32p && ret == 0) {\n+\t\tret = ((*objcrc32p) - realcrc)? -1 : 0;\n+\t}\n+\treturn ret;\n }\n \n-static int git_open_noatime(const char *name)\n+int git_open_noatime(const char *name)\n {\n \tstatic int sha1_file_open_flag = O_NOATIME;\n \n@@ -1924,15 +2102,46 @@ off_t nth_packed_object_offset(const struct packed_git *p, uint32_t n)\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+int nth_packed_object_objcrc32(const struct packed_git *p, uint32_t n,\n+\t\t\t uint32_t *objcrc32p)\n+{\n+\tint r;\n+\tunsigned char *base = (unsigned char *)(p->mds_data);\n+\tint wsize; /*size in bytes per CRC field, stored as 32-bit words */\n+\n+\tif (base == NULL) return 0;\n+\n+\tbase += 7;\n+\twsize = (*(base++)) * 4;\n+\tif (wsize != 4) {\n+\t\t/* other values not defined currently. */\n+\t\treturn -1;\n+\t}\n+\tbase += (n / 4) * (uint32_t)(4 * (1 + wsize));\n+\tr = n % 4;\n+\tif (base[r] == 0) return 0;\n+\tbase += 4;\n+\tbase += wsize * r;\n+\t*objcrc32p = *(uint32_t *) base;\n+\treturn 1;\n+}\n+\n+\n+\n+off_t find_pack_entry_one_extended(const unsigned char *sha1,\n+\t\t\t\t struct packed_git *p,\n+\t\t\t\t int *has_objcrc32p, uint32_t *objcrc32p)\n {\n \tconst uint32_t *level1_ofs = p->index_data;\n \tconst unsigned char *index = p->index_data;\n+\tconst unsigned char *mds = p->mds_data;\n \tunsigned hi, lo, stride;\n \tstatic int use_lookup = -1;\n \tstatic int debug_lookup = -1;\n \n+\tif (has_objcrc32p) *has_objcrc32p = 0;\n+\tif (objcrc32p) *objcrc32p = 0;\n+\n \tif (debug_lookup < 0)\n \t\tdebug_lookup = !!getenv(\"GIT_DEBUG_LOOKUP\");\n \n@@ -1942,6 +2151,11 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \t\tlevel1_ofs = p->index_data;\n \t\tindex = p->index_data;\n \t}\n+\n+\tif (!mds) {\n+\t\topen_pack_mds(p);\n+\t}\n+\n \tif (p->index_version > 1) {\n \t\tlevel1_ofs += 2;\n \t\tindex += 8;\n@@ -1977,8 +2191,14 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \t\tif (debug_lookup)\n \t\t\tprintf(\"lo %u hi %u rg %u mi %u\\n\",\n \t\t\t lo, hi, hi - lo, mi);\n-\t\tif (!cmp)\n+\t\tif (!cmp) {\n+\t\t\tif (has_objcrc32p && objcrc32p)\n+\t\t\t\t*(has_objcrc32p) =\n+\t\t\t\t (nth_packed_object_objcrc32(p,\n+\t\t\t\t\t\t\t mi,\n+\t\t\t\t\t\t\t objcrc32p) == 1);\n \t\t\treturn nth_packed_object_offset(p, mi);\n+\t\t}\n \t\tif (cmp > 0)\n \t\t\thi = mi;\n \t\telse\n@@ -2027,7 +2247,9 @@ static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e)\n \t\t\t\t\tgoto next;\n \t\t}\n \n-\t\toffset = find_pack_entry_one(sha1, p);\n+\t\toffset = find_pack_entry_one_extended(sha1, p,\n+\t\t\t\t\t\t &(e->has_objcrc32),\n+\t\t\t\t\t\t &(e->objcrc32));\n \t\tif (offset) {\n \t\t\t/*\n \t\t\t * We are about to tell the caller where they can\n@@ -2173,14 +2395,32 @@ static void *read_packed_sha1(const unsigned char *sha1,\n \treturn data;\n }\n \n-int pretend_sha1_file(void *buf, unsigned long len, enum object_type type,\n-\t\t unsigned char *sha1)\n+int pretend_sha1_file_extended(void *buf, unsigned long len,\n+\t\t\t enum object_type type,\n+\t\t\t unsigned char *sha1, uint32_t *objcrc32p)\n {\n-\tstruct cached_object *co;\n+\tstruct cached_object *co = NULL;\n+\tuint32_t crc32;\n+\tint has_crc32 = 0;\n \n-\thash_sha1_file(buf, len, typename(type), sha1);\n-\tif (has_sha1_file(sha1) || find_cached_object(sha1))\n+\thash_sha1_file_extended(buf, len, typename(type), sha1, &crc32);\n+\tif (has_sha1_file(sha1) || (co = find_cached_object(sha1))) {\n+\t\tuint32_t oldcrc32;\n+\t\tif (!has_sha1_file_crc(sha1, &oldcrc32)) {\n+\t\t\tif (co != NULL) {\n+\t\t\t\toldcrc32 = co->objcrc32;\n+\t\t\t\thas_crc32 = 1;\n+\t\t\t}\n+\t\t} else {\n+\t\t\thas_crc32 = 1;\n+\t\t}\n+\t\tif (has_crc32 && oldcrc32 != crc32) {\n+\t\t\t die(\"SHA1 COLLISION FOUND FOR %s \"\n+\t\t\t \"(dummy commit when running blame?)\",\n+\t\t\t sha1_to_hex(sha1));\n+\t\t}\n \t\treturn 0;\n+\t}\n \tif (cached_object_alloc <= cached_object_nr) {\n \t\tcached_object_alloc = alloc_nr(cached_object_alloc);\n \t\tcached_objects = xrealloc(cached_objects,\n@@ -2191,8 +2431,10 @@ int pretend_sha1_file(void *buf, unsigned long len, enum object_type type,\n \tco->size = len;\n \tco->type = type;\n \tco->buf = xmalloc(len);\n+\tco->objcrc32 = crc32;\n \tmemcpy(co->buf, buf, len);\n \thashcpy(co->sha1, sha1);\n+\tif (objcrc32p) *objcrc32p = crc32;\n \treturn 0;\n }\n \n@@ -2314,8 +2556,9 @@ void *read_object_with_reference(const unsigned char *sha1,\n }\n \n static void write_sha1_file_prepare(const void *buf, unsigned long len,\n- const char *type, unsigned char *sha1,\n- char *hdr, int *hdrlen)\n+\t\t\t\t const char *type, unsigned char *sha1,\n+\t\t\t\t uint32_t * objcrc32p,\n+\t\t\t\t char *hdr, int *hdrlen)\n {\n \tgit_SHA_CTX c;\n \n@@ -2327,6 +2570,10 @@ static void write_sha1_file_prepare(const void *buf, unsigned long len,\n \tgit_SHA1_Update(&c, hdr, *hdrlen);\n \tgit_SHA1_Update(&c, buf, len);\n \tgit_SHA1_Final(sha1, &c);\n+\tif (objcrc32p) {\n+\t\t*objcrc32p = crc32(0, NULL, 0);\n+\t\t*objcrc32p = htonl(crc32(*objcrc32p, buf, len));\n+\t}\n }\n \n /*\n@@ -2382,12 +2629,13 @@ static int write_buffer(int fd, const void *buf, size_t len)\n \treturn 0;\n }\n \n-int hash_sha1_file(const void *buf, unsigned long len, const char *type,\n- unsigned char *sha1)\n+int hash_sha1_file_extended(const void *buf, unsigned long len,\n+\t\t\t const char *type,\n+\t\t\t unsigned char *sha1, uint32_t *objcrc32p)\n {\n \tchar hdr[32];\n \tint hdrlen;\n-\twrite_sha1_file_prepare(buf, len, type, sha1, hdr, &hdrlen);\n+\twrite_sha1_file_prepare(buf, len, type, sha1, objcrc32p, hdr, &hdrlen);\n \treturn 0;\n }\n \n@@ -2441,10 +2689,13 @@ static int create_tmpfile(char *buffer, size_t bufsiz, const char *filename)\n \treturn fd;\n }\n \n-static int write_loose_object(const unsigned char *sha1, char *hdr, int hdrlen,\n+\n+static int write_loose_object(const unsigned char *sha1, uint32_t *objcrc32p,\n+\t\t\t char *hdr, int hdrlen,\n \t\t\t const void *buf, unsigned long len, time_t mtime)\n {\n \tint fd, ret;\n+\tuint32_t crc;\n \tunsigned char compressed[4096];\n \tgit_zstream stream;\n \tgit_SHA_CTX c;\n@@ -2467,7 +2718,7 @@ static int write_loose_object(const unsigned char *sha1, char *hdr, int hdrlen,\n \tstream.next_out = compressed;\n \tstream.avail_out = sizeof(compressed);\n \tgit_SHA1_Init(&c);\n-\n+\tcrc = crc32(0, NULL, 0);\n \t/* First header.. */\n \tstream.next_in = (unsigned char *)hdr;\n \tstream.avail_in = hdrlen;\n@@ -2482,11 +2733,13 @@ static int write_loose_object(const unsigned char *sha1, char *hdr, int hdrlen,\n \t\tunsigned char *in0 = stream.next_in;\n \t\tret = git_deflate(&stream, Z_FINISH);\n \t\tgit_SHA1_Update(&c, in0, stream.next_in - in0);\n+\t\tcrc = crc32(crc, in0, stream.next_in - in0);\n \t\tif (write_buffer(fd, compressed, stream.next_out - compressed) < 0)\n \t\t\tdie(\"unable to write sha1 file\");\n \t\tstream.next_out = compressed;\n \t\tstream.avail_out = sizeof(compressed);\n \t} while (ret == Z_OK);\n+\tcrc = htonl(crc);\n \n \tif (ret != Z_STREAM_END)\n \t\tdie(\"unable to deflate new object %s (%d)\", sha1_to_hex(sha1), ret);\n@@ -2496,9 +2749,10 @@ static int write_loose_object(const unsigned char *sha1, char *hdr, int hdrlen,\n \tgit_SHA1_Final(parano_sha1, &c);\n \tif (hashcmp(sha1, parano_sha1) != 0)\n \t\tdie(\"confused by unstable object source data for %s\", sha1_to_hex(sha1));\n-\n+\tif (objcrc32p && ((*objcrc32p) != crc)) {\n+\t\tdie(\"confused by unstable object source data (crc mismatch) for %s\", sha1_to_hex(sha1));\n+\t}\n \tclose_sha1_file(fd);\n-\n \tif (mtime) {\n \t\tstruct utimbuf utb;\n \t\tutb.actime = mtime;\n@@ -2508,24 +2762,41 @@ static int write_loose_object(const unsigned char *sha1, char *hdr, int hdrlen,\n \t\t\t\ttmpfile, strerror(errno));\n \t}\n \n-\treturn move_temp_to_file(tmpfile, filename);\n+\tret = move_temp_to_file(tmpfile, filename);\n+\tif (ret == 0) {\n+\t\tcrcdb_open(NULL);\n+\t\tcrcdb_process((crcdb_t)NULL, sha1, crc);\n+\t\tcrcdb_close(NULL);\n+\t}\n+\treturn ret;\n }\n \n-int write_sha1_file(const void *buf, unsigned long len, const char *type, unsigned char *returnsha1)\n+int write_sha1_file_extended(const void *buf, unsigned long len,\n+\t\t\t const char *type, unsigned char *returnsha1,\n+\t\t\t uint32_t *objcrc32p)\n {\n \tunsigned char sha1[20];\n \tchar hdr[32];\n \tint hdrlen;\n+\tuint32_t newcrc;\n \n \t/* Normally if we have it in the pack then we do not bother writing\n \t * it out into .git/objects/??/?{38} file.\n \t */\n-\twrite_sha1_file_prepare(buf, len, type, sha1, hdr, &hdrlen);\n+\twrite_sha1_file_prepare(buf, len, type, sha1, &newcrc, hdr, &hdrlen);\n \tif (returnsha1)\n \t\thashcpy(returnsha1, sha1);\n-\tif (has_sha1_file(sha1))\n+\tif (objcrc32p) *objcrc32p = newcrc;\n+\tif (has_sha1_file(sha1)) {\n+\t\tuint32_t oldcrc;\n+\t\tif (has_sha1_file_crc(sha1, &oldcrc)) {\n+\t\t\tif (newcrc != oldcrc) {\n+\t\t\t\tdie(\"hash collision\");\n+\t\t\t}\n+\t\t}\n \t\treturn 0;\n-\treturn write_loose_object(sha1, hdr, hdrlen, buf, len, 0);\n+\t}\n+\treturn write_loose_object(sha1, &newcrc, hdr, hdrlen, buf, len, 0);\n }\n \n int force_object_loose(const unsigned char *sha1, time_t mtime)\n@@ -2536,6 +2807,7 @@ int force_object_loose(const unsigned char *sha1, time_t mtime)\n \tchar hdr[32];\n \tint hdrlen;\n \tint ret;\n+\tuint32_t * const objcrc32p = NULL;\n \n \tif (has_loose_object(sha1))\n \t\treturn 0;\n@@ -2543,7 +2815,7 @@ int force_object_loose(const unsigned char *sha1, time_t mtime)\n \tif (!buf)\n \t\treturn error(\"cannot read sha1_file for %s\", sha1_to_hex(sha1));\n \thdrlen = sprintf(hdr, \"%s %lu\", typename(type), len) + 1;\n-\tret = write_loose_object(sha1, hdr, hdrlen, buf, len, mtime);\n+\tret = write_loose_object(sha1, objcrc32p, hdr, hdrlen, buf, len, mtime);\n \tfree(buf);\n \n \treturn ret;\n@@ -2572,6 +2844,86 @@ int has_sha1_file(const unsigned char *sha1)\n \treturn has_loose_object(sha1);\n }\n \n+int has_sha1_file_crc(const unsigned char *sha1, uint32_t *objcrc32p)\n+{\n+\tstruct pack_entry e;\n+\n+\n+\t/*\n+\t * builtin/send-pack.c uses a null SHA1 (all bytes zero) to\n+\t * indicate that a SHA-1 hash does not exist. We explicitly\n+\t * return 0 for this case, for correct behavior even if we\n+\t * somehow get that value into the database.\n+\t */\n+\tif (!hashcmp(sha1, null_sha1)) return 0;\n+\n+\tif (find_pack_entry(sha1, &e)) {\n+\t\tif (e.has_objcrc32) {\n+\t\t\tif (objcrc32p) *objcrc32p = e.objcrc32;\n+\t\t\treturn 1;\n+\t\t} else {\n+#ifdef PACKDB\n+\t\t\tif (e.p && e.p->pack_local) {\n+\t\t\t\t/*\n+\t\t\t\t * We have a local pack file, but could not\n+\t\t\t\t * find the CRC, so we first check if the\n+\t\t\t\t * CRC is still stored for loose objects.\n+\t\t\t\t * Then we try packdb (separate database for\n+\t\t\t\t * packed objects) and if it is not there, we\n+\t\t\t\t * compute it from scratch and add it to\n+\t\t\t\t * packdb.\n+\t\t\t\t */\n+\t\t\t\tif (has_loose_object_local_crc(sha1,\n+\t\t\t\t\t\t\t objcrc32p)) {\n+\t\t\t\t\treturn 1;\n+\t\t\t\t} else {\n+\t\t\t\t\tint status ;\n+\t\t\t\t\tpackdb_open();\n+\t\t\t\t\tstatus = (packdb_lookup(sha1,\n+\t\t\t\t\t\t\t\tobjcrc32p)\n+\t\t\t\t\t\t == 1);\n+\t\t\t\t\tif (status == 0) {\n+\t\t\t\t\t\tunsigned long len;\n+\t\t\t\t\t\tenum object_type type;\n+\t\t\t\t\t\tuint32_t crc;\n+\t\t\t\t\t\tcrc = crc32(0, NULL, 0);\n+\t\t\t\t\t\tvoid *buf = read_sha1_file\n+\t\t\t\t\t\t\t(sha1, &type, &len);\n+\t\t\t\t\t\tcrc = htonl(crc32(crc,\n+\t\t\t\t\t\t\t\t buf, len));\n+\t\t\t\t\t\tswitch(packdb_process\n+\t\t\t\t\t\t (sha1, crc)) {\n+\t\t\t\t\t\tcase 0:\n+\t\t\t\t\t\t\tif (objcrc32p)\n+\t\t\t\t\t\t\t\t*objcrc32p\n+\t\t\t\t\t\t\t\t\t= crc;\n+\t\t\t\t\t\t\tstatus = 1;\n+\t\t\t\t\t\t\tbreak;\n+\t\t\t\t\t\tcase 1:\n+\t\t\t\t\t\t\terror(\"packdb insert\"\n+\t\t\t\t\t\t\t \" botched\");\n+\t\t\t\t\t\t\tstatus = 0;\n+\t\t\t\t\t\t\tbreak;\n+\t\t\t\t\t\tcase -1:\n+\t\t\t\t\t\t\terror(\"packdb failed\");\n+\t\t\t\t\t\t\tstatus = 0;\n+\t\t\t\t\t\t\tbreak;\n+\t\t\t\t\t\t}\n+\t\t\t\t\t}\n+\t\t\t\t\tpackdb_close();\n+\t\t\t\t\treturn status;\n+\t\t\t\t}\n+\t\t\t} else {\n+\t\t\t\treturn 0;\n+\t\t\t}\n+#else\n+\t\t\treturn has_loose_object_local_crc(sha1, objcrc32p);\n+#endif\n+\t\t}\n+\t}\n+\treturn has_loose_object_crc(sha1, objcrc32p);\n+}\n+\n static void check_tree(const void *buf, size_t size)\n {\n \tstruct tree_desc desc;\n@@ -2600,7 +2952,8 @@ static void check_tag(const void *buf, size_t size)\n \t\tdie(\"corrupt tag\");\n }\n \n-static int index_mem(unsigned char *sha1, void *buf, size_t size,\n+static int index_mem(unsigned char *sha1, uint32_t *objcrc32p,\n+\t\t void *buf, size_t size,\n \t\t enum object_type type,\n \t\t const char *path, unsigned flags)\n {\n@@ -2631,22 +2984,26 @@ static int index_mem(unsigned char *sha1, void *buf, size_t size,\n \t}\n \n \tif (write_object)\n-\t\tret = write_sha1_file(buf, size, typename(type), sha1);\n+\t\tret = write_sha1_file_extended(buf, size, typename(type), sha1,\n+\t\t\t\t\t objcrc32p);\n \telse\n-\t\tret = hash_sha1_file(buf, size, typename(type), sha1);\n+\t\tret = hash_sha1_file_extended(buf, size, typename(type), sha1,\n+\t\t\t\t objcrc32p);\n \tif (re_allocated)\n \t\tfree(buf);\n \treturn ret;\n }\n \n-static int index_pipe(unsigned char *sha1, int fd, enum object_type type,\n+static int index_pipe(unsigned char *sha1, uint32_t *objcrc32p,\n+\t\t int fd, enum object_type type,\n \t\t const char *path, unsigned flags)\n {\n \tstruct strbuf sbuf = STRBUF_INIT;\n \tint ret;\n \n \tif (strbuf_read(&sbuf, fd, 4096) >= 0)\n-\t\tret = index_mem(sha1, sbuf.buf, sbuf.len, type,\tpath, flags);\n+\t\tret = index_mem(sha1, objcrc32p, sbuf.buf, sbuf.len, type,\n+\t\t\t\tpath, flags);\n \telse\n \t\tret = -1;\n \tstrbuf_release(&sbuf);\n@@ -2655,24 +3012,26 @@ static int index_pipe(unsigned char *sha1, int fd, enum object_type type,\n \n #define SMALL_FILE_SIZE (32*1024)\n \n-static int index_core(unsigned char *sha1, int fd, size_t size,\n+static int index_core(unsigned char *sha1, uint32_t *objcrc32p,\n+\t\t int fd, size_t size,\n \t\t enum object_type type, const char *path,\n \t\t unsigned flags)\n {\n \tint ret;\n \n \tif (!size) {\n-\t\tret = index_mem(sha1, NULL, size, type, path, flags);\n+\t\tret = index_mem(sha1, objcrc32p, NULL, size, type, path, flags);\n \t} else if (size <= SMALL_FILE_SIZE) {\n \t\tchar *buf = xmalloc(size);\n \t\tif (size == read_in_full(fd, buf, size))\n-\t\t\tret = index_mem(sha1, buf, size, type, path, flags);\n+\t\t\tret = index_mem(sha1, objcrc32p,\n+\t\t\t\t\tbuf, size, type, path, flags);\n \t\telse\n \t\t\tret = error(\"short read %s\", strerror(errno));\n \t\tfree(buf);\n \t} else {\n \t\tvoid *buf = xmmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);\n-\t\tret = index_mem(sha1, buf, size, type, path, flags);\n+\t\tret = index_mem(sha1, objcrc32p, buf, size, type, path, flags);\n \t\tmunmap(buf, size);\n \t}\n \treturn ret;\n@@ -2692,7 +3051,8 @@ static int index_core(unsigned char *sha1, int fd, size_t size,\n * avoid mmaping it in core is to deal with large binary blobs, and\n * by definition they do _not_ want to get any conversion.\n */\n-static int index_stream(unsigned char *sha1, int fd, size_t size,\n+static int index_stream(unsigned char *sha1, uint32_t *ojbcrc32p,\n+\t\t\tint fd, size_t size,\n \t\t\tenum object_type type, const char *path,\n \t\t\tunsigned flags)\n {\n@@ -2757,23 +3117,25 @@ static int index_stream(unsigned char *sha1, int fd, size_t size,\n \treturn 0;\n }\n \n-int index_fd(unsigned char *sha1, int fd, struct stat *st,\n-\t enum object_type type, const char *path, unsigned flags)\n+int index_fd_extended(unsigned char *sha1, uint32_t *objcrc32p,\n+\t\t int fd, struct stat *st,\n+\t\t enum object_type type, const char *path, unsigned flags)\n {\n \tint ret;\n \tsize_t size = xsize_t(st->st_size);\n \n \tif (!S_ISREG(st->st_mode))\n-\t\tret = index_pipe(sha1, fd, type, path, flags);\n+\t\tret = index_pipe(sha1, objcrc32p, fd, type, path, flags);\n \telse if (size <= big_file_threshold || type != OBJ_BLOB)\n-\t\tret = index_core(sha1, fd, size, type, path, flags);\n+\t\tret = index_core(sha1, objcrc32p, fd, size, type, path, flags);\n \telse\n-\t\tret = index_stream(sha1, fd, size, type, path, flags);\n+\t\tret = index_stream(sha1, objcrc32p,\n+\t\t\t\t fd, size, type, path, flags);\n \tclose(fd);\n \treturn ret;\n }\n \n-int index_path(unsigned char *sha1, const char *path, struct stat *st, unsigned flags)\n+int index_path_extended(unsigned char *sha1, uint32_t *objcrc32p, const char *path, struct stat *st, unsigned flags)\n {\n \tint fd;\n \tstruct strbuf sb = STRBUF_INIT;\n@@ -2784,7 +3146,8 @@ int index_path(unsigned char *sha1, const char *path, struct stat *st, unsigned\n \t\tif (fd < 0)\n \t\t\treturn error(\"open(\\\"%s\\\"): %s\", path,\n \t\t\t\t strerror(errno));\n-\t\tif (index_fd(sha1, fd, st, OBJ_BLOB, path, flags) < 0)\n+\t\tif (index_fd_extended(sha1, objcrc32p, fd, st,\n+\t\t\t\t OBJ_BLOB, path, flags) < 0)\n \t\t\treturn error(\"%s: failed to insert into database\",\n \t\t\t\t path);\n \t\tbreak;\n@@ -2795,8 +3158,10 @@ int index_path(unsigned char *sha1, const char *path, struct stat *st, unsigned\n \t\t\t errstr);\n \t\t}\n \t\tif (!(flags & HASH_WRITE_OBJECT))\n-\t\t\thash_sha1_file(sb.buf, sb.len, blob_type, sha1);\n-\t\telse if (write_sha1_file(sb.buf, sb.len, blob_type, sha1))\n+\t\t\thash_sha1_file_extended(sb.buf, sb.len, blob_type, sha1,\n+\t\t\t\t objcrc32p);\n+\t\telse if (write_sha1_file_extended(sb.buf, sb.len, blob_type,\n+\t\t\t\t\t\t sha1, objcrc32p))\n \t\t\treturn error(\"%s: failed to insert into database\",\n \t\t\t\t path);\n \t\tstrbuf_release(&sb);\ndiff --git a/t/t0000-basic.sh b/t/t0000-basic.sh\nindex f4e8f43..28c2ba2 100755\n--- a/t/t0000-basic.sh\n+++ b/t/t0000-basic.sh\n@@ -34,17 +34,18 @@ fi\n # git init has been done in an empty repository.\n # make sure it is empty.\n \n-find .git/objects -type f -print >should-be-empty\n+find .git/objects -type f -a ! -name crcs -a ! -name packdb -print >should-be-empty\n test_expect_success \\\n '.git/objects should be empty after git init in an empty repo.' \\\n 'cmp -s /dev/null should-be-empty'\n \n-# also it should have 2 subdirectories; no fan-out anymore, pack, and info.\n-# 3 is counting \"objects\" itself\n-find .git/objects -type d -print >full-of-directories\n+# also it should have 3 subdirectories;\n+# no fan-out anymore, pack, and info and crcs.\n+# 4 (listed by find) is the result of counting \"objects\" as well.\n+find .git/objects \\( -type d -o -name crcs \\) -print >full-of-directories\n test_expect_success \\\n- '.git/objects should have 3 subdirectories.' \\\n- 'test $(wc -l < full-of-directories) = 3'\n+ '.git/objects should have 3 subdirectories or files.' \\\n+ 'test $(wc -l < full-of-directories) = 4'\n \n ################################################################\n # Test harness\ndiff --git a/t/t5300-pack-object.sh b/t/t5300-pack-object.sh\nindex 602806d..880b425 100755\n--- a/t/t5300-pack-object.sh\n+++ b/t/t5300-pack-object.sh\n@@ -54,7 +54,7 @@ cd \"$TRASH/.git2\"\n \n test_expect_success \\\n 'check unpack without delta' \\\n- '(cd ../.git && find objects -type f -print) |\n+ '(cd ../.git && find objects -type f -print) | grep -v crcs |\n while read path\n do\n cmp $path ../.git/$path || {\n@@ -84,7 +84,7 @@ unset GIT_OBJECT_DIRECTORY\n cd \"$TRASH/.git2\"\n test_expect_success \\\n 'check unpack with REF_DELTA' \\\n- '(cd ../.git && find objects -type f -print) |\n+ '(cd ../.git && find objects -type f -print) | grep -v crcs |\n while read path\n do\n cmp $path ../.git/$path || {\n@@ -114,7 +114,7 @@ unset GIT_OBJECT_DIRECTORY\n cd \"$TRASH/.git2\"\n test_expect_success \\\n 'check unpack with OFS_DELTA' \\\n- '(cd ../.git && find objects -type f -print) |\n+ '(cd ../.git && find objects -type f -print) | grep -v crcs |\n while read path\n do\n cmp $path ../.git/$path || {\n@@ -211,6 +211,17 @@ test_expect_success \\\n \t\t\ttest-3-${packname_3}.idx'\n \n test_expect_success \\\n+ 'verify pack -v -M' \\\n+ 'test -z \"`git verify-pack -v -M test-1-${packname_1}.idx \\\n+\t\t\ttest-2-${packname_2}.idx \\\n+\t\t\ttest-3-${packname_3}.idx | grep \\`\" &&\n+ test 0 != `git verify-pack -v -M test-1-${packname_1}.idx | grep md= | wc -l` &&\n+ test -z \"`git verify-pack -v -M test-1-${packname_1}.idx | grep \"should be\"`\" &&\n+ (x=`git verify-pack -v -M test-1-${packname_1}.idx | wc -l`\n+ y=`git verify-pack -v -M test-1-${packname_1}.idx |grep -v \\ | wc -l`\n+ test $x = $y)'\n+\n+test_expect_success \\\n 'verify-pack catches mismatched .idx and .pack files' \\\n 'cat test-1-${packname_1}.idx >test-3.idx &&\n cat test-2-${packname_2}.pack >test-3.pack &&\ndiff --git a/t/t5301-sliding-window.sh b/t/t5301-sliding-window.sh\nindex 2fc5af6..ec0d72f 100755\n--- a/t/t5301-sliding-window.sh\n+++ b/t/t5301-sliding-window.sh\n@@ -22,13 +22,19 @@ test_expect_success \\\n git repack -a -d &&\n test \"`git count-objects`\" = \"0 objects, 0 kilobytes\" &&\n pack1=`ls .git/objects/pack/*.pack` &&\n- test -f \"$pack1\"'\n+ test -f \"$pack1\" &&\n+ test -z \"`git count-objects -v -M | grep MD`\"'\n \n test_expect_success \\\n 'verify-pack -v, defaults' \\\n 'git verify-pack -v \"$pack1\"'\n \n test_expect_success \\\n+ 'verify-pack -v -M, defaults' \\\n+ 'git verify-pack -v -M \"$pack1\" | grep \"\" > tmp\n+ test -z \"`cat tmp`\"'\n+\n+test_expect_success \\\n 'verify-pack -v, packedGitWindowSize == 1 page' \\\n 'git config core.packedGitWindowSize 512 &&\n git verify-pack -v \"$pack1\"'\n@@ -49,12 +55,14 @@ test_expect_success \\\n test \"`git count-objects`\" = \"0 objects, 0 kilobytes\" &&\n pack2=`ls .git/objects/pack/*.pack` &&\n test -f \"$pack2\" &&\n- test \"$pack1\" \\!= \"$pack2\"'\n+ test \"$pack1\" \\!= \"$pack2\" &&\n+ test -z \"`git count-objects -v -M | grep MD`\"'\n \n test_expect_success \\\n 'verify-pack -v, defaults' \\\n 'git config --unset core.packedGitWindowSize &&\n git config --unset core.packedGitLimit &&\n- git verify-pack -v \"$pack2\"'\n+ git verify-pack -v \"$pack2\" &&\n+ test -z \"`git count-objects -v -M | grep MD`\"'\n \n test_done\ndiff --git a/t/t5302-pack-index.sh b/t/t5302-pack-index.sh\nindex f8fa924..da10200 100755\n--- a/t/t5302-pack-index.sh\n+++ b/t/t5302-pack-index.sh\n@@ -37,12 +37,14 @@ test_expect_success \\\n test_expect_success \\\n 'pack-objects with index version 1' \\\n 'pack1=$(git pack-objects --index-version=1 test-1 count.shallow &&\n-\tgrep \"^count: 52\" count.shallow\n+\tgrep \"^count: 52\" count.shallow &&\n+\ttest -z \"`git count-objects -v -M | grep MD`\"\n '\n \n test_done\ndiff --git a/t/t5510-fetch.sh b/t/t5510-fetch.sh\nindex e0af4c4..3ce6027 100755\n--- a/t/t5510-fetch.sh\n+++ b/t/t5510-fetch.sh\n@@ -14,6 +14,12 @@ test_bundle_object_count () {\n \ttest \"$2\" = $(grep '^[0-9a-f]\\{40\\} ' verify.out | wc -l)\n }\n \n+test_bundle_mds_count () {\n+\tgit verify-pack -v -M \"$1\" >verify.out &&\n+\ttest \"$2\" = $(grep '^[0-9a-f]\\{40\\} ' verify.out | grep -v \"\" | wc -l)\n+}\n+\n+\n test_expect_success setup '\n \techo >file original &&\n \tgit add file &&\n@@ -215,7 +221,8 @@ test_expect_success 'bundle 1 has only 3 files ' '\n \t\tcat\n \t) bundle.pack &&\n \tgit index-pack bundle.pack &&\n-\ttest_bundle_object_count bundle.pack 3\n+\ttest_bundle_object_count bundle.pack 3 &&\n+\ttest_bundle_mds_count bundle.pack 3\n '\n \n test_expect_success 'unbundle 2' '\n@@ -238,7 +245,8 @@ test_expect_success 'bundle does not prerequisite objects' '\n \t\tcat\n \t) bundle.pack &&\n \tgit index-pack bundle.pack &&\n-\ttest_bundle_object_count bundle.pack 3\n+\ttest_bundle_object_count bundle.pack 3 &&\n+\ttest_bundle_mds_count bundle.pack 3\n '\n \n test_expect_success 'bundle should be able to create a full history' '\ndiff --git a/t/t9300-fast-import.sh b/t/t9300-fast-import.sh\nindex 438aaf6..63b4a13 100755\n--- a/t/t9300-fast-import.sh\n+++ b/t/t9300-fast-import.sh\n@@ -109,6 +109,12 @@ test_expect_success \\\n \t'A: verify pack' \\\n \t'for p in .git/objects/pack/*.pack;do git verify-pack $p||exit;done'\n \n+test_expect_success \\\n+\t'A: verify pack -v -M --- all objects have CRCs' \\\n+\t'for p in .git/objects/pack/*.pack;\n+\tdo git verify-pack -v -M $p | grep \"\" > tmp;\n+\t test -z \"`cat tmp`\" || exit; done'\n+\n cat >expect < $GIT_COMMITTER_DATE\n committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n@@ -1504,7 +1510,7 @@ INPUT_END\n test_expect_success \\\n \t'O: blank lines not necessary after other commands' \\\n \t'git fast-import actual &&\n \t test_cmp expect actual'\ndiff --git a/upload-pack.c b/upload-pack.c\nindex 470cffd..9721074 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -320,11 +320,32 @@ static int got_sha1(char *hex, unsigned char *sha1)\n {\n \tstruct object *o;\n \tint we_knew_they_have = 0;\n+\tint has_sha1_objcrc, has_objcrc32, has_sha1_blobcrc, has_blobcrc;\n+\tuint32_t sha1_objcrc, objcrc32, sha1_blobcrc, blobcrc;\n \n-\tif (get_sha1_hex(hex, sha1))\n+\tif (get_sha1_hex_crc(hex, sha1, &has_sha1_objcrc, &sha1_objcrc,\n+\t\t\t &has_sha1_blobcrc, &sha1_blobcrc))\n \t\tdie(\"git upload-pack: expected SHA1 object, got '%s'\", hex);\n \tif (!has_sha1_file(sha1))\n \t\treturn -1;\n+\thas_sha1_objcrc = has_sha1_file_crc(sha1, &objcrc32);\n+\tif (has_sha1_objcrc && has_objcrc32 && objcrc32 != sha1_objcrc) {\n+\t\tdie(\"git upload-pack: SHA1 collision on MD for %s\", hex);\n+\t}\n+\thas_blobcrc = !get_blob_mds(sha1, &blobcrc);\n+\n+\tif (has_sha1_blobcrc) {\n+\t\tif (has_blobcrc) {\n+\t\t\tif (sha1_blobcrc != blobcrc) {\n+\t\t\t\tdie(\"git upload-pack: SHA1 collision \"\n+\t\t\t\t \"on blob-MD for %s\", hex);\n+\t\t\t}\n+\t\t} else {\n+#ifdef BLOB_MDS_CHECK\n+\t\t\tpush_mds_check(sha1, sha1_blobcrc);\n+#endif\n+\t\t}\n+\t}\n \n \to = lookup_object(sha1);\n \tif (!(o && o->parsed))\n@@ -719,7 +740,7 @@ static int send_ref(const char *refname, const unsigned char *sha1, int flag, vo\n {\n \tstatic const char *capabilities = \"multi_ack thin-pack side-band\"\n \t\t\" side-band-64k ofs-delta shallow no-progress\"\n-\t\t\" include-tag multi_ack_detailed\";\n+\t\t\" include-tag multi_ack_detailed mds-check\";\n \tstruct object *o = parse_object(sha1);\n \tconst char *refname_nons = strip_namespace(refname);\n \n@@ -775,6 +796,9 @@ static void upload_pack(void)\n \tif (want_obj.nr) {\n \t\tget_common_commits();\n \t\tcreate_pack_file();\n+#ifdef BLOB_MDS_CHECK\n+\t\tprocess_mds_checks(die);\n+#endif\n \t}\n }\n \n-- \n1.7.1\n"}]}