Suppose a C project has a header file constants.h that is generated by processing a CSV constants.csv file with C program called csvtoconstantsh.

Then constants.h is used with main.c to generate a main executable. When run by hand the following sequence of commands are used:

clang -c csvtoconstantsh.c
clang -o csvtoconstantsh csvtoconstants.o
./csvtoconstantsh constants.csv constants.h
clang -c main.c
clang -o main main.o

constants.h: ...
(tab)./csvtoconstantsh constants.csv constants.h

Consider a Unix-like system with a single-core running three (single-threaded) processes, an SSH client, a graphical terminal (which is being used to display the SSH client), and a program performing a long computation

Initially process SSH client is active on the CPU, then the following events happen in the following order:

1. The SSH client computes some data and outputs it to the network.
2. The SSH client waits for new input from the network or its terminal
3. While the SSH client is waiting, the long computation program runs.
4. An "enter" keypress occurs, so the terminal program starts running to process it.
5. The terminal program adjusts the image it displays to account for a new line.
6. The terminal program forwards the keypress to the SSH client.
7. The SSH client receives the keypress.
8. As a result of the keypress, the SSH client sends something on the network.

Consider the following C code:

int global = 0;

void handle_sigint(int id) {
    global += 1;
    printf("SIGINT: global=%d\n", global);
}

int main() {
    Initialize();
    struct sigaction sa;
    sa.sa_handler = &handle_sigint;
    sigemptyset(&sa.sa_mask);
    sa.sa_flags = SA_RESTART;
    sigaction(SIGINT, &sa, NULL);

    char line[128];
    while (fgets(line, sizeof line, stdin)) {
        Process(line);
    }
}

Assume all necessary #includes and an implementation of the Initialize and Process functions are included, that these functions do not do anything with signals, that the system is setup so control-C always sends the signal SIGINT, and the C code is compiled into an executable.

For the following questions, consider a system with 7-bit page offsets, 10-bit virtual addresses and 11-bit physical addresses and the following page table:

Consider a system with page tables that are stored in memory as a single array. Suppose the system uses 65536 byte pages (so addresses have 16-bit page offsets), 4-byte page entries, and the page table base register is set to physical (byte) address 0x30000 (so the page table entry with index 0 is at 0x30000, the one with index 1 at 0x30004, the one with index 2 at 0x30008, etc.)

As part of translating a virtual address to a physical address, the system:

• accesses a page table entry at physical address 0x30110, and
• determines that the resulting physical address for the virtual address is 0x999433

For the following questions, consider a system with:

• two-level page tables
• page tables (at each level) containing 32 page table entries, each of which is 2 bytes in size
• 64-byte pages
• 16-bit virtual addresses
• 20-bit physical addresses

Consider the following C program (which uses the POSIX API):

// some needed #includes not shown
int global;
int main() {
    global = 0;
    printf("1"); fflush(stdout);
    pid_t p = fork();
    printf("2"); fflush(stdout);
    if (p == 0) {
        global = 3;
    } else {
        global = 4;
    }
    printf("%d", global); fflush(stdout);
    return 0;
}

For the following questions, assume:

• fork and printf and fflush do not fail;
• global always has a valid page table entry pointing to its storage in both processes
• in addition to valid bits, page table entries have permission bits for writing, execution, and user-mode accesses;

Consider the following incomplete C snippet (which uses the POSIX API):

int input_fd = open("input.txt", O_RDONLY);
if (input_fd < 0)
    handle_error();
pid_t pid = fork();

____________ /* 1 */
if (pid == 0) {
    ____________ /* 2 */
    const char *argv[] = {"./a.out", NULL};
    execv("./a.out", argv);
} else if (pid > 0) {
    ____________ /* 3 */
    int status;
    if ((pid_t) -1 == waitpid(pid, &status, 0)) {
        handle_error();
    }
}

In the snippet, __________ represents a blank to be replaced with code to complete the snippet.

For the following questions, assume that this program containing this snippet is not called a.out, and that open, fork, dup2,execv,closeandwaitpid` do not fail.

This code is intended to run a program called a.out, which normally would take input from the terminal using stdin, and have it read its input from input.txt

Consider a direct-mapped cache whose contents are as follows:

For the following questions, consider a 2-way set associative cache with an LRU (least recently used) replacement policy whose contents are as follows.

In the cache contents below, indices and tags are written in binary, and data bytes are written as a sequence of hexadecimal bytes with the lowest address first.

Suppose an array is declared as follows:

unsigned char array[16];

which is located at a memory address that is a multiple of 1024 (two to the tenth power).

and then we run the following C snippet:

int count = 0;
count += array[0];
count += array[3];
count += array[6];
count /= array[1];
count /= array[4];
count /= array[7];

For the following questions, consider a 2-way set associative cache with an LRU (least recently used) replacement policy, a write-back policy, and a write-allocate policy, whose contents are as follows.

In the cache contents below, indices and tags are written in binary, and data bytes are written as a sequence of hexadecimal bytes with the lowest address first.

Consider the following C code which is run only by calling the example() function:

struct thread_data {
    int x;
    int *p;
};

void *thread_func(void *raw_ptr) {
    struct thread_data *td;
    td = (struct thread_data *)raw_ptr;
    *(td->p) += td->x;      /* LINE A */
    td->x = *(td->p);       /* LINE B */
    return &td->x;
}

int global_array[2] = {0, 0};

void example() {
    pthread_t threads[2];
    for (int x = 0; x < 2; ++x) {
        struct thread_data *td;
        td = malloc(sizeof(struct thread_data));
        td->x = x;
        td->p = &global_array[x];
        int ret = pthread_create(&threads[x], NULL, thread_func, (void*) td);
        /* LINE C */
    }
    /* LINE D */
    for (int i = 0; i < 2; ++i) {
        void *raw_ptr;
        pthread_join(threads[i], &raw_ptr);
        int *p;
        p = (int*) raw_ptr;
        printf("got result %d\n", *p); /* LINE E */
    }
    /* LINE F */
}

The comments of the form "LINE X" are label particular parts of the code for the questions below.

Assume all appropriate #includes are used and the example() function is run and the example() function is the only thing that causes thread_func to be called or global_array to be accessed.

Consider the following code that uses mutexes:

pthread_mutex_t int_lock = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t ptr_lock = PTHREAD_MUTEX_INITIALIZER;

int global_int1 = 1;
int global_int2 = 2;
int global_int3 = 3;
int *global_ptr = &global_int1;

void thread1() {
    int *old_pointer;
    pthread_mutex_lock(&ptr_lock);
    old_pointer = global_ptr;
    global_ptr = &global_int3;
    pthread_mutex_unlock(&ptr_lock);        /* A */
    pthread_mutex_lock(&int_lock);
    global_int2 += global_int1;
    pthread_mutex_unlock(&int_lock);
    pthread_mutex_lock(&ptr_lock);          /* A */
    old_pointer = global_ptr;
    global_ptr = old_pointer;
    pthread_mutex_unlock(&ptr_lock);
}

void thread2() {
    pthread_mutex_lock(&ptr_lock);

    pthread_mutex_lock(&int_lock);          /* B */
    global_int1 += *global_ptr;         
    pthread_mutex_unlock(&int_lock);        /* B */
                                            /* C */
    global_ptr = &global_int2;
    pthread_mutex_unlock(&ptr_lock);
}

For the following questions, assume that thread1 and thread2 are started at the same time from different threads and run exactly once, and no other code manipulates the global variables above.

Consider the following code that uses barriers and mutexes:

pthread_barrier_t barrier;
pthread_mutex_t lock;
int x = 1, y = 2, z = 3;

void *thread1_func(void *) {
    pthread_mutex_lock(&lock);      /* LOCK A */
    y += z; 
    pthread_mutex_unlock(&lock);    /* UNLOCK A */
    pthread_barrier_wait(&barrier);
    pthread_mutex_lock(&lock);      /* LOCK B */
    x += z;
    pthread_mutex_unlock(&lock);    /* UNLOCK B */
    pthread_barrier_wait(&barrier);
}

void *thread2func(void *) {
    pthread_mutex_lock(&lock);      /* LOCK C */
    y += z;
    pthread_mutex_unlock(&lock);    /* UNLOCK C */
    pthread_barrier_wait(&barrier);
    pthread_mutex_lock(&lock);      /* LOCK D */
    y += z;
    pthread_mutex_unlock(&lock);    /* UNLOCK D */
    pthread_barrier_wait(&barrier);
    pthread_mutex_lock(&lock);      /* LOCK E */
    x += z;
    pthread_mutex_unlock(&lock);    /* UNLOCK E */
}

int main() {
    pthread_barrier_init(&barrier, 2);
    pthread_mutex_init(&lock, NULL);
    pthread_t thread1;
    pthread_t thread2;
    pthread_create(&thread1, NULL, thread1_func, NULL);
    pthread_create(&thread2, NULL, thread2_func, NULL);
    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);
    printf("%d %d %d\n", x, y, z);
    return 0;
}

Suppose we have a system for booking plane flights. This system needs to support booking a single ticket that encompasses multiple plane flights. To support this, the system, implemented in C with pthreads, uses the following data structures:

struct flight {
    pthread_mutex_t lock;
    int flight_id;
    int remaining_seats;
    struct tickets *tickets[MAX_SEATS];
};

struct ticket {
    int ticket_number;
    int num_flights;
    struct flight *flights[MAX_FLIGHTS];
};

The support booking and cancelling tickets, the system implements the following functions:

• struct ticket *BookTicket(int num_flights, struct flight *flights) --- books a ticket for the specified flights, or returns NULL if this is not possible due to insufficient remaining seats

• int ChangeTicket(struct ticket *ticket, int index, struct flight *new_flight) --- change the index'th flight (counting starting with 0) on the ticket ticket to new_flight. Return 0 if this is not possible due to insufficient remaining seats; otherwise return 1.

Psuedocode for these functions are as follows. Assume the AddTicketToFlight and RemoveTicketFromFlight functions handle adjusting remaining_seats.

struct ticket *BookTicket(int num_flights, struct flight *flights) {
    int can_book = 1;
    for (int i = 0; i < num_flights; i += 1) {
        pthread_mutex_lock(&flights[i]->lock);
        if (flights[i]->remaining_seats == 0) {
            can_book = 0;
        }
    }
    struct ticket *result;
    if (can_book) {
        result = AllocateTicket(num_flights, flights);
        for (int i = 0; i < num_flights; i += 1) {
            AddTicketToFlight(result, flights[i]);
        }
    }
    for (int i = 0; i < num_flights; i += 1) {
        pthread_mutex_unlock(&flights[i]->lock);
    }
    return result;
}

int ChangeTicket(struct ticket *ticket, int index, struct flight *new_flight) {
    int successful = 0;
    pthread_mutex_lock(&new_flight->lock);
    if (new_flight->remaining_seats > 0) {
        pthread_mutex_lock(&ticket->flights[index]->lock);
        RemoveTicketFromFlight(ticket->flights[index]);
        ticket->flights[index] = new_flight;
        AddTicketToFlight(ticket, new_flight);
        pthread_mutex_unlock(&ticket->flights[index]->lock);
        successful = 1;
    }
    pthread_mutex_unlock(&new_flight->lock);
    return successful;
}

Consider a server where users connect to the server and receive messages from a list of announcements. The server implementation uses one thread for each connected user, and in addition has another thread that adds messages Each user is part of a single "channel" that has a message history. These are represented using structs as follows:

const char *messages[MAX_MESSAGES];
int last_message_index = -1;
struct User users[NUM_USERS];
pthread_mutex_t message_lock;
pthread_cond_t new_message_cv;

struct User {
    int last_read_message_index; /* initially -1 */
};

When adding a message to the list of announcements, the server calls an AddMessage function. The threads representing user connections repeatedly calls a function called GetNextMessage to wait for and return a next message.

Partial implementations of these functions is shown below (where a blank written with underscores like __________ represents some omitted code):

void AddMessage(const char *message) {
    pthread_mutex_lock(&message_lock);
    last_message_index += 1;
    messages[last_messsage_index] = message;

    ________________________________________________        /* BLANK 1 */
    pthread_mutex_unlock(&message_lock);
}

const char *GetNextMessage(struct User *user) {
    pthread_mutex_lock(&message_lock);

    while (___________________________________________________) {       /* BLANK 2 */
        pthread_cond_wait(&new_message_cv, &message_lock);             
    }
    user->last_read_message_index += 1;
    const char *result = messages[user->last_read_message_index];
    pthread_mutex_unlock(&message_lock);
    return result;
}

As part of retrieving a web page from a remote web server, a machine running a web browser will send an acknowledgment to the remote web server.

To send this, the machine running the web browser will send an Ethernet frame on its local network, that contains a IP packet, which contains a TCP segment.

For the following questions assume that:

• A and B know each other's public keys;
• A and B have a shared encryption key (used for symmetric, non-public-key encryption) and a shared MAC (message authentication code) key;
• an attacker who can act as an eavesdropper and machine-in-the-middle is active on the network but does not have access to any non-public keys; and
• the encryption and MAC algorithms used are secure (no one without the appropriate key can decrypt or create a correct message authentication code)

Consider a seven-stage pipelined processor where the stages are:

• fetch
• decode (including reading registers)
• execute, part 1
• execute, part 2
• memory, part 1
• memory, part 2
• writeback

Assume that the results of arithmetic instructions are not available until near the end of the execute, part 2 stage. The results of instructions that load values from memory are not available until near the end of the memory, part 2 stage. Instructions that perform arithmetic need the values for the arithmetic by near the beginning of the execute, part 1 stage.

The processor uses forwarding (when possible without dramatically increasing cycle time) in combination with stalling to resolve data hazards.

movq 0x1234(%r8), %r9     
addq %r9, %r10            

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

Suppose a processor runs the following assembly snippet:

    movq $3, %r10
outer: 
    movq $2, %r11
inner:
    call foo
    subq $1, %r11
    cmpq $0, %r11
    jg inner
    subq $1, %r10
    cmpq $0, %r10
    jg outer

which could have been generated from this C code:

for (int i = 3; i > 0; i--) {
    for (int j = 2; j > 0; j--) {
        foo();
    }
}

Consider the following C function that adds two arbitrary-precision integers represented by an array of digit values ranging from 0 to 9, starting with the 1's place.

void AddNumbers(int num_digits, const char *a_digits, const char *b_digits, char *result_digits) {
    char carry = 0;
    for (int i = 0; i < num_digits; ++i) {
        result_digits[i] = a_digits[i] + b_digits[i] + carry;
        carry = 0;
        while (result_digits[i] > 10) {
            result_digits[i] -= 10;
            carry += 1;
        }
    }
}

Assume this is translated to assembly in a way which does not omit any arithmetic operations written in the C code above and that it runs on a processor where each arithmetic and comparison instruction takes a constant amount of time.

Consider the following C code:

struct message {
    unsigned int message_type;
    unsigned int message_length;
    char *data;
}; 

struct message_type {
     unsigned int seen_messages;
     ...
};

struct message pending_messages[MAX_NUM_MESSAGES];
struct message_type message_types[NUM_MESSAGE_TYPES];

void HandleMessage(int index) {
     if (index < MAX_NUM_MESSAGES) {
         unsigned int type = pending_messages[index].message_type;
         if (type < NUM_MESSAGE_TYPES) {
              message_types[type].seen_messages += 1;
              ... // additional message handling code
         }
     } else {
         abort();
     }
}

Assume that:

• pending_messages is located at address 0x101000,
• message_types at address 0x108000,
• sizeof(struct message) is 16,
• sizeof(struct message_type) is 128,
• the system runs with a single direct-mapped 256KB (2 to the 18 byte) data cache with 64 byte blocks (this cache has 4096 blocks and 4096 sets)

If an attacker can cause the above code to execute speculatively with a chosen value of the argument index, then they can use the above code to execute a Spectre-style attack and read an integer from memory at an attacker-chosen address that the above code can access but the attacker cannot.

In particular, the attacker would set index such that pending_messages[index].message_type ends up being located at the address. The code that increments seen_messages would access a memory location based on this value, which will cause the cache to be modified (even if this code is only executed speculatively).

The attacker will use a side channel to determine which sets of the data cache were accesssed when the increment of seen_messages was speculatively executed, and therefore learn about the value of type, which is the same as the value in the memory location the attacker chose.