type
status
date
slug
summary
tags
category
icon
password
Below are notes from Architectural and Operating System Support for Virtual Memory.
1 Anatomy(解剖) of a Typical Virtual Address Space
Distinction between "memory" and "address space"
- "memory" is a data storage medium
- "address space" is a set of memory addresses
- not all address actually refers for memory, some may not been allocated to memory, some may be reserved for memory-mapped IO or external devices(non-memory resources)
Address space of a typical process
- how program's higher-level notion of "memory" is mapped onto the hardware's notion of VM is specific to each operating system and application binary interface (ABI)
- a common approach is
- from bottom to top of the address
- program's code and data
- heap
- shared-library
- stack
- operating system
- heap and stack is laid in two end of the space, and grows in opposite direction, to maximize the flexibility (e.g. if need more space for heap, then use more space to grow heap)

Linux process memory map
- print by /proc/<pid>/maps (where <pid> is the process ID)
- each line is a particular range of addresses currently mapped in the virtual address space
- some lines list the name of a particular file backing the corresponding region(e.g. /lib/ld-linux.so.2), while others(e.g. heap and stack) are anonymous because they have no file backing them
- a portion of address space is reserved for the kernel
- although kernel is a separate process and conceptually should have its own address space
- but it would be expensive if the program performs a system call and fullly context switch to a different address space
- this does not violated VM isolation requirements, because kernel address space need access with escalated permissions
- vDSO (virtual dynamically linked shared object)
- is at kernel region of memory, but is executable by user code
- is a special-purpose performance optimization that speeds up some interactions between user and kernel code
- kernel manages various timekeeping data structures posed no special security risks, vDSO is invented as small, carefully controlled, user-accessible regions of kernel space
- partition between user and kernel memory region is left up to the OS
- the partition of 32-bit address space is critical
- 32-bit Linux: lower 3GB for user, upper 1GB for kernel
- 32-bit Windows: lower 2GB for user, upper 2GB for kernel
- the partition of 64-bit address space is not critical
- user/kernel is split in half
- in x86-64, currently requires bits 48-63 of any virtual address to be the same(called "canonical form") (0x0000_0000_0000_0000 to 0x0000_7ffff_7ffff_7ffff is for user, 0xffff_8000_0000_0000 to 0xffff_ffff_ffff_ffff is for kernel, access to address not in canonical form results in illegal memory access exceptions)

Multi-thread process
- all of the threads in a process share the same address space
- may have more than one stack region (usually one stack for each thread), all other virual address space region is shared among all of the thread
2 Memory Permissions
Read | Write | Execute | Use Cases |
Y | Y | Y | Code or data; was common but now deprecated/discouraged due to security risk: W^X (write XOR execute) principle |
Y | Y | - | Read-write data |
Y | - | Y | Executable code |
Y | - | - | Read only data |
- | Y | Y | N/A |
- | Y | - | Interaction with external devices |
- | - | Y | To protect code from inspection; uncommon use |
- | - | - | Guard pages: security feature used to trap buffer overflows or other illegal accesses (often allocated to either side of a newly allocated virtual memory) |
Many region permissions are derived from the segment in the program's object file.
- .data and .bss (zero-initialized data) segments: read/write
- .text (code): read/execute
- .rodata (read-only data): read
- .plt (procedure linkage table) or .got (global offset table): read or execute
- the dynamic loader in the OS is responsible for lazily resolving certain function calls, by patching .plt or .got sections on the fly
- so the dynamic loader may occasionally need to exchange executer permission for write permission (W^X principle) to update .plt or .got segment (self-modifying code)
Users can allocate their own memory regions using system calls(mmap in Unix-like system or VirtualAlloc in Windows).
- permission of these pages can be assigned by the user (not violating hardware restrictions such as W^X)
- permission can also be changed dynamically with system calls(mprotect in Unix-like or VirtualProtect in Windows)
3 Multithreaded Programs
All threads in a process share the same virtual address space (also share a single page table). Since each thread runs in a separate execution context, each thread does receive its own independent stack.
- Sharing stack data between each threads is generally discouraged as a matter of code cleanliness, but not illegal from the point of view of the VM.
Distinct processes not share any part of their address space unless they use one or more of the shared memory mechanism.
Process fork
- when a parent process is duplicated to form an identical child process
- the child process ends up with an exact duplicate of the virtual address space of the parent, the only change is the PID of the child will differ from that of the parent
- virtual space is isolated when fork, but physical data is identical when fork, so no need to duplicate entire physical address range
- most modern OS make liberal use of copy-on-write to implement fork
- as two processes execute, the page table entries for each affected page will slowly be updated accordingly

4 Shared Memory, Synonyms (同义词), and Homonyms (同音词)
Synonyms: multiple virtual addresses of a process point to the same physical address.
Homonyms: a single virtual address reused by more than one process can point to multiple physical addresses.
Shared memory allows different virtual addresses of different processes to point to the same physical address.
- Shared memory is generally used as a means for multiple processes to communicate with each other directly through normal loads and stores, and without the overhead of setting up some other external communication medium.
Synonyms, homonyms and shared memory breaks one-to-one mapping assumption, so it makes more difficult for VM to track the state of memory.
4.1 Homonyms (同音词)
Process-0 uses VA0(e.g. 0xa478_4000) to access PA (e.g. 0xb678_2908), Process-1 uses same numerical value VA1(i.e. 0xa478_4000) to access a different PA(e.g. 0x7834_8961).
Two ways to solve homonyms:
- Flush hardware structures(e.g. TLB) when context switched
- Attach process or address space ID to each virtual address.
- VIVT cache should also takes account of homonyms, or store/load buffer if using virtually addressed structure
4.2 Synonyms (同义词)
Process-0 uses VA0(e.g. 0xb974_c000) and VA1(e.g. 0x39297000) to same PA.
The state of any given physical page may be distributed across multiple page table entries, and all must be considered before taking any action.
- dirty bit must update to all page table entries
- when swapping out a page, all page table entries must be updated
- in high performance processor, load-store forwarding can be speculatively on virtual address and can fallback based on the translated physical addresses later
5 Thread-local Storage
TLS provides some subset of the process’ virtual address space which is (at least nominally) accessible only to that thread, and this in turn can sometimes make it easier to ensure that threads do not clobber each other’s private data.
In an abstract sense, TLS works as follows.
- The user is provided with some API that some data structure should be instantiated once per thread, within the local storage of that thread.
- At runtime, the TLS implementation assigns either a register (e.g., CP15 c13 on ARM, FS or GS on x86) or a base pointer to each thread. Any access to a thread local variable is then transparently indexed relative to the base address stored in the register to access the specific variable instance for the relevant thread.

6 Virtual Memory Management
Memory management requests come from the program explicitly (e.g., via malloc) or implicitly (e.g., stack-allocated function-local variables, or even basic allocation of storage for a program’s instructions). Then OS and VM subsystem is responsible to allocate physical memory.
In reality, the “heap” is just a generic name used to describe a region of memory within which a program can perform its dynamic random-access memory allocation. The C library then either makes the allocation from within its pool(s) of already-allocated memory, or it requests more heap memory from the operating system through system calls such as mmap or brk/sbrk.
- User-level memory management libraries are not technically a part of the VM subsystem, as they do not directly participate in the virtual-to-physical address translation process, nor do they manage physical resources in any way.
- For practical implementation reasons, system calls such as mmap or brk/sbrk generally only allocate VM at page granularity. User-level libraries generally filter out many OS system calls that might otherwise be needed by batching together small allocation requests or by reusing memory regions that have been freed by the program but not yet deallocated from the virtual address space.
The actual VM subsystem begins where the user-level memory management libraries stop. The rest of this book focuses mostly on studying VM from the perspectives of the operating system and VM subsystem, decoupled from the particulars of any one program or programming language.
7 Summary
This chapter talks about VM abstraction, permission bits, synonyms/homonyms, TLS.
The rest of the book is about sophisticated hardware and software mechanisms to implement VM abstraction (on function correctness and performance optimization).