해당 글은 malloc을 실제로 작성해보고 실제 할당이 이뤄지는 원리에 대해서 더욱 깊은 이해를 해보고자 하는 목적으로 작성되었습니다.

바로 본론으로 들어가봅시다.

malloc의 함수 프로토타입은 다음과 같습니다.

void *malloc(size_t size);

입력으로 바이트 수를 요구하고, 해당 크기의 메모리 블록에 대한 포인터를 반환합니다.

이를 구현할 수 있는 방법에는 여러가지가 있는데 해당 글에서는 sbrk를 사용하도록 하겠습니다. OS는 프로세스를 위한 스택 및 힙 공간을 예약하고, 이후 sbrk를 사용함으로써 유저는 힙을 조작할 수 있게 됩니다.

malloc을 가장 단순하게 구현한다면 다음과 같은 코드가 가능할 것입니다.

#include <assert.h>
#include <string.h>
#include <sys/types.h>
#include <unistd.h>


void *malloc(size_t size) {
  void *p = sbrk(0);
  void *request = sbrk(size);
  if (request == (void*) -1) {
    return NULL; // sbrk가 실패한 경우
  } else {
    assert(p == request); // thread-safe 하지 않은 경우
    return p;
  }
}

프로그램이 malloc에 공간을 요청할 때 malloc은 sbrk에게 힙 크기를 늘리도록 요청하고 힙으로부터 새 영역의 시작에 대한 포인터를 반환받게 됩니다.

이렇게 힙에 할당된 메모리는 메모리의 할당해제를 수행하는 free 함수를 통해 반환됩니다. free의 프로토타입은 다음과 같습니다.

void free(void *ptr);

free가 수행되면 앞서 malloc으로 반환된 포인터의 공간이 비워져야 합니다. 그러나 malloc에 의해 할당된 무언가에 대한 포인터가 주어지면 어떤 크기의 블록이 해당 할당과 연관되어 있는지는 알 수 없습니다.  해당 문제는 우리가 반환하는 포인터 바로 아래에서 멀리 떨어져 잇는 일부 공간에 메모리 영역에 대한 메타 정보를 저장함으로써 해결됩니다.

예를 들어 각 블록에 대해서 다음의 정보를 저장할 수 있을 것입니다.

struct block_meta {
    size_t size;				// 블록의 크기
    struct block_meta *next;			// 다음 블록의 위치
    int free;					// 할당 해제 여부
}

또한 연결된 블록에 대한 Head도 정의되어야 합니다.

void *global_base = NULL;

malloc 의 경우 가능하면 여유 공간을 재사용하고 기존 공간을 재사용할 수 없는 경우에만 공간을 할당합니다. 우리가 연결 리스트 구조를 가지고 있다는 점을 감안하면, 빈 블록이 있는지 여부를 확인하고 반환하는 것은 간단합니다. 어느 정도 크기의 요청을 받으면 연결된 목록을 반복하여 충분히 큰 여유 블록이 있는지를 확인합니다.

struct block_meta *find_free_block(struct block_meta **last, size_t size) {
    // last: 마지막으로 참조된 블록 정보
    // size: 할당하고자 하는 사이즈
    struct block_meta *current = global_base;
    while (current && !(current->free && current->size >= size)) {
    	*last = current;
        current = current->next;
    }
    return current;
}

만약 사용가능한 블록을 찾지 못한다면 sbrk를 사용하여 OS에 공간을 요청하고 새 블록을 연결 목록 끝에 추가해야 합니다.

#define META_SIZE sizeof(struct block_meta)

struct block_meat *request_space(struct block_meta *last, size_t size) {
    struct block_meta *block;
    block = sbrk(0);
    void *request = sbrk(size + META_SIZE);
    assert((void *)block == request);   // thread sagfe 하지 않은 경우
    if (request == (void *) -1) {
        return NULL;                    // sbrk를 통한 블록 할당 실패
    }
    if (last) {
        last->next = block;             // 만약 마지막 블록 정보가 매개변수로 들어왔다면, 이어 붙어줌
    }
    block->size = size;                 // 블록의 메타데이터에 size 정보를 저장
    block->next = NULL;                 // 블록의 메타데이터에 마지막 블록임을 표시
    block->free = 0;                    // 블록의 메타데이터에 할당되었음을 표시
    return block;
}

앞서 작성한 함수들을 종합하게 되면 여유 공간이 있는지를 확인하고 공간을 요청할 수 있게 되어 malloc을 작성할 준비가 완료되었습니다. 만약 HEAD 포인터인 global_base가 NULL인 경우 공간을 요청하고 기본 포인터를 새 블록으로 설정해야 합니다. 

반대로 HEAD 포인터가 실제 블록의 메타데이터를 가리키고 있다면 기존 공간을 재사용할 가능성이 있는지를 검사해야 합니다. 이떄 재사용이 가능하다면 재사용을 할 것이고, 그렇지 않다면 새로운 공간을 할당하게 될 것입니다.

void *malloc(size_t size)
{
	struct block_meta *block;               // 블록의 메타데이터를 저장할 구조체 포인터
    
    if (size <= 0)                              // 할당하려는 블록의 크기가 0보다 작다면 NULL 반환
    	return NULL;
    
    if (global_base == NULL) {                  // global_base가 NULL이라면, 즉 처음 malloc을 호출했다면
        block = request_space(NULL, size);      // request_space를 통해 블록 할당
        if (!block) {                           // 할당에 문제가 있었다면
            return NULL;                        // 종료
        }
        global_base = block;                    // global_base에 할당된 블록의 메타데이터를 저장
    } else {
        struct block_meta *last = global_base;
        block = find_free_block(&last, size);   // global_base부터 시작하여, size만큼의 빈 블록을 찾음
        if (!block) {                           // 빈 블록을 찾지 못했다면
            block = request_space(last, size);  // request_space를 통해 블록 할당
            if (!block) {                       // 할당에 문제가 있었다면
                return NULL;                    // 종료
            }
        } else {                                // 빈 블록을 찾았다면
            block->free = 0;                    // 블록의 메타데이터에 할당되었음을 표시
        }
    }
}