[Malloc] Implict

2024.04.14 - [sw정글/C] - [Malloc] Malloc Lab 개요

[Malloc] Malloc Lab 개요

책의 내용을 토대로 약간 변주를 주면서 나름대로 분석했다.

 

일단 Implict 즉 묵시적 방법으로 새롭게 malloc해줄 공간을 찾는다는것이다.

처음에는 용어의 혼동이 왔는데, malloc은 명시적 할당기이고, 지금 구현하는 malloc의 메모리할당방식은 묵시적 리스트방식으로,

가용블럭인지 비가용블럭인지판단안하고 모두 순회해서 적합한 메모리할당구역을 찾는다는 뜻이다.
반대의 개념으로 명시적 리스트 방식이 존재하는데, 가용블록만을 적절한 자료구조를 사용해서 순회해서 할당해줄 곳을 찾는다는것!

---

일단 매크로 및 상수부분이다.

 

/*워드 크기*/
#define WSIZE 4 

/*더블 워드 크기*/
#define DSIZE 8 

/*초기 가용블럭과 힙확장을 위한 기본크기 1을 비트쉬프트로 12번이동 ~ =2^12승 = 4096=4KB*/
#define CHUNKSIZE (1 << 12) 

#define MAX(x, y) ((x) > (y) ? (x) : (y))

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

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

/* 헤더 또는 풋터의 사이즈 리턴*/
#define GET_SIZE(p) (GET(p) & ~0x7)  
/* 헤더 또는 풋터의 할당비트 리턴 */
#define GET_ALLOC(p) (GET(p) & 0x01) 

#define HDRP(bp) ((char *)(bp)-WSIZE)
#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)))

앞으로 .각각의 매크로가 사용될때 어떻게 사용되는지 볼것이다

---

mm_init()

int mm_init(void)
{
    /*빈 가용 리스트를 만들기위헤 메모리 시스템에서 4워드를 가져온다*/
    heap_listp = mem_sbrk(4 * WSIZE);
    if ((heap_listp) == (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;
}

할당기를 초기화하는 함수이다,

mem_sbrk함수를 이용해 초기화 할만큼 늘려놓고 값을 할당후 -> 힙을 크게 확장해준다

여기서 mem_sbrk 는 현재 힙의 끝부분 부터 연속적으로 확장해주고 확장전의 주소를 가리키는 포인터를 반환해주는 함수이다

---

extend_heap()

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

요청이들어온 만큼 힙의 크기를 확장시켜주는 함수이다.

사이즈를 메모리 정렬 조건에 맞출 수있게 변경해준뒤, init에서 요청했던것처럼 mem_sbrk를 이용해서 힙을 원하는 만큼 확장하고 확장전에 가리키고 있던 포인터를 반환해준다.

---

coalesece()

책을보고 코드를 구현했을때는 뭔가 너무 많은 분기를 탐색한다고 생각했다.  아래 제시한 코드는 초기버전이고.. 요 밑이나 나중에 따로 간단하게 만든 코드도 올릴것이다

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

    // 앞 뒤 free블록이면 병합//
    if (prev_alloc && next_alloc)
        return bp;
    else if (prev_alloc && !next_alloc) /*다음블록이랑 병합할 수 있는 경우 -> head 는 현재 foot는 업데이트된 size를받아서 현재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) /*이전 블록과 통합.. foot 먼저 지정해야 오류가 없을듯?*/
    {
        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;
}

 

init → heap extend→ coalesce 시 앞뒤 할당되었나 확인 하는 과정 중 이전 블록이 할당되었나 확인 하는 과정 (초기 확장은 이전 블록은 prolog를 가리키기 때문에.) 

---

init → heap extend→ coalesce 시 앞뒤 할당되었나 확인 하는 과정 중 다음 블록이 할당되었나 확인 하는 과정 (초기 확장은 다음블록은 epilog에 의해 할당되었다고 생각된다.)

 

아래는 위의 coalesece 함수를 좀더 간단하게 구현한 코드이다. 

왼쪽 확인하고 비어있으면 병합, 오른쪽확인하고 비어있으면 병합이다. 

명시적가용리스트에서부터 간단하게 해보자 해서 새롭게 리펙토링했다.

static void *coalesce(void *bp)
{
    size_t size = GET_SIZE(HDRP(bp));

    if (!GET_ALLOC(HDRP(NEXT_BLKP(bp))))
    {
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }
    if (!GET_ALLOC(FTRP(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));
    }
    return bp;
}

---

mm_free()

void mm_free(void *ptr)
{
    size_t size = GET_SIZE(GET_HEAD_POINTER(ptr));

    PUT(GET_HEAD_POINTER(ptr), PACK(size, 0));
    PUT(GET_FOOT_POINTER(ptr), PACK(size, 0));

    coalesce(ptr);
}

 

할당되었다는 표시만 지운다.. ! 

---

mm_malloc()

void *mm_malloc(size_t size)
{
    size_t asize;      /*Adjusted block size*/
    size_t extendsize; /*Amount to extend heap if no fit*/
    char *bp;

    if (size == 0)
        return NULL;

    if (size <= DSIZE)
        asize = 2 * DSIZE;
    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;
}

메모리 정렬을 위해 할당사이즈(asize)를 초기화해주고, 메모리상 들어갈곳을 찾고(find_fit) 할당해준다(place)

할당에 실패했다면 힙사이즈를 확장후 할당해준다. 

즉,

• asize = 2 * DSIZE; 할당 요청 사이즈가 DSIZE보다 작으면 aszie는 더블사이즈의 두배를 요청
  → 왜냐면 이렇게 하면 4워드자나 (1워드 = 헤더, 1워드 =풋터, 1워드=데이터 이렇게 하면 정렬이 깨지니까 최소단위로 하나 더 할당해서 4워드로 유지하는것)
• else : 요청크기가 2워드를 넘어가면 asize를 2워드의 배수가 되게 할당
• asize가 들어갈 곳을 찾으면 그곳에 할당
• 아니라면 힙확장.

---

find_fit()

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

---

place()

---

 

가장기본적인 묵시적 리스트의 first_fit 방법이다. 

가장기본적인것만큼 점수도 가장 안나왔다 아마 54~6 사이였던것같다, 

기본적이지만 여기서 헤더,풋터 및 기본적인 말록의 작동방식및 malloc을 편하게 구현하기 위한 매크로 사용방식등을 익혔다.

 

특히 각각의 반환된 포인터들이 어디를 지목하고 있는지, 각각의 매크로가 어떤 기능을 하고, 비트계산은 어떻게 되는지 아는게 중요한하다..

아니면 나중에 이해가 안되서 발목잡힐듯하다.

 

뭐든 스노우볼 굴러가는건 동일한듯... 기초를 무시하지말자..!