[CS:APP] malloc 구현 코드로 이해하는 9.9 동적 메모리 할당

Об этом предложении

항목 이 구현의 선택 빈 블록 관리 묵시적 빈 리스트 블록 형식 헤더 + 페이로드 + 푸터 (경계 태그) 배치 정책 first fit 연결 free 시점에 즉시 연결 정렬 8바이트 (더블워드) 워드 크기 4바이트 0. 할당기가 풀어야 할 네 가지 질문 (9.9.5) 가장 단순한 할당기는 힙을 큰 바이트 배열로 보고 포인터 p 만 유지함. malloc 은 p 를 size만큼 올리고, free 는 아무것도 안 함. 처리량은 최고지만 블록을 재사용하지 않아서 이용도는 최악임. 그래서 실용적인 할당기는 네 가지를 정해야 함. 질문 이 구현의 답 코드 빈 블록을 어떻게 추적? 묵시적 리스트 헤더 크기를 따라 순회 어느 빈 블록에 넣을까? (배치) first fit find_fit 남는 부분은? (분할) 나머지가 16B 이상이면 분할 place 해제된 블록은? (연결) 즉시 연결 mm_free → coalesce 할당기의 제약과 목표 (9.9.3) 제약 임의의 malloc / free 순서를 처리해야 함 요청을 모았다가 재배열하지 않고 즉시 응답 해야 함 할당기의 자료구조도 힙 안에만 저장해야 함 정렬 요구를 지켜야 함 이미 할당된 블록은 수정/이동 금지 임 (그래서 압축 불가) 목표 처리량 : 단위 시간당 처리하는 요청 수 메모리 이용도 : 응용이 요청한 데이터 총량 ÷ 힙 크기 이 둘은 서로 충돌함. 빠르게 하면 알뜰하지 못하고, 알뜰하게 하려면 오래 탐색해야 함. 그 균형을 잡는 게 설계의 핵심임. 1. 블록 구조 힙 전체의 모양 [ 패딩 ][ 프롤로그 ][ 일반 블록 ][ 일반 블록 ] ... [ 에필로그 ] ↑ heap_listp 구성 설명 패딩 정렬을 맞추기 위한 빈 칸(4B) 프롤로그 크기 8B, 항상 allocated . 헤더+푸터만 있는 가짜 블록 일반 블록 malloc / free 로 생기는 블록들 에필로그 헤더만 있고 크기 0, allocated 비트 1. 힙의 끝 표지 프롤로그/에필로그를 두는 이유 연결( coalesce )할 때 현재 블록의 앞/뒤 블록 상태를 확인함. 힙 맨 앞/뒤 블록이면 이웃이 없을 수 있어서, 원래는 "이웃이 존재하는가?"를 따로 검사해야 함. 항상 allocated인 가짜 블록을 양 끝에 두면, 모든 블록에 대해 이 검사 없이 똑같은 코드로 처리됨. 에필로그의 값이 0/1 인 이유 크기 0 : 정상 블록은 최소 크기 때문에 0일 수 없음. 헤더를 읽었는데 크기가 0이면 "힙의 끝"으로 판단하고 탐색을 멈출 수 있음. alloc = 1 : 0이면 할당기가 free 블록으로 착각해서 쓰려고 할 수 있음. 절대 가용 블록으로 취급하지 않게 1로 설정함. 블록 하나의 구조 ┌─────────┬──────────────────┬─────────┐ │ 헤더 4B │ payload │ 푸터 4B │ │ size|a │ │ size|a │ └─────────┴──────────────────┴─────────┘ ↑ bp 헤더/푸터 : 블록 전체 크기(헤더+페이로드+푸터+패딩)와 할당 여부를 담음. payload : 사용자가 실제로 쓰는 공간임. int *p = malloc(20); 에서 p 가 가리키는 곳임. bp : 첫 번째 payload 바이트를 가리키는 포인터임. 블록의 시작이 아니라 payload의 시작 이라는 점이 제일 중요함. 응용 프로그램은 헤더의 존재를 모름. 할당기 내부에서 헤더에 접근할 때만 bp 에서 4바이트를 빼서 찾음. 헤더/푸터가 필요한 이유 블록이 얼마나 큰지, 사용 중인지 알아야 함. 앞뒤에 어떤 블록이 있는지 알아야 함. free 할 때 어디와 합칠지 알아야 함. 헤더 32비트를 쪼개 쓰는 법 31 3 2 1 0 ┌──────────────────────────┬──┬──┬──┐ │ block size │ 0│ 0│ a│ a=1: 사용 중, a=0: free └──────────────────────────┴──┴──┴──┘ 가능한 이유는 모든 블록의 크기가 8의 배수이기 때문 임. 32 = 0010 0000 40 = 0010 1000 48 = 0011 0000 8 = 23이라서 8의 배수는 이진수 끝 3자리가 항상 000 임. 어차피 비어 있는 자리라서 그중 최하위 비트를 "allocated" 정보로 재활용함. 예를 들어 할당된 24바이트( 0x18 ) 블록의 헤더는 0x18 | 0x1 = 0x19 , 빈 40바이트( 0x28 ) 블록의 헤더는 0x28 | 0x0 = 0x28 임. 이걸 다루는 매크로가 PACK() , GET_SIZE() , GET_ALLOC() 임. 왜 8의 배수여야 하나 → 정렬때문! malloc 이 반환한 메모리에 어떤 타입이 들어갈지 할당기는 모름. 그래서 가장 엄격한 정렬로 맞춰 둠. 정렬이 안 맞으면 느려지거나, 일부 CPU/명령어에서는 오류가 남. 이 구현은 payload 시작 주소를 8의 배수 로 맞춤. 패딩 워드를 맨 앞에 넣는 이유 패딩 없이 시작: [헤더 4B][payload] payload 시작 = 0x04 X 패딩 4B 추가: [패딩 4B][헤더 4B][payload] payload 시작 = 0x08 O 헤더가 4바이트라서, 헤더 바로 뒤의 payload를 8의 배수에 두려면 헤더가 8n+4 위치에 있어야 함. 첫 블록만 맞으면 뒤도 다 맞음. 블록 크기가 항상 8의 배수 라서 다음 헤더도 8n+4 위치가 되기 때문임. 묵시적 리스트와 최소 블록 크기 묵시적 리스트 빈 블록끼리 포인터로 연결돼 있지 않음. 헤더의 크기 필드를 따라 힙의 모든 블록을 훑어서 빈 블록을 찾음. 그래서 "묵시적"임. 장점은 단순함이고, 단점은 탐색 비용이 (할당+빈) 전체 블록 수에 비례 한다는 것임. 최소 블록 크기: 16바이트 헤더 4B + 푸터 4B + 정렬을 위한 최소 payload 8B임. 1바이트를 요청해도 16바이트 블록이 만들어짐. 할당기가 하는 일 요약 malloc() → free block을 찾아서 allocated로 변경 free() → allocated block을 free로 바꾸고 옆 free block과 합침 extend_heap() → 에필로그 자리에 새로운 free block 추가 2. memlib.c - 힙 공간 구현 (9.9.1) 실제 프로세스 힙 대신 큰 배열을 힙처럼 만들어 사용함. void *mem_sbrk(int incr) { char *old_brk = mem_brk; if ((incr < 0) || ((mem_brk + incr) > mem_max_addr)) { errno = ENOMEM; return (void *)-1; } mem_brk += incr; return (void *)old_brk; // 늘리기 전 brk를 반환 } 진짜 sbrk 와 같은 인터페이스 늘리기 전의 brk를 반환 함. 이 값이 새로 얻은 영역의 시작 주소라서 extend_heap 에서 bp 가 됨. 진짜 sbrk 와 다른 점은 힙 축소(음수 incr)를 거부 한다는 것임. free(ptr) 에는 malloc 이 반환한 포인터를 넘겨야 함. mm_free 는 bp-4 를 헤더로 보고 접근하기 때문에, 잘못된 포인터를 넘기면 엉뚱한 값을 읽어 힙이 깨질 수 있음. 3. 상수와 매크로 #define WSIZE 4 // 워드 = 헤더/푸터 크기 #define DSIZE 8 // 더블워드 = 정렬 단위 #define CHUNKSIZE (1<<12) // 힙 확장 기본 단위 (4096B) #define MAX(x, y) ((x) > (y) ? (x) : (y)) 값 만들기/읽기/쓰기 매크로 의미 PACK(size, alloc) 크기와 할당 비트를 OR해서 헤더 값을 만듦 GET(p) 주소 p 의 4바이트 읽기 PUT(p, val) 주소 p 에 4바이트 쓰기 GET_SIZE(p) GET(p) & ~0x7 → 하위 3비트를 지워서 크기만 가져옴 GET_ALLOC(p) GET(p) & 0x1 → 마지막 한 비트만 가져옴 GET / PUT 은 p 가 보통 void * 라서 역참조가 안 됨. 그래서 unsigned int * (4바이트)로 캐스팅해서 읽고 씀. 헤더/푸터가 1워드라서 4바이트 단위임. PACK 은 하위 3비트가 비어 있어서 OR만 해도 정보가 섞이지 않음. PACK(24, 1) = 0x19 , 에필로그는 PACK(0, 1) 임. 헤더 값이 33이면 이렇게 풀림. 33 = 0010 0001 GET_SIZE → 32 (하위 3비트를 지움) GET_ALLOC → 1 (사용 중) bp 로 주소 찾기 bp-4 bp bp+size-8 bp+size ↓ ↓ ↓ ↓ [ 헤더 ][ payload ................ ][ 푸터 ][ 다음 블록 헤더 ] HDRP payload 바로 앞이 헤더임. HDRP(bp) = bp - 4 FTRP 푸터 위치를 구하려면 블록 전체 크기를 알아야 해서 헤더를 읽음. FTRP(bp) = bp + GET_SIZE(HDRP(bp)) - DSIZE 숫자 예시로 보면 이렇게 됨. 주소: 100 104 120 124 [ H ][ ........ payload 16B ........ ][ F ] ↑ bp 블록 크기 24 → bp + size = 104 + 24 = 128 (다음 블록의 bp) 128 - 8 = 120 → 푸터 시작 bp + size 는 다음 블록의 bp 위치임. 여기서 8을 빼면 현재 블록의 푸터 위치가 나옴. bp가 현재 블록의 payload 시작점이라서, 블록의 시작점까지 4B, 푸터까지 4B를 빼는 것임. NEXT_BLKP 블록 전체 크기만큼 이동하면 다음 블록의 bp가 됨. bp-4 bp bp+size-4 bp+size ↓ ↓ ↓ ↓ [ 헤더 ][ payload ......... ][ 푸터 ][ 다음 헤더 ][ 다음 payload ... ↑ NEXT_BLKP(bp) = bp + size NEXT_BLKP(bp) = bp + GET_SIZE(bp - WSIZE) 헤더의 크기를 따라가는 이 동작이 묵시적 리스트 순회 의 핵심! PREV_BLKP 현재 블록의 바로 앞에는 이전 블록의 푸터가 있음. 이전 블록 현재 블록 ┌────────────────────────┐ ┌────────────────────┐ │ H │ payload │ F(20) │ │ H │ payload │ F │ └────────────────────────┘ └────────────────────┘ ↑ ↑ ↑ bp-8 bp-4 bp (이전 푸터) (현재 헤더) PREV_BLKP(bp) = bp - GET_SIZE(bp - DSIZE) 이전 블록의 푸터( bp-8 )에서 크기를 읽고, 그만큼 bp 에서 뒤로 이동하면 이전 블록의 bp 를 찾을 수 있음. 푸터가 없으면 힙을 처음부터 훑어야 함 코드를 읽을 때 주의할 점: 갱신 순서 FTRP(bp) 는 헤더에 적힌 크기 로 푸터 위치를 계산함. 그래서 place 와 coalesce 에서는 아래 순서가 중요함. 헤더를 새 크기로 먼저 바꾼 뒤 FTRP 를 부르면 → 새 크기 기준 위치 바꾸기 전에 부르면 → 옛 크기 기준 위치 순서가 틀리면 엉뚱한 주소를 덮어쓰게 됨. 4. mm_init : 초기 힙 구성 allocator가 처음 시작할 때 힙을 처음 만들어줌. mem_sbrk(4 * WSIZE) 로 16바이트 를 확보하고 이렇게 채움. 패딩(4B) - 프롤로그(헤더 4B, 푸터 4B) - 에필로그(헤더 4B) → 총 16B 오프셋: 0 4 8 12 [ 0 ][ 8/1 ] [ 8/1 ] [ 0/1 ] ↑ heap_listp 과정: 패딩 만들기 : 정렬을 위한 값 0을 씀. 프롤로그 헤더 생성 (크기 8, allocated) 프롤로그 푸터 생성 에필로그 헤더 생성 (크기 0, allocated) heap_listp 가 프롤로그 블록의 bp 를 가리키도록 +2*WSIZE 이동함. 이후 힙 순회의 출발점임. extend_heap 을 호출해서 첫 free block을 만듦. 패딩 4B + 프롤로그 헤더 4B = 8B라서 이후 블록들의 payload가 8의 배수 주소에 놓임. 5. extend_heap : 힙을 늘리고 free block 만들기 호출되는 경우 처음 allocator를 초기화할 때 ( mm_init ) malloc 할 공간이 없을 때 ( mm_malloc ) 코드 흐름 크기 맞추기 : words 가 홀수면 하나 올려서 짝수 워드(8의 배수 바이트) 로 만듦. 8바이트 정렬을 유지하려는 것임. mem_sbrk(size) : 힙의 끝을 size 만큼 늘리고, 새로 확보한 영역의 시작 주소 를 bp 로 받음. 새 블록의 헤더, 푸터 를 PACK(size, 0) 으로 씀. 새 블록 바로 뒤에 새 에필로그 를 만듦. coalesce(bp) 로 앞 블록이 비어 있으면 합침. 핵심: 왜 HDRP(bp) 가 맞나 확장 전: [ ... ][ 에필로그 ] 확장 후: [ ... ][ 에필로그 ][ 새 공간 ........ ] ↑ ↑ bp-4 bp (mem_sbrk가 반환한 옛 brk) mem_sbrk 가 반환한 bp 는 기존 에필로그 바로 뒤 임. 그래서 bp - 4 가 기존 에필로그 헤더 자리 이고, 거기에 새 free block의 헤더를 덮어씀. 기존 에필로그가 새 블록의 헤더가 되는 것임. 새로 확보한 영역의 맨 마지막 워드에 새 에필로그를 만듦. 확장 후 정리: [ ... ][ 헤더 | ...... free ...... | 푸터 ][ 새 에필로그 ] ↑ ↑ 옛 에필로그 자리 HDRP(NEXT_BLKP(bp)) 새 에필로그 위치는 이렇게 구함. PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); 방금 쓴 헤더의 크기를 이용해서 다음 블록의 bp 를 구하고, 그 헤더 자리가 새 에필로그가 됨. ex) 초기 힙이 [패딩(0~3)][프롤로그(4~11)][에필로그(12~15)] 일 때 extend_heap(1024) 를 호출하면: size = 4096 , mem_sbrk(4096) 이 16 을 반환하고 bp = 16 임. HDRP(bp) = 12 에 4096/0 을 씀 (옛 에필로그 자리). FTRP(bp) = 16 + 4096 - 8 = 4104 에 푸터를 씀. HDRP(NEXT_BLKP(bp)) = 4108 에 새 에필로그 0/1 을 씀. 왜 마지막에 coalesce 를 부르나 힙이 늘기 전에 마지막 블록이 free였다면 새 free block과 연속된 free 블록 이 생김. 확장 전: [P][A a][B f][E] 확장 후: [P][A a][B f][새로운 f][E] ← free 두 개가 붙음 coalesce: [P][A a][ B + 새 f ][E] ← 하나로 합침 초기화 때는 앞이 프롤로그(allocated)라서 합칠 게 없음. 6. mm_malloc : 블록 할당 흐름은 두 질문으로 요약됨. 몇 바이트 블록이 필요한가? 그 크기를 담는 빈 블록이 있는가? ex) malloc(20) │ ▼ asize 계산 │ ▼ find_fit() ↙ ↘ 찾음 못 찾음 │ │ ▼ ▼ place() extend_heap() │ │ ▼ ▼ bp 반환 place() │ ▼ bp 반환 (1) size와 asize size : 사용자가 요청한 데이터 크기 asize : allocator가 실제로 만들 블록 전체 크기 규칙) size 가 8 이하면 asize = 16 (최소 블록 크기) 그 외에는 size + 8 (헤더+푸터)을 8의 배수로 올림 요청 size 계산 asize 1 ~ 8 최소 블록 16 9 9+8=17 → 올림 24 20 20+8=28 → 올림 32 size == 0 이면 NULL 을 반환함. (2) find_fit : 맞는 빈 블록 찾기 asize 이상의 free block이 있는지 heap_listp 에서 시작해 힙을 훑음. 못 찾으면 NULL 을 반환하고, 그러면 힙을 확장함. 탐색 종료 조건 -> 에필로그(크기 0) 만나는 것. 배치 정책 (9.9.7) 정책 방식 장점 단점 first fit 처음부터 훑어 처음 맞는 블록 큰 블록이 뒤쪽에 남음 앞쪽에 작은 조각(splinter)이 쌓여 큰 요청의 탐색이 느려짐 next fit 직전 탐색이 끝난 곳부터 앞쪽에 조각이 많아도 빠를 수 있음 일부 연구에서 first fit보다 이용도가 나쁨 best fit 전부 훑어 가장 작게 맞는 블록 이용도가 대체로 가장 좋음 단순 리스트에서는 힙 전체 를 훑어야 함 이 구현은 first fit임. first fit은 의도해서 큰 블록을 뒤에 남기는 게 아니라, 앞쪽부터 쓰고 쪼개다 보니 생기는 부수 효과임. best fit의 단점은 나중에 나오는 분리 빈 리스트(9.9.14) 로 해결할 수 있음. 크기 클래스별로 리스트를 나눠서 전체를 훑지 않고도 best fit에 가까운 결과를 얻음. (3) place : 배치와 분할 찾은 블록이 필요한 것보다 클 때 선택지 1. 현재 블록 크기 - asize >= 최소 블록 크기(16) → 앞부분은 할당, 뒷부분은 새 free 블록으로 남김 (분할) 2. 아니면 → 통째로 사용 (남는 부분이 너무 작아서 블록을 못 만듦) 분할: [ 4048 free ] → [ 32 할당 ][ 4016 free ] 통째로 사용 : 단순하고 빠르지만 내부 단편화 가 생김. 분할 : 공간을 아끼지만 헤더/푸터를 하나 더 만들어야 함. 분할 기준이 16인 이유는 최소 블록 크기가 16이라 그보다 작은 나머지는 블록이 될 수 없기 때문임. (4) 못 찾으면 힙 확장 (9.9.9) extendsize = MAX(asize, CHUNKSIZE); 작은 요청마다 조금씩 sbrk 하면 비효율적이라 기본 4096바이트 씩 한 번에 늘림. 요청이 4096보다 크면(예: asize = 5008 ) 필요한 만큼 늘림. 책 본문은 "먼저 인접 빈 블록 연결을 시도하고, 안 되면 sbrk "라고 설명함. 이 구현은 free 마다 즉시 연결하므로 이미 최대한 합쳐져 있어서 바로 extend_heap 으로 감. 늘린 뒤에는 새 free block에 place 하고 bp 를 반환함. 이 흐름에서 place 는 각 경로에서 한 번씩만 호출됨. 7. mm_free 와 coalesce mm_free 블록의 alloc 비트를 1 → 0 으로 바꿈 (헤더와 푸터 둘 다) coalesce 를 호출해서 free 블록이 연속으로 붙어 있지 않게 해줌 연결 시점: 즉시 vs 지연 (9.9.10) 연결을 안 하면 거짓 단편화 가 생김. 실제로는 붙어 있는 빈 블록인데 별개 블록으로 취급해서 큰 공간으로 못 쓰게 됨. [3워드 빈 블록][3워드 빈 블록] → 각각 3워드로 관리 → 4워드 요청 시 사용 불가 합치면 [ 6워드 빈 블록 ] → 4워드 요청 가능 즉시 연결 지연 연결 시점 free 시점에 바로 병합 free 는 상태만 바꾸고, 나중에 malloc 이 빈 블록을 못 찾을 때 병합 장점 구현이 단순, 외부 단편화를 빠르게 줄임 불필요한 병합/분할을 줄임, free 가 빠름 단점 할당/해제를 반복하면 스래싱 (합쳤다가 바로 다시 쪼갬) 병합이 필요한 시점에 추가 작업 필요 교재의 코드 구현은 즉시 연결 을 사용 coalesce : 이웃의 상태로 네 가지 경우 prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // 이전 블록: 푸터로 확인 next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // 다음 블록: 헤더로 확인 Case [이전][현재][다음] 결과 1 [ a ] [ f ] [ a ] 합칠 것 없음 (현재만 free 표시) 2 [ a ] [ f ] [ f ] 현재 + 다음 합침 3 [ f ] [ f ] [ a ] 이전 + 현재 합침, bp 를 이전 블록으로 이동 4 [ f ] [ f ] [ f ] 셋 다 합침, bp 를 이전 블록으로 이동 합칠 때의 규칙: 합쳐진 덩어리의 맨 앞 헤더 와 맨 뒤 푸터 만 새 크기로 고침. 중간에 끼어 있던 옛 헤더/푸터는 지우지 않아도 되고, 그냥 내부 데이터로 남아서 무시됨. Case 4: [H 64][...][F 64] [H 32][...][F 32] [H 48][...][F 48] ↓ [H 144][........................................][F 144] ↑ 이전 블록의 헤더 다음 블록의 푸터 ↑ Case 합쳐진 블록의 헤더 합쳐진 블록의 푸터 2 현재 헤더 다음 블록의 푸터 3 이전 블록의 헤더 현재 푸터 4 이전 블록의 헤더 다음 블록의 푸터 Case 3, 4는 합쳐진 블록의 시작이 이전 블록으로 옮겨지므로