On Thu, Jan 12, 2012 at 4:01 PM, Wayne Uroda <wayne.ur...@grabba.com> wrote:
> Hi Peter,
>
> Regarding your first comment, are you saying that while I can put a
> definite lower bound on stack usage (stack uses at least X bytes), I cannot
> put a definite upper bound on stack use (stack never uses more than Y
> bytes)?
>
> I agree that in a completely general case it is impossible to put a
> ceiling on stack size. In my last tool I made the following assumptions:
>
> 1. No recursion or cycles in the call graph
> 2. No nested interrupts
> 3. The program uses a simple foreground-background model and does not do
> any context switching, nor does it deliberately tamper with the stack
> during run time (i.e. the stack pointer is only modified by adding or
> subtracting fixed values).
>
> I think the first assumption is fine as I am yet to meet anybody who
> thinks recursion in an embedded environment is good practice.
>
True. And if you allow recursion then the problem becomes unbounded
(modulo stack size).
Assumption 2 is definitely a show stopper for some people.
Except, nested interrupts essentially is a h/w version of recursion and has
the same problem as #1. So you need to also make the assumption that it
isn't allowed for the purpose of stack analysis.
> I have never used nested interrupts myself so I have some gaps in my
> understanding of how they work in practice and will have to do some
> research here to see what can be done. Still the tool should be able to
> compute stack usage of the background code just fine.
>
That really is all you can do, both practically and theoretically.
>
> As for assumption 3, I believe if the user is writing a program with
> multiple threads perhaps they can invoke this tool several times, each time
> passing in the entry point to a particular thread, and thereby compute the
> stack usage of each thread (the tool also may be tailored to support one or
> more RTOS).
>
If you do context they are essentially different stacks.
> I am sure I am being too naive about it but for my own work I found even
> basic stack analysis to be quite helpful.
>
Not naive at all. It is the nature of the beast.
thanks for making the effort.
eric
> I am happy for you to point out anything obvious or not-so-obvious that I
> am overlooking :)
>
> - Wayne
>
> -----Original Message-----
> From: pabi...@gmail.com [mailto:pabi...@gmail.com] On Behalf Of Peter
> Bigot
> Sent: Thursday, 12 January 2012 11:19 PM
> To: Wayne Uroda
> Cc: mspgcc-users@lists.sourceforge.net
> Subject: Re: [Mspgcc-users] Static analysis stack tool
>
> On Thu, Jan 12, 2012 at 6:49 AM, Wayne Uroda <wayne.ur...@grabba.com>
> wrote:
> > Hello,
> >
> > I am interested in starting an open source tool for msp430 development,
> specifically to perform static, whole elf analysis to investigate stack
> usage. Such a tool can identify maximum stack depth of each function and
> also find the maximum stack usage of an entire executable.
> >
> > I have a tool which I wrote and use personally but it is limited and
> specifically coded for the custom link setup I use for my company's
> products, so I wish to start from scratch.
> >
> > Before I begin I just wanted to check that I wasn't reinventing the
> wheel. How I have done it in the past was by parsing the output of the
> disassembler, building a graph of function calls and then analysing each
> function for instructions which modify the stack. Would I be better off
> trying to insert this functionality into the compiler/linker/disassembler
> itself? I have a feeling this would be a lot more complicated.
> >
> > I plan on using C++. Any comments are welcome.
>
> Three comments:
>
> 1) (you probably know this, but just in case somebody doesn't...) Go
> in recognizing that the halting problem reduces to this: at best
> you'll be able to find situations where the stack exceeds a specific
> size, but will not be able to prove it doesn't do so.
>
> 2) For analysis of stack space consumed by a function I would look at
> http://gcc-melt.org/. There may already be a solution; if not, it
> would still provide a more effective analysis environment than
> reconstructing control-flow graphs from assembly.
>
> 3) For call graph in linked programs, look into using libbfd from
> binutils to extract data from elf files directly rather than
> processing disassembly output.
>
> Good luck, and if you need support for something in the compiler or
> binutils (other than "how about a stack space analyzer") let me know.
>
> Peter
>
> > Thanks,
> > - Wayne Uroda
> >
> >
> ------------------------------------------------------------------------------
> > RSA(R) Conference 2012
> > Mar 27 - Feb 2
> > Save $400 by Jan. 27
> > Register now!
> > http://p.sf.net/sfu/rsa-sfdev2dev2
> > _______________________________________________
> > Mspgcc-users mailing list
> > Mspgcc-users@lists.sourceforge.net
> > https://lists.sourceforge.net/lists/listinfo/mspgcc-users
>
>
> ------------------------------------------------------------------------------
> RSA(R) Conference 2012
> Mar 27 - Feb 2
> Save $400 by Jan. 27
> Register now!
> http://p.sf.net/sfu/rsa-sfdev2dev2
> _______________________________________________
> Mspgcc-users mailing list
> Mspgcc-users@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/mspgcc-users
>
--
Eric B. Decker
Senior (over 50 :-) Researcher
------------------------------------------------------------------------------
RSA(R) Conference 2012
Mar 27 - Feb 2
Save $400 by Jan. 27
Register now!
http://p.sf.net/sfu/rsa-sfdev2dev2
_______________________________________________
Mspgcc-users mailing list
Mspgcc-users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mspgcc-users
