Last Updated: February 4, 2010
Table of Contents
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?
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.
NuttX Common Logic Design Description
The following declarations will be added.
g_waitingforfill. A doubly linked list that will be used to implement a prioritized list of the TCBs of tasks that are waiting for a page fill.
g_pgworker. The process ID of of the thread that will perform the page fills
During OS initialization in
sched/os_start.c, the following steps
will be performed:
g_waitingforfillqueue will be initialized.
pidof the page will worker thread will be saved in
g_pgworker. Note that we need a special worker thread to perform fills; we cannot use the "generic" worker thread facility because we cannot be assured that all actions called by that worker thread will always be resident in memory.
g_pgworker, and other
internal, private definitions will be provided in
All public definitions that should be used by the architecture-specific code will be available
Most architecture-specific functions are declared in
but for the case of this paging logic, those architecture specific functions are instead declared in
Page fault exception handling.
Page fault handling is performed by the function
This function is called from architecture-specific memory segmentation
fault handling logic. This function will perform the following
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_PAGEFILLand will be retained in the
g_waitingforfillprioritized task list.
g_waitingforfilllist. 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.
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.
pg_miss()must be "locked" in memory. Calling
pg_miss()cannot cause a nested page fault.
The page fill worker thread will be awakened on one of three conditions:
pg_miss(), the page fill worker thread will be awakenend (see above),
pg_callback()after completing last fill (when
CONFIG_PAGING_BLOCKINGFILLis defined... see below), or
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
That function will perform the following operations:
up_checkmapping()to see if the page fill still needs to be performed. In certain conditions, the page fault may occur on several threads and be queued multiple times. In this corner case, the blocked task will simply be restarted (see the logic below for the case of normal completion of the fill operation).
up_allocpage(tcb, &vpage). This architecture-specific function will set aside page in memory and map to virtual address (vpage). If all available pages are in-use (the typical case), this function will select a page in-use, un-map it, and make it available.
up_fillpage(). Two versions of the up_fillpage function are supported -- a blocking and a non-blocking version based upon the configuratin setting
CONFIG_PAGING_BLOCKINGFILLis defined, then up_fillpage is blocking call. In this case,
up_fillpage()will accept only (1) a reference to the TCB that requires the fill. Architecture-specific context information within the TCB will be sufficient to perform the fill. And (2) the (virtual) address of the allocated page to be filled. The resulting status of the fill will be provided by return value from
CONFIG_PAGING_BLOCKINGFILLis defined, then up_fillpage is non-blocking call. In this case
up_fillpage()will accept an additional argument: The page fill worker thread will provide a callback function,
pg_callback. This function is non-blocking, it will start an asynchronous page fill. After calling the non-blocking
up_fillpage(), the page fill worker thread will wait to be signaled for the next event -- the fill completion event. The callback function will be called when the page fill is finished (or an error occurs). The resulting status of the fill will be providing as an argument to the callback functions. This callback will probably occur from interrupt level.
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_allocpage(tcb, &vpage) and
will be prototyped in
For the blocking
up_fillpage(), the result of the fill will be returned directly from the call to
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.
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:
g_pftcband the task waiting at the head of the
g_waitingforfilllist. That will be the priority of he highest priority task waiting for a fill.
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
In the non-blocking case, the page fill worker thread will know that the page fill is complete when
In this either, the page fill worker thread will:
up_unblocktask(g_pftcb)to make the task that just received the fill ready-to-run.
g_waitingforfilllist is empty. If not:
g_pftcb, is higher in priority than the default priority of the page fill worker thread, then set the priority of the page fill worker thread to that priority.
pg_startfill()which will start the next fill (as described above).
Architecture-Specific Support Requirements
Memory Regions. Chip specific logic will map the virtual and physical address spaces into three general regions:
pg_miss()that is called from the page fault handler. It also includes the
pg_callback()function that wakes up the page fill worker thread and whatever architecture-specific logic that calls
This memory organization is illustrated in the following table. Notice that:
|SRAM||Virtual Address Space||Non-Volatile Storage|
|Virtual Page n (n > m)||Stored Page n|
|Virtual Page n-1||Stored Page n-1|
|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:
.rodatasections of this partial link should be collected into a single section.
Most standard, architecture-specific functions are declared in
However, for the case of this paging logic, the architecture specific functions are declared in
Standard, architecture-specific functions that should already be provided in the architecture port.
The following are used by the common paging logic:
void up_block_task(FAR struct tcb_s *tcb, tstate_t task_state);
void up_unblock_task(FAR struct tcb_s *tcb);
New, additional functions that must be implemented just for on-demand paging support:
int up_checkmapping(FAR struct tcb_s *tcb);
up_checkmapping()returns an indication if the page fill still needs to performed or not. In certain conditions, the page fault may occur on several threads and be queued multiple times. This function will prevent the same page from be filled multiple times.
int up_allocpage(FAR struct tcb_s *tcb, FAR void *vpage);
vpage. The size of the underlying physical page is determined by the configuration setting
CONFIG_PAGING_PAGESIZE. NOTE: This function must always return a page allocation. If all available pages are in-use (the typical case), then this function will select a page in-use, un-map it, and make it available.
int up_fillpage(FAR struct tcb_s *tcb, FAR const void *vpage, void (*pg_callback)(FAR struct tcb_s *tcb, int result));
up_fillpage(). This will start asynchronous page fill. The common paging logic will provide a callback function,
pg_callback, that will be called when the page fill is finished (or an error occurs). This callback is assumed to occur from an interrupt level when the device driver completes the fill operation.