Add support for allocation limits on arenas

[Eliasin]

Implements #135

Arenas can optionally keep track of an allocation_limit which is considered when allocating new chunks to an arena.

The limit is only checked in alloc_layout_slow and new_chunk, which means it should have a low performance overhead as the limit is only checked when trying to hit the global allocator.

To further avoid performance concerns, ChunkFooter has been refactored to keep track of the total allocated bytes, allowing Bump::allocated_bytes to avoid performing a walk of the chunk list.

No new new methods were added, and limits must be set after the creation of a Bump arena. Limits can be changed on the fly and are only enforced when attempting to allocate new chunks.

No changes were made to the errors returned by operations like alloc because of backwards compatibility.

I'm new to open source contributions and library development so sorry if there's anything obvious I missed.

[Eliasin]

Hey @fitzgen, just checking in to see if you've had time to review the latest changes? No worries if you're busy though 😃

[Eliasin]

All the comments should be resolved with these commits 😄

[Eliasin]

On an unrelated note, between the time I opened the PR and now I started project selection for my 4th year project in school and am looking at doing work exploring the applications of WASM modules for IoT app development and I noticed that you're a maintainer of wasmtime.

I'll hopefully be working with wasmtime and wit-bindgen for this so I might talk to you later on the bytecode alliance zulip 😄.

[Eliasin]

All the comments should be resolved with these commits 😄

I just have one concern regarding how allocation limits interact with the value for the minimum chunk size allocation. If a limit is set that is below DEFAULT_CHUNK_SIZE_WITHOUT_FOOTER, all allocations will fail because no sizes will be considered that are below it.

Should set_allocation_limit become fallible to warn about this case? Or should a note be left in the documentation for allocation limits?

Useful documentation notes might have to effectively make the value of DEFAULT_CHUNK_SIZE_WITHOUT_FOOTER public, but because of the details of this implementation, any reductions to DEFAULT_CHUNK_SIZE_WITHOUT_FOOTER could be a breaking change anyway.

[fitzgen]

I just have one concern regarding how allocation limits interact with the value for the minimum chunk size allocation. If a limit is set that is below DEFAULT_CHUNK_SIZE_WITHOUT_FOOTER, all allocations will fail because no sizes will be considered that are below it.

Ah this is a good point.

What if we chain on the limit as a size option to new_sizes in this scenario inside alloc_layout_slow:

let sizes = ...;

let sizes = sizes
    .chain(match self.allocation_limit() {
        Some(limit) if limit < DEFAULT_CHUNK_SIZE_WITHOUT_FOOTER
            && self.allocated_bytes() == 0 => Some(limit),
        _ => None,
    });

let new_footer = ...;

And then the existing filter_map and size checking in Bump::new will make this Just Work.

[Eliasin]

I just have one concern regarding how allocation limits interact with the value for the minimum chunk size allocation. If a limit is set that is below DEFAULT_CHUNK_SIZE_WITHOUT_FOOTER, all allocations will fail because no sizes will be considered that are below it.

Ah this is a good point.

What if we chain on the limit as a size option to new_sizes in this scenario inside alloc_layout_slow:

let sizes = ...;

let sizes = sizes
    .chain(match self.allocation_limit() {
        Some(limit) if limit < DEFAULT_CHUNK_SIZE_WITHOUT_FOOTER
            && self.allocated_bytes() == 0 => Some(limit),
        _ => None,
    });

let new_footer = ...;

And then the existing filter_map and size checking in Bump::new will make this Just Work.

This mostly works but my testing finds it interacts badly with the page strategy for small allocations and the addition of memory for the footer, breaking the quickcheck for allocation limits never being exceeded.

To make this work I think that either the size check needs to be moved back into new_chunk or the logic for deciding the final layout of the allocated chunk needs to be factored out so it can be used as the size check in alloc_layout_slow.

I think this was technically a problem before the above change and was just masked by how the rounding + overhead + footer size adjustment is not significant for larger limits.

This does have it's own problems though as if the check is just moved around the issue changes from happening when trying to allocate less than DEFAULT_CHUNK_SIZE_WITHOUT_FOOTER to happening when trying to allocate less than some amount which would be rounded up + overhead to over the limit, meaning it might be unclear to the end user why an allocation failed even though there is technically room before hitting the limit.

One way to work around this is to stipulate that the limit can be exceeded by some margin that covers the adjustment that new_chunk makes to requests. From what I can see, the max that new_chunk can decide to allocate over the requested size is 0x1000 - 1 - OVERHEAD when rounding large allocations to a page boundary, this margin of error may be unacceptably large though.

[Eliasin]

@fitzgen Since I'm not sure if plain comments trigger notifications

[Eliasin]

I took a stab at fixing this problem by factoring out the logic for determining the final size of chunk allocations so that the code in alloc_layout_slow could determine the exact size of a new allocated chunk. This fixes breaking the limit because of the difference in allocation request size and the final size.

I also allowed the chunk size halving process to go below the min chunk size when dealing with small limits as just requesting a chunk with the limit value usually rounds up past the limit and ends up being rejected.

[Eliasin]

I'm realizing now that this change causes some memory details about the new chunks to be calculated twice in a lot of cases so I'll make a change to avoid that now.

[Eliasin]

I'm realizing now that this change causes some memory details about the new chunks to be calculated twice in a lot of cases so I'll make a change to avoid that now.

I've made the change to cache the new chunk memory details so that they are not calculated twice but this necessitated a change in new_chunk, marking it as unsafe because of it no longer can verify (without recalculating and defeating the point) the safety of the new chunk memory details passed to it.

I'm not sure if that's an acceptable change and I'm not a fan of the name I have NewChunkMemoryDetails but I wanted to get a solution out and see what your opinion is.

[fitzgen]

https://github.com/fitzgen/bumpalo/runs/7239112120?check_suite_focus=true#step:5:126

Looks like abs_diff wasn't introduced until Rust 1.60, and our MSRV is 1.50. Mind open coding abs_diff here?

[Eliasin]

@fitzgen Should be good now, I ran the tests on 1.54.0

[fitzgen]

Looks like CI is still failing:

https://github.com/fitzgen/bumpalo/runs/7286188380?check_suite_focus=true#step:5:342

failures:
---- oom_instead_of_bump_pointer_overflow stdout ----
Layout::from_size_align errored: invalid parameters to Layout::from_size_align
note: test did not panic as expected
error: test failed, to rerun pass '--test tests'
failures:
    oom_instead_of_bump_pointer_overflow

[Eliasin]

Looks like CI is still failing:

https://github.com/fitzgen/bumpalo/runs/7286188380?check_suite_focus=true#step:5:342

failures:
---- oom_instead_of_bump_pointer_overflow stdout ----
Layout::from_size_align errored: invalid parameters to Layout::from_size_align
note: test did not panic as expected
error: test failed, to rerun pass '--test tests'
failures:
    oom_instead_of_bump_pointer_overflow

@fitzgen I think this might be a nightly breakage as I ran this test on upstream main with nightly and experienced a failure

[Eliasin]

Looks like CI is still failing: https://github.com/fitzgen/bumpalo/runs/7286188380?check_suite_focus=true#step:5:342

failures:
---- oom_instead_of_bump_pointer_overflow stdout ----
Layout::from_size_align errored: invalid parameters to Layout::from_size_align
note: test did not panic as expected
error: test failed, to rerun pass '--test tests'
failures:
    oom_instead_of_bump_pointer_overflow

@fitzgen I think this might be a nightly breakage as I ran this test on upstream main with nightly and experienced a failure

The test passes on this PR and upstream main on the nightly of July 10th 2022 but not July 11th 2022, which is today

[Eliasin]

Toying with the latest nightly it seems that Layout::size_from_align panics with a lot of values that stable won't with. Namely values of size near usize::MAX. I'm not sure if this constitutes a nightly regression or where to even report something like this though

[Eliasin]

I asked on the rust zulip and it seems like there is a new requirement for Layout::from_size_align that the size value must fit in an isize from this PR which the nightly docs now show so the test will have to be changed

[Eliasin]

I made an issue for the breakage with a tentative suggested change

[Eliasin]

Hey @fitzgen , just pinging in case this slipped by your email 😃

[fitzgen]

I don't have time to look into the old tests at the moment, if you can get them passing and send a PR then I can review that.

[fitzgen]

I think this should pass CI now if rebased

[Eliasin]

I think this should pass CI now if rebased

Seems like it does!

[fitzgen]

Thanks! And thanks for your patience!

[Eliasin]

I had a great time working on this PR, thanks for your work reviewing it and maintaining this crate! 😄