The memory manager uses a demand-paging algorithm to know when to load pages into memory, waiting until a thread references an address and incurs a page fault before retrieving the page from disk. Like copy-on-write, demand paging is a form of lazy evaluation—waiting to perform a task until it is required.
The memory manager uses lazy evaluation not only to bring pages into memory but also to construct the page tables required to describe new pages. For example, when a thread commits a large region of virtual memory with VirtualAlloc, the memory manager could immediately construct the page tables required to access the entire range of allocated memory. But what if some of that range is never accessed? Creating page tables for the entire range would be a wasted effort. Instead, the memory manager waits to create a page table until a thread incurs a page fault, and then it creates a page table for that page. This method significantly improves performance for processes that reserve and/or commit a lot of memory but access it sparsely.
With the lazy-evaluation algorithm, allocating even large blocks of memory is a fast operation. This performance gain isn't without its trade-offs, however: when a thread allocates memory, the memory manager must respond with a range of addresses for the thread to use. Because the memory manager doesn't build page tables until the thread actually accesses the memory, it can't look to determine which virtual addresses are free. To solve this problem, the memory manager maintains another set of data structures to keep track of which virtual addresses have been reserved in the process's address space and which have not. These data structures are known as virtual address descriptors (VADs). For each process, the memory manager maintains a set of VADs that describes the status of the process's address space. VADs are structured as a self-balancing binary tree to make lookups efficient. A diagram of a VAD tree is shown in Figure 7-18.
Figure 7-18 Virtual address descriptors
When a process reserves address space or maps a view of a section, the memory manager creates a VAD to store any information supplied by the allocation request, such as the range of addresses being reserved, whether the range will be shared or private, whether a child process can inherit the contents of the range, and the page protection applied to pages in the range.
When a thread first accesses an address, the memory manager must create a PTE for the page containing the address. To do so, it finds the VAD whose address range contains the accessed address and uses the information it finds to fill in the PTE. If the address falls outside the range covered by the VAD or in a range of addresses that are reserved but not committed, the memory manager knows that the thread didn't allocate the memory before attempting to use it and therefore generates an access violation.
Viewing Virtual Address Descriptors
You can use the kernel debugger's !vad command to view the VADs for a given process. First find the address of the root of the VAD tree with the !process command. Then specify that address to the !vad command, as shown in the following example of the VAD tree for a process running Notepad.exe:
kd> !process 2a0 1 Searching for Process with Cid == 2a0 PROCESS 8614d030 SessionId: 0 Cid: 02a0 Peb: 7ffdf000 ParentCid: 0554 DirBase: 00d93000 ObjectTable: 81bc47c8 TableSize: 41. Image: notepad.exe VadRoot 8118d868 Clone 0 Private 252. Modified 0. Locked 0. kd> !vad 8118d868 VAD level start end commit 84df4148 ( 2) 10 10 1 Private READWRITE 850cdbe8 ( 3) 20 20 1 Private READWRITE 810b0ee8 ( 1) 30 6f 7 Private READWRITE 8109d308 ( 3) 70 16f 32 Private READWRITE 810e9a28 ( 2) 170 17f 0 Mapped READWRITE 84aedfc8 ( 3) 180 195 0 Mapped READONLY 8118d868 ( 0) 1a0 1ce 0 Mapped READONLY 81190a08 ( 4) 1d0 210 0 Mapped READONLY 85c7b928 ( 3) 220 223 0 Mapped READONLY 86253a08 ( 4) 230 2f7 0 Mapped EXECUTE_READ 810aab48 ( 2) 300 342 0 Mapped READONLY 80db5448 ( 5) 350 64f 0 Mapped EXECUTE_READ Total VADs: 49 average level: 6 maximum depth: 13