Exercises: Computer Systems Basics

These exercises will help you prepare for quiz questions you may see for Block 1: Computer Systems Basics.

Acknowledgements: These exercises were originally developed for Harvard's CS 61 course and were kindly shared by Eddie Kohler.

BASICS-1. Sizes and alignments

QUESTION BASICS-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)).

True.

This also mostly true for arrays. The exception is zero-length arrays: sizeof(X[0]) == 0, but alignof(X[0]) == alignof(X).

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

True

QUESTION BASICS-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;
};

False (example: A1 = int, A2 = char)

QUESTION BASICS-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;
};

False (if n = 1)

QUESTION BASICS-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).

4M + 4K

QUESTION BASICS-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?

0

QUESTION BASICS-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]

#6 < #1 < #4 < #2 < #3 < #5

BASICS-2. 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);
    do_stuff(&p);
}

This program allocates objects a through g on the heap and then stores those pointers in some stack and global variables. We recommend you draw a picture of the state setup creates.

QUESTION BASICS-2A. 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.

1—D; 2—C; 3—E; 4—B; 5—A

Since p has automatic storage duration, it is located on the stack, giving us 5—A. The global variable has static storage duration, and so does its component global.y; so the pointer &global.y has an address that is below all heap-allocated pointers. This gives us 2—C. The remaining expressions go like this:

global.y == e;
p.y == &e[1], so *p.y == e[1] == (int) &d[100000], and (int *) *p.y == &d[100000];
p.x == g, so p.x[0] == g[0] == *g == c, and *p.x[0] == *c == (int) a.

Address #4 has value 0x8300000, which by assumption is a’s address; so 4—B. Address #3 is much larger than the other heap addresses, so 3—E. This leaves 1—D.

BASICS-3. 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 BASICS-3A. Arrange the following values in increasing numeric order. Assume that x is an int with value 8192.

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

h < a = d = f < b < c < e < g

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 BASICS-3B.

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

0x2c == 44

QUESTION BASICS-3C.

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

"61"

QUESTION BASICS-3D. Your answer should be different from the previous answer.

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

" 0x3d", " 61 ", etc.

BASICS-4. 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 BASICS-4A. 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;




};

Impossible

QUESTION BASICS-4B. Repeat Part A, but create a struct with size 12.

struct size_12 {
    char a;




};

abdc, acbd, acdb, adbc, adcb, …

QUESTION BASICS-4C. Repeat Part A, but create a struct with size 8.

struct size_8 {
    char a;




};

abcd

QUESTION BASICS-4D. 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.

Example: T = short[2], U = char, V = int

BASICS-5. Dynamic memory allocation

QUESTION BASICS-5A. True or false?

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

False, False

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

(size_t) -1, (size_t) -1—anything that causes an overflow

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 BASICS-5C. 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.”

cdefghab (and others). Expect “OK”

QUESTION BASICS-5D. 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.

efghbcad (and others). Expect “double-free + memory leak”

QUESTION BASICS-5E. 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.

efghadbc (and others). Expect “memory leak”

QUESTION BASICS-5F. 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.

eafhcgbd (and others). Expect “out of bounds write”

BASICS-6. Pointers and debugging allocators

You are debugging some students’ dmalloc code from Project 2. The codes use the following metadata, which tracks allocations as a linked list:

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

meta* mhead;    // head of active allocations list

Their linked-list manipulations in dmalloc are similar.

void* dmalloc(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 dfree differ.

Alice’s code:

void dfree(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 dfree(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 dfree(void* ptr, ...) { ...
    meta* m = (meta*) ptr - 1;
    m->next->prev = m->prev;
    m->prev->next = m->next;
    ...
}

Donna’s code:

void dfree(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 here is correct.

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

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

Chris

QUESTION BASICS-6B. 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
}

Alice

QUESTION BASICS-6C. 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);
    print_leak_report();
}

Bob

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

Donna