{"thread":{"id":"34774","subject":"[PATCH 02/23] export packed_object_info()","startedAt":"2013-08-27T04:25:44Z","lastAt":"2013-09-07T08:05:05Z","messageCount":83,"participants":["Nicolas Pitre","Nguyễn Thái Ngọc Duy","Junio C Hamano","Duy Nguyen"],"isPatch":true,"patchVersion":1,"patchTotal":23},"messages":[{"id":"225967","messageId":"1377577567-27655-1-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":null,"subject":"[PATCH 00/23] Preliminary pack v4 support","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:25:44Z","receivedAt":"2013-08-27T04:25:44Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Subject says it all... at last !\n\nThis can also be fetched here:\n\n\tgit://git.linaro.org/people/nico/git\n\nDemonstration of what it does at the moment:\n\n\thttp://article.gmane.org/gmane.comp.version-control.git/233038\n\nI'd like to preserve the author time stamps as they relate to where in\nthe world I was when the corresponding code was written. You'll notice\nI didn't work on the code in the same order as it is now presented.\n\nStill open question: what to do with a thin pack. Should we really\ncomplete it with local objects upon reception, or were we only over\nparanoid at the time we imposed this rule? Fixing a thin pack version 4\ncould be possible but not very eleguant. Hence my pondering about\nrelaxing this rule.\n\nComments welcome !\n\n\nNicolas\n"},{"id":"225977","messageId":"1377577567-27655-2-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 01/23] pack v4: initial pack dictionary structure and code","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:25:45Z","receivedAt":"2013-08-27T04:25:45Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Signed-off-by: Nicolas Pitre \n---\n packv4-create.c | 137 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 137 insertions(+)\n create mode 100644 packv4-create.c\n\ndiff --git a/packv4-create.c b/packv4-create.c\nnew file mode 100644\nindex 0000000..2de6d41\n--- /dev/null\n+++ b/packv4-create.c\n@@ -0,0 +1,137 @@\n+/*\n+ * packv4-create.c: management of dictionary tables used in pack v4\n+ *\n+ * (C) Nicolas Pitre \n+ *\n+ * This code is free software; you can redistribute it and/or modify\n+ * it under the terms of the GNU General Public License version 2 as\n+ * published by the Free Software Foundation.\n+ */\n+\n+#include \"cache.h\"\n+\n+struct data_entry {\n+\tunsigned offset;\n+\tunsigned hits;\n+};\n+\n+struct dict_table {\n+\tchar *data;\n+\tunsigned ptr;\n+\tunsigned size;\n+\tstruct data_entry *entry;\n+\tunsigned nb_entries;\n+\tunsigned max_entries;\n+\tunsigned *hash;\n+\tunsigned hash_size;\n+};\n+\n+struct dict_table *create_dict_table(void)\n+{\n+\treturn xcalloc(sizeof(struct dict_table), 1);\n+}\n+\n+void destroy_dict_table(struct dict_table *t)\n+{\n+\tfree(t->data);\n+\tfree(t->entry);\n+\tfree(t->hash);\n+\tfree(t);\n+}\n+\n+static int locate_entry(struct dict_table *t, const char *str)\n+{\n+\tint i = 0;\n+\tconst unsigned char *s = (const unsigned char *) str;\n+\n+\twhile (*s)\n+\t\ti = i * 111 + *s++;\n+\ti = (unsigned)i % t->hash_size;\n+\n+\twhile (t->hash[i]) {\n+\t\tunsigned n = t->hash[i] - 1;\n+\t\tif (!strcmp(str, t->data + t->entry[n].offset))\n+\t\t\treturn n;\n+\t\tif (++i >= t->hash_size)\n+\t\t\ti = 0;\n+\t}\n+\treturn -1 - i;\n+}\n+\n+static void rehash_entries(struct dict_table *t)\n+{\n+\tunsigned n;\n+\n+\tt->hash_size *= 2;\n+\tif (t->hash_size < 1024)\n+\t\tt->hash_size = 1024;\n+\tt->hash = xrealloc(t->hash, t->hash_size * sizeof(*t->hash));\n+\tmemset(t->hash, 0, t->hash_size * sizeof(*t->hash));\n+\n+\tfor (n = 0; n < t->nb_entries; n++) {\n+\t\tint i = locate_entry(t, t->data + t->entry[n].offset);\n+\t\tif (i < 0)\n+\t\t\tt->hash[-1 - i] = n + 1;\n+\t}\n+}\n+\n+int dict_add_entry(struct dict_table *t, const char *str)\n+{\n+\tint i, len = strlen(str) + 1;\n+\n+\tif (t->ptr + len >= t->size) {\n+\t\tt->size = (t->size + len + 1024) * 3 / 2;\n+\t\tt->data = xrealloc(t->data, t->size);\n+\t}\n+\tmemcpy(t->data + t->ptr, str, len);\n+\n+\ti = (t->nb_entries) ? locate_entry(t, t->data + t->ptr) : -1;\n+\tif (i >= 0) {\n+\t\tt->entry[i].hits++;\n+\t\treturn i;\n+\t}\n+\n+\tif (t->nb_entries >= t->max_entries) {\n+\t\tt->max_entries = (t->max_entries + 1024) * 3 / 2;\n+\t\tt->entry = xrealloc(t->entry, t->max_entries * sizeof(*t->entry));\n+\t}\n+\tt->entry[t->nb_entries].offset = t->ptr;\n+\tt->entry[t->nb_entries].hits = 1;\n+\tt->ptr += len + 1;\n+\tt->nb_entries++;\n+\n+\tif (t->hash_size * 3 <= t->nb_entries * 4)\n+\t\trehash_entries(t);\n+\telse\n+\t\tt->hash[-1 - i] = t->nb_entries;\n+\n+\treturn t->nb_entries - 1;\n+}\n+\n+static int cmp_dict_entries(const void *a_, const void *b_)\n+{\n+\tconst struct data_entry *a = a_;\n+\tconst struct data_entry *b = b_;\n+\tint diff = b->hits - a->hits;\n+\tif (!diff)\n+\t\tdiff = a->offset - b->offset;\n+\treturn diff;\n+}\n+\n+static void sort_dict_entries_by_hits(struct dict_table *t)\n+{\n+\tqsort(t->entry, t->nb_entries, sizeof(*t->entry), cmp_dict_entries);\n+\tt->hash_size = (t->nb_entries * 4 / 3) / 2;\n+\trehash_entries(t);\n+}\n+\n+void dict_dump(struct dict_table *t)\n+{\n+\tint i;\n+\n+\tsort_dict_entries_by_hits(t);\n+\tfor (i = 0; i < t->nb_entries; i++)\n+\t\tprintf(\"%d\\t%s\\n\",\n+\t\t\tt->entry[i].hits,\n+\t\t\tt->data + t->entry[i].offset);\n+}\n-- \n1.8.4.22.g54757b7\n"},{"id":"225954","messageId":"1377577567-27655-3-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 02/23] export packed_object_info()","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:25:46Z","receivedAt":"2013-08-27T04:25:46Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Signed-off-by: Nicolas Pitre \n---\n cache.h | 1 +\n sha1_file.c | 4 ++--\n 2 files changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 85b544f..b6634c4 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1160,6 +1160,7 @@ struct object_info {\n \t} u;\n };\n extern int sha1_object_info_extended(const unsigned char *, struct object_info *);\n+extern int packed_object_info(struct packed_git *, off_t, struct object_info *);\n \n /* Dumb servers support */\n extern int update_server_info(int);\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 8e27db1..c2020d0 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1782,8 +1782,8 @@ unwind:\n \tgoto out;\n }\n \n-static int packed_object_info(struct packed_git *p, off_t obj_offset,\n-\t\t\t struct object_info *oi)\n+int packed_object_info(struct packed_git *p, off_t obj_offset,\n+\t\t struct object_info *oi)\n {\n \tstruct pack_window *w_curs = NULL;\n \tunsigned long size;\n-- \n1.8.4.22.g54757b7\n"},{"id":"225969","messageId":"1377577567-27655-4-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 03/23] pack v4: scan tree objects","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:25:47Z","receivedAt":"2013-08-27T04:25:47Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"From: Nicolas Pitre \n\nLet's read a pack to feed our dictionary with all the path strings\ncontained in all the tree objects.\n\nDump the resulting dictionary sorted by frequency to stdout.\n\nSigned-off-by: Nicolas Pitre \n---\n Makefile | 1 +\n packv4-create.c | 137 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 138 insertions(+)\n\ndiff --git a/Makefile b/Makefile\nindex 3588ca1..4716113 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -550,6 +550,7 @@ PROGRAM_OBJS += shell.o\n PROGRAM_OBJS += show-index.o\n PROGRAM_OBJS += upload-pack.o\n PROGRAM_OBJS += remote-testsvn.o\n+PROGRAM_OBJS += packv4-create.o\n \n # Binary suffix, set to .exe for Windows builds\n X =\ndiff --git a/packv4-create.c b/packv4-create.c\nindex 2de6d41..00762a5 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -9,6 +9,8 @@\n */\n \n #include \"cache.h\"\n+#include \"object.h\"\n+#include \"tree-walk.h\"\n \n struct data_entry {\n \tunsigned offset;\n@@ -125,6 +127,22 @@ static void sort_dict_entries_by_hits(struct dict_table *t)\n \trehash_entries(t);\n }\n \n+static struct dict_table *tree_path_table;\n+\n+static int add_tree_dict_entries(void *buf, unsigned long size)\n+{\n+\tstruct tree_desc desc;\n+\tstruct name_entry name_entry;\n+\n+\tif (!tree_path_table)\n+\t\ttree_path_table = create_dict_table();\n+\n+\tinit_tree_desc(&desc, buf, size);\n+\twhile (tree_entry(&desc, &name_entry))\n+\t\tdict_add_entry(tree_path_table, name_entry.path);\n+\treturn 0;\n+}\n+\n void dict_dump(struct dict_table *t)\n {\n \tint i;\n@@ -135,3 +153,122 @@ void dict_dump(struct dict_table *t)\n \t\t\tt->entry[i].hits,\n \t\t\tt->data + t->entry[i].offset);\n }\n+\n+struct idx_entry\n+{\n+\toff_t offset;\n+\tconst unsigned char *sha1;\n+};\n+\n+static int sort_by_offset(const void *e1, const void *e2)\n+{\n+\tconst struct idx_entry *entry1 = e1;\n+\tconst struct idx_entry *entry2 = e2;\n+\tif (entry1->offset < entry2->offset)\n+\t\treturn -1;\n+\tif (entry1->offset > entry2->offset)\n+\t\treturn 1;\n+\treturn 0;\n+}\n+static int create_pack_dictionaries(struct packed_git *p)\n+{\n+\tuint32_t nr_objects, i;\n+\tstruct idx_entry *objects;\n+\n+\tnr_objects = p->num_objects;\n+\tobjects = xmalloc((nr_objects + 1) * sizeof(*objects));\n+\tobjects[nr_objects].offset = p->index_size - 40;\n+\tfor (i = 0; i < nr_objects; i++) {\n+\t\tobjects[i].sha1 = nth_packed_object_sha1(p, i);\n+\t\tobjects[i].offset = nth_packed_object_offset(p, i);\n+\t}\n+\tqsort(objects, nr_objects, sizeof(*objects), sort_by_offset);\n+\n+\tfor (i = 0; i < nr_objects; i++) {\n+\t\tvoid *data;\n+\t\tenum object_type type;\n+\t\tunsigned long size;\n+\t\tstruct object_info oi = {};\n+\n+\t\toi.typep = &type;\n+\t\toi.sizep = &size;\n+\t\tif (packed_object_info(p, objects[i].offset, &oi) < 0)\n+\t\t\tdie(\"cannot get type of %s from %s\",\n+\t\t\t sha1_to_hex(objects[i].sha1), p->pack_name);\n+\n+\t\tswitch (type) {\n+\t\tcase OBJ_TREE:\n+\t\t\tbreak;\n+\t\tdefault:\n+\t\t\tcontinue;\n+\t\t}\n+\t\tdata = unpack_entry(p, objects[i].offset, &type, &size);\n+\t\tif (!data)\n+\t\t\tdie(\"cannot unpack %s from %s\",\n+\t\t\t sha1_to_hex(objects[i].sha1), p->pack_name);\n+\t\tif (check_sha1_signature(objects[i].sha1, data, size, typename(type)))\n+\t\t\tdie(\"packed %s from %s is corrupt\",\n+\t\t\t sha1_to_hex(objects[i].sha1), p->pack_name);\n+\t\tif (add_tree_dict_entries(data, size) < 0)\n+\t\t\tdie(\"can't process %s object %s\",\n+\t\t\t\ttypename(type), sha1_to_hex(objects[i].sha1));\n+\t\tfree(data);\n+\t}\n+\tfree(objects);\n+\n+\treturn 0;\n+}\n+\n+static int process_one_pack(const char *path)\n+{\n+\tchar arg[PATH_MAX];\n+\tint len;\n+\tstruct packed_git *p;\n+\n+\tlen = strlcpy(arg, path, PATH_MAX);\n+\tif (len >= PATH_MAX)\n+\t\treturn error(\"name too long: %s\", path);\n+\n+\t/*\n+\t * In addition to \"foo.idx\" we accept \"foo.pack\" and \"foo\";\n+\t * normalize these forms to \"foo.idx\" for add_packed_git().\n+\t */\n+\tif (has_extension(arg, \".pack\")) {\n+\t\tstrcpy(arg + len - 5, \".idx\");\n+\t\tlen--;\n+\t} else if (!has_extension(arg, \".idx\")) {\n+\t\tif (len + 4 >= PATH_MAX)\n+\t\t\treturn error(\"name too long: %s.idx\", arg);\n+\t\tstrcpy(arg + len, \".idx\");\n+\t\tlen += 4;\n+\t}\n+\n+\t/*\n+\t * add_packed_git() uses our buffer (containing \"foo.idx\") to\n+\t * build the pack filename (\"foo.pack\"). Make sure it fits.\n+\t */\n+\tif (len + 1 >= PATH_MAX) {\n+\t\targ[len - 4] = '\\0';\n+\t\treturn error(\"name too long: %s.pack\", arg);\n+\t}\n+\n+\tp = add_packed_git(arg, len, 1);\n+\tif (!p)\n+\t\treturn error(\"packfile %s not found.\", arg);\n+\n+\tinstall_packed_git(p);\n+\tif (open_pack_index(p))\n+\t\treturn error(\"packfile %s index not opened\", p->pack_name);\n+\treturn create_pack_dictionaries(p);\n+}\n+\n+int main(int argc, char *argv[])\n+{\n+\tif (argc != 2) {\n+\t\tfprintf(stderr, \"Usage: %s \\n\", argv[0]);\n+\t\texit(1);\n+\t}\n+\tprocess_one_pack(argv[1]);\n+\tdict_dump(tree_path_table);\n+\treturn 0;\n+}\n-- \n1.8.4.22.g54757b7\n"},{"id":"225966","messageId":"1377577567-27655-5-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 04/23] pack v4: add tree entry mode support to dictionary entries","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:25:48Z","receivedAt":"2013-08-27T04:25:48Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Augment dict entries with a 16-bit prefix in order to store the file\nmode value of tree entries.\n\nSigned-off-by: Nicolas Pitre \n---\n packv4-create.c | 56 ++++++++++++++++++++++++++++++++++++--------------------\n 1 file changed, 36 insertions(+), 20 deletions(-)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex 00762a5..eccd9fc 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -14,11 +14,12 @@\n \n struct data_entry {\n \tunsigned offset;\n+\tunsigned size;\n \tunsigned hits;\n };\n \n struct dict_table {\n-\tchar *data;\n+\tunsigned char *data;\n \tunsigned ptr;\n \tunsigned size;\n \tstruct data_entry *entry;\n@@ -41,18 +42,19 @@ void destroy_dict_table(struct dict_table *t)\n \tfree(t);\n }\n \n-static int locate_entry(struct dict_table *t, const char *str)\n+static int locate_entry(struct dict_table *t, const void *data, int size)\n {\n-\tint i = 0;\n-\tconst unsigned char *s = (const unsigned char *) str;\n+\tint i = 0, len = size;\n+\tconst unsigned char *p = data;\n \n-\twhile (*s)\n-\t\ti = i * 111 + *s++;\n+\twhile (len--)\n+\t\ti = i * 111 + *p++;\n \ti = (unsigned)i % t->hash_size;\n \n \twhile (t->hash[i]) {\n \t\tunsigned n = t->hash[i] - 1;\n-\t\tif (!strcmp(str, t->data + t->entry[n].offset))\n+\t\tif (t->entry[n].size == size &&\n+\t\t memcmp(t->data + t->entry[n].offset, data, size) == 0)\n \t\t\treturn n;\n \t\tif (++i >= t->hash_size)\n \t\t\ti = 0;\n@@ -71,23 +73,28 @@ static void rehash_entries(struct dict_table *t)\n \tmemset(t->hash, 0, t->hash_size * sizeof(*t->hash));\n \n \tfor (n = 0; n < t->nb_entries; n++) {\n-\t\tint i = locate_entry(t, t->data + t->entry[n].offset);\n+\t\tint i = locate_entry(t, t->data + t->entry[n].offset,\n+\t\t\t\t\tt->entry[n].size);\n \t\tif (i < 0)\n \t\t\tt->hash[-1 - i] = n + 1;\n \t}\n }\n \n-int dict_add_entry(struct dict_table *t, const char *str)\n+int dict_add_entry(struct dict_table *t, int val, const char *str)\n {\n-\tint i, len = strlen(str) + 1;\n+\tint i, val_len = 2, str_len = strlen(str) + 1;\n \n-\tif (t->ptr + len >= t->size) {\n-\t\tt->size = (t->size + len + 1024) * 3 / 2;\n+\tif (t->ptr + val_len + str_len > t->size) {\n+\t\tt->size = (t->size + val_len + str_len + 1024) * 3 / 2;\n \t\tt->data = xrealloc(t->data, t->size);\n \t}\n-\tmemcpy(t->data + t->ptr, str, len);\n \n-\ti = (t->nb_entries) ? locate_entry(t, t->data + t->ptr) : -1;\n+\tt->data[t->ptr] = val >> 8;\n+\tt->data[t->ptr + 1] = val;\n+\tmemcpy(t->data + t->ptr + val_len, str, str_len);\n+\n+\ti = (t->nb_entries) ?\n+\t\tlocate_entry(t, t->data + t->ptr, val_len + str_len) : -1;\n \tif (i >= 0) {\n \t\tt->entry[i].hits++;\n \t\treturn i;\n@@ -98,8 +105,9 @@ int dict_add_entry(struct dict_table *t, const char *str)\n \t\tt->entry = xrealloc(t->entry, t->max_entries * sizeof(*t->entry));\n \t}\n \tt->entry[t->nb_entries].offset = t->ptr;\n+\tt->entry[t->nb_entries].size = val_len + str_len;\n \tt->entry[t->nb_entries].hits = 1;\n-\tt->ptr += len + 1;\n+\tt->ptr += val_len + str_len;\n \tt->nb_entries++;\n \n \tif (t->hash_size * 3 <= t->nb_entries * 4)\n@@ -139,7 +147,8 @@ static int add_tree_dict_entries(void *buf, unsigned long size)\n \n \tinit_tree_desc(&desc, buf, size);\n \twhile (tree_entry(&desc, &name_entry))\n-\t\tdict_add_entry(tree_path_table, name_entry.path);\n+\t\tdict_add_entry(tree_path_table, name_entry.mode,\n+\t\t\t name_entry.path);\n \treturn 0;\n }\n \n@@ -148,10 +157,16 @@ void dict_dump(struct dict_table *t)\n \tint i;\n \n \tsort_dict_entries_by_hits(t);\n-\tfor (i = 0; i < t->nb_entries; i++)\n-\t\tprintf(\"%d\\t%s\\n\",\n-\t\t\tt->entry[i].hits,\n-\t\t\tt->data + t->entry[i].offset);\n+\tfor (i = 0; i < t->nb_entries; i++) {\n+\t\tint16_t val;\n+\t\tuint16_t uval;\n+\t\tval = t->data[t->entry[i].offset] << 8;\n+\t\tval |= t->data[t->entry[i].offset + 1];\n+\t\tuval = val;\n+\t\tprintf(\"%d\\t%d\\t%o\\t%s\\n\",\n+\t\t\tt->entry[i].hits, val, uval,\n+\t\t\tt->data + t->entry[i].offset + 2);\n+\t}\n }\n \n struct idx_entry\n@@ -170,6 +185,7 @@ static int sort_by_offset(const void *e1, const void *e2)\n \t\treturn 1;\n \treturn 0;\n }\n+\n static int create_pack_dictionaries(struct packed_git *p)\n {\n \tuint32_t nr_objects, i;\n-- \n1.8.4.22.g54757b7\n"},{"id":"225971","messageId":"1377577567-27655-6-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 05/23] pack v4: add commit object parsing","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:25:49Z","receivedAt":"2013-08-27T04:25:49Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Let's create another dictionary table to hold the author and committer\nentries. We use the same table format used for tree entries where the\n16 bit data prefix is conveniently used to store the timezone value.\n\nIn order to copy straight from a commit object buffer, dict_add_entry()\nis modified to get the string length as the provided string pointer is\nnot always be null terminated.\n\nSigned-off-by: Nicolas Pitre \n---\n packv4-create.c | 98 +++++++++++++++++++++++++++++++++++++++++++++++++++------\n 1 file changed, 89 insertions(+), 9 deletions(-)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex eccd9fc..5c08871 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -1,5 +1,5 @@\n /*\n- * packv4-create.c: management of dictionary tables used in pack v4\n+ * packv4-create.c: creation of dictionary tables and objects used in pack v4\n *\n * (C) Nicolas Pitre \n *\n@@ -80,9 +80,9 @@ static void rehash_entries(struct dict_table *t)\n \t}\n }\n \n-int dict_add_entry(struct dict_table *t, int val, const char *str)\n+int dict_add_entry(struct dict_table *t, int val, const char *str, int str_len)\n {\n-\tint i, val_len = 2, str_len = strlen(str) + 1;\n+\tint i, val_len = 2;\n \n \tif (t->ptr + val_len + str_len > t->size) {\n \t\tt->size = (t->size + val_len + str_len + 1024) * 3 / 2;\n@@ -92,6 +92,7 @@ int dict_add_entry(struct dict_table *t, int val, const char *str)\n \tt->data[t->ptr] = val >> 8;\n \tt->data[t->ptr + 1] = val;\n \tmemcpy(t->data + t->ptr + val_len, str, str_len);\n+\tt->data[t->ptr + val_len + str_len] = 0;\n \n \ti = (t->nb_entries) ?\n \t\tlocate_entry(t, t->data + t->ptr, val_len + str_len) : -1;\n@@ -107,7 +108,7 @@ int dict_add_entry(struct dict_table *t, int val, const char *str)\n \tt->entry[t->nb_entries].offset = t->ptr;\n \tt->entry[t->nb_entries].size = val_len + str_len;\n \tt->entry[t->nb_entries].hits = 1;\n-\tt->ptr += val_len + str_len;\n+\tt->ptr += val_len + str_len + 1;\n \tt->nb_entries++;\n \n \tif (t->hash_size * 3 <= t->nb_entries * 4)\n@@ -135,8 +136,73 @@ static void sort_dict_entries_by_hits(struct dict_table *t)\n \trehash_entries(t);\n }\n \n+static struct dict_table *commit_name_table;\n static struct dict_table *tree_path_table;\n \n+/*\n+ * Parse the author/committer line from a canonical commit object.\n+ * The 'from' argument points right after the \"author \" or \"committer \"\n+ * string. The time zone is parsed and stored in *tz_val. The returned\n+ * pointer is right after the end of the email address which is also just\n+ * before the time value, or NULL if a parsing error is encountered.\n+ */\n+static char *get_nameend_and_tz(char *from, int *tz_val)\n+{\n+\tchar *end, *tz;\n+\n+\ttz = strchr(from, '\\n');\n+\t/* let's assume the smallest possible string to be \"x 0 +0000\\n\" */\n+\tif (!tz || tz - from < 13)\n+\t\treturn NULL;\n+\ttz -= 4;\n+\tend = tz - 4;\n+\twhile (end - from > 5 && *end != ' ')\n+\t\tend--;\n+\tif (end[-1] != '>' || end[0] != ' ' || tz[-2] != ' ')\n+\t\treturn NULL;\n+\t*tz_val = (tz[0] - '0') * 1000 +\n+\t\t (tz[1] - '0') * 100 +\n+\t\t (tz[2] - '0') * 10 +\n+\t\t (tz[3] - '0');\n+\tswitch (tz[-1]) {\n+\tdefault:\treturn NULL;\n+\tcase '+':\tbreak;\n+\tcase '-':\t*tz_val = -*tz_val;\n+\t}\n+\treturn end;\n+}\n+\n+static int add_commit_dict_entries(void *buf, unsigned long size)\n+{\n+\tchar *name, *end = NULL;\n+\tint tz_val;\n+\n+\tif (!commit_name_table)\n+\t\tcommit_name_table = create_dict_table();\n+\n+\t/* parse and add author info */\n+\tname = strstr(buf, \"\\nauthor \");\n+\tif (name) {\n+\t\tname += 8;\n+\t\tend = get_nameend_and_tz(name, &tz_val);\n+\t}\n+\tif (!name || !end)\n+\t\treturn -1;\n+\tdict_add_entry(commit_name_table, tz_val, name, end - name);\n+\n+\t/* parse and add committer info */\n+\tname = strstr(end, \"\\ncommitter \");\n+\tif (name) {\n+\t name += 11;\n+\t end = get_nameend_and_tz(name, &tz_val);\n+\t}\n+\tif (!name || !end)\n+\t\treturn -1;\n+\tdict_add_entry(commit_name_table, tz_val, name, end - name);\n+\n+\treturn 0;\n+}\n+\n static int add_tree_dict_entries(void *buf, unsigned long size)\n {\n \tstruct tree_desc desc;\n@@ -146,13 +212,16 @@ static int add_tree_dict_entries(void *buf, unsigned long size)\n \t\ttree_path_table = create_dict_table();\n \n \tinit_tree_desc(&desc, buf, size);\n-\twhile (tree_entry(&desc, &name_entry))\n+\twhile (tree_entry(&desc, &name_entry)) {\n+\t\tint pathlen = tree_entry_len(&name_entry);\n \t\tdict_add_entry(tree_path_table, name_entry.mode,\n-\t\t\t name_entry.path);\n+\t\t\t\tname_entry.path, pathlen);\n+\t}\n+\n \treturn 0;\n }\n \n-void dict_dump(struct dict_table *t)\n+void dump_dict_table(struct dict_table *t)\n {\n \tint i;\n \n@@ -169,6 +238,12 @@ void dict_dump(struct dict_table *t)\n \t}\n }\n \n+static void dict_dump(void)\n+{\n+\tdump_dict_table(commit_name_table);\n+\tdump_dict_table(tree_path_table);\n+}\n+\n struct idx_entry\n {\n \toff_t offset;\n@@ -205,6 +280,7 @@ static int create_pack_dictionaries(struct packed_git *p)\n \t\tenum object_type type;\n \t\tunsigned long size;\n \t\tstruct object_info oi = {};\n+\t\tint (*add_dict_entries)(void *, unsigned long);\n \n \t\toi.typep = &type;\n \t\toi.sizep = &size;\n@@ -213,7 +289,11 @@ static int create_pack_dictionaries(struct packed_git *p)\n \t\t\t sha1_to_hex(objects[i].sha1), p->pack_name);\n \n \t\tswitch (type) {\n+\t\tcase OBJ_COMMIT:\n+\t\t\tadd_dict_entries = add_commit_dict_entries;\n+\t\t\tbreak;\n \t\tcase OBJ_TREE:\n+\t\t\tadd_dict_entries = add_tree_dict_entries;\n \t\t\tbreak;\n \t\tdefault:\n \t\t\tcontinue;\n@@ -225,7 +305,7 @@ static int create_pack_dictionaries(struct packed_git *p)\n \t\tif (check_sha1_signature(objects[i].sha1, data, size, typename(type)))\n \t\t\tdie(\"packed %s from %s is corrupt\",\n \t\t\t sha1_to_hex(objects[i].sha1), p->pack_name);\n-\t\tif (add_tree_dict_entries(data, size) < 0)\n+\t\tif (add_dict_entries(data, size) < 0)\n \t\t\tdie(\"can't process %s object %s\",\n \t\t\t\ttypename(type), sha1_to_hex(objects[i].sha1));\n \t\tfree(data);\n@@ -285,6 +365,6 @@ int main(int argc, char *argv[])\n \t\texit(1);\n \t}\n \tprocess_one_pack(argv[1]);\n-\tdict_dump(tree_path_table);\n+\tdict_dump();\n \treturn 0;\n }\n-- \n1.8.4.22.g54757b7\n"},{"id":"225970","messageId":"1377577567-27655-7-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 06/23] pack v4: split the object list and dictionary creation","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:25:50Z","receivedAt":"2013-08-27T04:25:50Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Signed-off-by: Nicolas Pitre \n---\n packv4-create.c | 58 +++++++++++++++++++++++++++++++++++++++++++--------------\n 1 file changed, 44 insertions(+), 14 deletions(-)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex 5c08871..20d97a4 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -261,7 +261,7 @@ static int sort_by_offset(const void *e1, const void *e2)\n \treturn 0;\n }\n \n-static int create_pack_dictionaries(struct packed_git *p)\n+static struct idx_entry *get_packed_object_list(struct packed_git *p)\n {\n \tuint32_t nr_objects, i;\n \tstruct idx_entry *objects;\n@@ -275,7 +275,15 @@ static int create_pack_dictionaries(struct packed_git *p)\n \t}\n \tqsort(objects, nr_objects, sizeof(*objects), sort_by_offset);\n \n-\tfor (i = 0; i < nr_objects; i++) {\n+\treturn objects;\n+}\n+\n+static int create_pack_dictionaries(struct packed_git *p,\n+\t\t\t\t struct idx_entry *objects)\n+{\n+\tunsigned int i;\n+\n+\tfor (i = 0; i < p->num_objects; i++) {\n \t\tvoid *data;\n \t\tenum object_type type;\n \t\tunsigned long size;\n@@ -310,20 +318,21 @@ static int create_pack_dictionaries(struct packed_git *p)\n \t\t\t\ttypename(type), sha1_to_hex(objects[i].sha1));\n \t\tfree(data);\n \t}\n-\tfree(objects);\n \n \treturn 0;\n }\n \n-static int process_one_pack(const char *path)\n+static struct packed_git *open_pack(const char *path)\n {\n \tchar arg[PATH_MAX];\n \tint len;\n \tstruct packed_git *p;\n \n \tlen = strlcpy(arg, path, PATH_MAX);\n-\tif (len >= PATH_MAX)\n-\t\treturn error(\"name too long: %s\", path);\n+\tif (len >= PATH_MAX) {\n+\t\terror(\"name too long: %s\", path);\n+\t\treturn NULL;\n+\t}\n \n \t/*\n \t * In addition to \"foo.idx\" we accept \"foo.pack\" and \"foo\";\n@@ -333,8 +342,10 @@ static int process_one_pack(const char *path)\n \t\tstrcpy(arg + len - 5, \".idx\");\n \t\tlen--;\n \t} else if (!has_extension(arg, \".idx\")) {\n-\t\tif (len + 4 >= PATH_MAX)\n-\t\t\treturn error(\"name too long: %s.idx\", arg);\n+\t\tif (len + 4 >= PATH_MAX) {\n+\t\t\terror(\"name too long: %s.idx\", arg);\n+\t\t\treturn NULL;\n+\t\t}\n \t\tstrcpy(arg + len, \".idx\");\n \t\tlen += 4;\n \t}\n@@ -345,17 +356,36 @@ static int process_one_pack(const char *path)\n \t */\n \tif (len + 1 >= PATH_MAX) {\n \t\targ[len - 4] = '\\0';\n-\t\treturn error(\"name too long: %s.pack\", arg);\n+\t\terror(\"name too long: %s.pack\", arg);\n+\t\treturn NULL;\n \t}\n \n \tp = add_packed_git(arg, len, 1);\n-\tif (!p)\n-\t\treturn error(\"packfile %s not found.\", arg);\n+\tif (!p) {\n+\t\terror(\"packfile %s not found.\", arg);\n+\t\treturn NULL;\n+\t}\n \n \tinstall_packed_git(p);\n-\tif (open_pack_index(p))\n-\t\treturn error(\"packfile %s index not opened\", p->pack_name);\n-\treturn create_pack_dictionaries(p);\n+\tif (open_pack_index(p)) {\n+\t\terror(\"packfile %s index not opened\", p->pack_name);\n+\t\treturn NULL;\n+\t}\n+\n+\treturn p;\n+}\n+\n+static void process_one_pack(char *src_pack)\n+{\n+\tstruct packed_git *p;\n+\tstruct idx_entry *objs;\n+\n+\tp = open_pack(src_pack);\n+\tif (!p)\n+\t\tdie(\"unable to open source pack\");\n+\n+\tobjs = get_packed_object_list(p);\n+\tcreate_pack_dictionaries(p, objs);\n }\n \n int main(int argc, char *argv[])\n-- \n1.8.4.22.g54757b7\n"},{"id":"225973","messageId":"1377577567-27655-8-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 07/23] pack v4: move to struct pack_idx_entry and get rid of our own struct idx_entry","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:25:51Z","receivedAt":"2013-08-27T04:25:51Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Let's create a struct pack_idx_entry list with sorted sha1 which will\nbe useful later. The offset sorted list is now a separate indirect\nlist.\n\nSigned-off-by: Nicolas Pitre \n---\n packv4-create.c | 72 +++++++++++++++++++++++++++++++++------------------------\n 1 file changed, 42 insertions(+), 30 deletions(-)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex 20d97a4..012129b 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -11,6 +11,7 @@\n #include \"cache.h\"\n #include \"object.h\"\n #include \"tree-walk.h\"\n+#include \"pack.h\"\n \n struct data_entry {\n \tunsigned offset;\n@@ -244,46 +245,53 @@ static void dict_dump(void)\n \tdump_dict_table(tree_path_table);\n }\n \n-struct idx_entry\n+static struct pack_idx_entry *get_packed_object_list(struct packed_git *p)\n {\n-\toff_t offset;\n-\tconst unsigned char *sha1;\n-};\n+\tunsigned i, nr_objects = p->num_objects;\n+\tstruct pack_idx_entry *objects;\n+\n+\tobjects = xmalloc((nr_objects + 1) * sizeof(*objects));\n+\tobjects[nr_objects].offset = p->pack_size - 20;\n+\tfor (i = 0; i < nr_objects; i++) {\n+\t\thashcpy(objects[i].sha1, nth_packed_object_sha1(p, i));\n+\t\tobjects[i].offset = nth_packed_object_offset(p, i);\n+\t}\n+\n+\treturn objects;\n+}\n \n static int sort_by_offset(const void *e1, const void *e2)\n {\n-\tconst struct idx_entry *entry1 = e1;\n-\tconst struct idx_entry *entry2 = e2;\n-\tif (entry1->offset < entry2->offset)\n+\tconst struct pack_idx_entry * const *entry1 = e1;\n+\tconst struct pack_idx_entry * const *entry2 = e2;\n+\tif ((*entry1)->offset < (*entry2)->offset)\n \t\treturn -1;\n-\tif (entry1->offset > entry2->offset)\n+\tif ((*entry1)->offset > (*entry2)->offset)\n \t\treturn 1;\n \treturn 0;\n }\n \n-static struct idx_entry *get_packed_object_list(struct packed_git *p)\n+static struct pack_idx_entry **sort_objs_by_offset(struct pack_idx_entry *list,\n+\t\t\t\t\t\t unsigned nr_objects)\n {\n-\tuint32_t nr_objects, i;\n-\tstruct idx_entry *objects;\n+\tunsigned i;\n+\tstruct pack_idx_entry **sorted;\n \n-\tnr_objects = p->num_objects;\n-\tobjects = xmalloc((nr_objects + 1) * sizeof(*objects));\n-\tobjects[nr_objects].offset = p->index_size - 40;\n-\tfor (i = 0; i < nr_objects; i++) {\n-\t\tobjects[i].sha1 = nth_packed_object_sha1(p, i);\n-\t\tobjects[i].offset = nth_packed_object_offset(p, i);\n-\t}\n-\tqsort(objects, nr_objects, sizeof(*objects), sort_by_offset);\n+\tsorted = xmalloc((nr_objects + 1) * sizeof(*sorted));\n+\tfor (i = 0; i < nr_objects + 1; i++)\n+\t\tsorted[i] = &list[i];\n+\tqsort(sorted, nr_objects + 1, sizeof(*sorted), sort_by_offset);\n \n-\treturn objects;\n+\treturn sorted;\n }\n \n static int create_pack_dictionaries(struct packed_git *p,\n-\t\t\t\t struct idx_entry *objects)\n+\t\t\t\t struct pack_idx_entry **obj_list)\n {\n \tunsigned int i;\n \n \tfor (i = 0; i < p->num_objects; i++) {\n+\t\tstruct pack_idx_entry *obj = obj_list[i];\n \t\tvoid *data;\n \t\tenum object_type type;\n \t\tunsigned long size;\n@@ -292,9 +300,9 @@ static int create_pack_dictionaries(struct packed_git *p,\n \n \t\toi.typep = &type;\n \t\toi.sizep = &size;\n-\t\tif (packed_object_info(p, objects[i].offset, &oi) < 0)\n+\t\tif (packed_object_info(p, obj->offset, &oi) < 0)\n \t\t\tdie(\"cannot get type of %s from %s\",\n-\t\t\t sha1_to_hex(objects[i].sha1), p->pack_name);\n+\t\t\t sha1_to_hex(obj->sha1), p->pack_name);\n \n \t\tswitch (type) {\n \t\tcase OBJ_COMMIT:\n@@ -306,16 +314,16 @@ static int create_pack_dictionaries(struct packed_git *p,\n \t\tdefault:\n \t\t\tcontinue;\n \t\t}\n-\t\tdata = unpack_entry(p, objects[i].offset, &type, &size);\n+\t\tdata = unpack_entry(p, obj->offset, &type, &size);\n \t\tif (!data)\n \t\t\tdie(\"cannot unpack %s from %s\",\n-\t\t\t sha1_to_hex(objects[i].sha1), p->pack_name);\n-\t\tif (check_sha1_signature(objects[i].sha1, data, size, typename(type)))\n+\t\t\t sha1_to_hex(obj->sha1), p->pack_name);\n+\t\tif (check_sha1_signature(obj->sha1, data, size, typename(type)))\n \t\t\tdie(\"packed %s from %s is corrupt\",\n-\t\t\t sha1_to_hex(objects[i].sha1), p->pack_name);\n+\t\t\t sha1_to_hex(obj->sha1), p->pack_name);\n \t\tif (add_dict_entries(data, size) < 0)\n \t\t\tdie(\"can't process %s object %s\",\n-\t\t\t\ttypename(type), sha1_to_hex(objects[i].sha1));\n+\t\t\t\ttypename(type), sha1_to_hex(obj->sha1));\n \t\tfree(data);\n \t}\n \n@@ -378,14 +386,18 @@ static struct packed_git *open_pack(const char *path)\n static void process_one_pack(char *src_pack)\n {\n \tstruct packed_git *p;\n-\tstruct idx_entry *objs;\n+\tstruct pack_idx_entry *objs, **p_objs;\n+\tunsigned nr_objects;\n \n \tp = open_pack(src_pack);\n \tif (!p)\n \t\tdie(\"unable to open source pack\");\n \n+\tnr_objects = p->num_objects;\n \tobjs = get_packed_object_list(p);\n-\tcreate_pack_dictionaries(p, objs);\n+\tp_objs = sort_objs_by_offset(objs, nr_objects);\n+\n+\tcreate_pack_dictionaries(p, p_objs);\n }\n \n int main(int argc, char *argv[])\n-- \n1.8.4.22.g54757b7\n"},{"id":"225976","messageId":"1377577567-27655-9-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 08/23] pack v4: basic references encoding","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:25:52Z","receivedAt":"2013-08-27T04:25:52Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Add variable length number encoding. Let's apply the same encoding\ncurrently used for the offset to base of OBJ_OFS_DELTA objects which\nis the most efficient way to do this, and apply it to everything with\npack version 4.\n\nAlso add SHA1 reference encoding. This one is either an index into a\nSHA1 table encoded using the variable length number encoding, or the\nliteral 20 bytes SHA1 prefixed with a 0.\n\nThe index 0 discriminates between an actual index value or the literal\nSHA1. Therefore when the index is used its value must be increased by 1.\n\nSigned-off-by: Nicolas Pitre \n---\n packv4-create.c | 44 ++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 44 insertions(+)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex 012129b..bf33d15 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -245,6 +245,50 @@ static void dict_dump(void)\n \tdump_dict_table(tree_path_table);\n }\n \n+/*\n+ * Encode a numerical value with variable length into the destination buffer\n+ */\n+static unsigned char *add_number(unsigned char *dst, uint64_t value)\n+{\n+\tunsigned char buf[20];\n+\tunsigned pos = sizeof(buf) - 1;\n+\tbuf[pos] = value & 127;\n+\twhile (value >>= 7)\n+\t\tbuf[--pos] = 128 | (--value & 127);\n+\tdo {\n+\t\t*dst++ = buf[pos++];\n+\t} while (pos < sizeof(buf));\n+\treturn dst;\n+}\n+\n+/*\n+ * Encode an object SHA1 reference with either an object index into the\n+ * pack SHA1 table incremented by 1, or the literal SHA1 value prefixed\n+ * with a zero byte if the needed SHA1 is not available in the table.\n+ */\n+static struct pack_idx_entry *all_objs;\n+static unsigned all_objs_nr;\n+static unsigned char *add_sha1_ref(unsigned char *dst, const unsigned char *sha1)\n+{\n+\tunsigned lo = 0, hi = all_objs_nr;\n+\n+\tdo {\n+\t\tunsigned mi = (lo + hi) / 2;\n+\t\tint cmp = hashcmp(all_objs[mi].sha1, sha1);\n+\n+\t\tif (cmp == 0)\n+\t\t\treturn add_number(dst, mi + 1);\n+\t\tif (cmp > 0)\n+\t\t\thi = mi;\n+\t\telse\n+\t\t\tlo = mi+1;\n+\t} while (lo < hi);\n+\n+\t*dst++ = 0;\n+\thashcpy(dst, sha1);\n+\treturn dst + 20;\n+}\n+\n static struct pack_idx_entry *get_packed_object_list(struct packed_git *p)\n {\n \tunsigned i, nr_objects = p->num_objects;\n-- \n1.8.4.22.g54757b7\n"},{"id":"225974","messageId":"1377577567-27655-10-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 09/23] pack v4: commit object encoding","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:25:53Z","receivedAt":"2013-08-27T04:25:53Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This goes as follows:\n\n- Tree reference: either variable length encoding of the index\n into the SHA1 table or the literal SHA1 prefixed by 0 (see\n add_sha1_ref()).\n\n- Parent count: variable length encoding of the number of parents.\n This is normally going to occupy a single byte but doesn't have to.\n\n- List of parent references: a list of add_sha1_ref() encoded references,\n or nothing if the parent count was zero.\n\n- Author reference: variable length encoding of an index into the author\n string dictionary table which also covers the time zone. To make the\n overall encoding efficient, the author table is already sorted by usage\n frequency so the most used names are first and require the shortest\n index encoding.\n\n- Author time stamp: variable length encoded. Year 2038 ready!\n\n- Committer reference: same as author reference.\n\n- Committer time stamp: same as author time stamp.\n\nThe remainder of the canonical commit object content is then zlib\ncompressed and appended to the above.\n\nRationale: The most important commit object data is densely encoded while\nrequiring no zlib inflate processing, and all SHA1 references are most\nlikely to be direct indices into the pack index file requiring no SHA1\nsearch into the pack index file.\n\nSigned-off-by: Nicolas Pitre \n---\n packv4-create.c | 119 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 119 insertions(+)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex bf33d15..cedbbd9 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -13,6 +13,9 @@\n #include \"tree-walk.h\"\n #include \"pack.h\"\n \n+\n+static int pack_compression_level = Z_DEFAULT_COMPRESSION;\n+\n struct data_entry {\n \tunsigned offset;\n \tunsigned size;\n@@ -289,6 +292,122 @@ static unsigned char *add_sha1_ref(unsigned char *dst, const unsigned char *sha1\n \treturn dst + 20;\n }\n \n+/*\n+ * This converts a canonical commit object buffer into its\n+ * tightly packed representation using the already populated\n+ * and sorted commit_name_table dictionary. The parsing is\n+ * strict so to ensure the canonical version may always be\n+ * regenerated and produce the same hash.\n+ */\n+void * conv_to_dict_commit(void *buffer, unsigned long *psize)\n+{\n+\tunsigned long size = *psize;\n+\tchar *in, *tail, *end;\n+\tunsigned char *out;\n+\tunsigned char sha1[20];\n+\tint nb_parents, index, tz_val;\n+\tunsigned long time;\n+\tz_stream stream;\n+\tint status;\n+\n+\t/*\n+\t * It is guaranteed that the output is always going to be smaller\n+\t * than the input. We could even do this conversion in place.\n+\t */\n+\tin = buffer;\n+\ttail = in + size;\n+\tbuffer = xmalloc(size);\n+\tout = buffer;\n+\n+\t/* parse the \"tree\" line */\n+\tif (in + 46 >= tail || memcmp(in, \"tree \", 5) || in[45] != '\\n')\n+\t\tgoto bad_data;\n+\tif (get_sha1_hex(in + 5, sha1) < 0)\n+\t\tgoto bad_data;\n+\tin += 46;\n+\tout = add_sha1_ref(out, sha1);\n+\n+\t/* count how many \"parent\" lines */\n+\tnb_parents = 0;\n+\twhile (in + 48 < tail && !memcmp(in, \"parent \", 7) && in[47] == '\\n') {\n+\t\tnb_parents++;\n+\t\tin += 48;\n+\t}\n+\tout = add_number(out, nb_parents);\n+\n+\t/* rewind and parse the \"parent\" lines */\n+\tin -= 48 * nb_parents;\n+\twhile (nb_parents--) {\n+\t\tif (get_sha1_hex(in + 7, sha1))\n+\t\t\tgoto bad_data;\n+\t\tout = add_sha1_ref(out, sha1);\n+\t\tin += 48;\n+\t}\n+\n+\t/* parse the \"author\" line */\n+\t/* it must be at least \"author x 0 +0000\\n\" i.e. 21 chars */\n+\tif (in + 21 >= tail || memcmp(in, \"author \", 7))\n+\t\tgoto bad_data;\n+\tin += 7;\n+\tend = get_nameend_and_tz(in, &tz_val);\n+\tif (!end)\n+\t\tgoto bad_data;\n+\tindex = dict_add_entry(commit_name_table, tz_val, in, end - in);\n+\tif (index < 0)\n+\t\tgoto bad_dict;\n+\tout = add_number(out, index);\n+\ttime = strtoul(end, &end, 10);\n+\tif (!end || end[0] != ' ' || end[6] != '\\n')\n+\t\tgoto bad_data;\n+\tout = add_number(out, time);\n+\tin = end + 7;\n+\n+\t/* parse the \"committer\" line */\n+\t/* it must be at least \"committer x 0 +0000\\n\" i.e. 24 chars */\n+\tif (in + 24 >= tail || memcmp(in, \"committer \", 7))\n+\t\tgoto bad_data;\n+\tin += 10;\n+\tend = get_nameend_and_tz(in, &tz_val);\n+\tif (!end)\n+\t\tgoto bad_data;\n+\tindex = dict_add_entry(commit_name_table, tz_val, in, end - in);\n+\tif (index < 0)\n+\t\tgoto bad_dict;\n+\tout = add_number(out, index);\n+\ttime = strtoul(end, &end, 10);\n+\tif (!end || end[0] != ' ' || end[6] != '\\n')\n+\t\tgoto bad_data;\n+\tout = add_number(out, time);\n+\tin = end + 7;\n+\n+\t/* finally, deflate the remaining data */\n+\tmemset(&stream, 0, sizeof(stream));\n+\tdeflateInit(&stream, pack_compression_level);\n+\tstream.next_in = (unsigned char *)in;\n+\tstream.avail_in = tail - in;\n+\tstream.next_out = (unsigned char *)out;\n+\tstream.avail_out = size - (out - (unsigned char *)buffer);\n+\tstatus = deflate(&stream, Z_FINISH);\n+\tend = (char *)stream.next_out;\n+\tdeflateEnd(&stream);\n+\tif (status != Z_STREAM_END) {\n+\t\terror(\"deflate error status %d\", status);\n+\t\tgoto bad;\n+\t}\n+\n+\t*psize = end - (char *)buffer;\n+\treturn buffer;\n+\n+bad_data:\n+\terror(\"bad commit data\");\n+\tgoto bad;\n+bad_dict:\n+\terror(\"bad dict entry\");\n+bad:\n+\tfree(buffer);\n+\treturn NULL;\n+}\n+\n static struct pack_idx_entry *get_packed_object_list(struct packed_git *p)\n {\n \tunsigned i, nr_objects = p->num_objects;\n-- \n1.8.4.22.g54757b7\n"},{"id":"225975","messageId":"1377577567-27655-11-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 10/23] pack v4: tree object encoding","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:25:54Z","receivedAt":"2013-08-27T04:25:54Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This goes as follows:\n\n- Number of tree entries: variable length encoded.\n\nThen for each tree entry:\n\n- Path component reference: variable length encoded index into the path\n string dictionary table which also covers the entry mode. To make the\n overall encoding efficient, the author table is already sorted by usage\n frequency so the most used names are first and require the shortest\n index encoding.\n\n- SHA1 reference: either variable length encoding of the index into the\n SHA1 table or the literal SHA1 prefixed by 0 (see add_sha1_ref()).\n\nRationale: all the tree object data is densely encoded while requiring\nno zlib inflate processing, and all SHA1 references are most likely to\nbe direct indices into the pack index file requiring no SHA1 search.\nPath filtering can be accomplished on the path index directly without\nany string comparison during the tree traversal.\n\nStill lacking is some kind of delta encoding for multiple tree objects\nwith only small differences between them. But that'll come later.\n\nSigned-off-by: Nicolas Pitre \n---\n packv4-create.c | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 63 insertions(+)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex cedbbd9..f46fbd9 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -408,6 +408,69 @@ bad:\n \treturn NULL;\n }\n \n+/*\n+ * This converts a canonical tree object buffer into its\n+ * tightly packed representation using the already populated\n+ * and sorted tree_path_table dictionary. The parsing is\n+ * strict so to ensure the canonical version may always be\n+ * regenerated and produce the same hash.\n+ */\n+void * conv_to_dict_tree(void *buffer, unsigned long *psize)\n+{\n+\tunsigned long size = *psize;\n+\tunsigned char *in, *out, *end;\n+\tstruct tree_desc desc;\n+\tstruct name_entry name_entry;\n+\tint nb_entries;\n+\n+\tif (!size)\n+\t\treturn NULL;\n+\n+\t/*\n+\t * We can't make sure the result will always be smaller.\n+\t * The smallest possible entry is \"0 x\\0<40 byte SHA1>\"\n+\t * or 44 bytes. The output entry may have a realistic path index\n+\t * encoding using up to 3 bytes, and a non indexable SHA1 meaning\n+\t * 41 bytes. And the output data already has the and nb_entries\n+\t * headers. In practice the output size will be significantly\n+\t * smaller but for now let's make it simple.\n+\t */\n+\tin = buffer;\n+\tout = xmalloc(size);\n+\tend = out + size;\n+\tbuffer = out;\n+\n+\t/* let's count how many entries there are */\n+\tinit_tree_desc(&desc, in, size);\n+\tnb_entries = 0;\n+\twhile (tree_entry(&desc, &name_entry))\n+\t\tnb_entries++;\n+\tout = add_number(out, nb_entries);\n+\n+\tinit_tree_desc(&desc, in, size);\n+\twhile (tree_entry(&desc, &name_entry)) {\n+\t\tint pathlen = tree_entry_len(&name_entry);\n+\t\tint index = dict_add_entry(tree_path_table, name_entry.mode,\n+\t\t\t\t\t name_entry.path, pathlen);\n+\t\tif (index < 0) {\n+\t\t\terror(\"missing tree dict entry\");\n+\t\t\tfree(buffer);\n+\t\t\treturn NULL;\n+\t\t}\n+\t\tif (end - out < 45) {\n+\t\t\tunsigned long sofar = out - (unsigned char *)buffer;\n+\t\t\tbuffer = xrealloc(buffer, sofar + 45);\n+\t\t\tout = (unsigned char *)buffer + sofar;\n+\t\t\tend = out + 45;\n+\t\t}\n+\t\tout = add_number(out, index);\n+\t\tout = add_sha1_ref(out, name_entry.sha1);\n+\t}\n+\n+\t*psize = out - (unsigned char *)buffer;\n+\treturn buffer;\n+}\n+\n static struct pack_idx_entry *get_packed_object_list(struct packed_git *p)\n {\n \tunsigned i, nr_objects = p->num_objects;\n-- \n1.8.4.22.g54757b7\n"},{"id":"225968","messageId":"1377577567-27655-12-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 11/23] pack v4: dictionary table output","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:25:55Z","receivedAt":"2013-08-27T04:25:55Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Here's the code to dump a table into a pack. Table entries are written\naccording to the current sort order. This is important as objects use\nthis order to index into the table.\n\nSigned-off-by: Nicolas Pitre \n---\n packv4-create.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 49 insertions(+)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex f46fbd9..2956fda 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -556,6 +556,55 @@ static int create_pack_dictionaries(struct packed_git *p,\n \treturn 0;\n }\n \n+static unsigned long write_dict_table(struct sha1file *f, struct dict_table *t)\n+{\n+\tunsigned char buffer[1024], *end;\n+\tunsigned hdrlen;\n+\tunsigned long size, datalen;\n+\tz_stream stream;\n+\tint i, status;\n+\n+\t/*\n+\t * Stored dict table format: uncompressed data length followed by\n+\t * compressed content.\n+\t */\n+\n+\tdatalen = t->ptr;\n+\tend = add_number(buffer, datalen);\n+\thdrlen = end - buffer;\n+\tsha1write(f, buffer, hdrlen);\n+\n+\tmemset(&stream, 0, sizeof(stream));\n+\tdeflateInit(&stream, pack_compression_level);\n+\n+\tfor (i = 0; i < t->nb_entries; i++) {\n+\t\tstream.next_in = t->data + t->entry[i].offset;\n+\t\tstream.avail_in = 2 + strlen((char *)t->data + t->entry[i].offset + 2) + 1;\n+\t\tdo {\n+\t\t\tstream.next_out = (unsigned char *)buffer;\n+\t\t\tstream.avail_out = sizeof(buffer);\n+\t\t\tstatus = deflate(&stream, 0);\n+\t\t\tsize = stream.next_out - (unsigned char *)buffer;\n+\t\t\tsha1write(f, buffer, size);\n+\t\t} while (status == Z_OK);\n+\t}\n+\tdo {\n+\t\tstream.next_out = (unsigned char *)buffer;\n+\t\tstream.avail_out = sizeof(buffer);\n+\t\tstatus = deflate(&stream, Z_FINISH);\n+\t\tsize = stream.next_out - (unsigned char *)buffer;\n+\t\tsha1write(f, buffer, size);\n+\t} while (status == Z_OK);\n+\tif (status != Z_STREAM_END)\n+\t\tdie(\"unable to deflate dictionary table (%d)\", status);\n+\tif (stream.total_in != datalen)\n+\t\tdie(\"dict data size mismatch (%ld vs %ld)\",\n+\t\t stream.total_in, datalen);\n+\tdeflateEnd(&stream);\n+\n+\treturn hdrlen + datalen;\n+}\n+\n static struct packed_git *open_pack(const char *path)\n {\n \tchar arg[PATH_MAX];\n-- \n1.8.4.22.g54757b7\n"},{"id":"225965","messageId":"1377577567-27655-13-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 12/23] pack v4: creation code","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:25:56Z","receivedAt":"2013-08-27T04:25:56Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Let's actually open the destination pack file and write the header and\nthe tables.\n\nThe header isn't much different from pack v3, except for the pack version\nnumber of course.\n\nThe first table is the sorted SHA1 table normally found in the pack index\nfile. With pack v4 we write this table in the main pack file instead as\nit is index referenced by subsequent objects in the pack. Doing so has\nmany advantages:\n\n- The SHA1 references used to be duplicated on disk: once in the pack\n index file, and then at least once or more within commit and tree\n objects referencing them. The only SHA1 which is not being listed more\n than once this way is the one for a branch tip commit object and those\n are normally very few. Now all that SHA1 data is represented only once.\n\n- The SHA1 references found in commit and tree objects can be obtained\n on disk directly without having to deflate those objects first.\n\nThe SHA1 table size is obtained by multiplying the number of objects by 20.\n\nAnd then the commit and path dictionary tables are written right after\nthe SHA1 table.\n\nSigned-off-by: Nicolas Pitre \n---\n packv4-create.c | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++-----\n 1 file changed, 55 insertions(+), 5 deletions(-)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex 2956fda..5211f9c 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -605,6 +605,48 @@ static unsigned long write_dict_table(struct sha1file *f, struct dict_table *t)\n \treturn hdrlen + datalen;\n }\n \n+static struct sha1file * packv4_open(char *path)\n+{\n+\tint fd;\n+\n+\tfd = open(path, O_CREAT|O_EXCL|O_WRONLY, 0600);\n+\tif (fd < 0)\n+\t\tdie_errno(\"unable to create '%s'\", path);\n+\treturn sha1fd(fd, path);\n+}\n+\n+static unsigned int packv4_write_header(struct sha1file *f, unsigned nr_objects)\n+{\n+\tstruct pack_header hdr;\n+\n+\thdr.hdr_signature = htonl(PACK_SIGNATURE);\n+\thdr.hdr_version = htonl(4);\n+\thdr.hdr_entries = htonl(nr_objects);\n+\tsha1write(f, &hdr, sizeof(hdr));\n+\n+\treturn sizeof(hdr);\n+}\n+\n+static unsigned long packv4_write_tables(struct sha1file *f, unsigned nr_objects,\n+\t\t\t\t\t struct pack_idx_entry *objs)\n+{\n+\tunsigned i;\n+\tunsigned long written = 0;\n+\n+\t/* The sorted list of object SHA1's is always first */\n+\tfor (i = 0; i < nr_objects; i++)\n+\t\tsha1write(f, objs[i].sha1, 20);\n+\twritten = 20 * nr_objects;\n+\n+\t/* Then the commit dictionary table */\n+\twritten += write_dict_table(f, commit_name_table);\n+\n+\t/* Followed by the path component dictionary table */\n+\twritten += write_dict_table(f, tree_path_table);\n+\n+\treturn written;\n+}\n+\n static struct packed_git *open_pack(const char *path)\n {\n \tchar arg[PATH_MAX];\n@@ -658,9 +700,10 @@ static struct packed_git *open_pack(const char *path)\n \treturn p;\n }\n \n-static void process_one_pack(char *src_pack)\n+static void process_one_pack(char *src_pack, char *dst_pack)\n {\n \tstruct packed_git *p;\n+\tstruct sha1file *f;\n \tstruct pack_idx_entry *objs, **p_objs;\n \tunsigned nr_objects;\n \n@@ -673,15 +716,22 @@ static void process_one_pack(char *src_pack)\n \tp_objs = sort_objs_by_offset(objs, nr_objects);\n \n \tcreate_pack_dictionaries(p, p_objs);\n+\n+\tf = packv4_open(dst_pack);\n+\tif (!f)\n+\t\tdie(\"unable to open destination pack\");\n+\tpackv4_write_header(f, nr_objects);\n+\tpackv4_write_tables(f, nr_objects, objs);\n }\n \n int main(int argc, char *argv[])\n {\n-\tif (argc != 2) {\n-\t\tfprintf(stderr, \"Usage: %s \\n\", argv[0]);\n+\tif (argc != 3) {\n+\t\tfprintf(stderr, \"Usage: %s \\n\", argv[0]);\n \t\texit(1);\n \t}\n-\tprocess_one_pack(argv[1]);\n-\tdict_dump();\n+\tprocess_one_pack(argv[1], argv[2]);\n+\tif (0)\n+\t\tdict_dump();\n \treturn 0;\n }\n-- \n1.8.4.22.g54757b7\n"},{"id":"225972","messageId":"1377577567-27655-14-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 13/23] pack v4: object headers","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:25:57Z","receivedAt":"2013-08-27T04:25:57Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"In pack v4 the object size and type is encoded differently from pack v3.\nThe object size uses the same efficient variable length number encoding\nalready used elsewhere.\n\nThe object type has 4 bits allocated to it compared to 3 bits in pack v3.\nThis should be quite sufficient for the foreseeable future, especially\nsince pack v4 has only one type of delta object instead of two.\n\nSigned-off-by: Nicolas Pitre \n---\n packv4-create.c | 26 ++++++++++++++++++++++++++\n 1 file changed, 26 insertions(+)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex 5211f9c..6e0bb1d 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -647,6 +647,32 @@ static unsigned long packv4_write_tables(struct sha1file *f, unsigned nr_objects\n \treturn written;\n }\n \n+static unsigned int write_object_header(struct sha1file *f, enum object_type type, unsigned long size)\n+{\n+\tunsigned char buf[30], *end;\n+\tuint64_t val;\n+\n+\t/*\n+\t * We really have only one kind of delta object.\n+\t */\n+\tif (type == OBJ_OFS_DELTA)\n+\t\ttype = OBJ_REF_DELTA;\n+\n+\t/*\n+\t * We allocate 4 bits in the LSB for the object type which should\n+\t * be good for quite a while, given that we effectively encodes\n+\t * only 5 object types: commit, tree, blob, delta, tag.\n+\t */\n+\tval = size;\n+\tif (MSB(val, 4))\n+\t\tdie(\"fixme: the code doesn't currently cope with big sizes\");\n+\tval <<= 4;\n+\tval |= type;\n+\tend = add_number(buf, val);\n+\tsha1write(f, buf, end - buf);\n+\treturn end - buf;\n+}\n+\n static struct packed_git *open_pack(const char *path)\n {\n \tchar arg[PATH_MAX];\n-- \n1.8.4.22.g54757b7\n"},{"id":"225964","messageId":"1377577567-27655-15-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 14/23] pack v4: object data copy","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:25:58Z","receivedAt":"2013-08-27T04:25:58Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Blob and tag objects have no particular changes except for their object\nheader.\n\nDelta objects are also copied as is, except for their delta base reference\nwhich is converted to the new way as used elsewhere in pack v4 encoding\ni.e. an index into the SHA1 table or a literal SHA1 prefixed by 0 if not\nfound in the table (see add_sha1_ref). This is true for both REF_DELTA\nas well as OFS_DELTA.\n\nObject payload is validated against the recorded CRC32 in the source\npack index file when possible.\n\nSigned-off-by: Nicolas Pitre \n---\n packv4-create.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 66 insertions(+)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex 6e0bb1d..a6dc818 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -12,6 +12,7 @@\n #include \"object.h\"\n #include \"tree-walk.h\"\n #include \"pack.h\"\n+#include \"pack-revindex.h\"\n \n \n static int pack_compression_level = Z_DEFAULT_COMPRESSION;\n@@ -673,6 +674,71 @@ static unsigned int write_object_header(struct sha1file *f, enum object_type typ\n \treturn end - buf;\n }\n \n+static unsigned long copy_object_data(struct sha1file *f, struct packed_git *p,\n+\t\t\t\t off_t offset)\n+{\n+\tstruct pack_window *w_curs = NULL;\n+\tstruct revindex_entry *revidx;\n+\tenum object_type type;\n+\tunsigned long avail, size, datalen, written;\n+\tint hdrlen, idx_nr;\n+\tunsigned char *src, *end, buf[24];\n+\n+\trevidx = find_pack_revindex(p, offset);\n+\tidx_nr = revidx->nr;\n+\tdatalen = revidx[1].offset - offset;\n+\n+\tsrc = use_pack(p, &w_curs, offset, &avail);\n+\thdrlen = unpack_object_header_buffer(src, avail, &type, &size);\n+\n+\twritten = write_object_header(f, type, size);\n+\n+\tif (type == OBJ_OFS_DELTA) {\n+\t\tunsigned char c = src[hdrlen++];\n+\t\toff_t base_offset = c & 127;\n+\t\twhile (c & 128) {\n+\t\t\tbase_offset += 1;\n+\t\t\tif (!base_offset || MSB(base_offset, 7))\n+\t\t\t\tdie(\"delta offset overflow\");\n+\t\t\tc = src[hdrlen++];\n+\t\t\tbase_offset = (base_offset << 7) + (c & 127);\n+\t\t}\n+\t\tbase_offset = offset - base_offset;\n+\t\tif (base_offset <= 0 || base_offset >= offset)\n+\t\t\tdie(\"delta offset out of bound\");\n+\t\trevidx = find_pack_revindex(p, base_offset);\n+\t\tend = add_sha1_ref(buf, nth_packed_object_sha1(p, revidx->nr));\n+\t\tsha1write(f, buf, end - buf);\n+\t\twritten += end - buf;\n+\t} else if (type == OBJ_REF_DELTA) {\n+\t\tend = add_sha1_ref(buf, src + hdrlen);\n+\t\thdrlen += 20;\n+\t\tsha1write(f, buf, end - buf);\n+\t\twritten += end - buf;\n+\t}\n+\n+\tif (p->index_version > 1 &&\n+\t check_pack_crc(p, &w_curs, offset, datalen, idx_nr))\n+\t\tdie(\"bad CRC for object at offset %\"PRIuMAX\" in %s\",\n+\t\t (uintmax_t)offset, p->pack_name);\n+\n+\toffset += hdrlen;\n+\tdatalen -= hdrlen;\n+\n+\twhile (datalen) {\n+\t\tsrc = use_pack(p, &w_curs, offset, &avail);\n+\t\tif (avail > datalen)\n+\t\t\tavail = datalen;\n+\t\tsha1write(f, src, avail);\n+\t\twritten += avail;\n+\t\toffset += avail;\n+\t\tdatalen -= avail;\n+\t}\n+\tunuse_pack(&w_curs);\n+\n+\treturn written;\n+}\n+\n static struct packed_git *open_pack(const char *path)\n {\n \tchar arg[PATH_MAX];\n-- \n1.8.4.22.g54757b7\n"},{"id":"225959","messageId":"1377577567-27655-16-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 15/23] pack v4: object writing","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:25:59Z","receivedAt":"2013-08-27T04:25:59Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This adds the missing code to finally be able to produce a complete\npack file version 4. We trap commit and tree objects as those have\na completely new encoding. Other object types are copied almost\nunchanged.\n\nAs we go the pack index entries are updated in place to store the new\nobject offsets once they're written to the destination file. This will\nbe needed later for writing the pack index file.\n\nSigned-off-by: Nicolas Pitre \n---\n packv4-create.c | 74 ++++++++++++++++++++++++++++++++++++++++++++++++++++++---\n 1 file changed, 71 insertions(+), 3 deletions(-)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex a6dc818..a9e4fb3 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -739,6 +739,59 @@ static unsigned long copy_object_data(struct sha1file *f, struct packed_git *p,\n \treturn written;\n }\n \n+static off_t packv4_write_object(struct sha1file *f, struct packed_git *p,\n+\t\t\t\t struct pack_idx_entry *obj)\n+{\n+\tvoid *src, *result;\n+\tstruct object_info oi = {};\n+\tenum object_type type;\n+\tunsigned long size;\n+\tunsigned int hdrlen;\n+\n+\toi.typep = &type;\n+\toi.sizep = &size;\n+\tif (packed_object_info(p, obj->offset, &oi) < 0)\n+\t\tdie(\"cannot get type of %s from %s\",\n+\t\t sha1_to_hex(obj->sha1), p->pack_name);\n+\n+\t/* Some objects are copied without decompression */\n+\tswitch (type) {\n+\tcase OBJ_COMMIT:\n+\tcase OBJ_TREE:\n+\t\tbreak;\n+\tdefault:\n+\t\treturn copy_object_data(f, p, obj->offset);\n+\t}\n+\n+\t/* The rest is converted into their new format */\n+\tsrc = unpack_entry(p, obj->offset, &type, &size);\n+\tif (!src)\n+\t\tdie(\"cannot unpack %s from %s\",\n+\t\t sha1_to_hex(obj->sha1), p->pack_name);\n+\tif (check_sha1_signature(obj->sha1, src, size, typename(type)))\n+\t\tdie(\"packed %s from %s is corrupt\",\n+\t\t sha1_to_hex(obj->sha1), p->pack_name);\n+\n+\tswitch (type) {\n+\tcase OBJ_COMMIT:\n+\t\tresult = conv_to_dict_commit(src, &size);\n+\t\tbreak;\n+\tcase OBJ_TREE:\n+\t\tresult = conv_to_dict_tree(src, &size);\n+\t\tbreak;\n+\tdefault:\n+\t\tdie(\"unexpected object type %d\", type);\n+\t}\n+\tfree(src);\n+\tif (!result && size)\n+\t\tdie(\"can't convert %s object %s\",\n+\t\t typename(type), sha1_to_hex(obj->sha1));\n+\thdrlen = write_object_header(f, type, size);\n+\tsha1write(f, result, size);\n+\tfree(result);\n+\treturn hdrlen + size;\n+}\n+\n static struct packed_git *open_pack(const char *path)\n {\n \tchar arg[PATH_MAX];\n@@ -797,7 +850,8 @@ static void process_one_pack(char *src_pack, char *dst_pack)\n \tstruct packed_git *p;\n \tstruct sha1file *f;\n \tstruct pack_idx_entry *objs, **p_objs;\n-\tunsigned nr_objects;\n+\tunsigned i, nr_objects;\n+\toff_t written = 0;\n \n \tp = open_pack(src_pack);\n \tif (!p)\n@@ -808,12 +862,26 @@ static void process_one_pack(char *src_pack, char *dst_pack)\n \tp_objs = sort_objs_by_offset(objs, nr_objects);\n \n \tcreate_pack_dictionaries(p, p_objs);\n+\tsort_dict_entries_by_hits(commit_name_table);\n+\tsort_dict_entries_by_hits(tree_path_table);\n \n \tf = packv4_open(dst_pack);\n \tif (!f)\n \t\tdie(\"unable to open destination pack\");\n-\tpackv4_write_header(f, nr_objects);\n-\tpackv4_write_tables(f, nr_objects, objs);\n+\twritten += packv4_write_header(f, nr_objects);\n+\twritten += packv4_write_tables(f, nr_objects, objs);\n+\n+\t/* Let's write objects out, updating the object index list in place */\n+\tall_objs = objs;\n+\tall_objs_nr = nr_objects;\n+\tfor (i = 0; i < nr_objects; i++) {\n+\t\toff_t obj_pos = written;\n+\t\tstruct pack_idx_entry *obj = p_objs[i];\n+\t\twritten += packv4_write_object(f, p, obj);\n+\t\tobj->offset = obj_pos;\n+\t}\n+\n+\tsha1close(f, NULL, CSUM_CLOSE | CSUM_FSYNC);\n }\n \n int main(int argc, char *argv[])\n-- \n1.8.4.22.g54757b7\n"},{"id":"225956","messageId":"1377577567-27655-17-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 16/23] pack v4: tree object delta encoding","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:26:00Z","receivedAt":"2013-08-27T04:26:00Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"In order to be able to quickly walk tree objects, let's encode their\n\"delta\" as a range of entries into another tree object.\n\nThe encoding allows for the base object to change so multiple base\nobjects can be borrowed from. The code doesn't try to exploit this\npossibility at the moment though.\n\nThe code isn't optimal at the moment as it doesn't consider the case\nwhere a borrow sequence could be larger than the local sequence it\nmeans to replace.\n\nSigned-off-by: Nicolas Pitre \n---\n packv4-create.c | 115 ++++++++++++++++++++++++++++++++++++++++++++++++++------\n 1 file changed, 104 insertions(+), 11 deletions(-)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex a9e4fb3..744514c 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -409,24 +409,53 @@ bad:\n \treturn NULL;\n }\n \n+static int compare_tree_entries(struct name_entry *e1, struct name_entry *e2)\n+{\n+\tint len1 = tree_entry_len(e1);\n+\tint len2 = tree_entry_len(e2);\n+\tint len = len1 < len2 ? len1 : len2;\n+\tunsigned char c1, c2;\n+\tint cmp;\n+\n+\tcmp = memcmp(e1->path, e2->path, len);\n+\tif (cmp)\n+\t\treturn cmp;\n+\tc1 = e1->path[len];\n+\tc2 = e2->path[len];\n+\tif (!c1 && S_ISDIR(e1->mode))\n+\t\tc1 = '/';\n+\tif (!c2 && S_ISDIR(e2->mode))\n+\t\tc2 = '/';\n+\treturn c1 - c2;\n+}\n+\n /*\n * This converts a canonical tree object buffer into its\n * tightly packed representation using the already populated\n * and sorted tree_path_table dictionary. The parsing is\n * strict so to ensure the canonical version may always be\n * regenerated and produce the same hash.\n+ *\n+ * If a delta buffer is provided, we may encode multiple ranges of tree\n+ * entries against that buffer.\n */\n-void * conv_to_dict_tree(void *buffer, unsigned long *psize)\n+void * conv_to_dict_tree(void *buffer, unsigned long *psize,\n+\t\t\t void *delta, unsigned long delta_size,\n+\t\t\t const unsigned char *delta_sha1)\n {\n \tunsigned long size = *psize;\n \tunsigned char *in, *out, *end;\n-\tstruct tree_desc desc;\n-\tstruct name_entry name_entry;\n+\tstruct tree_desc desc, delta_desc;\n+\tstruct name_entry name_entry, delta_entry;\n \tint nb_entries;\n+\tunsigned int delta_start, delta_pos = 0, delta_match = 0, first_delta = 1;\n \n \tif (!size)\n \t\treturn NULL;\n \n+\tif (!delta_size)\n+\t\tdelta = NULL;\n+\n \t/*\n \t * We can't make sure the result will always be smaller.\n \t * The smallest possible entry is \"0 x\\0<40 byte SHA1>\"\n@@ -449,21 +478,85 @@ void * conv_to_dict_tree(void *buffer, unsigned long *psize)\n \tout = add_number(out, nb_entries);\n \n \tinit_tree_desc(&desc, in, size);\n+\tif (delta) {\n+\t\tinit_tree_desc(&delta_desc, delta, delta_size);\n+\t\tif (!tree_entry(&delta_desc, &delta_entry))\n+\t\t\tdelta = NULL;\n+\t}\n+\n \twhile (tree_entry(&desc, &name_entry)) {\n-\t\tint pathlen = tree_entry_len(&name_entry);\n-\t\tint index = dict_add_entry(tree_path_table, name_entry.mode,\n-\t\t\t\t\t name_entry.path, pathlen);\n-\t\tif (index < 0) {\n-\t\t\terror(\"missing tree dict entry\");\n-\t\t\tfree(buffer);\n-\t\t\treturn NULL;\n+\t\tint pathlen, index;\n+\n+\t\t/*\n+\t\t * Try to match entries against our delta object.\n+\t\t */\n+\t\tif (delta) {\n+\t\t\tint ret;\n+\n+\t\t\tdo {\n+\t\t\t\tret = compare_tree_entries(&name_entry, &delta_entry);\n+\t\t\t\tif (ret < 1)\n+\t\t\t\t\tbreak;\n+\t\t\t\tif (tree_entry(&delta_desc, &delta_entry))\n+\t\t\t\t\tdelta_pos++;\n+\t\t\t\telse\n+\t\t\t\t\tdelta = NULL;\n+\t\t\t} while (delta);\n+\n+\t\t\tif (ret == 0) {\n+\t\t\t\tif (!delta_match)\n+\t\t\t\t\tdelta_start = delta_pos;\n+\t\t\t\tdelta_match++;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (delta_match) {\n+\t\t\t/*\n+\t\t\t * Let's write a sequence indicating we're copying\n+\t\t\t * entries from another object:\n+\t\t\t *\n+\t\t\t * 0 + start_entry + nr_entries + object_ref\n+\t\t\t *\n+\t\t\t * However, if object_ref is the same as the\n+\t\t\t * preceeding one, we can omit it and save some\n+\t\t\t * more space, especially if that ends up being a\n+\t\t\t * full sha1 reference. Let's steal the LSB\n+\t\t\t * of delta_start for that purpose.\n+\t\t\t */\n+\t\t\tif (end - out < (first_delta ? 48 : 7)) {\n+\t\t\t\tunsigned long sofar = out - (unsigned char *)buffer;\n+\t\t\t\tbuffer = xrealloc(buffer, sofar + 48);\n+\t\t\t\tout = (unsigned char *)buffer + sofar;\n+\t\t\t\tend = out + 48;\n+\t\t\t}\n+\n+\t\t\tdelta_start <<= 1;\n+\t\t\tdelta_start |= first_delta;\n+\t\t\tout = add_number(out, 0);\n+\t\t\tout = add_number(out, delta_start);\n+\t\t\tout = add_number(out, delta_match);\n+\t\t\tif (first_delta)\n+\t\t\t\tout = add_sha1_ref(out, delta_sha1);\n+\t\t\tdelta_match = 0;\n+\t\t\tfirst_delta = 0;\n \t\t}\n+\n \t\tif (end - out < 45) {\n \t\t\tunsigned long sofar = out - (unsigned char *)buffer;\n \t\t\tbuffer = xrealloc(buffer, sofar + 45);\n \t\t\tout = (unsigned char *)buffer + sofar;\n \t\t\tend = out + 45;\n \t\t}\n+\n+\t\tpathlen = tree_entry_len(&name_entry);\n+\t\tindex = dict_add_entry(tree_path_table, name_entry.mode,\n+\t\t\t\t name_entry.path, pathlen);\n+\t\tif (index < 0) {\n+\t\t\terror(\"missing tree dict entry\");\n+\t\t\tfree(buffer);\n+\t\t\treturn NULL;\n+\t\t}\n \t\tout = add_number(out, index);\n \t\tout = add_sha1_ref(out, name_entry.sha1);\n \t}\n@@ -777,7 +870,7 @@ static off_t packv4_write_object(struct sha1file *f, struct packed_git *p,\n \t\tresult = conv_to_dict_commit(src, &size);\n \t\tbreak;\n \tcase OBJ_TREE:\n-\t\tresult = conv_to_dict_tree(src, &size);\n+\t\tresult = conv_to_dict_tree(src, &size, NULL, 0, NULL);\n \t\tbreak;\n \tdefault:\n \t\tdie(\"unexpected object type %d\", type);\n-- \n1.8.4.22.g54757b7\n"},{"id":"225958","messageId":"1377577567-27655-18-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 17/23] pack v4: load delta candidate for encoding tree objects","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:26:01Z","receivedAt":"2013-08-27T04:26:01Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"The SHA1 of the base object is retrieved and the corresponding object\nis loaded in memory for conv_to_dict_tree() to look at. Simple but\neffective. Obviously this relies on the delta matching already performed\nduring the pack v3 delta search. Some native delta search for pack v4\ncould be investigated eventually.\n\nSigned-off-by: Nicolas Pitre \n---\n packv4-create.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++++++---\n 1 file changed, 66 insertions(+), 3 deletions(-)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex 744514c..ed67eb6 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -832,18 +832,62 @@ static unsigned long copy_object_data(struct sha1file *f, struct packed_git *p,\n \treturn written;\n }\n \n+static unsigned char *get_delta_base(struct packed_git *p, off_t offset,\n+\t\t\t\t unsigned char *sha1_buf)\n+{\n+\tstruct pack_window *w_curs = NULL;\n+\tenum object_type type;\n+\tunsigned long avail, size;\n+\tint hdrlen;\n+\tunsigned char *src;\n+\tconst unsigned char *base_sha1 = NULL; ;\n+\n+\tsrc = use_pack(p, &w_curs, offset, &avail);\n+\thdrlen = unpack_object_header_buffer(src, avail, &type, &size);\n+\n+\tif (type == OBJ_OFS_DELTA) {\n+\t\tstruct revindex_entry *revidx;\n+\t\tunsigned char c = src[hdrlen++];\n+\t\toff_t base_offset = c & 127;\n+\t\twhile (c & 128) {\n+\t\t\tbase_offset += 1;\n+\t\t\tif (!base_offset || MSB(base_offset, 7))\n+\t\t\t\terror(\"delta offset overflow\");\n+\t\t\tc = src[hdrlen++];\n+\t\t\tbase_offset = (base_offset << 7) + (c & 127);\n+\t\t}\n+\t\tbase_offset = offset - base_offset;\n+\t\tif (base_offset <= 0 || base_offset >= offset)\n+\t\t\terror(\"delta offset out of bound\");\n+\t\trevidx = find_pack_revindex(p, base_offset);\n+\t\tbase_sha1 = nth_packed_object_sha1(p, revidx->nr);\n+\t} else if (type == OBJ_REF_DELTA) {\n+\t\tbase_sha1 = src + hdrlen;\n+\t} else {\n+\t\terror(\"expected to get a delta but got a %s\", typename(type));\n+\t}\n+\n+\tunuse_pack(&w_curs);\n+\n+\tif (!base_sha1)\n+\t\treturn NULL;\n+\thashcpy(sha1_buf, base_sha1);\n+\treturn sha1_buf;\n+}\n+\n static off_t packv4_write_object(struct sha1file *f, struct packed_git *p,\n \t\t\t\t struct pack_idx_entry *obj)\n {\n \tvoid *src, *result;\n \tstruct object_info oi = {};\n-\tenum object_type type;\n+\tenum object_type type, packed_type;\n \tunsigned long size;\n \tunsigned int hdrlen;\n \n \toi.typep = &type;\n \toi.sizep = &size;\n-\tif (packed_object_info(p, obj->offset, &oi) < 0)\n+\tpacked_type = packed_object_info(p, obj->offset, &oi);\n+\tif (packed_type < 0)\n \t\tdie(\"cannot get type of %s from %s\",\n \t\t sha1_to_hex(obj->sha1), p->pack_name);\n \n@@ -870,7 +914,26 @@ static off_t packv4_write_object(struct sha1file *f, struct packed_git *p,\n \t\tresult = conv_to_dict_commit(src, &size);\n \t\tbreak;\n \tcase OBJ_TREE:\n-\t\tresult = conv_to_dict_tree(src, &size, NULL, 0, NULL);\n+\t\tif (packed_type != OBJ_TREE) {\n+\t\t\tunsigned char sha1_buf[20], *ref_sha1;\n+\t\t\tvoid *ref;\n+\t\t\tenum object_type ref_type;\n+\t\t\tunsigned long ref_size;\n+\n+\t\t\tref_sha1 = get_delta_base(p, obj->offset, sha1_buf);\n+\t\t\tif (!ref_sha1)\n+\t\t\t\tdie(\"unable to get delta base sha1 for %s\",\n+\t\t\t\t\t\tsha1_to_hex(obj->sha1));\n+\t\t\tref = read_sha1_file(ref_sha1, &ref_type, &ref_size);\n+\t\t\tif (!ref || ref_type != OBJ_TREE)\n+\t\t\t\tdie(\"cannot obtain delta base for %s\",\n+\t\t\t\t\t\tsha1_to_hex(obj->sha1));\n+\t\t\tresult = conv_to_dict_tree(src, &size,\n+\t\t\t\t\tref, ref_size, ref_sha1);\n+\t\t\tfree(ref);\n+\t\t} else {\n+\t\t\tresult = conv_to_dict_tree(src, &size, NULL, 0, NULL);\n+\t\t}\n \t\tbreak;\n \tdefault:\n \t\tdie(\"unexpected object type %d\", type);\n-- \n1.8.4.22.g54757b7\n"},{"id":"225957","messageId":"1377577567-27655-19-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 18/23] pack v4: honor pack.compression config option","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:26:02Z","receivedAt":"2013-08-27T04:26:02Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Signed-off-by: Nicolas Pitre \n---\n packv4-create.c | 19 +++++++++++++++++++\n 1 file changed, 19 insertions(+)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex ed67eb6..2d46d11 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -15,6 +15,7 @@\n #include \"pack-revindex.h\"\n \n \n+static int pack_compression_seen;\n static int pack_compression_level = Z_DEFAULT_COMPRESSION;\n \n struct data_entry {\n@@ -1040,12 +1041,30 @@ static void process_one_pack(char *src_pack, char *dst_pack)\n \tsha1close(f, NULL, CSUM_CLOSE | CSUM_FSYNC);\n }\n \n+static int git_pack_config(const char *k, const char *v, void *cb)\n+{\n+\tif (!strcmp(k, \"pack.compression\")) {\n+\t\tint level = git_config_int(k, v);\n+\t\tif (level == -1)\n+\t\t\tlevel = Z_DEFAULT_COMPRESSION;\n+\t\telse if (level < 0 || level > Z_BEST_COMPRESSION)\n+\t\t\tdie(\"bad pack compression level %d\", level);\n+\t\tpack_compression_level = level;\n+\t\tpack_compression_seen = 1;\n+\t\treturn 0;\n+\t}\n+\treturn git_default_config(k, v, cb);\n+}\n+\n int main(int argc, char *argv[])\n {\n \tif (argc != 3) {\n \t\tfprintf(stderr, \"Usage: %s \\n\", argv[0]);\n \t\texit(1);\n \t}\n+\tgit_config(git_pack_config, NULL);\n+\tif (!pack_compression_seen && core_compression_seen)\n+\t\tpack_compression_level = core_compression_level;\n \tprocess_one_pack(argv[1], argv[2]);\n \tif (0)\n \t\tdict_dump();\n-- \n1.8.4.22.g54757b7\n"},{"id":"225955","messageId":"1377577567-27655-20-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 19/23] pack v4: relax commit parsing a bit","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:26:03Z","receivedAt":"2013-08-27T04:26:03Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"At least commit af25e94d4dcfb9608846242fabdd4e6014e5c9f0 in the Linux\nkernel repository has \"author <> 1120285620 -0700\"\n\nSigned-off-by: Nicolas Pitre \n---\n packv4-create.c | 6 +++---\n 1 file changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex 2d46d11..63dc3d2 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -157,12 +157,12 @@ static char *get_nameend_and_tz(char *from, int *tz_val)\n \tchar *end, *tz;\n \n \ttz = strchr(from, '\\n');\n-\t/* let's assume the smallest possible string to be \"x 0 +0000\\n\" */\n-\tif (!tz || tz - from < 13)\n+\t/* let's assume the smallest possible string to be \" <> 0 +0000\\n\" */\n+\tif (!tz || tz - from < 11)\n \t\treturn NULL;\n \ttz -= 4;\n \tend = tz - 4;\n-\twhile (end - from > 5 && *end != ' ')\n+\twhile (end - from > 3 && *end != ' ')\n \t\tend--;\n \tif (end[-1] != '>' || end[0] != ' ' || tz[-2] != ' ')\n \t\treturn NULL;\n-- \n1.8.4.22.g54757b7\n"},{"id":"225963","messageId":"1377577567-27655-21-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 20/23] pack index v3","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:26:04Z","receivedAt":"2013-08-27T04:26:04Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This is a minor change over pack index v2. Since pack v4 already contains\nthe sorted SHA1 table, it is therefore ommitted from the index file.\n\nSigned-off-by: Nicolas Pitre \n---\n pack-write.c | 6 +++++-\n packv4-create.c | 10 +++++++++-\n 2 files changed, 14 insertions(+), 2 deletions(-)\n\ndiff --git a/pack-write.c b/pack-write.c\nindex ca9e63b..631007e 100644\n--- a/pack-write.c\n+++ b/pack-write.c\n@@ -87,6 +87,8 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec\n \n \t/* if last object's offset is >= 2^31 we should use index V2 */\n \tindex_version = need_large_offset(last_obj_offset, opts) ? 2 : opts->version;\n+\tif (index_version < opts->version)\n+\t\tindex_version = opts->version;\n \n \t/* index versions 2 and above need a header */\n \tif (index_version >= 2) {\n@@ -127,7 +129,9 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec\n \t\t\tuint32_t offset = htonl(obj->offset);\n \t\t\tsha1write(f, &offset, 4);\n \t\t}\n-\t\tsha1write(f, obj->sha1, 20);\n+\t\t/* Pack v4 (using index v3) carries the SHA1 table already */\n+\t\tif (index_version < 3)\n+\t\t\tsha1write(f, obj->sha1, 20);\n \t\tgit_SHA1_Update(&ctx, obj->sha1, 20);\n \t\tif ((opts->flags & WRITE_IDX_STRICT) &&\n \t\t (i && !hashcmp(list[-2]->sha1, obj->sha1)))\ndiff --git a/packv4-create.c b/packv4-create.c\nindex 63dc3d2..bb171c5 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -1007,8 +1007,10 @@ static void process_one_pack(char *src_pack, char *dst_pack)\n \tstruct packed_git *p;\n \tstruct sha1file *f;\n \tstruct pack_idx_entry *objs, **p_objs;\n+\tstruct pack_idx_option idx_opts;\n \tunsigned i, nr_objects;\n \toff_t written = 0;\n+\tunsigned char pack_sha1[20];\n \n \tp = open_pack(src_pack);\n \tif (!p)\n@@ -1034,11 +1036,17 @@ static void process_one_pack(char *src_pack, char *dst_pack)\n \tfor (i = 0; i < nr_objects; i++) {\n \t\toff_t obj_pos = written;\n \t\tstruct pack_idx_entry *obj = p_objs[i];\n+\t\tcrc32_begin(f);\n \t\twritten += packv4_write_object(f, p, obj);\n \t\tobj->offset = obj_pos;\n+\t\tobj->crc32 = crc32_end(f);\n \t}\n \n-\tsha1close(f, NULL, CSUM_CLOSE | CSUM_FSYNC);\n+\tsha1close(f, pack_sha1, CSUM_CLOSE | CSUM_FSYNC);\n+\n+\treset_pack_idx_option(&idx_opts);\n+\tidx_opts.version = 3;\n+\twrite_idx_file(dst_pack, p_objs, nr_objects, &idx_opts, pack_sha1);\n }\n \n static int git_pack_config(const char *k, const char *v, void *cb)\n-- \n1.8.4.22.g54757b7\n"},{"id":"225960","messageId":"1377577567-27655-22-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 21/23] pack v4: normalize pack name to properly generate the pack index file name","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:26:05Z","receivedAt":"2013-08-27T04:26:05Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Signed-off-by: Nicolas Pitre \n---\n packv4-create.c | 73 +++++++++++++++++++++++++++------------------------------\n 1 file changed, 34 insertions(+), 39 deletions(-)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex bb171c5..6801e21 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -949,56 +949,46 @@ static off_t packv4_write_object(struct sha1file *f, struct packed_git *p,\n \treturn hdrlen + size;\n }\n \n-static struct packed_git *open_pack(const char *path)\n+static char *normalize_pack_name(const char *path)\n {\n-\tchar arg[PATH_MAX];\n+\tchar buf[PATH_MAX];\n \tint len;\n-\tstruct packed_git *p;\n \n-\tlen = strlcpy(arg, path, PATH_MAX);\n-\tif (len >= PATH_MAX) {\n-\t\terror(\"name too long: %s\", path);\n-\t\treturn NULL;\n-\t}\n+\tlen = strlcpy(buf, path, PATH_MAX);\n+\tif (len >= PATH_MAX - 6)\n+\t\tdie(\"name too long: %s\", path);\n \n \t/*\n \t * In addition to \"foo.idx\" we accept \"foo.pack\" and \"foo\";\n-\t * normalize these forms to \"foo.idx\" for add_packed_git().\n+\t * normalize these forms to \"foo.pack\".\n \t */\n-\tif (has_extension(arg, \".pack\")) {\n-\t\tstrcpy(arg + len - 5, \".idx\");\n-\t\tlen--;\n-\t} else if (!has_extension(arg, \".idx\")) {\n-\t\tif (len + 4 >= PATH_MAX) {\n-\t\t\terror(\"name too long: %s.idx\", arg);\n-\t\t\treturn NULL;\n-\t\t}\n-\t\tstrcpy(arg + len, \".idx\");\n-\t\tlen += 4;\n+\tif (has_extension(buf, \".idx\")) {\n+\t\tstrcpy(buf + len - 4, \".pack\");\n+\t\tlen++;\n+\t} else if (!has_extension(buf, \".pack\")) {\n+\t\tstrcpy(buf + len, \".pack\");\n+\t\tlen += 5;\n \t}\n \n-\t/*\n-\t * add_packed_git() uses our buffer (containing \"foo.idx\") to\n-\t * build the pack filename (\"foo.pack\"). Make sure it fits.\n-\t */\n-\tif (len + 1 >= PATH_MAX) {\n-\t\targ[len - 4] = '\\0';\n-\t\terror(\"name too long: %s.pack\", arg);\n-\t\treturn NULL;\n-\t}\n+\treturn xstrdup(buf);\n+}\n \n-\tp = add_packed_git(arg, len, 1);\n-\tif (!p) {\n-\t\terror(\"packfile %s not found.\", arg);\n-\t\treturn NULL;\n-\t}\n+static struct packed_git *open_pack(const char *path)\n+{\n+\tchar *packname = normalize_pack_name(path);\n+\tint len = strlen(packname);\n+\tstruct packed_git *p;\n+\n+\tstrcpy(packname + len - 5, \".idx\");\n+\tp = add_packed_git(packname, len - 1, 1);\n+\tif (!p)\n+\t\tdie(\"packfile %s not found.\", packname);\n \n \tinstall_packed_git(p);\n-\tif (open_pack_index(p)) {\n-\t\terror(\"packfile %s index not opened\", p->pack_name);\n-\t\treturn NULL;\n-\t}\n+\tif (open_pack_index(p))\n+\t\tdie(\"packfile %s index not opened\", p->pack_name);\n \n+\tfree(packname);\n \treturn p;\n }\n \n@@ -1010,6 +1000,7 @@ static void process_one_pack(char *src_pack, char *dst_pack)\n \tstruct pack_idx_option idx_opts;\n \tunsigned i, nr_objects;\n \toff_t written = 0;\n+\tchar *packname;\n \tunsigned char pack_sha1[20];\n \n \tp = open_pack(src_pack);\n@@ -1024,7 +1015,8 @@ static void process_one_pack(char *src_pack, char *dst_pack)\n \tsort_dict_entries_by_hits(commit_name_table);\n \tsort_dict_entries_by_hits(tree_path_table);\n \n-\tf = packv4_open(dst_pack);\n+\tpackname = normalize_pack_name(dst_pack);\n+\tf = packv4_open(packname);\n \tif (!f)\n \t\tdie(\"unable to open destination pack\");\n \twritten += packv4_write_header(f, nr_objects);\n@@ -1046,7 +1038,10 @@ static void process_one_pack(char *src_pack, char *dst_pack)\n \n \treset_pack_idx_option(&idx_opts);\n \tidx_opts.version = 3;\n-\twrite_idx_file(dst_pack, p_objs, nr_objects, &idx_opts, pack_sha1);\n+\tstrcpy(packname + strlen(packname) - 5, \".idx\");\n+\twrite_idx_file(packname, p_objs, nr_objects, &idx_opts, pack_sha1);\n+\n+\tfree(packname);\n }\n \n static int git_pack_config(const char *k, const char *v, void *cb)\n-- \n1.8.4.22.g54757b7\n"},{"id":"225962","messageId":"1377577567-27655-23-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 22/23] pack v4: add progress display","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:26:06Z","receivedAt":"2013-08-27T04:26:06Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Signed-off-by: Nicolas Pitre \n---\n packv4-create.c | 10 ++++++++++\n 1 file changed, 10 insertions(+)\n\ndiff --git a/packv4-create.c b/packv4-create.c\nindex 6801e21..22e14da 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -13,6 +13,7 @@\n #include \"tree-walk.h\"\n #include \"pack.h\"\n #include \"pack-revindex.h\"\n+#include \"progress.h\"\n \n \n static int pack_compression_seen;\n@@ -609,8 +610,10 @@ static struct pack_idx_entry **sort_objs_by_offset(struct pack_idx_entry *list,\n static int create_pack_dictionaries(struct packed_git *p,\n \t\t\t\t struct pack_idx_entry **obj_list)\n {\n+\tstruct progress *progress_state;\n \tunsigned int i;\n \n+\tprogress_state = start_progress(\"Scanning objects\", p->num_objects);\n \tfor (i = 0; i < p->num_objects; i++) {\n \t\tstruct pack_idx_entry *obj = obj_list[i];\n \t\tvoid *data;\n@@ -619,6 +622,8 @@ static int create_pack_dictionaries(struct packed_git *p,\n \t\tstruct object_info oi = {};\n \t\tint (*add_dict_entries)(void *, unsigned long);\n \n+\t\tdisplay_progress(progress_state, i+1);\n+\n \t\toi.typep = &type;\n \t\toi.sizep = &size;\n \t\tif (packed_object_info(p, obj->offset, &oi) < 0)\n@@ -648,6 +653,7 @@ static int create_pack_dictionaries(struct packed_git *p,\n \t\tfree(data);\n \t}\n \n+\tstop_progress(&progress_state);\n \treturn 0;\n }\n \n@@ -1002,6 +1008,7 @@ static void process_one_pack(char *src_pack, char *dst_pack)\n \toff_t written = 0;\n \tchar *packname;\n \tunsigned char pack_sha1[20];\n+\tstruct progress *progress_state;\n \n \tp = open_pack(src_pack);\n \tif (!p)\n@@ -1023,6 +1030,7 @@ static void process_one_pack(char *src_pack, char *dst_pack)\n \twritten += packv4_write_tables(f, nr_objects, objs);\n \n \t/* Let's write objects out, updating the object index list in place */\n+\tprogress_state = start_progress(\"Writing objects\", nr_objects);\n \tall_objs = objs;\n \tall_objs_nr = nr_objects;\n \tfor (i = 0; i < nr_objects; i++) {\n@@ -1032,7 +1040,9 @@ static void process_one_pack(char *src_pack, char *dst_pack)\n \t\twritten += packv4_write_object(f, p, obj);\n \t\tobj->offset = obj_pos;\n \t\tobj->crc32 = crc32_end(f);\n+\t\tdisplay_progress(progress_state, i+1);\n \t}\n+\tstop_progress(&progress_state);\n \n \tsha1close(f, pack_sha1, CSUM_CLOSE | CSUM_FSYNC);\n \n-- \n1.8.4.22.g54757b7\n"},{"id":"225961","messageId":"1377577567-27655-24-git-send-email-nico@fluxnic.net","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH 23/23] initial pack index v3 support on the read side","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T04:26:07Z","receivedAt":"2013-08-27T04:26:07Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"A bit crud but good enough for now.\n\nSigned-off-by: Nicolas Pitre \n---\n cache.h | 1 +\n sha1_file.c | 58 +++++++++++++++++++++++++++++++++++++++++++++++++++-------\n 2 files changed, 52 insertions(+), 7 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex b6634c4..63066a1 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1018,6 +1018,7 @@ extern struct packed_git {\n \toff_t pack_size;\n \tconst void *index_data;\n \tsize_t index_size;\n+\tconst unsigned char *sha1_table;\n \tuint32_t num_objects;\n \tuint32_t num_bad_objects;\n \tunsigned char *bad_object_sha1;\ndiff --git a/sha1_file.c b/sha1_file.c\nindex c2020d0..e9c54f4 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -504,7 +504,7 @@ static int check_packed_git_idx(const char *path, struct packed_git *p)\n \thdr = idx_map;\n \tif (hdr->idx_signature == htonl(PACK_IDX_SIGNATURE)) {\n \t\tversion = ntohl(hdr->idx_version);\n-\t\tif (version < 2 || version > 2) {\n+\t\tif (version < 2 || version > 3) {\n \t\t\tmunmap(idx_map, idx_size);\n \t\t\treturn error(\"index file %s is version %\"PRIu32\n \t\t\t\t \" and is not supported by this binary\"\n@@ -539,12 +539,13 @@ static int check_packed_git_idx(const char *path, struct packed_git *p)\n \t\t\tmunmap(idx_map, idx_size);\n \t\t\treturn error(\"wrong index v1 file size in %s\", path);\n \t\t}\n-\t} else if (version == 2) {\n+\t} else if (version == 2 || version == 3) {\n+\t\tunsigned long min_size, max_size;\n \t\t/*\n \t\t * Minimum size:\n \t\t * - 8 bytes of header\n \t\t * - 256 index entries 4 bytes each\n-\t\t * - 20-byte sha1 entry * nr\n+\t\t * - 20-byte sha1 entry * nr (version 2 only)\n \t\t * - 4-byte crc entry * nr\n \t\t * - 4-byte offset entry * nr\n \t\t * - 20-byte SHA1 of the packfile\n@@ -553,8 +554,10 @@ static int check_packed_git_idx(const char *path, struct packed_git *p)\n \t\t * variable sized table containing 8-byte entries\n \t\t * for offsets larger than 2^31.\n \t\t */\n-\t\tunsigned long min_size = 8 + 4*256 + nr*(20 + 4 + 4) + 20 + 20;\n-\t\tunsigned long max_size = min_size;\n+\t\tmin_size = 8 + 4*256 + nr*(20 + 4 + 4) + 20 + 20;\n+\t\tif (version != 2)\n+\t\t\tmin_size -= nr*20;\n+\t\tmax_size = min_size;\n \t\tif (nr)\n \t\t\tmax_size += (nr - 1)*8;\n \t\tif (idx_size < min_size || idx_size > max_size) {\n@@ -573,6 +576,36 @@ static int check_packed_git_idx(const char *path, struct packed_git *p)\n \t\t}\n \t}\n \n+\tif (version >= 3) {\n+\t\t/* the SHA1 table is located in the main pack file */\n+\t\tvoid *pack_map;\n+\t\tstruct pack_header *pack_hdr;\n+\n+\t\tfd = git_open_noatime(p->pack_name);\n+\t\tif (fd < 0) {\n+\t\t\tmunmap(idx_map, idx_size);\n+\t\t\treturn error(\"unable to open %s\", p->pack_name);\n+\t\t}\n+\t\tif (fstat(fd, &st) != 0 || xsize_t(st.st_size) < 12 + nr*20) {\n+\t\t\tclose(fd);\n+\t\t\tmunmap(idx_map, idx_size);\n+\t\t\treturn error(\"size of %s is wrong\", p->pack_name);\n+\t\t}\n+\t\tpack_map = xmmap(NULL, 12 + nr*20, PROT_READ, MAP_PRIVATE, fd, 0);\n+\t\tclose(fd);\n+\t\tpack_hdr = pack_map;\n+\t\tif (pack_hdr->hdr_signature != htonl(PACK_SIGNATURE) ||\n+\t\t pack_hdr->hdr_version != htonl(4) ||\n+\t\t pack_hdr->hdr_entries != htonl(nr)) {\n+\t\t\tmunmap(idx_map, idx_size);\n+\t\t\tmunmap(pack_map, 12 + nr*20);\n+\t\t\treturn error(\"packfile for %s doesn't match expectations\", path);\n+\t\t}\n+\t\tp->sha1_table = pack_map;\n+\t\tp->sha1_table += 12;\n+\t} else\n+\t\tp->sha1_table = NULL;\n+\n \tp->index_version = version;\n \tp->index_data = idx_map;\n \tp->index_size = idx_size;\n@@ -697,6 +730,10 @@ void close_pack_index(struct packed_git *p)\n \t\tmunmap((void *)p->index_data, p->index_size);\n \t\tp->index_data = NULL;\n \t}\n+\tif (p->sha1_table) {\n+\t\tmunmap((void *)(p->sha1_table - 12), 12 + p->num_objects * 20);\n+\t\tp->sha1_table = NULL;\n+\t}\n }\n \n /*\n@@ -808,7 +845,7 @@ static int open_packed_git_1(struct packed_git *p)\n \t\treturn error(\"file %s is far too short to be a packfile\", p->pack_name);\n \tif (hdr.hdr_signature != htonl(PACK_SIGNATURE))\n \t\treturn error(\"file %s is not a GIT packfile\", p->pack_name);\n-\tif (!pack_version_ok(hdr.hdr_version))\n+\tif (!pack_version_ok(hdr.hdr_version) && hdr.hdr_version != htonl(4))\n \t\treturn error(\"packfile %s is version %\"PRIu32\" and not\"\n \t\t\t\" supported (try upgrading GIT to a newer version)\",\n \t\t\tp->pack_name, ntohl(hdr.hdr_version));\n@@ -2226,9 +2263,12 @@ const unsigned char *nth_packed_object_sha1(struct packed_git *p,\n \tindex += 4 * 256;\n \tif (p->index_version == 1) {\n \t\treturn index + 24 * n + 4;\n-\t} else {\n+\t} else if (p->index_version == 2) {\n \t\tindex += 8;\n \t\treturn index + 20 * n;\n+\t} else {\n+\t\tindex = p->sha1_table;\n+\t\treturn index + 20 * n;\n \t}\n }\n \n@@ -2241,6 +2281,8 @@ off_t nth_packed_object_offset(const struct packed_git *p, uint32_t n)\n \t} else {\n \t\tuint32_t off;\n \t\tindex += 8 + p->num_objects * (20 + 4);\n+\t\tif (p->index_version != 2)\n+\t\t\tindex -= p->num_objects * 20;\n \t\toff = ntohl(*((uint32_t *)(index + 4 * n)));\n \t\tif (!(off & 0x80000000))\n \t\t\treturn off;\n@@ -2281,6 +2323,8 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \t\tstride = 24;\n \t\tindex += 4;\n \t}\n+\tif (p->index_version > 2)\n+\t\tindex = p->sha1_table;\n \n \tif (debug_lookup)\n \t\tprintf(\"%02x%02x%02x... lo %u hi %u nr %\"PRIu32\"\\n\",\n-- \n1.8.4.22.g54757b7\n"},{"id":"225986","messageId":"1377602225-30439-1-git-send-email-pclouds@gmail.com","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"[PATCH] Document pack v4 format","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-08-27T11:17:05Z","receivedAt":"2013-08-27T11:17:05Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n For my education but may help people who are interested in the\n format. Most is gathered from commit messages, except the delta tree\n entries.\n \n .idx is not documented yet, but it does not change much and not the\n focus right now anyway.\n\n Documentation/technical/pack-format-v4.txt (new) | 110 +++++++++++++++++++++++\n 1 file changed, 110 insertions(+)\n create mode 100644 Documentation/technical/pack-format-v4.txt\n\ndiff --git a/Documentation/technical/pack-format-v4.txt b/Documentation/technical/pack-format-v4.txt\nnew file mode 100644\nindex 0000000..9123a53\n--- /dev/null\n+++ b/Documentation/technical/pack-format-v4.txt\n@@ -0,0 +1,110 @@\n+Git pack v4 format\n+==================\n+\n+== pack-*.pack files have the following format:\n+\n+ - A header appears at the beginning and consists of the following:\n+\n+ 4-byte signature:\n+\t The signature is: {'P', 'A', 'C', 'K'}\n+\n+ 4-byte version number (network byte order): must be version\n+ number 4\n+\n+ 4-byte number of objects contained in the pack (network byte\n+ order)\n+\n+ - (20 * nr_objects)-byte SHA-1 table: sorted in memcmp() order.\n+\n+ - Commit name dictionary: the uncompressed length in variable\n+ encoding, followed by zlib-compressed dictionary. Each entry\n+ consists of two prefix bytes storing timezone followed by a\n+ NUL-terminated string.\n+\n+ Entries should be sorted by frequency so that the most frequent\n+ entry has the smallest index, thus most efficient variable\n+ encoding.\n+\n+ - Tree path dictionary: similar format to commit name\n+ dictionary. Each entry consists of two prefix bytes storing entry\n+ mode, then a NUL-terminated path name. Same sort order\n+ recommendation applies.\n+\n+ - The header is followed by number of object entries, each of\n+ which looks like this:\n+\n+ (undeltified representation)\n+ n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n+ [uncompressed data]\n+ [compressed data]\n+\n+ (deltified representation)\n+ n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n+ base object name in SHA-1 reference encoding\n+ compressed delta data\n+\n+ In undeltified format, blobs and tags do not have the\n+ uncompressed data, all object content is compressed. Trees are\n+ not compressed at all. Some headers in commits are stored\n+ uncompressed, the rest is compressed.\n+\n+ All objects except trees are deltified and compressed the same\n+ way in v3. Trees however are deltified differently and use\n+ undeltified representation. See \"Tree representation\" below for\n+ details.\n+\n+ - The trailer records 20-byte SHA-1 checksum of all of the above.\n+\n+=== Commit representation\n+\n+ - n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n+\n+ - Tree SHA-1 in SHA-1 reference encoding\n+\n+ - Parent count in variable length encoding\n+\n+ - Parent SHA-1s in SHA-1 reference encoding\n+\n+ - Author reference: the index, in variable length encoding, to comit\n+ name dictionary, which covers the name and also the time zone.\n+\n+ - Author timestamp in variable length encoding\n+\n+ - Committer reference: the index, in variable length encoding, to\n+ comit name dictionary, which covers the name and also the time\n+ zone.\n+\n+ - Committer timestamp in variable length encoding\n+\n+ - Compressed data of remaining header and the body\n+\n+=== Tree representation\n+\n+ - n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n+\n+ - Number of trees in variable length encoding\n+\n+ - A number of trees, each consists of\n+\n+ Path component reference: an index, in variable length encoding,\n+ into tree path dictionary, which also covers entry mode.\n+\n+ SHA-1 in SHA-1 reference encoding.\n+\n+Path component reference zero is an indicator of deltified portion and\n+has the following format:\n+\n+ - path component reference: zero\n+\n+ - index of the entry to copy from, in variable length encoding\n+\n+ - number of entries in variable length encoding\n+\n+ - base tree in SHA-1 reference encoding\n+\n+=== SHA-1 reference encoding\n+\n+This encoding is used to encode SHA-1 efficiently if it's already in\n+the SHA-1 table. It starts with an index number in variable length\n+encoding. If it's not zero, its value minus one is the index in the\n+SHA-1 table. If it's zero, 20 bytes of SHA-1 is followed.\n-- \n1.8.2.83.gc99314b\n"},{"id":"225999","messageId":"xmqqioyrfa5m.fsf@gitster.dls.corp.google.com","threadId":"34774","inReplyTo":"1377577567-27655-1-git-send-email-nico@fluxnic.net","subject":"Re: [PATCH 00/23] Preliminary pack v4 support","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-27T15:03:49Z","receivedAt":"2013-08-27T15:03:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> Subject says it all... at last !\n>\n> This can also be fetched here:\n>\n> \tgit://git.linaro.org/people/nico/git\n>\n> Demonstration of what it does at the moment:\n>\n> \thttp://article.gmane.org/gmane.comp.version-control.git/233038\n>\n> I'd like to preserve the author time stamps as they relate to where in\n> the world I was when the corresponding code was written. You'll notice\n> I didn't work on the code in the same order as it is now presented.\n\nWe can also notice things like \"From: user@machine.(none)\" ;-)\n\n> Still open question: what to do with a thin pack. Should we really\n> complete it with local objects upon reception, or were we only over\n> paranoid at the time we imposed this rule?\n\nI do not think paranoia had much to do with it. I am afraid that\nallowing a delta in a pack to depend on a base in another pack means\nthat the former pack becomes unusable without the latter, which\nwould make object store management (e.g. partial repacking) a lot\nmore cumbersome, no?\n"},{"id":"226001","messageId":"xmqqbo4jf9yf.fsf@gitster.dls.corp.google.com","threadId":"34774","inReplyTo":"1377577567-27655-2-git-send-email-nico@fluxnic.net","subject":"Re: [PATCH 01/23] pack v4: initial pack dictionary structure and code","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-27T15:08:08Z","receivedAt":"2013-08-27T15:08:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> Signed-off-by: Nicolas Pitre \n> ---\n\nWas there a reason not to reuse the hash-table Linus did in\nhash.[ch]?\n\nIt may not make much of a difference for something so small and\nisolated from the rest of the system, but if hash.[ch] can be easily\nfixed with a small tweak to suit the use by this subsystem better,\nit might be worth reusing the existing code with improvement, which\nmay help other potential users.\n\n> packv4-create.c | 137 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n> 1 file changed, 137 insertions(+)\n> create mode 100644 packv4-create.c\n>\n> diff --git a/packv4-create.c b/packv4-create.c\n> new file mode 100644\n> index 0000000..2de6d41\n> --- /dev/null\n> +++ b/packv4-create.c\n> @@ -0,0 +1,137 @@\n> +/*\n> + * packv4-create.c: management of dictionary tables used in pack v4\n> + *\n> + * (C) Nicolas Pitre \n> + *\n> + * This code is free software; you can redistribute it and/or modify\n> + * it under the terms of the GNU General Public License version 2 as\n> + * published by the Free Software Foundation.\n> + */\n> +\n> +#include \"cache.h\"\n> +\n> +struct data_entry {\n> +\tunsigned offset;\n> +\tunsigned hits;\n> +};\n> +\n> +struct dict_table {\n> +\tchar *data;\n> +\tunsigned ptr;\n> +\tunsigned size;\n> +\tstruct data_entry *entry;\n> +\tunsigned nb_entries;\n> +\tunsigned max_entries;\n> +\tunsigned *hash;\n> +\tunsigned hash_size;\n> +};\n> +\n> +struct dict_table *create_dict_table(void)\n> +{\n> +\treturn xcalloc(sizeof(struct dict_table), 1);\n> +}\n> +\n> +void destroy_dict_table(struct dict_table *t)\n> +{\n> +\tfree(t->data);\n> +\tfree(t->entry);\n> +\tfree(t->hash);\n> +\tfree(t);\n> +}\n> +\n> +static int locate_entry(struct dict_table *t, const char *str)\n> +{\n> +\tint i = 0;\n> +\tconst unsigned char *s = (const unsigned char *) str;\n> +\n> +\twhile (*s)\n> +\t\ti = i * 111 + *s++;\n> +\ti = (unsigned)i % t->hash_size;\n> +\n> +\twhile (t->hash[i]) {\n> +\t\tunsigned n = t->hash[i] - 1;\n> +\t\tif (!strcmp(str, t->data + t->entry[n].offset))\n> +\t\t\treturn n;\n> +\t\tif (++i >= t->hash_size)\n> +\t\t\ti = 0;\n> +\t}\n> +\treturn -1 - i;\n> +}\n> +\n> +static void rehash_entries(struct dict_table *t)\n> +{\n> +\tunsigned n;\n> +\n> +\tt->hash_size *= 2;\n> +\tif (t->hash_size < 1024)\n> +\t\tt->hash_size = 1024;\n> +\tt->hash = xrealloc(t->hash, t->hash_size * sizeof(*t->hash));\n> +\tmemset(t->hash, 0, t->hash_size * sizeof(*t->hash));\n> +\n> +\tfor (n = 0; n < t->nb_entries; n++) {\n> +\t\tint i = locate_entry(t, t->data + t->entry[n].offset);\n> +\t\tif (i < 0)\n> +\t\t\tt->hash[-1 - i] = n + 1;\n> +\t}\n> +}\n> +\n> +int dict_add_entry(struct dict_table *t, const char *str)\n> +{\n> +\tint i, len = strlen(str) + 1;\n> +\n> +\tif (t->ptr + len >= t->size) {\n> +\t\tt->size = (t->size + len + 1024) * 3 / 2;\n> +\t\tt->data = xrealloc(t->data, t->size);\n> +\t}\n> +\tmemcpy(t->data + t->ptr, str, len);\n> +\n> +\ti = (t->nb_entries) ? locate_entry(t, t->data + t->ptr) : -1;\n> +\tif (i >= 0) {\n> +\t\tt->entry[i].hits++;\n> +\t\treturn i;\n> +\t}\n> +\n> +\tif (t->nb_entries >= t->max_entries) {\n> +\t\tt->max_entries = (t->max_entries + 1024) * 3 / 2;\n> +\t\tt->entry = xrealloc(t->entry, t->max_entries * sizeof(*t->entry));\n> +\t}\n> +\tt->entry[t->nb_entries].offset = t->ptr;\n> +\tt->entry[t->nb_entries].hits = 1;\n> +\tt->ptr += len + 1;\n> +\tt->nb_entries++;\n> +\n> +\tif (t->hash_size * 3 <= t->nb_entries * 4)\n> +\t\trehash_entries(t);\n> +\telse\n> +\t\tt->hash[-1 - i] = t->nb_entries;\n> +\n> +\treturn t->nb_entries - 1;\n> +}\n> +\n> +static int cmp_dict_entries(const void *a_, const void *b_)\n> +{\n> +\tconst struct data_entry *a = a_;\n> +\tconst struct data_entry *b = b_;\n> +\tint diff = b->hits - a->hits;\n> +\tif (!diff)\n> +\t\tdiff = a->offset - b->offset;\n> +\treturn diff;\n> +}\n> +\n> +static void sort_dict_entries_by_hits(struct dict_table *t)\n> +{\n> +\tqsort(t->entry, t->nb_entries, sizeof(*t->entry), cmp_dict_entries);\n> +\tt->hash_size = (t->nb_entries * 4 / 3) / 2;\n> +\trehash_entries(t);\n> +}\n> +\n> +void dict_dump(struct dict_table *t)\n> +{\n> +\tint i;\n> +\n> +\tsort_dict_entries_by_hits(t);\n> +\tfor (i = 0; i < t->nb_entries; i++)\n> +\t\tprintf(\"%d\\t%s\\n\",\n> +\t\t\tt->entry[i].hits,\n> +\t\t\tt->data + t->entry[i].offset);\n> +}\n"},{"id":"226004","messageId":"xmqq7gf7f94f.fsf@gitster.dls.corp.google.com","threadId":"34774","inReplyTo":"1377577567-27655-6-git-send-email-nico@fluxnic.net","subject":"Re: [PATCH 05/23] pack v4: add commit object parsing","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-27T15:26:08Z","receivedAt":"2013-08-27T15:26:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> Let's create another dictionary table to hold the author and committer\n> entries. We use the same table format used for tree entries where the\n> 16 bit data prefix is conveniently used to store the timezone value.\n>\n> In order to copy straight from a commit object buffer, dict_add_entry()\n> is modified to get the string length as the provided string pointer is\n> not always be null terminated.\n>\n> Signed-off-by: Nicolas Pitre \n> ---\n> @@ -135,8 +136,73 @@ static void sort_dict_entries_by_hits(struct dict_table *t)\n> \trehash_entries(t);\n> }\n> \n> +static struct dict_table *commit_name_table;\n> static struct dict_table *tree_path_table;\n> \n> +/*\n> + * Parse the author/committer line from a canonical commit object.\n> + * The 'from' argument points right after the \"author \" or \"committer \"\n> + * string. The time zone is parsed and stored in *tz_val. The returned\n> + * pointer is right after the end of the email address which is also just\n> + * before the time value, or NULL if a parsing error is encountered.\n> + */\n> +static char *get_nameend_and_tz(char *from, int *tz_val)\n> +{\n> +\tchar *end, *tz;\n> +\n> +\ttz = strchr(from, '\\n');\n> +\t/* let's assume the smallest possible string to be \"x 0 +0000\\n\" */\n> +\tif (!tz || tz - from < 13)\n> +\t\treturn NULL;\n> +\ttz -= 4;\n> +\tend = tz - 4;\n> +\twhile (end - from > 5 && *end != ' ')\n> +\t\tend--;\n> +\tif (end[-1] != '>' || end[0] != ' ' || tz[-2] != ' ')\n> +\t\treturn NULL;\n> +\t*tz_val = (tz[0] - '0') * 1000 +\n> +\t\t (tz[1] - '0') * 100 +\n> +\t\t (tz[2] - '0') * 10 +\n> +\t\t (tz[3] - '0');\n> +\tswitch (tz[-1]) {\n> +\tdefault:\treturn NULL;\n> +\tcase '+':\tbreak;\n> +\tcase '-':\t*tz_val = -*tz_val;\n> +\t}\n> +\treturn end;\n> +}\n\nThis may want to share code with ident.c::split_ident_line(), as we\nhave been trying to reduce the number of ident-line parsers.\n"},{"id":"226005","messageId":"xmqq38pvf8yo.fsf@gitster.dls.corp.google.com","threadId":"34774","inReplyTo":"1377577567-27655-9-git-send-email-nico@fluxnic.net","subject":"Re: [PATCH 08/23] pack v4: basic references encoding","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-27T15:29:35Z","receivedAt":"2013-08-27T15:29:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> Add variable length number encoding. Let's apply the same encoding\n> currently used for the offset to base of OBJ_OFS_DELTA objects which\n> is the most efficient way to do this, and apply it to everything with\n> pack version 4.\n>\n> Also add SHA1 reference encoding. This one is either an index into a\n> SHA1 table encoded using the variable length number encoding, or the\n> literal 20 bytes SHA1 prefixed with a 0.\n>\n> The index 0 discriminates between an actual index value or the literal\n> SHA1. Therefore when the index is used its value must be increased by 1.\n>\n> Signed-off-by: Nicolas Pitre \n> ---\n> packv4-create.c | 44 ++++++++++++++++++++++++++++++++++++++++++++\n> 1 file changed, 44 insertions(+)\n>\n> diff --git a/packv4-create.c b/packv4-create.c\n> index 012129b..bf33d15 100644\n> --- a/packv4-create.c\n> +++ b/packv4-create.c\n> @@ -245,6 +245,50 @@ static void dict_dump(void)\n> \tdump_dict_table(tree_path_table);\n> }\n> \n> +/*\n> + * Encode a numerical value with variable length into the destination buffer\n> + */\n> +static unsigned char *add_number(unsigned char *dst, uint64_t value)\n> +{\n> +\tunsigned char buf[20];\n> +\tunsigned pos = sizeof(buf) - 1;\n> +\tbuf[pos] = value & 127;\n> +\twhile (value >>= 7)\n> +\t\tbuf[--pos] = 128 | (--value & 127);\n> +\tdo {\n> +\t\t*dst++ = buf[pos++];\n> +\t} while (pos < sizeof(buf));\n> +\treturn dst;\n> +}\n\nThis may want to reuse (or enhance-then-reuse) varint.[ch].\n\n> +/*\n> + * Encode an object SHA1 reference with either an object index into the\n> + * pack SHA1 table incremented by 1, or the literal SHA1 value prefixed\n> + * with a zero byte if the needed SHA1 is not available in the table.\n> + */\n> +static struct pack_idx_entry *all_objs;\n> +static unsigned all_objs_nr;\n> +static unsigned char *add_sha1_ref(unsigned char *dst, const unsigned char *sha1)\n> +{\n> +\tunsigned lo = 0, hi = all_objs_nr;\n> +\n> +\tdo {\n> +\t\tunsigned mi = (lo + hi) / 2;\n> +\t\tint cmp = hashcmp(all_objs[mi].sha1, sha1);\n> +\n> +\t\tif (cmp == 0)\n> +\t\t\treturn add_number(dst, mi + 1);\n> +\t\tif (cmp > 0)\n> +\t\t\thi = mi;\n> +\t\telse\n> +\t\t\tlo = mi+1;\n> +\t} while (lo < hi);\n> +\n> +\t*dst++ = 0;\n> +\thashcpy(dst, sha1);\n> +\treturn dst + 20;\n> +}\n> +\n> static struct pack_idx_entry *get_packed_object_list(struct packed_git *p)\n> {\n> \tunsigned i, nr_objects = p->num_objects;\n"},{"id":"226006","messageId":"xmqqy57ndtxb.fsf@gitster.dls.corp.google.com","threadId":"34774","inReplyTo":"1377577567-27655-10-git-send-email-nico@fluxnic.net","subject":"Re: [PATCH 09/23] pack v4: commit object encoding","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-27T15:39:44Z","receivedAt":"2013-08-27T15:39:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> This goes as follows:\n>\n> - Tree reference: either variable length encoding of the index\n> into the SHA1 table or the literal SHA1 prefixed by 0 (see\n> add_sha1_ref()).\n>\n> - Parent count: variable length encoding of the number of parents.\n> This is normally going to occupy a single byte but doesn't have to.\n>\n> - List of parent references: a list of add_sha1_ref() encoded references,\n> or nothing if the parent count was zero.\n>\n> - Author reference: variable length encoding of an index into the author\n> string dictionary table which also covers the time zone. To make the\n> overall encoding efficient, the author table is already sorted by usage\n> frequency so the most used names are first and require the shortest\n> index encoding.\n>\n> - Author time stamp: variable length encoded. Year 2038 ready!\n>\n> - Committer reference: same as author reference.\n>\n> - Committer time stamp: same as author time stamp.\n>\n> The remainder of the canonical commit object content is then zlib\n> compressed and appended to the above.\n>\n> Rationale: The most important commit object data is densely encoded while\n> requiring no zlib inflate processing, and all SHA1 references are most\n> likely to be direct indices into the pack index file requiring no SHA1\n> search into the pack index file.\n>\n> Signed-off-by: Nicolas Pitre \n> ---\n> packv4-create.c | 119 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n> 1 file changed, 119 insertions(+)\n>\n> diff --git a/packv4-create.c b/packv4-create.c\n> index bf33d15..cedbbd9 100644\n> --- a/packv4-create.c\n> +++ b/packv4-create.c\n> @@ -13,6 +13,9 @@\n> #include \"tree-walk.h\"\n> #include \"pack.h\"\n> \n> +\n> +static int pack_compression_level = Z_DEFAULT_COMPRESSION;\n> +\n> struct data_entry {\n> \tunsigned offset;\n> \tunsigned size;\n> @@ -289,6 +292,122 @@ static unsigned char *add_sha1_ref(unsigned char *dst, const unsigned char *sha1\n> \treturn dst + 20;\n> }\n> \n> +/*\n> + * This converts a canonical commit object buffer into its\n> + * tightly packed representation using the already populated\n> + * and sorted commit_name_table dictionary. The parsing is\n> + * strict so to ensure the canonical version may always be\n> + * regenerated and produce the same hash.\n> + */\n> +void * conv_to_dict_commit(void *buffer, unsigned long *psize)\n\nDrop SP between asterisk and \"conv_\"?\n\n> +{\n> +\tunsigned long size = *psize;\n> +\tchar *in, *tail, *end;\n> +\tunsigned char *out;\n> +\tunsigned char sha1[20];\n> +\tint nb_parents, index, tz_val;\n> +\tunsigned long time;\n> +\tz_stream stream;\n> +\tint status;\n> +\n> +\t/*\n> +\t * It is guaranteed that the output is always going to be smaller\n> +\t * than the input. We could even do this conversion in place.\n> +\t */\n> +\tin = buffer;\n> +\ttail = in + size;\n> +\tbuffer = xmalloc(size);\n> +\tout = buffer;\n> +\n> +\t/* parse the \"tree\" line */\n> +\tif (in + 46 >= tail || memcmp(in, \"tree \", 5) || in[45] != '\\n')\n> +\t\tgoto bad_data;\n> +\tif (get_sha1_hex(in + 5, sha1) < 0)\n> +\t\tgoto bad_data;\n\nIs this strict enough to guarantee roundtrip hash identity? Because\nget_sha1_hex() accepts hexadecimal represented with uppercase A-F,\nyou need to reject such a \"broken\" commit object, no?\n\nSame for parent commit object names below that are parsed with the\nsame helper.\n"},{"id":"226007","messageId":"xmqqtxibdtpy.fsf@gitster.dls.corp.google.com","threadId":"34774","inReplyTo":"1377577567-27655-11-git-send-email-nico@fluxnic.net","subject":"Re: [PATCH 10/23] pack v4: tree object encoding","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-27T15:44:09Z","receivedAt":"2013-08-27T15:44:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> This goes as follows:\n>\n> - Number of tree entries: variable length encoded.\n>\n> Then for each tree entry:\n>\n> - Path component reference: variable length encoded index into the path\n> string dictionary table which also covers the entry mode. To make the\n> overall encoding efficient, the author table is already sorted by usage\n> frequency so the most used names are first and require the shortest\n> index encoding.\n\ns/author table/tree path table/, I think. The reason why it is a\ngood idea to sort these tables by use count applies equally to both\nthe author table and the tree path table, though.\n\n> - SHA1 reference: either variable length encoding of the index into the\n> SHA1 table or the literal SHA1 prefixed by 0 (see add_sha1_ref()).\n>\n> Rationale: all the tree object data is densely encoded while requiring\n> no zlib inflate processing, and all SHA1 references are most likely to\n> be direct indices into the pack index file requiring no SHA1 search.\n> Path filtering can be accomplished on the path index directly without\n> any string comparison during the tree traversal.\n>\n> Still lacking is some kind of delta encoding for multiple tree objects\n> with only small differences between them. But that'll come later.\n>\n> Signed-off-by: Nicolas Pitre \n> ---\n> packv4-create.c | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n> 1 file changed, 63 insertions(+)\n>\n> diff --git a/packv4-create.c b/packv4-create.c\n> index cedbbd9..f46fbd9 100644\n> --- a/packv4-create.c\n> +++ b/packv4-create.c\n> @@ -408,6 +408,69 @@ bad:\n> \treturn NULL;\n> }\n> \n> +/*\n> + * This converts a canonical tree object buffer into its\n> + * tightly packed representation using the already populated\n> + * and sorted tree_path_table dictionary. The parsing is\n> + * strict so to ensure the canonical version may always be\n> + * regenerated and produce the same hash.\n> + */\n> +void * conv_to_dict_tree(void *buffer, unsigned long *psize)\n> +{\n> +\tunsigned long size = *psize;\n> +\tunsigned char *in, *out, *end;\n> +\tstruct tree_desc desc;\n> +\tstruct name_entry name_entry;\n> +\tint nb_entries;\n> +\n> +\tif (!size)\n> +\t\treturn NULL;\n> +\n> +\t/*\n> +\t * We can't make sure the result will always be smaller.\n> +\t * The smallest possible entry is \"0 x\\0<40 byte SHA1>\"\n> +\t * or 44 bytes. The output entry may have a realistic path index\n> +\t * encoding using up to 3 bytes, and a non indexable SHA1 meaning\n> +\t * 41 bytes. And the output data already has the and nb_entries\n> +\t * headers. In practice the output size will be significantly\n> +\t * smaller but for now let's make it simple.\n> +\t */\n> +\tin = buffer;\n> +\tout = xmalloc(size);\n> +\tend = out + size;\n> +\tbuffer = out;\n> +\n> +\t/* let's count how many entries there are */\n> +\tinit_tree_desc(&desc, in, size);\n> +\tnb_entries = 0;\n> +\twhile (tree_entry(&desc, &name_entry))\n> +\t\tnb_entries++;\n> +\tout = add_number(out, nb_entries);\n> +\n> +\tinit_tree_desc(&desc, in, size);\n> +\twhile (tree_entry(&desc, &name_entry)) {\n> +\t\tint pathlen = tree_entry_len(&name_entry);\n> +\t\tint index = dict_add_entry(tree_path_table, name_entry.mode,\n> +\t\t\t\t\t name_entry.path, pathlen);\n> +\t\tif (index < 0) {\n> +\t\t\terror(\"missing tree dict entry\");\n> +\t\t\tfree(buffer);\n> +\t\t\treturn NULL;\n> +\t\t}\n> +\t\tif (end - out < 45) {\n> +\t\t\tunsigned long sofar = out - (unsigned char *)buffer;\n> +\t\t\tbuffer = xrealloc(buffer, sofar + 45);\n> +\t\t\tout = (unsigned char *)buffer + sofar;\n> +\t\t\tend = out + 45;\n> +\t\t}\n> +\t\tout = add_number(out, index);\n> +\t\tout = add_sha1_ref(out, name_entry.sha1);\n> +\t}\n> +\n> +\t*psize = out - (unsigned char *)buffer;\n> +\treturn buffer;\n> +}\n> +\n> static struct pack_idx_entry *get_packed_object_list(struct packed_git *p)\n> {\n> \tunsigned i, nr_objects = p->num_objects;\n"},{"id":"226008","messageId":"xmqqppszdtiv.fsf@gitster.dls.corp.google.com","threadId":"34774","inReplyTo":"1377577567-27655-13-git-send-email-nico@fluxnic.net","subject":"Re: [PATCH 12/23] pack v4: creation code","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-27T15:48:24Z","receivedAt":"2013-08-27T15:48:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> Let's actually open the destination pack file and write the header and\n> the tables.\n>\n> The header isn't much different from pack v3, except for the pack version\n> number of course.\n>\n> The first table is the sorted SHA1 table normally found in the pack index\n> file. With pack v4 we write this table in the main pack file instead as\n> it is index referenced by subsequent objects in the pack. Doing so has\n> many advantages:\n>\n> - The SHA1 references used to be duplicated on disk: once in the pack\n> index file, and then at least once or more within commit and tree\n> objects referencing them. The only SHA1 which is not being listed more\n> than once this way is the one for a branch tip commit object and those\n> are normally very few. Now all that SHA1 data is represented only once.\n>\n\nThis tickles my curiosity. Why isn't this SHA-1 table sorted by\nreference count the same way as the tree path and the people name\ntables to keep the average length of varint references short?\n\n> - The SHA1 references found in commit and tree objects can be obtained\n> on disk directly without having to deflate those objects first.\n>\n> The SHA1 table size is obtained by multiplying the number of objects by 20.\n>\n> And then the commit and path dictionary tables are written right after\n> the SHA1 table.\n\n> Signed-off-by: Nicolas Pitre \n> ---\n> packv4-create.c | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++-----\n> 1 file changed, 55 insertions(+), 5 deletions(-)\n>\n> diff --git a/packv4-create.c b/packv4-create.c\n> index 2956fda..5211f9c 100644\n> --- a/packv4-create.c\n> +++ b/packv4-create.c\n> @@ -605,6 +605,48 @@ static unsigned long write_dict_table(struct sha1file *f, struct dict_table *t)\n> \treturn hdrlen + datalen;\n> }\n> \n> +static struct sha1file * packv4_open(char *path)\n> +{\n> +\tint fd;\n> +\n> +\tfd = open(path, O_CREAT|O_EXCL|O_WRONLY, 0600);\n> +\tif (fd < 0)\n> +\t\tdie_errno(\"unable to create '%s'\", path);\n> +\treturn sha1fd(fd, path);\n> +}\n> +\n> +static unsigned int packv4_write_header(struct sha1file *f, unsigned nr_objects)\n> +{\n> +\tstruct pack_header hdr;\n> +\n> +\thdr.hdr_signature = htonl(PACK_SIGNATURE);\n> +\thdr.hdr_version = htonl(4);\n> +\thdr.hdr_entries = htonl(nr_objects);\n> +\tsha1write(f, &hdr, sizeof(hdr));\n> +\n> +\treturn sizeof(hdr);\n> +}\n> +\n> +static unsigned long packv4_write_tables(struct sha1file *f, unsigned nr_objects,\n> +\t\t\t\t\t struct pack_idx_entry *objs)\n> +{\n> +\tunsigned i;\n> +\tunsigned long written = 0;\n> +\n> +\t/* The sorted list of object SHA1's is always first */\n> +\tfor (i = 0; i < nr_objects; i++)\n> +\t\tsha1write(f, objs[i].sha1, 20);\n> +\twritten = 20 * nr_objects;\n> +\n> +\t/* Then the commit dictionary table */\n> +\twritten += write_dict_table(f, commit_name_table);\n> +\n> +\t/* Followed by the path component dictionary table */\n> +\twritten += write_dict_table(f, tree_path_table);\n> +\n> +\treturn written;\n> +}\n> +\n> static struct packed_git *open_pack(const char *path)\n> {\n> \tchar arg[PATH_MAX];\n> @@ -658,9 +700,10 @@ static struct packed_git *open_pack(const char *path)\n> \treturn p;\n> }\n> \n> -static void process_one_pack(char *src_pack)\n> +static void process_one_pack(char *src_pack, char *dst_pack)\n> {\n> \tstruct packed_git *p;\n> +\tstruct sha1file *f;\n> \tstruct pack_idx_entry *objs, **p_objs;\n> \tunsigned nr_objects;\n> \n> @@ -673,15 +716,22 @@ static void process_one_pack(char *src_pack)\n> \tp_objs = sort_objs_by_offset(objs, nr_objects);\n> \n> \tcreate_pack_dictionaries(p, p_objs);\n> +\n> +\tf = packv4_open(dst_pack);\n> +\tif (!f)\n> +\t\tdie(\"unable to open destination pack\");\n> +\tpackv4_write_header(f, nr_objects);\n> +\tpackv4_write_tables(f, nr_objects, objs);\n> }\n> \n> int main(int argc, char *argv[])\n> {\n> -\tif (argc != 2) {\n> -\t\tfprintf(stderr, \"Usage: %s \\n\", argv[0]);\n> +\tif (argc != 3) {\n> +\t\tfprintf(stderr, \"Usage: %s \\n\", argv[0]);\n> \t\texit(1);\n> \t}\n> -\tprocess_one_pack(argv[1]);\n> -\tdict_dump();\n> +\tprocess_one_pack(argv[1], argv[2]);\n> +\tif (0)\n> +\t\tdict_dump();\n> \treturn 0;\n> }\n"},{"id":"226009","messageId":"alpine.LFD.2.03.1308271151570.14472@syhkavp.arg","threadId":"34774","inReplyTo":"xmqq38pvf8yo.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 08/23] pack v4: basic references encoding","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T15:53:18Z","receivedAt":"2013-08-27T15:53:18Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 27 Aug 2013, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > Add variable length number encoding. Let's apply the same encoding\n> > currently used for the offset to base of OBJ_OFS_DELTA objects which\n> > is the most efficient way to do this, and apply it to everything with\n> > pack version 4.\n> >\n> > Also add SHA1 reference encoding. This one is either an index into a\n> > SHA1 table encoded using the variable length number encoding, or the\n> > literal 20 bytes SHA1 prefixed with a 0.\n> >\n> > The index 0 discriminates between an actual index value or the literal\n> > SHA1. Therefore when the index is used its value must be increased by 1.\n> >\n> > Signed-off-by: Nicolas Pitre \n> > ---\n> > packv4-create.c | 44 ++++++++++++++++++++++++++++++++++++++++++++\n> > 1 file changed, 44 insertions(+)\n> >\n> > diff --git a/packv4-create.c b/packv4-create.c\n> > index 012129b..bf33d15 100644\n> > --- a/packv4-create.c\n> > +++ b/packv4-create.c\n> > @@ -245,6 +245,50 @@ static void dict_dump(void)\n> > \tdump_dict_table(tree_path_table);\n> > }\n> > \n> > +/*\n> > + * Encode a numerical value with variable length into the destination buffer\n> > + */\n> > +static unsigned char *add_number(unsigned char *dst, uint64_t value)\n> > +{\n> > +\tunsigned char buf[20];\n> > +\tunsigned pos = sizeof(buf) - 1;\n> > +\tbuf[pos] = value & 127;\n> > +\twhile (value >>= 7)\n> > +\t\tbuf[--pos] = 128 | (--value & 127);\n> > +\tdo {\n> > +\t\t*dst++ = buf[pos++];\n> > +\t} while (pos < sizeof(buf));\n> > +\treturn dst;\n> > +}\n> \n> This may want to reuse (or enhance-then-reuse) varint.[ch].\n\nGoodie! I didn't notice this had happened.\n\n\nNicolas\n"},{"id":"226010","messageId":"xmqqli3ndt9z.fsf@gitster.dls.corp.google.com","threadId":"34774","inReplyTo":"1377577567-27655-15-git-send-email-nico@fluxnic.net","subject":"Re: [PATCH 14/23] pack v4: object data copy","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-27T15:53:44Z","receivedAt":"2013-08-27T15:53:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> Blob and tag objects have no particular changes except for their object\n> header.\n>\n> Delta objects are also copied as is, except for their delta base reference\n> which is converted to the new way as used elsewhere in pack v4 encoding\n> i.e. an index into the SHA1 table or a literal SHA1 prefixed by 0 if not\n> found in the table (see add_sha1_ref). This is true for both REF_DELTA\n> as well as OFS_DELTA.\n>\n> Object payload is validated against the recorded CRC32 in the source\n> pack index file when possible.\n>\n> Signed-off-by: Nicolas Pitre \n> ---\n\nThe title somewhat confused me until I realized that this series is\nbuilding a program that would convert existing data from a single\npack into packv4 format, not a \"pack-objects --pack-verison=4\".\n\n> packv4-create.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n> 1 file changed, 66 insertions(+)\n>\n> diff --git a/packv4-create.c b/packv4-create.c\n> index 6e0bb1d..a6dc818 100644\n> --- a/packv4-create.c\n> +++ b/packv4-create.c\n> @@ -12,6 +12,7 @@\n> #include \"object.h\"\n> #include \"tree-walk.h\"\n> #include \"pack.h\"\n> +#include \"pack-revindex.h\"\n> \n> \n> static int pack_compression_level = Z_DEFAULT_COMPRESSION;\n> @@ -673,6 +674,71 @@ static unsigned int write_object_header(struct sha1file *f, enum object_type typ\n> \treturn end - buf;\n> }\n> \n> +static unsigned long copy_object_data(struct sha1file *f, struct packed_git *p,\n> +\t\t\t\t off_t offset)\n> +{\n> +\tstruct pack_window *w_curs = NULL;\n> +\tstruct revindex_entry *revidx;\n> +\tenum object_type type;\n> +\tunsigned long avail, size, datalen, written;\n> +\tint hdrlen, idx_nr;\n> +\tunsigned char *src, *end, buf[24];\n> +\n> +\trevidx = find_pack_revindex(p, offset);\n> +\tidx_nr = revidx->nr;\n> +\tdatalen = revidx[1].offset - offset;\n> +\n> +\tsrc = use_pack(p, &w_curs, offset, &avail);\n> +\thdrlen = unpack_object_header_buffer(src, avail, &type, &size);\n> +\n> +\twritten = write_object_header(f, type, size);\n> +\n> +\tif (type == OBJ_OFS_DELTA) {\n> +\t\tunsigned char c = src[hdrlen++];\n> +\t\toff_t base_offset = c & 127;\n> +\t\twhile (c & 128) {\n> +\t\t\tbase_offset += 1;\n> +\t\t\tif (!base_offset || MSB(base_offset, 7))\n> +\t\t\t\tdie(\"delta offset overflow\");\n> +\t\t\tc = src[hdrlen++];\n> +\t\t\tbase_offset = (base_offset << 7) + (c & 127);\n> +\t\t}\n> +\t\tbase_offset = offset - base_offset;\n> +\t\tif (base_offset <= 0 || base_offset >= offset)\n> +\t\t\tdie(\"delta offset out of bound\");\n> +\t\trevidx = find_pack_revindex(p, base_offset);\n> +\t\tend = add_sha1_ref(buf, nth_packed_object_sha1(p, revidx->nr));\n> +\t\tsha1write(f, buf, end - buf);\n> +\t\twritten += end - buf;\n> +\t} else if (type == OBJ_REF_DELTA) {\n> +\t\tend = add_sha1_ref(buf, src + hdrlen);\n> +\t\thdrlen += 20;\n> +\t\tsha1write(f, buf, end - buf);\n> +\t\twritten += end - buf;\n> +\t}\n> +\n> +\tif (p->index_version > 1 &&\n> +\t check_pack_crc(p, &w_curs, offset, datalen, idx_nr))\n> +\t\tdie(\"bad CRC for object at offset %\"PRIuMAX\" in %s\",\n> +\t\t (uintmax_t)offset, p->pack_name);\n> +\n> +\toffset += hdrlen;\n> +\tdatalen -= hdrlen;\n> +\n> +\twhile (datalen) {\n> +\t\tsrc = use_pack(p, &w_curs, offset, &avail);\n> +\t\tif (avail > datalen)\n> +\t\t\tavail = datalen;\n> +\t\tsha1write(f, src, avail);\n> +\t\twritten += avail;\n> +\t\toffset += avail;\n> +\t\tdatalen -= avail;\n> +\t}\n> +\tunuse_pack(&w_curs);\n> +\n> +\treturn written;\n> +}\n> +\n> static struct packed_git *open_pack(const char *path)\n> {\n> \tchar arg[PATH_MAX];\n"},{"id":"226011","messageId":"alpine.LFD.2.03.1308271153370.14472@syhkavp.arg","threadId":"34774","inReplyTo":"xmqqioyrfa5m.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 00/23] Preliminary pack v4 support","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T15:59:45Z","receivedAt":"2013-08-27T15:59:45Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 27 Aug 2013, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > Subject says it all... at last !\n> >\n> > This can also be fetched here:\n> >\n> > \tgit://git.linaro.org/people/nico/git\n> >\n> > Demonstration of what it does at the moment:\n> >\n> > \thttp://article.gmane.org/gmane.comp.version-control.git/233038\n> >\n> > I'd like to preserve the author time stamps as they relate to where in\n> > the world I was when the corresponding code was written. You'll notice\n> > I didn't work on the code in the same order as it is now presented.\n> \n> We can also notice things like \"From: user@machine.(none)\" ;-)\n\nHeh.\n\n> > Still open question: what to do with a thin pack. Should we really\n> > complete it with local objects upon reception, or were we only over\n> > paranoid at the time we imposed this rule?\n> \n> I do not think paranoia had much to do with it. I am afraid that\n> allowing a delta in a pack to depend on a base in another pack means\n> that the former pack becomes unusable without the latter, which\n> would make object store management (e.g. partial repacking) a lot\n> more cumbersome, no?\n\nThat's what I'm wondering. We already end up with a broken repository \nif the commit graph is spread across multiple packs and one of those \npack is removed. Having a delta base in a separate pack is not much \ndifferent in that regard.\n\nSo the rule could be that any kind of repacking must not carry over \ndeltas with a non local base i.e. repack always produces delta \nreferences belonging to the same pack.\n\n\nNicolas\n"},{"id":"226012","messageId":"alpine.LFD.2.03.1308271205090.14472@syhkavp.arg","threadId":"34774","inReplyTo":"xmqqbo4jf9yf.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 01/23] pack v4: initial pack dictionary structure and code","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T16:13:25Z","receivedAt":"2013-08-27T16:13:25Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 27 Aug 2013, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > Signed-off-by: Nicolas Pitre \n> > ---\n> \n> Was there a reason not to reuse the hash-table Linus did in\n> hash.[ch]?\n\nWell... Most likely because when I started that code (which used to be \nquite different initially) it might not have been served correctly by \nhash.c, or any other reasons I long have forgotten by now which might or \nmight not still be valid.\n\n> It may not make much of a difference for something so small and\n> isolated from the rest of the system, but if hash.[ch] can be easily\n> fixed with a small tweak to suit the use by this subsystem better,\n> it might be worth reusing the existing code with improvement, which\n> may help other potential users.\n\nAbsolutely. If someone wants to give a hand in that direction I'll \nhappily integrate patches into my series. I cannot promise I'll do the \nwork myself as I prefer spending the time I have available on actually \nmaking pack v4 usable.\n\n\nNicolas\n"},{"id":"226015","messageId":"xmqq8uzndqws.fsf@gitster.dls.corp.google.com","threadId":"34774","inReplyTo":"alpine.LFD.2.03.1308271153370.14472@syhkavp.arg","subject":"Re: [PATCH 00/23] Preliminary pack v4 support","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-27T16:44:51Z","receivedAt":"2013-08-27T16:44:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> On Tue, 27 Aug 2013, Junio C Hamano wrote:\n>\n>> Nicolas Pitre writes:\n>> ... \n>> > I'd like to preserve the author time stamps as they relate to where in\n>> > the world I was when the corresponding code was written. You'll notice\n>> > I didn't work on the code in the same order as it is now presented.\n>> \n>> We can also notice things like \"From: user@machine.(none)\" ;-)\n>\n> Heh.\n\nIn any case, the \"Date: \" in-body header next to your \"From: \"\nin-body header is your friend if you want to do the \"where and when\ndid I work on this?\"\n\n>> > Still open question: what to do with a thin pack. Should we really\n>> > complete it with local objects upon reception, or were we only over\n>> > paranoid at the time we imposed this rule?\n>> \n>> I do not think paranoia had much to do with it. I am afraid that\n>> allowing a delta in a pack to depend on a base in another pack means\n>> that the former pack becomes unusable without the latter, which\n>> would make object store management (e.g. partial repacking) a lot\n>> more cumbersome, no?\n>\n> That's what I'm wondering. We already end up with a broken repository \n> if the commit graph is spread across multiple packs and one of those \n> pack is removed. Having a delta base in a separate pack is not much \n> different in that regard.\n\nIn practice, maybe, but I somehow find that it is more fundamental\nbreakage not to be able to reconstitute objects that a pack and its\nindex claims to have than missing an object that is referenced in\nthe reachability graph.\n\nAs you have \"0-index\" escape hatch for SHA-1 table, but no similar\nescape hatch for the people's name table, I can see why it may be\ncumbersome to fix a thin pack by only appending to a received\npackfile and updating a few header fields, though.\n\n> So the rule could be that any kind of repacking must not carry over \n> deltas with a non local base i.e. repack always produces delta \n> references belonging to the same pack.\n"},{"id":"226016","messageId":"alpine.LFD.2.03.1308271238270.14472@syhkavp.arg","threadId":"34774","inReplyTo":"xmqq7gf7f94f.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 05/23] pack v4: add commit object parsing","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T16:47:20Z","receivedAt":"2013-08-27T16:47:20Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 27 Aug 2013, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > Let's create another dictionary table to hold the author and committer\n> > entries. We use the same table format used for tree entries where the\n> > 16 bit data prefix is conveniently used to store the timezone value.\n> >\n> > In order to copy straight from a commit object buffer, dict_add_entry()\n> > is modified to get the string length as the provided string pointer is\n> > not always be null terminated.\n> >\n> > Signed-off-by: Nicolas Pitre \n> > ---\n> > @@ -135,8 +136,73 @@ static void sort_dict_entries_by_hits(struct dict_table *t)\n> > \trehash_entries(t);\n> > }\n> > \n> > +static struct dict_table *commit_name_table;\n> > static struct dict_table *tree_path_table;\n> > \n> > +/*\n> > + * Parse the author/committer line from a canonical commit object.\n> > + * The 'from' argument points right after the \"author \" or \"committer \"\n> > + * string. The time zone is parsed and stored in *tz_val. The returned\n> > + * pointer is right after the end of the email address which is also just\n> > + * before the time value, or NULL if a parsing error is encountered.\n> > + */\n> > +static char *get_nameend_and_tz(char *from, int *tz_val)\n> > +{\n> > +\tchar *end, *tz;\n> > +\n> > +\ttz = strchr(from, '\\n');\n> > +\t/* let's assume the smallest possible string to be \"x 0 +0000\\n\" */\n> > +\tif (!tz || tz - from < 13)\n> > +\t\treturn NULL;\n> > +\ttz -= 4;\n> > +\tend = tz - 4;\n> > +\twhile (end - from > 5 && *end != ' ')\n> > +\t\tend--;\n> > +\tif (end[-1] != '>' || end[0] != ' ' || tz[-2] != ' ')\n> > +\t\treturn NULL;\n> > +\t*tz_val = (tz[0] - '0') * 1000 +\n> > +\t\t (tz[1] - '0') * 100 +\n> > +\t\t (tz[2] - '0') * 10 +\n> > +\t\t (tz[3] - '0');\n> > +\tswitch (tz[-1]) {\n> > +\tdefault:\treturn NULL;\n> > +\tcase '+':\tbreak;\n> > +\tcase '-':\t*tz_val = -*tz_val;\n> > +\t}\n> > +\treturn end;\n> > +}\n> \n> This may want to share code with ident.c::split_ident_line(), as we\n> have been trying to reduce the number of ident-line parsers.\n\nHmmm.... The problem I have with split_ident_line() right now is about \nthe fact that it is too liberal with whitespaces. Here I must be sure I \ncan deconstruct a commit object and be sure I still can regenerate it \nbyte for byte in order to match its SHA1 signature.\n\nSo there _must_ always be only one space between the email closing \nbracket and the time stamp, only one space between the time stamp and \nthe time zone value, and no space after the time zone.\n\nIs there a reason why split_ident_line() is not stricter in that regard?\n\n\nNicolas\n"},{"id":"226017","messageId":"alpine.LFD.2.03.1308271249280.14472@syhkavp.arg","threadId":"34774","inReplyTo":"xmqqy57ndtxb.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 09/23] pack v4: commit object encoding","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T16:50:45Z","receivedAt":"2013-08-27T16:50:45Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 27 Aug 2013, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > This goes as follows:\n> >\n> > - Tree reference: either variable length encoding of the index\n> > into the SHA1 table or the literal SHA1 prefixed by 0 (see\n> > add_sha1_ref()).\n> >\n> > - Parent count: variable length encoding of the number of parents.\n> > This is normally going to occupy a single byte but doesn't have to.\n> >\n> > - List of parent references: a list of add_sha1_ref() encoded references,\n> > or nothing if the parent count was zero.\n> >\n> > - Author reference: variable length encoding of an index into the author\n> > string dictionary table which also covers the time zone. To make the\n> > overall encoding efficient, the author table is already sorted by usage\n> > frequency so the most used names are first and require the shortest\n> > index encoding.\n> >\n> > - Author time stamp: variable length encoded. Year 2038 ready!\n> >\n> > - Committer reference: same as author reference.\n> >\n> > - Committer time stamp: same as author time stamp.\n> >\n> > The remainder of the canonical commit object content is then zlib\n> > compressed and appended to the above.\n> >\n> > Rationale: The most important commit object data is densely encoded while\n> > requiring no zlib inflate processing, and all SHA1 references are most\n> > likely to be direct indices into the pack index file requiring no SHA1\n> > search into the pack index file.\n> >\n> > Signed-off-by: Nicolas Pitre \n> > ---\n> > packv4-create.c | 119 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n> > 1 file changed, 119 insertions(+)\n> >\n> > diff --git a/packv4-create.c b/packv4-create.c\n> > index bf33d15..cedbbd9 100644\n> > --- a/packv4-create.c\n> > +++ b/packv4-create.c\n> > @@ -13,6 +13,9 @@\n> > #include \"tree-walk.h\"\n> > #include \"pack.h\"\n> > \n> > +\n> > +static int pack_compression_level = Z_DEFAULT_COMPRESSION;\n> > +\n> > struct data_entry {\n> > \tunsigned offset;\n> > \tunsigned size;\n> > @@ -289,6 +292,122 @@ static unsigned char *add_sha1_ref(unsigned char *dst, const unsigned char *sha1\n> > \treturn dst + 20;\n> > }\n> > \n> > +/*\n> > + * This converts a canonical commit object buffer into its\n> > + * tightly packed representation using the already populated\n> > + * and sorted commit_name_table dictionary. The parsing is\n> > + * strict so to ensure the canonical version may always be\n> > + * regenerated and produce the same hash.\n> > + */\n> > +void * conv_to_dict_commit(void *buffer, unsigned long *psize)\n> \n> Drop SP between asterisk and \"conv_\"?\n> \n> > +{\n> > +\tunsigned long size = *psize;\n> > +\tchar *in, *tail, *end;\n> > +\tunsigned char *out;\n> > +\tunsigned char sha1[20];\n> > +\tint nb_parents, index, tz_val;\n> > +\tunsigned long time;\n> > +\tz_stream stream;\n> > +\tint status;\n> > +\n> > +\t/*\n> > +\t * It is guaranteed that the output is always going to be smaller\n> > +\t * than the input. We could even do this conversion in place.\n> > +\t */\n> > +\tin = buffer;\n> > +\ttail = in + size;\n> > +\tbuffer = xmalloc(size);\n> > +\tout = buffer;\n> > +\n> > +\t/* parse the \"tree\" line */\n> > +\tif (in + 46 >= tail || memcmp(in, \"tree \", 5) || in[45] != '\\n')\n> > +\t\tgoto bad_data;\n> > +\tif (get_sha1_hex(in + 5, sha1) < 0)\n> > +\t\tgoto bad_data;\n> \n> Is this strict enough to guarantee roundtrip hash identity? Because\n> get_sha1_hex() accepts hexadecimal represented with uppercase A-F,\n> you need to reject such a \"broken\" commit object, no?\n\nIndeed, yes. Same concern as with split_ident_line() I mentioned \nbefore.\n\n> Same for parent commit object names below that are parsed with the\n> same helper.\n\nExact.\n\n\nNicolas\n"},{"id":"226018","messageId":"alpine.LFD.2.03.1308271250540.14472@syhkavp.arg","threadId":"34774","inReplyTo":"xmqqtxibdtpy.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 10/23] pack v4: tree object encoding","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T16:52:03Z","receivedAt":"2013-08-27T16:52:03Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 27 Aug 2013, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > This goes as follows:\n> >\n> > - Number of tree entries: variable length encoded.\n> >\n> > Then for each tree entry:\n> >\n> > - Path component reference: variable length encoded index into the path\n> > string dictionary table which also covers the entry mode. To make the\n> > overall encoding efficient, the author table is already sorted by usage\n> > frequency so the most used names are first and require the shortest\n> > index encoding.\n> \n> s/author table/tree path table/, I think. The reason why it is a\n> good idea to sort these tables by use count applies equally to both\n> the author table and the tree path table, though.\n\nExact. This was a cut and paste mistake.\n\n\nNicolas\n"},{"id":"226020","messageId":"alpine.LFD.2.03.1308271252570.14472@syhkavp.arg","threadId":"34774","inReplyTo":"xmqqppszdtiv.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 12/23] pack v4: creation code","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T16:59:15Z","receivedAt":"2013-08-27T16:59:15Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 27 Aug 2013, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > Let's actually open the destination pack file and write the header and\n> > the tables.\n> >\n> > The header isn't much different from pack v3, except for the pack version\n> > number of course.\n> >\n> > The first table is the sorted SHA1 table normally found in the pack index\n> > file. With pack v4 we write this table in the main pack file instead as\n> > it is index referenced by subsequent objects in the pack. Doing so has\n> > many advantages:\n> >\n> > - The SHA1 references used to be duplicated on disk: once in the pack\n> > index file, and then at least once or more within commit and tree\n> > objects referencing them. The only SHA1 which is not being listed more\n> > than once this way is the one for a branch tip commit object and those\n> > are normally very few. Now all that SHA1 data is represented only once.\n> >\n> \n> This tickles my curiosity. Why isn't this SHA-1 table sorted by\n> reference count the same way as the tree path and the people name\n> tables to keep the average length of varint references short?\n\nDoing so allows for the SHA1 index used in objects to be used directly \nfor lookups into the pack index in order to know immediately the \nlocation of the referenced object bypassing the binary search. \nFurthermore, SHA1 references are rather evenly spread across the whole \ntable. Only tree objects may share the same SHA1 references repeatedly \nacross multiple objects, and those are likely to end up being deltas \nagainst each other.\n\n\nNicolas\n"},{"id":"226022","messageId":"xmqq4nabdo82.fsf@gitster.dls.corp.google.com","threadId":"34774","inReplyTo":"alpine.LFD.2.03.1308271238270.14472@syhkavp.arg","subject":"Re: [PATCH 05/23] pack v4: add commit object parsing","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-27T17:42:53Z","receivedAt":"2013-08-27T17:42:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> Hmmm.... The problem I have with split_ident_line() right now is about \n> the fact that it is too liberal with whitespaces. Here I must be sure I \n> can deconstruct a commit object and be sure I still can regenerate it \n> byte for byte in order to match its SHA1 signature.\n\nYeah, I now see. It's the same \"accept with leniency\"\nget_sha1_hex() does, which is not appropriate for the \npurpose of this codepath.\n"},{"id":"226036","messageId":"alpine.LFD.2.03.1308271409320.14472@syhkavp.arg","threadId":"34774","inReplyTo":"xmqqli3ndt9z.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 14/23] pack v4: object data copy","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T18:24:58Z","receivedAt":"2013-08-27T18:24:58Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 27 Aug 2013, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > Blob and tag objects have no particular changes except for their object\n> > header.\n> >\n> > Delta objects are also copied as is, except for their delta base reference\n> > which is converted to the new way as used elsewhere in pack v4 encoding\n> > i.e. an index into the SHA1 table or a literal SHA1 prefixed by 0 if not\n> > found in the table (see add_sha1_ref). This is true for both REF_DELTA\n> > as well as OFS_DELTA.\n> >\n> > Object payload is validated against the recorded CRC32 in the source\n> > pack index file when possible.\n> >\n> > Signed-off-by: Nicolas Pitre \n> > ---\n> \n> The title somewhat confused me until I realized that this series is\n> building a program that would convert existing data from a single\n> pack into packv4 format, not a \"pack-objects --pack-verison=4\".\n\nI initially started with extensions to pack-objects but that quickly \nbecame a big hassle to keep things working while experimenting. So this \ntool is just a straight pack converter which in itself turned out to be \nquite complex already. Eventually its code could be merged into \npack-objects.\n\n\nNicolas\n"},{"id":"226035","messageId":"xmqqzjs3c7pd.fsf@gitster.dls.corp.google.com","threadId":"34774","inReplyTo":"1377602225-30439-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH] Document pack v4 format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-27T18:25:02Z","receivedAt":"2013-08-27T18:25:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy writes:\n\n> Signed-off-by: Nguyễn Thái Ngọc Duy \n> ---\n> For my education but may help people who are interested in the\n> format. Most is gathered from commit messages, except the delta tree\n> entries.\n\nThanks.\n\n> diff --git a/Documentation/technical/pack-format-v4.txt b/Documentation/technical/pack-format-v4.txt\n\nIn the final version it may be a good idea to either have this\ntogether with the documentation for the existing pack-formats, or\nadd a reference from the documentation for the existing formats to\npoint at this new file saying \"for v4 see ...\".\n\n> new file mode 100644\n> index 0000000..9123a53\n> --- /dev/null\n> +++ b/Documentation/technical/pack-format-v4.txt\n> @@ -0,0 +1,110 @@\n> +Git pack v4 format\n> +==================\n> +\n> +== pack-*.pack files have the following format:\n> +\n> + - A header appears at the beginning and consists of the following:\n> +\n> + 4-byte signature:\n> +\t The signature is: {'P', 'A', 'C', 'K'}\n> +\n> + 4-byte version number (network byte order): must be version\n> + number 4\n> +\n> + 4-byte number of objects contained in the pack (network byte\n> + order)\n> +\n> + - (20 * nr_objects)-byte SHA-1 table: sorted in memcmp() order.\n> +\n> + - Commit name dictionary: the uncompressed length in variable\n> + encoding, followed by zlib-compressed dictionary. Each entry\n> + consists of two prefix bytes storing timezone followed by a\n> + NUL-terminated string.\n\nThe log and code use different names to call this thing. \"commit\nname\" is misleading (e.g. it is not \"commit object name\", but \"names\nrecorded in commit objects\"; it is not only for \"committer\" names,\nbut also applies to authors; it is not just names but also emails\nand TZ used). Perhaps a better name would be \"ident\" table, as we\nuse the word \"ident\" only to refer to data to refer to people who\nare recorded on either author/committer/tagger lines of the objects?\n\n> + (undeltified representation)\n> + n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n> + [uncompressed data]\n> + [compressed data]\n\nThese two lines are not useful; it is better spelled as [data\nspecific to object type] as you have to enumerate what are stored\nand how for each type separately anyway.\n\n> +=== Tree representation\n> +\n> + - n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n> +\n> + - Number of trees in variable length encoding\n> +\n> + - A number of trees, each consists of\n\nThe above \"number of trees\" sounds both wrong; aren't they the\nnumber of \"tree entries\" (that can be blobs or subtrees) this tree\nobject records?\n\n> + Path component reference: an index, in variable length encoding,\n> + into tree path dictionary, which also covers entry mode.\n> +\n> + SHA-1 in SHA-1 reference encoding.\n> +\n> +Path component reference zero is an indicator of deltified portion and\n> +has the following format:\n> +\n> + - path component reference: zero\n> +\n> + - index of the entry to copy from, in variable length encoding\n> +\n> + - number of entries in variable length encoding\n> +\n> + - base tree in SHA-1 reference encoding\n> +\n> +=== SHA-1 reference encoding\n> +\n> +This encoding is used to encode SHA-1 efficiently if it's already in\n> +the SHA-1 table. It starts with an index number in variable length\n> +encoding. If it's not zero, its value minus one is the index in the\n> +SHA-1 table. If it's zero, 20 bytes of SHA-1 is followed.\n"},{"id":"226037","messageId":"alpine.LFD.2.03.1308271433210.14472@syhkavp.arg","threadId":"34774","inReplyTo":"1377602225-30439-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH] Document pack v4 format","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T18:53:01Z","receivedAt":"2013-08-27T18:53:01Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 27 Aug 2013, Nguyễn Thái Ngọc Duy wrote:\n\n> \n> Signed-off-by: Nguyễn Thái Ngọc Duy \n> ---\n> For my education but may help people who are interested in the\n> format. Most is gathered from commit messages, except the delta tree\n> entries.\n\nExcellent! That's the kind of thing I need help with.\n\nSome corrections below.\n\n> Documentation/technical/pack-format-v4.txt (new) | 110 +++++++++++++++++++++++\n> 1 file changed, 110 insertions(+)\n> create mode 100644 Documentation/technical/pack-format-v4.txt\n> \n> diff --git a/Documentation/technical/pack-format-v4.txt b/Documentation/technical/pack-format-v4.txt\n> new file mode 100644\n> index 0000000..9123a53\n> --- /dev/null\n> +++ b/Documentation/technical/pack-format-v4.txt\n> @@ -0,0 +1,110 @@\n> +Git pack v4 format\n> +==================\n> +\n> +== pack-*.pack files have the following format:\n> +\n> + - A header appears at the beginning and consists of the following:\n> +\n> + 4-byte signature:\n> +\t The signature is: {'P', 'A', 'C', 'K'}\n> +\n> + 4-byte version number (network byte order): must be version\n> + number 4\n> +\n> + 4-byte number of objects contained in the pack (network byte\n> + order)\n\nConceptually, I'd suggest we don't talk about what follows as part of \nthe header. Maybe the \"tables\" section would make more sense.\n\n> + - (20 * nr_objects)-byte SHA-1 table: sorted in memcmp() order.\n> +\n> + - Commit name dictionary: the uncompressed length in variable\n> + encoding, followed by zlib-compressed dictionary. Each entry\n> + consists of two prefix bytes storing timezone followed by a\n> + NUL-terminated string.\n> +\n> + Entries should be sorted by frequency so that the most frequent\n> + entry has the smallest index, thus most efficient variable\n> + encoding.\n> +\n> + - Tree path dictionary: similar format to commit name\n> + dictionary. Each entry consists of two prefix bytes storing entry\n> + mode, then a NUL-terminated path name. Same sort order\n> + recommendation applies.\n> +\n> + - The header is followed by number of object entries, each of\n> + which looks like this:\n> +\n> + (undeltified representation)\n> + n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n> + [uncompressed data]\n> + [compressed data]\n> +\n> + (deltified representation)\n> + n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n> + base object name in SHA-1 reference encoding\n> + compressed delta data\n> +\n> + In undeltified format, blobs and tags do not have the\n> + uncompressed data, all object content is compressed. Trees are\n> + not compressed at all. Some headers in commits are stored\n> + uncompressed, the rest is compressed.\n> +\n> + All objects except trees are deltified and compressed the same\n> + way in v3. Trees however are deltified differently and use\n\nLet's note that commits are not deltified at all.\n\n> + undeltified representation. See \"Tree representation\" below for\n> + details.\n> +\n> + - The trailer records 20-byte SHA-1 checksum of all of the above.\n> +\n> +=== Commit representation\n> +\n> + - n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n> +\n> + - Tree SHA-1 in SHA-1 reference encoding\n> +\n> + - Parent count in variable length encoding\n> +\n> + - Parent SHA-1s in SHA-1 reference encoding\n> +\n> + - Author reference: the index, in variable length encoding, to comit\n> + name dictionary, which covers the name and also the time zone.\n> +\n> + - Author timestamp in variable length encoding\n> +\n> + - Committer reference: the index, in variable length encoding, to\n> + comit name dictionary, which covers the name and also the time\n> + zone.\n> +\n> + - Committer timestamp in variable length encoding\n> +\n> + - Compressed data of remaining header and the body\n> +\n> +=== Tree representation\n> +\n> + - n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n> +\n> + - Number of trees in variable length encoding\n\nMaybe that would be better to refer to tree entries instead of trees.\n\n> + - A number of trees, each consists of\n> +\n> + Path component reference: an index, in variable length encoding,\n> + into tree path dictionary, which also covers entry mode.\n\nNote the index nust have 1 added due to 0 being reserved.\n\n> + SHA-1 in SHA-1 reference encoding.\n> +\n> +Path component reference zero is an indicator of deltified portion and\n> +has the following format:\n> +\n> + - path component reference: zero\n> +\n> + - index of the entry to copy from, in variable length encoding\n\nI'd say \"index of the starting entry in the tree object to copy from\" to \nbe clearer. Also bit 0 of this index has a special meaning, therefore \nthe actual index must be shifted left by 1 bit.\n\n> + - number of entries in variable length encoding\n\n\"number of entries to copy ...\"\n\n> +\n> + - base tree in SHA-1 reference encoding\n\nThe presence of this one depends on bit 0 in the index above. If that \nbit is set then this base tree is provided. Otherwise it is not \nprovided and the previous base tree reference encountered in this tree \nobject should be used. This is to avoid repeating a SHA1 reference,\nespecially if a literal 20-byte SHA1 has to be used, when multiple \nreferences to the same base tree are made which is likely to be the \ncommon case.\n\n> +=== SHA-1 reference encoding\n> +\n> +This encoding is used to encode SHA-1 efficiently if it's already in\n> +the SHA-1 table. It starts with an index number in variable length\n> +encoding. If it's not zero, its value minus one is the index in the\n> +SHA-1 table. If it's zero, 20 bytes of SHA-1 is followed.\n> -- \n> 1.8.2.83.gc99314b\n"},{"id":"226057","messageId":"alpine.LFD.2.03.1308271553530.14472@syhkavp.arg","threadId":"34774","inReplyTo":"xmqqy57ndtxb.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 09/23] pack v4: commit object encoding","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T19:59:20Z","receivedAt":"2013-08-27T19:59:20Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 27 Aug 2013, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > +\t/* parse the \"tree\" line */\n> > +\tif (in + 46 >= tail || memcmp(in, \"tree \", 5) || in[45] != '\\n')\n> > +\t\tgoto bad_data;\n> > +\tif (get_sha1_hex(in + 5, sha1) < 0)\n> > +\t\tgoto bad_data;\n> \n> Is this strict enough to guarantee roundtrip hash identity? Because\n> get_sha1_hex() accepts hexadecimal represented with uppercase A-F,\n> you need to reject such a \"broken\" commit object, no?\n\nBTW, is there any such objects in existence where sha1 ascii strings are \nrepresented using uppercase letters? Because there would be a simple \nway to encode that fact in the pack v4 sha1 reference... but that change \nhas to happen now.\n\nI'm already claiming we won't support mixed case though.\n\n\nNicolas\n"},{"id":"226059","messageId":"xmqqob8ic2kv.fsf@gitster.dls.corp.google.com","threadId":"34774","inReplyTo":"alpine.LFD.2.03.1308271553530.14472@syhkavp.arg","subject":"Re: [PATCH 09/23] pack v4: commit object encoding","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-27T20:15:44Z","receivedAt":"2013-08-27T20:15:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> On Tue, 27 Aug 2013, Junio C Hamano wrote:\n>\n>> Nicolas Pitre writes:\n>> \n>> > +\t/* parse the \"tree\" line */\n>> > +\tif (in + 46 >= tail || memcmp(in, \"tree \", 5) || in[45] != '\\n')\n>> > +\t\tgoto bad_data;\n>> > +\tif (get_sha1_hex(in + 5, sha1) < 0)\n>> > +\t\tgoto bad_data;\n>> \n>> Is this strict enough to guarantee roundtrip hash identity? Because\n>> get_sha1_hex() accepts hexadecimal represented with uppercase A-F,\n>> you need to reject such a \"broken\" commit object, no?\n>\n> BTW, is there any such objects in existence where sha1 ascii strings are \n> represented using uppercase letters?\n\nAny commit or tag object that refers to another object with SHA-1\nusing uppercase letters is broken and invalid. get_sha1_hex() is\nnot limited to reading these (i.e. it also is used to read object\nname given on the command line) so it is lenient, but the above\ncodepath should care so that the result of hashing will stay the\nsame.\n\n> Because there would be a simple \n> way to encode that fact in the pack v4 sha1 reference... but that change \n> has to happen now.\n\nHence, I do not think we care.\n\n> I'm already claiming we won't support mixed case though.\n\nYeah, I am already claiming we won't support any uppercase ;-).\n"},{"id":"226067","messageId":"alpine.LFD.2.03.1308271740110.14472@syhkavp.arg","threadId":"34774","inReplyTo":"xmqqob8ic2kv.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 09/23] pack v4: commit object encoding","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-27T21:43:01Z","receivedAt":"2013-08-27T21:43:01Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 27 Aug 2013, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > On Tue, 27 Aug 2013, Junio C Hamano wrote:\n> >\n> >> Nicolas Pitre writes:\n> >> \n> >> > +\t/* parse the \"tree\" line */\n> >> > +\tif (in + 46 >= tail || memcmp(in, \"tree \", 5) || in[45] != '\\n')\n> >> > +\t\tgoto bad_data;\n> >> > +\tif (get_sha1_hex(in + 5, sha1) < 0)\n> >> > +\t\tgoto bad_data;\n> >> \n> >> Is this strict enough to guarantee roundtrip hash identity? Because\n> >> get_sha1_hex() accepts hexadecimal represented with uppercase A-F,\n> >> you need to reject such a \"broken\" commit object, no?\n> >\n> > BTW, is there any such objects in existence where sha1 ascii strings are \n> > represented using uppercase letters?\n> \n> Any commit or tag object that refers to another object with SHA-1\n> using uppercase letters is broken and invalid. get_sha1_hex() is\n> not limited to reading these (i.e. it also is used to read object\n> name given on the command line) so it is lenient, but the above\n> codepath should care so that the result of hashing will stay the\n> same.\n\nIndeed, hence my concern about encoding the original case.\n\n> > Because there would be a simple \n> > way to encode that fact in the pack v4 sha1 reference... but that change \n> > has to happen now.\n> \n> Hence, I do not think we care.\n> \n> > I'm already claiming we won't support mixed case though.\n> \n> Yeah, I am already claiming we won't support any uppercase ;-).\n\nPerfect!\n\nI've added a get_sha1_lowhex() to my tree.\n\n\nNicolas\n"},{"id":"226076","messageId":"CACsJy8AttNxePUG9cKw9ihAmRd=kFpcsgwe2yj_FRQbhc-akCg@mail.gmail.com","threadId":"34774","inReplyTo":"xmqq8uzndqws.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 00/23] Preliminary pack v4 support","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-08-28T02:30:38Z","receivedAt":"2013-08-28T02:30:38Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Aug 27, 2013 at 11:44 PM, Junio C Hamano wrote:\n> As you have \"0-index\" escape hatch for SHA-1 table, but no similar\n> escape hatch for the people's name table, I can see why it may be\n> cumbersome to fix a thin pack by only appending to a received\n> packfile and updating a few header fields, though.\n\nWe also need an escape hatch for path name table. But what if we store\nappended objects in OBJ_REF_DELTA format where base ref is empty\ntree/commit and cached by sha1_file.c? We won't need to update\ndictionary tables. Parsing is a bit ugly though (e.g. v3 tree with v2\nbase) but we have to deal with that anyway because people can have v2\nand v3 packs mixed in.\n-- \nDuy\n"},{"id":"226077","messageId":"alpine.LFD.2.03.1308272241470.14472@syhkavp.arg","threadId":"34774","inReplyTo":"CACsJy8AttNxePUG9cKw9ihAmRd=kFpcsgwe2yj_FRQbhc-akCg@mail.gmail.com","subject":"Re: [PATCH 00/23] Preliminary pack v4 support","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-08-28T02:58:03Z","receivedAt":"2013-08-28T02:58:03Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 28 Aug 2013, Duy Nguyen wrote:\n\n> On Tue, Aug 27, 2013 at 11:44 PM, Junio C Hamano wrote:\n> > As you have \"0-index\" escape hatch for SHA-1 table, but no similar\n> > escape hatch for the people's name table, I can see why it may be\n> > cumbersome to fix a thin pack by only appending to a received\n> > packfile and updating a few header fields, though.\n> \n> We also need an escape hatch for path name table.\n\nWell, right. I think this is probably the cleanest solution if we don't \nwant to update the commit/tree dictionary table with new entries (they \ncould simply be appended at the end). That wouldn't work for the SHA1 \ntable though, so perhaps a secondary table for the appended objects \ncould then be carried into the pack index file.\n\n> But what if we store\n> appended objects in OBJ_REF_DELTA format where base ref is empty\n> tree/commit and cached by sha1_file.c?\n\nI don't follow you here. Missing objects need to be added to the pack, \nthey can't be cached anywhere.\n\n> We won't need to update\n> dictionary tables. Parsing is a bit ugly though (e.g. v3 tree with v2\n> base) but we have to deal with that anyway because people can have v2\n> and v3 packs mixed in.\n\nAbsolutely.\n\n\nNicolas\n"},{"id":"226078","messageId":"CACsJy8DAeeUrkUw6A28suLq4VoHjt-k3Wd8SLHWcjxr85A0c2g@mail.gmail.com","threadId":"34774","inReplyTo":"alpine.LFD.2.03.1308272241470.14472@syhkavp.arg","subject":"Re: [PATCH 00/23] Preliminary pack v4 support","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-08-28T03:06:49Z","receivedAt":"2013-08-28T03:06:49Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Aug 28, 2013 at 9:58 AM, Nicolas Pitre wrote:\n>> But what if we store\n>> appended objects in OBJ_REF_DELTA format where base ref is empty\n>> tree/commit and cached by sha1_file.c?\n>\n> I don't follow you here. Missing objects need to be added to the pack,\n> they can't be cached anywhere.\n\nI use ref-delta as an alternate escape hatch to store missing commits\nand trees in unparsed format. In order to do that, I need a base ref\nSHA-1 and we can create and store SHA-1 of empty commit and emptry\ntree in sha1_file.c (because empty commit is not in a valid format and\ncan't be parsed and stored in v3). So the result pack is still \"thin\"\nbut it should only lack at most two objects: empty commit and empty\ntree. Thinking again this is much uglier than escape hatches to v3\ntables..\n-- \nDuy\n"},{"id":"226392","messageId":"1377917393-28460-1-git-send-email-pclouds@gmail.com","threadId":"34774","inReplyTo":"1377602225-30439-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2] Document pack v4 format","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-08-31T02:49:53Z","receivedAt":"2013-08-31T02:49:53Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n Incorporated suggestions by Nico and Junio. I went ahead and added\n escape hatches for converting thin packs to full ones so the document\n does not really match the code (I've been watching Nico's repository,\n commit reading is added, good stuff!)\n\n The proposal is, value 0 in the index to ident table is reserved,\n followed by the ident string. The real index to ident table is idx-1.\n\n Similarly, the value 1 in the index to path name table is reserved \n (value 0 is already used for referring back to base tree) so the\n actual index is idx-2.\n\n Documentation/technical/pack-format.txt | 128 +++++++++++++++++++++++++++++++-\n 1 file changed, 127 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/technical/pack-format.txt b/Documentation/technical/pack-format.txt\nindex 8e5bf60..c866287 100644\n--- a/Documentation/technical/pack-format.txt\n+++ b/Documentation/technical/pack-format.txt\n@@ -1,7 +1,7 @@\n Git pack format\n ===============\n \n-== pack-*.pack files have the following format:\n+== pack-*.pack files version 2 and 3 have the following format:\n \n - A header appears at the beginning and consists of the following:\n \n@@ -36,6 +36,127 @@ Git pack format\n \n - The trailer records 20-byte SHA-1 checksum of all of the above.\n \n+== pack-*.pack files version 4 have the following format:\n+\n+ - A header appears at the beginning and consists of the following:\n+\n+ 4-byte signature:\n+\tThe signature is: {'P', 'A', 'C', 'K'}\n+\n+ 4-byte version number (network byte order): must be 4\n+\n+ 4-byte number of objects contained in the pack (network byte order)\n+\n+ - A series of tables, described separately.\n+\n+ - The tables are followed by number of object entries, each of\n+ which looks like below:\n+\n+ (undeltified representation)\n+ n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n+ data\n+\n+ (deltified representation)\n+ n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n+ base object name in SHA-1 reference encoding\n+ compressed delta data\n+\n+ In undeltified format, blobs and tags ares compressed. Trees are\n+ not compressed at all. Some headers in commits are stored\n+ uncompressed, the rest is compressed. Tree and commit\n+ representations are described in detail separately.\n+\n+ Blobs and tags are deltified and compressed the same way in\n+ v3. Commits are not delitifed. Trees are deltified using\n+ undeltified representation.\n+\n+ - The trailer records 20-byte SHA-1 checksum of all of the above.\n+\n+=== Pack v4 tables\n+\n+ - A table of sorted SHA-1 object names for all objects contained in\n+ the pack.\n+\n+ This table can be referred to using \"SHA-1 reference encoding\":\n+ It's an index number in variable length encoding. If it's\n+ non-zero, its value minus one is the index in this table. If it's\n+ zero, 20 bytes of SHA-1 is followed.\n+\n+ - Ident table: the uncompressed length in variable encoding,\n+ followed by zlib-compressed dictionary. Each entry consists of\n+ two prefix bytes storing timezone followed by a NUL-terminated\n+ string.\n+\n+ Entries should be sorted by frequency so that the most frequent\n+ entry has the smallest index, thus most efficient variable\n+ encoding.\n+\n+ The table can be referred to using \"ident reference encoding\":\n+ It's an index number in variable length encoding. If it's\n+ non-zero, its value minus one is the index in this table. If it's\n+ zero, a new entry in the same format is followed: two prefix\n+ bytes and a NUL-terminated string.\n+\n+ - Tree path table: the same format to ident table. Each entry\n+ consists of two prefix bytes storing tree entry mode, then a\n+ NUL-terminated path name. Same sort order recommendation applies.\n+\n+=== Commit representation\n+\n+ - n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n+\n+ - Tree SHA-1 in SHA-1 reference encoding\n+\n+ - Parent count in variable length encoding\n+\n+ - Parent SHA-1s in SHA-1 reference encoding\n+\n+ - Author reference in ident reference encoding\n+\n+ - Author timestamp in variable length encoding\n+\n+ - Committer reference in ident reference encoding\n+\n+ - Committer timestamp in variable length encoding\n+\n+ - Compressed data of remaining header and the body\n+\n+=== Tree representation\n+\n+ - n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n+\n+ - Number of tree entries in variable length encoding\n+\n+ - A number of entries, each starting with path component reference:\n+ an number, in variable length encoding.\n+\n+ If the path component reference is greater than 1, its value minus\n+ two is the index in tree path table. The path component reference\n+ is followed by the tree entry SHA-1 in SHA-1 reference encoding.\n+\n+ If the path component reference is 1, it's followed by\n+\n+ - two prefix bytes representing tree entry mode\n+\n+ - NUL-terminated path name\n+\n+ - tree entry SHA-1 in SHA-1 reference encoding\n+\n+ If the path component reference is zero, tree entries will be\n+ copied from another tree. It's followed by:\n+\n+ - the starting index number, in variable length encoding, in the\n+ base tree object to copy from. Bit zero in this number is base\n+ tree flag, so the actual index is this number shifted right by\n+ one bit.\n+\n+ - number of tree entries to copy from, in variable length encoding\n+\n+ - base tree in SHA-1 reference encoding if base tree flag is\n+ set. If the flag is cleared, the previous base tree encountered\n+ is used. This avoids repeating the same base tree SHA-1 in the\n+ common case.\n+\n == Original (version 1) pack-*.idx files have the following format:\n \n - The header consists of 256 4-byte network byte order\n@@ -160,3 +281,8 @@ Pack file entry: <+\n corresponding packfile.\n \n 20-byte SHA-1-checksum of all of the above.\n+\n+== Version 3 pack-*.idx files support only *.pack files version 4. The\n+ format is the same as version 2 except that the table of sorted\n+ 20-byte SHA-1 object names is missing in the .idx files. The same\n+ table exists in .pack files and will be used instead.\n-- \n1.8.2.83.gc99314b\n"},{"id":"226415","messageId":"CACsJy8CzvQSYRkH+FNuNhzicX9CLC7bRxKgq2RDmOuxh1Q-=5Q@mail.gmail.com","threadId":"34774","inReplyTo":"1377577567-27655-24-git-send-email-nico@fluxnic.net","subject":"Re: [PATCH 23/23] initial pack index v3 support on the read side","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-08-31T11:45:08Z","receivedAt":"2013-08-31T11:45:08Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Aug 27, 2013 at 11:26 AM, Nicolas Pitre wrote:\n> A bit crud but good enough for now.\n\nI wonder if we should keep a short SHA-1 table in .idx. An entry in\nthe original .idx v1 table is + then offset moved out\nto make the table more compact for binary search. I observe that we\ndon't always need 20 byte SHA-1 to uniquely identify an entry in a\npack, so the SHA-1 table could be split in two: one table contain the\nfirst part of SHA-1, long enough to identify any entry in the pack;\nthe second table contains either full SHA-1 or the remaining part.\nBinary search is done on the first table, if matched, full sha-1 from\nthe second table is compared. We already have the second sha-1 table\nin .pack v4. We could add the first table in .idx v3.\n\nOn linux-2.6 even in one-pack configuration, we only need the first 6\nbytes of sha-1 to identify an object. That would cut the bsearch sha-1\ntable to 1/4 full sha-1 table size.\n\n>\n> Signed-off-by: Nicolas Pitre \n> ---\n> cache.h | 1 +\n> sha1_file.c | 58 +++++++++++++++++++++++++++++++++++++++++++++++++++-------\n> 2 files changed, 52 insertions(+), 7 deletions(-)\n>\n> diff --git a/cache.h b/cache.h\n> index b6634c4..63066a1 100644\n> --- a/cache.h\n> +++ b/cache.h\n> @@ -1018,6 +1018,7 @@ extern struct packed_git {\n> off_t pack_size;\n> const void *index_data;\n> size_t index_size;\n> + const unsigned char *sha1_table;\n> uint32_t num_objects;\n> uint32_t num_bad_objects;\n> unsigned char *bad_object_sha1;\n> diff --git a/sha1_file.c b/sha1_file.c\n> index c2020d0..e9c54f4 100644\n> --- a/sha1_file.c\n> +++ b/sha1_file.c\n> @@ -504,7 +504,7 @@ static int check_packed_git_idx(const char *path, struct packed_git *p)\n> hdr = idx_map;\n> if (hdr->idx_signature == htonl(PACK_IDX_SIGNATURE)) {\n> version = ntohl(hdr->idx_version);\n> - if (version < 2 || version > 2) {\n> + if (version < 2 || version > 3) {\n> munmap(idx_map, idx_size);\n> return error(\"index file %s is version %\"PRIu32\n> \" and is not supported by this binary\"\n> @@ -539,12 +539,13 @@ static int check_packed_git_idx(const char *path, struct packed_git *p)\n> munmap(idx_map, idx_size);\n> return error(\"wrong index v1 file size in %s\", path);\n> }\n> - } else if (version == 2) {\n> + } else if (version == 2 || version == 3) {\n> + unsigned long min_size, max_size;\n> /*\n> * Minimum size:\n> * - 8 bytes of header\n> * - 256 index entries 4 bytes each\n> - * - 20-byte sha1 entry * nr\n> + * - 20-byte sha1 entry * nr (version 2 only)\n> * - 4-byte crc entry * nr\n> * - 4-byte offset entry * nr\n> * - 20-byte SHA1 of the packfile\n> @@ -553,8 +554,10 @@ static int check_packed_git_idx(const char *path, struct packed_git *p)\n> * variable sized table containing 8-byte entries\n> * for offsets larger than 2^31.\n> */\n> - unsigned long min_size = 8 + 4*256 + nr*(20 + 4 + 4) + 20 + 20;\n> - unsigned long max_size = min_size;\n> + min_size = 8 + 4*256 + nr*(20 + 4 + 4) + 20 + 20;\n> + if (version != 2)\n> + min_size -= nr*20;\n> + max_size = min_size;\n> if (nr)\n> max_size += (nr - 1)*8;\n> if (idx_size < min_size || idx_size > max_size) {\n> @@ -573,6 +576,36 @@ static int check_packed_git_idx(const char *path, struct packed_git *p)\n> }\n> }\n>\n> + if (version >= 3) {\n> + /* the SHA1 table is located in the main pack file */\n> + void *pack_map;\n> + struct pack_header *pack_hdr;\n> +\n> + fd = git_open_noatime(p->pack_name);\n> + if (fd < 0) {\n> + munmap(idx_map, idx_size);\n> + return error(\"unable to open %s\", p->pack_name);\n> + }\n> + if (fstat(fd, &st) != 0 || xsize_t(st.st_size) < 12 + nr*20) {\n> + close(fd);\n> + munmap(idx_map, idx_size);\n> + return error(\"size of %s is wrong\", p->pack_name);\n> + }\n> + pack_map = xmmap(NULL, 12 + nr*20, PROT_READ, MAP_PRIVATE, fd, 0);\n> + close(fd);\n> + pack_hdr = pack_map;\n> + if (pack_hdr->hdr_signature != htonl(PACK_SIGNATURE) ||\n> + pack_hdr->hdr_version != htonl(4) ||\n> + pack_hdr->hdr_entries != htonl(nr)) {\n> + munmap(idx_map, idx_size);\n> + munmap(pack_map, 12 + nr*20);\n> + return error(\"packfile for %s doesn't match expectations\", path);\n> + }\n> + p->sha1_table = pack_map;\n> + p->sha1_table += 12;\n> + } else\n> + p->sha1_table = NULL;\n> +\n> p->index_version = version;\n> p->index_data = idx_map;\n> p->index_size = idx_size;\n> @@ -697,6 +730,10 @@ void close_pack_index(struct packed_git *p)\n> munmap((void *)p->index_data, p->index_size);\n> p->index_data = NULL;\n> }\n> + if (p->sha1_table) {\n> + munmap((void *)(p->sha1_table - 12), 12 + p->num_objects * 20);\n> + p->sha1_table = NULL;\n> + }\n> }\n>\n> /*\n> @@ -808,7 +845,7 @@ static int open_packed_git_1(struct packed_git *p)\n> return error(\"file %s is far too short to be a packfile\", p->pack_name);\n> if (hdr.hdr_signature != htonl(PACK_SIGNATURE))\n> return error(\"file %s is not a GIT packfile\", p->pack_name);\n> - if (!pack_version_ok(hdr.hdr_version))\n> + if (!pack_version_ok(hdr.hdr_version) && hdr.hdr_version != htonl(4))\n> return error(\"packfile %s is version %\"PRIu32\" and not\"\n> \" supported (try upgrading GIT to a newer version)\",\n> p->pack_name, ntohl(hdr.hdr_version));\n> @@ -2226,9 +2263,12 @@ const unsigned char *nth_packed_object_sha1(struct packed_git *p,\n> index += 4 * 256;\n> if (p->index_version == 1) {\n> return index + 24 * n + 4;\n> - } else {\n> + } else if (p->index_version == 2) {\n> index += 8;\n> return index + 20 * n;\n> + } else {\n> + index = p->sha1_table;\n> + return index + 20 * n;\n> }\n> }\n>\n> @@ -2241,6 +2281,8 @@ off_t nth_packed_object_offset(const struct packed_git *p, uint32_t n)\n> } else {\n> uint32_t off;\n> index += 8 + p->num_objects * (20 + 4);\n> + if (p->index_version != 2)\n> + index -= p->num_objects * 20;\n> off = ntohl(*((uint32_t *)(index + 4 * n)));\n> if (!(off & 0x80000000))\n> return off;\n> @@ -2281,6 +2323,8 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n> stride = 24;\n> index += 4;\n> }\n> + if (p->index_version > 2)\n> + index = p->sha1_table;\n>\n> if (debug_lookup)\n> printf(\"%02x%02x%02x... lo %u hi %u nr %\"PRIu32\"\\n\",\n> --\n> 1.8.4.22.g54757b7\n>\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n\n\n\n-- \nDuy\n"},{"id":"226554","messageId":"CACsJy8CnSyw2ae5BS87S8Hid51JVFB3gyLzX+5czwio+C=-VRQ@mail.gmail.com","threadId":"34774","inReplyTo":"1377577567-27655-10-git-send-email-nico@fluxnic.net","subject":"Re: [PATCH 09/23] pack v4: commit object encoding","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-02T20:48:28Z","receivedAt":"2013-09-02T20:48:28Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Aug 27, 2013 at 11:25 AM, Nicolas Pitre wrote:\n> This goes as follows:\n>\n> - Tree reference: either variable length encoding of the index\n> into the SHA1 table or the literal SHA1 prefixed by 0 (see\n> add_sha1_ref()).\n>\n> - Parent count: variable length encoding of the number of parents.\n> This is normally going to occupy a single byte but doesn't have to.\n>\n> - List of parent references: a list of add_sha1_ref() encoded references,\n> or nothing if the parent count was zero.\n\nWith .pack v3 it's impossible to create delta cycles (3b910d0 add\ntests for indexing packs with delta cycles - 2013-08-23) but it is\npossible with .pack v4 (and therefore at least index-pack needs to\ndetect and reject them), correct? Some malicious user can create\ncommit A with parent ref 1, then make the SHA-1 table so that ref 1 is\nA. The same with the new tree representation.\n-- \nDuy\n"},{"id":"226576","messageId":"alpine.LFD.2.03.1309030156410.14472@syhkavp.arg","threadId":"34774","inReplyTo":"1377917393-28460-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH v2] Document pack v4 format","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-03T06:00:10Z","receivedAt":"2013-09-03T06:00:10Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 31 Aug 2013, Nguyễn Thái Ngọc Duy wrote:\n\n> \n> Signed-off-by: Nguyễn Thái Ngọc Duy \n> ---\n> Incorporated suggestions by Nico and Junio. I went ahead and added\n> escape hatches for converting thin packs to full ones so the document\n> does not really match the code (I've been watching Nico's repository,\n> commit reading is added, good stuff!)\n\nNow tree reading is added. multiple encoding bug fixes trickled down to \ntheir originating commits as well.\n\nSomething is still wrong with deltas though.\n\n\nNicolas\n"},{"id":"226577","messageId":"alpine.LFD.2.03.1309030201230.14472@syhkavp.arg","threadId":"34774","inReplyTo":"CACsJy8CzvQSYRkH+FNuNhzicX9CLC7bRxKgq2RDmOuxh1Q-=5Q@mail.gmail.com","subject":"Re: [PATCH 23/23] initial pack index v3 support on the read side","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-03T06:09:10Z","receivedAt":"2013-09-03T06:09:10Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 31 Aug 2013, Duy Nguyen wrote:\n\n> On Tue, Aug 27, 2013 at 11:26 AM, Nicolas Pitre wrote:\n> > A bit crud but good enough for now.\n> \n> I wonder if we should keep a short SHA-1 table in .idx. An entry in\n> the original .idx v1 table is + then offset moved out\n> to make the table more compact for binary search. I observe that we\n> don't always need 20 byte SHA-1 to uniquely identify an entry in a\n> pack, so the SHA-1 table could be split in two: one table contain the\n> first part of SHA-1, long enough to identify any entry in the pack;\n> the second table contains either full SHA-1 or the remaining part.\n> Binary search is done on the first table, if matched, full sha-1 from\n> the second table is compared. We already have the second sha-1 table\n> in .pack v4. We could add the first table in .idx v3.\n> \n> On linux-2.6 even in one-pack configuration, we only need the first 6\n> bytes of sha-1 to identify an object. That would cut the bsearch sha-1\n> table to 1/4 full sha-1 table size.\n\nI don't see the point though.\n\nWhy having two tables when only one suffice?\n\nIf the argument is about making the SHA1 binary search more efficient \ngiven a smaller memory footprint, that comes with extra complexity \ncoming from the variable length SHA1 strings in the second table. So \nI'm not sure there is much to gain.\n\nFurthermore, one of the design of pack v4 is to avoid the SHA1 binary \nsearch entirely. You will need the binary search only once to locate \nthe top commit object, but from there the entire object tree can be \nwalked simply by using the sha1ref index and looking up the \ncorresponding offset into the pack index file to locate the next object. \n\nSame thing for walking tree objects: the pack v4 tree deltas are meant \nto be walked inline without having to _apply_ any delta.\n\n\nNicolas\n"},{"id":"226578","messageId":"alpine.LFD.2.03.1309030225450.14472@syhkavp.arg","threadId":"34774","inReplyTo":"CACsJy8CnSyw2ae5BS87S8Hid51JVFB3gyLzX+5czwio+C=-VRQ@mail.gmail.com","subject":"Re: [PATCH 09/23] pack v4: commit object encoding","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-03T06:30:48Z","receivedAt":"2013-09-03T06:30:48Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 3 Sep 2013, Duy Nguyen wrote:\n\n> On Tue, Aug 27, 2013 at 11:25 AM, Nicolas Pitre wrote:\n> > This goes as follows:\n> >\n> > - Tree reference: either variable length encoding of the index\n> > into the SHA1 table or the literal SHA1 prefixed by 0 (see\n> > add_sha1_ref()).\n> >\n> > - Parent count: variable length encoding of the number of parents.\n> > This is normally going to occupy a single byte but doesn't have to.\n> >\n> > - List of parent references: a list of add_sha1_ref() encoded references,\n> > or nothing if the parent count was zero.\n> \n> With .pack v3 it's impossible to create delta cycles (3b910d0 add\n> tests for indexing packs with delta cycles - 2013-08-23) but it is\n> possible with .pack v4 (and therefore at least index-pack needs to\n> detect and reject them), correct? Some malicious user can create\n> commit A with parent ref 1, then make the SHA-1 table so that ref 1 is\n> A. The same with the new tree representation.\n\npack-index should validate the SHA1 of the object being pointed at.\n\nIn that case I doubt you'll be able to actually construct an object \nwhich contains a SHA1 parent reference and make the SHA1 of this very \nobject resolve to the same value.\n\n\nNicolas\n"},{"id":"226580","messageId":"alpine.LFD.2.03.1309030231350.14472@syhkavp.arg","threadId":"34774","inReplyTo":"alpine.LFD.2.03.1309030156410.14472@syhkavp.arg","subject":"Re: [PATCH v2] Document pack v4 format","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-03T06:46:44Z","receivedAt":"2013-09-03T06:46:44Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 3 Sep 2013, Nicolas Pitre wrote:\n\n> On Sat, 31 Aug 2013, Nguyễn Thái Ngọc Duy wrote:\n> \n> > \n> > Signed-off-by: Nguyễn Thái Ngọc Duy \n> > ---\n> > Incorporated suggestions by Nico and Junio. I went ahead and added\n> > escape hatches for converting thin packs to full ones so the document\n> > does not really match the code (I've been watching Nico's repository,\n> > commit reading is added, good stuff!)\n> \n> Now tree reading is added. multiple encoding bug fixes trickled down to \n> their originating commits as well.\n> \n> Something is still wrong with deltas though.\n\nDeltas fixed now.\n\nSo... looks like pack v4 is now \"functional\".\n\nHowever something is still wrong as it operates about 6 times slower \nthan pack v3.\n\nAnyone wishes to investigate?\n\n\nNicolas\n"},{"id":"226596","messageId":"CACsJy8D38ZtWdv0wxP9guMw_kTQ-Sm+K83B=nOX0Zb66esKPeQ@mail.gmail.com","threadId":"34774","inReplyTo":"alpine.LFD.2.03.1309030201230.14472@syhkavp.arg","subject":"Re: [PATCH 23/23] initial pack index v3 support on the read side","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-03T07:34:37Z","receivedAt":"2013-09-03T07:34:37Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Sep 3, 2013 at 1:09 PM, Nicolas Pitre wrote:\n> On Sat, 31 Aug 2013, Duy Nguyen wrote:\n>\n>> On Tue, Aug 27, 2013 at 11:26 AM, Nicolas Pitre wrote:\n>> > A bit crud but good enough for now.\n>>\n>> I wonder if we should keep a short SHA-1 table in .idx. An entry in\n>> the original .idx v1 table is + then offset moved out\n>> to make the table more compact for binary search. I observe that we\n>> don't always need 20 byte SHA-1 to uniquely identify an entry in a\n>> pack, so the SHA-1 table could be split in two: one table contain the\n>> first part of SHA-1, long enough to identify any entry in the pack;\n>> the second table contains either full SHA-1 or the remaining part.\n>> Binary search is done on the first table, if matched, full sha-1 from\n>> the second table is compared. We already have the second sha-1 table\n>> in .pack v4. We could add the first table in .idx v3.\n>>\n>> On linux-2.6 even in one-pack configuration, we only need the first 6\n>> bytes of sha-1 to identify an object. That would cut the bsearch sha-1\n>> table to 1/4 full sha-1 table size.\n>\n> I don't see the point though.\n>\n> Why having two tables when only one suffice?\n>\n> If the argument is about making the SHA1 binary search more efficient\n> given a smaller memory footprint, that comes with extra complexity\n> coming from the variable length SHA1 strings in the second table. So\n> I'm not sure there is much to gain.\n>\n> Furthermore, one of the design of pack v4 is to avoid the SHA1 binary\n> search entirely. You will need the binary search only once to locate\n> the top commit object, but from there the entire object tree can be\n> walked simply by using the sha1ref index and looking up the\n> corresponding offset into the pack index file to locate the next object.\n>\n> Same thing for walking tree objects: the pack v4 tree deltas are meant\n> to be walked inline without having to _apply_ any delta.\n\nHmm.. you are right. We avoid a lot of SHA-1 lookups with .pack v4. A\nmore compact SHA-1 table only benefits random SHA-1 lookups, which\nshould be much fewer compared to \"rev-list --objects --all\".\n-- \nDuy\n"},{"id":"226598","messageId":"CACsJy8B0XGAoxYBNoaYt5PP=kA3dfgFpdnMj8DCCX65UeOJ=ug@mail.gmail.com","threadId":"34774","inReplyTo":"alpine.LFD.2.03.1309030225450.14472@syhkavp.arg","subject":"Re: [PATCH 09/23] pack v4: commit object encoding","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-03T07:41:01Z","receivedAt":"2013-09-03T07:41:01Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Sep 3, 2013 at 1:30 PM, Nicolas Pitre wrote:\n> On Tue, 3 Sep 2013, Duy Nguyen wrote:\n>\n>> On Tue, Aug 27, 2013 at 11:25 AM, Nicolas Pitre wrote:\n>> > This goes as follows:\n>> >\n>> > - Tree reference: either variable length encoding of the index\n>> > into the SHA1 table or the literal SHA1 prefixed by 0 (see\n>> > add_sha1_ref()).\n>> >\n>> > - Parent count: variable length encoding of the number of parents.\n>> > This is normally going to occupy a single byte but doesn't have to.\n>> >\n>> > - List of parent references: a list of add_sha1_ref() encoded references,\n>> > or nothing if the parent count was zero.\n>>\n>> With .pack v3 it's impossible to create delta cycles (3b910d0 add\n>> tests for indexing packs with delta cycles - 2013-08-23) but it is\n>> possible with .pack v4 (and therefore at least index-pack needs to\n>> detect and reject them), correct? Some malicious user can create\n>> commit A with parent ref 1, then make the SHA-1 table so that ref 1 is\n>> A. The same with the new tree representation.\n>\n> pack-index should validate the SHA1 of the object being pointed at.\n>\n> In that case I doubt you'll be able to actually construct an object\n> which contains a SHA1 parent reference and make the SHA1 of this very\n> object resolve to the same value.\n\nWe could do that for commits. For trees, we need to look at the base's\ncontent to construct the current tree and cycles could happen. I think\nwe could make a rule that base trees must appear in the pack before\nthe tree being constructed (similar to delta-ofs). The exception is\nobjects appended for fixing thin pack.\n-- \nDuy\n"},{"id":"226612","messageId":"CACsJy8CZP+55nhfEbgRGa9=y0PyExyHt_seiSc23kB31-_c1Hg@mail.gmail.com","threadId":"34774","inReplyTo":"alpine.LFD.2.03.1309030231350.14472@syhkavp.arg","subject":"Re: [PATCH v2] Document pack v4 format","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-03T11:49:02Z","receivedAt":"2013-09-03T11:49:02Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Sep 3, 2013 at 1:46 PM, Nicolas Pitre wrote:\n> So... looks like pack v4 is now \"functional\".\n>\n> However something is still wrong as it operates about 6 times slower\n> than pack v3.\n>\n> Anyone wishes to investigate?\n\nYou recurse in decode_entries too deep.I check the first 10000\ndecode_entries() calls in pv4_get_tree(). The deepest level is 3491.\n-- \nDuy\n"},{"id":"226621","messageId":"CACsJy8CzpW_xsoxU=+OE6ssbnPu9tyAqRten0=Q5cxPUZ4aeMw@mail.gmail.com","threadId":"34774","inReplyTo":"CACsJy8CZP+55nhfEbgRGa9=y0PyExyHt_seiSc23kB31-_c1Hg@mail.gmail.com","subject":"Re: [PATCH v2] Document pack v4 format","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-03T14:54:19Z","receivedAt":"2013-09-03T14:54:19Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Sep 3, 2013 at 6:49 PM, Duy Nguyen wrote:\n> On Tue, Sep 3, 2013 at 1:46 PM, Nicolas Pitre wrote:\n>> So... looks like pack v4 is now \"functional\".\n>>\n>> However something is still wrong as it operates about 6 times slower\n>> than pack v3.\n>>\n>> Anyone wishes to investigate?\n>\n> You recurse in decode_entries too deep.I check the first 10000\n> decode_entries() calls in pv4_get_tree(). The deepest level is 3491.\n\nAnd I was wrong, the call depth is not that deep, but the number of\ndecode_entries calls triggered by one pv4_get_tree() is that many.\nThis is on git.git and the tree being processed is \"t\", which has 672\nentries.. There are funny access patterns. This is the output of\n\n fprintf(stderr, \"[%d] %d - %d %u\\n\", call_depth, copy_start,\ncopy_count, copy_objoffset);\n\n[1] 0 - 1 48838573\n[2] 0 - 1 48826699\n[3] 0 - 1 48820760\n[4] 0 - 1 48814812\n[5] 0 - 1 48805904\n[6] 0 - 1 48797000\n[7] 0 - 1 48794034\n[8] 0 - 1 48791067\n[9] 0 - 1 48788100\n[10] 0 - 1 48785134\n[11] 0 - 1 48776221\n[12] 0 - 1 48764321\n[13] 0 - 1 48503227\n[14] 0 - 1 48485415\n[15] 0 - 1 48473512\n[16] 0 - 1 48443621\n[17] 0 - 1 48401788\n[18] 0 - 1 48377834\n[19] 0 - 1 48371841\n[20] 0 - 1 48341809\n[21] 0 - 1 48260734\n[22] 0 - 1 48236635\n[23] 0 - 1 46845105\n[24] 0 - 1 14603061\n[25] 2 - 1 48838573\n[2] 0 - 1 48826699\n\nIt goes through 20+ base trees just to get one tree entry, I think..\n-- \nDuy\n"},{"id":"226779","messageId":"alpine.LFD.2.03.1309030831540.14472@syhkavp.arg","threadId":"34774","inReplyTo":"CACsJy8B0XGAoxYBNoaYt5PP=kA3dfgFpdnMj8DCCX65UeOJ=ug@mail.gmail.com","subject":"Re: [PATCH 09/23] pack v4: commit object encoding","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-05T03:50:21Z","receivedAt":"2013-09-05T03:50:21Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 3 Sep 2013, Duy Nguyen wrote:\n\n> On Tue, Sep 3, 2013 at 1:30 PM, Nicolas Pitre wrote:\n> > On Tue, 3 Sep 2013, Duy Nguyen wrote:\n> >\n> >> On Tue, Aug 27, 2013 at 11:25 AM, Nicolas Pitre wrote:\n> >> > This goes as follows:\n> >> >\n> >> > - Tree reference: either variable length encoding of the index\n> >> > into the SHA1 table or the literal SHA1 prefixed by 0 (see\n> >> > add_sha1_ref()).\n> >> >\n> >> > - Parent count: variable length encoding of the number of parents.\n> >> > This is normally going to occupy a single byte but doesn't have to.\n> >> >\n> >> > - List of parent references: a list of add_sha1_ref() encoded references,\n> >> > or nothing if the parent count was zero.\n> >>\n> >> With .pack v3 it's impossible to create delta cycles (3b910d0 add\n> >> tests for indexing packs with delta cycles - 2013-08-23) but it is\n> >> possible with .pack v4 (and therefore at least index-pack needs to\n> >> detect and reject them), correct? Some malicious user can create\n> >> commit A with parent ref 1, then make the SHA-1 table so that ref 1 is\n> >> A. The same with the new tree representation.\n> >\n> > pack-index should validate the SHA1 of the object being pointed at.\n> >\n> > In that case I doubt you'll be able to actually construct an object\n> > which contains a SHA1 parent reference and make the SHA1 of this very\n> > object resolve to the same value.\n> \n> We could do that for commits. For trees, we need to look at the base's\n> content to construct the current tree and cycles could happen. I think\n> we could make a rule that base trees must appear in the pack before\n> the tree being constructed (similar to delta-ofs). The exception is\n> objects appended for fixing thin pack.\n\nI don't really like such artificial constraints. You never know when \nsuch constraints are going to prevent future legitimate pack layout \noptimizations or the like.\n\nIt is simple enough to detect cycles during delta validation in \nindex-pack anyway.\n\n\nNicolas\n"},{"id":"226780","messageId":"alpine.LFD.2.03.1309042350560.14472@syhkavp.arg","threadId":"34774","inReplyTo":"CACsJy8CzpW_xsoxU=+OE6ssbnPu9tyAqRten0=Q5cxPUZ4aeMw@mail.gmail.com","subject":"Re: [PATCH v2] Document pack v4 format","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-05T04:12:53Z","receivedAt":"2013-09-05T04:12:53Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 3 Sep 2013, Duy Nguyen wrote:\n\n> On Tue, Sep 3, 2013 at 6:49 PM, Duy Nguyen wrote:\n> > On Tue, Sep 3, 2013 at 1:46 PM, Nicolas Pitre wrote:\n> >> So... looks like pack v4 is now \"functional\".\n> >>\n> >> However something is still wrong as it operates about 6 times slower\n> >> than pack v3.\n> >>\n> >> Anyone wishes to investigate?\n> >\n> > You recurse in decode_entries too deep.I check the first 10000\n> > decode_entries() calls in pv4_get_tree(). The deepest level is 3491.\n> \n> And I was wrong, the call depth is not that deep, but the number of\n> decode_entries calls triggered by one pv4_get_tree() is that many.\n> This is on git.git and the tree being processed is \"t\", which has 672\n> entries.. There are funny access patterns. This is the output of\n> \n> fprintf(stderr, \"[%d] %d - %d %u\\n\", call_depth, copy_start,\n> copy_count, copy_objoffset);\n> \n> [1] 0 - 1 48838573\n> [2] 0 - 1 48826699\n> [3] 0 - 1 48820760\n> [4] 0 - 1 48814812\n> [5] 0 - 1 48805904\n> [6] 0 - 1 48797000\n> [7] 0 - 1 48794034\n> [8] 0 - 1 48791067\n> [9] 0 - 1 48788100\n> [10] 0 - 1 48785134\n> [11] 0 - 1 48776221\n> [12] 0 - 1 48764321\n> [13] 0 - 1 48503227\n> [14] 0 - 1 48485415\n> [15] 0 - 1 48473512\n> [16] 0 - 1 48443621\n> [17] 0 - 1 48401788\n> [18] 0 - 1 48377834\n> [19] 0 - 1 48371841\n> [20] 0 - 1 48341809\n> [21] 0 - 1 48260734\n> [22] 0 - 1 48236635\n> [23] 0 - 1 46845105\n> [24] 0 - 1 14603061\n> [25] 2 - 1 48838573\n> [2] 0 - 1 48826699\n> \n> It goes through 20+ base trees just to get one tree entry, I think..\n\nYeah... that's true. The encoding should refer to the deepest tree \ndirectly in that case. Better delta heuristics will have to be worked \nout here. The code as it is now can't do that.\n\nThere was also a bug that prevented larger copy sequences to be created \nwhich is now fixed.\n\nI added to packv4-create the ability to specify the minimum range of \nconsecutive entries that can be represented by a copy sequence to allow \nexperiments. However, even when the tree deltas are completely disabled \n(using --min-tree-copy=0 achieves that) the CPU usage is still much \nhigher which is rather unexpected. In theory this shouldn't be the \ncase.\n\nMany other bugs have now been fixed. A git.git repository with packs \nversion 4 appears to be functional and passes git-fsck --full --strict.\n\n\nNicolas\n"},{"id":"226781","messageId":"CACsJy8BeU_01c0f5RJExcYo7xGETnduKOw-_shszHd0ZFgZDXw@mail.gmail.com","threadId":"34774","inReplyTo":"alpine.LFD.2.03.1309042350560.14472@syhkavp.arg","subject":"Re: [PATCH v2] Document pack v4 format","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-05T04:19:41Z","receivedAt":"2013-09-05T04:19:41Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Sep 5, 2013 at 11:12 AM, Nicolas Pitre wrote:\n> Many other bugs have now been fixed. A git.git repository with packs\n> version 4 appears to be functional and passes git-fsck --full --strict.\n\nYeah I was looking at the diff some minutes ago, saw changes in\npack-check.c and wondering if fsck was working. I'll add v4 support to\nindex-pack. Waiting to see the new, v4-aware tree walker interface\nwith good \"rev-list --all --objects\" numbers from you.\n-- \nDuy\n"},{"id":"226782","messageId":"alpine.LFD.2.03.1309050024090.14472@syhkavp.arg","threadId":"34774","inReplyTo":"CACsJy8BeU_01c0f5RJExcYo7xGETnduKOw-_shszHd0ZFgZDXw@mail.gmail.com","subject":"Re: [PATCH v2] Document pack v4 format","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-05T04:40:43Z","receivedAt":"2013-09-05T04:40:43Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 5 Sep 2013, Duy Nguyen wrote:\n\n> On Thu, Sep 5, 2013 at 11:12 AM, Nicolas Pitre wrote:\n> > Many other bugs have now been fixed. A git.git repository with packs\n> > version 4 appears to be functional and passes git-fsck --full --strict.\n> \n> Yeah I was looking at the diff some minutes ago, saw changes in\n> pack-check.c and wondering if fsck was working. I'll add v4 support to\n> index-pack.\n\nBeware that the tree delta encoding has changed a little. This saved up \nto 2% on some repos.\n\nI'll probably change the encoding to incorporate the escape hatch \nfor path and name references as discussed previously.\n\n> Waiting to see the new, v4-aware tree walker interface\n> with good \"rev-list --all --objects\" numbers from you.\n\nWell, unfortunately I've put more time than I really had available into \nthis project lately. I'm about to call for other people to take over it \nand pursue this work further.\n\nI really wanted to set the pack format direction since I've been toying \nwith this for so many years. Now the tool to convert a pack is there, \nand the read side is also there, proving that the format does work and \nthe encoding and decoding code is functional and may serve as reference. \nSo that's about the extent of what I can contribute at this point.\n\nI'll be happy to provide design assistance and code review comments of \ncourse. But I won't be able to put the time to do the actual coding \nmyself much longer.\n\n\nNicolas\n"},{"id":"226783","messageId":"CACsJy8CX=4Oz_h2NtS3FRdK6_zdFksa+JR5C6Z-z3Y70PLAsyQ@mail.gmail.com","threadId":"34774","inReplyTo":"alpine.LFD.2.03.1309050024090.14472@syhkavp.arg","subject":"Re: [PATCH v2] Document pack v4 format","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-05T05:04:00Z","receivedAt":"2013-09-05T05:04:00Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Sep 5, 2013 at 11:40 AM, Nicolas Pitre wrote:\n> On Thu, 5 Sep 2013, Duy Nguyen wrote:\n>\n>> On Thu, Sep 5, 2013 at 11:12 AM, Nicolas Pitre wrote:\n>> > Many other bugs have now been fixed. A git.git repository with packs\n>> > version 4 appears to be functional and passes git-fsck --full --strict.\n>>\n>> Yeah I was looking at the diff some minutes ago, saw changes in\n>> pack-check.c and wondering if fsck was working. I'll add v4 support to\n>> index-pack.\n>\n> Beware that the tree delta encoding has changed a little. This saved up\n> to 2% on some repos.\n\nThanks for the heads up.\n\n> I'll probably change the encoding to incorporate the escape hatch\n> for path and name references as discussed previously.\n>\n>> Waiting to see the new, v4-aware tree walker interface\n>> with good \"rev-list --all --objects\" numbers from you.\n>\n> Well, unfortunately I've put more time than I really had available into\n> this project lately. I'm about to call for other people to take over it\n> and pursue this work further.\n>\n> I really wanted to set the pack format direction since I've been toying\n> with this for so many years. Now the tool to convert a pack is there,\n> and the read side is also there, proving that the format does work and\n> the encoding and decoding code is functional and may serve as reference.\n> So that's about the extent of what I can contribute at this point.\n>\n> I'll be happy to provide design assistance and code review comments of\n> course. But I won't be able to put the time to do the actual coding\n> myself much longer.\n\nYou've done a great job in designing v4 and getting basic support in\nplace. I think you'll need to post your series again so Junio can pick\nit up. Then we (at least I) will try to continue from there. I have\nhigh hopes that this will not drop out like the spit-blob series.\n-- \nDuy\n"},{"id":"226784","messageId":"alpine.LFD.2.03.1309050131000.14472@syhkavp.arg","threadId":"34774","inReplyTo":"CACsJy8CX=4Oz_h2NtS3FRdK6_zdFksa+JR5C6Z-z3Y70PLAsyQ@mail.gmail.com","subject":"Re: [PATCH v2] Document pack v4 format","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-05T05:39:31Z","receivedAt":"2013-09-05T05:39:31Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 5 Sep 2013, Duy Nguyen wrote:\n\n> On Thu, Sep 5, 2013 at 11:40 AM, Nicolas Pitre wrote:\n> > On Thu, 5 Sep 2013, Duy Nguyen wrote:\n> >\n> >> On Thu, Sep 5, 2013 at 11:12 AM, Nicolas Pitre wrote:\n> >> > Many other bugs have now been fixed. A git.git repository with packs\n> >> > version 4 appears to be functional and passes git-fsck --full --strict.\n> >>\n> >> Yeah I was looking at the diff some minutes ago, saw changes in\n> >> pack-check.c and wondering if fsck was working. I'll add v4 support to\n> >> index-pack.\n> >\n> > Beware that the tree delta encoding has changed a little. This saved up\n> > to 2% on some repos.\n> \n> Thanks for the heads up.\n> \n> > I'll probably change the encoding to incorporate the escape hatch\n> > for path and name references as discussed previously.\n\nthis is now committed. I don't think there should be any more pack \nformat changes at this point.\n\nNow the pack index v3 probably needs to be improved a little, again to \naccommodate completion of thin packs. Given that the main SHA1 table is \nnow in the main pack file, it should be possible to still carry a small \nSHA1 table in the index file that corresponds to the appended objects \nonly. This means that a SHA1 search will have to first use the main SHA1 \ntable in the pack file as it is done now, and if not found then use the \nSHA1 table in the index file if it exists. And of course \nnth_packed_object_sha1() will have to be adjusted accordingly.\n\n\n\nNicolas\n"},{"id":"226859","messageId":"CACsJy8DKL9KnPAXcf+NPU_Y5J1Dz_pYxSpONN4LxcQVi1JOBYw@mail.gmail.com","threadId":"34774","inReplyTo":"alpine.LFD.2.03.1309050131000.14472@syhkavp.arg","subject":"Re: [PATCH v2] Document pack v4 format","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-05T16:52:22Z","receivedAt":"2013-09-05T16:52:22Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Sep 5, 2013 at 12:39 PM, Nicolas Pitre wrote:\n> Now the pack index v3 probably needs to be improved a little, again to\n> accommodate completion of thin packs. Given that the main SHA1 table is\n> now in the main pack file, it should be possible to still carry a small\n> SHA1 table in the index file that corresponds to the appended objects\n> only. This means that a SHA1 search will have to first use the main SHA1\n> table in the pack file as it is done now, and if not found then use the\n> SHA1 table in the index file if it exists. And of course\n> nth_packed_object_sha1() will have to be adjusted accordingly.\n\nWhat if the sender prepares the sha-1 table to contain missing objects\nin advance? The sender should know what base objects are missing. Then\nwe only need to append objects at the receiving end and verify that\nall new objects are also present in the sha-1 table.\n-- \nDuy\n"},{"id":"226863","messageId":"alpine.LFD.2.03.1309051311070.14472@syhkavp.arg","threadId":"34774","inReplyTo":"CACsJy8DKL9KnPAXcf+NPU_Y5J1Dz_pYxSpONN4LxcQVi1JOBYw@mail.gmail.com","subject":"Re: [PATCH v2] Document pack v4 format","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-05T17:14:11Z","receivedAt":"2013-09-05T17:14:11Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 5 Sep 2013, Duy Nguyen wrote:\n\n> On Thu, Sep 5, 2013 at 12:39 PM, Nicolas Pitre wrote:\n> > Now the pack index v3 probably needs to be improved a little, again to\n> > accommodate completion of thin packs. Given that the main SHA1 table is\n> > now in the main pack file, it should be possible to still carry a small\n> > SHA1 table in the index file that corresponds to the appended objects\n> > only. This means that a SHA1 search will have to first use the main SHA1\n> > table in the pack file as it is done now, and if not found then use the\n> > SHA1 table in the index file if it exists. And of course\n> > nth_packed_object_sha1() will have to be adjusted accordingly.\n> \n> What if the sender prepares the sha-1 table to contain missing objects\n> in advance? The sender should know what base objects are missing. Then\n> we only need to append objects at the receiving end and verify that\n> all new objects are also present in the sha-1 table.\n\nI do like this idea very much. And that doesn't increase the thin pack \nsize as the larger SHA1 table will be compensated by a smaller sha1ref \nencoding in those objects referring to the missing ones.\n\n\n\nNicolas\n"},{"id":"226879","messageId":"xmqq1u53hv6l.fsf@gitster.dls.corp.google.com","threadId":"34774","inReplyTo":"alpine.LFD.2.03.1309051311070.14472@syhkavp.arg","subject":"Re: [PATCH v2] Document pack v4 format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-09-05T20:26:10Z","receivedAt":"2013-09-05T20:26:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> On Thu, 5 Sep 2013, Duy Nguyen wrote:\n>\n>> On Thu, Sep 5, 2013 at 12:39 PM, Nicolas Pitre wrote:\n>> > Now the pack index v3 probably needs to be improved a little, again to\n>> > accommodate completion of thin packs. Given that the main SHA1 table is\n>> > now in the main pack file, it should be possible to still carry a small\n>> > SHA1 table in the index file that corresponds to the appended objects\n>> > only. This means that a SHA1 search will have to first use the main SHA1\n>> > table in the pack file as it is done now, and if not found then use the\n>> > SHA1 table in the index file if it exists. And of course\n>> > nth_packed_object_sha1() will have to be adjusted accordingly.\n>> \n>> What if the sender prepares the sha-1 table to contain missing objects\n>> in advance? The sender should know what base objects are missing. Then\n>> we only need to append objects at the receiving end and verify that\n>> all new objects are also present in the sha-1 table.\n>\n> I do like this idea very much. And that doesn't increase the thin pack \n> size as the larger SHA1 table will be compensated by a smaller sha1ref \n> encoding in those objects referring to the missing ones.\n\nLet me see if I understand the proposal correctly. Compared to a\nnormal pack-v4 stream, a thin pack-v4 stream:\n\n - has all the SHA-1 object names involved in the stream in its main\n object name table---most importantly, names of objects that\n \"thin\" optimization omits from the pack data body are included;\n\n - uses the SHA-1 object name table offset to refer to other\n objects, even to ones that thin stream will not transfer in the\n pack data body;\n\n - is completed at the receiving end by appending the data for the\n objects that were not transferred due to the \"thin\" optimization.\n\nSo the invariant \"all objects contained in the pack\" in:\n\n - A table of sorted SHA-1 object names for all objects contained in\n the pack.\n\nthat appears in Documentation/technical/pack-format.txt is still\nkept at the end, and more importantly, any object that is mentioned\nin this table can be reconstructed by using pack data in the same\npackfile without referencing anything else. Most importantly, if we\nwere to build a v2 .idx file for the resulting .pack, the list of\nobject names in the .idx file would be identical to the object names\nin this table in the .pack file.\n\nIf that is the case, I too like this.\n\nI briefly wondered if it makes sense to mention objects that are\noften referred to that do not exist in the pack in this table\n(e.g. new commits included in this pack refer to a tree object that\nhas not changed for ages---their trees mention this subtree using a\n\"SHA-1 reference encoding\" and being able to name the old,\nunchanging tree with an index to the object table may save space),\nbut that would break the above invariant in a big way---some objects\nmentioned in the table may not exist in the packfile itself---and it\nprobably is not a good idea. Unlike that broken idea, \"include\nnames of the objects that will be appended anyway\" approach to help\nfattening a thin-pack makes very good sense to me.\n"},{"id":"226881","messageId":"alpine.LFD.2.03.1309051655310.14472@syhkavp.arg","threadId":"34774","inReplyTo":"xmqq1u53hv6l.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v2] Document pack v4 format","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-05T21:04:03Z","receivedAt":"2013-09-05T21:04:03Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 5 Sep 2013, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > On Thu, 5 Sep 2013, Duy Nguyen wrote:\n> >\n> >> On Thu, Sep 5, 2013 at 12:39 PM, Nicolas Pitre wrote:\n> >> > Now the pack index v3 probably needs to be improved a little, again to\n> >> > accommodate completion of thin packs. Given that the main SHA1 table is\n> >> > now in the main pack file, it should be possible to still carry a small\n> >> > SHA1 table in the index file that corresponds to the appended objects\n> >> > only. This means that a SHA1 search will have to first use the main SHA1\n> >> > table in the pack file as it is done now, and if not found then use the\n> >> > SHA1 table in the index file if it exists. And of course\n> >> > nth_packed_object_sha1() will have to be adjusted accordingly.\n> >> \n> >> What if the sender prepares the sha-1 table to contain missing objects\n> >> in advance? The sender should know what base objects are missing. Then\n> >> we only need to append objects at the receiving end and verify that\n> >> all new objects are also present in the sha-1 table.\n> >\n> > I do like this idea very much. And that doesn't increase the thin pack \n> > size as the larger SHA1 table will be compensated by a smaller sha1ref \n> > encoding in those objects referring to the missing ones.\n> \n> Let me see if I understand the proposal correctly. Compared to a\n> normal pack-v4 stream, a thin pack-v4 stream:\n> \n> - has all the SHA-1 object names involved in the stream in its main\n> object name table---most importantly, names of objects that\n> \"thin\" optimization omits from the pack data body are included;\n> \n> - uses the SHA-1 object name table offset to refer to other\n> objects, even to ones that thin stream will not transfer in the\n> pack data body;\n> \n> - is completed at the receiving end by appending the data for the\n> objects that were not transferred due to the \"thin\" optimization.\n> \n> So the invariant \"all objects contained in the pack\" in:\n> \n> - A table of sorted SHA-1 object names for all objects contained in\n> the pack.\n> \n> that appears in Documentation/technical/pack-format.txt is still\n> kept at the end, and more importantly, any object that is mentioned\n> in this table can be reconstructed by using pack data in the same\n> packfile without referencing anything else. Most importantly, if we\n> were to build a v2 .idx file for the resulting .pack, the list of\n> object names in the .idx file would be identical to the object names\n> in this table in the .pack file.\n\nThat is right.\n\n> If that is the case, I too like this.\n> \n> I briefly wondered if it makes sense to mention objects that are\n> often referred to that do not exist in the pack in this table\n> (e.g. new commits included in this pack refer to a tree object that\n> has not changed for ages---their trees mention this subtree using a\n> \"SHA-1 reference encoding\" and being able to name the old,\n> unchanging tree with an index to the object table may save space),\n> but that would break the above invariant in a big way---some objects\n> mentioned in the table may not exist in the packfile itself---and it\n> probably is not a good idea.\n\nYet, if an old tree that doesn't change is often referred to, it should \nbe possible to have only one such reference in the whole pack and all \nthe other trees can use a delta copy sequence to refer to it. At this \npoint whether or not the tree being referred to is listed inline or in \nthe SHA1 table doesn't make a big difference.\n\n> Unlike that broken idea, \"include\n> names of the objects that will be appended anyway\" approach to help\n> fattening a thin-pack makes very good sense to me.\n> \n> \n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n> \n"},{"id":"226902","messageId":"1378433643-15638-1-git-send-email-pclouds@gmail.com","threadId":"34774","inReplyTo":"1377917393-28460-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v3] Document pack v4 format","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-06T02:14:03Z","receivedAt":"2013-09-06T02:14:03Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n Should be up to date with Nico's latest implementation and also cover\n additions to the format that everybody seems to agree on:\n\n - new types for canonical trees and commits\n - sha-1 table covering missing objects in thin packs\n\n Documentation/technical/pack-format.txt | 133 +++++++++++++++++++++++++++++++-\n 1 file changed, 132 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/technical/pack-format.txt b/Documentation/technical/pack-format.txt\nindex 8e5bf60..c5327ff 100644\n--- a/Documentation/technical/pack-format.txt\n+++ b/Documentation/technical/pack-format.txt\n@@ -1,7 +1,7 @@\n Git pack format\n ===============\n \n-== pack-*.pack files have the following format:\n+== pack-*.pack files version 2 and 3 have the following format:\n \n - A header appears at the beginning and consists of the following:\n \n@@ -36,6 +36,132 @@ Git pack format\n \n - The trailer records 20-byte SHA-1 checksum of all of the above.\n \n+== pack-*.pack files version 4 have the following format:\n+\n+ - A header appears at the beginning and consists of the following:\n+\n+ 4-byte signature:\n+\tThe signature is: {'P', 'A', 'C', 'K'}\n+\n+ 4-byte version number (network byte order): must be 4\n+\n+ 4-byte number of objects contained in the pack (network byte order)\n+\n+ - A series of tables, described separately.\n+\n+ - The tables are followed by number of object entries, each of\n+ which looks like below:\n+\n+ (undeltified representation)\n+ n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n+ data\n+\n+ (deltified representation)\n+ n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n+ base object name in SHA-1 reference encoding\n+ compressed delta data\n+\n+ \"type\" is used to determine object type. Commit has type 1, tree\n+ 2, blob 3, tag 4, ref-delta 7, canonical-commit 9 (commit type\n+ with bit 3 set), canonical-tree 10 (tree type with bit 3 set).\n+ Compared to v2, ofs-delta type is not used, and canonical-commit\n+ and canonical-tree are new types.\n+\n+ In undeltified format, blobs and tags ares compressed. Trees are\n+ not compressed at all. Some headers in commits are stored\n+ uncompressed, the rest is compressed. Tree and commit\n+ representations are described in detail separately.\n+\n+ Blobs and tags are deltified and compressed the same way in\n+ v3. Commits are not delitifed. Trees are deltified using\n+ undeltified representation.\n+\n+ Trees and commits in canonical types are in the same format as\n+ v2: in canonical format and deflated. They can be used for\n+ completing thin packs or preserving somewhat ill-formatted\n+ objects.\n+\n+ - The trailer records 20-byte SHA-1 checksum of all of the above.\n+\n+=== Pack v4 tables\n+\n+ - A table of sorted SHA-1 object names for all objects contained in\n+ the on-disk pack.\n+\n+ Thin packs are used for transferring on the wire and may omit base\n+ objects, expecting the receiver to add them before writing to\n+ disk. The SHA-1 table in thin packs must include the omitted objects\n+ as well.\n+\n+ This table can be referred to using \"SHA-1 reference encoding\": the\n+ index, in variable length encoding, to this table.\n+\n+ - Ident table: the uncompressed length in variable encoding,\n+ followed by zlib-compressed dictionary. Each entry consists of\n+ two prefix bytes storing timezone followed by a NUL-terminated\n+ string.\n+\n+ Entries should be sorted by frequency so that the most frequent\n+ entry has the smallest index, thus most efficient variable\n+ encoding.\n+\n+ The table can be referred to using \"ident reference encoding\": the\n+ index number, in variable length encoding, to this table.\n+\n+ - Tree path table: the same format to ident table. Each entry\n+ consists of two prefix bytes storing tree entry mode, then a\n+ NUL-terminated path name. Same sort order recommendation applies.\n+\n+=== Commit representation\n+\n+ - n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n+\n+ - Tree SHA-1 in SHA-1 reference encoding\n+\n+ - Parent count in variable length encoding\n+\n+ - Parent SHA-1s in SHA-1 reference encoding\n+\n+ - Author reference in ident reference encoding\n+\n+ - Author timestamp in variable length encoding\n+\n+ - Committer reference in ident reference encoding\n+\n+ - Committer timestamp, encoded as a difference against author\n+ timestamp with the LSB used to indicate negative difference.\n+\n+ - Compressed data of remaining header and the body\n+\n+=== Tree representation\n+\n+ - n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n+\n+ - Number of tree entries in variable length encoding\n+\n+ - A number of entries, each can be in either forms\n+\n+ - INT(path_index << 1) INT(sha1_index)\n+\n+ - INT((entry_start << 1) | 1) INT(entry_count << 1)\n+\n+ - INT((entry_start << 1) | 1) INT((entry_count << 1) | 1) INT(base_sha1_index)\n+\n+ INT() denotes a number in variable length encoding. path_index is\n+ the index to the tree path table. sha1_index is the index to the\n+ SHA-1 table. entry_start is the first tree entry to copy\n+ from. entry_count is the number of tree entries to\n+ copy. base_sha1_index is the index to SHA-1 table of the base tree\n+ to copy from.\n+\n+ The LSB of the first number indicates whether it's a plain tree\n+ entry (LSB not set), or an instruction to copy tree entries from\n+ another tree (LSB set).\n+\n+ For copying from another tree, is the LSB of the second number is\n+ set, it will be followed by a base tree SHA-1. If it's not set,\n+ the last base tree will be used.\n+\n == Original (version 1) pack-*.idx files have the following format:\n \n - The header consists of 256 4-byte network byte order\n@@ -160,3 +286,8 @@ Pack file entry: <+\n corresponding packfile.\n \n 20-byte SHA-1-checksum of all of the above.\n+\n+== Version 3 pack-*.idx files support only *.pack files version 4. The\n+ format is the same as version 2 except that the table of sorted\n+ 20-byte SHA-1 object names is missing in the .idx files. The same\n+ table exists in .pack files and will be used instead.\n-- \n1.8.2.83.gc99314b\n"},{"id":"226905","messageId":"alpine.LFD.2.03.1309052319310.20709@syhkavp.arg","threadId":"34774","inReplyTo":"1378433643-15638-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH v3] Document pack v4 format","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-06T03:23:08Z","receivedAt":"2013-09-06T03:23:08Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 6 Sep 2013, Nguy�n Th�i Ng�c Duy wrote:\n\n> \n> Signed-off-by: Nguy�n Th�i Ng�c Duy \n> ---\n> Should be up to date with Nico's latest implementation and also cover\n> additions to the format that everybody seems to agree on:\n> \n> - new types for canonical trees and commits\n> - sha-1 table covering missing objects in thin packs\n\nGreat! I've merged this into my branch with the following amendment:\n\ndiff --git a/Documentation/technical/pack-format.txt b/Documentation/technical/pack-format.txt\nindex 1980794..d0c2cde 100644\n--- a/Documentation/technical/pack-format.txt\n+++ b/Documentation/technical/pack-format.txt\n@@ -81,6 +81,13 @@ Git pack format\n completing thin packs or preserving somewhat ill-formatted\n objects.\n \n+ Thin packs are used for transferring on the wire and may omit delta\n+ base objects, expecting the receiver to add them at the end of the pack\n+ before writing to disk. The number of objects contained in the pack\n+ header must account for those omitted objects in any case. To indicate\n+ no more objects are included in a thin pack, a \"type 0\" byte\n+ indicator is inserted after the last transmitted object.\n+\n - The trailer records 20-byte SHA-1 checksum of all of the above.\n \n === Pack v4 tables\n@@ -88,10 +95,7 @@ Git pack format\n - A table of sorted SHA-1 object names for all objects contained in\n the on-disk pack.\n \n- Thin packs are used for transferring on the wire and may omit base\n- objects, expecting the receiver to add them before writing to\n- disk. The SHA-1 table in thin packs must include the omitted objects\n- as well.\n+ The SHA-1 table in thin packs must include the omitted objects as well.\n \n This table can be referred to using \"SHA-1 reference encoding\": the\n index, in variable length encoding, to this table.\n@@ -158,7 +162,7 @@ Git pack format\n entry (LSB not set), or an instruction to copy tree entries from\n another tree (LSB set).\n \n- For copying from another tree, is the LSB of the second number is\n+ For copying from another tree, if the LSB of the second number is\n set, it will be followed by a base tree SHA-1. If it's not set,\n the last base tree will be used.\n \n\n> diff --git a/Documentation/technical/pack-format.txt b/Documentation/technical/pack-format.txt\n> index 8e5bf60..c5327ff 100644\n> --- a/Documentation/technical/pack-format.txt\n> +++ b/Documentation/technical/pack-format.txt\n> @@ -1,7 +1,7 @@\n> Git pack format\n> ===============\n> \n> -== pack-*.pack files have the following format:\n> +== pack-*.pack files version 2 and 3 have the following format:\n> \n> - A header appears at the beginning and consists of the following:\n> \n> @@ -36,6 +36,132 @@ Git pack format\n> \n> - The trailer records 20-byte SHA-1 checksum of all of the above.\n> \n> +== pack-*.pack files version 4 have the following format:\n> +\n> + - A header appears at the beginning and consists of the following:\n> +\n> + 4-byte signature:\n> +\tThe signature is: {'P', 'A', 'C', 'K'}\n> +\n> + 4-byte version number (network byte order): must be 4\n> +\n> + 4-byte number of objects contained in the pack (network byte order)\n> +\n> + - A series of tables, described separately.\n> +\n> + - The tables are followed by number of object entries, each of\n> + which looks like below:\n> +\n> + (undeltified representation)\n> + n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n> + data\n> +\n> + (deltified representation)\n> + n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n> + base object name in SHA-1 reference encoding\n> + compressed delta data\n> +\n> + \"type\" is used to determine object type. Commit has type 1, tree\n> + 2, blob 3, tag 4, ref-delta 7, canonical-commit 9 (commit type\n> + with bit 3 set), canonical-tree 10 (tree type with bit 3 set).\n> + Compared to v2, ofs-delta type is not used, and canonical-commit\n> + and canonical-tree are new types.\n> +\n> + In undeltified format, blobs and tags ares compressed. Trees are\n> + not compressed at all. Some headers in commits are stored\n> + uncompressed, the rest is compressed. Tree and commit\n> + representations are described in detail separately.\n> +\n> + Blobs and tags are deltified and compressed the same way in\n> + v3. Commits are not delitifed. Trees are deltified using\n> + undeltified representation.\n> +\n> + Trees and commits in canonical types are in the same format as\n> + v2: in canonical format and deflated. They can be used for\n> + completing thin packs or preserving somewhat ill-formatted\n> + objects.\n> +\n> + - The trailer records 20-byte SHA-1 checksum of all of the above.\n> +\n> +=== Pack v4 tables\n> +\n> + - A table of sorted SHA-1 object names for all objects contained in\n> + the on-disk pack.\n> +\n> + Thin packs are used for transferring on the wire and may omit base\n> + objects, expecting the receiver to add them before writing to\n> + disk. The SHA-1 table in thin packs must include the omitted objects\n> + as well.\n> +\n> + This table can be referred to using \"SHA-1 reference encoding\": the\n> + index, in variable length encoding, to this table.\n> +\n> + - Ident table: the uncompressed length in variable encoding,\n> + followed by zlib-compressed dictionary. Each entry consists of\n> + two prefix bytes storing timezone followed by a NUL-terminated\n> + string.\n> +\n> + Entries should be sorted by frequency so that the most frequent\n> + entry has the smallest index, thus most efficient variable\n> + encoding.\n> +\n> + The table can be referred to using \"ident reference encoding\": the\n> + index number, in variable length encoding, to this table.\n> +\n> + - Tree path table: the same format to ident table. Each entry\n> + consists of two prefix bytes storing tree entry mode, then a\n> + NUL-terminated path name. Same sort order recommendation applies.\n> +\n> +=== Commit representation\n> +\n> + - n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n> +\n> + - Tree SHA-1 in SHA-1 reference encoding\n> +\n> + - Parent count in variable length encoding\n> +\n> + - Parent SHA-1s in SHA-1 reference encoding\n> +\n> + - Author reference in ident reference encoding\n> +\n> + - Author timestamp in variable length encoding\n> +\n> + - Committer reference in ident reference encoding\n> +\n> + - Committer timestamp, encoded as a difference against author\n> + timestamp with the LSB used to indicate negative difference.\n> +\n> + - Compressed data of remaining header and the body\n> +\n> +=== Tree representation\n> +\n> + - n-byte type and length (4-bit type, (n-1)*7+4-bit length)\n> +\n> + - Number of tree entries in variable length encoding\n> +\n> + - A number of entries, each can be in either forms\n> +\n> + - INT(path_index << 1) INT(sha1_index)\n> +\n> + - INT((entry_start << 1) | 1) INT(entry_count << 1)\n> +\n> + - INT((entry_start << 1) | 1) INT((entry_count << 1) | 1) INT(base_sha1_index)\n> +\n> + INT() denotes a number in variable length encoding. path_index is\n> + the index to the tree path table. sha1_index is the index to the\n> + SHA-1 table. entry_start is the first tree entry to copy\n> + from. entry_count is the number of tree entries to\n> + copy. base_sha1_index is the index to SHA-1 table of the base tree\n> + to copy from.\n> +\n> + The LSB of the first number indicates whether it's a plain tree\n> + entry (LSB not set), or an instruction to copy tree entries from\n> + another tree (LSB set).\n> +\n> + For copying from another tree, is the LSB of the second number is\n> + set, it will be followed by a base tree SHA-1. If it's not set,\n> + the last base tree will be used.\n> +\n> == Original (version 1) pack-*.idx files have the following format:\n> \n> - The header consists of 256 4-byte network byte order\n> @@ -160,3 +286,8 @@ Pack file entry: <+\n> corresponding packfile.\n> \n> 20-byte SHA-1-checksum of all of the above.\n> +\n> +== Version 3 pack-*.idx files support only *.pack files version 4. The\n> + format is the same as version 2 except that the table of sorted\n> + 20-byte SHA-1 object names is missing in the .idx files. The same\n> + table exists in .pack files and will be used instead.\n> -- \n> 1.8.2.83.gc99314b\n> \n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n> \n"},{"id":"226907","messageId":"CACsJy8BbxKfX_Ho8Nu2fvTp1xWYcaGPgwf6=iq0bZ4KSE+r6bw@mail.gmail.com","threadId":"34774","inReplyTo":"CACsJy8DKL9KnPAXcf+NPU_Y5J1Dz_pYxSpONN4LxcQVi1JOBYw@mail.gmail.com","subject":"Re: [PATCH v2] Document pack v4 format","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-06T04:18:34Z","receivedAt":"2013-09-06T04:18:34Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Sep 5, 2013 at 11:52 PM, Duy Nguyen wrote:\n> On Thu, Sep 5, 2013 at 12:39 PM, Nicolas Pitre wrote:\n>> Now the pack index v3 probably needs to be improved a little, again to\n>> accommodate completion of thin packs. Given that the main SHA1 table is\n>> now in the main pack file, it should be possible to still carry a small\n>> SHA1 table in the index file that corresponds to the appended objects\n>> only. This means that a SHA1 search will have to first use the main SHA1\n>> table in the pack file as it is done now, and if not found then use the\n>> SHA1 table in the index file if it exists. And of course\n>> nth_packed_object_sha1() will have to be adjusted accordingly.\n>\n> What if the sender prepares the sha-1 table to contain missing objects\n> in advance? The sender should know what base objects are missing. Then\n> we only need to append objects at the receiving end and verify that\n> all new objects are also present in the sha-1 table.\n\nOne minor detail to sort out: the size of sha-1 table. Previously it's\nthe number of objects in the pack. Now it's not true because the table\nmay have more entries. So how should we record the table size? We\ncould use null sha-1 as the end of table marker. Or we could make\npack-objects to write nr_objects as the number of entries _after_ pack\ncompletion, not the true number of objects in thin pack. I like the\nlatter (no more rehashing the entire pack after completion) but then\nwe need a cue to know that we have reached the end of the pack..\n-- \nDuy\n"},{"id":"226921","messageId":"CACsJy8AWa0NFViO+3Cnp_0Gqzqidcbx9vPd1wxCuY1jjWhyFaQ@mail.gmail.com","threadId":"34774","inReplyTo":"alpine.LFD.2.03.1309052319310.20709@syhkavp.arg","subject":"Re: [PATCH v3] Document pack v4 format","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-06T09:48:44Z","receivedAt":"2013-09-06T09:48:44Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Sep 6, 2013 at 10:23 AM, Nicolas Pitre wrote:\n> On Fri, 6 Sep 2013, Nguy­n Thái Ng÷c Duy wrote:\n>\n>>\n>> Signed-off-by: Nguy­n Thái Ng÷c Duy \n>> ---\n>> Should be up to date with Nico's latest implementation and also cover\n>> additions to the format that everybody seems to agree on:\n>>\n>> - new types for canonical trees and commits\n>> - sha-1 table covering missing objects in thin packs\n>\n> Great! I've merged this into my branch with the following amendment:\n\nI'd like to propose another change in the format to basically limit\nthe use of sha1ref format \"\\0\" to tree entries only. All forms\nof deltas must have non-zero sha1 index (i.e. reference to SHA-1\ntable). It will simplify handling code, and I think it makes sense too\n\ndiff --git a/Documentation/technical/pack-format.txt\nb/Documentation/technical/pack-format.txt\nindex d0c2cde..399416b 100644\n--- a/Documentation/technical/pack-format.txt\n+++ b/Documentation/technical/pack-format.txt\n@@ -74,7 +74,8 @@ Git pack format\n\n Blobs and tags are deltified and compressed the same way in\n v3. Commits are not deltified. Trees are deltified using\n- special copy sequences.\n+ special copy sequences. The base object name index in deltified\n+ format must not be zero (i.e. it must point to SHA-1 table).\n\n Trees and commits in canonical types are in the same format as\n v2: in canonical format and deflated. They can be used for\n@@ -166,6 +167,8 @@ Git pack format\n set, it will be followed by a base tree SHA-1. If it's not set,\n the last base tree will be used.\n\n+ base_sha1_index cannot be zero and followed by full SHA-1.\n+\n == Original (version 1) pack-*.idx files have the following format:\n\n - The header consists of 256 4-byte network byte order\n-- \nDuy\n"},{"id":"226937","messageId":"alpine.LFD.2.03.1309060916400.20709@syhkavp.arg","threadId":"34774","inReplyTo":"CACsJy8BbxKfX_Ho8Nu2fvTp1xWYcaGPgwf6=iq0bZ4KSE+r6bw@mail.gmail.com","subject":"Re: [PATCH v2] Document pack v4 format","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-06T13:19:11Z","receivedAt":"2013-09-06T13:19:11Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 6 Sep 2013, Duy Nguyen wrote:\n\n> On Thu, Sep 5, 2013 at 11:52 PM, Duy Nguyen wrote:\n> > On Thu, Sep 5, 2013 at 12:39 PM, Nicolas Pitre wrote:\n> >> Now the pack index v3 probably needs to be improved a little, again to\n> >> accommodate completion of thin packs. Given that the main SHA1 table is\n> >> now in the main pack file, it should be possible to still carry a small\n> >> SHA1 table in the index file that corresponds to the appended objects\n> >> only. This means that a SHA1 search will have to first use the main SHA1\n> >> table in the pack file as it is done now, and if not found then use the\n> >> SHA1 table in the index file if it exists. And of course\n> >> nth_packed_object_sha1() will have to be adjusted accordingly.\n> >\n> > What if the sender prepares the sha-1 table to contain missing objects\n> > in advance? The sender should know what base objects are missing. Then\n> > we only need to append objects at the receiving end and verify that\n> > all new objects are also present in the sha-1 table.\n> \n> One minor detail to sort out: the size of sha-1 table. Previously it's\n> the number of objects in the pack. Now it's not true because the table\n> may have more entries. So how should we record the table size? We\n> could use null sha-1 as the end of table marker. Or we could make\n> pack-objects to write nr_objects as the number of entries _after_ pack\n> completion, not the true number of objects in thin pack. I like the\n> latter (no more rehashing the entire pack after completion) but then\n> we need a cue to know that we have reached the end of the pack..\n\nSee the amendment I made to your documentation patch. I opted for the \nlater. To mark the end of the transmitted objects a zero byte (object \ntype 0) is used.\n\n\nNicolas\n"},{"id":"226939","messageId":"alpine.LFD.2.03.1309060922020.20709@syhkavp.arg","threadId":"34774","inReplyTo":"CACsJy8AWa0NFViO+3Cnp_0Gqzqidcbx9vPd1wxCuY1jjWhyFaQ@mail.gmail.com","subject":"Re: [PATCH v3] Document pack v4 format","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-06T13:25:45Z","receivedAt":"2013-09-06T13:25:45Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 6 Sep 2013, Duy Nguyen wrote:\n\n> On Fri, Sep 6, 2013 at 10:23 AM, Nicolas Pitre wrote:\n> > On Fri, 6 Sep 2013, Nguy­n Thái Ng÷c Duy wrote:\n> >\n> >>\n> >> Signed-off-by: Nguy­n Thái Ng÷c Duy \n> >> ---\n> >> Should be up to date with Nico's latest implementation and also cover\n> >> additions to the format that everybody seems to agree on:\n> >>\n> >> - new types for canonical trees and commits\n> >> - sha-1 table covering missing objects in thin packs\n> >\n> > Great! I've merged this into my branch with the following amendment:\n> \n> I'd like to propose another change in the format to basically limit\n> the use of sha1ref format \"\\0\" to tree entries only. All forms\n> of deltas must have non-zero sha1 index (i.e. reference to SHA-1\n> table). It will simplify handling code, and I think it makes sense too\n\nWhy?\n\nThis is still some artificial limitation and I tend not to like them.\n\n\"Simplifying handling code\" is not a good enough reason on its own, \nespecially if it reduce flexibility for possible future layout \noptimizations.\n\nIn what way is the code more difficult?\n\n\nNicolas\n"},{"id":"226940","messageId":"CACsJy8CVaFKZE2bM+1AZPTpq19BS8-=UrYCcvO004Aw_EX-vfg@mail.gmail.com","threadId":"34774","inReplyTo":"alpine.LFD.2.03.1309060922020.20709@syhkavp.arg","subject":"Re: [PATCH v3] Document pack v4 format","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-06T13:44:11Z","receivedAt":"2013-09-06T13:44:11Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Sep 6, 2013 at 8:25 PM, Nicolas Pitre wrote:\n> On Fri, 6 Sep 2013, Duy Nguyen wrote:\n>\n>> On Fri, Sep 6, 2013 at 10:23 AM, Nicolas Pitre wrote:\n>> > On Fri, 6 Sep 2013, Nguy­n Thái Ng÷c Duy wrote:\n>> >\n>> >>\n>> >> Signed-off-by: Nguy­n Thái Ng÷c Duy \n>> >> ---\n>> >> Should be up to date with Nico's latest implementation and also cover\n>> >> additions to the format that everybody seems to agree on:\n>> >>\n>> >> - new types for canonical trees and commits\n>> >> - sha-1 table covering missing objects in thin packs\n>> >\n>> > Great! I've merged this into my branch with the following amendment:\n>>\n>> I'd like to propose another change in the format to basically limit\n>> the use of sha1ref format \"\\0\" to tree entries only. All forms\n>> of deltas must have non-zero sha1 index (i.e. reference to SHA-1\n>> table). It will simplify handling code, and I think it makes sense too\n>\n> Why?\n>\n> This is still some artificial limitation and I tend not to like them.\n>\n> \"Simplifying handling code\" is not a good enough reason on its own,\n> especially if it reduce flexibility for possible future layout\n> optimizations.\n>\n> In what way is the code more difficult?\n\nThat'll be two ways of linking to another in-pack object. The linked\nobject must be in the pack anyway, its sha-1 should be present in the\nsha-1 table. \"\\0\" is a longer encoding for nothing. If the\nlinked sha1 is not in the pack (similar to the old ref-delta), it\nmakes the pack depend on another one, which is what we've been\navoding. In your code you reject sha1ref starting with zero too\n(sha1_file.c::get_base_delta and packv4-parse.c::decode_entries)\n-- \nDuy\n"},{"id":"226951","messageId":"alpine.LFD.2.03.1309061224350.20709@syhkavp.arg","threadId":"34774","inReplyTo":"CACsJy8CVaFKZE2bM+1AZPTpq19BS8-=UrYCcvO004Aw_EX-vfg@mail.gmail.com","subject":"Re: [PATCH v3] Document pack v4 format","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-06T16:44:11Z","receivedAt":"2013-09-06T16:44:11Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 6 Sep 2013, Duy Nguyen wrote:\n\n> On Fri, Sep 6, 2013 at 8:25 PM, Nicolas Pitre wrote:\n> > On Fri, 6 Sep 2013, Duy Nguyen wrote:\n> >\n> >> On Fri, Sep 6, 2013 at 10:23 AM, Nicolas Pitre wrote:\n> >> > On Fri, 6 Sep 2013, Nguy­n Thái Ng÷c Duy wrote:\n> >> >\n> >> >>\n> >> >> Signed-off-by: Nguy­n Thái Ng÷c Duy \n> >> >> ---\n> >> >> Should be up to date with Nico's latest implementation and also cover\n> >> >> additions to the format that everybody seems to agree on:\n> >> >>\n> >> >> - new types for canonical trees and commits\n> >> >> - sha-1 table covering missing objects in thin packs\n> >> >\n> >> > Great! I've merged this into my branch with the following amendment:\n> >>\n> >> I'd like to propose another change in the format to basically limit\n> >> the use of sha1ref format \"\\0\" to tree entries only. All forms\n> >> of deltas must have non-zero sha1 index (i.e. reference to SHA-1\n> >> table). It will simplify handling code, and I think it makes sense too\n> >\n> > Why?\n> >\n> > This is still some artificial limitation and I tend not to like them.\n> >\n> > \"Simplifying handling code\" is not a good enough reason on its own,\n> > especially if it reduce flexibility for possible future layout\n> > optimizations.\n> >\n> > In what way is the code more difficult?\n> \n> That'll be two ways of linking to another in-pack object. The linked\n> object must be in the pack anyway, its sha-1 should be present in the\n> sha-1 table. \"\\0\" is a longer encoding for nothing. If the\n> linked sha1 is not in the pack (similar to the old ref-delta), it\n> makes the pack depend on another one, which is what we've been\n> avoding.\n\nOK. Let's say that if the needed SHA1 exists in the table then the \nsha1ref should use an index into that table. That's a recommendation we \ncan make, just like we suggest to have the ident/path tables sorted by \nusage frequency.\n\nBut even if index 0 with a SHA1 is used inline for an object in the same \npack, it is still theoretically a valid pack even if somewhat wasteful. \nMaybe some tools in the future will benefit from this flexibility to \nsimplify their implementation.\n\nYou mention that only tree objects should use this encoding, but commits \nshould be allowed to use it as well. Suppose that a commit reverts some \nchanges to a pre-existing tree state. That tree might already be in \nanother pack and we shouldn't have to copy it into the current pack. \nSame goes for commit parents. Etc.\n\n> In your code you reject sha1ref starting with zero too\n> (sha1_file.c::get_base_delta and packv4-parse.c::decode_entries)\n\nYeah... because I wrote the minimum code to make it work with the \ncurrent encoder. But the decoder could be more lenient than that. It's \njust a matter of adding a call to find_pack_entry_one() when the sha1ref \nindex is 0.\n\n\nNicolas\n"},{"id":"227002","messageId":"alpine.LFD.2.03.1309070043420.20709@syhkavp.arg","threadId":"34774","inReplyTo":"1378433643-15638-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH v3] Document pack v4 format","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-07T04:52:10Z","receivedAt":"2013-09-07T04:52:10Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 6 Sep 2013, Nguyễn Thái Ngọc Duy wrote:\n\n> \n> Signed-off-by: Nguyễn Thái Ngọc Duy \n> ---\n> Should be up to date with Nico's latest implementation and also cover\n> additions to the format that everybody seems to agree on:\n> \n> - new types for canonical trees and commits\n> - sha-1 table covering missing objects in thin packs\n\nYes, I've tweaked the format again. I've implemented the code needed to \ncarry canonical commit and tree objects in pack v4. And things are much \nsimpler if the canonical commit and tree types are identical to pack v2. \nTherefore the new types are used for the pack v4 optimized commit and \ntree representations.\n\nI've therefore added this patch to my tree (with the needed changes to \nthe documentation patch):\n\ncommit 98d4b75aff266015b5dff0a324a2984c2a8f7fa2\nAuthor: Nicolas Pitre \nDate: Fri Sep 6 23:45:49 2013 -0400\n\n pack v4: allow canonical commit and tree objects\n \n If for some reason we can't transcode a commit or tree object (lossy\n encoding such as the zero-padded file mode for example) then we can still\n store the canonical object like in pack v2.\n \n This is also useful for completing a thin pack without having to add\n missing entries to the dictionary tables.\n \n To simplify things, the canonical commit and tree types retain their type\n number 1 and 2 respectively, and the transcoded types are now 9 and 10\n i.e. with bit 3 added.\n \n Signed-off-by: Nicolas Pitre \n\ndiff --git a/cache.h b/cache.h\nindex a6d016b..b68ad5a 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -330,6 +330,8 @@ enum object_type {\n \t/* 5 for future expansion */\n \tOBJ_OFS_DELTA = 6,\n \tOBJ_REF_DELTA = 7,\n+\tOBJ_PV4_COMMIT = (8 + 1),\n+\tOBJ_PV4_TREE = (8 + 2),\n \tOBJ_ANY,\n \tOBJ_MAX\n };\ndiff --git a/packv4-create.c b/packv4-create.c\nindex 11cfe6f..38fa594 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -981,10 +981,15 @@ static off_t packv4_write_object(struct sha1file *f, struct packed_git *p,\n \t\tdie(\"unexpected object type %d\", type);\n \t}\n \tfree(src);\n-\tif (!result)\n-\t\tdie(\"can't convert %s object %s\",\n-\t\t typename(type), sha1_to_hex(obj->sha1));\n+\tif (!result) {\n+\t\twarning(\"can't convert %s object %s\",\n+\t\t\ttypename(type), sha1_to_hex(obj->sha1));\n+\t\t/* fall back to copy the object in its original form */\n+\t\treturn copy_object_data(f, p, obj->offset);\n+\t}\n \n+\t/* Use bit 3 to indicate a special type encoding */\n+\ttype += 8;\n \thdrlen = write_object_header(f, type, obj_size);\n \tsha1write(f, result, buf_size);\n \tfree(result);\ndiff --git a/packv4-parse.c b/packv4-parse.c\nindex 86ec535..63bba03 100644\n--- a/packv4-parse.c\n+++ b/packv4-parse.c\n@@ -266,7 +266,7 @@ static int decode_entries(struct packed_git *p, struct pack_window **w_curs,\n \t\t\tif (++scp - src >= avail - 20)\n \t\t\t\treturn -1;\n \t\t/* let's still make sure this is actually a tree */\n-\t\tif ((*scp++ & 0xf) != OBJ_TREE)\n+\t\tif ((*scp++ & 0xf) != OBJ_PV4_TREE)\n \t\t\treturn -1;\n \t}\n \ndiff --git a/sha1_file.c b/sha1_file.c\nindex 79e1293..c7bf677 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1806,6 +1806,11 @@ static enum object_type packed_to_object_type(struct packed_git *p,\n \t}\n \n \tswitch (type) {\n+\tcase OBJ_PV4_COMMIT:\n+\tcase OBJ_PV4_TREE:\n+\t\t/* hide pack v4 special object types */\n+\t\ttype -= 8;\n+\t\tbreak;\n \tcase OBJ_BAD:\n \tcase OBJ_COMMIT:\n \tcase OBJ_TREE:\n@@ -2171,17 +2176,16 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n \t\tif (data)\n \t\t\tdie(\"BUG in unpack_entry: left loop at a valid delta\");\n \t\tbreak;\n+\tcase OBJ_PV4_COMMIT:\n+\t\tdata = pv4_get_commit(p, &w_curs, curpos, size);\n+\t\ttype -= 8;\n+\t\tbreak;\n+\tcase OBJ_PV4_TREE:\n+\t\tdata = pv4_get_tree(p, &w_curs, curpos, size);\n+\t\ttype -= 8;\n+\t\tbreak;\n \tcase OBJ_COMMIT:\n \tcase OBJ_TREE:\n-\t\tif (p->version >= 4 && !base_from_cache) {\n-\t\t\tif (type == OBJ_COMMIT) {\n-\t\t\t\tdata = pv4_get_commit(p, &w_curs, curpos, size);\n-\t\t\t} else {\n-\t\t\t\tdata = pv4_get_tree(p, &w_curs, curpos, size);\n-\t\t\t}\n-\t\t\tbreak;\n-\t\t}\n-\t\t/* fall through */\n \tcase OBJ_BLOB:\n \tcase OBJ_TAG:\n \t\tif (!base_from_cache)\n\n"},{"id":"227003","messageId":"alpine.LFD.2.03.1309070054320.20709@syhkavp.arg","threadId":"34774","inReplyTo":"alpine.LFD.2.03.1309061224350.20709@syhkavp.arg","subject":"Re: [PATCH v3] Document pack v4 format","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-07T04:57:03Z","receivedAt":"2013-09-07T04:57:03Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 6 Sep 2013, Nicolas Pitre wrote:\n\n> On Fri, 6 Sep 2013, Duy Nguyen wrote:\n> \n> > In your code you reject sha1ref starting with zero too\n> > (sha1_file.c::get_base_delta and packv4-parse.c::decode_entries)\n> \n> Yeah... because I wrote the minimum code to make it work with the \n> current encoder. But the decoder could be more lenient than that. It's \n> just a matter of adding a call to find_pack_entry_one() when the sha1ref \n> index is 0.\n\nFYI I've added the missing code to packv4-parse.c::decode_entries.\nThe code in sha1_file.c::get_delta_base was already fine.\n\n\nNicolas\n"},{"id":"227004","messageId":"CACsJy8B_61-FPqhN-qsavgznpq2vWj47=dAQjHwSuNX_kx5+0Q@mail.gmail.com","threadId":"34774","inReplyTo":"alpine.LFD.2.03.1309070043420.20709@syhkavp.arg","subject":"Re: [PATCH v3] Document pack v4 format","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-07T08:05:05Z","receivedAt":"2013-09-07T08:05:05Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Sep 7, 2013 at 11:52 AM, Nicolas Pitre wrote:\n> On Fri, 6 Sep 2013, Nguyễn Thái Ngọc Duy wrote:\n>\n>>\n>> Signed-off-by: Nguyễn Thái Ngọc Duy \n>> ---\n>> Should be up to date with Nico's latest implementation and also cover\n>> additions to the format that everybody seems to agree on:\n>>\n>> - new types for canonical trees and commits\n>> - sha-1 table covering missing objects in thin packs\n>\n> Yes, I've tweaked the format again. I've implemented the code needed to\n> carry canonical commit and tree objects in pack v4. And things are much\n> simpler if the canonical commit and tree types are identical to pack v2.\n> Therefore the new types are used for the pack v4 optimized commit and\n> tree representations.\n\nPhew, index-pack finally produces .idx identical to packv4-create\noutput. Yeah using new types for v4 tree and commit should help. I\nhave a lot of \"if (packv4 && type == OBJ_TREE)\" tests, now they become\n\"if (type == OBJ_PV4_TREE)\". Now rebasing on your tree.. Next step:\nthin pack support in index-pack, then export/move code in\npackv4-create to support v4 in pack-objects.\n-- \nDuy\n"}]}