`BitmapPageAllocator::init` assertion fails in default feature settings

[WIZeaz]

Hi! I believe I have found a problem in BitmapPageAllocator. To reproduce the problem, use the following code snippet and compile it with default feature settings.

fn test_alloc(){
        let mut allocator = BitmapPageAllocator::<4096>::new();
        let size = 256 * 1024 * 1024; // 256 MB size
        let start_addr = 40960; // can be any non-zero addr
        allocator.init(start_addr, size); // assertion failed: end <= Self::CAP
}

I believe it is a bug, because it is the normal behavior that the allocatable address index is not started from zero (zero means null, so it causes a lot of trouble).

I have investigated the reason for this bug. It turns out that the BitmapPageAllocator::inner only reserves the exact capacity of 256 MB (the maximum supported allocatable memory in default feature settings). It assumes the index of allocatable pages is started from zero. However, in BitmapPageAllocator::init, the start index of allocatable pages is calculated by start - self.base, where self.base is aligned down to 1GB. This creates an empty index before the index of the first allocatable page and causes an assertion failure.

To address the bug, I think the implementation should either add an alignment requirement for the start address or modify the way the start index is calculated.

[equation314]

This issue is not reproduced for me, and I'm unsure of the cause you described. Could you provide more detailed instructions on how to reproduce it?

[WIZeaz]

Sure. I think the reason you cannot reproduce the issue may be related to how the test is set up. If you are trying to reproduce it with a unit test inside this crate, you need to change
src/bitmap.rs:12 from

    type BitAllocUsed = bitmap_allocator::BitAlloc1M;

to

    type BitAllocUsed = bitmap_allocator::BitAlloc64K;

Otherwise, the capacity of BitmapPageAllocator::inner is large enough, and the assertion will not be triggered.

Alternatively, you can reproduce the issue by creating an empty Cargo project and using the following code:

use allocator::{BaseAllocator, BitmapPageAllocator};
fn main() {
    let mut allocator = BitmapPageAllocator::<4096>::new();
    let size = 256 * 1024 * 1024; // 256 MB
    let start_addr = 40960; // can be any non-zero addr
    allocator.init(start_addr, size); // assertion failed: end <= Self::CAP
}

with cargo.toml:

[package]
 # default package config 

[dependencies]
allocator = { git = "https://github.com/arceos-org/allocator.git", features = ["bitmap"] }

I have tested both approaches locally, and they reproduce the issue as expected.

[equation314]

@WIZeaz This is expected behavior. Due to the alignment requirements of alloc_pages_at, the base address needs to be aligned to the largest possible size. Therefore, an unused region is left before start, causing the end index to exceed the CAP. It's not trivial to improve this algorithm.

#10 does not change the logic but provides more detailed panic information in this case, reminding users to use a larger bitmap.

[WIZeaz]

Thanks for the explanation. If the algorithm can't be improved further, adding an explicit alignment requirement seems like a reasonable way to address this.

Would you be open to adding that requirement to the doc comment? I’m happy to put together a PR if that works for you.

One remaining question: why is self.base aligned down to 1 GB? If type BitAllocUsed = bitmap_allocator::BitAlloc64K, could we instead use a 256 MB alignment?