radix_trie: eliminate iteration in keydiff

[dougm]

Summary

The implementations of *_keydiff iterate. By using flsl(), they don't have to.

If flsl() is implemented as a loop, though, this is a loss. Of particular concern is behavior on riscv, where the standard loop implementations of ffs, fls, etc appear to be in place. The change proposed at https://reviews.freebsd.org/D40594 seems like it ought to replace the loops with __builtin_ffs and the like, but I don't see obvious benefits (the presence of ctz and clz opcodes in objdump output) from this change after building a riscv kernel.

Mark, do you have any suggestions on how to (or who could) get ffs and fls inlined on riscv?

Test Plan

Kernel boots.

[markj]

The change proposed at https://reviews.freebsd.org/D40594 seems like it ought to replace the loops with __builtin_ffs and the like, but I don't see obvious benefits (the presence of ctz and clz opcodes in objdump output) from this change after building a riscv kernel.

Mark, do you have any suggestions on how to (or who could) get ffs and fls inlined on riscv?

Those instructions are not part of the base ISA, but instead belong to one of a set of ratified "bit-manipulation" extensions. There appears to be some LLVM support for them but I'm not sure how to turn it on, and presumably we don't want to do that for GENERIC kernels? @jrtc27 or @mhorne could possibly say more.

[mhorne]

In D40585#924441, @markj wrote:

The change proposed at https://reviews.freebsd.org/D40594 seems like it ought to replace the loops with __builtin_ffs and the like, but I don't see obvious benefits (the presence of ctz and clz opcodes in objdump output) from this change after building a riscv kernel.

Mark, do you have any suggestions on how to (or who could) get ffs and fls inlined on riscv?

Those instructions are not part of the base ISA, but instead belong to one of a set of ratified "bit-manipulation" extensions. There appears to be some LLVM support for them but I'm not sure how to turn it on, and presumably we don't want to do that for GENERIC kernels? @jrtc27 or @mhorne could possibly say more.

Mark's assessment is correct. I've left a more detailed comment in D40594.

[alc]

sys/vm/vm_radix.c

300–304

On 32-bit machines, a long is 32 bits, but a vm_pindex_t is 64 bits.

[dougm]

flsl -> flsll

[markj]

In D40585#924470, @mhorne wrote:

I've left a more detailed comment in D40594.

Thank you!

sys/kern/subr_pctrie.c

56

libkern.h sorts after kernel.h.

[alc]

sys/vm/vm_radix.c

289

This description is wrong, This function does not return a slot. Please fix it.

[dougm]

Fix include order. Fix inaccurate comment. Add explanatory comment before flsl(). Do it twice.

[dougm]

At this point, I'll wait for Mark to re-approve.