Examples or documentation for custom storage allocator in c?

Question

I allocate a big region of memory lets say x of 1000 bytes.

// I am using c language and all of this is just pseudo code(function prototypes mostly) so far.
pointer = malloc( size(1000 units) ); // this pointer points to region of memory we created.

now we select this region by a pointer and allocate memory inside it to smaller blocks like

void *allocate_from_region( size_of_block1(300) );  //1000-300=700 (left free)
void *allocate_from_region( size_of_block2(100) );  //700-100 =600
void *allocate_from_region( size_of_block3(300) );  //600-300 =300 
void *allocate_from_region( size_of_block4(100) );  //300-100 =200
void *allocate_from_region( size_of_block5(150) );  //200-150 =50
// here we almost finished space we have in region (only 50 is left free in region)


boolean free_from_region(pointer_to_block2);        //free 100 more 
//total free = 100+50 but are not contiguous in memory

void *allocate_from_region( size_of_block6(150) );  // this one will fail and gives null as it cant find 150 units memory(contiguous) in region.

boolean free_from_region(pointer_to_block3); // this free 300 more so total free = 100+300+50 but contiguous free is 100+300 (from block 2 and 3)

void *allocate_from_region( size_of_block6(150); // this time it is successful 

Are there any examples about how to manage memory like this?

So far I have only did examples where I can allocate blocks next to each other in a region of memory and and end it once I ran out of memory inside the region. But how to search for blocks which are free inside the region and then check if enough contiguous memory is available. I am sure there should be some documentation or examples in c which shows how to do it.

Answer 1

Sure. What you are proposing is more-or-less exactly what some malloc implementations do. They maintain a "free list". Initially the single large block is on this list. When you make a request, the algorithm to allocate n bytes is:

search the free list to find a block at B of size m >= n
Remove B from the free list.
Return the block from B+n through B+m-1 (size m-n) to the free list (unless m-n==0) 
Return a pointer to B

To free a block at B of size n, we must put it back on the free list. However this isn't the end. We must also "coalesce" it with adjacent free blocks, if any, either above or below or both. This is the algorithm.

Let p = B; m = n;  // pointer to base and size of block to be freed
If there is a block of size x on the free list and at the address B + n, 
  remove it, set m=m+x.  // coalescing block above
If there is a block of size y on the free list and at address B - y, 
  remove it and set p=B-y; m=m+y;  // coalescing block below
Return block at p of size m to the free list.

The remaining question is how to set up the free list to make it quick to find blocks of the right size during allocation and to find adjacent blocks for coalescing during free operations. The simplest way is a singly linked list. But there are many possible alternatives that can yield better speed, usually at some cost of additional space for data structures.

Additionally there is the choice of which block to allocate when more than one is big enough. The usual choices are "first fit" and "best fit". For first fit, just take the first one discovered. Often the best technique is (rather than starting at the lowest addresses every time) to remember the free block after the one just allocated and use this as a starting point for the next search. This is called "rotating first fit."

For best, fit, traverse as many block as necessary to find the one that most closely matches the size requested.

If allocations are random, first fit actually performs a bit better than best fit in terms of memory fragmentation. Fragmentation is the bane of all non-compacting allocators.