240223_Malloc Lab(Explicit, Implicit)

• 주어진 파일에서 Malloc, Realloc, Free 등 함수를 직접 작성하여, out of Memory를 없애는 것이 목표이다.

• 해당 과제는 Implicit List 방식과 Explicit List 방식으로 작성하였다.

묵시적 가용 리스트(Implicit List)

• 묵시적이기에 내 위치 기준 인접 블록을 찾기 쉽게 하기위해서 블록 내부에 다음 블록을 찾기 위해 Header를, 이전 블록을 찾기 위해 Footer를 설정한다.

• Header, Footer에는 현재 블록의 사이즈 및 할당 여부의 정보가 저장되어있다.

• 해당 코드는 가용 블록 리스트를 First Fit 방법으로 탐색하며, 임의의 블록을 Free 시키면, 그 즉시 좌우 인접 블록을 확인하여 연결한 후 블록을 반환한다.

기본 상수 및 매크로 정의

#define ALIGNMENT 8

#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7) // 8의 배수로 padding

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

// 기본 사이즈 상수 정의
#define WSIZE               4
#define DSIZE               8
#define CHUNKSIZE           (1 << 12)                   // 4096byte

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

#define PACK(size, alloc)   ((size) | (alloc))          // or연산자로 사이즈 + 할당 여부 반환

#define GET(p)              (*(unsigned int *)(p))          // get
#define PUT(p, size)        (*(unsigned int *)(p) = size)   // set

#define GET_SIZE(p)         (GET(p) & ~0x7)             // 뒷자리 3개를 제외한 나머지 수 즉, 해당 블록의 사이즈 반환
#define GET_ALLOC(p)        (GET(p) & 0x1)              // 뒷자리 3개만 확인 즉, 해당 블록의 할당 여부 반환

#define HDRP(bp)            ((char *)(bp) - WSIZE)                      // header block
#define FTRP(bp)            ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // footer block

#define NEXT_BLKP(bp)       ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp)       ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

블록 포인터(bp)는 항상 payload부분을 가리키기때문에, GetSize나 GetAlloc을 할땐, Header또는 Footer에 저장된 정보를 참조해야한다.

mm_init

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));          // Prologue Header
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));          // Prologue Footer
    PUT(heap_listp + (3 * WSIZE), PACK(0, 1));              // Epilogue Header -> 왜 size == 0?
    heap_listp += 2 * WSIZE;                                // Prologue block 다음 블록 위치 지정

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

Epilogue Header의 사이즈를 0으로 저장하는 이유: Epilogue header의 크기를 0으로 유지함으로써, 프로그램의 가상 힙의 끝을 나타내는 데 필요한 최소한의 정보만 사용. 이는 구현을 단순화하고, 메모리 할당 및 해제 작업의 효율성을 향상.

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));       // New Epilogue Header

    return coalesce(bp);                        // 두 번째 힙 영역이 할당될 때, 기존에 있던 영역과 연결해주기 위해.
}

힙 확장 함수에서 header 및 footer를 달아준다.

coalesce

*/
// 가용 블록들을 통합
static void *coalesce(void *bp)
{
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_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(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(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 매개변수에는 free됐거나, 새로 확장된 힙 영역이 들어온다. 들어온 bp기준으로 이전, 다음 블록을 확인하여 가용블록이 있다면 연결하여 bp를 반환한다.

mm_malloc

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

    if(size == 0)
        return NULL;

    // header, footer가 달리니, 8byte 배수 크기로 맞춰준다.
    if(size <= DSIZE)
        asize = 2 * DSIZE;
    else
        asize = DSIZE * ((size + DSIZE + (DSIZE - 1)) / DSIZE);

    if((bp = first_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;
}

adjust된 사이즈(payload크기 8의 배수 + Header + footer(하나의 블록은 최소 16byte 크기를 가진다.))를 First Fit방법으로 찾아서 할당하거나, 힙 영역을 확장하여 할당한다.

first_fit

static void *first_fit(size_t asize)
{
    char *tempBp = heap_listp;

    while(GET_SIZE(HDRP(tempBp)) > 0)
    {
        if(GET_SIZE(HDRP(tempBp)) >= asize && !GET_ALLOC(HDRP(tempBp)))
            return tempBp;
        tempBp = NEXT_BLKP(tempBp);
    }

    return NULL;
}

Header의 사이즈가 0보다 클 때까지, 즉 Epilogue Header를 만나기 전까지 반복하여 할당할 블록 사이즈보다 크거나 같은 가용 블록의 bp를 반환한다.

place

static void place(void *bp, size_t asize)
{
    size_t beforeFreeBlkSize = GET_SIZE(HDRP(bp));
    
    // 만약 16byte 보다 작다면 사용하지 못하니 패딩을 채워준다.
    if((beforeFreeBlkSize - asize) >= (2*DSIZE))
    {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(beforeFreeBlkSize - asize, 0));
        PUT(FTRP(bp), PACK(beforeFreeBlkSize - asize, 0));
    }
    else
    {
        PUT(HDRP(bp), PACK(beforeFreeBlkSize, 1));
        PUT(FTRP(bp), PACK(beforeFreeBlkSize, 1));
    }
}

place함수의 bp는 사용할 가용 블록의 포인터이고, asize는 최소 16byte크기로 adjust되고, 사용자가 할당하고 싶은 사이즈이다.
만약 가용 블록이 24byte가 남아있고, 할당할 블록 사이즈가 16byte라 한다면, 할당 후 8byte가 남기때문에 이 남은 사이즈에 대해서 외부단편화를 없애기 위해 패딩으로 채워준다.

mm_free

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

    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    coalesce(ptr);
}

mm_realloc

void *mm_realloc(void *ptr, size_t size)
{
    void *oldptr = ptr;
    void *newptr;
    size_t copySize;

    newptr = mm_malloc(size);
    if (newptr == NULL)
        return NULL;
    copySize = GET_SIZE(HDRP(ptr)) - DSIZE;
    if (size < copySize)
        copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

여기서 주의할 점은 copySize에는 payload크기가 들어가야하기 때문에 DSIZE 즉 Header, Footer크기 만큼 빼줘야한다.

명시적 가용 리스트(Explicit List)

• 가용 블록들을 리스트로 관리하며, 가용 블럭에는 이전 가용 블록 및 다음 가용 블록 가리키는 포인터를 저장한다.
• 할당할 때, 힙 전체를 검색하는 것이 아닌 가용 블록 리스트를 탐색하면 된다.
• 가용 블록을 가용 블록 리스트에 저장할 때, Address Order방식은 주소 순서로 저장하여야하기 때문에, 저장할때, O(n)만큼에 시간이 더 들어가게 되기 때문에 해당 코드는 LIFO방식을 사용하여 저장하였다.

기본 상수 및 매크로

#define NEXT_FREE_BLOCK(bp) (*(void **)((bp) + WSIZE))
#define PREV_FREE_BLOCK(bp) (*(void **)(bp))

이전, 다음 가용 블록을 가리키는 포인터가 추가되었다. 나머지는 전과 동일하다.

mm_init

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

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

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

더미 가용 블록을 추가하는 방법도 있지만, 여기서는 Prologue Header,Footer의 사이즈를 16byte로 늘리고 Prologue Header, Footer 사이에 이전, 다음 가용 블록을 가리키는 포인터를 추가하였다.

extend_heap / mm_malloc

묵시적 가용 리스트와 동일하다.

coalesce

static void *coalesce(void *bp)
{
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));

    if(prev_alloc && next_alloc)
    {
        AddBlock(bp);
        return bp;
    }

    else 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));
        AddBlock(bp);
    }

    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);
        AddBlock(bp);
    }

    else
    {
        RemoveBlock(PREV_BLKP(bp));
        RemoveBlock(NEXT_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);
        AddBlock(bp);
    }

    return bp;
}

LIFO방식은 새로 생긴 가용 블록을 무조건 제일 앞으로 연결하는 방식이기때문에, 이전, 다음 가용 블록 리스트가 있다면, 현재 등록된 리스트에서 제거 한 후, 가용 블록 끼리 연결하고, 다시 가용 블록 리스트 맨 앞으로 넣어준다.

RemoveBlock

static void RemoveBlock(void *bp)
{
    if(bp == free_listp)
    {
        free_listp = NEXT_FREE_BLOCK(bp);
        if(free_listp != NULL)
            PREV_FREE_BLOCK(free_listp) = NULL;
        return;
    }

    NEXT_FREE_BLOCK(PREV_FREE_BLOCK(bp)) = NEXT_FREE_BLOCK(bp);
    if(NEXT_FREE_BLOCK(bp) != NULL)
        PREV_FREE_BLOCK(NEXT_FREE_BLOCK(bp)) = PREV_FREE_BLOCK(bp);
}

만약 삭제해야할 가용 블록이 루트인지 아닌지 확인한다.

AddBlock

static void AddBlock(void *bp)
{
    NEXT_FREE_BLOCK(bp) = free_listp;
    PREV_FREE_BLOCK(bp) = NULL;
    if(free_listp != NULL)
        PREV_FREE_BLOCK(free_listp) = bp;
    free_listp = bp;
}

새로 생긴 가용 블록을 제일 앞으로 가져와서 연결한다.

first_fit

static void *first_fit(size_t asize)
{
    char *tempBp = free_listp;

    while(tempBp != NULL)
    {
        if(GET_SIZE(HDRP(tempBp)) >= asize)
            return tempBp;
        tempBp = NEXT_FREE_BLOCK(tempBp);
    }

    return NULL;
}

가용 블록 리스트 내에서 adjust된 사이즈보다 크거나 같은 가용 블록을 찾아준다.

place

static void place(void *bp, size_t asize)
{
    size_t beforeFreeBlkSize = GET_SIZE(HDRP(bp));

    RemoveBlock(bp);

    if((beforeFreeBlkSize - asize) >= (2*DSIZE))
    {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(beforeFreeBlkSize - asize, 0));
        PUT(FTRP(bp), PACK(beforeFreeBlkSize - asize, 0));
        AddBlock(bp);
    }
    else
    {
        PUT(HDRP(bp), PACK(beforeFreeBlkSize, 1));
        PUT(FTRP(bp), PACK(beforeFreeBlkSize, 1));
    }
}

할당할 가용 블록을 리스트에서 제거 후, 공간이 남는다면 남은 가용 블록을 리스트에 연결하고, 아니면 제거한 채로 둔다.