이번주는 진짜 '꿀빨았다'
-> malloc lab 의사코드 따라서 치니까 되네?
-> 코드 함 봤더니 뭔말인지 이해되네?
-> 더하는건 시간이 너무 많이 드는거 같으니 딴거해도 되겠네?
-> 다음주 다다음주 할꺼도 미리 하고 책도 보고 하고싶은 공부해도 되네?

= 책 6~9장 , 11,12장 다 읽고 네트워크 개론 + SQL 기본개념 + 데이터베이스 공부

같은 조원 분도 컴공과에 지식이 방대하셔서 같이 프로잭트 빨리 끝내고 공부했다.
6주차도 최대한 구현에만 집중하고 디테일은 타협을 해야 할 것 같다.
주니어가 소켓 프로그래밍한답시고 1주일 잡고 있으면 뭐가 달라지겠는가?

물론 뭐라도 되긴 하겠지만 너무 비효율적이다.
기본을 잡고 항상 초심을 생각하자
나는 아무것도 아는게 없고 능력도 없는 주니어'지망생'이다.

주니어조차 되지 못하는 비전공생이다.

Malloc 이란?

힙 메모리를 할당하기 위한 함수이다.
물론 brk 같은게 커널에서 쓰는 시스템콜은 맞다.

malloc 함수들은 다음과 같은 일을 한다.

1. malloc 함수를 썼을 때 , 가용페이지가 있다면 할당한다.

2. 만약 힙 메모리가 부족하다면 추가 메모리를 요청한다.(sbrk)

3. 쓰지 않는 메모리들을 삭제하는 요청을 하면 가용 페이지들을 합친다.(free)

와 같은 일을 하면 된다.
기본적인 코드들은 미리 준비가 되어 있고, 우리는 의사코드를 따라 치면서 어떤 구조로 되어있는가를 파악하면 된다. 지금 하는 프로젝트 자체도 기본 중의 기본적인 방식으로 구현하는 것이고
이런 방식을 gpt한테 물어보면 기초적인 방식이라 비효율적이고 단편화 너무 심하게 일어난다고 엄청 비꼰다.

그렇기 때문에 우리가 해야 할 일은

• 코드 이해

• malloc 할당 방식 이해

이 두가지가 되겠다.
제발 부탁이니까 점수 욕심이 나더라도 본인의 부족한 점을 먼저 채웠으면 좋겠다.

define

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)

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

// 가용리스트 조작 매크로
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1 << 12)
//4096 2의 12승 비트연산을 사용

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

#define PACK(size, alloc) ((size) | (alloc))

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

우리가 쓸 함수들을 미리 선언해주는거다.
위의 내용들은 상당히 간단한데

• WSIZE = 워드 , DSIZE = 더블 , CHUNKSIZE = 메모리 크기

• bp = 블록 포인터(payload 가리킴) , HDPR(header) , FTRP(footer)

• BLKP(block pointer) , GET_SIZE(header 내용)

등등 그냥 위치에 있는 값들을 얻기 위해 편하게 사용할 수 있는 함수들이다.
위 내용이 이해가 안 된다면

• 해더가 몇 바이트 인지
• 페이로드의 시작 지점은 어디인지
• 이전/다음 페이지의 위치는 어떻게 파악하는지

등을 공부해보면 쉽게 이해가 갈 것이다.
페이징에 관한 개념이 익숙하지 않은 것이니 CSAPP 9장의 페이징에 관련된 내용들 중에서도
implicit free list의 각 부위별 크기에 대해서 생각하면 편하다.

mm_init

int mm_init(void)
{
    //mem_sbrk 는 리눅스 시스템에서 sbrk로 대체할 수 있다. mem_sbrk는 다양한 운영체제에서 사용한다.
    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)   //초기 메모리 블록을 요청하고 그결과를 heap_listp에 할당한다.
        return -1;                                          // 할당에 실패하면 (void *)-1를 반환하는데 반환값과 (void *)-1를 비교해서 할당실패이면 -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);
    find_nextp = heap_listp; // next_fit을 사용할 떄 필요한 변수

    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;
    return 0;
}

비어있는 메모리를 할당받는다.

제일 앞에 크기 0짜리 에필로그를 집어넣고(크기는 0이라도 4바이트 먹음[1칸])
그 뒤 프롤로그 넣어주고(프롤로그 header + footer 총 2칸 , 8바이트)
마지막으로 에필로그를 추가하고 끝낸다.(3*WIZE 부분)
next_fit 방식을 이용했기 때문에 find_nextp라는 함수를 이용해서 포인터 지정을 해준다.

if 구문은 데이터 할당이 잘못되었을때 -1을 리턴해준다.

extend_heap

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;

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));

    return coalesce(bp);
}

말 그대로 heap를 늘려주는거다.
size를 구한 다음 , 그 크기만큼(당연히 단위는 WSIZE라서 WIZE * N 크기가 나옴)
heap을 늘려주고

이후 에 필로그를 달아 준 다음

return coalesce(bp);를 통해 합칠 수 있는 가용리스트가 있는지 판별한다.

malloc

void *mm_malloc(size_t size)
{
    size_t asize;
    size_t extendsize;
    char *bp;

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

malloc을 할당해주는 함수이다.
많은 사람들이 asize 구하는 식에 대해서 궁금해 했다.

• asize = DSIZE * ((size + (DSIZE)+(DSIZE -1)) / DSIZE);
• print((a + 6)//7 * 7)
  이놈이 문제인데 생각보다 간단한 놈이다.

한줄로 말하면

6짜리를 할당해주고 싶은데 header + footer + payload + 규격 지키기
이거를 싹다 해줘야 되기 때문에 16을 할당해준다는거다.

왜 16이냐고?
기본적으로 header + footer가 8바이트를 잡아먹고
6만 할당해주면 규격이 깨지니까 8에 맞춰서 할당해준다는거다.
그러니까 8+8 = 16바이트 이다.

free

void mm_free(void *ptr)
{
    size_t size = GET_SIZE(HDRP(ptr));

    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    coalesce(ptr);
}

간단하다
header , footer 전부 가용으로 만들어준 후
coalesce 해서 가용 블럭을 합쳐준다.
끝

coalesce

뭔가 엄청 길어보이는데 똑같은 코드를 조건에 따라 4번 쓴거다.
어려운 부분은 너굴맨이 처리 했으니까 편하게 보면 된다.

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)
    {
        return bp;
    }

    else if (prev_alloc && !next_alloc)
    {
        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)
    {
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    else
    {
        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);
    }
    find_nextp = bp; // next_fit을 사용하기 위한 변수
    return bp;
}

엄청 길게 써놨는데 딱 2개만 보면 된다.

if (prev_alloc && next_alloc)
    {
        return bp;
    }

만약 이전/이후 블럭들이 가용이 아니다
-> 그냥 return 한다.

    else if (prev_alloc && !next_alloc) // ! _ , _ ! , _ _  중 하나
    {
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }

이전/이후 블럭들 중 가용블럭인놈 찾아서 그놈이랑 블럭을 이어준다.
이전/이후 모두 가용 블럭이면 둘다 이어준다.

이게 끝이다. 진짜 똑같은거 4번 적은거다

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

입력 값 만큼 늘리는거

fit

static void *find_fit(size_t asize){
    void *bp;
    bp = find_nextp;
    
    for(;GET_SIZE(HDRP(find_nextp)) > 0; find_nextp = NEXT_BLKP(find_nextp)){
        if(!GET_ALLOC(HDRP(find_nextp))&& (asize <= GET_SIZE(HDRP(find_nextp)))){
            return find_nextp;
        }
    }
    for(find_nextp = heap_listp; find_nextp != bp; find_nextp =NEXT_BLKP(find_nextp)){
        if (!GET_ALLOC(HDRP(find_nextp)) && (asize <= GET_SIZE(HDRP(find_nextp))))
        {
            return find_nextp;
        }
        
    }
    
    return NULL;
}

사실 find_fit 이라고 적어놨지만 이거 next_fit이다.
이전에 찾았던 포인터를 저장해 놓고, 그 포인터부터 에필로그 까지 탐색을 한 후,
값이 없으면 heap_listp 로 이동해서 다시 에필로그까지 탐색을 한다.
2번 탐색해도 없으면 그냥 안되는거니까 NULL을 출력해서 실패가 나오게 한다.

place

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

페이지를 할당하는 함수.
그냥 할당하면 된다

이제 정글 교육과정에 대한 빅데이터 학습을 끝냈다.
이번주도 최대한 빨리 끝낸다음 나에게 도움이 되는 공부를 하자.

정글 교육과정은 그게 아니라고?
오히려 개인공부를 더해서 훌륭한 신입이 된다면
정글 주최자 측도 만족하지 않을까?