top of page
작성자 사진Wonhyuk Yang

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에서 페이지 블록을 가지고 온 후, 재할당한다.


조회수 371회댓글 12개

관련 게시물

전체 보기

12 Comments


유형곤
유형곤
Jan 03, 2022

관련된 유익한 PPT가 있어서 공유합니당

https://www.linuxplumbersconf.org/event/2/contributions/65/attachments/15/171/slides-expanded.pdf

Like
유형곤
유형곤
Jan 03, 2022
Replying to

우왕 왜 그생각을 못했죠 ㅋㅋㅋㅋ 영상이 있구나!! 좋아요!

Like

유형곤
유형곤
Jan 02, 2022

이 글을 읽으면서 갑자기 드는 질문인데, 글에서 설명한 패치 시리즈에서 free_area를 page를 migrate type별로 나눴잖아요. 그럼 ZONE_MOVABLE은 왜 존재하는 걸까요? MOVABLE한 페이지를 하나의 Zone으로 묶어서 얻는 이점이 뭘까요?


물론 ZONE_MOVABLE 덕분에 메모리 핫플러깅을 활용할 수는 있지만 그게 ZONE_MOVABLE을 도입한 이유는 아닌 것 같아서요.

Like
유형곤
유형곤
Jan 03, 2022
Replying to

좀 더 찾아봤는데 좋은 설명이 있네요.


요약:

- List-based grouping: 일반적인 상황에서 별다른 configuration 없이 단편화를 줄일 수 있음.

- ZONE_MOVABLE: Movable한 페이지만 모아서 별도의 Zone으로 만들어서 high-order allocation이 다양한 크기로 자주 일어나는 상황에서 high-order allocation에 대한 가용성을 높임


좀 더 살을 붙이자면:

List-based grouping, ZONE_MOVABLE 둘다 memory compaction처럼 active하게(?) 공격적으로(?) 단편화를 막는 매커니즘은 아니지만, ZONE_MOVABLE은 존 사이의 페이지 마이그레이션이 없다고 할 때 ㅡ list-based grouping에서 서로 다른 migrate type에서 메모리를 빌려오면서 발생하는 단편화가 존재하지 않는다고 할 수 있음. 따라서 list-based grouping보다 더 높은 가용성을 제공함. (대신 관리자가 직접 세팅해줘야하는 단점이 있음)


https://lwn.net/Articles/224829/

https://lwn.net/Articles/224835/

Hence, the two patchsets posted are no longer mutually exclusive and will work together when they are both  applied.  This means that without configuration, external fragmentati…

Like

유형곤
유형곤
Jan 02, 2022

좋은 글이네요!

Like
Wonhyuk Yang
Wonhyuk Yang
Jan 02, 2022
Replying to

많이 부족한 글이지만 감사합니다😊!

Like

Paran Lee
Paran Lee
Apr 23, 2021

https://www.kernel.org/doc/gorman/html/understand/understand009.html



Figure 6.1: Free page block management 그림에서


2^(order) 단위로 관리되는 페이지를 page block 이라고 하는데,


여기서 외부 단편화를 위한 해소를 위한 방안으로,


기존 page block 에 migrate 타입 enum 레이블로 구분할 수 있도록 구현된 건가요?


p.s

댓글에 그림 첨부 너무 좋다..

Like
Wonhyuk Yang
Wonhyuk Yang
Apr 23, 2021
Replying to

해당 자료는 2.4 버전 기준으로 아는데 당시에는 해당 포스트에서 다루는 page block이 도입되기 전이에요.


위 그림에서 표현하는 block은 pages를 뜻하는 정도로 보이므로, 해당 패치에서 도입된 page block과는 조금 차이가 있어보여요

Like
bottom of page