Infinite loop

[douglas-raillard-arm]

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

[clarfonthey]

That is very peculiar. Are you sure that it's not just the allocation itself that's failing? I.e., does HashMap::with_capacity(1) not give the same error?

Since by default, HashMap::new doesn't allocate any memory, and so it wouldn't be calling those allocator functions until the insert call.

[douglas-raillard-arm]

The allocation itself succeeds (I can log the allocated pointer from kmalloc easily), so it's not that, but the part that actually fails is indeed the insert(). HashMap::new() on its own is fine.

[douglas-raillard-arm]

Is there any trick based on using unused pointer bits in hashbrown ? The addresses range used in kernel space is different from the one in userspace AFAIR. Other than that, it should be a run-of-the-mill no_std environment.

[clarfonthey]

The stored pointer isn't at the beginning of the allocation, but other than that, it shouldn't affect things. The empty map is stored as static data, but since you got to the allocation, that shouldn't have been the source of the issue, since the code would have read the data before that point.

Since you have the ability to log the pointer allocation, I'd honestly recommend just trying to build the crate yourself and injecting logging statements to debug things if you can, since that'd be the best way to figure out what the actual issue is. Besides that, there really isn't much to go on since this feels pretty specific to your issue.

[Amanieu]

This is almost certainly due to the use of NEON instructions in hashbrown, which aren't normally allowed in the kernel. Are you using the aarch64-unknown-none-softfloat target which specifically disables the use of FP/SIMD instructions?

[douglas-raillard-arm]

I'll try to add some debug prints when I figured how to make a local version of the crate.

Are you using the aarch64-unknown-none-softfloat target which specifically disables the use of FP/SIMD instructions?

It's using a custom target.json, derived from aarch64-unknown-none-softfloat:

{
  "abi": "softfloat",
  "arch": "aarch64",
  "data-layout": "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128-Fn32",
  "features": "+v8a,+strict-align,-neon,-fp-armv8",
  "llvm-target": "aarch64-unknown-none",
  "max-atomic-width": 128,
  "stack-probes": {
    "kind": "none"
  },
  "target-pointer-width": "64",
  "supported-sanitizers": [
    "kcfi"
  ]
}

So there should not be any NEON instruction in the binary. I haven't checked exhaustively the disassembly though, so maybe it could still sneak-in via intrinsics (?) or asm!().

EDIT: figured how to build my version of hashbrown with debug prints, let's see what happens when I get the pixel 6 back to experiment.

[douglas-raillard-arm]

I managed to find the problematic spot: when a print is added at the beginning of this loop, the issue disappears. So there probably is something unsound somewhere there that is exposed by optimizations (I'm using rust 1.81.0).

EDIT: I also confirm that this is the loop that becomes infinite in the broken case.

[clarfonthey]

Hmm, that is very strange, since we've thoroughly tested this and run it through miri without any undefined behaviour triggering. Since you're running on a target without NEON, you're almost certainly using the generic, not-SIMD implementation (which is also what we run via MIRI), which is very weird.

[clarfonthey]

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.

The one thing that immediately jumps to mind is that we have an explicit test for the target pointer width when factoring in the cache: if the pointer width is 32, then we take bits 31-25 of the hash for the 7-bit control code, whereas if the pointer width is 64, we take bits 63-57. It could be that the hash is still ending up as a 32-bit number and thus the control code is always zero, but since zero is a valid hash, that still feels unlikely.

[Amanieu]

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.

[douglas-raillard-arm]

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.

I'll add some asserts. Currently the code is like that, in which I assume the address will be correctly aligned under this condition:

align <= 8 || (size.is_power_of_two() && align <= size)

This is based on the kernel doc:

The address of a chunk allocated with kmalloc is aligned to at least ARCH_KMALLOC_MINALIGN bytes. For sizes which are a power of two, the alignment is also guaranteed to be at least the respective size. For other sizes, the alignment is guaranteed to be at least the largest power-of-two divisor of the size.

(and on arm64, ARCH_KMALLOC_MINALIGN is 8).

when factoring in the cache [...] whereas if the pointer width is 64, we take bits 63-57

I'm not sure of what you mean here by "factoring in the cache" but those bits will be in use for kernel space pointers on arm64, as can be seen here.

[douglas-raillard-arm]

Assert added and it's still landing on the infinite loop without panicking first.

[Amanieu]

I'm honestly out of ideas at this point. I would recommend setting up kernel debugging to figure out exactly which loop it's getting stuck in.

[douglas-raillard-arm]

@Amanieu that's figured already, see #566 (comment)

[Amanieu]

I mean single-stepping that loop with a debugger to figure out why it's not exiting on the first iteration since there's only one element in the table. match_empty should return at least 1 set bit and cause the loop to exit with None.

[douglas-raillard-arm]

Single stepping is going to be really challenging. Even installing a debugger is going to be a problem (it's Android, not a regular distro with a gdb package). On top of that the binary is mixed language (it's a C kernel module with one object file coming from Rust). I can however apply any patch you want to hashbrown, so if there is things you want me to print and add asserts that's straightforward.

The only thing to keep in mind is that extra printing in the loop leads to the issue disappearing, similarly to compiling with debug, so it's quite likely there is something unsound quite "local" to that spot (or anything inlined there).

The SAFETY comment of that snippet lists 4 points, maybe some of them can be turned into assert!() ?

        let group = unsafe { Group::load(self.ctrl(probe_seq.pos)) };

[douglas-raillard-arm]

I added the following obvious asserts according to SAFETY and they passed fine, with the infinite loop still happening:

            assert_eq!(self.bucket_mask, self.buckets() - 1);
            assert!(probe_seq.pos <= self.bucket_mask);

[Amanieu]

Maybe you could try sprinkling some #[inline(never)] around these functions to figure out which one is causing the issue? That should at least narrow down the issue to a set of functions.

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).

[douglas-raillard-arm]

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.

[Amanieu]

You should still be able to dump the contents of Group::load as hex, which should give us a clue as to what the underlying problem is. I would normally expect all bytes to be 0x80 except for the one byte containing the inserted element. And the loop should still exit after 1 iteration.

[douglas-raillard-arm]

So I tried adding #[derive(Debug)] on struct Group and then print it just after Group::load. This lead to a NULL pointer deref (the address was actually 9, not 0, but it also falls in the guard page). The second time I tried (rebuild), the print did not fire and it got stuck in the infinite loop, despite the print being obviously inside the loop. So codegen is play tricks on us to evade scrutiny, we must be onto something :)

Note that I validated the print itself by printing successfully probe_seq.pos, which was equal to 3. It's using format!() so that brings a String allocation in the loop.

[douglas-raillard-arm]

So there really is something going with the pointer obtained via self.ctrl(probe_seq.pos), which is self.ctrl(3). As soon as this *const u8 is dereferenced into a u64, the printing code is "skipped" and the lockup happens.

[Amanieu]

Could this be because the kernel doesn't support unaligned memory access for some reason?

[douglas-raillard-arm]

Maybe but I'd expect a fault leading to a panic.

The only print thing that has worked is turning the ptr into a slice of length 8 and printing that:

ptr=0xffffff88283080c2 data=[6, 255, 255, 255, 255, 255, 255, 255]

[cuviper]

Given that this only happens in release mode, not debug, and that added prints and such perturb the issue, it sounds like there could be a codegen bug here.

[Amanieu]

Right, that's the expected result. The first control byte represents the item you are searching for and the rest represent EMPTY. I would expect match_empty to return 0b0111111... where everything except the first bit is set.

If this really is a codegen bug then there isn't much we can do without directly looking at the generated assembly code.

[douglas-raillard-arm]

Maybe but I'd expect a fault leading to a panic.

Actually I don't think so: printing the slice as-is worked, but calling that locks up:

        let x: u64 = u64::from_le_bytes(slice.try_into().unwrap());

So I doubt it's kernel-related. It looks like from_le_bytes from core is basically a transmute(). So it's not surprising it behaves as badly as casting the *const u8 into a *const u64, because it probably is exactly the same after optimizations.

[douglas-raillard-arm]

If this really is a codegen bug then there isn't much we can do without directly looking at the generated assembly code.

I'll see if I can de-inline the whole find_inner() function.

Interestingly, I ran again and got a different output, is that expected ?

ptr=0xffffff802d686cc2 data=[96, 255, 255, 255, 255, 255, 255, 255]

[douglas-raillard-arm]

Here is the disassembly of RawTableInner::find_inner in v0.15.0 tag, with all #[inline(never)] removed except on find_inner() and compiled with the a very aggressive inline threshold:

0000000000000000 <_ZN9hashbrown3raw13RawTableInner10find_inner17hcb6003a74dbed1fcE>:
   0:   a9ba7bfd        stp     x29, x30, [sp, #-96]!
   4:   d379fc28        lsr     x8, x1, #57
   8:   b200c3e9        mov     x9, #0x101010101010101          // #72340172838076673
   c:   a9035ff8        stp     x24, x23, [sp, #48]
  10:   a90267fa        stp     x26, x25, [sp, #32]
  14:   a9406019        ldp     x25, x24, [x0]
  18:   9b097d17        mul     x23, x8, x9
  1c:   f940107a        ldr     x26, [x3, #32]
  20:   a9016ffc        stp     x28, x27, [sp, #16]
  24:   a90457f6        stp     x22, x21, [sp, #64]
  28:   aa1f03f6        mov     x22, xzr
  2c:   910003fd        mov     x29, sp
  30:   a9054ff4        stp     x20, x19, [sp, #80]
  34:   aa0203f3        mov     x19, x2
  38:   8a01031b        and     x27, x24, x1
  3c:   8b1b0328        add     x8, x25, x27
  40:   b207dbf0        mov     x16, #0xfefefefefefefefe        // #-72340172838076674
  44:   39400509        ldrb    w9, [x8, #1]
  48:   3940010a        ldrb    w10, [x8]
  4c:   39400d0b        ldrb    w11, [x8, #3]
  50:   3940090c        ldrb    w12, [x8, #2]
  54:   3940150d        ldrb    w13, [x8, #5]
  58:   f29fdff0        movk    x16, #0xfeff
  5c:   38404d0e        ldrb    w14, [x8, #4]!
  60:   3940090f        ldrb    w15, [x8, #2]
  64:   d370bd8c        lsl     x12, x12, #16
  68:   39400d08        ldrb    w8, [x8, #3]
  6c:   aa092149        orr     x9, x10, x9, lsl #8
  70:   53103def        lsl     w15, w15, #16
  74:   aa0b618a        orr     x10, x12, x11, lsl #24
  78:   2a0d21cb        orr     w11, w14, w13, lsl #8
  7c:   2a0861e8        orr     w8, w15, w8, lsl #24
  80:   aa090149        orr     x9, x10, x9
  84:   2a0b0108        orr     w8, w8, w11
  88:   aa088134        orr     x20, x9, x8, lsl #32
  8c:   ca170288        eor     x8, x20, x23
  90:   8b100109        add     x9, x8, x16
  94:   8a280128        bic     x8, x9, x8
  98:   f201c11c        ands    x28, x8, #0x8080808080808080
  9c:   54000180        b.eq    cc <_ZN9hashbrown3raw13RawTableInner10find_inner17hcb6003a74dbed1fcE+0xcc>  // b.none
  a0:   dac00388        rbit    x8, x28
  a4:   aa1303e0        mov     x0, x19
  a8:   dac01108        clz     x8, x8
  ac:   8b480f68        add     x8, x27, x8, lsr #3
  b0:   8a180115        and     x21, x8, x24
  b4:   aa1503e1        mov     x1, x21
  b8:   d63f0340        blr     x26
  bc:   37000160        tbnz    w0, #0, e8 <_ZN9hashbrown3raw13RawTableInner10find_inner17hcb6003a74dbed1fcE+0xe8>
  c0:   d1000788        sub     x8, x28, #0x1
  c4:   ea1c011c        ands    x28, x8, x28
  c8:   54fffec1        b.ne    a0 <_ZN9hashbrown3raw13RawTableInner10find_inner17hcb6003a74dbed1fcE+0xa0>  // b.any
  cc:   8a140688        and     x8, x20, x20, lsl #1
  d0:   f201c11f        tst     x8, #0x8080808080808080
  d4:   540001c1        b.ne    10c <_ZN9hashbrown3raw13RawTableInner10find_inner17hcb6003a74dbed1fcE+0x10c>  // b.any
  d8:   910022d6        add     x22, x22, #0x8
  dc:   8b1b02c8        add     x8, x22, x27
  e0:   8a18011b        and     x27, x8, x24
  e4:   17ffffd6        b       3c <_ZN9hashbrown3raw13RawTableInner10find_inner17hcb6003a74dbed1fcE+0x3c>
  e8:   52800020        mov     w0, #0x1                        // #1
  ec:   aa1503e1        mov     x1, x21
  f0:   a9454ff4        ldp     x20, x19, [sp, #80]
  f4:   a94457f6        ldp     x22, x21, [sp, #64]
  f8:   a9435ff8        ldp     x24, x23, [sp, #48]
  fc:   a94267fa        ldp     x26, x25, [sp, #32]
 100:   a9416ffc        ldp     x28, x27, [sp, #16]
 104:   a8c67bfd        ldp     x29, x30, [sp], #96
 108:   d65f03c0        ret
 10c:   aa1f03e0        mov     x0, xzr
 110:   17fffff7        b       ec <_ZN9hashbrown3raw13RawTableInner10find_inner17hcb6003a74dbed1fcE+0xec>

[Amanieu]

Can you remove all the #[inline(never)] except the one on find_inner. The asm is actually easier to read with everything inlined.

[douglas-raillard-arm]

@Amanieu I updated the asm in the previous comment and it's indeed much, much shorter.

[Amanieu]

Can you try removing +strict-align from the target json? I think this may be an LLVM codegen issue but I can't find anything wrong with the assembly code at first glance.

[douglas-raillard-arm]

Still crashing, but the disassembly is ~30% shorter with -strict-align:

0000000000000000 <_ZN9hashbrown3raw13RawTableInner10find_inner17h58079395b7fac51aE>:
   0:   a9ba7bfd        stp     x29, x30, [sp, #-96]!
   4:   d379fc28        lsr     x8, x1, #57
   8:   b200c3e9        mov     x9, #0x101010101010101          // #72340172838076673
   c:   a9035ff8        stp     x24, x23, [sp, #48]
  10:   a90267fa        stp     x26, x25, [sp, #32]
  14:   a9406019        ldp     x25, x24, [x0]
  18:   9b097d17        mul     x23, x8, x9
  1c:   f940107a        ldr     x26, [x3, #32]
  20:   a9016ffc        stp     x28, x27, [sp, #16]
  24:   a90457f6        stp     x22, x21, [sp, #64]
  28:   aa1f03f6        mov     x22, xzr
  2c:   910003fd        mov     x29, sp
  30:   a9054ff4        stp     x20, x19, [sp, #80]
  34:   aa0203f3        mov     x19, x2
  38:   8a01031b        and     x27, x24, x1
  3c:   f87b6b34        ldr     x20, [x25, x27]
  40:   b207dbe9        mov     x9, #0xfefefefefefefefe         // #-72340172838076674
  44:   f29fdfe9        movk    x9, #0xfeff
  48:   ca170288        eor     x8, x20, x23
  4c:   8b090109        add     x9, x8, x9
  50:   8a280128        bic     x8, x9, x8
  54:   f201c11c        ands    x28, x8, #0x8080808080808080
  58:   54000180        b.eq    88 <_ZN9hashbrown3raw13RawTableInner10find_inner17h58079395b7fac51aE+0x88>  // b.none
  5c:   dac00388        rbit    x8, x28
  60:   aa1303e0        mov     x0, x19
  64:   dac01108        clz     x8, x8
  68:   8b480f68        add     x8, x27, x8, lsr #3
  6c:   8a180115        and     x21, x8, x24
  70:   aa1503e1        mov     x1, x21
  74:   d63f0340        blr     x26
  78:   37000160        tbnz    w0, #0, a4 <_ZN9hashbrown3raw13RawTableInner10find_inner17h58079395b7fac51aE+0xa4>
  7c:   d1000788        sub     x8, x28, #0x1
  80:   ea1c011c        ands    x28, x8, x28
  84:   54fffec1        b.ne    5c <_ZN9hashbrown3raw13RawTableInner10find_inner17h58079395b7fac51aE+0x5c>  // b.any
  88:   8a140688        and     x8, x20, x20, lsl #1
  8c:   f201c11f        tst     x8, #0x8080808080808080
  90:   540001c1        b.ne    c8 <_ZN9hashbrown3raw13RawTableInner10find_inner17h58079395b7fac51aE+0xc8>  // b.any
  94:   910022d6        add     x22, x22, #0x8
  98:   8b1b02c8        add     x8, x22, x27
  9c:   8a18011b        and     x27, x8, x24
  a0:   17ffffe7        b       3c <_ZN9hashbrown3raw13RawTableInner10find_inner17h58079395b7fac51aE+0x3c>
  a4:   52800020        mov     w0, #0x1                        // #1
  a8:   aa1503e1        mov     x1, x21
  ac:   a9454ff4        ldp     x20, x19, [sp, #80]
  b0:   a94457f6        ldp     x22, x21, [sp, #64]
  b4:   a9435ff8        ldp     x24, x23, [sp, #48]
  b8:   a94267fa        ldp     x26, x25, [sp, #32]
  bc:   a9416ffc        ldp     x28, x27, [sp, #16]
  c0:   a8c67bfd        ldp     x29, x30, [sp], #96
  c4:   d65f03c0        ret
  c8:   aa1f03e0        mov     x0, xzr
  cc:   17fffff7        b       a8 <_ZN9hashbrown3raw13RawTableInner10find_inner17h58079395b7fac51aE+0xa8>

[douglas-raillard-arm]

Also I tried on the emulator platform where everything seems to works (never locked up) and the disassembly is identical (as expected, since it's the exact same toolchain)

[douglas-raillard-arm]

So I think inlining played some tricks again: the problem seems to now appear in insert() rather than get(). It may have been in insert() all along, and the adding/removing of get() that seemingly triggered the bug maybe just influenced the inlined blob, with the issue actually being in insert() ... This thing is a nightmare.

That being said, it's not totally surprising since the loop we have been looking at seems to be almost copy/pasted in a few functions.

[Amanieu]

The fact that this doesn't reproduce in QEMU despite being the exact same assembly code strongly suggests that the issue is not from hashbrown but rather from something specific to the kernel and/or hardware.

Even if you can't get kgdb working, surely you should be able to get a register state or at least a PC from a kernel thread stuck in a loop? A register state should be able to give enough information to figure out what is going on.

[douglas-raillard-arm]

I don't think we can state it is the exact same assembly. The issue has been "moving" around due to inlining and I can't just disable it fully otherwise the problem is hidden. So I while I was looking at one function, the problem was materialized somewhere else.

When the lockup happens, the CPU get stuck for 10s, then a watchdog detects it and the only info printed is a back trace with a single entry. That entry is either a kernel function involved in syscalls or the scheduler. However, removing the snippet from the module fixes the issue, so it definitely has something to do with it (and it's even clearer there is a problem in the code or compiler given that it depends on rust optimization level).

[clarfonthey]

I think that it should be mostly possible to verify that it's the same assembly if you use the same custom target for both and ensure that insert itself isn't inlined. It would be helpful to clarify that it is in fact the wrong code being generated and not just a hardware issue.