Memory Allocator

Summary

This project was created for my Operating Systems class at the University of San Francisco.

The goal of this project was to implement a memory allocator similar to the C library's malloc command. The memory allocator would be able to allocate, free, and reallocate memory as a replacement to malloc. The allocator optimizes memory use and runtime by using the mmap system call for large memory blocks that will be split into smaller blocks and distributed to successive allocations. In this way, the expensive system call will be used less often.

Managing Memory

Memory is stored in blocks split into a header storing metadata and the actual data itself. The metadata in the header stores the memory locations of the previous and next memory blocks, creating a linked list of memory locations.

Tracking Memory

To track if any space is available in the memory block, the allocator has a list of all used and freed memory locations. When allocating memory, the freed memory list is checked for a block of memory that will fit. If a block can be found in the freed memory list, the allocator can avoid making a system call for more memory. When freeing memory, the allocator will add it to the freed memory list.

Allocating Memory

The memory allocator allocates memory in 4096 byte blocks to minimize system calls. The blocks are split into smaller partitions to be used when needed. The allocator only needs to make another system call for additional memory when the current block runs ouf of space.

Freeing Memory

When freeing a memory block, the block is marked as free and merged with any adjacent free memory blocks. If the scribble feature is enabled, the memory block will have its contents overwritten with blank values.

Reallocating Memory

To reallocate memory, the allocator checks if the memory block can be expanded into adjacent blocks. If there is no space available, the allocator can create a new, larger block and copy the contents over. If the memory block is being made smaller, the trimmed space can be freed.