memory allocator

 A process runs within its own virtual address space that’s distinct from the virtual address spaces of other processes. This virtual address space typically comprises of 5 sections:

Text section: The part that contains the binary instructions to be executed by the processor.
Data section: Contains non-zero initialized static data.
BSS (Block Started by Symbol) : Contains zero-initialized static data. Static data uninitialized in program is initialized 0 and goes here.
Heap: Contains the dynamically allocated data.
Stack: Contains your automatic variables, function arguments, copy of base pointer etc. 




As you can see in the image, the stack and the heap grow in the opposite directions.
Sometimes the data, bss and heap sections are collectively referred to as the “data segment”,
the end of which is demarcated by a pointer named program break or brk.


That is, brk points to the end of the heap.


Now if we want to allocate more memory in the heap, we need to request the system to increment brk.

Similarly, to release memory we need to request the system to decrement brk.

Assuming we run Linux (or a Unix-like system), we can make use of sbrk() system call that lets us manipulate the program break.








Calling sbrk(0) gives the current address of program break.
Calling sbrk(x) with a positive value increments brk by x bytes, as a result allocating memory.
Calling sbrk(-x) with a negative value decrements brk by x bytes, as a result releasing memory.
On failure, sbrk() returns (void*) -1.







To be honest, sbrk() is not our best buddy in 2016. There are better alternatives like mmap() available today. sbrk() is not really thread safe. It can can only grow or shrink in LIFO order.




However, the glibc implementation of malloc still uses sbrk() for allocating memory that’s not too big in size.^[1]
So, we will go ahead with sbrk() for our simple memory allocator.

The malloc(size) function allocates size bytes of memory and returns a pointer to the allocated memory.
Our simple malloc will look like:

void *malloc(size_t size)
{
 void *block;
 block = sbrk(size);
 if (block == (void*) -1)
  return NULL;
 return block;
}

So now, we have two things to store for every block of allocated memory:
    1. size
    2. Whether a block is free or not-free?

The header will look something like this:

struct header_t {
 size_t size;
 unsigned is_free;
};

When a program requests for size bytes of memory, we calculate total_size = header_size + size, and call sbrk(total_size). We use this memory space returned by sbrk() to fit in both the header and the actual memory block. The header is internally managed, and is kept completely hidden from the calling program.

Now, each one of our memory blocks will look like:

Our header will now look like:

struct header_t {
 size_t size;
 unsigned is_free;
 struct header_t *next;
};

and the linked list of memory blocks like this:

void *malloc(size_t size)
{
 size_t total_size;
 void *block;
 struct header_t *header;
 if (!size)
  return NULL;
 pthread_mutex_lock(&global_malloc_lock);
 header = get_free_block(size);
 if (header) {
  header->is_free = 0;
  pthread_mutex_unlock(&global_malloc_lock);
  return (void*)(header + 1);
 }
 total_size = sizeof(struct header_t) + size;
 block = sbrk(total_size);
 if (block == (void*) -1) {
  pthread_mutex_unlock(&global_malloc_lock);
  return NULL;
 }
 header = block;
 header->size = size;
 header->is_free = 0;
 header->next = NULL;
 if (!head)
  head = header;
 if (tail)
  tail->next = header;
 tail = header;
 pthread_mutex_unlock(&global_malloc_lock);
 return (void*)(header + 1);
}

struct header_t *get_free_block(size_t size)
{
 struct header_t *curr = head;
 while(curr) {
  if (curr->is_free && curr->size >= size)
   return curr;
  curr = curr->next;
 }
 return NULL;
}