On-Demand Paging

Last Updated: February 4, 2010



Table of Contents

Introduction
  Overview
  Terminology
NuttX Common Logic Design Description
  Initialization
  Page Faults
  Fill Initiation
  Fill Complete
  Task Resumption
Architecture-Specific Support Requirements
  Memory Organization
  Architecture-Specific Functions

Introduction

Overview

This document summarizes the design of NuttX on-demand paging. This feature permits embedded MCUs with some limited RAM space to execute large programs from some non-random access media. This feature was first discussed in this email thread: https://groups.yahoo.com/neo/groups/nuttx/conversations/messages/213.

What kind of platforms can support NuttX on-demang paging?

  1. The MCU should have some large, probably low-cost non-volatile storage such as serial FLASH or an SD card. This storage probably does not support non-random access (otherwise, why not just execute the program directly on the storage media). SD and serial FLASH are inexpensive and do not require very many pins and SPI support is prevalent in just about all MCUs. This large serial FLASH would contain a big program. Perhaps a program of several megabytes in size.
  2. The MCU must have a (relatively) small block of fast SRAM from which it can execute code. A size of, say 256K (or 192K as in the NXP LPC3131) would be sufficient for many applications.
  3. The MCU has an MMU (again like the NXP LPC3131).

If the platform meets these requirement, then NuttX can provide on-demand paging: It can copy .text from the large program in non-volatile media into RAM as needed to execute a huge program from the small RAM.

Terminology

g_waitingforfill
An OS list that is used to hold the TCBs of tasks that are waiting for a page fill.
g_pftcb
A variable that holds a reference to the TCB of the thread that is currently be re-filled.
g_pgworker
The process ID of of the thread that will perform the page fills.
pg_callback()
The callback function that is invoked from a driver when the fill is complete.
pg_miss()
The function that is called from architecture-specific code to handle a page fault.
TCB
Task Control Block

NuttX Common Logic Design Description

Initialization

The following declarations will be added.

During OS initialization in sched/os_start.c, the following steps will be performed:

Declarations for g_waitingforfill, g_pgworker, and other internal, private definitions will be provided in sched/paging/paging.h. All public definitions that should be used by the architecture-specific code will be available in include/nuttx/page.h. Most architecture-specific functions are declared in include/nuttx/arch.h, but for the case of this paging logic, those architecture specific functions are instead declared in include/nuttx/page.h.

Page Faults

Page fault exception handling. Page fault handling is performed by the function pg_miss(). This function is called from architecture-specific memory segmentation fault handling logic. This function will perform the following operations:

  1. Sanity checking. This function will ASSERT if the currently executing task is the page fill worker thread. The page fill worker thread is how the page fault is resolved and all logic associated with the page fill worker must be "locked" and always present in memory.
  2. Block the currently executing task. This function will call up_block_task() to block the task at the head of the ready-to-run list. This should cause an interrupt level context switch to the next highest priority task. The blocked task will be marked with state TSTATE_WAIT_PAGEFILL and will be retained in the g_waitingforfill prioritized task list.
  3. Boost the page fill worker thread priority. Check the priority of the task at the head of the g_waitingforfill list. If the priority of that task is higher than the current priority of the page fill worker thread, then boost the priority of the page fill worker thread to that priority. Thus, the page fill worker thread will always run at the priority of the highest priority task that is waiting for a fill.
  4. Signal the page fill worker thread. Is there a page already being filled? If not then signal the page fill worker thread to start working on the queued page fill requests.

When signaled from pg_miss(), the page fill worker thread will be awakenend and will initiate the fill operation.

Input Parameters. None -- The head of the ready-to-run list is assumed to be that task that caused the exception. The current task context should already be saved in the TCB of that task. No additional inputs are required.

Assumptions.

Fill Initiation

The page fill worker thread will be awakened on one of three conditions:

The page fill worker thread will maintain a static variable called struct tcb_s *g_pftcb. If no fill is in progress, g_pftcb will be NULL. Otherwise, it will point to the TCB of the task which is receiving the fill that is in progess.

When awakened from pg_miss(), no fill will be in progress and g_pftcb will be NULL. In this case, the page fill worker thread will call pg_startfill(). That function will perform the following operations:

In any case, while the fill is in progress, other tasks may execute. If another page fault occurs during this time, the faulting task will be blocked, its TCB will be added (in priority order) to g_waitingforfill, and the priority of the page worker task may be boosted. But no action will be taken until the current page fill completes. NOTE: The IDLE task must also be fully locked in memory. The IDLE task cannot be blocked. It the case where all tasks are blocked waiting for a page fill, the IDLE task must still be available to run.

The architecture-specific functions, up_checkmapping(), up_allocpage(tcb, &vpage) and up_fillpage(page, pg_callback) will be prototyped in include/nuttx/arch.h

Fill Complete

For the blocking up_fillpage(), the result of the fill will be returned directly from the call to up_fillpage.

For the non-blocking up_fillpage(), the architecture-specific driver call the pg_callback() that was provided to up_fillpage() when the fill completes. In this case, the pg_callback() will probably be called from driver interrupt-level logic. The driver will provide the result of the fill as an argument to the callback function. NOTE: pg_callback() must also be locked in memory.

In this non-blocking case, the callback pg_callback() will perform the following operations when it is notified that the fill has completed:

Task Resumption

For the non-blocking up_fillpage(), the page fill worker thread will detect that the page fill is complete when it is awakened with g_pftcb non-NULL and fill completion status from pg_callback. In the non-blocking case, the page fill worker thread will know that the page fill is complete when up_fillpage() returns.

In this either, the page fill worker thread will:

Architecture-Specific Support Requirements

Memory Organization

Memory Regions. Chip specific logic will map the virtual and physical address spaces into three general regions:

  1. A .text region containing "locked-in-memory" code that is always avaialable and will never cause a page fault. This locked memory is loaded at boot time and remains resident for all time. This memory regions must include:
  2. A .text region containing pages that can be assigned allocated, mapped to various virtual addresses, and filled from some mass storage medium.
  3. And a fixed RAM space for .bss, .text, and .heap.

This memory organization is illustrated in the following table. Notice that:

SRAM Virtual Address Space Non-Volatile Storage
  DATA  
  Virtual Page n (n > m) Stored Page n
  Virtual Page n-1 Stored Page n-1
DATA ... ...
Physical Page m (m < n) ... ...
Physical Page m-1 ... ...
... ... ...
Physical Page 1 Virtual Page 1 Stored Page 1
Locked Memory Locked Memory Memory Resident

Example. As an example, suppose that the size of the SRAM is 192K (as in the NXP LPC3131). And suppose further that:

Then, the size of the locked, memory resident code is 32K (m=32 pages). The size of the physical page region is 96K (96 pages), and the size of the data region is 64 pages. And the size of the virtual paged region must then be greater than or equal to (1024-32) or 992 pages (n).

Building the Locked, In-Memory Image. One way to accomplish this would be a two phase link:

Architecture-Specific Functions

Most standard, architecture-specific functions are declared in include/nuttx/arch.h. However, for the case of this paging logic, the architecture specific functions are declared in include/nuttx/page.h. Standard, architecture-specific functions that should already be provided in the architecture port. The following are used by the common paging logic:

New, additional functions that must be implemented just for on-demand paging support: