Chapter 27 Exercises: Memory Management

Section A: Virtual Address Decomposition

1. Manual Page Table Walk Decompose the following virtual addresses into their PML4, PDP, PD, PT, and offset components (each in decimal and hex). Assume 4-level paging with 4KB pages.

a) 0x0000000000401000 (typical .text section in a non-PIE binary) b) 0x00007FFCF5A00000 (typical stack area) c) 0xFFFF800000000000 (Linux kernel direct map start) d) 0xFFFFFFFF80100000 (typical kernel .text in Linux)

For (a), show:

Bits 47:39 = PML4 index = ?
Bits 38:30 = PDP  index = ?
Bits 29:21 = PD   index = ?
Bits 20:12 = PT   index = ?
Bits 11:0  = Offset     = ?

2. Page Table Entry Construction Construct the 8-byte page table entry for: - Physical address: 0x0000000100000000 (4GB) - Flags: Present, Read/Write, User-accessible, NX bit set

Show the 64-bit value in hex and identify each field.

3. Address Space Coverage Answer these questions about the x86-64 virtual address space: - How many PML4 entries does a single user process typically use? - How large is the region covered by one PML4 entry? (in GB) - How many PT entries cover 1MB of address space? - If each process has its own PML4 table (512 entries × 8 bytes), how much memory does the PML4 table itself occupy?

4. Huge Page Address Decomposition With 2MB huge pages (PS bit set in PD entries), re-decompose: 0x0000000200400000 using 2MB pages: - PML4 index - PDP index - PD index - 21-bit offset within the 2MB page

How does the page table walk change when PS=1 in the PD entry?

Section B: /proc/self/maps Analysis

5. Map Your Own Process Write a C or NASM program that reads and prints /proc/self/maps using only raw syscalls (open, read, write, close). Identify: - The virtual address range for the .text section - The virtual address range for the heap - The virtual address ranges for all loaded shared libraries - The stack region - The vDSO mapping

6. Address Space Impact of malloc Write a program that: 1. Reads /proc/self/maps and records the heap end (the [heap] line's end address) 2. Calls malloc(1) 1000 times 3. Reads /proc/self/maps again 4. Reports how much the heap grew

Now repeat with malloc(200000) (which uses mmap, not brk). What mapping appears instead of heap growth?

7. ASLR Verification Write a program that: 1. Prints its own stack address (address of a local variable) 2. Prints the base address of libc.so.6 from /proc/self/maps 3. Exits with code 0

Run it 5 times and record the addresses. Are they the same? Temporarily disable ASLR:

sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"

Run again 5 times. What changes?

8. mmap vs brk Trace the difference between small and large allocations:

strace -e trace=brk,mmap,munmap ./your_malloc_test 2>&1 | grep -E "(brk|mmap|munmap)"

At what allocation size does glibc switch from brk to mmap? (Hint: it is approximately 128KB by default, controlled by M_MMAP_THRESHOLD in mallopt.)

Section C: Page Fault Analysis

9. Triggering Page Fault Types Write programs that trigger each type of page fault. Use strace or GDB to observe the SIGSEGV or kernel response:

a) Not-present: Access an unmapped virtual address (*(volatile int*)0x12345678 = 0) b) Protection violation (write to read-only): c mmap(NULL, 4096, PROT_READ, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) // then write to it c) NX violation: Map a page with PROT_WRITE but not PROT_EXEC, write shellcode to it, then jump to it d) Stack overflow: Write a recursive function with a large stack frame and recurse until the stack hits the guard page

For each: what is the error code? What address is in CR2?

10. Page Fault Error Code Decoder Write a kernel-level (or QEMU bare-metal) page fault handler that decodes and prints:

Page Fault at 0xADDRESS
  Error: [not-present|protection] [read|write] [kernel|user] [reserved] [fetch]
  CR2  : 0xFAULT_ADDRESS
  RIP  : 0xINSTRUCTION_ADDRESS

Test with at least three different fault types.

Section D: Memory Mapping Implementation

11. File Content Search via mmap Write a NASM program that: 1. Takes a filename (hardcoded or read from stdin) 2. Maps the file with sys_mmap (PROT_READ, MAP_PRIVATE) 3. Searches for the string "root" in the mapped region 4. Prints the byte offset of every occurrence 5. Unmaps and closes

Compare performance against a read()-based implementation on a 10MB file.

12. Shared Memory IPC Write two programs: producer.asm and consumer.asm that communicate via shared anonymous memory: - Producer: maps 4096 bytes with MAP_SHARED|MAP_ANONYMOUS, forks the consumer - Consumer: writes data to the shared page, sets a "done" flag byte - Producer: polls the flag byte (using HLT-equivalent in user space — just loop), then reads and prints the data

Verify that both processes see the same physical memory by printing the mapping address and the data.

13. mmap-Based Memory Allocator Implement a simple memory allocator using mmap:

; my_malloc(size: rdi) → rax = pointer or 0
; my_free(ptr: rdi, size: rsi) → void

; Requirements:
; - For any size, allocate with mmap (MAP_PRIVATE|MAP_ANONYMOUS)
; - Store the actual size in the 8 bytes before the returned pointer
; - my_free uses munmap with the stored size
; - Handle alignment: always return 16-byte aligned addresses

Test with alternating allocations and frees of varying sizes.

Section E: MinOS Memory Management

14. Bitmap Allocator Implementation and Test Implement the MinOS bitmap physical memory allocator from the chapter in full: - pmm_init(total_bytes) — marks all memory in use, then frees the "available" region (for simplicity, just free frames 1–N where N=total_bytes/4096-1; reserve frame 0 as "kernel") - pmm_alloc() — returns physical address of a free frame - pmm_free(physical_addr) — returns frame to pool

Write a test that: 1. Initializes with 16MB (4096 frames) 2. Allocates 1000 frames, stores them in an array 3. Frees every other frame 4. Verifies the free count is correct 5. Allocates 500 more frames and checks none conflict with the first batch

15. Page Table Construction in Assembly Write a MinOS function map_page(virt_addr, phys_addr, flags) that: 1. Walks the PML4 from CR3 2. Creates missing intermediate tables by calling pmm_alloc() (zero-initializes new pages with stosq) 3. Writes the final PT entry with the physical address and flags 4. Calls invlpg to flush the TLB

Test by mapping a known physical address to a known virtual address, writing to the virtual address, and verifying the physical page contains the written data.

16. Kernel Address Space Map Design the virtual address space layout for MinOS. Document your choices in a diagram showing: - Where the kernel code/data is mapped (hint: 0xFFFF800000000000) - Where the physical memory direct map is (all physical memory accessible via kernel vaddr) - Where user process stacks go - Where user process code goes - Where the kernel heap (vmalloc) goes

Implement at least the kernel identity map: map the first 2MB of physical memory to both virtual address 0 (for the bootloader's 1:1 map still in effect) and 0xFFFFFFFF80000000 (the kernel virtual base), using 2MB huge pages for efficiency.