Re: dynamic memory allocation

[wheeler@ida.org (David Wheeler)]

Stephen Leake (Stephen.Leake@gsfc.nasa.gov) wrote:
: I'm trying to convince my project that dynamic memory allocation is a
: bad idea in an embedded software system (a satellite control system, in
: this case). 

: They are proposing a message passing scheme where sending tasks allocate
: buffers for each message from a heap, and receiving tasks deallocate. I
: have suggested that the heap could become fragmented (the buffers are
: NOT all the same size). They say "we'll just test it thoroughly".

"Testing it thoroughly" cannot provide
strong evidence that something can't happen -- at best it can show that
it will only happen occasionally when the real inputs equal the test inputs.
There are some good referenceable papers that show the futility of
depending on testing alone to give any useful assurance in systems that
must be highly reliable.

Let's be practical.  If you knowingly insert code that doesn't always
work, and then testing doesn't encounter the problem, what exactly have
you shown?  What you've shown is that your testing wasn't good enough
to find that bug.  That's possibly interesting information, especially
if you want to know how good your testing is, but that
does NOT provide evidence that the system won't encounter a serious problem
in flight.  It doesn't even provide strong evidence that such an encounter
is unlikely unless you can prove that the tests are exactly what the
system will encounter -- this is the weakness of reliability measures.
Digital systems have a different failure mode than analog systems -- in most
analog systems similar inputs tend to produce similar outputs, and digital
systems need not do so.

: Can anyone provide a reference to a book or study article that says this
: is bad? To me it seems obvious, and the general tone in this newsgroup
: is that it's obvious. I have a couple books on realtime embedded design,
: and they don't even bother to mention dynamic allocation -
: unfortunately, that makes it hard to say "see, this book says it's bad".

Regarding memory allocation issues, this is the sort of thing that's
so obvious to practitioners that it's rarely written down.
I believe that the U.K.'s 00-55 military standard required
that allocation only occur during system initialization; note that
00-55 also advocated the use of formal methods.
Perhaps someone in the U.K. can enlighten you on the current status of 00-55.

See the Ada Quality & Style Guide 5.4.5, which discusses this.
It states that avoiding the use of dynamic allocation is unnecessary
since Ada has a "Storage_Error" exception.  Realize that this statement
in the AQ&S is only half true; if there's nothing you can DO about
a Storage_Error and must still perform the work correctly,
then you'll need a design that makes it impossible to have a Storage_Error.

You MAY be able to make the allocation reliable, depending on other factors.
For example, if there are only 3 message sizes, you may be able to
preallocate those sizes.  You might even be able to create a simple proof that
as long as a certain order is maintained, the approach is fine.
Naturally, this is all application-dependent.

I'm assuming that this really has to work with very high reliability.
If occasional failure IS acceptable (true for many ground-based
systems), then it may be cheaper to permit an occasional failure and
then reprogram it when the failure rate becomes unacceptable.


--- David A. Wheeler
    dwheeler@ida.org