subr_pctrie: add leaf callbacks to pctrie_reclaim

[dougm]

Summary

PCTRIE_RECLAIM frees all the interior nodes in a pctrie, but is little used because most trie-destroyers want to free leaves of the tree too. Add PCTRIE_RECLAIM_CALLBACK, with two extra arguments, a callback function and an auxiliary argument, that is invoked on every non-NULL leaf in the tree as the tree is destroyed.

Test Plan

A modification to swp_pager_meta_free_all in swap_pager.c has been developed to use this new method, and a kernel has been successfully booted with it.

Since I understand that I know nothing about how to test swap_pager code, I've also applied it to code in subr_rangeset.c. Perhaps that tests it. Or perhaps not.

[rlibby]

I have some nitpicks, but the actual logic looks good to me.

sys/kern/subr_pctrie.c

823

Just confirming the logic, we don't need the PCTRIE_NULL check here because we already know the slot is populated (we could e.g. KASSERT(child != PCTRIE_NULL) -- not that I think we need to).

869–870

Out of paranoia, I might check callback != NULL first, since that's the key condition for the compiler to determine if it can eliminate this. It will probably figure it out though. Please check the code gen if you haven't already.

sys/sys/pctrie.h

37–40

The #ifdef _KERNEL covers nearly everything in this file, did you intend for the typedefs to be outside it? I don't think it will cause a problem, but if it's needed for something then I don't understand.

223–224

Is the presence of the non-inline procedure defined in a header a potential API problem? I think this would be the only one.

Maybe instead of defining this procedure we could just pass down keyoff = offsetof(type, key) and effectively reimplement VAL2PTR in subr_pctrie.c? That could also get rid of the double callback. What's more, we know that the values we call the callback on aren't NULL, so we can omit the NULL check and it just becomes (void *)((uintptr_t)pkey - keyoff).

229–231

I would suggest a comment disclaimer somewhere that the entries are not visited in key order. I'm not sure where would be best, there are few other comments in the header.

We should probably eventually write a man page.

[dougm]

sys/kern/subr_pctrie.c

823

I confirm that. child is not NULL.

869–870

I'll deal with that.

sys/sys/pctrie.h

37–40

No particular intention. I'll move it into the ifdef.

223–224

Will do.

229–231

They are visited in order. I've added a comment to that effect in the sparsely-commented header.

[dougm]

Apply @rlibby suggestions.

[rlibby]

sys/sys/pctrie.h

229–231

Okay, re-reading pctrie_reclaim_prune, I agree that it is in-order. But then I think its banner comment is stale, it says leaves before children.

[rlibby]

Style nits, otherwise LGTM.

sys/kern/subr_pctrie.c

226

Looks like there's an extra space here.

228

alc commented on me inserting the leading blank line recently. We're allowed to omit it now, and you do on other new procedures below. I am ambivalent overall.

[dougm]

sys/kern/subr_pctrie.c

226

Will fix.

228

Will strip that blank line from the one-line functions in this neighborhood.

sys/sys/pctrie.h

229–231

Here's a rewrite of that comment:

/*
 * Walk the subtrie rooted at *pnode in order, invoking callback on leaves and
 * using the leftmost child pointer for path reversal, until an interior node
 * is stripped of all children, and returned for deallocation, with *pnode left
 * pointing the the parent of that node.
 */

[rlibby]

sys/sys/pctrie.h

229–231

the the, otherwise LGTM. Thanks.