C언어, 32bit 기준으로 작성.
동적 메모리 할당을 사용하는 이유
- 프로그램을 실행시키기 전에 자료구조의 크기를 알 수 없는 경우들이 있기 때문이다.
배열에 미리 넉넉하게 할당하여 쓰면 되지 않나?
- 수백만 라인의 코드와 수많은 사용자가 있는 큰 규모의 소프트웨어 제품에서는 관리하는데 어려움이 될 수 있다.
목표
1 : 처리량 극대화 ----------------- 처리 속도
2 : 메모리 이용도 최대화 ----------- 메모리 활용도
단편화(Fragmentation)
-
내부 단편화
- 할당된 블록이 데이터 보다 클 경우
- 정량화가 비교적 간단하다. (내부단편화 = 할당된 블록크기 - 데이터)
- footer optimization 등의 최적화 방법을 통해 개선할 수 있다.
-
외부 단편화
- 할당 요청을 만족시킬 수 있는 메모리 공간이 전체적으로 공간을 모았을 때는 충분한 크기이지만, 이 요청을 처리할 수 있는 단일한 가용블록은 없는 경우.
- 측정의 어려움 : 이전 요청의 패턴 & 할당기 구현 + 미래의 요청 패턴
- 많은 수의 작은 가용 블럭보다 적은 수의 더 큰 가용 블럭을 유지하는 방법을 채택한다. (측정, 예측의 어려움 때문에)
구현 이슈
- 가용블럭 구성 : 지속적으로 가용블럭을 어떻게 추적할 것인가?
- 배치 : 새롭게 블럭을 할당할 때, 가용 블럭을 어떻게 선택할 것인가?
- 분할 : 가용 블럭에 할당되고나서 어떻게 처리할 것인가?
- 연결 : 반환한 블럭을 어떻게 처리할 것인가?
묵시적 리스트 (implicit list)
- 가용 블럭이 헤더 내 필드에 의해서 묵시적으로 연결.
- 할당기는 간접적으로 가용 블록 전체 집합을 힙내의 전체 블럭을 다니면서 방문.
할당 블럭 배치 방법.
- First-fit : 처음 부터 검색해서 크기가 맞는 첫 번째 가용블럭 선택.
- Next-fit : 이전 검색이 종료된 지점에서 검색 시작.
- Best-fit : 모든 가용 블럭을 검사하여 크기가 가장 작은 블럭 선택.
명시적 할당기 구현 (C, 32bit)
1. 묵시적 리스트 - first-fit 이용.
# Score : 44 (util) + 9 (thru) = 53/100
/*
malloc lab
explicit allocator, implicit List - first_fit
Team Name:
Member 1 :
Member 2 :
Using default tracefiles in ./traces/
Perf index = 44 (util) + 9 (thru) = 53/100
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
team_t team = {
/* Team name */
"Malloc",
/* First member's full name */
"HooHoo",
/* First member's email address */
"ZZang",
/* Second member's full name (leave blank if none) */
"ZZang",
/* Second member's email address (leave blank if none) */
"MAN"
};
/* 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 */
#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 heaader and footer */
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
/* Given 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)))
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
void *heap_listp; /* Heap pointer */
void *heap_start; /* free list head */
static void *coalesce(void *);
static void *extend_heap(size_t);
static void *find_fit(size_t);
static void place(void *, size_t);
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void)
{
/* 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); /* Move heap pointer over to footer */
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}
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;
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 */
return coalesce(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 */
}
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);
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));
}
}
/*
* 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; /* 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);
/* 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;
}
/*
* mm_free - Freeing a block does nothing.
*/
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);
}
static void *coalesce(void *ptr)
{
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(ptr)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));
size_t size = GET_SIZE(HDRP(ptr));
if (prev_alloc && next_alloc) { /* Case 1 */
return ptr;
}
else if (prev_alloc && !next_alloc) { /* Case 2 */
size += GET_SIZE(HDRP(NEXT_BLKP(ptr)));
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size,0));
}
else if (!prev_alloc && next_alloc) { /* Case 3 */
size += GET_SIZE(HDRP(PREV_BLKP(ptr)));
PUT(FTRP(ptr), PACK(size, 0));
PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
ptr = PREV_BLKP(ptr);
}
else { /* Case 4 */
size += GET_SIZE(HDRP(PREV_BLKP(ptr))) + GET_SIZE(FTRP(NEXT_BLKP(ptr)));
PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(ptr)), PACK(size, 0));
ptr = PREV_BLKP(ptr);
}
return ptr;
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
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;
}
2. 묵시적 리스트 - next-fit 이용.
# Score : 43 (util) + 40 (thru) = 83/100
/*
malloc lab
explicit allocator, implicit List - next_fit
Team Name:
Member 1 :
Member 2 :
Using default tracefiles in ./traces/
Perf index = 43 (util) + 40 (thru) = 83/100
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
// 상수, 매크로
#define WSIZE 4 // 4bytes (word)
#define DSIZE 8 // 8bytes (double word)
#define CHUNKSIZE (1 << 12) // 한번에 늘릴 사이즈 설정.
#define MAX(x, y) ((x) > y ? (x): (y))
#define PACK(size, alloc) ((size) | (alloc)) // or 비트연산, 둘이 더해준다.
#define GET(p) (*(unsigned int *)(p)) // p 주소 내놔!
#define PUT(p, val) (*(unsigned int*)(p) = (val)) // p 주소에 value 입력해!
#define GET_SIZE(p) (GET(p) & ~0x7) // p 주소를 갖고와서, p & 11111000 실행. size 반환!
#define GET_ALLOC(p) (GET(p) & 0x1) // p 주소를 갖고와서, p & 00000001 실행. 할당되어 있으면 00000001 else 00000000
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
team_t team = {
/* Team name */
"zzangzzang",
/* First member's full name */
"OTL",
/* First member's email address */
"OTL",
/* Second member's full name (leave blank if none) */
"KIN",
/* Second member's email address (leave blank if none) */
"KIN"
};
#define ALIGNMENT 8
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
static char *heap_listp;
static char *find_ptr;
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){
find_ptr = bp;
return bp;
}
else if (prev_alloc && !next_alloc){
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){
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 {
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);
}
find_ptr = bp;
return bp;
}
static void *extend_heap(size_t words){
char *bp;
size_t size;
size = (words%2) ? (words+1) * WSIZE : words * WSIZE;
if ( (long)(bp = mem_sbrk(size)) == -1){
return NULL;
}
PUT(HDRP(bp), PACK(size,0));
PUT(FTRP(bp),PACK(size,0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0,1));
return coalesce(bp);
}
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));
PUT(heap_listp + (2*WSIZE), PACK(DSIZE,1));
PUT(heap_listp + (3*WSIZE), PACK(0,1));
heap_listp+= (2*WSIZE);
find_ptr = heap_listp;
if (extend_heap(CHUNKSIZE/WSIZE)==NULL)
return -1;
return 0;
}
void mm_free(void *bp){
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp),PACK(size,0));
PUT(FTRP(bp), PACK(size,0));
coalesce(bp);
}
static void *find_fit(size_t asize){
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;
}
static void *next_fit(size_t asize){ // next fit 검색
void *bp;
for (bp = NEXT_BLKP(find_ptr); GET_SIZE(HDRP(bp)) >= 0; bp = NEXT_BLKP(bp)){
if (GET_SIZE(HDRP(bp)) == 0){ // 0을 만나면(epilogue header), 힙의 시작 위치에서 다시탐색.
bp = heap_listp;
}
if (!GET_ALLOC(HDRP(bp)) && (asize<=GET_SIZE(HDRP(bp)))){
find_ptr = bp;
return bp;
}
if (bp == find_ptr){ // find_ptr 까지 왔는데 검색이 안됐으면 맞는 사이즈가 없으니 return
return NULL;
}
}
}
static void place(void *bp, size_t asize){
size_t csize = GET_SIZE(HDRP(bp));
if ( (csize-asize) >= (2*DSIZE)){ // split 이 가능한지 확인
PUT(HDRP(bp), PACK(asize,1));
PUT(FTRP(bp), PACK(asize,1));
bp = NEXT_BLKP(bp); //split 이후 free 블록으로 나눠질 블록의 bp로 이동.
PUT(HDRP(bp), PACK(csize-asize,0)); // free header
PUT(FTRP(bp), PACK(csize-asize,0)); // free footer
}
else{
PUT(HDRP(bp), PACK(csize,1)); // split 이 안되면 모두 할당
PUT(FTRP(bp), PACK(csize,1));
}
}
void *mm_malloc(size_t size){
size_t asize;
size_t extendsize;
char *bp;
if (size =< 0) return NULL;
if (size <= DSIZE){
asize = 2*DSIZE;
}
else {
asize = DSIZE* ( (size + (DSIZE)+ (DSIZE-1)) / DSIZE );
}
if ((bp = next_fit(asize)) != NULL){ // next_fit 탐색.
place(bp,asize); // 탐색 성공시 위치시킨다.
return bp;
}
// 들어갈 곳이 없으면, extend size.
extendsize = MAX(asize,CHUNKSIZE);
if ( (bp=extend_heap(extendsize/WSIZE)) == NULL){
return NULL;
}
place(bp,asize);
return bp;
}
void *mm_realloc(void *bp, size_t size){
if(size <= 0){
mm_free(bp);
return 0;
}
if(bp == NULL){
return mm_malloc(size);
}
void *newptr = mm_malloc(size);
if(newptr == NULL){
return 0;
}
size_t oldsize = GET_SIZE(HDRP(bp));
if(size < oldsize){
oldsize = size;
}
memcpy(newptr, bp, oldsize);
mm_free(bp);
return newptr;
}
3. 명시적 리스트 - LIFO
# Score : 42 (util) + 40 (thru) = 82/100
/*
malloc lab
explicit allocator, explicit free List - LIFO
Team Name:
Member 1 :
Member 2 :
Using default tracefiles in ./traces/
Perf index = 42 (util) + 40 (thru) = 82/100
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
// 상수, 매크로
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1 << 12) // 힙을 확장시킬 때 단위 설정. (12로 설정, 다른 숫자도 상관 없음)
#define MAX(x, y) ((x) > (y) ? (x): (y))
#define PACK(size, alloc) ((size) | (alloc)) // or 비트연산, 둘이 더해준다.
#define GET(p) (*(unsigned int *)(p)) // p 주소 내놔!
#define PUT(p, val) (*(unsigned int*)(p) = (val)) // p 주소에 value 입력해!
#define GET_SIZE(p) (GET(p) & ~0x7) // p 주소를 갖고와서, p & 11111000 실행. size 반환!
#define GET_ALLOC(p) (GET(p) & 0x1) // p 주소를 갖고와서, p & 00000001 실행. 할당되어 있으면 00000001 else 00000000
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
#define PRED(p) ((char *)(p)) // payload 시작점 다음블록에 이전 노드 저장.
#define SUCC(p) ((char *)(p) + WSIZE) // payload 시작점에 다음 노드를 저장.
team_t team = {
/* Team name */
"",
/* First member's full name */
"",
/* First member's email address */
"",
/* Second member's full name (leave blank if none) */
"",
/* Second member's email address (leave blank if none) */
""
};
#define ALIGNMENT 8
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
// 전역변수
static char *heap_listp = NULL; // 편의상 힙 시작점.
static char *find_ptr = NULL; // root가 가리키는 노드.
// char* a;
// a = &k;
// *a === k;
// char* find_ptr;
// find_ptr = 주소;
// *find_ptr = 값;
void add_free(char* ptr){
char* succ; // char* succ = *(unsigned int*)(find_ptr); \\ ---------------succ = **find_ptr;
succ = GET(find_ptr);
if (succ != 0){ // 루트에 연결 되어있는게 있을 때. // 루트가 가리키는 주소가 널이 아닐떄
PUT(succ, ptr); // 첫 노드의 이전 항목에 지금 갱신되는 것을 넣어주고.
}
PUT(SUCC(ptr), succ); // ptr의 다음 노드를 첫번째 노드로 연결 시켜준다.
PUT(find_ptr, ptr); // 루트가 가리키는 애를 새로들어온 애로 바꾼다.
}
void fix_link(char *ptr){ // fix과정은 무조건 연결을 끊어줌
if(GET(PRED(ptr)) == NULL){ // 첫노드
if(GET(SUCC(ptr)) != NULL){ // 다음 노드가 연결되어있으면,
PUT(PRED(GET(SUCC(ptr))), 0); // 다음 노드의 주소의 이전 노드의 주소를 지운다.
}
PUT(find_ptr, GET(SUCC(ptr))); // 루트 노드가 첫 노드가 가리키던 다음 노드를 가리키게 한다.
}
else{ // 루트노드 이외에 다른 노드일 때
if(GET(SUCC(ptr)) != NULL){ // 전, 후 모두 노드가 연결되어있으면
PUT(PRED(GET(SUCC(ptr))), GET(PRED(ptr))); // 다음노드의 주소의 이전노드값을 지금 노드의 이전값과 연결시킨다.
}
PUT(SUCC(GET(PRED(ptr))), GET(SUCC(ptr))); // 이전 노드에 입력되어있던 다음 노드 주소에 지금 노드의 다음노드 주소를 넣어준다.
}
PUT(SUCC(ptr), 0); // 현재 노드의 SUCC, PRED 초기화
PUT(PRED(ptr), 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){
// 둘다 할당 되어 있으면, free 리스트에 추가만 해주면 된다.
}
else if (prev_alloc && !next_alloc){
size += GET_SIZE(HDRP(NEXT_BLKP(bp))); // 다음 블록의 헤더를 보고 그 블록의 크기만큼 지금 블록의 사이즈에 추가한다.
fix_link(NEXT_BLKP(bp)); // 다음 블록을 합쳐주고 초기화
PUT(HDRP(bp), PACK(size,0)); // 헤더 갱신(더 큰 크기로 PUT)
PUT(FTRP(bp), PACK(size,0)); // 푸터 갱신
}
else if(!prev_alloc && next_alloc){
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
fix_link(PREV_BLKP(bp));// 이전 블록을 합쳐주고 초기화
PUT(FTRP(bp), PACK(size,0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size,0));
bp = PREV_BLKP(bp);
}
else {
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
fix_link(PREV_BLKP(bp));// 전블록
fix_link(NEXT_BLKP(bp));// 다음블록
PUT(HDRP(PREV_BLKP(bp)), PACK(size,0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size,0));
bp = PREV_BLKP(bp);
}
add_free(bp);
return bp;
}
static void *extend_heap(size_t words){
char *bp;
size_t size;
size = (words%2) ? (words+1) * DSIZE : words * DSIZE;
if ( (long)(bp = mem_sbrk(size)) == -1){ // 올림.
return NULL;
}
PUT(HDRP(bp), PACK(size,0));
PUT(FTRP(bp), PACK(size,0));
PUT(PRED(bp), 0);
PUT(SUCC(bp), 0);
PUT(HDRP(NEXT_BLKP(bp)), PACK(0,1));
return coalesce(bp);
}
int mm_init(void){
if ((heap_listp = mem_sbrk(4*WSIZE)) == (void*) -1){ // 16바이트 만큼 확보한다. (unused + PH + PF + SUC + PRED + EH)
return -1;
}
PUT(heap_listp, 0); // unused word 4 bytes, heap_listp 주소의 key값을 0으로 입력
PUT(heap_listp + (1*WSIZE), PACK(DSIZE,1)); // prologue header -> (8바이트(헤더푸터), 할당됨.)
PUT(heap_listp + (2*WSIZE), PACK(DSIZE,1)); // prologue footer생성.
PUT(heap_listp + (3*WSIZE), PACK(0,1)); // 에필로그 블록헤더
find_ptr = heap_listp; // find_ptr 은 heap_listp의 주소값을 복사한다.
heap_listp += (2*WSIZE);
if (extend_heap(CHUNKSIZE/WSIZE)==NULL)
return -1;
return 0;
}
void mm_free(void *bp){
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size,0));
PUT(FTRP(bp), PACK(size,0));
PUT(SUCC(bp), 0);
PUT(PRED(bp), 0);
coalesce(bp);
}
static void *find_fit(size_t asize){ // first fit
char *get_address = GET(find_ptr);
while (get_address != NULL){
if (GET_SIZE(HDRP(get_address)) >= asize){
return get_address;
}
get_address = GET(SUCC(get_address));
}
return NULL; // not fit any
}
static void place(void *bp, size_t asize){
size_t csize = GET_SIZE(HDRP(bp)); // 현재 블록
fix_link(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));
PUT(SUCC(bp), 0);
PUT(PRED(bp), 0);
coalesce(bp);
}
else{
PUT(HDRP(bp), PACK(csize,1));
PUT(FTRP(bp), PACK(csize,1));
}
}
void *mm_malloc(size_t size){
size_t asize;
size_t extendsize;
char *bp;
if (size <= 0) return NULL; // 0 보다 같거나 작으면 할당해 줄 필요 없다.
if (size <= DSIZE){
asize = 2*DSIZE;
}
else {
asize = DSIZE* ( (size + (DSIZE)+ (DSIZE-1)) / DSIZE ); // Double word allignment
}
if ((bp = find_fit(asize)) != NULL){ //first fit
place(bp,asize);
return bp;
}
extendsize = MAX(asize,CHUNKSIZE);
if ( (bp=extend_heap(extendsize/DSIZE)) == NULL){
return NULL; // 확장이 안되면 NULL 반환해라.
}
place(bp,asize); // 확장이 되면 넣어라.
return bp;
}
void *mm_realloc(void *bp, size_t size){
if(size <= 0){
mm_free(bp);
return 0;
}
if(bp == NULL){
return mm_malloc(size);
}
void *newptr = mm_malloc(size);
if(newptr == NULL){
return 0;
}
size_t oldsize = GET_SIZE(HDRP(bp));
if(size < oldsize){
oldsize = size;
}
memcpy(newptr, bp, oldsize);
mm_free(bp);
return newptr;
}
이후띵's 개발일지