Memory Allocator

This is a simple reimplementation of the memory allocation system (malloc, free, realloc), similar to the one provided on the C library.

It was implemented as an exercise for better understanding the underlying process of dynamic memory allocation and how it operates internally.

The initial code is part of the Malloc Lab and loosely follows the section on Dynamic Memory Allocation as described on the book Computer Systems's - A Programmers Perspective at Chapter 9: Virtual Memory.

The main implementation is on file mm.c. The other files are provided from the handouts for the lab. If you want to try it yourself, get it here.

Features

• Using implicit free lists.
• Applying "Next fit" strategy.
• Use of boundary tags (footer).
• Efficient method to coalesce free blocks (constant time, coalesce adjacent blocks).
• realloc shrinks/grows in-place when possible.

Evolution

This project evolved through a few iterations to improve performance and memory utilization:

• mm-first.c: Initial implementation using an implicit free list with headers only, a "First fit" strategy, and inefficient coalescing (full heap scan only when malloc failed).
• mm-second.c: Introduced boundary tags (header + footer) for improved coalescing after free.
• mm-third.c: The current iteration (mm.c), employing a "Next fit" strategy and optimized in-place realloc capabilities.

Performance

Passes all tests/traces (but it's much slower than glibc's malloc!):

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   91%    5694  0.001719  3312
 1       yes   92%    5848  0.001071  5459
 2       yes   95%    6648  0.004040  1646
 3       yes   97%    5380  0.004320  1245
 4       yes  100%   14400  0.000190 75670
 5       yes   91%    4800  0.006423   747
 6       yes   89%    4800  0.005646   850
 7       yes   55%   12000  0.014274   841
 8       yes   51%   24000  0.009428  2545
 9       yes   27%   14401  0.075906   190
10       yes   40%   14401  0.000219 65788
Total          75%  112372  0.123237   912

Perf index = 45 (util) + 40 (thru) = 85/100

Requirements

• Developed/tested on Linux
• GCC
• Make

Building and running

$ make clean
$ make mdriver                # compile the test runner
$ make test                   # run a simple test
$ make traces                 # run many tests (as seen above)
$ ./mdriver -f test-file.rep  # check src/README for more options