Memory leak

[MaderNoob]

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;
        }
    }
}

[arturkow2000]

We have found a same/similar problem which also results in breaking of heap. Despite still having half of the heap free, there are no big-enough free holes

Hole size: 8
Hole size: 8
Hole size: 8
Hole size: 52
Hole size: 24
Hole size: 0

Full log:

INFO pal_nrf::heap > using memory region: 0x20016B50 - 0x20026B4F
INFO pal_nrf::heap > 103600 bytes are unused
INFO fobnail > Hello from main
TRACE pal_nrf::heap > alloc 2464 bytes (65536 free)
TRACE pal_nrf::heap > alloc 16 bytes (63072 free)
TRACE pal_nrf::heap > alloc 1500 bytes (63056 free)
TRACE pal_nrf::heap > alloc 44 bytes (61556 free)
TRACE pal_nrf::heap > alloc 12 bytes (61512 free)
TRACE pal_nrf::heap > free 12 bytes (61500 free)
TRACE pal_nrf::heap > alloc 1696 bytes (61512 free)
TRACE pal_nrf::heap > alloc 8 bytes (59816 free)
TRACE pal_nrf::heap > alloc 192 bytes (59808 free)
TRACE pal_nrf::heap > alloc 29 bytes (59616 free)
TRACE pal_nrf::heap > alloc 29 bytes (59584 free)
TRACE pal_nrf::heap > alloc 4 bytes (59552 free)
TRACE pal_nrf::heap > alloc 56 bytes (59544 free)
TRACE pal_nrf::heap > alloc 32 bytes (59488 free)
TRACE pal_nrf::heap > alloc 32 bytes (59456 free)
TRACE pal_nrf::heap > alloc 4 bytes (59424 free)
TRACE pal_nrf::heap > alloc 56 bytes (59416 free)
TRACE pal_nrf::heap > alloc 384 bytes (59360 free)
TRACE pal_nrf::heap > free 192 bytes (58976 free)
TRACE pal_nrf::heap > alloc 104 bytes (59168 free)
TRACE pal_nrf::heap > alloc 192 bytes (59064 free)
TRACE pal_nrf::heap > alloc 104 bytes (58872 free)
TRACE pal_nrf::heap > alloc 8 bytes (58768 free)
TRACE pal_nrf::heap > alloc 30 bytes (58760 free)
TRACE pal_nrf::heap > free 8 bytes (58728 free)
TRACE pal_nrf::heap > alloc 60 bytes (58736 free)
TRACE pal_nrf::heap > free 30 bytes (58676 free)
TRACE pal_nrf::heap > free 29 bytes (58708 free)
TRACE pal_nrf::heap > alloc 192 bytes (58740 free)
TRACE pal_nrf::heap > alloc 104 bytes (58548 free)
TRACE pal_nrf::heap > alloc 256 bytes (58444 free)
TRACE usbd_ethernet::eem > wrote 48 bytes
TRACE pal_nrf::heap > alloc 7 bytes (58156 free)
TRACE pal_nrf::heap > alloc 3 bytes (58148 free)
TRACE pal_nrf::heap > alloc 164 bytes (58140 free)
TRACE pal_nrf::heap > alloc 20 bytes (57976 free)
TRACE pal_nrf::heap > alloc 2 bytes (57956 free)
TRACE pal_nrf::heap > alloc 20 bytes (57948 free)
TRACE pal_nrf::heap > alloc 5 bytes (57928 free)
TRACE pal_nrf::heap > alloc 20 bytes (57920 free)
TRACE pal_nrf::heap > alloc 15 bytes (57900 free)
TRACE pal_nrf::heap > alloc 20 bytes (57884 free)
TRACE pal_nrf::heap > alloc 1 bytes (57864 free)
TRACE pal_nrf::heap > alloc 20 bytes (57856 free)
TRACE pal_nrf::heap > alloc 1 bytes (57836 free)
TRACE pal_nrf::heap > alloc 20 bytes (57828 free)
TRACE pal_nrf::heap > alloc 2 bytes (57808 free)
TRACE pal_nrf::heap > alloc 20 bytes (57800 free)
TRACE pal_nrf::heap > alloc 1024 bytes (57780 free)
TRACE pal_nrf::heap > alloc 892 bytes (56756 free)
TRACE pal_nrf::heap > alloc 7 bytes (55864 free)
TRACE pal_nrf::heap > alloc 1024 bytes (55856 free)
TRACE pal_nrf::heap > alloc 2 bytes (54396 free)
TRACE pal_nrf::heap > alloc 20 bytes (54388 free)
TRACE pal_nrf::heap > alloc 1024 bytes (54368 free)
TRACE pal_nrf::heap > alloc 7 bytes (53344 free)
TRACE pal_nrf::heap > alloc 1024 bytes (53336 free)
TRACE pal_nrf::heap > alloc 3 bytes (52312 free)
TRACE pal_nrf::heap > alloc 24 bytes (52304 free)
TRACE pal_nrf::heap > alloc 2 bytes (52280 free)
TRACE pal_nrf::heap > alloc 24 bytes (52272 free)
TRACE pal_nrf::heap > alloc 5 bytes (52248 free)
TRACE pal_nrf::heap > alloc 24 bytes (52240 free)
TRACE pal_nrf::heap > alloc 15 bytes (52216 free)
TRACE pal_nrf::heap > alloc 24 bytes (52200 free)
TRACE usbd_ethernet::eem > wrote 64 bytes
TRACE usbd_ethernet::eem > wrote 64 bytes
TRACE usbd_ethernet::eem > wrote 64 bytes
TRACE usbd_ethernet::eem > wrote 64 bytes
TRACE usbd_ethernet::eem > wrote 64 bytes
TRACE usbd_ethernet::eem > wrote 64 bytes
TRACE usbd_ethernet::eem > wrote 64 bytes
TRACE usbd_ethernet::eem > wrote 64 bytes
TRACE usbd_ethernet::eem > wrote 64 bytes
TRACE usbd_ethernet::eem > wrote 64 bytes
TRACE usbd_ethernet::eem > wrote 64 bytes
TRACE usbd_ethernet::eem > wrote 64 bytes
TRACE usbd_ethernet::eem > wrote 64 bytes
TRACE usbd_ethernet::eem > wrote 64 bytes
TRACE usbd_ethernet::eem > wrote 64 bytes
TRACE usbd_ethernet::eem > wrote 64 bytes
TRACE usbd_ethernet::eem > wrote 63 bytes
TRACE pal_nrf::heap > alloc 7 bytes (54852 free)
TRACE pal_nrf::heap > alloc 3 bytes (54844 free)
TRACE pal_nrf::heap > alloc 164 bytes (54836 free)
TRACE pal_nrf::heap > alloc 20 bytes (54672 free)
TRACE pal_nrf::heap > alloc 2 bytes (54652 free)
TRACE pal_nrf::heap > alloc 20 bytes (54644 free)
TRACE pal_nrf::heap > alloc 5 bytes (54624 free)
TRACE pal_nrf::heap > alloc 20 bytes (54616 free)
TRACE pal_nrf::heap > alloc 15 bytes (54596 free)
TRACE pal_nrf::heap > alloc 20 bytes (54580 free)
TRACE pal_nrf::heap > alloc 1 bytes (54560 free)
TRACE pal_nrf::heap > alloc 20 bytes (54552 free)
TRACE pal_nrf::heap > alloc 1 bytes (54532 free)
TRACE pal_nrf::heap > alloc 20 bytes (54524 free)
TRACE pal_nrf::heap > alloc 2 bytes (54504 free)
TRACE pal_nrf::heap > alloc 20 bytes (54496 free)
TRACE pal_nrf::heap > alloc 1024 bytes (54476 free)
TRACE pal_nrf::heap > alloc 892 bytes (53452 free)
TRACE pal_nrf::heap > alloc 7 bytes (52560 free)
TRACE pal_nrf::heap > alloc 1024 bytes (52552 free)
TRACE pal_nrf::heap > alloc 3 bytes (51528 free)
TRACE pal_nrf::heap > alloc 24 bytes (51520 free)
TRACE pal_nrf::heap > alloc 2 bytes (51496 free)
TRACE pal_nrf::heap > alloc 24 bytes (51488 free)
TRACE pal_nrf::heap > alloc 5 bytes (51464 free)
TRACE pal_nrf::heap > alloc 24 bytes (51456 free)
TRACE pal_nrf::heap > alloc 15 bytes (51432 free)
TRACE pal_nrf::heap > alloc 24 bytes (51416 free)
TRACE pal_nrf::heap > free 15 bytes (46484 free)
TRACE pal_nrf::heap > free 20 bytes (46500 free)
TRACE pal_nrf::heap > free 1 bytes (46520 free)
TRACE pal_nrf::heap > free 20 bytes (46528 free)
TRACE pal_nrf::heap > free 1 bytes (46548 free)
TRACE pal_nrf::heap > free 20 bytes (46556 free)
TRACE pal_nrf::heap > free 2 bytes (46576 free)
TRACE pal_nrf::heap > free 20 bytes (46584 free)
TRACE pal_nrf::heap > free 164 bytes (46604 free)
TRACE pal_nrf::heap > alloc 7 bytes (53828 free)
TRACE pal_nrf::heap > alloc 3 bytes (53820 free)
TRACE pal_nrf::heap > alloc 164 bytes (53812 free)
TRACE pal_nrf::heap > alloc 20 bytes (53648 free)
TRACE pal_nrf::heap > alloc 2 bytes (53628 free)
TRACE pal_nrf::heap > alloc 20 bytes (53620 free)
TRACE pal_nrf::heap > alloc 5 bytes (53600 free)
TRACE pal_nrf::heap > alloc 20 bytes (53592 free)
TRACE pal_nrf::heap > alloc 15 bytes (53572 free)
TRACE pal_nrf::heap > alloc 20 bytes (53556 free)
TRACE pal_nrf::heap > alloc 1 bytes (53536 free)
TRACE pal_nrf::heap > alloc 20 bytes (53528 free)
TRACE pal_nrf::heap > alloc 1 bytes (53508 free)
TRACE pal_nrf::heap > alloc 20 bytes (53500 free)
TRACE pal_nrf::heap > alloc 2 bytes (53480 free)
TRACE pal_nrf::heap > alloc 20 bytes (53472 free)
TRACE pal_nrf::heap > alloc 789 bytes (53452 free)
TRACE pal_nrf::heap > alloc 892 bytes (52660 free)
TRACE pal_nrf::heap > alloc 7 bytes (51768 free)
TRACE pal_nrf::heap > alloc 789 bytes (51760 free)
TRACE pal_nrf::heap > alloc 15 bytes (47208 free)
TRACE pal_nrf::heap > alloc 20 bytes (47192 free)
TRACE pal_nrf::heap > alloc 1 bytes (47172 free)
TRACE pal_nrf::heap > alloc 20 bytes (47164 free)
TRACE pal_nrf::heap > alloc 1 bytes (47144 free)
TRACE pal_nrf::heap > alloc 20 bytes (47136 free)
TRACE pal_nrf::heap > alloc 2 bytes (47116 free)
TRACE pal_nrf::heap > alloc 20 bytes (47108 free)
TRACE pal_nrf::heap > alloc 2837 bytes (47088 free)
TRACE pal_nrf::heap > alloc 7 bytes (44248 free)
TRACE pal_nrf::heap > alloc 164 bytes (44240 free)
TRACE pal_nrf::heap > alloc 1 bytes (44076 free)
TRACE pal_nrf::heap > alloc 20 bytes (44068 free)
TRACE pal_nrf::heap > alloc 789 bytes (44048 free)
TRACE pal_nrf::heap > alloc 488 bytes (43256 free)
INFO fobnail > new client: 169.254.0.8:54916
TRACE pal_nrf::heap > alloc 168 bytes (42768 free)
TRACE pal_nrf::heap > alloc 256 bytes (36392 free)
TRACE pal_nrf::heap > alloc 256 bytes (36136 free)
TRACE pal_nrf::heap > free 256 bytes (35880 free)
TRACE pal_nrf::heap > alloc 256 bytes (36136 free)
TRACE pal_nrf::heap > alloc 4 bytes (35880 free)
TRACE pal_nrf::heap > free 4 bytes (35872 free)
TRACE pal_nrf::heap > alloc 528 bytes (35880 free)
TRACE pal_nrf::heap > alloc 1024 bytes (35352 free)
TRACE pal_nrf::heap > alloc 256 bytes (34328 free)
TRACE pal_nrf::heap > alloc 272 bytes (34072 free)
TRACE pal_nrf::heap > alloc 264 bytes (33800 free)
TRACE pal_nrf::heap > free 264 bytes (33536 free)
TRACE pal_nrf::heap > alloc 272 bytes (33800 free)
TRACE pal_nrf::heap > free 272 bytes (33528 free)
TRACE pal_nrf::heap > alloc 272 bytes (33800 free)
TRACE pal_nrf::heap > free 272 bytes (33528 free)
TRACE pal_nrf::heap > alloc 272 bytes (33800 free)
TRACE pal_nrf::heap > free 272 bytes (33528 free)
TRACE pal_nrf::heap > alloc 272 bytes (33800 free)
TRACE pal_nrf::heap > free 272 bytes (33528 free)
TRACE pal_nrf::heap > alloc 512 bytes (33576 free)
TRACE pal_nrf::heap > alloc 512 bytes (33064 free)
TRACE pal_nrf::heap > alloc 512 bytes (32552 free)
TRACE pal_nrf::heap > alloc 512 bytes (32040 free)
TRACE pal_nrf::heap > alloc 512 bytes (31528 free)
TRACE pal_nrf::heap > alloc 512 bytes (31016 free)
TRACE pal_nrf::heap > alloc 512 bytes (30504 free)
TRACE pal_nrf::heap > alloc 512 bytes (29992 free)
TRACE pal_nrf::heap > alloc 512 bytes (29480 free)
TRACE pal_nrf::heap > alloc 512 bytes (28968 free)
TRACE pal_nrf::heap > alloc 512 bytes (28456 free)
TRACE pal_nrf::heap > alloc 512 bytes (27944 free)
TRACE pal_nrf::heap > alloc 512 bytes (27432 free)
TRACE pal_nrf::heap > alloc 512 bytes (26920 free)
TRACE pal_nrf::heap > alloc 256 bytes (26408 free)
TRACE pal_nrf::heap > alloc 256 bytes (26152 free)
TRACE pal_nrf::heap > alloc 512 bytes (25896 free)
TRACE pal_nrf::heap > free 256 bytes (25384 free)
TRACE pal_nrf::heap > alloc 512 bytes (25640 free)
TRACE pal_nrf::heap > free 256 bytes (25128 free)
TRACE pal_nrf::heap > free 512 bytes (25384 free)
TRACE pal_nrf::heap > free 512 bytes (25896 free)
TRACE pal_nrf::heap > free 512 bytes (26408 free)
TRACE pal_nrf::heap > free 512 bytes (26920 free)
TRACE pal_nrf::heap > free 512 bytes (27432 free)
TRACE pal_nrf::heap > free 512 bytes (27944 free)
TRACE pal_nrf::heap > free 512 bytes (28456 free)
TRACE pal_nrf::heap > free 512 bytes (28968 free)
TRACE pal_nrf::heap > free 512 bytes (29480 free)
TRACE pal_nrf::heap > free 512 bytes (29992 free)
TRACE pal_nrf::heap > free 512 bytes (30504 free)
TRACE pal_nrf::heap > free 512 bytes (31016 free)
TRACE pal_nrf::heap > free 512 bytes (31528 free)
TRACE pal_nrf::heap > free 512 bytes (32040 free)
TRACE pal_nrf::heap > free 512 bytes (32552 free)
TRACE pal_nrf::heap > free 512 bytes (33064 free)
TRACE pal_nrf::heap > free 512 bytes (33576 free)
TRACE pal_nrf::heap > free 768 bytes (34088 free)
TRACE pal_nrf::heap > free 256 bytes (34856 free)
TRACE pal_nrf::heap > free 256 bytes (35112 free)
TRACE pal_nrf::heap > free 272 bytes (33528 free)
TRACE pal_nrf::heap > alloc 272 bytes (33800 free)
TRACE pal_nrf::heap > free 272 bytes (33528 free)
TRACE pal_nrf::heap > alloc 272 bytes (33800 free)
TRACE pal_nrf::heap > alloc 4 bytes (33528 free)
TRACE pal_nrf::heap > free 4 bytes (33520 free)
TRACE pal_nrf::heap > free 272 bytes (33528 free)
TRACE pal_nrf::heap > alloc 272 bytes (33800 free)
TRACE pal_nrf::heap > free 272 bytes (33528 free)
TRACE pal_nrf::heap > alloc 272 bytes (33800 free)
TRACE pal_nrf::heap > free 272 bytes (33528 free)
TRACE pal_nrf::heap > alloc 272 bytes (33800 free)
TRACE pal_nrf::heap > free 272 bytes (33528 free)
TRACE pal_nrf::heap > alloc 272 bytes (33800 free)
TRACE pal_nrf::heap > free 272 bytes (33528 free)
TRACE pal_nrf::heap > alloc 272 bytes (33800 free)
TRACE pal_nrf::heap > free 272 bytes (33528 free)
TRACE pal_nrf::heap > alloc 512 bytes (34088 free)
TRACE pal_nrf::heap > alloc 512 bytes (33576 free)
TRACE pal_nrf::heap > alloc 512 bytes (33064 free)
TRACE pal_nrf::heap > alloc 512 bytes (32552 free)
TRACE pal_nrf::heap > alloc 512 bytes (32040 free)
TRACE pal_nrf::heap > alloc 512 bytes (31528 free)
TRACE pal_nrf::heap > alloc 512 bytes (31016 free)
TRACE pal_nrf::heap > alloc 512 bytes (30504 free)
TRACE pal_nrf::heap > alloc 512 bytes (29992 free)
TRACE pal_nrf::heap > alloc 512 bytes (29480 free)
TRACE pal_nrf::heap > alloc 512 bytes (28968 free)
TRACE pal_nrf::heap > alloc 512 bytes (28456 free)
TRACE pal_nrf::heap > alloc 512 bytes (27944 free)
TRACE pal_nrf::heap > alloc 512 bytes (27432 free)
TRACE pal_nrf::heap > alloc 512 bytes (26920 free)
TRACE pal_nrf::heap > alloc 256 bytes (26408 free)
TRACE pal_nrf::heap > alloc 256 bytes (26152 free)
TRACE pal_nrf::heap > alloc 512 bytes (25896 free)
TRACE pal_nrf::heap > free 256 bytes (25384 free)
TRACE pal_nrf::heap > alloc 512 bytes (25640 free)
TRACE pal_nrf::heap > free 256 bytes (25128 free)
TRACE pal_nrf::heap > free 512 bytes (25384 free)
TRACE pal_nrf::heap > free 512 bytes (25896 free)
TRACE pal_nrf::heap > free 512 bytes (26408 free)
TRACE pal_nrf::heap > free 512 bytes (26920 free)
TRACE pal_nrf::heap > free 512 bytes (27432 free)
TRACE pal_nrf::heap > free 512 bytes (27944 free)
TRACE pal_nrf::heap > free 512 bytes (28456 free)
TRACE pal_nrf::heap > free 512 bytes (28968 free)
TRACE pal_nrf::heap > free 512 bytes (29480 free)
TRACE pal_nrf::heap > free 512 bytes (29992 free)
TRACE pal_nrf::heap > free 512 bytes (30504 free)
TRACE pal_nrf::heap > free 512 bytes (31016 free)
TRACE pal_nrf::heap > free 512 bytes (31528 free)
TRACE pal_nrf::heap > free 512 bytes (32040 free)
TRACE pal_nrf::heap > free 512 bytes (32552 free)
TRACE pal_nrf::heap > free 512 bytes (33064 free)
TRACE pal_nrf::heap > free 512 bytes (33576 free)
TRACE pal_nrf::heap > free 768 bytes (34088 free)
TRACE pal_nrf::heap > free 256 bytes (34856 free)
TRACE pal_nrf::heap > free 256 bytes (35112 free)
TRACE pal_nrf::heap > alloc 224 bytes (38148 free)
TRACE pal_nrf::heap > alloc 48 bytes (37924 free)
TRACE pal_nrf::heap > alloc 224 bytes (37876 free)
TRACE pal_nrf::heap > alloc 256 bytes (35404 free)
TRACE pal_nrf::heap > alloc 256 bytes (35148 free)
TRACE pal_nrf::heap > free 256 bytes (34892 free)
TRACE pal_nrf::heap > alloc 256 bytes (35148 free)
TRACE pal_nrf::heap > alloc 4 bytes (34892 free)
TRACE pal_nrf::heap > free 4 bytes (34884 free)
TRACE pal_nrf::heap > alloc 528 bytes (34892 free)
TRACE pal_nrf::heap > alloc 1024 bytes (34364 free)
TRACE pal_nrf::heap > alloc 256 bytes (33340 free)
TRACE pal_nrf::heap > alloc 272 bytes (33084 free)
TRACE pal_nrf::heap > alloc 264 bytes (32812 free)
TRACE pal_nrf::heap > free 264 bytes (32548 free)
TRACE pal_nrf::heap > alloc 272 bytes (32812 free)
TRACE pal_nrf::heap > free 272 bytes (32540 free)
TRACE pal_nrf::heap > alloc 272 bytes (32812 free)
TRACE pal_nrf::heap > alloc 4 bytes (32540 free)
TRACE pal_nrf::heap > free 4 bytes (32532 free)
TRACE pal_nrf::heap > free 272 bytes (32540 free)
TRACE pal_nrf::heap > alloc 272 bytes (32812 free)
TRACE pal_nrf::heap > alloc 4 bytes (32540 free)
TRACE pal_nrf::heap > free 4 bytes (32532 free)
TRACE pal_nrf::heap > alloc 512 bytes (32076 free)
TRACE pal_nrf::heap > alloc 512 bytes (31564 free)
TRACE pal_nrf::heap > alloc 512 bytes (31052 free)
TRACE pal_nrf::heap > alloc 512 bytes (30540 free)
TRACE pal_nrf::heap > alloc 512 bytes (30028 free)
TRACE pal_nrf::heap > alloc 512 bytes (29516 free)
TRACE pal_nrf::heap > alloc 512 bytes (29004 free)
TRACE pal_nrf::heap > alloc 512 bytes (28492 free)
TRACE pal_nrf::heap > alloc 512 bytes (27980 free)
TRACE pal_nrf::heap > alloc 512 bytes (27468 free)
TRACE pal_nrf::heap > alloc 512 bytes (26956 free)
TRACE pal_nrf::heap > alloc 512 bytes (26444 free)
TRACE pal_nrf::heap > alloc 512 bytes (25932 free)
TRACE pal_nrf::heap > alloc 256 bytes (25420 free)
TRACE pal_nrf::heap > alloc 256 bytes (25164 free)
TRACE pal_nrf::heap > alloc 512 bytes (24908 free)
TRACE pal_nrf::heap > free 256 bytes (24396 free)
TRACE pal_nrf::heap > alloc 512 bytes (24652 free)
TRACE pal_nrf::heap > free 256 bytes (24140 free)
TRACE pal_nrf::heap > free 512 bytes (24396 free)
TRACE pal_nrf::heap > free 512 bytes (24908 free)
TRACE pal_nrf::heap > free 512 bytes (25420 free)
TRACE pal_nrf::heap > free 512 bytes (25932 free)
TRACE pal_nrf::heap > free 512 bytes (26444 free)
TRACE pal_nrf::heap > free 512 bytes (26956 free)
TRACE pal_nrf::heap > free 512 bytes (27468 free)
TRACE pal_nrf::heap > free 512 bytes (27980 free)
TRACE pal_nrf::heap > free 512 bytes (28492 free)
TRACE pal_nrf::heap > free 512 bytes (29004 free)
TRACE pal_nrf::heap > free 512 bytes (29516 free)
TRACE pal_nrf::heap > free 512 bytes (30028 free)
TRACE pal_nrf::heap > free 512 bytes (30540 free)
TRACE pal_nrf::heap > free 512 bytes (31052 free)
TRACE pal_nrf::heap > free 512 bytes (31564 free)
TRACE pal_nrf::heap > free 512 bytes (32076 free)
TRACE pal_nrf::heap > free 512 bytes (32588 free)
TRACE pal_nrf::heap > free 768 bytes (33100 free)
TRACE pal_nrf::heap > free 256 bytes (33868 free)
TRACE pal_nrf::heap > free 256 bytes (34124 free)
TRACE pal_nrf::heap > alloc 224 bytes (33996 free)
TRACE pal_nrf::heap > alloc 208 bytes (33772 free)
TRACE pal_nrf::heap > alloc 392 bytes (33564 free)
TRACE pal_nrf::heap > alloc 256 bytes (33172 free)
TRACE pal_nrf::heap > alloc 256 bytes (32916 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > free 272 bytes (30052 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > free 272 bytes (30052 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > free 272 bytes (30052 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > free 272 bytes (30052 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > free 272 bytes (30052 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > free 272 bytes (30052 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > free 272 bytes (30052 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > free 272 bytes (30052 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > alloc 512 bytes (29588 free)
TRACE pal_nrf::heap > alloc 512 bytes (29076 free)
TRACE pal_nrf::heap > alloc 512 bytes (28564 free)
TRACE pal_nrf::heap > alloc 512 bytes (28052 free)
TRACE pal_nrf::heap > alloc 512 bytes (27540 free)
TRACE pal_nrf::heap > alloc 512 bytes (27028 free)
TRACE pal_nrf::heap > alloc 512 bytes (26516 free)
TRACE pal_nrf::heap > alloc 512 bytes (26004 free)
TRACE pal_nrf::heap > alloc 512 bytes (25492 free)
TRACE pal_nrf::heap > alloc 512 bytes (24980 free)
TRACE pal_nrf::heap > alloc 512 bytes (24468 free)
TRACE pal_nrf::heap > alloc 512 bytes (23956 free)
TRACE pal_nrf::heap > alloc 512 bytes (23444 free)
TRACE pal_nrf::heap > alloc 256 bytes (22932 free)
TRACE pal_nrf::heap > alloc 256 bytes (22676 free)
TRACE pal_nrf::heap > alloc 512 bytes (22420 free)
TRACE pal_nrf::heap > free 256 bytes (21908 free)
TRACE pal_nrf::heap > alloc 512 bytes (22164 free)
TRACE pal_nrf::heap > free 256 bytes (21652 free)
TRACE pal_nrf::heap > free 512 bytes (21908 free)
TRACE pal_nrf::heap > free 512 bytes (22420 free)
TRACE pal_nrf::heap > free 512 bytes (22932 free)
TRACE pal_nrf::heap > free 512 bytes (23444 free)
TRACE pal_nrf::heap > free 512 bytes (23956 free)
TRACE pal_nrf::heap > free 512 bytes (24468 free)
TRACE pal_nrf::heap > free 512 bytes (24980 free)
TRACE pal_nrf::heap > free 512 bytes (25492 free)
TRACE pal_nrf::heap > free 512 bytes (26004 free)
TRACE pal_nrf::heap > free 512 bytes (26516 free)
TRACE pal_nrf::heap > free 512 bytes (27028 free)
TRACE pal_nrf::heap > free 512 bytes (27540 free)
TRACE pal_nrf::heap > free 512 bytes (28052 free)
TRACE pal_nrf::heap > free 512 bytes (28564 free)
TRACE pal_nrf::heap > free 512 bytes (29076 free)
TRACE pal_nrf::heap > free 512 bytes (29588 free)
TRACE pal_nrf::heap > free 512 bytes (30100 free)
TRACE pal_nrf::heap > free 768 bytes (30612 free)
TRACE pal_nrf::heap > free 256 bytes (31380 free)
TRACE pal_nrf::heap > free 256 bytes (31636 free)
TRACE pal_nrf::heap > alloc 256 bytes (33172 free)
TRACE pal_nrf::heap > alloc 256 bytes (32916 free)
TRACE pal_nrf::heap > free 272 bytes (30052 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > free 272 bytes (30052 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > free 272 bytes (30052 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > free 272 bytes (30052 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > free 272 bytes (30052 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > free 272 bytes (30052 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > free 272 bytes (30052 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > alloc 4 bytes (30052 free)
TRACE pal_nrf::heap > free 4 bytes (30044 free)
TRACE pal_nrf::heap > free 272 bytes (30052 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > free 272 bytes (30052 free)
TRACE pal_nrf::heap > alloc 272 bytes (30324 free)
TRACE pal_nrf::heap > alloc 512 bytes (29076 free)
TRACE pal_nrf::heap > alloc 512 bytes (28564 free)
TRACE pal_nrf::heap > alloc 512 bytes (28052 free)
TRACE pal_nrf::heap > alloc 512 bytes (27540 free)
TRACE pal_nrf::heap > alloc 512 bytes (27028 free)
TRACE pal_nrf::heap > alloc 512 bytes (26516 free)
TRACE pal_nrf::heap > alloc 512 bytes (26004 free)
TRACE pal_nrf::heap > alloc 512 bytes (25492 free)
TRACE pal_nrf::heap > alloc 512 bytes (24980 free)
TRACE pal_nrf::heap > alloc 512 bytes (24468 free)
TRACE pal_nrf::heap > alloc 512 bytes (23956 free)
TRACE pal_nrf::heap > alloc 512 bytes (23444 free)
TRACE pal_nrf::heap > alloc 256 bytes (22932 free)
TRACE pal_nrf::heap > alloc 256 bytes (22676 free)
TRACE pal_nrf::heap > alloc 512 bytes (22420 free)
TRACE pal_nrf::heap > free 256 bytes (21908 free)
TRACE pal_nrf::heap > alloc 512 bytes (22164 free)
TRACE pal_nrf::heap > free 256 bytes (21652 free)
TRACE pal_nrf::heap > free 512 bytes (21908 free)
TRACE pal_nrf::heap > free 512 bytes (22420 free)
TRACE pal_nrf::heap > free 512 bytes (22932 free)
TRACE pal_nrf::heap > free 512 bytes (23444 free)
TRACE pal_nrf::heap > free 512 bytes (23956 free)
TRACE pal_nrf::heap > free 512 bytes (24468 free)
TRACE pal_nrf::heap > free 512 bytes (24980 free)
TRACE pal_nrf::heap > free 512 bytes (25492 free)
TRACE pal_nrf::heap > free 512 bytes (26004 free)
TRACE pal_nrf::heap > free 512 bytes (26516 free)
TRACE pal_nrf::heap > free 512 bytes (27028 free)
TRACE pal_nrf::heap > free 512 bytes (27540 free)
TRACE pal_nrf::heap > free 512 bytes (28052 free)
TRACE pal_nrf::heap > free 512 bytes (28564 free)
TRACE pal_nrf::heap > free 512 bytes (29076 free)
TRACE pal_nrf::heap > free 512 bytes (29588 free)
TRACE pal_nrf::heap > free 512 bytes (30100 free)
TRACE pal_nrf::heap > free 768 bytes (30612 free)
TRACE pal_nrf::heap > free 256 bytes (31380 free)
TRACE pal_nrf::heap > free 256 bytes (31636 free)
DEBUG fobnail::util::crypto > key "token" not found
INFO fobnail::server::token_provisioning > Generating new Ed25519 keypair
TRACE pal_nrf::heap > alloc 10 bytes (34796 free)
TRACE pal_nrf::heap > free 10 bytes (34784 free)
TRACE pal_nrf::heap > alloc 16 bytes (34796 free)
TRACE pal_nrf::heap > alloc 224 bytes (34780 free)
Hole size: 8
Hole size: 8
Hole size: 8
Hole size: 52
Hole size: 24
Hole size: 0
=== PANIC ===

[DemiMarie]

There are three different concerns I can think of, only one of which relates to the actual allocator. (Disclaimer: I have never worked on an embedded system; this is my understanding of the various stuff I have read about.)

1. On a memory-constrained embedded device such as Fobnail, heap allocation after initialization should be a last resort. Heap allocation during initialization (before processing any commands from the host) is fine, as the control flow at this point is (barring fatal errors) deterministic. For instance, one could allocate an object for each peripheral and one for the USB state machine. Tools exist for proving bounds on stack usage, provided certain assumptions (such as no indirect calls) are met.
2. If pre-allocating all objects is infeasible, one can e.g. have 256 slots and have the host responsible for allocating objects to the various slots. The device will reject attempts to operate on an object of the wrong type or that does not exist.
3. If a heap allocator is necessary, see https://sqlite.org/malloc.html#nofrag for how to prevent fragmentation.

[arturkow2000]

Some of the libraries we use require Rust's liballoc and heap, notably rsa crate and CoAP server, we also do use liballoc internally for things like string formatting. While rather everything is possible without heap, doing so would require significant amount of work.

If pre-allocating all objects is infeasible, one can e.g. have 256 slots and have the host responsible for allocating objects to the > various slots.

I am thinking of using another allocator (probably simple-chunk-allocator) for some objects in case linked-list-allocator cannot be fixed, or would be to hard to fix.

[DemiMarie]

Some of the libraries we use require Rust's liballoc and heap, notably rsa crate and CoAP server, we also do use liballoc internally for things like string formatting. While rather everything is possible without heap, doing so would require significant amount of work.

It would probably be a good idea, for reliability.

[MaderNoob]

This bug is not a matter of fragmentation, it is a logic bug in the heap implementation which causes memory to be lost. The back padding of a chunk should be stored as part of some chunk header and taken into account when the chunk is deallocated.

[phil-opp]

Thanks a lot for reporting this issue and especially for the example to reproduce it! I agree that this is something we should fix.

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.

I think the easiest solution would be to consider regions that would result in such a small back padding as unsuitable. This way, we should never get any padding that is too small to be stored. It might lead to an earlier heap exhaustion in some edge cases, but that's better than fragmenting the heap further and further by leaking lots of padding bytes.

[MaderNoob]

That sounds like a valid solution.

But if you wish to provide more flexibility with the chunks, you can store a single usize before each heap chunk which holds the size of the chunk, thus when deallocating the chunk you can know its size including the back padding, but this solution would add some complexity to the heap allocator.

[MaderNoob]

I created an alternative memory allocator which solves this problem and provides many more benefits, such as improved performance and memory utilization.

[phil-opp]

I just implemented a fix for this in #71 and created a new v0.10.4 release with it. Please let me know if this fixes your problems.

[phil-opp]

@MaderNoob

I created an alternative memory allocator which solves this problem and provides many more benefits, such as improved performance and memory utilization.

Nice crate! It's great to have more alternatives in this space and the benchmarks look impressive. Do you have docs about your design somewhere?

If you like, feel free submit a PR with your crate to our Rust OSDev newsletter in https://github.com/rust-osdev/homepage/pull/119, I'm sure many people will find it interesting.