vsta

Overview
Login

                      An Overview of the VSTa Microkernel
       
Abstact

   VSTa is an experimental kernel which attempts to blend the design of a
   microkernel with the system organization of Plan 9. The result is a
   small privileged kernel running user-mode tasks to provide system  
   services such as device drivers, filesystems, and name registry. Like
   Plan 9, each service provides a filesystem-like interface.

=== Motivation ===
   
   Two operating systems have emerged in recent years which show
   considerable promise. The POSIX-conforming QNX operating system (1 )
   is a relatively "clean" microkernel, with a 4K executive and most
   traditional system functions running as user-mode processes.
   Meanwhile, Plan 9 (2 ) has emerged as a next-generation view of
   computing from the original architects of UNIX. While each system
   represents significant new system functionality, the frustration has
   been in the proprietary nature of each system--synthesis and
   experimentation by an outside party is difficult or impossible. 

=== A Platform for Experimentation ===

==== A New Source Base ====
     
   With these interesting new ideas to try, and without a suitable code
   base on which to try them, the only option was to wait for the authors
   of these systems to publish more papers. When the author recently had
   the opportunity to take a 6 month sabbatical, the result was the VSTa
   operating system, written from scratch. VSTa is a non-proprietary
   source base permitting experimentation in many of the areas first
   broached by Plan 9 and QNX. While the full design is beyond the scope
   of this overview, several general design decisions are worth
   mentioning.
       
==== Symmetric Multiprocessing ====
       
   Microkernels have a surprising interaction with multi-processing
   support. In a monolithic kernel, vast amounts of system functionality
   all reside in the same kernel address space. When the kernel first
   supports multiprocessing, all of this code must be revamped to handle
   multiple parallel threads of execution. (3 ) Much of this "kernel"
   code is moved out to individual tasks in a microkernel organization.
   With such an organizational change, the job of converting this code to
   the appropriate level of parallelism is divided. A process can be
   single-threaded; it can be marked serially-reentrant (multiple
   threads, but only one running in the address space at a time--like a
   uniprocessor UNIX kernel); or the threads can run fully in parallel.
   The decision is made per-process.
   
   While real-time attributes are discussed later, it is worth noting
   that the job of writing code to operate correctly in the presence of
   parallel CPUs has some synergy with the goal of allowing kernel
   preemption. In both cases the programmer must always consider the
   possibility of the same code paths being entered and reentered at
   arbitrary points. Kernel preemption imposes additional demands,
   especially in code paths like exit().
   
   With the smaller kernels achieved by moving so much functionality out
   to processes, the remaining code is much easier to design, code, and
   test. Since writing parallel, preemptive code is harder to write than
   traditional single-threaded code,(4 ) the reduction in source size is
   desirable. 

   VSTa's machine-independent layers were written for a shared memory
   symmetric multiprocessor. A P/V semaphore interface is used for
   sleep-oriented interlocks. A P/V spinlock is used for spin-oriented
   interlocks, and also used to interlock against interrupt service
   procedures. The machine-dependent code, sadly, is only written for a
   uniprocessor i386--the only machine available to the author.
   
==== Real Time Facilities ====
   
   While VSTa is not a real-time operating system in itself, numerous
   features associated with real-time systems offer themselves naturally
   to solve microkernel design issues. Process memory locking is
   necessary in order to allow a disk driver task to run as a user
   process (as otherwise, of course, you will deadlock when your disk
   driver tries to demand page in a piece of itself from swap.)
   Non-degrading priorities are necessary to permit critical system
   services to respond to many users without being penalized for their
   apparent heavy CPU use. Low-latency process dispatch is necessary to 
   allow interrupt service code to run in a deterministic amount of time
   after a device event--especially important in the case of heavy data 
   sources like dumb serial ports and LAN interfaces.
   
   VSTa was designed with memory locking and real-time priorities. Except
   when a spinlock is held, a thread is preemptable even when running in
   kernel mode. Most spin-locks do not involve interrupt-driven code; for
   these, interrupts are still accepted and queued even while the
   spinlock is held--preemption to a real-time process is delayed until
   the spinlock is released.
   
==== Scheduling ====
   
   VSTa uses a very conventional priority-driven scheduler for real-time
   processes. However, most processes in the system run under an
   interactive, timesharing scheduling algorithm with unusual properties.
   The scheduler is driven from a tree where runnable processes are
   leafs. The internal nodes represent the partioning of groups of
   processes into percentage "slices" of the CPU pool (much like a fair
   share scheduler), with the lowest nodes containing the threads within
   a process.
   
   This organization has two desirable properties. First, it allows users
   and groups of users to partition the CPU resources fairly among groups
   based on local policy. With the ratio of CPUs to users approaching
   1:1, the classic departmental computing scenario may never arise. But
   it can be convenient to guarantee that some particular server will
   never consume more than half the CPU time (unless it would otherwise
   be idle.)
   
   Such a scheduler also provides many of the properties of a gang
   scheduler. When the classic UNIX scheduling algo- rithm is used to run
   closely cooperating processes, its global nature allows any runnable
   processes to compete directly with the threads. Since all threads
   under VSTa exist under a common scheduling node, the threads can  
   voluntarily relinquish the CPU; the CPU time relinquished remains
   within the "pool" of the node, so only other related threads under the
   node will complete for it. (5 )
   
==== Messaging ====
   
   In a microkernel, the goal is to identify a small, cohesive set of 
   kernel functions upon which all current and desired future system    
   functions can be implemented as user mode tasks. Like Plan 9 and QNX,
   VSTa uses a messaging engine as the underlying microkernel mechanism.
   VSTa, like QNX, supports scatter/gather lists for messages. VSTa,
   however, had to use significantly different techniques than QNX--VSTa
   supports virtual memory, where QNX can always assume the presence of  
   physical memory for its messages. ( 6 )
   
   VSTa structures the exchange of messages between client and server. A
   would-be client requests connection; a connection indication including
   the would-be client's capabilities is presented to the server. The
   server accepts or rejects the connection. If accepted, the client can
   then send messages. Each element in the scatter/gather list of the
   message is made available in the server's address space when the
   server receives the message. The contents are mapped on demand as the
   server makes reference to the data. Alternatively, the server can
   merely pass the message on without touching its contents (for
   instance, a middle module in a protocol might add a new initial buffer
   without needing to examine the contents being encapsulated.) The data
   was never mapped or read; the passing of data in these cases is thus
   quite efficient.
   
   If the server returns data it is copied into the client's address
   space before the client's request is completed. It would be desirable 
   to use the same "lazy" semantics for message mapping as the server,   
   but this would make it difficult for the server to know when the  
   client is done using the data. Techniques involving the "handing off"
   of pages of data are possible, but many servers would then have to
   copy data into new pages; any performance benefits can easily be lost.
   
==== Filesystem Interface ====
   
   Plan 9 imposes a filesystem-like interface onto all objects in the
   system. QNX permits a server to provide a filesystem interface, but 
   does not pursue such a thing as a goal in its own right. Plan 9 allows
   each process to build its own filesystem view by attaching objects at
   arbitrary points in its filesystem namespace. QNX provides a global
   view, but does not implement these mount points in the classic UNIX   
   (and Plan 9) way. QNX instead looks at its "mount table" as a simple
   mapping of leading strings for mount points, and a corresponding
   server.
   
   VSTa borrows much from each operating system. Like Plan 9, all servers
   provide their services in terms of a filesystem-like interface. The  
   format of the messages sent through the microkernel is standard and  
   implements a filesystem protocol similar to Plan 9's 9P protocol. ( 7
   ) VSTa use a string table approach like QNX, although the table is
   private to each process. In fact, the table and its interfaces are all
   entirely with the C library; neither the VSTa kernel nor its servers  
   have any control over a process' mount table.
   
==== Capabilities ====
   
   VSTa breaks from current operating systems in the way it structures
   capabilities. The desire was to allow a hierarchy of abilities, and to
   allow a given user to create sub-abilities without the intervention of
   a system manager. The resulting system is powerful, but does not map
   well onto a POSIX interface.
   
   In VSTa, an ability is represented as a dot-separated sequence of
   numbers, called an ID. The numbers become more specific reading from  
   left to right. An object in VSTa (8 ) has a label with such a label, 
   and for each position, another bitmask indicating what actions are  
   permitted (It also has a default access, which is just OR'ed in with
   any other bits granted.) For instance, assuming no default:
{{{
                    1.        2.        1.        3
                    EXEC READ WRITE     DELETE
}}}
   Would indicate that someone possessing 5.3 could not access the  
   object; someone with 1.5 could only execute it (a mismatch
   discontinues the accumulation). A hierarchy of "super users" is gained
   with the last rule: someone with 1.2 would gain read, write, excute,  
   and delete abilities! When someone possesses an ID which matches a
   label to the length of the ID, the ID is said to dominate the label.
   The remaining bits are OR'ed in as if the match continued to the end
   of the label. The superuser of a VSTa system, therefore, is someone
   who has an ID of length 0.
   
   One can forge a new ID; it is permitted if at least one of the current
   IDs dominates the new ID to be forged. Thus, someone who logs in with
   the ability 5.7 could store all sensitive data with a label of, say,  
   5.7.1 with all access requiring a full match:
{{{
                     5.  7.   1
                    (0)  (0)  READ|WRITE|EXECUTE|DELETE
}}}
   If this same user then wanted to run a somewhat suspect application,  
   he could forge a new ID of 5.7.2, disable his current IDs, and run the  
   application. Since the application does not possess an ID which allows
   access to 5.7.1, the user's data is protected. Because such ID
   manipulation can be done by any user, fine-grained protection designs
   are possible in a way which UNIX forbids without extensive use of
   super-user powers.
   
=== Current State ===
  
   The VSTa kernel currently comprises 2700 lines of portable C, 750
   lines of i386-specific C (using the "count the semicolons" method),
   and 400 lines of i386 assembly code. It compiles into roughly 50K of  
   32-bit i386 object code, with another 10K of data. Device servers
   exist for the keyboard, screen, floppy disk, ST-506 hard disk, and  
   real-time clock. Servers also exist for a flat contiguous-allocation
   filesystem, a DOS filesystem, an environment server (used by
   getenv()/setenv()), a swap manager (to manage multiple swap partitions
   and permit dynamic swap partition additions and deletions), and a     
   service registry database.
   
   The system boots and runs on top of either a flat contiguous
   filesystem or a DOS filesystem. Further device drivers and filesystems
   can be started and stopped from the command interpreter. The system
   does demand-paging of executables and does page-stealing when memory
   becomes scarce using a two-handed clock algorithm.
   
   At the application level, a C library and include files have been
   written to conform to the POSIX specification. GNU C, as, and ld have 
   been ported and run natively under VSTa. Emacs and other amenities are
   also available. As each port identifies a missing area, it is coded up
   based on the POSIX standard. Thus, the system deviates from POSIX more
   by omission than otherwise. The exception is the area of protection,
   where this incompatibility was foreseen and accepted at the conception
   of the project.
   
=== Future Projects ===
   
   It is satisfying to have a freely accessible environment on which to  
   prototype further facilities. Several categories of experimentation
   are of active interest to the author.
          
==== Performance ====
   
   VSTa provides very good interactive and compilation performance on a    
   single-user 25 Mhz i386 PC. However, several areas could be
   streamlined. For small buffers of data the current page-mapping
   messaging techniques are overkill; it would be much cheaper to just  
   copy the actual data around. A "fast path" for small buffers could
   shorten code paths for keystrokes, RS-232 bytes, and small writes to
   the screen. This must be traded off against the additional
   complication in the messaging machinery--but a prototype is certainly
   called for.
   
   Some servers, for the sake of simplicity, do not take full advantage
   of the scatter/gather functions. At least the disk drivers and
   filesystems should be carefully optimized to make best use of
   scatter/gather lists.
   
==== Clustering ====
   
   Accessing services through messages immediately leads one to ponder   
   the possibilities of remote access. The scatter/gather organization
   and lazy referencing of VSTa should make it possible to move the data
   from a client to the network interface without any intermediate
   copying of the data. Incoming connections must be mapped into a local 
   VSTa server connection; the networking daemon must forge appropriate
   IDs for the client. A mapping database used by the daemon might
   suffice:
{{{
                    theirbox:1.* -> mybox:99.*
                    trustedbox:* -> mybox:*
                    *:* -> REJECT
}}}
   This would allow both access control (you must have 1.* on theirbox to
   log in; trustedbox has the same accounts as us) and dynamic
   translation of IDs between systems.
   
   The name server is currently a local entity. However, once remote
   service access is available, it is a simple matter to import other
   node's name servers and use them locally. Because VSTa supports Plan
   9-style union directories, you could even mount each name server at
   the same point in your local filesystem name space, with your local   
   name server coming first. Ultimately, a network-aware database system
   must be implemented, but it is interesting to ponder how far these
   simple and powerful Plan 9 techniques can take one.
  
=== Acknowledgements ===
   
   The knowledge and vision of the Plan 9 and QNX developers is
   appreciated, both in their papers and on Usenet. This project would
   not have been possible without the outstanding tools from the Free   
   Software Foundation--especially the GNU C compiler and its
   accompanying utilities. Finally, I would like to thank the Bill and 
   Lynne Jolitz for the 386BSD source code. Its availability as a
   reference helped me unravel many an intricacy of the i386.
------
   
   Footnotes: 
    1. Hildebrand, Architectural Overview of QNX
    2. Pike et al, The Plan 9 Operating System
    3. Operating systems like System V.4.2 MP try to mitigate this with
       serializing code "wrappers." Few people seriously present this as
       an appropriate solution, or even an acceptable temporary fix.
    4. The author's estimate is 2-3 times harder.
    5. Of course, if there are no runnable threads, the CPU time will be 
       parceled out elsewhere in the scheduling tree.
    6. QNX designers have designed, but not yet implemented, a virtual  
       memory capability for their system.
    7. The protocol would have been 9P, except that it was designed
       before this level of detail was available for Plan 9.
    8. More precisely, the objects offered by standard VSTa servers.
------