Skip to content

FrameAllocator::add_frame does not coalesce adjacent ranges added in separate calls #50

@mevinagrise

Description

@mevinagrise

FrameAllocator::add_frame currently splits [start, end) into power-of-two blocks and inserts them directly into the corresponding free list, but it does not try to merge newly added buddy blocks.

Relevant code:

  • src/frame.rs:53-76
  • direct insertion at src/frame.rs:72
  • deallocation merge logic at src/frame.rs:193-211

This means allocation behavior depends on how free memory is batched.

For example, these two states should be equivalent from the allocator's point of view:

  1. add [0, 4) in one call
  2. add [0, 2) and [2, 4) in two calls

But today they are not equivalent.

Reproduction

use buddy_system_allocator::FrameAllocator;

#[test]
fn frame_allocator_should_coalesce_adjacent_ranges_added_separately() {
    let mut frame = FrameAllocator::<8>::new();

    frame.add_frame(0, 2);
    frame.add_frame(2, 4);

    // Currently returns None.
    assert_eq!(frame.alloc(4), Some(0));
}

Why this matters

This creates artificial fragmentation and makes allocator behavior depend on insertion history instead of the current free set.

If add_frame is intended to support incremental insertion of non-overlapping ranges, then adding adjacent ranges in separate calls should be equivalent to adding their union in one call.

Suggested fix

Introduce a small internal helper for inserting a free block with buddy coalescing, for example:

  • insert_free_block(start_frame, class)

Then reuse that helper from:

  • add_frame
  • dealloc_power_of_two

That would:

  • fix the batching-dependent behavior
  • keep the free lists in a normalized state
  • reduce duplicated free-block insertion logic

If it is confirmed to be a bug, I can submit a PR to help fix it.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions