hashbrown: Infinite loop

A very simple snippet lands on an infinite loop in some environment it seems:

    let left: u64 = 1;
    let right: u64 = 1;
    let mut myhash = HashMap::new();
    myhash.insert(left, right);

This works everywhere except in a very specific place: in a kernel module of Android 6.1 kernel (Pixel 6 device), compiled in release mode:

  • This does not use the Rust for Linux support
  • The code is compiled as a no_std staticlib, prelinked and then provided to the kernel build system as a standalone object file.
  • The global allocator is a straightforward wiring of the GlobalAllocator trait to kmalloc/kfree kernel functions.
  • In debug mode, everything is working fine, it only breaks in release.
  • The symptom is a hard lockup of the CPU running the code.

Unfortunately, I was not able to get a useful backtrace out of the kernel for whatever reason, which is a real shame

EDIT: added no_std

About this issue

  • Original URL
  • State: open
  • Created 2 years ago
  • Comments: 39 (17 by maintainers)

Most upvoted comments

Was thinking the same so I tried with #[inline(never)] on Group::load (generic.rs) and it “fixes” the issue. However, it also did “fix” it for Group::match_byte so maybe it’s just an unlucky side effect, similar to adding debug prints.

You could also add an assert to check that all bits are set in the bitmask returned by match_empty since the table should be completely empty at this point.

In fact can you also add an assert that the group load returns 0x8080808080808080 (top bit set in each byte).

I realized the issue is currently manifesting itself with this snippet:

    let mut mymap = hashbrown::HashMap::new();
    mymap.insert(left, right);
    let val = mymap.get(&left).unwrap();

and it’s looping in mymap.get(). When I opened the issue, this get() was not necessary, but maybe it “became necessary” after adding some debug prints. Would your invariants still hold then ?

Considering the extra assert added in the allocator did not fire, it seems pretty likely the issue is somewhere in hashbrown. I’m happy to try alternative branches with extra asserts etc to help figuring that issue but for now I don’t have any code actually depending on hashbrown (it was preliminary tests), so I’m going to go with the std BTreeMap since it’s fine too for the use case.

The global allocator is a straightforward wiring of the GlobalAllocator trait to kmalloc/kfree kernel functions.

Are you absolutely sure that the pointer returned by the allocator is correctly aligned? This is a problem that several people have encountered when using custom allocators. It might be worth dropping an assert there to be sure.

To be honest, I’m not entirely a fan of the way we currently do the probe sequence, since like you’re experiencing, it doesn’t have any guarantee to end. This means that a potentially malicious hash or a bad implementation could lead to an infinite loop.

Because the table is a power of 2, a quadratic probe sequence is guaranteed to visit each group exactly once before looping. The loop is then guaranteed to terminate as long as there is at least one empty bucket, which is guaranteed by the load factor. The hash only selects the starting position, all groups are still visited.