- 소프트웨어 정글 5주차 첫 번째 과제로 수행하였다.
처음에 주어진 코드
// memlib.c
/*
* memlib.c - a module that simulates the memory system. Needed because it
* allows us to interleave calls from the student's malloc package
* with the system's malloc package in libc.
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <sys/mman.h>
#include <string.h>
#include <errno.h>
#include "memlib.h"
#include "config.h"
/* private variables */
static char *mem_start_brk; /* points to first byte of heap */
static char *mem_brk; /* points to last byte of heap */
static char *mem_max_addr; /* largest legal heap address */
/*
* mem_init - initialize the memory system model
*/
void mem_init(void)
{
/* allocate the storage we will use to model the available VM */
if ((mem_start_brk = (char *)malloc(MAX_HEAP)) == NULL) {
fprintf(stderr, "mem_init_vm: malloc error\\n");
exit(1);
}
mem_max_addr = mem_start_brk + MAX_HEAP; /* max legal heap address */
mem_brk = mem_start_brk; /* heap is empty initially */
}
/*
* mem_deinit - free the storage used by the memory system model
*/
void mem_deinit(void)
{
free(mem_start_brk);
}
/*
* mem_reset_brk - reset the simulated brk pointer to make an empty heap
*/
void mem_reset_brk()
{
mem_brk = mem_start_brk;
}
/*
* mem_sbrk - simple model of the sbrk function. Extends the heap
* by incr bytes and returns the start address of the new area. In
* this model, the heap cannot be shrunk.
*/
void *mem_sbrk(int incr)
{
char *old_brk = mem_brk;
if ( (incr < 0) || ((mem_brk + incr) > mem_max_addr)) {
errno = ENOMEM;
fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\\n");
return (void *)-1;
}
mem_brk += incr;
return (void *)old_brk;
}
/*
* mem_heap_lo - return address of the first heap byte
*/
void *mem_heap_lo()
{
return (void *)mem_start_brk;
}
/*
* mem_heap_hi - return address of last heap byte
*/
void *mem_heap_hi()
{
return (void *)(mem_brk - 1);
}
/*
* mem_heapsize() - returns the heap size in bytes
*/
size_t mem_heapsize()
{
return (size_t)(mem_brk - mem_start_brk);
}
/*
* mem_pagesize() - returns the page size of the system
*/
size_t mem_pagesize()
{
return (size_t)getpagesize();
}
책 보고 구현한 코드
매크로 & 전역변수
// mm.c
/* single word (4) or double word (8) alignment */ // 블럭 크기다.
#define ALIGNMENT 8
/* rounds up to the nearest multiple of ALIGNMENT */ // alignment의 배수로 올림한다.
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7) // 8로나눈 나머지 전부 제거!
#define SIZE_T_SIZE (ALIGN(sizeof(size_t))) // size_t -> 메모리블럭의 크기를 반환한다. 32비트면 4바이트, 64비트면 8바이트
/*헤더와 푸터의 사이즈 & 워드 사이즈*/
#define W_SIZE 4
/*더블 워드 사이즈*/
#define D_SIZE 8
/*이만큼 확장한다 (4KB)*/
#define CHUNKSIZE (1 << 12)
#define MAX(x, y) ((x) > (y) ? (x) : (y))
/*alloc에 있는 비트 더해주기*/
#define PACK(size, alloc) ((size) | (alloc))
/*주소 p에 있는 값 읽고 쓰기*/
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
/*주소 p에 있는 size, allocated 필드 읽기*/
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
/*블록의 포인터가 주어질 시 (bp), 헤더와 푸터의 주소 계산*/
#define HDR_P(bp) ((char *)(bp) - W_SIZE)
#define FTR_P(bp) ((char *)(bp) + GET_SIZE(HDR_P(bp)) - D_SIZE)
/*현재 블록의 포인터가 주어질 시, 다음 블록의 포인터, 이전 블록의 포인터*/
#define NEXT_BLK_P(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - W_SIZE)))
#define PREV_BLK_P(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - D_SIZE)))
static char *heap_listp; // mem_brk와 같은 역할로 보인다. 단 mem_brk가 static이라 여기서 못쓴다.
coalesce
- 블럭이 free 될 때, 아래, 위 block과 합쳐주는 함수이다.
// mm.c
static void * coalesce(void *bp) {
size_t prev_alloc = GET_ALLOC(FTR_P(PREV_BLK_P(bp)));
size_t next_alloc = GET_ALLOC(HDR_P(NEXT_BLK_P(bp)));
size_t size = GET_SIZE(HDR_P(bp));
if (prev_alloc && next_alloc) { // case 1 : 위아래 모두 차있을 경우
return bp;
}
else if (prev_alloc && !next_alloc) { // case 2 : 위는 차있고 아래가 빈 경우
size += GET_SIZE(HDR_P(NEXT_BLK_P(bp)));
PUT(HDR_P(bp), PACK(size, 0));
PUT(FTR_P(bp), PACK(size, 0));
}
else if (!prev_alloc && next_alloc) { // case 3 : 위는 비었고 아래가 차있는 경우
size += GET_SIZE(HDR_P(PREV_BLK_P(bp)));
PUT(FTR_P(bp), PACK(size, 0));
PUT(HDR_P(PREV_BLK_P(bp)), PACK(size, 0));
bp = PREV_BLK_P(bp);
}
else { // case 4 : 위 아래 모두 빈 경우
size += GET_SIZE(HDR_P(PREV_BLK_P(bp))) + GET_SIZE(FTR_P(NEXT_BLK_P(bp)));
PUT(HDR_P(PREV_BLK_P(bp)), PACK(size, 0));
PUT(FTR_P(NEXT_BLK_P(bp)), PACK(size, 0));
bp = PREV_BLK_P(bp);
}
return bp;
}
extend_heap
// mm.c
static void *extend_heap(size_t words) {
char *bp;
size_t size;
/* words를 짝수로 만들어주고 연산한다. */
size = (words % 2) ? (words+1) * W_SIZE : words * W_SIZE;
/*heap 사이즈를 늘려준다.*/
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
/* free block 헤더, 푸터, 에필로그 헤더를 초기화한다.*/
PUT(HDR_P(bp), PACK(size, 0));
PUT(FTR_P(bp), PACK(size, 0));
PUT(HDR_P(NEXT_BLK_P(bp)), PACK(0, 1));
/*이전 블록이 free면, 합친다*/
return coalesce(bp);
}
mm_init
// mm.c
int mm_init(void)
{
/* 초기 상태의 빈 heap을 만들어준다. */
if ((heap_listp = mem_sbrk(4*W_SIZE)) == (void *)-1)
return -1;
PUT(heap_listp, 0); // Alignment padding
PUT(heap_listp + (1*W_SIZE), PACK(D_SIZE, 1)); // 프롤로그 헤더
PUT(heap_listp + (2*W_SIZE), PACK(D_SIZE, 1)); // 프롤로그 푸터
PUT(heap_listp + (3*W_SIZE), PACK(0, 1)); // 에필로그 헤더
heap_listp += (2*W_SIZE);
/* 빈 힙을 CHUNKSIZE 바이트의 free된 블록으로 확장한다. */
if (extend_heap(CHUNKSIZE/W_SIZE) == NULL)
return -1;
return 0;
}
mm_malloc
// mm.c
void *mm_malloc(size_t size) {
size_t asize;
size_t extendsize;
char *bp;
if (size == 0) {
return NULL;
}
if (size <= D_SIZE)
asize = 2 * D_SIZE;
else
asize = D_SIZE * ((size + (D_SIZE) + (D_SIZE)) / D_SIZE);
/* first fit으로 찾기*/
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
/* 못찾으면 힙 확장하고 블록 추가*/
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize/W_SIZE)) == NULL) {
return NULL;
}
place(bp, asize);
return bp;
}
mm_free