💡 Malloc - Lab: 동적 할당기 구현하기
- 아래의 모든 내용은 CS:APP 책의 9장 내용을 바탕으로, NEXT-FIT 방법론을 이용해 작성하였다.
01. 기본적인 상수와 매크로에 대해 먼저 알아보자!
- mm.c에서 기본적으로 사용하는 상수와 매크로는 아래와 같다.
한 줄씩 뜯어보면서, 각 매크로와 상수가 어떤 식으로 사용되는지 알아보자.
//*********************************************************
/* Basic constants and macros */
/* double word (8) alignment */
#define ALIGNMENT 8
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#define WSIZE 4 // word size = 4bytes
#define DSIZE 8 // double word size = 8bytes
#define CHUNKSIZE (1<<12) //Extend heap by this amount
#define MAX(x,y) ((x)>(y)?(x):(y))
/* Pack a size and allocated bit into a word (header)*/
#define PACK(size,alloc) ((size)|(alloc))
/* Read and write a word at address p */
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
/* Raed the size and allocated fields from address p */
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp) ((char*)(bp) - WSIZE)
#define FTRP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char*)(bp)-WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char*)(bp)-DSIZE)))
//*********************************************************
/* double word (8) alignment */
#define ALIGNMENT 8-
우선, ALIGNMENT는 정렬 조건을 설정해준다. 위와 같이 설정하면 정렬 조건은 8bytes ( = double word)가 된다. 우리는 앞으로 8의 배수 크기로 메모리를 할당해줄 수 있는 것이다.
-
말인 즉, 우리는 heap 공간의 한 칸을 word(=4bytes) 단위로 볼 것이므로, 앞으로 메모리 할당 요청이 들어오면 '짝수 칸 씩 할당 해 주겠다' 라는 말로 쉽게 치환 해 볼 수 있다.
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)- ALIGN(size)를 이용하면, size를 ALIGNMENT 정렬 조건에 맞도록 수정해준다.
size = 10인 경우를 예로 들어보자.
10 + (8-1) = 17일 것이다. 이는 7을 더해 올림을 해주기 위한 준비 과정으로 생각하면 되겠다.
다음으로,17 & ~0x7연산을 이진수로 생각해보자.
이진수에서 ~0x7은 하위 3비트가 0이다. 따라서, ~0x7과 AND 연산을 하게되면 하위 3비트가 0이되면서 8의 배수로 맞춰지게 된다.
이와 같은 과정을 거치면서 size = 10은 결과적으로 16으로 올림 연산이 된 것이다.
#define CHUNKSIZE (1<<12) //Extend heap by this amount-
1<<12는 결과적으로2¹² = 4096과 같다. 이는4096(bytes)를 의미하고, CHUNKSIZE라는 것은 힙을 새로 확장할 때 기준 단위다. -
따라서, CHUNKSIZE를
1<<12로 설정하겠다는 말은 '한 번 힙을 확장할 때 마다 4096bytes를 기준으로 확장하겠다.'는 말이다. -
4096 bytes는 범용적으로 활용하는 기본적인 단위다.
/* Pack a size and allocated bit into a word (header)*/
#define PACK(size,alloc) ((size)|(alloc))
/* Raed the size and allocated fields from address p */
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)-
우선
PACK(size,alloc)에 대해 먼저 살펴보자. 이는 메모리 블록의 header와 footer를 설정할 때, size (크기) 정보와 alloc (할당 여부) 정보를 합쳐주는 연산이다. -
24bytes크기의 할당 된 (1) 블록을 예로 들어보자.
-
위와 같이 이진수로 확인해보면 시각적으로 size 정보와 alloc 정보가 합쳐진다는 것이 무슨 말인지 보일 것이다.
-
참고로, 우리는 정렬 조건을 double word (=8bytes)로 설정 했으므로, size 정보는 하위 3비트를 제외한 부분이 된다. (무조건 8 이상의 배수이므로)
-
위의 개념을 이해했다면,
GET_SIZE(p)와GET_ALLOC(p)는 직관적으로 이해할 수 있다.GET_SIZE(p)를 먼저 살펴보자.
-
GET_SIZE(p)는 ~0x7과 AND 연산을 통해 하위 3비트를 0으로 바꾸어 size 정보만 추출한다.
-
GET_ALLOC(p)는 0x1과 AND 연산을 통해 하위 1비트만을 남겨 alloc 정보를 추출하는 것이다.
/* Read and write a word at address p */
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp) ((char*)(bp) - WSIZE)
#define FTRP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char*)(bp)-WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char*)(bp)-DSIZE)))- 위의
GET(p)와PUT(p,val)은 해당 포인터 주소의 값을 가져오거나 수정하는 역할이다. HDRP(bp),FTRP(bp)는 각각 해당 블록 포인터의 header와 footer의 주소를 반환해주는 역할이다.NEXT_BLKP(bp),PREV_BLKP(bp)는 각각 다음 블록 포인터의 주소, 이전 블록 포인터의 주소를 반환한다.
02. 이제 각 함수를 뜯어보자.
1. (mm.c) mm_init
int mm_init(void)
{
// void * heap_listp = NULL;
/* Create the initial empty heap */
if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
return -1;
/* prologue block */
PUT(heap_listp, 0);
PUT(heap_listp + (1*WSIZE), PACK(DSIZE,1));
PUT(heap_listp + (2*WSIZE), PACK(DSIZE,1));
/* eplilogue block */
PUT(heap_listp + (3*WSIZE), PACK(0,1));
heap_listp += (2*WSIZE);
last_bp = heap_listp;
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}- 코드를 그림을 그려가며 이해하면 쉬운데, 위의 코드에서 extend_heap을 호출하기 전까지의 상황을 그려보면 아래와 같다.
last_bp는 이후 find_fit() 함수를 NEXT-FIT 방법으로 구현할 때 쓸 것이다.
-
참고) mem_sbrk (memlib.h)
-
mem_sbrk는 증가시킬 메모리 공간의 크기를 매개변수로 받아 그 만큼 mem_brk를 확장해주는 함수이다.
-
단, incr이 음수이거나 힙의 크기를 넘어가면 에러 (-1)를 반환한다.
-
/*
* mem_sbrk - simple model of the sbrk function. Extends the heap
* by incr bytes and returns the start address of the new area. In
* this model, the heap cannot be shrunk.
*/
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;
}- 위의 상태를 그대로 머릿속에 두고, extend_heap을 이어가보자.
2. (mm.c) extend_heap
static void *extend_heap(size_t words)
{
char * bp;
size_t size;
/* Allocate an even number of words to maintain alignment */
size = (words % 2) ? (words+1)*WSIZE: words*WSIZE;
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
/* Initialize free block header/footer */
PUT(HDRP(bp), PACK(size,0));
PUT(FTRP(bp), PACK(size,0));
/* Set epilogue block */
PUT(HDRP(NEXT_BLKP(bp)), PACK(0,1));
return coalesce(bp);
}
static void *extend_heap(size_t words)- 매개변수를 word (=4bytes) 단위로 받는다. 즉, 확장할 힙의 '칸 수'로 받는다고 생각하면 편할 것 같다. 우리는 정렬 조건으로 8 bytes를 설정했으므로, 두 칸 단위(=짝수 단위)로 확장이 가능하다.
char * bp;char* bp;에서 자료형char*을 사용해준 이유는char이 1byte 이기 때문에 그렇다. 바이트 단위로 연산을 수행할 것이기 때문이지, '문자를 사용하나?' 하고 혼동해서는 안된다.
size = (words % 2) ? (words+1)*WSIZE: words*WSIZE;- 확장할 칸 수가 짝수 개인지 판단한다. 만약 홀수 개라면 1을 더한 뒤 WSIZE를 곱하고, 짝수 개라면 그냥 WSIZE를 곱해 byte 크기를 계산한다.
계산 값은 변수 size에 할당한다.
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;-
이후 mem_sbrk를 호출해 size 만큼 확장한다.
여기까지 실행했을 때, 현재 힙의 상태는 아래와 같을 것이다.
-
아직 header도, footer도, epilogue block도 제대로 설정되지 않았다. 아래 코드를 이어가보자.
/* Initialize free block header/footer */
PUT(HDRP(bp), PACK(size,0));
PUT(FTRP(bp), PACK(size,0));
/* Set epilogue block */
PUT(HDRP(NEXT_BLKP(bp)), PACK(0,1));-
header와 footer, epilogue block이 알맞게 설정되면서, 비로소 아래와 같은 상태가 된다.
-
이후, coalesce( ) 함수를 호출 해 연속된 비할당 블록들을 연결 해준다.
( mm_init에서는 이제 막 초기화를 하는 단계이기 때문에 의미가 없지만, 동적 할당을 이용하다 필요한 순간에 비어있는 메모리들이 연결 될 것이다.)
return coalesce(bp);3. (mm.c) coalesce
- 가용 가능한 메모리가 연속되어 있을 때, 경우에 맞게 합병하는 함수이다.
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){ /* Case 1 */
return bp;
}
else if (prev_alloc && !next_alloc){ /* 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){ /* 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{ /* Case 4 */
size += GET_SIZE(HDRP(PREV_BLKP(bp)))+ GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size,0));
PUT(FTRP(PREV_BLKP(bp)), PACK(size,0));
bp = PREV_BLKP(bp);
}
last_bp = bp;
return bp;
}- coalesce 함수의 동작은 아래 그림으로 대체한다.
4. (mm.c) place
/* Place block of asize bytes at start of free block bp
* and split if remainder would be at least minimum block size */
static void place(void *bp, size_t asize)
{
size_t csize = GET_SIZE(HDRP(bp));
if ((csize - asize) >= (2*DSIZE)) {
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));
}
}-
asize = 메모리 할당에서 요청된 블록 크기
-
csize = 현재 블록의 크기
-
if ((csize-asize) >= ((2*DSIZE)):: "남은 공간이 충분하다면" ~ 블록을 쪼갠다.
-
남은 공간이 충분하지 않다면 csize 만큼만 할당한다.
-
위 그림을 보고 잘 이해가 가지 않는다면, 아래 예시 그림 참고
위에서 블록의 최소 크기가 2*DSIZE인 이유?
- Header 4bytes, Footer 4bytes만으로 이미 8bytes이고, 데이터를 저장할 페이로드가 존재하려면 최소 8bytes가 더해져야 한다. (정렬 조건이 8bytes 이므로)
- Prologue Block과 헷갈리지 말 것 :: 간혹 Payload 없이 Header와 Footer만 존재하는 Prologue Block을 보고 이 개념이 헷갈릴 수 있는데, Prologue Block은 Payload를 필요로 하지 않는 유일한, 특수한 블록이라는 점을 기억하자.
5. (mm.c) mm_malloc
void *mm_malloc(size_t size)
{
size_t asize;
size_t extendsize;
char *bp;
/* Ignore spurious requests */
if (size == 0)
return NULL;
/* Adjust block size to include overhead and alignment reqs. */
if (size <= DSIZE)
asize = 2*DSIZE;
else
asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
/* Search the free list for a fit */
if ((bp = find_fit(asize)) != NULL){
place(bp, asize);
return bp;
}
/* No fit found. Get more memory and place the block */
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
return NULL;
place(bp,asize);
return bp;
}-
size = 사용자가 요청한 메모리 크기
-
asize = 정렬 요구사항에 맞춘 블록 크기
-
extendsize = 힙을 확장할 때 필요한 크기
/* Ignore spurious requests */ if (size == 0) return NULL; /* Adjust block size to include overhead and alignment reqs. */ if (size <= DSIZE) asize = 2*DSIZE; else asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE); -
asize를 계산 - (조건 분기)
size == 0일 때,NULL 반환size <= DSIZE일 때,asize = 2*DSIZE로 설정. (2*DSIZE는 최소 블록 크기)else) size를 8bytes 정렬을 만족하는 크기로 올림하는 계산식 수행
asize = DSIZE * ((size+(DSIZE)+(DSIZE))/DSIZE)
-
asize만큼 할당이 가능한 공간 탐색 (find_fit 호출)
/* Search the free list for a fit */ if ((bp = find_fit(asize)) != NULL){ place(bp, asize); return bp; } -
asize를 할당할 수 있는 공간이 없다면, extend_heap 호출
/* No fit found. Get more memory and place the block */ extendsize = MAX(asize, CHUNKSIZE); if ((bp = extend_heap(extendsize/WSIZE)) == NULL) return NULL; place(bp,asize); return bp; }6. (mm.c) find_fit
6-1. First-Fit 방식으로 구현
/* First-fit search */ static void *find_fit(size_t asize) { void *bp; for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) { if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) { return bp; } } return NULL; // No fit } -
포인터 bp에 heap_listp (첫 블록의 포인터)할당하고 다음 블록으로 넘어가며 할당 가능한 블록을 찾는다.
6-2. Next-Fit 방식으로 구현
/* Next-fit search */ static void *find_fit(size_t asize) { void *bp; if (last_bp == NULL) last_bp = heap_listp; for (bp = last_bp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) { if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) { last_bp = bp; return bp; } } return NULL; // No fit } -
포인터 bp에 last_bp (마지막으로 할당 연산을 한 포인터)할당하고 다음 블록으로 넘어가며 할당 가능한 블록을 찾는다.
6-3. Best-Fit 방식으로 구현
-
작성 중,,,
7. (mm.c) mm_free
/*
* mm_free - Freeing a block does nothing.
*/
void mm_free(void *ptr)
{
size_t size = GET_SIZE(HDRP(ptr));
PUT(HDRP(ptr),PACK(size,0));
PUT(FTRP(ptr),PACK(size,0));
coalesce(ptr);
}- 해당 포인터의 사이즈 가져오기
- header에 할당 상태 0으로 PUT 연산
- footer에 할당 상태 0으로 PUT 연산
- coalesce(ptr) 함수를 호출 해 연속된 비어있는 공간 합병.
8. (mm.c) mm_realloc
void *mm_realloc(void *ptr, size_t size) {
void *oldptr = ptr;
void *newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
copySize = GET_SIZE(HDRP(oldptr)) - DSIZE;
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}- oldptr 정보를 변수에 따로 저장 해 놓고, size만큼 새 메모리를 malloc해 newptr에 할당.
- meme_cpy( ) 를 이용 해 oldptr에서 newptr로 데이터 복사 해 줌.
- oldptr를 free( ) 해 반환함.
Cookie. 🍪
능동적으로 사고하고, 성장하기 위한. 🌱