Problem set 1 – CS 61 2022

Ungraded intermediate checkin: Sat 9/17 (see Turnin, below, for more)
Final turnin Fri 9/23 at 11:59:59pm EDT (one day later for DCE)
Most of our problem sets, including this one, can be completed natively on Linux, Mac OS X (with Xcode and Homebrew), Docker, or, possibly, Windows Subsystem for Linux. We grade using Linux.

Goal

Programming almost always requires the allocation and deallocation of dynamic memory. Dynamic allocation lets us write fast code for modern machines and 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:

Track memory usage statistics.
Reuse freed memory and avoid memory fragmentation.
Catch common programming errors, including boundary write errors, invalid frees, and double frees.
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

This problem set serves several purposes for us and you.

It gets you back into C/C++ programming, if you are a little rusty.
It teaches you about byte wrangling, sizes, and the memory representations of information. This is great preparation for the rest of class.
It introduces you to some common memory errors and shows how careful code can defend against them.
You’ll learn how malloc works.
It will be fun!

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-f22-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

Like much systems programming, 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
[01;31mtest01 FAIL: Unexpected output starting on line 1
[0;31m  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`[0m
$ 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.

Every student should commit and upload an initial checkin by midnight on Saturday 9/17 (one day later for DCE). This initial checkin should contain your work for at least Phases 1 and 2. Remember, though, this submission will not be graded and you won’t hear back from us unless we’re worried about your submission.
The complete problem set is due by Friday 9/23 (one day later for DCE).

Remember, the earlier you complete this problem set, the earlier you can get started on the next one!

It is important to get started early—this problem set is not trivial even though you don’t have to write that much code to make it work.

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.

Grading components:

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.
Coding style. Remember to document your metadata.

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.

Dynamically-allocated memory remains active until it explicitly freed with a call to free.
A successful call to malloc(sz) returns a pointer ptr 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 equal nullptr or a pointer to active dynamically-allocated memory. In particular:
1. It is not OK to call free(ptr) if ptr points to the program’s code, or into its global variables, or into the stack.
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 ptr is currently inactive (i.e., free(ptr) was previously called with the same pointer argument, and the ptr memory block was not reused by another malloc()).
These errors are called invalid frees. The third error is also called a double free.

Some notes on boundary cases:

free(nullptr) is allowed. It does nothing.
malloc(sz) returns memory whose alignment works for any object. (We’ll discuss alignment in class; for a preview, see CS:APP3e §3.9.3.) 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.)

There is also a secondary 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++ (optional note)

Most C++ dynamic memory allocation happens via the operators new and delete (or, for arrays, new[] and delete[]), rather than direct calls to malloc and free. These operators allocate and free memory, but they also initialize the returned memory, thus ensuring it holds valid objects of a given type.

Nevertheless, the C++ standard library’s implementations of new and delete calls functions like malloc and free under the hood.

C++ containers and other helper classes can be configured to allocate memory using a user-provided allocator. Check out test17 and test18 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–test19)

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 (test20–test30)

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) {
    // try default_buffer
    if (default_buffer.size - default_buffer.pos >= sz) {
        void* ptr = &default_buffer.buffer[default_buffer.pos];
        default_buffer.pos += sz;
        return ptr;
    }
    // otherwise, try to reuse a freed allocation
    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.

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).
Your allocator must look up allocation sizes for freed allocations, to test whether a requested size fits in a freed allocation.
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).

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 20–23 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 though in Phase 4 you will replace this implementation.

If you get stuck on Phase 2, switch to Phase 3. Tests 31–34 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 (test31–test51)

Memory allocation is critically important to software performance and correctness, so most allocation libraries are both 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. Still, though, simple validity checks can be incredibly powerful 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 31–42)

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:

Be careful of calls like free((void*) 0x16), where the ptr argument is not nullptr but it also doesn’t point to heap memory. Your debugging allocator should not crash when passed such a pointer. It should print an error message and exit in an orderly way.
The test programs define the desired error message format. Here’s our error message for test32:
```
MEMORY BUG: test32.cc:9: invalid free of pointer 0x4001a78010, not in heap
```
Error messages should be printed to standard error (using C’s fprintf(stderr, ...), or, equivalently, C++’s std::cerr).
Every error message must end in a newline. (If you leave out the newline, the message might not be printed in some environments.)
Different error situations require different error messages; the other test programs define the required messages.
Include the file name and line number of the problematic call to free().

Boundary write error detection (tests 43–45)

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 46–49)

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. They don’t cause a crash. (The operating system always reclaims all of a program’s memory when the program exits.) But in long-running programs, such as your browser, memory leaks have serious effect and are important to avoid.

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: test42.cc:13: allocated object 0x9b81140 with size 14
LEAK CHECK: test42.cc:14: allocated object 0x9b81110 with size 15
LEAK CHECK: test42.cc:11: allocated object 0x9b81170 with size 12
LEAK CHECK: test42.cc:18: allocated object 0x9b81050 with size 18
LEAK CHECK: test42.cc:10: allocated object 0x9b811e0 with size 11
LEAK CHECK: test42.cc:15: allocated object 0x9b810e0 with size 16
LEAK CHECK: test42.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, test50.cc and test51.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: test44.cc:9: invalid free of pointer 0x833306c, not allocated
  test44.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!

Phase 4: Internal metadata

Congratulations! You’ve now completed all the tests. But there’s more work to do.

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:

A valid call to m61_free (that is, a request to free an active allocation) should take O(1) time to validate its argument, free it, and coalesce it with adjacent freed allocations, if any.
A call to m61_malloc may take O(N) time, where N is the number of allocation blocks (freed or allocated). But you could do better! It’s relatively easy to achieve O(F) time, where F is the number of freed blocks; and it’s possible to achieve O(log S) time, where S is the size of the buffer (8 MiB), using an algorithm like buddy allocation.
All space used by the allocator should fit within the default_buffer, with the exception of at most a couple kilobytes of global variables (to, for example, keep track of statistics and/or a limited set of recently freed allocations).

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.

Document your metadata. Explain what additional data structures you used, and how you tested them.
Your metadata should be compact. The allocator should introduce at most tens of bytes of overhead per allocation, not hundreds or thousands.
Your malloc and free functions should not store unbounded metadata.
Your implementation should not introduce memory errors or undefined behaviors of its own. For instance, your code should not introduce any sanitizer errors; our solutions cleanly pass make SAN=1 check-all.

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.

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, long 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).

Nastytest

Difficult. Make your internal metadata implementation pass nastytest1.cc. This is a test that corrupts the internal allocator state but may evade detection. For hints, check out the discussion in the Datarep Supplemental 3 lecture recording.

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.

Problem set 1: Memory allocator