Getting stuck in CheckStl::invalidContainer()

[Steven Blackburn]

We recently upgraded from cppcheck 2.4.1 to 2.6 and now find that cppcheck gets stuck processing a specific file. The file is ~3.5ksloc and seems to depend on other files (presumably the includes) so is not practical to post as an issue (and is closed source). While checking v2.5 and compiling / running gdb on the latest version is on my TODO list it will take a while to reach the top, so I generated stack traces, using pstack, which suggests it has got stuck in CheckStl::invalidContainer() with lots of calls to forwardRange()... the extract below shows omits the first 28 calls to forwardRange:

  #29 0x000000000063146a in PathAnalysis::forwardRange(Token const*, Token const*, PathAnalysis::Info, std::function<PathAnalysis::Progress (PathAnalysis::Info const&)> const&) const ()
  #30 0x00000000006319e8 in PathAnalysis::forward(std::function<PathAnalysis::Progress (PathAnalysis::Info const&)> const&) const ()
  #31 0x0000000000631b0b in reaches(Token const*, Token const*, Library const&, std::list<std::pair<Token const*, std::string>, std::allocator<std::pair<Token const*, std::string> > >*) ()
  #32 0x000000000056a798 in std::_Function_handler<bool (PathAnalysis::Info const&), CheckStl::invalidContainer()::{lambda(PathAnalysis::Info const&)#1}>::_M_invoke(std::_Any_data const&, PathAnalysis::Info const&) ()
  #33 0x000000000057408d in std::_Function_handler<PathAnalysis::Progress (PathAnalysis::Info const&), PathAnalysis::forwardFind(std::function<bool (PathAnalysis::Info const&)>)::{lambda(PathAnalysis::Info const&)#1}>::_M_invoke(std::_Any_data const&, PathAnalysis::Info const&) ()
  #34 0x0000000000631325 in PathAnalysis::forwardRange(Token const*, Token const*, PathAnalysis::Info, std::function<PathAnalysis::Progress (PathAnalysis::Info const&)> const&) const ()
  #35 0x0000000000630de5 in PathAnalysis::forwardRange(Token const*, Token const*, PathAnalysis::Info, std::function<PathAnalysis::Progress (PathAnalysis::Info const&)> const&) const ()
  #36 0x00000000006319e8 in PathAnalysis::forward(std::function<PathAnalysis::Progress (PathAnalysis::Info const&)> const&) const ()

Does this sound related to any recent changes... I did look, but 400+ files have changed, including style tweaks, which makes it a non-starter for someone unfamiliar with the codebase.

Does anyone have any hints on how to turn this into a useful issue?

Steve.

[Daniel Marjamäki]

If we are lucky Cppcheck hangs on some specific piece of code in your source file.

I would try to reduce the code. Try to remove includes/functions/etc in your code.. does the hang remain if you remove all code below line number 2000 for instance. does the hang remain if you remove all includes except the sourcefile header. etc..

Ideally it would be possible to reduce it to a small piece of code.

Your question suggests that the hang seems to depend on various includes lets hope not.

[Steven Blackburn]

The code is resistant to a simple binary chop: I suspect due to the points in the problem path being in more than one area of the file. I can lose 1000 lines near the top, but that is about it. It does depend on a couple of include files, I think to get the class / function definitions.

I bit the bullet and compiled from source so can tell from the backtrace in gdb that it is bouncing between lines 110 and 123 of pathanalysis.cpp. I even added some debug output to forwardRange to try and find the problem lines, but the program will happily run between 15 and 46 calls deep for hours on end. Looking at the areas of the file it spends most time in doesn't reveal a "smoking gun" ... it could appear like a recursive function, with SomeClass::SomeFunction(int data) calling object.SomeFunction(data)... the "object" is not of type SomeClass though... and if cppcheck was treating it as recursive I suspect the problem would be more obvious.

One of the problems when trying to cut down the file is that sometimes cppcheck would take a long time to return (e.g. 1.5 mins) rather than just hang... combined with the calls between the functions means removing one function at a time (of over 125), then waiting a couple of minutes to check it had hung.... which isn't practical.

I've spent as long as I can on this now, especially as it isn't stopping me working as I can tell cppcheck to ignore the file. I am happy to try something quick + targeted, including instrumenting the code, but bear in mind this worked in 2.4.1, so something has changed fairly recently.

[Daniel Marjamäki]

thanks for your effort. hmm sounds tricky. :-(

[Paul Fultz]

What I have done in the past to find test cases that hang(or take a really long time), is to add code to abort after a function is called so many times:

void f() {
    static int count = 0;
    count++;
    if (count > 1000) {
        std::printf("Called\n");
        std::abort();
    }
    ...
}

Then you can use creduce to reduce the source file. We have a python script under tools/ to help call creduce(you will need to install creduce to use this script):

python3 tools/creduce.py -t 'Called' -f source.cpp -c 'clang++ -fsyntax-only -Wall -Werror' ./bin/cppcheck

You will need to add the includes and defines to the -c 'clang++ -fsyntax-only -Wall -Werror' flag so clang can compile the file correctly(which is used to keep creduce from creating a completely invalid program). Also this will modify the source file so make sure you have a copy. It also good to use a Release build of cppcheck for this.

There is also the tools/reduce.py python script as well, you can try(which doesn't need creduce or a compiler command), but this doesn't always reduce the program as much. Although I sometimes use this script to reduce the file somewhat and then fix it up to compiler and then run it through creduce.

[Paul Fultz]

We recently upgraded from cppcheck 2.4.1 to 2.6

In cppcheck 2.4, invalidContainer was updated to analyze across functions:

https://trac.cppcheck.net/ticket/9133

Although there hasn't been any significant changes to invalidContainer and PathAnalysis. You may want to use linux perf to figure out where its spending most of its time(you dont have to wait for the program to terminate to get a perf report).

[Jens Yllman]

#10933 is also about invalidContainer and PathAnalysis. In the test I have not come to any crash. But it takes very long time. I have not run it long enough to finish or crash. And running it in the debugger just show it SLOWLY going forward.

I am running my tests on cppcheck 2.7.

[Jens Yllman]

So if you look at the example in #10933 it is the size of the file that make it take very long time. If you cut it down it will go quicker.

If you profile the run you till see that Token::multiCompare() will take up most of the time. And like PathAnalysis::forwardRange the rest of the time. And multiCompare() is maybe a result of all the calls to Token::Match() in forwareRange(). I have no real solution at the moment. Maybe limiting the tokens called with multiCompare(), cause it looks like it is seaching for scope in forwardRange().