책에 있는 예제를 그대로 작성 후 코드를 분석해보았다.
성능 최적화를 하기보다는 가장 쉬운 방법만 선택해서 구현되었다.
이렇게 채점을 돌리면 딱 54점이 나온다.
mm_malloc 함수가 가장 큰 줄기를 차지한다. allocate(할당)함.
남은 free공간 중 요청받은 사이즈를 할당할만한 공간이 남았는지 확인해서(find_fit)
남았다면 place()로 할당, 남지 않았다면 extend_heap()으로 힙 공간을 늘려준다.
place()에서는 공간이 다시 분할되어야되는지 판단한다.
분할되면 bp와 header footer
header, footer를 옮겨주고 할당정보(0 or 1)를 표시한다.
mm_init은 빈 heap공간을 초기화하고 extend_heap을 호출한다.
find_fit에서는 할당할만한 free 공간 중 적절한 공간을 찾아서 그 공간의 주소값을 반환한다(first fit, next fit, best fit policy) mm_malloc에서 이 반환값을 보고 payload를 place하거나 힙공간을 추가로 할당한(extend_heap)다.
extend_heap에서는 요청된 size를 주소값에 맞게 변경해 CHUNKSIZE만큼 heap공간을 늘린 뒤 앞의 공간과 합친다. (coalesce 호출)
mm_free는 할당돼있던 메모리 공간을 free하고 coalesce를 호출해 합친다.
mm_realloc은 old_ptr와 할당할 size를 매개변수로 받는다. size에 맞는 메모리 공간을 찾아 old_ptr에 있는 데이터를 복사해 이사시킨다. 기존 데이터는 free해준다.
header & footer로만 구성된 8바이트 allocated 블록. init때 생성되어 절대 return되지 않는다.
header만 있는 0바이트 사이즈값을 저장하는 블록.
이 둘은 연결 과정 동안에 가장자리 조건을 없애주기 위한 속임수다.
static char *heap_listp
allocater는 한 개의 정적 전역변수👆를 사용하며, 항상 프롤로그 블록을 가리킨다.
CHUNKSIZE(= 2^12)를 어떻게 정했지? => 임의로 정한 듯
https://bozeury.tistory.com/entry/%ED%9E%99Heap%EA%B3%BC-%EC%8A%A4%ED%83%9DStack%EC%9D%98-%EC%B5%9C%EB%8C%80-%ED%81%AC%EA%B8%B0
/*Basic constants and macros*/
#define WSIZE 4 /*Word and header/footer size (bytes)*/
#define DSIZE 8 /*Double word size (bytes)*/
#define CHUNKSIZE (1<<12) /*Extend heap by this amount (bytes)*/
#define MAX(x, y) ((x) > (y)? (x) : (y)) /*큰 값이 앞으로 와서 짝을 지어라?*/
/* Pack a size and allocated bit into a word */ /*뭔 지 모르겠음*/
#define PACK(size, alloc) ((size) | (alloc))
/* Read and write a word at address p*/
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
/* Read the size and allocated fields from address p*/
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
/* Given block ptr bp, compute address of its header and footer*/
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
/* Giveb block ptr bp, compute address of next and previous blocks*/
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp)-WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp)-DSIZE)))
static char *heap_listp;
void *mm_malloc(size_t size)
{
size_t asize; /* Adjusted block size*/
size_t extendsize; /* Amount to extend heap if no fit */ /*공간이 모자라면 추가적으로 확장할 공간 크기*/
char *bp;
/* Ignore spurious requests : 안되는 요청 거절*/
if (size == 0)
{
return NULL;
}
/* Adjust block size to include overhead and alignment reqs. */
if (size <= DSIZE) asize = 2*DSIZE;
else asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE); /*size > DSIZE*/
// asize => padding을 포함해 조정된 payload의 크기
/* Search the free list for a fit */
if((bp = find_fit(asize)) != NULL)
{
place(bp, asize);
return bp;
}
/* No fit found. Get more memry and place the block */
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
{
return NULL;
}
place(bp, asize);
return bp;
}
static void *find_fit(size_t asize)
{ /* 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
*/
/* next-fit search */
char *bp = next_fit;
// Search from next_fit to the end of the heap
for (next_fit = bp; GET_SIZE(HDRP(next_fit)) > 0; next_fit = NEXT_BLKP(next_fit))
{
if (!GET_ALLOC(HDRP(next_fit)) && (asize <= GET_SIZE(HDRP(next_fit))))
{
// If a fit is found, return the address the of block pointer
return next_fit;
}
}
// If no fit is found by the end of the heap, start the search from the
// beginning of the heap to the original next_fit location
for (next_fit = heap_listp; next_fit < bp; next_fit = NEXT_BLKP(next_fit))
{
if (!GET_ALLOC(HDRP(next_fit)) && (asize <= GET_SIZE(HDRP(next_fit))))
{
return next_fit;
}
}
return NULL; /* No fit */
}
static void place(void *bp, size_t asize)
{
size_t csize = GET_SIZE(HDRP(bp));
if ((csize - asize) >= (2*DSIZE)){
/* 분할 후에 이 블록의 나머지가 최소 블록 크기(16 bytes)와 같거나 크다면 */
/* asize 할당 후 남은 공간 분할 후 빈 공간으로 둠 */
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));
}
}
힙을 CHUNKSIZE 바이트로 확장하고, mem_sbrk(size)를 호출한다.
static void *extend_heap(size_t words)
{
/*
새 가용 블록으로 힙 확장하기
*/
char *bp;
size_t size;
/* Allocate an even numbers of words to maintain alignment */
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
/* Initialize free block header/footer and the epilogue header */
PUT(HDRP(bp), PACK(size, 0)); /*Free block header*/
PUT(FTRP(bp), PACK(size, 0)); /*Free block footer*/
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /*New epilogue header*/
/* Coalesce if the previous block was free : Coalesce - 앞 뒤봐서 남는공간 합치기*/
return coalesce(bp);
}
int mm_init(void)
{
/*
* mm_init - Create the initial empty heap
* 최초 가용 블록으로 힙 생성하기
*/
if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1) {
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);
next_fit = heap_listp;
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}
mem_sbrk(size) : heap범위 안이라면 mem_brk의 값을 size만큼 키우고, 키우기 전의 mem_brk(old_brk)의 값을 반환한다. memlib.c 파일에 존재
void mm_free(void *bp)
{
//printf("here free is\n");
//printf("free : %p\n",bp);
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp);
}
void *mm_realloc(void *ptr, size_t size)
{
void *oldptr = ptr;
void *newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL) {
return NULL;
}
copySize = GET_SIZE(HDRP(oldptr));
if (size < copySize)
{
copySize = size;
}
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}
next_fit 변수는 어디에서 정의되어야 하나요?