#4 malloc-lab 동적 할당기 구현

-카네기 멜론 대학교(CMU)의 malloc-lab 동적할당기 구현

Implicit Allocator & Explicit Allocator

Implicit Allocator

Implicit Allocator는 언제 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 반환하는지를 할당기가 스스로 검출할 수 있다. 가장 잘 알려진 예로는 가비지 컬렉터(Garbage Collector, GC)가 있다. 가비지 컬렉터는 자동으로 사용하지 않는 블록들을 반환시켜주며, 이 작업을 가비지 컬렉션이라고 부른다.

Explicit Allocator

Explicit Allocator는 할당기가 스스로 블록을 반환하지 않으며, 할당된 메모리 블록을 명시적으로 직접 해제 해주어야 하는 할당기이다. 가장 잘 알려진 예로는 C 표준 라이브러리의 malloc패키지가 이에 해당한다. malloc을 이용해 명시적으로 메모리 공간을 확보한 뒤, free를 이용해 명시적으로 해당 공간을 해제해주어야 한다.

우리가 이번에 malloc-lab에서 구현할 할당기는 이 중 Explicit Allocator에 해당한다. 즉 c 표준 라이브러리의 malloc 라이브러리를 직접 구현한다고 이해하면 될 것 같다.

가용 리스트

가용 리스트에는 Implicit free list, Explicit free list, Seglist, Buddy system 등 다양한 리스트가 있지만, 이 포스팅에서는 Implicit free list에 대해서 설명을 이어가려 한다.

Header, Payload, Padding으로 구성되어 있으며 각각의 역할은 다음과 같다.

• Header : 메모리 블록의 크기, 할당 여부에 대한 값을 가짐
• Payload : 해당 블록에 저장되는 데이터를 가지고 있음 (블록이 할당 됨 상태 일 경우에)
• Padding : 더블 워드(8byte) 정렬 제한 조건을 사용할 경우, 블록의 크기는 항상 8의 배수여야 하는데 이러한 제한 조건을 지키기 위해 추가되어 진다. 이는 외부 단편화를 극복하는 전략 중 하나이기도 하다.

Implicit free list 밑의 가로를 블록으로 나눈 그림은 메모리 블록과 힙 구조를 추상화해서 나타낸 그림이다. 각 블록 한 칸은 1 word(4byte)를 의미하며, 더블 워드(8byte) 정렬 제한 조건에 따라 Implicit free list가 힙에 올라간 상태를 보여준다.

할당한 블록을 배치 하는 방법

프로그램이 k바이트의 블록을 요청한다면, 동적 할당기는 요청한 블록보다 크거나 같은 크기를 갖는 가용 상태(할당 되지 않은)의 블록을 리스트에서 검색한다. 할당기가 이 검색을 수행하는 방법은 여러가지가 있는데, 보편적으로 많이 사용되는 방법들은 아래와 같다.

1. First fit리스트를 처음부터 탐색해서 크기가 맞는 첫 번째 가용 블록을 선택한다.
2. Next fitFirst fit과 유사하지만, 검색을 리스트의 처음에서 시작하는 대신에 검색이 종료된 지점에서 검색을 시작한다.
3. Best fit모든 가용 블록을 검사하여 크기가 맞는 블록 중 가장 작은 블록을 선택한다.

First fit은 구현하기 간단하며, 리스트의 마지막에 가장 큰 가용 블록을 갖는 블록들을 남겨 놓는다는 장점이 있다. 그러나 리스트의 앞 부분에 작은 가용 블록들을 남겨둔다는 단점이 있다.

Next fit은 이전 검색에서 가용 블록을 발견했다면, 다음 검색에서는 리스트의 나머지 부분에서 원하는 블록을 찾을 가능성이 높다는 아이디어에서 First fit의 대안으로 고안되었다. Next fit은 일반적으로 First fit에 비해서 리스트의 앞 부분이 작은 크기의 블록들로 구성되면 First fit보다 매우 빠른 속도를 보이지만, 일부 연구에서는 Next fit이 First fit보다 최악의 메모리 이용도를 보인다는 것으로 밝혀졌다고 한다.

Best fit은 앞서 설명한 First fit과 Next fit보다 더 좋은 메모리 이용도를 갖는다. 그러나 힙을 완전히 검색해서 최소 크기의 가용 블록을 찾는다는 점에서 시간적인 단점을 갖는다. 이러한 Best fit의 단점을 개선하여 사용할 수 있는 리스트가 segregated free list(seglist)이다.

경계 태그를 이용한 블록 연결

우리는 앞서 Implicit free list의 블록 구조를 알아보았다. 그렇다면 할당기에서 서로 다른 블록은 어떻게 연결될 수 있을까? 만약 할당 해제하려는 블록을 현재 블록(current block)이라고 해보자.

현재 블록과 다음 블록(next block)을 하나의 블록으로 연결하는 것은 현재 블록의 헤더의 사이즈 값을 읽어 현재 위치에서 더한다면, 그 위치는 다음 블록의 헤더 위치가 될 것이다. 여기서 다음 블록이 가용 가능한지 다음 블록의 헤더를 읽어 판단한 뒤 연결해주면 상수 시간 내에 블록을 연결할 수 있다.

그렇다면 다음 블록이 아닌 이전 블록(previous block)을 현재 블록과 연결하려고 한다면, 어떻게 해야할까? 블록의 헤더에 크기와 가용 여부에 대한 정보가 있는 상태이기 때문에, 이전 블록이 가용 가능한지 판단하기 위해서는 이전 블록의 헤더 위치를 찾아야한다. 그러나 현재 블록(current block)에서 이전 블록의 헤더 위치가 어디인지 판단할 수 있는 방법은 다시 처음부터 탐색해서 해당 헤더에 도달 했을때 사이즈를 측정하는 방법밖에 없다(=이전 블록의 크기가 얼마인지 알 수 없기 때문에, 현재 블록 기준에서 이전 블록의 헤더가 어디에 위치해있는지 알 방법이 없다.). 따라서 이 방법은 선형 탐색시간이 걸리게된다.

이러한 문제를 해결하고자 각 블록의 끝 부분에 헤더와 동일한 정보(사이즈/가용여부)를 가지는 풋터(footer)라는 1워드 크기의 공간을 할당해준다. 그리고 이를 경계 태그라고 부른다.

풋터를 추가함으로써 현재 블록과 이전 블록을 연결할 때, 우리는 현재 블록의 헤더의 바로 앞이 이전 블록의 풋터이며, 이 풋터를 통해서 이전 블록의 크기를 알 수 있고, 이전 블록의 시작 위치를 알 수 있음이 보장된다.

이를 통해 다음 블록뿐 아니라 이전 블록과의 연결도 상수 시간 내에 완료할 수 있게 된다. 경계 태그를 포함한 implicit free list의 구조는 아래와 같다.

이 블록이 heep에 할당 된 경우를 추상화 해본다면

여기서 프롤로그 블록(Prologue header, Prologue footer)과 에필로그 블록(Epilogue header)은 각각 힙의 시작과 끝을 알려주는 블록이며, 연결 과정 구현에 있어서 가장자리 조건을 없애주기 위한 속임수이다.

C언어 malloc 구현

전체 코드 : https://github.com/saint6839/jungle-week-06/blob/main/mm_first_fit.c

코드는 first fit, next fit, best fit, worst fit 등의 fit 방법들 중에서 가장 간단한 first fit 방법을 포스팅하기로 하였다.

매크로 선언

먼저 구현에 있어서 반복되는 작업을 편리하게 처리하기 위해 매크로를 선언하였다.

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

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

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

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

// 특정 주소 p에 해당하는 블록의 사이즈와 가용 여부를 확인함
#define GET_SIZE(p) ((GET(p) >> 1) << 1)
#define GET_ALLOC(p) (GET(p) & 0x1)

// 특정 주소 p에 해당하는 블록의 헤더와 풋터의 포인터 주소를 읽어온다
#define HDRP(ptr) ((char *)(ptr)-WSIZE)
#define FTRP(ptr) ((char *)(ptr) + GET_SIZE(HDRP(ptr)) - DSIZE)

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

// 전역 변수 및 함수 선언
static void *heap_listp;
static void *extend_heap(size_t words);
static void *coalesce(void *ptr);
static void *find_fit(size_t asize);
static void place(void *ptr, size_t asize);

mm_init() - 메모리 영역 초기화

/*
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
    // mem_sbrk: 힙 영역을 incr(0이 아닌 양수) bytes 만큼 확장하고, 새로 할당된 힙 영역의 첫번째 byte를 가리키는 제네릭 포인터를 리턴함
    /* 비어있는 heap을 만든다.*/
    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
    {
        return -1;
    };

    PUT(heap_listp, 0);                            // Alignment padding
    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
    heap_listp += (2 * WSIZE);

    // 힙 영역을 확장하는 함수. 
    // 두 가지 경우에 호출된다.
    // (1) 힙이 초기화 될때 (2) mm_malloc이 적당한 맞춤fit을 찾지 못했을 때
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
    {
        return -1;
    }

    return 0;
}

먼저 heap_listp = mem_sbrk(4 * WSIZE) 를 통해 초기 힙 영역의 크기를 할당하게 된다. 이 함수는 힙 영역을 매개 변수로 받은 byte 크기 만큼 확장 한 뒤, 확장 되기 전의 시작점의 위치를 return 값으로 반환한다. 이 반환값은 heap_listp 변수에 담기게 되고 이때까지의 그림은 아래와 같다.

이후 코드에서 extend_heap()이 호출되기 전까지의 힙 영역의 모습을 그려보면 아래와 같다.

4워드 크기 만큼 힙 영역 공간을 확보했고, 각각의 주소에 1워드(4byte) 간격으로 패딩, 프롤로그 헤더, 프롤로그 풋터, 에필로그 헤더를 할당하였다. 이후 heap_listp를 2워드(8byte) 만큼 뒤로 보내서 위와 같은 그림이 그려지게 되었다.

extend_heap - 힙 영역 확장

최초 4워드의 프롤로그, 에필로그 블록이 초기화 된 이후에 extend_heap() 함수가 호출되어 초기 힙 영역이 할당되게 된다. 코드를 먼저 보고 어떤 과정으로 힙이 확장 되는지 그림을 통해 알아보자.

/* 아래와 같은 경우에 호출 될 수 있다.
1. 힙이 초기화 될 때
2. mm_malloc()이 적당한 맞춤 fit을 찾지 못하였을 때
정렬을 유지하기 위해 extend_heap()은 요청한 크기를 인접 2워드의 배수(8의 배수)로 반올림하며,
그 후에 메모리 시스템으로 부터 추가적인 힙 공간을 요청한다.
*/
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;

    /* 할당되지 않은 free 상태인 블록의 헤더/풋터와 에필로그 헤더를 초기화한다 */
    PUT(HDRP(ptr), PACK(size, 0));         // free 블록의 header
    PUT(FTRP(ptr), PACK(size, 0));         // free 블록의 footer
    PUT(HDRP(NEXT_BLKP(ptr)), PACK(0, 1)); // new epilogue header

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

words 값으로는 CHUNKSIZE / 4의 값인 1024가 들어오게 된다. 이 값은 size에서 짝수 갯수의 워드인지 판단하고, 짝수 이기 때문에 words * WSIZE;연산을 한 1024 * 4 = 4096이 size의 값으로 할당된다.

이후 ptr = mem_sbrk(size)를 수행한 뒤의 모습을 그림으로 표현하면 아래와 같다.

이전 mm_init()에서 4워드 만큼 증가 시킨 위치 주소 16에서 mem_sbrk(4096)을 수행하였기 때문에, 반환 값으로 증가의 시작점인 16이 반환 되었고, 이 값이 포인터 변수 *ptr에 담기게 되었다. 이후 코드를 따라 진행되는 과정을 그림으로 그려보면 아래와 같다.

앞서 프롤로그 블록은 힙의 시작을 알리고 에필로그 헤더는 힙의 끝을 알린다고 했었다. 그렇다면, 동적으로 할당되는 메모리 블록들은 프롤로그 블록과 에필로그 헤더 사이에서 할당이 이루어질것이다. 그 그림이 바로 방금 위에서 본 그림이라고 이해할 수 있다.

이 부분을 이해하는데 조금 시간이 걸렸었는데, 개념적으로는 프롤로그 블록과 에필로그 헤더 사이에 들어온다는것을 인지하고 있었지만, 내가 예상한 코드 구현과는 조금 달라서 헤맸었던것 같다. 코드 베이스로 설명을 해보면, 둘 사이에 메모리 공간이 생긴다기보다는 기존 에필로그 헤더의 위치가 크기/가용 여부 값이 포함된 블록 헤더로 새롭게 초기화되고 블록의 끝에 풋터가 초기화 된 뒤, 풋터의 끝에 새롭게 에필로그 헤더를 할당 해주는 것이다.

이를 결과적으로 보면 프롤로그 블록과 에필로그 헤더 사이에 공간을 밀어 넣는 것이라고 볼 수 있다.

이렇게 초기화를 이해했다면 나머지 함수들은 비교적 쉽게 따라가볼 수 있을 것이다.

mm_malloc - 동적 메모리 할당

/*
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
void *mm_malloc(size_t size)
{
    size_t asize;
    size_t extendsize;
    char *ptr;

    /* 의미 없는 요청 처리 안함 */
    if (size == 0)
    {
        return NULL;
    }
    /* examle)
       만약 payload에 넣으려고하는 데이터가 2byte라면 header(4byte) + footer(4byte) + payload(2byte) = 10byte 이지만, 더블워드 정렬 조건을 충족시키기 위해서 패딩 6byte를 추가해야한다. 따라서 총 16byte의 블록이 만들어지는데 이 과정을 계산하는 식이 아래 식이다.
   */
    if (size <= DSIZE)
    {
        asize = 2 * DSIZE; // 헤더 4byte, 풋터 4byte + 그리고 나머지 8byte가 데이터 들어올 공간임
    }
    else
    {
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
    }

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

    /* 리스트에 들어갈 수 있는 free 리스트가 없을 경우, 메모리를 확장하고 블록을 배치한다 */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((ptr = extend_heap(extendsize / WSIZE)) == NULL)
        return NULL;
    place(ptr, asize);

    return ptr;
}

// 메모리 영역에 메모리 블록을 위치시키는 함수
static void place(void *ptr, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(ptr));

    // 블록 내의 할당 부분를 제외한 나머지 공간의 크기가 더블 워드 이상이라면, 해당 블록의 공간을 분할한다.
    if ((csize - asize) >= (2 * DSIZE))
    {
        PUT(HDRP(ptr), PACK(asize, 1));
        PUT(FTRP(ptr), PACK(asize, 1));
        ptr = NEXT_BLKP(ptr);
        PUT(HDRP(ptr), PACK(csize - asize, 0));
        PUT(FTRP(ptr), PACK(csize - asize, 0));
    }
    // 블록 내의 할당 부분을 제외한 나머지 공간의 크기가 2 * 더블 워드(8byte)보다 작을 경우에는, 그냥 해당 블록의 크기를 그대로 사용한다
    else 
    {
        
        PUT(HDRP(ptr), PACK(csize, 1));
        PUT(FTRP(ptr), PACK(csize, 1));
    }
}

//first fit
static void *find_fit(size_t asize)
{
    void *ptr;

    // 에필로그 헤더(힙의 끝) 까지 탐색한다
    for (ptr = heap_listp; GET_SIZE(HDRP(ptr)) > 0; ptr = NEXT_BLKP(ptr))
    {
        // 할당 X and 여유 공간의 크기가 할당 할 크기보다 넉넉할 경우에만
        if (!GET_ALLOC(HDRP(ptr)) && (asize <= GET_SIZE(HDRP(ptr))))
        {
            return ptr;
        }
    }
    return NULL;
}

mm_malloc 함수는 우리가 알고 있는 malloc 함수와 거의 유사한 기능을 수행한다. 여기서 짚어볼 점은 먼저 이 부분이 될 것 같다.

/* examle)
   * 만약 payload에 넣으려고하는 데이터가 2byte라면 header(4byte) + footer(4byte) + payload(2byte) = 10byte 이지만, 더블워드 정렬 조건을 충족시키기 위해서 패딩 6byte를 추가해야한다. 따라서 총 16byte의 블록이 만들어지는데 이 과정을 계산하는 식이 아래 식이다.
   */
    if (size <= DSIZE)
    {
        asize = 2 * DSIZE; // 헤더 4byte, 풋터 4byte + 그리고 나머지 8byte가 데이터 들어올 공간임
    }
    else
    {
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
    }

여기서 size를 DSIZE를 기준으로 분기를 나누어준 이유가 무엇일까? 간단하게 말로 설명해보면, 우리는 메모리 블록의 시작과 끝을 헤더와 풋터를 이용해 구분하고 있다. 여기서 헤더와 풋터의 크기가 각각 1워드씩의 공간을 차지하기 때문에 블록은 우선 8byte부터 시작하게 되는것이다. 그리고 우리는 정렬 제한 조건을 더블 워드 정렬 제한 조건을 사용하기로 하였기 때문에 더블 워드의 크기인 8byte, 즉 8의 배수로 블록의 크기를 맞추어 주어야 한다.

따라서 헤더, 풋터의 기본 크기 8byte에 페이로드의 크기는 8의 배수를 만들기 위한 최소 크기 8byte 이상이 되어야 하므로, 16바이트인 2 * DSIZE 기준으로 분기를 나누어주고 있는 것이다. 이후 각 분기에 대한 설명은 코드 주석을 참고하면 된다.

이렇게 할당할 공간의 크기를 계산했다면, 할당할 위치를 찾아야 한다. 배치 위치에 대한 탐색 방법은 위에서 말했던 것처럼 first fit 방법을 사용하여, 앞에서부터 탐색한 뒤 배치 가능한 첫번째 블록에 메모리를 place() 함수를 이용해서 할당하게 된다.

place() 함수는 내부적으로 할당되는 공간이 넉넉하다면, 할당된 블록이 차지하는 공간을 제외한 나머지 공간을 새로운 가용 블록으로 선언해주게 된다. 이 또한 자세한 분기 조건에 대한 내용은 코드 주석을 참고하면 될 것 같다.

mm_realloc - 메모리 블록 크기 재할당

이 함수는 이미 할당된 메모리 블록의 크기를 늘리거나 줄일 경우 호출할 수 있는 함수이다.

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 
- 만약 ptr == NULL 이면, `mm_malloc(size)`과 동일한 동작을 수행한다.
- 만약 size가 0 이면, `mm_free(ptr)`와 동일한 동작을 수행한다.
- 만약 ptr != NULL 이면, 이전에 `mm_malloc()` 또는 `mm_realloc()`을 이용해 반환값이 존재하는 상태라고 볼 수 있다.
  이때 `mm_realloc()`을 호출하면, ptr이 가르키는 메모리 블록(이전 블록)의 메모리 크기가 바이트 단위로 변경된다. 이후 새 블록의 주소를 return 한다.
  새블록의 크기는 이전 ptr 블록의 크기와 최소한의 크기까지는 동일하고, 그 이외의 범위는 초기화되지 않는다. 예를 들어 이전 블록이 8바이트이고, 새 블록이 12바이트인 경우 첫 8바이트는 이전 블록과 동일하고 이후 4바이트는 초기화되지 않은 상태임을 의미한다.
 */
void *mm_realloc(void *ptr, size_t size)
{
    if (ptr == NULL) {
        return mm_malloc(size);
    }

    if (size == 0) {
        mm_free(ptr);
        return;
    } 

    void *new_ptr = mm_malloc(size);
    if (new_ptr == NULL) {
        return NULL;
    }
    size_t csize = GET_SIZE(HDRP(ptr));
    if (size < csize) { // 재할당 요청에 들어온 크기보다, 기존 블록의 크기가 크다면
        csize = size; // 기존 블록의 크기를 요청에 들어온 크기 만큼으로 줄인다.
    }
    memcpy(new_ptr, ptr, csize); // ptr 위치에서 csize만큼의 크기를 new_ptr의 위치에 복사함
    mm_free(ptr); // 기존 ptr의 메모리는 할당 해제해줌
    return new_ptr;
}

mm_realloc()의 의의는 기존 데이터를 유지한채로 메모리 블록의 크기를 변경한다는데 있다. 주의할 점은 크기를 재할당하려는 현재 블록의 다음 블록에 다른 메모리 블록이 이미 위치한 채로 블록의 크기를 변경할 경우 다음 블록의 위치들을 전부 밀어주어야 한다.

따라서 현재 위치에서 블록의 크기를 늘리는 것이 아닌 현재 위치의 블록의 내용들을 복사한 뒤, 메모리 영역의 크기를 늘린다. 이후 새로운 메모리 주소를 할당해주고, 기존의 메모리 주소는 할당 해제 시키는 과정을 통해서 메모리 블록 크기의 재할당이 이루어진다.

mm_free - 메모리 할당 해제

/*
 * mm_free - Freeing a block does nothing.
 */
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);
}

할당 해제는 비교적 간단하다. 매개변수로 들어온 주소 *ptr에 해당하는 위치의 블록 사이즈를 읽고, 해당 블록의 헤더와 풋터의 가용 여부를 0으로 바꾸어줌으로써 메모리 할당 해제 기능을 구현할 수 있다.

coalesce - 메모리 블록 연결(통합)

// 할당된 블록을 합칠 수 있는 경우 4가지에 따라 메모리 연결
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) 
    {
        return ptr;
    }
    // 다음 블록이 이미 할당 되어 있고, 이전 블록이 free 라면
    else if (prev_alloc && !next_alloc)
    {
        size += GET_SIZE(HDRP(NEXT_BLKP(ptr)));
        PUT(HDRP(ptr), PACK(size, 0));
        PUT(FTRP(ptr), PACK(size, 0));
    }
    // 다음 블록이 이미 할당 되어 있고, 이전 블록이 free 라면
    else if (!prev_alloc && next_alloc) 
    {
        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);
    }
    // 이전과 다음 블록이 모두 free일 경우
    else 
    {
        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);
    }
    return ptr;
}

포스팅의 앞 부분에서 말했던 경계 조건을 이용한 연결의 내용이 이 부분의 구현에 해당한다. 메모리를 보다 효율적으로 사용하기 위해, 현재 블록을 기준으로 이전 블록과 이후 블록의 가용 여부를 판단한다.

만약 가용 가능하다면, 현재 블록과 가용 가능한 블록을 합치게 된다. 합치는 과정은 아래 이미지를 참고하자. 아래 그림에서 a는 할당 됨을 의미하고, f는 가용 가능한 상태를 의미한다. 그림을 통해 이전, 다음 블록의 가용 여부에 따라 헤더, 풋터의 크기의 변화를 이해하고, 위 코드를 보면 이해하는데 도움이 된다.

https://velog.io/@saint6839/C언어-Malloc-lab-동적-할당기-구현하기