Show all solutions Hide all solutions

Test 1

Notes

Assume a Linux operating system running on the x86-64 architecture unless otherwise stated.

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.

The test questions concern Problem Set 1’s dynamic memory allocators and m61 tests that exercise its allocators. An m61 test is a complete program that indicates success by exiting with status 0, and indicates failure by failing an assertion, exiting with a nonzero status, or otherwise terminating abnormally.

1. Allocator testers (15 points)

QUESTION 1A. This tester aims to check that allocations are suitably aligned.

int main() {
    void* p1 = m61_malloc(1);
    void* p2 = m61_malloc(16);
    assert((uintptr_t) p1 % 16 == 0);
    assert((uintptr_t) p2 % 16 == 0);
}

Does this tester succeed or fail with a stub allocator whose m61_malloc always returns nullptr? Explain briefly.

3pt It passes. A null pointer converts to the integer 0, and 0 % 16 == 0, so both assertions hold. The tester never checks whether the allocations succeeded.

QUESTION 1B. Consider this tester.

int main() {
    char* p = (char*) m61_malloc(4);
    assert(&p[0] + 1 == &p[1] && &p[1] + 1 == &p[2] && &p[2] + 1 == &p[3]);
}

Which allocator behaviors does this tester actually check? List all that apply.

1. That the allocation succeeded
2. That the returned allocation is at least as large as requested
3. That distinct allocations are disjoint
4. That the returned allocation is suitably aligned
5. None of the above

2pt #5, none of these. The assertion is a consequence of how pointer arithmetic works on any char*; it is true no matter what address m61_malloc returns.

QUESTION 1C. Which of our four statistics is most difficult to support, and why?

1. total_count
2. total_bytes
3. active_count
4. active_bytes
5. They’re all easy

3pt #4, active_bytes, because it requires that m61_free look up the size that was allocated for a pointer.

QUESTION 1D. Consider m61-once.cc.

static char* buffer = nullptr;
static char* end_buffer = 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) {
        // out of memory in buffer
        return nullptr;
    }

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

void m61_free(void*) {
}

Which kind of test will almost certainly succeed for this allocator? List all that apply.

1. Alignment tests
2. Edge case tests (m61_malloc(0), m61_free(nullptr))
3. Disjoint allocation tests (allocated bytes have disjoint addresses)
4. Reuse tests (freed memory can be reused)
5. None of the above

4pt #3, disjoint allocation tests, is the one property this allocator gets right: the buffer advancement on line 20 ensures allocations don’t overlap, at least for nonzero sizes. Sizes are never rounded up, so only the first allocation is guaranteed aligned; repeated m61_malloc(0) calls return the same address; and m61_free does nothing, so freed memory is never reused.

QUESTION 1E. Describe how to change m61-once.cc so that a call m61_malloc(16000000) might succeed (return a valid non-null pointer). Be specific.

3pt Line 8 becomes buffer = reinterpret_cast<char*>(malloc(16 << 20)); (or any number ≥ 16,000,000). Line 10 should change to use the same constant.

2. Two-faced allocation (15 points)

QUESTION 2A. The m61-lastalloc.cc allocator implements a limited form of memory reuse: when an application frees its most recent allocation, that memory is reused. “I can do better,” said two-faced god Janus. This is the body of m61-janus.cc. You may assume it has no hidden bugs.

static char* buffer = reinterpret_cast<char*>(malloc(8 << 20));
static char* end_buffer = buffer + (8 << 20);
static char* first_buffer = buffer;
static char* last_buffer = buffer;
static std::map<char*, size_t> alloc_sizes;

void* m61_malloc(size_t sz) {
    if (sz == 0 || (sz % 16 != 0 && sz <= (8 << 20))) {
        sz += 16 - (sz % 16); // ensure alignment & unique allocations
    }

    char* cptr;
    if (static_cast<size_t>(first_buffer - buffer) >= sz) {
        first_buffer = first_buffer - sz;
        cptr = first_buffer;
    } else if (static_cast<size_t>(end_buffer - last_buffer) >= sz) {
        cptr = last_buffer;
        last_buffer = last_buffer + sz;
    } else {
        return nullptr;
    }
    alloc_sizes.insert({ cptr, sz });
    return cptr;
}

void m61_free(void* ptr) {
    if (ptr) {
        char* cptr = reinterpret_cast<char*>(ptr);
        auto it = alloc_sizes.find(cptr);
        assert(it != alloc_sizes.end());
        size_t sz = it->second;   // extract size from <cptr, size> pair
        alloc_sizes.erase(it);

        if (cptr == first_buffer) {
            first_buffer = cptr + sz;
        } else if (cptr + sz == last_buffer) {
            last_buffer = cptr;
        }
    }
}

Which line of m61-janus.cc detects invalid frees? Explain briefly.

3pt Line 30, assert(it != alloc_sizes.end()). It asserts that the supplied pointer is in the alloc_sizes map, which only happens if it’s an active allocation.

QUESTION 2B. Which regions of the m61-janus.cc buffer does m61_malloc treat as free space? Refer to specific variables.

2pt The area between buffer and first_buffer is free, and so is the area between last_buffer and end_buffer.

QUESTION 2C. Swapping lines 17 and 18 of m61-janus.cc creates a subtle bug:

last_buffer = last_buffer + sz;  // WRONG ORDER!
cptr = last_buffer;

What kind of tests might detect this bug, but would not fire for the original m61-janus.cc? Explain briefly.

1. Alignment tests
2. Edge case tests (m61_malloc(0), m61_free(nullptr))
3. Disjoint allocation tests (allocated bytes have disjoint addresses)
4. Reuse tests (freed memory can be reused)
5. None of the above

4pt #3, disjoint allocation tests.

A disjoint-allocation tester might detect this bug. The bug causes m61_malloc to return the wrong pointer—the pointer after the allocation, not the pointer to its beginning. This means that in a tester that does, for instance, ptr1 = m61_malloc(128); ptr2 = m61_malloc(16);, ptr1 and ptr2 would be 16 bytes apart, not 128.

Also accept #4, reuse tests, for full credit. With the lines swapped, cptr + sz never equals last_buffer in m61_free, so the top-of-buffer rewind stops working and a loop of m61_malloc(1024)/m61_free pairs exhausts the buffer; the original m61-janus.cc runs that loop indefinitely.

QUESTION 2D. Write or describe a reuse test that succeeds for m61-janus.cc, but fails for the other “hacky” reusing allocators we’ve discussed (m61-lastalloc.cc, which can reuse the most recent allocation, and m61-reuseempty.cc, which marks the whole buffer as free when the active_count statistic drops to 0).

6pt The key intuition here is that m61-janus can reuse memory indefinitely as long as each freed allocation is either the smallest allocation or the largest allocation in address terms. Many tests could be built on that intuition; here’s one:

int main() {
    void* ptr1 = m61_malloc(5 << 20);  // 5 MiB
    void* ptr2 = m61_malloc(11 << 18); // ~2.75 MiB
    assert(ptr1 && ptr2);
    m61_free(ptr1);
    void* ptr3 = m61_malloc(2 << 20);
    assert(ptr3);
}

QUESTION 2E. (Extra credit) Write invariant assertions that relate the values of m61-janus.cc’s first_buffer and last_buffer variables and its alloc_sizes variable.

3pt extra credit.

1. buffer <= first_buffer && first_buffer <= last_buffer && last_buffer <= end_buffer
2. alloc_sizes.empty() || alloc_sizes.begin()->first >= first_buffer
3. alloc_sizes.empty() || std::prev(alloc_sizes.end())->first + std::prev(alloc_sizes.end())->second <= last_buffer