Implicit List
💡 Implicit List 기본 아이디어
1) 블록 할당
- 블록의
사용 여부와 블록의사이즈를 각 블록 내부의 header 및 footer에 저장한다. - 리스트를 처음부터 검색해서
크기가 맞는 첫번째 가용 블록을 선택한다. (First fit) - 선택한 가용 블록이 사용할 사이즈보다 큰 사이즈를 가지고 있다면,필요한 사이즈만큼만 사용하고
나머지는 분할하여 또다른 가용 블록으로 남겨둔다.
2) 블록 반환
- 블록이 반환되면 주소상으로 인접한 블록을 확인해서 빈 블록이 있다면 연결하여 더 큰 블록으로 만들어서 가용 블록으로 만든다.
깃허브로 소스코드 확인
0. 기본 상수와 매크로
- 👩🏻💻 source code
/* 기본 상수 */ #define WSIZE 4 #define DSIZE 8 #define CHUNKSIZE (1 << 12) /* 매크로 */ #define MAX(x, y) ((x) > (y) ? (x) : (y)) #define PACK(size, alloc) ((size) | (alloc)) #define GET(p) (*(unsigned int *)(p)) #define PUT(p, val) (*(unsigned int *)(p) = (val)) #define GET_SIZE(p) (GET(p) & ~0x7) #define GET_ALLOC(p) (GET(p) & 0x1) #define HDRP(bp) ((char *)(bp) - WSIZE) #define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) #define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) #define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
기본 상수와 매크로
- WSIZE, DSIZE, CHUNKSIZE, MAX
#define WSIZE 4
- 1개의 word 사이즈
#define DSIZE 8
- 2개의 word 사이즈
#define CHUNKSIZE (1 << 12)
- heap을 한번 늘릴 때 필요한 사이즈
- 1 << 12 ⇒ 2의 12승 4096 ⇒ 4KB
- heap 메모리를 확장할 때 한 번에 4KB씩 확장하도록 정의한다.
#define MAX(x, y) ((x)>(y)? (x): (y))
- 주어진 값 중 어느 것이 더 클지 정하는 MAX 함수
가용 리스트에 접근하고 방문하는 매크로
- PACK, GET, PUT, GET_SIZE, GET_ALLOC, HDRP, FTRP, NEXT_BLKP, PREV_BLKP
PACK
- 블록 헤더에 사이즈와 할당여부를 넣을 함수
- alloc : 가용여부 (ex. 000) / size : block size를 의미. =>합치면 온전한 주소가 나온다.
GET
- p가 참조하는 워드를 읽어서 리턴
- p는 대개 (void *)포인터이기 때문에 직접적으로 역참조할 수 없어 type casting 필요
PUT
- p가 가리키는 워드에 val 저장
GET_SIZE
- 헤더 또는 푸터의 사이즈 리턴
GET_ALLOC
- 가용 여부 리턴
HDRP / FTRP
- 각각 현재 블록의 헤더와 풋터를 가리키는 포인터를 리턴
NEXT_BLKP/ PREV_BLKP
- 각각 다음과 이전 블록의 블록 포인터(bp)를 리턴
1. 초기 가용 리스트 만들기
- 대표 함수(1) :
mm_init()- 설명 : 초기화를 완료하고 할당과 반환 요청을 받을 준비를 완료한다.
- 리턴
int: 성공 시 0, 실패 시 -1
↳ 내부 함수(2) : extend_heap(size)
- 설명 : 힙의 크기를 확장한다.
- 파라미터
size: 확장하고자 하는 힙 사이즈 (words)
- 리턴
void*확장하며 생긴 가용 블록의 포인터
mm_init()
-
👩🏻💻 source code
int mm_init(void) { char *heap_listp; if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1) return -1; PUT(heap_listp, 0); PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); heap_listp+= (2*WSIZE); if (extend_heap(CHUNKSIZE / WSIZE) == NULL) return -1; return 0; } -
초기에 ‘정렬 패딩(unused) + 프롤로그 header + 프롤로그 footer + 에필로그 header’를 담기 위해 4워드 크기의 힙을 생성한다.
-
생성 후 CHUNKSIZE만큼 추가 메모리를 요청해 힙의 크기를 확장한다.
-
순서 확인하기
- 먼저 초기 힙 영역을 할당.(
mem_sbrk) - 미사용 패딩을 삽입
- prologue header 생성 → prologue footer 생성 → epilogue header 생성
- 초기 힙의 포인터를 prologue header 뒤로 옮긴다. (포인터는 항상 어느 블록이든 header 뒤에 위치)
- heap을 한번 특정 사이즈만큼 증가
- 먼저 초기 힙 영역을 할당.(
💡 미사용 패딩을 사용하는 이유
- prologue block 다음에 오는 실제 필요한 데이터를 더블 워드 정렬해주기 위해서
- 미사용 패딩을 사용해야 prologue block 뒤의 실제 데이터 블록들이 8의 배수로 정렬될 수 있다.
extend_heap(size)
- 👩🏻💻 source code
static void *extend_heap(size_t words) { char *bp; size_t size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; if ((long)(bp = mem_sbrk(size)) == -1) return NULL; PUT(HDRP(bp), PACK(size, 0)); PUT(FTRP(bp), PACK(size, 0)); PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); return coalesce(bp); }
- extend_heap이 호출되는 경우
- CASE 1. 힙이 초기화 될 때(init) 앞으로 블록을 넣기 위해 사이즈를 한번 늘리는 것 → ☑️ 현재 경우
- CASE 2.
mm_malloc이 적합한 fit 공간을 찾지 못했을
- 힙은 더블 워드 정렬 제한 조건에 따라 더블 워드 경계에서 시작한다.
- extend_heap으로 가는 모든 호출은 더블 워드(8byte)의 배수인 블록을 리턴한다.
mem_sbrk또한 더블 워드로 정렬된 메모리 블록을 리턴한다.
- 새로 추가된 사이즈 만큼의 가용 블록을 생성한다.
- 가용 블록의 헤더, 푸터 생성
- 에필로그의 위치를 확장된 힙 사이즈에 맞춰서 맨 뒤에 새로 생성한다.
- 만약 이전 힙이 가용 블록이라면 힙을 확장하며 만들어진 현재 가용 블록과 합친다.
2. 블록 반환과 연결
coalesce(bp)
- 설명 : 인접 가용 블록들을 경계 태그 연결 기술을 사용해서 통합한다.
- 리턴
int: 성공 시 0, 실패 시 -1
- 👩🏻💻 source code
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)); // @pb : 이전 블록, @cb : 현재 블록, @nb : 다음 블록 // [CASE 1] : pb, nb - 둘 다 할당 상태 if (prev_alloc && next_alloc) { return bp; } // [CASE 2] : pb - 할당 상태 / nb - 가용 상태 // resize block size : cb + nb else if (prev_alloc && !next_alloc) { size += GET_SIZE(HDRP(NEXT_BLKP(bp))); // 현재 블록 사이즈에 다음 블록 사이즈 더함 PUT(HDRP(bp), PACK(size, 0)); PUT(FTRP(bp), PACK(size, 0)); } // [CASE 3] : pb - 가용 상태 / nb - 할당 상태 // resize block size : pb + cb else if (!prev_alloc && next_alloc) { 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); } // [CASE 4] : pb - 가용 상태 / nb - 가용 상태 // resize block size : pb + nb else { size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp))); PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0)); bp = PREV_BLKP(bp); } return bp; }
coalesce 함수에서는 현재 블록이 살필 수 있는 4가지 케이스를 다뤄야 한다.
- 이전 블록과 다음 블록이 모두 할당되어 있는 경우 → 합칠 수 없다.
- 이전 블록은 할당상태이지만, 다음 블록은 가용상태인 경우 → 다음 블록과 합칠 수 있다.
- 이전 블록은 가용상태이고, 다음 블록은 할당 상태인 경우 → 이전 블록과 합칠 수 있다.
- 이전 블록이 가용상태이고, 다음 블록도 가용 상태인 경우 → 이전,다음 블록 모두 합칠 수 있다.
💡 bp는 항상 블록의 헤더 뒤에 위치하는게 좋기 때문에 연결이 끝나면 bp는 블록의 헤더에 위치해야 한다.
mm_free(bp)
- 설명 : 요청한 블록을 반환한다.
- 파라미터
void*: 반환하려는 블록의 포인터
- 👩🏻💻 source code
void mm_free(void *bp){ size_t size = GET_SIZE(HDRP(bp)); PUT(HDRP(bp),PACK(size,0)); PUT(FTRP(bp), PACK(size,0)); coalesce(bp); } - 이전에 할당한 블록을 해당 함수를 호출해서 반환한다.
- 요청한 블록(bp)를 반환하고
coalesce(bp)를 호출하여 인접 가용 블록을 연결한다.
💡핵심은 블록을 가용 리스트에서 제거하는게 아니라 가용상태로 만들어버린다는 것
3. 블록 할당
대표 함수(1) : mm_malloc(size)
- 설명 : 새 블록을 할당한다.
- 리턴
int: 성공 시 0, 실패 시 -1
- 👩🏻💻 default code
void *mm_malloc(size_t size) { int newsize = ALIGN(size + SIZE_T_SIZE); void *p = mem_sbrk(newsize); if (p == (void *)-1) return NULL; else { *(size_t *)p = size; return (void *)((char *)p + SIZE_T_SIZE); } } - 👩🏻💻 source code
void *mm_malloc(size_t size) { size_t asize; size_t extendsize; char *bp; if (size == 0) return NULL; if (size <= DSIZE) asize = 2 * DSIZE; else asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE); bp = next_fit(asize); // Choice fit-method : first_fit, next_fit, best_fit if (bp != NULL) { place(bp, asize); next_heap_listp = bp; return bp; } extendsize = MAX(asize, CHUNKSIZE); if ((bp = extend_heap(extendsize/WSIZE)) == NULL) return NULL; place(bp, asize); next_heap_listp = bp; return bp; }
- 사이즈 조정 : 할당 요청이 들어오면(malloc 함수 호출) 요청 받은
size를 조정한다. → 블록의 크기는 적어도 16바이트 이상이어야 한다. (header 4bytes + footer 4bytes + payload 8bytes) → 블록의 크기는 8의 배수이어야 하므로(정렬 요건), 항상 8의 배수가 되도록 올림 처리한다.
- 할당기가 요청한 크기를 조정하면 할당할 가용 블록이 가용 리스트에 있는지 탐색한다(
find_fit) → 맞는 블록을 찾으면 요청한 블록을 배치한다. (place) 필요하면 기존 블록을 분할한다. → 맞는 블록을 찾지 못하면 힙을 늘리고 다시 배치한다.
↳ 내부 함수(2) : find_fit(size)
- 설명 : first-fit, next-fit, best-fit 방식으로 가용 블록을 탐색한다.(선택)
- 파라미터
size: 필요한 가용 블록의 사이즈 (byte)
- 리턴
void*가용 블록의 포인터- 실패 시 null
💡 가용 블록 탐색 방식
first fit: 가용블럭 리스트를 처음부터 검색해서 크기가 맞는 첫번째 가용 블록을 선택
next fit: 검색을 리스트의 처음에서 시작하는 대신, 이전 검색이 종료된 지점에서 검색을 시작
best fit: 모든 가용블록을 검새해서 크기가 가장 맞는 가장 작은 블록을 선택
↳ 방법1 : first_fit
bp = heap_listp:bp변수를 가용 블록 리스트의 시작인heap_listp로 초기화GET_SIZE(HDRP(bp)) > 0: 현재 가용 블록의 크기가 0보다 큰지를 확인. 이 조건은 힙의 끝을 나타내는 에필로그 블록에 도달하기 전까지 루프를 실행bp = NEXT_BLKP(bp): 다음 가용 블록으로 이동.NEXT_BLKP매크로를 사용하여 현재 블록의 다음 블록 주소로 이동- 루프 내부에서 현재 블록이 가용 상태이고, 요청한 크기보다 크거나 같은지를 확인
!GET_ALLOC(HDRP(bp)): 현재 블록의 헤더가 가리키는 블록이 할당되지 않았는지 확인(asize <= GET_SIZE(HDRP(bp))): 요청한 크기(asize)가 현재 블록의 크기보다 작거나 같은지 확인
- 조건이 만족하면 현재 블록 포인터를 반환하고 함수를 종료
- 만약 적합한 가용 블록이 없으면 루프를 종료하고
NULL을 반환
↳ 방법2 : next_fit
- 👩🏻💻 source code
static void *next_fit(size_t asize) { char *bp; for (bp = NEXT_BLKP(next_heap_listp); GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) return bp; for (bp = heap_listp; bp <= next_heap_listp; bp = NEXT_BLKP(bp)) if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) return bp; return NULL; }
bp = NEXT_BLKP(next_heap_listp):bp변수를 다음 블록의 시작인next_heap_listp로 초기화GET_SIZE(HDRP(bp)) > 0: 현재 가용 블록의 크기가 0보다 큰지를 확인. 이 조건은 힙의 끝을 나타내는 에필로그 블록에 도달하기 전까지 루프를 실행bp = NEXT_BLKP(bp): 다음 가용 블록으로 이동.NEXT_BLKP매크로를 사용하여 현재 블록의 다음 블록 주소로 이동- 루프 내부에서 현재 블록이 가용 상태이고, 요청한 크기보다 크거나 같은지를 확인
!GET_ALLOC(HDRP(bp)): 현재 블록의 헤더가 가리키는 블록이 할당되지 않았는지 확인(asize <= GET_SIZE(HDRP(bp))): 요청한 크기(asize)가 현재 블록의 크기보다 작거나 같은지 확인
- 조건이 만족하면 현재 블록 포인터를 반환하고 함수를 종료
- 만약 적합한 가용 블록이 없으면 루프를 종료하고
NULL을 반환
💡 왜 bp 선언의 자료형이 다를까?
first_fit 함수는 임의의 데이터 타입을 가리킬 수 있는 포인터를 반환하고, next_fit 함수는 다음 블록을 가리키는 포인터로 바이트 단위로 이동할 수 있도록 char * 형 포인터를 사용한다.
↳ 방법3 : best_fit
- 👩🏻💻 source code
static void *best_fit(size_t asize) { void *bp; void *best_fit = NULL; for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) if (!best_fit || GET_SIZE(HDRP(bp)) < GET_SIZE(HDRP(best_fit))) best_fit = bp; return best_fit; }
best_fit이 아직 설정되지 않았거나 (GET_SIZE(HDRP(bp)) < GET_SIZE(HDRP(best_fit))), 현재 블록이 best_fit보다 더 작은 경우, best_fit을 현재 블록으로 업데이트한다.
↳ 내부 함수(3) : extend_heap(size)
- 설명 : 힙의 크기를 확장한다.
- 파라미터
size: 확장하고자 하는 힙 사이즈 (words)
- 리턴
- 확장하며 생긴 가용 블록의 포인터
↳ 내부 함수(4) : place(bp, size)
- 설명 : 찾은 가용 블록에 대해 할당 블록과 가용 블록으로 분할한다.
- 파라미터
bp: 찾은 가용 블록의 포인터size: 블록 할당에 필요한 사이즈 (byte)
- 👩🏻💻 source code
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); next_heap_listp = 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)); next_heap_listp = NEXT_BLKP(bp); } } - 가용 공간을 찾고 해당 가용 블록이 할당하려는 메모리 공간보다 클 경우 할당 블록과 가용 블록으로 블록을 분할한다.
- 할당하려는 메모리 공간이 만약 헤더와 푸터 오버헤드 사이즈(8byte) + 데이터(최소 8byte) 보다 크거나 같은 경우에는 앞 부분을 할당 공간으로, 뒷 부분을 가용 공간을 분할한다.
- 만약 할당하려는 메모리 공간이 헤더와 푸터 오버헤드 사이즈(8byte) + 데이터(최소 8byte) 보다 작은 경우에는 가용 블록 전체를 할당 블록으로 만든다.
4. 블록 재할당
mm_realloc(bp, size)
- 설명 : 이전에 할당한 메모리의 크기를 재조정한다.
- 파라미터
bp: 재조정하려는 공간의 포인터size: 재조정하려는 사이즈
- 리턴
void*: 재조정한 메모리의 포인터
- 👩🏻💻 source code
void *mm_realloc(void *ptr, size_t size) { if (ptr == NULL) { return mm_malloc(size); } if (size == 0) { mm_free(ptr); return NULL; } size_t old_size = GET_SIZE(HDRP(ptr)) - DSIZE; size_t copy_size = old_size < size ? old_size : size; void *new_ptr = mm_malloc(size); if (new_ptr == NULL) return NULL; memcpy(new_ptr, ptr, copy_size); mm_free(ptr); return new_ptr; }
예외 처리
- 인자로 전달 받은
ptr이 NULL인 경우에는 할당만 수행한다. (mm_malloc함수 호출) - 인자로 전달 받은
size가 0인 경우에는 메모리 반환만 수행한다. (mm_free함수 호출)
새 블록에 할당
- 할당 : 인자로 전달 받은
size만큼 할당할 수 있는 블록을 찾아 할당한다. (mm_malloc함수 호출)
데이터 복사
ptr이 가리키고 있던 블록이 가지고 있는 payload 크기를 구하고,새로 할당할size보다 기존의 크기가 크다면 size로 크기를 조정한다.- 조정한
size만큼 새로 할당한 블록으로 데이터를 복사한다. (memcpy함수 호출)
기존 블록 반환
- 데이터 복사 후, 기존 블록의 메모리를 반환한다. (
mm_free함수 호출)
참고자료
[c언어] Malloc Lab :: 동적 할당기 구현하기 (Implicit List, Explicit List, Segregated List, Buddy System)
Sunny Day!