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:

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:

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
• for practice, use command below:

$ 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

#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), 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

/* 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

/* 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/