Demand Paging

Demand paging provides a mechanism where data is only brought into physical memory as required by current execution context. The physical memory is conceptually divided in page-sized page frames as regions to hold data.

When the processor tries to access data and the data page exists in one of the page frames, the execution continues without any interruptions.
When the processor tries to access the data page that does not exist in any page frames, a page fault occurs. The paging code then brings in the corresponding data page from backing store into physical memory if there is a free page frame. If there is no more free page frames, the eviction algorithm is invoked to select a data page to be paged out, thus freeing up a page frame for new data to be paged in. If this data page has been modified after it is first paged in, the data will be written back into the backing store. If no modifications is done or after written back into backing store, the data page is now considered paged out and the corresponding page frame is now free. The paging code then invokes the backing store to page in the data page corresponding to the location of the requested data. The backing store copies that data page into the free page frame. Now the data page is in physical memory and execution can continue.

There are functions where paging in and out can be invoked manually using k_mem_page_in() and k_mem_page_out(). k_mem_page_in() can be used to page in data pages in anticipation that they are required in the near future. This is used to minimize number of page faults as these data pages are already in physical memory, and thus minimizing latency. k_mem_page_out() can be used to page out data pages where they are not going to be accessed for a considerable amount of time. This frees up page frames so that the next page in can be executed faster as the paging code does not need to invoke the eviction algorithm.

Terminology

Data Page

A data page is a page-sized region of data. It may exist in a page frame, or be paged out to some backing store. Its location can always be looked up in the CPU’s page tables (or equivalent) by virtual address. The data type will always be void * or in some cases uint8_t * when doing pointer arithmetic.

Page Frame

A page frame is a page-sized physical memory region in RAM. It is a container where a data page may be placed. It is always referred to by physical address. Zephyr has a convention of using uintptr_t for physical addresses. For every page frame, a struct z_page_frame is instantiated to store metadata. Flags for each page frame:

Z_PAGE_FRAME_FREE indicates a page frame is unused and on the list of free page frames. When this flag is set, none of the other flags are meaningful and they must not be modified.
Z_PAGE_FRAME_PINNED indicates a page frame is pinned in memory and should never be paged out.
Z_PAGE_FRAME_RESERVED indicates a physical page reserved by hardware and should not be used at all.
Z_PAGE_FRAME_MAPPED is set when a physical page is mapped to virtual memory address.
Z_PAGE_FRAME_BUSY indicates a page frame is currently involved in a page-in/out operation.
Z_PAGE_FRAME_BACKED indicates a page frame has a clean copy in the backing store.

Z_SCRATCH_PAGE

The virtual address of a special page provided to the backing store to: * Copy a data page from Z_SCRATCH_PAGE to the specified location; or, * Copy a data page from the provided location to Z_SCRATCH_PAGE. This is used as an intermediate page for page in/out operations. This scratch needs to be mapped read/write for backing store code to access. However the data page itself may only be mapped as read-only in virtual address space. If this page is provided as-is to backing store, the data page must be re-mapped as read/write which has security implications as the data page is no longer read-only to other parts of the application.

Paging Statistics

Paging statistics can be obtained via various function calls when CONFIG_DEMAND_PAGING_TIMING_HISTOGRAM_NUM_BINS is enabled:

Overall statistics via k_mem_paging_stats_get()
Per-thread statistics via k_mem_paging_thread_stats_get() if CONFIG_DEMAND_PAGING_THREAD_STATS is enabled
Execution time histogram can be obtained when CONFIG_DEMAND_PAGING_TIMING_HISTOGRAM is enabled, and CONFIG_DEMAND_PAGING_TIMING_HISTOGRAM_NUM_BINS is defined. Note that the timing is highly dependent on the architecture, SoC or board. It is highly recommended that k_mem_paging_eviction_histogram_bounds[] and k_mem_paging_backing_store_histogram_bounds[] be defined for a particular application.
- Execution time histogram of eviction algorithm via k_mem_paging_histogram_eviction_get()
- Execution time histogram of backing store doing page-in via k_mem_paging_histogram_backing_store_page_in_get()
- Execution time histogram of backing store doing page-out via k_mem_paging_histogram_backing_store_page_out_get()

Eviction Algorithm

The eviction algorithm is used to determine which data page and its corresponding page frame can be paged out to free up a page frame for the next page in operation. There are two functions which are called from the kernel paging code:

k_mem_paging_eviction_init() is called to initialize the eviction algorithm. This is called at POST_KERNEL.
k_mem_paging_eviction_select() is called to select a data page to evict. A function argument dirty is written to signal the caller whether the selected data page has been modified since it is first paged in. If the dirty bit is returned as set, the paging code signals to the backing store to write the data page back into storage (thus updating its content). The function returns a pointer to the page frame corresponding to the selected data page.

Currently, a NRU (Not-Recently-Used) eviction algorithm has been implemented as a sample. This is a very simple algorithm which ranks each data page on whether they have been accessed and modified. The selection is based on this ranking.

To implement a new eviction algorithm, the two functions mentioned above must be implemented.

Backing Store

Backing store is responsible for paging in/out data page between their corresponding page frames and storage. These are the functions which must be implemented:

k_mem_paging_backing_store_init() is called to initialized the backing store at POST_KERNEL.
k_mem_paging_backing_store_location_get() is called to reserve a backing store location so a data page can be paged out. This location token is passed to k_mem_paging_backing_store_page_out() to perform actual page out operation.
k_mem_paging_backing_store_location_free() is called to free a backing store location (the location token) which can then be used for subsequent page out operation.
k_mem_paging_backing_store_page_in() copies a data page from the backing store location associated with the provided location token to the page pointed by Z_SCRATCH_PAGE.
k_mem_paging_backing_store_page_out() copies a data page from Z_SCRATCH_PAGE to the backing store location associated with the provided location token.
k_mem_paging_backing_store_page_finalize() is invoked after k_mem_paging_backing_store_page_in() so that the page frame struct may be updated for internal accounting. This can be a no-op.

To implement a new backing store, the functions mentioned above must be implemented. k_mem_paging_backing_store_page_finalize() can be an empty function if so desired.

API Reference

Demand Paging APIs

Eviction Algorithm APIs

Eviction Algorithm APIs

Backing Store APIs

Backing Store APIs