[00/15] name-rev: eliminate recursion
mbox series

Message ID 20190919214712.7348-1-szeder.dev@gmail.com
Headers show
Series
  • name-rev: eliminate recursion
Related show

Message

SZEDER Gábor Sept. 19, 2019, 9:46 p.m. UTC
'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(-)

Comments

Derrick Stolee Sept. 20, 2019, 3:37 p.m. UTC | #1
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
SZEDER Gábor Sept. 20, 2019, 5:37 p.m. UTC | #2
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.)