Suppose a program displays its logo when it starts. Rather than store that logo in a separate data file, the program includes it in its executable. To do this, multiple steps are used:

1. First a program converts the logo file from SVG format in the file logo.svg into BMP format in the file logo.bmp:

   svg2png logo.svg logo.bmp
   

2. Then, the BMP file logo.bmp is converted to a file logo.h file that defines an array of unsigned chars logo using the xxd utility:

   xxd -i logo.bmp logo.h
   

3. The file logo.h is included by main.c, along with the utility header file graphics.h and the C standard library headers <stdlib.h> and <stdio.h>.

Consider the following incomplete Makefile that implements this scheme, including building the final executalbe program. In this incomplete Makefile, lines or partial lines of code that are not yet complete are replaced by ### BLANK X ### where X is some number:

all: program

### BLANK 1 ###
    svg2png logo.svg logo.bmp

### BLANK 2 ###
    xxd -i logo.bmp logo.h

main.o: ### BLANK 3 ###

graphics.o: graphics.h

%.o: %.c
    clang -c $^

program: main.o graphics.o
    clang -o program main.o graphics.o

(Assume the commands in each rule are prefixed by tab characters.)

Suppose a single-core Unix-like system is running three processes, one for a text editor, one for a compiler, and one for simulation. The following sequence of events happens:

1. initially, the compiler is running on the processor to generate assembly in memory;
2. then, the compiler starts waiting for more source code to be read from disk;
3. while the compiler is waiting, the simulation runs and does computations in memory, including using many functions in <math.h>
4. then, a keypress occurs and as a result, the text editor immediately runs to process the keypress and update the screen, and then ask for more input
5. then, after the keypress is handled, the simulation resumes running, continuing to do computations in memory
6. then, the compiler's read from disk finishes, and the compiler resumes generating assembly
7. the compiler opens and write a file back to disk to store the assembly it computed and starts waiting for this to complete
8. while the compiler is waiting for the data to finish being written by the disk, the simulation resumes running, performing computations in memory

On Linux, the sched_yield system call requests that the OS to context switch to another thread/process (if there is one to switch to). (sched_yield does not do anything else.)

For the following questions, suppose we are running a single-core Linux system with only two processes and that sched_yield calls and processes exiting are the only reason context switches occur, and that each call to sched_yield causes a context switch if another process can be run.

Suppose the first process is running the program:

int main() {
    int x = 1;
    printf("%d", x); fflush(stdout);
    x = x + 1;
    sched_yield();
    printf("%d", x); fflush(stdout);
    x = x + 1;
    sched_yield();
    printf("%d", x); fflush(stdout);
    exit(0);
}

and the second process is running the program:

int main() {
    printf("A"); fflush(stdout);
    sched_yield();
    printf("B"); fflush(stdout);
    sched_yield();
    printf("C"); fflush(stdout);
    exit(0);
}

(Assume all appropriate header files are #included.)

Suppose we start both of these programs at the same time, but arrange for the first process to initially have access to the processor.

For the following questions, suppose we run two processes. The first process runs with PID 48 and has a signal handler setup for SIGUSR1 with the following code:

int global = 0;
void handle_usr1_program1(int signum) {
    global += 1;
    int temp = global * 2 + global;
    printf("%d", temp); fflush(stdout);
    kill(54, SIGUSR1);
    printf("A"); fflush(stdout);
}

and the second process runs with PID 54 and has a signal handler setup for SIGUSR1 with the following code:

int global = 0;
void handle_usr1_program2(int signum) {
    global += 1;
    printf("%d", global); fflush(stdout);
}

Assume the code outside signal handlers in these processes does not do anything relevant to these questions (other than not exiting or exiting as described below) and that the signal handlers are setup using sigaction with an sa_flags value of SA_RESTART.

Consider the following program that uses the POSIX API:

pid_t orig_pid, other_pid;
void handle_signal(int signum) {
    if (signum == SIGUSR1) {
        printf("%d:SIGUSR1 ", (int) other_pid); fflush(stdout);
        if (other_pid != 0)
            kill(other_pid, SIGUSR2);
        else
            kill(orig_pid, SIGUSR2);
    } else {
        printf("%d:SIGUSR2 ", (int) other_pid); fflush(stdout);
        exit(0);
    }
}

int main() {
    struct sigaction sa;
    sa.sa_handler = &handle_signal;
    sigemptyset(&sa.sa_mask);
    sa.sa_flags = 0;
    sigaction(SIGUSR1, &sa, NULL);
    sigaction(SIGUSR2, &sa, NULL);
    orig_pid = getpid();
    other_pid = fork();
    if (other_pid == 0) {
        /* child process */
        kill(orig_pid, SIGUSR1);
        while (1) pause();
    } else {
        /* parent process */
        kill(other_pid, SIGUSR1);
        while (1) pause();
    }
}

Assume all relevant header files are #included, and that the call to fork does not fail.

For the questions below, assume that when this program runs that a signal handler is never started while a signal handler is already running in the same process.

The pause() function called by the code above waits until the current process receives a signal.

Consider the following program that uses the POSIX API:

int global = 0;
int main() {
    pid_t pid1, pid2;
    int status;
    pid1 = fork();
    if (pid1 == 0) {
        pid2 = fork();
        if (pid2 == 0) {
            global += 1;
        } else {
            global += 2;
            waitpid(pid2, &status, NULL);
        }
    } else {
        waitpid(pid1, &status, NULL); 
        pid2 = fork();
        if (pid2 == 0) {
            global += 4;
        } else {
            global += 8;
            waitpid(pid2, &status, NULL);
        }
    }
    printf("%d\n", global);
    return 0;
}

Assume all relevant header files are included and fork and waitpid do not fail.

Suppose an analyst wants to run an analysis on a large list of data files. They have a program they wrote called ./analyze, which reads a file from stdin and appends to a summary file.

Doing this by hand, they'd run commands like:

./analyze < first-file
./analyze < second-file
./analyze < third-file
...

They find that typing all these commands is tedious and fails to take advantage of their system having four cores, which could speed up the analysis by analyzing multiple files at the same time. So, they write a function to analyze a large list of files:

void analyze_all(int num_files, const char **filenames) {
    pid_t *pids = malloc(num_files * sizeof(pid_t));  // was erroneously not pointer on quiz as released
    for (int i = 0; i < num_files; i += 1) {
        pids[i] = fork();
        if (pids[i] < 0) {
            handle_error();
        } else if (pids[i] == 0) {
            int fd = open(filenames[i], O_RDONLY);
            if (fd < 0)
                handle_error();
            if (dup2(fd, STDIN_FILENO) < 0)
                handle_error();
            close(fd);
            const char *argv[] = {"./analyze", NULL};
            if (execv("./analyze", argv) < 0)
                handle_error();
        }
        /* LOCATION 1 */
    }
    /* LOCATION 2 */
}

This seems to function, but they discover that there are two problems:

• when the function returns, the analysis is still going on since it does not wait for the analyze programs to finish
• the function runs so many instances of the analyze program at the same time that it overloads their machine

The following questions ask about modifying the code to fix these issues. Throughout the questions, assume that the handle_error() function is never reached.

if (i >= 4) {
    waitpid(pids[i-3], NULL, 0);
}

Consider a system with a virtual memory system with:

• 13 bit virtual addresses
• 16 bit physical addresses
• 1024 byte pages

and the following page table:

*p += 1;

Suppose a system with 256 byte pages is running a process with the following memory layout (all address virtual, all ranges inclusive):

• 0x100-0x2ff (2 virtual pages): code and constants (read-only and executable)
• 0x300-0x4ff (2 virtual pages): global variables (read/write)
• 0x500-0x6ff (2 virtual pages): heap (read/write)
• 0xe00-0xfff (2 virtual pages): stack (read/write)
• (and all other virtual pages are not accessible to the process)

int fd = open("file.dat", O_RDWR);
char *p;
p = mmap(NULL, 4096, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);

Consider a system which uses single-level page tables with:

• 65536 (2 to the 16) byte pages (and therefore 16-bit page offsets)
• 32-bit virtual addresses
• 40-bit physical addresses
• 8 byte page table entries, which contain, starting with the most significant bits when interpreted as a 64-bit integer:
  • 24 unused bits (which must be 0)
  • a 24 bit physical page number
  • a 11 unused bits (which must be 0)
  • a user-mode-accessible bit
  • a readable bit
  • a writeable bit
  • an executable bit
  • a valid bit
• a page table base register, which contains the address of the first byte of the page table (so if the page table base register contains 0x10000, the first page table entry is at physical address 0x10000 and the second at 0x10008 and so on.)

movq 0x123450, %rax

Consider a system which uses three-level page tables with:

• 65536 (2 to the 16) byte pages (and therefore 16-bit page offsets)
• 55-bit virtual addresses
• 40-bit physical addresses
• 65536 byte page tables (at each level), each containing 8192 entries, where each entry is 8 bytes in size
• a page table base register, which contains the address of the first byte of the first-level page table (so if the page table base register contains 0x10000, the first page table entry in the first-level page table is at physical address 0x10000 and the second entry at 0x10008 and so on.)

Consider the following C snippet that computes two values sum and squared_sum from an array of doubles A with a constant number N elements.

double sum = 0.0;
for (int i = 0; i < N; ++i) {
    sum += A[i];
}
double squared_sum = 0.0;
for (int i = 0; i < N; ++i) {
    squared_sum += A[i] * A[i];
}

For the following questions, consider a direct-mapped data cache with 16 byte cache blocks.

Consider a two-way set associative cache whose contents are as follows. Data is written as as sequence of bytes, starting with the lowest address (lowest offset), with each byte written in hexadecimal. The "LRU way" bit indicates which way is least recently used in each set.

Consider a direct-mapped data cache with

• 16 byte cache blocks,
• 256 sets
• a write-allocate policy and a write-back policy

Suppose the cache is initially empty and a program using this cache does the following sequence of accesses, in this order:

• writing 4 bytes to an address with set index 4, block offset 8, tag 0x1234
• reading 4 bytes from an address with set index 3, block offset 0, tag 0x1234
• writing 4 bytes to an address with set index 3, block offset 4, tag 0x1234
• writing 4 bytes to an address with set index 4, block offset 0, tag 0x2000

In the following questions ask about what happens during the accesses above. Do not include anything that will happen while processing later accesses, even if they are affected by the accesses above.

Consider a direct-mapped data cache with

• 16 byte cache blocks,
• 256 sets

on a system where virtual memory is not in use.

Suppose a system has:

• 4096 byte pages;
• two-level page tables with 1024 entries in page tables at each level;
• a 2-way data TLB with 16 total entries; and
• a 8KB (8192 byte) data cache with 256-byte blocks which uses only physical addresses. (This cache has 8 block offset bits and 5 set index bits.)

Consider the following code that uses multiple threads using the POSIX ("pthreads") API.

int x, y;
void *thread_function(void *argument) {
    int *p = (int*) argument;
    *p = *p + x;
    return &y;
}

int main() {
    pthread_t thread;
    int z;
    x = 10; y = 20;
    if (0 != pthread_create(&thread, NULL, thread_function, &z))
        handle_error();
    printf("here\n");
    void *result;
    if (0 != pthread_join(thread, &result))
        handle_error();
    printf("%d %d %d %p\n", x, y, z, result);
    return 0;
}

Consider the following C code that uses the POSIX API and implements a binary search tree search function that can be called from multiple threads at the same time:

struct tree_node {
    int value;
    struct tree_node *left;
    struct tree_node *right;
    pthread_mutex_t lock;
};

bool Find(struct tree_node *node, int value) {
    bool result = false;
    if (node != NULL) {
        struct tree_node *next = NULL;
        pthread_mutex_lock(&node->lock);
        if (value == node->value) {
            result = true;
        } else {
            if (value < node->value) {
                next = node->left;
            } else {
                next = node->right;
            }
        }
        pthread_mutex_unlock(&node->lock);
        if (next != NULL) {
            result = Find(next, value);
        }
    }
    return result;
}

This Find function would be called by passing the root node of the tree as node and some integer value to search for.

pthread_mutex_lock(&root->lock);
struct tree_node *left;
left = root->left;
pthread_mutex_unlock(&root->lock);
pthread_mutex_lock(&left->lock);
struct tree_node *left_left;
left_left = left->left;
left->value = left_left->value;     /* Line A */
left->left = left_left->left;       /* Line B */
left->right = left_left->right;
free(left_left);
pthread_mutex_unlock(&left->lock);

Consider the following (incomplete) C code that uses barriers:

pthread_barrier_t barrier;
int global = 0;
int N, M;
void *f1(void *ignored) {
    for (int i = 0; i < N; i += 1) {
        pthread_barrier_wait(&barrier);
        printf("f1: %d, global: %d\n", i, global);
        global += i + 1;
        pthread_barrier_wait(&barrier);
    }
    return NULL;
}

void *f2(void *ignored) {
    for (int i = 0; i < M; i += 1) {
        pthread_barrier_wait(&barrier);
        if (_____________ /* BLANK 1 */) {
            global += 10;
        }
    }
    return NULL;
}

void run() {
    pthread_barrier_init(&barrier, NULL, 2);
    pthread_t t1, t2;
    N = 100;
    M = _________ /* BLANK 2 */;
    pthread_create(&t1, NULL, f1, NULL);
    pthread_create(&t2, NULL, f2, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    pthread_barrier_destroy(&barrier);
}

The _s marked "BLANK x" (for some x) represent some omitted code which is the subject of a question below.

Consider the following C code that uses the POSIX API (where identifiers in ALL_CAPITALS are integers defined elsewhere):

struct PageVersion {
    pthread_mutex_t lock;

    /* only accessed after locking 'lock' */
    char *label;
    char *data;
    struct Page *page;

    /* only accessed after locking 'page->lock' */
    struct PageVersion *next;
};

struct Page {
    pthread_mutex_t lock;
    struct PageVersion *all_versions;
    struct PageVersion *active_version;
};

struct PageVersion *add_version_to(struct Page *page, char *label, char *data) {
    struct PageVersion *version = malloc(sizeof(struct PageVersion));
    version->label = label;
    version->data = data;
    version->page = page;
    pthread_mutex_init(&version->lock);
    pthread_mutex_lock(&page->lock);
    version->next = page->all_versions;
    page->all_versions = version;
    pthread_mutex_unlock(&page->lock);
    return version;
}

void move_version_to_page(struct PageVersion *version, struct Page *new_page) {
    pthread_mutex_lock(&version->lock);
    pthread_mutex_lock(&version->page->lock);
    pthread_mutex_lock(&new_page->lock);
    struct PageVersion *iterator = version->page->all_versions;
    if (iterator == version) {
        version->page->all_versions = version->next;
    } else {
        while (iterator->next != version) {
            iterator = iterator->next;
        }
        iterator->next = iterator->next->next;
    }
    version->next = new_page->all_versions;
    new_page->all_versions = version;
    pthread_mutex_unlock(&new_page->lock);
    pthread_mutex_unlock(&version->lock);
    pthread_mutex_unlock(&version->page->lock);
}

bool set_active_by_label(struct Page *page, char *label) {
    bool found = false;
    pthread_mutex_lock(&page->lock);
    struct PageVersion *iterator = page->all_versions;
    while (iterator) {
        pthread_mutex_lock(&iterator->lock);
        if (0 == strcmp(iterator->label, label)) {
            found = true;
            page->active_version = iterator;
            break;
        }
        iterator = iterator->next;
        pthread_mutex_unlock(&iterator->lock);
    }
    pthread_mutex_unlock(&page->lock);
    return found;
}

Consider the following incomplete code that uses monitors:

pthread_mutex_t lock;
char *files[NUM_FILES];
bool file_is_ready_to_process[NUM_FILES];
bool file_is_processed[NUM_FILES];
pthread_cond_t file_is_ready_cv[NUM_FILES];
pthread_cond_t file_is_processed_cv[NUM_FILES];
pthread_cond_t any_file_processed_cv;

void PrepareFile(int index) {
    SetupFileToBeProcessed(files[index]);
    pthread_mutex_lock(&lock);
    file_is_ready_to_process[index] = true;
    pthread_cond_broadcast(&file_is_ready_cv[index]);
    pthread_mutex_unlock(&lock);
}

void ProcessFileWhenReady(int index) {
    pthread_mutex_lock(&lock);
    while (!file_is_ready_to_process[index]) {
        pthread_cond_wait(&file_is_ready_cv[index], &lock);
    }
    pthread_mutex_unlock(&lock);    /* LINE A */
    ProcessFile(files[index]);
    pthread_mutex_lock(&lock);      /* LINE B */
    file_is_processed[index] = true;
    pthread_cond_broadcast(&any_file_processed_cv);
    pthread_cond_broadcast(&file_is_processed_cv[index]);
    pthread_mutex_unlock(&lock);
}

void WaitForTwoFilesToBeProcessed(int index1, int index2) {
    pthread_mutex_lock(&lock);

    while (_______________________________________________ /* BLANK 1 */) {

        pthread_cond_wait(&file_is_processed_cv[_____ /* BLANK 2 */], &lock);
    }
    while (_______________________________________________ /* BLANK 3 */) {

        pthread_cond_wait(&file_is_processed_cv[_____ /* BLANK 4 */], &lock);
    }
    pthread_mutex_unlock(&lock);
}

/* returns first file_index_list[i] such that file_is_processed[file_index_list[i]]
   is false; if no such entry is exists, returns -1
 */
int FirstNonReadyFile(int *file_index_list, int files_index_list_length) {
    for (int i = 0; i < file_index_list_length; i += 1) {
        if (!file_is_processed[file_index_list[i]]))
            return file_index_list[i];
    }
    return -1;
}

void WaitForManyFilesToBeProcessed(int *file_index_list, int file_index_list_length) {
    pthread_mutex_lock(&lock);
    while (_______________________________________________ /* BLANK 5 */) {

        pthread_cond_wait(&any_file_processed_cv, &lock);  /* LINE C */
    }
    pthread_mutex_unlock(&lock);
}

Assume all relevant header files are included (and NUM_FILES is an integer constant larger than 10).

A line of _s marked with a comment like /* BLANK 1 */ indicates a place where code may need to be added to complete the code above.

When WaitForTwoFilesToBeProcessed(index1, index2) returns, file_is_processed[index1] and file_is_processed[index2] should both be true because they were set by ProecssFileWhenReady() in other threads.

Similarly, when WaitForManyFilesToBeProcessed(index_array, index_array_length) returns, file_is_processed[index_array[i]] should be true for all i from 0 to index_array_length - 1, inclusive.

Suppose two machines A and B are connected via a network that implements the "mailbox model" we discussed in lecture.

To send data reliably this way, one machine sends a message with that data, and expects the receiving machine to send an acknowledgments of each message with data sent. When acknowledgments are not received after waiting a long time, the data-sending machine is responsible for resending the message with data.

Suppose machine A and machine B are on separate wifi networks. The routers for these wifi networks are connected to a common wired network.

Suppose A, B, and C attempt to secure communication using (symmetric) cryptography. To do this, they have three shared keys:

• key 1 is known by A, B, and C
• key 2 is known by just A and B

Suppose A is sending data to B via C and wants to ensure that C cannot interfere or eavesdrop despite C's role in forwarding the message. To do this, A will encode the message using some cryptographic scheme before providing it to C to forward. Suppose (like the examples in lecture) we have an encryption and decryption functions E(key, message) (which produces a ciphertext) and D(key, ciphertext) (which recovers the original message), and a MAC function E(key, message) (which produces a MAC "tag"). In the options below, E(x, y) means the result of applying E to x and y, and similar for MAC(x, y).

The following questions ask which schemes prevent C from interfereing or eavesdropping in a particular way.

Consider a system for allowing students to submit course registration requests to the registrar.

The system uses the following insecure (as partly revealed in the correct answers to the questions below) scheme.

• the registrar and each student has their own private keys (separate keys for encryption and signing; assume the appropriate key is used depending on the operation required), which are not shared with anyone; the corresponding public keys are shared with all parties securely in advance
• a student's registration request consists of:
  • the student's name; and
  • a list of course registration requests, each containing:
    • a cryptographic hash of the identity of the course being registered for
    • a digital signature made using the student's private key over the cryptographic hash
    • a message encrypted using the registrar's public key containing:
      • the student's name
      • the section of the course the student is requesting
      • the identity of the course being registered for
• the student sends the request to the registrar over an (insecure) network
• the registrar verifies all signatures, that the messages decrypt properly, and that the student names all match when it receives them
• after processing the request, the registrar sends back a message containing:
  • the current time
  • a submessage encrypted using the student's public key containing:
    • a list of the courses the student is registered for
  • a digital signature made using the registrar's private key over:
    • the current time and the student's name

As an alternative to the asymmetric key exchange scheme we discussed in lecture (which we mentioned was commonly used in TLS), two communicating parties A and B can use asymmetric encryption or signatures in place of the special "asymmetric key exchange" operator. There is a secure way to do this, but the following questions discuss insecure ideas.

In the question below PE and PD represents asymmetric encryption and decryption. Assume that A and B have shared public keys for encryption and signature verification in advance, and that the corresponding private keys are never available to any attacker.

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

• fetch
• decode (include register file read)
• execute part 1
• execute part 2
• execute part 3
• memory
• writeback

Assume the stages do the same thing as the stages we discussed in lecture, except some of the stages we discussed in lecture are divided into multiple parts. When this happens, the divided stages need the inputs near the beginning of the stage for the first part and only have the results of that stage near the end of the stage for the last part.

Assume the processor resolves data hazards with a combination of stalling and forwarding.

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

instruction / cycle:    0  1  2  3  4  5  6  7  8  9  10 11 12
addq %r8, %r9           F  D  E1 E2 E3 M  W
imulq %r10, %r13           F  D  E1 E2 E3 M  W
movq (%r9), %r10              F  D  E1 E2 E3 M  W
subq %r8, %r9                    F  D  E1 E2 E3 M  W
nop                                 F  D  E1 E2 E3 M  W
nop                                    F  D  E1 E2 E3 M  W
xorq %r10, %r9                            F  D  E1 E2 E3 M  W

Consider the following C code:

int x = 100;
do {
    if (5 == x % 10)
        foo();
    quux();
    x -= 1;
} while (x >= 0);

For the following questions, consider an out-of-order processor with a similar design to what we discussed in lecture (with register renaming and a single instruction queue).

Suppose the processor executing the following assembly code:

addq %r8, %r9
subq %r9, %r10
xorq %r8, %r12
andq %r8, %r10
imulq %r12, %r10

(In each of the instructions above, the first operand is a source and the second is a source and destination of the instruction.)

Consider the following C code:

unsigned char table[256] = {
    0,
    11 % 256 , (2 * 11) % 256,
    (3 * 11) % 256, (4 * 11) % 256,
    ... /* and so on */
};


int Example(int x, int y) {
    if (x < 256) {
        unsigned char result = table[x];
        return table[(result + y) % 256];
    } else {
        return -1;
    }
}

Suppose table is located at address 0x100000, and the system has an 4-way L1 cache with 64-byte blocks and 256 sets.

To simplify this problem, assume that virtual memory is not in use.