stack overflow running `git stack`

[kaspar030]

• [X] I have searched the discussions
• [X] I have searched the existing issues

Description

I just installed git-stack using cargo install --locked on an up-to-date Arch linux installation.

Then, running git-stack leads to some 40 sec of 100% CPU usage, git-stack then stack overflows.

Version

git-stack 0.2.9

Steps to reproduce

This was on my local clone of kaspar030/RIOT, which has a lot of branches. I just typed git-stack there.

How can I provide more context?

Actual Behaviour

riot on  master via ⍱ 
❯ git-stack

thread 'main' has overflowed its stack
fatal runtime error: stack overflow
Aborted (core dumped)
riot on  master via ⍱ took 41s 
❯

Expected Behaviour

I don't know the expected output.

Debug Output

https://gist.github.com/kaspar030/b2e524241f7403abc2864181421d94cc

[epage]

Ouch, hadn't tested on a big repo yet and I can see that happening. This uses recursion a lot.

As a workaround setting stack.stack to descendants will probably avoid the worse problems.

I might be able to insert some hacks to workaround this but I'm looking at a more fundamental change in our data structure that makes it easier to iterate rather than recurse.

[epage]

@kaspar030 I just published v0.4.2 which should have all stackoverflows addressed.

[kaspar030]

I tried v0.4.5:

❯ git stack
WARN: Branches contain more than 50 commits (should these be protected?): 6lowpanm move_lifo_to_sysm rebased/cenk/pr/rpl/xtimer_switchm xtimer_shoot_earlym swie_802154_rxm swie_802154_freym nano_ltom 2016.10-branch-GNRC-measurementm 2016.10-branch-GNRC-measurement-L2-netdev1m regit/base/make_periph_use_submodulesm nanonet_minimizem add_cc2650_rfcm nanonet_testm msp430fr5969m regit/base/suit_minimalm ota_suit_v2_testm pr/ota_suit_v2/add_cosem ota_suit_v3m suitm pr/suit-dev/cleanup_debugm suit-dev_cim regit/base/rework_key_handlingm regit/base/suit-dev-prm rebased/rework_key_handlingm rework_key_handlingm regit/base/suit-dev_ci_rebasedm regit/tmp/suit-dev-prm suit-dev-prm pr/tools/suit_v4_rm_python_scriptsm pr/suit/document_suitm regit/base/suit-dev-cim suit-devm fix_typos2m regit/base/ztimer_testm laze_pythonm pr14055m pr13824m pr14749m nanonet

thread 'main' has overflowed its stack
fatal runtime error: stack overflow
error: git-stack died of signal 6

[epage]

Can you run with -vv?

I'm going to assume it'll flood your screen but I'm most interested in the general area its doing a stackoverflow, since I had thought I had gotten all the spots, and even with the tests I'm looking at adding, there are a lot of configuration differences that can change what path we hit.

[arxanas]

@epage I'm not sure exactly what the cause of your stack overflows here are, but maybe it would help you to use the Eden SCM DAG implementation? I integrated it into git-branchless in this release: https://github.com/arxanas/git-branchless/releases/tag/v0.3.5. It provided significant performance improvements for many operations (such as smartlog time 3s-> 10ms), and is naturally not recursive.

It lets you do things like query descendant commits very efficiently; see https://github.com/quark-zju/gitrevset for example operations. It also significantly decreases the amount of graph-related code you have to write yourself. (But it's GPL-2 licensed...)

[kaspar030]

Can you run with -vv?

Could've thought of that. here: https://gist.github.com/kaspar030/800ad8db4d26d3a94efac99dc2759ada

[kaspar030]

when running in rust-gdb, I can see that it recurses in git_stack::stack::to_tree ().

[kaspar030]

This is the bottom of the stack trace:

#22755 0x00005555555bd089 in git_stack::stack::to_tree ()
#22756 0x00005555555bc8ef in <git_stack::stack::DisplayTree as core::fmt::Display>::fmt ()
#22757 0x0000555555849a9c in core::fmt::write () at library/core/src/fmt/mod.rs:1110
#22758 0x000055555582089e in std::io::Write::write_fmt<std::io::stdio::StdoutLock> () at library/std/src/io/mod.rs:1639
#22759 std::io::stdio::{{impl}}::write_fmt () at library/std/src/io/stdio.rs:657
#22760 0x0000555555820833 in std::io::stdio::{{impl}}::write_fmt () at library/std/src/io/stdio.rs:631
#22761 0x00005555555b7e9a in git_stack::stack::stack ()
#22762 0x00005555555e968f in git_stack::run ()
#22763 0x00005555555e8960 in git_stack::main ()
#22764 0x00005555555c8973 in std::sys_common::backtrace::__rust_begin_short_backtrace ()
#22765 0x00005555555e52f9 in std::rt::lang_start::{{closure}} ()
#22766 0x00005555558283e9 in core::ops::function::impls::{{impl}}::call_once<(),Fn<()>> () at /rustc/149f4836dd6d9e789a26dca16dc034588866894e/library/core/src/ops/function.rs:259
#22767 std::panicking::try::do_call<&Fn<()>,i32> () at library/std/src/panicking.rs:401
#22768 std::panicking::try<i32,&Fn<()>> () at library/std/src/panicking.rs:365
#22769 std::panic::catch_unwind<&Fn<()>,i32> () at library/std/src/panic.rs:434
#22770 std::rt::lang_start_internal () at library/std/src/rt.rs:34
#22771 0x00005555555e9b02 in main ()

Looks like it stack overflows inside another panic. (not sure about this)

[epage]

Thanks, I've got a local reproduction. Looks like there was a case I missed in protecting against stackoverflows. We have one data structure for processing but then we have to re-shape it to graph the series of commits. This conversion is where I had missed a part. I made it so we don't show as many commits, but we still process just as many.

[epage]

I've got a change that reduces the chance for overflow (down to just --format commits). Removing it completely will be a bit more work.

@arxanas I'll keep that in mind. At least for right now, processing 10,000 commits seems to only take 0.7s in a debug build and 10,000 commits is a pathological case most likely hit when someone is first adopting git-stack and has not configured their protected branches.

[epage]

@kaspar030 I just published v0.4.6 with my latest fix. This works for me except with --format commits.

I'm assuming most of those 50+ commit branches are shared branches and that you'll want to mark them as protected so we don't try to modify their history. This will also speed up git-stack since we won't have to process as much. You can mark them as protected in .git/config with a simple git stack --protect <glob>

If they are not shared branches, I would definitely be interested in hearing more of your use case :).

[kaspar030]

@kaspar030 I just published v0.4.6 with my latest fix. This works for me except with --format commits.

It doesn't crash anymore here, with or without --format commits. Thanks a lot!