Details

Reviewers

alc
markj

Commits

rGd0b225d16418: swap_pager: use iterators in swp_pager_meta_build

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)

Diff Detail

Lint

Lint Skipped

Unit

Tests Skipped

Event Timeline

dougm requested review of this revision.Sep 30 2024, 7:58 AM

dougm created this revision.

dougm edited the test plan for this revision. (Show Details)Sep 30 2024, 3:48 PM

dougm added reviewers: alc, markj.

markj added inline comments.Oct 4 2024, 3:29 PM

sys/vm/swap_pager.c
2170	`blks` is invalid after the object lock was dropped.
2202	`blks` is invalid at this point, since the object lock was dropped.

dougm marked an inline comment as done.Oct 4 2024, 3:46 PM

dougm added inline comments.

sys/vm/swap_pager.c
2170	swblk_iter (re-)initializes blks.

alc added inline comments.Oct 4 2024, 3:59 PM

sys/vm/swap_pager.c
2170	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 added inline comments.Oct 4 2024, 4:36 PM

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
2170	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.
2176	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`.

Address all the concerns expressed so far.

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

alc added inline comments.Oct 5 2024, 5:22 PM

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.

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 added inline comments.Oct 5 2024, 8:13 PM

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
2170	I agree.

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 added inline comments.Oct 6 2024, 8:17 PM

sys/kern/subr_pctrie.c
610	Please reintroduce the fix here.

Modify iter_insert to use pctrie_root_store.

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

sys/vm/swap_pager.c
2243

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

markj added inline comments.Oct 7 2024, 2:45 PM

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?

Update after renaming swblk_iter init functions.

alc added inline comments.Oct 7 2024, 4:24 PM

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.

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 added inline comments.Oct 7 2024, 9:54 PM

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 accepted this revision.Oct 8 2024, 8:03 AM

alc added inline comments.

sys/vm/swap_pager.c
564–566

This revision is now accepted and ready to land.Oct 8 2024, 8:03 AM

The test plan should say what the units are.

dougm edited the test plan for this revision. (Show Details)Oct 8 2024, 8:29 AM

Closed by commit rGd0b225d16418: swap_pager: use iterators in swp_pager_meta_build (authored by dougm). · Explain WhyOct 8 2024, 8:33 AM

This revision was automatically updated to reflect the committed changes.

dougm added a commit: rGd0b225d16418: swap_pager: use iterators in swp_pager_meta_build.

Herald added subscribers: olce, imp. · View Herald TranscriptOct 8 2024, 8:33 AM

swap_pager: use swblk iterators in swp_pager_meta_build
ClosedPublic
Actions

Details

Diff Detail

Event Timeline

Revision Contents
Changeset List

Diff 144315

sys/kern/subr_pctrie.c

sys/sys/pctrie.h

sys/vm/swap_pager.c

swap_pager: use swblk iterators in swp_pager_meta_buildClosedPublicActions

Details

Diff Detail

Event Timeline

Revision ContentsChangeset List

Diff 144315

sys/kern/subr_pctrie.c

sys/sys/pctrie.h

sys/vm/swap_pager.c

swap_pager: use swblk iterators in swp_pager_meta_build
ClosedPublic
Actions

Revision Contents
Changeset List