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.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. -- Frank Buss, fb@frank-buss.de http://www.frank-buss.de, http://www.it4-systems.de
Recursion in HLL
Started by ●January 15, 2009
Reply by ●January 16, 20092009-01-16
Reply by ●January 16, 20092009-01-16
In article <l5mdnXWqNYqWAPLUnZ2dnUVZ_gydnZ2d@posted.visi>, Grant Edwards <grante@visi.com> wrote:>On 2009-01-15, Erich78 <sanjeevrajuus@yahoo.com> wrote: >> 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?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. -- Wim Lewis <wiml@hhhh.org>, Seattle, WA, USA. PGP keyID 27F772C1 "We learn from history that we do not learn from history." -Hegel
Reply by ●January 16, 20092009-01-16
Ed Prochak wrote:> On Jan 15, 5:50 pm, 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? 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? > > I also suspect it is not recursion. He hinted at "nested interrupts". > Also, I guess he has no RTOS. >It may also be accidental re-entrancy that's the issue, rather than recursion - that's a far more common problem.
Reply by ●January 16, 20092009-01-16
Erich78 wrote:> 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. > > Erichcflow is not "freeware" - it is free and open source software (look up the difference, such as at <http://en.wikipedia.org/wiki/Freeware>). 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.
Reply by ●January 16, 20092009-01-16
On 2009-01-16, David Brown <david.brown@hesbynett.removethisbit.no> wrote:>> I also suspect it is not recursion. He hinted at "nested >> interrupts". Also, I guess he has no RTOS. > > It may also be accidental re-entrancy that's the issue, rather > than recursion - that's a far more common problem.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. -- Grant Edwards grante Yow! FROZEN ENTREES may at be flung by members of visi.com opposing SWANSON SECTS ...
Reply by ●January 16, 20092009-01-16
Ed Prochak schreef:> On Jan 15, 11:26 am, "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 interested >> in detecting and cleaning up all recursion. Freeware would be preferred but >> Commercial tools could be considered as a second option. >> >> Erich > > Code reviews are Free.Code reviews are a good idea but are, unless your time is worthless, not free.
Reply by ●January 16, 20092009-01-16
Grant Edwards wrote:> 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.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. -- Frank Buss, fb@frank-buss.de http://www.frank-buss.de, http://www.it4-systems.de
Reply by ●January 16, 20092009-01-16
On 2009-01-16, Frank Buss <fb@frank-buss.de> wrote:> Grant Edwards wrote: > >> 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. > > This would be more difficult, because sometimes functions are used from > different threads without problems, because they are reentrant (e.g. many > libc functions).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.> 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.True, but that's a different class of problem.> 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.-- Grant Edwards grante Yow! Here I am in the at POSTERIOR OLFACTORY LOBULE visi.com but I don't see CARL SAGAN anywhere!!
Reply by ●January 16, 20092009-01-16
Erich, You could try www.SkandanTech.com They offer a tool called RecurSiv which detects direct and indirect recursion. The exact recursive paths are reported in a Text file or Excel Workbook. 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.
