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 k_mem_page_frame is instantiated to store metadata. Flags for each page frame:

  • K_MEM_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.

  • K_MEM_PAGE_FRAME_PINNED indicates a page frame is pinned in memory and should never be paged out.

  • K_MEM_PAGE_FRAME_RESERVED indicates a physical page reserved by hardware and should not be used at all.

  • K_MEM_PAGE_FRAME_MAPPED is set when a physical page is mapped to virtual memory address.

  • K_MEM_PAGE_FRAME_BUSY indicates a page frame is currently involved in a page-in/out operation.

  • K_MEM_PAGE_FRAME_BACKED indicates a page frame has a clean copy in the backing store.

K_MEM_SCRATCH_PAGE

The virtual address of a special page provided to the backing store to: * Copy a data page from k_MEM_SCRATCH_PAGE to the specified location; or, * Copy a data page from the provided location to K_MEM_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:

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:

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

group mem-demand-paging

Functions

int k_mem_page_out(void *addr, size_t size)

Evict a page-aligned virtual memory region to the backing store.

Useful if it is known that a memory region will not be used for some time. All the data pages within the specified region will be evicted to the backing store if they weren’t already, with their associated page frames marked as available for mappings or page-ins.

None of the associated page frames mapped to the provided region should be pinned.

Note that there are no guarantees how long these pages will be evicted, they could take page faults immediately.

If CONFIG_DEMAND_PAGING_ALLOW_IRQ is enabled, this function may not be called by ISRs as the backing store may be in-use.

Parameters:

  • addr – Base page-aligned virtual address

  • size – Page-aligned data region size

Return values:

  • 0 – Success

  • -ENOMEM – Insufficient space in backing store to satisfy request. The region may be partially paged out.

void k_mem_page_in(void *addr, size_t size)

Load a virtual data region into memory.

After the function completes, all the page frames associated with this function will be paged in. However, they are not guaranteed to stay there. This is useful if the region is known to be used soon.

If CONFIG_DEMAND_PAGING_ALLOW_IRQ is enabled, this function may not be called by ISRs as the backing store may be in-use.

Parameters:

  • addr – Base page-aligned virtual address

  • size – Page-aligned data region size

void k_mem_pin(void *addr, size_t size)

Pin an aligned virtual data region, paging in as necessary.

After the function completes, all the page frames associated with this region will be resident in memory and pinned such that they stay that way. This is a stronger version of z_mem_page_in().

If CONFIG_DEMAND_PAGING_ALLOW_IRQ is enabled, this function may not be called by ISRs as the backing store may be in-use.

Parameters:

  • addr – Base page-aligned virtual address

  • size – Page-aligned data region size

void k_mem_unpin(void *addr, size_t size)

Un-pin an aligned virtual data region.

After the function completes, all the page frames associated with this region will be no longer marked as pinned. This does not evict the region, follow this with z_mem_page_out() if you need that.

Parameters:

  • addr – Base page-aligned virtual address

  • size – Page-aligned data region size

void k_mem_paging_stats_get(struct k_mem_paging_stats_t *stats)

Get the paging statistics since system startup.

This populates the paging statistics struct being passed in as argument.

Parameters:

  • stats – [inout] Paging statistics struct to be filled.

void k_mem_paging_thread_stats_get(struct k_thread *thread, struct k_mem_paging_stats_t *stats)

Get the paging statistics since system startup for a thread.

This populates the paging statistics struct being passed in as argument for a particular thread.

Parameters:

  • thread – [in] Thread

  • stats – [inout] Paging statistics struct to be filled.

void k_mem_paging_histogram_eviction_get(struct k_mem_paging_histogram_t *hist)

Get the eviction timing histogram.

This populates the timing histogram struct being passed in as argument.

Parameters:

  • hist – [inout] Timing histogram struct to be filled.

void k_mem_paging_histogram_backing_store_page_in_get(struct k_mem_paging_histogram_t *hist)

Get the backing store page-in timing histogram.

This populates the timing histogram struct being passed in as argument.

Parameters:

  • hist – [inout] Timing histogram struct to be filled.

void k_mem_paging_histogram_backing_store_page_out_get(struct k_mem_paging_histogram_t *hist)

Get the backing store page-out timing histogram.

This populates the timing histogram struct being passed in as argument.

Parameters:

  • hist – [inout] Timing histogram struct to be filled.

struct k_mem_paging_stats_t
#include <demand_paging.h>

Paging Statistics.

Public Members

unsigned long cnt

Number of page faults.

unsigned long irq_locked

Number of page faults with IRQ locked.

unsigned long irq_unlocked

Number of page faults with IRQ unlocked.

unsigned long in_isr

Number of page faults while in ISR.

unsigned long clean

Number of clean pages selected for eviction.

unsigned long dirty

Number of dirty pages selected for eviction.

struct k_mem_paging_histogram_t
#include <demand_paging.h>

Paging Statistics Histograms.

Eviction Algorithm APIs

group mem-demand-paging-eviction

Eviction algorithm APIs.

Functions

void k_mem_paging_eviction_add(struct k_mem_page_frame *pf)

Submit a page frame for eviction candidate tracking.

The kernel will invoke this to tell the eviction algorithm the provided page frame may be considered as a potential eviction candidate.

This function will never be called before the initial k_mem_paging_eviction_init().

This function is invoked with interrupts locked.

Parameters:

  • pf – [in] The page frame to add

void k_mem_paging_eviction_remove(struct k_mem_page_frame *pf)

Remove a page frame from potential eviction candidates.

The kernel will invoke this to tell the eviction algorithm the provided page frame may no longer be considered as a potential eviction candidate.

This function will only be called with page frames that were submitted using k_mem_paging_eviction_add() beforehand.

This function is invoked with interrupts locked.

Parameters:

  • pf – [in] The page frame to remove

void k_mem_paging_eviction_accessed(uintptr_t phys)

Process a page frame as being newly accessed.

The architecture-specific memory fault handler will invoke this to tell the eviction algorithm the provided physical address belongs to a page frame being accessed and such page frame should become unlikely to be considered as the next eviction candidate.

This function is invoked with interrupts locked.

Parameters:

  • phys – [in] The physical address being accessed

struct k_mem_page_frame *k_mem_paging_eviction_select(bool *dirty)

Select a page frame for eviction.

The kernel will invoke this to choose a page frame to evict if there are no free page frames. It is not guaranteed that the returned page frame will actually be evicted. If it is then the kernel will call k_mem_paging_eviction_remove() with it.

This function will never be called before the initial k_mem_paging_eviction_init().

This function is invoked with interrupts locked.

Parameters:

  • dirty – [out] Whether the page to evict is dirty

Returns:

The page frame to evict

void k_mem_paging_eviction_init(void)

Initialization function.

Called at POST_KERNEL to perform any necessary initialization tasks for the eviction algorithm. k_mem_paging_eviction_select() is guaranteed to never be called until this has returned, and this will only be called once.

Backing Store APIs

group mem-demand-paging-backing-store

Backing store APIs.

Functions

int k_mem_paging_backing_store_location_get(struct k_mem_page_frame *pf, uintptr_t *location, bool page_fault)

Reserve or fetch a storage location for a data page loaded into a page frame.

The returned location token must be unique to the mapped virtual address. This location will be used in the backing store to page out data page contents for later retrieval. The location value must be page-aligned.

This function may be called multiple times on the same data page. If its page frame has its K_MEM_PAGE_FRAME_BACKED bit set, it is expected to return the previous backing store location for the data page containing a cached clean copy. This clean copy may be updated on page-out, or used to discard clean pages without needing to write out their contents.

If the backing store is full, some other backing store location which caches a loaded data page may be selected, in which case its associated page frame will have the K_MEM_PAGE_FRAME_BACKED bit cleared (as it is no longer cached).

k_mem_page_frame_to_virt(pf) will indicate the virtual address the page is currently mapped to. Large, sparse backing stores which can contain the entire address space may simply generate location tokens purely as a function of that virtual address with no other management necessary.

This function distinguishes whether it was called on behalf of a page fault. A free backing store location must always be reserved in order for page faults to succeed. If the page_fault parameter is not set, this function should return -ENOMEM even if one location is available.

This function is invoked with interrupts locked.

Parameters:

  • pf – Virtual address to obtain a storage location

  • location – [out] storage location token

  • page_fault – Whether this request was for a page fault

Returns:

0 Success

Returns:

-ENOMEM Backing store is full

void k_mem_paging_backing_store_location_free(uintptr_t location)

Free a backing store location.

Any stored data may be discarded, and the location token associated with this address may be re-used for some other data page.

This function is invoked with interrupts locked.

Parameters:

  • location – Location token to free

void k_mem_paging_backing_store_page_out(uintptr_t location)

Copy a data page from K_MEM_SCRATCH_PAGE to the specified location.

Immediately before this is called, K_MEM_SCRATCH_PAGE will be mapped read-write to the intended source page frame for the calling context.

Calls to this and k_mem_paging_backing_store_page_in() will always be serialized, but interrupts may be enabled.

Parameters:

  • location – Location token for the data page, for later retrieval

void k_mem_paging_backing_store_page_in(uintptr_t location)

Copy a data page from the provided location to K_MEM_SCRATCH_PAGE.

Immediately before this is called, K_MEM_SCRATCH_PAGE will be mapped read-write to the intended destination page frame for the calling context.

Calls to this and k_mem_paging_backing_store_page_out() will always be serialized, but interrupts may be enabled.

Parameters:

  • location – Location token for the data page

void k_mem_paging_backing_store_page_finalize(struct k_mem_page_frame *pf, uintptr_t location)

Update internal accounting after a page-in.

This is invoked after k_mem_paging_backing_store_page_in() and interrupts have been* re-locked, making it safe to access the k_mem_page_frame data. The location value will be the same passed to k_mem_paging_backing_store_page_in().

The primary use-case for this is to update custom fields for the backing store in the page frame, to reflect where the data should be evicted to if it is paged out again. This may be a no-op in some implementations.

If the backing store caches paged-in data pages, this is the appropriate time to set the K_MEM_PAGE_FRAME_BACKED bit. The kernel only skips paging out clean data pages if they are noted as clean in the page tables and the K_MEM_PAGE_FRAME_BACKED bit is set in their associated page frame.

Parameters:

  • pf – Page frame that was loaded in

  • location – Location of where the loaded data page was retrieved

void k_mem_paging_backing_store_init(void)

Backing store initialization function.

The implementation may expect to receive page in/out calls as soon as this returns, but not before that. Called at POST_KERNEL.

This function is expected to do two things:

  • Initialize any internal data structures and accounting for the backing store.

  • If the backing store already contains all or some loaded kernel data pages at boot time, K_MEM_PAGE_FRAME_BACKED should be appropriately set for their associated page frames, and any internal accounting set up appropriately.