malloc_implicit 구현
기본 상수 및 매크로
/* Basic constants and macros */
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1<<12)
#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) // 최하위비트(LSB : Least Significant Bit) 3비트(0x7 == 111)를 제외한 나머지 반환
#define GET_ALLOC(p) (GET(p) & 0x1) // LSB 1비트 반환(1 또는 0)
/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp) ((char *)(bp) - WSIZE) // 블록 맨 앞: bp에서 - 1워드
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // 블록 맨 뒤: bp에서 + block size(헤더에서 값 추출) - 2워드(footer, next header의 사이즈)
/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE((char *)(bp) - WSIZE)) // bp에서 + block size
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE)) // bp에서 - pre_block size(pre_footer에서 값 추출)
- WSIZE : 1 Word
- Dsize : 2 Word, 블록의 단위
- CHUNKSIZE : 초기 가용 블록과 힙 확장 시 추가되는 블록 크기
- PACK : 비트 연산을 통해 size와 alloc을 표시한 상수값 반환
- GET(p) : p가 가리키는 블록의 value 반환
- PUT(p,val) : p가 가리키는 블록에 value를 입력
- GET_SIZE(p) : 헤더/풋터에 적혀있는 사이즈 반환
- GET_ALLOC(p) : 헤더/풋터에 가용 여부(1 또는 0) 반환
- HDPR(bp) : 현재 블록의 헤더의 위치 반환
- FTRP(bp) : 현재 블록의 풋터의 위치 반환init
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)); // prologue header
PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); // prologue footer
PUT(heap_listp + (3*WSIZE), PACK(0,1)); // epliogue header
heap_listp += (2*WSIZE);
/* Extend the empth heap with a free block of CHUNKSIZE bytes */
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}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; // size를 2워드 기준으로 업데이트
if ((long)(bp = mem_sbrk(size)) == -1) // 블록을 가용할 수 없다면 NULL
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)); // alloc epilogue header
/* Coalesce if the previous block was free */
return coalesce(bp);
}malloc
void *mm_malloc(size_t size)
{
size_t asize;
size_t extendsize;
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); // '/'는 정수형 반환, DSIZE * 블록의 개수
/* Search the free list for a fit */
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
/* No fit found. Get more memory and place the block */
extendsize = MAX(asize,CHUNKSIZE);
if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
return NULL;
place(bp, asize);
return bp;
}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);
}coalesce
앞 블록과 뒷 블록이 가용상태인지 확인하여, 가용상태이면 연결한다.
경우가 4가지로 나뉜다.
1) 앞 뒤 블록이 가용이 아닐 때(할당되었을 때, 1&1)
2) 앞 블록은 가용이고, 뒷 블록은 할당일 때(1&0)
3) 앞 블록은 할당이고, 뒷 블록은 가용일 때(0&1)
4) 앞 뒤 블록 가용일 때(0&0)
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 (1&1)*/
return bp;
}
else if (prev_alloc && !next_alloc) { /* case 2 (1&0)*/
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 (0&1)*/
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 (0&0)*/
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;
}find_fit
적절한 가용 블록이 있는지 first-fit 방식으로 찾는다. 즉 heap_listp에서 시작해 모든 블럭을 탐색한다.
1) 만약 블록이 가용가능하고(GET_ALLOC == 1), 사이즈(GET_SIZE)가 원하는 사이즈보다 크면, bp를 반환한다. (반환된 bp는 malloc함수에서 데이터를 배치할 때 쓰인다.)
2) 만약 적절한 헤더가 아니라면 다음 블록으로 이동해서 다시 판단한다.
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)) { // start: bp, bp를 next_bp로 업데이트
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) { // 0 and asize
return bp;
}
}
return NULL; /* No fit*/
}place
place 함수는 가용할 수 있는 블록의 bp와 배치할 용량을 할당받는다.
1) 가용블록과 배치할 용량의 차이(csize-asize)가 4 Word와 비교하여,
1-1) 작으면 해당 블록을 모두 사용한다.
1-2) 크면 나머지를 분할하여 새로운 가용 블럭으로 사용한다.
static void place(void *bp, size_t asize)
{
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); // 블록의 나머지가 16바이트 이상이면 분할
PUT(HDRP(bp), PACK(csize-asize,0)); // 리스트가 모두 연결되어 있으므로 0으로 갱신
PUT(FTRP(bp), PACK(csize-asize,0));
}
else {
PUT(HDRP(bp), PACK(csize,1));
PUT(FTRP(bp), PACK(csize,1));
}
}realloc
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;
}
🏸⛰️🏄♀️🎳🚲⛳☕📈🎥