2025 CS 61 Test 1

Show all solutions Hide all solutions

1. Tracking books (25 points)

Angela Davis is writing a program to keep track of her books. She’s defined a struct to represent information about a book:

struct Book {
    std::string title;
    unsigned pub_year;
};

QUESTION 1A. Angela declares her set of books using this declaration:

#include "angelas_books.hh" /* for declaration of Book */

Book myBooks[10];

int main() { ... }

Which segments might hold the myBooks[0] object? List all that apply.

1. The text segment
2. The code segment
3. The .rodata read-only data segment
4. The data segment
5. The heap
6. The stack
7. A line segment
8. The AI-powered B2B SaaS market segment
9. None of the above

2pts. This is a writable global variable, so only #4.

QUESTION 1B. Write a code fragment including a declaration of Book myBooks[10] that places myBooks[0] in a different segment than those you listed above, and say which segment you chose.

3pts. Here are two examples:

#include "angelas_books.hh"

int main() {
    Book myBooks[10];                // memory is on stack
    Book* myBooks = new Book[10];    // memory is in heap
}

QUESTION 1C. Here are two declarations of array-like data structures containing 10 Books:

Book myBooks_arr[10] = {
    { "Blues Legacies and Black Feminism", 1998 },
    { "Notes on the State of Virginia", 1785 },
    { "If They Come in the Morning", 1971 }, ...
};
std::vector<Book> myBooks_vec = {
    { "Blues Legacies and Black Feminism", 1998 },
    { "Notes on the State of Virginia", 1785 },
    { "If They Come in the Morning", 1971 }, ...
};

List all the true statements.

1. sizeof(myBooks_arr) < sizeof(myBooks_vec)
2. sizeof(myBooks_arr) == sizeof(myBooks_vec)
3. sizeof(myBooks_arr) > sizeof(myBooks_vec)
4. sizeof(myBooks_arr[0]) < sizeof(myBooks_vec[0])
5. sizeof(myBooks_arr[0]) == sizeof(myBooks_vec[0])
6. sizeof(myBooks_arr[0]) > sizeof(myBooks_vec[0])

3pts. #3 is true: Every vector has the same size, because vector stores its actual elements elsewhere, on the heap; and that size is less than the size of 10 Books.

And #5 is true. Whether we dereference a vector or a plain array, the type of the resulting element is a Book.

QUESTION 1D. What is the most likely amount of padding the compiler will add to struct Book? Select one and explain briefly.

0. 0 bytes
1. 1 byte
2. 2 bytes
3. 3 bytes
4. 4 bytes
5. 5 bytes
8. 8 bytes
12. 12 bytes
16. 16 bytes
17. Other

2pts. std::string contains a pointer to character data, and pointers have alignment 8. So the likely padding is 4 bytes, inserted after pub_year to ensure Book’s size is a multiple of 8 (its alignment).

QUESTION 1E. Now, assume that you know nothing about the implementation of std::string: assume it could have any valid x86-64 Linux size and alignment. Given that, how much padding might the compiler add to struct Book (not including padding inside std::string)? List all that apply.

0. 0 bytes
1. 1 byte
2. 2 bytes
3. 3 bytes
4. 4 bytes
5. 5 bytes
8. 8 bytes
12. 12 bytes
16. 16 bytes
17. Other

3pts. The maximum alignment on x86-64 is 16, so the alignment of std::string is 1, 2, 4, 8, or 16.

• If std::string has alignment 16, then its size is a multiple of 16, and 12 bytes of padding are required after pub_year to bring the size of Book to a multiple of 16.
• If it has alignment 8, then 4 bytes of padding are required.
• If it has alignment 4, then 0 bytes of padding are required.
• If it has alignment 2, then we might need to introduce 2 bytes of padding before pub_year to bring pub_year’s offset to a multiple of 4.
• Similarly, if it has alignment 1, we might need to introduce 1, 2, or 3 bytes of padding before pub_year.

So the answer is 0, 1, 2, 3, 4, or 12.

QUESTION 1F. True or false: In addition to potential padding within struct Book, the compiler may introduce additional padding between elements of the myBooks array.

2pts. False. There is never any padding between array elements.

QUESTION 1G. For this and the following questions, you should assume that all objects may have any values allowed by their corresponding types—so b.pub_year might be 9349812, even though that year hasn’t happened yet.

How might the following function behave? List all that apply.

bool check_year(const Book& b) {
    return b.pub_year == 2024;
}

1. check_year(b) might return true without executing undefined behavior
2. check_year(b) might return false without executing undefined behavior
3. check_year(b) might execute undefined behavior
4. check_year(b) might infinite loop
5. None of the above

3pts. #1 and #2 are both possible.

QUESTION 1H. How might the following function behave? List all that apply.

bool check_year(const Book& b) {
    return b.pub_year == -1;
}

1. check_year(b) might return true without executing undefined behavior
2. check_year(b) might return false without executing undefined behavior
3. check_year(b) might execute undefined behavior
4. check_year(b) might infinite loop
5. None of the above

3pts. #1 and #2 are both possible. Even though b.year is unsigned, the comparison UINT_MAX == -1 returns true without undefined behavior.

QUESTION 1I. This function can execute undefined behavior; explain briefly how.

int current_year = ...;

// Test whether this book was published at least `n` years ago
bool check_old(const Book& b, int n) {
    return b.pub_year <= current_year - n;
}

2pts. The function may execute undefined behavior if current_year - n overflows.

QUESTION 1J. Describe how to modify check_old so that it never executes undefined behavior, but otherwise behaves identically.

2pts. If n or current_year are made unsigned, then the function will not execute undefined behavior. Or you can change the way the arithmetic is done to ensure it’s done on unsigned values: return b.pub_year + n <= current_year;. Or this cast works too: return b.pub_year <= current_year - (unsigned) n;

2. Unprinting objects (20 points)

The following printout was produced by print_object(*ptr), where A* ptr is a pointer to some struct type A with three members.

5030'0000'0040  11 18 00 00 00 00 00 00  1c 17 67 20 fd 7f 00 00
5030'0000'0050  68 65 6c 6c 6f 36 31 00

QUESTION 2A. One of struct A’s members has pointer type. Is that member first, second, or third in the struct? Explain briefly.

2pts. The pointer is second in the struct. This is because only bytes 8–15 of the printed data contain a value that looks like a pointer—specifically, a pointer to the stack.

QUESTION 2B. What are sizeof(A) and alignof(A)?

3pts. 24 and 8.

QUESTION 2C. The last 8 bytes of *ptr comprise an array of characters, declared as struct A member unsigned char s[8]. Given this, match each expression, on the left, which the corresponding value, on the right. You may use a value once, twice, or not at all.

• 1. ptr->s[0] & ptr->s[0]
  2. ptr->s[0] | ptr->s[0]
  3. ptr->s[0] ^ ptr->s[0]
  4. ptr->s[0] & ptr->s[1] & ptr->s[2]
  5. ptr->s[0] | ptr->s[1] | ptr->s[2]
  6. strlen(ptr->s)
• 1. 0x00
  2. 0x07
  3. 0x60
  4. 0x65
  5. 0x68
  6. 0x6f
  7. None of the above

4pts. 1–E, 2–E, 3–A, 4–C, 5–G, 6–B

QUESTION 2D. The remaining questions in this part focus on assembly. In each question, register %rdi initially holds the value of ptr.

Assuming register %rsi holds an integer index i, write a single instruction that loads the value of byte ptr->s[i] into register %rax. (For partial credit, write an arithmetic expression that computes the address of ptr->s[i] from %rdi and %rsi.)

4pts. movzbl 16(%rdi,%rsi), %eax (or movzbq 16(%rdi,%rsi), %rax)

The expression is 16 + %rdi + %rsi.

QUESTION 2E. Recall that one of A’s members has pointer type. Write one or more instructions that load the 8-byte value pointed to by that pointer into register %rcx.

4pts. movl 8(%rdi), %rsi; movq (%rsi), %rcx

QUESTION 2F. What numeric value is in register %rax when the processor reaches .L2? Hexadecimal preferred.

    leaq 0x10(%rdi), %rax
.L1:
    cmpb $0x50, (%rax)
    jb .L2
    addq $1, %rax
    jmp .L1
.L2:

3pts. The assembly searches the ptr->s array for an unsigned character whose value is less than 0x50 and returns its address. Here, the result is 0x5030'0000'0055.

3. A Garden of Earthly Delights (25 points)

The questions in this section concern Hieronymus Bosch’s implementation of problem set 1.

QUESTION 3A. Here’s some of Heer Bosch’s implementation:

std::map<uintptr_t, size_t> active_allocs;
std::map<uintptr_t, size_t> freed_allocs;

void m61_free(void* ptr) {
    uintptr_t addr = reinterpret_cast<uintptr_t>(ptr);
    auto active_it = active_allocs.find(addr);
    assert(active_it != active_allocs.end());

    size_t sz = active_it->second;
    auto [ free_it, inserted ] = freed_allocs.insert({ addr, sz });
}

Code from m61_malloc (not shown, but assume it is correct) inserts information about successful allocations into active_allocs.

Give a valid sequence of calls to m61_malloc and/or m61_free that should run without error, but that always fail on Bosch’s implementation. (“Fail” means either assertion failure or undefined behavior.)

3pts. m61_free(nullptr);

QUESTION 3B. Give an invalid sequence of calls to m61_malloc and/or m61_free that should always fail, but that inappropriately succeed on Bosch’s implementation. Explain briefly.

4pts.

void* ptr = m61_malloc(10);
m61_free(ptr);
m61_free(ptr);

Heer Bosch has forgotten to remove a record from active_allocs after that allocation was freed.

QUESTION 3C. Now Heer Bosch is implementing free map coalescing: when an allocation is freed, it should be coalesced with any freed neighbors. He’s added 5 new lines to the end of m61_free.

void m61_free(void* ptr) {
    uintptr_t addr = reinterpret_cast<uintptr_t>(ptr);
    auto active_it = active_allocs.find(addr);
    assert(active_it != active_allocs.end());

    size_t sz = active_it->second;
    auto [ free_it, inserted ] = freed_allocs.insert({ addr, sz });

    auto next_it = std::next(free_it);
    if (next_it != freed_allocs.end() && next_it->first == addr + sz) {
        free_it->second += next_it->second;
        freed_allocs.erase(next_it);
    }
}

Which of these statements appear to be true based on this code? List all that apply.

1. The size_t in active_allocs is unpadded, and equals the size provided to m61_malloc by the user.
2. The size_t in active_allocs is padded: it accounts for any padding and/or boundary write protection, and might be larger than the size provided by the user.
3. Heer Bosch’s code contains a partial implementation of internal metadata.
4. Heer Bosch’s code will never dereference an invalid iterator.
5. None of the above.

3pts. #2 and #4.

QUESTION 3D. Give a sequence of m61_malloc and m61_free calls that, if executed on this code, will result in a freed_allocs map that is not maximally coalesced.

4pts. Heer Bosch coalesces right, but not left; so if we free in descending order by address, the map will not be coalesced.

Almost certainly Heer Bosch’s m61_malloc code allocates in the natural way, i.e., ascending order by address; so this will work:

void* ptr1 = m61_malloc(10);
void* ptr2 = m61_malloc(10);
m61_free(ptr1);
m61_free(ptr2);

But you can also make it independent of allocation order.

std::vector<void*> ptrs = { m61_malloc(10), m61_malloc(10) };
std::sort(ptrs.begin(), ptrs.end());
m61_free(ptrs[0]);
m61_free(ptrs[1]);

QUESTION 3E. Heer Bosch has now started to implement boundary write protection. Here’s some code from his m61_malloc:

const int MY_CANARY = 0xDEADBEEF;

void* m61_malloc(size_t sz) {
    ... check for overflow, sz == 0, etc. ...

    void* ptr = find_free_space(sz);
    if (!ptr) {
        return nullptr;
    }
    // Otherwise, `ptr` points to a block of at least `sz` free bytes.

    uintptr_t addr = reinterpret_cast<uintptr_t>(ptr);
    int* a = reinterpret_cast<int*>(addr + sz);
    *a = MY_CANARY;

    return ptr;
}

True or false? Any non-null pointer returned by find_free_space must be 16-byte aligned.

3pts. True. The value returned by find_free_space is returned unchanged from m61_malloc, and a pset requirement is that values returned by m61_malloc are aligned to alignof(std::max_align_t), which is 16.

QUESTION 3F. Briefly list any problems you see with Heer Bosch’s boundary write implementation, based on its code and comments, or explain why it’s essentially correct.

4pts.

1. The comment indicates Heer Bosch has not allocated enough space for the canary. He should have called find_free_space(sz + sizeof(int)).
2. The canary is being stored at a possibly-unaligned location.

QUESTION 3G. Finally, Heer Bosch’s implementation of m61_calloc is as follows.

void* m61_calloc(size_t count, size_t sz, const char* file, int line) {
    if (count > default_buffer.size / sz) { // check for overflow
        return nullptr;
    }
    return m61_malloc(count * sz, file, line);
}

List the true statements.

1. The overflow check is necessary to prevent undefined behavior on line 5.
2. The overflow check is necessary to prevent line 5 from allocating less memory than the user intended.
3. The overflow check will correctly detect any case where count * sz overflows.
4. The overflow check can cause undefined behavior for some inputs.
5. Heer Bosch has forgotten an important function of m61_calloc.
6. None of the above.

4pts. #2, #3, #4, and #5.

An overflow check is not necessary to prevent line 5 from executing undefined behavior: multiplication of unsigned integers does not cause undefined behavior. But if overflow occurred, line 5 might request less memory than the user intended. The overflow check will definitely detect any case where count * sz overflows, but it can also cause a division by 0, which is undefined behavior. Finally, Heer Bosch forgot to zero out the allocated memory.

4. apply_f yourself (30 points)

The following questions concern this assembly code, which was compiled from a C++ function called apply_f.

_Z7apply_fRSt6vectorIiSaIiEE:
    pushq   %rbp
    pushq   %rbx
    subq    $8, %rsp
    movq    (%rdi), %rbx
    cmpq    8(%rdi), %rbx
    je      .L1
    movq    %rdi, %rbp
.L3:
    movl    (%rbx), %edi
    addq    $4, %rbx
    call    _Z1fi
    movl    %eax, -4(%rbx)
.L4:
    cmpq    %rbx, 8(%rbp)
    jne     .L3
.L1:
    addq    $8, %rsp
    popq    %rbx
    popq    %rbp
    ret

QUESTION 4A. Which callee-saved registers does this function use, other than %rsp?

2pts. %rbp and %rbx.

QUESTION 4B. Why has the compiler elected to use these callee-saved registers? Select the most likely answer.

1. Callee-saved registers are more efficient than caller-saved registers.
2. Many caller-saved registers are used for function parameters or return values.
3. Callee-saved registers let the compiler avoid repeatedly restoring registers inside the loop.
4. Callee-saved registers are used to store frame pointers and enhance debuggability.
5. None of these answers are good explanations.

2pts. #3

QUESTION 4C. Which lines of this assembly, if any, are only necessary to ensure stack alignment? Refer to specific line numbers.

3pts. Lines 4 and 18 (subq $8, %rsp and addq $8, %rsp).

QUESTION 4D. What are some likely return types for apply_f? List all that apply.

1. void
2. int
3. unsigned
4. long
5. char*
6. None of the above

3pts. #1 void only. The jump from line 7 to .L1 will return without having loaded anything into %rax, which can only happen for functions returning void.

QUESTION 4E. According to the function’s mangled name, it takes a single parameter of type std::vector<int>&; let’s name that parameter v. How does the function use v? List all that apply.

1. The function modifies v itself (for instance, by adding or removing elements).
2. The function modifies the elements of v.
3. If v is empty, the function does nothing.
4. None of the above.

4pts. #2 and #3

QUESTION 4F. Which of the following are compatible with the representation of std::vector<int> implied by this assembly? List all that apply.

• struct vecrep_1 {
      int* begin;
      size_t size;
  };
  

• struct vecrep_2 {
      int* begin;
      int* capacity;
      int* end;
  };
  

• struct vecrep_3 {
      int* begin;
      int* end;
  };
  

• struct vecrep_4 {
      int element_space[4];
      int* begin;
      int* end;
  };
  

4pts. Only vecrep_3.

QUESTION 4G. Change the function’s assembly so that it behaves exactly the same, but does not use the instruction je .L1 (line 7). Say which lines of assembly you are replacing (including, but not limited to, line 7) and give the new instructions. For full credit, your replacement instructions shouldn’t use label .L1 either.

3pts. Replace lines 6–8 with

movq %rdi, %rbp
jmp .L4

QUESTION 4H. The following assembly was compiled from the same apply_f C++ source code as the assembly above. The only difference is that we changed the definition of function f.

_Z7apply_fRSt6vectorIiSaIiEE:
        movq    (%rdi), %rax
        movq    8(%rdi), %rcx
        cmpq    %rcx, %rax
        je      .L8
.L10:
        movl    (%rax), %edx
        addq    $4, %rax
        leal    (%rdx,%rdx,4), %edx
        movl    %edx, -4(%rax)
        cmpq    %rcx, %rax
        jne     .L10
.L8:
        ret

Which optimizations are most responsible for this dramatically different assembly? List all that apply.

1. Tail call elimination
2. Argument elision
3. Loop unrolling
4. Inlining
5. None of the above

3pts. #4 Inlining. The compiler has removed the explicit call instruction and integrated f’s instructions into apply_f. That, in turn, made the use of callee-saved registers unnecessary, so the compiler uses caller-saved registers that don’t need to be saved and restored.

QUESTION 4I. Write a C++ function corresponding to the f from Question 4H.

3pts.

int f(int x) {
    return 5 * x;
}

QUESTION 4J. Write a C++ function corresponding to apply_f.

3pts.

void apply_f(std::vector<int>& v) {
    for (auto& x : v) {
        x = f(x);
    }
}

5. The end (5 points)

QUESTION 5A. How could we make office hours more useful for you? Any answer but no answer will receive full credit.

5pts