VIRTUAL MEMORY STRUCTURES

Virtual Address Space (vas)

The vas represents the virtual address space of a process and serves as the head of a doubly linked list of process region data structures called pregions. The vas data structure is always memory resident.

When aprocess is invoked, the system allocates a vas structure and puts its address in p_vas, a field in the proc structure.

The virtual address space of a process is broken down into logical chunks of virtually contiguous pages. (See the Process Management white paper for table of vas entries.)

Virtual memory elements of a pregion

Each pregion represents a process's view of a particular portion of pages and information on getting to those pages. The pregion points to the region data structure that describes the pages' physical locations in memory or in secondary storage. The pregion also contains the virtual addresses to which the process's pages are mapped, the page usage (text, data, stack, and so forth), and page protections (read, write, execute, and so on).

Figure 1-14 Virtual memory elements of the pregion

The following elements of a per-process pregion structure are important to the virtual memory subsystem.

The Region, a system resource

The region is a system-wide kernel data structure that associates groups of pages with a given process. Regions can be one of two types, private (used by a single process) or shared (able to be used by more than one process). Space for a region data structure is allocated as needed. The region structure is never written to a swap device, although its B-tree may be.

Regions are pointed to by pregions, which are a per-process resource. Regions point to the vnode where the blocks of data reside when not in memory.

pseudo-vas for Text and Shared Library pregions

When a file is opened as an a.out or shared library, the easiest way to keep track of the region is to create a pseudo-vas the first time the file is opened as an executable. This is done by calling mapvnode() and storing the vas pointer in the vnode's v_vas element. On subsequent opens of the file as an executable, the non-NULL value in v_vas aids in finding the region to which the virtual address space is being attached.

The pseudo-vas is type PT_MMAP, and the associated pregion has PF_PSEUDO set in p_flags. This pregion is attached to the region for this vnode. All the processes that use this executable or shared library (non-pseudo pregions) then attach to the region with type PT_TEXT (a.out) or PT_MMAP (shared library). The number of processes using a particular vnode as an executable is kept in the pseudo-vas in va_refcnt.

All pregions associated with a region are connected with a doubly-linked list that begins with the region element r_pregs, and is defined in the pregions by p_prpnext and p_prpprev. The list is sorted by p_off, the pregion's offset into the region, and is NULL-terminated.

Even after all processes using the a.out or shared library exit, the handle to the region remains; its pages can be disposed of at that time.

Figure 1-15 Mapping the pseudo-vas structures

Chunks -- Keeping the vfds and dbds together in one place

Since information is typically needed about groups of (rather than individual) pages, pages are grouped into chunks. A chunk contains 32 pairs of virtual frame descriptors and disk block desciptors:

A one-to-one correspondence is maintained between vfd and dbd through the vfddbd structure, which simply contains one vfd (c_vfd) and one dbd (c_dbd).

Figure 1-16 A chunk contains 32 vfddbd (256 bytes)

HP-UX regions use chunks of vfds and dbds to keep track of page ownership:

Virtual Frame Descriptors (vfd)

A one-word structure called a virtual frame descriptor enables processes to reference pages of memory. The vfd is used when the process is in memory, and can be used to refer to the page of memory described in pfdat.

Figure 1-17 Virtual frame descriptor (vfd) contents

Table 1-12 Virtual Frame Descriptor (struct vfd)

Element	Meaning
pg_v	Valid flag. If set, this page of memory contains valid data and pg_pfnum is valid. If not set, the page's valid data is on a swap device.
pg_cw	Copy-on-write flag. If set, a write to the page causes a data protection fault, at which time the system copies the page.
pg_lock	Lock flag. If set, raw I/O is occurring on this page. Either the data is being transferred between the page and the disk, or data is being transferred between two memory pages. The kernel sleeps waiting for completion of I/O before launching further raw I/O to or from this page. Nothing can read the page while it is being written to disk.
pg_mlock	If set, the page is locked in memory and cannot be paged out.
pg_pfnum (aliased as pg_pfn)	Page frame number, from which can be accessed the correct pfdat entry for this page.

 

Disk Block Descriptor (dbd)

When the pg_v bit in a vfd is not set, the vfd is invalid and the page of data is not in memory but on disk. In this case, the disk block descriptor (dbd) gives valid reference to the data. Like the vfd structure, the dbd is one word long.

Figure 1-18 Contents of disk block descriptor (dbd)

Balanced Trees (B-Trees)

Each region contains either a single array of vfd/dbd (chunk) or a pointer to a B-tree. The structure called a B-tree allows for quick searches and efficient storage of sparse data. A bnode is the same size as a chunk; both can be gotten from the same source of memory. The region's B-tree stores pairs of page indices and chunk addresses. HP-UX uses an order 29 B-tree.

A B-tree is searched with a key and yields a value. In the region B-tree, the key is the page number in the region divided by 32, the number of vfddbds in a chunk.

Figure 1-19 A sample B-tree (order = 3, depth = 3)

Each node of a B-tree contains room for order+1 keys (or index numbers) and order+2 values. If a node grows to contain more than order keys, it is split into two nodes; half of the pairs are kept in the original node and the other half are copied to the new node. The B-tree node data also includes the number of valid elements contained in that node.

Root of the B-tree

A structure called struct broot points to the start of the B-tree.

Hardware-Independent Page Information table (pfdat)

The hardware independent layer of the virtual memory subsystem manages pages in memory, pages written to swap devices, and the movement of pages from one to the other. The act of moving data from physical memory to a swap device, or moving data from a swap device to physical memory, is called paging.

Basic to hardware independence is the page frame data table (pfdat), a big array indexed directly through the page number. Each page of available memory is represented by one pfdat structure; one pfdat entry represents each page frame writable to a swap device. HP-UX never pages kernel memory (the pages containing kernel text, stack, and data); thus, pfdat manages only the subset representing freely available physical memory. When the pfdat is initialized, all free pages are linked in a list pointed to by phead.