Midterm sample questions

Review Questions:

This is a bank of questions from prior midterms. The real midterm will not have this many questions.

Some of these questions might not be appropriate this year. Most topics and questions that seem less appropriate this year, or which cover topics that we haven’t yet covered in class, are marked with ⚠️.

Previous exams used the following rules; this year’s rules will be similar.

The exam is open book, open note, open computer. You may access the book, and your own notes in paper form. You may also use a computer or equivalent to access your own class materials and public class materials. However, you may not access other materials except as explicitly allowed below. Specifically:

  • You may access a browser and a PDF reader.
  • You may access your own notes and problem set code electronically.
  • You may access an Internet site on which your own notes and problem set code are stored.
  • You may access the course site.
  • You may access pages directly linked from the course site, including our lectures, exercises, and section notes, and our preparation materials for the midterm (including solutions).
  • You may run a C compiler, including an assembler and linker, or a calculator.
  • You may use a Python interpreter.
  • You may access manual pages.

But:

  • You may not access Google or Wikipedia or anything else except as directly linked from the course site.
  • You may not access Piazza.
  • You may not access course videos.
  • You may not access an on-line disassembler, compiler explorer, or similar applications.
  • You absolutely may not contact other humans via IM or anything like it.
  • You may not access solutions from any previous exam, by paper or computer, except for those on the course site.

Any violations of this policy, or the spirit of this policy, are breaches of academic honesty and will be treated accordingly. Please appreciate our flexibility and behave honestly and honorably.

DATAREP-1. Sizes and alignments

QUESTION DATAREP-1A. True or false: For any non-array type X, the size of X (sizeof(X)) is greater than or equal to the alignment of type X (alignof(X)).

QUESTION DATAREP-1B. True or false: For any type X, the size of struct Y { X a; char newc; } is greater than the size of X.

QUESTION DATAREP-1C. True or false: For any types A1...An (with n ≥ 1), the size of struct Y is greater than the size of struct X, given:

struct X {
    A1 a1;
    ...
    An an;
};
struct Y {
    A1 a1;
    ...
    An an;
    char newc;
};

QUESTION DATAREP-1D. True or false: For any types A1...An (with n ≥ 1), the size of struct Y is greater than the size of union X, given:

union X {
    A1 a1;
    ...
    An an;
};
struct Y {
    A1 a1;
    ...
    An an;
};

QUESTION DATAREP-1E. Assume that structure struct Y { ... } contains K char members and M int members, with K≤M, and nothing else. Write an expression defining the maximum sizeof(struct Y).

QUESTION DATAREP-1F. You are given a structure struct Z { T1 a; T2 b; T3 c; } that contains no padding. What does (sizeof(T1) + sizeof(T2) + sizeof(T3)) % alignof(struct Z) equal?

QUESTION DATAREP-1G. Arrange the following types in increasing order by size. Sample answer: “1 < 2 = 4 < 3” (choose this if #1 has smaller size than #2, which has equal size to #4, which has smaller size than #3).

  1. char
  2. struct minipoint { uint8_t x; uint8_t y; uint8_t z; }
  3. int
  4. unsigned short[1]
  5. char**
  6. double[0]

DATAREP-2. Expressions

QUESTION DATAREP-2A. Here are eight expressions. Group the expressions into four pairs so that the two expressions in each pair have the same value, and each pair has a different value from every other pair. There is one unique answer that meets these constraints. m has the same type and value everywhere it appears (there’s one unique value for m that meets the problem’s constraints). Assume an x86-32 machine: a 32-bit architecture in which pointers are 32 bits long.

  1. sizeof(&m)
  2. -1
  3. m & -m
  4. m + ~m + 1
  5. 16 >> 2
  6. m & ~m
  7. m
  8. 1

DATAREP-3. Hello binary

This problem locates 8-bit numbers horizontally and vertically in the following 16x16 image. Black pixels represent 1 bits and white pixels represent 0 bits. For horizontal arrangements, the most significant bit is on the left as usual. For vertical arrangements, the most significant bit is on top.

A pixelated cat

Examples: The 8-bit number 15 (hexadecimal 0x0F, binary 0b00001111) is located horizontally at 3,4, which means X=3, Y=4.

15 is also located horizontally at 7,6.

The 8-bit number 0 is located vertically at 0,0. It is also located horizontally at 0,0 and 1,0.

The 8-bit number 134 (hexadecimal 0x86, binary 0b10000110) is located vertically at 8,4.

QUESTION DATAREP-3A. Where is 3 located vertically? (All questions refer to 8-bit numbers.)

QUESTION DATAREP-3B. Where is 12 located horizontally?

QUESTION DATAREP-3C. Where is 255 located vertically?

DATAREP-4. Hello memory

Shintaro Tsuji wants to represent the image of Question DATAREP-3 in computer memory. He stores it in an array of 16-bit unsigned integers:

unsigned short cute[16];

Row Y of the image is stored in integer cute[Y].

QUESTION DATAREP-4A. What is sizeof(cute), 2, 16, 32, or 64?

QUESTION DATAREP-4B. printf("%d\n", cute[0]); prints 16384. Is Shintaro’s machine big-endian or little-endian?

DATAREP-5. Hello program

Now that Shintaro has represented the image in memory as an array of unsigned short objects, he can manipulate the image using C. For example, here’s a function.

void swap(void) {
    for (int i = 0; i < 16; ++i) {
        cute[i] = (cute[i] << 8) | (cute[i] >> 8);
    }
}

Running swap produces the following image:

Swapped cat

Shintaro has written several other functions. Here are some images (A is the original):

Cat A Cat B Cat C Cat D Cat E

A

B

C

D

E
Cat F Cat G Cat H Cat I Cat J

F

G

H

I

J

For each function, what image does that function create?

QUESTION DATAREP-5A.

void f0() {
    for (int i = 0; i < 16; ++i) {
        cute[i] = ~cute[i];
    }
}

QUESTION DATAREP-5B.

void f1() {
    for (int i = 0; i < 16; ++i) {
        cute[i] = ((cute[i] >> 1) & 0x5555) | ((cute[i] << 1) & 0xAAAA);
        cute[i] = ((cute[i] >> 2) & 0x3333) | ((cute[i] << 2) & 0xCCCC);
        cute[i] = ((cute[i] >> 4) & 0x0F0F) | ((cute[i] << 4) & 0xF0F0);
        cute[i] =  (cute[i] >> 8)           |  (cute[i] << 8);
    }
}

QUESTION DATAREP-5C.

void f2() {
    char* x = (char*) cute;
    for (int i = 0; i < 16; ++i) {
        x[2*i] = i;
    }
}

For “fun”

The following programs generated the other images. Can you match them with their images?

void f3() {
    for (int i = 0; i < 16; ++i) {
        cute[i] &= ~(7 << i);
    }
}

void f4() {
    swap();
    for (int i = 0; i < 16; ++i) {
        cute[i] <<= i/4;
    }
    swap();
}

void f5() {
    for (int i = 0; i < 16; ++i) {
        cute[i] = -1 * !!(cute[i] & 64);
    }
}

void f6() {
    for (int i = 0; i < 8; ++i) {
        int tmp = cute[15-i];
        cute[15-i] = cute[i];
        cute[i] = tmp;
    }
}

void f7() {
    for (int i = 0; i < 16; ++i) {
        cute[i] = cute[i] & -cute[i];
    }
}

void f8() {
    for (int i = 0; i < 16; ++i) {
        cute[i] ^= cute[i] ^ cute[i];
    }
}

void f9() {
    for (int i = 0; i < 16; ++i) {
        cute[i] = cute[i] ^ 4080;
    }
}

DATAREP-6. Memory regions

Consider the following program:

struct ptrs {
    int** x;
    int* y;
};

struct ptrs global;

void setup(struct ptrs* p) {
    int* a = malloc(sizeof(int));
    int* b = malloc(sizeof(int));
    int* c = malloc(sizeof(int));
    int* d = malloc(sizeof(int));
    int* e = malloc(sizeof(int) * 2);
    int** f = malloc(4 * sizeof(int*));
    int** g = malloc(sizeof(int*));

    *a = 0;
    *b = 0;
    *c = (int) a;
    *d = *b;
    e[0] = 29;
    e[1] = (int) &d[100000];

    f[0] = b;
    f[1] = c;
    f[2] = 0;
    f[3] = 0;

    *g = c;

    global.x = f;
    global.y = e;

    p->x = g;
    p->y = &e[1];
}

int main(int argc, char** argv) {
    stack_bottom = (char*) &argc;
    struct ptrs p;
    setup(&p);
    m61_collect();
    do_stuff(&p);
}

This program allocates objects a through g on the heap and then stores those pointers in some stack and global variables. (It then calls our conservative garbage collector from class⚠️, but that won’t matter until the next problem.) We recommend you draw a picture of the state setup creates.

QUESTION DATAREP-6A. Assume that (uintptr_t) a == 0x8300000, and that malloc returns increasing addresses. Match each address to the most likely expression with that address value. The expressions are evaluated within the context of main. You will not reuse an expression.

Value         Expression
1. 0x8300040 A. &p
2. 0x8049894 B. (int*) *p.x[0]
3. 0x8361AF0 C. &global.y
4. 0x8300000 D. global.y
5. 0xBFAE0CD8 E. (int*) *p.y

DATAREP-7. Garbage collection

Here is the top-level function for the conservative garbage collector we wrote in class. (⚠️ 2018 note: We haven’t done this. ⚠️)

void m61_collect(void) {
    char* stack_top = (char*) &stack_top;

    // The entire contents of the heap start out unmarked
    for (size_t i = 0; i != nmr; ++i) {
        mr[i].marked = 0;
    }

    // Mark all reachable objects, starting with the roots (the stack)
    m61_markaccessible(stack_top, stack_bottom - stack_top);

    // Free everything that wasn't marked
    for (size_t i = 0; i != nmr; ++i) {
        if (mr[i].marked == 0) {
            m61_free(mr[i].ptr);
            --i;                // m61_free moved different data into this
                                // slot, so we must recheck the slot
        }
    }
}

This garbage collector is not correct because it doesn’t capture all memory roots.

Consider the program from the previous section, and assume that an object is reachable if do_stuff can access an address within the object via variable references and memory dereferences without casts or pointer arithmetic. Then:

QUESTION DATAREP-7A. Which reachable objects will m61_collect() free? Circle all that apply.

a

b

c

d

e

f

g

None of these

QUESTION DATAREP-7B. Which unreachable objects will m61_collect() not free? Circle all that apply.

a

b

c

d

e

f

g

None of these

QUESTION DATAREP-7C. Conservative garbage collection in C is often slower than precise garbage collection in languages such as Java. Why? Circle all that apply.

  1. C is generally slower than other languages.
  2. Conservative garbage collectors must search all reachable memory for pointers. Precise garbage collectors can ignore values that do not contain pointers, such as large character buffers.
  3. C programs generally use the heap more than programs in other languages.
  4. None of the above.

DATAREP-8. Memory errors

The following function constructs and returns a lower-triangular matrix of size N. The elements are random 2-dimensional points in the unit square. The matrix is represented as an array of pointers to arrays.

struct point2 {
    double d[2];
};
typedef point2* point2_vector;

point2_vector* make_random_lt_matrix(size_t N) {
    point2_vector* m = (point2_vector*) malloc(sizeof(point2_vector) * N);
    for (size_t i = 0; i < N; ++i) {
        m[i] = (point2*) malloc(sizeof(point2) * (i + 1));  /* LINE A */
        for (size_t j = 0; j <= i; ++j) {
            for (int d = 0; d < 2; ++d) {
                m[i][j].d[d] = drand48();                   /* LINE B */
            }
        }
    }
    return m;
}

This code is running on an x86-32 machine (size_t is 32 bits, not 64). You may assume that the machine has enough free physical memory and the process has enough available virtual address space to satisfy any memory allocation request.

QUESTION DATAREP-8A. Give a value of N so that, while make_random_lt_matrix(N) is running, no new fails, but a memory error (such as a null pointer dereference or an out-of-bounds dereference) happens on Line A. The memory error should happen specifically when i == 1.

(This problem is probably easier when you write your answer in hexadecimal.)

QUESTION DATAREP-8B. Give a value of N so that no new fails, and no memory error happens on Line A, but a memory error does happen on Line B.

DATAREP-9. Data representation

Assume a 64-bit x86-64 architecture unless explicitly told otherwise.

Write your assumptions if a problem seems unclear, and write down your reasoning for partial credit.

QUESTION DATAREP-9A. Arrange the following values in increasing numeric order. Assume that x is an int with value 8192.

1. EOF 5. 1000
2. x & ~x 6. (signed char) 65535
3. (signed char) 0x47F 7. The size of the stdio cache
4. x | ~x 8. -0x80000000

A possible answer might be “a < b < c = d < e < f < g < h.”

For each of the remaining questions, write one or more arguments that, when passed to the provided function, will cause it to return the integer 61 (which is 0x3d hexadecimal). Write the expected number of arguments of the expected types.

QUESTION DATAREP-9B.

int f1(int n) {
    return 0x11 ^ n;
}

QUESTION DATAREP-9C.

int f2(const char* s) {
    return strtol(s, nullptr, 0);
}

QUESTION DATAREP-9D. Your answer should be different from the previous answer.

int f3(const char* s) {
    return strtol(s, nullptr, 0);
}

QUESTION DATAREP-9E. For this problem, you will also need to define a global variable. Give its type and value.

f4:
    andl $5, %edi
    leal (%rsi,%rdi,2), %eax
    movzbl y(%rip), %ecx
    subl %ecx, %eax
    retq

DATAREP-10. Sizes and alignments

Assume a 64-bit x86-64 architecture unless explicitly told otherwise.

Write your assumptions if a problem seems unclear, and write down your reasoning for partial credit.

QUESTION DATAREP-10A. Use the following members to create a struct of size 16, using each member exactly once, and putting char a first; or say “impossible” if this is impossible.

  1. char a; (we’ve written this for you)
  2. unsigned char b;
  3. short c;
  4. int d;
struct size_16 {
    char a;




};

QUESTION DATAREP-10B. Repeat Part A, but create a struct with size 12.

struct size_12 {
    char a;




};

QUESTION DATAREP-10C. Repeat Part A, but create a struct with size 8.

struct size_8 {
    char a;




};

QUESTION DATAREP-10D. Consider the following structs:

struct x {
    T x1;
    U x2;
};
struct y {
    struct x y1;
    V y2;
};

Give definitions for T, U, and V so that there is one byte of padding in struct x after x2, and two bytes of padding in struct y after y1.

DATAREP-11. Dynamic memory allocation

QUESTION DATAREP-11A. True or false?

  1. free(nullptr) is an error.
  2. malloc(0) can never return nullptr.

QUESTION DATAREP-11B. Give values for sz and nmemb so that calloc(sz, nmemb) will always return nullptr (on a 32-bit x86 machine), but malloc(sz * nmemb) might or might not return null.

Consider the following 8 statements. (p and q have type char*.)

  1. free(p);
  2. free(q);
  3. p = q;
  4. q = nullptr;
  5. p = (char*) malloc(12);
  6. q = (char*) malloc(8);
  7. p[8] = 0;
  8. q[4] = 0;

QUESTION DATAREP-11C. Put the statements in an order that would execute without error or evoking undefined behavior. Memory leaks count as errors. Use each statement exactly once. Sample answer: “abcdefgh.”

QUESTION DATAREP-11D. Put the statements in an order that would cause one double-free error, and no other error or undefined behavior (except possibly one memory leak). Use each statement exactly once.

QUESTION DATAREP-11E. Put the statements in an order that would cause one memory leak (one allocated piece of memory is not freed), and no other error or undefined behavior. Use each statement exactly once.

QUESTION DATAREP-11F. Put the statements in an order that would cause one boundary write error, and no other error or undefined behavior. Use each statement exactly once.

DATAREP-12. Pointers and debugging allocators

You are debugging some students’ m61 code from Problem Set 1. The codes use the following metadata:

struct meta { ...
    meta* next;
    meta* prev;
};

meta* mhead;    // head of active allocations list

Their linked-list manipulations in m61_malloc are similar.

void* m61_malloc(size_t sz, const char* file, int line) {
    ...
    meta* m = (meta*) ptr;
    m->next = mhead;
    m->prev = nullptr;
    if (mhead) {
        mhead->prev = m;
    }
    mhead = m;
    ...
}

But their linked-list manipulations in m61_free differ.

Alice’s code:

void m61_free(void* ptr, ...) { ...
    meta* m = (meta*) ptr - 1;
    if (m->next != nullptr) {
        m->next->prev = m->prev;
    }
    if (m->prev == nullptr) {
        mhead = nullptr;
    } else {
        m->prev->next = m->next;
    }
    ...
}

Bob’s code:

void m61_free(void* ptr, ...) { ...
    meta* m = (meta*) ptr - 1;
    if (m->next) {
        m->next->prev = m->prev;
    }
    if (m->prev) {
        m->prev->next = m->next;
    }
    ...
}

Chris’s code:

void m61_free(void* ptr, ...) { ...
    meta* m = (meta*) ptr - 1;
    m->next->prev = m->prev;
    m->prev->next = m->next;
    ...
}

Donna’s code:

void m61_free(void* ptr, ...) { ...
    meta* m = (meta*) ptr - 1;
    if (m->next) {
        m->next->prev = m->prev;
    }
    if (m->prev) {
        m->prev->next = m->next;
    } else {
        mhead = m->next;
    }
    ...
}

You may assume that all code not shown is correct.

QUESTION DATAREP-12A. Whose code will segmentation fault on this input? List all students that apply.

int main() {
    void* ptr = malloc(1);
    free(ptr);
}

QUESTION DATAREP-12B. Whose code might report something like “invalid free of pointer [ptr1], not allocated” on this input? (Because a list traversal starting from mhead fails to find ptr1.) List all students that apply. Don’t include students whose code would segfault before the report.

int main() {
    void* ptr1 = malloc(1);
    void* ptr2 = malloc(1);
    free(ptr2);
    free(ptr1);   // <- message printed here
}

QUESTION DATAREP-12C. Whose code would improperly report something like “LEAK CHECK: allocated object [ptr1] with size 1” on this input? (Because the mhead list appears not empty, although it should be.) List all students that apply. Don’t include students whose code would segfault before the report.

int main() {
    void* ptr1 = malloc(1);
    free(ptr1);
    m61_printleakreport();
}

QUESTION DATAREP-12D. Whose linked-list code is correct for all inputs? List all that apply.

DATAREP-13. Arena allocation

Chimamanda Ngozi Adichie is a writing a program that needs to allocate and free a lot of nodes, where a node is defined as follows:

struct node {
    int key;
    void* value;
    node* left;
    node* right;      // also used in free list
};

She uses an arena allocator variant. Here’s her code.

struct arena_group {
    arena_group* next_group;
    node nodes[1024];
};

struct arena {
    node* frees;
    arena_group* groups;
};

node* node_alloc(arena* a) {
    if (!a->frees) {
        arena_group* g = new arena_group;
        // ... link `g` to `a->groups` ...
        for (size_t i = 0; i != 1023; ++i) {
            g->nodes[i].right = &g->nodes[i + 1];
        }
        g->nodes[1023].right = nullptr;
        a->frees = &g->nodes[0];
    }
    node* n = a->frees;
    a->frees = n->right;
    return n;
}

void node_free(arena* a, node* n) {
    n->right = a->frees;
    a->frees = n;
}

QUESTION DATAREP-13A. True or false?

  1. This allocator never has external fragmentation.
  2. This allocator never has internal fragmentation.

QUESTION DATAREP-13B. Chimamanda’s frenemy Paul Auster notices that if many nodes are allocated right in a row, every 1024th allocation seems much more expensive than the others. The reason is that every 1024th allocation initializes a new group, which in turn adds 1024 nodes to the free list. Chimamanda decides instead to allow a single element of the free list to represent many contiguous free nodes. The average allocation might get a tiny bit slower, but no allocation will be much slower than average. Here’s the start of her idea:

node* node_alloc(arena* a) {
    if (!a->frees) {
        arena_group* g = new arena_group;
        // ... link `g` to `a->groups` ...
        g->nodes[0].key = 1024;   // g->nodes[0] is the 1st of 1024 contiguous free nodes
        g->nodes[0].right = nullptr;
        a->frees = &g->nodes[0];
    }
    node* n = a->frees;
    // ???
    return n;
}

Complete this function by writing code to replace // ???.

QUESTION DATAREP-13C. Write a node_free function that works with the node_alloc function from the previous question.

void node_free(arena* a, node* n) {




}

QUESTION DATAREP-13D. Complete the following new function.

// Return the arena_group containing node `n`. `n` must be a node returned by
// a previous call to `node_alloc(a)`.
arena_group* node_find_group(arena* a, node* n) {
    for (arena_group* g = a->groups; g; g = g->next_group) {




    }
    return nullptr;
}

QUESTION DATAREP-13E. Chimamanda doesn’t like that the node_find_group function from part D takes O(G) time, where G is the number of allocated arena_groups. She remembers a library function that might help, posix_memalign:

int posix_memalign(void** memptr, size_t alignment, size_t size);

The function posix_memalign() allocates size bytes and places the address of the allocated memory in *memptr. The address of the allocated memory will be a multiple of alignment, which must be a power of two and a multiple of sizeof(void*). ...

“Cool,” she says, “I can use this to speed up node_find_group!” She now allocates a new group with the following code:

arena_group* g;
int r = posix_memalign(&g, 32768, sizeof(arena_group));
assert(r == 0); // posix_memalign succeeded

Given this allocation strategy, write a version of node_find_group that takes O(1) time.

arena_group* node_find_group(arena* a, node* n) {




}

DATAREP-14. Data representation

Sort the following expressions in ascending order by value, using the operators <, =, >. For example, if we gave you:

  1. int A = 6;
  2. int B = 0x6;
  3. int C = 3;

you would write C < A = B.

  1. unsigned char a = 0x191;
  2. char b = 0x293;
  3. unsigned long c = 0xFFFFFFFF;
  4. int d = 0xFFFFFFFF;
  5. int e = d + 3;
  6. f = 4 GB
  7. size_t g = sizeof(*s) (given short *s)
  8. long h = 256;
  9. i = 0b100000000000000000000000000000000000 (binary)
  10. unsigned long j = 0xACE - 0x101;

DATAREP-15. Memory

For the following questions, select the part(s) of memory from the list below that best describes where you will find the object.

  1. heap
  2. stack
  3. between the heap and the stack
  4. in a read-only data segment
  5. in a text segment starting at address 0x08048000
  6. in a read/write data segment
  7. in a register

Assume the following code, compiled without optimization.

#include <stdio.h>
#include <stdlib.h>
const long maxitems = 1000;
struct info {
    char name[20];
    unsigned int age;
    short height;
} s = { "sushi", 1, 9 };

int main(int argc, char* argv[]) {
    static long L = 0xbadf00d;
    unsigned long u = 0x8badf00d;
    int i, num = maxitems + 1;
    struct info *sp;
    printf("What did you do? %lx?\n", u);
    while (num > maxitems || num < 10) {
        printf("How much of it did you eat? ");
        scanf(" %d", &num);
    }
    sp = (struct info *)malloc(num * sizeof(*sp));
    for (i = 0; i < num; i++) {
        sp[i] = s;
    }
    return 0xdeadbeef;
}

QUESTION DATAREP-15A. The value 0xdeadbeef, when we are returning from main.

QUESTION DATAREP-15B. The variable maxitems

QUESTION DATAREP-15C. The structure s

QUESTION DATAREP-15D. The structure at sp[9]

QUESTION DATAREP-15E. The variable u

QUESTION DATAREP-15F. main

QUESTION DATAREP-15G. printf

QUESTION DATAREP-15H. argc

QUESTION DATAREP-15I. The number the user enters

QUESTION DATAREP-15J. The variable L

DATAREP-16. Memory and pointers

⚠️ This question may benefit from Unit 4, kernel programming. ⚠️

If multiple processes are sharing data via mmap, they may have the file mapped at different virtual addresses. In this case, pointers to the same object will have different values in the different processes. One way to store pointers in mmapped memory so that multiple processes can access them consistently is using relative pointers. Rather than storing a regular pointer, you store the offset from the beginning of the mmapped region and add that to the address of the mapping to obtain a real pointer. An alternative representation is called self-relative pointers. In this case, you store the difference in address between the current location (i.e., the location containing the pointer) and the location to which you want to point. Neither representation addresses pointers between the mmapped region and the rest of the address space; you may assume such pointers do not exist.

QUESTION DATAREP-16A. State one advantage that relative pointers have over self-relative pointers.

QUESTION DATAREP-16B. State one advantage that self-relative pointers have over relative pointers.

For the following questions, assume the following setup:

char* region; /* Address of the beginning of the region. */

// The following are sample structures you might find in
// a linked list that you are storing in an mmaped region.

struct ll1 {
     unsigned value;
     TYPE1 r_next; /* Relative Pointer. */
};
struct ll2 {
     unsigned value;
     TYPE2 sr_next; /* Self-Relative Pointer. */
};
ll1 node1;
ll2 node2;

QUESTION DATAREP-16C. Propose a type for TYPE1 and give 1 sentence why you chose that type.

QUESTION DATAREP-16D. Write a C expression to generate a (properly typed) pointer to the element referenced by the r_next field of ll1.

QUESTION DATAREP-16E. Propose a type for TYPE2 and give 1 sentence why you chose that type.

QUESTION DATAREP-16F. Write a C expression to generate a (properly typed) pointer to the element referenced by the sr_next field of ll2.

DATAREP-17. Data representation: Allocation sizes

union my_union {
    int f1[4];
    long f2[2];
};

int main() {
    void* p = malloc(sizeof(char*));
    my_union u;
    my_union* up = &u;
    ....
}

How much user-accessible space is allocated on the stack and/or the heap by each of the following statements? Assume x86-64.

QUESTION DATAREP-17A. union my_union { ... };

QUESTION DATAREP-17B. void* p = malloc(sizeof(char*));

QUESTION DATAREP-17C. my_union u;

QUESTION DATAREP-17D. my_union* up = &u;

DATAREP-18. Data representation: ENIAC

Professor Kohler has been developing Eddie’s NIfty Awesome Computer (ENIAC). When he built the C compiler for ENIAC, he assigned the following sizes and alignments to C’s fundamental data types. (Assume that every other fundamental type has the same size and alignment as one of these.)

Type sizeof alignof
char 1 1
char* 16 16 Same for any pointer
short 4 4
int 8 8
long 16 16
long long 32 32
float 16 16
double 32 32

QUESTION DATAREP-18A. This set of sizes is valid: it obeys all the requirements set by C’s abstract machine. Give one different size assignment that would make the set as a whole invalid.

QUESTION DATAREP-18B. What alignment must the ENIAC malloc guarantee?

For the following two questions, assume the following struct on the ENIAC:

struct s {
    char f1[7];
    char *f2;
    short f3;
    int f4;
};

QUESTION DATAREP-18C. What is sizeof(struct s)?

QUESTION DATAREP-18D. What is alignof(struct s)?

The remaining questions refer to this structure definition:

// This include file defines a struct inner, but you do not know anything
// about that structure, just that it exists.
#include "inner.hh"

struct outer {
    char f1[3];
    inner f2;
    short f3;
    int f4;
};

Indicate for each statement whether the statement is always true, possibly true, or never true on the ENIAC.

QUESTION DATAREP-18E: sizeof(outer) > sizeof(inner) (Always / Possibly / Never)

QUESTION DATAREP-18F: sizeof(outer) is a multiple of sizeof(inner) (Always / Possibly / Never)

QUESTION DATAREP-18G: alignof(outer) > alignof(struct inner) (Always / Possibly / Never)

QUESTION DATAREP-18H: sizeof(outer) - sizeof(inner) < 4 (Always / Possibly / Never)

QUESTION DATAREP-18I: sizeof(outer) - sizeof(inner) > 32 (Always / Possibly / Never)

QUESTION DATAREP-18J: alignof(inner) == 2 (Always / Possibly / Never)

DATAREP-19. Undefined behavior

Which of the following expressions, instruction sequences, and code behaviors cause undefined behavior? For each question, write Defined or Undefined. (Note that the INT_MAX and UINT_MAX constants have types int and unsigned, respectively.)

QUESTION DATAREP-19A. INT_MAX + 1 (Defined / Undefined)

QUESTION DATAREP-19B. UINT_MAX + 1 (Defined / Undefined)

QUESTION DATAREP-19C.

movq $0x7FFFFFFFFFFFFFFF, %rax
addl $1, %rax

(Defined / Undefined)

QUESTION DATAREP-19D. Failed memory allocation, i.e., malloc returns nullptr (Defined / Undefined)

QUESTION DATAREP-19E. Use-after-free (Defined / Undefined)

QUESTION DATAREP-19F. Here are two functions and a global variable:

const char string[128] = ".......";
int read_nth_char(int n) {
    return string[n];
}
int f(int i) {
    if (i & 0x40) {
        return read_nth_char(i * 2);
    } else {
        return i * 2;
    }
}

C’s undefined behavior rules would allow an aggressive optimizing compiler to simplify the code generated for f. Fill in the following function with the simplest C code you can, under the constraint that an aggressive optimizing compiler might generate the same object code for f and f_simplified.

int f_simplified(int i) {





}

DATAREP-20. Bit manipulation

It’s common in systems code to need to switch data between big-endian and little-endian representations. This is because networks represent multi-byte integers using big-endian representation, whereas x86-family processors store multi-byte integers using little-endian representation.

QUESTION DATAREP-20A. Complete this function, which translates an integer from big-endian representation to little-endian representation by swapping bytes. For instance, big_to_little(0x01020304) should return 0x04030201. Your return statement must refer to the u.c array, and must not refer to x. This function is compiled on x86-64 Linux (as every function is unless we say otherwise).

unsigned big_to_little(unsigned x) {
    union {
        unsigned intval;
        unsigned char c[4];
    } u;
    u.intval = x;



    return ______________________________________;
}

QUESTION DATAREP-20B. Complete the function again, but this time write a single expression that refers to x (you may refer to x multiple times, of course).

unsigned big_to_little(unsigned x) {



    return ______________________________________;
}

QUESTION DATAREP-20C. Now write the function little_to_big, which will translate a little-endian integer into big-endian representation. You may introduce helper variables or even call big_to_little if that’s helpful.

unsigned little_to_big(unsigned x) { 






}

DATAREP-21. Computer arithmetic

Bitwise operators and computer arithmetic can represent vectors of bits, which in turn are useful for representing sets. For example, say we have a function bit that maps elements to distinct bits; thus, bit(X) == (1 << i) for some i. Then a set {X0, X1, X2, …, Xn} can be represented as bit(X0) | bit(X1) | bit(X2) | … | bit(Xn). Element Xi is in the set with integer representation z if and only if (bit(Xi) & z) != 0.

QUESTION DATAREP-21A. What is the maximum number of set elements that can be represented in a single unsigned variable on an x86 machine?

QUESTION DATAREP-21B. Match each set operation with the C operator(s) that could implement that operation. (Complement is a unary operation.)
intersection          ==
equality ~
complement &
union ^
toggle membership
(flip whether an element is in the set)		 |

QUESTION DATAREP-21C. Complete this function, which should return the set difference between the sets with representations a and b. This is the set containing exactly those elements of set a that are not in set b.

unsigned set_difference(unsigned a, unsigned b) {





}

QUESTION DATAREP-21D. Below we’ve given a number of C++ expressions, some of their values, and some of their set representations for a set of elements. For example, the first row says that the integer value of expression 0 is just 0, which corresponds to an empty set. Fill in the blanks. This will require figuring out which bits correspond to the set elements A, B, C, and D, and the values for the 32-bit int variables a, x, and s. No arithmetic operation overflows; abs(x) returns the absolute value of x (that is, x < 0 ? -x : x).

Expression e Integer value Represented set
0 0 {}
a == a ______________ {A}
(unsigned) ~a < (unsigned) a ______________ {A}
a < 0 ______________ ______________
(1 << (s/2)) - 1 ______________ {A,B,C,D}
a * a ______________ {C}
abs(a) ______________ ______________
x & (x - 1) ______________ {}
x - 1 ______________ {A,D}
x ______________ ______________
s ______________ ______________

DATAREP-22. Bit Tac Toe

Brenda Bitdiddle is implementing tic-tac-toe using bitwise arithmetic. (If you’re unfamiliar with tic-tac-toe, see below.) Her implementation starts like this:

struct tictactoe {
    unsigned moves[2];
};
#define XS 0
#define OS 1

void tictactoe_init(tictactoe* b) {
    b->moves[XS] = b->moves[OS] = 0;
}

static const unsigned ttt_values[3][3] = {
    { 0x001, 0x002, 0x004 },
    { 0x010, 0x020, 0x040 },
    { 0x100, 0x200, 0x400 }
};

    // Mark a move by player `p` at row `row` and column `col`.
    // Return 0 on success; return –1 if position `row,col` has already been used.
    int tictactoe_move(tictactoe* b, int p, int row, int col) {
1.      assert(row >= 0 && row < 3 && col >= 0 && col < 3);
2.      assert(p == XS || p == OS);
3.      /* TODO: check for position reuse */
4.      b->moves[p] |= ttt_values[row][col];
5.      return 0;
    }

Each position on the board is assigned a distinct bit.

Tic-tac-toe, also known as noughts and crosses, is a simple paper-and-pencil game for two players, X and O. The board is a 3x3 grid. The players take turns writing their symbol (X or O) in an empty square on the grid. The game is won when one player gets their symbol in all three squares in one of the rows, one of the columns, or one of the two diagonals. X goes first; played perfectly, the game always ends in a draw.

You may access the Wikipedia page for tic-tac-toe.

QUESTION DATAREP-22A. Brenda’s current code doesn’t check whether a move reuses a position. Write a snippet of C code that returns –1 if an attempted move is reusing a position. This snippet will replace line 3.

QUESTION DATAREP-22B. Complete the following function. You may use the following helper function:

For full credit, your code should consist of a single “return” statement with a simple expression, but for substantial partial credit write any correct solution.

// Return the number of moves that have happened so far.
int tictactoe_nmoves(const tictactoe* b) {






}

QUESTION DATAREP-22C. Write a simple expression that, if nonzero, indicates that player XS has a win on board b across the main diagonal (has marks in positions 0,0, 1,1, and 2,2).

Lydia Davis notices Brenda’s code and has a brainstorm. “If you use different values,” she suggests, “it becomes easy to detect any win.” She suggests:

static const unsigned ttt_values[3][3] = {
    { 0x01001001, 0x00010002, 0x10100004 },
    { 0x00002010, 0x22020020, 0x00200040 },
    { 0x40004100, 0x00040200, 0x04400400 }
};

QUESTION DATAREP-22D. Repeat part A for Lydia’s values: Write a snippet of C code that returns –1 if an attempted move is reusing a position. This snippet will replace line 3 in Brenda’s code.

QUESTION DATAREP-22E. Repeat part B for Lydia’s values: Use popcount to complete tictactoe_nmoves.

int tictactoe_nmoves(const tictactoe* b) {








}

QUESTION DATAREP-22F. Complete the following function for Lydia’s values. For full credit, your code should consist of a single “return” statement containing exactly two constants, but for substantial partial credit write any correct solution.

// Return nonzero if player `p` has won, 0 if `p` has not won.
int tictactoe_check_win(const tictactoe* b, int p) {
    assert(p == XS || p == OS);







}

DATAREP-23. Memory and Pointers

Two processes are mapping a file into their address space. The mapped file contains an unsorted linked list of integers. As the processes cannot ensure that the file will be mapped at the same virtual address, they use relative pointers to link elements in the list. A relative pointer holds not an address, but an offset that user code can use to calculate a true address. Our processes define the offset as relative to the start of the file.

Thus, each element in the linked list is represented by the following structure:

struct ll_node {
    int value;
    size_t offset;
};

offset == (size_t) -1 indicates the end of the list. Other offset values represent the position of the next item in the list, calculated relative to the start of the file.

QUESTION DATAREP-23A. Write a function to find an item in the list. The function's prototype is:

ll_node* find_element(void* mapped_file, ll_node* list, int value);

The mapped_file parameter is the address of the mapped file data; the list parameter is a pointer to the first node in the list; and the value parameter is the value for which we are searching. The function should return a pointer to the linked list element if the value appears in the list or nullptr if the value is not in the list.

DATAREP-24. Integer representation

Write the value of the variable or expression in each problem, using signed decimal representation.

For example, if we gave you:

  1. int i = 0xA;
  2. int j = 0xFFFFFFFF;

you would write A) 10 B) -1.

QUESTION DATAREP-24A. int i = 0xFFFF; (You may write this either in decimal or as an expression using a power of 2)

QUESTION DATAREP-24B. short s = 0xFFFF; (You may write this either in decimal or as an expression using a power of 2)

QUESTION DATAREP-24C. unsigned u = 1 << 10;

QUESTION DATAREP-24D. ⚠️ From WeensyOS: unsigned long l = PTE_P | PTE_U;

QUESTION DATAREP-24E. int j = ~0;

QUESTION DATAREP-24F. ⚠️ From WeensyOS: sizeof(x86_64_pagetable);

QUESTION DATAREP-24G. Given this structure:

struct s {
    char c;
    short s;
    long l;
};
s* ps;

This expression: sizeof(ps);

QUESTION DATAREP-24H. Using the structure above: sizeof(*ps);

QUESTION DATAREP-24I. unsigned char u = 0xABC;

QUESTION DATAREP-24J. signed char c = 0xABC;

DATAREP-25. Data representation

In gdb, you observe the following values for a set of memory locations.

0x100001020:   0xa0   0xb1   0xc2   0xd3    0xe4   0xf5   0x06   0x17
0x100001028:   0x28   0x39   0x4a   0x5b    0x6c   0x7d   0x8e   0x9f
0x100001030:   0x89   0x7a   0x6b   0x5c    0x4d   0x3e   0x2f   0x10
0x100001038:   0x01   0xf2   0xe3   0xd4    0xc5   0xb6   0xa7   0x96

For each C expression below, write its value in hexadecimal. For example, if we gave you:

char *cp = (char*) 0x100001020; cp[0] =

the answer would be 0xa0.

Assume the following structure and union declarations and variable definitions.

struct _s1 {
       int i;
       long l;
       short s;
};

struct _s2 {
       char c[4];
       int i;
       struct _s1 s;
};

union _u {
       char c[8];
       int i;
       long l;
       short s;
};

char* cp = (char*) 0x100001020;
struct _s1* s1 = (struct _s1*) 0x100001020;
struct _s2* s2 = (struct _s2*) 0x100001020;
union _u* u = (union _u*) 0x100001020;

QUESTION DATAREP-25A. cp[4] =

QUESTION DATAREP-25B. cp + 7 =

QUESTION DATAREP-25C. s1 + 1 =

QUESTION DATAREP-25D. s1->i =

QUESTION DATAREP-25E. sizeof(s1) =

QUESTION DATAREP-25F. &s2->s =

QUESTION DATAREP-25G. &u->s =

QUESTION DATAREP-25H. s1->l =

QUESTION DATAREP-25I. s2->s.s =

QUESTION DATAREP-25J. u->l =

DATAREP-26. Sizes and alignments

Here’s a test struct with n members. Assume an x86-64 machine, where each Ti either is a basic x86-64 type (e.g., int, char, double) or is a type derived from such types (e.g., arrays, structs, pointers, unions, possibly recursively), and assume that ai≤8 for all i.

struct test {
    T1 m1;      // sizeof(T1) == s1, alignof(T1) == a1
    T2 m2;      // sizeof(T2) == s2, alignof(T2) == a2
    ...
    Tn mn;      // sizeof(Tn) == sn, alignof(Tn) == an
};

In these questions, you will compare this struct with other structs that have the same members, but in other orders.

QUESTION DATAREP-26A. True or false: The size of struct test is minimized when its members are sorted by size. In other words, if s1≤s2≤…≤sn, then sizeof(struct test) is less than or equal to the struct size for any other member order.

If true, briefly explain your answer; if false, give a counterexample (i.e., concrete types for T1, …, Tn that do not minimize sizeof(struct test)).

QUESTION DATAREP-26B. True or false: The size of struct test is minimized when its members are sorted by alignment. In other words, if a1≤a2≤…≤an, then sizeof(struct test) is less than or equal to the struct size for any other member order.

If true, briefly explain your answer; if false, give a counterexample.

QUESTION DATAREP-26C. True or false: The alignment of struct test is minimized when its members are sorted in increasing order by alignment. In other words, if a1≤a2≤…≤an, then alignof(struct test) is less than or equal to the struct alignment for any other member order.

If true, briefly explain your answer; if false, give a counterexample.

QUESTION DATAREP-26D. What is the maximum number of bytes of padding that struct test could contain for a given n? The answer will be a pretty simple formula involving n. (Remember that ai≤8 for all i.)

QUESTION DATAREP-26E. What is the minimum number of bytes of padding that struct test could contain for a given n?

DATAREP-27. Undefined behavior

QUESTION DATAREP-27A. Sometimes a conforming C compiler can assume that a + 1 > a, and sometimes it can’t. For each type below, consider this expression:

a + (int) 1 > a

and say whether the compiler:

  1. int a
  2. unsigned a
  3. char* a
  4. unsigned char a
  5. struct {int m;} a

QUESTION DATAREP-27B. The following code checks its arguments for sanity, but not well: each check can cause undefined behavior.

void sanity_check(int* array, size_t array_size, int* ptr_into_array) {
    if (array + array_size < array) {
        fprintf(stderr, "`array` is so big that it wraps around!\n");
        abort();
    }
    if (ptr_into_array < array || ptr_into_array > array + array_size) {
        fprintf(stderr, "`ptr_into_array` doesn’t point into the array!\n");
        abort();
    }
    ...

Rewrite these checks to avoid all undefined behavior. You will likely add one or more casts to uintptr_t. For full credit, write each check as a single comparison (no && or ||, even though the current ptr_into_array check uses ||).

array_size check:

ptr_into_array check:

QUESTION DATAREP-27C. In lecture, we discussed several ways to tell if a signed integer x is negative. One of them was the following:

int isnegative = (x & (1UL << (sizeof(x) * CHAR_BIT))) != 0;

But this is incorrect: it has undefined behavior. Correct it by adding two characters.

DATAREP-28. Memory errors and garbage collection

⚠️ We didn’t discuss garbage collectors in class this year. ⚠️

Recall that a conservative garbage collector is a program that can automatically free dynamically-allocated memory by detecting when that memory is no longer referenced. Such a GC works by scanning memory for currently-referenced pointers, starting from stack and global memory, and recursing over each referenced object until all referenced memory has been scanned. We built a conservative garbage collector in lecture datarep6.

QUESTION DATAREP-28A. An application program that uses conservative GC, and does not call free directly, will avoid certain errors and undefined behaviors. Which of the following errors are avoided? List all that apply.

  1. Use-after-free
  2. Double free
  3. Signed integer overflow
  4. Boundary write error
  5. Unaligned access

QUESTION DATAREP-28B. Write a C program that leaks unbounded memory without GC, but does not do so with GC. You should need less than 5 lines. (Leaking “unbounded” memory means the program will exhaust the memory capacity of any machine on which it runs.)

QUESTION DATAREP-28C. Not every valid C program works with a conservative GC, because the C abstract machine allows a program to manipulate pointers in strange ways. Which of the following pointer manipulations might cause the conservative GC from class to inappropriately free a memory allocation? List all that apply.

  1. Storing the pointer in a uintptr_t variable

  2. Writing the pointer to a disk file and reading it back later

  3. Using the least-significant bit of the pointer to store a flag:

    int* set_ptrflag(int* x, int flagval) {
    return (int*) ((uintptr_t) x | (flagval ? 1 : 0));
}
int get_ptrflag(int* x) {
    return (uintptr_t) x & 1;
}
int deref_ptrflag(int* x) {
    return *((int*) ((uintptr_t) x & ~1UL));
}

  4. Storing the pointer in textual form:

    void save_ptr(char buf[100], void* p) {
    sprintf(buf, "%p", p);
}
void* restore_ptr(const char buf[100]) {
    void* p;
    sscanf(buf, "%p", &p);
    return p;
}

  5. Splitting the pointer into two parts and storing the parts in an array:

    typedef union {
    unsigned long ival;
    unsigned arr[2];
} value;
value save_ptr(void* p) {
    value v;
    v.arr[0] = (uintptr_t) p & 0xFFFFFFFFUL;
    v.arr[1] = ((uintptr_t) p / 4294967296UL) & 0xFFFFFFFFUL;
    return v;
}

DATAREP-29. Bitwise

QUESTION DATAREP-29A. Consider this C fragment:

uintptr_t x = ...;
uintptr_t r = 0;
if (a < b) {
    r = x;
}

Or, shorter:

uintptr_t r = a < b ? x : 0;

Write a single expression that evaluates to the same value, but that does not use the conditional ?: operator. You will use the fact that a < b always equals 0 or 1. For full credit, do not use expensive operators (multiply, divide, modulus).

QUESTION DATAREP-29B. This function returns one more than the index of the least-significant 1 bit in its argument, or 0 if its argument is zero.

int ffs(unsigned long x) {
    for (int i = 0; i < sizeof(x) * CHAR_BIT; ++i) {
        if (x & (1UL << i)) {
            return i + 1;
        }
    }
    return 0;
}

This function runs in O(B) time, where B is the number of bits in an unsigned long. Write a version of ffs that runs instead in O(log B) time.

DATAREP-30. Data representation

QUESTION DATAREP-30A. Write a type whose size is 19,404,329 times larger than its alignment.

QUESTION DATAREP-30B. Consider a structure type T with N members, all of which have nonzero size. Assume that sizeof(T) == alignof(T). What is N?

QUESTION DATAREP-30C. What is a C type that obeys (T) -1 == (T) 255 on x86-64?

Parts D–G use this code. The architecture might or might not be x86-64.

unsigned char a[] = {
    0x7A, 0xEC, 0x0D, 0xBE, 0x99, 0x0A, 0xD8, 0x0E
};
unsigned* s1 = (unsigned*) &a[0];
unsigned* s2 = s1 + 1;

Assume that (uintptr_t) s2 - (uintptr_t) s1 == 4 and *s1 > *s2.

QUESTION DATAREP-30D. What is sizeof(a)?

QUESTION DATAREP-30E. What is sizeof(unsigned) on this architecture?

QUESTION DATAREP-30F. Is this architecture big-endian or little-endian?

QUESTION DATAREP-30G. Might the architecture be x86-64?

DATAREP-31. Memory errors

Mavis Gallant is starting on her debugging memory allocator. She’s written code that aims to detect invalid frees, where a pointer passed to m61_free was not returned by an earlier m61_malloc.

D1.    typedef struct m61_metadata {
D2.        size_t magic;
D3.        size_t padding;
D4.    } m61_metadata;

M1.    void* m61_malloc(size_t sz) {
M2.        m61_metadata* meta = base_malloc(sz + sizeof(m61_metadata));
M3.        meta->magic = 0x84157893401;
M4.        return (void*) (meta + 1);
M5.    }

F1.    void m61_free(void* ptr) {
F2.        m61_metadata* meta = (m61_metadata*) ptr - 1;
F3.        if (meta->magic != 0x84157893401) {
F4.            fprintf(stderr, "invalid free of %p\n", ptr);
F5.            abort();
F6.        }
F7.        base_free(ptr);
F8.    }

C1.    void* m61_calloc(size_t count, size_t sz) {
C2.        void* p = m61_malloc(sz * count);
C3.        memset(p, 0, sz * count);
C4.        return p;
C5.    }`

Help her track down bugs.

QUESTION DATAREP-31A. What is sizeof(struct m61_metadata)?

QUESTION DATAREP-31B. Give an m61_ function call (function name and arguments) that would cause both unsigned integer overflow and invalid memory accesses.

QUESTION DATAREP-31C. Give an m61_ function call (function name and arguments) that would cause integer overflow, but no invalid memory access within the m61_ functions. (The application might or might not make an invalid memory access later.)

QUESTION DATAREP-31D. These functions have some potential null pointer dereferences. Fix one such problem, including the line number(s) where your code should go.

QUESTION DATAREP-31E. Put a single line of C code in the blank. The resulting program should (1) be well-defined with no memory leaks when using default malloc/free/calloc, but (2) always cause undefined behavior when using Mavis’s debugging malloc/free/calloc.

... #includes ...
int main(void) {



    ________________________
}

QUESTION DATAREP-31F. A double free should print a different message than an invalid free. Write code so Mavis’s implementation does this; include the line numbers where the code should go.

ASM-1. Disassemble

Here’s some assembly produced by compiling a C program.

        .globl  f
        .align  16, 0x90
        .type   f,@function
f:
        movl    $1, %r8d
        jmp     .LBB0_1
.LBB0_6:
        incl    %r8d
.LBB0_1:
        movl    %r8d, %ecx
        imull   %ecx, %ecx
        movl    $1, %edx
.LBB0_2:
        movl    %edx, %edi
        imull   %edi, %edi
        movl    $1, %esi
        .align  16, 0x90
.LBB0_3:
        movl    %esi, %eax
        imull   %eax, %eax
        addl    %edi, %eax
        cmpl    %ecx, %eax
        je      .LBB0_7
        cmpl    %edx, %esi
        leal    1(%rsi), %eax
        movl    %eax, %esi
        jl      .LBB0_3
        cmpl    %r8d, %edx
        leal    1(%rdx), %eax
        movl    %eax, %edx
        jl      .LBB0_2
        jmp     .LBB0_6
.LBB0_7:
        pushq   %rax
.Ltmp0:
        movl    $.L.str, %edi
        xorl    %eax, %eax
        callq   printf
        movl    $1, %eax
        popq    %rcx
        retq

        .type   .L.str,@object
.L.str:
        .asciz  "%d %d\n"
        .size   .L.str, 7

QUESTION ASM-1A. How many arguments might this function have? Circle all that apply.

  1. 0
  2. 1
  3. 2
  4. 3 or more

QUESTION ASM-1B. What might this function return? Circle all that apply.

  1. 0
  2. 1
  3. −1
  4. Its first argument, whatever that argument is
  5. A square number other than 0 or 1
  6. None of the above

QUESTION ASM-1C. Which callee-saved registers does this function save and restore? Circle all that apply.

  1. %rax
  2. %rbx
  3. %rcx
  4. %rdx
  5. %rbp
  6. %rsi
  7. %rdi
  8. None of the above

QUESTION ASM-1D. This function handles signed integers. If we changed the C source to use unsigned integers instead, which instructions would change? Circle all that apply.

  1. movl
  2. imull
  3. addl
  4. cmpl
  5. je
  6. jl
  7. popq
  8. None of the above

QUESTION ASM-1E. What might this function print? Circle all that apply.

  1. 0 0
  2. 1 1
  3. 3 4
  4. 4 5
  5. 6 8
  6. None of the above

ASM-2. Assembly

Here is some x86 assembly code.

f:
         movl a, %eax
         movl b, %edx
         andl $255, %edx
         subl %edx, %eax
         movl %eax, a
         retq

QUESTION ASM-2A. Write valid C code that could have compiled into this assembly (i.e., write a C definition of function f), given the global variable declarations “extern unsigned a, b;.” Your C code should compile without warnings. REMINDER: You are not permitted to run a C compiler, except for the C compiler that is your brain.

QUESTION ASM-2B. Write different valid, warning-free C code that could have compiled into that assembly. This version should contain different operators than your first version. (For extra credit, use only one operator.)

QUESTION ASM-2C. Again, write different valid, warning-free C code that could have compiled into that assembly. In this version, f should have a different type than in your first version.

ASM-3. Assembly and Data Structures

For each code sample below, indicate the most likely type of the data being accessed. (If multiple types are equally likely, just pick one.)

QUESTION ASM-3A. movzbl %al, %eax

QUESTION ASM-3B. movl -28(%rbp), %edx

QUESTION ASM-3C. movsbl -32(%rbp), %eax

QUESTION ASM-3D. movzwl -30(%rbp), %eax

For each code sample below, indicate the most likely data structure being accessed (assume that g_var is a global variable). Be as specific as possible.

QUESTION ASM-3E. movzwl 6(%rdx,%rax,8), %eax

QUESTION ASM-3F. movl (%rdx,%rax,4), %eax

QUESTION ASM-3G.

movzbl 4(%rax), %eax
movsbl %al, %eax

For the remaining questions, indicate for what values of the register contents will the jump be taken.

QUESTION ASM-3H.

xorl %eax, %eax
jge LABEL

QUESTION ASM-3I.

testb $1, %eax
jne LABEL

QUESTION ASM-3J.

cmpl %edx, %eax
jl LABEL

ASM-4. Assembly language

The next four questions pertain to the following four code samples.

f1

f1:
       subq    $8, %rsp
       call    callfunc
       movl    %eax, %edx
       leal    1(%rax,%rax,2), %eax
       testb   $1, %dl
       jne     .L3
       movl    %edx, %eax
       shrl    $31, %eax
       addl    %edx, %eax
       sarl    %eax
.L3:
       addq    $8, %rsp
       ret

f2

f2:
       pushq   %rbx
       xorl    %ebx, %ebx
.L3:
       movl    %ebx, %edi
       addl    $1, %ebx
       call    callfunc
       cmpl    $10, %ebx
       jne     .L3
       popq    %rbx
       ret

f3

f3:
       subq    $8, %rsp
       call    callfunc
       subl    $97, %eax
       cmpb    $4, %al
       ja      .L2
       movzbl  %al, %eax
       jmp     *.L4(,%rax,8)
.L4:
       .quad   .L3
       .quad   .L9
       .quad   .L6
       .quad   .L7
       .quad   .L8
.L3:
       movl    $42, %edx
       jmp     .L5
.L6:
       movl    $4096, %edx
       jmp     .L5
.L7:
       movl    $52, %edx
       jmp     .L5
.L8:
       movl    $6440, %edx
       jmp     .L5
.L2:
       movl    $0, %edx
       jmp     .L5
.L9:
       movl    $61, %edx
.L5:
       movl    $.LC0, %esi
       movl    $1, %edi
       movl    $0, %eax
       call    __printf_chk
       addq    $8, %rsp
       ret
.LC0:
       .string "Sum = %d\n"

f4

f4:
       subq    $40, %rsp
       movl    $1, (%rsp)
       movl    $0, 16(%rsp)
.L2:
       leaq    16(%rsp), %rsi
       movq    %rsp, %rdi
       call    callfunc
       movl    16(%rsp), %eax
       cmpl    %eax, (%rsp)
       jne     .L2
       addq    $40, %rsp
       ret

Now answer the following questions. Pick the most likely sample; you will use each sample exactly once.

QUESTION ASM-4A. Which sample contains a for loop?

QUESTION ASM-4B. Which sample contains a switch statement?

QUESTION ASM-4C. Which sample contains only an if/else construct?

QUESTION ASM-4D. Which sample contains a while loop?

ASM-5. Calling conventions: 6186

University Professor Helen Vendler is designing a poetic new processor, the 6186. Can you reverse-engineer some aspects of the 6186’s calling convention from its assembly?

Here’s a function:

int f(int* a, unsigned b) {
    extern int g(int x);
    int index = g(a[2*b + 1]);
    return a[index + b];
}

And here’s that function compiled into 6186 instructions.

f:
    sub $24, %rsp
    movq %ra, (%rsp)
    mov %rb, %rx
    shl $1, %rx
    add $1, %rx
    movl (%ra, %rx, 4), %ra
    call g
    add %rb, %rr
    movq (%rsp), %ra
    movl (%ra, %rr, 4), %ra
    mov %ra, %rr
    add $24, %rsp
    ret

6186 assembly syntax is based on x86-64 assembly, and like the x86-64, 6186 registers are 64 bits wide. However, the 6186 has a different set of registers. There are just five general-purpose registers, %ra, %rb, %rr, %rx, and %ry. (“[W]hen she tries to be deadly serious she is speaking under…constraint”.) The example also features the stack pointer register, %rsp.

Give brief explanations if unsure.

QUESTION ASM-5A. Which register holds function return values?

QUESTION ASM-5B. What is sizeof(int) on the 6186?

QUESTION ASM-5C. Which general-purpose register(s) must be callee-saved?

QUESTION ASM-5D. Which general-purpose register(s) must be caller-saved?

QUESTION ASM-5E. Which general-purpose register(s) might be callee-saved or caller-saved (you can’t tell which)?

QUESTION ASM-5F. Assuming the compiler makes function stack frames as small as possible given the calling convention, what is the alignment of stack frames?

QUESTION ASM-5G. Assuming that the 6186 supports the same addressing modes as the x86-64, write a single instruction that has the same effect on %ra as these three instructions:

shl $1, %rx
add $1, %rx
movl (%ra,%rx,4), %ra

ASM-6. Data structure assembly

Here are four assembly functions, f1 through f4.

f1:
        pushq   %rbp
        movq    %rsp, %rbp
        testl   %esi, %esi
        jle     LBB0_3
        incl    %esi
LBB0_2:
        movq    8(%rdi), %rdi
        decl    %esi
        cmpl    $1, %esi
        jg      LBB0_2
LBB0_3:
        movl    (%rdi), %eax
        popq    %rbp
        retq
f2:
        pushq   %rbp
        movq    %rsp, %rbp
        movslq  %esi, %rax
        movq    (%rdi,%rax,8), %rcx
        movl    (%rcx,%rax,4), %eax
        popq    %rbp
        retq
f3:
        testl   %esi, %esi
        jle     LBB2_3
        incl    %esi
LBB2_2:
        movl    %edx, %eax
        andl    $1, %eax
        movq    8(%rdi,%rax,8), %rdi
        sarl    %edx
        decl    %esi
        cmpl    $1, %esi
        jg      LBB2_2
LBB2_3:
        movl    (%rdi), %eax
        retq
f4:
        movslq  %esi, %rax
        movl    (%rdi,%rax,4), %eax
        retq

QUESTION ASM-6A. Each function returns a value loaded from some data structure. Which function uses which data structure?

  1. Array
  2. Array of pointers to arrays
  3. Linked list
  4. Binary tree

QUESTION ASM-6B. The array data structure is an array of type T. Considering the code for the function that manipulates the array, which of the following types are likely possibilities for T? Circle all that apply.

  1. char
  2. int
  3. unsigned long
  4. unsigned long long
  5. char*
  6. None of the above

ASM-7. Where’s Waldo?

In the following questions, we give you C code and a portion of the assembly generated by some compiler for that code. (Sometimes we blank out a part of the assembly.) The C code contains a variable, constant, or function called waldo, and a point in the assembly is marked with asterisks ***. Your job is to find Waldo: write an assembly expression or constant that holds the value of waldo at the marked point. We’ve done the first one for you.

NON-QUESTION: Where’s Waldo?

int identity(int waldo) {
    return waldo;
}
00000000004007f6 <identity>:
  4007f6:       55                      push   %rbp
  4007f7:       48 89 e5                mov    %rsp,%rbp
  4007fa:       89 7d fc                mov    %edi,-0x4(%rbp)
  4007fd:       8b 45 fc                mov    -0x4(%rbp),%eax
           ***
  400800:       5d                      pop    %rbp
  400801:       c3                      retq

ANSWER: %edi, -0x4(%rbp), %eax, and %rax all hold the value of waldo at the marked point, so any of them is a valid answer. If the asterisks came before the first instruction, only %edi would work.

QUESTION ASM-7A: Where’s Waldo?

int f1(int a, int b, int waldo, int d) {
    if (a > b) {
        return waldo;
    } else {
        return d;
    }
}
0000000000400802 <f1>:
           ***
  400802:       55                      push   %rbp
  400803:       48 89 e5                mov    %rsp,%rbp
  400806:       89 7d fc                mov    %edi,-0x4(%rbp)
  400809:       89 75 f8                mov    %esi,-0x8(%rbp)
  40080c:       89 55 f4                mov    %edx,-0xc(%rbp)
  40080f:       89 4d f0                mov    %ecx,-0x10(%rbp)
  400812:       8b 45 fc                mov    -0x4(%rbp),%eax
  400815:       3b 45 f8                cmp    -0x8(%rbp),%eax
  400818:       7e 05                   jle    40081f <f1+0x1d>
  40081a:       8b 45 f4                mov    -0xc(%rbp),%eax
  40081d:       eb 03                   jmp    400822 <f1+0x20>
  40081f:       8b 45 f0                mov    -0x10(%rbp),%eax
  400822:       5d                      pop    %rbp
  400823:       c3                      retq

QUESTION ASM-7B: Where’s Waldo?

int int_array_get(int* a, int waldo) {
    int x = a[waldo];
    return x;
}
00000000004007d9 <int_array_get>:
INSTRUCTIONS OMITTED 
          ***
 4007dc:       8b 04 b7                mov    (%rdi,%rsi,4),%eax
 4007df:       c3                      retq

QUESTION ASM-7C: Where’s Waldo?

int matrix_get(int** matrix, int row, int col) {
    int* waldo = matrix[row];
    return waldo[col];
}
00000000004007e0 <matrix_get>:
 4007e0:       48 63 f6                movslq %esi,%rsi
 4007e3:       48 63 d2                movslq %edx,%rdx
          ***
 4007e6:       ?? ?? ?? ??             mov    ??,%rax
 4007ea:       8b 04 90                mov    (%rax,%rdx,4),%eax
 4007ed:       c3                      retq

QUESTION ASM-7D: Where’s Waldo?

int f5(int x) {
    extern int waldo(int);
    return waldo(x * 45);
}
0000000000400be0 <f5>:
          ***
 400be0:       6b ff 2d                imul   $0x2d,%edi,%edi
 400be3:       eb eb                   jmp    400bd0

QUESTION ASM-7E: Where’s Waldo?

int factorial(int waldo) {
    if (waldo < 2) {
        return 1;
    } else {
        return waldo * factorial(waldo - 1);
    }
}
0000000000400910 <factorial>:
     400910:       83 ff 01                cmp    $0x1,%edi
     400913:       b8 01 00 00 00          mov    $0x1,%eax
     400918:       7e 13                   jle    .L2 <factorial+0x1b>
     40091a:       [6 bytes of padding (a no-op instruction)]
.L1:          ***
     400920:       0f af c7                imul   %edi,%eax
     400923:       83 ef 01                sub    $0x1,%edi
     400926:       83 ff 01                cmp    $0x1,%edi
     400929:       75 f5                   jne    .L1 <factorial+0x10>
.L2: 40092b:       f3 c3                   repz retq

QUESTION ASM-7F: Where’s Waldo?

⚠️ This question currently uses 32-bit assembly.

int binary_search(const char* needle, const char** haystack, unsigned sz) {
    unsigned waldo = 0, r = sz;
    while (waldo < r) {
        unsigned m = waldo + ((r - waldo) >> 1);
        if (strcmp(needle, haystack[m]) < 0) {
            r = m;
        } else if (strcmp(needle, haystack[m]) == 0) {
            waldo = r = m;
        } else {
            waldo = m + 1;
        }
    }
    return waldo;
}
80484ab <binary_search>:
     INSTRUCTIONS OMITTED
.L1: 80484c3:       89 fe                   mov    %edi,%esi
     80484c5:       29 de                   sub    %ebx,%esi
     80484c7:       d1 ee                   shr    %esi
     80484c9:       01 de                   add    %ebx,%esi
     80484cb:       8b 44 b5 00             mov    0x0(%ebp,%esi,4),%eax
     80484cf:       89 44 24 04             mov    %eax,0x4(%esp)
     80484d3:       8b 44 24 30             mov    0x30(%esp),%eax
     80484d7:       89 04 24                mov    %eax,(%esp)
     80484da:       e8 11 fe ff ff          call   80482f0 <strcmp@plt>
     80484df:       85 c0                   test   %eax,%eax
     80484e1:       78 09                   js     .L2 <binary_search+0x41>
     80484e3:       85 c0                   test   %eax,%eax
     80484e5:       74 13                   je     80484fa <binary_search+0x4f>
               ***
     80484e7:       8d 5e 01                lea    0x1(%esi),%ebx
     80484ea:       eb 02                   jmp    .L3 <binary_search+0x43>
.L2: 80484ec:       89 f7                   mov    %esi,%edi
.L3: 80484ee:       39 df                   cmp    %ebx,%edi
     80484f0:       77 d1                   ja     .L1 <binary_search+0x18>
     INSTRUCTIONS OMITTED

In the remaining questions, you are given assembly compiled from one of the above functions by a different compiler, or at a different optimization level. Your goal is to figure out what C code corresponds to the given assembly.

QUESTION ASM-7G:

⚠️ This question currently uses 32-bit assembly.

804851d <waldo>:
804851d:       55                      push   %ebp
804851e:       89 e5                   mov    %esp,%ebp
8048520:       83 ec 18                sub    $0x18,%esp
8048523:       83 7d 08 01             cmpl   $0x1,0x8(%ebp)
8048527:       7f 07                   jg     8048530
8048529:       b8 01 00 00 00          mov    $0x1,%eax
804852e:       eb 10                   jmp    8048540
8048530:       8b 45 08                mov    0x8(%ebp),%eax
8048533:       48                      dec    %eax
8048534:       89 04 24                mov    %eax,(%esp)
8048537:       e8 e1 ff ff ff          call   804851d
804853c:       0f af 45 08             imul   0x8(%ebp),%eax
8048540:       c9                      leave
8048541:       c3                      ret

What’s Waldo? Circle one.

  1. f1
  2. f5
  3. matrix_get
  4. permutation_compare
  5. factorial
  6. binary_search

QUESTION ASM-7H:

⚠️ This question currently uses 32-bit assembly.

8048425 <waldo>:
8048425:       55                      push   %ebp
8048426:       89 e5                   mov    %esp,%ebp
8048428:       8b 45 08                mov    0x8(%ebp),%eax
804842b:       3b 45 0c                cmp    0xc(%ebp),%eax
804842e:       7e 05                   jle    8048435 <waldo+0x10>
8048430:       8b 45 10                mov    0x10(%ebp),%eax
8048433:       eb 03                   jmp    8048438 <waldo+0x13>
8048435:       8b 45 14                mov    0x14(%ebp),%eax
8048438:       5d                      pop    %ebp
8048439:       c3                      ret

What’s Waldo? Circle one.

  1. f1
  2. f5
  3. matrix_get
  4. permutation_compare
  5. factorial
  6. binary_search

QUESTION ASM-7I:

00000000004008b4 <waldo>:
 4008b4:       55                      push   %rbp
 4008b5:       48 89 e5                mov    %rsp,%rbp
 4008b8:       48 83 ec 10             sub    $0x10,%rsp
 4008bc:       89 7d fc                mov    %edi,-0x4(%rbp)
 4008bf:       8b 45 fc                mov    -0x4(%rbp),%eax
 4008c2:       6b c0 2d                imul   $0x2d,%eax,%eax
 4008c5:       89 c7                   mov    %eax,%edi
 4008c7:       e8 9e 05 00 00          callq  400e6a
 4008cc:       c9                      leaveq 
 4008cd:       c3                      retq

What’s Waldo? Circle one.

  1. f1
  2. f5
  3. matrix_get
  4. permutation_compare
  5. factorial
  6. binary_search

ASM-8. (removed because redundant)

ASM-9. Disassembly II

The questions in this section concern a function called ensmallen, which has the following assembly.

ensmallen:
 1.          movzbl  (%rsi),  %edx
 2.          testb   %dl, %dl
 3.          movb    %dl, (%rdi)
 4.          jne     .L22
 5.          jmp     .L23
 6.  .L18:
 7.          addq    $1, %rsi
 8.  .L22:
 9.          movzbl  (%rsi), %eax
10.          cmpb    %dl, %al
11.          je      .L18
12.          addq    $1, %rdi
13.          testb   %al, %al
14.          movb    %al, (%rdi)
15.          je      .L23
16.          movl    %eax, %edx
17.          jmp     .L22
18.  .L23:
19.          retq

QUESTION ASM-9A. How many arguments is this function likely to take? Give line numbers that helped you determine an answer.

QUESTION ASM-9B. Are the argument(s) pointers? Give line numbers that helped you determine an answer.

QUESTION ASM-9C. What type(s) are the argument(s) likely to have? Give line numbers that helped you determine an answer.

QUESTION ASM-9D. Write a likely signature for the function. Use return type void.

QUESTION ASM-9E. Write an alternate likely signature for the function, different from your last answer. Again, use return type void.

QUESTION ASM-9F. Which callee-saved registers does this function use? Give line numbers that helped you determine an answer.

QUESTION ASM-9G. The function has an “input” and an “output”. Give an “input” that would cause the CPU to jump from line 5 to label .L23, and describe what is placed in the “output” for that “input”.

QUESTION ASM-9H. Give an “input” for which the corresponding “output” is not a copy of the “input”. Your answer must differ from the previous answer.

QUESTION ASM-9I. Write C code corresponding to this function. Make it as compact as you can.

ASM-10. Machine programming

Intel really messed up this time. They’ve released a processor, the Fartium Core Trio, where every instruction is broken except the ones on this list.
1. cmpq %rdi, %rsi
2. decq %rsi
3. incq %rax
4. je L1
5. jl L2
6. jmp L3
7. movl (%rdi,%rax,4), %edi
8. retq
9. xchgq %rax, %rcx
10. xorq %rax, %rax

(In case you forgot, xchgq swaps two values—here, the values in two registers—without modifying condition codes.)

“So what if it’s buggy,” says Andy Grove; “it can still run programs.” For instance, he argues convincingly that this function:

void do_nothing() {
}

is implemented correctly by this Fartium instruction sequence:

retq

Your job is to implement more complex functions using only Fartium instructions. Your implementations must have the same semantics as the C functions, but may perform much worse than one might expect. You may leave off arguments and write instruction numbers (#1–10) or instruction names. Indicate where labels L1–L3 point (if you need them). Assume that the Fartium Core Trio uses the normal x86-64 calling convention.

QUESTION ASM-10A.

int return_zero() {
    return 0;
}

QUESTION ASM-10B.

int identity(int a) {
    return a;
}

QUESTION ASM-10C.

void infinite_loop() {
    while (1) {
        /* do nothing */
    }
}

QUESTION ASM-10D.

struct point {
    int x;
    int y;
    int z;
};

int extract_z(point* p) {
    return p->z;
}

So much for the easy ones. Now complete one out of the following parts, or more than one for extra credit.

QUESTION ASM-10E.

long add(long a, long b) {
    return a + b;
}

QUESTION ASM-10F.

int array_dereference(int* a, long i) {
    return a[i];
}

ASM-11. Program Layout

For the following questions, select the part(s) of memory from the list below that best describes where you will find the object.

  1. heap
  2. stack
  3. between the heap and the stack
  4. in a read-only data segment
  5. in a text segment starting at address 0x08048000
  6. in a read/write data segment
  7. in a register

Assume the following code, compiled without optimization.

#include <errno.h>
#include <getopt.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

// The following is copied from stdio.h for your reference
#define EOF (-1)

 1.    unsigned long fib(unsigned long n) {
 2.        if (n < 2) {
 3.            return n;
 4.        }
 5.        return fib(n - 1) + fib(n - 2);
 6.    }
 7.
 8.    int main(int argc, char *argv[]) {
 9.        extern int optind;
10.        char ch;
11.        unsigned long f, n;
12.
13.        // Command line processing
14.        while ((ch = getopt(argc, argv, "h")) != EOF) {
15.            switch (ch) {
16.            case 'h':
17.            case '?':
18.            default:
19.                return (usage());
20.            }
21.        }
22.
23.        argc -= optind;
24.        argv += optind;
25.
26.        if (argc != 1) {
27.            return usage();
28.        }
29.
30.        n = strtoul(strdup(argv[0]), nullptr, 10);
31.        if (n == 0 && errno == EINVAL) {
32.            return usage();
33.        }
34.
35.        /* Now call one of the fib routines. */
36.        f = fib(n);
37.        printf("fib(%lu) = %lu\n", n, f);
38.
39.        return 0;
40.    }

QUESTION ASM-11A. The string "fib(%lu) = %lu\n" (line 37).

QUESTION ASM-11B. optind (line 23).

QUESTION ASM-11C. When executing at line 5, where you will find the address to which fib returns.

QUESTION ASM-11D. Where will you find the value of EOF that is compared to the return value of getopt in line 14.

QUESTION ASM-11E. getopt (line 14)

QUESTION ASM-11F. fib (lines 1-6)

QUESTION ASM-11G. the variable f (line 36)

QUESTION ASM-11H. the string being passed to strtoul (line 30)

QUESTION ASM-11I. strdup (line 30)

QUESTION ASM-11J. The value of the fib function when we return from fib (line 5).

ASM-12. Assembly and Data Structures

Consider the following assembly function.

func:
        xorl    %eax, %eax
        cmpb    $0, (%rdi)
        je      .L27
.L26:
        addq    $1, %rdi
        addl    $1, %eax
        cmpb    $0, (%rdi)
        jne     .L26
.L27:
        retq

QUESTION ASM-12A. How many parameters does this function appear to have?

QUESTION ASM-12B. What do you suppose the type of that parameter is?

QUESTION ASM-12C. Write C++ code that corresponds to it.

ASM-13. Assembly language

Consider the following four assembly functions.

# Code Sample 1
       movq    %rdi, %rax
       testq   %rdx, %rdx
       je      .L2
       addq    %rdi, %rdx
       movq    %rdi, %rcx
.L3:
       addq    $1, %rcx
       movb    %sil, -1(%rcx)
       cmpq    %rdx, %rcx
       jne     .L3
.L2:
       rep ret
# Code Sample 2
       movq    %rdi, %rax
       testq   %rdx, %rdx
       je      .L2
       addq    %rdi, %rdx
       movq    %rdi, %rcx
.L3:
       addq    $1, %rcx
       addq    $1, %rsi
       movzbl  -1(%rsi), %r8d
       movb    %r8b, -1(%rcx)
       cmpq    %rdx, %rcx
       jne     .L3
.L2:
       rep ret
# Code Sample 3
      movb    (%rsi), %al
      testb   %al, %al
      je      .L3
      incq    %rsi
.L2:
      movb    %al, (%rdi)
      incq    %rdi
      movb    (%rsi), %al
      incq    %rsi
      testb   %al, %al
      jne     .L2
.L3:
      movq    %rdi, %rax
      ret
# Code Sample 4
       testq   %rdx, %rdx
       je      .L3
       movq    %rdi, %rax
.L2:
       movb    %sil, (%rax)
       incq    %rax
       decq    %rdx
       jne     .L2
.L3:
       movq    %rdi, %rax
       ret

(Note: The %sil register is the lowest-order byte of register %rsi, just as %al is the lowest-order byte of %rax and %r8b is the lowest-order byte of %r8.)

QUESTION ASM-13A. Which two of the assembly functions perform the exact same task?

QUESTION ASM-13B. What is that task? You can describe it briefly, or give the name of the corresponding C library function.

QUESTION ASM-13C. Explain how the other two functions differ from each other.

ASM-14. Golden Baron

A very rich person has designed a new x86-64-based computer, the Golden Baron Supercomputer 9000, and is paying you handsomely to write a C compiler for it. There’s just one problem. This person, like many very rich people, is dumb, and on their computer, odd-numbered memory addresses don’t work for data. When data is loaded into a general-purpose register from an odd-numbered address, the value read is zero. For example, consider the following instructions:

movl $0x01020304, a(%rip)
movl a(%rip), %eax

(where the address of a is even). Executed on true x86-64, %rax will hold the value 0x01020304; on Golden Baron, %rax will hold 0x00020004.

But it is still possible to write a correct C compiler for this ungodly hardware—you just have to work around the bad memory with code. You plan to use two bytes of Golden Baron memory for every one byte of normal x86-64 memory. For instance, an array int a[2] = {1, 0x0a0b0c0d}; would be stored in 16 bytes of memory, like so:

01 00 00 00 00 00 00 00 0d 00 0c 00 0b 00 0a 00

Pointer arithmetic, and moving multi-byte values to and from registers, must account for the zero bytes that alternate with meaningful bytes. So to read the correct value for a[2], the compiler must arrange to read the bytes at addresses A+8, A+10, A+12, and A+14, where A is the address of the first byte in a.

QUESTION ASM-14A. What should printf("%zu\n", sizeof(char)) print on Golden Baron?

QUESTION ASM-14B. This function

int f(signed char* c, size_t i) {
    return c[i];
}

can compile to two instructions on x86-64, including retq. It can also compile to two instructions on Golden Baron. (We’re assuming that memory used for Golden Baron instructions works normally.) What are those instructions?

QUESTION ASM-14C. This function

int g(int* a, size_t i) {
    return a[i];
}

can compile to two instructions on x86-64, but Golden Baron requires more work. Write the Golden Baron translation of this function in x86-64 assembly language. For partial credit, write C code that, executed on x86-64, would return the correct value from a Golden Baron-formatted array.

QUESTION ASM-14D. The Golden Baron’s x86-64 processor actually supports a secret instruction, swizzleq SRC, REG, which rearranges the nybbles (the hexadecimal digits—the aligned 4-bit slices) of the destination register REG based on the source argument SRC. Here’s some examples. Assuming that %rax holds the value 0x0123456789ABCDEF, the following swizzleq instructions leave the indicated results in %rax:

Use swizzleq to shorten your answer for Part C.

ASM-15. Instruction behavior

QUESTION ASM-15A. Name three different x86-64 instructions that always modify the stack pointer, no matter their arguments (instruction names only; suffixes don’t count, so movl and movq are the same instruction name).

QUESTION ASM-15B. Name three different x86-64 instructions that sometimes modify the stack pointer, depending on their arguments.

QUESTION ASM-15C. Name three different x86-64 instructions that never modify the stack pointer, no matter their arguments.

QUESTION ASM-15D. List three different instructions, including arguments, that if placed immediately before a retq instruction that ends a function, will never change the function’s behavior. The instructions should have different names. No funny business: assume the function was compiled from valid C, that relative jumps are fixed up, and that, for example, it doesn’t access its own code.

ASM-16. Calling convention

The following questions concern valid C++ functions compiled using the normal x86-64 calling convention. True or false?

QUESTION ASM-16A. If the function’s instructions do not save and restore any registers, then the C++ function did not call any other function.

QUESTION ASM-16B. If the function’s instructions do not change the stack pointer, then the function’s instructions do not contain a call instruction.

QUESTION ASM-16C. If the function’s instructions do not change the stack pointer, then the C++ function did not call any other function. Explain your answer briefly.

QUESTION ASM-16D. If the function’s instructions do not modify the %rax register, then the C++ function must return void.

QUESTION ASM-16E. If the function’s instructions store a local variable on the stack, then that variable’s address will be less than the function’s initial stack pointer.

ASM-17. Assembly

Here are three x86-64 assembly functions that were compiled from C.

f1:
    xorl    %eax, %eax
L2:
    movsbq  (%rdi), %rdx
    subq    $48, %rdx
    cmpq    $9, %rdx
    ja      L5
    imulq   $10, %rax, %rax
    incq    %rdi
    addq    %rdx, %rax
    jmp     L2
L5:
    ret
f2:
    movq    %rdi, %rax
L7:
    cmpb    $0, (%rax)
    je      L9
    incq    %rax
    jmp     L7
L9:
    cmpq    %rax, %rdi
    jnb     L11
    decq    %rax
    movb    (%rdi), %cl
    incq    %rdi
    movb    (%rax), %dl
    movb    %cl, (%rax)
    movb    %dl, -1(%rdi)
    jmp     L9
L11:
    ret
f3:
    xorl    %eax, %eax
L13:
    cmpq    %rax, %rdx
    je      L15
    movb    (%rdi,%rax), %cl
    movb    (%rsi,%rax), %r8b
    movb    %r8b, (%rdi,%rax)
    movb    %cl, (%rsi,%rax)
    incq    %rax
    jmp     L13
L15:
    ret

(Note: imulq $10, %rax, %rax means %rax *= 10.)

QUESTION ASM-17A. How many arguments does each function most likely take?

QUESTION ASM-17B. Which functions modify at least one caller-saved register? List all that apply or write “none”.

QUESTION ASM-17C. Which functions never modify memory? List all that apply or write “none”.

QUESTION ASM-17D. Write a signature for each function, giving a likely type for each argument and a likely return type. (You may give a void return type if you think the function doesn’t return a useful value.)

_______ f1(___________________________________)


_______ f2(___________________________________)


_______ f3(___________________________________)

QUESTION ASM-17E. One of these functions swaps the contents of two memory regions. Which one?

QUESTION ASM-17F. What is the value of %rax in f2 the first time L9 is reached? Write a C expression in terms of f2’s argument or arguments; you may use standard library functions.

QUESTION ASM-17G. Give arguments for each function that would result in the function returning without writing to memory or causing a fault.

f1(_____________________)


f2(_____________________)


f3(_____________________)

QUESTION ASM-17H. Complete this function so that it returns the number

  1. For full credit, use only calls to f1, f2, and f3. For partial credit, do something simpler.
int magic() {
    char s1[] = "Shaka kaSenzangakhona became King of the Zulu Kingdom in 1816";
    char s2[] = "Dingane kaSenzangakhona succeeded Shaka in 1828";
    char s3[] = "1661 in the Gregorian calendar is 3994 in the Korean calendar";




}

IO-1. I/O caching

Mary Ruefle, a poet who lives in Vermont, is working on her caching I/O library for CS 61. She wants to implement a cache with N slots. Since searching those slots might slow down her library, she writes a function that maps addresses to slots. Here’s some of her code.

#define SLOTSIZ 4096
struct io61_slot {
    char buf[SLOTSIZ];
    off_t pos; // = (off_t) -1 for empty slots
    ssize_t sz;
};

#define NSLOTS 64
struct io61_file {
    int fd;
    off_t pos; // current file position
    io61_slot slots[NSLOTS];
};

static inline int find_slot(off_t off) {
    return off % NSLOTS;
}

int io61_readc(io61_file* f) {
    int slotindex = find_slot(f->pos);
    io61_slot* s = &f->slots[slotindex];

    if (f->pos < s->pos || f->pos >= s->pos + s->sz) {
        // slot contains wrong data, need to refill it
        off_t new_pos = lseek(f->fd, f->pos, SEEK_SET);
        assert(new_pos != (off_t) -1); // only handle seekable files for now
        ssize_t r = read(f->fd, s->buf, SLOTSIZ);
        if (r == -1 || r == 0) {
            return EOF;
        }
        s->pos = f->pos;
        s->sz = r;
    }

    int ch = (unsigned char) s->buf[f->pos - s->pos];
    ++f->pos;
    return ch;
}

Before she can run and debug this code, Mary is led “to an emergency of feeling that … results in a poem.” She’ll return to CS61 and fix her implementation soon, but in the meantime, let’s answer some questions about it.

QUESTION IO-1A. True or false: Mary’s cache is a direct-mapped cache.

QUESTION IO-1B. What changes to Mary’s code could change your answer to Part A? Circle all that apply.

  1. New code for find_slot (keeping io61_readc the same)
  2. New code in io61_readc (keeping find_slot the same)
  3. New code in io61_readc and new code for find_slot
  4. None of the above

QUESTION IO-1C. Which problems would occur when Mary’s code was used to sequentially read a seekable file of size 2MiB (2×220 = 2097152 bytes) one character at a time? Circle all that apply.

  1. Excessive CPU usage (>10x stdio)
  2. Many system calls to read data (>10x stdio)
  3. Incorrect data (byte x read at a position where the file has byte y≠x)
  4. Read too much data (more bytes read than file contains)
  5. Read too little data (fewer bytes read than file contains)
  6. Crash/undefined behavior
  7. None of the above

QUESTION IO-1D. Which of these new implementations for find_slot would fix at least one of these problems with reading sequential files? Circle all that apply.

  1. return (off * 2654435761) % NSLOTS; /* integer hash function from Stack Overflow */
  2. return (off / SLOTSIZ) % NSLOTS;
  3. return off & (NSLOTS - 1);
  4. return 0;
  5. return (off >> 12) & 0x3F;
  6. None of the above

IO-2. Caches and reference strings

QUESTION IO-2A. True or false: A direct-mapped cache with N or more slots can handle any reference string containing ≤N distinct addresses with no misses except for cold misses.

QUESTION IO-2B. True or false: A fully-associative cache with N or more slots can handle any reference string containing ≤N distinct addresses with no misses except for cold misses.

Consider the following 5 reference strings.

Name String
α 1
β 1, 2
γ 1, 2, 3, 4, 5
δ 2, 4
ε 5, 2, 4, 2

QUESTION IO-2C. Which of the strings might indicate a sequential access pattern? Circle all that apply.

α

β

γ

δ

ε

None of these

QUESTION IO-2D. Which of the strings might indicate a strided access pattern with stride >1? Circle all that apply.

α

β

γ

δ

ε

None of these

The remaining questions concern concatenated permutations of these five strings. For example, the permutation αβγδε refers to this reference string:

1, 1, 2, 1, 2, 3, 4, 5, 2, 4, 5, 2, 4, 2.

We pass such permutations through an initially-empty, fully-associative cache with 3 slots, and observe the numbers of hits.

QUESTION IO-2E. How many cold misses might a permutation observe? Circle all that apply.

0

1

2

3

4

5

Some other number

Under LRU eviction, the permutation αβεγδ observes 5 hits as follows. (We annotate each access with “h” for hit or “m” for miss.)

1m; 1h, 2m; 5m, 2h, 4m, 2h; 1m, 2h, 3m, 4m, 5m; 2m, 4h.

QUESTION IO-2F. How many hits does this permutation observe under FIFO eviction?

QUESTION IO-2G. Give a permutation that will observe 8 hits under LRU eviction, which is the maximum for any permutation. There are several possible answers. (Write your answer as a permutation of αβγδε. For partial credit, find a permutation that has 7 hits, etc.)

QUESTION IO-2H. Give a permutation that will observe 2 hits under LRU eviction, which is the minimum for any permutation. There is one unique answer. (Write your answer as a permutation of αβγδε. For partial credit, find a permutation that has 3 hits, etc.)

IO-3. Processor cache

The git version control system is based on commit hashes, which are 160-bit (20-byte) hash values used to identify commits. In this problem you’ll consider the processor cache behavior of several versions of a “grading server” that maps commits to grades. Here’s the first version:

struct commit_info {
    char hash[20];
    int grade[11];
};

commit_info* commits;
size_t N;

int get_grade1(const char* hash, int pset) {
    for (size_t i = 0; i != N; ++i) {
        if (memcmp(commits[i].hash, hash, 20) == 0) {
            return commits[i].grade[pset];
        }
    }
    return -1;
}

We will ask questions about the average number of cache lines accessed by variants of get_grade(hash, pset). You should make the following assumptions:

QUESTION IO-3A. What is the expected number of cache lines accessed by get_grade1, in terms of N?

The second version:

struct commit_info {
   char hash[20];
   int grade[11];
};

commit_info** commits;
size_t N;

int get_grade2(const char hash[20], int pset) {
    for (size_t i = 0; i != N; ++i) {
        if (memcmp(commits[i]->hash, hash, 20) == 0) {
            return commits[i]->grade[pset];
        }
    }
    return -1;
}

QUESTION IO-3B. What is the expected number of cache lines accessed by get_grade2, in terms of N?

The third version:

struct commit_info {
    char hash[20];
    int grade[11];
};

struct commit_hint {
    char hint[8];
    commit_info* commit;
};

commit_hint* commits;
size_t N;

int get_grade3(const char* hash, int pset) {
    for (size_t i = 0; i != N; ++i) {
        if (memcmp(commits[i].hint, hash, 8) == 0
            && memcmp(commits[i].commit->hash, hash, 20) == 0) {
            return commits[i].commit->grade[pset];
        }
    }
    return -1;
}

QUESTION IO-3C. What is the expected number of cache lines accessed by get_grade3, in terms of N? (You may assume that N≤2000.)

The fourth version is a hash table.

struct commit_info {
    char hash[20];
    int grade[11];
};

commit_info** commits;
size_t commits_hashsize;

int get_grade4(const char* hash, int pset) {
    // choose initial bucket
    size_t bucket;
    memcpy(&bucket, hash, sizeof(bucket));
    bucket = bucket % commits_hashsize;
    // search for the commit starting from that bucket
    while (commits[bucket] != nullptr) {
        if (memcmp(commits[bucket]->hash, hash, 20) == 0) {
            return commits[bucket]->grade[pset];
        }
        bucket = (bucket + 1) % commits_hashsize;
    }
    return -1;
}

QUESTION IO-3D. Assume that a call to get_grade4 encounters C expected hash collisions (i.e., examines C buckets before finding the bucket that actually contains hash). What is the expected number of cache lines accessed by get_grade4, in terms of N and C?

IO-4. IO caching and strace

Elif Batuman is investigating several program executables left behind by her ex-roommate Fyodor. She runs each executable under strace in the following way:

strace -o strace.txt ./EXECUTABLE files/text1meg.txt > files/out.txt

Help her figure out properties of these programs based on their system call traces.

QUESTION IO-4A. Program ./mysterya:

open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x8193000
brk(0x81b5000)                          = 0x81b5000
read(3, "A", 1)                         = 1
write(1, "A", 1)                        = 1
read(3, "\n", 1)                        = 1
write(1, "\n", 1)                       = 1
read(3, "A", 1)                         = 1
write(1, "A", 1)                        = 1
read(3, "'", 1)                         = 1
write(1, "'", 1)                        = 1
read(3, "s", 1)                         = 1
write(1, "s", 1)                        = 1
...

Circle at least one option in each column.

  1. Sequential IO
  2. Reverse sequential IO
  3. Strided IO
  1. No read cache
  2. Unaligned read cache
  3. Aligned read cache
  1. No write cache
  2. Write cache
  1. Cache size 4096
  2. Cache size 2048
  3. Cache size 1024
  4. Other

QUESTION IO-4B. Program ./mysteryb:

open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x96c5000
brk(0x96e6000)                          = 0x96e6000
read(3, "A\nA's\nAA's\nAB's\nABM's\nAC's\nACTH'"..., 2048) = 2048
write(1, "A\nA's\nAA's\nAB's\nABM's\nAC's\nACTH'"..., 2048) = 2048
read(3, "kad\nAkron\nAkron's\nAl\nAl's\nAla\nAl"..., 2048) = 2048
write(1, "kad\nAkron\nAkron's\nAl\nAl's\nAla\nAl"..., 2048) = 2048
...

Circle at least one option in each column.

  1. Sequential IO
  2. Reverse sequential IO
  3. Strided IO
  1. No read cache
  2. Unaligned read cache
  3. Aligned read cache
  1. No write cache
  2. Write cache
  1. Cache size 4096
  2. Cache size 2048
  3. Cache size 1024
  4. Other

QUESTION IO-4C. Program ./mysteryc:

open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x9064000
brk(0x9085000)                          = 0x9085000
fstat64(3, {st_mode=S_IFREG|0664, st_size=1048576, ...}) = 0
lseek(3, 1046528, SEEK_SET)             = 1046528
read(3, "ingau\nRheingau's\nRhenish\nRhianno"..., 2048) = 2048
write(1, "oR\ntlevesooR\ns'yenooR\nyenooR\ns't"..., 2048) = 2048
lseek(3, 1044480, SEEK_SET)             = 1044480
read(3, "Quinton\nQuinton's\nQuirinal\nQuisl"..., 2048) = 2048
write(1, "ehR\neehR\naehR\ns'hR\nhR\nsdlonyeR\ns"..., 2048) = 2048
lseek(3, 1042432, SEEK_SET)             = 1042432
read(3, "emyslid's\nPrensa\nPrensa's\nPrenti"..., 2048) = 2048
write(1, "\ns'nailitniuQ\nnailitniuQ\nnniuQ\ns"..., 2048) = 2048
lseek(3, 1040384, SEEK_SET)             = 1040384
read(3, "Pindar's\nPinkerton\nPinocchio\nPin"..., 2048) = 2048
write(1, "rP\ndilsymerP\ns'regnimerP\nregnime"..., 2048) = 2048
...

Circle at least one option in each column.

  1. Sequential IO
  2. Reverse sequential IO
  3. Strided IO
  1. No read cache
  2. Unaligned read cache
  3. Aligned read cache
  1. No write cache
  2. Write cache
  1. Cache size 4096
  2. Cache size 2048
  3. Cache size 1024
  4. Other

QUESTION IO-4D. Program ./mysteryd:

open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x9a0e000
brk(0x9a2f000)                          = 0x9a2f000
fstat64(3, {st_mode=S_IFREG|0664, st_size=1048576, ...}) = 0
lseek(3, 1048575, SEEK_SET)             = 1048575
read(3, "o", 2048)                      = 1
lseek(3, 1048574, SEEK_SET)             = 1048574
read(3, "Ro", 2048)                     = 2
lseek(3, 1048573, SEEK_SET)             = 1048573
read(3, "\nRo", 2048)                   = 3
...
lseek(3, 1046528, SEEK_SET)             = 1046528
read(3, "ingau\nRheingau's\nRhenish\nRhianno"..., 2048) = 2048
write(1, "oR\ntlevesooR\ns'yenooR\nyenooR\ns't"..., 2048) = 2048
lseek(3, 1046527, SEEK_SET)             = 1046527
read(3, "eingau\nRheingau's\nRhenish\nRhiann"..., 2048) = 2048
lseek(3, 1046526, SEEK_SET)             = 1046526
read(3, "heingau\nRheingau's\nRhenish\nRhian"..., 2048) = 2048
...

Circle at least one option in each column.

  1. Sequential IO
  2. Reverse sequential IO
  3. Strided IO
  1. No read cache
  2. Unaligned read cache
  3. Aligned read cache
  1. No write cache
  2. Write cache
  1. Cache size 4096
  2. Cache size 2048
  3. Cache size 1024
  4. Other

QUESTION IO-4E. Program ./mysterye:

open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x93e5000
brk(0x9407000)                          = 0x9407000
read(3, "A", 1)                         = 1
read(3, "\n", 1)                        = 1
read(3, "A", 1)                         = 1
...
read(3, "A", 1)                         = 1
read(3, "l", 1)                         = 1
write(1, "A\nA's\nAA's\nAB's\nABM's\nAC's\nACTH'"..., 1024) = 1024
read(3, "t", 1)                         = 1
read(3, "o", 1)                         = 1
read(3, "n", 1)                         = 1
...

Circle at least one option in each column.

  1. Sequential IO
  2. Reverse sequential IO
  3. Strided IO
  1. No read cache
  2. Unaligned read cache
  3. Aligned read cache
  1. No write cache
  2. Write cache
  1. Cache size 4096
  2. Cache size 2048
  3. Cache size 1024
  4. Other

QUESTION IO-4F. Program ./mysteryf:

open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x9281000
brk(0x92a3000)                          = 0x92a3000
read(3, "A\nA's\nAA's\nAB's\nABM's\nAC's\nACTH'"..., 4096) = 4096
write(1, "A", 1)                        = 1
write(1, "\n", 1)                       = 1
write(1, "A", 1)                        = 1
...
write(1, "A", 1)                        = 1
write(1, "l", 1)                        = 1
read(3, "ton's\nAludra\nAludra's\nAlva\nAlvar"..., 4096) = 4096
write(1, "t", 1)                        = 1
write(1, "o", 1)                        = 1
write(1, "n", 1)                        = 1
...

Circle at least one option in each column.

  1. Sequential IO
  2. Reverse sequential IO
  3. Strided IO
  1. No read cache
  2. Unaligned read cache
  3. Aligned read cache
  1. No write cache
  2. Write cache
  1. Cache size 4096
  2. Cache size 2048
  3. Cache size 1024
  4. Other

IO-5. Processor cache

The following questions use the following C definition for an NxM matrix (the matrix has N rows and M columns).

struct matrix {
    unsigned N;
    unsigned M;
    double elt[0];
};

matrix* matrix_create(unsigned N, unsigned M) {
    matrix* m = (matrix*) malloc(sizeof(matrix) + N * M * sizeof(double));
    m->N = N;
    m->M = M;
    for (size_t i = 0; i < N * M; ++i) {
        m->elt[i] = 0.0;
    }
    return m;
}

Typically, matrix data is stored in row-major order: element mij (at row i and column j) is stored in m->elt[i*m->M + j]. We might write this in C using an inline function:

inline double* melt1(matrix* m, unsigned i, unsigned j) {
    return &m->elt[i * m->M + j];
}

But that’s not the only possible method to store matrix data. Here are several more.

inline double* melt2(matrix* m, unsigned i, unsigned j) {
    return &m->elt[i + j * m->N];
}

inline double* melt3(matrix* m, unsigned i, unsigned j) {
    return &m->elt[i + ((m->N - i + j) % m->M) * m->N];
}

inline double* melt4(matrix* m, unsigned i, unsigned j) {
    return &m->elt[i + ((i + j) % m->M) * m->N];
}

inline double* melt5(matrix* m, unsigned i, unsigned j) {
    assert(m->M % 8 == 0);
    unsigned k = (i/8) * (m->M/8) + (j/8);
    return &m->elt[k*64 + (i % 8) * 8 + j % 8];
}

QUESTION IO-5A. Which method (of melt1–melt5) will have the best processor cache behavior if most matrix accesses use loops like this?

for (unsigned j = 0; j < 100; ++j) {
    for (unsigned i = 0; i < 100; ++i) {
        f(*melt(m, i, j));
    }
}

QUESTION IO-5B. Which method will have the best processor cache behavior if most matrix accesses use loops like this?

for (unsigned i = 0; i < 100; ++i) {
    f(*melt(m, i, i));
}

QUESTION IO-5C. Which method will have the best processor cache behavior if most matrix accesses use loops like this?

for (unsigned i = 0; i < 100; ++i) {
    for (unsigned j = 0; j < 100; ++j) {
        f(*melt(m, i, j));
    }
}

QUESTION IO-5D. Which method will have the best processor cache behavior if most matrix accesses use loops like this?

for (int di = -3; di <= 3; ++di) {
    for (int dj = -3; dj <= 3; ++dj) {
        f(*melt(m, I + di, J + dj));
    }
}

QUESTION IO-5E. Here is a matrix-multiply function in ikj order.

matrix* matrix_multiply(matrix* a, matrix* b) {
    assert(a->M == b->N);
    matrix* c = matrix_create(a->N, b->M);
    for (unsigned i = 0; i != a->N; ++i) {
        for (unsigned k = 0; k != a->M; ++k) {
            for (unsigned j = 0; j != b->M; ++j) {
                *melt(c, i, j) += *melt(a, i, k) * *melt(b, k, j);
            }
        }
    }
}

This loop order is cache-optimal when data is stored in melt1 order. What loop order is cache-optimal for melt2?

QUESTION IO-5F. You notice that accessing a matrix element using melt1 is very slow. After some debugging, it seems like the processor on which you are running code has a very slow multiply instruction. Briefly describe a change to struct matrix that would let you write a version of melt1 with no multiply instruction. You may add members, change sizes, or anything you like.

IO-6. Caching

Assume that we have a cache that holds four slots. Assume that each letter below indicates an access to a block. Answer the following questions as they pertain to the following sequence of accesses.

E D C B A E D A A A B C D E

QUESTION IO-6A. What is the hit rate assuming an LRU replacement policy?

QUESTION IO-6B. What pages will you have in the cache at the end of the run?

QUESTION IO-6C. What is the best possible hit rate attainable if you could see into the future?

IO-7. Caching

Intel and CrossPoint have announced a new persistent memory technology with performance approaching that of DRAM. Your job is to calculate some performance metrics to help system architectects decide how to best incorporate this new technology into their platform.

Let's say that it takes 64ns to access one (32-bit) word of main memory (DRAM) and 256ns to access one (32-bit) word of this new persistent memory, which we'll call NVM (non-volatile memory). The block size of the NVM is 256 bytes. The NVM designers are quite smart and although it takes a long time to access the first byte, when you are accessing NVM sequentially, the devices perform read ahead and stream data efficiently -- at 32 GB/second, which is identical to the bandwidth of DRAM.

QUESTION IO-7A. Let's say that we are performing random accesses of 32 bits (on a 32-bit processor). What fraction of the accesses must be to main memory (as opposed to NVM) to achieve performance within 10% of DRAM?

QUESTION IO-7B. Let's say that they write every byte of a 256 block in units of 32 bits. How much faster will write-back cache perform relative to a write-through cache? (An approximate order of magnitude will be sufficient; showing work can earn partial credit.)

QUESTION IO-7C. Why might you not want to use a write-back cache?

IO-8. Reference strings

The following questions concern the FIFO (First In First Out), LRU (Least Recently Used), and LFU (Least Frequently Used) cache eviction policies.

Your answers should refer to seven-item reference strings made up of digits in the range 0–9. An example answer might be “1231231”. In each case, the reference string is processed by a 3-slot cache that’s initially empty.

QUESTION IO-8A. Give a reference string that has a 1/7 hit rate in all three policies.

QUESTION IO-8B. Give a reference string that has a 6/7 hit rate in all three policies.

QUESTION IO-8C. Give a reference string that has different hit rates under LRU and LFU policies, and compute the hit rates.

String:

LRU hit rate:

LFU hit rate:

QUESTION IO-8D. Give a reference string that has different hit rates under FIFO and LRU policies, and compute the hit rates.

String:

FIFO hit rate:

LRU hit rate:

QUESTION IO-8E. Now let's assume that you know a reference string in advance. Given a 3-slot cache and the following reference string, what caching algorithm discussed in class and/or exercises would produce the best hit rate, and would would that hit rate be?

“12341425321521”

IO-9. Caching: Access times and hit rates

Recall that x86-64 instructions can access memory in units of 1, 2, 4, or 8 bytes at a time. Assume we are running on an x86-64-like machine with 1024-byte cache lines. Our machine takes 32ns to access a unit if the cache hits, regardless of unit size. If the cache misses, an additional 8160ns are required to load the cache, for a total of 8192ns.

QUESTION IO-9A. What is the average access time per access to access all the data in a cache line as an array of 256 integers, starting from an empty cache?

QUESTION IO-9B. What unit size (1, 2, 4, or 8) minimizes the access time to access all data in a cache line, starting from an empty cache?

QUESTION IO-9C. What unit size (1, 2, 4, or 8) maximizes the hit rate to access all data in a cache line, starting from an empty cache?

IO-10. Single-slot cache code

Donald Duck is working on a single-slot cache for reading. He’s using the pos_tag/end_tag representation, which is:

struct io61_file {
   int fd;
   unsigned char cbuf[BUFSIZ];
   off_t tag;      // file offset of first character in cache (same as before)
   off_t end_tag;  // file offset one past last valid char in cache; end_tag - tag == old `csz`
   off_t pos_tag;  // file offset of next char to read in cache; pos_tag - tag == old `cpos`
};

Here’s our solution code; in case you want to scribble, the code is copied in the appendix.

 1.  ssize_t io61_read(io61_file* f, char* buf, size_t sz) {
 2.      size_t pos = 0;
 3.      while (pos != sz) {
 4.          if (f->pos_tag < f->end_tag) {
 5.              ssize_t n = sz - pos;
 6.              if (n > f->end_tag - f->pos_tag)
 7.                  n = f->end_tag - f->pos_tag;
 8.              memcpy(&buf[pos], &f->cbuf[f->pos_tag - f->tag], n);
 9.              f->pos_tag += n;
10.              pos += n;
11.          } else {
12.              f->tag = f->end_tag;
13.              ssize_t n = read(f->fd, f->cbuf, BUFSIZ);
14.              if (n > 0)
15.                  f->end_tag += n;
16.              else
17.                  return pos ? pos : n;
18.          }
19.      }
20.      return pos;
21.  }

Donald has ideas for “simplifying” this code. Specifically, he wants to try each of the following independently:

  1. Replacing line 4 with “if (f->pos_tag <= f->end_tag) {”.
  2. Removing lines 6–7.
  3. Removing line 9.
  4. Removing lines 16–17.

QUESTION IO-10A. Which simplifications could lead to undefined behavior? List all that apply or say “none.”

QUESTION IO-10B. Which simplifications could cause io61_read to loop forever without causing undefined behavior? List all that apply or say “none.”

QUESTION IO-10C. Which simplifications could lead to io61_read returning incorrect data in buf, meaning that the data read by a series of io61_read calls won’t equal the data in the file? List all that apply or say “none.”

QUESTION IO-10D. Chastened, Donald decides to optimize the code for a specific situation, namely when io61_read is called with a sz that is larger than BUFSIZ. He wants to add code after line 11, like so, so that fewer read system calls will happen for large sz:

11.          } else if (sz - pos > BUFSIZ) {
                 // DONALD’S CODE HERE




11A.         } else {
12.              f->tag = f->end_tag;
                 ....

Finish Donald’s code. Your code should maintain the relevant invariants between tag, pos_tag, end_tag, and the file position, but you need not keep tag aligned.

IO-11. Caching

QUESTION IO-11A. If it takes 200ns to access main memory, which of the following two caches will produce a lower average access time?

QUESTION IO-11B. Let’s say that you have a direct-mapped cache with four slots. A page with page number N must reside in the slot numbered N % 4. What is the best hit rate this could achieve given the following sequence of page accesses?

3 6 7 5 3 2 1 1 1 8

QUESTION IO-11C. What is the best hit rate a fully-associative four-slot cache could achieve for that sequence of page accesses? (A fully-associative cache may put any page in any slot. You may assume you know the full reference stream in advance.)

QUESTION IO-11D. What hit rate would the fully-associative four-slot cache achieve if it used the LRU eviction policy?

IO-12. I/O traces

QUESTION IO-12A. Which of the following programs cannot be distinguished by the output of the strace utility, not considering open calls? List all that apply; if multiple indistinguishable groups exist (e.g., A, B, & C can’t be distinguished, and D & E can’t be distinguished, but the groups can be distinguished from each other), list them all.

  1. Sequential byte writes using stdio
  2. Sequential byte writes using system calls
  3. Sequential byte writes using system calls and O_SYNC
  4. Sequential block writes using stdio and block size 2
  5. Sequential block writes using system calls and block size 2
  6. Sequential block writes using system calls and O_SYNC and block size 2
  7. Sequential block writes using stdio and block size 4096
  8. Sequential block writes using system calls and block size 4096
  9. Sequential block writes using system calls and O_SYNC and block size 4096

QUESTION IO-12B. Which of the programs in Part A cannot be distinguished using blktrace output? List all that apply.

QUESTION IO-12C. The buffer cache is coherent. Which of the following operating system changes could make the buffer cache incoherent? List all that apply.

  1. Application programs can obtain direct read access to the buffer cache
  2. Application programs can obtain direct write access to the disk, bypassing the buffer cache
  3. Other computers can communicate with the disk independently
  4. The computer has a uninterruptible power supply (UPS), ensuring that the operating system can write the contents of the buffer cache to disk if main power is lost

QUESTION IO-12D. The stdio cache is incoherent. Which of the operating system changes from Part C could make the stdio cache coherent? List all that apply.

IO-13. Reference strings and eviction

QUESTION IO-13A. When demonstrating cache eviction in class, we modeled a completely reactive cache, meaning that the cache performed at most one load from slow storage per access. Name a class of reference string that will have a 0% hit rate on any cold reactive cache. For partial credit, give several examples of such reference strings.

QUESTION IO-13B. What cache optimization can be used to improve the hit rate for the class of reference string in Part A? One word is enough; put the best choice.

QUESTION IO-13C. Give a single reference string with the following properties:

QUESTION IO-13D. Put the following eviction algorithms in order of how much space they require for per-slot metadata, starting with the least space and ending with the most space. (Assume the slot order is fixed, so once a block is loaded into slot i, it stays in slot i until it is evicted.) For partial credit say what you think the metadata would be.

  1. FIFO
  2. LRU
  3. Random

IO-14. Cache code

Several famous musicians have just started working on CS61 Problem Set

  1. They share the following code for their read-only, sequential, single-slot cache:
struct io61_file {
    int fd;
    unsigned char buf[4096];
    size_t pos;    // position of next character to read in `buf`
    size_t sz;     // number of valid characters in `buf`
};

int io61_readc(io61_file* f) {
    if (f->pos >= f->sz) {
        f->pos = f->sz = 0;
        ssize_t nr = read(f->fd, f->buf, sizeof(f->buf));
        if (nr <= 0) {
            f->sz = 0;
            return -1;
        } else {
            f->sz = nr;
        }
    }
    int ch = f->buf[f->pos];
    ++f->pos;
    return ch;
}

But they have different io61_read implementations. Donald (Lambert)’s is:

ssize_t io61_read(io61_file* f, char* buf, size_t sz) {
    return read(f->fd, buf, sz);
}

Solange (Knowles)’s is:

ssize_t io61_read(io61_file* f, char* buf, size_t sz) {
    for (size_t pos = 0; pos < sz; ++pos, ++buf) {
        *buf = io61_readc(f);
    }
    return sz;
}

Caroline (Shaw)’s is:

ssize_t io61_read(io61_file* f, char* buf, size_t sz) {
    if (f->pos >= f->sz) {
        return read(f->fd, buf, sz);
    } else {
        int ch = io61_readc(f);
        if (ch < 0) {
            return 0;
        }
        *buf = ch;
        return io61_read(f, buf + 1, sz - 1) + 1;
    }
}

You are testing each of these musicians’ codes by executing a sequence of io61_readc and/or io61_read calls on an input file and printing the resulting characters to standard output. There are no seeks, and your test programs print until end of file, so your tests’ output should equal the input file’s contents.

You should assume for these questions that no read system call ever returns -1.

QUESTION IO-14A. Describe an access pattern—that is, a sequence of io61_readc and/or io61_read calls (with lengths)—for which Donald’s code can return incorrect data.

QUESTION IO-14B. Which of these musicians’ codes can generate an output file with incorrect length?

For the remaining parts, assume the problem in Part B has been corrected, so that all musicians’ codes generate output files with correct lengths.

QUESTION IO-14C. Give an access pattern for which Solange’s code will return correct data and outperform Donald’s, or vice versa, and say whose code will win.

QUESTION IO-14D. Suggest a small change (≤10 characters) to Caroline’s code that would, most likely, make it perform at least as well as both Solange’s and Donald’s codes on all access patterns. Explain briefly.

IO-15. Caches

Parts A–C concern different implementations of Pset 3’s stdio cache. Assume a program that reads a 32768-byte file a character at a time, like this:

while (io61_readc(inf) != EOF) {
}

This program will call io61_readc 32769 times. (32769 = 215 + 1 = 8×212 + 1; the +1 accounts for the EOF return.) But the cache implementation might make many fewer system calls.

QUESTION IO-15A. How many read system calls are required assuming a single-slot, 4096-byte io61 cache?

QUESTION IO-15B. How many read system calls are required assuming an eight-slot, 4096-byte io61 cache?

QUESTION IO-15C. How many mmap system calls are required assuming an mmap-based io61 cache?

Parts D–F concern cache implementations and styles. We discussed many caches in class, including:

  1. The buffer cache
  2. The processor cache
  3. Single-slot aligned stdio caches
  4. Single-slot unaligned stdio caches
  5. Circular bounded buffers

QUESTION IO-15D. Which of those caches are implemented entirely in hardware? List all that apply.

QUESTION IO-15E. Which of those software caches could help speed up reverse sequential access to a disk file? List all that apply.

QUESTION IO-15F. Which of those software caches could help speed up access to a pipe or network socket? List all that apply.

MISC-1. Git

Edward Snowden is working on a CS61 problem set and he has some git questions.

QUESTION MISC-1A. The CS61 staff has released some new code. Which commands will help Edward get the code from code.seas.harvard.edu into his repository? Circle all that apply.

  1. git commit
  2. git add
  3. git push
  4. git pull

QUESTION MISC-1B. Edward has made some changes to his code. He hasn’t run git since making the changes. He wants to upload his latest version to code.seas.harvard.edu. Put the following git commands in an order that will accomplish this goal. You won’t necessarily use every command. You may add flags to a command (but you don’t have to). If you add flags, tell us what they are.

  1. git commit
  2. git add
  3. git push
  4. git pull

Edward Snowden’s partner, Edward Norton, has been working on the problem set also. They’ve been working independently.

At midnight on October 10, here’s how things stood. The git log for the partners’ shared code.seas.harvard.edu repository looked like this. The committer is listed in (parentheses).

52d44ee Pset release. (kohler)

The git log for Snowden’s local repository:

3246d07 Save Greenwald's phone number (snowden)
8633fbd Start work on a direct-mapped cache (snowden)
52d44ee Pset release. (kohler)

The git log for Norton’s local repository:

81f952e try mmap (norton)
52d44ee Pset release. (kohler)

At noon on October 11, their shared GitHub repository has this log:

d446e60 Increase cache size (snowden)
b677e85 use mmap on mmappable files (norton)
b46cfda Merge branch 'master' of code.seas.harvard.edu:~TheTrueHOOHA/cs61/TheTrueHOOHAs-cs61-psets.git 
        (norton)
81f952e try mmap (norton)
3246d07 Save Greenwald's phone number (snowden)
8633fbd Start work on a direct-mapped cache (snowden)
52d44ee Pset release. (kohler)

QUESTION MISC-1C. Give an order for these commands that could have produced that log starting from the midnight October 10 state. You might not use every command, and you might use some commands more than once. Sample (incorrect) answer: “1 4 4 5 2.”

  1. snowden: git commit -a
  2. snowden: git push
  3. snowden: git pull
  4. norton: git commit -a
  5. norton: git push
  6. norton: git pull

QUESTION MISC-1D. In your answer to Part C, circle the step(s) where there might have been a merge conflict.

MISC-2. Debugging

QUESTION MISC-2A. Match each tool or technique with a debugging situation for which it is well suited. Produce the best overall match that uses each situation exactly once.
1. strace A. Investigating segmentation faults
2. gdb B. Finding memory leaks
3. valgrind --tool=memcheck C. Checking your assumptions and verifying invariants
4. printf statements D. Discovering I/O patterns
5. assert E. Displaying program state

MISC-3. Pot Pourri

QUESTION MISC-3A. What does the following instruction place in %eax?

sarl $31, %eax

QUESTION MISC-3B. True/False: A direct-mapped cache with N slots can handle any reference string with < N distinct addresses with no misses except for compulsory misses.

QUESTION MISC-3C. What is 1 (binary) TB in hexadecimal?

QUESTION MISC-3D. Write the answer to the following in hexadecimal:

0xabcd + 12

QUESTION MISC-3E. True/False: The garbage collector we discussed is conservative, because it only runs when we tell it to.

QUESTION MISC-3F. True/False: Given the definition int array[10] the following two expressions mean the same thing: `&array[4] and array

QUESTION MISC-3G. Using the matrix multiply from lecture 12, in what order should you iterate over the indices i, j, and k to achieve the best performance.

QUESTION MISC-3H. True/False: fopen, fread, fwrite, and fclose are system calls.

QUESTION MISC-3I. Which do you expect to be faster on a modern Linux OS, insertion sorting into a linked list of 1000 elements or into an array of 1000 elements?

QUESTION MISC-3J. What does the hardware do differently when adding signed versus unsigned numbers?