스택(후입선출) 방식의 메모리 할당기 개념, 헤더 저장 방식, 느슨한/작은 스택 할당기의 구현과 LIFO 강제 방법을 다룬다.
이전 글에서는 모든 메모리 할당기 중 가장 단순한 선형/아레나 할당기를 살펴보았다. 이 글에서는 고정 크기의 스택-유사 할당기를 다룰 것이다. 이 글 전체에서 이 할당기를 _스택 할당기_라고 부르겠다.
Note: 스택-유사 할당기란, 후입선출 (LIFO) 원칙을 따르는 자료구조처럼 동작하는 할당기를 의미한다. 이는 스택 또는 _스택 프레임_과는 아무 관련이 없다.
스택 할당기는 아레나 할당기에서 자연스럽게 진화한 형태다. 스택 할당기의 접근 방식은 LIFO 원칙을 따르며 스택처럼 메모리를 관리하는 것이다. 따라서 책 더미처럼, 더미 위에 먼저 올려둔 것이 있다면 그 아래의 책을 집어 들기 전에 위에 있는 책을 먼저 들어 올려야 한다.
아레나 할당기와 마찬가지로 메모리 블록에 대한 오프셋을 저장해 두고, 할당할 때마다 그 오프셋을 앞으로 이동시킨다. 차이점은 메모리를 _해제_할 때 오프셋을 뒤로도 이동시킬 수 있다는 점이다. 아레나에서는 한 번에 전체 메모리만 해제할 수 있었다.
이전 글의 확장 아레나와 마찬가지로, 이전 할당의 오프셋을 추적해야 한다. 이는 _할당 단위(per-allocation)_로 메모리를 해제하기 위해 필요하다. 한 가지 접근은 해당 할당에 대한 정보를 저장하는 _헤더_를 저장하는 것이다. 이 헤더 덕분에 할당기는 그 메모리를 해제하기 위해 오프셋을 얼마나 뒤로 이동해야 하는지 알 수 있다.
스택 할당기에서 메모리를 할당하는 것은 아레나 할당기와 같이, 헤더를 고려하면서 오프셋을 앞으로 이동시키는 것만큼 간단하다. Big-O 표기법으로 할당의 복잡도는 O(1) (상수)이다.
블록을 해제할 때는 메모리 블록 앞에 저장된 헤더를 읽어 오프셋을 뒤로 이동시킬 수 있다. Big-O 표기법으로 이 메모리 해제의 복잡도는 O(1) (상수)이다.
할당 헤더에 무엇을 저장할지 실제로는 한 번도 명시하지 않았다는 것을 눈치챘을지도 모른다. 그 이유는 서로 다른 데이터를 저장하는, 스택 할당기에 대한 접근 방식이 여럿 존재하기 때문이다. 주요 접근은 세 가지다.
이 글에서는 처음 두 가지 접근을 다룰 것이다. 첫 번째는 헤더에 아주 적은 정보만 저장하므로 느슨한 스택(loose stack) 또는 _작은 스택(small stack)_이라고 부르겠다. 세 번째 접근은 할당의 크기를 동적으로 질의하고 싶을 때 유용하지만, 나는 보통 할당 크기를 수동으로 추적하기 때문에 거의 필요하지 않다.
스택 할당기는 할당 단위로 메모리를 해제할 수 있다는 점을 제외하면 여러 면에서 아레나 할당기처럼 동작한다. 완전한 스택 할당기는 다음 절차들을 가진다:
stack_init 미리 할당된 메모리 버퍼로 스택을 초기화stack_alloc 할당 헤더를 고려하면서 현재 버퍼 오프셋을 나타내도록 오프셋을 증가stack_free 전달된 메모리를 해제하고 해당 메모리를 _해제_하도록 오프셋을 감소stack_resize 먼저 리사이즈하려는 할당이 직전에 수행된 할당인지 확인하고, 그렇다면 같은 포인터를 반환하면서 버퍼 오프셋을 변경한다. 그렇지 않으면 stack_alloc을 대신 호출한다.stack_free_all 버퍼 오프셋을 0으로 설정하여 할당기 내부의 모든 메모리를 해제하는 데 사용(느슨한/작은) 스택 자료구조는 아레나와 동일한 정보를 담고 있다.
typedef struct Stack Stack;
struct Stack {
unsigned char *buf;
size_t buf_len;
size_t offset;
};
이 특정 스택 구현의 할당 헤더는 패딩을 인코딩하기 위해 정수를 사용한다.
typedef struct Stack_Allocation_Header Stack_Allocation_Header;
struct Stack_Allocation_Header {
uint8_t padding;
};
이 패딩은 새 할당이 올바르게 정렬(aligned)되도록 하기 위해, 헤더 앞에 배치되어야 하는 바이트 수를 저장한다.
Note: 패딩을 바이트로 저장하면, 이 스택 할당기에서 사용할 수 있는 최대 정렬이 128바이트로 제한된다. 더 높은 정렬이 필요하다면 패딩을 저장하는 데 사용하는 정수의 크기를 늘려라. 패딩이 지원할 수 있는 최대 정렬을 계산하려면 다음 식을 사용하라:
Maximum Alignment in Bytes=2 8×sizeof(padding)−1
stack_init 절차는 주어진 스택에 대해 매개변수들을 초기화하기만 한다.
void stack_init(Stack *s, void *backing_buffer, size_t backing_buffer_length) {
s->buf = (unsigned char *)backing_buffer;
s->buf_len = backing_buffer_length;
s->offset = 0;
}
아레나와 달리, 스택 할당기는 할당과 함께 헤더가 필요하다. 앞서 말했듯이 calc_padding_with_header 절차는 이전 글의 align_forward 절차와 비슷하지만, 헤더와 요청된 정렬을 기준으로 얼마나 많은 공간이 필요한지 결정한다. 헤더에는 패딩의 양을 저장해야 하고, 그 헤더 뒤의 주소를 반환해야 한다.
size_t calc_padding_with_header(uintptr_t ptr, uintptr_t alignment, size_t header_size) {
uintptr_t p, a, modulo, padding, needed_space;
assert(is_power_of_two(alignment));
p = ptr;
a = alignment;
modulo = p & (a-1); // (p % a) as it assumes alignment is a power of two
padding = 0;
needed_space = 0;
if (modulo != 0) { // Same logic as 'align_forward'
padding = a - modulo;
}
needed_space = (uintptr_t)header_size;
if (padding < needed_space) {
needed_space -= padding;
if ((needed_space & (a-1)) != 0) {
padding += a * (1+(needed_space/a));
} else {
padding += a * (needed_space/a);
}
}
return (size_t)padding;
}
void *stack_alloc_align(Stack *s, size_t size, size_t alignment) {
uintptr_t curr_addr, next_addr;
size_t padding;
Stack_Allocation_Header *header;
assert(is_power_of_two(alignment));
if (alignment > 128) {
// As the padding is 8 bits (1 byte), the largest alignment that can
// be used is 128 bytes
alignment = 128;
}
curr_addr = (uintptr_t)s->buf + (uintptr_t)s->offset;
padding = calc_padding_with_header(curr_addr, (uintptr_t)alignment, sizeof(Stack_Allocation_Header));
if (s->offset + padding + size > s->buf_len) {
// Stack allocator is out of memory
return NULL;
}
s->offset += padding;
next_addr = curr_addr + (uintptr_t)padding;
header = (Stack_Allocation_Header *)(next_addr - sizeof(Stack_Allocation_Header));
header->padding = (uint8_t)padding;
s->offset += size;
return memset((void *)next_addr, 0, size);
}
// Because C does not have default parameters
void *stack_alloc(Stack *s, size_t size) {
return stack_alloc_align(s, size, DEFAULT_ALIGNMENT);
}
stack_free에서는 전달된 포인터가 유효한지(즉, 이 할당기에 의해 할당되었는지) 확인해야 한다. 유효하다면 이 할당의 헤더를 얻을 수 있다는 의미다. 약간의 _포인터 산술(pointer arithmetic)_을 사용하면, 전달된 포인터 이전의 할당으로 오프셋을 재설정할 수 있다.
void stack_free(Stack *s, void *ptr) {
if (ptr != NULL) {
uintptr_t start, end, curr_addr;
Stack_Allocation_Header *header;
size_t prev_offset;
start = (uintptr_t)s->buf;
end = start + (uintptr_t)s->buf_len;
curr_addr = (uintptr_t)ptr;
if (!(start <= curr_addr && curr_addr < end)) {
assert(0 && "Out of bounds memory address passed to stack allocator (free)");
return;
}
if curr_addr >= start+(uintptr_t)s->offset {
// Allow double frees
return;
}
header = (Stack_Allocation_Header *)(curr_addr - sizeof(Stack_Allocation_Header));
prev_offset = (size_t)(curr_addr - (uintptr_t)header->padding - start);
s->offset = prev_offset;
}
}
할당을 리사이즈하는 것은 스택 할당기에서 때때로 유용하다. 이 특정 버전에서는 이전 오프셋을 저장하지 않으므로, 할당 크기를 변경해야 한다면 새 메모리를 다시 할당할 것이다. 만약 이전 할당이었을 때 더 많은 메모리를 할당하지 않고도 이를 더 효율적으로 만드는 방법을 찾아보는 것은 독자의 연습 문제로 남겨 두겠다.
void *stack_resize_align(Stack *s, void *ptr, size_t old_size, size_t new_size, size_t alignment) {
if (ptr == NULL) {
return stack_alloc_align(s, new_size, alignment);
} else if (new_size == 0) {
stack_free(s, ptr);
return NULL;
} else {
uintptr_t start, end, curr_addr;
size_t min_size = old_size < new_size ? old_size : new_size;
void *new_ptr;
start = (uintptr_t)s->buf;
end = start + (uintptr_t)s->buf_len;
curr_addr = (uintptr_t)ptr;
if (!(start <= curr_addr && curr_addr < end)) {
assert(0 && "Out of bounds memory address passed to stack allocator (resize)");
return NULL;
}
if (curr_addr >= start + (uintptr_t)s->offset) {
// Treat as a double free
return NULL;
}
if old_size == size {
return ptr;
}
new_ptr = stack_alloc_align(s, new_size, alignment);
memmove(new_ptr, ptr, min_size);
return new_ptr;
}
}
void *stack_resize(Stack *s, void *ptr, size_t old_size, size_t new_size) {
return stack_resize_align(s, ptr, old_size, new_size, DEFAULT_ALIGNMENT);
}
마지막으로 stack_free_all은 버퍼 오프셋을 0으로 설정하여 할당기 내부의 모든 메모리를 해제하는 데 사용된다. 이는 사이클/프레임 단위로 리셋하고 싶을 때 매우 유용하다. 이 경우 아레나와 완전히 동일하게 동작한다.
void stack_free_all(Stack *s) {
s->offset = 0;
}
위의 느슨한/작은 스택 할당기는 이미 매우 유용하지만, 해제에 대해 LIFO 원칙을 강제하지는 않는다. 사용자가 어떤 순서로든 임의의 메모리 블록을 해제할 수 있게 허용하지만, 그 블록 이후에 할당된 모든 것을 함께 해제해 버린다. LIFO 원칙을 강제하려면 이전 오프셋에 대한 데이터를 헤더와 일반 자료구조에 저장해야 한다.
struct Stack_Allocation_Header {
size_t prev_offset;
size_t padding;
};
struct Stack {
unsigned char *buf;
size_t buf_len;
size_t prev_offset;
size_t curr_offset;
};
이 새로운 헤더는 단순 패딩 접근에 비해 훨씬 더 크다. 더 작은 정수를 사용하면 헤더 크기를 줄일 수는 있지만, 그만큼 사용할 수 있는 할당의 크기도 줄어든다. 하지만 그 대신, 해제에서 LIFO를 강제할 수 있게 된다. 코드에는 몇 가지 조정만 필요하다. 리사이즈 절차는 독자의 연습 문제로 남겨 둔다.
stack_alloc_align...
s->prev_offset = s->offset; // Store the previous offset
s->offset += padding;
next_addr = curr_addr + (uintptr_t)padding;
header = (Stack_Allocation_Header *)(next_addr - sizeof(Stack_Allocation_Header));
header->padding = padding;
header->prev_offset = s->prev_offset; // store the previous offset in the header
s->offset += size;
stack_free...
header = (Stack_Allocation_Header *)(curr_addr - sizeof(Stack_Allocation_Header));
// Calculate previous offset from the header and its address
prev_offset = (size_t)(curr_addr - (uintptr_t)header->padding - start);
if (prev_offset != header->prev_offset) {
assert(0 && "Out of order stack allocator free");
return;
}
// Reset the offsets to the previous allocation
s->curr_offset = s->prev_offset;
s->prev_offset = header->prev_offset;
스택 할당기는 할당에 대해 _헤더_라는 개념을 사용하는 많은 할당기들 중 첫 번째다. 이 기본 형태의 스택 할당기에서는, LIFO 동작을 강제하고 싶지 않다면 개인적으로는 대신 Temp_Arena_Memory 구성체를 갖춘 아레나 할당기를 쓰는 것을 권장한다. 하지만 C++의 생성자와 소멸자 같은 것이 필요하다면, 스택 할당기가 해당 프레임워크(RAII)에 더 친화적일 것이다 (RAII)https://wikipedia.org/wiki/Placement_syntax.
스택 할당기는 두 개의 서로 다른 오프셋을 두는 방식으로 더 확장할 수도 있다. 하나는 시작 지점에서 출발해 앞으로 증가하고, 다른 하나는 끝에서 출발해 뒤로 증가한다. 이를 양끝 스택(double-ended stack)이라고 하며, (오프셋이 서로 겹치지 않는 한) 단편화를 극도로 낮게 유지하면서 메모리 사용량을 최대화할 수 있다.
다음 글에서는 _풀 할당기(pool allocators)_와, 같은 크기의 것들을 완전히 임의의 순서로 생성하고 파괴하는 데 그것들이 얼마나 유용한지에 대해 다룰 것이다.