Dynamic Memory Allocator

This lab challenged me to implement a dynamic memory allocator for C programs, simulating the functionality of malloc, free, and (optionally) realloc. I explored core concepts of memory management, data structures, and algorithmic trade-offs. Here's how I approached and implemented the allocator step-by-step.

Learning Objectives

Build a dynamic memory allocator using an explicit free list.

Understand algorithmic trade-offs between utilization and throughput.

Enhance debugging skills and deepen my understanding of pointers, macros, and C structs.

1. Key Design Decisions

Explicit Free List: I implemented an explicit free list, which maintains a doubly linked list of free blocks. This approach enables efficient traversal and coalescing of adjacent free blocks.
LIFO Free Policy: New free blocks are inserted at the head of the free list for simplicity and improved cache locality.
Coalescing: I implemented a coalescing strategy to merge adjacent free blocks, reducing external fragmentation and improving memory utilization.

2. Core Functions

a. `mm_malloc`: Allocating Memory

Purpose:

The mm_malloc function allocates a memory block of the requested size, ensuring alignment and efficient use of the heap.

Key Code:

void* mm_malloc(size_t size) {
  size_t reqSize = 0;
  BlockInfo* ptrFreeBlock = NULL;
  size_t blockSize;

  if (size == 0) return NULL; // Ignore zero-size requests

  size += WORD_SIZE; // Account for the size header
  reqSize = ALIGNMENT * ((size + ALIGNMENT - 1) / ALIGNMENT);

  ptrFreeBlock = (BlockInfo*)searchFreeList(reqSize);

  if (ptrFreeBlock == NULL) {
    requestMoreSpace(reqSize);
    ptrFreeBlock = (BlockInfo*)searchFreeList(reqSize);
    if (ptrFreeBlock == NULL) return NULL; // Allocation failure
  }

  removeFreeBlock(ptrFreeBlock);
  blockSize = reqSize;

  // Split oversized blocks
  size_t remainingSize = SIZE(ptrFreeBlock->sizeAndTags) - blockSize;
  if (remainingSize >= MIN_BLOCK_SIZE) {
    BlockInfo* newFreeBlock = (BlockInfo*)UNSCALED_POINTER_ADD(ptrFreeBlock, blockSize);
    newFreeBlock->sizeAndTags = remainingSize | TAG_PRECEDING_USED;
    ptrFreeBlock->sizeAndTags = blockSize | TAG_USED;
    *(size_t*)UNSCALED_POINTER_SUB(UNSCALED_POINTER_ADD(newFreeBlock, remainingSize), WORD_SIZE) = remainingSize | TAG_PRECEDING_USED;
    insertFreeBlock(newFreeBlock);
  } else {
    ptrFreeBlock->sizeAndTags |= TAG_USED;
    BlockInfo* followingBlock = (BlockInfo*)UNSCALED_POINTER_ADD(ptrFreeBlock, SIZE(ptrFreeBlock->sizeAndTags));
    followingBlock->sizeAndTags |= TAG_PRECEDING_USED;
  }

  return UNSCALED_POINTER_ADD(ptrFreeBlock, WORD_SIZE);
}

Analysis:

Block Splitting: To reduce internal fragmentation, larger free blocks are split into smaller ones.
Alignment: Ensures proper memory alignment for all allocations.
Efficiency: Searching the free list and requesting more space if necessary keeps allocation fast while balancing memory use.

b. `mm_free`: Freeing Memory

Purpose:

Reclaims a block of memory, marks it as free, and coalesces it with adjacent free blocks.

Key Code:

void mm_free(void* ptr) {
  BlockInfo* block = (BlockInfo*)UNSCALED_POINTER_SUB(ptr, WORD_SIZE);
  BlockInfo* followingBlock = (BlockInfo*)UNSCALED_POINTER_ADD(block, SIZE(block->sizeAndTags));

  block->sizeAndTags &= ~TAG_USED;
  followingBlock->sizeAndTags &= ~TAG_PRECEDING_USED;

  *(size_t*)UNSCALED_POINTER_SUB(UNSCALED_POINTER_ADD(block, SIZE(block->sizeAndTags)), WORD_SIZE) = block->sizeAndTags;

  insertFreeBlock(block);
  coalesceFreeBlock(block);
}

Analysis:

Marking Free Blocks: The TAG_USED bit is cleared, and the footer is updated to mark the block as free.
Coalescing: Adjacent free blocks are merged to minimize fragmentation and maintain a cleaner free list.

c. `coalesceFreeBlock`: Merging Free Blocks

Purpose:

Merges a free block with its neighboring free blocks, reducing fragmentation.

Key Code:

static void coalesceFreeBlock(BlockInfo* oldBlock) {
  BlockInfo* blockCursor = oldBlock;
  BlockInfo* freeBlock;
  size_t oldSize = SIZE(oldBlock->sizeAndTags);
  size_t newSize = oldSize;

  while ((blockCursor->sizeAndTags & TAG_PRECEDING_USED) == 0) {
    size_t size = SIZE(*((size_t*)UNSCALED_POINTER_SUB(blockCursor, WORD_SIZE)));
    freeBlock = (BlockInfo*)UNSCALED_POINTER_SUB(blockCursor, size);
    removeFreeBlock(freeBlock);
    newSize += size;
    blockCursor = freeBlock;
  }
  BlockInfo* newBlock = blockCursor;

  blockCursor = (BlockInfo*)UNSCALED_POINTER_ADD(oldBlock, oldSize);
  while ((blockCursor->sizeAndTags & TAG_USED) == 0) {
    size_t size = SIZE(blockCursor->sizeAndTags);
    removeFreeBlock(blockCursor);
    newSize += size;
    blockCursor = (BlockInfo*)UNSCALED_POINTER_ADD(blockCursor, size);
  }

  if (newSize != oldSize) {
    removeFreeBlock(oldBlock);
    newBlock->sizeAndTags = newSize | TAG_PRECEDING_USED;
    *(size_t*)UNSCALED_POINTER_SUB(blockCursor, WORD_SIZE) = newSize | TAG_PRECEDING_USED;
    insertFreeBlock(newBlock);
  }
}

Analysis:

Preceding Blocks: Merges free blocks before the current block by checking the preceding block’s TAG_PRECEDING_USED status.
Following Blocks: Merges subsequent free blocks by iterating through adjacent blocks until a used block is encountered.
Efficiency: Ensures that large free blocks are created whenever possible, improving allocation success rates.

d. `requestMoreSpace`: Expanding the Heap

Purpose:

Requests additional heap space from the memory system when no suitable free block is found.

Key Code:

static void requestMoreSpace(size_t reqSize) {
  size_t pagesize = mem_pagesize();
  size_t numPages = (reqSize + pagesize - 1) / pagesize;
  BlockInfo* newBlock;
  size_t totalSize = numPages * pagesize;

  void* mem_sbrk_result = mem_sbrk(totalSize);
  if ((size_t)mem_sbrk_result == -1) {
    printf("ERROR: mem_sbrk failed in requestMoreSpace\n");
    exit(0);
  }

  newBlock = (BlockInfo*)UNSCALED_POINTER_SUB(mem_sbrk_result, WORD_SIZE);
  newBlock->sizeAndTags = totalSize | TAG_PRECEDING_USED;
  *((size_t*)UNSCALED_POINTER_ADD(newBlock, totalSize - WORD_SIZE)) = totalSize | TAG_PRECEDING_USED;
  insertFreeBlock(newBlock);
  coalesceFreeBlock(newBlock);
}

Analysis:

Page Alignment: Requests memory in multiples of the system page size to optimize system-level performance.
Integration with Free List: Adds the newly allocated memory to the free list and immediately attempts to coalesce it with adjacent blocks.

3. Testing and Debugging

Tools Used:

Trace Files: Verified correctness using provided trace files like short1-bal.rep and short2-bal.rep.
mdriver Utility: Used the driver program to evaluate performance and utilization.

Challenges:

Balancing utilization and throughput was tricky. Using a LIFO policy improved throughput, while coalescing helped with utilization.
Debugging the free list and coalescing required careful pointer arithmetic and boundary checks.

4. Lessons Learned

Memory Management: Understanding low-level memory structures and alignment constraints deepened my appreciation for efficient memory use.
Algorithm Trade-Offs: Balancing competing metrics like fragmentation, throughput, and memory usage was a critical part of the lab.
C Programming: Working extensively with pointers, structs, and macros enhanced my proficiency in C.