Explicit Allocator - Explicit Free List

https://kimjingyu.tistory.com/entry/%EB%8F%99%EC%A0%81-%EB%A9%94%EB%AA%A8%EB%A6%AC-%ED%95%A0%EB%8B%B9%EA%B8%B0-%EA%B5%AC%ED%98%84

동적 메모리 할당기 구현

 

Explicit Free List 소개

위 포스팅에서 Explicit Allocator의 Implicit Free List 방식에 대해서 이해하고, 구현해봤었다.하지만 사실 Implicit Free List는 할당 시간이 전체 힙 블록의 수(N)에 비례하기 때문에 범용 할당기로는 적합하지 않다. 즉, Implicit Free List에서는 allocated block과 free block이 모두 연결되어 있어서, free block을 찾을 때 시간이 오래 걸린다.

 

따라서 더 좋은 방법은 가용 블록들을 Explicit Free List로 구성하는 것이다. 그리고 이 방식을 사용했을 때, 가장 큰 차이점은 가용 블록만을 위한 리스트를 연결시킨다는 점이다. 아래 그림에서  Explicit Free List를 사용했을 때, 블록의 형태를 확인해보자. allocated block은 안에 payload가 들어있기 때문에 할당기가 건드려서도 안되고 건드릴 수도 없지만, free block들은 안이 비어있기 때문에 할당기가 red, succ을 집어넣어서 이전 free list, 다음 free list를 가리키는 포인터를 저장하여 doubly linked free list로 구성될 수 있다.

Explicit Free List Block

 

아래는 Implicit Free List 방식의 block인데, 비교해보면 free 블록일 때, predecessor, successor의 존재 유무에 차이가 있음을 확인할 수 있다.

 

특징

이러한 Explicit Free List의 특징은 이중 연결 리스트로 이어져있고, 실제 주소값이 아무렇게나 존재하고, 포인터로만 연결되어 있다는 점을 확인할 수 있다.

 

 

 

장점

이렇게 Doubly Free List를 사용하면 first fit 할당 시간을 전체 블록 수에 비례하는 것에서 가용 블록의 수에 비례하는 것으로 줄일 수 있다.

 

다만, 블록을 반환하는 시간은 가용 리스트 내에서 블록을 정렬하는 정책을 어떤 것을 선택하는가에 따라 비례하거나 상수 시간을 가질 수 있다.

여기서 한 가지 접근법은 리스트를 새롭게 반환한 블록들을 리스트의 시작 부분에 삽입해서 LIFO 순으로 유지하는 것이다. 이렇게 LIFO 순서와 first fit 배치 정책을 사용하면 할당기는 최근에 사용된 블록들을 먼저 조사한다. 이 경우에 블록의 반환은 상수 시간에 수행된다. 그리고 경계 태그를 사용하면 연결도 상수 시간에 수행할 수 있다.

또 다른 접근방법은 리스트를 주소 순으로 관리하는 것으로, 리스트 내 각 블록의 주소가 다음 블록의 주소보다 작다. 따라서 이 경우에는 블록의 반환은 적당한 선행블록을 찾는데 선형 검색 시간을 필요로 한다. 그래서 first fit이 LIFO 순서를 사용하는 경우보다 주소 순서를 사용하는 best fit이 더 좋은 메모리 이용도를 가진다.

 

단점

이런 명시적 리스트의 단점은 일반적으로 가용 블록들이 충분히 커서 모든 필요한 포인터뿐 아니라 헤더, 추가적으로 풋터까지 포함해야 한다는 것이다. 그 결과, 최소 블록 크기가 커지고, 잠재적인 내부 단편화 가능성이 증가한다.

 

구현

명시적 리스트 방식을 사용할 때 포인트는 할당된 블록을 free 하게 되면, 그 free block을 어디에 넣을 것이진에 대해 고민해봐야 한다. 여기에는 앞서 본 방법에서 LIFO 정책을 사용하여 새로운 free block들을 list의 시작에 삽입함으로써 리스트를 LIFO 순서를 유지시킬 것이다.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name */
    "team 5",
    /* First member's full name */
    "kim-jingyu",
    /* First member's email address */
    "jingyu@jungle.com",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""};

#define WSIZE       4           // 워드 사이즈
#define DSIZE       8           // 더블 워드 사이즈
#define CHUNKSIZE   (1 << 12)   // 초기 가용 블록과 힙 확장을 위한 기본 크기

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

// 사이즈와 할당 비트를 합쳐서 header, footer에 저장할 수 있는 값 반환
#define PACK(size, alloc)   ((size) | (alloc))

// 특정 주소 p에 워드 읽고, 쓰기
#define GET(p)  (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (unsigned int)(val))

// 특정 주소 p에 해당하는 블록의 사이즈와 가용 여부 반환
#define GET_SIZE(p)     (GET(p) & ~0x7)
#define GET_ALLOC(p)    (GET(p) & 0x1)

// 특정 주소 p에 해당하는 블록의 header, footer의 포인터 주소 반환
#define HDRP(p)    ((char *)(p) - WSIZE)
#define FTRP(p)    ((char *)(p) + GET_SIZE(HDRP(p)) - DSIZE)

// 다음, 이전 블록의 헤더 이후의 시작 위치의 포인터 주소 반환
#define NEXT_BLKP(ptr)   (((char *)(ptr) + GET_SIZE((char *)(ptr) - WSIZE)))
#define PREV_BLKP(ptr)   (((char *)(ptr) - GET_SIZE((char *)(ptr) - DSIZE)))

#define GET_PRED(ptr)  (*(void**)(ptr))         // 이전 가용 블록의 주소
#define GET_SUCC(ptr)  (*(void**)((char*)(ptr) + WSIZE)) // 다음 가용 블록의 주소

// 기본 함수 선언
int mm_init(void);
void *mm_malloc(size_t size);
void mm_free(void *ptr);
void *mm_realloc(void *ptr, size_t size);

// 추가 함수 선언
static void *extend_heap(size_t words);
static void *coalesce(void *ptr);
static void *find_fit(size_t adjust_size);
static void place(void *ptr, size_t adjust_size);

// explicit free list 방식에서 추가
static void remove_free_block(void *bp);  // 가용 리스트에서 제거
static void add_free_block(void *bp);     // 가용 리스트에 추가

// 추가 정적 전역변수 선언
static char *free_listp;

int mm_init(void)
{
    // 초기 힙 영역의 크기 할당
    if((free_listp = mem_sbrk(8 * WSIZE)) == (void *)-1) {
        return -1;
    }

    PUT(free_listp, 0);                             // padding
    PUT(free_listp + (1 * WSIZE), PACK(DSIZE, 1));  // prologue header
    PUT(free_listp + (2 * WSIZE), PACK(DSIZE, 1));  // prologue footer
    PUT(free_listp + (3 * WSIZE), PACK(2 * DSIZE, 0));  // 첫 가용 블록의 헤더
    PUT(free_listp + (4 * WSIZE), NULL);            // 이전 가용 블록의 주소
    PUT(free_listp + (5 * WSIZE), NULL);            // 다음 가용 블록의 주소
    PUT(free_listp + (6 * WSIZE), PACK(2 * DSIZE, 0));  // 첫 가용 블록의 푸터
    PUT(free_listp + (7 * WSIZE), PACK(0, 1));      // epilogue header
    
    free_listp += (4 * WSIZE);   // 첫번째 가용 블록의 block pointer

    // 4096 비트만큼 힙 영역 확장
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL) {
        return -1;
    }
    
    return 0;
}

void *mm_malloc(size_t size)
{
    size_t adjust_size;
    size_t extend_size;
    char *ptr;

    // 의미없는 요청은 처리 안함
    if (size == 0) {
        return NULL;
    }

    // 더블 워드 정렬 제한 조건을 만족하기 위해, 할당할 공간의 크기 계산
    if (size <= DSIZE) {
        adjust_size = 2 * DSIZE;    // header(4byte) + footer(4byte) + 나머지(8byte)
    } else {
        adjust_size = DSIZE * ((size + DSIZE + (DSIZE - 1)) / DSIZE);
    }

    // 가용 블록을 가용 리스트에서 검색하고, 할당기는 요청한 블록을 배치
    if ((ptr = find_fit(adjust_size)) != NULL) {
        place(ptr, adjust_size);
        return ptr;
    }

    // 리스트에 들어갈 수 있는 free 리스트가 없으면, 메모리를 확장하고 블록을 배치
    extend_size = MAX(adjust_size, CHUNKSIZE);
    if ((ptr = extend_heap(extend_size / WSIZE)) == NULL) {
        return NULL;
    }
    place(ptr, adjust_size);
    return ptr;
}

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

void *mm_realloc(void *ptr, size_t size)
{
    /* 예외 처리 */
    if (ptr == NULL) // 포인터가 NULL인 경우 할당만 수행
        return mm_malloc(size);

    if (size <= 0) // size가 0인 경우 메모리 반환만 수행
    {
        mm_free(ptr);
        return 0;
    }

    void *newptr = mm_malloc(size); // 새로 할당한 블록의 포인터
    if (newptr == NULL)
        return NULL; // 할당 실패

    size_t copySize = GET_SIZE(HDRP(ptr)) - DSIZE;
    if (size < copySize)
        copySize = size;

    memcpy(newptr, ptr, copySize);

    mm_free(ptr);
    
    return newptr;
}

static void remove_free_block(void *ptr) {
    if (ptr == free_listp) {
        free_listp = GET_SUCC(free_listp);
        return;
    }
    GET_SUCC(GET_PRED(ptr)) = GET_SUCC(ptr);
    if (GET_SUCC(ptr) != NULL) {
        GET_PRED(GET_SUCC(ptr)) = GET_PRED(ptr);
    }
}

static void add_free_block(void *ptr) {
    GET_SUCC(ptr) = free_listp;
    if (free_listp != NULL) {
        GET_PRED(free_listp) = ptr;
    }
    free_listp = ptr;
}

static void *extend_heap(size_t words)
{
    char *ptr;
    size_t size;

    // 더블 워드 정렬 위해 짝수 개수의 워드 할당
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if ((long)(ptr = mem_sbrk(size)) == -1) {
        return NULL;
    }

    PUT(HDRP(ptr), PACK(size, 0));  // 기존 epilogue header 초기화(free 블록의 header)
    PUT(FTRP(ptr), PACK(size, 0));  // free 블록의 footer
    PUT(HDRP(NEXT_BLKP(ptr)), PACK(0, 1));  // new epilogue header

    // 만약 이전 블록이 free 였다면, 통합
    return coalesce(ptr);
}

static void *coalesce(void *ptr)
{
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(ptr))); // 이전 블록의 할당 여부
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr))); // 다음 블록의 할당 여부
    size_t size = GET_SIZE(HDRP(ptr));   // 현재 블록의 사이즈

    if (prev_alloc && next_alloc) {
        add_free_block(ptr);
        return ptr;
    } else if (prev_alloc && !next_alloc) {
        // case2 - 직전 블록 할당, 직후 블록이 가용인 경우.
        remove_free_block(NEXT_BLKP(ptr));
        size += GET_SIZE(HDRP(NEXT_BLKP(ptr)));
        PUT(HDRP(ptr), PACK(size, 0));
        PUT(FTRP(ptr), PACK(size, 0));
    } else if (!prev_alloc && next_alloc) {
        // case3 - 직전 블록 가용, 직후 블록이 할당된 경우.
        remove_free_block(PREV_BLKP(ptr));
        size += GET_SIZE(HDRP(PREV_BLKP(ptr)));
        PUT(FTRP(ptr), PACK(size, 0)); 
        PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
        ptr = PREV_BLKP(ptr);   // 블록 포인터를 직전 블록으로 옮긴다.
    } else {
        // case4 - 직전, 직후 블록이 모두 가용인 경우.
        remove_free_block(PREV_BLKP(ptr));
        remove_free_block(NEXT_BLKP(ptr));
        size += GET_SIZE(HDRP(PREV_BLKP(ptr))) + GET_SIZE(FTRP(NEXT_BLKP(ptr)));
        PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(ptr)), PACK(size, 0));
        ptr = PREV_BLKP(ptr);   // 블록 포인터를 직전 블록으로 옮긴다.
    }
    add_free_block(ptr);
    return ptr; // 최종 가용 블록 주소를 반환한다.
}

static void *find_fit(size_t adjust_size)
{
    void *bp = free_listp;

    while (bp != NULL) {
        if ((adjust_size <= GET_SIZE(HDRP(bp)))) {
            return bp;
        }
        bp = GET_SUCC(bp);
    }
    return NULL;
}

static void place(void *ptr, size_t adjust_size)
{
    remove_free_block(ptr);

    size_t current_size = GET_SIZE(HDRP(ptr));

    if ((current_size - adjust_size) >= (2 * DSIZE)) {
        PUT(HDRP(ptr), PACK(adjust_size, 1));
        PUT(FTRP(ptr), PACK(adjust_size, 1));

        PUT(HDRP(NEXT_BLKP(ptr)), PACK((current_size - adjust_size), 0));
        PUT(FTRP(NEXT_BLKP(ptr)), PACK((current_size - adjust_size), 0));
        add_free_block(NEXT_BLKP(ptr));
    } else {
        PUT(HDRP(ptr), PACK(current_size, 1));
        PUT(FTRP(ptr), PACK(current_size, 1));
    }
}