malloc LAB #2 : Implicit Free List

2025.04.28 - [문제풀이] - MALLOC | FREE LIST 구현기 #1

MALLOC | FREE LIST 구현기 #1

우린 앞의 글 내용에서 정말 대략적인 각 Free List의 구현 방법을 살펴 보았다. 여기서는 Implicit Free List에 대한 내용을 살펴보겠다.

모든 글에 대해 구현 내용을 다루는 만큼 앞에서 자주 사용할 매크로에 대해 미리 작성하겠다.

/* Basic constants and macros */
#define WSIZE 4 /* 워드와 푸터의 사이즈, 바이트 단위 */
#define DSIZE 8 /* 더블 워드 사이즈 */
#define CHUNKSIZE (1<<12)

#define MAX(x, y) ((x) > (y) ? (x) : (y)) // 기본적인 MAX 리턴 함수

// Alloc 여부를 변동 시킬 수 있는 매크로이다.
#define PACK(size, alloc) ((size) | (alloc))

/* 주소 p에 Read/Write를 수행 하는 매크로이다. */
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int*)(p) = (val))

/* 주소 p에 대한 블럭의 정보를 얻을 수 있다. */
#define GET_SIZE(p) (GET(p) & ~0x7)
// ~0x7은 맨 우측의 3비트를 빼고 나머지 내용을 보겠다는 것.
#define GET_ALLOC(p) (GET(p) & 0x1)
// 0x1은 맨 우측의 1비트만 보겠다는 것.

/* 주소 bp는 Payload를 가리킨다. 해당 위치 시점에서 Header와 Footer를 접근하기 위한 매크로. */
#define HDRP(bp)  ((char *)(bp) - WSIZE)
#define FTRP(bp)  ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

/* 주소 bp 기준으로 다음 블럭, 이전 블럭에 접근하는데 도움이 되는 함수이다. */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

/* single word (4) or double word (8) alignment */
#define ALIGNMENT (WSIZE * 2) /* 기존엔 명시 8이었으나 WSIZE에 의존적으로 전환 */
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

Implicit Free List 만들기

앞의 매크로들을 전제하고, 우리는 우선 heap에 대한 기본적인 접근을 만들어야한다. 이를 위해 간단한 포인터 하나를 선언한다 :

void * heap_listp;

 

mm_init | 초기화 함수, 첫 실행 단 한 번만 실행된다.

# [조건] heap_listp에 공간 배정을 시도한다.
	# 성공하는 경우 아래 내용을 이어서 진행한다.
	# 실패하면 진행을 못하니 즉시 중단한다.
    
# heap_listp 첫 위치에 대해서는 Alignment Padding을 배치한다.
	# 아래에서 설명할 공간 단위는 = Word 한 개의 용량을 말한다. 여기서는 4바이트를 WSIZE로 치환하지만
    # 변동 여지 때문에 공간 단위라는 워딩을 사용하겠다.
# heap_listp + (1 * 공간 단위) 위치에서는 Prologue Header 배치.
# heap_listp + (2 * 공간 단위) 위치에서는 Prologue Footer 배치.
# heap_listp + (3 * 공간 단위) 위치에는 Epilogue Header 배치.

# heap_listp는 Prologue Footer에서 부터 시작해야 한다.

# 초기화 루틴에서 확장 시도를 한다.
	# 성공하는 경우 성공하는대로 끝낸다.
    # 실패하는 경우 진행 불가하니 즉시 중단한다.

---

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

    PUT(heap_listp, 0); // Alignment padding
    PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); // 프롤로그 Header
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); // 프롤로그 Footer
    PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); // 에필로그 Header
    heap_listp += (2 * WSIZE); 

    // 초기 초기화 루틴을 CHUNKSIZE / WSIZE 만큼 확장 시도를 한다.
    if(extend_heap(CHUNKSIZE/WSIZE) == NULL)
        return -1;
    return 0;
}

최적화 꼼수로 heap_listp를 prologue footer 다음에 놓는 것을 적용하여 heap_listp는 WSIZE * 2에 위치하고 있다.

 

mm_malloc | 실질적으로 이 함수에서는 공간을 정해주기만 한다. 실제 배치는 상세 함수에서 이루어진다.

# 이상한 크기의 배정 시도를 차단한다.

# 배정받고자 하는 사이즈가 배정 할 최소 기준 사이즈와 비교를 수행한다.
	# 최소 기준 보다 적은 배정량 일경우, 가장 최소의 배정 값을 배정한다.
    # 최소 기준 보다 큰 경우, 적합한 계산 식을 통해 기준 사이즈의 배수 단위로 배정이 이뤄지게끔 한다.
    
# 적절한 배치 공간을 탐색한다.
	# 공간 탐색 성공 시 즉시 배치 한다. 배치되면 함수를 종료한다.
    # 탐색에 실패 한 경우 힙 확장을 시도하기 위해 일단 진행한다.
    
# 힙 확장을 시도한다.
	# 힙 확장에 성공하면 즉시 배치한다. 배치되면 함수를 종료한다.
    # 실패한경우, 대참사난거니까 즉시 종료해야한다.

---

void *mm_malloc(size_t size)
{
    size_t asize;
    size_t extendSize;
    char *ptr;
    if (size == 0) 
    	return NULL;

    if (size <= DSIZE)
        asize = 2*DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE); 
   
    if ((ptr = find_fit(asize)) != NULL)
    {
        place(ptr, asize);
        return ptr;
    }

    extendSize = MAX(asize, CHUNKSIZE);
    if ((ptr = extend_heap(extendSize/WSIZE)) == NULL)
        return NULL;
    place(ptr, asize);
    return ptr;
}

 

place | 실제 alloc 값을 조정하여 malloc 종료 직전 진행 되는 함수이다.

# asize와 현재 쓸 공간을 가리키는 ptr에 대한 연산을 진행한다.
	# 조건은 : 차 연산을 했는데 헤더, 푸터, payload를 담을 수 있는 유의미한 공간이 나오는 경우
    # 그럼 우선 전체 공간에 대해 Alloc 옵션을 전환한다.
    	# 차 연산에 대한 내용에 대해 다시 한번 전환을 해서 해당 구역은 사용이 가능하도록 조정한다.
    # 하지만 차 연산 후 유의미한 공간이 나오지 않으면 그냥 기존 배정에 딸려 주듯 던져준다.

---

static void place(void *ptr, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(ptr));

    // 옵션으로 초과 부분을 분할하는 역할
    if((csize - asize) >= (2 *DSIZE))
    {
        PUT(HDRP(ptr), PACK(asize, 1));
        PUT(FTRP(ptr), PACK(asize, 1));

        ptr = NEXT_BLKP(ptr);
        PUT(HDRP(ptr), PACK(csize - asize, 0));
        PUT(FTRP(ptr), PACK(csize - asize, 0));
    } 
    else
    {
        PUT(HDRP(ptr), PACK(csize, 1));
        PUT(FTRP(ptr), PACK(csize, 1));
    }  
}

 

find_fit | First Fit 기준 작성. First Fit은 전체 공간을 탐색하며 적절한 공간을 찾는 즉시 반환 후 끝낸다.

# 블럭이 존재하는 해당 Pool에 대해 수행한다.
	# heap_listp 부터 NEXT_BLKP 단위로 블럭을 옮기면서, Size > 0 이 아니면 반복문을 중단.
    # 방문하는 모든 블럭에 대해, 목표 사이즈 만큼 배정 가능한지, 그리고 아직 배정이 안된건지를 체크한다.
    	# 두 경우 만족하는 경우, 해당 사이즈에 대한 주소를 반환한다.

# 반복문이 끝났는데도 코드가 끝나지 않았다면 찾지 못한 것이니 찾지 못했다는 내용으로 반환한다.

---

static void *find_fit(size_t asize)
{
    void *ptr ;
    for(ptr = heap_listp; GET_SIZE(HDRP(ptr)) > 0; ptr = NEXT_BLKP(ptr))
    {
        if(asize <= GET_SIZE(HDRP(ptr))  && GET_ALLOC(HDRP(ptr)) != 1)
            return ptr;
    }
    return NULL;
}

결국 이것은 묵시적 리스트라서 가능한 것.
내가 탐색하고자하는 모든 Pool에 Alloc 된 것과 안 된것에 대해 배치 차이를 두지 않으니 이런식의 단순 무식 검사가 가능하다.
그냥 Alloc 옆에 Alloc 일수도 있고 Not Alloc 일수도 있고.. 

 

extend_heap | 힙 확장을 시도하는 함수이다. 늘리고 난뒤, 물리적으로 붙어있다면 합병 시도하는 함수까지 호출한다.

# 확장 요청 할 사이즈를 정한다. 이는 Chunksize에 영향을 받는다.
# 정해진 사이즈만큼 확장을 요청한다.
	# 성공 시 다음 코드 진행한다.
    # 실패 시 즉시 중단한다.
    
# Header와 Footer를 배정되지 않은 공간 처리 후 Epilogue Header를 새로 배정한다.
# 합병 함수를 호출하여 후보정을 거친다.

---

static void *extend_heap(size_t words)
{
    char *ptr;
    size_t size;
    size = (words % 2) ? (words + 1) * WSIZE : words * (WSIZE);
    if ((long) (ptr = mem_sbrk(size)) == -1)
        return NULL;

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

    return coalence(ptr);
}

 

coalence | 경계 태그 연결을 사용하여, 상수 시간에 인접 가용 블록들과 병합을 수행하는 함수이다.

# 자기 자신 블럭 기준으로, 이전 블럭에 대한 배정 여부를 확인한다.
# 자기 자신 블럭 기준으로, 다음 블럭에 대한 배정 여부를 확인한다.
# 현재 자기 자신에 대한 블럭 크기를 저장해둔다.

# 조건문 : 이전 칸에 대한 배정 여부, 다음 칸에 대한 배정 여부를 확인한다.
	# 이전, 다음 둘 다 사용중인 경우 | Case 1
    	# 특별히 할게 없으니 자기 자신을 반환하고 끝낸다.
    # 이전 은 사용중이나, 다음 칸은 사용중이지 않은 경우 | Case 2
    	# 자기 자신과 다음 블럭을 합병한다.
        # 다음 블럭에 대한 사이즈까지 합산한다.
        	# 이 사이즈를 기반으로 Header, Footer에 대한 새로운 배정을 적용한다.
        # 여기까지 해야 블럭 합병이 끝난 것
    # 이전은 사용중이지 않고, 다음 칸 이 사용중인 경우 | Case 3
    	# 이전 블럭과 자기 자신을 합병한다.
        	# 주의. 합병이 끝나면 포인터는 이전 블럭쪽에 가까운 방향으로 가야한다. 
            	# payload의 시작점이 합친 뒤의 Header 바로 다음으로 가야하는 것이니 당연
            # 이전 블럭에 대한 사이즈까지 합산한다.
        		# 이 사이즈를 기반으로 Header, Footer에 대한 새로운 배정을 적용한다.
                # 그리고 포인터는 이전 블럭에 대한 포인터로 정정한다.
                # 여기까지 해야 블럭 합병이 끝난 것
    # 이전, 다음 둘 다 사용중이지 않은 경우 | Case 4
    	# 양쪽에 대한 사이즈를 더한다.
       		# 이 사이즈를 기반으로 Header, Footer에 대한 새로운 배정을 적용한다.
        # 포인터는 이전 블럭에 대한 포인터로 정정한다.
        # 여기까지 해야 블럭 합병 끝.
# 포인터 반환 후 함수 종료

---

static void* coalence(void *ptr)
{
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(ptr)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));
    size_t size = GET_SIZE(HDRP(ptr));

    if (prev_alloc && next_alloc)
        return ptr;
    else if (prev_alloc && !next_alloc)
    {
        size += GET_SIZE(HDRP(NEXT_BLKP(ptr)));
        PUT(HDRP(ptr), PACK(size, 0));
        PUT(FTRP(ptr), PACK(size, 0));
    }
    else if (!prev_alloc && next_alloc)
    {
        size += GET_SIZE(HDRP(PREV_BLKP(ptr)));
        PUT(FTRP(ptr), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
        ptr = PREV_BLKP(ptr);
    }
    else
    {
        size += GET_SIZE(HDRP(PREV_BLKP(ptr))) +
        GET_SIZE(FTRP(NEXT_BLKP(ptr)));

        PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(ptr)), PACK(size, 0));
        ptr = PREV_BLKP(ptr);
    }
    return ptr;
}

mm_free | 매개변수로 들어온 포인터가 가리키는 구역의 배정 여부를 해제한다.

# 매개변수로 들어온 포인터의 정보를 파악해야 한다. 해당 포인터가 가리키는 공간의 크기를 파악하낟.
	# 크기를 바탕으로 Header, Footer를 추적해서 Alloc 상태를 전환한다.
# 합병 함수 호출 후 종료

---

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

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

mm_realloc | 기존 할당 내용을 정정하는 함수이다. 결이 크게 다르진 않다!

# 이상한 입력을 차단한다.

# 새로운 공간에 대한 배정을 우선 진행한다.
	# 배정이 실패하면 즉시 중단한다.
    
# 배정할 크기를 구한다음, memcpy 실시
# 기존 공간은 할당을 해제한다.
# 끝!

---

void *mm_realloc(void *ptr, size_t size)
{
    if(ptr == NULL)
        return mm_malloc(size);

    if(size <= 0)
    {
        mm_free(ptr);
        return 0;
    }

    void *oldptr = ptr;
    void *newptr = mm_malloc(size);
   
    if (newptr == NULL)
      return NULL;
    
    size_t copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
    if (size < copySize)
      copySize = size;

    memcpy(newptr, oldptr, copySize); // 얘가 중요하다

    mm_free(oldptr);
    return newptr;
}