Memory Allocator Project

Objectives

• Explore the fundamentals of memory management by implementing custom versions of malloc(), calloc(), realloc(), and free().
• Utilize memory management syscalls in Linux: brk(), mmap(), and munmap().
• Analyze and optimize memory allocation performance and reduce fragmentation.

Project Overview

This project involves building a minimalistic memory allocator to manually manage virtual memory. The goal is to create a reliable library that supports explicit allocation, reallocation, and initialization of memory, while optimizing memory usage and reducing fragmentation.

Project Structure

The project is organized as follows:

• src/ contains the implementation of the memory allocator.
• tests/ contains test cases and scripts to verify the functionality.
• utils/ includes osmem.h for the library interface, block_meta.h for metadata structures, and a printf() implementation that does not use the heap.

The test suite dynamically links with the library (libosmem.so) and verifies correctness by comparing syscall sequences with reference outputs.

API

1. void *os_malloc(size_t size)

   Allocates size bytes and returns a pointer to the allocated memory. Small allocations use brk() while larger chunks use mmap(). Memory is uninitialized. Passing 0 returns NULL.

2. void *os_calloc(size_t nmemb, size_t size)

   Allocates memory for an array of nmemb elements of size bytes each. Small allocations use brk(), larger ones use mmap(), and memory is zero-initialized. Passing 0 for either parameter returns NULL.

3. void *os_realloc(void *ptr, size_t size)

   Resizes the memory block at ptr to size bytes. The block is expanded in-place if possible; otherwise, a new block is allocated and data is copied. Passing NULL behaves like os_malloc(size). Passing 0 behaves like os_free(ptr).

4. void os_free(void *ptr)

   Frees memory previously allocated with os_malloc(), os_calloc(), or os_realloc(). Memory is marked as free for reuse; munmap() is used for mapped blocks.

Implementation Notes

• Memory blocks are tracked using a doubly linked list (struct block_meta) and aligned to 8 bytes.
• The allocator supports block splitting to reduce internal fragmentation and block coalescing to reduce external fragmentation.
• The best-fit strategy is used to select free blocks for allocation.
• Heap preallocation (e.g., 128 KB) reduces the number of syscalls for small allocations.
• Error handling is included for all syscalls.

Building and Testing

• Build the library (libosmem.so) using make in src/.
• Automated tests verify allocation correctness, block reuse, splitting, coalescing, and realloc behavior.
• Memory leaks and system call correctness are checked using scripts based on ltrace.

Resources

• "Implementing malloc" slides by Michael Saelee
• Malloc Tutorial