mojo's Blog
malloc 구현 코드 리뷰 본문
간단한 "implicit free list" 를 기반으로 한 malloc 코드이다.
first-fit 과 next-fit 를 사용하며 boundary tag 를 이용하여 coalesce 를 한다.
그리고 블럭들은 doubleword(8 byte) 단위로 정렬이 되어야 하며 최소 블럭 사이즈는 16 byte 여야 한다.
※ define 에 대한 설명
/*
* If NEXT_FIT defined use next fit search, else use first fit search
*/
#define NEXT_FITx
/* $begin mallocmacros */
/* Basic constants and macros */
#define WSIZE 4 /* Word and header/footer size (bytes) */ //line:vm:mm:beginconst
#define DSIZE 8 /* Doubleword size (bytes) */
#define CHUNKSIZE (1<<12) /* Extend heap by this amount (bytes) */ //line:vm:mm:endconst
#define MAX(x, y) ((x) > (y)? (x) : (y))
/* Pack a size and allocated bit into a word */
#define PACK(size, alloc) ((size) | (alloc)) //line:vm:mm:pack
/* Read and write a word at address p */
#define GET(p) (*(unsigned int *)(p)) //line:vm:mm:get
#define PUT(p, val) (*(unsigned int *)(p) = (val)) //line:vm:mm:put
/* Read the size and allocated fields from address p */
#define GET_SIZE(p) (GET(p) & ~0x7) //line:vm:mm:getsize
#define GET_ALLOC(p) (GET(p) & 0x1) //line:vm:mm:getalloc
/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp) ((char *)(bp) - WSIZE) //line:vm:mm:hdrp
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) //line:vm:mm:ftrp
/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) //line:vm:mm:nextblkp
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) //line:vm:mm:prevblkp
/* $end mallocmacros */
- NEXT_FITx : 이 경우는 first-fit 탐색을 해주며 next-fit 탐색을 해주고 싶으면 NEXT_FIT 으로
변경시키면 된다.
NEXT_FIT 가 선언되었는지 선언되지 않았는지를 판단하여 next-fit 을 돕는 tracking 용도의 변수가
선언되는데 이는 전역변수에 대한 설명을 통해 알 수 있다.
- WSIZE : word size 는 4 byte 로 정의한 것을 알 수 있다.
- DSIZE : doubleword size 는 8 byte 로 WSIZE 의 두 배로 정의한 것을 알 수 있다.
- CHUNKSIZE : malloc 을 하다보면 free 공간을 찾는 과정에서 적당한 할당 공간을 찾을 수 없는 경우가 존재한다.
이 경우에는 memlib.c 에 static char * 타입으로 선언된 mem_brk 를 가지고 sbrk 함수를 통해서
brk pointer 를 늘려줘야 하는데 최소 CHUNKSIZE 만큼을 늘려주는 역할을 한다.
이 때, 할당할 공간의 사이즈 asize 가 CHUNKSIZE 보다 클 경우는 asize 만큼 brk pointier 를 늘려준다.
- PACK(size, alloc) : alloc 값은 0 또는 1 이며 이러한 값을 통해 해당 블럭이 free 한지, 할당되었는지를 알 수 있다.
자세히 알아보면 doubleword(8 byte) 단위로 정렬해야 하며 block 사이즈는 최소 16 byte 임을 위에서 언급했다.
이러한 성질을 이용한다면, size 값은 16 byte 이상이면서 8 byte 로 나머지 연산을 취할 경우 항상 0 이다.
즉, size = 16 + 8a (a ≥ 0) 이며 2 진수로 나타낼 경우 하위 3 개의 비트를 제외한 나머지 비트를 0 과 1 로
구성 되는 것을 알 수 있는데, 이를 통해 하위 3 개의 비트는 사이즈가 아닌 다른 용도로 쓰이는 것을 알 수 있다.
하위 3 개의 비트중 LSB 값에 따라 free 인지 할당되었는지를 판별할 수 있는데 다음과 같이 정리가 가능하다.
- LSB = 0 : \(000_{2}\) 으로 블럭이 free 한 공간임을 알린다.
- LSB = 1 : \(001_{2}\) 으로 블럭이 할당된 공간임을 알린다.
그러면 LSB 를 제외한 나머지 2 bit 는 어떠한 용도로 쓰일까?
아쉽게도 나머지 2 bit 는 항상 0 bit 로 사용되지 않는 bit 이다.
- GET(p) : 포인터 타입 p 를 unsigned int * 타입으로 변환하여 p 가 가르키고 있는 공간에 존재하는 값을
가져오는 것을 알 수 있다.
implicit free list 에서는 boundary tag 를 사용하여 coalesce 를 하는데 구조를 대략적으로 알아야 할
필요가 있어보인다.
boundary tag 를 사용하면 앞, 뒤로 header, footer 에 대한 공간과 그 사이에 payload 및 padding 이
붙어서 이러한 공간들을 하나의 block 이라고 하며 사이즈는 최소 16 byte 이상이며 8 byte 정렬을 지킨다.
따라서, GET(p) 에서 p는 header 또는 footer 를 가르키고 있는 포인터가 될 수 있고, 이를 unsigned int *
타입으로 변환하여 unsigned int 값인 size 를 읽어서 해당 블럭의 사이즈 및 할당 여부를 알 수 있게 된다.
- PUT(p, val) : p 의 타입을 unsigned int * 타입으로 변환하여 가르키고 있는 공간에 val 값을 넣는다.
여기서 val 값은 해당 블럭의 사이즈 및 할당 여부를 알 수 있도록 하는 값이다.
- GET_SIZE(p) : GET(p) 를 통해 블럭의 size 및 할당 여부를 담고 있는 값을 가져오고 ~0x7 와 & 연산을 통해
block 의 size 를 가져오게 된다.
특정 블럭의 사이즈를 40 이라 하고 할당되었다고 가정하면 2진수로 \(101001_{2}\) 이다.
여기서 0x7 = \(000111_{2}\) 을 not 을 하게 되면 ~0x7 = \(111000_{2}\) 이 된다.
즉, 하위 3 비트를 제외한 나머지 비트를 추출해오는데 이는 결국 블럭의 사이즈가 되버린다.
따라서, \(101001_{2}\) & \(111000_{2}\) = \(101000_{2}\) = 40 이 블럭 사이즈가 된다.
- GET_ALLOC(p) : GET_SIZE(p) 와 동일하게 GET(p) 를 통해 블럭의 size 및 할당 여부를 담고 있는 값을
가져오고 0x1 과 & 연산을 통해 LSB 만을 가져오게 되는데 이는 0 또는 1 의 값으로 블럭의 할당 여부를 알 수 있다.
- HDRP(bp) : 블럭의 포인터 bp 를 통해 블럭의 header 가 가르키고 있는 주소를 받아오도록 한다.
(char *)(bp) - WSIZE 를 통해 bp 의 주소는 header 에서 시작하는 것이 아님을 알 수 있으며 동시에
WSIZE 만큼 빼서 header 의 주소를 받아오게 되므로 header 가 차지하고 있는 공간은 4 byte 임을 알 수 있다.
- FTRP(bp) : 블럭의 포인터 bp 를 통해 블럭의 footer 가 가르키고 있는 주소를 받아오도록 한다.
(char *)(bp) +GET_SIZE(HDRP(bp)) - DSIZE 를 통해 footer 가 가르키고 있는 주소를 가져오게 되는데
여기서 bp 가 가르키고 있는 주소에서 블럭 사이즈만큼 더해주면 다음 블럭의 주소를 가르키게 된다.
따라서 WSIZE 가 아닌 DSIZE 를 빼줘야 footer 가 가르키고 있는 주소를 얻게 되며 WSIZE 를 빼게 되면
자연스럽게 다음 블럭의 header 주소를 얻게 된다.
HDRP(bp), FTRP(bp) 를 가져오는 방식은 다음과 같이 가져오는 것을 알 수 있다.
- NEXT_BLKP(bp) : 현재 블럭에서 다음 블럭에 대한 주소값을 받아올 수 있다.
(char *)(bp) + GET_SIZE((char *)(bp) - WSIZE) 에서 (char *)(bp) - WSIZE 가 가르키는 곳은 header 이다.
따라서, GET_SIZE((char *)(bp) - WSIZE) 는 자연스럽게 현재 블럭에 대한 사이즈가 되며 이를 더하게 되면
다음 블럭에 대한 주소를 얻게 된다.
- PREV_BLKP(bp) : 현재 블럭에서 이전 블럭에 대한 주소값을 받아올 수 있다.
(char *)(bp) - GET_SIZE((char *)(bp) - DSIZE) 에서 (char *)(bp) - DSIZE 가 가르키는 곳은 footer 이다.
따라서, 위와 같은 연산을 통해 이전 블럭에 대한 주소를 얻게 된다.
※ 전역 변수에 대한 설명
/* Global variables */
static char *heap_listp = 0; /* Pointer to first block */
#ifdef NEXT_FIT
static char *rover; /* Next fit rover */
#endif
- heap_listp : 첫번째 block 의 pointer 를 담당하는 용도이다.
- rover : define 을 통해 NEXT_FIT 이 정의된 경우 rover 를 통해 next-fit 탐색을 돕도록 한다.
정의되지 않은 경우 해당 변수는 사용되지 않는다.
※ int mm_init(void)
int mm_init(void)
{
/* Create the initial empty heap */
if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1) //line:vm:mm:begininit
return -1;
PUT(heap_listp, 0); /* Alignment padding */
PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); /* Prologue header */
PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
PUT(heap_listp + (3*WSIZE), PACK(0, 1)); /* Epilogue header */
heap_listp += (2*WSIZE); //line:vm:mm:endinit
/* $end mminit */
#ifdef NEXT_FIT
rover = heap_listp;
#endif
/* $begin mminit */
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}
malloc 을 하기 위해선 초기화 작업은 필수다.
따라서 초기에 malloc 을 할 경우 해당 함수가 호출이 된다.
처음에 mem_sbrk(4*WSIZE) 를 호출함으로써 heap_listp 의 시작 주소를 변경시켜 준다.
그렇다면 mem_sbrk 함수는 어떤 매커니즘으로 수행이 되는지 확인이 필요하다.
static char *mem_heap; /* Points to first byte of heap */
static char *mem_brk; /* Points to last byte of heap plus 1 */
static char *mem_max_addr; /* Max legal heap addr plus 1*/
void mem_init(void)
{
mem_heap = (char *)Malloc(MAX_HEAP);
mem_brk = (char *)mem_heap;
mem_max_addr = (char *)(mem_heap + MAX_HEAP);
}
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 함수를 살펴보기 전에 전역 변수로 선언된 mem_heap, mem_brk, mem_max_addr 가
어떠한 용도로 사용되는지를 알아야 할 필요가 있어보인다.
우선 mem_init() 함수를 통해 전역 변수들에 대한 초기화 작업이 진행된다.
위와 같이 MAX_HEAP 사이즈 만큼 동적 할당을 통해 공간이 생성되며 mem_brk 는 시작부분,
mem_max_addr 는 mem_heap 의 가장 마지막 부분을 가르키게 된다.
이 주소들은 위에서 언급한 heap_listp 및 rover 가 해당 영역을 가르키게 된다.
그러면, 4*WSIZE 값을 파라미터로 받아와서 mem_sbrk 함수를 수행하는데 old_brk 는 mem_brk 의
주소를 할당받게 되며 이 주소값을 반환하여 heap_listp 에 주소를 할당해주는 것을 알 수 있다.
조건문을 보면 incr 값이 0 미만이거나 mem_max_addr 주소를 넘어가는 경우 에러 처리를 해준다.
에러가 없을 경우, mem_brk += incr 을 해주고 주소값 (void *)old_brk 를 반환하게 된다.
따라서 이러한 과정을 통해 다음과 같이 mem_brk 의 주소값이 변경되는 것을 알 수 있다.
다시 mm_init 함수로 돌아가면, 현재 heap_listp 는 mem_heap 주소를 가르키고 있으며 4 번의 PUT 이
연달아 일어나는 것을 알 수 있다.
이를 순차적으로 수행하면 다음과 같다.
- 시작 부분인 heap_listp 에 0 을 넣는다. (가장 앞 부분인 4 byte 는 사용하지 않음을 암시)
- heap_listp + (WSIZE) 에 DSIZE | 1 을 넣는다. (header 에 해당)
- heap_listp + (2*WSIZE) 에 DSIZE | 1 을 넣는다. (footer 에 해당)
- heap_listp + (3*WSIZE) 에 0 | 1 을 넣는다.
그리고 heap_listp 의 주소를 2 * WSIZE 만큼 이동시킨다.
만약 NEXT_FIT 이 선언된 경우에 rover 는 heap_listp 와 동일한 주소값을 갖도록 된다.
이러한 과정을 걸치면 다음과 같이 표현할 수 있다.
그 후에 extend_heap(CHUNKSIZE/WSIZE) 를 호출하여 heap 의 사이즈를 늘려주는걸 알 수 있다.
여기서 CHUNKSIZE/WSIZE 는 \(2^{12} / 4 = 2^{10}\) 으로 인자값을 \(2^{10}\) 으로 넘겨준다.
extend_heap 함수는 다음과 같다.
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
/* Allocate an even number of words to maintain alignment */
size = (words % 2) ? (words+1) * WSIZE : words * WSIZE; //line:vm:mm:beginextend
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL; //line:vm:mm:endextend
/* Initialize free block header/footer and the epilogue header */
PUT(HDRP(bp), PACK(size, 0)); /* Free block header */ //line:vm:mm:freeblockhdr
PUT(FTRP(bp), PACK(size, 0)); /* Free block footer */ //line:vm:mm:freeblockftr
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */ //line:vm:mm:newepihdr
/* Coalesce if the previous block was free */
return coalesce(bp); //line:vm:mm:returnblock
}
우선 파라메터로 받은 words 는 \(2^{10}\) 이다.
size 는 words 값이 홀수일 경우 (words + 1) * WSIZE 를 하여 할당을 해주는 것으로 보아 doubleword 단위로
정렬하는 것을 알 수 있다.
그러면 현재 words 값은 짝수이므로 자연스럽게 size 는 \(2^{12}\) 이며 mem_sbrk(size) 를 호출하여
받아온 주소값을 bp 에 할당해주는 것을 알 수 있다.
그 후에 3 번의 PUT 작업을 수행하면 다음과 같이 나타낼 수 있다.
그 후에 coalesce(bp) 를 호출한 후에 받아온 주소값을 반환하게 된다.
그러면 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) { /* Case 1 */
return bp;
}
else if (prev_alloc && !next_alloc) { /* Case 2 */
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) { /* Case 3 */
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 { /* Case 4 */
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);
}
/* $end mmfree */
#ifdef NEXT_FIT
/* Make sure the rover isn't pointing into the free block */
/* that we just coalesced */
if ((rover > (char *)bp) && (rover < NEXT_BLKP(bp)))
rover = bp;
#endif
/* $begin mmfree */
return bp;
}
우선, prev_alloc, next_alloc 값은 현재 블럭 bp 를 기준으로 이전 블럭과 다음 블럭의 할당 여부를 알 수 있는
0, 1 인 값이 들어가게 된다.
초록색으로 된 블럭을 할당된 블럭, 하늘색으로 된 블럭을 free 블럭으로 보자.
그러면 prev_alloc = 1, next_alloc = 1 이므로 양 쪽 전부 할당된 상태이며, size 값은 현재 bp 블럭의 사이즈이다.
따라서, case 1 에서 조건이 만족되므로 coalesce 없이 bp 를 반환하게 된다.
자연스럽게 extend_heap 함수에서 호출한 coalesce(bp) 값을 반환하게 되고 mm_init 함수에서
extend_heap(CHUNKSIZE/WSIZE) 값이 NULL 이 아니므로 최종적으로 0을 반환하며
mm_init 함수가 종료된다.
그러면 coalesce 함수의 나머지 케이스인 case 2, 3, 4 를 살펴보도록 하자.
이해를 쉽게 초록색을 할당된 블럭, 하늘색을 free 블럭, 보라색을 중간에 free 될 블럭이라 생각하고 살펴본다.
- case 2 : 이전 블럭이 할당되있고 다음 블럭이 free 블럭인 경우
free 블럭인 다음 블럭과 coalesce 를 해야 하므로 size 에 다음 블럭의 사이즈를 더해준다.
현재 블럭의 header 와 다음 블럭의 footer 에 PACK(size, 0) 값을 할당해준다.
- case 3 : 이전 블럭이 free 블럭이며 다음 블럭이 할당된 블럭인 경우
free 블럭인 이전 블럭과 coalesce 를 해야 하므로 size 에 이전 블럭의 사이즈를 더해준다.
이전 블럭의 header 와 현재 블럭의 footer 에 PACK(size, 0) 값을 할당해준다.
그리고 bp 는 이전 free 블럭으로 이동해줘야 한다.
- case 4 : 양쪽 블럭 전부 free 블럭인 경우
양쪽 블럭이 free 블럭으로 양쪽 블럭과 coalesce 를 해야 하므로 size 에 이전 블럭과 다음 블럭의 사이즈를
더해준다.
이전 블럭의 header 와 다음 블럭의 footer 에 PACK(size, 0) 값을 할당해준다.
그리고 case 3 과 동일하게 bp 는 이전 free 블럭으로 이동해줘야 한다.
※ mm_malloc(size_t size)
void *mm_malloc(size_t size)
{
size_t asize; /* Adjusted block size */
size_t extendsize; /* Amount to extend heap if no fit */
char *bp;
/* $end mmmalloc */
if (heap_listp == 0){
mm_init();
}
/* $begin mmmalloc */
/* Ignore spurious requests */
if (size == 0)
return NULL;
/* Adjust block size to include overhead and alignment reqs. */
if (size <= DSIZE) //line:vm:mm:sizeadjust1
asize = 2*DSIZE; //line:vm:mm:sizeadjust2
else
asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE); //line:vm:mm:sizeadjust3
/* Search the free list for a fit */
if ((bp = find_fit(asize)) != NULL) { //line:vm:mm:findfitcall
place(bp, asize); //line:vm:mm:findfitplace
return bp;
}
/* No fit found. Get more memory and place the block */
extendsize = MAX(asize,CHUNKSIZE); //line:vm:mm:growheap1
if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
return NULL; //line:vm:mm:growheap2
place(bp, asize); //line:vm:mm:growheap3
return bp;
}
heap_listp 값이 0 이면 최초로 malloc 함수를 호출한 것을 알 수 있다.
따라서, 이 경우에 mm_init() 을 하여 아래와 같은 구조를 만들어야 malloc 진행이 가능하다.
size 값에 따라서 다음과 같이 3 가지 케이스로 분류가 가능하다.
- size = 0 : NULL 을 리턴한다. (할당할 블럭이 없으니깐)
- size <= DSIZE : asize = 2*DSIZE 를 해준다. (Minimum block size = 16 (2*DSIZE))
- size > DSIZE : asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE) 를 해준다. (asize = 16, 24, 32, ... 으로 doubleword 단위로 정렬)
그 후에 find_fit(asize) 를 호출하여 할당 공간을 찾고 해당 주소를 bp 에 넣어준다.
그러면 find_fit 함수에 대해서 살펴보도록 한다.
static void *find_fit(size_t asize)
/* $end mmfirstfit-proto */
{
/* $end mmfirstfit */
#ifdef NEXT_FIT
/* Next fit search */
char *oldrover = rover;
/* Search from the rover to the end of list */
for ( ; GET_SIZE(HDRP(rover)) > 0; rover = NEXT_BLKP(rover))
if (!GET_ALLOC(HDRP(rover)) && (asize <= GET_SIZE(HDRP(rover))))
return rover;
/* search from start of list to old rover */
for (rover = heap_listp; rover < oldrover; rover = NEXT_BLKP(rover))
if (!GET_ALLOC(HDRP(rover)) && (asize <= GET_SIZE(HDRP(rover))))
return rover;
return NULL; /* no fit found */
#else
/* $begin mmfirstfit */
/* First fit search */
void *bp;
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; /* No fit */
/* $end mmfirstfit */
#endif
}
find_fit 함수는 할당할 수 있는 곳을 찾으면 바로 해당 주소를 반환하고 그 외엔 NULL 을 반환하다.
여기서 바로 해당 주소를 반환하는 것으로 best-fit 은 고려하지 않는다. (오직 first-fit, next-fit)
first-fit, next-fit 두 가지 케이스가 존재하는데, next-fit 부터 살펴보도록 한다.
- next-fit : oldrover 에 rover 를 할당한 후에 next-fit 탐색을 한다.
우선, rover 를 시작으로 하여 GET_SIZE(HDRP(rover)) = 0 일 때까지(마지막 도달) 탐색하면서 두 조건을
만족할 경우 해당 rover 를 반환해준다.
- free 공간이다. (GET_ALLOC(HDRP(rover)) = 0)
- 공간이 충분한 알맞는 공간이다. (asize <= GET_SIZE(HDRP(rover))
그리고 끝까지 탐색하지 못찾을 경우, 처음부터 oldrover(최초 rover) 까지 탐색을 시도한다.
모든 탐색을 시도했음에도 발견하지 못할 경우 NULL 을 반환하게 된다.
- first-fit : 첫 시작인 heap_listp 부터 전부 탐색을 시도하여 적합한 곳을 발견하면 반환하고
모든 탐색을 시도했음에도 발견하지 못할 경우 NULL 을 반환해준다.
다시 mm_malloc 함수로 돌아와서 적합한 곳을 찾아 bp 에 할당해주었다고 하자.
그러면 place(bp, asize) 를 통해 해당 bp 에 asize 만큼의 블럭을 만들어준다.
place 함수에 대해서 살펴보도록 한다.
static void place(void *bp, size_t asize)
/* $end mmplace-proto */
{
size_t csize = GET_SIZE(HDRP(bp));
if ((csize - asize) >= (2*DSIZE)) {
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(csize-asize, 0));
PUT(FTRP(bp), PACK(csize-asize, 0));
}
else {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
우선, csize 는 현재 free 블럭의 사이즈를 할당한 것을 알 수 있다.
편의를 위해 초록색을 asize 만큼 할당하고자 할 블럭, 하늘색을 free 블럭으로 두고 두 가지 케이스로
나눠서 살펴보도록 하자.
- csize - asize >= 2*DSIZE :
bp 의 header, footer 에 asize 를, 그리고 남은 사이즈 csize - asize 를 bp 의 다음 블럭의 header, footer 에
넣어준다.
- csize - asize < 2*DSIZE :
이 케이스는 약간 특별하다.
우선, 블럭의 최소 사이즈는 16 byte 라는 것을 감안할 때, asize 를 16, csize 를 24 라고 하면 나머지 8 byte
를 free 공간으로 남기게 된다면 이는 블럭의 최소 사이즈보다 더 작아지게 된다.
따라서, 이러한 문제를 방지하기 위해, csize 만큼의 블럭을 할당해버리는데 나머지 8 byte 는 결국 padding
을 첨가하여 해결이 가능하게 된다.
다시 mm_malloc 함수로 돌아오자.
만약 find_fit 함수를 호출하여 적합한 곳을 찾지 못하는 경우도 분명 존재할 것이다.
이 경우에는 brk pointer 를 증가시켜야 한다.
따라서 extendsize = MAX(asize, CHUNKSIZE) 를 통해 asize, CHUNKSIZE 둘 중에 더 큰 값을
extendsize 에 넣어줘야 한다.
그리고 extend_heap 함수를 호출시켜 정상적으로 brk pointer 를 증가시킨 경우, place(bp, asize)
를 실행한다.
그럼에도 불구하고 brk pointer 를 증가시키지 못하여 NULL 이 반환된 경우, mm_malloc 함수에서
파라메터로 받아온 size 또는 CHUNKSIZE 만큼 brk pointer 를 증가시키지 못한다.
※ void mm_free(void *bp)
void mm_free(void *bp)
{
/* $end mmfree */
if(bp == 0)
return;
/* $begin mmfree */
size_t size = GET_SIZE(HDRP(bp));
/* $end mmfree */
if (heap_listp == 0){
mm_init();
}
/* $begin mmfree */
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp);
}
파라메터로 받아온 void * 타입의 bp 에 대해서 해당 주소가 0 인 경우는 return 처리해준다.
size 값은 현재 bp 에 해당하는 블럭의 사이즈를 받아온다.
만약 heap_listp 가 0 인 경우는 한번도 malloc 을 하지 않은 상태이므로 mm_init() 을 해준다.
그리고 현재 free 하고자 하는 블럭의 header, footer 에 PACK(size, 0) 값을 넣어줌으로써
free 상태로 마킹한 후, coalesce 를 시도한다.
※ void *mm_realloc(void *ptr, size_t size)
void *mm_realloc(void *ptr, size_t size)
{
size_t oldsize;
void *newptr;
/* If size == 0 then this is just free, and we return NULL. */
if(size == 0) {
mm_free(ptr);
return 0;
}
/* If oldptr is NULL, then this is just malloc. */
if(ptr == NULL) {
return mm_malloc(size);
}
newptr = mm_malloc(size);
/* If realloc() fails the original block is left untouched */
if(!newptr) {
return 0;
}
/* Copy the old data. */
oldsize = GET_SIZE(HDRP(ptr));
if(size < oldsize) oldsize = size;
memcpy(newptr, ptr, oldsize);
/* Free the old block. */
mm_free(ptr);
return newptr;
}
이제 마지막 함수에 대한 설명이다.
이 함수는 기존의 ptr의 블럭 사이즈를 파라메터로 받아온 size 만큼 블럭 크기를 변경해주도록 한다.
우선, 파라메터로 받아온 size 값이 0 일 경우, 단순하게 받아온 블럭을 free 해주면 그만이다.
그리고 블럭의 해당 주소가 NULL 일 경우, 이 경우는 block 이 존재하지 않은 상태이다.
따라서 malloc 을 통해 새로 만들어주면 된다.
newptr = mm_malloc(size) 를 실행한 부분은 size 값이 적어도 1 이상이면서 ptr 이 NULL 이 아니다.
즉, 새롭게 할당한 newptr 을 통해 기존에 있던 ptr 을 newptr 에 복사한 후, ptr 을 free 시켜야 한다.
이 때, ptr 의 블럭 사이즈가 파라메터로 받아온 size 보다 클 경우 memcpy 를 하는 과정에서 불필요한
메모리 공간을 침범하는 경우가 발생할 수 있으므로 oldsize 에 size 를 할당하여 memcpy 를 해야 한다.
memcpy 를 완료하면 기존에 있던 ptr 을 free 해주고 새로 할당한 newptr 을 반환해주면 된다.
'학교에서 들은거 정리 > 시스템프로그래밍' 카테고리의 다른 글
| Garbage collection (0) | 2022.05.27 |
|---|---|
| Malloc (0) | 2022.05.27 |
| Dymaic Memory Allocation (0) | 2022.05.22 |
| Parallelism (0) | 2022.05.17 |
| Synchronization : Advanced (0) | 2022.05.12 |
