[CS/시스템 프로그래밍] malloc lab 온몸 비틀기 1편: 헤더 4바이트를 아끼려다 생긴 일

About this offer

교재 코드를 그대로 넣었을 때 56점이었던 malloc을 84점까지 올린 과정이다. 그런데 이 1편에서 제일 중요한 건 점수가 아니라, footer를 없애는 "최적화"를 했는데 점수가 그대로였던 일 이다. 그 실패 덕분에 트레이스를 한 줄씩 열어보기 시작했다. 점수는 어떻게 매겨지나 기본 코드 /* * mm-naive.c - The fastest, least memory-efficient malloc package. * * In this naive approach, a block is allocated by simply incrementing * the brk pointer. A block is pure payload. There are no headers or * footers. Blocks are never coalesced or reused. Realloc is * implemented directly using mm_malloc and mm_free. * * NOTE TO STUDENTS: Replace this header comment with your own header * comment that gives a high level description of your solution. */ #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <unistd.h> #include <string.h> #include "mm.h" #include "memlib.h" /********************************************************* * NOTE TO STUDENTS: Before you do anything else, please * provide your team information in the following struct. ********************************************************/ team_t team = { /* Team name */ "ateam", /* First member's full name */ "Harry Bovik", /* First member's email address */ "bovik@cs.cmu.edu", /* Second member's full name (leave blank if none) */ "", /* Second member's email address (leave blank if none) */ ""}; /* single word (4) or double word (8) alignment */ #define ALIGNMENT 8 /* rounds up to the nearest multiple of ALIGNMENT */ #define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7) #define SIZE_T_SIZE (ALIGN(sizeof(size_t))) /* * mm_init - initialize the malloc package. */ int mm_init(void) { return 0; } /* * mm_malloc - Allocate a block by incrementing the brk pointer. * Always allocate a block whose size is a multiple of the alignment. */ void *mm_malloc(size_t size) { int newsize = ALIGN(size + SIZE_T_SIZE); void *p = mem_sbrk(newsize); if (p == (void *)-1) return NULL; else { *(size_t *)p = size; return (void *)((char *)p + SIZE_T_SIZE); } } /* * mm_free - Freeing a block does nothing. */ void mm_free(void *ptr) { } /* * mm_realloc - Implemented simply in terms of mm_malloc and mm_free */ void *mm_realloc(void *ptr, size_t size) { void *oldptr = ptr; void *newptr; size_t copySize; newptr = mm_malloc(size); if (newptr == NULL) return NULL; copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE); if (size < copySize) copySize = size; memcpy(newptr, oldptr, copySize); mm_free(oldptr); return newptr; } malloc lab은 mm_malloc , mm_free , mm_realloc 을 직접 구현하고, mdriver 가 트레이스 파일 11개를 돌려서 점수를 매긴다. 트레이스 한 줄이 요청 하나다. a 0 2040 ← malloc(2040), id 0 f 0 ← free(id 0) r 0 4097 ← realloc(id 0, 4097) 점수는 두 개로 나뉜다. util (60점) : 살아 있는 데이터가 가장 많았을 때의 크기 ÷ 힙이 가장 컸을 때의 크기. 트레이스 11개의 평균. thru (40점) : 초당 처리한 요청 수(Kops). 600 Kops를 넘으면 만점. 점수 = 60 × util + 40 × min(1, Kops / 600) 즉 이 lab에서는 처리 속도보다 메모리를 효율적으로 쓰는 게 중요하다. 속도는 600 Kops만 넘기면 만점이라, 그다음부터는 메모리를 얼마나 알뜰하게 쓰느냐가 점수를 가른다. 측정 환경: x86-64 / gcc 13.3.0 / make 기본 -O2 0. 교재 코드: 복붙하지 않고 다시 쓰기 CS:APP 9.9절에는 implicit free list로 만든 할당기 코드가 통째로 나온다. 헤더와 footer로 블록을 관리하고, first fit으로 빈 블록을 찾고, free할 때 바로 앞뒤 블록과 합친다. 그런데 나는 이 코드를 그래도 복붙하지 않고 교재 코드를 충분히 이해한 뒤 최대한 보지 않고 직접 짜봤다. 이 lab은 결국 PACK , GET , PUT , HDRP , FTRP , NEXT_BLKP , PREV_BLKP 같은 매크로로 메모리를 4바이트씩 직접 읽고 쓰는 게 전부다. 이게 손에 안 익으면 직접 코드를 짤 때 많이 해맬 것 같아서 설계가 되어있는 교재 코드를 어차피 옮겨 쓰고 시작해볼 걸 그냥 직접 옮겨보자 싶었다. 그래서 순서를 이렇게 잡았다. 교재 코드를 읽으면서 각 함수가 뭘 하는지, 매크로가 어떤 주소를 계산하는지 이해한다. 매크로만 정의해두고 교재를 덮는다. 함수 몸통은 교재를 최대한 안 보고 직접 채운다. 이렇게 하니까 "bp에서 4바이트 앞이 헤더", "헤더에 적힌 크기만큼 가면 다음 블록", "앞 블록은 내 바로 앞 8바이트 자리의 footer를 읽어서 찾는다" 같은 블록 단위 계산이 손에 익어서 다음 최적화들을 할 때 훨신 수월했던 것 같다. 대신 first fit을 구현할 때 빼먹거나 다르게 쓴 게 좀 있어서 에러가 좀 나긴 했다... 1. first fit: 내가 빼먹었던 것들 처음 채운 핵심 두 함수는 이랬다. 지금 보니까 엄청 간단하게 아무생각 없이 쓴 거 같다. 디버깅을 하지 않아도 되는 코드를 짜는 게 중요한데 다음부터는 처음 짤 때부터 꼼꼼하게 설계하고 코드를 짜야할 것 같다. 단계마다 실제로 짰던 코드를 그대로 보여주고, 왜 터졌는지 적어보겠다. 헛다리 1: 블록을 아예 안 자르기 처음엔 split_block 같은 건 없었다. find_fit 이 블록을 찾으면 place 가 헤더와 footer에 요청 크기를 쓰는 게 전부였다. static void *find_fit(size_t asize) { ... if(GET_SIZE(HDRP(current)) == asize && !GET_ALLOC(HDRP(current))){ return current; // 크기가 "딱 맞는" 블록만 찾음 } ... } static void place(void *bp, size_t asize) { PUT(HDRP(bp), PACK(asize, 1)); // 요청 크기만 쓰고 끝 PUT(FTRP(bp), PACK(asize, 1)); } find_fit 은 딱 맞는 블록이 없으면 NULL 을 돌려주고, 그러면 extend_heap 으로 힙을 늘린 다음 그 블록에 place 를 한다. 문제는 늘린 블록이 요청보다 훨씬 크다는 거다. 그런데 place 는 앞부분에 요청 크기만 써버린다. 돌리자마자 segfault가 났다. gdb로 잡아보면 extend_heap 이 부른 coalesce 안에서 터진다. Program received signal SIGSEGV, Segmentation fault. 0x0000555555556f73 in coalesce (bp=0x7ffff68d2020) at mm.c:167 167 size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); #1 extend_heap (words=1024) at mm.c:112 #2 mm_malloc (size=4080) at mm.c:142 (gdb) p/x *(unsigned int*)((char*)bp - 8) ← 앞 블록 footer 자리 $1 = 0x1ff0 새로 늘린 청크( bp )의 바로 앞 4바이트는 원래 앞 블록의 footer여야 한다. 그런데 거기서 읽은 값으로 PREV_BLKP 를 계산하니까 엉뚱한 곳으로 가서 터진 거다. 왜 footer가 망가졌는지 보려고 malloc(2040) 한 번만 부르고 힙을 직접 읽어봤다. a header: size=2048 alloc=1 NEXT_BLKP(a) header: 0x0 (size=0 alloc=0) heap size = 8208 malloc(2040) 은 블록 크기 2048이 필요하다. mm_init이 만든 free 블록은 4096이라 "딱 맞는" 게 아니니까 find_fit 이 못 찾는다. 그래서 힙을 4096 늘리고, 그게 앞의 4096이랑 합쳐져서 8192짜리 블록이 된다. 그런데 place 가 앞에 2048이라고만 써버려서, 뒤 6144바이트는 헤더도 footer도 없는 공간 이 됐다. 그 자리 첫 4바이트가 0이라서 힙 순회 입장에서는 "크기 0 = 에필로그"처럼 보이고, 힙이 거기서 끝난 것처럼 된다. 이런 블록들이 쌓이다가 결국 쓰레기 footer를 읽은 거다. 여기서 처음으로 "블록 경계는 헤더랑 footer에 쓴 숫자가 전부"라는 게 실감 났다. 크기를 안 써주면 그 공간은 존재하지 않는 거나 마찬가지다. 헛다리 2: 자르긴 하는데, 늘린 블록만 남는 부분에도 헤더와 footer를 써줘야 한다는 걸 알고 split_block 을 만들었다. 처음 버전은 이랬다. static void *split_block(void *bp, size_t size){ size_t total = GET_SIZE(HDRP(bp)); // if(total <= 24){ // return bp; // } PUT(HDRP(bp), PACK(size, 0)); // 앞: 요청 크기 PUT(FTRP(bp), PACK(size, 0)); PUT(HDRP(NEXT_BLKP(bp)), PACK(total-size, 0)); // 뒤: 남는 크기 PUT(FTRP(NEXT_BLKP(bp)), PACK(total-size, 0)); return bp; } 그리고 이걸 extend_heap 으로 늘린 경우에만 불렀다. " find_fit 은 어차피 딱 맞는 블록만 찾으니까 자를 필요가 없고, 늘린 블록만 크니까 그것만 자르면 되겠지"라고 생각했다. else{ extend = MAX(size, CHUNKSIZE); if((bp = extend_heap(extend / WSIZE)) == NULL){ return NULL; } if(GET_SIZE(HDRP(bp)) != extend){ // 앞 free랑 합쳐져서 커졌으면 bp = split_block(bp, size); // 그때만 자른다 } place(bp, size); return bp; } segfault는 사라졌는데 이번엔 메모리가 바닥났다. ERROR: mem_sbrk failed. Ran out of memory... ERROR [trace 4, line 7671]: mm_malloc failed. split_block 으로 잘라낸 뒷부분은 이제 제대로 된 free 블록이다. 그런데 find_fit 이 여전히 크기가 딱 맞는 블록만 찾고 있었다. 예를 들어 첫 malloc(2040) 뒤에는 6144짜리 free 블록이 생기는데, 다음 요청이 그보다 작아도 크기가 딱 6144가 아니면 거기 못 들어간다. 그러니까 요청이 올 때마다 힙을 새로 늘렸고, 결국 바닥났다. 헛다리 3: 남는 게 0바이트여도 자르기 find_fit 을 >= 로 바꾸고, 찾은 블록이든 늘린 블록이든 항상 split_block 을 부르게 바꿨다. 그런데 이번엔 위 split_block 에서 주석 처리해둔 조건이 문제가 됐다. 블록 크기가 요청이랑 딱 같으면 total - size 가 0이다. 그러면 split_block 은 다음 블록 자리에 크기 0짜리 헤더를 쓴다. 크기 0이면 에필로그랑 구분이 안 된다. 게다가 FTRP(NEXT_BLKP(bp)) 는 "다음 블록 + 0 − 8"이라 자기 자신의 footer 자리 를 가리킨다. 방금 쓴 footer를 0으로 덮어써버리는 거다. 그래서 남는 크기가 최소 블록(헤더 4 + footer 4 + 최소 payload 8 = 16바이트)보다 작으면 자르지 않는 조건을 넣었다. 그리고 안 잘린 블록이 들어오면 place 가 블록 전체 크기를 쓰게 바꿨다. 최종 코드 교재코드 + first fit /* * mm-naive.c - The fastest, least memory-efficient malloc package. * * In this naive approach, a block is allocated by simply incrementing * the brk pointer. A block is pure payload. There are no headers or * footers. Blocks are never coalesced or reused. Realloc is * implemented directly using mm_malloc and mm_free. * * NOTE TO STUDENTS: Replace this header comment with your own header * comment that gives a high level description of your solution. */ #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <unistd.h> #include <string.h> #include "mm.h" #include "memlib.h" /********************************************************* * NOTE TO STUDENTS: Before you do anything else, please * provide your team information in the following struct. ********************************************************/ team_t team = { /* Team name */ "Team 10", /* First member's full name */ "Shin Ye Na", /* First member's email address */ "syn77@pusan.ac.kr", /* Second member's full name (leave blank if none) */ "", /* Second member's email address (leave blank if none) */ ""}; /* single word (4) or double word (8) alignment */ #define ALIGNMENT 8 #define WSIZE 4 #define DSIZE 8 #define CHUNKSIZE (1<<12) // 페이지 단위 할당 #define MAX(x, y) ((x) > (y) ? (x) : (y)) #define PACK(size, alloc) ((size) | (alloc)) #define GET(p) (*(unsigned int *)(p)) // int로 읽기 #define PUT(p, val) (*(unsigned int *)(p) = (val)) #define GET_SIZE(p) (GET(p) & ~0x7) #define GET_ALLOC(p) (GET(p) & 0x1) #define HDRP(bp) ((char *)(bp) - WSIZE) #define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) #define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp))) #define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE)) /* rounds up to the nearest multiple of ALIGNMENT */ #define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7) // 정렬의 배수로 올림 (~0x7로 지움 구현) #define SIZE_T_SIZE (ALIGN(sizeof(size_t))) // size_t를 올림 -> 여기서는 8바이트 즉, 푸터와 헤더 8바이트를 더해서 배수 구함 static void *extend_heap(size_t words); // 함수 프로토타입 선언 static void *coalesce(void *bp); static void *find_fit(size_t asize); static void place(void *bp, size_t asize); static void *split_block(void *bp, size_t size); static char *heap_listp; // 전역변수로 포인터 선언 /* * mm_init - initialize the malloc package. */ int mm_init(void) { if((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1){ return -1; } PUT(heap_listp, 0); PUT(heap_listp + 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 += 4 *WSIZE; // 첫 청크부터 시작하는 작은 최적화(처음에는 heap의 끝을 가르킴 ) if(extend_heap(CHUNKSIZE / WSIZE) == NULL){ // heap 공간 확보 return -1; } return 0; // 정상종료 } static void *extend_heap(size_t words) { size_t size; char *bp; size = (words%2) ? (words+1) * WSIZE : words * WSIZE; if((bp = mem_sbrk(size)) == (void *)-1){ return NULL; } PUT((char *)bp - WSIZE, PACK(size, 0)); // new chunk header PUT(FTRP(bp), PACK(size, 0)); // newe chunk footer PUT(HDRP(NEXT_BLKP(bp)), PACK(0,1)); // epilogue return coalesce(bp); } /* * mm_malloc - Allocate a block by incrementing the brk pointer. * Always allocate a block whose