Data representation exercises

Exercises not as directly relevant to this year’s class are marked with ⚠️.

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

True. This follows from the array layout rule: arrays are laid out sequentially in memory with no gaps. If the alignment of a type were greater than the size, then the array layout rule would cause element 1 in an array to be misaligned—a contradiction.

The requirement that size ≥ alignment is also mostly true that for array types. The exception is zero-length arrays. Given an array type AT equivalent to T[N], sizeof(AT) == 0, but alignof(AT) == alignof(T).

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

True. This follows from the struct layout rule.

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

struct X {
    T1 m1;
    ...
    Tn mn;
};

struct Y {
    T1 m1;
    ...
    Tn mn;
    char newc;
};

False. It’s possible for newc to slip into some padding that would otherwise be required to preserve alignment. (For example, let n=2, T1=int, and T2=char.)

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

union X {
    T1 m1;
    ...
    Tn mn;
};

struct Y {
    T1 m1;
    ...
    Tn mn;
};

False, because of the special case n=1.

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

4M + 4K. This happens if the chars and ints alternate: C++ will add 3 bytes of padding after every char.

QUESTION DATAREP-1F. Given struct Z { T1 a; T2 b; T3 c; }, which contains no padding, what does (sizeof(T1) + sizeof(T2) + sizeof(T3)) % alignof(struct Z) equal?

0. If the struct contains no padding, then its size equals the sum of the sizes of its members; and the size of any object is a multiple of its alignment.

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]

#6 < #1 < #4 < #2 < #3 < #5. The sizes are:

1. sizeof(char) == 1 (for all C++ implementations no matter what!)
2. sizeof(minipoint) == 3 (no need for padding)
3. sizeof(int) == 4
4. sizeof(unsigned short[1]) == 1 * sizeof(unsigned short) == 2
5. sizeof(char**) == 8
6. sizeof(double[0]) == 0 * sizeof(double) == 0 (tricky)

DATAREP-2. Expression matching

QUESTION DATAREP-2A. Consider the following eight expressions:

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

For one unique value of m, those eight expressions can be grouped into four matched pairs where the two expressions in each pair have the same value, and expressions in different pairs have different values. What are the values of the expressions for that m?

1. -1
2. 8
3. -1
4. 1
5. 0
6. 8
7. 0
8. 1

#2, #3, #6, and #8 are easy. Then bitwise arithmetic reasoning tells us m + ~m + 1 == m + (-m) == 0 and (m & ~m) == 0. That leaves

1. ?
2. 8
3. -1
4. ?
5. 0
6. 8
7. 0
8. 1

There are two unmatched values, -1 and 1; m must equal one of them. If m == 1, then (m & -m) == (1 & -1) == 1, and there are not four matched pairs. If m == -1, though, everything works out.

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.

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

• The pixel at 3,4 is white, which has bit value 0.
• 4,4 is white, also 0.
• 5,4 is white, also 0.
• 6,4 is white, also 0.
• 7,4 is black, which has bit value 1.
• 8,4, 9,4, and 10,4 are black, giving three more 1s.
• Reading them all off, this is 0b00001111, or 15.

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

9,6

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

5,5

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

14,3

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?

32

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

Little-endian. Each element of the the array cute represents a single row, in which a black pixel represents a 1 bit and a white pixel represents a 0 bit. DATAREP-3 states that in each row of the Hello Kitty image, the most significant bit is on the left. We can see that the Hello Kitty picture is 16 bits wide, or 2 bytes wide, which corresponds to one short. Let's look at cute[0], the first row of the image:

We have two bytes in the first row: 00000000 (most significant), and 01000000 (least significant). Shintaro's machine printed 16384, which we can convert to binary:

01000000 | 00000000

Shintaro's machine printed the least significant byte (01000000) and then the most significant byte (00000000). With big-endian, bytes are stored from most to least significant the "natural" way (left to right), whereas with little-endian, bytes are stored from most to least significant in reverse order (right to left). Since Shintaro's machine stored the least significant byte on the left, the data is stored in reverse order, which corresponds to little-endian representation.

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:

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

A	B	C	D	E
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];
    }
}

H. The code flips all bits in the input.

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);
    }
}

D

QUESTION DATAREP-5C.

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

J. cute is an array of unsigned shorts, so indexing with cute[i] accesses 16 bits/2 bytes of data, or the entire ith row of Hello Kitty. Function f2 creates a pointer x to cute of type char*, which has a size of 1 byte. Indexing with x[i] accesses 8 bits/1 byte of data, or half of a row of Hello Kitty. As the for loop iterates, x[0], x[2], x[4] ... x[30] access the first 8 bits of each row of Hello Kitty, which make up the lefthand side of the image:

x[0] = 0 sets the first byte of cute row 0 to 0000'0000, x[2] = 1 sets the first byte of cute row 1 to 0000'0001, x[4] = 2 sets the first byte of cute row 2 to 0000'0010, and so on. You can see that the lefthand side of image J displays this 'counting up' in binary. The code in the for loop never touches the second byte in each row of cute (x[1], x[3], etc.), so the righthand side of Hello Kitty remains unchanged.

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

f3—I; f4—B; f5—C; f6—F; f7—G; f8—A; f9—E

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(); // see next problem
    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 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.

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.

DATAREP-7. ⚠️ Garbage collection ⚠️

⚠️ Here is the top-level function for the conservative garbage collector we wrote in class.

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? List all that apply.

|--|-----|--|-----|--|-----|--|-----|--|-----|--|-----|--|-----|--|---------------| | | a | | b | | c | | d | | e | | f | | g | | None of these |

b, f.

The collector searches the stack for roots. This yields just the values in struct ptrs p (the only pointer-containing variable with automatic storage duration at the time m61_collect is called). The objects directly pointed to by p are g and e. The collector then recursively marks objects pointed to by these objects. From g, it finds c. From e, it finds nothing. Then it checks one more time. From c, it finds the value of a! Now, a is actually not a pointer here—the type of *c is int—so by the definition above, a is not actually reachable. But the collector doesn’t know this.

Putting it together, the collector marks a, c, e, and g. It won’t free these objects; it will free the others (b, d, and f). But b and f are reachable from global.

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

|--|-----|--|-----|--|-----|--|-----|--|-----|--|-----|--|-----|--|---------------| | | a | | b | | c | | d | | e | | f | | g | | None of these |

a

QUESTION DATAREP-7C. Conservative garbage collection in C is often slower than precise garbage collection in languages such as Java. Why? List 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.

#2

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

We are asked to produce a value of N so that no memory error happens on Line A when i == 0, but a memory error does happen when i == 1. So reason that through. What memory errors could happen on Line A if malloc() returns non-nullptr? There’s only one memory operation, namely the dereference m[i]. Perhaps this dereference is out of bounds.

If no memory error happens when i == 0, then a m[0] dereference must not cause a memory error. So the m object must contain at least 4 bytes. But a memory error does happen on Line A when i == 1. So the m object must contain less than 8 bytes. How many bytes were allocated for m? sizeof(point2_vector) * N == sizeof(point2 *) * N == 4 * N. So we have:

• (4 * N) ≥ 4
• (4 * N) < 8

It seems like the only possible answer is N == 1. But no, this doesn’t cause a memory error, because the loop body would never be executed with i == 1!

The key insight is that the multiplications above use 32-bit unsigned computer arithmetic. Let’s write N as X + 1. Then these inequalities become:

• 4 ≤ 4 * (X + 1) = 4 * X + 4 < 8
• 0 ≤ (4 * X) < 4

(Multiplication distributes over addition in computer arithmetic.) What values of X satisfy this inequality? It might be easier to see if we remember that multiplication by powers of two is equivalent to shifting:

• 0 ≤ (X << 2) < 4

The key insight is that this shift eliminates the top two bits of X. There are exactly four values for X that work: 0, 0x40000000, 0x80000000, and 0xC0000000. For any of these, 4 * X == 0 in 32-bit computer arithmetic, because 4×X = 0 (mod 2³²) in normal arithmetic.

Plugging X back in to N, we see that N ∈ {0x40000001, 0x80000001, 0xC0000001}. These are the only values that work.

Partial credit was awarded for values that acknowledged the possibility of overflow.

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.

If no memory error happens on Line A, then N < 2³⁰ (otherwise overflow would happen as seen above). But a memory error does happen on Line B. Line B dereferences m[i][j], for 0 ≤ j ≤ i; so how big is m[i]? It was allocated on Line A with size sizeof(point2) * (i + 1) == 2 * sizeof(double) * (i + 1) == 16 * (i + 1). If i + 1 ≥ 2³² / 16 = 2²⁸, this multiplication will overflow. Since i < N, we can finally reason that any N greater than or equal to 2²⁸ = 0x10000000 and less than 2³⁰ = 0x40000000 will cause the required memory error.

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.

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 DATAREP-9B.

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

0x2c == 44

QUESTION DATAREP-9C.

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

"61"

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

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

" 0x3d", " 61 ", etc.

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

This code was compiled from:

int f4(int a, int b) {
    extern unsigned char y;
    return (a & 5) * 2 + b - y;
}

A valid solution is a=0, b=61, unsigned char y=0.

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;




};

Impossible

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

struct size_12 {
    char a;




};

abdc, acbd, acdb, adbc, adcb, …

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

struct size_8 {
    char a;




};

abcd

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.

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

DATAREP-11. Dynamic memory allocation

QUESTION DATAREP-11A. True or false?

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

Both false. free(nullptr) is allowed, and defined to do nothing. malloc(0) might or might not return nullptr; from the manual page (man malloc):

If size is 0, then malloc() returns either NULL, or a unique pointer value that can later be successfully passed to free().

(nullptr is the preferred way to say NULL in C++.)

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

(size_t) -1, (size_t) -1 — anything that causes overflow on signed integers! sz * nmemb happens within the call to calloc, so calloc can check if overflow will occur and return nullptr. But sz * nmemb is calculated before it is passed to malloc. Depending on the result of the overflow (which is undefined behavior), malloc may or may not have enough space for that allocation; malloc wouldn't know that it overflowed in the first place. In this case, it may or may not return nullptr.

For parts C–F, consider the following 8 statements. (p and q have type char* and start out as uninitialized variables.)

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;

This tool will check your answers for parts C–F, but you should work out an answer to your satisfaction before checking it.

Statements:

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.”

Example solution: cdefghab. For each pointer, the malloc must precede the dereference, which must precede the free, so ega and fhb must appear in that order. The pointer assignments cd are then interspersed in safe places.

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.

Example solution: efghbcad. The key is to use statement c so that statements a and b both refer to the same allocation.

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.

Example solution: efghadbc.

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.

Example solution: eafhcgbd.

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 (crash) on this input? List all students that apply.

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

Chris’s code will segfault. After one allocation, the metadata list has one element, so ptr’s metadata node has m->next == m->prev == nullptr. This means that his m61_free code will dereference a null pointer (m->next->prev) and crash.

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 crash before the report.

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

Alice’s code can’t find ptr1. The shared m61_malloc code adds new linked list nodes at the head of the list, with next pointers leading to older heads. Thus, after the two allocations, memory looks like this in all four implementations:

mhead ─────────────────┐
                       │
           ptr1        v          ptr2
┌─────────┲━━━━━┓      ┌─────────┲━━━━━┓
│next┊prev┃░░░░░┃      │next┊prev┃░░░░░┃
│ XX ┊    ┃░░░░░┃      │    ┊ XX ┃░░░░░┃
└───────│─┺━━━━━┛      └──│──────┺━━━━━┛
^       │              ^  │
└──────────────────────│──┘
        └──────────────┘

Alice’s m61_free, though, sets mhead to nullptr when the freed metadata node has null prev. This loses all links to older nodes.

mhead XX

           ptr1
┌─────────┲━━━━━┓
│next┊prev┃░░░░░┃
│ XX ┊ XX ┃░░░░░┃
└─────────┺━━━━━┛

Alice should update mhead to m->next, not nullptr, when m->prev == nullptr.

QUESTION DATAREP-12C. Whose code could improperly report a leaked piece of memory on this input, or cause a crash in m61_printleakreport (because the mhead list contains garbage)? 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();
}

Bob’s code will do this. The problem is that Bob does not update mhead in the case that mhead points to the element being freed. After the malloc, memory looks like this:

mhead
│
v          ptr1
┌─────────┲━━━━━┓
│next┊prev┃░░░░░┃
│ XX ┊ XX ┃░░░░░┃
└─────────┺━━━━━┛

And after the free, memory looks like this. ptr1 and associated metadata has been freed, but mhead still points to the freed space:

mhead
│
v
?????????????????
?????????????????
?????????????????
?????????????????

The leak check report will print something associated with ptr1, and it might crash, too, by causing use-after-free errors.

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

Donna’s code is correct!

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.

True, True

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 // ???.

if (n->key == 1) {
    a->frees = n->right;
} else {
    a->frees = n + 1;
    a->frees->key = n->key - 1;
    a->frees->right = n->right;
}

Another solution:

if (n->right) {
    a->frees = n->right;
} else if (n->key == 1) {
    a->frees = NULL;
} else {
    a->frees = n + 1;
    a->frees->key = n->key - 1;
}

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) {




}

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

Or, if you use the solution above:

void node_free(arena* a, node* n) {
    n->right = a->frees;
    a->frees = 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;
}

arena_group* node_find_group(arena* a, node* n) {
    for (arena_group* g = a->groups; g; g = g->next_group) {
        if ((uintptr_t) &g->nodes[0] <= (uintptr_t) n
            && (uintptr_t) n <= (uintptr_t) &g->nodes[1023]) {
            return g;
        }
    }
    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) {




}

arena_group* node_find_group(arena* a, node* n) {
    uintptr_t n_addr = (uintptr_t) n;
    return (arena_group*) (n_addr - n_addr % 32768);
}

DATAREP-14. Data representation

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

9. int A = 6;
10. int B = 0x6;
11. 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;

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

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 0x00400000
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.

7, in a register

QUESTION DATAREP-15B. The variable maxitems

4, in a read-only data segment

QUESTION DATAREP-15C. The structure s

6, in a read/write data segment

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

1, heap

QUESTION DATAREP-15E. The variable u

2, stack, or 7, in a register

QUESTION DATAREP-15F. main

5, in a text segment starting at address 0x00400000

QUESTION DATAREP-15G. printf

3, between the heap and the stack

QUESTION DATAREP-15H. argc

2, stack, or 7, in a register

QUESTION DATAREP-15I. The number the user enters

2, stack

QUESTION DATAREP-15J. The variable L

6, in a read/write data segment

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.

The key thing to understand is that both of these approaches use relative pointers and both can be used to solve the problem of sharing a mapped region among processes that might have the region mapped at different addresses.

Possible advantages:

Within a region, you can safely use memcpy as moving pointers around inside the region does not change their value. If you copy a self relative pointer to a new location, its value has to change. That is, imagine that you have a self-relative pointer at offset 4 from the region and it points to the object at offset 64 from the region. The value of the self relative pointer is 60. If I copy that pointer to the offset 100 from the region, I have to change it to be -36. If you save the region as a uintptr_t or a char *, then you can simply add the offset to the region; self-relative-pointers will always be adding/subtracting from the address of the location storing the pointer, which may have a type other than char *, so you'd need to cast it before performing the addition/subtraction.

You can use a larger region: if we assume that we have only N bits to store the pointer, then in the base+offset model, offset could be an unsigned value, which will be larger than the maximum offset possible with a signed pointer, which you need for the self-relative case. That is, although the number of values that can be represented by signed and unsigned numbers differs by one, the implementation must allow for a pointer from the beginning of the region to reference an item at the very last location of the region -- thus, your region size is limited by the largest positive number you can represent.

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

You don't have to know the address at which the region is mapped to use them. That is, given a location containing a self-relative pointer, you can find the target of that pointer.

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.

A good choice is ptrdiff_t, which represents differences between pointers. Other reasonable choices include uintptr_t and unsigned long.

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

(ll1*) (region + node1.r_next)

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

The same choices work; again ptrdiff_t is best.

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

(ll2*) ((char*) &node2.sr_next + node2.sr_next)

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 { ... };

0; this declares the type, not any object

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

16: 8 on the heap plus 8 on the stack

QUESTION DATAREP-17C. my_union u;

16 (on the stack)

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

8 (on the stack)

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

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.

Some examples: sizeof(char) = 0; sizeof(char) = 2; sizeof(short) = 8 (i.e., longer than int); sizeof(int) = 2 (though not discussed in class, turns out that C++ requires ints are at least 2 bytes big); etc.

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

32

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)?

f1 is 7 bytes.

f2 is 16 bytes with 16-byte alignment, so add 9B padding.

f3 is 4 bytes (and is already aligned).

f4 is 8 bytes with 8-byte alignment, so add 4B padding.

That adds up to 7 + 9 + 16 + 4 + 4 + 8 = 16 + 16 + 16 = 48 bytes.

That’s a multiple of the structure’s alignment, which is 16, so no need for any end padding.

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

16

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)

Always

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

Possibly

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

Possibly

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

Never

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

Possibly

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

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)

Undefined

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

Defined

QUESTION DATAREP-19C.

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

(Defined / Undefined)

Defined (only C++ programs can have undefined behavior; the behavior of x86-64 instructions is always defined)

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

Defined

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

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) {





}

return i * 2;

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 ______________________________________;
}

return (u.c[0] << 24) | (u.c[1] << 16) | (u.c[2] << 8) | u.c[3];

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 ______________________________________;
}

    return ((x & 0xFF) << 24) | ((x & 0xFF00) << 8) | ((x & 0xFF0000) >> 8) | (x >> 24);

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) { 






}

    return big_to_little(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?

32

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	^

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) {





}

Any of these work:

    return a & ~b;
    return a - (a & b);
    return a & ~(a & 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	1	{A}
(unsigned) ~a < (unsigned) a	1	{A}
a < 0	1	{A}
(1 << (s/2)) - 1	15	{A,B,C,D}
a * a	4	{C}
abs(a)	2	{D}
x & (x - 1)	0	{}
x - 1	3	{A,D}
x	4	{C}
s	8	{B}

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.

Lots of people misinterpreted this to mean the player reused their own position and ignored the other player. That mistake was allowed with no points off. The code below checks whether any position was reused by either player.

if ((b->moves[XS] | b->moves[OS]) & ttt_values[row][col]) {
    return -1;
}

OR
if ((b->moves[XS] | b->moves[OS] | ttt_values[row][col]) == (b->moves[XS] | b->moves[OS])) {
    return -1;
}

OR
if ((b->moves[XS] + b->moves[OS]) & ttt_values[row][col]) {
    return -1;
}

OR
if ((b->moves[p] ^ ttt_values[row][col]) < b->moves[p]) {
    return -1;
}

etc.

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

• int popcount(unsigned n)
  Return the number of 1 bits in n. (Stands for “population count”; is implemented on recent x86 processors by a single instruction, popcnt.)

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) {






}

return popcount(b->moves[XS] | b->moves[OS]);

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

(b->moves[XS] & 0x421) == 0x421

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.

The same answers as for part A work.

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

int tictactoe_nmoves(const tictactoe* b) {








}

Either of:

return popcount((b->moves[0] | b->moves[1]) & 0x777);
return popcount((b->moves[0] | b->moves[1]) & 0x777000);

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);







}

return (b->moves[p] + 0x11111111) & 0x88888888;

// Another amazing possibility (Allen Chen and others):
return b->moves[p] & (b->moves[p] << 1) & (b->moves[p] << 2);

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.

ll_node* find_element(void* mapped_file, ll_node* list, int value) {
    while (true) {
        if (list->value == value)
            return list;
        if (list->offset == (size_t) -1)
            return NULL;
        list = (ll_node*) ((char*) mapped_file + list->offset);
    }
}

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)

2¹⁶ - 1 or 65535

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

-1

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

1024 or 2¹⁰

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

5

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

-1

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

4096 or 2¹²

QUESTION DATAREP-24G. Given this structure:

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

This expression: sizeof(ps);

TRICK QUESTION! 8

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

16

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

0xBC == 11*16 + 12 == 160 + 16 + 12 == 188

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

0xBC has most-significant bit on, so the value as a signed char is less than zero. We seek x so that 0xBC + x == 0x100. The answer is 0x44: 0xBC + 4 == 0xC0, and 0xC0 + 0x40 == 0x100. So −0x44 == −4*16 − 4 == −68.

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] =

0xE4 (-28)

QUESTION DATAREP-25B. cp + 7 =

0x100001027

QUESTION DATAREP-25C. s1 + 1 =

0x100001038

QUESTION DATAREP-25D. s1->i =

0xd3c2b1a0 (-742215264)

QUESTION DATAREP-25E. sizeof(s1) =

8

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

0x100001028

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

0x100001020

QUESTION DATAREP-25H. s1->l =

0x9f8e7d6c5b4a3928 (-6949479270644565720)

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

0xf201 (-3583)

QUESTION DATAREP-25J. u->l =

0x1706f5e4d3c2b1a0 (1659283875886707104)

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

False. T1 = char, T2 = int, T3 = char[5]

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.

True. Padding only occurs between objects with different alignments, and is limited by the second alignment; sorting by alignment therefore minimizes padding.

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.

True. It’s all the same; alignment is max alignment of every component, and is independent of order.

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

Alternating char and long gives the most padding, which is 7*(n/2) when n is even and 7*(n+1)/2 otherwise.

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

0

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:

• Must reject the expression as a type error.
• May assume that the expression is true (that a + (int) 1 > a for all a).
• Must not assume that the expression is true.

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

1—May assume; 2—Must not assume; 3—May assume; 4—May assume (in fact due to integer promotion, this statement really is always true, even in mathematical terms); 5—Must reject.

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:

array_size check: (uintptr_t) array + 4 * array_size < (uintptr_t) array

ptr_into_array check: (uintptr_t) ptr_into_array - (uintptr_t) array > 4 * array_size

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.

(x & (1UL << (sizeof(x) * CHAR_BIT - 1))) != 0

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

1, 2

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

while (true) {
    (void) malloc(1);
}

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

2, 4

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

Examples: (a < b) * x, (-(uintptr_t) (a < b)) & x

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.

int ffs(unsigned long x) {
    if (!x) {
        return 0;
    }
    int ans = 1;
    if (!(x & 0x00000000FFFFFFFFUL)) {
        ans += 32; x >>= 32;
    }
    if (!(x & 0x0000FFFF)) {
        ans += 16; x >>= 16;
    }
    if (!(x & 0x00FF)) {
        ans += 8; x >>= 8;
    }
    if (!(x & 0x0F)) {
        ans += 4; x >>= 4;
    }
    if (!(x & 0x3)) {
        ans += 2; x >>= 2;
    }
    return ans + (x & 0x1 ? 0 : 1);
}

DATAREP-30. Data representation

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

char[19404329]

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?

1

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

char (or unsigned char or signed char)

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)?

8

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

4

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

Little-endian

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

Yes

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.    struct m61_metadata {
D2.        size_t magic;
D3.        size_t padding;
D4.    };

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(meta);
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)?

16

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

m61_malloc((size_t) -15). This turns into malloc(1) and the dereference of meta->magic becomes invalid.

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

m61_malloc((size_t) -1)

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.

C3: if (p) { memset(p, 0, sz * count); }

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() {



    ________________________
}

free(nullptr);

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.

F4: fprintf(stderr, meta->magic == 0xB0B0B0B0 ? "double free of %p" : "invalid free of %p", ptr)

after F6: meta->magic = 0xB0B0B0B0;

DATAREP-32. Memory word search

QUESTION DATAREP-32A. What is decimal 61 in hexadecimal?

0x3d, 2 pts

The following is a partial dump of an x86-64 Linux program’s memory. Note that each byte is represented as a hexadecimal number. Memory addresses increase from top to bottom and from left to right.

           ..0 ..1 ..2 ..3 ..4 ..5 ..6 ..7  ..8 ..9 ..a ..b ..c ..d ..e ..f
  601080:   00  00  00  00  4f  ef  38  1e   47  97  48  45  ff  ff  00  00
  601090:   ff  ff  ff  ff  c3  ff  ff  ff   3d  00  00  00  30  c7  5f  14
  6010a0:   3d  00  00  00  00  00  00  00   70  7e  1b  01  00  00  00  00
  6010b0:   7c  2d  8f  ba  fd  7f  00  00   c3  ff  ff  ff  ff  ff  ff  ff
  6010c0:   a0  10  60  00  00  00  00  00   49  20  74  6f  6f  6b  20  36
  6010d0:   31  00  00  00  00  00  00  00   47  9d  ff  ff  ff  7f  00  00

QUESTION DATAREP-32B. What memory segment contains the memory dump?

Data segment (globals), 2 pts

For questions 3C–3I, give the last two digits of the address of the given object in this memory dump (so for the object located at address 0x6010a8, you would write “a8”). There’s a single best answer for every question, and all questions have different answers.

QUESTION DATAREP-32C. A long (64 bits) of value 61.

a0, 2 pts

QUESTION DATAREP-32D. A long of value -61.

b8, 2 pts

QUESTION DATAREP-32E. An int of value 61.

98, 1 pt

QUESTION DATAREP-32F. A pointer to an object in the heap.

a8, 2 pts

QUESTION DATAREP-32G. A pointer to a local variable.

d8, 2 pts

QUESTION DATAREP-32H. A pointer that points to an object present in the memory dump.

c0, 1 pt

QUESTION DATAREP-32I. The first byte of a C string comprising at least 4 printable ASCII characters. (Printable ASCII characters have values from 0x20 to 0x7e.)

c8, 1 pt

DATAREP-33. Architecture

QUESTION DATAREP-33A. Write a C++ expression that will evaluate to false on all typical 32-bit architectures and true on all typical 64-bit architectures.

3pts sizeof(void*) == 8

QUESTION DATAREP-33B. Give an integer value that has the same representation in big-endian and little-endian, and give its C++ type. Assume the same type sizes as x86-64.

2pts ex: int x = 0

QUESTION DATAREP-33C. Repeat question B, but with a different integer value.

2pts ex: int x = -1 :)

QUESTION DATAREP-33D. Complete this C++ function, which should return true iff it is called on a machine with little-endian integer representation. Again, you may assume the same type sizes as x86-64.

bool is_little_endian() {



}

3pts

bool is_little_endian() {
    union { int a; char c[4]; } u;
    u.a = 0;
    u.c[0] = 1;
    return u.a == 1;
}

DATAREP-34. Undefined behavior

The following code is taken from the well-known textbook Mastering C Pointers (with some stylistic changes). Assume it is run on x86-64.

#include <stdlib.h>
#include <stdio.h>
void main() {
    int* x = malloc(400);
    if (x == nullptr) {
        printf("Out of memory\n");
        exit(0);
    } else {
        for (int y = 0; y <= 198; ++x) {
            *(x + y) = 88;
        }
    }
}

QUESTION DATAREP-34A. List all situations in which this program will not execute undefined behavior. (There is at least one.)

3pts If malloc returns nullptr.

QUESTION DATAREP-34B. True or false? The expression ++x could be replaced with ++y without changing the meaning of the program.

3pts True! The undefined behavior is the same either way.

Here’s an updated version of the program.

#include <stdlib.h>
#include <stdio.h>
void main() {
    int* x = malloc(sizeof(int) * 200);
    if (x == nullptr) {
        printf("Out of memory\n");
        exit(0);
    } else {
        for (int y = 0; y <= 198; ++y) {
            *(x + y) = 88;
        }

        int i = random() % 200;
        printf("x[%d] == %d\n", i, x[i]);
    }
}

QUESTION DATAREP-34C. True or false? The expression *(x + y) could be replaced with x[y] without changing the meaning of the program.

3pts True

QUESTION DATAREP-34D. True or false? The expression *(x + y) could be replaced by * (int*) ((uintptr_t) x + y) without changing the meaning of the program.

3pts False (address arithmetic isn’t the same for pointer arithmetic, except for pointers with type equivalent to char)

DATAREP-35. Odd alignments

QUESTION DATAREP-35A. Write a struct definition that contains exactly seven bytes of padding on x86-64.

3pts struct {long a; char b;}

QUESTION DATAREP-35B. Can an x86-64 struct comprise more than half padding? Give an example if so, or explain briefly why not.

3pts Yes. struct {char a; long b; char c;} has size 24 and 14 bytes of padding.

The remaining questions consider a new architecture called x86-64-rainbow, which is like x86-64 plus special support for a fundamental data type called color. A color is a three-byte data type with red, green, and blue components, kind of like this:

struct color {
    unsigned char red;
    unsigned char green;
    unsigned char blue;
};

But unlike struct color on x86-64, which has size 3 and alignment 1, color on x86-64-rainbow has size 3 and alignment 3. All the usual rules for C abstract machine sizes and alignments still hold.

QUESTION DATAREP-35C. What is the alignment of pointers returned by malloc on x86-64-rainbow?

48! Pointers returned by malloc must be maximally aligned (they must be aligned suitably for any datatype). A struct that contains both a long double and a color must have alignment a multiple of both 16 and 3—that’s 48.

QUESTION DATAREP-35D. Give an example of an x86-64-rainbow struct that ends with more than 16 bytes of padding.

A simple example is struct { long a[3]; color b; }. This has alignment lcm(8,3) = 24, size 48 (the smallest multiple of 24 ≥ 27), and ends with 21 bytes of padding:

offsets 0-23:  24 bytes long a[3]
offsets 24-26: 3 bytes color b (NB starting offset is a multiple of 3)
offsets 27-47: 21 bytes padding

Other structs work too, such as struct { long a[2]; color b[3]; }.

DATAREP-36. Debugging allocators

In problem set 1, you built a debugging allocator that could detect many kinds of error. Some students used exclusively internal metadata, where the debugging allocator’s data was stored within the same block of memory as the payload. Some students used external metadata, such as a separate hash table mapping payload pointers to metadata information.

QUESTION DATAREP-36A. Which kind of error mentioned by the problem set could not be detected by external metadata alone?

2pts Boundary write errors.

The problem set requires the m61 library to detect invalid frees, which includes double frees. However, double frees are so common that a special double-free error message can help users. Jia Tolentino wants to print such a message. Her initial idea is to keep a set of recently freed pointers:

static void* recently_freed[10];
static size_t recently_freed_index;

static bool is_recently_freed(void* ptr) {
    for (int i = 0; i != 10; ++i) {
        if (recently_freed[i] == ptr) {
            return true;
        }
    }
    return false;
}

static void add_recently_freed(void* ptr) {
    recently_freed[recently_freed_index] = ptr;
    recently_freed_index = (recently_freed_index + 1) % 10;
}

QUESTION DATAREP-36B. What eviction policy is used for the recently_freed array?

2pts FIFO (round-robin).

Jia uses these helpers in m61_free as follows. (You may assume that is_invalid_free(ptr) returns true for every invalid or double free.)

void m61_free(void* ptr, const char* file, int line) {
    if (ptr != nullptr) {
        if (is_recently_freed(ptr)) {
            fprintf(stderr, "... double-free message ...");
            abort();
        } else if (is_invalid_free(ptr)) {
            fprintf(stderr, "... invalid-free message ...");
            abort();
        } else {
            add_recently_freed(ptr);
            ... actually free `ptr` ...
        }
    }
}

She has not yet changed m61_malloc, though she knows she needs to. Help her evaluate whether her design achieves the following mandatory and desirable (that is, optional) requirements.

Note: As you saw in tests 32 and 33 in pset 1, aggressive attacks from users can corrupt metadata arbitrarily. You should assume for the following questions that such aggressive attacks do not occur. The user might free something that was never allocated, and might double-free something, but will never overwrite metadata.

QUESTION DATAREP-36C. Mandatory: The design must not keep unbounded, un-reusable state for pointers that have been freed. Write “Achieved” or “Not achieved” and explain briefly.

6 pts for C-E together. +5 if one serious error; +3 if two serious errors

Achieved. The design only keeps space for 10 recently-freed pointers.

QUESTION DATAREP-36D. Desirable: The design should report a double-free as a double-free, not an invalid free. Write “Achieved” or “Not achieved” and explain briefly.

Not achieved. If a pointer falls off the list after 10 frees, Jia’s design will report a double-free of that pointer as an invalid free.

QUESTION DATAREP-36E. Mandatory: The design must never report valid frees as double-frees or invalid frees. Write “Achieved” or “Not achieved” and explain briefly.

Not achieved. A recently-freed pointer can be reused by malloc, but she hasn’t accounted for that. So if (1) a pointer is freed, (2) a malloc returns the same pointer, (3) the user frees that pointer again, that valid free will be reported as a double free.

QUESTION DATAREP-36F. Describe code to be added to m61_malloc that will achieve all mandatory requirements, if any are required.

3pts Here’s the cleanest solution to the 4E problem. Remove returned pointers from recently_freed. Add this code to malloc before return ptr:

for (int i = 0; i != 10; ++i) {
    if (recently_freed[i] == ptr) {
        recently_freed[i] = nullptr;
    }
}

DATAREP-37. Representations

Your job in the following questions is to complete each C++ program so that it prints 61 to standard output when run. Your answer should fill in the blank _________, and you may assume system calls execute without error. If a question cannot be answered so that the program reliably prints 61 with no undefined behavior, say so and explain briefly.

To compile these programs, use a command line such as c++ -std=gnu++17 -pthread x.cc.

QUESTION DATAREP-37A.

#include <cstdio>
int main() {
    printf("%d\n", _________);
}

61

QUESTION DATAREP-37B.

#include <cstdio>
int main() {
    printf("%ld\n", _________);
}

61L or (long) 61 are best; 61 will cause a compiler warning, because it’s an int and the format expects a long.

QUESTION DATAREP-37C.

#include <cstdio>
int main() {
    printf("%x\n", _________);
}

6 * 16 + 1, 0x61, 97

QUESTION DATAREP-37D.

#include <cstdio>
int main() {
    unsigned x = 4294967200;
    printf("%d\n", x + _________);
}

157, - x + 61, 96 + 61

QUESTION DATAREP-37E.

#include <cstdio>
struct sixtyfun {
    _________
};
int main() {
    printf("%zu\n", sizeof(sixtyfun));
}

char c[61];

QUESTION DATAREP-37F.

#include <cstdio>
struct sixtyfun {
    int i;
    _________
};
int main() {
    printf("%zu\n", sizeof(sixtyfun));
}

This cannot be done. struct sixtyfun has minimum alignment of 4 (because int has alignment 4), so its size must be a multiple of 4.

QUESTION DATAREP-37G.

#include <cstdio>
#include <cstdint>
struct sixtyfun {
    unsigned long larr[6];
    _________
    char carr[10];
};
int main() {
    sixtyfun x;
    printf("%zu\n", (uintptr_t) &x.carr[1] - (uintptr_t) &x.larr[1]);
}

Anything with size 20, such as char c[20]; or int x[5];.

QUESTION DATAREP-37H.

#include <cstdio>
#include <cassert>
int main() {
    unsigned x = 419618010;
    assert(x == 0x1902DCDA);
    _________
    printf("%d\n", ((x | a) >> b) & c);
}

int a = 255, b = 0, c = 61;
int a = -1, b = 0 (or anything ≤31), c = 61;
unsigned a = 0x10000, b = 12, c = 0xFF;
int a = 32, b = 1, c = 63;
There are many other possibilities!

QUESTION DATAREP-37I.

#include <cstdio>
int main() {
    int x;
    int y = x + 1;
    printf("%d\n", y - x + _________);
}

This cannot be done without undefined behavior, because y is computed using an uninitialized variable.

QUESTION DATAREP-37J.

#include <cstdio>
#include <unistd.h>
int main() {
    int x[10] = { 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };
    for (int i = 0; i <= STDERR_FILENO; ++i) {
        x[i] += _________;
    }
    printf("%d\n", x[0] + x[1] + x[2] + x[3]);
}

Anything that adds 15 total to x[0]…x[2]. For example, 5

QUESTION DATAREP-37K.

#include <cstdio>
#include <cassert>
#include <unistd.h>
int main() {
    const char* args[] = _________;
    int r = execvp(args[0], (char**) args);
    assert(r >= 0);
}

{ "echo", "61", nullptr }

QUESTION DATAREP-37L.

#include <cstdio>
#include <cassert>
#include <unistd.h>
int main() {
    int pfd[2];
    int r = pipe(pfd);
    assert(r >= 0);
    pid_t p = fork();
    assert(p >= 0);
    if (p == 0) {
        _________
        const char* args[] = {"cat", nullptr};
        r = execvp(args[0], (char**) args);
        assert(r >= 0);
    }
    close(pfd[0]);
    ssize_t nw = write(pfd[1], "61\n", 3);
    assert(nw == 3);
    close(pfd[1]);
    sleep(3);
}

dup2(pfd[0], 0); close(pfd[0]); close(pfd[1]);

The sleep(3), which is not waitpid, makes many other solutions work too. dup2(pfd[0], 0); works; pipe hygiene isn't important because the parent exits.

printf("61\n"); almost works, but something weird happens on Mac OS X.

QUESTION DATAREP-37M.

#include <cstdio>
#include <cassert>
#include <unistd.h>
#include <sys/wait.h>
int main() {
    pid_t p = fork();
    assert(p >= 0);
    if (p == 0) {
        printf("6");
        fflush(stdout);
        _exit(0);
    }
    _________
    printf("1\n");
}

waitpid(p, nullptr, 0)

QUESTION DATAREP-37N. Note that there are three blanks to fill in with code (you may also leave them empty).

#include <cstdio>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <unistd.h>
int x;
std::mutex m;
std::condition_variable cv;
void tf(int low, int high) {
    _________#1
    if (low + 1 == high) {
        _________#2
        ++x;
    } else {
        _________#3
        int mid = low + (high - low) / 2;
        std::thread t1(tf, low, mid);
        std::thread t2(tf, mid, high);
        t1.join();
        t2.join();
    }
}
int main() {
    std::thread t(tf, 0, 61);
    t.join();
    printf("%d\n", x);
}

#1, #3: nothing. #2: std::unique_lock<std::mutex> guard(m);

If the lock is in #1 (and there is no unlock in #3), that causes deadlock.

DATAREP-38. Memory layout

The following code computes a Fibonacci number.

#include <cerrno>
#include <getopt.h>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <unistd.h>

// copied from <cstdio> for your reference:
#define EOF (-1)

// copied from <getopt.h> for your reference:
extern int optind;

static void usage() {
    fprintf(stderr, "Usage: ./fib NUMBER\n");
    exit(1);
}

unsigned long fib(unsigned long n) {
    if (n < 2) {
        return n;
    } else {
        unsigned long tmp1 = fib(n - 1);
        unsigned long tmp2 = fib(n - 2);
        return tmp1 + tmp2;
    }
}

int main(int argc, char *argv[]) {
    // process command line options
    char ch;
    while ((ch = getopt(argc, argv, "h")) != EOF) {
        switch (ch) {
        case 'h':
        case '?':
        default:
            usage();
        }
    }

    // skip processed options
    argc -= optind;
    argv += optind;

    // require 1 argument
    if (argc != 1) {
        usage();
    }

    // parse argument
    unsigned long n = strtoul(strdup(argv[0]), nullptr, 10);
    if (n == 0 && errno == EINVAL) {
        usage();
    }

    // print fib(n)
    unsigned long f = fib(n);
    printf("fib(%lu) = %lu\n", n, f);
}

QUESTION DATAREP-38A. What are fib(0), fib(1), and fib(2)?

0, 1, and 1, respectively. Since 0 < 2 and 1 < 2, line 18 means fib(0) == 0 and fib(1) == 1. fib(2) equals fib(0) + fib(1), which is 0 + 1 == 1.

QUESTION DATAREP-38B. What are sizeof(fib(0)), sizeof(fib(1)), and sizeof(fib(2))?

8, 8, and 8. sizeof(EXPRESSION) means the same thing as sizeof(TYPE OF EXPRESSION), which here is sizeof(unsigned long) == 8.

For parts C–H, select from the list below the part of memory that best describes where you will find the object.

1. In the heap
2. In the stack
3. Between the heap and the stack
4. In a read-only data segment
5. In a code segment
6. In a read/write data segment

QUESTION DATAREP-38C. The string "fib(%lu) = %lu\n" (line 58).

This is a C string constant, which has type const char*. These kinds of objects are stored in read-only data segments (#4).

QUESTION DATAREP-38D. optind (line 12)

This object is global, because it’s declared outside of any function. All global objects are stored in a global data segment. This object’s type is int, so it is writable, and is stored in a read/write data segment (#6).

QUESTION DATAREP-38E. tmp1 (line 23)

tmp1 is a local variable, and all local variables are stored on the stack (#2).

QUESTION DATAREP-38F. fib (lines 1-6)

This function is stored in the executable’s code segment (#5).

QUESTION DATAREP-38G. strdup (line 51)

All functions are represented as instructions stored in memory. Those instructions are typically stored in a code segment (#5). However, strdup is a library function, and if such functions are defined in a shared library, they are often loaded at an address between the heap and the stack (#3).

QUESTION DATAREP-38H. The string being passed to strtoul (line 51). (Read the manual page for strdup first!)

The argument to strtoul is returned from strdup, and strdup “returns a pointer to a new string which is a duplicate of the string s. Memory for the new string is obtained with malloc”. Thus, this argument is a pointer into the heap (#1).

QUESTION DATAREP-38I. Does this program contain a memory leak?

Yes! The string allocated and returned by strdup is never freed, so it is leaked, and a leak-checking sanitizer will warn about it.

QUESTION DATAREP-38J. Consider a call to fib(10) that was called from fib(11). Will fib(10)’s tmp1 variable have a larger, smaller, or equal address as fib(11)’s?

Smaller. Stacks grow down, so local variables in a callee function will have smaller addresses than local variables in the caller.