메모리 할당 전략 - 파트 4

Pool Allocators

풀 기반 할당

이전 글에서는 스택 할당자를 살펴보았는데, 이는 선형/아레나 할당자의 자연스러운 진화였다. 이 글에서는 고정 크기의 _풀 할당자_를 다룬다.

풀 할당자는 내가 앞서 다뤘던 할당 전략들과는 조금 다르다. 풀은 제공된 백킹 버퍼를 동일한 크기의 _청크_로 나누고, 그 청크들 중 어떤 것이 비어 있는지 추적한다. 할당이 필요할 때는 비어 있는 청크 하나를 준다. 청크를 해제하려면 그 청크를 빈 청크 목록에 추가한다.

풀 할당자는 같은 크기의 메모리 청크를 할당해야 하고, 그것들이 동적으로 생성·파괴되며, 특히 무작위 순서로 생성·파괴될 수 있을 때 매우 유용하다. 풀은 또한 아레나와 스택이 갖는 장점처럼 단편화가 매우 적고, 할당/해제가 상수 시간 $O(1)$ 로 이뤄진다는 이점도 있다.

풀 할당자는 보통 동일한 수명을 공유하는 “것들(things)”의 _그룹_을 한 번에 할당하는 데 사용된다. 예를 들어 게임에서 엔티티를 배치 단위로 생성하고 파괴하며, 각 배치 안의 엔티티가 동일한 수명을 공유하는 경우가 있을 수 있다.

기본 로직

풀 할당자는 백킹 버퍼를 받아 그 버퍼를 풀/슬롯/빈/청크로 나눈다. 이름이야 무엇이든. 우리가 장미라고 부르는 그것은 다른 이름으로 불러도 똑같이 향기롭다. 로미오와 줄리엣 (II, ii, 1-2) 그리고 이들은 모두 같은 크기다.

문제는 이러한 할당과 해제가 어떻게 결정되느냐는 것이다. 그리고 어떻게 어떤 순서로든 할당할 수 있는데도 단편화가 매우 적게 유지되는가?

프리 리스트

프리 리스트는 메모리 버퍼 안의 빈 슬롯/청크에 대한 연결 리스트를 내부적으로 저장하는 데이터 구조다. 리스트의 노드는 제자리(in-place)로 저장되는데, 이렇게 하면 빈 슬롯을 추적하기 위한 다른 데이터 구조(예: 배열, 리스트 등)가 필요 없다. 데이터는 풀 할당자의 백킹 버퍼 안에만 저장된다.

일반적인 접근은 청크의 시작 부분에 헤더를 저장하는 것이다(스택 할당자처럼 청크 _앞_이 아니라 청크 _안_의 시작). 이 헤더는 다음으로 사용 가능한 빈 청크를 가리킨다. 사용 가능한 빈 청크가 없다면 아무것도 가리키지 않으며(NULL)..

할당과 해제

청크를 할당하려면 프리 리스트의 헤드(첫 요소)를 그냥 pop 하면 된다. 빅 O 표기법으로 할당의 복잡도는 $O(1)$ (상수)이다.

참고: 프리 리스트는 정렬되어 있을 필요가 없으며, 그 순서는 청크가 할당되고 해제되는 방식에 의해 결정된다.

청크를 해제하려면 해제된 청크를 프리 리스트의 헤드로 push 하면 된다. 빅 O 표기법으로 이 메모리 해제의 복잡도는 $O(1)$ (상수)이다.

구현

풀 할당자는 아레나 및 스택 할당자보다 코드가 더 적게 필요한데, 서로 다른 크기/정렬의 할당이나 리사이즈 할당을 위한 로직이 필요 없기 때문이다. 완전한 풀 할당자는 다음 절차들을 갖는다:

• pool_init 미리 할당된 메모리 버퍼로 풀을 초기화
• pool_alloc 프리 리스트에서 헤드를 pop
• pool_free 해제된 청크를 프리 리스트의 헤드로 push
• pool_free_all 풀의 모든 청크를 프리 리스트에 push

데이터 구조

풀 데이터 구조는 백킹 버퍼, 각 청크의 크기, 그리고 프리 리스트의 헤드를 포함한다.

typedef struct Pool Pool;
struct Pool {
	unsigned char *buf;
	size_t buf_len;
	size_t chunk_size;

	Pool_Free_Node *head; // Free List Head
};

프리 리스트의 각 노드는 다음 빈 청크를 가리키는 포인터만 담고 있으며, 테일(마지막 요소)이라면 NULL일 수 있다.

typedef struct Pool_Free_Node Pool_Free_Node;
struct Pool_Free_Node {
	Pool_Free_Node *next;
};

초기화

풀 초기화는 꽤 간단하다. 다만 각 청크가 같은 크기와 정렬을 갖기 때문에, 이 로직을 나중이 아니라 지금 수행할 수 있다.

void pool_free_all(Pool *p); // This procedure will be covered later in this article

void pool_init(Pool *p, void *backing_buffer, size_t backing_buffer_length,
               size_t chunk_size, size_t chunk_alignment) {
	// Align backing buffer to the specified chunk alignment
	uintptr_t initial_start = (uintptr_t)backing_buffer;
	uintptr_t start = align_forward_uintptr(initial_start, (uintptr_t)chunk_alignment);
	backing_buffer_length -= (size_t)(start-initial_start);

	// Align chunk size up to the required chunk_alignment
	chunk_size = align_forward_size(chunk_size, chunk_alignment);

	// Assert that the parameters passed are valid
	assert(chunk_size >= sizeof(Pool_Free_Node) &&
	       "Chunk size is too small");
	assert(backing_buffer_length >= chunk_size &&
	       "Backing buffer length is smaller than the chunk size");

	// Store the adjusted parameters
	p->buf = (unsigned char *)backing_buffer;
	p->buf_len = backing_buffer_length;
	p->chunk_size = chunk_size;
	p->head = NULL; // Free List Head

	// Set up the free list for free chunks
	pool_free_all(p);
}

할당

pool_alloc 절차는 각 청크가 같은 크기와 정렬을 가지므로 다른 할당자들보다 훨씬 단순하며, 따라서 이 매개변수들을 절차에 전달할 필요가 없다. 프리 리스트에서 가장 최근의 빈 청크를 pop 한 다음 새 할당으로 사용한다.

void *pool_alloc(Pool *p) {
	// Get latest free node
	Pool_Free_Node *node = p->head;

	if (node == NULL) {
		assert(0 && "Pool allocator has no free memory");
		return NULL;
	}

	// Pop free node
	p->head = p->head->next;

	// Zero memory by default
	return memset(node, 0, p->chunk_size);
}

해제

할당을 해제하는 것은 할당의 거의 정반대다. 해제할 청크를 프리 리스트에 push 한다.

void pool_free(Pool *p, void *ptr) {
	Pool_Free_Node *node;

	void *start = p->buf;
	void *end = &p->buf[p->buf_len];

	if (ptr == NULL) {
		// Ignore NULL pointers
		return;
	}

	if (!(start <= ptr && ptr < end)) {
		assert(0 && "Memory is out of bounds of the buffer in this pool");
		return;
	}

	// Push free node
	node = (Pool_Free_Node *)ptr;
	node->next = p->head;
	p->head = node;
}

모두 해제

모든 메모리를 해제하는 것은 모든 청크를 프리 리스트에 push 하는 것과 동일하다.

void pool_free_all(Pool *p) {
	size_t chunk_count = p->buf_len / p->chunk_size;
	size_t i;

	// Set all chunks to be free
	for (i = 0; i < chunk_count; i++) {
		void *ptr = &p->buf[i * p->chunk_size];
		Pool_Free_Node *node = (Pool_Free_Node *)ptr;
		// Push free node onto thte free list
		node->next = p->head;
		p->head = node;
	}
}

결론

풀 할당자는 “것들(things)”을 청크 단위로 할당해야 하고, 그 청크 안의 것들이 동일한 수명을 공유할 때 매우 유용한 할당자다. 전체 소스 코드는 여기에서 확인할 수 있다.

다음 글에서는 프리 리스트 메모리 할당자를 논의하겠다.