-
Beginner question: Do any microcontrollers have stack/heap collision detection?
Posted by e100 on 13 Sep, 2021 07:14 -
As in an interrupt is triggered or a hardware pin is set to indicate an error without the programmer having to manually add checks everywhere?
-
The search term you are looking for is "Memory Protection Unit". This is available on many ARM Cortex M devices, usually the higher end parts but I think ST (and maybe others) make some Cortex M0 parts with this function. I'm not aware of any 8 bit devices with memory protection.
-
Some STM8, I guess the automotives, have stack guard cells.
-
As said above, a microcontroller with an MPU Is the best bet.
For micros without it, you have freeMemory() https://learn.adafruit.com/memories-of-an-arduino/measuring-free-memory which, despite it's name, essentially tells you how much space is left before the stack and the heap collide, as explained in the link above.
-
The search term you are looking for is "Memory Protection Unit". This is available on many ARM Cortex M devices, usually the higher end parts but I think ST (and maybe others) make some Cortex M0 parts with this function. I'm not aware of any 8 bit devices with memory protection.
You can't in general automatically tell whether a memory access is supposed to be to the stack or the heap, at either the machine code or the C level.
If stack accesses are only ever within N bytes of the stack pointer and the stack pointer is never adjusted by more than N bytes then you can put a protected area of N bytes between the stack and the heap.
But if a function uses an array as a local variable with either the size or an index supplied as an argument then you can't guaranteed those conditions and the stack can leap right over the protected area. That's true regardless of which order you put the stack and the heap in RAM, or even if they are in different blocks of RAM with large unmapped parts of the address space between them.
Still, a protected area will in practice catch most casual errors. It's just not guaranteed.
-
Some more modern Cortex-M cores have a (number of) stack limit register.
Specifically, Cortex-M23,33, and 55.
They are optional, though, and only present if the Security Attribution Unit is implemented (the ones I've checked all have it).
For each stack (MSP and PSP) there's a stack limit register and its secure version, they work as one would expect: if the stack pointer goes below the limit, an exception is raised.
As an example of "real world" use, Azure RTOS (ThreadX) uses them to set per-thread stack depth limits. -
It is a pretty rare feature indeed.
The software running on MCUs tends to be simple enough that you can take a good guess at the required stack and give it plenty of headroom above it since todays MCUs have quite a bit of RAM. Recursive functions is what tends to blow up a stack to massive sizes, so avoid those. During development you can also fill up the stack with a known pattern and use it as a watermark to occasionally check how high the stack got. If you only ever see it get half full then you can be confident it will never fill up.
One way to actually detect it is indeed the MPU (Memory Protection Unit) that comes included in most ARM MCUs. Mark off a small area of RAM on the end of the stack for no read/write permission, so if the stack grows into that you will trip a memory access fault.
I suppose you could say some of the old hardware stack based MCUs like the PIC16F havea stack collision detection feature since they use a dedicated memory for stack and will crash once that runs out. -
As brucehoult said, it's impossible to catch all "stack overflows" in general, as stack access, on most architectures, is just a normal memory operation.
Now, a commonly used approach is to set up "stack guards" - small buffers put between the stack and the heap, and then write protect those guards, either with an MPU if available, or watching for modifications in the guard buffer, initialized with sentinel values, on a regular basis, if not. This of course won't catch all issues, as Bruce explained. But it's better than nothing.
As newbrain mentioned, some MCUs have stack limit registers. Recent ARM Cortex-M cores, but also some automotive MCUs from NXP, IIRC. Of course, for this scheme to be effective, that implies that any running code comply with the official ABI, which in turn implies using the dedicated stack pointer register(s), and decrement them accordingly every time the stack "grows". This is usually the case when using conforming compilers, such as GCC or LLVM. Of course, it still won't catch some overflows - as Bruce again explained. But it will at least catch attempts to grow the stack beyond its limits, when the running code otherwise doesn't contain any buggy overflow through memory access.
-
As brucehoult said, it's impossible to catch all "stack overflows" in general, as stack access, on most architectures, is just a normal memory operation.
Another trick is to check the stack pointer inside a timer interrupt (or other interrupt occuring often). As this interrupt samples the stack pointer at a reasonably high and random interval in respect to the code running, it is very likely to catch a stack overflow.
Now, a commonly used approach is to set up "stack guards" - small buffers put between the stack and the heap, and then write protect those guards, either with an MPU if available, or watching for modifications in the guard buffer, initialized with sentinel values, on a regular basis, if not. This of course won't catch all issues, as Bruce explained. But it's better than nothing. -
The search term you are looking for is "Memory Protection Unit". This is available on many ARM Cortex M devices, usually the higher end parts but I think ST (and maybe others) make some Cortex M0 parts with this function. I'm not aware of any 8 bit devices with memory protection.
You can't in general automatically tell whether a memory access is supposed to be to the stack or the heap, at either the machine code or the C level.
If stack accesses are only ever within N bytes of the stack pointer and the stack pointer is never adjusted by more than N bytes then you can put a protected area of N bytes between the stack and the heap.
But if a function uses an array as a local variable with either the size or an index supplied as an argument then you can't guaranteed those conditions and the stack can leap right over the protected area. That's true regardless of which order you put the stack and the heap in RAM, or even if they are in different blocks of RAM with large unmapped parts of the address space between them.
Still, a protected area will in practice catch most casual errors. It's just not guaranteed.
You can't guarantee that an out-of-bound access to the stack won't hit the heap or vice versa, at least not in a simple fashion. However with a stack limit registers you can make sure that stack and heap allocations never overlap and thus in-bounds accesses never collide. You are correct that you can't do it with just a protected region between them.
-
Of course it is good practice to implement regular checks for memory loss, be it heap or stack. A beginner should learn how to implement "self aware" firmware. Let the firmware detect which MCU it runs on, how much RAM is present...
I'd recommend to attack a large stack problem at development time: Don't let it happen in the first place. Analyze and clean up call tree, checking for possible call loops. Implement bookkeeping for reentrance. One of the problems that get simpler when using a ready-made RTOS observing its rules.
Regards, Dieter -
If your cortex-M gets a Bus Fault when running below start of the RAM, you could put the stack to the bottom of the RAM. On stack overflow, the mcu would try to write to invalid area and trigger the fault handler.
-
Edit: Beaten to it by dgtl
Another option is to flip the standard stack and heap layout.
so you place the stack in a defined region below the heap, and then if the stack overflows, you will get a hardfault when the stack overflows.
More information can be found here: https://github.com/knurling-rs/flip-link
-
Recursive functions is what tends to blow up a stack to massive sizes, so avoid those.
I really don't like this blind anti-recursion advice.
Recursion is an extremely valuable tool in the programmer's toolbox. You should of course understand what your algorithm is doing. Out of control iteration and out of control recursion are equally bad.
Useful recursive algorithms usually have maximum stack depth proportional to the log of the data size -- if a thousand data items then about 10 deep, if a million data items then about 20 deep (maybe 25 or 30 allowing for imperfect balance). With typically three or four variables plus return address for each function call that's just a few hundred bytes of stack, even for a million items of data.
If you have room to store a million data items in RAM then you surely have a few hundred bytes for the stack.
-
A heap implementation like dlmalloc won't grow indefinitely. If you give it a slab of memory it'll stay within it. With it you can also have multiple heaps (called arenas), to reduce global heap lock contention between multiple threads.
-
Recursive functions is what tends to blow up a stack to massive sizes, so avoid those.
I really don't like this blind anti-recursion advice.
Recursion is an extremely valuable tool in the programmer's toolbox. You should of course understand what your algorithm is doing. Out of control iteration and out of control recursion are equally bad.
Agreed. And, any kind of overflow in memory can wreak havoc as well anyway.
Recursive functions "blow up the stack" if they aren't correctly written, or mastered. Obviously you shouldn't use a tool that you do not master, in particular for any critical development.
It's true that recursive functions are often frowned upon, or even forbidden, in some environments. I think they aren't allowed in MISRA-C, for instance. The point is that recursion is often more complex to analyze than iteration, so many people don't even want to bother.
Funnily though, some algorithms are much easier to write in a recursive way, and some developers who would shy away from recursion for the above reasons may try to work around this by using iteration and hand-written stacks allocated on the heap. This can of course fail just as badly and memory allocation on the heap is usually a lot more expensive as well...
Sure the big point with stacks is that on the most common architectures, return addresses and data are just shared on the same stack, and the idea of corrupting a return address is very uncomfortable. But, writing in memory anywhere where you're not supposed to could make a program fail hard, it doesn't have to be return addresses. Sure it allows a range of nasty bugs, but I'm not even completely convinced the risk of overwriting return addresses is, on average, worse than overwriting any part of memory. It usually just fails earlier and in a more visible way.
A final thought is that you absolutely don't need recursion to blow up stacks. A stack with too small a size, a certain call depth, and a fair amount of local variables (for instance strings or arrays) is all that's needed, and it can happen a lot more easily that some may think, in particular on small targets with limited memory.
-
Quote
Another option is to flip the standard stack and heap layout.
Even if you don't get a fault when you fall below the hardware RAM, it becomes really easy to detect the overflow condition of both stack (bottom of RAM) and heap (top of RAM.) And you'll probably crash a lost faster on stack overflows. For example, on an AVR, if you overflow a stack that starts at the beginning of RAM, you'd start trying to push stuff into the io registers, and the top addresses are likely to be "reserved" and probably won't read back whatever is written to them...
so you place the stack in a defined region below the heap, and then if the stack overflows, you will get a hardfault when the stack overflows.
-
Recursive functions is what tends to blow up a stack to massive sizes, so avoid those.
I really don't like this blind anti-recursion advice.
Recursion is an extremely valuable tool in the programmer's toolbox. You should of course understand what your algorithm is doing. Out of control iteration and out of control recursion are equally bad.
I am not saying that recursion should never be used. It does fit some algorithms really nicely and i used it quite a bit before. But most of its uses in my experience tended to be in bigger object oriented apps running on more powerful hardware and also having a OS where you can't overrun the stack since the OS will catch a trap and kill you if you try to do that.
For small microcontrolers where a few KB of RAM is all you got its usually not a good idea to use recursive functions especially when they might be accepting a complicated set of input data from the outside world. Usually there is a way to unroll it into a loop. There you work on an array that is a known exact length regardless of architecture or compiler while you can still store the array on the stack if you like.Edit: Beaten to it by dgtl
Another option is to flip the standard stack and heap layout.
so you place the stack in a defined region below the heap, and then if the stack overflows, you will get a hardfault when the stack overflows.
More information can be found here: https://github.com/knurling-rs/flip-link
The problem is that is that there is no room for heap to grow into so it all has to be static allocation or stack.
Then again i do think that is the way to do it for small MCUs since the stuff that runs on them tends to be reasonably simple and you probably want a tight grip on where the precious kilobytes of memory go.
-
You can't in general automatically tell whether a memory access is supposed to be to the stack or the heap, at either the machine code or the C level.
Well, you could have that 40 years ago with Intel 8086 segmentation. The 80286 added a protected mode which IIRC actually enforced that stack accesses do not overflow to code/heap, although they could still overflow to other stack variables.
Of course it was a PITA for C implementations so as soon as the 80386 offered 32 bit address space the lazy programmers bypassed the whole mechanism and emulated flat addressing. -
Things are relatively easy when there is plenty of RAM, as one can have a fixed limit for the stack an heap.
Things get more tricky when you are tight on RAM and a fixed limit no longer works. In the extreme the same memory could be used for stack and heap, just not at the same time. Heap is anyway a compiler thing - some compilers may not even use a heap. Most processors don't handle the heap in hardware and are not aware of it. It would need support by the compiler to change the limit for the stack, when the top of the heap moves. -
The way I have been doing this is to fill the RAM (in the .s startup code, usually) with a value other than 0x00 - say 0xaa or 0x55, or better still fill the stack with 0xaa and the rest (DATA & BSS, where the heap ends up) with 0x55. And the RTOS memory with something yet different.
Then as you run the target, you can easily see how much of each is getting used up, over time.
Using an ISR to monitor all this is very clever
But the real challenge, in most embedded systems, is: what the hell are you going to do if it runs out of RAM? If there is an LCD, you could put up a Windows 3.1 "general protection fault at [address]"
I don't like recursion. It is not the same thing as a loop getting stuck, because under an RTOS everything else will still be running (if possibly slower) whereas if recursion bombs the stack, the whole thing blows up. Even without an RTOS, interrupts can continue running.
I had memory protection (page fault trap) in processors like the Z280, in 1987, and there were chips like the Z8000 MMU, mid-1980s or so, but never enabled it because there was nothing useful one could do in an embedded system, other than a reboot, which is not acceptable to the customer, so it had to be assured by design and testing, with defensive coding practices (no heap at all is a good start, even if it means having a statically allocated "general purpose buffer" which gets re-used for different things). There is just no "provably safe" way to have a heap, unless every malloc is freed afterwards, and (in a multi threaded scenario) the functions are mutex protected, and then one could argue there is no point. I am gonna get jumped on now
-
You can't in general automatically tell whether a memory access is supposed to be to the stack or the heap, at either the machine code or the C level.
Well, you could have that 40 years ago with Intel 8086 segmentation. The 80286 added a protected mode which IIRC actually enforced that stack accesses do not overflow to code/heap, although they could still overflow to other stack variables.
Of course it was a PITA for C implementations so as soon as the 80386 offered 32 bit address space the lazy programmers bypassed the whole mechanism and emulated flat addressing.
Well, yes, it just doesn't do anything for a language like C or Pascal at all.
Suppose you write a function to sort an array. The function gets a pointer to the start of the array in C or a VAR parameter in Pascal (which is a pointer under the hood), and a length and then starts doing comparisons and swaps of array elements.
The function can be passed arrays that are global variables (data segment), or allocated on the heap with malloc() or new (also data segment), or that are local variables in the calling function or one of its parents in Pascal (Stack segment). It has to work with all of them. The only solution is to pass both the segment number and the offset and copy the segment number into ES to access the array.
And then when you index the array you have no idea whether you should be checking for overflowing the stack or the heap.
If the 8086 had a limit register for each segment register then you could use that to check that 0 <= offset < limit (and pass the limit as a third part of each pointer). But it doesn't.
-
The way I have been doing this is to fill the RAM (in the .s startup code, usually) with a value other than 0x00 - say 0xaa or 0x55, or better still fill the stack with 0xaa and the rest (DATA & BSS, where the heap ends up) with 0x55. And the RTOS memory with something yet different.
Still there can be a situation where a program gets in a weird state due to external influences. I typically have the memory exceptions enabled on ARM microcontrollers to cause a reboot. With the pins being pulled to safe values during a reset this puts the device into a safe state. Sure operation will be interrupted but there is almost no alternative scenario in case things go seriously wrong on the software side. I've seen situations where a microcontroller would start executing at a random point in the program...
Then as you run the target, you can easily see how much of each is getting used up, over time.
Using an ISR to monitor all this is very clever
But the real challenge, in most embedded systems, is: what the hell are you going to do if it runs out of RAM? If there is an LCD, you could put up a Windows 3.1 "general protection fault at [address]"
I don't like recursion. It is not the same thing as a loop getting stuck, because under an RTOS everything else will still be running (if possibly slower) whereas if recursion bombs the stack, the whole thing blows up. Even without an RTOS, interrupts can continue running.
I had memory protection (page fault trap) in processors like the Z280, in 1987, and there were chips like the Z8000 MMU, mid-1980s or so, but never enabled it because there was nothing useful one could do in an embedded system, other than a reboot, which is not acceptable to the customer, so it had to be assured by design and testing, with defensive coding practices
-
Well, yes, it just doesn't do anything for a language like C or Pascal at all.
It does add something right away: the stack and heap can be prevented from growing into each other.
It is my understanding that the 80286 protected mode could actually enforce a hard limit on each.Suppose you write a function to sort an array. The function gets a pointer to the start of the array in C or a VAR parameter in Pascal (which is a pointer under the hood), and a length and then starts doing comparisons and swaps of array elements.
You know, in protected mode. The segment is an index into an array which specifies how large the segment is, among other things. You load segment index into ES, the CPU loads the associated segment data into actual (hidden) MMU registers.
The function can be passed arrays that are global variables (data segment), or allocated on the heap with malloc() or new (also data segment), or that are local variables in the calling function or one of its parents in Pascal (Stack segment). It has to work with all of them. The only solution is to pass both the segment number and the offset and copy the segment number into ES to access the array.
And then when you index the array you have no idea whether you should be checking for overflowing the stack or the heap.
You could even create some 60000 arrays, each in its own segment, isolated from the others and from the stack and the heap. Not sure what the supported allocation granularity was. My guess: no worse that 16 bytes because reasons
-
Yeah when a memory or similar trap gets tripped there is usually no safe way to recover from that. Once memory is corrupted its anyones guess what the program might do if it was allowed to continue.
So in embedded its better to just reset the program so that it follows a known startup sequence again rather than hoping the memory corruption was nothing important. If the corruption happens on the stack then the return address gets mangled, so this is usually a death sentence to the program, breaking everything, making it do random stuff before usually eventually locking up and sitting there forever. This is also the same idea behind watchdog timers, once they detect that a piece of important code has stopped running it just reboots the whole chip in order to get it back to life. You still have control in the trap and a separate working stack so you can attempt to display a error message with some debug info for a second or two before rebooting to make the reboot seam less mysterious.
Sure it sucks to have your product reboot all of a sudden, but that is still better than locking up and requiring the user to come power cycle it manually, or worse doing something completely wrong before the lockup and causing damage.