Heap

Heap이란?

 -> 프로그램이 실행되는 도중 동적으로 할당되고 헤제하여 사용하는 메모리 영역

 

동적 메모리 할당자의 종류

• tcmalloc - google
• ptmalloc2 - glibc
• Libumem - Solaris
• Jemalloc - FreeBSD and Firefox
• dlmalloc - General purpose allocator

dlmalloc

현재 우분투에서 사용되는 메모리할당자의 기본 알고리즘은 dlmalloc과 동일

 

heap이 생기고 없어지는 원리

char *p = malloc(size)

  원하는 size만큼 malloc을 호출하여 동적 메모리 할당

free(p)

  사용한 메모리를 free하여 반환

 

생기는 위치

특정 크기의 메모리 영역을 미리 할당한 뒤 이 영역을 사용하는 방식 -> free한 뒤에도 이 부분은 남아있음

 

CHUNK

• mem : malloc으로 할당받은 부분
• chunk : header(사이즈 정보)와 mem을 포함하는 영역
  • p = malloc(40); -> 0x2010의 주소를 return 받았다면
  • strcpy(p,"AAAA");
  • free(p);
• size : chunk의 크기
  • 32bit는 8byte, 64bit는 16byte단위로 정렬
• prev_size : 인접한 앞쪽 chunk의 크기
  • 앞쪽 청크가 free 될 때 prev_size가 초기화 됨

chunk size

size : chunk의 크기뿐만 아닌 3가지 속성도 나타냄

• 32bit는 8byte, 64bit는 16byte단위로 정렬

이 부분이 청크의 특성을 나타내는 데 사용

이 때 chunk사이즈 하위 3비트가 0이 된다.

왜냐면

1. 8바이트 정렬

   64bit 시스템에서 메모리 블록은 최소 8바이트 경계에 맞춰 할당된다.

   따라서 실제 크기는 8의 배수여야 하고, 그 결과 하위 3비트가 0이 된다.

2. 플래그 비트

   하위 3비트는 크기정보 대신 malloc의 내부 플래그를 저장하는데 사용된다.

 

예를들어 01000 = 8

이 있을 때

1번째 0이 1이되면 즉 01100 이 되면 non_main_arena에 속하면 1, 아니면 0

2번째 0이 1이되면 즉 01010 이 되면 is_mmaped 로 할당되었다면 1, 아니면 0

3번째 0이 1이되면 즉 01001 이 되면 prev_inuse bit 즉 인접한 이전 청크가 할당되면 1, 해제되면 0이 된다.

 

non_main_arena 

  청크가 메인아레나가 아닌 다른 전용 아레나에서 할당되었는지를 표시

 

• 아레나(Arena) 란?
  glibc malloc은 멀티스레드 환경에서 락 경합을 줄이기 위해 “아레나”라는 독립된 메모리 풀 단위로 관리한다.
  • main arena는 brk()/sbrk() 기반 힙과 mmap() 영역을 모두 관리한다.
  • thread (non-main) arena는 mmap()으로 커널에서 한 번에 큰 블록(기본 64MiB)을 확보한 뒤 내부에서 잘라 쓰는 방식으로 운영된다.
• NON_MAIN_ARENA 플래그
  • size 헤더의 LSB 비트 2(값 4)가 NON_MAIN_ARENA 플래그다.
    • 1 → 스레드 전용 아레나에서 할당된 청크이다.
    • 0 → main arena에서 할당된 청크이다.
• free() 시 동작
  • free(p) 호출 시 size 하위 3비트를 검사해 아레나 소속을 판별한다.
    • NON_MAIN_ARENA=1인 경우 해당 스레드 아레나의 free list로 반환한다.
    • NON_MAIN_ARENA=0인 경우 main arena의 free list로 반환한다.
  • 이로 인해 각 아레나가 독립적으로 자유 청크를 관리하여, 멀티스레드 환경에서 락 경합 없이 병렬 해제가 가능하다.

 

is_mmaped

 해당 청크가 mmap()으로 할당된 큰 블록인지 표시한다.

  즉 1이면 mmap영역에서 왔으므로 free시 내부 free list로 가는게 아닌 munmap()로 바로 반환된다.

 

mmap 영역이란?
운영체제의 가상 메모리 공간 중, 파일이나 장치가 아닌 “익명(anonymous)” 메모리를 페이지 단위로 매핑(mapping)해 주는 구역을 말함.

• 일반적인 malloc()/free()가 이용하는 힙(heap)은 프로세스의 브레이크(brk) 포인터 (=> 현재 힙의 끝 이자 다음에 할당될 힙 공간의 시작점)를 위아래로 움직여 크기를 조절하는 반면,
• mmap()은 원하는 주소에 원하는 크기(보통 페이지(4KiB) 단위)로 직접 가상 메모리를 할당해 준다.

 

• munmap()이란?
  mmap()으로 매핑한 메모리 영역을 운영체제에 “언매핑(unmapping)”하여 되돌려 주는 시스템 호출, 호출하면, p부터 length 바이트만큼 매핑된 페이지가 해제되어 다시 OS 관리로 돌아간다.
   

void *p = mmap(NULL, length, PROT_READ|PROT_WRITE,
               MAP_ANONYMOUS|MAP_PRIVATE, -1, 0);
// … 메모리 사용 …
munmap(p, length);

• mmap() 할당과 malloc() 할당의 차이
  1. 할당 방식
     • malloc()
       • 내부적으로 brk()/sbrk()를 호출해 힙 영역을 늘리거나 줄이며, 메타데이터와 자유청크(free chunks)를 한 공간에서 관리
       • 작은 객체 여러 개를 효율적으로 처리하도록 설계됨
     • mmap()
       • 운영체제에 바로 시스템 콜을 보내 페이지 단위로 메모리를 새롭게 매핑(할당)
       • 크기가 크거나(기본 임계값 넘는 경우) 특별 옵션이 필요할 때 사용
  2. 해제 방식
     • free() → 내부 free list에 반환 → 이후 재사용
     • munmap() → 운영체제에 바로 반환 → 프로세스 주소 공간에서 사라짐
  3. 단위 및 오버헤드
     • malloc()은 바이트 단위(실제로는 8바이트 정렬) 관리, 메타데이터 오버헤드 적음
     • mmap()은 페이지 단위(4KiB 이상) 관리, 시스템 콜 오버헤드가 크고 메모리 낭비(page rounding)가 발생할 수 있음
  4. 단편화(fragmentation)
     • 힙 내부 단편화(internal fragmentation) vs 외부 단편화(external fragmentation)
     • 매우 큰 할당/해제가 잦으면 힙 단편화가 심해질 수 있어, 대신 mmap()을 써서 큰 청크를 별도 관리

 

prev inuse bit

 

이렇게 이전 청크가 할당되면 001 아니면 000이다.

 

chunk의 종류

크게 3가지가 있다.

1. Allocated chunk

2. Freed chunk

3. Top chunk

 

Allocated chunk

malloc()을 호출했을 때 heap영역에 생기는 chunk

Freed chunk

해제된 청크

free()를 했을 때 실제로 반환되는 것이 아닌 힙에 남아있으며,  allocated chunk구조에서 free chunk로 변경됨(data가 있던 부분에 fd, bk가 생김)

fd : 뒤에 있는 청크

bk : 앞에 있는 포인터

 

Top chunk

힙에 가장 마지막에 위치

새롭게 할당되면 top chunk에서 분리해서 반환하고, 인접한 청크가 free되면 병합한다.

새로운 malloc이 요청되고 재사용가능한 chunk가 없으면 topchunk에서 분리해서 반환한다.

 

 

 

 

dlmalloc의 알고리즘

• chunk의 크기 정보가 chunk의 앞 뒤에 저장 : boundary tag
• 재사용가능한 chunk를 크기단위로 관리 : binning

boundary tag

chunk가 할당될 때 크기정보가 해당 chunk의 size에 저장

이전 청크가 해제 free() 될 때 이전 청크의 크기 정보가 prev_size에 저장

allocated chunk와 freed chunk가 있을 때 인접한 앞/뒤 청크의 주소 계산이 가능하다. 

이렇게 prev_size가 초기화 되어있다면 해당 청크의 기준에서 preb_size를 빼면 이전 청크의 주소가 나오게 된다.

그리고 뒤의 청크주소도 계산이 가능하다 해당 청크의 기준에서 size를 더하면 다음 청크가 나오게 된다.

이는 prev_size를 조작하면 이전 chunk를 조작할 수 있다.

그리고 size도 조작하면 다음 chunk의 위치를 바꿀 수 다.

 

binning

 

fast bin

small bin

large bin

unsorted bin

 

fast bin

size가 다른 10개의 청크를 각각 single linked list로 관리(FILO) -> 먼저들어오면 가장 마지막에 나감 

해제가 되어도 다음 chunk의 prev_inuse 값이 변경되지 않음 -> 인접한 청크와 병합 X

 

small bin

size가 다른 63개의 청크를 double ilinked list로 관리(FIFO) -> 먼저들어오면 먼저 나감

size가 512byte 이하

해제되면 뒤 청크의 prev_inuse 가 해제되면 인접한 청크와 병함

 

large bin

특정 범위의 size가 다른 63개의 청크를 double linked list(FIFO)로 관리됨 -> 먼저들어오면 먼저 나감

크기가 512byte이상 되는 청크, 범위 내에서 size가 큰 청크가 제일 앞이다.

해제되면 뒤 청크의 prev_inuse 가 해제되고 인접한 freed chunk와 통합된다. 

 

unsorted bin

unsorted bin에 들어가는 경우

 free 했을 때 bin으로 가기 전 (fastbin 제외)

 fastbin들이 병합(malloc_consolidate)되어 합쳐지면

 bestfit으로 할당된 chunk의 남은 부분 remainder

 인접한 청크도 이미 free되어있어 병합된 free 청크

unsorted bin에 나오는 경우

 사용자가 malloc을 호출하여 요청한 size와 동일한 청크가 있다

 

즉 사용자가 요청하고 남은 부분이 Unsorted bin으로 들어간다.

 

 

병합

해제하려는 청크의 앞, 뒤 청크가 이미 해제되어 있을 때

1. 해제하려는 청크의 앞이 이미 해제되어 있을 때

A는 이미 해제되어 있고 B는 할당되어 있다. 이 때 B를 해제하면 이 때 prev_inuse 가 설정되어 있지 않기 때문에 이전 청크가 free되었다 판단한다. 이러면 prev_size가 초기화 되어있으므로, 해당 청크의 주소에서 prev_size를 빼면 이전 청크의 주소를 알 수 있고 이를 병합한다.

 

2. 해제하려는 청크의 뒤가 이미 해제되어 있을 때

B가 해제되어있고 A는 할당되어 있다. 이러면 size를 더해서 이전청크로 가고, 이전 청크 즉 B가 해제되어있는지 알기 위해 C까지 간다 즉 size를 한번 더 더한다.

이러면 prec_innuse를 확인하여 B가 free되어있는지 확인하고 A와 B를 병합한다.

 

이 때 병합되는 부분에 freed chunk의 포인터 fd와 bk를 정리해줘야 한다.

이를 unlink라 한다.

 

 

unlink

bin리스트에 등록된 청크를 제거하기 위해 포인터 fd, bk를 정리하는 작업

즉 노드 (bin에 속한 각 청크) 3개가 있고, 모든 fd, bk가 연결되어 있을 때

그 중 2번째 노드가 다른 청크랑 병합될 때 fd,와 bk를 다시 계산하는 것이다.