CS3130 Spring 2023 quizzes

Suppose a single-core system is running three single-threaded processes A, B, and C.

The following events happen in the following order:

1. Process A asks to read from the keyboard. No input is available initially.
2. Process B does some computation.
3. Process B sends a signal to process C.
4. A key is pressed on the keyboard, causing process A to run.
5. Process A accesses an invalid memory location and is terminated as a result.
6. Process C's signal handler runs and prints a message to the screen.

Consider the following C code snippet running on a Linux system:

char buffer[1024];
int x, y;
fgets(buffer, sizeof buffer, stdin);
x = atoi(buffer);
fgets(buffer, sizeof buffer, stdin);
y = atoi(buffer);
printf("%d / %d = %d\n", x, y, x / y);

Consider the following C code snippet running on a Linux system:

char buffer[1024];
int x, y;
fgets(buffer, sizeof buffer, stdin);
x = atoi(buffer);
fgets(buffer, sizeof buffer, stdin);
y = atoi(buffer);
printf("%d / %d = %d\n", x, y, x / y);

Consider the following page table:

Suppose this page table is used on a system with 4096 byte pages. On this system, virtual addresses are divided into a 3-bit page number and a 12-bit page offset and physical addresses are divided into a 4-bit page number and a 12-bit page offset.

Consider a system with a virtual memory system with:

• a single-level page table
• 16-byte pages and therefore 4-bit page offsets
• 8-bit virtual addresses, divided up into a 4-bit virtual page number and 4-bit page offset
• 12-bit physical addresses, divided up into a 8-bit physical page number and 4-bit page offset
• page table entries stored as 2-byte integers where:
  • the most significant 8 bits are the physical page number
  • the least significant bit is the valid bit
  • the second least significant bit is the writeable bit
  • the third least significant bit is the user-mode accessible bit
  • the remaining bits are unused

Consider a system with a virtual memory system with:

• a 2-level page table table
• 4096-byte pages and therefore 12-bit page offsets
• 8-byte page table entries
• 4096-byte page tables at each level,
  • each of which starts at the beginning of a physical page, and
  • each of which contains 512 page table entries
• 36-bit physical addresses
• 30-bit virtual addreses, divided up into a 18-bit virtual page number (which is divided into two equal parts for the page lookup) and a 12-bit page offset

Suppose a system uses 4096-byte pages, so addresses have 12-bit page offsets.

Assume the system running this program is as lazy as possible in setting up page table entries -- it waits until a program accesses a virtual page to setup the page table entry for that page, following the allocate/load-on-demand strategy we discussed in lecture. (Perhaps a better strategy would be somewhere in between this lazy strategy and the strategy of loading everything in advance.)

The program starts, with all its pages initially unallocated (marked invalid in its page table). It then runs a function, whose machine code is loaded at addresses 0x2040-0x2072, which writes 3 8-byte values to the stack at addresses 0xFFF8, 0xFFF0, and 0xFFE8.

Suppose a system has:

• four-level page tables
• 16-bit virtual addresses
• 16-byte pages, and therefore 4-bit page offsets
• page tables at each level which contain 8 2-byte page table entries
• the 2-byte page table entries contain a 1-bit valid bit in the least significant bit, a 12-bit physical page number in the most significant bits, and the rest is unused

Consider a network which provides the best-effort "mailbox" model gaurentees we discussed in lecture.

Suppose we try to send data from machine A to machine B that doesn't fit in a single message in parts using the following broken protocol:

• machine A splits the data into four parts, and sends each of the parts in a separate message; then
• once machine B receives all four parts, it sends an acknowledgment that all the messages were received
• if machine A doesn't get an acknowledgment after a certain amount of time, it sends all four parts again, repeating indefinitely
• machine B takes the last four message it gets before sending an acknowledgment and combines them (in order it received them) to reconstruct the data. If machine B doesn't get all four messages, it waits indefinitely

Suppose www.foo.com's DNS server when queried returns a record containing the IP address for www.foo.com specifying a time-to-live of 10000 seconds.

In lecture, we mentioned key agreement protocols where two parties A and B would send each other key shares derived from secret values, then use the other's key share and their secret value to construct a shared secret value (known by A and B, but not anyone else).

Consider two strategies for eliminating duplicates from an array of values:

1. constructing a hashtable from the list of values, discarding any values found that were already in the hashtable
2. sorting the array of values, then removing consecutive items that have the same value

Suppose a 8-set direct mapped cache with 4B blocks has the following contents:

Consider the following C code:

unsigned char array[12];
...
a = array[0]; // (1)
b = array[0]; // (2)
sum += a * b;
a = array[4]; // (3)
b = array[1]; // (4)
sum += a * b;
a = array[8]; // (5)
b = array[2]; // (6)

For the following questions assume that:

1. array starts at an address that is a multiple of 4096 (2 to the 12th power)
2. only accesses to array use the data cache
3. the compiler does not reorder or optimize the code to reduce the number of memory accesses for array
4. the data cache is initially empty (all blocks invalid) when the code labeled (1) starts.

Consider the following C snippet:

unsigned char array1[4096];
unsigned char array2[4096];
...
for (int i = 0; i < 2048; ++i) {
    array1[i] = array2[i + 2048] * array2[i];
}

For the following questions, assume:

1. the snippet uses a 32768-byte 4-way set-associative cache with 64-byte blocks and an LRU replacement policy;
2. the data cache is initially empty when the for loop starts;
3. array1 and array2 are both located at addresses that are multiples of 32768.

Consider a system with:

• 4096-byte pages
• 50-bit physical addresses
• 48-bit virtual addresses
• 4-level page tables where
  • page tables at each level hold 512 8-byte entries
• a 2-way 4-entry data TLB with a random replacement policy
• a 2-way 4-entry instruction TLB with a random replacement policy
• a 16384-byte 4-way set associative data cache with 64-byte blocks that uses physical addresses
• a 16384-byte 4-way set associative instruction cache with 64-byte blocks that uses physical addresses

movq 0x12345, %rax

Consider the following C code:

void *thread_func(void *arg) {
    int *p;
    p = (int*) arg;
    *p = 1;         /* <----------------------------------- LINE A */
    return (void*) (p + 2);
}

void foo() {
    int array[4] = {0, 0, 0, 0};
    pthread_t thread_ids[2];
    for (int i = 0; i < 2; i += 1) {
        int *q = &array[i];
        pthread_create(&thread_ids[i], NULL, thread_func, (void*) q);
    }
    for (int i = 0; i < 2; i += 1) {
        int *r = NULL;
        pthread_join(&thread_ids[i], (void**) &r);
        *r = 2;     /* <----------------------------------- LINE B */
    }
    printf("%d %d %d %d\n", array[0], array[1], array[2], array[3]);
}

Consider the following C code:

struct dynamic_array {
    int *data;
    size_t size;
    pthread_mutex_t lock;
};

void append_to_array(struct dynamic_array *dest, struct dynamic_array *to_add) {
    pthread_mutex_lock(&dest->lock);
    pthread_mutex_lock(&to_add->lock);
    int *new_data;
    size_t new_size = (dest->size + to_add->size) * sizeof(int);

    /* BEFORE REALLOC */
    new_data = realloc(dest->data, new_size);
        /* was incorrectly new_data = realloc(dest, new_size)  in quiz as released */

    if (!new_data) { abort(); /* out of memory */ }
    dest->data = new_data;
    /* AFTER REALLOC */

    memcpy(dest->data + dest->size, to_add->data, to_add->size * sizeof(int));
        /* was incorrectly dest->new_data + dest->size  in quiz as released */
    dest->size += to_add->size;
    pthread_mutex_unlock(&to_add->lock);
    pthread_mutex_unlock(&dest->lock);
}

Consider the following C code:

struct dynamic_array {
    int *data;
    size_t size;
    pthread_mutex_t lock;
};

void append_to_array(struct dynamic_array *dest, struct dynamic_array *to_add) {
    pthread_mutex_lock(&dest->lock);
    pthread_mutex_lock(&to_add->lock);
    int *new_data;
    size_t new_size = (dest->size + to_add->size) * sizeof(int);
    new_data = realloc(dest->data, new_size);
    if (!new_data) { abort(); /* out of memory */ }
    dest->data = new_data;
    memcpy(dest->new_data + dest->size, to_add->data, to_add->size * sizeof(int));
    dest->size += to_add->size;
    pthread_mutex_unlock(&to_add->lock);
    pthread_mutex_unlock(&dest->lock);
}

Suppose we want to implement a variant of the producer-consumer pattern where producing threads can produce two types of values (type A and type B), and consumer threads can either wait for a value of a particular type A OR they can wait for a value of both type A and type B. When the threads wait, they should wait without consuming a lot of processor time.

To implement this, we'll use a Queue implementation that provides queue_enqueue, queue_dequeue, and queue_size operations.

The following quesitons ask about the following incompete implementation. Blanks (formatted like _____________) represent omitted code:

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

Queue a_values;
pthread_cond_t a_available = PTHREAD_COND_INITIALIZER;
Queue b_values;
pthread_cond_t both_available = PTHREAD_COND_INITIALIZER;

void EnqueueA(Item item) {
    pthread_mutex_lock(&lock);
    queue_enqueue(&a_values, item);
    _________________________________ /* BLANK 1 */
    pthread_mutex_unlock(&lock);
}

void EnqueueB(Item item) {
    pthread_mutex_lock(&lock);
    queue_enqueue(&b_values, item);
    pthread_cond_signal(&both_available);
    pthread_mutex_unlock(&lock);
}

Item DequeueA() {
    pthread_mutex_lock(&lock);
    while (queue_size(a_values) == 0) {
        pthread_cond_wait(&a_available, &lock);
    }
    Item result = queue_dequeue(&a_values);      /* was b_values when quiz originally released */
    pthread_mutex_unlock(&lock);
}

void DequeueBoth(Item *a_item_ptr, Item *b_item_ptr) {
    pthread_mutex_lock(&lock);

    while (_______________________________) { /* BLANK 2 */

        pthread_cond_wait(_________________ /* BLANK 3 */, &lock);
    }
    *a_item_ptr = queue_dequeue(&a_values);
    *b_item_ptr = queue_dequeue(&b_values);
    pthread_mutex_unlock(&lock);
}

Suppose we have a system where three threads are running in parallel and we want a function to send a value from thread 0 to thread 1, and another value from thread 1 to thread 2, and another value from thread 2 to thread 0. To do this, each thread calls a function like:

other_threads_value = SendAndReceiveValue(thread_id, my_value);

where my_value is the current thread's value and thread_id is 0, 1, or 2, depending on which thread is making the call.

Functions can call SendAndReceiveValue multiple times; each time they call it they should receive values from the following call to SendAndReceiveValue.

Consider the following implementation of this function using semaphores:

int values[3];
sem_t value_ready[3];
sem_t value_empty[3];

int SendAndReceiveValue(int thread_id, int value) {
    int other_thread_id = (thread_id + 1) % 3;
    sem_wait(&value_empty[other_thread_id]);
    values[other_thread_id] = value;
    sem_post(&value_ready[other_thread_id]);
    sem_wait(&value_ready[thread_id]);
    int received_value = values[thread_id];
    sem_post(&value_empty[thread_id]);
    return received_value;
}

For this question, consider a processor uses pipelining with 6 pipeline stages and a cycle time of 600 picoseconds (.000 000 6 milliseconds).

Consider a nine-stage pipelined processor with the following pipeline stages:

• a first fetch stage, during which a read from the instruction cache is started and the next program counter value is computed or predicted
• a second fetch stage, during which the read from the instruction cache is completed
• a decode stage, during which register values are read
• a first execute stage, at the beginning of which the operands for arithemtic operations need to be available
• a second execute stage
• a third execute stage, near the end of which the results of any arithmetic operations are available (and not earlier)
• a first memory stage, during which a data cache access is started (if necessary for the instruction)
• a second memory stage, during which a data cache access is completed
• a writeback stage, during which values are written to a registers

This processor uses forwarding combined with (when necessary) stalling to resolve data hazards.

addq %r8, %r9
xorq %r8, %r11
subq %r9, %r10

For the following question, consider a six-stage pipelined processor with the following pipeline stages:

• fetch
• decode
• execute 1
• execute 2
• memory
• writeback

For the two execute stages:

• the results of any conditional jump are computed during the execute 1 stage, allowing the correct instruction to be fetched during the execute 2 stage if it was mispredicted
• arithmetic instructions require their operands to be available near the beginning of the execute 1 stage
• arithmetic instructions have their results available near the end of the execute 2 stage

Suppose the processor is running the following assembly snippet:

    movq (%r8), %r9  
    subq $128, %r9   
    jle foo          
    addq %r9, %r10   

and the jle is mispredicted.

Consider the following assembly snippet:

    movq $4, %rax       // rax <- 4
start_loop:
    movq %r8, %r9       // r9 <- r8
    andq $3, %r9        // r9 <- r9 & 3
    cmpq $0, %r9        // set condition codes using r9 - 0
    jne skip            // if (r9 != 0) goto skip
    addq $1, %r8        // r8 <- r8 + 1     ***
skip:
    subq $1, %rax       // rax <- rax - 1
    cmp $0, %rax        // set condition codes using rax - 0
    jne start_loop      // if (rax != 0) goto start_loop
end_loop:

For the questions below, assume %r8 has an initial value of 4 every time the snippet above is run, in this case:

• the loop (marked by the start_loop and end_loop labels) will execute 4 times.

• during the first time the loop is executed, the addq $1, %r8 instruction will be executed

• during the other times the loop is executed, the addq $1, %r8 instruction will not be executed

Consider the following C code:

if (x < 1024) {
    char y = array1[x];
    if (y < 64) {
        foo(array2[y*2048]);
    }
}

where array1 and array2 are arrays of chars.

If an attacker can control x, they can use the Spectre vulnerability to read from memory using this code.

Suppose array1 is located at address 0x1000000, array2 is located at address 0x2000000. To simplfiy the problem, assume all addresses are physical.