When we link our programs together, the success of the operation reassures us that all our code and our static and global(?!) variables fit into the available memory. But what about the function parameters, the local variables and various other unknowns which go on the stack?
When someone mentions dynamic memory allocation, the worst-casers amongst us – which should be all of us – immediately start ranting against heap allocation and advocating either the somewhat safer use of fixed-size-block pools, or the ostensibly even safer but often design-compromising measure of banning of dynamic allocation altogether. But heaps and pools I’ve covered before on this blog. What we all tend to brush under the carpet is the admission that the implicit use of the stack in all our programming (in C and C++ at least) is also dynamic allocation and deserves much more careful consideration than we tend to give it.
The good news is that a LIFO stack, unlike a heap, is not subject to fragmentation. The bad news is that if it runs out of memory then, also unlike a heap, it typically fails to inform the program and, whether it does so or not, the failure is usually irrecoverable.
Worst case stack usage, on the face of it, seems easy to calculate but it actually turns out to be very difficult, as evidenced by the cost of the very few tools which claim to make a half-decent job of it. I say “half-decent” not because the tools are no good but because, by the candid admission of their vendors, they require quite a lot of help from their users, which, in turn, implies quite a lot of careful and time-consuming work.
I don’t want to go into a lot of detail here but this article by Nigel Jones on Embedded Gurus is a good starting point for those who do. The points I want to make are as follows:
- Many of us (and I include myself) do not apply our WCP thinking sufficiently to the matter of stack provision. It is not OK to use just “intelligent guesswork” in deciding something which is so vital to the proper functioning of our software.
- With more help from the compilers and linkers, which in general do not report to us as much as they could about stack usage, it would be much easier to work out stack sizes even for small projects where the expense of proprietary tools cannot easily be justified.
- My feeling is that, applying the KISS principle, there is much that could be done at the individual function level, as an adjunct to unit testing, where full conditional code coverage could and should be a realistic possibility. Once each function’s individual worst-case stack requirement has been reliably established it is then necessary only to traverse the call tree looking for the overall worst case. Although tedious, this might be easier and cheaper, for a small project, than configuring and deploying a specialised tool to analyse all the branches of the entire system. I am thinking hard about this approach at the moment.
- Given the residual uncertainty about the worst case provision, despite all reasonable efforts to establish it, I believe it is essential to design timely stack overflow detection into our systems, mustering any MPU or other hardware assistance available, even if the best response we can arrange is a safe shutdown.
Anyone using PendSV on Cortex (e.g. to implement an RTOS scheduler) should read this!
[Edited 29/09/11] It appears that there may or may not be a problem; the argument continues on the Embedded Gurus blog. If you’re tinkering with PendSV, it would be good to read the article (and the comments to it) anyway.
Timing issues are often important in systems containing software but, ultimately, all timing is determined by hardware. Let’s pursue this by splitting a hypothetical system into (1) the software we’re designing and (2) the platform it’s intended to run on. We also need to consider (3) the toolchain. To be a little more precise: Read more…
My last article, Whatever Happened to the Worst Case?, was a bit of a rant but it promised further articles on the subject. This is the first of these, which does no more than describe what I mean by the “Worst Case Principle”, or WCP. I am using WCP as both a label in the title and as a tag to identify each of the articles. The series is intended to provoke thought, not to be a complete treatise on designing robust software. That would fill a whole book – at least! Read more…
I’m dismayed about sloppy attitudes to design. I suspect they’re creeping across from consumer-focused software, where raw average speed is everything and an occasional glitch doesn’t matter. Well, I’m sorry, but as that kind of thinking creeps towards the vehicles I may travel in, or possibly the new nuclear power plant to be commissioned up the road from here, I feel the need to voice my concerns. Read more…
My last post, quite a while ago, expressed my preference for putting usage comments (as opposed to implementation comments), as far as possible, in header files on the grounds that the header file is the primary interface which the user has with the code. The code file (.c or .cpp), from a user’s perspective, contains a lot of irrelevant text and may not even be available for inspection in any case.
I did, however, write:
I’ve used several approaches but I’ve yet to settle on a “best” one. Indeed, the concept of “best” hinges to some extent on the approach, if any, taken with regard to external code documentation
Doxygen is perhaps the most popular open source tool for producing extensive, structured, external documentation by extracting comments (which have some special formatting) from the source files. As it can extract from both header and code files, the question is re-opened as to where it is best to put the usage comments. Read more…
An excellent and succinct article by Michael Barr entitled “What Belongs in a C .h Header File?” triggered the thoughts I am about to write down, for he forgot to mention comments as worthy items to be included. When conducting Advanced C courses, as I sometimes do, I have always emphasised the need for usage comments in header files. Header files provide the user’s interface to the implementation in the corresponding .c files, but the latter are often uninteresting to the user and may not even be available. Proprietary libraries, for example, are typically shipped in object form with their header files. It follows, therefore, that any comments which might be valuable to the user should be in the header file. Read more…
Most embedded software practitioners – sadly, not all – know that some form of what is normally called “Mutual Exclusion” is necessary when a read-write resource is shared among two or more concurrent activities, particularly (but not necessarily only) when test-and-set operations are involved. The expression “Mutual Exclusion” is so entrenched as a generic concept that I feel obliged to use it as such, but sometimes it is anything but mutual. Read more…
Since Easter, when I promised a new release of this software, I’ve been exceptionally busy in a money-earning sort of way. I’ve noticed that others are blogging less now that their business has (presumably) picked up, so I’m not alone in disappointing my readers, but that is no excuse and so I have just uploaded the software I promised. Read more…
I like C++, but sometimes it appears to work with the aid of magic which I don’t fully understand. Last time (was it really 3 weeks ago?) I mentioned a problem I had with compiling the software I have been offering to subscribers to this blog with the GNU compiler. Or, to put it more honestly, I created a problem which g++ legitimately complained about, but which the other two compilers I tried (VC++ and IAR) allowed me to get away with. I am simplifying somewhat but basically I coded something like this: Read more…