This is not the current version of the class.

# Datarep 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. Sizes and alignments

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

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

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


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


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

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?

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

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

## DATAREP-2. 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?

## DATAREP-11. Dynamic memory allocation

QUESTION DATAREP-11A. True or false?

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

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

For OFFLINE 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;

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

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

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

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

## DATAREP-12. Pointers and debugging allocators

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

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



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->prev = nullptr;
}
...
}


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


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


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
}


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


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

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

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

For parts C–I, 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).

QUESTION DATAREP-38D. optind (line 12)

QUESTION DATAREP-38E. tmp1 (line 23)

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

QUESTION DATAREP-38G. strdup (line 51)

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

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

QUESTION DATAREP-38H. 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?