Show all solutions Hide all solutions

Test 2

Notes

Assume a Linux operating system running on the x86-64 architecture unless otherwise stated. On this architecture, sizeof(int) == 4, sizeof(long) == sizeof(void*) == 8, and the maximum alignment required by any type is 16.

Some figures and code samples can be pinned to your browser so you can keep them visible as you scroll through the test. Push the 📌 and then drag the pinned figure where you want it.

Some questions concern Problem Set 1’s m61 allocators and tests; an m61 test is a complete program that indicates success by exiting with status 0 and failure by terminating abnormally (e.g., by failing an assertion). print_object(x) prints the address of object x, followed by the hexadecimal values of its bytes in increasing address order, 16 bytes per line. print_bytes(ptr, sz) prints in a similar format the sz bytes of memory starting at ptr.

1. Bytes of a record (15 points)

This program was compiled and run on x86-64 Linux.

struct record {
    short id;
    char tag;
    int count;
    const char* name;
    unsigned char flags;
};

int main() {
    const char* buf = "alpha";
    record r = { 61, 'Q', 10000, buf, 5 };
    print_object(r);
}

It printed:

7bc3'53bf'0040  3d 00 51 00 10 27 00 00  80 01 b8 4a 88 55 00 00
7bc3'53bf'0050  05 00 00 00 00 00 00 00

QUESTION 1A. Which byte offsets within r hold padding? List them all. (The first byte of r has offset 0.)

QUESTION 1B. What is sizeof(record)?

QUESTION 1C. What is the value of r.count in hexadecimal?

QUESTION 1D. These lines are added after the call to print_object(r) (though not necessarily in this order):

    print_bytes(buf, sizeof(buf));
    print_bytes(buf, strlen(buf));
    print_object(buf);
    print_object(r.name);

Assuming that print_object(r) printed the exact addresses and bytes shown above, which of these outputs might be generated by each line of code? List all that apply.

7bc3'53bf'0020 80 01 b8 4a 88 55 00 00
7bc3'53bf'0048 80 01 b8 4a 88 55 00 00
5588'4ab8'0180 61 6c 70 68 61
5588'4ab8'0180 61 6c 70 68 61 00
5588'4ab8'0180 61 6c 70 68 61 00 00 00
Sanitizer error: signed integer overflow
Sanitizer error: global buffer overflow

QUESTION 1E. buf is declared before r. How might its address relate to the address of r? List all that apply and explain briefly.

The address of buf must be less than the address of r
The address of buf must equal the address of r.name
The address of buf must be greater than the address of r
None of the above

QUESTION 1F. What is the minimum size of any structure with the same members as record (but not necessarily in the same order)?

2pt 16 bytes. Any order that avoids interior padding works, such as:
struct record {
    const char* name;
    int count;
    short id;
    char tag;
    unsigned char flags;
};
The members have sizes 8 + 4 + 2 + 1 + 1 = 16, each is naturally aligned at its offset, and 16 is a multiple of the struct’s alignment (8), so no padding is required.

QUESTION 1G. Some of these expressions always evaluate to the same numeric value. List all pairs (or greater subsets) that always have the same value.

r.name + 5 - 2
&r.id
(long) r.count % 2
(buf + strlen(buf)) - r.name
&r
nullptr
r.flags
&r.name[3]

2. Break that allocator (18 points)

Each part of this question shows a fragment of an m61 allocator with a bug. Your job is to design an m61 test that exposes that bug (but doesn’t falsely accuse any correct allocator). You may describe the test, but ideally write code: a few lines each is enough. You may assume all allocator code not shown is correct.

All the fragments share these declarations. The buffer is 8 MiB and comes from malloc, so it is 16-byte aligned; fresh space is handed out sequentially from buffer.

constexpr size_t buffer_size = 8 << 20;   // allocated size of buffer
static char* buffer;                      // next unused byte of the buffer
static char* end_buffer;                  // one past the end of the buffer
static std::map<char*, size_t> active;    // active payload -> requested size
static std::map<char*, size_t> freed;     // free block -> block size

QUESTION 2A. This m61_malloc stores a 32-byte header before each payload; it doesn’t support memory reuse yet.

void* m61_malloc(size_t sz) {
    size_t padding = sz % 16 ? 16 - sz % 16 : 0;
    size_t bsz = 32 + sz + padding;      // header plus payload plus alignment padding
    if (bsz > size_t(end_buffer - buffer)) {
        return nullptr;
    }
    char* ptr = buffer + 32;
    // ... initialize header, insert `ptr` into `active` ...
    buffer += bsz;
    return ptr;
}

Design a test that fails for this allocator. Your test should not require memory reuse.

4pt
int main() {
    void* p = m61_malloc(SIZE_MAX);
    assert(p == nullptr);
}
No allocator can satisfy a request for 2⁶⁴−1 bytes, so a correct m61_malloc returns nullptr. In this fragment, SIZE_MAX gets 1 byte of padding, and 32 + SIZE_MAX + 1 wraps around to 32, which is smaller than the space remaining, so line 4 does not fail. The function returns a bogus pointer to a “successful” allocation and advances buffer by only 32 bytes. Any sz ≥ SIZE_MAX − 46 triggers the bug (bsz wraps to 0, 16, or 32); SIZE_MAX works without knowing the header size.

QUESTION 2B. This m61_malloc uses purely external metadata; it doesn’t support wild-write detection yet.

void* m61_malloc(size_t sz) {
    if (sz > buffer_size) {
        return nullptr;
    }
    // ... maybe reuse a free block ...
    size_t bsz = sz % 16 ? (sz | 15) + 1 : sz;  // round up to multiple of 16
    if (bsz > size_t(end_buffer - buffer)) {
        return nullptr;
    }
    active.insert({ buffer, sz });
    char* ptr = buffer;
    buffer += sz;
    return ptr;
}

Design a test that fails for this allocator. Your test should not involve a wild write.

4pt Line 6 computes a rounded block size, but line 12 advances buffer by the requested size sz. Two kinds of test notice.

An alignment test: after an allocation whose size is not a multiple of 16, the next allocation starts at an unaligned address.
int main() {
    void* p = m61_malloc(1);
    void* q = m61_malloc(1);
    assert(p && q);
    assert((uintptr_t) q % 16 == 0);   // fails: q == (char*) p + 1
}
A zero-size test: m61_malloc(0) advances buffer by 0, so two such calls return the same pointer, but the specification says distinct active allocations must have distinct addresses.
int main() {
    void* p = m61_malloc(0);
    void* q = m61_malloc(0);
    assert(p && q && p != q);
}
(The fix is buffer += bsz on line 12, together with rounding 0 up to 16 as the later fragments do.)

QUESTION 2C. This allocator detects trailing wild writes with a canary byte stored immediately after each allocation.

void* m61_malloc(size_t sz) {
    // ... check `sz`, maybe reuse a free block ...
    size_t bsz = !sz || sz % 16 ? (sz | 15) + 1 : sz;  // round up to multiple of 16
    if (bsz > size_t(end_buffer - buffer)) {
        return nullptr;
    }
    active.insert({ buffer, sz });
    char* ptr = buffer;
    buffer[sz] = 0xFE;  // canary value
    buffer += bsz;
    return ptr;
}

void m61_free(void* ptr) {
    char* cptr = reinterpret_cast<char*>(ptr);
    // ... return if !ptr, detect invalid and double frees ...
    size_t sz = active[cptr];
    assert((unsigned char) cptr[sz] == 0xFE);  // check that canary value is unchanged
    // ... free the block ...
}

Design a wild-write subtest that demonstrates a problem with this allocator. A correct allocator would report the wild write when the allocation was freed (so the subtest is expected to abort); this allocator, given the right test, will not detect the wild write (so the subtest would not abort). Hint: Our subtest starts like this:

void ww_subtest() {
    char* p = (char*) m61_malloc(16);
    char* q = (char*) m61_malloc(1);
    assert(p && q);
    p[16] = 0;          // wild write: one zero byte just past the allocation

5pt
void ww_subtest() {
    char* p = (char*) m61_malloc(16);
    char* q = (char*) m61_malloc(1);
    assert(p && q);
    p[16] = 0;          // wild write: one zero byte just past the allocation
    q[0] = 0xFE;        // in this allocator, q[0] *is* p[16]: this restores the canary
    m61_free(p);        // a correct allocator reports the wild write here and aborts
}
When sz is a multiple of 16, bsz == sz, so the canary written on line 9 lands at buffer[sz], which is the first byte of the next block (line 10 advances buffer by exactly sz). The canary therefore lives inside whatever is allocated next, rather than in space reserved for it. The wild write p[16] = 0 by itself would be caught by line 18, so the test allocates q, whose first byte is the same byte as p[16], and writes 0xFE there using an ordinary in-bounds write. Line 18 then sees an intact canary and the wild write goes unreported. A correct allocator keeps its canary in space the user can never legitimately write, so q[0] = 0xFE cannot repair it, and m61_free(p) reports the error. Any multiple of 16 works as p’s size. (The fix is to reserve the canary byte, for instance by computing bsz from sz + 1.)

The sequence of allocator calls is what matters. A complete test would run ww_subtest in a subprocess (for instance with run_subtest from utils.hh) and check that the subprocess aborted, but that wrapper is not required for credit.

Partial credit: a subtest that evades detection with a different wild write, such as p[17] = 0 or p[-1] = 0, shows an understanding that a canary protects only the bytes it occupies, but not of this allocator’s particular bug. Such writes are also not ones every correct allocator must catch, so the test would falsely accuse some correct allocators.

QUESTION 2D. This allocator reuses memory. Assume m61_malloc correctly serves requests from freed blocks when possible, with correct splitting. Here is m61_free.

void m61_free(void* ptr) {
    char* cptr = reinterpret_cast<char*>(ptr);
    // ... return if !ptr, check for invalid and double frees ...
    size_t sz = active[cptr];
    size_t bsz = !sz || sz % 16 ? (sz | 15) + 1 : sz;  // round up to multiple of 16
    active.erase(cptr);  // free allocation
    auto next = freed.find(cptr + bsz);  // coalesce with following free block, if any
    if (next != freed.end()) {
        bsz += next->second;
        freed.erase(next);
    }
    freed.insert({ cptr, bsz });
}

Design a test that fails for this allocator. Your test should not involve wild writes. Hint: Our test starts like this:

int main() {
    char* a = (char*) m61_malloc(1 << 20);
    char* b = (char*) m61_malloc(1 << 20);
    char* c = (char*) m61_malloc((6 << 20) - 128);
    assert(a && b && c);

5pt
int main() {
    char* a = (char*) m61_malloc(1 << 20);
    char* b = (char*) m61_malloc(1 << 20);
    char* c = (char*) m61_malloc((6 << 20) - 128);
    assert(a && b && c);
    m61_free(a);                          // lower-addressed block first!
    m61_free(b);
    void* big = m61_malloc(2 << 20);
    assert(big);                          // fails: `a` and `b` never merged
}
m61_free only merges a block with the free block after it (line 7), never with the free block before it. a and b are adjacent, since fresh space is sequential and 1 MiB is a multiple of 16, so b == a + (1 << 20). Freeing a first finds b still active, so no merge happens; freeing b then finds c, still active, so again no merge. The 2 MiB request fits neither 1 MiB block, and after c only 128 bytes of fresh space remain, so m61_malloc returns nullptr. A correct allocator coalesces a and b into a block of at least 2 MiB and succeeds.

The free order is essential: freeing b before a would let line 7 merge a with b, and the test would pass. (Like the torture tests, this test assumes that consecutive fresh allocations are adjacent in memory.)

3. Could have compiled (12 points)

Each part of this question shows x86-64 assembly produced by an optimizing compiler, followed by several C++ functions. Which functions could a correct compiler have translated into that assembly? A function qualifies if the assembly behaves as the C++ abstract machine requires on every call that does not execute undefined behavior. Assume assertions are enabled.

QUESTION 3A.

<some_f>:
        xorl    %eax, %eax
        testl   %edi, %edi
        jne     .L2
        incl    %eax
.L2:
        ret

Which of these functions could compile to that assembly? List all that apply or say “none of the above”.

int f1(int x) {
    return x == 0;
}

int f2(long y) {
    return y == 0;
}

int f3(int z) {
    assert(false);
}

int f4(int m) {
    return !m;
}

int f5(int q) {
    if (q & q == q) {
        return true;
    }
    return false;
}

long f6(unsigned u) {
    return u == 0;
}

int f7(int a, int b) {
    return a == 0;
}

QUESTION 3B.

<some_g>:
        movl    $1, %eax
        ret

Which of these functions could compile to that assembly? List all that apply or say “none of the above”.

bool g1() {
    return true;
}

int g2(int x) {
    return x == x;
}

int g3(int x) {
    return x != 0;
}

int g4(int x) {
    return x + 1 > x;
}

int g5(unsigned x) {
    return x + 1 > x;
}

int g6(int x) {
    return x / x == 1;
}

int awesome[4] = {0, 1, 2, 3};
bool g7(int v) {
    for (int i = 0; i <= 4; ++i) {
        if (awesome[i] == v) {
            return true;
        }
    }
    return false;
}

QUESTION 3C.

<some_h>:
        movl    (%rsi), %eax
        leal    (%rdi,%rax,4), %eax
        ret

Which of these functions could compile to that assembly? List all that apply or say “none of the above”.

int h1(int a, const int* b) {
    return a + 4 * *b;
}

int* h2(int* a, const int* b) {
    return a + *b;
}

int h3(const int* a, int b) {
    return *a + 4 * b;
}

int h4(int a, const long* b) {
    return a + 4 * *b;
}

int h5(int a, const short* b) {
    return a + 4 * *b;
}