Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch.embedded > #30757

Re: Stack analysis tool that really work?

Show all headers | View raw

On 8/4/2021 12:14 PM, Niklas Holsti wrote:
> 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.

Yes, but you don't need that limit to be enforced by a "depth counter".
Instead, it can be encoded in the data that *drives* the recursion.
A *human* understands that there is a limit (and exactly what that limit
is, for any dataset).  But, an algorithm may be taxed with trying to
determine this.

I shouldn't have to adopt a coding style just for the sake of a tool.

> 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.

Events need not be interrupts.  They may be user actions/keystrokes.
But, the "grammar" (odd choice of words) that defines the range of
permissible actions can limit how deeply the "generic" algorithm
recurses.  Again, something that a human can see and verify but that
could evade anything sort of a sophisticated analysis of code+data.

>>>> 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.

But you can't *change* your algorithm, having discovered that it uses
more stack than you had anticipated (or, that other consumers have
left available for its use).  Without the sources, your only option
is to change the hardware to make more stack available.

[And, even that may not be possible; e.g., multithreaded in a single
address space]

>> 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 = ?

Dynamic Symbolic Execution.

>> 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.

Ah.  The symbolic tools (alluded to above) are *really* resource intensive.
You can spend HOURS analyzing a piece of code -- with a fast workstation.
(my point being this is a tool that you'd use to VERIFY your assumptions;
relying on it to tell you what you don't yet know -- esp if your code is
evolving -- is way too costly!)

>> 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.

But, wouldn't you inherently *know* where your design is headed?
And, just need the tool to confirm that?  (and put real numbers on it)

Back to comp.arch.embedded | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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