| .. _memory_management_api_demand_paging: |
| |
| 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 :c:func:`k_mem_page_in()` and :c:func:`k_mem_page_out()`. |
| :c:func:`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. :c:func:`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_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 |
| :kconfig:option:`CONFIG_DEMAND_PAGING_TIMING_HISTOGRAM_NUM_BINS` is enabled: |
| |
| * Overall statistics via :c:func:`k_mem_paging_stats_get()` |
| |
| * Per-thread statistics via :c:func:`k_mem_paging_thread_stats_get()` |
| if :kconfig:option:`CONFIG_DEMAND_PAGING_THREAD_STATS` is enabled |
| |
| * Execution time histogram can be obtained when |
| :kconfig:option:`CONFIG_DEMAND_PAGING_TIMING_HISTOGRAM` is enabled, and |
| :kconfig:option:`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 |
| :c:func:`k_mem_paging_histogram_eviction_get()` |
| |
| * Execution time histogram of backing store doing page-in via |
| :c:func:`k_mem_paging_histogram_backing_store_page_in_get()` |
| |
| * Execution time histogram of backing store doing page-out via |
| :c:func:`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: |
| |
| * :c:func:`k_mem_paging_eviction_init()` is called to initialize |
| the eviction algorithm. This is called at ``POST_KERNEL``. |
| |
| * :c:func:`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: |
| |
| * :c:func:`k_mem_paging_backing_store_init()` is called to |
| initialized the backing store at ``POST_KERNEL``. |
| |
| * :c:func:`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 |
| :c:func:`k_mem_paging_backing_store_page_out()` to perform actual |
| page out operation. |
| |
| * :c:func:`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. |
| |
| * :c:func:`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``. |
| |
| * :c:func:`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. |
| |
| * :c:func:`k_mem_paging_backing_store_page_finalize()` is invoked after |
| :c:func:`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. |
| :c:func:`k_mem_paging_backing_store_page_finalize()` can be an empty |
| function if so desired. |
| |
| API Reference |
| ************* |
| |
| .. doxygengroup:: mem-demand-paging |
| :project: Zephyr |
| |
| Eviction Algorithm APIs |
| ======================= |
| |
| .. doxygengroup:: mem-demand-paging-eviction |
| :project: Zephyr |
| |
| Backing Store APIs |
| ================== |
| |
| .. doxygengroup:: mem-demand-paging-backing-store |
| :project: Zephyr |