[PATCH 30/32] builtin/index-pack: Make the stack in compute_compat_oid explicit
- From
Eric W. Biederman <ebiederm@xmission.com>
- Date
- Sep 8, 2023, 23:10 UTC
- Message-ID
- <20230908231049.2035003-30-ebiederm@xmission.com>
- In-Reply-To
- <87sf7ol0z3.fsf@email.froward.int.ebiederm.org>
Testing index-pack generating the compatibilty hashes on a large repository (in this case the linux kernel) resulted in a stack overflow. I confirmed this by using ulimit -s to force the stack to a much larger size, and rerunning the test and the code succeeded. Still it is not a good look to overflow the stack in the default configuration.
Ideally the objects would be ordered such that no object has any references to any object that comes after it. With such an ordering convert_object_file followed by hash_object_file to could just be on every object in order to compute the compatibility hashes for every object.
Unfortunately the work to compute such an order is roughly equaivalent to the depth first processing compute_compat_oid is doing. The objects have to be loaded to get which other objects they reference. Knowning which objects reference which others is necessary to compute such an order.
Long story short I can see how to move the depth first traversal into a topological sort, but that just moves the problem that caused the deep recursion into another function, and makes everything more expensive by requiring reading the objects yet another time.
Avoid stack overflow by using an explicitly stack made of heap allocated objects instead of using the C call stack.
To get a feel for how much this explicit stack consumes I instrumented up the code. Testing against a linux kernel 2.16GiB packfile. This packfile had 9,033,248 objects, and 7,470,317 deltas. There were 6,543,758 mappings that cound not be computed opportunistically when the data was first read. In the function compute_compat_oid I measured a maximum cco stack depth of 66,415. I measured a maximum memory consumption of 103,783,520 bytes, or about 1563 bytes per level of the stack. In short call it 100MiB extra to compute the mappings in a 2GiB packfile.
Signed-off-by: "Eric W. Biederman" <ebiederm@xmission.com> --- builtin/index-pack.c | 106 +++++++++++++++++++++++++++++-------------- 1 file changed, 71 insertions(+), 35 deletions(-)
diff --git a/builtin/index-pack.c b/builtin/index-pack.c index f5da671ed82d..6827d14b91ce 100644 --- a/builtin/index-pack.c +++ b/builtin/index-pack.c @@ -2015,54 +2015,90 @@ static void *get_object_data(struct object_entry *obj, size_t *result_size) return NULL; /* The code never reaches here */ } -static void compute_compat_oid(struct object_entry *obj) -{ - struct repository *repo = the_repository; - const struct git_hash_algo *algo = repo->hash_algo; - const struct git_hash_algo *compat = repo->compat_hash_algo; +struct cco { + struct cco *prev; + struct object_entry *obj; struct object_file_convert_state state; - struct strbuf out = STRBUF_INIT; + struct strbuf out; size_t data_size; void *data; - int ret; +}; - if (obj->idx.compat_oid.algo) - return; +static struct cco *cco_push(struct cco *prev, struct object_entry *obj) +{ + struct repository *repo = the_repository; + const struct git_hash_algo *algo = repo->hash_algo; + const struct git_hash_algo *compat = repo->compat_hash_algo; + struct cco *cco; if (obj->real_type == OBJ_BLOB) - die("Blob object not converted"); + BUG("Blob object not converted"); - data = get_object_data(obj, &data_size); + cco = xmallocz(sizeof(*cco)); + cco->prev = prev; + cco->obj = obj; + strbuf_init(&cco->out, 0); - convert_object_file_begin(&state, &out, algo, compat, - data, data_size, obj->real_type); + cco->data = get_object_data(obj, &cco->data_size); - for (;;) { - struct object_entry *pobj; - ret = convert_object_file_step(&state); - if (ret != 1) - break; - /* Does it name an object in the pack? */ - pobj = find_in_oid_index(&state.oid); - if (pobj) { - compute_compat_oid(pobj); - oidcpy(&state.mapped_oid, &pobj->idx.compat_oid); - } else if (repo_oid_to_algop(repo, &state.oid, compat, - &state.mapped_oid)) - die(_("No mapping for oid %s to %s\n"), - oid_to_hex(&state.oid), compat->name); - } - convert_object_file_end(&state, ret); - if (ret != 0) - die(_("Bad object %s\n"), oid_to_hex(&obj->idx.oid)); - hash_object_file(compat, out.buf, out.len, obj->real_type, - &obj->idx.compat_oid); - strbuf_release(&out); + convert_object_file_begin(&cco->state, &cco->out, algo, compat, + cco->data, cco->data_size, obj->real_type); + return cco; +} - free(data); +static struct cco *cco_pop(struct cco *cco, int ret) +{ + struct repository *repo = the_repository; + const struct git_hash_algo *compat = repo->compat_hash_algo; + struct cco *prev = cco->prev; + + convert_object_file_end(&cco->state, ret); + if (ret != 0) + die(_("Bad object %s\n"), oid_to_hex(&cco->obj->idx.oid)); + hash_object_file(compat, cco->out.buf, cco->out.len, + cco->obj->real_type, &cco->obj->idx.compat_oid); + strbuf_release(&cco->out); + if (prev) + oidcpy(&prev->state.mapped_oid, &cco->obj->idx.compat_oid); nr_resolved_mappings++; display_progress(progress, nr_resolved_mappings); + + free(cco->data); + free(cco); + + return prev; +} + +static void compute_compat_oid(struct object_entry *obj) +{ + struct repository *repo = the_repository; + const struct git_hash_algo *compat = repo->compat_hash_algo; + struct cco *cco; + + cco = cco_push(NULL, obj); + for (;cco;) { + struct object_entry *pobj; + + int ret = convert_object_file_step(&cco->state); + if (ret != 1) { + cco = cco_pop(cco, ret); + continue; + } + + /* Does it name an object in the pack? */ + pobj = find_in_oid_index(&cco->state.oid); + if (pobj && pobj->idx.compat_oid.algo) + oidcpy(&cco->state.mapped_oid, &pobj->idx.compat_oid); + else if (pobj) + cco = cco_push(cco, pobj); + else if (repo_oid_to_algop(repo, &cco->state.oid, compat, + &cco->state.mapped_oid)) + die(_("When converting %s no mapping for oid %s to %s\n"), + oid_to_hex(&cco->obj->idx.oid), + oid_to_hex(&cco->state.oid), + compat->name); + } } static void compute_compat_oids(void)
-- 2.41.0