week06. malloc lab-implicit(2)

묵시적 가용 리스트

모든 실용적인 할당기는 블록 경계를 구분하고, 할당된 블록과 가용 블록을 구분하는 데이터 구조가 필요하다.

블록의 구조

이 경우에 한 블록은 1word의 header, Payload, 추가적인 padding으로 구성된다.
본문에서의 1개의 블록은 1 워드(word) = 4byte로 표현한다. 더블 워드는 8byte가 된다.

• header : 블록의 크기와 블록 할당 여부를 담음
• Payload : 데이터를 담는 부분
• Padding : 외부 단편화를 극복하기 위한 방법으로, 정렬 요구사항을 만족하기 위해 필요하다.

헤더에는 블록의 크기와 가용 여부를 나타내는데, 가용 여부는 3자리 비트로 이루어짐.
마지막 비트의 0과 1로 가용 여부를 판단하게 된다.
3비트인 이유는 블록의 크기가 16진수로 비트로 이루어지는데, 가용 여부 또한 16진수 비트로 구성해야 하나의 16진수로 구성할 수 있기 때문이다.

Padding은 블록의 크기를 일괄적으로 정렬해야 하기 때문에 들어가는데,
블록의 크기는 규격화 되어야 효율성이 증가한다.

경계 태그

이전 블록의 가용 여부를 확인하기 위해 각 블록의 끝 부분에 footer(경계 태그)를 추가한 것인데, 이 footer에는 header의 정보가 복사되어 있다.
footer가 존재한다면 각 블록은 자신의 이전 블록의 상태를 조사할 수 있다.

할당기가 현재의 블록을 반환할 때 4가지 케이스
1. 이전 블록과 다음 블록이 모두 할당된 상태
2. 이전 블록이 할당되고, 다음 블록이 가용 상태
3. 이전 블록이 가용상태, 다음이 할당된 상태
4. 이전 블록과 다음 블록 모두 가용 상태

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

코드 전체에서 사용하게 될 상수와 매크로 목록이다.

/* Basic constants and macros */
#define WSIZE 4 // word and header footer 사이즈를 byte로
#define DSIZE 8 // double word size를 byte로
#define CHUNKSIZE (1<<12) // heap을 늘릴 때 4kb 분량으로 늘림.

#define MAX(x,y) ((x)>(y) ? (x) : (y)) // x,y 중 큰 값을 가진다.

// size를 pack하고 개별 word 안의 bit를 할당 (size와 alloc을 비트연산), 헤더에서 써야하기 때문에 생성.
#define PACK(size,alloc) ((size)|(alloc)) // alloc : 가용여부 (ex.000) / size : block size를 의미 -> 이를 통합해서 header와 footer에 저장할 수 있는 값 리턴

/* address p위치에 words를 read와 write 한다.*/
#define GET(p) (*(unsigned int*)(p)) // 인자 p가 참조하는 워드를 읽어서 리턴. 즉, 헤더에 담긴 정보를 꺼낼 수 있음
#define PUT(p,val) (*(unsigned int*)(p)=(val)) // 인자 p가 가리키는 워드에 val을 저장

/* address p위치로부터 size를 읽고 field를 할당 */
#define GET_SIZE(p) (GET(p) & ~0x7) // 0x7를 2진수에서 역수를 취하면 11111000이 됨. 이것을 GET(p)를 통해 가져온 헤더 정보에 and 연산을 하면 block size만 가져올 수 있음
#define GET_ALLOC(p) (GET(p) & 0x1) // 위의 케이스와 반대로 00000001을 and해주면 헤더에서 가용여부만 가져올 수 있음

/* given block ptr bp, header와 footer의 주소를 계산 */
#define HDRP(bp) ((char*)(bp) - WSIZE) // bp의 현재 주소에서 4byte(1워드)만큼 빼주면 헤더의 위치가 됨 (char*)인 이유는 (int*)일 경우에는 WSIZE로 인해 16이 반환되기 때문?
#define FTRP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // 헤더의 끝 지점부터 GET SIZE(블록의 사이즈)만큼 더한 다음 word를 2번빼는게(그 뒤 블록의 헤드에서 앞으로 2번) footer의 시작 위치가 된다.


/* GIVEN block ptr bp, 이전 블록과 다음 블록의 주소를 계산 */
#define NEXT_BLKP(bp) ((char*)(bp) + GET_SIZE(((char*)(bp) - WSIZE))) // 그 다음 블록의 bp 위치로 이동한다.(bp에서 해당 블록의 크기만큼 이동 -> 그 다음 블록의 헤더 뒤로 감.)
#define PREV_BLKP(bp) ((char*)(bp) - GET_SIZE(((char*)(bp) - DSIZE))) // 그 전 블록의 bp위치로 이동.(이전 블록 footer로 이동하면 그 전 블록의 사이즈를 알 수 있으니 그만큼 그 전으로 이동.)

static void *heap_listp;
static char *last_bp;

초기 가용 리스트 만들기

mm_malloc이나 mm_free를 호출하기 전에,
mm_init 함수를 호출해서 힙을 초기화해야 한다.

메모리 시스템에서 4워드를 가져와서 빈 가용 리스트를 만들 수 있도록 초기화하고,
extend_heap 함수를 호출하여 CHUNKSIZE byte로 확장하고
초기 가용 블록을 생성한다.

int mm_init(void)
{
    /* create : 초기의 빈 heap 할당(mem_sbrk) */
    if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)    
        return -1;

    PUT(heap_listp, 0); // Alignment padding 생성
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE,1)); // prologue header 생성
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE,1)); // prologue footer 생성
    PUT(heap_listp + (3*WSIZE), PACK(0,1)); // epilogue block header 생성
    heap_listp += (2*WSIZE); // prologue header와 footer 사이로 포인터를 옮김.
    
    // 빈 Heap을 CHUNKSIZE byte로 확장하고, 초기 가용 블록을 생성해줌 
    if (extend_heap(CHUNKSIZE/WSIZE) == NULL){
        return -1;
    }
    last_bp = (char *)heap_listp; 
    return 0;
}

extend_heap이 호출되는 경우는 2가지이다.

• 힙이 초기화 될 때
• mm_malloc이 적당한 맞춤(fit)을 찾지 못했을 때
  -> 요청한 크기를 8바이트의 배수와 인접하게 반올림하고, 메모리 시스템에
  추가적인 힙 공간을 요청한다.

// 새 가용 블록으로 힙을 확장
static void *extend_heap(size_t words){
    char *bp;
    size_t size;
 
    /* alignment 유지를 위해 짝수 개수의 words를 할당*/
    size = (words % 2) ? (words+1) * WSIZE : words * WSIZE; // 홀수면 앞, 짝수면 뒤가 나옴
    if ((long)(bp = mem_sbrk(size)) == -1)
        return NULL;
    
    // free block header와 footer를 init하고 epilogue header를 init
    PUT(HDRP(bp), PACK(size, 0)); // free block header 생성 / regular block의 총합의 첫번째 부분. 현재 bp위치의 한 칸 앞에 헤더를 생성
    PUT(FTRP(bp), PACK(size, 0)); // free block footer 생성 / regular block의 마지막 부분
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0,1)); // block을 추가했으니 epilogue header를 새롭게 위치 조정해줌
    // HDRP : 1word 뒤에 있는 것을 지칭.
    // bp를 header에서 읽은 사이즈만큼 이동하고, 앞으로 한칸 간다. 그 위치가 결국 늘린 블록 끝에서 한칸 간것이기 때문에, epilogue header 위치가 됨

    // 만약 previous block이 free 상태라면 병합(coalesce)
    return coalesce(bp);
}

새로운 가용 블록을 생성한 뒤, 이전 가용 블록이 free 상태라면
두개의 블록을 합치기 위해 coalesce 함수를 호출하고
통합된 블록의 블록포인터(bp)를 리턴한다.

블록 반환과 연결

이전에 할당받은 블록을 반환하기 위해서는 mm_free 함수를 호출해서 반환하며
인접 가용 블록들을 경계 태그 연결 기술(coalesce)를 이용하여 통합한다.

void mm_free(void *bp)
{
    // 어느 시점에 있는 bp를 인자로 받음
    size_t size = GET_SIZE(HDRP(bp)); // bp의 주소를 가지고 헤더에 접근하여(HDRP) -> block의 사이즈를 얻음(GET_SIZE)
    PUT(HDRP(bp), PACK(size,0)); // header free -> 가용상태로 만들기
    PUT(FTRP(bp), PACK(size,0)); // footer free -> 가용상태로 만들기
    coalesce(bp);
}

static void *coalesce(void *bp){
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // 이전 블록이 할당되었는지 확인 : bp의 포인터를 통해 이전 블록을 찾고, 이 이전블록의 footer를 통해 할당 여부를 확인한다.
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // 다음 블록이 할당되었는지 확인 : bp의 포인터를 통해 다음 블록을 찾고, 이 다음블록의 header를 통해 할당 여부를 확인한다.
    size_t size = GET_SIZE(HDRP(bp)); // 현재 블록의 사이즈 확인

    // case 1 : 이전 블록과 다음 블록이 모두 할당된 케이스 -> 합칠 수 없음
    if (prev_alloc && next_alloc){
        last_bp = bp;
        return bp;
    }
    // case 2 : 이전 블록 : 할당 상태, 다음 블록 : 가용 상태 -> 다음 블록과 합침
    else if (prev_alloc && !next_alloc){
        size += GET_SIZE(HDRP(NEXT_BLKP(bp))); // 다음 블록의 크기를 현재 size에 더해줘요.
        PUT(HDRP(bp), PACK(size, 0)); // header 갱신 (더 큰 크기로 PUT)
        PUT(FTRP(bp), PACK(size,0)); // footer 갱신
    }
    // case 3 : 이전 블록 : 가용 상태, 다음 블록 : 할당 상태 -> 이전 블록과 합침
    else if (!prev_alloc && next_alloc){
        size += GET_SIZE(HDRP(PREV_BLKP(bp))); // 이전 블록의 크기를 현재 size에 더해줘요.
        PUT(FTRP(bp), PACK(size,0)); // 현재 위치의 footer에 block size를 갱신해줌
        PUT(HDRP(PREV_BLKP(bp)), PACK(size,0));
        bp = PREV_BLKP(bp);
    }
    // case 4 : 이전 블록과 다음 블록이 모두 가용 블록인 상태 -> 이전 및 다음 블록 모두 합칠 수 있다.
    else{
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp))); // 이전 블록 및 다음 블록의 크기를 현재 size에 더해줘요.
        PUT(HDRP(PREV_BLKP(bp)), PACK(size,0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size,0));
        bp = PREV_BLKP(bp);
    }
    last_bp = bp;
    return bp;
}

블록 할당

이제 동적으로 메모리를 할당 받기 위해
mm_malloc 함수를 호출해서 원하는 size byte의 메모리 블록을 요청한다.
추가적인 요청들을 체크한 후 할당기는 요청한 블록 크기를 조절해서 헤더와 풋터를 위한 공간을 확보하고, 더블 워드 요건을 만족시킨다.
일단 할당기가 요청한 크기를 조정한 후에 적절한 가용 블록을 가용 리스트에서 검색하고, 맞는 블록을 찾으면 할당기는 요청한 블록을 배치하고,
옵션으로 place 함수를 통해, 초과부분을 분할한 뒤
새롭게 할당한 블록을 리턴한다.

void *mm_malloc(size_t size)
{
    size_t asize; // block 사이즈 조정
    size_t extendsize; // heap에 맞는 fit이 없으면 확장하기 위한 사이즈
    char *bp;

    /* 거짓된 요청 무시 */
    if (size == 0) return NULL;

    /* overhead, alignment 요청 포함해서 블록 사이즈 조정 */
    if (size <= DSIZE){
        asize = 2*DSIZE;
    }
    else{
        // size보다 클 때, 블록이 가질 수 있는 크기 중, 최적회된 크기로 재조정
        asize = DSIZE * ((size + (DSIZE)+(DSIZE-1)) / DSIZE);
    }
    // fit에 맞는 free 리스트를 찾는다.
    if ((bp = next_fit(asize)) != NULL){
        place(bp,asize);
        return bp;
    }
    /* fit에 맞는게 없는 경우, 메모리를 더 가져와 block을 위치시킴 */
    extendsize = MAX(asize, CHUNKSIZE);
    if((bp=extend_heap(extendsize/WSIZE)) == NULL){
        return NULL;
    }
    place(bp, asize);
    last_bp = bp;
    return bp;
}

가용 블록 찾기

가용 블록을 찾기 위해 First fit 방식을 사용한다.
목록의 처음부터 순차적으로 검색해서 조건에 맞는 첫 번째 빈 블록을 선택한다.

static void *find_fit(size_t asize){
    void *bp;
    for (bp = (char *)heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
        // for문이 계속 돌면 epliogue header까지 간다. 
        // epliogue header는 0이므로 끝까지 가면 종료됨
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))){ // 이 블록이 가용상태이고, 내가 갖고있는 asize를 담을 수 있다면
            return bp; // 내가 넣을 수 있는 블록만 찾으면 되기 때문에, 바로 리턴
        }
    }
    return NULL; // NULL 리턴 시, fit에 맞는 block이 없는 것
}

가용 블록을 찾기 위한 Next fit 방식도 존재한다.
First fit과 달리 제일 최근(마지막)에 할당된 블록을 기준으로 다음 블록을 검색하는 방법이다.

static void *next_fit(size_t asize){
    char *bp = last_bp;

    for (bp=NEXT_BLKP(bp); GET_SIZE(HDRP(bp)) != 0; bp = NEXT_BLKP(bp)){
        if (!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp)) >= asize){
            last_bp = bp;
            return bp;
        }
    }
    bp = heap_listp;
    while (bp < last_bp) {
        bp = NEXT_BLKP(bp);
        if (!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp)) >= asize){
            last_bp = bp;
            return bp;
        }
    }
    return NULL;
}

블록 분할 옵션

요청한 블록을 가용 블록에 배치했을 때,
나머지 부분의 크기가 최소 블록의 크기와 같거나(4word) 큰 경우에
여유 분량을 분할(splice)하여 가용 블록으로 만들어주는 옵션이다.

static void place(void *bp, size_t asize){
    /*
    요청한 블록을 가용 블록의 시작 부분에 배치한다. 
    나머지 부분의 크기가 최소 블록의 크기와 같거나 큰 경우에만 분할하는 함수
    */
    // csize : current size, asize : adjust size
    size_t csize = GET_SIZE(HDRP(bp));
    if ((csize-asize) >= (2*DSIZE)){
        // 요청 용량만큼 블록 배치
        PUT(HDRP(bp), PACK(asize,1));
        PUT(FTRP(bp), PACK(asize,1));
        bp = NEXT_BLKP(bp);
        // 남은 블록에 header, footer 배치
        PUT(HDRP(bp), PACK(csize-asize, 0));
        PUT(FTRP(bp), PACK(csize-asize, 0));
    }
    else{
        // csize와 asize 차이가 4word(16byte)보다 작다면 해당 블록을 통째로 사용
        PUT(HDRP(bp), PACK(csize,1));
        PUT(FTRP(bp), PACK(csize,1));
    }
}