pctrie: add combined insert/lookup operations

[rlibby]

Summary

In several places in code, we do a pctrie lookup followed by a pctrie
insert. Provide a few flavors of combined lookup/insert. This may save
a portion of the work from walking a large pctrie twice.

The general idea is that while we walk the trie during insert, we also
do the same kind of tracking work that we do during pctrie_lookup_ge or
pctrie_lookup_le, and we pass out a pctrie node from where such a lookup
may continue.

Sponsored by: Dell EMC Isilon

[rlibby]

kib feedback on KASSERT style, and fix a comment typo

[dougm]

sys/sys/pctrie.h

97

if __predict_false is useful for all the other ENOMEM tests, it's useful here too.

[rlibby]

sys/sys/pctrie.h

97

I agree, I was thinking to do that in a separate commit, for more flexibility with MFC. I'll put that up for review tonight.

I can tell you that clang produced some code paths that were, let's say, non-optimal, without the predictions, when I examined the code gen for bgetvp.

[dougm]

Looks good to me.

[markj]

sys/kern/subr_pctrie.c

270–283

... or NULL if the slot is already populated.

281

I'm not sure if it matters anymore, but at one point making mode const helped ensure that constant folding would happen during inlining.

313

Do you need this NULL check, in light of the lack of such checks for neighbor_out?

[rlibby]

sys/kern/subr_pctrie.c

270–283

I'll add some words to that effect.

281

I did look at output of in-tree clang on amd64 to check that it did the extraneous code removal. If I can remember how to get the cross build set up, I can check gcc too.

313

I believe you're right that I don't. Will remove.

I made the typed out param to name##_PCTRIE_FIND_OR_INSERT optional, but the double pointer to the index is never NULL.

[rlibby]

markj feedback: reword comment, remove unneeded NULL check

[markj]

sys/kern/subr_pctrie.c

281

To build with gcc, install amd64-gcc13 and make buildkernel CROSS_TOOLCHAIN=amd64-gcc13.

[rlibby]

sys/kern/subr_pctrie.c

281

Thanks. I checked that gcc13 also removes the extraneous code here.

However, over in D45486, the situation is a little different, clang only inlined vm_page_insert_after (which with the patch is now just a wrapper). Marking bool lookup as const didn't change behavior, but marking vm_page_insert_lookup as __always_inline instead of inline did. I'll comment on the other diff.