Rajat Negi

Posted on Jul 8

Building malloc from Scratch (Part 2): Bridging Linux, Windows, and Raw CPU Pages

#c #linux #memoryallocator #computerscience

Recapping Part 1

In Part 1, I focused on the design rather than the implementation. The allocator's scope, architecture, and core concepts were established before writing any code.

Scope

Cross-platform (Linux and Windows)
Page-backed
Explicit free-list
Written in C

Project Structure

memory-allocator/
├── include/
│   └── allocator.h
├── src/
│   ├── allocator.c
│   ├── block.c
│   ├── free_list.c
│   ├── utils.c
│   └── os/
│       ├── os.h
│       ├── linux.c
│       └── windows.c
└── tests/
    ├── Makefile
    └── test_os.c

Step 1: Defining the OS Interface
Step 2: Building the Platform Backends
- Linux Backend
- Windows Backend
Step 3: Utility Functions
Step 4: Testing the Platform Layer
What's Next

Step 1: Defining the OS Interface

The allocator itself should never know whether it is running on Linux or Windows.

Instead, it interacts with a very small platform abstraction layer. Every request for raw memory goes through this interface, allowing the rest of the allocator to remain completely platform-independent.

src/os/os.h

#ifndef OS_H
#define OS_H

#include <stddef.h>

/* Allocate memory directly from the operating system */
void *os_alloc(size_t size);

/* Release memory back to the operating system */
void os_free(void *ptr, size_t size);

/* Query the system page size */
size_t os_page_size(void);

#endif

These three functions form the boundary between the allocator and the operating system.

os_alloc() requests one or more pages.
os_free() releases previously allocated pages.
os_page_size() retrieves the system's page size so the allocator never relies on hardcoded values such as 4096.

Everything built later like block headers, free lists, splitting, coalescing, malloc(), calloc(), realloc(), and free() will depend on these functions rather than directly calling operating system APIs.

Step 2: Building the Platform Backends

The interface is identical across platforms.

Only the implementation changes.

On Linux, pages come from mmap(). On Windows, they come from VirtualAlloc().

Both implementations expose the same interface, allowing the allocator logic to remain unchanged regardless of the operating system.

Linux Backend

src/os/linux.c

#ifdef __linux__

#include "os.h"

#include <stdio.h>
#include <sys/mman.h>
#include <unistd.h>

void *os_alloc(size_t size) {
  void *ptr = mmap(
    NULL,
    size,
    PROT_READ | PROT_WRITE,
    MAP_PRIVATE | MAP_ANONYMOUS,
    -1,
    0
  );

  if (ptr == MAP_FAILED) {
    return NULL;
  }

  return ptr;
}

void os_free(void *ptr, size_t size) {
  if (ptr == NULL) {
    return;
  }

  if (munmap(ptr, size) == -1) {
    perror("munmap");
  }
}

size_t os_page_size(void) {
  long page_size = sysconf(_SC_PAGESIZE);

  if (page_size == -1) {
    return 4096;
  }

  return (size_t)page_size;
}

#endif

Rather than using the traditional process heap (sbrk()), this allocator requests independent virtual memory mappings using mmap().

The call is configured with four important arguments:

PROT_READ | PROT_WRITE gives the mapping read and write permissions.
MAP_PRIVATE ensures modifications remain private to the current process.
MAP_ANONYMOUS creates memory that is not backed by a file.
Passing NULL allows the kernel to choose an appropriate virtual address.

On success, mmap() returns a page-aligned, zero-initialized region of virtual memory.

If the mapping cannot be created, it returns MAP_FAILED. Rather than exposing Linux-specific error values to the allocator, the wrapper simply returns NULL, providing the same behavior expected from a typical allocation function.

Releasing memory is equally straightforward.

munmap() returns the mapped pages to the operating system. Unlike Windows, Linux requires the original allocation size when unmapping a region, which is why os_free() accepts both the pointer and the size.

Finally, os_page_size() queries the operating system using sysconf() instead of assuming a fixed page size. While 4096 bytes is common on modern desktop systems, other architectures may use different page sizes.

Windows Backend

src/os/windows.c

#ifdef _WIN32

#include "os.h"

#include <windows.h>

void *os_alloc(size_t size) {
  return VirtualAlloc(
    NULL,
    size,
    MEM_RESERVE | MEM_COMMIT,
    PAGE_READWRITE
  );
}

void os_free(void *ptr, size_t size) {
  (void)size;

  if (ptr == NULL) {
    return;
  }

  VirtualFree(ptr, 0, MEM_RELEASE);
}

size_t os_page_size(void) {
  SYSTEM_INFO info;
  GetSystemInfo(&info);

  return (size_t)info.dwPageSize;
}

#endif

Windows exposes virtual memory management through the VirtualAlloc() and VirtualFree() APIs.

Although the API differs from Linux, the overall idea is the same: request one or more pages directly from the operating system.

VirtualAlloc() combines two operations:

MEM_RESERVE reserves a range of virtual addresses.
MEM_COMMIT makes those pages immediately available for use.

Using both flags together gives the allocator writable, zero-initialized memory in a single call.

Unlike Linux, VirtualFree() does not require the allocation size when releasing memory. Windows keeps track of that information internally, so the wrapper simply ignores the unused size parameter while preserving the same cross-platform interface.

Retrieving the page size is handled through GetSystemInfo(), which fills a SYSTEM_INFO structure containing information about the running system, including the page size.

Although the Linux and Windows implementations use completely different operating system APIs, they expose the same three functions:

void *os_alloc(size_t size);
void os_free(void *ptr, size_t size);
size_t os_page_size(void);

From this point onward, the allocator no longer needs to care which operating system it is running on.

The platform-specific work ends here.

Everything that follows like block headers, free lists, splitting, coalescing, and the implementation of malloc() itself will be written entirely against this abstraction layer.

Step 3: Utility Functions

With the platform layer complete, the next step is building a few small helper functions that the allocator will rely on throughout the project.

These functions are not responsible for allocating memory. Instead, they provide common operations such as alignment, size comparisons, and block manipulation that will become useful once block headers and free lists are introduced.

src/utils.c

#include "allocator.h"

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

/* Alignment utilities */
size_t align_up(size_t value, size_t alignment) {
  return (value + alignment - 1) & ~(alignment - 1);
}

bool is_power_of_two(size_t value) {
  return (value != 0) && ((value & (value - 1)) == 0);
}

size_t max_size(size_t a, size_t b) {
  return (a > b) ? a : b;
}

/* Placeholder until BlockHeader exists */
bool blocks_are_adjacent(void *block1, void *block2) {
  (void)block1;
  (void)block2;
  return false;
}

Although this file is small, it introduces one of the most important ideas in allocator design: memory alignment.

Alignment

Modern processors expect many types of data to begin at addresses that are multiples of a specific value, typically 8 or 16 bytes on 64-bit systems.

Suppose a program requests:

malloc(3);

Returning exactly three bytes would leave the next allocation starting at an unaligned address.

Instead, allocators round allocations upward so every payload begins on the correct alignment boundary.

malloc(3)
      │
      ▼
Round up to 8 bytes
      │
      ▼
+--------+-----------+
| Header |  Payload  |
+--------+-----------+
      │
      ▼
Next allocation also begins on an aligned boundary

Proper alignment improves performance and is required by some processor architectures.

The helper responsible for this is align_up().

size_t align_up(size_t value, size_t alignment) {
  return (value + alignment - 1) & ~(alignment - 1);
}

Although the expression looks unusual, it performs two simple operations:

Add enough bytes to reach the next alignment boundary.
Clear the lower bits to round the value down to that boundary.

For example:

align_up(5, 8)  = 8
align_up(8, 8)  = 8
align_up(9, 8)  = 16

This works only when the alignment is a power of two.

To verify that assumption, the allocator includes another helper.

bool is_power_of_two(size_t value) {
  return (value != 0) && ((value & (value - 1)) == 0);
}

This relies on a common bit manipulation trick.

A power of two contains exactly one bit set.

If the result is zero, the value is a power of two.

The remaining helpers are much simpler.

max_size() returns the larger of two values and improves readability wherever block sizes need to be compared.

blocks_are_adjacent() is currently only a placeholder. Once block headers are introduced, it will determine whether two neighboring blocks can be merged during coalescing.

Step 4: Testing the Platform Layer

Before building the allocator itself, it is worth verifying that the platform abstraction layer behaves correctly.

At this stage, the goal is intentionally simple:

Query the system page size.
Request one page from the operating system.
Write data into that page.
Read it back.
Release the page.

If this works on both Linux and Windows, the allocator has a reliable foundation to build upon.

tests/test_os.c

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

#include "os/os.h"

int main(void) {
  printf("Testing OS abstraction layer...\n");

  size_t page_size = os_page_size();
  printf("Page size: %zu bytes\n", page_size);

  void *ptr = os_alloc(page_size);

  if (ptr == NULL) {
    fprintf(stderr, "Allocation failed!\n");
    return 1;
  }

  printf("Allocated %zu bytes at %p\n", page_size, ptr);

  const char *message = "Hello, Memory Allocator!";
  strcpy((char *)ptr, message);

  printf("Read back: \"%s\"\n", (char *)ptr);

  os_free(ptr, page_size);

  printf("Memory released successfully.\n");

  return 0;
}

The test is intentionally small.

No allocator has been implemented yet.

The only purpose is to verify that both platform backends expose identical behavior through the abstraction layer.

To simplify compilation, the project uses a small Makefile.

tests/Makefile

CC = gcc

CFLAGS = -Wall -Wextra -std=c11 -I../include -I../src

LDFLAGS =

UNAME_S := $(shell uname -s)

ifeq ($(UNAME_S),Linux)
  OS_BACKEND = ../src/os/linux.c
endif

ifeq ($(UNAME_S),Darwin)
  OS_BACKEND = ../src/os/linux.c
endif

ifeq ($(OS),Windows_NT)
  OS_BACKEND = ../src/os/windows.c
endif

all: test_os

test_os: test_os.c $(OS_BACKEND) ../src/utils.c
  $(CC) $(CFLAGS) -o $@ test_os.c $(OS_BACKEND) ../src/utils.c $(LDFLAGS)

clean:
  rm -f test_os

.PHONY: all clean

The Makefile selects the appropriate platform backend automatically.

Linux builds with linux.c.
Windows builds with windows.c.
macOS currently reuses the Linux backend because it also provides mmap().

Once built, run:

make
./test_os

A successful run should produce output similar to:

Testing OS abstraction layer...
Page size: 4096 bytes
Allocated 4096 bytes at 0x71002a37c000
Read back: "Hello, Memory Allocator!"
Memory released successfully.

At this point, the project can successfully communicate with the operating system, request pages, access them, and return them safely.

That is all the allocator needs before introducing its own memory management.

What's Next?

The platform abstraction layer is now complete.

The allocator can request pages from the operating system, determine the system page size, and release memory through a common interface that works on both Linux and Windows.

In the next part, those raw pages will become usable memory blocks.

We'll introduce block headers, define the allocator's internal metadata, and begin implementing the data structures that eventually power malloc(), calloc(), realloc(), and free().

Explore the project on GitHub