책에 있는 예제를 그대로 작성 후 코드를 분석해보았다.

1st try [implicit free list & first fit]

• Free 블록 찾기 👉 implicit free list
• 할당할 블록 선택하기 👉 first fit
• free 블록 나누기 👉 나눔
• Coalescing free blocks 👉 일단 바로 합침(?)

성능 최적화를 하기보다는 가장 쉬운 방법만 선택해서 구현되었다.
이렇게 채점을 돌리면 딱 54점이 나온다.

---

prerequisite learning

동적 할당

• malloc, (calloc), realloc 비교
• brk, sbrk
• chunk

C 문법

• include 헤더
• 전처리기, 매크로 함수
• 비트 시프트 연산자(<<)

기타

• makefile

---

구현 방식

mm_malloc 함수가 가장 큰 줄기를 차지한다. allocate(할당)함.
남은 free공간 중 요청받은 사이즈를 할당할만한 공간이 남았는지 확인해서(find_fit)
남았다면 place()로 할당, 남지 않았다면 extend_heap()으로 힙 공간을 늘려준다.

place()에서는 공간이 다시 분할되어야되는지 판단한다.
분할되면 bp와 header footer
header, footer를 옮겨주고 할당정보(0 or 1)를 표시한다.

mm_init은 빈 heap공간을 초기화하고 extend_heap을 호출한다.

find_fit에서는 할당할만한 free 공간 중 적절한 공간을 찾아서 그 공간의 주소값을 반환한다(first fit, next fit, best fit policy) mm_malloc에서 이 반환값을 보고 payload를 place하거나 힙공간을 추가로 할당한(extend_heap)다.

extend_heap에서는 요청된 size를 주소값에 맞게 변경해 CHUNKSIZE만큼 heap공간을 늘린 뒤 앞의 공간과 합친다. (coalesce 호출)

mm_free는 할당돼있던 메모리 공간을 free하고 coalesce를 호출해 합친다.

mm_realloc은 old_ptr와 할당할 size를 매개변수로 받는다. size에 맞는 메모리 공간을 찾아 old_ptr에 있는 데이터를 복사해 이사시킨다. 기존 데이터는 free해준다.

---

Prologue block & Epilogue block

이 구조를 만드는 이유?

• prologue 병합에 유용
• 주소 alignment를 위해서
• while문에서 사이즈가 0이 아닌 조건 : 유일하게 사이즈가 0인 에필로그 블록으로 heap의 끝을 알 수 있다.

프롤로그 블록 :

header & footer로만 구성된 8바이트 allocated 블록. init때 생성되어 절대 return되지 않는다.

에필로그 블록 :

header만 있는 0바이트 사이즈값을 저장하는 블록.

이 둘은 연결 과정 동안에 가장자리 조건을 없애주기 위한 속임수다.

static char *heap_listp

allocater는 한 개의 정적 전역변수👆를 사용하며, 항상 프롤로그 블록을 가리킨다.

Code

CHUNKSIZE(= 2^12)를 어떻게 정했지? => 임의로 정한 듯
https://bozeury.tistory.com/entry/%ED%9E%99Heap%EA%B3%BC-%EC%8A%A4%ED%83%9DStack%EC%9D%98-%EC%B5%9C%EB%8C%80-%ED%81%AC%EA%B8%B0

MACRO 함수 정의

/*Basic constants and macros*/
#define WSIZE 4             /*Word and header/footer size (bytes)*/
#define DSIZE 8             /*Double word size (bytes)*/
#define CHUNKSIZE (1<<12)   /*Extend heap by this amount (bytes)*/

#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)          (*(unsigned int *)(p))
#define PUT(p, val)     (*(unsigned int *)(p) = (val))

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

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

/* Giveb block ptr bp, compute address of next and previous blocks*/
#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;

mm_malloc()

void *mm_malloc(size_t size)
{
    size_t asize;       /* Adjusted block size*/
    size_t extendsize; /* Amount to extend heap if no fit */    /*공간이 모자라면 추가적으로 확장할 공간 크기*/
    char *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);    /*size > DSIZE*/
    // asize => padding을 포함해 조정된 payload의 크기

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

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

find_fit()

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
    */
   /* next-fit search */
char *bp = next_fit;
    // Search from next_fit to the end of the heap
    for (next_fit = bp; GET_SIZE(HDRP(next_fit)) > 0; next_fit = NEXT_BLKP(next_fit))
    {
        if (!GET_ALLOC(HDRP(next_fit)) && (asize <= GET_SIZE(HDRP(next_fit))))
        {
            // If a fit is found, return the address the of block pointer
            return next_fit;
        }
    }
    // If no fit is found by the end of the heap, start the search from the
    // beginning of the heap to the original next_fit location
    for (next_fit = heap_listp; next_fit < bp; next_fit = NEXT_BLKP(next_fit))
    {
        if (!GET_ALLOC(HDRP(next_fit)) && (asize <= GET_SIZE(HDRP(next_fit))))
        {
            return next_fit;
        }
    }
    return NULL; /* No fit */

}

place()

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

    if ((csize - asize) >= (2*DSIZE)){  
        /* 분할 후에 이 블록의 나머지가 최소 블록 크기(16 bytes)와 같거나 크다면 */
        /* asize 할당 후 남은 공간 분할 후 빈 공간으로 둠 */
        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));
    }
}

extend_heap()

힙을 CHUNKSIZE 바이트로 확장하고, mem_sbrk(size)를 호출한다.

• extendheap은 init()에서 처음 힙이 초기화될 때, mm_malloc이 적당한 fit을 찾지 못해서 추가 메모리공간이 필요할 때 호출된다.
  
  _mm_init 뒤에 바로 extend_heap이 호출되는 경우

static void *extend_heap(size_t words)
{
    /*
        새 가용 블록으로 힙 확장하기
    */

    char *bp;
    size_t size;

    /* Allocate an even numbers of words to maintain alignment */
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if ((long)(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 if the previous block was free : Coalesce - 앞 뒤봐서 남는공간 합치기*/
    return coalesce(bp);
}

mm_init() : CHUNKSIZE크기의 empty heap 생성

int mm_init(void)
{
 /* 
 *  mm_init - Create the initial empty heap
 *  최초 가용 블록으로 힙 생성하기
 */
    if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1) {
        return -1;
    }

    PUT(heap_listp, 0);                                /* Alignment padding */
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1));       /* Prologue header */
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1));       /* Prologue footer */
    PUT(heap_listp + (3*WSIZE), PACK(0, 1));           /* Epilogue header */
    heap_listp += (2*WSIZE);
    next_fit = heap_listp;

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

mem_sbrk(size) : heap범위 안이라면 mem_brk의 값을 size만큼 키우고, 키우기 전의 mem_brk(old_brk)의 값을 반환한다. memlib.c 파일에 존재

free

void mm_free(void *bp)
{
    //printf("here free is\n");
    //printf("free : %p\n",bp);
    size_t size = GET_SIZE(HDRP(bp));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp);
}

realloc

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