[Malloc Lab] Implicit List
간접 리스트 방식으로 malloc, free 를 구현해보도록 하겠습니다.
간접 리스트 방식으로 구현하기에 앞서 Malloc / Free 를 구현할 때 유용한 매크로 변수, 매크로 함수, 메소드 들에 대한 설명을 첨부합니다.
먼저 mm_implicit.c 의 mm_init 메소드를 구현하겠습니다. mm_init 메소드는 동적 메모리 할당을 하기 위한 초기 힙 구조를 생성하는 메소드입니다.
/*
* Initialize: return -1 on error, 0 on success.
*/
int mm_init(void) {
if ( (heap_listp = mem_sbrk(4*WSIZE)) == -1 ) // 초기 empty heap 설정
return -1; // heap_listp = 새로 생성되는 heap 영역의 시작 주소
PUT(heap_listp, 0); // heap의 시작부분 할당
PUT(heap_listp + WSIZE, PACK(OVERHEAD, 1)); // prologue header block
PUT(heap_listp + DSIZE, PACK(OVERHEAD, 1)); // prologue footer block
PUT(heap_listp+WSIZE+DSIZE, PACK(0, 1)); // epilogue header block
heap_listp += DSIZE; // heap_listp를 footer block에 locate
if (extend_heap(CHUNKSIZE / WSIZE) == NULL) { // CHUNKSIZE Bytes 의 free block 을 생성. 초기 가용블럭을 생성합니다.
return -1;
}
return 0;
}mem_sbrk 함수를 통해 힙 영역의 크기를 키워줍니다. mem_sbrk 는 brk 포인터를 증가시킴으로써 힙 영역의 크기를 키우고 증가시키기 전 brk 포인터의 위치를 반환합니다. mem_sbrk 코드는 memlib.h 에 내장되어 있습니다. 코드 내용은 다음과 같습니다. epilogue 블럭의 사이즈는 특이하게 0임에 유의합시다.
heap_listp 에 mem_sbrk를 통해 워드 4개만큼 힙을 증가시키고 만약 힙 영역을 증가시킬 수 없다면 -1을 반환합니다.
put 을 이용해 Root Block 에 0을 입력하고, 그 다음 워드에 prologue header block, 그 다음 워드에 prologue footer block, 그 다음 워드에 epilogue block 을 정보와 함께 입력하고 heap_listp 를 prologue footer block 에 위치시키고, CHUNKSIZE 바이트만큼 증가시킵니다.
이번엔 Implicit List 방식을 이용해 malloc 함수를 구현해보도록 하겠습니다. malloc 함수의 소스코드는 다음과 같습니다.
/*
* malloc
*/
void *malloc (size_t size) {
size_t asize;
size_t extendsize;
char *bp;
if (size < DSIZE) { //malloc 의 size 가 double words 보다 작을 경우
asize = DSIZE + OVERHEAD;
} else {
asize = DSIZE * ( (size + 2*DSIZE - 1) / DSIZE );
}
if ( (bp = find_fit(asize)) != NULL) {
place((void *)bp, asize);
return (void *)bp;
} else { // find_fit 을 통해 가용블럭을 찾지 못한 경우, 힙을 증가시킵니다.
extendsize = MAX(asize,CHUNKSIZE);
if ( (bp = extend_heap(extendsize)) != NULL) { // CHUNKSIZE BYTES의 heap을 새로 생성합니다.
place((void *)bp, asize);
return (void *)bp;
}
}
return NULL;
}asize 는 adjusted Size 로, 실제 payload 를 저장할 공간 + header 와 footer, 그리고 Even Words Align을 위한 padding 을 고려하여 메모리 상에서 실제 그 블럭이 차지하는 size를 의미합니다.
asize를 만들어주고, asize 만큼 비어있는 가용 블럭 (free block) 을 찾습니다. 적절한 크기의 가용 블럭 (free block) 을 찾지 못한 경우, extend_heap메소드를 이용해 힙의 크기를 max(asize, CHUNKSIZE) 만큼 증가시킨 후 증가시킨 공간에 place 메소드를 통해 memory allocate 를 수행합니다. extend_heap 메소드와 place 메소드은 다음과 같습니다.
static void *extend_heap(size_t words) {
char *bp;
size_t size;
size = (words%2) ? (words+1) * WSIZE : words * WSIZE; // adjust size even align
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)); // Set epilogue Block
return coalesce(bp);
}extend_heap 은 parameter words 사이즈만큼 힙 크기를 증가시키고, 가용 블럭의 주소를 리턴하는 함수입니다.
mem_sbrk 를 통해 힙 사이즈를 증가시키고, 증가시킨 힙 공간만큼 가용 블럭이 생겼으므로, header와 footer 에 가용 영역에 대한 정보를 mapping 하고 epilogue block 을 표시해줍니다. 그리고 coalesce 를 통해 연결할 가용 블럭이 있다면 가용 블럭을 extend 시켜줍니다. coalesce 함수는 다음과 같습니다.
static void *coalesce(void *bp){
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // allocation status of previous block
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // allocation status of next block
size_t size = GET_SIZE(HDRP(bp));
if (prev_alloc && next_alloc){ // If two blocks are allocated already, return bp CASE 1
return bp;
}
else if (prev_alloc && !next_alloc){ // If next block is free block, return extended block CASE 2
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){ // If previous block is free block, return extended block CASE 3
size+= GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size,0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size,0));
bp = PREV_BLKP(bp);
}
else { // If two blocks are free block, return extended block CASE 4
size+= GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(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;
}Introduction to Malloc lab 에서 설명드렸던 coalesce 의 case 별로 구현해주었습니다.
다음은 place 메소드에 대한 설명입니다.
static void place(void *bp, size_t asize) {
//쪼개기 미구현 함수
/*
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
*/
//쪼개기 구현
size_t ThisBlockSize = GET_SIZE(HDRP(bp));
if ( (ThisBlockSize-asize) >= (2*DSIZE)){ // 2*DSIZE 는 OVERHEAD와 최소payload 의 합과 같습니다.
PUT(HDRP(bp), PACK(asize,1));
PUT(FTRP(bp), PACK(asize,1));
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(ThisBlockSize-asize,0));
PUT(FTRP(bp), PACK(ThisBlockSize-asize,0));
}
else{
PUT(HDRP(bp), PACK(ThisBlockSize,1));
PUT(FTRP(bp), PACK(ThisBlockSize,1));
}
};쪼개기를 이용하지 않고, 그냥 항상 가용 블럭의 처음과 끝을 모두 사용할 경우, 실제 메모리의 크기보다 힙이 커지게 되어 Segmentation Faults 가 발생합니다. 쪼개기를 이용하여 place 를 구현하는 방법은 주석과 코드와 같이 현재 가용블럭의 크기 (ThisBlockSize) 에서 asize (할당할 블럭의 adjusted size) 를 뺀 값이 OVERHEAD 와 최소payload(2words=8bytes)보다 크거나 같으면, 쪼개기를 수행할 수 있습니다. 쪼개기를 쓸 수 없는 경우, 가용블럭에 그냥 블럭에 대한 정보를 header와 footer 에 mapping 해줍니다.
이와 같이 구현하고, calloc 과 realloc 은 naive 방식으로 구현했던 것을 그대로 가져다 사용하면 다음과 같은 실행결과를 얻을 수 있습니다.
naive 방식의 score 가 66점이었던 것을 생각하면, First Fit 을 사용하는 Implicit List 방식은 성능이 좋지 않은 것을 알 수 있습니다. 이를 보완하기 위해서 Next fit 방식을 사용해보도록 하겠습니다.
Next fit 을 사용하기 위해서는 이전에 할당한 블록에 대한 포인터 주소 정보가 필요합니다. 이를 저장하기 위해서 새 변수 static char *previous_heap_listp 를 선언해주겠습니다.
그리고 find_fit 을 다음과 같이 구현해주도록 하겠습니다.
static void *find_fit (size_t asize) {
void *bp;
//Next Fit Code
// use previous_heap_listp
for (bp = previous_heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) { // until meet Epilogue
if ( (!GET_ALLOC(HDRP(bp))) && (asize <= GET_SIZE(HDRP(bp))) ) {
previous_heap_listp = bp;
return bp;
}
}
void *bbp = previous_heap_listp;
for (bp = heap_listp; bp < bbp; bp = NEXT_BLKP(bp)) { // until meet previous_heap_listp
if ( (!GET_ALLOC(HDRP(bp))) && (asize <= GET_SIZE(HDRP(bp))) ) {
previous_heap_listp = bp;
return bp;
}
}
return NULL;
}먼저 이전에 사용한 블럭의 포인터를 이용하여 다음 fit block 을 찾다가 epilogue 를 만나기 전까지 찾지 못하면 다시 처음으로 돌아와 이전 사용한 블럭의 포인터를 만나기 전까지 fit block 을 찾습니다. 그럼에도 찾지 못한다면 NULL을 리턴합니다. 추가로, coalesce 시, 마지막으로 사용한 블럭의 포인터가 바뀔 수 있으므로 coalesce도 다음과 같이 수정해줍니다.
static void *coalesce(void *bp){
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // allocation status of previous block
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // allocation status of next block
size_t size = GET_SIZE(HDRP(bp));
if (prev_alloc && next_alloc){ // If two blocks are allocated already, return bp CASE 1
previous_heap_listp = bp; // for next fit
return bp;
}
else if (prev_alloc && !next_alloc){ // If next block is free block, return extended block CASE 2
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){ // If previous block is free block, return extended block CASE 3
size+= GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size,0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size,0));
bp = PREV_BLKP(bp);
}
else { // If two blocks are free block, return extended block CASE 4
size+= GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size,0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size,0));
bp = PREV_BLKP(bp);
}
previous_heap_listp = bp; // for next fit
return bp;
}Next Fit 을 통해 malloc free 를 구현했을 때 얻을 수 있는 점수는 다음과 같습니다.
더 나아가, place 를 다음과 같이 구현하면 utilization score 가 더 상승해 높은 점수를 얻을 수 있습니다.
남는 가용블럭의 사이즈가 0보다 크기만 하면 남겨두는 방식으로 구현하였는데, coalesce 시 사용하지 않는 free block 을 더 줄일 수 있어 utilization 점수가 상승하는 것 같습니다.
향상된 place 코드는 다음과 같습니다.
static void place(void *bp, size_t asize) {
size_t currentBlockSize = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(asize,1));
PUT(FTRP(bp), PACK(asize,1));
size_t remainderBlockSize = currentBlockSize - asize;
if (remainderBlockSize > 0) {
PUT(HDRP(NEXT_BLKP(bp)), PACK(remainderBlockSize, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(remainderBlockSize, 0));
}
}