메모리 할당 전략 - 5부

Free List Allocators

Free List Based Allocation

이전 글에서는 제공된 백킹 버퍼를 동일한 크기의 청크(chunks) 로 나누고 어떤 청크가 비어 있는지 추적하는 풀 할당기를 살펴보았다. 풀 할당기는 매우 빠른 할당기로, 순서가 뒤섞인 해제(out of order free)를 상수 시간 $O(1)$ 에 수행할 수 있으며 단편화도 매우 적게 유지한다. 풀 할당기의 가장 큰 제약은 모든 메모리 할당이 동일한 크기여야 한다는 점이다.

프리 리스트(free list)는 범용 할당기로, 앞서 살펴본 다른 할당기들과 비교했을 때 어떤 제약도 강제하지 않는다. 임의의 크기에 대해 할당과 해제를 순서와 무관하게 수행할 수 있다. 이러한 성격 때문에, 이 시리즈에서 앞서 논의한 다른 방식들만큼 성능이 좋지는 않다.

프리 리스트 할당기를 구현하는 흔한 접근은 두 가지가 있다. 하나는 연결 리스트를 사용하는 방법이고, 다른 하나는 레드-블랙 트리를 사용하는 방법이다. 연결 리스트 접근이 가장 흔하며, 먼저 이것을 살펴보겠다.

Linked List Approach

이 절의 제목이 암시하듯, 메모리에서 연속된 가용 블록들의 주소와 크기를 저장하기 위해 연결 리스트를 사용한다. 사용자가 메모리를 요청하면, 연결 리스트에서 데이터가 들어갈 수 있는 블록을 검색한다. 그런 다음 해당 요소를 연결 리스트에서 제거하고, 데이터 바로 앞에 할당 헤더(해제 시 필요)를 배치한다( 스택 할당기 글에서 사용했던 것과 유사하다).

메모리를 해제할 때는 (할당 앞에 저장된) 할당 헤더를 복구해 해제하려는 블록의 크기를 알아낸다. 블록을 해제한 뒤에는 연결 리스트에 삽입하고, 더 큰 블록을 만들기 위해 서로 인접한(연속된) 메모리 블록들을 병합(coalescence) 하려고 시도한다.

Linked List Free List Implementation

n.b. 다음 구현은 이 할당기에서 요청되는 할당의 크기와 정렬(alignment)에 대해 몇 가지 제약을 둔다. 할당의 최소 크기는 프리 리스트 노드 데이터 구조의 크기 이상이어야 하며, 정렬도 비슷한 요구 사항이 있다.

Data Structures

연결 리스트 기반 프리 리스트 할당기를 구현하는 데 필요한 데이터 구조는 다음과 같다.

// Unlike our trivial stack allocator, this header needs to store the 
// block size along with the padding meaning the header is a bit
// larger than the trivial stack allocator
typedef struct Free_List_Allocation_Header Free_List_Allocation_Header;
struct Free_List_Allocation_Header {
    size_t block_size;
    size_t padding;
};

// An intrusive linked list for the free memory blocks
typedef struct Free_List_Node Free_List_Node;
struct Free_List_Node {
    Free_List_Node *next;
    size_t block_size;
};

typedef Placement_Policy Placement_Policy;
enum Placement_Policy {
    Placement_Policy_Find_First,
    Placement_Policy_Find_Best
};

typedef struct Free_List Free_List;
struct Free_List {
    void *           data;
    size_t           size;
    size_t           used;
    
    Free_List_Node * head;
    Placement_Policy policy;
};

Initialization

void free_list_free_all(Free_List *fl) {
    fl->used = 0;
    Free_List_Node *first_node = (Free_List_Node *)fl->data;
    first_node->block_size = fl->size;
    first_node->next = NULL;
    f->head = first_node;
}

void free_list_init(Free_List *fl, void *data, size_t size) {
    fl->data = data;
    fl->size = size;
    free_list_free_all(fl);
}

Allocation

이 할당기에서 메모리 블록을 할당하려면, 데이터를 담을 수 있는 메모리 블록을 찾아야 한다. 즉, 연결 리스트의 가용 메모리 블록들을 순회하며 요청한 크기 이상인 블록을 찾고, 그 블록을 가용 메모리 연결 리스트에서 제거한다. 첫 번째로 맞는 블록을 찾는 것을 first-fit 배치 정책이라고 하는데, 요청한 크기에 맞는 첫 번째 블록에서 멈추기 때문이다. 또 다른 배치 정책으로 best-fit 이 있는데, 이는 요청 크기를 수용할 수 있는 가용 블록들 중 가능한 한 가장 작은 블록을 찾는다. 후자의 선택은 할당기 내부의 메모리 단편화를 줄여준다.

그림에는 가용 메모리 블록이 3개 있지만, 요청된 메모리 할당 크기(헤더 포함)에 모두 적합한 것은 아니다.

할당이 이루어지면, 프리 리스트는 사용된 노드를 제거하도록 갱신된다.

이 알고리즘의 시간 복잡도는 $O(N)$ 이며, 여기서 N은 프리 리스트에 있는 가용 블록의 개수다.

// Defined Memory Allocation Strategies Part 3: /article/2019/02/15/memory-allocation-strategies-003/#alloc
size_t calc_padding_with_header(uintptr_t ptr, uintptr_t alignment, size_t header_size);

Free_List_Node *free_list_find_first(Free_List *fl, size_t size, size_t alignment, size_t *padding_, Free_List_Node **prev_node_) {
    // Iterates the list and finds the first free block with enough space 
    Free_List_Node *node = fl->head;
    Free_List_Node *prev_node = NULL;
    
    size_t padding = 0;
    
    while (node != NULL) {
        padding = calc_padding_with_header((uintptr_t)node, (uintptr_t)alignment, sizeof(Free_List_Allocation_Header));
        size_t required_space = size + padding;
        if (node->block_size >= required_space) {
            break;
        }
        prev_node = node;
        node = node->next;
    }
    if (padding_) *padding_ = padding;
    if (prev_node_) *prev_node_ = prev_node;
    return node;
}
Free_List_Node *free_list_find_best(Free_List *fl, size_t size, size_t alignment, size_t *padding_, Free_List_Node **prev_node_) {
    // This iterates the entire list to find the best fit
    // O(n)
    size_t smallest_diff = ~(size_t)0;
    
    Free_List_Node *node = fl->head;
    Free_List_Node *prev_node = NULL;
    Free_List_Node *best_node = NULL;
    
    size_t padding = 0;
    
    while (node != NULL) {
        padding = calc_padding_with_header((uintptr_t)node, (uintptr_t)alignment, sizeof(Free_List_Allocation_Header));
        size_t required_space = size + padding;
        if (node->block_size >= required_space && (it.block_size - required_space < smallest_diff)) {
            best_node = node;
        }
        prev_node = node;
        node = node->next;
    }
    if (padding_) *padding_ = padding;
    if (prev_node_) *prev_node_ = prev_node;
    return best_node;
}

void *free_list_alloc(Free_List *fl, size_t size, size_t alignment) {
    size_t padding = 0;
    Free_List_Node *prev_node = NULL;
    Free_List_Node *node = NULL;
    size_t alignment_padding, required_space, remaining;
    Free_List_Allocation_Header *header_ptr;
    
    if (size < sizeof(Free_List_Node)) {
        size = sizeof(Free_List_Node);
    }
    if (alignment < 8) {
        alignment = 8;
    }
    
    
    if (fl->policy == Placement_Policy_Find_Best) {
        node = free_list_find_best(fl, size, alignment, &padding, &prev_node);
    } else {
        node = free_list_find_first(fl, size, alignment, &padding, &prev_node);
    }
    if (node == NULL) {
        assert(0 && "Free list has no free memory");
        return NULL;
    }
    
    alignment_padding = padding - sizeof(Free_List_Allocation_Header);
    required_space = size + padding;
    remaining = node->block_size - required_space;
    
    if (remaining > 0) {
        Free_List_Node *new_node = (Free_List_Node *)((char *)node + required_space);
        new_node->block_size = rest;
        free_list_node_insert(&fl->head, node, new_node);
    }
    
    free_list_node_remove(&fl->head, prev_node, node);
    
    header_ptr = (Free_List_Allocation_Header *)((char *)node + alignment_padding);
    header_ptr->block_size = required_space;
    header_ptr->padding = alignment_padding;
    
    fl->used += required_space;
    
    return (void *)((char *)header_ptr + sizeof(Free_List_Allocation_Header));
}

Free and Coalescence

프리 리스트 할당기로 할당된 메모리 블록을 해제할 때는, 할당 헤더를 되찾고 그 메모리 블록을 이제 가용 메모리 블록으로 취급해야 한다. 그런 다음 (연결 리스트는 정렬되어 있으므로) 메모리 주소 순서에서 올바른 위치에 도달할 때까지 가용 메모리 블록들의 연결 리스트를 순회하고, 그 위치에 새 노드를 삽입해야 한다. 이는 주소 기준으로 이미 정렬되어 있는 리스트의 이전 노드와 다음 노드를 확인함으로써 달성할 수 있다.

프리 리스트에 삽입할 때는, 서로 연속된 가용 메모리 블록이 있다면 이를 병합(coalescence)하고자 한다. 연결 리스트를 순회하는 동안 이전/다음 가용 노드를 모두 저장해 두었으므로, 가능하다면 이 블록들을 합칠 수 있다.

이 알고리즘의 시간 복잡도는 $O(N)$ 이며, 여기서 N은 프리 리스트에 있는 가용 블록의 개수다.

void free_list_coalescence(Free_List *fl, Free_List_Node *prev_node, Free_List_Node *free_node);

void *free_list_free(Free_List *fl, void *ptr) {
    Free_List_Allocation_Header *header;
    Free_List_Node *free_node;
    Free_List_Node *node;
    Free_List_Node *prev_node = NULL;
    
    if (ptr == NULL) {
        return;
    }
    
    header = (Free_List_Allocation_Header *)((char *)ptr - sizeof(Free_List_Allocation_Header));
    free_node = (Free_List_Node *)header;
    free_node->block_size = header->block_size + header->padding;
    free_node->next = NULL;
    
    node = fl->head;
    while (node != NULL) {
        if (ptr < node) {
            free_list_node_insert(&fl->head, prev_node, free_node);
            break;
        }
        prev_node = node;
        node = node->next;
    }
    
    fl->used -= free_node->block_size;
    
    free_list_coalescence(fl, prev_node, free_node);
}

void free_list_coalescence(Free_List *fl, Free_List_Node *prev_node, Free_List_Node *free_node) {
    if (free_node->next != NULL && (void *)((char *)free_node + free_node->block_size) == free_node->next) {
        free_node->block_size += free_node->next->block_size;
        free_list_node_remove(&fl->head, free_node, free_node->next);
    }
    
    if (prev_node->next != NULL && (void *)((char *)prev_node + prev_node->block_size) == free_node) {
        prev_node->block_size += free_node->next->block_size;
        free_list_node_remove(&fl->head, prev_node, free_node);
    }
}

Utilities

프리 리스트 삽입, 제거, 그리고 헤더에 필요한 패딩을 계산하는 데 필요한 일반 유틸리티들.

void free_list_node_insert(Free_List_Node **phead, Free_List_Node *prev_node, Free_List_Node *new_node) {
    if (prev_node == NULL) {
        if (*phead != NULL) {
            new_node->next = *phead;
        } else {
            *phead = new_node;
        }
    } else {
        if (prev_node->next == NULL) {
            prev_node->next = new_node;
            new_node->next  = NULL;
        } else {
            new_node->next  = prev_node->next;
            prev_node->next = new_node;
        }
    }
}

void free_list_node_remove(Free_List_Node **phead, Free_List_Node *prev_node, Free_List_Node *del_node) {
    if (prev_node == NULL) { 
        *phead = del_node->next; 
    } else { 
        prev_node->next = del_node->next; 
    } 
}

Red Black Tree Approach

프리 리스트를 구현하는 또 다른 방법은 레드-블랙 트리를 사용하는 것이다. 그 목적은 할당과 해제를 더 빠르게 수행할 수 있도록 하는 데 있다. 위의 연결 리스트는 어떤 연산이든 선형으로 순회해야 한다($O(N)$). 레드-블랙 트리는 시간 복잡도를 $O(log(N))$ 으로 낮추면서도 공간 복잡도를 비교적 낮게 유지한다(이전과 같은 트릭, 즉 트리 데이터를 가용 메모리 블록 내부에 저장하는 방식 사용). 그리고 이러한 자료구조 접근의 결과로, 할당/해제 속도를 유지하면서 단편화를 줄이기 위해 항상 best-fit 알고리즘을 채택할 수도 있다.

공간 복잡도가 약간 증가하는 이유는 단일 연결 리스트 대신 (정렬된) 이중 연결 리스트가 필요하기 때문이다. 하지만 그 결과로 병합(coalescence) 연산을 $O(1)$ 시간에 수행할 수 있다.

이 구현은 많은 malloc 구현에서 흔히 볼 수 있는 측면이지만, 대부분의 malloc은 서로를 보완하는 여러 가지 다른 메모리 할당 전략을 함께 사용한다는 점에 유의하라.

이 글에서는 이 접근을 어떻게 구현하는지 시연하지 않고, 독자를 위한 작은 연습문제로 남겨 두겠다. 다음 다이어그램이 도움이 될 수 있다:

Conclusion

프리 리스트 할당기는 임의의 크기 할당과 순서에 구애받지 않는 해제가 필요한 범용 할당기가 필요할 때 매우 유용한 할당기다.

다음 글에서는 버디 메모리 할당기를 논의하겠다.