Re-import of missing page
[ikiwiki.git] / docs / developer / VirtualKernelPeek / index.mdwn
1 # A Peek at the DragonFly Virtual Kernel
2
3 #### This article was contributed by Aggelos Economopoulos.
4
5
6 >**NOTE:** This article originally appeared as two articles on <http://lwn.net/>.
7
8
9    In this article, we will describe several aspects of the architecture
10    of DragonFly BSD's virtual kernel infrastructure, which allows the
11    kernel to be run as a user-space process. Its design and implementation
12    is largely the work of the project's lead developer, Matthew Dillon, who
13    first announced his intention of modifying the kernel to run in userspace
14    on [September 2nd 2006](http://leaf.dragonflybsd.org/mailarchive/kernel/2006-09/msg00000.html). The first stable DragonFlyBSD version to feature
15    virtual kernel (vkernel) support was DragonFly 1.8, released on January
16    30th 2007.
17
18    The motivation for this work (as can be found in the initial mail linked
19    to above) was finding an elegant solution to one immediate and one long
20    term issue in pursuing the project's main goal of Single System Image
21    clustering over the Internet. First, as any person who is familiar with
22    distributed algorithms will attest, implementing cache coherency without
23    hardware support is a complex task. It would not be made any easier by
24    enduring a 2-3 minute delay in the edit-compile-run cycle while each
25    machine goes through the boot sequence. As a nice side effect, userspace
26    programming errors are unlikely to bring the machine down and one has the
27    benefit of working with superior debugging tools (and can more easily
28    develop new ones).
29
30    The second, long term, issue that virtual kernels are intended to address
31    is finding a way to securely and efficiently dedicate system resources to
32    a cluster that operates over the (hostile) Internet. Because a kernel is
33    a more or less standalone environment, it should be possible to completely
34    isolate the process a virtual kernel runs in from the rest of the system.
35    While the problem of process isolation is far from solved, there exist a
36    number of promising approaches. One option, for example, would be to use
37    systrace (refer to [Provos03]) to mask-out all but the few (and hopefully
38    carefully audited) system calls that the vkernel requires after
39    initialization has taken place. This setup would allow for a significantly
40    higher degree of protection for the host system in the event that the
41    virtualized environment was compromised. Moreover, the host kernel already
42    has well-tested facilities for arbitrating resources, although these
43    facilities are not necessarily sufficient or dependable; the CPU scheduler
44    is not infallible and mechanisms for allocating disk I/O bandwidth will
45    need to be implemented or expanded. In any case, leveraging preexisting
46    mechanisms reduces the burden on the project's development team, which
47    can't be all bad.
48
49
50 ## Preparatory work
51
52
53    Getting the kernel to build as a regular, userspace, elf executable
54    required tidying up large portions of the source tree. In this section we
55    will focus on the two large sets of changes that took place as part of
56    this cleanup. The second set might seem superficial and hardly worthy of
57    mention as such, but in explaining the reason that lead to it, we shall
58    discuss an important decision that was made in the implementation of the
59    virtual kernel.
60
61
62    The first set of changes was separating machine dependent code to
63    platform- and CPU-specific parts. The real and virtual kernels can be
64    considered to run on two different platforms; the first is (only, as must
65    reluctantly be admitted) running on 32-bit PC-style hardware, while the
66    second is running on a DragonFly kernel. Regardless of the differences
67    between the two platforms, both kernels expect the same processor
68    architecture. After the separation, the cpu/i386 directory of the kernel
69    tree is left with hand-optimized assembly versions of certain kernel
70    routines, headers relevant only to x86 CPUs and code that deals with
71    object relocation and debug information. The real kernel's platform
72    directory (platform/pc32) is familiar with things like programmable
73    interrupt controllers, power management and the PC bios (that the
74    vkernel doesn't need), while the virtual kernel's platform/vkernel
75    directory is happily using the system calls that the real kernel
76    can't have. Of course this does not imply that there is absolutely no
77    code duplication, but fixing that is not a pressing problem.
78
79
80    The massive second set of changes involved primarily renaming quite a few
81    kernel symbols so that there are no clashes with the libc ones (e.g.
82    *printf(), qsort, errno etc.) and using kdev_t for the POSIX dev_t type
83    in the kernel. As should be plain, this was a prerequisite for having the
84    virtual kernel link with the standard C library. Given that the kernel is
85    self-hosted (this means that, since it cannot generally rely on support
86    software after it has been loaded, the kernel includes its own helper
87    routines), one can question the decision of pulling in all of libc
88    instead of simply adding the (few) system calls that the vkernel actually
89    uses. A controversial choice at the time, it prevailed because it was
90    deemed that it would allow future vkernel code to leverage the extended
91    functionality provided by libc. Particularly, thread-awareness in the
92    system C library should accommodate the (medium term) plan to mimic
93    multi-processor operation by the use of one vkernel thread for each
94    hypothetical CPU. It is safe to say that if the plan is materialized,
95    linking against libc will prove to be a most profitable tradeoff.
96
97
98 ## The Virtual Kernel
99
100
101    In this section, we will study the architecture of the virtual kernel and
102    the design choices made in its development, focusing on its differences
103    from a kernel running on actual hardware. In the process, we'll need to
104    describe the changes made in the real (host) kernel code, specifically
105    in order to support a DragonFly kernel running as a user process.
106
107
108 ## Address Space Model
109
110
111    The first design choice made in the development of the vkernel is that
112    the whole virtualized environment is executing as part of the same
113    real-kernel process. This imposes well defined limits on the amount
114    of real-kernel resources that may be consumed by it and makes
115    containment straightforward. Processes running under the vkernel are not
116    in direct competition with host processes for cpu time and most parts of
117    the bookkeeping that is expected from a kernel during the lifetime of a
118    process are handled by the virtual kernel. The alternative<a name="AEN1"
119    href="vkernel.shtml#FTN.AEN1">[1]</a>, running each vkernel process<a
120    name="AEN2" href="vkernel.shtml#FTN.AEN2">[2]</a> in the context of a
121    real kernel process, imposes extra burden on the host kernel and requires
122    additional mechanisms for effective isolation of vkernel processes from
123    the host system. That said, the real kernel still has to deal with some
124    amount of VM work and reserve some memory space that is proportional to
125    the number of processes running under the vkernel. This statement will be
126    made clear after we examine the new system calls for the manipulation of
127    vmspace objects.
128
129    In the kernel, the main purpose of a vmspace object is to describe the
130    address space of one or more processes. Each process normally has one
131    vmspace, but a vmspace may be shared by several processes. An address
132    space is logically partitioned into sets of pages, so that all pages
133    in a set are backed by the same VM object (and are linearly mapped on
134    it) and have the same protection bits. All such sets are represented
135    as vm_map_entry structures. VM map entries are linked together both by
136    a tree and a linked list so that lookups, additions, deletions and
137    merges can be performed efficiently (with low time complexity). Control
138    information and pointers to these data structures are encapsulated in
139    the vm_map object that is contained in every vmspace (see the
140    diagram below).
141
142
143 [[dbsd-vm.png]]
144
145    A VM object (vm_object) is an interface to a data store and can be of
146    various types (default, swap, vnode, ...) depending on where it gets
147    its pages from. The existence of shadow objects somewhat complicates
148    matters, but for our purposes this simplified model should be
149    sufficient. For more information you're urged to have a look at the
150    source and refer to [McKusick04] and [Dillon00].
151
152    In the first stages of the development of vkernel, a number of system
153    calls were added to the kernel that allow a process to associate itself
154    with more than one vmspace. The creation of a vmspace is accomplished by
155    vmspace_create(). The new vmspace is uniquely identified by an arbitrary
156    value supplied as an argument. Similarly, the vmspace_destroy() call
157    deletes the vmspace identified by the value of its only parameter. It is
158    expected that only a virtual kernel running as a user process will need
159    access to alternate address spaces. Also, it should be made clear that
160    while a process can have many vmspaces associated with it, only one
161    vmspace is active at any given time. The active vmspace is the one
162    operated on by mmap()/munmap()/madvise()/etc.
163
164    The virtual kernel creates a vmspace for each of its processes and it
165    destroys the associated vmspace when a vproc is terminated, but this
166    behavior is not compulsory. Since, just like in the real kernel, all
167    information about a process and its address space is stored in kernel
168    memory<a name="AEN3" href="vkernel.shtml#FTN.AEN3">[3]</a>, the vmspace
169    can be disposed of and reinstantiated at will; its existence is only
170    necessary while the vproc is running. One can imagine the vkernel
171    destroying the vproc vmspaces in response to a low memory situation in
172    the host system.
173
174    When it decides that it needs to run a certain process, the vkernel
175    issues a vmspace_ctl() system call with an argument of VMSPACE_CTL_RUN
176    as the command (currently there are no other commands available),
177    specifying the desired vmspace to activate. Naturally, it also needs to
178    supply the necessary context (values of general purpose registers,
179    instruction/stack pointers, descriptors) in which execution will resume.
180    The original vmspace is special; if, while running on an alternate
181    address space, a condition occurs which requires kernel intervention
182    (for example, a floating point operation throws an exception or a system
183    call is made), the host kernel automatically switches back to the previous
184    vmspace handing over the execution context at the time the exceptional
185    condition caused entry into the kernel and leaving it to the vkernel to
186    resolve matters. Signals by other host processes are likewise delivered
187    after switching back to the vkernel vmspace.
188
189    Support for creating and managing alternate vmspaces is also available to
190    vkernel processes. This requires special care so that all the relevant
191    code sections can operate in a recursive manner. The result is that
192    vkernels can be nested, that is, one can have a vkernel running as a
193    process under a second vkernel running as a process under a third vkernel
194    and so on. Naturally, the overhead incurred for each level of recursion
195    does not make this an attractive setup performance-wise, but it is a neat
196    feature nonetheless.
197
198 ##Userspace I/O
199
200
201    Now that we know how the virtual kernel regains control when
202    its processes request/need servicing, let us turn to how it
203    goes about satisfying those requests. Signal transmission and
204    most of the filesystem I/O (read, write, ...), process control
205    (kill, signal, ...) and net I/O system calls are easy; the
206    vkernel takes the same code paths that a real kernel would. The
207    only difference is in the implementation of the copyin()/copyout()
208    family of routines for performing I/O to and from userspace.
209
210    When the real kernel needs to access user memory locations,
211    it must first make sure that the page in question is resident
212    and will remain in memory for the duration of a copy. In
213    addition, because it acts on behalf of a user process, it
214    should adhere to the permissions associated with that process.
215    Now, on top of that, the vkernel has to work around the fact
216    that the process address space is not mapped while it is
217    running. Of course, the vkernel knows which pages it needs to
218    access and can therefore perform the copy by creating a
219    temporary kernel mapping for the pages in question. This
220    operation is reasonably fast; nevertheless, it does incur
221    measurable overhead compared to the host kernel.
222
223 ## Page Faults
224
225
226    The interesting part is dealing with page faults (this
227    includes lazily servicing mmap()/madvise()/... operations).
228    When a process mmap()s a file (or anonymous memory) in its
229    address space, the kernel (real or virtual) does not
230    immediately allocate pages to read in the file data (or
231    locate the pages in the cache, if applicable), nor does it setup the
232    pagetable entries to fulfill the request. Instead, it merely notes in
233    its data structures that it has promised that the specified data will
234    be there when read and that writes to the corresponding memory locations
235    will not fail (for a writable mapping) and will be reflected on disk (if
236    they correspond to a file area). Later, if the process tries to access
237    these addresses (which do not still have valid pagetable entries (PTES),
238    if they ever did, because new mappings invalidate old ones), the CPU
239    throws a pagefault and the fault handling code has to deliver as promised;
240    it obtains the necessary data pages and updates the PTES. Following that,
241    the faulting instruction is restarted.
242
243    Consider what happens when a process running on an alternate vmspace
244    of a vkernel process generates a page fault trying to access the memory
245    region it has just mmap()ed. The real kernel knows nothing about this
246    and through a mechanism that will be described later, passes the
247    information about the fault on to the vkernel. So, how does the vkernel
248    deal with it? The case when the faulting address is invalid is trivially
249    handled by delivering a signal (SIGBUS or SIGSEGV) to the faulting vproc.
250    But in the case of a reference to a valid address, how can the vkernel
251    ensure that the current and succeeding accesses will complete? Existing
252    system facilities are not appropriate for this task; clearly, a new
253    mechanism is called for.
254
255    What we need, is a way for the vkernel to execute mmap-like operations
256    on its alternate vmspaces. With this functionality available as a set of
257    system calls, say vmspace_mmap()/vmspace_munmap()/etc, the vkernel code
258    servicing an mmap()/munmap()/mprotect()/etc vproc call would, after doing
259    some sanity checks, just execute the corresponding new system call
260    specifying the vmspace to operate on. This way, the real kernel would be
261    made aware of the required mapping and its VM system would do our work
262    for us.
263
264    The DragonFly kernel provides a vmspace_mmap() and a vmspace_munmap()
265    like the ones we described above, but none of the other calls we thought
266    we would need. The reason for this is that it takes a different,
267    non-obvious, approach that is probably the most intriguing aspect of the
268    vkernel work. The kernel's generic mmap code now recognizes a new flag,
269    MAP_VPAGETABLE. This flag specifies that the created mapping is governed
270    by a userspace virtual pagetable structure (a vpagetable), the address of
271    which can be set using the new vmspace_mcontrol() system call (which is
272    an extension of madvise(), accepting an extra pointer parameter) with an
273    argument of MADV_SETMAP. This software pagetable structure is similar to
274    most architecture-defined pagetables. The complementary vmspace_munmap(),
275    not surprisingly, removes mappings in alternate address spaces. These are
276    the primitives on which the memory management of the virtual kernel
277    is built.
278
279
280 **Table 1. New vkernel-related system calls**
281
282
283     int vmspace_create(void *id, int type, void *data);
284     int vmspace_destroy(void *id,);
285     int vmspace_ctl(void *id, int cmd, struct trapframe *tf,
286                     struct vextframe *vf);
287     int vmspace_mmap(void *id, void *start, size_t len, int prot,
288                      int flags, int fd, off_t offset);
289     int vmspace_munmap(void *id, void *start, size_t len);
290     int mcontrol(void *start, size_t len, int adv, void *val);
291     int vmspace_mcontrol(void *id, void *start, size_t len, int adv,
292                          void *val);
293
294
295
296    At this point, an overview of the virtual memory map of each vmspace
297    associated with the vkernel process is in order. When the virtual kernel
298    starts up, there is just one vmspace for the process and it is similar to
299    that of any other process that just begun executing (mainly consisting of
300    mappings for the heap, stack, program text and libc). During its
301    initialization, the vkernel mmap()s a disk file that serves the role of
302    physical memory (RAM). The real kernel is instructed (via
303    madvise(MADV_NOSYNC)) to not bother synchronizing this memory region with
304    the disk file unless it has to, which is typically when the host kernel is
305    trying to reclaim RAM pages in a low memory situation. This is imperative;
306    otherwise all the vkernel "RAM" data would be treated as valuable by the
307    host kernel and would periodically be flushed to disk. Using MADV_NOSYNC,
308    the vkernel data will be lost if the system crashes, just like actual RAM,
309    which is exactly what we want: it is up to the vkernel to sync user data
310    back to its own filesystem. The memory file is mmap()ed specifying
311    MAP_VPAGETABLE. It is in this region that all memory allocations (both for
312    the virtual kernel and its processes) take place. The pmap module, the
313    role of which is to manage the vpagetables according to instructions from
314    higher level VM code, also uses this space to create the vpagetables for
315    user processes.
316
317    On the real kernel side, new vmspaces that are created for these user
318    processes are very simple in structure. They consist of a single
319    vm_map_entry that covers the 0 - VM_MAX_USER_ADDRESS address range. This
320    entry is of type MAPTYPE_VPAGETABLE and the address for its vpagetable has
321    been set (by means of vmspace_mcontrol()) to point to the vkernel's RAM,
322    wherever the pagetable for the process has been allocated.
323
324    The true vm_map_entry structures are managed by the vkernel's VM
325    subsystem. For every one of its processes, the virtual kernel maintains the
326    whole set of vmspace/vm_map, vm_map_entry, vm_object objects that we
327    described earlier. Additionally, the pmap module needs to keep its own
328    (not to be described here) data structures. All of the above objects reside
329    in the vkernel's "physical" memory. Here we see the primary benefit of the
330    DragonFly approach: no matter how fragmented an alternate vmspace's virtual
331    memory map is and independently of the amount of sharing of a given page by
332    processes of the virtual kernel, the host kernel expends a fixed (and
333    reasonably sized) amount of memory for each vmspace. Also, after the initial
334    vmspace creation, the host kernel's VM system is taken out of the equation
335    (expect for pagefault handling), so that when vkernel processes require VM
336    services, they only compete among themselves for CPU time and not with the
337    host processes. Compared to the "obvious" solution, this approach saves
338    large amounts of host kernel memory and achieves a higher degree
339    of isolation.
340
341    Now that we have grasped the larger picture, we can finally examine our
342    "interesting" case: a page fault occurs while the vkernel process is using
343    one of its alternate vmspaces. In that case, the vm_fault() code will
344    notice it is dealing with a mapping governed by a virtual pagetable and
345    proceed to walk the vpagetable much like the hardware would. Suppose there
346    is a valid entry in the vpagetable for the faulting address; then the host
347    kernel simply updates its own pagetable and returns to userspace. If, on
348    the other hand, the search fails, the pagefault is passed on to the vkernel
349    which has the necessary information to update the vpagetable or deliver a
350    signal to the faulting vproc if the access was invalid. Assuming the
351    vpagetable was updated, the next time the vkernel process runs on the
352    vmspace that caused the fault, the host kernel will be able to correct
353    its own pagetable after searching the vpagetable as described above.
354
355    There are a few complications to take into account, however. First of
356    all, any level of the vpagetable might be paged out. This is straightforward
357    to deal with; the code that walks the vpagetable must make sure that a page
358    is resident before it tries to access it. Secondly, the real and virtual
359    kernels must work together to update the accessed and modified bits in the
360    virtual pagetable entries (VPTES). Traditionally, in architecture-defined
361    pagetables, the hardware conveniently sets those bits for us. The hardware
362    knows nothing about vpagetables, though. Ignoring the problem altogether
363    is not a viable solution. The availability of these two bits is necessary
364    in order for the VM subsystem algorithms to be able to decide if a page is
365    heavily used and whether it can be easily reclaimed or not (see [AST06]).
366    Note that the different semantics of the modified and accessed bits mean
367    that we are dealing with two separate problems.
368
369    Keeping track of the accessed bit turns out to require a minimal amount
370    of work. To explain this, we need to give a short, incomplete, description
371    of how the VM subsystem utilizes the accessed bit to keep memory reference
372    statistics for every physical page it manages. When the DragonFly pageout
373    daemon is awakened and begins scanning pages, it first instructs the pmap
374    subsystem to free whatever memory it can that is consumed by process
375    pagetables, updating the physical page reference and modification
376    statistics from the PTES it throws away. Until the next scan, any pages
377    that are referenced will cause a pagefault and the fault code will have
378    to set the accessed bit on the corresponding pte (or vpte). As a result,
379    the hardware is not involved<a name="AEN4"
380    href="vkernel.shtml#FTN.AEN4">[4]</a>. The behavior of the virtual kernel
381    is identical to that just sketched above, except that in this case page
382    faults are more expensive since they must always go through the real kernel.
383
384    While the advisory nature of the accessed bit gives us the flexibility
385    to exchange a little bit of accuracy in the statistics to avoid a
386    considerable loss in performance, this is not an option in emulating the
387    modified bit. If the data has been altered via some mapping the (now
388    "dirty") page cannot be reused at will; it is imperative that the data be
389    stored in the backing object first. The software is not notified when a pte
390    has the modified bit set in the hardware pagetable. To work around this,
391    when a vproc requests a mapping for a page and that said mapping be
392    writable, the host kernel will disallow writes in the pagetable entry
393    that it instantiates. This way, when the vproc tries to modify the page
394    data, a fault will occur and the relevant code will set the modified bit
395    in the vpte. After that, writes on the page can finally be enabled.
396    Naturally, when the vkernel clears the modified bit in the vpagetable it
397    must force the real kernel to invalidate the hardware pte so that it can
398    detect further writes to the page and again set the bit in the vpte, if
399    necessary.
400
401
402 ## Floating Point Context
403
404
405    Another issue that requires special treatment is saving and restoring
406    of the state of the processor's Floating Point Unit (FPU) when switching
407    vprocs. To the real kernel, the FPU context is a per-thread entity. On a
408    thread switch, it is always saved<a name="AEN5"
409    href="vkernel.shtml#FTN.AEN5">[5]</a> and machine-dependent arrangements
410    are made that will force an exception ("device not available" or DNA)
411    the first time that the new thread (or any thread that gets scheduled
412    later) tries to access the FPU<a name="AEN6"
413    href="vkernel.shtml#FTN.AEN6">[6]</a>. This gives the kernel the
414    opportunity to restore the proper FPU context so that floating point
415    computations can proceed as normal.
416
417    Now, the vkernel needs to perform similar tasks if one of its vprocs
418    throws an exception because of missing FPU context. The only difficulty
419    is that it is the host kernel that initially receives the exception. When
420    such a condition occurs, the host kernel must first restore the vkernel
421    thread's FPU state, if another host thread was given ownership of the FPU
422    in the meantime. The virtual kernel, on the other hand, is only interested
423    in the exception if it has some saved context to restore. The correct
424    behavior is obtained by having the vkernel inform the real kernel whether
425    it also needs to handle the DNA exception. This is done by setting a new
426    flag (PGEX_FPFAULT) in the trapframe argument of vmspace_ctl(). Of course,
427    the flag need not be set if the to-be-run virtualized thread is the owner
428    of the currently loaded FPU state. The existence of PGEX_FPFAULT causes
429    the vkernel host thread to be tagged with FP_VIRTFP. If the host kernel
430    notices said tag when handed a "device not available" condition, it will
431    restore the context that was saved for the vkernel thread, if any, before
432    passing the exception on to the vkernel.
433
434 ## Platform drivers
435
436
437    Just like for ports to new hardware platforms, the changes made for
438    vkernel are confined to few parts of the source tree and most of the kernel
439    code is not aware that it is in fact running as a user process. This applies
440    to filesystems, the vfs, the network stack and core kernel code. Hardware
441    device drivers are not needed or wanted and special drivers have been
442    developed to allow the vkernel to communicate with the outside world. In
443    this subsection, we will briefly mention a couple of places in the
444    platform code where the virtual kernel needs to differentiate itself
445    from the host kernel. These examples should make clear how much easier
446    it is to emulate platform devices using the high level primitives
447    provided by the host kernel, than dealing directly with the hardware.
448
449    <b>Timer</b>. The DragonFly kernel works with two timer types. The first
450    type provides an abstraction for a per-CPU timer (called a systimer)
451    implemented on top of a cputimer. The latter is just an interface to a
452    platform-specific timer. The vkernel implements one cputimer using
453    kqueue's EVFILT_TIMER. kqueue is the BSD high performance event
454    notification and filtering facility described in some detail in
455    [Lemon00]. The EVFILT_TIMER filter provides access to a periodic or
456    one-shot timer. In DragonFly, kqueue has been extended with signal-driven
457    I/O support (see [Stevens99]) which, coupled with the a signal mailbox
458    delivery mechanism allows for fast and very low overhead signal
459    reception. The vkernel makes full use of the two extensions.
460
461    <b>Console</b>. The system console is simply the terminal from which
462    the vkernel was executed. It should be mentioned that the vkernel
463    applies special treatment to some of the signals that might be generated
464    by this terminal; for instance, SIGINT will drop the user to the
465    in-kernel debugger.
466
467
468 ## Virtual Device Drivers
469
470    The virtual kernel disk driver exports a standard disk driver interface
471    and provides access to an externally specified file. This file is treated
472    as a disk image and is accessed with a combination of the read(), write()
473    and lseek() system calls. Probably the simplest driver in the kernel
474    tree, the memio driver for /dev/zero included in the comparison.
475
476
477    VKE implements an ethernet interface (in the vkernel) that tunnels all
478    the packets it gets to the corresponding tap interface in the host
479    kernel. It is a typical example of a network interface driver, with the
480    exception that its interrupt routine runs as a response to an event
481    notification by kqueue. A properly configured vke interface is the
482    vkernel's window to the outside world.
483
484 ## Structure of the vpagetable
485
486
487    Software address translation in a memory region governed by a
488    virtual pagetable is <b>very</b> similar to the scheme
489    implemented by 32-bit x86 hardware. In fact, if you are familiar with the
490    latter, this appendix might bore you before you know it.
491
492
493 [[images/vaddr.png]]
494
495
496    Because we want to easily cache vpagetable mappings in the hardware
497    pagetable, the page size is essentially forced to 4KB, although the
498    equivalent of the Intel PSE extension for 4MB pages is also supported.
499    The vpagetable is a two-level forward mapped pagetable where the higher
500    10 bits of a 32-bit virtual address index into a page directory page
501    (specifying a page directory entry, or pde) and the next 10 bits select
502    a pte in the pagetable page pointed to by the pde. The lower 12 bits
503    are the byte offset in the 4KB page (see the preceding figure).
504
505
506    The format of the vpte is presented in the figure below. If this is
507    a page directory, the high 20 bits provide the page frame number of the
508    pagetable page to be consulted next. On a pagetable, the same bits
509    combine with the low 12 bits of the virtual address to form the physical
510    address.
511
512
513 [[images/vpte.png]
514
515
516    Some of the low 12 bits of a vpte have a special meaning.
517
518 * If, at any level in the vpagetable, V is not set, then the address translation fails and the vkernel will have to signal the offending process about it
519 * The PS bit is named after the Page Size extension in the Pentium and later processors. If it is set in a page directory entry, then the high 10 bits of the pde specify the page frame number of a 4MB page and the low 22 bits of the virtual address provide the offset of the physical address in that page.
520 * The R, W, X bits have the obvious meanings. Since the kernel assumes basic x86 functionality, read permission implies execute permission.
521 * The U (user access bit) is currently unimplemented.
522 * The MANAGED bit indicates that there is no reverse-mapping information for the physical page pointed to by this pte. This is usually only true for certain System V shared memory pages.
523 * The G (global bit) is currently unimplemented.
524 * Finally, the WIRED bit is set if the target page has been mlock()ed or is otherwise held in place.
525
526 ## Signal Mailbox
527
528    Signal mailboxes are an alternative signal delivery mechanism that is
529    implemented as an extension to the standard sigaction() system call.
530
531     int sigaction(int signum, const struct sigaction *act, struct sigaction *oldact);
532
533    where
534
535
536     struct sigaction {
537         union {
538                 void (*sa_handler)(int);
539                 int *sa_mailbox;
540         };
541         int sa_flags;
542         /* ... */
543     };
544
545    If a process does a sigaction() system call specifying SA_MAILBOX in
546    sa_flags, then the kernel will deliver the specified signal (signum)
547    by writing its number to the integer pointed to by sa_mailbox. The
548    next system call (or the current one if any) that blocks will return
549    with EINTR. Any further system calls are unaffected and will proceed
550    normally. If the process is running on an alternate vmspace, the
551    kernel forces a switch to the original vmspace before updating the
552    mailbox. If two or more signals are set to deliver to the same mailbox,
553    then successive deliveries overwrite each other so that, after the
554    interruption of the next system call, the value in the mailbox is the
555    number of the last signal delivered. It is expected that after checking
556    a mailbox that has had a signal delivered to it, the user program will
557    clear it by storing a zero in order to be able to detect further
558    occurrences of the corresponding signal.
559
560
561    The reason for the addition of this mechanism was to enable fast signal
562    delivery for the case that the application would just set a non-local
563    variable and return from the signal handler. Since signal handlers can
564    run at any time, it is difficult to determine what state the program is
565    in, therefore, most applications prefer to act in response to a signal
566    (most likely SIGIO) only in selected code locations (typically the main
567    loop). Hence the above case is quite common.
568
569
570    It also involves a large overhead. If the kernel, while servicing a
571    process (e.g. in a system call or page fault) notices that there is
572    a pending signal and that the process catches this signal (i.e. it
573    has specified a signal handler for it and is not currently blocking
574    it), it initiates the delivery procedure. Architecture-specific code
575    saves the current user context (general-purpose registers, instruction
576    and stack pointers, descriptors) in a signal frame structure and
577    pushes this frame onto the user stack<a name="AEN7"
578    href="vkernel.shtml#FTN.AEN7">[7]</a>. It also sets up the process
579    registers so that the signal trampoline will run next. The trampoline
580    is assembler code that is copied by the kernel into the address space
581    of every user process. It is this code that calls the handler
582    procedure and after it returns (assuming it does return), issues a
583    sigreturn() system call. The kernel then arranges for the process to
584    resume running in the specified context (normally the context
585    previously saved).
586
587
588    Compare this procedure with the one followed for delivering a
589    signal that has specified a mailbox. When the kernel notices a
590    pending signal, it copies the appropriate signal number to the
591    specified user address and sets a flag (P_MAILBOX) on the
592    receiving process. If this occurs during a system call, EINTR
593    is returned immediately, otherwise the next system call that attempts
594    to sleep will be interrupted and the P_MAILBOX flag cleared. Either
595    way, only one system call gets interrupted. This way, we save one
596    round trip to userspace and lots of copying of data just to execute
597    a handful of instructions that merely store a preset value to a known
598    memory location.
599
600
601    Also, having the signal handler notify the main application code by
602    setting a variable involves a classic race  when the program has
603    nothing else to do but wait for the signal. Clearly, wasting CPU
604    time in a tight loop testing the value of the variable is not an
605    attractive option. What we want to do is sleep until we are waken
606    by a signal, e.g. with pause(). But suppose that a signal arrives
607    after we test the variable and before we go to sleep; then we may
608    sleep forever.
609
610
611     01    sigset_t io_mask, empty_mask;
612     02    sigemptyset(&amp;empty_mask);
613     03    sigemptyset(&amp;io_mask);
614     04    sigaddset(&amp;io_mask, SIGIO);
615     05    if (sigprocmask(SIG_BLOCK, &amp;io_mask, NULL))
616     06            /* error */
617     07    for (;;) {
618     08            while (event == 0)
619     09                    sigsuspend(&amp;empty_mask);
620     10            event = 0;
621     11            if (sigprocmask(SIG_UNBLOCK, &amp;io_mask, NULL))
622     12                    /* error */
623     13            /* respond to event etc */
624     14            if (sigprocmask(SIG_BLOCK, &amp;io_mask, NULL))
625     15                    /* error */
626     16    }
627
628    The canonical way to avoid this race using the POSIX signal
629    system calls is to block the offending signal before checking
630    the variable (lines 5 and 14 in the listing above). Then, any
631    such signal will not be delivered but will remain in a pending
632    state. Next, block by calling sigsuspend() (l. 9) with an
633    appropriate signal mask as an argument. sigsuspend() puts us
634    to sleep and installs the provided signal mask which,
635    presumably, no longer blocks the signal so that, if it is pending,
636    it will be delivered and wake up the process. Afterwards, it will
637    be a good idea to unblock said signal (l. 11), because sigsuspend()
638    restores the original signal mask when returning.
639
640     01    for (;;) {
641     02            while (event == 0)
642     03                    pause();
643     04            /* window */
644     05            event = 0;
645     06            /* respond to event etc */
646     07    }
647
648    Now lets see how we deal with the situation if we have arranged
649    for the signal to be delivered to a mailbox. In this case, all
650    we have to do is test the mailbox (l. 2). If it is non-zero, a
651    signal has been delivered to it; set it back to zero (l. 5) and
652    proceed to service the event. Signals may be lost if they are
653    delivered just before we reset the value in the mailbox (l. 4),
654    but at this point we are already on the code path to service
655    them, so this is inconsequential. If the mailbox was zero, we
656    just block (l. 3). If a signal has arrived between the check
657    and our going to sleep, the system call will return immediately
658    with EINTR, as it will if a signal is delivered to us after we
659    block. Notice how the signal mailbox semantics make this a
660    non-issue allowing us to write straightforward code. Saving
661    two system calls per iteration (l. 11,14 in the first listing)
662    doesn't hurt either.
663
664
665 ## Bibliography
666
667
668    [McKusick04] *The Design and Implementation of the FreeBSD 
669    Operating System*, Kirk McKusick and George Neville-Neil
670
671    [Dillon00] *<http://www.freebsd.org/doc/en/articles/vm-design/>
672        Design elements of the FreeBSD VM system* Matthew Dillon
673
674    [Lemon00]  *<http://people.freebsd.org/~jlemon/papers/kqueue.pdf>
675        Kqueue: A generic and scalable event notification facility*
676    Jonathan Lemon
677
678    [AST06] *Operating Systems Design and Implementation*,
679    Andrew Tanenbaum and Albert Woodhull.
680
681    [Provos03] *Improving Host Security with System Call Policies*
682    Niels Provos
683
684    [Stevens99] *UNIX Network Programming, Volume 1: Sockets and XTI*,
685    Richard Stevens.
686
687
688 ## Notes
689
690
691 <table border="0">
692
693   <tr>
694       <td align="LEFT" valign="TOP" width="5%">
695         <a name="FTN.AEN1" 
696             href="vkernel.shtml#AEN1">[1]
697         </a>
698       </td>
699       <td align="LEFT" valign="TOP">
700         <p>
701            There are of course other alternatives, the most obvious one being
702            having one process for the virtual kernel and another for contained
703            processes, which is mostly equivalent to the choice made in
704            DragonFly.
705         </p>
706       </td>
707   </tr>
708   <tr>
709       <td align="LEFT" valign="TOP" width="5%">
710         <a name="FTN.AEN2" 
711             href="vkernel.shtml#AEN2">[2]
712         </a>
713       </td>
714       <td align="LEFT" valign="TOP">
715         <p>
716            A process running under a virtual kernel will also be referred to
717            as a "vproc" to distinguish it from host kernel processes.
718         </p>
719       </td>
720   </tr>
721   <tr>
722       <td align="LEFT" valign="TOP" width="5%">
723         <a name="FTN.AEN3" 
724             href="vkernel.shtml#AEN3">[3]
725         </a>
726       </td>
727       <td align="LEFT" valign="TOP">
728         <p>
729            The small matter of the actual data belonging to the vproc is not
730            an issue, but you will have to wait until we get to the RAM file
731            in the next subsection to see why.
732         </p>
733       </td>
734   </tr>
735   <tr>
736       <td align="LEFT" valign="TOP" width="5%">
737         <a name="FTN.AEN4" 
738             href="vkernel.shtml#AEN4">[4]
739         </a>
740       </td>
741       <td align="LEFT" valign="TOP">
742         <p>
743           Well not really, but a thorough VM walkthrough is out
744           of scope here.
745         </p>
746       </td>
747   </tr>
748   <tr>
749       <td align="LEFT" valign="TOP" width="5%">
750         <a name="FTN.AEN5" 
751             href="vkernel.shtml#AEN5">[5]
752         </a>
753       </td>
754       <td align="LEFT" valign="TOP">
755         <p>
756           This is not optimal; x86 hardware supports fully lazy FPU save, but
757           the current implementation does not take advantage of that yet.
758         </p>
759       </td>
760   </tr>
761   <tr>
762       <td align="LEFT" valign="TOP" width="5%">
763         <a name="FTN.AEN6" 
764             href="vkernel.shtml#AEN6">[6]
765         </a>
766       </td>
767       <td align="LEFT" valign="TOP">
768         <p>
769           The kernel will occasionally make use of the FPU itself, but this
770           does not directly affect the vkernel related code paths.
771         </p>
772       </td>
773   </tr>
774   <tr>
775       <td align="LEFT" valign="TOP" width="5%">
776         <a name="FTN.AEN7"
777             href="vkernel.shtml#AEN7">[7]
778         </a>
779       </td>
780       <td align="LEFT" valign="TOP">
781         <p>
782           Or any alternative stack the user has designated for signal delivery.
783         </p>
784       </td>
785   </tr>
786 </table>
787