컴퓨터 시스템/CSAPP
동적 메모리 할당 - malloc 함수 구현(분리 가용 리스트)
bewisesh91
2021. 12. 15. 22:07
728x90
분리 가용 리스트
사용 가능한 블록을 하나의 리스트가 아닌 다수의 리스트를 사용하여 관리할 수 있다. 기본적인 아이디어는 모든 사용 가능한 블록을
특정 크기 집합들로 분리하고 각 크기 집합들 별로 별개의 리스트를 갖도록 하는 것이다.
만약 어떤 블록을 할당하고자 한다면, 여러 가지 크기 집합 중에서 적당한 크기 집합을 찾고, 다시 해당 크기 집합의 리스트를
탐색하면서 블록이 들어갈 위치를 결정하는 것이다. 만약 적당한 크기 집합을 찾지 못한다면 힙에 부가적인 메모리 요청을 하는 식으로
동작이 이루어진다.
▶ 구현 코드(First Fit)
/*
* 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 */
"jungle3rd_week06",
/* First member's full name */
"group_09",
/* First member's email address */
"bewise.seunghyun@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 4 // Word and header/footer size (bytes)
#define DSIZE 8 // Double word size (bytes)
#define CHUNKSIZE (1 << 12) // Extend heap by this amount (bytes)
#define INITCHUNKSIZE (1 << 6)
#define LISTLIMIT 20
#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))
#define SET_PTR(p, ptr) (*(unsigned int *)(p) = (unsigned int)(ptr))
/* 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 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))
#define PRED_PTR(ptr) ((char *)(ptr))
#define SUCC_PTR(ptr) ((char *)(ptr) + WSIZE)
#define PRED(bp) (*(char **)(bp))
#define SUCC(ptr) (*(char **)(SUCC_PTR(ptr)))
/* glbal variable */
void *segregated_free_lists[LISTLIMIT];
static void *extend_heap(size_t);
static void *coalesce(void *);
static void *place(void *, size_t);
static void insert_node(void *, size_t);
static void delete_node(void *);
/* mm_init - initialize the malloc package. */
int mm_init(void){
int list;
char *heap_start;
for (list = 0; list < LISTLIMIT; list++){
segregated_free_lists[list] = NULL;
}
if ((long)(heap_start = mem_sbrk(4 * WSIZE)) == -1){
return -1;
}
PUT(heap_start, 0); /* Alignment padding*/
PUT(heap_start + (1 * WSIZE), PACK(DSIZE, 1)); /*prologue header*/
PUT(heap_start + (2 * WSIZE), PACK(DSIZE, 1)); /*prologue footer*/
PUT(heap_start + (3 * WSIZE), 0); /*Epilogue header*/
if (extend_heap(INITCHUNKSIZE) == 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;
size_t extendsize;
void *ptr = NULL;
/* double word size에 맞게 size를 조정 */
if (size == 0)
return NULL;
if (size < DSIZE){
asize = 2 * DSIZE;
}
else{
asize = ALIGN(size) + DSIZE;
}
int list = 0;
size_t searchsize = asize;
while (list < LISTLIMIT){
if (((searchsize <= 1) && (segregated_free_lists[list] != NULL)) || (list == LISTLIMIT - 1) )
{
ptr = segregated_free_lists[list];
while ((ptr != NULL) && ((asize > GET_SIZE(HDRP(ptr))))){
ptr = PRED(ptr);
}
if (ptr != NULL)
break;
}
searchsize = searchsize >> 1;
list++;
}
if (ptr == NULL){
extendsize = MAX(asize, CHUNKSIZE);
if ((ptr = extend_heap(extendsize)) == NULL)
return NULL;
}
ptr = place(ptr, asize);
return ptr;
}
void mm_free(void *ptr){
size_t size = GET_SIZE(HDRP(ptr));
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
insert_node(ptr, size);
coalesce(ptr);
}
void *mm_realloc(void *ptr, size_t size){
void *new_ptr = ptr;
int extendsize = 0;
int remainder;
size_t new_size = size;
size_t next_size = GET_SIZE(HDRP(NEXT_BLKP(ptr)));
if (size == 0)
return NULL;
if (new_size <= DSIZE){
new_size = 2 * DSIZE;
}
else{
new_size = ALIGN(size + DSIZE);
}
if (!GET_ALLOC(HDRP(NEXT_BLKP(ptr))) && new_size <= next_size + GET_SIZE(HDRP(ptr))){
PUT(HDRP(ptr), PACK(next_size + GET_SIZE(HDRP(ptr)), 0));
PUT(FTRP(ptr), PACK(GET_SIZE(HDRP(ptr)), 0));
delete_node(NEXT_BLKP(ptr));
place(ptr, new_size);
}
else if (!GET_SIZE(HDRP(NEXT_BLKP(ptr)))){
remainder = GET_SIZE(HDRP(ptr)) - new_size;
if (remainder < 0){
extendsize = MAX(-remainder, 1 << 5);
if (extend_heap(extendsize) == NULL){
return NULL;
}
}
remainder += extendsize;
delete_node(NEXT_BLKP(ptr));
PUT(HDRP(ptr), PACK(new_size + remainder, 1));
PUT(FTRP(ptr), PACK(new_size + remainder, 1));
}
else{
new_ptr = mm_malloc(new_size - DSIZE);
memcpy(new_ptr, ptr, MIN(size, new_size));
mm_free(ptr);
}
return new_ptr;
}
static void *extend_heap(size_t size){
void *ptr;
size_t asize;
asize = ALIGN(size);
if ((ptr = mem_sbrk(asize)) == (void *)-1)
return NULL;
PUT(HDRP(ptr), PACK(asize, 0));
PUT(FTRP(ptr), PACK(asize, 0));
PUT(HDRP(NEXT_BLKP(ptr)), PACK(0, 1));
insert_node(ptr, asize);
return coalesce(ptr);
}
static void insert_node(void *ptr, size_t size){
int list = 0;
void *search_ptr;
void *before_ptr = NULL;
while ((list < LISTLIMIT - 1) && (size > 1)){
size >>= 1;
list++;
}
search_ptr = segregated_free_lists[list];
while ((search_ptr != NULL) && (size > GET_SIZE(HDRP(search_ptr)))){
before_ptr = search_ptr;
search_ptr = PRED(search_ptr);
}
if (search_ptr != NULL){
if (before_ptr != NULL){
SET_PTR(PRED_PTR(ptr), search_ptr);
SET_PTR(SUCC_PTR(search_ptr), ptr);
SET_PTR(SUCC_PTR(ptr), before_ptr);
SET_PTR(PRED_PTR(before_ptr), ptr);
}
else{
SET_PTR(PRED_PTR(ptr), search_ptr);
SET_PTR(SUCC_PTR(search_ptr), ptr);
SET_PTR(SUCC_PTR(ptr), NULL);
segregated_free_lists[list] = ptr;
}
}
else{
if (before_ptr != NULL){
SET_PTR(PRED_PTR(ptr), NULL);
SET_PTR(SUCC_PTR(ptr), before_ptr);
SET_PTR(PRED_PTR(before_ptr), ptr);
}
else{
SET_PTR(PRED_PTR(ptr), NULL); // SET_PTR(p, ptr) (*(unsigned int *)(p) = (unsigned int)(ptr))
SET_PTR(SUCC_PTR(ptr), NULL);
segregated_free_lists[list] = ptr;
}
}
}
static void delete_node(void *ptr){
int list = 0;
size_t size = GET_SIZE(HDRP(ptr));
while ((list < LISTLIMIT - 1) && (size > 1)){
size >>= 1;
list++;
}
if (PRED(ptr) != NULL){
if (SUCC(ptr) != NULL){
SET_PTR(SUCC_PTR(PRED(ptr)), SUCC(ptr));
SET_PTR(PRED_PTR(SUCC(ptr)), PRED(ptr));
}
else{
SET_PTR(SUCC_PTR(PRED(ptr)), NULL);
segregated_free_lists[list] = PRED(ptr);
}
}
else{
if (SUCC(ptr) != NULL){
SET_PTR(PRED_PTR(SUCC(ptr)), NULL);
}
else{
segregated_free_lists[list] = NULL;
}
}
return;
}
static void *coalesce(void *ptr){
size_t prev_alloc = GET_ALLOC(HDRP(PREV_BLKP(ptr)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));
size_t size = GET_SIZE(HDRP(ptr));
// Do not coalesce with previous block if the previous block is tagged with Reallocation tag
if (prev_alloc && next_alloc){
return ptr;
}
else if (prev_alloc && !next_alloc){
delete_node(ptr);
delete_node(NEXT_BLKP(ptr));
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){
delete_node(ptr);
delete_node(PREV_BLKP(ptr));
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{
delete_node(ptr);
delete_node(PREV_BLKP(ptr));
delete_node(NEXT_BLKP(ptr));
size += GET_SIZE(HDRP(PREV_BLKP(ptr))) + GET_SIZE(HDRP(NEXT_BLKP(ptr)));
PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(ptr)), PACK(size, 0));
ptr = PREV_BLKP(ptr);
}
insert_node(ptr, size);
return ptr;
}
static void *place(void *ptr, size_t asize)
{
size_t ptr_size = GET_SIZE(HDRP(ptr));
size_t remainder = ptr_size - asize;
delete_node(ptr);
if (remainder <= DSIZE * 2){
PUT(HDRP(ptr), PACK(ptr_size, 1));
PUT(FTRP(ptr), PACK(ptr_size, 1));
}
else if (asize >= 120){
PUT(HDRP(ptr), PACK(remainder, 0));
PUT(FTRP(ptr), PACK(remainder, 0));
PUT(HDRP(NEXT_BLKP(ptr)), PACK(asize, 1));
PUT(FTRP(NEXT_BLKP(ptr)), PACK(asize, 1));
insert_node(ptr, remainder);
return NEXT_BLKP(ptr);
}
else{
PUT(HDRP(ptr), PACK(asize, 1));
PUT(FTRP(ptr), PACK(asize, 1));
PUT(HDRP(NEXT_BLKP(ptr)), PACK(remainder, 0));
PUT(FTRP(NEXT_BLKP(ptr)), PACK(remainder, 0));
insert_node(NEXT_BLKP(ptr), remainder);
}
return ptr;
}