{"thread":{"id":"677","subject":"[PATCH 2/3] delta check","startedAt":"2005-05-20T20:59:17Z","lastAt":"2005-05-20T20:59:17Z","messageCount":1,"participants":["Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"3645","messageId":"Pine.LNX.4.62.0505201657310.4397@localhost.localdomain","threadId":"677","inReplyTo":null,"subject":"[PATCH 2/3] delta check","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-20T20:59:17Z","receivedAt":"2005-05-20T20:59:17Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This patch adds knowledge of delta objects to fsck-cache and various\nobject parsing code.  A new switch to git-fsck-cache is provided to\ndisplay the maximum delta depth found in a repository.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\nIndex: git/fsck-cache.c\n===================================================================\n--- git.orig/fsck-cache.c\n+++ git/fsck-cache.c\n@@ -6,15 +6,46 @@\n #include \"tree.h\"\n #include \"blob.h\"\n #include \"tag.h\"\n+#include \"delta.h\"\n \n #define REACHABLE 0x0001\n \n static int show_root = 0;\n static int show_tags = 0;\n static int show_unreachable = 0;\n+static int show_max_delta_depth = 0;\n static int keep_cache_objects = 0; \n static unsigned char head_sha1[20];\n \n+static void expand_deltas(void)\n+{\n+\tint i, max_depth = 0;\n+\n+\t/*\n+\t * To be as efficient as possible we look for delta heads and\n+\t * recursively process them going backward, and parsing\n+\t * resulting objects along the way.  This allows for processing\n+\t * each delta objects only once regardless of the delta depth.\n+\t */\n+\tfor (i = 0; i < nr_objs; i++) {\n+\t\tstruct object *obj = objs[i];\n+\t\tif (obj->parsed && !obj->delta && obj->attached_deltas) {\n+\t\t\tint depth = 0;\n+\t\t\tchar type[10];\n+\t\t\tunsigned long size;\n+\t\t\tvoid *buf = read_sha1_file(obj->sha1, type, &size);\n+\t\t\tif (!buf)\n+\t\t\t\tcontinue;\n+\t\t\tdepth = process_deltas(buf, size, obj->type,\n+\t\t\t\t\t       obj->attached_deltas);\n+\t\t\tif (max_depth < depth)\n+\t\t\t\tmax_depth = depth;\n+\t\t}\n+\t}\n+\tif (show_max_delta_depth)\n+\t\tprintf(\"maximum delta depth = %d\\n\", max_depth);\n+}\n+\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\n static void check_connectivity(void)\n {\n \tint i;\n@@ -25,7 +56,12 @@\n \t\tstruct object_list *refs;\n \n \t\tif (!obj->parsed) {\n-\t\t\tprintf(\"missing %s %s\\n\", obj->type, sha1_to_hex(obj->sha1));\n+\t\t\tif (obj->delta)\n+\t\t\t\tprintf(\"unresolved delta %s\\n\",\n+\t\t\t\t       sha1_to_hex(obj->sha1));\n+\t\t\telse\n+\t\t\t\tprintf(\"missing %s %s\\n\",\n+\t\t\t\t       obj->type, sha1_to_hex(obj->sha1));\n \t\t\tcontinue;\n \t\t}\n \n@@ -43,7 +79,12 @@\n \t\t\tcontinue;\n \n \t\tif (show_unreachable && !(obj->flags & REACHABLE)) {\n-\t\t\tprintf(\"unreachable %s %s\\n\", obj->type, sha1_to_hex(obj->sha1));\n+\t\t\tif (obj->attached_deltas)\n+\t\t\t\tprintf(\"foreign delta reference %s\\n\", \n+\t\t\t\t       sha1_to_hex(obj->sha1));\n+\t\t\telse\n+\t\t\t\tprintf(\"unreachable %s %s\\n\",\n+\t\t\t\t       obj->type, sha1_to_hex(obj->sha1));\n \t\t\tcontinue;\n \t\t}\n \n@@ -201,6 +242,8 @@\n \t\treturn fsck_commit((struct commit *) obj);\n \tif (obj->type == tag_type)\n \t\treturn fsck_tag((struct tag *) obj);\n+\tif (!obj->type && obj->delta)\n+\t\treturn 0;\n \treturn -1;\n }\n \n@@ -384,6 +427,10 @@\n \t\t\tshow_root = 1;\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strcmp(arg, \"--delta-depth\")) {\n+\t\t\tshow_max_delta_depth = 1;\n+\t\t\tcontinue;\n+\t\t}\n \t\tif (!strcmp(arg, \"--cache\")) {\n \t\t\tkeep_cache_objects = 1;\n \t\t\tcontinue;\n@@ -400,6 +447,8 @@\n \t}\n \tfsck_sha1_list();\n \n+\texpand_deltas();\n+\n \theads = 0;\n \tfor (i = 1; i < argc; i++) {\n \t\tconst char *arg = argv[i]; \n@@ -423,7 +472,7 @@\n \t}\n \n \t/*\n-\t * If we've not been gived any explicit head information, do the\n+\t * If we've not been given any explicit head information, do the\n \t * default ones from .git/refs. We also consider the index file\n \t * in this case (ie this implies --cache).\n \t */\nIndex: git/delta.c\n===================================================================\n--- /dev/null\n+++ git/delta.c\n@@ -0,0 +1,115 @@\n+#include \"object.h\"\n+#include \"blob.h\"\n+#include \"tree.h\"\n+#include \"commit.h\"\n+#include \"tag.h\"\n+#include \"delta.h\"\n+#include \"cache.h\"\n+#include <string.h>\n+\n+/* the delta object definition (it can alias any other object) */\n+struct delta {\n+\tunion {\n+\t\tstruct object object;\n+\t\tstruct blob blob;\n+\t\tstruct tree tree;\n+\t\tstruct commit commit;\n+\t\tstruct tag tag;\n+\t} u;\n+};\n+\n+struct delta *lookup_delta(unsigned char *sha1)\n+{\n+\tstruct object *obj = lookup_object(sha1);\n+\tif (!obj) {\n+\t\tstruct delta *ret = xmalloc(sizeof(struct delta));\n+\t\tmemset(ret, 0, sizeof(struct delta));\n+\t\tcreated_object(sha1, &ret->u.object);\n+\t\treturn ret;\n+\t}\n+\treturn (struct delta *) obj;\n+}\n+\n+int parse_delta_buffer(struct delta *item, void *buffer, unsigned long size)\n+{\n+\tstruct object *reference;\n+\tstruct object_list *p;\n+\n+\tif (item->u.object.delta)\n+\t\treturn 0;\n+\titem->u.object.delta = 1;\n+\tif (size <= 20)\n+\t\treturn -1;\n+\treference = lookup_object(buffer);\n+\tif (!reference) {\n+\t\tstruct delta *ref = xmalloc(sizeof(struct delta));\n+\t\tmemset(ref, 0, sizeof(struct delta));\n+\t\tcreated_object(buffer, &ref->u.object);\n+\t\treference = &ref->u.object;\n+\t}\n+\n+\tp = xmalloc(sizeof(*p));\n+\tp->item = &item->u.object;\n+\tp->next = reference->attached_deltas;\n+\treference->attached_deltas = p;\n+\treturn 0;\n+}\n+\n+int process_deltas(void *src, unsigned long src_size, const char *src_type,\n+\t\t   struct object_list *delta_list)\n+{\n+\tint deepest = 0;\n+\tdo {\n+\t\tstruct object *obj = delta_list->item;\n+\t\tstatic char type[10];\n+\t\tvoid *map, *delta, *buf;\n+\t\tunsigned long map_size, delta_size, buf_size;\n+\t\tmap = map_sha1_file(obj->sha1, &map_size);\n+\t\tif (!map)\n+\t\t\tcontinue;\n+\t\tdelta = unpack_sha1_file(map, map_size, type, &delta_size);\n+\t\tmunmap(map, map_size);\n+\t\tif (!delta)\n+\t\t\tcontinue;\n+\t\tif (strcmp(type, \"delta\") || delta_size <= 20) {\n+\t\t\tfree(delta);\n+\t\t\tcontinue;\n+\t\t}\n+\t\tbuf = patch_delta(src, src_size,\n+\t\t\t\t  delta+20, delta_size-20,\n+\t\t\t\t  &buf_size);\n+\t\tfree(delta);\n+\t\tif (!buf)\n+\t\t\tcontinue;\n+\t\tif (check_sha1_signature(obj->sha1, buf, buf_size, src_type) < 0)\n+\t\t\tprintf(\"sha1 mismatch for delta %s\\n\", sha1_to_hex(obj->sha1));\n+\t\tif (obj->type && obj->type != src_type) {\n+\t\t\terror(\"got %s when expecting %s for delta %s\",\n+\t\t\t      src_type, obj->type, sha1_to_hex(obj->sha1));\n+\t\t\tfree(buf);\n+\t\t\tcontinue;\n+\t\t}\n+\t\tobj->type = src_type;\n+\t\tif (src_type == blob_type) {\n+\t\t\tparse_blob_buffer((struct blob *)obj, buf, buf_size);\n+\t\t} else if (src_type == tree_type) {\n+\t\t\tparse_tree_buffer((struct tree *)obj, buf, buf_size);\n+\t\t} else if (src_type == commit_type) {\n+\t\t\tparse_commit_buffer((struct commit *)obj, buf, buf_size);\n+\t\t} else if (src_type == tag_type) {\n+\t\t\tparse_tag_buffer((struct tag *)obj, buf, buf_size);\n+\t\t} else {\n+\t\t\terror(\"unknown object type %s\", src_type);\n+\t\t\tfree(buf);\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (obj->attached_deltas) {\n+\t\t\tint depth = process_deltas(buf, buf_size, src_type,\n+\t\t\t\t\t\t   obj->attached_deltas);\n+\t\t\tif (deepest < depth)\n+\t\t\t\tdeepest = depth;\n+\t\t}\n+\t\tfree(buf);\n+\t} while ((delta_list = delta_list->next));\n+\treturn deepest + 1;\n+}\nIndex: git/tag.c\n===================================================================\n--- git.orig/tag.c\n+++ git/tag.c\n@@ -13,6 +13,8 @@\n                 ret->object.type = tag_type;\n                 return ret;\n         }\n+\tif (!obj->type)\n+\t\tobj->type = tag_type;\n         if (obj->type != tag_type) {\n                 error(\"Object %s is a %s, not a tree\", \n                       sha1_to_hex(sha1), obj->type);\nIndex: git/tree.c\n===================================================================\n--- git.orig/tree.c\n+++ git/tree.c\n@@ -83,6 +83,8 @@\n \t\tret->object.type = tree_type;\n \t\treturn ret;\n \t}\n+\tif (!obj->type)\n+\t\tobj->type = tree_type;\n \tif (obj->type != tree_type) {\n \t\terror(\"Object %s is a %s, not a tree\", \n \t\t      sha1_to_hex(sha1), obj->type);\nIndex: git/blob.c\n===================================================================\n--- git.orig/blob.c\n+++ git/blob.c\n@@ -14,6 +14,8 @@\n \t\tret->object.type = blob_type;\n \t\treturn ret;\n \t}\n+\tif (!obj->type)\n+\t\tobj->type = blob_type;\n \tif (obj->type != blob_type) {\n \t\terror(\"Object %s is a %s, not a blob\", \n \t\t      sha1_to_hex(sha1), obj->type);\nIndex: git/delta.h\n===================================================================\n--- git.orig/delta.h\n+++ git/delta.h\n@@ -1,6 +1,21 @@\n+#ifndef DELTA_H\n+#define DELTA_H\n+\n+/* handling of delta buffers */\n extern void *diff_delta(void *from_buf, unsigned long from_size,\n \t\t\tvoid *to_buf, unsigned long to_size,\n \t\t        unsigned long *delta_size);\n extern void *patch_delta(void *src_buf, unsigned long src_size,\n \t\t\t void *delta_buf, unsigned long delta_size,\n \t\t\t unsigned long *dst_size);\n+\n+/* handling of delta objects */\n+struct delta;\n+struct object_list;\n+extern struct delta *lookup_delta(unsigned char *sha1);\n+extern int parse_delta_buffer(struct delta *item, void *buffer, unsigned long size);\n+extern int parse_delta(struct delta *item, unsigned char sha1);\n+extern int process_deltas(void *src, unsigned long src_size,\n+\t\t\t  const char *src_type, struct object_list *delta);\n+\n+#endif\nIndex: git/commit.c\n===================================================================\n--- git.orig/commit.c\n+++ git/commit.c\n@@ -37,6 +37,8 @@\n \t\tret->object.type = commit_type;\n \t\treturn ret;\n \t}\n+\tif (!obj->type)\n+\t\tobj->type = commit_type;\n \treturn check_commit(obj, sha1);\n }\n \nIndex: git/object.c\n===================================================================\n--- git.orig/object.c\n+++ git/object.c\n@@ -4,6 +4,7 @@\n #include \"commit.h\"\n #include \"cache.h\"\n #include \"tag.h\"\n+#include \"delta.h\"\n #include <stdlib.h>\n #include <string.h>\n \n@@ -104,6 +105,7 @@\n \tunsigned long mapsize;\n \tvoid *map = map_sha1_file(sha1, &mapsize);\n \tif (map) {\n+\t\tint is_delta;\n \t\tstruct object *obj;\n \t\tchar type[100];\n \t\tunsigned long size;\n@@ -111,9 +113,14 @@\n \t\tmunmap(map, mapsize);\n \t\tif (!buffer)\n \t\t\treturn NULL;\n-\t\tif (check_sha1_signature(sha1, buffer, size, type) < 0)\n+\t\tis_delta = !strcmp(type, \"delta\");\n+\t\tif (!is_delta && check_sha1_signature(sha1, buffer, size, type) < 0)\n \t\t\tprintf(\"sha1 mismatch %s\\n\", sha1_to_hex(sha1));\n-\t\tif (!strcmp(type, \"blob\")) {\n+\t\tif (is_delta) {\n+\t\t\tstruct delta *delta = lookup_delta(sha1);\n+\t\t\tparse_delta_buffer(delta, buffer, size);\n+\t\t\tobj = (struct object *) delta;\n+\t\t} else if (!strcmp(type, \"blob\")) {\n \t\t\tstruct blob *blob = lookup_blob(sha1);\n \t\t\tparse_blob_buffer(blob, buffer, size);\n \t\t\tobj = &blob->object;\nIndex: git/Makefile\n===================================================================\n--- git.orig/Makefile\n+++ git/Makefile\n@@ -36,7 +36,7 @@\n \t$(INSTALL) $(PROG) $(SCRIPTS) $(dest)$(bin)\n \n LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o \\\n-\t tag.o date.o index.o diff-delta.o patch-delta.o\n+\t tag.o delta.o date.o index.o diff-delta.o patch-delta.o\n LIB_FILE=libgit.a\n LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h\n \nIndex: git/object.h\n===================================================================\n--- git.orig/object.h\n+++ git/object.h\n@@ -9,10 +9,12 @@\n struct object {\n \tunsigned parsed : 1;\n \tunsigned used : 1;\n+\tunsigned delta : 1;\n \tunsigned int flags;\n \tunsigned char sha1[20];\n \tconst char *type;\n \tstruct object_list *refs;\n+\tstruct object_list *attached_deltas;\n };\n \n extern int nr_objs;\n"}]}