Bigger Example 1: Custom Memory Allocator
Question: Develop a basic memory allocator that mimics the functionality of malloc() and free() in C. The allocator should manage a pool of memory and provide functions for allocating and freeing memory blocks. Implement features such as coalescing adjacent free blocks to optimize memory usage.
Below is a simple implementation of a basic memory allocator in C that mimics the functionality of malloc()
and free()
. The allocator manages a pool of memory and provides functions for allocating and freeing memory blocks. It also includes a basic coalescing mechanism to optimize memory usage.
#include <stdio.h>
#include <stdlib.h>
#define MEMORY_POOL_SIZE 1024
typedef struct Block {
size_t size;
struct Block* next;
} Block;
static char memoryPool[MEMORY_POOL_SIZE];
static Block* freeList = NULL;
void initializeAllocator() {
// Initialize the allocator with a single block representing the entire memory pool
freeList = (Block*)memoryPool;
freeList->size = MEMORY_POOL_SIZE - sizeof(Block);
freeList->next = NULL;
}
void* myMalloc(size_t size) {
if (size == 0 || size > MEMORY_POOL_SIZE) {
return NULL; // Invalid size
}
Block* current = freeList;
Block* previous = NULL;
// Find the first block that is large enough to accommodate the requested size
while (current != NULL && (current->size < size)) {
previous = current;
current = current->next;
}
if (current == NULL) {
return NULL; // Out of memory
}
// If the block is larger than needed, split it into two blocks
if (current->size > size + sizeof(Block)) {
Block* newBlock = (Block*)((char*)current + sizeof(Block) + size);
newBlock->size = current->size - sizeof(Block) - size;
newBlock->next = current->next;
current->size = size;
current->next = newBlock;
}
// Remove the allocated block from the free list
if (previous == NULL) {
freeList = current->next;
} else {
previous->next = current->next;
}
return (void*)((char*)current + sizeof(Block));
}
void myFree(void* ptr) {
if (ptr == NULL) {
return; // Invalid pointer
}
// Add the freed block back to the free list
Block* block = (Block*)((char*)ptr - sizeof(Block));
block->next = freeList;
freeList = block;
// Coalesce adjacent free blocks
Block* current = freeList;
while (current != NULL && current->next != NULL) {
if ((char*)current + sizeof(Block) + current->size == (char*)current->next) {
// Merge current and the next block
current->size += sizeof(Block) + current->next->size;
current->next = current->next->next;
} else {
current = current->next;
}
}
}
int main() {
initializeAllocator();
// Example usage
int* a = (int*)myMalloc(sizeof(int));
*a = 42;
printf("Allocated memory for integer: %d\n", *a);
double* b = (double*)myMalloc(sizeof(double));
*b = 3.14;
printf("Allocated memory for double: %f\n", *b);
myFree(a);
printf("Freed memory for integer\n");
char* c = (char*)myMalloc(50);
printf("Allocated memory for char array\n");
myFree(b);
myFree(c);
return 0;
}
Let's break down the provided C code step by step:
Header Files:
#include <stdio.h>
#include <stdlib.h>
These are standard header files in C. <stdio.h>
is for input/output operations, and <stdlib.h>
is for memory allocation and other standard library functions.
Macros:
#define MEMORY_POOL_SIZE 1024
Defines the size of the memory pool, which is a fixed-size array named memoryPool
. This is the total amount of memory that the allocator manages.
Data Structure:
typedef struct Block {
size_t size;
struct Block* next;
} Block;
Defines a structure Block
representing a memory block. It contains the size of the block and a pointer to the next block.
Global Variables:
static char memoryPool[MEMORY_POOL_SIZE];
static Block* freeList = NULL;
memoryPool
is an array of characters representing the memory pool.freeList
is a pointer to the linked list of free memory blocks.
Function: initializeAllocator()
void initializeAllocator() {
freeList = (Block*)memoryPool;
freeList->size = MEMORY_POOL_SIZE - sizeof(Block);
freeList->next = NULL;
}
Initializes the allocator by setting the free list to the beginning of the memory pool.
The size of the initial block is set to the entire size of the memory pool minus the size of the
Block
structure.
Function: myMalloc(size_t size)
void* myMalloc(size_t size) {
if (size == 0 || size > MEMORY_POOL_SIZE) {
return NULL; // Invalid size
}
// ...
}
Checks if the requested size is valid.
Searches for the first free block that can accommodate the requested size.
If the block is larger than needed, it is split into two blocks.
Removes the allocated block from the free list and returns a pointer to the allocated memory.
Function: myFree(void* ptr)
void myFree(void* ptr) {
if (ptr == NULL) {
return; // Invalid pointer
}
// ...
}
Checks if the pointer is valid.
Adds the freed block back to the free list.
Coalesces adjacent free blocks to optimize memory usage.
Function: main()
int main() {
initializeAllocator();
// ...
}
- Calls
initializeAllocator()
to set up the memory allocator.
int* a = (int*)myMalloc(sizeof(int));
*a = 42;
printf("Allocated memory for integer: %d\n", *a);
- Allocates memory for an integer, sets its value, and prints the allocated memory.
double* b = (double*)myMalloc(sizeof(double));
*b = 3.14;
printf("Allocated memory for double: %f\n", *b);
- Allocates memory for a double, sets its value, and prints the allocated memory.
myFree(a);
printf("Freed memory for integer\n");
- Frees the memory allocated for the integer and prints a message.
char* c = (char*)myMalloc(50);
printf("Allocated memory for char array\n");
- Allocates memory for a character array and prints a message.
myFree(b);
myFree(c);
- Frees the memory allocated for the double and character array.
Summary:
The code implements a simple memory allocator with a fixed-size memory pool and basic memory allocation and deallocation functions.
It maintains a linked list of free memory blocks, coalescing adjacent free blocks to optimize memory usage.
The
main()
function demonstrates the usage of the allocator by allocating and freeing memory for different data types.