This lecture is about the first process in xv6.
The operating system can switch the x86 to protected mode, which supports 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. The chapters published on the schedule page may be helpful.
In today's lecture we see how xv6 creates the kernel address spaces, and the first user process. A process consists of an address space and one thread of control (to run the program) in xv6. 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.
The process chapter covers the material below in more detail.
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.
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).
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).