Re: dynamic memory allocation

[Glen Cornell <cornell@gdls.com>]

Stephen Leake wrote:
...
> 
> 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".
> 

I'm not sure that dynamic memory allocation for an embedded system is
such 
a bad practice for the "qualified" embedded systems developer.  However,
most programmers new to embedded systems that I've seen have a
"workstation" mindset.  That is, memory is inexhaustible.  Like they
say, "it's not the gun that kills, it's the person pulling the
trigger".  This mindset is bad for systems that need to remain
operational indefinitely.  For systems such as the M1 tank, we
completely disallow the practice of dynamic memory allocation - sort of.

Allocators are a great compromise, allowing some flexibility to designs
while enforcing some discipline.  I took the C++ Standard Template
Library as an example for its implementation, although any algorithms
book probably would cover the topic.  The member functions allocate and
deallocate can be implementors of your chosen memory allocation scheme. 
This could be simple wrappers around new and unchecked_deallocation or
fixed block allocation at elaboration.  Whatever the implementation,
keep the interface the same, to easily change to a new implementation. 
The following is an example of an allocator's interface:

-- 
-- File Name: bound_allocator.1.ada
-- This is the embedded version of the unbound_allocator package.
-- this class allocates and initializes objects from a fixed size pool
-- created at elaboration.
-- 

generic

    type T_Object is limited private;
    type T_Handle is access T_Object;
    Maximum_Number_Of_Objects : in Positive := 20;
    -- keep it small to force the programmer to do a
    -- memory utilization analysis.

    -- T operations:
    with procedure Create (This : in out T_Handle) is <>;
    with procedure Destroy (This : in out T_Handle) is <>;
    with procedure Assign (To : in out T_Object; From : in T_Object) is
<>;

package Bound_Allocator is

    Invalid_Object_Execption : exception;
    -- the user tries to deallocate memory that was not allocated here

    Memory_Empty_Exception : exception;
    -- the user tries to deallocate from an empty pool (should never
occur)

    Memory_Full_Exception : exception;
    -- The user tries to allocate memory when the pool is full

    function Allocate
		-- allocate memory, initialize the object's data structure,
		-- and invoke the constructor.
		return T_Handle;

    procedure Deallocate
		 -- invoke the destructor and 
		 -- return the object's memory to the free pool
		 (Obj : in out T_Handle
		  -- the object to destroy
		  );

    function Verify
		-- was the object allocated from this pool?
		-- this method will NOT raise an exception
		(Obj : in T_Handle
		 -- The object
		 ) return Boolean;

end Bound_Allocator;

This is certainly not the panacea, but it does the job for simple types
(i.e. watch out for discriminant types without default discriminants,
task types, and other voodoo).

Try to convince your contemporaries to use the allocator, even if it
simply calls new and unchecked_conversion.  This way, at least you can
manage the transition to other allocation schemes or even have a means
to search for memory leaks.  (Once you've switched over to a safer
allocator and corrected the memory leak, you can say "I told you so!")

> On the other side, are there any discussions of how to test such a
> system, to show that it does not become fragmented? Or a book on
> designing dynamic memory allocation algorithms to avoid fragmentation?
> 

Wouldn't it be great to have Purify for Ada?

----------
Glen Cornell
cornell@gdls.com