Part 7 of 7 · 3 min read
Exercises
Easy
Easy 1: Split with two levels (20 minutes)
With 10-bit fields and a 12-bit offset, split the address 0x00C01234 into the top index, the second index and the offset.
Done when: top index 3, second index 1, offset 0x234.
Hint
0x00C01234 >> 22 is 3, and (addr >> 12) & 0x3FF is 1.
Easy 2: Count the reads (20 minutes)
How many memory accesses does a TLB miss cost for (a) a flat table, (b) a two-level table, (c) a four-level table? Include the data read.
Done when: 2, 3 and 5.
Hint
A flat table needs one read of the table and one of the data.
Easy 3: Inverted table size (20 minutes)
A machine has 8 GiB of memory, 4 KiB pages and 12 bytes per inverted entry. How large is the inverted table?
Done when: 2,097,152 frames and 24 MiB.
Hint
8 GiB / 4 KiB frames, times 12 bytes.
Medium
Medium 1: Size of a sparse process (45 minutes)
A 32-bit process with 4 KiB pages has 5 MiB of code, data and heap at the bottom, and 2 MiB of stack at the top. Find the number of second-level tables and the total table memory under a two-level layout. Compare with a flat table.
Done when: 1 top table and 3 second-level tables (two for the bottom, one for the top), 16 KiB in all, against 4 MiB.
Hint
5 MiB needs two tables of 4 MiB coverage; 2 MiB of stack needs one.
Medium 2: Decode a real address (45 minutes)
Print the address of a stack variable and of a function, and write a program that cuts any address into the four 9-bit indexes and the 12-bit offset. Compare with the table of section 3 for a run with setarch -R.
Done when: a table of two addresses with their four indexes and offsets.
Hint
Shift right by 12, 21, 30 and 39, and mask with 0x1FF.
Medium 3: Measure VmPTE (60 minutes)
Write the program that maps 16 GiB of address space with MAP_NORESERVE, touches 16 pages side by side or 1 GiB apart, and prints VmPTE before and after.
Done when: a table like the one in section 3 from your own run.
Hint
Read /proc/self/status and look for the line that starts with VmPTE.
Hard
Hard 1: A three-level layout (60 minutes)
A machine has 39-bit virtual addresses, 4 KiB pages and 8-byte entries. Find the number of levels (each table is one page), the bits in each index, and the size of a flat table.
Done when: three levels of 9 bits each, and a flat table of 2^27 × 8 bytes = 1 GiB.
Hint
39 − 12 = 27 bits of page number, cut into 9 + 9 + 9.
Hard 2: Walk by hand and in code (90 minutes)
Build a two-level table in C for a 32-bit space (arrays of 1,024 entries). Map three virtual pages, translate five addresses, and count the table reads for each.
Done when: five translations, with each table read counted, and one address that traps.
Hint
Allocate the second-level table only when the first mapping in its region is made.
Hard 3: Hash table against tree (90 minutes)
Simulate 10,000 mapped pages that cluster in 20 regions of 500 pages. Compute the memory used by a two-level table (4-byte entries, 4 KiB tables) and by a hashed table with 16,384 slots and 16-byte chain entries. Compare.
Done when: two sizes in bytes and a sentence on which is smaller for this clustered workload.
Hint
A region of 500 pages fits in one second-level table of 1,024 entries.