[TOOR] 23. Heap chunk 구조

Heap

일단 heap 청크 구조를 알려면 힙이 무엇인지 알아야 할 것 같다.
heap 은

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

동적 메모리 할당자는

• tcmalloc (google)
• ptmalloc2 (glibc)
• libumen (solaris)
• jemalloc (FreeBSD and Firefox)
• dlmalloc (General purpose allocator)

등이 있다.

우리가 봐야할 것은 ptmalloc2 와 dlmalloc 이다.

dlmalloc

• 리눅스에서 사용되는 힙 관리에 사용되는 memory allocator
• dlmalloc 이 사용되다가 쓰레드 기능이 추가된 ptmalloc이 현재 사용된다.

그러므로 현재 우분투에서 사용되는 Memory Alocator 의 기본 알고리즘은 dlmalloc 과 동일하다.

Heap 은 어디에 생기는가

힙을 생성하려면 C언어 코드 상에서
char * p = malloc(size)

• 원하는 size 만큼 malloc 을 호출하여 동적 메모리 할당
  free(p)
• 사용한 메모리를 free 하여 반환

으로 할당과 해제를 해줄 수 있다.

malloc 호출전의 vmmap 이다.

malloc을 호출한 후에는 heap 영역이 생겼음을 볼 수 있다.

특정 크기 (0x21000) 의 메모리 영역을 미리 할당한 뒤 이 영역을 사용하는 방식이다.
이 메모리 영역을 top chunk 라 한다.

Chunk

heap chunk 의 기본 구조는 다음과 같다.

• mem : malloc으로 할당받은 부분
• chunk : header(사이즈 정보) 와 mem 을 포함하는 영역
  P = malloc(40); → 0x2010의 주소를 return 받았다면
  strcpy(p, “AAAA”);
  free(p)
• size : chunk의 크기를 나타냄
  • 32bit 는 8바이트, 64bit는 16바이트 단위로 정렬
• prev_size : 인접한 앞쪽 chunk의 크기를 나타냄.
  • 두개의 청크가 나란히 할당 되어있는 경우에는 prev_size가 0이지만
  • 앞쪽 chunk 가 free 될 때 prev_size 부분이 초기화 됨.

chunk size

청크의 size 필드에는 chunk의 크기 뿐만 아니라 3가지 속성도 나타내고 있다.
32 bit 는 8바이트, 64bit는 16바이트 단위로 정렬되기 때문에 하위 3니블이 사용되지 않는다.
따라서 이를 chunk 의 특성을 나타내는 데 사용한다.

0	0	0
non_main_arena ( main arena)	is_mmaped	prev_inuse bit
thread_arena에 속하면 1	mmap으로 할당 되었으면 1	인접한 이전 chunk가 할당되면 1
thread arena에 속하지 않으면 0	mmap으로 할당되지 않았으면 0	인접한 이전 chunk가 해제되면 0

prev inuse bit

 

이런식으로 인접한 이전 청크가 할당, 해제 되어있는지 여부를 판단할 때 사용된다.

Chunk 의 종류

Allocated chunk

malloc, realloc, calloc 등을 사용할 때 힙 영역에 할당되는 청크이다.

allocated chunk 의 구조는 위와 같다.

size 가 21인 이유는 header(0x10) + data(0x10) = 0x20 이고 이전 청크가 사용중이므로 세팅되어 0x21 인 것이다.

Freed chunk

free 를 이용해서 해제한 청크이다.
청크의 헤더는 동일하지만 데이터 부분의 앞쪽에 fd와 bk가 생성된다. (large bin 일때는 fd_nextsize, bk_nextsize 도 생성된다.)
free 된 청크들은 메모리 할당자가 효율적으로 관리하기 위해서 비슷한 크기끼리 관리하는데 이를 binning 이라 하고 linked list 로 관리된다.
free 후의 heap chunks 는 다음과 같다.

• free(ptr)을 호출했을 때, 실제로 반환되는 것이 아니라 힙 영역에 남아있으며, allocated chunk 구조에서 Free chunk 구조로 변경됨 (data가 있던 부분에 fd, bk가 생김) (fd = forward, bk = backward)
• 크기가 큰 경우 fd next_size, bk next_size도 생김

Top Chunk (a.k.a wildness chunk)

힙영역의 가장 마지막에 위치하며 새롭게 할당 (malloc) 되면 top chunk 에서 분리해서 반환하고 top chunk 에서 인접한 chunk 가 free 되면 병합한다.
top chunk 는 일반적으로 0x21000 정도가 할당된다.

만약 Top Chunk 의 크기보다 큰 사이즈를 요청할 경우

• Main Arena : sbrk() 호출하여 메모리 확장하여 Top Chunk의 크기 늘림
• Sub Arena: mmap() 호출하여 메모리 할당

dlmalloc algorithm

dlmalloc 이 메모리를 관리하는 방법이지만 tcmalloc2 과 매우 흡사하니 상관 없다.

dlmalloc 은 chunk 의 크기 정보가 chunk 앞뒤에 저장된다. 이를 boundary tag 라고 한다.
또한 재사용 가능한 chunk 를 크기 단위로 관리하는데 이를 binning 이라 한다.

boundary tag

size

모두 다 할당 되어 있으므로 해당 청크의 size 부분에 각 청크의 size 가 들어가 있다.

prev_size

prev_size 는 chunk 가 해제될 때 바로 뒤에 있는 chunk 의 prev_size 에 저장된다.
→ allocated chunk 와 freed chunk 가 있을 때 인접한 앞/뒤 chunk의 주소 계산 가능

임의의 chunk(B) 기준으로 인접한 앞 chunk(A) 의 주소 계산 가능
(해제 되어 있는 경우 → prev_size 초기화)
chunk(B) 의 prev_size 를 chunk_addr(B) 와 빼주면 이전 청크의 주소를 계산할 수 있다.

임의의 chunk(B) 기준으로 인접한 뒤 chunk© 의 주소 계산 가능
chunk(B) 의 size 를 chunk_addr(B) 에 더해주면 다음 청크의 주소를 계산할 수 있다.

이렇게도 할 수 있다.

이걸 해커의 관점에서 보면

• prev_size 를 조작하면, 이전 chunk 의 위치를 조작 가능하다.
• size 를 조작하면 다음 chunk 의 위치를 조작 가능하다 .
• prev_inuse bit 를 조작하면 이전 chunk의 할당/해제 여부를 조작 가능하다.

binninb

bin의 종류

bin에 대한 정보는 malloc_state 구조체 (Arena 의 Header) 에서 확인할 수 있다.

• fastbinY[NFASTBINS] : fast bin 을 관리하는 배열 (10개)
• bins[NBINS * 2 - 2] : unsorted bin, small bin, large bin 을 관리하는 배열
  • bin[0] : N/A (사용되지 않음), 특수한 목적에 사용
  • bin[1] : unsorted bin(1개)
  • bin[2] ~ bin[63] : small bin (62개)
  • bin[64] ~ bin[126] : large bin (63개)

이 bin들은 arena 에서 관리하는데 보통 main arena 가 관리한다.

	Unsorted bin	Fast bin	Small bin	Large bin
chunk 크기	variable	< 64 (32bit) < 128 (64bit)	< 512	≥ 512
linked list 종류	double	single	double	double
fit 알고리즘	exact fit	exact fit	exact/best fit	best fit
개수	1	10 → 7	62	63
입출력 방식	FIFO	LIFO	FIFO	FIFO

Fast bin

• size가 다른 10개의 chunk 를 각각 single linked list 로 관리한다.
• chunk의 size가 64바이트 이하(32bit 기준), 128 바이트 이하(64 bit 기준)
• 해제가 되어도 다음 chunk 의 prev_inuse 값이 변경되지 않음
  → 인접한 chunk 와 병합되지 않음

Small bin

chunk 크기가 MIN_LARGE_SIZE 보다 작은 chunk 들을 포함하는 62개의 small bin 이 존재하며 한 가지 크기의 chunk 만 저장되기 때문에 자동으로 정렬이 되어 삽입 및 제거하는 것이 빠르다.

• FIFO (First in First Out) 를 사용하여 double-linked list 로 관리
  • 먼제 해제된 청크가 먼저 재할당.
• 서로 다른 크기의 62개의 small bin 존재
• chunk 크기가 MIN_LARGE_SIZE 보다 작은 chunk 들을 관리
  • 32bit system : MIN_LARGE_SIZE = 512 byte
  • 64bit system : MIN_LARGE_SIZE= 1024 byte
    • chunk 크기의 범위는 0x20 ~ 0x400 까지이며 0x20 부터 0x80 까지 fast bin 과 겁침 (0x400 보다 미만임)
• small bin 에 포함되는 chunk 들은 인접하게 배치되지 않음
  • 서로 인접한 경우 PREV_INUSE bit 가 clear 되므로 free 할 때 인접한 free chunk와 병합

large bin

small bin 과 같은 방식으로 동작하지만 small bin과 fast bin 처럼 정해진 크기 단위로 관리하는 것이 아니라 특정 범위 단위에 따라 관리하기 때문에 다양한 크기를 저장하게 된다.

이로 인해 삽입에 대한 정렬이 수동으로 이루어지기 대문에 메모리 할당 또는 반환 속도가 가장 느리다. (하지만, 대부분 프로그램에서 자주 사용하지 않는다.)

• FIFO (First in First Out)를 사용하며 double-linked list로 관리한다.
• 63개의 bin을 사용하며 특정 범위 단위로 관리한다.
  • 하나의 bin에 다양한 크기의 chunk 들을 보관
  • bin 내에서 크기 별로 정렬되어 할당의 효율성 향상
• 범위 내 가장 큰 size의 chunk가 제일 앞에 오도록 정렬
• chunk의 크기가 MIN_LARGE_SIZE와 같거나 큰 chunk 들을 관리
  • 32bit system : 512 byte 보다 같거나 큰 청크
  • 64bit system : 1024 byte 보다 같거나 큰 청크
• large bin에 포함되는 chunk 들은 서로 인접한 경우 PREV_INPUSE bit 가 clear 되어 병합됨.

bin의 개수 및 범위

• Chunk의 크기는 0x400(512) bytes 이상부터 시작하며 범위는 다음과 같다.
  • largebin[0] ~ largebin[31] (32개) : 0x40 (64) bytes 씩 증가
  • largebin[32] ~ largebin[47] (16개) : 0x200 (512) bytes 씩 증가
  • largebin[48] ~ largebin[55] (8개) : 0x1000 (4,096) bytes 씩 증가
  • largebin[56] ~ largebin[59]

• fd_nextsize, bk_nextsize
• 하나의 링크드 리스트 내에 다른 크기를 가리키는 포인터가 존재함. (double linked list)

Unsorted bin

• unsorted bin 에 들어가는 경우
  • free 했을 때 각 bin (small bin, large bin) 으로 들어가기 전 (fast bin 은 제외)
    • free 했을 때 해당 청크가 small, large bin 의 크기라면 unsorted bin에 먼저 들어가게 된다.
  • fastbin 들이 병합 (malloc_consolidate) 되어 합쳐지면
    • 인접한 청크가 해제 되었을 때 fast bin이 특정 상황에 합쳐지면
      • 특정상황 ( e.g. 큰 청크 크기의 요청을 받았을 때 붙어져 있는 Fast bin에 포함된 청크들을 한꺼번에 합쳐 버린다. fast bin은 여러개의 청크를 합쳐버림 → malloc_consolidate)
  • bestfit 으로 할당된 chunk의 남은 부분인 remainder
    • 0x140 바이트의 청크가 free 되어 있고 사용자가 100바이트를 요청하면 해당 청크의 크기를 잘라서 남은 부분인 40바이트는 Unsorted bin으로 들어가고 100은 반환한다.
  • 인접한 chunk도 이미 free 되어 있어, 병합 (consolidate) 된 free chunk
• unsorted bin 에서 나오는 경우
  • 사용자가 malloc 을 호출하여 요청한 size 와 동일한 chunk 가 있으면 반환한다.

Arena

dlmalloc 코드를 기반으로 하여 멀티 쓰레딩 기능을 지원한다.

dlmalloc 에서는 동일한 시간에 2개의 스레드가 메모리 할당 요청을 할 경우 freelist data structures 는 사용가능한 스레드에 둘러싸인 상태로 공유되어 오로지 하나의 스래드만 critical section (임계영역) 에 들어갈 수 있으므로 멀티 스레드 환경에 적합하지 않다. (많은 스레드를 사용하는 응용 프로그램에서 성능 문제 발생)

ptmalloc2 에서는 동일한 시간에 2개의 스레드가 메모리 할당 요청을 할 경우 메모리는 각각의 스레드에게 분배된 힙 영역을 일정하게 유지시키고 힙을 유지하기 위한 freelist data structures 또한 분배되어 있기 때문에 즉시 할당 가능하다 .

Arena 란?

각각의 스레드가 서로 간섭하지 않고 서로 다른 메모리 영역에서 액세스 할 수 있도록 도와주는 힙 영역이다.

단일 스레드 프로세스인 경우 Arena는 한개를 가지게 되고 멀티 스레드 프로세스인 경우에는 여러개의 Arena를 가지며 서로 다른 Arena안에 존재하는 각각의 스레드는 정지하지 않고 힙 작업을 수행할 수 있다.

하지만 모든 스레드에 Arena를 할당해주면 자원 고갈이 심해질 것이므로 각각의 시스템과 코어의 개수에 따라 Arena의 개수가 정해져 있다.

32bit 시스템인 경우 long type 크기가 4byte이기 때문에 코어 * 4 만큼의 Arena를 가진다.

64bit 시스템인 경우 long type 크기가 8byte 이기 때문에 코어 * 8 만큼의 Arena를 가짐

Arena를 모두 사용하고 있어 더 이상 증가시킬 수 없다면 여러 스레드가 하나의 Arena에서 공유하여 힙 작업을 수행한다.

이 말은, 각각의 Arena 안에서 여러개의 스레드가 존재할 수 있으며 뮤텍스를 사용하여 액세스를 제어한다.

뮤텍스?

뮤텍스는 공유자원에 접근하기 위한 방식인데 간단하게 화장실이 하나밖에 없는 상황에 비유할 수 있다.

화장실이 1개이며 화장실 열쇠를 가진 사람1이 사용하고 있다.

공유자원을 오브젝트를 가진 프로세스 혹은 쓰레드가 사용하고 있다.

사람 1이 화장실을 나와 화장실 열쇠를 대기줄 맨 앞에 서있는 사람에게 건내준다.

다음 프로세스 혹은 쓰레드가 공유자원에 접근한다.

정리하면 새로운 스레드가 생성되면 사용되지 않는 Arena를 찾아 할당하며, 더이상 Arena를 할당할 수 없다면 여러 스레드가 하나의 Arena에서 작업을 수행하게 된다 .

Arena 란? 요약

Arena는 멀티 스레드 환경을 지원하기 위해 도입된 개념이다 .

멀티 스레드 프로세스인 경우 하나 이상의 Arena를 가진다.

서로 다른 Arena는 서로 간섭을 받지않고 작업을 수행할 수 있다.

자원 고갈을 방지하기 위해 시스템 환경과 코어 개수에 따라 Arena의 개수가 제한된다.

하나의 Arena에서 여러 스레드가 존재할 수 있으며 뮤텍스를 이용해 충돌을 방지한다.

Arena의 종류

Arena의 종류는 크게 Main Arena와 Main Arena를 제외한 Arena로 나뉜다.

Main Arena

메인 쓰레드로서 생성되었기 때문에 Main Arena라고 부른다.

단일 스레드용 프로그램을 위해 존재하며 malloc() 과 같은 힙 작업을 요구하는 코드를 실행하지 않아도 기본적으로 132KB 크기의 Initial Heap을 가진다.

Main Arena가 감당할 수 있을 만큼의 동적 할당 요구가 들어오면 sbrk()를 통해 heap segment를 확장한다.

sbrk(), brk()?

brk() 는 프로그램 break location을 확장시킴으로서 메모리를 확보한다.

brk()의 성공시 return 값은 0, 실패시 return 값은 -1 이 된다.

sbkr() 는 내부적으로 brk system call을 사용한다.

따라서 brk()와 마찬가지로 break location을 확장시킴으로 메모리를 확보한다.

brk() 와의 차이점은 brk() 의 return 값은 성공 시 0, 실패시 -1 이었지만, sbkr() 의 return 값은 성공 시 할당받은 메모리 영역의 끝 주소 값, 실패 시 -1 을 리턴한다.

malloc() 사용 시 system library에서 sbrk() 를 이용해 메모리를 넉넉히 받아온 다음 후에 malloc()이 들어올 때 마다 미리 받아온 공간에서 잘라서 할당 (이게 Top Chunk?)

너무 큰 사이즈의 동적 할당 요구가 들어오면 mmap() 을 통해 새로운 힙 메모리를 할당해준다.

mmap()

새로운 메모리를 할당하고 호출한 프로세스에서 해당 메모리를 사용한다.

Main Arena는 하나의 힙 만을 가질 수 있으며 heap_info 구조체를 가질 수 없다.

이 때, 하나의 힙은 여러 개의 chunk로 나누어지며 각 chunk는 각각의 header를 갖는다.

Main Arena를 제외한 Arena

새로운 스레드가 생성되어 힙 작업을 수행하고자 할 때 다른 스레드를 기다리는 것을 줄이기 위해 새로운 Arena를 생성하게 된다.

sbrk() 를 사용하는 Main Arena 와는 다르게 mmap() 을 이용해 새로운 힙 메모리를 할당받으며 mprotect() 를 사용하여 확장한다 .

또한, Main Arena 를 제외한 Arena 들은 Main_Arena 와는 다르게 여러 개의 서브 힙과 heap_info 구조체를 가질 수 있다

Sub Arena

새로운 스레드가 생성되어 힙 작업을 수행하고자 할 때 다른 스레드를 기다리는 것을 줄이기 위해 새로운 Arena를 생성하게 되는데 이를 Sub Arena 라고 한다.

sbrk를 사용하는 Main Arena 와 달리 mmap()을 통해 새로운 힙 메모리에 할당받으며 mprotect() 를 사용하여 확장한다.

또한, Sub Arena 는 Main Arena 와 달리 여러 개의 서브 힙과 heap_info 구조체를 가질 수 있다.

+ brk(), sbrk(), mmap()

brk()

• 프로세스의 data segment에 할당 메모리량을 변경하기 위해 사용
• program break 위치를 이동시킴으로써 메모리를 획득하여 성공 시 0, 실패 시 -1 을 반환
• 참고로 break 는 BSS 영역 끝의 다음 위치에 존재함
• ex) brk(주소 값) : 요청한 주소 값까지 메모리 할당

sbrk()

• sbrk의 기능은 내부적으로 brk system call 을 사용
• brk와 동일하게 작업하며 성공 시 세그먼트 break 주소를 반환며 실패 시 -1을 반환
• ex) sbrk(메모리크기) : 이전 세그먼트부터 메모리 크기만큼 메모리 할당.

mmap()

• 새로운 메모리를 할당하고 호출한 프로세스에서 해당 메모리를 사용

Arena 구조

이 글은 옵시디언을 이용해서 작성되었습니다.