Ever wondered how your computer allocates memory during program execution? Why do specialized memory allocators improve systems programming performance? Although most high-level programming languages abstract memory allocation, it is a vital procedure that impacts your program's performance and stability. Runtime dynamic memory allocation is a low-level memory management strategy. This blogpost simulates dynamic memory management using linked lists to learn about it. 

 

Understanding Memory Allocation 

 Dynamic memory allocation occurs during runtime in modern computer languages, unlike static memory allocation at compile time. C programs can use malloc() and free() to request and release heap memory, which the operating system allocates dynamically. 

The heap allocates memory for variables with unknown sizes at compile time. However, the programmer must efficiently manage heap memory. Memory allocators dynamically request, use, and release memory to maximize efficiency. 

Standard memory allocators are usually adequate, but bespoke ones can improve control and speed. This is particularly true in resource-constrained systems programming or embedded systems. 

Introduction to Linked Lists 

Every node in a linked list has data and a pointer to the next node. Linked lists are helpful for dynamic data storage because they can insert and remove items efficiently without contiguous memory space, unlike arrays. 

For memory management, linked lists may monitor free memory blocks. Traverse the list to discover blank memory blocks. Linked lists provide dynamic memory allocation and deallocation without a fixed-size array or memory pool.

Simulating a Memory Allocator

Let's simulate a simple memory allocator using linked lists. This technique builds a linked list-based memory block allocator. And the major operations we're using for our allocator are malloc and free.

Step 1: Define the Block Structure 

Start by defining a memory block structure. Each block will include its size and a pointer to the next block in the list.

typedef struct Block {
    size_t size;
    struct Block* next;
} Block;

Step 2: Create a Linked List of Free Blocks

Next, we need a linked list for free memory blocks. First, all memory is free and in one huge block.

Block* freeList = NULL;

Step 3: Implement the malloc Function

The malloc method finds the first free block big enough to meet the memory request by traversing the linked list. Find a block, allocate it, then divide the rest into a smaller free block if needed.

void* my_malloc(size_t size) {
    Block* prev = NULL;
    Block* curr = freeList;

    // Traverse the free list to find a suitable block
    while (curr != NULL) {
        if (curr->size >= size) {
            // If the block is large enough, allocate it
            if (curr->size > size + sizeof(Block)) {
                // Split the block if it's too large
                Block* nextBlock = (Block*)((char*)curr + size);
                nextBlock->size = curr->size - size - sizeof(Block);
                nextBlock->next = curr->next;
                curr->size = size;
                curr->next = NULL;
            }

            // Remove the allocated block from the free list
            if (prev == NULL) {
                freeList = curr->next;
            } else {
                prev->next = curr->next;
            }

            return (void*)(curr + 1); // Return the memory after the Block header
        }
        prev = curr;
        curr = curr->next;
    }

    // If no suitable block is found, return NULL
    return NULL;
}

Step 4: Implement the free Function

The free function returns the block to the free list when memory is no longer required. Returning the freed block to the list and merging nearby blocks if feasible reduces fragmentation.

void my_free(void* ptr) {
    Block* block = (Block*)ptr - 1; // Get the Block header

    // Insert the freed block back into the free list
    block->next = freeList;
    freeList = block;
}

Example Code

Let's see a comprehensive example of how to use the linked list-based allocator for malloc and free:

#include <stddef.h>

typedef struct Block {
    size_t size;
    struct Block* next;
} Block;

Block* freeList = NULL;

void* my_malloc(size_t size) {
    Block* prev = NULL;
    Block* curr = freeList;

    while (curr != NULL) {
        if (curr->size >= size) {
            if (curr->size > size + sizeof(Block)) {
                Block* nextBlock = (Block*)((char*)curr + size);
                nextBlock->size = curr->size - size - sizeof(Block);
                nextBlock->next = curr->next;
                curr->size = size;
                curr->next = NULL;
            }
            if (prev == NULL) {
                freeList = curr->next;
            } else {
                prev->next = curr->next;
            }
            return (void*)(curr + 1);
        }
        prev = curr;
        curr = curr->next;
    }
    return NULL;
}

void my_free(void* ptr) {
    Block* block = (Block*)ptr - 1;
    block->next = freeList;
    freeList = block;
}

This basic linked list memory allocator simulates dynamic memory management. It finds the first eligible free block and returns memory to the free list. 

Performance Considerations and Limitations 

The linked list-based allocator simulates dynamic memory allocation well, but it has limitations too. Non-contiguous block allocation and freeing can trigger fragmentation. Small memory blocks may spread over the heap, causing wasteful memory consumption. 

As allocations rise, linked list traversal to discover free blocks slows. Buddy and slab allocators reduce fragmentation and expedite up allocation, boosting performance. 

Conclusion 

We used linked lists to mimic dynamic memory allocation in this blog. We learnt dynamic memory management by constructing a simple memory allocator, which is useful in systems programming. Custom allocators provide flexibility and control, but performance and memory utilization must be considered. Understanding memory management is useful when programming embedded systems or performance-critical applications.