Hisho

Memory allocators written in C for learning purposes.

Run

make
./hisho_test
make clean

Implementations

Buddy Allocator

• Code: src/hisho_buddy.h src/hisho_buddy.c
• Description:
  • A buddy memory allocator
  • Implemented using an array of doubly linked lists, each representing a level
  • On free, if a block's buddy is also free, a block and its buddy will merge into a free block twice their size.
  • Each block has an overhead of 16 bytes for its header.
  • Written with the help of resources listed in #Resources.
• Pros:
  • Farily simple implementation
  • Avoids external fragmentation
  • Freeing memory is fast
  • Memory blocks are word aligned
• Cons:
  • 16 byte overhead due to header size
  • Internal fragmentation due to:
    • All block sizes being a power of 2
  • Fixed memory size set at compile time (#4)
• Usage:

  // alloc
  char str[] = "hisho";
  char *p = (char *)hisho_buddy__alloc(sizeof(str));
  memcpy(p, str, sizeof(str));
  
  // free
  hisho_buddy__free(p);

• Debug:

  // Print blocks, by their size, in all free lists.
  hisho_buddy__print_free_lists(stdout);

  Level 0:
  Level 1: 512
  Level 2: 256
  Level 3: 128
  Level 4: 64
  

• Todo
  • #2 Block size index can be optimized
  • #3 Block free index can be optimized
  • #4 Support setting the buddy allocator size at runtime

Dynamic memory allocator with 'first fit' strategy

• Code: src/hisho_ff.h src/hisho_ff.c
• Description:
  • A storage allocator implemented with a linked list that allocates blocks using the 'first fit' strategy.
  • Each block has an overhead of 16 bytes for its header.
  • On free a block will coalesce with the next block if it's unused, but not the previous block.
  • All block sizes are a multiple of the block header size for alignment purposes.
  • Written with the help of resources listed in #Resources.
• Pros:
  • Simple implementation
  • Avoids external fragmentation to a certain degree
  • Memory blocks are word aligned
• Cons:
  • 16 byte overhead due to header size (todo)
  • Internal fragmentation due to:
    • block sizes being a miltiple of the header size
  • External fragmentation due to:
    • simplicity of first fit strategy
    • coalescing only occuring with next block (todo)
  • Fixed memory expansion size set at compile time (todo)
• Usage:

  // alloc
  char str[] = "hisho";
  char *p = (char *)hisho_ff__alloc(sizeof(str));
  memcpy(p, str, sizeof(str));
  
  // free
  hisho_ff__free(p);

• Debug:

  // Print a table of all blocks and their properties
  hisho_ff__print_blocks(stdout);
  
  // Print stats about the allocator
  hisho_ff__print_stats(stdout);

  Blocks
          Header          Units           Size            Used            Next            Chars
          0x1059bc420     0               0               1               0x1092e6000
          0x1092e6000     1               16              1               0x1092e6030     hisho
          0x1092e6030     1020            16320           0               0x0
  
  Stats
          Header U        Buffer U        Free U          Total U         Total S
          2               1               1020            1023            16368
  

• Todo
  • Add functionality to coalese with prev block
  • Reduce size of header to sizeof(size_t) instead of 2*sizeof(size_t)
    • Encode is_used into u_size's first bit
  • Allow option to initalize allocator in order to set parameters like expansion size.

Static memory allocator with stack

• Code: src/hisho_s.h src/hisho_s.c
• Description:
  • A rudimentary storage allocator that uses a LIFO queue (stack) to manage memory.
  • Free calls must be made in opposite order to the alloc calls.
  • Memory is fixed in size and stored in a static variable (data segment of virtual address space of program).
  • Written with the help of resources listed in #Resources.
• Pros:
  • Very simple implementation
  • No fragmentation since data stored sequentially
• Cons:
  • Fixed size that must be set at compile time
  • Can only free last allocation
  • Wastes unused memory space
• Usage:

  // alloc
  char str[] = "hisho";
  char *p = hisho_s__alloc(sizeof(str));
  memcpy(p, str, sizeof(str));
  
  // free
  hisho_s__free(p);

• Debug:

  // Print memory and head pointer
  hisho_s__print();

  [hisho       ]
  [     ^      ]
  

Resources

• Books
  • K&R: The C Programming Language. 2nd Edition
  • Game Programming Patterns: Optimization Patterns: Data Locality
• Articles
  • Wikipedia: Memory Management
  • Wikipedia: Buddy Memory Allocation
  • Wikipedia: CPU cache
  • Data alignment: Straighten up and fly right
  • Writing a memory manager
• Blog Posts
  • Allocation Adventures 1: The DataComponent
  • Allocation Adventures 2: Arrays of Arrays
  • Allocation Adventures 3: The Buddy Allocator
  • angrave/SystemProgramming: Memory, Part 1: Heap Memory Introduction
  • angrave/SystemProgramming: Memory, Part 2: Implementing a Memory Allocator
  • What a C programmer should know about memory
• Stack Overflow
  • Explain this implementation of malloc from the K&R book
• Videos
  • Code for Game Developers - Anatomy of a Memory Allocation
  • Ryan Zezeski on Memory by the Slab: The Tale of Bonwick's Slab Allocator
  • Handmade Hero Day 157 - Introduction to General Purpose Allocation

Namesake

"hishoghutyun" (հիշողություն) means "memory" in Armenian. Hisho is short for that :)