On Wed, Jan 29, 2025 at 10:30 PM Kent Overstreet
<kent.overstreet@xxxxxxxxx> 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@xxxxxxxxx> 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@xxxxxxxxx> 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=bcachefs
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
