Rename *_iter( functions to *_iter_init. Though I'd swear I'd done that once already.

Add pctrie_replace to the set of functions taking a hassmr parameter.

Revert changes from the last update to subr_pctrie.c, since, as @alc points out, those changes are not the topic of this change. Let's save all the unrelated subr_pctrie complaints for a different change.

Get a complete version of the iter_insert_lookup here, with hassmr.

Rewrite the sb->p checks in meta_build to match the arrangement of the MPASS after the allocated label.

Address all the concerns expressed so far.

Add a missing function argument.

Copy @alc's edit.

Avoid checking the same page for validity twice, at the cost of finding the next page when it might turn out not to matter.

Try to address feedback from @markj and @alc.

Fix some sloppiness.

Reset the page iterator too.

Update to account for overlapping changes to swap_pager.c. Address comments from @alc. Drop variable 'pi'.

In D46800#1067418, @bz wrote:

In D46800#1067105, @dougm wrote:

My concern with this is that if the argument n to the macro has side effects, they will be effected twice. I don't find examples of that in the kernel, though I do find somewhere that n is a function call, so that a function would be invoked twice.

Let me suggest an alternative.

#define order_base_2(n) ilog2(2*(n)-1)

I believe that addresses your problem. What it costs is overflow when n has its high order bit set. I don't think that's a significant cost.

Seems to work for me. Do you want to commandeer the change for this?

What exactly do you mean by "freeing"? I wouldn't expect this patch on its own to affect how fast we can free pages, or is this including your other iterator patches?

With this patch:
{F96917947}
I compared the cycles consumed freeing 1000000 pages without and with this patch. The results from ministat:

My concern with this is that if the argument n to the macro has side effects, they will be effected twice. I don't find examples of that in the kernel, though I do find somewhere that n is a function call, so that a function would be invoked twice.

A performance test. With this patch {F96492700}, which computes stats on calls to swp_pager_meta_free, I ran all 8 stress2 swap tests, recording the stats immediately before and aofter the tests. The stats are 'cycles', 'calls', and 'pages' (freed). The results are:

Address @alc feedback.

Update the patch to reflect the changes already checked in to main to address the last couple of comments.

Let the assertion remain.

Define no-radix-tree-modification versions of vm_page_remove and vm_page_free and use them.

In D46753#1065827, @alc wrote:

No, this is not what @markj meant.

Undo the last non-whitespace change, since it breaks swap_pager_find_least by possibly creating an empty block.

Address @markj concerns.

Apply iterators to vm_kern.c:_kmem_unback.

Process vm_object_collapse_scan similarly.

Back out one change that isn't ripe yet, as it depends on other changes not yet offered for review.

Incorporate changes from comments-only commit. Fix calculation of initial start value.

Accept as many suggestions as possible, but without defining a FOREACH macro.

Move pctrie_iter struct declaration in vm_page.h.

This proposal proved much less popular with its intended audience than I anticipated.

Incorporate meta_transfer changes. Use blk.index for sp->p in several places. Compute 'start' more simply.

Address @alc feedback.

Use a bitmask. Scope the bitmask outside of the loop to avoid reinitializing to zero.

A version without bitmasking. Perhaps this is acceptable?