Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.arch.embedded > #30756
| From | Niklas Holsti <niklas.holsti@tidorum.invalid> |
|---|---|
| Newsgroups | comp.arch.embedded |
| Subject | Re: Stack analysis tool that really work? |
| Date | 2021-08-04 22:14 +0300 |
| Organization | Tidorum Ltd |
| Message-ID | <in078sF1a5uU1@mid.individual.net> (permalink) |
| References | <sdukj9$8tu$1@dont-email.me> <sea47k$j3s$1@dont-email.me> <imsdtvF7jafU1@mid.individual.net> <seb289$ol0$1@dont-email.me> |
On 2021-08-03 12:28, Don Y wrote: > On 8/3/2021 1:43 AM, Niklas Holsti wrote: >> On 2021-08-03 3:56, Don Y wrote: >>> On 7/29/2021 9:22 AM, pozz wrote: >>>> arm gcc and Cortex-Mx MCUs embedded systems. >>>> >>>> Is there a compilation-time (static) tool for stack analysis that >>>> really works? >>> >>> What do you mean by "really works"? It's a (potentially) unbounded >>> problem >>> as the compiler can't know what the inputs will drive the code to do, in >>> practice. >> >> There are practical static-analysis methods to compute an upper bound >> on the stack usage that work well for many embedded programs. An upper >> bound is usually all one needs. The exact worst case is less interesting. > > That depends on the actual algorithm being implemented, the style of the > developer and, often, the inputs provided. > > For example, I often use recursive algorithms for pattern matching (because > they are easier to "get right"). Looking at the algorithm, you can't know > how deep the recursion will be -- without seeing the input it will be fed. Well, most embedded programmers avoid recursion. And if you implement recursion in a memory-constrained system, your design and code should set a hard limit on the recursion depth and reject input that would require deeper recursion. Some (admittedly complex) static analyses can discover such limits from the machine code, in the same way as they discover loop iteration limits for WCET analysis. (In fact, I believe that the AbsInt tools translate loops into recursions before the analysis.) >> Some problems arise for programs that branch to dynamically computed >> addresses, for example by calling functions via function pointers. >> Static analyses may not be able to find the set of possible target >> addresses. When that happens you have to guide the analysis by >> specifying where such control transfers can end up. For typical >> embedded code that is not hard to do, but a program that relies >> extensively on virtual function calls may be hard to analyze. > > The same is true of a program that is driven by external events. > The code doesn't (typically) "know" the constraints placed on those > events. (one can argue as to whether or not this is "good practice") > So, it can't "find the end". Again, if some sequences of external events might use an unbounded amount of stack, the design and code should set a hard limit. I have not encountered such programs. The typical design is to allow some fixed maximum nesting of event processing (eg. a finite set of interrupt priority levels) and otherwise enqueue the events for sequential processing, which does not require an unbounded stack. >>> There are general tools that you can probably instrument to coax a >>> number out of the source (if you don't have access to the source, you're >>> typically SoL) but they will be expensive in time or money. >> >> The exact stack usage of a subprogram can't be derived from source >> code without knowing what machine code the compiler and linker will >> produce. The static stack-analysis tools typically work on the final >> executable code (which also means that they can be independent of the >> programming language). > > If you don't have the sources, you can't *do* anything with the results > of the analysis -- other than define a minimum stack size (which may > be a surprise to you *and* your hardware!) If the program is single-threaded, the allocated stack size is usually set in the linker command file. Sure, you need the source for that file if you want to change the stack size. Of course you are screwed if your machine does not have enough memory for the size of stack you want. > If you don't have the sources, you likely haven't a clue as to how > the code behaves, under the complete set of I/O conditions. I've analyzed the stack usage (upper bounds) of many libraries without access to source code. Typically embedded libraries have call-graphs that can be extracted from the machine code without assumptions about the I/O or other run-time values. But that may no longer be the case for libraries written in C++ or other languages with run-time binding of calls. I agree that for complete programs one sometimes needs more insight, in particular if there are calls through function pointers or local variables with dynamic (data-dependent) size. >> But (as I said in an earlier post) the tools I am aware of, for the >> OP's target, are not free. > > You can possibly instrument some DSE-like tools. Sorry, what is a "DSE-like" tool? DSE = ? > How efficient are those you've used? Do they operate in "near compile > time"? For stack-usage analysis the tools are quite fast, typically, because embedded programs tend not to allocate dynamically-sized local variables. The main time is spent in reading the executable and decoding the instructions. For programs that allocate local variables of dynamic size the analysis becomes much more complex, can need lots of time and memory, and can often fail. > I.e., are they practical to use iteratively? On an entire > application? Yes, for many applications. And if you are implementing a safety-critical system, you design your application to be analysable.
Back to comp.arch.embedded | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Stack analysis tool that really work? pozz <pozzugno@gmail.com> - 2021-07-29 18:22 +0200
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-07-29 19:36 +0300
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-02 17:56 -0700
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-03 11:43 +0300
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-03 02:28 -0700
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-04 22:14 +0300
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-04 15:43 -0700
Re: Stack analysis tool that really work? pozz <pozzugno@gmail.com> - 2021-08-03 11:49 +0200
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-03 20:17 -0700
Re: Stack analysis tool that really work? pozz <pozzugno@gmail.com> - 2021-08-04 16:43 +0200
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-04 11:06 -0700
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-05 12:00 +0300
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-05 04:54 -0700
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-04 20:00 +0300
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-04 10:50 -0700
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-04 21:50 +0300
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-04 15:46 -0700
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-05 13:43 +0300
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-05 06:16 -0700
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-05 18:39 +0300
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-06 01:09 -0700
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-06 22:58 +0300
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-06 16:04 -0700
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-06 16:06 -0700
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-07 14:20 +0300
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-07 10:26 -0700
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-07 20:46 +0300
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-07 15:14 -0700
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-07 14:09 +0300
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-07 08:09 -0700
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-07 19:50 +0300
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-07 20:02 +0300
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-07 10:34 -0700
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-07 21:10 +0300
Re: Stack analysis tool that really work? George Neuner <gneuner2@comcast.net> - 2021-08-06 22:55 -0400
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-07 13:40 +0300
Re: Stack analysis tool that really work? George Neuner <gneuner2@comcast.net> - 2021-08-08 18:34 -0400
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-09 10:50 +0300
Re: Stack analysis tool that really work? Paul Rubin <no.email@nospam.invalid> - 2021-08-09 11:26 -0700
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-09 22:59 +0300
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-09 12:04 -0700
Re: Stack analysis tool that really work? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2021-08-05 13:18 +0300
Re: Stack analysis tool that really work? Don Y <blockedofcourse@foo.invalid> - 2021-08-05 04:59 -0700
csiph-web