TIL Malloc Lab — realloc 최적화와 Implicit Free List 마무리

About this offer

오늘은 mm_realloc() 의 여러 확장 경로를 구현하고 Implicit Free List 방식의 메모리 할당기를 마무리했다. realloc 은 단순히 더 큰 블록을 새로 할당하는 함수가 아니다. 가능하다면 기존 블록 주변의 free block을 활용해 Heap 확장을 줄이고, 기존 데이터도 유지해야 한다. 최종적으로 다음 경우를 처리했다. bp == NULL 인 경우 size == 0 인 경우 기존 블록을 축소하는 경우 오른쪽 free block으로 확장하는 경우 Heap 끝에서 Epilogue를 이동하며 직접 확장하는 경우 왼쪽 free block으로 확장하는 경우 왼쪽과 오른쪽 free block을 모두 사용하는 경우 위 방법을 사용할 수 없어 새 블록을 할당하는 경우 block 경계가 사라질 때 Next Fit의 rover를 보정하는 경우 realloc의 특수한 입력 먼저 bp 가 NULL 이면 기존 블록이 없다는 뜻이므로 malloc(size) 와 같은 방식으로 처리한다. if (bp == NULL) return mm_malloc(size); 반대로 요청 크기가 0이면 기존 블록을 해제하고 `NULL`을 반환한다. > ```c if (size == 0) { mm_free(bp); return NULL; } 이 두 경우를 먼저 처리하면 이후부터는 정상적인 block 주소와 0보다 큰 요청 크기만 생각하면 된다. 기존 블록을 줄이는 경우 현재 블록이 새로 필요한 크기보다 크다면 주소를 옮길 필요가 없다. 다만 축소하고 남는 공간이 최소 block 크기인 16바이트 이상이라면 뒤쪽을 별도의 free block으로 분할한다. ┌───────────────────────────────┐ │ 기존 ALLOCATED 블록 │ └───────────────────────────────┘ ↓ 축소 ┌──────────────────┬────────────┐ │ ALLOCATED │ FREE │ │ asize │ temp_size │ └──────────────────┴────────────┘ 이 과정에서는 Header와 Footer를 기록하는 순서가 중요했다. 현재 Header에는 아직 축소 전 크기인 old_asize 가 들어 있다. 이 상태에서 FTRP(bp) 를 계산하면 기존 블록의 마지막 Footer를 가리킨다. 이 위치는 분할 후 새 free block의 Footer가 된다. 따라서 기존 Footer 위치에 남는 크기를 먼저 기록하고, 그다음 Header를 asize 로 변경해야 한다. 분할해서 만든 free block의 오른쪽에 또 다른 free block이 있을 수도 있으므로 마지막에는 coalesce() 를 호출했다. 오른쪽 free block을 이용한 제자리 확장 기존 블록보다 큰 공간이 필요하더라도 바로 새 블록을 할당할 필요는 없다. 오른쪽 block이 free이고 현재 block과 합친 크기가 asize 이상이라면 기존 bp 를 유지한 채 확장할 수 있다. bp bp ↓ ↓ ┌──────────────┬────────────┐ ┌──────────────────┬──────────┐ │ ALLOCATED │ FREE │ → │ ALLOCATED │ FREE │ │ old_asize │ │ │ asize │ remainder│ └──────────────┴────────────┘ └──────────────────┴──────────┘ 이 방식은 bp 가 바뀌지 않는다. 기존 payload도 같은 주소에 있으므로 데이터를 복사할 필요가 없다. 오른쪽 block을 합친 뒤 16바이트 이상 남으면 다시 free block으로 분할한다. 남는 공간이 16바이트보다 작다면 독립적인 block으로 사용할 수 없으므로 오른쪽 block 전체를 흡수한다. 처음에는 다음 변수들의 의미가 섞여서 많이 헷갈렸다. asize old_asize next_old_asize adjust_next_old_asize 각 변수의 의미는 다음과 같다. asize : 새로 필요한 전체 block 크기 old_asize : 현재 block의 전체 크기 next_old_asize : 현재 block과 오른쪽 block을 합친 크기 adjust_next_old_asize : 두 block을 합친 뒤 남는 크기 변수 이름만 보는 것보다 실제 block 그림과 함께 보는 편이 훨씬 이해하기 쉬웠다. Heap 끝에서 Epilogue 직접 확장 현재 block 바로 다음의 block size가 0이라면 다음 위치는 Epilogue다. 즉 현재 block이 Heap의 마지막 실제 block이라는 뜻이다. [현재 ALLOC][Epilogue] 이때 새 블록을 따로 할당하면 기존 데이터를 복사하고 기존 block을 해제해야 한다. 대신 부족한 크기만큼 Heap을 직접 늘리면 기존 주소를 유지할 수 있다. 확장 전: [현재 ALLOC][Epilogue] 확장 후: [더 커진 현재 ALLOC][새 Epilogue] 이미 old_asize 만큼의 공간은 있으므로 추가로 필요한 크기는 다음과 같다. asize - old_asize 이 크기만큼 mem_sbrk() 를 호출했다. void *extend_result = mem_sbrk(asize - old_asize); 여기서 extend_heap() 을 사용하지 않은 이유도 알게 됐다. extend_heap() 은 새로운 free block을 만들고 coalesce() 까지 수행하는 함수다. 이번 경우에는 별도의 free block이 필요한 것이 아니라 기존 allocated block 자체를 늘려야 한다. 확장에 성공하면 현재 block의 Header와 Footer를 새 크기로 변경하고, 확장된 Heap 끝에 새로운 Epilogue Header를 기록했다. PUT(HDRP(bp), PACK(asize, 1)); PUT(FTRP(bp), PACK(asize, 1)); PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); mem_sbrk() 가 실패할 수도 있으므로 metadata는 반드시 확장 성공 이후에 변경해야 한다. 왼쪽 free block을 이용한 확장 오른쪽에서 공간을 확보할 수 없더라도 왼쪽 block이 free라면 확장에 사용할 수 있다. 확장 전: [왼쪽 FREE][현재 ALLOC][오른쪽 ALLOC] 확장 후: [새 ALLOC][남은 FREE][오른쪽 ALLOC] 다음 조건을 만족하면 왼쪽 block과 현재 block을 합친다. 왼쪽 block이 free 오른쪽 block은 allocated 왼쪽 크기 + 현재 크기 >= asize 오른쪽 확장과 가장 큰 차이는 block의 시작 주소가 왼쪽으로 이동한다는 점이다. 기존 payload도 bp 에서 prev_bp 로 옮겨야 한다. 두 메모리 영역이 겹칠 수 있으므로 memcpy() 가 아니라 memmove() 를 사용했다. memmove(prev_bp, bp, old_asize - DSIZE); old_asize 에는 Header와 Footer도 포함되므로 실제 payload 최대 크기는 old_asize - DSIZE 다. 데이터를 옮기기 전에 metadata를 먼저 기록하면 기존 payload 일부를 덮어쓸 수 있다. 따라서 순서는 다음과 같아야 한다. 기존 payload 이동 → 새 Header/Footer 기록 → 남는 공간이 있으면 free block 생성 → 새 시작 주소인 prev_bp 반환 양쪽 free block을 모두 이용한 확장 이전 block과 다음 block이 모두 free이고 한쪽만으로는 공간이 부족하다면 세 block을 모두 합칠 수 있다. 확장 전: [왼쪽 FREE][현재 ALLOC][오른쪽 FREE] 확장 후: [새 ALLOC][남은 FREE] 전체 크기는 다음과 같이 계산했다. combined_size = GET_SIZE(HDRP(prev_bp)) + old_asize + GET_SIZE(HDRP(next_bp)); 요청 크기만큼 사용하고 남는 크기는 다음과 같다. remainder = combined_size - asize; 왼쪽 확장과 마찬가지로 block 시작 주소가 prev_bp 로 바뀌므로 payload부터 memmove() 로 옮겼다. 남는 공간이 16바이트 이상이면 하나의 free block으로 분할했다. 그보다 작으면 내부 단편화를 조금 허용하고 합친 전체 공간을 allocated block으로 사용했다. 이 과정에서 Footer 위치를 계산하는 것이 특히 헷갈렸다. 양쪽 block을 모두 흡수하므로 최종 영역의 Footer는 기존 현재 block의 Footer가 아니라 기존 오른쪽 free block의 끝에 있어야 한다. 이를 prev_bp 와 combined_size 를 이용해 계산했다. HDRP(prev_bp) + combined_size - WSIZE rover가 잘못된 block 경계를 가리킨 문제 Next Fit을 시험하던 중 place() 에서 Segmentation Fault가 발생했다. GDB로 확인한 Header 값은 다음과 같았다. 0x5e5e5e5e 이 값은 정상적인 block size가 아니라 mdriver가 payload에 채운 테스트 패턴이었다. 즉 rover가 정상적인 block 시작 주소가 아니라 block 내부를 가리키고 있었다. 원인은 find_fit_next() 자체보다 이전의 coalesce() 와 realloc() 에 있었다. 두 block을 합치면 기존 Header 중 일부가 사라진다. rover가 그 경계를 기억하고 있었다면 합친 뒤에는 payload 내부를 가리키게 된다. 병합 전: [현재 block][오른쪽 FREE] ↑ rover 병합 후: [하나의 더 큰 block] ↑ 기존 rover는 내부 주소 따라서 coalesce 또는 realloc으로 block 경계가 사라질 때 rover가 병합 범위 안에 있는지 검사했다. 내부를 가리키고 있다면 새로 만들어진 유효한 block 경계로 이동시켰다. 오른쪽 block을 흡수하는 두 경우에도 각각 rover 보정이 필요했다. 분할한 경우: 새로 만들어진 free block으로 이동 분할하지 않은 경우: 합쳐진 allocated block의 다음 block으로 이동 두 경우 모두 다음 코드를 사용하지만 현재 Header에 기록된 크기가 다르기 때문에 NEXT_BLKP(bp) 가 가리키는 위치도 달라진다. rover = NEXT_BLKP(bp); 이번 디버깅을 통해 rover는 단순히 “다음 free block”을 저장하는 포인터가 아니라, Next Fit이 다음 탐색을 시작할 수 있는 유효한 block 경계를 저장하는 포인터라는 점을 이해했다. 인접 block으로 확장할 수 없는 경우 오른쪽, 왼쪽, 양쪽 block을 이용할 수 없고 Epilogue 직접 확장도 실패했다면 새 block을 할당해야 한다. 처리 순서는 다음과 같다. mm_malloc(size) 로 새 block을 할당한다. 기존 payload를 새 block에 복사한다. 기존 block을 해제한다. 새 block 주소를 반환한다. void *new_bp = mm_malloc(size); if (new_bp == NULL) return NULL; memcpy(new_bp, bp, old_asize - DSIZE); mm_free(bp); return new_bp; 기존 block을 먼저 해제하면 그 공간의 데이터가 유지된다고 보장할 수 없다. 반드시 복사를 먼저 끝낸 다음 mm_free(bp) 를 호출해야 한다. 배치 정책과 CHUNKSIZE 비교 First Fit, Next Fit, Best Fit도 각각 구현해 같은 조건에서 비교했다. 비교 결과 현재 trace에서는 First Fit의 전체 점수가 가장 높았다. First Fit: 93/100 Best Fit : 91/100 Next Fit : 88/100 Next Fit은 탐색 속도가 빨랐지만 utilization이 낮았고, Best Fit도 항상 더 좋은 공간 활용률을 보장하지는 않았다. 최종 구현에서는 First Fit을 사용했다. 초기 Heap 확장 크기인 CHUNKSIZE 도 4096바이트부터 256바이트까지 바꿔가며 비교했다. 현재 구현과 trace에서는 256바이트일 때 utilization이 가장 높아 다음 값을 선택했다. #define CHUNKSIZE (1 << 8) 이 값이 모든 프로그램에서 항상 최적이라는 뜻은 아니다. 이번 Malloc Lab의 trace를 기준으로 선택한 결과다. 최종 테스트 결과 최종 코드로 mdriver -v 를 실행했다. Results for mm malloc: trace valid util ops secs Kops 0 yes 99% 5694 0.004844 1175 1 yes 100% 5848 0.004566 1281 2 yes 99% 6648 0.007432 894 3 yes 100% 5380 0.003945 1364 4 yes 97% 14400 0.000056258065 5 yes 92% 4800 0.003766 1275 6 yes 92% 4800 0.003834 1252 7 yes 55% 12000 0.025010 480 8 yes 51% 24000 0.105769 227 9 yes 99% 14401 0.000030483255 10 yes 87% 14401 0.000032450031 Total 88% 112372 0.159284 705 Perf index = 53 (util) + 40 (thru) = 93/100 최종 결과는 다음과 같다. 11개 기본 trace 모두 valid = yes 전체 utilization 88% utilization 점수 53점 throughput 점수 40점 최종 성능 점수 93/100 realloc-bal.rep utilization 99% realloc2-bal.rep utilization 87% 초기 결과는 utilization 77%, 총점 86점이었다. First Fit 선택, CHUNKSIZE 조정, realloc 제자리 확장 최적화를 적용한 뒤 utilization은 88%, 총점은 93점으로 올라갔다. 모든 trace가 통과했다는 것은 제공된 테스트 흐름에서 allocator의 정합성이 유지됐다는 뜻이다. 다만 기본 trace가 realloc의 모든 세부 분기를 각각 실행했다는 뜻은 아니므로, 특정 분기를 완전히 검증하려면 별도의 작은 trace나 Heap Checker가 필요하다. find_fit_next() 와 find_fit_best() 는 정책 비교를 위해 구현을 남겨뒀지만 최종 find_fit() 에서는 First Fit만 사용한다. 이 때문에 두 함수의 미사용 경고가 나오지만 allocator의 동작 오류는 아니다. malloc lab 회고 처음에는 malloc 이 Heap에서 빈 공간 하나를 찾아 반환하는 함수 정도라고 생각했다. 직접 구현해 보니 정렬, Header와 Footer, 최소 block 크기, 분할, 병합, 탐색 정책을 함께 고려해야 했다. 가장 어려웠던 부분은 포인터 연산과 metadata를 기록하는 순서였다. Header의 크기를 변경하는 순간 FTRP(bp) 와 NEXT_BLKP(bp) 가 계산하는 주소도 달라졌다. 같은 값을 기록하더라도 어느 metadata를 먼저 바꾸느냐에 따라 전혀 다른 위치를 덮을 수 있었다. realloc 에서는 여기에 데이터 이동까지 추가됐다. 오른쪽 확장은 기존 주소를 유지하지만 왼쪽이나 양쪽 확장은 block 시작점이 바뀐다. 이때는 payload를 먼저 memmove() 로 옮긴 뒤 Header와 Footer를 기록해야 했다. Next Fit의 rover 문제도 기억에 남는다. 크래시는 place() 에서 발생했지만 실제 원인은 그보다 앞서 block 경계를 변경한 coalesce() 와 realloc() 에 있었다. 오류가 나타난 위치와 원인을 만든 위치가 다를 수 있다는 것을 GDB로 직접 확인했다. 이번 주차 동안 다음 내용을 배웠다. Heap에서 물리적인 block 경계를 계산하는 방법 Header/Footer에 크기와 할당 상태를 함께 저장하는 방법 split과 coalescing이 필요한 이유 First Fit, Next Fit, Best Fit의 차이 내부 단편화와 외부 단편화가 발생하는 이유 memcpy() 와 memmove() 의 차이 Heap 끝에서 Epilogue를 이동시키는 방법 기존 payload를 보존하며 block 크기를 변경하는 방법 GDB로 잘못된 block 주소와 metadata를 추적하는 방법 아직 Explicit Free List와 Segregated Free List가 남아 있다. 두 방식 모두 지금 만든 Header/Footer와 물리적 block 이동 구조를 그대로 활용하지만, free block의 payload에 연결 정보를 저장해 탐색 범위를 줄인다는 차이가 있다. 이번 구현에서는 Implicit Free List 방식의 allocator를 직접 완성했고, 제공된 모든 기본 trace에서 valid = yes 를 확인했다. 최종 점수도 93점까지 올릴 수 있었다. Malloc Lab을 하면서 가장 크게 느낀 점은 코드 한 줄을 외우는 것보다 그 코드가 Heap의 어느 주소를 읽고, 어떤 block 경계를 바꾸는지 이해하는 것이 훨씬 중요하다는 것이었다.