{"thread":{"id":"52003","subject":"[RFC PATCH 0/6] Better threaded delta resolution in index-pack","startedAt":"2019-10-09T23:44:30Z","lastAt":"2020-03-10T21:45:37Z","messageCount":31,"participants":["Jonathan Tan","Derrick Stolee","Jeff King","Josh Steadmon"],"isPatch":true,"patchVersion":1,"patchTotal":6},"messages":[{"id":"383768","messageId":"cover.1570663470.git.jonathantanmy@google.com","threadId":"52003","inReplyTo":null,"subject":"[RFC PATCH 0/6] Better threaded delta resolution in index-pack","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-09T23:44:16Z","receivedAt":"2019-10-09T23:44:30Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Quoting myself [1]:\n\n> index-pack does parallelize delta resolution, but\n> it cannot split up trees into threads: each delta base root can go into\n> its own thread, but when a delta base root is processed, all deltas on\n> that root (direct or indirect) is 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. Here are patches that teach index-pack to better divide up\nthe work.\n\nAs an example of the effect, 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\nAs you can see from the diff stats, my new algorithm uses comparable\nlines of code to the existing one, but I think that it is a bit more\ncomplicated. My main point of difficulty was in handling the delta base\ncache - it must be GC-able, but at the same time available to another\nthread if it was being used as a base to inflate a delta. In the end,\nwhat I did was to make individual mutex-guarded refcounts for each\ninflation result, but the buffer itself is not mutex-guarded: so a\nthread could increment the refcount within the mutex, inflate (and\nverify) outside the mutex, and then decrement the refcount within the\nmutex. (One global mutex guards all the refcounts, as well as other\nthings.) Any ideas for making this design less complicated is\nappreciated.\n\nIf this is a good direction, let me know and I'll refine the patches. I\npersonally think that the improvement in performance is worth the slight\nadded complexity. Also, in this patch set, I did some cleanup to make\nfuture patches clearer, but some of the cleanup is undone by the future\npatches themselves; let me know if it's easier to review if I should\nsquash those patches.\n\nAlso CC-ing Mike Hommey because Mike brought up a repo with a similar\ncase [2], although that case happens during repack.\n\n[1] https://public-inbox.org/git/20190926003300.195781-1-jonathantanmy@google.com/\n[2] https://public-inbox.org/git/20190704100530.smn4rpiekwtfylhz@glandium.org/\n\nJonathan Tan (6):\n index-pack: unify threaded and unthreaded code\n index-pack: remove redundant parameter\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 builtin/index-pack.c | 375 ++++++++++++++++++++-----------------------\n 1 file changed, 177 insertions(+), 198 deletions(-)\n\n-- \n2.23.0.581.g78d2f28ef7-goog\n\n"},{"id":"383769","messageId":"32ef0122a55bfbdbde0595b2aad930d83b27dd6d.1570663470.git.jonathantanmy@google.com","threadId":"52003","inReplyTo":"cover.1570663470.git.jonathantanmy@google.com","subject":"[PATCH 1/6] index-pack: unify threaded and unthreaded code","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-09T23:44:17Z","receivedAt":"2019-10-09T23:44:33Z","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 a23454da6e..1a2600d4b3 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1210,15 +1210,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.23.0.581.g78d2f28ef7-goog\n\n"},{"id":"383770","messageId":"cf6c9f6e1799c587b4defa0e874b07aa9b72548b.1570663470.git.jonathantanmy@google.com","threadId":"52003","inReplyTo":"cover.1570663470.git.jonathantanmy@google.com","subject":"[PATCH 2/6] index-pack: remove redundant parameter","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-09T23:44:18Z","receivedAt":"2019-10-09T23:44:36Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Signed-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 1a2600d4b3..99f6e2957f 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@@ -982,12 +982,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.23.0.581.g78d2f28ef7-goog\n\n"},{"id":"383771","messageId":"39740c6e58bd6cb6ea33e5abb4ab8542ff6eb7b7.1570663470.git.jonathantanmy@google.com","threadId":"52003","inReplyTo":"cover.1570663470.git.jonathantanmy@google.com","subject":"[PATCH 3/6] index-pack: remove redundant child field","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-09T23:44:19Z","receivedAt":"2019-10-09T23:44:39Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Instead, recompute ancestry if we ever need to reclaim memory.\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 99f6e2957f..35f7f9e52b 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+\tint nr = 0, alloc = 0;\n+\tint 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.23.0.581.g78d2f28ef7-goog\n\n"},{"id":"383772","messageId":"0f0ffe71c5df9129a04546b8e3ed13a3ece1b9b1.1570663470.git.jonathantanmy@google.com","threadId":"52003","inReplyTo":"cover.1570663470.git.jonathantanmy@google.com","subject":"[PATCH 4/6] index-pack: calculate {ref,ofs}_{first,last} early","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-09T23:44:20Z","receivedAt":"2019-10-09T23:44:40Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Whenever 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\nSigned-off-by: Jonathan Tan \n---\n builtin/index-pack.c | 125 +++++++++++++++++++++----------------------\n 1 file changed, 61 insertions(+), 64 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 35f7f9e52b..17997834ec 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@@ -928,10 +910,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@@ -945,19 +942,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(result->data, result->size,\n+\thash_object_file(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@@ -983,30 +992,15 @@ 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 \t\t\tBUG(\"child->real_type != OBJ_REF_DELTA\");\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@@ -1016,11 +1010,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@@ -1028,7 +1022,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@@ -1071,9 +1065,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@@ -1367,21 +1360,25 @@ 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(&d->oid, base_obj->data,\n-\t\t\t\tbase_obj->size, type_name(type)))\n+\t\tif (check_object_signature(&d->oid, data,\n+\t\t\t\t\t size, 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.23.0.581.g78d2f28ef7-goog\n\n"},{"id":"383773","messageId":"6fcda102acd550818536c69c41c270a8058050a7.1570663470.git.jonathantanmy@google.com","threadId":"52003","inReplyTo":"cover.1570663470.git.jonathantanmy@google.com","subject":"[PATCH 5/6] index-pack: make resolve_delta() assume base data","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-09T23:44:21Z","receivedAt":"2019-10-09T23:44:43Z","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 17997834ec..3908cd3115 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -926,7 +926,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@@ -941,8 +941,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@@ -1000,6 +1000,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t\t\t\t\t base->obj->real_type))\n \t\t\tBUG(\"child->real_type != OBJ_REF_DELTA\");\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@@ -1014,6 +1015,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.23.0.581.g78d2f28ef7-goog\n\n"},{"id":"383774","messageId":"505d8e79cd983d5b3dfd56c4f0432ad647132957.1570663470.git.jonathantanmy@google.com","threadId":"52003","inReplyTo":"cover.1570663470.git.jonathantanmy@google.com","subject":"[PATCH 6/6] index-pack: make quantum of work smaller","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-09T23:44:22Z","receivedAt":"2019-10-09T23:44:44Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Signed-off-by: Jonathan Tan \n---\n builtin/index-pack.c | 267 ++++++++++++++++++++-----------------------\n 1 file changed, 127 insertions(+), 140 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 3908cd3115..f6318037ca 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -38,15 +38,22 @@ struct base_data {\n \tstruct object_entry *obj;\n \tint ref_first, ref_last;\n \tint ofs_first, ofs_last;\n+\tint retain_data;\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+LIST_HEAD(work_head);\n+LIST_HEAD(done_head);\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 +376,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-\tint nr = 0, alloc = 0;\n-\tint 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@@ -886,7 +895,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@@ -902,7 +911,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@@ -920,6 +929,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@@ -953,14 +964,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@@ -969,84 +974,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\tBUG(\"child->real_type != OBJ_REF_DELTA\");\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@@ -1065,33 +992,97 @@ 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+static void *do_work(void *data)\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\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\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\tchild_obj = objects +\n+\t\t\t\t\tref_deltas[parent->ref_first++].obj_no;\n+\t\t\t\tassert(child_obj->real_type == OBJ_REF_DELTA);\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\tlist_del(&parent->list);\n+\t\t\t\tlist_add(&parent->list, &done_head);\n+\t\t\t}\n+\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\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\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@@ -1192,11 +1183,12 @@ 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 \t\t\tint ret = pthread_create(&thread_data[i].thread, NULL,\n-\t\t\t\t\t\t threaded_second_pass, thread_data + i);\n+\t\t\t\t\t\t do_work, thread_data + i);\n \t\t\tif (ret)\n \t\t\t\tdie(_(\"unable to create thread: %s\"),\n \t\t\t\t strerror(ret));\n@@ -1206,7 +1198,7 @@ static void resolve_deltas(void)\n \t\tcleanup_thread();\n \t\treturn;\n \t}\n-\tthreaded_second_pass(¬hread_data);\n+\tdo_work(¬hread_data);\n }\n \n /*\n@@ -1362,10 +1354,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@@ -1376,11 +1366,8 @@ static void fix_unresolved_deltas(struct hashfile *f)\n \t\tif (check_object_signature(&d->oid, data,\n \t\t\t\t\t size, 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+\t\tappend_obj_to_pack(f, d->oid.hash, data, size, type);\n+\t\tdo_work(NULL); /* will pick up new object in objects array (added by append_obj_to_pack) */\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n \t}\n \tfree(sorted_by_pos);\n-- \n2.23.0.581.g78d2f28ef7-goog\n\n"},{"id":"383801","messageId":"67ca2f70-361a-bebd-7590-37337959552c@gmail.com","threadId":"52003","inReplyTo":"39740c6e58bd6cb6ea33e5abb4ab8542ff6eb7b7.1570663470.git.jonathantanmy@google.com","subject":"Re: [PATCH 3/6] index-pack: remove redundant child field","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-10-10T14:45:32Z","receivedAt":"2019-10-10T14:45:38Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/9/2019 7:44 PM, Jonathan Tan wrote:\n> Instead, recompute ancestry if we ever need to reclaim memory.\n\nI find this message lacking in important details:\n\n1. Where do we recompute ancestry?\n2. What are the performance implications of this change?\n3. Why is it important that you construct a stack of deltas in prune_base_data()?\n\n> Signed-off-by: Jonathan Tan \n> ---\n> builtin/index-pack.c | 41 ++++++++++++++++++++++-------------------\n> 1 file changed, 22 insertions(+), 19 deletions(-)\n> \n> diff --git a/builtin/index-pack.c b/builtin/index-pack.c\n> index 99f6e2957f..35f7f9e52b 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> +\tint nr = 0, alloc = 0;\n> +\tint 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\nSeems like this method should be removed and all callers should\ncall free_base_data() instead.\n\n-Stolee\n\n"},{"id":"383831","messageId":"20191010190229.100750-1-jonathantanmy@google.com","threadId":"52003","inReplyTo":"67ca2f70-361a-bebd-7590-37337959552c@gmail.com","subject":"Re: [PATCH 3/6] index-pack: remove redundant child field","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-10T19:02:29Z","receivedAt":"2019-10-10T19:02:34Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> On 10/9/2019 7:44 PM, Jonathan Tan wrote:\n> > Instead, recompute ancestry if we ever need to reclaim memory.\n> \n> I find this message lacking in important details:\n> \n> 1. Where do we recompute ancestry?\n> 2. What are the performance implications of this change?\n> 3. Why is it important that you construct a stack of deltas in prune_base_data()?\n\nThanks for taking a look at this. My original plan (as I perhaps badly\nexplained in the cover letter [1]) was to show the individual small\nsteps that I took to reach the end goal, each step still passing all\ntests, in the hope that small steps are easier to understand than one\nbig one. Hence why I didn't explain much in this commit message (and\nothers), because I thought that I might have to squash them later. But\nperhaps that is too confusing and I should have just squashed them in\nthe first place (and explain all the changes in the commit message -\nit's +177 -198, which is not too big anyway).\n\nTo answer the question anyway, the short answer is that it doesn't\nmatter because I'm going to replace this mechanism in later patches. But\na longer answer:\n\n 1. In prune_base_delta() (the stack of deltas you mention in question\n 3).\n 2. Slightly fewer pointer management during the normal course of\n operation, but an allocation if we ever need to reclaim memory.\n 3. To recompute the ancestry. We have ancestry using the \"base\"\n pointer, but I need to iterate from the oldest to newest, so I\n create an array of all the \"base\" pointers and iterate in reverse.\n\n[1] https://public-inbox.org/git/cover.1570663470.git.jonathantanmy@google.com/\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> Seems like this method should be removed and all callers should\n> call free_base_data() instead.\n\nI agree, and did it in the next patch. Here I left it to preserve the\n{link,unlink}_base_data symmetry.\n"},{"id":"384234","messageId":"20191017062015.GA10862@sigill.intra.peff.net","threadId":"52003","inReplyTo":"32ef0122a55bfbdbde0595b2aad930d83b27dd6d.1570663470.git.jonathantanmy@google.com","subject":"Re: [PATCH 1/6] index-pack: unify threaded and unthreaded code","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-10-17T06:20:15Z","receivedAt":"2019-10-17T06:20:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 09, 2019 at 04:44:17PM -0700, Jonathan Tan wrote:\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 a23454da6e..1a2600d4b3 100644\n> --- a/builtin/index-pack.c\n> +++ b/builtin/index-pack.c\n> @@ -1210,15 +1210,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\nI wondered at first if this would be a problem with NO_PTHREADS. But I\nthink since the cleanups around 2094c5e582 (index-pack: remove #ifdef\nNO_PTHREADS, 2018-11-03), we always define threaded_second_pass(), even\nif all the locks are noops and we only ever have one thread.\n\n-Peff\n"},{"id":"384235","messageId":"20191017062121.GB10862@sigill.intra.peff.net","threadId":"52003","inReplyTo":"cf6c9f6e1799c587b4defa0e874b07aa9b72548b.1570663470.git.jonathantanmy@google.com","subject":"Re: [PATCH 2/6] index-pack: remove redundant parameter","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-10-17T06:21:21Z","receivedAt":"2019-10-17T06:21:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 09, 2019 at 04:44:18PM -0700, Jonathan Tan wrote:\n\n> Signed-off-by: Jonathan Tan \n> ---\n> builtin/index-pack.c | 26 ++++++++++++--------------\n> 1 file changed, 12 insertions(+), 14 deletions(-)\n\nYeah, this seems like a good cleanup. Probably worth explaining in the\ncommit message that we can infer it from the functions themselves.\n\n-Peff\n"},{"id":"384236","messageId":"20191017062433.GC10862@sigill.intra.peff.net","threadId":"52003","inReplyTo":"20191010190229.100750-1-jonathantanmy@google.com","subject":"Re: [PATCH 3/6] index-pack: remove redundant child field","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-10-17T06:24:34Z","receivedAt":"2019-10-17T06:24:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 10, 2019 at 12:02:29PM -0700, Jonathan Tan wrote:\n\n> > On 10/9/2019 7:44 PM, Jonathan Tan wrote:\n> > > Instead, recompute ancestry if we ever need to reclaim memory.\n> > \n> > I find this message lacking in important details:\n> > \n> > 1. Where do we recompute ancestry?\n> > 2. What are the performance implications of this change?\n> > 3. Why is it important that you construct a stack of deltas in prune_base_data()?\n> \n> Thanks for taking a look at this. My original plan (as I perhaps badly\n> explained in the cover letter [1]) was to show the individual small\n> steps that I took to reach the end goal, each step still passing all\n> tests, in the hope that small steps are easier to understand than one\n> big one. Hence why I didn't explain much in this commit message (and\n> others), because I thought that I might have to squash them later. But\n> perhaps that is too confusing and I should have just squashed them in\n> the first place (and explain all the changes in the commit message -\n> it's +177 -198, which is not too big anyway).\n\nFWIW, I like the breakdown. These are tricky cleanups, and seeing them\nindividually makes it easy to verify that they don't themselves break\nanything. I think they just need more explanation.\n\n-Peff\n"},{"id":"384237","messageId":"20191017062640.GD10862@sigill.intra.peff.net","threadId":"52003","inReplyTo":"39740c6e58bd6cb6ea33e5abb4ab8542ff6eb7b7.1570663470.git.jonathantanmy@google.com","subject":"Re: [PATCH 3/6] index-pack: remove redundant child field","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-10-17T06:26:41Z","receivedAt":"2019-10-17T06:26:43Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 09, 2019 at 04:44:19PM -0700, Jonathan Tan wrote:\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> +\tint nr = 0, alloc = 0;\n\nMinor, but please use size_t for allocation variables.\n\n> +\tint i;\n\nTechnically this probably ought to be a size_t as well, but I'm much\nmore concerned about the allocation ones, where we might accidentally\noverflow and underallocate a buffer. Overflowing \"i\" would probably just\nlead to an error or bad result.\n\nI _think_ what the patch is actually doing makes sense (taking as an\nassumption that it's heading in a useful direction for the end of the\nseries).\n\n-Peff\n"},{"id":"384238","messageId":"20191017063043.GE10862@sigill.intra.peff.net","threadId":"52003","inReplyTo":"0f0ffe71c5df9129a04546b8e3ed13a3ece1b9b1.1570663470.git.jonathantanmy@google.com","subject":"Re: [PATCH 4/6] index-pack: calculate {ref,ofs}_{first,last} early","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-10-17T06:30:43Z","receivedAt":"2019-10-17T06:31:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 09, 2019 at 04:44:20PM -0700, Jonathan Tan wrote:\n\n> Whenever we make a struct base_data, immediately calculate its delta\n> children. This eliminates confusion as to when the\n> {ref,ofs}_{first,last} fields are initialized.\n\nThat _seems_ like a good idea, but I'm a little worried just because I\ndon't entirely understand why it was being done lazily before. If you've\npuzzled all that out, it would be nice to make the argument in the\ncommit message.\n\n-Peff\n"},{"id":"384239","messageId":"20191017063243.GF10862@sigill.intra.peff.net","threadId":"52003","inReplyTo":"6fcda102acd550818536c69c41c270a8058050a7.1570663470.git.jonathantanmy@google.com","subject":"Re: [PATCH 5/6] index-pack: make resolve_delta() assume base data","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-10-17T06:32:43Z","receivedAt":"2019-10-17T06:33:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 09, 2019 at 04:44:21PM -0700, Jonathan Tan wrote:\n\n> A subsequent commit will make the quantum of work smaller, necessitating\n> more locking. This commit allows resolve_delta() to be called outside\n> the lock.\n\nOK, that makes sense, I think.\n\n-Peff\n"},{"id":"384240","messageId":"20191017063554.GG10862@sigill.intra.peff.net","threadId":"52003","inReplyTo":"505d8e79cd983d5b3dfd56c4f0432ad647132957.1570663470.git.jonathantanmy@google.com","subject":"Re: [PATCH 6/6] index-pack: make quantum of work smaller","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-10-17T06:35:55Z","receivedAt":"2019-10-17T06:35:57Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 09, 2019 at 04:44:22PM -0700, Jonathan Tan wrote:\n\n> Signed-off-by: Jonathan Tan \n> ---\n> builtin/index-pack.c | 267 ++++++++++++++++++++-----------------------\n> 1 file changed, 127 insertions(+), 140 deletions(-)\n\nI think this is a good direction to go in. I confess I didn't carefully\ngo over the implementation details, since you've marked this as RFC and\nit sounds like you're mainly asking about direction. It looks pretty\nreasonable from a high level, though.\n\n-Peff\n"},{"id":"384287","messageId":"cover.1571343096.git.jonathantanmy@google.com","threadId":"52003","inReplyTo":"cover.1570663470.git.jonathantanmy@google.com","subject":"[PATCH v2 0/7] Better threaded delta resolution in index-pack","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-17T20:17:09Z","receivedAt":"2019-10-17T20:17:24Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Thanks, Stolee and Peff, for taking a look at it. Here is a v2. It is\nmostly unchanged, except for expanded commit messages and code comments.\n\nI've also added a documentation clarification that\ncore.deltaBaseCacheLimit is per-thread, appearing as the first patch in\nthis patch series.\n\nFrom patch 3 (now patch 4):\n\n> > +\tint i;\n> \n> Technically this probably ought to be a size_t as well, but I'm much\n> more concerned about the allocation ones, where we might accidentally\n> overflow and underallocate a buffer. Overflowing \"i\" would probably just\n> lead to an error or bad result.\n\nI believe this needs to be signed, since we're iterating in reverse\norder, so I made it a ssize_t instead (note the extra \"s\" in front).\n\nFrom patch 4 (now patch 5):\n\n> > Whenever we make a struct base_data, immediately calculate its delta\n> > children. This eliminates confusion as to when the\n> > {ref,ofs}_{first,last} fields are initialized.\n> \n> That _seems_ like a good idea, but I'm a little worried just because I\n> don't entirely understand why it was being done lazily before. If you've\n> puzzled all that out, it would be nice to make the argument in the\n> commit message.\n\nI've added an explanation in the commit message.\n\nJonathan Tan (7):\n Documentation: deltaBaseCacheLimit is per-thread\n index-pack: unify threaded and unthreaded code\n index-pack: remove redundant parameter\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 | 446 ++++++++++++++++++----------------\n 2 files changed, 242 insertions(+), 206 deletions(-)\n\nRange-diff against v1:\n-: ---------- > 1: 0a6777a243 Documentation: deltaBaseCacheLimit is per-thread\n1: 7562afbaa9 = 2: b19d6131e0 index-pack: unify threaded and unthreaded code\n2: a8567333dc ! 3: f01f069a08 index-pack: remove redundant parameter\n @@ Metadata\n ## Commit message ##\n index-pack: remove redundant parameter\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 +\n Signed-off-by: Jonathan Tan \n \n ## builtin/index-pack.c ##\n3: 97eddde2ec ! 4: 3359b66b84 index-pack: remove redundant child field\n @@ Metadata\n ## Commit message ##\n index-pack: remove redundant child field\n \n - Instead, recompute ancestry if we ever need to reclaim memory.\n + This is refactoring 1 of 2 to simplify struct base_data.\n +\n + In index-pack, each thread maintains a doubly-linked list of the delta\n + chain that it is currently processing (the \"base\" and \"child\" pointers\n + in struct base_data). When a thread exceeds the delta base cache limit\n + and needs to reclaim memory, it uses the \"child\" pointers to traverse\n + the lineage, reclaiming the memory of the eldest delta bases first.\n +\n + A subsequent patch will perform memory reclaiming in a different way and\n + will thus no longer need the \"child\" pointer. Because the \"child\"\n + pointer is redundant even now, remove it so that the aforementioned\n + subsequent patch will be clearer. In the meantime, reclaim memory in the\n + reverse order of the \"base\" pointers.\n \n Signed-off-by: Jonathan Tan \n \n @@ builtin/index-pack.c: static void free_base_data(struct base_data *c)\n -\t\tif (b->data && b != retain)\n -\t\t\tfree_base_data(b);\n +\tstruct base_data **ancestry = NULL;\n -+\tint nr = 0, alloc = 0;\n -+\tint i;\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 @@ builtin/index-pack.c: static void free_base_data(struct base_data *c)\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 + \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 ++\t}\n +\tfree(ancestry);\n }\n \n4: 5d9687145d ! 5: 7f18480c45 index-pack: calculate {ref,ofs}_{first,last} early\n @@ Metadata\n ## Commit message ##\n index-pack: calculate {ref,ofs}_{first,last} early\n \n + This is refactoring 2 of 2 to simplify struct base_data.\n +\n Whenever we make a struct base_data, immediately calculate its delta\n children. This eliminates confusion as to when the\n {ref,ofs}_{first,last} fields are initialized.\n \n + Before this patch, the delta children were calculated at the last\n + possible moment. This allowed the members of struct base_data to be\n + populated in any order, superficially useful when we have the object\n + contents before the struct object_entry. But this makes reasoning about\n + the state of struct base_data more complicated, hence this patch.\n +\n Signed-off-by: Jonathan Tan \n \n ## builtin/index-pack.c ##\n5: ca4997017d = 6: 910b15219f index-pack: make resolve_delta() assume base data\n6: 4f7c252a7c ! 7: 2f2e36d3ef index-pack: make quantum of work smaller\n @@ Metadata\n ## Commit message ##\n index-pack: make quantum of work smaller\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 +\n + This 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 +\n + on my laptop, clone time improved from 3m2s to 2m5s (using 3 threads,\n + which is the default).\n +\n + The solution is to have a global work stack. This stack contains delta\n + bases (objects, whether appearing directly in the packfile or generated\n + by delta resolution, that themselves have delta children) that need to\n + be processed; whenever a thread needs work, it peeks at the top of the\n + stack and processes its next unprocessed child. If a thread finds the\n + stack empty, it will look for more delta base roots to push on the stack\n + instead.\n +\n + The main weakness of having a global work stack is that more time is\n + spent in the mutex, but profiling has shown that most time is spent in\n + the resolution of the deltas themselves, so this shouldn't be an issue\n + in practice. In any case, experimentation (as described in the clone\n + command above) shows that this patch is a net improvement.\n +\n Signed-off-by: Jonathan Tan \n \n ## builtin/index-pack.c ##\n @@ builtin/index-pack.c: 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 @@ builtin/index-pack.c: struct base_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 @@ builtin/index-pack.c: static void free_base_data(struct base_data *c)\n -\tstruct base_data *b;\n -\tstruct thread_local *data = get_thread_data();\n -\tstruct base_data **ancestry = NULL;\n --\tint nr = 0, alloc = 0;\n --\tint i;\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 @@ builtin/index-pack.c: static void free_base_data(struct base_data *c)\n }\n \n static int is_delta_type(enum object_type type)\n +@@ builtin/index-pack.c: 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 @@ builtin/index-pack.c: 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 @@ builtin/index-pack.c: static int compare_ref_delta_entry(const void *a, const vo\n }\n \n -static void resolve_base(struct object_entry *obj)\n -+static void *do_work(void *data)\n - {\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 + static void *threaded_second_pass(void *data)\n + {\n -\tset_thread_data(data);\n +\tif (data)\n +\t\tset_thread_data(data);\n @@ builtin/index-pack.c: static int compare_ref_delta_entry(const void *a, const vo\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 @@ builtin/index-pack.c: static int compare_ref_delta_entry(const void *a, const vo\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 @@ builtin/index-pack.c: static int compare_ref_delta_entry(const void *a, const vo\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 @@ builtin/index-pack.c: static int compare_ref_delta_entry(const void *a, const vo\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 @@ builtin/index-pack.c: static void resolve_deltas(void)\n \tif (nr_threads > 1 || getenv(\"GIT_FORCE_THREADS\")) {\n \t\tinit_thread();\n \t\tfor (i = 0; i < nr_threads; i++) {\n - \t\t\tint ret = pthread_create(&thread_data[i].thread, NULL,\n --\t\t\t\t\t\t threaded_second_pass, thread_data + i);\n -+\t\t\t\t\t\t do_work, thread_data + i);\n - \t\t\tif (ret)\n - \t\t\t\tdie(_(\"unable to create thread: %s\"),\n - \t\t\t\t strerror(ret));\n -@@ builtin/index-pack.c: static void resolve_deltas(void)\n - \t\tcleanup_thread();\n - \t\treturn;\n - \t}\n --\tthreaded_second_pass(¬hread_data);\n -+\tdo_work(¬hread_data);\n - }\n - \n - /*\n @@ builtin/index-pack.c: 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 @@ builtin/index-pack.c: static void fix_unresolved_deltas(struct hashfile *f)\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\tdo_work(NULL); /* will pick up new object in objects array (added by append_obj_to_pack) */\n ++\t\tthreaded_second_pass(NULL);\n ++\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n \t}\n \tfree(sorted_by_pos);\n-- \n2.23.0.866.gb869b98d4c-goog\n\n"},{"id":"384288","messageId":"0a6777a2431e96f1e53110fa2ce2219420b0640c.1571343096.git.jonathantanmy@google.com","threadId":"52003","inReplyTo":"cover.1571343096.git.jonathantanmy@google.com","subject":"[PATCH v2 1/7] Documentation: deltaBaseCacheLimit is per-thread","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-17T20:17:10Z","receivedAt":"2019-10-17T20:17:33Z","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 852d2ba37a..ce1ba8d55f 100644\n--- a/Documentation/config/core.txt\n+++ b/Documentation/config/core.txt\n@@ -388,7 +388,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.23.0.866.gb869b98d4c-goog\n\n"},{"id":"384289","messageId":"f01f069a080d705ddb52e2353fa303b979a3cb78.1571343096.git.jonathantanmy@google.com","threadId":"52003","inReplyTo":"cover.1571343096.git.jonathantanmy@google.com","subject":"[PATCH v2 3/7] index-pack: remove redundant parameter","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-17T20:17:12Z","receivedAt":"2019-10-17T20:17:33Z","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 df6b3b8cf6..296804230c 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@@ -982,12 +982,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.23.0.866.gb869b98d4c-goog\n\n"},{"id":"384290","messageId":"b19d6131e01692e47eafd58bb5a9b0cd2a8c88ee.1571343096.git.jonathantanmy@google.com","threadId":"52003","inReplyTo":"cover.1571343096.git.jonathantanmy@google.com","subject":"[PATCH v2 2/7] index-pack: unify threaded and unthreaded code","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-17T20:17:11Z","receivedAt":"2019-10-17T20:17:33Z","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 60a5591039..df6b3b8cf6 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1210,15 +1210,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.23.0.866.gb869b98d4c-goog\n\n"},{"id":"384291","messageId":"3359b66b841e7eabdc45d3d937e97208b22e2901.1571343096.git.jonathantanmy@google.com","threadId":"52003","inReplyTo":"cover.1571343096.git.jonathantanmy@google.com","subject":"[PATCH v2 4/7] index-pack: remove redundant child field","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-17T20:17:13Z","receivedAt":"2019-10-17T20:17:34Z","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 296804230c..220e1e3693 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.23.0.866.gb869b98d4c-goog\n\n"},{"id":"384292","messageId":"7f18480c45193d2a54832705cd29353911ad5b83.1571343096.git.jonathantanmy@google.com","threadId":"52003","inReplyTo":"cover.1571343096.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":"2019-10-17T20:17:14Z","receivedAt":"2019-10-17T20:17:38Z","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 | 125 +++++++++++++++++++++----------------------\n 1 file changed, 61 insertions(+), 64 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 220e1e3693..d21353757d 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@@ -928,10 +910,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@@ -945,19 +942,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(result->data, result->size,\n+\thash_object_file(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@@ -983,30 +992,15 @@ 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 \t\t\tBUG(\"child->real_type != OBJ_REF_DELTA\");\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@@ -1016,11 +1010,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@@ -1028,7 +1022,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@@ -1071,9 +1065,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@@ -1367,21 +1360,25 @@ 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(&d->oid, base_obj->data,\n-\t\t\t\tbase_obj->size, type_name(type)))\n+\t\tif (check_object_signature(&d->oid, data,\n+\t\t\t\t\t size, 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.23.0.866.gb869b98d4c-goog\n\n"},{"id":"384293","messageId":"910b15219f0875663953e0087529ab19815ef3f4.1571343096.git.jonathantanmy@google.com","threadId":"52003","inReplyTo":"cover.1571343096.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":"2019-10-17T20:17:15Z","receivedAt":"2019-10-17T20:17:41Z","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 d21353757d..31607a77fc 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -926,7 +926,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@@ -941,8 +941,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@@ -1000,6 +1000,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,\n \t\t\t\t\t base->obj->real_type))\n \t\t\tBUG(\"child->real_type != OBJ_REF_DELTA\");\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@@ -1014,6 +1015,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.23.0.866.gb869b98d4c-goog\n\n"},{"id":"384294","messageId":"2f2e36d3efede79f55347ce9d80d453bb05a4e15.1571343096.git.jonathantanmy@google.com","threadId":"52003","inReplyTo":"cover.1571343096.git.jonathantanmy@google.com","subject":"[PATCH v2 7/7] index-pack: make quantum of work smaller","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-17T20:17:16Z","receivedAt":"2019-10-17T20:17:43Z","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 | 336 ++++++++++++++++++++++++-------------------\n 1 file changed, 190 insertions(+), 146 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 31607a77fc..072592a35d 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@@ -850,15 +886,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@@ -886,7 +914,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@@ -902,7 +930,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@@ -920,6 +948,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@@ -953,14 +983,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@@ -969,84 +993,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\tBUG(\"child->real_type != OBJ_REF_DELTA\");\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@@ -1065,33 +1011,128 @@ 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\tchild_obj = objects +\n+\t\t\t\t\tref_deltas[parent->ref_first++].obj_no;\n+\t\t\t\tassert(child_obj->real_type == OBJ_REF_DELTA);\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@@ -1192,6 +1233,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@@ -1362,10 +1404,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@@ -1376,11 +1416,15 @@ static void fix_unresolved_deltas(struct hashfile *f)\n \t\tif (check_object_signature(&d->oid, data,\n \t\t\t\t\t size, 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.23.0.866.gb869b98d4c-goog\n\n"},{"id":"392649","messageId":"20200228000350.GB12115@google.com","threadId":"52003","inReplyTo":"cover.1571343096.git.jonathantanmy@google.com","subject":"Re: [PATCH v2 0/7] Better threaded delta resolution in index-pack","fromName":"Josh Steadmon","fromEmail":"steadmon@google.com","sentAt":"2020-02-28T00:03:50Z","receivedAt":"2020-02-28T00:03:59Z","isPatch":true,"sender":{"key":"steadmon@google.com","avatar":"https://avatars.githubusercontent.com/u/2654920?v=4"},"body":"On 2019.10.17 13:17, Jonathan Tan wrote:\n> Thanks, Stolee and Peff, for taking a look at it. Here is a v2. It is\n> mostly unchanged, except for expanded commit messages and code comments.\n> \n> I've also added a documentation clarification that\n> core.deltaBaseCacheLimit is per-thread, appearing as the first patch in\n> this patch series.\n> \n> From patch 3 (now patch 4):\n> \n> > > +\tint i;\n> > \n> > Technically this probably ought to be a size_t as well, but I'm much\n> > more concerned about the allocation ones, where we might accidentally\n> > overflow and underallocate a buffer. Overflowing \"i\" would probably just\n> > lead to an error or bad result.\n> \n> I believe this needs to be signed, since we're iterating in reverse\n> order, so I made it a ssize_t instead (note the extra \"s\" in front).\n> \n> From patch 4 (now patch 5):\n> \n> > > Whenever we make a struct base_data, immediately calculate its delta\n> > > children. This eliminates confusion as to when the\n> > > {ref,ofs}_{first,last} fields are initialized.\n> > \n> > That _seems_ like a good idea, but I'm a little worried just because I\n> > don't entirely understand why it was being done lazily before. If you've\n> > puzzled all that out, it would be nice to make the argument in the\n> > commit message.\n> \n> I've added an explanation in the commit message.\n> \n> Jonathan Tan (7):\n> Documentation: deltaBaseCacheLimit is per-thread\n> index-pack: unify threaded and unthreaded code\n> index-pack: remove redundant parameter\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 | 446 ++++++++++++++++++----------------\n> 2 files changed, 242 insertions(+), 206 deletions(-)\n\nThis series mostly looks good to me. There were a few parts I had\ntrouble following or convincing myself were safe, so there could be some\nimprovements with comments or more explicit commit messages, but no\nproblems apart from that.\n"},{"id":"392650","messageId":"20200228000412.GC12115@google.com","threadId":"52003","inReplyTo":"f01f069a080d705ddb52e2353fa303b979a3cb78.1571343096.git.jonathantanmy@google.com","subject":"Re: [PATCH v2 3/7] index-pack: remove redundant parameter","fromName":"Josh Steadmon","fromEmail":"steadmon@google.com","sentAt":"2020-02-28T00:04:12Z","receivedAt":"2020-02-28T00:04:21Z","isPatch":true,"sender":{"key":"steadmon@google.com","avatar":"https://avatars.githubusercontent.com/u/2654920?v=4"},"body":"On 2019.10.17 13:17, Jonathan Tan wrote:\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> \n> Signed-off-by: Jonathan Tan \n> ---\n> builtin/index-pack.c | 26 ++++++++++++--------------\n> 1 file changed, 12 insertions(+), 14 deletions(-)\n> \n> diff --git a/builtin/index-pack.c b/builtin/index-pack.c\n> index df6b3b8cf6..296804230c 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\nIt looks like compare_ofs_delta_bases() could be similarly cleaned up\nhere? This seems to be the only caller.\n\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\nAnd same with compare_ref_delta_bases here.\n\n\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> @@ -982,12 +982,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> -- \n> 2.23.0.866.gb869b98d4c-goog\n> \n"},{"id":"392651","messageId":"20200228000437.GD12115@google.com","threadId":"52003","inReplyTo":"3359b66b841e7eabdc45d3d937e97208b22e2901.1571343096.git.jonathantanmy@google.com","subject":"Re: [PATCH v2 4/7] index-pack: remove redundant child field","fromName":"Josh Steadmon","fromEmail":"steadmon@google.com","sentAt":"2020-02-28T00:04:37Z","receivedAt":"2020-02-28T00:04:44Z","isPatch":true,"sender":{"key":"steadmon@google.com","avatar":"https://avatars.githubusercontent.com/u/2654920?v=4"},"body":"On 2019.10.17 13:17, Jonathan Tan wrote:\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\nI had a small complaint that we're allocating new memory in a function\nwhere we are trying to free up space, but in practice it probably\ndoesn't matter. And this is removed in a later patch anyway.\n"},{"id":"392652","messageId":"20200228000459.GE12115@google.com","threadId":"52003","inReplyTo":"2f2e36d3efede79f55347ce9d80d453bb05a4e15.1571343096.git.jonathantanmy@google.com","subject":"Re: [PATCH v2 7/7] index-pack: make quantum of work smaller","fromName":"Josh Steadmon","fromEmail":"steadmon@google.com","sentAt":"2020-02-28T00:04:59Z","receivedAt":"2020-02-28T00:05:09Z","isPatch":true,"sender":{"key":"steadmon@google.com","avatar":"https://avatars.githubusercontent.com/u/2654920?v=4"},"body":"On 2019.10.17 13:17, Jonathan Tan wrote:\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> \n> This 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> \n> on my laptop, clone time improved from 3m2s to 2m5s (using 3 threads,\n> which is the default).\n> \n> The solution is to have a global work stack. This stack contains delta\n> bases (objects, whether appearing directly in the packfile or generated\n> by delta resolution, that themselves have delta children) that need to\n> be processed; whenever a thread needs work, it peeks at the top of the\n> stack and processes its next unprocessed child. If a thread finds the\n> stack empty, it will look for more delta base roots to push on the stack\n> instead.\n> \n> The main weakness of having a global work stack is that more time is\n> spent in the mutex, but profiling has shown that most time is spent in\n> the resolution of the deltas themselves, so this shouldn't be an issue\n> in practice. In any case, experimentation (as described in the clone\n> command above) shows that this patch is a net improvement.\n> \n> Signed-off-by: Jonathan Tan \n> ---\n> builtin/index-pack.c | 336 ++++++++++++++++++++++++-------------------\n> 1 file changed, 190 insertions(+), 146 deletions(-)\n> \n> diff --git a/builtin/index-pack.c b/builtin/index-pack.c\n> index 31607a77fc..072592a35d 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\nAs a newb, the addition of a field just called \"list\" struck me as\nneeding a more descriptive name. But this makes more sense now after\nlooking at list.h. And it seems that most uses in other parts of the\ncode are similarly just named \"list\".\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\nSeeing several new shared variables made me paranoid about whether or\nnot these were thread-safe. There are already five mutexes in this file,\nbut there are no clear descriptions (apart from hints in the lock names)\nabout which locks protect which variables. It would be nice to make this\na bit more explicit.\n\nI wish we had something similar to Abseil's \"GUARDED_BY\" annotations [1]\nso that we could ensure thread safety with static analysis, but that's\nobviously out of scope for this series.\n\n[1]: https://abseil.io/docs/cpp/guides/synchronization#thread-annotations\n\n\n> @@ -920,6 +948,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\nThe extra +2 here confused me for a bit, but it makes sense now. You're\nsubtracting indices to get the length, so you want +1 to make the math\nwork out, and you're doing it across two different lists. In the edge\ncase where a list is empty, \"first\" is 0 and \"last\" is -1, so the math\nstill works out.\n\n\n> @@ -1065,33 +1011,128 @@ static int compare_ref_delta_entry(const void *a, const void *b)\n[snip]\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\nThis part made me uneasy at first, because it looks like we might be\ndoing work on shared data outside of the work lock. But just prior to\nunlocking, we parent->retain_data, so we know it won't be freed. And the\nonly part we modify is child, which I don't believe is shared with any\nother threads.\n"},{"id":"393042","messageId":"20200310212902.77827-1-jonathantanmy@google.com","threadId":"52003","inReplyTo":"20200228000412.GC12115@google.com","subject":"Re: [PATCH v2 3/7] index-pack: remove redundant parameter","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-03-10T21:29:02Z","receivedAt":"2020-03-10T21:29:08Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> It looks like compare_ofs_delta_bases() could be similarly cleaned up\n> here? This seems to be the only caller.\n\n[snip]\n\n> And same with compare_ref_delta_bases here.\n\nThat's true, although I didn't need these cleanups for the rest of my patches,\nso I think it's better to defer them to reduce the overall size of the\npatch.\n"},{"id":"393043","messageId":"20200310214206.81606-1-jonathantanmy@google.com","threadId":"52003","inReplyTo":"20200228000459.GE12115@google.com","subject":"Re: [PATCH v2 7/7] index-pack: make quantum of work smaller","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-03-10T21:42:06Z","receivedAt":"2020-03-10T21:42:13Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> > +/*\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> Seeing several new shared variables made me paranoid about whether or\n> not these were thread-safe. There are already five mutexes in this file,\n> but there are no clear descriptions (apart from hints in the lock names)\n> about which locks protect which variables. It would be nice to make this\n> a bit more explicit.\n\nI think that this patch set should confine itself to the work mutex and\nwhat it controls (since that's what this patch set is affecting), but\nadmittedly, that is already more than a handful.\n\nThe work mutex controls work_head and done_head, and all the struct\nbase_data contained therein, except for data. However, data is\ncontrolled by the semaphore retain_data (and the semaphore is itself\ncontrolled by the work mutex, as described in the previous sentence):\nwhen retain_data is positive, data can be read from but not written to.\nThe work mutex also controls base_cache_used but not base_cache_limit.\nThe work mutex does not control any struct base_data outside of\nwork_head and done_head, so it is possible to generate a struct\nbase_data outside the mutex, take the mutex, and add it to the list\n(reducing time spent in the mutex).\n\nThis scheme seems rather complicated to me, but I couldn't make it\nsimpler - I was hoping for advice on this. If this is the best we can\ndo, I can try to document it in code comments.\n\n> I wish we had something similar to Abseil's \"GUARDED_BY\" annotations [1]\n> so that we could ensure thread safety with static analysis, but that's\n> obviously out of scope for this series.\n> \n> [1]: https://abseil.io/docs/cpp/guides/synchronization#thread-annotations\n\nI think what we need is more complicated than what these annotations\nprovide, but anyway, Abseil is C++-only, I believe.\n\n> > @@ -1065,33 +1011,128 @@ static int compare_ref_delta_entry(const void *a, const void *b)\n> [snip]\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> \n> This part made me uneasy at first, because it looks like we might be\n> doing work on shared data outside of the work lock. But just prior to\n> unlocking, we parent->retain_data, so we know it won't be freed.\n\nThat's correct that it made you uneasy (I think the usual solution is to\nmake data refcounted, but we don't have a refcounting implementation in\nGit), and that's correct that my solution was that parent->retain_data\nprevents data from being concurrently written to (in this case, freed).\nI didn't know how better to implement this.\n\n> And the\n> only part we modify is child, which I don't believe is shared with any\n> other threads.\n\nYes - in the part you quoted, child is a whole new object (created from\nresolve_delta() or make_base()). It is only added to the list within the\nmutex (the work_lock()).\n"},{"id":"393044","messageId":"20200310214532.83349-1-jonathantanmy@google.com","threadId":"52003","inReplyTo":"20200228000350.GB12115@google.com","subject":"Re: [PATCH v2 0/7] Better threaded delta resolution in index-pack","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-03-10T21:45:32Z","receivedAt":"2020-03-10T21:45:37Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> This series mostly looks good to me. There were a few parts I had\n> trouble following or convincing myself were safe, so there could be some\n> improvements with comments or more explicit commit messages, but no\n> problems apart from that.\n\nThanks!\n\nFor the rest who are following along, I somehow couldn't \"git am\" these\non latest master, but I could \"git am\" these on an old master commit\n(from the time of the original work). The subsequent rebase works with\ntrivially-resolved merge conflicts except for one due to a21781011f\n(\"index-pack: downgrade twice-resolved REF_DELTA to die()\", 2020-02-04)\n- but that was fixed by changing the relevant assert() command to\nif/die().\n"}]}