👩‍💻Dynamic Memory Allocation in the Heap : Malloc & free
(힙공간에서의 동적메모리 할당)
👩‍💻computer systems 9장
👩‍💻 implicit list , explicit list & seglist allocator

1. Heap Allocation

• 메모리 구조를 추상화한 거를 보면 [스택]-[힙]-[코드 :[statics]-[리터럴]-[텍스트]]로 이루어져 있다.
• 이번 malloc-lab에서는 동적 데이터 구조와 malloc,free,new,gc(garbage collector)의 개념을 활용하여 런타임 시의 메모리 관리에 대해서 알아보자.

2. Allocator

1)블록 단위 왜 사용할까?

• 페이지 object 하나하나를 할당하기에는 너무 큼직함.
  • object가 들어갈 수 있는 공간이 없거나 할당 공간이 너무 남아돌아서 다음 object 할당에 비효율적임.
    
• 대신 좀 더 유연하게 이런 상황들을 대처할 수 있는 word-aligned블록을 활용한다.
• 위의 할당된블록들 (⬛어두운 블록) & free블록(⬜흰블록)들은 각각 malloc과 free를 통해서 지정 가능

2) Dynamic Memory Allocation

(1) 동적 메모리 allocator는 필요할 때만 memory블록을 할당한다

(2) Explicit vs Implicit Memory allocator

2-1 Explicit : aplication allocates + frees space

• ex. C: malloc & free

2-2 Implicit : apllication allocates only!

• ex. Java,ML, Lisp: gc(garbage collection)
• 👉Implicit memory allocator에 관해서는 여기로!

3) Explicit Memory Allocator :malloc & free

(1) 기본 구조

• size : 할당을 하기 위해 필요한 연속된 바이트의 크기
• void* : size바이트 크기 이상에 해당되는 새로이 할당한 블록을 가르키는 포인터
• void* ptr: free를 해주기 위한 포인터
• 할당 성공시 : size바이트만큼 8바이트 단위로 이어진 메모리 블록을 가르키는 포인터 리턴
• 실패시 : NULL(0)와 errno 리턴
• malloc 예시
  

(2) Allocation 예시 (64 비트 word)

• p1은 4바이트 크기의 word할당
• p2는 5바이트 크기의 word할당
• p3는 6바이트 크기의 word할당
• free(p2)는 p2포인터가 가르키는 블록을 free(반환)
• p4는 2바이트 크기의 word 할당

(3) Allocator 사용시 고려할 점들

1. 개발자가 직접 할당/free 공간을 지정하지는 않음!

• 대신 할당/free해야하는 공간의 크기, 언제 할당해야하거나 free해야하는 지에 대한 시점을 지정한다.

2. 빠른 할당

• 초(sec) 당 malloc 또는 초(sec)당 말록한 바이트을 최소화하는 것을 목표로 하자!
• 이상적으로는 상수시간이 걸리도록, O(n)이 되지 않도록!

3. Memory utilization 최대화

• 위처럼 이상적으로 힙영역에 빈 공간없이 사용될 거 같지만..
• 힙영역 대부분에는 불필요한 프로그램 데이터가 저장되어 있다. 최대한 공간을 낭비하지 않도록 하자.
• 👿 fragmentation (사용되고 있지 않음에도 할당할 수 없는 공간)을 만들지 말자!

  🤔 최적화를 위해 thoughput (unit 당 완료한 request 개수)와 memory utilization간 조율할 것인가?

3. fragmentation

1) 종류

internal fragmentation	external fragmentation
payload<block	free공간 하나하나 < word가 할당될만한 연속된 공간<=free공간들의 총합
metadata, alignment, policy에 따라 발생 가능	할당또는 free request 양상에 따라서 발생 가능
☑️ 힙 데이터구조 유지할 때 오버헤드 시 발생가능
☑️ alignment 중 padding에 의해 발생가능
☑️ policy : 블록 split하지 않겠다고 결정 시 등 등
📌 placement policy: first-fit, next-fit, best-fit (seglist가 best-fit사용 시 시간 절약 제일 많이 함!)
📌 splitting policy: 항상해줄까? 가끔해줄까? 사이즈에 따라 해줄까?
📌 coalescing policy: immediate vs deferred (당장?나중에?)
😊 오로지 이전의 request 패턴에 의해서 발생 가능하므로 예측 & 해결이 비교적 쉬움	😫 미래 request에 의해 발생하므로 예측 & 해결이 어려움

2. Internal vs External fragmentation 한눈에 비교하기

• p1에서 4바이트 word 할당
• p2에서 5바이트 word 할당
• p3에서 6바이트 word 할당
• p2를 free해줌
• p4는 6바이트. 할당되지 않은 공간의 합은 7로 충분하지만 연속된 공간은 부족함! ➡️ External fragmentation

---

4. 구현 시 고려할 포인트들

🎯task 1. 포인터만(free(p)) 주어졌을 때 얼마만큼 free를 해줘야하는 지 결정하는 방법?

🎯task 2. free block을 tracking 방법에는 뭐가 있을까?

🎯task 3. 할당할 블록을 골라줄 때 어떻게 해야 제일 효율적일까? (ft. placement)

🎯task 4. 할당된 free block보다 크기가 작은 구조체 (structure)에서 여분공간(extra space)을 어떻게 활용해야할까? (ft.splitting)

🎯task 5. 블록을 free시켜주면 나중에 사용가능하도록 만들어줘야하는데 reinsert 여부 결정(ft. merge)

5. 구현 포인트 solutions

[task 1] 얼마만큼을 free해줘야할 지 어떻게 알까?

💡 Solution: [Standard] data payload 앞의 header word 블록에 길이 저장

• p0에서 4바이트 word를 할당해줄 때
• 블록의 크기를 나타내는 metadata를 헤더(Header)에 추가해주기 (대신 추가적인 할당공간 필요함!)

[task 2] Free block을 어떻게 track할까?

💡 Solution: 대표적인 방법은 implicit list, explicit list, seglist 활용 등이 있다.

👩‍ 💻malloc-lab에서 위의 세가지 방법으로 free block을 추적하는 방법들을 구현해볼 것이다. cf. 크기별로 블록 sort하기 (RBtree와 같은 균형트리를 사용+ free블록 각각에 포인터 + 길이를 key로)

💡 Splitting, boundary tags, coalescing은 모든 allocator에서 공통이다.

Implicit Free List

1. Implicit Free List : Block format으로 track

• 모든 블록 연결
• 1 word크기의 블록에서
  • 블록의 metadata
    • 블록의 크기에 대한 정보
    • 할당 상태 (🅰️) : Least Significant Bit (LSB) 가 1일때는 할당됨, 0일 때는 free인 상태
    • 블록의 크기가 항상 2의 제곱이라면 같은 word에 비트를 넣을 수 있음 (size 읽을 때 lower order bit 숨길 수 있음)

2. Implicit Free List : Heap format 으로 track

• 힙의 시작에 word시작이 블록의 일부가 될 수 없음.
• 16바이트(2word)의 제곱으로 블록 size가 정해지고, payload는 16바이트 단위로 들어간다.
• 따라서 internal fragmentation 발생가능
• 블록 Header에 블록 사이즈와 블록 할당 여부가 들어있다 (metadata)
• 힙의 끝에는 size가 0인 header같아보이는 블록이 할당
  

[task 3] 할당할 블록을 골라줄 때 어떻게 해야 제일 효율적일까? (ft. placement)

💡 Solution: Implicit Free List : Free 블록 찾는 법

• First fit : 리스트를 처음부터 순회하면서 size가 맞는 첫번째 free블록 선택
• Next fit : 이전 순회를 마쳤던 곳에서 first-fit 수행
• Best fit : 리스트 전체를 순회하면서 size-free블록 간의 바이트가 가장 적게 남는 곳을 선택

[task 4] 할당된 free block보다 크기가 작은 구조체 (structure)에서 여분공간(extra space)을 어떻게 활용해야할까? (ft.splitting)

💡 Solution: Implicit Free List : Free 블록 할당하는 법 (ft.블록 split)

• 할당 상태 : 할당된블록들 (⬛어두운 블록) & free블록(⬜흰블록)& 🟨포인터 p가 가르키는 블록(할당하려는 블록)
• 48비트(6바이트)의 할당되지 않은 공간이 있을 때
• p에서 24비트(3바이트)+1바이트(metadata포함) 크기의 공간을 할당하고 싶다고 하자.
• 할당된 공간 <= free 공간일 때 공간을 다 쓰기 vs. split를 해야 효율적일까?

[task 5] 할당된 free block보다 크기가 작은 구조체 (structure)에서 여분공간(extra space)을 어떻게 활용해야할까? (ft.splitting)

💡 Solution: Implicit Free List : 할당된 블록을 Free하는 법

• 할당 상태 : 할당된블록들 (⬛어두운 블록) & free블록(⬜흰블록) & 🟨포인터 p가 가르키는 블록(free하려는 블록)
• free(p) : 포인터 p가 가르키는 위치를 free해주고
• malloc(40) : 40비트(5바이트)+(1바이트:metadata포함)크기를 할당하려고 할 때 External fragmentation 발생! (공간은 있는데 하나의 블록이 아님!)

[task 6] 블록을 free시켜주면 나중에 사용가능하도록 만들어줘야하는데 reinsert

💡 Solution: Implicit Free List : Free했던 블록들 합쳐주는(Coalescing) 법

• free(p) : p 포인터가 가르키는 위치의 블록을 free했을 때, 다음 free블록들과 coalesce(합)해주기!
  🤔 External fragmentation 방지할 수 있겠네! 그럼 앞에 있는 free블록도 합쳐주면 공간 더 생겨서 좋은 거 아님? 그래서 다음이 나옴

6-1. 양방향 Coalescing (bidirectional):

• footer에 boundary tag를 포함시키기
  • boundary tag : header를 복제해서 free 블록의 끝에 붙이기
  • But, 그림과 같이 역순회가 가능하지만 추가적인 공간이 필요해짐

6-2. 상수시간으로 Coalescing (constant-time):

👀constant time coalescing 한눈에 보기

🤗현재 free된 블록 기준으로 앞뒤로 free인 블록 존재 여부에 따라 coalesce 상태 비교

7. Implicit Free List : 요약

구현	단순함
할당하는데 시간복잡도	O(heap에 있는 블록의 수)
free하는데 시간복잡도	O(1)
memory utilization	placement policy에 따라ㅓ
사용도	흔히 사용 X (특수한 application 목적만)

---

Explicit Free List

• free 블록들 간에 포인터를 사용해서 가장 적절한 free 블록 빠르게 찾기
• 포인터들을 연결하기 위해 데이터 공간 사용
• 일반적으로 이중연결 리스트으로 구현
• coalsce하기 위한 boundary tag 여전히 필요
  
• 연결된 순서가 블록 순서와 블록 순서와 불일치 할 수 있음!

1. Allocated blocks vs Free block

• 할당된 블록의 구조
• 블록의 사이즈 + 할당상태를 나타낼 header와 footer
• payload (application data)
• 부가적 패딩
• free 블록의 구조
• 블록의 사이즈 + 할당상태를 나타낼 header와 footer
• 다음 주소를 가르키는 포인터, 이전 주소를 가르키는 포인터 ➡️ 모든 블록의 implicit list 대신 free block에 대한 explicit list 활용
• 즉, implicit list에서는 implicitly(암시적으로)블록의 크기를 갖고 free 블록의 위치를 추적했지만, explicit free list는 할당된 블록은 implicit free list와 동일한 구조지만 free block은 전후를 가르킬 포인터로 explicitly(명시적으로) free 블록들을 추적함!

2. List vs. Memory order

3. Explicit Free List: Free 블록 할당하는 법

• explicit free list의 핵심은 free인 블록들 간의 이중 연결 리스트로 free인 블록을 track해주는 것!
• 리스트에서 할당하고자하는 위치의 포인터를 앞과 뒤가 가르키도록 해주면 됨.
• 할당된 블록(⬛어두운 블록)을 제외한 split 이후의 free블록(⬜흰블록)을 향해 predecessor와 successor의 포인터가 가르키도록 해주기
  

4. Explicit Free List: Free 할당된 블록을 Free하는 법

➕ Insertion Policy : free해준 블록을 free list 어디에 넣어줘야할까?

Policy	LIFO (last in first out)	Address-ordered
장점	단순하고 시간복잡도가 O(1)	address-order보다 fragmentation이 좋다는 연구결과 있음
단점	address-order보다 fragmentation이 심하다는 연구결과 있음	free해준 블록 삽입 시 시간복잡도 O(n)

4-1. LIFO policy

(1) 할당된 두 블록 사이일 때

free해준 블록을 free list의 Head에 위치시키기

---

(2) free블록과 할당된 블록 사이일 때

predecessor 블록을 잘라내기(splice) ➡️ 두 메모리 블록 합쳐(coalsce)주기 ➡️ 새 블록을 free list의 Head에 위치시키기 (양쪽 둘다 혹은 양쪽 한쪽에다가 모두 가능)

---

(3) 할당된 블록과 free블록 사이일 때

successor 블록을 잘라내기(splice) ➡️ 두 메모리 블록 합쳐(coalsce)주기 ➡️ 새 블록을 free list의 Head에 위치시키기

---

(4) free인 두 블록 사이일 때

successor 블록와 predecessor 블록 잘라내기(splice) ➡️ 세 메모리 블록 합쳐(coalsce)주기 ➡️ 새 블록을 free list의 Head에 위치시키기

4-2. Address-order policy

5. Explicit Free List : 요약

구현	비교적 단순함 (리스트 splice해줘야해서 implicit list보다 좀 더 복잡)
할당하는데 시간복잡도	O(free 블록의 개수) cf.implicit free는 모든 블록
free하는데 시간복잡도	O(1)
memory utilization	placement policy에 따라 & larger minimum block size (next/prev) vs. implicit list
사용도	흔히 사용 O (+optimization을 더함)

• linked list의 주 사용 목적은 segregated free list와 함께 사용하기 위함임!
  • 여러개의 다양한 size 클래스 혹은 다른 object 타입을 담기 위한 linked list를 사용해서 segregated free list 구현

---

Seglist(Segregated free list) Allocators

• 각 size bracket(class)이 각자 free list를 가지고 있음
  
• Explicit free list 사용 시보다 빠르게 적절한 크기의 free 블록 찾도록 (best-fit allocation)
• 작은 size는 각각의 size class가 있고, 큰 size는 size class가 2의 제곱 크기로 있음

1. Simple Segregated Storage

• 각 size class를 위한 heap & free list (같은 리스트에 있는 각 블록들은 같은 사이즈임)
• split ❌
• size가 n인 블록을 할당하기 위해서
• free list에서 size가 n이 비어 있지 않다면 ➡️ 리스트의 첫 블록에 할당 (리스트는 implicit일수도 explicit일 수도 있음)
• free list가 비어있다면 ➡️ 새로운 페이지 가져오기 ➡️ 페이지 내의 모든 블록을 바탕으로 새로운 free list생성➡️ list의 첫 블록에 할당하기
• 시간 복잡도가 상수시간이다.
• 블록 free하기 : free list에 추가하기
• 단점 : 빠르지만 fragmentation 심각할 수 있음

2. Segregated Fits (simpe segregated storage 개선 ver.)

• free list 배열들로 이루어져 있음. 각 배열들은 특정 size class을 위한 배열들이다.
• *size가 n인 블록을 할당하기 위해서
  • 적절한 블록 사이즈의 free list 탐색
  • 적절한 블록을 발견하면
    • 블록 split + 적절한 리스트에 fragment 담기(선택 사항)
    • 블록 발견 실패 시 : 다음으로 큰 사이즈 클래스에서 탐색
    • 적절한 크기의 블록을 찾을 때까지 반복
• 블록 free해주기
  • Coalesce + 적절한 리스트에 넣기 (선택 사항)
• 성능
  • sequential fits 보다 탐색에서 빠름
  • simple segregated storage에서 발생하는 fragmentation을 조절함 (Best fit과 utilization 성능 비슷)
  • Coalscing 시 free블록 탐색 시간이 증가할 수 있음 (어떤 size class가 적절한 지 탐색하기 때문) ➡️ deferred coalescing을 하면 도움이 될 수 있음 (바로바로 coalesce하지 말고 나중에~)

---

6. 구현

깃허브에서 보기

• 👉naive 방식
• 👉explicit list 방식
• 👉implicit list 방식
• 👉seg list 방식

1. naive

📌성능요약
: Perf index = 44 (util) + 9 (thru) = 54/100

/*
 * mm.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"

// mdriver 구동을 위한 team정보 struct 설정
team_t team = {
    /* Team name */

    "team 1",
    /* First member's full name */
    "hyemin Pyo",
    /* First member's email address */
    "pyolovely01@gmail.com",

    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""};

/* ================================ Macros ===================================== */
// 각종 변수,함수 설정
#define WSIZE 4 // word and header footer 사이즈를 byte로.
#define DSIZE 8 // double word size를 byte로
#define CHUNKSIZE (1<<12)

/* ------------------------------ Basic Utility ------------------------------- */

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

// size를 pack하고 개별 word 안의 bit를 할당 (size와 alloc을 비트연산)
#define PACK(size,alloc) ((size)| (alloc))

/* address p위치에 words를 read와 write를 한다. */
#define GET(p) (*(unsigned int*)(p))
#define PUT(p,val) (*(unsigned int*)(p)=(val))

// address p위치로부터 size를 읽고 field를 할당
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)

/* given block ptr bp, 그것의 header와 footer의 주소를 계산*/
#define HDRP(bp) ((char*)(bp) - WSIZE)
#define FTRP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

/* GIVEN block ptr bp, 이전 블록과 다음 블록의 주소를 계산*/
#define NEXT_BLKP(bp) ((char*)(bp) + GET_SIZE(((char*)(bp)-WSIZE)))
#define PREV_BLKP(bp) ((char*)(bp) - GET_SIZE(((char*)(bp) - DSIZE)))

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

    if (prev_alloc && next_alloc){ // case 1 - 이전과 다음 블록이 모두 할당 되어있는 경우, 현재 블록의 상태는 할당에서 가용으로 변경
        return bp;
    }
    else if (prev_alloc && !next_alloc){ // case2 - 이전 블록은 할당 상태, 다음 블록은 가용상태. 현재 블록은 다음 블록과 통합 됨.
        size += GET_SIZE(HDRP(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)));
        PUT(FTRP(bp), PACK(size,0)); 
        PUT(HDRP(PREV_BLKP(bp)), PACK(size,0)); // 헤더를 이전 블록의 BLKP만큼 통합?
        bp = PREV_BLKP(bp);
    }
    else { // case 4- 이전 블록과 다음 블록 모두 가용상태. 이전,현재,다음 3개의 블록 모두 하나의 가용 블록으로 통합.
        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;
    /* alignment 유지를 위해 짝수 개수의 words를 Allocate */
    size = (words%2) ? (words+1) * WSIZE : words * WSIZE;
    if ( (long)(bp = mem_sbrk(size)) == -1){
        return NULL;
    }

    /* free block 헤더와 푸터를 init하고 epilogue 헤더를 init*/
    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 추가

    /* 만약 prev block이 free였다면, coalesce해라.*/
    return coalesce(bp);
}

static char *heap_listp;
/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
 /* create 초기 빈 heap*/
    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);

    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)); // header, footer 들을 free 시킨다.
    PUT(FTRP(bp), PACK(size,0));
    coalesce(bp);
}


static void *find_fit(size_t asize){ // first fit 검색을 수행
    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; 
}

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));
    }
} 
/* * 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; // heap에 맞는 fit이 없으면 확장하기 위한 사이즈
    char *bp;

    /* 거짓된 요청 무시*/
    if (size == 0) return NULL;

    /* overhead, alignment 요청 포함해서 블록 사이즈 조정*/
    if (size <= DSIZE){
        asize = 2*DSIZE;
    }
    else {
        asize = DSIZE* ( (size + (DSIZE)+ (DSIZE-1)) / DSIZE );

    }
    /* fit에 맞는 free 리스트를 찾는다.*/
    if ((bp = find_fit(asize)) != NULL){
        place(bp,asize);
        return bp;
    }

    /* fit 맞는게 없다. 메모리를 더 가져와 block을 위치시킨다.*/
    extendsize = MAX(asize,CHUNKSIZE);
    if ( (bp=extend_heap(extendsize/WSIZE)) == NULL){
        return NULL;
    }
    place(bp,asize);
    return bp;
}

/*
 * mm_free - Freeing a block does nothing.
 */

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
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 = GET_SIZE(HDRP(oldptr));  
    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

2. Implicit list

📌성능요약
: Perf index = 46 (util) + 9 (thru) = 55/100

/*
 * mm.c - implicit free list based malloc package 
 * 
 * Block Format: Minimum size is 8 bytes.
 *  - Allocated-Block Format: [Header - Payload]
 *  - Free-Block Format: [Header - (Space) - Footer]
 * Header/Footer: 1-word holds [block size, prev-bit, alloc-bit]
 *  - prev-bit: is previous block allocated.
 *  - alloc-bit: is current block allocated.
 * List Format: implicit free list
 *    [Head-Block[1] | Regular-Blocks(F/A) ...| Tail-Block[1]]
 * Placement Policy: using first-fit algorithm.
 * Split Policy: always split if remainder is greater than 8 bytes
 * Coalescing Policy: bi-direction coalescing after each unallocation
 * 
 * realloc: split if new size is less than the block size by 8 bytes
 *          allocate-copy-free if new size is greater than block size
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

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

/* =============================================================================== */

team_t team = {
  /*team*/
  "team 1",
  /* First member's full name */
  "Hyemin Pyo",
  /* First member's email address */
  "pyolovely01@gmail.com",
  /* Second member's full name (leave blank if none) */
  "",
  /* Second member's email address (leave blank if none) */
  ""
};

/* ========================== Function Prototype =============================== */

inline static void* resize_block(void*, size_t);
inline static void* reallocate_block(void*, size_t);
inline static void* extend_heap(size_t);
inline static void* first_fit(size_t);
inline static void* best_fit(size_t);
inline static void* find_fit(size_t);
inline static void place(void*, size_t);
inline static void* coalesce(void*);
inline static void set_prev_bit(void*, size_t);

/* ========================== Compilation Flags =============================== */

// #define DEBUG                 /* uncomment to turn-on heap checker */

#ifdef DEBUG
  static void mm_check(int line);
  #define heap_check(line) (mm_check(line))
#else
  #define heap_check(line)
#endif

/* ================================ Macros ===================================== */

#define WSIZE 4                           /* Word size in bytes */
#define DSIZE 8                           /* Double word size in bytes */
#define CHUNKSIZE (1<<8)                  /* Minimum heap allocation size */
#define MIN_BLOCK_SIZE 8                  /* Minimum block size */
#define ALIGNMENT 8                       /* Payload Alignment */
#define WTYPE u_int32_t                   /* Word type */
#define BYTE char                         /* Byte type */

/* ------------------------------ Basic Utility ------------------------------- */

/* Move the address ptr by offset bytes */
#define MOVE_BYTE(ptr, offset) ((WTYPE *)((BYTE *)(ptr) + (offset)))
/* Move the address ptr by offset words */
#define MOVE_WORD(ptr, offset) ((WTYPE *)(ptr) + (offset))
/* Read a word from address ptr */
#define READ_WORD(ptr) (*(WTYPE *)(ptr))
/* Write a word value to address ptr */
#define WRITE_WORD(ptr, value) (*(WTYPE *)(ptr) = (value))
/* rounds up size (in bytes) to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
/* Get the maximum of x and y */
#define MAX(x, y) ((x) > (y)? (x) : (y))
/* Get the minimum of x and y */
#define MIN(x, y) ((x) < (y)? (x) : (y))

/* ----------------------- Header/Footer Macros ---------------------------- */

/* Pack the size, prev-allocated and allocation bits into a word */
#define PACK(size, prev, alloc) ((size) | (prev << 1) | (alloc))
/* Read the size from header/footer word at address Hptr */
#define READ_SIZE(Hptr) (READ_WORD(Hptr) & ~0x7)
/* Read the allocation-bit from header/footer word at address Hptr */
#define READ_ALLOC(Hptr) (READ_WORD(Hptr) & 0x1)
/* Read the prev-allocated-bit from header/footer word at address Hptr */
#define READ_PREV_ALLOC(Hptr) ((READ_WORD(Hptr) & 0x2) >> 1)
/* Write the size, prev-allocated and allocation bits to the word at address Hptr */
#define WRITE(Hptr, size, prev, alloc)\
  (WRITE_WORD((Hptr), PACK((size), (prev), (alloc))))

/* Write the size to the word at address Hptr */
#define WRITE_SIZE(Hptr, size)\
  (WRITE((Hptr), (size), READ_PREV_ALLOC(Hptr), READ_ALLOC(Hptr)))

/* Write allocation-bit to the word at address Hptr */
#define WRITE_ALLOC(Hptr, alloc)\
  (WRITE((Hptr), READ_SIZE(Hptr), READ_PREV_ALLOC(Hptr), alloc))

/* Write prev-allocated-bit to the word at address Hptr */
#define WRITE_PREV_ALLOC(Hptr, prev)\
  (WRITE((Hptr), READ_SIZE(Hptr), prev, READ_ALLOC(Hptr)))

/* ---------------------------- Payload Macros ------------------------------ */

/* Get the header-word pointer from the payload pointer pp */
#define HEADER(pp) (MOVE_WORD(pp, -1))
/* Get the footer-word pointer from the payload pointer pp */
#define FOOTER(pp) (MOVE_BYTE(pp, (BLOCK_SIZE(pp) - DSIZE)))
/* Get next block payload pointer from pp (current payload pointer) */
#define NEXT_BLOCK(pp) (MOVE_BYTE(pp, BLOCK_SIZE(pp)))
/* Get previous block payload pointer from pp (current payload pointer) */
#define PREV_BLOCK(pp) (MOVE_BYTE(pp, - READ_SIZE(MOVE_WORD(pp, -2))))
/* Read the block size at the payload pp */
#define BLOCK_SIZE(pp) (READ_SIZE(HEADER(pp)))
/* Read the payload size at pp */
#define PAYLOAD_SIZE(pp) (BLOCK_SIZE(pp) - WSIZE)
/* Gets the block allocation status (alloc-bit) */
#define GET_ALLOC(pp) (READ_ALLOC(HEADER(pp)))
/* Gets the previous block allocation status (prev-alloc-bit) */
#define GET_PREV_ALLOC(pp) (READ_PREV_ALLOC(HEADER(pp)))
/* Check if the block at the payload pp is free */
#define IS_FREE(pp) (!(GET_ALLOC(pp)))
/* Check if the previous block of the payload pp is free */
#define IS_PREV_FREE(pp) (!(GET_PREV_ALLOC(pp)))


/* Sets the size, prev-allocated and allocation-bit to header of block at pp */
#define SET_HEADER(pp, size, prev, alloc) ((WRITE(HEADER(pp),(size),(prev),(alloc))))
/* Sets the size to header of block at pp */
#define SET_HEADER_SIZE(pp, size) ((WRITE_SIZE(HEADER(pp),(size))))
/* Sets the allocation-bit to header of block at pp */
#define SET_HEADER_ALLOC(pp, alloc) ((WRITE_ALLOC(HEADER(pp),(alloc))))
/* Sets the prev-allocated-bit to header of block at pp */
#define SET_HEADER_PREV_ALLOC(pp, prev) ((WRITE_PREV_ALLOC(HEADER(pp),(prev))))

/* Sets the size, prev-allocated and allocation-bit to header/footer of block at pp */
#define SET_INFO(pp, size, prev, alloc)\
  ((WRITE(HEADER(pp),(size),(prev),(alloc))), \
   (WRITE(FOOTER(pp),(size),(prev),(alloc))))

/* Sets the size to header/footer of block at pp */
#define SET_SIZE(pp, size) (SET_INFO((pp),(size),GET_PREV_ALLOC(pp),GET_ALLOC(pp)))
/* Sets the allocation-bit to header/footer of block at pp */
#define SET_ALLOC(pp, alloc) (SET_INFO((pp),BLOCK_SIZE(pp),GET_PREV_ALLOC(pp),(alloc)))
/* Sets the prev-allocated-bit to header/footer of block at pp */
#define SET_PREV_ALLOC(pp, prev) (SET_INFO((pp),BLOCK_SIZE(pp),(prev),GET_ALLOC(pp)))

/* ======================= Private Global Variables ============================== */

// private global variable
static WTYPE* heap_listp;     /* pointer to first block payload */

/* =========================== Public Functions ================================== */

/* 
 * Initialize the malloc package.
 * return 0 on success, -1 on error.
 */
int mm_init(void) {
  /* Create the initial empty heap */
  if ((heap_listp = mem_sbrk(DSIZE)) == (WTYPE*)-1) return -1;

  WRITE(heap_listp, 0,0,1);                    /* Head Word */
  WRITE(heap_listp + 1, 0,1,1);                /* Tail Word */

  heap_listp += 2;

  /* Extend the empty heap with a free block of CHUNKSIZE bytes */
  if (extend_heap(CHUNKSIZE) == NULL) return -1;
  heap_check(__LINE__);
  return 0;
}

/* 
 *  Allocate an aligned block of memory of at least size bytes
 *  Return address of allocated block on success, NULL on error.
 */
void* mm_malloc(size_t size) {
  if (size == 0) return NULL;
  void* pp;                             /* Payload Pointer */
  size = ALIGN(size + WSIZE);           /* Add header word */

  /* Search the free list for a fit */
  if ((pp = find_fit(size)) == NULL) {
    /* No fit found, request a block from the memory */
    pp = extend_heap(MAX(size, CHUNKSIZE));
    if (pp == NULL) return NULL;
  }

  place(pp, size);
  heap_check(__LINE__);
  return pp;
}

/*
 * Free the allocated block at ptr, and coalesce it.
 */
void mm_free(void* ptr) {
  SET_ALLOC(ptr, 0);
  set_prev_bit(NEXT_BLOCK(ptr), 0);
  coalesce(ptr);
  heap_check(__LINE__);
}

/*
 * # ptr = NULL : allocate block of the given size.
 * # size = 0 : free the given block, return NULL.
 * # else: resize the allocated block at ptr.
 * 
 * Return address of the reallocated block, NULL on error.
 */
void* mm_realloc(void* ptr, size_t size) {
  if (ptr == NULL){
    return mm_malloc(size);
  }else if (size == 0){
    mm_free(ptr);
    return NULL;
  }else{
    ptr = resize_block(ptr, size);
    heap_check(__LINE__);
    return ptr;
  }
}

/* =========================== Private Functions ================================== */

/*
 * Resize the allocated block at pp to have size bytes
 * Return address of the resized block, NULL on error.
 */
static void* resize_block(void* pp, size_t size) {
  size_t asize = MAX(MIN_BLOCK_SIZE, ALIGN(size + WSIZE));
  size_t bsize = BLOCK_SIZE(pp);
  size_t csize = bsize - asize;

  if (asize > bsize) return reallocate_block(pp, size);

  if (csize >= MIN_BLOCK_SIZE){
    SET_HEADER_SIZE(pp, asize);
    void* free_part = NEXT_BLOCK(pp);
    SET_INFO(free_part, csize, 1, 0);
    set_prev_bit(NEXT_BLOCK(free_part), 0);
    coalesce(free_part);
  }

  return pp;
}

/*
 * Allocate block of the given size, copy content, free old block
 * Return address of the new block, NULL on error.
 */
static void* reallocate_block(void* ptr, size_t size) {
  void *newptr = mm_malloc(size);
  if (newptr == NULL) return NULL;
  size_t copy_size = MIN(PAYLOAD_SIZE(ptr), size);
  memcpy(newptr, ptr, copy_size);
  mm_free(ptr);
  return newptr;
}

/**
 * Add free block with aligned size to the end of the heap.
 * Return address of the added free block, NULL on error.
*/
void* extend_heap(size_t size) {
  WTYPE* pp;
  size = ALIGN(size);
  if ((long)(pp = mem_sbrk(size)) == -1) return NULL;

  size_t prev_bit = GET_PREV_ALLOC(pp);
  SET_INFO(pp, size, prev_bit, 0);            /* Initialize a free block */
  SET_HEADER(NEXT_BLOCK(pp), 0,0,1);          /* New Tail Word */

  if (!prev_bit) return coalesce(pp);   /* coalesce if previous block is free */
  return pp;
}

/* Find the first block greater than or equal to size
 * Return address of the first-fit, NULL if no-fit.
*/
static void* first_fit(size_t size) {
  void* pp;

  for (pp = heap_listp; BLOCK_SIZE(pp) > 0; pp = NEXT_BLOCK(pp)) {
    if (IS_FREE(pp) && (size <= BLOCK_SIZE(pp))) return pp;
  }

  return NULL;
}

/* Find the smallest block greater than or equal to size
 * Return address of the best-fit, NULL if no-fit.
*/
static void* best_fit(size_t size) {
  void* pp;
  void* best = NULL;
  size_t best_size = __SIZE_MAX__;

  for (pp = heap_listp; BLOCK_SIZE(pp) > 0; pp = NEXT_BLOCK(pp)) {
    size_t curr_size = BLOCK_SIZE(pp);
    if (IS_FREE(pp) && (size <= curr_size) && (curr_size < best_size)){
      best = pp;
    }
  }

  return best;
}

/**
 * Find a free block with size greater than or equal to size.
 * Return address of a fit-block, NULL if no fit.
*/
static void* find_fit(size_t size) {
  return first_fit(size);
}

/**
 * Allocate the free block at pp.
 * Split the block if the remainder is greater than MIN_BLOCK_SIZE.
*/
static void place(void *pp, size_t size) {
  size_t bsize = BLOCK_SIZE(pp);

  if (bsize < (size + MIN_BLOCK_SIZE)){
    SET_ALLOC(pp, 1);
    set_prev_bit(NEXT_BLOCK(pp), 1);
  }else{
    SET_HEADER(pp, size, GET_PREV_ALLOC(pp), 1);
    pp = NEXT_BLOCK(pp);
    SET_INFO(pp, bsize-size, 1, 0);
  }
}

/**
 * Coalesce the current block with its free previous and/or next blocks.
 * Return the address of the coalesced free-block.
*/
static void* coalesce(void *pp) {
  size_t prev_alloc = GET_PREV_ALLOC(pp);
  size_t next_alloc = GET_ALLOC(NEXT_BLOCK(pp));
  size_t size = BLOCK_SIZE(pp);
  size_t prev_bit = prev_alloc;

  if (prev_alloc && next_alloc) return pp;
  
  if (!next_alloc) size += BLOCK_SIZE(NEXT_BLOCK(pp));

  if (!prev_alloc) {
    pp = PREV_BLOCK(pp);
    size += BLOCK_SIZE(pp);
    prev_bit = GET_PREV_ALLOC(pp);
  }

  SET_INFO(pp, size, prev_bit, 0);
  return pp;
}
/**
 * Sets the prev-bit in the (free/allocated) block at pp.
*/
static void set_prev_bit(void* pp, size_t prev_bit){
  if (IS_FREE(pp)){
    SET_PREV_ALLOC(pp, prev_bit);
  }else{
    SET_HEADER_PREV_ALLOC(pp, prev_bit);
  }
}

/* ========================== Debugging Functions =============================== */

#ifdef DEBUG
/** 
 * Heap Consistency Checker, checks for:
 * - head and tail words of the heap
 * - block header and footer equality for free blocks
 * - block size >= minimum size
 * - payload alignment
 * - coalescing (no contiguous free blocks)
 * - prev-bit correctness.
 * - total heap size
*/
static void mm_check(int line){
  WTYPE* ptr = mem_heap_lo();
  WTYPE* end_ptr = MOVE_BYTE(ptr, mem_heapsize()) - 1;
  // Check head word (size = 0, prev is free, allocated)
  if (READ_SIZE(ptr) != 0){
    printf("Error at %d: head-word size = %u\n",line, READ_SIZE(ptr));
  }

  if (READ_ALLOC(ptr) != 1){
    printf("Error at %d: head-word is not allocated\n",line);
  }

  if (READ_PREV_ALLOC(ptr)){
    printf("Error at %d: head-word is prev is allocated\n",line);
  }

  // Check tail word (size = 0, allocated)
  if (READ_SIZE(end_ptr) != 0){
    printf("Error at %d: tail-word size = %u\n",line, READ_SIZE(end_ptr));
  }

  if (READ_ALLOC(end_ptr) != 1){
    printf("Error at %d: tail-word is not allocated\n",line);
  }

  size_t heap_size = DSIZE;
  int prev_free = 0;

  // Check regular blocks
  for (ptr = heap_listp; ptr < end_ptr; ptr = NEXT_BLOCK(ptr)){
    // check header and footer equality
    if (IS_FREE(ptr) && (READ_WORD(HEADER(ptr)) != READ_WORD(FOOTER(ptr)))){
      printf("Error at %d: at block %p => header = %u, footer = %u\n",
        line, ptr, READ_WORD(HEADER(ptr)), READ_WORD(FOOTER(ptr)));
    }
    // check that block size >= minimum size
    if (BLOCK_SIZE(ptr) < MIN_BLOCK_SIZE){
      printf("Error at %d: block %p has size < min size, (%u < %u)\n",
        line, ptr, BLOCK_SIZE(ptr), MIN_BLOCK_SIZE);
    }
    // check payload alignment
    if((unsigned) ptr % ALIGNMENT){
      printf("Error at %d: block %p is not aligned to %d\n",
        line, ptr, ALIGNMENT);
    }
    // check coalescing.
    if (prev_free && IS_FREE(ptr)){
      printf("Error at %d: two contiguous free blocks not coalesced\n", line);
    }
    // check prev-allocated bit
    if (prev_free != IS_PREV_FREE(ptr)){
      printf("Error at %d: block %p prev-bit is incorrect\n", line, ptr);
    }

    prev_free = IS_FREE(ptr);
    heap_size += BLOCK_SIZE(ptr);
  }
  // check total heap size
  if (heap_size != mem_heapsize()){
    printf("Error at %d: heap size not accurate, %u should be %u\n",
     line, heap_size, mem_heapsize());
  }
}

#endif

3. Explicit list

📌성능요약
: Perf index = 46 (util) + 40 (thru) = 86/100

/* mm.c
 * 
 * Blocks are aligned to double-word boundaries.  This
 * yields 8-byte aligned blocks on a 32-bit processor, and 16-byte aligned
 * blocks on a 64-bit processor.  However, 16-byte alignment is stricter
 * than necessary; the assignment only requires 8-byte alignment.  The
 * minimum block size taken is 4 words.
 * This allocator uses the size of a pointer, e.g., sizeof(void *), to
 * define the size of a word.  This allocator also uses the standard
 * type uintptr_t to define unsigned integers that are the same size
 * as a pointer, i.e., sizeof(uintptr_t) == sizeof(void *).
 */

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

#include "memlib.h"
#include "mm.h"
/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/

team_t team = {
  "team 1",
  "Hyemin Pyo",
  "pyolovely01@gmail.com",
  "",
  "",
};

//* Basic constants and macros: */
#define WSIZE      sizeof(void *) /* Word and header/footer size (bytes) */
#define DSIZE      (2 * WSIZE)    /* Doubleword size (bytes) */
#define CHUNKSIZE  (1 << 12)      /* Extend heap by this amount (bytes) */

/*Max value of 2 values*/
#define MAX(x, y) ((x) > (y) ? (x) : (y))

/* Pack a size and allocated bit into a word */
#define PACK(size, alloc)  ((size) | (alloc))

/* Read and write a word at address p. */
#define GET(p)       (*(uintptr_t *)(p))
#define PUT(p, val)  (*(uintptr_t *)(p) = (val))

/* Read the size and allocated fields from address p */
#define GET_SIZE(p)   (GET(p) & ~(DSIZE - 1))
#define GET_ALLOC(p)  (GET(p) & 0x1)


/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp)  ((void *)(bp) - WSIZE)
#define FTRP(bp)  ((void *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp)  ((void *)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLKP(bp)  ((void *)(bp) - GET_SIZE((void *)(bp) - DSIZE))

/* Given ptr in free list, get next and previous ptr in the list */
/* bp is address of the free block. Since minimum Block size is 16 bytes, 
   we utilize to store the address of previous block pointer and next block pointer.
*/
#define GET_NEXT_PTR(bp)  (*(char **)(bp + WSIZE))
#define GET_PREV_PTR(bp)  (*(char **)(bp))

/* Puts pointers in the next and previous elements of free list */
#define SET_NEXT_PTR(bp, qp) (GET_NEXT_PTR(bp) = qp)
#define SET_PREV_PTR(bp, qp) (GET_PREV_PTR(bp) = qp)

/* Global declarations */
static char *heap_listp = 0; 
static char *free_list_start = 0;

/* Function prototypes for internal helper routines */
static void *coalesce(void *bp);
static void *extend_heap(size_t words);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);

/* Function prototypes for maintaining free list*/
static void insert_in_free_list(void *bp); 
static void remove_from_free_list(void *bp); 

/* Function prototypes for heap consistency checker routines: */
static void checkblock(void *bp);
static void checkheap(bool verbose);
static void printblock(void *bp); 

/**
 * Initialize the memory manager.
 * @param - void no parameter passed in
 * @return - int 0 for success or -1 for failure
 */
int mm_init(void) {
  
  /* Create the initial empty heap. */
  if ((heap_listp = mem_sbrk(8*WSIZE)) == NULL) 
    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 */
  free_list_start = heap_listp + 2*WSIZE; 

  /* Extend the empty heap with a free block of minimum possible block size */
  if (extend_heap(4) == NULL){ 
    return -1;
  }
  return 0;
}

/* 
 * Requires:
 *   size of memory asked by the programmer.
 *
 * Effects:
 *   Allocate a block with at least "size" bytes of payload, unless "size" is
 *   zero.  Returns the address of this block if the allocation was successful
 *   and NULL otherwise.
 */
void *mm_malloc(size_t size) 
{
  size_t asize;      /* Adjusted block size */
  size_t extendsize; /* Amount to extend heap if no fit */
  void *bp;

  /* Ignore spurious requests. */
  if (size == 0)
    return (NULL);

  /* Adjust block size to include overhead and alignment reqs. */
  if (size <= DSIZE)
    asize = 2 * DSIZE;
  else
    asize = DSIZE * ((size + DSIZE + (DSIZE - 1)) / DSIZE);

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

/* 
 * Requires:
 *   "bp" is either the address of an allocated block or NULL.
 *
 * Effects:
 *   Free a block.
 */
void mm_free(void *bp){
  size_t size;
  /* Ignore spurious requests. */
  if (bp == NULL)
    return;
  /* Free and coalesce the block. */
  size = GET_SIZE(HDRP(bp));
  PUT(HDRP(bp), PACK(size, 0));
  PUT(FTRP(bp), PACK(size, 0));
  coalesce(bp);
}

/*
 * Requires:
 *   "ptr" is either the address of an allocated block or NULL.
 *
 * Effects:
 *   Reallocates the block "ptr" to a block with at least "size" bytes of
 *   payload, unless "size" is zero.  
 *   If "size" is zero, frees the block "ptr" and returns NULL.  
 *   If the block "ptr" is already a block with at
 *   least "size" bytes of payload, then "ptr" may optionally be returned.
 *   Further if requested size is greater than the current block size at pointer bp
 *   and we have the next block as empty with sum of current block size and next block (which happens to be empty)
 *   then we dont need call malloc but just combine current block and next block to resize them so as to 
 *   satisfy the requested realloc size. 
 *   If nothing can be done then a new block is allocated (using malloc) and the contents of the old block
 *   "ptr" are copied to that new block.  Returns the address of this new
 *   block if the allocation was successful and NULL otherwise.
 */
void *mm_realloc(void *bp, size_t size){
  if((int)size < 0) 
    return NULL; 
  else if((int)size == 0){ 
    mm_free(bp); 
    return NULL; 
  } 
  else if(size > 0){ 
      size_t oldsize = GET_SIZE(HDRP(bp)); 
      size_t newsize = size + 2 * WSIZE; // 2 words for header and footer
      /*if newsize is less than oldsize then we just return bp */
      if(newsize <= oldsize){ 
          return bp; 
      }
      /*if newsize is greater than oldsize */ 
      else { 
          size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); 
          size_t csize;
          /* next block is free and the size of the two blocks is greater than or equal the new size  */ 
          /* then we only need to combine both the blocks  */ 
          if(!next_alloc && ((csize = oldsize + GET_SIZE(  HDRP(NEXT_BLKP(bp))  ))) >= newsize){ 
            remove_from_free_list(NEXT_BLKP(bp)); 
            PUT(HDRP(bp), PACK(csize, 1)); 
            PUT(FTRP(bp), PACK(csize, 1)); 
            return bp; 
          }
          else {  
            void *new_ptr = mm_malloc(newsize);  
            place(new_ptr, newsize);
            memcpy(new_ptr, bp, newsize); 
            mm_free(bp); 
            return new_ptr; 
          } 
      }
  }else 
    return NULL;
} 


/*
 * Requires:
 *   "bp" is the address of a newly freed block.
 *
 * Effects:
 *   Perform boundary tag coalescing. 
 *   Removes and inserts appropiate free block pointers to the explicit free list
 *   Returns the address of the coalesced block.
 */
static void *coalesce(void *bp){

  //if previous block is allocated or its size is zero then PREV_ALLOC will be set.
  size_t NEXT_ALLOC = GET_ALLOC(  HDRP(NEXT_BLKP(bp))  );
  size_t PREV_ALLOC = GET_ALLOC(  FTRP(PREV_BLKP(bp))  ) || PREV_BLKP(bp) == bp;
  size_t size = GET_SIZE(HDRP(bp));
  
  /* Next block is only free */   
  if (PREV_ALLOC && !NEXT_ALLOC) {                  
    size += GET_SIZE( HDRP(NEXT_BLKP(bp))  );
    remove_from_free_list(NEXT_BLKP(bp));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
  }
  /* Prev block is only free */  
  else if (!PREV_ALLOC && NEXT_ALLOC) {               
    size += GET_SIZE( HDRP(PREV_BLKP(bp))  );
    bp = PREV_BLKP(bp);
    remove_from_free_list(bp);
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
  }
  /* Both blocks are free */ 
  else if (!PREV_ALLOC && !NEXT_ALLOC) {                
    size += GET_SIZE( HDRP(PREV_BLKP(bp))  ) + GET_SIZE( HDRP(NEXT_BLKP(bp))  );
    remove_from_free_list(PREV_BLKP(bp));
    remove_from_free_list(NEXT_BLKP(bp));
    bp = PREV_BLKP(bp);
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
  }/* lastly insert bp into free list and return bp */
  insert_in_free_list(bp);
  return bp;
}

/* 
 * Requires:
 *   None.
 *
 * Effects:
 *   Extend the heap with a free block and return that block's address.
 */

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

  /* Allocate an even number of words to maintain alignment */
  size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
  //Since minimum block size given to us is 4 words (ie 16 bytes)
  if (size < 16){
    size = 16;
  }
  /* call for more memory space */
  if ((int)(bp = mem_sbrk(size)) == -1){ 
    return NULL;
  }
  /* Initialize free block header/footer and the epilogue header */
  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 bp with next and previous blocks */
  return coalesce(bp);
}

/*
 * Requires:
 *   Size of memory to find.
 * Effects:
 *   Finds a fit for a block with "asize" bytes from the free list.
 *   Extends the heap in some special cases.
 *   And Returns that block's address
 *   or NULL if no suitable block was found. 
 */

static void *find_fit(size_t asize){
  void *bp;
  static int last_malloced_size = 0;
  static int repeat_counter = 0;
  if( last_malloced_size == (int)asize){
      if(repeat_counter>30){  
        int extendsize = MAX(asize, 4 * WSIZE);
        bp = extend_heap(extendsize/4);
        return bp;
      }
      else
        repeat_counter++;
  }
  else
    repeat_counter = 0;
  for (bp = free_list_start; GET_ALLOC(HDRP(bp)) == 0; bp = GET_NEXT_PTR(bp) ){
    if (asize <= (size_t)GET_SIZE(HDRP(bp)) ) {
      last_malloced_size = asize;
      return bp;
    }
  }
  return NULL;
}

/* 
 * Requires:
 *   "bp" is the address of a free block that is at least "asize" bytes.
 * Effects:
 *   Place a block of "asize" bytes at the start of the free block "bp" and
 *   split that block if the remainder would be at least the minimum block
 *   size. 
 */
static void place(void *bp, size_t asize){
  size_t csize = GET_SIZE(HDRP(bp));

  if ((csize - asize) >= 4 * WSIZE) {
    PUT(HDRP(bp), PACK(asize, 1));
    PUT(FTRP(bp), PACK(asize, 1));
    remove_from_free_list(bp);
    bp = NEXT_BLKP(bp);
    PUT(HDRP(bp), PACK(csize-asize, 0));
    PUT(FTRP(bp), PACK(csize-asize, 0));
    coalesce(bp);
  }
  else {
    PUT(HDRP(bp), PACK(csize, 1));
    PUT(FTRP(bp), PACK(csize, 1));
    remove_from_free_list(bp);
  }
}

/*Inserts the free block pointer int the free_list*/
static void insert_in_free_list(void *bp){
  SET_NEXT_PTR(bp, free_list_start); 
  SET_PREV_PTR(free_list_start, bp); 
  SET_PREV_PTR(bp, NULL); 
  free_list_start = bp; 
}
/*Removes the free block pointer int the free_list*/
static void remove_from_free_list(void *bp){
  if (GET_PREV_PTR(bp))
    SET_NEXT_PTR(GET_PREV_PTR(bp), GET_NEXT_PTR(bp));
  else
    free_list_start = GET_NEXT_PTR(bp);
  SET_PREV_PTR(GET_NEXT_PTR(bp), GET_PREV_PTR(bp));
}


/* 
 * The remaining routines are heap consistency checker routines. 
 */

/*
 * Requires:
 *   "bp" is the address of a block.
 *
 * Effects:
 *   Perform a minimal check on the block "bp".
 */
static void
checkblock(void *bp) 
{

  if ((uintptr_t)bp % DSIZE)
    printf("Error: %p is not doubleword aligned\n", bp);
  if (GET(HDRP(bp)) != GET(FTRP(bp)))
    printf("Error: header does not match footer\n");
}

/* 
 * Requires:
 *   None.
 *
 * Effects:
 *   Perform a minimal check of the heap for consistency. 
 */
void
checkheap(bool verbose) 
{
  void *bp;

  if (verbose)
    printf("Heap (%p):\n", heap_listp);

  if (GET_SIZE(HDRP(heap_listp)) != DSIZE ||
      !GET_ALLOC(HDRP(heap_listp)))
    printf("Bad prologue header\n");
  checkblock(heap_listp);

  for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = (void *)NEXT_BLKP(bp)) {
    if (verbose)
      printblock(bp);
    checkblock(bp);
  }

  if (verbose)
    printblock(bp);
  if (GET_SIZE(HDRP(bp)) != 0 || !GET_ALLOC(HDRP(bp)))
    printf("Bad epilogue header\n");
}

/*
 * Requires:
 *   "bp" is the address of a block.
 *
 * Effects:
 *   Print the block "bp".
 */
static void
printblock(void *bp) 
{
  bool halloc, falloc;
  size_t hsize, fsize;

  checkheap(false);
  hsize = GET_SIZE(HDRP(bp));
  halloc = GET_ALLOC(HDRP(bp));  
  fsize = GET_SIZE(FTRP(bp));
  falloc = GET_ALLOC(FTRP(bp));  

  if (hsize == 0) {
    printf("%p: end of heap\n", bp);
    return;
  }

  printf("%p: header: [%zu:%c] footer: [%zu:%c]\n", bp, 
      hsize, (halloc ? 'a' : 'f'), 
      fsize, (falloc ? 'a' : 'f'));
}


/*
 * The last lines of this file configures the behavior of the "Tab" key in
 * emacs.  Emacs has a rudimentary understanding of C syntax and style.  In
 * particular, depressing the "Tab" key once at the start of a new line will
 * insert as many tabs and/or spaces as are needed for proper indentation.
 */

/* Local Variables: */
/* mode: c */
/* c-default-style: "bsd" */
/* c-basic-offset: 8 */
/* c-continued-statement-offset: 4 */
/* indent-tabs-mode: t */
/* End: */

4. Seglist

📌성능요약
: Perf index = 58 (util) + 40 (thru) = 98/100

/*
 * mm.c
 * 
 * Block Format: Minimum size is 16 bytes.
 *  - Free-Block Format: [Header - Pred - Succ - (Empty) - Footer]
 *  - Allocated-Block Format: [Header - Payload - Footer]
 *  - Header/Footer: 1-word holds size of the block and allocation-bit at LSB(Least Significant Bit)
 *  - Pred: 1-word holds the address of the predecessor free-block.
 *  - Succ: 1-word holds the address of the successor free-block.
 * 
 * List Format: array of 8 explicit-free lists
 * Heap Format: [seglist-array[8] | Head-Block[1] | Regular-Blocks ...| Tail-Block[1]]
 *  - Head/Tail: 1-word allocated block of zero size.
 * 
 * Placement Policy: using best-fit algorithm.
 * Split Policy: split if remainder is greater than 16 bytes
 * Coalescing Policy: bi-direction coalescing for free-blocks and allocated-blocks
 * Heap Extension Policy: 
 *  - if the size is greater than CHUNK_SIZE: extend by one block of the given size
 *  - else: extend the heap by a few blocks each of the given size. 
 * 
 * realloc:
 *  - if new-size is greater than current-size: expand the block if it can be expanded,
 *    otherwise, reallocate the block (allocate - copy - free).
 *  - if the new-size is less than current size by 64 byte at least then split.
 * 
 * NOTE: Coalescing is not strict, there are some free blocks not coalesced just to keep
 *       a variety of sizes in the seglist.
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

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

/* =============================================================================== */

team_t team = {
  /* Team name */
  "pyotato",
  /* First member's full name */
  "Hyemin PYo",
  /* First member's email address */
  "pyolovely01@gmail.com",
  /* Second member's full name (leave blank if none) */
  "",
  /* Second member's email address (leave blank if none) */
  ""
};

/* ========================== Function Prototype =============================== */

inline static void* resize_block(void*, size_t);
inline static void* reallocate_block(void*, size_t);
inline static int can_expand(void*, size_t);
inline static void* expand_block(void*, size_t);
inline static void chop_block(void*, size_t);
inline static void* extend_heap(size_t);
inline static void* first_fit(void*, size_t);
inline static void* best_fit(void*, size_t);
inline static void* find_fit(size_t);
inline static void* place(void*, size_t);
inline static void* coalesce(void*);
inline static void link_block(void*);
inline static void unlink_block(void*);
inline static int seg_index(size_t);

/* ========================== Compilation Flags =============================== */

// #define DEBUG                 /* uncomment to turn-on heap checker */

#ifdef DEBUG
  static void mm_check(int);
  static void check_seglist(int, int);
  static int check_free_list(int, int);
  #define heap_check(line) (mm_check(line))
#else
  #define heap_check(line)
#endif
//NOTE at 236: two contiguous free blocks not coalesced 식으로 heap 체크 가능
/* ================================ Macros ===================================== */

#define WSIZE 4                           /* Word size in bytes */
#define DSIZE 8                           /* Double word size in bytes */
#define CHUNKSIZE (1<<8)                  /* Minimum heap allocation size */
#define MIN_BLOCK_SIZE 16                 /* Minimum block size */
#define ALIGNMENT 8                       /* Payload Alignment */
#define SEGLIST_NUM 8                     /* The Number of lists in the seglist */
#define WTYPE u_int32_t                   /* Word type */
#define BYTE char                         /* Byte type */

/* ------------------------------ Basic Utility ------------------------------- */

/* Move the address ptr by offset bytes */
#define MOVE_BYTE(ptr, offset) ((WTYPE *)((BYTE *)(ptr) + (offset)))
/* Move the address ptr by offset words */
#define MOVE_WORD(ptr, offset) ((WTYPE *)(ptr) + (offset))
/* Read a word from address ptr */
#define READ_WORD(ptr) (*(WTYPE *)(ptr))
/* Write a word value to address ptr */
#define WRITE_WORD(ptr, value) (*(WTYPE *)(ptr) = (value))
/* rounds up size (in bytes) to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
/* Get the maximum of x and y */
#define MAX(x, y) (((x) > (y))? (x) : (y))
/* Get the minimum of x and y */
#define MIN(x, y) (((x) < (y))? (x) : (y))

/* ----------------------- Header/Footer Macros ---------------------------- */

/* Pack the size and allocated-bit into a word */
#define PACK(size, alloc) ((size) | (alloc))
/* Read the size from header/footer word at address Hptr */
#define READ_SIZE(Hptr) (READ_WORD(Hptr) & ~0x7)
/* Read the allocated-bit from header/footer word at address Hptr */
#define READ_ALLOC(Hptr) (READ_WORD(Hptr) & 0x1)
/* Write the size and allocation-bit to the word at address Hptr */
#define WRITE(Hptr, size, alloc) (WRITE_WORD((Hptr), PACK((size), (alloc))))
/* Write the size to the word at address Hptr */
#define WRITE_SIZE(Hptr, size) (WRITE((Hptr), (size), READ_ALLOC(Hptr)))
/* Write allocation-bit to the word at address Hptr */
#define WRITE_ALLOC(Hptr, alloc) (WRITE((Hptr), READ_SIZE(Hptr), (alloc)))

/* ---------------------------- Payload Macros ------------------------------ */

/* Get the header-word pointer from the payload pointer pp */
#define HEADER(pp) (MOVE_WORD(pp, -1))
/* Get the footer-word pointer from the payload pointer pp */
#define FOOTER(pp) (MOVE_BYTE(pp, PAYLOAD_SIZE(pp)))
/* Get next block payload pointer from pp (current payload pointer) */
#define NEXT_BLOCK(pp) (MOVE_BYTE(pp, BLOCK_SIZE(pp)))
/* Get previous block payload pointer from pp (current payload pointer) */
#define PREV_BLOCK(pp) (MOVE_BYTE(pp, - READ_SIZE(MOVE_WORD(pp, -2))))
/* Read the block size at the payload pp */
#define BLOCK_SIZE(pp) (READ_SIZE(HEADER(pp)))
/* Read the payload size at pp */
#define PAYLOAD_SIZE(pp) (BLOCK_SIZE(pp) - DSIZE)
/* Check if the block at the payload pp is free */
#define IS_FREE(pp) (!(READ_ALLOC(HEADER(pp))))

/* Sets the size and allocation-bit to header/footer of block at pp */
#define SET_INFO(pp, size, alloc)\
  ((WRITE(HEADER(pp),(size),(alloc))), \
   (WRITE(FOOTER(pp),(size),(alloc))))

/* Sets the size to header/footer of block at pp */
#define SET_SIZE(pp, size)\
  ((WRITE_SIZE(HEADER(pp),(size))), \
   (WRITE_SIZE(FOOTER(pp),(size))))

/* Sets the allocation-bit to header/footer of block at pp */
#define SET_ALLOC(pp, alloc)\
  ((WRITE_ALLOC(HEADER(pp),(alloc))), \
   (WRITE_ALLOC(FOOTER(pp),(alloc))))

/* Get the predecessor payload address */
#define GET_PRED(pp) ((WTYPE *)(READ_WORD(pp)))
/* Get the successor payload address */
#define GET_SUCC(pp) ((WTYPE *)(READ_WORD(MOVE_WORD(pp, 1))))
/* Set the predecessor payload address to pred_pp */
#define SET_PRED(pp, pred_pp) (WRITE_WORD(pp, ((WTYPE) pred_pp)))
/* Set the successor payload address to succ_pp */
#define SET_SUCC(pp, succ_pp) (WRITE_WORD(MOVE_WORD(pp, 1), ((WTYPE) succ_pp)))

/* ======================= Private Global Variables ============================== */

// private global variable
static WTYPE** seglist;       /* array of free-list pointers */

/* =========================== Public Functions ================================== */

/* 
 * Initialize the malloc package.
 * return 0 on success, -1 on error.
 */
int mm_init(void) {
  /* Create the initial empty heap */
  void* heap = mem_sbrk((SEGLIST_NUM + 2) * WSIZE); /* seglist + head + tail */
  if (heap == (void*)-1) return -1;

  seglist = heap;
  heap = MOVE_WORD(heap, SEGLIST_NUM);
  // initialize the seglist
  for(int i = 0; i < SEGLIST_NUM; ++i){
    seglist[i] = NULL;
  }

  WRITE(heap, 0, 1);                          /* Head Word */
  WRITE(MOVE_WORD(heap, 1), 0, 1);            /* Tail Word */

  /* Extend the empty heap with a small free block */
  if (extend_heap(4 * MIN_BLOCK_SIZE) == NULL) return -1;
  heap_check(__LINE__);
  return 0;
}

/* 
 *  Allocate an aligned block of memory of at least size bytes
 *  Return address of allocated block on success, NULL on error.
 */
void* mm_malloc(size_t size) {
  if (size == 0) return NULL;
  void* pp;                             /* Payload Pointer */
  size = ALIGN(size + DSIZE);           /* Add header and footer words */
  size = MAX(size, MIN_BLOCK_SIZE);

  /* Search the free list for a fit */
  if ((pp = find_fit(size)) == NULL) {
    /* No fit found, request a block from the memory */
    if (size > CHUNKSIZE){
      pp = extend_heap(size);
    }else{
      pp = extend_heap(4 * CHUNKSIZE);
      chop_block(pp, size);
    }
    if (pp == NULL) return NULL;
  }

  pp = place(pp, size);
  heap_check(__LINE__);
  return pp;
}

/*
 * Free the allocated block at ptr, and coalesce it.
 */
void mm_free(void* ptr) {
  SET_ALLOC(ptr, 0);
  link_block(ptr);
  coalesce(ptr);
  heap_check(__LINE__);
}

/*
 * # ptr = NULL : allocate block of the given size.
 * # size = 0 : free the given block, return NULL.
 * # else: resize the allocated block at ptr.
 * 
 * Return address of the reallocated block, NULL on error.
 */
void* mm_realloc(void* ptr, size_t size) {
  if (ptr == NULL){
    return mm_malloc(size);
  }else if (size == 0){
    mm_free(ptr);
    return NULL;
  }else{
    ptr = resize_block(ptr, size);
    heap_check(__LINE__);
    return ptr;
  }
}

/* =========================== Private Functions ================================== */

/*
 * Resize the allocated block at pp to have size bytes
 * Return address of the resized block, NULL on error.
 */
static void* resize_block(void* pp, size_t size) {
  size_t asize = MAX(MIN_BLOCK_SIZE, ALIGN(size + DSIZE));
  size_t bsize = BLOCK_SIZE(pp);
  size_t csize = bsize - asize;

  if (asize > bsize) {
    if (can_expand(pp, asize)) return expand_block(pp, asize);
    return reallocate_block(pp, size);
  }

  // Split only if the fragment is large enough.
  if (csize >= (4 * MIN_BLOCK_SIZE)){
    SET_INFO(pp, asize, 1);
    void* fp = NEXT_BLOCK(pp);
    SET_INFO(fp, csize, 0);
    link_block(fp);
  }

  return pp;
}

/*
 * Allocate block of the given size, copy content, free old block
 * Return address of the new block, NULL on error.
 */
static void* reallocate_block(void* ptr, size_t size) {
  void *newptr = mm_malloc(size);
  if (newptr == NULL) return NULL;
  size_t copy_size = MIN(PAYLOAD_SIZE(ptr), size);
  memcpy(newptr, ptr, copy_size);
  mm_free(ptr);
  return newptr;
}

/**
 * checks if the allocated-block at pp can expand to have the given size
 */
static int can_expand(void* pp, size_t size){
  size_t bsize = BLOCK_SIZE(pp);

  for(void* ptr = NEXT_BLOCK(pp); IS_FREE(ptr) ; ptr = NEXT_BLOCK(ptr)){
    bsize += BLOCK_SIZE(ptr);
    if (bsize >= size) return 1;
  }

  for(void* ptr = pp; !READ_ALLOC(MOVE_WORD(ptr, -2)) ; ){
    ptr = PREV_BLOCK(ptr);
    bsize += BLOCK_SIZE(ptr);
    if (bsize >= size) return 1;
  }

  return 0;
}

/**
 * expands the allocated-block at pp until it has the given size
 * return address to the new expanded block
*/
static void* expand_block(void *pp, size_t size) {
  void* cpp = pp;
  size_t bsize = BLOCK_SIZE(pp);

  for(void* ptr = NEXT_BLOCK(pp); IS_FREE(ptr) ; ptr = NEXT_BLOCK(ptr)){
    bsize += BLOCK_SIZE(ptr);
    unlink_block(ptr);
    if (bsize >= size) break;
  }

  if (bsize >= size) {
    SET_INFO(cpp, bsize, 1);
    return cpp;
  }

  for(void* ptr = pp; !READ_ALLOC(MOVE_WORD(ptr, -2)) ; ){
    cpp = ptr = PREV_BLOCK(ptr);
    bsize += BLOCK_SIZE(ptr);
    unlink_block(ptr);
    if (bsize >= size) break;
  }
   
  if (cpp != pp) memmove(cpp, pp, PAYLOAD_SIZE(pp));
  SET_INFO(cpp, bsize, 1);
  return cpp;
}

/**
 * chop the given free-block into a small free-blocks of the given size.
*/
static void chop_block(void* pp, size_t size){
  if ((pp == NULL) || (size < MIN_BLOCK_SIZE)) return;
  size_t bsize = BLOCK_SIZE(pp);
  if ((size + MIN_BLOCK_SIZE) > bsize) return;
  unlink_block(pp);

  while(bsize >= (size + MIN_BLOCK_SIZE)){
    SET_INFO(pp, size, 0);
    link_block(pp);
    pp = NEXT_BLOCK(pp);
    bsize -= size;
  }

  SET_INFO(pp, bsize, 0);
  link_block(pp);
}

/**
 * Add free block with aligned size to the end of the heap.
 * Return address of the added free block, NULL on error.
*/
void* extend_heap(size_t size) {
  WTYPE* pp;
  size = ALIGN(size);
  if ((long)(pp = mem_sbrk(size)) == -1) return NULL;

  SET_INFO(pp, size, 0);                      /* Initialize a free block */
  link_block(pp);
  WRITE(HEADER(NEXT_BLOCK(pp)), 0, 1);        /* New Tail Word */

  return pp;
}

/* Find the first block greater than or equal to size
 * Return address of the first-fit, NULL if no-fit.
*/
static void* first_fit(void* free_list, size_t size) {
  for (void* pp = free_list; pp != NULL ; pp = GET_SUCC(pp)) {
    if (size <= BLOCK_SIZE(pp)) return pp;
  }
  return NULL;
}

/* Find the smallest block greater than or equal to size
 * Return address of the best-fit, NULL if no-fit.
*/
static void* best_fit(void* free_list, size_t size) {
  void* pp;
  void* best = NULL;
  size_t best_size = __SIZE_MAX__;

  for (pp = free_list; pp != NULL ; pp = GET_SUCC(pp)) {
    size_t curr_size = BLOCK_SIZE(pp);
    if ((size <= curr_size) && (curr_size < best_size)){
      best = pp;
    }
  }

  return best;
}

/**
 * Find a free block with size greater than or equal to size.
 * Return address of a fit-block, NULL if no fit.
*/
static void* find_fit(size_t size) {
  for(int i = seg_index(size); i < SEGLIST_NUM; ++i){
    void* fit = best_fit(seglist[i], size);
    if (fit != NULL) return fit;
  }
  return NULL;
}

/**
 * Allocate the free block at pp.
 * Split the block if the remainder is greater than MIN_BLOCK_SIZE.
 * Returns the address of the allocated block payload
*/
static void* place(void *pp, size_t size) {
  size_t bsize = BLOCK_SIZE(pp);
  size_t csize = bsize - size;

  unlink_block(pp);
  if (csize < MIN_BLOCK_SIZE){
    SET_ALLOC(pp, 1);
  }else{
    SET_INFO(pp, csize, 0);
    link_block(pp);
    pp = NEXT_BLOCK(pp);
    SET_INFO(pp, size, 1);
  }

  return pp;
}

/**
 * Coalesce the current block with its free previous and/or next blocks.
 * Return the address of the coalesced block.
*/
static void* coalesce(void *pp) {
  void* cpp = pp;                            /* coalesced payload pointer */
  void* prev_footer = MOVE_WORD(pp, -2);
  void* next_header = HEADER(NEXT_BLOCK(pp));
  
  size_t prev_alloc = READ_ALLOC(prev_footer);
  size_t next_alloc = READ_ALLOC(next_header);
  size_t curr_alloc = !IS_FREE(pp);
  size_t size = BLOCK_SIZE(pp);

  if (prev_alloc && next_alloc) return pp;

  if (!curr_alloc) unlink_block(pp);

  if (!next_alloc) {
    size += READ_SIZE(next_header);
    unlink_block(MOVE_WORD(next_header, 1));
  }

  if (!prev_alloc) {
    size += READ_SIZE(prev_footer);
    cpp = PREV_BLOCK(pp);
    unlink_block(cpp);
    if (curr_alloc) memmove(cpp, pp, PAYLOAD_SIZE(pp));
  } 

  SET_INFO(cpp, size, curr_alloc);
  if (!curr_alloc) link_block(cpp);

  return cpp;
}

/**
 * Add the block at pp to the free-list
*/
static void link_block(void* pp){
  int index = seg_index(BLOCK_SIZE(pp));
  WTYPE* list = seglist[index];
  if (list) SET_PRED(list, pp);
  SET_SUCC(pp, list);
  SET_PRED(pp, NULL);
  seglist[index] = pp;
}

/**
 * Remove the block at pp from the free-list 
*/
static void unlink_block(void* pp) {
  int index = seg_index(BLOCK_SIZE(pp));
  WTYPE* pred_pp = GET_PRED(pp);
  WTYPE* succ_pp = GET_SUCC(pp);
  if (pred_pp) SET_SUCC(pred_pp, succ_pp);
  if (succ_pp) SET_PRED(succ_pp, pred_pp);
  if (pp == seglist[index]) seglist[index] = succ_pp;
}

/**
 * Returns the index of the seglist that should contain blocks of the given size 
*/
static int seg_index(size_t size){
  if (size <= MIN_BLOCK_SIZE) return 0;
  if (size <= (2 * MIN_BLOCK_SIZE)) return 1;
  if (size <= (4 * MIN_BLOCK_SIZE)) return 2;
  if (size <= (8 * MIN_BLOCK_SIZE)) return 3;
  if (size <= (16 * MIN_BLOCK_SIZE)) return 4;
  if (size <= (64 * MIN_BLOCK_SIZE)) return 5;
  if (size <= (256 * MIN_BLOCK_SIZE)) return 6;
  return 7;
}

/* ========================== Debugging Functions =============================== */

#ifdef DEBUG
/** 
 * Heap Consistency Checker, checks for:
 * - head and tail words of the heap
 * - block header and footer equality
 * - block size >= minimum size
 * - payload alignment
 * - coalescing (no contiguous free blocks)
 * - total heap size
 * - seglist consistency.
*/
static void mm_check(int line){
  WTYPE* ptr = MOVE_WORD(mem_heap_lo(), SEGLIST_NUM);
  WTYPE* end_ptr = MOVE_BYTE(ptr, mem_heapsize()) - (SEGLIST_NUM + 1); 
  // Check head word (size = 0, allocated)
  if (READ_SIZE(ptr) != 0){
    printf("Error at %d: head-word size = %u\n",line, READ_SIZE(ptr));
  }

  if (READ_ALLOC(ptr) != 1){
    printf("Error at %d: head-word is not allocated\n",line);
  }

  // Check tail word (size = 0, allocated)
  if (READ_SIZE(end_ptr) != 0){
    printf("Error at %d: tail-word size = %u\n",line, READ_SIZE(end_ptr));
  }

  if (READ_ALLOC(end_ptr) != 1){
    printf("Error at %d: tail-word is not allocated\n",line);
  }

  size_t heap_size = (SEGLIST_NUM + 2) * WSIZE;
  int free_count = 0;
  int prev_free = 0;

  // Check regular blocks
  for (ptr = MOVE_WORD(ptr, 2); ptr < end_ptr; ptr = NEXT_BLOCK(ptr)){
    // check header and footer equality
    if (READ_WORD(HEADER(ptr)) != READ_WORD(FOOTER(ptr))){
      printf("Error at %d: at block %p => header = %u, footer = %u\n",
        line, ptr, READ_WORD(HEADER(ptr)), READ_WORD(FOOTER(ptr)));
    }
    // check that block size >= minimum size
    if (BLOCK_SIZE(ptr) < MIN_BLOCK_SIZE){
      printf("Error at %d: block %p has size < min size, (%u < %u)\n",
        line, ptr, BLOCK_SIZE(ptr), MIN_BLOCK_SIZE);
    }
    // check payload alignment
    if((unsigned) ptr % ALIGNMENT){
      printf("Error at %d: block %p is not aligned to %d\n",
        line, ptr, ALIGNMENT);
    }
    // check coalescing.
    if (prev_free && IS_FREE(ptr)){
      printf("NOTE at %d: two contiguous free blocks not coalesced\n", line);
    }

    if(IS_FREE(ptr)) ++free_count;
    prev_free = IS_FREE(ptr);
    heap_size += BLOCK_SIZE(ptr);
  }
  // check total heap size
  if (heap_size != mem_heapsize()){
    printf("Error at %d: heap size not accurate, %u should be %u\n",
     line, heap_size, mem_heapsize());
  }
  // check seglist consistency
  check_seglist(line, free_count);
}

/** 
 * Seglist Consistency Checker, checks for:
 * - seglist pointer
 * - each free-list consistency
 * - the free-block count in seglist matches the free_count (free-blocks in the heap)
*/
static void check_seglist(int line, int free_count){
  int count = 0;
  // checks the seglist pointer
  if (seglist != mem_heap_lo()){
    printf("Error at %d: Seglist pointer doesn't point to heap start address.\n",
      line);
  }
  // check each free-list in the seglist
  for(int i = 0; i < SEGLIST_NUM; ++i){
    count += check_free_list(line, i);
  }
  // check the free-block count in seglist matches the free_count
  if (count != free_count){
    printf("Error at %d: %d missing free-blocks from the seglist.\n",
      line, (free_count - count));
  }
}

/** 
 * Free-List Consistency Checker, checks for:
 * - blocks are free.
 * - free-blocks are in heap range.
 * - the predecessor consistency.
 * Return the number of blocks in the free-list
*/
static int check_free_list(int line, int li){
  void* start_ptr = MOVE_WORD(mem_heap_lo(), SEGLIST_NUM);
  void* end_ptr = MOVE_BYTE(start_ptr, mem_heapsize()) - (SEGLIST_NUM + 1); 
  void* pred_pp = NULL;
  int count = 0;

  for(void* pp = seglist[li]; pp != NULL; pp = GET_SUCC(pp)){
    // check if block is free
    if (!IS_FREE(pp)){
      printf("Error at %d: Seglist[%d] contains an allocated-block %p.\n",
        line, li, pp);
    }
    // check if free-block in heap range
    if (pp <= start_ptr || pp >= end_ptr){
      printf("Error at %d: Seglist[%d] contains a free-block %p out of the heap range.\n",
        line, li, pp);
    }
    // check the predecessor pointer
    if (pred_pp != GET_PRED(pp)){
      printf("Error at %d: in Seglist[%d], inconsistant predecessor link at %p.\n",
        line, li, pp );
    }

    ++count;
    pred_pp = pp;
  }

  return count;
}

#endif

---

references

• computer systems chapter 9
• clear.rice.edu
• snu.c.kr

---

🤗 오타, 수정해야할 내용은 댓글로 부탁드립니다. 공부 중인 내용을 정리하여 올린 것이므로 틀린 내용에 관해서 코멘트 및 질문 환영합니다.