Explicit Allocator란?

Implicit free list 는 모든 가용 리스트를 선형적으로 탐색하여 할당 가능한 주소공간을 찾으면, 요구에 맞는 사이즈의 메모리를 할당하였습니다. 당연하게도 모든 가용 블록을 탐색하기 때문에 탐색 시간이 전체 블록 수에 비례합니다.

반면 Explicit Allocator의 FILO(First In Last Out) 방식은 free blocks를 연결 리스트를 통해 관리하기 때문에 탐색 시간이 free blocks의 수에 비례하게 됩니다.

Basic macros

// Basic constants and macros
#define WSIZE               4                                                       // word = 4 byte
#define DSIZE               8                                                       // double word = 8 byte
#define CHUNKSIZE           (1 << 12)                                               // chunk size = 2^12 = 4096

#define MAX(x, y)           ((x) > (y) ? (x) : (y))                                 // x와 y 중 큰 값을 반환

// Pack a size and allocated bit into a word
#define PACK(size, alloc)   ((size) | (alloc))                                      // 크기 비트와 할당 비트를 통합해 header 및 footer에 저장할 수 있는 값 리턴

// Read and write a word at address p
#define GET(p)              (*(unsigned int *)(p))                                  // p가 참조하는 word를 읽어서 리턴 ((void*)라서 type casting 필요)
#define PUT(p, val)         (*(unsigned int *)(p) = (val))                          // p가 가리키는 word에 val 저장

// Read the size and allocated fields from address p
#define GET_SIZE(p)         (GET(p) & ~0x7)                                         // 사이즈 (뒤에 세자리 없어짐 -> 할당 여부와 무관한 사이즈를 반환)
#define GET_ALLOC(p)        (GET(p) & 0x1)                                          // 할당 여부 (마지막 한자리, 즉 할당 여부만 가지고 옴)

// Given block ptr bp, compute address of its header and footer
#define HDRP(bp)            ((char *)(bp) - WSIZE)                                  // 해당 블록의 header 주소를 반환 (payload 시작점인 bp에서 헤더 크기인 1 word를 뺀 값)
#define FTRP(bp)            ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)             // 해당 블록의 footer 주소를 반환 (payload 시작점인 bp에서 블록 사이즈를 더한 뒤 2 word를 뺀 값)

// Given block ptr bp, compute address of next and previous blocks
#define NEXT_BLKP(bp)       ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))       // 다음 블록의 bp를 반환 (현재 bp에서 해당 블록의 크기를 더해준 값)
#define PREV_BLKP(bp)       ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))       // 이전 블록의 bp를 반환 (현재 bp에서 이전 블록의 크기를 빼준 값 -> DSIZE를 빼야 이전 블록의 정보를 가져올 수 있음!!)

// Find Successor and Find Predecessor
#define FIND_SUCC(bp)       (*(void**)(bp+WSIZE))               // 후임자 (Next) 찾기
#define FIND_PRED(bp)       (*(void**)(bp))                     // 전임자 (Prev) 찾기

전역 변수

static char *heap_listp = NULL;         // 메모리 힙의 시작 주소
static char *free_listp = NULL;         // free_list에 대한 주소

Init mm_init(void)

int mm_init(void)
{
    // 초기 힙 생성
    if ((heap_listp = mem_sbrk(6 * WSIZE)) == (void *)-1) // 8워드 크기의 힙 생성, free_listp에 힙의 시작 주소값 할당(가용 블록만 추적)
        return -1;
        PUT(heap_listp, 0);                                         // Padding (8의 배수로 정렬하기 위해 패딩 블록 할당)
        PUT(heap_listp + (1 * WSIZE), PACK(2*DSIZE, 1));            // Prologue Header
        PUT(heap_listp + (2 * WSIZE), NULL);
        PUT(heap_listp + (3 * WSIZE), NULL);          
        PUT(heap_listp + (4 * WSIZE), PACK(2*DSIZE, 1));            // Prologue Footer
        PUT(heap_listp + (5 * WSIZE), PACK(0, 1));                  // Epilogue Header

    free_listp = heap_listp + DSIZE;

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

    return 0;
}

Implicit 구현과는 다르게 Free Block에 Predecessor,Successor 를 넣어줘야 하기 때문에 힙의 크기를 추가해줍니다.
mem_sbrk(4 * WSIZE)) --> mem_sbrk(6 * WSIZE))

add_free_block(void *bp)

static void add_free_block(void *bp) { 
    FIND_SUCC(bp) = free_listp;
    FIND_PRED(bp) = NULL;
    FIND_PRED(free_listp) = bp;
    free_listp = bp;
}

위와 같은 원리로 add_free_block 을 하게되면 새로운 블록은 연결 리스트의 첫 번째에 위치하게 됩니다.

remove_free_block(void *bp)

static void remove_free_block(void *bp) {
    if (bp == free_listp) {                 // 삭제하려는 bp가 리스트의 시작점이면.
        FIND_PRED(FIND_SUCC(bp)) = NULL;    // bp의 다음 지점에서의 Prev를 Null로 설정하면 해당 지점이 첫 지점이 됩니다.
        free_listp = FIND_SUCC(free_listp); // free_listp를 다음 칸으로 옮깁니다.
    }
    else {                                  // 중간지점 어딘가라면..
        FIND_SUCC(FIND_PRED(bp)) = FIND_SUCC(bp);
        FIND_PRED(FIND_SUCC(bp)) = FIND_PRED(bp);
     }
}

위와 같이 첫 번째 케이스, 두 번째 케이스로 분기하여 처리해줍니다.