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

v6.18.37 / mm/page_alloc.c

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

## expand

```c

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;
}

```

### 1740행

```c

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

```

zone의 큰 빈 블록 page를 low order까지 나누는 내부 함수입니다. 반환형이 정수인 것은 빈 목록에 추가한 페이지 수를 보고하기 때문입니다.

### 1741행

```c

				  int high, int migratetype)

```

high는 현재 큰 블록의 order이고 migratetype은 나눈 빈 블록을 넣을 목록 종류입니다. low와 high의 단위는 바이트가 아닙니다.

### 1743행

```c

	unsigned int size = 1 << high;

```

2의 high제곱으로 현재 블록의 페이지 수를 구합니다. high=3이면 size=8페이지입니다.

### 1744행

```c

	unsigned int nr_added = 0;

```

빈 목록에 실제 추가한 페이지 수를 0에서 셉니다.

### 1746행

```c

	while (high > low) {

```

현재 order가 필요한 order보다 큰 동안만 분할합니다. 같아지면 더 쪼개지 않습니다.

### 1747행

```c

		high--;

```

한 번 분할하면 각 절반의 order는 1 줄어듭니다.

### 1748행

```c

		size >>= 1;

```

새 절반의 페이지 수로 size를 갱신합니다. 뒤쪽 절반의 시작도 이 수로 찾습니다.

### 1749행

```c

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

```

page[size]가 예상한 zone 범위 안에 있는지 디버그 조건을 검사합니다. 잘못된 경계 계산으로 다른 zone의 메타데이터를 조작하면 안 됩니다.

### 1757행

```c

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

```

뒤쪽 절반을 디버깅용 guard 영역으로 지정할지 판단합니다. 성공하면 일반 할당용 빈 목록에 넣지 않습니다.

### 1758행

```c

			continue;

```

guard로 지정된 절반은 아래 목록 추가와 nr_added 계산을 건너뛰고 다음 분할로 진행합니다.

### 1760행

```c

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

```

뒤쪽 절반을 해당 order와 migratetype의 free list에 넣습니다. false는 목록의 tail에 추가하라는 선택이 아님을 나타냅니다.

### 1761행

```c

		set_buddy_order(&page[size], high);

```

이 절반의 시작 페이지에 buddy order를 기록하여 이후 탐색·병합 시 크기를 알 수 있게 합니다.

### 1762행

```c

		nr_added += size;

```

이번에 빈 목록에 추가한 절반의 페이지 수를 누적합니다.

### 1765행

```c

	return nr_added;

```

실제로 빈 목록에 추가한 페이지 수를 호출자에게 돌려줍니다. guard로 남긴 페이지는 이 값에 들어가지 않습니다.