[wip] MIT 6.828 Operating System Lab 2

# Lab 2. [Memory Management](https://pdos.csail.mit.edu/6.828/2017/labs/lab2/)

エクササイズをやっていく。本文を必要なところだけ訳しながらやるつもり

Lab 2 は以下の新しいソースファイルを含んでいる。

- inc/memlayout.h
- kern/pmap.c
- kern/pmap.h
- kern/kclock.c
- kern/kclock.h

memlayout.h は、pmap.c で実装される、仮想アドレス空間のレイアウトを示す。
memlayout.h と pmap.h は、PageInfo 構造体を定義する。これは、どの物理メモリに対応するページがフリーであるかを管理するのに使う。
kclock.c と、kclock.h は、PC の バッテリバックアップされたクロックと、CMOS RAM ハードウェア を操作する。BIOS は PC がもつ物理メモリの大きさなどをそこに保管する。
pmap.c のコードは、このデバイスハードウェアを読み、物理メモリの大きさを知る必要がある。しかし、その部分はすでに実装済みなので、あなたはCMOSハードウェアがどう動くかの詳細を知る必要はない。

memlayout.h と pmap.h は、このラボであなたが使用し、理解する必要のある多くの定義を含んでいるので、特に注意を払おう。
inc/mmu.h もまた、このラボで有用な多くの定義を含んでおり、調べる必要があるかもしれない。

## Part 1: 物理ページの管理

オペレーティングシステムは、物理RAMのどの部分がフリーで、どこが使われているかを管理しなければならない。
JOS は、PC の物理メモリを、ページ単位で管理する。これは、MMU を使って、それぞれの割り当てられたメモリ単位を保護したり、マップするためである。

それでは、物理ページアロケータを書いてみよう。物理ページアロケータは、PageInfo 構造体 (xv6 と異なり、フリーページ自体には埋め込まれない) からなる連結リスト  をつかって、どのページがフリーであるかを管理する。各 PageInfo はひとつの物理ページに対応する。
あなたは、仮想メモリ実装の残りを書く前に、物理ページアロケータを書く必要がある。なぜなら、ページテーブルの管理をするコードは、ページテーブルを保管するための物理メモリを割り当てる必要があるからだ。


> **問題 1.** kern/pmap.c の中で、以下のコードを実装せよ。(おそらく以下の順で)
> 
> boot_alloc()
> mem_init() (check_page_free_list(1) の呼び出しまで)
> page_init()
> page_alloc()
> page_free()
> 
> check_page_free_list() と check_page_alloc() が、物理ページアロケータをテストする。JOS をブートし、check_page_alloc() が成功することを確かめよ。成功するようにコードを直せ。自分で assert() を足して、前提が正しいことを確かめるのも助けになるかもしれない。

このラボ、またすべての 6.828 のラボでは、実際に何をするべきなのかを突き止めるためのいくらかの調べものが必要になる。この課題は JOS に追加すべきすべてのコードの詳細を説明しない。JOS のソースの修正すべき部分のコメントを読もう。これらのコメントはしばしばスペックやヒントを含んでいる。JOS の関連する部分や、Intel マニュアル、あるいは 6.004, 6.033 の講義ノートを参照する必要もあるかもしれない。

以下解答：

```C
 // この単純な物理ページアロケータは、JOS が仮想メモリをセットアップしているときにのみ使われる。
 // page_alloc() が真のアロケータである。
 // n>0 ならば、'n' バイトを保持するのに必要な連続した物理メモリを割り当てる。
 // メモリの初期化はしない。カーネルの仮想アドレスを返す。
 //
 // n==0 ならば、アロケーションをせずに、次のフリーページのアドレスを返す。
 //
 // メモリ不足の場合は、boot_alloc は panic する。この関数は、page_free_list がセットアップ
 // される以前の初期化時のみ使われる。
 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.
 +	result = nextfree;
 +	nextfree += ROUNDUP(n, PGSIZE);
 +	if (nextfree < result) {
 +		panic("Memory limit exceeded.");
 +	}
  
 -	return NULL;
 +	return result;
  }
```

```C
 // Set up a two-level page table:
 //    kern_pgdir is its linear (virtual) address of the root
 //
 // This function only sets up the kernel part of the address space
 // (ie. addresses >= UTOP).  The user part of the address space
 // will be setup later.
 //
 // From UTOP to ULIM, the user is allowed to read but not write.
 // Above ULIM the user cannot read or write.
 void
 mem_init(void)
 {
 	uint32_t cr0;
 	size_t n;
 
  	// Find out how much memory the machine has (npages & npages_basemem).
  	i386_detect_memory();
  
 -	// Remove this line when you're ready to test this function.
 -	panic("mem_init: This function is not finished\n");
 -
  	//////////////////////////////////////////////////////////////////////
  	// create initial page directory.
  	kern_pgdir = (pde_t *) boot_alloc(PGSIZE);
 	memset(kern_pgdir, 0, PGSIZE);
 
 	//////////////////////////////////////////////////////////////////////
 	// Recursively insert PD in itself as a page table, to form
 	// a virtual page table at virtual address UVPT.
 	// (For now, you don't have understand the greater purpose of the
 	// following line.)
 
 	// Permissions: kernel R, user R
 	kern_pgdir[PDX(UVPT)] = PADDR(kern_pgdir) | PTE_U | PTE_P;
 
 	//////////////////////////////////////////////////////////////////////
 	// 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((uint32_t) npages * sizeof(struct PageInfo));
 +	memset(pages, 0, (uint32_t) npages * sizeof(struct PageInfo));
  
  	//////////////////////////////////////////////////////////////////////
  	// Now that we've allocated the initial kernel data structures, we set
 	// up the list of free physical pages. Once we've done so, all further
 	// memory management will go through the page_* functions. In
 	// particular, we can now map memory using boot_map_region
 	// or page_insert
 	page_init();
```

[JOSのメモリレイアウト](https://qiita.com/ogiekako/items/a4a0d139554f8dbdca9a) も参照のこと。