-
segregated free list
가용 블록을 블록의 크기(2의 지수승) 단위로 구성된 각각의 리스트로 관리하는 방식.
2^1 , 2^2, 2^3 ...... 2^20의 크기까지 관리
위 2가지의 방법에 비해서 요청한 블록의 크기에 따라 할당해주는 블록의 크기를 정해주므로 외부 단편화를 줄일 수 있다
/*
* 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 */
"Swjungle-2",
/* First member's full name */
"Jeong, Wonjong",
/* First member's email address */
"wonjong0701@naver.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 4
#define DSIZE 8
#define CHUNKSIZE (1<<12)
#define INITCHUNKSIZE (1<<6) // 64
#define LISTLIMIT 20
#define REALLOC_BUFFER (1<<7) // 128
// calculate max value
#define MAX(x,y) ((x)>(y) ? (x) : (y))
//size와 할당 여부를 하나로 합친다
#define PACK(size,alloc) ((size)|(alloc))
//포인터 p가 가리키는 주소의 값을 가져온다.
#define GET(p) (*(unsigned int *)(p))
//포인터 p가 가리키는 곳에 val을 역참조로 갱신
#define PUT(p,val) (*(unsigned int *)(p)=(val))
//포인터 p가 가리키는 곳의 값에서 하위 3비트를 제거하여 블럭 사이즈를 반환(헤더+푸터+페이로드+패딩)
#define GET_SIZE(p) (GET(p) & ~0X7)
//포인터 p가 가리키는 곳의 값에서 맨 아래 비트를 반환하여 할당상태 판별
#define GET_ALLOC(p) (GET(p) & 0X1)
//블럭포인터를 통해 헤더 포인터,푸터 포인터 계산
#define HDRP(bp) ((char*)(bp) - WSIZE)
#define FTRP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
//블럭포인터 -> 블럭포인터 - WSIZE : 헤더위치 -> GET_SIZE으로 현재 블럭사이즈계산 -> 다음 블럭포인터 반환
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
//블럭포인터 -> 블럭포인터 - DSIZE : 이전 블럭 푸터 -> GET_SIZE으로 이전 블럭사이즈계산 -> 이전 블럭포인터 반환
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
//포인터 p가 가리키는 메모리에 포인터 ptr을 입력
#define SET_PTR(p, ptr) (*(unsigned int *)(p) = (unsigned int)(ptr))
//가용 블럭 리스트에서 next 와 prev의 포인터를 반환
#define NEXT_PTR(ptr) ((char *)(ptr))
#define PREV_PTR(ptr) ((char *)(ptr) + WSIZE)
//segregated list 내에서 next 와 prev의 포인터를 반환
#define NEXT(ptr) (*(char **)(ptr))
#define PREV(ptr) (*(char **)(PREV_PTR(ptr)))
//전역변수
char *heap_listp = 0;
void *segregated_free_lists[LISTLIMIT];
//함수 목록
static void *coalesce(void *bp);
static void *extend_heap(size_t words);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);
static void insert_node(void *ptr, size_t size);
static void delete_node(void *ptr);
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void)
{
int list;
for (list = 0; list < LISTLIMIT; list++) {
segregated_free_lists[list] = NULL;
}
/* 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);
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
if (extend_heap(INITCHUNKSIZE) == NULL)
return -1;
return 0;
}
static void *extend_heap(size_t words){
char *bp;
size_t size;
// 요청받은 크기를 2워드 배수(8byte)로 반올림. 그리고 힙 공간 요청
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));
insert_node(bp,size); // 가용 리스트에 새로 할당받은 영역 추가
return coalesce(bp); // 가용 블록 합치기
}
static void insert_node(void *ptr, size_t size) {
int idx = 0; // 리스트의 인덱스
void *search_ptr = ptr;
void *insert_ptr = NULL; //실제 노드가 삽입되는 위치
// Select segregated list
// 2의 지수승으로 인덱스를 나누어 리스트를 관리하므로
// size의 비트를 하나씩 제거하며 카운트를 세면 그 카운트수가 리스트의 index가 됨.
while ((idx < LISTLIMIT - 1) && (size > 1)) {
size >>= 1;
idx++;
}
// Keep size ascending order and search
search_ptr = segregated_free_lists[idx]; // search_ptr이 할당되어있으면 null이 아니겠지?
// 첫 삽입이라면 search_ptr이 null이니까 반복문을 거치치 않음
// 이 위치에 삽입이 되어있다면 null이 아닐 것이고 기존 블록의 사이즈보다 만들려는 사이즈가 더 크면 반복문 시작
// 이게 가용 리스트에서 찾는 게 아니라 할당된 리스트에서 찾는거지?
// insert_ptr이 가리키는 곳은 연속된 힐당된 주소 중 가장 끝에 있는 주소
while ((search_ptr != NULL) && (size > GET_SIZE(HDRP(search_ptr)))) {
insert_ptr = search_ptr; // insert ptr에 기존에 있던 주소값으로 업데이트
search_ptr = NEXT(search_ptr); // search ptr의 위치를 뒤 블록으로 옮김
}
// Set NEXT and PREV
// 이제부터 insert_ptr이 앞 블록, search_ptr이 뒷 블록이라고 보면 되겠지?
if (search_ptr != NULL) {
if (insert_ptr != NULL) { // 앞뒤가 모두 할당된 블록인 경우
SET_PTR(NEXT_PTR(ptr), search_ptr); // 가용 리스트의 ptr의 next를 뒷 블록 주소로 변경
SET_PTR(PREV_PTR(search_ptr), ptr); // 뒷 블록의 앞 주소를 ptr로 변경
SET_PTR(PREV_PTR(ptr), insert_ptr); // ptr의 앞 주소를 앞 블록 주소로 변경
SET_PTR(NEXT_PTR(insert_ptr), ptr); // 앞 주소의 뒷 주소를 ptr로 변경
} else { // 앞이 비었고 뒤가 할당된 경우
SET_PTR(NEXT_PTR(ptr), search_ptr); // ptr의 다음 주소를 뒷 블록으로 변경
SET_PTR(PREV_PTR(search_ptr), ptr); // 뒷 블록의 앞 주소를 ptr로 변경
SET_PTR(PREV_PTR(ptr), NULL); // ptr의 앞 주소를 null로 변경
segregated_free_lists[idx] = ptr; // 가용 리스트의 인덱스에 ptr 업데이트. 앞 포인터가 갱신되는 상황이니까?
}
} else {
if (insert_ptr != NULL) { // 앞이 할당되었고 뒤가 비어있는 경우
SET_PTR(NEXT_PTR(ptr), NULL); // ptr의 뒷 주소를 null로 변경
SET_PTR(PREV_PTR(ptr), insert_ptr); // ptr의 앞 주소를 앞 블록으로 변경
SET_PTR(NEXT_PTR(insert_ptr), ptr); // 앞 블록의 뒷 주소를 ptr로 변경
} else { // 둘다 비어있는 경우
SET_PTR(NEXT_PTR(ptr), NULL); // ptr의 앞 주소 null로 변경
SET_PTR(PREV_PTR(ptr), NULL); // ptr의 뒷 주소 null로 변경
segregated_free_lists[idx] = ptr; // 가용 리스트의 인덱스에 ptr 업데이트. 앞 포인터가 갱신되는 상황이니까?
}
}
return;
}
static void delete_node(void *ptr) {
int idx = 0;
size_t size = GET_SIZE(HDRP(ptr));
// Select segregated list
// 사이즈에 맞는 가용 리스트의 인덱스 찾기
while ((idx < LISTLIMIT - 1) && (size > 1)) {
size >>= 1;
idx++;
}
if (NEXT(ptr) != NULL) {
if (PREV(ptr) != NULL) { // 앞 블록과 뒷 블록이 할당되어있는 경우
SET_PTR(PREV_PTR(NEXT(ptr)), PREV(ptr)); // 뒷 블록의 앞 주소를 앞 블록으로
SET_PTR(NEXT_PTR(PREV(ptr)), NEXT(ptr)); // 앞 블록의 뒷 주소를 뒷 블록으로
} else { // 앞 블록이 가용 블록이고 뒷 블록이 할당된 경우
SET_PTR(PREV_PTR(NEXT(ptr)), NULL); // 뒷 블록의 앞 주소를 null로 변경
segregated_free_lists[idx] = NEXT(ptr); // 가용 리스트에 뒷 블록 주소 넣기
}
} else {
if (PREV(ptr) != NULL) { // 앞 블록이 할당되었고 뒷 블록이 가용 블록인 경우
SET_PTR(NEXT_PTR(PREV(ptr)), NULL); // 앞 블록의 뒷 주소를 null로 변경
} else { // 앞 블록과 뒷 블록 모두 가용 블록인 경우
segregated_free_lists[idx] = NULL; // 가용 리스트에 null
}
}
return;
}
/*
* 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)
{
// int newsize = ALIGN(size + SIZE_T_SIZE);
// void *p = mem_sbrk(newsize);
// if (p == (void *)-1)
// return NULL;
// else {
// *(size_t *)p = size;
// return (void *)((char *)p + SIZE_T_SIZE);
// }
size_t asize;
size_t extendsize; //들어갈 자리가 없을때 늘려야 하는 힙의 용량
char *bp;
/* Ignore spurious*/
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;
}
//전,후에 free block 이 있을시 합쳐줌 + 합쳐지는 경우 segregation_lists에서 기존 free block 노드 삭제해줌
// 합칠 때 기존 가용 블록들을 리스트에서 삭제하고 합쳐진 크기로 다시 리스트에 삽입
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){
return bp;
}
else if (prev_alloc && !next_alloc){ // 뒷 블록이 가용 블록인 경우
delete_node(bp); // bp 블록 삭제
delete_node(NEXT_BLKP(bp)); // bp의 뒷 블록 삭제
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){ // 앞 블록이 가용 블록인 경우
delete_node(bp);
delete_node(PREV_BLKP(bp));
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{ // 앞 뒷 블록이 모두 가용 블록인 경우
delete_node(bp);
delete_node(PREV_BLKP(bp));
delete_node(NEXT_BLKP(bp));
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);
}
insert_node(bp,size); // bp가 가용 블록의 위치이므로 가용 블록 추가
return bp;
}
static void *find_fit(size_t asize){
char *bp;
int idx = 0;
size_t searchsize = asize; // 찾고자 하는 사이즈
// Search for free block in segregated list
// 인덱스 0부터 가용 리스트 검색
while (idx < LISTLIMIT) {
// 마지막 인덱스 or (?? 비트연산 and 해당 인덱스가 할당된 경우)
if ((idx == LISTLIMIT - 1) || ((searchsize <= 1) && (segregated_free_lists[idx] != NULL))) {
bp = segregated_free_lists[idx]; // bp에 현재 서치중인 블록 주소 넣기
// Ignore blocks that are too small or marked with the reallocation bit
// 너무 작거나 재할당 비트로 표시된 블록 무시
while ((bp != NULL) && ((asize > GET_SIZE(HDRP(bp))))) // bp 블록이 비어있지 않고 타겟사이즈를 넣을 수 있는 블록을 찾을 때까지
{
bp = NEXT(bp); // 블록 탐색
}
if (bp != NULL) // 할당 가능한 블록을 찾은 경우
return bp;
}
searchsize >>= 1; // 반복문 종료 조건
idx++; // 인덱스를 올려서 더 큰 블록을 서치
}
return NULL;
}
static void place(void *bp, size_t asize){
size_t csize = GET_SIZE(HDRP(bp));
delete_node(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));
insert_node(bp,(csize-asize));
}
else{
PUT(HDRP(bp),PACK(csize,1));
PUT(FTRP(bp),PACK(csize,1));
}
}
/*
* 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));
insert_node(bp,size);
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);
copySize = GET_SIZE(HDRP(oldptr));
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}
성장형 개발자 gitddabong