rcore-os / rcore-os/buddy_system_allocator

`Heap::add_to_heap` does not coalesce adjacent ranges added in separate calls

Open
#51 0 comments 0 reactions 0 assignees View on GitHub

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 dealloc can be coalesced
  • memory added through repeated add_to_heap calls 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_heap and dealloc

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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.