[CS:APP] Explicit Free Lists 구현

 

1. Explicit Free Lists 구현해보기

 

 안녕하세요! FlyDuck Dev🦢입니다.

오늘은 Explicit Free Lists를 구현한 것을 토대로, 주요 로직 사항을 정리해보고자 합니다. 묵시적 가용 리스트와 다른 주요한 차이점은

(1) 포인터 2개가 추가되고, 그만큼 프리 블록의 최소크기가 커진다는 점,

(2) coalesced block을 free list의 맨 앞에 삽입해야 한다는 점입니다(LIFO 순서로 리스트를 유지하는 방법을 취하였기 때문)

 

 

2. Implicit Free Lists  vs Explicit Free Lists 

암시적 프리 리스트는 구현이 비교적 간단하지만, 블록 할당 시간이 힙 블록의 총 수에 선형적으로 비례하기 때문에, 일반적인 목적의 할당자에 적합하지 않습니다. (하지만 미리 블록 수가 적다는 것이 알려진 특수 목적의 할당자에서는 괜찮을 수 있습니다.)

 

더 나은 접근 방법은 free 블록을 명시적인 데이터 구조로 구성하는 것입니다. free 블록의 본문은 프로그램에서 필요하지 않기 때문에, 데이터 구조를 구현하는 포인터는 free 블록의 본문 내부에 저장될 수 있습니다.

 

예를 들어, 각 자유 블록에 선행자(pred)와 후속자(succ) 포인터를 포함하여 이중 연결 자유 리스트로 힙을 구성할 수 있습니다. 

 

암시적 프리 리스트 대신 이중 연결 리스트를 사용하면, 첫 번째 적합 할당 시간이 블록 총 수에 선형적인 것에서 자유 블록의 수에 선형적인 것으로 감소됩니다. 그러나 블록을 해제하는 시간은 자유 리스트에서 블록을 정렬하는 정책에 따라 선형적이거나 상수적일 수 있습니다.

일반적으로 명시적 리스트의 단점은 자유 블록이 필요한 모든 포인터, 헤더 및 (가능한 경우) 푸터를 포함할 수 있는 충분한 크기여야 한다는 것입니다. 이로 인해 더 큰 최소 블록 크기와 내부 단편화 가능성이 증가합니다.

 

3. 구현방법 2가지

(1)

새롭게 해제된 블록을 리스트의 시작 부분에 삽입하여 나중에 들어온 것이 먼저 나가는 (LIFO) 순서로 리스트를 유지하는 것입니다. LIFO 정렬과 첫번째 적합 정책을 사용하면, 할당자는 가장 최근에 사용된 블록을 먼저 검사합니다. 이 경우, 블록을 해제하는 데 상수 시간이 걸릴 수 있습니다. 경계 태그가 사용되면, 병합도 상수 시간에 수행될 수 있습니다.

(2)

다른 방법은 각 블록의 주소가 그 다음 블록의 주소보다 작은 주소 순서로 리스트를 유지하는 것입니다. 이 경우, 블록 해제에는 적절한 선행자를 찾기 위해 선형 시간 검색이 필요합니다. 이 경우, 주소 순서대로 첫 번째 적합을 사용하는 것이 LIFO 순서대로 첫 번째 적합보다 메모리 활용도가 높아져서 가장 적합한 것에 가까워집니다.

 

4. 구현(LIFO 순서로 리스트를 유지)

 

기본 상수 및 매크로 정의

묵시적 가용리스트의 기본 매크로들에 추가로

(1) 선행, 후행 자유블록을 가르킬 포인터 두개를 추가 정의합니다.

(2) 또한 자유 블록의 최소 크기는 기본 헤더/푸터에 4바이트가 포함(페이로드 내에서 이전과 다음 자유 블록을 가리키는 두 개의 포인터를 위한 공간이 포함)되기 때문에, 첫 번째 자유 블록이 추가되기 전 자유 리스트의 초기 크기와 자유 블록의 최소 사이즈를 16으로 정의해주었습니다.

// CONSTANTS
#define ALIGNMENT         8         // memory alignment factor
#define WSIZE             4         // Size in bytes of a single word 
#define DSIZE             8         // Size in bytes of a double word
#define INITSIZE          16        // Initial size of free list before first free block added
#define MINBLOCKSIZE      16        /* Minmum size for a free block, includes 4 bytes for header/footer
                                       and space within the payload for two pointers to the prev and next
                                       free blocks */

#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define MAX(x, y) ((x) > (y)? (x) : (y))
#define PACK(size, alloc) ((size) | (alloc))
#define GET(p)        (*(size_t *)(p))
#define PUT(p, val)   (*(size_t *)(p) = (val))
#define GET_SIZE(p)  (GET(p) & ~0x1)
#define GET_ALLOC(p) (GET(p) & 0x1)
#define HDRP(bp)     ((void *)(bp) - WSIZE)
#define FTRP(bp)     ((void *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

#define NEXT_BLKP(bp) ((void *)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLKP(bp) ((void *)(bp) - GET_SIZE(HDRP(bp) - WSIZE))
#define NEXT_FREE_BLKP(bp)(*(void **)(bp))         //추가1
#define PREV_FREE_BLKP(bp)(*(void **)(bp + WSIZE)) //추가2

Creating the Initial Free List

 

static char *heap_listp = 0; /* Points to the start of the heap */

static char *free_listp = 0; /* Poitns to the frist free block */

 

포인터 2개를 만들어서 하나는 힙 리스트 전체를 가리키게 하고,

나머지 하나는 자유 블록 리스트를 가리키게 합니다. (1*WSIZE)의 간격 차이를 반영해줍니다.

static char *heap_listp = 0;  /* Points to the start of the heap */
static char *free_listp = 0;  /* Poitns to the frist free block */

int mm_init(void)
{
    // (32 bytes total)
    if ((heap_listp = mem_sbrk(INITSIZE+MINBLOCKSIZE)) == (void *)-1){
        return -1;
    }

    PUT(heap_listp, PACK(MINBLOCKSIZE, 1)); //PROLOGUE_HEADER
    PUT(heap_listp + (1*WSIZE), PACK(MINBLOCKSIZE, 0)); //FREE_HEADER

    PUT(heap_listp + (2*WSIZE), PACK(0, 0)); //NEXT_FREE_BLKP
    PUT(heap_listp + (3*WSIZE), PACK(0, 0)); //PREV_FREE_BLKP

    PUT(heap_listp + (4*WSIZE), PACK(MINBLOCKSIZE, 0)); //FREE_FOOTER
    PUT(heap_listp + (5*WSIZE), PACK(0, 1)); //에필로그 헤더 유지
    free_listp = heap_listp +WSIZE;

    return 0;
}

malloc

요청된 크기에 맞는 자유 블록이 있으면 해당 블록을 할당하고, 그렇지 않으면 힙을 확장하여 새로운 자유 블록을 생성하여 할당하는 역할

void *mm_malloc(size_t size) {
    if (size == 0) {
        return NULL;
    }

    size_t asize; /* Adjusted block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *bp;
    
    asize = MAX(ALIGN(size) + DSIZE, MINBLOCKSIZE);

    /* Search the free list for a fit */
    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }

    /* No fit found. Get more memory and place the block */
    extendsize = MAX(asize, MINBLOCKSIZE);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL) {
        return NULL;
    }
    place(bp, asize);
    return bp;
}

• 매개변수로 전달받은 size가 0이면 NULL을 반환합니다.
• asize 변수는 요청된 size를 조정한 값으로, ALIGN(size) + DSIZE와 MINBLOCKSIZE 중 더 큰 값을 선택하여 사용합니다. ALIGN(size)는 size를 워드(4바이트) 크기로 정렬한 값을 반환하며, DSIZE는 헤더와 푸터를 위한 8바이트를 의미합니다. 
• find_fit(asize) 함수를 호출하여 asize에 맞는 자유 블록을 검색합니다. 만약 자유 블록이 있다면 해당 블록을 할당하고 반환합니다.
• 자유 블록이 없다면, extend_heap 함수를 호출하여 힙을 확장합니다. extend_heap 함수는 힙을 확장한 후 새로운 자유 블록을 생성합니다.
• 생성된 자유 블록에 asize 크기의 블록을 할당하고 반환합니다.

mm_realloc, mm_free, extend_heap

Implicit Free Lists 의 구현과 동일합니다.

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

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));

    coalesce(bp);
}

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 = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
    copySize = GET_SIZE(HDRP(oldptr));
    //copySize = GET_SIZE(HDRP(oldptr))-2 *WSIZE - SIZE_T_SIZE;
    if (size < copySize){
        copySize = size;
    }
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

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));         /* Free block header */
    PUT(FTRP(bp), PACK(size, 0));         /* Free block footer */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */

    return coalesce(bp);
}

find_fit

요청된 크기(size)에 맞는 빈 블록을 검색하는 함수입니다. 현재 할당되지 않은 free_listp부터 시작하여 모든 빈 블록을 반복하며, 크기가 적절하고 할당되어 있지 않은 블록을 찾으면 해당 블록을 반환합니다. 빈 블록이 없을 경우 NULL을 반환합니다.

static void *find_fit(size_t size)
{
  void *bp;

  for (bp = free_listp; GET_ALLOC(HDRP(bp)) == 0; bp = NEXT_FREE_BLKP(bp)) {
    if (!GET_ALLOC(HDRP(bp)) && (size <= GET_SIZE(HDRP(bp))))
      return bp; 
  }
  return NULL; 
}

coalesce

 주어진 블록(bp)이 coalesced 된 이후 free list에 삽입하는 역할을 하는 함수입니다.

Coalescing은 인접한 free 블록을 합치는 과정으로, 주어진 블록과 그 주변 블록의 할당 여부를 검사하여, 4가지 경우에 따라 알맞은 병합 작업을 수행하고, 이후 coalesced block을 free list의 맨 앞에 삽입합니다.

static void *coalesce(void *bp) {
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))) || PREV_BLKP(bp) == bp;
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));
    // if (prev_alloc && next_alloc) {  // case 1
    //     return bp;
    // } //if~ else if 문 아래로 빠짐
    if (prev_alloc && !next_alloc) {  // case 2
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        remove_from_list(NEXT_BLKP(bp)); // 다음 블록 제거
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    } else if (!prev_alloc && next_alloc) {  // case 3
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        remove_from_list(PREV_BLKP(bp)); // 이전 블록 제거
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    } else if (!prev_alloc && !next_alloc) { // case 4
    size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        remove_from_list(PREV_BLKP(bp)); // 이전 블록 제거
        remove_from_list(NEXT_BLKP(bp)); // 다음 블록 제거
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    // "coalesced block"을 "free list"의 맨 앞에 삽입
    NEXT_FREE_BLKP(bp) = free_listp; //새로운 노드의 NEXT_FREE_BLKP 필드를 현재 free list의 첫 번째 노드의 주소로 설정
    PREV_FREE_BLKP(free_listp) = bp; //현재 free list의 첫 번째 노드의 PREV_FREE 필드를 새로운 노드의 주소로 설정
    PREV_FREE_BLKP(bp) = NULL; //최상단
    free_listp = bp; //전역 변수 free_listp를 새로운 노드의 주소로 설정하여, free list의 첫 번째 노드를 업데이트
    return bp;
}

함수의 첫 번째 라인에서는 prev_alloc과 next_alloc을 계산합니다. prev_alloc은 이전 블록의 할당 여부를 나타내고, next_alloc은 다음 블록의 할당 여부를 나타냅니다. 이 값을 계산하는 이유는 각각의 coalescing case를 판단하기 위함입니다.

 

case 1은 이전 블록과 다음 블록이 모두 할당된 경우입니다. 이 경우 블록을 coalesce할 필요가 없습니다.

case 2는 이전 블록은 할당되지 않았고, 다음 블록은 할당된 경우입니다. 

case 3는 이전 블록이 할당된 경우이고, 다음 블록이 할당되지 않은 경우입니다.

case 4는 이전 블록과 다음 블록이 모두 할당되지 않은 경우입니다. 

이후 coalesced된 블록(bp)을 free list의 맨 앞에 삽입합니다. 이를 위해, 새로운 노드(bp)의 NEXT_FREE_BLKP 필드를 현재 free list의 첫 번째 노드의 주소로 설정하고, 현재 free list의 첫 번째 노드의 PREV_FREE_BLKP 필드를 새로운 노드의 주소로 설정합니다. 새로운 노드의 PREV_FREE_BLKP 필드는 NULL을 가리키게 됩니다. 마지막으로, 전역 변수인 free_listp를 새로운 노드의 주소로 설정하여 free list의 첫 번째 노드를 업데이트합니다.

 

remove_from_list

이 함수는 인자로 받은 free block인 removed를 free list에서 제거하는 기능을 합니다.

//* remove_freeblock - Removes the given free block pointed to by bp from the free list.
static void remove_from_list(void *removed)
{
    //제거할 때 연결리스트 작업 느낌으로
    if(removed == heap_listp) return;
    //removed->llink->rlink = removed->rlink;
    if (PREV_FREE_BLKP(removed)){
        NEXT_FREE_BLKP(PREV_FREE_BLKP(removed)) = NEXT_FREE_BLKP(removed);
    } else {
        free_listp = NEXT_FREE_BLKP(removed);
    }
    //removed->rlink->llink = removed->llink;
    if (NEXT_FREE_BLKP(removed)){
        PREV_FREE_BLKP(NEXT_FREE_BLKP(removed)) = PREV_FREE_BLKP(removed);
    }
}

place

이 함수는 주어진 블록 bp에 대해 할당(place)을 수행합니다. 할당할 크기 asize를 받아서, 만약 bp의 크기가 asize보다 크다면, 블록을 분할(split)하고(분할 된 블록은 할당되고, 남은 부분은 다시 빈 블록으로 처리됩니다), 그렇지 않으면 블록 전체를 사용하여 할당합니다. 또한 할당이 완료된 블록은 remove_from_list 함수를 사용하여 빈 블록 리스트에서 제거됩니다.

static void place(void *bp, size_t asize) {
    // Gets the total size of the free block 
    size_t csize = GET_SIZE(HDRP(bp));

    // Case 1: Splitting is performed 
    if ((csize - asize) >= (MINBLOCKSIZE)) {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        remove_from_list(bp);
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize - asize, 0));
        PUT(FTRP(bp), PACK(csize - asize, 0));
        coalesce(bp);
    } 
    else { // Case 2: Splitting not possible. Use the full free block 
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
        remove_from_list(bp);
    }
}

5. 전체 코드

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

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

team_t team = {
    "fly-Walker",
    "flyduck-dev🕊",
    "fantasy coding",
    "",
    ""
};

// CONSTANTS
#define ALIGNMENT         8         // memory alignment factor
#define WSIZE             4         // Size in bytes of a single word 
#define DSIZE             8         // Size in bytes of a double word
#define INITSIZE          16        // Initial size of free list before first free block added
#define MINBLOCKSIZE      16        /* Minmum size for a free block, includes 4 bytes for header/footer
                                       and space within the payload for two pointers to the prev and next
                                       free blocks */

#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define MAX(x, y) ((x) > (y)? (x) : (y))
#define PACK(size, alloc) ((size) | (alloc))
#define GET(p)        (*(size_t *)(p))
#define PUT(p, val)   (*(size_t *)(p) = (val))
#define GET_SIZE(p)  (GET(p) & ~0x1)
#define GET_ALLOC(p) (GET(p) & 0x1)
#define HDRP(bp)     ((void *)(bp) - WSIZE)
#define FTRP(bp)     ((void *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

#define NEXT_BLKP(bp) ((void *)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLKP(bp) ((void *)(bp) - GET_SIZE(HDRP(bp) - WSIZE))
#define NEXT_FREE_BLKP(bp)(*(void **)(bp))
#define PREV_FREE_BLKP(bp)(*(void **)(bp + WSIZE))

// PROTOTYPES
static void *extend_heap(size_t words);
static void *find_fit(size_t size);
static void *coalesce(void *bp);
static void place(void *bp, size_t asize);
static void remove_from_list(void *bp);

static char *heap_listp = 0;  /* Points to the start of the heap */
static char *free_listp = 0;  /* Poitns to the frist free block */

int mm_init(void)
{
    // (32 bytes total)
    if ((heap_listp = mem_sbrk(MINBLOCKSIZE)) == (void *)-1){
        return -1;
    }

    PUT(heap_listp, PACK(MINBLOCKSIZE, 1)); //PROLOGUE_HEADER
    PUT(heap_listp + (1*WSIZE), PACK(MINBLOCKSIZE, 0)); //FREE_HEADER

    PUT(heap_listp + (2*WSIZE), PACK(0, 0)); //NEXT_FREE_BLKP
    PUT(heap_listp + (3*WSIZE), PACK(0, 0)); //PREV_FREE_BLKP

    PUT(heap_listp + (4*WSIZE), PACK(MINBLOCKSIZE, 0)); //FREE_FOOTER
    PUT(heap_listp + (5*WSIZE), PACK(0, 1)); //에필로그 헤더 유지
    free_listp = heap_listp +WSIZE;
    return 0;
}

void *mm_malloc(size_t size) {
    if (size == 0) {
        return NULL;
    }

    size_t asize; /* Adjusted block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *bp;
    
    asize = MAX(ALIGN(size) + DSIZE, MINBLOCKSIZE);

    /* Search the free list for a fit */
    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }

    /* No fit found. Get more memory and place the block */
    extendsize = MAX(asize, MINBLOCKSIZE);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL) {
        return NULL;
    }
    place(bp, asize);
    return bp;
}

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

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));

    coalesce(bp);
}

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 = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
    copySize = GET_SIZE(HDRP(oldptr));
    //copySize = GET_SIZE(HDRP(oldptr))-2 *WSIZE - SIZE_T_SIZE;
    if (size < copySize){
        copySize = size;
    }
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

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));         /* Free block header */
    PUT(FTRP(bp), PACK(size, 0));         /* Free block footer */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */

    return coalesce(bp);
}

static void *find_fit(size_t size)
{
  void *bp;

  for (bp = free_listp; GET_ALLOC(HDRP(bp)) == 0; bp = NEXT_FREE_BLKP(bp)) {
    if (!GET_ALLOC(HDRP(bp)) && (size <= GET_SIZE(HDRP(bp))))
      return bp; 
  }
  return NULL; 
}


//* remove_freeblock - Removes the given free block pointed to by bp from the free list.
static void remove_from_list(void *removed)
{
    //제거할 때 연결리스트 작업...
    if(removed == heap_listp) return;
    //removed->llink->rlink = removed->rlink;
    if (PREV_FREE_BLKP(removed)){
        NEXT_FREE_BLKP(PREV_FREE_BLKP(removed)) = NEXT_FREE_BLKP(removed);
    } else {
        free_listp = NEXT_FREE_BLKP(removed);
    }
    //removed->rlink->llink = removed->llink;
    if (NEXT_FREE_BLKP(removed)){
        PREV_FREE_BLKP(NEXT_FREE_BLKP(removed)) = PREV_FREE_BLKP(removed);
    }
}


static void *coalesce(void *bp) {
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))) || PREV_BLKP(bp) == bp;
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));
    // if (prev_alloc && next_alloc) {  // case 1
    //     return bp;
    // } //if~ else if 문 아래로 빠짐
    if (prev_alloc && !next_alloc) {  // case 2
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        remove_from_list(NEXT_BLKP(bp)); // 다음 블록 제거
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    } else if (!prev_alloc && next_alloc) {  // case 3
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        remove_from_list(PREV_BLKP(bp)); // 이전 블록 제거
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    } else if (!prev_alloc && !next_alloc) { // case 4
    size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        remove_from_list(PREV_BLKP(bp)); // 이전 블록 제거
        remove_from_list(NEXT_BLKP(bp)); // 다음 블록 제거
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    // "coalesced block"을 "free list"의 맨 앞에 삽입
    NEXT_FREE_BLKP(bp) = free_listp; //새로운 노드의 NEXT_FREE_BLKP 필드를 현재 free list의 첫 번째 노드의 주소로 설정
    PREV_FREE_BLKP(free_listp) = bp; //현재 free list의 첫 번째 노드의 PREV_FREE 필드를 새로운 노드의 주소로 설정
    PREV_FREE_BLKP(bp) = NULL; //최상단
    free_listp = bp; //전역 변수 free_listp를 새로운 노드의 주소로 설정하여, free list의 첫 번째 노드를 업데이트
    return bp;
}

static void place(void *bp, size_t asize) {
    // Gets the total size of the free block 
    size_t csize = GET_SIZE(HDRP(bp));

    // Case 1: Splitting is performed 
    if ((csize - asize) >= (MINBLOCKSIZE)) {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        remove_from_list(bp);
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize - asize, 0));
        PUT(FTRP(bp), PACK(csize - asize, 0));
        coalesce(bp);
    } 
    else { // Case 2: Splitting not possible. Use the full free block 
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
        remove_from_list(bp);
    }
}

 

+ 점수가 10점 정도 더 오른 코드

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

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

team_t team = {
    "fly-Walker",
    "flyduck-dev🕊",
    "fantasy coding",
    "",
    ""
};

// CONSTANTS
#define ALIGNMENT         8         // memory alignment factor
#define WSIZE             4         // Size in bytes of a single word 
#define DSIZE             8         // Size in bytes of a double word
#define CHUNKSIZE (1 << 12)
#define MINBLOCKSIZE      16

#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define MAX(x, y) ((x) > (y)? (x) : (y))
#define PACK(size, alloc) ((size) | (alloc))
#define GET(p)        (*(size_t *)(p))
#define PUT(p, val)   (*(size_t *)(p) = (val))
#define GET_SIZE(p)  (GET(p) & ~0x1)
#define GET_ALLOC(p) (GET(p) & 0x1)
#define HDRP(bp)     ((void *)(bp) - WSIZE)
#define FTRP(bp)     ((void *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

#define NEXT_BLKP(bp) ((void *)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLKP(bp) ((void *)(bp) - GET_SIZE(HDRP(bp) - WSIZE))
#define NEXT_FREE_BLKP(bp)(*(void **)(bp))
#define PREV_FREE_BLKP(bp)(*(void **)(bp + WSIZE))

// PROTOTYPES
static void *extend_heap(size_t words);
static void *find_fit(size_t size);
static void *coalesce(void *bp);
static void place(void *bp, size_t asize);
static void remove_from_list(void *bp);

static char *heap_listp = 0;  /* Points to the start of the heap */
static char *free_listp = 0;  /* Poitns to the frist free block */

int mm_init(void)
{
    // (32 bytes total)
    if ((heap_listp = mem_sbrk(6*WSIZE)) == (void *)-1){
        return -1;
    }

    PUT(heap_listp, 0);//정렬을 위한 패딩
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE * 2, 1)); //FREE_HEADER

    PUT(heap_listp + (2*WSIZE), PACK(0, 0)); //NEXT_FREE_BLKP
    PUT(heap_listp + (3*WSIZE), PACK(0, 0)); //PREV_FREE_BLKP

    PUT(heap_listp + (4*WSIZE), PACK(DSIZE * 2, 1)); //FREE_FOOTER
    PUT(heap_listp + (5*WSIZE), PACK(0, 1)); //에필로그 헤더 유지
    free_listp = heap_listp + (2*WSIZE);
    if (extend_heap(CHUNKSIZE/WSIZE) == NULL){
        return -1;
    }
    return 0;
}

void *mm_malloc(size_t size) {
    if (size == 0) {
        return NULL;
    }

    size_t asize; /* Adjusted block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *bp;
    // if (size <= 2 * DSIZE) {
    //    asize = 2 * DSIZE;
    // } else {
    //   asize = ALIGN(size)+ DSIZE;
    // }
    asize = MAX(ALIGN(size) + DSIZE, MINBLOCKSIZE);

    /* Search the free list for a fit */
    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }

    /* No fit found. Get more memory and place the block */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL) {
        return NULL;
    }
    place(bp, asize);
    return bp;
}

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

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));

    coalesce(bp);
}

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 = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
    copySize = GET_SIZE(HDRP(oldptr));
    //copySize = GET_SIZE(HDRP(oldptr))-2 *WSIZE - SIZE_T_SIZE;
    if (size < copySize){
        copySize = size;
    }
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

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));         /* Free block header */
    PUT(FTRP(bp), PACK(size, 0));         /* Free block footer */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */

    return coalesce(bp);
}

static void *find_fit(size_t size)
{
  void *bp;

  for (bp = free_listp; GET_ALLOC(HDRP(bp)) == 0; bp = NEXT_FREE_BLKP(bp)) {
    if (!GET_ALLOC(HDRP(bp)) && (size <= GET_SIZE(HDRP(bp))))
      return bp; 
  }
  return NULL; 
}


//* remove_freeblock - Removes the given free block pointed to by bp from the free list.
static void remove_from_list(void *removed)
{
    //제거할 때 연결리스트 작업...
    if(removed == heap_listp) return;
    //removed->llink->rlink = removed->rlink;
    if (PREV_FREE_BLKP(removed)){
        NEXT_FREE_BLKP(PREV_FREE_BLKP(removed)) = NEXT_FREE_BLKP(removed);
    } else {
        free_listp = NEXT_FREE_BLKP(removed);
    }
    //removed->rlink->llink = removed->llink;
    if (NEXT_FREE_BLKP(removed)){
        PREV_FREE_BLKP(NEXT_FREE_BLKP(removed)) = PREV_FREE_BLKP(removed);
    }
}


static void *coalesce(void *bp) {
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))) || PREV_BLKP(bp) == bp;
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));
    // if (prev_alloc && next_alloc) {  // case 1
    //     return bp;
    // } //if~ else if 문 아래로 빠짐
    if (prev_alloc && !next_alloc) {  // case 2
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        remove_from_list(NEXT_BLKP(bp)); // 다음 블록 제거
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    } else if (!prev_alloc && next_alloc) {  // case 3
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        remove_from_list(PREV_BLKP(bp)); // 이전 블록 제거
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    } else if (!prev_alloc && !next_alloc) { // case 4
    size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        remove_from_list(PREV_BLKP(bp)); // 이전 블록 제거
        remove_from_list(NEXT_BLKP(bp)); // 다음 블록 제거
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    // "coalesced block"을 "free list"의 맨 앞에 삽입
    NEXT_FREE_BLKP(bp) = free_listp; //새로운 노드의 NEXT_FREE_BLKP 필드를 현재 free list의 첫 번째 노드의 주소로 설정
    //printf("free_list: %x\n",free_listp);
    //printf("bp: %x\n",bp);
    //printf("free_list: %x\n",free_listp);
    PREV_FREE_BLKP(free_listp) = bp; //현재 free list의 첫 번째 노드의 PREV_FREE 필드를 새로운 노드의 주소로 설정
    PREV_FREE_BLKP(bp) = NULL; //최상단
    free_listp = bp; //전역 변수 free_listp를 새로운 노드의 주소로 설정하여, free list의 첫 번째 노드를 업데이트
    return bp;
}

static void place(void *bp, size_t asize) {
    // Gets the total size of the free block 
    size_t csize = GET_SIZE(HDRP(bp));

    // Case 1: Splitting is performed 
    if ((csize - asize) >= (MINBLOCKSIZE)) {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        remove_from_list(bp);
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize - asize, 0));
        PUT(FTRP(bp), PACK(csize - asize, 0));
        coalesce(bp);
    } 
    else { // Case 2: Splitting not possible. Use the full free block 
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
        remove_from_list(bp);
    }
}