Malloc LAB Implicit List, First Fit 방식 구현

Malloc LAB Implicit List, First Fit 방식 구현

[참조 사이트]

https://e-juhee.tistory.com/entry/c%EC%96%B8%EC%96%B4-Malloc-Lab-%EB%8F%99%EC%A0%81-%ED%95%A0%EB%8B%B9%EA%B8%B0-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-Implicit-List-Explicit-List-Segregated-List-Buddy-System

※ 코드 작성하실 때, 함수 순서를 꼭 지켜주셔야합니다! 그렇지 않으면 C언어 특성상 호출된 함수가 본인보다 뒤에 있으면 읽지 못해 세그멘테이션 오류를 일으킵니다!(자세한 내용은 전체 코드를 확인해주세요)

앞으로 우리는 mm.c 라는 파일만을 수정하여 Malloc을 구현합니다. 밑에 내용은 Malloc에 들어가야하는 요소들을 정리한 것입니다. CSAPP에 나오는 제일 기본의 Malloc Lab 방식입니다.

• 해당 방식은 44 (이용도) + 6 (처리량) = 50 가 나옵니다. 참고로 환경마다 다른 점수가 나옵니다.

1. 기본 상수와 매크로 정의

사용 할 헤더파일들을 include하고, 자주 사용하는 매크로와 상수들을 미리 정의해놓습니다.

// 기본적인 include 항목들
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

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

// 기본 상수
#define WSIZE 4                // 글자, 헤더, 풋터 크기 4byte
#define DSIZE 8                // 더블(부동소수점) 글자 크기 8byte
#define CHUNKSIZE (1<<12)      // 힙 확장을 위한 기본 크기(초기의 빈 블록의 크기)

// 매크로
#define MAX(x, y)  ((x) > (y) ? (x) : (y))

// size와 할당 비트를 결합, header와 footer에 저장할 값
#define PACK(size, alloc)  ((size) | (alloc))

// p가 참조하는 워드 반환(포인터라서 직접 역참조 불가능 -> 타입 캐스팅)
#define GET(p)        (*(unsigned int *)(p))
// p에 val 저장
#define PUT(p, val)   (*(unsigned int *)(p) = (val))

// 사이즈 (~0x7: ...11111000, '&' 연산으로 뒤에 세자리 없어짐)
#define GET_SIZE(p)   (GET(p) & ~0x7)
// 할당 상태
#define GET_ALLOC(p)  (GET(p) & 0x1)

// Header 포인터
#define HDRP(bp)      ((char *)(bp) - WSIZE)
// Footer 포인터 (Header의 정보를 참조해서 가져오기 때문에, Header의 정보를 변경했다면 변경된 위치의 Footer가 반환됨)
#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)))

2. Heap 생성하기 (mm_init)

최초 가용 블록으로 힙을 생성합니다.

• 초기에 ‘정렬 패딩(unused) + 프롤로그 header + 프롤로그 footer + 에필로그 header’를 담기 위해 4워드 크기의 힙을 생성합니다.
• 생성 후 CHUNKSIZE만큼 추가 메모리를 요청해 힙의 크기를 확장한다.

// mm_init - initialize the malloc package.
// 힙생성하기, 패딩 + 프롤로그 헤더 + 프롤로그 풋터 + 에필로그 풋터를 담기위해 4워드 크기합을 구성함
// 생성 후 CHUNKSIZE만큼 추가 메모리를 요청해 힙의 크기를 확장
int mm_init(void)
{
    char *heap_listp;    // 초기 힙을 생성한다 

    if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)    // 4워드 크기의 힙 생성, heap_listp에 힙의 시작 주소값 할당
        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)      // free블록으로 빈 힙을 CHUNKSIZE bytes로 확장
        return -1;
    return 0;
}

3. Heap 확장하기 (extend_heap)

위에 호출되는 함수인 extend_heap입니다. 새 가용 블록으로 힙을 확장합니다.

• 추가 메모리 요청: 요청받은 words만큼 추가 메모리를 요청한다. (mem_sbrk 함수 요청)
• 추가 메모리 요청에 성공하면 새로운 메모리를 새 빈 블록으로 만든다.
  새 빈 블록의 header, footer를 초기화하고 힙의 끝부분을 나타내는 에필로그 블록의 헤더도 변경한다.

// 힙 확장: 새 가용 블록으로 힙을 확장한다.
static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;

    // 더블 워드 정렬 유지
    // size: 확장할 크기
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;   // 더블워드의 가장 가까운 배수로 반올림(홀수면 1 더해서 곱한다)
    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);     // 병합 후 coalesce 함수에서 리턴된 블록 포인터 반환
}

4. 블록 반환하기 (mm_free)

블록을 반환하고 공개 태그 연결을 사용해서 상수 시간에 인접 가용 블록들과 통합한다.

• 가용 상태로 변경: 블록의 상태를 할당 상태에서 가용 상태로 변경한다. (PACK 매크로 호출)
• 병합: 주소상으로 인접한 블록에 빈 블록이 있다면 연결한다. (coalesce 함수 호출)

// mm_free - Freeing a block does nothing.
// 블록 반환하기
void mm_free(void *bp)
{
    size_t size = GET_SIZE(HDRP(bp));  // 현재 블록(bp)의 헤더를 읽어서 블록 크기(size)를 가져옴

    PUT(HDRP(bp), PACK(size, 0));      // 블록의 헤더(Header) 정보를 업데이트: size 그대로, 할당 비트(allocation bit)는 0 (free 상태)
    PUT(FTRP(bp), PACK(size, 0));      // 블록의 푸터(Footer) 정보도 업데이트: size 그대로, 할당 비트는 0 (free 상태)
    coalesce(bp);                      // 인접한 가용 블록들과 병합(Coalesce) 시도
}

4-1. 병합 (coalesce)

• 할당 여부 확인 : 인접 블록의 할당 상태를 확인한다. (GET_ALLOC 매크로 호출)
• 병합 : 인접 블록 중 가용 상태인 블록이 있다면 현재 블록과 합쳐서 더 큰 하나의 가용 블록으로 만든다.

// 상수 시간에 인접 가용 블록 병합하기
static void *coalesce(void *bp) {
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));  // 이전 블록 할당 상태 가져옴(0 = free, 1 = allocated)
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));  // 다음 블록 할당 상태 가져옴(0 = free, 1 = allocated)
    size_t size = GET_SIZE(HDRP(bp));                    // 현재 블록 사이즈

     /// case 1. 이전 블록과 다음 블록 모두 할당된 경우 (병합 불가)
    if (prev_alloc && next_alloc) {             
        return bp;
    }

    // Case 2: 이전 블록은 할당, 다음 블록은 가용(free)한 경우
    else if (prev_alloc && !next_alloc) {        
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));    // 현재 블록과 다음 블록을 합쳐 크기를 늘림
        PUT(HDRP(bp), PACK(size, 0));             // 현재 블록의 헤더를 새 size로 업데이트 (free 상태)
        PUT(FTRP(bp), PACK(size, 0));             // 합쳐진 블록의 푸터를 새 size로 업데이트
    }

    /// case 3: 이전 블록은 가용(free), 다음 블록은 할당된 경우
    else if (!prev_alloc && next_alloc) {      
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));    // 이전 블록과 현재 블록을 합쳐 크기를 늘린다
        PUT(FTRP(bp), PACK(size, 0));             // 이전 블록의 헤더를 새 size로 업데이트(free)
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));  // 현재 블록의 푸터를 새 size로 업데이트
        bp = PREV_BLKP(bp);                       // bp를 병합된 블록(이전 블록) 쪽으로 이동
    }

    else {                                                       // Case 3: 이전 블록은 가용(free), 다음 블록은 할당된 경우
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));   // 이전 블록 + 현재 블록 + 다음 블록을 모두 합쳐 크기를 늘림
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));                 // 이전 블록의 헤더를 새 size로 업데이트 (free 상태)
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));                 // 다음 블록의 푸터를 새 size로 업데이트 (free 상태)
        bp = PREV_BLKP(bp);                                      // bp를 병합된 블록(이전 블록) 쪽으로 이동
    }
    return bp;       // 병합이 끝난 블록의 포인터를 반환
}

5. 가용 블록에 할당하기(mm_malloc)

• 사이즈 조정
  • 할당 요청이 들어오면(malloc 함수 호출) 요청 받은 size 를 조정합니다.
  • 블록의 크기는 적어도 16바이트 이상이어야 합니다. (header 4Bytes + footer 4B + payload 8B)
  • 블록의 크기는 8의 배수이어야 하므로(정렬 요건), 항상 8의 배수가 되도록 올림 처리합니다.
• 가용 블록 검색(step 1)
  • 조정된 사이즈를 가지고 있는 블록을 검색합니다. (find_fit 함수 호출)
  • 적합한 블록을 찾았다면 해당 블록에 할당합니다. (place 함수 호출)
• 힙 확장(step 2)
  • 적합한 블록이 없는 경우, 추가 메모리를 요청해 힙을 확장합니다. (extend_heap 함수 호출)
  • 힙을 확장하고 나서 받은 새 메모리 블록에 할당합니다. (place 함수 호출)

// mm_malloc - Allocate a block by incrementing the brk pointer.
// Always allocate a block whose size is a multiple of the alignment.
// brk 포인터를 증가시켜 블록을 할당합니다. 항상 정렬 크기의 배수인 블록을 할당합니다.
void *mm_malloc(size_t size)
{
    size_t asize;           // 요청된 크기를 조정한 블록 크기 (payload + overhead 포함)
    size_t extendsize;      // heap을 확장할 사이즈
    char *bp;               // 새로 할당할 블록 포인터

    // 잘못된 요청 처리: size가 0이면 NULL 반환
    if(size == 0)
        return NULL;

    // 요청 크기 조정 (payload + header/footer 포함, alignment 맞추기)
    if (size <= DSIZE)        // 8바이트 이하 시
        asize = 2*DSIZE;      // 최소 블록 크기 16바이트 할당 (헤더 4 + 푸터 4 + 저장공간 8)
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);     // size에 overhead 추가하고, DSIZE 단위로 8의 배수로 올림 (align)

    // Step 1: 가용 리스트에서 알맞은 블록 찾기
    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);     // 블록을 할당하고
        return bp;            // 포인터 반환
    }

    // Step 2: 가용 블록이 없으면 힙을 확장
    extendsize = MAX(asize, CHUNKSIZE);     // 최소 CHUNKSIZE만큼은 확장
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
        return NULL;    // 확장 실패시 NULL 반환

    place(bp, asize);   // 새로 확장한 블록에 메모리 배치
    return bp;          // 새 블록 포인터 반환
}

6. 가용 블록 검색하기(find_fit)[First-fit]

• 힙의 첫번째 블록부터 탐색을 시작합니다.
• 가용 상태이면서 현재 필요한 크기인 asize 를 담을 수 있는 블록을 찾을 때까지 탐색을 이어갑니다.
  (First-fit)

// 검색 후 가용블록 반환하기
// 가용 리스트를 순차적으로 검색해서, 요청 크기 이상의 가용 블록을 찾아 반환한다
static void *find_fit(size_t asize)
{
    void *bp = mem_heap_lo() + 2 * WSIZE;   // 힙 시작 주소에서 2워드(8바이트)를 건너뛴 곳(첫 블록)부터 탐색 시작

    // 힙의 끝까지 순차적으로 블록 탐색
    while (GET_SIZE(HDRP(bp)) > 0)
    {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))   // 현재 블록이 가용 상태이고, 요청 크기(asize)를 수용할 수 있으면
            return bp;                                               // 현재 블록 포인터 반환

        bp = NEXT_BLKP(bp);                                          // 조건에 맞지 않으면 다음 블록으로 이동해서 탐색을 이어감
    }
    return NULL;    // 끝까지 탐색했지만 맞는 블록이 없으면 NULL 반환
}

7. 블록 분할 및 할당하기 (place)

• 선택한 가용 블록이 사용할 사이즈보다 큰 사이즈를 가지고 있다면,
  필요한 사이즈만큼만 사용하고 나머지는 분할하여 또다른 가용 블록으로 남겨둔다.

// 효과적으로 분할하기
// 블록을 할당할 때, 남는 공간이 충분하면 블록을 분할(split) 하고, 그렇지 않으면 그냥 전체 블록을 할당한다
static void place(void *bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));     // 현재 블록의 전체 크기 가져오기

    if ((csize - asize) >= (2 * DSIZE))    // Case 1: 블록을 분할할 수 있는 경우 (남은 크기가 최소 블록 크기 이상일 때)
    {
        // 현재 블록에 asize 크기만큼 할당 표시
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));

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

    else                                   // Case 2: 블록을 분할하지 않고 통째로 사용하는 경우
    {
        // 현재 블록 전체를 할당 표시
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

8. 가용 블록 재할당하기(mm_realloc)

예외 처리

• 인자로 전달 받은 ptr이 NULL인 경우에는 할당만 수행합니다. (mm_malloc 함수 호출)
• 인자로 전달 받은 size가 0인 경우에는 메모리 반환만 수행합니다. (mm_free 함수 호출)

1 ~ 2. 새 블록에 할당

• 할당: 인자로 전달 받은 size만큼 할당할 수 있는 블록을 찾아 할당합니다. (mm_malloc 함수 호출)

3 ~ 4. 데이터 복사

• ptr이 가리키고 있던 블록이 가지고 있는 payload 크기를 구하고,새로 할당할 size보다 기존의 크기가 크다면 size로 크기를 조정합니다.
• 조정한 size만큼 새로 할당한 블록으로 데이터를 복사합니다. (memcpy 함수 호출)

5. 기존 블록 반환

• 데이터 복사 후, 기존 블록의 메모리를 반환한다. (mm_free 함수 호출)

/*
 * 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;       // 복사할 데이터 크기

    // Step 1: 새 크기만큼 메모리를 할당
    newptr = mm_malloc(size);
    if (newptr == NULL)    // 메모리 할당 실패 시 NULL 반환
        return NULL;       

    // Step 2: 기존 블록의 크기 읽기
    copySize = GET_SIZE(HDRP(oldptr));

    // Step 3: 복사할 크기를 요청 크기로 조정 (원래 블록이 더 크면 size까지만 복사)
    if (size < copySize)
        copySize = size;

    // Step 4: 데이터 복사
    memcpy(newptr, oldptr, copySize);

    // Step 5: 기존 블록 반환 (free)
    mm_free(oldptr);

    return newptr;         // 새 블록 포인터 반환
}

재할당 최적화 포인트

• 실제 고급 malloc 구현에서는
  • 기존 블록이 크면 그대로 반환(realloc-in-place),
  • 또는 이웃 블록 병합(coalescing)해서 크기 늘리기 같은 고급 최적화를 추가하기도 한다.

(지금 이 mm_realloc은 항상 새로 할당 → 복사 → 해제하는 아주 기본 버전이야.)

Implicit List, First Fit 방식 C언어 전체 코드

/*
 * mm-naive.c - 가장 빠르지만 메모리 효율이 가장 낮은 malloc 패키지입니다.
 * 이 단순 접근 방식에서는 brk 포인터를 단순히 증가시켜 블록을 할당합니다.
 * 블록은 순수한 페이로드입니다. 헤더나 푸터가 없습니다. 블록은 병합되거나 재사용되지 않습니다.
 * realloc은 mm_malloc과 mm_free를 사용하여 직접 구현됩니다.
 *
 * 참고: 이 헤더 주석을 해결책에 대한 간략한 설명을 제공하는 자체 헤더 주석으로 바꾸세요.
 */
#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 */
    "5team",
    /* First member's full name */
    "Kim Taeyong",
    /* 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 WSIZE 4                // 글자, 헤더, 풋터 크기 4byte
#define DSIZE 8                // 더블(부동소수점) 글자 크기 8byte
#define CHUNKSIZE (1<<12)      // 힙 확장을 위한 기본 크기(초기의 빈 블록의 크기)

// 매크로
#define MAX(x, y)  ((x) > (y) ? (x) : (y))

// size와 할당 비트를 결합, header와 footer에 저장할 값
#define PACK(size, alloc)  ((size) | (alloc))

// p가 참조하는 워드 반환(포인터라서 직접 역참조 불가능 -> 타입 캐스팅)
#define GET(p)        (*(unsigned int *)(p))
// p에 val 저장
#define PUT(p, val)   (*(unsigned int *)(p) = (val))

// 사이즈 (~0x7: ...11111000, '&' 연산으로 뒤에 세자리 없어짐)
#define GET_SIZE(p)   (GET(p) & ~0x7)
// 할당 상태
#define GET_ALLOC(p)  (GET(p) & 0x1)

// Header 포인터
#define HDRP(bp)      ((char *)(bp) - WSIZE)
// Footer 포인터 (Header의 정보를 참조해서 가져오기 때문에, Header의 정보를 변경했다면 변경된 위치의 Footer가 반환됨에 유의)
#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 void *coalesce(void *bp) {
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));  // 이전 블록 할당 상태 가져옴(0 = free, 1 = allocated)
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));  // 다음 블록 할당 상태 가져옴(0 = free, 1 = allocated)
    size_t size = GET_SIZE(HDRP(bp));                    // 현재 블록 사이즈

     /// case 1. 이전 블록과 다음 블록 모두 할당된 경우 (병합 불가)
    if (prev_alloc && next_alloc) {
        return bp;
    }

    // Case 2: 이전 블록은 할당, 다음 블록은 가용(free)한 경우
    else if (prev_alloc && !next_alloc) {        
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));    // 현재 블록과 다음 블록을 합쳐 크기를 늘림
        PUT(HDRP(bp), PACK(size, 0));             // 현재 블록의 헤더를 새 size로 업데이트 (free 상태)
        PUT(FTRP(bp), PACK(size, 0));             // 합쳐진 블록의 푸터를 새 size로 업데이트
    }

    /// case 3: 이전 블록은 가용(free), 다음 블록은 할당된 경우
    else if (!prev_alloc && next_alloc) {      
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));    // 이전 블록과 현재 블록을 합쳐 크기를 늘린다
        PUT(FTRP(bp), PACK(size, 0));             // 이전 블록의 헤더를 새 size로 업데이트(free)
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));  // 현재 블록의 푸터를 새 size로 업데이트
        bp = PREV_BLKP(bp);                       // bp를 병합된 블록(이전 블록) 쪽으로 이동
    }

    else {                                                       // Case 3: 이전 블록은 가용(free), 다음 블록은 할당된 경우
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));   // 이전 블록 + 현재 블록 + 다음 블록을 모두 합쳐 크기를 늘림
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));                 // 이전 블록의 헤더를 새 size로 업데이트 (free 상태)
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));                 // 다음 블록의 푸터를 새 size로 업데이트 (free 상태)
        bp = PREV_BLKP(bp);                                      // bp를 병합된 블록(이전 블록) 쪽으로 이동
    }
    return bp;       // 병합이 끝난 블록의 포인터를 반환
}

// 힙 확장: 새 가용 블록으로 힙을 확장한다.
static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;

    // 더블 워드 정렬 유지
    // size: 확장할 크기
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;   // 더블워드의 가장 가까운 배수로 반올림(홀수면 1 더해서 곱한다)
    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);     // 병합 후 coalesce 함수에서 리턴된 블록 포인터 반환
}

/////////////////
// 검색 후 가용블록 반환하기 (First fit)
// 가용 리스트를 순차적으로 검색해서, 요청 크기 이상의 가용 블록을 찾아 반환한다
static void *find_fit(size_t asize)
{
    void *bp = mem_heap_lo() + 2 * WSIZE;   // 힙 시작 주소에서 2워드(8바이트)를 건너뛴 곳(첫 블록)부터 탐색 시작

    // 힙의 끝까지 순차적으로 블록 탐색
    while (GET_SIZE(HDRP(bp)) > 0)
    {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))   // 현재 블록이 가용 상태이고, 요청 크기(asize)를 수용할 수 있으면
            return bp;                                               // 현재 블록 포인터 반환

        bp = NEXT_BLKP(bp);                                          // 조건에 맞지 않으면 다음 블록으로 이동해서 탐색을 이어감
    }
    return NULL;    // 끝까지 탐색했지만 맞는 블록이 없으면 NULL 반환
}

// 효과적으로 분할하기
// 블록을 할당할 때, 남는 공간이 충분하면 블록을 분할(split) 하고, 그렇지 않으면 그냥 전체 블록을 할당한다
static void place(void *bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));     // 현재 블록의 전체 크기 가져오기

    if ((csize - asize) >= (2 * DSIZE))    // Case 1: 블록을 분할할 수 있는 경우 (남은 크기가 최소 블록 크기 이상일 때)
    {
        // 현재 블록에 asize 크기만큼 할당 표시
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));

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

    else                                   // Case 2: 블록을 분할하지 않고 통째로 사용하는 경우
    {
        // 현재 블록 전체를 할당 표시
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}
//////////////

// mm_init - initialize the malloc package.
// 힙 생성하기: 패딩+프롤로그 헤더+프롤로그 풋터+에필로그 풋터를 담기위해 4워드 크기합을 구성함
// 생성 후 CHUNKSIZE만큼 추가 메모리를 요청해 힙의 크기를 확장
int mm_init(void)
{
    char *heap_listp;    // 초기 힙을 생성한다 

    if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)    // 4워드 크기의 힙 생성, heap_listp에 힙의 시작 주소값 할당
        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)      // free블록으로 빈 힙을 CHUNKSIZE bytes로 확장
        return -1;
    return 0;
}

// mm_malloc - Allocate a block by incrementing the brk pointer.
// Always allocate a block whose size is a multiple of the alignment.
// 가용 블록 할당하기
// brk 포인터를 증가시켜 블록을 할당합니다. 항상 정렬 크기의 배수인 블록을 할당합니다.
void *mm_malloc(size_t size)
{
    size_t asize;           // 요청된 크기를 조정한 블록 크기 (payload + overhead 포함)
    size_t extendsize;      // heap을 확장할 사이즈
    char *bp;               // 새로 할당할 블록 포인터

    // 잘못된 요청 처리: size가 0이면 NULL 반환
    if(size == 0)
        return NULL;

    // 요청 크기 조정 (payload + header/footer 포함, alignment 맞추기)
    if (size <= DSIZE)        // 8바이트 이하 시
        asize = 2*DSIZE;      // 최소 블록 크기 16바이트 할당 (헤더 4 + 푸터 4 + 저장공간 8)
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);     // size에 overhead 추가하고, DSIZE 단위로 8의 배수로 올림 (align)

    // Step 1: 가용 리스트에서 알맞은 블록 찾기
    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);     // 블록을 할당하고
        return bp;            // 포인터 반환
    }

    // Step 2: 가용 블록이 없으면 힙을 확장
    extendsize = MAX(asize, CHUNKSIZE);     // 최소 CHUNKSIZE만큼은 확장
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
        return NULL;    // 확장 실패시 NULL 반환

    place(bp, asize);   // 새로 확장한 블록에 메모리 배치
    return bp;          // 새 블록 포인터 반환
}

// mm_free - Freeing a block does nothing.
// 블록 반환하기
void mm_free(void *bp)
{
    size_t size = GET_SIZE(HDRP(bp));  // 현재 블록(bp)의 헤더를 읽어서 블록 크기(size)를 가져옴

    PUT(HDRP(bp), PACK(size, 0));      // 블록의 헤더(Header) 정보를 업데이트: size 그대로, 할당 비트(allocation bit)는 0 (free 상태)
    PUT(FTRP(bp), PACK(size, 0));      // 블록의 푸터(Footer) 정보도 업데이트: size 그대로, 할당 비트는 0 (free 상태)
    coalesce(bp);                      // 인접한 가용 블록들과 병합(Coalesce) 시도
}

// 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;       // 복사할 데이터 크기

    // Step 1: 새 크기만큼 메모리를 할당
    newptr = mm_malloc(size);
    if (newptr == NULL)    // 메모리 할당 실패 시 NULL 반환
        return NULL;       

    // Step 2: 기존 블록의 크기 읽기
    copySize = GET_SIZE(HDRP(oldptr));

    // Step 3: 복사할 크기를 요청 크기로 조정 (원래 블록이 더 크면 size까지만 복사)
    if (size < copySize)
        copySize = size;

    // Step 4: 데이터 복사
    memcpy(newptr, oldptr, copySize);

    // Step 5: 기존 블록 반환 (free)
    mm_free(oldptr);

    return newptr;         // 새 블록 포인터 반환
}

→ Implicit List 방식의 한계(50점)

• 블록 할당 시 힙을 처음부터 탐색해나가기 때문에 최악의 경우 탐색 시간이 전체 힙 블록의 수에 비례하게 됩니다. 따라서, 범용 할당기에는 적합하지 않고 블록의 수가 적은 특수한 경우에만 사용하는 것이 좋습니다.
• 이 한계점은 가용 블록들을 명시적 자료구조로 구성하는 Explict List 방식으로 개선할 수 있습니다.
• 최종적으로 해당 방식은 44 (이용도) + 6 (처리량) = 50 가 나왔습니다. 참고로 환경마다 다른 점수가 나옵니다.