그 동안 공부한 내용을 간략하게 설명을 아래와 같이 하려 한다.
어떤 프로세스를 실행을 하면 멀티 스레드 환경덕분에 프로세스에서 실행해야 할 여러 task를 각각의 스레드가 처리를 한다. 처리를 할 때는 자원이 필요한데 프로세스가 운영체제로 부터 할당 받아온 자원을 스레드들이 공유해서 사용한다. 스택은 제외. heap을 공유를 해서 사용할 때 여러 스레드가 사용하게 되면 race condition이 발생 할 수도 있고 dead lock 환경이 발생 할 수 있어서 arena라는 스레드 별 heap 영역을 만들어 줬다. 이 아레나는 공유가 가능하지만 한 스레드가 사용할 때는 lock을 걸어서 자신만의 힙 영역처럼 사용이 가능하다. 이 아레나에는 chunk, bin이 있고 스레드별로 개인 tcache가 존재한다. 이 tcache는 일정 크기 이하의 chunk를 free했을 때 bin에 않넣고 tcache에 저장을 하는데 이번 시간에 tcache에 대해서 더 자세히 공부하려고 한다.
tcache
tcache는 bin보다 더 빠르게 free한 chunk를 할당해주기 위해서 glibc 2.26 (ubuntu 17.10) 이후에 도입 된 기술이다. 그래서 ptmalloc2에서는 chunk를 할당 할 때 tcache를 먼저 보고 unsorted bin fast bin 순으로 보면서 크기에 맞는 chunk를 찾아서 할당해 준다.
우선 먼저 tcache의 구조에 대해서 알아보기 위해 tcache structure에 대해서 알아보려고 한다.
tcache_entry
/* We overlay this structure on the user-data portion of a chunk when
the chunk is stored in the per-thread cache. */
typedef struct tcache_entry
{
struct tcache_entry *next;
} tcache_entry;next 포인터는 같은 크기의 free chunk를 가리킨다.
다음 tcache_pthread_struct
/* There is one of these for each thread, which contains the
per-thread cache (hence "tcache_perthread_struct"). Keeping
overall size low is mildly important. Note that COUNTS and ENTRIES
are redundant (we could have just counted the linked list each
time), this is for performance reasons. */
typedef struct tcache_perthread_struct
{
char counts[TCACHE_MAX_BINS];
tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;
# define TCACHE_MAX_BINS 64
static __thread tcache_perthread_struct *tcache = NULL;위 코드에서 tcache에 저장이 가능한 최대 수가 저장이 되어 있으며 count는 chunk가 tcache에 있는지 그 수를 저장한다. 그리고 entries는 free된 청크를 저장하는 곳으로 파악하면 된다.
이 사진이 이해하는데 도움을 많이 줄 것이다.
tcache에 저장된 free chunk들은 병합하지 않고 원래 크기를 갖으며 저장이 된다. 그리고 추가적으로 count에는 한 index에 가지고 있는 free chunk의 수 이고 최대가 7개 이다.
시간이 지난 후 tcache entry가 아래와 같이 바뀌었다.
typedef struct tcache_entry {
struct tcache_entry *next;
+ /* This field exists to detect double frees. */
+ struct tcache_perthread_struct *key;
} tcache_entry;코드를 보면 key 포인터가 추가 된 것을 볼수가 있다. 이 키는 tcache에 들어온 free chunk가 tcache로 저장이 되어있다는 것을 포인터로 알 수 있게 해준다.그러니까 일반적으로 할당된 chunk에는 key 값이 NULL이지만 free로 tcache에 들어가면 key 값이 tcache 값으로 바뀐다. 이를 통해서 같은 사이즈에 chunk를 free시킬 때 double free를 방지하는 루틴을 넣어둔 것이다. key 필드에 값을 넣어두는 것은 tcache_put 함수를 통해서 이루워진다.
tcache_put
tcache_put(mchunkptr chunk, size_t tc_idx) {
tcache_entry *e = (tcache_entry *)chunk2mem(chunk);
assert(tc_idx < TCACHE_MAX_BINS);
+ /* Mark this chunk as "in the tcache" so the test in _int_free will detect a
double free. */
+ e->key = tcache;
e->next = tcache->entries[tc_idx];
tcache->entries[tc_idx] = e;
++(tcache->counts[tc_idx]);
}tcache_put 함수는 해제되는 청크의 key에 tcache라는 값을 대입하도록 변경되었고 여기서 tcache는 tcache_perthread라는 구조체 변수를 가리킨다.
조금전에 malloc을 실행하면 free된 list에서 크기에 맞는 chunk를 가져와서 할당시킨다고 말했다. 그리고 우선적으로 tcache를 먼저 찾아본다고 했다. 아래 코드를 보면 더 이해가 쉬울 것이다.
malloc
void *
__libc_malloc (size_t bytes)
{
......
......
#if USE_TCACHE
/* int_free also calls request2size, be careful to not pad twice. */
size_t tbytes;
/ / Calculate the actual size of the chunk according to the parameters passed in malloc, and calculate the subscript corresponding to tcache
checked_request2size (bytes, tbytes);
size_t tc_idx = csize2tidx (tbytes);
/ / Initialize tcache
MAYBE_INIT_TCACHE ();
DIAG_PUSH_NEEDS_COMMENT;
If (tc_idx < mp_.tcache_bins // The idx obtained from size is within the legal range
/*&& tc_idx < TCACHE_MAX_BINS*/ /* to appease gcc */
&& tcache
&& tcache->entries[tc_idx] != NULL) // tcache->entries[tc_idx] 有 chunk
{
return tcache_get (tc_idx);
}
DIAG_POP_NEEDS_COMMENT;
#endif
......
......
}malloc이 호출되면 MAYBE_INIT_TCACHE()를 실행하게 되는데 함수는 아래와 같다.
__tcache_init()
tcache_init(void)
{
mstate ar_ptr;
void *victim = 0;
const size_t bytes = sizeof (tcache_perthread_struct);
if (tcache_shutting_down)
return;
Arena_get (ar_ptr, bytes); // find available arena
Victim = _int_malloc (ar_ptr, bytes); // Request a chunk of sizeof(tcache_prethread_struct) size if (!victim && ar_ptr != NULL)
{
ar_ptr = arena_get_retry (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
}
if (ar_ptr != NULL)
__libc_lock_unlock (ar_ptr->mutex);
/* In a low memory situation, we may not be able to allocate memory
- in which case, we just keep trying later. However, we
typically do this very early, so either there is sufficient
memory, or there isn't enough memory to do non-trivial
allocations anyway. */
If (victim) // initialize tcache
{
tcache = (tcache_perthread_struct *) victim;
memset (tcache, 0, sizeof (tcache_perthread_struct));
}
}tcache가 비어있을 때 MAYBE_INIT_TCACHE()가 tcache_init()를 호출 한다. 그리고 victim 값이 1이 된다면 성공적으로 tcache_perthread_struct를 생성하는 것을 볼 수가 있다. 이렇게 생성을 하고 entry에 이제 free chunk를 저장하는 것이다.
아까 다시 chunk를 할당해주면 key 값을 NULL로 변환시켜준다고 했는데 이 역할을 tcache_get 함수가 수행한다. 코드는 아래와 같다.
tcache_get()
tcache_get (size_t tc_idx)
assert (tcache->entries[tc_idx] > 0);
tcache->entries[tc_idx] = e->next;
--(tcache->counts[tc_idx]);
+ e->key = NULL;
return (void *) e;
}그리고 double free 루틴을 어떻게 체크하는지 아래 함수를 보면 이해가 쉬울 것이다.
__int_free()
_int_free (mstate av, mchunkptr p, int have_lock)
#if USE_TCACHE
{
size_t tc_idx = csize2tidx (size);
-
- if (tcache
- && tc_idx < mp_.tcache_bins
- && tcache->counts[tc_idx] < mp_.tcache_count)
+ if (tcache != NULL && tc_idx < mp_.tcache_bins)
{
- tcache_put (p, tc_idx);
- return;
+ /* Check to see if it's already in the tcache. */
+ tcache_entry *e = (tcache_entry *) chunk2mem (p);
+
+ /* This test succeeds on double free. However, we don't 100%
+ trust it (it also matches random payload data at a 1 in
+ 2^<size_t> chance), so verify it's not an unlikely
+ coincidence before aborting. */
+ if (__glibc_unlikely (e->key == tcache))
+ {
+ tcache_entry *tmp;
+ LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
+ for (tmp = tcache->entries[tc_idx];
+ tmp;
+ tmp = tmp->next)
+ if (tmp == e)
+ malloc_printerr ("free(): double free detected in tcache 2");
+ /* If we get here, it was a coincidence. We've wasted a
+ few cycles, but don't abort. */
+ }
+
+ if (tcache->counts[tc_idx] < mp_.tcache_count)
+ {
+ tcache_put (p, tc_idx);
+ return;
+ }
}
}
#endifif문을 통해서 key 값이 tcache면 double free로 인지하도록 설정을 하게 되어있다. 이것을 abort라고 하고 중단하게 한다.
그렇다면 어떻게 우회해서 double free를 할 것인가라는 생각을 할 것이다.
답은 쉽다. key 값에 tcache가 저장되지 않게 하면 된다. 그렇게 된다면 같은 사이즈의 chunk를 free 했을 때에도 이 chunk가 tcache가 아니라고 생각하고 중복으로 tcache에 들어가게 됨으로써 값을 변조시킬 수 있게 되는 것이다. 더 자세한 double free 기법은 다음 시간에 소개하려고 한다.
