Malloc LAB - Implicit (1)

최교진·2021년 1월 19일
c언어malloc동적할당자료구조
2

malloc LAB

목록 보기
1/3
post-thumbnail

Malloc이란? C언어의 동적 메모리 할당을 의미합니다. (Dynamic Memory Allocation)

  • 예를 들어 배열의 크기를 미리 알수 없다면? 어떻게 메모리를 할당해줘야 할까요?

    → 이 때 쓰이는 것이 '동적 메모리 할당'

  • implicit, explicit, seglist 등 여러 방법이 있지만, 우리는 implicit 방법을 이용해서 랩을 수행하겠습니다. 여유가 되면 explicit 까지도 도전해보세요.

말록랩 과제 설명

참고자료

기본 할당기 설계

주어진 파일 리스트의 memlib.c 파일을 살펴보면 할당기의 기본적인 설계를 볼 수 있다.

  1. mem_init
  • mem_start_brk : 힙의 시작점
  • mem_max_addr : 가능한 legal heap의 끝 주소
  • mem_brk : 힙의 종료점
    (init 단계에서는 heap이 비어 있으므로 mem_start_brk와 같다.
  1. mem_sbrk
  • 추가 힙 메모리를 요청하고 성공하면 기존 힙의 시작점 주소를, 아니면 -1을 리턴한다.

Implicit Malloc

mm.c 파일에서 조작해야 할 함수는 아래와 같다.
(본 글에서는 6번까지 구현할 예정)

  1. mm_init
  2. extend_heap
  3. mm_free
  4. coalesce
  5. mm_malloc
  6. find_fit
  7. mm_realloc
  8. place

mm_init

할당기의 초기화 함수. 묵시적 가용 리스트는 아래와 같은 구조를 가지고 있다.

  • Header : 블록의 할당 여부와 크기를 저장한다.

  • Payload : 할당된 블록에만 값이 들어있다.

  • Padding : Double Word 정렬을 위해 붙여 주는 공간.

  • Footer : 경계 태그로 사용되며, Header의 값이 복사되어 있다. 블록을 반환할 때 이전 블록을 상수 시간 내에 탐색할 수 있도록 하는 장치.

    (Footer가 없으면 모든 블록의 size 정보가 다르기 때문에 이전 Header를 찾아내기 위해서는 힙의 시작점부터 순차적으로 탐색해야 하는 불편이 생긴다)

  1. 위의 블록 구조를 참고하여, 프롤로그 블록 + 에필로그 블록을 초기화 시 할당한다. 이 블록은 Header와 Footer로 구성된 8바이트 할당 블록이며, 할당기 프로그램이 종료될 때까지 반환되지 않는다. (이유는 경계 조건을 무시하기 위해)
  2. 또한 Double Word 정렬을 위해 사용하지 않는 패딩 블록을 맨 앞에 붙여놓는다.
  3. 힙이 확장될 때 에필로그 블록은 확장된 힙의 마지막에 위치하도록 한다.
  • mm_init
int mm_init(void)
{
    /* Create the initial empty heap */
    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
        return -1;
    PUT(heap_listp, PACK(DSIZE, 1));               /* 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 header ** when find func, note endpoint */
    heap_listp += (2 * WSIZE);

    /* Extend the empty heap with a free block of CHUNKSIZE bytes */
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;
    return 0;
}

extend_heap

이 함수는 2가지 경우에 호출될 수 있다.

  1. 힙이 초기화될 때
    초기화 후에 초기 가용 블록을 생성하기 위해 호출된다.
  1. 요청한 크기의 메모리 할당을 위해 충분한 공간을 찾지 못했을 때
    Double word 정렬을 위해 8의 배수로 반올림하고, 추가 힙 공간을 요청한다.
  • extend_heap
static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;

    /* Allocate an even number of words to maintain alignment */
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1)
        return NULL;

    /* Initialize free block header/footer and the epilogue header */
    PUT(HDRP(bp), PACK(size, 0));         /* Free block header */
    PUT(FTRP(bp), PACK(size, 0));         /* Free block footer */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */

    /* Coalesce if the previous block was free */
    return coalesce(bp);
}

mm_free / coalesce

블록을 반환하고(= mm_free) 경계 태그(Header, Footer)를 사용해서 상수 시간 내에 인접한 가용 블록(free)들과 통합한다. (= coalesce)

여기서는 4가지 Case가 존재한다.

  • Case 1 : 이전과 다음 블록이 모두 할당되어 있다.
    - 현재 블록만 가용 상태로 변경한다.
  • Case 2 : 이전 블록은 할당 상태, 다음 블록은 가용 상태이다.
    - 현재 블록과 다음 블록을 통합한다.
  • Case 3 : 이전 블록은 가용 상태, 다음 블록은 할당 상태이다.
    - 이전 블록과 현재 블록을 통합한다.
  • Case 4 : 이전 블록과 다음 블록 모두 가용 상태이다.
    - 이전 블록, 현재 블록, 다음 블록을 통합한다.

프롤로그와 에필로그를 할당 상태로 초기화했기 때문에, free를 요청한 블록의 주소 bp가 힙의 시작 부분 또는 끝 부분에 위치하는 경계조건(Edge Condition)을 무시할 수 있게 된다.

  • mm_free / coalesce
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));

    if (prev_alloc && next_alloc)
    { /* Case 1 */
        return bp;
    }

    else if (prev_alloc && !next_alloc)
    { /* Case 2 */
        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)
    { /* Case 3 */
        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);
    }

    else
    { /* Case 4 */
        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);
    }

    return bp;
}

mm_malloc / find_fit

요청한 size 만큼의 공간이 있는 메모리 블록을 할당하는 함수. 아래의 기능을 구현한다.

  • Header와 Footer 공간을 위해 최소 16bytes(4워드)의 크기를 유지하도록 한다.

  • Double Word 정렬을 유지하기 위해 8의 배수로 반올림한 메모리 크기를 할당한다.

  • 메모리 할당 크기를 조절한 후, 가용 블록 리스트를 검색하여 적합한 블록을 찾았을 때 배치한다.
    - find_fit 함수
    - 여기에서는 First Fit 방식을 사용한다.

    가용 상태이고, 요청한 사이즈만큼 충분한 공간이 있을 때 해당 블록 포인터(bp)를 반환

  • OPTION : 찾은 블록에 배치한 후 여유공간이 충분하다면 분할한다. (= place)

  • mm_malloc
void *mm_malloc(size_t size)
{
    size_t asize;      /* Adjusted block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *bp;

    /* Ignore spurious requests */
    if (size == 0)
        return NULL;

    /* Adjust block size to include overhead and alignment reqs. */
    if (size <= DSIZE)
        asize = 2 * DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);

    /* Search the free list for a fit */
    if ((bp = find_fit(asize)) != NULL)
    {
        place(bp, asize);
        return bp;
    }

    /* No fit found. Get more memory and place the block */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
        return NULL;
    place(bp, asize);
    return bp;
}
  • find_fit
static void *find_fit(size_t asize)
{
    /* first-fit search */
    char *bp;

    // start the search from the beginning of the heap
    for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
    {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
        {
            return bp;
        }
    }
    return NULL; /* No fit */
}
profile
최교진
코딩 벌레가 되어보자
다음 포스트

Malloc LAB - Implicit (2)

0개의 댓글