📚 Introduction to the Heap

💡 What is the Heap?

The heap is a region of memory used for dynamic memory allocation — memory that is allocated and freed at runtime rather than at compile time.

In C, you access the heap using:

• malloc() / calloc() / realloc()
• and free() to release the memory

Unlike the stack, which has a Last-In-First-Out (LIFO) structure, the heap is non-linear — memory blocks can be allocated and freed in any order, which introduces complexity like fragmentation.

🧠 Heap vs Stack in Physical & Virtual Memory

📦 Typical Memory Layout (Simplified)

High Memory Address
+---------------------+ 
|   Stack             |  ← grows downward
|   Local variables   |
+---------------------+ 
|                     |
|   (unmapped space)  |
|                     |
+---------------------+ 
|   Heap              |  ← grows upward
|   malloc, buffers   |
+---------------------+ 
|   BSS Segment       |  ← uninitialized globals
|   Data Segment      |  ← initialized globals
|   Text Segment      |  ← code (read-only)
+---------------------+
Low Memory Address

🧭 Where Are They Physically?

🔷 Stack

• Usually starts at the top of the user space address (like 0x7fffffffe000 on x86_64).
• The OS reserves a region for the stack — usually a few MB per thread.
• Grows down, closer to heap space.

🔶 Heap

• Starts just after the data segment (where global/static variables live).
• The brk/sbrk system calls traditionally manage it, moving the program’s “heap break” up or down.
• Nowadays, mmap() is used too (especially for larger allocations), which allows non-contiguous heap memory.

🧩 In Linux: Heap & Stack Mapping via /proc

You can inspect the layout using:

cat /proc/<pid>/maps

You’ll see entries like:

00400000-00452000 r-xp ... /bin/bash     ← Text segment
00651000-00652000 rw-p ...               ← Data segment
00652000-008b3000 rw-p ...               ← Heap
7ffddc1ce000-7ffddc1ef000 rw-p ...       ← Stack

🧵 Why Heap Matters in Low-Level Systems

In embedded systems, operating systems, or kernels like Linux, developers often need fine-grained control over memory — you can’t just use malloc() and call it a day.

That’s where custom heap implementations (like yours) shine.

🏗️ Heap Usage in the Linux Kernel

Linux doesn’t use malloc() — instead, it provides its own memory allocation APIs, optimized for kernel needs.

🧩 Key Kernel Memory Allocation APIs

These functions are backed by specialized allocators designed to avoid fragmentation and support high performance under concurrent workloads.

⚙️ How Linux Organizes Heap Memory

Linux divides kernel memory into zones:

1. ZONE_DMA – memory accessible by certain legacy devices
2. ZONE_NORMAL – normal RAM for most kernel allocations
3. ZONE_HIGHMEM – memory not permanently mapped into kernel space (on 32-bit)

Heap-like functionality is usually implemented using:

• Buddy Allocator – for physical page allocation
• Slab/Slub/Slob Allocators – for frequently used kernel objects (e.g., structs)
• vmalloc – for large or non-contiguous memory regions

🔍 Custom Heap vs Kernel Heap

🧪 Use Cases for Your Own Heap

• Bare-metal programming
• Bootloaders
• Kernel modules in development environments
• Simulations / educational systems
• Custom allocators for specific performance goals

📌 Thoughts

The heap is a foundational concept in systems programming. Linux manages it via a set of highly tuned allocators, but understanding and building your own (like the one in malloc_heap.c) is one of the best ways to really understand how memory works at a low level.

Ever wondered how malloc() and free() work under the hood? In environments where you don’t have a standard C library—like embedded systems or operating system kernels—you might need to write your own heap memory allocator.

The following of this article, we’ll walk through a minimalist heap allocator in C.

📦 1. Source Code malloc_heap.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h> // For uintptr_t
#include "malloc_heap.h"

void heap_init(void *hp, char *heap, int total) {
    heap_ctrl_t *ctrl = (heap_ctrl_t *)hp;
    ctrl->total = total;
    ctrl->mp.addr = heap;
    ctrl->mp.size = 0;
    ctrl->top = (free_point_t *)(heap + total);

    free_point_t *first = (free_point_t *)heap;
    first->addr = NULL;
    first->size = total;
}

void *halloc(int size, void *hp) {
    heap_ctrl_t *heap = (heap_ctrl_t *)hp;
    if (size <= 0 || size >= heap->total) return NULL;

    size = ((size + 1) & ~1) + sizeof(free_point_t);

    free_point_t *pp, *cp, *np;

    for (pp = &heap->mp; (cp = (free_point_t *)pp->addr); pp = cp) {
        if (cp->size < size)
            continue;

        if (cp->size > size + sizeof(free_point_t)) {
            np = (free_point_t *)((char *)cp + size);
            pp->addr = (char *)np;
            np->addr = cp->addr;
            np->size = cp->size - size;
            cp->size = size;
        } else {
            pp->addr = cp->addr;
        }

        heap->total -= cp->size;
        cp->addr = (char *)cp;
        return (void *)(cp + 1);
    }
    return NULL;
}

int hfree(void *vfp, void *vhp) {
    if (!vfp) return -1;

    free_point_t *fp = ((free_point_t *)vfp) - 1;
    if ((char *)fp != fp->addr || fp->size <= 0) return -1;

    heap_ctrl_t *hp = (heap_ctrl_t *)vhp;
    free_point_t *pp, *cp, *wp;

    for (pp = &hp->mp; (cp = (free_point_t *)pp->addr); pp = cp) {
        if ((uintptr_t)cp > (uintptr_t)fp)
            break;
    }

    hp->total += fp->size;
    pp->addr = (char *)fp;
    wp = (free_point_t *)((char *)fp + fp->size);

    if ((char *)cp == (char *)wp) {
        fp->size += cp->size;
        fp->addr = cp->addr;
    } else {
        fp->addr = (char *)cp;
    }

    if (pp != &hp->mp && (char *)pp + pp->size == (char *)fp) {
        pp->size += fp->size;
        pp->addr = fp->addr;
    }

    return 0;
}

int heap_size(void *hp) {
    return ((heap_ctrl_t *)hp)->total;
}

int heap_check(void *vhp, void *heap, int total) {
    heap_ctrl_t *hp = (heap_ctrl_t *)vhp;
    char *top = (char *)heap + total;
    free_point_t *pp, *cp;

    hp->total = 0;

    for (pp = &hp->mp; (cp = (free_point_t *)pp->addr); pp = cp) {
        if ((uintptr_t)cp < (uintptr_t)heap || (uintptr_t)cp > (uintptr_t)top)
            return -1;
        if (pp->size < 0 || pp->size > total)
            return -1;

        hp->total += pp->size;
    }

    if (hp->total <= 0 || hp->total >= total)
        return -1;

    return 0;
}

✅ What This Code Does

This is a manual memory allocator using a free list approach:

• Maintains a list of free blocks (free_point_t)
• Each block contains a size and next address
• Supports halloc() to allocate and hfree() to deallocate memory
• Tries to merge adjacent blocks to reduce fragmentation

✅ 2. malloc_heap.h – Header for Allocator

// malloc_heap.h

#ifndef MALLOC_HEAP_H
#define MALLOC_HEAP_H

#ifdef __cplusplus
extern "C" {
#endif

// Type definitions
typedef struct free_point_s {
    int size;
    char *addr;
} free_point_t;

typedef struct heap_ctrl_s {
    int total;
    free_point_t mp;
    free_point_t *top;
} heap_ctrl_t;

// API functions
void heap_init(void *hp, char *heap, int total);
void *halloc(int size, void *hp);
int hfree(void *ptr, void *hp);
int heap_size(void *hp);
int heap_check(void *vhp, void *heap, int total);

#ifdef __cplusplus
}
#endif

#endif // MALLOC_HEAP_H

✅ 3. example of usage.c

#include <stdio.h>
#include <string.h>
#include "malloc_heap.h"  // 💡 Our custom heap allocator

#define HEAP_SIZE 1024
char raw_heap[HEAP_SIZE];
heap_ctrl_t heap;

int main() {
    printf("🔧 Initializing custom heap...\n");
    heap_init(&heap, raw_heap, HEAP_SIZE);

    printf("📊 Heap size after init: %d bytes\n", heap_size(&heap));

    char *ptr1 = (char *)halloc(100, &heap);
    if (ptr1) {
        strcpy(ptr1, "Hello, Heap!");
        printf("✅ Allocated and wrote: %s\n", ptr1);
    }

    printf("📊 Heap size after allocation: %d bytes\n", heap_size(&heap));

    char *ptr2 = (char *)halloc(200, &heap);
    if (ptr2) {
        strcpy(ptr2, "Second block!");
        printf("✅ Second allocation: %s\n", ptr2);
    }

    if (hfree(ptr1, &heap) == 0) {
        printf("♻️  Freed first block\n");
    }

    if (heap_check(&heap, raw_heap, HEAP_SIZE) == 0) {
        printf("🧪 Heap integrity: OK\n");
    } else {
        printf("❌ Heap check failed!\n");
    }

    printf("📊 Final heap size: %d bytes\n", heap_size(&heap));

    return 0;
}

✅ 4. Makefile

# Makefile for custom heap allocator demo

# Compiler and flags
CC = gcc
CFLAGS = -Wall -Wextra -O2

# Source files
SRCS = usage.c malloc_heap.c
OBJS = $(SRCS:.c=.o)

# Executable name
TARGET = heap_demo

# Default rule
all: $(TARGET)

$(TARGET): $(OBJS)
	$(CC) $(CFLAGS) -o $@ $^

%.o: %.c
	$(CC) $(CFLAGS) -c $< -o $@

# Clean up build files
clean:
	rm -f $(OBJS) $(TARGET)

# Just run it (handy shortcut)
run: all
	./$(TARGET)

🛠️ Compilation

In your project folder (with usage.c, malloc_heap.c, and malloc_heap.h), just run:

make        # Builds the heap_demo
make run    # Builds + runs the program
make clean  # Cleans up .o files and binary

🧰 Use Cases

This pattern is ideal when:

• You’re building a kernel or embedded runtime
• You want to implement your own allocator for performance tuning
• You’re teaching students how memory allocation works
• You’re running on a system without malloc() / free()

🚫 Limitations

• Not thread-safe
• No double-free protection
• No advanced strategies like best-fit/worst-fit
• No dynamic resizing of the heap

📚 Conclusion

This is a compact and educational allocator. Whether you’re learning or building something low-level, studying and tweaking allocators gives you deep insight into memory management.

Want to take it further? Try adding:

• A freelist compaction algorithm
• Statistics (e.g., fragmentation %)
• Thread safety with mutex locks