Address spaces using segments

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.

Address spaces

Example hardware for address spaces: x86 segments

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):

Case study (xv6)

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.

Overview of address spaces in xv6

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 x86 designers probably had in mind more interesting uses of segments. What might they have been?

xv6 process structure

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.

xv6 kernel address space

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.

creating the first process's address space

running the first process

Managing physical memory

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?

Growing an address space

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).