On Mon, Nov 25, 2024 at 12:33:10AM +0100, Andreas Gruenbacher wrote: > On Sun, Nov 24, 2024 at 8:24 PM Kent Overstreet > <[email protected]> wrote: > > On Sun, Nov 24, 2024 at 02:11:47PM +0100, Andreas Gruenbacher wrote: > > > From: Andreas Gruenbacher <[email protected]> > > > > > > In this place in the code, eytzinger1_next() is trying to move the > > > lowest child on the left, which is equivalent to doubling i until the > > > next doubling would cause it to be greater than size. This is > > > implemented by shifting i to the left so that the most significant bits > > > of both numbers align, and then shifting i right by one if it is greater > > > than size. > > > > > > The code accidentally computes the most significant bit of (size + 1) > > > instead of size. This happens to be harmless because in that case, the > > > right shifting will compensate, but it is confusing and unnecessary. > > > > > > Likewise, eytzinger1_prev() is trying to move the lowest child on the > > > right. The same applies here. > > > > > > Signed-off-by: Andreas Gruenbacher <[email protected]> > > > > Looks correct. There's eytzinger tests in fs/bcachefs/util.c, could you > > run those? > > Hmm, this actually breaks the following tests in util.c: > > BUG_ON(eytzinger1_prev(0, size) != eytzinger1_last(size)); > BUG_ON(eytzinger0_prev(-1, size) != eytzinger0_last(size)); > > The inverse tests are fine: > > BUG_ON(eytzinger1_next(0, size) != eytzinger1_first(size)); > BUG_ON(eytzinger0_next(-1, size) != eytzinger0_first(size)); > > And so are all the other tests. > > Are those identities actually relevant, or are they just a > peculiarity? Do they justify an additional addition in > eytzinger1_prev()?
I think they can be considered a peculiarity we can drop, since 0 isn't a valid element for eytzinger1, and the same for -1 and eytzinger0. > Note that these tests rely on the behavior of __fls(0), which is > undefined. On x86_64, __fls(0) returns (long unsigned int)-1. That's another point in favor of dropping them. We'll need to be careful with that and do some code auditing or add new debug asserts, since there are other identities we rely on (e.g. for eytzinger_for_each() and likely elsewhere).
