[TIL] CSAPP 9장 공부4 - 간단한 할당기2(Explicit, first-fit)

1. 아침 문제 풀이

1. 25192번 - 인사성 밝은 곰곰이

import sys

N = int(sys.stdin.readline())
record = {}
count = 0

for _ in range(N) :
    input = sys.stdin.readline().strip()
    if input == 'ENTER' :
        record = {} # 모든 기록 초기화
    elif input not in record :
        count += 1
        record[input] = 1

print(count)

 아침마다 같이 공부하는 사람들끼리 문제를 풀고 있다.
오늘 문제는 좀 귀여웠다. 
저번 금요일의 문제 풀이에 이어서 Hash를 사용하여 풀면 된다.

---

2. Explicit Free List

명시적 가용 리스트

1. 묵시적 가용 리스트

• 전에 구현해본 implicit free list는 블록 할당 시간이 전체 힙 블록 수에 비례
  • 모든 힙 블록을 탐색하기 때문에
• 범용 할당기에 적합하지 않다.

---

2. 기본 설계

사용할 블록 format

heap 영역 구조

• 이중 연결 가용 리스트
  • prev : 현재 블록에서 이전 가용 블럭 주소
  • next : 현재 블록에서 다음 가용 블럭 주소
• first_list : 가용 리스트의 top
  • 블록을 반환하는 시간은 가용 리스트 내에서 블록을 정렬하는 정책에 따라 달라진다.
  • 후입선출 구조를 유지하도록 새로 할당된거나 반환되는 블록을 리스트의 top으로 설정
  • 대부분의 최근에 사용된 블록들을 먼저 조사

---

3. 매크로 정의

• PREV_FREE(bp) : 현재 블록의 prev 가 저장되어 있는 위치 반환
• NEXT_FREE(bp) : 현재 블록의 next가 저장되어 있는 위치 반환

---

4. 함수 정의

1. put_free_block : 가용 리스트에 블럭 삽입하기

가용 리스트 삽입

• 새로 삽입된 블록의 prev = NULL
• 새로 삽인된 블록의 next = first_list가 가리키고 있던 블록
• first_list가 가리키는 블록의 prev = 새로 삽입된 블록
• first_list = 새로 삽입된 블록

2. remove_free_block

• top에 위치한 블럭을 제거할 경우
  • first_list 위치 변경
  • 현재 블럭의 prev = NULL;
• 중간에 있는 블럭을 제거할 경우
  • 현재 블럭의 NEXT → prev 값 변경
  • 현재 블럭의 PREV → next 값 변경

---

5. 구현시 주의할 점

• mm_init()
  • 처음 할당 받아야 할 크기 = 24byte
  • Padding, Prolog Header, Prolog prev, Prolog next, Prolog Footer, Epilogue Header
  • 각각 4byte로 총 6개이므로 24byte를 할당 받아야 한다.
•  find_fit()
  • 이 함수는 가용 영역 중 알맞은 영역이 있으면 그 영역을 반환해주는 함수이다.
  • 명시적 가용 리스트에서는 탐색 방향을 top → prolog 로 잡았다. (LIFO)
  • prolog 는 가용 리스트에서 유일한 할당 비트를 가지므로 GET_ALLOC() 매크로로 알아낼 수 있다.
• place()
  • 이 함수는 할당 받은 가용 영역에 데이터를 할당한다.
  • 대신, 할당하고 남은 영역이 존재하면 분할해야 한다.
  • 그러므로 가용 리스트에서 할당받은 영역을 제거(remove_free_block)
  • 그 후 남은 가용 영역이 존재하면 그 영역을 리스트에 추가(put_free_block)
• coalesce()
  • 인접한 가용 영역이 존재할 때 이를 연결해주는 함수
  • 만약 합쳐지는 경우가 생기면 똑같은 위치를 저장되지 않도록 해야한다.
  • 즉, 현재 영역과 합쳐질 영역들은 모두 리스트에서 제거해주어야한다.
  • 무조건 현재 가용 영역은 리스트에 추가해주어야 한다.

---

< 참고 블로그 >

🔗 https://dean30.tistory.com/45?category=967988

🔗 https://ttl-blog.tistory.com/1079

🔗 https://grapestore.tistory.com/87

🔗 https://d-cron.tistory.com/m/33

 

---

현재 malloc-lab 과제 진행상황

1. implicit (first-fit) 구현 완료 - 54점

2. implicit (next-fit) 구현 완료 - 83점

3. explicit (first-fit, LIFO) 구현 완료 - 82점

---

🛠️ C 구현 코드

#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 // 2워드
#define WSIZE 4 // 1워드
#define CHUNKSIZE (1 << 12) //초기 가용 블록과 힙 확장을 위한 기본 크기

/* -------------- 매크로 정의 ------------------------------------------ */
#define MAX(x, y) ((x) > (y) ? (x) : (y)) //큰 값 반환

#define PACK(size, alloc) ((size) | (alloc)) //Header or Footer 에 저장할 값 반환

#define GET(p) (*(unsigned int *)(p)) //p가 참조하는 word 반환
#define PUT(p, val) (*(unsigned int *)(p) = (val)) //p가 가리키는 word에 val 저장

#define GET_SIZE(p) (GET(p) & ~0x7) //p가 가리키는 block size 반환
#define GET_ALLOC(p) (GET(p) & 0x1) //p가 가리키는 block의 할당 비트 반환

#define HDRP(bp) ((char *)(bp) - WSIZE) //bp가 가리키는 block의 Header를 가리키는 포인터 반환
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - ALIGNMENT) //bp가 가리키는 block의 Footer를 가리키는 포인터 반환

#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) //다음 block pointer 반환
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - ALIGNMENT))) //이전 block pointer 반환

#define PREV_FREE(bp) (*(void **)(bp)) //현재 블록의 이전 가용 블록 주소 저장 위치 반환
#define NEXT_FREE(bp) (*(void **)(bp + WSIZE)) //현재 블록의 다음 가용 블록 주소 저장 위치 반환

/* -------------- 함수 정의 -------------------------------------------- */
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);
static void put_free_block(void *bp);
static void remove_free_block(void *bp);

/* -------------전역 변수 선언 --------------------------------------------*/
static void *heap_listp;
static char *first_list; //가용 리스트의 헤더

/* 
 * mm_init - initialize the malloc package.
 * 할당기를 초기화한다.
 * 성공이면 0 / 아니면 -1 반환
 */
int mm_init(void){
    if ((heap_listp = mem_sbrk(3 * ALIGNMENT)) == (void *)-1) {
        return -1;
    }
    PUT(heap_listp, 0); //Padding Word
    PUT(heap_listp + (1*WSIZE), PACK(ALIGNMENT * 2, 1)); //Prolog Header

    PUT(heap_listp + (2*WSIZE), NULL); //Prolog prev
    PUT(heap_listp + (3*WSIZE), NULL); //Prolog next

    PUT(heap_listp + (4*WSIZE), PACK(ALIGNMENT * 2, 1)); //Prolog Footer
    PUT(heap_listp + (5*WSIZE), PACK(0, 1)); //Epilogue Header - 크기를 0으로 할당
    
    first_list = heap_listp + ALIGNMENT; //가용 리스트의 top 설정

    if (extend_heap(CHUNKSIZE/WSIZE) == NULL) {
        return -1;
    }
    return 0;
}

/*
 * 힙을 확장하기 위한 함수
 * 1. 힙을 초기화할 때
 * 2. mm_malloc()이 적당한 fit을 찾지 못했을 때
 * 요청한 크기를 정렬을 유지하기 위해 8(double words)의 배수로 반올림하여 요청
 */
static void *extend_heap(size_t words) {
    char *bp;
    // words가 홀수일 경우 1을 더한 후 4만큼 곱해준다.
    size_t size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;

    //실패했을 경우
    if ((long)(bp = mem_sbrk(size)) == -1) {
        return NULL;
    }

    //새로운 가용 블록 생성
    PUT(HDRP(bp), PACK(size, 0)); //가용 블록의 HEADER
    PUT(FTRP(bp), PACK(size, 0)); //가용 블록의 FOOTER
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); //새로운 Epilogue

    //새로 할당 받은 가용 블록 앞에 또다른 가용 블록이 존재할 수 있다.
    return coalesce(bp);
}

/* 
 * 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;
    size_t extendsize;
    char *bp;

    //size가 0이면 필요 없다.
    if (size <= 0) {
        return NULL;
    }

    //size가 2 word 보다 작을 경우
    if (size <= ALIGNMENT) {
        asize = 2 * ALIGNMENT;
    }
    else { //클 경우
        asize = ALIGNMENT * ((size + (ALIGNMENT) + (ALIGNMENT - 1)) / ALIGNMENT);
    }

    //할당할 수 있는 가용 영역이 있으면
    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }

    //할당할 영역이 없으므로 힙 영역 확장하기
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL) {
        return NULL;
    }
    place(bp, asize);
    return bp;
}

/*
 * explicit free list를 이용한 first-fit
 */
static void *find_fit(size_t asize) {
    void *bp = first_list; //가용리스트의 top
    //top -> prolog 블록 방향으로 탐색
    //가용 리스트 내부의 유일한 할당 블록이다.
    while (GET_ALLOC(HDRP(bp)) != 1) {
        if (GET_SIZE(HDRP(bp)) >= asize) {
            return bp;
        }
        bp = NEXT_FREE(bp);
    }
    return NULL;
}

/*
 * 할당받은 영역이 사용하고 남은 영역이 분할 가능한지 파악
 * 최소 블록 크기 = 16byte
 */
static void place(void *bp, size_t asize) {
    size_t size = GET_SIZE(HDRP(bp));
    remove_free_block(bp); //할당받은 영역은 가용 리스트에서 제거
    if ((size - asize) >= (2 * (ALIGNMENT))) {
        //앞에서부터 할당하기
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));

        //나머지는 다음 블록에 가용 영역 할당
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(size - asize, 0));
        PUT(FTRP(bp), PACK(size - asize, 0));

        //남은 가용 영역 리스트에 추가하기
        put_free_block(bp);
    }
    else { //현재 영역 전부 사용
        PUT(HDRP(bp), PACK(size, 1));
        PUT(FTRP(bp), PACK(size, 1));
    }
}

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *ptr) {
    size_t size = GET_SIZE(HDRP(ptr));

    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    //연결할 수 있는 가용 블록이 있으면 연결하기
    coalesce(ptr);
}

/*
 * 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));

    if (prev_alloc && next_alloc) { //둘다 할당되어 있는 상태일 때
        put_free_block(bp); //현재 가용 블럭 리스트에 추가하기
        return bp;
    }
    else if (prev_alloc && !next_alloc) { //이전 블록만 할당되어 있을 때
        remove_free_block(NEXT_BLKP(bp)); //다음 블록 리스트에서 제거 (현재와 연결하므로)
        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) { //다음 블록만 할당되어 있을 때
        remove_free_block(PREV_BLKP(bp)); // 이전 블럭 리스트에서 제거
        size += GET_SIZE(HDRP(PREV_BLKP(bp))); //이전 블록 사이즈만큼 증가
        bp = PREV_BLKP(bp);
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
        // //현재 가용 블록과 이전 가용 블록 더하기
        // PUT(FTRP(bp), PACK(size, 0));
        // PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        // //블록의 앞을 가리켜야 하므로 이전의 블록 포인터가 현재 블록 포인터
        // bp = PREV_BLKP(bp);
    }
    else { //둘다 할당 안되어 있을 때
        remove_free_block(PREV_BLKP(bp)); // 이전 블럭 리스트에서 제거
        remove_free_block(NEXT_BLKP(bp)); // 다음 블록 리스트에서 제거
        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);
    }
    put_free_block(bp); //현재 가용 블럭 리스트에 추가하기
    return bp;
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size) {
    void *oldptr = ptr;
    void *newptr;
    size_t copySize;
    
    newptr = mm_malloc(size);
    if (newptr == NULL)
      return NULL;
    copySize = GET_SIZE(HDRP(oldptr));
    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

/*
 * 반환되거나 새로 할당된 가용 블럭을 top으로 설정
 */
static void put_free_block(void *bp) {
    PREV_FREE(bp) = NULL;
    NEXT_FREE(bp) = first_list;
    PREV_FREE(first_list) = bp;
    first_list = bp;
}

/*
 * 사용한 가용 블록은 가용 리스트에서 제거되어야 한다.
 */
static void remove_free_block(void *bp) {
    if (bp == first_list) {
      PREV_FREE(NEXT_FREE(bp)) = NULL;
      first_list = NEXT_FREE(bp);
    }
    else {
        NEXT_FREE(PREV_FREE(bp)) = NEXT_FREE(bp);
        PREV_FREE(NEXT_FREE(bp)) = PREV_FREE(bp);
    }
}