Introduction
In the first part of this lecture, I introduce the structure of memory chunk and the internal implementation of memory allocation in ptmalloc. In this part, I will continue the remaining part in ptmalloc. First, I will give a introduction on deallocation and reallocation procedure in ptmalloc. Then I will introduce the security checks in ptmalloc and their intentions.
Ptmalloc Deallocation
Function __libc_free
Similar to ptmalloc allocation, function _int_free is the internal implementation of pamalloc deallocation and is invoked via the wrapper function __libc_free. Different from __libc_malloc, there are some extra steps to do before calling _int_free.
void __libc_free (void *mem)
{
mstate ar_ptr;
mchunkptr p; /* chunk corresponding to mem */
p = mem2chunk (mem);
if (chunk_is_mmapped (p)) /* release mmapped memory. */
{
/* see if the dynamic brk/mmap threshold needs adjusting */
if (!mp_.no_dyn_threshold
&& p->size > mp_.mmap_threshold
&& p->size > DEFAULT_MMAP_THRESHOLD_MAX)
{
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;
}
ar_ptr = arena_for_chunk (p);
_int_free (ar_ptr, p, 0);
}
libc_hidden_def (__libc_free)
Function __libc_free will first check if the current chunk is directly allocate via mmap. If so, the deallocator will unmap the chunk directly without call _libc_free.
Then it will check if the current chunk belongs to the main_arena. If no, the deallocator will retrieve the arena pointer first. To get the arena pointer, the chunk pointer will be ANDed with 0xfff00000 on X86 system, while on X64 system the chunk pointer will be ANDed with 0xfffffffffc000000.
Function unlink
Unlink function is a very important function in heap chunk management. As demonstrated in part one, all freed chunks except for fastbin chunk are maintained via doubly linked list. Function unlink(P, BK, FD) will remove the chunk P from its current doubly linked list.
Free internal
In general, the procedure can be divided into three steps. In the first step, if the freed chunk belongs to fastbin chunk, the deallocator will insert the chunk into fastbin chunk. In the second step, if size of the freed chunk is larger than fast bin size, the deallocator will process the chunk first and insert the processed chunks into corresponding chunk. The third step is an extra step, if size of the freed chunk is larger than a threshold (0x10000), the deallocator will try to consolidate the freed chunk as much as possible. More details have been given in the picture below and I will introduce the workflow of each step combined with the source code of libc.
Fastbin Chunk Deallocation
/* We might not have a lock at this point and concurrent modifications
of system_mem might have let to a false positive. Redo the test
after getting the lock. */
if (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ || chunksize (chunk_at_offset (p, size)) >= av->system_mem;)
{
errstr = "free(): invalid next size (fast)";
goto errout;
}
if (! have_lock)
{
(void)mutex_unlock(&av->mutex);
locked = 0;
}
free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
set_fastchunks(av);
unsigned int idx = fastbin_index(size);
fb = &fastbin (av, idx);
/* Atomically link P to its fastbin: P->FD = *FB; *FB = P; */
mchunkptr old = *fb, old2;
unsigned int old_idx = ~0u;
do
{
/* Check that the top of the bin is not the record we are going to add
(i.e., double free). */
if (__builtin_expect (old == p, 0))
{
errstr = "double free or corruption (fasttop)";
goto errout;
}
/* Check that size of fastbin chunk at the top is the same as
size of the chunk that we are adding. We can dereference OLD
only if we have the lock, otherwise it might have already been
deallocated. See use of OLD_IDX below for the actual check. */
if (have_lock && old != NULL)
old_idx = fastbin_index(chunksize(old));
p->fd = old2 = old;
}
while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);
The deallocator will first check the validity of size of the freed chunk and the first chunk (old) in the fastbin. If the check passes, the deallocator will insert the freed chunk into the fastbin as the new first chunk and set the FD pointer to point to old.
Smallbin Chunk Deallocation
nextchunk = chunk_at_offset(p, size);
/* Lightweight tests: check whether the block is already the
top block. */
if (__glibc_unlikely (p == av->top))
{
errstr = "double free or corruption (top)";
goto errout;
}
/* Or whether the next chunk is beyond the boundaries of the arena. */
if (__builtin_expect (contiguous (av)
&& (char *) nextchunk>= ((char *) av->top + chunksize(av->top)), 0))
{
errstr = "double free or corruption (out)";
goto errout;
}
/* Or whether the block is actually not marked used. */
if (__glibc_unlikely (!prev_inuse(nextchunk)))
{
errstr = "double free or corruption (!prev)";
goto errout;
}
nextsize = chunksize(nextchunk);
if (__builtin_expect (nextchunk->size <= 2 * SIZE_SZ, 0) || __builtin_expect (nextsize >= av->system_mem, 0))
{
errstr = "free(): invalid next size (normal)";
goto errout;
}
free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
/* consolidate backward */
if (!prev_inuse(p)) {
prevsize = p->prev_size;
size += prevsize;
p = chunk_at_offset(p, -((long) prevsize));
unlink(p, bck, fwd);
}
if (nextchunk != av->top) {
/* get and clear inuse bit */
nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
/* consolidate forward */
if (!nextinuse) {
unlink(nextchunk, bck, fwd);
size += nextsize;
} else
clear_inuse_bit_at_offset(nextchunk, 0);
/*
Place the chunk in unsorted chunk list. Chunks are
not placed into regular bins until after they have
been given one chance to be used in malloc.
*/
bck = unsorted_chunks(av);
fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
{
errstr = "free(): corrupted unsorted chunks";
goto errout;
}
p->fd = fwd;
p->bk = bck;
if (!in_smallbin_range(size))
{
p->fd_nextsize = NULL;
p->bk_nextsize = NULL;
}
bck->fd = p;
fwd->bk = p;
set_head(p, size | PREV_INUSE);
set_foot(p, size);
check_free_chunk(av, p);
}
else {
size += nextsize;
set_head(p, size | PREV_INUSE);
av->top = p;
check_chunk(av, p);
}
The deallocation on a smallbin chunk works as following:
(1) If the adjacent previous chunk is freed, merge the current chunk with the previous chunk. Unlink the previous chunk and set the newly merged chunk as current chunk.
(2) If the next adjacent chunk is top chunk, merge the current chunk into top chunk. Otherwise go to step (3).
(3) If the next adjacent chunk is freed, merge the current chunk with the next adjacent chunk. Unlink the next adjacent chunk and set the newly merged chunk as current chunk. If the next adjacent chunk is not freed, set the P bit of next adjacent chunk to 0.
(4) Insert the current chunk into the unsorted bin. Set header and footer accordingly.
Reduce Fragmented Chunks
if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
if (have_fastchunks(av))
malloc_consolidate(av);
if (av == &main_arena) {
#ifndef MORECORE_CANNOT_TRIM
if ((unsigned long)(chunksize(av->top)) >=
(unsigned long)(mp_.trim_threshold))
systrim(mp_.top_pad, av);
#endif
} else {
/* Always try heap_trim(), even if the top chunk is not
large, because the corresponding heap might go away. */
heap_info *heap = heap_for_ptr(top(av));
assert(heap->ar_ptr == av);
heap_trim(heap, mp_.top_pad);
}
}
If the size of freed chunk exceeds FASTBIN_CONSOLIDATION_THRESHOLD, the deallocator will merge the fastbin chunks as much as possible. According to the type of mstate, trim the heap respectively.
Ptmalloc Reallocation
Function realloc will try to resize the target chunk and return a new chunk pointer of the requested size. The first step of reallocation extracts the desired chunk from heap. The second step will do the post-processing on the remaining part.
Realloc Internal
The workflow of _int_realloc is shown below.
Resize chunk
if ((unsigned long) (oldsize) >= (unsigned long) (nb))
{
/* already big enough; split below */
newp = oldp;
newsize = oldsize;
}
else
{
/* Try to expand forward into top */
if (next == av->top &&
(unsigned long) (newsize = oldsize + nextsize) >=
(unsigned long) (nb + MINSIZE))
{
set_head_size (oldp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
av->top = chunk_at_offset (oldp, nb);
set_head (av->top, (newsize - nb) | PREV_INUSE);
check_inuse_chunk (av, oldp);
return chunk2mem (oldp);
}
/* Try to expand forward into next chunk; split off remainder below */
else if (next != av->top &&
!inuse (next) &&
(unsigned long) (newsize = oldsize + nextsize) >= (unsigned long) (nb))
{
newp = oldp;
unlink (next, bck, fwd);
}
/* allocate, copy, free */
else
{
newmem = _int_malloc (av, nb - MALLOC_ALIGN_MASK);
if (newmem == 0)
return 0; /* propagate failure */
newp = mem2chunk (newmem);
newsize = chunksize (newp);
/*
Avoid copy if newp is next chunk after oldp.
*/
if (newp == next)
{
newsize += oldsize;
newp = oldp;
}
else
{
/*code of copying data*/
_int_free (av, oldp, 1);
check_inuse_chunk (av, newp);
return chunk2mem (newp);
}
}
}
(1) If the requested size is smaller than the current size, go to post-processing.
(2) If the next chunk is top chunk, split one chunk from the top chunk and merge the current chunk with the new chunk and return.
(3) In the situation when the next adjacent chunk is not top chunk, the next adjacent chunk is freed and the addition of size of the current chunk and next adjacent chunk is larger than the requested size. Unlink the next chunk, merge current chunk and next chunk, set the merged chunk as current chunk and go to post-processing. Otherwise go to step 4.
(4) Allocate a new chunk of requested size. If the new chunk happens to be the next adjacent chunk of current chunk, merge the current chunk with the new chunk and go to post-processing. Otherwise, free the current chunk and return the newly allocated chunk.
Post-processing
remainder_size = newsize - nb;
if (remainder_size < MINSIZE) /* not enough extra to split off */
{
set_head_size (newp, newsize | (av != &main_arena ? NON_MAIN_ARENA : 0));
set_inuse_bit_at_offset (newp, newsize);
}
else /* split remainder */
{
remainder = chunk_at_offset (newp, nb);
set_head_size (newp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
/* Mark remainder as inuse so free() won't complain */
set_inuse_bit_at_offset (remainder, remainder_size);
_int_free (av, remainder, 1);
}
check_inuse_chunk (av, newp);
return chunk2mem (newp);
(1) If the size of remainder chunk is smaller than the smallest size, do not split the chunk and return the whole chunk as return value.
(2) Otherwise, split the current chunk into a chunk of requested size and a chunk of remainder size. Free the remainder chunk and return the chunk of requested size.
Security Checks in Ptmalloc
- Now I will introduce the security checks in ptmalloc covering unlink, _int_malloc and _int_free.
Security checks in unlink
Check if the chunk (smallbin chunk) to unlink belongs to an doubly linked list.if (__builtin_expect (FD->bk != P || BK->fd != P, 0)) malloc_printerr (check_action, "corrupted double-linked list", P, AV); -
If the chunk to unlink is a largebin, take the following check if the previous check pass. The following code checks if the largebin belongs to another doubly linked list.
if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0) || __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0)) malloc_printerr (check_action,"corrupted double-linked list (not small)", P, AV);
Security checks in _int_malloc
1. The victim chunk to alloc is placed in the fastbin linked list. If the size victim chunk does not fit the fastbin index, it means that metadata of the victim chunk has been corrupted.
if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
{
errstr = "malloc(): memory corruption (fast)";
errout:
malloc_printerr (check_action, errstr, chunk2mem (victim), av);
return NULL;
}
- Check if the backward chunk and victim chunk belong to the same doubly linked list. If the forward pointer of the backward chunk does not point to the victim chunk, it means that the smallbin double linked list is corrupted.
if (__glibc_unlikely (bck->fd != victim)) { errstr = "malloc(): smallbin double linked list corrupted"; goto errout; } -
When processing the unsorted chunks, it will first check the metadata of unsorted chunk is legal. If the size of victim chunk is too small or too large, the check fails.
if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0) || __builtin_expect (victim->size > av->system_mem, 0)) malloc_printerr (check_action, "malloc(): memory corruption", chunk2mem (victim));
-
When inserting a remainder chunk splitted from large chunk, it will check if the first chunk in unsorted bin list points to the head of unsorted bin list.
if (__glibc_unlikely (fwd->bk != bck)) { errstr = "malloc(): corrupted unsorted chunks"; goto errout; } if (__glibc_unlikely (fwd->bk != bck)) { errstr = "malloc(): corrupted unsorted chunks 2"; goto errout; }
Security checks in _int_free
1. Check if the chunk to free is located at an valid address: (1) The chunk does exceed the bottom of address space. (2) The last 4 (on X64) or 3 (on X86) bits are all zero.
if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
|| __builtin_expect (misaligned_chunk (p), 0))
{
errstr = "free(): invalid pointer";
errout:
if (!have_lock && locked)
(void) mutex_unlock (&av->mutex);
malloc_printerr (check_action, errstr, chunk2mem (p), av);
return;
}
- Check if the size of the chunk is valid: (1) larger than minimal space. (2) The last 4 (on X64) or 3 (on X86) bits are not all zero.
if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size))) { errstr = "free(): invalid size"; goto errout; } -
Check if the size of chunk to insert into fastbin is valid.
if (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ || chunksize (chunk_at_offset (p, size)) >= av->system_mem) { errstr = "free(): invalid next size (fast)"; goto errout; } -
Check the first chunk in fastbin is not the current chunk that is to be inserted.
if (__builtin_expect (old == p, 0)) { errstr = "double free or corruption (fasttop)"; goto errout; } -
Check the size of first chunk in fastbin is the same as the size of the current chunk that is to be inserted.
if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0)) { errstr = "invalid fastbin entry (free)"; goto errout; } -
Check the chunk to be freed is not the top chunk.
if (__glibc_unlikely (p == av->top)) { errstr = "double free or corruption (top)"; goto errout; } -
Check the next adjacent chunk is not exceeding the size of current heap.
if (__builtin_expect (contiguous (av) && (char *) nextchunk >= ((char *) av->top + chunksize(av->top)), 0)) { errstr = "double free or corruption (out)"; goto errout; } -
Check the P bit of next adjacent chunk is set.
if (__glibc_unlikely (!prev_inuse(nextchunk))) { errstr = "double free or corruption (!prev)"; goto errout; } -
Check the size of next adjacent chunk is valid.
if (__builtin_expect (nextchunk->size <= 2 * SIZE_SZ, 0) || __builtin_expect (nextsize >= av->system_mem, 0)) { errstr = "free(): invalid next size (normal)"; goto errout; } -
When inserting the chunk into the unsorted bin, check if the backward pointer of first chunk in unsorted bin is pointing to the head of unsorted bin.
if (__glibc_unlikely (fwd->bk != bck)) { errstr = "free(): corrupted unsorted chunks"; goto errout; }
Conclusion
After this part of my tutorial, I recommend to read the Summary section in previous one again. I believe you will find more details hidden there. So far, I have finished the tutorial on ptmalloc memory management. I will move to the exploitation part next.
氷 菓 