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

v6.6 / mm/page_alloc.c

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

## expand

```c

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

```

### 1389행

```c

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

```

zone의 큰 빈 블록 page를 나누는 내부 함수입니다. v6.6의 반환형은 void이므로 추가한 페이지 수를 반환하지 않습니다.

### 1390행

```c

	int low, int high, int migratetype)

```

low는 필요한 order, high는 현재 블록의 order이며 migratetype은 빈 목록의 종류를 지정합니다. order의 단위는 바이트가 아닙니다.

### 1392행

```c

	unsigned long size = 1 << high;

```

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

### 1394행

```c

	while (high > low) {

```

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

### 1395행

```c

		high--;

```

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

### 1396행

```c

		size >>= 1;

```

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

### 1397행

```c

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

```

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

### 1405행

```c

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

```

뒤쪽 절반을 디버깅용 guard 영역으로 지정할지 판단합니다. 이 버전은 migratetype도 넘겨 guard 페이지 관련 처리를 진행합니다.

### 1406행

```c

			continue;

```

guard로 지정된 절반은 아래의 일반 빈 목록 추가를 건너뜁니다. v6.6에는 nr_added 카운터가 없습니다.

### 1408행

```c

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

```

뒤쪽 절반을 해당 order와 migratetype의 빈 목록에 추가합니다. 앞쪽 절반은 같은 page 시작점을 유지하며 계속 나눌 수 있습니다.

### 1409행

```c

		set_buddy_order(&page[size], high);

```

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