Skip to content

README.MD

Latest commit

 

History

History
101 lines (77 loc) · 3.61 KB

README.MD

File metadata and controls

101 lines (77 loc) · 3.61 KB

malloc

Educational implementation of a dynamic memory allocator in the spirit of malloc/free. The goal of this project is to gain a deep understanding of how a memory allocator works (heap organization, allocation strategies, fragmentation, coalescing, etc.), rather than to provide a production-ready replacement for glibc’s malloc(3).

Project goals

  • Reproduce the behavior of a user-space allocator (malloc/realloc/free).
  • Handle fragmentation and coalescing of free blocks.
  • Manipulate the heap directly mmap.

This project is primarily intended for educational use by students in systems programming, low-level C programming, or security.

Build

git clone https://github.com/A1astar/malloc.git
cd malloc

make          # builds the library
make test     # builds test binary
make fclean    # cleanup

Usage

As a library (LD_PRELOAD or explicit linking)

LD_PRELOAD=./libft_malloc.so ./my_prorgam

Explicit linking at compile time:

gcc -o program program.c -L. -lft_malloc

Allocator architecture / design

  • Internal block structure
    • Header: single size_t metadata (size + allocated flag in LSB)
    • Block alignment: 16 bytes
    • Payload immediately follows header (offset by align16(sizeof(size_t)))
    • No explicit prev/next pointers — blocks found by traversing via size
  • Heap management
    • Uses mmap exclusively (no sbrk)
    • Three allocation strategies:
      • TINY: blocks ≤ 1024 bytes → pre-allocated arena
      • SMALL: blocks ≤ 4096 bytes → pre-allocated arena
      • LARGE: blocks > 4096 bytes → individual mmap per allocation
    • Arena size: 100 blocks × max_block_size + arena header, page-aligned
  • Free-block organization
    • Implicit free list (no explicit links between free blocks)
    • Traversal by size field embedded in each block
    • Arena tracks max_available (largest free block) for quick fit checks
    • Circular doubly linked list of arenas per type (TINY/SMALL)
    • Separate circular doubly linked list for large mmap allocations
  • Allocation strategy
    • First fit within arenas
    • Arena selection: search existing arenas for sufficient max_available, else create new arena
    • Block splitting: if found block > requested size, create new free block with remainder
  • Coalescing
    • Triggered on free() after marking block as free
    • Forward coalescing only (merges consecutive free blocks)
    • Updates arena's max_available during merge
    • Empty arenas (nb_alloc == 0) are unmapped, unless it's the last one of his kind
  • Security / robustness
    • Thread-safe: global pthread_mutex_t protects all operations
    • Validates pointers via is_from_current_allocator() before freeing
    • LSB flag prevents double-free (checks allocated bit)
    • Bounded arena traversal (stops at arena boundaries)

Tests and validation

  • Command to run tests:

    make test
./malloc_test

References and documentation

One Heap to malloc them all, One Heap to free them, One Heap to coalesce, and in the memory bind them...