Is there a way to detect Recursion in High Level language like C ? We have had terrible Resets in the last Customer Release and I am being asked to analze Semaphore deadlocks, Nested Interrupts and Stack overrun issues. We suspect that there is recursion in our sources and am interested in detecting and cleaning up all recursion. Freeware would be preferred but Commercial tools could be considered as a second option. Erich
Recursion in HLL
Started by ●January 15, 2009
Reply by ●January 15, 20092009-01-15
On Thu, 15 Jan 2009 10:26:34 -0600, Erich78 wrote:> Is there a way to detect Recursion in High Level language like C ? We > have had terrible Resets in the last Customer Release and I am being > asked to analze Semaphore deadlocks, Nested Interrupts and Stack overrun > issues. We suspect that there is recursion in our sources and am > interested in detecting and cleaning up all recursion. Freeware would be > preferred but Commercial tools could be considered as a second option. > > ErichI _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. -- Tim Wescott Control systems and communications consulting http://www.wescottdesign.com Need to learn how to apply control theory in your embedded system? "Applied Control Theory for Embedded Systems" by Tim Wescott Elsevier/Newnes, http://www.wescottdesign.com/actfes/actfes.html
Reply by ●January 15, 20092009-01-15
Erich78 wrote:> Is there a way to detect Recursion in High Level language like C ? > We have had terrible Resets in the last Customer Release and I am being > asked to analze Semaphore deadlocks, Nested Interrupts and Stack overrun > issues. We suspect that there is recursion in our sources and am interested > in detecting and cleaning up all recursion. Freeware would be preferred but > Commercial tools could be considered as a second option.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 http://www.abvolt.com
Reply by ●January 15, 20092009-01-15
On Jan 15, 11:26=A0am, "Erich78" <sanjeevraj...@yahoo.com> wrote:> Is there a way to detect Recursion in High Level language like C ? > We have had terrible Resets in the last Customer Release and I am being > asked to analze Semaphore deadlocks, Nested Interrupts and Stack overrun > issues. We suspect that there is recursion in our sources and am interest=ed> in detecting and cleaning up all recursion. Freeware would be preferred b=ut> Commercial tools could be considered as a second option. > > ErichCode 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?
Reply by ●January 15, 20092009-01-15
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 www.skandantech.com 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
Reply by ●January 15, 20092009-01-15
On 2009-01-15, Erich78 <sanjeevrajuus@yahoo.com> wrote:> Is there a way to detect Recursion in High Level language like C ?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.> We have had terrible Resets in the last Customer Release and I > am being asked to analze Semaphore deadlocks, Nested > Interrupts and Stack overrun issues. We suspect that there is > recursion in our sourcesYou _suspect_ there is recursion in your sources? Where did you get theses "sources" in which you don't know if recursion is used?> and am interested in detecting and cleaning up all recursion.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?> Freeware would be preferred but Commercial tools could be > considered as a second option.There's Joerg Schilling's calltree program: ftp://ftp.berlios.de/pub/calltree And Gnu cflow: http://www.gnu.org/software/cflow/ I know that cflow will indicate recursion, and I suspect that calltree will as well. -- Grant Edwards grante Yow! ! Up ahead! It's a at DONUT HUT!! visi.com
Reply by ●January 15, 20092009-01-15
<snippitydoodah>> You _suspect_ there is recursion in your sources? Where did > you get theses "sources" in which you don't know if recursion > is used? > > > and am interested in detecting and cleaning up all recursion. > > 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?Two very good points. This sounds like the sort of problem one might encounter while reverse engineering someone else's code...
Reply by ●January 15, 20092009-01-15
Grant Edwards wrote:> You _suspect_ there is recursion in your sources? Where did > you get theses "sources" in which you don't know if recursion > is used?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 http://www.abvolt.com
Reply by ●January 15, 20092009-01-15
On 2009-01-15, Vladimir Vassilevsky <antispam_bogus@hotmail.com> wrote:> Grant Edwards wrote: > >> You _suspect_ there is recursion in your sources? Where did >> you get theses "sources" in which you don't know if recursion >> is used? > > It is easy enough to make an occasional recursion by mistake, especially > when refacturing some older code.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. -- Grant Edwards grante Yow! Here we are in America at ... when do we collect visi.com unemployment?
Reply by ●January 15, 20092009-01-15
On Jan 15, 5:50=A0pm, Grant Edwards <gra...@visi.com> wrote:> On 2009-01-15, Vladimir Vassilevsky <antispam_bo...@hotmail.com> wrote: > > > Grant Edwards wrote: > > >> You _suspect_ there is recursion in your sources? =A0Where did > >> you get theses "sources" in which you don't know if recursion > >> is used? > > > It is easy enough to make an occasional recursion by mistake, especiall=y> > when refacturing some older code. > > I guess I've been lucky. =A0In 25 years I don't think I've ever > seen accidental recursion. =A0I'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. > > -- > Grant Edwards =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 grante =A0 =A0 =A0 =A0 ==A0 =A0 Yow! Here we are in America> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 at ==A0 =A0 =A0 =A0 =A0 =A0 =A0 ... when do we collect> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0visi.com ==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
