Embedded Memory Allocation | Dr Dobb’s

Possibly the worst sin of calling malloc is that it might take a very long time to complete.

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 theonline listings. The basic idea is simple: a fairly large block of memory (either statically or via the system’s malloc (depending on theINIT_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 #defineoption (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:

?

1 2 3 4 5 6 7 8 9 10 11

[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:

?

1 2 3 4

[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 ofmalloc 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).

Source: Embedded Memory Allocation | Dr Dobb’s