Group pages of related mobility to reduce external fragmentation

Purpose

해당 패치의 시작은 연속된 큰 메모리 할당(High-order allocations)이 어렵다는 이유로 시작됐다. 연관된 타입들의 페이지들을 grouping 하고 타입 별로 메모리 할당자를 분리하는 것으로 외부 단편화를 줄인다.

Main Patch Series

1. 835c134ec4dd Add a bitmap that is used to track flags affecting a block of pages

2. b2a0ac8875a0 Split the free lists for movable and unmovable allocations

3. 535131e6925b Choose pages from the per-cpu list based on migration type

4. e2c55dc87f4a Drain per-cpu lists when high-order allocations fail

5. c361be55b312 Move free pages between lists on steal

6. e010487dbe09 Group high-order atomic allocations

7. e12ba74d8ff3 Group short-lived and reclaimable kernel allocations

8. 46dafbca2bba Be more agressive about stealing when MIGRATE_RECLAIMABLE allocations fallback

---

External Fragmentation

예전의 리눅스의 zone에는 하나의 free list로 페이지들을 관리하였다. 아래의 그림은 Max order가 4이고 사용가능한 페이지가 8개 있는 zone의 그림이다.

커널에서 할당된 페이지들은 사용되는 용도에 따라 다른 속성을 가진다. 페이지가 reclaim 또는 migrate 될 수 있는 속성을 임의로 movable이라 하고, 그럴 수 없는 페이지의 속성을 unmovable이라 하자. Order 0의 movable 페이지와 unmovable 페이지가 번갈아가면서 할당하면 아래와 상황이 발생한다.

짝수 페이지들은 movable 속성을 가지고, 홀수 페이지들은 unmovable이다. movable 속성 페이지들이 reclaim 또는 migrate 된다면 아래 그림과 같이 된다.

위 그림에서 Zone은 free pages가 4임에도 1 이상의 Order에 대해서는 할당이 실패한는데 외부 단편화가 극심하기 때문이다.

---

Basic idea

핵심 아이디어는 페이지의 속성에 따라 free list를 분리하는 것이다. 만약 위 예제의 경우 movable과 unmovable의 분리되면 아래 그림과 같다.

마찬가지로, Order 0의 movable 페이지와 unmovable 페이지가 번갈아가면서 할당된다 생각해보자.

이전과 다르게 같은 속성의 타입들이 함께 뭉쳐져 있게 된다. 이런 상태에서 movable 페이지들이 migrate나 reclaim이 된다면 아래와 같이 연속된 페이지를 사용할 수 있게 된다.

실제 구현에서의 페이지의 타입은 총 4가지로,

1. Movable: migration이 가능한 페이지로 주로 유저 영역의 페이지이다.

2. Reclaimable: 커널 캐시로 사용되어 reclaim 가능하거나, 짧은 시간동안 할당되어 있는 페이지이다.

3. Unmovable: 기본적으로 커널에서 할당하는 페이지로 reclaim될 수 없는 페이지들이다.

4. High Atomic: Sleep이나 IO를 하지 않고 High order 요청에 사용되는 페이지이다.

---

Implementation

위에서 소개한 아이디어를 좀 더 구체화해보자.

우선, 페이지 블록(page block)이라는 단위를 도입한다. 페이지 블록은 동일한 타입의 페이지들을 모으기 위한 페이지들의 집합이다. 페이지 블록의 크기를 Order 2로 하면 아래 그림과 같다.

Page 0~3은 Page block 0에 속하고, Page 4~7은 Page block 1에 속한다.

또한 사용되던 페이지가 free되면 어느 migration 타입의 free list에 추가되는지 알 수 있어야 한다. 이를 위해 페이지 블록마다 속성을 저장하고, 해당 페이지가 속한 페이지 블록 속성에 따라 free list가 결정된다.

위의 그림에서 page 3이 free 될 때, 해당 페이지가 속한 page block의 속성이 Movable이기에, Movable free list에 추가된다.

만약, migration type에 할당 요청을 충족시킬 page가 없다면, 다른 migration type으로부터 페이지 블록을 steal한다.

만약 위 그림처럼 Movable free list에 할당 요청을 만족시킬 페이지가 없다면, 다른 Migration type free list에서 페이지 블록을 가지고 온 후, 재할당한다.