버디 할당기(buddy allocator)와 버디 메모리 할당 알고리즘이 내부 단편화를 줄이기 위해 어떻게 동작하는지, 그리고 이를 구현하는 방법을 살펴본다.
이전 글에서는 자유 리스트 할당기와, 이것이 보통 연결 리스트 또는 레드-블랙 트리로 어떻게 구현되는지를 다뤘다. 이번 글에서는 버디 알고리즘과, 이것이 메모리 할당 전략에 어떻게 적용되는지를 다룬다.
이전 글에서 레드-블랙 트리 접근법은, 빈 메모리 블록을 찾기 위한 탐색의 시간 복잡도를 개선하고 그 결과로 _best-fit_을 얻는 방법으로 간단히 언급했다. 자유 리스트의 큰 문제 중 하나는, 할당이 임의의 크기일 수 있기 때문에 내부 메모리 단편화에 매우 취약하다는 점이다. 자유 리스트의 성질은 그대로 요구하되 내부 메모리 단편화는 줄이고 싶다면, 버디 알고리즘Wikipedia 문서는 특히 Example 섹션에 있는 기본 표 다이어그램만으로는 이해하기가 그리 쉽지 않다. (Accessed 2021-12-01)도 비슷한 원리로 동작한다.
_버디 알고리즘_은 기반(backing) 메모리 블록의 크기가 바이트 단위에서 2의 거듭제곱이라고 가정한다. 할당 요청이 들어오면, 할당기는 요청된 할당 크기 이상인 크기의 블록을 찾는다(자유 리스트와 유사). 요청된 할당 크기가 해당 블록의 절반보다 작다면, 블록은 두 개(왼쪽과 오른쪽)로 분할되고, 이렇게 생긴 두 블록을 “buddies”Just like Jackie Chan and Chris Tucker in Rush Hour.라고 부른다. 요청된 할당 크기가 왼쪽 버디의 크기의 절반보다 여전히 작다면, 요청된 할당 크기에 맞게 가능한 한 작아질 때까지 버디 블록은 재귀적으로 분할된다.
블록이 해제될 때는, 버디(연속된 인접 블록)들에 대해 병합(coalescence)을 수행할 수 있다. 자유 리스트와 마찬가지로, 특정 조건들이 필요하다. 어떤 블록에 (자유 상태의) 버디가 없거나, 블록이 여전히 사용 중이거나, 버디 블록이 부분적으로 사용 중이라면 병합을 수행할 수 없다.
버디 할당기의 각 블록은 (이전 글의 자유 리스트와 유사하게) _인라인_으로 정보를 저장하는 헤더를 갖는다. 여기에는 블록의 크기와, 자유 상태인지 여부가 저장된다.
typedef struct Buddy_Block Buddy_Block;
struct Buddy_Block { // Allocation header (metadata)
size_t size;
bool is_free;
};
저장된 크기로부터 다음 버디 블록을 직접 계산할 수 있으므로, 다음 버디 블록에 대한 포인터를 저장할 필요는 없다.
Buddy_Block *buddy_block_next(Buddy_Block *block) {
return (Buddy_Block *)((char *)block + block->size);
}
n.b. 버디 할당기의 많은 구현은 여기서 이중 연결 리스트를 사용하고 명시적인 포인터를 저장하는데, 이는 인접한 버디를 병합하고 앞/뒤로 순회하는 일을 더 쉽게 만든다. 하지만 이는 메모리 블록의 할당 헤더 크기를 키운다는 추가 비용이 있다.
위에서 설명했듯이, 가장 잘 맞는 블록을 얻기 위해서는 재귀적 분할 알고리즘이 필요하다. 요청된 크기의 할당에 최적인 크기가 될 때까지 블록을 계속 분할해야 한다.
Buddy_Block *buddy_block_split(Buddy_Block *block, size_t size) {
if (block != NULL && size != 0) {
// Recursive split
while (size < block->size) {
size_t sz = block->size >> 1;
block->size = sz;
block = buddy_block_next(block);
block->size = sz;
block->is_free = true;
}
if (size <= block->size) {
return block;
}
}
// Block cannot fit the requested allocation size
return NULL;
}
요청된 할당 크기에 맞는 자유 블록을 찾는 일은 head와 tail 포인터로 경계가 정해진 (암시적) 연결 리스트를 순회함으로써 달성할 수 있다 꼬리는 단지 기반 메모리 버퍼의 (Buddy_Block *)((char *)data + size)이며, 메모리 경계에 대한 센티널 값을 나타낼 뿐 진짜 블록은 아니다.. 요청된 할당 크기에 대한 블록을 찾을 수 없지만 더 큰 자유 블록이 있다면, 위의 분할 알고리즘을 사용한다. 사용 가능한 자유 블록이 없다면, 아래 절차는 할당기가 (가능성이지만) 메모리가 부족함을 나타내기 위해 NULL을 반환한다 할당기에 남은 메모리가 충분할 수도 있지만, 내부 단편화가 너무 커서 어느 것도 연속(contiguous)하지 않을 수 있다..
Buddy_Block *buddy_block_find_best(Buddy_Block *head, Buddy_Block *tail, size_t size) {
// Assumes size != 0
Buddy_Block *best_block = NULL;
Buddy_Block *block = head; // Left Buddy
Buddy_Block *buddy = buddy_block_next(block); // Right Buddy
// The entire memory section between head and tail is free,
// just call 'buddy_block_split' to get the allocation
if (buddy == tail && block->is_free) {
return buddy_block_split(block, size);
}
// Find the block which is the 'best_block' to requested allocation sized
while (block < tail && buddy < tail) { // make sure the buddies are within the range
// If both buddies are free, coalesce them together
// NOTE: this is an optimization to reduce fragmentation
// this could be completely ignored
if (block->is_free && buddy->is_free && block->size == buddy->size) {
block->size <<= 1
if (size <= block->size && (best_block == NULL || block->size <= best_block->size)) {
best_block = block;
}
block = buddy_block_next(buddy);
if (block < tail) {
// Delay the buddy block for the next iteration
buddy = buddy_block_next(block);
}
continue;
}
if (block->is_free && size <= block->size &&
(best_block == NULL || block->size <= best_block->size)) {
best_block = block;
}
if (buddy->is_free && size <= buddy->size &&
(best_block == NULL || buddy->size < best_block->size)) {
// If each buddy are the same size, then it makes more sense
// to pick the buddy as it "bounces around" less
best_block = buddy;
}
if (block->size <= buddy->size) {
block = buddy_block_next(buddy);
if (block < tail) {
// Delay the buddy block for the next iteration
buddy = buddy_block_next(block);
}
} else {
// Buddy was split into smaller blocks
block = buddy;
buddy = buddy_block_next(buddy);
}
}
if (best_block != NULL) {
// This will handle the case if the 'best_block' is also the perfect fit
return buddy_block_split(best_block, size);
}
// Maybe out of memory
return NULL;
}
이 알고리즘은 과도한 내부 단편화를 겪을 수 있다. 독자를 위한 연습으로, 순회하면서 인접한 자유 버디들을 병합해 볼 수 있다 하나의 버디가 되어, 다른 누군가가 되려 하는 것: https://www.imdb.com/title/tt0120601/.
버디 할당기 자체의 초기화는 비교적 간단하다. 할당기는 세 가지 정보를 저장한다. head 블록(기반 메모리 데이터와 동일한 포인터), 기반 메모리 데이터의 상한 메모리 경계를 나타내는 센티널 포인터 tail ((char *)head + size로, 이는 “진짜” 블록이 아님을 의미한다), 그리고 각 할당의 정렬(alignment)이다. 아래의 buddy_allocator_init 절차는 assert를 사용해 데이터에 대한 몇 가지 작은 검사를 수행한다.
n.b. 이 버디 할당기 구현은 코드를 크게 단순화하기 위해 모든 할당이 동일한 정렬을 가져야 한다. 버디 할당기는 보통 더 복잡한 할당기의 한 부분 전략이므로, 정렬에 대한 이러한 가정은 실제로는 덜 문제가 된다.
typedef struct Buddy_Allocator Buddy_Allocator;
struct Buddy_Allocator {
Buddy_Block *head; // same pointer as the backing memory data
Buddy_Block *tail; // sentinel pointer representing the memory boundary
size_t alignment;
};
void buddy_allocator_init(Buddy_Allocator *b, void *data, size_t size, size_t alignment) {
assert(data != NULL);
assert(is_power_of_two(size) && "size is not a power-of-two");
assert(is_power_of_two(alignment) && "alignment is not a power-of-two");
// The minimum alignment depends on the size of the `Buddy_Block` header
assert(is_power_of_two(sizeof(Buddy_Block)) == 0);
if (alignment < sizeof(Buddy_Block)) {
alignment = sizeof(Buddy_Block);
}
assert((uintptr_t)data % alignment == 0 && "data is not aligned to minimum alignment");
b->head = (Buddy_Block *)data;
b->head->size = size;
b->head->is_free = true;
// The tail here is a sentinel value and not a true block
b->tail = buddy_block_next(b->head);
b->alignment = alignment;
}
할당은 이제 나머지를 이미 설정했으므로 비교적 직관적이다. 먼저 요청된 할당 크기를 늘려 헤더를 수용하고, 최적 블록을 찾기 전에 앞으로 정렬해야 한다. 하나를 찾았다면, 헤더에서 사용 가능한 데이터로 오프셋을 적용해야 한다. 블록을 찾을 수 없다면, 더 이상 병합할 수 없을 때까지 모든 자유 블록을 계속 병합한 뒤 다시 사용 가능한 블록을 찾아본다. 그래도 블록이 없다면, 이 특정 할당기에서 메모리가 부족하다는 뜻으로 NULL을 반환한다.
size_t buddy_block_size_required(Buddy_Allocator *b, size_t size) {
size_t actual_size = b->alignment;
size += sizeof(Buddy_Block);
size = align_forward_size(size, b->alignment);
while (size > actual_size) {
actual_size <<= 1;
}
return actual_size;
}
void buddy_block_coalescence(Buddy_Block *head, Buddy_Block *tail) {
for (;;) {
// Keep looping until there are no more buddies to coalesce
Buddy_Block *block = head;
Buddy_Block *buddy = buddy_block_next(block);
bool no_coalescence = true;
while (block < tail && buddy < tail) { // make sure the buddies are within the range
if (block->is_free && buddy->is_free && block->size == buddy->size) {
// Coalesce buddies into one
block->size <<= 1;
block = buddy_block_next(block);
if (block < tail) {
buddy = buddy_block_next(block);
no_coalescence = false;
}
} else if (block->size < buddy->size) {
// The buddy block is split into smaller blocks
block = buddy;
buddy = buddy_block_next(buddy);
} else {
block = buddy_block_next(buddy);
if (block < tail) {
// Leave the buddy block for the next iteration
buddy = buddy_block_next(block);
}
}
}
if (no_coalescence) {
return;
}
}
}
void *buddy_allocator_alloc(Buddy_Allocator *b, size_t size) {
if (size != 0) {
size_t actual_size = buddy_block_size_required(b, size);
Buddy_Block *found = buddy_block_find_best(b->head, b->tail, actual_size);
if (found == NULL) {
// Try to coalesce all the free buddy blocks and then search again
buddy_block_coalescence(b->head, b->tail);
found = buddy_block_find_best(b->head, b->tail, actual_size);
}
if (found != NULL) {
found->is_free = false;
return (void *)((char *)found + b->alignment);
}
// Out of memory (possibly due to too much internal fragmentation)
}
return NULL;
}
이 할당 알고리즘의 일반적인 시간 복잡도는 평균적으로 _O(N)_이지만, 공간 복잡도는 _O(log N)_이다.
n.b. 버디 할당기는 여전히 내부 단편화에 취약하다. 일반적인 자유 리스트 할당기보다는 덜하지만, 2의 거듭제곱 제약 때문에 실제로는 그 심각도가 덜하다.
이 알고리즘에서 메모리 해제는 매우 간단한데, 전달된 포인터 앞에 저장된 헤더를 자유 상태로 표시하기만 하면 되기 때문이다.
void buddy_allocator_free(Buddy_Allocator *b, void *data) {
if (data != NULL) {
Buddy_Block *block;
assert(b->head <= data);
assert(data < b->tail);
block = (Buddy_Block *)((char *)data - b->alignment);
block->is_free = true;
// NOTE: Coalescence could be done now but it is optional
// buddy_block_coalescence(b->head, b->tail);
}
}
메모리 해제의 일반적인 시간 복잡도는 _O(1)_이다. 원한다면 내부 단편화를 최소화하는 데 도움이 되도록 이 free 직후에 buddy_block_coalescence를 수행할 수 있다.
버디 할당기는 강력한 할당기이며 개념적으로 단순한 알고리즘이지만, 이를 효율적으로 구현하는 것은 이 시리즈에서 논의했던 이전의 모든 할당기들보다 훨씬 더 어렵다.
다음 글들에서는 가상 메모리에 대해 많이 다룰 것이다. 가상 메모리가 어떻게 동작하는지, 이를 어떻게 활용할 수 있는지, 그리고 그 이점이 무엇인지에 대해 이야기하겠다.