원래는 회고록을 잘 쓰지 않는데, 이번 한 주의 회고록을 쓰는 이유는 따로 있다.
너무 팀 플레이를 적극적으로 다양하게 많은 얘기를 나눴기 때문에 팀원들과의 사고 과정 회로를 적지 않으면 너무 아쉬웠다.
이러한 사고의 과정을 기록해두고자 한다. (나중에 도움이 될 가능성이 크지 않을까?)
1일차 (2026-04-10 - 금)
malloc을 구현하기에 앞서 간단히 CSAPP 책 9.9장 동적메모리 할당을 읽고 팀 회의 시간을 가졌다.
첫날 시작 오후 10시 반
첫날 마무리 새벽 1시 반
회의 주제 : malloc 구현에 필요한 implicit free list, explicit free list, segregated free list 간단히 학습 후 공유
Knowledge Level : Low
First day knowledge before meeting : malloc을 구현하기에 어떤 알고리즘으로 구성되어 있는질 알지 못했음
Study Method : 9.9장을 그냥 한 번 다 속독으로 읽고 모르는 부분만 따로 정리 (책 중점 학습 진행)
Knowledge
- 명시적인 할당기와 묵시적인 할당기가 무엇인지 구분 가능
- 내부 단편화, 외부 단편화가 무엇인지 앎 (Fragment)
- 워드와 더블워드가 무엇을 의미하는지 앎 (4Byte, 8Byte)
- 하나의 힙 블럭 단위가 어떻게 구성되어 있는지 앎 (Header, Payload, Footer)
- Malloc 구현 알고리즘인 명시적 가용 리스트, 묵시적 가용 리스트, 분리 가용 리스트가 무엇인지 앎 (지식에 오류가 많은 상태로) - 따로 정리 예정
- 힙 생성시 초기화 하는 과정에 대해 앎 (Padding, Header, Prologue Header, Prologue Footer, epilogue Header)
Meeting Contents (역시 기록이 중요하다)
- memlib.c 메모리 시스템 모델 구현 과정을 보지 않고 first-fit, next-fit, best-fit에 대해 토의
- laze coalease, immediate coalease 에 대해 토의
깨달은 점
1. 회의시 화이트 보드를 적극적으로 활용하기 위해 최대한 정리를 하고자 노력하자! (서기 필수!)
2. 블럭에 있는 Header와 Footer는 동일한 정보를 저장한다.
3. Header와 Footer 끝에 있는 3bit가 왜 남을까?
4. 실제로 extend_heap()을 통해 힙 영역을 확장할 때, 왜 coalease를 통해 immediate free를 할까?
5. lazy coalease는 실제로 사용되는 전략이며, 다양한 경우 최적화를 위해 선택된다.
6. 왜 Prologue header, Prologue Footer, Epilogue Header가 존재할까?
1. 회의시 화이트 보드를 적극적으로 활용하기 위해 최대한 정리를 하고자 노력하자!
3시간 동안의 회의 내용을 블로그로 7일이 지난 시점에 다시 기억하고 생각 해내려 하니 너무 어렵다.
진짜 많은것을 했는데 화이트 보드를 예쁘게 작성하고, 회의 내용을 사진을 찍어두지도 않으니 기록 남기기가 너무 힘들다.
이제부턴 무조건 회의시에 AI로 자동 스크립트 저장과 서기 역할을 둘 다 해야겠다.
2. 블럭에 있는 Header와 Footer는 동일한 정보를 저장한다.
3. Header와 Footer 끝에 있는 3bit가 왜 남을까?
그림을 보면 힙 블록이 어떻게 구성되어 있는지 알 수 있다.
처음엔 Header안에 사이즈와 앞과 뒤가 alloc인지를 저장하는 0x00000018|0x1 = 0x00000019가 어떻게 저장되는건지 감이 전혀 안왔다. 지금은 확실하게 말할 수 있다.
Header와 Footer는 위 이미지 처럼 현재 블럭 사이즈의 정보와 현재 블럭이 할당블럭인지 가용블럭인지에 대한 정보를 담고 있다. (그림이 좀 잘못되었다. 마지막 1001이 아니라, 0001 0001 이다.)
무조건 최소 블럭 사이즈가 16Byte이상 이므로 마지막 3bit는 쓰지 않는 공간으로 남게 된다.
그렇기에 이 공간을 통해 현재 블럭이 할당인지 가용인지를 구별하고, 실제로 Footer를 제거할 때 두번째 bit에 이전 블럭이 가용인지 할당인지를 구별하게 하면 Footer 블럭도 제거할 수 있다고 한다.
4. 실제로 extend_heap()을 통해 힙 영역을 확장할 때, 왜 coalease를 통해 immediate free를 할까?
회의 도중 전혀 기억이 안났다....!!!!
하지만 지금은 말할 수 있다. 힙을 확장할 때 처음 생성할 때만 확장하는 게 아니라 지금 있는 힙 블럭들이 있는 공간의 사이즈 자체가 작으면 extend_heap()을 통해 확장을 해야하는데, 확장하기 전 Free 블럭 공간이 이미 존재하고 있을 수도 있기 때문이다.
위 그림을 설명하자면, 기존 128Byte의 공간이 있고 16byte free 공간이 2군데가 있다
하지만, 64byte 요청을 하게 되면, 공간이 없어 힙 영역을 확장해야 하고,
그렇게 128byte로 설정한 크기만큼 확장을 하고 앞이 free이기 때문에 합치는 작업이 필요하다.
5. lazy coalease는 실제로 사용되는 전략이며, 다양한 경우 최적화를 위해 선택된다.
- lazy coalease(지연 연결)은 free 전략을 채택할 때 말 그대로 합치는 작업을 나중에 한꺼번에 처리하겠다는 의미
기존 연결 방식 (Immediate Coalease)
1. 앞/뒤 블록 확인
2. free list에서 이웃 블록 제거 (Explicit Free List, Segregated Free List)
3. 합침(Implicit Free List) or 합쳐서 다시 free list에 삽입 (Explicit Free List, Segregated Free List)
이러한 방식을 나중에 정말 필요할 때, 한꺼번에 합치는 과정을 의미
이 기존 방식은 이 과정이 오버헤드가 될 수 있다. 하지만 lazy는 이 과정을 한꺼번에 처리하므로 오버헤드를 줄일 수 있다.
6. 왜 Prologue header, Prologue Footer, Epilogue Header가 존재할까?
간단하게 이해하면, 계산을 쉽게 하기 위해서이다. 블록을 할당하게 되면, 힙 블록 포맷에 따라 Header와 Footer가 생기는데, 그 Header위치를 같이 맞춰주고, 이곳이 할당된 블록이라는 것을 인지시켜줌으로써 잘못된 주소로 접근될 수 있는 오류를 방지하기 위한 초기화 작업이다.
Meeting Contents 생각나는 대로 상세히 정리
1. 점수가 좋은 implicit free list를 구현하기 위해선 어떤 전략을 채택해야 할까?
first fit에 lazy coalease를 도입하게 되면 어떨까? - 좋지 않을 것 같다?
next fit에 lazy coalease를 도입하게 되면 어떨까? - 좋나?
best fit에 lazy coalease를 도입하면 어떨까? - 좋을지도?
이런 다양한 사고가 계속 오갔던것으로 기억난다. 정확한 답은 안 나왔던 것 같다. 어떤 결과는 나왔는데, 나 스스로가 납득은 못한걸지도..
왜냐 이 당시엔 직접 코드로 구현한걸 보지도 못했고 어떻게 구현을 해야하는지 감도 안잡혔기 때문이다..
지금 내 생각은 작은 malloc과 free가 많이 반복되면 (짧은 생명주기) immediate coalease보다 괜찮을 것 같다는 생각이 든다.
Why? -> 짧은 생명주기가 반복되면 overhead가 크기 때문에 똑같은 크기의 블록이 free 되었다 alloc 되었다 free 되었다가 반복되면, 계속해서 coalease로 양쪽 상태를 확인할 필요가 없기 때문
더보기
그런데 여기서 내부 단편화 외부 단편화 얘기도 같이하면서 엄청 머리를 박았던 기억이 난다. (지금 생각해도 너무 힘들었다..)
[사실 아직도 머리속에 정리가 안되어 있는 상태라 결론이 제대로 났는지 모르겠다.]
2. extend heap에서 사이즈를 늘리는 게 있는데, 줄이는 것도 같이 있나?
extend_heap을 할 때, mem_sbrk(int incr) 라는 함수로 증가할 크기 값을 받는데,
현재 책에는 증가만 되고 감소는 안되게 되어있었다.
팀원 한분이 '-도 된다' 즉, 감소도 된다로 조사를 해왔고, 여기서 논의가 생겼다.
나는 감소도 된다는 쪽에 속했는데, 증가만 된다. 와 의견이 갈렸다.
논의를 하다가 AI로 예시가 있는지 찾아봤는데,
'실제 서비스를 하다 트래픽이 엄청나게 쏠려 한번에 기존 할당된 힙영역보다 많은 공간을 필요로 하게 되어 엄청나게 확장되었다고 가정하면, 감소도 할 수 있다.'로 생각이 들었는데, 만약 '힙이 계속 확장된 상태로 한 공간이 계속 그 영역을 지속적으로 소비하게 되어 힙을 줄일때 문제가 발생하게 되는 경우가 발생하면, 어떻게 되냐?' 라는 의견이 나왔다.
이거는 실제로 생각해보았을 때, 감소하면 실제 사용자에게 에러를 발생시키게 되는 꼴이 되므로 절대 있으면 안되는 일이었다. 이것에 대해서도 엄청난 토의를 했는데, 결국 결론이 나지 않았다.
다음날 팀원들이 찾아서 가상메모리에 주소를 어떻게 처리하는 방법이 있다고 했긴 했지만, 지금은 이정도로 알고 넘어가야 할 것 같다.
그리고 기본적으론 확장만 하지 축소는 절대로 권장하지 않는 방법이다. (문제가 발생할 수 있기 때문)
3. 힙 블록 포맷의 기본 단위는 16Byte가 기본이다. free할 때, Payload를 지우면 Payload가 0이 되므로 8Byte로 설정해도 되는거 아닌가? -> 메모리 공간을 더 확보하기 위해
이때 논의가 나왔는데, 왜 8Byte로 쓰지 않을까? 결론은 '될 것 같다'로 결론이 났었다.
하지만 지금 생각해보니 Free와 Alloc 공간의 크기를 같게 설정하는데, 매번 free 할때마다, header와 footer의 size를 바꿔줘야 하고, coalease overhead도 심각하게 발생하고, 최소 단위를 8Byte로 해서 생성시키면, 위 3번에서 3bit가 아닌 2bit가 남게 되므로 크게 문제는 없는데, 설계에서도 많은 변화가 발생할 것 같다는 생각이 들었다.
결론적으로 드는 생각은 구현도 힘들고, overhead도 심각하게 많이 발생하고, 굳이? 생성후에 다시 합치는 과정을 한 번 더 해야하는걸까? 라는 생각이 들긴 한다.
2일차 (2026-04-11 - 토)
malloc을 구현하기에 앞서 한 번 더 CSAPP 책 9.9장 동적메모리 할당을 읽고 팀 회의 시간을 가졌다.
둘째날 시작 오후 9시
둘째날 마무리 오후 11시
회의 주제 : explicit free list, segregated free list 장단점 조사
실제로는 malloc 구현에 필요한 implicit free list, explicit free list, segregated free list 자세히 학습 후 공유
Knowledge Level : Middle
Second day knowledge before meeting : malloc을 구현하기에 Explicit와 Segregated의 세부흐름을 모름
Study Method : 9.9장을 그냥 한 번 더 속독으로 읽고 장단점을 AI를 활용해서 조사하며 궁금한 점 정리
Knowledge
- 명시적인 할당기와 묵시적인 할당기가 무엇인지 구분 가능
- 내부 단편화, 외부 단편화가 무엇인지 앎 (Fragment)
- 워드와 더블워드가 무엇을 의미하는지 앎 (4Byte, 8Byte)
- 하나의 힙 블럭 단위가 어떻게 구성되어 있는지 앎 (Header, Payload, Footer)
- Malloc 구현 알고리즘인 명시적 가용 리스트, 묵시적 가용 리스트, 분리 가용 리스트가 무엇인지 앎 (지식에 오류가 있음) - 따로 정리 예정
- 힙 생성시 초기화 하는 과정에 대해 앎 (Padding, Header, Prologue Header, Prologue Footer, epilogue Header)
- Header와 Footer가 똑같은 정보가 들어가 있다는 사실을 알고 있음
- Implicit Free List에 대해서 알고 있음
Meeting Contents (역시 기록이 중요하다)
- memlib.c 메모리 시스템 모델 구현 과정을 보지 않고 메모리를 줄이는 방법에 대해 토의
- explicit free list (LIFO, 주소기반) 방식에 대해서 상세히 토의
깨달은 점
1. Explicit Free List의 LIFO 방식에 가용블록 생성과 할당의 흐름 자체가 LIFO 방식이다 [삽입 삭제 둘다 O(1)]
2. Explicit Free List에서 next fit은 어떤 형태로 구현이 될까?
3. PRED, SUCC가 실제로 어떻게 작동할까?
4. Segregate Free List의 가용블록 생성과 할당은 어떻게 동작할까?
1. Explicit Free List의 LIFO 방식에 가용블록 생성과 할당의 흐름 자체가 LIFO 방식이다
위 이미지가 흐름이다. 즉 FBL에 제일 처음에 넣고 제일 처음에서 빼서 할당한다. (Last In First Out) - Stack 방식
2. Explicit Free List에서 next fit은 어떤 형태로 구현이 될까?
next-fit의 개념은 이전 탐색했던 곳부터 시작해서 다시 찾는 방법이다.
실제로 그 말 그대로 Free할 때는 상관없고, 할당할 때만 이전 포인터를 찾아서 그 쪽부터 시작해 할당할 수 있는 블록을 찾는 과정이다. 이 방법을 사용하면, 앞쪽에 블록들이 쌓이는 외부 단편화의 문제를 해결할 수 있지만, 메모리 공간 지역성의 문제가 생길 수 있다. (퍼져서 분배하게 되어)
First Fit
[빈][빈][빈][빈][빈][빈]
↑ 계속 여기서만 탐색
Next Fit
[빈][빈][빈][빈][빈][빈]
↑ 계속 이동3. PRED, SUCC가 실제로 어떻게 작동할까?
predecessor (전임자) | successor (후임자)
Free 블록의 포인터로 2개가 생긴다는 것을 알고 있다.
그렇다면, 할당되고 Free 했을 경우 포인터 2개가 생겨 Free 블록의 크기가 커지는건가?
아니다. 기존 alloc과 free 블록의 크기는 같고 Header와 Free 블록의 크기가 각각 4Byte라면, 8Byte의 포인터가 2개가 생기는 것이므로, 전체 24Byte의 크기가 최소 블록의 크기가 되는 것이다.
4. Segregate Free List의 가용블록 생성과 할당은 어떻게 동작할까?
명시적 가용 리스트 구현 방법에서 가용 블럭 리스트 (위에서 말한 FBL)을 어떻게 나눌 것인가?가 추가되는 것이다.
즉, FBL을 크기에 맞춰 나눠서 각자의 FBL안에서는 명시적 가용 리스트의 구현 방법 2가지에 따라 방법이 나뉘는 것 뿐이다.
여기서 추가로 Buddy 시스템 방법이 있는데, 이 크기 설정하는 방법이 2^n에 따라 나뉘는 것 뿐이다.
Meeting Contents 생각나는 대로 상세히 정리
사실 2일차에서 많은 회색지대가 걷혀지고 구현 전 단계에서 정리할 수 있는건 다 정리한 것 같다. (1일차에 알게 된 점이라고 적은 것들도 2일차에서 많이 정확해진 개념들이다.)
1. allocaed 블록에 Footer를 없앨 수 있다!
팀 동료가 찾았다. allocated 블록에 Footer를 제거해서 메모리 효율을 높일 수 있다고 (4byte)나 줄여진다.
하지만, 사이즈가 8Byte 기준이기 때문에 결국엔 최소 블록 크기는 24Byte가 된다.
- 방법
남는 3bit의 2번째 공간에 prev alloc을 줘서 앞에 있는 블록이 free 블록인지 alloc 블록인지를 판단하는 방법이다.
( 000 -> 010 )
2. explicit free list에서 next fit을 적용하면 어떻게 작동할까? (더 좋지 않을까?)
'더 좋지 않을까?' 라는 생각에서 비롯되기 보다 일단 '어떻게 작동할까?' 에서 비롯된 것 같긴 하다.
정리하자면, next fit을 하게 되면, split된 블록은 그 자리에 있고, 그 쪽부터 다시 탐색
만약 split이 안되고 딱 맞으면 그 위치가 다른 블록으로 대체 되므로, 첫 시작은 LIFO를 깨지 않음
그리고 이것 말고도 전체를 다 탐색했는데 없으면? heap을 확장하는 것과 처음으로 어떻게 다시 돌아가는지에 대한 판단은 실제로 다음으로 미뤄서 생각해봐야 할 것 같다. (결론이 나지 않았던 것 같다.)
더보기
의미있게 논의 했던 내용들을 가볍게 정리하는 게 너무 힘들긴 하다. 다시 한번 그때 그때 정리하는 습관이 중요하다는 생각이 든다.
3일차 (2026-04-13 - 월)
implicit free list를 적용한 malloc을 구현하고 그 구현에 대해 공유
셋째날 시작 오후 10시
셋째날 마무리 오후 11시 40분
회의 주제 : 실제 implicit을 구현한 내용에 대해 토의
Knowledge Level : High
Second day knowledge before meeting : malloc을 구현하면서 실제로 데이터가 어떻게 흘러가는지 이해함
Study Method : implicit을 구현해보면서 궁금한 내용들을 정리
Knowledge
- 명시적인 할당기와 묵시적인 할당기가 무엇인지 구분 가능
- 내부 단편화, 외부 단편화가 무엇인지 앎 (Fragment)
- 워드와 더블워드가 무엇을 의미하는지 앎 (4Byte, 8Byte)
- 하나의 힙 블럭 단위가 어떻게 구성되어 있는지 앎 (Header, Payload, Footer)
- Malloc 구현 알고리즘인 명시적 가용 리스트, 묵시적 가용 리스트, 분리 가용 리스트가 무엇인지 앎 (지식에 오류가 있음) - 따로 정리 예정
- 힙 생성시 초기화 하는 과정에 대해 앎 (Padding, Header, Prologue Header, Prologue Footer, epilogue Header)
- Header와 Footer가 똑같은 정보가 들어가 있다는 사실을 알고 있음
- Implicit Free List에 대해서 알고 있음
- 실제 구현을 할 수 있음
Meeting Contents (역시 기록이 중요하다)
- 각자 구현하면서 다를 만한 내용을 소개
- implicit 구현 중 점수를 올리기 위해 realloc을 직접 구현한 내용을 공유
깨달은 점
1. find_fit, place를 따로 두는 이유
2. size_t 를 자료형으로 따로 사용하는 이유
3. realloc에 대해서
1. find_fit, place를 따로 두는 이유
find_fit(size_t size)
말 그대로 find_fit으로 free 리스트 영역에서 직관적으로 딱 맞는 크기의 할당 가능한 영역을 찾기 위한 함수
place(char *p, size_t asize)
그 공간에 값을 할당하기 위한 함수
2. size_t를 자료형으로 따로 사용하는 이유
size_t 자료형은 컴퓨터의 운영체제에 따라 지원하는 바이트 단위가 바뀐다.
32bit 컴퓨터 -> 4Byte
64bit 컴퓨터 -> 8Byte
이것 말고 중요한 건, 확장할 수 있는 공간이 4Byte (4GB) 크기를 넘는 공간이 한꺼번에 요청될리는 없겠지만, 그런 예외상황을 방지하기 위해 사용한다. 그렇지 않다면, unsigned int(4Byte)를 써서 사용해도 문제가 없다.
3. realloc에 대해서
1. 확장가능
- alloc free (alloc + free 공간이 내가 할당할 resize 크기보다 크다)
2. 확장 불가능
- [alloc, free] 이지만 (alloc + free 공간이 내가 할당할 resize 크기보다 작다)
- [alloc, epilogue] 로 아예 heap 자체를 확장해야 하는 경우 -> [alloc, free, epilogue] 도 적용
위 2가지 케이스를 벗어나는 경우, 그냥 heap을 확장하거나 가능한 영역을 찾아서 memcpy로 복제하는 방법이 있다.
4일차 (2026-04-14 - 화)
최대한 점수를 내기 위해 노력한 과정을 공유하고 코드 리뷰
넷째날 시작 오후 10시
넷째날 마무리 새벽 1시
회의 주제 : 각자 AI를 적극 활용해서 점수가 가장 많이 나올 것이라 예상한 로직을 구현해서 코드 공유
너무 내용이 길어져서 4일차는 간단하게 내가 구현한 코드에 대한 리뷰를 작성하고자 한다. (너무 시간을 많이 소비했다..)
더보기
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
/* 단일 워드(4) 또는 더블 워드(8) 정렬 */
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1 << 10) //(1 << 12)
#define ALIGNMENT 8
/* 크기를 ALIGNMENT의 배수로 올림 */
/*
예를 들어, 15byte를 할당 시,
(15 + 7)
10110 & 11111000 = 10000 -> (16)
예를 들어, 16byte를 할당 시,
(16 + 7)
10111 & 11111000 = 10000 -> (16)
예를 들어, 17byte를 할당 시,
(17 + 7)
11000 & 11111000 = 11000 -> (24)
즉, 올림처리
*/
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MINBLOCKSIZE (DSIZE + (2 * SIZE_T_SIZE))
#define SEG_LIST_COUNT 16
#define SEG_ROOT_BYTES (SEG_LIST_COUNT * SIZE_T_SIZE)
#define SEG_MAX_INDEX (SEG_LIST_COUNT - 1)
#define SEG_INDEX(size) \
((size) <= MINBLOCKSIZE ? 0 \
: (size) <= 1 << 5 ? 1 \
: (size) <= 1 << 6 ? 2 \
: (size) <= 1 << 7 ? 3 \
: (size) <= 1 << 8 ? 4 \
: (size) <= 1 << 9 ? 5 \
: (size) <= 1 << 10 ? 6 \
: (size) <= 1 << 11 ? 7 \
: (size) <= 1 << 12 ? 8 \
: (size) <= 1 << 13 ? 9 \
: (size) <= 1 << 14 ? 10 \
: (size) <= 1 << 15 ? 11 \
: (size) <= 1 << 16 ? 12 \
: (size) <= 1 << 17 ? 13 \
: (size) <= 1 << 18 ? 14 \
: 15)
/**
* 사이즈를 지정할 때, 왜 size_t로 8바이트 데이터 타입을 쓰는지 생각해보니
* 메모리 용량이 4바이트일 경우 2^32 = 2^10 = 1000byte -> (1000)^3 * 2^2 = 4 * 10^9 = 4,000,000kB = 4,000Mb = 4Gbyte
* 메모리 용량이 4기가 보다 더 클 수도 있기 때문에 (나의 생각)
*/
#define PACK(size, alloc) ((size) | (alloc))
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
#define GET2(p) (*(void **)(p)) // 포인터 값을 조회하기 위한 용도
#define PUT2(p, val) (*(void **)(p) = (val)) // 포인터 값을 저장하기 위한 용도
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
// 여기서 footer를 안 쓰면, footer에 정보를 넣을 수 가 없다.
#define HDRP(bp) ((char *)(bp) - WSIZE)
/**
* 내 생각
* 4바이트씩 PRED, SUCC 할당하면 8바이트만 늘리면 되고, 4바이트 안에 주소가 다 넣을 정도의 예시들만 있을 것 같다.
* 원래 64bit 컴퓨터라면 8바이트를 할당해야 하긴 한다.
* -> 물어보니
* 무조건 포인터 크기는 플랫폼에 따라 고정되므로
* 할당하는 데이터 크기 (4바이트냐 8바이트냐) 상관없이 주소를 저장하려면 포인터 크기만큼 무조건 필요
*/
#define PRED(bp) ((char *)(bp)) // 현재 bp의 PRED가 저장되어 있는 위치
#define SUCC(bp) ((char *)(bp) + SIZE_T_SIZE) // 현재 bp의 SUCC가 저장되어 있는 위치
#define GET_PRED(bp) ((char *)GET2(PRED(bp)))
#define GET_SUCC(bp) ((char *)GET2(SUCC(bp)))
#define SET_PRED(bp, ptr) (PUT2(PRED(bp), (ptr)))
#define SET_SUCC(bp, ptr) (PUT2(SUCC(bp), (ptr)))
#define SEG_HEAD(index) ((char *)(seg_free_listp + ((index) * SIZE_T_SIZE)))
#define GET_SEG_HEAD(index) ((char *)GET2(SEG_HEAD(index)))
#define SET_SEG_HEAD(index, ptr) (PUT2(SEG_HEAD(index), (ptr)))
#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)))
static char *heap_listp;
// 가용 리스트에 제일 앞에 담기는 것
// 정해진 리스트의 개수를 배열로 담는 그릇
static char *seg_free_listp;
/*
* SEG LIST 전환 힌트
* - 지금은 `heap_free_listp` 하나만 쓰는 단일 explicit free list 구조다.
* - 다음 단계에서는 `static char *seg_free_listp[SEG_LIST_COUNT];` 같은 head 배열로 바꾸는 쪽이 가장 단순하다.
* - `SEG_INDEX(size)`는 "이 크기의 free block이 어느 리스트로 들어가야 하는가"를 빠르게 정하는 용도다.
*
* 함수 추가/수정 힌트
* - `mm_init`
* 모든 seglist head를 NULL로 초기화해야 한다.
* 만약 head 배열을 힙 앞부분에 둘 생각이면 `SEG_ROOT_BYTES`만큼 prologue 전에 추가 공간을 확보하면 된다.
*
* - `push_free`
* 이제는 단일 head가 아니라 `SEG_INDEX(GET_SIZE(HDRP(bp)))`로 class를 구해서
* 해당 class head에만 LIFO 방식으로 insert하면 된다.
*
* - `rem_free`
* 제거할 블록의 현재 크기로 class를 다시 구한 뒤,
* 그 class list 안에서만 pred/succ를 끊어주면 된다.
*
* - `find_fit`
* 요청 크기의 class에서 시작해서 더 큰 class로 올라가며 탐색하면 된다.
* 처음에는 "각 class 내부 first fit + 상위 class 순차 탐색"만 해도 구현이 단순하고 충분히 빠르다.
*
* - `coalesce`
* 이웃 free block이 있으면 각각 자기 class list에서 먼저 제거한 뒤 합친다.
* 그리고 최종 병합 블록 한 개만 새 크기에 맞는 class로 다시 insert해야 한다.
*
* - `place` / `place_allocated`
* 할당 전에 원래 free block은 해당 seglist에서 제거해야 한다.
* split이 생기면 남은 free block은 "남은 크기 기준 class"로 다시 insert해야 한다.
*
* - 필요하면 나중에 `find_fit` 안에서만 쓸 작은 helper를 하나 더 만들어도 된다.
* 예: "특정 class head를 가져오는 함수", "다음 non-empty class를 찾는 함수"
*/
static void *extend_heap(size_t words);
static void *coalesce(void *bp);
static char *find_fit(size_t size);
static void place(char *bp, size_t asize);
static void place_allocated(char *bp, size_t block_size, size_t asize, int coalesce_split);
static void push_free(void *p);
static void rem_free(void *p);
/*
* mm_init - malloc 패키지 초기화.
*/
int mm_init(void)
{
// (void*) -1
/**
* (void *)는 모든 타입을 저장할 수 있는 저장소 (주소만 알 수 있음)
* 즉, 어떤 타입이든 담을 수 있는 generic pointer
* 주소만 가지고 있고, 역참조하려면 캐스팅 필요
*
* (void*) -1 (유효하지 않은 주소)
* 보통 시스템 콜 실패 시 반환값!
*/
size_t prologue_size = SEG_ROOT_BYTES + DSIZE;
if ((heap_listp = mem_sbrk(SEG_ROOT_BYTES + (4 * WSIZE))) == (void *)-1)
return -1;
PUT(heap_listp, 0); // 4 byte 패딩 설정
PUT(heap_listp + (1 * WSIZE), PACK(prologue_size, 1));
seg_free_listp = heap_listp + (2 * WSIZE);
for (int i = 0; i < SEG_LIST_COUNT; i++)
{
SET_SEG_HEAD(i, NULL);
}
PUT(heap_listp + SEG_ROOT_BYTES + (2 * WSIZE), PACK(prologue_size, 1));
PUT(heap_listp + SEG_ROOT_BYTES + (3 * WSIZE), PACK(0, 1));
heap_listp = seg_free_listp;
if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
return -1;
return 0;
}
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
if ((bp = mem_sbrk(size)) == (void *)-1)
{
return NULL;
}
// 이거 때문에 초기화 할 때, 패딩과 프롤로그 헤더를 따로 만든다.
PUT(HDRP(bp), PACK(size, 0)); // free block header
PUT(FTRP(bp), PACK(size, 0)); // free block footer
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // new epilogue header
// 힙을 늘릴 때, 앞에 있는 것이 Free일 수 도 있기 때문
// 힙 확장 전략을 고려한 것 (My Think 검증 아직 안함)
return coalesce(bp);
}
// heap_free_listp에 스택 방식으로 집어넣기
static void push_free(void *p)
{
if (p == NULL)
{
return;
}
// 1. 사이즈를 구한다.
size_t size = GET_SIZE(HDRP(p));
// 2. 사이즈에 맞는 클래스를 찾는다.
char index = SEG_INDEX(size);
// 3. LIFO 방식으로 집어넣는다.
char *old_ptr;
old_ptr = GET_SEG_HEAD(index);
/**
* PUT2(PRED(p), NULL);
* PUT2(SUCC(p), old_ptr);
*/
SET_PRED(p, NULL);
SET_SUCC(p, old_ptr);
if (old_ptr != NULL)
{
SET_PRED(old_ptr, p);
}
SET_SEG_HEAD(index, p);
}
// heap_free_listp에 스택 방식으로 빼기
// 만약에 rem_free할 공간을 찾질 못한다면?
static void rem_free(void *p)
{
// 1. 먼저 사이즈를 구한다.
if (p == NULL)
{
return;
}
size_t size = GET_SIZE(HDRP(p));
// 2. 사이즈에 맞는 클래스를 찾는다.
char index = SEG_INDEX(size);
// 3. LIFO 방식으로 클래스에서 찾아서 제거한다.
// -> 하지만 그 클래스에 아무것도 존재하지 않는다면
// -> 다음 블럭으로 넘어가서 체크를 해봐야 한다.
// 중요!!
if (index < SEG_LIST_COUNT)
{
char *pred = GET_PRED(p);
char *succ = GET_SUCC(p);
/**
* 만약 없어진게 첫번째꺼라면
* free list 첫번째에 값 집어넣기
**/
if (pred == NULL)
{
SET_SEG_HEAD(index, succ);
}
else
{
// 앞에 있는거의 뒤를 다음걸로 설정
SET_SUCC(pred, succ);
}
// 만약 마지막이 아니라면,
if (succ != NULL)
{
// 뒤에 있는거의 앞을 이전걸로 설정
SET_PRED(succ, pred);
}
// 중요!!
SET_PRED(p, NULL);
SET_SUCC(p, NULL);
return;
}
return;
}
static void *coalesce(void *bp)
{
char *prev_bp = PREV_BLKP(bp);
char *next_bp = NEXT_BLKP(bp);
size_t prev_alloc = GET_ALLOC(FTRP(prev_bp));
size_t next_alloc = GET_ALLOC(HDRP(next_bp));
size_t size = GET_SIZE(HDRP(bp));
// free 전략을 취할 때,
// 합치면서 heap_free_listp에 있는거 제거 후 다시 추가
// 여기서 나는 계속 rem_free(bp)를 해줬었는데,
// 아직 bp는 생각해보니 heap_free_listp에 들어가지 않은 상태였다.. 할필요가 없었다.. (crash 발생 원인..ㅜㅜ)
if (!prev_alloc)
{
rem_free(prev_bp);
size += GET_SIZE(HDRP(prev_bp));
bp = prev_bp;
}
if (!next_alloc)
{
rem_free(next_bp);
size += GET_SIZE(HDRP(next_bp));
}
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
push_free(bp);
return bp;
}
static void place_allocated(char *bp, size_t block_size, size_t asize, int coalesce_split)
{
size_t remain_size = block_size - asize;
char *split_ptr;
if (remain_size < MINBLOCKSIZE)
{
PUT(HDRP(bp), PACK(block_size, 1));
PUT(FTRP(bp), PACK(block_size, 1));
return;
}
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
split_ptr = NEXT_BLKP(bp);
PUT(HDRP(split_ptr), PACK(remain_size, 0));
PUT(FTRP(split_ptr), PACK(remain_size, 0));
// realloc처럼 allocated block 중간에서 split한 free block은 다음 블록과 바로 이어질 수 있으므로 coalesce 경로가 필요하다.
// mm_malloc에서 원래 free block을 잘라 쓰는 경우에는 이미 coalescing이 끝난 상태라 push_free만 해도 된다.
if (coalesce_split)
{
coalesce(split_ptr);
}
else
{
push_free(split_ptr);
}
}
/*
* mm_malloc - brk 포인터를 늘려 블록 할당.
* 항상 정렬 배수 크기의 블록을 할당한다.
*/
void *mm_malloc(size_t size)
{
size_t asize;
size_t extendsize;
char *bp;
if (size == 0)
return NULL;
/**
* explicit free list의 경우
* pred, succ가 8바이트씩 더 잡는다고 생각해서 무조건 32byte가 최소단위라고 생각했는데,
* 아니고 기존 payload 위치를 pred, succ가 대체한다고 생각해야함..
*
* size의 경우는 예제에 따라 4byte로 넣어도 상관없지만
* 주소는 64bit의 컴퓨터의 경우 환경에 따라 8byte로 주소가 들어갈 수 있으므로
*
* MINBLOCKSIZE = 24 byte
*/
asize = MAX(ALIGN(size + DSIZE), MINBLOCKSIZE);
// 할당 하기 전에 영역 전부를 다 살펴보고
// place를 통해 그 자리에 할당
if ((bp = find_fit(asize)) != NULL)
{
place(bp, asize);
return bp;
}
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
return NULL;
place(bp, asize);
return bp;
}
/**
* find_fit
*/
static char *find_fit(size_t size)
{
int index = SEG_INDEX(size);
while (index < SEG_LIST_COUNT)
{
char *bp = GET_SEG_HEAD(index);
while (bp != NULL)
{
// 안에서 Linked List 방식으로 탐색 중
size_t free_size = GET_SIZE(HDRP(bp));
if (!GET_ALLOC(HDRP(bp)) && free_size >= size)
{
return bp;
}
bp = GET_SUCC(bp);
}
index += 1;
}
return NULL;
}
static void place(char *p, size_t asize)
{
// 실제 사이즈
size_t real_size = GET_SIZE(HDRP(p));
rem_free(p);
place_allocated(p, real_size, asize, 0);
}
/*
* mm_free - 블록 해제 시 아무 동작도 하지 않음.
*/
void mm_free(void *ptr)
{
if (ptr == NULL)
{
return;
}
// *(size_t *)ptr = 0;
size_t size = GET_SIZE(HDRP(ptr));
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
coalesce(ptr);
}
void *mm_realloc(void *ptr, size_t size)
{
// free alloc free
// 1. 사이즈가 감소할 경우 -> place로 자르기
// 2. 뒤에 free가 있고, 뒤에 사이즈를 더한 값이 size보다 클 경우에는 딱 충분한 크기만큼만 확장 (free일 경우) - place를 사용해서 구현
// 3. 뒤가 확장이 불가능한 eplilogue header일 경우
// 4. 이 경우들 다 빼고 예외상황에는 단순구현으로
if (ptr == NULL)
{
return mm_malloc(size);
}
if (size == 0)
{
mm_free(ptr);
return NULL;
}
void *newptr;
char *next_bp = NEXT_BLKP(ptr);
size_t asize = MAX(ALIGN(size + DSIZE), MINBLOCKSIZE); // 요청크기
size_t cur_size = GET_SIZE(HDRP(ptr));
size_t next_size = GET_SIZE((HDRP(next_bp)));
size_t copySize;
// 1. 요청 크기가 더 작아진 경우에는 같은 자리에서 바로 잘라서 남는 부분만 free block으로 돌려준다.
if (asize <= cur_size)
{
// 이걸 하는게 더 메모리 효율이 좋을까? 나쁠까? 분석
// place_allocated(ptr, cur_size, asize, 1);
return ptr;
}
// 1-1. malloc으로 공간있는지 먼저 확인
// realloc에서는 현재 allocated block 자체에 coalesce(ptr)를 직접 쓰면 안 된다.
// 2. 확장가능 alloc free
// 이전 free block과 합쳐지면 payload 시작 주소가 바뀔 수 있기 때문이다.
// 따라서 바로 뒤 free block만 free list에서 제거해서 현재 블록 뒤에 직접 붙인다.
if (!GET_ALLOC(HDRP(next_bp)) && (cur_size + next_size) >= asize)
{
rem_free(next_bp);
place_allocated(ptr, cur_size + next_size, asize, 1);
return ptr;
}
// 바로 뒤가 epilogue면 heap을 늘린 뒤, 다시 한 번 "뒤 free 붙이기"를 시도한다.
// 공간이 없으므로 추가
if (next_size == 0 || (!GET_ALLOC(HDRP(next_bp)) && (cur_size + next_size) < asize))
{
// 3. 확장불가능
/**
* -> [alloc free]이지만, alloc + free가 asize보다 작은 경우 -> [*alloc free alloc] -> [alloc alloc]으로, 확장 불가능한 경우
* -> [alloc epilogue]으로, 아예 heap 자체를 확장해야하는 경우 -> [alloc free epilogue]
**/
// MAX(asize - cur_size, CHUNKSIZE)
if (extend_heap((asize - cur_size) / WSIZE) != NULL)
{
// 2번째 케이스
next_bp = NEXT_BLKP(ptr);
next_size = GET_SIZE(HDRP(next_bp));
if (!GET_ALLOC(HDRP(next_bp)) && (cur_size + next_size) >= asize)
{
rem_free(next_bp);
place_allocated(ptr, cur_size + next_size, asize, 1);
return ptr;
}
}
}
// 위 경로가 모두 실패하면 새 블록을 받아서 옮기는 단순 fallback으로 처리한다.
// mm_malloc이 내부에서 find_fit/place를 모두 처리하므로 realloc에서는 free block을 직접 다루지 않는 편이 안전하다.
newptr = mm_malloc(size);
if (newptr == NULL)
{
return NULL;
}
// 복사 길이는 "기존 payload 크기"와 "새 요청 크기" 중 작은 값이어야 한다.
// block 전체 크기를 memcpy에 넣으면 header/footer까지 읽을 수 있다.
copySize = cur_size - DSIZE;
if (size < copySize)
{
copySize = size;
}
memcpy(newptr, ptr, copySize);
mm_free(ptr);
return newptr;
}
내가 구현한 코드는 buddy system을 활용해서 struct나 배열을 쓰지 않고, 주소를 할당해서 크기에 따른 Free Block List를 나누고 실제로 들어간 코드는 Explicit Free List의 LIFO 방식을 채택해서 구현했다.
여기에 realloc에 대한 정리 내용도 들어가 있고.. 하루종일 이것만 쓸 순 없기에 여기서 끝내고자 한다..
확실히 많은 것을 배운 한 주 였다.
기간 (2026-04-10 ~ 2026-04-15)
'정글캠프-WIL' 카테고리의 다른 글
| C언어로 구현한 자료구조 회고 (0) | 2026.04.09 |
|---|
