Section 3: Data representation exercises

In today’s section, we’ll walk through a selection of our data representation exercises, which are problems taken from prior exams. Also take the opportunity to ask questions about the problem set and class material.

All exercises assume a 64-bit x86-64 architecture unless otherwise stated.

The main subjects of these exercises are:

• DATAREP-1: Size and alignment rules.
• DATAREP-2: Computer integer arithmetic.
• DATAREP-11: Memory error types.
• DATAREP-12: Problem set 1, memory debugging, linked list manipulation.
• DATAREP-31: Problem set 1, memory debugging, undefined behavior.

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-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 an integer overflow!

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-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(ptr);
F8.    }

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

Help her track down bugs.

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

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;