On Wed, Jan 29, 2025 at 10:30 PM Kent Overstreet kent.overstreet@linux.dev wrote:
On Wed, Jan 29, 2025 at 10:21:31PM +0100, Andreas Gruenbacher wrote:
On Wed, Jan 29, 2025 at 9:28 PM Kent Overstreet kent.overstreet@linux.dev wrote:
On Wed, Jan 29, 2025 at 07:21:49PM +0100, Andreas Gruenbacher wrote:
On Wed, Jan 29, 2025 at 7:04 PM Kent Overstreet kent.overstreet@linux.dev wrote:
On Tue, Jan 28, 2025 at 05:38:48PM +0100, Andreas Gruenbacher wrote:
Rename eytzinger0_find_test_val() to eytzinger0_find_test_le() and add a new eytzinger0_find_test_val() wrapper that calls it.
We have already established that the array is sorted in eytzinger order, so we can use the eytzinger iterator functions and check the boundary conditions to verify the result of eytzinger0_find_le().
Only scan the entire array if we get an incorrect result. When we need to scan, use eytzinger0_for_each_prev() so that we'll stop at the highest matching element in the array in case there are duplicates; going through the array linearly wouldn't give us that.
For test code, wouldn't it be simpler to iterate over the test array, testing with every element as a search value? There's enough corner cases in lookup that I think it'd be worthwhile (and probably add some extra test values, e.g. first/last elements +1/-1).
If you expect to get the same index back, that won't work when there are duplicates.
No, but we wouldn't expect to get the same index back if we're testing every combination of elements (+0, -1, +1) x (le, ge, gt) - and it sounds like perhaps we should, if you've been finding bugs. Thoughts?
I don't really know what you're after here. Function eytzinger0_find_test() already tests every combination of elements (+0, -1, +1) x (le, ge, gt).
Ok - it can be hard to tell looking at isolated patches vs. being able to fetch a git repo. Do you have it in a branch I can fetch from?
The full scans of the array in eytzinger0_find_test_{le,gt,ge}() are not there to verify correctness; they're only there to produce slightly nicer debug output. I'm perfectly happy with removing that if you prefer.
No, not at all
I think the test code would have to do short linear searches from the test element, and then verify the search functions against that.
What for? We already know from the eytzinger0_for_each loop in eytzinger0_find_test() that the array is in eytzinger sort order, and we also know from eytzinger{0,1}_test() that the _prev() and _next() functions are doing "the right thing". So the one thing left to verify in eytzinger0_find_test_{le,gt,ge}() is that all the search functions always return the boundary element. That's done by going to the next element in search order and by verifying that it no longer fulfils the search criterion.
Have you spotted any issues with searching over arrays with duplicate elements?
Only that eytzinger0_find_ge() didn't always find the first matching element in the array; see patches 17 and 18.
Gotcha
Ok, it sounds like everything I'm after is there - give me a git branch so I can read through it that way and I'll be happy to merge when you say it's ready
Sure, I've pushed the patches here:
https://git.kernel.org/pub/scm/linux/kernel/git/agruen/linux.git/log/?h=bcac...
Note that you don't want to merge the following patch:
bcachefs: Run the eytzinger tests on modprobe
And this minor one should probably be changed to use __maybe_unused or dropped; not sure which of the two options you prefer:
bcachefs: remove dead code in is_aligned
I've only run the self tests. They seem to provide good coverage and I don't expect any trouble, but some real filesystem testing would be great.
Thanks, Andreas