malloc lab-implicit list에 관하여 + 구현

묵시적 할당리스트

malloc을 구현함에 있어
가장 중요한 부분은 할당가능부분 을 찾는 것이다.

해서 효율적인 할당리스트들은 자유블록안에 포인터가 구성되어있고, 이를 위한 자료구조가 필요하다고 한다.

그럼 묵시적 할당리스트는 무엇이냐 하면 블록내의 포인터는 존재하지 않고
헤더로만 할당할수 있는 블록인지 아닌지를 판별하는 할당리스트이다.
(이름 이해하기가 까다로웠다..)

그 원리가 무엇이냐면

블록크기는 워드크기(32비트의 경우 4바이트, 64비트면 8바이트)의 두배로 잡았다고 가정하면, 항상 8의 배수의 블록크기만 갖는다고 할 수 있다.

이 점에서 8의 배수라면 마지막 3비트는 사용하지않는다. 이점을 활용하여
가장 끝 3비트를 활용할 기회가 생기고 자유영역을 확인하는 비트로 사용한다.

그래서 처음 4바이트, 끝 4바이트는 항상 헤더와 푸터로 고정시킨 후
페이로드에는 할당받을 데이터크기,
패딩은 8의 배수를 맞출 영역이다.

따라서 페이로드는 0일 수 없기 때문에 위 경우 최소 블록은 16바이트이다.

헤더와 푸터에 사이즈와 가용여부가 존재하기 때문에
블록을 넘어다니기 쉽다.

결론은 할당리스트에 대해 감을 잡기 좋은 케이스 같다.
처음엔 감이 하나도 안잡혔는데 어쨌든 알고리즘적으로는 건너뛰고 여부를 판단하고
넘겨준다는 점에서 단순구현이 가능하기 때문이다.

---

구현

전체적인 흐름

memlib.c

mem_init

1. 실제 할당받을 전체 힙크기를 malloc으로 받아놓는다. (환경세팅 개념)
2. 🤔 왜 malloc을 구현하는데 malloc을 할당받는가?

https://github.com/bminor/glibc

주요 메모리 할당 파일들:
malloc/malloc.c # 메인 malloc 구현
malloc/arena.c # 멀티스레드 arena 관리
malloc/hooks.c # 디버깅/프로파일링 훅
sysdeps/unix/sysv/linux/sbrk.c # sbrk 시스템콜 래퍼

- 리눅스 시스템에 내장되어있는데 시스템콜로 접근하는 것은 더 복잡하다.

   3. 그래서 실제로 구현하는 것은 아니고, malloc알고리즘 이해라고 보면 된다.

void mem_init(void) {
  /* allocate the storage we will use to model the available VM */
  if ((mem_start_brk = (char *)malloc(MAX_HEAP)) == NULL) {  // 20MB크기
    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_sbrk

• 힙의 크기를 늘리는 것처럼 보이게 해주는 함수.
• maxheap을 넘지 않는 선에서 필요한 만큼 추가 할당 (포인터 위치변경)

예시) 원래 힙이 100이었다면 포인터가 101에 있다가
넘어가면 101반환하고 다시 200에 가있는 형식

void *mem_sbrk(int incr) {
  char *old_brk = mem_brk;  // 메모리의 현재 주소를 저장, 이때 char인 이유는
                            // 바이트 단위 연산이 필요하기 때문이다.

  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;         // 여기서 mem_brk가 그거됨
  return (void *)old_brk;  // void형으로 반환하는 이유는 받는부분에서
                           // 타입캐스팅을 유연하게 하기 위함.
}

mm.c

mm_init()

• 프롤로그(8바이트 할당) 헤더와 푸터를 설정
• 에필로그(0바이트 할당) 헤더를 생성
  • 푸터를 생성할 필요가 없음
• 힙영역 시작위치만 프롤로그데이터영역으로 바꾼다음 4kb extend

int mm_init(void) {
  if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1) return -1;

  PUT(heap_listp, 0);

  PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));  // 0x1008 = 0x11 헤더
  PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));  // 0x1010 = 0x11 헤더
  PUT(heap_listp + (3 * WSIZE), PACK(0, 1));      // 0x1018 = 0x01 헤더

  heap_listp += (2 * WSIZE);  // 프롤로그의 페이로드부분에 항상 위치.
  free_list_root = NULL;
  // 힙을 페이지크기로 늘림 처음으로의 자유영역
  if (extend_heap(CHUNKSIZE / WSIZE) == NULL) return -1;

  return 0;
}

extend_heap(word)

• 사이즈를 요청 워드만큼 위 mm_sbrk 함수를 이용해서 확장
• 프롤로그와 에필로그 설정 (이때부터 프롤로그도 할당가능)
• coalesce함수로 자유영역 확장(밑에서 나옴)

static void *extend_heap(size_t words) {
  size_t size;
  char *bp;
  // 짝수워드로 데이터를 늘린다
  size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;

  bp = mem_sbrk(size);

  if ((long)bp == -1) return NULL;

  PUT(HDRP(bp), PACK(size, 0));
  PUT(FTRP(bp), PACK(size, 0));
  PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));

  // 안하고 들어가도 된다.coalesce에서 자유영역에 추가함.
  return coalesce(bp);
}

coalesce(bp)

1. 앞, 뒤 자유영역을 같이 확장하기 위한 함수
   • 해당 지역만 free한다면 블록의 수가 늘어나므로 비효율적
   • 외부단편화 위험있음(블록의 크기가 작을 것이기 때문에)
   • free인 영역을 하나로 합쳐서 조절하면서 할당
     

     

2. 위 그림처럼 4가지 경우가 존재한다.

// 자유영역 병합 함수
static void *coalesce(void *bp) {
  size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
  // 다음의 헤더를 보고 alloc 확인
  size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));

  int size = GET_SIZE(HDRP(bp));

  if (prev_alloc && next_alloc) {  // 앞뒤 둘다 데이터가 있다면
    add_free_list(bp);
    return bp;
  } else if (prev_alloc && !next_alloc) {
    // next가 자유영역
    remove_free_list(NEXT_BLKP(bp));
    size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
    PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));  // 1번잘못
    PUT(HDRP(bp), PACK(size, 0));
    add_free_list(bp);
  } else if (!prev_alloc && next_alloc) {
    remove_free_list(PREV_BLKP(bp));
    size += GET_SIZE(HDRP(PREV_BLKP(bp)));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
    bp = PREV_BLKP(bp);
    add_free_list(bp);
  } else {
    remove_free_list(PREV_BLKP(bp));
    remove_free_list(NEXT_BLKP(bp));
    size += GET_SIZE(HDRP(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);
    add_free_list(bp);
  }

  return bp;
}

mm_malloc(size)

• 할당할 사이즈를 더블워드 사이즈로 반올림한다.
• find_fit함수를 이용해 최초적합위치를 찾아 포인터반환
• place함수를 이용해 자유영역을 분리

void *mm_malloc(size_t size) {
  size_t asize;        // 할당할 사이즈
  size_t extend_size;  // 양을 늘릴 사이즈
  char *bp;

  if (size <= 0) return NULL;

  if (size <= DSIZE)
    asize = DSIZE * 2;
  else
    asize = DSIZE * ((size + DSIZE + (DSIZE + 1)) / DSIZE);  // 반올림 공식

  if ((bp = find_fit(asize)) != NULL) {
    place(bp, asize);
    return bp;
  }

  extend_size = MAX(asize, CHUNKSIZE);
  if ((bp = extend_heap(extend_size / WSIZE)) == NULL) return NULL;

  place(bp, asize);
  return bp;
}

 

find_fit(bp, size)

순회를 돌며 비할당영역+사이즈가 맞으면 bp 반환

 

 

static void *find_fit(size_t asize) {
char *bp;
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
  // 에필로그의 값이 0인 것을 이용
  if (!GET_ALLOC(HDRP(bp)) && (GET_SIZE(HDRP(bp)) >= asize)) {
    return bp;
  }
}
return NULL;
}

 

place(bp, size)

해당 사용영역이 사이즈를 빼고도 16바이트가 남으면(최소블록단위)
가용영역을 분리하여 단편화를 줄인다.

static void place(void *bp, size_t asize) {
  // 이미 가능할때만 들어온다.
  size_t free_alloc_size = GET_SIZE(HDRP(bp));
  if (free_alloc_size - asize >= (DSIZE * 2)) {
    // 남은 양이 최소블록크기를 넘는다면
    PUT(HDRP(bp), PACK(asize, 1));
    PUT(FTRP(bp), PACK(asize, 1));

    PUT(HDRP(NEXT_BLKP(bp)), PACK(free_alloc_size - asize, 0));
    PUT(FTRP(NEXT_BLKP(bp)), PACK(free_alloc_size - asize, 0));
  } else {
    PUT(HDRP(bp), PACK(free_alloc_size, 1));
    PUT(FTRP(bp), PACK(free_alloc_size, 1));
  }
}

mm_free(ptr)

• 다시 할당가능영역으로 바꿔주는 함수.

void mm_free(void *ptr) {
  size_t size = GET_SIZE(HDRP(ptr));

  PUT(HDRP(ptr), PACK(size, 0));  // 헤더 0처리
  PUT(FTRP(ptr), PACK(size, 0));  // 푸터 0처리
  coalesce(ptr);
}

 

---

구현하며

커널수준에서 직접가상메모리에 접근하는 것이 아니고, 

받아온 영역에서 메모리를 할당하는 코드! 정확히는 메모리할당에 관해 고려하게 됐다.

앞으로 fit별로 구현해보고 어떤식으로 달라지는 확인해보자!