이번주 회고
이번주는 생각보다 시간이 너무 부족했다.
직접 머리 박으면서 하는 것도 힘들고, 메모리 오류를 밥먹듯이 봤던것 같다.
그래도 팀원들 많이 도와주고 도움도 많이 받으면서 같이 해결해나가는게 즐거웠다.
특히 Explicit 구현하는데 시간을 너무 많이 써서 마지막 버디 시스템 도입 못해본게 너무 아쉽다.
직접 글과 자료 보면서 악으로 깡으로 짜는게 쉽지 않았던 것 같다.
다음부터는 그냥 구글링도 좀 하고 이론적인 내용을 좀 더 봐야할 것같다.
Malloc-lab
우리는 현재 C언어에서 메모리를 할당 받는 함수로 malloc을 사용한다.
그 내부는 어떻게 돌아갈까? 라는 의문을 가지고 이 과제를 보면 매우 흥미로울 것 같다.
먼저 우리는 malloc을 이용한다고 하면 메모리 영역에서 heap 영역을 할당 받고 그 공간을 사용한다.
미초기화된 데이터 영역 직후부터 위쪽으로 커지는 메모리 영역이라고 생각하면 편하다.
기본적인 할당기를 구현 할 것인데, 먼저 묵시적 가용 리스트를 사용해 구현해보겠다.
할당기의 요구사항을 봐보면 다음과 같다.
1. 임의의 요청 순서 처리하기
2. 요청에 즉시 응답하기
3. 힙만 사용하기
4. 블록 정렬하기(정렬요건)
5. 할당된 블록을 수정하지 않기
처리량은 최대화하고, 메모리 이용도를 최대화 해보자
그러기 위해선 먼저 단편화를 최소화해보고
할당하는 블록의 배치를 정하는 기법을 사용해야한다.
first-fit : 가용 리스트를 처음부터 검색해서 크기가 맞는 첫 번째 가용 블록을 선택하는 기법
next-fit: 이전 검색에서 가용 블록을 발견했다면 다음 블록을 찾는 방법.
first-fit 보다 빠른 속도를 가지지만 next-fit이 first-fit보다 최악의 메모리 이용도를 가진다.
best-fit: 프로세스 크기와 딱 알맞는 크기의 메모리를 할당하는 기법
단 , 모든 힙을 다 검색해야해서 작은 내부 단편화가 생겨 구멍이 송송 나서 외부 단편화가 심해져 최악의 알고리즘이다.
알맞는 배치 알고리즘과 가용 블록을 분할하여 메모리 효율점을 높여야 하고
추가적인 힙 메모리를 획득하는 함수와 가용 블록을 연결하는 함수
블록의 header는 블록사이즈와 allocate의 유무가 들어가 있어 이것으로 공간을 체크할 것이다.
헤더를 응용해 경계 태그라는 footer라는 블록을 추가해서 경계 태그를 확인하며 블록을 연결 할 것인데,
4가지 케이스를 확인할 것이다.
1. 이전과 다음 블록이 모두 할당되어있다.
2. 이전 블록은 할당된 상태, 다음 블록은 가용 상태
3. 이전 블록은 가용상태, 다음 블록은 할당상태
4. 이전 블록과 다음 블록 모두 가용상태
first-fit 구현
#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 */
"hard hot",
/* First member's full name */
"killer park",
/* First member's email address */
"slstls2@gmail.com",
/* 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
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#define WSIZE 8
#define DSIZE 16
#define CHUNKSIZE (1<<12)
#define MAX(x,y) ((x) > (y)? (x) : (y))
// pack 사이즈 size | alloc
#define PACK(size,alloc) ((size) | (alloc))
// GET 확인하기 위한
#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) & 0x1)
// 포인트에 대해 - wordsize = 헤더
#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 NEXT_FBLKP(bp) ((void **)(bp))
#define PREV_FBLKP(bp) ((void **)(bp+WSIZE))
// bp 부분에 할당
#define PUT_NEXT_FBLKP(bp,ptr) (*(void **)(bp)=(char*)ptr)
#define PUT_PREV_FBLKP(bp,ptr) (*(void **)(bp+WSIZE)=(char*)ptr)
static char *heap_listp;
static char *free_listp;
int mm_init(void);
static void *extend_heap(size_t words);
void mm_free(void *ptr);
static void *coalesce(void *bp);
void *mm_malloc(size_t size);
static void *find_fit(size_t asize);
static void place(void *bp,size_t asize);
static void deletefree_list(void *bp);
static void makefree_list(void *bp);
/*
* mm_init - initialize the malloc package.
*/
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)); // Epilogue 헤더
heap_listp += (2*WSIZE);
free_listp = 0;
if(extend_heap(CHUNKSIZE/DSIZE) == 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;
// 현재의 헤더값, 헤더값 초기화
PUT(HDRP(bp),PACK(size,0));
// 푸터값 초기화
PUT(FTRP(bp),PACK(size,0));
// 헤더 = 다음블록의 헤더값, 할당
PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1));
return coalesce(bp);
}
/*
* mm_free - Freeing a block does nothing.
*/
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 *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));
// CASE 1
if (prev_alloc && next_alloc) {
return bp;
}
//CASE 2
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));
}
// CASE 3
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);
}
// CASE 4
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);
}
return bp;
}
/*
* 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;
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 = 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;
}
// 내가 사용하려는 fit 알고리즘
static void *find_fit(size_t asize){
/*
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
#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)))
*/
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 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_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 = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}Next-fit 구현
#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 */
"hard hot",
/* First member's full name */
"killer park",
/* First member's email address */
"slstls2@gmail.com",
/* 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
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#define WSIZE 8
#define DSIZE 16
#define CHUNKSIZE (1<<12)
#define MAX(x,y) ((x) > (y)? (x) : (y))
// pack 사이즈 size | alloc
#define PACK(size,alloc) ((size) | (alloc))
// GET 확인하기 위한
#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) & 0x1)
// 포인트에 대해 - wordsize = 헤더
#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 NEXT_FBLKP(bp) ((void **)(bp))
#define PREV_FBLKP(bp) ((void **)(bp+WSIZE))
// bp 부분에 할당
#define PUT_NEXT_FBLKP(bp,ptr) (*(void **)(bp)=(char*)ptr)
#define PUT_PREV_FBLKP(bp,ptr) (*(void **)(bp+WSIZE)=(char*)ptr)
static char *heap_listp;
static char *free_listp;
static char *next_fit;
int mm_init(void);
static void *extend_heap(size_t words);
void mm_free(void *ptr);
static void *coalesce(void *bp);
void *mm_malloc(size_t size);
static void *find_fit(size_t asize);
static void place(void *bp,size_t asize);
static void deletefree_list(void *bp);
static void makefree_list(void *bp);
/*
* mm_init - initialize the malloc package.
*/
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)); // Epilogue 헤더
heap_listp += (2*WSIZE);
next_fit = heap_listp;
if(extend_heap(CHUNKSIZE/DSIZE) == 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;
// 현재의 헤더값, 헤더값 초기화
PUT(HDRP(bp),PACK(size,0));
// 푸터값 초기화
PUT(FTRP(bp),PACK(size,0));
// 헤더 = 다음블록의 헤더값, 할당
PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1));
return coalesce(bp);
}
/*
* mm_free - Freeing a block does nothing.
*/
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 *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));
// CASE 1
if (prev_alloc && next_alloc) {
return bp;
}
//CASE 2
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));
}
// CASE 3
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);
}
// CASE 4
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);
}
next_fit = bp;
return bp;
}
/*
* 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;
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 = 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;
}
// 내가 사용하려는 fit 알고리즘
static void *find_fit(size_t asize){
/*
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
#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)))
*/
void *bp;
for(bp = next_fit;GET_SIZE(HDRP(bp))> 0;bp = NEXT_BLKP(bp)) {
if(!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
next_fit = bp;
return bp;
}
}
return NULL;
}
// 블록 분할과정
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_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 = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}위의 두 경우는 묵시적인 가용리스트이다.
묵시적 가용 리스트는 범용 할당기에 적당하지 않은데, 힙 블록수가 알려져 있고, 작고 특수한 경우를 제외하고는 명시적으로 가용리스트를 구성하는 것이 더 좋은 방법이다.
묵시적 가용리스트 대신에 이중 연결 리스트를 사용하면 first-fit 할당 시간을 전체 블록 수에 비례하는 것에서 가용 블록의 수에 비례 하는 것으로 줄일 수 있다.
free된 시작 부분에서 LIFO 순으로 유지하면서 first-fit 배치 정책을 사용해보겠다.
하지만 무조건 명시적 가용리스트가 좋다는 것은 아니다.
명시적 리스트는 가용 블록들이 충분히 커서 모든 필요한 포인터뿐만 아니라 헤더, 추가적으로 푸터까지 포함해야한다.
그러면 최소 블록크기가 커지니 잠재적인 내부 단편화 가능성이 증가한다.
Explicit 구현
#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 */
"hard hot",
/* First member's full name */
"killer park",
/* First member's email address */
"slstls2@gmail.com",
/* 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
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#define WSIZE 8
#define DSIZE 16
#define CHUNKSIZE (1<<12)
#define MAX(x,y) ((x) > (y)? (x) : (y))
// pack 사이즈 size | alloc
#define PACK(size,alloc) ((size) | (alloc))
// GET 확인하기 위한
#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) & 0x1)
// 포인트에 대해 - wordsize = 헤더
#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 NEXT_FBLKP(bp) ((void **)(bp))
#define PREV_FBLKP(bp) ((void **)(bp+WSIZE))
// bp 부분에 할당
// explicit 구현을 위한 매크로 함수
#define PUT_NEXT_FBLKP(bp,ptr) (*(void **)(bp)=(char*)ptr)
#define PUT_PREV_FBLKP(bp,ptr) (*(void **)(bp+WSIZE)=(char*)ptr)
// next와 ,prev를 가르키는 포인터
void *heap_listp;
char *free_listp;
/* new_freelist */
// free 리스트만들기
static void make_freelist(void *bp)
{
// printf("new freelist\n");
void* root = free_listp;
if (root==NULL){
// printf("null\n");
PUT_NEXT_FBLKP(bp, NULL);
PUT_PREV_FBLKP(bp,NULL);
}
else{
// printf("not null\n");
PUT_NEXT_FBLKP(bp,root);
PUT_PREV_FBLKP(bp,NULL);
PUT_PREV_FBLKP(root,bp);
}
free_listp=bp;
}
//delete freelist
// free 리스트 삭제
static void delete_freelist(void *bp)
{
// printf("delete freelist\n");
char *prev_free = *PREV_FBLKP(bp);
char *next_free = *NEXT_FBLKP(bp);
if (prev_free!=NULL) {PUT_NEXT_FBLKP(prev_free,next_free);
}
if (next_free!=NULL) {PUT_PREV_FBLKP(next_free,prev_free);
}
if (free_listp==bp) free_listp=next_free;
}
/*
* 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));
// void *old_root = free_listp;
if (prev_alloc && next_alloc) { /* Case 1 */
make_freelist(bp);
return bp;
}
else if (prev_alloc && !next_alloc) { /* Case 2 */
void *next_fblk=NEXT_BLKP(bp);
delete_freelist(next_fblk);
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 */
void *prev_fblk=PREV_BLKP(bp);
delete_freelist(prev_fblk);
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{
void *prev_fblk=PREV_BLKP(bp);
void *next_fblk=NEXT_BLKP(bp);
delete_freelist(next_fblk);
delete_freelist(prev_fblk);
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);
}
make_freelist(bp);
return bp;
}
/*
* extend_heap - extends the heap with a new free block
*/
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 = (words % 4) ? ((words/4)+1) * 4 * 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);
}
/*
* find_fit
*/
static void *find_fit(size_t asize)
{
/* First-fit search */
void *bp;
for (bp = free_listp; bp!=NULL; bp = *NEXT_FBLKP(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));
delete_freelist(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));
make_freelist(bp);
}
else {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
/*
* 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);
free_listp=NULL;
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}
/*
* 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; /* Adjust 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 *bp)
{
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp);
}
/*
* 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 = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}
중간에 realloc 부분이 크기를 확인하지 않고 무조건 메모리를 추가적으로 할당한 사실을 발견해서
필요한 만큼만 할당하도록 Explicit 의 realloc 부분을 수정해보았다.
Explicit Realloc수정
/*
* 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 */
"hard hot",
/* First member's full name */
"killer park",
/* First member's email address */
"slstls2@gmail.com",
/* 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 LISTLIMIT 20
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#define WSIZE 8
#define DSIZE 16
#define CHUNKSIZE (1<<12)
#define MAX(x,y) ((x) > (y)? (x) : (y))
// pack 사이즈 size | alloc
#define PACK(size,alloc) ((size) | (alloc))
// GET 확인하기 위한
#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) & 0x1)
// 포인트에 대해 - wordsize = 헤더
#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 NEXT_FBLKP(bp) ((void **)(bp))
#define PREV_FBLKP(bp) ((void **)(bp+WSIZE))
// bp 부분에 할당
#define PUT_NEXT_FBLKP(bp,ptr) (*(void **)(bp)=(char*)ptr)
#define PUT_PREV_FBLKP(bp,ptr) (*(void **)(bp+WSIZE)=(char*)ptr)
// next와 ,prev를 가르키는 포인터
void *heap_listp;
char *free_listp;
void *segregated_lists[LISTLIMIT];
/* new_freelist */
static void make_freelist(void *bp)
{
// printf("new freelist\n");
void* root = free_listp;
if (root==NULL){
// printf("null\n");
PUT_NEXT_FBLKP(bp, NULL);
PUT_PREV_FBLKP(bp,NULL);
}
else{
// printf("not null\n");
PUT_NEXT_FBLKP(bp,root);
PUT_PREV_FBLKP(bp,NULL);
PUT_PREV_FBLKP(root,bp);
}
free_listp=bp;
}
//delete freelist
static void delete_freelist(void *bp)
{
// printf("delete freelist\n");
char *prev_free = *PREV_FBLKP(bp);
char *next_free = *NEXT_FBLKP(bp);
if (prev_free!=NULL) {
PUT_NEXT_FBLKP(prev_free,next_free);
}
if (next_free!=NULL) {
PUT_PREV_FBLKP(next_free,prev_free);
}
if (free_listp==bp) {
free_listp=next_free;
}
}
/*
* 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));
// void *old_root = free_listp;
if (prev_alloc && next_alloc) { /* Case 1 */
make_freelist(bp);
return bp;
}
else if (prev_alloc && !next_alloc) { /* Case 2 */
void *next_fblk=NEXT_BLKP(bp);
delete_freelist(next_fblk);
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 */
void *prev_fblk=PREV_BLKP(bp);
delete_freelist(prev_fblk);
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{
void *prev_fblk=PREV_BLKP(bp);
void *next_fblk=NEXT_BLKP(bp);
delete_freelist(next_fblk);
delete_freelist(prev_fblk);
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);
}
make_freelist(bp);
return bp;
}
/*
* extend_heap - extends the heap with a new free block
*/
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 = (words % 4) ? ((words/4)+1) * 4 * 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);
}
/*
* find_fit
*/
static void *find_fit(size_t asize)
{
/* First-fit search */
void *bp;
for (bp = free_listp; bp!=NULL; bp = *NEXT_FBLKP(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));
delete_freelist(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));
make_freelist(bp);
}
else {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
/*
* 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);
free_listp=NULL;
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}
/*
* 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; /* Adjust 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 *bp)
{
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp);
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size)
{
/*
#define NEXT_FBLKP(bp) ((void **)(bp))
#define PREV_FBLKP(bp) ((void **)(bp+WSIZE))
#define PUT_NEXT_FBLKP(bp,ptr) (*(void **)(bp)=(char*)ptr)
#define PUT_PREV_FBLKP(bp,ptr) (*(void **)(bp+WSIZE)=(char*)ptr)
// 이전 블록의 크기를 탐색하여 다음 블록의 주소를 계산하기
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
// 이전 블록의 주소를 계산해서 이전 블록에 대한 작업 수행용
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp)- DSIZE)))
할당체크
#define GET_ALLOC(p) (GET(p) & 0x1)
*/
//가독성을 높이기 위한 ptr realloc 메모리 변환전을 가르키는 포인터
void *oldptr = ptr;
size_t copySize;
size_t oldsize = GET_SIZE(HDRP(oldptr));
size_t newsize = size + (2*DSIZE);
size_t csize = oldsize + GET_SIZE(HDRP(NEXT_BLKP(oldptr)));
size_t check_free = GET_ALLOC(HDRP(NEXT_BLKP(oldptr)));
// 사이즈에 확인
if(size == 0) {
mm_free(oldptr);
return NULL;
}
else if(oldsize >= newsize){
return oldptr;
}
else{
// 다음 블록이 할당 안되어있고 내가 원래 할당 받는거보다 효율적으로 받을수 있는경우
if(!check_free && csize >= newsize){
rm_freelist(NEXT_BLKP(oldptr));
PUT(HDRP(ptr), PACK(csize,1));
PUT(FTRP(ptr), PACK(csize,1));
return ptr;
}
else{
// 길이를 늘릴때 place와 MIN 매크로 함수를 사용해서 효율적인 메모리 공간할당
void *newptr = mm_malloc(newsize);
// place를 안하면 남는 패딩블록 까지 그냥 할당할 수 도 있어서 사용ㅎ....
place(newptr,newsize);
memcpy(newptr, oldptr, MIN(oldsize,newsize));
mm_free(oldptr);
return newptr;
}
}
return NULL;
}
마지막 분리 가용 리스트가 있는데
이 부분은 크기 클래스를 나누어 크기에 맞는 리스트만을 탐색하는 방법이다.
이론은 대충이런데 솔직히 시간이 없어서 버디시스템으로의 구현은 하지 못했다.
노가다 식으로 크기 클래스만 나눠서 구현했다.
Segreated List 구현
/*
* 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 */
"hard hot",
/* First member's full name */
"killer park",
/* First member's email address */
"slstls2@gmail.com",
/* 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
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
/* Basic constants and macros */
#define WSIZE 8 /* Word and header/footer size(bytes) */
#define DSIZE 16 /* Double word size (bytes) */
#define CHUNKSIZE (1<<12) /* Extend heap by this amount (bytes)*/
#define MAX(x, y) ((x) > (y)? (x) : (y))
#define MIN(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)
/* Givne block ptr bp, compute the address of its header 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)))
/* Given free block ptr bp, get ptr of next and previous ptr*/
#define NEXT_FBLKP(bp) ((void **)(bp))
#define PREV_FBLKP(bp) ((void **)(bp+WSIZE))
#define PUT_NEXT_FBLKP(bp,ptr) (*(void **)(bp)=(char*)ptr)
#define PUT_PREV_FBLKP(bp,ptr) (*(void **)(bp+WSIZE)=(char*)ptr)
void *heap_listp;
char *free_listp0;
char *free_listp1;
char *free_listp2;
char *free_listp3;
/* rm_freelist*/
static void rm_freelist(void *bp)
{
// printf("delete freelist\n");
char *prev_free = *PREV_FBLKP(bp);
char *next_free = *NEXT_FBLKP(bp);
// printf("rm from list\n");
// printf("prev:%p\t\t next: %p\n",*PREV_FBLKP(bp), *NEXT_FBLKP(bp));
if (prev_free!=NULL) {PUT_NEXT_FBLKP(prev_free,next_free);
// printf("prev-next: %p\n",*NEXT_FBLKP(prev_free));
}
if (next_free!=NULL) {PUT_PREV_FBLKP(next_free,prev_free);
// printf("next-prev: %p\n",*PREV_FBLKP(next_free));
}
if (free_listp0==bp) free_listp0=next_free;
else if (free_listp1==bp) free_listp1=next_free;
else if (free_listp2==bp) free_listp2=next_free;
else if (free_listp3==bp) free_listp3=next_free;
}
/* new_seg_flst*/
static void new_seg_flst(void* bp,char* free_listp)
{
// printf("new freelist\n");
void* old_root = free_listp;
if (old_root==NULL){
// printf("null\n");
PUT_NEXT_FBLKP(bp, NULL);
PUT_PREV_FBLKP(bp,NULL);
}
else{
PUT_NEXT_FBLKP(bp,old_root);
PUT_PREV_FBLKP(bp,NULL);
PUT_PREV_FBLKP(old_root,bp);
}
}
/* new_freelist */
static void new_freelist(void *bp)
{
if (GET_SIZE(HDRP(bp))<(1<<5)*WSIZE) {
new_seg_flst(bp, free_listp0);
free_listp0 = bp;
}
else if (GET_SIZE(HDRP(bp))<(1<<7)*WSIZE) {
new_seg_flst(bp, free_listp1);
free_listp1 = bp;
}
else if (GET_SIZE(HDRP(bp))<(1<<9)*WSIZE) {
new_seg_flst(bp, free_listp2);
free_listp2 = bp;
}
else {
new_seg_flst(bp, free_listp3);
free_listp3 = 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));
// void *old_root = free_listp;
if (prev_alloc && next_alloc) { /* Case 1 */
// printf("case1\n");
new_freelist(bp);
return bp;
}
else if (prev_alloc && !next_alloc) { /* Case 2 */
// printf("case2\n");
void *next_fblk=NEXT_BLKP(bp);
rm_freelist(next_fblk);
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 */
// printf("case3\n");
void *prev_fblk=PREV_BLKP(bp);
rm_freelist(prev_fblk);
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{
// printf("case4\n");
void *prev_fblk=PREV_BLKP(bp);
void *next_fblk=NEXT_BLKP(bp);
rm_freelist(next_fblk);
rm_freelist(prev_fblk);
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);
}
new_freelist(bp);
return bp;
}
/*
* extend_heap - extends the heap with a new free block
*/
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 = (words % 4) ? ((words/4)+1) * 4 * 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);
}
/*
* find_fit_seg
*/
static void *find_fit_seg(size_t asize, char* free_listp)
{
/* First-fit search */
void *bp;
for (bp = free_listp; bp!=NULL; bp = *NEXT_FBLKP(bp)){
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
return bp;
}
}
return NULL; /* No fit */
}
/*
* find_fit
*/
static void *find_fit(size_t asize)
{
void* bp;
if(asize<(1<<4)*WSIZE)
{
bp =find_fit_seg(asize, free_listp0);
if(bp!=NULL) return bp;
}
if(asize<(1<<7)*WSIZE)
{
bp =find_fit_seg(asize, free_listp1);
if(bp!=NULL) return bp;
}
if(asize<(1<<9)*WSIZE)
{
bp =find_fit_seg(asize, free_listp2);
if(bp!=NULL) return bp;
}
return bp =find_fit_seg(asize, free_listp3);
}
/*
* place
*/
static void place(void *bp, size_t asize)
{
size_t csize = GET_SIZE(HDRP(bp));
rm_freelist(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));
new_freelist(bp);
}
else {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
/*
* 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);
free_listp0=NULL;
free_listp1=NULL;
free_listp2=NULL;
free_listp3=NULL;
// printf("init: %d\n",free_listp==NULL);
/* Extent the empty heap wit a free block of CHUNKSIZE bytes */
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}
/*
* 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; /* Adjust 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 *bp)
{
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp);
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size)
{
/*
#define NEXT_FBLKP(bp) ((void **)(bp))
#define PREV_FBLKP(bp) ((void **)(bp+WSIZE))
#define PUT_NEXT_FBLKP(bp,ptr) (*(void **)(bp)=(char*)ptr)
#define PUT_PREV_FBLKP(bp,ptr) (*(void **)(bp+WSIZE)=(char*)ptr)
// 이전 블록의 크기를 탐색하여 다음 블록의 주소를 계산하기
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
// 이전 블록의 주소를 계산해서 이전 블록에 대한 작업 수행용
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp)- DSIZE)))
할당체크
#define GET_ALLOC(p) (GET(p) & 0x1)
*/
//가독성을 높이기 위한 ptr realloc 메모리 변환전을 가르키는 포인터
void *oldptr = ptr;
size_t copySize;
size_t oldsize = GET_SIZE(HDRP(oldptr));
size_t newsize = size + (2*DSIZE);
size_t csize = oldsize + GET_SIZE(HDRP(NEXT_BLKP(oldptr)));
size_t check_free = GET_ALLOC(HDRP(NEXT_BLKP(oldptr)));
if(size == 0) {
mm_free(oldptr);
return NULL;
}
else if(oldsize >= newsize){
return oldptr;
}
else{
if(!check_free && csize >= newsize){
rm_freelist(NEXT_BLKP(oldptr));
PUT(HDRP(ptr), PACK(csize,1));
PUT(FTRP(ptr), PACK(csize,1));
return ptr;
}
else{
void *newptr = mm_malloc(newsize);
place(newptr,newsize);
memcpy(newptr, oldptr, MIN(oldsize,newsize));
mm_free(oldptr);
return newptr;
}
}
return NULL;
}
후기
분리 가용 리스트는 클래스를 몇개로 나눠주냐에 따라 점수가 1~2점 정도 왔다 갔다 했다.
하지만 애당초 정해진 테스트케이스 내에서 동작하기 때문에 무조건 적으로 클래스를 많이 생성한다고 해서 효율적인 것은 아니다. 또한 끝나고 불필요하게 할당한 메모리를 확인해 줌으로서 2점을 더 챙길 수 있었다.
'정글' 카테고리의 다른 글
| TIL(27일차) 네트워크 (0) | 2023.05.23 |
|---|---|
| (TIL26일차) 동시성 프로그래밍 (1) | 2023.05.20 |
| (TIL 25일차) 가상 메모리1 (0) | 2023.05.18 |
| TIL(24일차) 프로세스 (0) | 2023.05.18 |
| (TIL23일차) 캐시 (0) | 2023.05.18 |
