Virtual Memory Management #

Heap Allocation #

¹

• Heap grows upward, stack grows downward
• Heap boundary is adjusted by the syscalls: brk and sbrk
• When a malloc region is assigned to a process, the physical page is only allocated when it is written (causing a minor page fault)

malloc in GLibc ² #

• For small allocation (< 128 KiB), allocate heap space
• For large allocation, allocate by mmap

Differences between malloc and calloc #

calloc is much more than just malloc + memset.

• when you call malloc, you are not sure whether the pages have been zeroed, but calloc can know
• when you allocate pages, you probably only write a few of them in between instead of all of them. e.g. numpy identity matrix only writes diagonal
• physical memory is allocated on write fault on zeroed out on demand. Zeroing out and writing changes at the same time save one cache miss.

Page Table #

Each 4K page contains 512 8bytes Page Table Directory, each containing the Physical Address of next level page table and read/write permission. To index each directory, 9 bit (2^9=512) is taken out of the virtual address (64 bit in total, but only 48 bit is used). For a four-level page table shown above, 4*9 + 12 (12 bit is the page offset, so is same for physical and virtual address).

Address Space size #

X86-64 only uses 48 bit of both virtual and physical address space. Linux reserves 46 bit for PFN (Physical Frame Number), adding the 12 bit page offset it supports up to 58 bit physical address space for future expansion.

• 16 bit out of 64 bit virtual address pointer can be used as tagged pointer ³
  • the pointer can’t be dereferenced directly, otherwise, CPU will raise exception
  • be cautious about using too many bits, as future five-level is expected to use more than 48 bits
  • widely exploited by database
    • pointer swizzling in LeanStore just uses 1 bit
    • Microsoft CPR (SIGMOD 2019) uses all available bits
• physical address space consumer: not just the DRAM, but also DMA devices ⁴

PTE #

• the translation process on Rust OS impl
• Linux’s consumption of PTE
• Linear Compressed Pages (MICRO 2013) tracks custom page metadata using unused PTE bits

References #

• Architectural and Operating System Support for Virtual Memory
• How the kernel manage your memory