This lecture is about virtual memory, focusing on address spaces. It is the first lecture out of series of lectures that uses xv6 as a case study.
PC block diagram without virtual memory support:
The x86 starts out in real mode and translation is as follows:
The operating system can switch the x86 to protected mode, which supports 32-bit virtual and physical addresses, and allows the O/S to set up address spaces so that user processes can't change them. Translation in protected mode is as follows:
Next lecture covers paging; now we focus on segmentation.
Protected-mode segmentation works as follows (see handout):
xv6 is a reimplementation of Unix 6th edition.
Newer Unixs have inherited many of the conceptual ideas even though they added paging, networking, graphics, improve performance, etc.
You will need to read most of the source code multiple times. Your goal is to explain every line to yourself.
In today's lecture we see how xv6 creates the kernel address spaces, first user address spaces, and switches to it. To understand how this happens, we need to understand in detail the state on the stack too---this may be surprising, but a thread of control and address space are tightly bundled in xv6, in a concept called process. The kernel address space is the only address space with multiple threads of control. We will study context switching and process management in detail next weeks; creation of the first user process (init) will get you a first flavor.
xv6 uses only the segmentation hardware on the x86; it doesn't use paging. (In JOS you will use page-table hardware too, which we cover in next lecture.)
the code segment runs from 0 to 2^32 and is mapped X and R the data segment runs from 0 to 2^32 but is mapped W (read and write).
text original data and bss fixed-size stack expandable heapA process's code, data, and stack segments all map this virtual address space to the same range of linear addresses. That is, all three segments are the same.
The x86 designers probably had in mind more interesting uses of segments. What might they have been?
we're about to look at how the first XV6 process starts up it will run initcode.S, which does exec("/init") /init is a program that starts up a shell we can type to what's the important state of an xv6 process? kernel proc table has an entry for each process p->mem points to user mem phys address p->kstack points to kern stack phys address struct context holds saved kernel registers EIP, ESP, EAX, &c for when a system call is waiting for input user half: user memory user process sees memory as starting at zero instructions, data, stack, expandable heap kernel half: kernel executing a system call for a process on the process's kernel stack xv6 has two kinds of transitions trap + return: user->kernel, kernel->user system calls, interrupts, divide-by-zero, &c save user process state ... run in kernel ... restore state process switch: between kernel halves one process is waiting for input, run another or time-slicing between compute-bound processes save p1's kernel-half state ... restore p2's kernel-half state setting up first process involves manually initializing this state saved state for trap during trap, the CPU: switches to process's kernel stack pushes SS, ESP, EFLAGS, CS, EIP onto kernel stack jumps into kernel kernel then pushes the other user registers this is struct trapframe trap return reverses this, resuming at saved user EIP for first process: manually set up these "saved" registers on the kernel stack EIP 0, ESP top of user memory, &c saved state for process switch save registers (EIP, ESP, EAX, &c) in oldp->context restore registers from newp->context now we are at the EIP of newp, and using its kernel stack this is the only way xv6 switches among processes there is no direct user->user process switch instead, user TRAP kernel PROCESS-SWITCH kernel TRAP-RETURN user for first process: manually set up EIP and ESP to run forkret, which returns from trap
Since an xv6 process's address space is essentially a single segment, a process's physical memory must be contiguous. So xv6 may run into fragmentation if process sizes are a significant fraction of physical memory.
Let's see how xv6 creates the kernel address space by tracing xv6 from when it boots, focusing on address space management. You might want to turn of the second CPU for this sequence, by changing the line in .bochsrc that starts with cpu: count=2.
00007bec [00007bec] 7d7d // return address in bootmain 00007bf0 [00007bf0] 0080 // callee-saved ebx 00007bf4 [00007bf4] 7369 // callee-saved esi 00007bf8 [00007bf8] 0000 // callee-saved ebp 00007bfc [00007bfc] 7c4a // return address for bootmain: spin 00007c00 [00007c00] c031fcfa // first instruction at 7c00 (start)
0020cfbc [0020cfbc] 0000 0020cfc0 [0020cfc0] 0000 0020cfc4 [0020cfc4] 0000 0020cfc8 [0020cfc8] 0000 0020cfcc [0020cfcc] 0000 0020cfd0 [0020cfd0] 0000 0020cfd4 [0020cfd4] 0000 0020cfd8 [0020cfd8] 0000 0020cfdc [0020cfdc] 0023 0020cfe0 [0020cfe0] 0023 0020cfe4 [0020cfe4] 0000 0020cfe8 [0020cfe8] 0000 0020cfec [0020cfec] 0000 0020cff0 [0020cff0] 001b 0020cff4 [0020cff4] 0200 0020cff8 [0020cff8] 0ffc 0020cffc [0020cffc] 0023
To create an address space we must allocate physical memory, which will be freed when an address space is deleted (e.g., when a user program terminates). xv6 implements a first-fit memory allocator (see kalloc.c, sheet 22).
kalloc() maintains a list of ranges of free memory. The allocator finds the first range that is larger than the amount of requested memory. It splits that range in two: one range of the size requested and one of the remainder. It returns the first range. When memory is freed, kfree will merge ranges that are adjacent in memory.
Under what scenarios is a first-fit memory allocator undesirable?
How can a user process grow its address space? growproc.
We could do a lot better if segments didn't have to be contiguous in physical memory. How could we arrange that? Using page tables, which is our next topic. This is one place where page tables would be useful, but there are others too (e.g., in fork).