Copyright © 1991, Dr. Dobb's Journal

Copyright © 1991, Dr. Dobb's Journal

Copyright © 1991, Dr. Dobb's Journal

Copyright © 1991, Dr. Dobb's Journal

Copyright © 1991, Dr. Dobb's Journal

This article contains the following executables: 386BSD.891

William Frederick Jolitz and Lynne Greer Jolitz

In the previous article we examined the machine-dependent layer initialization of the "stripped-down" kernel -- the machine-dependent portion of the kernel which installs the kernel into the position to execute processes (via the bootstrap procedure) and prepares the system for initialization of the minimum machine-independent portions of the kernel (processes, files, and pertinent tables). We viewed our 386BSD kernel as a kind of "virtual machine" (not to be confused with the "virtual" in "virtual memory"), where functions underlie other functions transparently. When initialized, the system can use portions that require little direction to initialize even larger portions. Thus, this virtual machine assembles itself tool by tool, much like a set of Russian dolls. The machine-dependent kernel initialization is the innermost of the dolls -- the kernel of the kernel around which all is built.

We now extend the layered model further, by incrementally turning on all its internal services using the kernel's main( ) procedure. In other words, this next outer layer will be built by the kernel's main( ) procedure, which in turn initializes higher-level portions of the kernel. This is the second major milestone of our UNIX port -- the halcyon point where most of the kernel services and data structures are initialized.

At this stage, we'll review key elements of the BSD kernel which will be invoked in future articles. We'll briefly examine the interrelationships between some of these elements, in order to delineate the broader picture a bit more and illuminate some important ideas in UNIX system design.

A basic understanding of the entire system demands a return to the layered model described last month. In brief, the kernel is a program which runs in supervisor mode on the 386 (or "Ring 0" -- for a review on rings, see "The Standalone System" DDJ March 1991). The kernel implements the primitives, called "system calls," of UNIX and manages the environment and other characteristics of the many user "processes" run to provide functionality to the system. (Each user process runs in a separate "Ring 3" address space.) Only processes running in their protected address spaces are truly visible to the UNIX user, as they provide the requested functionality (a command processor or "shell," a compiler, an editor, and so on). These processes constitute the outermost layer of our layered operating system model. System calls and various processor exceptions (page fault, device interrupt, overflow , and so on) are methods by which a process either directly or indirectly enters the UNIX kernel to request services. In this way, the kernel acts as a transparent (not statically-linked) subroutine library that functions as a kind of virtual machine. It's as if the microprocessor hardware itself actually did a whole read( ) system call request in the single lcall instruction used to signal a system call. (For further information, see Leffler, et al, The Design and Implementation of the 4.3BSD UNIX Operation System, Chapter 3: Kernel Services, page 43-45, Addison-Wesley, 1989.)

Layers within the kernel are split into the (mostly) machine-independent "top" half, and the (mostly) machine-dependent "bottom" half. The top half synchronously processes exceptions and system calls and blocks a currently executing process when an event causes a delay, such as a temporary memory shortage, or a device input/output operation. Blocking a process permits the kernel to run another delayed process, allowing multiple processes to appear to run concurrently on a single processor. The bottom half, in contrast, asynchronously processes device interrupts that are never allowed to be blocked. Device interrupts can be viewed, therefore, as high-priority, real-time tasks brought to life by a hardware interrupt to render the necessary effect and then exit the stage. They then return the kernel from the interrupt back to whatever code was running before the interrupt occurred. In a way, device interrupts are practically stateless and serve primarily to signal the occurrence of an external event to the synchronous "top" layers. Note, however, that such notifications will only take effect when the top layers allow preemption -- in the UNIX model, this is only allowed at certain points when operating in the "top" layers (generally, when returning to the user process from the kernel, or when blocking for an event).

The impact of the layered model on our 386BSD port cannot be understated. Our 386BSD system can be broken up into modular subsystems that have neat boundaries and work by a handful of simple rules. One rule which we live by is the aforementioned low-level asynchronous, top-level synchronous arrangement. For example, if we describe some code that must block for a resource, we are already restricted to a discussion of the top layer. Likewise, if we describe an event that occurs as a result of a peripheral completing an operation, rest assured it resides within the lower layers. This organization allows us to break the whole into parts we can handle; otherwise we quickly become mired in complexity.

Understanding and following the rules inherent in our layered model greatly simplifies UNIX kernel design. Without these rules, we would need a lot more "critical region" code dealing with arbitrary preemption. These same rules, however, also limit our ability to easily implement UNIX in real-time environments. (For example, Ethernet delays are sometimes unpredictable.) Some versions of UNIX attempt to improve real-time performance by minimizing worst-case delays through the judicious addition of blocks to allow high-priority processes to run, but this is not a simple fix.

There is reason to believe that the synchronous design of UNIX limits its performance with disk file writes. In a paper presented at the Summer 1990 USENIX Technical Conference, "Why Aren't Operating Systems Getting Faster as Fast as Hardware?" (USENIX Technical Proceedings, page 247) John Osterhout of the University of California at Berkeley discusses the need to "decouple filesystem...operations that modify files," as synchronous writes are required for filesystem stability, consistency, and crash recovery. This is currently not a great problem, because filesystem reads (the majority of operations) can be elegantly cached and anticipated. Still, this raises questions about the current UNIX model and may result in its revision.

Last month, we discussed bottom-level initialization, where the Interrupt Descriptor Table (IDT), a 386 hardware interface to interrupts and exceptions, was wired into code entry points (IDTVEC (XXX)). This is how 386BSD glues the hardware interrupts onto the bottom layer. In addition, some of the top-layer interfaces were also established. Now we need to build and initialize the other top-layer kernel functions in our BSD kernel main( ). With the kernel initialized, we must get the ball rolling by bootstrapping user processes to add functionality in the form of services (such as a command processor that will allow useful work to be done with our 386BSD system).

To implement the UNIX model, we refer to many items -- all of which are managed by the top layers and referenced by lower layers. These include processes, address spaces, files, filesystems, buffers, messages, signals, credentials, and others. They are grouped into a global set managed by the kernel on behalf of all processes, and a private set managed by the process for the benefit of the program running within the process.

The global set of objects is split into a shared database (proc, inode, buffer cache, and file structures), as well as a group of consumable resources (memory pages, data buffers, and heap storage). The shared database objects use methods for which items are searched, contended, modified, allocated, deleted, and linked together; all in a preemptible fashion, since many processes may attempt simultaneous access to these objects during multitasking operation. These databases must be initialized, allocated the appropriate minimum requirements for operation, and linked as the system requires.

The UNIX paradigm is "process-centric," that is, most of the activity is built around the current running process. With the exception of necessary functions such as scheduling or interprocess communications (which require knowledge of multiple processes), most of the kernel is written without any explicit knowledge of any process save the running one. Thus, an understanding of how a process is provided services tells you the bulk of what the kernel does. Very little of the code and data structures are explicitly aimed at this "global" view.

The focus of kernel activity is the list of processes (the "proc table"). Processes are linked into various lists so they can locate other processes through various relationships. As the kernel operates, processes migrate onto and off of different lists. While the process structure is not globally allocated, the list of entries is itself a global resource. Each system call and exception is directed to operate on a given process. As such, the BSD kernel uses the struct proc entry of each process as the key data structure that indexes all related kernel entities of a process.

Processes operate synchronously, processing a system call item by item. If they need to wait for either a resource or an external event, they must block with a sleep( ) function call to await changes and give up the processor. Elsewhere in the kernel, a corresponding wakeup( ) function call will awaken the snoozing process, preparing the process to run when next possible. While sleep gives up the processor, wakeup schedules processes to run -- it does not transfer to processes nor even insure that the process will ever run. Wakeup calls are idempotent. Many can occur before the process actually starts to run.

A process can only wait on a single event at a time, and is usually uniquely identified by the kernel address of the object for which it waits. This event is stored in the p_wchan field of the process's proc slot. Events themselves don't require additional space when active, so secondary or recursive effects (as might happen in the case of a block on memory starvation) don't occur.

As the 386BSD system and its drivers are all written with these event mechanisms in place, we are potentially multitasking from the start, although until we replicate (or "fork") to create multiple processes, no actual context switches occur to different processes. (There are no other processes to switch to.) Instead, the processor is allowed to idle, waiting for events. In the UNIX perspective, we always try to organize the general case so that it functions seamlessly on initialization, in order to leverage it early. An example of this approach can be observed in the mechanisms that provide diskless operation, where we must provide a root filesystem over a network connection before we have a filesystem to run the programs that normally initialize the network and locate the filesystem on the network. (Got it? Good.)

Machine-independent initialization is begun by wiring up a "process zero." In the previous article, we took care in the assembly language initialization to craft a separate region for the kernel stack -- this will be our "Oth" process kernel stack. We then commence the creation and attachment of the necessary auxiliary data structures that process 0 will use during the lifetime of our system. No process is specially considered, so all must have these structures present and consistent with other structures in the kernel. To avoid recursive problems with the "virgin" birth, the first process must be hand-wired with the barest of necessities, and space for the auxiliary structures must be allocated statically. In fact, we will find that process 0 will attempt to become eternal, so it's actually more costly to dynamically allocate space for it than to do so statically!

Having made a 0th process, we now must create a process list to which the system can refer in a global fashion, to locate, add, delete, and modify processes. This is not really complicated, because at this point all of the queue pointers point either at our just-born process O or at "nil." At this stage, all process-related operations can now be activated, although only for statically-allocated processes (which is not very interesting -- we need to turn on the virtual memory and storage allocation functions for something more useful).

UNIX likes to have access to herds of processes, many appearing to run simultaneously,to do its bidding. As a result, we need to rapidly flit between processes running for a brief slice of time before blocking. To make this a low-cost operation, we use a priority-ordered run queue of process pointers to rapidly select the next process to run when it's time to switch. This is now initialized to permit the context switch code to be run (as it will be called when we block for I/O operations).

As mentioned in the previous article, 386BSD has been rewritten to use a new virtual memory system with greater capabilities. This new package, derived from MACH version 2, possesses generalized mechanisms which allow management of multiple regions of virtual memory within the user processes and kernel itself, thus avoiding the arbitrary and idiosyncratic methods used in earlier Berkeley UNIX virtual memory systems. This "new vm" is composed of machine-dependent (physical map) and machine-independent (virtual map) portions.

This new virtual memory system was originally conceived in 1985 at Carnegie-Mellon University by Avadis Tevanian (now at Next) and Michael Wayne Young to provide an easily retargettable virtual memory system with the modern functionality required by the MACH operating system implementation. It serves as the basis for virtual memory systems in current MACH implementations, OSF/1, and Berkeley UNIX.

To initialize the virtual memory system, all remaining pages of physical memory (not occupied by the kernel program itself) are each first allocated a resident page data structure (vm_page). Queues of free pages are created so that pages can be allocated from them.

Next, virtual memory objects are created to provide an abstraction on which to hang collections of physical pages. To allocate virtual address space, virtual memory maps are also created to identify valid regions of virtual memory and the characteristics of these regions. The virtual memory system will associate virtual memory objects containing physical pages of memory with portions of address space mapped by a virtual memory map, as needed.

We then initialize the kernel's virtual address map and provide a mechanism to allocate portions of "wired down" memory to the kernel's address space with a function called kmem_alloc. This function, the most primitive of storage allocators, allows us to allocate pages of memory dynamically in the granularity of pages at a time.

With a memory allocator present, the initialization of the physical map (pmap) portion of the system is completed, allocating tables that will be used by the physical map module to track the association of physical pages of memory with the hardware address translation mechanisms data structures (Page Directory Table and Page Table Pages on the 386). At this point, the virtual memory system can allocate multiple address spaces and on-fault physical pages to legitimate references to previously mapped virtual map regions.

In designing a virtual memory system, the common drawback is the inherent complexity required. Not only does the system have to allocate virtual address space, but it also needs to allocate pages of memory to "back up" the virtual space. On some systems, the virtual memory system allocates space, grabs some pages, and manually wires them into the address translation map. With the new 386BSD virtual memory system, when you ask for memory from a memory allocator, both virtual and physical memory are allocated. In other words, you always get the memory in an address space.

Another point to consider when designing virtual memory systems: Suppose we share the same pages in different processes. We may wish to "back up" shared pages that might be modified incrementally -- thus, unique pages need be created only when the contents of a page change. This mechanism, called "copy on write," allows us to postpone or avoid entirely modifying a process's memory. Only a mechanism to track changes is required. This is accomplished by copying virtual memory objects that shadow the original object.

To complete the initialization of the virtual memory system, we must now initialize and activate "pagers," the software that reads in the contents of pages from the filesystem and stages pages in and out of processor memory to disk when we run short of "fast" storage. Pagers interface with external forms of information, such as local filesystems, disk swap partitions, disk drives, network filesystems, and the like.

Besides allocating pages of memory from the virtual memory system, we need a means of allocating smaller granularity objects. Many data structures, possessing short and long lifetime and generally in the order of 32 bytes in size, are allocated by the kernel on an "as needed" basis. UNIX provides user processes with a malloc( ) memory allocator for general-purpose memory allocation; the same type of function resides in the BSD kernel. This provides for a global heap store -- so called because everything is kept in a heap, all piled together!

Kernel malloc( ) uses the virtual memory system to obtain actual storage to manage (called an "arena"). This storage area encompasses the heap itself. After the vm system has been activated, we initialize our allocator. From this point on, we can dynamically allocate data structures. Older versions of BSD used statically allocated tables that minimally required the system to be patched and rebooted if a resource was overutilized -- sometimes the system even had to be recompiled from its source code. With dynamic allocation, the configuration can be changed on a live system and the effect observed immediately.

Once enough of the system services are established, we can proceed to scale and configure tables appropriate for operation, among them the buffer cache and character list (clist) structures. While these are usually similar on most systems, a few have private buffer memory pools associated with devices (such as a disk array with onboard RAM) that should be specially arranged prior to system operation. Currently, the amount of disk buffering memory is chosen as a fixed percentage of memory at boot time, but work is underway to allow a more dynamic allocation scheme.

Next, we configure( ) devices in the system by walking a table of devices -- calling each device driver's probe routine with the parameters for each device and testing for the presence of each recorded device. Not all devices need be present. In fact, alternative addresses may be recorded for the same device. If the device is present, a probe routine will return true, with a subsequent call to the corresponding attach( ) routine to allocate resources (memory, interrupts, and so on) for the device and wire it into 386BSD. (In future articles, we will discuss how 386BSD dynamically structures the interrupt control devices on-the-fly.)

After cpu_startup( ), the system begins to schedule processes. We allow for this by enabling the rescheduling clock. This clock periodically interrupts the kernel and adjusts the priority of other processes that might compete for use of the processor.

We next initialize the virtual filesystem layer. We make our first reference to it by mounting the root filesystem and marking it as the top-level point from which to resolve filename references. The root filesystem, like other filesystems, can be of many different types. However, as this request is honored by code that calls successively lower-layer functions, we ultimately get to the bottom layers in the form of a device driver that extracts from the disk or network the external information of the filesystem on which all files are stored. If the root filesystem cannot be located, 386-BSD abruptly terminates.

In this article, we have just touched on the layout of our generic 386BSD system (4.3 > x < 4.4), and introduced many of the mechanisms, data structures, and relationships between them. Our point is not to provide exhaustive descriptions of the operation of BSD in general, but to provide enough background to understand the operation of 386-related code, as well as design choices.

To accomplish this task, we've purposely not described much of the detail of the various BSD subsystems; it is sufficient at this point if you have obtained some notion of what they are and why we need to turn them on in the order that we do. In conducting a port, one actually makes it through this body of code pretty quickly. It is the ticklish operations of fork, exec, and process context switching that get the first shakedown journey and surprises. Also, when the kernel design has been refined, and much of this code revised, this area continues to present challenges.

In the next article, we will leave the hand-waving descriptions of process switching behind and dig into some actual code. In particular, we shall examine sleep( ), wakeup( ), and swtch( ), and how the three of these bring off the illusion of multiple simultaneous process execution on a sole processor. We will also delve into why the UNIX paradigm shifts comparatively easily when it comes to multitasking, and why it's been such a long uphill climb to move others (notably MS-DOS and Finder) into preemptible multitasking. Finally, we will discuss some of the requirements for the extensions needed to support multiprocessor and multithreaded operation in the monolithic 386BSD kernel.

Copyright © 1991, Dr. Dobb's Journal