CS 111 Lecture 16: Virtual Memory

Prepared by Andrew Yoon for a lecture given by Professor Paul Eggert on 11/20/13

Table of Contents

• Overview
• Problem
• Solutions
  • Segmented Memory
  • Virtual Memory
• More about VM
  • Example Implementation
  • Page Faulting
  • Swap space
  • Allocating memory

Overview: What's the advantage of VM?

Performance of VM not quite as good as RAM, and we must rely on locality of reference: if a program refers to location x, its next reference is probably x, x-1, or x+1.

Say we have 128 KiB of RAM and 16 MiB of VM.

Example of a program's memory references
16 MiB VM -----------------------------------------------
 |           |  x  |            |     |
 |           |   x |            |     |
 |           |     |            |   x |
Time         |     |            | x   |
 |           | x   |            |     |
 V           |     |            | x   |

We can store just the used portions of VM in our 128 KiB of RAM.

A problem with this is thrashing, where the 'actual' picture looks like this:

16 MiB VM -----------------------------------------------
 |           |  x  |            |     |
 |           |     |   x        |     |
 |        x  |     |            |   x |
Time         |     |            |     |    x
 |           | x   |            |  x  |
 V           |     |         x  |     |

And we don't have enough room in our RAM to store all the references. In this case I/O operations dominate paging. This is too slow! To the user it may appear that the program doesn't work at all!

As we can see, VM doesn't provide too much of a performance boost.

So why use VM at all? In practice, it is used to solve the following problem.

Problem

Lots of unreliable processes with bad memory references. Examples:

• a[i]

  , i out of range

• *p

  , p points to

  NULL

  , is freed, or is uninitialized

• p = (char *) i

  , i is a random int or pointer

• char a[n]

  , if n is very large we will run out of memory, or if n is negative we will corrupt the stack

Solutions

0. Don't do that! Fire programmer who writes buggy code
1. Every memory process is a syscall
2. The compiler inserts code around every access, checking if pointer is valid.
   1. How does the compiler know range?
      • We can use a better language, like Java, which stores every array's size.

   2. gcc -fsanitize=address

      • The compiler inserts, around every access, a check to see if it is valid. It accomplishes this using shadow memory.
      • Each byte in shadow memory describes one 8-byte block in real memory. To find a pointer p, we use

        (p >> 3) + shadow_mem_start

        and the shadow memory will tell us if it is valid.
3. Per-process base-bounds pair.
   • We add 2 columns to the process table, called base and bounds, and assign them values L and U, respectively.
   • Every memory access a must be bounded by L and U. L <= a <= U
   • Enforced by hardware, using privileged registers rL and rU.

               Example
               RAM---------------------------------------------------------
               |  p4  |  p1  |(unused)|  p2  |  p3  |(reserved for kernel)|
               ------------------------------------------------------------
                      L1     U1
               L0     U0
   

   • Assume we have position-independent code.

     gcc -fPIC

   • Some downsides to this approach:
     • Running processes can't be relocated (unless all references are relative to L)
     • External fragmentation
     • Whole program must fit in RAM at once
     • Must predict size at start
     • Buffer overruns can be a problem
4. Segmented Memory
   • Say we have a 32-bit pointer. The first 8 bits describe its purpose (code, stack, big I/O buffer, etc.) and the last 24 bits describe its offset in the corresponding segment.
   • Associated with each process is a segment table.

               Example Segment Table
                 | Loc | Size |
               0 |     |      |
                 |     |      |
     Segment #       .
                     .
                     .
             255 |     |      |
   

   (The location column refers to physical memory addresses.)
   • Now our memory map could look like this:

               RAM---------------------------------------------------------
               | p3,s3 | p3,s0 | p3,s1 | etc | p3,s2 |(reserved for kernel)|
               ------------------------------------------------------------
               

5. Virtual Memory
   • Use the same table as above, but no size column. Instead, we choose one segment--or "page"--size. For example, x86 uses 4096 bytes.
   • 32-bit virtual addresses. The first 20 bits describe the virtual page number, and the last 12 bits describe the offset in the page.

               Example 1-level page table (per process)
                 -----32 bits wide----
               0 | 20 bits | 12 bits |
                     .
                     .
                     .
        2^20 - 1 |         |         |
               2^22 bytes/page table = 4 MiB/process
   

   • The page table describes the physical addresses of the pages, which are aligned on page boundaries. Because of this alignment, the bottom 12 bits of the memory addresses will be all 0's. So in the page table, we can use these bits to describe extra information about the pages.
   • The privileged register

     %cr3

     points to the page table. You cannot see your own page table, so it is secure.
   • VM eliminates external fragmentation because of the alignment, but also introduces internal fragmentation (up to 4095 bytes per page)

More about VM

We can have multiple level page tables, such as the doubly indirect block we used in Lab 3. For example, if we are using a 2-level page table, our virtual address could look like this:

            | 10 bits | 10 bits | 12 bits |
               "hi"      "med"     "lo"

hi points to level 1 of the table, med points to level 2.

Example implementation:

/*
 * pmap(va)
 * gives physical memory at virtual address va
 */
unsigned pmap(unsigned va) {
    unsigned hi = va >> 22;
    unsigned med = (va >> 12) & ((1 << 10) - 1);
    unsigned* l1pt = asm("%cr3" .....);
    unsigned* l2pt = l1pt[hi] &~ ((1 << 12) - 1);
    if (l2pt == FAULT)
        return FAULT;
    return l2pt[med] &~ ((1 << 12) - 1);
}

Page Faulting

The hardware traps when given a "bad" address. (There's no physical memory in the page table). The kernel takes over, and it can:

• Terminate process (dump core) OR
• Raise SEGV signal OR
• Create page table entry with real memory, then RETI to return control. The instruction that failed will now work. This is the most common approach. (How does it work?)

            unsigned long long (unsigned va) {
                return swapbase(va >> 12);
            }

Swap space

Say we have a page table, which points to a bunch of processes in physical memory.

            Swap space----------------------------------------------------
            |    | 1 |        | 3 | 2 |      | 5 |   | 4 | |(virtual mem)|
            --------------------------------------------------------------

Physical memory is a cache of swap space.

Allocating memory

malloc(large_array)

• Allocates page table entries - some can work, some can be 0.
• On a system with over-allocated memory, malloc needs to allocate more memory than is in the swap space, so we have to use the 2nd level of the page table. If this memory is already in use, the kernel kills the program.