2024 CS 61 Test 1

Show all solutions Hide all solutions

Rules

The exam is open book, open note, limited open computer. You may access the textbook and your own notes. You may also use computers or electronic devices to access your own class materials and public class materials. Specifically:

• You may access your own notes and problem set code electronically.
• You may access Internet sites on which your own notes and problem set code are stored.
• You may access a browser and a PDF reader.
• You may access the course site.
• You may access pages directly linked from the course site, including our lecture notes, exercises, and section notes, and reference material, such as cppreference.com.
• You may access our lecture, problem set, and section code.
• You may run a C++ compiler, including an assembler and linker.
• You may access manual pages and common utilities, including calculators and a Python interpreter.

However:

• You may not access class discussion forums or other question forums such as Stack Overflow.
• You may not access an on-line disassembler or compiler explorer.
• You may not access solutions from any previous exam, by paper or computer, except for those on the course site.
• You may not broadly search the Internet for answers to questions or access other courses’ materials. Stick to our course site.
• You may not interact with AI models (e.g., ask ChatGPT a question).
• You absolutely may not contact other humans with questions about the exam—whether in person, via IM, or by posting questions to forums—with the exception of course staff.

Any violations of this policy are breaches of academic honesty and will be treated accordingly. Please appreciate our flexibility and behave honestly and honorably.

Additionally, students are taking the exam at different times. Do not post publicly about the exam until given permission to do so by course staff. This includes general comments about exam difficulty.

Questions

If you have questions during the exam, write us email at cs61-staff@g.harvard.edu. Don’t use the Edboard. We may not notice Edboard posts, and you aren’t supposed to access the Edboard anyway.

Completing your exam

You have 90 minutes to complete the exam starting from the time you press Start. Different students may have different exams. Enter your answers directly in this form. A green checkmark appears when an answer is saved.

Students with extra time accommodations: If your extra time is not reflected next to the start button, contact course staff and wait for confirmation before pressing it.

You should not need to attach a drawing or other longer notes, but you may do so by adding them to a test1 subdirectory in your cs61-f24-psets repository. Make sure you push your changes to GitHub before time is up, and explain in this form where we should look at your notes.

There is no need to explicitly “submit” the exam. Your changes are automatically saved with timestamps. We’ll grade the latest version saved within your exam window.

Notes

Assume a Linux operating system running on the x86-64 architecture unless otherwise stated. If you get stuck, move on to the next question. If you’re confused, explain your thinking briefly for potential partial credit.

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.

1. Our governing body (20 points)

The Harvard Corporation has attempted to complete pset 1. Their implementation has a lot of problems, but they refuse to admit they’ve done anything wrong. Your job is to prove that they have problems by attacking their implementation.

QUESTION 1A. This code, from m61_calloc, intends to detect integer overflow. Write a call to m61_calloc that causes integer overflow at the marked line, but does not trigger the check. (We’re omitting file and line parameters.)

void* m61_calloc(size_t count, size_t sz) {
    if (count * sz > default_buffer.size) { // check for overflow
        return nullptr;
    }
    void* ptr = m61_malloc(count * sz);
    ...

4pts. m61_calloc((size_t) -1, (size_t) -1); There are many possible correct answers. Any two numbers that cause overflow but whose product exceeds SIZE_MAX and overflows to less than default_buffer.sz is correct.

QUESTION 1B. They tried again with this version. Write a call to m61_calloc that causes undefined behavior with this version.

void* m61_calloc(size_t count, size_t sz) {
    if (count > default_buffer.size / sz) { // check for overflow
        return nullptr;
    }
    void* ptr = m61_malloc(count * sz);
    ...

4pts. m61_calloc(1, 0) This causes a divide by 0 error. Any answer where sz==0 is correct.

QUESTION 1C. This code, from m61_malloc and m61_free, intends to account for active allocations. (This is from Phase 1 of the pset, before memory reuse.) Write a sequence of calls to m61_malloc and/or m61_free that cause num_active_alloc to become negative, which should be impossible.

long num_active_alloc = 0;
long num_total_alloc = 0;

void* m61_malloc(size_t sz) {
    if (sz == 0) {
        return nullptr;
    }
    ...
    ++num_active_alloc;
    ++num_total_alloc;
    return ptr;
}

void* m61_free(void* ptr) {
    --num_active_alloc; // not reusing memory, so nothing else to do
}

4pts. m61_free(nullptr) The m61_free function does no error checking before decrementing the num_active_alloc variable. Any sequence of calls with more frees than allocations, will lead to a negative num_active_alloc counter.

QUESTION 1D. This code, from m61_malloc, attempts to account for alignment requirements.

void* m61_malloc(size_t sz) {
    if (default_buffer.pos + sz > default_buffer.size) {
        return nullptr;
    }
    if (default_buffer.pos % 16 != 0) {
        default_buffer.pos += default_buffer.pos % 16; // align allocation
    }
    void* ptr = &default_buffer.buffer[default_buffer.pos];
    default_buffer.pos += sz;
    return ptr;
}

But the // align allocation line is wrong. What should it be instead?

4pts. default_buffer.pos += 16 - default_buffer.pos % 16; There are a couple of syntaxes for this alignment; any expression that rounds up to the nearest multiple of 16 is correct.

QUESTION 1E. Given Question 1D’s uncorrected code, write a sequence of m61_malloc calls where the last call will return a nonnull pointer outside the bounds of default_buffer. (Recall that default_buffer.size == 0x800000.)

4pts. m61_malloc(0x7FFFFF); m61_malloc(1) or similar. The first m61_malloc call sets default_buffer.pos very close to default_buffer.size. Then the next m61_malloc call, the first check passes, but then the alignment adds more than default_buffer.size - default_buffer.pos, so the next pointer returned is outside of the buffer.

2. An investigation (15 points)

These questions concern an investigation into data representation for standard C++ data structures, similar to the one we performed in Lecture 3. A set of objects are read out of standard input and inserted, in sorted order, into a data structure a of type CONTAINER<T>. Then the following loop is used to print the contents of the data structure:

CONTAINER<T> a;
for (auto& x : a) {
    print_object(x);
    printf("\n");
}

This prints the data representations of the contents of the container, starting from the first element and going to the last. Elements are separated by a blank line.

You will use the output of that loop to guess the likely values for CONTAINER and T. CONTAINER is always either std::vector or std::list, but T might be any basic type or well-known C++ library type.

QUESTION 2A. Give likely CONTAINER (vector or list) and T for this output.

7208'0000'0020  01 00 00 00

7208'0000'0024  02 00 00 00

7208'0000'0028  03 00 00 00

7208'0000'002c  04 00 00 00

3pts. std::vector, int The addresses are sequential with differences of 4 and we have elements of four bytes in each address.

QUESTION 2B. Give likely CONTAINER and T for this output.

7204'0000'0020  31

7204'0000'0021  32

7204'0000'0022  33

3pts. std::vector, char The addresses are sequential with differences of 1 and we have elements of 1 byte in each address.

QUESTION 2C. Give likely CONTAINER and T for this output.

7208'0000'0070  31

7208'0000'0090  32

7208'0000'0050  33

7208'0000'00b0  34

3pts. std::list, char Since the addresses are non sequential the container cannot be a vector. The values are 1 byte each and happen to be the ASCII values for the characters 1, 2, 3, and 4.

QUESTION 2D. Give likely CONTAINER and T for this output.

720c'0000'0040  50 00 00 00 0c 72 00 00  0a 00 00 00 00 00 00 00
720c'0000'0050  43 53 36 31 2d 52 6f 63  6b 73 00 00 00 00 00 00

720c'0000'0010  20 00 00 00 0c 72 00 00  05 00 00 00 00 00 00 00
720c'0000'0020  48 65 6c 6c 6f 00 00 00  00 00 00 00 00 00 00 00

720c'0000'0070  90 00 00 00 0c 72 00 00  23 00 00 00 00 00 00 00
720c'0000'0080  23 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00

3pts. std::list, std::string Since the addresses are non sequential, the container cannot be a vector. The first 8 bytes of each value are the address of the string. The second 8 bytes is the length of the string. And the last 16 bytes is the buffer that contains the string.

QUESTION 2E. Give likely CONTAINER and T for this output.

7210'0000'0000  01 00 00 00 00 00 00 00

7210'0000'0008  02 00 00 00 00 00 00 00

7210'0000'0010  03 00 00 00 00 00 00 00

7210'0000'0018  04 00 00 00 00 00 00 00

7210'0000'0020  05 00 00 00 00 00 00 00

3pts. std::vector, unsigned long or another 8 byte type

3. Abstract machine (20 points)

We have studied both properties of the C++ abstract machine, which should be true across all implementations, and properties of a typical implementation (x86-64 Linux). For each of the following statements, say whether it is true for any implementation of the C++ abstract machine; true on the x86-64 implementations we’ve studied; or not true. In your answer, write “abstract machine”, “conventional x86-64”, or “false”.

QUESTION 3A. sizeof(char) == 1.

2pts. Abstract machine. The size of a character is always 1 as defined by the C++ abstract machine, as we mentioned in Lecture. (The humorous ISO C++ FAQ says "No, sizeof(char) is always 1. Always. It is never 2. Never, never, never.")

QUESTION 3B. For any type T, and given an array T arr[1], sizeof(arr) == sizeof(T).

2pts. Abstract machine. As defined by the C++ standard, an array T[N] has size N * sizeof(T). An array is a contiguous region of the object, so an array of size one is just a singular instance of the object.

QUESTION 3C. For any struct type T, sizeof(T) > 1.

2pts. False. Consider struct foo {char x}. This will have a size of exactly 1 (refer to 3A), and so therefore since we provided a counterexample, this statement is false.

QUESTION 3D. The stack grows down, so if main calls function f, then the addresses of f’s local variables are smaller than the addresses of main’s local variables.

2pts. Conventional x86-64, OR False (because we default to sanitizers this semester, and with sanitizers stacks don’t always grow down). Stacks grow down on the x86-64 system we've studied in class, but they may not necessarily grow down on a different machine. If the stack grows down, then the f’s local variables are smaller than main’s local variables.

QUESTION 3E. The address of a dynamically-allocated object (such as a new int) is larger than the address of any global variable.

2pts. Conventional x86-64. On the machine we've studied in class, memory segments were laid out in order of increasing address of code, data, heap, stack. Dynamically allocated objects live in the heap, while global variables live in the data segment. However, the layout of memory segments is a convention of the CPU, and is not defined by the C++ abstract machine.

QUESTION 3F. The address of a dynamically-allocated object is different from the address of any global variable.

2pts. Abstract machine. The abstract machine defines variables with static lifetime (i.e. global variables) as those that exist for the lifetime of the program, while dynamically-allocated objects may be cleaned up before the program ends. Therefore, a dynamically-allocated object could not have the same address as a global variable.

QUESTION 3G. Every dynamically-allocated object has a unique address.

2pts. False. Because dynamically allocated objects may be cleaned up and reallocated, it is plausible that a sequence of malloc, free, malloc allocates the same address again after it is freed.

QUESTION 3H. For a simple struct object with components T1 x1; T2 x2; ...; Tn xn;, the address of the xn component is always greater than the address of the x1 component.

2pts. Abstract machine. The C++ abstract machine defines the members of a struct to be laid out in order. If n > 1, then the address of the xn component will necessarily be after the address of x1.

QUESTION 3I. For a function with local variables T1 x1; T2 x2; ...; Tn xn;, the address of the xn object is always greater than the address of the x1 object.

2pts. False. Neither the system we've studied in class nor the C++ abstract machine define the ordering of local variables in memory. Because of this, the compiler is free to re-order local variables as it wants.

QUESTION 3J. The amount of padding added at the end of a struct for alignment purposes is always less than 16 bytes.

2pts. Conventional x86-64. The C++ abstract machine does have alignment, but the fact that it is always less than 16 bytes is defined by the x86-64 Conventions. The abstract machine says that the size must be a multiple of the alignment, but doesn't specify upper bounds on what that alignment is.

We can imagine a system where:

struct foo {
    T x; // T has alignment 32
    char y;
    // we will need 31 bytes of alignment here
};

Whereas the system we studied in class (Conventional X86-64) has std::max_align_t == 16, so we can conclude there is never a need to add at least 16 bytes of padding.

4. Assembly (20 points)

Here is some assembly produced by a compiler for a C++ function named f. The function involves traversing an array.

_Z1f....:
    xor    %eax,%eax
    test   %rsi,%rsi
    je     L2
L1:
    dec    %rsi
    lea    (%rdi,%rsi,4),%rdx
    xor    %ecx,%ecx
    mov    (%rdx),%ecx
    cmp    $0x5,%ecx
    jae    L1
    add    %ecx,%eax
    test   %rsi,%rsi
    jne    L1
L2:
    ret

QUESTION 4A. What is the most likely number of parameters in the C++ declaration for function f? Explain briefly.

2pts. 2, because the function uses %rdi and %rsi Starting from the top of the function, %rsi is used in the instruction test %rsi,%rsi. %rdi is used in the instruction lea (%rdi,%rsi,4),%rdx. None of the other argument registers present in the assembly are used as a source register.

QUESTION 4B. What are the likely type(s) of the parameter(s)?

2pts. The first parameter is a pointer because it's used in a lea instruction, probably to an array of unsigned int since the scale in the lea instruction is 4. The second parameter is an index size as it's used as the base in the lea instruction, likely a size_t.

QUESTION 4C. What is the likely type of the return value?

1pt. unsigned or int. We're dereferencing the pointer stored in %rdx, which points to an int as discussed in 4B.

QUESTION 4D. Give argument values for which the function returns 0.

2pts. [any pointer], 0 If 0 is the second argument (%rsi) then test %rsi, %rsi is true, the jump to L2 is taken and the function returns with %eax set to 0.

QUESTION 4E. Give argument values for which the source C++ function would always execute undefined behavior.

2pts. 0, 1 (that is, nullptr, 1). This is because %rdi stores a pointer, and we dereference this pointer later on. Any index greater than 1 works. s

QUESTION 4F. List an instruction in the function definition that is redundant (i.e., could be removed without changing function behavior).

2pts. xor %ecx, %ecx the value of %ecx is overwritten immediately after.

QUESTION 4G. Does the function traverse the array “forwards” (from index 0 up) or “backwards” (from index N down)?

1pt. Backwards We can see this in the line dec %rsi, the value of the index is decreasing, and the that we exit the loop by testing of %rsi is storing 0 in the line test %rsi, %rsi.

QUESTION 4H. Write C++ code that could have compiled into the function.

4pts.

unsigned f(unsigned* x, size_t n) {
    unsigned sum = 0;
    while (n > 0) {
        --n;
        if (x[n] < 5) {
            sum += x[n];
        }
    }
    return sum;
}

We loop through the array backwards, find the address of each element using the index, dereference the address, and add the value to %eax (which starts at 0) if the element is less than 5, and return %eax at the end.

QUESTION 4I. Under what conditions might f’s C++ declaration have had more than the most likely number of parameters? List all that apply; explain briefly if unsure.

1. The function definition did not use all of the declared parameters.
2. The compiler determined that the function code using the surplus parameters had no observable effect.
3. The compiler determined that the function code using the surplus parameters was only invoked if earlier code caused undefined behavior.
4. Multiple function parameters were packed into single registers for the purpose of argument passing.
5. None of the above.

2pts. 1, 2, 3 1: If the function doesn't use the parameter, we won't see an instruction using it. 2: The compiler can write no assembly instructions if it determined that the parameters have no observable effect. 3: The compiler is allowed to assume that undefined behavior is never going to happen. 4:

QUESTION 4J. Under what conditions might f’s C++ declaration have had fewer than the most likely number of parameters? List all that apply; explain briefly if unsure.

1. At least one function parameter was a reference argument.
2. At least one function parameter had size larger than 8 bytes.
3. The compiler determined that callers of the function were passing more arguments than the declaration had parameters.
4. None of the above.

2pts. Only 2. If 1 were true, said parameter would likely be passed in as a pointer (and still appear in the assembly). 2 is possible. If we have:

struct foo_t {
    long x;
    long y;
};
void f(foo_t bar);

Then it is possible that f will simply split the components inside the struct into two registers, despite taking in only one argument. If 3 were true, the compiler would throw an error. 4 is false because 2 is true.

5. Assembly matching (20 points)

The following eight assembly functions each take at least one argument and return a result. The functions can be paired so that the two elements of each pair always produce identical results given identical parameters. Your job is to find the matching pairs.

One of these functions uses an instruction you haven’t seen before: rorq, or rotate right. Like shrq, the bitwise shift-right instruction, rorq SRC, DST shifts the bits in DST right by SRC places; but then rorq takes the bits that were shifted off and moves them into the vacated more-significant places in DST. Here’s a C++ implementation of rorq:

unsigned long rorq(unsigned src, unsigned long dst) {
    for (unsigned i = 0; i < src; ++i) {
        unsigned long low_bit = dst & 1;
        dst = (dst >> 1) | (low_bit << 63);  // rotate by one place
    }
    return dst;
}

The functions:

• f0:
      xorl %eax, %eax
      ret
  

• f1:
      imulq $2, %rsi
      leaq (%rdi,%rsi), %rax
      movw (%rax), %ax
      movzwl %ax, %eax
      retq
  

• f2:
      movq $0, %rax
      movw (%rdi,%rsi,2), %ax
      retq
  

• f3:
      movq %rdi, -8(%rsp)
      testq %rsi, %rsi
      jge L4
      movl %edi, -4(%rsp)
      shrq $32, %rdi
      movl %edi, -8(%rsp)
  L4:
      movq -8(%rsp), %rax
      retq
  

• f4:
      movq %rdi, %rdx
      addq %rdi, %rdx
      addq %rdi, %rdx
      addq %rdi, %rdx
      leaq -1(%rdx), %rax
      ret
  

• f5:
      salq $0x2, %rdi
      movq %rdi, %rax
      decq %rax
      ret
  

• f6:
      movq %rsi, %rcx
      cmpq $0, %rcx
      sets %cl
      negl %ecx
      andl $0x20, %ecx
      rorq %cl, %rdi
      movq %rdi, %rax
      retq
  

• f7:
  L1:
      testq %rax, %rax
      je L2
      decq %rax
      jmp L1
  L2:
      ret
  

QUESTION 5A. Name the four matching pairs, or as many of them as you can find.

12pts.

• f0 and f7 always return 0.
• f1 and f2 access an array of shorts (arg1[arg2]).
• f3 and f6 optionally swap the 32-bit words in their first argument. The swap is only performed if the second argument is less than 0.
• f4 and f5 return arg1 * 4 - 1.

QUESTION 5B. Which function(s) access the red zone?

2pts. f3 is the only function that accesses addresses less than %rsp which is in the red zone.

QUESTION 5C. Which function(s) contain a loop?

3pts. f7 is the only snippet that involves a jump statement to earlier in the code, a requirement for a loop.

QUESTION 5D. Which function(s) might access objects in a caller’s local variables, and under what circumstances?

3pts. f1 and f2, if the caller passes a pointer to a local array as the first argument

6. The end (5 points)

QUESTION 6A. What topics are you interested in spending more time on? Any answer but no answer will receive full credit.

5pts