[SW 정글 42일차] malloc 구현하기 시작 (implicit + first-fit)

어제 저녁을 먹고 구현을 하기 시작했는데 다시 한번 코드를 처음부터 보면 왜 코드가 이렇게 나왔는지를 생각해봤다.

지금까지 공부한 것을 복습할 수 있는 좋은 시간이였고 궁금증을 계속가지면 더 깊이 있는 공부를 하려고 노력했다.

내가 구현한 동적 메모리 할당기는 explicit allocator이고 implicit available list를 사용했다.

coalesce를 위해서 선택한 검색 방법은 first-fit이다.first-fit은 할당받고자 할 때, 무조건 heap area의 처음부분부터 allocated되지 않은 영역을 찾는 것이다.

 

1. memlib.c 파헤치기

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <sys/mman.h>
#include <string.h>
#include <errno.h>

#include "memlib.h"
#include "config.h"

/* private variables */
static char *mem_start_brk;  /* points to first byte of heap */
static char *mem_brk;        /* points to last byte of heap */
static char *mem_max_addr;   /* largest legal heap address */ 

void mem_init(void)
{
    /* allocate the storage we will use to model the available VM */
    // heap의 최대 크기(MAX_HEAP)을 할당했을 때, 그 시작주소가 NULL이면 문제가 있는 것이므로 에러처리
    if ((mem_start_brk = (char *)malloc(MAX_HEAP)) == NULL) {
	fprintf(stderr, "mem_init_vm: malloc error\n");
	exit(1);
    }
    // heap의 마지막을 가리키는 mem_max_addr
    mem_max_addr = mem_start_brk + MAX_HEAP;  /* max legal heap address */
    mem_brk = mem_start_brk;                  /* heap is empty initially */
}

void *mem_sbrk(int incr) 
{
    // return을 위해 이전 mem_brk를 저장해둠.
    char *old_brk = mem_brk;

    if ( (incr < 0) || ((mem_brk + incr) > mem_max_addr)) {
	errno = ENOMEM;
	fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
	return (void *)-1;
    }
    mem_brk += incr;
    return (void *)old_brk;
}

내가 설계한 allocator가 기존의 시스템 수준의 malloc 패키지와 독립적으로 동작할 수 있도록 memlib.c 패키지에서 제공되는 메모리 시스템의 모델을 사용한다.

위 코드를 분석한 것은 아래와 같다.

 

 

 

2. mm.c 파헤치기

mm파일이 우리가 수정하여 malloc을 구현하는 것이다.

먼저, 코드 전체에서 사용할 상수와 매크로를 정의한다.

매크로란 코드에서 반복적으로 선언(사용)되는 숫자나 함수를 미리 정의하여 의미가 서로 다른 것이 섞여서 사용되면 각각의 의미가 헷갈리기때문에 그 부분을 방지해준다.
또한, 코드가 길어지고 복잡해졌을 때 코드 입력 실수를 줄일 수 있다.

#define은 컴파일 직전에 처리되므로 전처리기 과정을 거치면 매크로가 정의된다.
보통 전처리기는 반복되는 값이나 작업을 미리 정의할 때 사용하며 컴파일 옵션 설정이나 조건부 컴파일도 가능하다.

- 매크로 선언
#define 매크로명 매크로하고자하는대상
- 기존에 선언된 매크로의 이름을 재정의
#define 새 매크로명 기존 매크로명
- 매크로 해제
#undef 매크로이름

 

- 매크로 정의 코드

// sigle word 사이즈 지정(4bytes)
#define WSIZE 4
// double word 사이즈 지정(8bytes)
#define DSIZE 8
// 초기가용블록과 힙 확장을 위한 chuncksize
#define CHUNKSIZE (1 << 12)

 
#define MAX(x, y) ((x) > (y) ? (x) : (y))
// 블록의 size와 할당여부를 알려주는 alloc bit를 합쳐 header와 footer에 담을 수 있도록 반환
#define PACK(size, alloc)    ((size) | (alloc))
// pointer p를 역참조하여 값을 가져옴
// p는 대부분 void( *)일 것이고 void형 pointer는 직접적으로 역참조가 안되므로 형변환을 함.
#define GET(p)               (*(unsigned int *)(p))
// pointer p를 역참조하여 val로 값을 바꿈
#define PUT(p, val)          (*(unsigned int *)(p) = (val))
// pointer p에 접근하여 블록의 size를 반환
#define GET_SIZE(p)          (GET(p) & ~(0x7))
// pointer p에 접근하여 블록의 할당bit를 반환
#define GET_ALLOC(p)         (GET(p) & 0x1)

// block pointer p를 주면 해당 block의 header를 가리키는 pointer 반환
#define HDRP(bp)             ((char *)(bp) - WSIZE)
// block pointer p를 주면 해당 block의 footer를 가리키는 pointer 반환
#define FTRP(bp)             ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
// block pointer p의 다음 블록의 위치를 가리키는 pointer 반환
#define NEXT_BLKP(bp)        ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
// block pointer p의 이전 블록의 위치를 가리키는 pointer 반환
#define PREV_BLKP(bp)        ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

 

- mm_init 함수 정의

mm_init함수는 메모리 시스템에서 4word를 가져와서 비어있는 가용 리스트를 만들고 extend_heap()함수를 통해 CHUNCKSIZE 바이트로 확장하고 초기 가용 블록을 생성해주는 역할을 한다.

// heap에서 edge condition을 없애주기 위해 초기화 작업 진행
int mm_init(void)
{   
    // 4word가 필요하므로 heap 전체 영역이 4워드 미만이면 안됨
    if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
        return -1;

    PUT(heap_listp, 0); // alignment padding
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); // prologue header
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); // prologue footer
    PUT(heap_listp + (3*WSIZE), PACK(0, 1)); // epliogue header
    heap_listp += (2*WSIZE);
    
    if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
        return -1;
    return 0;
}

 

- extend_heap 함수 정의

extend_heap()은 힙이 초기화 될 때와 mm_malloc이 적당한 맞춤fit을 찾지 못했을 때 alignment를 유지하기 위한 역할을 한다.

static void *extend_heap(size_t words)
{
    size_t size;
    // 가용 리스트의 크기를 8의 배수로 맞추기 위한 작업
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    // mem_sbrk함수를 이용하여 늘렸을 때, 늘어날 수 없다면 return NULL
    if ((long)(bp = mem_sbrk(size)) == -1)
        return NULL;
    // header와 footer 업데이트
    PUT(HDRP(bp), PACK(size, 0)); // header에 size와 할당비트 업데이트
    PUT(FTRP(bp), PACK(size, 0)); // footer에 size와 할당비트 업데이트
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // 새로운 epilogue header생성

    return coalesce(bp);
}

 

- mm_free 함수 정의

할당받았던 block을 free시켜주는 역할을 한다.

void mm_free(void *bp) {
    size_t size = GET_SIZE(HDRP(bp));
    PUT(HDRP(bp), PACK(size, 0)); 
    PUT(FTRP(bp), PACK(size, 0)); 
    coalesce(bp); 
}

 

- coalesce 함수 정의

free된 영역을 합쳐주는 역할을 한다.

static void *coalesce(void *bp)
{
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));
    // 앞 뒤 블록 둘 다 allocated일 경우
    if (prev_alloc && next_alloc) {
        return bp;
    }
    // 뒤 블록만 free일 경우
    else if (prev_alloc && !next_alloc) {
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }
    //앞 블록만 free일 경우
    else if (!prev_alloc && next_alloc) {
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    // 앞 뒤 블록 둘 다 free일 경우
    else {
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    return bp;
}

 

- mm_malloc 함수 정의

인자로 size를 받으면 그 size에 적합한 메모리를 할당해주는 역할을 하는 것이다.

현재 free된 메모리 영역에 들어가지 못하는 size를 인자로 넣었다면 메모리 시스템에게 extend_heap()을 요청한다.

free된 메모리 영역에 적합한 사이즈라면 2가지 경우가 나뉜다.

첫 번째는 8바이트보다 작은 size로 인자가 들어오면 header와 footer 8바이트를 포함하여 총 16바이트(2*DSIZE)를 할당해주면 된다.

두 번째는 8바이트보다 큰 size가 들어온다면 alignment constraints를 맞추기 위해 하나의 수식을 이용한다.

DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
// 맨 앞 DSIZE: alignment constraints에 의해 8의 배수만큼 할당받아야 하므로 곱해주는 것임
// size: 할당받고자 하는 size
// DSIZE: header와 footer 8bytes
// (DSIZE - 1): 계산을 하면 7인데 왜 7을 더하냐면 예를 들어, 23(size + header + footer)byte라면
// 24byte를 할당받아야하므로 우리가 DSIZE를 나누면 몫으로 3이 나와야한다.
// 그래서 7을 더해서 30으로 만들어주고 몫만 필요하므로 나머지는 신경쓰지 않는 것이다.
// 핵심은 몫을 구하기 위해 dummy값을 더하고 나머지는 신경쓰지 않아도 된다는 것.

 전체 코드는 아래와 같다.

void *mm_malloc(size_t size)
{
    size_t asize;
    size_t extendsize;
    char *bp;
    if (size == 0)
        return NULL;
    if (size <= DSIZE)
        asize = 2*DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
    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;
}

 

- place와 find-fit 함수 정의

place함수는 mm_malloc에서 할당이 가능한 size라고 판단이 내려지면 실제로 메모리를 할당받고 값을 업데이트시키는 역할을 한다.

find-fit은 size에 맞는 적합한 free 영역을 찾는다.

찾는 방식은 first-fit 방식이다.

static void place(void *bp, size_t asize) {
    size_t csize = GET_SIZE(HDRP(bp));
    if((csize - asize) >= (2 * DSIZE)) {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize - asize, 0));
        PUT(FTRP(bp), PACK(csize - asize, 0));
    }
    else {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

// first-fit
static void *find_fit(size_t asize)
{
    void *bp;
    for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            return bp;
        }
    }
    return NULL;
}

 

- mm_realloc 함수 정의

mm_relloc 함수는 malloc으로 할당 받은 메모리 영역을 size를 변경하여 재할당받는 역할을 한다.

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 = GET_SIZE(HDRP(oldptr));
    /* copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE); */
    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

 

---

[오늘의 나는 어땠을까?]

오늘도 2주에 한번 씩 부모님이 오시는 주여서 점심 때는 부모님과 함께 식사를 했다.

점심을 먹은 뒤, 부모님이 샤인머스켓을 사주셔서 휴게실에 있는 냉장고에 넣고 동료들에게 먹고싶은 사람에게 먹으라고 알려주었고 양이 얼마안되지만 먹은 동료들은 만족을 해서 기분이 좋았다.

 

저녁을 먹은 뒤에는 정글에 들어와서 처음으로 운동이라는 것을 했다.

정글에 들어오기 전에는 꾸준히 운동을 해왔는데 정글에서는 운동할 시간을 따로 내기가 힘들어 운동이라는 것은 걷기 뿐이였다.

오랜만에 땀을 운동을 하니 기분도 더 좋아지는 것같고 스트레스도 풀리는 느낌이였다.

하지만, 확실히 시간을 많이 잡아먹기도 하고 공부에 몰두해야하고 이제 얼마 안남은 정글생활에서 내가 얻고자 하는 것들을 위해서라면 운동은 잠시 접어야겠다는 생각이 든다.

그래도 건강은 언제나 유념하면서 지내고