Virtual Memory · Memory Allocation

1. TODO 1 in vtop_starter.c: split v into the four 9-bit indices and the 12-bit offset
2. TODO 2: read the 8-byte pagemap entry at offset (v / 4096) × 8 with pread
3. TODO 3: decode bits 63 (present), 61 (file), 56 (only mine), 0–54 (frame)
4. TODO 4: physical address = frame × 4096 + offset
5. Run with sudo. Then: add a fork() and look at global_var before and after the child writes it

sudo ./vtop (real, shortened)

name           [pgd pud pmd pte] offset
main (code)    [171  69   8 502] +0x388
   present  file 1  only mine 1
printf (libc)  [255 482 169  96] +0x100
   present  file 1  only mine 0
global_var     [171  69   8 505] +0x010
   present  file 0  only mine 1
malloc(64)     [171  69 459 503] +0x2a0
   present  file 0  only mine 1
big, untouched [255 482 164   4] +0x010
   not present
big, touched   [255 482 164   4] +0x010
   present  frame 0x135111
   physical 0x135111010

Without root every frame reads as 0: the kernel hides physical addresses from normal users. The present, file and "only mine" bits still work.

1. TODO 2 first (grow): sbrk(HDR_ALIGNED + n), fill in the header, append it to the list
2. TODO 1 find_fit: walk the list; return the first free block with size ≥ n
3. TODO 3 split: if the block is much bigger than n, cut the rest into a new free block
4. TODO 4 free: mark it free; merge with the next block while it is free and adjacent
5. Compare your heap dumps with the expected ones; then strace -e trace=brk ./mymalloc

./mymalloc (reference; real, shortened)

1. a = 100, b = 1000, c = 50 bytes:
   +0x000: 112 used  +0x090: 1008 used
   +0x4a0:  64 used   break +0x500
2. free(b):  +0x090: 1008 FREE
3. d = malloc(200): first fit + split
   +0x090: 208 used  +0x180: 768 FREE
4. free(d): merges: +0x090: 1008 FREE
5. free(a); e = malloc(3000):
   +0x000: 1152 FREE  +0x4a0: 64 used
   +0x500: 3008 used  break +0x10e0
c still holds "C"

Why a static stdout buffer? printf would call malloc for its buffer, and glibc's malloc would move the same program break: two allocators fighting over one heap.