2025. 10. 23. 23:40ㆍMalloc Lab
지금 필자의 심정은 이러하다.
필자의 18년차(필자는 07년식이다.) 인생 최대의 위기가 다가왔다 바로 mallocLab이다.
c언어의 malloc 함수를 직접 이번주차에 구현해야하는데, 일단 작성해야할 코드파일이 너무 많다.
그리고 malloc 함수를 직접 구현한다는게.... 음..... 어떻게 하는걸까..?
오늘은 이 malloc 구현이라는 절망을 마주치기 전에 이 폭풍전야에 한번 기존 malloc 함수가 어떻게 구현되었는지,
그리고 동적 할당의 원리는 뭔지, 활용은 어떻게 하는지 한번 이 malloc 이 친구의 생기부 부터 LinkedIn 프로필,
거기에 TMI까지 한번 안나올때까지 털어보자.
1. 말록의 와꾸
말록이는 어떻게 생겼을까?
우선 말록이는 어렸을 때에는 K&R 스타일로 생겼다.
K&R 스타일은 예에ㅔ전에 유닉스에서 쓰던 초초초초 간단한 방식으로,
힙에 큰 메모리 공간을 올려두고, 그걸 블록 단위로 잘라서 빈 블록 목록에 담아 두는데, 여기서 빈 블록 목록을 free list라고 한다.
요청이 들어오면 free list에서 크기가 맞는 블록을 골라 떼어 준다.
이걸 first-fit이라고도 부른다.
아주 큰 피자를 조각내서 배고픈 사람들이 요청한 만큼 조각을 나눠주는 거라고 생각하면 좋다.
TMI로 free등을 통해 반납한 블록들이 이웃해서 모두 비어 있다면, 서로 붙여서 더 큰 하나의 블록으로 만든다.
말록이가 이제 좀 커서 초등학생이 됐는데, 이때는 dlmalloc 방식이 된다.
dlmalloc은 Doug Lea라는 겁나 쩌는 컴퓨터 과학자분이 만들어서 Doug Lea's malloc을 줄여서 dlmalloc이다.
기존의 K&R 스타일은 free list의 탐색비용과 단편화가 높았고,
이를 개선하기 위해 빠른 평균 성능과 적당한 단편화를 동시에 목표로 하며 개발됐다.
dlmalloc은 빈 블록들을 크기별로 분류해서 넣어두는 상자들 bin에 분류(작은 건 small bins인 이중 연결 리스트
→ O(1)에 가까운 탐색, 큰 건 tree bins인 균형 트리에 넣음 → O(log n) 탐색)하고,
만약에 bin에서 빈 블록을 못 찾는다면, 즉시 힙의 맨 끝에 남아 있는 큰 덩어리인 top chunk에서 잘라서 쓰고,
아주 큰 블록을 요구하면 따로 파일이나 익명 메모리를 가상 주소 공간에 직접 매핑하는
mmap(메모리 매핑 시스템 콜)으로 주는 방식이다.
피자 가게에서 아주 큰 파티 주문은 가게 창고에서 조달하지 않고,
외부에 미리 만든 피자가 쌓인 물류 창고에서 직배송했다가 파티가 끝나면 바로 반납 하는 것과 비슷하다.
TMI로 반납 시에는 이웃한 빈 블록들을 확인하여 즉시 병합하고, 할당 시에는 분할해서 단편화를 줄인다.
이제 고3이 된 말록이는 ptmalloc이 됐다.
기존의 dlmalloc은 아주 좋은 아이디어였지만, 멀티스레드 환경에서는 락 경합이 커지면 느려지는 현상이 생겼다.
자 여기서 락 경합이란 지금 스레드 하나가 쓰고있는 메모리 공간을 공유 자료구조를 보호하는 임계구역 으로 지정하여
다른 스레드가 그 구역 만큼 못쓰게 하는 락 이라는 기능에 의해,
여러 스레드가 차지하려고 동시에 몰려서 한 스레드만 들어가고 나머지는 기다리느라
여러 스레드들을 활용 못해 성능이 떨어지는 현상이다.
이 락 경합을 해결하기 위해 glibc(GNU C Library의 약자로, 리눅스에서 사용하는 표준 C 라이브러리) 쪽에서 스레드 환경에 맞게
dlmalloc을 리눅스 + 멀티스레드 실전용으로 개조한 버전이 ptmalloc이다.
우선 기존의 전역 힙 하나에서 작은 힙 풀인 아레나를 여러 개 만들어서 스레드들이 서로 다른 아레나를 쓰게 해 락 경합을 줄인다.
또한 기존의 전역 힙 하나에 락을 걸었듯, 아레나마다 별도의 락을 걸어놔서 한 스레드가 잡은 락이 다른 스레드를 막지 않게 했다.
스레드마다 로컬 캐시를 둬서 작은 블록을 요청할 때에는 스레드의 개인 주머니인 스레드 로컬 캐시를 사용해서
락 없이 초고속으로 사용한다. 이 캐시를 tcache라고 한다.
이 외에도 경로 최적화, 정책 및 트림 튜닝, 트레이드오프등을 추가했다.
마치 이제 피자를 먹기 위해서 개인용 피자 주머니가 사람마다 생기고, 하나의 피자가게 본점 대신 여러 체인점들이
생겨서 각각의 사람들의 주문을 수행할 수 있게 됐다고 이해하면 좋다.
이 다음부터는 ptmalloc의 대안으로 다양한 malloc들이 등장한다.
마치 RPG게임에서 전직 경로를 선택하는 것처럼 말이다.
대표적인 malloc으로는
대규모 병렬 워크로드에서도 매우 낮은 평균 지연 시간을 지닌 tcmalloc,
대규모 서비스에서 단편화를 억제하고 안정적인 지연 시간을 jemalloc이 있다.
2. 말록이의 내부
이제 이 친구의 내부를 알아보자.
우리가 물론 저 사진처럼 해부학 하는거 아니고 그냥 malloc 함수가 어떻게 되어있는지 보는거 뿐이니 겁먹지마라.
malloc 함수는 크게 모델, 정책, 메커니즘 이 3개로 이루어진다. 한번 차근차근 알아보자.
(1) 모델 - 힙을 블록 집합으로 보는 관점
힙은 크기와 상태(비어있음 / 사용중)를 가진 블록들의 집합이다.
프로그램이 malloc 함수를 통해 메모리 할당을 요청하면 C로 구현된 메모리 할당기(=malloc)는 요청 크기 이상
(정렬과 메타데이터 때문에 좀 더 크게 줘야 하고, 요청 크기대로 줄 수 있는게 아닌 블록 단위로 줘야하기에
요청크기보다 클 수도 있다.)의 블록을 하나 꺼내주고,
malloc(sizeof(int))등의 경우, 요청 크기를 내부 단위로 보정 후 필요 시 분할하여 정확한 크기에 맞춘다.
반대로, free()등을 통한 반납이 오면 반납되는 블록을 비어 있음으로 표시하고,
경우에 따라 인접한 빈 블록과 병합하여 더 큰 블록으로 되돌린다.
요청과 반납에서의 모든 블록들은 정렬 규칙(예: 8, 16 바이트 경계에 맞춰야 한다.)을 지켜야 하고,
분할과 병합 같은 형태 변화가 안전하게 수행되기 위해
각 블록의 경계에는 크기와 상태를 담은 최소한의 메타데이터가 있어야 한다.
요약하면, 모델의 목표는 같은 총 용량으로도 “항상 맞는 크기의 블록을 꺼낼 수 있게” 집합의 형태를 동적으로 관리하는 데 있다.
(2) 정책 - 어떤 블록을 줄지와 공간을 어떻게 관리할지
malloc으로 구현한 메모리 할당기는 요청이 오면 먼저 어떤 블록을 줄지 결정한다.
보통 크기가 처음 맞는 것인 first-fit이나, 가장 꼭 맞는 best-fit,
사이즈 클래스인 bin으로 분류된 목록에서 요청 크기 이상을 고른다.
줄 블록을 선택한 뒤에는 선택한 블록이 크다면 분할해서 필요한 만큼 준 뒤, 잔여 공간이 최소 블록 크기 미만이면, 분할하지 않고
통째로 주어 스플린터(분할 후 남은 크기 < 최소 블록 크기 일 때 잔여 공간이 재활용 불가능해서 메모리를 낭비 하는 현상)를 막
프로그램이 free()등을 통해 반납 시에는 반납 블록과 인접한 빈 블록을 병합하여 더 큰 연속 공간을 회복하며
힙 내부 재조정이 이루어진다.
만약 요청 단계에서 내부에 적합한 블록을 못 찾으면 공급 단계로 넘어가서
요청크기가 mmap 임계치 이하라면 힙을 확장하고,
임계치 이상이면 mmap(메모리 매핑 시스템 콜)을 호출하여 OS에게 별도 매핑을 받는다.
마지막으로 반납 단계에서는 반납 정책에 따라 오래 비는 큰 영역은 트림이나 언매핑으로 커널에 돌려주며 메모리 발자국을 줄인다.
malloc은 find(어떤 블록을 줄지), shape(힙 내부 재조정), supply(mmap에게 메모리 공급), return(커널에 돌려주기)의
4개 정책을 통해 속도, 단편화, 메모리 사용량의 균형을 잡는다.
(3) 메커니즘 - 정책을 빠르고 안전하게 수행하는 장치들
위의 정책들을 실전에서 빠르고 안전하게 돌리기 위해서, 힙 내부에는 몇가지 장치가 필요하다.
첫 번째 장치인 인덱싱은 빈 블록을 사이즈 클래스(=bin)로 나누고,
최근 반납했거나 초소형인 블록은 fastbin이나 tcache 같은 매우 빠른 경로에 둔다.
이를 통해 요청 크기 이상의 블록들을 상수 시간에 가깝게 찾는게 가능해진다.
두 번째 장치인 일관성 메타데이터는 블록과 블록의 사이인 블록 경계에 크기와 상태를 저장하여 분할이나 병합시에
이웃 블록의 확인이 즉시 가능하고, 정렬과 최소 블록 크기 불변식을 지켜서 스플린터를 방지한다.
세 번째 장치인 확장과 축소는 공급시에 사용하는 커널 호출의 비용은 매우 비싸기에,
이를 자잘한 경우에 사용하지 않게 막아주고 메모리를 절약 시켜주는 장치이다.
확장은 sbrk 계열의 시스템 호출을 통해 힙 끝을 한 번에 큼직하게 늘리고,
앞단에 top chunk를 유지하여 그 안에서 잘라 쓰며 커널 호출 빈도를 줄여주고,
축소는 오래 비는 큰 블록은 커널 호출을 통해 OS에 반납하여 프로세스가 DRAM에 실제로 차지 중인 용량을 줄여준다.
또한 확장과 축소는 임계치 이상을 mmap으로 별도 매핑해주어 즉시 반납이 쉽게 해준다.
네 번째 장치인 동시성과 캐시는 멀티스레드에서 락 경합을 줄이고 평균 속도를 높이고 꼬리 지연을 낮추기 위해
다중 아레나를 사용하고, 작은 블록을 락 없이 즉시 재사용할 수 있게 tcache를 사용하고,
지연 병합으로 빠른 반납과 할당 지원을 하는 fastbin을 사용한다.
마지막으로, 검증과 계측은 내부 재조정(분할, 병합, 리스트 조작) 중 불변식이 깨지지 않도록 힙 체커를 통해
정렬 만족, 헤더와 푸터의 일치, 연속 free 금지, free list의 무결성, 힙 스윕 합계와 리스트 합계가 같은지를 검증하고,
어서션(항상 참인 조건이 참이 아니면 코드를 즉시 중단 시키는 것)과 블록 수, free 합계, 호출 횟수 등을 숫자로 기록하여
디버깅과 성능 분석에 이용하도록 계측한다.
3. 말록이를 굴려보자
이제 말록이의 인생과 생김새, 내부 구성 요소까지 알아봤으니 굴릴 시간이다.
간단한 C언어 malloc 함수 사용 예제들을 보며 말록이를 노동시킬 방법을 알아보자.
int *intPtr = malloc(sizeof(int)); // int의 크기(4바이트)만큼 할당하고, 할당한 주소를 포인터에 저장
.
.
.
free(intPtr); // 사용 후에는 반드시 free를 통해 반납해줘야 메모리를 절약할 수 있다.
보통 이런식으로 포인터를 통한 Call by reference 사용 + 할당을 위해 사용하고 free를 통해 반납한다.
int *intPtr = malloc(sizeof *intPtr); // sizeof(int) 대신 sizeof *intPtr로 해도 된다 둘다 4바이트임
이런식으로도 쓸 수 있다.
int *intPtr = malloc(10 * sizeof(int));
.
.
.
free(intPtr)
이런식으로 배열도 가능하다.
하나 알아두면 좋은 점으로, malloc은 할당 실패시 NULL을 반환한다는 점이다.
오늘도 긴 글 읽어줘서 고맙다.
즐코딩.