CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Name the bug (20 minutes)

Name the bug in each: (a) char *s = malloc(4); strcpy(s, "hello"); (b) free(p); p->x = 1; (c) int *a = malloc(40); return; with no free. (d) free(&local); where local is a local variable.

Done when: (a) heap overflow, (b) use after free, (c) memory leak, (d) invalid free.

Hint

Count the bytes in "hello" with its end mark.

Easy 2: Which tool (20 minutes)

Say whether ASan, Valgrind, or both, would report: a one-byte overflow; an uninitialised read; a use after free; a leak.

Done when: both; Valgrind only; both; both.

Hint

Only Memcheck tracks whether a value was ever stored.

Easy 3: Leak rate (20 minutes)

A server loses 4,096 bytes for each request and handles 200 requests per second. Find the growth in one hour, in MiB.

Done when: 4,096 × 200 × 3,600 = 2,949,120,000 bytes, about 2,813 MiB.

Hint

Multiply, then divide by 1,048,576.

Medium

Medium 1: Reproduce the table (45 minutes)

Build the program of section 1, and run each case plain, under ASan and under Valgrind. Fill a table with what each reports.

Done when: a table that matches section 3 and section 4, with the exit code of each plain run.

Hint

Use echo $? after each plain run.

Medium 2: Find and fix a leak (60 minutes)

Write the request handler of section 2, and run it under valgrind --leak-check=full. Fix it, and run it again.

Done when: a report with about 98 blocks definitely lost before the fix and "All heap blocks were freed" after it, plus the RSS table of section 2 with flat values after the fix.

Hint

Add free(buf) before the function returns.

Medium 3: Overflow that hides (60 minutes)

Allocate 20 bytes and write at index 23, then allocate 25 bytes and write at index 39. Run the program plain and under ASan.

Done when: the plain run prints its output with no error (the usable sizes are 24 and 40 on this allocator), and ASan reports the first write as 3 bytes after a 20-byte region, with the second reported after the first is fixed.

Hint

Print the result of malloc_usable_size first. ASan stops at the first error.

Hard

Hard 1: Count your own allocations (90 minutes)

Write a small library that wraps malloc and free in macros, keeps a count of live blocks and total bytes, and prints a report of the leaked blocks, with file and line, at exit.

Done when: a test program with three leaked blocks gives a report of three entries with the right lines.

Hint

Use __FILE__ and __LINE__ in the macros.

Hard 2: Overhead on three programs (90 minutes)

Measure the time and the peak resident size of three programs of your choice (for example a sort, a hash table and a string loop), plain, with ASan and with Valgrind.

Done when: a table of nine timings and nine sizes, with a sentence on which program slowed the most and a guess at why.

Hint

Use bash time and /usr/bin/time -v if it is installed.

Hard 3: A use-after-free that hides (90 minutes)

Allocate 64 ints, store 42 in element 20, free the block, and print element 20. Then add a malloc of the same size, with a memset to zero, between the free and the print. Run both versions plain and under ASan.

Done when: the first plain run prints 42, the second prints 0, and ASan reports a heap-use-after-free for both.

Hint

A freed block of the same size is the likely one for the next malloc of that size. Use an element far from the start, since the allocator writes its own links into the first 16 bytes of a freed block.