CSAPP : Allocator 구현(종합 설계, Explict)
1. 명시적 가용 리스트 사용 이유
앞선 글에서 Implicit Allocator를 설계 했다.
블록 할당 시간이 전체 힙 블록의 수에 비례하기 때문에 Implicit 가용 리스트는 범용 할당기에 적합하지 않다.
(why? : find_fit 함수를 확인하면 블록이 가용하고, 내가 갖고 있는 asize를 담을 수 있으면 할당을 할 수 있는데 이를 확인하려면 전체 힙 블록의 수를 하나씩 확인해가야하고 최악의 경우에는 전체 힙 블록을 다 탐색해야할 수 있다.)
이를 보완한 것이 명시적 가용 리스트(Explicit Free List)이다.
- 가용 블록들을 명시적 자료구조로 구성
- 포인터들을 가용 블록의 본체 내에 저장하여 구현
- 가용 블록 내에 pred(predecessor)와 succ(successor) 포인터를 포함하는 이중 연결 가용 리스트로 구성
- 이러한 이중 연결 가용 리스트를 사용하면 first fit 할당 시간 --> 가용 블록의 수에 비례하는 것으로 줄임
단점 : 일반적으로 가용 블록들이 충분히 커서 모든 필요한 포인터 뿐만 아니라 헤더, 추가적으로 풋터까지 포함해야한다.
그 결과, 최소 블록 크기가 커지고 잠재적인 내부 단편화 가능성이 커진다
2. Explicit Free List 구현
1) IDEA
- 가용 블록끼리 포인터로 연결해 다음 블록 위치를 알 수 있음.
- 가용 블록 안의 Payload자리에 앞 가용 블록(predecessor block)와 뒷 가용 블록(successor block)의 주소를 저장
- 하나의 이중 연결 리스트를 만들어서 가용 블록을 연결
- 다음 가용 블록은 Implicit 방식과 달리 메모리 내에서 물리적으로 연속적이지 않아도 된다.
- 주소 상으로 인접 블록이 아니더라도 포인터 주소를 이용해서 위치를 찾아간다.
2) 할당(Allocation)
- 해당 가용 리스트를 분할한 다음 새 가용 블록을 기존 가용 블록과 링크되었던 이전(prev), 다음(next) 블록과 연결
3) 가용(Free)
- 새로 반환된 가용 블록을 free list를 어디에 연결?
-> LIFO(Last in First Out) 방안
1) Free list 처음에 새 반환 블록을 넣는다.(Stack)
-> Address Ordered 방안
1) Free list 주소 순으로 연결 (이전 블록 주소 < 현재 블록 주소 < 다음 블록 주소)
2) 단편화 발생 확률은 낮아지나 탐색 시간이 길어진다. (주소 순으로 연속적으로 연결하니 일일이 찾아가면서 해야한다)
3-1) LIFO(Last in First Out) 방안
(1) Case 1 : 반환 블록 양쪽이 할당되어 있을 때
- 해당 블록만 가용 상태로 반환하면 되니 추가 작업이 필요 없고, 연결된 새 가용 블록을 Free list에만 추가해주면 된다.
(2) Case 2 : 반환 블록 직전이 할당 블록, 직후가 가용 블록일 때
- 직후 블록을 Free list에서 떼어낸 다음 현재 반환할 블록 뒤로 연결한다.
- 새로 연결한 블록을 Free list의 root와 연결한다.(Last In 구조)
(3) Case 3 : 반환 블록 직전이 가용블록, 직후가 할당 블록일 때
- 직전 블록을 Free list에서 떼어낸 다음 반환 블록과 연결한다.
- 새 연결할 블록을 Free list의 root와 연결한다.
(4) Case 4 : 반환 블록 직전/직후 전부 다 가용 블록일 때
- 직전 블록/직후
- 새 블록을 Free list의 root와 연결한다
3. Malloc 구현 코드
memlib.c
// --------------------- 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; // 힙의 처음을 가리키는 포인터
static char *mem_brk; // 힙의 마지막 자리를 가리키는 포인터
static char *mem_max_addr; // MAX_HEAP의 끝 자리를 나타낸다. 이 이상으로는 할당할 수 없음
/* *mem_init - Initilaize the memory system model */
// 최초 가용 블록으로 힙 생성하기
void mem_init(void)
{
mem_heap = (char *)Malloc(MAX_HEAP); // MAX_HEAP 크기 만큼 할당
mem_brk = (char *)mem_heap; // 힙의 처음 가리키는 포인터로 brk 정의 --> 마지막 자리를 가리킬 것이다.
mem_max_addr = (char *)(mem_heap + MAX_HEAP); // 힙의 처음을 가리키는 포인터 + MAX_HEAP size이므로 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; // 전에 있던 brk값으로 mem_sbrk의 리턴 값이 된다.
// incr(용량)이 들어왔을 때, 음수거나, MAX_HEAP을 초과하면 오류 메시지 반환
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;
}mm.c
mm파일을 수정하여 Malloc을 구현하는 것이다.
먼저 코드 전체에서 사용할 상수와 매크로를 정의
매크로란 코드에서 반복적으로 선언(사용)되는 숫자나 함수를 미리 정의하여 의미가 서로 다른 것이 섞여서 사용되면 의미가 헷갈리기 때문에 그 부분을 방지해줌. 또한, 코드가 길어지고 복잡해졌을 때 코드 입력 실수를 줄일 수 있다.
#define은 컴파일 직전에 처리되므로 전처리기 과정을 거치면 매크로가 정의된다.
보통 전처리기는 반복되는 값이나 작업을 미리 정의할 때 사용하며 컴파일 옵션 설정이나 조건부 컴파일도 가능하다.
- 매크로 선언
#define 매크로명 매크로하고자 하는 대상
- 기존에 선언된 매크로의 이름을 재정의
#define 새 매크로명 기존 매크로명
- 매크로 해제
#undef 매크로 이름
- 매크로
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
/* 메모리 할당 시 기본적으로 header와 footer를 위해 필요한 더블워드만큼의 메모리 크기 */
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
/* Basic constants and macros */
#define WSIZE 4 /* Word and header/footer size (bytes) */
#define DSIZE 8 /* Double word size (bytes) */
#define MINIMUM 16 /* Initial Prologue block size, header, footer, PREC, SUCC */
#define CHUNKSIZE (1<<12) /* Extend heap by this amount : 4096bytes -> 4k(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))) // (char*)(bp) + GET_SIZE(지금 블록의 헤더값)
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) // (char*)(bp) - GET_SIZE(이전 블록의 풋터값)
/* Free List 상에서의 이전, 이후 블록의 포인터를 리턴한다. */
#define PREC_FREEP(bp) (*(void**)(bp)) // 이전 블록의 bp
#define SUCC_FREEP(bp) (*(void**)(bp + WSIZE)) // 이후 블록의 bp
/* define searching method for find suitable free blocks to allocate*/
/* global variable & functions */
static char* heap_listp = NULL; // 항상 prologue block을 가리키는 정적 전역 변수 설정
static char* free_listp = NULL; // free list의 맨 첫 블록을 가리키는 포인터- int mm_init(void)
❖ Explicit allocator 의 초기 힙은 6word의 메모리를 가진다.
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void)
{
/* 메모리에서 6words를 가져오고 이걸로 빈 가용 리스트 초기화 */
/* padding, prol_header, prol_footer, PREC, SUCC, epil_header */
if ((heap_listp = mem_sbrk(6*WSIZE)) == (void*)-1){
return -1;
}
PUT(heap_listp,0); /* Alignment padding */
PUT(heap_listp + (1*WSIZE), PACK(MINIMUM,1)); /* Prologue header */
PUT(heap_listp + (2*WSIZE), NULL); // prologue block안의 PREC 포인터 NULL로 초기화
PUT(heap_listp + (3*WSIZE), NULL); // prologue block안의 SUCC 포인터 NULL로 초기화
PUT(heap_listp + (4*WSIZE), PACK(MINIMUM,1)); /* Prologue footer */
PUT(heap_listp + (5*WSIZE), PACK(0,1)); /* Epilogue header */
free_listp = heap_listp + 2*WSIZE; //free_listp를 탐색의 시작점으로 둔다
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
// 그 후 CHUNKSIZE만큼 힙을 확장해 초기 가용 블록을 생성한다
if (extend_heap(CHUNKSIZE/WSIZE)==NULL)
return -1;
return 0;
}- static void* coalesce(void* bp)
// coalesce(bp) : 해당 가욕 블록을 앞뒤 가용 블록과 연결하고 연결된 가용 블록의 주소를 리턴한다.
static void *coalesce(void *bp){
// 직전 블록의 footer, 직후 블록의 header를 보고 가용 여부 확인
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 : 앞, 뒷 블록 모두 할당 -> 해당 블록만 free list에 넣어준다
// Case 2 : 앞 블록 할당, 뒷 블록 가용
if (prev_alloc && !next_alloc){
removeBlock(NEXT_BLKP(bp)); // free 상태였던 뒷 블록 free list에서 제거
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){
removeBlock(PREV_BLKP(bp)); // free 상태였던 앞 블록 free list에서 제거
size+= GET_SIZE(HDRP(PREV_BLKP(bp))); // 이전 블록의 헤더만큼 사이즈 추가
bp = PREV_BLKP(bp);
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
}
//Case 4 : 앞 블록 가용, 뒷 블록 가용
else if(!prev_alloc && !next_alloc) {
removeBlock(NEXT_BLKP(bp)); // free 상태였던 뒷 블록 free list에서 제거
removeBlock(PREV_BLKP(bp)); // free 상태였던 앞 블록 free list에서 제거
size+= GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp))); // 이전 블록 헤더, 다음 블록 푸터 까지로 사이즈 늘리기
bp = PREV_BLKP(bp);
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
}
// 연결된 새 가용 블록을 free list에 추가한다
putFreeBlock(bp);
return bp;
}- void putFreeBlock(void* bp)
순서(Sequence)
1) 현재 블록
PREC : NULL
SUCC : NULL
free_listp : PREC의 위치, 시작점이라고 생각
2) 가용 블럭 추가됨(Last In)
추가된 블록을 기준으로 생각해보자
PREC(현재 bp) : NULL (현재 앞에 가리킬 것이 없기 때문에)
SUCC(현재 bp) : 다음 블록(원래 이전에 있던 것)의 bp(블록 포인터)를 가리켜야함
PREC(이전 bp=free_listp) : 현 블록의 bp를 가리켜야함
다음에 들어올 것을 감안하여
free_listp위치도 현 bp값으로 바꿔줘야함.
이를 위해서, 이중 포인터 개념 필요
참고 : https://velog.io/@letsbebrave/c-%EC%9D%B4%EC%A4%91%ED%8F%AC%EC%9D%B8%ED%84%B0
무언가 형식 지정자 때문에 필요한 것 같다.
/*
putFreeBlock(bp) : 새로 반환되거나 생성된 가용 블록을 free list의 첫 부분에 넣는다.
*/
// Last in : 선입 구조
// free_listp : 뒷 블록의 bp
// bp : 현 블록의 bp
void putFreeBlock(void* bp){
SUCC_FREEP(bp) = free_listp; // 뒷블록의 bp값 = free_listp
PREC_FREEP(bp) = NULL; // 앞블록의 bp값 = NULL(앞블록은 선입 구조이기 때문에 없음)
PREC_FREEP(free_listp) = bp; // 뒷블록 기준-> 앞블록(현블록)의 bp값 = bp
free_listp = bp; // free_listp는 다음에 들어올 것을 염두에 두고 bp로 갱신
}- void removeBlock(void *bp)
/*
removeBlock(bp) : 할당되거나 연결되는 가용 블록을 free list에서 없앤다.
*/
void removeBlock(void *bp){
//free list의 첫번째 블록을 없앨 때
if (bp == free_listp){
PREC_FREEP(SUCC_FREEP(bp)) = NULL; // 앞에 것의 PREC이 가리키는 값을 NULL로 바꿔준다.
free_listp = SUCC_FREEP(bp); //free_listp의 값을 뒤의 bp로 바꿔준다
}
// free list 안에서 없앨 때
else{
SUCC_FREEP(PREC_FREEP(bp)) = SUCC_FREEP(bp); //앞 블록의 SUCC가 없애주는 블록의 SUCC값을 가리키도록 한다.
PREC_FREEP(SUCC_FREEP(bp)) = PREC_FREEP(bp); //뒷 블록의 PREC가 없애주는 블록의 PREC값을 가리키도록 한다.
}
}bp를 인자로 받았을 때
1) free list의 첫번째 블록이라면
- 앞에 것의 PREC이 가리키는 값을 NULL로 바꿔준다.
- free_listp의 값을 뒤의 bp로 바꿔준다
2) free list의 첫번째 블록이 아니라면
- 앞 블록의 SUCC가 없애주는 블록의 SUCC값을 가리키도록 한다.
- 뒷 블록의 PREC가 없애주는 블록의 PREC값을 가리키도록 한다.
- static void* find_fit(size_t asize)
static void *find_fit(size_t asize)
{
/* First-fit search */
void *bp;
// free list에서 가용 블럭을 차례로 확인한다. 맨 뒤의 프롤로그 블록이 유일하게 할당되었으므로 만나면 탐색 종료
for (bp = free_listp; GET_ALLOC(HDRP(bp)) != 1; bp = SUCC_FREEP(bp)) {
if (asize <= GET_SIZE(HDRP(bp))) {
//이 블록이 내가 갖고 있는 asize를 담을 수 있으면
return bp; // 블록 위치 바로 리턴
}
}
return NULL; /* No fit */
}First fit 방식으로 구현.
Free list에서 유일한 할당 블록은 맨 뒤의 프롤로그 블록이므로, 할당 블록을 만났다는 뜻은 모든 Free list 노드를 다 훑은 것으로 봄
(== 종료 조건)
- static void place(void* bp, size_t asize)
static void place(void *bp, size_t asize)
// 들어갈 위치를 포인터로 받는다. (find fit에서 찾은 bp) 크기는 asize로 받음.
{
size_t csize = GET_SIZE(HDRP(bp));
// 현재 있는 블록 사이즈
removeBlock(bp);
if ((csize - asize) >= (2*DSIZE)) {
// 현재 블록 사이즈 안에서 asize를 넣어도 2*DSIZE(헤더와 풋터를 감안한 최소 사이즈)만큼 남으면
// 다른 data를 넣을 수 있음
PUT(HDRP(bp), PACK(asize, 1));
// 헤더 위치에 asize만큼 넣고 1(alloc)로 상태 변환. 원래 헤더 사이즈에서 지금 넣으려고 하는 사이즈(asize)로 갱신.(자르는 효과)
PUT(FTRP(bp), PACK(asize, 1));
// 풋터도 변경
bp = NEXT_BLKP(bp);
// regular block만큼 하나 이동해서 bp 위치 갱신
PUT(HDRP(bp), PACK(csize-asize, 0));
// 나머지 블록(csize-asize) 다 가용하다(0)하다라는 걸 다음 헤더에 표시
PUT(FTRP(bp), PACK(csize-asize, 0));
// 풋터에도 표시
putFreeBlock(bp);
// free list 첫번째에 분할된 블럭을 넣는다.
}
else { // 현재 블록 사이즈 안에서 asize를 넣으면 2*DSIZE보다 작으면 분할할 필요 없음
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}직접적으로 힙에 할당 메모리를 넣는 작업
1) 할당할 수 있는 free 블록을 Free list에서 없애주고
2) 할당 후 분할이 되었다면, Free list 첫번째에 분할된 블럭을 넣어야한다.
- void *mm_realloc(void *ptr, size_t size)
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
// 조정할 블록 위치와 요청 사이즈를 인자로 받는다.
void *mm_realloc(void *ptr, size_t size)
{
void *oldptr = ptr; // 크기를 조절하고 싶은 힙의 시작 포인터
void *newptr; // 크기 조절 뒤의 새 힙의 시작 포인터
size_t copySize; // 복사할 힙의 크기
newptr = mm_malloc(size);
if (newptr == NULL) // 요청 사이즈가 0보다 작거나 같으면 반환을 한다.
return NULL;
// copySize = 조절하고 싶은 힙의 크기
copySize = GET_SIZE(HDRP(oldptr));
// 원래 메모리 크기보다 적은 크기를 realloc하면 크기에 맞는 메모리만 할당되고 나머지는 안된다.
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize); // newptr에 oldptr를 시작으로 copySize만큼의 메모리 값을 복사한다.
mm_free(oldptr); // 기존의 힙을 반환한다.
return newptr;
}realloc 함수는 malloc으로 할당 받은 메모리 영역을 size를 변경하여 재할당받는 역할을 한다.
주의할 점은 할당된 블록을 늘리거나 줄이는 것이 아닌 새롭게 원하는 size를 할당 받고 전에 것을 free하는 형식이다.
출처 :
https://github.com/dkkim0122/malloc-lab/blob/main/mm.c