rcore-os / rcore-os/buddy_system_allocator
`Heap::add_to_heap` does not coalesce adjacent ranges added in separate calls
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 145
- Forks
- 34
- PR merge metrics
- No merged PRs in 30d
Description
Heap::add_to_heap appears to have the same structural issue as FrameAllocator::add_frame.
It splits the incoming range into buddy-sized blocks and pushes them directly into the free lists, but it does not try to merge newly added buddy blocks.
Relevant code:
src/lib.rs:90-118- direct insertion at
src/lib.rs:112-114 - deallocation merge logic at
src/lib.rs:195-217
As a result, heap allocation behavior depends on whether contiguous memory is added in one call or split across multiple calls.
Reproduction
use buddy_system_allocator::Heap;
use core::alloc::Layout;
#[repr(align(64))]
struct Backing64([u8; 64]);
#[test]
fn heap_should_not_depend_on_how_ranges_are_batched() {
let mut heap = Heap::<7>::new();
let mut backing = Backing64([0; 64]);
let start = backing.0.as_mut_ptr() as usize;
let middle = start + 32;
let end = start + 64;
unsafe {
heap.add_to_heap(start, middle);
heap.add_to_heap(middle, end);
}
let layout = Layout::from_size_align(64, 1).unwrap();
// Currently returns Err(()).
assert!(heap.alloc(layout).is_ok());
}
Why this matters
Heap::add_to_heap is an incremental API, and its current safety contract already requires the added ranges to be valid, writable, and non-overlapping.
If two adjacent, compatible free ranges are added separately, it is surprising that they cannot later be used as one larger buddy block.
In practice this means:
- memory added through
dealloccan be coalesced - memory added through repeated
add_to_heapcalls may stay artificially fragmented
Suggested fix
Use the same approach as for FrameAllocator:
- add an internal helper such as
insert_free_block(ptr, class) - make that helper merge with an existing buddy if present
- reuse it from both
add_to_heapanddealloc
That would make the heap behavior independent of insertion batching and keep the free lists normalized.
If it is confirmed to be a bug, I can submit a PR to help fix it.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with src/lib.rs:90-118, especially the direct free-list insertion at lines 112-114, and compare it with the deallocation merge logic at lines 195-217. Run the provided heap_should_not_depend_on_how_ranges_are_batched reproduction. Done means separately added adjacent ranges can satisfy the 64-byte allocation and existing deallocation behavior remains intact.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- operating-systems
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Quiet
- Clarity
- Clearly specified
- Newbie friendliness
- 72/100