[WEEK6]탐험준비 - Malloc Lab

이번 주 과제는 C에서 메모리 동적할당 할 때 사용하는 malloc을 직접 구현해 보는 것이다!

http://csapp.cs.cmu.edu/3e/malloclab.pdf

위 링크는 카네기멜론 CSAPP malloc랩 구현 과제 설명 pdf이다. 파일에 나온 지시사항을 따라서 implicit, explicit, seglist 까지 구현해 보면 된다. 나는 explicit 까지 구현을 완료했고 테스트 케이스는 전부다 통과하지 못했다 ㅜㅜ

나름대로 추상화를 한다고 노트에 끄적이면서 열심히 했지만 엄청 구현도 복잡하고 에러투성이의 안좋은 추상화였다. 나중에 피어리뷰할때 답을 구현해 놓은 것을 보니 훨씬 더 간단한 추상화 방법으로 구현되어 있었다. 

이번 과제를 통해 배운 내용들을 아래에 정리해 보자.

주요개념들

동적할당이란?

프로그램이 런타임중에 메모리를 할당하는 것을 말하며, 메모리 동적할당은 힙영영에서 일어난다. C에서는 malloc 이라는 함수를 통해 프로그래머가 메모리 동적할당을 할 수 있으며 프로그램이 종료되기 전에 무조건 free로 메모리 해제를 해줘야 한다. 아니면 메모리 누수가 발생한다.

할당 방식의 두 종류(Types of allocators)

• Explicit allocator(한글로 뭐지..? 외재적 할당기??)
  어플리케이션에서 할당과 해제를 둘 다 맡는다. ex) malloc, free in C
• Implicit allocator(암시적 할당기??)
  어플리케이션에서 할당하지만 해제는 하지 않는다. ex) garbage collection in Java, ML, and Lisp

과제 채점 척도

1. Throughput (스루풋, 처리율)

주어진 시간안에 몇 개의 malloc call에 대한 몇 개의 free call을 수행할 수 있는가?

2. Memory Utilization

Aggregated payload, 즉 malloc으로 만들어진 할당된 바이트수의 최대치를 현재 힙 사이즈로 나눈 값을 확인한다. Memory Utilization은 메모리 단편화에 의해 안좋게 나올 수 있다.

메모리 단편화

1. Internal fregmentation (내부적 단편화)

내부적 단편화는 실제로 할당된 블록보다 할당해서 쓰는 메모리 즉 payload가 작을 때 생긴다. align을 맞추기 위한 padding 때문에 생기거나 heap 데이터구조를 유지하는데에 드는 오버헤드 때문에 발생한다. (오버헤드가 뭘 뜻하는 지 잘 모르겠다.. 찾아보자)

2. External fregmentation (외부적 단편화)

아래 그림에 나와있는 것처럼 원하는 크기만큼 이어진 메모리공간이 힙메모리 상에 없을 때 외부적 단편화가 발생한 것이다. 이는 할당과 해제가 반복되면서 메모리 중간중간에 free block이 생기지만 해당 크기보다 작거나 같은 메모리만 할당할 수 있기 때문이다.

 

Implicit List

Implicit list는 할당된 블록과 free 블록을 모두 link하는 리스트로 관리한다.

블록의 1 word는 해당 블록의 사이즈와 할당되있는지 해제되어 있는지를 확인하는 bit로 이루어져 있다.

list에서 free block을 찾는 방법은 크게 3가지 방법이 있다.

• First fit
  리스트의 처음부터 찾아나가는 방식
• Next fit
  이전의 탐색이 끝난 위치부터 찾아나가는 방식
• Best fit
  원하는 크기와 가장 맞는 free block을 찾는 방식. 느리지만 utilization에 이점이 있다.

Q. 교과서에있는 그림에는 왜 비트플래그가 3bit나 있을까? 해답은 820쪽 맨 마지막 문단에 있는 것 같다. 이전 블록의 할당/가용 비트를 저장한다면 할당된 블록들의 풋터가 필요없어진다. 이 부분을 개선한다면 제출 후 점수가 조금더 올라가지 않을까?

Explicit List

Explicit list는 free된 블록만 리스트로 관리한다.

위 그림과 같이 이전과 다음 freeblock을 가리키는 head와 tail이 1 word씩 붙어있다.

Explicit policy에는 두 가지 방식이 있는데 나는 LIFO 방식을 사용했다. 주소 순서대로 관리하는 Address-ordered policy도 있는데 둘의 장단점을 알려면..  교재 ppt에 studies suggest 라고 되어있는걸로보아 논문을 찾아봐야 한다. 우선은 다음에 찾는것으로 생각하자.

구현부

1. Place 함수

찾는 heap 영역이 남으면 남은 부분을 free 영역으로 재정의 하는 함수이다.

// 찾는 heap 영역이 남으면 남은 부분을 free 영역으로 재정의 하는 함수
static void place(void *bp, size_t asize)
{
    // printf("place call\n");
    size_t csize = GET_SIZE(HDRP(bp));
        
    if ((csize - asize) >= (2 * DSIZE))
    {
        void** bp_aft = (unsigned int**)bp;
        void** bp_bf = (unsigned int**)((char *)bp + WSIZE);
 
        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));

        //** free 영역에 next, prev 설정
        //** 중간 블록인 경우
        if (*(unsigned int *)bp_aft != 0 && *(unsigned int *)bp_bf != 0)
        {   
            // printf("****************place 1 case\n");

            *(unsigned int **)bp = *(unsigned int **)bp_aft;
            **(unsigned int***)(bp_bf) = (unsigned int*)bp;
            *(unsigned int **)((char *)bp + WSIZE) = *(unsigned int **)bp_bf;
            *(unsigned int **)((char *)*(unsigned int ***)bp_aft + WSIZE) = (unsigned int*)bp;
        }
        //** 마지막 블록인 경우
        else if (*(unsigned int *)bp_bf != 0)
        {
            // printf("****************place 2 case\n");
            *(unsigned int **)((char *)bp + WSIZE) = *(unsigned int **)bp_bf;
            **(unsigned int***)(bp_bf) = (unsigned int*)bp;
            *(unsigned int**)(bp) = NULL;
        }
        //** 루트가 가리키는 블록인 경우
        else if (*(unsigned int *)bp_aft != 0)
        {
            root_freep = (unsigned int*)bp;
            *(unsigned int **)((char *)*(unsigned int ***)bp_aft + WSIZE) = (unsigned int*)bp;
            *(unsigned int **)bp = *(unsigned int **)bp_aft;
            *(unsigned int**)((char*)bp + WSIZE) = NULL;
            
        }
        //** 루트가 가리키면서 마지막 블록인 경우
        else
        {
            // printf("****************place 4 case\n");
            root_freep = (unsigned int**)bp;
            *(unsigned int**)bp = NULL;
            *(unsigned int**)((char *)bp + WSIZE) = NULL;
        }
    }
    else
    {   
        // printf("****************place 5 case\n");
        void* bp_aft = bp;
        void* bp_bf = (char *)bp + WSIZE;
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
        if((*(unsigned int*)bp_aft) != 0 && (*(unsigned int*)((char *)bp_aft + WSIZE)) != 0)
        {
            // printf("****************place 5-1 case\n");
            **(unsigned int***)(bp_bf) = *(unsigned int**)bp_aft;
            *(unsigned int **)((char *)*(unsigned int ***)bp_aft + WSIZE) = *(unsigned int**)bp_bf;
        }
        //** 마지막 블록인 경우
        else if (*(unsigned int *)bp_bf != 0)
        {
            // printf("****************place 5-2 case\n");
            **(unsigned int***)(bp_bf) = NULL;
        }
        //** 루트가 가리키는 블록인 경우
        else if (*(unsigned int *)bp_aft != 0)
        {
            // printf("****************place 5-3 case\n");
            root_freep = *(unsigned int **)bp_aft;
            *(unsigned int**)((char*)*(unsigned int ***)bp_aft + WSIZE) = NULL;
        }
        //** 루트가 가리키면서 마지막 블록인 경우
        else
        {
            // printf("****************place 5-4 case\n");
            root_freep = NULL;
        }
           
    }
}

ㄷesadfasdf21. Place 함수

2. Coalesce 함수

free함수 호출 시 해당 free 블록에 인접한 가용블록이 있을 경우 합쳐주는 함수이다. 아래 추상화된 그림을 참고하여 구현하였다.

//** free함수 호출 시 해당 freed 블록에 인접한 가용블록이 있을 경우 합쳐주는 함수.
static void *coalesce(void *bp, void ***mybp)
{
    // printf("coalesce call\n");
    
    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)
    {
        // printf("****************coalesce 1 case\n");
        void *bp_aft = bp;
        void *bp_bf = (char *)bp + WSIZE;

        // ** prev, next freep 추가
        // root가 어딘가를 가리키고 있을 때
        if (bp != root_freep && root_freep != NULL)
        {
            // printf("****************coalesce 1-1 case\n");
            *(unsigned int**)((char *)bp + WSIZE) = NULL;
            *(unsigned int**)((char *)root_freep + WSIZE) = (unsigned int*)bp;
            *(unsigned int**)bp = (unsigned int*)root_freep;
            root_freep = (unsigned int*)bp;
        }
        // bp == root_freep 인 경우는 초기화 경우, NULL인 경우는 모든 블록을 다 할당해서 가용공간이 없을 때 
        else
        {
            // printf("****************coalesce 1-2 case\n");
            root_freep = (unsigned int*)bp;
            *(unsigned int**)((char *)root_freep) = NULL;
            *(unsigned int**)((char *)bp + WSIZE) = NULL;
        }
        return bp;
    } 
    // 다음 블록만 free인 경우
    else if (prev_alloc && !next_alloc)
    {
        // printf("****************coalesce 2 case\n");
        // 해당블록크기 + 다음블록크기 사이즈로 헤더와 풋터를 수정
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));

        //** 헤더 수정하기전에 미리 저장
        void *bp_aft = NEXT_BLKP(bp);
        void *bp_bf = (char *)NEXT_BLKP(bp) + WSIZE;

        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
        
        //** 다음 free 블록이 중간 블록인 경우
        if ((*(unsigned int*)bp_aft) != 0 && (*(unsigned int*)((char *)bp_aft + WSIZE)) != 0)
        {
            // printf("****************coalesce 2-1 case\n");
            //루트가 가리키던 블록을 가리키도록 변경
            *(unsigned int**)bp = (unsigned int*)root_freep;
            *(unsigned int**)((char *)bp + WSIZE) = NULL;
            *(unsigned int**)((char *)root_freep + WSIZE) =(unsigned int*)bp;

            // cross
            *(unsigned int **)((char *)*(unsigned int ***)bp_aft + WSIZE) = *(unsigned int**)bp_bf;
            **(unsigned int ***)bp_bf = *(unsigned int**)bp_aft;
            root_freep = (unsigned int*)bp;

        }
        //** 다음 free 블록이 루트가 가리키는 블록인 경우
        else if ((*(unsigned int*)bp_aft) != 0)
        {
            // printf("****************coalesce 2-2 case\n");
            //루트가 가리키던 블록이 가리키던 블록을 가리키도록 변경
            *(unsigned int**)bp = *(unsigned int**)root_freep;
            // **(unsigned int***)bp_bf = NULL;
            //루트가 가리키는 블록이 가리키는 블록의 이전 블록포인터를 현재 블록으로 변경
            *(unsigned int**)((char*)*(unsigned int***)(root_freep) + WSIZE) = (unsigned int*)bp;
            *(unsigned int**)((char *)bp + WSIZE) = NULL;
            root_freep = (unsigned int*)bp;
        }
        //** 다음 free 블록이 마지막 블록인 경우
        else if ((*(unsigned int*)((char *)bp_aft + WSIZE)) != 0)
        {
            // printf("****************coalesce 2-3 case\n");
            *(unsigned int**)bp = *(unsigned int**)root_freep;
            *(unsigned int**)((char *)bp + WSIZE) = NULL;
            // 마지막 블록 이전 블록이 가리키는 블록ptr를 NULL로 설정
            **(unsigned int**)((char *)bp_aft + WSIZE) = NULL;
            *(unsigned int**)((char *)root_freep + WSIZE) = (unsigned int*)bp;
            root_freep = (unsigned int*)bp;
        }
        //** 다음 블록이 유일 블록인 경우
        else
        {
            // printf("****************coalesce 2-4 case\n");
            root_freep = (unsigned int**)bp;
            *(unsigned int**)root_freep = NULL;
            *(unsigned int**)((char*)root_freep + WSIZE) = NULL;
        }
    }
    // 이전 블록만 free인 경우
    else if (!prev_alloc && next_alloc)
    {
        // printf("****************coalesce 3 case\n");
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        void ** bbp = bp;
        // 블록 포인터를 이전 블록위치로 옮겨야 함
        bp = PREV_BLKP(bp);
        void **bp_aft = bp;
        void **bp_bf = (char *)bp + WSIZE;
        //** 이전 free 블록이 중간 블록인 경우
        if ((*(unsigned int*)bp) != 0 && (*(unsigned int*)((char *)bp + WSIZE)) != 0)
        {

            **(unsigned int***)bp_bf = *(unsigned int**)bp; 
            *(unsigned int **)((char*)*(unsigned int***)bp_aft + WSIZE) = *(unsigned int**)bp_bf;
            
            *(unsigned int**)bp = (unsigned int*)root_freep;
            *(unsigned int**)((char *)bp + WSIZE) = NULL;
            *(unsigned int**)((char *)root_freep + WSIZE) = (unsigned int*)bp;

            root_freep = (unsigned int*)bp;
        }
        //** 이전 free 블록이 루트가 가리키는 블록인 경우
        else if ((*(unsigned int*)bp) != 0)
        {
            //** 할거 없음
            // printf("****************coalesce 3-2 case\n");
        }
        //** 이전 free 블록이 마지막 블록인 경우
        else if ((*(unsigned int*)((char *)bp + WSIZE)) != 0)
        {
            // printf("****************coalesce 3-3 case\n");
            // bef ptr이 가리키는 블록이 가리키는 aft ptr을 NULL로 수정
            **(unsigned int***)((char *)bp + WSIZE) = NULL;
            // root ptr이 가리키는 블록이 가리키는 aft ptr을 bp로 수정
            *(unsigned int**)((char *)root_freep + WSIZE) = (unsigned int*)bp;
            *(unsigned int**)((char *)bp + WSIZE) = NULL;
            *(unsigned int**)bp = (unsigned int*)root_freep;
            root_freep = (unsigned int*)bp;
        }
        //** 이전 블록이 유일 블록인 경우
        else
        {
            //** 할거 없음
            // printf("****************coalesce 3-4 case\n");
        }
    }
    // 이전 블록, 다음 블록 둘 다 free인 경우
    else
    {
        // printf("****************coalesce 4 case\n");
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        void ** bp1 = bp;
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        void **bpp = (NEXT_BLKP(bp));
        void **bpp_aft = bpp; 
        void **bpp_bf = (char *)bpp + WSIZE;
        bp = PREV_BLKP(bp);
        void **bp_aft = bp;
        void **bp_bf = (char *)bp + WSIZE;
        //** 왼쪽 중간노드 + 오른쪽 중간노드
        if ((*(unsigned int*)bp) != 0 && (*(unsigned int*)((char *)bp + WSIZE)) != 0 && (*(unsigned int*)bpp) != 0 && (*(unsigned int*)((char *)bpp + WSIZE)) != 0)
        {
            // printf("****************coalesce 4 - 1 case\n");
            fflush(stdout); 
            //** 왼쪽 노드 전후노드 cross
            **(unsigned int***)bp_bf = *(unsigned int**)bp_aft; 
            *(unsigned int **)((char*)*(unsigned int***)bp_aft + WSIZE) = *(unsigned int**)bp_bf;
            //** 오른쪽 노드 전후노드 cross
            **(unsigned int***)bpp_bf = *(unsigned int**)bpp_aft; 
            *(unsigned int **)((char*)*(unsigned int***)bpp_aft + WSIZE) = *(unsigned int**)bpp_bf;

            *(unsigned int**)((char *)bp + WSIZE) = NULL;
            *(unsigned int**)bp = (unsigned int*)root_freep;
            *(unsigned int**)((char *)root_freep + WSIZE) = (unsigned int*)bp;
            root_freep = (unsigned int*)bp;
        }
        //** 왼쪽 루트노드 + 오른쪽 마지막 노드
        else if((*(unsigned int*)bp) != 0 && (*(unsigned int*)((char *)bp + WSIZE)) == 0 && (*(unsigned int*)bpp) == 0 && (*(unsigned int*)((char *)bpp + WSIZE)) != 0)
        {
            // printf("****************coalesce 4 - 2 case\n");
            *(unsigned int**)root_freep = NULL;
        }
        //** 왼쪽 마지막 노드 + 오른쪽 루트 노드
        else if((*(unsigned int*)bp) == 0 && (*(unsigned int*)((char *)bp + WSIZE)) != 0 && (*(unsigned int*)bpp) != 0 && (*(unsigned int*)((char *)bpp + WSIZE)) == 0)
        {
            // printf("****************coalesce 4 - 3 case\n");
            root_freep = (unsigned int*)bp;
            *(unsigned int**)((char *)root_freep + WSIZE) = NULL;
        }
        //** 왼쪽 중간 노드 + 오른쪽 루트 노드
        else if((*(unsigned int*)bp) != 0 && (*(unsigned int*)((char *)bp + WSIZE)) != 0 && (*(unsigned int*)bpp) != 0 && (*(unsigned int*)((char *)bpp + WSIZE)) == 0)
        { 
        	// printf("****************coalesce 4 - 4 case\n");
            //** 왼쪽 노드 전후노드 cross
            //이전 노드가 다음 노드를 가리키도록
            **(unsigned int***)bp_bf = *(unsigned int**)bp_aft; 
            //다음 노드가 이전 노드를 가리키도록
            *(unsigned int **)((char*)(*(unsigned int***)bp_aft) + WSIZE) = *(unsigned int**)bp_bf;
            *(unsigned int**)((char *)bp + WSIZE) = NULL;
            //** 루트가 가리키던 노드가 가리키는 이전 노드가 bp여야됨
            *(unsigned int **)((char*)(*(unsigned int***)root_freep) + WSIZE) = (unsigned int*)bp;
            //루트가 가리키던 블록이 가리키던 블록을 가리키도록 변경
            //만약 왼쪽 중간노드가 우선순위 2번째라면 다음 노드를 가리키도록 수정해야함
            if (*(unsigned int**)bp == *(unsigned int**)root_freep)
            {
                // printf("case1");
                *(unsigned int**)bp = **(unsigned int***)bp;
                *(unsigned int **)((char*)*(unsigned int***)bp_aft + WSIZE) = (unsigned int*)bp;
            }
            else
            {
                // printf("case2");
                *(unsigned int**)bp = *(unsigned int**)root_freep;
            }
            root_freep = (unsigned int*)bp;
        }
        //** 왼쪽 루트 노드 + 오른쪽 중간 노드
        else if((*(unsigned int*)bp) != 0 && (*(unsigned int*)((char *)bp + WSIZE)) == 0 && (*(unsigned int*)bpp) != 0 && (*(unsigned int*)((char *)bpp + WSIZE)) != 0)
        {
            // printf("****************coalesce 4 - 5 case\n");
            //** 오른쪽 노드 전후노드 cross
            **(unsigned int**)bpp_bf = *(unsigned int**)bpp_aft; 
            *(unsigned int *)((char*)*(unsigned int**)bpp_aft + WSIZE) = *(unsigned int**)bpp_bf;
        }
        //** 왼쪽 중간 노드 + 오른쪽 마지막 노드
        else if((*(unsigned int*)bp) != 0 && (*(unsigned int*)((char *)bp + WSIZE)) != 0 && (*(unsigned int*)bpp) == 0 && (*(unsigned int*)((char *)bpp + WSIZE)) != 0)
        {
            // printf("****************coalesce 4 - 6 case\n");
            //** 왼쪽 노드 전후노드 cross
            **(unsigned int***)bp_bf = *(unsigned int**)bp_aft; 
            *(unsigned int **)((char*)*(unsigned int***)bp_aft + WSIZE) = *(unsigned int**)bp_bf;
            // bef ptr이 가리키는 블록이 가리키는 aft ptr을 NULL로 수정
            **(unsigned int***)((char *)bp + WSIZE) = NULL;
            *(unsigned int **)(bp_bf) = NULL;
            //루트가 가리키던 블록이 가리키던 블록을 가리키도록 변경
            *(unsigned int**)bp = *(unsigned int**)root_freep;
            *(unsigned int**)((char *)root_freep + WSIZE) = (unsigned int*)bp;
            root_freep = (unsigned int*)bp;
        }
        //** 왼쪽 마지막 노드 + 오른쪽 중간 노드
        else if((*(unsigned int*)bp) == 0 && (*(unsigned int*)((char *)bp + WSIZE)) != 0 && (*(unsigned int*)bpp) != 0 && (*(unsigned int*)((char *)bpp + WSIZE)) != 0)
        {
            // printf("****************coalesce 4 - 7 case\n");
            //** 오른쪽 노드 전후노드 cross
            **(unsigned int***)bpp_bf = *(unsigned int**)bpp_aft; 
            *(unsigned int **)((char*)*(unsigned int***)bpp_aft + WSIZE) = *(unsigned int**)bpp_bf;
            **(unsigned int***)((char *)bp + WSIZE) = NULL;
            *(unsigned int **)(bp_bf) = NULL;
            //루트가 가리키던 블록이 가리키던 블록을 가리키도록 변경
            *(unsigned int**)bp = *(unsigned int**)root_freep;
            *(unsigned int**)((char *)root_freep + WSIZE) = (unsigned int*)bp;
            root_freep = (unsigned int*)bp;
        }   
    }
    show_freelist();
    return bp;
}

 

참고자료: CSAPP chapter 9, 카네기멜론 해당 챕터 강의 

추가로 공부할 관련 내용: 가비지 컬렉터