관련 내용에 대해서는 저번 포스팅에서 설명했기에 이번 포스팅에서는 묵시적 가용 리스트를 이용해 구현한 동적 메모리 할당기 코드를 보도록 하겠다.
코드
코드 내부에 unistd.h 등의 헤더는 유닉스에서 사용할 수 있는 헤더로 따로 설정을 하지 않는 이상 window 환경에서는 돌아가지 않습니다.
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include <sys/mman.h>
#include <errno.h>
#include "mm.h"
#include "memlib.h"
//bp는 항상 헤더 뒤에 위치함
/* double word (8) alignment */
#define WSIZE 4 //word size
#define DSIZE 8 //double word size
#define CHUNKSIZE (1<<12) // heap을 확장할 때 확장할 최소 크기
#define MAX(x, y) ((x) > (y)? (x) : (y))
#define PACK(size, alloc) ((size) | (alloc)) //header에 들어갈 값
#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)
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
//다음 블록 위치 = 지금 위치에서 지금 블록의 크기 만큼 뒤로 가면 다음 블록 header 바로 뒤
//(본인 블록 header에서 블럭 크기 확인)
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
//이전 블록 위치 = 지금 위치에서 이전 블록 크기 만큼 앞으로 가면 이전 블록 header 바로 뒤
//(이전 블록의 footer에서 이전 블록의 크기 확인)
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
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);
char* heap_listp;1. mm_init
mm_init 함수는 초기 힙 영역을 할당하는 것과 같은 필요한 초기화들을 수행한다.
가용리스트는 아래와 같은 변하지 않는 형태를 유지한다.
더블 워드 경계 정렬방식으로 인한 미사용 패딩 워드 뒤에 헤더와 풋터로만 구성된 8바이트 할당 블록인 프롤로그 블록이 온다. 그 뒤로 malloc 또는 free를 통해 호출된 일반 블록들이 오고 힙은 항상 에필로그 블록으로 끝난다.
프롤로그와 에필로그 블록은 연결과정 동안 가장자리 조건을 없애주기 위해 임의로 설정한 블록이다.
/*
* 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));
PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1));
PUT(heap_listp + (3*WSIZE), PACK(0, 1));
heap_listp += (2*WSIZE);
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}2. extend_heap
확장하고자 하는 사이즈를 인자로 받는 extend_heap함수는 인자로 받은 사이즈를 더블워드 정렬 조건에 맞게 8의 배수로 만들고 그 사이즈 만큼 힙을 확장시킨다.
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
size = (words % 2) ? (words+1) * WSIZE : words * WSIZE; //8의 배수로 만들기
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
PUT(HDRP(bp), PACK(size, 0)); //size크기의 블록 생성
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); //새로운 epilogue block 생성
return coalesce(bp);
}3. mm_malloc
void *mm_malloc(size_t size)
{
size_t asize;
size_t extendsize;
char *bp;
//확장을 원하는 사이즈가 양수가 아니면 NULL반환
if (size <= 0)
return NULL
//블럭의 최소크기를 맞추기 위해 size를 조정
//블럭의 최소 크기는 16byte(header(4byte) + footer(4byte) + data(1byte 이상) = 9byte -> 8의 배수로 만들기 = 16byte
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;
}
//할당 가능한 영역이 없으면 heap 확장
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
return NULL;
place(bp, asize);
return bp;
}3. find fit과 place
find fit은 first fit 방식으로 할당 가능한 가용영역을 찾는 함수이다.
처음에 설정한 heap_listp부터 선형탐색으로 필요한 가용영역을 찾는다.
place함수는 선택된 가용영역에 할당을 시키는 함수이다.
선택된 가용영역이 필요한 영역 + 최소 블럭 크기(16byte) 이상이라면 필요한 영역만큼 할당시킨 후 분할을 실행한다.
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 place(void*bp, size_t asize)
{
size_t csize = GET_SIZE(HDRP(bp));
//가용영역의 크기가 필요한 영역 + 16byte 이상이면 분할
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));
}
}4. free와 realooc
free함수는 인자로 받은 블록에 할당되어 있던 메모리를 반환한다.
header와 footer에 가용상태를 0으로 갱신하고 앞 뒤에 연결할 수 있는 블록이 있다면 연결해준다.
realloc함수는 기본으로 주어진 내용을 바꾸지는 않았다.
realloc은 이미 할당한 블록의 크기를 바꿀 때 사용한다. 인자로 주어진 블록의 데이터를 인자로 주어진 사이즈 만큼의 다른 블록으로 옮긴다.
이때 인자로 주어진 사이즈 만큼의 블록을 찾기 위해 malloc이 수행된다.
만약 인자로 주어진 사이즈가 기존 블록의 사이즈보다 작다면 인자로 주어진 사이즈만큼의 데이터만 잘라서 옮긴다.
memcpy는 기본으로 제공되는 함수로 블록 내 데이터를 옮기는 역할을 한다.
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);
}
void *mm_realloc(void *bp, size_t size){
if(size <= 0){ //equivalent to mm_free(ptr).
mm_free(bp);
return 0;
}
if(bp == NULL){
return mm_malloc(size); //equivalent to mm_malloc(size).
}
void *newp = mm_malloc(size); //new pointer.
if(newp == NULL){
return 0;
}
size_t oldsize = GET_SIZE(HDRP(bp));
if(size < oldsize){
oldsize = size; //shrink size.
}
memcpy(newp, bp, oldsize); //cover.
mm_free(bp);
return newp;
}5. coalesce
coalesce함수는 가용블록의 앞이나 뒤에 연결할 수 있는 가용블록이 존재한다면 연결해 더 큰 가용블록을 만드는 역할을 한다.
가용블록의 이전, 다음 블록의 할당 여부를 확인해 할당이 되지 않았다면 연결을 진행한다.
만약 앞에 있던 블록과 연결했다면 bp는 항상 header의 뒤를 가르켜야 하기 때문에 앞에 있던 블록의 header 뒤로 갱신해준다.
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){
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);
}
return bp;
}피드백 환영합니다.
-끝-
