Section 5.2. Overview of the FreeBSD Virtual-Memory System

5.2. Overview of the FreeBSD Virtual-Memory System

The FreeBSD virtual-memory system is based on the Mach 2.0 virtual-memory system [Tevanian, 1987], with updates from Mach 2.5 and Mach 3.0. The Mach virtual-memory system was adopted because it features efficient support for sharing and a clean separation of machine-independent and machine-dependent features, as well as multiprocessor support. None of the original Mach system-call interface remains. It has been replaced with the interface first proposed for 4.2BSD that has been widely adopted by the UNIX industry; the FreeBSD interface is described in Section 5.5.

The virtual-memory system implements protected address spaces into which can be mapped data sources (objects) such as files or private, anonymous pieces of swap space. Physical memory is used as a cache of recently used pages from these objects and is managed by a global page-replacement algorithm.

The virtual address space of most architectures is divided into two parts . For FreeBSD running on 32-bit architectures, the top 1 Gbyte of the address space is reserved for use by the kernel. Systems with many small processes making heavy use of kernel facilities such as networking can be configured to use the top 2 Gbyte for the kernel. The remaining address space is available for use by processes. A traditional UNIX layout is shown in Figure 5.3 (on page 142). Here, the kernel and its associated data structures reside at the top of the address space. The initial text and data areas of the user process start at or near the beginning of memory. Typically, the first 4 or 8 Kbyte of memory are kept off-limits to the process. The reason for this restriction is to ease program debugging; indirecting through a null pointer will cause an invalid address fault instead of reading or writing the program text. Memory allocations made by the running process using the malloc () library routine (or the sbrk system call) are done on the heap that starts immediately following the data area and grows to higher addresses. The argument vector and environment vectors are at the top of the user portion of the address space. The user's stack starts just below these vectors and grows to lower addresses. Subject to only administrative limits, the stack and heap can each grow until they meet. At that point, a process running on a 32-bit machine will be using nearly 3 Gbyte of address space.

Figure 5.3. Layout of virtual address space.

In FreeBSD and other modern UNIX systems that support the mmap system call, address-space usage is less structured. Shared library implementations may place text or data arbitrarily, rendering the notion of predefined regions obsolete. For compatibility, FreeBSD still supports the sbrk call that malloc () uses to provide a contiguous heap region, and the stack region is automatically grown to its size limit. By default, shared libraries are placed just below the run-time configured maximum stack area.

At any time, the currently executing process is mapped into the virtual address space. When the system decides to context switch to another process, it must save the information about the current-process address mapping, then load the address mapping for the new process to be run. The details of this address-map switching are architecture dependent. Some architectures need to change only a few memory-mapping registers that point to the base, and to give the length of memory-resident page tables. Other architectures store the page-table descriptors in special high-speed static RAM. Switching these maps may require dumping and reloading hundreds of map entries.

Both the kernel and user processes use the same basic data structures for the management of their virtual memory. The data structures used to manage virtual memory are as follows :

vmspace	Structure that encompasses both the machine-dependent and machine-independent structures describing a process's address space
vm_map	Highest-level data structure that describes the machine-independent virtual address space
vm_map_entry	Structure that describes a virtually contiguous range of addresses that share protection and inheritance attributes and that use the same backing-store object
object	Structure that describes a source of data for a range of addresses
shadow object	Special object that represents modified copy of original data
vm_page	The lowest -level data structure that represents the physical memory being used by the virtual-memory system

In the remainder of this section, we describe briefly how all these data structures fit together. The remainder of this chapter describes the details of the structures and how the structures are used.

Figure 5.4 shows a typical process address space and associated data structures. The vmspace structure encapsulates the virtual-memory state of a particular process, including the machine-dependent and machine-independent data structures, as well as statistics. The machine-dependent pmap structure is opaque to all but the lowest level of the system and contains all information necessary to manage the memory-management hardware. This pmap layer is the subject of Section 5.13 and is ignored for the remainder of the current discussion. The machine-independent data structures include the address space that is represented by a vm_map structure. The vm_map contains a linked list of vm_map_entry structures, hints for speeding up lookups during memory allocation and page-fault handling, and a pointer to the associated machine-dependent pmap structure contained in the vmspace. A vm_map_entry structure describes a virtually contiguous range of addresses that have the same protection and inheritance attributes. Every vm_map_entry points to a chain of vm_object structures that describes sources of data (objects) that are mapped at the indicated address range. At the tail of the chain is the original mapped data object, usually representing a persistent data source, such as a file. Interposed between that object and the map entry are one or more transient shadow objects that represent modified copies of the original data. These shadow objects are discussed in detail in Section 5.5.

Figure 5.4. Data structures that describe a process address space.

Each vm_object structure contains a linked list of vm_page structures representing the physical-memory cache of the object, as well as the type of and a pointer to the pager structure that contains information on how to page in or page out data from its backing store. There is a vm_page structure allocated for every page of physical memory managed by the virtual-memory system, where a page here may be a collection of multiple, contiguous hardware pages that will be treated by the machine-dependent layer as though they were a single unit. The structure also contains the status of the page (e.g., modified or referenced) and links for various paging queues. A vm_page structure is most commonly and quickly found through a global hash list that is keyed by the object and logical page within that object whose contents are held by the page.

All structures contain the necessary interlocks for multithreading in a multiprocessor environment. The locking is fine grained, with at least one lock per instance of a data structure. Many of the structures contain multiple locks to protect individual fields.