{"thread":{"id":"39107","subject":"[PATCH 0/2] nd/slim-index-pack-memory-usage update","startedAt":"2015-04-18T10:47:03Z","lastAt":"2015-07-08T14:11:11Z","messageCount":17,"participants":["Nguyễn Thái Ngọc Duy","Junio C Hamano","Duy Nguyen","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"259620","messageId":"1429354025-24659-1-git-send-email-pclouds@gmail.com","threadId":"39107","inReplyTo":null,"subject":"[PATCH 0/2] nd/slim-index-pack-memory-usage update","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2015-04-18T10:47:03Z","receivedAt":"2015-04-18T10:47:03Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"The only change is in the commit message of 2/2 [1]. Sorry it took too\nlong, I completely forgot about it.\n\n[1] http://article.gmane.org/gmane.comp.version-control.git/264544\n\nNguyễn Thái Ngọc Duy (2):\n  index-pack: reduce object_entry size to save memory\n  index-pack: kill union delta_base to save memory\n\n builtin/index-pack.c | 290 +++++++++++++++++++++++++++++++--------------------\n 1 file changed, 179 insertions(+), 111 deletions(-)\n\n-- \n2.3.0.rc1.137.g477eb31\n"},{"id":"259621","messageId":"1429354025-24659-2-git-send-email-pclouds@gmail.com","threadId":"39107","inReplyTo":"1429354025-24659-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 1/2] index-pack: reduce object_entry size to save memory","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2015-04-18T10:47:04Z","receivedAt":"2015-04-18T10:47:04Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"For each object in the input pack, we need one struct object_entry. On\nx86-64, this struct is 64 bytes long. Although:\n\n - The 8 bytes for delta_depth and base_object_no are only useful when\n   show_stat is set. And it's never set unless someone is debugging.\n\n - The three fields hdr_size, type and real_type take 4 bytes each\n   even though they never use more than 4 bits.\n\nBy moving delta_depth and base_object_no out of struct object_entry\nand make the other 3 fields one byte long instead of 4, we shrink 25%\nof this struct.\n\nOn a 3.4M object repo (*) that's about 53MB. The saving is less\nimpressive compared to index-pack memory use for basic bookkeeping (**),\nabout 16%.\n\n(*) linux-2.6.git already has 4M objects as of v3.19-rc7 so this is\nnot an unrealistic number of objects that we have to deal with.\n\n(**)  3.4M * (sizeof(object_entry) + sizeof(delta_entry)) = 311MB\n\nBrought-up-by: Matthew Sporleder <msporleder@gmail.com>\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n builtin/index-pack.c | 30 +++++++++++++++++++-----------\n 1 file changed, 19 insertions(+), 11 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 4632117..9d854fb 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -18,9 +18,12 @@ static const char index_pack_usage[] =\n struct object_entry {\n \tstruct pack_idx_entry idx;\n \tunsigned long size;\n-\tunsigned int hdr_size;\n-\tenum object_type type;\n-\tenum object_type real_type;\n+\tunsigned char hdr_size;\n+\tsigned char type;\n+\tsigned char real_type;\n+};\n+\n+struct object_stat {\n \tunsigned delta_depth;\n \tint base_object_no;\n };\n@@ -64,6 +67,7 @@ struct delta_entry {\n };\n \n static struct object_entry *objects;\n+static struct object_stat *obj_stat;\n static struct delta_entry *deltas;\n static struct thread_local nothread_data;\n static int nr_objects;\n@@ -873,13 +877,15 @@ static void resolve_delta(struct object_entry *delta_obj,\n \tvoid *base_data, *delta_data;\n \n \tif (show_stat) {\n-\t\tdelta_obj->delta_depth = base->obj->delta_depth + 1;\n+\t\tint i = delta_obj - objects;\n+\t\tint j = base->obj - objects;\n+\t\tobj_stat[i].delta_depth = obj_stat[j].delta_depth + 1;\n \t\tdeepest_delta_lock();\n-\t\tif (deepest_delta < delta_obj->delta_depth)\n-\t\t\tdeepest_delta = delta_obj->delta_depth;\n+\t\tif (deepest_delta < obj_stat[i].delta_depth)\n+\t\t\tdeepest_delta = obj_stat[i].delta_depth;\n \t\tdeepest_delta_unlock();\n+\t\tobj_stat[i].base_object_no = j;\n \t}\n-\tdelta_obj->base_object_no = base->obj - objects;\n \tdelta_data = get_data_from_pack(delta_obj);\n \tbase_data = get_base_data(base);\n \tresult->obj = delta_obj;\n@@ -902,7 +908,7 @@ static void resolve_delta(struct object_entry *delta_obj,\n  * \"want\"; if so, swap in \"set\" and return true. Otherwise, leave it untouched\n  * and return false.\n  */\n-static int compare_and_swap_type(enum object_type *type,\n+static int compare_and_swap_type(signed char *type,\n \t\t\t\t enum object_type want,\n \t\t\t\t enum object_type set)\n {\n@@ -1499,7 +1505,7 @@ static void show_pack_info(int stat_only)\n \t\tstruct object_entry *obj = &objects[i];\n \n \t\tif (is_delta_type(obj->type))\n-\t\t\tchain_histogram[obj->delta_depth - 1]++;\n+\t\t\tchain_histogram[obj_stat[i].delta_depth - 1]++;\n \t\tif (stat_only)\n \t\t\tcontinue;\n \t\tprintf(\"%s %-6s %lu %lu %\"PRIuMAX,\n@@ -1508,8 +1514,8 @@ static void show_pack_info(int stat_only)\n \t\t       (unsigned long)(obj[1].idx.offset - obj->idx.offset),\n \t\t       (uintmax_t)obj->idx.offset);\n \t\tif (is_delta_type(obj->type)) {\n-\t\t\tstruct object_entry *bobj = &objects[obj->base_object_no];\n-\t\t\tprintf(\" %u %s\", obj->delta_depth, sha1_to_hex(bobj->idx.sha1));\n+\t\t\tstruct object_entry *bobj = &objects[obj_stat[i].base_object_no];\n+\t\t\tprintf(\" %u %s\", obj_stat[i].delta_depth, sha1_to_hex(bobj->idx.sha1));\n \t\t}\n \t\tputchar('\\n');\n \t}\n@@ -1672,6 +1678,8 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \tcurr_pack = open_pack_file(pack_name);\n \tparse_pack_header();\n \tobjects = xcalloc(nr_objects + 1, sizeof(struct object_entry));\n+\tif (show_stat)\n+\t\tobj_stat = xcalloc(nr_objects + 1, sizeof(struct object_stat));\n \tdeltas = xcalloc(nr_objects, sizeof(struct delta_entry));\n \tparse_pack_objects(pack_sha1);\n \tresolve_deltas();\n-- \n2.3.0.rc1.137.g477eb31\n"},{"id":"259622","messageId":"1429354025-24659-3-git-send-email-pclouds@gmail.com","threadId":"39107","inReplyTo":"1429354025-24659-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 2/2] index-pack: kill union delta_base to save memory","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2015-04-18T10:47:05Z","receivedAt":"2015-04-18T10:47:05Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Once we know the number of objects in the input pack, we allocate an\narray of nr_objects of struct delta_entry. On x86-64, this struct is\n32 bytes long. The union delta_base, which is part of struct\ndelta_entry, provides enough space to store either ofs-delta (8 bytes)\nor ref-delta (20 bytes).\n\nBecause ofs-delta encoding is more efficient space-wise and more\nperformant at runtime than ref-delta encoding, Git packers try to use\nofs-delta whenever possible, and it is expected that objects encoded\nas ref-delta are minority.\n\nIn the best clone case where no ref-delta object is present, we waste\n(20-8) * nr_objects bytes because of this union. That's about 38MB out\nof 100MB for deltas[] with 3.4M objects, or 38%. deltas[] would be\naround 62MB without the waste.\n\nThis patch attempts to eliminate that. deltas[] array is split into\ntwo: one for ofs-delta and one for ref-delta. Many functions are also\nduplicated because of this split. With this patch, ofs_deltas[] array\ntakes 51MB. ref_deltas[] should remain unallocated in clone case (0\nbytes). This array grows as we see ref-delta. We save about half in\nthis case, or 25% of total bookkeeping.\n\nThe saving is more than the calculation above because some padding in\nthe old delta_entry struct is removed. ofs_delta_entry is 16 bytes,\nincluding the 4 bytes padding. That's 13MB for padding, but packing\nthe struct could break platforms that do not support unaligned\naccess. If someone on 32-bit is really low on memory and only deals\nwith packs smaller than 2G, using 32-bit off_t would eliminate the\npadding and save 27MB on top.\n\nA note about ofs_deltas allocation. We could use ref_deltas memory\nallocation strategy for ofs_deltas. But that probably just adds more\noverhead on top. ofs-deltas are generally the majority (1/2 to 2/3) in\nany pack. Incremental realloc may lead to too many memcpy. And if we\npreallocate, say 1/2 or 2/3 of nr_objects initially, the growth rate\nof ALLOC_GROW() could make this array larger than nr_objects, wasting\nmore memory.\n\nBrought-up-by: Matthew Sporleder <msporleder@gmail.com>\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n builtin/index-pack.c | 260 +++++++++++++++++++++++++++++++--------------------\n 1 file changed, 160 insertions(+), 100 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 9d854fb..3ed53e3 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -28,11 +28,6 @@ struct object_stat {\n \tint base_object_no;\n };\n \n-union delta_base {\n-\tunsigned char sha1[20];\n-\toff_t offset;\n-};\n-\n struct base_data {\n \tstruct base_data *base;\n \tstruct base_data *child;\n@@ -52,26 +47,28 @@ struct thread_local {\n \tint pack_fd;\n };\n \n-/*\n- * Even if sizeof(union delta_base) == 24 on 64-bit archs, we really want\n- * to memcmp() only the first 20 bytes.\n- */\n-#define UNION_BASE_SZ\t20\n-\n #define FLAG_LINK (1u<<20)\n #define FLAG_CHECKED (1u<<21)\n \n-struct delta_entry {\n-\tunion delta_base base;\n+struct ofs_delta_entry {\n+\toff_t offset;\n+\tint obj_no;\n+};\n+\n+struct ref_delta_entry {\n+\tunsigned char sha1[20];\n \tint obj_no;\n };\n \n static struct object_entry *objects;\n static struct object_stat *obj_stat;\n-static struct delta_entry *deltas;\n+static struct ofs_delta_entry *ofs_deltas;\n+static struct ref_delta_entry *ref_deltas;\n static struct thread_local nothread_data;\n static int nr_objects;\n-static int nr_deltas;\n+static int nr_ofs_deltas;\n+static int nr_ref_deltas;\n+static int ref_deltas_alloc;\n static int nr_resolved_deltas;\n static int nr_threads;\n \n@@ -480,7 +477,8 @@ static void *unpack_entry_data(unsigned long offset, unsigned long size,\n }\n \n static void *unpack_raw_entry(struct object_entry *obj,\n-\t\t\t      union delta_base *delta_base,\n+\t\t\t      off_t *ofs_offset,\n+\t\t\t      unsigned char *ref_sha1,\n \t\t\t      unsigned char *sha1)\n {\n \tunsigned char *p;\n@@ -509,11 +507,10 @@ static void *unpack_raw_entry(struct object_entry *obj,\n \n \tswitch (obj->type) {\n \tcase OBJ_REF_DELTA:\n-\t\thashcpy(delta_base->sha1, fill(20));\n+\t\thashcpy(ref_sha1, fill(20));\n \t\tuse(20);\n \t\tbreak;\n \tcase OBJ_OFS_DELTA:\n-\t\tmemset(delta_base, 0, sizeof(*delta_base));\n \t\tp = fill(1);\n \t\tc = *p;\n \t\tuse(1);\n@@ -527,8 +524,8 @@ static void *unpack_raw_entry(struct object_entry *obj,\n \t\t\tuse(1);\n \t\t\tbase_offset = (base_offset << 7) + (c & 127);\n \t\t}\n-\t\tdelta_base->offset = obj->idx.offset - base_offset;\n-\t\tif (delta_base->offset <= 0 || delta_base->offset >= obj->idx.offset)\n+\t\t*ofs_offset = obj->idx.offset - base_offset;\n+\t\tif (*ofs_offset <= 0 || *ofs_offset >= obj->idx.offset)\n \t\t\tbad_object(obj->idx.offset, _(\"delta base offset is out of bound\"));\n \t\tbreak;\n \tcase OBJ_COMMIT:\n@@ -612,55 +609,108 @@ static void *get_data_from_pack(struct object_entry *obj)\n \treturn unpack_data(obj, NULL, NULL);\n }\n \n-static int compare_delta_bases(const union delta_base *base1,\n-\t\t\t       const union delta_base *base2,\n-\t\t\t       enum object_type type1,\n-\t\t\t       enum object_type type2)\n+static int compare_ofs_delta_bases(off_t offset1, off_t offset2,\n+\t\t\t\t   enum object_type type1,\n+\t\t\t\t   enum object_type type2)\n {\n \tint cmp = type1 - type2;\n \tif (cmp)\n \t\treturn cmp;\n-\treturn memcmp(base1, base2, UNION_BASE_SZ);\n+\treturn offset1 - offset2;\n }\n \n-static int find_delta(const union delta_base *base, enum object_type type)\n+static int find_ofs_delta(const off_t offset, enum object_type type)\n {\n-\tint first = 0, last = nr_deltas;\n-\n-        while (first < last) {\n-                int next = (first + last) / 2;\n-                struct delta_entry *delta = &deltas[next];\n-                int cmp;\n-\n-\t\tcmp = compare_delta_bases(base, &delta->base,\n-\t\t\t\t\t  type, objects[delta->obj_no].type);\n-                if (!cmp)\n-                        return next;\n-                if (cmp < 0) {\n-                        last = next;\n-                        continue;\n-                }\n-                first = next+1;\n-        }\n-        return -first-1;\n+\tint first = 0, last = nr_ofs_deltas;\n+\n+\twhile (first < last) {\n+\t\tint next = (first + last) / 2;\n+\t\tstruct ofs_delta_entry *delta = &ofs_deltas[next];\n+\t\tint cmp;\n+\n+\t\tcmp = compare_ofs_delta_bases(offset, delta->offset,\n+\t\t\t\t\t      type, objects[delta->obj_no].type);\n+\t\tif (!cmp)\n+\t\t\treturn next;\n+\t\tif (cmp < 0) {\n+\t\t\tlast = next;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tfirst = next+1;\n+\t}\n+\treturn -first-1;\n }\n \n-static void find_delta_children(const union delta_base *base,\n-\t\t\t\tint *first_index, int *last_index,\n-\t\t\t\tenum object_type type)\n+static void find_ofs_delta_children(off_t offset,\n+\t\t\t\t    int *first_index, int *last_index,\n+\t\t\t\t    enum object_type type)\n {\n-\tint first = find_delta(base, type);\n+\tint first = find_ofs_delta(offset, type);\n \tint last = first;\n-\tint end = nr_deltas - 1;\n+\tint end = nr_ofs_deltas - 1;\n \n \tif (first < 0) {\n \t\t*first_index = 0;\n \t\t*last_index = -1;\n \t\treturn;\n \t}\n-\twhile (first > 0 && !memcmp(&deltas[first - 1].base, base, UNION_BASE_SZ))\n+\twhile (first > 0 && ofs_deltas[first - 1].offset == offset)\n \t\t--first;\n-\twhile (last < end && !memcmp(&deltas[last + 1].base, base, UNION_BASE_SZ))\n+\twhile (last < end && ofs_deltas[last + 1].offset == offset)\n+\t\t++last;\n+\t*first_index = first;\n+\t*last_index = last;\n+}\n+\n+static int compare_ref_delta_bases(const unsigned char *sha1,\n+\t\t\t\t   const unsigned char *sha2,\n+\t\t\t\t   enum object_type type1,\n+\t\t\t\t   enum object_type type2)\n+{\n+\tint cmp = type1 - type2;\n+\tif (cmp)\n+\t\treturn cmp;\n+\treturn hashcmp(sha1, sha2);\n+}\n+\n+static int find_ref_delta(const unsigned char *sha1, enum object_type type)\n+{\n+\tint first = 0, last = nr_ref_deltas;\n+\n+\twhile (first < last) {\n+\t\tint next = (first + last) / 2;\n+\t\tstruct ref_delta_entry *delta = &ref_deltas[next];\n+\t\tint cmp;\n+\n+\t\tcmp = compare_ref_delta_bases(sha1, delta->sha1,\n+\t\t\t\t\t      type, objects[delta->obj_no].type);\n+\t\tif (!cmp)\n+\t\t\treturn next;\n+\t\tif (cmp < 0) {\n+\t\t\tlast = next;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tfirst = next+1;\n+\t}\n+\treturn -first-1;\n+}\n+\n+static void find_ref_delta_children(const unsigned char *sha1,\n+\t\t\t\t    int *first_index, int *last_index,\n+\t\t\t\t    enum object_type type)\n+{\n+\tint first = find_ref_delta(sha1, type);\n+\tint last = first;\n+\tint end = nr_ref_deltas - 1;\n+\n+\tif (first < 0) {\n+\t\t*first_index = 0;\n+\t\t*last_index = -1;\n+\t\treturn;\n+\t}\n+\twhile (first > 0 && !hashcmp(ref_deltas[first - 1].sha1, sha1))\n+\t\t--first;\n+\twhile (last < end && !hashcmp(ref_deltas[last + 1].sha1, sha1))\n \t\t++last;\n \t*first_index = first;\n \t*last_index = last;\n@@ -927,16 +977,13 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t\t\t\t\t\t  struct base_data *prev_base)\n {\n \tif (base->ref_last == -1 && base->ofs_last == -1) {\n-\t\tunion delta_base base_spec;\n-\n-\t\thashcpy(base_spec.sha1, base->obj->idx.sha1);\n-\t\tfind_delta_children(&base_spec,\n-\t\t\t\t    &base->ref_first, &base->ref_last, OBJ_REF_DELTA);\n+\t\tfind_ref_delta_children(base->obj->idx.sha1,\n+\t\t\t\t\t&base->ref_first, &base->ref_last,\n+\t\t\t\t\tOBJ_REF_DELTA);\n \n-\t\tmemset(&base_spec, 0, sizeof(base_spec));\n-\t\tbase_spec.offset = base->obj->idx.offset;\n-\t\tfind_delta_children(&base_spec,\n-\t\t\t\t    &base->ofs_first, &base->ofs_last, OBJ_OFS_DELTA);\n+\t\tfind_ofs_delta_children(base->obj->idx.offset,\n+\t\t\t\t\t&base->ofs_first, &base->ofs_last,\n+\t\t\t\t\tOBJ_OFS_DELTA);\n \n \t\tif (base->ref_last == -1 && base->ofs_last == -1) {\n \t\t\tfree(base->data);\n@@ -947,7 +994,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t}\n \n \tif (base->ref_first <= base->ref_last) {\n-\t\tstruct object_entry *child = objects + deltas[base->ref_first].obj_no;\n+\t\tstruct object_entry *child = objects + ref_deltas[base->ref_first].obj_no;\n \t\tstruct base_data *result = alloc_base_data();\n \n \t\tif (!compare_and_swap_type(&child->real_type, OBJ_REF_DELTA,\n@@ -963,7 +1010,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t}\n \n \tif (base->ofs_first <= base->ofs_last) {\n-\t\tstruct object_entry *child = objects + deltas[base->ofs_first].obj_no;\n+\t\tstruct object_entry *child = objects + ofs_deltas[base->ofs_first].obj_no;\n \t\tstruct base_data *result = alloc_base_data();\n \n \t\tassert(child->real_type == OBJ_OFS_DELTA);\n@@ -999,15 +1046,20 @@ static void find_unresolved_deltas(struct base_data *base)\n \t}\n }\n \n-static int compare_delta_entry(const void *a, const void *b)\n+static int compare_ofs_delta_entry(const void *a, const void *b)\n+{\n+\tconst struct ofs_delta_entry *delta_a = a;\n+\tconst struct ofs_delta_entry *delta_b = b;\n+\n+\treturn delta_a->offset - delta_b->offset;\n+}\n+\n+static int compare_ref_delta_entry(const void *a, const void *b)\n {\n-\tconst struct delta_entry *delta_a = a;\n-\tconst struct delta_entry *delta_b = b;\n+\tconst struct ref_delta_entry *delta_a = a;\n+\tconst struct ref_delta_entry *delta_b = b;\n \n-\t/* group by type (ref vs ofs) and then by value (sha-1 or offset) */\n-\treturn compare_delta_bases(&delta_a->base, &delta_b->base,\n-\t\t\t\t   objects[delta_a->obj_no].type,\n-\t\t\t\t   objects[delta_b->obj_no].type);\n+\treturn hashcmp(delta_a->sha1, delta_b->sha1);\n }\n \n static void resolve_base(struct object_entry *obj)\n@@ -1053,7 +1105,8 @@ static void *threaded_second_pass(void *data)\n static void parse_pack_objects(unsigned char *sha1)\n {\n \tint i, nr_delays = 0;\n-\tstruct delta_entry *delta = deltas;\n+\tstruct ofs_delta_entry *ofs_delta = ofs_deltas;\n+\tunsigned char ref_delta_sha1[20];\n \tstruct stat st;\n \n \tif (verbose)\n@@ -1062,12 +1115,18 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\t\t\tnr_objects);\n \tfor (i = 0; i < nr_objects; i++) {\n \t\tstruct object_entry *obj = &objects[i];\n-\t\tvoid *data = unpack_raw_entry(obj, &delta->base, obj->idx.sha1);\n+\t\tvoid *data = unpack_raw_entry(obj, &ofs_delta->offset,\n+\t\t\t\t\t      ref_delta_sha1, obj->idx.sha1);\n \t\tobj->real_type = obj->type;\n-\t\tif (is_delta_type(obj->type)) {\n-\t\t\tnr_deltas++;\n-\t\t\tdelta->obj_no = i;\n-\t\t\tdelta++;\n+\t\tif (obj->type == OBJ_OFS_DELTA) {\n+\t\t\tnr_ofs_deltas++;\n+\t\t\tofs_delta->obj_no = i;\n+\t\t\tofs_delta++;\n+\t\t} else if (obj->type == OBJ_REF_DELTA) {\n+\t\t\tALLOC_GROW(ref_deltas, nr_ref_deltas + 1, ref_deltas_alloc);\n+\t\t\thashcpy(ref_deltas[nr_ref_deltas].sha1, ref_delta_sha1);\n+\t\t\tref_deltas[nr_ref_deltas].obj_no = i;\n+\t\t\tnr_ref_deltas++;\n \t\t} else if (!data) {\n \t\t\t/* large blobs, check later */\n \t\t\tobj->real_type = OBJ_BAD;\n@@ -1118,15 +1177,18 @@ static void resolve_deltas(void)\n {\n \tint i;\n \n-\tif (!nr_deltas)\n+\tif (!nr_ofs_deltas && !nr_ref_deltas)\n \t\treturn;\n \n \t/* Sort deltas by base SHA1/offset for fast searching */\n-\tqsort(deltas, nr_deltas, sizeof(struct delta_entry),\n-\t      compare_delta_entry);\n+\tqsort(ofs_deltas, nr_ofs_deltas, sizeof(struct ofs_delta_entry),\n+\t      compare_ofs_delta_entry);\n+\tqsort(ref_deltas, nr_ref_deltas, sizeof(struct ref_delta_entry),\n+\t      compare_ref_delta_entry);\n \n \tif (verbose)\n-\t\tprogress = start_progress(_(\"Resolving deltas\"), nr_deltas);\n+\t\tprogress = start_progress(_(\"Resolving deltas\"),\n+\t\t\t\t\t  nr_ref_deltas + nr_ofs_deltas);\n \n #ifndef NO_PTHREADS\n \tnr_dispatched = 0;\n@@ -1164,7 +1226,7 @@ static void resolve_deltas(void)\n static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved);\n static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned char *pack_sha1)\n {\n-\tif (nr_deltas == nr_resolved_deltas) {\n+\tif (nr_ref_deltas + nr_ofs_deltas == nr_resolved_deltas) {\n \t\tstop_progress(&progress);\n \t\t/* Flush remaining pack final 20-byte SHA1. */\n \t\tflush();\n@@ -1175,7 +1237,7 @@ static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned cha\n \t\tstruct sha1file *f;\n \t\tunsigned char read_sha1[20], tail_sha1[20];\n \t\tstruct strbuf msg = STRBUF_INIT;\n-\t\tint nr_unresolved = nr_deltas - nr_resolved_deltas;\n+\t\tint nr_unresolved = nr_ofs_deltas + nr_ref_deltas - nr_resolved_deltas;\n \t\tint nr_objects_initial = nr_objects;\n \t\tif (nr_unresolved <= 0)\n \t\t\tdie(_(\"confusion beyond insanity\"));\n@@ -1197,11 +1259,11 @@ static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned cha\n \t\t\tdie(_(\"Unexpected tail checksum for %s \"\n \t\t\t      \"(disk corruption?)\"), curr_pack);\n \t}\n-\tif (nr_deltas != nr_resolved_deltas)\n+\tif (nr_ofs_deltas + nr_ref_deltas != nr_resolved_deltas)\n \t\tdie(Q_(\"pack has %d unresolved delta\",\n \t\t       \"pack has %d unresolved deltas\",\n-\t\t       nr_deltas - nr_resolved_deltas),\n-\t\t    nr_deltas - nr_resolved_deltas);\n+\t\t       nr_ofs_deltas + nr_ref_deltas - nr_resolved_deltas),\n+\t\t    nr_ofs_deltas + nr_ref_deltas - nr_resolved_deltas);\n }\n \n static int write_compressed(struct sha1file *f, void *in, unsigned int size)\n@@ -1261,14 +1323,14 @@ static struct object_entry *append_obj_to_pack(struct sha1file *f,\n \n static int delta_pos_compare(const void *_a, const void *_b)\n {\n-\tstruct delta_entry *a = *(struct delta_entry **)_a;\n-\tstruct delta_entry *b = *(struct delta_entry **)_b;\n+\tstruct ref_delta_entry *a = *(struct ref_delta_entry **)_a;\n+\tstruct ref_delta_entry *b = *(struct ref_delta_entry **)_b;\n \treturn a->obj_no - b->obj_no;\n }\n \n static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n {\n-\tstruct delta_entry **sorted_by_pos;\n+\tstruct ref_delta_entry **sorted_by_pos;\n \tint i, n = 0;\n \n \t/*\n@@ -1282,28 +1344,25 @@ static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n \t * resolving deltas in the same order as their position in the pack.\n \t */\n \tsorted_by_pos = xmalloc(nr_unresolved * sizeof(*sorted_by_pos));\n-\tfor (i = 0; i < nr_deltas; i++) {\n-\t\tif (objects[deltas[i].obj_no].real_type != OBJ_REF_DELTA)\n-\t\t\tcontinue;\n-\t\tsorted_by_pos[n++] = &deltas[i];\n-\t}\n+\tfor (i = 0; i < nr_ref_deltas; i++)\n+\t\tsorted_by_pos[n++] = &ref_deltas[i];\n \tqsort(sorted_by_pos, n, sizeof(*sorted_by_pos), delta_pos_compare);\n \n \tfor (i = 0; i < n; i++) {\n-\t\tstruct delta_entry *d = sorted_by_pos[i];\n+\t\tstruct ref_delta_entry *d = sorted_by_pos[i];\n \t\tenum object_type type;\n \t\tstruct base_data *base_obj = alloc_base_data();\n \n \t\tif (objects[d->obj_no].real_type != OBJ_REF_DELTA)\n \t\t\tcontinue;\n-\t\tbase_obj->data = read_sha1_file(d->base.sha1, &type, &base_obj->size);\n+\t\tbase_obj->data = read_sha1_file(d->sha1, &type, &base_obj->size);\n \t\tif (!base_obj->data)\n \t\t\tcontinue;\n \n-\t\tif (check_sha1_signature(d->base.sha1, base_obj->data,\n+\t\tif (check_sha1_signature(d->sha1, base_obj->data,\n \t\t\t\tbase_obj->size, typename(type)))\n-\t\t\tdie(_(\"local object %s is corrupt\"), sha1_to_hex(d->base.sha1));\n-\t\tbase_obj->obj = append_obj_to_pack(f, d->base.sha1,\n+\t\t\tdie(_(\"local object %s is corrupt\"), sha1_to_hex(d->sha1));\n+\t\tbase_obj->obj = append_obj_to_pack(f, d->sha1,\n \t\t\t\t\tbase_obj->data, base_obj->size, type);\n \t\tfind_unresolved_deltas(base_obj);\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n@@ -1495,7 +1554,7 @@ static void read_idx_option(struct pack_idx_option *opts, const char *pack_name)\n \n static void show_pack_info(int stat_only)\n {\n-\tint i, baseobjects = nr_objects - nr_deltas;\n+\tint i, baseobjects = nr_objects - nr_ref_deltas - nr_ofs_deltas;\n \tunsigned long *chain_histogram = NULL;\n \n \tif (deepest_delta)\n@@ -1680,11 +1739,12 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \tobjects = xcalloc(nr_objects + 1, sizeof(struct object_entry));\n \tif (show_stat)\n \t\tobj_stat = xcalloc(nr_objects + 1, sizeof(struct object_stat));\n-\tdeltas = xcalloc(nr_objects, sizeof(struct delta_entry));\n+\tofs_deltas = xcalloc(nr_objects, sizeof(struct ofs_delta_entry));\n \tparse_pack_objects(pack_sha1);\n \tresolve_deltas();\n \tconclude_pack(fix_thin_pack, curr_pack, pack_sha1);\n-\tfree(deltas);\n+\tfree(ofs_deltas);\n+\tfree(ref_deltas);\n \tif (strict)\n \t\tforeign_nr = check_objects();\n \n-- \n2.3.0.rc1.137.g477eb31\n"},{"id":"265463","messageId":"xmqqoajt5glu.fsf@gitster.dls.corp.google.com","threadId":"39107","inReplyTo":"1429354025-24659-3-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH 2/2] index-pack: kill union delta_base to save memory","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-07-03T16:51:57Z","receivedAt":"2015-07-03T16:51:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n\n> Once we know the number of objects in the input pack, we allocate an\n> array of nr_objects of struct delta_entry. On x86-64, this struct is\n> 32 bytes long. The union delta_base, which is part of struct\n> delta_entry, provides enough space to store either ofs-delta (8 bytes)\n> or ref-delta (20 bytes).\n\nSorry for responding to a patch 7000+ messages ago, but some kind\nfolks at Google were puzzled by this code, and I think they found a\nsmall bug.\n\n>  static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n>  {\n> -\tstruct delta_entry **sorted_by_pos;\n> +\tstruct ref_delta_entry **sorted_by_pos;\n>  \tint i, n = 0;\n>  \n>  \t/*\n> @@ -1282,28 +1344,25 @@ static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n>  \t * resolving deltas in the same order as their position in the pack.\n>  \t */\n>  \tsorted_by_pos = xmalloc(nr_unresolved * sizeof(*sorted_by_pos));\n> -\tfor (i = 0; i < nr_deltas; i++) {\n> -\t\tif (objects[deltas[i].obj_no].real_type != OBJ_REF_DELTA)\n> -\t\t\tcontinue;\n> -\t\tsorted_by_pos[n++] = &deltas[i];\n> -\t}\n> +\tfor (i = 0; i < nr_ref_deltas; i++)\n> +\t\tsorted_by_pos[n++] = &ref_deltas[i];\n>  \tqsort(sorted_by_pos, n, sizeof(*sorted_by_pos), delta_pos_compare);\n\nYou allocate an array of nr_unresolved (which is the sum of\nnr_ref_deltas and nr_ofs_deltas in the new world order with patch)\nentries, fill only the first nr_ref_deltas entries of it, and then\nsort that first n (= nr_ref_deltas) entries.  The qsort and the\nsubsequent loop only looks at the first n entries, so nothing is\nfilling or reading these nr_ofs_deltas entres at the end.\n\nI do not see any wrong behaviour other than temporary wastage of\nnr_ofs_deltas pointers that would be caused by this, but this\nallocation is misleading.\n\nAlso, the old code before this change had to use 'i' and 'n' because\nsome of the things we see in the (old) deltas[] array we scanned\nwith 'i' would not make it into the sorted_by_pos[] array in the old\nworld order, but now because you have only ref delta in a separate\nref_deltas[] array, they increment lock&step.  That also puzzled me\nwhile re-reading this code.\n\nPerhaps something like this is needed?\n\n\n builtin/index-pack.c | 10 +++++-----\n 1 file changed, 5 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 48fa472..d6c48cd 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1334,7 +1334,7 @@ static int delta_pos_compare(const void *_a, const void *_b)\n static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n {\n \tstruct ref_delta_entry **sorted_by_pos;\n-\tint i, n = 0;\n+\tint i;\n \n \t/*\n \t * Since many unresolved deltas may well be themselves base objects\n@@ -1346,12 +1346,12 @@ static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n \t * before deltas depending on them, a good heuristic is to start\n \t * resolving deltas in the same order as their position in the pack.\n \t */\n-\tsorted_by_pos = xmalloc(nr_unresolved * sizeof(*sorted_by_pos));\n+\tsorted_by_pos = xmalloc(nr_ref_deltas * sizeof(*sorted_by_pos));\n \tfor (i = 0; i < nr_ref_deltas; i++)\n-\t\tsorted_by_pos[n++] = &ref_deltas[i];\n-\tqsort(sorted_by_pos, n, sizeof(*sorted_by_pos), delta_pos_compare);\n+\t\tsorted_by_pos[i] = &ref_deltas[i];\n+\tqsort(sorted_by_pos, nr_ref_deltas, sizeof(*sorted_by_pos), delta_pos_compare);\n \n-\tfor (i = 0; i < n; i++) {\n+\tfor (i = 0; i < nr_ref_deltas; i++) {\n \t\tstruct ref_delta_entry *d = sorted_by_pos[i];\n \t\tenum object_type type;\n \t\tstruct base_data *base_obj = alloc_base_data();\n"},{"id":"265475","messageId":"CACsJy8D872sj9WQec_FZrTxx=gqy++L1XLxJdEtEQNpGpFYr=Q@mail.gmail.com","threadId":"39107","inReplyTo":"xmqqoajt5glu.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 2/2] index-pack: kill union delta_base to save memory","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2015-07-03T18:29:19Z","receivedAt":"2015-07-03T18:29:19Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Jul 3, 2015 at 11:51 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n>\n>> Once we know the number of objects in the input pack, we allocate an\n>> array of nr_objects of struct delta_entry. On x86-64, this struct is\n>> 32 bytes long. The union delta_base, which is part of struct\n>> delta_entry, provides enough space to store either ofs-delta (8 bytes)\n>> or ref-delta (20 bytes).\n>\n> Sorry for responding to a patch 7000+ messages ago, but some kind\n> folks at Google were puzzled by this code, and I think they found a\n> small bug.\n>\n>>  static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n>>  {\n>> -     struct delta_entry **sorted_by_pos;\n>> +     struct ref_delta_entry **sorted_by_pos;\n>>       int i, n = 0;\n>>\n>>       /*\n>> @@ -1282,28 +1344,25 @@ static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n>>        * resolving deltas in the same order as their position in the pack.\n>>        */\n>>       sorted_by_pos = xmalloc(nr_unresolved * sizeof(*sorted_by_pos));\n>> -     for (i = 0; i < nr_deltas; i++) {\n>> -             if (objects[deltas[i].obj_no].real_type != OBJ_REF_DELTA)\n>> -                     continue;\n>> -             sorted_by_pos[n++] = &deltas[i];\n>> -     }\n>> +     for (i = 0; i < nr_ref_deltas; i++)\n>> +             sorted_by_pos[n++] = &ref_deltas[i];\n>>       qsort(sorted_by_pos, n, sizeof(*sorted_by_pos), delta_pos_compare);\n>\n> You allocate an array of nr_unresolved (which is the sum of\n> nr_ref_deltas and nr_ofs_deltas in the new world order with patch)\n> entries, fill only the first nr_ref_deltas entries of it, and then\n> sort that first n (= nr_ref_deltas) entries.  The qsort and the\n> subsequent loop only looks at the first n entries, so nothing is\n> filling or reading these nr_ofs_deltas entres at the end.\n>\n> I do not see any wrong behaviour other than temporary wastage of\n> nr_ofs_deltas pointers that would be caused by this, but this\n> allocation is misleading.\n>\n> Also, the old code before this change had to use 'i' and 'n' because\n> some of the things we see in the (old) deltas[] array we scanned\n> with 'i' would not make it into the sorted_by_pos[] array in the old\n> world order, but now because you have only ref delta in a separate\n> ref_deltas[] array, they increment lock&step.  That also puzzled me\n> while re-reading this code.\n>\n> Perhaps something like this is needed?\n\nYeah I can see the confusion when reading the code without checking\nits history. You probably want to kill the argument nr_unresolved too\nbecause it's not needed anymore after your patch.\n\nSo what's the bug you mentioned? All I got from the above was wastage\nand confusion, no bug.\n-- \nDuy\n"},{"id":"265507","messageId":"xmqqzj3c3efv.fsf_-_@gitster.dls.corp.google.com","threadId":"39107","inReplyTo":"CACsJy8D872sj9WQec_FZrTxx=gqy++L1XLxJdEtEQNpGpFYr=Q@mail.gmail.com","subject":"[PATCH] index-pack: fix overallocation of sorted_by_pos array","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-07-04T01:21:40Z","receivedAt":"2015-07-04T01:21:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"When c6458e60 (index-pack: kill union delta_base to save memory,\n2015-04-18) attempted to reduce the memory footprint of index-pack,\none of the key thing it did was to keep track of ref-deltas and\nofs-deltas separately.\n\nIn fix_unresolved_deltas(), however it forgot that it now wants to\nlook only at ref deltas in one place.  The code allocated an array\nsufficient to hold both ref- and ofs-deltas, stuffed only ref-deltas\nin the array, sorted it (with the right count) and iterated over the\narray (with the right count).\n\nThere is no externally visible ill effect, other than a small\nwastage of memory, but the code was misleading.\n\nAlso, the old code before this change had to use 'i' and 'n' because\nsome of the things we see in the (old) deltas[] array we scanned\nwith 'i' would not make it into the sorted_by_pos[] array in the old\nworld order, but now because you have only ref delta in a separate\nref_deltas[] array, they increment lock&step.  We no longer need\nseparate variables (nor the nr_unresolved parameter).\n\nHelped-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n\n * This time with a formal log message.  Again, this is not really a\n   \"bug\"-fix; just returning the memory that we allocated without\n   using to the system, and making the code easier to follow.\n\n builtin/index-pack.c | 16 ++++++++--------\n 1 file changed, 8 insertions(+), 8 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 3ed53e3..fa13e20 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1223,7 +1223,7 @@ static void resolve_deltas(void)\n  * - append objects to convert thin pack to full pack if required\n  * - write the final 20-byte SHA-1\n  */\n-static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved);\n+static void fix_unresolved_deltas(struct sha1file *f);\n static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned char *pack_sha1)\n {\n \tif (nr_ref_deltas + nr_ofs_deltas == nr_resolved_deltas) {\n@@ -1245,7 +1245,7 @@ static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned cha\n \t\tmemset(objects + nr_objects + 1, 0,\n \t\t       nr_unresolved * sizeof(*objects));\n \t\tf = sha1fd(output_fd, curr_pack);\n-\t\tfix_unresolved_deltas(f, nr_unresolved);\n+\t\tfix_unresolved_deltas(f);\n \t\tstrbuf_addf(&msg, _(\"completed with %d local objects\"),\n \t\t\t    nr_objects - nr_objects_initial);\n \t\tstop_progress_msg(&progress, msg.buf);\n@@ -1328,10 +1328,10 @@ static int delta_pos_compare(const void *_a, const void *_b)\n \treturn a->obj_no - b->obj_no;\n }\n \n-static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n+static void fix_unresolved_deltas(struct sha1file *f)\n {\n \tstruct ref_delta_entry **sorted_by_pos;\n-\tint i, n = 0;\n+\tint i;\n \n \t/*\n \t * Since many unresolved deltas may well be themselves base objects\n@@ -1343,12 +1343,12 @@ static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n \t * before deltas depending on them, a good heuristic is to start\n \t * resolving deltas in the same order as their position in the pack.\n \t */\n-\tsorted_by_pos = xmalloc(nr_unresolved * sizeof(*sorted_by_pos));\n+\tsorted_by_pos = xmalloc(nr_ref_deltas * sizeof(*sorted_by_pos));\n \tfor (i = 0; i < nr_ref_deltas; i++)\n-\t\tsorted_by_pos[n++] = &ref_deltas[i];\n-\tqsort(sorted_by_pos, n, sizeof(*sorted_by_pos), delta_pos_compare);\n+\t\tsorted_by_pos[i] = &ref_deltas[i];\n+\tqsort(sorted_by_pos, nr_ref_deltas, sizeof(*sorted_by_pos), delta_pos_compare);\n \n-\tfor (i = 0; i < n; i++) {\n+\tfor (i = 0; i < nr_ref_deltas; i++) {\n \t\tstruct ref_delta_entry *d = sorted_by_pos[i];\n \t\tenum object_type type;\n \t\tstruct base_data *base_obj = alloc_base_data();\n-- \n2.5.0-rc1-213-g8b7a1c9\n"},{"id":"265520","messageId":"xmqqvbdz36j3.fsf@gitster.dls.corp.google.com","threadId":"39107","inReplyTo":"CACsJy8D872sj9WQec_FZrTxx=gqy++L1XLxJdEtEQNpGpFYr=Q@mail.gmail.com","subject":"Re: [PATCH 2/2] index-pack: kill union delta_base to save memory","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-07-04T22:24:48Z","receivedAt":"2015-07-04T22:24:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen <pclouds@gmail.com> writes:\n\n>>> @@ -1282,28 +1344,25 @@ static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n>>>        * resolving deltas in the same order as their position in the pack.\n>>>        */\n>>>       sorted_by_pos = xmalloc(nr_unresolved * sizeof(*sorted_by_pos));\n>>> -     for (i = 0; i < nr_deltas; i++) {\n>>> -             if (objects[deltas[i].obj_no].real_type != OBJ_REF_DELTA)\n>>> -                     continue;\n>>> -             sorted_by_pos[n++] = &deltas[i];\n>>> -     }\n>>> +     for (i = 0; i < nr_ref_deltas; i++)\n>>> +             sorted_by_pos[n++] = &ref_deltas[i];\n>>>       qsort(sorted_by_pos, n, sizeof(*sorted_by_pos), delta_pos_compare);\n>>\n>> You allocate an array of nr_unresolved (which is the sum of\n>> nr_ref_deltas and nr_ofs_deltas in the new world order with patch)\n>> entries, fill only the first nr_ref_deltas entries of it, and then\n>> sort that first n (= nr_ref_deltas) entries.  The qsort and the\n>> subsequent loop only looks at the first n entries, so nothing is\n>> filling or reading these nr_ofs_deltas entres at the end.\n>>\n>> I do not see any wrong behaviour other than temporary wastage of\n>> nr_ofs_deltas pointers that would be caused by this, but this\n>> allocation is misleading.\n>>\n>> Also, the old code before this change had to use 'i' and 'n' because\n>> some of the things we see in the (old) deltas[] array we scanned\n>> with 'i' would not make it into the sorted_by_pos[] array in the old\n>> world order, but now because you have only ref delta in a separate\n>> ref_deltas[] array, they increment lock&step.  That also puzzled me\n>> while re-reading this code.\n>>\n>> Perhaps something like this is needed?\n>\n> Yeah I can see the confusion when reading the code without checking\n> its history. You probably want to kill the argument nr_unresolved too\n> because it's not needed anymore after your patch.\n>\n> So what's the bug you mentioned? All I got from the above was wastage\n> and confusion, no bug.\n\nActually, the above is not analyzed correctly.  I thought\nnr_unresolved was ref + ofs, but look at the caller in the\nfix_thin_pack codepath:\n\n\tint nr_unresolved = nr_ofs_deltas + nr_ref_deltas - nr_resolved_deltas;\n\tint nr_objects_initial = nr_objects;\n\tif (nr_unresolved <= 0)\n\t\tdie(_(\"confusion beyond insanity\"));\n\tREALLOC_ARRAY(objects, nr_objects + nr_unresolved + 1);\n\tmemset(objects + nr_objects + 1, 0,\n\t       nr_unresolved * sizeof(*objects));\n\tf = sha1fd(output_fd, curr_pack);\n\tfix_unresolved_deltas(f, nr_unresolved);\n\nIf there were tons of nr_resolved_deltas and only small number of\nnr_ofs_deltas, then the allocation in question may actually be\nunder-allocating.\n\nSo...\n"},{"id":"265522","messageId":"xmqqr3on369x.fsf_-_@gitster.dls.corp.google.com","threadId":"39107","inReplyTo":"xmqqzj3c3efv.fsf_-_@gitster.dls.corp.google.com","subject":"[PATCH] index-pack: fix allocation of sorted_by_pos array","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-07-04T22:30:18Z","receivedAt":"2015-07-04T22:30:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"When c6458e60 (index-pack: kill union delta_base to save memory,\n2015-04-18) attempted to reduce the memory footprint of index-pack,\none of the key thing it did was to keep track of ref-deltas and\nofs-deltas separately.\n\nIn fix_unresolved_deltas(), however it forgot that it now wants to\nlook only at ref deltas in one place.  The code allocated an array\nfor nr_unresolved, which is sum of number of ref- and ofs-deltas\nminus nr_resolved, which may be larger or smaller than the number\nref-deltas.  Depending on nr_resolved, this was either under or over\nallocating.\n\nAlso, the old code before this change had to use 'i' and 'n' because\nsome of the things we see in the (old) deltas[] array we scanned\nwith 'i' would not make it into the sorted_by_pos[] array in the old\nworld order, but now because you have only ref delta in a separate\nref_deltas[] array, they increment lock&step.  We no longer need\nseparate variables.  And most importantly, we shouldn't pass the\nnr_unresolved parameter, as this number does not play a role in the\nworking of this helper function.\n\nHelped-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n\n * This time, correcting the analysis; the previous one claimed that\n   this was not a bug but just an overallocation. It indeed is a bug\n   that uses an unrelated value that may or may not be sufficiently\n   large to hold the whole thing, I think.\n\n builtin/index-pack.c | 16 ++++++++--------\n 1 file changed, 8 insertions(+), 8 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 3ed53e3..fa13e20 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1223,7 +1223,7 @@ static void resolve_deltas(void)\n  * - append objects to convert thin pack to full pack if required\n  * - write the final 20-byte SHA-1\n  */\n-static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved);\n+static void fix_unresolved_deltas(struct sha1file *f);\n static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned char *pack_sha1)\n {\n \tif (nr_ref_deltas + nr_ofs_deltas == nr_resolved_deltas) {\n@@ -1245,7 +1245,7 @@ static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned cha\n \t\tmemset(objects + nr_objects + 1, 0,\n \t\t       nr_unresolved * sizeof(*objects));\n \t\tf = sha1fd(output_fd, curr_pack);\n-\t\tfix_unresolved_deltas(f, nr_unresolved);\n+\t\tfix_unresolved_deltas(f);\n \t\tstrbuf_addf(&msg, _(\"completed with %d local objects\"),\n \t\t\t    nr_objects - nr_objects_initial);\n \t\tstop_progress_msg(&progress, msg.buf);\n@@ -1328,10 +1328,10 @@ static int delta_pos_compare(const void *_a, const void *_b)\n \treturn a->obj_no - b->obj_no;\n }\n \n-static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n+static void fix_unresolved_deltas(struct sha1file *f)\n {\n \tstruct ref_delta_entry **sorted_by_pos;\n-\tint i, n = 0;\n+\tint i;\n \n \t/*\n \t * Since many unresolved deltas may well be themselves base objects\n@@ -1343,12 +1343,12 @@ static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)\n \t * before deltas depending on them, a good heuristic is to start\n \t * resolving deltas in the same order as their position in the pack.\n \t */\n-\tsorted_by_pos = xmalloc(nr_unresolved * sizeof(*sorted_by_pos));\n+\tsorted_by_pos = xmalloc(nr_ref_deltas * sizeof(*sorted_by_pos));\n \tfor (i = 0; i < nr_ref_deltas; i++)\n-\t\tsorted_by_pos[n++] = &ref_deltas[i];\n-\tqsort(sorted_by_pos, n, sizeof(*sorted_by_pos), delta_pos_compare);\n+\t\tsorted_by_pos[i] = &ref_deltas[i];\n+\tqsort(sorted_by_pos, nr_ref_deltas, sizeof(*sorted_by_pos), delta_pos_compare);\n \n-\tfor (i = 0; i < n; i++) {\n+\tfor (i = 0; i < nr_ref_deltas; i++) {\n \t\tstruct ref_delta_entry *d = sorted_by_pos[i];\n \t\tenum object_type type;\n \t\tstruct base_data *base_obj = alloc_base_data();\n-- \n2.5.0-rc1-220-g8f9c9ba\n"},{"id":"265636","messageId":"xmqqvbdwyinx.fsf@gitster.dls.corp.google.com","threadId":"39107","inReplyTo":"xmqqr3on369x.fsf_-_@gitster.dls.corp.google.com","subject":"Re: [PATCH] index-pack: fix allocation of sorted_by_pos array","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-07-06T23:23:46Z","receivedAt":"2015-07-06T23:23:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> When c6458e60 (index-pack: kill union delta_base to save memory,\n> 2015-04-18) attempted to reduce the memory footprint of index-pack,\n> one of the key thing it did was to keep track of ref-deltas and\n> ofs-deltas separately.\n>\n> In fix_unresolved_deltas(), however it forgot that it now wants to\n> look only at ref deltas in one place.  The code allocated an array\n> for nr_unresolved, which is sum of number of ref- and ofs-deltas\n> minus nr_resolved, which may be larger or smaller than the number\n> ref-deltas.  Depending on nr_resolved, this was either under or over\n> allocating.\n>\n> Also, the old code before this change had to use 'i' and 'n' because\n> some of the things we see in the (old) deltas[] array we scanned\n> with 'i' would not make it into the sorted_by_pos[] array in the old\n> world order, but now because you have only ref delta in a separate\n> ref_deltas[] array, they increment lock&step.  We no longer need\n> separate variables.  And most importantly, we shouldn't pass the\n> nr_unresolved parameter, as this number does not play a role in the\n> working of this helper function.\n>\n> Helped-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n> Signed-off-by: Junio C Hamano <gitster@pobox.com>\n> ---\n>\n>  * This time, correcting the analysis; the previous one claimed that\n>    this was not a bug but just an overallocation. It indeed is a bug\n>    that uses an unrelated value that may or may not be sufficiently\n>    large to hold the whole thing, I think.\n\nI think this one as a real \"crash hotfix\" must be in the upcoming\nrelease (the obvious alternative is to revert the series with\nc6458e60 which I really want to avoid).\n\nAs Eric's \"worktree add\" would need some more time to solidify,\nlet's delay the -rc2 and later by a few weeks.\n"},{"id":"265638","messageId":"CACsJy8CsUu1zEnah9Ah3tQxk8N-xPpOBuV5TpQ4EB6+nyiDW3g@mail.gmail.com","threadId":"39107","inReplyTo":"xmqqr3on369x.fsf_-_@gitster.dls.corp.google.com","subject":"Re: [PATCH] index-pack: fix allocation of sorted_by_pos array","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2015-07-07T00:36:23Z","receivedAt":"2015-07-07T00:36:23Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Jul 5, 2015 at 5:30 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> When c6458e60 (index-pack: kill union delta_base to save memory,\n> 2015-04-18) attempted to reduce the memory footprint of index-pack,\n> one of the key thing it did was to keep track of ref-deltas and\n> ofs-deltas separately.\n>\n> In fix_unresolved_deltas(), however it forgot that it now wants to\n> look only at ref deltas in one place.  The code allocated an array\n> for nr_unresolved, which is sum of number of ref- and ofs-deltas\n> minus nr_resolved, which may be larger or smaller than the number\n> ref-deltas.  Depending on nr_resolved, this was either under or over\n> allocating.\n\nIt's either that or we could put back \"if (real_type != OBJ_REF_DELTA)\ncontinue;\" in the sorted_by_pos population loop. Resolved deltas can't\nhave real_type == OBJ_REF_DELTA, so if we allocate nr_unresolved, it's\nguaranteed over-allocation, never under-allocation. But I guess your\napproach would make the code easier to read.\n\nI keep tripping over this \"real_type vs type\" in this code. What do\nyou think about renaming \"type\" field to \"in_pack_type\" and\n\"real_type\" to \"canon_type\" (or \"final_type\")? \"Real\" does not really\nsay anything in this context..\n-- \nDuy\n"},{"id":"265735","messageId":"xmqqvbdw3r40.fsf@gitster.dls.corp.google.com","threadId":"39107","inReplyTo":"CACsJy8CsUu1zEnah9Ah3tQxk8N-xPpOBuV5TpQ4EB6+nyiDW3g@mail.gmail.com","subject":"Re: [PATCH] index-pack: fix allocation of sorted_by_pos array","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-07-07T15:49:19Z","receivedAt":"2015-07-07T15:49:19Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen <pclouds@gmail.com> writes:\n\n> I keep tripping over this \"real_type vs type\" in this code. What do\n> you think about renaming \"type\" field to \"in_pack_type\" and\n> \"real_type\" to \"canon_type\" (or \"final_type\")? \"Real\" does not really\n> say anything in this context..\n\nAn unqualified name \"type\" does bother me for the word to express\nwhat representation the piece of data uses (i.e. is it a delta, or\nis it a base object of \"tree\" type, or what).  I think I tried to\nunconfuse myself by saying \"representation type\" in in-code\ncomments, reviews and log messages when it is not clear which kind\nbetween \"in-pack representation\" or \"Git object type of that stored\ndata\" a sentence is talking about, and I agree \"in_pack_type\" would\nbe a vast improvement over just \"type\".\n\nTo me personally real- and final- mean about the same thing\n(i.e. what is the real type of the object that is stored?) in the\ncontext of this codepath.\n\nEspecially, if the other one is renamed with \"in_pack_\" prefix,\n\"real_type\" is not just clear enough but is probably better because\nit explains what it is from its \"meaning\" (i.e. it is the type of\nthe Git object, not how it is represented in the pack-stream) than\n\"final_type\" that is named after \"how\" it is computed (i.e. it makes\nsense to you only if you know that an in-pack type \"this is delta\"\ndoes not have the full information and you have to traverse the\ndelta chain and you will finally find out what it is when you hit\nthe base representation).\n\nThanks.\n"},{"id":"265738","messageId":"20150707160630.GA4456@peff.net","threadId":"39107","inReplyTo":"xmqqvbdw3r40.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] index-pack: fix allocation of sorted_by_pos array","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-07-07T16:06:31Z","receivedAt":"2015-07-07T16:06:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 07, 2015 at 08:49:19AM -0700, Junio C Hamano wrote:\n\n> Duy Nguyen <pclouds@gmail.com> writes:\n> \n> > I keep tripping over this \"real_type vs type\" in this code. What do\n> > you think about renaming \"type\" field to \"in_pack_type\" and\n> > \"real_type\" to \"canon_type\" (or \"final_type\")? \"Real\" does not really\n> > say anything in this context..\n> \n> An unqualified name \"type\" does bother me for the word to express\n> what representation the piece of data uses (i.e. is it a delta, or\n> is it a base object of \"tree\" type, or what).  I think I tried to\n> unconfuse myself by saying \"representation type\" in in-code\n> comments, reviews and log messages when it is not clear which kind\n> between \"in-pack representation\" or \"Git object type of that stored\n> data\" a sentence is talking about, and I agree \"in_pack_type\" would\n> be a vast improvement over just \"type\".\n\nI think this is doubly confusing because pack-objects _does_ use\nin_pack_type. And its \"type\" is therefore the \"real\" object type. Which\nis the opposite of index-pack, which uses \"type\" for the in-pack type.\nSo at the very least, we should harmonize these two uses.\n\n> Especially, if the other one is renamed with \"in_pack_\" prefix,\n> \"real_type\" is not just clear enough but is probably better because\n> it explains what it is from its \"meaning\" (i.e. it is the type of\n> the Git object, not how it is represented in the pack-stream) than\n> \"final_type\" that is named after \"how\" it is computed (i.e. it makes\n> sense to you only if you know that an in-pack type \"this is delta\"\n> does not have the full information and you have to traverse the\n> delta chain and you will finally find out what it is when you hit\n> the base representation).\n\nYeah, I agree real_type is fine when paired with in_pack_type. We might\nconsider modifying pack-objects.h to match (on top of just moving\nindex-pack to in_pack_type).\n\n-Peff\n"},{"id":"265842","messageId":"1436356591-8148-1-git-send-email-pclouds@gmail.com","threadId":"39107","inReplyTo":"20150707160630.GA4456@peff.net","subject":"[PATCH 1/2] index-pack: rename the field \"type\" to \"in_pack_type\"","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2015-07-08T11:56:30Z","receivedAt":"2015-07-08T11:56:30Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"We have two types in this code: in-pack and canonical. \"in_pack_type\"\nmakes it clearer than plain \"type\".\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n builtin/index-pack.c | 42 +++++++++++++++++++++---------------------\n 1 file changed, 21 insertions(+), 21 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 48fa472..797e571 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -19,7 +19,7 @@ struct object_entry {\n \tstruct pack_idx_entry idx;\n \tunsigned long size;\n \tunsigned char hdr_size;\n-\tsigned char type;\n+\tsigned char in_pack_type;\n \tsigned char real_type;\n };\n \n@@ -493,7 +493,7 @@ static void *unpack_raw_entry(struct object_entry *obj,\n \tp = fill(1);\n \tc = *p;\n \tuse(1);\n-\tobj->type = (c >> 4) & 7;\n+\tobj->in_pack_type = (c >> 4) & 7;\n \tsize = (c & 15);\n \tshift = 4;\n \twhile (c & 0x80) {\n@@ -505,7 +505,7 @@ static void *unpack_raw_entry(struct object_entry *obj,\n \t}\n \tobj->size = size;\n \n-\tswitch (obj->type) {\n+\tswitch (obj->in_pack_type) {\n \tcase OBJ_REF_DELTA:\n \t\thashcpy(ref_sha1, fill(20));\n \t\tuse(20);\n@@ -534,11 +534,11 @@ static void *unpack_raw_entry(struct object_entry *obj,\n \tcase OBJ_TAG:\n \t\tbreak;\n \tdefault:\n-\t\tbad_object(obj->idx.offset, _(\"unknown object type %d\"), obj->type);\n+\t\tbad_object(obj->idx.offset, _(\"unknown object type %d\"), obj->in_pack_type);\n \t}\n \tobj->hdr_size = consumed_bytes - obj->idx.offset;\n \n-\tdata = unpack_entry_data(obj->idx.offset, obj->size, obj->type, sha1);\n+\tdata = unpack_entry_data(obj->idx.offset, obj->size, obj->in_pack_type, sha1);\n \tobj->idx.crc32 = input_crc32;\n \treturn data;\n }\n@@ -631,7 +631,7 @@ static int find_ofs_delta(const off_t offset, enum object_type type)\n \t\tint cmp;\n \n \t\tcmp = compare_ofs_delta_bases(offset, delta->offset,\n-\t\t\t\t\t      type, objects[delta->obj_no].type);\n+\t\t\t\t\t      type, objects[delta->obj_no].in_pack_type);\n \t\tif (!cmp)\n \t\t\treturn next;\n \t\tif (cmp < 0) {\n@@ -685,7 +685,7 @@ static int find_ref_delta(const unsigned char *sha1, enum object_type type)\n \t\tint cmp;\n \n \t\tcmp = compare_ref_delta_bases(sha1, delta->sha1,\n-\t\t\t\t\t      type, objects[delta->obj_no].type);\n+\t\t\t\t\t      type, objects[delta->obj_no].in_pack_type);\n \t\tif (!cmp)\n \t\t\treturn next;\n \t\tif (cmp < 0) {\n@@ -759,7 +759,7 @@ static int check_collison(struct object_entry *entry)\n \tenum object_type type;\n \tunsigned long size;\n \n-\tif (entry->size <= big_file_threshold || entry->type != OBJ_BLOB)\n+\tif (entry->size <= big_file_threshold || entry->in_pack_type != OBJ_BLOB)\n \t\treturn -1;\n \n \tmemset(&data, 0, sizeof(data));\n@@ -767,7 +767,7 @@ static int check_collison(struct object_entry *entry)\n \tdata.st = open_istream(entry->idx.sha1, &type, &size, NULL);\n \tif (!data.st)\n \t\treturn -1;\n-\tif (size != entry->size || type != entry->type)\n+\tif (size != entry->size || type != entry->in_pack_type)\n \t\tdie(_(\"SHA1 COLLISION FOUND WITH %s !\"),\n \t\t    sha1_to_hex(entry->idx.sha1));\n \tunpack_data(entry, compare_objects, &data);\n@@ -891,7 +891,7 @@ static void *get_base_data(struct base_data *c)\n \t\tstruct base_data **delta = NULL;\n \t\tint delta_nr = 0, delta_alloc = 0;\n \n-\t\twhile (is_delta_type(c->obj->type) && !c->data) {\n+\t\twhile (is_delta_type(c->obj->in_pack_type) && !c->data) {\n \t\t\tALLOC_GROW(delta, delta_nr + 1, delta_alloc);\n \t\t\tdelta[delta_nr++] = c;\n \t\t\tc = c->base;\n@@ -1085,7 +1085,7 @@ static void *threaded_second_pass(void *data)\n \t\tcounter_unlock();\n \t\twork_lock();\n \t\twhile (nr_dispatched < nr_objects &&\n-\t\t       is_delta_type(objects[nr_dispatched].type))\n+\t\t       is_delta_type(objects[nr_dispatched].in_pack_type))\n \t\t\tnr_dispatched++;\n \t\tif (nr_dispatched >= nr_objects) {\n \t\t\twork_unlock();\n@@ -1121,12 +1121,12 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\tstruct object_entry *obj = &objects[i];\n \t\tvoid *data = unpack_raw_entry(obj, &ofs_delta->offset,\n \t\t\t\t\t      ref_delta_sha1, obj->idx.sha1);\n-\t\tobj->real_type = obj->type;\n-\t\tif (obj->type == OBJ_OFS_DELTA) {\n+\t\tobj->real_type = obj->in_pack_type;\n+\t\tif (obj->in_pack_type == OBJ_OFS_DELTA) {\n \t\t\tnr_ofs_deltas++;\n \t\t\tofs_delta->obj_no = i;\n \t\t\tofs_delta++;\n-\t\t} else if (obj->type == OBJ_REF_DELTA) {\n+\t\t} else if (obj->in_pack_type == OBJ_REF_DELTA) {\n \t\t\tALLOC_GROW(ref_deltas, nr_ref_deltas + 1, ref_deltas_alloc);\n \t\t\thashcpy(ref_deltas[nr_ref_deltas].sha1, ref_delta_sha1);\n \t\t\tref_deltas[nr_ref_deltas].obj_no = i;\n@@ -1136,7 +1136,7 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\t\tobj->real_type = OBJ_BAD;\n \t\t\tnr_delays++;\n \t\t} else\n-\t\t\tsha1_object(data, NULL, obj->size, obj->type, obj->idx.sha1);\n+\t\t\tsha1_object(data, NULL, obj->size, obj->in_pack_type, obj->idx.sha1);\n \t\tfree(data);\n \t\tdisplay_progress(progress, i+1);\n \t}\n@@ -1161,8 +1161,8 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\tstruct object_entry *obj = &objects[i];\n \t\tif (obj->real_type != OBJ_BAD)\n \t\t\tcontinue;\n-\t\tobj->real_type = obj->type;\n-\t\tsha1_object(NULL, obj, obj->size, obj->type, obj->idx.sha1);\n+\t\tobj->real_type = obj->in_pack_type;\n+\t\tsha1_object(NULL, obj, obj->size, obj->in_pack_type, obj->idx.sha1);\n \t\tnr_delays--;\n \t}\n \tif (nr_delays)\n@@ -1215,7 +1215,7 @@ static void resolve_deltas(void)\n \tfor (i = 0; i < nr_objects; i++) {\n \t\tstruct object_entry *obj = &objects[i];\n \n-\t\tif (is_delta_type(obj->type))\n+\t\tif (is_delta_type(obj->in_pack_type))\n \t\t\tcontinue;\n \t\tresolve_base(obj);\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n@@ -1314,7 +1314,7 @@ static struct object_entry *append_obj_to_pack(struct sha1file *f,\n \tsha1write(f, header, n);\n \tobj[0].size = size;\n \tobj[0].hdr_size = n;\n-\tobj[0].type = type;\n+\tobj[0].in_pack_type = type;\n \tobj[0].real_type = type;\n \tobj[1].idx.offset = obj[0].idx.offset + n;\n \tobj[1].idx.offset += write_compressed(f, buf, size);\n@@ -1566,7 +1566,7 @@ static void show_pack_info(int stat_only)\n \tfor (i = 0; i < nr_objects; i++) {\n \t\tstruct object_entry *obj = &objects[i];\n \n-\t\tif (is_delta_type(obj->type))\n+\t\tif (is_delta_type(obj->in_pack_type))\n \t\t\tchain_histogram[obj_stat[i].delta_depth - 1]++;\n \t\tif (stat_only)\n \t\t\tcontinue;\n@@ -1575,7 +1575,7 @@ static void show_pack_info(int stat_only)\n \t\t       typename(obj->real_type), obj->size,\n \t\t       (unsigned long)(obj[1].idx.offset - obj->idx.offset),\n \t\t       (uintmax_t)obj->idx.offset);\n-\t\tif (is_delta_type(obj->type)) {\n+\t\tif (is_delta_type(obj->in_pack_type)) {\n \t\t\tstruct object_entry *bobj = &objects[obj_stat[i].base_object_no];\n \t\t\tprintf(\" %u %s\", obj_stat[i].delta_depth, sha1_to_hex(bobj->idx.sha1));\n \t\t}\n-- \n2.3.0.rc1.137.g477eb31\n"},{"id":"265841","messageId":"1436356591-8148-2-git-send-email-pclouds@gmail.com","threadId":"39107","inReplyTo":"1436356591-8148-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 2/2] pack-objects: rename the field \"type\" to \"real_type\"","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2015-07-08T11:56:31Z","receivedAt":"2015-07-08T11:56:31Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This is to avoid the too generic name \"type\" and harmonize with the\nnaming in index-pack. There's a subtle difference though: real_type in\nindex-pack is what the upper level see, no delta types (after delta\nresolution). But real_type in pack-objects is the type to be written in\nthe pack, delta types are fine (it's actually markers for reused deltas)\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n builtin/pack-objects.c | 36 ++++++++++++++++++------------------\n pack-bitmap-write.c    |  6 +++---\n pack-objects.h         |  2 +-\n 3 files changed, 22 insertions(+), 22 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 80fe8c7..e03bf3e 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -244,7 +244,7 @@ static unsigned long write_no_reuse_object(struct sha1file *f, struct object_ent\n \tstruct git_istream *st = NULL;\n \n \tif (!usable_delta) {\n-\t\tif (entry->type == OBJ_BLOB &&\n+\t\tif (entry->real_type == OBJ_BLOB &&\n \t\t    entry->size > big_file_threshold &&\n \t\t    (st = open_istream(entry->idx.sha1, &type, &size, NULL)) != NULL)\n \t\t\tbuf = NULL;\n@@ -348,7 +348,7 @@ static unsigned long write_reuse_object(struct sha1file *f, struct object_entry\n \tstruct pack_window *w_curs = NULL;\n \tstruct revindex_entry *revidx;\n \toff_t offset;\n-\tenum object_type type = entry->type;\n+\tenum object_type type = entry->real_type;\n \tunsigned long datalen;\n \tunsigned char header[10], dheader[10];\n \tunsigned hdrlen;\n@@ -452,11 +452,11 @@ static unsigned long write_object(struct sha1file *f,\n \t\tto_reuse = 0;\t/* explicit */\n \telse if (!entry->in_pack)\n \t\tto_reuse = 0;\t/* can't reuse what we don't have */\n-\telse if (entry->type == OBJ_REF_DELTA || entry->type == OBJ_OFS_DELTA)\n+\telse if (entry->real_type == OBJ_REF_DELTA || entry->real_type == OBJ_OFS_DELTA)\n \t\t\t\t/* check_object() decided it for us ... */\n \t\tto_reuse = usable_delta;\n \t\t\t\t/* ... but pack split may override that */\n-\telse if (entry->type != entry->in_pack_type)\n+\telse if (entry->real_type != entry->in_pack_type)\n \t\tto_reuse = 0;\t/* pack has delta which is unusable */\n \telse if (entry->delta)\n \t\tto_reuse = 0;\t/* we want to pack afresh */\n@@ -676,8 +676,8 @@ static struct object_entry **compute_write_order(void)\n \t * And then all remaining commits and tags.\n \t */\n \tfor (i = last_untagged; i < to_pack.nr_objects; i++) {\n-\t\tif (objects[i].type != OBJ_COMMIT &&\n-\t\t    objects[i].type != OBJ_TAG)\n+\t\tif (objects[i].real_type != OBJ_COMMIT &&\n+\t\t    objects[i].real_type != OBJ_TAG)\n \t\t\tcontinue;\n \t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n \t}\n@@ -686,7 +686,7 @@ static struct object_entry **compute_write_order(void)\n \t * And then all the trees.\n \t */\n \tfor (i = last_untagged; i < to_pack.nr_objects; i++) {\n-\t\tif (objects[i].type != OBJ_TREE)\n+\t\tif (objects[i].real_type != OBJ_TREE)\n \t\t\tcontinue;\n \t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n \t}\n@@ -994,7 +994,7 @@ static void create_object_entry(const unsigned char *sha1,\n \tentry = packlist_alloc(&to_pack, sha1, index_pos);\n \tentry->hash = hash;\n \tif (type)\n-\t\tentry->type = type;\n+\t\tentry->real_type = type;\n \tif (exclude)\n \t\tentry->preferred_base = 1;\n \telse\n@@ -1355,9 +1355,9 @@ static void check_object(struct object_entry *entry)\n \t\tswitch (entry->in_pack_type) {\n \t\tdefault:\n \t\t\t/* Not a delta hence we've already got all we need. */\n-\t\t\tentry->type = entry->in_pack_type;\n+\t\t\tentry->real_type = entry->in_pack_type;\n \t\t\tentry->in_pack_header_size = used;\n-\t\t\tif (entry->type < OBJ_COMMIT || entry->type > OBJ_BLOB)\n+\t\t\tif (entry->real_type < OBJ_COMMIT || entry->real_type > OBJ_BLOB)\n \t\t\t\tgoto give_up;\n \t\t\tunuse_pack(&w_curs);\n \t\t\treturn;\n@@ -1411,7 +1411,7 @@ static void check_object(struct object_entry *entry)\n \t\t\t * deltify other objects against, in order to avoid\n \t\t\t * circular deltas.\n \t\t\t */\n-\t\t\tentry->type = entry->in_pack_type;\n+\t\t\tentry->real_type = entry->in_pack_type;\n \t\t\tentry->delta = base_entry;\n \t\t\tentry->delta_size = entry->size;\n \t\t\tentry->delta_sibling = base_entry->delta_child;\n@@ -1420,7 +1420,7 @@ static void check_object(struct object_entry *entry)\n \t\t\treturn;\n \t\t}\n \n-\t\tif (entry->type) {\n+\t\tif (entry->real_type) {\n \t\t\t/*\n \t\t\t * This must be a delta and we already know what the\n \t\t\t * final object type is.  Let's extract the actual\n@@ -1443,7 +1443,7 @@ static void check_object(struct object_entry *entry)\n \t\tunuse_pack(&w_curs);\n \t}\n \n-\tentry->type = sha1_object_info(entry->idx.sha1, &entry->size);\n+\tentry->real_type = sha1_object_info(entry->idx.sha1, &entry->size);\n \t/*\n \t * The error condition is checked in prepare_pack().  This is\n \t * to permit a missing preferred base object to be ignored\n@@ -1503,9 +1503,9 @@ static int type_size_sort(const void *_a, const void *_b)\n \tconst struct object_entry *a = *(struct object_entry **)_a;\n \tconst struct object_entry *b = *(struct object_entry **)_b;\n \n-\tif (a->type > b->type)\n+\tif (a->real_type > b->real_type)\n \t\treturn -1;\n-\tif (a->type < b->type)\n+\tif (a->real_type < b->real_type)\n \t\treturn 1;\n \tif (a->hash > b->hash)\n \t\treturn -1;\n@@ -1581,7 +1581,7 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \tvoid *delta_buf;\n \n \t/* Don't bother doing diffs between different types */\n-\tif (trg_entry->type != src_entry->type)\n+\tif (trg_entry->real_type != src_entry->real_type)\n \t\treturn -1;\n \n \t/*\n@@ -2149,11 +2149,11 @@ static void prepare_pack(int window, int depth)\n \n \t\tif (!entry->preferred_base) {\n \t\t\tnr_deltas++;\n-\t\t\tif (entry->type < 0)\n+\t\t\tif (entry->real_type < 0)\n \t\t\t\tdie(\"unable to get type of object %s\",\n \t\t\t\t    sha1_to_hex(entry->idx.sha1));\n \t\t} else {\n-\t\t\tif (entry->type < 0) {\n+\t\t\tif (entry->real_type < 0) {\n \t\t\t\t/*\n \t\t\t\t * This object is not found, but we\n \t\t\t\t * don't have to include it anyway.\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex c05d138..572f4d6 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -64,12 +64,12 @@ void bitmap_writer_build_type_index(struct pack_idx_entry **index,\n \n \t\tentry->in_pack_pos = i;\n \n-\t\tswitch (entry->type) {\n+\t\tswitch (entry->real_type) {\n \t\tcase OBJ_COMMIT:\n \t\tcase OBJ_TREE:\n \t\tcase OBJ_BLOB:\n \t\tcase OBJ_TAG:\n-\t\t\treal_type = entry->type;\n+\t\t\treal_type = entry->real_type;\n \t\t\tbreak;\n \n \t\tdefault:\n@@ -96,7 +96,7 @@ void bitmap_writer_build_type_index(struct pack_idx_entry **index,\n \n \t\tdefault:\n \t\t\tdie(\"Missing type information for %s (%d/%d)\",\n-\t\t\t    sha1_to_hex(entry->idx.sha1), real_type, entry->type);\n+\t\t\t    sha1_to_hex(entry->idx.sha1), real_type, entry->real_type);\n \t\t}\n \t}\n }\ndiff --git a/pack-objects.h b/pack-objects.h\nindex d1b98b3..33cde59 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -14,7 +14,7 @@ struct object_entry {\n \tvoid *delta_data;\t/* cached delta (uncompressed) */\n \tunsigned long delta_size;\t/* delta data size (uncompressed) */\n \tunsigned long z_delta_size;\t/* delta data size (compressed) */\n-\tenum object_type type;\n+\tenum object_type real_type;\n \tenum object_type in_pack_type;\t/* could be delta */\n \tuint32_t hash;\t\t\t/* name hint hash */\n \tunsigned int in_pack_pos;\n-- \n2.3.0.rc1.137.g477eb31\n"},{"id":"265851","messageId":"20150708134713.GA5136@peff.net","threadId":"39107","inReplyTo":"1436356591-8148-2-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH 2/2] pack-objects: rename the field \"type\" to \"real_type\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-07-08T13:47:14Z","receivedAt":"2015-07-08T13:47:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 08, 2015 at 06:56:31PM +0700, Nguyễn Thái Ngọc Duy wrote:\n\n> This is to avoid the too generic name \"type\" and harmonize with the\n> naming in index-pack. There's a subtle difference though: real_type in\n> index-pack is what the upper level see, no delta types (after delta\n> resolution). But real_type in pack-objects is the type to be written in\n> the pack, delta types are fine (it's actually markers for reused deltas)\n\nHrm, now I'm confused about whether this change is a good idea.\n\nThe definition of in_pack_type says:\n\n>  \tenum object_type in_pack_type;\t/* could be delta */\n\nso now I am confused about what exactly \"type\" (and now \"real_type\")\nmeans.\n\n-Peff\n"},{"id":"265853","messageId":"CACsJy8B0OCu3-TKVztj+wCmtqXdeh6iNK5ir4Xi2BXWW14wdOQ@mail.gmail.com","threadId":"39107","inReplyTo":"20150708134713.GA5136@peff.net","subject":"Re: [PATCH 2/2] pack-objects: rename the field \"type\" to \"real_type\"","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2015-07-08T13:57:35Z","receivedAt":"2015-07-08T13:57:35Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Jul 8, 2015 at 8:47 PM, Jeff King <peff@peff.net> wrote:\n> On Wed, Jul 08, 2015 at 06:56:31PM +0700, Nguyễn Thái Ngọc Duy wrote:\n>\n>> This is to avoid the too generic name \"type\" and harmonize with the\n>> naming in index-pack. There's a subtle difference though: real_type in\n>> index-pack is what the upper level see, no delta types (after delta\n>> resolution). But real_type in pack-objects is the type to be written in\n>> the pack, delta types are fine (it's actually markers for reused deltas)\n>\n> Hrm, now I'm confused about whether this change is a good idea.\n\nOh good :) I found it not-so-good too after seeing the check \"if\n(real_type == OBJ_REF...)\"\n\n> The definition of in_pack_type says:\n>\n>>       enum object_type in_pack_type;  /* could be delta */\n>\n> so now I am confused about what exactly \"type\" (and now \"real_type\")\n> means.\n\nI think we just overload \"type\" with \"this delta is detected reusable\nalready\" in write_object(). It only means 'real type in the output\npack' for canonical types. For generated deltas, we already know if\nit's ref-delta or ofs-delta, we don't rely on real_type\n-- \nDuy\n"},{"id":"265855","messageId":"20150708141110.GA5555@peff.net","threadId":"39107","inReplyTo":"CACsJy8B0OCu3-TKVztj+wCmtqXdeh6iNK5ir4Xi2BXWW14wdOQ@mail.gmail.com","subject":"Re: [PATCH 2/2] pack-objects: rename the field \"type\" to \"real_type\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-07-08T14:11:11Z","receivedAt":"2015-07-08T14:11:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 08, 2015 at 08:57:35PM +0700, Duy Nguyen wrote:\n\n> > The definition of in_pack_type says:\n> >\n> >>       enum object_type in_pack_type;  /* could be delta */\n> >\n> > so now I am confused about what exactly \"type\" (and now \"real_type\")\n> > means.\n> \n> I think we just overload \"type\" with \"this delta is detected reusable\n> already\" in write_object(). It only means 'real type in the output\n> pack' for canonical types. For generated deltas, we already know if\n> it's ref-delta or ofs-delta, we don't rely on real_type\n\nAh. I think I'd be inclined to just leave it as \"type\" then.\n\n-Peff\n"}]}