2024 CS 61 Test 2

Show all solutions Hide all solutions

Exam scheduling

You must take this test in person at Winokur Lecture Hall, SEC 1.321, Allston.

Exam scheduling

You must take this test in person at William James Hall B1.

Exam scheduling

You must take this test in person at Maxwell Dworkin G115.

Exam scheduling

You are scheduled to take the test at home. After your exam period is over, you will record a short video explaining one of your answers, make a shareable URL for that video, and update the exam to include that URL.

Exam scheduling

You are scheduled to take the test at the DAO Alternative Testing Center. Press Start to begin the exam when you are in the testing center and ready.

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.

If unsure, briefly explain your thinking for potential partial credit.

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 test2 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.

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 (22 points)

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

QUESTION 1A. After step 3 (general process address spaces), the Harvard Corporation’s WeensyOS looks like this:

Note that addresses below 0x100000 appear in reverse video in the virtual memory displays.

This OS does not implement kernel isolation correctly. How can you tell? Explain briefly.

4pts. The kernel’s code and data is reverse video in the virtual memory map, meaning processes can access this code and data directly.

QUESTION 1B. The Corporation uses this code to set up a process’s initial page table in process_setup.

ptable[pid].pagetable = kalloc_pagetable();
for (uintptr_t addr = 0; addr < PROC_START_ADDR; addr += PAGESIZE) {
    int perm = PTE_P | PTE_W | PTE_U;
    if (addr == 0) {
        perm = 0;
    }
    int r = vmiter(ptable[pid].pagetable, addr).try_map(addr, perm);
    assert(r == 0);
}

Change this code to fix the problem in the previous question (without otherwise breaking the OS).

4pts. Change the initialization of int perm to int perm = PTE_P | PTE_W.

For a fully correct kernel, you would need code like this:

int perm = PTE_P | PTE_W;
if (addr == 0) {
    perm = 0;
} else if (addr == CONSOLE_ADDR) {
    perm |= PTE_U;
}

but the simple version is enough for full credit. Maybe give extra credit if someone mentions the console.

QUESTION 1C. After a bit more hacking, the Corporation’s kernel implementation of syscall_page_alloc looks like this.

int syscall_page_alloc(uintptr_t addr) {
    if (addr % PAGESIZE != 0) {
        return -1;
    }
    void* ptr = kalloc(PAGESIZE);
    vmiter it(current, addr);
    it.map(ptr, PTE_P | PTE_W | PTE_U);
    assert(physpages[addr / PAGESIZE].refcount == 0);
    ++physpages[addr / PAGESIZE].refcount;
    memset((void*) addr, 0, PAGESIZE);
    return 0;
}

Describe at least three substantially different problems with this code that should be fixed by the time the Corporation completes the pset.

6pts.

1. addr is not checked for validity. This value is provided by the user. The kernel should check that addr >= PROC_START_ADDR.

2. Also, it should check that addr < MEMSIZE_VIRTUAL.

3. The kalloc call might fail if the OS runs out of memory. If it failed, the system call should return -1 and there shouldn’t be any vmiter mapping.

4. The it.map() call might fail if the OS runs out of memory. The Corporation should call try_map instead, freeing ptr and returning -1 if it fails.

5. The code effectively allocates two pages for every call to syscall_page_alloc: it first allocates a new page with kalloc, then it “allocates” the page with physical address addr by incrementing its reference count. Only the first allocation is required.

6. The code clears the wrong page. It clears the page with physical address addr, but in the process’s virtual address space, physical page ptr is mapped at that address. The memset line should clear ptr, not addr.

7. The code does not check if addr is already allocated. If addr is already allocated (e.g. by a previous call to syscall_page_alloc, then the kernel should either return -1 or free the old page before reallocating it.

QUESTION 1D. The memory maps in the first question show WeensyOS running the four allocator processes after step 3. Each allocator process contains three segments—code, data, and stack—where the code segment occupies 3 pages and the data and stack segments occupy one page each. Each allocator process also has a four-level page table.

Here’s a duplicate of the initial portion of the physical memory map from the that diagram, in text format for screen readers. Bold shows characters with red backgrounds.

                               PHYSICAL MEMORY
  0x000000 R111111111222222222333333333444444444K44342344444244424124344344
  0x040000 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK34443242333334434341344241K

Which physical pages are most likely to contain process 2’s page table pages? Either refer to features of the physical memory map or give specific addresses.

4pts. Pages 0xA000-0xD000: the four red-background pages labeled “2”.

QUESTION 1E. Which physical pages are most likely to contain process 2’s code? Either refer to features of the physical memory map or give specific addresses.

4pts. Pages 0xE000-0x11000: the three “2” pages immediately following the page table pages (the red-background “2” pages). This is because the process_setup code allocates pages for the code segment before it allocates pages for the data or stack segments.

2. Kernel multiple choice (16 points)

QUESTION 2A. %cr3: List all that apply.

1. The value in the %cr3 register must be a multiple of 1000.
2. The value in the %cr3 register must be a multiple of 0x1000.
3. The value in the %cr3 register is interpreted as a virtual address.
4. The value in the %cr3 register is interpreted as a physical address.
5. The value in the %cr3 register is not interpreted as an address.
6. The value in the %cr3 register is the same for every process.
7. None of the above.

4pts. 2, 4

QUESTION 2B. Which of the following statements are required for correct kernel isolation in WeensyOS? List all that apply.

1. Processes cannot directly change the %rax register.
2. Processes cannot directly change the %cr3 register.
3. Processes cannot modify physical memory containing kernel code.
4. Processes cannot modify physical memory containing their own process code.
5. Processes cannot transfer control to arbitrary locations in the kernel.
6. Processes cannot transfer control to the kernel at all.
7. None of the above.

4pts. 2, 3, 5

QUESTION 2C. Page table entries: List all that apply.

1. Page table entries are 8 bytes big.
2. Page table entries are stored in arrays called page table pages.
3. Page table entries are initially assigned by software, but interpreted most frequently by hardware.
4. Page table entries are divided into components called the offset, the level-1 index, the level-2 index, the level-3 index, and the level-4 index.
5. Page table entries are divided into flags and an optional physical address.
6. Page table entries may be modified by the kernel in response to a system call.
7. None of the above.

4pts. 1, 2, 3, 5, 6

QUESTION 2D. WeensyOS stacks: List that all apply. (Assume a WeensyOS that has correctly completed all steps of Problem Set 3.)

1. A WeensyOS running N processes uses N physical pages of memory for stacks.
2. A WeensyOS running N processes uses N+1 physical pages of memory for stacks.
3. All WeensyOS process stacks are located at the same virtual memory address.
4. All WeensyOS process stacks are located at the same physical memory address.
5. Each WeensyOS process page table has exactly one present mapping for a stack page.
6. Each WeensyOS process page table has exactly one user-visible present mapping for a stack page.
7. None of the above.

4pts. 2, 3, 6

3. Blocks and pages (22 points)

For your reference: Table of powers of 2

QUESTION 3A. How big is an x86-64 page?

2pts. 4096 bytes

QUESTION 3B. How many page table entries fit in an x86-64 page?

2pts. 512

QUESTION 3C. Intel has produced a new architecture, the 🤮96-64. This architecture’s virtual memory system resembles x86-64’s—it has 4-level page tables and 64-bit virtual addresses—but its page size is 8192 bytes.

What is the size in bits of the page offset part of a 🤮96-64 address?

3pts. 13

QUESTION 3D. What is the size in bits of the level-1 index part of a 🤮96-64 address? (Level-2, 3, and 4 indexes will have the same size in bits.)

3pts. The bit size of an index is determined by the number of entries that fit on a page. A page is 8192 bytes, so 8192 / 8 = 1024 entries. That’s 10 bits.

QUESTION 3E. In x86-64, which we studied in class, virtual addresses have only 48 meaningful bits, even though their size is 8 bytes (64 bits). This is a consequence of the x86-64 page table design: a 4-level page table with x86-64’s offset and index sizes can distinguish only 48 bits.

How many meaningful bits does a 🤮96-64 virtual address contain?

3pts. 13 + 10×4 = 53 bits

QUESTION 3F. A run of strace stdio-cat61 on a 🤮96-64 machine produces results like this.

openat(AT_FDCWD, "/tmp/cs61-22f7/outputs/out.txt", O_WRONLY|O_CREAT|O_TRUNC, 0666) = 4
fcntl(4, F_GETFL)                       = 0x8001 (flags O_WRONLY|O_LARGEFILE)
fstat(3, {st_mode=S_IFREG|0644, st_size=10485760, ...}) = 0
read(3, "ax's\nAkbar\nAkbar's\nAkhmatova\nAkh"..., 4096) = 4096
fstat(4, {st_mode=S_IFREG|0644, st_size=0, ...}) = 0
read(3, "he's\nAndromeda\nAndromeda's\nAndro"..., 4096) = 4096
write(4, "ax's\nAkbar\nAkbar's\nAkhmatova\nAkh"..., 4096) = 4096
read(3, "sia's\nAsiatic\nAsiatic's\nAsiatics"..., 4096) = 4096
write(4, "he's\nAndromeda\nAndromeda's\nAndro"..., 4096) = 4096
read(3, "dos\nBarbados's\nBarbara\nBarbara's"..., 4096) = 4096
write(4, "sia's\nAsiatic\nAsiatic's\nAsiatics"..., 4096) = 4096
read(3, "\nBest\nBest's\nBetelgeuse\nBetelgeu"..., 4096) = 4096
write(4, "dos\nBarbados's\nBarbara\nBarbara's"..., 4096) = 4096

How big is the corresponding stdio cache in 🤮96-64 pages?

3pts. 1/2 page

QUESTION 3G. The following four strace fragments are from different variants of cat61, running on the same input file as the previous question. Which of these variants corresponds to a correct stdio-like cache with size of exactly one 🤮96-64 page? Explain briefly. Note that read system calls are not present in these strace fragments.

• cat61a:

  openat(AT_FDCWD, "/tmp/cs61-22f7/outputs/out.txt", O_WRONLY|O_CREAT|O_TRUNC, 0666) = 4
  fcntl(4, F_GETFL)                       = 0x8001 (flags O_WRONLY|O_LARGEFILE)
  fstat(4, {st_mode=S_IFREG|0644, st_size=0, ...}) = 0
  write(4, "ax's\nAkbar\nAkbar's\nAkhmatova\nAkh"..., 4096) = 4096
  write(4, "he's\nAndromeda\nAndromeda's\nAndro"..., 4096) = 4096
  write(4, "sia's\nAsiatic\nAsiatic's\nAsiatics"..., 4096) = 4096
  write(4, "dos\nBarbados's\nBarbara\nBarbara's"..., 4096) = 4096
  

• cat61b:

  openat(AT_FDCWD, "/tmp/cs61-22f7/outputs/out.txt", O_WRONLY|O_CREAT|O_TRUNC, 0666) = 4
  fcntl(4, F_GETFL)                       = 0x8001 (flags O_WRONLY|O_LARGEFILE)
  fstat(4, {st_mode=S_IFREG|0644, st_size=0, ...}) = 0
  write(4, "ax's\nAkbar\nAkbar's\nAkhmatova\nAkh"..., 8192) = 8192
  write(4, "he's\nAndromeda\nAndromeda's\nAndro"..., 8192) = 8192
  write(4, "sia's\nAsiatic\nAsiatic's\nAsiatics"..., 8192) = 8192
  write(4, "dos\nBarbados's\nBarbara\nBarbara's"..., 8192) = 8192
  

• cat61c:

  openat(AT_FDCWD, "/tmp/cs61-22f7/outputs/out.txt", O_WRONLY|O_CREAT|O_TRUNC, 0666) = 4
  fcntl(4, F_GETFL)                       = 0x8001 (flags O_WRONLY|O_LARGEFILE)
  fstat(4, {st_mode=S_IFREG|0644, st_size=0, ...}) = 0
  write(4, "ax's\nAkbar\nAkbar's\nAkhmatova\nAkh"..., 8192) = 8192
  write(4, "sia's\nAsiatic\nAsiatic's\nAsiatics"..., 8192) = 8192
  write(4, "\nBest\nBest's\nBetelgeuse\nBetelgeu"..., 8192) = 8192
  write(4, "is\nCalais's\nCalcutta\nCalcutta's\n"..., 8192) = 8192
  

• cat61d:

  openat(AT_FDCWD, "/tmp/cs61-22f7/outputs/out.txt", O_WRONLY|O_CREAT|O_TRUNC, 0666) = 4
  fcntl(4, F_GETFL)                       = 0x8001 (flags O_WRONLY|O_LARGEFILE)
  fstat(4, {st_mode=S_IFREG|0644, st_size=0, ...}) = 0
  write(4, "ax's\nAkbar\nAkbar's\nAkhmatova\nAkh"..., 16384) = 16384
  write(4, "\nBest\nBest's\nBetelgeuse\nBetelgeu"..., 4096) = 4096
  write(4, "rant\nBrant's\nBraque\nBraque's\nBra"..., 12288) = 12288
  write(4, "cero's\nCid\nCid's\nCimabue\nCimabue"..., 4096) = 4096
  

3pts. cat61c. The system calls indicate a cache size of 8192 bytes, which is the 🤮96-64 page size. cat61b also has this cache size, but given the sequence of read calls in the previous question, its writes produce incorrect results.

The previous question’s reads showed these byte contents:

1. Offset 0: "ax's\nAkbar\nAkbar's\nAkhmatova\nAkh"
2. Offset 4096: "he's\nAndromeda\nAndromeda's\nAndro"
3. Offset 8192: "sia's\nAsiatic\nAsiatic's\nAsiatics"
4. Offset 12288: "dos\nBarbados's\nBarbara\nBarbara's"
5. Offset 16384: "\nBest\nBest's\nBetelgeuse\nBetelgeu"

When writing 8192 bytes at a time, the first three writes should produce the data from offset 0, offset 8192, and offset 16384. That’s what cat61c shows. cat61b doesn’t: the data written at offset 8192 is from offset 4096 in the input file.

QUESTION 3H. Unlike the stdio cache, the buffer cache has no fixed size in pages. What entity manages the size of the buffer cache, and what limits the buffer cache’s size?

3pts. The kernel manages the buffer cache, and its size depends on how much memory the machine has and what fraction of that memory is in use for other purposes.

4. Bad I/O caches (15 points)

This question involves implementations of io61 calls like io61_readc, io61_read, and io61_write. You may want to refer to the problem set code and to the single-slot cache section material.

QUESTION 4A. In the handout code, io61_readc calls read, causing one system call per byte. This student has tried to speed up io61_readc by having it call io61_read. What’s wrong with their implementation? Explain briefly.

int io61_readc(io61_file* f) {
    unsigned char ch;
    ssize_t nr = io61_read(f, &ch, 1);
    return nr == 1 ? ch : EOF;
}

ssize_t io61_read(io61_file* f, unsigned char* buf, size_t sz) {
    size_t nr = 0;
    while (nr != sz) {
        int ch = io61_readc(f);
        if (ch == EOF) {
            break;
        }
        buf[nr] = ch;
        ++nr;
    }
    return nr;
}

5pts. io61_readc calls io61_read, which calls io61_readc: infinite mutual recursion. This code will cause a segmentation fault on stack overflow.

QUESTION 4B. This version of io61_read uses a single-slot cache based on our section material. What’s wrong with this implementation? Explain briefly.

struct io61_file {
    int fd, mode;
    static constexpr size_t bufsize = 4096;
    unsigned char cbuf[bufsize];
    off_t tag, pos_tag, end_tag;
};

ssize_t io61_read(io61_file* f, unsigned char* buf, size_t sz) {
    size_t nr = 0;
    while (nr != sz && f->pos_tag != f->end_tag) {
        buf[nr] = f->cbuf[f->pos_tag - f->tag];
        ++nr;
        ++f->pos_tag;
    }
    return nr;
}

5pts. This io61_read can access data in the cbuf cache, but it never refills that cache (there’s no call to io61_fill). A call to io61_read may return end-of-file simply because the data in the cache buffer was used.

QUESTION 4C. This version of io61_flush attempts to flush the cbuf cache for writing. What’s wrong with it? Explain briefly.

int io61_flush(io61_file* f) {
    while (f->mode == O_WRONLY && f->end_tag > f->tag) {
        ssize_t nw = write(f->fd, f->cbuf, f->bufsize);
        f->tag = f->pos_tag = f->tag + nw;
    }
    return 0;
}

5pts. The most egregious error is that it writes f->bufsize bytes, even if the cache contains fewer bytes than that (because f->end_tag - f->tag < f->bufsize). Other errors:

1. nw might be -1, to indicate an error; and if so, it should not be added to f->tag.

2. If write returns a permanent (nonrecoverable) error, the function should return -1.

3. After a short write, the next write system call’s buf argument should start partway into f->cbuf, because the initial bytes in f->cbuf were already written.

5. Reference strings (20 points)

For these questions, write reference strings as sequences of numbers, such as “1 2 3 4 1 2 5”.

QUESTION 5A. What is the maximum hit rate possible for the following reference string, over all possible cache slot counts and eviction algorithms? Assume the cache is initially empty, and assume no prefetching.

1 2 3 1 4 1 2 3 4 5

4pts. 50%, because only half of the accesses are duplicates. If you explicitly assume a specific number of slots the maximum hit rate might be even lower.

QUESTION 5B. Calculate the hit rate for the following reference string, a 3-slot fully-associative cache, and the Least Frequently Used eviction policy. (This policy evicts the slot whose contents were used least often. In case of a tie, it evicts the slot whose contents were used least recently.)

1 2 3 1 4 1 2 3 4 5

4pts. 1m 2m 3m 1h 4m/2 1h 2m/3 3m/4 4m/2 5m/3: the hit rate is 20%.

QUESTION 5C. Write a reference string for which the Least Frequently Used eviction policy has a higher hit rate than the First-In, First-Out eviction policy. Assume the cache is fully associative; you may choose the number of slots (we’ll assume 3 slots unless you state otherwise).

4pts. “1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10”, for example.

QUESTION 5D. Write a reference string for which the Least Frequently Used eviction policy has a higher hit rate than the Least Recently Used eviction policy. Assume the cache is fully associative; you may choose the number of slots (we’ll assume 3 slots unless you state otherwise).

4pts. “1 1 1 1 1 1 1 2 3 4 1”, for example.

QUESTION 5E. In reference strings corresponding to sequential access, such as “1 2 3 4 5 6 7 8 9 …”, every address is unique. One might assume that reference strings with no repeats are uncacheable (have max hit rate 0%), but we know from lecture and pset 4 that caches enormously improve the performance of sequential access. Which cache optimizations are involved in caching sequential access, especially for reads? Explain briefly.

4pts. Batching and prefetching.

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

Video

QUESTION 6B. This button will activate 80 minutes after you start the test. Once you click it, it will reveal the problem number for which you should submit a three-minute-or-less explanation video. Video instructions are here.

QUESTION 6C. Prepare your video on Part 1, Our governing body. Your video should describe your general approach, then give more depth into a Part 1 question of your choice.

QUESTION 6D. Prepare your video on Part 2, Kernel multiple choice. Your video should describe your general approach, then give more depth into a Part 2 question of your choice.

QUESTION 6E. Prepare your video on Part 3, Blocks and pages. Your video should describe your general approach, then give more depth into a Part 3 question of your choice.

QUESTION 6F. Prepare your video on Part 4, Bad I/O caches. Your video should describe your general approach, then give more depth into a Part 4 question of your choice.

QUESTION 6G. Prepare your video on Part 5, Reference strings. Your video should describe your general approach, then give more depth into a Part 5 question of your choice.

QUESTION 6H. Once you have recorded your 3-minute video, copy the unlisted link to that video here. You can obtain a link by, for example, uploading the video to YouTube as “Unlisted,” so that only those with the link can view it; or uploading it to Google Drive, with permissions set so that only those with the link can view it.