-
[정글 Week07_MallocLab] 구현 1: Implicit + First-fit + Eager카테고리 없음 2025. 4. 28. 14:27
- 가용리스트 조작 메크로
#define ALIGNMENT 8 // 리스트 정렬 기준 #define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7) // 주어진 size에 'ALIGNMENT - 1'만큼 더한 뒤, 하위 3비트를 0으로 마스킹 -> size보다 크고 가장 작은 ALINGMENT의 배수 반환 #define SIZE_T_SIZE (ALIGN(sizeof(size_t))) // 헤더/푸터에 size_t 값을 담기 위해 8 bytes(ALIGNMENT) 단위로 올림-정렬한 최소 블록 크기 #define WSIZE 4 // 워드 사이즈 (bytes) -> 헤더, 푸터 사이즈로 사용 #define DSIZE 8 // 더블워드 사이즈 (bytes) #define CHUNKSIZE (1<<12) // 힙 확장 단위 사이즈 4096 bytes(4KB) #define MAX(x, y) ((x) > (y) ? (x) : (y)) // x가 y보다 크면 x를, x가 y보다 작거나 같으면 y 반환 #define PACK(size, alloc) ((size) | (alloc)) // size와 alloc을 1개의 4bytes 값으로 합쳐서 저장 - 헤더에 저장되는 값 #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에 저장된 값을 읽고 비트마스킹 -> 블록 사이즈 확보 #define GET_ALLOC(p) (GET(p) & 0x1) // 주소 p의 1비트 자리값을 읽고 alloc 여부 확인 #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))) // 다음 bp 찾기: 현재 블록 헤더에서 현재 블록 사이즈 찾아내서 현재 bp에서 그만큼 뒤로 간 값 #define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) // 이전 bp 찾기: 이전 블록 푸터에서 이전 블록 전체 사이즈 알아내고 현재 bp에서 그만큼 앞으로 간 값
💡 바이트 계산은 char* 로, 1 워드(4 바이트) 읽기/쓰기는 unsigned int* 로 캐스팅해 주는 것이 관용적인 방법이다.
이렇게 하면 바이트 포인터로는 메모리 내애서 정확히 어디로 이동할지, 워드 포인터로는 4바이트 단위로 어떻게 읽고 쓸지를 분리해서 다룰 수 있어서 경계 태그 할당기에서 필요한 비트 조작, 메모리 정렬 등의 규칙을 모두 만족할 수 있다.
또한, unsigned int는 비트 시프트나 OR 연산이 정의된 동작이기 때문에, signed int에서 발생할 수 있는 부호 비트 처리나 오버플로우 걱정 없이 비트마스크를 다룰 수 있다.
따라서, char*로 정확한 바이트 오프셋을 구하고, 그 위치를 unsigned int*로 캐스팅해서 읽고 쓰는 방식이 권장된다.- mm_init
/* * malloc 패키지 초기화 + 초기 힙 생성 */ int mm_init(void) { if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1) return -1; // mem_sbrk를 호출해 메모리 시스템에서 4워드를 가져와 힙(brk)을 그만큼 확장하고, 확장 전 포인터를 heap_listp에 저장 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); // 힙을 CHUNKSIZE bytes/4 bytes (-> 워드 단위 환산)만큼 확장하고 힙에 4KB의 초기 가용 블록 추가 if (extend_heap(CHUNKSIZE/WSIZE) == NULL) return -1; return 0; }다음은 위 코드에서 heap_listp += (2*WSIZE); 까지 실행시켜 16bytes로 padding, prologue header, prologue footer, epilogue header를 만든 결과이다.
4B 4B 4B 4B ┌──────────┬───────────────┬───────────────┬─────────────────┐ │ padding │ prologue hdr │ prologue ftr │ epilogue hdr │ │ 0 / 0 │ 8 / 1 │ 8 / 1 │ 0 / 1 │ └──────────┴───────────────┴───────────────┴─────────────────┘ ↑ ↑ heap_listp brk그 다음 if (extend_heap(CHUNKSIZE/WSIZE) == NULL) return -1; 를 실행시켜 heap을 4KB만큼 확장해준다.
free 블록 배치에 대한 상세한 설명은 아래 extend_heap에서 계속된다.
4B 4B 4B 4B 4088B 4B 4B ┌──────────┬──────────┬──────────┬──────────┬─────────┬──────────┬──────────┐ │ padding │ prologue │ prologue │ free | free | free | epilogue │ │ │ hdr │ ftr │ hdr | payload | ftr | hdr │ │ 0 / 0 │ 8 / 1 │ 8 / 1 │ 4096 / 0 | | 4096 / 0 | 0 / 1 │ └──────────┴──────────┴──────────┴──────────┴─────────┴──────────┴──────────┘ ↑ ↑ ↑ heap_listp bp brk (구 brk)- extend_heap
기존의 brk는 16bytes 지점이었다. 그런데 mem_sbrk(size)는 이전 brk에서 요청받은 size만큼 brk를 높인 후 이전 brk를 반환한다. bp는 mem_sbrk(size) 결과를 할당받았기 때문에 이전 brk인 16bytes 지점이고, 새로운 brk는 기존 16bytes에 입력받은 4096bytes가 더해진 4112bytes 지점이 된다.
그리고 bp - 4(bytes) 지점에 free 블록의 header 포인터를 설정하고 (size 4096, alloc 0)을 저장하고, bp - size - 8(bytes) 지점에 free 블록의 footer 포인터를 설정하고 역시 (size 4096, alloc 0)를 저장한다. bp부터 footer 전까지는 자동으로 free payload의 자리가 되며, 그 크기는 4088(4096-(4 * 2)) bytes이다. 또, bp의 다음 블록에 새로운 epilogue header를 생성해준다.
마지막으로 bp의 인접 free 블록과 합치고 합쳐진 블록의 payload 포인터를 반환한다. mm 프로그램 최초 실행시에는 coalesce case 1에 해당돼서 연결 작업 없이 바로 동일한 bp가 반환된다.
/* * 새로운 가용 블록으로 힙 확장하기 */ static void *extend_heap(size_t words) { char *bp; size_t size; size = words * WSIZE; if ((long)(bp = mem_sbrk(size)) == -1) return NULL; // size만큼 brk를 올려주고, 올리기 전의 brk(== 새 블록의 시작)을 bp에 저장 PUT(HDRP(bp), PACK(size, 0)); // bp - 4 위치에 header PUT(FTRP(bp), PACK(size, 0)); // bp + size - 8 위치에 footer PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // free 블록 뒤에 새로운 epilogue header 생성 return coalesce(bp); // 인접 free 블록과 합치고 합쳐진 블록의 payload 포인터를 리턴 }- coalesce
coalesce는 '경계 태그' 연결을 통해서 상수시간에 인접 가용 블록들과 연결시킨다.
case 1. 인접 블록이 모두 할당된 경우
바로 bp를 반환한다.
case 2. 이전 블록은 할당, 다음 블록은 미할당된 경우
다음 블록의 헤더에서 다음 블록의 사이즈를 알아내 현재 블록 사이즈에 더해준다. 그 후 현재 블록 헤더에 (갱신된 사이즈, 미할당), 다음 블록 풋터에 동일하게 (갱신된 사이즈, 미할당)을 저장한다. 주의할 점은 FTRP(bp) 메크로가 이미 합쳐진 블록의 끝을 계산해줬기 때문에 FTRP(NEXT_BLKP(bp))이 아니라 FTRP(bp)에 (size, 0)값을 써줘야한다. 마지막으로 변경된 bp를 반환한다.
case 3. 이전 블록은 미할당, 다음 블록은 할당된 경우
이전 블록의 헤더에서 이전 블록의 사이즈를 알아낸 후 현재 블록 사이즈에 더해준다. 그 후 이전 블록 헤더에 (갱신된 사이즈, 미할당), 이전 블록 풋터에 동일하게 (갱신된 사이즈, 미할당)을 저장한다. 그리고 bp를 이전 블록의 bp로 변경한다! 마지막으로 변경된 bp를 반환한다.
case 4. 인접 블록이 모두 미할당된 경우
이전 블록의 헤더에서 이전 블록의 사이즈를 알아내고, 다음 블록의 헤더에서 다음 블록의 사이즈를 알아내서 두 값을 현재 블록 사이즈에 더해준다. 그 후 이전 블록 헤더에 (갱신된 사이즈, 미할당), 다음 블록 풋터에 동일하게 (갱신된 사이즈, 미할당)을 저장한다. 그리고 bp를 이전 블록의 bp로 변경한다. 마지막으로 변경된 bp를 반환한다.
/* * 경계 태그 연결을 사용해서 상수 시간에 인접 가용 블록들과 통합 */ 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) { return bp; } // case 2: 이전 블록은 이미 할당, 다음 블록은 미할당된 경우 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: 이전 블록은 미할당, 다음 블록은 이미 할당된 경우 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: 이전 블록, 다음 블록 모두 할당된 경우 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; }- mm_malloc
1. 먼저, 오버헤드와 정렬 기준(8bytes)를 고려해서 블록 사이즈를 재조정한다.
1) 요청 사이즈가 8bytes보다 작다면 오버헤드를 고려해서 할당 사이즈를 16bytes로 맞춰준다.
오버헤드는 헤더(4bytes)와 풋터(4bytes)를 포함하고, 요청 사이즈는 1bytes 이상일테니 가장 가까운 8의 배수인 16bytes를 할당해주는 것이다.
2) 요청 사이즈가 8bytes보다 크다면 ALIGN 메크로를 이용해서 현재 사이즈에 8bytes를 더한 값 보다 큰 조건을 만족하는 가장 작은 8의 배수를 할당 사이즈로 맞춰준다.
2. 다음으로 재조정한 사이즈 이상의 가용 블록을 찾고, 메모리를 할당해준다.
1) 적당한 가용 블록을 찾으면 bp에 asize만큼의 블록을 할당해주고 bp를 반환한다.
2) 적당한 가용 블록을 못 찾았으면 힙을 확장해주고, bp에 asize만큼의 블록을 할당해준 후 bp를 반환한다. 힙을 확장할 때는 위에서 재조정한 블록 사이즈와 CUNCKSIZE(4096 bytes) 중 더 큰 값을 기준으로 확장시킨다.
/* * brk 포인터를 증가시키면서 블록 할당 * 항상 ALIGNMENT의 배수만큼의 크기를 가지는 블록을 할당한다. */ void *mm_malloc(size_t size) { size_t asize; // 할당 사이즈 size_t extendsize; // 확장 사이즈 char *bp; if (size == 0) return NULL; // 오버헤드와 정렬 기준(8bytes)를 고려해서 블록 사이즈 재조정 if (size <= DSIZE) { // 요청 사이즈가 8bytes보다 작으면 헤더와 푸터로 인한 오버헤드를 고려해서 할당 사이즈를 16bytes로 asize = 2 * DSIZE; } else { // 요청 사이즈가 DSIZE보다 크면 asize = ALIGN(size + DSIZE); // + DSIZE는 헤더와 푸터로 인한 오버헤드 } // 적당한 free list를 찾으면 bp에 asize 만큼의 블록 만들어주고 bp 반환 if ((bp = find_fit(asize)) != NULL) { place(bp, asize); return bp; } // 적당한 free list를 못 찾으면 힙 확장 후 bp에 asize 만큼의 블록 만들어주고 bp 반환 extendsize = MAX(asize, CHUNKSIZE); if ((bp = extend_heap(extendsize/WSIZE)) == NULL) { return NULL; } place(bp, asize); return bp; }- find_fit
find_fit은 first-fit 배치 전략으로 구현했다. fitst-fit은 가장 먼저 만나게 되는 가용 블록을 할당한다.
heap_listp부터 size가 0보다 큰 블록들을 모두 조사하는데, '할당되어있지 않고 요청 사이즈가 블록 사이즈보다 작거나 같으면' 해당 블록을 바로 반환하게 된다.
만약 bp를 다음 블록으로 옮기면서 끝까지 찾아봤는데도 할당 가능한 가용 블록을 못 찾았다면 NULL을 반환한다.
/* * first fit으로 가용블록 탐색 후 찾은 가용블록의 bp 반환 */ static void *find_fit(size_t asize) { void *bp; for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) { // heap_listp부터 순차적으로 블록을 훑으면서 if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) { // 할당되지 않은 블록 중 요청 크기보다 크거나 같은 블록을 찾으면 return bp; // 해당 블록 바로 반환 } } return NULL; // 못 찾으면 NULL }- place
place는 bp로 찾은 가용 블록 중 asize만큼 할당하고 경우에 따라 split까지 수행한다.
먼저, bp가 가리키는 가용 블록의 현재 크기를 알아낸 후
1) 만약 '가용 블록의 사이즈 - 요청 사이즈' 값이 16 bytes보다 크거나 같다면 asize만큼만 할당하고 나머지는 미할당으로 만들어준다.
2) 만약 '가용 블록의 사이즈 - 요청 사이즈' 값이 16 bytes보다 작다면 현재 가용 블록 전체를 할당한다. 이때는 남는 공간만큼 내부단편화가 생긴다.
/* * free 블록에 asiz만큼 할당 표시. 필요시 split까지 수행 */ static void place(void *bp, size_t asize) { size_t csize = GET_SIZE(HDRP(bp)); // bp가 가리키는 'free 블록'의 현재크기를 읽는다. if ((csize - asize >= (2*DSIZE))) { // 현재 블록 크기 - 요청 크기가 16 바이트보다 크거나 같다면 free가 충분히 크므로 free를 두개로 나눈다. PUT(HDRP(bp), PACK(asize, 1)); // 현재 블록의 헤더에 요청 크기만큼 할당되었음을 설정 PUT(FTRP(bp), PACK(asize, 1)); // 현재 블록의 풋터에 요청 크기만큼 할당되었음을 설정 bp = NEXT_BLKP(bp); // bp를 다음 블록의 bp로 이동 PUT(HDRP(bp), PACK(csize-asize, 0)); // 다음 블록의 헤더에 '현재 가용 크기 - 요청 크기'만큼 미할당되었음을 설정 PUT(FTRP(bp), PACK(csize-asize, 0)); // 다음 블록의 풋터에 '현재 가용 크기 - 요청 크기'만큼 미할당되었음을 설정 } else { // 현재 블록 크기 - 요청 크기가 16 바이트보다 작다면 free 전체를 쓴다. PUT(HDRP(bp), PACK(csize, 1)); // 현재 블록의 헤더에 전체 할당되었음을 설정 PUT(FTRP(bp), PACK(csize, 1)); // 현재 블록의 풋터에 전체 할당되었음을 설정 } }- mm_free
현재 블록의 크기만큼 할당된 메모리를 해제한다. 현재 블록의 헤더와 풋터에 현재 블록의 크기만큼 미할당되었음을 설정해주고 가용블록이 앞, 뒤에 있다면 연결해준다.
/* * 아무것도 하지 않는 블록을 메모리에서 해제 */ void mm_free(void *ptr) { size_t size = GET_SIZE(HDRP(ptr)); // 현재 블록의 크기 PUT(HDRP(ptr), PACK(size, 0)); // 현재 블록의 헤더에 현재 블록의 크기만큼 미할당되었음을 설정 PUT(FTRP(ptr), PACK(size, 0)); // 현재 블록의 푸터에 현재 블록의 크기만큼 미할당되었음을 설정 coalesce(ptr); // ptr 앞/뒤 확인해서 가용 블록 연결 }- realloc
realloc은 할당받은 메모리의 사이즈를 변경해준다. 현재 블록에서 확장/축소 시도해보고 안 되면 새로운 블록을 할당하고 데이터 복사 후 이전 블록을 해제한다.
0. 먼저, 포인터가 NULL이거나 size가 0인 경우를 C 표준 realloc 정의에 따라 처리해준다.
- 포인터가 NULL이라면 realloc(NULL, size)는 malloc(size)와 동일한 동작을 수행한다.
- size가 0이라면 realloc(ptr, 0)은 free(ptr)과 동일한 동작을 수행한다.
1. 요청받은 크기를 정렬 기준에 따라 재조정해준다.
1) 요청 사이즈가 8bytes보다 작다면 오버헤드를 고려해서 할당 사이즈를 16bytes로 맞춰준다.
2) 요청 사이즈가 8bytes보다 크다면 현재 사이즈에 8bytes를 더한 값 보다 큰 조건을 만족하는 가장 작은 8의 배수를 할당 사이즈로 맞춰준다.
2. 재조정된 요청사이즈와 가용 사이즈를 비교해서 아래 선택지 중 하나를 수행한다.
1) 현재 블록 재사용
현재 블록 크기 ≥ 요청 크기 → 바로 그 블록 할당하고 포인터를 반환한다.
2) 인접 블록 합치기
다음 블록이 free이고, (현재 블록 + 다음 블록) 크기 ≥ 요청 크기 → 두 블록을 합쳐서 제자리 할당 후 포인터를 반환한다.
3) 새 블록으로 이동
위 두 경우에 모두 해당하지 않으면 새 블록 할당(mm_malloc) 후 기존 데이터만큼 복사(memcpy)한 다음, 옛 블록 해제(mm_free)하고 새 포인터를 반환한다.
/* * 현재 블록에서 요청받은 만큼 확장/축소 시도 후 안 되면 새로운 블록 할당->데이터 복사->예전 블록 free * 0. C 표준 realloc 정의에 따른 특수상황 처리* * 1) ptr이 NULL 이면 realloc(NULL, size)은 malloc(size)과 동일 * 2) size가 0이면 free(ptr)와 동일 * 1. 요청 사이즈를 정렬 기준에 맞춰 재정렬 * 2. 요청 사이즈와 현재 가용 사이즈에 따라 아래 셋 중 하나 수행 * 1) 현재 블록 사용 * 2) 인접 블록 합치기 * 3) 새 블록으로 이동하기 */ void *mm_realloc(void *ptr, size_t size) { // 0. C 표준 realloc 정의에 따른 특수상황 처리 // 1) ptr이 NULL 이면 realloc(NULL, size)은 malloc(size)과 동일 if (ptr == NULL) { return mm_malloc(size); } // 2) size가 0 이면 realloc(ptr, 0)은 free(ptr)와 동일 if (size == 0) { mm_free(ptr); return NULL; } // 1. 요청받은 크기를 정렬 기준에 따라 재조정 size_t asize; if (size <= DSIZE) // 최소 16B asize = 2 * DSIZE; else // 8B 정렬 + header/footer asize = ALIGN(size + (DSIZE)); // 🧚🏻 현재 블록의 크기와 다음 블록의 포인터 저장 size_t csize = GET_SIZE(HDRP(ptr)); // 지금 블록의 전체 크기 void *next_bp = NEXT_BLKP(ptr); // 바로 다음 블록 // 2. 현재 블록이 요청 사이즈보다 크면 그대로 반환 if (asize <= csize) { return ptr; } // 3. 현재 블록이 충분히 크지 않다면 if (!GET_ALLOC(HDRP(next_bp))) { // 뒤 블록이 free 이고, 합치면 충분히 큰지 체크 size_t next_size = GET_SIZE(HDRP(next_bp)); if (csize + next_size >= asize) { // 3-1) 연결했을 때 충분히 크다면 size_t newsize = csize + next_size; PUT(HDRP(ptr), PACK(newsize, 1)); PUT(FTRP(ptr), PACK(newsize, 1)); return ptr; // 복사없이 제자리 확장 완료 } } // 3-2) 연결했을 때도 충분치 않다면 새로 할당 후 기존 블록 사이즈 복사 void *newptr = mm_malloc(size); if (newptr == NULL) return NULL; // payload 크기만 복사 (헤더/풋터 제외) size_t copySize = csize - DSIZE; // csize 에는 header+footer 8B 포함되어있으므로 제외 if (size < copySize) copySize = size; memcpy(newptr, ptr, copySize); // 새로운 포인터에 기존 포인터에 mm_free(ptr); // 기존 ptr은 메모리 할당 해제 return newptr; }