A kernel function gets dynamic memory in a fairly straightforward manner by invoking one of a variety of functions: __get_free_pages() or alloc_pages() to get pages from the zoned page frame allocator, kmem_cache_ alloc() or kmalloc() to use the slab allocator for specialized or general-purpose objects, and vmalloc() or vmalloc_32() to get a noncontiguous memory area. If the request can be satisfied, each of these functions returns a page descriptor address or a linear address identifying the beginning of the allocated dynamic memory area.

These simple approaches work for two reasons:

  • The kernel is the highest-priority component of the operating system.
  • The kernel trusts itself.

When allocating memory to User Mode processes, the situation is entirely different:

  • Process requests for dynamic memory are considered non-urgent.
  • Because user programs cannot be trusted, the kernel must be prepared to catch all addressing errors caused by processes in User Mode.

The kernel succeeds in deferring the allocation of dynamic memory to processes by using a new kind of resource. When a User Mode process asks for dynamic memory, it doesn’t get additional page frames; instead, it gets the right to use a new range of linear addresses, which become part of its address space. This interval is called a “memory region.”

1 The Process’s Address Space

The address space of a process consists of all linear addresses that the process is allowed to use.

The kernel represents intervals of linear addresses by means of resources called memory regions, which are characterized by an initial linear address, a length, and some access rights.

2 The Memory Descriptor

All information related to the process address space is included in an object called the memory descriptor of type mm_struct. This object is referenced by the mm field of the process descriptor.

2.1 Memory Descriptor of Kernel Threads

Contrary to regular processes, kernel threads do not use memory regions, therefore most of the fields of a memory descriptor are meaningless for them.

3 Memory Regions

Linux implements a memory region by means of an object of type vm_area_struct.

3.1 Memory Region Data Structures

3.2 Memory Region Access Rights

3.3 Memory Region Handling

  • Finding the closest region to a given address: find_vma()
  • Finding a region that overlaps a given interval: find_vma_intersection()
  • Finding a free interval: get_unmapped_area()
  • Inserting a region in the memory descriptor list: insert_vm_struct()

3.4 Allocating a Linear Address Interval

3.5 Releasing a Linear Address Interval

4 Page Fault Exception Handler

The Linux Page Fault exception handler must distinguish exceptions caused by programming errors from those caused by a reference to a page that legitimately belongs to the process address space but simply hasn’t been allocated yet.

4.1 Handling a Faulty Address Outside the Address Space

4.2 Handling a Faulty Address Inside the Address Space

4.3 Demand Paging

The term demand paging denotes a dynamic memory allocation technique that consists of deferring page frame allocation until the last possible moment—until the process attempts to address a page that is not present in RAM, thus causing a Page Fault exception.

4.4 Copy On Write

4.5 Handling Noncontiguous Memory Area Accesses

5 Creating and Deleting a Process Address Space

5.1 Creating a Process Address Space

5.2 Deleting a Process Address Space

6 Managing the Heap