The key here is that all page allocation functions call vm_page_dequeue(), completing any lingering page queue operations that involve the plinks.q field.

Are you going to update the patch to include vm_page_grab_pages()?

Aren't all of the changes to vm_page.h valid? Can we have a standalone patch with just those changes?

In D49957#1140976, @alc wrote:

Now that iterators are much smaller, consisting of only four 64-bit fields, I think we should seriously consider embedding an iterator in the vm_object for use by operations that require a write lock on the object. If that iterator is used by the functions that insert and remove pages from the trie, then it will always be consistent, and most of the pctrie_iter_reset()s can be eliminated. With the removal of the memq from the object, this would only grow the size of the vm_object by 2 64-bit fields. (If there was some way to avoid having both the root of the pctrie and the iterator's pointer to that root within the vm_object, then the size of the vm_object would only grow by 1 64-bit field.)

The operations, like vm_map_pmap_enter(), that utilize a read lock will still need to define and use their own private iterator.

That all said, I think that we should complete the removal of the memq, and then consider embedding an iterator in the object.

Now that iterators are much smaller, consisting of only four 64-bit fields, I think we should seriously consider embedding an iterator in the vm_object for use by operations that require a write lock on the object. If that iterator is used by the functions that insert and remove pages from the trie, then it will always be consistent, and most of the pctrie_iter_reset()s can be eliminated. With the removal of the memq from the object, this would only grow the size of the vm_object by 2 64-bit fields. (If there was some way to avoid having both the root of the pctrie and the iterator's pointer to that root within the vm_object, then the size of the vm_object would only grow by 1 64-bit field.)

The performance results in the TEST PLAN are much improved over what I was seeing last fall for a similar set of changes, in particular, the results for vm_page_alloc(). Clearly, the improvements to the implementation of iterators in the last few months, particularly I suspect the elimination of the rather large array on the stack, have made a difference. Modulo any low-level changes/fixes to this patch that are needed, I would be very happy to see it committed. This is really the most critical step in my mind to the elimination of the two linked list pointers from struct vm_page, which I hope will yield a small but measurable performance improvement, particularly for pages allocated from superpage reservations.

In D49391#1126158, @alc wrote:

The vm_page.h comment incorrectly says vm_page_alloc accepts VM_ALLOC_WAITOK.

The vm_page.h comment incorrectly says vm_page_alloc accepts VM_ALLOC_WAITOK.

This change increased the cycles spent in both vm_object_split() and vm_object_collapse_scan() during a buildworld. It appears that we're not moving enough pages to overcome the startup costs of the iterator.

Shouldn't this be abandoned?

Update in response to reviewer comments.

In D47829#1090358, @dougm wrote:

Comments in vm_reserv.c need to be updated to reflect this change.

If you have measured the improvement, how big is it?

Update in response to reviewer comments.

Let's limit this change to vm_page_iter_free. It reduces the average cycles in _kmem_unback and vm_object_page_remove by 7% and 5.3%, respectively.

By itself, this is going to be slower. This should be a part of a larger patch that removes the memq, so that we can evaluate whether the elimination of the memq makes up for the higher cost of the iterators.

Cycles to perform a 2MB aligned vm_page_alloc_contig() for shm_create_largepage() on a Ryzen 5900X:

x base
+ iter
+------------------------------------------------------------------------------+
|  +                                                             x             |
|  ++                                                            x             |
|  ++                                                           xx             |
| ++++        +                                                xxx xx         x|
||_MA___|                                                     |__MA____|       |
+------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  10         16813         17866       16989.5       17074.6     294.94715
+  10         12691         13496         12759       12833.1     239.58643
Difference at 95.0% confidence
        -4241.5 +/- 252.466
        -24.841% +/- 1.2701%
        (Student's t, pooled s = 268.696)

Is this related to the KASSERT that was recently added to vm_object_terminate_single_page?

In D47046#1079047, @dougm wrote:

In D47036, I put it after vm_radix_iter_step, mostly because PCTRIE_ITER_LOOKUP_LE comes shortly after PCTRIE_ITER_STEP_GE in pctrie.h. 'step' and 'jump' are built on top of lookup_ge, so I kept them grouped with lookup_ge.

I had a comment, and there should be one here for consistency with all the other little functions in this file.

I agree that we should have a sensible order to things, and that we don't. I suggest non-iter before iter, then insert before lookup before remove before replace before disposal, then lookup == before lookup >= before lookup <=.

To be clear, there is no question that this function will get used, so adding it sooner, rather than later, would be okay with me.

I'm looking at patches from both you and @dougm that define this function. However, each of you adds it in a different location within the file. :-)

Incorporating D47277 has increased the average number of cycles to perform vm_page_alloc() to 1325.

Incorporating D47277 yielded the lowest average cycles in vm_page_alloc_contig() that I've seen.

Switching from ..._lookup_le() to ..._lookup_lt() increased the average number of cycles in vm_page_alloc().

D47207 has reduced the average number of cycles to perform vm_page_alloc() from 1295 to 1265.