CSAPP에 나와있는 변수, 함수, 매크로들을 정리한 문서입니다.

동작하도록 만들기 위해서는 추가적인 작업이 필요합니다.
(find_fit&place 함수 구현, 타입 변환 등...)

1. memlib.c 파일

1) 변수

(1) *mem_start_brk

static char *mem_start_brk;

힙의 첫 번째 바이트를 가리키는 포인터이다.

(2) *mem_brk

static char *mem_brk;

현재 힙의 끝(마지막 바이트 + 1)을 가리키는 포인터이다.

(3) *mem_max_addr

static char *mem_max_addr;

허용 가능한 힙의 최대 주소에서 1을 더한 값이다.

2) 함수

(1) mem_init

void mem_init(void)
{
    /* 첫번째 문단 */
    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;
    mem_brk = mem_start_brk;
}

mem_init 함수는 memlib.c 안에 정의되어 있다.
이 함수의 역할은 Malloc Lab에서 사용할 가상 힙 메모리 모델을 초기화하는 것이다.
실제 시스템 메모리를 직접 건드리지 않고, 고정된 크기의 가상 힙을 모델링하여 안전하게 할당기를 실습할 수 있도록 한다.

첫번째 문단

#define MAX_HEAP (20*(1<<20))

if ((mem_start_brk = (char *)malloc(MAX_HEAP)) == NULL) {
    fprintf(stderr, "mem_init_vm: malloc error\n");
    exit(1);
}

malloc(MAX_HEAP)을 통해 20MB 크기의 메모리 공간을 확보한다.
(config.h에 MAX_HEAP이 정의되어 있다.)
이는 할당기 실습에서 사용할 전체 가상 힙 공간이다.

mem_start_brk은 이 힙 공간의 시작 주소를 저장한다.
만약 메모리 할당에 실패하면 exit(1)로 프로그램을 종료한다.

두번째 문단

mem_max_addr = mem_start_brk + MAX_HEAP;

mem_max_addr는 가상 힙의 최대 주소값을 나타낸다.
이는 힙의 첫번째 바이트에서 MAX_HEAP을 더한 주소이다.

mem_brk = mem_start_brk

mem_brk는 현재 힙의 끝 주소이다.
아직 아무것도 할당되지 않았기 때문에, 힙 시작 주소로 초기화된다.

(2) *mem_sbrk

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

mem_sbrk 함수는 기존의 시스템 호출 sbrk()처럼 동작하는 가상 힙 확장 함수이다.
힙을 incr 바이트만큼 확장하고, 확장 이전 힙의 끝 주소를 반환한다.

단, 이 구현에서는 힙 축소는 허용되지 않는다 (incr < 0 금지).

첫번째 문단

char *old_brk = mem_brk;

현재 힙 포인터 mem_brk를 old_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;
}

만약 incr가 음수거나 힙이 확장되었을 때 경계를 초과한다면, 에러 메시지를 출력하고 (void *)-1을 반환한다.

세번째 문단

mem_brk += incr;
return (void *)old_brk;

mem_brk를 incr만큼 증가시켜 확장한다.
확정 전 힙 포인터였던 old_brk를 반환한다.

2. mm.c 파일

1) 매크로

(1) ALIGNMENT

#define ALIGNMENT 8

정렬조건을 8바이트로 설정한다.

(2) ALIGN

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

주어진 size를 ALIGNMENT의 배수로 올린다.
즉, 8바이트로 정렬해준다.

(3) SIZE_T_SIZE

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

size_t 타입의 크기를 8바이트 단위로 정렬해서 알려준다.

(4) WSIZE

#define WSIZE 4

word의 크기는 4바이트이다.
header/footer의 크기도 4바이트로 설정했다.

(5) DSIZE

#define DSIZE 8 

double word의 크기는 8바이트이다.

(6) CHUNKSIZE

#define CHUNKSIZE (1 << 12)

초기 가용 블록과 힙 확장을 위한 기본 크기 (4KB)이다.

(7) PACK

#define PACK(size, alloc) ((size) | (alloc))

블록의 크기(size)와 할당 여부를 OR비트 연산으로 합쳐서 header를 표시한다.

(8) GET

#define GET(p) (*(unsigned int *)(p))

포인터 p가 가리키는 메모리 주소에 있는 4바이트를 가져온다.

(9) PUT

#define PUT(p, val) (*(unsigned int *)(p) = (val))

포인터 p가 가리키는 곳에 val 값을 저장한다.

(10) GET_SIZE

#define GET_SIZE(p) (GET(p) & ~0x7)

포인터 p가 가리키는 4바이트 값에서 하위 3비트를 제거해 블록의 크기만 가져온다.

(11) GET_ALLOC

#define GET_ALLOC(p) (GET(p) & 0x1) 

포인터 p가 가리키는 4바이트 값에서 하위 1비트만 추출해 할당 여부만 가져온다.

(12) HDRP

#define HDRP(bp) ((char *)(bp) - WSIZE)

payload 포인터 bp에서 4바이트(WSIZE) 앞쪽으로 이동해서 블록의 헤더 주소를 계산한다.
아래는 bp의 위치이다.

[ Header | Payload | ... | Footer ]
          ↑
         bp

(13) FTRP

#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

bp를 기준으로 블록의 전체 크기만큼 뒤로 이동한다.
그 후 8바이트(header+footer)를 앞으로 이동해 footer의 위치를 계산한다.

(14) NEXT_BLKP

#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))

현재 블록의 bp를 기준으로 블록의 전체 크기만큼 뒤로 이동한다.
즉, 다음 블록 포인터로 이동한다.

(15) PREV_BLKP

#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

현재 블록의 bp에서 8바이트만큼 앞으로 가서 이전 블록의 footer를 찾는다.
bp를 기준으로 footer에 적힌 크기만큼 앞으로 이동하여 이전 블록의 시작 주소를 계산한다.
즉, 이전 블록 포인터로 이동한다.

2) 함수

(1) mm_init

/* 첫번째 문단 */
static char *heap_listp = 0;

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));
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));
    PUT(heap_listp + (3 * WSIZE), PACK(0, 1));
    heap_listp += (2 * WSIZE);

	/* 네번째 문단 */
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;
        
    return 0;
}

mm_init은 할당기를 초기화하고, 성공하면 0을 실패하면 -1을 반환하는 함수이다.
문단을 나눠서 이해해보자.

첫번째 문단

static char *heap_listp = 0;

heap_listp는 프롤로그 블록의 payload 시작 주소를 나타내는 포인터다.
초기에는 아직 아무 메모리를 가리키지 않기 때문에 0으로 설정한다.

두번째 문단

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

mem_sbrk(4 * WSIZE)를 호출해서 16바이트만큼의 초기 힙 공간을 확보한다.
성공하면 heap_listp는 새로 할당받은 힙 메모리의 시작 주소를 가리킨다.
실패하면 -1을 반환하고 종료한다.

세번째 문단

PUT(heap_listp, 0);
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));
PUT(heap_listp + (3 * WSIZE), PACK(0, 1));
heap_listp += (2 * WSIZE);

PUT(heap_listp, 0);

힙의 첫 번째 워드에 0을 저장한다.
패딩 워드를 만들어 8바이트 정렬을 유지하기 위한 것이다.

PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));

힙 두 번째 워드에 프롤로그 블록의 header를 저장한다.
크기는 8바이트(DSIZE), 할당됨(1) 상태로 표시한다.

PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));

힙 세 번째 워드에 프롤로그 블록의 footer를 저장한다.
역시 크기 8바이트, 할당됨(1) 상태다.

PUT(heap_listp + (3 * WSIZE), PACK(0, 1));

힙 네 번째 워드에 에필로그 블록의 header를 저장한다.
크기는 0, 할당됨(1) 상태다.
(에필로그는 항상 '0 크기, 할당됨'으로 표시한다)

heap_listp += (2 * WSIZE); 

프롤로그 블록의 payload 시작 주소를 가리키도록 포인터를 8바이트 이동시킨다.

그림으로 표시하면 다음과 같다.

0 | 8/1 | payload(0) | 8/1 | 0/1
        ↑
   heap_listp

네번째 문단

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

extend_heap(CHUNKSIZE / WSIZE)를 호출해 4KB만큼 힙을 확장한다.
확장에 실패하면 -1을, 성공하면 0을 반환한다.

(2) *extend_heap

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

extend_heap은 words만큼 힙을 확장하는 함수이다.

첫번째 문단

char *bp;
size_t size;

bp는 새로 확장한 힙의 payload 시작 주소를 저장할 포인터이다.
즉, 새로 생긴 free block의 포인터이다.
size는 이번에 얼마나 힙을 확장할지 결정하는 크기이다.

두번째 문단

size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
if ((long)(bp = mem_sbrk(size)) == -1)
    return NULL;

만약 words가 홀수라면, 8바이트 정렬을 맞추기 위해 1을 더해준다.
그런 다음 WSIZE(4바이트)를 곱해 바이트 단위 크기로 맞춘다.
항상 짝수 개 워드(8바이트 배수)만큼 되도록 강제한다.

성공하면 bp는 확장 전 포인터로 정의된다.
실패하면 NULL을 반환하고 종료한다.

세번째 문단

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

PUT(HDRP(bp), PACK(size, 0));

새로 만든 free block의 header에 크기와 할당 여부를 기록한다.
이때 크기는 size, 할당 여부는 0(free 상태)이다.

PUT(FTRP(bp), PACK(size, 0));

새로 만든 free block의 footer에 크기와 할당 여부를 기록한다.
크기는 size, 할당 여부는 0이다.

PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));

새로 만든 free block 뒤에 크기와 할당 여부를 가진 에필로그 블록을 만들어준다.
크기는 0, 할당 여부는 1이다.
즉, 새 free block 뒤에 새로운 에필로그 블록을 넣어 힙 경계를 명확하게 만든다.

네번째 문단

return coalesce(bp);

확장한 새 free block(bp)을 coalesce해서 반환한다.
바로 이전 블록이 free였을 수도 있기 때문에, 바로 이어서 합칠 수 있는지 체크한다.

(3) 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_free는 주어진 포인터 ptr이 가리키는 블록을 해제(free)하는 함수이다.

첫번째 문단

size_t size = GET_SIZE(HDRP(ptr));

HDRP(ptr)를 통해 해당 블록의 header의 위치를 찾는다.
GET_SIZE(HDRP(ptr))를 통해 블록의 전체 크기(size)를 추출한다.

즉, "ptr이 속한 블록의 크기"를 가져와서 size에 저장한다.

두번째 문단

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

블록의 헤더와 풋터에 size와 0(free 상태)를 기록한다.
이 블록은 free 상태이며, 크기는 size임을 힙에 표시하는 것이다.

세번째 문단

coalesce(ptr);

방금 해제한 블록이 주변 free 블록들과 병합(coalescing)이 가능한지 체크한다.
만약 주변 블록도 free 상태라면, 인접한 free 블록들과 합쳐서 더 큰 free 블록을 만든다.

(4) *coalesce

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) {
        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));
    }
    
	/* 네번째 문단 */
    else if (!prev_alloc && next_alloc) {
        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 {
        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);
    }
	
    /* 여섯번째 문단 */
  	return bp;
}

coalesce는 주어진 블록(bp)을 기준으로, 주변 free 블록들과 병합(coalescing)하는 함수이다.

첫번째 문단

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

• prev_alloc: 이전 블록의 풋터에서 할당 여부 정보를 가져온다.
• next_alloc: 다음 블록의 헤더에서 할당 여부 정보를 가져온다.
• size: 현재 블록(bp)의 크기를 가져온다.

현재 블록의 앞뒤 블록이 할당 상태인지 아닌지를 미리 조사해두는 부분이다.

두번째 문단

if (prev_alloc && next_alloc) {
    return bp;
}

이전 블록과 다음 블록이 모두 할당되어 있으면 병합할 필요가 없다.
아무것도 병합하지 않고 현재 블록(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));
}

이전 블록은 할당되어 있으며, 다음 블록만 free인 경우이다.
이 경우 현재 블록 + 다음 블록을 합쳐서 하나의 free 블록으로 만든다.
병합된 블록의 헤더와 풋터를 다시 써준다.

네번째 문단

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

이전 블록은 free 상태, 다음 블록은 할당되어있는 경우이다.
이 경우 이전 블록 + 현재 블록을 합쳐서 하나의 free 블록으로 만든다.
이때 bp를 앞 블록의 시작점으로 옮긴다.

다섯번째 문단

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

이전 블록과 다음 블록 모두 free 상태인 경우이다.
이 경우 이전 블록 + 현재 블록 + 다음 블록을 전부 합친다.
이때 bp를 합쳐진 가장 앞 블록으로 옮긴다.

여섯번째 문단

return bp;

병합이 끝난 블록의 포인터(bp)를 반환한다.
이 포인터는 병합된 블록의 payload 시작 위치를 가리킨다.
이후 다른 동작(예: 할당 등)에서 이 병합된 블록을 사용할 수 있다.

(5) *mm_malloc

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);
        return bp;
    }
 
    /* 다섯번째 문단 */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
        return NULL;
  
    place(bp, asize);
    return bp;
}

mm_malloc은 사용자가 요청한 size만큼 메모리를 할당하는 함수이다.

첫번째 문단

size_t asize;
size_t extendsize;
char *bp;

• asize: 요청한 size를 조정해 실제로 할당할 크기를 저장한다.
• extendsize: 힙을 얼마나 확장할지 결정할 때 사용한다.
• bp: 할당할 블록의 payload 시작 포인터이다.

두번째 문단

if (size == 0)
    return NULL;

요청한 size가 0이면, 메모리 할당이 의미가 없다.
NULL을 반환하고, 종료한다.

세번째 문단

if (size <= DSIZE)
    asize = 2 * DSIZE;
else
    asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);

요청한 size를 조정하여 asize를 만든다.
size <= DSIZE(8)이면, 최소 블록 크기 16바이트(2 * DSIZE)를 할당한다.
size > DSIZE이면, 8바이트 단위로 올림 정렬하여 블록 크기를 맞춘다.

블록은 항상 최소 16바이트 이상, 8바이트 단위 정렬을 유지해야 한다.

네번째 문단

if ((bp = find_fit(asize)) != NULL) {
    place(bp, asize);
    return bp;
}

free list에서 asize 크기 이상인 블록을 찾는다 (find_fit).
찾았다면, 그 블록에 실제로 배치하고(place) 바로 반환한다.

이미 할당할 수 있는 free block이 있으면, 힙을 확장하지 않고 재사용한다.

다섯번째 문단

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

free block이 없다면, 힙을 확장해야 한다.
요청한 asize와 기본 크기 CHUNKSIZE(4KB) 중 더 큰 쪽을 골라서 확장한다.
확장에 성공했다면, 새로 생긴 free block에 블록을 배치(place)한다.