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.
Details
- Reviewers
rlibby kib - Commits
- rGc0d0bc2bed80: subr_pctrie: add leaf callbacks to pctrie_reclaim
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.
Diff Detail
- Lint
Lint Skipped - Unit
Tests Skipped
Event Timeline
I have some nitpicks, but the actual logic looks good to me.
sys/kern/subr_pctrie.c | ||
---|---|---|
826 | 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). | |
872–873 | 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. |
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. |
sys/kern/subr_pctrie.c | ||
---|---|---|
228 | Will fix. | |
230 | 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. */ |
sys/sys/pctrie.h | ||
---|---|---|
229–231 | the the, otherwise LGTM. Thanks. |