목차
동적 메모리 할당기란?
동적 메모리 할당기는 런타임에 추가적인 가상메모리를 획득할 필요가 있을 때 사용합니다.
이는 힙 heap 이라고 하는 프로세스의 가상메모리 영역을 관리합니다.
힙은 다양한 크기의 블록들의 집합으로 구성되고, 각 블록은 할당(allocated) 되었거나 가용(free)한 상태를 가집니다. 가용한 블록들을 할당을 위해 사용할 수 있습니다.
여러 종류의 free list 관리법으로 구현 난이도 혹은 실행 성능등을 개선 할 수 있습니다.
[CS] 그림으로 알아보는 메모리 동적할당 - Implicit, Explicit, Segregated list Allocator
사용자가 필요한 만큼의 메모리를 프로그램이 작동하는 도중에 할당받고자 한다면 어떻게 해야 할까요?
velog.io
malloc 구현 개요
https://bdbest.tistory.com/157?category=968756
Malloc Lab - assignment
목차 개요 직접 실제로 동작하는 나만의 malloc, free, realloc 함수 만들기 사실상 메모리 관련 자료구조를 구현하는 실습. linked_list와 유사하다. lab ( git 자료) 사용법. 내가 수정 할 수 있는 파일은
bdbest.tistory.com
CMU에서 진행되는 malloc lab 과제를 수행하며, CSAPP를 참고해 구현했습니다.
여기서 구현하는 것은 implicit 가용 리스트를 사용하는 할당기입니다.
explicit의 경우
최소 블록 크기는 일반적으로 header(1 word) + footer (1word) + free_list_pointer(2word) 로 최소 4 word에 초기 시작시 시작 패딩 (1word) + epilogue (1word) 로 추가 할당이 필요하기에 최소 6 word가 필요합니다.
동적 할당기 조작을 위한 기본 상수 및 매크로 정의
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
/* 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)))
/* ------------------------------------------------------------------ */
/* CSAPP figure 9.43 */
/* 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 (12) amount (bytes) heap의 초기 사이즈 설정용 */
#define MAX(x, y) ((x) > (y) ? (x) : (y))
/*Pack a size and allocated bit into a word / 헤더와 푸터에 넣기전 블록 크기와, 할당,가용 여부를 합친다 */
#define PACK(size, alloc) ((size) | (alloc)) /* or | 비트 연산자 */
/* Read and write a word at address p */
/* 함수형 매크로 */
#define GET(p) (*(unsigned int *)(p)) /* 인자 p가 참조하는 워드를 읽고 리턴. */
#define PUT(p, val) (*(unsigned int *)(p) = (val)) /* 인자 p가 가리키는 워드에 val을 저장 */
/* Read the size and allocated fields from address p */
#define GET_SIZE(p) (GET(p) & ~0x7) /* 주소 p에 있는 헤더 혹은 푸터의 size를 리턴 16진수로 4비트 이상부터 = ~0x7 */
#define GET_ALLOC(p) (GET(p) & 0x1) /* 헤더 혹은 푸터의 alloc(할당,가용 비트)를 리턴 */
/* 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 its 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))) /**/
/* 함수 선언*/
static char *heap_listp;
static void *find_fit(size_t asize);
static void *extend_heap(size_t words);
static void place(void *bp, size_t asize);
static void *coalesce(void *bp);
HDRP() ~ PREV_BLKP() 등을 이해하기 위한 자료:
mm_init() -> extend_heap() 실행시 묵시적 가용 리스트의 시각화
주요 함수:
- mm_init()
- mm_malloc()
- mm_free()
- mm_realloc()
1. mm_init()
사용되는 주변 함수: extend_heap()
/* mm_init - initialize the malloc package.*/
int mm_init(void)
{
/* Create the initial empty heap */
/* 메모리 시스템에서 4워드를 가져온다. 가상메모리 구현까지는 libc의 malloc을 사용한다. (memlib.c init 참조)*/
// 어디서 선언됐지?
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
return -1;
/* 동적할당기를 위한 초기화. 빈 가상 메모리 가용 리스트 만들기 */
/* PUT(p, val) 인자 p가 가르키는 워드에 val 저장 */
PUT(heap_listp, 0); /* Alignment padding */
/* Prolog block consist 2 word, header, footer, therefore size == DSIZE */
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); /* Prolog header */
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); /* Prolog footer */
PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); /* Epilogue header */
heap_listp += (2 * WSIZE); /* prolog footer 의 시작을 가리킨다. */
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
/* chunksize는 byte 단위로, wsize로 나누면 워드 단위로 바뀐다. */
if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
return -1;
return 0;
}
mm_intit은 malloc, free 등이 호출되기전 힙을 초기화하기 위한 함수이다. extend_heap으로 CHUNKSIZE 바이트로 확장하고 초기 가용 블록을 생성한다. 이를 통해 malloc, free (할당,반환) 요청을 받을 준비를 마친다.
그림 1의 검은색 4개의 워드들이 mm_init 실행 후 extend_heap 실행 전까지의 힙의 모습이다.
2. mm_malloc()
사용되는 주변 함수: extend_heap(), find_fit(), place()
/*
* 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; /* adjusted block size */
size_t extendsize; /* Amount to extend heap if no fit */
char *bp;
/* ignore spurious request */
if (size <= 0)
return NULL;
/* Adjust block size to include overhead and alignment requests */
/* 삽입하려는 데이터 크기(size)를 정렬 기준에 따라 조절한 값을 asize에 담아준다.*/
if (size <= DSIZE)
asize = 2 * DSIZE;
else
asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
/* Search the free list for a fit */
/* 적절한 가용 블록이 없다면 find_fit은 NULL을 리턴 */
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;
}
malloc 함수가 콜되면 다음 단계를 거쳐 실행된다.
1. 인자로 주어진 size가 0이거나 음수라면 무의미하기한 콜이기에 종료된다.
2. 인자로 주어진 size를, 정렬 요건을 만족시키기 위해 8의 배수로 반올림시킨다. (= asize) 최소 블록 크기는 4워드, 2더블워드다.
3. 적절한 가용 블록이 있는지 find_fit()을 통해 힙을 처음부터 블록 단위로 탐색한다. 여기선 first fit method로 진행된다.
3.1 있다면 place() 로 size 만큼의 블록을 할당하고 해당 블록 주소, bp를 반환한다.
4. 적절한 가용 블록이 없다면(asize보다 큰 가용블록이 없음) extend_heap을 통해 공간을 늘려주고 place()를 진행하고 마무리한다.
3. mm_free()
/*
* 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);
}
주어진 블록 포인터 bp를 가지고 header와 footer의 할당 여부를 가용 상태로 바꿔준다. (1 -> 0 )
4. mm_realloc()
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *bp, size_t size)
{
/* equivalent to mm_free(ptr). if size <= 0 */
if (size <= 0)
{
mm_free(bp);
return 0;
}
/* equivalent to mm_malloc(size). if bp == NULL */
if (bp == NULL)
{
return mm_malloc(size);
}
/* re-allocation begin */
/* 새롭게 요청된 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 */
/* 1st 인자: 복사받을 메모리를 주소 */
/* 2nd 인자: 복사할 메모리를 주소 */
/* 3rd 인자: 복사할 메모리 길이 (bytes) */
/* 원래 블록을 새롭게 할당한 블록에 복사해준다. */
memcpy(newp, bp, oldsize); //cover.
/* 원 메모리를 해제해준다*/
mm_free(bp);
return newp;
}
mm_realloc() 은 이미 할당된 메모리의 크기를 바꾸고 싶을 때 사용하는 함수이다. 더 작은 메모리가 필요한 경우는 상정하지 않고, 추가적인 메모리를 할당해주는 방식을 구현했다.
1. size 가 0이랑 같거나 작다면 해당 메모리를 free 하자는 것과 동일한 의미로 받아들인다.
1.1 bp 가 NULL 이라면 size 만큼을 새롭게 할당해달라는 의미로 받아들인다.
2. mm_malloc을 통해 새롭게 요청된 size에 맞는 블록을 할당해준다.
3. 원래 블록을 memcpy() c 언어 내장함수로 복사해 새롭게 할당한 블록으로 붙혀넣어준다.
주변 함수:
- find_fit()
- extend_heap()
- place()
- coalesce()
1. find_fit()
first_fit()
/* 묵시적 가용리스트에서 first fit 검색을 수행 */
static void *first_fit(size_t asize)
{
/* first fit search */
void *bp;
/* heap_listp 는 시작 포인트, prolog의 header 다음을 가르키고 있다. */
/* GET_SIZE(HDRP(bp)) 가 0보다 작을 경우는 epilouge block을 만났을 때다.*/
/* for문의 스탭마다 bp를 다음 블록으로 옮긴다. */
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
{
/* free block 이고, asize 가 들어갈 수 있다면*/
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
{
return bp;
}
}
return NULL; /* no fit */
}first fit의 경우 항상 리스트의 시작지점부터 탐색을 시작해 가장 처음 요청된 크기에 맞는 블록의 주소를 반환한다.
first fit의 장점.
가장 큰 가용블록들을 리스트 뒤에 남겨두는 경향이 있다.
단점:
리스트 앞부분에 작은 가용 블록들을 남겨두는 경향이 있어서 큰 블록을 찾는 경우에 검색 시간이 늘어난다.
next_fit()
static void *next_fit(size_t asize)
{
void *bp;
if (next_fit_p == NULL)
next_fit_p = heap_listp;
/* 지난번 포인트부터 서치 시작. */
for (bp = next_fit_p; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
{
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
{
next_fit_p = bp;
return bp;
}
}
for (bp = heap_listp; bp != next_fit_p; bp = NEXT_BLKP(bp))
{
/* free block 이고, asize 가 들어갈 수 있다면*/
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
{
next_fit_p = bp;
return bp;
}
}
/* no fit */
next_fit_p = NULL;
return NULL;
}
next fit
검색을 리스트의 처음에서 시작하는 대신, 이전 검색이 종료된 지점에서 검색을 시작한다.
이는 이전 검색에서 가용 블록을 발견했다면 다음 검색에서는 리스트의 나머지 부분에서 원하는 블록을 찾을 가능성이 높다는 아이디어에서 착안한 방법이다.
next fit의 장점
next fit 은 first fit에 비해서 매우 빠른 속도를 갖는다. 리스트의 앞부분이 많은 작은 가용블록으로 이루어질 경우 특히 더 이런 성향을 보인다.
단점:
일부 연구 결과에 의하면 next fit 이 first fit 보다 최악의 메모리 이용도를 갖는 것으로 밝혀졌다.
2. extend_heap()
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;
/* sbrk는 size로 음수가 주어지거나, 가상메모리 공간을 초과할 경우 -1을 retrun */
/* 성공적일 경우, brk ptr에 incr 즉 size를 더해주고, 더하기 이전 주소를 return */
/* mm_init()에서 한번 콜된 sbrk 덕분에 mem_brk가 새로운 top을 가르키고 있다. */
/* 그렇기에 sbrk가 다시 콜되면 올바르게 힙이 커진다. 그리고 bp에는 return된 old brk가 대입된다.*/
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
/* Initialize free block header/footer and the epilouge 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 epilouge header */
/* coalesce if the previous block was free */
return coalesce(bp);
}
3. place()
static void place(void *bp, size_t asize)
{
/* 현재 가용 블록의 크기 c(urrent)ize */
size_t csize = GET_SIZE(HDRP(bp));
/* csize와 asize의 차이가 2*Dsize 보다 크다면, 새로운 블록을 만들 공간이 되기에 */
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
{
/* cszie를 size로 배정한다. 1 워드 정도 차이가 난다면 이는 padding 워드가 된다. */
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
4. 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));
/* case 1 : prev & next all alloc */
if (prev_alloc && next_alloc)
{
next_fit_p = bp;
return bp;
}
/* case 2 : prev alloc & next free */
else if (prev_alloc && !next_alloc)
{
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0));
/* def FTRP에 get_size(HDRP(bp))가 포함되어있기에 HDRP 이후 바로 FTRP 가능 */
PUT(FTRP(bp), PACK(size, 0));
bp = PREV_BLKP(bp);
}
/* case 3 : prev free & next alloc */
else if (!prev_alloc && next_alloc)
{
size += GET_SIZE(FTRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
/* */
bp = PREV_BLKP(bp);
}
/* case 4 : prev free & next free */
else
{
size += GET_SIZE(FTRP(PREV_BLKP(bp))) + GET_SIZE(HDRP(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_p = bp;
return bp;
}
'sw사관학교 정글 2기 > 컴퓨터 시스템' 카테고리의 다른 글
| Tiny 웹 서버 소스코드 분석 및 웹서버에 대한 것들. (0) | 2021.09.24 |
|---|---|
| 네트워크 - Protocol, TCP/IP, OSI 계층, TCP, UDP, HTTP 등등 (0) | 2021.09.16 |
| c - 비트 연산자, 매크로 (0) | 2021.09.10 |
| Malloc Lab - assignment (0) | 2021.09.09 |
| Red Black Tree - 소스 코드 해석- (1) | 2021.09.07 |
댓글