Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

RawTable::insert_no_grow needs safety checks, or should be unsafe #253

Closed
cuviper opened this issue Mar 29, 2021 · 2 comments · Fixed by #254
Closed

RawTable::insert_no_grow needs safety checks, or should be unsafe #253

cuviper opened this issue Mar 29, 2021 · 2 comments · Fixed by #254

Comments

@cuviper
Copy link
Member

cuviper commented Mar 29, 2021

This program segfaults:

use hashbrown::raw::RawTable;
fn main() {
    let mut table = RawTable::new();
    loop {
        table.insert_no_grow(0, 0);
    }
}

If I change this to have some initial capacity, then in debug mode it panics decrementing growth_left:

thread 'main' panicked at 'attempt to subtract with overflow', /home/jistone/.cargo/registry/src/jackfan.us.kg-1ecc6299db9ec823/hashbrown-0.11.2/src/raw/mod.rs:882:13

In release mode that loops forever. I added debug prints for len/capacity, and that gets up to 16/14 before hanging entirely.

I suppose panic/infinite-loop is somewhat acceptable from a safety perspective, as long as we're sure to do one of those without corrupting memory, but the empty case is definitely a problem. Maybe we should assert the same condition that the regular insert uses when it decides to resize? We could even use/mimic try_insert_no_grow and then panic on error.

@Amanieu
Copy link
Member

Amanieu commented Mar 29, 2021

The main use case for insert_no_grow is to support the Entry type in libstd which isn't parameterized by S. This means that libstd's entry must reserve space when the Entry is created so that it can later call insert_no_grow without a hasher.

Since it is barely used outside hashbrown, I'm happy to switch this function to being unsafe.

@cuviper
Copy link
Member Author

cuviper commented Mar 29, 2021

We do use it in indexmap too, but only when bulk-inserting items where we're sure the capacity is sufficient. I could live with that being unsafe.

bors added a commit that referenced this issue Mar 30, 2021
Make `RawTable::insert_no_grow` unsafe

For performance reasons, this method _assumes_ that there is sufficient
capacity for the new element, and it misbehaves otherwise, breaking
invariants or even segfaulting. The necessary conditions could be
checked, but if we're to keep it lean, it should be `unsafe`, so the
burden is on the caller to ensure capacity.

Fixes #253.
@bors bors closed this as completed in 26f725b Mar 30, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants