Skip to content

BTree's insert_fit breaks pointer provenance rules #78477

Closed
@RalfJung

Description

@RalfJung

This code violates pointer provenance rules:

    fn insert_fit(&mut self, key: K, val: V) -> *mut V {
        debug_assert!(self.node.len() < CAPACITY);

        unsafe {
            slice_insert(self.node.keys_mut(), self.idx, key);
            slice_insert(self.node.vals_mut(), self.idx, val);
            self.node.as_leaf_mut().len += 1;

            self.node.val_mut_at(self.idx)
        }
    }

Specifically, self.node.keys_mut() returns a slice covering the previously existing elements of this node, but it is used to also access the new element one-past-the-end of the previous slice.

Either slice_insert needs to be passed a slice covering all the memory it needs to access (of type &mut [MaybeUninit<_>]), or else it needs to be passed a raw pointer (that may access the entire buffer) and a length. But keys_mut/vals_mut can only be used to access elements that already exist, not to initialize new elements.

Cc @ssomers

Metadata

Metadata

Assignees

No one assigned

    Labels

    A-collectionsArea: `std::collections`C-bugCategory: This is a bug.I-unsoundIssue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/SoundnessP-mediumMedium priorityT-libsRelevant to the library team, which will review and decide on the PR/issue.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions