detect recursive C code

[Einar ?rn]

Hi all,

is there a good way to detect recursive C code in large systems? A
method or a free tool?

Best regards,
E

 

[Richard Tobin]

is there a good way to detect recursive C code in large systems? A
method or a free tool?

I don't know of anything specifically for that purpose, but many
profilers indicate recursive cycles in their output. This will only
detect recursive functions that are actually called of course.

-- Richard

 

[Mark Piffer]

Hi all,

is there a good way to detect recursive C code in large systems? A
method or a free tool?

Best regards,
E

I don't know if it meets the exact purpose, but I think GLOBAL is a
suitable tool to reverse engineer C source code and caller/callee
dependencies (http://www.gnu.org/software/global). You can of course
try doxygen (http://www.doxygen.org), it can create call-trees and
therefore should find recursions (although I never tried that)

Mark

 

[Michael Wojcik]

is there a good way to detect recursive C code in large systems? A
method or a free tool?

There are a number of static-analysis tools that generate call graphs
from C source. Loops in the call graph indicate recursion. They're
not guaranteed, though:

- If the recursion only occurs in dead code which is never actually
executed, you may have a false positive (depending on how you define
"recursive C code" for your purposes).

- It's hard for analyzers to detect recursion through function
pointers, since they'd have to check every value such a pointer can
be set to by the program; so if the code uses function pointers you
could get false negatives.

Dynamic (runtime) analysis obviously suffers from flow coverage
issues - you can't rule out recursion until you've tested all
possible flow paths through the code.

In short, it's very difficult (maybe impossible, though I don't
offhand see a proof of that; this doesn't look to me like it's
isomorphic to the halting problem) to algorithmically determine that
a given body of C code is not recursive.

A program could detect recursion at runtime (given sufficient
resources) by maintaining its own stack of tokens identifying which
functions have been called in the current path; each function on
entry checks the stack to see if it's already there, and then adds
itself to the top. The repetitive code can be hidden in macros, but
this is still not particularly fun to implement. And, of course, you
have to decide what the program does if it detects recursion.

 

[Robert Wessel]

(...) this doesn't look to me like it's
isomorphic to the halting problem) to algorithmically determine that
a given body of C code is not recursive.

Actually, it is. Informally, you need to determine that the program
can reach another particular point in the code (which is trivially
equivalent to the halting problem), given a particular starting point
before reaching another point (eg. the next line), which is an
additional complication.

A program could detect recursion at runtime (given sufficient
resources) by maintaining its own stack of tokens identifying which
functions have been called in the current path; each function on
entry checks the stack to see if it's already there, and then adds
itself to the top. The repetitive code can be hidden in macros, but
this is still not particularly fun to implement. And, of course, you
have to decide what the program does if it detects recursion.

While quite implementation dependant (and using very undefined
behavior), if you can, on your implementation, walk the stack of
activation records, it's usually pretty easy to write a routine that
saves the callers address in an auto, and then looks through all the
stack frames looking for a duplicate. All you need in each routine is
something like "{void *RecurseTest; CheckRecursion(&RecurseTest,
__LINE__);}"

 

[Einar ?rn]

dependencies (http://www.gnu.org/software/global). You can of course

try doxygen (http://www.doxygen.org), it can create call-trees and

Thanks for the answers, however I never found out how to use these
tools so I used the excelent tool cflow instead.

http://www.opengroup.org/onlinepubs/009695399/utilities/cflow.html

It prints a callgraph and marks the recursive functions.
E.

 

[Dave Thompson]

On 29 Oct 2004 15:48:59 GMT, (e-mail address removed) (Michael Wojcik)
wrote:

A program could detect recursion at runtime (given sufficient
resources) by maintaining its own stack of tokens identifying which
functions have been called in the current path; each function on
entry checks the stack to see if it's already there, and then adds
itself to the top. The repetitive code can be hidden in macros, but
this is still not particularly fun to implement. And, of course, you
have to decide what the program does if it detects recursion.

Or a static flag, (as little as) one bit, for each function.

With somewhat simpler code; but still worth hiding, and also
automating which helps prevent cut&paste or other editing errors.


- David.Thompson1 at worldnet.att.net