-
CSAPP : Allocator 구현(종합 설계, Explict)개발/Malloc 2022. 5. 11. 20:07
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
'개발 > Malloc' 카테고리의 다른 글
CSAPP : Allocator 구현(종합 설계) (0) 2022.05.08 CSAPP : 동적 메모리 할당 (9.9) (0) 2022.05.07