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.