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.791

William Frederick Jolitz and Lynne Greer Jolitz

Much has been made of the preparations we have required before we could embark on our present project. While that's all well and good, at some point we really would like to get on with our adventure and start the main assault -- the kernel itself. Our roundabout development of tools and equipment allowed us to scope out the weak points in the 386BSD specification, with the added bonus of enhancing our experience and confidence. By following a disciplined set of guidelines and procedures, we minimized one of the most demoralizing activities of all -- trying to build our system without any idea as to where the bugs (or failure modes) lie, especially those enormously irritating compiler bugs induced by driver implementation bugs.

Now we arrive at the point in which we would like to create a "strippeddown" kernel. At this stage of our work, our primary concern is with the machine-dependent portions of the kernel that install it into the position to execute processes (via the bootstrap procedure) and prepare the system for initialization of the minimum machine-independent portions of the kernel (processes, files, and pertinent tables).

Our 386BSD kernel is a kind of "virtual machine" (not to be confused with the "virtual" in "virtual memory"), where functions underlie other functions transparently. When the system is initialized, it 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. The next outer layer will then be built by the kernel's main( ) procedure (to be discussed later), which in turn initializes higher-level portions of the kernel.

While our basic approach toward "wiring" the 386 for operation with the machine independent BSD kernel is similar to that of our standalone system (see DDJ March 1991), the details are now very important. In fact, we've changed so much since our discussion of the 386BSD specification (DDJ January 1991) that even the specification needs to be revised in several key areas such as the virtual memory system and per-process data structure. In addition, the most recent versions of 386BSD (less than a month old) incorporate the unique feature of the 386 architecture in a form of "recursive" paging which not only leverages resources to the hilt, but also reduces complexity enormously. (See text box "Brief Notes: 386BSD Recursive Paging.")

The structure of the BSD UNIX system is akin to that of an onion. Consisting of layer upon layer, the outside layers of the BSD onion are those processes visible to the computer "user," while the inner layers hide processes the user needn't see, such as those relating to the hardware. (This can also be called the "Almond Roca" kernel, if you prefer sweets.)

The operating system kernel lies in the innermost layer. Its primary responsibility is to provide the appropriate level of utility services upon which other programs and facilities are built. The kernel itself consists of an inner "machine-dependent" portion and an outer "machine-independent" portion. The center of the onion could be considered the raw hardware itself.

In UNIX parlance, the kernel is typically divided into the "high kernel" and the "low kernel." The high kernel is concerned with UNIX abstractions, such as files, processes, and other related objects. The low kernel, in contrast, is concerned with the functionality of the kernel -- how to implement the abstractions with machine-dependent mechanisms for operation.

Despite the "purity of essence" debates, UNIX has grown like a weed. (Any undesired plant is a weed, and one could say the same about UNIX, at least initially -- just ask DEC or IBM or Apple.) It has grown because the ever-increasing hunger for applications, and the functional infrastructure needed to support them, to simplify or enhance work is insatiable. Doubtlessly, UNIX will continue to grow in size and popularity (although some of us would prefer it grow in a graceful and planned manner). However, there are times when the "essence" of UNIX must be examined and understood, such as when a native port is conducted. By restricting UNIX functions via conditional compilation, we can work on making the core of the kernel functional. Once the core is functional, remaining portions can be added incrementally. This incremental methodology allows us to backtrack when errors or malfunctions occur. In addition, we always have recourse to the previous version if necessary.

What constitutes a minimal UNIX kernel? This varies according to the kind of port desired and resources available. For example, one alternative plan we almost selected involved using the Network FileSystem (NFS) instead of working with the hard disk. If we had chosen that approach, code for implementing an NFS client, along with the networking code, would have been a mandatory component of our minimal port, while the disk driver and related support would have been relegated to a less-important role.

Since we are concentrating on the machine-dependent portions of the minimal kernel, we must pare-down considerably what is required. For 386BSD, we opted for a traditional port (see DDJ March 1991) that relied on a hard disk, a console interface (via the keyboard and display) and the process reschedule clock (via the interval timer). All network protocol and related system services (interprocess communications) were removed through conditional compilation. Any extended functionality in the main body of the kernel meant to accelerate operations (for example, macros, hash lookups, short circuit evaluation) was also avoided -- after all, it makes no sense to improve the speed of something that does not even run to begin with. Also, algorithm improvement is not always a machine-independent phenomenon.

The point in generating the "tiniest" kernel imaginable is to simplify the port. At this stage, we never expected to run something this small as a complete "production" system. As we incrementally added subsystems to our minimal kernel, we got a clearer understanding of the impact of each on the kernel. Even within this small system, redundant code and interfaces occurred. As such, a small amount of patience in this area always pays a handsome dividend later.

Our minimal kernel was created by adding conditional compilation (#ifdefs) statements to the BSD kernel source code to defeat the subsystems for networking, TCP/IP protocols, routing, NFS, interprocess communications (other than pipe), user process debugging, and the related services on which they depend. In addition, since we only needed drivers for disk, display, keyboard, and process scheduling clock, we could scale down the drivers and omit autoconfiguration code. After making this operational, fleshing out the drivers, and adding back in support to run debuggers caused the kernel to grow considerably.

Once you are running "high," you need to install a stack. The stack should be placed in the process's portion of address space. This way, it can be easily changed when we move from a process or task to another, because each process must have its own kernel stack. In a way, 386BSD functions like a subroutine call for a user process, with its own internal calls stacking on this separate stack, unlike the "jump to system" program approach used on systems such as TOPS-10.

Keeping each process's kernel stack at the same virtual location works well when using a single thread of execution processes, but is not advisable for multithreaded execution. For the multithreaded version of 386BSD, "lightweight" processes will require multiple kernel stacks and will be allocated out of kernel global virtual memory as needed.

The kernel program's address space established, we must "wire" the 386 processor hardware to the kernel interfaces and set initial conditions for the system, including interrupt and exception processing, user process address space definition, and preparation for context switching. All of the facilities must be set from the earliest point possible, because before we leave the kernel to execute a single user process instruction, we are already running multitasking. In fact, we will even use multitasking and exception processing as we initialize the system! This really should come as no surprise, as software aficionados can never resist the temptation to use double-duty or recursive code -- or even inscrutable self-referential code. As a result, we page-fault the page tables to allocate them to be used in paging the first process.

In the standalone system (see DDJ March 1991) we built a Global Descriptor Table to reinitialize segmentation. Now, we must follow the same techniques developed for the standalone system to build a Global Descriptor Table for descriptors used primarily by the kernel, and a Local Descriptor Table used primarily by the user tasks. (The local table can later be made "relative" per task if desired.) An Interrupt Descriptor Table must also be built that instructs the processor to execute special assembly code stubs (located at IDT-VEC(XXX) entry points) within the kernel (SEL_KPL) when any exceptions are triggered. Low-level code in each bus adapter's support code, used to wire-down all possible interrupts, is called to catch unintended interrupts prior to the configuring of devices by the kernel. And finally, through the use of special assembly language entry points (see DDJ March 1991), the descriptor tables are loaded, with any user or kernel exceptions caught on the fly.

Up to this point, we've just assumed that sufficient memory would be present to satisfy our needs, but this should not continue. Instead, we must probe and check the amount of memory present against recorded values in the system's configuration memory. If a value appears unusually large, we choose the lesser of the two. If both seem questionable, however, we revert to our minimum assumption -- 640 Kbytes of base memory only.

Memory in hand, we next initialize the virtual memory system that will manage both physical memory and virtual address space. The routine pmap_boot-strap( ) scales resources and assumptions based on available physical memory, and synchronizes the arrangement of the early "pmap" or physical map of the system to its internal data structures. The Mach virtual memory system, portions of which are incorporated into BSD, is split into machine dependent (pmap) and machine independent (vm_map) parts.

The remaining portion of init386( ) creates a way for a user process to enter the kernel and an initial process state through which a user process can be run for the first time. Because processes inherit these characteristics, this "zeroth" process state in effect initializes all subsequent sibling processes!

As you may have noted, over the course of this series we have been building upon our previous work as we head toward our goal, and increasingly we are relying on an understanding of our growing set of tools. And, at the same time, we have recently changed some of our code to accommodate some of the exciting new developments at Berkeley. With all the changes occurring, even those very familiar with this software can become somewhat "lost."

At this stage, it is important to go back and recall the perspective we tried to established on this project. We compared it to that of climbing a mountain, and we carefully outlined and prepared for all the problems we thought we would encounter. However, even with all the preparation we could muster, we've still had to be fast on our feet. Paths which we had carefully mapped out just six months ago are wiped away by an avalanche -- removed forever by the force of innovation. Work and time and effort have been tossed aside as we've been forced to adapt new approaches, not only to keep up with the group, but occasionally to set the pace (as in recursive paging). And finally, as our system grows, the complexity grows as well, and with it the blizzards of bugs and incompatibilities that occasionally blind and dispire.

And now, after months of effort, we have developed the barest of kernels. We will continue on with our kernel development, but we now have the makings of the "Basic Kernel." Key elements of our Basic Kernel (multitasking, processes, device drivers, executing the first process, games tests, paging, and swapping) are crucial to establish a working understanding of 386BSD and Berkeley UNIX. We look forward to seeing you on the trail with us.

When we began this project, many of our notions were based on prior experience in that we emphasized the similarities of the 386 to other machines while discounting its idiosyncrasies. Like a new car owner fumbling in the wrong place for the headlight switch and cursing it for having moved from the dashboard to the steering column, we mainly tried to just get 386BSD running. However, once we felt "settled in," we decided to see if we could take it to the limit. Consequently, the last few months have been like motoring with Mr. Toad -- with the onslaught of software changes, "wild" seems too weak a word.

In keeping with the CSRG goals for the upcoming 4.4BSD release, one major task was to migrate 386BSD to a virtual memory system derived from CMU's MACH operating system. While this decision was appropriate, a major problem relating to the 386 arose almost immediately; when implemented as designed by CMU on the 386, the virtual memory system swallowed copious quantities of virtual address space for the operating system -- space which is needed for user processes. Most of this space was gobbled up maintaining address maps of all in-memory processes page tables, so that the system could maintain access to them at all times should they become active.

At the same time, we had been getting somewhat tired of how process page table mapping was handled in the traditional BSD virtual memory system; since the page tables themselves were in physical memory (for use by the 386's MMU), we needed pages of page tables to map the page tables themselves before we could modify them. As you can guess, this increased the amount of "bookkeeping" overhead considerably, especially when interacting features are added (such as shared libraries and shared memory). We hoped there would be a better way.

An ideal virtual memory system design gives access to information on the virtual-to-physical translation process (and the converse) very quickly. However, while the information is there, right on the same piece of silicon and working at warp speed doing just this, there is no way via software to invoke the mechanism other than through transparent processes -- creating the "virtual memory" effect. (Don't expect any change in this area any time soon, either, because for many hardware design reasons this is a nontrivial addition.) As a consequence, the systems programmer must encode a tedious subroutine with a sole purpose to emulate the same translation process in software that is performed in a fraction of the time of a single instruction by part of the hardware.

    Minimal Kernel Breakdown (by module)
vmunix: text    data    bss    module name

        1152    32      0      clock.o
        0       500     0      conf.o
        4548    740     32     cons.o
        1508    24      0      init_main.o
        0       1212    0      init_sysent.o
        1588    28      0      kern_clock.o
        2044    12      0      kern_descrip.o
        3296    80      0      kern_exec.o
        1840    48      0      kern_exit.o
        1600    36      0      kern_fork.o
        956     0       0      kern_mman.o
        312     0       0      kern_proc.o
        1280    0       0      kern_prot.o
        1216    0       0      kern_resource.o
        3564    32      0      kern_sig.o
        684     16      0      kern_subr.o
        1808    24      0      kern_synch.o
        1864    4       0      kern_time.o
        248     0       0      kern_xxx.o
        6176    20508   0      locore.o
        5596    596     0      machdep.o
        0       148     0      param.o
        2184    84      8      subr_prf.o
        1092    72      0      subr_rmap.o
        244     0       0      subr_xxx.o
        184     72      0      swapgeneric.o
        3340    0       0      sys_generic.o
        4156    68      0      sys_inode.o
        1096    56      0      sys_process.o
        784     16      0      sys_socket.o
        2260    224     0      trap.o
        9480    516     0      tty.o
        12      204     0      tty_conf.o
        3928    4       0      tty_pty.o
        1924    0       0      tty_subr.o
        8680    1220    0      ufs_alloc.o
        3312    116     0      ufs_bio.o
        1668    0       0      ufs_bmap.o
        1248    48      0      ufs_disksubr.o
        416     0       0      ufs_fio.o
        3968    68      0      ufs_inode.o
        436     0       0      ufs_machdep.o
        2048    0       0      ufs_mount.o
        6020    220     0      ufs_namei.o
        2288    208     0      ufs_subr.o
        7100    112     0      ufs_syscalls.o
        0       620     0      ufs_tables.o
        0       152     0      vers.o
        2280    48      0      vm_drum.o
        2964    52      0      vm_machdep.o
        4364    180     0      vm_mem.o
        8280    188     0      vm_page.o
        2056    20      0      vm_proc.o
        3060    24      0      vm_pt.o
        2788    72      0      vm_sched.o
        528     0       0      vm_subr.o
        1052    32      0      vm_sw.o
        1836    44      0      vm_swap.o
        1536    152     0      vm_swp.o
        2048    68      0      vm_text.o
        3768    1492    1024   wd.o
totals: 145708  30492   1064

    Fully Loaded Kernel Breakdown (by module)
vmunix: text    data    bss     module
        0       4       0      af.o
        592     16      0       autoconf.o
        844     0       0       clock.o
        2584    168     0       com.o
        0       640     0       conf.o
        4096    676     40      cons.o
        540     132     0       dead_vnops.o
        1440    28      0       device_pager.o
        3180    152     48      fd.o
        1264    140     0       fifo_vnops.o
        2812    12      0       if.o
        2600    12      0       if_ether.o
        1056    24      18      if_ethersubr.o
        464     0       0       if_loop.o
        5044    12      12      if_ne.o
        3184    16      0       if_sl.o
        3852    12      4       if_we.o
        2844    4       0       in.o
        356     0       0       in_cksum.o
        1684    0       0       in_pcb.o
        12      320     0       in_proto.o
        1496    12      0       init_main.o
        0       1532    0       init_sysent.o
        0       468     0       ioconf.o
        2056    68      0       ip_icmp.o
        4564    60      48      ip_input.o
        2616    0       0       ip_output.o
        1372    4       0       isa.o
        1204    16      0       kern_acct.o
        1280    4       0       kern_clock.o
        3184    0       0       kern_descrip.o
        3176    0       0       kern_exec.o
        1424    0       0       kern_exit.o
        996     8       4       kern_fork.o
        1204    0       0       kern_kinfo.o
        1772    0       0       kern_ktrace.o
        1028    4       0       kern_lock.o
        1892    268     0       kern_malloc.o
        796     0       0       kern_physio.o
        1180    0       0       kern_proc.o
        1844    0       0       kern_prot.o
        1140    0       0       kern_resource.o
        4172    132     0       kern_sig.o
        684     0       0       kern_subr.o
        1988    4       0       kern_synch.o
        1408    4       0       kern_time.o
        264     0       0       kern_xxx.o
        7076    684     0       locore.o
        4684    192     0       machdep.o
        552     0       0       mem.o
        708     44      4       mfs_vfsops.o
        656     132     0       mfs_vnops.o
        1600    0       0       nfs_bio.o
        1020    0       0       nfs_node.o
        21700   36      0       nfs_serv.o
        7748    152     0       nfs_socket.o
        1040    144     21672   nfs_srvcache.o
        10284   40      4       nfs_subs.o
        1956    72      80      nfs_syscalls.o
        2996    40      1       nfs_vfsops.o
        21304   424     0       nfs_vnops.o
        348     12      16      npx.o
        0       152     0       param.o
        6308    16      0       pmap.o
        2908    4       36      radix.o
        164     8       0       raw_cb.o
        1072    36      0       raw_ip.o
        812     0       0       raw_usrreq.o
        2304    8       0       route.o
        4552    116     0       rtsock.o
        2584    60      0       slcompress.o
        2296    180     0       spec_vnops.o
        716     0       0       subr_log.o
        1764    8       0       subr_prf.o
        888     0       0       subr_rmap.o
        340     0       0       subr_xxx.o
        5456    28      0       swap_pager.o
        0       40      0       swapvmunix.o
        3344    0       0       sys_generic.o
        0       0       0       sys_machdep.o
        904     56      0       sys_process.o
        604     20      0       sys_socket.o
        228     0       0       tcp_debug.o
        5820    8       0       tcp_input.o
        1896    16      0       tcp_output.o
        1504    12      0       tcp_subr.o
        832     60      0       tcp_timer.o
        1620    8       0       tcp_usrreq.o
        2912    0       0       trap.o
        9488    316     0       tty.o
        1864    204     0       tty_compat.o
        12      204     0       tty_conf.o
        3452    4       0       tty_pty.o
        1988    0       0       tty_subr.o
        504     0       0       tty_tty.o
        1980    36      0       udp_usrreq.o
        9644    0       0       ufs_alloc.o
        2012    0       0       ufs_bmap.o
        1424    0       0       ufs_disksubr.o
        3756    0       0       ufs_inode.o
        1668    12      0       ufs_lockf.o
        3832    4       0       ufs_lookup.o
        4572    20      0       ufs_quota.o
        732     0       0       ufs_subr.o
        0       620     0       ufs_tables.o
        3948    64      0       ufs_vfsops.o
        8264    524     0       ufs_vnops.o
        620     0       0       uipc_domain.o
        2672    64      4       uipc_mbuf.o
        8       176     0       uipc_proto.o
        6164    0       0       uipc_socket.o
        3184    24      0       uipc_socket2.o
        5520    0       0       uipc_syscalls.o
        3320    32      0       uipc_usrreq.o
        0       232     0       vers.o
        3644    0       0       vfs_bio.o
        1108    4       0       vfs_cache.o
        0       24      0       vfs_conf.o
        1776    0       0       vfs_lookup.o
        3940    44      0       vfs_subr.o
        7544    0       0       vfs_syscalls.o
        1684    20      0       vfs_vnops.o
        3524    0       0       vm_fault.o
        1964    20      0       vm_glue.o
        84      0       0       vm_init.o
        1848    0       0       vm_kern.o
        944     0       308     vm_machdep.o
        7624    16      0       vm_map.o
        384     20      0       vm_meter.o
        3196    4       0       vm_mmap.o
        3588    16      0       vm_object.o
        2500    32      0       vm_page.o
        824     8       0       vm_pageout.o
        636     20      0       vm_pager.o
        1160    0       0       vm_swap.o
        416     0       0       vm_unix.o
        304     0       0       vm_user.o
        2200    28      0       vnode_pager.o
        6176    1648    524     wd.o
        5252    48      9       wt.o
totals: 359636 12248 22832

Copyright © 1991, Dr. Dobb's Journal