实验地址

Part 1: Physical Page Management

通过 lab 1 的分析可以得到下面的物理内存分布图,大致上可以分为 basemem, IO Hole, extened memory 三大类

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
+------------------+  <- 0xFFFFFFFF (4GB)          -
|      32-bit      |                               |
|  memory mapped   |                               |
|     devices      |                               |
|                  |                               |
/\/\/\/\/\/\/\/\/\/\                               |
                                                   |
/\/\/\/\/\/\/\/\/\/\                               |
|                  |                               |
|      Unused      |                               |
|                  |                               |
+------------------+  <- depends on amount of RAM  | extended
|                  |                               | memory
|                  |                               |
| Extended Memory  |                               |
|                  |                               |
|                  |                               |
+------------------+  <- 0x00100000 (1MB)          -
|     BIOS ROM     |                               |
+------------------+  <- 0x000F0000 (960KB)        |
|  16-bit devices, |                               | IO Hole
|  expansion ROMs  |                               |
+------------------+  <- 0x000C0000 (768KB)        |
|   VGA Display    |                               |
+------------------+  <- 0x000A0000 (640KB)        _
|                  |                               |
|    Low Memory    |                               |  basemem
|                  |                               |
+------------------+  <- 0x00000000                _

Exercise 2

In the file kern/pmap.c, you must implement code for the following functions (probably in the order given).

boot_alloc() mem_init() (only up to the call to check_page_free_list(1)) page_init() page_alloc() page_free()

check_page_free_list() and check_page_alloc() test your physical page allocator. You should boot JOS and see whether check_page_alloc() reports success. Fix your code so that it passes. You may find it helpful to add your own assert()s to verify that your assumptions are correct.

练习一主要写一个 physical page allocator

boot_alloc()

boot_alloc() 只有在 JOS 初始化虚拟内存的时候才会被调用,具体调用在 mem_init() 内。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void
mem_init(void)
{
  uint32_t cr0;
  size_t n;

  // Find out how much memory the machine has (npages & npages_basemem).
  i386_detect_memory();

  //////////////////////////////////////////////////////////////////////
  // create initial page directory.
  kern_pgdir = (pde_t *) boot_alloc(PGSIZE);
  memset(kern_pgdir, 0, PGSIZE);

  // ...
}

从中得知 boot_alloc() 主要对页目录(page directory)进行初始化

boot_alloc() 上方提供的注释知道要实现下面两个功能:

  1. n>0 时需要 allocates enough memory
  2. 如果内存不足(out of memory)需要抛出异常 panic()

第一点需要计算 第一个虚拟地址 ,根据 boot_alloc() 下方的注释知道 end 位于一个没被 kernel code 或者全局变量占用的虚拟地址的起始位置。

第二点判断内存不足,可通过 mem_init() 得知 i386_detect_memory() 用于发现机器上剩余的物理内存的

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
static void
i386_detect_memory(void)
{
  size_t basemem, extmem, ext16mem, totalmem;

  // Use CMOS calls to measure available base & extended memory.
  // (CMOS calls return results in kilobytes.)
  basemem = nvram_read(NVRAM_BASELO);
  extmem = nvram_read(NVRAM_EXTLO);
  ext16mem = nvram_read(NVRAM_EXT16LO) * 64;

  // Calculate the number of physical pages available in both base
  // and extended memory.
  if (ext16mem)
    totalmem = 16 * 1024 + ext16mem;
  else if (extmem)
    totalmem = 1 * 1024 + extmem;
  else
    totalmem = basemem;

  npages = totalmem / (PGSIZE / 1024);  // 物理内存的页数
  npages_basemem = basemem / (PGSIZE / 1024);  // basemem 的页数

  cprintf("Physical memory: %uK available, base = %uK, extended = %uK\n",
          totalmem, basemem, totalmem - basemem);
}

npages 是物理内存对应的页数,每页大小为 PGSIZE 所以一共分配的空间大小为 npages * PGSIZE , 而虚拟地址的的起始地址从 inc/memlayout.h 中得知为 KERNBASE(0xF0000000) ,所以最大能访问的虚拟地址为 KERNBASE + (npages * PGSIZE)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// This simple physical memory allocator is used only while JOS is setting
// up its virtual memory system.  page_alloc() is the real allocator.
//
// If n>0, allocates enough pages of contiguous physical memory to hold 'n'
// bytes.  Doesn't initialize the memory.  Returns a kernel virtual address.
//
// If n==0, returns the address of the next free page without allocating
// anything.
//
// If we're out of memory, boot_alloc should panic.
// This function may ONLY be used during initialization,
// before the page_free_list list has been set up.
static void *
boot_alloc(uint32_t n)
{
  static char *nextfree;	// virtual address of next byte of free memory
  char *result;

  // Initialize nextfree if this is the first time.
  // 'end' is a magic symbol automatically generated by the linker,
  // which points to the end of the kernel's bss segment:
  // the first virtual address that the linker did *not* assign
  // to any kernel code or global variables.
  if (!nextfree) {
    extern char end[];
    nextfree = ROUNDUP((char *) end, PGSIZE);
  }

  // Allocate a chunk large enough to hold 'n' bytes, then update
  // nextfree.  Make sure nextfree is kept aligned
  // to a multiple of PGSIZE.
  //
  // LAB 2: Your code here.

  if (0 == n) {
    return nextfree;
  }

  result = nextfree;
  nextfree = ROUNDUP((char *)(nextfree + n), PGSIZE);

  if ((uint32_t)nextfree > (KERNBASE + npages * PGSIZE)) {
    panic("boot_alloc: out of memory.\n");
  }

  return result;
}

mem_init()

mem_init() 中得知需要对 PageInfo 进行初始化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void
mem_init(void)
{
  //////////////////////////////////////////////////////////////////////
  // Allocate an array of npages 'struct PageInfo's and store it in 'pages'.
  // The kernel uses this array to keep track of physical pages: for
  // each physical page, there is a corresponding struct PageInfo in this
  // array.  'npages' is the number of physical pages in memory.  Use memset
  // to initialize all fields of each struct PageInfo to 0.
  // Your code goes here:
  pages = (struct PageInfo *)boot_alloc(npages * sizeof(struct PageInfo));
  memset(pages, 0, npages * sizeof(struct PageInfo));
}

page_init()

page_init() 主要判断哪些 page 是 free 的,从对应注释中可以了解到下面的内存结构:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
+------------------+  <- 0xFFFFFFFF (4GB)          -
|      32-bit      |                               |
|  memory mapped   |                               |
|     devices      |                               |
|                  |                               |
/\/\/\/\/\/\/\/\/\/\                               |
                                                   |
/\/\/\/\/\/\/\/\/\/\                               |
|                  |                               |
|      Unused      |                               |
|                  |                               |
+------------------+  <- depends on amount of RAM  | extended
|                  |                               | memory
|     Kernel       |                               |
|                  |                               |
+------------------+  <- 0x00100000 (1MB)          -
|     BIOS ROM     |                               |
+------------------+  <- 0x000F0000 (960KB)        |
|  16-bit devices, |                               | IO Hole
|  expansion ROMs  |                               |
+------------------+  <- 0x000C0000 (768KB)        |
|   VGA Display    |                               |
+------------------+  <- 0x000A0000 (640KB)        _
|                  |                               |  Low Memory
|                  |                               |
+------------------+  <- 0x00001000 (4KB)          |  basemem
|   Real-mode IDT  |                               |
+------------------+  <- 0x00000000                _

而且只有

  • 除了 real-mode IDT 剩下的 base memory
  • extened memory 未使用的

才能清空,因此主要把那两者加入 page_free_list

从注释能了解到 real-mode IDT 占据第 0 页,所以一开始只要从第 1 页开始就行,一直到 npages_basemem

而 extened memory 中由于有的部分已经被 kernel 占用,随后分配给 page_dir 最后是 npagesPageInfo 占用

但是 EXTPHYSMEM 只是 kernel 的起始位置,而终止位置可以根据 boot_alloc(0) 得到, boot_alloc() 分配的是内核最尾部,后面的应该都是可以使用的,由于 boot_alloc() 返回的是虚拟地址,需要用 PADDR() 转化为物理地址

page_init() 实际上用于初始化之前分配的 pages 数组,并构建 PageInfo 链表 page_free_list 用于保存空闲的页

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// --------------------------------------------------------------
// Tracking of physical pages.
// The 'pages' array has one 'struct PageInfo' entry per physical page.
// Pages are reference counted, and free pages are kept on a linked list.
// --------------------------------------------------------------

//
// Initialize page structure and memory free list.
// After this is done, NEVER use boot_alloc again.  ONLY use the page
// allocator functions below to allocate and deallocate physical
// memory via the page_free_list.
//
void
page_init(void)
{
  // The example code here marks all physical pages as free.
  // However this is not truly the case.  What memory is free?
  //  1) Mark physical page 0 as in use.
  //     This way we preserve the real-mode IDT and BIOS structures
  //     in case we ever need them.  (Currently we don't, but...)
  //  2) The rest of base memory, [PGSIZE, npages_basemem * PGSIZE)
  //     is free.
  //  3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM), which must
  //     never be allocated.
  //  4) Then extended memory [EXTPHYSMEM, ...).
  //     Some of it is in use, some is free. Where is the kernel
  //     in physical memory?  Which pages are already in use for
  //     page tables and other data structures?
  //
  // Change the code to reflect this.
  // NB: DO NOT actually touch the physical memory corresponding to
  // free pages!

  size_t i;
  page_free_list = NULL;

  for (i = 1; i < npages_basemem; ++i) {
    pages[i].pp_ref = 0;
    pages[i].pp_link = page_free_list;
    page_free_list = &pages[i];
  }

  for (i = PADDR(boot_alloc(0)) / PGSIZE; i < npages; ++i) {
    pages[i].pp_ref = 0;
    pages[i].pp_link = page_free_list;
    page_free_list = &pages[i];
  }

}

page_alloc()

page_alloc() 主要用于返回 page_free_list 中的一个 PageInfo 结构,并根据 (alloc_flags & ALLOC_ZERO) 这个条件对返回的 PageInfo 结构进行初始化,同时 不增加 PageInfopp_ref 字段。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//
// Allocates a physical page.  If (alloc_flags & ALLOC_ZERO), fills the entire
// returned physical page with '\0' bytes.  Does NOT increment the reference
// count of the page - the caller must do these if necessary (either explicitly
// or via page_insert).
//
// Be sure to set the pp_link field of the allocated page to NULL so
// page_free can check for double-free bugs.
//
// Returns NULL if out of free memory.
//
// Hint: use page2kva and memset
struct PageInfo *
page_alloc(int alloc_flags)
{
  if (!page_free_list) {
    return NULL;
  }

  struct PageInfo *ret = page_free_list;
  page_free_list = ret->pp_link;
  ret->pp_link = NULL;
  if (alloc_flags & ALLOC_ZERO) {
    memset(page2kva(ret), '\0', PGSIZE);
  }
  return ret;
}

page_free()

page_free() 主要将 pp 对应的物理页设置为空闲状态

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
//
// Return a page to the free list.
// (This function should only be called when pp->pp_ref reaches 0.)
//
void
page_free(struct PageInfo *pp)
{
  // Fill this function in
  // Hint: You may want to panic if pp->pp_ref is nonzero or
  // pp->pp_link is not NULL.
  if (pp->pp_ref || pp->pp_link) {
    panic("page_free: pp_ref is nonzero or pp_link is not NULL\n");
  }
  pp->pp_link = page_free_list;
  page_free_list = pp;
}

Part 2: Virtual Memory

virtual address
程序使用的地址
linear address
virtual address 经过 segment translation 得到
physical address
linear address 经过 paging 得到

简单的转化过程

1
2
3
4
5
6
7
8
           Selector  +--------------+         +-----------+
          ---------->|              |         |           |
                     | Segmentation |         |  Paging   |
Software             |              |-------->|           |---------->  RAM
            Offset   |  Mechanism   |         | Mechanism |
          ---------->|              |         |           |
                     +--------------+         +-----------+
            Virtual                   Linear                Physical

具体过程如下图,图中 logical address 即为 virtual address,详细过程见 Intel 80386 Reference Manual

Figure 1: x86 translation andregisters

Figure 1: x86 translation andregisters

Q1

Assuming that the following JOS kernel code is correct, what type should variable x have, uintptr_t or physaddr_t?

1
2
3
4
mystery_t x;
char* value = return_a_pointer();
*value = 10;
x = (mystery_t) value;

xuintptr_t

Exercise 4

In the file kern/pmap.c, you must implement code for the following functions.

pgdir_walk() boot_map_region() page_lookup() page_remove() page_insert()

check_page(), called from mem_init(), tests your page table management routines. You should make sure it reports success before proceeding.

pgdir_walk()

pgdir_walk() 中注释知道关联的 page table 可能不存在,所以需要判断它是否存在,而根据 5.2.4.2 Present Bit 中提到的

The Present bit indicates whether a page table entry can be used in address translation. P=1 indicates that the entry can be used. When P=0 in either level of page tables, the entry is not valid for address translation, and the rest of the entry is available for software use; none of the other bits in the entry is tested by the hardware. Figure 5-11 illustrates the format of a page-table entry when P=0.

Figure 2: page table entry

Figure 2: page table entry

知道可以用 *pte & PTE_P 这个条件判断

第二是 MMU 会检查 权限位 所以需要对其进行设置,6.4 Page-Level Protection 有权限位介绍

第三是需要返回一个指针指向虚拟地址 va 对应的 PTE

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// Given 'pgdir', a pointer to a page directory, pgdir_walk returns
// a pointer to the page table entry (PTE) for linear address 'va'.
// This requires walking the two-level page table structure.
//
// The relevant page table page might not exist yet.
// If this is true, and create == false, then pgdir_walk returns NULL.
// Otherwise, pgdir_walk allocates a new page table page with page_alloc.
//    - If the allocation fails, pgdir_walk returns NULL.
//    - Otherwise, the new page's reference count is incremented,
//	the page is cleared,
//	and pgdir_walk returns a pointer into the new page table page.
//
// Hint 1: you can turn a PageInfo * into the physical address of the
// page it refers to with page2pa() from kern/pmap.h.
//
// Hint 2: the x86 MMU checks permission bits in both the page directory
// and the page table, so it's safe to leave permissions in the page
// directory more permissive than strictly necessary.
//
// Hint 3: look at inc/mmu.h for useful macros that manipulate page
// table and page directory entries.
//
pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
  pde_t *pte = &pgdir[PDX(va)];
  struct PageInfo *pageInfo;
  // 通过 present bit 判断 page 是否存在
  if (!(*pte & PTE_P)) {
    if (!create) {
      return NULL;
    }
    pageInfo = page_alloc(1);
    if (!pageInfo) {
      return NULL;
    }
    pageInfo->pp_ref++;
    // Hint 2: 权限设置
    // https://pdos.csail.mit.edu/6.828/2018/readings/i386/s06_04.htm
    // https://pdos.csail.mit.edu/6.828/2018/readings/i386/s06_05.htm
    *pte = (pte_t)page2pa(pageInfo) | PTE_U | PTE_W | PTE_P;
  }

  return (pte_t *)KADDR(PTE_ADDR(*pte)) + PTX(va);
}

boot_map_region()

boot_map_region() 主要将 [va, va+size) 对应的虚拟地址空间映射到物理地址空间 [pa, pa+size)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//
// Map [va, va+size) of virtual address space to physical [pa, pa+size)
// in the page table rooted at pgdir.  Size is a multiple of PGSIZE, and
// va and pa are both page-aligned.
// Use permission bits perm|PTE_P for the entries.
//
// This function is only intended to set up the ``static'' mappings
// above UTOP. As such, it should *not* change the pp_ref field on the
// mapped pages.
//
// Hint: the TA solution uses pgdir_walk
static void
boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
{
  size_t pgs = size / PGSIZE;
  if (size % PGSIZE) {
    pgs++;
  }

  for (int i = 0; i < pgs; ++i) {
    uintptr_t cur_va = va + i * PGSIZE;  // 当前 page 的 va
    pte_t *pte = pgdir_walk((pde_t *)pgdir, (void *)cur_va, 1);  // 获取当前 va 的 PTE 地址
    if (!pte) {
      panic("boot_map_region: out of memory.\n");
    }
    physaddr_t cur_pa = pa + i * PGSIZE;  // 当前 page 的 pa
    *pte = cur_pa | perm | PTE_P;  // 修改 va 对应的 PTE 值
  }
}

page_lookup()

page_lookup() 主要将 va 返回对应的 page 信息

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//
// Return the page mapped at virtual address 'va'.
// If pte_store is not zero, then we store in it the address
// of the pte for this page.  This is used by page_remove and
// can be used to verify page permissions for syscall arguments,
// but should not be used by most callers.
//
// Return NULL if there is no page mapped at va.
//
// Hint: the TA solution uses pgdir_walk and pa2page.
//
struct PageInfo *
page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
  pte_t *pte = pgdir_walk(pgdir, va, 0);
  // 对应 page 不存在
  if (!pte || !(*pte & PTE_P)) {
    return NULL;
  }

  if (pte_store) {
    *pte_store = pte;
  }

  // va 对应的 pa
  physaddr_t pa = PTE_ADDR(*pte);
  // pa 对应的 PageInfo
  return pa2page(pa);
}

page_remove()

page_remove() 用于删除 va 的映射关系

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//
// Unmaps the physical page at virtual address 'va'.
// If there is no physical page at that address, silently does nothing.
//
// Details:
//   - The ref count on the physical page should decrement.
//   - The physical page should be freed if the refcount reaches 0.
//   - The pg table entry corresponding to 'va' should be set to 0.
//     (if such a PTE exists)
//   - The TLB must be invalidated if you remove an entry from
//     the page table.
//
// Hint: The TA solution is implemented using page_lookup,
// 	tlb_invalidate, and page_decref.
//
void
page_remove(pde_t *pgdir, void *va)
{
  pte_t *pte;
  // va 对应的 PageInfo 和 PTE 地址
  struct PageInfo *pageInfo = page_lookup(pgdir, va, &pte);

  // 没映射
  if (!pageInfo)
    return ;

  // pp->pp_ref -= 1
  // if (!pp->pp_ref) {
  //    page_free(pp);
  // }
  page_decref(pageInfo);

  // 清空 PTE
  *pte = 0;

  // TLB 失效
  tlb_invalidate(pgdir, va);
}

page_insert()

page_insert() 主要修改 pgdir ,使 va 映射到 pp 对应的物理页

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//
// Map the physical page 'pp' at virtual address 'va'.
// The permissions (the low 12 bits) of the page table entry
// should be set to 'perm|PTE_P'.
//
// Requirements
//   - If there is already a page mapped at 'va', it should be page_remove()d.
//   - If necessary, on demand, a page table should be allocated and inserted
//     into 'pgdir'.
//   - pp->pp_ref should be incremented if the insertion succeeds.
//   - The TLB must be invalidated if a page was formerly present at 'va'.
//
// Corner-case hint: Make sure to consider what happens when the same
// pp is re-inserted at the same virtual address in the same pgdir.
// However, try not to distinguish this case in your code, as this
// frequently leads to subtle bugs; there's an elegant way to handle
// everything in one code path.
//
// RETURNS:
//   0 on success
//   -E_NO_MEM, if page table couldn't be allocated
//
// Hint: The TA solution is implemented using pgdir_walk, page_remove,
// and page2pa.
//
int
page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm)
{
  // va 对应的 PTE
  // va 对应 Page 没分配则新建
  pde_t *pte = pgdir_walk(pgdir, va, 1);

  // 无 PTE 则因内存不足而创建失败
  if (!pte) {
    return -E_NO_MEM;
  }

        pp->pp_ref++;

  // va 已被映射需要先移除
        if (*pte & PTE_P) {
    page_remove(pgdir, va);
  }

  // PageInfo 转换为其对应 pa
  physaddr_t pa = page2pa(pp);

  *pte = pa | perm | PTE_P;

        return 0;
}

Part 3: Kernel Address Space

JOS 将地址空间分为整体和用户两个部分,并用 ULIM 分界,其内存分布图如 inc/memlayout.h 中所示

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
Virtual memory map:                                Permissions
                                                   kernel/user

   4 Gig -------->  +------------------------------+
                    |                              | RW/--
                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                    :              .               :
                    :              .               :
                    :              .               :
                    |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| RW/--
                    |                              | RW/--
                    |   Remapped Physical Memory   | RW/--
                    |                              | RW/--
   KERNBASE, ---->  +------------------------------+ 0xf0000000      --+
   KSTACKTOP        |     CPU0's Kernel Stack      | RW/--  KSTKSIZE   |
                    | - - - - - - - - - - - - - - -|                   |
                    |      Invalid Memory (*)      | --/--  KSTKGAP    |
                    +------------------------------+                   |
                    |     CPU1's Kernel Stack      | RW/--  KSTKSIZE   |
                    | - - - - - - - - - - - - - - -|                 PTSIZE
                    |      Invalid Memory (*)      | --/--  KSTKGAP    |
                    +------------------------------+                   |
                    :              .               :                   |
                    :              .               :                   |
   MMIOLIM ------>  +------------------------------+ 0xefc00000      --+
                    |       Memory-mapped I/O      | RW/--  PTSIZE
ULIM, MMIOBASE -->  +------------------------------+ 0xef800000
                    |  Cur. Page Table (User R-)   | R-/R-  PTSIZE
   UVPT      ---->  +------------------------------+ 0xef400000
                    |          RO PAGES            | R-/R-  PTSIZE
   UPAGES    ---->  +------------------------------+ 0xef000000
                    |           RO ENVS            | R-/R-  PTSIZE
UTOP,UENVS ------>  +------------------------------+ 0xeec00000
UXSTACKTOP -/       |     User Exception Stack     | RW/RW  PGSIZE
                    +------------------------------+ 0xeebff000
                    |       Empty Memory (*)       | --/--  PGSIZE
   USTACKTOP  --->  +------------------------------+ 0xeebfe000
                    |      Normal User Stack       | RW/RW  PGSIZE
                    +------------------------------+ 0xeebfd000
                    |                              |
                    |                              |
                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                    .                              .
                    .                              .
                    .                              .
                    |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|
                    |     Program Data & Heap      |
   UTEXT -------->  +------------------------------+ 0x00800000
   PFTEMP ------->  |       Empty Memory (*)       |        PTSIZE
                    |                              |
   UTEMP -------->  +------------------------------+ 0x00400000      --+
                    |       Empty Memory (*)       |                   |
                    | - - - - - - - - - - - - - - -|                   |
                    |  User STAB Data (optional)   |                 PTSIZE
   USTABDATA ---->  +------------------------------+ 0x00200000        |
                    |       Empty Memory (*)       |                   |
   0 ------------>  +------------------------------+                 --+

(*) Note: The kernel ensures that "Invalid Memory" is *never* mapped.
    "Empty Memory" is normally unmapped, but user programs may map pages
    there if desired.  JOS user programs map pages temporarily at UTEMP.

Exercise 5

Fill in the missing code in mem_init() after the call to check_page().

Your code should now pass the check_kern_pgdir() and check_page_installed_pgdir() checks.

根据 mem_init() 中缺失代码部分前面的注释进行补充:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void
mem_init(void)
{
  // ...
  //////////////////////////////////////////////////////////////////////
  // Map 'pages' read-only by the user at linear address UPAGES
  // Permissions:
  //    - the new image at UPAGES -- kernel R, user R
  //      (ie. perm = PTE_U | PTE_P)
  //    - pages itself -- kernel RW, user NONE
  // Your code goes here:
  boot_map_region(kern_pgdir, UPAGES, npages * sizeof(struct PageInfo), PADDR(pages), PTE_U|PTE_P);

  //////////////////////////////////////////////////////////////////////
  // Use the physical memory that 'bootstack' refers to as the kernel
  // stack.  The kernel stack grows down from virtual address KSTACKTOP.
  // We consider the entire range from [KSTACKTOP-PTSIZE, KSTACKTOP)
  // to be the kernel stack, but break this into two pieces:
  //     * [KSTACKTOP-KSTKSIZE, KSTACKTOP) -- backed by physical memory
  //     * [KSTACKTOP-PTSIZE, KSTACKTOP-KSTKSIZE) -- not backed; so if
  //       the kernel overflows its stack, it will fault rather than
  //       overwrite memory.  Known as a "guard page".
  //     Permissions: kernel RW, user NONE
  // Your code goes here:
  boot_map_region(kern_pgdir, KSTACKTOP-KSTKSIZE, KSTKSIZE, PADDR(bootstack), PTE_W);

  //////////////////////////////////////////////////////////////////////
  // Map all of physical memory at KERNBASE.
  // Ie.  the VA range [KERNBASE, 2^32) should map to
  //      the PA range [0, 2^32 - KERNBASE)
  // We might not have 2^32 - KERNBASE bytes of physical memory, but
  // we just set up the mapping anyway.
  // Permissions: kernel RW, user NONE
  // Your code goes here:
  boot_map_region(kern_pgdir, KERNBASE, 0xffffffff - KERNBASE, 0, PTE_W);

  // ...
}

Q2

What entries (rows) in the page directory have been filled in at this point? What addresses do they map and where do they point? In other words, fill out this table as much as possible:

参考 layout 图得到

Entry Points to (logically): Base Virtual Address
1023 Page table for phys memory: [252mb, 256mb) 0xffc00000
1022 Page table for phys memory: [248mb, 252mb) 0xff800000
. ? ?
960 Page table for phy memory: [0, 4mb) 0xf0000000(KSTACKTOP, KERNBASE)
959 Kernel stack 0xefc00000
958 Memory-mapped I/O 0xef800000
957 Page directory page itself 0xef400000
956 RO PAGES 0xef000000(UPAGES)
. ? ?
2 Program Data & Heap 0x00800000
1 Empty Memory 0x00400000
0 Empty Memory 0x00000000

Q3

We have placed the kernel and user environment in the same address space. Why will user programs not be able to read or write the kernel’s memory? What specific mechanisms protect the kernel memory?

通过 6.4 Page-Level Protection 权限位即 PTE_WPTE_U 两个 bit 起作用

Q4

What is the maximum amount of physical memory that this operating system can support? Why?

2G

PTSIZEUPAGES 为 4M

sizeof(struct PageInfo)) = 8b ,所以最大页数为 4096 * 1024 / 8 = 512 * 1024

每页大小为 4KB, 所以最多有 512 * 1024 * 4096 = 2GB 物理内存

Q5

How much space overhead is there for managing memory, if we actually had the maximum amount of physical memory? How is this overhead broken down?

4MB PageInfo :

2MB 给页表
每个页表大小为 4096 bytes, 可引导 1024 * 4096 = 4MB 内存;需要 2GB / 4MB = 512 张页表,所以 512 * 4096 = 2MB
4KB 给页目录
每个页目录大小为 4096 bytes,一张页目录可引导 1024 个页表

Q6

Revisit the page table setup in kern/entry.S and kern/entrypgdir.c. Immediately after we turn on paging, EIP is still a low number (a little over 1MB). At what point do we transition to running at an EIP above KERNBASE? What makes it possible for us to continue executing at a low EIP between when we enable paging and when we begin running at an EIP above KERNBASE? Why is this transition necessary?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
.globl entry
entry:
  movw	$0x1234,0x472			# warm boot

  # We haven't set up virtual memory yet, so we're running from
  # the physical address the boot loader loaded the kernel at: 1MB
  # (plus a few bytes).  However, the C code is linked to run at
  # KERNBASE+1MB.  Hence, we set up a trivial page directory that
  # translates virtual addresses [KERNBASE, KERNBASE+4MB) to
  # physical addresses [0, 4MB).  This 4MB region will be
  # sufficient until we set up our real page table in mem_init
  # in lab 2.

  # Load the physical address of entry_pgdir into cr3.  entry_pgdir
  # is defined in entrypgdir.c.
  movl	$(RELOC(entry_pgdir)), %eax
  movl	%eax, %cr3
  # Turn on paging.
  movl	%cr0, %eax
  orl	$(CR0_PE|CR0_PG|CR0_WP), %eax
  movl	%eax, %cr0

  # Now paging is enabled, but we're still running at a low EIP
  # (why is this okay?).  Jump up above KERNBASE before entering
  # C code.
  mov	$relocated, %eax
  jmp	*%eax

从 kern/entry.S 中得知在 jmp *%eax 之后 EIP 才在 KERNBASE 运行

由于 VA[0, 4MB)被映射到 PA[0, 4MB)上所以开了 paging 还要在低位地址上执行

转换能让内核把低位地址映射到用户层上,以便用户层使用低位地址的空间