Stack Overflow Detection

s

Obviously if the stack overflows then that's a sign of flaw in the programming, so really you're trying to implement a system that accommodates buggy programming and just peforms a "salvage operation" by killing the program before it can do any damage... do I understand correctly?

To my knowledge there are two symptoms of stack overflow:

1) The stack pointer being greater than it should be 2) Data after the stack pointer getting changed

As you've said, you can't really rely on the first one because it could go forward and then move back to a safe area. As for the second, well it has a very good chance of working, but there's still a 1 in

256 chance that the corrupt byte will be exactly equal to the "test value" :-P

Assuming that I'm right in saying that you'll just kill the program if the stack overflows, what will be the benefit of this? Will it stop the Green Laser of Death from being turned on, or will it stop permanent storage from being corrupted or something like that?

Look into the map file. A sensible linker will provide the call tree with the corresponding stack usage. Depending on the system, you may or may not need to account for the stack usage in the interrupts. Avoid the unpredictable stack usage such as recursions and the dynamic allocations from stack.

This is one of the common ways. The main problem with it is that you never know for sure what is the maximum stack usage.

Check the SP in the interrupt which happens at random time instants. This also doesn't guarantee the detection of the max. usage.

Use the CPU with MMU. Limit the stack segment size.

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

The stack isn't currently overflowing, in so far as the software isn't going nuts for no obvious reason, I guess I'm looking at having something that can detect a situation where the heap data might "collide" with the stack data. I suppose one problem is I've not previously defined what I mean by "overflowing", I think the previous line corrects this. As for the action to take if a problem is detected, I suppose a reset would be a good start. But then I suppose if there is a situation where such a problem occurs, it's probably going to reoccur. I don't expect this to ever be a problem, but on a previous project there was a requirement to have this safety feature. It's not required on this project, but I was thinking about adding it anyway.

Thanks, Richard.

I'll take a look at the map file and see if there is anything useful in there, thanks. As for maximum stack usage, it's a fair point, I guess it would have to be determined by trial and error, which is clearly a little clumsy. I had thought of the interrupt idea, as you say though, it still doesn't guarantee you'll actually catch it. Stack segment limits, I'll look into that!

Thanks, Richard.

Are you sure about that? Would it not just be a case of determining how much stack space each of the function's use, and then looking at the logic of the program to see what could possibly be the deepest level?

Even if there were recursive functions involved, they could still be given a finite limit:

double RaiseToIntPower(double val,unsigned exp) { if (0 =3D=3D exp) return 1;

if (1 =3D=3D exp) return val;

return val * RaiseToIntPower(val,--exp); }

For example the logic of the program my prevent "exp" from being more than 7, or then again you could hardcode your own "if (exp > 7)" within the function.

(Obviously it's a stupid idea to implement this function as a recursive funciton, but it was an easy example to throw together for the purposes of explanation.)

It is commonly used. You can fill the stack area with a known value and check the highest level actually reached. You can then double the amount of space for good measure. This is not a guarantee, of course.

Perform blackbox and whitebox testing, make sure all paths are taken, you will have a better idea, but still no guarantee.

Vendor-supplied library functions could be an issue, and library functions that call other library functions, etc. How many auto variables do the deeper internal functions use? Are the call stack and the "software" stack combined? Sometimes yes, sometimes not.

One hopes that the vendor recommends a minimum stack depth, but ...

--
Rich Webb     Norfolk, VA

There are static-analysis tools that can do that. Some compilers/linkers do it and there are stand-alone tools like GnatStack, StackAnalyzer from AbsInt, and Bound-T from my company. Of course, these tools are not available for all processors, and may have difficulty with recursion and stack frames of dynamic (run-time-computed) size.

--
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Or in some systems, HW failures, EMI or radiation events.

That's one option. Sometimes runtime stacks are set much larger than expected need and instrumented like this to verify/determine (to some statistical significance) the actual stack usage.

Quite possibly all of the above. Or maybe it just irritates the user. Sometimes resetting is not really an option.

Robert

** Posted from **

s

What for? What processor? It's not really possible to give any sensible answer without this information.

s

I think the best way to check how deep the stack is used is doing the following:

1) Initialize the all stack array with the 0xFF or any other known pattern. It should be done as first step after Power On ( maybe in main() or in assembler). 2) Let the system run for some time with the most features used. 3) Try to investigate the stack RAM area in various possible ways: a) adding some command to print the all stack to the screen or to other existing output. b) running the special function which checks all area of stack and gives the first address different from 0xFF c) see the RAM content inside the debugger - if avalaible.

I hope it helps.

Yossi

Thanks for the reply. I think that's the strategy I'll use, I guess firstly I need to determine how much memory the stack typically uses, this strategy would certainly give me a very good idea. It won't 100% guarantee I've seen the worst case scenario, but if I look at what happens and then allocate (say) twice that amount, or +50%, I'll probably be ok. I could then employ some kind of check to make sure that if the stack DOES go beyond this limit then the system does something drastic like reset, happy in the knowledge that it's highly unlikely due to my previous testing (i.e. your suggested strategy)!

Cheers, Richard.

d

ve

g

Hi, While doing stack memory analysis dont forget to be aware of the involvement of nested interrupts.In architectures where seperate interrupt stack is not present,ISRs may occupy your tasks stack.If there is an occurance of nested interrupts,your stack might grow due to this. Just my 2 cents of thought......

Regards, s.subbarayan

Thanks, All assistance welcome! Cheers, Richard.

Op Fri, 30 May 2008 17:11:44 +0200 schreef Tomás Ó hÉilidhe :

Yes.

No. "By trial and error" would be a more accurate term. It might be 'wrong' in the purist's eye, but it can still be cost-effective.

Or smaller, depending on the direction of stack growth. So: the stack pointer being outside of stack bounds.

Or before, depending on the direction of stack growth. So: data just outside of stack bounds getting changed.

Often, a stack element is more than one byte. Besides, "exactly" is not a sensible requirement.

Obviously, for safety critical systems it has to be shown/proven that all paths execute OK. Another safety feature could be to have a stack checker kicking in once in a while, which goes into an error handler if it detects an overflow, gracefully shutting down any dangerous equipment (which could be a fresh process that starts after the scheduler has suspended all other processes).

--
Gemaakt met Opera's revolutionaire e-mailprogramma:  
http://www.opera.com/mail/

Most sensible answer yet.

You CAN know the max stack usage if you can trace out every possible call and interrupt (the call tree, as you mentioned). If it's THAT important (in a "high reliability" application such as vehicle control), the program can/should be planned and written from the start with this in mind (doing as you said above, avoiding unpredictable stack usage).

But this method, while rigorous, may not be easily applicable to "a system I'm working on."

Make a repetitive interrupt that does nothing but check the stack. If it happens often enough, it will have the largest size the stack reaches. It would have to run quite often and may take a substantial percentage of CPU cycles to catch the stack value as used in short subroutines and interrupts, but it would reasonably find the max the stack has reached (not neccesarily the theoretical max the stack could get).

There's an old-fashioned device called a logic analyzer that when properly set up can do wonders for tracing things such as stack usage in real time without interfering with normal operation, but they don't work with embedded parts that don't have address and data lines brought out to pins. Some manufacturers have made versions of their microcontrollers with all the pertinent lines bonded out, but I don't know if anyone still does that.