Skip to content

Allocators in BTreeMap and BTreeSet need more work #161678

Description

@maxdexh

In #157428, we banned allocators from unwinding out of their drop to fix #159334 and its related issues. We also introduced AllocatorClone to fix #156920. However, the btree module currently uses Allocator + Clone bounds instead of AllocatorClone, which is now completely unsound because there is no longer any safety requirement related to clone correctness.

We do not plan to stabilize this code anytime soon and it has its own nightly feature (btreemap_alloc), but it would still be nice if we didn't have such blatantly unsound code in std.
Short-term, we can just replace all Allocator + Clone bounds with AllocatorClone.

Long-term, we may want to consider whether it is a good idea to be cloning the allocator here at all.
The cloning here could all be done by reference, but it was discovered that doing this led to regressions with ZST allocators (like the most important allocator, Global), due to needless passing around of the reference, which LLVM fails to optimize away due to the complex usage pattern (and storage of the reference in the Entry structs that is impossible to optimize away).

We should probably come up with another solution that allows ZSTs to be passed by-value, while expensive-to-clone allocators can be passed by reference, perhaps through some kind of unsafe trait AllocatorShare { type Share<'a>: Allocator; fn share_alloc(&self) -> Self::Share<'_>; }. This would also allow something like Box<Arc<&Arc<A>>> to be passed around as A::Share, since it can defer recursively.

@rustbot label A-allocators requires-nightly I-unsound A-collections

Metadata

Metadata

Assignees

No one assigned

    Labels

    A-allocatorsArea: Custom and system allocatorsA-collectionsArea: `std::collections`C-bugCategory: This is a bug.I-unsoundIssue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/SoundnessT-libsRelevant to the library team, which will review and decide on the PR/issue.requires-nightlyThis issue requires a nightly compiler in some way. When possible, use a F-* label instead.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions