Demystifying malloc: Build Your Own Memory Allocator in C

SegFault — Thu, 01 May 2025 19:30:29 +0000

Okay, let's dive into the world of memory management in C on Linux!

Introduction: Why Care About Memory Allocation?

Imagine your computer's memory (RAM) as a large plot of land. When your C program runs, it needs plots of land (memory) to store its data (variables, structures, etc.).

Stack: Think of this as a small, temporary storage shed on your land. It's used for function calls and local variables. It's very fast and managed automatically, but it's limited in size.
Heap: This is the main, large area of your land. When you need space that persists beyond a single function call, or when you need a large amount of space, you request it from the heap. This is dynamic memory allocation.

Standard C provides functions like malloc(), calloc(), realloc(), and free() to manage this heap land. These functions ask the operating system (OS) for memory and keep track of which parts are used and which are free.

In this tutorial, we'll build our own simple version of these functions. Why?

Learning: Understanding how they might work under the hood demystifies memory management.
Control: Sometimes, for specific applications, a custom allocator can be more efficient (though the standard ones are usually highly optimized).

We'll call our functions alt_malloc, alt_free, alt_calloc, and alt_realloc (for "alternative"). We'll primarily use two tools the Linux kernel gives us:

sbrk(): Imagine this command lets you push the boundary fence of your heap land further out, giving you a bit more contiguous space. It's relatively simple but less flexible.
mmap(): This is like asking the OS for a specific, separate plot of land (possibly quite large) anywhere it can find space. It's more flexible, especially for large requests.

Our allocator will use sbrk for smaller requests and mmap for larger ones, similar to how many real allocators work.

Let's Get Started!

Setup: Creating the Files

First, create three files in a directory:

alt_mem.h (The Header File - Our library's public interface)
alt_mem.c (The Source File - Where our implementation lives)
main.c (A Test File - To try out our functions)

File 1: alt_mem.h

// SPDX-License-Identifier: BSD-3-Clause

#pragma once // Ensures this header is included only once per compilation unit

#include <stddef.h> // Provides size_t type

// --- Function Prototypes ---
// These declare the functions we will implement in alt_mem.c

/*
 * Allocates 'size' bytes of uninitialized memory.
 * Returns: A pointer to the allocated memory, or NULL if the request fails.
 */
void *alt_malloc(size_t size);

/*
 * Frees the memory space pointed to by 'ptr', which must have been returned
 * by a previous call to alt_malloc(), alt_calloc() or alt_realloc().
 * If 'ptr' is NULL, no operation is performed.
 */
void alt_free(void *ptr);

/*
 * Allocates memory for an array of 'nmemb' elements of 'size' bytes each
 * and returns a pointer to the allocated memory. The memory is set to zero.
 * Returns: A pointer to the allocated memory, or NULL if the request fails.
 */
void *alt_calloc(size_t nmemb, size_t size);

/*
 * Changes the size of the memory block pointed to by 'ptr' to 'size' bytes.
 * The contents will be unchanged in the range from the start of the region
 * up to the minimum of the old and new sizes. If the new size is larger,
 * the added memory will not be initialized.
 * If 'ptr' is NULL, the call is equivalent to alt_malloc(size).
 * If 'size' is 0, the call is equivalent to alt_free(ptr).
 * Returns: A pointer to the newly allocated memory, or NULL if the request fails.
 */
void *alt_realloc(void *ptr, size_t size);

File 2: alt_mem.c (Initial Skeleton)

// SPDX-License-Identifier: BSD-3-Clause

#include "alt_mem.h" // Include our header

#include <stdio.h>      // For perror
#include <stdlib.h>     // For exit, EXIT_FAILURE
#include <unistd.h>     // For sbrk, sysconf, getpagesize
#include <sys/mman.h>   // For mmap, munmap
#include <string.h>     // For memset, memcpy

// --- Constants and Macros ---

// Alignment: Most CPUs access memory more efficiently if data starts at
// addresses that are multiples of 4 or 8. We'll align to 8 bytes.
// This macro takes a size 'x' and rounds it UP to the nearest multiple of 8.
// Example: ALIGN8(3) -> 8, ALIGN8(8) -> 8, ALIGN8(10) -> 16
#define ALIGN8(x) (((x) + 7) & (~7))

// Threshold for using mmap instead of sbrk. Allocations larger than or
// equal to this size will use mmap. 128 KiB is a common threshold.
#define MMAP_THRESHOLD (128 * 1024)

// --- Error Handling Helper ---
// A simple macro to check for errors and exit if something critical fails.
#define DIE(assertion, call_description)                                \
    do {                                                                \
        if (assertion) {                                                \
            perror(call_description);                                   \
            exit(EXIT_FAILURE);                                         \
        }                                                               \
    } while (0)


// --- Function Implementations (Stubs for now) ---

void *alt_malloc(size_t size) {
    // TODO: Implement this
    (void)size; // Prevent unused variable warning for now
    fprintf(stderr, "alt_malloc not implemented yet!\n");
    return NULL;
}

void alt_free(void *ptr) {
    // TODO: Implement this
    (void)ptr; // Prevent unused variable warning
    fprintf(stderr, "alt_free not implemented yet!\n");
}

void *alt_calloc(size_t nmemb, size_t size) {
    // TODO: Implement this
    (void)nmemb; (void)size; // Prevent unused variable warnings
    fprintf(stderr, "alt_calloc not implemented yet!\n");
    return NULL;
}

void *alt_realloc(void *ptr, size_t size) {
    // TODO: Implement this
    (void)ptr; (void)size; // Prevent unused variable warnings
    fprintf(stderr, "alt_realloc not implemented yet!\n");
    return NULL;
}

File 3: main.c (Initial Test)

#include <stdio.h>
#include "alt_mem.h" // Include our allocator's header

int main(void) {
    printf("Starting memory allocator test...\n");

    // Try to allocate some memory (it will fail for now)
    void *p1 = alt_malloc(100);
    if (p1 == NULL) {
        printf("Allocation 1 failed (as expected initially).\n");
    }

    // Try to free (it will do nothing useful yet)
    alt_free(p1);
    printf("Called free (did nothing yet).\n");


    printf("Memory allocator test finished.\n");
    return 0;
}

Compilation and Testing (Step 0)

Open your Linux terminal, navigate to the directory where you saved the files, and compile:

gcc alt_mem.c main.c -o allocator_test

gcc: The C compiler.
alt_mem.c main.c: The source files to compile.
-o allocator_test: Specifies the name of the output executable file.

Now run it:

./allocator_test

You should see output indicating that the functions aren't implemented yet. This confirms our basic setup is working!

Step 1: Keeping Track - The Metadata Block

When we allocate memory, we need to store some information about that memory chunk: how big is it? Is it currently in use or free? Where is the next chunk?

We'll store this information in a small structure just before the memory we give to the user.

Think of it like a tag on a piece of luggage. The luggage (user memory) is what the user cares about, but the tag (metadata) tells the baggage handlers (our allocator) where it's going and how big it is.

Let's define this structure and its possible states inside alt_mem.c, near the top:

// Add these includes if they aren't already there
#include <stdbool.h> // For bool type (optional, could use int)

// --- Data Structures ---

// Possible states for a memory block
typedef enum {
    STATUS_FREE,    // Block is free and available for allocation
    STATUS_ALLOC,   // Block is currently allocated (used by sbrk)
    STATUS_MAPPED   // Block was allocated using mmap
} block_status;

// Metadata structure prepended to each memory block
typedef struct block_meta {
    size_t size;             // Size of the *user* data area (payload), doesn't include sizeof(struct block_meta)
    block_status status;     // Current status of the block (FREE, ALLOC, MAPPED)
    struct block_meta *next; // Pointer to the next block_meta in the list
    struct block_meta *prev; // Pointer to the previous block_meta in the list
} block_meta_t;

// --- Global Variables ---

// Head of the linked list of memory blocks. Initially NULL.
static block_meta_t *head = NULL;

// Flag to track if we've done the initial large allocation (optimization)
static bool preallocated = false;

size: Stores the size of the usable memory region following the metadata.
status: Tells us if the block is free, allocated via sbrk, or allocated via mmap.
next/prev: These pointers link all our blocks together, forming a doubly linked list. This lets us navigate through our managed memory.
head: A global pointer that always points to the first block in our list. If head is NULL, we haven't allocated anything yet.
preallocated: A flag we'll use later for an optimization.

Step 2: Basic Allocation (alt_malloc with sbrk)

Let's implement a very simple alt_malloc. For now, it will always ask the OS for new memory using sbrk, ignoring any potentially free blocks we might have later.

Replace the stub alt_malloc in alt_mem.c with this:

// Helper function to request memory from the OS using sbrk
// Returns a pointer to the new block's metadata, or NULL on failure
static block_meta_t *request_space(size_t size, block_meta_t *last_entry) {
    // Request enough space for the metadata block PLUS the requested user size
    block_meta_t *block = sbrk(sizeof(block_meta_t) + size);
    if (block == (void *)-1) { // sbrk returns (void*)-1 on error
        perror("sbrk failed");
        return NULL; // Indicate failure
    }

    // Initialize the metadata for this new block
    block->size = size;
    block->status = STATUS_ALLOC; // Mark as allocated
    block->next = NULL;          // This is the new last block
    block->prev = last_entry;    // Link to the previous block

    // Update the previous block's 'next' pointer if it exists
    if (last_entry) {
        last_entry->next = block;
    } else {
        // If there was no previous block, this is the new head of the list
        head = block;
    }

    return block;
}

// Helper function to find the last block in our linked list
// Needed to link a new sbrk block at the end
static block_meta_t *find_last_entry(void) {
    block_meta_t *current = head;
    if (!current) {
        return NULL; // List is empty
    }
    // Traverse the list until we find the block whose 'next' is NULL
    while (current->next) {
        current = current->next;
    }
    return current;
}


void *alt_malloc(size_t size) {
    // 1. Handle invalid size
    if (size == 0) {
        return NULL;
    }

    // 2. Align the requested size to 8 bytes
    size = ALIGN8(size);

    // 3. Find the last block in our list to link the new one after it
    block_meta_t *last_entry = find_last_entry();

    // 4. Request new space using sbrk
    //    (For now, we always request new space)
    block_meta_t *new_block = request_space(size, last_entry);
    if (!new_block) {
        return NULL; // sbrk failed
    }

    // 5. Return the pointer to the user data area
    //    This is right *after* our metadata block
    return (void *)(new_block + 1); // Pointer arithmetic: moves pointer by sizeof(block_meta_t)
}

We added find_last_entry() to walk our linked list and find where to append the new block.
We added request_space() to contain the sbrk call and metadata initialization.
alt_malloc now:
- Checks for size == 0.
- Aligns the size.
- Finds the end of the list.
- Calls request_space to get memory from the OS and set up the metadata.
- Returns a pointer to the memory after the metadata (new_block + 1).

Compilation and Testing (Step 2)

Modify main.c to allocate and maybe write some data:

#include <stdio.h>
#include <string.h> // For strcpy
#include "alt_mem.hh"

int main(void) {
    printf("Starting memory allocator test...\n");

    printf("Attempting allocation 1 (100 bytes)...\n");
    char *p1 = alt_malloc(100);
    if (p1) {
        printf(" -> Allocation 1 successful! Address: %p\n", p1);
        // Try writing to the allocated memory
        strcpy(p1, "Hello");
        printf(" -> Wrote 'Hello' to p1.\n");
        // Access the string through the pointer
        printf(" -> p1 contains: %s\n", p1);
    } else {
        printf(" -> Allocation 1 failed.\n");
    }

    printf("\nAttempting allocation 2 (50 bytes)...\n");
    int *p2 = alt_malloc(50); // Allocate space for about 12 ints
     if (p2) {
        printf(" -> Allocation 2 successful! Address: %p\n", p2);
        // Try writing some integers
        for (int i = 0; i < 10; ++i) {
            p2[i] = i * 10;
        }
        printf(" -> Wrote 10 integers to p2.\n");
         printf(" -> p2[5] contains: %d\n", p2[5]);
    } else {
        printf(" -> Allocation 2 failed.\n");
    }

    // We still can't free memory properly yet!
    // alt_free(p1);
    // alt_free(p2);

    printf("\nMemory allocator test finished.\n");
    return 0;
}

Compile and run again:

gcc alt_mem.c main.c -o allocator_test
./allocator_test

You should see successful allocations and the addresses printed! We're managing memory (but leaking it badly since alt_free does nothing).

Step 3: Basic Freeing (alt_free)

Now, let's implement alt_free. The simplest thing it can do is find the metadata block associated with the user pointer and mark it as STATUS_FREE.

Add this function to alt_mem.c:

// Helper function to get the metadata block from a user pointer
// Returns NULL if ptr is invalid (though we don't validate fully here)
static block_meta_t *get_block_ptr(void *ptr) {
    if (!ptr) {
        return NULL;
    }
    // The metadata block is located just BEFORE the user pointer
    return (block_meta_t *)ptr - 1;
}

void alt_free(void *ptr) {
    // 1. Handle NULL pointer
    if (ptr == NULL) {
        return; // Do nothing if ptr is NULL
    }

    // 2. Get the pointer to the metadata block
    block_meta_t *block = get_block_ptr(ptr);

    // 3. Mark the block as free
    //    (We'll add coalescing and mmap handling later)
    if (block->status == STATUS_ALLOC) { // Only free sbrk-allocated blocks this way for now
         block->status = STATUS_FREE;
         printf("DEBUG: Marked block at %p (user ptr %p) as FREE\n", (void*)block, ptr);
    } else if (block->status == STATUS_MAPPED) {
        // TODO: Handle freeing mmap-ed blocks later
        printf("DEBUG: Freeing MAPPED blocks not implemented yet.\n");
    } else if (block->status == STATUS_FREE) {
        // Optional: Warn about double free?
        printf("DEBUG: Warning - block at %p (user ptr %p) already FREE.\n", (void*)block, ptr);
    }

    // TODO: Add coalescing (merging free blocks) later
    // TODO: Add returning memory to OS (munmap/sbrk reduction) later
}

We added get_block_ptr() to easily find the metadata header from the user's data pointer.
alt_free now finds the block and sets its status to STATUS_FREE. It doesn't yet reuse this memory or give it back to the OS.

Compilation and Testing (Step 3)

Uncomment the alt_free calls in main.c:

#include <stdio.h>
#include <string.h> // For strcpy
#include "alt_mem.h"

int main(void) {
    printf("Starting memory allocator test...\n");

    printf("Attempting allocation 1 (100 bytes)...\n");
    char *p1 = alt_malloc(100);
    if (p1) { /* ... */ } else { /* ... */ }

    printf("\nAttempting allocation 2 (50 bytes)...\n");
    int *p2 = alt_malloc(50);
    if (p2) { /* ... */ } else { /* ... */ }

    printf("\nFreeing allocation 1...\n");
    alt_free(p1); // Now this will mark the block

    printf("Freeing allocation 2...\n");
    alt_free(p2); // And this one

    // What happens if we allocate again?
    // Currently, it will still ask sbrk for MORE memory,
    // ignoring the blocks we just freed.
    printf("\nAttempting allocation 3 (20 bytes) after freeing...\n");
    void *p3 = alt_malloc(20);
     if (p3) {
        printf(" -> Allocation 3 successful! Address: %p\n", p3);
        alt_free(p3); // Free it immediately for this test
    } else {
        printf(" -> Allocation 3 failed.\n");
    }


    printf("\nMemory allocator test finished.\n");
    return 0;
}

Compile and run:

gcc alt_mem.c main.c -o allocator_test
./allocator_test

You'll see the DEBUG messages showing blocks being marked as FREE. However, notice that allocation 3 likely gets a new, higher memory address. Our allocator isn't smart enough to reuse the space from p1 or p2 yet.

Step 4: Reusing Memory - The Best-Fit Strategy

To reuse freed memory, alt_malloc needs to:

Scan the linked list of blocks.
Look for a block with status == STATUS_FREE.
Check if that free block is large enough (block->size >= requested_size).
Among all suitable free blocks, choose the best one. "Best-fit" means choosing the smallest free block that is still large enough. This tries to leave larger free blocks available for future large requests.
If a suitable free block is found, mark it as STATUS_ALLOC and return it.
If no suitable free block is found, then resort to sbrk to get new memory.

Let's implement the search function:

// --- Helper Functions (Add this function) ---

// Find the best-fit free block for a given size
// Returns the best block found, or NULL if no suitable block exists
static block_meta_t *find_best_fit(size_t size) {
    block_meta_t *current = head;
    block_meta_t *best_fit = NULL;

    while (current) {
        // Check if the block is free and large enough
        if (current->status == STATUS_FREE && current->size >= size) {
            // Is it the first suitable block found, or smaller than the current best?
            if (best_fit == NULL || current->size < best_fit->size) {
                best_fit = current;
                // Optimization: If we found a perfect fit, we can stop searching
                if (best_fit->size == size) {
                    break;
                }
            }
        }
        current = current->next; // Move to the next block
    }
    return best_fit;
}

Now, modify alt_malloc to use find_best_fit:

void *alt_malloc(size_t size) {
    // 1. Handle invalid size
    if (size == 0) {
        return NULL;
    }

    // 2. Align the requested size
    size = ALIGN8(size);

    // 3. Search for a suitable free block (Best-Fit)
    block_meta_t *best_block = find_best_fit(size);

    if (best_block) {
        // --- Block Found! ---
        printf("DEBUG: Found suitable free block at %p (size %zu) for request %zu\n",
               (void*)best_block, best_block->size, size);

        // TODO: Implement block splitting later if best_block->size > size

        best_block->status = STATUS_ALLOC; // Mark it as allocated
        return (void *)(best_block + 1);   // Return user pointer
    } else {
        // --- No Suitable Block Found ---
        printf("DEBUG: No suitable free block found. Requesting new space via sbrk.\n");

        // 4. Find the last block to link after
        block_meta_t *last_entry = find_last_entry();

        // 5. Request new space using sbrk
        block_meta_t *new_block = request_space(size, last_entry);
        if (!new_block) {
            return NULL; // sbrk failed
        }

        // 6. Return the pointer to the user data area
        return (void *)(new_block + 1);
    }
}

Compilation and Testing (Step 4)

Use the same main.c from Step 3.

Compile and run:

gcc alt_mem.c main.c -o allocator_test
./allocator_test

Now, look closely at the output for Allocation 3! It should print the "DEBUG: Found suitable free block..." message and the address of p3 should match the address previously used by either p1 or p2 (specifically, it should match p1's address if p1 was 100 bytes and p3 requested 20, as 100 is the "best fit" for 20 among 100 and 50). We are reusing memory!

Step 5: Block Splitting

We have a problem. If we find a 1000-byte free block and only need 50 bytes, our current code marks the entire 1000-byte block as allocated. That wastes 950 bytes!

We need to split the block. If the chosen free block (best_block) is significantly larger than the requested size, we can carve out the size needed, mark that part allocated, and leave the remainder as a new, smaller free block.

When can we split? We need enough leftover space to hold at least a block_meta_t structure plus a minimum usable payload (let's say 8 bytes, our alignment).

Modify the if (best_block) section within alt_malloc:

    if (best_block) {
        // --- Block Found! ---
        printf("DEBUG: Found suitable free block at %p (size %zu) for request %zu\n",
               (void*)best_block, best_block->size, size);

        // Calculate remaining size after allocation
        size_t remaining_size = best_block->size - size;

        // Check if we can split the block
        // Need enough space for a new metadata block + minimum payload (e.g., 8 bytes)
        if (remaining_size >= sizeof(block_meta_t) + ALIGN8(1)) {
             printf("DEBUG: Splitting block. Remaining size: %zu\n", remaining_size - sizeof(block_meta_t));

            // 1. Create the new free block's metadata *after* the allocated portion
            block_meta_t *new_free_block = (block_meta_t *)((char *)(best_block + 1) + size);
            new_free_block->size = remaining_size - sizeof(block_meta_t);
            new_free_block->status = STATUS_FREE;

            // 2. Link the new free block into the list
            new_free_block->next = best_block->next;
            new_free_block->prev = best_block;

            // 3. Update links of surrounding blocks
            if (best_block->next) {
                best_block->next->prev = new_free_block;
            }
            best_block->next = new_free_block;

            // 4. Update the size of the original (now allocated) block
            best_block->size = size;

        } else {
            // Not enough space to split, allocate the whole block
             printf("DEBUG: Not enough space to split block. Allocating entire block (%zu bytes).\n", best_block->size);
        }

        best_block->status = STATUS_ALLOC; // Mark the (potentially smaller) block as allocated
        return (void *)(best_block + 1);   // Return user pointer
    } else {
        // --- No Suitable Block Found ---
        // ... (sbrk part remains the same) ...
    }

We calculate remaining_size.
We check if remaining_size is enough to hold sizeof(block_meta_t) plus a minimum aligned block size (e.g., ALIGN8(1) which is 8).
If splittable:
- Calculate the address of the new metadata header (new_free_block). It's located sizeof(block_meta_t) bytes before the end of the original user data area, or (char*)(best_block + 1) + size.
- Initialize the new_free_block metadata (size, status).
- Link new_free_block into the list between best_block and best_block->next.
- Update best_block->size to the requested size.
If not splittable, we just use the whole best_block as before.

Compilation and Testing (Step 5)

Let's refine main.c to test splitting better:

#include <stdio.h>
#include <string.h>
#include "alt_mem.h"

int main(void) {
    printf("Starting memory allocator test...\n");

    printf("\n[Test 1: Basic Allocation]\n");
    void *p1 = alt_malloc(200); // Allocate a larger block
    printf("p1 (%p) allocated 200 bytes.\n", p1);
    void *p2 = alt_malloc(50);
    printf("p2 (%p) allocated 50 bytes.\n", p2);

    printf("\n[Test 2: Freeing and Splitting]\n");
    printf("Freeing p1 (%p)...\n", p1);
    alt_free(p1); // Free the 200-byte block

    printf("Allocating p3 (80 bytes)...\n");
    void *p3 = alt_malloc(80); // Should reuse and split the block from p1
    printf("p3 (%p) allocated 80 bytes. Should be same base address as p1.\n", p3);

    printf("\n[Test 3: Using the Remainder]\n");
    printf("Allocating p4 (100 bytes)...\n");
    // The remainder from splitting p1 should be 200 - 80 - sizeof(meta)
    // Let's assume sizeof(meta) is 24 (typical for 64-bit with size_t, enum, 2 pointers)
    // Remainder payload = 200 - 80 - 24 = 96.
    // So, a request for 100 should *not* fit in the remainder, it should use sbrk.
    // Let's request something smaller, like 60.
    void *p4 = alt_malloc(60);
    printf("p4 (%p) allocated 60 bytes. Should reuse the remainder of p1's block.\n", p4);


    printf("\n[Test 4: Clean up]\n");
    alt_free(p2);
    alt_free(p3);
    alt_free(p4);
    printf("Freed p2, p3, p4.\n");


    printf("\nMemory allocator test finished.\n");
    return 0;
}

Compile and run:

gcc alt_mem.c main.c -o allocator_test
./allocator_test

Observe the output carefully. You should see:

p1 and p2 allocated at different addresses.
p1 freed.
p3 allocated at the same base address as p1. You should see the "DEBUG: Splitting block" message.
p4 allocated at an address after p3's data but within the original bounds of p1's block (if sizeof(block_meta_t) allows). You should see "DEBUG: Found suitable free block..." for the remainder.

Step 6: Merging Free Blocks (Coalescing)

Now consider this: you allocate block A, then block B. You free A, then you free B. You now have two adjacent free blocks in memory. If a large allocation request comes in that's bigger than A or B alone, but smaller than A + B combined, we can't satisfy it!

We need coalescing: when freeing a block, check if its immediate neighbors (previous or next in memory, not just in the list order) are also free. If they are, merge them into one larger free block.

How do we know if they are physically adjacent?

block->next is adjacent if (char *)block + sizeof(block_meta_t) + block->size == (char *)block->next.
block->prev is adjacent if (char *)block->prev + sizeof(block_meta_t) + block->prev->size == (char *)block.

Let's implement the join_free_blocks function:

// --- Helper Functions (Add this function) ---

// Coalesce adjacent free blocks starting from 'block'
// Merges with next block(s) if free and adjacent.
// Merges with previous block(s) if free and adjacent.
static void join_free_blocks(block_meta_t *block) {
    printf("DEBUG: Attempting to coalesce around block %p (size %zu)\n", (void*)block, block->size);

    // 1. Coalesce with the NEXT block (if possible)
    if (block->next && block->next->status == STATUS_FREE) {
        // Check for physical adjacency
        if ((char *)block + sizeof(block_meta_t) + block->size == (char *)block->next) {
            printf("DEBUG: Coalescing block %p with next block %p\n", (void*)block, (void*)block->next);
            // Increase current block size
            block->size += sizeof(block_meta_t) + block->next->size;
            // Bypass the merged block in the list
            block->next = block->next->next;
            if (block->next) {
                block->next->prev = block;
            }
        } else {
             printf("DEBUG: Next block %p is FREE but not adjacent.\n", (void*)block->next);
        }
    }

    // 2. Coalesce with the PREVIOUS block (if possible)
    //    Note: If we merged with the next block above, 'block' itself is still the
    //    correct starting point for checking the previous block.
    if (block->prev && block->prev->status == STATUS_FREE) {
        // Check for physical adjacency
        if ((char *)block->prev + sizeof(block_meta_t) + block->prev->size == (char *)block) {
             printf("DEBUG: Coalescing block %p with previous block %p\n", (void*)block, (void*)block->prev);
            // Increase previous block's size
            block->prev->size += sizeof(block_meta_t) + block->size;
            // Bypass the current block ('block') in the list
            block->prev->next = block->next;
            if (block->next) {
                block->next->prev = block->prev;
            }
            // Important: After merging with previous, the 'block' pointer is now
            // invalid in the sense that the 'previous' block is the one we should
            // consider as the result of the merge. However, since we're just
            // finishing the free operation, we don't need to update the caller's
            // 'block' variable. The list structure is now correct.
            // block = block->prev; // Conceptually, but not needed here.
        } else {
             printf("DEBUG: Previous block %p is FREE but not adjacent.\n", (void*)block->prev);
        }
    }
     printf("DEBUG: Coalescing finished.\n");
}

Now, call this function at the end of alt_free (only for sbrk-allocated blocks for now):

void alt_free(void *ptr) {
    if (ptr == NULL) {
        return;
    }

    block_meta_t *block = get_block_ptr(ptr);

    if (block->status == STATUS_ALLOC) {
        block->status = STATUS_FREE;
        printf("DEBUG: Marked block at %p (user ptr %p) as FREE\n", (void*)block, ptr);
        // *** Call coalesce here ***
        join_free_blocks(block);
    } else if (block->status == STATUS_MAPPED) {
        // TODO: Handle freeing mmap-ed blocks later
        printf("DEBUG: Freeing MAPPED blocks not implemented yet.\n");
    } else if (block->status == STATUS_FREE) {
        printf("DEBUG: Warning - block at %p (user ptr %p) already FREE.\n", (void*)block, ptr);
    }
}

Compilation and Testing (Step 6)

Modify main.c to test coalescing:

#include <stdio.h>
#include <string.h>
#include "alt_mem.h"

int main(void) {
    printf("Starting memory allocator test...\n");

    printf("\n[Test 1: Allocate Three Adjacent Blocks]\n");
    char *a = alt_malloc(100); printf("a (%p) alloc 100\n", a);
    char *b = alt_malloc(120); printf("b (%p) alloc 120\n", b);
    char *c = alt_malloc(150); printf("c (%p) alloc 150\n", c);

    printf("\n[Test 2: Free Middle Block - No Coalesce]\n");
    printf("Freeing b (%p)...\n", b);
    alt_free(b); // Should just mark b as free

    printf("\n[Test 3: Free First Block - Coalesce Forward]\n");
    printf("Freeing a (%p)...\n", a);
    alt_free(a); // Should mark a free, then merge a and b

    printf("\n[Test 4: Allocate to Test Forward Coalesce]\n");
    // Original sizes: a=100, b=120. Meta size ~24.
    // Merged free block should be around 100 + 120 + 24 = 244 bytes.
    printf("Allocating d (220 bytes)...\n");
    char *d = alt_malloc(220); // Should fit in the merged a+b block and split
    printf("d (%p) alloc 220. Should reuse merged a+b block.\n", d);
    alt_free(d); // Free it for next test

    printf("\n[Test 5: Free Last Block - Coalesce Backward]\n");
    // State: Merged a+b (free), c (alloc)
    printf("Freeing c (%p)...\n", c);
    alt_free(c); // Should mark c free, then merge (a+b) with c.

    printf("\n[Test 6: Allocate to Test Full Coalesce]\n");
    // Merged block should be ~ 100 + 120 + 150 + 2*meta = 370 + 48 = 418
    printf("Allocating e (400 bytes)...\n");
    char *e = alt_malloc(400); // Should fit in the fully merged block
    printf("e (%p) alloc 400. Should reuse fully merged block.\n", e);

    printf("\n[Test 7: Clean up]\n");
    alt_free(e);
    printf("Freed e.\n");

    printf("\nMemory allocator test finished.\n");
    return 0;
}

Compile and run:

gcc alt_mem.c main.c -o allocator_test
./allocator_test

Follow the DEBUG messages. You should see:

Freeing b doesn't coalesce.
Freeing a coalesces with b (forward).
Allocating d reuses the merged a+b block.
Freeing c coalesces with the merged a+b block (backward).
Allocating e reuses the fully merged a+b+c block.

Step 7: Handling Large Allocations (mmap)

sbrk is simple but can lead to fragmentation and isn't ideal for very large allocations. mmap is better suited for this. We'll use mmap for requests >= MMAP_THRESHOLD.

mmap-allocated blocks are managed separately; they don't participate in sbrk heap expansion or coalescing with sbrk-allocated blocks. They are still part of our linked list for tracking purposes.

First, add a helper function to perform the mmap allocation:

// --- Helper Functions (Add this function) ---

// Map memory using mmap for large allocations
// Returns pointer to user data area, or NULL on failure
static void *map_memory(size_t size, block_meta_t *last_entry) {
    // Request size + metadata space.
    // MAP_ANONYMOUS: Memory not backed by a file, initialized to zero.
    // MAP_PRIVATE: Modifications are private to this process.
    block_meta_t *block = mmap(NULL, // Let kernel choose address
                             sizeof(block_meta_t) + size,
                             PROT_READ | PROT_WRITE, // Permissions
                             MAP_PRIVATE | MAP_ANONYMOUS,
                             -1, // File descriptor (none for anonymous)
                             0); // Offset (0 for anonymous)

    DIE(block == MAP_FAILED, "mmap failed"); // Check for error

    // Initialize metadata
    block->size = size;
    block->status = STATUS_MAPPED; // Mark as mmap-ed
    block->next = NULL;
    block->prev = last_entry;

    // Link into the list
    if (last_entry) {
        last_entry->next = block;
    } else {
        head = block; // First block overall
    }
    printf("DEBUG: Mapped new block at %p (size %zu) for request %zu\n",
           (void*)block, size, size);

    // Return pointer to user data area
    return (void *)(block + 1);
}

Now, modify alt_malloc to check the threshold:

void *alt_malloc(size_t size) {
    // 1. Handle invalid size
    if (size == 0) {
        return NULL;
    }

    // 2. Align the requested size
    size = ALIGN8(size);

    // 3. *** Check for large allocation ***
    if (size >= MMAP_THRESHOLD) {
        printf("DEBUG: Request size %zu >= threshold %d. Using mmap.\n", size, MMAP_THRESHOLD);
        block_meta_t *last_entry = find_last_entry(); // Still need last entry to link
        return map_memory(size, last_entry);
    }

    // --- If size < MMAP_THRESHOLD, proceed with sbrk logic ---

    // 4. Search for a suitable free block (Best-Fit)
    block_meta_t *best_block = find_best_fit(size); // find_best_fit ignores MAPPED blocks

    if (best_block) {
        // ... (Block splitting logic remains the same) ...
        printf("DEBUG: Found suitable free block at %p (size %zu) for request %zu\n",
               (void*)best_block, best_block->size, size);

        size_t remaining_size = best_block->size - size;
        if (remaining_size >= sizeof(block_meta_t) + ALIGN8(1)) {
             printf("DEBUG: Splitting block...\n");
             // ... (split logic) ...
        } else {
             printf("DEBUG: Not enough space to split...\n");
        }
        best_block->status = STATUS_ALLOC;
        return (void *)(best_block + 1);

    } else {
        // --- No Suitable sbrk Block Found ---
        printf("DEBUG: No suitable free block found. Requesting new space via sbrk.\n");
        block_meta_t *last_entry = find_last_entry();
        block_meta_t *new_block = request_space(size, last_entry); // request_space uses sbrk
        if (!new_block) return NULL;
        return (void *)(new_block + 1);
    }
}

Note: Our existing find_best_fit function already correctly ignores STATUS_MAPPED blocks because it explicitly checks for current->status == STATUS_FREE. Our join_free_blocks also correctly ignores STATUS_MAPPED blocks when checking neighbors because it checks block->next->status == STATUS_FREE and block->prev->status == STATUS_FREE.

Step 8: Freeing mmap-ed Memory (munmap)

Freeing mmap-ed memory is different: we use munmap() to return it directly to the OS. We also need to remove its metadata block from our linked list.

Modify alt_free:

void alt_free(void *ptr) {
    if (ptr == NULL) {
        return;
    }

    block_meta_t *block = get_block_ptr(ptr);

    if (block->status == STATUS_ALLOC) {
        // --- Freeing sbrk block ---
        block->status = STATUS_FREE;
        printf("DEBUG: Marked sbrk block at %p (user ptr %p, size %zu) as FREE\n",
               (void*)block, ptr, block->size);
        join_free_blocks(block); // Coalesce sbrk blocks

    } else if (block->status == STATUS_MAPPED) {
        // --- Freeing mmap block ---
         printf("DEBUG: Freeing MAPPED block at %p (user ptr %p, size %zu) using munmap\n",
               (void*)block, ptr, block->size);

        // 1. Unlink the block from the list
        if (block->prev) {
            block->prev->next = block->next;
        } else {
            // Block was the head of the list
            head = block->next;
        }
        if (block->next) {
            block->next->prev = block->prev;
        }

        // 2. Release memory back to the OS
        // We need to unmap the metadata AND the user data area
        size_t total_size = sizeof(block_meta_t) + block->size;
        int ret = munmap(block, total_size);
        DIE(ret == -1, "munmap failed");

    } else if (block->status == STATUS_FREE) {
        printf("DEBUG: Warning - block at %p (user ptr %p) already FREE.\n", (void*)block, ptr);
    }
}

Compilation and Testing (Steps 7 & 8)

Update main.c to test large allocations:

#include <stdio.h>
#include <string.h>
#include "alt_mem.h"

#define LARGE_ALLOC_SIZE (200 * 1024) // Larger than MMAP_THRESHOLD

int main(void) {
    printf("Starting memory allocator test...\n");

    printf("\n[Test 1: Small Allocations (sbrk)]\n");
    void *s1 = alt_malloc(100); printf("s1 (%p) alloc 100\n", s1);
    void *s2 = alt_malloc(200); printf("s2 (%p) alloc 200\n", s2);

    printf("\n[Test 2: Large Allocation (mmap)]\n");
    void *m1 = alt_malloc(LARGE_ALLOC_SIZE);
    printf("m1 (%p) alloc %d (large)\n", m1, LARGE_ALLOC_SIZE);

    printf("\n[Test 3: Another Small Allocation (sbrk)]\n");
    // Should still use sbrk, potentially reusing if s1/s2 freed, or extending heap
    void *s3 = alt_malloc(150); printf("s3 (%p) alloc 150\n", s3);

    printf("\n[Test 4: Freeing Large Allocation]\n");
    printf("Freeing m1 (%p)...\n", m1);
    alt_free(m1); // Should trigger munmap

    printf("\n[Test 5: Freeing Small Allocations]\n");
    printf("Freeing s1 (%p)...\n", s1); alt_free(s1);
    printf("Freeing s2 (%p)...\n", s2); alt_free(s2); // Should coalesce with s1 if adjacent
    printf("Freeing s3 (%p)...\n", s3); alt_free(s3); // Should coalesce if adjacent

    printf("\n[Test 6: Large Allocation Again]\n");
    // Should use mmap again, likely at a different address than before
    void *m2 = alt_malloc(LARGE_ALLOC_SIZE);
    printf("m2 (%p) alloc %d (large)\n", m2, LARGE_ALLOC_SIZE);
    alt_free(m2);


    printf("\nMemory allocator test finished.\n");
    return 0;
}

Compile and run:

gcc alt_mem.c main.c -o allocator_test
./allocator_test

Observe the DEBUG output. You should see:

Small allocations using sbrk.
The large allocation triggering the mmap message.
Another small allocation using sbrk.
Freeing the large allocation triggering the munmap message.
Freeing small allocations potentially triggering coalescing.
The second large allocation using mmap again.

Step 9: Implementing alt_calloc

calloc(nmemb, size) is like malloc(nmemb * size) but initializes the memory to zero.

If we use mmap (because the total size is large), MAP_ANONYMOUS already zeroes the memory for us!
If we use sbrk (by finding a free block or extending the heap), we must manually zero the memory using memset.

Let's implement alt_calloc:

void *alt_calloc(size_t nmemb, size_t size) {
    // 1. Calculate total size and check for overflow / zero request
    size_t total_size = nmemb * size;
    if (nmemb == 0 || size == 0 || total_size / nmemb != size) { // Check for overflow
        return NULL;
    }

    // 2. Align the total size
    total_size = ALIGN8(total_size);

    // 3. Decide between mmap and sbrk based on threshold
    void *ptr = NULL;
    if (total_size >= MMAP_THRESHOLD) {
        printf("DEBUG calloc: Request size %zu >= threshold. Using mmap.\n", total_size);
        block_meta_t *last_entry = find_last_entry();
        ptr = map_memory(total_size, last_entry);
        // mmap anonymous memory is already zeroed by the kernel
        if (!ptr) return NULL; // map_memory failed

    } else {
        printf("DEBUG calloc: Request size %zu < threshold. Using sbrk logic.\n", total_size);
        // Use the same logic as alt_malloc for finding/allocating sbrk blocks
        block_meta_t *block = find_best_fit(total_size);
        if (block) {
            // Found a free block
            printf("DEBUG calloc: Found suitable free block at %p\n", (void*)block);
             // Split if necessary (same logic as malloc)
            size_t remaining_size = block->size - total_size;
             if (remaining_size >= sizeof(block_meta_t) + ALIGN8(1)) {
                printf("DEBUG calloc: Splitting block.\n");
                block_meta_t *new_free_block = (block_meta_t *)((char *)(block + 1) + total_size);
                new_free_block->size = remaining_size - sizeof(block_meta_t);
                new_free_block->status = STATUS_FREE;
                new_free_block->next = block->next;
                new_free_block->prev = block;
                if (block->next) block->next->prev = new_free_block;
                block->next = new_free_block;
                block->size = total_size;
            } else {
                 printf("DEBUG calloc: Not splitting block.\n");
            }
            block->status = STATUS_ALLOC;
            ptr = (void *)(block + 1);

        } else {
            // No free block, request new space
             printf("DEBUG calloc: No suitable free block. Requesting new space via sbrk.\n");
            block_meta_t *last_entry = find_last_entry();
            block = request_space(total_size, last_entry);
            if (!block) return NULL; // sbrk failed
            ptr = (void *)(block + 1);
        }

        // *** Zero the memory for sbrk allocations ***
        if (ptr) {
             printf("DEBUG calloc: Zeroing %zu bytes for sbrk allocation at %p\n", total_size, ptr);
            memset(ptr, 0, total_size);
        }
    }

    return ptr;
}

Compilation and Testing (Step 9)

Add calloc tests to main.c:

#include <stdio.h>
#include <string.h>
#include <stdlib.h> // For exit
#include "alt_mem.h"

#define LARGE_ALLOC_SIZE (200 * 1024)

// Helper to check if memory is zeroed
void check_zero(void *ptr, size_t size) {
    unsigned char *byte_ptr = (unsigned char *)ptr;
    for (size_t i = 0; i < size; ++i) {
        if (byte_ptr[i] != 0) {
            fprintf(stderr, "Error: Memory not zeroed at byte %zu!\n", i);
            exit(EXIT_FAILURE); // Abort test
        }
    }
     printf(" -> Memory check: OK (all bytes zero)\n");
}


int main(void) {
    printf("Starting memory allocator test...\n");

    printf("\n[Test 1: calloc Small (sbrk)]\n");
    int *c1 = alt_calloc(10, sizeof(int)); // 40 bytes aligned to 40
    printf("c1 (%p) calloc 10 ints\n", c1);
    if(c1) check_zero(c1, 10 * sizeof(int));
    alt_free(c1);

    printf("\n[Test 2: calloc Large (mmap)]\n");
    long *c2 = alt_calloc(50000, sizeof(long)); // > MMAP_THRESHOLD
    printf("c2 (%p) calloc 50000 longs (large)\n", c2);
     if(c2) check_zero(c2, 50000 * sizeof(long)); // mmap should zero it
    alt_free(c2); // Should use munmap

    // Add other malloc/free tests here if desired

    printf("\nMemory allocator test finished.\n");
    return 0;
}

Compile and run:

gcc alt_mem.c main.c -o allocator_test
./allocator_test

Check the output. You should see the "DEBUG calloc" messages, the correct use of mmap or sbrk, and the "Memory check: OK" messages confirming the zeroing worked.

Step 10: Implementing alt_realloc

realloc(ptr, new_size) is the most complex. It changes the size of an existing allocation.

Cases for realloc(ptr, new_size):

ptr == NULL: Equivalent to alt_malloc(new_size).
new_size == 0: Equivalent to alt_free(ptr). Return NULL.
Block is STATUS_MAPPED:
- If new_size == old_size, return ptr.
- Otherwise, always alt_malloc(new_size), memcpy the minimum of old and new data, alt_free(ptr), and return the new pointer. mremap() could optimize this, but we'll keep it simple.
Block is STATUS_ALLOC (sbrk block): a. Shrinking (new_size < old_size): * If the leftover space (old_size - new_size) is large enough to create a new free block (i.e., >= sizeof(meta) + alignment), split the block similar to how malloc splits. Create a new STATUS_FREE block for the remainder, update the current block's size to new_size, and join_free_blocks() on the new free block. * If not enough space to split, just keep the original block size (internal fragmentation). Some allocators might update the size field anyway, but not splitting is safer here. Return ptr. b. Growing (new_size > old_size): i. Check Next Block: Look at block->next. If it's STATUS_FREE and physically adjacent and the combined size (block->size + sizeof(meta) + block->next->size) is >= new_size, then: * Merge block->next into block (update size, unlink block->next). * If the newly merged block is now larger than new_size, potentially split off the excess as a new free block (similar to shrinking). * Return ptr. ii. Check Last Block + Extend sbrk: (Optimization - Harder) If block is the very last block allocated via sbrk on the heap, we can try to extend the heap using sbrk(new_size - old_size). If successful, just update block->size and return ptr. This avoids copying. (We'll skip this optimization for simplicity in this tutorial, as tracking the "last sbrk block" adds complexity). iii. Allocate New, Copy, Free: If the above don't work, call alt_malloc(new_size), memcpy(new_ptr, ptr, old_size), alt_free(ptr), and return new_ptr.

Let's implement alt_realloc based on these rules (omitting the "last block + sbrk extend" optimization):

#include <string.h> // Ensure memcpy is included

// Helper for min
static size_t min(size_t a, size_t b) {
    return (a < b) ? a : b;
}


void *alt_realloc(void *ptr, size_t size) {
    // 1. Handle edge cases: ptr is NULL or size is 0
    if (ptr == NULL) {
        return alt_malloc(size); // Behaves like malloc
    }
    if (size == 0) {
        alt_free(ptr); // Behaves like free
        return NULL;
    }

    // 2. Get metadata and align new size
    block_meta_t *block = get_block_ptr(ptr);
    size_t new_size = ALIGN8(size);
    size_t old_size = block->size; // Current usable size

     printf("DEBUG realloc: ptr=%p, old_size=%zu, new_size=%zu, status=%d\n",
           ptr, old_size, new_size, block->status);

    // Sanity check: Cannot realloc a free block
    if (block->status == STATUS_FREE) {
        fprintf(stderr, "Error: Attempting to realloc a freed block at %p\n", ptr);
        return NULL; // Or abort, depending on desired strictness
    }

    // 3. Handle STATUS_MAPPED blocks
    if (block->status == STATUS_MAPPED) {
        printf("DEBUG realloc: Block is MAPPED.\n");
        if (new_size == old_size) {
            return ptr; // Size is the same, do nothing
        }
        // Allocate new, copy, free old for mmap realloc
        void *new_ptr = alt_malloc(new_size); // Will use mmap if new_size is large
        if (!new_ptr) return NULL; // Allocation failed
        memcpy(new_ptr, ptr, min(new_size, old_size));
        alt_free(ptr); // Frees the original mmap block
        return new_ptr;
    }

    // --- Handle STATUS_ALLOC (sbrk) blocks ---

    // 4. Handle Shrinking
    if (new_size <= old_size) {
        printf("DEBUG realloc: Shrinking block (or size unchanged).\n");
        // Try to split if significant space is saved
        size_t diff = old_size - new_size;
        if (diff >= sizeof(block_meta_t) + ALIGN8(1)) {
            printf("DEBUG realloc: Splitting block during shrink.\n");
            // Create the new free block for the remainder
            block_meta_t *new_free_block = (block_meta_t *)((char *)(block + 1) + new_size);
            new_free_block->size = diff - sizeof(block_meta_t);
            new_free_block->status = STATUS_FREE;

            // Link it in
            new_free_block->next = block->next;
            new_free_block->prev = block;
            if (block->next) block->next->prev = new_free_block;
            block->next = new_free_block;

            // Update original block's size
            block->size = new_size;

            // Coalesce the newly created free block with its *next* neighbor if possible
            join_free_blocks(new_free_block);
        } else {
             printf("DEBUG realloc: Not enough space saved to split block during shrink.\n");
             // Keep the block as is (internal fragmentation)
        }
        return ptr; // Return original pointer (data is still valid at the start)
    }

    // 5. Handle Growing
    printf("DEBUG realloc: Growing block.\n");

    // 5a. Check if next block is free and physically adjacent and large enough
    if (block->next && block->next->status == STATUS_FREE &&
        (char *)block + sizeof(block_meta_t) + old_size == (char *)block->next)
    {
        size_t combined_size = old_size + sizeof(block_meta_t) + block->next->size;
         printf("DEBUG realloc: Next block (%p, size %zu) is FREE and adjacent.\n",
               (void*)block->next, block->next->size);
        if (combined_size >= new_size) {
             printf("DEBUG realloc: Coalescing with next block to grow.\n");
            // Merge block->next into block
            block->size = combined_size; // New size is the combined payload
            block_meta_t* next_next = block->next->next; // Save pointer
            block->next = next_next;     // Unlink the absorbed block
            if (next_next) next_next->prev = block;

            // Check if we have excess space after merging, try to split again
            size_t excess = block->size - new_size;
            if (excess >= sizeof(block_meta_t) + ALIGN8(1)) {
                 printf("DEBUG realloc: Splitting after growing via coalesce.\n");
                block_meta_t *new_free_block = (block_meta_t *)((char *)(block + 1) + new_size);
                new_free_block->size = excess - sizeof(block_meta_t);
                new_free_block->status = STATUS_FREE;

                new_free_block->next = block->next;
                new_free_block->prev = block;
                if(block->next) block->next->prev = new_free_block;
                block->next = new_free_block;
                block->size = new_size; // Set block size accurately

                // No need to call join_free_blocks here, as we just created it from merged space
            }
             printf("DEBUG realloc: Growth successful via coalesce. New size: %zu\n", block->size);
            return ptr; // Return original pointer
        } else {
             printf("DEBUG realloc: Next free block not large enough (%zu needed, %zu available)\n",
                   new_size - old_size, sizeof(block_meta_t) + block->next->size);
        }
    } else {
         printf("DEBUG realloc: Next block (%p) is not suitable for merge (status=%d, adjacent check failed?).\n",
               (void*)block->next, block->next ? block->next->status : -1);
    }

    // 5b. (Skipping sbrk extension optimization)

    // 5c. Allocate new block, copy data, free old block
    printf("DEBUG realloc: Cannot grow in place. Allocating new block, copying, freeing old.\n");
    void *new_ptr = alt_malloc(new_size);
    if (!new_ptr) {
        return NULL; // Allocation failed
    }
    memcpy(new_ptr, ptr, old_size); // Copy original data
    alt_free(ptr);                  // Free the old block
    return new_ptr;
}

Compilation and Testing (Step 10)

Add realloc tests to main.c:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "alt_mem.h"

// check_zero helper from before...
void check_zero(void *ptr, size_t size) { /* ... */ }

int main(void) {
    printf("Starting memory allocator test...\n");

    printf("\n[Test 1: realloc ptr=NULL]\n");
    void *r1 = alt_realloc(NULL, 100);
    printf("r1 (%p) realloc(NULL, 100) (like malloc)\n", r1);

    printf("\n[Test 2: realloc size=0]\n");
    printf("Realloc r1 (%p) to size 0 (like free)...\n", r1);
    void *r_null = alt_realloc(r1, 0);
    if (r_null == NULL) printf(" -> OK, returned NULL\n"); else printf(" -> FAIL, did not return NULL\n");
    // r1 is now freed (or should be)

    printf("\n[Test 3: realloc - Shrinking with Split]\n");
    char *r2 = alt_malloc(500);
    strcpy(r2, "Test string data");
    printf("r2 (%p) alloc 500. Contains: '%s'\n", r2, r2);
    printf("Realloc r2 to 100 bytes...\n");
    char *r2_shrunk = alt_realloc(r2, 100);
    printf("r2_shrunk (%p) realloc to 100. Should be same addr as r2.\n", r2_shrunk);
    printf(" -> Contains: '%.*s'\n", 100, r2_shrunk); // Print only 100 chars
    // Now there should be a free block of ~376 bytes after r2_shrunk

    printf("\n[Test 4: realloc - Growing using adjacent free block]\n");
    printf("Realloc r2_shrunk back to 400 bytes...\n");
    char *r2_grown = alt_realloc(r2_shrunk, 400);
    printf("r2_grown (%p) realloc to 400. Should be same addr as r2/r2_shrunk.\n", r2_grown);
    printf(" -> Original string still there? '%.*s'\n", 20, r2_grown);
    // Should have merged with the free block created in Test 3

    printf("\n[Test 5: realloc - Growing by moving]\n");
    char *r3 = alt_malloc(50); // Allocate a small block right after r2_grown potentially
    printf("r3 (%p) alloc 50.\n", r3);
    printf("Realloc r2_grown to 1000 bytes...\n");
    char *r2_moved = alt_realloc(r2_grown, 1000);
    printf("r2_moved (%p) realloc to 1000. Should be at a NEW address.\n", r2_moved);
    printf(" -> Original string still there? '%.*s'\n", 20, r2_moved);

    printf("\n[Test 6: Clean up]\n");
    alt_free(r3);
    alt_free(r2_moved); // Free the final location of the block
    printf("Freed r3, r2_moved.\n");


    printf("\n[Test 7: realloc mmap block]\n");
    size_t large_size = 200 * 1024;
    size_t larger_size = 300 * 1024;
    char *m1 = alt_malloc(large_size);
    printf("m1 (%p) alloc %zu (mmap)\n", m1, large_size);
    memset(m1, 'A', large_size); // Fill with 'A'
    printf("Realloc m1 to %zu bytes...\n", larger_size);
    char *m2 = alt_realloc(m1, larger_size);
    printf("m2 (%p) realloc to %zu. Should be NEW address.\n", m2, larger_size);
    if (m2 && m2[0] == 'A' && m2[large_size - 1] == 'A') {
        printf(" -> Data seems to be copied correctly.\n");
    } else {
         printf(" -> Data copy check failed!\n");
    }
    alt_free(m2);


    printf("\nMemory allocator test finished.\n");
    return 0;
}

Compile and run:

gcc alt_mem.c main.c -o allocator_test
./allocator_test

Carefully follow the DEBUG output for the realloc tests. Verify:

Shrinking happens in-place and splits correctly.
Growing happens in-place by merging with the following free block when possible.
Growing uses alloc-copy-free when it can't happen in-place.
realloc on mmap-ed blocks uses alloc-copy-free.

Conclusion and Final Code

Congratulations! You've built a functional, albeit simple, dynamic memory allocator in C. It handles small and large allocations, reuses freed blocks using a best-fit strategy, splits blocks to reduce waste, coalesces adjacent free blocks to combat fragmentation, and correctly implements malloc, free, calloc, and realloc.

Final Code:

alt_mem.h

// SPDX-License-Identifier: BSD-3-Clause

#pragma once // Ensures this header is included only once per compilation unit

#include <stddef.h> // Provides size_t type

// --- Function Prototypes ---
// These declare the functions we will implement in alt_mem.c

/*
 * Allocates 'size' bytes of uninitialized memory.
 * Returns: A pointer to the allocated memory, or NULL if the request fails.
 */
void *alt_malloc(size_t size);

/*
 * Frees the memory space pointed to by 'ptr', which must have been returned
 * by a previous call to alt_malloc(), alt_calloc() or alt_realloc().
 * If 'ptr' is NULL, no operation is performed.
 */
void alt_free(void *ptr);

/*
 * Allocates memory for an array of 'nmemb' elements of 'size' bytes each
 * and returns a pointer to the allocated memory. The memory is set to zero.
 * Returns: A pointer to the allocated memory, or NULL if the request fails.
 */
void *alt_calloc(size_t nmemb, size_t size);

/*
 * Changes the size of the memory block pointed to by 'ptr' to 'size' bytes.
 * The contents will be unchanged in the range from the start of the region
 * up to the minimum of the old and new sizes. If the new size is larger,
 * the added memory will not be initialized.
 * If 'ptr' is NULL, the call is equivalent to alt_malloc(size).
 * If 'size' is 0, the call is equivalent to alt_free(ptr).
 * Returns: A pointer to the newly allocated memory, or NULL if the request fails.
 */
void *alt_realloc(void *ptr, size_t size);

alt_mem.c

// SPDX-License-Identifier: BSD-3-Clause

#include "alt_mem.h" // Include our header

#include <stdio.h>      // For perror, printf (debug)
#include <stdlib.h>     // For exit, EXIT_FAILURE
#include <unistd.h>     // For sbrk, sysconf
#include <sys/mman.h>   // For mmap, munmap, MAP_FAILED, PROT_*, MAP_*
#include <string.h>     // For memset, memcpy
#include <stdbool.h>    // For bool type (optional)


// --- Constants and Macros ---

// Alignment: Align memory blocks to 8 bytes
#define ALIGN8(x) (((x) + 7) & (~7))

// Threshold for using mmap instead of sbrk (128 KiB)
#define MMAP_THRESHOLD (128 * 1024)

// Minimum payload size for a splittable block remainder (must hold meta + alignment)
#define MIN_SPLIT_PAYLOAD ALIGN8(1)

// --- Error Handling Helper ---
#define DIE(assertion, call_description)                                \
    do {                                                                \
        if (assertion) {                                                \
            perror(call_description);                                   \
            exit(EXIT_FAILURE);                                         \
        }                                                               \
    } while (0)


// --- Data Structures ---

// Possible states for a memory block
typedef enum {
    STATUS_FREE,    // Block is free and available for allocation
    STATUS_ALLOC,   // Block is currently allocated (used by sbrk)
    STATUS_MAPPED   // Block was allocated using mmap
} block_status;

// Metadata structure prepended to each memory block
typedef struct block_meta {
    size_t size;             // Size of the *user* data area (payload)
    block_status status;     // Current status of the block
    struct block_meta *next; // Pointer to the next block_meta in the list
    struct block_meta *prev; // Pointer to the previous block_meta in the list
} block_meta_t;


// --- Global Variables ---

// Head of the linked list of memory blocks.
static block_meta_t *head = NULL;


// --- Helper Functions ---

// Find the last block in our linked list
static block_meta_t *find_last_entry(void) {
    block_meta_t *current = head;
    if (!current) {
        return NULL;
    }
    while (current->next) {
        current = current->next;
    }
    return current;
}

// Request memory from the OS using sbrk (for smaller allocations)
static block_meta_t *request_space(size_t size, block_meta_t *last_entry) {
    block_meta_t *block = sbrk(sizeof(block_meta_t) + size);
    if (block == (void *)-1) {
        perror("sbrk failed");
        return NULL;
    }

    block->size = size;
    block->status = STATUS_ALLOC;
    block->next = NULL;
    block->prev = last_entry;

    if (last_entry) {
        last_entry->next = block;
    } else {
        head = block;
    }
    printf("DEBUG sbrk: Requested block at %p (meta), user size %zu\n", (void*)block, size);
    return block;
}

// Map memory using mmap (for large allocations)
static void *map_memory(size_t size, block_meta_t *last_entry) {
    block_meta_t *block = mmap(NULL, sizeof(block_meta_t) + size,
                             PROT_READ | PROT_WRITE,
                             MAP_PRIVATE | MAP_ANONYMOUS,
                             -1, 0);

    DIE(block == MAP_FAILED, "mmap failed");

    block->size = size;
    block->status = STATUS_MAPPED;
    block->next = NULL;
    block->prev = last_entry;

    if (last_entry) {
        last_entry->next = block;
    } else {
        head = block;
    }
    printf("DEBUG mmap: Mapped block at %p (meta), user size %zu\n", (void*)block, size);
    return (void *)(block + 1);
}

// Find the best-fit free block (only considers sbrk blocks)
static block_meta_t *find_best_fit(size_t size) {
    block_meta_t *current = head;
    block_meta_t *best_fit = NULL;

    while (current) {
        if (current->status == STATUS_FREE && current->size >= size) {
            if (best_fit == NULL || current->size < best_fit->size) {
                best_fit = current;
                if (best_fit->size == size) break; // Perfect fit found
            }
        }
        current = current->next;
    }
    return best_fit;
}

// Get metadata pointer from user pointer
static block_meta_t *get_block_ptr(void *ptr) {
    if (!ptr) return NULL;
    return (block_meta_t *)ptr - 1;
}

// Coalesce adjacent free sbrk blocks
static void join_free_blocks(block_meta_t *block) {
     printf("DEBUG coalesce: Attempting around %p (size %zu, status %d)\n",
           (void*)block, block->size, block->status);

     // Coalesce with next block (must be FREE and physically adjacent sbrk block)
    if (block->next && block->next->status == STATUS_FREE &&
        (char *)block + sizeof(block_meta_t) + block->size == (char *)block->next)
    {
         printf("DEBUG coalesce: Merging %p with next %p\n", (void*)block, (void*)block->next);
        block->size += sizeof(block_meta_t) + block->next->size;
        block->next = block->next->next;
        if (block->next) block->next->prev = block;
    }

    // Coalesce with previous block (must be FREE and physically adjacent sbrk block)
    if (block->prev && block->prev->status == STATUS_FREE &&
        (char *)block->prev + sizeof(block_meta_t) + block->prev->size == (char *)block)
    {
        printf("DEBUG coalesce: Merging %p into previous %p\n", (void*)block, (void*)block->prev);
        block->prev->size += sizeof(block_meta_t) + block->size;
        block->prev->next = block->next;
        if (block->next) block->next->prev = block->prev;
        // block = block->prev; // Conceptually the merged block is the previous one
    }
     printf("DEBUG coalesce: Finished attempt around %p\n", (void*)block);
}

// Split a block if the remainder is large enough
static void try_split_block(block_meta_t* block, size_t requested_size) {
    size_t remaining_payload = block->size - requested_size;

    if (remaining_payload >= sizeof(block_meta_t) + MIN_SPLIT_PAYLOAD) {
        printf("DEBUG split: Splitting block %p (orig size %zu, req size %zu)\n",
                (void*)block, block->size, requested_size);
        // Calculate new free block meta address
        block_meta_t *new_free_block = (block_meta_t *)((char *)(block + 1) + requested_size);
        new_free_block->size = remaining_payload - sizeof(block_meta_t);
        new_free_block->status = STATUS_FREE;

        // Link new free block into the list
        new_free_block->next = block->next;
        new_free_block->prev = block;
        if (block->next) block->next->prev = new_free_block;
        block->next = new_free_block;

        // Update original block's size
        block->size = requested_size;

        // Coalesce the *newly created* free block forward if possible
        // (We don't need to check backward as we just split from 'block')
        join_free_blocks(new_free_block);

    } else {
         printf("DEBUG split: Not enough space to split block %p (remainder %zu)\n",
               (void*)block, remaining_payload);
    }
}


// --- Public API Functions ---

void *alt_malloc(size_t size) {
    if (size == 0) return NULL;
    size = ALIGN8(size);

    block_meta_t *block = NULL;
    block_meta_t *last_entry = find_last_entry(); // Needed for both paths

    if (size >= MMAP_THRESHOLD) {
         printf("DEBUG malloc: Using mmap for request size %zu\n", size);
        return map_memory(size, last_entry);
    }

    // Try finding best fit among existing sbrk blocks
    block = find_best_fit(size);
    if (block) {
         printf("DEBUG malloc: Found free block %p (size %zu) for request %zu\n",
               (void*)block, block->size, size);
        // Try to split if the found block is larger than needed
        try_split_block(block, size);
        block->status = STATUS_ALLOC;

    } else {
         printf("DEBUG malloc: No suitable free block. Using sbrk for request size %zu\n", size);
        // No suitable free block, request new space via sbrk
        block = request_space(size, last_entry);
        if (!block) return NULL; // sbrk failed
        // block->status is already STATUS_ALLOC from request_space
    }

    return (void *)(block + 1); // Return user data pointer
}

void alt_free(void *ptr) {
    if (ptr == NULL) return;

    block_meta_t *block = get_block_ptr(ptr);

    if (block->status == STATUS_ALLOC) {
         printf("DEBUG free: Freeing sbrk block %p (size %zu)\n", (void*)block, block->size);
        block->status = STATUS_FREE;
        join_free_blocks(block); // Attempt to merge with neighbors

    } else if (block->status == STATUS_MAPPED) {
         printf("DEBUG free: Freeing mmap block %p (size %zu)\n", (void*)block, block->size);
        // Unlink from list
        if (block->prev) block->prev->next = block->next;
        else head = block->next;
        if (block->next) block->next->prev = block->prev;

        // Unmap memory
        size_t total_size = sizeof(block_meta_t) + block->size;
        int ret = munmap(block, total_size);
        DIE(ret == -1, "munmap failed");

    } else if (block->status == STATUS_FREE) {
         printf("DEBUG free: Warning - block %p already free.\n", (void*)block);
        // Double free detected - could abort or just ignore
    } else {
         fprintf(stderr, "Error: Invalid block status (%d) during free at %p\n", block->status, (void*)block);
         // Could indicate memory corruption
    }
}

void *alt_calloc(size_t nmemb, size_t size) {
    size_t total_size = nmemb * size;
    // Check for overflow and zero request
    if (nmemb == 0 || size == 0 || (nmemb > 0 && total_size / nmemb != size)) {
        return NULL;
    }

    void *ptr = alt_malloc(total_size); // Use alt_malloc for allocation logic

    if (ptr) {
        // If allocation came from sbrk (STATUS_ALLOC), zero it.
        // mmap anonymous memory is already zeroed.
        block_meta_t *block = get_block_ptr(ptr);
        if (block->status == STATUS_ALLOC) {
             printf("DEBUG calloc: Zeroing sbrk block %p (size %zu)\n", (void*)block, block->size);
            memset(ptr, 0, block->size); // Zero the user payload
        } else {
             printf("DEBUG calloc: Block %p is mmap-ed (already zeroed)\n", (void*)block);
        }
    }
    return ptr;
}

// Helper for min comparison
static size_t min(size_t a, size_t b) { return (a < b) ? a : b; }

void *alt_realloc(void *ptr, size_t size) {
    // 1. Handle edge cases
    if (ptr == NULL) return alt_malloc(size);
    if (size == 0) { alt_free(ptr); return NULL; }

    block_meta_t *block = get_block_ptr(ptr);
    size_t new_size = ALIGN8(size);
    size_t old_size = block->size;

    printf("DEBUG realloc: ptr=%p, old_size=%zu, new_size=%zu, status=%d\n",
           ptr, old_size, new_size, block->status);

    if (block->status == STATUS_FREE) {
        fprintf(stderr, "Error: Realloc on freed block %p\n", ptr); return NULL;
    }

    // 2. Handle MAPPED blocks -> always alloc/copy/free if size changes
    if (block->status == STATUS_MAPPED) {
        if (new_size == old_size) return ptr;
        printf("DEBUG realloc: MAPPED block. Alloc-copy-free.\n");
        void *new_ptr = alt_malloc(new_size); // malloc handles threshold check
        if (!new_ptr) return NULL;
        memcpy(new_ptr, ptr, min(new_size, old_size));
        alt_free(ptr); // Munmaps the old block
        return new_ptr;
    }

    // --- Handle ALLOC (sbrk) blocks ---

    // 3. Shrinking or same size
    if (new_size <= old_size) {
         printf("DEBUG realloc: Shrinking/same size sbrk block %p\n", (void*)block);
        try_split_block(block, new_size); // Split if significant space saved
        return ptr; // Original pointer is still valid
    }

    // 4. Growing - Check next block for merge opportunity
    printf("DEBUG realloc: Growing sbrk block %p\n", (void*)block);
    if (block->next && block->next->status == STATUS_FREE &&
        (char *)block + sizeof(block_meta_t) + old_size == (char *)block->next)
    {
        size_t combined_payload = old_size + sizeof(block_meta_t) + block->next->size;
        printf("DEBUG realloc: Next block %p is free and adjacent. Combined payload: %zu\n",
               (void*)block->next, combined_payload);

        if (combined_payload >= new_size) {
            // Merge is sufficient
             printf("DEBUG realloc: Merging next block %p into %p\n", (void*)block->next, (void*)block);
            // Absorb next block
            block->size = combined_payload;
            block_meta_t *next_next = block->next->next;
            block->next = next_next;
            if (next_next) next_next->prev = block;

            // Split if we merged too much space
            try_split_block(block, new_size);
            printf("DEBUG realloc: Growth via merge successful for %p. New size: %zu\n", (void*)block, block->size);
            return ptr; // Original pointer still valid
        } else {
             printf("DEBUG realloc: Next block not large enough for merge.\n");
        }
    } else {
         printf("DEBUG realloc: Next block not suitable for merging.\n");
    }

    // 5. Cannot grow in place - Allocate new, copy, free old
    printf("DEBUG realloc: Cannot grow in place. Alloc-copy-free for %p.\n", (void*)block);
    void *new_ptr = alt_malloc(new_size);
    if (!new_ptr) return NULL;
    memcpy(new_ptr, ptr, old_size); // Copy *only* the old data size
    alt_free(ptr);                  // Free the original sbrk block
    return new_ptr;
}

main.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h> // For exit, EXIT_FAILURE
#include "alt_mem.h" // Include our allocator's header

#define LARGE_ALLOC_SIZE (200 * 1024)
#define LARGER_ALLOC_SIZE (300 * 1024)

// Helper to check if memory is zeroed
void check_zero(const char* test_name, void *ptr, size_t size) {
    if (!ptr) {
         fprintf(stderr, "[%s] Error: Pointer is NULL, cannot check zero.\n", test_name);
         exit(EXIT_FAILURE);
    }
    unsigned char *byte_ptr = (unsigned char *)ptr;
    for (size_t i = 0; i < size; ++i) {
        if (byte_ptr[i] != 0) {
            fprintf(stderr, "[%s] Error: Memory not zeroed at byte %zu (value: 0x%02x)!\n", test_name, i, byte_ptr[i]);
            exit(EXIT_FAILURE); // Abort test
        }
    }
     printf("[%s] -> Memory check: OK (all %zu bytes zero)\n", test_name, size);
}


int main(void) {
    printf("Starting memory allocator test...\n");

    printf("\n--- Malloc & Free Test ---\n");
    void *p1 = alt_malloc(100); printf("p1 (%p) alloc 100\n", p1);
    void *p2 = alt_malloc(200); printf("p2 (%p) alloc 200\n", p2);
    void *p3 = alt_malloc(50);  printf("p3 (%p) alloc 50\n", p3);
    alt_free(p2); printf("Freed p2 (%p)\n", p2);
    void *p4 = alt_malloc(150); printf("p4 (%p) alloc 150 (should reuse p2's space and split)\n", p4);
    alt_free(p1); printf("Freed p1 (%p)\n", p1);
    alt_free(p4); printf("Freed p4 (%p) (should coalesce with remainder of p2)\n", p4);
    alt_free(p3); printf("Freed p3 (%p) (should coalesce with p1)\n", p3);
    // Now should have one large free block

    printf("\n--- Calloc Test ---\n");
    int *c1 = alt_calloc(20, sizeof(int)); printf("c1 (%p) calloc 20 ints (sbrk)\n", c1);
    check_zero("calloc_small", c1, 20 * sizeof(int));
    long *c2 = alt_calloc(40000, sizeof(long)); printf("c2 (%p) calloc 40000 longs (mmap)\n", c2);
    check_zero("calloc_large", c2, 40000 * sizeof(long));
    alt_free(c1); printf("Freed c1\n");
    alt_free(c2); printf("Freed c2 (munmap)\n");

    printf("\n--- Realloc Test ---\n");
    char *r1 = alt_realloc(NULL, 100); printf("r1 (%p) realloc(NULL, 100)\n", r1);
    strcpy(r1, "Initial Data");
    printf("Realloc r1 to 50 (shrink & split)...\n");
    char *r2 = alt_realloc(r1, 50); printf("r2 (%p) realloc to 50. Addr should be same as r1.\n", r2);
    printf(" -> r2 contains: '%.*s'\n", 50, r2);

    printf("Realloc r2 to 400 (grow via coalesce)...\n");
    char *r3 = alt_realloc(r2, 400); printf("r3 (%p) realloc to 400. Addr should be same as r1/r2.\n", r3);
    printf(" -> r3 still starts with: '%.*s'\n", 20, r3);

    char *r_neighbor = alt_malloc(30); printf("r_neighbor (%p) alloc 30.\n", r_neighbor); // Block next attempt to grow in place
    printf("Realloc r3 to 1000 (grow via move)...\n");
    char *r4 = alt_realloc(r3, 1000); printf("r4 (%p) realloc to 1000. Addr should be NEW.\n", r4);
    printf(" -> r4 still starts with: '%.*s'\n", 20, r4);

    printf("Realloc r4 to 0 (free)...\n");
    void* r_null = alt_realloc(r4, 0);
    if (r_null == NULL) printf(" -> OK, returned NULL.\n"); else printf(" -> FAILED, expected NULL.\n");

    alt_free(r_neighbor); printf("Freed r_neighbor\n");


    printf("\n--- Realloc Mmap Test ---\n");
    char *m1 = alt_malloc(LARGE_ALLOC_SIZE); printf("m1 (%p) alloc %d (mmap)\n", m1, LARGE_ALLOC_SIZE);
    memset(m1, 'X', LARGE_ALLOC_SIZE);
    printf("Realloc m1 to %d (mmap grow)...\n", LARGER_ALLOC_SIZE);
    char *m2 = alt_realloc(m1, LARGER_ALLOC_SIZE); printf("m2 (%p) realloc to %d. Addr should be NEW.\n", m2, LARGER_ALLOC_SIZE);
    if (m2 && m2[0] == 'X' && m2[LARGE_ALLOC_SIZE-1] == 'X') printf(" -> Data copy seems OK.\n"); else printf(" -> Data copy check FAILED.\n");
    printf("Realloc m2 to 500 (mmap shrink)...\n");
    char *m3 = alt_realloc(m2, 500); printf("m3 (%p) realloc to 500. Addr should be NEW.\n", m3);
     if (m3 && m3[0] == 'X' && m3[499] == 'X') printf(" -> Data copy seems OK.\n"); else printf(" -> Data copy check FAILED.\n");
    alt_free(m3); printf("Freed m3\n"); // Free the final small mmap block


    printf("\nMemory allocator test finished.\n");
    return 0;
}

Further Exploration:

Efficiency: This allocator uses a linear scan for find_best_fit, which is slow ($O(N)$ where N is the number of blocks). Real allocators use more complex data structures (like segregated free lists, trees) to find free blocks faster.
Thread Safety: This allocator is not thread-safe. If multiple threads called alt_malloc or alt_free concurrently, the linked list could become corrupted. Adding mutexes or other locking mechanisms would be necessary.
sbrk Reduction: Our alt_free doesn't shrink the heap using sbrk(negative_value) if the very last block becomes free. This could be added.
Different Strategies: Explore "first-fit" or "worst-fit" allocation strategies instead of "best-fit".

This tutorial provides a solid foundation for understanding the core concepts behind dynamic memory allocation!

DEV Community: SegFault

Demystifying malloc: Build Your Own Memory Allocator in C