# Use of malloc in PIC

How can I use malloc() and free() functions in a PIC? I've checked the stdlib.h header and there's no mention of them. I'm using MCC18.

Has anybody had to use them?

I need them because I am porting a library from Windows XP to the PIC. The porting guide says to

adapt the Operating System's specific functions to my PIC ones

But I don't know how to "translate" the malloc() and free() functions.

-
Try to use static allocation if possible. – Nick T Dec 14 '10 at 14:42
Why? The problem really is that I'm writing the bottom layer (the platform specific one) of a pretty huge library and a lot of functions I have no idea what they are for are using this.. and I have no idea how to change from dynamic to static.. – stef Dec 14 '10 at 14:48
It sounds like a PIC microcontroller with < 4KB RAM may be wrong for your application. On a PC measure the memory usage of your PC library before beginning a port. You may be better off with something beefier like an ARM Cortex-M3. Rule of thumb: if the codebase you're porting is too big to understand then it won't fit in a PIC. – Toby Jaffey Dec 14 '10 at 23:16
Windows drivers (and applications in general) essentially are written with an 'unlimited RAM' paradigm, since if physical RAM is exhausted, virtual memory can be swapped in. Depending on what the library is doing, it may very well consume more than the 4kB available in your PIC18F87J11. I suspect that you won't be able to gauge how much memory the driver is going to use. – Madmanguruman Dec 17 '10 at 14:14
Another potential issue: a Win32 int is 32 bits, whereas with the MCC18 compiler, it's only 16 bits. You could get weird overflow problems if you're not careful. – Madmanguruman Dec 17 '10 at 14:17
show 1 more comment

In many applications, one will need to allocate memory, but won't need to free anything while keeping something that was allocated after it. On such a system, all one need do is use the linker to define an array using all available RAM, set a pointer to the start of that array, and then use a nice easy malloc function:

char *next_alloc;
void *malloc(int size)
{
char  *this_alloc;
this_alloc = next_alloc;
if ((END_OF_ALLOC_SPACE - this_alloc) < size)
return -1;
next_alloc += size;
return this_alloc;
}
void free(void *ptr)
{
if (ptr)
next_alloc = (char*)ptr;
}


Nice and easy, and just two bytes total overhead for any number of allocations. Calling free() on a block will deallocate that block and everything after it.

Slightly more complicated allocation patterns can be handled by using two pointers--one which allocates stuff from the bottom of memory moving up, and one of which goes from the top of memory downward. It's also possible to use a compactifying garbage collector if the data in the heap is homogenous and one knows where all the outside references to it are.

-

This is hardly an answer to your question, but dynamic memory allocation is generally frowned upon small RAM environments and in the absence of an operating system (e.g. in the microcontroller world)... the heap space you have available in an embedded environment is typically measured in hundreds of bytes...

Implementing malloc and free is essentially maintenance of a linked list of "free segment" structures, and as you can imagine, the metadata associated with free segments is not insubstantial when compared to the amount of memory typically available... that is the "overhead" of managing a dynamic memory pool consumes a significant amount of the available resources.

-
 There are implementations where the metadata overhead is very small. For an allocated block, you only need its size. For unused blocks, the linked list pointer(s) can usually fit for free, even with quite reasonable minimal block sizes. – Kuba Ober Feb 10 at 22:53 The problem with small, long running systems that use microcontrollers is not usually about metadata, but about memory fragmentation. What's worse, small changes to your code can introduce memory fragmentation where there was previously none, so that you may make an innocent-looking change that suddenly makes your program stop working "way too soon". – Kuba Ober Feb 10 at 22:54

I don't know if the C18 standard library supports malloc and free, but Microchip App Note AN914 shows how you can implement your own.

In any case, Thomas and other posters have suggested, using dynamic memory on PICs with their very small RAM space is fraught with peril. You can rapidly run out of contiguous space due to the lack of more advanced virtual memory managers that full blown OS's give you, leading to failed allocations and crashes. Worse, it may not be deterministic, and will likely be a pain to debug.

If what you are doing is truly dynamically determined at run-time (rare for most embedded things), and you only need to allocate space on a couple very special occasions, I could see malloc and free being acceptable.

-
 Running out of contiguous space, a.k.a. heap fragmentation, is a problem that's wholly independent of how big your address space is and whether you have virtual memory. You may want to trade off some wasted RAM for lower heap fragmentation, but eventually, on a long running system, you have no guarantees about not running out of heap space. The only difference between small and big systems here is the one of how long does it take for the disk to start thrashing (on systems with disk-paged VM), or the allocator to return NULL (on embedded stuff). – Kuba Ober Feb 10 at 22:59

malloc() in microcontrollers is generally considered a "bad thing". But, if you absolutely need it then you'll want to find a third party version.

If you're lucky, the code you're porting may not rely on reusing blocks of memory. If this is the case, you can write a simple allocator which returns a pointer into a RAM buffer, then advances the pointer by the requested block size.

I've successfully used this approach before in porting PC libraries to microcontrollers.

Below, you'd setup the allocator with my_malloc_init() and allocate memory with my_malloc(). my_free() is there to satisfy the dependency but won't actually do anything. Eventually you'll run out of space, of course.

To make this work, you'll need to measure the worst-case memory requirement of your code (do this on a PC if possible) then set up HEAP_SIZE accordingly. Before entering the part of your library requiring dynamic memory, call my_malloc_init(). Before re-use, make sure nothing still points at heap.

uint8_t heap[HEAP_SIZE];
uint8_t *heap_ptr;

void my_malloc_init(void)
{
heap_ptr = heap;
}

void *my_malloc(size_t len)
{
uint8_t *p = heap_ptr;
heap_ptr += len;
if (heap_ptr >= heap + HEAP_SIZE)
return NULL;
else
return p;
}

void my_free(void)
{
// do nothing
}


(note: in the real world, you might need to consider pointer alignment, ie. rounding up heap_ptr by 2 or 4 bytes)

Another option is to use a simpler allocation structure than malloc() usually provides, like a FreeList, though this may not allow you to allocate variable sized blocks.

-
I wonder when malloc IS considered a good thing in embedded. – Kellenjb Dec 15 '10 at 0:19
I still agree you do not want dynamic allocation in programs, as others have said, but this is a great way to go about it. Third party malloc designed for embedded is by far the best choice. Avoiding segmentation is a must. @jobyTaffey Well written. – Kortuk Dec 15 '10 at 0:21
@Kellenjb well, that's a whole new question :-) – Toby Jaffey Dec 15 '10 at 0:23
I would suggest that my_free should set heap_ptr to the passed-in value, effectively freeing the indicated item and everything allocated after it. Obviously one must allocate things in a sequence that permits such usage, but such patterns aren't uncommon. Another useful variation is to have two pairs of alloc/free functions, one of which allocates top-down and the other of which allocates bottom-up. – supercat Mar 24 '11 at 15:53

Well, how big is your PIC in terms of memory?

malloc is a very inefficient way of allocating memory. The problem with it is that memory can become fragmented with frequent frees and mallocs and with only a few kilobytes of memory, allocation failures are all too common. It's quite likely that if you're using a smaller chip or an earlier PIC18 there is no support for malloc, as Microchip either viewed it as very difficult to implement (or maybe even impossible in some cases) or not used enough for it to be worth it. Not to mention it, but it's also quite slow, you're looking at 1 cycle to use a static buffer already available and 100s to 1,000's of cycles to do a malloc.

If you want to allocate statically, create things like a buffer for your sprintf functions (if any, around 128 bytes), a buffer for your SD card (if any), and so on, until you remove the need for malloc. Ideally, you only use it where you absolutely need it and can't get away with static allocation, but these situations are usually rare and maybe a sign that you should be looking at bigger/more powerful microcontrollers.

And if you're developing/porting an "operating system" on the PIC18 and if it supports microcontrollers it probably has support for static allocation. For example, SQLite3 supports static allocation - you allocate it a large buffer array and it uses that where possible, even though it isn't for microcontrollers. If it doesn't, then are you sure it's designed for a small PIC18?

-
 I see what you mean.. I'm using the PIC18F87J11, which has 128K of ram, can it be enough? – stef Dec 14 '10 at 15:02 Stefano, that chip has 3,904 bytes of RAM. It has 128K of program flash memory. – W5VO♦ Dec 14 '10 at 15:13 @Stefao Salati - 3.8KB is tiny. – Thomas O Dec 14 '10 at 15:29 Right sorry.. do you think it can be enough anyway? – stef Dec 14 '10 at 15:31 @Stefano Salati, no need to apologise. I think you'd be pushing it really. It might work, but it would take a chunk out of performance and your free memory. – Thomas O Dec 14 '10 at 15:33
show 1 more comment

If you are considering malloc() and free() for your embedded software I suggest you take a look at uC/OS-II and OSMemGet() and OSMemPut(). While malloc() let you allocate an arbitrary block of memory, OSMem*() give you a fixed-sized block from a pre-allocated pool. I find this approach a good balance between the flexibility of malloc() and the robustness of static allocation.

-

AFAIK, to do this correctly, you really need to be looking at a device with some kind of memory-management unit (MMU). While dynamic allocation mechanisms for the PIC18 series do exist, they're not really going to be that solid - and speaking as someone who's worked on firmware that pushes the limits of the PIC18 series, I can say that you're not going to get a sizable application in there if you spend all the overhead on a memory manager.

Better solution: try to understand what it's doing, and why it needs dynamic allocation. See if you can't re-factor it to work with static allocation. (It may be the case that this is simply not possible - if the library/application is designed to do something that scales freely, or doesn't have bounds of the amount of input it can accept.) But sometimes, if you really think about what you're trying to do, you might find it is possible (and possibly even quite easy) to use static allocation instead.

-
You're incorrect. An MMU allows you to interface with external memory (likely more than the 4kB on the PIC). There is very little difference in dynamic and static allocation with and without an MMU. Once you start getting into virtual memory, there's a difference, but that's only tangentially related to malloc. – Kevin Vermeer Dec 20 '10 at 1:37
Early Macintosh programmers used malloc() and free() (or their Pascal equivalents) quite often, despite the fact that early Macintosh computers had no MMU. The idea that "correctly" using malloc() requires a MMU seems incorrect to me. – davidcary Mar 11 '11 at 16:27