malloc like function using custom heap

Question

What would be the best approach in C if I wish to construct malloc like functionality with a custom pre-allocated heap?

My specific issue here is that I have a mmap-able (memory like) device which has been placed into my address space but I need to attain a more flexible way of using this memory to store objects which will be allocated and freed over time.

I know that malloc, free and the other similar functions are used to perform this kind of allocation on the heap but is there any way to use the logic provided by this kind of function for its dynamic behaviour while providing my own address space to operate as the heap in question?

Answer 1

malloc and family is a rather complex set of library functions. They do a lot of bookkeeping like which parts of the heap are in use and such.

A relatively easy way to use the standard memory allocator malloc is to remap the default heap with your custom mapping.

void * part_of_heap = memalign(sysconf(_SC_PAGESIZE), nbytes);
void * ret = mmap(part_of_heap, nbytes
             , PROT_READ | PROT_WRITE, MAP_FIXED, fd, 0);
if (ret == MAP_FAILED) {/* ... */}
free(part_of_heap);

Now anything that is placed in the area part_of_heap-part_of_heap+nbytes by malloc will go into your own mapped area. This is unsupported though and will not guarantee that any allocations will actually go there.

Otherwise you would need to implement your own memory allocator, which has to do bookkeeping. A linked list would do for starters. I know of no open implementation that would serve your needs.

Answer 2

Boost.Interprocess has stateful allocators suitable for shared memory segments: they may be re-usable for other mmapped address ranges too.

Otherwise, you may need to roll your own. In increasing order of complexity, you could consider:

1. a simple arena allocator: this is almost trivial, but has no way to free individual objects and reuse their memory
2. a simple object pool allocator: this works for fixed-size objects with almost no overhead (assuming the object is at least as large as a pointer, you can maintain a singly-linked list of freed objects)
3. a hybrid system with multiple object pools for different sizes (but each pool is individually a simple fixed-size instance)
4. some kind of slab/slub allocator (multiple fixed-size pools sharing a simple underlying allocator of large fixed-size slabs)
5. a SLOB allocator
6. a full malloc/free implementation (several are open source, so you can take an implementation and rip out anything you don't need).

Which of those are suitable will depend on some information you haven't given:

• object size
  • object pools work if you have only one, or only a few, sizes of object to allocate
  • arena allocators don't care about object size
  • neither support realloc
• object lifetime
  • object pools generally support arbitrary malloc/free sequences
  • arenas usually allow deallocation only all-at-once (so you just reset the arena to an empty state). You could modify this to allow LIFO deallocation.
• space/performance tradeoffs
  • the full heap implementation will probably be the slowest and most complex, but is also the most flexible
  • SLOB is easier and lighter-weight, but suffers more from fragmentation