[CS] malloc-lab 구현 - 명시적 가용 리스트

malloc-lab - 명시적 가용 리스트

• explicit free list 방식
• 자세한 것은 이전의 [[malloc-lab 구현 - 묵시적 가용 리스트]] 참고

상수 및 매크로 선언

#define MINIMUM 16

#define PREC_FREEP(bp) (*(void **)(bp))
#define SUCC_FREEP(bp) (*(void **)(bp + WSIZE))

static char *free_listp = NULL;

putFreeBlock()

• 새 free 블록을 free list의 처음에 추가한다(LIFO).
• 포인터 free_listp는 free list의 첫 주소를 가리키므로, free_listp가 가리키는 free list 안의 블록과 PRED, SUCC 링크를 진행한다.

void putFreeBlock(void *bp) {
    SUCC_FREEP(bp) = free_listp;
    PREC_FREEP(bp) = NULL;
    PREC_FREEP(free_listp) = bp;
    free_listp = bp;
}

removeBlock()

• 할당되거나 연결되는 가용 블록을 free list에서 없앤다.
• free list 상에서 해당 블록의 이전, 이후 블록을 서로 이어준다.

void removeBlock(void *bp) {
    if (bp == free_listp) {
        PREC_FREEP(SUCC_FREEP(bp)) = NULL;
        free_listp = SUCC_FREEP(bp);
    } else {
        SUCC_FREEP(PREC_FREEP(bp)) = SUCC_FREEP(bp);
        PREC_FREEP(SUCC_FREEP(bp)) = PREC_FREEP(bp);
    }
}

coalesce()

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

    putFreeBlock(bp);
    return bp;
}

place()

• 할당될 블록을 free list에서 삭제
• 분할된 경우, 새 가용 블록을 free list에 넣어준다.

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);
        PUT(HDRP(bp), PACK(csize - asize, 0));
        PUT(FTRP(bp), PACK(csize - asize, 0));
        putFreeBlock(bp);
    } else {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

find_fit()

• First Fit 방식으로 구현한다.
• free list 만을 돌면서 리스트 맨 뒤의 프롤로그 블록을 만나면, 종료

static void *find_fit(size_t asize) {
    void *bp;
    for (bp = free_listp; GET_ALLOC(HDRP(bp)) != 1; bp = SUCC_FREEP(bp)) {
        if (asize <= GET_SIZE(HDRP(bp))) {
            return bp;
        }
    }

    return NULL;
}

mm_init()

• 이전 블록을 가리키는 PREC와 이후 블록을 가리키는 SUCC를 NULL로 초기화

int mm_init(void) {
    if ((heap_listp = mem_sbrk(6 * WSIZE)) == (void *)-1)
        return -1;

    PUT(heap_listp, 0);
    PUT(heap_listp + (1 * WSIZE), PACK(MINIMUM, 1));
    PUT(heap_listp + (2 * WSIZE), NULL);
    PUT(heap_listp + (3 * WSIZE), NULL);
    PUT(heap_listp + (4 * WSIZE), PACK(MINIMUM, 1));
    PUT(heap_listp + (5 * WSIZE), PACK(0, 1));
    free_listp = heap_listp + (2 * WSIZE);

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

mm_malloc()

void *mm_malloc(size_t size) {
    size_t asize;
    size_t extendsize;
    char *bp;

    if (size == 0)
        return NULL;

    asize = ALIGN(size + SIZE_T_SIZE);

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

참고

• malloc, free 구현 프로젝트