| Message ID | 20191209115258.9281-1-szeder.dev@gmail.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | name-rev: eliminate recursion | expand |
On 12/9/2019 6:52 AM, SZEDER Gábor wrote: > 'git name-rev' is implemented using a recursive algorithm, and, > consequently, it can segfault in deep histories (e.g. WebKit), and > thanks to a test case demonstrating this limitation every test run > results in a dmesg entry logging the segfaulting git process. > > This patch series eliminates the recursion. > > Changes since v2: > > - Add the new patch 12 to use 'name->tip_name' instead of > 'tip_name', to make the patch eliminating the recursion a bit even > easier to follow (only with '--ignore-all-space', though, without > that option that patch's diff is still mostly gibberish). > The end result is the still same, see the empty interdiff. This new commit makes sense, and I see how it adjusts the context lines in the patch that follows. This series looks good to me. Thanks, -Stolee
Derrick Stolee <stolee@gmail.com> writes: > On 12/9/2019 6:52 AM, SZEDER Gábor wrote: >> 'git name-rev' is implemented using a recursive algorithm, and, >> consequently, it can segfault in deep histories (e.g. WebKit), and >> thanks to a test case demonstrating this limitation every test run >> results in a dmesg entry logging the segfaulting git process. >> >> This patch series eliminates the recursion. >> >> Changes since v2: >> >> - Add the new patch 12 to use 'name->tip_name' instead of >> 'tip_name', to make the patch eliminating the recursion a bit even >> easier to follow (only with '--ignore-all-space', though, without >> that option that patch's diff is still mostly gibberish). >> The end result is the still same, see the empty interdiff. > > This new commit makes sense, and I see how it adjusts the context lines > in the patch that follows. This series looks good to me. I've finished eyeballing the patches myself, and they seem to be in a good shape, too. Thanks.
'git name-rev' is implemented using a recursive algorithm, and, consequently, it can segfault in deep histories (e.g. WebKit), and thanks to a test case demonstrating this limitation every test run results in a dmesg entry logging the segfaulting git process. This patch series eliminates the recursion. Changes since v2: - Add the new patch 12 to use 'name->tip_name' instead of 'tip_name', to make the patch eliminating the recursion a bit even easier to follow (only with '--ignore-all-space', though, without that option that patch's diff is still mostly gibberish). The end result is the still same, see the empty interdiff. - Minor commit message updates (a typofix and René's signoff). v2: https://public-inbox.org/git/20191112103821.30265-1-szeder.dev@gmail.com/ v1: https://public-inbox.org/git/20190919214712.7348-1-szeder.dev@gmail.com/T/#u René Scharfe (1): name-rev: use strbuf_strip_suffix() in get_rev_name() SZEDER Gábor (13): t6120-describe: correct test repo history graph in comment t6120-describe: modernize the 'check_describe' helper name-rev: avoid unnecessary cast in name_ref() name-rev: use sizeof(*ptr) instead of sizeof(type) in allocation t6120: add a test to cover inner conditions in 'git name-rev's name_rev() name-rev: extract creating/updating a 'struct name_rev' into a helper name-rev: pull out deref handling from the recursion name-rev: restructure parsing commits and applying date cutoff name-rev: restructure creating/updating 'struct rev_name' instances name-rev: drop name_rev()'s 'generation' and 'distance' parameters name-rev: use 'name->tip_name' instead of 'tip_name' name-rev: eliminate recursion in name_rev() name-rev: cleanup name_ref() builtin/name-rev.c | 147 +++++++++++++++++++++++++++++--------------- t/t6120-describe.sh | 72 +++++++++++++++++----- 2 files changed, 153 insertions(+), 66 deletions(-) Interdiff against v2: Range-diff against v2: 1: 8d70ed050d = 1: 8d70ed050d t6120-describe: correct test repo history graph in comment 2: 3720b6859d ! 2: d2091869c8 t6120-describe: modernize the 'check_describe' helper @@ Commit message 'test_expect_success' blocks, with extra hand-rolled code to record and examine its exit code. - Update this helper and move the 'git decribe' invocation inside the + Update this helper and move the 'git describe' invocation inside the 'test_expect_success' block. Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com> 3: ad2f2eee68 ! 3: 9d13032871 name-rev: use strbuf_strip_suffix() in get_rev_name() @@ Commit message string to the strbuf and then use strbuf_strip_suffix(), making the code more idiomatic. - [TODO: René's signoff!] + Signed-off-by: René Scharfe <l.s.r@web.de> Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com> ## builtin/name-rev.c ## 4: c86a2ae2d0 = 4: b1a8d7ce03 name-rev: avoid unnecessary cast in name_ref() 5: 4fc960cc05 = 5: 3497d0bc42 name-rev: use sizeof(*ptr) instead of sizeof(type) in allocation 6: 1493cb4484 = 6: 43cba1a369 t6120: add a test to cover inner conditions in 'git name-rev's name_rev() 7: fc842e578b = 7: 7053fc707c name-rev: extract creating/updating a 'struct name_rev' into a helper 8: 7f182503e2 = 8: 28d957df88 name-rev: pull out deref handling from the recursion 9: 0cdd40b75b = 9: 5bd4dede3d name-rev: restructure parsing commits and applying date cutoff 10: e1733e3c56 = 10: 92f3897ff3 name-rev: restructure creating/updating 'struct rev_name' instances 11: bd6e2e6d87 = 11: cd24270f23 name-rev: drop name_rev()'s 'generation' and 'distance' parameters -: ---------- > 12: f33c0bbfd0 name-rev: use 'name->tip_name' instead of 'tip_name' 12: 0cf63c6d64 ! 13: e5d7d291bd name-rev: eliminate recursion in name_rev() @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit + distance = name->distance + 1; + } -- strip_suffix(tip_name, "^0", &len); +- strip_suffix(name->tip_name, "^0", &len); - if (name->generation > 0) -- new_name = xstrfmt("%.*s~%d^%d", (int)len, tip_name, +- new_name = xstrfmt("%.*s~%d^%d", +- (int)len, +- name->tip_name, - name->generation, - parent_number); - else -- new_name = xstrfmt("%.*s^%d", (int)len, tip_name, +- new_name = xstrfmt("%.*s^%d", (int)len, +- name->tip_name, - parent_number); - generation = 0; - distance = name->distance + MERGE_TRAVERSAL_WEIGHT; - } else { -- new_name = tip_name; +- new_name = name->tip_name; - generation = name->generation + 1; - distance = name->distance + 1; + if (create_or_update_name(parent, new_name, taggerdate, 13: 316f7af43c = 14: 0b556389a3 name-rev: cleanup name_ref()