선형/아레나 할당자의 기본 개념, 정렬(alignment), 그리고 실용적인 C 구현(초기화·할당·리사이즈·전체 해제)까지 다룬다.
내가 다룰 첫 번째 메모리 할당 전략은 가장 단순한 것들 중 하나이기도 한 선형 할당(linear allocation)이다. 이름이 시사하듯, 메모리는 선형으로 할당된다. 이 시리즈 전반에서 나는 이 메모리를 할당하기 위한 수단으로서 _allocator_라는 개념을 사용할 것이다. 선형 할당자는 Arena 또는 Region-based allocator 같은 다른 이름으로도 알려져 있다. 이 글에서는 이 할당자를 _Arena_라고 부르겠다.
아레나의 로직은 마지막 할당의 끝을 나타내기 위한 오프셋(또는 포인터)만 있으면 된다. 그 외에도 이전 할당의 시작 오프셋이나 할당 횟수 같은 데이터가 저장될 수도 있다.
아레나에서 메모리를 할당하려면 오프셋(또는 포인터)을 앞으로 이동시키기만 하면 된다. Big-O 표기법으로 할당의 복잡도는 O(1) (상수)이다.
가능한 한 가장 단순한 할당자이기 때문에, 아레나 할당자는 사용자가 특정 메모리 블록만 해제하는 것을 허용하지 않는다. 보통 메모리는 한 번에 전부 해제된다.
Note: 다음 코드 예제는 C로 작성된다.
가장 단순한 아레나 할당자는 이런 형태일 수도 있다:
static unsigned char *arena_buffer;
static size_t arena_buffer_length;
static size_t arena_offset;
void *arena_alloc(size_t size) {
// Check to see if the backing memory has space left
if (arena_offset+size <= arena_buffer_length) {
void *ptr = &arena_buffer[arena_offset];
arena_offset += size;
// Zero new memory by default
memset(ptr, 0, size);
return ptr;
}
// Return NULL if the arena is out of memory
return NULL;
}
알 수 있듯이, 이보다 더 단순할 수는 없다. 다만 이 기본 접근에는 두 가지 문제가 있다:
첫 번째 문제는 전역 데이터를 구조체로 묶고 그 구조체를 arena_alloc에 전달하면 쉽게 해결된다. 두 번째 문제는 _비정렬 메모리(unaligned memory)_의 기본 이슈를 이해해야 한다.
현대 컴퓨터 아키텍처는 항상 메모리를 “워드 크기”(32비트 머신에서는 4바이트, 64비트 머신에서는 8바이트) 단위로 읽는다. (비정렬 접근을 허용하는 프로세서에서) 비정렬 메모리 접근이 발생하면 프로세서는 여러 개의 “워드”를 읽어야 한다. 이는 비정렬 메모리 접근이 정렬된 메모리 접근보다 훨씬 느릴 수도 있다는 뜻이다. 이 시리즈에서 메모리 정렬에 대해 너무 깊게 쓰지는 않겠다. 더 배우고 싶다면 다음 글들을 추천한다:
사실상 모든 아키텍처에서, 어떤 것이 정렬되어야 하는 바이트 수는 2의 거듭제곱(1, 2, 4, 8, 16 등)이어야 한다. 따라서 정렬 값이 2의 거듭제곱인지 확인(assert)하는 절차를 만들어야 한다:
bool is_power_of_two(uintptr_t x) {
return (x & (x-1)) == 0;
}
메모리 주소를 지정된 정렬 값에 맞추는 것은 간단한 모듈로 산술이다. 메모리 주소가 지정된 정렬 값의 배수가 되기 위해 앞으로 몇 바이트를 더 가야 하는지 찾으면 된다.
uintptr_t align_forward(uintptr_t ptr, size_t align) {
uintptr_t p, a, modulo;
assert(is_power_of_two(align));
p = ptr;
a = (uintptr_t)align;
// Same as (p % a) but faster as 'a' is a power of two
modulo = p & (a-1);
if (modulo != 0) {
// If 'p' address is not aligned, push the address to the
// next value which is aligned
p += a - modulo;
}
return p;
}
이제 메모리를 정렬하는 방법을 알았으니, 원래의 arena_alloc을 올바르게 정렬을 지원하도록 업데이트하고 아레나 데이터를 구조체 안에 저장할 수 있다.
typedef struct Arena Arena;
struct Arena {
unsigned char *buf;
size_t buf_len;
size_t prev_offset; // This will be useful for later on
size_t curr_offset;
};
void *arena_alloc_align(Arena *a, size_t size, size_t align) {
// Align 'curr_offset' forward to the specified alignment
uintptr_t curr_ptr = (uintptr_t)a->buf + (uintptr_t)a->curr_offset;
uintptr_t offset = align_forward(curr_ptr, align);
offset -= (uintptr_t)a->buf; // Change to relative offset
// Check to see if the backing memory has space left
if (offset+size <= a->buf_len) {
void *ptr = &a->buf[offset];
a->prev_offset = offset;
a->curr_offset = offset+size;
// Zero new memory by default
memset(ptr, 0, size);
return ptr;
}
// Return NULL if the arena is out of memory (or handle differently)
return NULL;
}
#ifndef DEFAULT_ALIGNMENT
#define DEFAULT_ALIGNMENT (2*sizeof(void *))
#endif
// Because C doesn't have default parameters
void *arena_alloc(Arena *a, size_t size) {
return arena_alloc_align(a, size, DEFAULT_ALIGNMENT);
}
아레나 할당자는 이제 기본적인 용도로는 사용할 수 있지만, 일상적으로 쓰기에 실용적으로 만들어 줄 몇 가지 기능이 빠져 있다. 완전한 아레나 할당자는 다음 절차들을 갖게 된다:
arena_init 사전 할당된 메모리 버퍼로 아레나를 초기화한다arena_alloc 오프셋을 단순히 증가시켜 현재 버퍼 오프셋을 나타낸다arena_free 아무것도 하지 않는다(완전성을 위해 존재)arena_resize 먼저 리사이즈하려는 할당이 바로 이전에 수행된 할당인지 검사하고, 그렇다면 같은 포인터를 반환하면서 버퍼 오프셋을 변경한다. 그렇지 않다면 대신 arena_alloc을 호출한다.arena_free_all 버퍼 오프셋들을 0으로 설정하여 할당자 내부의 모든 메모리를 해제하는 데 사용한다arena_init 절차는 주어진 아레나의 매개변수들을 초기화하기만 한다.
void arena_init(Arena *a, void *backing_buffer, size_t backing_buffer_length) {
a->buf = (unsigned char *)backing_buffer;
a->buf_len = backing_buffer_length;
a->curr_offset = 0;
a->prev_offset = 0;
}
앞서 말했듯이, arena_free는 정말로 아무것도 하지 않는다. 이는 순전히 완전성을 위해 존재한다.
void arena_free(Arena *a, void *ptr) {
// Do nothing
}
아레나에서 할당을 리사이즈하는 것은 때때로 유용하다. 메모리 낭비를 줄이기 위해 prev_offset을 추적하고, 전달된 old_memory가 그 오프셋이 가리키는 것과 같다면 그 메모리 블록을 그대로 리사이즈하는 것이 유용하다.
void *arena_resize_align(Arena *a, void *old_memory, size_t old_size, size_t new_size, size_t align) {
unsigned char *old_mem = (unsigned char *)old_memory;
assert(is_power_of_two(align));
if (old_mem == NULL || old_size == 0) {
return arena_alloc_align(a, new_size, align);
} else if (a->buf <= old_mem && old_mem < a->buf+buf_len) {
if (a->buf+a->prev_offset == old_mem) {
a->curr_offset = a->prev_offset + new_size;
if (new_size > old_size) {
// Zero the new memory by default
memset(&a->buf[a->curr_offset], 0, new_size-old_size);
}
return old_memory;
} else {
void *new_memory = arena_alloc_align(a, new_size, align);
size_t copy_size = old_size < new_size ? old_size : new_size;
// Copy across old memory to the new memory
memmove(new_memory, old_memory, copy_size);
return new_memory;
}
} else {
assert(0 && "Memory is out of bounds of the buffer in this arena");
return NULL;
}
}
// Because C doesn't have default parameters
void *arena_resize(Arena *a, void *old_memory, size_t old_size, size_t new_size) {
return arena_resize_align(a, old_memory, old_size, new_size, DEFAULT_ALIGNMENT);
}
마지막으로, arena_free_all은 버퍼 오프셋들을 0으로 설정하여 할당자 내부의 모든 메모리를 해제하는 데 사용된다. 이는 사이클/프레임 단위로 리셋하고 싶을 때 매우 유용하다.
void arena_free_all(Arena *a) {
a->curr_offset = 0;
a->prev_offset = 0;
}
이 할당자를 사용하려면 뒷받침(backing) 메모리를 제공해야 한다. 간단한 접근은 배열을 제공하는 것이다:
unsigned char backing_buffer[256];
Arena a = {0};
arena_init(&a, backing_buffer, 256);
다른 접근은 malloc을 사용하는 것이다:
void *backing_buffer = malloc(256);
Arena a = {0};
arena_init(&a, backing_buffer, 256);
이제 아주 첫 번째 커스텀 할당자를 구현했다! 전체 소스 코드는 여기에서 확인할 수 있다.
다음 글에서는 _아레나 할당자_가 스택 할당자로 발전하는 기본적인 과정을 이야기할 것이다.
추가 기능 하나로 임시 아레나 메모리 _세이브포인트(savepoint)_를 더할 수 있다. 이는 아레나에서 아주 짧은 기간 동안만 메모리를 사용한 뒤, 이전에 저장해 둔 지점으로 되돌리고 싶을 때 매우 유용하다.
typedef struct Temp_Arena_Memory Temp_Arena_Memory;
struct Temp_Arena_Memory {
Arena *arena;
size_t prev_offset;
size_t curr_offset;
};
Temp_Arena_Memory temp_arena_memory_begin(Arena *a) {
Temp_Arena_Memory temp;
temp.arena = a;
temp.prev_offset = a->prev_offset;
temp.curr_offset = a->curr_offset;
return temp;
}
void temp_arena_memory_end(Temp_Arena_Memory temp) {
temp.arena->prev_offset = temp.prev_offset;
temp.arena->curr_offset = temp.curr_offset;
}