Arenas를 사용한 더 쉬운 객체 관리
Source: Dev.to
(번역을 진행하려면 번역하고자 하는 전체 텍스트를 제공해 주세요.)
Source:
Introduction
제가 Cdecl 업데이트를 시작했을 때, 가장 먼저 한 일은 선언을 나타내기 위해 abstract syntax tree (AST) 데이터 구조를 사용하는 것이었습니다.
AST를 구성하는 과정에서 최종 타입이 결정될 때까지 자리표시자 노드를 생성해야 할 때가 있습니다. 예를 들어, 다음 선언을 생각해 보세요:
int a[2][3];파싱 중에 첫 번째 [를 만나면 “int”의 무언가에 대한 배열 2임을 알지만, 그 “무언가”가 무엇인지 혹은 아무것도 아닌지 아직 알 수 없습니다. 두 번째 [를 만나야 비로소 배열 2의 배열 3이 int임을 알게 됩니다. ([3]이 없었다면 단순히 배열 2 of int가 되었을 것입니다.)
최종 타입이 확정되면, 자리표시자 노드를 올바른 타입의 새로운 노드로 교체하면 됩니다.
대부분의 경우 자리표시자 노드에 free를 호출하면 된다고 생각할 수 있습니다. 그렇게 할 수도 있지만, 그 경우 트리 안뿐만 아니라 호출 스택에 있는 함수들의 스택 프레임에 있는 로컬 변수들에서도 해당 노드를 가리키는 포인터가 없도록 보장해야 합니다. 그렇지 않으면 dangling pointer 문제가 발생할 수 있습니다. 더 간단한 방법은 arenas를 사용하는 것입니다.
Arenas
arena는 일반적으로 실제 관심 객체가 이후에 사용자 정의 할당자를 사용해 할당되는, 동적으로 할당된 큰 메모리 청크를 의미합니다. 다음 질문에 대한 답에 따라 아레나를 구현하는 방법은 다양합니다:
- 그 안에서 할당될 모든 객체가 동일한 타입(또는 최소한 동일한 크기)일까요, 아니면 서로 다른 타입(또는 크기)일까요?
- 할당될 객체의 최대 개수를 미리 알 수 있을까요?
- 그렇지 않다면, 필요에 따라 아레나를 확장해야 할까요?
- 개별 객체를 아레나에서 해제해야 할까요?
- 스레드‑안전성이 필요할까요? (프로그램이 스레드를 사용하지 않는다면 답은 “아니오”입니다.)
모든 아레나 구현이 공통적으로 갖는 유일한 점은 아레나를 해제하면 그 안에 있는 모든 객체가 해제된다는 것이며, 이는 아레나를 처음 사용하는 주요 이유 중 하나입니다.
Cdecl을 위한 아레나
Cdecl의 경우, 앞서 질문들에 대한 답은 다음과 같습니다:
- Yes. (모든 객체가 AST 노드입니다.)
- No. (객체의 최대 개수를 알 수 없습니다.)
- Yes. (필요에 따라 아레나가 성장해야 합니다.)
- No. (개별 객체를 해제할 필요가 없습니다.)
- No. (스레드‑안전할 필요가 없습니다.)
위와 같은 답변을 바탕으로, 단순한 단일 연결 리스트만으로 충분합니다:
typedef struct slist slist;
struct slist {
slist *next;
void *data;
};
void slist_push_front(slist **phead, void *data) {
slist *const new = malloc(sizeof *new);
assert(new != NULL);
*new = (slist){ .next = *phead, .data = data };
*phead = new;
}AST 노드를 아레나에 넣기
c_ast_t c_ast_new(/* params */, slist **parena) {
c_ast_t *const ast = malloc(sizeof *ast);
/* ... */
slist_push_front(parena, ast);
return ast;
}모든 AST 노드를 한 번에 해제하기
void slist_cleanup(slist **phead,
void (*free_fn)(void *)) {
slist *node = *phead, *next;
for ( ; node != NULL; node = next ) {
next = node->next;
if (free_fn != NULL)
(*free_fn)(node->data);
free(node);
}
*phead = NULL;
}아레나로서 보면, 연결 리스트는 매우 단순합니다—아레나라고 부르기에도 다소 얇은 감이 있을 수 있습니다. Cdecl의 경우, 이것만으로 충분합니다—과도하게 설계하지 마세요.
더 복잡한 아레나
연결 리스트 위에 약간 더 복잡한 아레나를 만들 수 있습니다. 여기서는 각 노드가 블록 형태의 객체들을 담습니다. 예를 들어, 첫 번째 블록은 최대 8개의 객체를 저장할 수 있다고 가정합니다. 공간이 부족하면 추가 블록을 할당합니다. 각 블록은 같은 크기이거나 이전 블록 크기의 두 배가 될 수 있으며, 최대 크기까지 제한됩니다:
typedef struct arena arena;
struct arena {
slist *blocks;
size_t block_size_min, block_size_max;
size_t obj_size;
size_t avail;
};
void arena_init(arena *a,
size_t block_size_min,
size_t block_size_max,
size_t obj_size) {
*a = (arena){
.block_size_min = block_size_min,
.block_size_max = block_size_max,
.obj_size = obj_size
};
}블록 정의
typedef struct arena_block arena_block;
struct arena_block {
size_t size;
alignas(max_align_t) char data[];
};유연 배열 멤버(data[])가 객체들을 저장할 공간을 제공합니다.
할당자
void *arena_alloc(arena *a) {
if (a->avail == 0) {
arena_block *block = arena_node2block(a->blocks);
size_t const block_size = block == NULL ?
a->block_size_min :
block_size block_size_max / 2 ?
block_size block_size_max;
block = malloc(sizeof(arena_block) + block_size * a->obj_size);
assert(block != NULL);
a->avail = block->size = block_size;
slist_push_front(&a->blocks, block->data);
}
return &a->blocks->data[--a->avail * a->obj_size];
}a->avail이 0이면 새 블록을 할당해야 합니다:
arena_node2block은 일단 무시하고,block이NULL이면 기존 블록이 없으므로a->block_size_min부터 시작합니다.- 그렇지 않으면 이전 블록 크기의 두 배를 사용하되(
a->block_size_max를 초과하지 않도록) 제한합니다.
새로 할당된 블록은 블록 리스트의 앞에 삽입되고, 할당자는 다음 빈 슬롯에 대한 포인터를 반환합니다.
Source:
Allocation Logic
- 블록이 없을 경우,
block_size는block_size_min이 됩니다. - 그렇지 않고
block_size를 두 배로 늘려도block_size_max를 초과하지 않으면,block_size를 두 배로 늘립니다. - 그 외의 경우에는
block_size_max를 사용합니다.
그 다음 블록 하나와 block_size 개의 객체에 대한 메모리를 할당하고, block이 아니라 data를 블록들의 연결 리스트 머리(head)에 푸시합니다. 이렇게 하면 return 라인에서 수행되는 것처럼 블록 안의 어떤 객체 주소든 쉽게 계산할 수 있습니다.
size는 slist의 data가 가리키는 객체 앞에 메모리 상에 “숨겨져” 있습니다. 이 트릭은 할당자에서 흔히 사용되며, malloc이 메모리 청크의 크기를 저장하고 나중에 복구할 수 있게 하는 방식과 동일합니다.
Getting the Block Size
블록에 대한 slist*가 주어지면 arena_node2block을 사용해 블록의 크기를 얻을 수 있습니다:
static inline arena_block* arena_node2block( slist *node ) {
return node == NULL ? NULL :
(arena_block*)(node->data - offsetof(arena_block, data));
}node->data는 배열이므로 첫 번째 요소에 대한 포인터로 “디케이”됩니다. 메모리 상에서는 앞서 언급한 size가 그 앞에 저장됩니다. node->data 바로 앞에 sizeof(size_t) 바이트만큼 있다고 생각할 수 있지만, 실제로는 size와 data 사이에 패딩이 존재할 수 있습니다. 패딩을 포함한 정확한 바이트 수를 빼기 위해 표준 매크로 offsetof를 사용할 수 있습니다. 이 경우 offsetof는 구조체 내 data의 오프셋을 반환하며, 여기에는 모든 패딩이 포함됩니다.
Deallocator Implementation
void arena_cleanup( arena *a, void (*free_fn)(void*) ) {
for ( slist *node = a->blocks, *next_node;
node != NULL; node = next_node ) {
arena_block *const block = arena_node2block( node );
if ( free_fn != NULL ) {
for ( size_t i = a->avail; i size; ++i )
(*free_fn)( &block->data[ i * a->obj_size ] );
a->avail = 0;
}
free( block );
next_node = node->next;
free( node );
}
a->blocks = NULL;
}코드는 비교적 직관적입니다. 기억해야 할 유일한 점은 첫 번째 블록이 완전히 채워지지 않을 수 있으므로 실제 객체에 대해서만 free_fn을 호출해야 한다는 것입니다. 따라서 0이 아니라 a->avail부터 반복을 시작하고, 나머지 모두 가득 찬 블록에 대해서는 a->avail을 0으로 설정합니다.
결론
객체 관리를 위해 아레나를 사용하면 전체 객체 컬렉션을 한 번에 해제할 때 메모리 관리가 단순해질 수 있습니다. 아레나는 malloc와 free 호출을 줄여주기 때문에 성능이 더 좋을 수도 있습니다. 여기서 소개한 두 가지 구현 외에도 다양한 아레나 구현이 존재합니다—다음 프로젝트에서 아레나를 고려해 보세요.