06_week_C_malloc_implementation_명시적할당기+명시적 가용 리스트

명시적 할당기 + 명시적 가용리스트 Explicit free list Address order
주소순 정렬을 사용한 방법
주소순 정렬후 first fit을 사용하면 메모리 이용도에서 보다 좋은 결과를 얻을 수 있음

implicit free list와 다른점은 heap list와 free list로 관리가 이뤄지기때문에
탐색을 하는 구간이 훨씬 줄어드는 것을 알 수 있음
(우리는 free list만 탐색)

// 명시적 할당기 + 명시적 가용 리스트 = Explicit
// 이중 연결 리스트를 사용하여 block을 allocate 하고 free함
/* implicit 가용 리스트를 사용할 때와의 차이는 
coalesce, place, insert에서 차이가 있고
delete 부분을 새로 추가해준다 (free와는 다른 동작을 함)

insert - PRED와 SUCC 까지 넣어서 앞 뒤 블록을 연결해줘야함
coalesce - 각각의 케이스에 맞춰서 진행
place - 할당시에 가용 list에서 빼와서 끊고 또 이어붙임
delete - 가용 list에서 빼오는 작업, 빼오면서 앞 뒤의 연결을 이어주고 해당 block은 제거됨

*/
/*
Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   99%    5694  0.000162 35148
 1       yes   99%    5848  0.000126 46450
 2       yes   99%    6648  0.000187 35608
 3       yes  100%    5380  0.000142 37887
 4       yes   66%   14400  0.000159 90395
 5       yes   92%    4800  0.002538  1891
 6       yes   92%    4800  0.002394  2005
 7       yes   55%   12000  0.034186   351
 8       yes   51%   24000  0.129684   185
 9       yes   27%   14401  0.044330   325
10       yes   34%   14401  0.001687  8536
Total          74%  112372  0.215595   521

Perf index = 44 (util) + 35 (thru) = 79/100
*/

#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 */
    "No.2",
    /* First member's full name */
    "ChiWoo Shin",
    /* First member's email address */
    "shin8037@naver.com",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""
};


#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1<<12) 

// Max 함수 정의
#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)

// Given 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)))

//explicit free list -- pointer의 정보를 읽어오기 위한 macro
#define PRED(bp) ((char *)(bp))
#define SUCC(bp) ((char *)(bp) + WSIZE)

//선언부 - 책에는 없지만 선언부가 없으면 동작에 문제가 생김 특히 heap_listp
static void *heap_listp = NULL;
static char *root = NULL; // root는 항상 list의 제일 앞을 보고 있음

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

/* data가 쌓이는 순서는 가장 오래된 데이터가 Top이고 가장 최신의 데이터가 bottom에 위치하게됨 즉 
PRED에는 구 주소들이 쌓이게되고
SUCC에는 최신 데이터의 값들이 쌓이게됨
*/
static void __insert(char* bp){
    char *succ; // 후계자 포인터를 선언해주고
    for (succ = GET(root); succ != NULL; succ = GET(SUCC(succ))){ // 후계자 포인터에 root의 주소를 넣고, 그 주소가 NULL이 아니면 돌리고, 후계자 포인터에 + WSIZE 한만큼 더해감
        if(bp < succ){ // bp 즉 현재 pointer가 succ보다 작으면 -- succ 이전 ptr이면
            PUT(PRED(bp), GET(PRED(succ))); // bp 포인터에 succ의 주소를 넣음
            PUT(SUCC(bp), succ); // bp의 succ 포인터에 for문의 조건문을 통해 얻은 succ 주소를 넣음

            if(GET(PRED(succ)) != NULL) // succ의 주소가 NULL이 아니면 
                PUT(SUCC(GET(PRED(succ))), bp); // 해당 주소 + wsize (succ 위치에) bp 값을 넣음
            else // succ의 주소가 NULL 이면 Root 라는 얘기 root 앞은 아무것도 없으니깐 NULL
                PUT(root, bp); // 따라서 root에 bp 값을 부여해줌
            
            PUT(PRED(succ), bp); // succ의 주소에 bp의 값을 넣음
            return;
        }
        else if(GET(SUCC(succ)) == NULL){ // succ에 해당하는 주소가 비어있고 bp가 succ 보다 클때
            PUT(PRED(bp), succ); // succ 주소를 bp에 넣어주고
            PUT(SUCC(bp), 0); // SUCC의 값을 지워줌 -- 뒤에 할당된 block이 없다
            PUT(SUCC(succ), bp); // 새로운 주소를 succ에 넣음
            return;
        }
    }
    // 위 조건들에 다 걸리지 않을 경우 - bp가 succ보다 크면서 succ에 해당하는 주소도 차있따.
    // bp가 가용 리스트의 하나뿐인 블록의 주소일 경우
    PUT(root, bp); // root에 bp 주소를 넣고
    PUT(PRED(bp), 0); // PRED, SUCC 값을 지움
    PUT(SUCC(bp), 0);
}

static void delete_node(char *bp){ // delete node의 역할은 해당 block을 비우는게 아닌 얘를 리스트에서 삭제한다는 의미
    if(GET(PRED(bp)) == NULL && GET(SUCC(bp)) == NULL) // bp가 root 이면서 혼자 있을때
        PUT(root, GET(SUCC(bp))); // root에 bp의 bp의 SUCC 주소를 넣는다 --> 즉 NULL을 넣음
    else if (GET(PRED(bp)) != NULL && GET(SUCC(bp)) == NULL) // bp가 root 가 아니면서 list의 마지막일때
        PUT(SUCC(GET(PRED(bp))), GET(SUCC(bp))); // 제일 마지막 block에 NULL을 넣음
    else if (GET(PRED(bp)) == NULL && GET(SUCC(bp)) != NULL){ // bp가 root 면서 뒤에 다른 할당된 block이 있을때
        PUT(PRED(GET(SUCC(bp))), GET(PRED(bp))); // 해당 위치에 NULL 값을 넣어줌
        PUT(root, GET(SUCC(bp))); // 다시한번 더 root에 NULL을 넣어서 확실히 함
    }
    else{ // bp의 앞, 뒤에 할당된 block이 다 있을 때
        PUT(PRED(GET(SUCC(bp))), GET(PRED(bp))); // 현재 블록의 정보를 SUCC는 앞의 블럭으로 PRED는 뒤 블럭으로 정보를 보내줌
        PUT(SUCC(GET(PRED(bp))), GET(SUCC(bp))); //
    }
    // bp는 이제 가용 블록이 아니므로 PRED, SUCC 정보를 지워줌
    PUT(PRED(bp), 0);
    PUT(SUCC(bp), 0);
}

static void *find_fit(size_t asize){  // 적합한 곳을 찾는다 first fit
    for (char *bp = GET(root); bp != NULL; bp = GET(SUCC(bp))){  // bp는 root부터 시작해서, bp 가 NULL이 아닐때 돌고, offset은 bp 에 WSIZE 만큼 이동한 주소
        if (asize <= GET_SIZE(HDRP(bp))){ // asize가 블록의 크기보다 작으면
            return bp; // 그냥 bp를 넣으면 되니깐 바로 return
        }
    }
    return NULL; // 장소가 없으면 NULL
}

static void *coalesce(void *bp) // 병합 함수
{
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // 이전 block의 footer에서 할당 여부를 prev_alloc에 저장하고
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // 다음 block의 header를 통해서 할당 여부를 next_alloc에 저장
    size_t size = GET_SIZE(HDRP(bp)); // 현재 header pointer의 크기를 size에 넣어줌

    if (prev_alloc && next_alloc){ //case 1 : current block 기준 이전과 다음 block 전부 할당
        __insert(bp); // 해당하는 bp를 insert하고 
        return bp; // 둘다 할당 상태이면 현재 block만 가용으로 return 해주면 됨
    }
    else if(prev_alloc && !next_alloc){ // case 2 : current block 기준으로 이전 block은 할당 다음 block은 가용
        delete_node(NEXT_BLKP(bp)); // 다음 블록을 비우고 
        size += GET_SIZE(HDRP(NEXT_BLKP(bp))); // 현재 header pointer의 크기에 다음 블럭의 header pointer 사이즈를 더해줌
        PUT(HDRP(bp), PACK(size, 0)); // 이때 얻은 size로 Header와 footer를 재할당
        PUT(FTRP(bp), PACK(size, 0));
        __insert(bp); // 거기에 넣자
    }
    else if(!prev_alloc && next_alloc){ // case 3 : current block 기준으로 이전 block은 가용 다음 block은 할당
        size += GET_SIZE(HDRP(PREV_BLKP(bp))); // 현재 header pointer 의 크기에 이전 블럭의 header pointer 사이즈를 더해주고
        PUT(FTRP(bp), PACK(size, 0)); // footer를 새로 얻은 size로 초기화 하고
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 블럭의 header pointer를 새로 얻은 size로 초기화
        bp = PREV_BLKP(bp); // block pointer에 이전 block pointer를 넣어서 이동 시켜줌 --> 이렇게 되면 이전 block pointer를 기준으로 두개 블록 사이즈가 연결됨 (prev block + current block)
    }
    else{ // case 4 : current block 기준 이전과 다음 모두 가용 
        delete_node(NEXT_BLKP(bp));
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp))); // 위아래 block size 전부를 더해줌 --> 즉 3개 block의 크기
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 block의 header pointer
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0)); // 다음 block의 footer pointer를 새로 할당된 size로 초기화함
        bp = PREV_BLKP(bp); // pointer 이동해주고
    }
    return bp; // 마무리로 변경된 bp를 return 함
}


static void place(void *bp, size_t asize){ 
    size_t csize = GET_SIZE(HDRP(bp)); 
    delete_node(bp); // current block을 가용 연결리스트에서 지워주고

    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));
        PUT(PRED(bp), 0);
        PUT(SUCC(bp), 0);
        coalesce(bp); // 그리고 병합
    }
    else{ 
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

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

    size = (words %2) ? (words +1)*WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1) 
        return NULL;

    // Initialize free block header/footer and the epilogue header
    PUT(HDRP(bp), PACK(size, 0)); 
    PUT(FTRP(bp), PACK(size, 0));
    PUT(PRED(bp), 0);
    PUT(SUCC(bp), 0);
    
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));

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

int mm_init(void)
{
    //Create the inital empty 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)); 
    root = heap_listp; // 초기 시작 값을 즉 top 값을 root에 저장
    heap_listp += (2*WSIZE); 

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

    return 0; 
}


void *mm_malloc(size_t size) // malloc 함수
{
    size_t asize; // Adjusted block size
    size_t extendsize; // Abount to extend heap if no fit
    char *bp;

    // ignore spurious requests
    if (size == 0) 
        return NULL;

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

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

    extendsize = MAX(asize, CHUNKSIZE); 
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
        return NULL; 
    
    place(bp, asize); 
    return bp; 

}

void mm_free(void *bp) // free를 하는 방법
{
    size_t size = GET_SIZE(HDRP(bp)); // size에 current block의 크기를 할당해줌

    PUT(HDRP(bp), PACK(size,0)); // header pointer에 사이즈는 할당하지만 할당을 해지함 free로오
    PUT(FTRP(bp), PACK(size,0)); // footer도 위 header와 동일
    PUT(PRED(bp), 0);
    PUT(SUCC(bp), 0);
    coalesce(bp); // 이전 블록과 연결해서 계속 확인
}

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