kernel/memory_management/demand_paging.html · kernel/memory_management/demand_paging.rst 공식 원문 ↗

Zephyr 3.7.0 · Kernel · Memory Management

Demand Paging

실행에 필요한 data page만 RAM frame에 올리고, 부족할 때 eviction과 backing store를 통해 physical memory를 재사용합니다.

Official pathkernel/memory_management/demand_paging.html
Source filekernel/memory_management/demand_paging.rst
Source versionZephyr 3.7.0
TranslationFull · reviewed

본문 기준: Zephyr 3.7.0 LTS3 · 이후 유지보수 패치는 별도입니다.

Part 1

요약·해설

Page table은 virtual data page의 위치를 추적하고, page frame metadata와 eviction algorithm·backing store가 resident/dirty/backed 상태를 관리합니다.

Data page

virtual identity

Page frame

physical container

Backing store

location token

Part 2

접을 수 있는 영어 원문 전체

영어 원문 전체 펼치기
원문 SHA-256 5D6A9F19656EA62C9D69B5B9981D815069A9A5836D0D971D4B430C140E8CB79C 
.. _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 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
: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 ``K_MEM_SCRATCH_PAGE``.

* :c:func:`k_mem_paging_backing_store_page_out()` copies a data page
  from ``K_MEM_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

Part 3

한국어 전문 번역

Demand paging은 현재 execution context가 요구할 때만 data를 physical memory로 가져오는 방식입니다. Physical memory는 data를 담는 page-sized page frame으로 개념적으로 나뉩니다.

  • Processor가 접근한 data page가 page frame에 있으면 중단 없이 실행을 계속합니다.
  • 어느 frame에도 없으면 page fault가 발생합니다. Free frame이 있으면 backing store에서 page를 가져오고, 없으면 eviction algorithm이 내보낼 page를 골라 frame을 비웁니다. 수정된 dirty page는 backing store에 먼저 쓰고, clean page 또는 write-back 완료 page는 paged out으로 간주합니다. Backing store가 요청 page를 free frame에 복사하면 실행을 계속합니다.

k_mem_page_in()은 가까운 미래에 쓸 page를 미리 불러 page fault 수와 latency를 줄입니다. k_mem_page_out()은 오랫동안 접근하지 않을 page를 미리 내보내 다음 page-in에서 eviction algorithm을 호출할 필요를 줄입니다.

용어

Data Page: Page 크기의 data 영역입니다. Page frame에 있거나 backing store로 나가 있을 수 있으며 CPU page table 또는 동등한 구조에서 virtual address로 위치를 찾습니다. Pointer arithmetic에는 void * 또는 uint8_t *를 사용합니다.

Page Frame: RAM의 page-sized physical memory 영역으로 data page를 담는 container입니다. 항상 physical address로 부르고 Zephyr는 physical address에 uintptr_t를 사용합니다. Frame마다 metadata용 struct k_mem_page_frame instance가 있습니다.

  • K_MEM_PAGE_FRAME_FREE: 사용하지 않아 free list에 있습니다. 이 flag가 설정되면 다른 flag는 의미가 없고 수정하면 안 됩니다.
  • K_MEM_PAGE_FRAME_PINNED: Memory에 고정되어 page-out하면 안 됩니다.
  • K_MEM_PAGE_FRAME_RESERVED: Hardware가 예약해 전혀 사용하면 안 되는 physical page입니다.
  • K_MEM_PAGE_FRAME_MAPPED: Physical page가 virtual address에 map되어 있습니다.
  • K_MEM_PAGE_FRAME_BUSY: Page-in/out operation에 참여 중입니다.
  • K_MEM_PAGE_FRAME_BACKED: Backing store에 clean copy가 있습니다.

K_MEM_SCRATCH_PAGE: Backing store가 page-in/out 중간 page로 쓰는 특별한 virtual address입니다. 원문 첫 bullet에는 k_MEM_SCRATCH_PAGE로 표기되지만 나머지 문서와 API의 symbol은 K_MEM_SCRATCH_PAGE입니다. Scratch page는 read-write로 map해야 합니다. 원래 read-only인 data page 자체를 store에 직접 넘겨 read-write로 remap하면 application의 다른 부분에도 쓰기 가능해지는 security implication이 있으므로 중간 mapping을 사용합니다.

Paging 통계

CONFIG_DEMAND_PAGING_TIMING_HISTOGRAM_NUM_BINS가 활성화되면 여러 함수로 paging 통계를 얻습니다. k_mem_paging_stats_get()은 전체 통계, CONFIG_DEMAND_PAGING_THREAD_STATS가 켜지면 k_mem_paging_thread_stats_get()은 thread별 통계를 제공합니다.

CONFIG_DEMAND_PAGING_TIMING_HISTOGRAM과 bin 수가 정의되면 실행 시간 histogram도 얻습니다. Timing은 architecture, SoC, board에 크게 의존하므로 application별 k_mem_paging_eviction_histogram_bounds[]와 k_mem_paging_backing_store_histogram_bounds[] 정의를 권장합니다.

  • k_mem_paging_histogram_eviction_get(): eviction algorithm 시간
  • k_mem_paging_histogram_backing_store_page_in_get(): backing store page-in 시간
  • k_mem_paging_histogram_backing_store_page_out_get(): backing store page-out 시간

Eviction Algorithm

Eviction algorithm은 다음 page-in을 위해 어느 data page와 frame을 내보낼지 결정합니다. Kernel paging code는 POST_KERNEL에 k_mem_paging_eviction_init()을 호출하고, 필요할 때 k_mem_paging_eviction_select()을 호출합니다.

Select의 dirty output은 page가 처음 들어온 뒤 수정됐는지 알립니다. Dirty이면 backing store에 write-back해 내용을 갱신해야 하며 함수는 선택한 page frame pointer를 반환합니다.

현재 sample은 NRU(Not-Recently-Used) algorithm입니다. 각 page의 access·modified 여부로 순위를 정해 선택하는 단순 방식입니다. 새 algorithm은 init과 select를 포함한 아래 계약을 구현해야 합니다.

Backing Store

Backing store는 storage와 page frame 사이에서 data page를 page-in/out합니다. POST_KERNEL에 init하고, location_get으로 page-out location token을 예약하며, location_free로 token을 반환합니다.

page_in은 location에서 K_MEM_SCRATCH_PAGE로, page_out은 scratch page에서 location으로 복사합니다. page_finalize는 page-in 뒤 page frame accounting을 갱신하며 구현에 따라 no-op일 수 있습니다. 새 backing store는 아래 함수들을 구현해야 합니다.

API 참고

mem-demand-paging group은 manual page-in/out, pinning, 통계와 histogram API를 제공합니다.

int k_mem_page_out(void *addr, size_t size)

Page-aligned virtual memory 영역을 backing store로 내보냅니다. 이미 나가지 않은 모든 data page를 eviction하고 page frame을 새 mapping/page-in에 사용할 수 있게 합니다. 연결 frame은 pinned 상태면 안 됩니다. Eviction 유지 시간은 보장되지 않아 곧바로 page fault로 다시 들어올 수 있습니다. CONFIG_DEMAND_PAGING_ALLOW_IRQ가 켜지면 backing store 사용 충돌 때문에 ISR에서 호출할 수 없습니다.

매개변수

  • addr: page-aligned base virtual address
  • size: page-aligned data region 크기

반환값: 성공은 0, backing store 공간 부족은 -ENOMEM이며 이때 영역 일부만 page-out됐을 수 있습니다.

void k_mem_page_in(void *addr, size_t size)

Virtual data 영역을 memory로 불러옵니다. 완료 시 관련 frame이 모두 resident이지만 계속 머문다는 보장은 없습니다. 곧 사용할 영역의 page fault latency를 줄일 때 유용합니다. CONFIG_DEMAND_PAGING_ALLOW_IRQ가 켜지면 ISR에서 호출할 수 없습니다.

매개변수

  • addr: page-aligned base virtual address
  • size: page-aligned 영역 크기
void k_mem_pin(void *addr, size_t size)

필요하면 page-in한 뒤 virtual data 영역을 pin합니다. 완료 후 frame은 resident이며 eviction되지 않습니다. z_mem_page_in()보다 강한 연산입니다. CONFIG_DEMAND_PAGING_ALLOW_IRQ가 켜지면 ISR에서 호출할 수 없습니다.

매개변수

  • addr: page-aligned base virtual address
  • size: page-aligned 영역 크기
void k_mem_unpin(void *addr, size_t size)

Virtual data 영역의 pinned 표시를 제거하지만 page-out하지는 않습니다. 내보내려면 뒤이어 z_mem_page_out()을 호출합니다.

매개변수

  • addr: page-aligned base virtual address
  • size: page-aligned 영역 크기
void k_mem_paging_stats_get(struct k_mem_paging_stats_t *stats)

System startup 이후 전체 paging 통계를 채웁니다.

매개변수

  • stats: [inout] 채울 paging statistics 구조체
void k_mem_paging_thread_stats_get(struct k_thread *thread, struct k_mem_paging_stats_t *stats)

System startup 이후 특정 thread의 paging 통계를 채웁니다.

매개변수

  • thread: 대상 thread
  • stats: [inout] 채울 paging statistics 구조체
void k_mem_paging_histogram_eviction_get(struct k_mem_paging_histogram_t *hist)

Eviction 실행 시간 histogram을 채웁니다.

매개변수

  • hist: [inout] 채울 timing histogram
void k_mem_paging_histogram_backing_store_page_in_get(struct k_mem_paging_histogram_t *hist)

Backing store page-in 실행 시간 histogram을 채웁니다.

매개변수

  • hist: [inout] 채울 timing histogram
void k_mem_paging_histogram_backing_store_page_out_get(struct k_mem_paging_histogram_t *hist)

Backing store page-out 실행 시간 histogram을 채웁니다.

매개변수

  • hist: [inout] 채울 timing histogram
struct k_mem_paging_stats_t

Paging statistics 구조체입니다.

unsigned long cnt

Page fault 횟수입니다.

unsigned long irq_locked

IRQ가 locked인 상태에서 발생한 page fault 횟수입니다.

unsigned long irq_unlocked

IRQ가 unlocked인 상태에서 발생한 page fault 횟수입니다.

unsigned long in_isr

ISR에서 발생한 page fault 횟수입니다.

unsigned long clean

Eviction 대상으로 선택한 clean page 수입니다.

unsigned long dirty

Eviction 대상으로 선택한 dirty page 수입니다.

struct k_mem_paging_histogram_t

Paging operation 실행 시간 histogram 구조체입니다.

Eviction Algorithm API

mem-demand-paging-eviction group은 candidate lifecycle과 선택 algorithm 계약입니다.

void k_mem_paging_eviction_add(struct k_mem_page_frame *pf)

Kernel이 page frame을 잠재 eviction candidate tracking에 추가합니다. eviction_init() 이전에는 호출되지 않고 interrupt가 locked된 상태에서 호출됩니다.

매개변수

  • pf: 추가할 page frame
void k_mem_paging_eviction_remove(struct k_mem_page_frame *pf)

Kernel이 page frame을 candidate에서 제거합니다. 이전에 eviction_add()로 제출한 frame에만 호출하며 interrupt가 locked된 상태입니다.

매개변수

  • pf: 제거할 page frame
void k_mem_paging_eviction_accessed(uintptr_t phys)

Architecture별 memory fault handler가 physical address의 frame이 새로 접근됐음을 알려 다음 eviction candidate가 될 가능성을 낮춥니다. Interrupt가 locked된 상태에서 호출됩니다.

매개변수

  • phys: 접근된 physical address
struct k_mem_page_frame *k_mem_paging_eviction_select(bool *dirty)

Free page frame이 없을 때 kernel이 eviction 후보를 고릅니다. 반환 frame이 실제로 eviction된다는 보장은 없고, 실제 제거 시 kernel이 eviction_remove()를 호출합니다. eviction_init() 완료 전에는 호출되지 않으며 interrupt가 locked된 상태입니다.

매개변수

  • dirty: [out] 선택 page가 dirty인지 기록할 위치

반환값: Eviction 대상으로 선택한 page frame입니다.

void k_mem_paging_eviction_init(void)

POST_KERNEL에 한 번 호출되어 eviction algorithm을 초기화합니다. 이 함수가 반환하기 전에는 eviction_select()가 호출되지 않습니다.

Backing Store API

mem-demand-paging-backing-store group은 location token과 scratch-page copy lifecycle을 정의합니다.

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

Page frame에 올라온 data page의 storage location을 예약하거나 기존 location을 가져옵니다. Token은 mapped virtual address마다 고유하고 page-aligned여야 합니다. K_MEM_PAGE_FRAME_BACKED가 설정된 clean cached page면 이전 location을 반환해야 합니다. Store가 가득 차면 다른 clean cache location을 재사용하면서 기존 frame의 BACKED bit를 지울 수 있습니다. Page fault 요청은 항상 free location 하나를 확보해야 하므로 page_fault가 false일 때 마지막 하나만 남았다면 -ENOMEM을 반환해야 합니다. Interrupt locked 상태에서 호출됩니다.

매개변수

  • pf: storage location을 얻을 page frame
  • location: [out] storage location token
  • page_fault: page fault를 위한 요청인지 여부

반환값: 성공은 0, backing store가 가득 차면 -ENOMEM입니다.

void k_mem_paging_backing_store_location_free(uintptr_t location)

Backing store location을 해제해 data를 버리고 token을 다른 page에 재사용할 수 있게 합니다. Interrupt locked 상태에서 호출됩니다.

매개변수

  • location: 해제할 location token
void k_mem_paging_backing_store_page_out(uintptr_t location)

K_MEM_SCRATCH_PAGE에서 지정 location으로 data page를 복사합니다. 호출 직전 scratch page는 source frame에 read-write로 map됩니다. Page-in과 page-out 호출은 항상 직렬화되지만 interrupt는 enabled일 수 있습니다.

매개변수

  • location: 나중에 복구할 data page location token
void k_mem_paging_backing_store_page_in(uintptr_t location)

지정 location에서 K_MEM_SCRATCH_PAGE로 data page를 복사합니다. 호출 직전 scratch page는 destination frame에 read-write로 map됩니다. Page-in/out은 직렬화되지만 interrupt는 enabled일 수 있습니다.

매개변수

  • location: data page location token
void k_mem_paging_backing_store_page_finalize(struct k_mem_page_frame *pf, uintptr_t location)

Page-in 뒤 interrupt를 다시 lock한 상태에서 내부 accounting을 갱신합니다. Custom page-frame field에 다음 eviction location을 기록할 수 있고 no-op도 허용됩니다. Backing store가 paged-in data를 cache한다면 이때 K_MEM_PAGE_FRAME_BACKED를 설정합니다. Kernel은 page table에서 clean이고 frame에 BACKED가 설정된 page만 write 없이 page-out합니다.

매개변수

  • pf: load된 page frame
  • location: data page를 가져온 location
void k_mem_paging_backing_store_init(void)

POST_KERNEL에 backing store를 초기화합니다. 반환 직후부터 page-in/out 호출을 받을 수 있습니다. 내부 data structure와 accounting을 초기화하고, boot 때 이미 store에 clean copy가 있는 loaded page는 K_MEM_PAGE_FRAME_BACKED와 내부 장부를 맞춰야 합니다.

Source

출처

영어 원문에는 문단, 문서 지시문, 표, 코드, 코드 심벌, 경로를 그대로 보존했습니다.