ACP: Replace GlobalAlloc::realloc with GlobalAlloc::resize

[CAD97]

Proposal

Problem statement

The GlobalAlloc::realloc function (and the free std::alloc::realloc function) takes a new_size: usize argument. The current documentation of the function requires that

new_size, when rounded up to the nearest multiple of layout.align(), must not overflow (i.e., the rounded value must be less than usize::MAX).

No mention is currently made anywhere in the std::alloc documentation about the fact that rust created allocations are required to be no more than isize::MAX bytes.

Effectively, this means that GlobalAlloc::realloc has an undocumented requirement that new_size (when rounded up) does not exceed isize::MAX (not usize::MAX, as is currently documented). Neither callers nor implementers have been told that this requirement exists.

Experience in the stdlib has shown that even the most highly reviewed Rust code still forgets to manually enforce the isize::MAX limit in edge cases (e.g. rust-lang/rust#95334). For this reason, rust-lang/rust#95295 is currently FCP-merge to automatically enforce that layout sizes respect the isize::MAX limit with Layout.

This ensures that all Rust allocation APIs cannot request an object larger than isize::MAX... except for GlobalAlloc::realloc, which takes a plain usize for the new size, and not a Layout.

Motivation, use-cases

One way or another, GlobalAlloc::realloc needs to be changed so that the correct isize::MAX limit is respected. There are two available solutions that do not change stable API: caller enforced (change the documentation to read isize::MAX) or callee enforced (all GlobalAlloc implementers must check and prevent too-large allocations from succeeding).

A new function which takes Layout is also desirable, as this would realign realloc with the other allocation functions in automatically enforcing the size limit via the Layout type invariants. In addition, by passing a requested new alignment, this enables alignment changing realloc.

Allocators will often serve all allocations with an alignment of at least some minimum alignment. On x86, this is often 8 bytes; on x86_64, 16. So while Rust's allocation APIs strictly require deallocating with the same alignment used to allocate, in practice it's often fine to allocate at low alignment and deallocate at the basic alignment.

An alignment changing realloc allows users to communicate that this is what they are doing to the compiler. By calling an aligning realloc with the correct size and alignment, it is possible to do conversions like Vec<u8> into Vec<u32> without copying and without falling afoul of mismatched alloc/dealloc alignment.

Solution sketches

caller enforced, deprecate, and replace

This is the author's preferred option.

Document that GlobalAlloc::realloc has a safety requirement that the rounded size must not exceed isize::MAX. Implementers may continue to service realloc requests exactly as they come in.

Additionally, deprecate GlobalAlloc::realloc and encourage users to call a replacement function instead:

unsafe fn resize(&self, ptr: *mut u8, old_layout: Layout, new_layout: Layout) -> *mut u8 {
    // like realloc, a default implementation is provided.
    if old_layout.align() == new_layout.align() {
        // when the alignment does not change, call the existing realloc
        self.realloc(ptr, old_layout, new_layout.size())
    } else {
        // otherwise do the fallback new allocation with copy
        let new_ptr = unsafe { self.alloc(new_layout) };
        if !new_ptr.is_null() {
            unsafe {
                ptr::copy_nonoverlapping(ptr, new_ptr, cmp::min(old_layout.size(), new_layout.size()));
                self.dealloc(ptr, old_layout);
            }
        }
        new_ptr
    }
}

A new free function std::alloc::resize is also provided which calls Global::resize, std::alloc::realloc is deprecated in favor of std::alloc::resize, and #[global_allocator] is updated to plumb GlobalAlloc::resize in addition to the existing GlobalAlloc methods.

The System allocator implementation is updated to implement resize where both old and new alignment are below the minimum guaranteed alignment via the system realloc. When either alignment exceeds this, the fallback realloc is used.

Windows implementation

    #[inline]
    unsafe fn resize(&self, ptr: *mut u8, old_layout: Layout, new_layout: Layout) -> *mut u8 {
        if old_layout.align() <= MIN_ALIGN && new_layout.align() <= MIN_ALIGN {
            // SAFETY: because `ptr` has been successfully allocated with this allocator,
            // `HEAP` must have been successfully initialized.
            let heap = unsafe { get_process_heap() };

            // SAFETY: `heap` is a non-null handle returned by `GetProcessHeap`,
            // `ptr` is a pointer to the start of an allocated block.
            // The returned pointer points to the start of an allocated block.
            unsafe { HeapReAlloc(heap, 0, ptr as c::LPVOID, new_layout.size()) as *mut u8 }
        } else {
            // SAFETY: `aligned_realloc_fallback` is implemented using `dealloc` and `alloc`, which will
            // correctly handle `ptr` and return a pointer satisfying the guarantees of `System`
            unsafe { aligned_realloc_fallback(self, ptr, old_layout, new_layout) }
        }
    }

Possible alternative names to resize include aligned_realloc, realloc_s, and realign. Alternatively, separate grow/shrink could be provided, as is done in the Allocator trait.

Why provide a new GlobalAlloc function?

Allocator stabilizing is still a distant future thing, as at a minimum it is blocked on fixing MIR to not treat Box as a primitive pointer when it contains an allocator. Providing a new GlobalAlloc function is a lower effort solution which still takes the burden of remembering to check the size limit off of callers. The ability to change the alignment at the same time is an additional bonus, but not a core motivator for providing the new API.

Unfortunately, the result of forgetting to check the size limit and allocating an object of more than isize::MAX bytes is likely to appear to just work. This is a subtle soundness hole, and one reasonably unlikely to hit miscompilations... until it does, likely resulting in some completely inscrutable failure far removed from the actual problem.

caller enforced

Document that GlobalAlloc::realloc has a safety requirement that the rounded size must not exceed isize::MAX. Implementers may continue to service realloc requests exactly as they come in.

Eventually, GlobalAlloc will be deprecated in favor of the Allocator trait, and #[global_allocator] will also be redefined to work on Allocator instead of GlobalAlloc. At this point, reallocation will take a new Layout and automatically enforce the isize::MAX limit.

Until that point, callers of realloc will need to manually enforce that the rounded size does not exceed isize::MAX.

callee enforced

Document that GlobalAlloc::realloc must be implemented to fail to allocate more than isize::MAX bytes.

Instead of putting the burden on developers calling the raw allocation functions, we instead tell roughly every GlobalAlloc implementer (that doesn't just wrap another implementer) that oops! they're actually subtly unsound. At least the cost of checking the limit is minimized, since the allocator necessarily is already checking the size... except no, not really; any GlobalAlloc which calls an existing allocator which does not guarantee that allocations of more than isize::MAX bytes fail will have to separately check that limit before calling into the actual allocator implementation.

Eventually, GlobalAlloc will be deprecated in favor of the Allocator trait, and #[global_allocator] will also be redefined to work on Allocator instead of GlobalAlloc. At this point, reallocation will take a new Layout and automatically enforce the isize::MAX limit.

Links and related work

• Zulip discussion about alignment-changing realloc for GlobalAlloc
• wg-alloc issue for providing alignment-changing realloc for GlobalAlloc
• Enforce that layout size fits in isize in Layout rust#95295
• Enforce that layout size fits in isize in Layout rust#95295 (comment): automatically checking the isize::MAX limit in Layout comes almost entirely for free since it already needs to check that usize overflow cannot happen.

What happens now?

This issue is part of the libs-api team API change proposal process. Once this issue is filed the libs-api team will review open proposals in its weekly meeting. You should receive feedback within a week or two.

[joboet]

Why not stabilize just the Allocator trait and its associated types (AllocError and Global) without the whole integration into alloc? That would allow crates like hashbrown to use the trait without workarounds and would solve this issue, while still not forcing a decision on things like the storage API.

[CAD97]

Because we're still not completely certain that Allocator has the right shape. There's at the moment at least three open questions:

• The trait needs to discuss whether and when allocations outlive the allocator, and this is somewhat subtle. Relax Allocator bounds into pin-safe trait rust#94114
• impl Allocator for &impl Allocator is potentially more of a footgun than a benefit. 'unsafe impl<A> Allocator for &A where A: Allocator' is problematic rust#98232
• It's unclear if returning excess size is actually a benefit; e.g. jemallocator can't provide it without extra overhead and none of std collections take advantage of it because doing so has pessimised the common case. (no link, sorry)

[thomcc]

A month or so ago I wrote https://hackmd.io/ld8wv8kHQaKF_YsU6r8CKQ?view about my experience trying to use the Allocator trait in anger in my game engine over a year ago. The experience made me feel that the current design needs more work and should take inspiration from the RawWaker design, perhaps.

It's rough and I've been meaning to clean it up, but since it's being discussed I may as well just drop the link.

It's unclear if returning excess size is actually a benefit

It should be a separate API, IMO. I think I've filed issues to this effect in this the alloc-wg repository.

[Amanieu]

We discussed this in the libs meeting and decided that simply updating the requirements in the documentation as proposed in rust-lang/rust#108630 is the best way forward for GlobalAlloc. Adding a new method would cause too much churn and we plan on deprecating GlobalAlloc to replace it with Allocator everywhere.