swap_pager: use swblk iterators in swp_pager_meta_build

[dougm]

Summary

Add a method to use an iterator for pctrie insertion; this should improve performance when the last search ended near the place where the new item will be inserted.

Add an iterator argument to swp_pager_meta_build, so that the lookups and insertions it does can be faster in the common case when keys are bunched close together, or appear in sequence.

Test Plan

I've run the stress2 swap tests without incident.

With this test patch: {F97661278}, I've tested the time (measured in machine cycles) it takes to do 1 million swp_page_meta_build calls (and a smaller number of swp_pager_getswapspace calls) with and without this change. The results, analyzed by ministat, are here:

x old
+ new
+------------------------------------------------------------------------------+
| +                                                                            |
| ++                                                                           |
|+++   +                                           x  xx                       |
|+++  ++                                           xx xxxx  x              x  x|
||MA_|                                           |_____M__A________|           |
+------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  12      45506632      50173397      46252604      46751133     1558878.7
+  12      36901703      37918690      37119202      37277605     376800.52
Difference at 95.0% confidence
        -9.47353e+06 +/- 960197
        -20.2637% +/- 1.66335%
        (Student's t, pooled s = 1.13404e+06)

[markj]

sys/vm/swap_pager.c

2158–2159

blks is invalid after the object lock was dropped.

2191–2192

blks is invalid at this point, since the object lock was dropped.

[dougm]

sys/vm/swap_pager.c

2158–2159

swblk_iter (re-)initializes blks.

[alc]

sys/vm/swap_pager.c

2158–2159

The takeaway from this should be that the name is too terse. There should be a suffix that implies that the iterator is being initialized.

[markj]

sys/kern/subr_pctrie.c

610

This pattern exists elsewhere (e.g., in pctrie_insert_lookup()), but I believe we need to use pctrie_node_store() or equivalent to store to the root node as well. In particular, this store should have release semantics, to synchronize with unlocked lookups.

sys/vm/swap_pager.c

2158–2159

Sorry for jumping the gun. I think I agree that the name is a bit terse. It's not obvious at a glance that swblk_iter() initializes the iterator when swblk_iter_lookup() does not. Maybe swblk_iter_start() or swblk_iter_init() would be clearer.

2166

swblk_iter() returns the next swap block, which may or may not be at pindex, right? I think this condition also needs to check sb->p.

[dougm]

Address all the concerns expressed so far.

[dougm]

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

[alc]

sys/kern/subr_pctrie.c

307–308

This should really be committed separately as a concurrency bug fix.

539–540

Iterators will always be performed with the relevant lock held, so these last two parameters are pointless.

[dougm]

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.

[alc]

sys/kern/subr_pctrie.c

307–308

As a fix, this should come first.

610

@markj While your observation is correct, I would also observe that several of these functions are penalizing arm64 by introducing memory barriers in operations on non-SMR tries, like the swap pager's, that aren't needed.

sys/vm/swap_pager.c

2158–2159

I agree.

[dougm]

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

Add _reinit functions to use lookup instead of lookup_ge for resetting after lock acquisition in meta_build.

[alc]

sys/kern/subr_pctrie.c

610

Please reintroduce the fix here.

[dougm]

Modify iter_insert to use pctrie_root_store.

[alc]

Can you separate out the function renames, and commit that first.

sys/vm/swap_pager.c

2234

[dougm]

Stop naming iterator initializers with "_init", since another patch does that now. Alphabetize order of definition in one place.

[markj]

sys/kern/subr_pctrie.c

610

Right now, there's no way for this code to know whether a given pctrie was initialized with PCTRIE_DEFINE_SMR or not. We could set a bit in the root node to indicate that, and incorporate it when storing a pointer to a node. Alternately, define no-SMR variants of all pctrie internal functions, wherein PCTRIE_LOCKED stores are just plain stores, and have PCTRIE_DEFINE generate wrappers for those functions. Or maybe there's another option?

[dougm]

Update after renaming swblk_iter init functions.

[alc]

sys/kern/subr_pctrie.c

610

I have been assuming the latter, i.e., define non-SMR variants. I'd hate to add conditional control flow at run-time to amd64 where there is no real distinction between _LOCKED _UNSERIALIZED.

[dougm]

Add swblk_iter_init_only(), which does not end with a lookup, and use it in places where a returned lookup value was being discarded.

[dougm]

sys/kern/subr_pctrie.c

307–308

See D46895.

539–540

Iterators are always performed with the relevant lock held. I can remove these parameters for now, and put them back in later when I'm adding smr iteration, but that's all off-topic for this patch, and belongs as part of a concurrency bug fix. D46895 seems like the place to argue this.

610

D46895 is an attempt to address this issue. It's not going to be addressed as part of this change.

[alc]

sys/vm/swap_pager.c

564–566

[alc]

The test plan should say what the units are.