목차
힙 기초 1,2,3 page는 glibc 2.23 버전 기준으로 설명했었다. glibc 2.26 이후 tcache 라는 기능이 추가되었는데, 기존 malloc, free 관련한 로직에서 tcache라는것이 추가적으로 이용될 뿐 전체적인 동적할당 구조는 비슷하다.
(아래 내용은 glibc 2.26 기준으로 설명했습니다)
1. tcache란?
tcache는 glibc 2.26 버전 부터 생겨난 기술로써, 힙 관리의 성능향상을 목적으로 만들어진 기술이다. 이로써 기존 보다 힙 관리를 함에 있어 성능이 향상되었다는 장점은 있지만, 반대로 보안적인 체크가 많이 결여되었다. 따라서 이러한 보안 허점을 이용하여 exploit이 가능하다
tcache는 free list를 관리하는 bin들과 비슷한 개념으로 생각하면 되는데, 기존에 동적할당 관련 로직에서 추가적으로 tcache를 먼저 확인하여 캐시 역할로써 빠른 성능을 낼 수 있는 힙 관리 기법중 하나이다. 이제부터 tcache의 구조를 하나씩 알아보자
2. tcache_perthread_struct 구조체
위 사진은 tcache의 전체적인 구조이다. 우선 bin에서 free chunk들이 관리되는 것처럼 tcache에서 free chunk들이 관리된다.
( tcache_perthread_struct, tcache_entry는 glibc 2.26에서 새롭게 추가된 구조체이다.)
2.23에서 bin들이 main_arena에 존재했는데, tcache는 main_arena가 아닌 tcache_perthread_struct
에 존재한다. 이는 구조체 형태로 두개의 멤버 변수를 갖는다
•
count[tc_idx]
•
tcache_entry[tc_idx]
tcache_entry[tc_idx] 배열은 기존 bin들 역할과 동일하다고 생각하면 된다. 각 배열의 인덱스마다 동일한 사이즈 별로 free 청크들이 연결되는데, 위 사진처럼 단일 연결리스트로 연결된다. (LIFO)
count[tc_idx] 는 tcache_entry[tc_idx] 에 연결되어있는 청크의 개수가 삽입된다.
ex) 위 사진 설명
위 사진처럼 0x20사이즈(헤더포함)의 2개의 청크가 free된다면, tcache_entry[0] 에 리스트로 연결될 것이다. tcache는 LIFO 구조이기 때문에 fastbin과 동일하게 리스트에 삽입되고, count[0]은 2가 들어간다.
tcache_perthread_struct 구조체에서 두번째 멤버변수인 tcache_entry 또한 구조체 형태로 이루어져있다.
구조체의 멤버변수는 포인터변수 next밖에 없다. 해당 포인터는 tcache list를 관리한다고 보면 된다.
이제 tcache_perthread_strcut 구조체에 어떻게 데이터가 들어가있는지 직접 디버깅으로 확인해보자
위 그림과 비슷한 상황을 만들었다. 0x20 크기의 청크가 현재 tcache_entry[0] 에 2개의 청크가 리스트로 연결되어 있다.
2.23에서는 heapbase부터 차례대로 malloc된 주소가 들어가지만 2.26부터는 heapbase에 tcache_perthread_struct 구조체 내용이 제일 먼저 malloc된다.
•
char count[64] ⇒ 64byte
•
tcache_entry[64] ⇒ 8*64 = 512byte
따라서 tcache_pertherad_struct의 할당되는 청크의 크기는 64 + 512 + 16(헤더) = 592byte(0x250)이다. 현재 tcache_entry[0]에 2개의 청크가 리스트로 연결되어 있기 때문에 count[0]에 2가 들어가있는 것을 볼 수 있다.
또한 tcache_entry[0] = 0x5555557562a0에 연결된 청크를 보면 0x555555756260 청크가 연결되어 있는 것을 확인할 수 있다.
3. tcache 사용 과정
tcache와 관련된 주요 함수는 다음과 같다
•
tcache_init : tcache 초기화 관련 함수
•
tcache_put : tcache list에 삽입하는 함수
•
tcache_get : tache list에서 제거하는 함수
이미 힙 기초 1,2,3 에서 malloc의 동작과정은 설명했기 때문에 tcache 관련된 부분만 설명하겠다
1.
malloc이 호출되면 제일 먼저 __libc_malloc 이 호출된다. malloc_hook 이 존재하면 그거를 실행하고 아니면 다음로직으로 넘어간다
2.
tcache가 비여있으면 MAYBE_INIT_TCACHE 가 호출된다
2.1 해당 함수안에서 tcache_init 함수가 호출된다.
2.2 tcache_init 안에서 _int_malloc 을 호출하여 tcache_perthread_struct 를 청크를 할당받는다
3.
만약 현재 요청한 청크 사이즈에 맞는게 tcache 안에 존재하면, tcache_get 함수를 호출하여 재할당해준다
4.
만약 tcache에 재할당 해줄수 있는 마땅한 청크가 없다면, _int_malloc 을 호출한다
5.
기존 glibc 2.23 처럼 fastbin or unsorted bin or small bin을 확인하고 재할당 가능한 청크가 있다면, 할당해준다. 그다음 현재 tcache_entry[tc_idx]에 자리가 비여있다면, tcache 에 넣을 수 있을 만큼 빈들에 있는 청크를 넣는다
6.
그다음 청크를 재할당한 청크의 주소를 반환한다
free 함수 역시 tcache 위주로 설명하겠다
1.
처음에 _libc_free 함수가 호출되면서 free_hook을 검사한다. 있으면 호출되고 없으면 넘어간다
2.
tcache가 비여있으면 호출되서 tcache 초기화 과정을 거친다
3.
_int_free 함수가 호출된다
4.
tcache에 넣을수 있으면 tcache_put함수를 호출하여 넣는다. 나머지 로직은 2.23과 동일하다
4. tcache 상세 분석
위 malloc, free 흐름을 코드를 간단하게 분석해보자.
4.1 __libc_malloc
•
hook이 있으면 호출함. 2.23과 동일
•
MAYBE_INIT_TCACHE() 함수가 추가된 것을 볼 수 있음.
•
MAYBE_INIT_TCACHE가 호출되면, tcache가 NULL일시 tcache_init을 다시 호출함
•
47 라인 > tcache_perthread_struct 구조체 크기를 'bytes' 변수에 저장함
•
49 라인 > tcache_shutting_down 값이 참인경우 바로 return됨. 기본값은 0인데 , tcache_thread_freeres 함수가 호출된 경우에 참이됨
•
53 라인 > 에서 해당 사이즈 만큼 _int_malloc 을 호출해서 힙 영역을 할당받음
•
54 라인 > 만일 arena_get, _int_malloc 둘다 실패할 경우 다시 한번 시도함
•
69 라인 > 할당 받은 힙영역의 주소(victim)가 널이 아니면, victim을 tcache_perthread_struct 형태로 tcache라는 변수에 저장함. 그리고 해당 영역을 memset으로 초기화함
다시 __libc_malloc으로 돌아와서
•
90 라인 > 요청한 사이즈를 청크구조에 맞게 사이즈를 할당하여 tbytes변수에 저장.
•
91 라인 > tbytes 변수에 저장된 청크 크기를 이용하여 tcache 인덱스 저장 (tc_idx)
•
93 라인 > MAYBE_INIT_TCACHE() 함수가 호출완료 된 후
•
96 라인 > 현재 91라인에서 계산된 tc_idx가 최대 인덱스크기 63보다 작고,
•
98 라인 > tcache가 비여있지 않고
•
99 라인 > tc_idx 인덱스의 tcache_entry가 NULL이 아니면 tcache_get을 호출함.
즉 현재 요청한 사이즈가 tcache에 있는 청크로 재할당해줄 수있다는 소리이고, 이때 tcache에서 해당 청크를 가져오는 함수가 바로 tcache_get임
•
e에다가 현재 tc_dix 인덱스에 들어있는 값을 복사한다
•
tc_idx 가 64보다 크면 종료시킨다
•
올바른 주소값을 얻지 못하면 종료시킨다
•
tcache에서 재할당을 해주고 나머지 리스트를 왼쪽으로 댕겨야 하므로 e→next의 값을 tc_idx 엔트리 값에 복사한다
•
그리고 해당 tc_idx에 해당하는 counts 개수를 감소시킨다
•
e를 반환한다
4.2 _int_malloc
tcache에 재할당해줄 수 있는 청크가 없다면 _int_malloc이 호출된다
4.2.1 fastbin 관련로직
•
133 라인 > nb(요청사이즈+헤더) 사이즈가 fastbin 범위인지 검사
•
135 라인 > 맞다면, nb 사이즈에 해당하는 fastbin idx를 저장
•
136 라인 > arena에서 fastbin의 해당 idx 주소를 fb에 저장
⇒ #define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])
•
137 라인 > 현 fastbin의 가장 앞쪽 청크 주소를 pp에 저장
•
138 라인 > REMOVE_FB() 함수 호출
REMOVE_FB() 함수는 위 사진처럼 정의되어 있다.
(victim은 재할당할 청크의 주소를 담을 변수이다.)
◦
126 라인 > victim에 fastbin의 제일 앞쪽(왼쪽) 청크 주소가 저장됨
◦
127 라인 > victim이 NULL이면 fastbin에 list가 없다는 뜻임
즉 해당 size의 free된 청크가 없기때문에 break하여 small bin으로 넘어감
◦
130 라인 > catomic_... 함수의 반환값이 pp에 담기게 되므로 결국 while( pp ≠ victim ) 이라고 보면됨.
결국, 130라인은, unlink가 진행되는 부분이라고 생각하면 된다. 재할당해줄 맨 앞 청크를 뺴고, victim→fd를 fastbin의 제일 앞으로 떙기는 것이다!
다시 '1. fastbin 관련로직' 글 바로 아래 사진에 이어서
•
140 라인 > victim이 0이 아니면, 즉 재할당받을 청크 주소가 담겨져 있으면
•
142 라인 > 꺼내온 victim의 청크 사이즈가 실제 그 bin에 맞는 크기인지 검사한다. ** 익스시 fastbin에 등록한 fake chunk의 사이즈를 맞춰줘야하는 이유가 이때문이다
•
149 라인 > remalloc을 통해 할당된 chunk인지 확인한다
•
153 라인 > nb(헤더포함 요청 청크사이즈)를 인자로 csize2tidx를 호출한다.
⇒ 이 함수는 요청 청크 사이즈를 tcache에 맞는 index로 바꿔준다
•
154 라인 > 만약 tcache가 NULL이 아니고, tc_idx가 64보다 작으면 조건문 안으로 들어간다
•
156 라인 > tc_victim 변수를 선언함
•
159 라인 > tcache→counts[tc_idx] 값이 최대치를 벗어나지 않았고, pp = *fb 일때까지 반복문 안의 내용을 수행한다
◦
161 라인 > REMOVE_FB() 함수를 호출한다. 위에서 설명했기 때문에 따로 설명은 안하겠다. 간단히 말하면 해당 함수의 목적은 fastbin에 남아있는 청크들을 while문을 돌면서 unlink 하는 목적이다
◦
165 라인 > tc_victim이 NULL이 아니라면, tcache_put함수를 호출하여 fastbin에서 뺀 청크를 tache에 삽입한다
•
169 라인 > tcache를 사용하지 않는다면 glibc 2.23 처럼 동작한다.
•
197 라인 > tcache에 넣은 청크 주소를 e에 복사한다
•
198 라인 > tc_idx가 64보다 크다면 종료시킨다
•
199 ~ 201 라인 > LIFO 구조로 tcache에 삽입한다
4.2.2 small bin 관련 로직
small bin 관련로직도 기존 로직은 glibc 2.23과 비슷하다
•
204 라인 > fastbin 로직에서 #if USE_TCACHE 부분 로직과 거의 동일하다
•
219 라인 > 다음 청크의 inuse_bit 를 세팅해준다
•
220 라인 > 메인 아레나에서 생성된 청크가 아니라면, set_non_main_arena를 호출한다
•
223-223 라인 > fd, bk를 설정한다
•
225 라인 > small bin에서 재할당하고 남은 청크들을 tcache_put 함수를 호출하여 tcache에 넣어준다
4.2.3 unsorted bin 관련 로직
아래코드 맨 위에 else 부분은 small bin 관련 로직이 아닌 경우부터 시작되는 코드다
•
small bin 범위가 아닐때 idx에 largebin의 index를 구해서 넣는다
•
fastbin에 청크가 있으면 malloc_consolidate()를 호출해서 병합한다. 병합된 청크는 unsorted bin으로 들어간다
•
259 라인 > TCACHE를 사용한다면 아래 로직이 수행된다. 나머지는 위 쪽에서 설명한 부분과 동일하다.
•
264 라인 > return_cached를 0으로 초기화 한다. 해당 변수의 사용용도는 추후에 설명하겠다
•
9383라인 윗 부분은 기존 glibc 2.23에서의 동작과 거의 유사함. 위 TCACHE 관련 로직은 unsorted bin에서 처리되는 tcache 관련 부분이다.
•
위 코드는 victim이 small chunk가 아니거나, unsorted bin에 청크가 여러개 존재하고, last remainder chunk가 아닐경우 수행되는 로직이다.
•
9389 라인 > 현재 unsorted bin에서 검사중인 청크사이즈와 요청한 청크사이즈 + 헤더 사이즈가 동일한 경우 조건문 안으로 들어온다. 즉 현재 선택된 unsorted bin에 있는 청크가 재할당 가능하다는 소리이다
•
9397 라인 > 2개의 조건이 만족하면 if문안으로 들어간다
1.
위에 위에 사진에서 tcache_nb에 nb를 특정 조건에 맞으면 복사하였는데, 해당 조건에 만족하는 경우는 요청한 청크 크기가 tcache 범위안에 존재하는 의미이다.
2.
tc_idx에 해당하는 count 개수가 64를 넘지 않으면 만족함.
기존 2.23에서는 여기서 바로 해당 청크 mem 주소를 return 했지만, 2.26 부터는 일단 tcache에 먼져 저장한다. 즉 해당 조건문은 요청 청크가 tcache 안에서 관리되는 사이즈라는 소리이다
•
281 라인 > tcache_put 함수를 호출하여 unosrted bin에 있는 청크를 tacache에 넣는다
•
282 라인 > return_cached = 1로 세팅하고 continue로 로직을 반복한다
•
위 코드는 아까 size = nb를 만족하지 않는 청크 즉, unsorted bin에 있는 청크들로 재할당해줄수 있는 것이 없을때 자기의 빈으로 넣어주는 로직이다. 2.23과 거의 동일하다
•
9419 라인 > unsorted bin에서 가져온 chunk가 small bin range인 경우 수행된다
•
9425 라인 > unsorted bin에서 가져온 chunk가 large bin range인 경우 수행된다
위, 위 에 코드의 if - else 부분이 끝나고 진행되는 부분이다.
•
9475 라인 > bin들에 chunk가 남아있는지 한번에 확인할 수 있는 binmap에 추가된 정보를 업데이트함
•
9476 - 9479 라인 > bck와 fwd사이에 삽입한다
•
9485 라인 > 3개의 조건을 확인한다
1.
return_cached가 0이 아닌지 확인한다. 이부분은 아까 요청사이즈가 unsorted bin에서 만족하는게 있을때 1로 바꼇다
2.
tcache_unsorted_limit가 양수고
3.
tcache_unsorted_count > tcache_unsorted_limit 이면
위 3가지의 조건이 만족된다면 현재 요청 사이즈가 unsorted bin → tcache로 이동되었으므로 tcache_get함수로 해당 청크 주소를 얻어오고 반환한다
•
9494 라인 > unsorted bin을 scan하는 과정과 각자의 빈에 넣는 과정을 최대 10000번 반복한다. 여기까지의 과정을 통해 unsorted bin에 있던 모든 청크가 빠져나와 크기에 맞는 bin으로 재분배된다.(사이즈 맞는게 있으면 반환되고)
•
9500 라인 > 각각의 빈으로 들어가는 로직이 다 끝난 후, 해당 라인으로 들어온다면 다시 한번 return_cached 변수를 확인하여 tcache_get 함수를 호출한다
4.3 __libc_free
•
7 라인 > free_hook 이 있으면 실행 없으면 넘어감
•
19 라인 > mmap으로 할당된 청크면 그에 맞는 로직 수행
•
36 라인 > __libc_malloc 과 동일하게 MATBE_INIT_TCACHE 함수 호출. 여기서 tcache_init으로 초기안되있으면 초기화 시킴
•
38 라인 > _int_free 함수 호출
4.4 _int_free
tcache 관련 부분만 보겠다. 나머지는 glibc 2.23 설명했던것과 동일.
•
90 라인 > 현재 free 하려는 청크가 tcache 사이즈이라면 tcache_put 함수를 이용해서 넣는다.
