Page MenuHomeFreeBSD
Differential D46895

pctrie: unlock writes without smr
Needs ReviewPublic
Actions

Authored by dougm on Oct 4 2024, 6:45 AM.
Tags
None
Referenced Files
Unknown Object (File)
Tue, Nov 19, 7:39 PM
Unknown Object (File)
Mon, Nov 18, 3:28 AM
Unknown Object (File)
Sun, Nov 17, 7:06 PM
Unknown Object (File)
Sat, Nov 16, 12:18 PM
Unknown Object (File)
Sat, Nov 16, 12:50 AM
Unknown Object (File)
Fri, Nov 15, 3:01 PM
Unknown Object (File)
Wed, Nov 13, 12:07 PM
Unknown Object (File)
Wed, Nov 13, 12:23 AM
View All 42 Files
Subscribers
bnovkov

Details

Reviewers
alc
markj
kib
Summary

Stores to a pctrie have to be locked only when smr allows concurrent lookups. With no smr, stores can be unsynchronized. Based on whether or not a pctrie type is generated with or without smr, do or do not lock stores.

Modify the operations that modify the pctrie so that they don't perform locked stores, but instead return to the top level the source and destination for the store. These two can be examined at the top level to determine if any allocation or deallocation is necessary, and then the store is performed at the top level according to whether or not smr is used for that pctrie type.

This means that a few operations previously hidden in subr_pctrie.c are now exposed in pctrie.h.

Diff Detail

Lint
Lint Skipped
Unit
Tests Skipped

Event Timeline

dougm requested review of this revision.Oct 4 2024, 6:45 AM
dougm created this revision.
dougm updated this revision to Diff 144263.Oct 4 2024, 4:51 PM

Add a missing function argument.

dougm updated this revision to Diff 144308.Oct 5 2024, 6:01 PM

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

dougm updated this revision to Diff 144314.Oct 5 2024, 7:06 PM

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

dougm added a reviewer: markj.Oct 5 2024, 8:29 PM
alc added a comment.Oct 6 2024, 7:40 PM

There are too many things going on here at once. Can you generate a simple patch that fixes the correctness bug that Mark pointed out.

dougm updated this revision to Diff 144349.Oct 6 2024, 8:32 PM

Update after pctrie_root_store commit.

dougm mentioned this in D46848: swap_pager: use swblk iterators in swp_pager_meta_build.Oct 7 2024, 9:54 PM
dougm updated this revision to Diff 144465.Oct 8 2024, 8:41 AM

Update after the commit that introduced iter_insert to main.

markj added a comment.Oct 8 2024, 3:09 PM

This introduces some branches that can't be collapsed at compile-time. On amd64 though, I'd expect/hope the compiler at least eliminates the branch in pctrie_node_store(). Is that the case?

sys/kern/subr_pctrie.c
109–110

Can we pass an enum value from callers instead of a bool?

dougm added a comment.Oct 8 2024, 4:42 PM
In D46895#1071700, @markj wrote:

This introduces some branches that can't be collapsed at compile-time. On amd64 though, I'd expect/hope the compiler at least eliminates the branch in pctrie_node_store(). Is that the case?

It appears not. There is no actual function pctriie_node_store compiled, but it is inlined in functions beginning with pctrie_insert_lookup_string, and there are a couple of branches added there.

sys/kern/subr_pctrie.c
109–110

If there is a good reason.

alc added inline comments.Oct 8 2024, 5:06 PM
sys/kern/subr_pctrie.c
109–110

It clearly conveys information about the type of access at the call site. true/false tell me nothing without looking at the implementation.

dougm updated this revision to Diff 144502.Oct 8 2024, 5:41 PM

Deboolification.

markj added a comment.Oct 11 2024, 1:12 PM

This seems okay to me from a correctness perspective, but is it worth it? Aren't we losing quite a bit of inlining?

As a hack for x86, can we simply use an ifdef to merge the locked and unserialized cases in pctrie_node_store()?

sys/kern/subr_pctrie.c
223

access is too generic a name given that it refers only to stores. Maybe store_type?

dougm added a comment.EditedOct 11 2024, 6:34 PM
In D46895#1072679, @markj wrote:

As a hack for x86, can we simply use an ifdef to merge the locked and unserialized cases in pctrie_node_store()?

Isn't it really a hack for smr_types.h?

Or atomic_san.h?

markj added a comment.Oct 11 2024, 7:10 PM
In D46895#1072882, @dougm wrote:
In D46895#1072679, @markj wrote:

As a hack for x86, can we simply use an ifdef to merge the locked and unserialized cases in pctrie_node_store()?

Isn't it really a hack for smr_types.h?

Or atomic_san.h?

My understanding is that the compiler doesn't collapse the PCTRIE_UNSERIALIZED and PCTRIE_LOCKED cases of pctrie_node_store() on amd64, even though they're effectively the same. (On amd64, atomic_store_rel_*(...) expands to __compiler_membar(); atomic_store_*(...).) Assuming that this is the case, I think that's a problem to be solved in the pctrie code. That said, I haven't looked at the disassembly myself, so perhaps I'm missing something.

The general intent is that the branches in pctrie_node_store() should be collapsed at compile-time, but now that's not the case, so I think it's up to the pctrie code to try and help the compiler. I can't really see how you'd solve this in smr_types.h.

atomic_san.h just exists to provide indirection so that sanitizer runtimes can intercept all uses of atomic_*() macros; the real definitions are in machine/atomic.h and atomic_common.h.

dougm updated this revision to Diff 144783.Oct 13 2024, 8:15 PM
dougm edited the summary of this revision. (Show Details)

Pull the locked stores out of subr_pctrie.c and leave them for inline functions in pctrie.h to perform, with whatever synchronization type is appropriate.

dougm updated this revision to Diff 144786.Oct 13 2024, 9:10 PM

Where this change causes a couple of functions to only be invoked with parameter access == PCTRIE_UNSYNCHRONIZED, drop that parameter.

dougm updated this revision to Diff 144832.Oct 14 2024, 5:03 PM

Since the insert_lookup functions now never actually insert anything they don't have to have a uint64_t* argument that might get inserted, they only need a uint64_t argument for the lookup. Make that change.

I foresee this being used to move a node from one pctrie to another with a new index, by first doing the insert_lookup with the new index, then seeing if malloc is either successful or unneeded, then removing the item from the old trie, changing its index to the one, and plugging it into the space that the insert_lookup provided.

dougm added a subscriber: bnovkov.Oct 17 2024, 7:54 AM
dougm updated this revision to Diff 145173.Oct 19 2024, 7:23 PM

Avoid an extra node_load in pctrie_insert_node by passing the node argument to it. Break pctrie_init_node out of pctrie_insert_node, in anticipation of batch insertion.

dougm added a reviewer: kib.Oct 19 2024, 9:43 PM
dougm added a child revision: D47271: pctrie: add function to transfer between pctries.Wed, Oct 23, 10:42 PM
bnovkov added a comment.Thu, Oct 24, 5:48 PM

I'd appreciate if you could break this patch into a couple of smaller ones, it'll make D47271 easier to review as well.

dougm updated this revision to Diff 145562.Mon, Oct 28, 9:46 PM

Rebase.

dougm updated this revision to Diff 145867.Fri, Nov 1, 4:13 PM

Rebase.

dougm updated this revision to Diff 146007.Mon, Nov 4, 7:35 PM

Rebase. Undo some function reordering that makes this reviewer easier, even if it preserves some odd ordering.

Is this reviewable yet, or shall I continue to slice little bits off of it for separate checkins?

dougm added a comment.Sat, Nov 9, 8:29 AM

Performance test:
Ran 12 buildworlds, without and with this change, on an amd64 machine to verify it did not harm performance there.
Without:

56769.432u 1417.580s 1:03:23.59 1529.7% 79527+3176k 168829+33929io 126734pf+0w
56860.947u 1453.741s 1:03:24.84 1532.6% 79494+3176k 107451+34330io 103664pf+0w
56908.519u 1491.555s 1:03:26.58 1534.1% 79457+3176k 107194+34880io 103639pf+0w
56891.023u 1498.763s 1:03:34.60 1530.6% 79470+3175k 107164+34882io 103608pf+0w
56983.071u 1553.436s 1:03:46.20 1529.8% 79408+3175k 104894+34791io 103649pf+0w
56881.515u 1501.567s 1:03:30.68 1532.0% 79452+3176k 106838+34848io 103632pf+0w
56860.773u 1534.425s 1:03:27.26 1533.7% 79423+3175k 106843+35201io 103637pf+0w
56822.932u 1554.642s 1:03:25.65 1533.9% 79408+3175k 106891+35310io 103645pf+0w
56745.737u 1558.012s 1:03:21.41 1533.7% 79397+3173k 106833+34994io 103669pf+0w
56768.943u 1546.209s 1:03:28.76 1531.0% 79405+3175k 107045+35225io 103647pf+0w
56728.036u 1557.456s 1:03:18.47 1534.4% 79396+3174k 106889+35040io 103632pf+0w
56849.483u 1557.751s 1:03:29.65 1533.1% 79409+3173k 106797+34997io 103671pf+0w

With:

56823.004u 1406.423s 1:03:19.33 1532.6% 79525+3177k 169149+33671io 126758pf+0w
56894.320u 1452.191s 1:03:23.22 1534.1% 79489+3177k 107496+34521io 103710pf+0w
56873.514u 1484.114s 1:03:27.84 1532.5% 79455+3176k 107341+34808io 103625pf+0w
56861.778u 1477.955s 1:03:24.18 1533.5% 79470+3175k 107119+34980io 103620pf+0w
56825.775u 1543.975s 1:03:26.64 1533.3% 79413+3173k 107044+35011io 103653pf+0w
56951.746u 1545.610s 1:03:33.63 1533.9% 79413+3174k 107117+35304io 103640pf+0w
56876.186u 1536.238s 1:03:31.71 1532.4% 79417+3173k 107132+34995io 103663pf+0w
56966.031u 1542.074s 1:03:36.94 1532.8% 79401+3175k 107247+35316io 103637pf+0w
56921.548u 1545.400s 1:03:34.07 1532.9% 79406+3174k 107172+34936io 103651pf+0w
56882.619u 1537.124s 1:03:31.19 1532.8% 79421+3173k 106989+35784io 103607pf+0w
56925.801u 1540.126s 1:03:31.98 1533.7% 79410+3173k 107158+35402io 103653pf+0w
56948.563u 1645.405s 1:03:42.43 1532.8% 79316+3171k 106999+34963io 103628pf+0w

Revision Contents
Changeset List

PathSize
sys/
kern/
279 lines
sys/
291 lines

Diff 144783

View Options

sys/kern/subr_pctrie.c

Loading...
View Options

sys/sys/pctrie.h

Loading...