Virtual Address Descriptors

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. When a thread allocates memory, the memory manager must respond with a range of addresses for the thread to use. To do this, 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. Windows Server 2003 implements an AVL tree algorithm (named after their inventors, Adelson-Velskii and Landis) that better balances the VAD tree, resulting in, on average, fewer comparisons when searching for a VAD corresponding with a virtual address. A diagram of a VAD tree is shown in Figure 7-28.

Figure 7-28. 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.

EXPERIMENT: 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