Recursion in HLL

I _think_ the search term you want is "static code analysis". Static code analyzer tools are used to estimate stack depth (i.e. they answer the question "how many call levels can be made"), so I assume they'd also pick up on recursive loops.

How much are you confident that the cause is in the software? BTW, on several consulting assignments they invited me to fix what they thought to be the software problems, however I ended up correcting the schematic, layout, power supply or EMI issues.

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

ed

ut

Code reviews are Free.

Apparently you have a stack dump. Have you analyzed that? Does it show recursion??

Nested Interrupts are not recursion. Have you finally overloaded your processor to the point that it cannot complete one interrupt before another one comes in? Have you done timings?

Are you using an RTOS?

Received many mails about possible options. One suggested QAC from Programming Research. That looks like quite an expensive tool for a Small Business. Did a Google on "Recursion QAC" and found a different hit called

They seem to offer a tool called RecurSiv which would detect direct and indirect recursion. Any experience with these tools ?

I have already spent a day with cflow (freeware) and cygwin and got no where.

Erich

You can do an analysis of a static call-tree to detect cycles, but there's nothing you can really do to detect recursion that may happen at run-time if the software uses function pointers. I suspect you end up with something akin to the halting problem.

You _suspect_ there is recursion in your sources? Where did you get theses "sources" in which you don't know if recursion is used?

Huh? If you've implemented an algorithm using recursion, then how do you propose to "clean up" that recursion without trying to solve the halting problem?

There's Joerg Schilling's calltree program:

ftp://ftp.berlios.de/pub/calltree

And Gnu cflow:

I know that cflow will indicate recursion, and I suspect that calltree will as well.

Two very good points. This sounds like the sort of problem one might encounter while reverse engineering someone else's code...

It is easy enough to make an occasional recursion by mistake, especially when refacturing some older code. Something like that:

void Foo() { Crap(); if(something) Bar(); Trash(); Rubbish(); }

void Bar() { Bla_Bla_Bla(); Nonsense(); Foo(); }

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

I guess I've been lucky. In 25 years I don't think I've ever seen accidental recursion. I've seen plenty of stack and buffer overflows and underflows, infinite loops, uninitialized or null pointers dereferenced, and various other things that make boards reset. But, I can honestly say that unintentional recursion is a new one for me.

I have also seen intentional recursion that never terminated due to buggy logic in the code, but I don't think that's what the OP is talking about.

=A0 =A0 Yow! Here we are in America

=A0 =A0 =A0 =A0 =A0 =A0 =A0 ... when do we collect

=A0 =A0 =A0 =A0 =A0 =A0unemployment?

I also suspect it is not recursion. He hinted at "nested interrupts". Also, I guess he has no RTOS.

Ed

Recursion is sometimes useful, because some tasks are easier to express with a recursion, which is no problem, if you take care of the stack size and recursion depth. But I assume you mean unintended recursion, like Vladimir described.

Usually the reason for unintended recursion is a problem in the clean separation (and documentation) of layers or components. E.g. if you are using the MVC pattern in a GUI program, and if the data layer is calling the GUI layer (which is not allowed in the MVC pattern, but can be implemented by unskilled programmers), because the GUI layer calls the data layer, which can lead to unintended recursions.

I would suggest that first you reproduce the problem. Then you can analyze it and fix it. But in the long term, you should analyze and document the components of your software and write regression tests for it. Documentation includes component descriptions, sequence diagrams, state diagrams, high level descriptions and dependencies of the layers in the program and how they interact, e.g. the GUI thread calls the I2C driver, but the I2C driver must not call the GUI layer.

For timing issues, the use of an oscilloscope and some GPIO ports can be useful, e.g. to see if there is some more time available for interrupts or if you are already at the limit. You have to make sure, that you are measuring the worst case. Maybe execute the interrupt function twice on each interrupt, if possible, so that you can be sure that the ususal processing time is ok.

Well, any recursive algorithm can be implemented without recursion, as we learn in CS 101. Of course, sometimes this amount to just implementing the stack by hand, and sometimes it just means you're doing tail-call elimination by hand, but sometimes it can make things more efficient or compact.

Given the OP's request, I would wonder if the problem is recursion per se, or just an excessively deep call tree (recursive or not) blowing the stack.

It may also be accidental re-entrancy that's the issue, rather than recursion - that's a far more common problem.

cflow is not "freeware" - it is free and open source software (look up the difference, such as at ).

An alternative that could be very useful in understanding the code is to use doxygen to generate linked source code files and call graphs - recursion will show up as loops in the call graphs.

But be aware that no call graph software will be able to see where interrupt functions are "called" - you have to do some manual tracking to fit them into the big picture.

Indeed. And it's not something that any of the call-tree programs I've seen will detect. Not that it would be difficult to do so -- you'd just need to compare the call-trees starting at each thread entry point and find functions that are present in more than one of the trees.

Code reviews are a good idea but are, unless your time is worthless, not free.

This would be more difficult, because sometimes functions are used from different threads without problems, because they are reentrant (e.g. many libc functions). But for other cases even if the call tree doesn't show problems, two threads could access the same data which can cause problems, if not locked with some mutex concept.

In C it is difficult, but the OP was not clear about the language he used (he wrote "like C"). E.g. in Haskell or other functional languages, it would be much easier to prove the correcteness of a program, even if interrupts and multithreading is used.

It's not difficult to detect which functions are being called re-entrantly (is that word?), but you're going to get a lot more "hits" and most of them will be OK because the function is re-entrant.

True, but that's a different class of problem.

Erich, You could try

Though their website does not list it, you could mail them for a cheaper version of the tool which does not offer Excel reports claiming to be Small Business or OpenSource.