Module: Dynamic Allocator Misuse

Metadata and Chunks

Yan Shoshitaishvili

Arizona State University

Heap Metadata and its Corruption

As we saw with tcache, the ptmalloc uses a bunch of metadata to track its operation. It keeps them in:

​

1. global metadata (i.e., the tcache structure)
2. per-chunk metadata

​

What's a chunk?

Metadata: Allocated Chunks

malloc(x) returns mem_addr, but in actuality, ptmalloc tracks chunk_addr:

unsigned long mchunk_prev_size;

unsigned long mchunk_size;

USABLE MEMORY (at least size x)

mem_addr:

chunk_addr:

Metadata: Size?

malloc(n) guarantees at least n usable space, but chunks sizes are multiples of 0x10.

unsigned long mchunk_prev_size;

unsigned long mchunk_size;

USABLE MEMORY (at least size x)

mem_addr:

chunk_addr:

Last 3 bits are flags:

Bit 0: PREV_IN_USE

Bit 1: IS_MMAPPED

Bit 2: NON_MAIN_ARENA

​

Not used for tcache...

Metadata: Overlapping metadata!

To save memory, the prev_size field of a chunk whose PREV_INUSE flag is set (i.e., the previous chunk is not free) is used by the previous chunk!

​

​

​

chunk1: unsigned long *a = malloc(0x10)

prev_size

size

a[0]

a[1]

chunk2: unsigned long *b = malloc(0x10)

prev_size

size

b[0]

b[1]

chunk1: unsigned long *a = malloc(0x18)

prev_size

size

a[0]

a[1]

chunk2: unsigned long *b = malloc(0x10)

prev_size

size

b[0]

b[1]

a[2]

Metadata: Freed Chunks

As we saw with tcache, a free()d chunk has additional metadata about the location of other chunks:

unsigned long mchunk_prev_size;

unsigned long mchunk_size;

CACHE-SPECIFIC METADATA

mem_addr:

chunk_addr:

Metadata: Different Caches

This information is constantly changing (see: tcache) and PTMALLOC IS VERY COMPLEX. This is an approximation.

​

Currently, the ptmalloc caching design is (in order of use):

​

1. 64 singly-linked tcache bins for allocations of size 16 to 1032 (functionally "covers" fastbins and smallbins)
2. 10 singly-linked "fast" bins for allocations of size up to 160 bytes
3. 1 doubly-linked "unsorted" bin to quickly stash free()d chunks that don't fit into tcache or fastbins
4. 64 doubly-linked "small" bins for allocations up to 512 bytes
5. doubly-linked "large" bins (anything over 512 bytes) that contain different-sized chunks

Metadata: tcache Chunks

Free tcache-cached chunks have a pointer to the allocated space of the next chunk and a pointer to the per-thread struct.

unsigned long mchunk_prev_size;

unsigned long mchunk_size;

struct tcache_entry *next;

struct tcache_perthread_struct *key;

mem_addr:

chunk_addr:

Metadata: largebin Chunks

When free()d, large are:

1. Consolidated with adjacent free chunks.
2. Put into an "unsorted" bin regardless of size.
3. Properly put into a doubly-linked list later, during the next allocation that they fail to "satisfy".

​

unsigned long mchunk_prev_size;

unsigned long mchunk_size;

struct malloc_chunk* fd;

struct malloc_chunk* bk;

struct malloc_chunk* fd_nextsize;

struct malloc_chunk* bk_nextsize;

mem_addr:

chunk_addr:

Metadata: The Wilderness

The heap is a finite-sized allocation that needs to be manually expanded.

​

During allocation, malloc() will (simplified view):

​

1. Look for a free chunk that will satisfy the allocation, and return it.
2. Otherwise, check the "available" space left at the end of the heap. If there is enough there, return that and reduce the "available" space.
3. If there isn't enough "available" space, malloc() will mmap() certain large allocations.
4. Otherwise, malloc will grow the heap with brk() and go to #2.

​

How does malloc() store the available space? In the "Wilderness", a fake chunk at the end of the heap that stores the available space.

Other Allocators?

Allocators are different! This metadata discussion, and tcache, is very ptmalloc-specific.

​

Example: jemalloc has no inline metadata!