1. Field of the Invention
The invention relates to apparatus for providing access to memory storage in computer systems, and more particularly, to apparatus and concomitant methods of providing access protection to specific pages of virtual memory space.
2. Description of the Prior Art
Most modern computer systems, particularly mainframe computers, employ high speed random access memory (RAM) circuits as main memory and relatively slow mass memory devices, such as hard disk or magnetic tape drives, as auxiliary (mass) storage. The disparity in access times between random access memory and disk or tape drives is substantial and severe, with the former having access times often ranging in the order of at least tens of milliseconds. Given this disparity, user programs are not executed from auxiliary storage, but rather are transferred therefrom into main memory for execution therein.
In practice, consideration of cost, physical circuitry size and/or power requirements frequently limit the amount of RAM memory that is used in implementing a main memory to a finite real address space which is often substantially less than the maximum address space of a processor that is to access this memory. For example, a processor that operates with a 31 bit virtual address word, which inherently possesses the capability of separately addressing 2.sup.31 (over 2 billion) bytes, may often operate with as little as a few million bytes (Mbytes) of actual RAM. To provide sufficiently rapid execution speeds, the available RAM must be shared among all current user programs that are executing on the processor as well as with a resident portion of the operating system used by the processor. Unfortunately, RAM is rarely, if ever, sized sufficiently large to fully accommodate all the instructions and data that form each such user program and the resident portion of the operating system.
However, it was recognized quite early in the art that, through normal operation of instruction fetches, stack and data accesses, and standard programming techniques, most program instructions possess a rather good spatial locality of reference. This means that, at memory location x in an executing user program, this program will exhibit a strong tendency to interact within relatively small time delays with different but nearby memory locations, such as locations x+1, x+2 and so on. This behavior, often involving preceding instructions, e.g., locations x-1, x-2 and so on, is clearly evident in loops and other similar program structures. Although the organization of external data is often as constrained by the architecture of the processor as are the stack and instruction accesses, such data, particularly arrays, are stored in contiguous memory locations and, as such, often exhibit spatial locality. In this regard, certain programmed operations, such as illustratively clearing, transposing, adding or array multiplication, that at any instance utilize one element of an array will likely access other elements of the array within a short time. Similarly, the art has recognized that instructions and data often exhibit a good temporal locality of reference as well, i.e., where the same memory location is repeatedly accessed over time.
Given these recognitions regarding spatial and temporal localities, the art has turned to and now widely uses a number of memory techniques that attempt to share a relatively small amount of real memory among a number of currently executing user programs, each of which is capable of addressing a much larger memory space. These memory management techniques are generally known as virtual memory techniques.
One such virtual memory technique is paging. Here, in essence, different finite portions, i.e., "pages", of memory data (collectively including both instructions and data values) for each user program, rather than all the memory data for that program, are successively copied ("swapped") from auxiliary storage into main memory and then used for current program execution. Owing to spatial and temporal localities, the main memory contains pages of memory data that not only possess memory locations that have just been recently accessed but also locations that are expected to be subsequently accessed within a very short delay time. With a well designed paging system, the vast majority of memory access time should be spent accessing memory data located within pages previously copied into main memory with relatively little access time being spent in copying new pages of memory data from auxiliary storage.
Specifically, whenever the processor attempts to access memory while executing a user program, the processor issues a so-called "virtual address" for a desired memory datum that is to be accessed. The size of the virtual address is generally only limited by the maximum address space of the processor that is allowed for program usage. By contrast, a so-called "real" or "physical" address is used to directly access memory in order to locate the desired memory datum stored therein. Since the virtual address of any given memory datum is not necessarily the same as its corresponding real address, a translation facility, provided by the operating system working in conjunction with memory access hardware and generally transparent to any executing user program, translates each virtual address issued by the processor to a corresponding real address prior to accessing main memory in order to obtain this datum.
Both virtual and real memory space are divided into fixed sized areas or segments, each of which is, in turn, divided into a number of contiguous pages. Each page is formed of a predefined number of memory locations, typically ranging from 2 to 4 kbytes. Though pages for any program are contiguous in virtual memory; the corresponding physical pages for that program, being swapped into and out of main memory as required by the operating system during on-going program execution, tend to be randomly scattered throughout main memory. A physical page in main memory is often referred to as a "page frame".
The random locations of page frames in main memory necessitates that the operating system maintain address translation, specifically and illustratively segment and page software tables and an address translation process which utilizes these tables for use in translating virtual to real addresses. These tables and the translation process collectively form the address translation facility. For each virtual page copied from auxiliary storage as a page frame into main memory, the address translation tables store the page frame address that corresponds to each virtual page address. Inasmuch as memory locations within any page, whether virtual or real, are contiguous, then through these tables, a virtual address located within such a virtual page can be mapped into a physical address of a location residing in main memory.
Given this virtual addressing scheme, whenever the processor attempts a memory access for a given memory datum during execution of a user program, the processor issues a virtual address for that datum. The datum may currently reside in main memory or it may not. If the datum resides in the main memory, the virtual to real address correspondence for that datum exists in the page and segment tables. As such, the address translation process, upon accessing these tables, extracts the physical address of the datum and thereafter applies this address to the main memory. Once this datum has been accessed, user program execution proceeds accordingly.
If, however, the desired datum does not currently reside within the main memory because a page containing that datum has not yet been swapped into main memory, then no valid entry for its associated virtual page exists in the page and segment tables. As such, the datum must be retrieved from auxiliary storage. Accordingly, the address translation process, upon accessing these tables using that virtual address, produces a page fault. At this point, interpretation of a current instruction (which caused the page fault) halts, the current state of the processor is saved and the processor transfers execution to a software page fault handler. Rather than accessing and copying only the desired datum from auxiliary storage, the page fault handler translates the incoming virtual page address and, then, through input/output controller(s) for an appropriate mass storage device(s), copies an entire page containing that desired datum from auxiliary storage as a page frame into main memory. Thereafter, the fault handler updates the segment and page tables accordingly with a real address for this page. Execution then returns from the fault handler to the address translation process which, in turn, accesses the desired datum from the newly copied page. When appropriate, the fault handler, will subsequently resume execution of the current program instruction that generated the page fault.
The processor must ensure that one user program does not intentionally or accidentally use the pages presently used by another user program or the operating system. The processor performs such memory protection using one or more protection techniques. Typically, main memory is protected by three different protection techniques: storage key protection, low address protection, and page protection. Each protection technique is discussed below.
To facilitate storage key protection, as each page frame is copied into main memory, the processor associates the page frame with a hidden byte known as a storage protection key (hereinafter referred to as a key). The key contains eight bits (one byte); however, only the first four bits are used as the key itself. The remaining four bits of the key are used to indicate page frame status, and are irrelevant to this discussion. As a result of the limited number of bits used for the key, there are only 16 different keys available. Of these 16 keys, key zero is reserved for the operating system. Keys 1 through 15 are assigned to user programs (or individual jobs) as each is executed by the operating system. Since there are only 15 available keys, multiple user programs may be assigned the same key. The key, associated with a particular user program(s) that stores to a given page frame, is itself stored in a register as a hidden byte associated with that page frame.
In practice, the operating system assigns each user program a key. The key is stored in a program status word (PSW) for that particular program. The PSW contains information about each user program presently executing and is stored in a so-called special register within the processor to facilitate repeated access by the operating system during program execution. The specific information carried by the PSW, other than the key, is irrelevant to our page protection technique. Whenever a user program issues a valid virtual address, the translation facility translates the virtual address into a page frame and then the processor compares the key in the PSW of that program to the key associated with that page frame. If the keys are identical, the operating system permits access to that page frame. However, if the keys do not match, the operating system terminates the user program which has attempted an inappropriate memory access. In this manner, a user program cannot inadvertently access (either to read or write) that page frame. Of course, the operating system, having key zero, may access any key protected page frame.
Another memory protection technique protects so-called low address memory space. To maintain a portion of memory that is only alterable by systems programs, the processor uses a low address protection technique. Typically, the first 512 bytes of memory space, known as the low address portion of memory, are reserved for routines which interact with hardware, such as control timer interrupts, supervisor calls, program checks, machine checks, and input/output interrupts. The low address protection technique permits user programs to fetch from the low address portion of memory space. However, user programs are not permitted to store to that memory space.
Another memory protection technique protects individual pages of memory. Using a so-called page protection technique, an entire page of memory can be protected from either inadvertent or intentional memory alteration. Typically, the page protection technique is utilized to protect memory space that is not protected by low address protection. Consequently, page protection enables the processor to protect individual pages of memory within an otherwise unprotected segment of memory. Page protection is used in addition to key protection and provides protection of a memory location from being inadvertently altered by other user programs as well as the operating system. As noted above, key protection does not protect page frames from alterations accomplished by the operating system, i.e., a program using key zero.
Page protection is implemented by setting a page protection bit within a page table entry. The page protection technique blocks a program from storing information to a page that corresponds to a page table entry having a set protection bit. When the protection bit is zero, the processor permits both fetching and storing to a page frame; when the protection bit is one, only fetching from that frame is permitted. In operation, during address translation, the translation routine tests the status of the protection bit for the page frame to which a virtual address points. If a program attempts to store to a location having a set protection bit, e.g., a value of one, the processor interrupts execution of the program.
Typically, during user program execution, the program will request the processor to protect one or more pages of memory. In response, the processor will set the page protection bit for the page frame that the program previously accessed. Consequently, the program requesting the page protection, as well as all other programs having the same key or key zero, may only fetch information from the protected page. Subsequently, the program that requested page protection may wish to write to the protected page. To do so, the processor must first change the page protection bit to zero, then the program alters information within the previously protected page. While the protection bit is set to zero, the entire page is open to inadvertent alteration by other programs which have the same key as the program that requested page protection. In addition, the operating system, having key zero, may inadvertently write to the presently unprotected page. Inadvertent storage, known as overlay, typically occurs when a power failure or programming error causes a program to write to an incorrect address.
Thus, a need exists in the art to provide a memory space protection technique which allows a program that has requested page protection to both read and write information to its protected page without opening the page to inadvertent overlay. Such a memory protection technique must be compatible with present virtual memory storage systems and their present protection techniques, i.e., storage key protection, low address protection and page protection.
USPTO Backgrounds
USPTO Backgrounds