| Message ID | 20190919214712.7348-1-szeder.dev@gmail.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | name-rev: eliminate recursion | expand |
On 9/19/2019 5:46 PM, 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. A noble goal! Recursion into commit history is much easier to get stack overflows than when we recurse into the directory hierarchy. > Patches 1-5 and 14-15 are while-at-it cleanups I noticed on the way, > and patch 6 improves test coverage. These cleanups are nice, and I think I followed them pretty closely. > Patches 7-11 are preparatory refactorings that are supposed to make > this series easier to follow, and make patch 12, the one finally > eliminating the recursion, somewhat shorter, and even much shorter > when viewed with '--ignore-all-space'. Patch 13 cleans up after those > preparatory steps. I responded to several of these, mostly with questions and not actual recommendations. I do want to apply your patches locally so I can try this --ignore-all-space trick to really be sure patch 12 is doing the right thing. Great organization of patches! -Stolee
On Fri, Sep 20, 2019 at 11:37:12AM -0400, Derrick Stolee wrote: > On 9/19/2019 5:46 PM, 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. > > A noble goal! Recursion into commit history is much easier to get > stack overflows than when we recurse into the directory hierarchy. > > > Patches 1-5 and 14-15 are while-at-it cleanups I noticed on the way, > > and patch 6 improves test coverage. > > These cleanups are nice, and I think I followed them pretty closely. > > > Patches 7-11 are preparatory refactorings that are supposed to make > > this series easier to follow, and make patch 12, the one finally > > eliminating the recursion, somewhat shorter, and even much shorter > > when viewed with '--ignore-all-space'. Patch 13 cleans up after those > > preparatory steps. > > I responded to several of these, mostly with questions and not actual > recommendations. I do want to apply your patches locally so I can try > this --ignore-all-space trick to really be sure patch 12 is doing the > right thing. git fetch https://github.com/szeder/git name-rev-no-recursion (But this is sort of a v1.1, as it already includes René's suggestion for patch 3.)
'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. Patches 1-5 and 14-15 are while-at-it cleanups I noticed on the way, and patch 6 improves test coverage. Patches 7-11 are preparatory refactorings that are supposed to make this series easier to follow, and make patch 12, the one finally eliminating the recursion, somewhat shorter, and even much shorter when viewed with '--ignore-all-space'. Patch 13 cleans up after those preparatory steps. SZEDER Gábor (15): t6120-describe: correct test repo history graph in comment t6120-describe: modernize the 'check_describe' helper name-rev: use strip_suffix() in get_rev_name() 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: eliminate recursion in name_rev() name-rev: cleanup name_ref() name-rev: plug a memory leak in name_rev() name-rev: plug a memory leak in name_rev() in the deref case builtin/name-rev.c | 140 ++++++++++++++++++++++++++++---------------- t/t6120-describe.sh | 72 ++++++++++++++++++----- 2 files changed, 147 insertions(+), 65 deletions(-)