Section 3

1. Debugging an allocator

Setting

In this portion of section, we’re going to get more comfortable with debugging concepts and the GDB debugger via a broken allocator called m61-derp.cc. Here it is.

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

static m61_statistics gs;         // global statistics

// Idea: Track ALL blocks, allocated or free, in a single structure!
// Each block says whether it's free.
struct allocinfo {
    size_t bsz;      // size of block (includes padding)
    size_t usz;      // user size of block (only meaningful on allocated blocks)
    bool free;
};
static std::map<char*, allocinfo> blocks;

void* m61_malloc(size_t sz) {
    if (blocks.empty()) {
        char* buffer = reinterpret_cast<char*>(malloc(8 << 20));
        assert(buffer);
        // whole buffer is initially free
        blocks.insert({ buffer, { 8 << 20, 0, true }});
    }

    auto it = blocks.begin();
    while (it != blocks.end() && (!it->second.free || it->second.bsz < sz)) {
        ++it;
    }
    if (it == blocks.end()) {
        return nullptr;
    }

    // Successful allocation! Current state:
    //
    //     `it`
    //       ↓
    //       ┌──────────────────────────────────────────────┐
    //       │     first:   ║           second:             │
    //       │ ptr to first ║   bsz   │    usz   │   free   │
    //   <---│ byte in free ║ size of │  size of │          │----->
    //       │     space    ║  block  │user alloc│          │
    //       ├──────────────────────────────────────────────┤
    //       │      PTR     ║   BSZ   │    -     │   true   │
    //       └──────────────────────────────────────────────┘
    //
    // where BSZ ≥ the user’s requested size SZ.
    //
    // So split off an aligned block big enough to contain SZ, and mark it
    // allocated. The rest of the original block remains free. (ASZ is a
    // multiple of 16 so that SZ ≤ ASZ ≤ BSZ.)
    //
    //   `it`
    //     ↓
    //     ┌───────────────────────────────┐    ┌─────────────────────────────┐
    //  <--│  PTR  ║  ASZ  │  SZ   │ false │<-->│PTR+ASZ║BSZ-ASZ│  -  │  true │--->
    //     └───────────────────────────────┘    └─────────────────────────────┘

    // alignment: round up to multiple of 16
    size_t asz = sz && sz % 16 == 0 ? sz : (sz | 15) + 1;

    // split this block!
    // first insert new block
    char* nextptr = it->first + asz;
    blocks[nextptr] = { it->second.bsz - asz, 0, true };
    // then shrink our portion & mark it allocated
    it->second.bsz = asz;
    it->second.usz = sz;
    it->second.free = false;

    // statistics
    gs.total_count += 1;
    gs.total_bytes += sz;
    gs.active_count += 1;
    gs.active_bytes += sz;

    return it->first;
}

void m61_free(void* ptr) {
    if (!ptr) {
        return;
    }
    char* bufptr = reinterpret_cast<char*>(ptr);
    auto it = blocks.find(bufptr);
    if (it == blocks.end()) {
        assert(false && "invalid free");
    } else if (it->second.free) {
        assert(false && "double free");
    }
    it->second.free = 1;

    // statistics
    gs.active_count -= 1;
    gs.active_bytes -= it->second.usz;
}

m61_statistics m61_get_statistics() {
    return gs;
}

The student who wrote m61-derp.cc wasn’t expecting this allocator to pass all the torture tests, but it’s failing tests that the student expected it to pass.

$ make SAN=0 M61=derp -k check-torture
*** Using m61-derp.cc, sanitizers disabled ***

torture/01-stats-initial passed
torture/02-stats-count passed
torture/03-distinct passed
Assertion failed: (false && "double free"), function m61_free, file m61-derp.cc, line 86.
/bin/sh: line 1: 40574 Abort trap: 6           ASAN_OPTIONS=detect_leaks=0 ./$t
torture/04-fill FAILED with exit status 134
make: *** [check-torture/04-fill] Error 1
torture/05-zero-and-null passed
Assertion failed: (false && "double free"), function m61_free, file m61-derp.cc, line 86.
/bin/sh: line 1: 40578 Abort trap: 6           ASAN_OPTIONS=detect_leaks=0 ./$t
torture/06-alignment FAILED with exit status 134
make: *** [check-torture/06-alignment] Error 1
torture/07-huge passed
torture/08-reuse passed
Assertion failed: (ptrs[j]), function main, file 09-reuse-five.cc, line 10.
/bin/sh: line 1: 40584 Abort trap: 6           ASAN_OPTIONS=detect_leaks=0 ./$t
torture/09-reuse-five FAILED with exit status 134

The problem is that line 62, blocks[nextptr] = { it->second.bsz - asz, 0, true };, can insert a 0-length block into the map! This might overwrite an existing free block. Possible fixes: don’t execute the line if asz == it->second.bsz; or use blocks.insert({ nextpr, ... }), which will leave any existing data alone. Either fix will pass torture tests 1–13.

Allocator basics

Skim the code in groups and answer these comprehension questions:

1. Does this allocator use internal or external metadata? What kind?
2. Does this allocator split free blocks during allocation?
3. Does it coalesce blocks during free?
4. Does it ensure every allocated block is aligned?
5. Does it ensure zero-byte allocations receive distinct addresses?
6. Does it protect against unsigned integer overflow?

1. External metadata—a std::map.
2. Yes, it splits.
3. It doesn’t coalesce.
4. It does align. (May be worth a minute talking about (sz | 15) + 1!)
5. It does ensure zero-byte allocations get distinct addresses.
6. It does not protect against unsigned integer overflow. For that you’d need sz && sz % 16 != 0 && sz < SIZE_MAX - 16.

Gather back to discuss.

Debugging strategies

Let’s debug this allocator. (You may see the problem right away, you may not; what’s interesting is the debugging process.)

In groups:

1. Discuss general strategies for debugging a failure, in the context of m61-derp’s failure on torture/04-fill. What do you need to know about the bug to make progress? How can you run experiments to narrow down where the bug occurs, either in the allocator’s code or during the progression of the test?

2. Start running some of those experiments.

For instance, the torture/04-fill bug manifests as a double-free report in a test that has no double frees. An important narrowing-down strategy is to figure out which free causes the double-free report: is it early in the test, or late? How would you narrow this down? Take about 10 minutes, and then we’ll hear from everyone how they got on.

Hopefully students bring up strategies including invariants/assertions, GDB, and printouts. You can be guided by students when thinking about what comes next.

Example approach: Add printfs (or C++ std::println()) to the test; the ones that do print happen before the bug occurred.

Debugging with GDB

Printouts are an excellent debugging strategy, but sometimes the appropriate tool is to poke around live inside a paused, but running, program. This is especially useful if the program automatically pauses itself right when a problem is detected. That’s what exactly how abort behaves if a program is run under a debugger!

Many of you have used GDB before, but if you haven’t, here’s a crash course. (We have more material on GDB and a command cheatsheet.)

We invoke GDB with gdb EXECUTABLEFILE. This reads symbols from EXECUTABLEFILE, but does not actually run it. Run the program with r [OPTIONAL ARGUMENTS]. This will start the program—just as if you had run it on the terminal—and run it until something like a crash happens. You can also interrupt the command by pressing Control-C. Normally, this would cause the command to quit, but in a debugger the program doesn’t quit, it just pauses itself and gives the debugger control.

Once the debugger has control in a paused, but running, program, you can type commands that examine that program’s memory and check which functions are executing. For example, the p command can print a variable, and the bt command can print all the running functions, starting from the currently executing one (usually a version of abort) and then going through its caller, and that function’s caller, all the way up to main. This can directly show where the crash occurred.

Here’s a backtrace of torture/04-fill at the crash point:

(gdb) bt
#0  __pthread_kill_implementation (threadid=281474842206240, signo=signo@entry=6, no_tid=no_tid@entry=0) at ./nptl/pthread_kill.c:44
#1  0x0000fffff7ace1b4 [PAC] in __pthread_kill_internal (threadid=<optimized out>, signo=6) at ./nptl/pthread_kill.c:89
#2  0x0000fffff7a785fc in __GI_raise (sig=sig@entry=6) at ../sysdeps/posix/raise.c:26
#3  0x0000fffff7a62720 [PAC] in __GI_abort () at ./stdlib/abort.c:77
#4  0x0000fffff7ac0a58 [PAC] in __libc_message_impl (vma_name=vma_name@entry=0xfffff7baa980 "glibc: assert", fmt=<optimized out>)
    at ../sysdeps/posix/libc_fatal.c:138
#5  0x0000fffff7a710d8 [PAC] in __libc_message_wrapper (vmaname=0xfffff7baa980 "glibc: assert", fmt=<optimized out>)
    at ../include/stdio.h:203
#6  __assert_fail (assertion=0xaaaaaaac1420 "false && \"double free\"", file=0xaaaaaaac13d8 "m61-derp.cc", line=<optimized out>, 
    function=<optimized out>) at ./assert/assert.c:37
#7  0x0000aaaaaaaa4bd4 [PAC] in m61_free (ptr=0xfffff723f020) at m61-derp.cc:86
#8  0x0000aaaaaaaa4528 in main () at torture/04-fill.cc:40
(gdb) f 7
#7  0x0000aaaaaaaa4bd4 [PAC] in m61_free (ptr=0xfffff723f020) at m61-derp.cc:86
86          assert(false && "double free");
(gdb) up
#8  0x0000aaaaaaaa4528 in main () at torture/04-fill.cc:40
40              m61_free(ptrs[i]);
(gdb) l
35          fill_pattern(more[i], i, 1000 + i);
36      }
37      for (int i = 0; i != nptrs; ++i) {
38          if (ptrs[i]) {
39              assert(check_pattern(ptrs[i], i, i));
40              m61_free(ptrs[i]);
41          }
42          assert(check_pattern(more[i], i, 1000 + i));
43          m61_free(more[i]);
44      }
(gdb) p i
$1 = 1

What GDB commands can you use to examine the internal state that causes the double-free error?

Seems like printing the iterator might be useful.

(gdb) l
81      char* bufptr = reinterpret_cast<char*>(ptr);
82      auto it = blocks.find(bufptr);
83      if (it == blocks.end()) {
84          assert(false && "invalid free");
85      } else if (it->second.free) {
86          assert(false && "double free");
87      }
88      it->second.free = 1;
89  
90      // statistics
(gdb) p *it
$2 = {first = 0xfffff723f020 "\261", second = {bsz = 0, usz = 0, free = true}}

And indeed this is useful, because the iterator is pointing at a zero-length block! That seems very strange. Should the map contain zero-length blocks? How might one get in?

Debugging with invariants

Another debugging approach involves adding assertions to your code. These are statements that you, the programmer, believe should be true at a particular point in the code. It’s very easy to write a program that implicitly depends on such beliefs, and that goes wildly wrong if a belief doesn’t actually hold. (For instance, you might believe that a requested size is small enough that adding 16 doesn’t overflow.)

A statement like assert(EXPR) means “crash the program if EXPR is not true here.” Our tests and torture tests have lots of assertions in them, but it’s often super useful to add assertions to your allocator too.

Assertions come in many shapes, but allocator metadata often benefits from a particular form of assertion called a representation checker or representation invariant. This is a function that checks an interesting data structure for internal consistency. The properties checked are expected to hold at every point during a program. (A subsystem that actively modifies a data structure might temporarily violate the representation invariant, but it must restore the invariant before returning.) A good rep checker should assert “everything it can”. During early-stage development and debugging, it’s good practice to write a rep checker and call it at the beginning and end of every method that touches the data structure. That will catch bugs early, as soon as they occur, rather than at some future point when the data structure’s buggy state gets serious enough to cause a crash.

In groups, develop a rep checker for m61-derp.cc’s data structure that’s as comprehensive as possible. Add calls to the rep checker. When does the rep checker fire? (Hopefully by this point students will have found the error.)

void check_rep() {
    char* buffer = nullptr;     // infer start of buffer from first iterator
    char* expected = nullptr;   // expected position of next iterartor
    for (auto it = blocks.begin(); it != blocks.end(); ++it) {
        // check start of block
        if (!buffer) {
            buffer = it->first;
        } else {
            assert(expected == it->first);
        }
        // check sizes against each other:
        // no zero-length block; blocks 8MiB or smaller
        assert(it->second.bsz > 0 && it->second.bsz <= (8 << 20));
        // blocks are aligned
        assert(it->second.bsz % 16 == 0);
        // free blocks have no `usz`; allocated blocks do
        if (!it->second.free) {
            assert(it->second.usz <= it->second.bsz);
            // no more padding than necessary
            assert(it->second.bsz - it->second.usz <= 16);
        }
        // assign expected next position
        expected = it->first + it->second.bsz;
    }
    // found at least 1 block; blocks together cover 8MiB
    assert(buffer && expected == buffer + (8 << 20));
}

2. Exercises

We’ll use the rest of section to go through exercises motivated by test questions. Come up with your own answers in groups, then discuss!

2.1. Sizes and alignments

Question 2.1A. True or false: For any non-array type X, the size of X (sizeof(X)) is greater than or equal to the alignment of type X (alignof(X)).

True. This follows from the array layout rule: arrays are laid out sequentially in memory with no gaps. If the alignment of a type were greater than the size, then the array layout rule would cause element 1 in an array to be misaligned—a contradiction.

The requirement that size ≥ alignment is also mostly true that for array types. The exception is zero-length arrays. Given an array type AT equivalent to T[N], sizeof(AT) == 0, but alignof(AT) == alignof(T).

Question 2.1B. True or false: For any type T, the size of struct Y { T a; char newc; } is greater than the size of T.

True. This follows from the struct layout rule.

Question 2.1C. True or false: For any types T1...Tn (with n ≥ 1), the size of struct Y is greater than the size of struct X, given:

struct X {
    T1 m1;
    ...
    Tn mn;
};

struct Y {
    T1 m1;
    ...
    Tn mn;
    char newc;
};

False. It’s possible for newc to slip into some padding that would otherwise be required to preserve alignment. (For example, let n=2, T1=int, and T2=char.)

Question 2.1D. True or false: For any types T1...Tn (with n ≥ 1), the size of struct Y is greater than the size of union X, given:

union X {
    T1 m1;
    ...
    Tn mn;
};

struct Y {
    T1 m1;
    ...
    Tn mn;
};

False, because of the special case n=1.

Question 2.1E. Assume that structure struct Y { ... } contains K char members and M int members, with K≤M, and nothing else. Write an expression defining the maximum sizeof(struct Y).

4M + 4K. This happens if the chars and ints alternate: C++ will add 3 bytes of padding after every char.

Question 2.1F. Given struct Z { T1 a; T2 b; T3 c; }, which contains no padding, what does (sizeof(T1) + sizeof(T2) + sizeof(T3)) % alignof(struct Z) equal?

0. If the struct contains no padding, then its size equals the sum of the sizes of its members; and the size of any object is a multiple of its alignment.

Question 2.1G. Arrange the following types in increasing order by size. Sample answer: “1 < 2 = 4 < 3” (choose this if #1 has smaller size than #2, which has equal size to #4, which has smaller size than #3).

1. char
2. struct minipoint { uint8_t x; uint8_t y; uint8_t z; }
3. int
4. unsigned short[1]
5. char**
6. double[0]

#6 < #1 < #4 < #2 < #3 < #5. The sizes are:

1. sizeof(char) == 1 (for all C++ implementations no matter what!)
2. sizeof(minipoint) == 3 (no need for padding)
3. sizeof(int) == 4
4. sizeof(unsigned short[1]) == 1 * sizeof(unsigned short) == 2
5. sizeof(char**) == 8
6. sizeof(double[0]) == 0 * sizeof(double) == 0 (tricky)

2.2 Expression matching

Question 2.2. Consider the following eight expressions:

1. m
2. sizeof(&m)
3. -1
4. m & -m
5. m + ~m + 1
6. 32 >> 2
7. m & ~m
8. 1

For one unique value of m, those eight expressions can be grouped into four matched pairs where the two expressions in each pair have the same value, and expressions in different pairs have different values. What are the values of the expressions for that m?

1. -1
2. 8
3. -1
4. 1
5. 0
6. 8
7. 0
8. 1

#2, #3, #6, and #8 are easy. Then bitwise arithmetic reasoning tells us m + ~m + 1 == m + (-m) == 0 and (m & ~m) == 0. That leaves

1. ?
2. 8
3. -1
4. ?
5. 0
6. 8
7. 0
8. 1

There are two unmatched values, -1 and 1; m must equal one of them. If m == 1, then (m & -m) == (1 & -1) == 1, and there are not four matched pairs. If m == -1, though, everything works out.

2.3 Dynamic memory allocation

Question 2.3A. True or false?

1. free(nullptr) is an error.
2. malloc(0) can never return nullptr.

Both false. free(nullptr) is allowed, and defined to do nothing. malloc(0) might or might not return nullptr; from the manual page (man malloc):

If size is 0, then malloc() returns either NULL, or a unique pointer value that can later be successfully passed to free().

(nullptr is the preferred way to say NULL in C++.)

Question 2.3B. The calloc function (signature void* calloc(size_t sz, size_t nmemb)) returns a pointer to an allocation that can hold an array of nmemb objects of size sz, or nullptr if such an array cannot be allocated. (If either sz or nmemb is 0, calloc behaves like malloc.) Give values for sz and nmemb so that calloc(sz, nmemb) will always return nullptr on a 64-bit x86-64 machine, but malloc(sz * nmemb) might or might not return null.

(size_t) -1, (size_t) -1 — anything that causes unsigned integer overflow! calloc must check if overflow will occur and return nullptr if the mathematical integer sz * nmemb doesn’t fit in a size_t. But in our example, sz * nmemb is calculated before it is passed to malloc. There may or may not be enough space for the result of the overflow; malloc wouldn't know that it overflowed in the first place.

For parts C–F, consider the following 8 statements. (p and q have type char* and start out as uninitialized variables.)

1. free(p);
2. free(q);
3. p = q;
4. q = nullptr;
5. p = (char*) malloc(12);
6. q = (char*) malloc(8);
7. p[8] = 0;
8. q[4] = 0;

Question 2.3C. Put the statements in an order that would execute without error or evoking undefined behavior. Memory leaks count as errors. Use each statement exactly once. Sample answer: “abcdefgh.”

Example solution: cdefghab. For each pointer, the malloc must precede the dereference, which must precede the free, so ega and fhb must appear in that order. The pointer assignments cd are then interspersed in safe places.

Question 2.3D. Put the statements in an order that would cause one double-free error, and no other error or undefined behavior (except possibly one memory leak). Use each statement exactly once.

Example solution: efghbcad. The key is to use statement c so that statements a and b both refer to the same allocation.

Question 2.3E. Put the statements in an order that would cause one memory leak (one allocated piece of memory is not freed), and no other error or undefined behavior. Use each statement exactly once.

Example solution: efghadbc.

Question 2.3F. Put the statements in an order that would cause one boundary write error, and no other error or undefined behavior. Use each statement exactly once.

Example solution: eafhcgbd.

2.4 Pointers and debugging allocators

You are debugging some students’ m61 code from Problem Set 1. The codes use the following metadata:

struct meta { ...
    meta* next;
    meta* prev;
};

meta* mhead;    // head of active allocations list

Their linked-list manipulations in m61_malloc are similar.

void* m61_malloc(size_t sz, const char* file, int line) {
    ...
    meta* m = (meta*) ptr;
    m->next = mhead;
    m->prev = nullptr;
    if (mhead) {
        mhead->prev = m;
    }
    mhead = m;
    ...
}

But their linked-list manipulations in m61_free differ.

Alice’s code:

void m61_free(void* ptr, ...) { ...
    meta* m = (meta*) ptr - 1;
    if (m->next != nullptr) {
        m->next->prev = m->prev;
    }
    if (m->prev == nullptr) {
        mhead = nullptr;
    } else {
        m->prev->next = m->next;
    }
    ...
}

Bob’s code:

void m61_free(void* ptr, ...) { ...
    meta* m = (meta*) ptr - 1;
    if (m->next) {
        m->next->prev = m->prev;
    }
    if (m->prev) {
        m->prev->next = m->next;
    }
    ...
}

Chris’s code:

void m61_free(void* ptr, ...) { ...
    meta* m = (meta*) ptr - 1;
    m->next->prev = m->prev;
    m->prev->next = m->next;
    ...
}

Donna’s code:

void m61_free(void* ptr, ...) { ...
    meta* m = (meta*) ptr - 1;
    if (m->next) {
        m->next->prev = m->prev;
    }
    if (m->prev) {
        m->prev->next = m->next;
    } else {
        mhead = m->next;
    }
    ...
}

You may assume that all code not shown is correct.

Question 2.4A. Whose code will segmentation fault (crash) on this input? List all students that apply.

int main() {
    void* ptr = malloc(1);
    free(ptr);
}

Chris’s code will segfault. After one allocation, the metadata list has one element, so ptr’s metadata node has m->next == m->prev == nullptr. This means that his m61_free code will dereference a null pointer (m->next->prev) and crash.

Question 2.4B. Whose code might report something like “invalid free of pointer [ptr1], not allocated” on this input (because a list traversal starting from mhead fails to find ptr1)? List all students that apply. Don’t include students whose code would crash before the report.

int main() {
    void* ptr1 = malloc(1);
    void* ptr2 = malloc(1);
    free(ptr2);
    free(ptr1);   // <- message printed here
}

Alice’s code can’t find ptr1. The shared m61_malloc code adds new linked list nodes at the head of the list, with next pointers leading to older heads. Thus, after the two allocations, memory looks like this in all four implementations:

mhead ─────────────────┐
                       │
           ptr1        v          ptr2
┌─────────┲━━━━━┓      ┌─────────┲━━━━━┓
│next┊prev┃░░░░░┃      │next┊prev┃░░░░░┃
│ XX ┊    ┃░░░░░┃      │    ┊ XX ┃░░░░░┃
└───────│─┺━━━━━┛      └──│──────┺━━━━━┛
^       │              ^  │
└──────────────────────│──┘
        └──────────────┘

Alice’s m61_free, though, sets mhead to nullptr when the freed metadata node has null prev. This loses all links to older nodes.

mhead XX

           ptr1
┌─────────┲━━━━━┓
│next┊prev┃░░░░░┃
│ XX ┊ XX ┃░░░░░┃
└─────────┺━━━━━┛

Alice should update mhead to m->next, not nullptr, when m->prev == nullptr.

Question 2.4C. Whose code could improperly report a leaked piece of memory on this input, or cause a crash in m61_printleakreport (because the mhead list contains garbage)? List all students that apply. Don’t include students whose code would segfault before the report.

int main() {
    void* ptr1 = malloc(1);
    free(ptr1);
    m61_printleakreport();
}

Bob’s code will do this. The problem is that Bob does not update mhead in the case that mhead points to the element being freed. After the malloc, memory looks like this:

mhead
│
v          ptr1
┌─────────┲━━━━━┓
│next┊prev┃░░░░░┃
│ XX ┊ XX ┃░░░░░┃
└─────────┺━━━━━┛

And after the free, memory looks like this. ptr1 and associated metadata has been freed, but mhead still points to the freed space:

mhead
│
v
?????????????????
?????????????????
?????????????????
?????????????????

The leak check report will print something associated with ptr1, and it might crash, too, by causing use-after-free errors.

Question 2.4D. Whose linked-list code is correct for all inputs? List all that apply.

Donna’s code is correct!

3. Fragmentation

We don’t expect to reach this material in section, but it is useful!

Fragmentation is a problem that can afflict memory allocators. An allocator suffers fragmentation when its free space is large enough to accommodate an allocation, but unusable in practice for that allocation. For instance, an M61 allocator might report active_bytes 800'000, meaning it had more than 7 MiB bytes of free space; but that free space might be so awkwardly arranged that a call of m61_malloc(1'000'000) would have to fail!

Question for the section: How might this happen? (Take suggestions, draw the result.)

Group work (10-15m)

Divide the room in thirds.

1. One third should design an attack that provokes this behavior—a sequence of m61_malloc and m61_free calls that eventually result in 800,000 active_bytes, but no contiguous free space of 1,000,000 bytes or more.

2. The other thirds should independently design allocator strategies that are robust to this test. That is, their goal is to develop an allocator strategy that defeats the attack invented by the other third.

Example: An attack might look like this:

void* ptrs[15];
ptrs[0] = m61_malloc(100000);
ptrs[1] = m61_malloc(900000);
// repeat that 7 more times
ptrs[14] = m61_malloc(100000);
for (int i = 1; i < 14; i += 2) {
    m61_free(ptrs[i]);
}

Modulo metadata and padding, this results in the following free regions given the natural left-to-right allocation strategy: [100K, 1M), [1.1M, 2M), [2.1M, 3M), ..., [7.1M, 8M), [8.1M, 8.388M)—nothing larger than 0.9M.

A defense strategy would be to allocate smaller and larger allocations from different regions of the buffer. For example, you might place allocations of 200K or less “on the left” (starting at lower addresses), and larger allocations “on the right” (starting at higher addresses and working down).

Continuation option 1

Discuss and then swap: the attack group picks their preferred robust allocator and tries to make it more robust, while the robust-allocator groups try to design an attack that defeats the allocator they just built.

Continuation option 2

Discuss and then sketch an implementation of the best defense strategy, including code.

Continuation option 3

Challenge the class to come up with a fragmentation-free workload and M61 allocator. This is an allocator that, for a given class of workloads, never refuses an allocation unless the total amount of free space in the allocator buffer is less than the requested size.

Answer: Almost any allocator is fragmentation-free if every allocation in the workload has the same size!