9.9.12 종합 설계 : 간단한 할당기의 구현

할당기 기본 설계

• mem_init
  힙에 가용한 가상 메모리를 큰 더블 워드로 정렬된 바이트의 배열로 모델.
• mem_heap
  mem_heap과 brk 사이 바이트가 할당된 가상 메모리를 나타낸다.
• mem_brk
  brk 다음에 오는 바이트는 미할당 가상 메모리가 된다.
• mem_sbrk
  추가적 힙메모리를 요청하는 함수.
  힙을 축소하라는 요청을 거부하는 것만 제외하고 sbrk 함수와 동일한 의미.

세 개의 함수.

1. extern int mm_init(void);
   할당기를 초기화.
   성공하면 0, 아니면 -1 리턴.
   header(블록사이즈+가용/비가용), payload, padding(옵션),
   footer로 이루어짐.
2. extern void *mm_malloc (size_t size);
   실제 malloc 함수처럼 작용.
3. extern void mm_free (void *ptr);
   실제 free 함수처럼 작용.

static char *mem_heap; 
static char *mem_brk;
static char *mem_max_addr;
...

void mem_init(void)
{ mem_heap = (char *)malloc(MAX_HEAP);
mem_brk = (char *)mem_heap;
mem_max_addr = (char *)(mem_heap + MAX_HEAP);}

void *mem_sbrk(int incr)
{
	char *old_brk = mem_brk;
    
    if ( (incr < 0) || 
    	((mem_brk + incr) > mem_max_addr)) {
      errno = ENOMEM;
      fprintf(stderr, "ERROR : ....");
      return (void *)-1;
      }
    mem_brk += incr;
    return (void *)old_brk;

mem_brk로 현재 brk를 가져와서,
만약 원하는 incr, 증가값이 음수거나,
현재 값에서 증가 시키는게 초과한다면 실패 선언.

아니라면 brk를 그냥 incr만큼 증가시켜준다.

...
그 뒤로 malloc 함수를 설명해주지만
코드는 ...안 적어주고 있나?

아 나중에 적어주는군.
확실히 init 자체에서 malloc을 쓰면 모순이겠지.

묵시적 가용 리스트로 구성하며,

• 더블 워드 경계로 정렬된 미사용 패딩 워드.
• prolog 블록. (헤더와 풋터로만 구성된 8바이트 할당 블록.)
  (초기화시 생성하며 절대로 반환하지 않는다.)
• malloc, free로 인해 생성된 0, 또는 1개 이상 일반 블록.
• epilogue 블록.
  헤더만으로 구성되었으며 크기가 0인 블록.

할당기는 한 개의 정적 전역 변수(static)를 사용하며
항상 프롤로그 블록을 가리킨다.

가용 리스트 조작을 위한 기본 상수와 매크로

#define WSIZE	4	// word와 헤더, 풋터 사이즈.
#define DSIZE	8	 // 더블 워드 사이즈.
#define CHUNKSIZE (1<<12)	// 초기 가용 블록과 힙 확장을 위한 기본 크기.

#define MAX(x, y) ((x) >(y)? (x) : (y))

#define PACK(size, alloc) ((size) | (alloc)) 
// 크기와 할당 비트를 통합. 헤더와 풋터에 저장할 수 있는 값을 리턴함.

#define GET(p)	(*(unsinged int *)(p)) // 인자 p가 참조하는 워드를 읽어서 리턴. 
// p가 가리키는 메모리 위치에서 4바이트 워드를 읽어서 리턴.
#define PUT(p, val) (*(unsigned int *)(p) = (val)) 
// 인자 p가 가리키는 워드에 val을 저장.

#define GET_SIZE(p)	(GET(p) & ~0x7) // 주소 p에 있는 헤더 또는 풋터의 size를 리턴.
#define GET_ALLOC(p) (GET(p) & 0x1) // 주소 p에 있는 헤더 또는 풋터의 할당 비트를 리턴.

// bp는 블록 포인터.
#define HDRP(bp)	((char *)(bp) - WSIZE) // 헤더를 가리키는 포인터를 리턴.
#define FTRP(bp) 	((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) 
// 풋터를 가리키는 포인터를 리턴.

#define NEXT_BLKP(bp)	((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) 
// 다음 블록 포인터를 리턴.
#define PREV_BLKP(bp) 	((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) 
// 이전 블록 포인터를 리턴.

이런식의 사용이 가능하다.

size_t size = GET_SIZE(HDRP(NEXT_BLKP(bp)));

초기 가용 리스트 만들기

int mm_init(void)
{

	// 만약 현재 4배의 더블 워드를 더한다면 죽는다고 선언할 경우 실패.
	if((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
    	return -1;
    
    
    // padding 정렬용.
    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);
    
    // 다 배정했으니 heap의 크기를 늘려놓겠다.
    if(extend_heap(CHUNKSIZE/WSIZE) == NULL)
    	return -1;
    return 0;
    
    }

...

static void *extend_heap(size_t words)
{
	char *bp;
    size_t size;
   
   // 짝수배의 워드만큼 할당.
    size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size) == -1)
    	return NULL;
        
    //free block 헤더, 풋터, 에필로그 헤더 초기화.
    PUT(HDRP(bp), PACK(size,0)); // free 헤더
    PUT(FTRP(bp), PACK(size,0)); // free 풋터
    PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1)); // 새로운 에필로그 헤더
    
    //앞선 블록이 free라면 연결해주겠다..
    return coalesce(bp);
    
    }

...

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);}

...
연결하는 함수.

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 : 둘 다 할당.
    if(prev_alloc && next_alloc) {
    	return bp;
        }
    // case 2 : 뒤가 가용.
    else if (prev_alloc && !next_alloc){
    	size += GET_SIZ(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size,0));}
    // case 3 : 앞이 가용.
    else if (!prev_alloc && next_alloc){
    	size += GET_SIZ(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size,0));
        bp = PREV_BLKP(bp);}
    // case 4 : 앞 뒤 가용.
    else{
    	size += GET_SIZ(HDRP(PREV_BLKP(bp))) 
        	+ GET_SIZ(HDRP(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;
    
    }
     

...
malloc

void *mm_malloc(size_t size)
{
	size_t asize; // 적정 블록 사이즈.
    size_t extendsize; // 
    char *bp;
    
    // 만약 용량을 요구하지 않을 경우 무시.
    if (size == 0)
    	return NULL;
    
    // overhead와 정렬 reqs를 포함한 사이즈.
    if (size <= DSIZE)
    	asize = 2*DSIZE;
    else
    	asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
        
    // free list에서 딱 맞는 거 찾기.
    if ((bp = find_fit(asize)) != NULL){
    	place(bp, asize);
        return bp;
        
    // 딱 맞는거 못 찾았다면 메모리 더 갖고 오기.    
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
    	retunr NULL;
    place(bp, asize);
    return bp;
    
    }

...
find_fit

static void *find_fit(size_t asize)

static void place(void *bp, size_t asize)