[WEEK 06] C - MALLOC LAB

할당기 기본 설계

memlib.c 패키지에서 제공되는 메모리 시스템의 모델을 사용

mem_init 함수는 힙에 가용한 가상메모리를 큰 더블 워드로 정렬된 바이트의 배열로 모델

mem_heap과 mem_brk 사이의 바이트들은 할당된 가상메모리

mem_brk 다음에 오는 바이트들은 미할당 가상메모리

할당기는 mem_sbrk 함수를 호출해서 추가적인 힙 메모리를 요청

/* Private global variables */

/* Points to first byte of heap*/
static char *mem_heap;
/* Points to last byte of heap plus 1 */
static char *mem_brk;
/* Max legal heap addr plus 1 */
static char *mem_max_addr;

/* mem_init - Initialize the memory system model */
void mem_init(void)
{
    mem_heap = (char *)malloc(MAX_HEAP);
    mem_brk = (char *)mem_heap;
    mem_max_addr = (char *)(mem_heap + MAX_HEAP);
}

/* mem_sbrk - Simple model of the sbrk function.
Extends the heap by incr bytes and returns the start address of the new area.
In this model. the heap cannot be shrunk */
void *mem_sbrk(int incr)
{
    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;
}

mm_init 함수는 할당기를 초기화, 성공이면 0을 아니면 -1을 리턴

mm_malloc과 mm_free 함수는 이들에 대응되는 시스템 함수들과 동일한 인터페이스와 의미

할당기는 최소 블록 크기는 16바이트이며 가용 리스트는 묵시적 가용 리스트로 구성

첫번째 워드는 더블 워드 경계로 정렬된 미사용 패딩 워드

패딩 다음에는 헤더와 풋터로만 구성된 8바이트 할당 블록인 프롤로그 블록

프롤로그 블록은 초기화 과정에서 생성되며 절대 반환하지 않는다.

프롤로그 블록 다음에는 malloc 또는 free를 호출해서 0 또는 1개 이상의 일반 블록

힙은 항상 헤더만으로 구성된 크기가 0으로 할당된 에필로그 블록

(프롤로그와 에필로그 블록들은 연결과정 동안에 가장자리 조건을 없애주는 방법)

할당기는 한 개의 정적(static) 전역변수를 사용하며, 항상 프롤로그 블록을 가리킨다.

가용 리스트 조작을 위한 기본 상수와 매크로

/* 가용 리스트 조작을 위한 기본 상수와 매크로 */

/* 워드와 헤더/풋터의 크기 */
#define WSIZE       4
/* 더블 워드의 크기 */
#define DSIZE       8
/* 초기 가용 블록과 힙 확장을 위한 기본 크기 */
#define CHUNKSIZE   (1 << 12)

/* x가 y보다 크면 x, 그렇지 않으면 y */
#define MAX(x, y) ((x) > (y) ? (x) : (y))

/* 크기와 할당 비트를 통합해서 헤더와 풋터에 저장할 수 있는 값을 리턴 */
#define PACK(size, alloc)   ((size) | (alloc))

/* 인자 p가 참조하는 워드를 읽어서 리턴 */
#define GET(p)      (*(unsigned int *)(p))
/* 인자 p가 가리키는 워드에 val을 저장 */
#define PUT(p, val) (*(unsigned int *)(p) = (val))

/* 주소 p에 있는 헤더 또는 풋터의 크기를 리턴 */
#define GET_SIZE(p)     (GET(p) & ~0x7)
/* 주소 p에 있는 할당 비트를 리턴 */
#define GET_ALLOC(p)    (GET(p) & 0x1)

/* 블록 포인터 bp가 주어지면 블록 헤더를 가리키는 포인터를 리턴 */
#define HDRP(pb)    ((char *)(bp)-WSIZE)
/* 블록 포인터 bp가 주어지면 블록 풋터를 가리키는 포인터를 리턴 */
#define FTRP(bp)    ((char *)(bp) + GET_SIZE(HDRP(bp) - DSIZE))

/* 다음 블록의 블록 포인터를 리턴 */
#define NEXT_BLKP(bp)   ((char *)(bp) + GET_SIZE(((char *)(bp)-WSIZE)))
/* 이전 블록의 블록 포인터를 리턴 */
#define PREV_BLKP(bp)   ((char *)(bp)-GET_SIZE(((char *)(bp)-DSIZE)))

• WSIZE: 워드 크기

• DSIZE: 더블 워드

• CHUNKSIZE: 초기 가용 블록과 힙 확장을 위한 기본 크기

• PACK 매크로: 크기와 할당 비트를 통합해서 헤더와 풋터에 저장할 수 있는 값을 리턴

• GET 매크로: 인자 p가 참조하는 워드를 읽어서 리턴

• PUT 매크로: 인자 p가 가리키는 워드에 val을 저장

초기 가용 리스트 만들기

/* 최초 가용 블록으로 힙 생성 */
/* mm_init 함수는 할당기를 초기화하고 성공이면 0을 아니면 -1을 리턴 */
/* 메모리 시스템에서 4워드를 가져와서 빈 가용 리스트를 만들 수 있도록 초기화 */

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

    /* 힙을 CHUNKSIZE 바이트로 확장 */
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;
    return 0;
}

mm_malloc이나 mm_free를 호출하기 전에 어플리케이션은 mm_init 함수를 호출해서 힙을 초기화

mm_init 함수는 메모리 시스템에서 4워드를 가져와서 빈 가용 리스트를 만들 수 있도록 초기화

extend_heap 함수를 호출해서 힙을 CHUNKSIZE 바이트로 확장하고 초기 가용 블록을 생성

extend_heap 함수는 (1) 힙이 초기화 될 때와 (2) mm_malloc이 적당한 맞춤 fit을 찾지 못했을 때 호출

extend_heap은 정렬을 유지하기 위해서 요청한 크기를 인접 2워드의 배수(8바이트)로 올림한 후 메모리 시스템으로부터 추가적인 힙 공간을 요청

힙은 더블 워드 경계에서 시작하고, extend_heap으로 가는 모든 호출은 그 크기가 더블 워드의 배수인 블록을 리턴

mem_sbrk로의 모든 호출은 에필로그 블록의 헤더에 곧이어서 더블 워드 정렬된 메모리 블록을 리턴

헤더는 새 가용 블록의 헤더가 되고, 블록의 마지막 워드는 새 에필로그 블록 헤더가 됨

이전 힙이 가용 블록으로 끝났다면, 두 개의 가용 블록을 통합하기 위해 coalesce 함수를 호출

통합된 블록의 블록 포인터를 리턴

블록 반환과 연결

/* 블록을 반환하고 경계 태그 연결을 사용해서 상수 시간에 인접 가용 블록들과 통합 */
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);
}

/* 힙을 CHUNKSIZE 바이트로 확장하고 초기 가용 블록을 생성 */
static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;

    /* 요청한 크기를 인접 2워드의 배수(8바이트)로 올림 후 메모리 시스템으로부터 추가적인 힙 공간 요청 */
    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);
}

응용이는 이전에 할당한 블록을 mm_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));

    /* 이전과 다음 블록이 모두 할당되어 있는 경우 */
    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(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(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;
}

요청한 블록을 반환하고(bp) 인접 가용 블록들을 경계 태그 연결 기술을 사용해서 통합

블록 할당

/* 가용 리스트에서 블록 할당 */
void *mm_malloc(size_t size)
{
    size_t asize;
    size_t extendsize;
    char *bp;

    if (size == 0)
        return NULL;

    /* 최소 16바이트 크기의 블록을 구성 (8바이트는 정렬 요건, 추가적인 8바이트는 헤더와 풋터 오버헤드를 위해) */
    if (size <= DSIZE)
        asize = 2 * DSIZE;
    /* 8바이트를 넘으면 오버헤드 바이트를 추가하고, 인접 8의 배수로 반올림 */
    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;
}

어플리케이션은 mm_malloc 함수를 호출해서 size바이트의 메모리 블록을 요청

할당기는 요청한 블록 크기를 조절해서 헤더와 풋터를 위한 공간을 확보하여 더블 워드 요건을 충족

DSIZE와의 대소비교를 통해 조건문을 설정하여 최소 16바이트 크기의 블록을 구성

(8바이트는 정렬 요건을 만족시키기 위해, 추가적인 8바이트는 헤더와 풋터 오버헤드를 위해)

8바이트를 넘는 요청에 대해서 오버헤드 바이트를 추가하고, 인접 8의 배수로 반올림

할당기가 요청한 크기를 조정한 후에 적절한 가용 블록을 가용 리스트에서 검색

맞는 블록을 찾으면 할당기는 요청한 블록을 배치하고 (초과부분을 분할) 새롭게 할당한 블록을 리턴

할당기가 맞는 블록을 찾지 못하면 힙을 새로운 가용 블록으로 확장

요청한 블록을 새 가용 블록에 배치하고 (블록을 분할) 새롭게 할당한 블록의 포인터를 리턴

find_fit 함수

static void *find_fit(size_t asize)
{
    /* First-fit search */
    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;
        }
    }

    /* No fit */
    return NULL;
}

place 함수

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