Midterm Quiz (Spring 2025) #

Show all solutions Hide all solutions

Rules #

Read these rules carefully! In this quiz, you CANNOT interact with others, use AI tools, or access shared documents or editors. If you violate these rules, we will treat this as a matter of academic integrity and follow the process for academic code conduct violations.

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

• You may access a browser and a PDF reader.
• You may access your own notes and assignment code electronically.
• You may access the course site.
• You may access our lecture notes, exercises, and section notes.
• You may access our lecture, assignment, and section code.
• You may access online resources, including search engines, Wikipedia, and other websites.
• You may run a C or C++ compiler, including an assembler and linker.
• You may access manual pages and common utilities, including calculators and a Python interpreter.

However:

• You cannot use AI tools (like ChatGPT, Github Copilot, Google Bard, and others) during the quiz, with the exception of "AI overview" text from a normal search engine query.
• You cannot contact other humans with questions about the quiz — whether in person, via IM, or by posting questions to forums — with the exception of course staff.
• You cannot interact with other humans via chat, text, phone calls, shared Google Docs, or anything like it.
• You cannot ask the quiz questions on class discussion forums or other question forums such as Stack Overflow.
• You cannot access solutions from any previous quiz, from this course or others, by paper or computer, except for those on the CS 300 course site.

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 quiz at different times. Do not post publicly about the quiz until given permission to do so by course staff. This includes general comments about quiz difficulty.

Completing your quiz #

You have 120 minutes to complete the quiz starting from the time you press "Start".

Different students may have different quizzes. 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 midterm subdirectory in your cs300-s25-projects 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.

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.

1. Undefined behavior (12 points) #

Consider the following C program. Specifically, for each point in the code marked "Point <N>", consider whether executing that line causes undefined behavior.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* car_size;
char* best_car;

void transform_name(char* p) {
    char* local;
    local = p;
    local[1] = 'X';
    best_car = local;
}

void update_size(int* p) {
    car_size = p;
}

int main() {
    char* car1   = "Sedan";   // Read-only string literal
    char car2[7] = "Hybrid";  // Array on stack (6 chars + null terminator)

    transform_name(car1);  // <------------------- POINT 1
    transform_name(car2);  // <------------------- POINT 2

    printf("Best is %s\n", best_car); // <-------- POINT 3

    char buffer[3];
    strcpy(buffer, car2); // <-------------------- POINT 4

    int* some_size = (int*)malloc(sizeof(int));
    *some_size = 50;
    update_size(some_size);

    free(some_size); // <------------------------- POINT 5

    if (*car_size > 10) { // <-------------------- POINT 6
        printf("%s has lots of room\n", car1);
    }

    return 0;

QUESTION 1A For each marked line, indicate if it causes undefined behavior. If the line causes undefined behavior, briefly explain why (a few words is fine, at most one sentence). If the line does not cause undefined behavior, no explanation is required.

You should have an answer for each of the following points in the code:

1. POINT 1
2. POINT 2
3. POINT 3
4. POINT 4
5. POINT 5
6. POINT 6

2. Alignment (15 pts) #

You are creating a new struct called fish to represent fish in an aquarium.  Here's your definition of the struct:

struct fish {
    char name[7];
    struct fish* parent;
    short species;
    int id_num;
    char healthy;
    int* caretaker_id;
};

QUESTION 2A What is the size of the fish struct? To express your answer, copy the struct definition above and add comments to indicate 1) how many bytes are allocated for each member of the struct, and 2) how many bytes of padding (if any) are between each member.

   struct fish {  
     char name[7]; // 7 bytes               [1pt]  
     // 1B padding                          [2pts:  +1 size, +1 position]  
     struct fish* parent; // 8 bytes        [0.5pt]  
     short species; // 2 bytes              [0.5pt]  
     // 2B padding                          [2pts]  
     int id_num; // 4B                      [0.5pt]  
     char healthy; // 1B                    [0.5pt]  
     // 7B padding //                       [2pts]  
     int* caretaker_id; // 8B               [1pt]  
   };  

QUESTION 2B Rearrange the members of the struct such that they have minimal padding. To express your answer, copy the struct definition above and reorder the members. Then, annotate it to show where padding is present. If you believe the struct is already minimally-padded, explain why.

struct fish {  
    struct fish* parent; // 8B  
    int* caretaker_id; // 8B  
    int id_num; // 4B  
    short species; // 2B  
    char name[7]; // 6 characters + null terminator (7 bytes)  
    char healthy; // 1B  
    // +2B padding  
};

3. Memory organization (8 points) #

Alex is writing a program that needs to display lot of different error messages to the user when things go wrong. To avoid writing a lot of big strings for error messages all throughout his program, he makes an array of strings called errors to store them all in one place.

To print an error message, Alex makes a function called get_errors() to get a pointer to the array, and then provides an index to get the string for the error that's needed. Here's the code for Alex's get_errors function and an example of how it might be used:

char** get_errors() {
    char* errors[4] = {
        "Page not found - try another",
        "Access denied - you don't have permission.",
        "Page has moved - look elsewhere.",
        "System is busy - try again later.",
    };

    return errors;
}

int main() {
    // . . . Do some stuff ...

if (/* some error, e.g., page not found */) {
        char** the_errors = get_errors();
        printf("%s", the_errors[0]);        // Prints "Page not found ..."
    }
    // . . .
}

QUESTION 3A. What memory segment is the array errors located in?

QUESTION 3B. When Alex compiles his code, the compiler returns a warning on the get_errors function that says "function returns address of local variable". Allen warns Alex not to run the program, because it could cause undefined behavior. Why is this version of get_errors problematic? Explain your answer in terms of how the function uses memory; i.e., it is not sufficient to say "because it's a local variable." Your answer should be at most one sentence.

QUESTION 3C. Suggest two potential fixes for how Alex could solve the problem by changing how or where the array is declared in the program. In your answer, explain why each fix would work in terms of how the program uses memory; in other words, it's not sufficient to say, "use <name of memory segment> instead." For each fix, your answer should be a few words, at most one sentence.

4. Assembly (11 points) #

Kazuya wrote some C code for the class, but accidentally posted the assembly code to EdStem instead:

 1 mystery_func:
 2         movl    %edi, -20(%rbp)     // First argument 'a'
 3         movq    %rsi, -32(%rbp)     // Second argument 'b'
 4         movl    $0, -4(%rbp)        // Local stack variable 'c'
 5         movl    $0, -8(%rbp)        // Local stack variable 'd'
 6         jmp     .L2
 7 .L5:    movl    -8(%rbp), %eax      // <-- LOOP START
 8         cmpl    -20(%rbp), %eax
 9         jle     .L3
10         movq    -32(%rbp), %rax
11         movl    (%rax), %eax
12         addl    %eax, -4(%rbp)
13         jmp     .L4
14 .L3:
15         movl    -8(%rbp), %eax
16         addl    %eax, -4(%rbp)
17 .L4:
18         addl    $1, -8(%rbp)
19 .L2:
20         cmpl    $9, -8(%rbp)
21         jle     .L5   // <---------------- LOOP END
22         movl    -4(%rbp), %eax
23         ret

Aijah sees that this function takes two arguments and uses two local variables, which are all stored somewhere on the stack. She also notices that the function contains a loop (as marked), and returns an int. Help Aijah further understand the assembly and reverse-engineer Kazuya's code by answering the following questions:

QUESTION 4A. Identify the line where the loop variable gets incremented.

QUESTION 4B. Which variable contains an address that gets dereferenced? Your answer should refer to one of the variables indicated in the comments (i.e., either a, b, c, or d).

QUESTION 4C. Which variable contains the int returned by the function?

QUESTION 4D. Which of the following C code examples could have produced the assembly code for the loop? [Hint: these examples differ only in the contents of the loop body. The for(.. ) part is identical across all options and is not part of the answer. Additionally, assume that the dereference operation(s) you found in part B are added in the appropriate place in the example.]

Write your preferred option and give a brief justification.

Option 1:

for(...) {
    if (d > a) {
       c += b
    } 
}

Option 2:

for(...) {
    if (d > a) {
       c += b
    } else {
       c += d
    }
}

Option 3:

for(...) {
    while (d > a) {
         c += b
         d += a
    } 
}

Option 4:

for(...) {
    c += b
}

5. DMalloc (9 points) #

Daniel is implementing DMalloc has set up the metadata in two parts: a struct before the payload with metadata, and a struct with a secret value at the end of the payload, to detect boundary write errors. Specifically, the layout for Daniel's metadata, and struct definitions, look like this:

struct metadata {
    int freed;  // 1 if data was freed, 0 otherwise
};

struct secret {
    char secret; // Secret value to detect write errors
};

QUESTION 5A. Daniel is writing the dfree() function, which takes in a pointer ptr of type void* that points to the start of the payload, as shown in the diagram. Which of the following lines of code would successfully compute a pointer to the start of the metadata, based on ptr? That is, which of the following lines would successfully compute:

struct metadata* m = /* OPTION HERE */

For each option, write "correct" or "incorrect"; if the option is incorrect, briefly explain your reasoning (a few words at most):

1. ptr - 1
2. ((struct metadata*)ptr) - 1
3. ((char*)ptr) - sizeof(struct metadata)
4. ((int*)ptr) - sizeof(int)

QUESTION 5B. Alaina is helping Daniel test his dfree() function and wants to construct a program with a boundary write error that Daniel's implementation can't detect. Alaina writes the following program:

void test099() {
    int* array = (int*)malloc(12 * sizeof(int));
    array[13] = 42; // Boundary write error!
    dfree(array); 
}

Can Daniel's implementation for the secret value detect the error? Answer "yes" or "no", and explain your reasoning (a few words, at most one sentence).

6. Stack (12 points) #

Ethan, Cash, and Andrew are debugging a program where function fun calls function more_fun.  To help debug, they've made a complete (and correct!) diagram of the stack just before more_fun returns:

QUESTION 6A.  Which of the following locations does the return address labeled \[PART A\] in the diagram point to?  Choose one option below, then explain your reasoning (a few words, max 1 sentence).

• Option 1: An instruction in the code for more_fun
• Option 2: An instruction in the code for fun
• Option 3: One of more_fun's local variables
• Option 4: One of fun's local variables

QUESTION 6B. What address (in hex) is in the stored %rbp value in more_fun's stack frame (labeled [PART B])?

QUESTION 6C. Right after more_fun returns (i.e., immediately after the ret instruction is executed), what address will be stored in the %rsp register?

QUESTION 6D. Ethan, Cash, and Andrew all think the stack is too complicated and propose an alternative solution: instead of adding to the stack on each function call, the compiler assigns each function a fixed, unique region of memory in the data segment large enough to store its local variables. Each time a function is called, it would always use the same addresses, eliminating the need to use%rsp and%rbp for local variables. Explain two potential problems with this approach (roughly one sentence each).

7. Snake (11 points) #

Rahel has written a new variant of Snake: Serpent (sea snake)! In this game, the snake is amphibious: it can be on land and in the water.

Like in Snake, Rahel keeps track of each cell state using bitflags. Here are definitions for each cell state (note that these differ from the actual Snake project):

#define LAND_CELL  0b0000
#define FLAG_SNAKE 0b0001
#define FLAG_WATER 0b0010
#define FLAG_WALL  0b0100
#define FLAG_FOOD  0b1000

QUESTION 7A. Rahel is trying to show Cedric how to update the state of a cell as the snake/serpent moves. For each of the update methods below, write "correct" or "incorrect" to indicate if the method will correctly update a cell (represented by the variable cell) as the head of the snake/serpent moves into it.

[Hint: remember that a snake can only move into a cell that is not a wall or part of the snake itself.]

Method 1:

if (cell != 0b0100) {                                             
  cell += 1;
}

Method 2:

cell ^= 0b0001;                                             

Method 3:

if (((cell & 0b0001) == 0) && (cell <= 0b0010 || cell == 0b1000)) {
  cell |= 0x1;
}

Method 4:

if (((cell | 0b0001) == 0) && (cell <= 0b0010 || cell == 0b1000)) {
  cell &= 0x1;
}

QUESTION 7B. Cedric thinks reading the cell states in binary is too confusing. Instead, he proposes defining each cell to be an array of five slots that each represent a state:

    typedef int[5] cell;

    0       1       2       3      4
   +-------+-------+-------+------+------+
   | land  | snake | water | wall | food |
   +-------+-------+-------+------+------+

Each slot of the array contains a value of 0 if it is unset, and a value equal to its index if it is set. For example, a food cell would have the following array:

     0       1       2       3      4
    +-------+-------+-------+------+------+
    | 0     | 0     | 0     | 0    | 4    |
    +-------+-------+-------+------+------+

Cedric then suggests changing the game implementation to simply check the sum of the array’s values, e.g., checking (cell[0] + cell[1] + cell[2] + cell[3] + cell[4]) == 4 to see if it is a food cell.

Explain two problems with Cedric’s approach, one related to correctness and one related to efficiency.

8. Numbers on the Wall (15 points) #

Julia and Eric found a hexdump scrawled on a whiteboard with a note that it represents an array of int's  called arr, and was produced on an x86-64 system.  Assume that the hexdump contains the entire array, and does not include any other data.  Here's the hexdump:

    0x4af45ab0 0C 00 00 00 10 00 00 00 FC FF FF FF FF FF FF FF 
    0x4af45ac0 A1 00 00 00 FA FF FF FF FF FF FF 7F FF AB 02 00 

[Tip: as you work on this problem, you may want to copy this hexdump into a doc or text file so you can annotate it!]

QUESTION 8A How many integers are contained in the array arr?

QUESTION 8B Following the hexdump, what would be the resulting value in hex if we printed out the following expressions? Assume that we would print the result as type int (same as the array), just formatted in hex. If the value is undefined or would result in an error, write "undefined" or "error" and briefly explain why.  [Hint:  remember that x86-64 uses little endian!]

1. arr[0]
2. arr[4]
3. arr[0] | arr[4]

QUESTION 8C. Following the hexdump, what would be the resulting value in decimal if we printed out the following expressions?  As before, assume that we would print the result as type int (just as a decimal number this time). If the value is undefined or would result in an error, write "undefined" or "error" and briefly explain why. [Hint:  remember that x86-64 uses little endian!]

1. arr[2]
2. arr[0] + arr[6]
3. arr[3] + arr[0]

9. CS 300/1310 Feedback (6 points) #

QUESTION 9A. If you could make one change to CS 300/1310 to improve it (other than firing the instructor and dropping the quizzes), what would you change? Any answer but no answer will receive full credit.

QUESTION 9B. What topics do you wish we had spent more time on? Any answer but no answer will receive full credit.

10. Submit! (1 points) #

QUESTION 10A. Write "I AM DONE" in the box. (You may still continue editing other questions until the time limit expires.)