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)
Was thinking the same so I tried with
#[inline(never)]onGroup::load(generic.rs) and it “fixes” the issue. However, it also did “fix” it forGroup::match_byteso maybe it’s just an unlucky side effect, similar to adding debug prints.I realized the issue is currently manifesting itself with this snippet:
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.
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.
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.