In-Depth Exploration of C Language: Challenges from Code to Soul

The C language, as a cornerstone of programming, is renowned for its efficiency, flexibility, and close-to-the-metal characteristics. However, deeply learning C is not just about mastering syntax and basic usage; it involves understanding its underlying mechanisms, core philosophies, and how to use it to solve complex problems. Today, we will take a look at the kernel of C through a very challenging yet educational example.

Challenge: Implement a Mini Memory Allocator

Memory management is one of the core aspects of learning C. <span>malloc</span> and <span>free</span> are the protagonists of dynamic memory allocation, but have you ever thought about how to implement your own memory allocator without the standard library? Today, we will implement a mini memory manager from scratch, fully simulating the functionality of <span>malloc</span> and <span>free</span>.

Background of the Problem

A memory allocator needs to dynamically allocate and release memory in a contiguous block of memory. A common implementation method is to manage unallocated memory blocks through a free list. Each memory block needs to record two pieces of information:

1. Size Information
   
   : The size of the current memory block.
2. Pointer to the Next Free Block
   
   : To facilitate the maintenance of the free list.

When a user requests a block of memory, the allocator needs to find a sufficiently large free block and allocate it to the user; when the user releases memory, the allocator needs to return it to the free list and may merge it with adjacent free blocks to reduce fragmentation.

Code Implementation

The following is an implementation of a mini memory allocator based on a free list, which uses a static array to simulate heap space and implements <span>mymalloc</span> and <span>myfree</span>.

#include <stdio.h>
#include <stddef.h>

// Define heap size
#define HEAP_SIZE 1024

// Structure of memory block
typedef struct Block {
    size_t size;             // Size of current block
    struct Block *next;      // Pointer to next free block
} Block;

// Simulate heap space
static char heap[HEAP_SIZE];
static Block *free_list = NULL;

// Initialize memory allocator
void init_allocator() {
    free_list = (Block *)heap;
    free_list->size = HEAP_SIZE - sizeof(Block);
    free_list->next = NULL;
}

// Memory allocation function
void *mymalloc(size_t size) {
    if (size <= 0) {
        return NULL;
    }

    // Align to 8 bytes
    size = (size + 7) & ~7;

    Block *prev = NULL, *curr = free_list;

    // Traverse free list to find a sufficiently large block
    while (curr) {
        if (curr->size >= size + sizeof(Block)) {
            // If the current block is large enough, split it
            Block *allocated = (Block *)((char *)curr + sizeof(Block) + size);
            allocated->size = curr->size - size - sizeof(Block);
            allocated->next = curr->next;

            if (prev) {
                prev->next = allocated;
            } else {
                free_list = allocated;
            }

            curr->size = size;
            curr->next = NULL;

            return (void *)((char *)curr + sizeof(Block));
        }

        prev = curr;
        curr = curr->next;
    }

    // If there is not enough space, return NULL
    return NULL;
}

// Memory release function
void myfree(void *ptr) {
    if (!ptr) {
        return;
    }

    Block *block = (Block *)((char *)ptr - sizeof(Block));
    Block *curr = free_list;
    Block *prev = NULL;

    // Insert into free list in address order
    while (curr && curr < block) {
        prev = curr;
        curr = curr->next;
    }

    block->next = curr;

    if (prev) {
        prev->next = block;
    } else {
        free_list = block;
    }

    // Merge adjacent free blocks
    if (curr && (char *)block + block->size + sizeof(Block) == (char *)curr) {
        block->size += curr->size + sizeof(Block);
        block->next = curr->next;
    }

    if (prev && (char *)prev + prev->size + sizeof(Block) == (char *)block) {
        prev->size += block->size + sizeof(Block);
        prev->next = block->next;
    }
}

// Print current free list (for debugging)
void print_free_list() {
    Block *curr = free_list;
    printf("Free list:\n");
    while (curr) {
        printf("Block at %p: size = %zu\n", (void *)curr, curr->size);
        curr = curr->next;
    }
}

int main() {
    init_allocator();
    print_free_list();

    printf("\nAllocating 100 bytes...\n");
    void *p1 = mymalloc(100);
    print_free_list();

    printf("\nAllocating 200 bytes...\n");
    void *p2 = mymalloc(200);
    print_free_list();

    printf("\nFreeing the first block...\n");
    myfree(p1);
    print_free_list();

    printf("\nAllocating 50 bytes...\n");
    void *p3 = mymalloc(50);
    print_free_list();

    printf("\nFreeing the second block...\n");
    myfree(p2);
    print_free_list();

    printf("\nFreeing the third block...\n");
    myfree(p3);
    print_free_list();

    return 0;
}

Code Analysis

1. Alignment Operation
   
   : To improve memory access efficiency, we align the size of allocated memory blocks to 8-byte boundaries.
2. Free List Maintenance
   
   : Use a singly linked list structure to manage free memory blocks, updating the list during allocation and deallocation.
3. Splitting and Merging
   
   :

• Splitting: When a free block is larger than the requested size, it is divided into two parts: one part is allocated to the user, and the other part remains in the free list.
• Merging: When freeing memory, if adjacent free blocks can be merged, they are combined into a larger block.