LoginSignup
6
6

More than 5 years have passed since last update.

LinuxAdvent Calendar 2014Day 20
@akachochin

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

Posted at

今回やること

どうもです。@akachochinです。前回からはや1ヵ月近くが立ちました。なかなか時間が取れずでしたが、仕事も落ち着き始めようやく少し時間がとれるようになってきました。
忘年会も始まるこの時期、仕事が落ち着かないと酒飲みとしては困ります。
閑話休題。
今回は複数ページを割り当てるための内部関数二つを見たいと思います。

__rmqueue_smallest()と__rmqueue_fallback()

デフォルトで、__rmqueue_smallest()が呼ばれます。

mm/page_alloc.c
/*
 * Go through the free lists for the given migratetype and remove
 * the smallest available page from the freelists
 */
static inline
struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
            int migratetype)
{
  unsigned int current_order;
  struct free_area *area;
  struct page *page;

  /* Find a page of the appropriate size in the preferred list */
  for (current_order = order; current_order < MAX_ORDER; ++current_order) {
    area = &(zone->free_area[current_order]);
    if (list_empty(&area->free_list[migratetype]))
      continue;

    page = list_entry(area->free_list[migratetype].next,
              struct page, lru);
    list_del(&page->lru);
    rmv_page_order(page);
    area->nr_free--;
    expand(zone, page, order, current_order, area, migratetype);
    return page; 
  }

  return NULL;
}

思い出してほしいですが、連続したページと言っても3ページとか7ページのような”中途半端な”ページを割り当てるのではなく、2のべき乗の複数ページを割当ます。
orderはlog2Page(2のorder乘)です。

zone->free_area[current_order]には、2のべき乗の連続したページを示すareaが格納されています。
areaはキューを持ち、その中に何のエントリがなければ、そのorderにおける連続したページはないので、次に進みます。
例えばorder = 2の場合、2^2 = 4ページ分の連続したページを探すことになります。

rmv_page_order

さて、連続したページを見つけられた場合、rmv_page_orderが呼ばれます。

mm/page_alloc.c
static inline void rmv_page_order(struct page *page)
{
  __ClearPageBuddy(page);
  set_page_private(page, 0);
}
include/linux/mm.h
#define PAGE_BUDDY_MAPCOUNT_VALUE (-128)
/* 略 */
/*
 * PageBuddy() indicate that the page is free and in the buddy system
 * (see mm/page_alloc.c).
 *
 * PAGE_BUDDY_MAPCOUNT_VALUE must be <= -2 but better not too close to
 * -2 so that an underflow of the page_mapcount() won't be mistaken
 * for a genuine PAGE_BUDDY_MAPCOUNT_VALUE. -128 can be created very
 * efficiently by most CPU architectures.
 */
/* 略 */
static inline void __SetPageBuddy(struct page *page)
{
  VM_BUG_ON_PAGE(atomic_read(&page->_mapcount) != -1, page);
  atomic_set(&page->_mapcount, PAGE_BUDDY_MAPCOUNT_VALUE);
}

static inline void __ClearPageBuddy(struct page *page)
{
  VM_BUG_ON_PAGE(!PageBuddy(page), page);
  atomic_set(&page->_mapcount, -1);
}

おそらく、_mapcountが特殊な値であることをもって、該当ページがBuddy(組)に配置されているかを判別できるのだと推定できます。
そして、Buddyから外されたので、_mapcountの値を変更できるということでしょう。

expand

expand()は「欲しい連続ページよりも大きな連続ページを獲得した場合、それを分割して必要な箇所のみを取得、残りの箇所については他のorderのfree_listに割り当てる。」関数です。

mm/page_alloc.c
static inline void expand(struct zone *zone, struct page *page,
  int low, int high, struct free_area *area,
  int migratetype)
{
  unsigned long size = 1 << high;

  while (high > low) {
    area--;
    high--;
    size >>= 1;
/* デバッグコードなので、略 */
    list_add(&page[size].lru, &area->free_list[migratetype]);
    area->nr_free++;
    set_page_order(&page[size], high);
  }
}

lowには本来要求されていたorder、highには空きページが存在したorderが渡される。
例えば、low=2(要求されたページサイズが2^2)、実際に空きページが見つかったorderが4である場合を考えてみましょう。
この場合、連続した4ページを管理するLRU、連続した8ページを管理するLRUの中に空きがなく、16ページを管理するためのLRU内にようやっと空きページがあるという状況になります。

size = 16 area(order=4のfree_area) high = 4
size = 8 area(order=3のfree_area) high=3
list_addには割り当てたページの8ページ先のページをorder3のarea->free_listにつなぎます。つまり連続した16ページの後半8ページをorder3のarea->free_listにつなぎます。
size = 4 area(order=2のfree_area) high=2
list_addには割り当てたページの8ページ先のページをorder3のarea->free_listにつなぎます。つまり先に分割した前半の8ページの後半4ページをorder2のarea->free_listにつなぎます。

zone->free_areaについて

ここまでのところで、空いた連続ページ群を管理するためのareaが出てきました。
その定義は以下の通りです。

include/linux/mmzone.h
/* x86の場合、特にCONFIG_FORCE_MAX_ZONEORDERでしていない場合は以下の値 */
#define MAX_ORDER 11
struct free_area {
  struct list_head  free_list[MIGRATE_TYPES];
  unsigned long   nr_free;
};
/* 略 */
struct zone {
/* 略 */
  struct free_area  free_area[MAX_ORDER];
/* 略 */
}

上に引用した定義から、以下の事があります。
* zoneはfree_areaをMAX_ORDER個持つ
* free_areaはMIGRATE_TYPES個のページキューを持つ

さて、MAX_ORDERはべき乗に関する話(2^0,2^1,2^2...個の連続ページ)だとわかりますが、MIGRATE_TYPESとはなんでしょうか。

MIGRATE_TYPESとは...

MIGRATE_TYPESを探すと、以下のヘッダに行き着きます。

include/linux/mmzone.h
#define for_each_migratetype_order(order, type) \
  for (order = 0; order < MAX_ORDER; order++) \
    for (type = 0; type < MIGRATE_TYPES; type++)

enum {
  MIGRATE_UNMOVABLE,
  MIGRATE_RECLAIMABLE,
  MIGRATE_MOVABLE,
  MIGRATE_PCPTYPES, /* the number of types on the pcp lists */
  MIGRATE_RESERVE = MIGRATE_PCPTYPES,
#ifdef CONFIG_CMA
  /*
   * MIGRATE_CMA migration type is designed to mimic the way
   * ZONE_MOVABLE works.  Only movable pages can be allocated
   * from MIGRATE_CMA pageblocks and page allocator never
   * implicitly change migration type of MIGRATE_CMA pageblock.
   *
   * The way to use it is to change migratetype of a range of
   * pageblocks to MIGRATE_CMA which can be done by
   * __free_pageblock_cma() function.  What is important though
   * is that a range of pageblocks must be aligned to
   * MAX_ORDER_NR_PAGES should biggest page be bigger then
   * a single pageblock.
   */
  MIGRATE_CMA,
#endif
#ifdef CONFIG_MEMORY_ISOLATION
  MIGRATE_ISOLATE,  /* can't allocate from here */
#endif
  MIGRATE_TYPES
};

さらに調べると、以下のDocumentationに行き着きます。

Page migration allows the moving of the physical location of pages between
nodes in a numa system while the process is running. This means that the
virtual addresses that the process sees do not change. However, the system rearranges the physical location of those pages.

The main intend of page migration is to reduce the latency of memory access by moving pages near to the processor where the process accessing that memory is running.

相当に意訳すると...

ページマイグレーションによって、プロセスを動かしつつNUMAシステムのノード間でページの物理的な配置を動かすことができる。これはプロセスから見える仮想アドレスが変わらず(それと紐づく物理アドレスが変わる)ことを意味する。
ページマイグレーションが主に意図するのはメモリアクセスの遅延を減らすことであり、それは該当ページにアクセスしているプロセスが動作しているCPUから近いメモリにページを移すことによって行う。

もう少し詳しく知りたければ、以下のページも参考になると思います。

http://lwn.net/Articles/157066/
http://gihyo.jp/dev/serial/01/linuxcon_basic/0005

ちなみに、__rmqueue_fallback()は、指定したマイグレーションタイプに連続したページがない場合、マイグレーションタイプが異なる連続ページからページを移してきて頁割り当てを行います。

mm/page_alloc.c
static inline struct page *
__rmqueue_fallback(struct zone *zone, int order, int start_migratetype)
{
  /* Find the largest possible block of pages in the other */
  for (current_order = MAX_ORDER-1; current_order >= order;
            --current_order) {
    for (i = 0;; i++) {
      migratetype = fallbacks[start_migratetype][i];

      if (list_empty(&area->free_list[migratetype]))
        continue;

ところが、「マイグレーションタイプはなんでも良い」というわけにはいかないようです。
制約があり、それを規定するのがfallbackテーブルです。

mm/page_alloc.c
/*
 * This array describes the order lists are fallen back to when
 * the free lists for the desirable migrate type are depleted
 */
static int fallbacks[MIGRATE_TYPES][4] = {
  [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,     MIGRATE_RESERVE },
  [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,     MIGRATE_RESERVE },
#ifdef CONFIG_CMA
  [MIGRATE_MOVABLE]     = { MIGRATE_CMA,         MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRAT     E_RESERVE },
  [MIGRATE_CMA]         = { MIGRATE_RESERVE }, /* Never used */
#else
  [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE,   MIGRATE_RESERVE },
#endif
  [MIGRATE_RESERVE]     = { MIGRATE_RESERVE }, /* Never used */
#ifdef CONFIG_MEMORY_ISOLATION
  [MIGRATE_ISOLATE]     = { MIGRATE_RESERVE }, /* Never used */
#endif
};

例えば、MIGRATE_UNMOVABLEのページを調達したいがページがない場合、MIGRATE_RECLAIMABLE,MIGRATE_MOVABLE,MIGRATE_RESERVEのいずれかから調達することになります。

次回やりたいこと

だいぶ前になりますが、Linux(x86-32bit)のページフォルトハンドラを読んでみる(その5)を書きました。
その6からその9でdo_linear_fault()とdo_anonymous_page()を読みました。
次回は、do_nonlinear_fault()を見たいと思います。

6
6
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
6