Memory Allocation

[!NOTE] This module explores the core principles of Memory Allocation, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. The Problem: The Heap is Manual

When you declare int x;, the compiler allocates it on the Stack. It’s fast and automatic. When you call malloc(100), you are asking for 100 bytes on the Heap. The OS must find a free hole in the chaos.

The Memory Allocator (part of libc or the runtime) manages a large chunk of memory requested from the kernel (via sbrk or mmap).

Fragmentation: The Enemy

1. External Fragmentation: Total free memory is enough, but it’s scattered in small non-contiguous holes.
2. Internal Fragmentation: You ask for 10 bytes, but the allocator gives you a 32-byte block (padding). The extra 22 bytes are wasted.

---

2. Allocation Strategies

1. Free List (First Fit / Best Fit)

Maintain a Linked List of free blocks.

• First Fit: Scan the list, take the first hole that fits. Fast, but fragments memory.
• Best Fit: Scan the whole list, find the smallest hole that fits. Slow (O(N)), but saves large holes.

2. The Buddy System

Divide memory into powers of 2 (4KB, 8KB, 16KB…). If you need 7KB:

1. Split a 16KB block into two 8KB “buddies”.
2. Give one 8KB block to the user. Coalescing: When you free the 8KB block, check if its “buddy” is also free. If so, merge them back into a 16KB block.

3. Slab Allocation (Kernel Favorite)

The OS Kernel creates frequent objects of the same size (e.g., task_struct, inode). Instead of a generic allocator, we create a Cache (Slab) for each object type.

• Pros: Zero fragmentation (objects fit perfectly). Extremely fast allocation (pop from free list).

---

3. Interactive: Allocator Visualizer

Simulate a simple Heap Allocator. Watch how random allocations create External Fragmentation (holes).

0x0000 0xFFFF

Heap: Empty

---

4. Code Example: Low-Level Allocation

How do languages interact with raw memory?

• Go: Uses unsafe.Pointer to bypass type safety.
• Java: Uses ByteBuffer (or Unsafe) to allocate off-heap memory (outside GC control).

package main

import (
	"fmt"
	"unsafe"
)

type Header struct {
	Size int
	Free bool
}

func main() {
	// Simulate a raw memory block
	// [Header][Data.....][Header][Data.....]

	// 1. Create a byte array acting as our "Heap"
	heap := make([]byte, 1024)

	// 2. Cast the beginning to a Header struct
	ptr := unsafe.Pointer(&heap[0])
	header := (*Header)(ptr)

	header.Size = 64
	header.Free = false

	fmt.Printf("Allocated Block at %p\n", header)
	fmt.Printf("Block Size: %d\n", header.Size)

	// 3. Calculate address of next block
	// Pointer Arithmetic: ptr + sizeof(Header) + Size
	nextPtr := uintptr(ptr) + unsafe.Sizeof(*header) + uintptr(header.Size)
	nextHeader := (*Header)(unsafe.Pointer(nextPtr))

	nextHeader.Size = 128
	nextHeader.Free = true

	fmt.Printf("Next Free Block at 0x%x\n", nextPtr)
}

import java.nio.ByteBuffer;

public class OffHeap {
    public static void main(String[] args) {
        // Allocate 1KB Off-Heap (Directly in OS RAM, not JVM Heap)
        // This is not subject to GC! You must manage it manually.
        ByteBuffer buffer = ByteBuffer.allocateDirect(1024);

        // Write data "manually" like C
        // Address 0: 42
        buffer.putInt(0, 42);

        // Address 4: 123
        buffer.putInt(4, 123);

        System.out.println("Value at offset 0: " + buffer.getInt(0));
        System.out.println("Value at offset 4: " + buffer.getInt(4));

        // If we lose the reference to 'buffer', the Cleaner will eventually
        // free the OS memory, but it's non-deterministic.
    }
}