명시적 동적 할당기를 구현하는 과제다
define 목록
#define WSIZE 4 // word 크기(byte 단위)
#define DSIZE 8 // double word 크기(byte 단위)
#define CHUNKSIZE (1<<12) // 2^10 * 2^2 (byte 단위) -> 4KB
#define MAX(x,y) ((x)>(y)) ? (x) : (y) // x,y 중 큰 값
#define PACK(size,alloc) ((size) | (alloc)) // size 와 할당여부
#define GET(p) (*(unsigned int *)p) // p가 가리키는 값
#define PUT(p,val) (*(unsigned int *)(p) = (val)) // p가 가리키는 값을 val로 설정
#define GET_SIZE(p) (GET(p) & ~0x7) // ~0x7 -> ...11111000 뒤 세자리 비트 외 넷째자리 비트부터 size 판독
#define GET_ALLOC(p) (GET(p) & 0x1) // 뒤 세자리 비트가 001인지 000인지 판독
#define HDRP(bp) ((char*)(bp) - WSIZE) // bp보다 WSIZE 앞 -> 헤더 부분
#define FTRP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // bp의 현재블럭 크기 - 헤더 크기(WSIZE, bp위치가 헤더 시작부분이 아니라 헤더 끝 부분이기 때문) - 푸터 크기(WSIZE) -> 푸터 부분
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) //bp - WSIZE -> bp의 헤더, bp의 현재 블럭 크기를 더해서 다음 블럭으로 이동
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) //bp - DSIZE -> bp의 이전 블럭의 푸터, bp의 이전 블럭 크기를 빼서 이전 블럭으로 이동과제를 구현하기 위해 자주 쓰이는 것들을 정의해놓은 목록이고 각각에 간단한 주석을 달아놓았다. malloc-lab이 어떻게 진행되는지 코드를 보면서 이해해보자. 가장 먼저 초기화 과정을 살펴보자.
mm_init
int mm_init(void){
if((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1){
return -1;
}
PUT(heap_listp,0);
PUT(heap_listp + 1*WSIZE, PACK(DSIZE,1));
PUT(heap_listp + 2*WSIZE, PACK(DSIZE,1));
PUT(heap_listp + 3*WSIZE, PACK(0,1));
heap_listp += 2*WSIZE;
if(extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}가장 먼저 힙 공간을 할당해주는데 heap_listp는 프로세스 전반에 쓰일 변수이니 전역변수로 선언해줘야 한다. mem_sbrk함수로 heap_listp 값을 받아오는데 지금은 mem_sbrk함수를 모르니 임의의 포인터라고만 생각해두자. heap_listp에 첫 부분에는 0을 PUT하고, 다음 word와 그 다음 word에는 DSIZE로 할당됐다는 표시를 해준다. 그 다음 word에는 0 size로 할당됐다고 표시하고 heap_listp를 DSIZE로 할당된 word들 사이로 옮긴다.
이게 무슨 작업인가 하고 보니, 첫 번째 word가 힙의 시작지점을 뜻하고 DSIZE크기인 두 word가 프롤로그 블럭 역할을 한다. 그리고 그 다음 word가 힙의 끝 부분을 의미한다. 여기까지가 힙의 기본 구조를 만드는 작업이고 heap_listp를 프롤로그 블럭 가운데에 놓은 다음 extend_heap 함수를 실행한다. 아직 함수 내용을 보진 않았지만 현재 힙에 공간이 전혀 없고 이름으로 봤을 때 힙 공간을 늘려주는 함수라고 추측해볼 수 있다. 위에서 지나쳤던 mem_sbrk 함수와 extend_heap 함수를 차례로 살펴보자
void *mem_sbrk(int incr) {
char *old_brk = mem_brk;
if ( (incr < 0) || ((mem_brk + incr) > mem_max_addr)) {
errno = ENOMEM;
fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
return (void *)-1;
}
mem_brk += incr;
return (void *)old_brk;
}memlib.c 파일에 있는 함수로 int 인자를 받는다. mem_brk는 전역변수로 mem_init 때 할당받은 메모리공간의 포인터다. 인자로 받은 incr 값만큼 더한값이 메모리주소 최대치를 넘어가는지를 판별해준다. 그렇지 않다면 incr값을 더해주고 더해주기 전 값을 리턴한다. 힙 공간에 대한 안전장치 정도로 생각하면 될 것 같다.
static void *extend_heap(size_t words){
char *bp;
size_t size;
size = (words % 2) ? (words+1)*WSIZE : words*WSIZE; //DSIZE 단위로 설정
if((long)(bp = mem_sbrk(size)) == -1)
return NULL;
PUT(HDRP(bp), PACK(size,0));
PUT(FTRP(bp), PACK(size,0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0,1));
return coalesce(bp);
}인자로 받은 words를 짝수단위로 설정해서 DSIZE 단위의 size가 되도록 하고, mm_init에서 mem_sbrk(4WSIZE)를 실행했으니 여기서는 size만큼 힙 공간을 늘리고 첫 부분으로부터 4WSIZE 만큼 떨어진 즉, 현재 힙의 마지막 블럭 다음으로 bp를 리턴받게 된다. 그리고서 WSIZE만큼 앞인 마지막 블럭이었던 곳을 헤더로 해서 size와 미할당 상태값을 넣어주고 size에 맞는 푸터에도 같은 작업을 해준다. 그리고 힙의 마지막 블럭을 그 뒤에 다시 배치시켜준다. 결국 이 작업은 함수명대로 힙 크기를 늘려주는 거라고 보면 된다. return에 있는 coalesce 함수는 가용 공간과 관련된 것인데 나중에 free함수와 같이 살펴보는 것으로 하자.
mm_malloc
void *mm_malloc(size_t size){
size_t asize;
size_t extendsize;
char *bp;
if(size <= 0)
return NULL;
asize = DSIZE -(-size /DSIZE)*DSIZE;
if((bp = find_fit(asize)) != NULL){
place(bp, asize);
return bp;
}
extendsize = MAX(asize, CHUNKSIZE);
if((bp = extend_heap(extendsize/WSIZE)) == NULL)
return NULL;
place(bp, asize);
return bp;
}힙 공간을 사용할 수 있게 되었으니 이제 본격적으로 메모리를 할당하는 malloc 함수를 보자. size를 인자로 받아서 헤더,푸터 크기(WSIZE+WSIZE = DSIZE)에 size크기를 DSIZE단위에 적용한 크기를 더한 asize를 할당한다. find_fit함수를 통해 asize 크기를 감당할 수 있는 블럭을 찾아서 place 한다. 현재 가용블럭이 없다면 extend_heap 함수를 통해 힙 크기를 늘리고 다시 할당을 시도한다.
static void *find_fit(size_t asize){
char *bp = NEXT_BLKP(heap_listp);
while(GET_SIZE(HDRP(bp)) > 0){
if(!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp)) >= asize)
return bp;
bp = NEXT_BLKP(bp);
}
return NULL;
}heap_listp가 가리키는 프롤로그 블럭의 다음블럭 즉, 현재 힙의 사실상 첫 번째 블럭부터 시작해서 가용블럭이면서 asize이상의 크기인 블럭을 찾는다. 이 방식은 first fit이고 장단점을 비교하여 next fit, best fit 방식으로 함수를 구현할 수도 있다.
static void place(void *bp, size_t asize){
size_t csize = GET_SIZE(HDRP(bp));
if(csize - asize >= DSIZE + WSIZE*2){
PUT(HDRP(bp), PACK(asize,1));
PUT(FTRP(bp), PACK(asize,1));
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(csize - asize,0));
PUT(FTRP(bp), PACK(csize - asize,0));
}else{
PUT(HDRP(bp), PACK(csize,1));
PUT(FTRP(bp), PACK(csize,1));
}
}가용블럭의 위치를 찾아서 bp를 인자로 받고 asize로 할당할 크기를 인자로 받아서 해당 블럭에 적용해주면 되는데 가용블럭의 크기가 적용할 크기보다 크다면 남는 공간은 다시 가용블럭으로 설정해줄 필요가 있다. 물론 헤더와 푸터만 있으면 의미가 없는 블럭이기 때문에 헤더+푸터 크기(2 * WSIZE)보다 더 커야하고 DSIZE 단위로 할당하고 있기 때문에 최소단위의 공간도 필요하다.
mm_free
void mm_free(void *bp){
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size,0));
PUT(FTRP(bp), PACK(size,0));
coalesce(bp);
}할당된 블럭의 헤더와 푸터를 가용상태(0)로 만들어주는 작업을 한다. 그리고서 coalesce함수를 실행하는데 extend_heap함수에서도 호출한 이 함수는 가용블럭이 생겼을 때, 가용블럭들을 연결해서 더 큰 하나의 가용블럭으로 만들 수 있는지 체크하고 작업하는 역할을 한다.
static void *coalesce(void *bp){
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
if(prev_alloc && next_alloc){
return bp;
}else if(prev_alloc && !next_alloc){
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size,0));
PUT(FTRP(bp), PACK(size,0));
}else if(!prev_alloc && next_alloc){
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size,0));
PUT(FTRP(bp), PACK(size,0));
bp = PREV_BLKP(bp);
}else{
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size,0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size,0));
bp = PREV_BLKP(bp);
}
return bp;
}코드는 길지만 각각의 상황들은 아주 간단하다. 우선 인자로 받은 bp의 블럭은 이제 가용상태가 되었기 때문에 이 함수가 호출됐을 것이다. 이 블럭의 앞 블럭과 뒷 블럭의 가용여부를 확인해서 가용블럭들의 크기를 더해 하나의 가용블럭으로 만들어준다.
mm_realloc
void *mm_realloc(void *bp, size_t size){
if(size <= 0){
mm_free(bp);
return NULL;
}
if(bp == NULL)
return mm_malloc(size);
void *oldptr = bp;
void *newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
copySize = GET_SIZE(HDRP(oldptr));
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}할당했던 블럭을 다른 곳에 다시 할당해주는 함수이다. newptr에 메모리를 할당해주고 기존에 있던 oldptr의 크기만큼(새 공간이 더 작으면 가능한 만큼만) 메모리를 복사해주고 oldptr의 블럭은 free해준다.
여기까지 구현하면 54/100 정도의 score가 나올 것이다. 더 높은 점수를 받기 위해선 explicit 방식, seglist 방식을 적용해야 한다. 각각의 방식들이 어떤 것인지 설명만 추가하도록 하겠다
Explicit Free List
명시적 가용 리스트라고 불리는 이 방식은 할당된 블럭들은 제외하고 가용한 블럭들끼리 리스트를 만들어서 가용블럭 탐색 시간을 줄일 수 있다. 그러기 위해선 특정 가용 블럭 다음에 어떤 블럭이 가용 블럭인지를 알아야 하는데 헤더,푸터와 비슷하게 predecessor, successor를 활용한다. 블럭마다 2 * WSIZE 만큼의 공간이 더 필요하게 되고 내부 단편화 가능성이 높아진다는 단점이 생긴다.
이 리스트를 두 가지 방법으로 정렬할 수 있는데 첫 번째는 free된 블럭을 리스트 맨 앞에 붙이고 가용블럭을 찾을 땐 first fit으로 찾는 LIFO 방식이다. 간단한 작업으로 이루어지는만큼 효율성 측면에서는 부정적일 확률이 높다. 다른 방법은 주소 순으로 정렬하고 first fit으로 찾는 것이다. free된 블럭이 들어가야 할 주소를 찾아야 하는 작업이 필요하지만 찾는 블럭이 best fit일 때와 비슷해서 메모리 이용도가 좋아진다.
Segregated Free List
분리 가용 리스트라고 불리는 이 방식은 가용 리스트들을 크기 단위로 관리하여 할당 시간을 줄인다.
