{"thread":{"id":"54125","subject":"[PATCH 0/7] Better threaded delta resolution in index-pack (another try)","startedAt":"2020-08-24T19:16:59Z","lastAt":"2020-09-08T22:53:44Z","messageCount":28,"participants":["Jonathan Tan","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":7},"messages":[{"id":"404356","messageId":"cover.1598296530.git.jonathantanmy@google.com","threadId":"54125","inReplyTo":null,"subject":"[PATCH 0/7] Better threaded delta resolution in index-pack (another try)","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-08-24T19:16:30Z","receivedAt":"2020-08-24T19:16:59Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"I'm trying to resurrect [1] and have rebased it to latest master\n(675a4aaf3b (\"Ninth batch\", 2020-08-19)).\n\nPeff said [2] (of v1) that the overall direction seems reasonable and\nJosh Steadmon said [3] (of v2) that it looks mostly good except for\npossible improvements to commit messages and comments. Josh did not list\nout specific improvements to commit messages but I have taken his\nsuggestions for comments.\n\n[1] https://lore.kernel.org/git/cover.1571343096.git.jonathantanmy@google.com/\n[2] https://lore.kernel.org/git/20191017063554.GG10862@sigill.intra.peff.net/\n[3] https://lore.kernel.org/git/20200228000350.GB12115@google.com/\n\nJonathan Tan (7):\n Documentation: deltaBaseCacheLimit is per-thread\n index-pack: remove redundant parameter\n index-pack: unify threaded and unthreaded code\n index-pack: remove redundant child field\n index-pack: calculate {ref,ofs}_{first,last} early\n index-pack: make resolve_delta() assume base data\n index-pack: make quantum of work smaller\n\n Documentation/config/core.txt | 2 +-\n builtin/index-pack.c | 449 ++++++++++++++++++----------------\n 2 files changed, 244 insertions(+), 207 deletions(-)\n\n-- \n2.28.0.297.g1956fa8f8d-goog\n\n"},{"id":"404357","messageId":"2a1caac85a6fe4812aea246e6e467c0d25dcbb1c.1598296530.git.jonathantanmy@google.com","threadId":"54125","inReplyTo":"cover.1598296530.git.jonathantanmy@google.com","subject":"[PATCH 1/7] Documentation: deltaBaseCacheLimit is per-thread","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-08-24T19:16:31Z","receivedAt":"2020-08-24T19:17:04Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Clarify that core.deltaBaseCacheLimit is per-thread, as can be seen from\nthe fact that cache usage (base_cache_used in struct thread_local in\nbuiltin/index-pack.c) is tracked individually for each thread and\ncompared against delta_base_cache_limit.\n\nSigned-off-by: Jonathan Tan \n---\n Documentation/config/core.txt | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/Documentation/config/core.txt b/Documentation/config/core.txt\nindex 74619a9c03..02002cf109 100644\n--- a/Documentation/config/core.txt\n+++ b/Documentation/config/core.txt\n@@ -399,7 +399,7 @@ the largest projects. You probably do not need to adjust this value.\n Common unit suffixes of 'k', 'm', or 'g' are supported.\n \n core.deltaBaseCacheLimit::\n-\tMaximum number of bytes to reserve for caching base objects\n+\tMaximum number of bytes per thread to reserve for caching base objects\n \tthat may be referenced by multiple deltified objects. By storing the\n \tentire decompressed base objects in a cache Git is able\n \tto avoid unpacking and decompressing frequently used base\n-- \n2.28.0.297.g1956fa8f8d-goog\n\n"},{"id":"404358","messageId":"20200824191656.3870231-1-jonathantanmy@google.com","threadId":"54125","inReplyTo":"cover.1598296530.git.jonathantanmy@google.com","subject":"[PATCH] fetch-pack: in partial clone, pass --promisor","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-08-24T19:16:32Z","receivedAt":"2020-08-24T19:17:06Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"When fetching a pack from a promisor remote, the corresponding .promisor\nfile needs to be created. \"fetch-pack\" originally did this by passing\n\"--promisor\" to \"index-pack\", but in 5374a290aa (\"fetch-pack: write\nfetched refs to .promisor\", 2019-10-16), \"fetch-pack\" was taught to do\nthis itself instead, because it needed to store ref information in the\n.promisor file.\n\nThis causes a problem with superprojects when transfer.fsckobjects is\nset, because in the current implementation, it is \"index-pack\" that\ncalls fsck_finish() to check the objects; before 5374a290aa,\nfsck_finish() would see that .gitmodules is a promisor object and\ntolerate it being missing, but after, there is no .promisor file (at the\ntime of the invocation of fsck_finish() by \"index-pack\") to tell it that\n.gitmodules is a promisor object, so it returns an error.\n\nTherefore, teach \"fetch-pack\" to pass \"--promisor\" to index pack once\nagain. \"fetch-pack\" will subsequently overwrite this file with the ref\ninformation.\n\nAn alternative is to instead move object checking to \"fetch-pack\", and\nlet \"index-pack\" only index the files. However, since \"index-pack\" has\nto inflate objects in order to index them, it seems reasonable to also\nlet it check the objects (which also require inflated files).\n\nSigned-off-by: Jonathan Tan \n---\n fetch-pack.c | 17 ++++++++++-------\n t/t5616-partial-clone.sh | 16 ++++++++++++++++\n 2 files changed, 26 insertions(+), 7 deletions(-)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 7f20eca4f8..d467edc24e 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -866,13 +866,16 @@ static int get_pack(struct fetch_pack_args *args,\n \t\t\t * have this responsibility.\n \t\t\t */\n \t\t\targs->check_self_contained_and_connected = 0;\n-\t\t/*\n-\t\t * If we're obtaining the filename of a lockfile, we'll use\n-\t\t * that filename to write a .promisor file with more\n-\t\t * information below. If not, we need index-pack to do it for\n-\t\t * us.\n-\t\t */\n-\t\tif (!(do_keep && pack_lockfiles) && args->from_promisor)\n+\n+\t\tif (args->from_promisor)\n+\t\t\t/*\n+\t\t\t * write_promisor_file() may be called afterwards but\n+\t\t\t * we still need index-pack to know that this is a\n+\t\t\t * promisor pack. For example, if transfer.fsckobjects\n+\t\t\t * is true, index-pack needs to know that .gitmodules\n+\t\t\t * is a promisor object (so that it won't complain if\n+\t\t\t * it is missing).\n+\t\t\t */\n \t\t\tstrvec_push(&cmd.args, \"--promisor\");\n \t}\n \telse {\ndiff --git a/t/t5616-partial-clone.sh b/t/t5616-partial-clone.sh\nindex 8827c2ed18..5a01466db4 100755\n--- a/t/t5616-partial-clone.sh\n+++ b/t/t5616-partial-clone.sh\n@@ -163,6 +163,22 @@ test_expect_success 'manual prefetch of missing objects' '\n \ttest_line_count = 0 observed.oids\n '\n \n+test_expect_success 'partial clone with transfer.fsckobjects=1 works with submodules' '\n+\ttest_create_repo submodule &&\n+\ttest_commit -C submodule mycommit &&\n+\n+\ttest_create_repo src_with_sub &&\n+\ttest_config -C src_with_sub uploadpack.allowfilter 1 &&\n+\ttest_config -C src_with_sub uploadpack.allowanysha1inwant 1 &&\n+\n+\tgit -C src_with_sub submodule add \"file://$(pwd)/submodule\" mysub &&\n+\tgit -C src_with_sub commit -m \"commit with submodule\" &&\n+\n+\tgit -c transfer.fsckobjects=1 \\\n+\t\tclone --filter=\"blob:none\" \"file://$(pwd)/src_with_sub\" dst &&\n+\ttest_when_finished rm -rf dst\n+'\n+\n test_expect_success 'partial clone with transfer.fsckobjects=1 uses index-pack --fsck-objects' '\n \tgit init src &&\n \ttest_commit -C src x &&\n-- \n2.28.0.297.g1956fa8f8d-goog\n\n"},{"id":"404359","messageId":"648ec34821bd435468a0917167bdeef7ca101c02.1598296530.git.jonathantanmy@google.com","threadId":"54125","inReplyTo":"cover.1598296530.git.jonathantanmy@google.com","subject":"[PATCH 2/7] index-pack: remove redundant parameter","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-08-24T19:16:33Z","receivedAt":"2020-08-24T19:17:12Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"find_{ref,ofs}_delta_{,children} take an enum object_type parameter, but\nthe object type is already present in the name of the function. Remove\nthat parameter from these functions.\n\nSigned-off-by: Jonathan Tan \n---\n builtin/index-pack.c | 26 ++++++++++++--------------\n 1 file changed, 12 insertions(+), 14 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex f865666db9..a8444d550b 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -614,7 +614,7 @@ static int compare_ofs_delta_bases(off_t offset1, off_t offset2,\n \t 0;\n }\n \n-static int find_ofs_delta(const off_t offset, enum object_type type)\n+static int find_ofs_delta(const off_t offset)\n {\n \tint first = 0, last = nr_ofs_deltas;\n \n@@ -624,7 +624,8 @@ 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 OBJ_OFS_DELTA,\n+\t\t\t\t\t objects[delta->obj_no].type);\n \t\tif (!cmp)\n \t\t\treturn next;\n \t\tif (cmp < 0) {\n@@ -637,10 +638,9 @@ static int find_ofs_delta(const off_t offset, enum object_type type)\n }\n \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+\t\t\t\t int *first_index, int *last_index)\n {\n-\tint first = find_ofs_delta(offset, type);\n+\tint first = find_ofs_delta(offset);\n \tint last = first;\n \tint end = nr_ofs_deltas - 1;\n \n@@ -668,7 +668,7 @@ static int compare_ref_delta_bases(const struct object_id *oid1,\n \treturn oidcmp(oid1, oid2);\n }\n \n-static int find_ref_delta(const struct object_id *oid, enum object_type type)\n+static int find_ref_delta(const struct object_id *oid)\n {\n \tint first = 0, last = nr_ref_deltas;\n \n@@ -678,7 +678,8 @@ static int find_ref_delta(const struct object_id *oid, enum object_type type)\n \t\tint cmp;\n \n \t\tcmp = compare_ref_delta_bases(oid, &delta->oid,\n-\t\t\t\t\t type, objects[delta->obj_no].type);\n+\t\t\t\t\t OBJ_REF_DELTA,\n+\t\t\t\t\t objects[delta->obj_no].type);\n \t\tif (!cmp)\n \t\t\treturn next;\n \t\tif (cmp < 0) {\n@@ -691,10 +692,9 @@ static int find_ref_delta(const struct object_id *oid, enum object_type type)\n }\n \n static void find_ref_delta_children(const struct object_id *oid,\n-\t\t\t\t int *first_index, int *last_index,\n-\t\t\t\t enum object_type type)\n+\t\t\t\t int *first_index, int *last_index)\n {\n-\tint first = find_ref_delta(oid, type);\n+\tint first = find_ref_delta(oid);\n \tint last = first;\n \tint end = nr_ref_deltas - 1;\n \n@@ -983,12 +983,10 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n {\n \tif (base->ref_last == -1 && base->ofs_last == -1) {\n \t\tfind_ref_delta_children(&base->obj->idx.oid,\n-\t\t\t\t\t&base->ref_first, &base->ref_last,\n-\t\t\t\t\tOBJ_REF_DELTA);\n+\t\t\t\t\t&base->ref_first, &base->ref_last);\n \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+\t\t\t\t\t&base->ofs_first, &base->ofs_last);\n \n \t\tif (base->ref_last == -1 && base->ofs_last == -1) {\n \t\t\tfree(base->data);\n-- \n2.28.0.297.g1956fa8f8d-goog\n\n"},{"id":"404360","messageId":"2e7baaabf0ad9d724f5a81495213f4626b8c04ab.1598296530.git.jonathantanmy@google.com","threadId":"54125","inReplyTo":"cover.1598296530.git.jonathantanmy@google.com","subject":"[PATCH 3/7] index-pack: unify threaded and unthreaded code","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-08-24T19:16:34Z","receivedAt":"2020-08-24T19:17:15Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Signed-off-by: Jonathan Tan \n---\n builtin/index-pack.c | 10 +---------\n 1 file changed, 1 insertion(+), 9 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex a8444d550b..357e03b5aa 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1211,15 +1211,7 @@ static void resolve_deltas(void)\n \t\tcleanup_thread();\n \t\treturn;\n \t}\n-\n-\tfor (i = 0; i < nr_objects; i++) {\n-\t\tstruct object_entry *obj = &objects[i];\n-\n-\t\tif (is_delta_type(obj->type))\n-\t\t\tcontinue;\n-\t\tresolve_base(obj);\n-\t\tdisplay_progress(progress, nr_resolved_deltas);\n-\t}\n+\tthreaded_second_pass(¬hread_data);\n }\n \n /*\n-- \n2.28.0.297.g1956fa8f8d-goog\n\n"},{"id":"404361","messageId":"91459ab4119a33d40d39a565c96282db7865c946.1598296530.git.jonathantanmy@google.com","threadId":"54125","inReplyTo":"cover.1598296530.git.jonathantanmy@google.com","subject":"[PATCH 5/7] index-pack: calculate {ref,ofs}_{first,last} early","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-08-24T19:16:36Z","receivedAt":"2020-08-24T19:17:17Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"This is refactoring 2 of 2 to simplify struct base_data.\n\nWhenever we make a struct base_data, immediately calculate its delta\nchildren. This eliminates confusion as to when the\n{ref,ofs}_{first,last} fields are initialized.\n\nBefore this patch, the delta children were calculated at the last\npossible moment. This allowed the members of struct base_data to be\npopulated in any order, superficially useful when we have the object\ncontents before the struct object_entry. But this makes reasoning about\nthe state of struct base_data more complicated, hence this patch.\n\nSigned-off-by: Jonathan Tan \n---\n builtin/index-pack.c | 123 +++++++++++++++++++++----------------------\n 1 file changed, 60 insertions(+), 63 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 032716553c..e98b11ab37 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -33,12 +33,15 @@ struct object_stat {\n };\n \n struct base_data {\n+\t/* Initialized by make_base(). */\n \tstruct base_data *base;\n \tstruct object_entry *obj;\n-\tvoid *data;\n-\tunsigned long size;\n \tint ref_first, ref_last;\n \tint ofs_first, ofs_last;\n+\n+\t/* Not initialized by make_base(). */\n+\tvoid *data;\n+\tunsigned long size;\n };\n \n struct thread_local {\n@@ -362,14 +365,6 @@ static void set_thread_data(struct thread_local *data)\n \t\tpthread_setspecific(key, data);\n }\n \n-static struct base_data *alloc_base_data(void)\n-{\n-\tstruct base_data *base = xcalloc(1, sizeof(struct base_data));\n-\tbase->ref_last = -1;\n-\tbase->ofs_last = -1;\n-\treturn base;\n-}\n-\n static void free_base_data(struct base_data *c)\n {\n \tif (c->data) {\n@@ -406,19 +401,6 @@ static void prune_base_data(struct base_data *youngest_child)\n \tfree(ancestry);\n }\n \n-static void link_base_data(struct base_data *base, struct base_data *c)\n-{\n-\tc->base = base;\n-\tif (c->data)\n-\t\tget_thread_data()->base_cache_used += c->size;\n-\tprune_base_data(c);\n-}\n-\n-static void unlink_base_data(struct base_data *c)\n-{\n-\tfree_base_data(c);\n-}\n-\n static int is_delta_type(enum object_type type)\n {\n \treturn (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA);\n@@ -929,10 +911,25 @@ static void *get_base_data(struct base_data *c)\n \treturn c->data;\n }\n \n-static void resolve_delta(struct object_entry *delta_obj,\n-\t\t\t struct base_data *base, struct base_data *result)\n+static struct base_data *make_base(struct object_entry *obj,\n+\t\t\t\t struct base_data *parent)\n {\n-\tvoid *base_data, *delta_data;\n+\tstruct base_data *base = xcalloc(1, sizeof(struct base_data));\n+\tbase->base = parent;\n+\tbase->obj = obj;\n+\tfind_ref_delta_children(&obj->idx.oid,\n+\t\t\t\t&base->ref_first, &base->ref_last);\n+\tfind_ofs_delta_children(obj->idx.offset,\n+\t\t\t\t&base->ofs_first, &base->ofs_last);\n+\treturn base;\n+}\n+\n+static struct base_data *resolve_delta(struct object_entry *delta_obj,\n+\t\t\t\t struct base_data *base)\n+{\n+\tvoid *base_data, *delta_data, *result_data;\n+\tstruct base_data *result;\n+\tunsigned long result_size;\n \n \tif (show_stat) {\n \t\tint i = delta_obj - objects;\n@@ -946,19 +943,31 @@ static void resolve_delta(struct object_entry *delta_obj,\n \t}\n \tdelta_data = get_data_from_pack(delta_obj);\n \tbase_data = get_base_data(base);\n-\tresult->obj = delta_obj;\n-\tresult->data = patch_delta(base_data, base->size,\n-\t\t\t\t delta_data, delta_obj->size, &result->size);\n+\tresult_data = patch_delta(base_data, base->size,\n+\t\t\t\t delta_data, delta_obj->size, &result_size);\n \tfree(delta_data);\n-\tif (!result->data)\n+\tif (!result_data)\n \t\tbad_object(delta_obj->idx.offset, _(\"failed to apply delta\"));\n-\thash_object_file(the_hash_algo, result->data, result->size,\n+\thash_object_file(the_hash_algo, result_data, result_size,\n \t\t\t type_name(delta_obj->real_type), &delta_obj->idx.oid);\n-\tsha1_object(result->data, NULL, result->size, delta_obj->real_type,\n+\tsha1_object(result_data, NULL, result_size, delta_obj->real_type,\n \t\t &delta_obj->idx.oid);\n+\n+\tresult = make_base(delta_obj, base);\n+\tif (result->ref_last == -1 && result->ofs_last == -1) {\n+\t\tfree(result_data);\n+\t} else {\n+\t\tresult->data = result_data;\n+\t\tresult->size = result_size;\n+\t\tget_thread_data()->base_cache_used += result->size;\n+\t\tprune_base_data(result);\n+\t}\n+\n \tcounter_lock();\n \tnr_resolved_deltas++;\n \tcounter_unlock();\n+\n+\treturn result;\n }\n \n /*\n@@ -984,24 +993,9 @@ static int compare_and_swap_type(signed char *type,\n 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\tfind_ref_delta_children(&base->obj->idx.oid,\n-\t\t\t\t\t&base->ref_first, &base->ref_last);\n-\n-\t\tfind_ofs_delta_children(base->obj->idx.offset,\n-\t\t\t\t\t&base->ofs_first, &base->ofs_last);\n-\n-\t\tif (base->ref_last == -1 && base->ofs_last == -1) {\n-\t\t\tfree(base->data);\n-\t\t\treturn NULL;\n-\t\t}\n-\n-\t\tlink_base_data(prev_base, base);\n-\t}\n-\n \tif (base->ref_first <= base->ref_last) {\n \t\tstruct object_entry *child = objects + ref_deltas[base->ref_first].obj_no;\n-\t\tstruct base_data *result = alloc_base_data();\n+\t\tstruct base_data *result;\n \n \t\tif (!compare_and_swap_type(&child->real_type, OBJ_REF_DELTA,\n \t\t\t\t\t base->obj->real_type))\n@@ -1009,7 +1003,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t\t\t (uintmax_t)child->idx.offset,\n \t\t\t oid_to_hex(&base->obj->idx.oid));\n \n-\t\tresolve_delta(child, base, result);\n+\t\tresult = resolve_delta(child, base);\n \t\tif (base->ref_first == base->ref_last && base->ofs_last == -1)\n \t\t\tfree_base_data(base);\n \n@@ -1019,11 +1013,11 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \n \tif (base->ofs_first <= base->ofs_last) {\n \t\tstruct object_entry *child = objects + ofs_deltas[base->ofs_first].obj_no;\n-\t\tstruct base_data *result = alloc_base_data();\n+\t\tstruct base_data *result;\n \n \t\tassert(child->real_type == OBJ_OFS_DELTA);\n \t\tchild->real_type = base->obj->real_type;\n-\t\tresolve_delta(child, base, result);\n+\t\tresult = resolve_delta(child, base);\n \t\tif (base->ofs_first == base->ofs_last)\n \t\t\tfree_base_data(base);\n \n@@ -1031,7 +1025,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t\treturn result;\n \t}\n \n-\tunlink_base_data(base);\n+\tfree_base_data(base);\n \treturn NULL;\n }\n \n@@ -1074,9 +1068,8 @@ static int compare_ref_delta_entry(const void *a, const void *b)\n \n static void resolve_base(struct object_entry *obj)\n {\n-\tstruct base_data *base_obj = alloc_base_data();\n-\tbase_obj->obj = obj;\n-\tbase_obj->data = NULL;\n+\tstruct base_data *base_obj = make_base(obj, NULL);\n+\n \tfind_unresolved_deltas(base_obj);\n }\n \n@@ -1369,22 +1362,26 @@ static void fix_unresolved_deltas(struct hashfile *f)\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+\t\tstruct base_data *base;\n+\t\tvoid *data;\n+\t\tunsigned long size;\n+\t\tstruct object_entry *obj;\n \n \t\tif (objects[d->obj_no].real_type != OBJ_REF_DELTA)\n \t\t\tcontinue;\n-\t\tbase_obj->data = read_object_file(&d->oid, &type,\n-\t\t\t\t\t\t &base_obj->size);\n-\t\tif (!base_obj->data)\n+\t\tdata = read_object_file(&d->oid, &type, &size);\n+\t\tif (!data)\n \t\t\tcontinue;\n \n \t\tif (check_object_signature(the_repository, &d->oid,\n-\t\t\t\t\t base_obj->data, base_obj->size,\n+\t\t\t\t\t data, size,\n \t\t\t\t\t type_name(type)))\n \t\t\tdie(_(\"local object %s is corrupt\"), oid_to_hex(&d->oid));\n-\t\tbase_obj->obj = append_obj_to_pack(f, d->oid.hash,\n-\t\t\t\t\tbase_obj->data, base_obj->size, type);\n-\t\tfind_unresolved_deltas(base_obj);\n+\t\tobj = append_obj_to_pack(f, d->oid.hash, data, size, type);\n+\t\tbase = make_base(obj, NULL);\n+\t\tbase->data = data;\n+\t\tbase->size = size;\n+\t\tfind_unresolved_deltas(base);\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n \t}\n \tfree(sorted_by_pos);\n-- \n2.28.0.297.g1956fa8f8d-goog\n\n"},{"id":"404362","messageId":"3e69f41f19535fa2c04fae6adc78bcc4f052d523.1598296530.git.jonathantanmy@google.com","threadId":"54125","inReplyTo":"cover.1598296530.git.jonathantanmy@google.com","subject":"[PATCH 7/7] index-pack: make quantum of work smaller","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-08-24T19:16:38Z","receivedAt":"2020-08-24T19:17:20Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Currently, when index-pack resolves deltas, it does not split up delta\ntrees into threads: each delta base root (an object that is not a\nREF_DELTA or OFS_DELTA) can go into its own thread, but all deltas on\nthat root (direct or indirect) are processed in the same thread.\n\nThis is a problem when a repository contains a large text file (thus,\ndelta-able) that is modified many times - delta resolution time during\nfetching is dominated by processing the deltas corresponding to that\ntext file.\n\nThis patch contains a solution to that. When cloning using\n\n git -c core.deltabasecachelimit=1g clone \\\n https://fuchsia.googlesource.com/third_party/vulkan-cts\n\non my laptop, clone time improved from 3m2s to 2m5s (using 3 threads,\nwhich is the default).\n\nThe solution is to have a global work stack. This stack contains delta\nbases (objects, whether appearing directly in the packfile or generated\nby delta resolution, that themselves have delta children) that need to\nbe processed; whenever a thread needs work, it peeks at the top of the\nstack and processes its next unprocessed child. If a thread finds the\nstack empty, it will look for more delta base roots to push on the stack\ninstead.\n\nThe main weakness of having a global work stack is that more time is\nspent in the mutex, but profiling has shown that most time is spent in\nthe resolution of the deltas themselves, so this shouldn't be an issue\nin practice. In any case, experimentation (as described in the clone\ncommand above) shows that this patch is a net improvement.\n\nSigned-off-by: Jonathan Tan \n---\n builtin/index-pack.c | 341 ++++++++++++++++++++++++-------------------\n 1 file changed, 193 insertions(+), 148 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex c6d2acc13a..0a5b938e1e 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -38,15 +38,49 @@ struct base_data {\n \tstruct object_entry *obj;\n \tint ref_first, ref_last;\n \tint ofs_first, ofs_last;\n+\t/*\n+\t * Threads should increment retain_data if they are about to call\n+\t * patch_delta() using this struct's data as a base, and decrement this\n+\t * when they are done. While retain_data is nonzero, this struct's data\n+\t * will not be freed even if the delta base cache limit is exceeded.\n+\t */\n+\tint retain_data;\n+\t/*\n+\t * The number of direct children that have not been fully processed\n+\t * (entered work_head, entered done_head, left done_head). When this\n+\t * number reaches zero, this struct base_data can be freed.\n+\t */\n+\tint children_remaining;\n \n \t/* Not initialized by make_base(). */\n+\tstruct list_head list;\n \tvoid *data;\n \tunsigned long size;\n };\n \n+/*\n+ * Stack of struct base_data that have unprocessed children.\n+ * threaded_second_pass() uses this as a source of work (the other being the\n+ * objects array).\n+ */\n+LIST_HEAD(work_head);\n+\n+/*\n+ * Stack of struct base_data that have children, all of whom have been\n+ * processed or are being processed, and at least one child is being processed.\n+ * These struct base_data must be kept around until the last child is\n+ * processed.\n+ */\n+LIST_HEAD(done_head);\n+\n+/*\n+ * All threads share one delta base cache.\n+ */\n+size_t base_cache_used;\n+size_t base_cache_limit;\n+\n struct thread_local {\n \tpthread_t thread;\n-\tsize_t base_cache_used;\n \tint pack_fd;\n };\n \n@@ -369,36 +403,38 @@ static void free_base_data(struct base_data *c)\n {\n \tif (c->data) {\n \t\tFREE_AND_NULL(c->data);\n-\t\tget_thread_data()->base_cache_used -= c->size;\n+\t\tbase_cache_used -= c->size;\n \t}\n }\n \n-static void prune_base_data(struct base_data *youngest_child)\n+static void prune_base_data(struct base_data *retain)\n {\n-\tstruct base_data *b;\n-\tstruct thread_local *data = get_thread_data();\n-\tstruct base_data **ancestry = NULL;\n-\tsize_t nr = 0, alloc = 0;\n-\tssize_t i;\n+\tstruct list_head *pos;\n \n-\tif (data->base_cache_used <= delta_base_cache_limit)\n+\tif (base_cache_used <= base_cache_limit)\n \t\treturn;\n \n-\t/*\n-\t * Free all ancestors of youngest_child until we have enough space,\n-\t * starting with the oldest. (We cannot free youngest_child itself.)\n-\t */\n-\tfor (b = youngest_child->base; b != NULL; b = b->base) {\n-\t\tALLOC_GROW(ancestry, nr + 1, alloc);\n-\t\tancestry[nr++] = b;\n+\tlist_for_each_prev(pos, &done_head) {\n+\t\tstruct base_data *b = list_entry(pos, struct base_data, list);\n+\t\tif (b->retain_data || b == retain)\n+\t\t\tcontinue;\n+\t\tif (b->data) {\n+\t\t\tfree_base_data(b);\n+\t\t\tif (base_cache_used <= base_cache_limit)\n+\t\t\t\treturn;\n+\t\t}\n \t}\n-\tfor (i = nr - 1;\n-\t i >= 0 && data->base_cache_used > delta_base_cache_limit;\n-\t i--) {\n-\t\tif (ancestry[i]->data)\n-\t\t\tfree_base_data(ancestry[i]);\n+\n+\tlist_for_each_prev(pos, &work_head) {\n+\t\tstruct base_data *b = list_entry(pos, struct base_data, list);\n+\t\tif (b->retain_data || b == retain)\n+\t\t\tcontinue;\n+\t\tif (b->data) {\n+\t\t\tfree_base_data(b);\n+\t\t\tif (base_cache_used <= base_cache_limit)\n+\t\t\t\treturn;\n+\t\t}\n \t}\n-\tfree(ancestry);\n }\n \n static int is_delta_type(enum object_type type)\n@@ -851,15 +887,7 @@ static void sha1_object(const void *data, struct object_entry *obj_entry,\n }\n \n /*\n- * This function is part of find_unresolved_deltas(). There are two\n- * walkers going in the opposite ways.\n- *\n- * The first one in find_unresolved_deltas() traverses down from\n- * parent node to children, deflating nodes along the way. However,\n- * memory for deflated nodes is limited by delta_base_cache_limit, so\n- * at some point parent node's deflated content may be freed.\n- *\n- * The second walker is this function, which goes from current node up\n+ * Walk from current node up\n * to top parent if necessary to deflate the node. In normal\n * situation, its parent node would be already deflated, so it just\n * needs to apply delta.\n@@ -887,7 +915,7 @@ static void *get_base_data(struct base_data *c)\n \t\tif (!delta_nr) {\n \t\t\tc->data = get_data_from_pack(obj);\n \t\t\tc->size = obj->size;\n-\t\t\tget_thread_data()->base_cache_used += c->size;\n+\t\t\tbase_cache_used += c->size;\n \t\t\tprune_base_data(c);\n \t\t}\n \t\tfor (; delta_nr > 0; delta_nr--) {\n@@ -903,7 +931,7 @@ static void *get_base_data(struct base_data *c)\n \t\t\tfree(raw);\n \t\t\tif (!c->data)\n \t\t\t\tbad_object(obj->idx.offset, _(\"failed to apply delta\"));\n-\t\t\tget_thread_data()->base_cache_used += c->size;\n+\t\t\tbase_cache_used += c->size;\n \t\t\tprune_base_data(c);\n \t\t}\n \t\tfree(delta);\n@@ -921,6 +949,8 @@ static struct base_data *make_base(struct object_entry *obj,\n \t\t\t\t&base->ref_first, &base->ref_last);\n \tfind_ofs_delta_children(obj->idx.offset,\n \t\t\t\t&base->ofs_first, &base->ofs_last);\n+\tbase->children_remaining = base->ref_last - base->ref_first +\n+\t\tbase->ofs_last - base->ofs_first + 2;\n \treturn base;\n }\n \n@@ -954,14 +984,8 @@ static struct base_data *resolve_delta(struct object_entry *delta_obj,\n \t\t &delta_obj->idx.oid);\n \n \tresult = make_base(delta_obj, base);\n-\tif (result->ref_last == -1 && result->ofs_last == -1) {\n-\t\tfree(result_data);\n-\t} else {\n-\t\tresult->data = result_data;\n-\t\tresult->size = result_size;\n-\t\tget_thread_data()->base_cache_used += result->size;\n-\t\tprune_base_data(result);\n-\t}\n+\tresult->data = result_data;\n+\tresult->size = result_size;\n \n \tcounter_lock();\n \tnr_resolved_deltas++;\n@@ -970,86 +994,6 @@ static struct base_data *resolve_delta(struct object_entry *delta_obj,\n \treturn result;\n }\n \n-/*\n- * Standard boolean compare-and-swap: atomically check whether \"*type\" is\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(signed char *type,\n-\t\t\t\t enum object_type want,\n-\t\t\t\t enum object_type set)\n-{\n-\tenum object_type old;\n-\n-\ttype_cas_lock();\n-\told = *type;\n-\tif (old == want)\n-\t\t*type = set;\n-\ttype_cas_unlock();\n-\n-\treturn old == want;\n-}\n-\n-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_first <= base->ref_last) {\n-\t\tstruct object_entry *child = objects + ref_deltas[base->ref_first].obj_no;\n-\t\tstruct base_data *result;\n-\n-\t\tif (!compare_and_swap_type(&child->real_type, OBJ_REF_DELTA,\n-\t\t\t\t\t base->obj->real_type))\n-\t\t\tdie(\"REF_DELTA at offset %\"PRIuMAX\" already resolved (duplicate base %s?)\",\n-\t\t\t (uintmax_t)child->idx.offset,\n-\t\t\t oid_to_hex(&base->obj->idx.oid));\n-\n-\t\tget_base_data(base);\n-\t\tresult = resolve_delta(child, base);\n-\t\tif (base->ref_first == base->ref_last && base->ofs_last == -1)\n-\t\t\tfree_base_data(base);\n-\n-\t\tbase->ref_first++;\n-\t\treturn result;\n-\t}\n-\n-\tif (base->ofs_first <= base->ofs_last) {\n-\t\tstruct object_entry *child = objects + ofs_deltas[base->ofs_first].obj_no;\n-\t\tstruct base_data *result;\n-\n-\t\tassert(child->real_type == OBJ_OFS_DELTA);\n-\t\tchild->real_type = base->obj->real_type;\n-\t\tget_base_data(base);\n-\t\tresult = resolve_delta(child, base);\n-\t\tif (base->ofs_first == base->ofs_last)\n-\t\t\tfree_base_data(base);\n-\n-\t\tbase->ofs_first++;\n-\t\treturn result;\n-\t}\n-\n-\tfree_base_data(base);\n-\treturn NULL;\n-}\n-\n-static void find_unresolved_deltas(struct base_data *base)\n-{\n-\tstruct base_data *new_base, *prev_base = NULL;\n-\tfor (;;) {\n-\t\tnew_base = find_unresolved_deltas_1(base, prev_base);\n-\n-\t\tif (new_base) {\n-\t\t\tprev_base = base;\n-\t\t\tbase = new_base;\n-\t\t} else {\n-\t\t\tfree(base);\n-\t\t\tbase = prev_base;\n-\t\t\tif (!base)\n-\t\t\t\treturn;\n-\t\t\tprev_base = base->base;\n-\t\t}\n-\t}\n-}\n-\n static int compare_ofs_delta_entry(const void *a, const void *b)\n {\n \tconst struct ofs_delta_entry *delta_a = a;\n@@ -1068,33 +1012,131 @@ static int compare_ref_delta_entry(const void *a, const void *b)\n \treturn oidcmp(&delta_a->oid, &delta_b->oid);\n }\n \n-static void resolve_base(struct object_entry *obj)\n-{\n-\tstruct base_data *base_obj = make_base(obj, NULL);\n-\n-\tfind_unresolved_deltas(base_obj);\n-}\n-\n static void *threaded_second_pass(void *data)\n {\n-\tset_thread_data(data);\n+\tif (data)\n+\t\tset_thread_data(data);\n \tfor (;;) {\n-\t\tint i;\n-\t\tcounter_lock();\n-\t\tdisplay_progress(progress, nr_resolved_deltas);\n-\t\tcounter_unlock();\n+\t\tstruct base_data *parent = NULL;\n+\t\tstruct object_entry *child_obj;\n+\t\tstruct base_data *child;\n+\n \t\twork_lock();\n-\t\twhile (nr_dispatched < nr_objects &&\n-\t\t is_delta_type(objects[nr_dispatched].type))\n-\t\t\tnr_dispatched++;\n-\t\tif (nr_dispatched >= nr_objects) {\n-\t\t\twork_unlock();\n-\t\t\tbreak;\n+\t\tif (list_empty(&work_head)) {\n+\t\t\t/*\n+\t\t\t * Take an object from the object array.\n+\t\t\t */\n+\t\t\twhile (nr_dispatched < nr_objects &&\n+\t\t\t is_delta_type(objects[nr_dispatched].type))\n+\t\t\t\tnr_dispatched++;\n+\t\t\tif (nr_dispatched >= nr_objects) {\n+\t\t\t\twork_unlock();\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tchild_obj = &objects[nr_dispatched++];\n+\t\t} else {\n+\t\t\t/*\n+\t\t\t * Peek at the top of the stack, and take a child from\n+\t\t\t * it.\n+\t\t\t */\n+\t\t\tparent = list_first_entry(&work_head, struct base_data,\n+\t\t\t\t\t\t list);\n+\n+\t\t\tif (parent->ref_first <= parent->ref_last) {\n+\t\t\t\tint offset = ref_deltas[parent->ref_first++].obj_no;\n+\t\t\t\tchild_obj = objects + offset;\n+\t\t\t\tif (child_obj->real_type != OBJ_REF_DELTA)\n+\t\t\t\t\tdie(\"REF_DELTA at offset %\"PRIuMAX\" already resolved (duplicate base %s?)\",\n+\t\t\t\t\t (uintmax_t) child_obj->idx.offset,\n+\t\t\t\t\t oid_to_hex(&parent->obj->idx.oid));\n+\t\t\t\tchild_obj->real_type = parent->obj->real_type;\n+\t\t\t} else {\n+\t\t\t\tchild_obj = objects +\n+\t\t\t\t\tofs_deltas[parent->ofs_first++].obj_no;\n+\t\t\t\tassert(child_obj->real_type == OBJ_OFS_DELTA);\n+\t\t\t\tchild_obj->real_type = parent->obj->real_type;\n+\t\t\t}\n+\n+\t\t\tif (parent->ref_first > parent->ref_last &&\n+\t\t\t parent->ofs_first > parent->ofs_last) {\n+\t\t\t\t/*\n+\t\t\t\t * This parent has run out of children, so move\n+\t\t\t\t * it to done_head.\n+\t\t\t\t */\n+\t\t\t\tlist_del(&parent->list);\n+\t\t\t\tlist_add(&parent->list, &done_head);\n+\t\t\t}\n+\n+\t\t\t/*\n+\t\t\t * Ensure that the parent has data, since we will need\n+\t\t\t * it later.\n+\t\t\t *\n+\t\t\t * NEEDSWORK: If parent data needs to be reloaded, this\n+\t\t\t * prolongs the time that the current thread spends in\n+\t\t\t * the mutex. A mitigating factor is that parent data\n+\t\t\t * needs to be reloaded only if the delta base cache\n+\t\t\t * limit is exceeded, so in the typical case, this does\n+\t\t\t * not happen.\n+\t\t\t */\n+\t\t\tget_base_data(parent);\n+\t\t\tparent->retain_data++;\n \t\t}\n-\t\ti = nr_dispatched++;\n \t\twork_unlock();\n \n-\t\tresolve_base(&objects[i]);\n+\t\tif (parent) {\n+\t\t\tchild = resolve_delta(child_obj, parent);\n+\t\t\tif (!child->children_remaining)\n+\t\t\t\tFREE_AND_NULL(child->data);\n+\t\t} else {\n+\t\t\tchild = make_base(child_obj, NULL);\n+\t\t\tif (child->children_remaining) {\n+\t\t\t\t/*\n+\t\t\t\t * Since this child has its own delta children,\n+\t\t\t\t * we will need this data in the future.\n+\t\t\t\t * Inflate now so that future iterations will\n+\t\t\t\t * have access to this object's data while\n+\t\t\t\t * outside the work mutex.\n+\t\t\t\t */\n+\t\t\t\tchild->data = get_data_from_pack(child_obj);\n+\t\t\t\tchild->size = child_obj->size;\n+\t\t\t}\n+\t\t}\n+\n+\t\twork_lock();\n+\t\tif (parent)\n+\t\t\tparent->retain_data--;\n+\t\tif (child->data) {\n+\t\t\t/*\n+\t\t\t * This child has its own children, so add it to\n+\t\t\t * work_head.\n+\t\t\t */\n+\t\t\tlist_add(&child->list, &work_head);\n+\t\t\tbase_cache_used += child->size;\n+\t\t\tprune_base_data(NULL);\n+\t\t} else {\n+\t\t\t/*\n+\t\t\t * This child does not have its own children. It may be\n+\t\t\t * the last descendant of its ancestors; free those\n+\t\t\t * that we can.\n+\t\t\t */\n+\t\t\tstruct base_data *p = parent;\n+\n+\t\t\twhile (p) {\n+\t\t\t\tstruct base_data *next_p;\n+\n+\t\t\t\tp->children_remaining--;\n+\t\t\t\tif (p->children_remaining)\n+\t\t\t\t\tbreak;\n+\n+\t\t\t\tnext_p = p->base;\n+\t\t\t\tfree_base_data(p);\n+\t\t\t\tlist_del(&p->list);\n+\t\t\t\tfree(p);\n+\n+\t\t\t\tp = next_p;\n+\t\t\t}\n+\t\t}\n+\t\twork_unlock();\n \t}\n \treturn NULL;\n }\n@@ -1195,6 +1237,7 @@ static void resolve_deltas(void)\n \t\t\t\t\t nr_ref_deltas + nr_ofs_deltas);\n \n \tnr_dispatched = 0;\n+\tbase_cache_limit = delta_base_cache_limit * nr_threads;\n \tif (nr_threads > 1 || getenv(\"GIT_FORCE_THREADS\")) {\n \t\tinit_thread();\n \t\tfor (i = 0; i < nr_threads; i++) {\n@@ -1364,10 +1407,8 @@ static void fix_unresolved_deltas(struct hashfile *f)\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;\n \t\tvoid *data;\n \t\tunsigned long size;\n-\t\tstruct object_entry *obj;\n \n \t\tif (objects[d->obj_no].real_type != OBJ_REF_DELTA)\n \t\t\tcontinue;\n@@ -1379,11 +1420,15 @@ static void fix_unresolved_deltas(struct hashfile *f)\n \t\t\t\t\t data, size,\n \t\t\t\t\t type_name(type)))\n \t\t\tdie(_(\"local object %s is corrupt\"), oid_to_hex(&d->oid));\n-\t\tobj = append_obj_to_pack(f, d->oid.hash, data, size, type);\n-\t\tbase = make_base(obj, NULL);\n-\t\tbase->data = data;\n-\t\tbase->size = size;\n-\t\tfind_unresolved_deltas(base);\n+\n+\t\t/*\n+\t\t * Add this as an object to the objects array and call\n+\t\t * threaded_second_pass() (which will pick up the added\n+\t\t * object).\n+\t\t */\n+\t\tappend_obj_to_pack(f, d->oid.hash, data, size, type);\n+\t\tthreaded_second_pass(NULL);\n+\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n \t}\n \tfree(sorted_by_pos);\n-- \n2.28.0.297.g1956fa8f8d-goog\n\n"},{"id":"404363","messageId":"080e3b06d36e6abe660489765e7d424fc1bab62d.1598296530.git.jonathantanmy@google.com","threadId":"54125","inReplyTo":"cover.1598296530.git.jonathantanmy@google.com","subject":"[PATCH 6/7] index-pack: make resolve_delta() assume base data","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-08-24T19:16:37Z","receivedAt":"2020-08-24T19:17:25Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"A subsequent commit will make the quantum of work smaller, necessitating\nmore locking. This commit allows resolve_delta() to be called outside\nthe lock.\n\nSigned-off-by: Jonathan Tan \n---\n builtin/index-pack.c | 8 +++++---\n 1 file changed, 5 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex e98b11ab37..c6d2acc13a 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -927,7 +927,7 @@ static struct base_data *make_base(struct object_entry *obj,\n static struct base_data *resolve_delta(struct object_entry *delta_obj,\n \t\t\t\t struct base_data *base)\n {\n-\tvoid *base_data, *delta_data, *result_data;\n+\tvoid *delta_data, *result_data;\n \tstruct base_data *result;\n \tunsigned long result_size;\n \n@@ -942,8 +942,8 @@ static struct base_data *resolve_delta(struct object_entry *delta_obj,\n \t\tobj_stat[i].base_object_no = j;\n \t}\n \tdelta_data = get_data_from_pack(delta_obj);\n-\tbase_data = get_base_data(base);\n-\tresult_data = patch_delta(base_data, base->size,\n+\tassert(base->data);\n+\tresult_data = patch_delta(base->data, base->size,\n \t\t\t\t delta_data, delta_obj->size, &result_size);\n \tfree(delta_data);\n \tif (!result_data)\n@@ -1003,6 +1003,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t\t\t (uintmax_t)child->idx.offset,\n \t\t\t oid_to_hex(&base->obj->idx.oid));\n \n+\t\tget_base_data(base);\n \t\tresult = resolve_delta(child, base);\n \t\tif (base->ref_first == base->ref_last && base->ofs_last == -1)\n \t\t\tfree_base_data(base);\n@@ -1017,6 +1018,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \n \t\tassert(child->real_type == OBJ_OFS_DELTA);\n \t\tchild->real_type = base->obj->real_type;\n+\t\tget_base_data(base);\n \t\tresult = resolve_delta(child, base);\n \t\tif (base->ofs_first == base->ofs_last)\n \t\t\tfree_base_data(base);\n-- \n2.28.0.297.g1956fa8f8d-goog\n\n"},{"id":"404364","messageId":"6fe6ede5ff2dabed0d7633bc2a385d9047b13cb3.1598296530.git.jonathantanmy@google.com","threadId":"54125","inReplyTo":"cover.1598296530.git.jonathantanmy@google.com","subject":"[PATCH 4/7] index-pack: remove redundant child field","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-08-24T19:16:35Z","receivedAt":"2020-08-24T19:17:26Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"This is refactoring 1 of 2 to simplify struct base_data.\n\nIn index-pack, each thread maintains a doubly-linked list of the delta\nchain that it is currently processing (the \"base\" and \"child\" pointers\nin struct base_data). When a thread exceeds the delta base cache limit\nand needs to reclaim memory, it uses the \"child\" pointers to traverse\nthe lineage, reclaiming the memory of the eldest delta bases first.\n\nA subsequent patch will perform memory reclaiming in a different way and\nwill thus no longer need the \"child\" pointer. Because the \"child\"\npointer is redundant even now, remove it so that the aforementioned\nsubsequent patch will be clearer. In the meantime, reclaim memory in the\nreverse order of the \"base\" pointers.\n\nSigned-off-by: Jonathan Tan \n---\n builtin/index-pack.c | 41 ++++++++++++++++++++++-------------------\n 1 file changed, 22 insertions(+), 19 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 357e03b5aa..032716553c 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -34,7 +34,6 @@ struct object_stat {\n \n struct base_data {\n \tstruct base_data *base;\n-\tstruct base_data *child;\n \tstruct object_entry *obj;\n \tvoid *data;\n \tunsigned long size;\n@@ -44,7 +43,6 @@ struct base_data {\n \n struct thread_local {\n \tpthread_t thread;\n-\tstruct base_data *base_cache;\n \tsize_t base_cache_used;\n \tint pack_fd;\n };\n@@ -380,27 +378,37 @@ static void free_base_data(struct base_data *c)\n \t}\n }\n \n-static void prune_base_data(struct base_data *retain)\n+static void prune_base_data(struct base_data *youngest_child)\n {\n \tstruct base_data *b;\n \tstruct thread_local *data = get_thread_data();\n-\tfor (b = data->base_cache;\n-\t data->base_cache_used > delta_base_cache_limit && b;\n-\t b = b->child) {\n-\t\tif (b->data && b != retain)\n-\t\t\tfree_base_data(b);\n+\tstruct base_data **ancestry = NULL;\n+\tsize_t nr = 0, alloc = 0;\n+\tssize_t i;\n+\n+\tif (data->base_cache_used <= delta_base_cache_limit)\n+\t\treturn;\n+\n+\t/*\n+\t * Free all ancestors of youngest_child until we have enough space,\n+\t * starting with the oldest. (We cannot free youngest_child itself.)\n+\t */\n+\tfor (b = youngest_child->base; b != NULL; b = b->base) {\n+\t\tALLOC_GROW(ancestry, nr + 1, alloc);\n+\t\tancestry[nr++] = b;\n \t}\n+\tfor (i = nr - 1;\n+\t i >= 0 && data->base_cache_used > delta_base_cache_limit;\n+\t i--) {\n+\t\tif (ancestry[i]->data)\n+\t\t\tfree_base_data(ancestry[i]);\n+\t}\n+\tfree(ancestry);\n }\n \n static void link_base_data(struct base_data *base, struct base_data *c)\n {\n-\tif (base)\n-\t\tbase->child = c;\n-\telse\n-\t\tget_thread_data()->base_cache = c;\n-\n \tc->base = base;\n-\tc->child = NULL;\n \tif (c->data)\n \t\tget_thread_data()->base_cache_used += c->size;\n \tprune_base_data(c);\n@@ -408,11 +416,6 @@ static void link_base_data(struct base_data *base, struct base_data *c)\n \n static void unlink_base_data(struct base_data *c)\n {\n-\tstruct base_data *base = c->base;\n-\tif (base)\n-\t\tbase->child = NULL;\n-\telse\n-\t\tget_thread_data()->base_cache = NULL;\n \tfree_base_data(c);\n }\n \n-- \n2.28.0.297.g1956fa8f8d-goog\n\n"},{"id":"404366","messageId":"20200824193606.3883431-1-jonathantanmy@google.com","threadId":"54125","inReplyTo":"20200824191656.3870231-1-jonathantanmy@google.com","subject":"Re: [PATCH] fetch-pack: in partial clone, pass --promisor","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-08-24T19:36:06Z","receivedAt":"2020-08-24T19:36:13Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> When fetching a pack from a promisor remote, the corresponding .promisor\n> file needs to be created. \"fetch-pack\" originally did this by passing\n> \"--promisor\" to \"index-pack\", but in 5374a290aa (\"fetch-pack: write\n> fetched refs to .promisor\", 2019-10-16), \"fetch-pack\" was taught to do\n> this itself instead, because it needed to store ref information in the\n> .promisor file.\n\nOops...please ignore this. This has already been sent out as\nhttps://lore.kernel.org/git/20200820175116.3889786-1-jonathantanmy@google.com/\n"},{"id":"404375","messageId":"xmqqwo1n3h5t.fsf@gitster.c.googlers.com","threadId":"54125","inReplyTo":"cover.1598296530.git.jonathantanmy@google.com","subject":"Re: [PATCH 0/7] Better threaded delta resolution in index-pack (another try)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-08-24T20:47:26Z","receivedAt":"2020-08-24T20:47:36Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan writes:\n\n> I'm trying to resurrect [1] and have rebased it to latest master\n> (675a4aaf3b (\"Ninth batch\", 2020-08-19)).\n\nYay.\n\nThanks.\n"},{"id":"404377","messageId":"xmqqsgcb3ghn.fsf@gitster.c.googlers.com","threadId":"54125","inReplyTo":"648ec34821bd435468a0917167bdeef7ca101c02.1598296530.git.jonathantanmy@google.com","subject":"Re: [PATCH 2/7] index-pack: remove redundant parameter","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-08-24T21:01:56Z","receivedAt":"2020-08-24T21:02:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan writes:\n\n> find_{ref,ofs}_delta_{,children} take an enum object_type parameter, but\n> the object type is already present in the name of the function. Remove\n> that parameter from these functions.\n\nInteresting. \n\nThese \"find children\" are the only caller for each delta type and\nthey always pass OFS/REF constant that corresponds to them, so\nfind_*_delta() can lose the type. But compare_*_delta_bases()\ncannot, as the other one in the objects[] array may be of different\ntype.\n\nMakes sense. Thanks.\n\n"},{"id":"404378","messageId":"xmqqo8mz3g2d.fsf@gitster.c.googlers.com","threadId":"54125","inReplyTo":"2e7baaabf0ad9d724f5a81495213f4626b8c04ab.1598296530.git.jonathantanmy@google.com","subject":"Re: [PATCH 3/7] index-pack: unify threaded and unthreaded code","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-08-24T21:11:06Z","receivedAt":"2020-08-24T21:11:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan writes:\n\n> Signed-off-by: Jonathan Tan \n> ---\n> builtin/index-pack.c | 10 +---------\n> 1 file changed, 1 insertion(+), 9 deletions(-)\n>\n> diff --git a/builtin/index-pack.c b/builtin/index-pack.c\n> index a8444d550b..357e03b5aa 100644\n> --- a/builtin/index-pack.c\n> +++ b/builtin/index-pack.c\n> @@ -1211,15 +1211,7 @@ static void resolve_deltas(void)\n> \t\tcleanup_thread();\n> \t\treturn;\n> \t}\n> -\n> -\tfor (i = 0; i < nr_objects; i++) {\n> -\t\tstruct object_entry *obj = &objects[i];\n> -\n> -\t\tif (is_delta_type(obj->type))\n> -\t\t\tcontinue;\n> -\t\tresolve_base(obj);\n> -\t\tdisplay_progress(progress, nr_resolved_deltas);\n> -\t}\n> +\tthreaded_second_pass(¬hread_data);\n> }\n\nThe threaded_second_pass() function has a lot more noise than the\nabove simple and easy-to-grok loop, managing the locks, but those\nall turn into no-op unless init_thread() is called, which happens\nonly when this code is not reached. So OK, this looks essentially\na no-op clean-up.\n\nThanks.\n\n"},{"id":"404380","messageId":"xmqqk0xn3fo8.fsf@gitster.c.googlers.com","threadId":"54125","inReplyTo":"3e69f41f19535fa2c04fae6adc78bcc4f052d523.1598296530.git.jonathantanmy@google.com","subject":"Re: [PATCH 7/7] index-pack: make quantum of work smaller","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-08-24T21:19:35Z","receivedAt":"2020-08-24T21:19:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan writes:\n\n> Currently, when index-pack resolves deltas, it does not split up delta\n> trees into threads: each delta base root (an object that is not a\n> REF_DELTA or OFS_DELTA) can go into its own thread, but all deltas on\n> that root (direct or indirect) are processed in the same thread.\n>\n> This is a problem when a repository contains a large text file (thus,\n> delta-able) that is modified many times - delta resolution time during\n> fetching is dominated by processing the deltas corresponding to that\n> text file.\n\nWe favor wide and shallow delta trees for both reduced storage\nfootprint and lower runtime overhead, so optimizing the index-pack\nfor that use case makes a lot of sense.\n\n"},{"id":"404382","messageId":"20200824212751.3907181-1-jonathantanmy@google.com","threadId":"54125","inReplyTo":"cover.1598296530.git.jonathantanmy@google.com","subject":"[PATCH] fixup! index-pack: make quantum of work smaller","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-08-24T21:27:51Z","receivedAt":"2020-08-24T21:28:00Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"---\n> Josh did not list\n> out specific improvements to commit messages but I have taken his\n> suggestions for comments.\n\n...and somehow I forgot to commit them before sending out this patch\nset, so here they are.\n\n builtin/index-pack.c | 7 +++++++\n 1 file changed, 7 insertions(+)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 0a5b938e1e..4fa9127c35 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -62,6 +62,8 @@ struct base_data {\n * Stack of struct base_data that have unprocessed children.\n * threaded_second_pass() uses this as a source of work (the other being the\n * objects array).\n+ *\n+ * Guarded by work_mutex.\n */\n LIST_HEAD(work_head);\n \n@@ -70,11 +72,16 @@ LIST_HEAD(work_head);\n * processed or are being processed, and at least one child is being processed.\n * These struct base_data must be kept around until the last child is\n * processed.\n+ *\n+ * Guarded by work_mutex.\n */\n LIST_HEAD(done_head);\n \n /*\n * All threads share one delta base cache.\n+ *\n+ * base_cache_used is guarded by work_mutex, and base_cache_limit is read-only\n+ * in a thread.\n */\n size_t base_cache_used;\n size_t base_cache_limit;\n-- \n2.28.0.297.g1956fa8f8d-goog\n\n"},{"id":"404383","messageId":"20200824220829.GA802799@coredump.intra.peff.net","threadId":"54125","inReplyTo":"cover.1598296530.git.jonathantanmy@google.com","subject":"Re: [PATCH 0/7] Better threaded delta resolution in index-pack (another try)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-24T22:08:29Z","receivedAt":"2020-08-24T22:08:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 24, 2020 at 12:16:30PM -0700, Jonathan Tan wrote:\n\n> I'm trying to resurrect [1] and have rebased it to latest master\n> (675a4aaf3b (\"Ninth batch\", 2020-08-19)).\n> \n> Peff said [2] (of v1) that the overall direction seems reasonable and\n> Josh Steadmon said [3] (of v2) that it looks mostly good except for\n> possible improvements to commit messages and comments. Josh did not list\n> out specific improvements to commit messages but I have taken his\n> suggestions for comments.\n\nI haven't looked closely yet, but since I was doing timings of\nindex-pack recently[1], I wondered if this might change anything\n(spoiler: it doesn't really seem to).\n\nHere's the result of p5302 with my extra tests on my 8-core (16 with\nhyperthreading) laptop against linux.git:\n\n 5302.3: index-pack 0 threads 266.66(263.85+2.71)\n 5302.4: index-pack 1 threads 275.06(272.11+2.85)\n 5302.5: index-pack 2 threads 159.49(285.44+3.51)\n 5302.6: index-pack 4 threads 102.54(318.86+4.30)\n 5302.7: index-pack 8 threads 75.60(391.39+6.56) \n 5302.8: index-pack 16 threads 75.56(748.45+13.37)\n 5302.9: index-pack default number of threads 75.01(389.33+6.59) \n\nSo the conclusions from that other series remain pretty similar: nothing\ngets faster as we move past the number of actual cores. The penalty for\ndoing so seems less than what I got before, though (though it might just\nbe a fluke; it was something like 2s worse before your patches, and\nthere's a bit of noise; the increased CPU time can be disregarded as the\nprocessors are throttled down when more are running).\n\nThe overall time seems to get slightly worse, though (HEAD~7 is before\nyour patch, HEAD is with it):\n\n Test HEAD~7 HEAD \n --------------------------------------------------------------------------------------------\n 5302.9: index-pack default number of threads 71.96(376.11+3.66) 74.18(390.62+6.08) +3.1%\n\nThere may be other cases that get better, though. A 3% increase here is\nprobably OK if we get something for it. But if our primary goal here is\nincreasing multithread efficiency, then we should be able to show some\nbenchmark that improves. :)\n\n-Peff\n\n[1] https://lore.kernel.org/git/20200821175153.GA3263018@coredump.intra.peff.net/\n"},{"id":"404437","messageId":"20200825181145.1091378-1-jonathantanmy@google.com","threadId":"54125","inReplyTo":"20200824220829.GA802799@coredump.intra.peff.net","subject":"Re: [PATCH 0/7] Better threaded delta resolution in index-pack (another try)","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-08-25T18:11:45Z","receivedAt":"2020-08-25T18:11:56Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> The overall time seems to get slightly worse, though (HEAD~7 is before\n> your patch, HEAD is with it):\n> \n> Test HEAD~7 HEAD \n> --------------------------------------------------------------------------------------------\n> 5302.9: index-pack default number of threads 71.96(376.11+3.66) 74.18(390.62+6.08) +3.1%\n> \n> There may be other cases that get better, though. A 3% increase here is\n> probably OK if we get something for it. But if our primary goal here is\n> increasing multithread efficiency, then we should be able to show some\n> benchmark that improves. :)\n\nAh...good question. Cloning from\nhttps://fuchsia.googlesource.com/third_party/vulkan-cts (mentioned in\npatch 7), cd-ing to the pack dir, and running:\n\n git index-pack --stdin -o foo <*.pack\n\nI got 8m2.878s with my patches and 12m6.365s without. But I ran this on\na cloud virtual machine (what I have access to right now) so the numbers\nmight look different on a dedicated machine.\n"},{"id":"404480","messageId":"20200825211836.GA1448402@coredump.intra.peff.net","threadId":"54125","inReplyTo":"20200825181145.1091378-1-jonathantanmy@google.com","subject":"Re: [PATCH 0/7] Better threaded delta resolution in index-pack (another try)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-25T21:18:36Z","receivedAt":"2020-08-25T21:18:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Aug 25, 2020 at 11:11:45AM -0700, Jonathan Tan wrote:\n\n> > There may be other cases that get better, though. A 3% increase here is\n> > probably OK if we get something for it. But if our primary goal here is\n> > increasing multithread efficiency, then we should be able to show some\n> > benchmark that improves. :)\n> \n> Ah...good question. Cloning from\n> https://fuchsia.googlesource.com/third_party/vulkan-cts (mentioned in\n> patch 7), cd-ing to the pack dir, and running:\n> \n> git index-pack --stdin -o foo <*.pack\n> \n> I got 8m2.878s with my patches and 12m6.365s without. But I ran this on\n> a cloud virtual machine (what I have access to right now) so the numbers\n> might look different on a dedicated machine.\n\nThanks, that's a much more interesting example. Here's what I get on my\n8-core machine:\n\n 5302.9: index-pack default number of threads 167.70(546.19+12.00) 83.69(585.61+6.95) -50.1%\n\nSo that's a considerable improvement. And hardly surprising given the\nrepository structure. I used the script below to show the size of the\ndelta families, and the vk-master ones really dominate in size and\nobject number (the biggest is 50GB in one delta family).\n\nI also ran my PERF_EXTRA tests on them to see if it behaved differently\nas the threads increased. Nope:\n\n 5302.3: index-pack 0 threads 434.13(425.90+8.16)\n 5302.4: index-pack 1 threads 428.65(421.82+6.77)\n 5302.5: index-pack 2 threads 224.05(424.13+6.21)\n 5302.6: index-pack 4 threads 125.43(457.68+5.77)\n 5302.7: index-pack 8 threads 82.60(579.10+7.78) \n 5302.8: index-pack 16 threads 82.89(1147.82+9.66)\n 5302.9: index-pack default number of threads 83.91(576.92+8.52) \n\nStill maxes out at the number of physical cores (not unexpected, but\nthat was the thing I was most curious about ;) ). I may run it on the\n40-core machine, too. It's possible that with the new threading we're\nable to do better going past 20-threads. I doubt it, because I think\nit's mostly a function of Git's locking granularity, but worth checking.\n\n-Peff\n\n-- >8 --\n#!/bin/sh\n# script to output size, count, and filenames for each delta family\n\ngit rev-list --objects --all |\ngit cat-file --buffer \\\n --batch-check='%(objectname) %(deltabase) %(objectsize) %(rest)' |\nperl -alne '\n if ($F[1] =~ /[^0]/) {\n push @{$children{$F[1]}}, $F[0];\n } else {\n push @bases, $F[0];\n }\n $size{$F[0]} = $F[2];\n $name{$F[0]} = $F[3];\n END {\n sub add_to_component {\n my ($oid, $data) = @_;\n $data->{names}->{$name{$oid}}++;\n $data->{size} += $size{$oid};\n $data->{nr}++;\n add_to_component($_, $data) for @{$children{$oid}};\n }\n for my $b (@bases) {\n my $data = { size => 0, nr => 0, names => {} };\n add_to_component($b, $data);\n print join(\" \",\n $data->{size}, $data->{nr},\n\t\t sort keys(%{$data->{names}})\n ), \"\\n\";\n }\n }\n' |\nsort -rn\n"},{"id":"404483","messageId":"20200825214615.GA1476535@coredump.intra.peff.net","threadId":"54125","inReplyTo":"20200825211836.GA1448402@coredump.intra.peff.net","subject":"Re: [PATCH 0/7] Better threaded delta resolution in index-pack (another try)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-08-25T21:46:15Z","receivedAt":"2020-08-25T21:46:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Aug 25, 2020 at 05:18:36PM -0400, Jeff King wrote:\n\n> Still maxes out at the number of physical cores (not unexpected, but\n> that was the thing I was most curious about ;) ). I may run it on the\n> 40-core machine, too. It's possible that with the new threading we're\n> able to do better going past 20-threads. I doubt it, because I think\n> it's mostly a function of Git's locking granularity, but worth checking.\n\nFor the curious (I know you were all on the edge of your seat):\n\n 5302.3: index-pack 0 threads 519.23(479.10+40.10) \n 5302.4: index-pack 1 threads 525.94(476.27+49.64) \n 5302.5: index-pack 2 threads 271.82(458.93+55.52) \n 5302.6: index-pack 5 threads 115.88(463.84+50.69) \n 5302.7: index-pack 10 threads 67.26(478.37+57.38) \n 5302.8: index-pack 20 threads 43.02(524.01+77.33) \n 5302.9: index-pack 40 threads 33.42(709.86+100.24) \n 5302.10: index-pack 80 threads 32.02(1030.75+228.28)\n 5302.11: index-pack default number of threads 43.58(551.13+68.92) \n\nSo it actually does do a slight improvement to go from 20 to 40 threads\non this repository/machine combo. Not enough to make me revise the code\nI sent the other day, though. And we still get nothing from going past\nthe number of physical cores.\n\n-Peff\n"},{"id":"405180","messageId":"00502dee35e2d21fda2b240b57381b09b098e198.1599594441.git.jonathantanmy@google.com","threadId":"54125","inReplyTo":"cover.1599594441.git.jonathantanmy@google.com","subject":"[PATCH v2 2/7] index-pack: remove redundant parameter","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-09-08T19:48:30Z","receivedAt":"2020-09-08T19:48:59Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"find_{ref,ofs}_delta_{,children} take an enum object_type parameter, but\nthe object type is already present in the name of the function. Remove\nthat parameter from these functions.\n\nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \n---\n builtin/index-pack.c | 26 ++++++++++++--------------\n 1 file changed, 12 insertions(+), 14 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 9721bf1ffe..0e0889afc4 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -614,7 +614,7 @@ static int compare_ofs_delta_bases(off_t offset1, off_t offset2,\n \t 0;\n }\n \n-static int find_ofs_delta(const off_t offset, enum object_type type)\n+static int find_ofs_delta(const off_t offset)\n {\n \tint first = 0, last = nr_ofs_deltas;\n \n@@ -624,7 +624,8 @@ 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 OBJ_OFS_DELTA,\n+\t\t\t\t\t objects[delta->obj_no].type);\n \t\tif (!cmp)\n \t\t\treturn next;\n \t\tif (cmp < 0) {\n@@ -637,10 +638,9 @@ static int find_ofs_delta(const off_t offset, enum object_type type)\n }\n \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+\t\t\t\t int *first_index, int *last_index)\n {\n-\tint first = find_ofs_delta(offset, type);\n+\tint first = find_ofs_delta(offset);\n \tint last = first;\n \tint end = nr_ofs_deltas - 1;\n \n@@ -668,7 +668,7 @@ static int compare_ref_delta_bases(const struct object_id *oid1,\n \treturn oidcmp(oid1, oid2);\n }\n \n-static int find_ref_delta(const struct object_id *oid, enum object_type type)\n+static int find_ref_delta(const struct object_id *oid)\n {\n \tint first = 0, last = nr_ref_deltas;\n \n@@ -678,7 +678,8 @@ static int find_ref_delta(const struct object_id *oid, enum object_type type)\n \t\tint cmp;\n \n \t\tcmp = compare_ref_delta_bases(oid, &delta->oid,\n-\t\t\t\t\t type, objects[delta->obj_no].type);\n+\t\t\t\t\t OBJ_REF_DELTA,\n+\t\t\t\t\t objects[delta->obj_no].type);\n \t\tif (!cmp)\n \t\t\treturn next;\n \t\tif (cmp < 0) {\n@@ -691,10 +692,9 @@ static int find_ref_delta(const struct object_id *oid, enum object_type type)\n }\n \n static void find_ref_delta_children(const struct object_id *oid,\n-\t\t\t\t int *first_index, int *last_index,\n-\t\t\t\t enum object_type type)\n+\t\t\t\t int *first_index, int *last_index)\n {\n-\tint first = find_ref_delta(oid, type);\n+\tint first = find_ref_delta(oid);\n \tint last = first;\n \tint end = nr_ref_deltas - 1;\n \n@@ -983,12 +983,10 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n {\n \tif (base->ref_last == -1 && base->ofs_last == -1) {\n \t\tfind_ref_delta_children(&base->obj->idx.oid,\n-\t\t\t\t\t&base->ref_first, &base->ref_last,\n-\t\t\t\t\tOBJ_REF_DELTA);\n+\t\t\t\t\t&base->ref_first, &base->ref_last);\n \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+\t\t\t\t\t&base->ofs_first, &base->ofs_last);\n \n \t\tif (base->ref_last == -1 && base->ofs_last == -1) {\n \t\t\tfree(base->data);\n-- \n2.28.0.526.ge36021eeef-goog\n\n"},{"id":"405181","messageId":"dc9f0958d819f756a18f8eb7d4d1b8d618223e07.1599594441.git.jonathantanmy@google.com","threadId":"54125","inReplyTo":"cover.1599594441.git.jonathantanmy@google.com","subject":"[PATCH v2 3/7] index-pack: unify threaded and unthreaded code","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-09-08T19:48:31Z","receivedAt":"2020-09-08T19:49:10Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Signed-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \n---\n builtin/index-pack.c | 10 +---------\n 1 file changed, 1 insertion(+), 9 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 0e0889afc4..c7b4aef4e4 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1211,15 +1211,7 @@ static void resolve_deltas(void)\n \t\tcleanup_thread();\n \t\treturn;\n \t}\n-\n-\tfor (i = 0; i < nr_objects; i++) {\n-\t\tstruct object_entry *obj = &objects[i];\n-\n-\t\tif (is_delta_type(obj->type))\n-\t\t\tcontinue;\n-\t\tresolve_base(obj);\n-\t\tdisplay_progress(progress, nr_resolved_deltas);\n-\t}\n+\tthreaded_second_pass(¬hread_data);\n }\n \n /*\n-- \n2.28.0.526.ge36021eeef-goog\n\n"},{"id":"405182","messageId":"01d6d882768127df1596e3a4c63d9b1a5a9ba093.1599594441.git.jonathantanmy@google.com","threadId":"54125","inReplyTo":"cover.1599594441.git.jonathantanmy@google.com","subject":"[PATCH v2 7/7] index-pack: make quantum of work smaller","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-09-08T19:48:35Z","receivedAt":"2020-09-08T19:49:22Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Currently, when index-pack resolves deltas, it does not split up delta\ntrees into threads: each delta base root (an object that is not a\nREF_DELTA or OFS_DELTA) can go into its own thread, but all deltas on\nthat root (direct or indirect) are processed in the same thread.\n\nThis is a problem when a repository contains a large text file (thus,\ndelta-able) that is modified many times - delta resolution time during\nfetching is dominated by processing the deltas corresponding to that\ntext file.\n\nThis patch contains a solution to that. When cloning using\n\n git -c core.deltabasecachelimit=1g clone \\\n https://fuchsia.googlesource.com/third_party/vulkan-cts\n\non my laptop, clone time improved from 3m2s to 2m5s (using 3 threads,\nwhich is the default).\n\nThe solution is to have a global work stack. This stack contains delta\nbases (objects, whether appearing directly in the packfile or generated\nby delta resolution, that themselves have delta children) that need to\nbe processed; whenever a thread needs work, it peeks at the top of the\nstack and processes its next unprocessed child. If a thread finds the\nstack empty, it will look for more delta base roots to push on the stack\ninstead.\n\nThe main weakness of having a global work stack is that more time is\nspent in the mutex, but profiling has shown that most time is spent in\nthe resolution of the deltas themselves, so this shouldn't be an issue\nin practice. In any case, experimentation (as described in the clone\ncommand above) shows that this patch is a net improvement.\n\nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \n---\n builtin/index-pack.c | 348 +++++++++++++++++++++++++------------------\n 1 file changed, 200 insertions(+), 148 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex f69a50d46b..8acd078aa0 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -38,15 +38,56 @@ struct base_data {\n \tstruct object_entry *obj;\n \tint ref_first, ref_last;\n \tint ofs_first, ofs_last;\n+\t/*\n+\t * Threads should increment retain_data if they are about to call\n+\t * patch_delta() using this struct's data as a base, and decrement this\n+\t * when they are done. While retain_data is nonzero, this struct's data\n+\t * will not be freed even if the delta base cache limit is exceeded.\n+\t */\n+\tint retain_data;\n+\t/*\n+\t * The number of direct children that have not been fully processed\n+\t * (entered work_head, entered done_head, left done_head). When this\n+\t * number reaches zero, this struct base_data can be freed.\n+\t */\n+\tint children_remaining;\n \n \t/* Not initialized by make_base(). */\n+\tstruct list_head list;\n \tvoid *data;\n \tunsigned long size;\n };\n \n+/*\n+ * Stack of struct base_data that have unprocessed children.\n+ * threaded_second_pass() uses this as a source of work (the other being the\n+ * objects array).\n+ *\n+ * Guarded by work_mutex.\n+ */\n+static LIST_HEAD(work_head);\n+\n+/*\n+ * Stack of struct base_data that have children, all of whom have been\n+ * processed or are being processed, and at least one child is being processed.\n+ * These struct base_data must be kept around until the last child is\n+ * processed.\n+ *\n+ * Guarded by work_mutex.\n+ */\n+static LIST_HEAD(done_head);\n+\n+/*\n+ * All threads share one delta base cache.\n+ *\n+ * base_cache_used is guarded by work_mutex, and base_cache_limit is read-only\n+ * in a thread.\n+ */\n+static size_t base_cache_used;\n+static size_t base_cache_limit;\n+\n struct thread_local {\n \tpthread_t thread;\n-\tsize_t base_cache_used;\n \tint pack_fd;\n };\n \n@@ -369,36 +410,38 @@ static void free_base_data(struct base_data *c)\n {\n \tif (c->data) {\n \t\tFREE_AND_NULL(c->data);\n-\t\tget_thread_data()->base_cache_used -= c->size;\n+\t\tbase_cache_used -= c->size;\n \t}\n }\n \n-static void prune_base_data(struct base_data *youngest_child)\n+static void prune_base_data(struct base_data *retain)\n {\n-\tstruct base_data *b;\n-\tstruct thread_local *data = get_thread_data();\n-\tstruct base_data **ancestry = NULL;\n-\tsize_t nr = 0, alloc = 0;\n-\tssize_t i;\n+\tstruct list_head *pos;\n \n-\tif (data->base_cache_used <= delta_base_cache_limit)\n+\tif (base_cache_used <= base_cache_limit)\n \t\treturn;\n \n-\t/*\n-\t * Free all ancestors of youngest_child until we have enough space,\n-\t * starting with the oldest. (We cannot free youngest_child itself.)\n-\t */\n-\tfor (b = youngest_child->base; b != NULL; b = b->base) {\n-\t\tALLOC_GROW(ancestry, nr + 1, alloc);\n-\t\tancestry[nr++] = b;\n+\tlist_for_each_prev(pos, &done_head) {\n+\t\tstruct base_data *b = list_entry(pos, struct base_data, list);\n+\t\tif (b->retain_data || b == retain)\n+\t\t\tcontinue;\n+\t\tif (b->data) {\n+\t\t\tfree_base_data(b);\n+\t\t\tif (base_cache_used <= base_cache_limit)\n+\t\t\t\treturn;\n+\t\t}\n \t}\n-\tfor (i = nr - 1;\n-\t i >= 0 && data->base_cache_used > delta_base_cache_limit;\n-\t i--) {\n-\t\tif (ancestry[i]->data)\n-\t\t\tfree_base_data(ancestry[i]);\n+\n+\tlist_for_each_prev(pos, &work_head) {\n+\t\tstruct base_data *b = list_entry(pos, struct base_data, list);\n+\t\tif (b->retain_data || b == retain)\n+\t\t\tcontinue;\n+\t\tif (b->data) {\n+\t\t\tfree_base_data(b);\n+\t\t\tif (base_cache_used <= base_cache_limit)\n+\t\t\t\treturn;\n+\t\t}\n \t}\n-\tfree(ancestry);\n }\n \n static int is_delta_type(enum object_type type)\n@@ -851,15 +894,7 @@ static void sha1_object(const void *data, struct object_entry *obj_entry,\n }\n \n /*\n- * This function is part of find_unresolved_deltas(). There are two\n- * walkers going in the opposite ways.\n- *\n- * The first one in find_unresolved_deltas() traverses down from\n- * parent node to children, deflating nodes along the way. However,\n- * memory for deflated nodes is limited by delta_base_cache_limit, so\n- * at some point parent node's deflated content may be freed.\n- *\n- * The second walker is this function, which goes from current node up\n+ * Walk from current node up\n * to top parent if necessary to deflate the node. In normal\n * situation, its parent node would be already deflated, so it just\n * needs to apply delta.\n@@ -887,7 +922,7 @@ static void *get_base_data(struct base_data *c)\n \t\tif (!delta_nr) {\n \t\t\tc->data = get_data_from_pack(obj);\n \t\t\tc->size = obj->size;\n-\t\t\tget_thread_data()->base_cache_used += c->size;\n+\t\t\tbase_cache_used += c->size;\n \t\t\tprune_base_data(c);\n \t\t}\n \t\tfor (; delta_nr > 0; delta_nr--) {\n@@ -903,7 +938,7 @@ static void *get_base_data(struct base_data *c)\n \t\t\tfree(raw);\n \t\t\tif (!c->data)\n \t\t\t\tbad_object(obj->idx.offset, _(\"failed to apply delta\"));\n-\t\t\tget_thread_data()->base_cache_used += c->size;\n+\t\t\tbase_cache_used += c->size;\n \t\t\tprune_base_data(c);\n \t\t}\n \t\tfree(delta);\n@@ -921,6 +956,8 @@ static struct base_data *make_base(struct object_entry *obj,\n \t\t\t\t&base->ref_first, &base->ref_last);\n \tfind_ofs_delta_children(obj->idx.offset,\n \t\t\t\t&base->ofs_first, &base->ofs_last);\n+\tbase->children_remaining = base->ref_last - base->ref_first +\n+\t\tbase->ofs_last - base->ofs_first + 2;\n \treturn base;\n }\n \n@@ -954,14 +991,8 @@ static struct base_data *resolve_delta(struct object_entry *delta_obj,\n \t\t &delta_obj->idx.oid);\n \n \tresult = make_base(delta_obj, base);\n-\tif (result->ref_last == -1 && result->ofs_last == -1) {\n-\t\tfree(result_data);\n-\t} else {\n-\t\tresult->data = result_data;\n-\t\tresult->size = result_size;\n-\t\tget_thread_data()->base_cache_used += result->size;\n-\t\tprune_base_data(result);\n-\t}\n+\tresult->data = result_data;\n+\tresult->size = result_size;\n \n \tcounter_lock();\n \tnr_resolved_deltas++;\n@@ -970,86 +1001,6 @@ static struct base_data *resolve_delta(struct object_entry *delta_obj,\n \treturn result;\n }\n \n-/*\n- * Standard boolean compare-and-swap: atomically check whether \"*type\" is\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(signed char *type,\n-\t\t\t\t enum object_type want,\n-\t\t\t\t enum object_type set)\n-{\n-\tenum object_type old;\n-\n-\ttype_cas_lock();\n-\told = *type;\n-\tif (old == want)\n-\t\t*type = set;\n-\ttype_cas_unlock();\n-\n-\treturn old == want;\n-}\n-\n-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_first <= base->ref_last) {\n-\t\tstruct object_entry *child = objects + ref_deltas[base->ref_first].obj_no;\n-\t\tstruct base_data *result;\n-\n-\t\tif (!compare_and_swap_type(&child->real_type, OBJ_REF_DELTA,\n-\t\t\t\t\t base->obj->real_type))\n-\t\t\tdie(\"REF_DELTA at offset %\"PRIuMAX\" already resolved (duplicate base %s?)\",\n-\t\t\t (uintmax_t)child->idx.offset,\n-\t\t\t oid_to_hex(&base->obj->idx.oid));\n-\n-\t\tget_base_data(base);\n-\t\tresult = resolve_delta(child, base);\n-\t\tif (base->ref_first == base->ref_last && base->ofs_last == -1)\n-\t\t\tfree_base_data(base);\n-\n-\t\tbase->ref_first++;\n-\t\treturn result;\n-\t}\n-\n-\tif (base->ofs_first <= base->ofs_last) {\n-\t\tstruct object_entry *child = objects + ofs_deltas[base->ofs_first].obj_no;\n-\t\tstruct base_data *result;\n-\n-\t\tassert(child->real_type == OBJ_OFS_DELTA);\n-\t\tchild->real_type = base->obj->real_type;\n-\t\tget_base_data(base);\n-\t\tresult = resolve_delta(child, base);\n-\t\tif (base->ofs_first == base->ofs_last)\n-\t\t\tfree_base_data(base);\n-\n-\t\tbase->ofs_first++;\n-\t\treturn result;\n-\t}\n-\n-\tfree_base_data(base);\n-\treturn NULL;\n-}\n-\n-static void find_unresolved_deltas(struct base_data *base)\n-{\n-\tstruct base_data *new_base, *prev_base = NULL;\n-\tfor (;;) {\n-\t\tnew_base = find_unresolved_deltas_1(base, prev_base);\n-\n-\t\tif (new_base) {\n-\t\t\tprev_base = base;\n-\t\t\tbase = new_base;\n-\t\t} else {\n-\t\t\tfree(base);\n-\t\t\tbase = prev_base;\n-\t\t\tif (!base)\n-\t\t\t\treturn;\n-\t\t\tprev_base = base->base;\n-\t\t}\n-\t}\n-}\n-\n static int compare_ofs_delta_entry(const void *a, const void *b)\n {\n \tconst struct ofs_delta_entry *delta_a = a;\n@@ -1068,33 +1019,131 @@ static int compare_ref_delta_entry(const void *a, const void *b)\n \treturn oidcmp(&delta_a->oid, &delta_b->oid);\n }\n \n-static void resolve_base(struct object_entry *obj)\n-{\n-\tstruct base_data *base_obj = make_base(obj, NULL);\n-\n-\tfind_unresolved_deltas(base_obj);\n-}\n-\n static void *threaded_second_pass(void *data)\n {\n-\tset_thread_data(data);\n+\tif (data)\n+\t\tset_thread_data(data);\n \tfor (;;) {\n-\t\tint i;\n-\t\tcounter_lock();\n-\t\tdisplay_progress(progress, nr_resolved_deltas);\n-\t\tcounter_unlock();\n+\t\tstruct base_data *parent = NULL;\n+\t\tstruct object_entry *child_obj;\n+\t\tstruct base_data *child;\n+\n \t\twork_lock();\n-\t\twhile (nr_dispatched < nr_objects &&\n-\t\t is_delta_type(objects[nr_dispatched].type))\n-\t\t\tnr_dispatched++;\n-\t\tif (nr_dispatched >= nr_objects) {\n-\t\t\twork_unlock();\n-\t\t\tbreak;\n+\t\tif (list_empty(&work_head)) {\n+\t\t\t/*\n+\t\t\t * Take an object from the object array.\n+\t\t\t */\n+\t\t\twhile (nr_dispatched < nr_objects &&\n+\t\t\t is_delta_type(objects[nr_dispatched].type))\n+\t\t\t\tnr_dispatched++;\n+\t\t\tif (nr_dispatched >= nr_objects) {\n+\t\t\t\twork_unlock();\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tchild_obj = &objects[nr_dispatched++];\n+\t\t} else {\n+\t\t\t/*\n+\t\t\t * Peek at the top of the stack, and take a child from\n+\t\t\t * it.\n+\t\t\t */\n+\t\t\tparent = list_first_entry(&work_head, struct base_data,\n+\t\t\t\t\t\t list);\n+\n+\t\t\tif (parent->ref_first <= parent->ref_last) {\n+\t\t\t\tint offset = ref_deltas[parent->ref_first++].obj_no;\n+\t\t\t\tchild_obj = objects + offset;\n+\t\t\t\tif (child_obj->real_type != OBJ_REF_DELTA)\n+\t\t\t\t\tdie(\"REF_DELTA at offset %\"PRIuMAX\" already resolved (duplicate base %s?)\",\n+\t\t\t\t\t (uintmax_t) child_obj->idx.offset,\n+\t\t\t\t\t oid_to_hex(&parent->obj->idx.oid));\n+\t\t\t\tchild_obj->real_type = parent->obj->real_type;\n+\t\t\t} else {\n+\t\t\t\tchild_obj = objects +\n+\t\t\t\t\tofs_deltas[parent->ofs_first++].obj_no;\n+\t\t\t\tassert(child_obj->real_type == OBJ_OFS_DELTA);\n+\t\t\t\tchild_obj->real_type = parent->obj->real_type;\n+\t\t\t}\n+\n+\t\t\tif (parent->ref_first > parent->ref_last &&\n+\t\t\t parent->ofs_first > parent->ofs_last) {\n+\t\t\t\t/*\n+\t\t\t\t * This parent has run out of children, so move\n+\t\t\t\t * it to done_head.\n+\t\t\t\t */\n+\t\t\t\tlist_del(&parent->list);\n+\t\t\t\tlist_add(&parent->list, &done_head);\n+\t\t\t}\n+\n+\t\t\t/*\n+\t\t\t * Ensure that the parent has data, since we will need\n+\t\t\t * it later.\n+\t\t\t *\n+\t\t\t * NEEDSWORK: If parent data needs to be reloaded, this\n+\t\t\t * prolongs the time that the current thread spends in\n+\t\t\t * the mutex. A mitigating factor is that parent data\n+\t\t\t * needs to be reloaded only if the delta base cache\n+\t\t\t * limit is exceeded, so in the typical case, this does\n+\t\t\t * not happen.\n+\t\t\t */\n+\t\t\tget_base_data(parent);\n+\t\t\tparent->retain_data++;\n \t\t}\n-\t\ti = nr_dispatched++;\n \t\twork_unlock();\n \n-\t\tresolve_base(&objects[i]);\n+\t\tif (parent) {\n+\t\t\tchild = resolve_delta(child_obj, parent);\n+\t\t\tif (!child->children_remaining)\n+\t\t\t\tFREE_AND_NULL(child->data);\n+\t\t} else {\n+\t\t\tchild = make_base(child_obj, NULL);\n+\t\t\tif (child->children_remaining) {\n+\t\t\t\t/*\n+\t\t\t\t * Since this child has its own delta children,\n+\t\t\t\t * we will need this data in the future.\n+\t\t\t\t * Inflate now so that future iterations will\n+\t\t\t\t * have access to this object's data while\n+\t\t\t\t * outside the work mutex.\n+\t\t\t\t */\n+\t\t\t\tchild->data = get_data_from_pack(child_obj);\n+\t\t\t\tchild->size = child_obj->size;\n+\t\t\t}\n+\t\t}\n+\n+\t\twork_lock();\n+\t\tif (parent)\n+\t\t\tparent->retain_data--;\n+\t\tif (child->data) {\n+\t\t\t/*\n+\t\t\t * This child has its own children, so add it to\n+\t\t\t * work_head.\n+\t\t\t */\n+\t\t\tlist_add(&child->list, &work_head);\n+\t\t\tbase_cache_used += child->size;\n+\t\t\tprune_base_data(NULL);\n+\t\t} else {\n+\t\t\t/*\n+\t\t\t * This child does not have its own children. It may be\n+\t\t\t * the last descendant of its ancestors; free those\n+\t\t\t * that we can.\n+\t\t\t */\n+\t\t\tstruct base_data *p = parent;\n+\n+\t\t\twhile (p) {\n+\t\t\t\tstruct base_data *next_p;\n+\n+\t\t\t\tp->children_remaining--;\n+\t\t\t\tif (p->children_remaining)\n+\t\t\t\t\tbreak;\n+\n+\t\t\t\tnext_p = p->base;\n+\t\t\t\tfree_base_data(p);\n+\t\t\t\tlist_del(&p->list);\n+\t\t\t\tfree(p);\n+\n+\t\t\t\tp = next_p;\n+\t\t\t}\n+\t\t}\n+\t\twork_unlock();\n \t}\n \treturn NULL;\n }\n@@ -1195,6 +1244,7 @@ static void resolve_deltas(void)\n \t\t\t\t\t nr_ref_deltas + nr_ofs_deltas);\n \n \tnr_dispatched = 0;\n+\tbase_cache_limit = delta_base_cache_limit * nr_threads;\n \tif (nr_threads > 1 || getenv(\"GIT_FORCE_THREADS\")) {\n \t\tinit_thread();\n \t\tfor (i = 0; i < nr_threads; i++) {\n@@ -1364,10 +1414,8 @@ static void fix_unresolved_deltas(struct hashfile *f)\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;\n \t\tvoid *data;\n \t\tunsigned long size;\n-\t\tstruct object_entry *obj;\n \n \t\tif (objects[d->obj_no].real_type != OBJ_REF_DELTA)\n \t\t\tcontinue;\n@@ -1379,11 +1427,15 @@ static void fix_unresolved_deltas(struct hashfile *f)\n \t\t\t\t\t data, size,\n \t\t\t\t\t type_name(type)))\n \t\t\tdie(_(\"local object %s is corrupt\"), oid_to_hex(&d->oid));\n-\t\tobj = append_obj_to_pack(f, d->oid.hash, data, size, type);\n-\t\tbase = make_base(obj, NULL);\n-\t\tbase->data = data;\n-\t\tbase->size = size;\n-\t\tfind_unresolved_deltas(base);\n+\n+\t\t/*\n+\t\t * Add this as an object to the objects array and call\n+\t\t * threaded_second_pass() (which will pick up the added\n+\t\t * object).\n+\t\t */\n+\t\tappend_obj_to_pack(f, d->oid.hash, data, size, type);\n+\t\tthreaded_second_pass(NULL);\n+\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n \t}\n \tfree(sorted_by_pos);\n-- \n2.28.0.526.ge36021eeef-goog\n\n"},{"id":"405183","messageId":"34b53f268fad32aca499f5f4b73ceedca693e9ef.1599594441.git.jonathantanmy@google.com","threadId":"54125","inReplyTo":"cover.1599594441.git.jonathantanmy@google.com","subject":"[PATCH v2 6/7] index-pack: make resolve_delta() assume base data","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-09-08T19:48:34Z","receivedAt":"2020-09-08T19:49:56Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"A subsequent commit will make the quantum of work smaller, necessitating\nmore locking. This commit allows resolve_delta() to be called outside\nthe lock.\n\nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \n---\n builtin/index-pack.c | 8 +++++---\n 1 file changed, 5 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 94d0f53b03..f69a50d46b 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -927,7 +927,7 @@ static struct base_data *make_base(struct object_entry *obj,\n static struct base_data *resolve_delta(struct object_entry *delta_obj,\n \t\t\t\t struct base_data *base)\n {\n-\tvoid *base_data, *delta_data, *result_data;\n+\tvoid *delta_data, *result_data;\n \tstruct base_data *result;\n \tunsigned long result_size;\n \n@@ -942,8 +942,8 @@ static struct base_data *resolve_delta(struct object_entry *delta_obj,\n \t\tobj_stat[i].base_object_no = j;\n \t}\n \tdelta_data = get_data_from_pack(delta_obj);\n-\tbase_data = get_base_data(base);\n-\tresult_data = patch_delta(base_data, base->size,\n+\tassert(base->data);\n+\tresult_data = patch_delta(base->data, base->size,\n \t\t\t\t delta_data, delta_obj->size, &result_size);\n \tfree(delta_data);\n \tif (!result_data)\n@@ -1003,6 +1003,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t\t\t (uintmax_t)child->idx.offset,\n \t\t\t oid_to_hex(&base->obj->idx.oid));\n \n+\t\tget_base_data(base);\n \t\tresult = resolve_delta(child, base);\n \t\tif (base->ref_first == base->ref_last && base->ofs_last == -1)\n \t\t\tfree_base_data(base);\n@@ -1017,6 +1018,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \n \t\tassert(child->real_type == OBJ_OFS_DELTA);\n \t\tchild->real_type = base->obj->real_type;\n+\t\tget_base_data(base);\n \t\tresult = resolve_delta(child, base);\n \t\tif (base->ofs_first == base->ofs_last)\n \t\t\tfree_base_data(base);\n-- \n2.28.0.526.ge36021eeef-goog\n\n"},{"id":"405184","messageId":"cb0b3738dd0bc018e7f2677ca3b172364bf18961.1599594441.git.jonathantanmy@google.com","threadId":"54125","inReplyTo":"cover.1599594441.git.jonathantanmy@google.com","subject":"[PATCH v2 5/7] index-pack: calculate {ref,ofs}_{first,last} early","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-09-08T19:48:33Z","receivedAt":"2020-09-08T19:49:59Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"This is refactoring 2 of 2 to simplify struct base_data.\n\nWhenever we make a struct base_data, immediately calculate its delta\nchildren. This eliminates confusion as to when the\n{ref,ofs}_{first,last} fields are initialized.\n\nBefore this patch, the delta children were calculated at the last\npossible moment. This allowed the members of struct base_data to be\npopulated in any order, superficially useful when we have the object\ncontents before the struct object_entry. But this makes reasoning about\nthe state of struct base_data more complicated, hence this patch.\n\nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \n---\n builtin/index-pack.c | 123 +++++++++++++++++++++----------------------\n 1 file changed, 60 insertions(+), 63 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex c8db464557..94d0f53b03 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -33,12 +33,15 @@ struct object_stat {\n };\n \n struct base_data {\n+\t/* Initialized by make_base(). */\n \tstruct base_data *base;\n \tstruct object_entry *obj;\n-\tvoid *data;\n-\tunsigned long size;\n \tint ref_first, ref_last;\n \tint ofs_first, ofs_last;\n+\n+\t/* Not initialized by make_base(). */\n+\tvoid *data;\n+\tunsigned long size;\n };\n \n struct thread_local {\n@@ -362,14 +365,6 @@ static void set_thread_data(struct thread_local *data)\n \t\tpthread_setspecific(key, data);\n }\n \n-static struct base_data *alloc_base_data(void)\n-{\n-\tstruct base_data *base = xcalloc(1, sizeof(struct base_data));\n-\tbase->ref_last = -1;\n-\tbase->ofs_last = -1;\n-\treturn base;\n-}\n-\n static void free_base_data(struct base_data *c)\n {\n \tif (c->data) {\n@@ -406,19 +401,6 @@ static void prune_base_data(struct base_data *youngest_child)\n \tfree(ancestry);\n }\n \n-static void link_base_data(struct base_data *base, struct base_data *c)\n-{\n-\tc->base = base;\n-\tif (c->data)\n-\t\tget_thread_data()->base_cache_used += c->size;\n-\tprune_base_data(c);\n-}\n-\n-static void unlink_base_data(struct base_data *c)\n-{\n-\tfree_base_data(c);\n-}\n-\n static int is_delta_type(enum object_type type)\n {\n \treturn (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA);\n@@ -929,10 +911,25 @@ static void *get_base_data(struct base_data *c)\n \treturn c->data;\n }\n \n-static void resolve_delta(struct object_entry *delta_obj,\n-\t\t\t struct base_data *base, struct base_data *result)\n+static struct base_data *make_base(struct object_entry *obj,\n+\t\t\t\t struct base_data *parent)\n {\n-\tvoid *base_data, *delta_data;\n+\tstruct base_data *base = xcalloc(1, sizeof(struct base_data));\n+\tbase->base = parent;\n+\tbase->obj = obj;\n+\tfind_ref_delta_children(&obj->idx.oid,\n+\t\t\t\t&base->ref_first, &base->ref_last);\n+\tfind_ofs_delta_children(obj->idx.offset,\n+\t\t\t\t&base->ofs_first, &base->ofs_last);\n+\treturn base;\n+}\n+\n+static struct base_data *resolve_delta(struct object_entry *delta_obj,\n+\t\t\t\t struct base_data *base)\n+{\n+\tvoid *base_data, *delta_data, *result_data;\n+\tstruct base_data *result;\n+\tunsigned long result_size;\n \n \tif (show_stat) {\n \t\tint i = delta_obj - objects;\n@@ -946,19 +943,31 @@ static void resolve_delta(struct object_entry *delta_obj,\n \t}\n \tdelta_data = get_data_from_pack(delta_obj);\n \tbase_data = get_base_data(base);\n-\tresult->obj = delta_obj;\n-\tresult->data = patch_delta(base_data, base->size,\n-\t\t\t\t delta_data, delta_obj->size, &result->size);\n+\tresult_data = patch_delta(base_data, base->size,\n+\t\t\t\t delta_data, delta_obj->size, &result_size);\n \tfree(delta_data);\n-\tif (!result->data)\n+\tif (!result_data)\n \t\tbad_object(delta_obj->idx.offset, _(\"failed to apply delta\"));\n-\thash_object_file(the_hash_algo, result->data, result->size,\n+\thash_object_file(the_hash_algo, result_data, result_size,\n \t\t\t type_name(delta_obj->real_type), &delta_obj->idx.oid);\n-\tsha1_object(result->data, NULL, result->size, delta_obj->real_type,\n+\tsha1_object(result_data, NULL, result_size, delta_obj->real_type,\n \t\t &delta_obj->idx.oid);\n+\n+\tresult = make_base(delta_obj, base);\n+\tif (result->ref_last == -1 && result->ofs_last == -1) {\n+\t\tfree(result_data);\n+\t} else {\n+\t\tresult->data = result_data;\n+\t\tresult->size = result_size;\n+\t\tget_thread_data()->base_cache_used += result->size;\n+\t\tprune_base_data(result);\n+\t}\n+\n \tcounter_lock();\n \tnr_resolved_deltas++;\n \tcounter_unlock();\n+\n+\treturn result;\n }\n \n /*\n@@ -984,24 +993,9 @@ static int compare_and_swap_type(signed char *type,\n 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\tfind_ref_delta_children(&base->obj->idx.oid,\n-\t\t\t\t\t&base->ref_first, &base->ref_last);\n-\n-\t\tfind_ofs_delta_children(base->obj->idx.offset,\n-\t\t\t\t\t&base->ofs_first, &base->ofs_last);\n-\n-\t\tif (base->ref_last == -1 && base->ofs_last == -1) {\n-\t\t\tfree(base->data);\n-\t\t\treturn NULL;\n-\t\t}\n-\n-\t\tlink_base_data(prev_base, base);\n-\t}\n-\n \tif (base->ref_first <= base->ref_last) {\n \t\tstruct object_entry *child = objects + ref_deltas[base->ref_first].obj_no;\n-\t\tstruct base_data *result = alloc_base_data();\n+\t\tstruct base_data *result;\n \n \t\tif (!compare_and_swap_type(&child->real_type, OBJ_REF_DELTA,\n \t\t\t\t\t base->obj->real_type))\n@@ -1009,7 +1003,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t\t\t (uintmax_t)child->idx.offset,\n \t\t\t oid_to_hex(&base->obj->idx.oid));\n \n-\t\tresolve_delta(child, base, result);\n+\t\tresult = resolve_delta(child, base);\n \t\tif (base->ref_first == base->ref_last && base->ofs_last == -1)\n \t\t\tfree_base_data(base);\n \n@@ -1019,11 +1013,11 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \n \tif (base->ofs_first <= base->ofs_last) {\n \t\tstruct object_entry *child = objects + ofs_deltas[base->ofs_first].obj_no;\n-\t\tstruct base_data *result = alloc_base_data();\n+\t\tstruct base_data *result;\n \n \t\tassert(child->real_type == OBJ_OFS_DELTA);\n \t\tchild->real_type = base->obj->real_type;\n-\t\tresolve_delta(child, base, result);\n+\t\tresult = resolve_delta(child, base);\n \t\tif (base->ofs_first == base->ofs_last)\n \t\t\tfree_base_data(base);\n \n@@ -1031,7 +1025,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t\treturn result;\n \t}\n \n-\tunlink_base_data(base);\n+\tfree_base_data(base);\n \treturn NULL;\n }\n \n@@ -1074,9 +1068,8 @@ static int compare_ref_delta_entry(const void *a, const void *b)\n \n static void resolve_base(struct object_entry *obj)\n {\n-\tstruct base_data *base_obj = alloc_base_data();\n-\tbase_obj->obj = obj;\n-\tbase_obj->data = NULL;\n+\tstruct base_data *base_obj = make_base(obj, NULL);\n+\n \tfind_unresolved_deltas(base_obj);\n }\n \n@@ -1369,22 +1362,26 @@ static void fix_unresolved_deltas(struct hashfile *f)\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+\t\tstruct base_data *base;\n+\t\tvoid *data;\n+\t\tunsigned long size;\n+\t\tstruct object_entry *obj;\n \n \t\tif (objects[d->obj_no].real_type != OBJ_REF_DELTA)\n \t\t\tcontinue;\n-\t\tbase_obj->data = read_object_file(&d->oid, &type,\n-\t\t\t\t\t\t &base_obj->size);\n-\t\tif (!base_obj->data)\n+\t\tdata = read_object_file(&d->oid, &type, &size);\n+\t\tif (!data)\n \t\t\tcontinue;\n \n \t\tif (check_object_signature(the_repository, &d->oid,\n-\t\t\t\t\t base_obj->data, base_obj->size,\n+\t\t\t\t\t data, size,\n \t\t\t\t\t type_name(type)))\n \t\t\tdie(_(\"local object %s is corrupt\"), oid_to_hex(&d->oid));\n-\t\tbase_obj->obj = append_obj_to_pack(f, d->oid.hash,\n-\t\t\t\t\tbase_obj->data, base_obj->size, type);\n-\t\tfind_unresolved_deltas(base_obj);\n+\t\tobj = append_obj_to_pack(f, d->oid.hash, data, size, type);\n+\t\tbase = make_base(obj, NULL);\n+\t\tbase->data = data;\n+\t\tbase->size = size;\n+\t\tfind_unresolved_deltas(base);\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n \t}\n \tfree(sorted_by_pos);\n-- \n2.28.0.526.ge36021eeef-goog\n\n"},{"id":"405185","messageId":"c12f3a78de4aae8ba4bb031d764a345adcb1627d.1599594441.git.jonathantanmy@google.com","threadId":"54125","inReplyTo":"cover.1599594441.git.jonathantanmy@google.com","subject":"[PATCH v2 4/7] index-pack: remove redundant child field","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-09-08T19:48:32Z","receivedAt":"2020-09-08T19:50:06Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"This is refactoring 1 of 2 to simplify struct base_data.\n\nIn index-pack, each thread maintains a doubly-linked list of the delta\nchain that it is currently processing (the \"base\" and \"child\" pointers\nin struct base_data). When a thread exceeds the delta base cache limit\nand needs to reclaim memory, it uses the \"child\" pointers to traverse\nthe lineage, reclaiming the memory of the eldest delta bases first.\n\nA subsequent patch will perform memory reclaiming in a different way and\nwill thus no longer need the \"child\" pointer. Because the \"child\"\npointer is redundant even now, remove it so that the aforementioned\nsubsequent patch will be clearer. In the meantime, reclaim memory in the\nreverse order of the \"base\" pointers.\n\nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \n---\n builtin/index-pack.c | 41 ++++++++++++++++++++++-------------------\n 1 file changed, 22 insertions(+), 19 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex c7b4aef4e4..c8db464557 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -34,7 +34,6 @@ struct object_stat {\n \n struct base_data {\n \tstruct base_data *base;\n-\tstruct base_data *child;\n \tstruct object_entry *obj;\n \tvoid *data;\n \tunsigned long size;\n@@ -44,7 +43,6 @@ struct base_data {\n \n struct thread_local {\n \tpthread_t thread;\n-\tstruct base_data *base_cache;\n \tsize_t base_cache_used;\n \tint pack_fd;\n };\n@@ -380,27 +378,37 @@ static void free_base_data(struct base_data *c)\n \t}\n }\n \n-static void prune_base_data(struct base_data *retain)\n+static void prune_base_data(struct base_data *youngest_child)\n {\n \tstruct base_data *b;\n \tstruct thread_local *data = get_thread_data();\n-\tfor (b = data->base_cache;\n-\t data->base_cache_used > delta_base_cache_limit && b;\n-\t b = b->child) {\n-\t\tif (b->data && b != retain)\n-\t\t\tfree_base_data(b);\n+\tstruct base_data **ancestry = NULL;\n+\tsize_t nr = 0, alloc = 0;\n+\tssize_t i;\n+\n+\tif (data->base_cache_used <= delta_base_cache_limit)\n+\t\treturn;\n+\n+\t/*\n+\t * Free all ancestors of youngest_child until we have enough space,\n+\t * starting with the oldest. (We cannot free youngest_child itself.)\n+\t */\n+\tfor (b = youngest_child->base; b != NULL; b = b->base) {\n+\t\tALLOC_GROW(ancestry, nr + 1, alloc);\n+\t\tancestry[nr++] = b;\n \t}\n+\tfor (i = nr - 1;\n+\t i >= 0 && data->base_cache_used > delta_base_cache_limit;\n+\t i--) {\n+\t\tif (ancestry[i]->data)\n+\t\t\tfree_base_data(ancestry[i]);\n+\t}\n+\tfree(ancestry);\n }\n \n static void link_base_data(struct base_data *base, struct base_data *c)\n {\n-\tif (base)\n-\t\tbase->child = c;\n-\telse\n-\t\tget_thread_data()->base_cache = c;\n-\n \tc->base = base;\n-\tc->child = NULL;\n \tif (c->data)\n \t\tget_thread_data()->base_cache_used += c->size;\n \tprune_base_data(c);\n@@ -408,11 +416,6 @@ static void link_base_data(struct base_data *base, struct base_data *c)\n \n static void unlink_base_data(struct base_data *c)\n {\n-\tstruct base_data *base = c->base;\n-\tif (base)\n-\t\tbase->child = NULL;\n-\telse\n-\t\tget_thread_data()->base_cache = NULL;\n \tfree_base_data(c);\n }\n \n-- \n2.28.0.526.ge36021eeef-goog\n\n"},{"id":"405186","messageId":"cover.1599594441.git.jonathantanmy@google.com","threadId":"54125","inReplyTo":"cover.1598296530.git.jonathantanmy@google.com","subject":"[PATCH v2 0/7] Better threaded delta resolution in index-pack (another try)","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-09-08T19:48:28Z","receivedAt":"2020-09-08T19:50:08Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"From What's Cooking [1]:\n\n> * jt/threaded-index-pack (2020-08-27) 9 commits\n> - builtin/index-pack.c: fix some sparse warnings\n> - fixup! index-pack: make quantum of work smaller\n> - index-pack: make quantum of work smaller\n> - index-pack: make resolve_delta() assume base data\n> - index-pack: calculate {ref,ofs}_{first,last} early\n> - index-pack: remove redundant child field\n> - index-pack: unify threaded and unthreaded code\n> - index-pack: remove redundant parameter\n> - Documentation: deltaBaseCacheLimit is per-thread\n> \n> \"git index-pack\" learned to resolve deltified objects with greater\n> parallelism.\n> \n> Expecting the final reroll.\n> cf. https://colabti.org/irclogger/irclogger_log/git-devel?date=2020-08-31#l82\n\nHere's the reroll.\n\n[1] https://lore.kernel.org/git/xmqqk0xa8rvn.fsf@gitster.c.googlers.com/\n\nJonathan Tan (7):\n Documentation: deltaBaseCacheLimit is per-thread\n index-pack: remove redundant parameter\n index-pack: unify threaded and unthreaded code\n index-pack: remove redundant child field\n index-pack: calculate {ref,ofs}_{first,last} early\n index-pack: make resolve_delta() assume base data\n index-pack: make quantum of work smaller\n\n Documentation/config/core.txt | 2 +-\n builtin/index-pack.c | 456 +++++++++++++++++++---------------\n 2 files changed, 251 insertions(+), 207 deletions(-)\n\n-- \n2.28.0.526.ge36021eeef-goog\n\n"},{"id":"405187","messageId":"fe79905660bb11a88f605713cd132cbde46ec8a5.1599594441.git.jonathantanmy@google.com","threadId":"54125","inReplyTo":"cover.1599594441.git.jonathantanmy@google.com","subject":"[PATCH v2 1/7] Documentation: deltaBaseCacheLimit is per-thread","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-09-08T19:48:29Z","receivedAt":"2020-09-08T19:50:13Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Clarify that core.deltaBaseCacheLimit is per-thread, as can be seen from\nthe fact that cache usage (base_cache_used in struct thread_local in\nbuiltin/index-pack.c) is tracked individually for each thread and\ncompared against delta_base_cache_limit.\n\nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \n---\n Documentation/config/core.txt | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/Documentation/config/core.txt b/Documentation/config/core.txt\nindex 74619a9c03..02002cf109 100644\n--- a/Documentation/config/core.txt\n+++ b/Documentation/config/core.txt\n@@ -399,7 +399,7 @@ the largest projects. You probably do not need to adjust this value.\n Common unit suffixes of 'k', 'm', or 'g' are supported.\n \n core.deltaBaseCacheLimit::\n-\tMaximum number of bytes to reserve for caching base objects\n+\tMaximum number of bytes per thread to reserve for caching base objects\n \tthat may be referenced by multiple deltified objects. By storing the\n \tentire decompressed base objects in a cache Git is able\n \tto avoid unpacking and decompressing frequently used base\n-- \n2.28.0.526.ge36021eeef-goog\n\n"},{"id":"405208","messageId":"xmqqk0x3x4lt.fsf@gitster.c.googlers.com","threadId":"54125","inReplyTo":"cover.1599594441.git.jonathantanmy@google.com","subject":"Re: [PATCH v2 0/7] Better threaded delta resolution in index-pack (another try)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-09-08T22:53:34Z","receivedAt":"2020-09-08T22:53:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan writes:\n\n> Here's the reroll.\n>\n> [1] https://lore.kernel.org/git/xmqqk0xa8rvn.fsf@gitster.c.googlers.com/\n\nIt seems that the only changes (as expected) are squashing in the\nfollow-up \"oops\" fixes into the right place in the series?\n\nWill replace; thanks.\n\n\n>\n> Jonathan Tan (7):\n> Documentation: deltaBaseCacheLimit is per-thread\n> index-pack: remove redundant parameter\n> index-pack: unify threaded and unthreaded code\n> index-pack: remove redundant child field\n> index-pack: calculate {ref,ofs}_{first,last} early\n> index-pack: make resolve_delta() assume base data\n> index-pack: make quantum of work smaller\n>\n> Documentation/config/core.txt | 2 +-\n> builtin/index-pack.c | 456 +++++++++++++++++++---------------\n> 2 files changed, 251 insertions(+), 207 deletions(-)\n"}]}