Problem set 1: Memory allocator

Goal

Programming almost always requires the allocation and deallocation of dynamic memory. Dynamic allocation lets us give each program just as much memory as it requires. But how do memory allocators work?

In this problem set, you will write your own debugging memory allocator. We give you a simple allocator that never reuses freed memory. You will change the allocator to:

  1. Track memory usage statistics.
  2. Reuse freed memory and avoid memory fragmentation.
  3. Catch common programming errors, including boundary write errors, invalid frees, and double frees.
  4. Store allocation metadata directly inside the allocated memory.

The handout code for this problem set is in the pset1 directory. This contains a skeleton memory allocator and many test programs. Your code will go in pset1/m61.cc.

Mechanics

At a high level, this problem set has several goals.

Collaboration

This problem set is subject to the CS 61 collaboration policy. Do not use solutions you find on the web, and don’t ask anyone else, human or not, to do your work for you.

Getting the code

Problem sets are released through GitHub Classroom. Our GitHub organization is “cs61”. Problem sets will be released using the cs61/cs61-f23-psets repository.

Follow the GitHub setup instructions to obtain your own personal GitHub problem sets repository. (You may have already done this for Pset 0.) Then, from your repository directory, run git pull handout main to obtain pset 1, and git push to save the results in your GitHub. This should create a pset1/ subdirectory that contains your handout code.

Planning, coding, and testing

Similar to real-world programming tasks, the problem sets in this class reward incremental work and test-driven development. Our handout code comes with many tests, and our make check targets run your code against all those tests in order. It’s a good idea to work on the tests in order: get the simple stuff working, then gradually add more complex functionality.

The make check commands will report when the actual output of a test differs from the expected output, stopping on the first failed test. To check a single test or a range of tests, try make check-N, as in make check-1 or make check-1-10. If you want to see the full output of a test, run that test on the command line using ./testNUMBER. Some examples:

$ make check-1
  COMPILE m61.cc
  COMPILE hexdump.cc
  COMPILE test01.cc
  LINK test01
test01 FAIL: Unexpected output starting on line 1
  test01.cc:11: Expected `alloc count: active          0   total          0   fail          0`
  output:1:          Got `alloc count: active 18446744073709551615   total 18446744073709551615   fail 18446744073709551615
                          alloc size:  active 18446744073709551615   total 18446744073709551615   fail 18446744073709551615`
$ make clean
  CLEAN
$ make test01
  COMPILE m61.cc
  COMPILE hexdump.cc
  COMPILE test01.cc
  LINK test01
$ ./test01
alloc count: active 18446744073709551615   total 18446744073709551615   fail 18446744073709551615
alloc size:  active 18446744073709551615   total 18446744073709551615   fail 18446744073709551615

Getting started

A graduated submission process will encourage you to get started on the pset early.

  1. Commit and upload check-in #1 to the grading server by midnight on Sunday 9/17 . This check-in should contain your work for at least phase 1 (i.e. passing tests 1-20). Name your commit "checkin 1".

  2. Commit and upload check-in #2 to the grading server by midnight on Friday 9/22 . This check-in should contain your work for at least phases 1 through 2 (i.e. passing tests 1-32). Name your commit "checkin 2".

    Each check-in is worth 2.5 pts for completion. You will not recieve feedback on it. Late hours may not be applied to check-ins.

  3. The complete problem set is due by Friday 9/29 .

It is important to get started early—this problem set is not trivial. Giving yourself as much time as possible to think, code, debug, and talk to peers and course staff will help you learn the most, and minimize stress.

If you join the course late, you will be excused from any check-in dates that occured before you joined the class. Include in your README.md: "I joined the course late on MM/DD, please excuse me from check-in #X."

Turnin

You will turn in your code using Git. In the pset1/ subdirectory, you MUST include two text files called README.md and AUTHORS.md. The README.md file will include any extra credit attempted and comments for graders. The AUTHORS.md file should list your names as well as any other collaborators and citations. (Just list “None” if you have none.)

Your submission will not be graded until you configure the grading server. Log in and enter your GitHub username and repository URL. Verify that all tests that you expect to pass continue to pass on the grading server.

If you enrolled in the course on or before 9/10, you should have received an email with your login credentials for the grading server. If you did not receive an email, check your spam folder. If you have more than one Harvard email address, check all of them. If you still don't find an email from noreply@cs61.seas.harvard.edu, please send an email cs61-staff@g.harvard.edu.

If you joined the course after 9/10, please send an email to cs61-staff@g.harvard.edu so that we can make a grading server account for you.

Grading components:

  1. Tested allocator functions (the test programs we hand out, plus possibly others). If running make check reports All tests succeeded! you’ve probably got all these points.
  2. Coding style. Remember to document your metadata.
  3. Completion points for the two intermediate check-ins.

Memory allocation in C

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

void* malloc(size_t size)
Allocates size bytes of memory and returns a pointer to it. 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). If size == 0, may return nullptr or a unique allocation.

void free(void* ptr)
Free a single block of memory previously allocated by malloc.

The rules of malloc and free are simple: Allocate once, then free once.

Some notes on boundary cases:

In addition to malloc(), C supports another memory allocation function:

void* calloc(size_t count, size_t sz)
Allocates memory for an array of count objects, each with size sz. The returned memory is set to zero.

Here’s a simple implementation of calloc built using malloc. (But note that the implementation is buggy! Can you see the bug?)

void* calloc(size_t count, size_t sz) {
    void* ptr = malloc(sz * count);
    if (ptr != nullptr) {
        memset(ptr, 0, sz * count);     // clear memory to 0
    }
    return ptr;
}

Memory allocation in C++

Most dynamic memory allocation in C++ happens via the operators new and delete (or, for arrays, new[] and delete[]), rather than via direct calls to malloc and free. Nevertheless, the C++ implementations of new and delete call functions like malloc and free under the hood.

new and new[] can also initialize the returned memory, ensuring that the memory holds valid objects of the specified type. For example, the code int* arr = new int[3]{42,43,44} both allocates memory for a new array and also sets the initial element values to 42, 43, and 44 respectively.

C++ containers and other helper classes can be configured to allocate memory via a user-provided allocator instead of the default allocators. Check out test18 and test19 to see how this works.

Starting point

You’ll implement the allocator functions called m61_malloc, m61_free, and m61_calloc. These functions behave like malloc, free, and calloc, respectively, but they allocate memory out of a fixed-size buffer.

In our handout code, the m61 allocator never reuses memory. It obtains an 8-megabyte block of memory from the operating system at initialization time; the default_buffer.buffer variable points to the first byte in this block. A call to m61_malloc(sz) returns the next sz bytes in the block (default_buffer.pos keeps track of how much data has been allocated so far). m61_free does nothing, so once the initial 8 megabytes have been used, the allocator runs out of space. As the problem set goes on, you will implement space reuse for this allocator.

The m61_ function specifications are analogous to their standard counterparts, but m61_ and standard memory allocations are not interchangeable. For instance, memory allocated by m61_malloc must be freed by m61_free, and memory allocated by malloc must not be passed to m61_free.

Phase 1: Statistics (test01–test20)

In the first phase, you’ll track simple statistics about allocations, avoid some pitfalls of C++ arithmetic, and fix a bug or two in the existing m61_malloc implementation.

Implement the function:

m61_statistics m61_get_statistics()
Returns a structure containing information about memory allocations so far.

The m61_statistics structure is defined like this:

struct m61_statistics {
    unsigned long long nactive;           // number of active allocations [#malloc - #free]
    unsigned long long active_size;       // number of bytes in active allocations
    unsigned long long ntotal;            // number of allocations, total
    unsigned long long total_size;        // number of bytes in allocations, total
    unsigned long long nfail;             // number of failed allocation attempts
    unsigned long long fail_size;         // number of bytes in failed allocation attempts
    uintptr_t heap_min;                   // smallest address in any region ever allocated
    uintptr_t heap_max;                   // largest address in any region ever allocated
};

You will also need to change the m61_malloc and m61_free functions to keep track of these statistics.

When you finish Phase 1, your code should track all of these statistics except for active_size, which you will tackle in Phase 2. You will also harden your code against several common errors.

Run make check to test your work. You’ll want to examine the test programs to figure out what they’re doing and what output is expected. You will notice some comments at the end of the file, such as this in test01.cc:

//! alloc count: active          0   total          0   fail          0
//! alloc size:  active          0   total          0   fail          0

These lines define the expected output for the test. The make check command checks your actual output against the expected output and reports any discrepancies. (It does this by running check.pl.)

Feel free to change the test files as you debug, but remember that we’ll run your code against unmodified tests.

Stuck? Tackle the tests one at a time: make test01 work, then make test02 work, and so forth. And check our hints.

Phase 2: Memory reuse (test21–test32)

The handout allocator never reuses memory. Any program using it will eventually run out of memory, even if that program repeatedly frees all the memory it allocates. In Phase 2, you’ll implement memory reuse, where memory returned to the allocator via m61_free can be used again.

After memory reuse, your m61_malloc might use a helper function like this:

static void* m61_find_free_space(size_t sz) {
    // do we have a freed allocation that will work?
    for (allocation& a : freed allocation set) {
        if (a is at least sz bytes big) {
            void* ptr = first byte in a;
            remove a from freed allocation set;
            return ptr;
        }
    }
    // otherwise fail
    return nullptr;
}

Compared to the handout allocator, several new features are required.

  1. Your allocator must track a global set of freed allocations. To do this, you can use a container data structure, such as std::map (an ordered key–value structure) or std::vector (a resizable array), or you can roll your own (for instance, see our linked list example code).

  2. Your allocator must look up allocation sizes for freed allocations, to test whether a requested size fits in a freed allocation.

  3. Your allocator will also need to look up allocation sizes for active allocations! This is so m61_free can populate the freed-allocation set. There are several ways to track allocation sizes; one way is to add a global set of active allocations in addition to the set of freed allocations (for instance, std::map<void*, size_t> active_sizes).

  4. Finally, your allocator must coalesce freed allocations when necessary. Coalescing means merging adjacent freed allocations; this allows the combined space to be used for a bigger allocation. For instance, consider this code:

    void* ptr1 = m61_malloc(3 << 20); // 3 megabytes
void* ptr2 = m61_malloc(3 << 20);
m61_free(ptr1);
m61_free(ptr2);
// Although the freed allocations are 3 MiB each, they can be coalesced, allowing this to succeed:
void* bigptr = m61_malloc(6 << 20); // 6 megabytes
assert(bigptr);

Note that you can, and should, make incremental progress even before all those features are implemented. For instance, you could enforce a minimum allocation size. If every allocation is at least 1000 bytes, then it follows that any freed allocation is at least 1000 bytes, so a new allocation of 1000 bytes or less can fit into any freed allocation. This idea would allow you to pass tests 21–25 without tracking allocation sizes.

By the end of this phase, you should also correctly track the active size statistic.

Whether or not you’re confident in your pointer arithmetic and C++ programming ability, we strongly recommend you implement Phase 2 with external metadata first, even if you decide to try the implementing internal metadata for extra credit later on.

If you get stuck on Phase 2, switch to Phase 3. Tests 33–36 can be completed without tracking allocations.

Your allocator must use the memory in default_buffer. In particular, don’t replace our allocator with calls to malloc or new.

Phase 3: Debugging support (test33–test53)

Memory allocation is critically important to software performance and correctness, so allocation libraries should be optimized and robust. A robust library checks for common user errors and reports those errors early, with a helpful error message and an abort(), before the program goes totally off the rails. The C and C++ programming languages give the programmer full control over the contents of memory, so it’s impossible for a library to detect all errors. However, simple validity checks can be incredibly helpful and make your programs much more robust. Think of this phase as showing you how to program defensively.

Your work in this phase is arranged by type of error.

Invalid free and double-free detection (tests 33–44)

m61_free(ptr, file, line) should print an error message and then call C’s abort() function when a non-null ptr argument does not point to active dynamically-allocated memory.

Some things to watch:

Boundary write error detection (tests 45–47)

A boundary error is when a program reads or writes memory beyond the actual dimensions of an allocated object. A common type of boundary write error is to access an entry beyond the end of an array; here, the array has 10 elements at indexes 0 through 9, but the loop also accesses index 10:

int* array = (int*) malloc(10 * sizeof(int));
...
for (int i = 0; i <= 10 /* WHOOPS */; ++i) {
    array[i] = calculate(i);
}

These kinds of errors are relatively common in practice. Other errors, such as writing to totally random locations in memory or writing to memory before the beginning of an allocated block, also occur, but after-the-end boundary writes seem most common.

A debugging memory allocator can’t detect boundary read errors, but it can detect many boundary write errors. Your m61_free(ptr, file, line) should print an error message and call abort() if it detects that the memory block associated with ptr suffered a boundary write error.

No debugging allocator can reliably detect all boundary write errors. For example, consider this:

int* array = (int*) malloc(10 * sizeof(int));
int secret = array[10];     // save boundary value
array[10] = 1384139431;     // boundary write error
array[10] = secret;         // restore old value! dmalloc can’t tell there was an error!

Or this:

int* array = (int*) malloc(10 * sizeof(int));
array[200000] = 0;          // a boundary write error, but very far from the boundary!

We’re just expecting your code to catch common simple cases. You should definitely catch the case where the user writes one or more zero bytes directly after the allocated block.

Memory leak reporting (tests 48–51)

A memory leak happens when code allocates a block of memory but forgets to free it. Memory leaks are not as serious as other memory errors, particularly in short-running programs. But in long-running programs (e.g., a web browser), memory leaks have serious effects and are important to avoid. For example, a memory leak in a browser may prevent the browser from creating a new tab or playing a video!

Complete the m61_print_leak_report() function. This function should print a report about every active allocation in the system: that is, every object that has been malloced but not freed. It prints the report to standard output (not standard error). A report should follow the format of this example:

LEAK CHECK: test50.cc:13: allocated object 0x9b81140 with size 14
LEAK CHECK: test50.cc:14: allocated object 0x9b81110 with size 15
LEAK CHECK: test50.cc:11: allocated object 0x9b81170 with size 12
LEAK CHECK: test50.cc:18: allocated object 0x9b81050 with size 18
LEAK CHECK: test50.cc:10: allocated object 0x9b811e0 with size 11
LEAK CHECK: test50.cc:15: allocated object 0x9b810e0 with size 16
LEAK CHECK: test50.cc:16: allocated object 0x9b81080 with size 17

To use the leak checker, call m61_print_leak_report() before exiting the program, after cleaning up all known allocations using free calls. Any missing frees should show up in the leak report.

To implement a leak checker, you’ll need to keep track of every active allocated block of memory. It’s easiest to do this by adding more information to the block metadata. You will also use the file and line arguments to m61_malloc().

Note: You may assume that the file argument to these functions has static storage duration. This means you don’t need to allocate a copy of the string contents: it is perfectly safe to use the const char* file argument.

Advanced reports and checking

Our last test programs, test52.cc and test53.cc, require you to update your reporting and error detection code to print better information and defend against more diabolically invalid frees. You will need to read the test code and understand what is being tested to defend against it.

Update your invalid free message. After determining that a pointer is invalid, your code should check whether the pointer is inside a different allocated block. This will use the same structures you created for the leak checker. If the invalid pointer is inside another block, print out that block, like so:

MEMORY BUG: test52.cc:9: invalid free of pointer 0x833306c, not allocated
  test52.cc:8: 0x833306c is 128 bytes inside a 2001 byte region allocated here

And make sure your invalid free detector can handle certain diabolical situations. What situations? Check the test code to find out!

And that's it!

Style

Your code should be clean, clear, correct, and consistent. The most important style guideline is consistency. Our handout code follows a certain format (indentation amount, comment usage, variable names). We won’t grade you down if you choose a different format. But pick a format. Don’t write code that changes style from line to line.

For this problem set, additional coding guidelines will be incorporated into your grade.

Debugging allocators have a long history. dmalloc is one of the early ones; here’s a list of some others. Modern compilers integrate both optional allocation debugging features and some debugging features that are on by default. For instance, Mac OS and Linux’s memory allocators can detect some boundary write errors, double frees, and so forth. Recent clang and gcc -fsanitize=memory arguments can catch even more problems.

Feel free to look at the code and documentation for other allocators to get ideas, but make sure you cite them if you do.

Extra credit

We encourage you to learn more, flex your coding muscles, and show your mastery by doing some extra credit work! Please note that our policy is to not debug extra credit work for students.

You may submit extra credit along with your initial problem set submission, or with a new commit later in the semester. (To get your extra credit graded later in the semester, add a flag to the new commit on the grading server.) Please indicate what extra credit you attempted in your README.md.

Reallocation

Easy. Implement m61_realloc. This function is based on the C standard library’s realloc, and should behave like this:

/// m61_realloc(ptr, sz, file, line)
///    Changes the size of the dynamic allocation pointed to by `ptr`
///    to hold at least `sz` bytes. If the existing allocation cannot be
///    enlarged, this function makes a new allocation, copies as much data
///    as possible from the old allocation to the new, and returns a pointer
///    to the new allocation. If `ptr` is `nullptr`, behaves like
///    `m61_malloc(sz, file, line). `sz` must not be 0. If a required
///    allocation fails, returns `nullptr` without freeing the original
///    block.

void* m61_realloc(void* ptr, size_t sz, const char* file, int line);

For full credit, your solution must be correct—it must follow the specification (see a realloc manual page or standard for details)—and you must provide new tests that exercise its functionality.

Additional Test(s)

Moderate. You may have encountered a bug in your implementation that evaded the tests we gave you (or it evaded some of the earlier tests, but then you caught it in the process of debugging later tests). You can earn extra credit by writing test(s) that target these bugs. Any additional test must cover a realistic bug.

Model your new tests after our existing tests: add new files with names like test52.cc (the GNUmakefile specifies what kinds of filenames work with make). In your test files, explain what is being tested and why your tests are not redundant with our existing tests. Your memory allocator should pass your test(s).

Internal metadata (formerly phase 4)

Moderate. This extra credit opportunity requires a significant refactoring of your code from phases 1-3, so it is worth double the amount of extra credit points, relative to the other extra credit opportunities. You can submit your internal metadata implementation as your final submission upon the problem set 1 deadline, or you can submit it later in the semester by flagging an additional commit on the grading server. With either route you take, make sure that the commit you flag for grading passes all tests on the grading server.

How did you store per-allocation metadata in Phase 2 and Phase 3? Many students use C++ data structures like std::vector or std::map; some others use operators like new and delete to allocate dynamic memory. But though these techniques are convenient, this problem set implements an independent dynamic memory allocator! It’s kind of cheating to rely on someone else’s dynamic allocator to hold your allocator’s metadata.

But there is an extremely cool technique by which your allocator can store its metadata in the memory it controls. In this phase, you’ll implement that technique, which we call internal metadata.

To implement internal metadata, m61_malloc adds space for a fixed metadata header to the user’s requested size. When an allocation succeeds, m61_malloc initializes the first bytes of allocation with the metadata header, and then returns a pointer to the payload, which is the portion of the allocation following that header (and which is large enough to hold the user’s requested size). The m61_free function takes a payload pointer, not a header pointer, as input. However, since the header has a fixed size, it’s easy to compute the header address from the payload address using pointer arithmetic! See CS:APP3e Figure 9.35 “Format of a simple heap block” for an example of this type of layout.

You’ll define the structure format for your internal metadata, but it will contain, at minimum, the size of the allocation. As part of your work, you’ll document your metadata (see Style below).

How can you best implement and test your internal metadata? One idea might be to first implement internal metadata alongside working external metadata. Your code can then verify that the internal metadata matches the external metadata, for instance with assertions in m61_free. Once you’re confident in your internal metadata, you can remove the external metadata. But remember to use git commit to save your work at sensible points!

For full credit, your internal metadata representation must meet certain performance targets. Ideally:

Nastytest

Difficult. Make your internal metadata implementation pass nastytest1.cc. This is a test that corrupts the internal allocator state but may evade detection.

Multiple buffers

Moderate. Your handout allocator uses only one buffer, default_buffer. That limits the total size of data that can be allocated. Change your allocator so that it can allocate and use new buffers when the current buffer(s) run out of room. All allocated buffers should be freed when the program exits. Add tests that validate your work.

Large buffers

Moderate. (Extension to “multiple buffers”) The handout allocator can allocate data of maximum size 8 MiB (or a bit less, depending on metadata). Change your allocator to support arbitrarily large allocations. This will involve changing your metadata and/or the m61_memory_buffer structure. You will also need to decide whether very large allocations should be returned to the operating system when they are freed. (It’s generally good practice to return very large allocations immediately.) Add tests that validate your work.

High-performance allocation

Difficult. Change your m61_malloc internal metadata implementation to support O(1) memory allocation (or O(log N) memory allocation), for at least some classes of allocation. Your current implementation likely walks over all freed allocations, or all total allocations, to find a free block big enough, and thus likely has computational complexity O(F) or O(N).

There are several algorithms for high-performance memory allocation. One of the best known general-purpose allocator algorithms is buddy allocation. (CS 161 notes on buddy allocation) Or you can implement a useful special case, such as O(1) allocation and freeing for selected memory sizes.

As always, add tests that validate your work.

Notes

This lab was created for CS 61 and revamped in 2022.