OS-DEV: malloc/free - the secrets revealed

back
The average programmer uses them with almost no thought about the background. He just orders memory during runtime of his program
and gives it back to the system - so it seems to him. The OS Developer of such a library has of course other things to take care of: how to split the
memory, the Operating System sets aside for especially this purpose, in small and smaller chunks as the programmer needs them. To manage
this region, also called Heap, in the standard c library, a set of functions is known: malloc(), free(). They hand out resp. take back memory chunks.

malloc and free aren't difficult to develop nor to implement. You just need to keep in mind: you assign the malloc library an adress to work with,
which the OS has to map into the process adress space. It is up to you to decide, where to place it.

Then, you'll need a structure to keep some bookkeeping data: let's call it chunk_t. Below, you can see a layout of chunk_t:

Upon initializing the malloc library (at the first usage of malloc() is recommended for this operation) you place some data at the beginning of the heap:
chunk_t *used_head,*used_tail; chunk_t *free_head,*free_tail; you have to place them by hand, ie incrementing the actual position counter by
sizeof(chunk_t), casting the adress to chunk_t and placing the initial values there. It looks like this, assuming, the start of the heap is 0xc0500000. 
       //definitions!
       typedef struct MEM{
         adresse_t *block_adresse;
         uint_t block_length;
         struct mem *next;
       } mem_t;

       typedef struct mem_list{
         mem_t *head; //um schnell durch das speicherblock-array zu marschieren
         mem_t *tail;
       } mem_list_t;
       
       //declaration of variable used blocks:
       mem_list_t used_blocks;
       //declaration of variable free blocks:
       mem_list_t free_blocks;
       
       //somewhere, the lists are initialized, say in a function 'malloc_init();'
       free_blocks.head=(mem_t *)0xc0500000;
       free_blocks.tail=free_blocks.head;
       free_blocks.head->next=NULL;
       used_blocks.head=(mem_t *)0xc0500060;
       used_blocks.ende=used_blocks.head;
       used_blocks.head->next=NULL;


Having done all this initialization stuff and knowing, what datatypes we need, we can proceed to what to do next:

Allocating a memory area for further use.
This can be done as follows:

Now, lets have a look at how to free an allocated memory region:
basically, it's nothing more than taking the adress to be freed, traverse the list of used blocks, remove the block in question and attach it to the
list of free blocks. Now, look at it in Detail:

look at the illustration above to see, how a heap can look like after several allocations/deallocations of memory chunks:

You see, it is not as grim as it looks like on the first glance. What you will of course need is a decent knowledge about how to handle linked lists.

Think further. What might be useful? What can happen? How does the Operating System deal out Memory?
back