6.824 2002 Lecture 8: Address Spaces, VM hardware and software Address Spaces One of the main ingredients in our notion of a program Often the end-point of communication, e.g. RPC Important boundary: programming language inside, communication outside How to implement a basic address space? How to make the boundary more flexible? Why isolate? [picture 1: physical address space, kernel and processes packed together.] My buggy TCP proxy might scribble on your emacs. I might read your private emacs buffers. want to force clean interfaces programmers would take advantage of unrestricted sharing... yuck. Why address spaces? Starts at 0, contiguous. Easier for compiler to generate code if addrs are predictable. Easier to make large data structures of contiguous memory. Matrices, stack. Can't name other programs' memory -- so private. "Virtual address" is an address relative to an address space. "Physical address" is an address in machine's RAM. Only the hardware and the O/S are allowed to use PAs. [picture 2: multiple virtual address spaces] Alternate plan: Java. The language enforces isolation between classes. Cannot refer to a different class's private data. So it's easy to achieve isolation among modules. But a Java VM provides a single address space. I *can* refer to a different class's public data. Think about why this might be good or bad. Why not use base and bound to implement address spaces? CPU has two registers, base and bound. CPU adds base to each program VA to produce PA. Doesn't allow access beyond bound. O/S changes base and bound before switching into a process. This is a perfectly good implementation of an address space. And many older machines (and x86...) do it this way. Why isn't it good enough? What do modern machines provide for virtual memory? Split AS into fixed-size pages (e.g. 4096 bytes). So can view VA as page # and offset. [picture: VA] O/S sets up a "page table" telling CPU where to find each page. CPU indexes page table array with VP#. Gets a PPN out. Adds offset. [picture: VA indexes table, then add offset] Can implement any mapping, including our isolated contiguous spaces. CPU needs a Page Table Register (PTR). O/S makes it point to the current process's PTE array. Only O/S can write PTR and PTEs. Also need a Page Table Length register (PTL). For speed, TLB (translation lookaside buffer) caches translations. [picture: CPU, VMM w/ PTR, phys mem w/ PTE arrays and pages] How can we enforce isolation with this hardware? O/S and CPU have to be careful: O/S: don't map the PTEs into process' address space. CPU: don't let programs modify the PTR or PTL. What's in a PTE? Typically fields are hardware-defined. Typically fits in 32 bits. About 20 bits of physical page number. Valid bit. Readable. Writeable. Referenced. Dirty. What if program makes an invalid reference? Off the end of the PTE table, not valid, not read or write. Trap to the O/S, a bit like an interrupt or system call. O/S can terminate the process. Segmentation fault (core dumped) Turns out there are lots of neat things you can do in the trap handler. For example, let's implement address space larger than phys mem. So the "real" home of each page is on disk. We'll use phys mem as a cache. Assume we have a single disk dedicated to paging this one program. Or we're paging the program to a big file on disk. Here's what the trap handler could do. 1. Find a phys page to re-use, call it P. Note it's probably refered to by some PTE entry. Better be one that the program isn't likely to access soon... 2. If P's PTE says P is dirty, write P to its home on the disk. 3. Mark P's PTE "invalid." 4. Find disk addr of faulting VA. Should be easy, just directly address disk with VA. 5. Read that page from disk to P. 6. Put P into the faulting VA's PTE. 7. Mark PTE as valid, read/write, not dirty. 8. Return from trap to user program. In general, VM hardware gives us a useful level of indirection. O/S can read real data from anywhere it likes in trap handler. O/S can make PTEs point to any page of real memory. How does the o/s view virtual memory? The O/S knows about "memory objects" E.g. file, paging area. The objects are the "real" memory. But note they may not be DRAM. The O/S keeps, per-process, VA -> object mappings. This is the "real" description of a process's address space. The O/S uses phys RAM as a cache of memory objects. E.g. to cache file contents. But only a cache: can always re-read from disk. The O/S uses PTE array as a cache of mappings. But only a cache: can always fault and re-build PTE. Example uses of VM hardware: big virtual address space (this is what we just implemented) hard part is actually page replacement choice especially when many big programs fighting over limited phys mem run one at a time to avoid paging? big physical address space Machine has 16 GB of RAM, but 32-bit addresses. How do you use the other 12 GB? Run lots of programs, use VM to map them to different 4GB segments. Requires 22-bit phys addr in PTE copy-on-write for faster fork() give child a copy of parent's PTE array mark all PTEs in both processes read-only on write fault, copy to new phys page, change PTE demand page for fast program start-up automatic stack extension automatic zero-fill memory map files into memory: fast, convenient makes file data look like ordinary memory, e.g. struct, array, &c saves memory: all my xterms map instructions from xterm program file share memory among processes just put same phys addr in PTEs in both processes accelerate local RPC, implement UNIX pipes just tell program about trap and let it do what it wants e.g. distributed shared memory efficient way to intercept accesses to remote memory