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

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

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

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

먼저 알아둘 개념

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 page가 일반 free list에 추가되지 않을 때 nr_added가 어떻게 달라지는지 계산해 보세요. 반환값은 처음 큰 블록 크기가 아니라 실제 추가한 페이지 수입니다.

그림으로 보는 변화

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.18.37 원문 기준입니다. 주석·빈 줄을 포함한 함수 전체를 먼저 보고, 그 아래에서 각 줄을 설명합니다.

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

	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))
			continue;

		__add_to_free_list(&page[size], zone, high, migratetype, false);
		set_buddy_order(&page[size], high);
		nr_added += size;
	}

	return nr_added;
}

static inline unsigned int expand(struct zone *zone, struct page *page, int low,

				  int high, int migratetype)

	unsigned int size = 1 << high;

	unsigned int nr_added = 0;

	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))

			continue;

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

		set_buddy_order(&page[size], high);

		nr_added += size;

	return nr_added;

함께 생각해 볼 질문

출처와 읽은 범위

Linux stable v6.18.37 · mm/page_alloc.c

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