Description
Problem
The heap implementation has a memory leak, so that even using only code that is considered safe, the heap memory can be exhausted so that next allocation requests will fail.
Cause
This happens because, when the back padding of a chunk is not enough to store a hole, it is considered to be part of the allocated chunk, but when that chunk is deallocated, this back padding is not taken into account, and the size of the hole is just set to the size of the aligned layout of the allocation.
Example
The following example provides a function which breaks the heap and wastes all of it's memory. Heap allocations that are performed after a call to break_heap and are of a size that is larger than 16 bytes will fail with an out of memory condition, even though this function properly deallocates every single allocation that it performs before returning.
Note that although this example contains unsafe blocks, it is considered safe, and if another allocator would have been used here, this function would not break the heap, since all allocations are properly deallocated, which is guaranteed by using the Allocation struct, and by wrapping allocations in a Box in the Barrier struct.
If this function is executed for example on the chunk allocator from the simple-chunk-allocator crate, the function loops infinitely because it keeps trying to waste the largest chunk but it doesn't get wasted since that heap implementation doesn't have this memory leak bug.
This function can break the heap even if some parts of it are used, and it will waste all of the currently unused chunks that are larger than 16 bytes.
fn break_heap() {
/// A safe abstraction over a heap allocation.
struct Allocation {
ptr: *mut u8,
layout: Layout,
}
impl Allocation {
fn new(size: usize) -> Self {
let layout = Layout::from_size_align(size, 1).unwrap();
let ptr = unsafe { alloc(layout) };
if ptr.is_null() {
panic!("allocation failed, size: {}", size);
}
Self { ptr, layout }
}
fn try_new(size: usize) -> Option<Self> {
let layout = Layout::from_size_align(size, 1).unwrap();
let ptr = unsafe { alloc(layout) };
if ptr.is_null() {
return None;
}
Some(Self { ptr, layout })
}
}
impl Drop for Allocation {
fn drop(&mut self) {
unsafe { dealloc(self.ptr, self.layout) }
}
}
/// The barrier allocates many chunks of memory and must keep track of them.
/// To do so it uses a linked list, and this struct represents a node in
/// that linked list.
struct BarrierLinkedListNode {
next: Option<Box<BarrierLinkedListNode>>,
}
/// A barrier that is used to prevent the wasted chunk from merging with the
/// top of the heap when deallocated.
struct Barrier {
_node: Box<BarrierLinkedListNode>,
}
impl Barrier {
fn new() -> Self {
// in order to create a barrier we must allocate as many chunks of 16 bytes as
// possible, to make sure that we hit the right hole.
fn try_allocate_node() -> Option<Box<BarrierLinkedListNode>> {
// using the unsafe `alloc` function here so that we can check for allocation
// failure instead of panicking.
let ptr = unsafe { alloc(Layout::new::<BarrierLinkedListNode>()) }
.cast::<BarrierLinkedListNode>();
if ptr.is_null() {
return None;
}
unsafe { ptr.write(BarrierLinkedListNode { next: None }) };
Some(unsafe { Box::from_raw(ptr) })
}
// we expect at least 1 allocation to be successful.
let mut cur = try_allocate_node().unwrap();
loop {
match try_allocate_node() {
Some(mut allocated_node) => {
allocated_node.next = Some(cur);
cur = allocated_node;
},
None => break,
}
}
Self { _node: cur }
}
}
/// Returns an estimation for the size of the largest chunk in the heap.
///
/// The result is guaranteed to be aligned to 8 bytes.
fn guess_heap_largest_chunk_size() -> usize {
// start from the minimum allocation size
let mut cur_allocation_size = 16;
loop {
if Allocation::try_new(cur_allocation_size * 2).is_none() {
break;
}
cur_allocation_size *= 2;
}
// we now know that the heap size it between `cur_allocation_size` and
// `cur_allocation_size * 2` (not including `cur_allocation_size * 2`).
//
// we can perform a binary search to find the actual heap size.
let mut step = cur_allocation_size / 2;
while step >= 8 {
if Allocation::try_new(cur_allocation_size + step).is_some() {
cur_allocation_size += step
}
step /= 2;
}
cur_allocation_size
}
// a loop which runs on each largest block in the heap
loop {
// find the size of the current largest chunk in the heap.
let heap_largest_chunk_size = guess_heap_largest_chunk_size();
println!("heap_largest_chunk_size: {}", heap_largest_chunk_size);
// We can only waste chunks of memory that are larger than 16.
// If the largest chunk is not larger than 16, then we don't have any more
// chunks to waste.
if heap_largest_chunk_size <= 16 {
break;
}
// Now we must perform a trick to prevent this chunk form merging with the top
// of the heap in case it is at the end of the heap.
//
// We don't know if it's indeed at the end or not, so we perform the trick
// anyway.
//
// The trick involves splitting our huge chunk into 2 parts: a barrier
// allocation and another allocation for the rest of the chunk.
//
// The barrier must come after the other chunk to prevent that chunk from
// merging with the top of the heap.
//
// The initial allocation done below is the allocation for the rest of the chunk
// other than the barrier, which will make the allocator create a hole
// right at the end of the large chunk that we're currently wasting.
// That hole will then be allocated to make it a barrier.
// We must first allocate chunk at the end of the heap, so that the
// `check_merge_top` function doesn't fix the problem. Thus, we leave 16
// bytes which is the minimum chunk size, which will make sure that a hole
// is created right after our initial allocation and we can then allocate
// something into that hole.
//
// the purpose of the initial allocation is just to allow us to create that
// barrier at the end of the heap.
let initial_allocation_size = heap_largest_chunk_size - 16;
// The allocation for the barrier.
// Note that this allocation lives for the entire duration while we waste this
// chunk, because otherwise the deallocated holes might merge with the
// top of the heap.
//
// It's actually not necessary for it to live for the entire time, but just for
// the first waste allocation, which will create a region of wasted
// memory between the wasted chunk and the barrier.
let _barrier_allocation;
// the scope is so that the initial allocation is freed once we successfully
// initialize the barrier, since the only purpose of the initial allocation
// is to create the barrier.
{
let _initial_allocation = Allocation::new(initial_allocation_size);
// after the initial allocation, make sure that we create a barrier to
// "unfree" the hole that was created at the end of the heap, which will prevent
// deallocations from merging with the top of the heap through the
// `check_merge_top` function.
_barrier_allocation = Barrier::new();
}
let mut cur_size = initial_allocation_size;
// slowly waste the chunk.
while cur_size > 16 {
let smaller_size = cur_size - 8;
{
let _allocation = Allocation::new(smaller_size);
}
cur_size = smaller_size;
}
}
}