[WEEK06] Malloc Lab - Ⅲ

김상호·2022년 5월 11일
junglemalloclab개발일지정글
0

Development Log

목록 보기
22/45

Malloc Lab

Explicit Allocator

explicit 방법은 할당이 해제되어있는 블록들을 연결리스트 형태로 관리하여 모든 블록을 검사하지 않고, 할당이 해제된 블록들만 검사하는 implicit에서 개서된 방법이다. 하지만 implicit에 next-fit 방식의 성능과는 유사하다.

연결리스트에 블록을 추가하는 방식에 따라 블록의 물리적인 순서대로 연결리스트가 구성되는 ordered-list 방식과 최신에 해제된 블록을 연결리스트의 가장 앞에 추가하는 LIFO 방식으로 나뉜다. 성능적인 측면에서는 LIFO 방식이, 단편화를 방지하기 위해서는 ordered-list 방식이 좋다고 한다. 아래 과정은 LIFO 방식으로 설명한다. LIFO 방식은 물리적 순서와 연결리스트의 순서가 같음을 보장하지 않음에 주의해야 한다.

implicti 방식에서 달라진 점은 가장 처음 블록에 header와 footer 이외에 prev & next block pointer가 들어간다는 점이다. 해당 정보들을 이용하여 해제된 블록들을 연결리스트의 형태로 관리한다. 가장 앞 블록은 할당이 되어있는 블록으로 연결리스트에 들어가 있어 연결리스트의 끝점을 나타내는 역할을 수행한다.

Explicit Allocator 메모리 할당 과정

할당 되어있는 블록의 경우에는 연결리스트에서 관리하지 않기 때문에 prev, next 정보는 필요하지 않다.

  1. 연결리스트의 처음부터 순회하면서 블록의 사이즈를 확인한다. 연결리스트 내의 블록들은 마지막 블록을 제외하고는 이미 모두 할당이 해제된 블록이다.
  2. 블록의 사이즈가 본인보다 작다면 할당할 수 없는 공간이다. 해당 블록의 next 포인터로 이동하여 다음 블록을 검사한다.
  3. 블록의 사이즈가 본인보다 크거나 같다면 할당할 수 있는 공간이다.
    • 해당 블록을 연결리스트에서 제거한다.
    • 메모리가 할당될 수 있는 사이즈 공간을 초과한다면 블록을 분할하여 할당하고, 나머지 부분을 해제된 블록으로 바꿔준 후 연결리스트에 추가한다.
    • 메모리를 할당하고 해당 블록의 block pointer 주소를 반환한다.
  4. 할당할 수 있는 공간이 없어 연결리스트의 끝에 도달했다면 힙을 확장하여 할당한다.
  5. 추가적으로 3-2 과정에서 분할된 블록의 사이즈가 일정 수준보다 작은 사이즈가 만들어지게 되는 경우라면, 해당 블록을 전부 사용하여 외부 단편화를 방지한다.

Explicit Allocator 메모리 할당 해제과정

  1. 할당을 해제할 메모리 주소를 받는다. 해제할 메모리 주소의 앞뒤에 블록들을 확인한다.
  2. 할당을 해제할 블록의 앞 또는 뒤에 이미 할당이 해제된 블록이 존재한다면 해당 블록들을 연결리스트에서 제거한다.
  3. 이후 제거한 블록들과 합쳐 하나의 할당 해제상태 블록으로 만들고, 연결리스트의 가장 앞에 추가한다.

Explicit Allocator 기본 설계

함수에 필요한 것들이 대부분이 무언가를 넣는 것이기 때문에 매크로를 만들어 놓는 것이 좋다. 프로그램 전반적으로 계속 쓰일 것이기 때문이다. 따라서 맨 처음 변수 혹은 매크로를 설정해야 한다. Explicit은 Implicit와 전반적인 매크로가 비슷하다.

매크로 설정

  • 1개의 word 사이즈
  • 2배의 word 사이즈
  • heap을 한번 늘릴 때 필요한 사이즈
  • 주어진 값 중 어느것이 더 클지 정하는 MAX 함수
  • 블록 헤더에 사이즈와 할당 여부를 넣을 함수
  • 블록에 담긴 값을 읽어오는 함수
  • 특정 위치에 값을 넣는 함수
  • 해당 블록의 사이즈를 읽는 함수
  • 해당 블록의 할당 여부를 읽는 함수
  • 헤더 위치를 읽는 함수
  • 푸터 위치를 읽는 함수
  • 현재 블록의 다음 블록 위치로 이동하는 함수
  • 현재 블록의 이전 블록 위치로 이동하는 함수
  • 연결리스트에서 다음 블록 위치를 읽는 함수
  • 연결리스트에서 이전 블록 위치를 읽는 함수
  • 연결리스트에 다음 블록에 값을 넣는 함수
  • 연결리스트에 이전 블록에 값을 넣는 함수
  • 초기에 세팅할 힙
  • 연결리스트를 가리키는 포인터

위의 매크로들은 모두 반복적으로 쓰이는 변수나 함수를 일반화 시켜놓은 것이다. 코드는 다음과 같다.

#define WSIZE     4         
#define DSIZE     8         
#define CHUNKSIZE (1 << 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))) 

// 추가된 선언
/* Given ptr in free list, get next and previous ptr in the list */
#define GET_NEXT_PTR(bp) (*(char **)(bp + WSIZE))
#define GET_PREV_PTR(bp) (*(char **)(bp))

/* Puts pointers in the next and previous elements of free list */
#define SET_NEXT_PTR(bp, qp) (GET_NEXT_PTR(bp) = qp)
#define SET_PREV_PTR(bp, qp) (GET_PREV_PTR(bp) = qp)

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

// 추가된 함수
static void insert_in_free_list(void *bp);
static void remove_from_free_list(void *bp);
static char *free_list_start;

mm_init

기본적으로 mm_init은 할당기를 초기화하고 성공이면 0, 실패면 -1을 리턴한다. 초기화 하는 과정에서 가용 리스트의 prologue header, prologue footer, epilogue header, prev, next를 만드는 과정이 포함된다.

mm_init 함수에 필요한 것

  • 힙을 초기 사이즈만큼 세팅한다.
  • 가용 리스트에 패딩을 넣는다.
  • 가용 리스트에 prologue header를 넣는다
  • 가용 리스트에 prev를 넣는다.
  • 가용 리스트에 next를 넣는다.
  • 가용 리스트에 prologue footer를 넣는다.
  • 가용 리스트에 epilogue header를 넣는다.
  • 힙에 블록을 할당하기 위해 사이즈를 적당히 한 번 늘린다.
int mm_init(void) {
    if ((heap_listp = mem_sbrk(8*WSIZE)) == (void *)-1) { return -1; }
    PUT(heap_listp, 0); 
    PUT(heap_listp + (1*WSIZE), PACK(2*DSIZE, 1));  /* Prologue header */
    PUT(heap_listp + (2 * WSIZE), NULL);    /* prev free block pointer 는 null */
	PUT(heap_listp + (3 * WSIZE), NULL);    /* next free block pointer 는 null */
    PUT(heap_listp + (2*WSIZE), PACK(2*DSIZE, 1));  /* Prologue footer */            
    PUT(heap_listp + (3*WSIZE), PACK(0, 1));     /* Epilogue header */        
    free_list_start = heap_listp + (2*WSIZE); 
    if (extend_heap(CHUNKSIZE/WSIZE) == NULL) { return -1; }
    
    return 0;
}

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

extend_heap의 용도는 크게 다음과 같다.

  • 힙이 초기화 될때(init) 앞으로 블록을 넣기 위해 사이즈를 한번 늘리는 것
  • malloc을 통해 블록을 넣을 영역을 알아봤지만 적당한 맞춤 영역을 찾지 못했을 때 늘리는 것

코드를 보면

  • 먼저 인자를 words 크기로 받아서, size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; 8의 배수로 size값을 맞춰준다.
  • 메모리로부터 추가적인 힙공간을 요청(mem_sbrk(size))
  • 사이즈를 늘렸으니 그 자리에는 가용 블록이 들어가야 한다. 이유는 malloc을 통해 할당을 요청하면 데이터가 블록에 들어갈 수 있기 때문이다.
  • 새 가용 블록 header와 footer를 만든다.
  • 기존 가용리스트의 epilogue header 위치를 조정한다.

coalesce

static void *coalesce(void *bp) {
    //PREV_BLK(bp) == bp: epilogue block을 만났을 떄. Extend했을 때 epilogue를 만나는 유일한 경우
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))) || PREV_BLKP(bp) == bp; 
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); 
    size_t size = GET_SIZE(HDRP(bp)); 

    /* case 1 : 이전, 다음 블록 모두 할당되어있다면 */
    if (prev_alloc && next_alloc) {  
        insert_in_free_list(bp);
        return bp;
    /* case 2 : 이전 블록은 할당되어있고, 다음 블록은 가용상태라면 */    
    } else if (prev_alloc && !next_alloc) {
        size += GET_SIZE(HDRP(NEXT_BLKP(bp))); 
        remove_from_free_list(NEXT_BLKP(bp));
        PUT(HDRP(bp), PACK(size, 0));          
        PUT(FTRP(bp), PACK(size, 0));          
    /* case 3 : 이전 블록은 가용상태이고, 다음 블록이 할당상태라면 */
    } else if (!prev_alloc && next_alloc) {
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        remove_from_free_list(PREV_BLKP(bp));  
        PUT(FTRP(bp), PACK(size, 0));           
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    /* case 4 : 이전, 다음 블록 모두 가용 상태라면 */
    } else {
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        remove_from_free_list(NEXT_BLKP(bp));
        remove_from_free_list(PREV_BLKP(bp));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));                              
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));                              
        bp = PREV_BLKP(bp);                                                     
    }
    insert_in_free_list(bp);
    return bp; 
}

coalesce 함수에서는 현재 블록이 살필 수 있는 4가지 케이스를 다룬다.

  • 이전 블록과 다음 블록이 모두 할당되어 있는 경우 → 합칠 수 없다.
  • 이전 블록은 할당상태이지만, 다음 블록은 가용상태인 경우 → 다음 블록과 합칠 수 있다.
  • 이전 블록은 가용상태이고, 다음블록은 할당 상태인 경우 → 이전 블록과 합칠 수 있다.
  • 이전 블록과 다음 블록이 모두 가용상태인 경우 → 이전, 다음 블록 모두 합칠 수 있다.

mm_malloc

void *mm_malloc(size_t size) {
    size_t asize;       
    size_t extendsize;  
    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;
}

mm_malloc 에서는 얼마나 블록을 할당할지에 대한 사이즈를 인자로 받는다. 사이즈는 임의로 들어올 수 있기 때문에 정렬을 위해 함수 내부에서 사이즈를 조정해야 한다. 그리고 할당을 할 수 없을 때는 힙을 확장해 할당할 수 있는 자리를 마련해주어야 한다.

할당기가 요청한 크기를 조정하면 할당할 가용 블록이 가용 리스트에 있는지 탐색한다(find_fit). 맞는 블록을 찾으면 블록을 배치한다. 필요하면 기존 블록을 분할한다(place). 맞는 블록을 찾지 못하면 힙을 늘리고 다시 배치한다.

find_fit 

static void *find_fit(size_t asize) {
    /* First-fit search */
    void *bp;
    

    for (bp = free_list_start; !GET_ALLOC(HDRP(bp)); bp = GET_NEXT_PTR(bp)) {
        if (asize <= (size_t)GET_SIZE(HDRP(bp))) {
            // last_malloced_size = asize;
            return bp;
        }
    }
    return NULL;
}

find_fit 함수의 코드를 보면

  • 처음부터 검색하기 위해 bp 포인터 위치를 처음 init때 세팅했던 위치(free_list_start)로 잡는다.
  • GET_NEXT_PTR 함수를 이용해 다음 블록으로 이동한다.
  • 블록의 헤더를 검사한다. 해당 블록의 사이즈가 넣으려고 했던 사이즈보다 커야 한다.
  • 연결리스트는 가용 상태의 블록들의 리스트이다. 가용상태 블록 중 적절한 크기를 만나거나 리스트를 다 돌면 for문을 종료한다.
  • 만약 적절한 위치를 찾지 못하면 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));
        remove_from_free_list(bp);       
        bp = NEXT_BLKP(bp);                  
        PUT(HDRP(bp), PACK(csize-asize, 0)); 
        PUT(FTRP(bp), PACK(csize-asize, 0));
        coalesce(bp);
    } else {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
        remove_from_free_list(bp);
    }
}

place함수는 위치와 할당할 크기를 인자로 받는다.

우선 넣을 위치의 블록 사이즈를 계산하고 할당할 크기보다 블록 사이즈가 크면 나머지 부분은 가용블록으로 쪼갠다.(그대로 놔두면 영역 낭비가 된다.)

블록 사이즈가 크면, 블록을 할당하고(블록 헤더, 푸터 위치를 재조정) 나머지 부분을 쪼갠다. 그렇지 않으면 블록을 할당만 한다.

explicit는 할당을 하면 가용 상태 리스트에서 해당 블록을 제거한다(remove_from_free_list).

mm_free 

void mm_free(void *bp) {
    if (bp == NULL) { return; }
    size_t size = GET_SIZE(HDRP(bp));  
    PUT(HDRP(bp), PACK(size, 0));      
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp);  
}

free 함수는 반환할 블록의 위치를 인자로 받는다. 그리고 해당 블록의 가용 여부를 0으로 변경한다. 여기서 핵심은 블록을 가용 리스트에서 제거하는게 아니라 가용상태로 만들어버린다는 것이다.

블록을 반환한 후 가용 블럭이 생기면 항상 연결하는 함수를 실행해서 연결 가능한 블록을 챙겨야 한다.

realloc

void *mm_realloc(void *ptr, size_t size) {
    if ((int)size <= 0) {
        mm_free(ptr);
        return NULL;
    } else {
        size_t old_size = GET_SIZE(HDRP(ptr));
        size_t new_size = size + (2*WSIZE);

        if (new_size <= old_size) {
            return ptr;
        } else { 
            size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));
            size_t csize;

            if (!next_alloc && ((csize = old_size + GET_SIZE(HDRP(NEXT_BLKP(ptr))))) >= new_size) {
                remove_from_free_list(NEXT_BLKP(ptr));
                PUT(HDRP(ptr), PACK(csize, 1));
                PUT(FTRP(ptr), PACK(csize, 1));
                return ptr;
            } else {
                void *new_ptr = mm_malloc(new_size);
                place(new_ptr, new_size);
                memcpy(new_ptr, ptr, new_size);
                mm_free(ptr);
                return new_ptr;
            }
        }
    }
}

realloc 에서는 크기를 조정할 블록의 위치와 요청 사이즈를 인자로 받는다. 그후 malloc(size)을 통해 요청 사이즈만큼 블록을 할당한다.

여기서 핵심은 이미 할당된 블록의 사이즈를 직접 건드리는게 아니라, 임시로 요청 사이즈만큼의 블록을 만들고 현재의 블록을 반환하는 것이다. 그러면 사이즈 변경한 효과가 나기 때문이다. 또한 블록 내 데이터 또한 똑같이 옮겨야 하니 C라이브러리에 있는 memcpy함수를 활용한다. 그리고 기존 블록을 반환한다.

insert_in_free_list

static void insert_in_free_list(void *bp) {
    SET_NEXT_PTR(bp, free_list_start);
    SET_PREV_PTR(free_list_start, bp);
    SET_PREV_PTR(bp, NULL);
    free_list_start = bp;
}

insert_in_free_list에서는 블록의 위치를 인자로 받는다.

여기서 핵심은 연결리스트에 새로 추가되는 블록이기 때문에 이전 블록의 위치를 저장하고 있는 free_list_start을 통해 서로 가르킬 수 있게 값을 넣어준다. 연결리스트에 젤 앞은 가르킬 블록이 없기 때문에 NULL값을 넣어준다. 마지막으로 free_list_start을 bp의 값으로 최신화 해준다.

remove_from_free_list

static void remove_from_free_list(void *bp) {
    // 다음 블록이 있다면
    if (GET_PREV_PTR(bp)) {
        // 다음 블록의 주소에, 이전 블록의 주소를 넣는다.
        SET_NEXT_PTR(GET_PREV_PTR(bp), GET_NEXT_PTR(bp));
    // 다음 블록이 없다면, 즉 자신이 젤 앞 블록이라면
    } else {
        // 이전 노드를 젤 앞 블록으로 만들어준다.
        free_list_start = GET_NEXT_PTR(bp);
    }
    SET_PREV_PTR(GET_NEXT_PTR(bp), GET_PREV_PTR(bp));
}

remove_from_free_list에서는 제거할 블록의 위치를 인자로 받는다.

여기서 핵심은 연결리스트에서 제거하는 블록이기 때문에 블록의 앞, 뒤를 다 확인해야 한다. 만약 제거할 블록의 다음 블록이 있다면, 다음 블록의 주소에 이전 블록의 주소를 넣는다. 그런데 제거할 블록의 다음 블록이 없다면, 즉 제거할 블록이 젤 앞 블록이라면, 이전 노드를 젤 앞 블록으로 만들어준다.

Malloc Lap 구현 Github 링크
Malloc Lap

profile
김상호
: )
이전 포스트

[WEEK06] Malloc Lab - Ⅱ

다음 포스트

[WEEK07] Proxy - Ⅰ

0개의 댓글