pctrie: unlock writes without smr

[dougm]

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.

[dougm]

Add a missing function argument.

[dougm]

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

[dougm]

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

[alc]

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]

Update after pctrie_root_store commit.

[dougm]

Update after the commit that introduced iter_insert to main.

[markj]

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

103–104

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

[dougm]

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

103–104

If there is a good reason.

[alc]

sys/kern/subr_pctrie.c

103–104

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

[dougm]

Deboolification.

[markj]

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

213

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

[dougm]

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]

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]

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]

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

[dougm]

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]

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.

[bnovkov]

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]

Rebase.

[dougm]

Rebase.

[dougm]

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]

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