MMURTL: Your Own 32-Bit Operating System
A message-based, multitasking, real-time kernel
Richard Burgess
Rich spent 20 years in the U.S. Coast Guard, primarily in systems analysis and design. He now heads The D Group, a Lorton, Virginia consulting firm. Rich can be reached via e-mail at [email protected].
MMURTL (pronounced "Myrtle") is an operating system designed to run on 386SX or better Intel-based PCs. MMURTL, short for "message-based, multitasking, real-time kernel," supports flat, 32-bit, virtual-paged memory space and all 32-bit instructions (including device drivers) without resorting to thunking 16-bit BIOS code. Still, MMURTL's file system is DOS FAT-compatible, so to use it, all you have to do is run the loader from MS-DOS, then boot MMURTL. In a general sense, MMURTL's messaging types have a client/server flavor. One of MMURTL's most attractive features, however, is that it's small (at least for a multitasking OS), running in only one Mbyte, with room to spare for an application or two.
I initially used MASM 5.x to develop MMURTL. After running into some problems with 32-bit instructions, however, I switched to Turbo Assembler 2.x, then TASM 3.x. More recently, I've been using DASM, the assembler included with MMURTL. Still, the code assembles with TASM or MASM.
In this article, I'll discuss MMURTL's paged-memory management, specifically, the code contained in the file MEMCODE.INC. The current version of the complete MMURTL operating system--source code, executables, device drivers, C compiler, assembler, documentation, and other utilities--is available electronically (see "Availability," page 3).
Before going further, I'll define a few unique, MMURTL-specific terms.
A MMURTL job is an application or system service. Each job has its own linear memory space provided by the OS and paging hardware. A job has one or more tasks (threads of execution) managed with 32-bit Intel task-state segments (TSS). Jobs are kept track of in MMURTL with a structure called a "job control block" (JCB).
Physical memory includes the memory chips and their addresses as accessed by the hardware. If I put address 00001 on the address bus of the processor, I'm addressing the second byte of physical memory. Linear memory, on the other hand, is what applications use as they run. This memory is actually translated by the paging hardware to physical addresses that MMURTL manages. Programs running in MMURTL have no idea where they are physically running in the machine's hardware address space, nor would they want to. These are "fake" addresses, but very real to every job on the system.
Logical memory is the memory that programs deal with and is based around a "selector." A protected-mode program's memory is always referenced to a selector, mapped (in a table) to linear memory by the OS and translated by the processor. Generally, selectors are managed in a local or global descriptor table (LDT or GDT); MMURTL, however, doesn't use LDTs. Logical memory is read by the processor, where an additional address translation takes place. The GDT allows you to set up a zero-based address space that really isn't at linear address 0.
If you are familiar with segmented programming, you know MS-DOS uses tiny, small, medium, large, and huge memory models to accommodate the variety of segmented programming needs. The only memory model in MMURTL is analogous to the small memory model, in which you have two segments: one for code, the other for data and stack. This sounds like a restriction until you consider that a single segment can be as large as all physical memory (or larger, with demand paging).
MMURTL doesn't provide memory management in the sense that compilers and language systems provide a heap or an area managed and cleaned up for the caller. MMURTL is a paged-memory system: It allocates pages of memory as they are requested and returns them to the pool of free pages when they are deallocated. MMURTL manages all the memory in the processor's address space as pages. Because linear addresses are "fake" and the real memory (physical pages) can be allocated in any order, address-space fragmentation is really not a concern.
A page is four Kbytes of contiguous memory on a 4-Kbyte boundary of physical and linear addressing.
MMURTL uses three defined segments in the GDT--the OS code segment (08h), the application code segment (18h), and a data segment (10h). Selectors (or "segment numbers") are fixed.
Using the same data selector for the OS and all programs lets you use 32-bit near-data pointers exclusively, thereby greatly simplifying application development. This technique also speeds up code by maintaining the same data selectors throughout the program's entire execution. The only selector that changes is the code selector, which goes through a call gate into the OS and back again. This means the only 48-bit pointers you'll use in MMURTL are for an OS call address (16-bit selector, 32-bit offset).
Paging lets you manage physical- and linear-memory addresses with simple table entries. These table entries are used by the paging hardware to translate (or map) physical to linear memory. Linear memory is what applications see as their own address space. For instance, you can take the very highest 4-Kbyte page in physical memory and map it into the OS's linear space as the second page of its memory. This 4-Kbyte page of memory becomes addresses 4096--8191, even though it's really sitting up at a physical 16-Mbyte address.
The structures that hold these translations are called "page tables" (PTs), and each entry in a PT is called a "page-table entry" (PTE). Every PT has 1024 4-byte PTEs, so a single 4-Kbyte PT can manage four Mbytes of linear/physical memory. That's not too much overhead for what we get out of it.
The paging hardware finds the page tables using a page directory (PD). Every MMURTL job gets a unique PD, and each entry in a PD is called a "page directory entry" (PDE). Each PDE is four bytes long and holds the physical address of a PT. This means you can have 1024 PDEs in the PD, each pointing to a different PT, which can have 1024 entries, each representing four Kbytes of physical memory. This allows you to map the entire 4-gigabyte linear address space:1024*1024*4K(4096)=4,294,967,296 (4 gigabytes).
MMURTL's OS code and data are both mapped into the bottom of every job's address space. A job's memory space actually begins at the 1-gigabyte linear-memory mark. This is so high because it gives the OS and each application one gigabyte of linear memory space. Leaving the OS zero-based also greatly simplifies memory initialization. Figure 1, the map of a single job and the OS, is identical for every job and service installed.
The OS has to know where to find all the tables allocated for memory management and how to get to them quickly. I could have built a separate table and managed it, but this wasn't necessary, and I wanted to keep overhead down.
The processor translates these linear (fake) addresses into real (physical) addresses. First, it finds the current PD by looking at the current task's value in the control register CR3, the physical address of the current PD. The processor uses the upper ten bits of the linear address it's translating as an index into the PD. The entry it finds is the physical address of the PT. The processor then uses the next ten bits as an index into the PT. Now it's got the PTE, the physical address of the page it's after. Sounds like a lot of work, but it's done with very little overhead.
The OS has no special privileges as far as addressing physical memory. MMURTL uses linear addresses (fake ones), just like the applications, which is fine until you have to update or change a PDE or PTE. At that point, you can't just get the value out of CR3 and use it to find the PT because you'll crash. Likewise, you can't take a physical address out of a PDE and find the PT it points to.
Finding the PD for an application isn't a problem. When you start the application, you build the PD and stick the physical address in the TSS field for CR3, then put the linear address of the PD in the JCB. This is fine for one address (the PD). However, it's another story when you're talking about dozens or hundreds of linear addresses for all the PTs that need to be managed.
MMURTL keeps the linear address of all PTs in the upper two Kbytes of the PD. (Two Kbytes doesn't sound like much to save, but when 10, 20, or even 30 jobs are running, it adds up.) The upper two Kbytes are a shadow of the lower two. Each PDE has the physical address of a PT. MMURTL needs to know the physical address of a PT, given its linear address for aliasing addresses between jobs (and it needs it fast).
MMURTL's shadow entry with the linear address of the PT is exactly 2048 bytes above each real entry in a PD; the shadow entries are marked "not used."
Table 1 lists the sample entries that describe the page directory. This example assumes one PDE for the OS and one for the application.
The structure PDR1 in the source code describes a PTE. Each of the physical and linear addresses stored are only 20 bits because the last 12 bits of the 32-bit address are below the granularity of a page (4096 bytes). These lower 12 bits for a linear address are the same as the last 12 bits for a physical address. All the shadow entries are marked "not present," as are all entries with nothing in them, so they don't exist as far as the processor is concerned. If you decide to move the shadow information into separate tables and expand the OS to address and handle 4 gigabytes of memory, it will be transparent to applications.
AllocPage, AllocOSPage, and AllocDMAPage are the only calls to allocate memory in MMURTL. AllocPage allocates contiguous linear pages in the job's address range. This is 1--2 gigabytes. The pages are all initially marked read/write with the user-protection level. AllocOSPage allocates contiguous linear pages in the OS address range; this is 0--1 gigabyte. These pages are all initially marked read/write with the system-protection level; entries automatically show up in all jobs' memory space because all OS PTs are listed in every job's PD. AllocDMAPage allocates contiguous linear pages in the OS address range, but it ensures that these pages are below the 16-Mbyte physical-address boundary. Most direct memory access (DMA) hardware on ISA machines can't access physical memory above 16 Mbytes. AllocDMAPage also returns the physical address needed by the DMA users.
All allocation routines first check nFreePages to see if there are enough physical pages to satisfy the request. If so, they call FindRun to determine if that number of pages exists as contiguous free entries in one of the PTs. If not, MMURTL will create a new PT (see AddOSPT). They then call FindRun again. This is strictly on a first-fit basis. Adding a 4-Kbyte PT for four more megabytes of clean linear address space creates less overhead than using cleanup code or linked lists to manage that space. When a large enough run is found, the allocation routines call AddRun to get the linear address that they return to the customer. AddRun does the actual allocation of physical memory for each page. All AllocPage calls return either an address to contiguous linear memory or an error if it's not available. With a 1-gigabyte address space, it's unlikely you won't find a contiguous section of PTEs. It's more likely you'll run out of physical memory.
When pages are deallocated, the caller passes in a linear address (from a previous AllocPage call) along with the number of pages to deallocate. The caller must ensure that the number of pages in DeAllocPage does not exceed what was allocated. If it does, the OS will attempt to deallocate as many pages as requested. This may run into memory allocated in another request (but only from that caller's memory space). There will be no error, but the memory will not be available for later use. If fewer pages are passed in, only that number will be deallocated. With the sole exception of DMA users (device drivers), the caller will never know (nor should it try to find out) where the physical memory is located.
By handling translation of linear to physical memory, the processor takes a great deal of work away from the OS. It is not important if pages of memory in a particular job are physically next to each other (with the exception of DMA). The main goal of physical memory management is simply to keep track of how much physical memory there is and whether or not it's currently in use. Physical-memory allocation is tracked by pages with a single array, the page-allocation map (PAM), which is similar to a bit-allocation map for a disk. Each byte of the array represents eight 4-Kbyte pages (1 bit/page). This means the PAM would be 512 bytes long for 16 Mbytes of physical memory. The current version of MMURTL can handle 64 Mbytes of physical memory, making the PAM 2048 bytes long. The PAM is an array of bytes from 0--2047, with the least-significant bit of byte 0 representing the first physical 4-Kbyte page in memory (physical addresses 0--4095).
Physical memory for AllocPage and AllocOSPage is allocated from the top down. For AllocDMAPage, I allocate physical memory from the bottom up. Thus, even if you install a device driver that uses DMA after your applications are up and running, physical memory below 16 Mbytes will be available (that is, if any is left). The PAM shows which pages of memory are in use, not who they belong to. To get this information, you must go to the PDs and PTs.
That's it for memory management--simple but effective. MMURTL's messaging is really its most powerful, and probably its most interesting, feature, but you'll have to read the architecture section of the documentation to find out.
Many people have helped MMURTL along the way. Reginald B. Carey of CSSi (Columbia, MD) is the inspiration behind the MMURTL kernel primitives. Thanks also to Tom Clark and Dan Haynes of the U.S. Coast Guard's Telecommunications and Information Systems Command (Alexandria, VA), Dave McLarty of Convergent Consultants (Atlanta, GA), and Scott Bair of the U.S. Coast Guard.
Copyright © 1994, Dr. Dobb's JournalMMURTL Terms and Definitions
Segmentation
Paging, Page Tables, and
The Memory MAP
Page-Directory Entries
Allocation of Linear Memory
Deallocation of Linear Memory
Allocation of Physical Memory
Acknowledgments
Figure 1 Job map.
Table 1: Entries in the page directory.
==========================================================================
Entry # Description
==========================================================================
0 Physical address of OS PT
1--255 Empty PTEs
256 Physical address of job PT
257--511 Empty PTEs
512 Linear address of OS PT (shadow)
513--767 Empty shadow PTEs
768 Linear address of job PT (shadow)
769--1023 Empty shadow PTEs
==========================================================================
