크래프톤 정글 주제별 탐구 - 메모리 할당기

정의

동적 메모리 할당기(Dynamic Memory Allocator)는 힙(heap) 이라고 하는 프로세스의 가상 메모리 영역을 관리한다. 메모리 구조를 참고하면 도움이 될 것이다.

일단, 현재 정글에서 요구하는 순서에 맞추어 진행을 해보고자 하겠다.

가용 리스트 조작을 위한 기본 상수와 매크로

동적 메모리 할당을 통해 힙 영역에 뭔가를 저장하고 싶다면, 먼저 가용 리스트에 대해 이해해야 한다.

가용 리스트는 물론 묵시적 가용 리스트, 명시적 가용 리스트, 분리 가용 리스트 등 여러 가지가 있지만, 일단 CSAPP 9장에 작성된 내용인 만큼 묵시적 가용 리스트를 기반으로 생각해보도록 하자.

먼저 워드 크기, 더블 워드 초기 가용 블록과 힙 확장을 위한 기본 크기 상수들이 존재할 것이다. 정렬 방식에 따라 블록의 크기 및 배수가 결정될 것이고, 이에 따라 저장되는 크기가 역시 변하기 때문이다.

또한, Chunk Size가 필요하다. 이는, 힙을 증가시킬 때 필요한 크기이다. 다시 말해, brk(break) 포인터의 값이 이만큼 증가할 것이다 를 나타내는 상수이다.

사용할 함수들의 리스트로는 다음과 같다.

GET, PUT

GET(p), PUT(p, val) : p를 참조하거나, val 값을 넣는 것. 이때, 모든 값들은 unsigned int 의 형으로 작성한다. val은 또 다른 것의 주소값이다.

#define GET(p)    (*(unsigned int *)(p))
#define PUT(p)    (*(unsigned int*)(p) = val)

GET_SIZE, GET_ALLOC

GET_SIZE(p), GET_ALLOC(p) : p의 크기를 가져오거나, 할당 여부를 가져온다. 이들은 전부 헤더값을 통해 알 수 있다.

물론, p의 크기는 지정된 정렬 제한조건의 크기의 배수일 것이다. 또한, 헤더는 다음과 같이 결정된다. (단, 이때 하나의 블록의 크기를 N이라고 한다.)

헤더 = P의 크기 + 할당 여부 이때, 헤더의 제일 앞 세 비트를 할당 여부로 사용한다. 0이면 가용, 1이면 할당이다.

이로 위의 함수들은 다음과 같이 정의할 수 있다.

#define GET_SIZE(p)     (GET(p) & ~0x7)
#define GET_ALLOC(p)     (GET(p) & 0x1)

비트 마스킹을 통해 둘 다 구현할 수 있다. -0x7의 경우, 0x7이 0111 이므로, 이를 보수연산을 진행한 결과는(4bit 기준) 1111 1111 1111 1000 이므로, 이를 and 연산을 통해 크기만 가져올 수 있다.

반대로, 0x1 을 통해 할당 여부를 가져올 수 있다.

HDRP, FTRP

다음 함수들은 헤더의 위치와 푸터의 위치를 반환하는 함수들이다.

bp의 위치를 가지고 생각하면, 처음 부분에서의 WSIZE를 감소시키면(한 블럭 앞으로 가면) 헤더로 이동할 수 있다. bp의 푸터의 경우에는 마지막 블럭으로 이동해야 한다. 그렇다면, bp의 위치를 가지고 푸터로 이동하려면, 헤더에 위치로 먼저 이동한 다음, 두 헤더 블럭 크기만큼(현재 한 블럭이 Word이므로 더블 워드만큼) 감소하면 푸터의 위치로 이동할 수 있다.

#define HDRP(bp)     ((char *)(bp) - WSIZE)
#define FTRP(bp)     ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

NEXT_BLKP, PREV_BLKP

마지막으로, 이전과 다음 블럭으로 이동하는 함수이다. 이 경우, 다음 블럭은 현재 bp의 크기만큼 이동한 다음, 워드 사이즈만큼을 감소시킨다. 이유는, 현재 포인터 위치 + 할당 블록 사이즈를 추가하면 이후, 헤더만큼을 초과해서 넘기 때문에 헤더의 크기만큼 감소시키는 것이다.

이전 블럭의 경우 현재 포인터에서 할당 블록의 크기만큼을 감소시킨 뒤에, 더블 블럭의 크기만큼을 더 감소시킨다. 그 이유는, 할당 블럭만큼을 감소시키면 이후, 헤더 크기 + 푸터 크기만큼을 더 줄어야 하기 때문이다. 그러면 이전 블럭의 헤더 다음 위치를 반환된 포인터가 가르킬 것이다.

mm_init

mm_init 함수의 경우에는 초기 brk ptr의 위치 할당, 빈 가용 리스트를 만드는 것 등을 실행한다. 이는, 최초 가용 블록을 생성하는 것을 통해 진행하며, 이를 위해서는 extend_heap 함수가 필요하다.

제일 먼저, mem_sbrk를 통해 4 Word 만큼의 공간을 할당한다. 이는 처음에 프롤로그 블럭, 에필로그 블럭을 만들기 위함이다. 이때, 각 블럭은 헤더, 푸터가 들어가므로, 이들은 4워드의 공간이 필요하다.

물론, 이를 진행할 때에는 가용 블럭에만 헤더와 푸터가 포함되고, 할당된 블럭에 헤더만 들어가는 방식을 사용해서 문제를 해결할 수도 있다. 하지만, 이를 진행하였을 때, 원활하게 작업이 진행되지 않아, 이는 추후 추가해보려고 한다.