Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
<html>
<head>
<title>On-Demand Paging</title>
</head>
<body background="backgd.gif">
<hr><hr>
<table width ="100%">
<tr align="center" bgcolor="#e4e4e4">
<td>
<h1><big><font color="#3c34ec"><i>On-Demand Paging</i></font></big></h1>
<h2><font color="#dc143c">>>> Under Construction <<<</font></h2>
<p>Last Updated: August 12, 2010</p>
</td>
</tr>
</table>
<hr><hr>
<table width ="100%">
<tr bgcolor="#e4e4e4">
<td>
<h1>Table of Contents</h1>
</td>
</tr>
</table>
<center><table width ="80%">
<tr>
<td>
<table>
<tr>
<td valign="top" width="22"><img height="20" width="20" src="favicon.ico"></td>
<td>
<a href="#Terminology">Terminolgy</a>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td>
<table>
<tr>
<td valign="top" width="22"><img height="20" width="20" src="favicon.ico"></td>
<td>
<a href="#Initialization">Initialization</a>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td>
<table>
<tr>
<td valign="top" width="22"><img height="20" width="20" src="favicon.ico"></td>
<td>
<a href="#PageFaults">Page Faults</a>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td>
<table>
<tr>
<td valign="top" width="22"><img height="20" width="20" src="favicon.ico"></td>
<td>
<a href="#Fillnitiation">Fill Initiation</a>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td>
<table>
<tr>
<td valign="top" width="22"><img height="20" width="20" src="favicon.ico"></td>
<td>
<a href="#FillComplete">Fill Complete</a>
</td>
</tr>
</table>
</td>
</tr>
<tr>
<td>
<table>
<tr>
<td valign="top" width="22"><img height="20" width="20" src="favicon.ico"></td>
<td>
<a href="#TaskResumption">Task Resumption</a>
</td>
</tr>
</table>
</td>
</tr>
</table></center>
<table width ="100%">
<tr bgcolor="#e4e4e4">
<td>
<a name="Terminology"><h1>Terminolgy</h1></a>
</td>
</tr>
</table>
<dl>
<dt><code>g_waitingforfill</code></dt>
<dd>An OS list that is used to hold the TCBs of tasks that are waiting for a page fill.</dd>
<dt><code>g_pendingfill</code></dt>
<dd>A variable that holds a reference to the TCB of the thread that is currently be re-filled.</dd>
<dt><code>g_pgworker</code></dt>
<dd>The <i>process</i> ID of of the thread that will perform the page fills.</dd>
<dt><code>pg_callback()</code></dt>
<dd>The callback function that is invoked from a driver when the fill is complete.</dd>
<dt><code>pg_miss()</code></dt>
<dd>The function that is called from chip-specific code to handle a page fault.</dd>
<dt><code>TCB</code></dt>
<dd>Task Control Block</dd>
</dl>
<table width ="100%">
<tr bgcolor="#e4e4e4">
<td>
<a name="Initialization"><h1>Initialization</h1></a>
</td>
</tr>
</table>
<p>
The following declarations will be added.
<ul>
<li>
<b><code>g_waitingforfill</code></b>.
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.
</li>
<li>
<b><code>g_pgworker</code></b>.
The <i>process</i> ID of of the thread that will perform the page fills
</li>
</ul>
</p>
<p>
During OS initialization in <code>sched/os_start.c</code>, the following steps
will be performed:
<ul>
<li>
The <code>g_waitingforfill</code> queue will be initialized.
</li>
<li>
The special, page fill worker thread, will be started.
The <code>pid</code> of the page will worker thread will be saved in <code>g_pgworker</code>.
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.
</li>
</ul>
</p>
<p>
Declarations for <code>g_waitingforfill</code>, <code>g_pgworker</code>, and other
internal, private definitions will be provided in <code>sched/pg_internal.h</code>.
All public definitions that should be used by the chip-specific code will be available
in <code>include/nuttx/page.h</code> and <code>include/nuttx/arch.h</code>.
</p>
<table width ="100%">
<tr bgcolor="#e4e4e4">
<td>
<a name="PageFaults"><h1>Page Faults</h1></a>
</td>
</tr>
</table>
<p>
<b>Page fault exception handling</b>.
Page fault handling is performed by the function <code>pg_miss()</code>.
This function is called from architecture-specific memory segmentation
fault handling logic. This function will perform the following
operations:
<ol>
<li>
<b>Sanity checking</b>.
This function will ASSERT if the currently executing task is the page fill worker thread.
The page fill worker thread is how the the page fault is resolved and all logic associated with the page fill worker
must be "locked" and always present in memory.
</li>
<li>
<b>Block the currently executing task</b>.
This function will call <code>up_block_task()</code> 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 <code>TSTATE_WAIT_PAGEFILL</code> and will be retained in the <code>g_waitingforfill</code> prioritized task list.
</li>
<li>
<b>Boost the page fill worker thread priority</b>.
Check the priority of the task at the head of the <code>g_waitingforfill</code> 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.
</li>
<li>
<b>Signal the page fill worker thread</b>.
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.
</li>
</ol>
</p>
<p>
When signaled from <code>pg_miss()</code>, the page fill worker thread will be awakenend and will initiate the fill operation.
</p>
<p>
<b>Input Parameters.</b>
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.
</p>
<p>
<b>Assumptions</b>.
<ul>
<li>
It is assumed that this function is called from the level of an exception handler and that all interrupts are disabled.
</li>
<li>
The <code>pg_miss()</code> must be "locked" in memory.
Calling <code>pg_miss()</code> cannot cause a nested page fault.
</li>
<li>
It is assumed that currently executing task (the one at the head of the ready-to-run list) is the one that cause the fault.
This will always be true unless the page fault occurred in an interrupt handler.
Interrupt handling logic must always be available and "locked" into memory so that page faults never come from interrupt handling.
</li>
<li>
The chip-specific page fault exception handling has already verified that the exception did not occur from interrupt/exception handling logic.
</li>
<li>
As mentioned above, the task causing the page fault must not be the page fill worker thread because that is the only way to complete the page fill.
</li>
<li>
Chip specific logic will map the virtual address space into three regions:
<ol>
<li>
A .text region containing "locked-in-memory" code that is always avaialable and will never cause a page fault.
</li>
<li>
A .text region containing pages that can be assigned allocated, mapped to various virtual addresses, and filled from some mass storage medium.
</li>
<li>
And a fixed RAM space for .bss, .text, and .heap.
</li>
</ol>
</li>
</ul>
</p>
<p>
<b>Locking code in Memory</b>.
One way to accomplish this would be a two phase link:
<ul>
<li>
In the first phase, create a partially linked objected containing all interrupt/exception handling logic, the page fill worker thread plus all parts of the IDLE thread (which must always be available for execution).
</li>
<li>
All of the <code>.text</code> and <code>.rodata</code> sections of this partial link should be collected into a single section.
</li>
<li>
The second link would link the partially linked object along with the remaining object to produce the final binary.
The linker script should position the "special" section so that it lies in a reserved, "non-swappable" region.
</ul>
</p>
<table width ="100%">
<tr bgcolor="#e4e4e4">
<td>
<a name="FillInitiation"><h1>Fill Initiation</h1></a>
</td>
</tr>
</table>
<p>
The page fill worker thread will be awakened on one of two conditions:
<ul>
<li>
When signaled by <code>pg_miss()</code>, the page fill worker thread will be awakenend (see above), or
</li>
<li>
From <code>pg_fillcomplete()</code> after completing last fill (see below).
</li>
</ul>
</p>
<p>
The page fill worker thread will maintain a static variable called <code>_TCB *g_pendingfill</code>.
If not fill is in progress, <code>g_pendingfill</code> will be NULL.
Otherwise, will point to the TCB of the task which is receiving the fill that is in progess.
</p>
<p>
When awakened from <code>pg_miss()</code>, no fill will be in progress and <code>g_pendingfill</code> will be NULL.
In this case, the page fill worker thread will call <code>pg_startfill()</code>.
That function will perform the following operations:
<ul>
<li>
Call <code>up_allocpage(vaddr, &page)</code>.
This chip-specific function will set aside page in memory and map to virtual address (vaddr).
If all pages available pages are in-use (the typical case),
this function will select a page in-use, un-map it, and make it available.
</li>
<li>
Call the chip-specific function <code>up_fillpage(page, pg_callback)</code>.
This will start asynchronous page fill.
The page fill worker thread will provide a callback function, <code>pg_callback</code>,
that will be called when the page fill is finished (or an error occurs).
This callback will probably from interrupt level.
</li>
<li>
Restore default priority of the page fill worker thread's default priority and wait to be signaled for the next event -- the fill completion event.
</li>
</ul>
</p>
<p>
While the fill is in progress, other tasks may execute.
If another page fault occurs during this time, the faulting task will be blocked and its TCB will be added (in priority order) to <code>g_waitingforfill</code>.
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.
<p>
The chip-specific functions, <code>up_allocpage(vaddr, &page)</code> and <code>up_fillpage(page, pg_callback)</code>
will be prototyped in <code>include/nuttx/arch.h</code>
</p>
<table width ="100%">
<tr bgcolor="#e4e4e4">
<td>
<a name="FillComplete"><h1>Fill Complete</h1></a>
</td>
</tr>
</table>
<p>
When the chip-specific driver completes the page fill, it will call the <code>pg_callback()</code> that was provided to <code>up_fillpage</code>.
<code>pg_callback()</code> will probably be called from driver interrupt-level logic.
The driver ill provide the result of the fill as an argument.
NOTE: <code>pg_callback()</code> must also be locked in memory.
</p>
<p>
When <code>pg_callback()</code> is called, it will perform the following operations:
<ul>
<li>
Verify that <code>g_pendingfill</code> is non-NULL.
</li>
<li>
If the priority of thread in <code>g_pendingfill</code> is higher than page fill worker thread, boost work thread to that level.
</li>
<li>
Signal the page fill worker thread.
</li>
</ul>
</p>
<table width ="100%">
<tr bgcolor="#e4e4e4">
<td>
<a name="TaskResumption"><h1>Task Resumption</h1></a>
</td>
</tr>
</table>
<p>
When the page fill worker thread is awakened and <code>g_pendingfill</code> is non-NULL (and other state variables are in concurrence),
the page fill thread will know that is was awakened because of a page fill completion event.
In this case, the page fill worker thread will:
<ul>
<li>
Verify consistency of state information and <code>g_pendingfill</code>.
</li>
<li>
Verify that the page fill completed successfully, and if so,
</li>
<li>
Call <code>up_unblocktask(g_pendingfill)</code> to make the task that just received the fill ready-to-run.
</li>
<li>
Check if the <code>g_waitingforfill</code> list is empty.
If not:
<ul>
<li>
Remove the highest priority task waiting for a page fill from <code>g_waitingforfill</code>,
</li>
<li>
Save the task's TCB in <code>g_pendingfill</code>,
</li>
<li>
If the priority of the thread in <code>g_pendingfill</code>, 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.
</li>
<li>
Call <code>pg_startfill()</code> which will start the next fill (as described above).
</li>
</ul>
</li>
<li>
Otherwise,
<ul>
<li>
Set <code>g_pendingfill</code> to NULL.
</li>
<li>
Restore the default priority of the page fill worker thread.
</li>
<li>
Wait for the next fill related event (a new page fault).
</li>
</ul>
</li>
</ul>
</p>
</body>
</html>