Bootstrap Loading

Tom Van Vleck

History

The initial design of Multics bootload was led by André Bensoussan (GE Bull) in 1966, with input from many others on the Multics team. Nguyen Van Binh (GE Bull) started the initial coding. When Van Binh returned to France, the project was taken over by Noel Morris and Tom Van Vleck (MIT Project MAC) in 1967. Story: Phase One

This note describes how Multics bootloading evolved, with emphasis on the early days, since that is the part I was involved in.

Background: bootstrap loading

In the early 60s, computer systems used to start up their operating systems in a multi-step process. After power on or a reset of the CPU, the operator had to insert a few instructions (the bootstrap loader) into memory. Then the operator forced the CPU to execute the first instruction of the bootstrap. Those instructions read in a complete core image of the operating system a from card reader, paper tape reader, or magnetic tape. The core image looked like a version of the operating system, with executable instructions and tables set up, ready to execute. The bootstrap transferred control into the loaded data and executed it as instructions, and the operating system woke up ready to go. (Sometimes such bootload images were created by stopping a running idle system, and making a snapshot of core memory.)

Early 1960s computers had a control panel with switches that allowed one to store binary values into any storage location, and to enter an address into the switches and cause the CPU to execute the instruction at that location. They were bootstrapped by depositing a few instructions into memory with the console switches, and then executing an absolute transfer to the first location.

Other computers had the bootstrap loader "hard wired" in a diode matrix or rope memory, and a single button to start loading and executing software. If a machine could be loaded from more than one I/O device, these later computers had physical switches or dials that caused the loader instructions to be modified with the address of the boot device. The PDP-10, for example, had a Read-In Mode button that reset the CPU and I/O, and did a DATAI instruction to read the device selected by a set of binary switches. The IBM 7070 and IBM 1620 computers I used on summer jobs in the early 60s had an electric typewriter with a hard-wired debugger that allowed the operator to display and alter locations by typing commands.

A system image loaded in this way needed to find the computer's hardware configuration, I/O devices, and so forth. The usual way to make this work was to generate a boot image ahead of time, tailored to the local hardware: this system generation (SYSGEN) process accepted descriptions of how devices were configured, how much memory was on the machine, hardware features available, software options, and so forth, and wrote out a boot image specifically for the machine. SYSGEN experts could tune a system's performance by omitting programs that a site didn't need from the operating system image, and by choosing sizes for OS tables based on anticipated usage.

Multics Bootstrap Loading

The GE-645

The Multics system was designed for a new machine, the GE-645, which extended the GE-635 by adding paged and segmented memory access modes to the CPU. The 1965 Fall Joint Computer Conference paper "System Design of a Computer for Time-Sharing Applications" describes the 645 processor extensions. The 645 was a shared memory multiprocessor system that could have up to 8 active devices (CPUs or GIOCs) in a single configuration. The Multics hardware also incorporated a new I/O controller called the GIOC.

Multics Design

The general design of Multics was described in the 1965 paper, "Introduction and Overview of the Multics System". The planned Multics supervisor did not run in absolute addressing mode: it was written in the high-level EPL language that used segmented addresses. The Multics runtime required a fairly complex operating environment, with addressing tables, stack segments, and inter-procedure linkage set up. Making a core image snapshot of such an environment posed multiple problems, and making system boot tapes tailored to the configuration conflicted with the desire to have Multics able to dynamically configure the system, adding and removing CPUs and GIOCs while the system ran.

Multics Bootload Design

The Multics team chose the basic design strategy of providing a single system boot tape per release. There would be no SYSGEN; system tuning would be specified by adjusting parameters at boot time or at run time. The features of the planned Multics helped make this possible: segmented memory made it possible to allocate memory to system tables at initialization time instead of system generation time, and we planned to make much of the operating system operate in demand-paged mode, so that there was less cost for including system software that might not be called.

Multics system initialization was designed to execute in several phases, each establishing a richer execution environment used by the next phase. The Multics system loading process was designed to start with a small bootstrap loader, as before; it loaded programs that ran in absolute addressing mode for a short time, setting up the PL/I runtime environment, and then entered segmented, paged addressing mode in the CPU. Configuration dependencies were handled by having the loading process read configuration information and initialize system tables during the bootloading process.

The Multics design divides programs into rings of protection. Each Multics process's address space has segment descriptors for the operating system as well as user programs. Most of the operating system runs in Ring 0, the most privileged environment, only accessible from user programs via gated calls. The design of system bootstrapping was to load a small collection of programs, initialize them, and then use the additional facilites they provided to load another collection, initialize it, and so on.

Multics Bootload Implementation

MSPM BC.4.01, System Initialization and Bootload describes the basic hardware bootload process on the GE-645.

The GE-645 had a hardware console with a hard-wired Selectric typewriter and a few control buttons. There was also a TAPE/CARD switch on each GIOC. Pressing the BOOT button set up an GIOC mailbox that contained the channel and device number of the boot device, and then simulated an I/O connect instruction to read in the tape and transfer to the first word read in from the device, signalling it to read a record (from tape or card) into absolute location 30, leaving PCWs, DCWs, etc in loc 0-5.

The initial design of software for system boot was described in MSPM BL.4.00, Bootstrap Initializer -- Overview. (When we actually wrote the code to initialize Multics, we made many implementation decisions, and this spec was never updated.)

Here is the sequence of steps that Multics took for a "cold" bootload ftom tape:

• Configure the hardware for a bootload run.
• Mount a Multics boot tape.
• Push the BOOT button.
• The first record of tape is loaded into memory and executed. This program was bootstrap1. This program is described in MSPM BL.4.01, Bootstrap 1.
• bootstrap1 allocates some special segments at fixed addresses: fault vectors, mailboxes, SCAS
• bootstrap1 reads records until the first collection mark. This is "collection 1." This code is Multics format assembler and EPL object segments.
• bootstrap1 makes a descriptor segment, turns on appending mode, and loads the segments of collection 1. It then sets up a stack and calls (at 0 offset, not symbolically) bootstrap2, which pre-links the collection 1 segments, including itself, and calls the first EPL program, initializer. bootstrap2 is described in MSPM BL.4.02, Bootstrap 2.
• collection 1 contains the perm-wired supervisor:
  • loads and initializes machinery needed for paging
  • includes disk DIM, fault/interrupt interceptor, page control, traffic control
  • establishes the EPL environment: operators, basic runtime, stack, linkage
• initializer calls the initialization routines for collection 1, including setting up system tables and turning on paging. Then it loads and executes collections 2 and 3. initializer is described in MSPM BL.5.00, Overview of the Multics Initializer.
• collection 2 contains the paged supervisor, including the file system, ttydim, etc.
  • patches traffic control tables to look as if a process is running and inits traffic control
  • when we init this collection, we hook into the file system
• collection 2 reads in collection 3 and ends by calling out to init_proc in ring 0. For the initializer, this program calls system_startup_ in the initializer's initial ring, which sets up ring 1 and then invokes system_control_ in the user ring, which starts the Answering Service.

Debugging Bootloading

Each test of Multics bootloading required compiling and assembling whatever programs had to be changed, by editing the programs on CTSS and submitting a batch job to the Project MAC GE-635 using MRGEDT. The text and link files from these compilations were then processed by the Multics System Tape Generator, running under the 645 simulator, to write a Multics System Tape (MST). Once a boot tape was prepared, programmers would sign up for a block of stand-alone time on the GE-645. (Most debugging was done on the Project MAC 645 in Technology Square, but it was possible to copy a boot tape to Bell Labs in Murray Hill, using an IBM 7711, and try it out on the Murray Hill GE-645.) Testing a new boot tape required the programmers to have exclusive use of the whole mainframe. At the beginning of testing Multics initialization, we would boot our latest tape, and it would read some data, compute for a while, and then crash. We'd take a dump on the line printer, analyze the problem, modify our code, and sign up for another stand-alone time slot. Noel and I were not the only programmers doing bootload runs, but as we were debugging the initializer, we worked with the experts on each system facility, integrating pieces of software into the bootable system and giving it its first test in the actual system environment.

This basic design did not cover a number of issues, and we had to consult with other programmers and make implementation choices whenever we encountered a roadblock. The first major problem the team encountered happened when bootstrap2 finished its execution and wanted to transfer to initializer. We hadn't really thought about how to do this: the "natural" way in the Multics design would be to take a linkage fault, and as I remember, our code had set up the hardware fault vectors to send a linkage fault to the linker program. But oops, the linker had to call other programs, and they were not linked, so it would take a linkage fault while processing a linkage fault, and loop forever. This felt like a major hole in the design of system initialization. We conferred with many members of the team, seeking a solution that could be implemented quickly and have the least impact on the design of Multics. We chose to implement a temporary facility, the pre-linker, used only in collection 1, which snaps all links between collection 1 programs using tables created by bootstrap1. The pre-linker handles only those cases of linkage required during initialization. This strategy enabled a supervisor design in which there were no linkage faults in ring 0. In order to make descriptor segment management simple, we also chose to enforce the limitation that there would be no dynamic addition of ring 0 segments.

Another problem we tackled while implementing system bootload was handling the variability of configuration. How would the Multics supervisor know how many CPUs, GIOCs, etc there were, and where the disk was, and so on, in order to initialize supervisor tables? Initially this was going to be done with switches: at one point I calculated that at least 576 switches would have to be set to describe the whole configuration, and of course only a small fraction of the enormous number of possible settings represented viable configurations. Our next idea was to develop a "configuration deck" of text information that bootstrap1 would read somehow.

(I remember the first time we got as far as calling init_core_control. The CPU lights had been blinking away and suddenly seemed to freeze. It appeared that Multics was in a hard loop. We waited a few minutes to make sure, and then crashed the system and took a dump. We sent the dump to the programmer in Murray Hill, who called on the phone and said "Why'd you kill it? It was only half done." It turned out that the program was initializing a structure that had an array of 37-bit elements, and that the EPL compiler generated a page and a half of code for each store. The compiler was modified to annotate the assembly code it produced for array accesses: arrays were "good", "synchronous", or "idiotic." When the "idiotic" table declaration was changed, init_core_control became very fast.)

Multics System Tape Generator

The system tape that we booted Multics from had to be created with specialized software. The initial design for the system tape generator was done by Peter Schicker (MIT Project MAC) in 1967. The MST generator was an EPL program that read a "header file" which listed the segments to be copied to the system tape, and their meta-attributes. Initially it ran as a Multics 6.36 simulator job launched from CTSS, until Multics was self-hosting in 1968. See MST Generator source at MIT. We also built a program called the MST Checker, described in MSPM BV.4, MST Checker, which checked that a system tape was correctly prepared, and generated a cross reference of which segments called which. This tool was important in 1967, when making an incorrect system tape would lose a day's work. See MST Checker source at MIT.

Bootload Operating System (BOS)

Early Bootloading

When Noel and I took over development of bootstrap1 in 1967, Nguyen Van Binh showed us his approach to testing. Each time Van Binh wanted to test his self-loading tape, he first booted GECOS on the GE-645 (from cards), and then invoked the GECOS hardware debugger, called RAID. This debugger was a simple program that took over the whole machine and allowed a programmer to inspect and modify core locations and take a core dump. Once the 645 was sitting in RAID, Van Binh would reset the CPU and try booting Multics from his tape. Typically this would run for a few seconds and then crash or loop. Then Van Binh would halt the CPU and force a transfer to the absolute location of RAID by using the CPU front panel switches, and use RAID to dump core on the line printer by manipulating the CPU switches. When Noel and I started testing the bootstrap, we had to do a lot of running around; having two people was a big advantage. The RAID dump was just a many-page listing of locations and their contents in octal. To debug, we located the addressing tables in the listing, and program variables set up by bootstrap1, and checked their values.

Segment Dumper

John Gintell had just joined GE about that time, and one of his first projects was to reduce our dependency on GECOS and RAID. John wrote a program in GMAP called the 645 Segment Dumper, a self-loading card deck that we could boot after bootstrap1 had crashed, to dump core to the line printer. It worked great. The new program dumped memory segments on separate pages by using the 645's addressing tables; this made debugging bootstrap1 much easier. Loading the card deck every time was tedious though; we had to keep switching the GIOC from tape to card booting, and the card reader had the unfortunate habit of shuffling input decks. Also, loading the dump program wiped out a section of memory. As we asked for more features in the dump program, it got bigger and clobbered more core.

I don't remember who suggested that we change the dump program to start by loading a little program that saved a block of core to a special section of disk, and then load the dumper into the core block. The dumper could then dump that area from the disk block instead of dumping itself. This arrangement meant that we could take a dump of almost all of core. Furthermore, the dumper could accept requests from the console typewriter to dump only a selected range of memory, rather than being controlled by the CPU switches. The development team started thinking of more features to add to the dumper, now that we had the basic idea of using the disk and console.

BOS creation

BOS, the Bootload Operating System, evolved from the segment dumper. Stan Dunten and Noel Morris led the design of a small software system that used the console and card reader, and had its own little partition of disk. BOS had a "toehold" that managed gaining control, and swapping memory out to disk to gain space, and swapping in the executive. If the system crashed or looped, the operator could manually transfer to the toehold at absolute location 10000 to get a dump and reboot. The main program looped reading and executing commands from the console, and could load and execute overlays called BOS command programs such as DUMP, which was a repackaging of John Gintell's online dumper. BOS had a very primitive file system that it used to store the swapped region, a "configuration deck," and the BOS command programs. It was told what the hardware configuration was by cards in its configuration deck. BOS was written in EPLBSA assembly language and did not do virtual memory or dynamic linking; it did use a simple layout of segmented memory. Early design of BOS was described in MSPM section BV.1. The source of BOS is online at MIT, thanks to Bull.

One particular BOS command, called BOOT, simulated the hardware BOOT button to initiate a bootload of a Multics system tape. BOOT left an image of the BOS configuration deck in absolute memory locations 14000 thru 15777 (octal), where the Multics bootstrap process could read and parse it and find the hardware.

Other useful BOS commands were written to perform system maintenance operations, such as saving and restoring disk contents and patching memory. The FDUMP command dumped core to the a disk partition, instead of the line printer; online multics commands could explore and format the dump, saving paper and time. One key element of this automation is a communication region, the flagbox, that is addressable by both BOS and the Multics hardcore. A "boot in progress" flag is set in this region when BOS attempts to boot Multics, and reset when the system comes up fully. Attempts to reboot when this flag is set will pause and await operator guidance. The BOS RUNCOM facility could execute little scripts, which could test flags and execute commands conditionally.

Originally, booting BOS from tape required a small card deck, the 3-card loader, and switching the CARD/TAPE boot source switch on the I/O controller. Noel Morris did some tricky code in the 70s so that the BOS tape could be a standard-format Multics labeled tape. Booting such a tape would try to execute the tape label, and cause a TROUBLE fault, which would execute another part of the tape label which was specially set up to catch the fault and continue loading. This worked fine unless the Field Engineers had left the STOP ON FAULT on the CPU turned on, which they sometimes did while running hardware diagnostics.

TODO: explain the INTK card. Would an MST boot without BOS? Probably not, how would it find the configuration.

Bootloading Evolution

Software Evolution

As the Multics runtime evolved, the bootstrap process had to have more features added. When combined linkage and bound segments were introduced, the bootstrap code had to be updated. The introduction of the PL/I compiler and the replacement of EPL by PL/I required changes to make bootstrapping work. When ALM became available, EPLBSA code was re-written in the new assembler.

After the MSPM was written, bootload evolved rapidy in the late 60s and early 70s with little documentation, as software were added and changed. (If we had the file of MIT's Multics Operating Staff Notes, these would provide much insight into when various features changed.) Document AN70, System Initialization PLM describes system bootloading of 6180 systems in the early 1970s. The original Multics Operator's Handbook, written in 1970 or so, has not survived. The Nov 1986 revision 4 is available: AM81-04, Multics Operator's Handbook.

The introduction of the New Storage System required changes to file system initialization and the introduction of logical volume management and the hardcore partition. Document AN61, Storage System PLM, describes file system initialization as of 1978.

Hardware Evolution

Significant changes had to be made to bootloading to get it working on the Honeywell 6180 in the early 1970s. The GIOC was replaced by the IOM. Low level privileged instructions changed and both BOS and the bootstrap programs had to be updated. Booting a system got more complicated when the tape and card MPCs had to have firmware loaded before they could respond to the IOM. This was first done in the 1970s by using the Hardware T&D tape.

Late in its development, Multics supported a "paged mode" IOM. See MTB-652 for a little information.

Cold booting a Multics system was very complicated, requiring T&D tapes, BOS tapes, and Multics system tapes, and a working card reader. MTB-130 On the Cardreaderless Unified Bootload Tape (1974-10-18) describes a method to unify all system booting into a single tape. Read the glossary story about Zero Six Dog.

As system architectures changed, the code in the bootstrap and BOS had to be adapted. For instance, the DPS-8 version of the Multics hardware required changes to initialization.

Bootload Command Environment (BCE)

Major changes to how Multics systems were supported and bootloaded were begun in 1982 and released in 1985 (MR 11). Instead of supporting two highly privileged boot environments maintainable only by experts, we would have one. The goal was that in MR12, BOS was not required to support Multics. The planning memos for BCE span several years. Some are online:

• MTB-598-01 Bootload Multics Status and New Initialization PLM material. (1982-12-02)
• MTB-626 The config deck editor for Bootload Multics (1983-06-07)
• MTB-631 Bootload Multics Task List (1983-08-23)
• MTB-651 Bootload Multics Phase 1 (1984-03-15)
• MTB-745-01 Add Save/Restore to the BCE command set. (1986-06-05)

XXX BCE was needed for Orion and Dipper support. Was it also justified by B2 requirements?

Gary Dixon In Multics release MR11, Multics bootloading was done by a facility called Bootload Command Environment, BCE. Here are some of the missing pieces in later bootload strategies, as summarized from the Operator's Guide to Multics (GB61-01) for Multics Release 11.0 (June 1985).

Gary Dixon BOS in this time frame was much simplified. It was limited to: save/restore contents of disks; doing pack-to-pack disk copies; and booting BCE (the Bootload Command Environment).

Gary Dixon BCE subsumed most of the other BOS functionality, with some important additions. BCE primary functions were: booting Multics; dumping main memory and disks; and initiating emergency shutdown (ESD) of Multics, in the event of a crash or system hang. BCE was initially loaded from a combined tape called the BCE/Multics system tape, which was either booted from BOS, or booted directly. Once booted from tape, it stored the BCE/MST image on the root physical volume (RPV) in a special BCE partition, for use in later bootloads of the same release.

Gary Dixon In the BCE environment, you could: edit the config deck (also stored in the BCE partition), to change the hardware configuration; set the system clock, etc; load firmware into other MPCs (beside that for the tape controller); boot Multics (as will be described later); take dumps; do ESD; etc.

Gary Dixon As I recall, BCE was always booted from a tape. I believe this was a separate tape from the MST (at least in the beginning). Once BCE is started from tape, it has commands to:

• Cold install a new Multics system, from a Multics System Tape (MST). As part of this process:
  • The entire MST is loaded in Multics memory;
  • Multics is partially started up to configure all of hardcore for the current hardware configuration;
  • Multics then transfers back to BCE without shutdown.
  • BCE captures this configured Multics hardcore memory image, and saves it to a file in the BCE disk partition.
  • BCE then returns control to Multics hardcore, so it can continue system start-up.
• Subsequent boots from BCE boot the preconfigured Multics memory image, loading it from disk into memory, and transferring into the image, just as was done when the image was first saved (see above).
• Changing hardware config, or loading an upgraded Multics release involved loading same/new MST tape, and re-saving the Multics hardcore memory (for the possibly new device configuration) as an image in the BCE disk partition.

Gary Dixon Many of the steps involved in configuring the hardware and booting Multics were performed in BCE exec_coms. When starting Multics, BCE read in the Multics portion of the BCE/Multics system tape image (usually from disk, unless a new release was being installed); told the initializer to configure the software based on information in the current config deck; then saved a memory image of the pre-configured Multics as another file in the BCE partition. If subsequent bootloads did not change the hardware configuration, this saved system image would be loaded to speed the overall bootload. Using saved images reduced typical bootload times from 20 minutes or more down to 5 minutes.

Gary Dixon It was this tight interface between an initializing Multics and its underlying BCE that forced a closer integration of the BCE code with Multics code; and put the BCE bootloader on the start of the Multics system tape.

System Documentation

Multics System Initialization Program Logic Manual (AN70-01) describes system bootloading under BCE. MTB-652 New Initialization SDN (1984-03-15), by Keith Loepere, is an online draft of the manual. A later document on Multics initialization, including BCE, circa 1988: MDD-05 System Initialization.

Should we add shutdown, or put into a separate doc? We cover ESD in failure-recovery but should also describe normal shutdown.

Updated 2013-03-14 thanks to Bernie Greenberg. Updated 2013-04-08 thanks to Gary Dixon. Updated 2015-10-03 with pointers to AN70-1 and MTB-652.