선언부

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

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

#define ALIGNMENT 8

#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

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

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

#define PACK(size, alloc) ((size) | (alloc))    //블록 크기 + 할당 정보 합침 ->  header, footer에 할당할 수 있는 값 알림

#define GET(p)     (*(unsigned int *)(p)) 
#define PUT(p,val) (*(unsigned int *)(p) = (val))

#define GET_SIZE(p)  (GET(p) & ~0x7) // 블록 크기정보 반환
#define GET_ALLOC(p) (GET(p) & 0x1)  // 블록이 할당되었는지 유무 반환

#define HDRP(bp) ((char *)(bp) - WSIZE) // header 주소
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // footer 주소 

#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) // next block pointer
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) // prev block pointer

#define PRED_FREE(bp) (*(void**)(bp))   //이전 free block pointer
#define SUCC_FREE(bp) (*(void**)(bp + WSIZE))   //다음 free block pointer

static void* heap_listp; // heap 시작주소 pointer
static void* segregation_list[LISTLIMIT];

static void* extend_heap(size_t words);
static void* coalesce(void* bp);
static void* first_fit(size_t a_size);
static void place(void* bp, size_t a_size);

static void remove_block(void* bp);
static void insert_block(void* bp, size_t size);

구현

/*
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
    int list;

    for (list = 0; list < LISTLIMIT; list++) {
        segregation_list[list] = NULL;     // segregation_list를 NULL로 초기화
    }                                      // 나중에 그 list에는 값이 없음을 표시할 수 있도록. 

    /* 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);  //set pointer 
    
    
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL) //extend heap
    {
        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.
 */
void* mm_malloc(size_t size)
{
    int a_size = ALIGN(size + SIZE_T_SIZE); //수정해볼것

    // size_t a_size;      /* Adjusted block size */
    size_t extend_size; /* Amount to extend heap if no fit */
    char* bp;

    /* Search the free list for a fit */
    if ((bp = first_fit(a_size)) != NULL)
    {
        place(bp, a_size);               //가능하면 분할
        return bp;
    }

    // free block 못찾음
    extend_size = MAX(a_size, CHUNKSIZE);
    if ((bp = extend_heap(extend_size / WSIZE)) == NULL) //heap 확장
    {
        return NULL;
    }
    place(bp, a_size);
    return bp;
}

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void* bp)
{
    size_t size = GET_SIZE(HDRP(bp));

    PUT(HDRP(bp), PACK(size, 0)); //free
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp); // 연결
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void* mm_realloc(void* bp, size_t size)
{
    void* old_bp = bp;
    void* new_bp;
    size_t copySize;

    new_bp = mm_malloc(size); //새로 할당

    if (new_bp == NULL) return NULL;

    copySize = GET_SIZE(HDRP(old_bp));

    if (size < copySize) // 이전 블록보다 요구되는 크기가 작으면 크기 줄이기
        copySize = size;

    //  old_bp 메모리 영역에서 new_bp 메모리 영역으로 copySize byte 만큼 복사
    memcpy(new_bp, old_bp, copySize);

    mm_free(old_bp);

    return new_bp;
}

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

    //짝수로 할당 -> double word alignment
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1)
    {
        return NULL;
    }

    
    PUT(HDRP(bp), PACK(size, 0));         //free block header
    PUT(FTRP(bp), PACK(size, 0));         //free block footer
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); //new epilogue header

    
    return coalesce(bp);    // coalesce if the previous block was free
}

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) { // prev next 모두 할당
        insert_block(bp, size); //그냥 블록 그대로 넣으면 됨
        return bp;
    }

    else if (prev_alloc && !next_alloc) // next free
    {
        remove_block(NEXT_BLKP(bp)); // 합쳐질거기때문에 -> free block list에서 제거

        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));   // hd, ft update
        PUT(FTRP(bp), PACK(size, 0));
    }

    else if (!prev_alloc && next_alloc) // prev free
    {
        remove_block(PREV_BLKP(bp)); // 합쳐질거기때문에 -> free block list에서 제거

        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        
        PUT(FTRP(bp), PACK(size, 0));   // hd, ft update
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));

        bp = PREV_BLKP(bp);
    }

    else if (!prev_alloc && !next_alloc) // prev, next all free
    {
        remove_block(PREV_BLKP(bp)); // 합쳐질거기때문에 -> free block list에서 제거
        remove_block(NEXT_BLKP(bp));

        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); //bp를 prev로 옮겨줌

    }

    insert_block(bp, size); // 연결된 블록 free block list에 삽입

    return bp;
}

static void place(void* bp, size_t a_size) //분할
{
    size_t c_size = GET_SIZE(HDRP(bp)); //current size
   
    remove_block(bp); //할당된 것이므로 지움

    
    if ((c_size - a_size) >= (2 * DSIZE)) // 한 블록 생성 가능할 정도로 여유
    {   
        PUT(HDRP(bp), PACK(a_size, 1));
        PUT(FTRP(bp), PACK(a_size, 1));

        bp = NEXT_BLKP(bp); 
        
   
        PUT(HDRP(bp), PACK(c_size - a_size, 0)); // 나머지 공간은 free 
        PUT(FTRP(bp), PACK(c_size - a_size, 0));

        coalesce(bp); //연결. 뒤에 free 블럭이 있을수도 있으니까
    }                   // coalesce 함수에 들어가면 무조건 insert를 하게 됨
    
    else // 그냥 할당
    {
        PUT(HDRP(bp), PACK(c_size, 1));
        PUT(FTRP(bp), PACK(c_size, 1));
    }
}

static void* first_fit(size_t a_size)
{
    void* bp;

    int idx = 0;
    size_t searchsize = a_size;

    while (idx < LISTLIMIT) {

        // 마지막 인덱스 도달 or segregation_list가 NULL이 아닐경우
        if ((idx == LISTLIMIT - 1) || (searchsize <= 1) && (segregation_list[idx] != NULL)) {
            bp = segregation_list[idx]; //현재 인덱스에 해당하는 list를 bp에 저장

            while ((bp != NULL) && (a_size > GET_SIZE(HDRP(bp)))) { // 더 큰 free 블록이 필요 => 할당불가
                bp = SUCC_FREE(bp); //다음 free block으로 bp이동
            }
            if (bp != NULL) { // 찾음
                return bp; // 할당
            }
        }
        searchsize >>= 1; //searchsize 감소시킴
        idx++;
    }

    return NULL;

}

static void remove_block(void* bp) { //free block list에서 제거
    int idx = 0;
    size_t size = GET_SIZE(HDRP(bp));

    while ((idx < LISTLIMIT - 1) && (size > 1)) { //지우고자 하는 list idx 찾아들어감
        size >>= 1; // size 감소시킴
        idx++;
    }

    if (SUCC_FREE(bp) != NULL) { // 다음 블록이 할당되어있음
        if (PRED_FREE(bp) != NULL) { // 이전 블록이 할당되어있음 (중간에 있는걸 지우는 경우)

            // a <-> bp <-> b
            PRED_FREE(SUCC_FREE(bp)) = PRED_FREE(bp); // a <- b
            SUCC_FREE(PRED_FREE(bp)) = SUCC_FREE(bp); // a <-> b
        }
        else { // 이전 블록이 NULL일 경우 (list에서 맨 처음을 지우는 경우) NULL <-> bp <-> a
            PRED_FREE(SUCC_FREE(bp)) = NULL; // NULL <- a 
            segregation_list[idx] = SUCC_FREE(bp); // a를 처음으로 셋팅
        }
    }
    else { // 다음 블록이 free일 경우

        // a <-> bp <-> NULL
        if (PRED_FREE(bp) != NULL) { // 이전블록이 할당되어있음 = 리스트의 끝의 블록을 지우는 경우
            SUCC_FREE(PRED_FREE(bp)) = NULL; // a <-> NULL
        }
        else { // 애초에 하나만 존재했을 경우
            segregation_list[idx] = NULL; // NULL로 설정
        }
    }
    return;
}

static void insert_block(void* bp, size_t size) {   //free block list에 삽입
    int idx = 0;
    void* search_ptr;
    void* insert_ptr = NULL; //search_ptr의 값 저장해놓음

    while ((idx < LISTLIMIT - 1) && (size > 1)) { //segregation_list의 idx를 찾는 과정
        size >>= 1; //size 감소시킴. 2의 지수승으로 인덱스를 나누어 리스트를 관리하므로 size의 비트를 하나씩 제거하며 카운트를 세면 그 카운트수가 리스트의 index가 됨.
        idx++;
    }

    search_ptr = segregation_list[idx];
    //오름차순으로 저장하기 위해 삽입하려는 블럭보다 사이즈가 작은것들은 패스
    while ((search_ptr != NULL) && (size > GET_SIZE(HDRP(search_ptr)))) {
        insert_ptr = search_ptr;
        search_ptr = SUCC_FREE(search_ptr); //succ로 계속 넘어가서 찾는다.
    }

    if (search_ptr != NULL) { //search_ptr이 NULL이 아닐 때 = 다음 블록이 있음
        if (insert_ptr != NULL) { //insert_ptr이 NULL이 아닐 때 = 이전 블록이 있음

            //  insert, search 사이에 넣는 경우 : insert_ptr <-> search_ptr 
            SUCC_FREE(bp) = search_ptr; // bp -> search_ptr
            PRED_FREE(bp) = insert_ptr; // insert_ptr <- bp -> search_ptr

            PRED_FREE(search_ptr) = bp; // insert_ptr <- bp <-> search_ptr
            SUCC_FREE(insert_ptr) = bp; // insert_ptr <-> bp <-> search_ptr
        }

        else { //insert_ptr이 NULL일 때 = 이전 블록이 없음 (제일 작음)

                                            // search_ptr
            SUCC_FREE(bp) = search_ptr;     // bp -> search_ptr
            PRED_FREE(bp) = NULL;           // NULL <- bp -> search_ptr

            PRED_FREE(search_ptr) = bp;     //  NULL <- bp <-> search_ptr

            segregation_list[idx] = bp;     //segregation_list update
        }
    }

    else { // search_ptr이 NULL일 때 = 다음 블록이 없음
        if (insert_ptr != NULL) {       // insert_ptr이 NULL이 아닐때 = 이전 블록이 있음 // 처음 시작할 때는 이 코드가 돌아갈 일이 없지만

                                         // insert_ptr
            SUCC_FREE(bp) = NULL;       // bp -> NULL
            PRED_FREE(bp) = insert_ptr; // insert_ptr <- bp -> NULL
            SUCC_FREE(insert_ptr) = bp; // insert_ptr <-> bp -> NULL
        }
        else { // 아무것도 없어서 list에 내가 처음 넣을 때
            SUCC_FREE(bp) = NULL; // bp -> NULL
            PRED_FREE(bp) = NULL; // NULL <- bp -> NULL
            segregation_list[idx] = bp; //segregation_list update
        }
    }

    return;
}