Memory allocation using implicit free block tracking and next-fit method

Memory allocation using implicit free block tracking and next-fit method

 

✏️Next fit 이란?

검색을 시작하는 위치를 이전에 할당한 메모리 블록의 다음 블록으로 설정해 검색 시간을 최적화 할 수 있다.

 

장점 : first fit 이후 block만 탐색하면 되니 탐색 범위가 줄어들어 first fit보다 성증이 더 좋을 가능성이 높다.

단점 : 탐색 범위가 너무 작아 제한된 경우, 이전 블록과 연결된 빈공간을 발견하지 못해 fragmentation(단편화) 문제가 발생할 확률이 높다. 즉, 최적의 메모리 사용이 아닐 수 있다.

 

next fit은 할당 요청이 빈벌할 경우 성능이 저하되는 문제가 있다.

---

2023.04.10 - [CS(ComputerScience)] - Memory malloc implicit

---

가장 마지막 탐색 위치

static char *last_fitp; // Next Fit 구현을 위해 last block point 만들어줌

first fit까지 탐색한 마지막 블록을 가리키는 pointer

 

coalescing

static void *coalesce(void *bp)
{
	...

    // Case 1
    if (prev_alloc && next_alloc) {
		...
    }

    // Case 2
    else if (prev_alloc && !next_alloc) {
		...
    }

    // Case 3
    else if(!prev_alloc && next_alloc) {
		...
    }

    // Case 4
    // else if(!prev_alloc && !next_alloc) {
    else {
		....
    }

    last_fitp = bp; // Next fit
    return bp;
}

가용블록들을 합쳐주고 마지막 탐색 포인트 반환

 

int mm_init(void)
{
	...
    
    last_fitp = heap_listp; // Next fit
    return 0;
}

last_fitp 초기화

 

void *mm_malloc(size_t size)
{
	...

    last_fitp = bp; // Next fit
    return bp; // 할당된 블록의 시작 주소 반환
}

last_fitp 업데이트

---

Next fit 함수

/* Next Fit */
static void *next_fit(size_t asize)
{
    // 이전에 할당한 블록의 다음 블록부터 탐색하기 시작. 따라서 first fit보다 빠름
    // 할당 요청이 빈버하게 발생하는 경우, 이전 할당한 블록 이후에 공간이 없을 경우,
    // 기능 저하 문제가 발생할 수 있음
    char *p = last_fitp; // last fit block point, 이전 탐색 끝난 위치

    // last_fitp (마지막으로 할당을 시도한 블록) 이후에 있는 블록들을 탐색합니다.
    while (GET_SIZE(HDRP(p)) != 0) // Epilogue block의 size가 0이니깐 0이 되면 탐색 종료.
    {
        p = (NEXT_BLKP(p)); // next_block 가리킴
        if (!GET_ALLOC(HDRP(p)) && (GET_SIZE(HDRP(p)) >= asize)) {
            last_fitp = p;
            // printf("next_fit: found a fit at %p\n", (void *)p);
            return p;
        }
        // p = (NEXT_BLKP(p)); // next_block 가리킴
    }

    p = heap_listp; // prologue block, heap의 처음
    // 힙의 처음부터 last_fitp까지의 블록을 다시 탐색합니다.
    // 이는 첫번째 while문에서 찾을 수 없는 블록을 찾기 위한 것.
    while (p < last_fitp)
    {
        p = NEXT_BLKP(p);

        if (!GET_ALLOC(HDRP(p)) && (GET_SIZE(HDRP(p)) >= asize)) {
            last_fitp = p;
            // printf("next_fit: found a fit at %p\n", (void *)p);
            return p;
        }
    }
    // printf("next_fit: no fit found\n");
    return NULL; // No fit found
}

첫번재 while문에서 이전 탐색 이후부터 끝까지 탐색하면서 할당 가능한 블록을 만나면, 바로 메모리 할당

만약 첫번째 while문에서 할당 가능한 블록을 찾지 못했을 경우, 두번째 while문에서 찾아줘야 한다.

 

즉, Next fit은 first fit 보다 탐색 범위가 적다.

 

---

📄 mm.c

/*
 * 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 "mm.h"
#include "memlib.h"

/*********************************************************
 * 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) */
    ""
};

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

/* Basic constants and macros */
#define WSIZE 4 /* Word and header/footer size(bytes) */
#define DSIZE 8 /* Double word size(bytes) */

/* Extend heap by this amount(bytes) sbrk() 함수기능 */
// 2의 12승, 4096byte 메모리 할당 효율성을 높이기 위한 정의
// 사용 가능한 block이 없을 경우 확장. 너무 작게 설정하면 자주 확장하므로 적절한 크기로 설정해줘야 함.
#define CHUNKSIZE (1<<12) 
#define MAX(x, y) ((x) > (y)? (x) : (y))

/* Paxk a size and allocated bit into a word */
// size는 블록의 크기 정보를 저장
// alloc은 블록의 할당 여부(0, 1) 나타냄
#define PACK(size, alloc) ((size) | (alloc)) // OR 연산자 이용해 블록의 헤더 값을 생성

/* Read and write a word at address p */
// header와 footer는 모두 word형식으로 저장ㄷ됨.
// 각 비트(bit)는 0 또는 1의 값을 가지는 bit의 모음
#define GET(p) (*(unsigned int *)(p)) // 포인터 p가 가리키는 4byte word(void point 형태)를 반환
#define PUT(p, val) (*(unsigned int*)(p) = (val)) // 포인터 p가 가리키는 word에 val값을 저장

/* Read the size and allocated fields from address p */
// ~0x7(111...11000) 마지막 3비트를 0으로 만들어줌.
// 마지막 3비트를 제외한 나머지 부분을 반환해 주소 'p'을 블록 크기를 추출
#define GET_SIZE(p) (GET(p) & ~0x7) // 상위 29bit에 블록 크기 반환
#define GET_ALLOC(p) (GET(p) & 0x1) // 하위 1bit에 할당 여부 반환(0 or 1)

/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp) ((char*)(bp) - WSIZE) // bp 포인터가 가르키는 블록의 header 포인터 반환
#define FTRP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // bp 포인터가 가르키는 블록의 footer 포인터 반환

/* Given block ptr bp, compute address of next and previous blocks */
// bp : 현재 블록을 가리키는 포인터
// bp 포인터가 가리키는 블록의 다음 블록 포인터 반환
#define NEXT_BLKP(bp) ((char*)(bp) + GET_SIZE(((char*)(bp) - WSIZE))) // 현재 블록 사이즈만큼 더해주고 word만큼 이동해(bp - WSIZE) header위치로 감.
// bp 포인터가 가리키는 블록의 이전 블록 포인터 반환
#define PREV_BLKP(bp) ((char*)(bp) - GET_SIZE(((char*)(bp) - DSIZE))) // 이전 블록의 fooder로 이동해(bp - DSIZE) 이전 블록 사이즈만큼 빼줌

/* Next Fit */
// #define FREE_LIST_NEXT(bp) (*(char **)(bp + WSIZE))
// #define SET_NEXT_FREE(bp, ptr) (*(void **)(bp + WSIZE) = ptr)
// #define SET_PREV_FREE(bp, ptr) (*(void **)(bp) = ptr)

/* 
 * mm_init - initialize the malloc package.
 */
static char *heap_listp; // 처음에 쓸 가용블록 heap을 만들어 줌
static char *last_fitp; // Next Fit 구현을 위해 last block point 만들어줌
static void *extend_heap(size_t words);
static void *coalesce(void *bp);

static void place(void *bp, size_t asize);
static void *next_fit(size_t asize);
void *mm_malloc(size_t size);
int mm_init(void);

static void *extend_heap(size_t words)
{
    // printf("extend heap\n");
    char *bp; // 현재 블록을 가리키는 포인터 생성
    size_t size; // 확장하고 싶은 word 크기

    /* Allocate an even number of words to maintain alignment */
    // 정렬을 위해 짝수 갯수의 words 할당.
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;

    /* 메모리 확장 불가능 예외처리 */
    if ((long)(bp = mem_sbrk(size)) == -1)
        return NULL;

    /* Initialize free block header/footer and the epilogue header */
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // epilogue header

    /* Coalesce if the previous block was free */
    // 이전 블록이 가용이면, 가용 메모리 늘리기
    return coalesce(bp);
}

static void *coalesce(void *bp)
{
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // 이전 블록 footer에 접근해 할당 여부 반환
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // 다음 블록 header에 접근해 할당 여부 반환
    size_t size = GET_SIZE(HDRP(bp)); // 현재 블록의 header에 접근해 size정보 반환

    // Case 1
    if (prev_alloc && next_alloc) {
        last_fitp = bp; //Next fit
        // 이전 블록과 다음 블록 모두 할당되어 있으면 현재 block point 반환
        return bp;
    }

    // Case 2
    else if (prev_alloc && !next_alloc) {
        // 이전 블록 할당, 다음 블록 free
        // 다음 블록 header에 접근

        size += GET_SIZE(HDRP(NEXT_BLKP(bp))); // 다음 블록 사이즈 만큼 size 더해줌
        // block point는 현재 그대로 유지지
        PUT(HDRP(bp), PACK(size, 0)); // 현재 블록의 header 정보 갱신
        PUT(FTRP(bp), PACK(size, 0)); // 현재 블록의 footer 정보 갱신
    }

    // Case 3
    else if(!prev_alloc && next_alloc) {
        // 이전 블록 free, 다음 블록 할당
        // 이전 블록 footer에 접근

        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        // block point를 이전 블록의 포인터 위치로 갱신
        PUT(FTRP(bp), PACK(size, 0)); // 현재 블록의 footer의 정보 갱신
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 블록의 header 정보 갱신
        bp = PREV_BLKP(bp); // block point를 이전 블록의 block point로 변경
    }

    // Case 4
    // else if(!prev_alloc && !next_alloc) {
    else {
        // 이전 블록 free, 다음 블록 free
        // 이전 블록 footer와 다음 블록 header에 접근

        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        // block point를 이전 블록의 포인터 위치로 갱신
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 블록의 header 정보 갱신
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0)); // 다음 블록의 fooder 정보 갱신
        bp = PREV_BLKP(bp); // block point를 이전 블록의 block point로 변경
    }

    last_fitp = bp; // Next fit
    return bp;
}

/* First Fit */
// static void *find_fit(size_t asize)
// {
//     char *p = heap_listp; // prologue block
//     while (GET_SIZE(HDRP(p)) != 0) // Epilogue block의 size가 0이니깐 0이 되면 탐색 종료.
//     {
//         if (!GET_ALLOC(HDRP(p)) && (GET_SIZE(HDRP(p)) >= asize)) {
//             // printf("find_fit: found a fit at address %p\n", p);
//             return p;
//         }
//         p = (NEXT_BLKP(p)); // next_block 가리킴
//     }
//     // printf("find_fit: no fit found\n");
//     return NULL; // No fit found
// }

/* Next Fit */
static void *next_fit(size_t asize)
{
    // 이전에 할당한 블록의 다음 블록부터 탐색하기 시작. 따라서 first fit보다 빠름
    // 할당 요청이 빈버하게 발생하는 경우, 이전 할당한 블록 이후에 공간이 없을 경우,
    // 기능 저하 문제가 발생할 수 있음
    char *p = last_fitp; // last fit block point, 이전 탐색 끝난 위치

    // last_fitp (마지막으로 할당을 시도한 블록) 이후에 있는 블록들을 탐색합니다.
    while (GET_SIZE(HDRP(p)) != 0) // Epilogue block의 size가 0이니깐 0이 되면 탐색 종료.
    {
        p = (NEXT_BLKP(p)); // next_block 가리킴
        if (!GET_ALLOC(HDRP(p)) && (GET_SIZE(HDRP(p)) >= asize)) {
            last_fitp = p;
            // printf("next_fit: found a fit at %p\n", (void *)p);
            return p;
        }
        // p = (NEXT_BLKP(p)); // next_block 가리킴
    }

    p = heap_listp; // prologue block, heap의 처음
    // 힙의 처음부터 last_fitp까지의 블록을 다시 탐색합니다.
    // 이는 첫번째 while문에서 찾을 수 없는 블록을 찾기 위한 것.
    while (p < last_fitp)
    {
        p = NEXT_BLKP(p);

        if (!GET_ALLOC(HDRP(p)) && (GET_SIZE(HDRP(p)) >= asize)) {
            last_fitp = p;
            // printf("next_fit: found a fit at %p\n", (void *)p);
            return p;
        }
    }
    // printf("next_fit: no fit found\n");
    return NULL; // No fit found
}

static void place(void *bp, size_t asize)
{
    // find_fit에서 이미 asize보다 큰 free block 찾았으므로
    // 나머지 부분이 있거나 없거나 두가지 케이스밖에 없음
    size_t old_size = GET_SIZE(HDRP(bp)); // header에 접근해 free_block 사이즈 반환
    size_t remaining = old_size - asize; // 할당 한뒤, 남겨지는 사이즈 splitting

    if (remaining >= (2*DSIZE)) {
        // splitting
        // printf("Splitting block with size %zu into blocks with sizes %zu and %zu\n", old_size, asize, remaining);
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));

        char *next_bp = NEXT_BLKP(bp); // free block splitting
        PUT(HDRP(next_bp), PACK(remaining, 0));
        PUT(FTRP(next_bp), PACK(remaining, 0));
    } else {
        // printf("Placing block with size %zu\n", old_size);
        PUT(HDRP(bp), PACK(old_size, 1));
        PUT(FTRP(bp), PACK(old_size, 1));
    }
}

int mm_init(void)
{
    /* Create the initial empty heap */
    if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
        return -1;

    // Alignment padding, 빈공간 정렬을 효율적으로 하기 위해(짝수되도록)
    PUT(heap_listp, 0); 
    // Prologue Block, 8의 배수 정렬 효율적 & splitting 쉽도록
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); // Prologue header
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); // Prologue footer
    // free block의 끝을 나타내는 역할, heap 확장하는 과정에서 사용.
    PUT(heap_listp + (3*WSIZE), PACK(0, 1)); // Epilogue header
    // prologue header와 prologue footer 사이의 첫 번째 블록을 가리킴
    // 메모리 할당 및 해제 시, 잘못된 방법으로 할당&해제 되는 것을 방지
    heap_listp += (2*WSIZE); 

    /* Extend the empty heap with a free block of CHUNKSIZE bytes */
    // heap 크기가 작아서, heap을 확장해야 하는 경우, 호출하는 함수.
    // heap 확장이 실패하면 -1 반환.
    if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
        return -1;
    last_fitp = heap_listp; // Next fit
    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; /* Adjusted block size */
    size_t extendsize; /* Amount to exted heap if no fit */
    char *bp;

    /* Ignore spurious requests 잘못된 요청 예외처리 */
    if (size == 0)
        return NULL;

    /* Adjust block size to include overhead and alignment reqs */
    if (size <= DSIZE)
        asize = 2*DSIZE; // 8의 배수로 조정
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);

    /* 1. first fit : Search the free list for a fit */
    // if ((bp = find_fit(asize)) != NULL) {
    //     place(bp, asize);
    //     return bp;
    // }

    /* 2. Next fit : Search the free list for a fit */
    if ((bp = next_fit(asize)) != NULL) {
        place(bp, asize);
        last_fitp = bp;
        return bp;
    }

    /* No fit found. Get more memory and place the block */
    // 넣어 줄 곳 없으면 heap 확장
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
        return NULL;
    place(bp, asize);

    last_fitp = bp; // Next fit
    return bp; // 할당된 블록의 시작 주소 반환
}

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *ptr)
{
    size_t size = GET_SIZE(HDRP(ptr)); // header 정보 이용해 현재 블록의 size 가져옴.

    // 빈공간으로 만들기
    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    coalesce(ptr);
}

void *mm_realloc(void *ptr, size_t size)
{
    void *old_bp = ptr;
    void *new_bp;
    size_t copySize;

    new_bp = mm_malloc(size);

    if (new_bp == NULL)
        return NULL;

    copySize = GET_SIZE(HDRP(old_bp)) - DSIZE; // size에서 header와 footer 제외한 면적

    // 새로 할당해주는 size가 old block pointer가 가리키는 곳의 사이즈보다 작으면
    // copySize 값을 업데이트!
    if (size < copySize)
        copySize = size;

    // old block pointer가 가리키는 곳에서 copySize만큼 가져와 
    // new block pointer가 가리키는 곳에 할당해준다.
    memcpy(new_bp, old_bp, copySize); 
    mm_free(old_bp);

    return new_bp;
}

 

mm_init, mm_malloc, coalesce 함수 모두 last_fitp을 현재 까지 탐색한 block을 가리키는 포인터값으로 설정해주고 block pointer를 반환해줘야 한다.

 

---

test 결과

next fit

 

random test case도 있기 때문에 점수가 항상 80점으로 나올 수 없다.

77~81점이 나온다.

---

처음에 참고한 코드를 돌리고 extended heap관련 오류가 발생!

printf 디버깅 방식으로 문제를 해결해왔었다.

 

그런데, 오류가 해결되고 나서도 점수가 자꾸 45점....

팀원에게 물어본 결과 printf를 주석처리해야 점수가 높다고 한다.

다시 돌려보니 77~81점!!!!

 

---

참고한 코드 : https://github.com/kjhchs2/malloc-lab/blob/master/mm.c