Notes for CSC 2/456, 2-16-2000 ff Miscellaneous topics in memory management ============================ Mach case study Reference: Machine Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures by Rashid et al, 2nd Int'l Conf. on Architectural Support for Programming Languages and Operating Systems, Oct 1987. IEEE Trans. on Computers, Aug. '88. Essentially the same system that's now in Solaris, NetBSD, FreeBSD, and Digital Unix (True64). Design Goals support large sparse virtual address spaces support memory sharing between tasks (processes) efficient message-passing via copy-on-write virtual copy operations user provided backing store and pagers not clear in hindsight whether anybody cares about this separate software memory management from hardware support (portability) Hardware Assumptions an ability to handle and recover from page faults -- that's it Definitions task - execution environment (incl address space) for threads to execute thread - basic unit of cpu utilization (a pc) message - typed collection of data objects used in communication memory object - collection of data available from a pager (can be mapped into an address space) Data Structures Pmap: The hardware defined physical address map. Machine dependencies are isolated in the software that manages the pmap. The pmap is really used as a hint; at fault time all virtual memory information can be reconstructed from the machine-independent data structures. Resident page table: A machine independent page table. Entries correspond to machine-independent pages, which are constructed using some power-of-two multiple of physical pages. Entries may be simultaneously linked onto several lists, including a memory object list (which links the pages within an object), a memory allocation queue (including "free", "reclaimable", and "allocated"), and a hash bucket (used for lookup during page faults). Reading between the lines (I should check this with an expert), it appears that the hash table is separate from the resident page table. The resident page table itself has one entry per machine-independent physical page, and can therefore be perused by the pageout daemon. The hash table is keyed on (memory object/offset) and uses open chaining. The buckets themselves lie in the resident page table. Address map: A doubly linked list of map entries, describing a mapping from a range of virtual addresses to a region of a memory object. Each entry defines a contiguous region of memory with common protection and inheritance attributes. In effect, the address map implements a (potentially) sparse segmented memory constructed from logical pages, which are themselves constructed from multiple physical pages. Share map: Similar to an address map, it defines a region of memory shared by two or more tasks. Each share map is pointed to by multiple address map entries, one (or more) for each task sharing the region of memory defined by the share map. In effect, the share map allows multiple tasks to refer to a region of memory using a common indirect reference, namely the share map, so that one task can change the structure of the shared memory (ie, cause it to become copy-on-write) without explicitly notifying all tasks sharing the memory. Copy-On-Write To avoid the cost of copying large amounts of data, Mach (and Accent, Mach's precursor) makes "logical" copies, simply by manipulating address maps. Two address spaces can then refer to the same physical memory (or copy) without actually performing a copy operation. If a page in the common copy is ever modified, a real copy has to be performed (although only the single page need be copied). In effect, the copy is performed using lazy evaluation; only those pages actually modified are ever copied. Shadow Objects When a user attempts to modify a page that is marked readonly in order to implement copy-on-write, a fault occurs. A new memory object, called a shadow object, is created that contains the modified pages. Logically, the shadow object defines the entire copy-on-write region; in actuality it relies on the old memory object for unmodified pages. The shadow object is inserted into the list of memory objects that define the corresponding region. The creation of shadow objects, as a result of copy-on-write, causes a memory region to be implemented by multiple memory objects, which are chained off the corresponding address map entry. Since we expect that most pages marked copy-on-write are never actually modified, we would expect that the lists of objects defining a region are short. Note also that shadow objects are chained off share maps if necessary, so all tasks sharing the memory see the new copy. Chains can grow arbitrarily long if shadow objects are also shared copy-on-write, but Mach squeezes out any shadow maps that end up shadowing *all* of the next object down the chain. This keeps the chains from getting outlandish if, say, process A forks process B, which forks process C, etc. Handling Page Faults Suppose a page fault for virtual address N occurs. This simply means the address translation was not found by the hardware (either in the TLB or the hardware page table). We then: - search the address map sequentially (address maps are assumed to have 4-5 entries on average) for the entry whose range of addresses includes N; the entry gives the page offset of the region within the virtual address space defined by the address map. - if the address map entry points to a sharing map, search that map sequentially for the appropriate entry. - the entry points to a list of memory objects that contain the pages in the region. All but the last of these will be a shadow object. - for each memory object, determine if the needed page is in that object * hash on memory object/offset pair to resident page table * if found, then retrieve physical address from page table entry * if not found, ask (default) pager associated with the memory object for the memory * if pager doesn't have page, repeat lookup on next object Other typical operations Pageout daemon (Unix policy, roughly) scans resident page table. Maintains three lists, linked through the page entries: free list, reclaimable list (pages not mapped, but containing useful things), and allocated list. There is a separate "object cache" that contains memory objects that aren't in any address map, but which the kernel thinks are likely to be wanted in the future. Copy on write and similar operations that affect all or much of a memory object use the links that chain together all the pages of a particular memory object. Pmaps Physical page tables (if any) are considered a cache for the information in the machine-independent page tables, much as the TLB is a cache for the information in the physical page tables (if any). Each address map entry indicates the "current" and "maximum" rights for a range of addresses in a particular address space. Neither of these is necessarily the same as the rights known in the pmap layer. The maximum rights indicate what the task is logically entitled to. The current rights indicate what the machine-independent layer is giving to the task at the moment. These may be less is the page is being handled copy-on-write. The pmap rights are less than or equal to the current vmap rights. There are several reasons the pmap rights might be less than the vmap rights: (1) on a machine with linear page tables, you can't afford to have a whole sparse address space in the pmap at once. Some entries may be missing entirely. (2) on a machine with an inverted page table, you can't have more than one translation for a given frame at a given time (see below). (3) if you're using virtual memory to maintain coherence in a distributed system (this is a hot topic these days), the pmap layer may turn rights off because the up-to-date copy of a page is currently located on a different processor. The pmap layer guarantees that when it is told to increase the rights of a mapping, the new rights will persist long enough for the faulting thread to make forward progress. --------------------- Swap space management BSD 4.4 has four built-in pagers: one that pages to/from files, one to/from memory-mapped devices, one from zero-fill memory, and one to/from "swap space". Mach originally used vnode pagers instead of the swap space pager. Paging was therefore done to ordinary files. The BSD people decided, however, that the ordinary file system didn't deliver a large enough fraction of the available disk bandwidth, so they built this special one. It requires dedicated (at boot time) hardware disk partitions. Pages from different processes are all mixed together in the swap space. The kernel does NOT have to pre-allocate space for processes at load time; it allocates pages of swap space on demand. ============================ Inverted page tables (ala IBM PC/RT, Power PC) Linear and tree-structured page tables are easy to understand. The vmap layer in Mach uses a linked list to provide a very space-efficient representation of sparse address spaces. The one organization we haven't really looked at in any detail is the inverted page table. The idea is similar to the hash table used in the Mach vmap layer, but with a different purpose (pmap-level information). PC/RT Address translation: start with a 32-bit "short virtual address". Interpret the top four bits as a segment register name (16 segment registers). Replace those top four bits with the contents of the 12-bit segment register to form a 40-bit "long virtual address". Look this up in the (single, global) inverted page table (see below). Segment registers are local to each process (so my 5th segment is different from yours), but segment register contents have to be globally unique: long virtual addresses specify locations in a system-wide space. Note contrast to x86: segment registers are not generally visible to the assembly language programmer on the PC/RT -- program just uses 32-bit addresses. This makes passing pointers to subroutines a lot easier. It also allows the use of extra-big "virtual segments" by loading segment ids of two real segments into adjacent segment registers. There is one inverted page table for the whole system, NOT for each process. This table contains one entry for each physical frame, NOT each virtual page. It is therefore great for representing sparse address spaces. However it does not have all the information a regular page table has -- the OS has to keep track of all the information about invalid pages. Assuming we have hardware TLB reload, the page table lookup algorithm works like this: we take the (long) virtual address [ = (segment id, virtual page, page offset)] of the referenced page and apply a hash function to it. On the IBM PC/RT, the hash function is the xor of the virtual page number and the segment number. The hash value gives an index into the page table. For good hash table behavior, we want there to be more table entries than there are page frames (maybe twice as many). But each frame requires a significant amount of space to describe it (~128 bits), and we don't want to spend that on empty entries. So the hash table on the PC/RT is separate from the page table and contains only page table indices. The page table entries themselves contain (1) segment id and virtual page number (tag), (2) hash chain pointer (another page table index), and (3) protection information (including sub-page transaction lock bits on the PC/RT, to support database transactions. There is exactly one page table entry per physical frame. The translation for a given segment/vpage pair is the page table index at which a matching entry is found. This will either be the index specified in the the hash table at the index of the hash value, or the index specified in the chain field of some entry reached from there. Problem: things don't work right if the system has two virtual addresses for the same physical address, either within one process or among processes. These can happen, for example, as a result of copy-on-write for message passing. We can't have two page table entries for the same frame -- where would we put the modify bit? Mach addresses this problem by remembering that the pmap is just a hint -- it keeps only one of the mappings in the page table at a time, and suffers a page fault on pinging references -- correct, but not very good performance. Reference: Chang and Mergen, "801 Storage: Architecture and Programming," ACM TOCS, Feb. 1988, pp. 28-50. ============================ The TLB (ATC) shootdown problem. Suppose we have a multiprocessor. Every processor has its own TLB, but some of the memory is shared. Page tables may be shared or private. If we change a page table entry that another processor may be using, we have to force that processor to get its TLB consistent with the page table. Adding something to a page table doesn't hurt (the other processor will fix up its TLB on the next miss), but removing something from a page table does hurt (we don't want the other processor to go on using it). There are several schemes for assuring consistency. The kernel needs to know which processors may be using a page table entry. It has to stop them from using it while it's being changed, and force them to fix their TLBs after changing it. Note that modify bits kept in TLBs have to be found during pageout. Moreover, when the hardware kicks out a TLB entry to make room for another one, we have to make sure that it doesn't write the (old) data entry back to the page table in order to set modify bits, when somebody has changed something in between. The 68030 uses a RMW operation to write out the modify bit, which is ok, but many processors write back the whole TLB entry. In a similar vein, if the OS is using a bigger page size than the hardware, there is the possibility that the HW will look at two (or more) page table entries that we are in the process of changing, and see inconsistent data. If we always stall a processor when changing its page table we can make sure that neither of these problems occurs. Algorithms: CMU Mach initiator locks the page table, queues a shootdown request on each "responder", and sends them remote interrupts each responder acknowledges interrupt by removing itself from the list of active processors, and then spins on the page table lock, waiting for the update to be completed initiator makes changes and unlocks the page table, terminating spins responders flush appropriate TLB entries and proceed (special care is needed to avoid deadlocks and to lock out interrupts at appropriate times) RP3 Mach avoids spinning in responders. spinning was needed because HW might otherwise re-write stale page table entries, and because Mach changes mappings for large virtual pages that may have multiple HW page table entries, which must be changed atomically. RP3 lacks these two problems. initiator locks page table, makes changes, and attaches a note describing the changes. It then sends an interrupt to each responder. each responder flushes its TLB as necessary and modifies a shared data structure to indicate it did so initiator waits for the data structures to change, then removes change notice and unlocks page table Platinum uses separate page tables for every processor; does not need to synchronize single page table with multiple TLBs. In particular, the problems of multi-frame pages and full-entry writebacks of dirty bits do not arise, because no processor ever modifies the table from which another processor will do HW TLB reloads. (This is a general solution to the problem that the RP3 avoids by not using multi-frame pages.) initiator attaches notice to Cmap (coherent level page table), with bitmap of responders, and sends an interrupt to each responder. The bitmap is initialized from the list (contained in the Cmap) of all processors in which the translation is currently in use. Because it is a *subset* of the processors in which the translation *might* be in use, it allows the initiator to avoid sending interrupts to any processors in which the address space is not currently active. Initiator is guaranteed that when the interrupt-causing instruction completes, the remote processor is no longer executing user code. This is crucial. each responder changes its own page table and TLB, and removes itself from the bitmap. if the bitmap is then clear it removes the message from the page table. Q: why does initiator have to wait in RP3 Mach? Why can't the last responder remove the change notice and unlock the page table? Is this just an oversight on the part of the RP3 people, or is there some reason the initiator can't continue until all users of the physical page table have been synchronized? A, from Bryan Rosenberg, the inventor of the algorithm: In general, a TLB shootdown operation is invoked in the middle of some operation (writing a page out to disk, for example), that can't correctly proceed until no further uses of the old page table entry are possible. There's nothing in the TLB shootdown process itself that requires the initiator to wait, but the code that invoked the shootdown relies on the fact that once the shootdown returns, no other processor will use the old page table entry. I suppose it would be possible to package up the entire computation that required the shootdown into some sort of continuation, and to then let the last responding processor complete the computation, but that sounds like a lot more trouble than it's worth. ============================ Caches Fifteen years ago many computers didn't have caches. Now almost all of them do. Improvements in processor speed have been outstripping improvements in bus and memory speed, so you can no longer afford to wait for memory on every load or store. Recall that TLBs are built out of associative memory. That's memory where instead of saying "what's in location X" you say "what's in the second half of the location whose first half contains X". Fully-associative memory is difficult to build. Two problems: (1) you have to broadcast the thing you're looking for to all locations, which takes more gate delays the larger the memory is, and (2) you have to have a separate comparator for everything you check in parallel. People build fully-associative TLBs, but they tend to have fewer than 100 entries. Caches have thousands of entries. People don't build fully-associative caches. Caches are generally "set-associative". That means that if tag X is in the cache, it is guaranteed to be in one of a small set of locations. Typical caches are 1, 2, or 4-way set associative. 1-way set-associative caches are called "direct mapped" caches. We can think of a cache as being a two-dimensional table, where the low-order bits of the tag specify the row, and the number of columns equals the degree of associativity. Now we need one comparator for each column. Performance problems result if a program on a k-way set associative machine has more than k locations in its working set that need to go in the same set in the cache. In such a case the program will suffer many cache misses. Each entry in a cache is called a "line". Lines are generally larger than single words and smaller than pages. Implementations tend to range from 8-128 bytes. When you get a cache miss on a read or a write (that is, the word you're accessing isn't in the cache), the cache brings in the whole line containing the word you're accessing. Caches improve performance for two reasons: (1) temporal locality -- if a program accesses a variable once, it's likely to access it again soon. (2) spatial locality -- if a program accesses a given variable, it's likely to access nearby variables soon. Keeping something in the cache exploits temporal locality. Bringing in a whole line full of nearby stuff on a miss exploits spatial locality. There is a trend (in uniprocessors) toward larger cache lines, in order better to exploit spatial locality. The trend is possible because busses are getting wider, to pump up their bandwidth in the absence of significantly faster bus clock rates (which are limited by capacitive loading). On multiprocessors, longer lines make cache coherence (see below) more of a problem -- they increase the likelihood that multiple processors will be accessing *something* within a given line. This is the "false sharing" problem. ---------------- Often a processor has more than one cache. Nowadays the *primary* cache is always on-chip, and can usually be accessed in 2 processor cycles. Typically (though not always), there is one primary cache for instructions and one for data, both direct mapped. This "split I and D" approach reduces the number of collisions in the cache, since instructions and data never collide with each other. Primary caches tend to be in the 8K-64K range. If you go much bigger than that you can't get at the contents in only 2 cycles. Many processors have a secondary cache on-chip. This may take up to about 10 cycles to access. Secondary on-chip caches today tend to be in the 256K-1MB range. A high-performance computer, especially one that is expected to execute programs with large working sets, often has an off-chip cache as well. Off-chip caches are usually implemented with SRAM chips, which are faster but more expensive than DRAM chips (from which main memory is constructed). At present, off-chip caches typically take about 50 cycles to access. Main memory may take 100 or more. Secondary and tertiary caches (on-chip and off) are typically combined (no split I and D), and 2 or 4-way set-associative. Typical off-chip caches are currently measured in small numbers of megabytes. ---------------- When a processor writes a word, the write has to get back to memory at some point, so other processors (or later computation on the same processor, some time after the line has been evicted) can see it. There are two main choices here: write-through caches and write-back caches. Write-through caches always send a write on to memory immediately, though they let the processor continue as soon as the data has been written to the cache. Write-back caches have dirty bits, much like TLB entries. Dirty lines are written back to memory when evicted. Write-through caches are simpler to build, but generate more bus traffic. The traffic can be reduced somewhat by using a "write-merge" buffer that holds onto the last several writes, combining any that go to the same line of memory. In systems with two-level caches, it is common for the primary cache to be write-through (the data path between the primary and secondary caches doesn't go over a bus, and can sustain high data rates) and for the secondary cache to be write-back (to minimize bus traffic). It is also common for primary caches to be "virtually tagged," meaning that the index calculation is based on the virtual address, rather than the physical address, so that the initial part of the lookup can proceed in parallel with address translation. Even if virtually tagged, they are usually physically indexed, meaning that the translation has to be complete by the time the comparators are looking to see if the tags are right. ---------------- Just as TLB consistency is a problem in multiprocessors, because multiple TLBs cache data from a shared page table, cache coherence is a problem, because multiple caches cache data from shared memory. Small multiprocessors are now usually built with cache controllers that "snoop" on the bus for traffic regarding variables currently cached in the local cache. For example, a write to line X, seen on the bus, usually causes all other processors to evict X from their caches. Similarly, a read to line X causes any processor that has a writable copy of X in its cache to demote that copy to read-only. (This notion of writability is separate from the access rights in the TLB/page table.) A subsequent write by the processor with the demoted line will be a miss that has to go back out on the bus again. Primary caches don't snoop; secondary caches do. If you make the primary cache write-through, you can guarantee that everything in the primary cache is also in the secondary cache (this is called "multi-level inclusion"), and then it suffices for the secondary cache to snoop (and kick things out of the primary cache when necessary). Standard MESI (modified - exclusive - shared - invalid) state diagram: read miss _ ,----------------------,/ \ read hit | V | invalid <--bus write-once-- shared | ^ < > ^ | | | \ / | | | | bus \ / bus | | | | write \ / read | | write | | miss \ / miss | | write miss | | / \ | | hit | | / \ | | | | / \ | | v | / \ | v exclusive <--write hit--- modified | ^ \__/ write hit see Archibald and Baer, TOCS, Nov. '86 for more detail The distinction between modified and exclusive is a little subtle. When a cache line is "shared" and you have a write hit, you write *through* to memory. That means memory is up-to-date. Everybody else sees the write and invalidates their copy, if any. On subsequent write hits, you move to the 'exclusive' state and do NOT write through. When you eventually evict the line, you have to write it back. ================================= Linking Compilers seldom produce exactly the bits that will be in the code segment in memory when your program runs. Two tasks generally remain to be done (1) Most programs are made of separately-compiled modules. Something needs to stitch these together to make a whole program. This is called LINKING; it's done by a LINKER. The '.o' files that the compiler produces from your source files are called 'object' files because they contain 'object' code (as opposed to source code). They define certain *symbols* that represent interesting things in your program--mainly data structures and subroutines--and contain *unresolved references* to symbols in other object files. The linker takes a collection of object files and resolves mutual references. It usually knows about certain "standard" libraries that contain many of the symbols. (2) Because your program is made from separately-compiled pieces, the compiler doesn't know when it creates a given .o file where in your address space that file will lie. This means it doesn't know the absolute addresses at which variables and subroutines will lie. Some references can be made in terms of relative offsets from the program counter, but others have to be deferred until we know what the absolute address of the beginning of the object file will be. Once we know this address, we can RELOCATE the code. This job is usually also done by the linker. Object files contain information indicating that certain words need to have the offset of the beginning of the file (or some constant derived from that offset, e.g. the top few bits, or the bottom few) added to them. A warning: the term "loading" is sometimes used for relocation. It is better used for the task of putting a program (or at least part of it) into physical memory so it can run. The kernel does loading in response to an exec system call (or its equivalent in non-Unix systems). Once upon a time, when hardware didn't do address translation, programs had to be relocated when they were loaded; hence the confusion. It's especially unfortunate that Unix's linker is called "ld", which suggests "loader". Sometimes a linker is called a "link editor" or "link-loader". -------- Shared libraries Interesting/important application of fancy link/loading. Advantages save disk space -- don't have copies of libraries in every executable on the disk save space in main memory -- don't have copies of libraries in every running process in memory allow upgrades of libraries without re-compilation -- when you replace the shared copy of the library you automatically upgrade every application that is set up to use it. Shared libraries are compiled into position-independent code. (This is a special compiler option.) It means two things: (1) all internal code references (jumps, calls) are pc-relative, and all internal data references are relative to a base register, so you don't care what address you're linked at. (2) all external references are made through indirection tables. The tables are private to each process, so each process can resolve its cross-module references differently. The tables can be placed with the process-specific internal data, so both can be accessed relative to a single register, typically the gp (globals pointer). Every time you call into a different library, the code of the library has to save and update the gp. This isn't too hard if you put the data segment at a known offset from the code in virtual space. The library is linked into the application at *load time*, as part of the process start-up procedure initiated by the operating system in response to an exec system call. Data and code segments are separate. Code is shared, but every process has its own copy of the data (at least logically; see optimizations below). The designer of the shared library has to be careful to make sure that the code is *clean* - no data in it. This isn't necessarily as easy as it sounds: you have to worry about things like immediate addressing modes and case statement jump tables. [In some sense, the name "shared" library is misleading, since really every process has a logically private copy of the library. The sharing is just an optimization.] References from a shared library back into the main program are not allowed (at least not in Unix, OS/2, etc. -- this is a research topic). External references to things in shared libraries *from* shared libraries go through the indirection tables. These are treated as part of the process-private data portion of the library. Because of the indirection, you can put your shared libraries at whatever addresses you want. They can call each other even if other processes choose to put them in different places. [There exist simpler shared library systems that allocate addresses globally, but those aren't nearly as nice because of the lack of flexibility and the need for sysadmin intervention.] Optimizations: - Linking at load time is expensive. To minimize the start-up latency, procedural references in the indirection tables are set to point not to the actual procedure (which would mean we'd have to do all the linking for external references out of the library in which the procedure is located), but rather into the linker itself. If and when you actually call the procedure at run time, you end up calling into the linker, which patches things up for you. If you never make the call, you avoid the overhead. Even if you're certain to make the call, you get to spread the work out over time so the visible latency is never dreadfully high. - Private copies of the data of a "shared" library can actually share physical page frames if they aren't modified, using copy-on-write. Every time a process that uses the library starts executing, we map the (pristine version of) the data *read-only*. If and when a given process tries to make a *change* to the data, it takes a page fault. We then create a separate physical copy, and map it R/W. If processes don't make changes, or only change a subset of the data pages, then we never make the copies. - When a program is compiled and linked, it needs to know what the interface to the library is. We want to make sure it actually gets a version of the library that implements that interface. That means we want the version that existed at link time, or a backwards-compatible upgrade. Unix does this via version numbers. Conventions on the numbering allow the system to tell whether the installed library is compatible with the one the program thought it had when it was compiled.