vfs_subr: maintain sorted tailq

[dougm]

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.

[dougm]

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

[kib]

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

[dougm]

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.

[kib]

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?

[dougm]

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]

sys/kern/vfs_subr.c

551

Sorry, it should be 'with indexes -3 and -4' in the original comment.

[dougm]

sys/kern/vfs_subr.c

551

Right. I'll drop the else.

[dougm]

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

[pho]

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]

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.