Problem set 1: Memory allocator

In this problem set, you’ll design and write a debugging memory allocator—a dropin replacement for malloc and free that:

  1. Tracks memory usage statistics.
  2. Reuses freed memory and avoids memory fragmentation.
  3. Catches common programming errors.

This year, we are breaking your work up into three phases that build on each other. Pset 1A will be discussed in class on Wednesday, September 9.

Interface

Dynamic memory allocation lets a running program access just the memory it needs. When a program needs more memory to accomplish some task, it asks for more memory; when done, it relinquishes the memory for other use. Dynamic allocation is a central feature of modern computer systems.

C-style dynamic memory allocation uses two basic functions, malloc and free.

void* malloc(size_t size)
Allocates size contiguous bytes of memory and returns a pointer to the first byte in that block. The returned memory is not initialized (it can contain anything). Returns nullptr if the allocation failed (because size was too big, or memory is exhausted, or for whatever other reason).
void free(void* ptr)
Frees a single block of memory previously allocated by malloc.

The basic rule of malloc and free is “one in, one out.”

Some notes on boundary cases:

Implementation

Fast malloc implementations work in batches: they obtain big memory buffers from the underlying operating system, then divide those buffers into blocks that are handed out in response to application malloc calls. Your turnin must be able to service malloc requests using a single 8 MiB buffer.

A buffer-based malloc implementation must track which parts of a buffer are allocated and which are free. This involves tracking metadata: the state of each part of the buffer, including the size of each allocated or free block. Fast allocators track much of this metadata internally—inside the allocation buffer itself—but your turnin can use external metadata instead, which stores this information in standard data structures like std::map.

Many malloc implementations also export statistics, including the number of allocations, the number of bytes currently allocated, and the number of failed allocations so far. Your turnin must track these statistics.

Some malloc implementations include integrated debugging and error checking, where common programming errors involving dynamic allocation are detected and reported. Your turnin must be able to detect some errors, including invalid and double frees.

Phase A: Tests

In the first week, we want you to design tests for a dynamic memory allocator, with maximum freedom, at the same time as you think about the eventual design of your memory allocator. The only constraints:

  1. The memory allocation functions are named m61_malloc and m61_free rather than malloc and free. (This avoids conflicts with the system’s allocator.)

  2. Memory allocated by m61_malloc can only be freed by m61_free—you can’t mix the m61 allocator with the system allocator.

  3. The functions otherwise behave like malloc and free and require the same behavior from their callers (e.g., “one in, one out”).

A good test is:

Each test should be an independent program that starts with #include "m61.hh". The test body should be in the main() function. If a test succeeds, main() should exit with status 0; if it fails, main() should exit with status 1.

Notes on exiting: By convention, a program that exits with status 0 has completed its task successfully. A program can exit with status 0 either by calling exit(0) or, more simply, by falling off the end of the main function. A program can exit with status 1 by calling exit(1), by calling abort(), or, best, by calling assert with a failing predicate. (For examples of assert see below, or read this.)

This initial phase is purposely vague. Testing some allocator functionality will require that you design interfaces we haven’t specified yet (how to return statistics, how to report a programming error). Use the Edboard to post your thoughts and comment on others’! Some simple example tests are below; as the week progresses, we’ll post more of our own tests too.

Phase 1A turnin (Tuesday September 8, 11:59pm): Post your tests publicly to Ed with a brief description. We’ll discuss in class.

Example tests

// Test: `m61_malloc(0)` returns a nonnull pointer like it’s supposed to
#include "m61.hh"
#include <cassert>

int main() {
    void* ptr = m61_malloc(0);
    assert(ptr != nullptr); // crash the program here unless `ptr != nullptr`
    assert(ptr); // This means the same thing!
}

// Test: Two `m61_malloc(0)` calls return distinct nonnull pointers
#include "m61.hh"
#include <cassert>

int main() {
    void* ptr1 = m61_malloc(0);
    void* ptr2 = m61_malloc(0);
    assert(ptr1 && ptr2);
    assert(ptr1 != ptr2);
}

// Test: We can allocate at least 7.9 mebibytes
#include "m61.hh"
#include <cassert>

int main() {
    void* ptr = m61_malloc((size_t) (7.9 * (1 << 20)));
}

Here’s a malloc implementation that should pass these tests (it’s the system allocator):

#ifndef M61_HH
#define M61_HH
#include <cstdlib>

inline void* m61_malloc(size_t sz) {
    return malloc(sz);
}

inline void m61_free(void* ptr) {
    free(ptr);
}

#endif

Here’s one that should fail them:

#ifndef M61_HH
#define M61_HH
#include <cstdlib>

inline void* m61_malloc(size_t sz) {
    return nullptr;
}

inline void m61_free(void*) {
}

#endif

Here’s an example run of the first test (saved in test01.cc) with the working allocator (saved in m61.hh):

$ c++ -o test01 test01.cc
$ ./test01
$

Here’s one with the failing allocator:

$ c++ -o test01 test01.cc
$ ./test01
test01: test01.cc:7: int main(): Assertion `ptr != nullptr' failed.
Aborted                    ./test01

(Note that a successful run prints nothing—is this unambiguous? How would you improve it?)

Notes

This lab was created for CS 61.