[시스템 프로그래밍] Malloc Lab Implicit (2)

 

 

 

6. coalesce() 함수 구현

 

 

사용하는 이유는 위에서 살펴봤고.. 바로 구현해보자.

 

 

 

 

 

 

1. 이전 블록과 다음 불록이 모두 할당 된 상태 -> 합칠 수 없으니 그대로 반환한다.

2. 다음 블록이 가용 상태 -> 다음 블록과 합치고 반환한다.

3. 이전 블록이 가용 상태 -> 이전 블록과 합치고 반환한다.

4. 이전과 다음 모두 가용 상태 -> 둘 모두 합치고 반환한다.

 

 

 

extend_heap 함수를 사용할 때 coalesce 함수를 호출하도록 설정했다.

 

다시 한 번 테스트 해 보자.

 

 

 

 

 

 

점수가 정말 낮지만 오류는 발생하지 않았다.

가용 블록을 합치지 않아 크기가 제대로 정렬되지 않았다고 생각한 게 맞았나보다.

 

이제 성능을 끌어올려보자.

 

 

7. place 함수 수정

 

 

place 함수로 블록을 할당할 때 할당할 크기보다 블록 사이즈가 큰 경우 나머지 블록은 가용 블록으로 쪼갤 수 있다.

 

이전에 작성한 함수는 그대로 놔 두기 때문에 영역이 심하게 낭비되니, place 함수를 수정해보자.

 

 

 

 

 

 

 

현재 블록 사이즈에서 asize(할당하는 크기)를 넣어도 크기가 2*DSIZE 보다 크면 다른 데이터를 넣을 수 있다.

 

이런 경우 헤더 위치에 asize만큼 넣어주고 상태도 변경시킨다.

다음 블록으로 이동해 나머지 블록은 모두 가용 블록으로 표시한다.

 

크기가 남지 않으면 이전에 작성한 로직대로 동작하도록 한다.

 

place 함수를 수정했으니 아마 성능이 좋아지지 않았을까?

테스트 해 보자.

 

 

 

 

 

이전에 비해 많이 향상됨을 확인할 수 있다.

 

 

 

8. free 함수 구현

 

 

좀 더 나은 성능을 위해 free 함수를 제대로 구현하자.

 

 

 

 

free 함수는 반환할 블록의 위치를 인자로 받고 해당 블록의 가용 상태로 바꾸는 역할을 한다.

 

가용 상태로 만들기 끝내지 말고, 전에 작성한 coalesce 함수를 호출해 블록을 합칠 수 있으면 합치는 작업까지 수행하자.

 

free 함수를 작성했으니 다시 테스트 해 보자.

 

 

 

 

 

 

성능이 좀 더 향상됐다.

수정을 거듭할수록 성능이 좋아지고 있다.

 

 

9. next fit 구현

 

 

next fit 방법은 할당할 블록을 찾을 때 가장 최근에 할당된 블록을 기준으로 탐색을 시작하는 방법이다.

 

 

 

 

 

구현도 간단한 편이다.

찾으면 바로 반환하고 찾지 못한 경우 처음부터 다시 탐색을 시작하는 방식으로 진행된다.

 

bp가 변할 때 last_bp 변수를 갱신하는 부분을 추가한 후 테스트 해 보자.

 

 

 

 

 

 

 

first fit 방식을 사용할 때 보다 속도는 훨씬 빨라졌지만 공간 활용도는 약간 떨어짐을 확인할 수 있다.

 

 

 

<전체 소스코드>

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

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

/* If you want debugging output, use the following macro.  When you hand
 * in, remove the #define DEBUG line. */
#define DEBUG
#ifdef DEBUG
# define dbg_printf(...) printf(__VA_ARGS__)
#else
# define dbg_printf(...)
#endif


/* do not change the following! */
#ifdef DRIVER
/* create aliases for driver tests */
#define malloc mm_malloc
#define free mm_free
#define realloc mm_realloc
#define calloc mm_calloc
#endif /* def DRIVER */

/* single word (4) or double word (8) alignment */

/* rounds up to the nearest multiple of ALIGNMENT */

/*
 * Initialize: return -1 on error, 0 on success.
 */

#define ALIGNMENT 8


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

#define MAX(x, y) ((x) > (y) ? (x) : (y)) 
#define MIN(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 GET8(p) (*(unsigned long *)(p))
#define PUT8(p, val) (*(unsigned long *)(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))  

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

static char* heap_listp = 0;
static char* last_bp;
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);


int mm_init(void) {
    
    if((heap_listp = mem_sbrk(4*WSIZE)) == (void*)-1) { // create heap
        return -1;
    }

    PUT(heap_listp, 0); // padding area
    PUT(heap_listp+(WSIZE), PACK(OVERHEAD, 1)); // prologue header area
    PUT(heap_listp+(DSIZE), PACK(OVERHEAD, 1)); // prologue footer area 
    PUT(heap_listp+(DSIZE + WSIZE), PACK(0, 1)); // epilogue header area
    heap_listp += DSIZE;

    if(extend_heap(CHUNKSIZE / WSIZE) == NULL) { // extends heap size
        return -1;
    }
    
    last_bp = heap_listp;
    return 0;
}

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

static void *coalesce(void *bp) {

    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // prev assigned block
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // next assigned block
    size_t size = GET_SIZE(HDRP(bp)); // get size

    if (prev_alloc && next_alloc) { // case 1. only current available
        last_bp = bp;
        return bp;
    } else if (prev_alloc && !next_alloc) { // case 2. next_alloc is available
        size += GET_SIZE(HDRP(NEXT_BLKP(bp))); 
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
        // need?
    } else if (!prev_alloc && next_alloc) { // case 3. prev_alloc is available
        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 { // case 4. both alloc is available
        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);
    }
    last_bp = bp;
    return bp;
}

/*
 * malloc
 */
void *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);
        last_bp = bp;
        return bp;
    }

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

    place(bp, asize);

    last_bp = bp;
    return bp;

}

static void *find_fit(size_t asize) {
    /* first fit */
    // void *bp;

    // for(bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
    //     if(!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
    //         return bp;
    //     }
    // }

    /* next fit */
    char* bp = last_bp;
    
    for(bp = NEXT_BLKP(bp); GET_SIZE(HDRP(bp)) != 0; bp = NEXT_BLKP(bp)) {
        if (GET_ALLOC(HDRP(bp)) == 0 && GET_SIZE(HDRP(bp)) >= asize) {
            last_bp = bp;
            return bp;
        }
    }

    bp = heap_listp;
    while(bp < last_bp) {
        bp = NEXT_BLKP(bp);

        if (GET_ALLOC(HDRP(bp)) == 0 && GET_SIZE(HDRP(bp)) >= asize) {
            last_bp = bp;
            return bp;
        }
    }
    return NULL;
}

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

/*
 * free
 */
void free (void *ptr) {

    if(!ptr) return;
    
    size_t size = GET_SIZE(HDRP(ptr));

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

    coalesce(ptr);
}

/*
 * realloc - you may want to look at mm-naive.c
 */
void *realloc(void *oldptr, size_t size) {
    
    if(size <= 0) {
        free(oldptr);
        return 0;
    }

    if(oldptr == NULL) {
        return malloc(size);
    }

    void *newp = malloc(size);
    if(newp == NULL) return 0;

    size_t oldsize = GET_SIZE(HDRP(oldptr));
    if(size < oldsize) oldsize = size;

    memcpy(newp, oldptr, oldsize);
    free(oldptr);

    return newp;
}

/*
 * calloc - you may want to look at mm-naive.c
 * This function is not tested by mdriver, but it is
 * needed to run the traces.
 */
void *calloc (size_t nmemb, size_t size) {
    return NULL;
}


/*
 * Return whether the pointer is in the heap.
 * May be useful for debugging.
 */
static int in_heap(const void *p) {
    return p < mem_heap_hi() && p >= mem_heap_lo();
}

/*
 * Return whether the pointer is aligned.
 * May be useful for debugging.
 */
static int aligned(const void *p) {
    return (size_t)ALIGN(p) == (size_t)p;
}

/*
 * mm_checkheap
 */
void mm_checkheap(int verbose) {
}