Bigger Example 1: Custom Memory Allocator

PublishedDecember 28, 2023

I am Jyotiprakash, a deeply driven computer systems engineer, software developer, teacher, and philosopher. With a decade of professional experience, I have contributed to various cutting-edge software products in network security, mobile apps, and healthcare software at renowned companies like Oracle, Yahoo, and Epic. My academic journey has taken me to prestigious institutions such as the University of Wisconsin-Madison and BITS Pilani in India, where I consistently ranked among the top of my class.

At my core, I am a computer enthusiast with a profound interest in understanding the intricacies of computer programming. My skills are not limited to application programming in Java; I have also delved deeply into computer hardware, learning about various architectures, low-level assembly programming, Linux kernel implementation, and writing device drivers. The contributions of Linus Torvalds, Ken Thompson, and Dennis Ritchie—who revolutionized the computer industry—inspire me. I believe that real contributions to computer science are made by mastering all levels of abstraction and understanding systems inside out.

In addition to my professional pursuits, I am passionate about teaching and sharing knowledge. I have spent two years as a teaching assistant at UW Madison, where I taught complex concepts in operating systems, computer graphics, and data structures to both graduate and undergraduate students. Currently, I am an assistant professor at KIIT, Bhubaneswar, where I continue to teach computer science to undergraduate and graduate students. I am also working on writing a few free books on systems programming, as I believe in freely sharing knowledge to empower others.

Comments

Join the discussion

No comments yet. Be the first to comment.

C Programming

Part 1 of 50

More from this blog

Computer Arithmetic: From Fast Adders to Floating-Point

Arithmetic is the beating heart of every processor. Whether your machine is rendering 3-D graphics, training a neural network, or simply incrementing a loop counter, the ALU (Arithmetic Logic Unit) is doing the heavy lifting. In this deep-dive, I wan...

Feb 12, 202629 min read

The Complete Memory Hierarchy: From Semiconductor RAM to Virtual Memory

The performance gap between processors and main memory has been widening for decades. Modern processors can execute billions of instructions per second, but accessing data from main memory takes hundreds of processor cycles. This disparity creates a ...

Jan 7, 202670 min read

The Ultimate Spring Boot Guide: From Fundamentals to Production-Ready REST APIs

Introduction Welcome to the most comprehensive Spring Boot guide you'll find! This isn't just another tutorial that skims the surface. We're going to dive deep into every concept, explain every annotation, walk through every line of code, and underst...

Dec 26, 2025125 min read

Understanding Functions, Memory, and Pointers in C: A Complete Guide

Part 1: Functions and the Call Stack Before we can understand pointers and memory management in C, we need to understand how functions work and what happens behind the scenes when your program runs. This foundation will make everything else click int...

Dec 16, 202583 min read

Datapath and Control

The Basic Processing Unit is the brain of every computer. It fetches instructions from memory, decodes them, and executes the operations they specify. Whether you're running a simple addition or a complex algorithm, every operation flows through this...

Dec 10, 202534 min read

Jyotiprakash's Blog

251 posts

I'm Jyotiprakash, a software dev and professor at KIIT, with expertise in system programming.

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.

Command Palette