buddy allocator: 큰 빈 블록을 반씩 나누기

이 코드는 어떤 문제를 푸나요?

요청한 크기의 빈 블록이 없다면 더 큰 블록을 쪼개서 사용할 수 있습니다. buddy의 order는 바이트 크기가 아니라 2의 몇 제곱 개 페이지인지를 나타냅니다. expand는 큰 블록의 앞부분을 계속 남겨 두면서 뒤쪽 절반들을 빈 목록에 돌려놓습니다.

읽을 범위: v6.6 · mm/page_alloc.c · expand 1389–1411행입니다. 아래에 이 범위의 원문과 각 줄의 설명을 실었습니다. 주제 전체의 흐름과 다른 경로는 기존 분석에서 함께 읽으실 수 있습니다.

먼저 알아둘 개념

order

order n의 블록은 2^n개 페이지입니다. 페이지가 4 KiB인 예에서 order 3은 8페이지, 32 KiB입니다. 페이지 크기는 커널 구성에 따라 달라집니다.

buddy

같은 크기로 나눈 두 절반은 서로 buddy입니다. 임의의 인접 빈 페이지 두 개가 항상 합쳐질 수 있는 것은 아니며 주소 정렬과 order가 맞아야 합니다.

migratetype

비슷한 이동 가능성을 가진 페이지를 모아 단편화를 줄이려는 분류입니다. 이 함수는 분할한 빈 절반을 해당 종류의 목록에 넣습니다.

처음 읽을 때

8페이지 블록에서 2페이지가 필요하다고 가정해 보세요. 8을 4+4로 나누고, 앞의 4를 다시 2+2로 나누면 요청한 2페이지와 빈 4·2페이지 블록이 남습니다.

더 깊이 살펴볼 때

guard로 지정된 절반이 일반 free list에 들어가지 않는 이유와 set_page_guard의 migratetype 인자를 살펴보세요. v6.6 expand는 void 함수이므로 상태 변경을 추적해야 하며 최신 버전의 반환값 설명을 적용하지 않습니다.

그림으로 보는 변화

GIF 재생1단계 · 멈춰 보기2단계 · 멈춰 보기3단계 · 멈춰 보기

1단계 고정

GIF 원본 열기

1. 큰 빈 블록 선택

예시 high=3: 8페이지

화살표는 분할 순서를 뜻합니다. 예시는 low=1, guard page를 쓰지 않는 경우입니다.

2. 절반을 빈 목록에 반환

8 → 4 + 4, 뒤의 4를 free list에 추가

주소가 증가하는 쪽의 절반 page[size]를 반환합니다. 원래 시작 page는 유지합니다.

3. 필요한 크기까지 반복

앞의 4 → 2 + 2, 뒤의 2를 반환

남은 앞의 2페이지가 요청 크기입니다. 일반 빈 목록에 더한 양은 예시에서 4+2=6페이지지만 이 버전 함수의 반환값은 없습니다.

expand를 한 줄씩 읽기

줄 번호는 v6.6 원문 기준입니다. 주석·빈 줄을 포함한 함수 전체를 먼저 보고, 그 아래에서 각 줄을 설명합니다.

static inline void expand(struct zone *zone, struct page *page,
	int low, int high, int migratetype)
{
	unsigned long size = 1 << high;

	while (high > low) {
		high--;
		size >>= 1;
		VM_BUG_ON_PAGE(bad_range(zone, &page[size]), &page[size]);

		/*
		 * Mark as guard pages (or page), that will allow to
		 * merge back to allocator when buddy will be freed.
		 * Corresponding page table entries will not be touched,
		 * pages will stay not present in virtual address space
		 */
		if (set_page_guard(zone, &page[size], high, migratetype))
			continue;

		add_to_free_list(&page[size], zone, high, migratetype);
		set_buddy_order(&page[size], high);
	}
}

static inline void expand(struct zone *zone, struct page *page,

	int low, int high, int migratetype)

	unsigned long size = 1 << high;

	while (high > low) {

		high--;

		size >>= 1;

		VM_BUG_ON_PAGE(bad_range(zone, &page[size]), &page[size]);

		if (set_page_guard(zone, &page[size], high, migratetype))

			continue;

		add_to_free_list(&page[size], zone, high, migratetype);

		set_buddy_order(&page[size], high);

함께 생각해 볼 질문

출처와 읽은 범위

Linux stable v6.6 · mm/page_alloc.c

해당 버전 원본 파일 · 기존 코드 분석 · 설명 원고