# Deep understanding of heap implementation
- ở bài viết này sẽ làm rõ thêm nội dung hiểu sâu về triển khai heap
- trọng tâm sẽ nằm ở **tcache Data Structure**
## malloc
(https://github.com/iromise/glibc/blob/master/malloc/malloc.c#L448)
```
/*
malloc(size_t n)
Returns a pointer to a newly allocated chunk of at least n bytes, or null
if no space is available. Additionally, on failure, errno is
set to ENOMEM on ANSI C systems.
If n is zero, malloc returns a minumum-sized chunk. (The minimum
size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit
systems.) On most systems, size_t is an unsigned type, so calls
with negative arguments are interpreted as requests for huge amounts
of space, which will often fail. The maximum supported value of n
differs across systems, but is in all cases less than the maximum
representable value of a size_t.
*/
```
- source:
```c
void *__libc_malloc(size_t bytes) {
mstate ar_ptr;
void * victim;
void *(*hook)(size_t, const void *) = atomic_forced_read(__malloc_hook);
if (__builtin_expect(hook != NULL, 0))
return (*hook)(bytes, RETURN_ADDRESS(0));
arena_get(ar_ptr, bytes);
victim = _int_malloc(ar_ptr, bytes);
/* Retry with another arena only if we were able to find a usable arena
before. */
if (!victim && ar_ptr != NULL) {
LIBC_PROBE(memory_malloc_retry, 1, bytes);
ar_ptr = arena_get_retry(ar_ptr, bytes);
victim = _int_malloc(ar_ptr, bytes);
}
if (ar_ptr != NULL) __libc_lock_unlock(ar_ptr->mutex);
assert(!victim || chunk_is_mmapped(mem2chunk(victim)) ||
ar_ptr == arena_for_chunk(mem2chunk(victim)));
return victim;
}
```
## free
(https://github.com/iromise/glibc/blob/master/malloc/malloc.c#L465)
```
/*
free(void* p)
Releases the chunk of memory pointed to by p, that had been previously
allocated using malloc or a related routine such as realloc.
It has no effect if p is null. It can have arbitrary (i.e., bad!)
effects if p has already been freed.
Unless disabled (using mallopt), freeing very large spaces will
when possible, automatically trigger operations that give
back unused memory to the system, thus reducing program footprint.
*/
```
- source:
```c
void __libc_free(void *mem) {
mstate ar_ptr;
mchunkptr p; /* chunk corresponding to mem */
/ / Determine whether there is a hook function __free_hook
void (*hook)(void *, const void *) = atomic_forced_read(__free_hook);
if (__builtin_expect(hook != NULL, 0)) {
(*hook)(mem, RETURN_ADDRESS(0));
return;
}
// free NULL has no effect
if (mem == 0) /* free(0) has no effect */
return;
/ / Convert mem to chunk state
p = mem2chunk(mem);
// If the block memory is obtained by mmap
if (chunk_is_mmapped(p)) /* release mmapped memory. */
{
/* See if the dynamic brk/mmap threshold needs adjusting.
Dumped fake mmapped chunks do not affect the threshold. */
if (!mp_.no_dyn_threshold && chunksize_nomask(p) > mp_.mmap_threshold &&
chunksize_nomask(p) <= DEFAULT_MMAP_THRESHOLD_MAX &&
!DUMPED_MAIN_ARENA_CHUNK(p)) {
mp_.mmap_threshold = chunksize(p);
mp_.trim_threshold = 2 * mp_.mmap_threshold;
LIBC_PROBE(memory_mallopt_free_dyn_thresholds, 2,
mp_.mmap_threshold, mp_.trim_threshold);
}
munmap_chunk(p);
return;
}
// Get a pointer to the allocation area according to the chunk
ar_ptr = arena_for_chunk(p);
// execute release
_int_free(ar_ptr, p, 0);
}
```
## tcache protection mechanism
### ptmalloc2 allocator
- ở libc 2.26 đến libc 2.29 trở đi, tcache sẽ kiểm tra chunk có **free()** hay chưa bằng cách thêm một giá trị tại ``bk_pointer``
===> cơ chế này để chống double free
- [examble](https://hackmd.io/@trhoanglan04/H1kTJh87h#231)
- for practice, use command below:
```bash
$ wget https://ftp.gnu.org/gnu/glibc/glibc-2.29.tar.gz
```
### ptmalloc3 allocator
- ở libc > 2.31, có thêm cơ chế xor bảo vệ tcache
```c
#define PROTECT_PTR(pos, ptr) \
((__typeof (ptr)) ((((size_t) pos) >> 12) ^ ((size_t) ptr)))
#define REVEAL_PTR(ptr) PROTECT_PTR (&ptr, ptr)
```
> với **ptr** là chunk trước đó trong tcache còn **pos** là chunk được free
- về cơ bản ta chỉ cần đảo ngược phép xor là được
``(ptr >> 12)^addr``
> **ptr** là chunk mà ta sẽ overwrite ``fw_pointer``
> **addr** là địa chỉ cần malloc tới
## tcache Data Structure
- tcache là một kỹ thuật được giới thiệu sau glibc 2.26 (ubuntu 17.10) (xem [commit](https://sourceware.org/git/?p=glibc.git;a=commitdiff;h=d5c3fafc4307c9b7a4c7d5cb381fcdbfad340bcc)), mục đích là để cải thiện ==Hiệu suất quản lý heap==
- nhưng trong khi cải thiện hiệu suất, nó đã loại bỏ rất nhiều kiểm tra bảo mật, vì vậy có nhiều cách mới để sử dụng nó.
```
Free tcahce-cached chunks have a pointer to the allocated space of the next chunk
and a pointer to the per-thread struct
```
### tcache_entry
- [source code](https://code.woboq.org/userspace/glibc/malloc/malloc.c.html#tcache_entry)
```c
/* 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;
```
- ``tcache_entry`` linking cái free chunk structures
- cái ``*next`` sẽ trỏ tới chunk tiếp theo cùng size
> free(b) sẽ trỏ b trước (*next của b sẽ trỏ NULL)
> tiếp tục free(a) sẽ trỏ a, *next của a sẽ trỏ b
> tương tự cho những cái sau
- ngoài ra, ``tcache_entry`` còn ghép dữ liệu user data portion của free chunk
### tcache_perthread_struct
- [source code](https://code.woboq.org/userspace/glibc/malloc/malloc.c.html#tcache_perthread_struct)
```c
/* 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;
```
- mỗi thread duy trì 1 luồng ``tcache_prethread_struct``
- là 1 cấu trúc quản lí toàn bộ tcache
>``counts[tc_idx]`` ghi lại số freed chunks trong chuỗi ``tcache_entry`` chain, với tối đa 7 chunks trên mỗi chain
>``entries[tc_idx]`` linking các freed chunks cùng size trong dslk đơn (tựa fastbins)
- example:
> khi malloc 0x10
> khi free
> nhận thấy là:
> highlight vàng ---> **counts**
> highlight lam ---> **entries** (là 1 pointer) ---> trỏ đến chunk highlight lục
- more example:
> malloc 0x30 và free nó
> lúc này **counts** nó đếm lượt free cho 0x10 và 0x30 mỗi bin là '1'
> tương tự như thế cho các freed chunk cùng size (1++) hoặc khác size
### summary
> struct dựa trên 2 thành phần : **counts** và **entries**
- **counts** của từng size có dấu hiệu nhận biết là 2 bytes
> ví dụ ở hightlight vàng:
> 0x0000 : size 0x50
> -------0001 : size 0x40
> ------------0000 : size 0x30
> -----------------0001 : size 0x20
> max counts là 64 ``(8*8)``
> 
> số '0x291' ``(0x280 + 0x10)`` là size of allocated chunk
> 
### ref
- http://tukan.farm/2017/07/08/tcache/
- https://www.youtube.com/watch?v=0jHtqqdVv1Y
- https://www.youtube.com/watch?v=dtHIaH6q_1M
- https://elixir.bootlin.com/glibc/glibc-2.27/source/malloc/malloc.c#L2930
- https://azeria-labs.com/heap-exploitation-part-2-glibc-heap-free-bins/
Sign in with Wallet
Connect another wallet