[cap-talk] Memory allocation in embedded systems

[Jonathan S. Shapiro]

On Tue, 2007-01-02 at 00:58 +0000, David Hopwood wrote:
> If C had a general-purpose pool allocator in its standard library, I might
> have used that, but it doesn't.

David: are you aware of umem, which is a malloc replacement based on the
slab allocator? The slab allocator definitely qualifies as a pool-based
allocator.

If this is of interest, let me know offline and I will ask Jonathan
Adams (the author) if the umem allocator is available under sensible
terms. I'm pretty sure it has been released under Sun's community source
license, but it is conceivable that they released it under BSD.

I'ld also draw your attention to the kmalloc() that was widely used in
UNIX kernel prior to the publication of the slab allocator. In most
implementations, kmalloc() takes a pool name as an additional argument.
kmalloc() is certainly available under a BSD copyright.

> There is an obvious objection to this argument, which is that given a fixed
> total amount of memory, the *first* allocation failure of a system that takes
> memory from multiple separate, statically sized pools, will occur before that
> of a system that takes memory from a common pool. However, when the first
> allocation failure occurs is not the point. In a well-written embedded or
> safety-critical application (or in an OS kernel), you always have robust error
> handling of any possible resource exhaustion situation. Failure of an allocation
> attempt is not a problem as long as it occurs at a point where you can recover
> correctly.

This is equally true in a conventional heap-based implementation. The
real issue is slightly more subtle. [You do this for a living, so please
pardon my presumption.]

A pool-based allocator is never subject to fragmentation, which
completely eliminates an entire class of allocation failures, some of
which may leave an unrecoverable system. The problem with a general
allocator is that some fraction of allocations are durable, and if you
are sufficiently unlucky you can end up in a fragmentation corner where
the fragmentation is caused by the durable objects and the only way you
can recover is to compact the heap.

In most of the languages used for embedded programming, compacting the
heap is something you *really* don't want to do, because (a) the
languages involved don't generally provide a mechanism for accurate
pointer tracing, and (b) the compact pass may violate your scheduling
commitments, and if you are stuck in this particular way it cannot be
deferred to a schedulable time.

> It's better to fail the specific operation that caused a pool to 
> overflow, than to fail some possibly unrelated operation later.

Norm and I (and I think Charlie and Bill) are fond of a mantras for
KeyKOS/EROS:

  Fail early, but not often.

The longer you continue execution from the moment you make a mistake,
the less recoverable your situation gets. Very quickly you discover that
you cannot recover at all. On the other hand, if you fail unrecoverably
in a critical system due to anything other then a hardware error, you
need to hire better engineers, look hard at your methods, and make some
very expensive apologies that will be enforced by your customers' legal
representation (or in some cases their estate, depending on the
application).

I used to tell my students that they could commit their code into the
repository whenever they were willing to run the code on their own
pacemaker. Some time later I stopped when I learned just how bad
pacemaker software quality standards are.  Also, NSF turned down the
grant proposal that would have funded the pacemaker installations for
some reason. :-)

> As Jonathan points out, sometimes a memory pool is used as a cache from which
> entries can be evicted whenever needed. In that case, exhausting the pool does
> not affect correctness, only performance. (But such caches are rarer in embedded
> systems than they are in operating systems, partly because cacheing optimizations
> do not help with worst-case real-time performance.)

Agreed. When Coyotos (and I assume CapROS) are used in an embedded
system that doesn't have a persistent store, these structures aren't
just a cache and the limits on the prime space bank are set in such a
way as to guarantee that the total number of user-level objects fits in
the cache.

In principle you could tune the system to the wall in such a way that it
might invalidate and reload clean objects from ROM, but in practice this
only occurs at system startup.

>From an implementation perspective they are still a cache, but the
cleaner never runs.

>  - Memory is dirt-cheap. If you don't have enough memory to be able to write
>    the application in a straightforward way, just get some more. (I am in the
>    fortunate position of normally being able to dictate the hardware spec for
>    the systems I design, as well as writing the software.)

Indeed. We're presently building a **power strip** with *megabytes* of
RAM, because you simply can't buy memory chips much smaller than that.
It's quite silly. About the only applications I know about that still
have memory limits are things like smart dust, where the issue is
available battery power.


shap