Channels ▼

Al Williams

Dr. Dobb's Bloggers

Embedded Memory Allocation

October 13, 2014

You can find a lot of advice that you should avoid dynamic memory allocation on embedded systems. That's pretty sound guidance. However, sometimes, for any of a variety of reasons, you just have to do it. Most commonly, you need to use some third-party code that requires memory allocation (for example, code out of your standard C or C++ library).

Why is it bad? Depends on your point of view. Possibly the worst sin of calling malloc is that it might take a very long time to complete. It depends on the implementation, of course, but it might call into the operating system to get more memory or scan free space trying to coalesce free space. Neither of those things is likely to be fast. While it is unusual in the C universe, some memory allocators do garbage collection, and that can be another source of uncertainty.

Another issue is that the call might fail. A common remedy to that is to only call malloc during initialization. Get all the memory you need, and then start the main program loop. That's fine if you can manage it, but if you can't control the libraries you call, that may not be a good answer either.

Another argument — one that I don't subscribe to — is that pointers are inherently bad and cause mysterious errors. If you agree, you probably shouldn't be writing this kind of software to start with.

One way to beat the malloc problems is to adopt a hybrid approach. It is possible to allocate a fixed chunk of memory and then quickly parcel out pieces. That's the approach I've used in the code you can download in the online listings. The basic idea is simple: a fairly large block of memory (either statically or via the system's malloc (depending on the INIT_MALLOC #define). Because I'm aiming at small systems, the block can't be more than 64K, although that wouldn't be hard to change.

The program maintains three pools (LOW, MID, and HIGH) with configurable sizes. In reality, each chunk of memory is two bytes larger than its size to account for a "prefix." The prefix is a linked list "pointer" (actually, an array index) when the chunk is free that points to the next chunk. When the chunk is allocated, the prefix contains the actual size of the memory (so it can be put back into the correct free list).

This assumes you understand your program's allocation patterns well enough to pick the sizes for each memory pool. I included a #define option (UPSIZE) to allow larger blocks to stand in for smaller blocks if the smaller pool is exhausted. I also included another #define (FALLBACK) to use the system allocator if the private heap is exhausted. However, both of those defeat the purpose (but might be useful while you generate statistics).

The actual allocation is pretty simple:

[CODE]
if (p) 
	{
	  prefix=p;
	  p+=sizeof(short);
	  low_head=*((unsigned short *)(heap+prefix));  // remove from free list
// remember what list we belong on
	  *((unsigned short *)(heap+prefix))=LOW_SIZE;  
	  return heap+p;
	}
[/CODE]

As you can tell from the code, the free list tracks the start of each chunk, not the address returned to the caller. The free operation is also very simple:

[CODE]
   *pprefix=low_head;
   low_head=prefix;
[/CODE]

This just returns the block to the free list (I do check to make sure it looks like we allocated the block).

There's two things you should know before you try to use this code in practice: First, should you use it at all. You ought to understand how your native allocation system works and see if you can coax it to work (or, better, fix things so you don't need dynamic allocation). For example, the GNU library provides options to control allocation (see the documentation on mallopt). You also need to understand how to link your new versions of malloc in place of the system's version. This is especially tricky if you want to call the system version yourself.

GNU makes it easy with some hooks but your mileage may vary depending on your target system.

Once you know how to customize malloc, you open the door to other techniques. For example, many people use custom malloc libraries for debugging (dmalloc is one example). Don't forget you may also need to replace other memory allocation code like calloc and realloc (or, at least, forbid them).

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video