Virtual Memory: Grouping pages by mobility

2000년대에는 가상 메모리에서 단편화를 줄이려는 노력이 꾸준히 있었다. 그 중 하나가 이 글에서 분석할, Mel Gorman의 패치 시리즈이다. 이 패치 시리즈는 특성이 서로 다른 페이지를 묶어서 관리해 외부 단편화를 최소화한다.

External Fragmentation

https://commons.wikimedia.org/wiki/File:External_Fragmentation.svg

시스템이 부팅된 이후 시간이 지남에 따라서 메모리는 자연스럽게 단편화가 발생한다. 위 사진처럼 실제 가용 메모리의 크기는 충분하더라도 메모리 블럭이 쪼개지면서 연속적이지 않게되는 걸 외부 단편화라고 한다. 부팅 이후 시간이 많이 지나면 지날수록 외부 단편화가 심해진다.

What is mobility

우선 mobility가 무엇인지 살펴보자. 리눅스에서 페이지의 mobility는 migratetype으로 정의되므로 migratetype을 읽어보자.

enum migratetype

  42 enum migratetype {
  43         MIGRATE_UNMOVABLE,
  44         MIGRATE_MOVABLE,
  45         MIGRATE_RECLAIMABLE,
  46         MIGRATE_PCPTYPES,       /* the number of types on the pcp lists */
  47         MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES,
  48 #ifdef CONFIG_CMA
  49         /*
  50          * MIGRATE_CMA migration type is designed to mimic the way
  51          * ZONE_MOVABLE works.  Only movable pages can be allocated
  52          * from MIGRATE_CMA pageblocks and page allocator never
  53          * implicitly change migration type of MIGRATE_CMA pageblock.
  54          *
  55          * The way to use it is to change migratetype of a range of
  56          * pageblocks to MIGRATE_CMA which can be done by
  57          * __free_pageblock_cma() function.  What is important though
  58          * is that a range of pageblocks must be aligned to
  59          * MAX_ORDER_NR_PAGES should biggest page be bigger than
  60          * a single pageblock.
  61          */
  62         MIGRATE_CMA,
  63 #endif
  64 #ifdef CONFIG_MEMORY_ISOLATION
  65         MIGRATE_ISOLATE,        /* can't allocate from here */
  66 #endif
  67         MIGRATE_TYPES
  68 };

 

MIGRATE_MOVABLE: 페이지를 할당하면 페이지의 가상 주소 -> 물리 주소 매핑이 존재하는데, 이 때 페이지 테이블을 수정해서 가상 주소가 가리키는 물리 주소를 바꾸고, 페이지에 기록된 데이터를 다른 페이지로 복사하면 가상 주소가 가리키는 페이지를 옮길 수 있다. 이런 식으로 옮길 수 있는 페이지가 MIGRATE_MOVABLE에 속한다. 사용자 프로세스가 사용하는 페이지가 여기에 해당된다. 이렇게 페이지를 옮길 경우 성능상 오버헤드가 생기는 대신 물리적으로 연속된 페이지를 확보할 수 있다.

MIGRATE_RECLAIMABLE:

페이지가 예를 들어 페이지 캐시로 이런 경우에 페이지는 MOVABLE하진 않지만 쉽게 RECLAIM할 수 있다. 이렇듯 캐시로 사용되거나, 페이지의 생애 주기가 매우 짧을 때 MIGRATE_RECLAIMABLE을 사용한다. 페이지 할당시 __GFP_RECLAIMABLE으로 할당하면 RECLAIMABLE한 페이지가 할당된다.

MIGRATE_UNMOVABLE:

위에서 살펴본 MOVABLE과 RECLAIMABLE은 특수한 케이스로, 일반적으로 할당하는 페이지들은 reclaimable, movable하지 않다. 페이지 할당시 별다른 플래그가 없으면 MIGRATE_UNMOVABLE로 할당된다.

MIGRATE_HIGHATOMIC:

Atomic하고, IO를 수행하지 않는 컨텍스트에서 high-order allocation을 수행할 때 사용된다.

MIGRATE_CMA, MIGRATE_ISOLATE: 이 글에서는 다루지 않는다.

MIGRATE_TYPES: migratetype의 개수이다.

Grouping pages by mobility

이 패치 시리즈 이전에는 zone의 free_area를 order별로만 관리했다. (그림 참조)

https://lwn.net/Articles/121618/

이 패치 시리즈 이후에는 migratetype별로 페이지를 관리한다. 사진이 migratetype이 도입되기 전 사진이라 살짝 다르긴 한데, 개념 자체는 사진이 잘 설명하고 있다.

https://lwn.net/Articles/121618/

그런데 왜 페이지를 mobility에 따라 분리하면 외부 단편화가 줄어들까?

위 사진은 단편화가 발생한 메모리를 그림으로 나타낸 것이다. 빨간 페이지는 Unmovable한 페이지이고, 파란색은 Reclaimable한 페이지라고 해보자. Reclaimable한 페이지는 여기저기 흩어져서 할당된다 해도 할당시에 Reclaim할 수 있거나, 생애주기가 짧아서 조금만 기다리면 할당할 수 있는 상태가 된다. 하지만 Unmovable한 페이지는 언제 해제될지 모르기 때문에, 이런 페이지가 여기저기 흩어져서 할당되면 시간이 지날수록 high-order allocation이 극단적으로 어려워진다.

그런 점에서 Mel Gorman의 패치 시리즈는 서로 다른 특성의 페이지를 따로 관리하기 때문에, Unmovable한 페이지가 여기저기 흩어지는 것을 막아서 외부 단편화를 줄인다고 할 수 있다. 실제로 테스트 결과도 high-order allocation의 성공률이 드라마틱하게 올라갔다. (Mel 그는 신이야..!)

Split the free lists for movable and unmovable allocations

실제 패치를 보면 free_area를 migrate type에 따라 나눠서 관리함을 알 수 있다.

commit b2a0ac8875a0a3b9f0739b60526f8c5977d2200f
Author: Mel Gorman <mel@csn.ul.ie>
Date:   Tue Oct 16 01:25:48 2007 -0700
	Split the free lists for movable and unmovable allocations

    This patch adds the core of the fragmentation reduction strategy.  It works by
    grouping pages together based on their ability to migrate or be reclaimed.
    Basically, it works by breaking the list in zone->free_area list into
    MIGRATE_TYPES number of lists.

    Signed-off-by: Mel Gorman <mel@csn.ul.ie>
    Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
    Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
index 322e8048463e..57700038e669 100644
--- a/include/linux/mmzone.h
+++ b/include/linux/mmzone.h
@@ -33,8 +33,16 @@
  */
 #define PAGE_ALLOC_COSTLY_ORDER 3

+#define MIGRATE_UNMOVABLE     0
+#define MIGRATE_MOVABLE       1
+#define MIGRATE_TYPES         2
+
+#define for_each_migratetype_order(order, type) \
+       for (order = 0; order < MAX_ORDER; order++) \
+               for (type = 0; type < MIGRATE_TYPES; type++)
+
 struct free_area {
-       struct list_head        free_list;
+       struct list_head        free_list[MIGRATE_TYPES];
        unsigned long           nr_free;
 };

이 패치가 도입된 후로는 페이지의 특성인 migrate type에 따라 free_area를 별도로 관리한다.

Reduce external fragmentation by grouping pages by mobility v30

Linux-Kernel Archive: [PATCH 0/13] Reduce external fragmentation by grouping pages by mobility v30

실제 패치 시리즈의 링크이다. 코드 레벨에서 분석해보려고 했으나 가상 메모리 서브시스템을 잘 몰라서 실패했다. changelog를 보면 대강 하는 일은 다음과 같다.

- migrate type을 추가하고 free_area에서 migrate type에 따라 페이지를 관리

- 할당하려는 migrate type에 free 페이지가 없을 때 다른 migrate type에서 가져옴

- high-order allocation이 실패하면 per-cpu freelist를 비워버림

- MIGRATE_RECLAIMABLE에서 free 페이지를 가져올 때는 좀더 aggressive하게 할당을 시도함

- 생애주기가 짧은 페이지를 할당할 때는 __GFP_RECLAIMABLE 플래그를 포함해서 할당

... 등등