CODEWITHSUNDEEP
cmemory-managementstaticmalloc
qxn
qxn

Reputation: 17594

Allocate static memory (as malloc replacement)

I saw this question, but it simply illustrates what I want to do rather than explaining how to do it.

I have a C library that will be run on systems that support dynamic memory allocation as well as systems that don't. I want to make the transition between systems simple by writing my own malloc function that allocates memory from a static array when the heap is not available.

I'm not looking for a completely fleshed out solution to my problem, but a blog post with an example would be helpful. Determining when and when not to use malloc is easy. But it's taking me some time to figure out how to allocate memory from a static array.

static char my_memory[10000] = { 0 };

static void *my_malloc(size_t size) {
    // Here, I want to allocate 'size' in 'my_memory'.
    return NULL;
}

static void *my_free(void* memory) {
    // Here, I want to free 'memory' from 'my_memory'.
}

EDIT:
My needs are pretty simple, here, and very little memory will be allocated this way (and rarely freed). Steve Jessop's simple solution is a good fit.

Upvotes: 2

Views: 4691

Answers (3)

Steve Jessop
Steve Jessop

Reputation: 279455

About the simplest allocator it's possible to write:

  • init: current_position = my_memory + sizeof(my_memory). Depending on alignment requirements of your implementation, you might have to make sure current_position is correctly aligned.
  • allocate: return ((current_position - my_memory) <= size) ? 0 : (current_position -= size);. For alignment, you might have to round size up to a multiple of some number first.
  • free: do nothing.

That's it. Obviously if you call free a lot, this strategy runs out of memory way too soon. So you can introduce a complication:

  • allocate: increase size by enough space to write the size of the allocation into the start of every "block" you carve off the array. Return a pointer to the end of the size record (i.e. the start of the usable memory). Also, make sure that every allocation is big enough to contain a header struct that you define, even if the request is for less than that.

You've introduced a per-allocation overhead, but this allows you to:

  • free: use the header struct to add the freed block to some kind of data structure (continue to remember the size).

  • allocate: if there's an allocation in the data structure that can satisfy the request then return it, otherwise carve another slice off the main array and return that.

Now you have a working memory allocator. It doesn't work particularly well, you're about 60 years behind the state of the art, so you're probably going to need to introduce more complications. But the entire history of memory allocation algorithms is beyond the scope of a single answer. You can progress from here until either your allocator is good enough for your purposes, or else you give up and decide to use an existing library.

Upvotes: 2

hanumantmk
hanumantmk

Reputation: 661

An oldie but a goodie (for a blog post describing the problem): http://g.oswego.edu/dl/html/malloc.html

Or if you're looking for something packaged: http://hempeldesigngroup.com/embedded/stories/memorymanager/

Upvotes: 1

Joe
Joe

Reputation: 7818

You can hold the address (in your case the offset in the array) to the next free block at the beginning of each allocation, i.e. you use some of your array to be the list of free blocks. This takes account of how you allocate and find memory blocks, free is trickier in that as you give back the memory you need to do more than just adjust your free offsets in the array, you also need to coalesce mutliple free blocks together, otherwise you end up with memory fragmentation and you can't then allocate chunks in a size you need.

I think the key concept is that the allocated blocks also always contain the offset to the next free block, that's how you use your own array only to track what's allocated in it.

Upvotes: 1

Related Questions