동적 메모리 할당: 명시적(explicit) 가용 리스트

서론

동적 메모리 할당을 할 때 가용 리스트를 구성하는 방법에는 묵시적 가용 리스트(implicit), 명시적 가용 리스트(explicit), 분리 가용 리스트(segregated), 버디 시스템(buddy system) 등이 있습니다. 본문에서는 이 중 명시적 가용 리스트(explicit)를 사용한 동적 메모리 할당을 설명합니다.
implicit에서 수정한 코드이기 때문에 수정되지 않은 코드는 설명을 적지 않습니다. 이전 게시글에 자세한 설명이 있습니다.

---

explicit에서 블록의 구성

implicit에서 사용한 블록과 달리 explicit에서는 가용 블록에 가용리스트의 다음 블록을 가리키는 Next와 이전 블록을 가리키는 Prev 포인터가 추가되어 있다.

정의 & 선언

#define GET_NEXT(bp) (*(void **)(bp))         
#define GET_PREV(bp) (*(void **)(bp + WSIZE)) 

• Next free block의 시작주소를 읽어오는 함수
• Prev free block의 시작주소를 읽어오는 함수

static char *heap_listp = NULL;
static char *free_listp = NULL;

• free_lisp: 가용 블록 리스트의 시작

---

함수

void putFreeBlock(void *bp): LIFO - 반환되거나 분할로 생긴 가용 블록을 가용리스트 가장 앞에 추가

void putFreeBlock(void *bp)
{
    GET_NEXT(bp) = free_listp; 
    GET_PREV(bp) = NULL;      
    GET_PREV(free_listp) = bp; 
    free_listp = bp;          
}

• 들어온 가용블록의 다음 블록을 현재 가용리스트 가장 앞으로 하기
• 새로 들어온 가용블록의 앞을 없애주면서 가용리스트의 가장 앞임을 알 수 있게 한다.
• 들어온 가용블록을 현재 가용리스트 앞으로 하기
• 가용리스트의 가장 앞을 들어온 가용블록으로 하기

void removeBlock(void *bp): 가용 블록을 free list에서 삭제

void removeBlock(void *bp)
{
    if (bp == free_listp) 
    {
        free_listp = GET_NEXT(bp);     
        GET_PREV(GET_NEXT(bp)) = NULL; 
    }
    else if (GET_NEXT(bp) == NULL)
    {
        GET_NEXT(GET_PREV(bp)) = NULL;
        GET_PREV(bp) = NULL;
    }
    else
    {
        GET_NEXT(GET_PREV(bp)) = GET_NEXT(bp);
        GET_PREV(GET_NEXT(bp)) = GET_PREV(bp);
    }
}

• bp가 가용리스트의 첫번째이면 bp 다음 블록을 첫번째 블록으로 만들고, bp 다음 블록의 이전을 NULL로 처리하기
• bp가 가용리스트의 마지막이면 NULL 처리
• bp가 가용리스트의 중간 블록이면 bp의 이전 블록과 다음 블록 이어주기

int mm_init(void)

int mm_init(void)
{
    if ((heap_listp = mem_sbrk(6 * WSIZE)) == (void *)-1)
        return -1;
    PUT(heap_listp, 0);                                /* Alignment padding */
    PUT(heap_listp + (1 * WSIZE), PACK(2 * DSIZE, 1)); /* Prologue header */
    PUT(heap_listp + (2 * WSIZE), NULL);               /* 프롤로그 NEXT NULL로 초기화. */
    PUT(heap_listp + (3 * WSIZE), NULL);               /* 프롤로그 PREV NULL로 초기화 */
    PUT(heap_listp + (4 * WSIZE), PACK(2 * DSIZE, 1)); /* Prologue footer */
    PUT(heap_listp + (5 * WSIZE), PACK(0, 1));         /* Epilogue header */

    free_listp = heap_listp + DSIZE;

    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;
    return 0;
}

🤔 왜 NEXT를 앞으로?
payload 자리를 찾아가는 코드로 구성되어 있기 때문에 해당 자리에서 바로 찾을 수 있는 곳에 NEXT를 둬서 최대한의 동작을 줄임

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));                   
    /* Case 1 앞, 뒤 모두 할당되어 있을 때 */
    /* Case 2 앞은 할당되어 있고, 뒤는 가용블록일 때 */
    if (prev_alloc && !next_alloc)
    {
        removeBlock(NEXT_BLKP(bp));
        size += GET_SIZE(HDRP(NEXT_BLKP(bp))); 
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }
    /* Case 3 앞은 가용블록이고, 뒤는 할당되어 있을 때 */
    else if (!prev_alloc && next_alloc)
    {
        removeBlock(PREV_BLKP(bp));
        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);
    }
    /* Case 4 앞, 뒤 모두 가용블록일 때 */
    else if (!prev_alloc && !next_alloc)
    {
        removeBlock(NEXT_BLKP(bp));
        removeBlock(PREV_BLKP(bp));
        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);
    }
    putFreeBlock(bp);
    return bp;
}

static void place(void *bp, size_t asize)

static void place(void *bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));  
    removeBlock(bp);                   
    if ((csize - asize) >= (2 * DSIZE)) 
    {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1)); 
        bp = NEXT_BLKP(bp);
        putFreeBlock(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));
    }
}

• 사용할 가용블록을 가용리스트에서 없애기
• 분할의 가치가 있으면 분할하고 남은 가용블록을 가용리스트에 추가하고 분할할만큼 크지 않으면 다 쓰기

참고자료

• <Computer Systems: A Programmers Perspective> Section 9.9 - Randal Bryant
• github dkkim0122/malloc-lab
• 블로그 <정글사관학교 44일차 TIL: Explicit malloc 정리 및 구현 review>

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