Let's dive into the fascinating world of dynamic memory allocation by building our own malloc in C! Understanding how malloc works under the hood is not only a great learning experience but also empowers you to optimize memory usage in your applications. This article will guide you through the process step-by-step, providing insights into the core concepts and implementation details.

Why Implement Your Own Malloc?

Before we jump into the code, let's understand the motivations behind creating a custom malloc. While the standard library's malloc is generally sufficient, there are scenarios where a custom implementation can shine:

• Learning and Understanding: Implementing malloc provides a deep understanding of memory management concepts, such as heap organization, fragmentation, and garbage collection.
• Performance Optimization: Custom malloc implementations can be tailored to specific application needs, potentially improving performance by reducing overhead and fragmentation. For instance, if you know that your application will only allocate small blocks of memory, you can optimize your malloc for that specific case.
• Debugging and Profiling: A custom malloc allows you to add debugging and profiling features, such as memory leak detection and allocation tracing, which can be invaluable for identifying and resolving memory-related issues.
• Embedded Systems: In resource-constrained environments like embedded systems, a lightweight custom malloc can be more suitable than the standard library's implementation.

Core Concepts

Before we start coding, let's review some fundamental concepts:

• Heap: The heap is a region of memory that is used for dynamic memory allocation. It's a large pool of memory from which malloc carves out blocks for your program.
• Memory Blocks: malloc divides the heap into blocks. Each block can be either allocated (in use by your program) or free (available for allocation).
• Metadata: Each memory block typically has associated metadata, such as its size and whether it's free or allocated. This metadata is crucial for managing the heap.
• Fragmentation: Fragmentation occurs when the heap becomes divided into small, non-contiguous blocks of free memory. This can make it difficult to allocate large blocks, even if the total amount of free memory is sufficient. There are two types of fragmentation: internal and external. Internal fragmentation occurs when a block is larger than the requested size, and the excess memory within the block is wasted. External fragmentation occurs when there is enough total free memory, but it is not contiguous, making it impossible to allocate a large block.

Basic Structure

At its heart, a custom malloc implementation needs to manage a data structure representing the heap. Let's define a simple structure to represent a memory block:

typedef struct block_meta {
 size_t size;
 struct block_meta *next;
 int free;
} block_meta;

Here's what each field represents:

• size: The size of the data block (excluding the metadata).
• next: A pointer to the next block in the heap (for maintaining a linked list of blocks).
• free: A flag indicating whether the block is free (1) or allocated (0).

Initializing the Heap

Before we can allocate memory, we need to initialize the heap. We can use the sbrk system call to extend the program's data segment, effectively allocating memory for the heap.

#include <unistd.h>

#define HEAP_SIZE (1024 * 1024) // 1MB

block_meta *head = NULL;

void *init_heap() {
 head = sbrk(0);
 void *heap = sbrk(HEAP_SIZE);
 if (heap == (void *) -1) {
 return NULL; // sbrk failed
 }
 head->size = HEAP_SIZE - sizeof(block_meta);
 head->next = NULL;
 head->free = 1;
 return heap;
}

This function allocates a chunk of memory of size HEAP_SIZE and initializes the head block to represent the entire heap as a single free block.

Implementing malloc

Now, let's implement the malloc function. The basic steps are as follows:

1. Search for a free block that is large enough to satisfy the allocation request.
2. If a suitable block is found, mark it as allocated.
3. If the block is significantly larger than the requested size, split it into two blocks: one allocated block and one free block.
4. Return a pointer to the beginning of the allocated block's data area.

void *malloc(size_t size) {
 if (size <= 0) {
 return NULL;
 }

 block_meta *block = find_free_block(size);
 if (!block) {
 block = request_space(size);
 if (!block) {
 return NULL; // Failed to allocate space
 }
 }
 else {
 block->free = 0;
 }

 return (block + 1); // Return pointer to data area
}

Helper Functions

We'll need a few helper functions to make malloc work:

find_free_block

This function searches the linked list of blocks for a free block that is large enough to accommodate the requested size.

block_meta *find_free_block(size_t size) {
 block_meta *current = head;
 while (current) {
 if (current->free && current->size >= size) {
 return current;
 }
 current = current->next;
 }
 return NULL;
}

request_space

This function is called when no suitable free block is found. It allocates a new block of memory using sbrk and adds it to the linked list.

block_meta *request_space(size_t size) {
 block_meta *block = sbrk(0);
 void *request = sbrk(size + sizeof(block_meta));
 if (request == (void*) -1) {
 return NULL; // sbrk failed.
 }

 block->size = size;
 block->next = NULL;
 block->free = 0;

 if (!head) {
 head = block;
 return block;
 }

 block_meta *current = head;
 while (current->next) {
 current = current->next;
 }
 current->next = block;
 return block;
}

Implementing free

The free function is responsible for marking a previously allocated block as free, allowing it to be reused by subsequent malloc calls. A basic implementation looks like this:

void free(void *ptr) {
 if (!ptr) {
 return;
 }

 block_meta *block = (block_meta*)ptr - 1;
 block->free = 1;
}

Splitting Blocks

To reduce internal fragmentation, we can split a free block if it's significantly larger than the requested size. Here's how we can modify find_free_block to include splitting:

#define MIN_BLOCK_SIZE 128 // Minimum block size after splitting

block_meta *find_free_block(size_t size) {
 block_meta *current = head;
 while (current) {
 if (current->free && current->size >= size) {
 // Check if we can split the block
 if (current->size > size + sizeof(block_meta) + MIN_BLOCK_SIZE) {
 split_block(current, size);
 return current;
 }
 return current;
 }
 current = current->next;
 }
 return NULL;
}

void split_block(block_meta *block, size_t size) {
 block_meta *new_block = (block_meta*)((char*)block + sizeof(block_meta) + size);
 new_block->size = block->size - size - sizeof(block_meta);
 new_block->next = block->next;
 new_block->free = 1;

 block->size = size;
 block->next = new_block;
}

Coalescing Free Blocks

To combat external fragmentation, we can coalesce adjacent free blocks into larger free blocks. This can be done in the free function:

void free(void *ptr) {
 if (!ptr) {
 return;
 }

 block_meta *block = (block_meta*)ptr - 1;
 block->free = 1;
 coalesce_blocks(block);
}

void coalesce_blocks(block_meta *block) {
 if (block->next && block->next->free) {
 block->size += block->next->size + sizeof(block_meta);
 block->next = block->next->next;
 }
}

Putting It All Together

Here's the complete code, incorporating all the improvements we've discussed:

#include <stdio.h>
#include <unistd.h>

typedef struct block_meta {
 size_t size;
 struct block_meta *next;
 int free;
} block_meta;

#define HEAP_SIZE (1024 * 1024) // 1MB
#define MIN_BLOCK_SIZE 128 // Minimum block size after splitting

block_meta *head = NULL;

void *init_heap();
void *malloc(size_t size);
void free(void *ptr);
block_meta *find_free_block(size_t size);
block_meta *request_space(size_t size);
void split_block(block_meta *block, size_t size);
void coalesce_blocks(block_meta *block);

int main() {
 init_heap();

 int *data = (int*) malloc(100 * sizeof(int));
 if (data == NULL) {
 printf("Failed to allocate memory\n");
 return 1;
 }

 for (int i = 0; i < 100; i++) {
 data[i] = i;
 }

 for (int i = 0; i < 100; i++) {
 printf("%d ", data[i]);
 }
 printf("\n");

 free(data);

 return 0;
}

void *init_heap() {
 head = sbrk(0);
 void *heap = sbrk(HEAP_SIZE);
 if (heap == (void *) -1) {
 return NULL; // sbrk failed
 }
 head->size = HEAP_SIZE - sizeof(block_meta);
 head->next = NULL;
 head->free = 1;
 return heap;
}

void *malloc(size_t size) {
 if (size <= 0) {
 return NULL;
 }

 block_meta *block = find_free_block(size);
 if (!block) {
 block = request_space(size);
 if (!block) {
 return NULL; // Failed to allocate space
 }
 }

 block->free = 0;
 return (block + 1); // Return pointer to data area
}

void free(void *ptr) {
 if (!ptr) {
 return;
 }

 block_meta *block = (block_meta*)ptr - 1;
 block->free = 1;
 coalesce_blocks(block);
}

block_meta *find_free_block(size_t size) {
 block_meta *current = head;
 while (current) {
 if (current->free && current->size >= size) {
 // Check if we can split the block
 if (current->size > size + sizeof(block_meta) + MIN_BLOCK_SIZE) {
 split_block(current, size);
 return current;
 }
 return current;
 }
 current = current->next;
 }
 return NULL;
}

block_meta *request_space(size_t size) {
 block_meta *block = sbrk(0);
 void *request = sbrk(size + sizeof(block_meta));
 if (request == (void*) -1) {
 return NULL; // sbrk failed.
 }

 block->size = size;
 block->next = NULL;
 block->free = 0;

 if (!head) {
 head = block;
 return block;
 }

 block_meta *current = head;
 while (current->next) {
 current = current->next;
 }
 current->next = block;
 return block;
}

void split_block(block_meta *block, size_t size) {
 block_meta *new_block = (block_meta*)((char*)block + sizeof(block_meta) + size);
 new_block->size = block->size - size - sizeof(block_meta);
 new_block->next = block->next;
 new_block->free = 1;

 block->size = size;
 block->next = new_block;
}

void coalesce_blocks(block_meta *block) {
 if (block->next && block->next->free) {
 block->size += block->next->size + sizeof(block_meta);
 block->next = block->next->next;
 }
}

Testing and Debugging

Thorough testing is crucial to ensure the correctness and robustness of your custom malloc implementation. Use a variety of test cases, including allocating and freeing blocks of different sizes, allocating many small blocks, and allocating very large blocks. Tools like Valgrind can help detect memory leaks and other memory-related errors.

Conclusion

Implementing your own malloc in C is a challenging but rewarding exercise. It provides a deep understanding of dynamic memory allocation and empowers you to optimize memory usage in your applications. While this article provides a basic implementation, there are many ways to extend and improve it, such as adding support for different allocation strategies, implementing garbage collection, and improving fragmentation management. So go ahead, experiment, and create your own malloc!