Kent, to continue our discussion from last November, I've gone through more parts of the eytzinger code and as a result, here are some patches for you to consider.
What I've not looked at are the eytzinger_to_inorder and inorder_to_eytzinger functions, as well as the implementation of sort. Those functions could use a bit more documentation, but the code iself looks reasonable.
Shuah, I've also had a quick look at converting the tests into kernel selftests, but that hasn't gone very far because of the lack of support for basic functions like __fls(), __ffs(), ffz(), and rounddown_pow_of_two() in selftests. Are there any plans for making those kinds of primitives generally available to selftests?
Thanks, Andreas
Andreas Gruenbacher (21): bcachefs: remove dead code in is_aligned bcachefs: bch2_blacklist_entries_gc cleanup bcachefs: Run the eytzinger tests on modprobe bcachefs: EYTZINGER_DEBUG fix bcachefs: eytzinger self tests: eytzinger0_for_each loop cleanups bcachefs: eytzinger self tests: missing newline termination bcachefs: eytzinger self tests: fix cmp_u16 typo bcachefs: eytzinger[01]_test improvement bcachefs: eytzinger0_find_test improvement bcachefs: add eytzinger0_for_each_prev bcachefs: improve the eytzinger0_find_le tests bcachefs: convert eytzinger0_find to be 1-based bcachefs: convert eytzinger0_find_le to be 1-based bcachefs: simplify eytzinger0_find_le bcachefs: add eytzinger0_find_gt tests bcachefs: implement eytzinger0_find_gt directly bcachefs: add eytzinger0_find_ge tests bcachefs: implement eytzinger0_find_ge directly bcachefs: convert eytzinger sort to be 1-based (1) bcachefs: convert eytzinger sort to be 1-based (2) bcachefs: eytzinger1_{next,prev} cleanup
fs/bcachefs/eytzinger.c | 89 +++++++------- fs/bcachefs/eytzinger.h | 99 +++++++-------- fs/bcachefs/journal_seq_blacklist.c | 7 +- fs/bcachefs/super.c | 5 + fs/bcachefs/util.c | 183 +++++++++++++++++++++------- fs/bcachefs/util.h | 4 + 6 files changed, 240 insertions(+), 147 deletions(-)
This statement does nothing.
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/eytzinger.c | 1 - 1 file changed, 1 deletion(-)
diff --git a/fs/bcachefs/eytzinger.c b/fs/bcachefs/eytzinger.c index 2eaffe37b5e7..c0fdfe909cf2 100644 --- a/fs/bcachefs/eytzinger.c +++ b/fs/bcachefs/eytzinger.c @@ -20,7 +20,6 @@ static bool is_aligned(const void *base, size_t size, unsigned char align) { unsigned char lsbits = (unsigned char)size;
- (void)base; #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS lsbits |= (unsigned char)(uintptr_t)base; #endif
Hello Andreas,
On 2025-01-28 17:38, Andreas Gruenbacher wrote:
This statement does nothing.
I would suggest this statement does nothing only in the case of #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS.
In the case where CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS _is_ defined, it tells the compiler that it should not emit a warning for an unused parameter.
Perhaps it should be moved in to an #else of the #ifndef in order to more clearly communicate that it is expected and okay to ignore this parameter in this case.
Cheers, -Eric
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com
fs/bcachefs/eytzinger.c | 1 - 1 file changed, 1 deletion(-)
diff --git a/fs/bcachefs/eytzinger.c b/fs/bcachefs/eytzinger.c index 2eaffe37b5e7..c0fdfe909cf2 100644 --- a/fs/bcachefs/eytzinger.c +++ b/fs/bcachefs/eytzinger.c @@ -20,7 +20,6 @@ static bool is_aligned(const void *base, size_t size, unsigned char align) { unsigned char lsbits = (unsigned char)size;
- (void)base; #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS lsbits |= (unsigned char)(uintptr_t)base; #endif
On Wed, Jan 29, 2025 at 11:32 AM Eric Herman eric@commonscaretakers.com wrote:
Hello Andreas,
On 2025-01-28 17:38, Andreas Gruenbacher wrote:
This statement does nothing.
I would suggest this statement does nothing only in the case of #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS.
In the case where CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS _is_ defined, it tells the compiler that it should not emit a warning for an unused parameter.
Perhaps it should be moved in to an #else of the #ifndef in order to more clearly communicate that it is expected and okay to ignore this parameter in this case.
How about declaring base __maybe_unused?
Thanks, Andreas
Cheers, -Eric
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com
fs/bcachefs/eytzinger.c | 1 - 1 file changed, 1 deletion(-)
diff --git a/fs/bcachefs/eytzinger.c b/fs/bcachefs/eytzinger.c index 2eaffe37b5e7..c0fdfe909cf2 100644 --- a/fs/bcachefs/eytzinger.c +++ b/fs/bcachefs/eytzinger.c @@ -20,7 +20,6 @@ static bool is_aligned(const void *base, size_t size, unsigned char align) { unsigned char lsbits = (unsigned char)size;
(void)base;
Hello Andreas,
On 2025-01-29 14:19, Andreas Gruenbacher wrote:
On Wed, Jan 29, 2025 at 11:32 AM Eric Herman eric@commonscaretakers.com wrote:
Hello Andreas,
On 2025-01-28 17:38, Andreas Gruenbacher wrote:
This statement does nothing.
I would suggest this statement does nothing only in the case of #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS.
In the case where CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS _is_ defined, it tells the compiler that it should not emit a warning for an unused parameter.
Perhaps it should be moved in to an #else of the #ifndef in order to more clearly communicate that it is expected and okay to ignore this parameter in this case.
How about declaring base __maybe_unused?
Yes, that would be better.
Cheers,
-Eric
Thanks, Andreas
Cheers, -Eric
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com
fs/bcachefs/eytzinger.c | 1 - 1 file changed, 1 deletion(-)
diff --git a/fs/bcachefs/eytzinger.c b/fs/bcachefs/eytzinger.c index 2eaffe37b5e7..c0fdfe909cf2 100644 --- a/fs/bcachefs/eytzinger.c +++ b/fs/bcachefs/eytzinger.c @@ -20,7 +20,6 @@ static bool is_aligned(const void *base, size_t size, unsigned char align) { unsigned char lsbits = (unsigned char)size;
(void)base;
Use an eytzinger0_for_each loop here.
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/journal_seq_blacklist.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-)
diff --git a/fs/bcachefs/journal_seq_blacklist.c b/fs/bcachefs/journal_seq_blacklist.c index 1f25c111c54c..e463d2d95359 100644 --- a/fs/bcachefs/journal_seq_blacklist.c +++ b/fs/bcachefs/journal_seq_blacklist.c @@ -231,15 +231,14 @@ bool bch2_blacklist_entries_gc(struct bch_fs *c) struct journal_seq_blacklist_table *t = c->journal_seq_blacklist_table; BUG_ON(nr != t->nr);
- unsigned i; - for (src = bl->start, i = t->nr == 0 ? 0 : eytzinger0_first(t->nr); - src < bl->start + nr; - src++, i = eytzinger0_next(i, nr)) { + src = bl->start; + eytzinger0_for_each(i, nr) { BUG_ON(t->entries[i].start != le64_to_cpu(src->start)); BUG_ON(t->entries[i].end != le64_to_cpu(src->end));
if (t->entries[i].dirty || t->entries[i].end >= c->journal.oldest_seq_found_ondisk) *dst++ = *src; + src++; }
unsigned new_nr = dst - bl->start;
FOR DEBUGGING ONLY -- DO NOT MERGE!
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/eytzinger.c | 12 +++--------- fs/bcachefs/eytzinger.h | 4 ++++ fs/bcachefs/super.c | 5 +++++ fs/bcachefs/util.c | 2 +- fs/bcachefs/util.h | 4 ++++ 5 files changed, 17 insertions(+), 10 deletions(-)
diff --git a/fs/bcachefs/eytzinger.c b/fs/bcachefs/eytzinger.c index c0fdfe909cf2..08549ab3c18e 100644 --- a/fs/bcachefs/eytzinger.c +++ b/fs/bcachefs/eytzinger.c @@ -242,7 +242,7 @@ void eytzinger0_sort(void *base, size_t n, size_t size, return eytzinger0_sort_r(base, n, size, _CMP_WRAPPER, SWAP_WRAPPER, &w); }
-#if 0 +#if 1 #include <linux/slab.h> #include <linux/random.h> #include <linux/ktime.h> @@ -263,7 +263,7 @@ static int mycmp(const void *a, const void *b) return 0; }
-static int test(void) +void eytzinger_sort_test(void) { size_t N, i; ktime_t start, end; @@ -288,17 +288,11 @@ static int test(void) u32 prev = 0;
eytzinger0_for_each(i, N) { - if (prev > arr[i]) - goto err; + BUG_ON(prev > arr[i]); prev = arr[i]; }
kfree(arr); } - return 0; - -err: - kfree(arr); - return -1; } #endif diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index 0541192d7bc0..16303908ccff 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -5,6 +5,8 @@ #include <linux/bitops.h> #include <linux/log2.h>
+#define EYTZINGER_DEBUG + #ifdef EYTZINGER_DEBUG #define EYTZINGER_BUG_ON(cond) BUG_ON(cond) #else @@ -316,4 +318,6 @@ void eytzinger0_sort_r(void *, size_t, size_t, cmp_r_func_t, swap_r_func_t, const void *); void eytzinger0_sort(void *, size_t, size_t, cmp_func_t, swap_func_t);
+void eytzinger_sort_test(void); + #endif /* _EYTZINGER_H */ diff --git a/fs/bcachefs/super.c b/fs/bcachefs/super.c index a6ed9a0bf1c7..d8ad43fb48fc 100644 --- a/fs/bcachefs/super.c +++ b/fs/bcachefs/super.c @@ -2120,6 +2120,11 @@ static int __init bcachefs_init(void) { bch2_bkey_pack_test();
+ eytzinger_sort_test(); + eytzinger1_test(); + eytzinger0_test(); + eytzinger0_find_test(); + if (!(bcachefs_kset = kset_create_and_add("bcachefs", NULL, fs_kobj)) || bch2_btree_key_cache_init() || bch2_chardev_init() || diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index e0a876cbaa6b..9a63d971ee65 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -698,7 +698,7 @@ void memcpy_from_bio(void *dst, struct bio *src, struct bvec_iter src_iter) } }
-#if 0 +#if 1 void eytzinger1_test(void) { unsigned inorder, eytz, size; diff --git a/fs/bcachefs/util.h b/fs/bcachefs/util.h index fb02c1c36004..b963c523f5d7 100644 --- a/fs/bcachefs/util.h +++ b/fs/bcachefs/util.h @@ -696,4 +696,8 @@ static inline bool test_bit_le64(size_t bit, __le64 *addr) return (addr[bit / 64] & cpu_to_le64(BIT_ULL(bit % 64))) != 0; }
+void eytzinger1_test(void); +void eytzinger0_test(void); +void eytzinger0_find_test(void); + #endif /* _BCACHEFS_UTIL_H */
When EYTZINGER_DEBUG is defined, <linux/bug.h> needs to be included.
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/eytzinger.h | 1 + 1 file changed, 1 insertion(+)
diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index 16303908ccff..6fa6d51a5420 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -8,6 +8,7 @@ #define EYTZINGER_DEBUG
#ifdef EYTZINGER_DEBUG +#include <linux/bug.h> #define EYTZINGER_BUG_ON(cond) BUG_ON(cond) #else #define EYTZINGER_BUG_ON(cond)
The iterator variable of eytzinger0_for_each loops has been changed to be locally scoped at some point, so remove variables defined outside the loop that are now unused. In addition and for clarity, use a different variable inside those loops where an outside variable would be shadowed.
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/util.c | 22 +++++++++++----------- 1 file changed, 11 insertions(+), 11 deletions(-)
diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 9a63d971ee65..58a7b962847d 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -473,10 +473,10 @@ void bch2_time_stats_to_text(struct printbuf *out, struct bch2_time_stats *stats u64 last_q = 0;
prt_printf(out, "quantiles (%s):\t", u->name); - eytzinger0_for_each(i, NR_QUANTILES) { - bool is_last = eytzinger0_next(i, NR_QUANTILES) == -1; + eytzinger0_for_each(j, NR_QUANTILES) { + bool is_last = eytzinger0_next(j, NR_QUANTILES) == -1;
- u64 q = max(quantiles->entries[i].m, last_q); + u64 q = max(quantiles->entries[j].m, last_q); prt_printf(out, "%llu ", div64_u64(q, u->nsecs)); if (is_last) prt_newline(out); @@ -701,7 +701,7 @@ void memcpy_from_bio(void *dst, struct bio *src, struct bvec_iter src_iter) #if 1 void eytzinger1_test(void) { - unsigned inorder, eytz, size; + unsigned inorder, size;
pr_info("1 based eytzinger test:");
@@ -734,7 +734,7 @@ void eytzinger1_test(void) void eytzinger0_test(void) {
- unsigned inorder, eytz, size; + unsigned inorder, size;
pr_info("0 based eytzinger test:");
@@ -764,7 +764,7 @@ void eytzinger0_test(void) } }
-static inline int cmp_u16(const void *_l, const void *_r, size_t size) +static inline int cmp_u16(const void *_l, const void *_r) { const u16 *l = _l, *r = _r;
@@ -787,8 +787,8 @@ static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) c2 = test_array[i];
if (c1 != c2) { - eytzinger0_for_each(i, nr) - pr_info("[%3u] = %12u", i, test_array[i]); + eytzinger0_for_each(j, nr) + pr_info("[%3u] = %12u", j, test_array[j]); pr_info("find_le(%2u) -> [%2zi] = %2i should be %2i", i, r, c1, c2); } @@ -806,9 +806,9 @@ void eytzinger0_find_test(void) eytzinger0_sort(test_array, nr, sizeof(test_array[0]), cmp_u16, NULL);
/* verify array is sorted correctly: */ - eytzinger0_for_each(i, nr) - BUG_ON(i != eytzinger0_last(nr) && - test_array[i] > test_array[eytzinger0_next(i, nr)]); + eytzinger0_for_each(j, nr) + BUG_ON(j != eytzinger0_last(nr) && + test_array[j] > test_array[eytzinger0_next(j, nr)]);
for (i = 0; i < U16_MAX; i += 1 << 12) eytzinger0_find_test_val(test_array, nr, i);
pr_info() format strings need to be newline terminated.
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/util.c | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-)
diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 58a7b962847d..7cf319290a88 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -703,7 +703,7 @@ void eytzinger1_test(void) { unsigned inorder, size;
- pr_info("1 based eytzinger test:"); + pr_info("1 based eytzinger test:\n");
for (size = 2; size < 65536; @@ -711,7 +711,7 @@ void eytzinger1_test(void) unsigned extra = eytzinger1_extra(size);
if (!(size % 4096)) - pr_info("tree size %u", size); + pr_info("tree size %u\n", size);
BUG_ON(eytzinger1_prev(0, size) != eytzinger1_last(size)); BUG_ON(eytzinger1_next(0, size) != eytzinger1_first(size)); @@ -736,7 +736,7 @@ void eytzinger0_test(void)
unsigned inorder, size;
- pr_info("0 based eytzinger test:"); + pr_info("0 based eytzinger test:\n");
for (size = 1; size < 65536; @@ -744,7 +744,7 @@ void eytzinger0_test(void) unsigned extra = eytzinger0_extra(size);
if (!(size % 4096)) - pr_info("tree size %u", size); + pr_info("tree size %u\n", size);
BUG_ON(eytzinger0_prev(-1, size) != eytzinger0_last(size)); BUG_ON(eytzinger0_next(-1, size) != eytzinger0_first(size)); @@ -788,8 +788,8 @@ static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search)
if (c1 != c2) { eytzinger0_for_each(j, nr) - pr_info("[%3u] = %12u", j, test_array[j]); - pr_info("find_le(%2u) -> [%2zi] = %2i should be %2i", + pr_info("[%3u] = %12u\n", j, test_array[j]); + pr_info("find_le(%2u) -> [%2zi] = %2i should be %2i\n", i, r, c1, c2); } } @@ -800,7 +800,7 @@ void eytzinger0_find_test(void) u16 *test_array = kmalloc_array(allocated, sizeof(test_array[0]), GFP_KERNEL);
for (nr = 1; nr < allocated; nr++) { - pr_info("testing %u elems", nr); + pr_info("testing %u elems\n", nr);
get_random_bytes(test_array, nr * sizeof(test_array[0])); eytzinger0_sort(test_array, nr, sizeof(test_array[0]), cmp_u16, NULL);
Fix an obvious typo in cmp_u16().
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/util.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 7cf319290a88..0ffbd22d3a5e 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -768,7 +768,7 @@ static inline int cmp_u16(const void *_l, const void *_r) { const u16 *l = _l, *r = _r;
- return (*l > *r) - (*r - *l); + return (*l > *r) - (*r > *l); }
static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search)
In eytzinger[01]_test(), make sure that eytzinger[01]_for_each() iterates over all array elements.
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/util.c | 2 ++ 1 file changed, 2 insertions(+)
diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 0ffbd22d3a5e..4122012ddfb2 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -728,6 +728,7 @@ void eytzinger1_test(void)
inorder++; } + BUG_ON(inorder - 1 != size); } }
@@ -761,6 +762,7 @@ void eytzinger0_test(void)
inorder++; } + BUG_ON(inorder != size); } }
In eytzinger0_find_test(), remember the smallest element seen so far instead of comparing adjacent array elements.
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/util.c | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-)
diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 4122012ddfb2..87502e1ac7ce 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -802,15 +802,18 @@ void eytzinger0_find_test(void) u16 *test_array = kmalloc_array(allocated, sizeof(test_array[0]), GFP_KERNEL);
for (nr = 1; nr < allocated; nr++) { + u16 prev = 0; + pr_info("testing %u elems\n", nr);
get_random_bytes(test_array, nr * sizeof(test_array[0])); eytzinger0_sort(test_array, nr, sizeof(test_array[0]), cmp_u16, NULL);
/* verify array is sorted correctly: */ - eytzinger0_for_each(j, nr) - BUG_ON(j != eytzinger0_last(nr) && - test_array[j] > test_array[eytzinger0_next(j, nr)]); + eytzinger0_for_each(j, nr) { + BUG_ON(test_array[j] < prev); + prev = test_array[j]; + }
for (i = 0; i < U16_MAX; i += 1 << 12) eytzinger0_find_test_val(test_array, nr, i);
Add an eytzinger0_for_each_prev() macro for iterating through an eytzinger array in reverse.
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/eytzinger.h | 5 +++++ fs/bcachefs/util.c | 9 +++++++++ 2 files changed, 14 insertions(+)
diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index 6fa6d51a5420..f25c895aa184 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -246,6 +246,11 @@ static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size) (_i) != -1; \ (_i) = eytzinger0_next((_i), (_size)))
+#define eytzinger0_for_each_prev(_i, _size) \ + for (unsigned (_i) = eytzinger0_last((_size)); \ + (_i) != -1; \ + (_i) = eytzinger0_prev((_i), (_size))) + /* return greatest node <= @search, or -1 if not found */ static inline int eytzinger0_find_le(void *base, size_t nr, size_t size, cmp_func_t cmp, const void *search) diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 87502e1ac7ce..3fe9a3b8c696 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -763,6 +763,15 @@ void eytzinger0_test(void) inorder++; } BUG_ON(inorder != size); + + inorder = size - 1; + eytzinger0_for_each_prev(eytz, size) { + BUG_ON(eytz != eytzinger0_first(size) && + eytzinger0_next(eytzinger0_prev(eytz, size), size) != eytz); + + inorder--; + } + BUG_ON(inorder != -1); } }
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.
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/util.c | 41 ++++++++++++++++++++++++++++++----------- 1 file changed, 30 insertions(+), 11 deletions(-)
diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 3fe9a3b8c696..c772629783f3 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -782,29 +782,48 @@ static inline int cmp_u16(const void *_l, const void *_r) return (*l > *r) - (*r > *l); }
-static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) +static void eytzinger0_find_test_le(u16 *test_array, unsigned nr, u16 search) { - int i, c1 = -1, c2 = -1; - ssize_t r; + int r, s; + bool bad;
r = eytzinger0_find_le(test_array, nr, sizeof(test_array[0]), cmp_u16, &search); - if (r >= 0) - c1 = test_array[r]; + if (r >= 0) { + if (test_array[r] > search) { + bad = true; + } else { + s = eytzinger0_next(r, nr); + bad = s >= 0 && test_array[s] <= search; + } + } else { + s = eytzinger0_last(nr); + bad = s >= 0 && test_array[s] <= search; + }
- for (i = 0; i < nr; i++) - if (test_array[i] <= search && test_array[i] > c2) - c2 = test_array[i]; + if (bad) { + s = -1; + eytzinger0_for_each_prev(j, nr) { + if (test_array[j] <= search) { + s = j; + break; + } + }
- if (c1 != c2) { eytzinger0_for_each(j, nr) pr_info("[%3u] = %12u\n", j, test_array[j]); - pr_info("find_le(%2u) -> [%2zi] = %2i should be %2i\n", - i, r, c1, c2); + pr_info("find_le(%12u) = %3i should be %3i\n", + search, r, s); + BUG(); } }
+static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) +{ + eytzinger0_find_test_le(test_array, nr, search); +} + void eytzinger0_find_test(void) { unsigned i, nr, allocated = 1 << 12;
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 emelements +1/-1).
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com
fs/bcachefs/util.c | 41 ++++++++++++++++++++++++++++++----------- 1 file changed, 30 insertions(+), 11 deletions(-)
diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 3fe9a3b8c696..c772629783f3 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -782,29 +782,48 @@ static inline int cmp_u16(const void *_l, const void *_r) return (*l > *r) - (*r > *l); } -static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) +static void eytzinger0_find_test_le(u16 *test_array, unsigned nr, u16 search) {
- int i, c1 = -1, c2 = -1;
- ssize_t r;
- int r, s;
- bool bad;
r = eytzinger0_find_le(test_array, nr, sizeof(test_array[0]), cmp_u16, &search);
- if (r >= 0)
c1 = test_array[r];
- if (r >= 0) {
if (test_array[r] > search) {bad = true;} else {s = eytzinger0_next(r, nr);bad = s >= 0 && test_array[s] <= search;}- } else {
s = eytzinger0_last(nr);bad = s >= 0 && test_array[s] <= search;- }
- for (i = 0; i < nr; i++)
if (test_array[i] <= search && test_array[i] > c2)c2 = test_array[i];
- if (bad) {
s = -1;eytzinger0_for_each_prev(j, nr) {if (test_array[j] <= search) {s = j;break;}}
- if (c1 != c2) { eytzinger0_for_each(j, nr) pr_info("[%3u] = %12u\n", j, test_array[j]);
pr_info("find_le(%2u) -> [%2zi] = %2i should be %2i\n",i, r, c1, c2);
pr_info("find_le(%12u) = %3i should be %3i\n",search, r, s);BUG();} +static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) +{
- eytzinger0_find_test_le(test_array, nr, search);
+}
void eytzinger0_find_test(void) { unsigned i, nr, allocated = 1 << 12; -- 2.48.1
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.
Andreas
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com
fs/bcachefs/util.c | 41 ++++++++++++++++++++++++++++++----------- 1 file changed, 30 insertions(+), 11 deletions(-)
diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 3fe9a3b8c696..c772629783f3 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -782,29 +782,48 @@ static inline int cmp_u16(const void *_l, const void *_r) return (*l > *r) - (*r > *l); }
-static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) +static void eytzinger0_find_test_le(u16 *test_array, unsigned nr, u16 search) {
int i, c1 = -1, c2 = -1;ssize_t r;
int r, s;bool bad; r = eytzinger0_find_le(test_array, nr, sizeof(test_array[0]), cmp_u16, &search);
if (r >= 0)c1 = test_array[r];
if (r >= 0) {if (test_array[r] > search) {bad = true;} else {s = eytzinger0_next(r, nr);bad = s >= 0 && test_array[s] <= search;}} else {s = eytzinger0_last(nr);bad = s >= 0 && test_array[s] <= search;}
for (i = 0; i < nr; i++)if (test_array[i] <= search && test_array[i] > c2)c2 = test_array[i];
if (bad) {s = -1;eytzinger0_for_each_prev(j, nr) {if (test_array[j] <= search) {s = j;break;}}
if (c1 != c2) { eytzinger0_for_each(j, nr) pr_info("[%3u] = %12u\n", j, test_array[j]);pr_info("find_le(%2u) -> [%2zi] = %2i should be %2i\n",i, r, c1, c2);
pr_info("find_le(%12u) = %3i should be %3i\n",search, r, s);BUG(); }}
+static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) +{
eytzinger0_find_test_le(test_array, nr, search);+}
void eytzinger0_find_test(void) { unsigned i, nr, allocated = 1 << 12; -- 2.48.1
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 think the test code would have to do short linear searches from the test element, and then verify the search functions against that.
Have you spotted any issues with searching over arrays with duplicate elements?
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).
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.
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.
Thanks, Andreas
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
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
On Thu, Jan 30, 2025 at 12:17:51AM +0100, Andreas Gruenbacher wrote:
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
That code is a cut and paste of sort.c, so we should just drop it - no reason for those to diverge (and perhaps add a giant comment on where it's from).
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.
I've fetched it to my repo and added it to the CI:
https://evilpiepirate.org/~testdashboard/ci?user=kmo&branch=eytzinger
On Thu, Jan 30, 2025 at 12:36 AM Kent Overstreet kent.overstreet@linux.dev wrote:
I've fetched it to my repo and added it to the CI:
https://evilpiepirate.org/~testdashboard/ci?user=kmo&branch=eytzinger
Ah, the following went wrong in "bcachefs: convert eytzinger0_find to be 1-based":
diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index d3e8b9edf335..3afb346b0738 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -308,7 +308,7 @@ static inline int eytzinger0_find_ge(void *base, size_t nr, size_t size, #define eytzinger0_find(base, nr, size, _cmp, search) \ ({ \ size_t _size = (size); \ - void *_base1 = (base) - _size; \ + void *_base1 = (void *)(base) - _size; \ const void *_search = (search); \ size_t _nr = (nr); \ size_t _i = 1; \
The eytzinger0_find() macro is still a bit of a mess.
I've updated https://git.kernel.org/pub/scm/linux/kernel/git/agruen/linux.git/log/?h=bcac....
Thanks, Andreas
Several of the algorithms on eytzinger trees are implemented in terms of the eytzinger0 primitives. However, those algorithms can just as easily be expressed in terms of the eytzinger1 primitives, and that leads to better and easier to understand code. Start by converting eytzinger0_find().
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/eytzinger.h | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-)
diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index f25c895aa184..d3e8b9edf335 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -307,17 +307,17 @@ static inline int eytzinger0_find_ge(void *base, size_t nr, size_t size,
#define eytzinger0_find(base, nr, size, _cmp, search) \ ({ \ - void *_base = (base); \ + size_t _size = (size); \ + void *_base1 = (base) - _size; \ const void *_search = (search); \ size_t _nr = (nr); \ - size_t _size = (size); \ - size_t _i = 0; \ + size_t _i = 1; \ int _res; \ \ - while (_i < _nr && \ - (_res = _cmp(_search, _base + _i * _size))) \ - _i = eytzinger0_child(_i, _res > 0); \ - _i; \ + while (_i <= _nr && \ + (_res = _cmp(_search, _base1 + _i * _size))) \ + _i = eytzinger1_child(_i, _res > 0); \ + _i - 1; \ })
void eytzinger0_sort_r(void *, size_t, size_t,
eytzinger0_find_le() is also easy to concert to 1-based eytzinger (but see the next commit).
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/eytzinger.h | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-)
diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index d3e8b9edf335..130f5fe30bd7 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -255,27 +255,27 @@ static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size) static inline int eytzinger0_find_le(void *base, size_t nr, size_t size, cmp_func_t cmp, const void *search) { - unsigned i, n = 0; + void *base1 = base - size; + unsigned i, n = 1;
if (!nr) return -1;
do { i = n; - n = eytzinger0_child(i, cmp(base + i * size, search) <= 0); - } while (n < nr); + n = eytzinger1_child(i, cmp(base1 + i * size, search) <= 0); + } while (n <= nr);
- if (n & 1) { + if (!(n & 1)) { /* * @i was greater than @search, return previous node: * * if @i was leftmost/smallest element, - * eytzinger0_prev(eytzinger0_first())) returns -1, as expected + * eytzinger1_prev(eytzinger1_first())) returns 0, as expected */ - return eytzinger0_prev(i, nr); - } else { - return i; + i = eytzinger1_prev(i, nr); } + return i - 1; }
static inline int eytzinger0_find_gt(void *base, size_t nr, size_t size,
Replace the over-complicated implementation of eytzinger0_find_le() by an equivalent, simplifer version.
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/eytzinger.h | 26 ++++++-------------------- 1 file changed, 6 insertions(+), 20 deletions(-)
diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index 130f5fe30bd7..89a0e4192212 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -256,26 +256,12 @@ static inline int eytzinger0_find_le(void *base, size_t nr, size_t size, cmp_func_t cmp, const void *search) { void *base1 = base - size; - unsigned i, n = 1; - - if (!nr) - return -1; - - do { - i = n; - n = eytzinger1_child(i, cmp(base1 + i * size, search) <= 0); - } while (n <= nr); - - if (!(n & 1)) { - /* - * @i was greater than @search, return previous node: - * - * if @i was leftmost/smallest element, - * eytzinger1_prev(eytzinger1_first())) returns 0, as expected - */ - i = eytzinger1_prev(i, nr); - } - return i - 1; + unsigned n = 1; + + while (n <= nr) + n = eytzinger1_child(n, cmp(base1 + n * size, search) <= 0); + n >>= __ffs(n) + 1; + return n - 1; }
static inline int eytzinger0_find_gt(void *base, size_t nr, size_t size,
Add eytzinger0_find_gt() tests similar to the eytzinger0_find_le() tests.
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/util.c | 38 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 38 insertions(+)
diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index c772629783f3..d84632870b56 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -819,9 +819,47 @@ static void eytzinger0_find_test_le(u16 *test_array, unsigned nr, u16 search) } }
+static void eytzinger0_find_test_gt(u16 *test_array, unsigned nr, u16 search) +{ + int r, s; + bool bad; + + r = eytzinger0_find_gt(test_array, nr, + sizeof(test_array[0]), + cmp_u16, &search); + if (r >= 0) { + if (test_array[r] <= search) { + bad = true; + } else { + s = eytzinger0_prev(r, nr); + bad = s >= 0 && test_array[s] > search; + } + } else { + s = eytzinger0_first(nr); + bad = s >= 0 && test_array[s] > search; + } + + if (bad) { + s = -1; + eytzinger0_for_each(j, nr) { + if (test_array[j] > search) { + s = j; + break; + } + } + + eytzinger0_for_each(j, nr) + pr_info("[%3u] = %12u\n", j, test_array[j]); + pr_info("find_gt(%12u) = %3i should be %3i\n", + search, r, s); + BUG(); + } +} + static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) { eytzinger0_find_test_le(test_array, nr, search); + eytzinger0_find_test_gt(test_array, nr, search); }
void eytzinger0_find_test(void)
Instead of implementing eytzinger0_find_gt() in terms of eytzinger0_find_le() and adjusting the result, implement it directly.
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/eytzinger.h | 17 +++++++---------- 1 file changed, 7 insertions(+), 10 deletions(-)
diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index 89a0e4192212..a5a1abae5b13 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -264,20 +264,17 @@ static inline int eytzinger0_find_le(void *base, size_t nr, size_t size, return n - 1; }
+/* return smallest node > @search, or -1 if not found */ static inline int eytzinger0_find_gt(void *base, size_t nr, size_t size, cmp_func_t cmp, const void *search) { - ssize_t idx = eytzinger0_find_le(base, nr, size, cmp, search); + void *base1 = base - size; + unsigned n = 1;
- /* - * if eytitzinger0_find_le() returned -1 - no element was <= search - we - * want to return the first element; next/prev identities mean this work - * as expected - * - * similarly if find_le() returns last element, we should return -1; - * identities mean this all works out: - */ - return eytzinger0_next(idx, nr); + while (n <= nr) + n = eytzinger1_child(n, cmp(base1 + n * size, search) <= 0); + n >>= __ffs(n + 1) + 1; + return n - 1; }
static inline int eytzinger0_find_ge(void *base, size_t nr, size_t size,
Add eytzinger0_find_ge() tests similar to the eytzinger0_find_gt() tests.
Note that the current implementation of eytzinger0_find_ge() doesn't always find the first element >= @search, so the tests will occasionally fail. The next commit fixes that.
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/util.c | 38 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 38 insertions(+)
diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index d84632870b56..e75329399c6e 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -856,10 +856,48 @@ static void eytzinger0_find_test_gt(u16 *test_array, unsigned nr, u16 search) } }
+static void eytzinger0_find_test_ge(u16 *test_array, unsigned nr, u16 search) +{ + int r, s; + bool bad; + + r = eytzinger0_find_ge(test_array, nr, + sizeof(test_array[0]), + cmp_u16, &search); + if (r >= 0) { + if (test_array[r] < search) { + bad = true; + } else { + s = eytzinger0_prev(r, nr); + bad = s >= 0 && test_array[s] >= search; + } + } else { + s = eytzinger0_first(nr); + bad = s >= 0 && test_array[s] >= search; + } + + if (bad) { + s = -1; + eytzinger0_for_each(j, nr) { + if (test_array[j] >= search) { + s = j; + break; + } + } + + eytzinger0_for_each(j, nr) + pr_info("[%3u] = %12u\n", j, test_array[j]); + pr_info("find_ge(%12u) = %3i should be %3i\n", + search, r, s); + BUG(); + } +} + static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) { eytzinger0_find_test_le(test_array, nr, search); eytzinger0_find_test_gt(test_array, nr, search); + eytzinger0_find_test_ge(test_array, nr, search); }
void eytzinger0_find_test(void)
Implement eytzinger0_find_ge() directly instead of implementing it in terms of eytzinger0_find_le() and adjusting the result.
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/eytzinger.h | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-)
diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index a5a1abae5b13..6a363b12bd21 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -277,15 +277,17 @@ static inline int eytzinger0_find_gt(void *base, size_t nr, size_t size, return n - 1; }
+/* return smallest node >= @search, or -1 if not found */ static inline int eytzinger0_find_ge(void *base, size_t nr, size_t size, cmp_func_t cmp, const void *search) { - ssize_t idx = eytzinger0_find_le(base, nr, size, cmp, search); - - if (idx < nr && !cmp(base + idx * size, search)) - return idx; + void *base1 = base - size; + unsigned n = 1;
- return eytzinger0_next(idx, nr); + while (n <= nr) + n = eytzinger1_child(n, cmp(base1 + n * size, search) < 0); + n >>= __ffs(n + 1) + 1; + return n - 1; }
#define eytzinger0_find(base, nr, size, _cmp, search) \
In this first step, convert the eytzinger sort functions to use 1-based primitives.
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/eytzinger.c | 48 +++++++++++++++++++++++++---------------- 1 file changed, 29 insertions(+), 19 deletions(-)
diff --git a/fs/bcachefs/eytzinger.c b/fs/bcachefs/eytzinger.c index 08549ab3c18e..93a5819a6878 100644 --- a/fs/bcachefs/eytzinger.c +++ b/fs/bcachefs/eytzinger.c @@ -147,28 +147,28 @@ static int do_cmp(const void *a, const void *b, cmp_r_func_t cmp, const void *pr return cmp(a, b, priv); }
-static inline int eytzinger0_do_cmp(void *base, size_t n, size_t size, +static inline int eytzinger1_do_cmp(void *base1, size_t n, size_t size, cmp_r_func_t cmp_func, const void *priv, size_t l, size_t r) { - return do_cmp(base + inorder_to_eytzinger0(l, n) * size, - base + inorder_to_eytzinger0(r, n) * size, + return do_cmp(base1 + inorder_to_eytzinger1(l, n) * size, + base1 + inorder_to_eytzinger1(r, n) * size, cmp_func, priv); }
-static inline void eytzinger0_do_swap(void *base, size_t n, size_t size, +static inline void eytzinger1_do_swap(void *base1, size_t n, size_t size, swap_r_func_t swap_func, const void *priv, size_t l, size_t r) { - do_swap(base + inorder_to_eytzinger0(l, n) * size, - base + inorder_to_eytzinger0(r, n) * size, + do_swap(base1 + inorder_to_eytzinger1(l, n) * size, + base1 + inorder_to_eytzinger1(r, n) * size, size, swap_func, priv); }
-void eytzinger0_sort_r(void *base, size_t n, size_t size, - cmp_r_func_t cmp_func, - swap_r_func_t swap_func, - const void *priv) +static void eytzinger1_sort_r(void *base1, size_t n, size_t size, + cmp_r_func_t cmp_func, + swap_r_func_t swap_func, + const void *priv) { int i, j, k;
@@ -177,9 +177,9 @@ void eytzinger0_sort_r(void *base, size_t n, size_t size, swap_func = NULL;
if (!swap_func) { - if (is_aligned(base, size, 8)) + if (is_aligned(base1, size, 8)) swap_func = SWAP_WORDS_64; - else if (is_aligned(base, size, 4)) + else if (is_aligned(base1, size, 4)) swap_func = SWAP_WORDS_32; else swap_func = SWAP_BYTES; @@ -189,47 +189,57 @@ void eytzinger0_sort_r(void *base, size_t n, size_t size, for (i = n / 2 - 1; i >= 0; --i) { /* Find the sift-down path all the way to the leaves. */ for (j = i; k = j * 2 + 1, k + 1 < n;) - j = eytzinger0_do_cmp(base, n, size, cmp_func, priv, k, k + 1) > 0 ? k : k + 1; + j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k + 1, k + 2) > 0 ? k : k + 1;
/* Special case for the last leaf with no sibling. */ if (j * 2 + 2 == n) j = j * 2 + 1;
/* Backtrack to the correct location. */ - while (j != i && eytzinger0_do_cmp(base, n, size, cmp_func, priv, i, j) >= 0) + while (j != i && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, i + 1, j + 1) >= 0) j = (j - 1) / 2;
/* Shift the element into its correct place. */ for (k = j; j != i;) { j = (j - 1) / 2; - eytzinger0_do_swap(base, n, size, swap_func, priv, j, k); + eytzinger1_do_swap(base1, n, size, swap_func, priv, j + 1, k + 1); } }
/* sort */ for (i = n - 1; i > 0; --i) { - eytzinger0_do_swap(base, n, size, swap_func, priv, 0, i); + eytzinger1_do_swap(base1, n, size, swap_func, priv, 1, i + 1);
/* Find the sift-down path all the way to the leaves. */ for (j = 0; k = j * 2 + 1, k + 1 < i;) - j = eytzinger0_do_cmp(base, n, size, cmp_func, priv, k, k + 1) > 0 ? k : k + 1; + j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k + 1, k + 2) > 0 ? k : k + 1;
/* Special case for the last leaf with no sibling. */ if (j * 2 + 2 == i) j = j * 2 + 1;
/* Backtrack to the correct location. */ - while (j && eytzinger0_do_cmp(base, n, size, cmp_func, priv, 0, j) >= 0) + while (j && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, 1, j + 1) >= 0) j = (j - 1) / 2;
/* Shift the element into its correct place. */ for (k = j; j;) { j = (j - 1) / 2; - eytzinger0_do_swap(base, n, size, swap_func, priv, j, k); + eytzinger1_do_swap(base1, n, size, swap_func, priv, j + 1, k + 1); } } }
+void eytzinger0_sort_r(void *base, size_t n, size_t size, + cmp_r_func_t cmp_func, + swap_r_func_t swap_func, + const void *priv) +{ + void *base1 = base - size; + + return eytzinger1_sort_r(base1, n, size, cmp_func, swap_func, priv); +} + void eytzinger0_sort(void *base, size_t n, size_t size, cmp_func_t cmp_func, swap_func_t swap_func)
In this second step, transform the eytzinger indexes i, j, and k in eytzinger1_sort_r() from 0-based to 1-based. This step looks a bit messy, but the resulting code is slightly better.
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/eytzinger.c | 42 ++++++++++++++++++++--------------------- 1 file changed, 21 insertions(+), 21 deletions(-)
diff --git a/fs/bcachefs/eytzinger.c b/fs/bcachefs/eytzinger.c index 93a5819a6878..00cc5f0826e3 100644 --- a/fs/bcachefs/eytzinger.c +++ b/fs/bcachefs/eytzinger.c @@ -170,7 +170,7 @@ static void eytzinger1_sort_r(void *base1, size_t n, size_t size, swap_r_func_t swap_func, const void *priv) { - int i, j, k; + unsigned i, j, k;
/* called from 'sort' without swap function, let's pick the default */ if (swap_func == SWAP_WRAPPER && !((struct wrapper *)priv)->swap_func) @@ -186,46 +186,46 @@ static void eytzinger1_sort_r(void *base1, size_t n, size_t size, }
/* heapify */ - for (i = n / 2 - 1; i >= 0; --i) { + for (i = n / 2; i >= 1; --i) { /* Find the sift-down path all the way to the leaves. */ - for (j = i; k = j * 2 + 1, k + 1 < n;) - j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k + 1, k + 2) > 0 ? k : k + 1; + for (j = i; k = j * 2, k < n;) + j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k, k + 1) > 0 ? k : k + 1;
/* Special case for the last leaf with no sibling. */ - if (j * 2 + 2 == n) - j = j * 2 + 1; + if (j * 2 == n) + j *= 2;
/* Backtrack to the correct location. */ - while (j != i && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, i + 1, j + 1) >= 0) - j = (j - 1) / 2; + while (j != i && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, i, j) >= 0) + j /= 2;
/* Shift the element into its correct place. */ for (k = j; j != i;) { - j = (j - 1) / 2; - eytzinger1_do_swap(base1, n, size, swap_func, priv, j + 1, k + 1); + j /= 2; + eytzinger1_do_swap(base1, n, size, swap_func, priv, j, k); } }
/* sort */ - for (i = n - 1; i > 0; --i) { - eytzinger1_do_swap(base1, n, size, swap_func, priv, 1, i + 1); + for (i = n; i > 1; --i) { + eytzinger1_do_swap(base1, n, size, swap_func, priv, 1, i);
/* Find the sift-down path all the way to the leaves. */ - for (j = 0; k = j * 2 + 1, k + 1 < i;) - j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k + 1, k + 2) > 0 ? k : k + 1; + for (j = 1; k = j * 2, k + 1 < i;) + j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k, k + 1) > 0 ? k : k + 1;
/* Special case for the last leaf with no sibling. */ - if (j * 2 + 2 == i) - j = j * 2 + 1; + if (j * 2 + 1 == i) + j *= 2;
/* Backtrack to the correct location. */ - while (j && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, 1, j + 1) >= 0) - j = (j - 1) / 2; + while (j >= 1 && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, 1, j) >= 0) + j /= 2;
/* Shift the element into its correct place. */ - for (k = j; j;) { - j = (j - 1) / 2; - eytzinger1_do_swap(base1, n, size, swap_func, priv, j + 1, k + 1); + for (k = j; j > 1;) { + j /= 2; + eytzinger1_do_swap(base1, n, size, swap_func, priv, j, k); } } }
On Tue, Jan 28, 2025 at 05:38:57PM +0100, Andreas Gruenbacher wrote:
In this second step, transform the eytzinger indexes i, j, and k in eytzinger1_sort_r() from 0-based to 1-based. This step looks a bit messy, but the resulting code is slightly better.
I really hate the cute and paste of lib/sort.c, I wonder if we could get rid of that by adding a more generic sort that takes an option "index/access element" helper.
I've come across situations where we want to sort radix trees as well, so - maybe?
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com
fs/bcachefs/eytzinger.c | 42 ++++++++++++++++++++--------------------- 1 file changed, 21 insertions(+), 21 deletions(-)
diff --git a/fs/bcachefs/eytzinger.c b/fs/bcachefs/eytzinger.c index 93a5819a6878..00cc5f0826e3 100644 --- a/fs/bcachefs/eytzinger.c +++ b/fs/bcachefs/eytzinger.c @@ -170,7 +170,7 @@ static void eytzinger1_sort_r(void *base1, size_t n, size_t size, swap_r_func_t swap_func, const void *priv) {
- int i, j, k;
- unsigned i, j, k;
/* called from 'sort' without swap function, let's pick the default */ if (swap_func == SWAP_WRAPPER && !((struct wrapper *)priv)->swap_func) @@ -186,46 +186,46 @@ static void eytzinger1_sort_r(void *base1, size_t n, size_t size, } /* heapify */
- for (i = n / 2 - 1; i >= 0; --i) {
- for (i = n / 2; i >= 1; --i) { /* Find the sift-down path all the way to the leaves. */
for (j = i; k = j * 2 + 1, k + 1 < n;)j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k + 1, k + 2) > 0 ? k : k + 1;
for (j = i; k = j * 2, k < n;)j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k, k + 1) > 0 ? k : k + 1;/* Special case for the last leaf with no sibling. */
if (j * 2 + 2 == n)j = j * 2 + 1;
if (j * 2 == n)j *= 2;/* Backtrack to the correct location. */
while (j != i && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, i + 1, j + 1) >= 0)j = (j - 1) / 2;
while (j != i && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, i, j) >= 0)j /= 2;/* Shift the element into its correct place. */ for (k = j; j != i;) {
j = (j - 1) / 2;eytzinger1_do_swap(base1, n, size, swap_func, priv, j + 1, k + 1);
j /= 2;eytzinger1_do_swap(base1, n, size, swap_func, priv, j, k);/* sort */
- for (i = n - 1; i > 0; --i) {
eytzinger1_do_swap(base1, n, size, swap_func, priv, 1, i + 1);
- for (i = n; i > 1; --i) {
eytzinger1_do_swap(base1, n, size, swap_func, priv, 1, i);/* Find the sift-down path all the way to the leaves. */
for (j = 0; k = j * 2 + 1, k + 1 < i;)j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k + 1, k + 2) > 0 ? k : k + 1;
for (j = 1; k = j * 2, k + 1 < i;)j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k, k + 1) > 0 ? k : k + 1;/* Special case for the last leaf with no sibling. */
if (j * 2 + 2 == i)j = j * 2 + 1;
if (j * 2 + 1 == i)j *= 2;/* Backtrack to the correct location. */
while (j && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, 1, j + 1) >= 0)j = (j - 1) / 2;
while (j >= 1 && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, 1, j) >= 0)j /= 2;/* Shift the element into its correct place. */
for (k = j; j;) {j = (j - 1) / 2;eytzinger1_do_swap(base1, n, size, swap_func, priv, j + 1, k + 1);
for (k = j; j > 1;) {j /= 2;eytzinger1_do_swap(base1, n, size, swap_func, priv, j, k);}
2.48.1
From: Andreas Gruenbacher andreas.gruenbacher@gmail.com
The eytzinger code was previously relying on the following wrap-around properties and their "eytzinger0" equivalents:
eytzinger1_prev(0, size) == eytzinger1_last(size) eytzinger1_next(0, size) == eytzinger1_first(size)
However, these properties are no longer relied upon and no longer necessary, so remove the corresponding asserts and forbid the use of eytzinger1_prev(0, size) and eytzinger1_next(0, size).
This allows to further simplify the code in eytzinger1_next() and eytzinger1_prev(): where the left shifting happens, eytzinger1_next() is trying to move i to 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 align and then shifting i to the right by one if the result is greater than size.
Likewise, eytzinger1_prev() is trying to move to the lowest child on the right; the same applies here.
The 1-offset in (size - 1) in eytzinger1_next() isn't needed at all, but the equivalent offset in eytzinger1_prev() is surprisingly needed to preserve the 'eytzinger1_prev(0, size) == eytzinger1_last(size)' property. However, since we no longer support that property, we can get rid of these offsets as well. This saves one addition in each function and makes the code less confusing.
Signed-off-by: Andreas Gruenbacher agruenba@redhat.com --- fs/bcachefs/eytzinger.h | 18 ++++-------------- fs/bcachefs/util.c | 12 ------------ 2 files changed, 4 insertions(+), 26 deletions(-)
diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index 6a363b12bd21..e600a7d52001 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -59,24 +59,14 @@ static inline unsigned eytzinger1_last(unsigned size) return rounddown_pow_of_two(size + 1) - 1; }
-/* - * eytzinger1_next() and eytzinger1_prev() have the nice properties that - * - * eytzinger1_next(0) == eytzinger1_first()) - * eytzinger1_prev(0) == eytzinger1_last()) - * - * eytzinger1_prev(eytzinger1_first()) == 0 - * eytzinger1_next(eytzinger1_last()) == 0 - */ - static inline unsigned eytzinger1_next(unsigned i, unsigned size) { - EYTZINGER_BUG_ON(i > size); + EYTZINGER_BUG_ON(i == 0 || i > size);
if (eytzinger1_right_child(i) <= size) { i = eytzinger1_right_child(i);
- i <<= __fls(size + 1) - __fls(i); + i <<= __fls(size) - __fls(i); i >>= i > size; } else { i >>= ffz(i) + 1; @@ -87,12 +77,12 @@ static inline unsigned eytzinger1_next(unsigned i, unsigned size)
static inline unsigned eytzinger1_prev(unsigned i, unsigned size) { - EYTZINGER_BUG_ON(i > size); + EYTZINGER_BUG_ON(i == 0 || i > size);
if (eytzinger1_left_child(i) <= size) { i = eytzinger1_left_child(i) + 1;
- i <<= __fls(size + 1) - __fls(i); + i <<= __fls(size) - __fls(i); i -= 1; i >>= i > size; } else { diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index e75329399c6e..0257a4c3bb4e 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -713,12 +713,6 @@ void eytzinger1_test(void) if (!(size % 4096)) pr_info("tree size %u\n", size);
- BUG_ON(eytzinger1_prev(0, size) != eytzinger1_last(size)); - BUG_ON(eytzinger1_next(0, size) != eytzinger1_first(size)); - - BUG_ON(eytzinger1_prev(eytzinger1_first(size), size) != 0); - BUG_ON(eytzinger1_next(eytzinger1_last(size), size) != 0); - inorder = 1; eytzinger1_for_each(eytz, size) { BUG_ON(__inorder_to_eytzinger1(inorder, size, extra) != eytz); @@ -747,12 +741,6 @@ void eytzinger0_test(void) if (!(size % 4096)) pr_info("tree size %u\n", size);
- BUG_ON(eytzinger0_prev(-1, size) != eytzinger0_last(size)); - BUG_ON(eytzinger0_next(-1, size) != eytzinger0_first(size)); - - BUG_ON(eytzinger0_prev(eytzinger0_first(size), size) != -1); - BUG_ON(eytzinger0_next(eytzinger0_last(size), size) != -1); - inorder = 0; eytzinger0_for_each(eytz, size) { BUG_ON(__inorder_to_eytzinger0(inorder, size, extra) != eytz);
On Tue, Jan 28, 2025 at 05:38:37PM +0100, Andreas Gruenbacher wrote:
Kent, to continue our discussion from last November, I've gone through more parts of the eytzinger code and as a result, here are some patches for you to consider.
What I've not looked at are the eytzinger_to_inorder and inorder_to_eytzinger functions, as well as the implementation of sort. Those functions could use a bit more documentation, but the code iself looks reasonable.
Shuah, I've also had a quick look at converting the tests into kernel selftests, but that hasn't gone very far because of the lack of support for basic functions like __fls(), __ffs(), ffz(), and rounddown_pow_of_two() in selftests. Are there any plans for making those kinds of primitives generally available to selftests?
Ping on this patchset - can you throw up a git repo that's ready to be applied directly, and have you run the test that failed yourself to confirm the fix?
Also, I'll make an exception for this patchset if need be, but fyi: in the future I'm getting out of the game of running tests for people.
Either run ktest locally, or get redhat to chip in on the cluster and I'll give you CI access (and I highly reccomend that option, it'll get you quick feedback with a nice dashboard and you can use it for non bcachefs work as well).
On Fri, Feb 7, 2025 at 7:56 PM Kent Overstreet kent.overstreet@linux.dev wrote:
On Tue, Jan 28, 2025 at 05:38:37PM +0100, Andreas Gruenbacher wrote:
Kent, to continue our discussion from last November, I've gone through more parts of the eytzinger code and as a result, here are some patches for you to consider.
What I've not looked at are the eytzinger_to_inorder and inorder_to_eytzinger functions, as well as the implementation of sort. Those functions could use a bit more documentation, but the code iself looks reasonable.
Shuah, I've also had a quick look at converting the tests into kernel selftests, but that hasn't gone very far because of the lack of support for basic functions like __fls(), __ffs(), ffz(), and rounddown_pow_of_two() in selftests. Are there any plans for making those kinds of primitives generally available to selftests?
Ping on this patchset - can you throw up a git repo that's ready to be applied directly, and have you run the test that failed yourself to confirm the fix?
Did you miss this message?
https://lore.kernel.org/linux-bcachefs/20250130103400.1899121-1-agruenba@red...
The test results at:
https://evilpiepirate.org/~testdashboard/ci?user=kmo&branch=eytzinger
are still for the initial version, but I've applied the fix right away:
https://git.kernel.org/pub/scm/linux/kernel/git/agruen/linux.git/log/?h=bcac...
On top of that, I've got a small patch that adds eytzinger0_find self tests. That patch still needs testing before I can post it, though.
Oh, and let me warn you about "bcachefs: Run the eytzinger tests on modprobe" again: this really is FOR DEBUGGING ONLY, so please do not merge.
Thanks, Andreas
Also, I'll make an exception for this patchset if need be, but fyi: in the future I'm getting out of the game of running tests for people.
Either run ktest locally, or get redhat to chip in on the cluster and I'll give you CI access (and I highly reccomend that option, it'll get you quick feedback with a nice dashboard and you can use it for non bcachefs work as well).
On Fri, Feb 07, 2025 at 10:50:05PM +0100, Andreas Gruenbacher wrote:
On Fri, Feb 7, 2025 at 7:56 PM Kent Overstreet kent.overstreet@linux.dev wrote:
On Tue, Jan 28, 2025 at 05:38:37PM +0100, Andreas Gruenbacher wrote:
Kent, to continue our discussion from last November, I've gone through more parts of the eytzinger code and as a result, here are some patches for you to consider.
What I've not looked at are the eytzinger_to_inorder and inorder_to_eytzinger functions, as well as the implementation of sort. Those functions could use a bit more documentation, but the code iself looks reasonable.
Shuah, I've also had a quick look at converting the tests into kernel selftests, but that hasn't gone very far because of the lack of support for basic functions like __fls(), __ffs(), ffz(), and rounddown_pow_of_two() in selftests. Are there any plans for making those kinds of primitives generally available to selftests?
Ping on this patchset - can you throw up a git repo that's ready to be applied directly, and have you run the test that failed yourself to confirm the fix?
Did you miss this message?
https://lore.kernel.org/linux-bcachefs/20250130103400.1899121-1-agruenba@red...
No, I saw it.
I'm looking for a branch that is ready to be applied as is - fixups in the correct place, no debug patches.
That way there's no confusion over exactly what is going in, and we elimanate a lot of the back and forth.
The test results at:
https://evilpiepirate.org/~testdashboard/ci?user=kmo&branch=eytzinger
are still for the initial version, but I've applied the fix right away:
https://git.kernel.org/pub/scm/linux/kernel/git/agruen/linux.git/log/?h=bcac...
I shall point my CI at that...
On top of that, I've got a small patch that adds eytzinger0_find self tests. That patch still needs testing before I can post it, though.
Oh, and let me warn you about "bcachefs: Run the eytzinger tests on modprobe" again: this really is FOR DEBUGGING ONLY, so please do not merge.
Why is that in the branch? You ran the eytzinger tests, and that's for code that's self contained that I'm not concerned about running it myself (and if I did, then we'd be following up on getting it working with kunit now...)
If you want to leave it in the branch as an informational thing ("yes these tests were run and here's how"), it should be at the top, not the bottom, so that when I take it out I still have a subset that's an exact match (to the sha1) of something you've been working with and testing.
linux-kselftest-mirror@lists.linaro.org
-
Andreas Gruenbacher -
Eric Herman -
Kent Overstreet