동적 메모리 할당: 묵시적(implicit) 가용 리스트

서론

동적 메모리 할당을 할 때 가용 리스트를 구성하는 방법에는 묵시적 가용 리스트(implicit), 명시적 가용 리스트(explicit), 분리 가용 리스트(segregated), 버디 시스템(buddy system) 등이 있습니다. 본문에서는 이 중 묵시적 가용 리스트(implicit)를 사용한 동적 메모리 할당을 설명합니다.

---

implicit에서 블록의 구성

블록엔 데이터(+패딩) 앞 뒤에 헤더와 푸터가 있다. 헤더와 푸터는 같은 값으로 안에는 블록의 크기(헤더와 푸터를 포함한)와 할당 정보가 들어있다.

🤔 푸터(footer)는 왜 있어야 할까?
푸터는 경계 태그(boundary tag)로 이전의 헤더 블록을 찾기 위해서 존재한다. 푸터가 없다면 헤더를 통해 할당 정보를 확인해야 하는데, 거꾸로 훑고 가면 헤더가 헤더인지 알 수가 없고 앞에서부터 훑으면 가용블록에 비례하게 된다. 푸터가 있으면 이전의 헤더 블록을 찾기 위해 상수 시간만큼만 가면 된다.

정의 & 선언

#define WSIZE 4             
#define DSIZE 8             
#define CHUNKSIZE (1 << 12) 

• 워드 사이즈(바이트 기준). 32비트 아키텍처에서 데이터를 처리할 때 더 쉽고 효율적으로 처리하기 위해서 4바이트를 워드 사이즈로 정의한다.
• 더블 워드 사이즈(바이트 기준)
• 힙을 확장할 때 기준으로 사용한다. 컴퓨터 시스템에서 일반적으로 사용되는 페이지 크기인 4KB를 사용한다.

#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define PACK(size, alloc) ((size) | (alloc))

• x와 y 중 최댓값을 찾는 함수
• 사이즈(8의 배수이기 때문에 하위 3비트는 0이므로 할당 비트와 or 연산 시 할당 비트를 따라감)와 할당 비트를 워드로 만들어주는 함수

#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))

• p에 있는 데이터를 읽고 쓰는 함수

#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)

• p에 있는 사이즈 정보를 읽는 함수. ~0x7 = 0xFFFFFFF8 = 하위 3비트를 제외한 비트들이 모두 1인 값. & 연산을 하면 8이하의 값은 나올 수 없다.
• p에 있는 할당 정보를 읽는 함수. 하위 1비트를 추출하여 해당 값이 0이면 할당되어 있지 않은 상태이고, 1이면 할당되어 있는 상태이다.

#define HDRP(bp) ((char *)(bp)-WSIZE)                        
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) 

• payload 시작주소에서 1워드 돌아간다. 즉, header의 시작주소
• payload 시작주소에서 (블록의 크기-2워드)를 더한다. 즉, footer의 시작주소

#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp)-WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp)-GET_SIZE(((char *)(bp)-DSIZE))) 

• 다음 블록의 payload 시작주소
• 이전 블록의 payload 시작주소

static char *heap_listp;

• 힙의 시작을 알려줄 변수

---

함수

int mm_init(void): 빈 초기 힙을 만드는 함수

int mm_init(void)
{
    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
        return -1;
    PUT(heap_listp, 0);                            
    PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); 
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); 
    PUT(heap_listp + (3 * WSIZE), PACK(0, 1));     
    heap_listp += (2 * WSIZE);                     
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;
    return 0;
}

• 만약 메모리 할당 오류가 발생했으면 -1 리턴
• 미사용 패딩, 프롤로그 헤더, 프롤로그 푸터, 에필로그 헤더 추가
• Prologue 헤더만큼을 건너뛴다. payload를 변수로 사용하기 때문이다.
• 힙을 확장하는데 확장할 수 없을 경우 -1 리턴

static void *extend_heap(size_t words): 힙의 크기를 조정하는 함수

해당 함수는 두 가지 경우에 호출된다.
1. 힙이 초기화될 때
2. mm_malloc이 적당한 맞춤 fit을 찾지 못했을 때

static void *extend_heap(size_t words) /* 워드 단위 */
{
    char *bp;
    size_t size;

    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; 
    if ((long)(bp = mem_sbrk(size)) == -1)                    
        return NULL;

    PUT(HDRP(bp), PACK(size, 0));         
    PUT(FTRP(bp), PACK(size, 0));         
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); 

    return coalesce(bp);
}

🤔 프롤로그 & 에필로그 블록은 왜 있는걸까?
가장자리 조건을 없애주기 위한 속임수이다. 여기서 가장자리 조건(edge condition)이란 프로그램이 주어진 입력에 대해 예상된 동작을 수행하기 위해 필요한 경계 조건이다.

• 더블 워드 정렬 조건에 맞추기 위해서 데이터 크기 words가 홀수이면 짝수로 만들어 준다.(padding)
• 사이즈를 해당 크기만큼 늘릴 수 없으면 NULL 반환
• 가용 블록 헤더 초기화
• 가용 블록 푸터 초기화
• 새로운 에필로그 헤더 초기화
• 주변의 가용 블록과 연결(있다면)

static void coalesce(void bp): 블록을 연결하는 함수

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));             

    if (prev_alloc && next_alloc)
    {
        return bp;
    }
    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));
    }
    else if (!prev_alloc && next_alloc)
    {
        size += GET_SIZE(HDRP(PREV_BLKP(bp))); 
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    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;
}

• prev_alloc: bp 이전 블록의 푸터에서 가져온 할당 정보
• next_alloc: bp 다음 블록의 헤더에서 가져온 할당 정보
• size: 현재 블록의 사이즈
• Case 1. 앞, 뒤 모두 할당되어 있을 때
  현재 블록의 payload를 가리키는 포인터 반환
• Case 2. 앞은 할당되어 있고, 뒤는 가용블록일 때
  size: 현재 블록의 크기에 다음 블록의 크기를 더한 크기
• Case 3. 앞은 가용블록이고, 뒤는 할당되어 있을 때
  size: 현재 블록의 크기에 이전 블록의 크기를 더한 크기
• Case 4. 앞, 뒤 모두 가용블록일 때
  size: 현재 블록의 크기에 앞, 뒤 블록의 크기를 더한 크기

void *mm_malloc(size_t size): 가용 블록을 할당하는 함수

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);

    /* Search the free list for a fit */
    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;
}

• asize: 조정된 블록 크기
• extendsize: 크기가 맞는 가용 블록이 없으면 확장할 크기
• 사이즈가 0인 의미없는 요청이 들어올 경우, NULL 리턴
• 헤더, 푸터 오버헤드와 정렬 조건에 맞춰 블록 크기 조정하기
  만약 DSIZE보다 작다면 16바이트로 맞춘다. 왜 16바이트? 정렬조건인 더블 워드를 충족하기 위한 8바이트, 헤더와 푸터 오버헤드를 위한 8바이트.
  DSIZE보다 크다면 오버헤드 추가 후, 8의 배수로 맞춰준다.
• 만약 할당하고 싶은 크기 이상의 가용블록이 있을 경우, 배치 후 bp 리턴
• 없을 경우 힙 확장하기
  만약 확장할 수 없을 경우 NULL 리턴, 할 수 있을 경우 bp리턴

static void *find_fit(size_t asize): 원하는 크기 이상의 가용 블록을 찾는 함수(first-fit 사용)

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

• 힙의 시작부터 / 크기가 > 0일때동안, 즉 에필로그 헤더가 나오기 전까지 / 다음 블록으로 이동하면서 for 루프를 돈다.
• 만약 할당이 안 되어 있고 할당하고자 하는 크기보다 블록의 크기가 크다면 bp 리턴, 아니면 NULL 리턴

static void place(void *bp, size_t asize): 가용 블록을 배치하는 함수

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));
    }
}

• csize: 가용 블록의 크기
• 할당하고 남은 가용 블록의 크기가 2*DSIZE 이상이면 분할의 가치가 있으므로 분할하고, 아니면 전부 사용한다.(이때 패딩 생길 수 있다.)

void mm_free(void *ptr): 할당된 블록을 해제해서 가용 블록으로 만드는 함수

void mm_free(void *ptr)
{
    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): 재할당하는 함수

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)) - DSIZE; /* 기존에 할당된 블록의 사이즈. */
    if (size < copySize)
        copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

• 파라미터로 받은 크기만큼 메모리를 할당한다.
• 만약에 할당되지 않으면 NULL을 리턴한다.
• 기존에 할당된 블록의 크기가 받은 크기보다 크면 받은 크기로 만들어 준다.
• 받은 크기만큼의 메모리에 있던 내용을 복사한다.
• 이전에 할당된 메모리를 해제한다.

참고자료

• <Computer Systems: A Programmers Perspective> Section 9.9 - Randal Bryant

* 전체 코드는 여기서 확인하실 수 있습니다.