OS X VM Overview

The VM system used in OS X is a descendent of Mach VM, which was created at Carnegie Mellon University in the 1980s. To a large extent, the fundamental design is the same, although some of the details are different, particularly when enhancing the VM system. It does, however, support the ability to request certain paging behavior through the use of universal page lists (UPLs). See Universal Page Lists (UPLs) for more information.

The design of Mach VM centers around the concept of physical memory being a cache for virtual memory.

At its highest level, Mach VM consists of address spaces and ways to manipulate the contents of those address spaces from outside the space. These address spaces are sparse and have a notion of protections to limit what tasks can access their contents.

At a lower level, the object level, virtual memory is seen as a collection of VM objects and memory objects, each with a particular owner and protections. These objects can be modified with object calls that are available both to the task and (via the back end of the VM) to the pagers.

The VM object is internal to the virtual memory system, and includes basic information about accessing the memory. The memory object, by contrast, is provided by the pager. The contents of the memory associated with that memory object can be retrieved from disk or some other backing store by exchanging messages with the memory object. Implicitly, each VM object is associated with a given pager through its memory object.

VM objects are cached with system pages (RAM), which can be any power of two multiple of the hardware page size. In the OS X kernel, system pages are the same size as hardware pages. Each system page is represented in a given address space by a map entry. Each map entry has its own protection and inheritance. A given map entry can have an inheritance of shared, copy, or none. If a page is marked shared in a given map, child tasks share this page for reading and writing. If a page is marked copy, child tasks get a copy of this page (using copy-on-write). If a page is marked none, the child’s page is left unallocated.

VM objects are managed by the machine-independent VM system, with the underlying virtual to physical mappings handled by the machine-dependent pmap system. The pmap system actually handles page tables, translation lookaside buffers, segments, and so on, depending on the design of the underlying hardware.

When a VM object is duplicated (for example, the data pages from a process that has just called fork), a shadow object is created. A shadow object is initially empty, and contains a reference to another object. When the contents of a page are modified, the page is copied from the parent object into the shadow object and then modified. When reading data from a page, if that page exists in the shadow object, the page listed in the shadow object is used. If the shadow object has no copy of that page, the original object is consulted. A series of shadow objects pointing to shadow objects or original objects is known as a shadow chain.

Shadow chains can become arbitrarily long if an object is heavily reused in a copy-on-write fashion. However, since fork is frequently followed by exec, which replaces all of the material being shadowed, long chains are rare. Further, Mach automatically garbage collects shadow objects, removing any intermediate shadow objects whose pages are no longer referenced by any (nondefunct) shadow object. It is even possible for the original object to be released if it no longer contains pages that are relevant to the chain.

The VM calls available to an application include vm_map and vm_allocate, which can be used to map file data or anonymous memory into the address space. This is possible only because the address space is initially sparse. In general, an application can either map a file into its address space (through file mapping primitives, abstracted by BSD) or it can map an object (after being passed a handle to that object). In addition, a task can change the protections of the objects in its address space and can share those objects with other tasks.

In addition to the mapping and allocation aspects of virtual memory, the VM system contains a number of other subsystems. These include the back end (pagers) and the shared memory subsystem. There are also other subsystems closely tied to VM, including the VM shared memory server. These are described in Other VM and VM-Related Subsystems.

Memory Maps Explained

Each Mach task has its own memory map. In Mach, this memory map takes the form of an ordered doubly linked list. As described in OS X VM Overview, each of these objects contains a list of pages and shadow references to other objects.

In general, you should never need to access a memory map directly unless you are modifying something deep within the VM system. The vm_map_entry structure contains task-specific information about an individual mapping along with a reference to the backing object. In essence, it is the glue between an VM object and a VM map.

While the details of this data structure are beyond the scope of this document, a few fields are of particular importance.

The field is_submap is a Boolean value that tells whether this map entry is a normal VM object or a submap. A submap is a collection of mappings that is part of a larger map. Submaps are often used to group mappings together for the purpose of sharing them among multiple Mach tasks, but they may be used for many purposes. What makes a submap particularly powerful is that when several tasks have mapped a submap into their address space, they can see each other’s changes, not only to the contents of the objects in the map, but to the objects themselves. This means that as additional objects are added to or deleted from the submap, they appear in or disappear from the address spaces of all tasks that share that submap.

The field behavior controls the paging reference behavior of a specified range in a given map. This value changes how pageins are clustered. Possible values are VM_BEHAVIOR_DEFAULT, VM_BEHAVIOR_RANDOM, VM_BEHAVIOR_SEQUENTIAL, and VM_BEHAVIOR_RSEQNTL, for default, random, sequential, or reverse-sequential pagein ordering.

The protection and max_protection fields control the permissions on the object. The protection field indicates what rights the task currently has for the object, while the max_protection field contains the maximum access that the current task can obtain for the object.

You might use the protection field when debugging shared memory. By setting the protection to be read-only, any inadvertent writes to the shared memory would cause an exception. However, when the task actually needs to write to that shared region, it could increase its permissions in the protection field to allow writes.

It would be a security hole if a task could increase its own permissions on a memory object arbitrarily, however. In order to preserve a reasonable security model, the task that owns a memory object must be able to limit the rights granted to a subordinate task. For this reason, a task is not allowed to increase its protection beyond the permissions granted in max_protection.

Possible values for protection and max_protection are described in detail in xnu/osfmk/mach/vm_prot.h.

Finally, the use_pmap field indicates whether a submap’s low-level mappings should be shared among all tasks into which the submap is mapped. If the mappings are not shared, then the structure of the map is shared among all tasks, but the actual contents of the pages are not.

For example, shared libraries are handled with two submaps. The read-only shared code section has use_pmap set to true. The read-write (nonshared) section has use_pmap set to false, forcing a clean copy of the library’s DATA segment to be mapped in from disk for each new task.

Named Entries

The OS X VM system provides an abstraction known as a named entry. A named entry is nothing more than a handle to a shared object or a submap.

Shared memory support in OS X is achieved by sharing objects between the memory maps of various tasks. Shared memory objects must be created from existing VM objects by calling vm_allocate to allocate memory in your address space and then calling mach_make_memory_entry_64 to get a handle to the underlying VM object.

The handle returned by mach_make_memory_entry_64 can be passed to vm_map to map that object into a given task’s address space. The handle can also be passed via IPC or other means to other tasks so that they can map it into their address spaces. This provides the ability to share objects with tasks that are not in your direct lineage, and also allows you to share additional memory with tasks in your direct lineage after those tasks are created.

The other form of named entry, the submap, is used to group a set of mappings. The most common use of a submap is to share mappings among multiple Mach tasks. A submap can be created with vm_region_object_create.

What makes a submap particularly powerful is that when several tasks have mapped a submap into their address space, they can see each other’s changes to both the data and the structure of the map. This means that one task can map or unmap a VM object in another task’s address space simply by mapping or unmapping that object in the submap.

Universal Page Lists (UPLs)

A universal page list, or UPL, is a data structure used when communicating with the virtual memory system. UPLs can be used to change the behavior of pages with respect to caching, permissions, mapping, and so on. UPLs can also be used to push data into and pull data from VM objects. The term is also often used to refer to the family of routines that operate on UPLs. The flags used when dealing with UPLs are described in osfmk/mach/memory_object_types.h.

The life cycle of a UPL looks like this:

1. A UPL is created based on the contents of a VM object. This UPL includes information about the pages within that object.

2. That UPL is modified in some way.

3. The changes to the UPL are either committed (pushed back to the VM system) or aborted, with ubc_upl_commit or ubc_upl_abort, respectively.

If you have a control handle for a given VM object (which generally means that you are inside a pager), you can use vm_object_upl_request to get a UPL for that object. Otherwise, you must use the vm_map_get_upl call. In either case, you are left with a handle to the UPL.

When a pagein is requested, the pager receives a list of pages that are locked against the object, with certain pages set to not valid. The pager must either write data into those pages or must abort the transaction to prevent invalid data in the kernel. Similarly in pageout, the kernel must write the data to a backing store or abort the transaction to prevent data loss. The pager may also elect to bring additional pages into memory or throw additional pages out of memory at its discretion.

Because pagers can be used both for virtual memory and for memory mapping of file data, when a pageout is requested, the data may need to be freed from memory, or it may be desirable to keep it there and simply flush the changes to disk. For this reason, the flag UPL_CLEAN_IN_PLACE exists to allow a page to be flushed to disk but not removed from memory.

When a pager decides to page in or out additional pages, it must determine which pages to move. A pager can request all of the dirty pages by setting the RETURN_ONLY_DIRTY flag. It can also request all pages that are not in memory using the RETURN_ONLY_ABSENT flag.

There is a slight problem, however. If a given page is marked as BUSY in the UPL, a request for information on that page would normally block. If the pager is doing prefetching or preflushing, this is not desirable, since it might be blocking on itself or on some other pager that is blocked waiting for the current transaction to complete. To avoid such deadlock, the UPL mechanism provides the UPL_NOBLOCK flag. This is frequently used in the anonymous pager for requesting free memory.

The flag QUERY_OBJECT_TYPE can be used to determine if an object is physically contiguous and to get other properties of the underlying object.

The flag UPL_PRECIOUS means that there should be only one copy of the data. This prevents having a copy both in memory and in the backing store. However, this breaks the adjacency of adjacent pages in the backing store, and is thus generally not used to avoid a performance hit.

The flag SET_INTERNAL is used by the BSD subsystem to cause all information about a UPL to be contained in a single memory object so that it can be passed around more easily. It can only be used if your code is running in the kernel’s address space.

Since this handle can be used for multiple small transactions (for example, when mapping a file into memory block-by-block), the UPL API includes functions for committing and aborting changes to only a portion of the UPL. These functions are upl_commit_range and upl_abort_range, respectively.

To aid in the use of UPLs for handling multi-part transactions, the upl_commit_range and upl_abort_range calls have a flag that causes the UPL to be freed when there are no unmodified pages in the UPL. If you use this flag, you must be very careful not to use the UPL after all ranges have been committed or aborted.

Finally, the function vm_map_get_upl is frequently used in file systems. It gets the underlying VM object associated with a given range within an address space. Since this returns only the first object in that range, it is your responsibility to determine whether the entire range is covered by the resulting UPL and, if not, to make additional calls to get UPLs for other objects. Note that while the vm_map_get_upl call is against an address space range, most UPL calls are against a vm_object.

Using Mach Memory Maps

From the context of the kernel (not from a KEXT), there are two maps that you will probably need to deal with. The first is the kernel map. Since your code is executing in the kernel’s address space, no additional effort is needed to use memory referenced in the kernel map. However, you may need to add additional mappings into the kernel map and remove them when they are no longer needed.

The second map of interest is the memory map for a given task. This is of most interest for code that accepts input from user programs, for example a sysctl or a Mach RPC handler. In nearly all cases, convenient wrappers provide the needed functionality, however.

Most of these functions are based around the vm_offset_t type, which is a pointer-sized integer. In effect, you can think of them as pointers, with the caveat that they are not necessarily pointers to data in the kernel’s address space, depending on usage.

The low-level VM map API includes the following functions:

kern_return_t vm_map_copyin(vm_map_t src_map, vm_offset_t src_addr,

            vm_size_t len, boolean_t src_destroy,

            vm_map_copy_t *copy_result);

kern_return_t vm_map_copyout(vm_map_t map, vm_offset_t *addr, /*  Out */

            register vm_map_copy_t copy);

kern_return_t vm_map_copy_overwrite(vm_map_t dst_map,

            vm_offset_t dst_address,vm_map_copy_t copy,

            boolean_t interruptible, pmap_t pmap);

void vm_map_copy_discard(vm_map_copy_t copy);

void vm_map_wire(vm_map_t map, vm_offset_t start, vm_offset_t end,

            vm_prot_t access_type, boolean_t user_wire);

void vm_map_unwire(vm_map_t map, vm_offset_t start, vm_offset_t  end,

            boolean_t user_wire);

The function vm_map_copyin copies data from an arbitrary (potentially non–kernel) memory map into a copy list and returns the copy list pointer in copy_result. If something goes wrong and you need to throw away this intermediate object, it should be freed with vm_map_copy_discard.

In order to actually get the data from the copy list, you need to overwrite a memory object in the kernel’s address space with vm_map_copy_overwrite. This overwrites an object with the contents of a copy list. For most purposes, the value passed for interruptible should be FALSE, and pmap should be NULL.

Copying data from the kernel to user space is exactly the same as copying data from user space, except that you pass kernel_map to vm_map_copyin and pass the user map to vm_map_copy_overwrite. In general, however, you should avoid doing this, since you could end up with a task’s memory being fragmented into lots of tiny objects, which is undesirable.

Do not use vm_map_copyout when copying data into an existing user task’s address map. The function vm_map_copyout is used for filling an unused region in an address map. If the region is allocated, then vm_map_copyout does nothing. Because it requires knowledge of the current state of the map, it is primarily used when creating a new address map (for example, if you are manually creating a new process). For most purposes, you do not need to use vm_map_copyout.

The functions vm_map_wire and vm_map_unwire can be used to wire and unwire portions of an address map. If you set the argument user_wire to TRUE, then the page can be unwired from user space. This should be set to FALSE if you are about to use the memory for I/O or for some other operation that cannot tolerate paging. In vm_map_wire, the argument access_type indicates the types of accesses that should not be allowed to generate a page fault. In general, however, you should be using vm_wire to wire memory.

As mentioned earlier, this information is presented strictly for use in the heart of the kernel. You cannot use anything in this section from a kernel extension.

Other VM and VM-Related Subsystems

There are two additional VM subsystems: pagers and the working set detection subsystem. In addition, the VM shared memory server subsystem is closely tied to (but is not part of) the VM subsystem. This section describes these three VM and VM-related subsystems.

Address Spaces

This section explains issues that some developers may see when using their drivers in Panther or later. These changes were necessitated by a combination of hardware and underlying OS changes; however, you may see problems resulting from the changes even on existing hardware.

There are three basic areas of change in OS X v10.3. These are:

• IOMemoryDescriptor changes

• VM system (pmap) changes

• Kernel dependency changes

These are described in detail in the sections that follow.

Allocating Memory in the Kernel

As with most things in the OS X kernel, there are a number of ways to allocate memory. The choice of routines depends both on the location of the calling routine and on the reason for allocating memory. In general, you should use Mach routines for allocating memory unless you are writing code for use in the I/O Kit, in which case you should use I/O Kit routines.

#include <libkern/OSMalloc.h>

#define MYTAGNAME "com.apple.mytag"

...

OSMallocTag mytag = OSMalloc_Tagalloc(MYTAGNAME, OSMT_DEFAULT);

void *datablock = OSMalloc(PAGE_SIZE_64, mytag);

...

OSFree(datablock, PAGE_SIZE_64, mytag);

void *IOMalloc(vm_size_t size);

void *IOMallocAligned(vm_size_t size, vm_size_t alignment);

void *IOMallocContiguous(vm_size_t size, vm_size_t alignment,

            IOPhysicalAddress *physicalAddress);

void *IOMallocPageable(vm_size_t size, vm_size_t alignment);

void IOFree(void *address, vm_size_t size);

void IOFreeAligned(void *address, vm_size_t size);

void IOFreeContiguous(void *address, vm_size_t size);

void IOFreePageable(void *address, vm_size_t size);

kern_return_t kmem_alloc(vm_map_t map, vm_offset_t *addrp, vm_size_t  size);

void kmem_free(vm_map_t map, vm_offset_t addr, vm_size_t size);

kern_return_t mem_alloc_aligned(vm_map_t map, vm_offset_t *addrp,

            vm_size_t size);

kern_return_t kmem_alloc_wired(vm_map_t map, vm_offset_t *addrp,

            vm_size_t size);

kern_return_t kmem_alloc_pageable(vm_map_t map, vm_offset_t *addrp,

            vm_size_t size);

kern_return_t kmem_alloc_contig(vm_map_t map, vm_offset_t *addrp,

            vm_size_t size, vm_offset_t mask, int flags);