Section 1: Allocation metadata

This is an outline of today’s section.

1. Setup (5m)

Tell students to sit in groups.
Make sure all students have GitHub accounts and have configured the grading server and gotten a private repository. Help them if they haven’t.
Have them update their code from the latest pset code (git pull handout main).
Students who have set up GitHub should set up Docker; report any problems you encounter.

2. Simple statistics (10-15m group work)

The psets repo has a new directory, pset1b.

It has a single m61.hh header, but multiple m61*.cc files, including m61-system.cc, m61-null.cc, m61-once.cc, and m61-section.cc (where section code should go).
Running make M61=section TESTNAME will link a test against m61-section.cc (and remember that M61 choice for future makes).
The stats-001.cc file was taken from the class’s posted tests. It checks several statistics, but NOT the “active bytes” statistic.
Students should discuss in groups how to make that test pass, and then implement their choices and test them.

3. Discussion (5m)

Discuss the solutions different groups had. Were they similar? Different?
Statistics calculations are related to memory reuse. In particular, consider stats-008.cc. What must be true at line 28 (// *** What is `stats.active_bytes` here?)? Does that fact help us to reuse memory?
- This leads to m61-reuseempty.cc, which restores the buffer to all-free when active_count drops to 0.
stats-009.cc, on the other hand, frees one block out of two allocated blocks, then checks that the active_bytes equals the size of the other block. How might you implement this?
Point students at https://cs61.seas.harvard.edu/site/2026/Containers/

4. Active bytes (10-15m group work)

Students should discuss in groups how to make that test pass, and then implement their choices and test them.

5. Discussion (10m)

Discuss the solutions different groups had. Were they similar? Different?

This staff solution is checked in as m61-staff.cc.

#include "m61.hh"
#include <map>

static m61_statistics gs;         // global statistics
static char* buffer = nullptr;
static char* end_buffer = nullptr;
static std::map<char*, size_t> active_allocs; // size of each active allocation

void* m61_malloc(size_t sz) {
    if (!buffer) {
        buffer = reinterpret_cast<char*>(malloc(8 << 20));
        assert(buffer);
        end_buffer = buffer + (8 << 20);
    }

    size_t space = end_buffer - buffer;
    if (sz > space) {
        // out of memory in buffer
        return nullptr;
    }

    // successful allocation
    void* ptr = buffer;
    gs.total_count += 1;
    gs.total_bytes += sz;
    gs.active_count += 1;
    gs.active_bytes += sz;
    active_allocs.insert({ buffer, sz });

    buffer += sz;
    return ptr;
}

void m61_free(void* ptr) {
    if (ptr) {
        char* bufptr = reinterpret_cast<char*>(ptr);
        auto it = active_allocs.find(bufptr);
        if (it == active_allocs.end()) {
            assert(false && "invalid free");
        }
        gs.active_count -= 1;
        gs.active_bytes -= it->second;
        active_allocs.erase(it);
    }
}

m61_statistics m61_get_statistics() {
    return gs;
}

The data structure needed for this test is called a “allocation map”. For each active allocation, this map remembers useful information such as the allocation’s size.
- Note that allocation maps give us a way to detect invalid frees!
Preview: The best allocators store this data in memory next to the allocation itself, so that an allocation’s size can be found without a separate lookup. How might you do this?

Now we pivot to memory reuse. The m61-once.cc allocator (which we saw in class) does not reuse memory. Full memory reuse isn’t easy, but some limited kinds of memory reuse are easier. We saw how easy it is to detect total memory reuse. Put up and discuss m61-lastalloc.cc:

#include "m61.hh"

static char* buffer = nullptr;
static char* end_buffer = nullptr;
static char* last_allocation = nullptr;

void* m61_malloc(size_t sz) {
    if (!buffer) {
        buffer = reinterpret_cast<char*>(malloc(8 << 20));
        assert(buffer);
        end_buffer = buffer + (8 << 20);
    }

    size_t space = end_buffer - buffer;
    if (sz > space) {
        return nullptr;
    }

    void* ptr = buffer;
    last_allocation = buffer;
    buffer += sz;
    return ptr;
}

void m61_free(void* ptr) {
    if (ptr == last_allocation) {
        buffer = last_allocation;
        last_allocation = nullptr;
    }
}

What is an example test where this allocator will reuse memory safely?
What is an example test where this allocator will not reuse memory safely?

6. Free map (10-15m)

So keeping a single piece of metadata—last_allocation—lets us support certain kinds of memory reuse.

Now, in groups, and with the allocation map in mind, students should discuss how to support arbitrary memory reuse within the buffer.

7. Summary

Back together, discuss the solutions and data structure choices students have come up with. Hopefully someone will notice the need for splitting and coalescing! If they haven’t, point them at a test that requires coalescing.