이 글은 C언어로 만드는 malloc lab 구현 글입니다.
동적 메모리 할당기를 만드는 이유
어떤 프로그램을 구현할 때 그 프로그램을 왜 만드는지 모른다면 제대로 구현하기 힘들다. malloc lab 프로젝트의 경우에도 내가 malloc lab을 처음 만드는 사람이라고 생각하고 진행하였다.
상황 : 프로그래머들은 실제 프로그램이 들어올 때 어떤 크기가 들어올지 알 수가 없다.
만약 malloc이라는 게 없다면, 배열을 정해진 최대 배열 크기를 갖는 정적 배열로 정의할 것이다. 일단 크게 만들어놓으면 프로그램이 터질 일은 줄어들기 때문이다.
작은 프로그램에서는 저 방법이 크게 문제가 되지 않을 수 있다. 그러나 코드 길이가 수백만 줄이고 사용자가 많은 규모의 소프트웨어라면 정적배열 선언은 관리가 어려워진다.
그 어려움을 해결하려면 런타임시 메모리에 데이터를 동적으로 할당하는 것이다. 이렇게 되면 메모리의 최대 크기는 사용가능한 가상메모리의 양에 의해서만 제한된다. 좀 더 유연한 구조가 되는 것이다.
동적 메모리 할당기 만들기
앞으로 프로그램은 할당기라고 부를 것이다.
할당기를 만들기 전 먼저, 할당기가 아래와 같이 크게 2종류 있다는 것을 알아놓자.
참고 : 여기서 블록은 힙 내의 데이터를 넣는 구역을 의미한다. 밑에서 더 자세하게 다룰 것이니 일단은 데이터를 넣는 하나의 단위라고 생각하자.
-
명시적 할당기 : 애플리케이션이 명시적으로 할당된 블록을 반환해줄 것을 요구함.
- C에서는 malloc 함수를 호출해서 블록을 할당, free 함수를 호출해서 블록을 반환.
-
묵시적 할당기 : 언제 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고, 언제 블록을 반환하는지를 할당기가 검출할 수 있어야 함.
- 자바에서는 garbage collector라는 개념이 있으며, 자동으로 사용하지 않은 할당된 블록을 반환시켜주는 작업을 함. (가비지 콜렉션)
참고로 이 글에선 명시적 할당기만 다룰 것이다.
명시적 할당기의 조건은 다음과 같다.
- 임의의 요청 순서 처리 : 가용할 수 있는 블록이 할당 요청에 의해 할당되어야 함. 아무 순서로 할당과 반환요청을 할 수 있어야 함.
- 요청에 즉시 응답 & 블록 정렬 : 할당기는 블록들이 어떤 종류의 데이터 객체라도 저장할 수 있고 정렬해야 함.
- 힙만 사용 : 할당기가 사용하는 비확장적인 자료 구조는 힙 자체에 저장되어야 함.
- 할당된 블록을 수정하지 않기 : 일단 블록이 할당되면 임의로 이들을 수정하거나 이동하지 않음.
또한 메모리는 (가상메모리라도) 무한하지 않다. 결국 한정된 디스크 크기에 기반하기 때문에 우리는 무조건적으로 할당기를 통해 할당만 할 수는 없다. 할당과 해제를 적절히 처리해줘야하는 것이다. 그러므로 할당기는 가용한 힙에 가능한 많은 데이터를 넣기 위해 적절한 균형을 찾아야 한다.
malloc 구현
그럼 이제 본격적으로 malloc 프로그램을 다뤄보자. 우리는 아래의 사항을 유의하면서 구현해야 한다.
malloc 프로그램의 구현 시 유의해야 할 점
- 힙 영역을 늘릴 수 있어야 함.
- 가용 블록 여부를 파악할 수 있어야 함.
- 새롭게 할당하기 위해 적절한 가용블록을 선택할 수 있어야 함.
- 블록을 할당한 후 남는 부분들을 처리해야 함.
- 할당이 해제된 블록을 적절하게 합쳐야 함.
즉, malloc 프로그램에는 힙 영역 늘리기, 가용 블록 여부 파악해서 가용블록 선택하기, 블록의 남는 부분 처리하기, 블록 합치기, 블록 할당 해제하기 등의 기능이 들어가야 한다.
위의 기능을 구현하기 위해선 정보가 필요하다. 대부분의 할당기는 정보를 블록 내에 저장한다. 블록 한 개에는 아래의 정보들이 들어간다.
- 헤더 : 블록 크기와 블록 할당 여부를 담는다.
- 데이터 : 담아야 할 데이터를 담는 부분(payload라고도 부른다.)
- 여백(패딩) : 외부 단편화를 극복하기 위한 전략의 일부분으로 사용할 수도 있고, 정렬 요구사항을 만족하기 위해 필요.
보통 하나의 블록은 4바이트나 8바이트로 구성하는데, 그걸 부르는 단위를 word라고 부른다. 따라서 1워드는 4바이트이고, 더블 워드가 될 경우 8바이트가 된다. 블록 크기는 대개 4의 배수 혹은 8의 배수로 구분된다.
위 그림을 잘 이해해야 코드 구현하기 쉬워지니 한번 이해해보자.
-
첫 층은 블록의 헤더로서 블록 크기와 가용 여부를 나타낼 것이다. 가용 여부는 3자리 비트로 이루어진다. 마지막 비트의 0과 1로 할당과 가용(사용가능)을 구분한다. 그러면 왜 앞 뒤 2자리가 있는지 궁금할 것이다.
블록 크기는 16진수 비트로 이루어지는데 가용 여부 또한 16진수 비트로 구성해야 비트 연산을 통해 하나의 16진수로 구성할 수 있기 때문이다. -
두번째 층은 데이터이다. 할당된 블록의 경우 특정한 자료가 담긴다.
-
세번째 층은 패딩이다. 패딩이 왜 들어가는지 궁금할 것이다. 패딩은 블록의 크기를 일괄적으로 정렬해야 하기 때문에 들어간다. 블록의 크기는 규격화 되어야 효율성이 증가한다. 하나의 블록 크기가 다 다르다면 컴퓨터는 모든 블록을 다 따로따로 계산해야 할 것이다.
예를 들어 크기가 2byte인 데이터를 넣어야 하면, 컴퓨터는 16byte 블록을 할당할 것이다. 왜냐하면 블록에 header와 footer는 무조건 들어가야 하는데, 이들은 각각 4바이트씩이다.(1워드로 볼 수 있다.)
2+4+4 = 10byte로 생성 요건을 충족했지만, 방금 말했듯이 규격화해야하고 8의 배수 등으로 무조건 정렬 조건을 만족해야 하기 때문이다. 이미 들어가야 하는 자료가 8byte를 넘으니 6 byte를 더해서 16byte 블록을 할당한다.
이때 패딩을 사용해 6byte가 들어가게 된다.
- 마지막 층은 블록의 푸터로서 헤더와 동일한 기능을 수행한다. 굳이 2개를 만들어야 하냐는 이유도 있겠지만, 이유가 있다.
시간적으로 블록의 연결을 줄일 수 있기 때문이다. Donald Knuth라는 사람이 경계 태그라는 기법을 개발했는데, 각 블록이 푸터를 포함하게 되면 할당기는 시작 위치와 이전 블록의 상태를 자신의 푸터만 조사해서 파악할 수 있다. 이전 블록은 항상 현재 블록의 시작 부분에서 1word 앞에 위치하기 때문이다.
푸터를 넣음으로써 이전 블록과 다음 블록의 상태를 쉽게 파악할 수 있다. 물론, 장점만 있는 것은 아니다. 모든 블록이 헤더와 푸터를 유지해야 하므로 블록의 개수가 많아지면 메모리 오버헤드가 크게 발생할 수 있다.
블록의 설명은 이정도로 하자. 이렇게 블록을 만들다보면 블록들은 아래와 같이 연속된 배열로 구성할 수 있다.
여기서 이 연속된 배열은 가용 리스트라고 부르겠다. 실제 malloc 구현 시 쓰이는 개념이고 코드에 녹아내어야 하니 순서대로 한번 알아보자.
- 패딩 : 위에 설명한 용도의 패딩과 똑같다고 생각하면 된다.
- 프롤로그 헤더,푸터(prologue header/footer) : 메모리를 할당하거나 반환하다보면 블록을 연결해야 할 일이 생긴다. 그 연결과정 동안에 가장자리 조건을 없애기 위한 트릭이라고 생각하면 된다.
- 에필로그 헤더(epilogue header) : 에필로그 헤더 또한 프롤로그와 같이 일종의 트릭이다.
- header,footer: 실제로 데이터가 들어가는 블럭의 헤더와 푸터이다. 위에 블록 그림에서 설명한 헤더와 푸터라고 이해하면 된다.
malloc 프로그램은 전체 힙에서 이 가용 리스트를 할당한 다음, 가용 리스트 내부에 블록을 할당&반환하고, 가용리스트가 넘치면 새로운 리스트를 추가하고 빼는 식의 프로그램이라고 생각하면 된다.
기본 설계
이제 기본적인 개념은 알았으니, 설계를 해보자. 먼저 할당기가 시작할 때 호출되는 mm_init 함수를 만들어보자.
기본적으로 mm_init은 할당기를 초기화하고 성공이면 0, 실패면 -1을 리턴한다. 초기화 하는 과정에는 가용 리스트의 prologue header,footer, epilogue header를 만드는 과정이 포함된다.
이때 최소 블록 크기는 16바이트로 정한다. 가용 리스트는 묵시적 가용 리스트로 구성된다.
참고 : 묵시적 가용리스트란 사용가능한 블록이 헤더 내 필드에 의해서 암묵적으로 연결되는 구조의 리스트를 말한다. (블럭 내 헤더를 보고 가용여부를 알 수 있음)
mm_init 함수에 필요한 것
- 힙을 초기 사이즈만큼 세팅한다.
- 가용 리스트에 패딩을 넣는다.
- 가용 리스트에 프롤로그 헤더를 넣는다.
- 가용 리스트에 프롤로그 푸터를 넣는다.
- 가용 리스트에 에필로그 헤더를 넣는다.
- 힙에 블록을 할당하기 위해 사이즈를 적당히 한번 늘린다.
함수에 필요한 것들의 대부분이 무언가를 넣는 것이기 때문에 매크로를 만들어놓는 것이 좋다. 프로그램 전반적으로 계속 쓰일 것이기 때문이다. 따라서 맨 처음 변수 혹은 매크로를 설정해야 한다.
매크로 설정
- 1개의 word 사이즈
- 2배의 word 사이즈
- heap을 한번 늘릴 때 필요한 사이즈
- 주어진 값 중 어느 것이 더 클지 정하는 MAX 함수
- 블록 헤더에 사이즈와 할당여부를 넣을 함수
- 블록에 담긴 값을 읽어오는 함수
- 특정 위치에 값을 넣는 함수
- 해당 블록의 사이즈를 읽는 함수
- 해당 블록의 할당 여부를 읽는 함수
- 헤더 위치를 읽는 함수
- 푸터 위치를 읽는 함수
- 현재 블록의 다음 블록 위치로 이동하는 함수
- 현재 블록의 이전 블록 위치로 이동하는 함수
- 초기에 세팅할 힙
위의 매크로들은 모두 반복적으로 쓰이는 변수나 함수를 일반화 시켜놓은 것이다. 코드는 다음과 같다.
#define WSIZE 4 // word and header footer 사이즈를 byte로.
#define DSIZE 8 // double word size를 byte로
#define CHUNKSIZE (1<<12) // heap을 늘릴 때 얼만큼 늘릴거냐? 4kb 분량.
#define MAX(x,y) ((x)>(y)? (x) : (y)) // x,y 중 큰 값을 가진다.
// size를 pack하고 개별 word 안의 bit를 할당 (size와 alloc을 비트연산), 헤더에서 써야하기 때문에 만듬.
#define PACK(size,alloc) ((size)| (alloc)) // alloc : 가용여부 (ex. 000) / size : block size를 의미. =>합치면 온전한 주소가 나온다.
/* address p위치에 words를 read와 write를 한다. */
#define GET(p) (*(unsigned int*)(p)) // 포인터를 써서 p를 참조한다. 주소와 값(값에는 다른 블록의 주소를 담는다.)을 알 수 있다. 다른 블록을 가리키거나 이동할 때 쓸 수 있다.
#define PUT(p,val) (*(unsigned int*)(p)=(int)(val)) // 블록의 주소를 담는다. 위치를 담아야지 나중에 헤더나 푸터를 읽어서 이동 혹은 연결할 수 있다.
// address p위치로부터 size를 읽고 field를 할당
#define GET_SIZE(p) (GET(p) & ~0x7) // '~'은 역수니까 11111000이 됨. 비트 연산하면 000 앞에거만 가져올 수 있음. 즉, 헤더에서 블록 size만 가져오겠다.
#define GET_ALLOC(p) (GET(p) & 0x1) // 00000001이 됨. 헤더에서 가용여부만 가져오겠다.
/* given block ptr bp, header와 footer의 주소를 계산*/
#define HDRP(bp) ((char*)(bp) - WSIZE) // bp가 어디에있던 상관없이 WSIZE 앞에 위치한다.
#define FTRP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // 헤더의 끝 지점부터 GET SIZE(블록의 사이즈)만큼 더한 다음 word를 2번빼는게(그 뒤 블록의 헤드에서 앞으로 2번) footer의 시작 위치가 된다.
/* GIVEN block ptr bp, 이전 블록과 다음 블록의 주소를 계산*/
#define NEXT_BLKP(bp) ((char*)(bp) + GET_SIZE(((char*)(bp)-WSIZE))) // 그 다음 블록의 bp 위치로 이동한다.(bp에서 해당 블록의 크기만큼 이동 -> 그 다음 블록의 헤더 뒤로 감.)
#define PREV_BLKP(bp) ((char*)(bp) - GET_SIZE(((char*)(bp) - DSIZE))) // 그 전 블록의 bp위치로 이동.(이전 블록 footer로 이동하면 그 전 블록의 사이즈를 알 수 있으니 그만큼 그 전으로 이동.)
static char *heap_listp; // 처음에 쓸 큰 가용블록 힙을 만들어줌.이제 다시 mm_init 함수를 구현해보자. 구현 코드는 다음과 같다.
int mm_init(void){ // 처음에 heap을 시작할 때 0부터 시작. 완전 처음.(start of heap)
/* create 초기 빈 heap*/
if ((heap_listp = mem_sbrk(4*WSIZE)) == (void*)-1){ // old brk에서 4만큼 늘려서 mem brk로 늘림.
return -1;
}
PUT(heap_listp,0); // 블록생성시 넣는 padding을 한 워드 크기만큼 생성. heap_listp 위치는 맨 처음.
PUT(heap_listp + (1*WSIZE), PACK(DSIZE,1)); // prologue header 생성. pack을 해석하면, 할당을(1) 할건데 8만큼 줄거다(DSIZE). -> 1 WSIZE 늘어난 시점부터 PACK에서 나온 사이즈를 줄거다.)
PUT(heap_listp + (2*WSIZE), PACK(DSIZE,1)); // prologue footer생성.
PUT(heap_listp + (3*WSIZE), PACK(0,1)); // epilogue block header를 처음에 만든다. 그리고 뒤로 밀리는 형태.
heap_listp+= (2*WSIZE); // prologue header와 footer 사이로 포인터로 옮긴다. header 뒤 위치. 다른 블록 가거나 그러려고.
if (extend_heap(CHUNKSIZE/WSIZE)==NULL) // extend heap을 통해 시작할 때 한번 heap을 늘려줌. 늘리는 양은 상관없음.
return -1;
return 0;
}먼저 초기 힙 영역을 할당.(mem_sbrk) → 그리고 패딩을 하나 삽입 → prologue header 생성 → prologue footer 생성 → epilogue header 생성 → 초기 힙의 포인터를 prologue header 뒤로 옮긴다. (포인터는 항상 어느 블록이든 header 뒤에 위치한다. 헤더를 읽어서 다른 블록의 값을 가지고오거나 이동을 용이하게 하기 위해서다.) → heap을 한번 특정 사이즈만큼 증가
init 함수 도중에 heap을 특정 사이즈만큼 증가시키려 했기 때문에 이 액션도 함수로 만들 것이다. extend_heap 이라는 함수를 만들 것이다.
extend_heap 구현
static void *extend_heap(size_t words){ // 새 가용 블록으로 힙 확장, 예시로는 2의 10승만큼 워드블록을 만들어라.
char *bp;
size_t size; // size+t = unsigned int, 이 함수에서 넣을 size를 하나 만들어줌.
/* alignment 유지를 위해 짝수 개수의 words를 Allocate */
size = (words%2) ? (words+1) * WSIZE : words * WSIZE; // 홀수이면(1이나오니까) 앞에꺼, 짝수이면(0이 나오니까) 뒤에꺼. 홀수 일 때 +1 하는건 8의 배수 맞추기 위함인듯.
// 홀수가 나오면 사이즈를 한번 더 재정의. 힙에서 늘릴 사이즈를 재정의.
if ( (long)(bp = mem_sbrk(size)) == -1){ // sbrk로 size로 늘려서 long 형으로 반환한다.(한번 쫙 미리 늘려놓는 것) mem_sbrk가 반환되면 bp는 현재 만들어진 블록의 끝에 가있음.
return NULL;
} // 사이즈를 늘릴 때마다 old brk는 과거의 mem_brk위치로 감.
/* free block 헤더와 푸터를 init하고 epilogue 헤더를 init*/
PUT(HDRP(bp), PACK(size,0)); // free block header 생성. /(prologue block이랑 헷갈리면 안됨.) regular block의 총합의 첫번째 부분. 현재 bp 위치의 한 칸 앞에 헤더를 생성.
PUT(FTRP(bp),PACK(size,0)); // free block footer / regular block 총합의 마지막 부분.
PUT(HDRP(NEXT_BLKP(bp)), PACK(0,1)); // 블록을 추가했으니 epilogue header를 새롭게 위치 조정해줌. (HDRP: 1워드 뒤에 있는 것을 지칭.
// 처음 세팅의 의미 = bp를 헤더에서 읽은 사이즈만큼 이동하고, 앞으로 한칸 간다. 그위치가 결국 늘린 블록 끝에서 한칸 간거라 거기가 epilogue header 위치.
/* 만약 prev block이 free였다면, coalesce해라.*/
return coalesce(bp); // 처음에는 coalesc를 할게 없지만 함수 재사용을 위해 리턴값으로 선언
}이 함수의 용도는 크게 다음과 같다.
- 힙이 초기화 될 때(init) 앞으로 블록을 넣기 위해 사이즈를 한번 늘리는 것
- malloc을 통해 블록을 넣을 영역을 알아봤지만 적당한 맞춤 영역을 찾지 못했을 때 늘리는 것
이제 코드를 따라가면서 로직을 보자.
먼저 인자를 words 크기로 받아서, 정렬 기준을 유지하기 위해 2워드의 배수로 반올림. (words%2) ? (words+1) * WSIZE : words * WSIZE; → 그리고 메모리로부터 추가적인 힙공간을 요청(mem_sbrk)
→ 사이즈를 늘렸으니 그 자리에는 가용 블록이 들어가야 함. 그래야 추후에 malloc을 통해 할당을 요청하면 데이터가 블록에 들어갈 수 있기 때문이다.
→ 새 가용 블록의 header와 footer를 만듬.
→ 그리고 기존 가용리스트의 epilogue header 위치를 조정.(epilogue header는 항상 가용리스트의 끝 부분에 있어야 하기 때문에 위치를 재조정해야 한다.)
참고 : 이 때 bp포인터의 위치에 주의해야한다. 코드를 따라가면서 bp가 어떻게 움직일 수 있는지 잘 살펴보기 바란다.
블록 연결하는 함수 만들기(coalesce)
- 힙을 확장하면서 가용블록이 생긴다. 가용 블록이 생기면, 생기는 시점에 현재 블록 주변에도 가용 블록이 있는지 살피고 합칠 수 있는 블록은 합쳐야 한다. 합치지 않으면, 작은 가용 블록들로 쪼개져 있는 경우에는 작은 블록들의 합이 충분히 커서 큰 메모리가 들어갈 수 있어보이지만, 구역이 나뉘어져있어서 못 들어가는 경우가 생기기 때문이다.
- 참고로 위의 문제를 false fragmentation(오류 단편화)이라고 한다.
- 따라서 합치는 함수를 구현해보자.
extend_heap의 리턴값이기도 하지만 블록을 반환하는free함수에서도 쓰일 예정이다.
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){ // case 1 - 이전과 다음 블록이 모두 할당 되어있는 경우, 현재 블록의 상태는 할당에서 가용으로 변경
return bp; // 이미 free에서 가용이 되어있으니 여기선 따로 free 할 필요 없음.
}
else if (prev_alloc && !next_alloc){ // case2 - 이전 블록은 할당 상태, 다음 블록은 가용상태. 현재 블록은 다음 블록과 통합 됨.
size += GET_SIZE(HDRP(NEXT_BLKP(bp))); // 다음 블록의 헤더를 보고 그 블록의 크기만큼 지금 블록의 사이즈에 추가한다.
PUT(HDRP(bp),PACK(size,0)); // 헤더 갱신(더 큰 크기로 PUT)
PUT(FTRP(bp), PACK(size,0)); // 푸터 갱신
}
else if(!prev_alloc && next_alloc){ // case 3 - 이전 블록은 가용상태, 다음 블록은 할당 상태. 이전 블록은 현재 블록과 통합.
size+= GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size,0)); // 푸터에 먼저 조정하려는 크기로 상태 변경한다.
PUT(HDRP(PREV_BLKP(bp)), PACK(size,0)); // 현재 헤더에서 그 앞블록의 헤더 위치로 이동한 다음에, 조정한 size를 넣는다.
bp = PREV_BLKP(bp); // bp를 그 앞블록의 헤더로 이동(늘린 블록의 헤더이니까.)
}
else { // case 4- 이전 블록과 다음 블록 모두 가용상태. 이전,현재,다음 3개의 블록 모두 하나의 가용 블록으로 통합.
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; // 4개 케이스중에 적용된거로 bp 리턴
}coalesce 함수에서는 현재 블록이 살필 수 있는 4가지 케이스를 다뤄야 한다.
- 이전 블록과 다음 블록이 모두 할당되어 있는 경우 → 합칠 수 없다.
- 이전 블록은 할당상태이지만, 다음 블록은 가용상태인 경우 → 다음 블록과 합칠 수 있다.
- 이전 블록은 가용상태이고, 다음 블록은 할당 상태인 경우 → 이전 블록과 합칠 수 있다.
- 이전 블록이 가용상태이고, 다음 블록도 가용 상태인 경우 → 이전,다음 블록 모두 합칠 수 있다.
이 함수에서는 코드를 따라가며 가용 상태인 블록과 어떻게 합쳐지는지 살펴보기 바란다.
참고로 bp는 위에서 정했듯 항상 블록의 헤더 뒤에 위치하는게 좋기 때문에 연결이 끝나면 bp는 블록의 헤더에 위치해야 한다.
데이터 할당 함수 만들기(malloc)
연결하는 함수도 만들었으니 이제 가용 리스트에서 블록을 할당하는 함수를 만들어보자. 블록이 할당되면 데이터가 들어갈 수 있기 때문이다.
void *mm_malloc(size_t size){ // 가용 리스트에서 블록 할당 하기
size_t asize; // 블록 사이즈 조정
size_t extendsize; // heap에 맞는 fit이 없으면 확장하기 위한 사이즈
char *bp;
/* 거짓된 요청 무시*/
if (size == 0) return NULL; // 인자로 받은 size가 0이니까 할당할 필요 없음.
/* overhead, alignment 요청 포함해서 블록 사이즈 조정*/
if (size <= DSIZE){
asize = 2*DSIZE; // 헤더와 푸터를 포함해서 블록 사이즈를 다시 조정해야되니까 DSIZE의 2배를 준다.(헤더와 푸터 합쳐서 8바이트)예를 들어 헤더와 푸터에는 16/1 이 들어간다.
}
else {
asize = DSIZE* ( (size + (DSIZE)+ (DSIZE-1)) / DSIZE ); // size보다 클 때, 블록이 가질 수 있는 크기 중에 최적화된 크기로 재조정.
}
/* fit에 맞는 free 리스트를 찾는다.*/
if ((bp = find_fit(asize)) != NULL){
place(bp,asize);
return bp; // place를 마친 블록의 위치를 리턴.
}
/* 위에서 안됐다 = fit 맞는게 없다. 메모리를 더 가져와 block을 위치시킨다.*/
extendsize = MAX(asize,CHUNKSIZE); // asize와 CHUNKSIZE(우리가 원래 처음에 세팅한 사이즈.) 중에 더 큰거로 넣는다.
if ( (bp=extend_heap(extendsize/WSIZE)) == NULL){
// CHUNKSIZE는 블록을 늘리는 양이고, MAX_ADDR는 힙의 최대 크기라서 두개는 다르다. 인자로 들어가는건 단위 블록 수.
return NULL;
}
place(bp,asize); // 확장된 상태에서 asize를 넣어라.
return bp;
}이 함수에서는 얼마나 블록을 할당할지에 대한 사이즈를 인자로 받는다.
사이즈는 임의로 들어올 수 있기 때문에 정렬을 위해 함수 내부에서 사이즈를 조정해야 한다.
그리고 할당을 할 수 없을 때는 힙을 확장해 할당할 수 있는 자리를 마련해주어야 한다.
참고로, 사이즈 조정에 대한 코드는 이 부분이다. else에 있는 수식은 무조건 인접한 8의 배수로 만들어준다.(8의 배수가 우리가 정한 기준이다.)
if (size <= DSIZE){
asize = 2*DSIZE; // 헤더와 푸터를 포함해서 블록 사이즈를 다시 조정해야되니까 DSIZE의 2배를 준다.(헤더와 푸터 합쳐서 8바이트)예를 들어 헤더와 푸터에는 16/1 이 들어간다.
}
else {
asize = DSIZE* ( (size + (DSIZE)+ (DSIZE-1)) / DSIZE ); // size보다 클 때, 블록이 가질 수 있는 크기 중에 최적화된 크기로 재조정.할당기가 요청한 크기를 조정하면 할당할 가용 블록이 가용 리스트에 있는지 탐색한다(find_fit) → 맞는 블록을 찾으면 요청한 블록을 배치한다.(place) 필요하면 기존 블록을 분할한다. → 맞는 블록을 찾지 못하면 힙을 늘리고 다시 배치한다.
이제 내부에서 쓰는 find_fit 과 place 함수를 만들어보자.
find_fit 함수
static void *find_fit(size_t asize){ // first fit 검색을 수행
void *bp;
for (bp= heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){ // init에서 쓴 heap_listp를 쓴다. 처음 출발하고 그 다음이 regular block 첫번째 헤더 뒤 위치네.
// for문이 계속 돌면 epilogue header까기 간다. epilogue header는 0이니까 종료가 된다.
if (!GET_ALLOC(HDRP(bp)) && (asize<=GET_SIZE(HDRP(bp)))){ // 이 블록이 가용하고(not 할당) 내가 갖고있는 asize를 담을 수 있으면
return bp; // 내가 넣을 수 있는 블록만 찾는거니까, 그게 나오면 바로 리턴.
}
}
return NULL; // 종료 되면 null 리턴. no fit 상태.
}find_fit 함수는 가용 리스트에 적절한 블록을 찾는 함수이다. 탐색은 크게 3가지 방법으로 나뉜다.
- first fit : 가용블록 리스트를 처음부터 검색해서 크기가 맞는 첫번째 가용 블록을 선택
- next fit : 검색을 리스트의 처음에서 시작하는 대신, 이전 검색이 종료된 지점에서 검색을 시작
- best fit : 모든 가용블록을 검사해서 크기가 맞는 가장 작은 블록을 선택
여기서는 first fit 으로 구현해보려고 한다.
따라서 처음부터 검색하기 위해 bp 포인터 위치를 처음 init 때 세팅했던 위치(heap_listp)로 잡는다. 여기서부터 탐색하면 모든 블록을 다 탐색할 수 있다.
→ NEXT_BLKP 함수를 이용해 다음 블록으로 이동한다.
→ 블록의 헤더를 검사한다. 검사 조건은 가용 블록이어야 하고, 해당 블록의 사이즈가 넣으려고 했던 사이즈보다 커야 한다는 것이다.
→ 사이즈가 0인 블록이 나오면 탐색을 종료한다.(사이즈가 0인 블록은 epilogue header이다. epilogue header는 가용 리스트의 끝이기 때문에 탐색을 종료해야 한다.)
→ 만약 적절한 위치를 찾지 못하면 NULL을 리턴한다.
이제 위치를 찾았으면 place 함수를 만들어보자.
place 함수
static void place(void *bp, size_t asize){ // 들어갈 위치를 포인터로 받는다.(find fit에서 찾는 bp) 크기는 asize로 받음.
// 요청한 블록을 가용 블록의 시작 부분에 배치, 나머지 부분의 크기가 최소 블록크기와 같거나 큰 경우에만 분할하는 함수.
size_t csize = GET_SIZE(HDRP(bp)); // 현재 있는 블록의 사이즈.
if ( (csize-asize) >= (2*DSIZE)){ // 현재 블록 사이즈안에서 asize를 넣어도 2*DSIZE(헤더와 푸터를 감안한 최소 사이즈)만큼 남냐? 남으면 다른 data를 넣을 수 있으니까.
PUT(HDRP(bp), PACK(asize,1)); // 헤더위치에 asize만큼 넣고 1(alloc)로 상태변환. 원래 헤더 사이즈에서 지금 넣으려고 하는 사이즈(asize)로 갱신.(자르는 효과)
PUT(FTRP(bp), PACK(asize,1)); //푸터 위치도 변경.
bp = NEXT_BLKP(bp); // regular block만큼 하나 이동해서 bp 위치 갱신.
PUT(HDRP(bp), PACK(csize-asize,0)); // 나머지 블록은(csize-asize) 다 가용하다(0)하다라는걸 다음 헤더에 표시.
PUT(FTRP(bp), PACK(csize-asize,0)); // 푸터에도 표시.
}
else{
PUT(HDRP(bp), PACK(csize,1)); // 위의 조건이 아니면 asize만 csize에 들어갈 수 있으니까 내가 다 먹는다.
PUT(FTRP(bp), PACK(csize,1));
}
}place 함수는 위치와 할당할 크기를 인자로 받는다.
우선 넣을 위치의 블록 사이즈를 계산한다. 할당할 크기보다 블록 사이즈가 크면 나머지 부분은 가용블록으로 쪼개야하기 때문이다. (그대로 놔두면 영역 낭비가 된다.)
블록 사이즈가 크면, 블록을 할당하고(블록 헤더,푸터 위치를 재조정) 나머지 부분을 쪼갠다.(블록 헤더 푸터를 새로 표시)
그렇지 않으면 블록을 할당만 한다.
place 까지 만들었으면 malloc 함수 구현은 끝났다. 이제 블록을 반환하는 free 함수를 만들어보자.
free 함수
// 블록을 반환하고 경계 태그 연결 사용 -> 상수 시간 안에 인접한 가용 블록들과 통합하는 함수
void mm_free(void *bp){
// 어느 시점에 있는 bp를 인자로 받는다.
size_t size = GET_SIZE(HDRP(bp)); // 얼만큼 free를 해야 하는지.
PUT(HDRP(bp),PACK(size,0)); // header, footer 들을 free 시킨다. 안에 들어있는걸 지우는게 아니라 가용상태로 만들어버린다.
PUT(FTRP(bp), PACK(size,0));
coalesce(bp);
}free 함수는 반환할 블록의 위치를 인자로 받는다. 그리고 해당 블록의 가용 여부를 0(가용상태)으로 만들어버린다. 여기서 핵심은 블록을 가용 리스트에서 제거하는게 아니라 가용상태로 만들어버린다는 것이다.
블록이 반환 되었으니 extend_heap 과 유사하게 블록을 연결하는 함수를 실행한다. 가용 블럭이 생기면 항상 연결하는 함수를 실행해서 연결 가능한 블록을 챙겨야 한다.
이제 기본적인 함수 제작은 완료했다. 추가로 할당된 블록의 사이즈를 조정하는 함수도 만들어보자. malloc 의 자매 함수로 realloc 이라는 함수를 만들 것이다.
realloc 함수
void *mm_realloc(void *bp, size_t size){
if(size <= 0){
mm_free(bp);
return 0;
}
if(bp == NULL){
return mm_malloc(size);
}
void *newp = mm_malloc(size);
if(newp == NULL){
return 0;
}
size_t oldsize = GET_SIZE(HDRP(bp));
if(size < oldsize){
oldsize = size;
}
memcpy(newp, bp, oldsize);
mm_free(bp);
return newp;
}realloc 에서는 크기를 조정할 블록의 위치와 요청 사이즈를 인자로 받는다. 그 후 malloc(size) 을 통해 요청 사이즈만큼 블록을 할당한다. 여기서 핵심은 이미 할당된 블록의 사이즈를 직접 건드리는게 아니라, 임시로 요청 사이즈만큼의 블록을 만들고 현재의 블록을 반환하는 것이다. 그러면 사이즈를 변경한 효과가 나기 때문이다. 또한 블록 내 데이터 또한 똑같이 옮겨야 하니 C라이브러리에 있는 memcpy 함수를 활용한다. 그리고 기존 블록을 반환한다.
여기서 만약
1.요청 사이즈가 0보다 작거나 같으면 반환을 해도 되니 반환을 해버린다.
2.위치가 없다면 malloc 을 통해 새롭게 사이즈만큼 생성한다. (예외처리의 일종)
3.요청 사이즈가 기존 사이즈보다 작으면 요청 사이즈만큼의 데이터만 잘라서 옮긴다.
memcpy 관련 : https://blockdmask.tistory.com/442
여기까지하면 기본적인 malloc 프로그램 제작이 된 것이다. 오늘 구현한 방식은 implicit 방식이다. 구현 순서는 아래와 같다.
구현 순서
- define macro : 구현에 필요한 변수들을 선언해줌
- mm_init : 최초에 가용블록을 만들어 힙을 생성
- extend_heap : 새 가용 블록으로 힙 확장
- coalesce : 인접 가용 블록들과 통합
- mm_malloc : 가용 블록 리스트에서 블록 할당
- find_fit : 할당할 블록이 들어갈 위치 찾기
- place : 할당할 블록을 찾은 위치에 넣기(필요시 분할)
- free : 블록을 반환
- realloc : 블록 크기를 재조정
참고로 implicit 방식 이외에도 explicit , segregated 방식도 있다.
간단하게 설명해보자면,
explicit : 가용한 블록을 찾을 때, 가용한 블록만 존재하는 연결리스트를 따로 만들어서 거기서 찾는다. 할당된 블록을 따로 확인하지 않아도 되니 탐색 시간이 줄어든다.
segregated : 가용한 블록만 존재하는 리스트를 여러개 만든다. 각 리스트에는 거의 동일한 크기의 가용 블록을 저장해서 사이즈 별로 탐색할 수 있게 한다. 이 방법 또한 탐색 시간을 줄일 수 있다.
implicit 방식을 이해했으니 explicit 이나 segregated 는 생각의 응용을 통해 구현할 수 있을 것이다.
implicit 방식에서도 블록을 탐색하는 방식을 first fit 말고 다른 방법으로 구현할 수 있다. next fit 방식으로 구현해보는 것도 도움이 될 것이다.
오늘의 전체 코드는 아래의 깃헙에서 모두 볼 수 있다. 참고로 explicit 방법 코드나 next fit 탐색 방식 코드도 같이 볼 수 있다.
할당된 블럭에는 굳이 footer가 필요없지 않나요? free한 블럭만 footer 를 넣어주고 할당된 블럭은 footer대신 데이터를 할당해주는게 보다 메모리 효율이 좋을거같아서요..!!