CSAPP : Allocator 구현(종합 설계)
묵시적 가용 리스트에 기초한 간단한 할당기의 구현
- Allocator(할당기) 기본 설계
// --------------------- Declaration --------------- //
extern int mm_init(void);
extern void *mm_malloc (size_t size);
extern void mm_free (void *ptr);
/* Private global variables */
static char *mem_heap; /* Points to first byte of heap */
static char *mem_brk; /* Points to last byte of heap plus 1 */
static char *mem_max_addr; /* Max legal heap addr plus 1 */
/* *mem_init - Initilaize the memory system model */
void mem_init(void)
{
mem_heap = (char *)Malloc(MAX_HEAP);
mem_brk = (char *)mem_heap;
mem_max_addr = (char *)(mem_heap + MAX_HEAP);
}
/*
* 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;
}
mem_heap : 힙의 처음을 가리키는 포인터
mem_brk : 힙의 마지막 자리를 가리키는 포인터
mem_max_addr : MAX_HEAP의 끝 자리를 나타낸다. 이 이상으로는 할당할 수 없음
⭐️ mem_brk
현재 내가 할당받은 힙 공간 중에서 가장 마지막 공간 +1칸을 나타내는 곳이다.
즉, old_brk는 늘린 heap의 첫 번째 칸을 나타낸다.
Function
1) mem_init : 최초 가용 블록으로 힙 생성하기 --> 할당기를 초기화하고, 성공하면 0을 아니면 -1을 리턴한다.
2) mem_sbrk : incr(할당 요청이 들어왔을 때, 요청된 용량)이 들어왔을 때, MAX_HEAP을 초과하지 않으면 추가로 mem_brk를 할당 요청 용량 만큼(incr) 옮긴다.
요청된 용량이 음수이거나, MAX_HEAP을 초과하면 error 메시지를 반환한다.
old_brk : 전에 있던 brk 값으로 mem_sbrk의 리턴 값이 된다.
- Allocator(할당기) 코드
- 가용 리스트 조작을 위한 기본 상수 및 매크로 정의
#define WSIZE 4 /* Word and header/footer size (bytes) */
#define DSIZE 8 /* Double word size (bytes) */
#define CHUNKSIZE (1<<12) /* Extend heap by this amount (bytes) */
#define MAX(x, y) ((x) > (y)? (x) : (y))
/* Pack a size and allocated bit into a word */
#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))
/* Read 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)))WSIZE : 1 Words이며, 헤더/풋터의 크기
DSIZE : 2 Words이며, 블록들은 DSIZE 단위로 크기가 결정된다
CHUNKSIZE : 2^12 byte 초기 가용 블록과 힙 확장 시 추가되는 블록 크기(최소 크기)
PACK(size, alloc) ((size) | (alloc)) : 비트 연산자를 통해 size와 alloc을 표시하는 상수값을 반환한다.
GET(p) : p(포인터)가 가리키는 블록의 데이터를 반환한다.
PUT(p, val) : p(포인터)가 가리키는 블록에 value(데이터)를 입력한다
GET_SIZE(p) : 비트 연산자를 통해 헤더/풋터에 적혀있는 사이즈를 반환한다.
GET_ALLOC(p) : 비트 연산자를 통해 헤더/풋터에 현재 블록의 가용 여부를 판단한다.
bp는 현재 블록의 포인터를 나타낸다.
HDPR(bp) : 현재 블록의 헤더의 위치를 반환한다. (bp - 1words)
FTRP(bp) : 현재 블록의 풋터의 위치를 반환한다. (bp + 현 블록의 크기 - 2words)
-> bp + 현 블록의 크기 = 다음 블록의 bp를 나타냄. 이 자리에서 -2words하면 현 블록의 풋터를 나타내게됨.
NEXT_BLKP(bp) : 다음 블록의 bp의 위치를 가리킨다. (bp + 현재 블록의 크기)
-> bp -1words로 현 블록의 헤더를 읽는다.
PREV_BLKP(bp) : 이전 블록의 bp의 위치를 가리킨다. (bp - 이전 블록의 크기)
-> bp - 2words로 전 블록의 풋터를 읽는다.
- mm_init : 최초 가용 블록으로 힙 생성하기
int mm_init(void)
{
/* Create the initial empty heap */
if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
return -1;
PUT(heap_listp, 0); /* Alignment padding */
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);
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}우선 초기 할당을 위해 4워드 (16 byte)의 가용 리스트를 만든다.
sbrk 함수에서 incr = 4*WSIZE이고 할당할 수 없는 경우 void * -1을 반환한다.
1번째 칸 - 0을 적어 넣는다.
2번째 칸 - 용량 : 2word, 할당: 1(할당됨)이라는 헤더를 적어 넣는다.
3번째 칸 - 용량 : 2word, 할당: 1(할당됨)이라는 풋터를 적어 넣는다.(2번 째, 3번째 칸은 prologue block이라 칭한다.)
4번째 칸 - 용량 : 0word, 할당: 1(할당됨)이라는 헤더를 적어 넣는다. (이 칸은 앞으로 epilogue block header라 칭한다.)
heap_listp(현재 위치를 나타내는 포인터)를 2word 뒤로 옮긴다. 위의 그림과 같이 3번째 칸을 가리키게 되고, extend_heap 함수 호출
- extend_heap : 새 가용 블록으로 힙 확장하기
호출 되는 경우 2가지
1) 힙이 초기화 될 때
2) 요청한 크기의 메모리 할당을 위해 충분한 공간을 찾지 못했을 때
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 and the epilogue header */
PUT(HDRP(bp), PACK(size, 0)); /* Free block header */
PUT(FTRP(bp), PACK(size, 0)); /* Free block footer */
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */
/* Coalesce if the previous block was free */
return coalesce(bp);
}Function
extend_heap
우리는 2word ; 8byte씩 할당받을 수 있다. words가 홀수면 +1을 해줘서 공간을 할당 받는다.
*삼항 조건 연산자 : 맨 앞에 조건문이 들어가고, 그 뒤로 물음표(?)와 조건이 참 truthy이라면 실행할 식이 물음표 뒤에 들어간다.
바로 뒤 콜론(:)이 들어가며 조건이 거짓 falsy면 실행할 식이 마지막에 들어간다. 보통 if 명령문의 단축 형태로 쓰인다.
(words % 2) : 나머지가 존재하면 True/ 아니면 False
size를 mem_sbrk의 인자로 넘겨줘서 -1을 반환 받으면 (즉, mem_sbrk 함수에서 이 size가 할당 가능한 heap의 범위를 초과했다고 판단하면) 할당하지 않는다.
배정받은 가용 블록의 앞뒤에 이 블록이 가용상태라는 정보를 담은 헤더와 풋터를 배치한다. (PUT HDRP, FTRP)
다음 블록의 헤더로 가서 epilogue block header를 입력 (PUT HDRP(NEXT_BLKP(bp))
주의 : 다음 블록이라고는 했지만 실제로는 존재하지 않는 블록이다.
단지, extend_heap으로 배치한 블록 너머에 오지 않도록 배치한 블록 다음 공간을 블록이라고 가정하고 epilogue block header를 배치하는 것
- mm_free 블록을 반환(free), 경계 태그 연결을 사용해서 상수 시간에 인접 가용 블록들과 통합(coalesce)
1 void mm_free(void *bp)
2 {
3 size_t size = GET_SIZE(HDRP(bp));
4
5 PUT(HDRP(bp), PACK(size, 0));
6 PUT(FTRP(bp), PACK(size, 0));
7 coalesce(bp);
8 }
9
10 static void *coalesce(void *bp)
11 {
12 size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
13 size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
14 size_t size = GET_SIZE(HDRP(bp));
15
16 if (prev_alloc && next_alloc) { /* Case 1 */
17 return bp;
18 }
19
20 else if (prev_alloc && !next_alloc) { /* Case 2 */
21 size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
22 PUT(HDRP(bp), PACK(size, 0));
23 PUT(FTRP(bp), PACK(size,0));
24 }
25
26 else if (!prev_alloc && next_alloc) { /* Case 3 */
27 size += GET_SIZE(HDRP(PREV_BLKP(bp)));
28 PUT(FTRP(bp), PACK(size, 0));
29 PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
30 bp = PREV_BLKP(bp);
31 }
32
33 else { /* Case 4 */
34 size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
35 GET_SIZE(FTRP(NEXT_BLKP(bp)));
36 PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
37 PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
38 bp = PREV_BLKP(bp);
39 }
40 return bp;
41 }Fuction
1) mm_free
블록의 위치를 인자로 받는다. 그리고 해당 블록의 가용 여부를 0(가용상태)로 만든다.
핵심 : 블록을 가용 리스트에서 제거하는 것이 아니라 가용 상태로 만든다는 것
반환하려는 블록의 헤더와 풋터 0으로 입력
2) coalesce
앞 블록의 풋터와 뒷 블록의 헤더에서 정보를 읽어 앞 블록과 뒷 블록이 가용 상태인지 본다.(12~13 줄)
prev_alloc, next_alloc
연결을 위해 현재 블록의 사이즈를 읽어온다 (14줄)
size
Case1) 앞 블록과 뒷 블록이 모두 할당(prev_alloc && next_alloc)
- 현재 블록만 가용 상태로 변경(이미 free에서 가용 되었으므로 따로 free할 필요 없음)
Case2) 앞 블록은 할당, 뒷 블록은 가용(prev_alloc && !next_alloc)
- 현재 블록은 뒷 블록과 통합 가능
뒷 블록의 헤더를 보고 그 블록의 크기 만큼 현재 블록의 사이즈에 추가(21줄)
헤더 갱신(22줄)
풋터 갱신(23줄)
Case3) 앞 블록은 가용, 뒷 블록은 할당(!prev_alloc && next_alloc)
- 현재 블록은 앞 블록과 통합 가능
앞 블록의 헤더를 보고 그 블록의 크기 만큼 현재 블록의 사이즈에 추가(27줄)
풋터에 먼저 조정하려는 크기로 상태를 변경(28줄)
bp를 그 앞 블록의 헤더로 이동하여 헤더 갱신(29줄)
bp 자체를 그 앞 블록의 헤더로 이동(30줄)
Case4) 앞 블록과 뒷 블록 모두 가용
- 현재 블록은 앞, 뒷 블록과 통합 가능
앞 블록 헤더, 뒷 블록 푸터 까지로 사이즈 늘리기(34~35줄)
헤더부터 앞으로 가서 사이즈를 넣어주고(36줄)
푸터 뒤로 가서 사이즈를 넣어준다(37줄)
bp 자체를 그 앞 블록의 헤더로 이동(38줄)
⭐️ 주의 : 코드에서 header에 포함된 size를 기준으로 해야한다.
풋터 포인트를 구할 때, 헷갈릴 수 있지만, FTRP의 정의를 보면 헷갈리지 않을 수 있다.
FTRP(bp) : 현재 블록의 풋터의 위치를 반환한다. (bp + 현 블록의 크기 - 2words)
여기서 현 블록의 크기가 헤더에 갱신이 되었는지 안되었는지만 확인해주면된다.
ex)
Case 2의 경우 HDRP(bp)로 인해서 크기가 갱신이 되어있고, 그래서 FTRP(bp)는 현재 갱신된 크기를 말한다
Case4의 경우 HDRP(PREV_BLKP(bp))로 인해서 앞 블록의 헤더 값이 갱신되었다. 하지만 FTRP(NEXT_BLKP(bp))는 NEXT_BLKP(bp)의 헤더의 크기는 갱신이 되어있지 않기 때문에(헤더의 크기라고 편의상 말하는 것이지만, 풋터가 가리키는 블록의 크기를 말한다고 보면된다.) 앞선 갱신이 영향을 미칠 수 없다.
return : 4개 케이스 중에 적용된 것으로 bp return(참고로 bp는 위에서 정했듯 항상 블록의 헤더 뒤에 위치하는게 좋다. 연결이 끝나면 bp는 블록의 헤더에 위치해야한다.)
- 가용 리스트에서 블록 할당하기(mm_malloc)
1 void *mm_malloc(size_t size)
2 {
3 size_t asize; /* Adjusted block size */
4 size_t extendsize; /* Amount to extend heap if no fit */
5 char *bp;
6
7 /* Ignore spurious requests */
8 if (size == 0)
9 return NULL;
10
11 /* Adjust block size to include overhead and alignment reqs. */
12 if (size <= DSIZE)
13 asize = 2*DSIZE;
14 else
15 asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
16
17 /* Search the free list for a fit */
18 if ((bp = find_fit(asize)) != NULL) {
19 place(bp, asize);
20 return bp;
21 }
22
23 /* No fit found. Get more memory and place the block */
24 extendsize = MAX(asize,CHUNKSIZE);
25 if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
26 return NULL;
27 place(bp, asize);
28 return bp;
29 }Function
mm_malloc
asize : 블록 사이즈 조정
extendsize : heap에 맞는 fit이 없으면 확장하기 위한 사이즈
1) size == 0 이면 할당할 필요 없음 --> return NULL
2) size <= DSIZE --> asize = 2*DSIZE
최소 16바이트 크기의 블록을 구성
- 헤더와 풋터를 포함해서 블록 사이즈를 조정해야한다. (헤더+풋터 = 8바이트)
- 정렬 조건을 맞추기 위해(8바이트)
ex) header(4byte) + footer(4byte) + data(1byte 이상) = 9byte -> 8의 배수로 만들기 = 16byte
3) size > DSIZE --> asize = DSIZE * (( size + (DSIZE) + (DSIZE-1)) / DSIZE )
충분한 8byte의 배수 용량을 할당할 수 있도록 하는 것.
(간단하게 말하면 (요청된 용량+헤더의 크기)보다 큰 8의 배수를 찾는 과정)
find_fit함수로 적당한 크기의 가용 블록을 검색한다. place함수로 초과 부분을 분할하고 새롭게 할당한 블록의 블록 포인터를 반환(18줄)
만약 적당한 가용 블록을 찾지 못한다면 extend_heap 함수로 heap을 확장하여 추가 확장 블록을 배정한다. (extendsize/WSIZE는 칸의 갯수를 말한다.) 만약 heap을 확장하는 것에 성공하면 블록을 배치하고 bp를 반환한다. (extend_heap에서 힙을 확장하는 데 실패하면 NULL을 반환하게 된다. 그래서 bp == NULL이 되면 배치를 하지 않고 NULL을 반환한다.)(24~28줄)
- 적절한 가용 블록 리스트 검색(find_fit)
1 static void *find_fit(size_t asize)
2 {
3 /* First-fit search */
4 void *bp;
5
6 for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
// init에서 쓴 heap_listp를 쓴다. 처음 출발 후, 다음 block의 첫번 째 헤더 뒤 위치다.
// for문이 계속 돌면 epilogue header까지 간다. epilogue header는 0이니까 종료된다.
7 if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
//이 블록이 가용하고(not 할당) 내가 갖고 있는 asize를 담을 수 있으면
8 return bp; // 블록 위치 바로 리턴
9 }
10 }
11 return NULL; /* No fit */
12 #endif
13 }탐색 방법 3가지
- first fit : 가용 블록 리스트를 처음부터 검색해서 크기가 맞는 첫번째 가용 블록을 선택
- next fit : 검색을 리스트의 처음에서 시작하는 대신, 이전 검색이 종료된 지점에서 검색을 시작
- best fit : 모든 가용블록을 검사해서 크기가 맞는 가장 작은 블록을 선택
Function
find_fit(First fit)
우선 for문으로 탐색한다. bp는 heap의 시작점을 가리키는 heap_listp에서 시작하여, 헤더를 읽는다.
만약(해당 헤더의) 블록이 할당되어있지 않고(GET_ALLOC 함수로 판단)
사이즈도 원하는 크기(asize)보다 크다면 (GET_SIZE로 판단) bp를 반환한다.
그러면 위의 mm_malloc에서 해당 bp에 데이터를 배치할 것.
만약 적절한 헤더가 아니라면 다음 블록의 헤더로 이동해서 같은 판단 작업을 수행하고,
움직일 수 없게 되면(GET_SIZE(HDRP(bp))>0이 아닐 때(힙의 끝점에 0/1로 표시한 epilogue header가 있는 것을 기억해야함)
NULL을 반환. (NULL을 반환하면, mm_malloc함수에서 extend heap으로 확장할 것)
- 데이터 할당할 가용 블록의 bp와 배치 용량을 할당(place)
1 static void place(void *bp, size_t asize)
// 들어갈 위치를 포인터로 받는다. (find fit에서 찾은 bp) 크기는 asize로 받음.
2 {
3 size_t csize = GET_SIZE(HDRP(bp));
4 // 현재 있는 블록 사이즈
5 if ((csize - asize) >= (2*DSIZE)) {
// 현재 블록 사이즈 안에서 asize를 넣어도 2*DSIZE(헤더와 풋터를 감안한 최소 사이즈)만큼 남으면
// 다른 data를 넣을 수 있음
6 PUT(HDRP(bp), PACK(asize, 1));
// 헤더 위치에 asize만큼 넣고 1(alloc)로 상태 변환. 원래 헤더 사이즈에서 지금 넣으려고 하는 사이즈(asize)로 갱신.(자르는 효과)
7 PUT(FTRP(bp), PACK(asize, 1));
// 풋터 위치도 변경
8 bp = NEXT_BLKP(bp);
// regular block만큼 하나 이동해서 bp 위치 갱신
9 PUT(HDRP(bp), PACK(csize-asize, 0));
// 나머지 블록(csize-asize) 다 가용하다(0)하다라는 걸 다음 헤더에 표시
10 PUT(FTRP(bp), PACK(csize-asize, 0));
// 풋터에도 표시
11 }
12 else { // 현재 블록 사이즈 안에서 asize를 넣으면 2*DSIZE보다 작으면 분할할 필요 없음
13 PUT(HDRP(bp), PACK(csize, 1));
14 PUT(FTRP(bp), PACK(csize, 1));
15 }
16 }Function
place(void *bp, size_t asize)
csize = 해당 가용 블록의 전체 크기
만약 csize와 asize 차이가 16byte(4칸)보다 작다면 (12번째 줄 else문)
해당 블록을 통째로 사용해서, 해당 블록의 첫 자리에는 헤더를, 끝 자리에는 풋터를 놓는다.
헤더와 풋터만 놔도 2칸을 다 사용해버리기 때문에 실제로 데이터를 배치할 수 있는 공간은 2칸보다 큰 2의 배수인 4칸이 된다.
(헤더 + 데이터 2칸 + 풋터)
그래서 만약 가용 블록과 요구되는 용량(데이터+헤더+풋터)의 차이가 4칸이상이라면, 통째로 쓰기에는 아까우므로 분리를 해줘야한다.
요청 용량만큼 블록을 배치하고 풋터를 배치한다.(6~7줄)
남은 블록에 헤더와 풋터를 배치한다 (8~10줄)
출처 :