malloc에 관한 모든 것(2)

100·2025년 4월 26일

C언어

목록 보기

4/6

malloclab 톺아보기

carnegie mellon 대학의 malloclab과제를 따라가며 malloc을 실제로 구현해보자.
CS:APP 9.9장의 내용을 참고하며 진행한다.
과제 명세의 pdf를 요약하면 아래와 같다.

개요

malloc, free, realloc을 직접 구현하여 사용자 정의 동적 메모리 할당기 만들 것이다.
모든 코드는 mm.c 파일 하나만 수정하면 되며, mm_init, mm_malloc, mm_free, mm_realloc 네 가지 함수를 반드시 정의해야 한다. 추가적인 헬퍼 함수들을 만들어도 된다.
프로그램은 memlib.c가 제공하는 메모리 관리 인터페이스만을 사용하여 힙 메모리를 다룬다. 따라서 시스템 콜(malloc, free, realloc, sbrk 등)을 직접 호출하는 것은 금지된다. 메모리 확장은 mem_sbrk를 사용한다.

구현 조건

초기화 (mm_init)
힙 영역을 설정하고 초기 블록을 준비한다.
할당 (mm_malloc)
요청된 크기 이상의 블록을 찾아 할당하고, 8바이트 정렬을 반드시 만족해야 한다.
해제 (mm_free)
주어진 포인터를 해제하고, 인접한 free 블록과 coalescing(병합) 해야 한다.
재할당 (mm_realloc)
블록 크기를 변경하며, 필요하면 새로운 블록을 할당하고 데이터를 복사한다.
특별히, ptr == NULL이면 malloc, size == 0이면 free로 처리해야 한다.

지원 함수 (memlib)

mem_sbrk(int n): 힙을 n바이트 확장한다.
mem_heap_lo(), mem_heap_hi(): 힙의 시작/끝 주소를 얻는다.
mem_heapsize(): 현재 힙의 크기를 구한다.

성능 평가 방식

정확성(20%) : 프로그램이 정상 동작해야 한다.
성능(35%) :
- 메모리 사용 효율(공간 활용률)
- 연산 처리 속도(throughput) 를 종합 평가한다.
스타일(10%) : 코드 구조화, 주석, heap checker 품질에 따라 점수를 준다.

성능 점수는 공간 활용률에 더 높은 가중치 (60%)를 준다. 속도만 빠르거나 메모리만 아끼는 걸로는 좋은 점수를 받을 수 없다. 두 가지를 모두 적절히 고려해야 한다.

Heap Consistency Checker

mm_check 함수를 작성** 하여 heap 상태를 점검해야 한다.
예를 들어:

free 블록들이 모두 올바르게 free 상태인지,
할당 블록끼리 겹치지 않는지,
free 블록들이 리스트에 제대로 포함되어 있는지 등을 확인할 수 있다.
개발 중에는 mm_check를 적극 활용하지만, 제출할 때는 호출을 제거해야 한다.

금지사항

시스템 호출 금지 (malloc, free, realloc, sbrk 직접 사용 불가)
글로벌 배열이나 구조체 금지 (단일 포인터/정수형 전역 변수만 허용)
mm.c 이외의 파일 수정 금지

힌트

초기에 malloc과 free만 통과시키는 것이 목표. (realloc은 나중)
8바이트 정렬을 신경쓸 것.
implicit free list 기반으로 먼저 구현하고, 이후 최적화 시 explicit free list 를 고려해볼 수 있다.
작은 테스트 케이스(short traces)로 먼저 디버깅하고, 이후 전체 trace를 돌린다.
디버거(gdb)나 mdriver -V 옵션을 활용해 문제를 추적한다.
포인터 연산은 매크로(macros)로 깔끔하게 관리한다.

요약 정리

항목	요약
수정할 파일	mm.c만 수정
필수 구현 함수	mm_init(), mm_malloc(), mm_free(), mm_realloc(), mm_check()
구현 조건	8바이트 정렬, mem_sbrk로 메모리 확장, 글로벌 배열 금지
성능 평가	정확성 + 공간 활용률 + 연산 처리 속도
추천 방법	implicit free list → coalescing → first-fit or next-fit
개발 순서	malloc/free부터 완성 → realloc 추가

작업 환경

aws의 ec2 리눅스 환경이나 docker 환경 중 택1을 할 수 있었는데, 나는 docker환경을 선택했다.
문제 명세대로 mm.c 파일만 수정할 거고, 일부 함수는 memlib.c에 있는걸 활용할 것이다.
환경을 제대로 살펴보면 아래 그립과 같다.
(test 방법 : make clean -> make -> ./mdriver 또는 ./mdriver -t traces/ -v)

구현 중 생각해야 하는 점

Docker는 호스트 OS의 CPU 아키텍처를 따르기 때문에, 일반적인 64비트 시스템에서는 포인터(void *)의 크기가 8바이트가 된다. 만약 malloc 구현에서 explicit free block 방식을 사용한다면, 헤더(Header) 4바이트, prev 포인터 8바이트, next 포인터 8바이트, 풋터(Footer) 4바이트를 사용한다. 따라서 하나의 가용 블록을 관리하기 위해 필요한 최소 크기는 24바이트가 된다.

메모리 블록을 할당하거나 관리할 때는 이 최소 크기를 항상 고려해야 하며, 모든 블록 크기는 8바이트 단위(8바이트 align)로 정렬되어야 한다. 특히, 가용 블록의 payload 영역에는 prev 포인터와 next 포인터가 순서대로 저장되는데, next 포인터는 payload 시작 위치에 저장되고, prev 포인터는 그 다음 8바이트 오프셋에 저장된다. 이 구조를 정확히 이해하고 포인터 접근 시에도 오프셋을 고려하여 읽고 써야 한다.

또한, 헤더와 풋터는 각각 4바이트 크기만을 사용하므로, 블록 크기를 계산하거나 포인터 연산을 할 때 헤더/풋터 크기와 payload 크기의 차이를 구분하여 계산해야 한다. 예를 들어, 블록의 크기를 얻을 때는 헤더를 기준으로 하고, 풋터를 찾을 때는 payload 크기만큼 이동한 뒤에 위치를 계산해야 한다.

정리하면, 64비트 환경에서는 포인터 크기가 8바이트이기 때문에 블록 구조 설계 시 최소 크기(24바이트)를 항상 만족해야 하며, 포인터 연산, 블록 크기 계산, 블록 나누기(splitting), 병합(coalescing) 등 모든 메모리 관리 연산에서 이 구조를 일관되게 유지해야 안정적인 동작을 보장할 수 있다.
(implict 방식을 사용하면 free될 때 payload 부분에 포인터가 안 들어가서 이걸 고민할 필요가 없다.)

구현하기

implicit free list + first fit

간단한 할당기라 함은, implicit free list + first-fit + immediate coalescing 방식이다.
힙 시작 포인터 전역 변수를 하나 선언한 것 빼고는 책(CS:APP 9.9.12)과 다 똑같다.

Docker는 호스트 OS의 영향을 많이 받기 때문인지,
같은 코드를 실행해도 컴퓨터 스펙에 따라 점수 차이가 크게 났다(60점 초반 ~ 70점 후반).
Mac과 Windows 모두 Docker를 VM 위에서 실행하지만,
Windows는 WSL2를 경유해야 해서 메모리, 파일시스템, 네트워크 모두 추가적인 우회가 발생하고,
이로 인해 Docker 성능 저하가 더 심해지는 것으로 추측된다.
다만 이후 개선된 코드들을 실행할 때는 하드웨어 스펙 차이에 따른 점수 차이가 거의 발생하지 않았다.
왜 유독 이 코드에서만 점수 편차가 크게 나타났는지는 추가로 분석이 필요할 것 같다.

/*
 * mm-naive.c - The fastest, least memory-efficient malloc package.
 *
 * In this naive approach, a block is allocated by simply incrementing
 * the brk pointer.  A block is pure payload. There are no headers or
 * footers.  Blocks are never coalesced or reused. Realloc is
 * implemented directly using mm_malloc and mm_free.
 *
 * NOTE TO STUDENTS: Replace this header comment with your own header
 * comment that gives a high level description of your solution.
 */
#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 */
    "ateam",
    /* First member's full name */
    "Harry Bovik",
    /* First member's email address */
    "bovik@cs.cmu.edu",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""};


/* 기본 상수 및 매크로 */
#define ALIGNMENT 8
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

#define WSIZE 4             // Word 크기 (헤더/풋터)
#define DSIZE 8             // Double word 크기
#define CHUNKSIZE (1 << 12) // 힙 확장 시 기본 단위 (4096바이트)

#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define PACK(size, alloc) ((size) | (alloc)) // 크기와 할당 여부 비트 합침

#define GET(p) (*(unsigned int *)(p))              // 주소 p에서 값 읽기
#define PUT(p, val) (*(unsigned int *)(p) = (val)) // 주소 p에 값 저장

#define GET_SIZE(p) (GET(p) & ~0x7) // 헤더에서 블록 크기 추출
#define GET_ALLOC(p) (GET(p) & 0x1) // 할당 여부 추출

#define HDRP(bp) ((char *)(bp) - WSIZE)                      // 블록 포인터로 헤더 주소 계산
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // 풋터 주소 계산

#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)))               // 다음 블록
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) // 이전 블록

/* 전역 변수: 힙 시작 포인터 */
static char *heap_listp = 0;

static void *find_fit(size_t asize)
{
    /* First-fit search */
    void *bp;
    for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
    {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
        {
            return bp;
        }
    }
    return NULL; /* No fit */
}

static void place(void *bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));
    if ((csize - asize) >= (2 * DSIZE))
    {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize - asize, 0));
        PUT(FTRP(bp), PACK(csize - asize, 0));
    }
    else{
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

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

    // Case 1: 양 옆 모두 할당 → 그대로
    if (prev_alloc && next_alloc)
    {
        return bp;
    }

    // Case 2: 다음 블록만 가용
    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));
    }

    // Case 3: 이전 블록만 가용
    else if (!prev_alloc && next_alloc)
    {
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }

    // Case 4: 양 옆 모두 가용
    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;
}

/* 힙 확장 함수: 새 가용 블록 생성 */
static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;

    // 정렬을 위해 words 수를 짝수로 맞춰서 WSIZE 곱
    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

    // 앞 블록과 병합 (coalesce)
    return coalesce(bp);
}

/* 힙 초기화 함수 */
int mm_init(void)
{
    // 초기 힙 생성: padding + prologue header/footer + epilogue header
    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
        return -1;

    PUT(heap_listp, 0);                            // 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);                     // 유저 블록 시작 위치 설정

    // 힙을 CHUNKSIZE만큼 확장하고 free 블록 생성
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;

    return 0;
}

/* 블록 반환 함수 */
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_malloc(size_t size)
{
    size_t asize;      // 정렬 + 오버헤드 적용된 크기
    size_t extendsize; // fit 실패 시 확장할 크기
    char *bp;

    // 0바이트 요청 무시
    if (size == 0)
        return NULL;

    // 최소 블록 크기 맞추기 (DSIZE 이상, header + footer 포함)
    if (size <= DSIZE)
        asize = 2 * DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);

    // 프리 리스트에서 적합한 블록 탐색
    if ((bp = find_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;
}


/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size)
{
    void *newptr;
    size_t copySize;

    if ((newptr = mm_malloc(size)) == NULL)
        return NULL;

    copySize = GET_SIZE(HDRP(ptr)) - DSIZE; // payload 크기
    if (size < copySize)
        copySize = size;

    memcpy(newptr, ptr, copySize); // 내용 복사
    mm_free(ptr);                  // 기존 블록 반환
    return newptr;
}

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   99%    5694  0.005367  1061
 1       yes   99%    5848  0.004725  1238
 2       yes   99%    6648  0.008144   816
 3       yes  100%    5380  0.005909   910
 4       yes   66%   14400  0.000145 99516
 5       yes   92%    4800  0.004199  1143
 6       yes   92%    4800  0.004016  1195
 7       yes   55%   12000  0.075413   159
 8       yes   51%   24000  0.231135   104
 9       yes   27%   14401  0.037705   382
10       yes   34%   14401  0.000898 16035
Total          74%  112372  0.377658   298

Perf index = 44 (util) + 20 (thru) = 64/100

implict free list + next fit

나는 바로 explicit 구현으로 넘어갔지만,
다른 사람(feat. at this moment)이 짜본 코드가 점수가 잘 나온대서 가져와봤다.
그런데 다른 것보다 진짜 더 높은 점수가 나와서 당황스럽다.
header랑 footer를 아예 8byte로 짜버렸는데 메모리 사용엔 낭비가 없는지 의문이다.
분명 묵시적 방식을 64 비트 체계 위에서 돌린다고 해도
header랑 footer 크기를 조정할 필요가 없을 것 같은데... 좀 더 알아볼 필요가 있다.

//묵시적 프리 리스트
//넥스트 핏
//헤더푸터크기 64비트 기준 wsize=8
//최소블록크기 dsize=16
//초기화 = prologue(가짜 할당 블록) + epilogue(가짜 0바이트 할당 블록) + extend_heap(CHUNKSIZE)
//힙 확장 extend_heap(words)
//병합, 네가지 케이스 처리 후 last_fitp를 병합 결과로 갱신
//분할, 남은 크기 >= 2*DSIZE(16B)일때만 스플릿 -> 너무 많은 조각이 생기지 않도록
//realloc(재할당) = 기존 공간이 충분하면 그대로 사용하고, 뒷 블록이 프리이고 붙여서 공간이 충분해진다면 인플레이스 확장
//그 외에는 new malloc + memcpy + free

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

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

#define WSIZE 8
#define DSIZE 16
#define CHUNKSIZE (1<<12)
#define PACK(size, alloc) ((size) | (alloc))
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

static char *heap_listp = 0;
static char *last_fitp = NULL;

static void *extend_heap(size_t words);
static void *coalesce(void *bp);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);

team_t team = {
    "KRAFTON JUNGLE 8th 301",
    "J",
    "J@gmail.com",
    "",
    ""
};

#define ALIGNMENT 8
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

int mm_init(void) {
    // printf("[DEBUG] mm_init() 시작\n");

    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1) {
        // printf("[DEBUG] mem_sbrk(4*WSIZE) 실패\n");
        return -1;
    }

    PUT(heap_listp, 0);
    PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));
    PUT(heap_listp + (3 * WSIZE), PACK(0, 1));
    heap_listp += (2 * WSIZE);

    last_fitp = NEXT_BLKP(heap_listp);

    if (extend_heap(CHUNKSIZE / WSIZE) == NULL) {
        // printf("[DEBUG] extend_heap 실패\n");
        return -1;
    }

    // printf("[DEBUG] mm_init() 완료\n");
    return 0;
}

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

    if (size == 0)
        return NULL;

    if (size <= DSIZE)
        asize = 2 * DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);

    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }

    extendsize = (asize > CHUNKSIZE) ? asize : CHUNKSIZE;
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL) {
        // printf("extend_heap failed inside mm_malloc\n");
        return NULL;
    }
    place(bp, asize);
    return bp;
}

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) {
    size_t oldsize;
    void *newptr;
    size_t asize;

    if (ptr == NULL)
        return mm_malloc(size);

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

    oldsize = GET_SIZE(HDRP(ptr));

    if (size <= DSIZE)
        asize = 2 * DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);

    if (asize <= oldsize) {
        return ptr;
    } else {
        void *next_bp = NEXT_BLKP(ptr);
        size_t next_alloc = GET_ALLOC(HDRP(next_bp));
        size_t next_size = GET_SIZE(HDRP(next_bp));

        if (!next_alloc && (oldsize + next_size) >= asize) {
            PUT(HDRP(ptr), PACK(oldsize + next_size, 1));
            PUT(FTRP(ptr), PACK(oldsize + next_size, 1));
            return ptr;
        }

        newptr = mm_malloc(size);
        if (newptr == NULL)
            return NULL;

        memcpy(newptr, ptr, oldsize - DSIZE);
        mm_free(ptr);
        return newptr;
    }
}

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

    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;

    if ((bp = mem_sbrk(size)) == (void *)-1) {
        // printf("[DEBUG] mem_sbrk(size=%zu) 실패\n", size);
        return NULL;
    }

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

    // 에필로그 블록 재설정
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));

    last_fitp = bp;

    return coalesce(bp);
}

static void *coalesce(void *bp)
{
    size_t prev_alloc = 1;
    if ((char *)bp > heap_listp) {               /* 프로로그 뒤일 때만 */
        prev_alloc = GET_ALLOC(HDRP(PREV_BLKP(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: 앞, 뒤 모두 할당
        // last_fitp는 bp로 유지
        last_fitp = bp;
        return bp;
    } else if (prev_alloc && !next_alloc) {
        // case 2: 앞은 할당, 뒤는 free
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
        last_fitp = bp;
    } else if (!prev_alloc && next_alloc) {
        // case 3: 앞은 free, 뒤는 할당
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
        last_fitp = bp;
    } else {
        // case 4: 앞, 뒤 모두 free
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
        last_fitp = bp;
    }
    return bp;
}

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

    // last_fitp 초기화 (최초 검색 시 시작점 설정)
    if (last_fitp == NULL)
        last_fitp = NEXT_BLKP(heap_listp);

    // 1. last_fitp부터 힙 끝까지 검색
    bp = last_fitp;
    while (GET_SIZE(HDRP(bp)) > 0) {
        if (!GET_ALLOC(HDRP(bp)) && (GET_SIZE(HDRP(bp)) >= asize)) {
            last_fitp = bp; // 성공 시 포인터 갱신
            return bp;
        }
        bp = NEXT_BLKP(bp);
    }

    // 2. 힙 시작부터 last_fitp까지 재검색 (에필로그 접근 방지)
    for (bp = NEXT_BLKP(heap_listp); 
         GET_SIZE(HDRP(bp)) > 0 && bp != last_fitp;  // 종료 조건: 유효 블록 + last_fitp 미도달
         bp = NEXT_BLKP(bp)) 
    {
        if (!GET_ALLOC(HDRP(bp)) && (GET_SIZE(HDRP(bp)) >= asize)) {
            last_fitp = bp; // 성공 시 포인터 갱신
            return bp;
        }
    }

    // 3. 적합한 블록 없음
    return NULL;
}


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

    if ((csize - asize) >= (2 * DSIZE)) {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));

        void *next_bp = NEXT_BLKP(bp);
        PUT(HDRP(next_bp), PACK(csize - asize, 0));
        PUT(FTRP(next_bp), PACK(csize - asize, 0));
    } else {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   90%    5694  0.001416  4020
 1       yes   92%    5848  0.000826  7076
 2       yes   94%    6648  0.002345  2835
 3       yes   96%    5380  0.002464  2183
 4       yes   66%   14400  0.000142101767
 5       yes   90%    4800  0.002433  1973
 6       yes   86%    4800  0.002300  2087
 7       yes   54%   12000  0.006713  1788
 8       yes   47%   24000  0.006782  3539
 9       yes   42%   14401  0.000213 67706
10       yes   86%   14401  0.000112128466
Total          77%  112372  0.025746  4365

Perf index = 46 (util) + 40 (thru) = 86/100

explict free list + first fit

implicit에서 explicit 방식으로 고치기 위해 다음 사항들을 점검해야 했다.

항목	implicit free list	explicit free list 변경사항
coalesce	그냥 header/footer 갱신만 했음	free list에서 블록 제거 + 새 병합 블록 삽입
extend_heap	header/footer 세팅 후 바로 리턴	coalesce 호출 → free list에 삽입
mm_free	header/footer 갱신	header/footer 갱신 + free list에 삽입 (coalesce 통해)
find_fit	힙 전체 블록 순회	free list만 순회
place	header/footer만 갱신	free list에서 분할 처리한 블록 재삽입 or 제거

free list에 블록 삽입하는 함수 필요
새로 생긴 free block을 free list의 처음에 삽입 (LIFO 방식 추천)
SET_NEXT_FREE(bp, free_listp) 이런 식으로 연결

static void insert_free_block(void *bp);

free list에서 블록 제거하는 함수 필요
할당(place)하거나 병합(coalesce)할 때, free list에서 끊어내야 함
prev/next 포인터를 수정해야 함

static void remove_free_block(void *bp);

(+ realloc을 케이스를 나누어 동작하도록 개선했다.)

/*
 * mm-explicit.c - 명시적 가용 리스트(Explicit Free List)를 이용한 malloc 구현.
 *
 * 가용 블록 구조:
 * 헤더(4바이트) | Prev 포인터(8바이트) | Next 포인터(8바이트) | 풋터(4바이트)
 * 최소 블록 크기는 24바이트이다.
 *
 * 할당된 블록 구조:
 * 헤더(4바이트) | 유저 데이터(payload, 8바이트 정렬) | 풋터(4바이트)
 *
 * 가용 리스트 관리:
 * - 명시적 이중 연결 리스트 사용.
 * - free_listp가 가용 리스트의 첫 번째 블록을 가리킨다.
 * - 삽입은 항상 LIFO(최근 삽입) 방식으로 수행한다.
 * - 병합(Coalescing) 시 인접한 가용 블록을 합치고, 가용 리스트를 갱신한다.
 */

 #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 */
     "Explicit Free List Team",
     /* First member's full name */
     "Harry Bovik",
     /* First member's email address */
     "bovik@cs.cmu.edu",
     /* Second member's full name (leave blank if none) */
     "",
     /* Second member's email address (leave blank if none) */
     ""};
 
 #define ALIGNMENT 8                 // 8바이트 정렬을 위한 크기
 #define WSIZE 4                     // 워드 크기 및 헤더/풋터 크기 (4바이트)
 #define DSIZE 8                     // 더블 워드 크기 (8바이트)
 #define MIN_BLOCK_SIZE 24           // 최소 블록 크기 (헤더+포인터2개+풋터 = 24바이트)
 #define CHUNKSIZE (1 << 12)         // 힙 확장 기본 크기 (4096바이트)
 
 #define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7) // 8바이트 정렬에 맞게 size를 올림
 #define MAX(x, y) ((x) > (y) ? (x) : (y)) // 두 값 중 큰 값을 반환
 #define PACK(size, alloc) ((size) | (alloc)) // 블록 크기와 할당 여부를 합쳐 저장
 
 #define GET(p) (*(unsigned int *)(p)) // 주소 p에 저장된 값을 읽음
 #define PUT(p, val) (*(unsigned int *)(p) = (val)) // 주소 p에 val을 저장
 
 #define GET_SIZE(p) (GET(p) & ~0x7) // 헤더나 풋터에서 블록 크기를 추출
 #define GET_ALLOC(p) (GET(p) & 0x1) // 헤더나 풋터에서 할당 여부를 추출
 
 #define HDRP(bp) ((char *)(bp) - WSIZE) // 블록 포인터 bp로부터 헤더 주소 계산
 #define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // 블록 포인터 bp로부터 풋터 주소 계산
 #define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp))) // 다음 블록의 포인터 계산
 #define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) // 이전 블록의 포인터 계산
 
 #define NEXT_FREE_PTR(bp) (*(void **)(bp)) // 가용 블록의 next 포인터를 읽음
 #define PREV_FREE_PTR(bp) (*(void **)((char *)(bp) + DSIZE)) // 가용 블록의 prev 포인터를 읽음
 #define SET_NEXT_FREE(bp, ptr) (NEXT_FREE_PTR(bp) = (ptr)) // 가용 블록의 next 포인터를 설정
 #define SET_PREV_FREE(bp, ptr) (PREV_FREE_PTR(bp) = (ptr)) // 가용 블록의 prev 포인터를 설정
 
 static char *heap_listp = 0; // 힙의 시작 포인터
 static void *free_listp = NULL; // 명시적 가용 리스트의 첫 번째 블록 포인터
 
 static void *extend_heap(size_t words); // 힙을 확장하는 함수
 static void *coalesce(void *bp); // 인접 가용 블록들과 병합하는 함수
 static void *find_fit(size_t asize); // 주어진 크기에 맞는 가용 블록을 찾는 함수
 static void place(void *bp, size_t asize); // 가용 블록에 메모리를 배치하는 함수
 static void insert_free_block(void *bp); // 가용 리스트에 블록을 삽입하는 함수
 static void remove_free_block(void *bp); // 가용 리스트에서 블록을 제거하는 함수
 
 
 int mm_init(void)
 {
     // 힙의 초기 공간 4워드 할당 (패딩 + 프롤로그 블록 + 에필로그 블록)
     if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
         return -1;
 
     PUT(heap_listp, 0);                            // 패딩 워드
     PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); // 프롤로그 헤더
     PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); // 프롤로그 풋터
     PUT(heap_listp + (3 * WSIZE), PACK(0, 1));     // 에필로그 헤더
     heap_listp += (2 * WSIZE);                     // heap_listp를 프롤로그 payload로 이동
 
     free_listp = NULL; // 가용 리스트 포인터 초기화
 
     // 초기 힙 공간을 CHUNKSIZE만큼 확장
     if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
         return -1;
 
     return 0;
 }
 
 
 static void insert_free_block(void *bp)
 {
     // 현재 가용 블록의 next를 기존 free_listp로 설정
     SET_NEXT_FREE(bp, free_listp);
     // 현재 가용 블록의 prev를 NULL로 설정 (가용 리스트 맨 앞이므로)
     SET_PREV_FREE(bp, NULL);
 
     // 기존 free_listp가 존재하면, 그 블록의 prev를 현재 bp로 설정
     if (free_listp != NULL)
         SET_PREV_FREE(free_listp, bp);
 
     // free_listp를 현재 bp로 갱신
     free_listp = bp;
 }
 
 
 static void remove_free_block(void *bp)
 {
     void* prev_free = PREV_FREE_PTR(bp);
     void* next_free = NEXT_FREE_PTR(bp);
 
     // 이전 블록이 있으면, 이전 블록의 next를 현재 bp의 next로 설정
     if (prev_free)
          SET_NEXT_FREE(prev_free, next_free);
     else
          free_listp = next_free; // prev가 없으면 free_listp를 next로 갱신
 
     // 다음 블록이 있으면, 다음 블록의 prev를 현재 bp의 prev로 설정
     if (next_free)
          SET_PREV_FREE(next_free, prev_free);
 }
 
 
 
 static void *extend_heap(size_t words)
 {
     char *bp;
     size_t size;
 
     // words 수를 짝수로 맞춰서 8바이트 정렬 유지
     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)); // 새로운 에필로그 블록 설정
 
     return coalesce(bp); // 확장된 블록을 병합하여 반환
 }
 
 
 void mm_free(void *bp)
 {
     if (bp == 0) return; // NULL 포인터 무시
 
     size_t size = GET_SIZE(HDRP(bp));
 
     PUT(HDRP(bp), PACK(size, 0)); // 헤더에 가용 표시
     PUT(FTRP(bp), PACK(size, 0)); // 풋터에 가용 표시
 
     coalesce(bp); // 인접 블록들과 병합
 }
 
 
 static void *coalesce(void *bp)
 {
     // 이전 블록과 다음 블록의 할당 상태를 확인
     size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
     size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
     size_t size = GET_SIZE(HDRP(bp));
 
     // 병합 전 이웃 블록들의 원래 포인터를 저장 (나중에 제거할 때 사용)
     void *original_prev_bp = NULL;
     void *original_next_bp = NULL;
 
     if (!prev_alloc) {
         original_prev_bp = PREV_BLKP(bp); // 이전 블록이 가용이면 저장
     }
     if (!next_alloc) {
         original_next_bp = NEXT_BLKP(bp); // 다음 블록이 가용이면 저장
     }
 
     if (prev_alloc && next_alloc) { // Case 1: 앞뒤 모두 할당됨
         insert_free_block(bp); // 현재 블록만 가용 리스트에 삽입
         return bp;
     }
     else if (prev_alloc && !next_alloc) { // Case 2: 다음 블록만 가용
         remove_free_block(original_next_bp); // 다음 블록을 가용 리스트에서 제거
         size += GET_SIZE(HDRP(original_next_bp)); // 크기 합치기
         PUT(HDRP(bp), PACK(size, 0)); // 새 크기로 헤더 갱신
         PUT(FTRP(bp), PACK(size, 0)); // 새 크기로 풋터 갱신
     }
     else if (!prev_alloc && next_alloc) { // Case 3: 이전 블록만 가용
         remove_free_block(original_prev_bp); // 이전 블록을 가용 리스트에서 제거
         size += GET_SIZE(HDRP(original_prev_bp)); // 크기 합치기
         PUT(HDRP(original_prev_bp), PACK(size, 0)); // 이전 블록 헤더 갱신
         PUT(FTRP(bp), PACK(size, 0)); // 현재 블록 풋터 갱신
         bp = original_prev_bp; // 병합 결과 포인터를 이전 블록으로 변경
     }
     else { // Case 4: 앞뒤 모두 가용
         remove_free_block(original_prev_bp); // 이전 블록 제거
         remove_free_block(original_next_bp); // 다음 블록 제거
         size += GET_SIZE(HDRP(original_prev_bp)) + GET_SIZE(HDRP(original_next_bp)); // 세 블록 크기 합치기
         PUT(HDRP(original_prev_bp), PACK(size, 0)); // 합친 크기로 헤더 갱신
         PUT(FTRP(original_next_bp), PACK(size, 0)); // 합친 크기로 풋터 갱신
         bp = original_prev_bp; // 병합 결과 포인터를 이전 블록으로 변경
     }
 
     insert_free_block(bp); // 병합 결과 블록을 가용 리스트에 삽입
     return bp;
 }
 
 
 void *mm_malloc(size_t size)
 {
     size_t asize;      // 정렬 및 오버헤드 포함 조정된 블록 크기
     size_t extendsize; // 힙을 확장할 크기
     char *bp;
 
     if (size == 0)
         return NULL; // 요청 크기가 0이면 무시
 
     if (size <= DSIZE * 2)
         asize = MIN_BLOCK_SIZE; // 최소 블록 크기 (24바이트)
     else
         asize = ALIGN(size + DSIZE); // 요청 크기 + 헤더/풋터 오버헤드 추가 후 정렬
 
     // 가용 리스트에서 적절한 블록을 찾기
     if ((bp = find_fit(asize)) != NULL) {
         place(bp, asize); // 찾은 블록에 배치
         return bp;
     }
 
     // 적절한 블록이 없다면 힙 확장
     extendsize = MAX(asize, CHUNKSIZE);
     if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
         return NULL; // 확장 실패 시 NULL 반환
 
     place(bp, asize); // 확장된 블록에 배치
     return bp;
 }
 
 static void *find_fit(size_t asize)
 {
     void *bp;
 
     // 가용 리스트를 순차 탐색하여 첫 번째로 맞는 블록을 찾음
     for (bp = free_listp; bp != NULL; bp = NEXT_FREE_PTR(bp)) {
         if (asize <= GET_SIZE(HDRP(bp))) {
             return bp; // 크기가 충분한 블록을 찾으면 반환
         }
     }
     return NULL; // 맞는 블록이 없으면 NULL 반환
 }
 
 static void place(void *bp, size_t asize)
 {
     size_t csize = GET_SIZE(HDRP(bp)); // 현재 가용 블록 크기
 
     remove_free_block(bp); // 가용 리스트에서 현재 블록 제거
 
     if ((csize - asize) >= MIN_BLOCK_SIZE) { // 분할할 수 있는 경우
         PUT(HDRP(bp), PACK(asize, 1)); // 요청 크기로 헤더 설정 (할당 표시)
         PUT(FTRP(bp), PACK(asize, 1)); // 요청 크기로 풋터 설정 (할당 표시)
 
         // 남은 부분을 새 가용 블록으로 설정
         void* next_bp = NEXT_BLKP(bp);
         PUT(HDRP(next_bp), PACK(csize - asize, 0));
         PUT(FTRP(next_bp), PACK(csize - asize, 0));
 
         coalesce(next_bp); // 남은 가용 블록 병합 및 삽입
     }
     else { // 블록 전체를 할당
         PUT(HDRP(bp), PACK(csize, 1)); // 전체 크기로 헤더 설정
         PUT(FTRP(bp), PACK(csize, 1)); // 전체 크기로 풋터 설정
     }
 }
 
 
/**
  * mm_realloc - 메모리 블록 재할당
  * 최적화는 Next Fit 전략과 독립적이므로 그대로 사용 가능.
  */
 void *mm_realloc(void *ptr, size_t size)
  {
      // Case 1: ptr is NULL, equivalent to malloc(size)
      if (ptr == NULL) {
          return mm_malloc(size);
      }
 
      // Case 2: size is 0, equivalent to free(ptr)
      if (size == 0) {
          mm_free(ptr);
          return NULL;
      }
 
      // 필요한 실제 블록 크기 계산
      size_t asize;
      if (size <= DSIZE * 2)
          asize = MIN_BLOCK_SIZE;
      else
          asize = ALIGN(size + DSIZE);
 
      size_t old_block_size = GET_SIZE(HDRP(ptr)); // 현재 블록 크기
 
      // Optimization 1: 현재 블록 크기가 충분한 경우 (축소 또는 동일)
      if (asize <= old_block_size) {
          if ((old_block_size - asize) >= MIN_BLOCK_SIZE) { // 분할 가능하면
              PUT(HDRP(ptr), PACK(asize, 1));
              PUT(FTRP(ptr), PACK(asize, 1));
              void *remainder_bp = NEXT_BLKP(ptr);
              PUT(HDRP(remainder_bp), PACK(old_block_size - asize, 0));
              PUT(FTRP(remainder_bp), PACK(old_block_size - asize, 0));
              coalesce(remainder_bp); // 남은 블록 가용 리스트에 추가
          }
          // 분할 불필요하거나 불가능하면 그대로 반환
          return ptr;
      }
 
      // Optimization 2: 다음 블록이 가용 상태이고 병합하여 충분한 경우
      void *next_bp = NEXT_BLKP(ptr);
      int next_alloc = GET_ALLOC(HDRP(next_bp));
      size_t next_size = GET_SIZE(HDRP(next_bp));
 
      if (!next_alloc && next_size > 0) {
          size_t combined_size = old_block_size + next_size;
          if (combined_size >= asize) { // 병합하면 충분
              remove_free_block(next_bp); // 병합 전에 다음 블록 제거
 
              if ((combined_size - asize) >= MIN_BLOCK_SIZE) { // 병합 후 분할 가능하면
                  PUT(HDRP(ptr), PACK(asize, 1));
                  PUT(FTRP(ptr), PACK(asize, 1));
                  void *remainder_bp = NEXT_BLKP(ptr);
                  PUT(HDRP(remainder_bp), PACK(combined_size - asize, 0));
                  PUT(FTRP(remainder_bp), PACK(combined_size - asize, 0));
                  coalesce(remainder_bp); // 남은 블록 추가
              } else { // 병합 후 전체 사용
                  PUT(HDRP(ptr), PACK(combined_size, 1));
                  PUT(FTRP(ptr), PACK(combined_size, 1));
              }
              return ptr; // 기존 포인터 반환
          }
      }
 
      // Fallback: 새로 할당, 복사, 해제
      void *newptr = mm_malloc(size);
      if (newptr == NULL) return NULL;
 
      size_t old_payload_size = old_block_size - DSIZE;
      size_t copySize = (size < old_payload_size) ? size : old_payload_size;
      memcpy(newptr, ptr, copySize);
      mm_free(ptr); // 기존 블록 해제
 
      return newptr;
  }

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   89%    5694  0.000177 32115
 1       yes   92%    5848  0.000109 53799
 2       yes   94%    6648  0.000276 24052
 3       yes   96%    5380  0.000210 25619
 4       yes   66%   14400  0.000160 90056
 5       yes   88%    4800  0.000383 12526
 6       yes   85%    4800  0.000423 11358
 7       yes   55%   12000  0.001735  6916
 8       yes   51%   24000  0.001906 12594
 9       yes   33%   14401  0.023644   609
10       yes   30%   14401  0.000247 58280
Total          71%  112372  0.029270  3839

Perf index = 43 (util) + 40 (thru) = 83/100

explict free list + next fit

implicit free list에 first fit 대신 next fit을 적용하면 점수가 많이 좋아지지만,
explicit free list에 next fit을 적용했다고 해서 점수가 크게 좋아지진 않는다.

어차피 두 방식 모두 리스트를 선형적으로 탐색하는 기본적인 시간 복잡도 한계를 가지기 때문이다.
Next Fit은 평균적으로 약간 빠를 수 있지만,
최악의 경우 전체를 탐색하는 것은 동일하며 메모리 이용률은 더 나빠질 수 있다.

/*
 * mm-explicit-nextfit-reallocopt.c - 명시적 가용 리스트 및 Next Fit 전략,
 *
 * 가용 블록 구조:
 * 헤더(4바이트) | Prev 포인터(8바이트) | Next 포인터(8바이트) | 풋터(4바이트)
 * 최소 블록 크기는 24바이트이다.
 *
 * 할당된 블록 구조:
 * 헤더(4바이트) | 유저 데이터(payload, 8바이트 정렬) | 풋터(4바이트)
 *
 * 가용 리스트 관리:
 * - 명시적 이중 연결 리스트 사용.
 * - free_listp가 가용 리스트의 첫 번째 블록을 가리킨다.
 * - 삽입은 항상 LIFO 방식으로 수행한다.
 * - 병합(Coalescing) 시 인접한 가용 블록을 합치고, 가용 리스트를 갱신한다.
 * - 배치 전략: Next Fit. next_fit_rover가 마지막 탐색 위치를 기억한다.
 */

 #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 */
     "Explicit NextFit ReallocOpt",
     /* First member's full name */
     "Harry Bovik",
     /* First member's email address */
     "bovik@cs.cmu.edu",
     /* Second member's full name (leave blank if none) */
     "",
     /* Second member's email address (leave blank if none) */
     ""};
 
 #define ALIGNMENT 8                 // 8바이트 정렬을 위한 크기
 #define WSIZE 4                     // 워드 크기 및 헤더/풋터 크기 (4바이트)
 #define DSIZE 8                     // 더블 워드 크기 (8바이트)
 #define MIN_BLOCK_SIZE 24           // 최소 블록 크기 (헤더+포인터2개+풋터 = 24바이트)
 #define CHUNKSIZE (1 << 12)         // 힙 확장 기본 크기 (4096바이트)
 
 #define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7) // 8바이트 정렬에 맞게 size를 올림
 #define MAX(x, y) ((x) > (y) ? (x) : (y)) // 두 값 중 큰 값을 반환
 #define PACK(size, alloc) ((size) | (alloc)) // 블록 크기와 할당 여부를 합쳐 저장
 
 #define GET(p) (*(unsigned int *)(p)) // 주소 p에 저장된 값을 읽음
 #define PUT(p, val) (*(unsigned int *)(p) = (val)) // 주소 p에 val을 저장
 
 #define GET_SIZE(p) (GET(p) & ~0x7) // 헤더나 풋터에서 블록 크기를 추출
 #define GET_ALLOC(p) (GET(p) & 0x1) // 헤더나 풋터에서 할당 여부를 추출
 
 #define HDRP(bp) ((char *)(bp) - WSIZE) // 블록 포인터 bp로부터 헤더 주소 계산
 #define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // 블록 포인터 bp로부터 풋터 주소 계산
 #define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp))) // 다음 블록의 포인터 계산
 #define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) // 이전 블록의 포인터 계산
 
 #define NEXT_FREE_PTR(bp) (*(void **)(bp)) // 가용 블록의 next 포인터를 읽음
 #define PREV_FREE_PTR(bp) (*(void **)((char *)(bp) + DSIZE)) // 가용 블록의 prev 포인터를 읽음
 #define SET_NEXT_FREE(bp, ptr) (NEXT_FREE_PTR(bp) = (ptr)) // 가용 블록의 next 포인터를 설정
 #define SET_PREV_FREE(bp, ptr) (PREV_FREE_PTR(bp) = (ptr)) // 가용 블록의 prev 포인터를 설정
 
 static char *heap_listp = 0; // 힙의 시작 포인터
 static void *free_listp = NULL; // 명시적 가용 리스트의 첫 번째 블록 포인터
 static void *next_fit_rover = NULL; // Next Fit 탐색 시작 포인터
 
 static void *extend_heap(size_t words);
 static void *coalesce(void *bp);
 static void *find_fit(size_t asize); // Next Fit 로직으로 수정됨
 static void place(void *bp, size_t asize);
 static void insert_free_block(void *bp);
 static void remove_free_block(void *bp); // Next Fit rover 관리 로직 추가됨
 
 
 int mm_init(void)
 {
     if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
         return -1;
 
     PUT(heap_listp, 0);                            // 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);
 
     free_listp = NULL;
     next_fit_rover = NULL; // rover 초기화
 
     if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
         return -1;
 
     // 초기 rover는 첫 번째 가용 블록을 가리킴
     next_fit_rover = free_listp;
 
     return 0;
 }
 
 
 static void insert_free_block(void *bp)
 {
     SET_NEXT_FREE(bp, free_listp);
     SET_PREV_FREE(bp, NULL);
 
     if (free_listp != NULL)
         SET_PREV_FREE(free_listp, bp);
 
     free_listp = bp;
 }
 
 
 static void remove_free_block(void *bp)
 {
     void* prev_free = PREV_FREE_PTR(bp);
     void* next_free = NEXT_FREE_PTR(bp);
 
     // --- Next Fit Rover Handling ---
     // 제거되는 블록이 현재 rover이면, rover를 리스트상의 다음 블록으로 이동
     if (next_fit_rover == bp) {
         next_fit_rover = next_free;
     }
     // --- End Rover Handling ---
 
     if (prev_free)
          SET_NEXT_FREE(prev_free, next_free);
     else
          free_listp = next_free;
 
     if (next_free)
          SET_PREV_FREE(next_free, prev_free);
 }
 
 
 
 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));
 
     return coalesce(bp);
 }
 
 
 void mm_free(void *bp)
 {
     if (bp == 0) return;
 
     size_t size = GET_SIZE(HDRP(bp));
 
     // 이미 해제된 블록을 다시 해제하는지 확인 (선택적)
     // if (!GET_ALLOC(HDRP(bp))) { ... 에러 처리 ... }
 
     PUT(HDRP(bp), PACK(size, 0));
     PUT(FTRP(bp), PACK(size, 0));
 
     coalesce(bp);
 }
 
 
 static void *coalesce(void *bp)
 {
     size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
     size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
     size_t size = GET_SIZE(HDRP(bp));
     void *original_prev_bp = NULL;
     void *original_next_bp = NULL;
 
     if (!prev_alloc) original_prev_bp = PREV_BLKP(bp);
     if (!next_alloc) original_next_bp = NEXT_BLKP(bp);
 
     if (prev_alloc && next_alloc) { // Case 1
         insert_free_block(bp);
         return bp;
     }
     else if (prev_alloc && !next_alloc) { // Case 2
         // remove_free_block은 next_fit_rover를 처리함
         remove_free_block(original_next_bp);
         size += GET_SIZE(HDRP(original_next_bp));
         PUT(HDRP(bp), PACK(size, 0));
         PUT(FTRP(bp), PACK(size, 0));
     }
     else if (!prev_alloc && next_alloc) { // Case 3
         // remove_free_block은 next_fit_rover를 처리함
         remove_free_block(original_prev_bp);
         size += GET_SIZE(HDRP(original_prev_bp));
         PUT(HDRP(original_prev_bp), PACK(size, 0));
         PUT(FTRP(bp), PACK(size, 0));
         bp = original_prev_bp;
     }
     else { // Case 4
         // remove_free_block은 next_fit_rover를 처리함
         remove_free_block(original_prev_bp);
         remove_free_block(original_next_bp);
         size += GET_SIZE(HDRP(original_prev_bp)) + GET_SIZE(HDRP(original_next_bp));
         PUT(HDRP(original_prev_bp), PACK(size, 0));
         PUT(FTRP(original_next_bp), PACK(size, 0));
         bp = original_prev_bp;
     }
 
     insert_free_block(bp);
     // coalesce 후 rover 관리는 remove_free_block/insert_free_block 호출에 의해 간접적으로 이루어짐
     // 만약 합쳐진 블록이 리스트 맨 앞에 삽입되면, rover가 이걸 가리키도록 해야할까?
     // -> Next Fit의 정의상 다음 탐색 시작점은 '마지막으로 할당된 블록 다음'이다.
     //    coalesce 자체가 할당은 아니므로, coalesce 때문에 rover를 직접 옮길 필요는 없다.
     //    rover는 find_fit 또는 remove_free_block 에서만 갱신된다.
     return bp;
 }
 
 
 void *mm_malloc(size_t size)
 {
     size_t asize;
     size_t extendsize;
     char *bp;
 
     if (size == 0) return NULL;
 
     if (size <= DSIZE * 2)
         asize = MIN_BLOCK_SIZE;
     else
         asize = ALIGN(size + DSIZE);
 
     // Next Fit을 사용하여 블록 탐색
     if ((bp = find_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;
 }
 
 
 /**
  * find_fit - Next Fit 전략을 사용하여 가용 블록 탐색
  */
 static void *find_fit(size_t asize)
 {
     void *bp;
     void *current_search_start = next_fit_rover; // 현재 탐색 시작점 (rover)
 
     // rover가 유효하지 않은 경우 (예: NULL), 리스트 시작부터 탐색
     if (current_search_start == NULL) {
         current_search_start = free_listp;
     }
 
     // 1. rover 위치부터 리스트 끝까지 탐색
     for (bp = current_search_start; bp != NULL; bp = NEXT_FREE_PTR(bp)) {
         if (asize <= GET_SIZE(HDRP(bp))) {
             next_fit_rover = bp; // 찾았으므로 rover를 현재 블록으로 업데이트
             return bp;
         }
     }
 
     // 2. 리스트 처음부터 원래 rover 위치까지 탐색 (Wrap around)
     //    (탐색 시작점이 처음(free_listp)이었다면 이 루프는 실행되지 않음)
     if (current_search_start != free_listp) {
         for (bp = free_listp; bp != current_search_start; bp = NEXT_FREE_PTR(bp)) {
              // 만약 리스트가 손상되어 무한 루프가 돌 가능성을 대비
             if (bp == NULL) break;
             if (asize <= GET_SIZE(HDRP(bp))) {
                 next_fit_rover = bp; // 찾았으므로 rover를 현재 블록으로 업데이트
                 return bp;
             }
         }
     }
 
     // 리스트 전체를 탐색했지만 적절한 블록을 찾지 못함
     return NULL;
 }
 
 
 static void place(void *bp, size_t asize)
 {
     size_t csize = GET_SIZE(HDRP(bp));
 
     // 블록을 배치하기 전에 가용 리스트에서 제거 (remove_free_block이 rover 관리)
     remove_free_block(bp);
 
     if ((csize - asize) >= MIN_BLOCK_SIZE) { // 분할
         PUT(HDRP(bp), PACK(asize, 1));
         PUT(FTRP(bp), PACK(asize, 1));
 
         void* next_bp = NEXT_BLKP(bp);
         PUT(HDRP(next_bp), PACK(csize - asize, 0));
         PUT(FTRP(next_bp), PACK(csize - asize, 0));
         coalesce(next_bp); // 남은 블록을 가용 리스트에 추가 (및 병합 시도)
     }
     else { // 전체 사용
         PUT(HDRP(bp), PACK(csize, 1));
         PUT(FTRP(bp), PACK(csize, 1));
     }
     // place 함수 자체는 rover를 직접 건드리지 않음.
     // find_fit에서 rover를 설정하고, remove_free_block에서 필요시 rover를 이동시킴.
 }
 
 
 /**
  * mm_realloc - 메모리 블록 재할당
  * 최적화는 Next Fit 전략과 독립적이므로 그대로 사용 가능.
  */
 void *mm_realloc(void *ptr, size_t size)
  {
      // Case 1: ptr is NULL, equivalent to malloc(size)
      if (ptr == NULL) {
          return mm_malloc(size);
      }
 
      // Case 2: size is 0, equivalent to free(ptr)
      if (size == 0) {
          mm_free(ptr);
          return NULL;
      }
 
      // 필요한 실제 블록 크기 계산
      size_t asize;
      if (size <= DSIZE * 2)
          asize = MIN_BLOCK_SIZE;
      else
          asize = ALIGN(size + DSIZE);
 
      size_t old_block_size = GET_SIZE(HDRP(ptr)); // 현재 블록 크기
 
      // Optimization 1: 현재 블록 크기가 충분한 경우 (축소 또는 동일)
      if (asize <= old_block_size) {
          if ((old_block_size - asize) >= MIN_BLOCK_SIZE) { // 분할 가능하면
              PUT(HDRP(ptr), PACK(asize, 1));
              PUT(FTRP(ptr), PACK(asize, 1));
              void *remainder_bp = NEXT_BLKP(ptr);
              PUT(HDRP(remainder_bp), PACK(old_block_size - asize, 0));
              PUT(FTRP(remainder_bp), PACK(old_block_size - asize, 0));
              coalesce(remainder_bp); // 남은 블록 가용 리스트에 추가
          }
          // 분할 불필요하거나 불가능하면 그대로 반환
          return ptr;
      }
 
      // Optimization 2: 다음 블록이 가용 상태이고 병합하여 충분한 경우
      void *next_bp = NEXT_BLKP(ptr);
      int next_alloc = GET_ALLOC(HDRP(next_bp));
      size_t next_size = GET_SIZE(HDRP(next_bp));
 
      if (!next_alloc && next_size > 0) {
          size_t combined_size = old_block_size + next_size;
          if (combined_size >= asize) { // 병합하면 충분
              remove_free_block(next_bp); // 병합 전에 다음 블록 제거
 
              if ((combined_size - asize) >= MIN_BLOCK_SIZE) { // 병합 후 분할 가능하면
                  PUT(HDRP(ptr), PACK(asize, 1));
                  PUT(FTRP(ptr), PACK(asize, 1));
                  void *remainder_bp = NEXT_BLKP(ptr);
                  PUT(HDRP(remainder_bp), PACK(combined_size - asize, 0));
                  PUT(FTRP(remainder_bp), PACK(combined_size - asize, 0));
                  coalesce(remainder_bp); // 남은 블록 추가
              } else { // 병합 후 전체 사용
                  PUT(HDRP(ptr), PACK(combined_size, 1));
                  PUT(FTRP(ptr), PACK(combined_size, 1));
              }
              return ptr; // 기존 포인터 반환
          }
      }
 
      // Fallback: 새로 할당, 복사, 해제
      void *newptr = mm_malloc(size);
      if (newptr == NULL) return NULL;
 
      size_t old_payload_size = old_block_size - DSIZE;
      size_t copySize = (size < old_payload_size) ? size : old_payload_size;
      memcpy(newptr, ptr, copySize);
      mm_free(ptr); // 기존 블록 해제
 
      return newptr;
  }

Results for mm malloc:
trace  valid  util     ops      secs  Kops
0       yes   92%    5694  0.000178 31989
1       yes   93%    5848  0.000109 53799
2       yes   95%    6648  0.000172 38674
3       yes   97%    5380  0.000117 45983
4       yes   66%   14400  0.000153 93933
5       yes   90%    4800  0.000632  7594
6       yes   88%    4800  0.000624  7689
7       yes   55%   12000  0.012075   994
8       yes   51%   24000  0.049166   488
9       yes   25%   14401  0.019829   726
10       yes   45%   14401  0.000198 72769
Total          72%  112372  0.083253  1350

Perf index = 43 (util) + 40 (thru) = 83/100

explicit free list + best fit

병합 최적화, 분할 관리 개선, best fit을 활용하여 개선한 버전(feat. lilboy)이다.
best fit을 사용하기 때문에 메모리 관리 측면에서 높은 점수를 받은 듯하다.

/*
* mm-explicit.c - 명시적 가용 리스트(Explicit Free List)를 이용한 malloc 구현.
*
* 가용 블록 구조:
* 헤더(4바이트) | Prev 포인터(8바이트) | Next 포인터(8바이트) | 풋터(4바이트)
* 최소 블록 크기는 24바이트이다.
*
* 할당된 블록 구조:
* 헤더(4바이트) | 유저 데이터(payload, 8바이트 정렬) | 풋터(4바이트)
*
* 가용 리스트 관리:
* - 명시적 이중 연결 리스트 사용.
* - free_listp가 가용 리스트의 첫 번째 블록을 가리킨다.
* - 삽입은 항상 LIFO(최근 삽입) 방식으로 수행한다.
* - 병합(Coalescing) 시 인접한 가용 블록을 합치고, 가용 리스트를 갱신한다.
*/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include <stdint.h> // SIZE_MAX 사용을 위한 헤더 추가

#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 */
    "Explicit Free List Team",
    /* First member's full name */
    "Harry Bovik",
    /* First member's email address */
    "bovik@cs.cmu.edu",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""};

#define ALIGNMENT 8                 // 8바이트 정렬을 위한 크기
#define WSIZE 4                     // 워드 크기 및 헤더/풋터 크기 (4바이트)
#define DSIZE 8                     // 더블 워드 크기 (8바이트)
#define MIN_BLOCK_SIZE 24           // 최소 블록 크기 (헤더+포인터2개+풋터 = 24바이트)
#define CHUNKSIZE (1 << 12)         // 힙 확장 기본 크기 (4096바이트)

#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7) // 8바이트 정렬에 맞게 size를 올림
#define MAX(x, y) ((x) > (y) ? (x) : (y)) // 두 값 중 큰 값을 반환
#define PACK(size, alloc) ((size) | (alloc)) // 블록 크기와 할당 여부를 합쳐 저장

#define GET(p) (*(unsigned int *)(p)) // 주소 p에 저장된 값을 읽음
#define PUT(p, val) (*(unsigned int *)(p) = (val)) // 주소 p에 val을 저장

#define GET_SIZE(p) (GET(p) & ~0x7) // 헤더나 풋터에서 블록 크기를 추출
#define GET_ALLOC(p) (GET(p) & 0x1) // 헤더나 풋터에서 할당 여부를 추출

#define HDRP(bp) ((char *)(bp) - WSIZE) // 블록 포인터 bp로부터 헤더 주소 계산
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // 블록 포인터 bp로부터 풋터 주소 계산
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp))) // 다음 블록의 포인터 계산
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) // 이전 블록의 포인터 계산

#define NEXT_FREE_PTR(bp) (*(void **)(bp)) // 가용 블록의 next 포인터를 읽음
#define PREV_FREE_PTR(bp) (*(void **)((char *)(bp) + DSIZE)) // 가용 블록의 prev 포인터를 읽음
#define SET_NEXT_FREE(bp, ptr) (NEXT_FREE_PTR(bp) = (ptr)) // 가용 블록의 next 포인터를 설정
#define SET_PREV_FREE(bp, ptr) (PREV_FREE_PTR(bp) = (ptr)) // 가용 블록의 prev 포인터를 설정

static char *heap_listp = 0; // 힙의 시작 포인터
static void *free_listp = NULL; // 명시적 가용 리스트의 첫 번째 블록 포인터

static void *extend_heap(size_t words); // 힙을 확장하는 함수
static void *coalesce(void *bp); // 인접 가용 블록들과 병합하는 함수
static void *find_fit(size_t asize); // 주어진 크기에 맞는 가용 블록을 찾는 함수
static void place(void *bp, size_t asize); // 가용 블록에 메모리를 배치하는 함수
static void insert_free_block(void *bp); // 가용 리스트에 블록을 삽입하는 함수
static void remove_free_block(void *bp); // 가용 리스트에서 블록을 제거하는 함수


int mm_init(void)
{
    // 힙의 초기 공간 4워드 할당 (패딩 + 프롤로그 블록 + 에필로그 블록)
    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
        return -1;

    PUT(heap_listp, 0);                            // 패딩 워드
    PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); // 프롤로그 헤더
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); // 프롤로그 풋터
    PUT(heap_listp + (3 * WSIZE), PACK(0, 1));     // 에필로그 헤더
    heap_listp += (2 * WSIZE);                     // heap_listp를 프롤로그 payload로 이동

    free_listp = NULL; // 가용 리스트 포인터 초기화

    // 초기 힙 공간을 CHUNKSIZE만큼 확장
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;

    return 0;
}


static void insert_free_block(void *bp)
{
    // 현재 가용 블록의 next를 기존 free_listp로 설정
    SET_NEXT_FREE(bp, free_listp);
    // 현재 가용 블록의 prev를 NULL로 설정 (가용 리스트 맨 앞이므로)
    SET_PREV_FREE(bp, NULL);

    // 기존 free_listp가 존재하면, 그 블록의 prev를 현재 bp로 설정
    if (free_listp != NULL)
        SET_PREV_FREE(free_listp, bp);

    // free_listp를 현재 bp로 갱신
    free_listp = bp;
}


static void remove_free_block(void *bp)
{
    void* prev_free = PREV_FREE_PTR(bp);
    void* next_free = NEXT_FREE_PTR(bp);

    // 이전 블록이 있으면, 이전 블록의 next를 현재 bp의 next로 설정
    if (prev_free)
         SET_NEXT_FREE(prev_free, next_free);
    else
         free_listp = next_free; // prev가 없으면 free_listp를 next로 갱신

    // 다음 블록이 있으면, 다음 블록의 prev를 현재 bp의 prev로 설정
    if (next_free)
         SET_PREV_FREE(next_free, prev_free);
}



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

    // words 수를 짝수로 맞춰서 8바이트 정렬 유지
    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)); // 새로운 에필로그 블록 설정

    return coalesce(bp); // 확장된 블록을 병합하여 반환
}


void mm_free(void *bp)
{
    if (bp == 0) return; // NULL 포인터 무시

    size_t size = GET_SIZE(HDRP(bp));

    PUT(HDRP(bp), PACK(size, 0)); // 헤더에 가용 표시
    PUT(FTRP(bp), PACK(size, 0)); // 풋터에 가용 표시

    coalesce(bp); // 인접 블록들과 병합
}


static void *coalesce(void *bp)
{
    // 이전 블록과 다음 블록의 할당 상태를 확인
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));

    // 병합 전 이웃 블록들의 원래 포인터를 저장 (나중에 제거할 때 사용)
    void *original_prev_bp = NULL;
    void *original_next_bp = NULL;

    if (!prev_alloc) {
        original_prev_bp = PREV_BLKP(bp); // 이전 블록이 가용이면 저장
    }
    if (!next_alloc) {
        original_next_bp = NEXT_BLKP(bp); // 다음 블록이 가용이면 저장
    }

    if (prev_alloc && next_alloc) { // Case 1: 앞뒤 모두 할당됨
        insert_free_block(bp); // 현재 블록만 가용 리스트에 삽입
        return bp;
    }
    else if (prev_alloc && !next_alloc) { // Case 2: 다음 블록만 가용
        remove_free_block(original_next_bp); // 다음 블록을 가용 리스트에서 제거
        size += GET_SIZE(HDRP(original_next_bp)); // 크기 합치기
        PUT(HDRP(bp), PACK(size, 0)); // 새 크기로 헤더 갱신
        PUT(FTRP(bp), PACK(size, 0)); // 새 크기로 풋터 갱신
    }
    else if (!prev_alloc && next_alloc) { // Case 3: 이전 블록만 가용
        remove_free_block(original_prev_bp); // 이전 블록을 가용 리스트에서 제거
        size += GET_SIZE(HDRP(original_prev_bp)); // 크기 합치기
        PUT(HDRP(original_prev_bp), PACK(size, 0)); // 이전 블록 헤더 갱신
        PUT(FTRP(bp), PACK(size, 0)); // 현재 블록 풋터 갱신
        bp = original_prev_bp; // 병합 결과 포인터를 이전 블록으로 변경
    }
    else { // Case 4: 앞뒤 모두 가용
        remove_free_block(original_prev_bp); // 이전 블록 제거
        remove_free_block(original_next_bp); // 다음 블록 제거
        size += GET_SIZE(HDRP(original_prev_bp)) + GET_SIZE(HDRP(original_next_bp)); // 세 블록 크기 합치기
        PUT(HDRP(original_prev_bp), PACK(size, 0)); // 합친 크기로 헤더 갱신
        PUT(FTRP(original_next_bp), PACK(size, 0)); // 합친 크기로 풋터 갱신
        bp = original_prev_bp; // 병합 결과 포인터를 이전 블록으로 변경
    }

    insert_free_block(bp); // 병합 결과 블록을 가용 리스트에 삽입
    return bp;
}


void *mm_malloc(size_t size)
{
    size_t asize;      // 정렬 및 오버헤드 포함 조정된 블록 크기
    size_t extendsize; // 힙을 확장할 크기
    char *bp;

    if (size == 0)
        return NULL; // 요청 크기가 0이면 무시

    if (size <= DSIZE * 2)
        asize = MIN_BLOCK_SIZE; // 최소 블록 크기 (24바이트)
    else
        asize = ALIGN(size + DSIZE); // 요청 크기 + 헤더/풋터 오버헤드 추가 후 정렬

    // 가용 리스트에서 적절한 블록을 찾기
    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize); // 찾은 블록에 배치
        return bp;
    }

    // 적절한 블록이 없다면 힙 확장
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
        return NULL; // 확장 실패 시 NULL 반환

    place(bp, asize); // 확장된 블록에 배치
    return bp;
}

static void *find_fit(size_t asize)
{
    void *bp;
    void *best_fit_bp = NULL;  // 가장 적합한 블록의 포인터
    size_t min_size = SIZE_MAX;  // 충분한 크기 중 가장 작은 크기 (초기값은 최대값으로 설정)

    // 가용 리스트를 순차 탐색하여 가장 적합한 블록을 찾음 (Best Fit)
    for (bp = free_listp; bp != NULL; bp = NEXT_FREE_PTR(bp)) {
        size_t current_size = GET_SIZE(HDRP(bp));
        
        // 요청 크기에 맞고, 현재까지 찾은 최소 크기보다 작은 블록을 발견한 경우
        if (asize <= current_size && current_size < min_size) {
            min_size = current_size;  // 최소 크기 갱신
            best_fit_bp = bp;         // 최적 블록 포인터 갱신
            
            // 정확히 맞는 크기를 찾았다면 즉시 반환 (완벽한 Best Fit)
            if (current_size == asize) {
                return best_fit_bp;
            }
        }
    }
    
    return best_fit_bp;  // 가장 적합한 블록 반환 (없으면 NULL)
}

static void place(void *bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp)); // 현재 가용 블록 크기

    remove_free_block(bp); // 가용 리스트에서 현재 블록 제거

    if ((csize - asize) >= MIN_BLOCK_SIZE) { // 분할할 수 있는 경우
        PUT(HDRP(bp), PACK(asize, 1)); // 요청 크기로 헤더 설정 (할당 표시)
        PUT(FTRP(bp), PACK(asize, 1)); // 요청 크기로 풋터 설정 (할당 표시)

        // 남은 부분을 새 가용 블록으로 설정
        void* next_bp = NEXT_BLKP(bp);
        PUT(HDRP(next_bp), PACK(csize - asize, 0));
        PUT(FTRP(next_bp), PACK(csize - asize, 0));

        coalesce(next_bp); // 남은 가용 블록 병합 및 삽입
    }
    else { // 블록 전체를 할당
        PUT(HDRP(bp), PACK(csize, 1)); // 전체 크기로 헤더 설정
        PUT(FTRP(bp), PACK(csize, 1)); // 전체 크기로 풋터 설정
    }
}


/**
  * mm_realloc - 메모리 블록 재할당
  * 이전 블록 및 다음 블록과의 병합을 통한 최적화 추가
  */
void *mm_realloc(void *ptr, size_t size)
 {
     // Case 1: ptr is NULL, equivalent to malloc(size)
     if (ptr == NULL) {
         return mm_malloc(size);
     }

     // Case 2: size is 0, equivalent to free(ptr)
     if (size == 0) {
         mm_free(ptr);
         return NULL;
     }

     // 필요한 실제 블록 크기 계산
     size_t asize;
     if (size <= DSIZE * 2)
         asize = MIN_BLOCK_SIZE;
     else
         asize = ALIGN(size + DSIZE);

     size_t old_block_size = GET_SIZE(HDRP(ptr)); // 현재 블록 크기

     // Optimization 1: 현재 블록 크기가 충분한 경우 (축소 또는 동일)
     if (asize <= old_block_size) {
         if ((old_block_size - asize) >= MIN_BLOCK_SIZE) { // 분할 가능하면
             PUT(HDRP(ptr), PACK(asize, 1));
             PUT(FTRP(ptr), PACK(asize, 1));
             void *remainder_bp = NEXT_BLKP(ptr);
             PUT(HDRP(remainder_bp), PACK(old_block_size - asize, 0));
             PUT(FTRP(remainder_bp), PACK(old_block_size - asize, 0));
             coalesce(remainder_bp); // 남은 블록 가용 리스트에 추가
         }
         // 분할 불필요하거나 불가능하면 그대로 반환
         return ptr;
     }

     // Optimization 2: 이전 블록이 가용 상태이고 병합하여 충분한 경우
     void *prev_bp = PREV_BLKP(ptr);
     int prev_alloc = GET_ALLOC(FTRP(prev_bp));
     size_t prev_size = GET_SIZE(HDRP(prev_bp));
     
     if (!prev_alloc && prev_size > 0) {
         size_t combined_size = old_block_size + prev_size;
         remove_free_block(prev_bp); // 병합 전에 이전 블록 제거
         
         size_t old_payload_size = old_block_size - DSIZE;
         
         // 데이터를 이전 블록으로 이동 (memcpy는 겹치는 영역에서 안전하지 않음)
         memmove(prev_bp, ptr, old_payload_size);
         
         if ((combined_size - asize) >= MIN_BLOCK_SIZE) { // 병합 후 분할 가능하면
             PUT(HDRP(prev_bp), PACK(asize, 1));
             PUT(FTRP(prev_bp), PACK(asize, 1));
             void *remainder_bp = NEXT_BLKP(prev_bp);
             PUT(HDRP(remainder_bp), PACK(combined_size - asize, 0));
             PUT(FTRP(remainder_bp), PACK(combined_size - asize, 0));
             coalesce(remainder_bp); // 남은 블록 추가
         } else { // 병합 후 전체 사용
             PUT(HDRP(prev_bp), PACK(combined_size, 1));
             PUT(FTRP(prev_bp), PACK(combined_size, 1));
         }
         return prev_bp; // 병합된 이전 블록 포인터 반환
     }

     // Optimization 3: 다음 블록이 가용 상태이고 병합하여 충분한 경우
     void *next_bp = NEXT_BLKP(ptr);
     int next_alloc = GET_ALLOC(HDRP(next_bp));
     size_t next_size = GET_SIZE(HDRP(next_bp));

     if (!next_alloc && next_size > 0) {
         size_t combined_size = old_block_size + next_size;
         if (combined_size >= asize) { // 병합하면 충분
             remove_free_block(next_bp); // 병합 전에 다음 블록 제거

             if ((combined_size - asize) >= MIN_BLOCK_SIZE) { // 병합 후 분할 가능하면
                 PUT(HDRP(ptr), PACK(asize, 1));
                 PUT(FTRP(ptr), PACK(asize, 1));
                 void *remainder_bp = NEXT_BLKP(ptr);
                 PUT(HDRP(remainder_bp), PACK(combined_size - asize, 0));
                 PUT(FTRP(remainder_bp), PACK(combined_size - asize, 0));
                 coalesce(remainder_bp); // 남은 블록 추가
             } else { // 병합 후 전체 사용
                 PUT(HDRP(ptr), PACK(combined_size, 1));
                 PUT(FTRP(ptr), PACK(combined_size, 1));
             }
             return ptr; // 기존 포인터 반환
         }
     }
     
     // Optimization 4: 이전 블록과 다음 블록 모두 가용하고 병합하여 충분한 경우
     if (!prev_alloc && !next_alloc && (prev_size + old_block_size + next_size) >= asize) {
         size_t combined_size = prev_size + old_block_size + next_size;
         remove_free_block(prev_bp); // 이전 블록 제거
         remove_free_block(next_bp); // 다음 블록 제거
         
         size_t old_payload_size = old_block_size - DSIZE;
         
         // 데이터를 이전 블록으로 이동
         memmove(prev_bp, ptr, old_payload_size);
         
         if ((combined_size - asize) >= MIN_BLOCK_SIZE) { // 병합 후 분할 가능하면
             PUT(HDRP(prev_bp), PACK(asize, 1));
             PUT(FTRP(prev_bp), PACK(asize, 1));
             void *remainder_bp = NEXT_BLKP(prev_bp);
             PUT(HDRP(remainder_bp), PACK(combined_size - asize, 0));
             PUT(FTRP(remainder_bp), PACK(combined_size - asize, 0));
             coalesce(remainder_bp); // 남은 블록 추가
         } else { // 병합 후 전체 사용
             PUT(HDRP(prev_bp), PACK(combined_size, 1));
             PUT(FTRP(prev_bp), PACK(combined_size, 1));
         }
         return prev_bp; // 병합된 이전 블록 포인터 반환
     }

     // Fallback: 새로 할당, 복사, 해제
     void *newptr = mm_malloc(size);
     if (newptr == NULL) return NULL;

     size_t old_payload_size = old_block_size - DSIZE;
     size_t copySize = (size < old_payload_size) ? size : old_payload_size;
     memcpy(newptr, ptr, copySize);
     mm_free(ptr); // 기존 블록 해제

     return newptr;
 }

Results for mm malloc:
trace  valid  util     ops      secs  Kops
0       yes   99%    5694  0.000122 46520
1       yes   99%    5848  0.000136 43000
2       yes   99%    6648  0.000138 48209
3       yes   99%    5380  0.000114 47110
4       yes   66%   14400  0.000157 92013
5       yes   96%    4800  0.002253  2130
6       yes   95%    4800  0.002234  2149
7       yes   55%   12000  0.012237   981
8       yes   51%   24000  0.048316   497
9       yes   40%   14401  0.000267 53836
10       yes   45%   14401  0.000196 73662
Total          77%  112372  0.066170  1698

Perf index = 46 (util) + 40 (thru) = 86/100

segregated free list + first fit

Segregated Free List를 사용할 때는 각 리스트 내에서 First Fit 전략을 사용하는 것이 가장 권장된다. 이미 크기별로 나누어져 탐색 범위가 좁아졌기 때문에, 리스트 내에서 처음 맞는 블록을 즉시 사용하는 First Fit이 가장 빠르고 간단하며, 메모리 이용률도 크게 나쁘지 않다. Best Fit은 내부 단편화 관리에 이점이 있지만 탐색 시간이 길어 성능 이점을 일부 상쇄할 수 있으며, Next Fit은 복잡성이 높아 비효율적이다.