[C] malloc lab Part.2

정글 51일차

malloc 흐름 정리

---

free

void mm_free(void *bp)
{
    size_t size = GET_SIZE(HDRP(bp)); //free할 현재 블록의 크기를 가져옴

    PUT(HDRP(bp), PACK(size, 0)); //header free
    PUT(FTRP(bp), PACK(size, 0)); //footer free
    coalesce(bp);
}

• free()는 내부적으로 메모리를 지우지않고 헤더와 푸터의 alloc을 0으로 설정해 가용 블록 해줌
• 인접 free 블록이 있으면 병합

---

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)); //현재 블록 크기 확인. size = 현재블록의 size

    //Case 1 : 둘다 할당
    if (prev_alloc && next_alloc){
        return bp;
    }

    //Case 2 : 이전 블록 alloc 1, 다음블록 free 0
    //현재 블록 + 다음 블록 병합
    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)); //푸터 업데이트 : 뒤 블록의 푸터 위치
}

    //Case 3 : 이전 블록 free 0, 다음 블록 alloc 1
    //이전 블록 + 현재 블록 병합
    else if (!prev_alloc && next_alloc){
        size += GET_SIZE(FTRP(PREV_BLKP(bp))); //이전 블록 크기만큼 증가
        PUT(FTRP(bp), PACK(size, 0)); //푸터 업데이트 : 현재 위치
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); //헤더 업데이트 : 이전 블록 시작
        bp = PREV_BLKP(bp); //bp를 이전 블록으로 이동
    }
    //Case 4 : 이전 블록 free 0, 다음 블록 free 0
    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); //bp 변경
    }
    return bp;
}

Case 1

양쪽 다 할당된 경우이므로 그대로 return

Case 2

현재블록 + 다음 블록 병합

PUT(FTRP(bp), PACK(size, 0));에서 NEXT_BLKP(bp) 가 아닌 FTRP(bp)인 이유 :
FTRP(bp)는 헤더에서 값을 읽어옴->헤더는 이미 size갱신됨. 그래서 FTRP로 푸터 갱신이 가능하다.

Case 3

이전 블록 + 현재 블록 병합

이전 블록의 헤더, 현재 블록의 푸터만 수정한다.

Case 4

이전 블록 + 현재 블록 + 다음 블록 병합

헤더의 위치가 바뀜. bp는 아직 현재 블록 기준이므로 PUT(FTRP(NEXT_BLKP(bp)) 이렇게 됨

---

Malloc

void *mm_malloc(size_t size)
{
    size_t asize; //실제로 할당할 블록 크기(payload+header/footer 포함)
    size_t extendsize; //힙 확장할 크기
    char *bp; 

    //예외처리
    if (size == 0)
        return NULL;
        
    if (size <= DSIZE) //최소 블록 크기 보장(header+footer+최소payload)
        asize = 2*DSIZE;
    else
        //DSIZE 초과면 8의 배수로 올림
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE); //(DSIZE - 1)을 해주는 이유 : 쓸데없는 메모리 낭비를 줄이기 위해

    //가용 리스트에서 asize를 만족하는 free블록 찾기
    //찾았으면 place()로 블록 할당
    if ((bp = find_fit(asize)) != NULL){
        place(bp, asize);
        return bp;
    }

    //찾지 못했으면 heap확장
    extendsize = MAX(asize, CHUNKSIZE);

    //한번에 최소 CHUNKSIZE 이상 확장. extend는 무조건 실행됨
    if ((bp = extend_heap (extendsize/WSIZE)) == NULL)
        return NULL;

    //확장한 블록에 배정
    place(bp, asize);
    return bp;
}

• 블록의 크기를 alignment 배수 (여기선 8) 크기로 할당해야 한다.

올림 연산 분석

(size + DSIZE + (DSIZE - 1)) / DSIZE

• size : 사용자가 요청한 메모리 크기
• DSIZE : 헤더 + 푸터의 합 (4byte+4byte)
• (DSIZE - 1) : 올림처리를 위한 트릭, -1이 꼭 필요
• (DSIZE - 1)를 해주는 이유 : 쓸데없는 메모리 낭비를 줄이기 위해

예시) size = 25 바이트 요청

+8 (헤더,푸터) → 33

+7 → 40

40 / 8 = 5

asize = 5 * 8 = 40

요청 25byte -> 실제 할당 블록은 4B

find_fit

1. first_fit

static void *find_fit(size_t asize)
{
    char *bp = heap_listp; //앞부터 탐색

    //종료조건 : 에필로그 블록을 만나기 전까지 
    while (GET_SIZE(HDRP(bp)) > 0)
    {
        if (GET_SIZE(HDRP(bp)) >= asize && !GET_ALLOC(HDRP(bp))) //asize가 적당한 크기를 찾았고, ALLOC이 0이라면 
        {
            return bp;
        }
        bp = NEXT_BLKP(bp); //bp는 다음 블럭으로 이동
    }
    return NULL; //못찾았으면 NULL반환
}

수도코드

앞부터 탐색. 앞 = heap_listp
가용 블록이 하나도 없다면 NULL 반환
asize <= 빈공간 && 할당안된 블록이라면 return bp
아니면 다음 블럭으로 이동
언제까지? 에필로그 블록을 만나기 전까지

bp = heap_listp
while (GET_SIZE(HDRP(bp) > 0
if(GET_SIZE(HDRP(bp))) = asize && !GET_ALLOC(HDRP(bp)))
return bp
bp = NEXT_BLKP(bp);
return NULL

---

place

//적당한 가용블록 찾았을 때, 그 블록을 실제 요청한 크기로 할당 상태로 바꿔줌
static void place(void *bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp)); //현재 블록 크기
    
    //분할이 가능한지 확인 (최소 블록 크기 이상 남을 때)
    //asize와 (csize-asize)로 분할
    if (csize - asize >= (2*DSIZE))
    {
        PUT(HDRP(bp), PACK(asize, 1)); //헤더에 할당표시
        PUT(FTRP(bp), PACK(asize, 1)); //푸터에 할당표시

        //나머지 부분을 free블록으로 만들기
        void *new_bp = NEXT_BLKP(bp);
        PUT(HDRP(new_bp), PACK(csize - asize, 0)); //free헤더
        PUT(FTRP(new_bp), PACK(csize - asize, 0)); //free푸터
    } else //분할 x,전체 블록 csize할당
    {
        PUT(HDRP(bp), PACK(csize,1)); //헤더에 할당표시
        PUT(FTRP(bp), PACK(csize,1)); //푸터에 할당표시
    }
}

수도코드

현재 블록의 크기 가져오기
요청한 크기를 뺀 남은 공간 찾기 
남은 공간이 최속 블록 크기 이상이라면,
	앞부분 asize만큼은 헤더/푸터에 alloc 1
    남은 부분은 헤더/푸터에 alloc 0
남은 공간이 작으면?현재 블록 전체를 alloc 1

Test 결과

현재 점수는 71점이 나온다. 성능 개선을 위해 next_fit, best_fit을 사용해 구현을 해봐야겠다.