Malloc-Lab
개요
메모리 정렬 제한과 패킹
https://woo-dev.tistory.com/139
32bit의 CPU는 한 번에 32bit(4byte)를 들고 오는데, 주소가 맞지 않으면 1개의 블럭이 아니라 2개의 블럭을 읽어야 되고 shift 및 OR 연산도 해줘야되기 때문에 속도가 느려진다.
메모리가 정렬되어 있지 않다면 이러한 어긋나는 주소가 많을 것이고 속도는 더욱 더 느려질 수 있기 때문에 패딩 데이터를 추가한다.
Heap
런타임 때 가상 메모리를 획득하기 위해, 메모리의 힙 영역에 동적 할당을 진행한다.
* 런타임 : 컴파일 과정을 마친 응용 프로그램이, 사용자에 의해 실행되어지는 때(time)을 의미한다.
즉 동적 메모리 할당기(Dynamic memory allocator)는 힙이라고 알려진 가상 메모리를 관리하게 된다. 이러한 힙 영역에는 할당된 블록(allocated)과 가용 블록(free)이 있다.
그리고 이러한 할당기에는 explicit allocator(c에서 malloc과 free 함수), implicit allocator(garbage collection)이 있다. 먼저 explicit allocator를 보기로 하겠다.
Malloc Package
- malloc
void *malloc(size_t size)할당 성공 시, 8바이트로 정렬된(32비트라고 가정했을 때) 메모리의 주소를 가르키는 포인터를 반환한다. 실패 시 NULL(0)을 반환한다.
- free
void free(void *p)가용한 메모리 블록을 가리키는 포인터를 반환한다. p는 먼저 malloc이나 calloc에 의해 할당이 됐었어야 한다.
- calloc : 블록을 0으로 초기화시키는 malloc의 또다른 버전이라고 보면 된다.
- realloc : 이미 할당된 블록의 사이즈를 변화시킨다. (줄이거나 늘리거나)
- sbrk(S break) : 힙 자체를 늘리거나 줄일 때 사용한다.
간단한 malloc 사용 예시
#include <stdio.h>
#include <stdlib.h>
void main(int n) {
int i, *p;
// n개의 int형(4바이트) 블록을 할당시킨다.
p = (int *)malloc(n * sizeof(int));
if (p == NULL) {
perror("malloc");
exit(0);
}
// 할당된 블록들을 초기화시키기
for (i = 0; i < n; i++) {
p[i] = i;
}
// 힙 안의 할당되어진 블록들을 free 시키기
free(p);
}
allocator 구현의 제약들
- 이미 할당된 블록의 사이즈를 수정할 수 없다.
- malloc 요청에 바로 응답한다. 이를 지연시키거나 재정렬이 불가능하다.(요청 자체를 정렬, 즉 순서를 바꾸는 것이 효율적이다. 하지만 malloc 요청이 들어오면 지연시키는 것이 아니라 곧바로 힙의 메모리를 할당한 후 포인터를 반환할 수 있어야 한다.)
- free인 블록에만 할당이 가능하다.
- 메모리 정렬이 필요하다.(32비트라면 4바이트씩, 64비트라면 8바이트씩)
- free 블록만 조작하거나 변경할 수 있다.
- 할당된 블록은 옮길 수 없다.
allocator 구현 이슈
- 어느 정도의 메모리를 free시켜야 할지, 하나의 포인터로 어떻게 알 수 있는가?
- free 블록들을 어떻게 추적할 것인가?
- 메모리를 할당한 후, 남은 free 블록들을 어떻게 처리할 것인가? 그대로 놔두면 내부 단편화가 일어날 것이다. 작은 블록으로 다시 나눠서 free 블록으로 쓸 수도 있을 것이다.
- 할당될 free 블록득을 어떻게 고를 것인가?
- free된 블록들을 어떻게 할 것인가? 재연결을 어떻게 할 것인가?
header
header에는 해당 블록의 사이즈가 몇인지, 할당되었는지 혹은 free인지를 나타내는 데이터가 담겨져 있다.
free 블록들을 추적하는 방법
- implicit list : 모든 블록들의 헤더들을 방문하여, 해당 블록이 사용할 수 있는지를 저장한다.
- explicit list : free 블록 내에 다음 free 블록을 가리키는 포인터가 있어, 한 free 블록에서 다음 free 블록의 위치를 명시적으로 알 수 있다.
- segregated free list : 할당이 해제되어 있는 블록들을 사이즈 별로 각각의 연결 리스트로 만들어 관리한다.
- blocks sorted by size : 균형 트리(ex. 레드 블랙 트리)를 이용해 가용 리스트들을 크기 순서대로 정렬한다.
Method 1: Implicit Free List
블록의 사이즈와, 할당되었는지 혹은 free인지 판별할 수 있는 상태를 2개의 워드(4바이트, 윗 윗 그림의 박스 1개)를 이용해서 나타내는 것은 너무 낭비다. 따라서 위의 그림처럼 1개의 워드에 블록의 크기와 할당 유무 상태를 담는다. 이것이 header이다.
블록이 할당되어 있으면 a(1개의 비트)는 1이고, free이면 0이다. 사이즈만 표시하게 되면, a는 항상 0이기 때문에(사이즈가 4바이트이면 100, 2바이트이면 10 등 끝은 항상 0이다) 여기를 allocated/free flag로 사용한다.
Implicit Free List 예시
맨 처음은 unused word로 처리한다. 맨 처음 헤더가 필요하고, 여기선 32bit로 8바이트(워드 2개)로 정렬되어 있다는 전제가 있기 때문이다.
free 블록을 찾는 방법
- first fit : 리스트의 처음부터 탐색을 시작해, 조건에 맞는 맨 첫 블록에 할당한다.
p = start;
while ((p < end) && ((*p & 1) || (*p <= len))) {
p = p + (*p & -2);
}p의 주소값이, heap의 맨 끝 주소보다 작을 때만 반복해서 찾는다. 그리고 p가 가르키는 값(헤더인듯?)의 맨 끝 비트가 1이면 할당되어 있다는 뜻이니 또 넘어간다. 또한 우리가 할당하려는 사이즈보다, p가 가르키는 블록의 사이즈가 작으면 할당할 수 없으니 이 또한 넘어간다.
p = p + (*p & -2);2는 11111110이라고 볼 수 있다. 따라서 &라는 비트 연산자를 통해 p의 사이즈만 가져올 수 있다. 맨 마지막은 allocated, free를 나타내는 flag이므로 이와 상관없이 사이즈만 가져올 수 있다.
- next fit : 이전 탐색이 끝난 지점으로부터 free 리스트를 탐색한다.
- best fit : 처음부터 전부 검색하여 크기가 딱 맞는 블록을 추려낸다. first fit보다 느릴 수 있다.
free 블록에 할당하기
우리가 할당하고자 하는 블록의 크기가 free 블록의 크기보다 작을 수 있다. 이럴 때는 내부 단편화로 고생하기 보다는 남은 블록을 split 해주는 것이 효율적이다.
void addblock (ptr p, int len) {
int newsize = ((len + 1) >> 1) << 1;
int oldsize = *p & -2;
*p = newsize | 1;
if (newsize < oldsize) {
*(p + newsize) = oldsize - newsize;
}
}할당되는 크기인 newsize는 짝수가 되게 한다.(왜 그런지는 모르겠다) 홀수가 들어오면 +1을 한 후 오른쪽으로 shift하고 다시 왼쪽으로 shift하면 맨 끝이 0이면서 크기는 짝수가 된다. 원래 사이즈를 oldsize로 읽어주고 p가 가르키는 곳에는 newsize를 넣음과 동시에 1을 더하여 allocated임을 표시한다. 이 때 만약 원래 블록의 크기가 더 컸다면, p에 newsize만큼 더한 곳의 헤더에는 할당하고 남은 블록의 크기를 나타내게 한다. 이 때 newsize와 oldsize 모두 맨 끝 비트(allocated/free flag)는 0이므로 둘이 빼주기만 하면 된다.
할당된 블록을 free시키기
void free_block(ptr p) {
*p = *p & - 2;
}free시키는 것은 어렵지 않다. 단순히 맨 끝 flag 비트를 0으로 바꿔주면 된다. 블록에 할당된 데이터는 지워지는 방식이 아니라 덮어씌워지게 되는 것이다.
하지만 이렇게만 해주면 다음과 같이 5를 할당할 때 외부 단편화로 인해 할당할 수 없게 된다. 따라서 free끼리 이어져 있다면 연결시켜줘야 한다.
Coalescing
단순히 free만 시키는 코드에서 보완한 것(연결까지 해줄 수 있는)이 밑의 코드이다.
void free_block(ptr p) {
*p = *p & -2; // 기존 블록을 반환한다. *p = 0000 0101(allocated) -> 0000 0100(free), p = 0000 1000이라고 가정한다면,
next = p + *p; // 다음 블록은 기존 블록에 그 크기를 더한 값이 된다. next = 0000 1100
if ((*next & 1) == 0) { // 만약 다음 블록이 free 블록이라면, ex. *next = 0000 0010
*p = *p + *next; // 블록의 크기를 늘린다. 이 때 *p, 즉 포인터가 가르키는 값은 헤더이다.
} // *p는 0000 0110으로 크기가 4에서 6으로 된다.
}flag를 0으로 만들어준 후, next는 현재 가르키는 포인터에 사이즈를 더해주는 것이다. 이 때 이 next의 flag가 0이라면 free 블록임을 나타내므로 포인터가 가르키는 header에 현재 블록 사이즈와 next 블록의 사이즈를 더해준다. 이 때 둘 다 flag는 0이므로 그저 더해주기만 하면 된다.
위는 다음의 블록이 free일 때이다. 하지만 이전의 블록이 free라면 어떻게 연결해줄 수 있을까?
Bidirectional Coalescing
헤더를 그저 모방하여(복사하여), 블록의 끝에 위치시키도록 한다. 이를 footer 혹은 경계 태그라고 칭한다. 이는 free 리스트를 탐색할 때 뒤로 가는 것 뿐만 아니라 앞으로도 갈 수 있게 해주지만, 공간을 추가적으로 요구한다.
헤더에서 한 칸만 앞으로 가면 이전 블록이 할당 상태인지, free 상태인지 알 수 있다. 따라서 상수 시간, constant time으로 연결을 처리할 수 있다. 따라서 free 블록을 연결하는 데에 발생할 수 있는 시간 복잡도는 O(1)이 된다.
Coalescing 4가지 경우
Boundary Tag의 단점과 개선 방안
-
단점 : 결국 header와 footer라는 개념을 사용하면 새로운 메모리 공간을 계속 필요로 하는 셈이니 메모리 오버헤드가 발생한다.
* 오버헤드 : 어떤 처리를 하기 위해 필요한 간접적인 시간 or 메모리로, header와 footer라는 개념을 도입하면서 메모리 공간을 차지하게 되니 전체적으로 필요한 메모리 공간이 더 늘어나게 된다. -
개선 방안 : 이전 혹은 이후 블록이 할당된다면, 즉 할당된 블록이 되버린다면 footer를 없애고 데이터를 넣을 수 있도록 한다. case들을 살펴보면 할당된 블록들의 footer들은, 연결된 블록의 header와 footer에 아무런 영향을 끼치고 있지 않다. 따라서 할당된 블록에서는 footer가 필요치 않다.
그렇다면, 해당 블록은 어떻게 이전의 블록이 할당되었는지 혹은 free인지 알 수 있을까? 해당 블록에서 헤더의 사용하지 않는 비트인 3개의 비트 중 1개에 이전의 블록 할당 상태를 저장하면 된다. 이러면 앞의 블록이 할당되었다고 가정했을 때, 현재 해당 블록의 3개 비트 중 1개의 비트는 이전 블록이 할당되었다고 알려주므로 연결을 시도하지 않을 것이다.
Implicit free list 요약
- 할당에 필요한 시간 : 최악의 경우 선형 시간이 소모된다.
- free 시키는데 필요한 시간 : 이전 혹은 다음 블록이 free라서 연결을 진행함에도 불구하고 상수 시간이 소모된다.
- 메모리 최적화의 정도는 free 블록을 어떻게 찾는지에 따라 달라진다.(first-fit, next-fit, best-fit)
- 할당하고 남은 블록을 분할하거나, 경계 태그를 이용해 free 블록을 연결하는 개념은 모든 할당기의 종류들을 구현할 때 통용되는 개념이다.
소스 코드(first-fit, next-fit)
* next-fit 선언 부분을 주석 처리하면 first-fit으로 동작한다.
/*
* Malloc using implicit free list with first-fit or next-fit
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
/*********************************************************
* Information of my team
********************************************************/
team_t team = {
/* Team name */
"jungle",
/* First member's full name */
"Shin Seung Jun",
/* First member's email address */
"alohajune22@gmail.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
/* rounds up to the nearest multiple of ALIGNMENT */
// size(변수)보다 크면서 가장 가까운 8의 배수로 만들어주는 것이 Align이다. -> 정렬
// size = 7 : (00000111 + 00000111) & 11111000 = 00001110 & 11111000 = 00001000 = 8
// size = 13 : (00001101 + 00000111) & 11111000 = 00010000 = 16
// 즉 1 ~ 7 바이트 -> 8 바이트
// 8 ~ 16 바이트 -> 16 바이트
// 7 ~ 24 바이트 -> 24 바이트
// 여기서 ~는 not 연산자로, 원래 0x7은 0000 0111이고 ~0x7은 1111 1000이 된다.
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
/* 메모리 할당 시 */
// size_t는 '부호 없는 32비트 정수'로 unsigned int이다. 따라서 4바이트이다.
// 따라서 메모리 할당 시 기본적으로 header와 footer가 필요하므로 더블워드만큼의 메모리가 필요하다. size_t이므로 4바이트이니 ALIGN을 거치면 8바이트가 된다.
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
/* 기본 상수와 매크로 */
#define WSIZE 4 // 워드 사이즈
#define DSIZE 8 // 더블 워드 사이즈
#define CHUNKSIZE (1<<12) // 처음 4kB 할당. 초기 free 블록이다.
#define MAX(x, y) ((x) > (y) ? (x) : (y)) // 최댓값을 구하는 함수 매크로
#define PACK(size, alloc) ((size) | (alloc)) // free 리스트에서 header와 footer를 조작하는 데에는, 많은 양의 캐스팅 변환과 포인터 연산이 사용되기에 애초에 매크로로 만든다.
// size 와 alloc을 or 비트 연산시킨다.
// 애초에 size의 오른쪽 3자리는 000으로 비어져 있다.
// 왜? -> 메모리가 더블 워드 크기로 정렬되어 있다고 전제하기 때문이다. 따라서 size는 무조건 8바이트보다 큰 셈이다.
/* 포인터 p가 가르키는 워드의 값을 읽거나, p가 가르키는 워드에 값을 적는 매크로 */
#define GET(p) (*(unsigned int *)(p)) // 보통 p는 void 포인터라고 한다면 곧바로 *p(* 자체가 역참조)를 써서 참조할 수 없기 때문에, 그리고 우리는 4바이트(1워드)씩 주소 연산을 한다고 전제하기에 unsigned int로 캐스팅 변환을 한다. p가 가르키는 곳의 값을 불러온다.
#define PUT(p, val) (*(unsigned int *)(p) = (val)) // p가 가르키는 곳에 val를 넣는다.
/* header 혹은 footer의 값인 size or allocated 여부를 가져오는 매크로 */
#define GET_SIZE(p) (GET(p) & ~0x7) // 블록의 사이즈만 가지고 온다. ex. 1011 0111 & 1111 1000 = 1011 0000으로 사이즈만 읽어옴을 알 수 있다.
#define GET_ALLOC(p) (GET(p) & 0x1) // 블록이 할당되었는지 free인지를 나타내는 flag를 읽어온다. ex. 1011 0111 & 0000 0001 = 0000 0001로 allocated임을 알 수 있다.
/* 블록 포인터 bp(payload를 가르키고 있는 포인터)를 바탕으로 블록의 header와 footer의 주소를 반환하는 매크로 */
#define HDRP(bp) ((char *)(bp) - WSIZE) // header는 payload보다 앞에 있으므로 4바이트(워드)만큼 빼줘서 앞으로 1칸 전진하게 한다.
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // footer는 payload에서 블록의 크기만큼 뒤로 간 다음 8바이트(더블 워드)만큼 빼줘서 앞으로 2칸 전진하게 해주면 footer가 나온다.
// 이 때 포인터는 char형이어야 4 혹은 8바이트, 즉 정확히 1바이트씩 움직일 수 있다. 만약 int형으로 캐스팅 해주면 - WSIZE 했을 때 16바이트 만큼 움직일 수도 있다.
/* 블록 포인터 bp를 바탕으로, 이전과 다음 블록의 payload를 가르키는 주소를 반환하는 매크로 */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) // 지금 블록의 payload를 가르키는 bp에, 지금 블록의 header 사이즈를 읽어서 더하면(word 만큼) 다음 블록의 payload를 가르키게 된다.
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) // 지금 블록의 payload를 가르키는 bp에, 이전 블록의 footer 사이즈를 읽어서 뺴면(double word 만큼) 이전 블록의 payload를 가르키게 된다.
/* define searching method for find suitable free blocks to allocate */
#define NEXT_FIT // define하면 next_fit, 안하면 first_fit으로 탐색한다.
/* global variable & functions */
static char* heap_listp; // 항상 prologue block을 가리키는 정적 전역 변수 설정
// static 변수는 함수 내부(지역)에서도 사용이 가능하고 함수 외부(전역)에서도 사용이 가능하다.
#ifdef NEXT_FIT // #ifdef ~ #endif를 통해 조건부로 컴파일이 가능하다. NEXT_FIT이 선언되어 있다면 밑의 변수를 컴파일 할 것이다.
static void* last_freep; // next_fit 사용 시 마지막으로 탐색한 free 블록을 가리키는 포인터이다.
#endif
/* 코드 순서상, implicit declaration of function(warning)을 피하기 위해 미리 선언해주는 부분? */
static void* extend_heap(size_t words);
static void* coalesce(void* bp);
static void* find_fit(size_t asize);
static void place(void* bp, size_t newsize);
int mm_init(void);
void *mm_malloc(size_t size);
void mm_free(void *bp);
void *mm_realloc(void *ptr, size_t size);
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void) {
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1) // memlib.c를 살펴보면 할당 실패시 (void *)-1을 반환하고 있다. 정상 포인터를 반환하는 것과는 달리, 오류 시 이와 구분 짓기 위해 mem_sbrk는 (void *)-1을 반환하고 있다.
return -1; // 할당에 실패하면 -1을 리턴한다.
PUT(heap_listp, 0); // Alignment padding으로 unused word이다. 맨 처음 메모리를 8바이트 정렬(더블 워드)을 위해 사용하는 미사용 패딩이다.
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); // prologue header로, 맨 처음에서 4바이트 뒤에 header가 온다. 이 header에 사이즈(프롤로그는 8바이트)와 allocated 1(프롤로그는 사용하지 말라는 의미)을 통합한 값을 부여한다.
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); // prologue footer로, 값은 header와 동일해야 한다.
PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); // epilogue header
heap_listp += (2 * WSIZE); // heap_listp는 prologue footer를 가르키도록 만든다.
#ifdef NEXT_FIT
last_freep = heap_listp; // next_fit 사용 시 마지막으로 탐색한 free 블록을 가리키는 포인터이다.
#endif
// CHUCKSIZE만큼 힙을 확장해 초기 free 블록을 생성한다. 이 때 CHUCKSIZE는 2^12으로 4kB 정도였다.(4096 bytes)
if (extend_heap(CHUNKSIZE / WSIZE) == NULL) { // 곧바로 extend_heap이 실행된다.
return -1;
}
return 0;
}
/*
* extend_heap - word 단위의 메모리를 인자로 받아 힙을 늘려준다.
*/
static void* extend_heap(size_t words) {
char* bp;
size_t size;
size = (words % 2 == 1) ? (words + 1) * WSIZE : (words) * WSIZE; // words가 홀수로 들어왔다면 짝수로 바꿔준다. 짝수로 들어왔다면 그대로 WSIZE를 곱해준다. ex. 5만큼(5개의 워드 만큼) 확장하라고 하면, 6으로 만들고 24바이트로 만든다.
// 8바이트(2개 워드, 짝수) 정렬을 위해 짝수로 만들어줘야 한다.
if ((long)(bp = mem_sbrk(size)) == -1) { // 변환한 사이즈만큼 메모리 확보에 실패하면 NULL이라는 주소값을 반환해 실패했음을 알린다. bp 자체의 값, 즉 주소값이 32bit이므로 long으로 캐스팅한다.
return NULL; // 그리고 mem_sbrk 함수가 실행되므로 bp는 새로운 메모리의 첫 주소값을 가르키게 된다.
}
// 새 free 블록의 header와 footer를 정해준다. 자연스럽게 전 epilogue 자리에는 새로운 header가 자리 잡게 된다. 그리고 epilogue는 맨 뒤로 보내지게 된다.
PUT(HDRP(bp), PACK(size, 0)); // 새 free 블록의 header로, free 이므로 0을 부여
PUT(FTRP(bp), PACK(size, 0)); // 새 free 블록의 footer로, free 이므로 0을 부여
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // 앞에서 현재 bp(새롭게 늘어난 메모리의 첫 주소 값으로 역시 payload이다)의 header에 값을 부여해주었다. 따라서 이 header의 사이즈 값을 참조해 다음 블록의 payload를 가르킬 수 있고, 이 payload의 직전인 header는 epilogue가 된다.
return coalesce(bp); // 앞 뒤 블록이 free 블록이라면 연결하고 bp를 반환한다.
}
/*
* mm_free - Freeing a block does nothing.
*/
void mm_free(void *bp) {
size_t size = GET_SIZE(HDRP(bp)); // bp가 가리키는 블록의 사이즈만 들고 온다.
// header, footer 둘 다 flag를 0으로 바꿔주면 된다.
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp); // 앞 뒤 블록이 free 블록이라면 연결한다.
}
/*
* coalesce - 앞 혹은 뒤 블록이 free 블록이고, 현재 블록도 free 블록이라면 연결시키고 연결된 free 블록의 주소를 반환한다.
*/
static void* coalesce(void* bp) {
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // 이전 블록의 free 여부
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // 다음 블록의 free 여부
size_t size = GET_SIZE(HDRP(bp)); // 현재 블록의 사이즈
// 경우 1. 이전 블록 할당, 다음 블록 할당 - 연결시킬 수 없으니 그대로 bp를 반환한다.
if (prev_alloc && next_alloc) {
return bp;
}
// 경우 2. 이전 블록 할당, 다음 블록 free - 다음 블록과 연결시키고 현재 bp를 반환하면 된다.
else if (prev_alloc && !next_alloc) {
size += GET_SIZE(HDRP(NEXT_BLKP(bp))); // 다음 블록의 header에 저장된 다음 블록의 사이즈를 더해주면 연결된 만큼의 사이즈가 나온다.
PUT(HDRP(bp), PACK(size, 0)); // 현재 블록의 header에 새로운 header가 부여된다.
PUT(FTRP(bp), PACK(size, 0)); // 다음 블록의 footer에 새로운 footer가 부여된다.
}
// 경우 3. 이전 블록 free, 다음 블록 할당 - 이전 블록과 연결시키고 이전 블록을 가리키도록 bp를 바꾼다.
else if (!prev_alloc && next_alloc) {
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0)); // 현재 블록의 footer에 새로운 footer를 부여한다.
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 블록의 header에 새로운 header를 부여한다.
bp = PREV_BLKP(bp); // bp가 이전 블록을 가리키도록 한다.
}
// 경우 4. 이전 블록 free, 다음 블록 free - 모두 연결한 후 이전 블록을 가리키도록 bp를 바꾼다.
else {
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp))); // 이전 블록의 header에서 사이즈를, 다음 블록의 footer에서 사이즈를 읽어와 size를 더한다.
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 블록의 header에 새로운 header를 부여한다.
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0)); // 다음 블록의 footer에 새로운 footer를 부여한다.
bp = PREV_BLKP(bp);
}
#ifdef NEXT_FIT
last_freep = bp;
#endif
return bp;
}
/*
* 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; // 알맞은 크기의 free 블록이 없을 시 확장하는 사이즈
char *bp;
if (size == 0) {
return NULL; // 가짜 요청은 무시한다.
}
asize = ALIGN(size + SIZE_T_SIZE); // header와 footer를 위한 메모리, 즉 word 2개가 필요하므로 SIZE_T_SIZE만큼의 메모리가 필요하다. 여기에 현재 할당하려는 size를 더하면, header와 footer가 포함되면서 할당하려는 블록의 크기가 된다.
// 적절한 공간을 가진 블록을 찾으면 할당(혹은 분할까지) 진행한다.
// bp는 계속 free 블록을 가리킬 수 있도록 한다.
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
// 적절한 공간을 찾지 못했다면 힙을 늘려주고, 그 늘어난 공간에 할당시켜야 한다.
extendsize = MAX(asize, CHUNKSIZE); // 둘 중 더 큰 값을 선택한다.
if ((bp = extend_heap(extendsize / WSIZE)) == NULL) { // 실패 시 bp로는 NULL을 반환한다.
return NULL;
}
// 힙을 늘리는 데에 성공했다면, 그 늘어난 공간에 할당시킨다.
place(bp, asize);
return bp;
}
/*
* find_fit - 힙을 탐색하여 요구하는 메모리 공간보다 큰 가용 블록의 주소를 반환한다.
*/
static void* find_fit(size_t asize) {
// next-fit
#ifdef NEXT_FIT
void* bp;
void* old_last_freep = last_freep;
// 이전 탐색이 종료된 시점에서부터 다시 시작한다.
for (bp = last_freep; GET_SIZE(HDRP(bp)); bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
return bp;
}
}
// last_freep부터 찾았는데도 없으면 처음부터 찾아본다. 이 구문이 없으면 앞에 free 블록이 있음에도 extend_heap을 하게 되니 메모리 낭비가 된다.
for (bp = heap_listp; bp < old_last_freep; bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
return bp;
}
}
// 탐색을 마쳤으니 last_freep도 수정해준다.
last_freep = bp;
return NULL; // 못 찾으면 NULL을 리턴한다.
// first-fit
#else
void* bp;
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) { // heap_listp, 즉 prologue부터 탐색한다. 전에 우리는 heap_listp += (2 * WSIZE)를 해두었다.
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) { // 할당된 상태가 아니면서 해당 블록의 사이즈가 우리가 할당시키려는 asize보다 크다면 해당 블록에 할당이 가능하므로 곧바로 bp를 반환한다.
return bp;
}
}
return NULL; // 못 찾으면 NULL을 리턴한다.
#endif
}
/*
* place - 요구 메모리를 할당할 수 있는 가용 블록을 할당한다.(즉 실제로 할당하는 부분이다) 이 때 분할이 가능하다면 분할한다.
*/
static void place(void* bp, size_t asize) {
size_t csize = GET_SIZE(HDRP(bp)); // 현재 할당할 수 있는 후보, 즉 실제로 할당할 free 블록의 사이즈
// 분할이 가능한 경우
// 남은 메모리가 최소한의 free 블록을 만들 수 있는 4 word가 되느냐
// -> header/footer/payload/정렬을 위한 padding까지 총 4 word 이상이어야 한다.
if ((csize - asize) >= (2 * DSIZE)) { // 2 * DSIZE는 총 4개의 word인 셈이다. csize - asize 부분에 header, footer, payload, 정렬을 위한 padding까지 총 4개가 들어갈 수 있어야 free 블록이 된다.
// 앞의 블록은 할당시킨다.
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
// 뒤의 블록은 free시킨다.
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(csize - asize, 0));
PUT(FTRP(bp), PACK(csize - asize, 0));
coalesce(bp); // free 이후 뒤의 것과 또 연결될 수 있으므로 coalesce 실행
// 분할이 불가능한 경우
// csize - asize가 2 * DSIZE보다 작다는 것은 header, footer, payload, 정렬을 위한 padding 각 1개씩 총 4개로 이루어진 free 블록이 들어갈 공간이 없으므로 어쩔 수 없이 내부 단편화가 될 수 밖에 없다.
} else {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size) {
// 블록의 크기를 줄이는 것이면 줄이려는 size만큼으로 줄인다.
// 블록의 크기를 늘리는 것이면
// 핵심은, 이미 할당된 블록의 사이즈를 직접 건드리는 것이 아니라, 요청한 사이즈 만큼의 블록을 새로 메모리 공간에 만들고 현재의 블록을 반환하는 것이다.
// 해당 블록의 사이즈가 이 정도로 변경되었으면 좋겠다는 것이 size,
void *oldptr = ptr; // 크기를 조절하고 싶은 힙의 시작 포인터
void *newptr; // 크기 조절 뒤의 새 힙의 시작 포인터
size_t copySize; // 복사할 힙의 크기
newptr = mm_malloc(size); // place를 통해 header, footer가 배정된다.
if (newptr == NULL) {
return NULL;
}
copySize = GET_SIZE(HDRP(oldptr)); // 원래 블록의 사이즈
if (size < copySize) { // 만약 블록의 크기를 줄이는 것이라면 size만큼으로 줄이면 된다. copySize - size 공간의 데이터는 잘리게 된다. 밑의 memcpy에서 잘린 만큼의 데이터는 복사되지 않는다.
copySize = size;
}
memcpy(newptr, oldptr, copySize); // oldptr부터 copySize까지의 데이터를, newptr부터 심겠다.
mm_free(oldptr); // 기존 oldptr은 반환한다.
return newptr;
}Method 2: Explicit Free List
implicit free list가 모든 블록(할당 + free)을 탐색하며 해당 블록이 할당되었는지, 아니면 free인지 확인하며 필요한 동작을 수행했다면, explicit free list는 오직 free 블록만 탐색하게 된다. 이러한 free 블록을 탐색할 수 있도록 이중 연결 리스트로 구성되는데, 이를 통해서 앞으로만 탐색하는 것이 아니라 뒤로도 탐색하는 것이 가능해진다.
free 블록의 payload 부분은 사용하지 않는 상태로 되기 때문에 이 공간을 활용한다. 해당 블록에, 전의 free 블록의 주소로 갈 수 있는(주소값을 담고 있는) predecessor과 뒤의 free 블록의 주소로 갈 수 있는(주소값을 담고 있는) successor를 넣게 된다. 이를 통해 할당 블록은 탐색하지 않아 시간 비용을 낮출 수는 있지만, free 블록에서는 prec과 succ를 위한 공간이 추가적으로 요구되므로 메모리 활용도는 낮아진다.
이러한 연결 리스트에 free 블록을 추가하는 방식에 따라 블록의 물리적인 순서대로 연결리스트를 구성하는 address-ordered 방식과, 최근에 해제된 블록을 연결 리스트의 가장 앞에 넣고 할당할 때에도 되도록 앞의 free 블록이 할당되도록 하는 LIFO(last in first out) 방식이 있다. 전자는 단편화 방지에 좋은 반면, 후자는 탐색 시간을 상수로 만들기에 각자 장단점이 있다고 한다.
LIFO 방식을 보이도록 하겠다. LIFO를 이용한 explicit free list에서 주의할 점은 연결리스트 안의 free 블록 순서가, 물리적인 순서와는 다를 수 있음을 알아야 한다는 것이다. 그리고 이 연결리스트의 맨 끝은 prologue 블록(prologue 블록은 할당되어 있는 블록)이 들어가 있어 연결리스트가 끝나는 지점을 알 수 있게 한다.
메모리 할당 과정
- 연결리스트의 처음 블록부터 순회하며 블록의 사이즈가 할당시키기에 적절한지 탐색한다.
- 블록의 사이즈가 적절치 않다면 다음 블록으로 포인터를 이동시킨다.
- 만약 적절하다면, 즉 할당할 수 있다면
3-1. 해당 블록을 연결리스트에서 제거한다.
3-2. 할당 이후 분할이 가능하면 분할하여 새로운 free 블록을 만들고 연결리스트에 이 새로운 free 블록을 추가한다.(분할 시 최소 크기의 free 블록(header/footer/predecessor/successor)을 만들 수 없다면 어쩔 수 없이 메모리 주소 정렬을 위해 내부 단편화를 진행한다)
3-3. 메모리를 할당하고 해당 블록을 가리키는 포인터를 반환하여 해당 블록을 사용할 수 있게 한다. - 할당할 수 있는 공간이 없어 연결 리스트의 끝인 prologue 블록을 만나게 된다면 힙의 공간을 늘려서 할당한다.
할당 해제 과정
- case 1, 이전과 다음 블록 모두 할당인 경우
해당 블록을 free 시킨 후 연결리스트의 맨 처음에 추가한다. 그리고 추가된 블록의 다음이 원래 연결리스트의 맨 처음이었던 블록과 연결되도록 한다.
- case 2, 다음 블록이 free인 경우
해제 이후 다음 free 블록과 연결시킨다. 동일하게 이 free 블록을 연결리스트의 맨 처음에 넣고 원래 연결리스트의 맨 처음이었던 블록과 연결시킨다.
- case 3, 이전 블록이 free인 경우
해제 이후 이전 free 블록과 연결시킨다. 동일하게 이 free 블록을 연결리스트의 맨처음에 넣고 원래 연결리스트의 맨 처음이었던 블록과 연결시킨다.
- case 4, 이전과 다음 블록이 모두 free인 경우
이전, 현재 해제한, 다음 블록 모두 연결시킨다. 동일하게 이 free 블록을 연결리스트의 맨처음에 넣고 원래 연결리스트의 맨 처음이었던 블록과 연결시킨다.
implicit free list와의 비교
- 전체 블록의 갯수가 아닌, free 블록 갯수에 대해서만 탐색하게 되므로 할당 시간을 줄이게 된다.
- 하지만 연결 리스트 구성을 위해 free 블록에는 2개(2개의 word)의 추가적인 메모리가 필요하다.
소스 코드(first-fit)
/*
* Malloc using explicit free list with first-fit
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
/*********************************************************
* Information of my team
********************************************************/
team_t team = {
/* Team name */
"jungle",
/* First member's full name */
"Shin Seung Jun",
/* First member's email address */
"alohajune22@gmail.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
/* rounds up to the nearest multiple of ALIGNMENT */
// size(변수)보다 크면서 가장 가까운 8의 배수로 만들어주는 것이 Align이다. -> 정렬
// size = 7 : (00000111 + 00000111) & 11111000 = 00001110 & 11111000 = 00001000 = 8
// size = 13 : (00001101 + 00000111) & 11111000 = 00010000 = 16
// 즉 1 ~ 7 바이트 -> 8 바이트
// 8 ~ 16 바이트 -> 16 바이트
// 7 ~ 24 바이트 -> 24 바이트
// 여기서 ~는 not 연산자로, 원래 0x7은 0000 0111이고 ~0x7은 1111 1000이 된다.
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
/* 메모리 할당 시 */
// size_t는 '부호 없는 32비트 정수'로 unsigned int이다. 따라서 4바이트이다.
// 따라서 메모리 할당 시 기본적으로 header와 footer가 필요하므로 더블워드만큼의 메모리가 필요하다. size_t이므로 4바이트이니 ALIGN을 거치면 8바이트가 된다.
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
/* 기본 상수와 매크로 */
#define WSIZE 4 // 워드 사이즈
#define DSIZE 8 // 더블 워드 사이즈
#define MINIMUM 16
#define CHUNKSIZE (1<<12) // 처음 4kB 할당. 초기 free 블록이다.
#define MAX(x, y) ((x) > (y) ? (x) : (y)) // 최댓값을 구하는 함수 매크로
#define PACK(size, alloc) ((size) | (alloc)) // free 리스트에서 header와 footer를 조작하는 데에는, 많은 양의 캐스팅 변환과 포인터 연산이 사용되기에 애초에 매크로로 만든다.
// size 와 alloc을 or 비트 연산시킨다.
// 애초에 size의 오른쪽 3자리는 000으로 비어져 있다.
// 왜? -> 메모리가 더블 워드 크기로 정렬되어 있다고 전제하기 때문이다. 따라서 size는 무조건 8바이트보다 큰 셈이다.
/* 포인터 p가 가르키는 워드의 값을 읽거나, p가 가르키는 워드에 값을 적는 매크로 */
#define GET(p) (*(unsigned int *)(p)) // 보통 p는 void 포인터라고 한다면 곧바로 *p(* 자체가 역참조)를 써서 참조할 수 없기 때문에, 그리고 우리는 4바이트(1워드)씩 주소 연산을 한다고 전제하기에 unsigned int로 캐스팅 변환을 한다. p가 가르키는 곳의 값을 불러온다.
#define PUT(p, val) (*(unsigned int *)(p) = (val)) // p가 가르키는 곳에 val를 넣는다.
/* header 혹은 footer의 값인 size or allocated 여부를 가져오는 매크로 */
#define GET_SIZE(p) (GET(p) & ~0x7) // 블록의 사이즈만 가지고 온다. ex. 1011 0111 & 1111 1000 = 1011 0000으로 사이즈만 읽어옴을 알 수 있다.
#define GET_ALLOC(p) (GET(p) & 0x1) // 블록이 할당되었는지 free인지를 나타내는 flag를 읽어온다. ex. 1011 0111 & 0000 0001 = 0000 0001로 allocated임을 알 수 있다.
/* 블록 포인터 bp(payload를 가르키고 있는 포인터)를 바탕으로 블록의 header와 footer의 주소를 반환하는 매크로 */
#define HDRP(bp) ((char *)(bp) - WSIZE) // header는 payload보다 앞에 있으므로 4바이트(워드)만큼 빼줘서 앞으로 1칸 전진하게 한다.
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // footer는 payload에서 블록의 크기만큼 뒤로 간 다음 8바이트(더블 워드)만큼 빼줘서 앞으로 2칸 전진하게 해주면 footer가 나온다.
// 이 때 포인터는 char형이어야 4 혹은 8바이트, 즉 정확히 1바이트씩 움직일 수 있다. 만약 int형으로 캐스팅 해주면 - WSIZE 했을 때 16바이트 만큼 움직일 수도 있다.
/* 블록 포인터 bp를 바탕으로, 이전과 다음 블록의 payload를 가르키는 주소를 반환하는 매크로 */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) // 지금 블록의 payload를 가르키는 bp에, 지금 블록의 header 사이즈를 읽어서 더하면(word 만큼) 다음 블록의 payload를 가르키게 된다.
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) // 지금 블록의 payload를 가르키는 bp에, 이전 블록의 footer 사이즈를 읽어서 뺴면(double word 만큼) 이전 블록의 payload를 가르키게 된다.
/* 블록 포인터 bp가 가리키고 있는 free 블록 안의 prec(predecessor)과 succ(successor)을 반환해주는 매크로 */
// bp가 가리키고 있는 prec 혹은 succ칸에는 또 다른 주소값(포인터)가 담겨져 있다. 따라서 bp는 이중 포인터라고 할 수 있다. 그렇기에 **로 캐스팅해줘야 한다.
// 결국엔 *(bp)인 셈으로 bp가 가리키고 있는 칸의 값이 나오게 되는데, 이 때 주소값이 나오게 된다.(prec 혹은 succ)
#define PREC_FREEP(bp) (*(void**)(bp))
#define SUCC_FREEP(bp) (*(void**)(bp + WSIZE))
/*
* global variable & functions
*/
static char* heap_listp; // 항상 prologue block을 가리키는 정적 전역 변수 설정. static 변수는 함수 내부(지역)에서도 사용이 가능하고 함수 외부(전역)에서도 사용이 가능하다.
static char* free_listp; // free list의 맨 첫 블록을 가리키는 포인터이다.
/* 코드 순서상, implicit declaration of function(warning)을 피하기 위해 미리 선언해주는 부분? */
static void* extend_heap(size_t words);
static void* coalesce(void* bp);
static void* find_fit(size_t asize);
static void place(void* bp, size_t newsize);
int mm_init(void);
void *mm_malloc(size_t size);
void mm_free(void *bp);
void *mm_realloc(void *ptr, size_t size);
/*
* mm_init
*/
int mm_init(void) {
// unused padding, prologue header/prologue footer, prec, succ, epilogue_header 총 6개가 필요하다.
if ((heap_listp = mem_sbrk(6*WSIZE)) == (void*)-1) { // 할당 실패 시 -1을 반환한다.
return -1;
}
PUT(heap_listp, 0); // unused padding
PUT(heap_listp + (1 * WSIZE), PACK(MINIMUM, 1)); // prologue header
PUT(heap_listp + (2 * WSIZE), NULL); // prec
PUT(heap_listp + (3 * WSIZE), NULL); // succ
PUT(heap_listp + (4 * WSIZE), PACK(MINIMUM, 1)); // prologue footer
PUT(heap_listp + (5 * WSIZE), PACK(0, 1)); // epilogue header
free_listp = heap_listp + 2 * WSIZE; // free_listp를 탐색하는 메커니즘이다.
// CHUCKSIZE만큼 힙을 확장해 초기 free 블록을 생성한다. 이 때 CHUCKSIZE는 2^12으로 4kB 정도였다.(4096 bytes)
if (extend_heap(CHUNKSIZE / WSIZE) == NULL) { // 곧바로 extend_heap이 실행된다.
return -1;
}
return 0;
}
/*
* extend_heap - word 단위의 메모리를 인자로 받아 힙을 늘려준다.
*/
static void* extend_heap(size_t words) {
char* bp;
size_t size;
size = (words % 2 == 1) ? (words + 1) * WSIZE : (words) * WSIZE; // words가 홀수로 들어왔다면 짝수로 바꿔준다. 짝수로 들어왔다면 그대로 WSIZE를 곱해준다. ex. 5만큼(5개의 워드 만큼) 확장하라고 하면, 6으로 만들고 24바이트로 만든다.
// 8바이트(2개 워드, 짝수) 정렬을 위해 짝수로 만들어줘야 한다.
if ((long)(bp = mem_sbrk(size)) == -1) { // 변환한 사이즈만큼 메모리 확보에 실패하면 NULL이라는 주소값을 반환해 실패했음을 알린다. bp 자체의 값, 즉 주소값이 32bit이므로 long으로 캐스팅한다.
return NULL; // 그리고 mem_sbrk 함수가 실행되므로 bp는 새로운 메모리의 첫 주소값을 가르키게 된다.
}
// 새 free 블록의 header와 footer를 정해준다. 자연스럽게 전 epilogue 자리에는 새로운 header가 자리 잡게 된다. 그리고 epilogue는 맨 뒤로 보내지게 된다.
PUT(HDRP(bp), PACK(size, 0)); // 새 free 블록의 header로, free 이므로 0을 부여
PUT(FTRP(bp), PACK(size, 0)); // 새 free 블록의 footer로, free 이므로 0을 부여
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // 앞에서 현재 bp(새롭게 늘어난 메모리의 첫 주소 값으로 역시 payload이다)의 header에 값을 부여해주었다. 따라서 이 header의 사이즈 값을 참조해 다음 블록의 payload를 가르킬 수 있고, 이 payload의 직전인 header는 epilogue가 된다.
return coalesce(bp); // 앞 뒤 블록이 free 블록이라면 연결하고 bp를 반환한다.
}
/*
* mm_free - Freeing a block does nothing.
*/
void mm_free(void *bp) {
size_t size = GET_SIZE(HDRP(bp)); // bp가 가리키는 블록의 사이즈만 들고 온다.
// header, footer 둘 다 flag를 0으로 바꿔주면 된다.
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp); // 앞 뒤 블록이 free 블록이라면 연결한다.
}
/*
* coalesce - 이전 혹은 다음 블록이 free이면 연결시키고, 경우에 따라 free 리스트에서 제거하고 새로워진 free 블록을 free 리스트에 추가한다.
*/
static void* coalesce(void* bp) {
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // 이전 블록의 free 여부
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // 다음 블록의 free 여부
size_t size = GET_SIZE(HDRP(bp)); // 현재 블록의 사이즈
// 경우 1. 이전 블록 할당, 다음 블록 할당 - 연결시킬 수 없으니 그대로 bp를 반환한다.
if (prev_alloc && next_alloc) {
putFreeBlock(bp);
return bp;
}
else if (prev_alloc && !next_alloc) {
removeBlock(NEXT_BLKP(bp)); // free 상태였던 다음 블록을 free 리스트에서 제거한다.
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) {
removeBlock(PREV_BLKP(bp)); // free 상태였던 이전 블록을 free 리스트에서 제거한다.
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
bp = PREV_BLKP(bp);
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
}
else {
removeBlock(PREV_BLKP(bp)); // free 상태였던 이전 블록을 free 리스트에서 제거한다.
removeBlock(NEXT_BLKP(bp)); // free 상태였던 다음 블록을 free 리스트에서 제거한다.
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
bp = PREV_BLKP(bp);
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
}
// 연결되어진 새로운 free 블록을 free 리스트에 추가한다.
putFreeBlock(bp);
return bp;
}
/*
* mm_malloc
*/
void *mm_malloc(size_t size) {
size_t asize; // 수정된 블록의 크기
size_t extendsize; // 알맞은 크기의 free 블록이 없을 시 확장하는 사이즈
char *bp;
if (size == 0) {
return NULL; // 가짜 요청은 무시한다.
}
asize = ALIGN(size + SIZE_T_SIZE); // header와 footer를 위한 메모리, 즉 word 2개가 필요하므로 SIZE_T_SIZE만큼의 메모리가 필요하다. 여기에 현재 할당하려는 size를 더하면, header와 footer가 포함되면서 할당하려는 블록의 크기가 된다.
// 적절한 공간을 가진 블록을 찾으면 할당(혹은 분할까지) 진행한다.
// bp는 계속 free 블록을 가리킬 수 있도록 한다.
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
// 적절한 공간을 찾지 못했다면 힙을 늘려주고, 그 늘어난 공간에 할당시켜야 한다.
extendsize = MAX(asize, CHUNKSIZE); // 둘 중 더 큰 값을 선택한다.
if ((bp = extend_heap(extendsize / WSIZE)) == NULL) { // 실패 시 bp로는 NULL을 반환한다.
return NULL;
}
// 힙을 늘리는 데에 성공했다면, 그 늘어난 공간에 할당시킨다.
place(bp, asize);
return bp;
}
/*
* find_fit - first-fit, free 리스트의 맨 처음부터 탐색하여 요구하는 메모리 공간보다 큰 free 블록의 주소를 반환한다.
*/
static void* find_fit(size_t asize) {
void* bp;
// free 리스트의 맨 마지막은 할당되어진 prologue 블록(정확히는 payload를 가리키는, free 블록이었으면 prev이었을 워드를 가리키고 있다)이다.
for (bp = free_listp; GET_ALLOC(HDRP(bp)) != 1; bp = SUCC_FREEP(bp)) {
if (asize <= GET_SIZE(HDRP(bp))) {
return bp;
}
}
return NULL;
}
/*
* place - 요구 메모리를 할당할 수 있는 가용 블록을 할당한다.(즉 실제로 할당하는 부분이다) 이 때 분할이 가능하다면 분할한다.
*/
static void place(void* bp, size_t asize) {
size_t csize = GET_SIZE(HDRP(bp)); // 현재 할당할 수 있는 후보, 즉 실제로 할당할 free 블록의 사이즈
// 해당 블록을 할당해야 하므로 free 리스트에서 제거한다.
removeBlock(bp);
// 분할이 가능한 경우
// 할당하고 남은 메모리가 free 블록을 만들 수 있는 4개의 word가 되느냐
// header/footer/prec/next가 필요하니 최소 4개의 word는 필요하다.
if ((csize - asize) >= (2 * DSIZE)) {
// 앞의 블록은 할당시킨다.
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
// 뒤의 블록은 free시킨다.
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(csize - asize, 0));
PUT(FTRP(bp), PACK(csize - asize, 0));
// free 리스트의 첫 번째에 분할된, 즉 새롭게 수정된 free 블록이 추가된다.
putFreeBlock(bp);
// 분할이 불가능한 경우
// csize - asize가 2 * DSIZE보다 작다는 것은 할당되고 남은 공간에 header/footer/prec/next가 들어갈 자리가 충분치 않음을 의미한다. 최소한의 크기를 가지는 free 블록을 만들 수 없으므로 어쩔 수 없이 주소 정렬을 위해 내부 단편화를 진행한다.
} else {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
/*
* removeBlock - 할당되거나, 이전 혹은 다음 블록과 연결되어지는 free 블록은 free 리스트에서 제거해야 한다.
*/
void removeBlock(void *bp) {
// free 리스트의 첫 번째 블록을 없앨 때
// ex. (참고로 PREC, SUCC word 안에는 주소값, 즉 포인터가 들어있다는 것을 유심해야 한다.)
// 0x72 <-> 0x24 <-> 0x08 맨 처음, bp(free_listp)가 0x72를 가리키고 있다고 가정.
// 0x72 -> 0x24 <-> 0x08 PREC_FREEP(SUCC_FREEP(bp)) = NULL;
// 0x24 <-> 0x08 free_listp는 0x24가 되면 앞의 0x72는 이제 완전히 날라가게 된다.
if (bp == free_listp) { // bp가 free_listp라는 말은 free 리스트의 처음이라는 뜻이다.
PREC_FREEP(SUCC_FREEP(bp)) = NULL; // bp가 가리키는 free 블록의 바로 다음 블록에서 이전 블록을 잇는 prec 블록의 값을 NULL로 수정하면 끊어지게 된다.
free_listp = SUCC_FREEP(bp); // bp가 가리키는 free 블록의 바로 다음 블록이 free_listp, 즉 free 리스트의 맨 처음이 되도록 한다.
// bp가 free 리스트의 맨 처음을 가리키는 것이 아니라, free 리스트 안의 블록을 가리키고 있을 때, 해당 블록을 없앴다고 가정하고 (free 리스트 안에서) 앞 뒤의 블록을 이어주면 된다.
// ex. (참고로 PREC, SUCC word 안에는 주소값, 즉 포인터가 들어있다는 것을 유심해야 한다.)
// 0x72 <-> 0x24 <-> 0x08 bp가 free_listp가 아닌 0x24를 가리키고 있다고 가정.
// 0x72 -> 0x08 SUCC_FREEP(PREC_FREEP(bp)) = SUCC_FREEP(bp);
// 0x72 <-> 0x08 PREC_FREEP(SUCC_FREEP(bp)) = PREC_FREEP(bp);
} else {
SUCC_FREEP(PREC_FREEP(bp)) = SUCC_FREEP(bp);
PREC_FREEP(SUCC_FREEP(bp)) = PREC_FREEP(bp);
}
}
/*
* putFreeBlock - free 되거나, 연결되어 새롭게 수정된 free 블록을 free 리스트의 맨 처음에 넣는다.
*/
void putFreeBlock(void* bp) {
SUCC_FREEP(bp) = free_listp; // 이제 bp 블록의 다음은 free_listp가 되게 된다.
PREC_FREEP(bp) = NULL; // free 리스트의 맨 처음 블록의 이전 블록은 당연히 NULL이어야 한다.
PREC_FREEP(free_listp) = bp; // free_listp, 즉 bp의 다음 블록의 이전(PREC)이 bp를 향하도록 한다. free_listp가 밀려난 셈이니까.
free_listp = bp; // 이제 free 리스트의 맨 처음을 가리키는 포인터인 free_listp를 bp로 바꿔준다. 이제 bp는 완벽히 free 리스트의 맨 처음이 되었다.
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size) {
// 블록의 크기를 줄이는 것이면 줄이려는 size만큼으로 줄인다.
// 블록의 크기를 늘리는 것이면
// 핵심은, 이미 할당된 블록의 사이즈를 직접 건드리는 것이 아니라, 요청한 사이즈 만큼의 블록을 새로 메모리 공간에 만들고 현재의 블록을 반환하는 것이다.
// 해당 블록의 사이즈가 이 정도로 변경되었으면 좋겠다는 것이 size,
void *oldptr = ptr; // 크기를 조절하고 싶은 힙의 시작 포인터
void *newptr; // 크기 조절 뒤의 새 힙의 시작 포인터
size_t copySize; // 복사할 힙의 크기
newptr = mm_malloc(size); // place를 통해 header, footer가 배정된다.
if (newptr == NULL) {
return NULL;
}
copySize = GET_SIZE(HDRP(oldptr)); // 원래 블록의 사이즈
if (size < copySize) { // 만약 블록의 크기를 줄이는 것이라면 size만큼으로 줄이면 된다. copySize - size 공간의 데이터는 잘리게 된다. 밑의 memcpy에서 잘린 만큼의 데이터는 복사되지 않는다.
copySize = size;
}
memcpy(newptr, oldptr, copySize); // oldptr부터 copySize까지의 데이터를, newptr부터 심겠다.
mm_free(oldptr); // 기존 oldptr은 반환한다.
return newptr;
}Method 3: Segregated Free List
seg-list 방법은 free 블록들을 사이즈 별로 모아, 해당 사이즈가 속할 수 있는 구간의 연결리스트에 관리하는 방법이다. 따라서 연결리스트를 사용하는 explicit 방법에서 개선된 방법이라고 생각하면 된다.
사이즈 별로 연결리스트를 만들어야 하기에 여러 개의 연결리스트가 필요하며 이 말은 여러 개의 연결리스트 포인터가 존재한다는 의미이다.(당연히 이 포인터 또한 힙에 저장되어 있을 것이다) 특정한 사이즈의, 이를 테면 37사이즈만큼의 메모리를 할당하고자 하면 위 그림에서 32 ~ 64 사이즈 연결리스트를 선택하게 되고 해당 연결리스트에서 적절한 free 블록을 찾게 된다. 위와 같이 대부분의 seg-list에서 연결리스트 사이즈는 2의 제곱수를 기준으로 한다.
하나의 연결리스트에서 적절한 사이즈의 free 블록을 찾아야 하는 explicit과는 다르게, 사이즈 별로 연결리스트가 나눠져 있기 때문에 적절한 free 블록을 찾는 시간을 훨씬 줄일 수 있다. 유사한 사이즈의 연결리스트로 바로 가서 찾으면 되기 때문에 탐색 범위가 훨씬 줄어들기 때문이다. 따라서 앞서 설명한 implicit, explicit과 비교했을 때 성능이 가장 좋다.
해당 연결리스트에서 적절한 사이즈의 블록을 찾지 못했다면, 다음 크기의 연결리스트로 넘어가 찾게 된다. 이렇게 연결리스트 간의 탐색을 제외하고는, 연결리스트를 사용하는 개념은 explicit과 비슷하기에 explicit과 동작이 유사하다.
소스 코드(first-fit)
/*
* Malloc using segregated free list with first-fit
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
/*********************************************************
* Information of my team
********************************************************/
team_t team = {
/* Team name */
"jungle",
/* First member's full name */
"Shin Seung Jun",
/* First member's email address */
"alohajune22@gmail.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
/* rounds up to the nearest multiple of ALIGNMENT */
// size(변수)보다 크면서 가장 가까운 8의 배수로 만들어주는 것이 Align이다. -> 정렬
// size = 7 : (00000111 + 00000111) & 11111000 = 00001110 & 11111000 = 00001000 = 8
// size = 13 : (00001101 + 00000111) & 11111000 = 00010000 = 16
// 즉 1 ~ 7 바이트 -> 8 바이트
// 8 ~ 16 바이트 -> 16 바이트
// 7 ~ 24 바이트 -> 24 바이트
// 여기서 ~는 not 연산자로, 원래 0x7은 0000 0111이고 ~0x7은 1111 1000이 된다.
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
/* 메모리 할당 시 */
// size_t는 '부호 없는 32비트 정수'로 unsigned int이다. 따라서 4바이트이다.
// 따라서 메모리 할당 시 기본적으로 header와 footer가 필요하므로 더블워드만큼의 메모리가 필요하다. size_t이므로 4바이트이니 ALIGN을 거치면 8바이트가 된다.
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
/* 기본 상수와 매크로 */
#define WSIZE 4 // 워드 사이즈
#define DSIZE 8 // 더블 워드 사이즈
#define CHUNKSIZE (1<<12) // 처음 4kB 할당. 초기 free 블록이다.
#define LISTLIMIT 20
#define MAX(x, y) ((x) > (y) ? (x) : (y)) // 최댓값을 구하는 함수 매크로
#define PACK(size, alloc) ((size) | (alloc)) // free 리스트에서 header와 footer를 조작하는 데에는, 많은 양의 캐스팅 변환과 포인터 연산이 사용되기에 애초에 매크로로 만든다.
// size 와 alloc을 or 비트 연산시킨다.
// 애초에 size의 오른쪽 3자리는 000으로 비어져 있다.
// 왜? -> 메모리가 더블 워드 크기로 정렬되어 있다고 전제하기 때문이다. 따라서 size는 무조건 8바이트보다 큰 셈이다.
/* 포인터 p가 가르키는 워드의 값을 읽거나, p가 가르키는 워드에 값을 적는 매크로 */
#define GET(p) (*(unsigned int *)(p)) // 보통 p는 void 포인터라고 한다면 곧바로 *p(* 자체가 역참조)를 써서 참조할 수 없기 때문에, 그리고 우리는 4바이트(1워드)씩 주소 연산을 한다고 전제하기에 unsigned int로 캐스팅 변환을 한다. p가 가르키는 곳의 값을 불러온다.
#define PUT(p, val) (*(unsigned int *)(p) = (val)) // p가 가르키는 곳에 val를 넣는다.
/* header 혹은 footer의 값인 size or allocated 여부를 가져오는 매크로 */
#define GET_SIZE(p) (GET(p) & ~0x7) // 블록의 사이즈만 가지고 온다. ex. 1011 0111 & 1111 1000 = 1011 0000으로 사이즈만 읽어옴을 알 수 있다.
#define GET_ALLOC(p) (GET(p) & 0x1) // 블록이 할당되었는지 free인지를 나타내는 flag를 읽어온다. ex. 1011 0111 & 0000 0001 = 0000 0001로 allocated임을 알 수 있다.
/* 블록 포인터 bp(payload를 가르키고 있는 포인터)를 바탕으로 블록의 header와 footer의 주소를 반환하는 매크로 */
#define HDRP(bp) ((char *)(bp) - WSIZE) // header는 payload보다 앞에 있으므로 4바이트(워드)만큼 빼줘서 앞으로 1칸 전진하게 한다.
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // footer는 payload에서 블록의 크기만큼 뒤로 간 다음 8바이트(더블 워드)만큼 빼줘서 앞으로 2칸 전진하게 해주면 footer가 나온다.
// 이 때 포인터는 char형이어야 4 혹은 8바이트, 즉 정확히 1바이트씩 움직일 수 있다. 만약 int형으로 캐스팅 해주면 - WSIZE 했을 때 16바이트 만큼 움직일 수도 있다.
/* 블록 포인터 bp를 바탕으로, 이전과 다음 블록의 payload를 가르키는 주소를 반환하는 매크로 */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) // 지금 블록의 payload를 가르키는 bp에, 지금 블록의 header 사이즈를 읽어서 더하면(word 만큼) 다음 블록의 payload를 가르키게 된다.
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) // 지금 블록의 payload를 가르키는 bp에, 이전 블록의 footer 사이즈를 읽어서 뺴면(double word 만큼) 이전 블록의 payload를 가르키게 된다.
/* 블록 포인터 bp가 가리키고 있는 free 블록 안의 prec(predecessor)과 succ(successor)을 반환해주는 매크로 */
// bp가 가리키고 있는 prec 혹은 succ칸에는 또 다른 주소값(포인터)가 담겨져 있다. 따라서 bp는 이중 포인터라고 할 수 있다. 그렇기에 **로 캐스팅해줘야 한다.
// 결국엔 *(bp)인 셈으로 bp가 가리키고 있는 칸의 값이 나오게 되는데, 이 때 주소값이 나오게 된다.(prec 혹은 succ)
#define PRED_FREE(bp) (*(void**)(bp))
#define SUCC_FREE(bp) (*(void**)(bp + WSIZE))
/*
* global variable & functions
*/
static void* heap_listp;
static void* segregation_list[LISTLIMIT];
static void* extend_heap(size_t words);
static void* coalesce(void *bp);
static void* find_fit(size_t asize);
static void place(void* bp, size_t asize);
static void remove_block(void *bp);
static void insert_block(void *bp, size_t size);
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void) {
int list;
// seglist의 포인터 모두 NULL로 초기화시킨다.
for (list = 0; list < LISTLIMIT; list++) {
segregation_list[list] = NULL;
}
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1) // memlib.c를 살펴보면 할당 실패시 (void *)-1을 반환하고 있다. 정상 포인터를 반환하는 것과는 달리, 오류 시 이와 구분 짓기 위해 mem_sbrk는 (void *)-1을 반환하고 있다.
return -1; // 할당에 실패하면 -1을 리턴한다.
PUT(heap_listp, 0); // Alignment padding으로 unused word이다. 맨 처음 메모리를 8바이트 정렬(더블 워드)을 위해 사용하는 미사용 패딩이다.
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); // prologue header로, 맨 처음에서 4바이트 뒤에 header가 온다. 이 header에 사이즈(프롤로그는 8바이트)와 allocated 1(프롤로그는 사용하지 말라는 의미)을 통합한 값을 부여한다.
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); // prologue footer로, 값은 header와 동일해야 한다.
PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); // epilogue header
heap_listp += (2 * WSIZE); // heap_listp는 prologue footer를 가르키도록 만든다.
// CHUCKSIZE만큼 힙을 확장해 초기 free 블록을 생성한다. 이 때 CHUCKSIZE는 2^12으로 4kB 정도였다.(4096 bytes)
if (extend_heap(CHUNKSIZE / WSIZE) == NULL) { // 곧바로 extend_heap이 실행된다.
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; // 알맞은 크기의 free 블록이 없을 시 확장하는 사이즈
char *bp;
if (size == 0) {
return NULL; // 가짜 요청은 무시한다.
}
asize = ALIGN(size + SIZE_T_SIZE); // header와 footer를 위한 메모리, 즉 word 2개가 필요하므로 SIZE_T_SIZE만큼의 메모리가 필요하다. 여기에 현재 할당하려는 size를 더하면, header와 footer가 포함되면서 할당하려는 블록의 크기가 된다.
// 적절한 공간을 가진 블록을 찾으면 할당(혹은 분할까지) 진행한다.
// bp는 계속 free 블록을 가리킬 수 있도록 한다.
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
// 적절한 공간을 찾지 못했다면 힙을 늘려주고, 그 늘어난 공간에 할당시켜야 한다.
extendsize = MAX(asize, CHUNKSIZE); // 둘 중 더 큰 값을 선택한다.
if ((bp = extend_heap(extendsize / WSIZE)) == NULL) { // 실패 시 bp로는 NULL을 반환한다.
return NULL;
}
// 힙을 늘리는 데에 성공했다면, 그 늘어난 공간에 할당시킨다.
place(bp, asize);
return bp;
}
/*
* mm_free - Freeing a block does nothing.
*/
void mm_free(void *bp) {
size_t size = GET_SIZE(HDRP(bp)); // bp가 가리키는 블록의 사이즈만 들고 온다.
// header, footer 둘 다 flag를 0으로 바꿔주면 된다.
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp); // 앞 뒤 블록이 free 블록이라면 연결한다.
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size) {
// 블록의 크기를 줄이는 것이면 줄이려는 size만큼으로 줄인다.
// 블록의 크기를 늘리는 것이면
// 핵심은, 이미 할당된 블록의 사이즈를 직접 건드리는 것이 아니라, 요청한 사이즈 만큼의 블록을 새로 메모리 공간에 만들고 현재의 블록을 반환하는 것이다.
// 해당 블록의 사이즈가 이 정도로 변경되었으면 좋겠다는 것이 size,
void *oldptr = ptr; // 크기를 조절하고 싶은 힙의 시작 포인터
void *newptr; // 크기 조절 뒤의 새 힙의 시작 포인터
size_t copySize; // 복사할 힙의 크기
newptr = mm_malloc(size); // place를 통해 header, footer가 배정된다.
if (newptr == NULL) {
return NULL;
}
copySize = GET_SIZE(HDRP(oldptr)); // 원래 블록의 사이즈
if (size < copySize) { // 만약 블록의 크기를 줄이는 것이라면 size만큼으로 줄이면 된다. copySize - size 공간의 데이터는 잘리게 된다. 밑의 memcpy에서 잘린 만큼의 데이터는 복사되지 않는다.
copySize = size;
}
memcpy(newptr, oldptr, copySize); // oldptr부터 copySize까지의 데이터를, newptr부터 심겠다.
mm_free(oldptr); // 기존 oldptr은 반환한다.
return newptr;
}
/*
* extend_heap - word 단위의 메모리를 인자로 받아 힙을 늘려준다.
*/
static void* extend_heap(size_t words) {
char* bp;
size_t size;
size = (words % 2 == 1) ? (words + 1) * WSIZE : (words) * WSIZE; // words가 홀수로 들어왔다면 짝수로 바꿔준다. 짝수로 들어왔다면 그대로 WSIZE를 곱해준다. ex. 5만큼(5개의 워드 만큼) 확장하라고 하면, 6으로 만들고 24바이트로 만든다.
// 8바이트(2개 워드, 짝수) 정렬을 위해 짝수로 만들어줘야 한다.
if ((long)(bp = mem_sbrk(size)) == -1) { // 변환한 사이즈만큼 메모리 확보에 실패하면 NULL이라는 주소값을 반환해 실패했음을 알린다. bp 자체의 값, 즉 주소값이 32bit이므로 long으로 캐스팅한다.
return NULL; // 그리고 mem_sbrk 함수가 실행되므로 bp는 새로운 메모리의 첫 주소값을 가르키게 된다.
}
// 새 free 블록의 header와 footer를 정해준다. 자연스럽게 전 epilogue 자리에는 새로운 header가 자리 잡게 된다. 그리고 epilogue는 맨 뒤로 보내지게 된다.
PUT(HDRP(bp), PACK(size, 0)); // 새 free 블록의 header로, free 이므로 0을 부여
PUT(FTRP(bp), PACK(size, 0)); // 새 free 블록의 footer로, free 이므로 0을 부여
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // 앞에서 현재 bp(새롭게 늘어난 메모리의 첫 주소 값으로 역시 payload이다)의 header에 값을 부여해주었다. 따라서 이 header의 사이즈 값을 참조해 다음 블록의 payload를 가르킬 수 있고, 이 payload의 직전인 header는 epilogue가 된다.
return coalesce(bp); // 앞 뒤 블록이 free 블록이라면 연결하고 bp를 반환한다.
}
/*
* coalesce - 앞 혹은 뒤 블록이 free 블록이고, 현재 블록도 free 블록이라면 연결시키고 연결된 free 블록의 주소를 반환한다.
*/
static void *coalesce(void *bp) {
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // 이전 블록의 free 여부
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // 다음 블록의 free 여부
size_t size = GET_SIZE(HDRP(bp)); // 현재 블록의 사이즈
// 경우 1. 이전 블록 할당, 다음 블록 할당 - 연결시킬 수 없으니 그대로 bp를 반환한다.
// 해당 블록을 seglist에서 적절한 연결리스트를 찾아 넣는다.
if (prev_alloc && next_alloc) {
insert_block(bp, size);
return bp;
}
else if (prev_alloc && !next_alloc) {
remove_block(NEXT_BLKP(bp)); // free 상태였던 다음 블록을 free 리스트에서 제거한다.
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) {
remove_block(PREV_BLKP(bp)); // free 상태였던 이전 블록을 free 리스트에서 제거한다.
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 if (!prev_alloc && !next_alloc) {
remove_block(PREV_BLKP(bp)); // free 상태였던 이전 블록을 free 리스트에서 제거한다.
remove_block(NEXT_BLKP(bp)); // free 상태였던 다음 블록을 free 리스트에서 제거한다.
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);
}
// seglist에서 현재 넣으려는 블록이 속하는 사이즈의 연결리스트를 찾아 수정된 free 블록을 추가한다.
insert_block(bp, size);
return bp;
}
/*
* place - 요구 메모리를 할당할 수 있는 가용 블록을 할당한다.(즉 실제로 할당하는 부분이다) 이 때 분할이 가능하다면 분할한다.
*/
static void place(void *bp, size_t asize) {
size_t csize = GET_SIZE(HDRP(bp)); // 현재 할당할 수 있는 후보, 즉 실제로 할당할 free 블록의 사이즈
// 할당하는 블록인 bp는 seglist에서 속한 연결리스트로부터 제거한다.
remove_block(bp);
// 분할이 가능한 경우
// 할당하고 남은 메모리가 free 블록을 만들 수 있는 4개의 word가 되느냐
// header/footer/prec/next가 필요하니 최소 4개의 word는 필요하다.
if ((csize - asize) >= (2 * DSIZE)) {
// 앞의 블록은 할당시킨다.
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
// 뒤의 블록은 free시킨다.
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(csize - asize, 0));
PUT(FTRP(bp), PACK(csize - asize, 0));
coalesce(bp); // 뒤의 블록의 뒤의 블록이 free일 수 있으므로 연결을 실행한다.
}
// 분할이 불가능한 경우
// csize - asize가 2 * DSIZE보다 작다는 것은 할당되고 남은 공간에 header/footer/prec/next가 들어갈 자리가 충분치 않음을 의미한다. 최소한의 크기를 가지는 free 블록을 만들 수 없으므로 어쩔 수 없이 주소 정렬을 위해 내부 단편화를 진행한다.
else {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
/*
* find_fit - first-fit, 해당 블록의 사이즈가 속할 수 있는 사이즈 범위를 가진 연결리스트를 탐색하고, 그 연결리스트 내에서 적절한 블록을 또 탐색한다.
*/
static void *find_fit(size_t asize) {
void* bp;
int list = 0;
size_t searchsize = asize;
while (list < LISTLIMIT) {
// bp가 19번째(0부터 시작했으니 19번째는 마지막 연결리스트이다) 연결리스트에 도달하거나, 이는 끝 지점에 도달했다는 것이다.
// 혹은 searchsize가 1이하가 되면(여기서는 찾았다는 의미이다. asize를 4로 가정하고 밑의 비트연산과 list++을 해보면 알 수 있다.) 해당 사이즈의 연결리스트가 존재할 때 연결리스트로 들어가서 적절한 free 블록을 찾게 된다.
if ((list == LISTLIMIT - 1) || (searchsize <= 1) && (segregation_list[list] != NULL)) {
bp = segregation_list[list];
while ((bp != NULL) && (asize > GET_SIZE(HDRP(bp)))) {
bp = SUCC_FREE(bp);
}
if (bp != NULL) {
return bp;
}
}
searchsize >>= 1; // seachsize를 2로 나눠가면서(shift 비트연산을 하면서) while문에서 적절한 사이즈를 가진 연결리스트를 찾도록 해준다.
list++;
}
return NULL;
}
/*
* remove_block -
*/
static void remove_block(void *bp) {
int list = 0;
size_t size = GET_SIZE(HDRP(bp));
// 지우고자 하는 블록의 사이즈가 속할 수 있는 사이즈 범위를 가진 연결 리스트를 찾는다.
while ((list < LISTLIMIT - 1) && (size > 1)) {
size >>= 1;
list++;
}
if (SUCC_FREE(bp) != NULL) { // 다음 블록이 존재한다면
if (PRED_FREE(bp) != NULL) { // 이전 블록도 존재한다면
PRED_FREE(SUCC_FREE(bp)) = PRED_FREE(bp); // 중간 블록을 없애는 작업을 진행한다.
SUCC_FREE(PRED_FREE(bp)) = SUCC_FREE(bp); // 다음 블록의 PRED(앞으로 향하는), 이전 블록의 SUCC(뒤로 향하는)를 각각 현재 블록의 이전 블록을, 현재 블록의 다음 블록을 향하도록 하여 중간 블록을 생략하도록 만든다.
} else {
PRED_FREE(SUCC_FREE(bp)) = NULL; // 다음 블록이 존재하고 이전 블록이 존재하지 않는다면 이는 연결리스트의 맨 처음이라는 뜻이 된다. 다음 블록의 PRED(앞으로 향하는)를 NULL로 바꿔주면 자연스럽게 연결리스트의 맨 앞 블록이 생략되는 셈이다.
segregation_list[list] = SUCC_FREE(bp);
}
} else {
if (PRED_FREE(bp) != NULL) { // 다음 블록이 존재하지 않고, 이전 블록이 존재한다면 이는 현재 블록이 연결리스트의 맨 마지막 블록임을 뜻한다.
SUCC_FREE(PRED_FREE(bp)) = NULL; // 이전 블록의 다음이 NULL을 향하게 하여 현재 블록을 생략하게 만들면 된다.
} else {
segregation_list[list] = NULL; // 다음 블록이 존재하지 않고, 이전 블록 또한 존재하지 않는다면 현재 블록 밖에 없다는 뜻이다. 그냥 연결리스트의 맨 처음을 NULL로 만들면 모두 무시되는 셈이다.
}
}
return;
}
static void insert_block(void *bp, size_t size) {
int list = 0;
void *search_ptr; // 블록들을 탐색하는 포인터
void *insert_ptr = NULL; // search_ptr의 바로 앞 탐색 포인터(실제로 삽입할 곳을 가리키게 되는 포인터)
// 추가하고자 하는 블록의 사이즈가 속할 수 있는 사이즈 범위를 가진 연결 리스트를 찾는다.
while ((list < LISTLIMIT - 1) && (size > 1)) {
size >>= 1;
list++;
}
// 적절한 사이즈 범위를 가진 연결리스트에서 적절한 곳에 넣을 수 있는 블록을 탐색하는 과정이다.
// 오름차순으로 저장하기 위해, 나보다 작은 블록은 넘기고 큰 블록을 만났을 때 멈추게 된다. 따라서 실제로 삽입하게 되는 곳은 insert_ptr이 가리키는 곳이다.
search_ptr = segregation_list[list];
while ((search_ptr != NULL) && (size > GET_SIZE(HDRP(search_ptr)))) { // 더 큰 사이즈의 free 블록을 만나면 멈춘다.
insert_ptr = search_ptr;
search_ptr = SUCC_FREE(search_ptr);
}
// search_ptr이 더 큰 블록이고, insert_ptr은 바로 그 전의 블록을 가리키는 포인터인 상태로 탐색이 끝나게 된다.
if (search_ptr != NULL) { // 더 큰 블록이 존재하고
if (insert_ptr != NULL) { // 현재 가리키는 블록도 존재한다면 bp를 중간에 끼워 넣어야 한다.
SUCC_FREE(bp) = search_ptr;
PRED_FREE(bp) = insert_ptr;
PRED_FREE(search_ptr) = bp;
SUCC_FREE(insert_ptr) = bp;
} else { // 더 큰 블록이 존재하고 현재 가리키는 블록이 존재하지 않는다면(이전 블록이 없다면) 이는 연결리스트의 맨처음임을 말한다.
SUCC_FREE(bp) = search_ptr;
PRED_FREE(bp) = NULL;
PRED_FREE(search_ptr) = bp;
segregation_list[list] = bp; // 따라서 bp를 연결리스트의 맨 처음에 삽입하면 된다.
}
} else { // 더 큰 블록이 존재하지 않고,
if (insert_ptr != NULL) { // 이전 블록이 존재한다면
SUCC_FREE(bp) = NULL; // 이는 맨 끝 블록임을 말한다.
PRED_FREE(bp) = insert_ptr;
SUCC_FREE(insert_ptr) = bp;
} else { // 더 큰 블록이 존재하지 않고, 이전 블록도 존재하지 않는다면
SUCC_FREE(bp) = NULL; // 추가하려는 블록은 연결리스트의 맨 처음이 된다.
PRED_FREE(bp) = NULL;
segregation_list[list] = bp;
}
}
return;
}참고한 블로그 및 Github, 서적
- CS 그림으로 알아보는 메모리 동적할당
- dkkim0122님 Github
- seglist
- sunset-asparagus님 Notion
- CSAPP 9.9장 이후
- 메모리 할당기에 대한 각각의 소스 코드는 저의 Github에서도 보실 수 있습니다.
메타몽 닮음 :) email: alohajune22@gmail.com