CS 300/1310 Spring 2023 Midterm Quiz

Welcome to our midterm quiz! We’re hoping this quiz provides you with an opportunity to review your knowledge and what you've learned in CS 300 so far. Our questions are designed to check your conceptual understanding, rather than asking you to memorize details.

Please make sure you read the rules below before you get started.

Rules

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 may not ask the quiz questions on class discussion forums or other question forums such as Stack Overflow.
• You may not access solutions from any previous quiz, from this course or others, by paper or computer, except for those on the CS 300 course site.
• You absolutely may not 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.

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 80 minutes to complete the quiz starting from the time you press "Start". Different students may have different quizs. 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-s23-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. Signed Numbers (8 points)

QUESTION 1A. Malte has two code examples he wants to use for a lecture on signed numbers and integer overflow. However, when running these examples he unintentionally invokes undefined behavior, and his computer catches on fire!

Below is the program that he ran. For each of the function calls (labeled 1-4), determine:

• If signed integer overflow, unsigned integer overflow, or no overflow occurs.
• If the function call invokes undefined behavior.

int add(int a, int b) {
	return a + b;
}

unsigned int sub(unsigned int a, unsigned int b) {
	return a - b;
}

int main() {
  add(1, 0xFFFF'FFFA);     // 1
  add(0x7FFF'FFAC, 0x64);    // 2

  sub(300, 330);             // 3
  sub(0x8000'000A, 16);      // 4
}

8pts

1. No overflow, not undefined behavior
2. Signed integer overflow, undefined behavior
3. Unsigned integer overflow, not undefined behavior
4. No overflow, not undefined behavior

2. Alignment (8 points)

QUESTION 2A. HTAs Liz and Ed are working on a new data struct called the linkEd_Lizt. The linkEd_Lizt is used to store information about their favorite jams, as seen below:

struct linkEd_Lizt {
  char* description;
  struct linkEd_Lizt* next_jam;
  struct linkEd_Lizt* previous_jam;
  char name[15]; // 14 characters + NUL terminators
  short jam_short;
  int ranking;
}

If HTA Richard were to malloc heap memory for this struct, how much memory should he request? How many of these bytes will be padding bytes? (Give your answer as a number of bytes, i.e., not as sizeof(struct linkEd_Lizt).)

2pts 8 + 8 + 8 + 15 + 1 byte of padding + 2 + 2 bytes of padding + 4 = 48 bytes in total

3 bytes of padding.

QUESTION 2B. HTA Will thinks that the size of the structs should match the sizes of their jams -- humongous! How can Will rearrange the struct to ensure the linkEd_Lizt struct has a size of exactly 56 bytes? In your answer, write the struct declaration with comments to indicate where padding bytes (if any) occur.

6pts

struct linkEd_Lizt {
 char* description;
 char name[15]; // 14 characters + NUL terminators
 struct linkEd_Lizt* next_jam;
 short jam_short;
 struct linkEd_Lizt* previous_jam;
 int ranking;
}

8 + 15 + 1 byte of padding + 8 + 2 + 6 bytes of padding + 8 + 4 + 4 bytes of padding = 56 bytes in total

Note that changing the order of any of the pointer variables will result in the same alignment.

3. Assembly (8 points)

QUESTION 3A. Armed with your Section 3 knowledge on ethical hacking, you hack the CS300 grading server and find a suspicious looking assembly file that you suspect lowers student grades based on their names—yikes! The function returns 1 if a student’s grade gets unfairly lowered, and 0 otherwise:

unfair:
        mov %rdi, %rcx
.L1:
        movzbl (%rcx), %eax
        cmpb $0, %al
        je .L2
        cmpb $76, %al
        je .L3
        addq $1, %rcx
        jmp .L1
.L2:
        movl    $0, %eax
        ret
.L3:
        movl    $1, %eax
        ret

What are the criteria that Malte is using to unfairly deduct points? In other words, in what cases will the function return 1?

8pts The function returns 1 (i.e. Malte deducts points) if a student name contains an L in it (ASCII 76)

4. Stack (10 points)

QUESTION 4A. Below is a partial implementation of Snake for a 1 by 300 board where the snake is permanently moving to the right and collisions with walls are not yet implemented. You may assume that the program includes everything necessary to compile.

int game_over = 0;
int board_length = 300;

void update(char* cells, int* pos_p) {
    int old_pos = *pos_p;
    int new_pos = *pos_p + 1;
    cells[new_pos] = FLAG_SNAKE;
    cells[old_pos] = FLAG_PLAIN;
    *pos_p = new_pos;
    // DRAW THE DIAGRAM AT THIS POINT
}

int main() {
    int pos = 0;
    char* cells = malloc(board_length);
    memset(cells, FLAG_PLAIN, board_length);
    cells[pos] = FLAG_SNAKE;
    while (!game_over) {
        update(cells, &pos);
        render(cells);
    }
    free(cells);
}

Draw a diagram of the layout of the stack segment at the point when the update function returns. Assume an x86-64 calling convention with compiler optimizations disabled, that the local variable pos is stored at address 0x7fff'ffff'e97c in main()'s stack frame, that the compiler is using the base pointer register %rbp, and that stack canaries are disabled.

Please format your answer like:

• %rbp of main()'s caller, 0x7fff'ffff'e980
• pos, 0x7fff'ffff'e97c
• ...

10pts

• saved %rbp of main()'s caller, 0x7fff'ffff'e980
• pos, 0x7fff'ffff'e97c
• cells, 0x7fff'ffff'e970 [note 8-byte alignment]
• return address in main(), 0x7fff'ffff'e968
• ----------- start of update()'s stack frame --------
• saved %rbp of main(), 0x7fff'ffff'e960
• cells, 0x7fff'ffff'e958
• pos_p, 0x7fff'ffff'e950
• old_pos, 0x7fff'ffff'e94c
• new_pos, 0x7fff'ffff'e948

5. Caching (8 points)

The CS 300 staff have decided to add an exciting new extra credit opportunity to the Caching I/O project: a multi-slot I/O cache.

The idea is to take inspiration from the CPU cache, and store fixed-size blocks that each contain a contiguous range of bytes in the file on disk (e.g., 4096 bytes). Since data on disk doesn’t have addresses, cache entries are identified by byte offsets into the file, e.g., [0, 4096) or [8192, 12,288).

When the program calls io300_read or io300_write, the caching I/O library checks the bytes at the current file position are contained in any of the blocks currently in the cache's N slots; if so, a cache hit happens, otherwise a cache miss happens and the data gets retrieved from disk.

QUESTION 5A. How should the caching I/O library handle the situation when all slots in the cache are occupied?

2pts When the caching I/O library gets a read/write call, it first checks if the cache contains the range of bytes where the current read/write head is according to the application’s prior I/O calls (not the actual OS R/W head). If so, cache hit; if not, pick a slot to evict from (e.g., via LRU, writing back if modified) and load the range of bytes from disk (cache miss). We gave credit for any answer that mentioned a cache eviction policy.

QUESTION 5B. For what workload would such a multi-slot cache provide speedups over the single-slot cache you implemented in the project, and why? (Give one example, there may be multiple.)

6pts Workloads for which this design is beneficial would be seek-heavy workloads that jump around the file a lot, but keep revisiting the same locations (or nearby locations). For example, a program that interleaves bytes from the start and end of a file is always accessing two blocks at the start and end of the input file to read bytes, and would achieve a 100% cache hit rate in this design. 2pts for workload, 4pts for correct justification.

6. Undefined Behavior (10pts)

QUESTION 6A. Consider the following C program. For every labeled example, indicate whether it contains undefined behavior, and if it does, explain why. Be sure to read the entire code snippet before writing your answers.

long* dragons(int* ptr) {
   int* arr = malloc(sizeof(int) * (*ptr));
   for (int i=1; i < *ptr; i++) {
       arr[i - 1] = i;
   }
   // Example 1
   printf("My least favorite number is %d\n", arr[0]);
   // Example 2
   printf("My favorite number is %d\n", arr[4]);


   // Example 3
   char drags[] = "dragons";
   drags[7] = '!';
   // End of Example 3

   // Example 4
   printf("Here be %s?\n", drags);
   // End of Example 4

   free(ptr);
   free(arr);
   long l = 2024;
   int* l_ptr = &l;
   return l_ptr;
}


int main(){
   int* ptr = malloc(sizeof(int));
   *ptr = 5;
   long* returned_ptr = dragons(ptr);
   // Example 5
   printf("The current year is: %ld\n", *returned_ptr);
   // Example 6
   printf("High %d!\n", *ptr);
}

10pts

1. Not UB
2. UB: Accessing uninitialized memory
3. Not UB: overwrites the null byte
4. UB: string no longer NUL-terminated, so will run over the end
5. UB: Accessing variable out of scope. (The long is stack-initialized in dragons and read in main)
6. UB: Use after free.

7. Project 2: DMalloc (4 points)

QUESTION 7A. Like your DMalloc implementation, the standard C malloc implementation also stores metadata with each allocation. Below, we show you a slightly simplified version of that metadata, which stores the size of each allocation and whether that allocation has been freed in a header:

Describe two memory errors that can occur using malloc’s metadata implementation, but not using DMalloc's. Explain how your DMalloc implementation fixes these problems.

4pts Many possible answers:

• No detection for wild writes. Solve by implementing sentinel values
• No padding to space out allocations. Solve by adding padding.
• Metadata is very close to payload, so wild writes can accidentally edit the size or freed status of a block. Solve by adding padding between metadata and payload.
• No good way to easily check if a pointer has not been allocated. Solve by adding secret values to the metadata to make it harder to spoof.
• Does not store a list of active allocations, so cannot detect memory leaks. Solved by adding a list of allocations.

8. CS 300/1310 Feedback (6 points)

QUESTION 8A. 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.

3pts Any answer

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

3pts Any answer