{"thread":{"id":"3400","subject":"[PATCH] Thin pack - create packfile with missing delta base.","startedAt":"2006-02-19T23:28:04Z","lastAt":"2006-02-19T23:28:04Z","messageCount":1,"participants":["Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"16432","messageId":"7vd5hjexob.fsf@assigned-by-dhcp.cox.net","threadId":"3400","inReplyTo":null,"subject":"[PATCH] Thin pack - create packfile with missing delta base.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-19T23:28:04Z","receivedAt":"2006-02-19T23:28:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This goes together with \"rev-list --object-edge\" change, to feed\npack-objects list of edge commits in addition to the usual\nobject list.  Upon seeing such list, pack-objects loosens the\nusual \"self contained delta\" constraints, and can produce delta\nagainst blobs and trees contained in the edge commits without\nstoring the delta base objects themselves.\n\nThe resulting packfile is not usable in .git/object/packs, but\nis a good way to implement \"delta-only\" transfer.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\n\n * For \"delta transfer\"; this comes on top of \"next\".\n\n pack-objects.c |  298 +++++++++++++++++++++++++++++++++++++++++---------------\n 1 files changed, 218 insertions(+), 80 deletions(-)\n\n630dcb88482d99b77f83e1ed67b24d4026183c81\ndiff --git a/pack-objects.c b/pack-objects.c\nindex 0c9f4c9..fc923c9 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -3,6 +3,7 @@\n #include \"delta.h\"\n #include \"pack.h\"\n #include \"csum-file.h\"\n+#include \"diff.h\"\n #include <sys/time.h>\n \n static const char pack_usage[] = \"git-pack-objects [-q] [--no-reuse-delta] [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] {--stdout | base-name} < object-list\";\n@@ -26,6 +27,13 @@ struct object_entry {\n \tstruct object_entry *delta_sibling; /* other deltified objects who\n \t\t\t\t\t     * uses the same base as me\n \t\t\t\t\t     */\n+\tint preferred_base;\t/* we do not pack this, but is encouraged to\n+\t\t\t\t * be used as the base objectto delta huge\n+\t\t\t\t * objects against.\n+\t\t\t\t */\n+\tint based_on_preferred;\t/* current delta candidate is a preferred\n+\t\t\t\t * one, or delta against a preferred one.\n+\t\t\t\t */\n };\n \n /*\n@@ -48,7 +56,7 @@ static int local = 0;\n static int incremental = 0;\n static struct object_entry **sorted_by_sha, **sorted_by_type;\n static struct object_entry *objects = NULL;\n-static int nr_objects = 0, nr_alloc = 0;\n+static int nr_objects = 0, nr_alloc = 0, nr_result = 0;\n static const char *base_name;\n static unsigned char pack_file_sha1[20];\n static int progress = 1;\n@@ -229,7 +237,8 @@ static int encode_header(enum object_typ\n \treturn n;\n }\n \n-static unsigned long write_object(struct sha1file *f, struct object_entry *entry)\n+static unsigned long write_object(struct sha1file *f,\n+\t\t\t\t  struct object_entry *entry)\n {\n \tunsigned long size;\n \tchar type[10];\n@@ -239,6 +248,9 @@ static unsigned long write_object(struct\n \tenum object_type obj_type;\n \tint to_reuse = 0;\n \n+\tif (entry->preferred_base)\n+\t\treturn 0;\n+\n \tobj_type = entry->type;\n \tif (! entry->in_pack)\n \t\tto_reuse = 0;\t/* can't reuse what we don't have */\n@@ -326,10 +338,11 @@ static void write_pack_file(void)\n \tif (!base_name)\n \t\tf = sha1fd(1, \"<stdout>\");\n \telse\n-\t\tf = sha1create(\"%s-%s.%s\", base_name, sha1_to_hex(object_list_sha1), \"pack\");\n+\t\tf = sha1create(\"%s-%s.%s\", base_name,\n+\t\t\t       sha1_to_hex(object_list_sha1), \"pack\");\n \thdr.hdr_signature = htonl(PACK_SIGNATURE);\n \thdr.hdr_version = htonl(PACK_VERSION);\n-\thdr.hdr_entries = htonl(nr_objects);\n+\thdr.hdr_entries = htonl(nr_result);\n \tsha1write(f, &hdr, sizeof(hdr));\n \toffset = sizeof(hdr);\n \tfor (i = 0; i < nr_objects; i++)\n@@ -341,9 +354,10 @@ static void write_pack_file(void)\n static void write_index_file(void)\n {\n \tint i;\n-\tstruct sha1file *f = sha1create(\"%s-%s.%s\", base_name, sha1_to_hex(object_list_sha1), \"idx\");\n+\tstruct sha1file *f = sha1create(\"%s-%s.%s\", base_name,\n+\t\t\t\t\tsha1_to_hex(object_list_sha1), \"idx\");\n \tstruct object_entry **list = sorted_by_sha;\n-\tstruct object_entry **last = list + nr_objects;\n+\tstruct object_entry **last = list + nr_result;\n \tunsigned int array[256];\n \n \t/*\n@@ -368,7 +382,7 @@ static void write_index_file(void)\n \t * Write the actual SHA1 entries..\n \t */\n \tlist = sorted_by_sha;\n-\tfor (i = 0; i < nr_objects; i++) {\n+\tfor (i = 0; i < nr_result; i++) {\n \t\tstruct object_entry *entry = *list++;\n \t\tunsigned int offset = htonl(entry->offset);\n \t\tsha1write(f, &offset, 4);\n@@ -378,27 +392,87 @@ static void write_index_file(void)\n \tsha1close(f, NULL, 1);\n }\n \n-static int add_object_entry(unsigned char *sha1, unsigned int hash)\n+static int locate_object_entry_hash(const unsigned char *sha1)\n+{\n+\tint i;\n+\tunsigned int ui;\n+\tmemcpy(&ui, sha1, sizeof(unsigned int));\n+\ti = ui % object_ix_hashsz;\n+\twhile (0 < object_ix[i]) {\n+\t\tif (!memcmp(sha1, objects[object_ix[i]-1].sha1, 20))\n+\t\t\treturn i;\n+\t\tif (++i == object_ix_hashsz)\n+\t\t\ti = 0;\n+\t}\n+\treturn -1 - i;\n+}\n+\n+static struct object_entry *locate_object_entry(const unsigned char *sha1)\n+{\n+\tint i;\n+\n+\tif (!object_ix_hashsz)\n+\t\treturn NULL;\n+\n+\ti = locate_object_entry_hash(sha1);\n+\tif (0 <= i)\n+\t\treturn &objects[object_ix[i]-1];\n+\treturn NULL;\n+}\n+\n+static void rehash_objects(void)\n {\n+\tint i;\n+\tstruct object_entry *oe;\n+\n+\tobject_ix_hashsz = nr_objects * 2;\n+\tif (object_ix_hashsz < 256)\n+\t\tobject_ix_hashsz = 256;\n+\tobject_ix = xrealloc(object_ix, sizeof(int) * object_ix_hashsz);\n+\tobject_ix = memset(object_ix, 0, sizeof(int) * object_ix_hashsz);\n+\tfor (i = 0, oe = objects; i < nr_objects; i++, oe++) {\n+\t\tint ix = locate_object_entry_hash(oe->sha1);\n+\t\tif (0 <= ix)\n+\t\t\tcontinue;\n+\t\tix = -1 - ix;\n+\t\tobject_ix[ix] = i + 1;\n+\t}\n+}\n+\n+static int add_object_entry(const unsigned char *sha1, const char *name, int exclude)\n+{\n+\tunsigned int hash = 0;\n \tunsigned int idx = nr_objects;\n \tstruct object_entry *entry;\n \tstruct packed_git *p;\n \tunsigned int found_offset = 0;\n \tstruct packed_git *found_pack = NULL;\n+\tint ix;\n \n-\tfor (p = packed_git; p; p = p->next) {\n-\t\tstruct pack_entry e;\n-\t\tif (find_pack_entry_one(sha1, &e, p)) {\n-\t\t\tif (incremental)\n-\t\t\t\treturn 0;\n-\t\t\tif (local && !p->pack_local)\n-\t\t\t\treturn 0;\n-\t\t\tif (!found_pack) {\n-\t\t\t\tfound_offset = e.offset;\n-\t\t\t\tfound_pack = e.p;\n+\tif (!exclude) {\n+\t\tfor (p = packed_git; p; p = p->next) {\n+\t\t\tstruct pack_entry e;\n+\t\t\tif (find_pack_entry_one(sha1, &e, p)) {\n+\t\t\t\tif (incremental)\n+\t\t\t\t\treturn 0;\n+\t\t\t\tif (local && !p->pack_local)\n+\t\t\t\t\treturn 0;\n+\t\t\t\tif (!found_pack) {\n+\t\t\t\t\tfound_offset = e.offset;\n+\t\t\t\t\tfound_pack = e.p;\n+\t\t\t\t}\n \t\t\t}\n \t\t}\n \t}\n+\tif ((entry = locate_object_entry(sha1)) != NULL)\n+\t\tgoto already_added;\n+\n+\twhile (*name) {\n+\t\tunsigned char c = *name++;\n+\t\tif (isspace(c))\n+\t\t\tcontinue;\n+\t\thash = hash * 11 + c;\n+\t}\n \n \tif (idx >= nr_alloc) {\n \t\tunsigned int needed = (idx + 1024) * 3 / 2;\n@@ -406,45 +480,79 @@ static int add_object_entry(unsigned cha\n \t\tnr_alloc = needed;\n \t}\n \tentry = objects + idx;\n+\tnr_objects = idx + 1;\n \tmemset(entry, 0, sizeof(*entry));\n \tmemcpy(entry->sha1, sha1, 20);\n \tentry->hash = hash;\n-\tif (found_pack) {\n-\t\tentry->in_pack = found_pack;\n-\t\tentry->in_pack_offset = found_offset;\n+\n+\tif (object_ix_hashsz <= nr_objects * 2)\n+\t\trehash_objects();\n+\telse {\n+\t\tix = locate_object_entry_hash(entry->sha1);\n+\t\tif (0 <= ix)\n+\t\t\tdie(\"internal error in object hashing.\");\n+\t\tobject_ix[-1 - ix] = idx + 1;\n+\t}\n+\n+ already_added:\n+\tif (exclude)\n+\t\tentry->preferred_base = 1;\n+\telse {\n+\t\tif (found_pack) {\n+\t\t\tentry->in_pack = found_pack;\n+\t\t\tentry->in_pack_offset = found_offset;\n+\t\t}\n \t}\n-\tnr_objects = idx+1;\n \treturn 1;\n }\n \n-static int locate_object_entry_hash(unsigned char *sha1)\n+static void add_pbase_tree(struct tree_desc *tree)\n {\n-\tint i;\n-\tunsigned int ui;\n-\tmemcpy(&ui, sha1, sizeof(unsigned int));\n-\ti = ui % object_ix_hashsz;\n-\twhile (0 < object_ix[i]) {\n-\t\tif (!memcmp(sha1, objects[object_ix[i]-1].sha1, 20))\n-\t\t\treturn i;\n-\t\tif (++i == object_ix_hashsz)\n-\t\t\ti = 0;\n+\twhile (tree->size) {\n+\t\tconst unsigned char *sha1;\n+\t\tconst char *name;\n+\t\tunsigned mode;\n+\t\tunsigned long size;\n+\t\tchar type[20];\n+\n+\t\tsha1 = tree_entry_extract(tree, &name, &mode);\n+\t\tupdate_tree_entry(tree);\n+\t\tif (!has_sha1_file(sha1))\n+\t\t\tcontinue;\n+\t\tif (sha1_object_info(sha1, type, &size))\n+\t\t\tcontinue;\n+\t\tadd_object_entry(sha1, name, 1);\n+\t\tif (!strcmp(type, \"tree\")) {\n+\t\t\tstruct tree_desc sub;\n+\t\t\tvoid *elem;\n+\t\t\telem = read_sha1_file(sha1, type, &sub.size);\n+\t\t\tsub.buf = elem;\n+\t\t\tif (sub.buf) {\n+\t\t\t\tadd_pbase_tree(&sub);\n+\t\t\t\tfree(elem);\n+\t\t\t}\n+\t\t}\n \t}\n-\treturn -1 - i;\n }\n \n-static struct object_entry *locate_object_entry(unsigned char *sha1)\n+static void add_preferred_base(unsigned char *sha1)\n {\n-\tint i = locate_object_entry_hash(sha1);\n-\tif (0 <= i)\n-\t\treturn &objects[object_ix[i]-1];\n-\treturn NULL;\n+\tstruct tree_desc tree;\n+\tvoid *elem;\n+\telem = read_object_with_reference(sha1, \"tree\", &tree.size, NULL);\n+\ttree.buf = elem;\n+\tif (!tree.buf)\n+\t\treturn;\n+\tadd_object_entry(sha1, \"\", 1);\n+\tadd_pbase_tree(&tree);\n+\tfree(elem);\n }\n \n static void check_object(struct object_entry *entry)\n {\n \tchar type[20];\n \n-\tif (entry->in_pack) {\n+\tif (entry->in_pack && !entry->preferred_base) {\n \t\tunsigned char base[20];\n \t\tunsigned long size;\n \t\tstruct object_entry *base_entry;\n@@ -463,7 +571,8 @@ static void check_object(struct object_e\n \t\t */\n \t\tif (!no_reuse_delta &&\n \t\t    entry->in_pack_type == OBJ_DELTA &&\n-\t\t    (base_entry = locate_object_entry(base))) {\n+\t\t    (base_entry = locate_object_entry(base)) &&\n+\t\t    (!base_entry->preferred_base)) {\n \n \t\t\t/* Depth value does not matter - find_deltas()\n \t\t\t * will never consider reused delta as the\n@@ -501,25 +610,6 @@ static void check_object(struct object_e\n \t\t    sha1_to_hex(entry->sha1), type);\n }\n \n-static void hash_objects(void)\n-{\n-\tint i;\n-\tstruct object_entry *oe;\n-\n-\tobject_ix_hashsz = nr_objects * 2;\n-\tobject_ix = xcalloc(sizeof(int), object_ix_hashsz);\n-\tfor (i = 0, oe = objects; i < nr_objects; i++, oe++) {\n-\t\tint ix = locate_object_entry_hash(oe->sha1);\n-\t\tif (0 <= ix) {\n-\t\t\terror(\"the same object '%s' added twice\",\n-\t\t\t      sha1_to_hex(oe->sha1));\n-\t\t\tcontinue;\n-\t\t}\n-\t\tix = -1 - ix;\n-\t\tobject_ix[ix] = i + 1;\n-\t}\n-}\n-\n static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)\n {\n \tstruct object_entry *child = me->delta_child;\n@@ -538,7 +628,6 @@ static void get_object_details(void)\n \tint i;\n \tstruct object_entry *entry;\n \n-\thash_objects();\n \tprepare_pack_ix();\n \tfor (i = 0, entry = objects; i < nr_objects; i++, entry++)\n \t\tcheck_object(entry);\n@@ -576,6 +665,24 @@ static int sha1_sort(const struct object\n \treturn memcmp(a->sha1, b->sha1, 20);\n }\n \n+static struct object_entry **create_final_object_list()\n+{\n+\tstruct object_entry **list;\n+\tint i, j;\n+\n+\tfor (i = nr_result = 0; i < nr_objects; i++)\n+\t\tif (!objects[i].preferred_base)\n+\t\t\tnr_result++;\n+\tlist = xmalloc(nr_result * sizeof(struct object_entry *));\n+\tfor (i = j = 0; i < nr_objects; i++) {\n+\t\tif (!objects[i].preferred_base)\n+\t\t\tlist[j++] = objects + i;\n+\t}\n+\tcurrent_sort = sha1_sort;\n+\tqsort(list, nr_result, sizeof(struct object_entry *), sort_comparator);\n+\treturn list;\n+}\n+\n static int type_size_sort(const struct object_entry *a, const struct object_entry *b)\n {\n \tif (a->type < b->type)\n@@ -586,6 +693,10 @@ static int type_size_sort(const struct o\n \t\treturn -1;\n \tif (a->hash > b->hash)\n \t\treturn 1;\n+\tif (a->preferred_base < b->preferred_base)\n+\t\treturn -1;\n+\tif (a->preferred_base > b->preferred_base)\n+\t\treturn 1;\n \tif (a->size < b->size)\n \t\treturn -1;\n \tif (a->size > b->size)\n@@ -610,6 +721,8 @@ static int try_delta(struct unpacked *cu\n {\n \tstruct object_entry *cur_entry = cur->entry;\n \tstruct object_entry *old_entry = old->entry;\n+\tint old_preferred = (old_entry->preferred_base ||\n+\t\t\t     old_entry->based_on_preferred);\n \tunsigned long size, oldsize, delta_size, sizediff;\n \tlong max_size;\n \tvoid *delta_buf;\n@@ -618,9 +731,15 @@ static int try_delta(struct unpacked *cu\n \tif (cur_entry->type != old_entry->type)\n \t\treturn -1;\n \n-\t/* If the current object is at edge, take the depth the objects\n-\t * that depend on the current object into account -- otherwise\n-\t * they would become too deep.\n+\t/* We do not compute delta to *create* objects we are not\n+\t * going to pack.\n+\t */\n+\tif (cur_entry->preferred_base)\n+\t\treturn -1;\n+\n+\t/* If the current object is at pack edge, take the depth the\n+\t * objects that depend on the current object into account --\n+\t * otherwise they would become too deep.\n \t */\n \tif (cur_entry->delta_child) {\n \t\tif (max_depth <= cur_entry->delta_limit)\n@@ -646,8 +765,27 @@ static int try_delta(struct unpacked *cu\n \t * delete).\n \t */\n \tmax_size = size / 2 - 20;\n-\tif (cur_entry->delta)\n-\t\tmax_size = cur_entry->delta_size-1;\n+\tif (cur_entry->delta) {\n+\t\tif (cur_entry->based_on_preferred) {\n+\t\t\tif (old_preferred)\n+\t\t\t\tmax_size = cur_entry->delta_size-1;\n+\t\t\telse\n+\t\t\t\t/* trying with non-preferred one when we\n+\t\t\t\t * already have a delta based on preferred\n+\t\t\t\t * one is pointless.\n+\t\t\t\t */\n+\t\t\t\treturn 0;\n+\t\t}\n+\t\telse if (!old_preferred)\n+\t\t\tmax_size = cur_entry->delta_size-1;\n+\t\telse\n+\t\t\t/* otherwise...  even if delta with a\n+\t\t\t * preferred one produces a bigger result than\n+\t\t\t * what we currently have, which is based on a\n+\t\t\t * non-preferred one, it is OK.\n+\t\t\t */\n+\t\t\t;\n+\t}\n \tif (sizediff >= max_size)\n \t\treturn -1;\n \tdelta_buf = diff_delta(old->data, oldsize,\n@@ -657,6 +795,7 @@ static int try_delta(struct unpacked *cu\n \tcur_entry->delta = old_entry;\n \tcur_entry->delta_size = delta_size;\n \tcur_entry->depth = old_entry->depth + 1;\n+\tcur_entry->based_on_preferred = old_preferred;\n \tfree(delta_buf);\n \treturn 0;\n }\n@@ -722,7 +861,7 @@ static void find_deltas(struct object_en\n static void prepare_pack(int window, int depth)\n {\n \tif (progress)\n-\t\tfprintf(stderr, \"Packing %d objects\", nr_objects);\n+\t\tfprintf(stderr, \"Packing %d objects\", nr_result);\n \tget_object_details();\n \tif (progress)\n \t\tfputc('.', stderr);\n@@ -861,8 +1000,6 @@ int main(int argc, char **argv)\n \t\tgettimeofday(&prev_tv, NULL);\n \t}\n \twhile (fgets(line, sizeof(line), stdin) != NULL) {\n-\t\tunsigned int hash;\n-\t\tchar *p;\n \t\tunsigned char sha1[20];\n \n \t\tif (progress && (eye_candy <= nr_objects)) {\n@@ -881,31 +1018,32 @@ int main(int argc, char **argv)\n \t\t\t}\n \t\t\teye_candy += eye_candy_incr;\n \t\t}\n+\t\tif (line[0] == '-') {\n+\t\t\tif (get_sha1_hex(line+1, sha1))\n+\t\t\t\tdie(\"expected edge sha1, got garbage:\\n %s\",\n+\t\t\t\t    line+1);\n+\t\t\tadd_preferred_base(sha1);\n+\t\t\tcontinue;\n+\t\t}\n \t\tif (get_sha1_hex(line, sha1))\n \t\t\tdie(\"expected sha1, got garbage:\\n %s\", line);\n-\t\thash = 0;\n-\t\tp = line+40;\n-\t\twhile (*p) {\n-\t\t\tunsigned char c = *p++;\n-\t\t\tif (isspace(c))\n-\t\t\t\tcontinue;\n-\t\t\thash = hash * 11 + c;\n-\t\t}\n-\t\tadd_object_entry(sha1, hash);\n+\t\tadd_object_entry(sha1, line+40, 0);\n \t}\n \tif (progress)\n \t\tfprintf(stderr, \"Done counting %d objects.\\n\", nr_objects);\n \tif (non_empty && !nr_objects)\n \t\treturn 0;\n \n-\tsorted_by_sha = create_sorted_list(sha1_sort);\n+\tsorted_by_sha = create_final_object_list();\n \tSHA1_Init(&ctx);\n \tlist = sorted_by_sha;\n-\tfor (i = 0; i < nr_objects; i++) {\n+\tfor (i = 0; i < nr_result; i++) {\n \t\tstruct object_entry *entry = *list++;\n \t\tSHA1_Update(&ctx, entry->sha1, 20);\n \t}\n \tSHA1_Final(object_list_sha1, &ctx);\n+\tif (progress && (nr_objects != nr_result))\n+\t\tfprintf(stderr, \"Result has %d objects.\\n\", nr_result);\n \n \tif (reuse_cached_pack(object_list_sha1, pack_to_stdout))\n \t\t;\n@@ -918,6 +1056,6 @@ int main(int argc, char **argv)\n \t}\n \tif (progress)\n \t\tfprintf(stderr, \"Total %d, written %d (delta %d), reused %d (delta %d)\\n\",\n-\t\t\tnr_objects, written, written_delta, reused, reused_delta);\n+\t\t\tnr_result, written, written_delta, reused, reused_delta);\n \treturn 0;\n }\n-- \n1.2.2.g0d27\n"}]}