In this article we will be learning:

• Introduction to Heap
• brk() and sbrk() system call
• Unmapped region
• Dummy malloc()
• Organizing the Heap
• Memory block representation
• Malloc implementation
• calloc(), free() and realloc() implemtattaion

Heap:

• Heap is a memory region responsible for storing variables which are allocated dynamically that is fulfilling the different memory requests using memory managers libraries(malloc(), calloc() and realloc().

• In the above diagram we can see that heap is a continuous space of memory with three bounds:
  • A starting point
  • A maximum limit( can be managed via getrlimit() and setrlimit().
  • An end point called the break which marks the end of the memory which can be accessed for read and write.

Memory Region:

The memory region is divided into four important sections:

• Stack section: For storing the non-static local variables, volatile variables, context of the caller function during function call.
• Heap: For storing the variables allocated dynamically using malloc(), calloc() and realloc().
• Data Segment: It is again divided into two parts:
  • BSS segment or uninitialized segment: for storing uninitialized static variables, global variables, extern variables.
  • Initialized segment: For storing initialized static variables, global variables, extern , constant
• Text or code segment: For storing the instruction , binary and is read only memory.

For more details please refer to Memory layout of C program

Memory Allocators: brk() and sbrk() system call:

brk(): It stand for break and specifies the maximum space that can be allocated that is beyond which the program would break.

sbrk():  space increment after program break address, used to change the space allocated for the calling process that is alter the break value.

For more detail please refer: Memory allocators- brk() and sbrk().

As discussed internally malloc() uses the brk() and sbrk() system call for allocating a memory. But the below piece of code snippet is just a dummy C code for malloc() for giving the idea about internal working.

* An horrible dummy malloc */

 #include <sys/types.h>
 #include <unistd.h>

 void *malloc(size_t size)
 {
   void *p;
   p = sbrk (0); // This gives the old break point
   /* If sbrk fails , we return NULL */
   if (sbrk(size) == (void*) -1)
      return NULL;
   return p;
 }

Organizing the Heap:

When a memory is allocated with a malloc(), there is extra information called metadata or heap control data which is placed at the beginning of each chunk.

The control information placed in this metadata are:

• Size: Size of memory segment in bytes, without size of control data
• A flag indicating whether the chunk is free or not and
• Pointer to next heap entry in the list
• Pointer to previous heap entry in the list
• Pointer to data part

Of course, this block of information is before the pointer returned by malloc.

This can be translated into C with a doubly linked list as a data structure.

typedef struct meta_data *block
#define HEAP_NODE_SIZE sizeof(struct meta_data)

struct meta_data {
  size_t size;
  int free;
  struct meta_data *next;
  struct meta_data *prev;
};

Memory allocation(malloc):

To allocate a new memory region, the heap list is traversed until we find a free block with enough space for the asked size.

We begin at the base address of the heap and check the current chunk, if it fit the required asked size we just return the address, otherwise we continue to the next chunk until we find a fitting one(smallest free available block to satisfy the request).

If such a heap region is found , the new node is created and inserted into the heap list. It holds the information such as size, used flag, as well as pointer to previous and next chunk. Finally, the pointer is returned and is ready to be used.

If the heap region is not found, it returns NULL.

Consider that no memory is allocated until now:

The grey blocks denotes the first and only heap node and it occupies some memory of total heap memory itself.

Now consider a memory region of 100 bytes is requested:

Now consider a another request of 200 bytes, the heap would look like the following:

Extending the heap:

This scenario occurs when there is no fitting chunk for the required size. In this case we need to extend the heap. In this break is moved and initialize a new chunk and add this chunk at the end that is next field of last chunk should point to this new chunk.

Sample Functions:

CREATING A MEMORY CHUNK OF SIZE “SIZE”

#define HEAP_NODE_SIZE sizeof(struct meta_data)

struct meta_data *create_chunk(size_t size)
{
  struct meta_data *block;
  block = sbrk(0);
  if(sbrk(HEAP_NODE_SIZE + size) == (void*) -1)
     return NULL;

  block->size = size;
  block->free = 0;
  block->next = NULL;
  block->prev= NULL;
  return block;
}

FINDING A FREE BLOCK OF REQUESTED SIZE:

The only thing to take into consideration is to keep a track of the last chunk so that malloc function can extend the end of the heap if we do not find any fitting chunks

struct meta_data *find_free_block(size_t size, struct meta_data *last)
{
   struct meta_data *current_chunk = base_chunk;
   while ( (current_chunk && current_chunk->free == 0) &&
           (current_chunk->size >= size + HEAP_NODE_SIZE) &&
           (current_chunk->size <= MAX_HEAP_SIZE))
   {
      *last = current_chunk;
      current_chunk= current_chunk->next;
   }
   return current_chunk;
}

EXTENDING THE HEAP:

The above function is used when we did not get the required chunk in the memory and we need to request space from the OS using sbrk() and add our new block to the end of the linked list.

struct meta_data *extend_heap(struct meta_data *last, size_t size)
{
  struct meta_data *new = create_chunk(size);
  if (!new)
    return NULL;
  last->next= new_chunk;
  new_chunk->prev = last;
  return new_chunk; 
}

The above approach is first fit but in this case there is lot of memory wastage and also it suffers from fragmentation issue.

Due to frequent allocation and de-allocation of memory, there is a block of memory but they are not continuous hence it cannot be allocated.

Consider an example where a memory required is of 500 bytes and in first fit algorithm it traverses through the pool of memory chunk and find a chunk of size 700 bytes as 4th chunk.

So in this case the same memory of 700 bytes is allocated but the extra 200 bytes remains unused and in other case say 300 bytes is unused. Now in future if a request is made for 400 bytes it cannot be fulfilled as these 500 (200+300) bytes are not continuous. Such problem is called external or space fragmentation.

The solution to this problem is best fit algorithm which depends upon splitting the block if it happens to be more then the required size.

Split blocks:
A chunk is splitted when it is wide enough to hold the asked size plus a new chunk of size atleast (sizeof(struct meta_data) + 4).

void split_block(struct meta_data *org_chunk, size_t size)
{
   struct meta_data *new_chunk = org_chunk + HEAP_NODE_SIZE + size;
   new_chunk->size = org_chunk->size - size - HEAP_NODE_SZIE;
   new_chunk->next = org_chunk->next;
   new_chunk->next->prev = new_chunk;
   org_chunk->next= new_chunk;
   new_chunk->prev = org_chunk;
   org_chunk->size = size;
   new_chunk->free = 1;
} 

Considering that the above discussion is clear, we now move with the implementation of the malloc.

Algorithm:

• First initialize the base with NULL and align the requested size.
• If the base is not aligned that is empty at that point
  • create a new chunk, assign size, set free and set next and prev of new chunk = NULL and
  • base =new_chunk;
• If the base is initialized:
  • Search for the free chunk wide enough;
  • If the chunk is available:
    • Try to split the chunk if the difference between the requested size and size of the meta_data is enough to store the meta-data and minimal block of 4 bytes.
    • Mark the chunk as used(chunk->free = 0)
• Otherwise( if the free chunk is not found):
  • Create a new chunk, assign size and next pointer as NULL, free =1 and
  • Iterate through the list to get the last chunk and next of last = new chunk

Program:

Initialization:

Consider the heap itself is a normal array of bytes(unsigned char) with size HEAP_TOTAL_SIZE and HEAP_NODE_SIZE = sizeof(struct meta_data); and heapStart of type meta_data* points to start of the heap array. This pointer is never modified and always points to the first node of the list.

#define align4(x) (((((x) -1) > >2) < <2)+4)
struct meta_data *base = heapStart;


void *malloc(size_t size)
{
   size_t align_size = align(size);
   struct meta_data *block = NULL;
   struct meta_data *last;
   if(base == heapStart)
   {
      block = create_chunk(size);
      if (!block)
        return NULL;
      base = block;
   }
   else
   {
     block = find_free_block(size, last);
     if(block)
     {
        if(block->size >= align_size + HEAP_NODE_SIZE + 4) 
              split_block(block, size);
        block->free = 0;
     }
     else // if free block is not found means new chunk has to be appended at last
     {
         block = extend_heap(last , size);
         if(!block)
            return NULL;
     }
    return block + HEAP_NODE_SIZE;
}

free:

To deallocate, or free, an allocated region, the C library function free() is used to which a pointer to an memory region is passed that was previously allocated by malloc(), calloc() o realloc().

Since in the case of free we do not specify the size, hence at first from the pointer provided we need to subtract the heap control node to point to actual heap control list node of the memory region. Then it is marked free by clearing the free flag.

But if we merely stick with the above approach, the heap area would get filled with more and more heap control node and their corresponding freed memory region, resulting in fragmented heap. This would fail the allocation request as these region will not be continuous.

Fragmentataion:

A major issue of malloc is fragmentation: after several use of malloc and free, we end with
a heap divided in many chunks individually to satisfy small malloc but not the big malloc as they are not continuous. This issue is known as the space fragmentation or external fragmentation problem.

When we select a free chunk wider enough to hold the requested allocation and another
chunk, we split the current chunk. While this offer a better usage of the memory (the new
chunk is free for further reservation) it introduces more fragmentation.

A solution to eliminate some fragmentation is to fusion free chunks. When we free a chunk,
and its neighbors are also free, we can merge them in one bigger chunk eliminating the heap control node and resulting in a larger free memory region. All we have to do is
to test the next and previous chunks.

Thus having a double linked as a data structure for memory allocators comes handy in the case of free when we merge the chunks with its neighbors.

Consider the heap looks like below:

Now a request came to deallocate 50 bytes, so its flag is cleared a nd since its neighbors are not free so nothing can be done. The heap looks like below:

Now a request came to deallocate 200 bytes. Its flag is cleared. The successive block is free. So the freed memory region can be merged with successive block, removing the heap control node and merge the freed memory space to the successive block. There is no precedent block. So afterwards, the heap will look like in following figure:

The precedent block is also free, so merge the intermediate block with the precedent block. Finally, after deallocating the 200 memory region, the heap looks like in following figure:

Fusion Code:

struct meta_data *fusion(struct block *cur_chunk)
{
  if(cur_chunk->next && cur_chunk->next->free)
  {
    cur_chunk->size = cur_chunk->size + HEAP_NODE_SZIE + cur->next->size;
    cur_chunk->next= cur->next->next;
    cur_chunk->next->prev = cur_chunk;
 }
return cur_chunk;
}

The pointer passed to free should be a valid pointer and also we should get a pointer to meta data which holds the other important information about the allocated pointer such as the size.

Function for getting the metadata

struct meta_data *get_block(void *p)
{
   char *tmp = p;
   return return (p = tmp -= sizeof(struct meta_data);
}

Function for validating the pointer passed to free:

int valid_ptr(void *p)
{
   if(base)
   {
     if (p>base && p <sbrk(0))
      {
             /* ptr is pointing to data */
             return (p == ( get_block (p))->ptr );
      }
   return 0;
}

Algorithm for free function:

• Verify whether the pointer is a valid.
• If the address is valid:
  • We get the block address.
  • We mark it free
  • If there is a previous chunk and its free then we fusion the current chunk with the previous.
  • We also try fusion with the next block.
  • If its the last block, release the memory.
  • After freeing if there is no block we set the base = NULL;
• If the pointer is not valid, we return silently

free implementation:

void free(void *p)
{
   struct 
   if(valid_ptr(p))
   {
      struct meta_data *b;
      b = get_block(p);
      b->free = 1;
      if (b->prev && b->prev->free)
           b = fusion(b->prev);
      if(b->next)
        fusion(b);
      else
      {
        if(b->prev)
          b->prev->next= NULL;
        else // it was the last node
          base = heapStart;
        brk(b);
      }
    }
}

realloc:

• realloc is nothing but resizing chunks which is previously allocated by malloc() or calloc().
• If we pass realloc a NULL pointer, it is supposed to behave like malloc.
• It we pass previously allocated pointer, it should free up the space if the size is smaller than the previous size.
• If the new size happens to be bigger, it should allocate a new space and copy the existing data to new space and free up the old space.
• Syntax: void *ptr= realloc(void *ptr, size_t size);

There is one function for copying data from one location to another:

void copy_block (struct meta_data *src, struct meta_data *dst)
{
   int *sdata, *ddata;
   sdata = src->ptr;
   ddata = dst->ptr;
   while (*sdata)
   {
       *ddata = *sdata;
       *data++;
       *sdata++;
   }
}
       

Algorithm for realloc:

• Allocate a new block of the given size using malloc
• Copy data from old on to new one
• Free the old block
• Return the new pointer.

But there can be few scenarios where an algorithm should be optimized like we do not want to allocate a new memory if there is enough room at present memory location.

Please read realloc internal working for better understanding of algorithm

So optimized form of realloc algorithm is as follows:

• First check whether the pointer exist, if not:
  • call a malloc i.e malloc(size)
• If pointer is there:
  • get the metadata part of it by calling get_block()
  • If the asked size is less than the current size
  • No need to copy anything, just split the current block for better optimization of memory.
• If the asked size is more than current size
  • Here two cases comes:
  • If the free extra memory is adjacent to the current block
    • Merge them
    • If the size after merging is more than required
    • Again no need to copy anything, just split the current block for better optimization of memory.
  • If the free block is not adjacent, means a new memory of required size need to allocated:
    • Do malloc of asked size
  • If success:
    • Copy the old content to new memory
    • free the old memory
    • return the new pointer

C implementation:

void *realloc(void *ptr, int size)
{
   void *p;
   void *newptr;
   struct meta_data *meta;
   int org_size;
   if(!ptr)
   {
     p = malloc(size);
     if(!p)
       return NULL;
   }
   if(valid_addr(ptr))
   {
      meta = get_block(ptr);
      org_size = meta->size;
      /* If the new size is less then original size */
      if (meta->size >=size)
      {
          if (meta->size > size + HEAP_NODE_SIZE + 4)
             split_block(meta, size);
      }
      else
      {
        /* If current and its next can fulfil the new size requirement */
        if(meta->next && meta->next->free && 
             (meta->size + HEAP_NODE_SIZE + meta->next->size >=size))
        {
             fusion(meta);
             if (meta->size > size + HEAP_NODE_SIZE + 4)
                  split_block(meta, size);
        }
        else
        {
           /* if current and its next cannot fulfil the asked size, so altogether a new  
              a new memory need to be allocated and content need to be copied */
           newp = malloc(size);
           if(!newp)
               return NULL;
           copy_block(newptr, ptr, org_size);
           free(ptr);
           return newptr;
         }
       return ptr;
}
                    

calloc:

calloc() is a memory allocator API responsible for allocating ‘n’ memory block of memory each of size say ‘size’.

Algorithm for calloc is straightforward:

• Use malloc with the right size( n *size).
• Put 0 in each bytes

The data block size in the chunk is always a multiple of 4, so iterate by 4 bytes steps

void *calloc(size_t number , size_t size ){
 struct meta_data *new;
 size_t s4 ,i;
 new = malloc(number * size );
 if (new) {
    s4 = align4(number * size) << 2;
    for (i=0; i<s4 ; i++)
    new[i] = 0;
 }
 return (new );
}

References:

• Malloc_tutorial.pdf (epita.fr)
• Malloc tutorial (danluu.com)
• Sample implementation of C memory functions (sunshine2k.de)

Categories: C Language