vfs_subr: maintain sorted tailq
ClosedPublic
Actions

Authored by dougm on Oct 19 2024, 5:08 PM.

Details

Reviewers

markj
kib

Commits

rGe2414d91d33f: vfs_subr: maintain sorted tailq

Summary

Pctries are based on unsigned index values. Type daddr_t is signed. Using daddr_t as an index type for a pctrie works, except that the pctrie considers negative values greater than nonnegative ones. Building a sorted tailq of bufs, based on pctrie results, sorts negative daddr_ts larger than nonnegative ones, and makes code that depends on the tailq being actually sorted broken.

Write wrappers for the functions that do pctrie operations that depend on index ordering that fix the order problem, and use them in place of direct pctrie operations.

Test Plan

The ext3fs.sh stress test that failed before works again.

Diff Detail

Repository

rG FreeBSD src repository

Lint

Lint Not Applicable

Unit

Tests Not Applicable

Event Timeline

dougm requested review of this revision.Oct 19 2024, 5:08 PM

dougm created this revision.

Addresses this bug: https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=282134

May be, instead, allow to specify type of the trie in the TRIE macros?

In D47200#1076214, @kib wrote:

May be, instead, allow to specify type of the trie in the TRIE macros?

You could pass an extra argument to all the functions that compare indices, such as pctrie_lookup_ge_node, to indicate whether they could compare two values normally, or with their high-order bits flipped, and you'd flip those bits for signed indices. There would be a runtime cost. Or you could have each function replaced by a pair of functions, one for signed and the other for unsigned, and pick the functions to use in macros. It would be tough.

In D47200#1076223, @dougm wrote:

In D47200#1076214, @kib wrote:

May be, instead, allow to specify type of the trie in the TRIE macros?

You could pass an extra argument to all the functions that compare indices, such as pctrie_lookup_ge_node, to indicate whether they could compare two values normally, or with their high-order bits flipped, and you'd flip those bits for signed indices. There would be a runtime cost. Or you could have each function replaced by a pair of functions, one for signed and the other for unsigned, and pick the functions to use in macros. It would be tough.

What I proposed is close to the second option. But ok.

sys/kern/vfs_subr.c
551	Suppose that we have the buffers with indexes 3 and -4 on queue (and no other), and looking up a buffer with the index >= -2. Then the LOKUP_GE(-2) returns NULL, and the second LOOKUP_GE(0) returns the buffer with the index -4. Am I wrong?

This revision is now accepted and ready to land.Oct 19 2024, 10:12 PM

In D47200#1076225, @kib wrote:

What I proposed is close to the second option. But ok.

Do we even need the unsigned version? If we changed to handle only int64_t type, would anybody notice? Is anybody inserting keys >= 2**63?

sys/kern/vfs_subr.c
551	The second LOOKUP_GE(0) return the buffer with the index 3.

kib added inline comments.Oct 19 2024, 10:41 PM

sys/kern/vfs_subr.c
551	Sorry, it should be 'with indexes -3 and -4' in the original comment.

dougm added inline comments.Oct 19 2024, 10:56 PM

sys/kern/vfs_subr.c
551	Right. I'll drop the else.

Drop an 'else' to fix a wraparound bug identified by @kib.

This revision now requires review to proceed.Oct 19 2024, 10:57 PM

kib accepted this revision.Oct 19 2024, 11:20 PM

This revision is now accepted and ready to land.Oct 19 2024, 11:20 PM

I'm running tests with both D47150.145188.patch and D47200.145189.patch. I'll be running a full set of stress2 tests, which takes about 60 hours.
No problems seen in the first 8 hours.

pho mentioned this in D47150: swap_pager: move scan_all_shadowed, use pctrie iterators.Oct 20 2024, 8:06 AM

markj accepted this revision.Oct 21 2024, 3:07 PM

In D47200#1076295, @pho wrote:

I'm running tests with both D47150.145188.patch and D47200.145189.patch. I'll be running a full set of stress2 tests, which takes about 60 hours.
No problems seen in the first 8 hours.

I completed a full stress2 test without seeing any issues.

Closed by commit rGe2414d91d33f: vfs_subr: maintain sorted tailq (authored by dougm). · Explain WhyOct 22 2024, 9:59 PM

This revision was automatically updated to reflect the committed changes.

dougm added a commit: rGe2414d91d33f: vfs_subr: maintain sorted tailq.

Herald added subscribers: olce, imp. · View Herald TranscriptOct 22 2024, 9:59 PM