cgroupsとメモリ資源と関係を勉強する前に、Linuxの仮想記憶周りを読む...

## あらまし
[前回](http://qiita.com/akachochin/items/1efb887aa10c45298415)、cgroupsについて軽くではあるが書いてみました。

上記の文章の最後に「次はcgroupsとメモリ管理というネタで行ってみたい」と書きました。
もちろんすぐにcgroupsと仮想記憶の関係がわかればよいのであるが、何ぶんLinuxの仮想記憶は読むのも初めてです。よって、Linuxの仮想記憶の概要をつかむためにまずはソースを読んでみます。

流れがわかりにくい箇所もあります。が、ソースを読んで迷った過程をあえて記録に残したいと考えたからです。ご了解ください。

## ということでfork()
仮想記憶の機能を理解するには、経験則上、とっかかりが必要です。
そのとっかかりの一つがfork()だと思っています。
人によっては、page fault(例外ハンドラ)から入ったり、mmap()から入ったりすることもあろうが、前回fork()がらみのところを読んだので、今回もここから行きます。

```c:kernel/fork.c
#ifdef __ARCH_WANT_SYS_FORK
SYSCALL_DEFINE0(fork)
{
#ifdef CONFIG_MMU
	return do_fork(SIGCHLD, 0, 0, NULL, NULL);
#else
	/* can not support in nommu mode */
	return -EINVAL;
#endif
}
#endif
```
考えてみれば、このifdefは当たり前なのだが、すごいものがあります。
確かにMMUなしのCPUでは、fork()は成り立たないように思えるのだが、MMUなしのCPUではプロセスをどうやって生成しているのでしょうか？
そんな疑問をひとまず脇によけて先に進みます。

```c:kernel/fork.c
long do_fork(unsigned long clone_flags,
        unsigned long stack_start,
         unsigned long stack_size,
         int __user *parent_tidptr,
         int __user *child_tidptr)
{
  /* 略 */
  p = copy_process(clone_flags, stack_start, stack_size,child_tidptr, NULL, trace);
```
おそらくはcopy_process()で、親のプロセス構造体を元手に子のプロセス構造体を作るのだろう。
当然、その中には仮想アドレス空間に関することも含まれるのであろうと想定して、先に進みます。

```c:kernel/fork.c
static struct task_struct *copy_process(unsigned long clone_flags,
          unsigned long stack_start,
          unsigned long stack_size,
          int __user *child_tidptr,
          struct pid *pid,
          int trace)
{
/* とても長い。略。引数チェックのあと、いろいろなものをコピーしている */
  retval = copy_mm(clone_flags, p);
  if (retval)
    goto bad_fork_cleanup_signal;
```
目当ての仮想記憶に関連しそうなところがありました。

```c:kernel/fork.c
static int copy_mm(unsigned long clone_flags, struct task_struct *tsk)
{
  /* 略 */
  /*
   * Are we cloning a kernel thread?
   *
   * We need to steal a active VM for that..
   */
  oldmm = current->mm;
  if (!oldmm)
    return 0;

  /* 略 */ 
  retval = -ENOMEM;
  mm = dup_mm(tsk);
  if (!mm)
    goto fail_nomem;
```

いかにも仮想アドレス空間の複製をしそうな名前のdup_mm()。見てみましょう。

```c:kernel/fork.c
/*
 * Allocate a new mm structure and copy contents from the
 * mm structure of the passed in task structure.
 */
 static struct mm_struct *dup_mm(struct task_struct *tsk)
{
  struct mm_struct *mm, *oldmm = current->mm;
  int err;

  mm = allocate_mm();
  if (!mm)
    goto fail_nomem;

  memcpy(mm, oldmm, sizeof(*mm));
  mm_init_cpumask(mm);
  dup_mm_exe_file(oldmm, mm);

  err = dup_mmap(mm, oldmm);
  if (err)
    goto free_pt;
```

まず、oldmmを取得します。currentはおそらく現在実行中のプロセス(つまり、fork()を実行している親プロセス)だと思われます。
新たにmm_struct構造体を割り当てて、親のmm_structをコピーしています。

そして、アドレス空間に関していえば、dup_mmap()がもう少し複雑なことをする複写処理だと推定できます。(似たような名前の関数が続きますが・・・)

## ところで、mm_structとは？

```c:include/linux/mm_types.h
345 struct mm_struct {
346   struct vm_area_struct *mmap;    /* list of VMAs */
/* 以下たくさんのメンバがあるが、略 */
```

要は、プロセスのアドレス空間を表現するための構造体です。

そして、アドレス空間と一口に言っても、その中には属性の違う領域がいくつかあるのはイメージがつくかと思います。

例えば、命令(.text)がロードされるメモリ領域であれば読み+実行属性となるでしょうし、データ(.data)であれば読み+書き属性となるでしょう。
その他にも様々な属性があります。
そんな「プロセスアドレス空間内の様々な領域」を表現したものがvm_area_struct構造体になると思われます。

```c:include/linux/mm_types.h
*
* This struct defines a memory VMM memory area. There is one of these
* per VM-area/task.  A VM area is any part of the process virtual memory
* space that has a special rule for the page-fault handlers (ie a shared
* library, the executable area etc).
*/
struct vm_area_struct {
 /* The first cache line has the info for VMA tree walking. */

 unsigned long vm_start;   /* Our start address within vm_mm. */
 unsigned long vm_end;   /* The first byte after our end address

 /* linked list of VM areas per task, sorted by address */
 struct vm_area_struct *vm_next, *vm_prev;
/* 略 */
 pgprot_t vm_page_prot;    /* Access permissions of this VMA. */
 unsigned long vm_flags;   /* Flags, see mm.h. */

  /*
   * For areas with an address space and backing store,
   * linkage into the address_space->i_mmap interval tree, or
   * linkage of vma in the address_space->i_mmap_nonlinear list.
   */
  union {
    struct { 
      struct rb_node rb;
      unsigned long rb_subtree_last;
    } linear;
    struct list_head nonlinear;
  } shared;

  /*
   * A file's MAP_PRIVATE vma can be in both i_mmap tree and anon_vma
   * list, after a COW of one of the file pages.  A MAP_SHARED vma
   * can only be in the i_mmap tree.  An anonymous MAP_PRIVATE, stack
   * or brk vma (with NULL file) can only be in an anon_vma list.
   */
  struct list_head anon_vma_chain; /* Serialized by mmap_sem &
            * page_table_lock */
  struct anon_vma *anon_vma;  /* Serialized by page_table_lock */

  /* Function pointers to deal with this struct. */
  const struct vm_operations_struct *vm_ops;

  /* Information about our backing store: */
  unsigned long vm_pgoff;   /* Offset (within vm_file) in PAGE_SIZE
             units, *not* PAGE_CACHE_SIZE */
  struct file * vm_file;    /* File we map to (can be NULL). */
  void * vm_private_data;   /* was vm_pte (shared mem) */
/* 略 */
```

そのままdup_mmap()を読んでみることにしましょう。

```c:kern/fork.c
#ifdef CONFIG_MMU
static int dup_mmap(struct mm_struct *mm, struct mm_struct *oldmm)
{
/* 略 */
   prev = NULL;
/* 親のアドレス空間の領域を一つずつ処理していく */
   for (mpnt = oldmm->mmap; mpnt; mpnt = mpnt->vm_next) {
     struct file *file;
/* 略 */
/* 
 * まずは領域がannonymous memoryとして処理。
 * 実は対象となる領域がannonymous memoryでない場合、即0を返すので問題ない
 */
     if (anon_vma_fork(tmp, mpnt))
       goto fail_nomem_anon_vma_fork;

/* 
 * 以下、バッキングストアの有無によって処理が分かれているが、今回は略
 */
```

さて、ここでanonという名称の関数が出てきました。
これはその名前からAnnonymous Memoryを扱っているのだろうと思います。
横道に逸れて(深みにはまって)Annonymous Memoryの実現方法を見てみたくなったので、続けて読みます。

## Annonymous Memory(匿名メモリ)とは
要するに「バッキングストア(元ネタとなるファイル)のないデータを格納するためのメモリ領域」です。
例えば、.textの中身やSHAREDでregular fileをmapしたmmap領域などはバッキングストアがあるメモリ領域です。

メモリ不足のときを考えてみましょう。例えば、.textなら捨てたとしてもまた実行形式ファイルから読めば内容を再生できるし、mmap領域であれば一旦ファイルに書き込んで同期をとってしまえば内容を再生できます。
こうした領域は「バッキングストアがある」メモリ領域になります。

しかし、.dataやスタック領域はAnnonymous Memoryと言えます。
これまたメモリ不足のときを考えればよいのですが、.dataは一度RAM上の値が変わると実行ファイル内の内容と一致しなくなります。
だからといって、メモリ不足時に「実行形式ファイルに書きだせば」実行形式ファイルの初期値が変わり、ファイルが壊れてしまいます。
スタックに至っては、実行形式ファイルのどこにも「元ネタ」はありません。
よって、メモリ不足時にはこれらのメモリ領域はswapさせないとダメです。

メモリ領域にはこういう観点の見方もあるということを頭の片隅に於いてもらえれば良いと思います。

## 仮想記憶にズブズブと....
anon_vma_fork()はkernel/の下でなく、mm/の下のソースにあります。
いよいよ仮想記憶のコードにどっぷりと浸かることになります。

```c:mm/rmap.c
int anon_vma_fork(struct vm_area_struct *vma, struct vm_area_struct *pvma)
{
  struct anon_vma_chain *avc;
  struct anon_vma *anon_vma;
/* 略 */
  /*
   * First, attach the new VMA to the parent VMA's anon_vmas,
   * so rmap can find non-COWed pages in child processes.
   */
  if (anon_vma_clone(vma, pvma))
    return -ENOMEM;
  /* Then add our own anon_vma. */
  anon_vma = anon_vma_alloc();
  if (!anon_vma)
    goto out_error;
  avc = anon_vma_chain_alloc(GFP_KERNEL);
  if (!avc)
    goto out_error_free_anon_vma;
```

またまたclone系。複製の層を下へ下へと潜っていきます。

```c:mm/rmap.c
/*
 * Attach the anon_vmas from src to dst.
 * Returns 0 on success, -ENOMEM on failure.
 */
int anon_vma_clone(struct vm_area_struct *dst, struct vm_area_struct *src)
{
  struct anon_vma_chain *avc, *pavc;
  struct anon_vma *root = NULL;
/* anon_vma_chainのanon_vma_chainを先頭とするsame_vmaリストを逆にたどる */
  list_for_each_entry_reverse(pavc, &src->anon_vma_chain, same_vma) {
    struct anon_vma *anon_vma;
 
    avc = anon_vma_chain_alloc(GFP_NOWAIT | __GFP_NOWARN);
    if (unlikely(!avc)) {
      unlock_anon_vma_root(root);
      root = NULL;
      avc = anon_vma_chain_alloc(GFP_KERNEL);
      if (!avc)
        goto enomem_failure;
    }
    anon_vma = pavc->anon_vma;
    root = lock_anon_vma_root(root, anon_vma);
    anon_vma_chain_link(dst, avc, anon_vma);
```

anon_vmaとかanon_vma_chainとか新しい構造体が出てきました。
それらは以下のヘッダにあります。

```c:include/linux/rmap.h
/*
 * The anon_vma heads a list of private "related" vmas, to scan if
 * an anonymous page pointing to this anon_vma needs to be unmapped:
  * the vmas on the list will be related by forking, or by splitting.
 *
 * Since vmas come and go as they are split and merged (particularly
 * in mprotect), the mapping field of an anonymous page cannot point
 * directly to a vma: instead it points to an anon_vma, on whose list
 * the related vmas can be easily linked or unlinked.
 *
 * After unlinking the last vma on the list, we must garbage collect
 * the anon_vma object itself: we're guaranteed no page can be
 * pointing to this anon_vma once its vma list is empty.
 */
struct anon_vma {
  struct anon_vma *root;    /* Root of this anon_vma tree */
  struct rw_semaphore rwsem;  /* W: modification, R: walking the list */
  /*
   * The refcount is taken on an anon_vma when there is no
   * guarantee that the vma of page tables will exist for
   * the duration of the operation. A caller that takes
   * the reference is responsible for clearing up the
   * anon_vma if they are the last user on release
   */
  atomic_t refcount;

  /*
   * NOTE: the LSB of the rb_root.rb_node is set by
   * mm_take_all_locks() _after_ taking the above lock. So the
   * rb_root must only be read/written after taking the above lock
   * to be sure to see a valid next pointer. The LSB bit itself
   * is serialized by a system wide lock only visible to
   * mm_take_all_locks() (mm_all_locks_mutex).
   */
  struct rb_root rb_root; /* Interval tree of private "related" vmas */
};

/*
 * The copy-on-write semantics of fork mean that an anon_vma
 * can become associated with multiple processes. Furthermore,
 * each child process will have its own anon_vma, where new
 * pages for that process are instantiated.
 *
 * This structure allows us to find the anon_vmas associated
 * with a VMA, or the VMAs associated with an anon_vma.
 * The "same_vma" list contains the anon_vma_chains linking
 * all the anon_vmas associated with this VMA.
 * The "rb" field indexes on an interval tree the anon_vma_chains
 * which link all the VMAs associated with this anon_vma.
 */
struct anon_vma_chain {
  struct vm_area_struct *vma;
  struct anon_vma *anon_vma;
  struct list_head same_vma;   /* locked by mmap_sem & page_table_lock */
  struct rb_node rb;      /* locked by anon_vma->rwsem */
  unsigned long rb_subtree_last;
#ifdef CONFIG_DEBUG_VM_RB
  unsigned long cached_vma_start, cached_vma_last;
#endif
};
```

次に、先に進み、anon_vma_chain_link()の中を見ます。

```c:mm/rmap.c
static void anon_vma_chain_link(struct vm_area_struct *vma,
        struct anon_vma_chain *avc,
        struct anon_vma *anon_vma)
{
  avc->vma = vma; 
  avc->anon_vma = anon_vma;
/* anon_vma_chain(head)の次にsame_vmaをつなぐ */
  list_add(&avc->same_vma, &vma->anon_vma_chain);
   anon_vma_interval_tree_insert(avc, &anon_vma->rb_root);
}
```

ここまで読むと、anon_vma_chainは以下の構造になっているように読めます。

```
vma->anon_vma_chain -- <same_vma> -- <same_vma>
                         [avc]         [avc]
                        * vmaは子プロセスのvma
                        * anon_vmaは親プロセス(fork時点)と共用
```

anon_vmaのrb_rootにavcをつないでおきます。
これによって、anon_vmaからはそれが属するvma(vm_area_struct)を引くことができるし、vma側からはanon_vmaをたどることができるようになるはずです。

anon_vma_clone()が終わると、anon_vma視点では、親と子のvmaは以下の構造となるはずです。これで、親と子がとりあえず同じメモリの内容が見える(=複写された*かのように*)ようになります。

```
(Parents)vma->anon_vma_chain -- <same_vma> -- <same_vma>
                                 [avc]         [avc]
                               vma |         vma |
                                   |             |
                                   |             |
                                anon_vma      anon_vma
                                   |             |
                                   |             |
                               vma |         vma |
                                 [avc]         [avc]
(Child   )vma->anon_vma_chain -- <same_vma> -- <same_vma>
```

ちなみにここには載せませんが、list_addもリストヘッドも個々の要素も同じlist_head構造体で捌いたりしています。小ネタ的には「なるほど」と思わせるものがあります。

```c:mm/rmap.c
/* pageをstruct vm_area_structが指すanon_mapが指す領域に移動する */
void page_move_anon_rmap(struct page *page,
	struct vm_area_struct *vma, unsigned long address)
{
	struct anon_vma *anon_vma = vma->anon_vma;
/* 略 */
	/* bit0を立てて、これがanonを指すことを示す */
	anon_vma = (void *) anon_vma + PAGE_MAPPING_ANON;
	page->mapping = (struct address_space *) anon_vma;
}
```

## さらに横道にそれて、Annonymous Memoryと物理ページ(struct page)

1つの物理ページには、それを表現するデータ構造があるのが想定されます。
Linuxではstruct pageがそれに当たります。
いくら、アドレス空間があっても、そこに物理ページを紐付ける手段なければ、何にもなりません。
物理ページとの紐付けについて、疑問に思えてきました。Annonymous Memoryの実装はmm/rmap.cにあるので、物理ページとの紐付けを行う処理もまたこのソースにあると推定し、読んでみます。

すると、pageとanonのmapをひもづけるような関数を見つけました。

```c:mm/rmap.c
void page_add_anon_rmap(struct page *page,
	struct vm_area_struct *vma, unsigned long address)
{
	do_page_add_anon_rmap(page, vma, address, 0);
}

/*
 * Special version of the above for do_swap_page, which often runs
 * into pages that are exclusively owned by the current process.
 * Everybody else should continue to use page_add_anon_rmap above.
 */
void do_page_add_anon_rmap(struct page *page,
	struct vm_area_struct *vma, unsigned long address, int exclusive)
{
	/* 略 */
	/* address might be in next vma when migration races vma_adjust */
	if (first)
		__page_set_anon_rmap(page, vma, address, exclusive);
	else
		__page_check_anon_rmap(page, vma, address);
}

/* ここでmap */
static void __page_set_anon_rmap(struct page *page,
	struct vm_area_struct *vma, unsigned long address, int exclusive)
{
	struct anon_vma *anon_vma = vma->anon_vma;

/* 略 */
	anon_vma = (void *) anon_vma + PAGE_MAPPING_ANON;
	page->mapping = (struct address_space *) anon_vma;
	page->index = linear_page_index(vma, address);
}
```

page構造体のmappingは、それが属するなにがしかのデータ構造につながるようです。
でも、キャストしていることからわかるとおり、mappingはaddress_space構造体のポインタです。一方、anon_vmaはanon_vma構造体のポインタです。
では、実際page構造体のmappingを参照するときに構造体の種別をどうやって見分けるのでしょうか。

実は、PAGE_MAPPING_ANONがポイントです。

```c:include/linux/mm.h
#define PAGE_MAPPING_ANON 1
#define PAGE_MAPPING_KSM  2
#define PAGE_MAPPING_FLAGS  (PAGE_MAPPING_ANON | PAGE_MAPPING_KSM)
```

アドレス値に1を足すことでbit0が1になります。
特殊な事情のない限り、構造体の先頭アドレスが奇数番地に配置されることはありません。よって、page構造体のmappingの値を見れば、それがAnnonymous Memoryに属するかどうかがわかります。

そして、page_add_anon_rmap()の引数で渡ってくるaddressをindexという値に変換しています。(おそらく、addressは仮想アドレスだと思われる)
この変換を行っているのは、以下の関数です。

```c:include/linux/pagemap.h

static inline pgoff_t linear_page_index(struct vm_area_struct *vma,
					unsigned long address)
{
	pgoff_t pgoff;
	if (unlikely(is_vm_hugetlb_page(vma)))
		return linear_hugepage_index(vma, address);
	/* vm map areaの先頭からのオフセットをページ単位で求め...*/
	pgoff = (address - vma->vm_start) >> PAGE_SHIFT;
	/* 
         * え、このvm_pgoffは何者？vm_map_area内のオフセットを
         * 求めたいのなら、さらに下駄を履かせる必要はあるの？
         * そもそもvm_pgoffは何？
         */
	pgoff += vma->vm_pgoff;
	return pgoff >> (PAGE_CACHE_SHIFT - PAGE_SHIFT);
}
```

vm_pgoffsetがよくわからんのでgrepすると、以下の関数がその理解の助けになりそうです。

```c:mm/mmap.c

/* これがおそらく、anonymousな場合のpg_off */
int insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vma)
{
	struct vm_area_struct *prev;
	struct rb_node **rb_link, *rb_parent;

	/*
	 * The vm_pgoff of a purely anonymous vma should be irrelevant
	 * until its first write fault, when page's anon_vma and index
	 * are set.  But now set the vm_pgoff it will almost certainly
	 * end up with (unless mremap moves it elsewhere before that
	 * first wfault), so /proc/pid/maps tells a consistent story.
	 *
	 * By setting it to reflect the virtual start address of the
	 * vma, merges and splits can happen in a seamless way, just
	 * using the existing file pgoff checks and manipulations.
	 * Similarly in do_mmap_pgoff and in do_brk.
	 */
	if (!vma->vm_file) {
		BUG_ON(vma->anon_vma);
		vma->vm_pgoff = vma->vm_start >> PAGE_SHIFT;
	}
```
Annonymous Memoryの場合は、vm_pgoffにそのvmaの先頭アドレスをページ単位に丸めた値が格納されるようです。結構コメントも詳しく書いてあるのでイメージができます。

ここまでを読むと、page構造体からそれに対応した仮想アドレスを取得することと、その逆をどのようにすればよいかが見えてきます。

しかし、物理アドレスをLinuxではどうやって扱っているのでしょうか？
例えば、仮想アドレスから物理アドレスを得る、ページ構造体からそれが指している物理アドレスを得る方法が今ひとつ見えません。

ここいらの疑問をを次回以降見ていきたいと思います。