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:

Tracks memory usage statistics.
Reuses freed memory and avoids memory fragmentation.
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.”

A block of dynamically-allocated memory remains active until it explicitly freed with a call to free.
A successful call ptr = malloc(sz) returns a pointer to “new” dynamically allocated memory. This means that the sz bytes of storage starting at address ptr do not overlap with any other active objects, including the program’s code and global variables, its stack, and any other active dynamically allocated memory.
The pointer argument in free(ptr) must either be nullptr or an active pointer to dynamically-allocated memory. In particular:
1. It is not OK to call free(ptr) if ptr points to the program’s code, its global variables, or the stack. (See Segments)
2. It is not OK to call free(ptr) unless ptr was returned by a previous call to malloc.
3. It is not OK to call free(ptr) if the block of memory at ptr is currently inactive because it was already freed.
All three of these errors are called invalid frees. The third error is common enough to have its own name; it is a double free.
It is illegal to access inactive dynamically-allocated memory. Once a block is freed, any examination or modification of the data in that block causes undefined behavior.

Some notes on boundary cases:

free(nullptr) is allowed. It does nothing.
malloc(0) is allowed. It should return a non-null pointer to a unique active allocation. (This means, for example, that if two calls to malloc(0) return non-null pointers, and neither allocation is freed, then those pointers must be different. Although the standard allows malloc(0) to return nullptr, your implementation should not.)
malloc(sz) returns memory whose alignment works for any object. On 64-bit x86 machines, this means that the address value returned by malloc() must be evenly divisible by 16. (That is, alignof(std::max_align_t) == 16 on x86-64; see this reference page for more info on std::max_align_t.)

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.

Part 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:

The memory allocation functions are named m61_malloc and m61_free rather than malloc and free. (This avoids conflicts with the system’s allocator.)
Memory allocated by m61_malloc can only be freed by m61_free—you can’t mix the m61 allocator with the system allocator.
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:

Reliable: it succeeds for every good implementation. A test that assumed the memory buffer had a fixed address (like 0x10008000) would not be reliable: memory buffer location can vary.
Non-redundant: it fails for at least one realistic bad implementation. A test that asserted that m61_malloc(100000000000) returns nullptr is not that valuable; we require that m61_malloc can work with a single 8 MiB buffer, and no laptop has 100 GB of memory.
Powerful: it would fail for many bad implementations.
Fast: it succeeds or fails quickly.
Unambiguous: it reports clearly whether it succeeded or failed.

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 terminate with an error status.

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 terminate with an error status 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?)

Part B: Allocator

In the second week, we want you to write an allocator that passes as many of your own tests as possible. This portion of your Pset 1 work is due on Friday September 18 at 11:59pm.

Your allocator must support the m61_malloc, m61_free, and m61_get_statistics interfaces defined in pset1b/m61.hh.
Your allocator must fit entirely within the m61-pset.cc file (so you’ll build a test with make M61=pset TESTNAME).
Your allocator must serve all requests from a single 8 MiB buffer. See m61-once.cc for an example.
Your allocator must support memory reuse.
Your allocator must use memory efficiently (it can’t use the whole buffer for a single 1-byte allocation).
Your allocator must keep correct statistics (total_count, total_bytes, active_count, and active_bytes).
Your allocator must detect some invalid frees, double frees, and wild writes. (It is impossible to detect all invalid frees, double frees, and wild writes at the allocator level, but your allocator must detect the most obvious examples, like a free of a stack pointer or an attempt to free a pointer that was just freed. The more misbehavior you can detect the better.)

We recommend students start with external metadata, but we also recommend that students experiment with internal metadata. You can create your own m61-internal.cc file with internal metadata and test it with make M61=internal TESTNAME.

Testing

You must test your allocator yourself, and coming up with good tests and a good testing strategy is essential for this part of the pset. Luckily, you have already written some tests, and your classmates have written many more that you can use!

Your turnin must include default tests, of the kind described above and supported by our Makefile. We ship a few default tests; you should add more.

Default tests are in files named pset1b/<WHATEVER>NNN.cc (where NNN is a three-digit number), and in files named pset1b/t/<WHATEVER>.cc (no numbers required). So pset1b/test000.cc is a default test, and so is pset1b/t/my-magic-test.cc.
A default test must contain a main function and must successfully link against any m61 allocator.
When run at the command line (./test000 or ./t/my-magic-test), a default test must either exit(0) on success or terminate abnormally on failure. It may print additional information, but failures must be detectable through exit status alone.
The pset1b makefile can build any default test; make without arguments builds them all. make check builds and runs them all, exiting on the first error. You can also run make check-TESTNAME.

If you want, you can also implement special tests. Special tests do not need to link against any m61 allocator. For instance, a special test might access internal allocator debugging information, or it might request a different response for invalid frees.

Put special tests in files named pset1b/tt/<WHATEVER>.cc.
make special builds all special tests, and make check-special builds and runs them, exiting on the first error.

Why special tests? Tests can be easier to write when a library offers special test-mode behavior. In this pset, a concrete example is testing invalid frees. When a debugging allocator detects serious user error, it should call abort(), which terminates the program abnormally. In this case, an error termination is what you want. But that conflicts with the default testing rules, which say that non-zero exit status means the test failed! Students worked around this using fork, which creates a new process:
int main() {
    if (fork() == 0) { // create child process
        int x = 42;
        m61_free(&x);  // child calls invalid free function, m61_free calls abort, then child crashes
        _exit(0);      // should never reach here
    }
    // So the child process exits with status 0 on *failure*, and other status on success.

    int status;
    wait(&status);       // find out child’s exit status
    assert(!WIFEXITED(status) || WEXITSTATUS(status) != 0); // assert that child did not exit with status 0
    // So the parent process exits with status 0 on *success* -- clever!
}
That works fine, but it’s a little slow (process creation is slow) and wordy. This would be simpler:
int main() {
    m61_set_error_status(0);   // hypothetical test seam: exit with status 0 on error (don't abort)
    m61_free(nullptr);         // do not cause error
    assert(true);              // ok so far
    m61_free(&main);           // invalid free -- should exit *with status 0* thanks to seam
    assert(false && "invalid free not detected");
}
The m61_set_error_status function is called a test seam: a function that changes behavior to make testing easier.

Test seams aren’t allowed in default tests (which must work against any allocator), but they’re allowed in the special test area.

Turnin

Check in your code to GitHub by the deadline, and check on the grading server that your tests compile there.

Part C: Torture tests

Don’t worry, you aren’t going to be tortured. This final portion of your Pset 1 work is due on Sunday September 27 at 11:59pm.

In the third week, we’re distributing our own torture tests to exercise your allocator, including some tests that evaluate allocator performance. Run git pull handout main; make M61=pset check-torture to merge the torture tests and run your code against them.

We have modified GNUmakefile and utils.hh to add more functionality. If you also edited these files, you may need to resolve conflicts before going further.

Run make check-torture/01 to run a specific test.
The torture tests are generally ordered by increasing difficulty, but you can attack them in any order you want. Read pset1b/torture/README.md to get situated. Each torture test’s code starts with a comment describing how it works.
You don’t need to pass all of them. torture/33, for example, is pretty nasty. In the performance tests, external metadata will generally run slower than internal metadata, and tests 28 and 29 may cause trouble for the simplest free list designs. Our goal is to provide you with a space to learn and some interesting tests to flex against. Remember that problem set scores are downweighted this year, remember that correctness is more important than speed, and don’t drive yourself crazy.

You can run make -k check-torture to run all the torture tests, rather than stopping at the first failure.
Our Makefile builds your code by default with sanitizers enabled. A sanitizer is a compiler feature that adds extra checking code to your program. Sanitizers can detect many kinds of programming error before they cause security holes, and they’re incredible friends to programmers. Your allocator should pass all of the tests without causing a sanitizer report. Even the error-detection tests (17–20 + 32-33), which involve user misbehavior, should not cause sanitizer errors within your code.
Performance tests: Tests 21–31 measure aspects of allocator performance including speed, fragmentation, and memory overhead. We hope to post a leaderboard! That leaderboard will be compiled with sanitizers off (make SAN=0 check-torture), because sanitizers can have high cost, but your code must still run clean with sanitizers.
Allocators have inherent tradeoffs; for instance, minimizing your allocator’s overhead will make it harder to detect wild writes. You don’t have to find the best tradeoff (there isn’t one), but you should have a clear explanation for why you chose your design.
Error messages: The error-detection tests print out any error messages generated by your allocator. Though there are no specific requirements on error messages, we’ll attempt to collate them and highlight the best ones. A useful error message would be clear, specific, and user-focused: for instance, Double free of pointer 0x9324771a0. Less useful: some gobbledegook about your internal implementation, like Assertion failed: (h && checkh(h) && h->magicd != magicf && checkt(h2t(h))), function m61_free, file m61-staffi.cc, line 209. You could even add a std::source_location argument to the m61_malloc and m61_free functions to get more precise locations for error messages!
Your allocator should not cheat. Don’t try to confuse timing harnesses by printing crafted output, for example. (Presented without comment!)

Turnin

Check in your code to GitHub by the deadline, and check on the grading server that your tests compile there.

Notes

This lab was created for CS 61.