Linux(x86-32bit)のページフォルトハンドラを読んでみる(その8) 

## 今回やること

どうもです。@akachochinです。前回から時間が結構経ちました。kernelvmのつくばはなかなか楽しめました。個人的にはLinuxのシュリンクが大変興味深かったです。その上、そのあとの秋葉原での飲み会も楽しめました。やはり、カーネル好きな人たちと語れるのは楽しいです。

さて、[前回](http://qiita.com/akachochin/items/325863a6699000e228b8)書いたとおり、今回はalloc_page_vma()を見ます。

## alloc_page_vma()

以下の通り、alloc_page_vma() -> alloc_pages_vma() -> alloc_pages_node() -> \_\_alloc_pages()の順で呼ばれ、最終的には__alloc_pages_nodemask()が呼ばれます。

```c:include/linux/gfp.h
static inline struct page *
__alloc_pages(gfp_t gfp_mask, unsigned int order,
    struct zonelist *zonelist)
{
  return __alloc_pages_nodemask(gfp_mask, order, zonelist, NULL);
}

static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask,
            unsigned int order)
{
  /* Unknown node is current node */
  if (nid < 0)
    nid = numa_node_id();

  return __alloc_pages(gfp_mask, order, node_zonelist(nid, gfp_mask));
}
/* 略 */
#ifdef CONFIG_NUMA
/* 今回話を簡単にするために、ここは略 */
#else
#define alloc_pages(gfp_mask, order) \
    alloc_pages_node(numa_node_id(), gfp_mask, order)
#define alloc_pages_vma(gfp_mask, order, vma, addr, node) \
  alloc_pages(gfp_mask, order)
#endif
#define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)
#define alloc_page_vma(gfp_mask, vma, addr)     \   
  alloc_pages_vma(gfp_mask, 0, vma, addr, numa_node_id())
#define alloc_page_vma_node(gfp_mask, vma, addr, node)    \   
  alloc_pages_vma(gfp_mask, 0, vma, addr, node)
```

__alloc_pages_nodemask()は以下の実装となります。

```c:mm/page_alloc.c
/*
 * This is the 'heart' of the zoned buddy allocator.
 */
struct page *
__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,
      struct zonelist *zonelist, nodemask_t *nodemask)
{
/* 略 */
  int migratetype = allocflags_to_migratetype(gfp_mask);
/* 略 */
```

このmygratetypeは後で使われます。これは以下のようにメモリ割り当ての属性がMOVABLEとRECLAIMABLEであるかどうかを示すフラグとなります。
allocflags_to_migratetype()は以下実装となります。

```c:include/linux/gfp.h
static inline int allocflags_to_migratetype(gfp_t gfp_flags)
{
  WARN_ON((gfp_flags & GFP_MOVABLE_MASK) == GFP_MOVABLE_MASK);
  
  if (unlikely(page_group_by_mobility_disabled))
    return MIGRATE_UNMOVABLE;
    
  /* Group based on mobility */
  return (((gfp_flags & __GFP_MOVABLE) != 0) << 1) |
    ((gfp_flags & __GFP_RECLAIMABLE) != 0);
}
```

続いて、get_page_from_freelist()が呼ばれます。
もちろん、この関数がページ割り当ての中心になることは容易に想像できます。

```c:mm/page_alloc.c
  /* First allocation attempt */
  page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask, order,
      zonelist, high_zoneidx, alloc_flags,
      preferred_zone, migratetype);

/* 略 */
  return page;
}
EXPORT_SYMBOL(__alloc_pages_nodemask);
```

## get_page_from_freelist()

瑣末な箇所を省略すると、だいたい以下の実装となります。

```c:mm/page_alloc.c
/*
 * get_page_from_freelist goes through the zonelist trying to allocate
 * a page.
 */
static struct page *
get_page_from_freelist(gfp_t gfp_mask, nodemask_t *nodemask, unsigned int order,    struct zonelist *zonelist, int high_zoneidx, int alloc_flags,
    struct zone *preferred_zone, int migratetype)
{
/* 略 */
  for_each_zone_zonelist_nodemask(zone, z, zonelist,
            high_zoneidx, nodemask) {
    unsigned long mark;
/* 略 */
      /* 
       * CONFIG_NUMAが無効な場合、単に0を返す
       * この場合、defaultへいく。
       * (see include/linux/swap.h)
       */
      ret = zone_reclaim(zone, gfp_mask, order);
      switch (ret) {
      case ZONE_RECLAIM_NOSCAN:
        /* did not scan */
        continue;
      case ZONE_RECLAIM_FULL:
        /* scanned but unreclaimable */
        continue;
      default:
        /* did we reclaim enough */
        if (zone_watermark_ok(zone, order, mark,
            classzone_idx, alloc_flags))
          goto try_this_zone;
/* 略 */
      }
    }

try_this_zone:
    page = buffered_rmqueue(preferred_zone, zone, order,
            gfp_mask, migratetype);
    if (page)
      break;
/* 略 */
  }

/* 略 */
  return page;
}
```

zone_watermark_ok()は該当zoneに十分な空きページがあるかどうかを調べる関数で最終的には以下の関数__zone_watermark_ok()が呼ばれます。

```c:mm/page_alloc.c
static bool __zone_watermark_ok(struct zone *z, int order, unsigned long mark,
          int classzone_idx, int alloc_flags, long free_pages)
{
/* 略 */
#ifdef CONFIG_CMA
  /* If allocation can't use CMA areas don't use free CMA pages */
  if (!(alloc_flags & ALLOC_CMA))
    free_cma = zone_page_state(z, NR_FREE_CMA_PAGES);
#endif

  if (free_pages - free_cma <= min + lowmem_reserve)
    return false;
/* 略 */
  return true;
}
```

ここで、CMAとは、Continuous Memory Allocator frameworkのことである。概要は[ここ](http://lwn.net/Articles/416303/)に書かれているので参考にされたいです。
また、引数のfree_pagesはzone_page_state()という関数経由でzone->vm_stat[]から取ってきます。(include/linux/vmstat.h)

## buffered_rmqueue()
ページ割り当てはbuffered_rmqueue()で実施するようです。

```c:mm/page_alloc.c
static inline
struct page *buffered_rmqueue(struct zone *preferred_zone,
      struct zone *zone, int order, gfp_t gfp_flags,
      int migratetype)
{
  unsigned long flags;
  struct page *page;
  int cold = !!(gfp_flags & __GFP_COLD);
```

### まず、__GFP_COLDって何？

まずは、以下の定義のコメントを見ることにします。

```c:include/linux/gfp.h
#define __GFP_COLD  ((__force gfp_t)___GFP_COLD)  /* Cache-cold page required */
```

Cache-cold pageとは「該当ページに対応したキャッシュが残っている率が低いページ」のことを指します。

[LWN.netの記事](http://lwn.net/Articles/14768/)によると、

> The processor cache contains memory which has been accessed recently. The kernel often has a good idea of which pages have seen recent accesses and are thus likely to be present in cache. 

とあり、このように解放されて間もないRAMのデータがキャッシュに残っているかもしれないページはhotなページと言います。
その逆に解放されてから時間が経過しているページのことをcoldなページと言います。
※もちろん、hotだからといって常にCPUキャッシュに残っているとは限らず、その逆にcoldだからといってCPUキャッシュに残っていない保証はどこにもありません。あくまでも「その可能性が高い」だけです。

記事にあるとおり、おおよそはhotなページが良いのですが、DMAに使うメモリのように「Cache Flush&Invalidate時に書き戻したり無効にするキャッシュエントリが少ないほうが良い」ケースもあるのです。

### 1ページだけ割り当てる

次に、1ページだけ割り当てるケースを見ることにします。

```c:mm/page_alloc.c
again:
  /* 2 ^ 0 ... つまり1ページだけ割り当てたい場合 */
  if (likely(order == 0)) {
    struct per_cpu_pages *pcp;
    struct list_head *list;

    local_irq_save(flags);
    pcp = &this_cpu_ptr(zone->pageset)->pcp;
```

今動いているCPUごとに持っているページを取得するためにper_cpu_pagesを取得します。
データ構造は以下のとおりです。

```c:include/linux/mmzone.h
struct per_cpu_pages {
  int count;    /* number of pages in the list */
  int high;   /* high watermark, emptying needed */
  int batch;    /* chunk size for buddy add/remove */
     
  /* Lists of pages, one per migrate type stored on the pcp-lists */
  struct list_head lists[MIGRATE_PCPTYPES];
};
```

migratetypeごとに存在するページキューを取得し、中が空か判定します。
中が空の場合、ページを補充するようです。

```c:mm/page_alloc.c
    list = &pcp->lists[migratetype];
    if (list_empty(list)) {
      pcp->count += rmqueue_bulk(zone, 0,
          pcp->batch, list,
          migratetype, cold);
      if (unlikely(list_empty(list)))
        goto failed;
    }
```

ここに来た時点で、キューの中にはページが存在するはずです。
よって、1ページ分だけページを取得します。
coldな場合は、リストの末尾にあるデータを取得し、そうでない場合はlistの先頭、つまりhotなページを取得します。
(struct listはinclude/linux/list.hにあるとおり、doubly-link listです。よって、list->prevはリストの末尾を指します。)

```c:mm/page_alloc.c
    if (cold)
      page = list_entry(list->prev, struct page, lru);
    else
      page = list_entry(list->next, struct page, lru);

    list_del(&page->lru);
    pcp->count--;
```

### 複数ページを割り当てる

以下のように、__rmqueue()が割り当て作業の中心となります。

```c:mm/page_alloc.c
  /* 複数のページを割り当てる */
  } else {
/* 略 */
    spin_lock_irqsave(&zone->lock, flags);
    page = __rmqueue(zone, order, migratetype);
    spin_unlock(&zone->lock);
    if (!page)
      goto failed;
    __mod_zone_freepage_state(zone, -(1 << order),
            get_pageblock_migratetype(page));
  }
```

\_\_rmqueue()では、\_\_rmqueue_smallest()が呼ばれます。
以降の処理などから考えるに、たいていの場合は__rmqueue_smallest()で片がつきます。

```c:mm/page_alloc.c
/*
 * Do the hard work of removing an element from the buddy allocator.
 * Call me with the zone->lock already held.
 */
static struct page *__rmqueue(struct zone *zone, unsigned int order,
            int migratetype)
{
  struct page *page;

retry_reserve:
  page = __rmqueue_smallest(zone, order, migratetype);
```

それでも片がつかない場合、以下のように\_\_rmqueue_fallback()が呼ばれます。

```c:mm/page_alloc.c
  if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {
    page = __rmqueue_fallback(zone, order, migratetype);
/* 略 */
```

これら\_\_rmqueue_smallest()と\_\_rmqueue_fallback()は次回見ることにします。

## ちなみに、buffered_rmqueue()の最後

以下のとおり、ほとんどが統計情報の更新と思われるので、深入りはしません。

```c:mm/page_alloc.c
  __mod_zone_page_state(zone, NR_ALLOC_BATCH, -(1 << order));

  __count_zone_vm_events(PGALLOC, zone, 1 << order);
  zone_statistics(preferred_zone, zone, gfp_flags);
  local_irq_restore(flags);

  VM_BUG_ON_PAGE(bad_range(zone, page), page);
  if (prep_new_page(page, order, gfp_flags))
    goto again;
  return page;

failed:
  local_irq_restore(flags);
  return NULL;
}
```

## 次回
複数ページを割り当てるための、\_\_rmqueue_smallest()と\_\_rmqueue_fallback()を見ていきます。