DIRECTORY Basics USING [BITAND, BITSHIFT, LongNumber], PrincOps USING [bytesPerPage, PageCount, PageNumber, wordsPerPage]; VM: CEDAR DEFINITIONS IMPORTS Basics = BEGIN PageNumber: TYPE = PrincOps.PageNumber; PageCount: TYPE = PrincOps.PageCount; Interval: TYPE = RECORD [page: PageNumber, count: PageCount]; nullInterval: Interval = [page: 0, count: 0]; PageState: TYPE = RECORD [ dataState: DataState, readOnly: BOOL, -- altered only by MakeReadOnly and MakeReadWrite hasRealMemory: BOOL, -- altered only by SwapIn and MakeUndefined needsCleaning: BOOL, -- a hint for clients of "Clean" pinCount: INT -- altered only by Pin and Unpin ]; DataState: TYPE = { none, undefined, unchanged, changed}; State: PROC [page: PageNumber] RETURNS [state: PageState]; SetDataState: PRIVATE UNSAFE PROC [interval: Interval, dataState: DataState]; VMPartition: TYPE = {lowCore, pda, mds, normalVM}; LogPageCount: TYPE = NAT[0..23--LogBase2[PageCount.LAST]-1--]; Allocate: PROC [count: PageCount, partition: VMPartition _ normalVM, subRange: Interval _ nullInterval, start: PageNumber _ 0, alignment: LogPageCount _ 0, in64K: BOOL _ FALSE] RETURNS [interval: Interval]; CantAllocate: ERROR [bestInterval: Interval]; Free: UNSAFE PROC [interval: Interval] = TRUSTED INLINE {SetDataState[interval, none]}; SwapIn: UNSAFE PROC [interval: Interval, kill: BOOL _ FALSE, pin: BOOL _ FALSE, nextPage: PageNumber _ 0]; Kill, MakeUndefined: UNSAFE PROC [interval: Interval] = TRUSTED INLINE {SetDataState[interval, undefined]}; Touch: PROC [interval: Interval] = TRUSTED INLINE {SwapIn[interval: interval]}; Pin: PROC [interval: Interval] = TRUSTED INLINE {SwapIn[interval: interval, pin: TRUE]}; Unpin: PROC [interval: Interval]; MakeReadOnly: PROC [interval: Interval]; MakeReadWrite: PROC [interval: Interval]; MakeUnchanged: PROC [interval: Interval] = TRUSTED INLINE {SetDataState[interval, unchanged]}; MakeChanged: PROC [interval: Interval] = TRUSTED INLINE {SetDataState[interval, changed]}; Clean: PROC [interval: Interval]; Age: PROC [interval: Interval]; AddressFault: ERROR [address: LONG POINTER]; WriteProtectFault: ERROR [address: LONG POINTER]; CantDoIO: ERROR [reason: IOErrorType, page: PageNumber]; IOErrorType: TYPE = {software, hardware}; wordsPerPage: NAT = PrincOps.wordsPerPage; bytesPerPage: NAT = PrincOps.bytesPerPage; PagesForWords: PROC [words: INT] RETURNS [pages: PageCount] = INLINE { longA: Basics.LongNumber = [li[li: words+wordsPerPage-1]]; longB: Basics.LongNumber = [bytes[lh: longA.hl, ll: longA.lh, hh: 0, hl: longA.hh]]; RETURN[longB.li] }; WordsForPages: PROC [pages: PageCount] RETURNS [words: INT] = INLINE { longA: Basics.LongNumber = [li[li: pages]]; longB: Basics.LongNumber = [bytes[lh: longA.ll, ll: 0, hh: longA.hl, hl: longA.lh]]; RETURN[longB.li] }; PagesForBytes: PROC [bytes: INT] RETURNS [pages: PageCount] = INLINE { n1: Basics.LongNumber = [li[li: bytes+1]]; n2: Basics.LongNumber = [num[ lowbits: Basics.BITSHIFT[n1.lowbits, -1] + (IF Basics.BITAND[n1.highbits, 1] = 1 THEN 100000B ELSE 0), highbits: Basics.BITSHIFT[n1.highbits, -1] ]]; RETURN[PagesForWords[n2.li]] }; BytesForPages: PROC [pages: PageCount] RETURNS [bytes: INT] = INLINE { words: INT = WordsForPages[pages]; RETURN[words+words] }; AddressForPageNumber: UNSAFE PROC [page: PageNumber] RETURNS [address: LONG POINTER] = INLINE { longA: Basics.LongNumber = [li[li: page]]; longB: Basics.LongNumber = [bytes[lh: longA.ll, ll: 0, hh: longA.hl, hl: longA.lh]]; RETURN[LOOPHOLE[longB.lc]] }; PageNumberForAddress: PROC [address: LONG POINTER] RETURNS [page: PageNumber] = INLINE { longA: Basics.LongNumber = LOOPHOLE[address]; longB: Basics.LongNumber = [bytes[lh: longA.hl, ll: longA.lh, hh: 0, hl: longA.hh]]; RETURN[longB.li] }; lowCore: UNCOUNTED ZONE; END. 9¶VM.mesa last edited by Levin on September 20, 1983 11:56 am Basic Types The fundamental entities in which the VM traffics are page numbers and page counts, defined by the following types. Implementation note: The language doesn't allow us to express this precisely the way we would like: INT[0..2^24). Implementation note: The language doesn't allow us to express this precisely the way we would like: INT[0..2^24]. Their base representation (in PrincOps) is as INTs, but in reality they are non-negative quantities. Although they have 32-bit representations, they are actually limited by the addressing capabilities of the architecture. A virtual address is 32 bits, and since a page is 256 words (see wordsPerPage, below), the maximum page count is 232/28 = 224. Many of the virtual memory operations manipulate a sequence of consecutive pages in the address space; hence it is convenient to define the following: Page State Manipulation Each page in the virtual memory has a client-visible state, called its PageState. Most of the operations in this interface alter the PageState(s) of the page(s) passed as parameters to them. For the convenience of the client (and occasionally to improve performance), operations generally apply to an Interval rather than an individual page. Any operation defined on an Interval manipulates the pages of the interval in an undefined order. If the operation completes without error, each page will have had the operation applied to it exactly once. However, if an error is reported (e.g., AddressFault), no assumptions can be made about the PageStates of the pages in the interval (other than the information implicit in the error report). In particular, the operation may have been applied successfully to some pages in the interval and not to others. This type describes the state of the contents of a virtual memory page, independent of whether it presently resides in real memory or in backing storage. The responsibility for maintenance of this state is shared between the implementation of this interface and the client. "none" means that the virtual page has no associated backing storage; i.e., it is unallocated. "undefined" means that no location of the page has a well-defined value. This is the initial state of pages obtained via Allocate[...]. Whenever a location in an allocated virtual memory page is altered, the page data enter the "changed" state. This state is exited only by explicit use of SetDataState; in particular, the "unchanged" state can be reached only by invoking MakeUnchanged. It should be noted that the unchanged/changed distinction is not the same as the hardware-supported clean/dirty distinction. The latter is not visible to the client of this interface (although the "needsCleaning" bit is a close approximation). Explicit changes to a page's dataState are made using Free, Kill, MakeChanged, and MakeUnchanged. This procedure appears here only to satisfy the inline definitions of Free, Kill, MakeChanged, and MakeChanged. In most cases, the PageState of a virtual memory page changes only as the result of an operation on that page. (In this context, "operation" means a procedure in this interface or a memory access within the addresses bounded by the page. Thus, a successful store into a page is construed as an operation that changes the page's dataState to "changed".) However, there is one important exception. The "hasRealMemory" field of a page's PageState may change asynchonously with operations on the page. This is because the virtual memory system employs a replacement algorithm that occasionally alters the correspondence between virtual and real memory. When real memory is required by a virtual page for which "hasRealMemory" is FALSE, the replacement algorithm considers pages for which "hasRealMemory" is TRUE and chooses a suitable victim. The requestor's "hasRealMemory" state becomes TRUE; the victim's becomes FALSE. The replacement algorithm's decision process can be affected by certain operations in this interface (e.g., Pin, Age). Virtual Memory Allocation Virtual memory is divided into four (disjoint) partitions: The "normalVM" partition describes regular virtual memory and is the one that most clients will use. The remaining three partitions are rather special and are intended for use by knowledgeable clients providing low-level I/O and architectural support facilities; such clients will necessarily operate below the safe language level. Allocate searches the specified partition of virtual memory for an interval such that (1) for each page in "interval", State[page].dataState = none, (2) interval.count = count, (3) if subRange.count >= count, then "interval" is contained in "subRange", (4) interval.page MOD 2alignment is zero, and (5) if start is non-zero, then interval.page-start is minimal, and (6) if in64K is TRUE, then the interval does not cross a 64K word boundary. If such an interval is found, it is returned and, for every page in "interval", State[page] = [dataState: undefined, readOnly: FALSE, hasRealMemory: FALSE, pinCount: 0] If no such interval can be found, CantAllocate is raised, passing a interval "bestInterval" such that (1) for each page in "bestInterval", State[page].dataState = none, (2) bestInterval.count < count with count-bestInterval.count minimal, and (3) if subRange.count >= count, then "bestInterval" is contained in "subRange", Note that "bestInterval" has no guaranteed alignment properties. Performance note: if in64K is TRUE (and partition = normalVM), the allocator adopts a "clumping" policy that will tend to segregate storage allocated with in64K = TRUE from other storage. The allocator will put aside "clumps" of 64K words aligned on 64K word boundaries and satisfy all requests with in64K = TRUE from these clumps. This is intended to be used for "long-term" storage, like code segments and display bitmaps, in order to cut down on virtual memory fragmentation. This error is raised by Allocate and gives the largest available interval within the requested one. Free makes previously allocated memory again available for allocation. If, for any page in "interval", State[page].dataState = none, AddressFault is raised. Procedures that may affect the virtual-real memory correspondence SwapIn ensures that real memory is associated with the specified interval of virtual memory. Common variants (Touch and Pin) are defined separately for convenience and clarity. The "kill" parameter permits an optimization of the client's code: if TRUE, the equivalent of SetDataState[interval, undefined] is first performed. The subsequent behavior of SwapIn for each page in "interval" is as follows: If State[page].dataState = none, AddressFault is raised. If State[page].hasRealMemory = FALSE (i.e., the page does not already have associated real memory): A real memory page is assigned, causing State[page].hasRealMemory to become TRUE. In doing so, other virtual memory pages with associated real memory and for which State[otherPage].pinCount = 0 may have their real memory reclaimed (after ensuring that its data are written to backing storage). If State[page].dataState is "unchanged" or "changed", the real memory page is set to the contents of the corresponding backing storage page (i.e., it is read from the disk). State[page].dataState is unaffected by this procedure. If "pin" is TRUE, State[page].pinCount is incremented by one. The implementation may perform certain optimizations that cause the actual order of state changes to differ from the sequence implied by this description. In particular, disk transfers may be batched, and if an address fault is detected within the interval, there is no guarantee that the preceding pages in the interval will have reached the states implied by the above description. Furthermore, if "kill" is TRUE, the implementation may optimize the real memory management to avoid freeing and reallocating memory. The "nextPage" parameter is a hint to be used in optimizing the disk arm; if it is non-zero, the disk driver will be informed that the likely subsequent disk operation will be to the backing storage page associated with "nextPage". The primary clients of SwapIn will be the PageFault process, which will call with kill and pin FALSE, and the File system, which will typically call with kill = reading and pin = TRUE before initiating an i/o operation. If, for any page in "interval", State[page].dataState = none, AddressFault is raised. Otherwise, for each page in "interval", State[page].dataState is set to "undefined" and State[page].hasRealMemory becomes FALSE (i.e., any associated real memory is reclaimed). If, for any page in "interval", State[page].dataState = none, AddressFault is raised. Otherwise, for each page in "interval", State[page].hasRealMemory becomes TRUE, causing memory accesses to the page to proceed without delay. Since the real memory has not been pinned (see below), the real memory may be reclaimed by the replacement algorithm at any time. This procedure would generally be used by a client who plans to reference an interval in the near future and wants to avoid the delay of a page fault, e.g., Process.Detach[FORK Touch[interval]]. Virtual memory pages can be "pinned" in real memory; that is, their contents can be forced to reside in main storage until they are subsequently unpinned. Since pinning reduces the pool of pages that can participate in the replacement algorithm, it should be used only when logically required and not to try to reduce swapping (it is likely to have just the opposite effect). Consequently, only specialized clients should use Pin and Unpin. For each page in "interval", the following actions occur: If State[page].dataState = none, AddressFault is raised. If State[page].hasRealMemory is FALSE, a page of real memory is acquired, causing State[page].hasRealMemory to become TRUE. Then, unless State[page].dataState is "undefined", the real memory page is set to the contents of the corresponding backing storage page (i.e., the page is read from disk). State[page].pinCount is incremented by one. For each page in "interval", the following actions occur: If State[page].dataState = none, AddressFault is raised. If State[page].pinCount is greater than zero, it is decremented by one. Upon completion of Unpin, any page in "interval" for which State[page].pinCount = 0 becomes eligible for consideration by the replacement algorithm. Procedures that do not affect the virtual-real memory correspondence The following two procedures alter the "readOnly" field of a PageState. These procedures affect only the virtual memory system's data structures; they do not cause any I/O operations to occur as side-effects. If, for any page in "interval", State[page].dataState = none, AddressFault is raised. Otherwise, for each page in "interval", State[page].readOnly becomes TRUE. A subsequent attempt to store into any page of the interval will cause WriteProtectFault to be raised. If, for any page in "interval", State[page].dataState = none, AddressFault is raised. Otherwise, for each page in "interval", State[page].readOnly becomes FALSE. The following two procedures alter the "dataState" field of a PageState. These procedures affect only the virtual memory system's data structures; they do not cause any I/O operations to occur as side-effects. If, for any page in "interval", State[page].dataState = none, AddressFault is raised. Otherwise, State[page].dataState is set to "unchanged". Note: MakeUnchanged can be used by a client to detect when the contents of a virtual memory page have been altered, since any store causes the page's dataState to become "changed". If, for any page in "interval", State[page].dataState = none, AddressFault is raised. Otherwise, State[page].dataState is set to "changed". Performance Accelerators The procedures described here have no visible effect on the PageState and therefore are not formally necessary. However, they do affect the performance of the virtual memory implementation and are intended for use when the client has particular knowledge of the virtual memory reference patterns. If, for any page in "interval", State[page].dataState = none, AddressFault is raised. Otherwise, this procedure ensures that the backing storage for each page in the interval contains the same information as the associated real memory (if any). If, for any page in "interval", State[page].dataState = none, AddressFault is raised. Otherwise, this procedure increases the likelihood that the backing storage associated with pages in the interval will be selected for replacement. However, this procedure does not initiate any I/O operations. Errors The following two errors generally arise from erroneous memory accesses to virtual memory. AddressFault means that an unallocated page (i.e., one for which State[page].dataState = none) has been referenced. (The name AddressFault is intended to suggest that the program performing the access has an incorrect address.) Following this model, the operations in this interface raise AddressFault if any page they are asked to manipulate is unallocated. WriteProtectFault is raised by an attempt to store into a page for which State[page].readOnly is TRUE. No operations in this interface raise WriteProtectFault explicitly. CantDoIO is raised by SwapIn (including its derivatives Touch and Pin) and Clean when the input/output operation from/to backing storage cannot be performed. The "reason" parameter is a generic classification of the cause of the error. Utilities It is frequently necessary to convert between counts in different units (pages, words, bytes) and between counts and addresses. The following definitions and procedures are copied from the PrincOps and PrincOpsUtils interfaces to avoid forcing clients to acquire those interfaces for these common operations. Implementation note: These implementations are temporary ones (see PrincOpsUtils) that should be updated to the commented-out versions when the Trinity instruction set is adopted. RETURN[Basics.DBITSHIFT[words, -logWordsPerPage]] RETURN[Basics.DBITSHIFT[pages, logWordsPerPage]] RETURN[Basics.DBITSHIFT[bytes, -logBytesPerPage]] RETURN[Basics.DBITSHIFT[pages, logBytesPerPage]] RETURN[Basics.DBITSHIFT[page, logWordsPerPage]] RETURN[Basics.DBITSHIFT[address, -logWordsPerPage]] Special-purpose Facilities The following zone provides a simple way for obtaining small blocks of storage from the first 64K of the virtual address space. All such memory is permanently resident. At present, only lowCore.NEW is supported; lowCore.FREE doesn't actually reclaim any storage. The block of memory returned by lowCore.NEW is guaranteed to be 16-word aligned. Ê­– "Cedar" style˜Jšœ™Jšœ3™3J˜šÏk ˜ Jšœœœ œ ˜,Jšœ œ5˜C—J˜Jšœœ œœ ˜&J˜Jš˜head2™ Ibodyšœs™sJ˜šÏn œœ˜'IitemšÏss™s—šž œœ˜%MšŸs™s—J˜LšœÒÏuœ œ œ™ÞLšœ–™–J˜Jšžœœœ&˜=J˜-J˜—™L™ÙJ™šž œœœ˜Jšœ˜Jšœ œÏc1˜BJšœœ¡+˜AJšœœ¡ ˜6Jšœ œ¡ ˜/Jšœ˜—šž œœ˜Jšœ%˜%Lšœú™úL™ô—J˜Jšžœœœ˜:L™a˜Jšž œœ,˜MLšŸo™oL™—L™–—™Lšœ:™:J˜Jšž œœ!˜2L™ÌJ˜Jšž œœœ¡œ˜>J˜Jš žœœ•œœœ˜ÎJ™LšœU™UMšœ>™>Mšœ™MšœK™KMšœ  œ ™-MšœB™BMšœK™KLšœO™OMšœX™XLšœe™eMšœB™BMšœI™IMšœO™OL™@LšŸá™á˜Jšž œœ˜-Jšœc™c—J˜šžœ œ˜&Jšœœ ˜0—Lšœ™L™—™ALšœ±™±J˜š žœ œœœœœ˜jšœâ™âMšœ8™8šœc™cM™¦M™­—M™6M™=—Lšœ…™…Lšœç™çL™Û—J˜šžœ œ˜5Jšœœ%˜5Lšœ‡™‡—J˜šžœœ˜ Jšœœ˜.Lšœç™çLšœÂ™Â—L™ºJ˜šžœœ˜Jšœœ"œ˜9L™9Mšœ8™8Mšœ©™©M™+L˜—šžœœ˜!L™9Mšœ8™8MšœG™GLšœ”™”—J˜—™DLšœÑ™ÑJ˜šž œœ˜(Lšœ‰™‰—J˜šž œœ˜)Lšœ¢™¢—LšœÒ™ÒJ˜šž œœ˜(Jšœœ%˜5LšœŽ™ŽL™µ—J˜šž œœ˜&Jšœœ#˜3LšœŒ™Œ—J˜—™Lšœ©™©L™šžœœ˜!Lšœõ™õ—J˜šžœœ˜Lšœ©™©——™Lšœñ™ñJ˜Jšž œœ œœ˜,Jšžœœ œœ˜1J˜Lšœì™ìJ˜Jšžœœ)˜8˜Jšž œœ˜)—J˜J˜—™ Lšœµ™µL™Jšœœ˜*Jšœœ˜*J˜LšŸ´™´J˜šž œœ œœ˜;Jšœœ˜ Jšœ œ™1Jšœ:˜:JšœT˜TJšœ ˜Jšœ˜J˜—šž œœœ œ˜;Jšœœ˜ Jšœ œ™0Jšœ+˜+JšœT˜TJšœ ˜Jšœ˜J˜—šž œœ œœ˜;Jšœœ˜ Jšœ œ™1Jšœ*˜*šœ˜šœœ˜*Jš œœœœ œ˜;—Jšœœ˜*J˜—Jšœ˜Jšœ˜J˜—šž œœœ œ˜;Jšœœ˜ Jšœ œ™0Jšœœ˜"Jšœ ˜Jšœ˜J™—š žœ œœ œœ˜TJšœœ˜ Jšœ œ™/Jšœ*˜*JšœT˜TJšœœ ˜Jšœ˜J˜—š žœœ œœœ˜MJšœœ˜ Jšœ œ™3Jšœœ ˜-JšœT˜TJšœ ˜Jšœ˜J˜——™LšœÚ™ÚJ˜Jšžœœ˜—J˜Jšœ˜J˜—…—ÚP=