Consider the following C declarations:

int a[4] = {1,1,2,2};
int b[4] = {2,2,3,3};

int *p[4] = {&a[0], &b[0], &a[2], &b[2]};

Given these declarations and initial values, which of the following snippets will not access out-of-bounds memory, create a pointer to out-of-bounds memory, or otherwise cause an error? Select all that apply.

Suppose one is using a single-core Linux system and running the following C snippet in process A:

unsigned int x = fgetc(stdin);
unsigned int y = fgetc(stdin);
for (int i = 0; i < 100000000; i += 1) {
    x += y;
}
printf("%u\n", x);

After one provides input to the program and before it computes the final value of x, another process, process B, on the system outputs a message to the terminal and exits. Then, process A finishes its computation and outputs the final value of x.

Which of the following is true about this situation? Select all that apply.

Consider a single-core system, running two processes A and B. Process A runs

fgets(buffer, sizeof buffer, stdin);

to read in the input line "1234\n" from the keyboard.

The user using this program types "12" well before the program calls fgets, and then the user waits a while, then types "34" and presses enter.

Meanwhile, process B tries to perform as many calculations as possible when it gets to run. The OS contexts switches to process B whenever the process A does not need the processor. The OS also uses hardware exceptions to learn about keyboard input.

Which of the following is true about this scenario? Select all that apply.

Consider the following code that uses fork():

pid_t pid;

char str[20] = "foo";
pid = fork();
if (pid == 0) {
    strcat(str, "bar");
    printf("%s\n", str);
    exit(0);
} else {
    strcat(str, "quux");
    printf("%s\n", str);
}
printf("%s\n", str);

(Assume all required header files are included.)

Which of the following are possible outputs? Select all that apply.

Consider the following C code:

int fds[2];
pid_t pids[2];

pipe(fds);

for (int i = 0; i < 2; i += 1) {
    pids[i] = fork();
    if (pids[i] == 0) {
        char c;
        read(fds[0], &c, 1);
        write(STDOUT_FILENO, &c, 1);
        exit(0);
    }
}

write(fds[1], "AB", 2);
write(STDOUT_FILENO, "C", 1);
for (int i = 0; i < 2; i += 1) {
    int status;
    waitpid(pids[i], &status, 0);
}

One possible output of the above code is CAB. Which, if any of the following are additional possible outputs of the above code? Select all that apply.

Consider the following C code:

int fd1 = 100;
pid_t pid;

pid = fork();
if (pid == 0) {
    int fd2 = open("newfile.txt", O_CREAT | O_RDWR | O_TRUNC);
    dup2(fd2, 100);
    close(fd2);
}
write(fd1, "hello", 5);
if (pid != 0) {
    waitpid(pid, NULL, 0);
}

Assume fork() and open() are successful, and that only stdin, stdout, and stderr are open before the code snippet starts. After the code finishes, what are possible contents of newfile.txt? Select all that apply.

Suppose a system uses:

• 16384-byte pages
• two-level page tables, and
• page tables containing 2048 entries, each of which takes up 8 bytes.

When accessing the virtual address 0x99120000, the system reads a first-level page table entry which contains physical page number 0x4000. (The physical page with page number 0x4000 starts at physical address 0x10000000.) Then, it will access a second-level page table entry at physical address ___.

If not enough information is given write "unknown" and explain briefly in the comments.

Suppose a system has two-level page tables with 4096-byte pages and 30-bit virtual addresses. Virtual addresses are divided into a 9-bit first virtual page number part, a 9-bit second virtual page number part, and a 12-bit page offset.

Suppose a program's page tables have valid entries for:

• virtual page 0x1, virtual page 0x2, and virtual page 0x3 (corresponding to virtual addresses 0x1000 through 0x3fff)
• virtual page 0x9000, virtual page 0x9001 (corresponding to virtual addresses 0x9000000 through 0x9001fff)
• virtual page 0x9100 (corresponding to virtual addresses 0x9100000 through 0x9109fff)
• virtual page 0x1ffff (corresponding to virtual adresses 0x1ffff000 through 0x1fffffff)

and does not have valid page table entries for any other pages.

What is the minimum number of second-level page tables stored for this program?

Suppose array1 and array2 are arrays of 4-byte ints and we perform the following:

for (int i = 0; i < 10000; i += 1) {
    for (int j = 0; j < 4; j += 4) {
        array1[i] += array2[(i * 3 + j) % 10000];
    }
}

Assume that only accesses to array1 and array2 use the cache and the compiler does not omit any memory accesses to array1 and array2.

Suppose this code runs with a 128-byte 2-way set associative cache with 8-byte blocks that is initially empty.

Which of the following changes would be likely to increase the number of cache misses the code experiences?

Suppose a system has a 4-way TLB with 128 entries on a system with 65536-byte pages.

A program accesses virtual address 0x123456 that, given the program's memory layout, corresponded to physical address 0x234567. When performing this access, the processor reads a TLB entry as part of completing the access and therefore avoids doing a page table lookup.

The processor might access a different TLB entry in the same set if the program accessed ___. Select all that apply.

Consider the following pseudocode library for a game where players try to change count to equal goal and be the first to call check when count matches goal.

pthread_mutex_t count_lock = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t goal_lock = PTHREAD_MUTEX_INITIALIZER;

int goal = 10;
int count = 0;

void change_goal(int new_goal) {
  pthread_mutex_lock(&goal_lock);
  goal = new_goal;
  pthread_mutex_unlock(&goal_lock);
}

void increment() {
  pthread_mutex_lock(&count_lock);
  count += 1;
  pthread_mutex_unlock(&count_lock);
}

void decrement() {
  pthread_mutex_lock(&goal_lock);
  pthread_mutex_lock(&count_lock);
  count -= 1;
  pthread_mutex_unlock(&goal_lock);
  pthread_mutex_unlock(&count_lock);
}

bool check() {
  pthread_mutex_lock(&count_lock);
  pthread_mutex_lock(&goal_lock);
  if (goal == count) printf("Winner! Goal %d reached.\n", goal);
  pthread_mutex_unlock(&goal_lock);
  pthread_mutex_unlock(&count_lock);
}

Assume there are exactly three threads playing this game. The threads can only access count_lock, goal_lock, goal, and count using the functions listed. No other threads are accessing this library.

What is possible while this game is being played? Select all that apply.

Consider the following program (assume all necessary headers are included).

size_t* weights[3];

void* A(void* argument) {
  int index = (int) argument;
  weights[index] = malloc(sizeof(size_t));
  return NULL;
}

void* B(void* argument) {
  int index = (int) argument;
  size_t val = 7;
  weights[index] = &val;
  return NULL;
}

void* C(void* argument) {
  int index = (int) argument;
  weights[index] = (size_t*) C;
  return NULL;
}

int main() {
  pthread_t p1, p2, p3;

  if (0 != pthread_create(&p1, NULL, A, 0)) handle_error();
  if (0 != pthread_create(&p2, NULL, B, 1)) handle_error();
  if (0 != pthread_create(&p3, NULL, C, 2)) handle_error();

  if (0 != pthread_join(p1, NULL)) handle_error();
  if (0 != pthread_join(p2, NULL)) handle_error();
  if (0 != pthread_join(p3, NULL)) handle_error();
}

At the end of main() (before main returns), which pointers are valid? (Consider a pointer valid if it points to accessible memory, even if interpreting that memory as a size_t might be dubious.) Select all that apply.

Suppose we have six-stage pipelined processor with a cycle time of 400 ps.

When running a function with 14 instructions, if we fetch the first instruction at time 0 ps, then the earliest time the last instruction could finish is in _____ ps. (Assume instructions do not finish until they complete their final stage.)

Suppose we take a single-cycle processor with a cycle time of 1 ns. It takes 1.00 s to run a program.

If we modify that processor by adding registers into a multi-cycle pipelined processor, then which of the following would be a plausible result when running the same program? Select all that apply.

Suppose an out-of-order processor with many functional units executes the following assembly snippet:

addq %r10, %r11
subq %r11, %r12
movq (%r11), %r12
xorq %r12, %r11
movq %r10, (%r13)

The movq (%r11), %r12 instruction could execute (perform its data cache operation) at the same time as ____ executes (performs its data cache and/or arithmetic operation). Select all that apply.

Suppose an out-of-order processor that uses register renaming is executing the following loop:

begin:  subq $1, %r8
        addq %r10, %r11
        cmpq %r8, %r9
        jle begin

Assuming this loop runs for many iterations, then most likely ___. Select all that apply.

Consider the following C function:

#define LEN 8
char hidden_string[LEN];

bool is_hidden_rotated(char *input_string) {
    for (int offset = 0; offset < LEN; offset += 1) {
        bool maybe_match = true;
        for (int i = 0; maybe_match && i < LEN; i += 1) {
            if (input_string[i] != hidden_string[(offset + i) % LEN]) {
                maybe_match = false;
            }
        }
        if (maybe_match) return true;
    }
    return false;
}

Assume that the compiler does not omit any of the comparison or array accesses shown above.

Suppose we can call this function and observe how long it takes and how fast cache accesses are after the function runs and know that an input of ABCDEFGH returns true. But we cannot directly observe the value of hidden_string.

What would be the best strategy to find out the value of hidden_string?

Suppose we run the following pseudocode:

char array[CACHE_SIZE];
...
for (int i = 0; i < CACHE_SIZE; i += 1) {
    array[i] = 0;
}
*pointer += 1;
for (int i = 0; i < CACHE_SIZE: i += 1) {
    if (TimeToAccess(&array[i]) >= THRESHOLD) {
        WasSlow(i);
    }
}

If we have a system without virtual memory with a 4-way 512KB (524288 byte) cache with 256-byte blocks and an LRU replacement policy, the array is placed at address 0x14000000. If WasSlow is called with i set to 512, then which (if any) of the following are possible values of pointer? Select all that apply.

Consider the following C code:

int array[1000];
int some_value;

...

array[mystery * 2] += some_value;
array[mystery * 3] += some_value;

Suppose we run the above code on a system without virtual memory and with a 2-way 64KB (65536 byte) data cache with 32-byte cache blocks.

If array is located at address 0x10004000 and we discover that running the above += operations accesses data cache set indices 514, 515, and 739.

Based on this, what is a plausible value of mystery?

Consider the following C-like psuedocode:

struct FileInfo {
    int is_socket;
    int socket_index;
    ...
};
struct FileInfo all_files[4096];
...

struct SocketInfo {
    unsigned long local_address;
    unsigned long remote_address;
    unsigned short remote_port;
    unsigned short local_port;
    ...
};

struct SocketInfo all_sockets[4096];

int GetLocalPortFor(int file_number)  {
    if (file_number < 0 || file_number >= 4096) {
        return -1;
    } else if (!all_files[file_number].is_socket) {
        return -1;
    } else {
        int socket_index = all_files[file_number].socket_index;
        struct SocketInio *socket_info = &all_sockets[socket_index];
        return socket_info->local_port;
    }
}

Suppose the above code runs in an OS kernel in kernel mode and the GetLocalPortFor function is callable via a system call.

Assuming no mitigations are made to prevent it, this function could be vulnerable to a Spectre-style attack based on the memory access to local_port. In a successful attack, the attacker will learn about a value in memory at a target address of their choice.

When executing the Spectre-style attack, we should choose file_number such that the target address is located in the same place as the address that would be computed for ____.