정글사관학교 44일차 TIL: Explicit malloc 정리 및 구현 review

어제 떡하니 코드만 달랑 올려놓고 말아서 많은 분들이 실망했을 것으로 아는 바, 오늘은 디테일하게 Explicit 방식에 대해 정리하고 코드까지 리뷰하는 것으로 TIL 정리를 해보겠다.

정리를 하기 전에, 동적 메모리 할당 이전에 나오는 개념인 시스템 콜에 대해 간단히 정리하고 넘어간다.

시스템 콜

시스템 콜: OS(특히 커널)이 제공하는 서비스에 접근하기 위한 상호작용을 말한다.

• 커널(kernel): 메모리에 상주하고 있는 운영체제 핵심 중 일부를 뜻한다. 응용프로그램이 컴퓨터 시스템에서 수행되기 위해서는 메모리에 프로그램이 올라가 있어야 한다. 운영체제 역시 하나의 프로그램으로, 메모리에 올라가야 하는데 OS는 무겁기 때문에 필요한 핵심만 메모리에 올라간다. 이때, 메모리에 상주해 있는 OS의 일부를 커널이라 한다.

커널은 메모리나 하드웨어와 같이 중요한 컴퓨터 시스템 자원을 관리한다. 중요한 것들이니 사용자가 실수로 건드렸다가는 대참사가 일어날 수 있기에 OS에서는 두 가지 모드를 제공하여 이를 방지한다. User 모드와 Kernel 모드가 그것이다.

1. User 모드: 사용자가 응용프로그램을 실행하는 모드. 유저가 접근 가능한 영역은 제한적으로 두고 메모리/하드웨어 등 자원에 함부로 접근하지 못하게 한다.
2. Kernel 모드: 운영체제 코드를 실행하는 모드이다. 모든 자원에 접근이 가능하다. 컴퓨터 환경에 치명적인 영향을 끼칠 수 있는 명령을 특권 명령이라 하는데, 이 특권 명령은 커널 모드에서만 실행이 가능하다. 따라서 여기에 접근이 불가능한 User 모드에서는 안전하게 사용할 수 있다.

만약 OS가 시스템 자원을 활용하고 싶다면? 시스템 콜을 해서 모드를 전환해 커널 서비스를 사용한다. 만약 시스템 콜을 하면 프로그램은 유저 모드에서 커널 모드로 전환한다. 명령 수행이 끝나면 다시 유저 모드로 복귀한다.

Explicit allocation(명시적 할당)

응용프로그램이 직접 메모리를 할당/반환하는 방식의 할당기이다. Java 같은 상위 수준 언어들은 할당되어 있으나 사용하지는 않는 블록을 자동으로 반환하는 기능인 garbage collection을 제공하는 반면, C와 같은 저수준 언어는 app에서 직접 메모리를 할당/반환해줘야 한다.

malloc 패키지와 sbrk, mmap

void* malloc(size_t, size): 성공 시 적어도 size만큼 메모리 블록을 초기화하지 않고 리턴한다.

• x86(32비트)은 2word(8 bytes), x86-64(64비트)는 4word(16 bytes) 정렬 블록을 기본 단위로 리턴한다.
• mmap or sbrk 함수를 이용해 명시적으로 힙 메모리를 할당/반환한다.\

void* free (void* p)

• 할당된 블록의 시작을 가리키는 주소를 인자로 받아서 가용 상태 블록으로 만든다.
• 이때 주소 p에 해당하는 블록은 반드시 alloc, malloc, realloc으로 할당된 상태여야 한다.

calloc(): 초기화된 블록을 할당받는다.

realloc(): 초기에 할당받은 블록의 크기를 줄이거나 늘린다.

mmap(): 커널에 새 가상 메모리 영역을 생성해줄 것을 요청하는 함수.

sbrk(): space break 함수로, 힙 크기를 늘이거나 줄이는 함수다. 커널의 brk 포인터(힙의 맨 끝을 가리키는 포인터)에 incr만큼 크기를 더해서 힙을 늘이거나 줄인다. 성공하면 이전의 brk 포인터 값을 리턴한다. 실패하면 -1을 리턴하고 errno = ENOMEM 이라고 설정해준다. incr = 0이면 늘어나지 않았으니 현재의 brk 값을 리턴한다.

할당기 처리량 & 최고 메모리 이용도 간 밸런스 조절

• 할당기 처리량: 단위 시간 당 완료되는 요청 수
• peak memory utilization(메모리 최고 이용도): 힙을 얼마나 효율적으로 쓰고 있나?를 측정하는 척도. 할당 데이터 크기가 커질수록 힙 크기도 커진다. 이때 할당기가 메모리 공간을 낭비할수록 할당 메모리 용량 대비 힙 크기가 증가한다.

할당기 구현 이슈

• 가용 블록 구성: 사용할 수 있는 가용 블록을 어떻게 추적하는가?
• 배치: 할당하려는 가용 블록을 어떻게 선택하나?
• 분할: 가용 블록보다 더 작은 블록을 할당했을 때, 나머지 가용 블록은 어떻게 처리할까?
• 반환: 전달받은 주소로 얼마나 많은 메모리를 반환하나?
• 연결: 방금 반환된 블록은 어떻게 연결하나?

Explicit Free list

핵심 아이디어

가용 블록끼리 포인터로 연결해 다음 블록 위치를 명시적으로 알 수 있다.

 

개요

가용 블록은 header와 footer 말고는 데이터를 필요로 하지 않는다. ⇒ 가용 블록 안의 payload 자리에 다음 가용블록(successor block)과 이전 가용 블록(predecessor block)의 주소를 저장한다.

• 하나의 이중 연결 리스트를 만들어서 가용 블록을 연결한다.
• 다음 가용 블록은 Implicit 방식과 달리 메모리 내에서 물리적으로 연속적이지 않아도 된다. 주소 상으로 인접 블록이 아니더라도 포인터 주소를 이용해서 위치를 찾아간다. 아래 이미지처럼 논리적으로는 연속적이나 물리적으로는 엉켜있는 것을 볼 수 있다.

할당

해당 가용 리스트를 분할한 다음 새 가용 블록을 기존 가용 블록과 링크되었던 이전(prev), 다음(next) 블록과 연결한다.

가용

새로 반환된 가용 블록을 free 리스트 어디에 연결해줘야 하는가?

LIFO (Last In First Out) 방안

• free list 처음에 새 반환 블록을 넣는다. (스택 생각하면 됨)
• 간단하고 O(1)의 시간 복잡도를 가지나 단편화 발생 확률이 높다.

Address Ordered 방안

• Free list를 주소 순으로 연결한다. (이전 블록 주소 < 현재 블록 주소 < 다음 블록 주소)
• Fragmentation 확률은 낮아지나 탐색 시간이 길어진다. (주소 순으로 연속적으로 연결하니 일일이 찾아가면서 해야 해서)

💡 여기서는 LIFO 방식을 설명한다.

• Case 1: 반환 블록 양쪽이 할당되어 있을 때
  • 해당 블록만 가용 상태로 반환하면 되니 추가 작업이 필요 없다

  • 

• Case 2: 반환 블록 직전이 할당 블록, 직후가 가용 블록일 때
  • 직후 블록을 Free list에서 떼어낸 다음 현재 반환할 블록 뒤로 연결한다.
  • 새로 연결한 블록을 free list의 root와 연결한다.

  • 

• Case 3: 반환 블록 직전이 가용블록, 직후가 할당 블록
  • 직전 블록을 Free list에서 떼어낸 다음 반환 블록과 연결한다.
  • 새 블록을 Free list의 root와 연결한다.

  • 

• Case 4: 반환 블록 직전/직후 전부 다 가용 블록일 때
  • 직전 블록/직후 블록을 각각 free list에서 떼어낸 다음 반환 블록과 연결한다.
  • 새 블록을 Free list의 root와 연결한다.

  • 

malloc 구현 - Explicit

memlib.c

💡 기존 `malloc` 패키지 대신 힙 메모리 초기화와 sbrk 함수를 정의한 패키지

변수(global variable)

• mem_start_brk: 힙의 첫 바이트를 가리키는 변수
• mem_brk: 힙의 마지막 바이트를 가리키는 변수. 이 포인터 뒤에다 sbrk 함수로 새로운 사이즈의 힙을 할당받아 연결한다.
  • 할당된 가상 메모리: mem_start_brk와 mem_brk 사이
  • 미할당된 가상 메모리: mem_brk 이후
  • mem_max_addr: 힙의 최대 크기(20MB)의 주소를 가리키는 변수

함수

• void mem_init(void)
  • 먼저 20MB만큼 MAX_HEAP(최대 크기만큼)을 malloc으로 동적 할당해온다. 만약 메모리를 불러오는데 실패했다면 에러를 띄우고 프로그램을 종료. 이때의 시작점이 mem_start_brk다.
  • 아직 힙이 비어있으니 mem_brk도 mem_start_brk와 같다.

  • void mem_init(void)
    {
        /* allocate the storage we will use to model the available VM */
        // config.h에 정의되어 있음, #define MAX_HEAP (20*(1<<20)) : 20971520bytes == 20 MB
        if ((mem_start_brk = (char *)malloc(MAX_HEAP)) == NULL) {
    	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 */
    }

• 💡 최대 힙 메모리 공간을 할당받고 초기화
• void* mem_sbrk(int incr)
  • 힙을 줄이려 하거나 최대 힙 크기를 넘어버리면 -1을 리턴.
  • old_brk 주소를 리턴하는 이유: 새 메모리 시작부터 사용해야 하므로.

  • void *mem_sbrk(int incr) // 바이트 형태로 입력 받음
    {
      char *old_brk = mem_brk; // 힙 늘이기 전 끝 포인터를 저장 (mem_brk는 힙의 끝 가리킴)
      // 힙이 줄어들거나 최대 힙 사이즈 벗어나면 메모리 부족으로 에러처리 & -1을 리턴
    	if ( (incr < 0) || ((mem_brk + incr) > mem_max_addr)) {
    			errno = ENOMEM; // 메모리 부족 에러 처리
    			frintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
    			return (void *)-1; // 리턴 값이 void* 여야 하니 형 변환해줌
    	}
    	mem_brk += incr; //mem_brk에 incr만큼 더해서 힙 늘려줌
    	return (void *)old_brk; //이전 brk를 리턴 => 새로운 메모리를 처음부터 사용해야 하니 (위 코드에서 old_brk 뒤로는 여분 공간이 생겨난 상태!)

• 💡 바이트 단위로 필요 메모리 크기를 입력받아 그 크기만큼 힙을 늘려주고 새 메모리의 시작 지점을 리턴.

 

mm.c (Explicit Allocator, First-fit)

• int mm_init(void)

  

• 💡 Explicit allocator의 초기 힙은 6word의 메모리를 가진다.

• int mm_init(void)
  {
  	/* 메모리에서 6word 가져오고 이걸로 빈 가용 리스트 초기화 */
  	/* padding, prol_header, prol_footer, PREC, SUCC, epil_header */
  	if ((heap_listp = mem_sbrk(6*WSIZE)) == (void*) -1)
  		return -1;
  	
  	PUT(heap_listp, 0) // Alignment padding. 더블 워드 경계로 정렬된 미사용 패딩.
  	PUT(heap_listp + (1*WSIZE), PACK(MINIMUM, 1));
    PUT(heap_listp + (2*WSIZE), NULL); // prec
    PUT(heap_listp + (3*WSIZE), NULL); // succ
    PUT(heap_listp + (4*WSIZE), PACK(MINIMUM, 1));
    PUT(heap_listp + (5*WSIZE), PACK(0, 1));
  
    free_listp = heap_listp + 2*WSIZE;
  
    /* 그 후 CHUNKSIZE만큼 힙을 확장해 초기 가용 블록을 생성 */
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL) 
    { // 실패하면 -1 리턴
        return -1;
    }
    return 0;
  }

• static void* coalesce(void* bp)

    static void* coalesce(void* bp){
        //직전 블록의 footer, 직후 블록의 header를 보고 가용 여부를 확인.
        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: 직전, 직후 블록이 모두 할당 -> 해당 블록만 free list에 넣어준다.
  
        // case 2: 직전 블록 할당, 직후 블록 가용
  
        if (prev_alloc && !next_alloc) {
            removeBlock(NEXT_BLKP(bp)); // free 상태였던 직후 블록을 free list에서 제거
            size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
            PUT(HDRP(bp), PACK(size, 0));
            PUT(FTRP(bp), PACK(size, 0));
        }
  
        // case 3: 직전 블록 가용, 직후 블록 할당
        else if (!prev_alloc && next_alloc){ // alloc이 0이니까  !prev_alloc == True.
            removeBlock(PREV_BLKP(bp)); // 직전 블록을 free list에서 제거
            size += GET_SIZE(HDRP(PREV_BLKP(bp)));
            PUT(HDRP(bp), PACK(size, 0));
            PUT(FTRP(bp), PACK(size, 0));
        }
  
        // case 4: 직전, 직후 블록 모두 가용
        else if (!prev_alloc && !next_alloc) {
            removeBlock(PREV_BLKP(bp));
            removeBlock(NEXT_BLKP(bp));
            size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp))); // 앞뒤 free된 블록 전체 사이즈 계산
            bp = PREV_BLKP(bp); // 현재 bp를 가용인 앞쪽 블록으로 이동시켜 => 거기가 전체 free 블록의 앞쪽이 되어야 함.
            PUT(HDRP(bp), PACK(size, 0));
            PUT(FTRP(bp), PACK(size, 0));
        }
  
        // 연결된 새 가용 블록을 free list에 추가
        putFreeBlock(bp);
  
        return bp;
    }

• 💡 만약 반환 블록 직전/직후 중 free 블록이 있다면 그 블록을 free list에서 없애준 후 반환 블록과 연결한다. 그 후 연결된 새 블록을 free list의 첫 부분에 넣는다.

 

• void putFreeBlock(void* bp)포인터 free_listp는 free list의 첫 주소를 가리키므로, free_listp가 가리키는 free list 안의 블록과 PRED, SUCC 링크를 진행한다.(DK's github 참조)

    void putFreeBlock(void* bp){
        SUCC_FREEP(bp) = free_listp;
        PREC_FREEP(bp) = NULL;
        PREC_FREEP(free_listp) = bp;
        free_listp = bp;
    }

• 

• 💡 새 free 블록을 free list의 처음에 추가한다.

 

• void removeBlock(void* bp)free list 상에서 해당 블록의 이전/이후 블록을 서로 이어준다.

• void putFreeBlock(void* bp){
      SUCC_FREEP(bp) = free_listp;
      PREC_FREEP(bp) = NULL;
      PREC_FREEP(free_listp) = bp;
      free_listp = bp;
  }

• 💡 할당되거나 연결되는 가용 블록을 free list에서 없앤다.

 

• static void* find_fit(size_t asize)

    static void* find_fit(size_t asize){
        /* First-fit */
        void* bp;
  
        // free list의 맨 뒤는 프롤로그 블록이다. Free list에서 유일하게 할당된 블록이므로 얘를 만나면 탐색 종료.
        for (bp = free_listp; GET_ALLOC(HDRP(bp)) != 1; bp = SUCC_FREEP(bp)){
            if(asize <= GET_SIZE(HDRP(bp))){
                return bp;
            }
        }
  
        // 못 찾으면 NULL을 리턴한다.
        return NULL;
  
    }

• 💡 First fit 방식으로 구현. free list에서 유일한 할당 블록은 맨 뒤의 프롤로그 블록이므로, 할당된 블록을 만났다는 뜻은 모든 free list 노드를 다 훑은 것으로 본다(==종료 조건)
• static void place(void* bp, size_t asize)앞에서 putFreeBlock이 새롭게 만들어진 free 블록을 free list에 넣는 작업이라면, place()는 직접적으로 힙에 할당 메모리를 넣는 작업.

• static void plce(void* bp, size_t asize) {
  	// 현재 할당할 수 있는 후보 가용 블록 주소
  	size_t csize = GET_SIZE(HDRP(bp)));
  	
  	// 할당될 블록이므로 free list에서 없애준다.
  	removeBlock(bp);
  	
  	// 분할이 가능한 경우
  	if ((csize - asize) >=(2*DSIZE)){
  		// 앞 블록은 할당 블록으로 & 뒷 블록은 가용 블록으로 분할.
  		
  		// 여기는 앞 블록을 할당 블록으로
  		PUT(HDRP(bp), PACK(asize, 1));
  		PUT(FTRP(bp), PACK(asize, 1));
  		// 뒷 블록은 가용블록으로 분할
  		bp = NEXT_BLKP(bp); // 블록 포인터 이동
  		PUT(HDRP(bp), PACK(csize - asize, 0));
  		PUT(FTRP(bp), PACK(csize - asize, 0));
  		
  		// free list 첫번째에 분할된 블록을 넣는다.
  		putFreeBlock(bp);
  	}
  	else {
  		PUT(HDRP(bp), PACK(csize, 1));
  		PUT(FTRP(bp), PACK(csize, 1));
  	}
  }

• 💡 할당할 수 있는 free 블록을 free list에서 없애준다. 할당 후 만약 분할되었다면, 새 가용 리스트를 free list에 넣어준다.

Reference

전반적인 흐름 모두 DK's github을 참조.(감사합니다 DK!)