Krafton_jungle 5기 6주차 WIL - Implicit free list

Implicit free list

 

묵시적 가용 리스트의 구현을 위해서는 다음과 같은 메크로가 필요하다.

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

 

 

묵시적 가용 리스트

할당기에서 사용하는 자료 구조로 묵시적 가용 리스트의 경우 하나의 거대한 동적 할당 영역에서 8byte의 배수 단위로 구성된 블록을 잘라가며 데이터를 할당한다. 가용 리스트의 특징은 1word size의 padding과 2개의 프롤로그 헤더, 마지막으로 1개의 에필로그 헤더로 전체 힙이 구성되어 있다. 최초 초기화 시 다음과같이 설정해주고 그 사이에 payload를 지니고 있는 블록을 끼워 맞추는 식으로 데이터를 할당해나간다. 그러다 처음 할당한 영역을 다 사용하거나, 더 큰 용량의 메모리를 요구하는 경우, brk 포인터를 청크 사이즈만큼 내려주어 추가적으로 메모리를 할당한다. 그 과정은 아래 코드와 같다.

void mem_init(void)
{
    /* allocate the storage we will use to model the available VM */
    if ((mem_start_brk = (char *)malloc(MAX_HEAP)) == NULL) {
	fprintf(stderr, "mem_init_vm: malloc error\n");
	exit(1);
    }

    mem_max_addr = mem_start_brk + MAX_HEAP;  /* max legal heap address */
    mem_brk = mem_start_brk;                  /* heap is empty initially */
}


void *mem_sbrk(int incr) 
{
    char *old_brk = mem_brk;

    if ( (incr < 0) || ((mem_brk + incr) > mem_max_addr)) {
	errno = ENOMEM;
	fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
	return (void *)-1;
    }
    mem_brk += incr;
    return (void *)old_brk;
}

동적 메모리를 할당하고, 요청시 brk 포인터를 사전에 정의해둔 만큼 추가해주는 코드

/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{   
    if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *) -1) 
        return -1;
    // 공갈워드
    PUT(heap_listp, 0);
    // 프롤로그 헤더
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1));
    // 프롤로그 헤더2 - 탐색 일관성 유지용
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1));
    // 에필로그 헤더
    PUT(heap_listp + (3*WSIZE), PACK(0, 1));
    // 탐색 시작점 설정
    heap_listp += (2*WSIZE);

    // next_fit을 위한 포인터 설정
    next_listp = heap_listp;

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

프롤로그 헤더와 에필로그 헤더를 설정해주는 코드.

 

동적 메모리 할당, 해제

이렇게 초기화가 완료된 리스트엔 8byte의 배수로 구성된 블록을 할당하고, 해제해줄 수 있다. 그 과정은 아래 코드와 같다.

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

        // next_fix을 위한 설정
        next_listp = bp;

        return bp;
    }
	
    // 만약 탐색을 마쳤는데 메모리를 할당할 수 있는 영역을 찾지 못한 경우
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
        return NULL;
    place(bp, asize);

    // next_fix을 위한 설정
    next_listp = bp;

    return bp;
}

메모리의 할당

 

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

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

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) {         // case1

        // next_fix을 위한 설정
        next_listp = bp;

        return bp;
    }

    else if (prev_alloc && !next_alloc) {   // case2
        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) {   // case3
        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 {                                  // case4
        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);
    }

    // next_fix을 위한 설정
    next_listp = bp;

    return bp;
}

단편화를 해결하기 위해 앞뒤 블록의 가용 유무를 확인하고, 같이 해제해주는 코드

 

void *mm_realloc(void *ptr, size_t size) {
    if (ptr == NULL) {
        return mm_malloc(size);
    }
    if (size == 0) {
        mm_free(ptr);
        return NULL;
    }
    size_t new_size = size + DSIZE;
    void *oldptr = ptr;
    void *newptr;
    size_t original_size = GET_SIZE(HDRP(oldptr));
    // 만약 즉시 할당 가능하면 pointer return
    if (new_size <= original_size) {
        return oldptr;
    } else {
        // 다음 블록 사이즈 확인
        size_t next_size = original_size + GET_SIZE(HDRP(NEXT_BLKP(oldptr)));
        // 다음 블록이 allocated 되어있지 않고 size의 합이 할당 가능한 영역이라면
        if (!GET_ALLOC(HDRP(NEXT_BLKP(oldptr))) && (new_size <= next_size)) {
            // allocated
            PUT(HDRP(oldptr), PACK(next_size, 1));
            PUT(FTRP(oldptr), PACK(next_size, 1));
            // 왜 place를 하면 안될까
            // place(oldptr, new_size);
            next_listp = oldptr;
            return oldptr;
        } else {
            // 만약 기존 데이터에 할당이 불가능하다면
            newptr = mm_malloc(new_size);
            if (newptr == NULL) {
                return NULL;
            }
            memmove(newptr, oldptr, new_size);
            next_listp = newptr;
            mm_free(oldptr);
            oldptr = NULL;
            return newptr;
        }
    }
}

 

realloc같은 경우는 가장 크게 애를 먹었던 부분인데, 데이터를 할당하기 전에 가용 블록의 사이즈를 나눠주려고 했는데 빈번하게 실패했다.

결국 인터넷에서 정글 선배님들의 코드를 보고 해결했음. 우선 명시적 가용 리스트를 구현하고 난  뒤 한번 더 최적화를 진행할 예정이다.

 

 

// FIRST_FIT
static void *find_fit(size_t asize) {
    void *bp;
    // 에필로그 헤더는 size가 0임으로 해당 조건에 걸림
    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;
        }
    }
    return NULL;
}


// BEST_FIT
static void *find_fit(size_t asize) {
    void *bp;
    void *best_p = NULL;
    size_t min_size = SIZE_MAX;
    // 에필로그 헤더는 size가 0임으로 해당 조건에 걸림
    for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))) && (min_size > GET_SIZE(HDRP(bp)))) {
            best_p = bp;
        }
    }
    if (best_p != NULL) {
        return best_p;
    } else {
        return NULL;
    }
}


// NEXT_FIT
static void *find_fit(size_t asize) {

    void *bp;
    void *old_ptr = next_listp;

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

    for (bp = heap_listp; bp < old_ptr; bp = NEXT_BLKP(bp)) {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            next_listp = NEXT_BLKP(bp);
            return bp;
        }
    }
    return NULL;
}

위 코드는 탐색 알고리즘이였는데 속도는 next_fit, first_fit, best_fit 순으로 빨랐다.

 

 

 

전체코드

/*
 * mm-naive.c - The fastest, least memory-efficient malloc package.
 * 
 * In this naive approach, a block is allocated by simply incrementing
 * the brk pointer.  A block is pure payload. There are no headers or
 * footers.  Blocks are never coalesced or reused. Realloc is
 * implemented directly using mm_malloc and mm_free.
 *
 * NOTE TO STUDENTS: Replace this header comment with your own header
 * comment that gives a high level description of your solution.
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include <stdint.h>

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

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

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name */
    "ateam",
    /* First member's full name */
    "Harry Bovik",
    /* First member's email address */
    "bovik@cs.cmu.edu",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""
};

/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{   
    if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *) -1) 
        return -1;
    // 공갈워드
    PUT(heap_listp, 0);
    // 프롤로그 헤더
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1));
    // 프롤로그 헤더2 - 탐색 일관성 유지용
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1));
    // 에필로그 헤더
    PUT(heap_listp + (3*WSIZE), PACK(0, 1));
    // 탐색 시작점 설정
    heap_listp += (2*WSIZE);

    // next_fit을 위한 포인터 설정
    next_listp = heap_listp;

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

/* 
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
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);

        // next_fix을 위한 설정
        next_listp = bp;

        return bp;
    }

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

    // next_fix을 위한 설정
    next_listp = bp;

    return bp;
}

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *bp)
{
    size_t size = GET_SIZE(HDRP(bp));

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


void *mm_realloc(void *ptr, size_t size) {
    if (ptr == NULL) {
        return mm_malloc(size);
    }
    if (size == 0) {
        mm_free(ptr);
        return NULL;
    }
    size_t new_size = size + DSIZE;
    void *oldptr = ptr;
    void *newptr;
    size_t original_size = GET_SIZE(HDRP(oldptr));
    // 만약 즉시 할당 가능하면 pointer return
    if (new_size <= original_size) {
        return oldptr;
    } else {
        // 다음 블록 사이즈 확인
        size_t next_size = original_size + GET_SIZE(HDRP(NEXT_BLKP(oldptr)));
        // 다음 블록이 allocated 되어있지 않고 size의 합이 할당 가능한 영역이라면
        if (!GET_ALLOC(HDRP(NEXT_BLKP(oldptr))) && (new_size <= next_size)) {
            // allocated
            PUT(HDRP(oldptr), PACK(next_size, 1));
            PUT(FTRP(oldptr), PACK(next_size, 1));
            // 왜 place를 하면 안될까
            // place(oldptr, new_size);
            next_listp = oldptr;
            return oldptr;
        } else {
            // 만약 기존 데이터에 할당이 불가능하다면
            newptr = mm_malloc(new_size);
            if (newptr == NULL) {
                return NULL;
            }
            memmove(newptr, oldptr, new_size);
            next_listp = newptr;
            mm_free(oldptr);
            oldptr = NULL;
            return newptr;
        }
    }
}


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) {         // case1

        // next_fix을 위한 설정
        next_listp = bp;

        return bp;
    }

    else if (prev_alloc && !next_alloc) {   // case2
        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) {   // case3
        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 {                                  // case4
        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);
    }

    // next_fix을 위한 설정
    next_listp = bp;

    return bp;
}

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

    // words가 홀수면 패딩 추가해주기
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    // brk 포인터 를 뒤로 밀어준다
    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);

}

// FIRST_FIT
static void *find_fit(size_t asize) {
    void *bp;
    // 에필로그 헤더는 size가 0임으로 해당 조건에 걸림
    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;
        }
    }
    return NULL;
}


// BEST_FIT
static void *find_fit(size_t asize) {
    void *bp;
    void *best_p = NULL;
    size_t min_size = SIZE_MAX;
    // 에필로그 헤더는 size가 0임으로 해당 조건에 걸림
    for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))) && (min_size > GET_SIZE(HDRP(bp)))) {
            best_p = bp;
        }
    }
    if (best_p != NULL) {
        return best_p;
    } else {
        return NULL;
    }
}


// NEXT_FIT
static void *find_fit(size_t asize) {

    void *bp;
    void *old_ptr = next_listp;

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

    for (bp = heap_listp; bp < old_ptr; bp = NEXT_BLKP(bp)) {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            next_listp = NEXT_BLKP(bp);
            return bp;
        }
    }
    return NULL;
}


static void place(void* bp, size_t allocated_size) {
    size_t curr_size = GET_SIZE(HDRP(bp));
    // Case 1. 남는 부분이 최소 블록 크기(16 bytes) 이상일 때 -> 블록 분할
    if ((curr_size - allocated_size) >= (2 * DSIZE))            // 남는 블록이 최소 블록 크기(16 bytes) 이상일 때
    {
        PUT(HDRP(bp), PACK(allocated_size, 1));                 // Header -> size와 allocated(1) 설정
        PUT(FTRP(bp), PACK(allocated_size, 1));                 // Footer -> size와 allocated(1) 설정
        bp = NEXT_BLKP(bp);                                     // bp 위치를 다음 블록 위치로 갱신
        // 블록 분할
        PUT(HDRP(bp), PACK(curr_size - allocated_size, 0));     // 남은 공간의 Header -> 남는 size와 free(0) 설정
        PUT(FTRP(bp), PACK(curr_size - allocated_size, 0));     // 남은 공간의 Footer -> 남는 size와 free(0) 설정
    }
    // Case 2. 남는 부분이 최소 블록 크기(16 bytes) 미만일 때 -> 블록 분할 필요 X
    else
    {
        PUT(HDRP(bp), PACK(curr_size, 1));                      // 분할할 필요가 없다면, 그냥 할당
        PUT(FTRP(bp), PACK(curr_size, 1));
    }
}