Malloc Lab
Implicit Allocator
Implicit 방법은 순차적으로 모든 블록을 검사하는 선형적인 방법이다. 일종의 브루트 포스방식이라고 생각할 수 있다. 처음 블록부터 차례대로 검사하는 first-fit 방식을 사용하면 성능이 많이 떨어진다. 하지만 마지막 검사한 블록을 시작으로 하여 검사하는 next-fit 방식을 사용한다면 성능을 향상 시킬수 있다. 이번에는 기본적인 방식인 first-fit 방식으로 설명한다.
heap의 가장 처음과 끝 4byte는 힙의 처음과 끝을 알 수 있게 하는 블록이다. 사이즈는 0, 할당여부는 1인 정보를 부여한다. 이후, 가장 처음 블록은 header와 footer 이외에 어떠한 정보도 들어있지 않은 initial block을 설정한다. 모든 탐색은 해당 블록으로 부터 시작할 수 있게하기 위함이다.
이후 모든 방식에서 블록의 포인터(block pointer)를 활용하여 탐색을 수행하게 된다. block pointer는 header 칸의 바로 뒤 주소로 하는데, block pointer와 할당된 메모리의 주소가 같아 바로 반환하여 사용자에게 메모리가 저장된 위치를 바로 알려줄 수 있어 해당 위치로 잡는다.
Implicit Allocator 메모리 할당 과정
- 탐색을 진행하는 블록의 header 또는 footer를 확인하여 해당 블록의 할당 여부를 확인한다.
- 할당이 되어있다면, 블록의 사이즈만큼 옆으로 이동하여 다음 블록을 확인한다.
- 할당이 되어있지 않다면, 블록의 사이즈를 확인한다.
- 메모리가 할당될 수 있는 사이즈 공간과 같다면 메모리를 할당하고 해당 블록의 block pointer 주소를 반환한다.
- 메모리가 할당될 수 있는 사이즈 공간을 초과한다면 블록을 분할하여 할당하고, 나머지 부분을 해제된 블록으로 바꿔준다.
- 메모리가 할당될 수 있는 사이즈보다 작은 공간이라면 블록의 사이즈만큼 옆으로 이동하여 다음 블록을 확인한다.
- 할당할 수 있는 공간이 없어 힙의 끝에 도달했다면 힙을 확장하여 할당한다.
- 추가적으로 3-2 과정에서 불할된 블록의 사이즈가 일정 수준보다 작은 사이즈가 만들어지게 되는 경우라면, 해당 블록을 전부 사용하여 외부 단편화를 방지한다.
Implicit Allocator 메모리 할당 해제과정
- 할당을 해제할 메모리 주소를 받는다. 해제할 메모리 주소의 앞뒤에 블록들을 확인한다.
- 할당을 해제할 블록의 앞 또는 뒤에 이미 할당이 해제된 블록이 존재한다면 해당 블록과 합쳐 하나의 할당 해제상태 블록으로 만들어 외부 단편화를 방지한다.
Implicit Allocator 기본 설계
함수에 필요한 것들이 대부분이 무언가를 넣는 것이기 때문에 매크로를 만들어 놓는 것이 좋다. 프로그램 전반적으로 계속 쓰일 것이기 때문이다. 따라서 맨 처음 변수 혹은 매크로를 설정해야 한다.
매크로 설정
- 1개의 word 사이즈
- 2배의 word 사이즈
- heap을 한번 늘릴 때 필요한 사이즈
- 주어진 값 중 어느것이 더 클지 정하는 MAX 함수
- 블록 헤더에 사이즈와 할당 여부를 넣을 함수
- 블록에 담긴 값을 읽어오는 함수
- 특정 위치에 값을 넣는 함수
- 해당 블록의 사이즈를 읽는 함수
- 해당 블록의 할당 여부를 읽는 함수
- 헤더 위치를 읽는 함수
- 푸터 위치를 읽는 함수
- 현재 블록의 다음 블록 위치로 이동하는 함수
- 현재 블록의 이전 블록 위치로 이동하는 함수
- 초기에 세팅할 힙
위의 매크로들은 모두 반복적으로 쓰이는 변수나 함수를 일반화 시켜놓은 것이다. 코드는 다음과 같다.
#define WSIZE 4 // 워드, 헤더, 푸터 4byte 크기로
#define DSIZE 8 // 더블 워드, 8byte 크기로
#define CHUNKSIZE (1 << 12) // heap을 늘릴 때 얼만큼 늘릴거냐? 4kb 분량
#define MAX(x, y) ((x) > (y) ? (x) : (y)) // x > y가 참이면 x, 거짓이면 y
#define PACK(size, alloc) ((size) | (alloc)) // 크기와 할당 비트를 통합해서 header와 footer에 저장할 수 있는 값 리턴
#define GET(p) (*(unsigned int *)(p)) // 인자 p가 참조하는 워드를 읽어서 리턴
#define PUT(p, val) (*(unsigned int *)(p) = (val)) // 인자 p가 가리키는 워드에 val을 저장한다.
#define GET_SIZE(p) (GET(p) & ~0x7) // 주소 p에 있는 헤더 또는 풋터의 size를 리턴
#define GET_ALLOC(p) (GET(p) & 0x1) // 주소 p에 있는 헤더 또는 풋터의 할당 비트를 리턴
#define HDRP(bp) ((char *)(bp) - WSIZE) // bp(현재 블록의 포인터)가 주어지면, 현재 블록의 header 위치 반환
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // bp(현재 블록의 포인터)가 주어지면, 현재 블록의 footer 위치 반환
#define NEXT_BLKP(bp) (((char *)(bp) + GET_SIZE((char *)(bp) - WSIZE))) // 다음 블록 bp 위치 반환(bp + 현재 블록의 크기)
#define PREV_BLKP(bp) (((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE))) // 이전 블록 bp 위치 반환(bp - 이전 블록의 크기)
static void *extend_heap(size_t words); // 새 가용 블록으로 힙 확장
static void *coalesce(void *bp); // 인접 가용 블록들과 통합
static void *find_fit(size_t asize); // 가용 리스트를 처음부터 검색해서 크기가 맞는 첫 번째 가용 블록을 선택
static void place(void *bp, size_t asize); // 가용 공간과 할당할 사이즈가 들어갈 수 있는 공간에 header와 footer에
// 정보를 넣어주고 공간 할당을 하고 남은 부분이 있으면
// (넣어줄 가용 블록 크기 - 할당할 크기) 만큼을 가용공간으로 만듬
static void *heap_listp; // find_fit에서 사용하기 위한 정적 전역 변수
static void *next_fit; // find_fit(next-fit) 구현시 필요한 변수mm_init
기본적으로 mm_init은 할당기를 초기화하고 성공이면 0, 실패면 -1을 리턴한다. 초기화 하는 과정에서 가용 리스트의 prologue header, prologue footer, epilogue header를 만드는 과정이 포함된다. 이때 최소 블록 크기는 16바이트로 정한다. 가용 리스트는 묵시적 가용 리스트로 구성된다.
mm_init 함수에 필요한 것
- 힙을 초기 사이즈만큼 세팅한다.
- 가용 리스트에 패딩을 넣는다.
- 가용 리스트에 prologue header를 넣는다
- 가용 리스트에 prologue footer를 넣는다.
- 가용 리스트에 epilogue header를 넣는다.
- 힙에 블록을 할당하기 위해 사이즈를 적당히 한 번 늘린다.
int mm_init(void) {
/* 최소 16바이트(header, footer, payload)을 할당해야되는데
전체로 봤을 때 16바이트를 할당할 수 없으면 return -1 */
if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1) {
return -1;
}
PUT(heap_listp, 0); // 블록 생성시 넣는 padding을 1워드 크기만큼 생성, heap_listp 위치는 맨 처음
PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); // prologue block header 생성
PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); // prologue block footer 생성
PUT(heap_listp + (3*WSIZE), PACK(0, 1)); // epilogue block header 생성
heap_listp += (2*WSIZE); // heap_listp 포인터를 prologue header와 footer 사이에 위치 시킨다.
// CHUNKSIZE: (1<<12) = 4096, 빈 힙을 CHUNKSIZE 바이트의 사용 가능한 블록으로 확장
// 공간이 없다면 return -1;
if (extend_heap(CHUNKSIZE/WSIZE) == NULL) {
return -1;
}
return 0;
}extend_heap
static void *extend_heap(size_t words) {
char *bp;
size_t size;
// 64bit 운영체제는 주소 단위를 8바이트로 읽기 때문에 최소 8바이트가 필요
// 짝수 * 4는 무조건 8의 배수이기 때문에 홀수일 때 짝수로 만들어서 *4를 함
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
// size 크기 만큼 heap을 확장 시킨다. 확장할 공간이 없다면 return NULL
if ((long)(bp = mem_sbrk(size)) == -1) {
return NULL;
}
PUT(HDRP(bp), PACK(size, 0)); // free block header 생성, regular block의 첫번째 부분
PUT(FTRP(bp), PACK(size, 0)); // free block footer 생성, regular block의 마지막 부분
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // free block footer 뒤에 epilogue 위치 설정
// 새 가용 블록으로 힙을 확장하고 이전 블록이 가용블록이면 합침
return coalesce(bp);
}extend_heap의 용도는 크게 다음과 같다.
- 힙이 초기화 될때(init) 앞으로 블록을 넣기 위해 사이즈를 한번 늘리는 것
- malloc을 통해 블록을 넣을 영역을 알아봤지만 적당한 맞춤 영역을 찾지 못했을 때 늘리는 것
코드를 보면
- 먼저 인자를 words 크기로 받아서,
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;8의 배수로 size값을 맞춰준다. - 메모리로부터 추가적인 힙공간을 요청(
mem_sbrk(size)) - 사이즈를 늘렸으니 그 자리에는 가용 블록이 들어가야 한다. 이유는 malloc을 통해 할당을 요청하면 데이터가 블록에 들어갈 수 있기 때문이다.
- 새 가용 블록 header와 footer를 만든다.
- 기존 가용리스트의 epilogue header 위치를 조정한다.
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)); // 현재 블록 헤더의 사이즈 확인
/* case 1 : 이전, 다음 블록 모두 할당되어있다면 */
if (prev_alloc && next_alloc) {
next_fit = bp; // find_fit(next-fit) 구현시 next_fit에 bp위치를 저장
return bp;
/* case 2 : 이전 블록은 할당되어있고, 다음 블록은 가용상태라면 */
} else if (prev_alloc && !next_alloc) {
size += GET_SIZE(HDRP(NEXT_BLKP(bp))); // 현재 블록 사이즈에 다음 블록 사이즈를 더해준다.
PUT(HDRP(bp), PACK(size, 0)); // 현재 블록 header에 size를 넣고 가용상태로 변경
PUT(FTRP(bp), PACK(size, 0)); // 다음 블록 footer에 size를 넣고 가용상태로 변경
/* case 3 : 이전 블록은 가용상태이고, 다음 블록이 할당상태라면 */
} else if (!prev_alloc && next_alloc) {
size += GET_SIZE(HDRP(PREV_BLKP(bp))); // 현재 블록 사이즈에 이전 블록 사이즈를 더해준다.
PUT(FTRP(bp), PACK(size, 0)); // 현재 블록 footer에 size를 넣고 가용상태로 변경
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 블록 header에 size를 넣고 가용상태로 변경
bp = PREV_BLKP(bp); // bp를 이전 블록 payload 시작 위치로 변경
/* case 4 : 이전, 다음 블록 모두 가용 상태라면 */
} else {
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp))); // size에 이전, 다음 블록의 사이즈를 더해준다.
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 블록 header에 size를 넣고 가용상태로 변경
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0)); // 다음 블록 footer에 size를 넣고 가용상태로 변경
bp = PREV_BLKP(bp); // bp를 이전 블록 payload 시작 위치로 변경
}
next_fit = bp; // find_fit(next-fit) 구현시 next_fit에 bp위치를 저장
return bp; // bp 반환
}coalesce 함수에서는 현재 블록이 살필 수 있는 4가지 케이스를 다룬다.
- 이전 블록과 다음 블록이 모두 할당되어 있는 경우 → 합칠 수 없다.
- 이전 블록은 할당상태이지만, 다음 블록은 가용상태인 경우 → 다음 블록과 합칠 수 있다.
- 이전 블록은 가용상태이고, 다음블록은 할당 상태인 경우 → 이전 블록과 합칠 수 있다.
- 이전 블록과 다음 블록이 모두 가용상태인 경우 → 이전, 다음 블록 모두 합칠 수 있다.
mm_malloc
void *mm_malloc(size_t size) {
size_t asize; // 블록 사이즈 조정
size_t extendsize; // heap에 맞는 fit이 없다면 확장하기 위한 사이즈
char *bp;
/* Ignore spurious requests */
if (size == 0) {
return NULL;
}
/* 할당할 크기가 8바이트보다 작으면 asize에 16바이트를 담음
할당할 크기가 8바이트보다 크면 8의 배수로 맞춰줘야되기 때문에
(header/footer의 크기 8바이트 + 7바이트 + 할당할 크기) / 8을 하면
나머지는 버려지고 몫만 남는데 그 몫 * 8을 하면 할당할 크기를 담을 수 있는
최소한의 크기의 8의 배수를 구할 수 있음 */
if (size <= DSIZE) {
asize = 2*DSIZE;
} else {
asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
}
// find_fit으로 asize의 크기를 넣을 수 있는 공간이 있다면
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp; // place를 마친 블록의 위치를 리턴
}
// find_fit에 넣을 수 있는 공간이 없다면, 새 가용블록으로 힙을 확장.
extendsize = MAX(asize, CHUNKSIZE);
// 확장할 공간이 더 남아있지 않다면 NULL 반환
if ((bp = extend_heap(extendsize/WSIZE)) == NULL) {
return NULL;
}
// 확장이 됬다면, asize 만큼 공간을 할당하고 잘라준다.
place(bp, asize);
return bp;
}mm_malloc 에서는 얼마나 블록을 할당할지에 대한 사이즈를 인자로 받는다. 사이즈는 임의로 들어올 수 있기 때문에 정렬을 위해 함수 내부에서 사이즈를 조정해야 한다. 그리고 할당을 할 수 없을 때는 힙을 확장해 할당할 수 있는 자리를 마련해주어야 한다.
할당기가 요청한 크기를 조정하면 할당할 가용 블록이 가용 리스트에 있는지 탐색한다(find_fit). 맞는 블록을 찾으면 블록을 배치한다. 필요하면 기존 블록을 분할한다(place). 맞는 블록을 찾지 못하면 힙을 늘리고 다시 배치한다.
find_fit
static void *find_fit(size_t asize) {
/* First-fit search */
void *bp;
// GET_SIZE(HDRP(bp)) > 0 : 블록의 크기가 0 보다 작을 때, 즉 apilogue를 만날 때까지 반복
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
// 현재 블록이 가용 상태이고, 할당하고 싶은 사이즈(asize)가 현재 블록보다 작을때 bp 반환
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
return bp;
}
}
// for문이 종료됬다면, 알맞는 크기가 없으니 NULL 반환
return NULL;
}static void *find_fit(size_t asize) {
/* NEXT-fit search */
void *bp;
// GET_SIZE(HDRP(bp)) > 0 : 블록의 크기가 0 보다 작을 때, 즉 apilogue를 만날 때까지 반복
for (bp = next_fit; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
// 현재 블록이 가용 상태이고, 할당하고 싶은 사이즈(asize)가 현재 블록보다 작을때 bp 반환
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
return bp;
}
}
for (bp = heap_listp; bp != next_fit; bp=NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
return bp;
}
}
// for문이 종료됬다면, 알맞는 크기가 없으니 NULL 반환
return NULL;
}
find_fit함수는 가용 리스트에 적절한 블록을 찾는 함수이다. 탐색은 크게 3가지 방법으로 나뉜다.
- first fit : 가용블록 리스트를 처음부터 검색해서 크기가 맞는 첫번째 가용 블록을 선택
- next fit : 검색을 리스트의 처음에서 시작하는 대신, 이전 검색이 종료된 지점에서 검색을 시작
- best fit : 모든 가용블록을 검사해서 크기가 맞는 가장 작은 블록을 선택
find_fit 함수의 코드를 보면
- 처음부터 검색하기 위해 bp 포인터 위치를 처음 init때 세팅했던 위치(heap_listp)로 잡는다.
NEXT_BLKP함수를 이용해 다음 블록으로 이동한다.- 블록의 헤더를 검사한다. 검사 조건은 가용 블록이어야 하고, 해당 블록의 사이즈가 넣으려고 했던 사이즈보다 커야 한다.
- 사이즈가 0인 블록이 나오면 탐색을 종료한다(사이즈가 0인 블록은 epilogue header)
- 만약 적절한 위치를 찾지 못하면 NULL을 리턴
place
static void place(void *bp, size_t asize) {
size_t csize = GET_SIZE(HDRP(bp)); // 현재 블록의 사이즈
if ((csize - asize) >= (2*DSIZE)) { // 분할 후에 이 블록의 나머지가 최소 블록 크기(16 bytes)와 같거나 크다면
PUT(HDRP(bp), PACK(asize, 1)); // header 위치에 asize 만큼 넣고 할당 상태로 변경
PUT(FTRP(bp), PACK(asize, 1)); // footer 위치에 asize 만큼 넣고 할당 상태로 변경
bp = NEXT_BLKP(bp); // bp 위치를 다음 블록 위치로 갱신
// asize 할당 후 남은 공간 분할 후 가용 상태로 변경
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));
}
}place함수는 위치와 할당할 크기를 인자로 받는다.
우선 넣을 위치의 블록 사이즈를 계산하고 할당할 크기보다 블록 사이즈가 크면 나머지 부분은 가용블록으로 쪼갠다.(그대로 놔두면 영역 낭비가 된다.)
블록 사이즈가 크면, 블록을 할당하고(블록 헤더, 푸터 위치를 재조정) 나머지 부분을 쪼갠다. 그렇지 않으면 블록을 할당만 한다.
mm_free
void mm_free(void *bp) {
size_t size = GET_SIZE(HDRP(bp)); // free 시킬 블록의 사이즈를 size에 담아준다.
// header와 footer를 가용상태로 변경
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp); // 이전, 다음 블록을 체크해 공간을 합쳐준다.
}
free 함수는 반환할 블록의 위치를 인자로 받는다. 그리고 해당 블록의 가용 여부를 0으로 변경한다. 여기서 핵심은 블록을 가용 리스트에서 제거하는게 아니라 가용상태로 만들어버린다는 것이다.
블록을 반환한 후 가용 블럭이 생기면 항상 연결하는 함수를 실행해서 연결 가능한 블록을 챙겨야 한다.
relloc
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)); // 현재 크기를 copysize에 담는다.
// size가 copySize보다 작다면, copySize의 값을 size의 값으로 바꾼다.
if (size < copySize) {
copySize = size;
}
// newptr : 복사받을 메모리를 가리키는 포인터, oldptr : 복사할 메모리를 가리키는 포인터, copySize : 크기
memcpy(newptr, oldptr, copySize);
mm_free(oldptr); // 기존의 메모리 free
return newptr;
}realloc 에서는 크기를 조정할 블록의 위치와 요청 사이즈를 인자로 받는다. 그후 malloc(size)을 통해 요청 사이즈만큼 블록을 할당한다.
여기서 핵심은 이미 할당된 블록의 사이즈를 직접 건드리는게 아니라, 임시로 요청 사이즈만큼의 블록을 만들고 현재의 블록을 반환하는 것이다. 그러면 사이즈 변경한 효과가 나기 때문이다. 또한 블록 내 데이터 또한 똑같이 옮겨야 하니 C라이브러리에 있는 memcpy함수를 활용한다. 그리고 기존 블록을 반환한다.
Malloc Lap 구현 Github 링크
Malloc Lap
: )