implicit free list
implicit free list는 동적 메모리 할당기를 구현하는 방법 중 하나다.
동적 메모리 할당기는 힙 영역을 관리한다.
실은 할당기는 두 개의 유형이 있는데 우리는 이 중 묵시적 할당기 implicit allocator를 구현하려 한다.
명시적 할당기 explicit allocator는 가비지 컬렉터로 알려져있다.
동적으로 메모리를 할당해주는 할당기는 힙 영역에서 블록 단위로 메모리를 관리한다. 그리고 사용자의 요청이 있을 때마다 비어있는 공간 free block을 할당해준다.
🙋🏻♀️ 그렇다면 블록은 어떤 구조로 관리해야 할까?
정답은 하나가 아니다. 이번에는 가장 간단한 묵시적 가용 리스트 implicit free list의 구조를 보고 구현한다.(다음 포스팅은 더 효율적인 방법, 명시적 가용 리스트를 구현한다.)
묵시적 가용 리스트는 모든 블록을 메모리에 쭉 나열하고 필요할 때 앞에서부터 차례차례 검사하여 가용 블록을 찾아 할당하는 방식이다.
이 방법은 1. 단순하다는 장점이 있다. 하지만, 2. 힙에 있는 전체 블록을 탐색해야 한다는 단점이 있다.
자, 일단 묵시적 가용 리스트 implicit free list 가 어찌 생겨먹었는 지 보자.
블록이 할당 되었는지 아니면 가용 블록인지 구분해야 한다. 그렇게 하기 위해서 하나의 블록에는 헤더가 필요할 것이다.
한 블록은 1워드의 헤더, 데이터(payload), 추가적인 패딩으로 구성된다. 헤더에는 블록 크기와 블록이 할당되었는지 여부를 나타내는 가용 상태를 인코딩한다.
위의 블록 포맷으로 힙의 연속된 할당 및 가용 블록의 배열을 다음과 같이 나타낼 수 있다.
n/m의 표시에서 n은 크기, m은 할당 여부이다. m이 0이라면 free block(할당 되지 않음)을 의미하고 1이라면 allocated block(할당됨)을 의미한다.
- 첫 1칸 : 정렬 패딩(unused)
CPU가 바로 payload에 접근하기 위해서 정렬 단위를 맞춰주는 역할을 하는 패딩이다. - 다음 2칸 : 힙 영역의 시작을 알리는 프롤로그 블록이다.(헤더, 푸터로 구성된다)
- 그 이후 : 실제 메모리 블록이다.
헤더, 푸터는 각각 1칸을 차지하고 페이로드는 설정된 정렬 단위로 배치된다.(8B 정렬을 가정한다면, 위의 사진처럼 헤더&푸터 8B + 페이로드 8B로 최소 16B의 공간이어야 메모리를 사용할 수 있다.) - 마지막 1칸 : 힙 영역의 종료를 알리는 에필로그 블록이다.
간결하지만 생각보다 많은 개념이 엮여서 탄생한 구조이다.
이제 할당기 중, 가장 간결한 implicit free list + first fit 방법으로 구현을 시작해보자!
CSAPP 책에는 위의 방식이 서술되어있다. 있는 그대로 따라 쳤다.
66점이 나왔다.
단순히 따라치니까 이게 오타인지, 논리적 오류인지 알 수가 없었다.
처음에 학생 정보 입력란에 , 하나 안 붙여서 init 함수부터도 실행이 안 되었다. 코드를 완벽하게 이해한 후에 작성한 게 아니라서 어디가 문제인지 알 수 없어 어렵게 발견했다🥲
그 과정, 그리고 그 이후에 한줄 한줄 코드를 뜯어보면서 이해했다.
define 매크로
-
ALIGNMENT : 정렬 단위
-
ALIGN : 정렬 단위에 맞춰 사이즈를 조정해주는 매크로, 인자로 size를 받는다.
-
WSIZE : 1word 크기
-
DSIZE : 2word 크기
-
CHUNKSIZE : 힙 영역 확장시, 최소 요청 단위의 메모리 덩어리 크기이다. 보통 페이지 크기와 일치시켜 4KB로 지정한다.
-
PACK : 사이즈만큼의 가장 마지막 비트에 할당 여부를 저장한다.
-
PUT : 인자로 입력받은 포인터에 val의 값으로 변경한다.
-
HDRP : 해당 블록 페이로드 시작점의 위치에서 블록의 헤더 주소를 반환한다.
1 word 만큼 이전 블록으로 이동하면 현재 블록의 header를 만난다. -
FTRP : 위와 같이 블록의 푸터 주소를 반환한다.
header에서 현재 블록의 size를 얻어 이동한다. 그러면 다음 블록의 페이로드에 위치하는데 다음 블록의 헤더로 이동하고(1word), 현재 블록의 푸터로 이동(1word)한다. -
NEXTBLKP : 다음 블록의 페이로드 시작 주소
1 word 전의 현재 블록의 헤더에서 현재 블록의 size 정보를 얻고, size만큼 이동한다. 현재 페이로드 시작 주소에서 size만큼 이동하면 다음 블록의 페이로드 시작 주소가 된다. -
PREVBLKP : 이전 블록의 페이로드 시작 주소
2 word 만큼 이전 블록으로 이동하면 현재 블록의 header를 지나 이전 블록의 footer를 만난다. 그 footer에서 size 정보를 얻어 이동시킨다.
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8 // 블록 크기로 8바이트의 배수로 맞추기 위함
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7) // 임의의 사이즈를 8의 배수로 만들어주는 함수
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
// 들어가기
#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) // 1 word 패딩 이후
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // 2 word header 이후
// 현재 payload의 포인터에서 1 word 전 : 현재 block 헤더 / 헤더에서 해당 block 사이즈를 얻어옴
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
// 현재 payload의 포인터에서 2 word 전 : 이전 block 푸터 / 이전 block 사이즈를 얻어옴
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
coalesce
/*
* coalesce
* 블록 bp가 해제(free)된 뒤에,
* 이전 블록과 다음 블록의 상태를 보고 인접한 빈 블록들과 병합(merge)하는 역할
*
* 경계 태그 연결을 사용해서 상수 시간에 인접 가용 블록들과 통합한다.
*/
static void *coalesce(void *bp)
{
if (bp == NULL)
{
return NULL;
}
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // bp 바로 이전 블록의 payload 시작 포인터 의 푸터 의 할당 비트
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // bp 바로 다음 블록의 payload 시작 포인터 의 푸터 의 할당 비트
size_t size = GET_SIZE(HDRP(bp));
// 이전, 다음 블록 모두 할당
if (prev_alloc && next_alloc)
{
return bp;
}
// 다음 블록 가용 상태
else if (prev_alloc && !next_alloc)
{
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0)); // 사이즈, 할당 여부
PUT(FTRP(bp), PACK(size, 0)); // 이미 업데이트된 header를 참조하여 새로운 footer주소에 도착
}
// 이전 블록 가용 상태
else if (!prev_alloc && next_alloc)
{
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0)); // size 변경
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 블록의 header 주소를 현재 블록의 header 주소로 변경
bp = PREV_BLKP(bp);
}
// 이전 블록, 다음 블록 가용 상태
else
{
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 블록의 header 주소로 업데이트
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0)); // 다음 블록의 footer 주소로 업데이트
bp = PREV_BLKP(bp);
}
return bp;
}extend_heap
static void *extend_heap(size_t words)
{
char *bp; // 반환된 새 블록의 payload 시작 주소를 가리킬 포인터
size_t size;
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; // WSIZE를 곱하여 결국 8의 배수가 되도록 보장함
if ((long)(bp = mem_sbrk(size)) == -1) // 힙 확장 + 확장 전 포인터 bp에 저장
{
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);
}find_fit
void *find_fit(size_t asize)
{
void *bp;
// first fit
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;
}place
void place(void *bp, size_t asize)
{
size_t csize = GET_SIZE(HDRP(bp)); // csize: free block 크기
if ((csize - asize) >= (2 * DSIZE))
{
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
// 나머지는 free block으로 분할
bp = NEXT_BLKP(bp); // 나중에 free block 합침(지연 연결)
PUT(HDRP(bp), PACK(csize - asize, 0));
PUT(FTRP(bp), PACK(csize - asize, 0));
}
else
{
// 잔여 block이 넉넉치 않고 fit함
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}mm_init
int mm_init(void)
{
/* 1) 힙 영역의 기본 구조를 위한 4 워드(4*WSIZE 바이트) 확보 */
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
{
return -1;
}
/* 2) Alignment padding (정렬 패딩) */
PUT(heap_listp, 0);
/* 3) Prologue header: 크기 DSIZE(=8바이트), 할당(1) */
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));
/* 4) Prologue footer: 크기 DSIZE(=8바이트), 할당(1) */
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));
/* 5) Epilogue header: 크기 0, 할당(1) → 힙 끝 표시 */
PUT(heap_listp + (3 * WSIZE), PACK(0, 1));
/* 6) heap_listp를 첫 번째 유효 블록의 payload 시작점으로 조정 */
heap_listp += (2 * WSIZE);
/* 7) CHUNKSIZE 바이트(보통 4096B 등)만큼 빈 블록 생성 */
if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
{
return -1;
}
return 0;
}mm_malloc
void *mm_malloc(size_t size)
{
char *bp;
size_t asize;
size_t extendsize;
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_free
void mm_free(void *ptr)
{
size_t size = GET_SIZE(HDRP(ptr));
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
coalesce(ptr);
}mm_realloc
void *mm_realloc(void *ptr, size_t size)
{
void *oldptr = ptr;
void *newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}전체 코드
/*
* 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 */
"hyeona",
/* First member's full name */
"Seol Hyeona",
/* First member's email address */
"shappy0209@naver.com",
/* 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 // 블록 크기로 8바이트의 배수로 맞추기 위함
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7) // 임의의 사이즈를 8의 배수로 만들어주는 함수
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
// 들어가기
#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) // 1 word 패딩 이후
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // 2 word header 이후
// 현재 payload의 포인터에서 1 word 전 : 현재 block 헤더 / 헤더에서 해당 block 사이즈를 얻어옴
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
// 현재 payload의 포인터에서 2 word 전 : 이전 block 푸터 / 이전 block 사이즈를 얻어옴
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
// heap_listp 정의
static void *heap_listp;
/*
* coalesce
* : 반환된 free block을 앞, 뒤 free block과 병합하는 함수
*
* 블록 bp가 해제(free)된 뒤에,
* 이전 블록과 다음 블록의 상태를 보고 인접한 빈 블록들과 병합(merge)한다.
*
* 경계 태그 연결을 사용해서 상수 시간에 인접 가용 블록들과 통합한다.
*/
static void *coalesce(void *bp)
{
if (bp == NULL)
{
return NULL;
}
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // bp 바로 이전 블록의 payload 시작 포인터 의 푸터 의 할당 비트
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // bp 바로 다음 블록의 payload 시작 포인터 의 푸터 의 할당 비트
size_t size = GET_SIZE(HDRP(bp));
// 이전, 다음 블록 모두 할당
if (prev_alloc && next_alloc)
{
return bp;
}
// 다음 블록 가용 상태
else if (prev_alloc && !next_alloc)
{
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0)); // 사이즈, 할당 여부
PUT(FTRP(bp), PACK(size, 0)); // 이미 업데이트된 header를 참조하여 새로운 footer주소에 도착
}
// 이전 블록 가용 상태
else if (!prev_alloc && next_alloc)
{
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0)); // size 변경
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 블록의 header 주소를 현재 블록의 header 주소로 변경
bp = PREV_BLKP(bp);
}
// 이전 블록, 다음 블록 가용 상태
else
{
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 블록의 header 주소로 업데이트
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0)); // 다음 블록의 footer 주소로 업데이트
bp = PREV_BLKP(bp);
}
return bp;
}
/*
* extend_heap
* : mm_malloc에서 적당한 free block을 찾지 못한 경우 heap을 확장하는 함수
*
* 힙을 지정된 크기만큼 늘리고,
* 그 새 영역을 하나의 빈(free) 블록으로 초기화한 뒤,
* 인접한 빈 블록들과 병합(coalesce)해준다.
*/
static void *extend_heap(size_t words)
{
char *bp; // 반환된 새 블록의 payload 시작 주소를 가리킬 포인터
size_t size;
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; // WSIZE를 곱하여 결국 8의 배수가 되도록 보장함
if ((long)(bp = mem_sbrk(size)) == -1) // 힙 확장 + 확장 전 포인터 bp에 저장
{
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);
}
/*
* find_fit 함수
* : 요청한 크기의 free block이 있는 지 확인하는 함수
*
* size에 맞는 free block이 있다면 포인터를 반환한다.
*/
void *find_fit(size_t asize)
{
void *bp;
// first fit
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;
}
/*
* place 함수
* : free block을 할당하여 초기화하는 함수
*
* 헤더와 푸터를 세팅한다.
*/
void place(void *bp, size_t asize)
{
size_t csize = GET_SIZE(HDRP(bp)); // csize: free block 크기
if ((csize - asize) >= (2 * DSIZE)) // 남는 블록이 재사용 가능한 최소 크기보다 크다면
{
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
// 나머지는 free block으로 분할
bp = NEXT_BLKP(bp); // 나중에 free block 합침(지연 연결)
PUT(HDRP(bp), PACK(csize - asize, 0));
PUT(FTRP(bp), PACK(csize - asize, 0));
}
else
{
// 잔여 block이 넉넉치 않고 fit함
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
/*
* mm_init - initialize the malloc package.
* 최초 가용 블록으로 힙 생성하기
*/
int mm_init(void)
{
/* 1) 힙 영역의 기본 구조를 위한 4 워드(4*WSIZE 바이트) 확보 */
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
{
return -1;
}
/* 2) Alignment padding (정렬 패딩) */
PUT(heap_listp, 0);
/* 3) Prologue header: 크기 DSIZE(=8바이트), 할당(1) */
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));
/* 4) Prologue footer: 크기 DSIZE(=8바이트), 할당(1) */
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));
/* 5) Epilogue header: 크기 0, 할당(1) → 힙 끝 표시 */
PUT(heap_listp + (3 * WSIZE), PACK(0, 1));
/* 6) heap_listp를 첫 번째 유효 블록의 payload 시작점으로 조정 */
heap_listp += (2 * WSIZE);
/* 7) CHUNKSIZE 바이트(보통 4096B 등)만큼 빈 블록 생성 */
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)
{
char *bp;
size_t asize; // 실제 할당할 블록 크기
size_t extendsize; // free 블록이 없을 때 확장 요청할 크기
if (size == 0)
{
return NULL;
}
if (size <= DSIZE)
{
asize = 2 * DSIZE; // 헤더+푸터(8B) 페이로드(8B)
}
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_free - Freeing a block does nothing.
*/
void mm_free(void *ptr)
{
size_t size = GET_SIZE(HDRP(ptr));
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
coalesce(ptr);
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size)
{
void *oldptr = ptr;
void *newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}
어서오세요! ☺️ 후회 없는 내일을 위해 오늘을 열심히 살아가는 개발자입니다.