Heap Fundamentals: tcache

On Wednesday evening I started to go through the flow chart with the VIP students and it encouraged me that some walkthroughs of the flow chart would be valuable.

The task of this series of lectures we started last time is to understand what happens in the malloc and free flowcharts. The big reason for this is that any working exploit will live in one of those boxes. So you have to be able to contrive a situation that will walk the process into the vulnerable corner case. (Inversely as the secure software designer you need to be able to ensure that your program doesn't allow an entry into one of the key boxes with vulnerable constraints.)

OK so let's look at the malloc and free flow charts again (a daily occurence for a little bit):

The MALLOC flowchart

The FREE flowchart

Mastering tcache: the why of it (part 1)

Thread safe means that the meta-data for tcache (the heads of the linked lists) doesn't live in glibc (the main_arena) but as a big-honking struct inside of the heap. This is because the heap, glibc, and many segments of your program are SHARED ACROSS THREADS.

So EACH THREAD GETS THEIR OWN TCACHE STRUCT.

Why tcache limits? The Defragmentation Story:

Memory fragmentation is bad
THUS it is good to merge free'd chunks that are next to each other
Those chunks might not be the same size
The possibility of merging is WHY doubly-linked exists in smallbins/largebins
tcache and fastbins are "not really free" and are not designed to merge
That means that the more we use tcache and fastbins the more fragmented we get
SO occasionally we should consolidate these "not free" fastbins -> unsorted bin
Since tcache is made for a quick thread performance we try to load it up whenever possible
But because memory fragmentation is bad we limit the size of tcache
So at most 7 chunks per tcache bin and everything else will eventually get consolidated
This strikes the balance between speed and defragmented memory
The quick version of consolidating is to move smallbins into tcache AND to move fastbins into tcache

tcache TLDR

Needs to live in its own struct (not main_arena) on the heap [to be thread safe],

needs to be fast (one, singly-linked, bin per chunk size 0x20-0x410) [to be faster than typical locked shared resource using],

needs to have a limited count (7) of chunks per bin [to avoid excessive fragmentation].

Mastering tcache: the how of it

OK now the job is simple. Look at this struct, imagine it filling up and walk through the chart and decide that we know what's going on:

This is a struct, structs are almost like a map that tells us how to interpret a big piece of memory.

This particular struct is 40 rows long, ok rows is not a normal measurement but there are 64 bins. Each bin is one address, so there are 32 "rows" of addresses (each row is two addresses long). But first there are 8 "counts" per row (bytes in 32-bit and shorts in 64-bit) making 8 rows of counts and 32 rows of bins.

In the 64-bit case this means the struct is 40*16 bytes long or 0x280 and in 32-bit this struct is 40*8 bytes long or 0x140 total.

So let's suppose you want to know if the tcache has a chunk of size 0x20 available, you'd go to the first count spot on the first row and check if that value is greater than 0. If it is you can find a re-usable chunk in the first address of row 9.

Let's trace it

OK let's make some sample programs in order to see the boxes. Let's make some, compile them, trace them, then adjust them:

Let's run these and use the flowcharts and talk about what's happening.