malloc/free implementation. Just4Fun!

Thu 26 November 2015

Some time ago I bought the The Linux Programming Interface book, one of the best books I have acquired. One of the first chapters I read were about memory allocation. At the end of the chapter, author offers some exercises to the reader. Among them there is a challenging one. He suggests to implement the equivalent to the malloc and free functions. The challenge has been accepted!

First of all, this implementation is just for study purposes. It means you should NOT start to implement your malloc and free functions for production programs. Do not reinvent the wheel! The glibc are being improved for decades for many great guys. You probably will take more time to do the equivalent excellent work! ;)

I assume that you know a little bit about how a process and its segments works. It is nice remember this code does not cover all details. As any software it can be improved (a lot).

System calls

There are two system calls allows the program to increase the program break, brk and sbrk. The program break defines where is the end of process's data segment. It means if the program increases the program break, memory is allocated. Otherwise, it deallocate memory. In this code only sbrk is used, its only parameter defines the amount of memory program wants to increase. If the program break has being increased successfully, a pointer to the beginning of the allocated memory is returned. Otherwise, (void*) -1 is returned. brk is not being used. It allows the program set the end of data segment to the pointer passed in the functions arguments. I think this function is not being in use because the code does not decrease the program break. Maybe in the future I implement this feature and use the brk system call.

For more details, take a look in the man page. ;)

Code

/** * This source code contains a simple malloc and free functions implementation. * It was created just for study purposes */ #include #include "memory.h" #define HEADER_SIZE sizeof(Header) #define NUNITS(bytes) bytes / HEADER_SIZE struct header { unsigned int size; //memory block size in bytes struct header *next; //next memory block in the free list }; typedef struct header Header; static Header* increase_heap(unsigned int); static Header *free_list = NULL; static Header base; void* memory_alloc(size_t bytes) { Header *block; Header *previous = &base; unsigned int nunits = NUNITS(bytes); if(!nunits) nunits = 1; if(!free_list){ //first call Header *block = increase_heap(nunits); block->next = &base; base.size = 0; base.next = block; free_list = &base; } //look for a memory block with enough size for(block = base.next; block != &base; previous = block, block = block->next ){ if(nunits <= block->size){ if(nunits == block->size){ //the current memory block has exactly size! \o/ previous->next = block->next; block->next = NULL; return block + 1; } //the block is bigger. Let's split it Header *remain_block = block + 1 + nunits; remain_block->size = block->size - 1 - nunits; remain_block->next = block->next; previous->next = remain_block; block->size = nunits; return block + 1; } } //need more memory block = increase_heap(nunits); return block + 1; } void memory_free(void* ptr) { Header *fblock = ((Header*)ptr) - 1; Header *block; Header *previous = &base; for(block = base.next; block != &base; previous = block, block = block->next){ //let's find an adjacent memory block if((block + 1 + block->size) == fblock){ block->size += fblock->size; ptr = NULL; return; } else if((fblock + 1 + fblock->size) == block){ fblock->size += block->size + 1; fblock->next = block->next; previous->next = fblock; ptr = NULL; return; } } previous->next = fblock; fblock->next = &base; ptr = NULL; } Header* increase_heap(unsigned int units) { #define MIN_ALLOC HEADER_SIZE * 2 Header *block; if(units <= 1) block = (Header*) sbrk(MIN_ALLOC); else block = (Header*) sbrk( (1 + units) * HEADER_SIZE); block->size = units; block->next = NULL; return block; }

The cornerstone of the code is a linked list, called free_list. It stores all available memories blocks. Each element is composed for a header and the memory itself. The header is a structure that contains two metadata. The first field of the struct is block's size and the second is a pointer to next memory block in the free_list. The first thing necessary when a program request some memory is check if the free_list is already initialized (line 29). If not, it is initiated with a block of 0 size (lines 29 ~ 36). This is done to keep the first element in the list always the same. Thus, it is more easy to know when stop a loop through the list and reduce the code complexity.

Once free_list initiated, a search in the list is performed. Looking for a memory block with enough size to attempt the request. The algorithm follows the 'first fit' approach. It means that the first memory block found with enough size is split and returned a pointer to the memory to the caller (lines 38 ~ 53). If any block has enough size, the heap is increased and the new memory is returned (line 55). The pointer returned to the user is a pointer to the memory block itself. It is not include the header. Does not make sense give to caller access to the control structures. This structure is used only for memory management and to know what is the memory block size when the program wants to frees it.

As you can see between lines 26 and 28, all memory blocks are multiple of the header size. It means the minimum memory size allocated is the HEADER_SIZE * 2 (with the header). This approach facilitate the pointer arithmetic and avoid counting every single byte. In other words, even if the user requests less memory, the allocated memory will be always multiple of the HEADER_SIZE.

When the user wants to free a pointer, another search in the free_list is performed. This time, looking for a memory block next the to the block is being freed. If a block is found, the two blocks are merged into one (lines 64 ~ 77). Otherwise, the block is appended in the list (lines 78 ~ 80). The goal of merge close blocks is avoid memory fragmentation. ;)

According to my weak skill in asymptotic analysis, both functions have running time of O(n). Since each functions performed a search in the free_list. Please, tell me if I am wrong. I will study more about this topic and correct if I wrote bullshit. The following sources are the header and a test program.

#ifndef _MEMORY_HEADER #define _MEMORY_HEADER /** * Allocates a block of memory with bytes of length * @returns a pointer to the allocated block of memory. Return NULL in error */ void* memory_alloc(size_t bytes); /** * Deallocates the ptr block of memory * @returns 0 on success */ void memory_free(void* ptr); #endif

#include #include #include #define LOOP 10 #define ARRAY_LENGTH 10 struct ordinary { int a; float b; double c; long d; char e; void *f; }; int main(){ memory_free(memory_alloc(2048)); int *i = (int*) memory_alloc(sizeof(int)); int *i2 = (int*) memory_alloc(sizeof(int)); *i = 2; *i2 = 100; printf("%d + %d = %d\n", *i, *i2, *i + *i2); memory_free(i2); memory_free(i); i = (int*) memory_alloc(sizeof(int)); *i = 0; unsigned int index = 0; for(index = 0; index < LOOP; index++ ){ int *int_ptr = (int*) memory_alloc(sizeof(int)); *int_ptr = index; *i += *int_ptr; memory_free(int_ptr); } printf("The sum of 0 until %d is %d\n", LOOP, *i); memory_free(memory_alloc(2048)); memory_free(memory_alloc(2048)); memory_free(memory_alloc(2048 * 5)); struct ordinary *op = (struct ordinary*) memory_alloc(sizeof(struct ordinary)); op->a = 1; op->b = 1.0f; op->c = 9.99; op->d = 999l; op->e = 'a'; op->f = i; printf("a = %d, b = %f, c = %f, d = %ld, e = %c, f = %p\n", op->a, op->b, op->c, op->d, op->e, op->f); memory_free(op); int *ia = (int*) memory_alloc(sizeof(int) * ARRAY_LENGTH); for(index = 0; index < ARRAY_LENGTH; ++index){ ia[index] = index * 2; } printf("[ "); for(index = 0; index < ARRAY_LENGTH; ++index){ if(index < ARRAY_LENGTH -1) printf("%d, ", ia[index]); else printf("%d", ia[index]); } printf(" ]\n"); memory_free(ia); exit(EXIT_SUCCESS); }

Feel free to ask me in the comments. =]

References

brk, sbrk

The Linux Programing Interface

The C Programming Language

Repository

vanz

malloc/free implementation. Just4Fun!

System calls

Code

References