Goal : C program을 위한 동적 메모리 할당자 만들기 → malloc, free, realloc (정확하고, 효율적이며 빠른 할당자 만들기)
구현에 대한 설명은 아래 링크 참조, or 정글 수강생이라면, Compass에 주어진 malloclab.pdf를 참고하면 된다
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f10/www/labs/malloclab-writeup.pdf
수정 가능 파일은 mm.c 이며, memlib.c 파일을 참고하고 구현을 시작하면 된다.
다른 .c file들은 mdriver.c가 실행될 때, 함수의 처리량을 계산하기 위해 작성된 소스 코드이기 때문에, malloc-lab을 진행할 때 고려대상이 되지 않는다
기본적으로 주어진 코드들 mm.c / csapp를 이용해서 기본구현을 마치고, csapp에서 배운 내용들을 바탕으로, c의 기본라이브러리에 존재하는 malloc과 가장 유사한 처리량 및 메모리 효율을 나타내는 malloc을 만들면 된다
구현 고려사항을 설명하기에 앞서, mm.c의 subroutine들이 어떤 개념하에, 어떻게 동작하는지 간략하게 설명한다
(CSAPP 기본 예제 존재여부에 따라, subroutine들의 전체 코드를 사용한다)
구현 해야 할 함수는 다음과 같다
- mm_init
- extend_heap
- mm_free (설명 x)
- coalesce
- mm_malloc
- find_fit(직접 구현 과제 - 설명 x)
- place (직접구현과제 - 설명 x)
- realloc
int mm_init(void)
목적 : 메모리 초기 설정을 담당하는 함수
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void)
{
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
return -1;
PUT(heap_listp, 0); // Alignment padding -> Unused Block
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); // Prologue header
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); // Prologue footer
PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); // Epilogue header
heap_listp += (2 * WSIZE);
if(extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}
위 init 함수에는 각 Block(Unused / Prologue / Epilogue)의 용도만 숙지하고 있으면 된다
1. Unused Block
목적 : 16byte (Double Word) 정렬을 맞춰주기 위해 사용되는 블록이다
설명 :
첫 16 byte - Unused Block(8 byte) + Prologue Block(8 byte)
다음 16 byte - Prologue Block(8 byte) + Regular Block Header(8 byte)
위를 통해서 알 수 있는 것은, 블록을 순회하는 포인터가 존재할 때, 16바이트마다 payload 위치에 존재할 수 있다는 것이다
만약, Unused Block이 존재하지 않았다면 ,16바이트 단위마다, Regular Block payload 대신, Regular Block Header가 존재했을 것이며, 우리가 궁금한 것은 payload이기 때문에, WSIZE만큼 이동해야 우리가 원하는 payload를 찾을 수 있는 것이다
2. Prologue Block & Epilogue Block
목적 : 첫번째 / 마지막 블록 해제 시, 발생하는 예외처리를 간단하게 만든다
이름에서 알 수 있듯, 힙의 처음 / 마지막을 나타내는 블록으로 사용된다.
Q. 프롤로그 및 에필로그 블록은 왜 사용하는걸까?
위에서 언급했듯, 예외처리를 간단하게 만든다는 장점이 존재한다.
위 내용을 이해하기 위해서는, free()의 동작 과정을 이해해야한다
메모리 해제 시(free),
- 인접 블록의 할당 여부(0 or 1)을 확인하고,
- 인접 블록이 할당되어 있지 않은 경우, 인접 블록을 병합하여 메모리를 해제
이때, 인접 블록의 할당 여부를 통해 병합 여부를 판단하기 때문에, 에필로그 블록과 프롤로그 블록은 모두 '할당된 상태'로 사용한다
결론: 메모리 해제는 free 블록만 찾아서 병합하기 때문에, 프롤로그 및 에필로그 블록 사용 시, 따로 예외처리를 해주지 않아도된다는 이점 존재
static void *extend_heap(size_t words)
목적 : 가용(or free) 블록이 존재하지 않을 때, 힙을 확장해주는 함수
/*
* extend_heap - Extends the heap with a new free block of at least 'words' words.
* Returns a pointer to the new block or NULL on failure.
*/
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
// size는 총 할당 free block을 의미한다
// bp = 이전 brk를 가리키고 있다
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
if((bp = mem_sbrk(size)) == (void *)-1)
return NULL;
// bp를 -WSIZE만큼 이동하면, epilogue block이 나오고, 이를 가용 가능(free)block으로 할당한다
// FTRP(bp), PACK(size, 0)을 통해서, footer block 또한 생성한다
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
return coalesce(bp);
}
정렬을 맞추어주기 위해서 CHUNKSIZE(or adjusted size) / WSIZE를 인자로 넣어준다
이후, size의 홀수, 짝수 여부를 판별하여 처리해준다 -> 정렬을 맞춰주기 위함
mem_sbrk(size)를 통해서 CHUNKSIZE만큼, 힙 영역을 확장해주고, 기존, Epilogue Block을 덮어씌우면서, 가용 블록 추가 및 Eplilogue Block을 이동시킨다
마지막으로, 인접한 가용 블록 이 있는지 확인하고, 생성된 가용 블록과 병합한다
void *mm_malloc(size_t size)
목적 : size만큼의 메모리를 할당하기 위해, 가용 블록을 찾아 할당 블록으로 변경하고, 포인터 반환
void *mm_malloc(size_t size)
{
size_t asize, extendsize;
char *bp;
if (size <= 0)
return NULL;
if (size <= DSIZE)
asize = 2 * DSIZE;
else
asize = ALIGN(size + DSIZE);
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
extendsize = MAX(CHUNKSIZE, asize);
if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
return NULL;
place(bp, asize);
return bp;
}
asize : 조정된 블록 사이즈
extendsize : 추가할 블록 사이즈
size가 0 이하라면 할당을 중단한다.
size가 DSIZE보다 작을 경우, 정렬 요건을 만족하기 위해 블록 크기를 2 * DSIZE로 조정하고, 그 외에는 ALIGN 매크로를 이용해 정렬된 크기(asize)로 맞춘다.
적절한 가용 블록을 find_fit으로 찾았다면, place를 호출해 해당 블록에 메모리를 할당하며,
만약 찾지 못했다면, extend_heap으로 힙을 확장한 뒤, 새로 확장한 블록에 place를 수행한다.
static void *coalesce(void *bp)
목적 : 현재 포인터가 기리키는 블록 근처에 가용 블록이 있다면 병합하는 함수
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));
// Case 1. 이전 블록, 다음 블록 모두 할당된 상태
if (prev_alloc && next_alloc)
{
return bp;
}
// Case 2. 이전 블록은 할당된 상태, 다음 블록은 가용한 상태
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));
}
// Case 3. 이전 블록은 가용한 상태, 다음 불록은 할당된 상태
else if (!prev_alloc && next_alloc)
{
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);
}
// Case 4. 이전 블록, 다음 블록 모두 가용한 상태
else
{
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);
}
find_nextp = bp;
return bp;
}
void *mm_realloc(void *bp, size_t size)
목적 : 현재 포인터가 기리키는 블록을 size만큼 재조정하는 함수
void *mm_realloc(void *bp, size_t size)
{
void *old_bp = bp;
void *new_bp = bp;
size_t copy_size;
if (size <= 0)
{
mm_free(bp);
return 0;
}
new_bp = mm_malloc(size);
if (new_bp == NULL)
return NULL;
copy_size = GET(HDRP(old_bp)) - DSIZE;
if (size < copy_size)
copy_size = size;
memcpy(new_bp, old_bp, copy_size);
mm_free(old_bp);
return new_bp;
}
기존 포인터와, 새 포인터를 설정한 뒤, 기존 데이터를 담을 copy_size를 선언한다
size가 0인 경우, 메모리 반환만 수행하고 종료한다
새로운 메모리 블록을 할당하기 위해 malloc을 실행하고, 할당에 실패하면 NULL을 반환한다
할당에 성공했다면, 기존 데이터를 복사한 뒤, 더 큰 값으로 메모리를 할당하고, 이전 메모리 블록을 해제한다