jun-wiki
Pages (Latest 10 updated) :
TIL 25
오늘의 목표는 묵시적 할당기인 동적 할당기를 명시적 할당기로 전환하는게 목표다
이중 연결리스트 방식이기에 pred/succ 만들어 연결해 줄거다
최소 할당 크기 변환도 고려해보았는데 16바이트 안에 다 들어가니까 문제 없을 거 같다
실제 가용 블록 될때에는 사용자가 알아서 쓸테니까 걍 페이지로드에 pred/succ 박아놓을 계획이다
뭐, 정 문제 생기면 페이지로드 초기화 명령어 넣으면 되겠지
목표
일단 바꿀 목표부터 정하고 이뤄나가야 겠다
- pred/succ 매크로
- 힙 익스텐드에 pred/succ 배치
- 배치과정에 리스트 연결 조작
- free 과정에 리스트 연결 조작
- 병합 과정에 리스트 연결 조작
- realloc 과정에 리스트 연결 조작
모아놓고 보니 전부 같은 소리긴 하다
1트
바로 들어가 보자
pred/succ매크로
/* 추가 확장으로 pred/succ */
#define PRED_FIELD(bp) ((char *)(bp) + 0)
#define SUCC_FIELD(bp) ((char *)(bp) + PSIZE)
/* pred/succ 접근 매크로 */
#define GET_PRED(bp) ((void*)GET(PRED_FIELD(bp)))
#define SET_PRED(bp, x) (PUT(PRED_FIELD(bp), (unsigned int)(x)))
#define GET_SUCC(bp) ((void*)GET(SUCC_FIELD(bp)))
#define SET_SUCC(bp, x) (PUT(SUCC_FIELD(bp), (unsigned int)(x)))
pred는 페이로드 시작이니 걍 bp로 가리키고 succ는 포인터 사이즈 만큼 이동해서 다시 가리키면 된다
그리고 값 접근하는 경우는 매번 타입 캐스팅하고 이런거 자신 없어서 한번에 다 정해줬다
값을 받고 쓸때는 void로 변환하고
저장할때에는 부호없는 정수 형식으로 저장한다고 보면된다
- pred/succ 매크로
- 힙 익스텐드에 pred/succ 배치
- 배치과정에 리스트 연결 조작
- free 과정에 리스트 연결 조작
- 병합 과정에 리스트 연결 조작
- realloc 과정에 리스트 연결 조작
다음으로 가자
힙 익스텐드
뭐 건드려야 할지 모르겠어서
SET_PRED(NEXT_BLKP(bp), bp);
SET_SUCC(bp, NEXT_BLKP(bp));
이거 2줄 추가하고 넘어갔다
다음 블록 에필로그 헤더면 어찌 될지 모르겠다
if문 넣어서 하고 싶은데 비효율적일까봐 일단 빼고 오류 생기거나 하면 고려해 봐야겠다
배치과정
배치 과정까지 오다 보니까 문제 발견했다
위에 코드 복붙 똑같은 걸 끼워 쓰다 보니
NEXT_BLKP같은 걸 쓰면 다음 블록(물리적 위치) 이지 실제 연결리스트가 아닌 거시다…
그래서 매크로 다시 싹 고쳤다
2트
관련 매크로 수정하고 새로 만들어 보겠다
매크로
기존 것들은 그대로 유지하고 새로 추가했다
-
현재 블록 리스트에서 제거하고 연결리스트 앞뒤끼리 연결
-
블록 a, b 연결
-
블록 a, b 사이에 c 넣기
이렇게 3개 만들었다
/* bp를 free-list에서 제거: pred ↔ succ 서로 물리기 */
#define UNLINK(bp) do { \
void* _bp = (bp); \
void* _pred = GET_PRED(_bp); \
void* _succ = GET_SUCC(_bp); \
if (_pred) SET_SUCC(_pred, _succ); \
if (_succ) SET_PRED(_succ, _pred); \
} while (0)
/* a ↔ b 를 서로 물림 (NULL 허용) */
#define LINK(a, b) do { \
if (a) SET_SUCC((a), (b)); \
if (b) SET_PRED((b), (a)); \
} while (0)
/* bp를 앞뒤 사이에 넣기 */
#define INSERT_BETWEEN(prev, bp, next) do { \
SET_PRED((bp), (prev)); \
SET_SUCC((bp), (next)); \
if (prev) SET_SUCC((prev), (bp)); \
if (next) SET_PRED((next), (bp)); \
} while (0)
init
좀 이리저리 구른 결과 여기서부터 손봐야 된다는 걸 알아냈다
가용 리스트를 만들어 운용한다고 쳐도 앞에 프롤로그거나 뒤가 에필로그면 어떻게 운용할지 모르겠어서 말이다
그래서 새로 연결리스트용 포인터 헤드를 만들어줬다
/* 리스트 헤드용 포인터 만듦 */
static void *free_head = NULL;
그리고 init도 LIFO 방식으로 업뎃 했다
int mm_init(void)
{
if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
return -1;
PUT(heap_listp + (0*WSIZE), 0);
PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); // 프롤로그 헤더
PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); // 프롤로그 푸터
// 실제 힙 확장하고 사용자 메모리 들어갈 곳
PUT(heap_listp + (3*WSIZE), PACK(0, FL_ALLOC | FL_PREV_ALLOC)); // 에필로그 헤더 (힙 영역 마무리)
heap_listp += (2*WSIZE);
/* 리스트 포인터 초기화 */
free_head = NULL;
void *bp = extend_heap(CHUNKSIZE/WSIZE);
if (bp == NULL) return -1;
// extend_heap에서 만든 가용 블록을 free-list 헤드에 삽입 (LIFO)
SET_PRED(bp, NULL);
SET_SUCC(bp, free_head);
if (free_head) SET_PRED(free_head, bp);
free_head = bp;
return 0;
}
새로 생긴 가용 블록을 리스트 맨 앞에 넣는 방식으로 처리
LIFO 쓸거라 관련함수 만들었다
해제나 이런거에 쓸려니까 하나 필요해서 말이다
#define INSERT_FRONT(bp) do { \
SET_PRED((bp), NULL); \
SET_SUCC((bp), free_head); \
if (free_head) SET_PRED(free_head, (bp)); \
free_head = (bp); \
} while (0)
힙 익스텐드
밥 먹고 와서 만들었는데…
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;
// 확장전 에필로그 바로 뒤
unsigned int old_ep = GET(HDRP(bp));
// 직전 블록 할당 상태
unsigned int prev = old_ep & FL_PREV_ALLOC;
// init 할때랑 동일
PUT(HDRP(bp), PACK(size, prev));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, FL_ALLOC));
bp = coalesce(bp);
// LIFO 삽입 방식
SET_PRED(bp, NULL);
SET_SUCC(bp, free_head);
if (free_head) SET_PRED(free_head, bp);
free_head = bp;
// 병합
return bp;
}
LIFO를 매번 하기 어려워 힙익스텐드로 옮겼기에 init의 LIFO는 제거했다
find fit
malloc은 딱히 건들 거 없어 보여서 내버려 두고 find_fit 손봤다
static void *find_fit(size_t asize) {
for (void *bp = free_head; bp != NULL; bp = GET_SUCC(bp)) {
if (GET_SIZE(HDRP(bp)) >= asize) return bp;
}
return NULL;
}
널가드에다가 리스트 순회로 전환했다
first fit이면 충분 할 거 같아 안바꿨다
배치
static void place(void *bp, size_t asize) {
size_t csize = GET_SIZE(HDRP(bp));
size_t remainder = csize - asize;
if (remainder >= MIN_BLOCK) {
UNLINK(bp);
PUT(HDRP(bp), PACK(asize, GET_PREV_ALLOC(HDRP(bp)) | 0x1));
char *nbp = NEXT_BLKP(bp);
PUT(HDRP(nbp), PACK(remainder, FL_PREV_ALLOC));
PUT(FTRP(nbp), PACK(remainder, 0));
// nbp free-list에 삽입 LIFO
INSERT_FRONT(nbp);
// nbp 다음 블록 헤드 prev_alloc = 0
PUT(HDRP(NEXT_BLKP(nbp)), GET(HDRP(NEXT_BLKP(nbp))) & ~FL_PREV_ALLOC);
}
else {
UNLINK(bp);
PUT(HDRP(bp), PACK(csize, GET_PREV_ALLOC(HDRP(bp)) | 0x1)); // 내 prev 유지 + alloc=1
unsigned int nh = GET(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(NEXT_BLKP(bp)), nh | FL_PREV_ALLOC); // 다음 헤더에 prev_alloc=1만 OR
}
}
배치의 경우 UNLINK먼저 하고
분할해서 남는 것들은
free-list에 LIFO로 추가하게 수정했다
병합
병합은 의외로 그리 안어려웠는데
걍 기존 코드 맨 앞줄에 UNLINK 붙여서 가용블록에서만 떼주는 거 했다
뭐, 틀렸을 수도 있다
static void *coalesce(void *bp)
{
size_t prev_alloc = GET_PREV_ALLOC(HDRP(bp));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
// case 1 앞뒤 둘다 가용 불가
if (prev_alloc && next_alloc) {
return bp;
}
// case 2 다음 블록 가용가능
else if (prev_alloc && !next_alloc) {
UNLINK(NEXT_BLKP(bp)); // 다음 블록 언링크
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, GET_PREV_ALLOC(HDRP(bp)))); // 앞 상태 보존
PUT(FTRP(bp), PACK(size, 0));
}
// case 3 이전 블록 가용가능
else if (!prev_alloc && next_alloc) {
void *pp = PREV_BLKP(bp);
UNLINK(pp); // 이전 블록 언링크
size += GET_SIZE(HDRP(pp));
unsigned int prevprev = GET_PREV_ALLOC(HDRP(pp)); // 병합 후 블록의 prev_alloc
PUT(HDRP(pp), PACK(size, prevprev));
PUT(FTRP(pp), PACK(size, 0));
bp = pp;
}
// case 4 앞뒤 둘다 가용 가능
else {
void *pp = PREV_BLKP(bp);
void *np = NEXT_BLKP(bp);
UNLINK(pp); // 이전 블록 언링크
UNLINK(np); // 다음 블록 언링크
size += GET_SIZE(HDRP(pp)) + GET_SIZE(HDRP(np));
unsigned int prevprev = GET_PREV_ALLOC(HDRP(pp));
PUT(HDRP(pp), PACK(size, prevprev));
PUT(FTRP(np), PACK(size, 0));
bp = pp;
}
unsigned int nh = GET(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(NEXT_BLKP(bp)), nh & ~FL_PREV_ALLOC); // 다음 헤더 prev_alloc=0
return bp;
}
재할당
개같은 재할당 기존꺼 쓰다가 한번 최적화겸 할려고 했는데
그냥 너무 어지럽다
일단 케이스 쪼개길 몇번 해서 흐름부터 잡았다
대격변
재할당 하나 바꾸려다 보니까 이것저것 손좀 많이 댔다
어차피 무푸터 방식이기에 asize 정해주는 공식 손 봤고 분할을 따로 함수로 빼서 활용성을 높였다
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)
asize = MAX(MIN_BLOCK, ALIGN(size + WSIZE))
새 asize 공식이다 한줄로 쇼부 본다 최소 블록이냐 아니면 size에 헤더 합친걸로 정렬하냐로 말이다
기존에 단순히 복사하고 맞는 블록에 붙여쓰기 하던 realloc 개조했고 말이다
그래도 전체적 흐름은 동일하다
재할당
void *mm_realloc(void *ptr, size_t size)
{
if (ptr == NULL) return mm_malloc(size);
if (size == 0) { mm_free(ptr); return NULL; }
size_t oldsize = GET_SIZE(HDRP(ptr));
size_t payload = oldsize - 2*WSIZE;
size_t asize;
if (size <= DSIZE) asize = 2*DSIZE;
else asize = DSIZE * ((size + (DSIZE-1)) / DSIZE) + 2*WSIZE;
if (asize <= oldsize) {
return ptr;
}
void *newptr = mm_malloc(size);
if (newptr == NULL) return NULL;
size_t copySize = (size < payload) ? size : payload;
memcpy(newptr, ptr, copySize);
mm_free(ptr);
return newptr;
}
기존의 코드다
그냥 기존 블록 free하고 새로 검색해서 거기에다가 복사 붙여넣기하는 간단한 방법이다
그리고 우리가 구연해야 할 건
무푸터 방식에다가 연결리스트이기에 이것저것 해줘야 한다
-
축소, 확장 나눔
-
축소하는 경우
-
자르고 남은 블록이 최소 크기 이상이면 새 블록
-
최소 크기 이하시 병합
-
-
확장하는 경우
-
현재 블록 오른쪽 확인해서 병합
-
오른쪽이 에필로그일 경우 힙익스텐드로 확장
-
-
둘 다 안될 경우 새 블록으로 이사
기본적인 흐름이다
축소하는 경우의 분할 부터 만들어야 한다
나 같은 경우는 배치에서 떼와서 만들었다
static void split_tail(void *bp, size_t asize) {
size_t csize = GET_SIZE(HDRP(bp));
size_t remainder = csize - asize;
if (remainder >= MIN_BLOCK) {
PUT(HDRP(bp), PACK(asize, GET_PREV_ALLOC(HDRP(bp)) | 0x1));
void *nbp = NEXT_BLKP(bp);
PUT(HDRP(nbp), PACK(remainder, FL_PREV_ALLOC));
PUT(FTRP(nbp), PACK(remainder, 0));
// nbp free-list에 삽입 LIFO
INSERT_FRONT(nbp);
// nbp 다음 블록 헤드 prev_alloc = 0
PUT(HDRP(NEXT_BLKP(nbp)), GET(HDRP(NEXT_BLKP(nbp))) & ~FL_PREV_ALLOC);
}
else {
PUT(HDRP(bp), PACK(csize, GET_PREV_ALLOC(HDRP(bp)) | 0x1)); // 내 prev 유지 + alloc=1
unsigned int nh = GET(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(NEXT_BLKP(bp)), nh | FL_PREV_ALLOC); // 다음 헤더에 prev_alloc=1만 OR
}
}
이사는 기존 코드 재활용했고 확장을 새로 만들었다
다음 블록 가용 가능할 경우 크기 확인 후 병합, 에필로그일 경우 힙 확장 후 다시금 병합
이도저도 아닐 경우 이사로 이동하게 말이다
void *mm_realloc(void *ptr, size_t size)
{
if (ptr == NULL) return mm_malloc(size);
if (size == 0) { mm_free(ptr); return NULL; }
size_t oldsize = GET_SIZE(HDRP(ptr));
size_t payload = oldsize - WSIZE;
size_t asize = MAX(MIN_BLOCK, ALIGN(size + WSIZE));
// 축소
if (asize <= oldsize) {
split_tail(ptr, asize);
return ptr;
// 확장
} else {
void *next = NEXT_BLKP(ptr);
if (!GET_ALLOC(HDRP(next)) && oldsize + GET_SIZE(HDRP(next)) >= asize) {
UNLINK(next);
size_t combined = oldsize + GET_SIZE(HDRP(next));
PUT(HDRP(ptr), PACK(combined, FL_ALLOC | GET_PREV_ALLOC(HDRP(ptr))));
split_tail(ptr, asize);
return ptr;
} else if (GET_SIZE(HDRP(NEXT_BLKP(ptr))) == 0) {
if (extend_heap(MAX(asize - oldsize, CHUNKSIZE)/WSIZE) != NULL) {
next = NEXT_BLKP(ptr);
UNLINK(next);
size_t combined = oldsize + GET_SIZE(HDRP(next));
PUT(HDRP(ptr), PACK(combined, FL_ALLOC | GET_PREV_ALLOC(HDRP(ptr))));
split_tail(ptr, asize);
return ptr;
}
}
// 이사
void *new = mm_malloc(size);
if (new == NULL) return NULL;
size_t copySize = (size < payload) ? size : payload;
memcpy(new, ptr, copySize);
mm_free(ptr);
return new;
}
}
완성코드다
…
안타깝게도 빌드가 안된다…
3트
솔직히 말하면 23트쯤 된다
그치만 기록 안남겼으니 무효다
문제는 MIN_BLOCK을 명시적 할당기에 어울리게 바꿔져야 한다는 것이었다
이를 통해 asize랑 payload계산 새로 하고 말이다
// 기존: #define MIN_BLOCK (2*DSIZE) // 16 (X)
#define OVERHEAD (2*WSIZE) // 헤더(4) + 푸터(4) = 8
#define MIN_BLOCK ALIGN(OVERHEAD + 2*PSIZE)
// free 블록은 pred/succ 두 포인터가 payload에 필요
// 64비트라면 8*2 + 8 = 24바이트 → ALIGN 하면 24 그대로
// 기존: asize = MAX(MIN_BLOCK, ALIGN(size + WSIZE)); // (X)
// 헤더만 더해서 size 기록 -> FTRP가 -DSIZE(=8) 가정과 충돌
asize = MAX(MIN_BLOCK, ALIGN(size + OVERHEAD)); // (O)
// 기존: size_t payload = oldsize - WSIZE; // (X)
size_t payload = oldsize - OVERHEAD; // (O)
그래도 뻐킹 빌드가 안된다…
…
pred/succ를 거지같이 짜놔서 안되는 거였다…
이것도 다시 짜니 상당히 어지럽다
#define PRED_FIELD(bp) ((char *)(bp) + 0)
#define SUCC_FIELD(bp) ((char *)(bp) + PSIZE)
// 포인터 전용 매크로
#define PRED_PTR(bp) (*(void **)(PRED_FIELD(bp)))
#define SUCC_PTR(bp) (*(void **)(SUCC_FIELD(bp)))
// 접근 매크로 교체
// 기존 (X)
// #define GET_PRED(bp) ((void*)GET(PRED_FIELD(bp)))
// #define SET_PRED(bp, x) (PUT(PRED_FIELD(bp), (unsigned int)(x)))
// #define GET_SUCC(bp) ((void*)GET(SUCC_FIELD(bp)))
// #define SET_SUCC(bp, x) (PUT(SUCC_FIELD(bp), (unsigned int)(x)))
// 새로 (O)
#define GET_PRED(bp) (PRED_PTR(bp))
#define SET_PRED(bp, x) (PRED_PTR(bp) = (x))
#define GET_SUCC(bp) (SUCC_PTR(bp))
#define SET_SUCC(bp, x) (SUCC_PTR(bp) = (x))
그래도 수정하니 빌드 성공해서
점수도 나왔다
Results for mm malloc:
trace valid util ops secs Kops
0 yes 89% 5694 0.000091 62298
1 yes 92% 5848 0.000052112031
2 yes 94% 6648 0.000128 51897
3 yes 96% 5380 0.000088 60998
4 yes 66% 14400 0.000065221198
5 yes 88% 4800 0.000266 18059
6 yes 85% 4800 0.000272 17621
7 yes 55% 12000 0.000652 18405
8 yes 51% 24000 0.000667 35987
9 yes 33% 14401 0.011277 1277
10 yes 30% 14401 0.000147 97899
Total 71% 112372 0.013706 8199
Perf index = 43 (util) + 40 (thru) = 83/100
으음…
영 만족스럽지 못한 결과다
83점의 벽에 막혔으니 말이다…
리스트 여러개 운용하는 세그리게이티드 방식으로 다음에 시도해보아야겠다
전체코드 대충 던져놓고 마무리 하겠다
/*
* mm-naive.c - The fastest, least memory-efficient malloc package.
*
* In this naive approach, a block is allocated by simply incrementing
* the brk pointer. A block is pure payload. There are no headers or
* footers. Blocks are never coalesced or reused. Realloc is
* implemented directly using mm_malloc and mm_free.
*
* NOTE TO STUDENTS: Replace this header comment with your own header
* comment that gives a high level description of your solution.
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
/*********************************************************
* NOTE TO STUDENTS: Before you do anything else, please
* provide your team information in the following struct.
********************************************************/
team_t team = {
/* Team name */
"ateam",
/* First member's full name */
"Harry Bovik",
/* First member's email address */
"bovik@cs.cmu.edu",
/* Second member's full name (leave blank if none) */
"",
/* Second member's email address (leave blank if none) */
""};
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1<<12)
#define OVERHEAD (2*WSIZE)
#define MIN_BLOCK ALIGN(OVERHEAD + 2*PSIZE)
#define PSIZE ((int)sizeof(void*))
#define MAX(x, y) ((x) > (y)? (x) : (y))
/*
* size = 블록의 전체 크기
* flags = 하위 비트 플래그로 사용
* alloc = 할당 상태 비트 0x1
* prev_alloc = 직전 블록 할당 상태 비트 0x2
* p = 일반 포인터 (헤더/푸터 가리킬 때 씀)
* bp = 블록 포인터 (페이로드의 시작 주소)
*/
#define PACK(size, flags) ((size) | (flags))
#define FL_ALLOC 0x1 // 현재 블록 할당됨
#define FL_PREV_ALLOC 0x2 // 직전 블록 할당됨
#define FL_NONE 0x0
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & FL_ALLOC)
#define GET_PREV_ALLOC(p) (GET(p) & FL_PREV_ALLOC)
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
/* 추가 확장으로 pred/succ 만들거임 ㅇㅋ? */
#define PRED_FIELD(bp) ((char *)(bp) + 0)
#define SUCC_FIELD(bp) ((char *)(bp) + PSIZE)
// 포인터 전용 매크로
#define PRED_PTR(bp) (*(void **)(PRED_FIELD(bp)))
#define SUCC_PTR(bp) (*(void **)(SUCC_FIELD(bp)))
#define GET_PRED(bp) (PRED_PTR(bp))
#define SET_PRED(bp, x) (PRED_PTR(bp) = (x))
#define GET_SUCC(bp) (SUCC_PTR(bp))
#define SET_SUCC(bp, x) (SUCC_PTR(bp) = (x))
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp)) - DSIZE))
/* bp를 free-list에서 제거: pred ↔ succ 서로 물리기
* + pred 없으면 리스트 포인터 지금이 맨앞임
*/
#define UNLINK(bp) do { \
void* _bp = (bp); \
void* _pred = GET_PRED(_bp); \
void* _succ = GET_SUCC(_bp); \
if (_pred) SET_SUCC(_pred, _succ); else free_head = _succ; \
if (_succ) SET_PRED(_succ, _pred); \
} while (0)
#define INSERT_FRONT(bp) do { \
SET_PRED((bp), NULL); \
SET_SUCC((bp), free_head); \
if (free_head) SET_PRED(free_head, (bp)); \
free_head = (bp); \
} while (0)
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
static void *heap_listp;
static void *extend_heap(size_t words);
static void *coalesce(void *bp);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);
static void split_tail(void *bp, size_t asize);
/* 리스트 헤드용 포인터 만듦 */
static void *free_head = NULL;
int mm_init(void)
{
if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
return -1;
PUT(heap_listp + (0*WSIZE), 0);
PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); // 프롤로그 헤더
PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); // 프롤로그 푸터
// 실제 힙 확장하고 사용자 메모리 들어갈 곳
PUT(heap_listp + (3*WSIZE), PACK(0, FL_ALLOC | FL_PREV_ALLOC)); // 에필로그 헤더 (힙 영역 마무리)
heap_listp += (2*WSIZE);
/* 리스트 포인터 초기화 */
free_head = NULL;
void *bp = extend_heap(CHUNKSIZE/WSIZE);
if (bp == NULL) return -1;
return 0;
}
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;
// 확장전 에필로그 바로 뒤
unsigned int old_ep = GET(HDRP(bp));
// 직전 블록 할당 상태
unsigned int prev = old_ep & FL_PREV_ALLOC;
// init 할때랑 동일
PUT(HDRP(bp), PACK(size, prev));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, FL_ALLOC));
bp = coalesce(bp);
// LIFO 삽입 방식
SET_PRED(bp, NULL);
SET_SUCC(bp, free_head);
if (free_head) SET_PRED(free_head, bp);
free_head = bp;
// 병합
return bp;
}
void *mm_malloc(size_t size)
{
size_t asize;
size_t extendsize;
char *bp;
if (size == 0)
return NULL;
asize = MAX(MIN_BLOCK, ALIGN(size + OVERHEAD));
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
// 힙 익스텐드하고 재할당
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) {
for (void *bp = free_head; bp != NULL; bp = GET_SUCC(bp)) {
if (GET_SIZE(HDRP(bp)) >= asize) return bp;
}
return NULL;
}
static void place(void *bp, size_t asize) {
UNLINK(bp);
split_tail(bp, asize);
}
void mm_free(void *ptr)
{
size_t size = GET_SIZE(HDRP(ptr));
unsigned int prev = GET_PREV_ALLOC(HDRP(ptr)); // 덮어쓰기 전에 읽기
PUT(HDRP(ptr), PACK(size, prev)); // alloc=0, prev 유지
PUT(FTRP(ptr), PACK(size, 0)); // 가용 푸터 작성
unsigned int nh = GET(HDRP(NEXT_BLKP(ptr)));
PUT(HDRP(NEXT_BLKP(ptr)), nh & ~0x2); // 다음 헤더 prev_alloc=0으로 클리어
void *bp = coalesce(ptr);
INSERT_FRONT(bp);
}
static void *coalesce(void *bp)
{
size_t prev_alloc = GET_PREV_ALLOC(HDRP(bp));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
// case 1 앞뒤 둘다 가용 불가
if (prev_alloc && next_alloc) {
return bp;
}
// case 2 다음 블록 가용가능
else if (prev_alloc && !next_alloc) {
UNLINK(NEXT_BLKP(bp)); // 다음 블록 언링크
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, GET_PREV_ALLOC(HDRP(bp)))); // 앞 상태 보존
PUT(FTRP(bp), PACK(size, 0));
}
// case 3 이전 블록 가용가능
else if (!prev_alloc && next_alloc) {
void *pp = PREV_BLKP(bp);
UNLINK(pp); // 이전 블록 언링크
size += GET_SIZE(HDRP(pp));
unsigned int prevprev = GET_PREV_ALLOC(HDRP(pp)); // 병합 후 블록의 prev_alloc
PUT(HDRP(pp), PACK(size, prevprev));
PUT(FTRP(pp), PACK(size, 0));
bp = pp;
}
// case 4 앞뒤 둘다 가용 가능
else {
void *pp = PREV_BLKP(bp);
void *np = NEXT_BLKP(bp);
UNLINK(pp); // 이전 블록 언링크
UNLINK(np); // 다음 블록 언링크
size += GET_SIZE(HDRP(pp)) + GET_SIZE(HDRP(np));
unsigned int prevprev = GET_PREV_ALLOC(HDRP(pp));
PUT(HDRP(pp), PACK(size, prevprev));
PUT(FTRP(np), PACK(size, 0));
bp = pp;
}
unsigned int nh = GET(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(NEXT_BLKP(bp)), nh & ~FL_PREV_ALLOC); // 다음 헤더 prev_alloc=0
return bp;
}
static void split_tail(void *bp, size_t asize) {
size_t csize = GET_SIZE(HDRP(bp));
size_t remainder = csize - asize;
if (remainder >= MIN_BLOCK) {
PUT(HDRP(bp), PACK(asize, GET_PREV_ALLOC(HDRP(bp)) | 0x1));
void *nbp = NEXT_BLKP(bp);
PUT(HDRP(nbp), PACK(remainder, FL_PREV_ALLOC));
PUT(FTRP(nbp), PACK(remainder, 0));
// nbp free-list에 삽입 LIFO
INSERT_FRONT(nbp);
// nbp 다음 블록 헤드 prev_alloc = 0
PUT(HDRP(NEXT_BLKP(nbp)), GET(HDRP(NEXT_BLKP(nbp))) & ~FL_PREV_ALLOC);
}
else {
PUT(HDRP(bp), PACK(csize, GET_PREV_ALLOC(HDRP(bp)) | 0x1)); // 내 prev 유지 + alloc=1
unsigned int nh = GET(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(NEXT_BLKP(bp)), nh | FL_PREV_ALLOC); // 다음 헤더에 prev_alloc=1만 OR
}
}
void *mm_realloc(void *ptr, size_t size)
{
if (ptr == NULL) return mm_malloc(size);
if (size == 0) { mm_free(ptr); return NULL; }
size_t oldsize = GET_SIZE(HDRP(ptr));
size_t payload = oldsize - OVERHEAD;
size_t asize = MAX(MIN_BLOCK, ALIGN(size + OVERHEAD));
// 축소
if (asize <= oldsize) {
split_tail(ptr, asize);
return ptr;
// 확장
} else {
void *next = NEXT_BLKP(ptr);
if (!GET_ALLOC(HDRP(next)) && oldsize + GET_SIZE(HDRP(next)) >= asize) {
UNLINK(next);
size_t combined = oldsize + GET_SIZE(HDRP(next));
PUT(HDRP(ptr), PACK(combined, FL_ALLOC | GET_PREV_ALLOC(HDRP(ptr))));
split_tail(ptr, asize);
return ptr;
} else if (GET_SIZE(HDRP(NEXT_BLKP(ptr))) == 0) {
if (extend_heap(MAX(asize - oldsize, CHUNKSIZE)/WSIZE) != NULL) {
next = NEXT_BLKP(ptr);
UNLINK(next);
size_t combined = oldsize + GET_SIZE(HDRP(next));
PUT(HDRP(ptr), PACK(combined, FL_ALLOC | GET_PREV_ALLOC(HDRP(ptr))));
split_tail(ptr, asize);
return ptr;
}
}
// 이사
void *new = mm_malloc(size);
if (new == NULL) return NULL;
size_t copySize = (size < payload) ? size : payload;
memcpy(new, ptr, copySize);
mm_free(ptr);
return new;
}
}