Hi all,
Today's linux-next merge of the refactor-heap tree got conflicts in:
drivers/md/bcache/bset.c
drivers/md/bcache/bset.h
drivers/md/bcache/btree.c
drivers/md/bcache/writeback.c
between commit:
3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter")
from the block tree and commit:
afa5721abaaa ("bcache: Remove heap-related macros and switch to generic min_heap")
from the refactor-heap tree.
Ok, these conflicts are too extensive, so I am dropping the refactor-heap
tree for today. I suggest you all get together and sort something out.
I fixed it up (see above) and can carry the fix as necessary. This
is now fixed as far as linux-next is concerned, but any non trivial
conflicts should be mentioned to your upstream maintainer when your tree
is submitted for merging. You may also want to consider cooperating
with the maintainer of the conflicting tree to minimise any particularly
complex conflicts.
Here are the conflicts:
diff --cc drivers/md/bcache/bset.c
index 463eb13bd0b2,bd97d8626887..000000000000
--- a/drivers/md/bcache/bset.c
+++ b/drivers/md/bcache/bset.c
@@@ -54,9 -54,11 +54,11 @@@ void bch_dump_bucket(struct btree_keys
int __bch_count_data(struct btree_keys *b)
{
unsigned int ret = 0;
- struct btree_iter iter;
+ struct btree_iter_stack iter;
struct bkey *k;
+ min_heap_init(&iter.heap, NULL, MAX_BSETS);
+
if (b->ops->is_extents)
for_each_key(b, k, &iter)
ret += KEY_SIZE(k);
@@@ -67,9 -69,11 +69,11 @@@ void __bch_check_keys(struct btree_key
{
va_list args;
struct bkey *k, *p = NULL;
- struct btree_iter iter;
+ struct btree_iter_stack iter;
const char *err;
+ min_heap_init(&iter.heap, NULL, MAX_BSETS);
+
for_each_key(b, k, &iter) {
if (b->ops->is_extents) {
err = "Keys out of order";
@@@ -1094,24 -1109,30 +1109,35 @@@ static inline bool btree_iter_end(struc
void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k,
struct bkey *end)
{
+ const struct min_heap_callbacks callbacks = {
+ .less = new_btree_iter_cmp,
+ .swp = new_btree_iter_swap,
+ };
+
if (k != end)
- BUG_ON(!heap_add(iter,
- ((struct btree_iter_set) { k, end }),
- btree_iter_cmp));
+ BUG_ON(!min_heap_push(&iter->heap,
+ &((struct btree_iter_set) { k, end }),
+ &callbacks,
+ NULL));
}
-static struct bkey *__bch_btree_iter_init(struct btree_keys *b,
- struct btree_iter *iter,
- struct bkey *search,
- struct bset_tree *start)
+static struct bkey *__bch_btree_iter_stack_init(struct btree_keys *b,
+ struct btree_iter_stack *iter,
+ struct bkey *search,
+ struct bset_tree *start)
{
struct bkey *ret = NULL;
++<<<<<<< HEAD
+ iter->iter.size = ARRAY_SIZE(iter->stack_data);
+ iter->iter.used = 0;
++=======
+ iter->heap.size = ARRAY_SIZE(iter->heap.preallocated);
+ iter->heap.nr = 0;
++>>>>>>> refactor-heap/refactor-heap
#ifdef CONFIG_BCACHE_DEBUG
- iter->b = b;
+ iter->iter.b = b;
#endif
for (; start <= bset_tree_last(b); start++) {
@@@ -1293,10 -1324,11 +1329,15 @@@ void bch_btree_sort_partial(struct btre
struct bset_sort_state *state)
{
size_t order = b->page_order, keys = 0;
- struct btree_iter iter;
+ struct btree_iter_stack iter;
int oldsize = bch_count_data(b);
++<<<<<<< HEAD
+ __bch_btree_iter_stack_init(b, &iter, NULL, &b->set[start]);
++=======
+ min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ __bch_btree_iter_init(b, &iter, NULL, &b->set[start]);
++>>>>>>> refactor-heap/refactor-heap
if (start) {
unsigned int i;
@@@ -1323,11 -1355,13 +1364,17 @@@ void bch_btree_sort_into(struct btree_k
struct bset_sort_state *state)
{
uint64_t start_time = local_clock();
- struct btree_iter iter;
+ struct btree_iter_stack iter;
++<<<<<<< HEAD
+ bch_btree_iter_stack_init(b, &iter, NULL);
++=======
+ min_heap_init(&iter.heap, NULL, MAX_BSETS);
+
+ bch_btree_iter_init(b, &iter, NULL);
++>>>>>>> refactor-heap/refactor-heap
- btree_mergesort(b, new->set->data, &iter, false, true);
+ btree_mergesort(b, new->set->data, &iter.iter, false, true);
bch_time_stats_update(&state->time, start_time);
diff --cc drivers/md/bcache/bset.h
index 011f6062c4c0,f79441acd4c1..000000000000
--- a/drivers/md/bcache/bset.h
+++ b/drivers/md/bcache/bset.h
@@@ -318,17 -323,7 +323,20 @@@ struct btree_iter
#ifdef CONFIG_BCACHE_DEBUG
struct btree_keys *b;
#endif
++<<<<<<< HEAD
+ struct btree_iter_set {
+ struct bkey *k, *end;
+ } data[];
+};
+
+/* Fixed-size btree_iter that can be allocated on the stack */
+
+struct btree_iter_stack {
+ struct btree_iter iter;
+ struct btree_iter_set stack_data[MAX_BSETS];
++=======
+ MIN_HEAP_PREALLOCATED(struct btree_iter_set, btree_iter_heap, MAX_BSETS) heap;
++>>>>>>> refactor-heap/refactor-heap
};
typedef bool (*ptr_filter_fn)(struct btree_keys *b, const struct bkey *k);
diff --cc drivers/md/bcache/btree.c
index d011a7154d33,a2bb86d52ad4..000000000000
--- a/drivers/md/bcache/btree.c
+++ b/drivers/md/bcache/btree.c
@@@ -1309,9 -1309,11 +1309,11 @@@ static bool btree_gc_mark_node(struct b
uint8_t stale = 0;
unsigned int keys = 0, good_keys = 0;
struct bkey *k;
- struct btree_iter iter;
+ struct btree_iter_stack iter;
struct bset_tree *t;
+ min_heap_init(&iter.heap, NULL, MAX_BSETS);
+
gc->nodes++;
for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) {
@@@ -1570,9 -1572,11 +1572,11 @@@ static int btree_gc_rewrite_node(struc
static unsigned int btree_gc_count_keys(struct btree *b)
{
struct bkey *k;
- struct btree_iter iter;
+ struct btree_iter_stack iter;
unsigned int ret = 0;
+ min_heap_init(&iter.heap, NULL, MAX_BSETS);
+
for_each_key_filter(&b->keys, k, &iter, bch_ptr_bad)
ret += bkey_u64s(k);
@@@ -1615,7 -1619,8 +1619,12 @@@ static int btree_gc_recurse(struct btre
struct gc_merge_info r[GC_MERGE_NODES];
struct gc_merge_info *i, *last = r + ARRAY_SIZE(r) - 1;
++<<<<<<< HEAD
+ bch_btree_iter_stack_init(&b->keys, &iter, &b->c->gc_done);
++=======
+ min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done);
++>>>>>>> refactor-heap/refactor-heap
for (i = r; i < r + ARRAY_SIZE(r); i++)
i->b = ERR_PTR(-EINTR);
@@@ -1912,8 -1916,10 +1921,10 @@@ static int bch_btree_check_recurse(stru
{
int ret = 0;
struct bkey *k, *p = NULL;
- struct btree_iter iter;
+ struct btree_iter_stack iter;
+ min_heap_init(&iter.heap, NULL, MAX_BSETS);
+
for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid)
bch_initial_mark_key(b->c, b->level, k);
@@@ -1959,9 -1965,11 +1970,11 @@@ static int bch_btree_check_thread(void
cur_idx = prev_idx = 0;
ret = 0;
+ min_heap_init(&iter.heap, NULL, MAX_BSETS);
+
/* root node keys are checked before thread created */
- bch_btree_iter_init(&c->root->keys, &iter, NULL);
- k = bch_btree_iter_next_filter(&iter, &c->root->keys, bch_ptr_bad);
+ bch_btree_iter_stack_init(&c->root->keys, &iter, NULL);
+ k = bch_btree_iter_next_filter(&iter.iter, &c->root->keys, bch_ptr_bad);
BUG_ON(!k);
p = k;
@@@ -2052,9 -2060,11 +2065,11 @@@ int bch_btree_check(struct cache_set *c
int ret = 0;
int i;
struct bkey *k = NULL;
- struct btree_iter iter;
+ struct btree_iter_stack iter;
struct btree_check_state check_state;
+ min_heap_init(&iter.heap, NULL, MAX_BSETS);
+
/* check and mark root node keys */
for_each_key_filter(&c->root->keys, k, &iter, bch_ptr_invalid)
bch_initial_mark_key(c, c->root->level, k);
@@@ -2548,11 -2558,12 +2563,16 @@@ static int bch_btree_map_nodes_recurse(
if (b->level) {
struct bkey *k;
- struct btree_iter iter;
+ struct btree_iter_stack iter;
++<<<<<<< HEAD
+ bch_btree_iter_stack_init(&b->keys, &iter, from);
++=======
+ min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ bch_btree_iter_init(&b->keys, &iter, from);
++>>>>>>> refactor-heap/refactor-heap
- while ((k = bch_btree_iter_next_filter(&iter, &b->keys,
+ while ((k = bch_btree_iter_next_filter(&iter.iter, &b->keys,
bch_ptr_bad))) {
ret = bcache_btree(map_nodes_recurse, k, b,
op, from, fn, flags);
@@@ -2581,12 -2592,12 +2601,17 @@@ int bch_btree_map_keys_recurse(struct b
{
int ret = MAP_CONTINUE;
struct bkey *k;
- struct btree_iter iter;
+ struct btree_iter_stack iter;
++<<<<<<< HEAD
+ bch_btree_iter_stack_init(&b->keys, &iter, from);
++=======
+ min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ bch_btree_iter_init(&b->keys, &iter, from);
++>>>>>>> refactor-heap/refactor-heap
- while ((k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) {
+ while ((k = bch_btree_iter_next_filter(&iter.iter, &b->keys,
+ bch_ptr_bad))) {
ret = !b->level
? fn(op, b, k)
: bcache_btree(map_keys_recurse, k,
diff --cc drivers/md/bcache/writeback.c
index 792e070ccf38,c1d28e365910..000000000000
--- a/drivers/md/bcache/writeback.c
+++ b/drivers/md/bcache/writeback.c
@@@ -915,8 -915,9 +915,14 @@@ static int bch_dirty_init_thread(void *
k = p = NULL;
prev_idx = 0;
++<<<<<<< HEAD
+ bch_btree_iter_stack_init(&c->root->keys, &iter, NULL);
+ k = bch_btree_iter_next_filter(&iter.iter, &c->root->keys, bch_ptr_bad);
++=======
+ min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ bch_btree_iter_init(&c->root->keys, &iter, NULL);
+ k = bch_btree_iter_next_filter(&iter, &c->root->keys, bch_ptr_bad);
++>>>>>>> refactor-heap/refactor-heap
BUG_ON(!k);
p = k;
--
Cheers,
Stephen Rothwell
On Thu, May 09, 2024 at 03:27:45PM +1000, Stephen Rothwell wrote:
> Hi all,
>
> Today's linux-next merge of the refactor-heap tree got conflicts in:
>
> drivers/md/bcache/bset.c
> drivers/md/bcache/bset.h
> drivers/md/bcache/btree.c
> drivers/md/bcache/writeback.c
>
> between commit:
>
> 3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter")
>
> from the block tree and commit:
>
> afa5721abaaa ("bcache: Remove heap-related macros and switch to generic min_heap")
>
> from the refactor-heap tree.
>
> Ok, these conflicts are too extensive, so I am dropping the refactor-heap
> tree for today. I suggest you all get together and sort something out.
Coli and Kuan, you guys will need to get this sorted out quick if we
want refactor-heap to make the merge window
On Thu, May 09, 2024 at 03:58:57PM -0400, Kent Overstreet wrote:
> On Thu, May 09, 2024 at 03:27:45PM +1000, Stephen Rothwell wrote:
> > Hi all,
> >
> > Today's linux-next merge of the refactor-heap tree got conflicts in:
> >
> > drivers/md/bcache/bset.c
> > drivers/md/bcache/bset.h
> > drivers/md/bcache/btree.c
> > drivers/md/bcache/writeback.c
> >
> > between commit:
> >
> > 3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter")
> >
> > from the block tree and commit:
> >
> > afa5721abaaa ("bcache: Remove heap-related macros and switch to generic min_heap")
> >
> > from the refactor-heap tree.
> >
> > Ok, these conflicts are too extensive, so I am dropping the refactor-heap
> > tree for today. I suggest you all get together and sort something out.
>
> Coli and Kuan, you guys will need to get this sorted out quick if we
> want refactor-heap to make the merge window
Hi Coli and Kent,
If I understand correctly, the reported bug is because we attempted to
point (heap)->data to a dynamically allocated memory , but at that time
(heap)->data was not a regular pointer but a fixed size array with a
length of MAX_BSETS.
In my refactor heap patch series, I introduced a preallocated array and
decided in min_heap_init() whether the data pointer should point to an
incoming pointer or to the preallocated array. Therefore, I am
wondering if my patch might have unintentionally fixed this bug?
I am unsure how to reproduce the reported issue. Could you assist me in
verifying whether my assumption is correct?
Regards,
Kuan-Wei
On Fri, May 10, 2024 at 06:44:29AM +0800, Kuan-Wei Chiu wrote:
> On Thu, May 09, 2024 at 03:58:57PM -0400, Kent Overstreet wrote:
> > On Thu, May 09, 2024 at 03:27:45PM +1000, Stephen Rothwell wrote:
> > > Hi all,
> > >
> > > Today's linux-next merge of the refactor-heap tree got conflicts in:
> > >
> > > drivers/md/bcache/bset.c
> > > drivers/md/bcache/bset.h
> > > drivers/md/bcache/btree.c
> > > drivers/md/bcache/writeback.c
> > >
> > > between commit:
> > >
> > > 3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter")
> > >
> > > from the block tree and commit:
> > >
> > > afa5721abaaa ("bcache: Remove heap-related macros and switch to generic min_heap")
> > >
> > > from the refactor-heap tree.
> > >
> > > Ok, these conflicts are too extensive, so I am dropping the refactor-heap
> > > tree for today. I suggest you all get together and sort something out.
> >
> > Coli and Kuan, you guys will need to get this sorted out quick if we
> > want refactor-heap to make the merge window
>
> Hi Coli and Kent,
>
> If I understand correctly, the reported bug is because we attempted to
> point (heap)->data to a dynamically allocated memory , but at that time
> (heap)->data was not a regular pointer but a fixed size array with a
> length of MAX_BSETS.
>
> In my refactor heap patch series, I introduced a preallocated array and
> decided in min_heap_init() whether the data pointer should point to an
> incoming pointer or to the preallocated array. Therefore, I am
> wondering if my patch might have unintentionally fixed this bug?
>
> I am unsure how to reproduce the reported issue. Could you assist me in
> verifying whether my assumption is correct?
This is a merge conflict, not a runtime. Can you rebase onto Coli's
tree? We'll have to retest.
On Thu, May 09, 2024 at 07:16:31PM -0400, Kent Overstreet wrote:
> On Fri, May 10, 2024 at 06:44:29AM +0800, Kuan-Wei Chiu wrote:
> > On Thu, May 09, 2024 at 03:58:57PM -0400, Kent Overstreet wrote:
> > > On Thu, May 09, 2024 at 03:27:45PM +1000, Stephen Rothwell wrote:
> > > > Hi all,
> > > >
> > > > Today's linux-next merge of the refactor-heap tree got conflicts in:
> > > >
> > > > drivers/md/bcache/bset.c
> > > > drivers/md/bcache/bset.h
> > > > drivers/md/bcache/btree.c
> > > > drivers/md/bcache/writeback.c
> > > >
> > > > between commit:
> > > >
> > > > 3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter")
> > > >
> > > > from the block tree and commit:
> > > >
> > > > afa5721abaaa ("bcache: Remove heap-related macros and switch to generic min_heap")
> > > >
> > > > from the refactor-heap tree.
> > > >
> > > > Ok, these conflicts are too extensive, so I am dropping the refactor-heap
> > > > tree for today. I suggest you all get together and sort something out.
> > >
> > > Coli and Kuan, you guys will need to get this sorted out quick if we
> > > want refactor-heap to make the merge window
> >
> > Hi Coli and Kent,
> >
> > If I understand correctly, the reported bug is because we attempted to
> > point (heap)->data to a dynamically allocated memory , but at that time
> > (heap)->data was not a regular pointer but a fixed size array with a
> > length of MAX_BSETS.
> >
> > In my refactor heap patch series, I introduced a preallocated array and
> > decided in min_heap_init() whether the data pointer should point to an
> > incoming pointer or to the preallocated array. Therefore, I am
> > wondering if my patch might have unintentionally fixed this bug?
> >
> > I am unsure how to reproduce the reported issue. Could you assist me in
> > verifying whether my assumption is correct?
>
> This is a merge conflict, not a runtime. Can you rebase onto Coli's
> tree? We'll have to retest.
Oh, sorry for the misunderstanding I caused. When I mentioned "bug" [1]
earlier, I was referring to the bug addressed in
3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter"),
not a merge conflict.
Here are the results after the rebase:
https://github.com/visitorckw/linux.git refactor-heap
[1]: https://bugs.launchpad.net/ubuntu/+source/linux/+bug/2039368
Regards,
Kuan-Wei
On Fri, May 10, 2024 at 11:07:11AM +0800, Kuan-Wei Chiu wrote:
> On Thu, May 09, 2024 at 07:16:31PM -0400, Kent Overstreet wrote:
> > On Fri, May 10, 2024 at 06:44:29AM +0800, Kuan-Wei Chiu wrote:
> > > On Thu, May 09, 2024 at 03:58:57PM -0400, Kent Overstreet wrote:
> > > > On Thu, May 09, 2024 at 03:27:45PM +1000, Stephen Rothwell wrote:
> > > > > Hi all,
> > > > >
> > > > > Today's linux-next merge of the refactor-heap tree got conflicts in:
> > > > >
> > > > > drivers/md/bcache/bset.c
> > > > > drivers/md/bcache/bset.h
> > > > > drivers/md/bcache/btree.c
> > > > > drivers/md/bcache/writeback.c
> > > > >
> > > > > between commit:
> > > > >
> > > > > 3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter")
> > > > >
> > > > > from the block tree and commit:
> > > > >
> > > > > afa5721abaaa ("bcache: Remove heap-related macros and switch to generic min_heap")
> > > > >
> > > > > from the refactor-heap tree.
> > > > >
> > > > > Ok, these conflicts are too extensive, so I am dropping the refactor-heap
> > > > > tree for today. I suggest you all get together and sort something out.
> > > >
> > > > Coli and Kuan, you guys will need to get this sorted out quick if we
> > > > want refactor-heap to make the merge window
> > >
> > > Hi Coli and Kent,
> > >
> > > If I understand correctly, the reported bug is because we attempted to
> > > point (heap)->data to a dynamically allocated memory , but at that time
> > > (heap)->data was not a regular pointer but a fixed size array with a
> > > length of MAX_BSETS.
> > >
> > > In my refactor heap patch series, I introduced a preallocated array and
> > > decided in min_heap_init() whether the data pointer should point to an
> > > incoming pointer or to the preallocated array. Therefore, I am
> > > wondering if my patch might have unintentionally fixed this bug?
> > >
> > > I am unsure how to reproduce the reported issue. Could you assist me in
> > > verifying whether my assumption is correct?
> >
> > This is a merge conflict, not a runtime. Can you rebase onto Coli's
> > tree? We'll have to retest.
>
> Oh, sorry for the misunderstanding I caused. When I mentioned "bug" [1]
> earlier, I was referring to the bug addressed in
> 3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter"),
> not a merge conflict.
>
> Here are the results after the rebase:
> https://github.com/visitorckw/linux.git refactor-heap
>
> [1]: https://bugs.launchpad.net/ubuntu/+source/linux/+bug/2039368
The ubuntu kernels build with UBSAN now, and the bug reported is just a
UBSAN warning. The original implementation's iterator has a fixed size
sets array that is indexed out of bounds when the iterator is allocated
on the heap with more space -- the patch restructures it a bit to have a
single iterator type with a flexible array and then a larger "stack"
type which embeds the iterator along with the preallocated region.
I took a brief look at the refactor-heap branch but I'm not entirely
sure what's going on with the new min heaps: in the one place where the
larger iterators are used (in bch_btree_node_read_done) it doesn't look
like the heap is ever initialized (perhaps since the old iter_init
wasn't used here because of the special case it got missed in the
refactor?) With the new heaps it should be fairly easy to fix though;
just change the fill_iter mempool to be allocating only the minheap data
arrays and setup iter->heap.data properly with that instead.
Hope that helps,
Matthew Mirvish
>
> Regards,
> Kuan-Wei
On Thu, May 09, 2024 at 11:46:18PM -0400, Matthew Mirvish wrote:
> On Fri, May 10, 2024 at 11:07:11AM +0800, Kuan-Wei Chiu wrote:
> > On Thu, May 09, 2024 at 07:16:31PM -0400, Kent Overstreet wrote:
> > > On Fri, May 10, 2024 at 06:44:29AM +0800, Kuan-Wei Chiu wrote:
> > > > On Thu, May 09, 2024 at 03:58:57PM -0400, Kent Overstreet wrote:
> > > > > On Thu, May 09, 2024 at 03:27:45PM +1000, Stephen Rothwell wrote:
> > > > > > Hi all,
> > > > > >
> > > > > > Today's linux-next merge of the refactor-heap tree got conflicts in:
> > > > > >
> > > > > > drivers/md/bcache/bset.c
> > > > > > drivers/md/bcache/bset.h
> > > > > > drivers/md/bcache/btree.c
> > > > > > drivers/md/bcache/writeback.c
> > > > > >
> > > > > > between commit:
> > > > > >
> > > > > > 3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter")
> > > > > >
> > > > > > from the block tree and commit:
> > > > > >
> > > > > > afa5721abaaa ("bcache: Remove heap-related macros and switch to generic min_heap")
> > > > > >
> > > > > > from the refactor-heap tree.
> > > > > >
> > > > > > Ok, these conflicts are too extensive, so I am dropping the refactor-heap
> > > > > > tree for today. I suggest you all get together and sort something out.
> > > > >
> > > > > Coli and Kuan, you guys will need to get this sorted out quick if we
> > > > > want refactor-heap to make the merge window
> > > >
> > > > Hi Coli and Kent,
> > > >
> > > > If I understand correctly, the reported bug is because we attempted to
> > > > point (heap)->data to a dynamically allocated memory , but at that time
> > > > (heap)->data was not a regular pointer but a fixed size array with a
> > > > length of MAX_BSETS.
> > > >
> > > > In my refactor heap patch series, I introduced a preallocated array and
> > > > decided in min_heap_init() whether the data pointer should point to an
> > > > incoming pointer or to the preallocated array. Therefore, I am
> > > > wondering if my patch might have unintentionally fixed this bug?
> > > >
> > > > I am unsure how to reproduce the reported issue. Could you assist me in
> > > > verifying whether my assumption is correct?
> > >
> > > This is a merge conflict, not a runtime. Can you rebase onto Coli's
> > > tree? We'll have to retest.
> >
> > Oh, sorry for the misunderstanding I caused. When I mentioned "bug" [1]
> > earlier, I was referring to the bug addressed in
> > 3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter"),
> > not a merge conflict.
> >
> > Here are the results after the rebase:
> > https://github.com/visitorckw/linux.git refactor-heap
> >
> > [1]: https://bugs.launchpad.net/ubuntu/+source/linux/+bug/2039368
>
> The ubuntu kernels build with UBSAN now, and the bug reported is just a
> UBSAN warning. The original implementation's iterator has a fixed size
> sets array that is indexed out of bounds when the iterator is allocated
> on the heap with more space -- the patch restructures it a bit to have a
> single iterator type with a flexible array and then a larger "stack"
> type which embeds the iterator along with the preallocated region.
>
> I took a brief look at the refactor-heap branch but I'm not entirely
> sure what's going on with the new min heaps: in the one place where the
> larger iterators are used (in bch_btree_node_read_done) it doesn't look
> like the heap is ever initialized (perhaps since the old iter_init
> wasn't used here because of the special case it got missed in the
> refactor?) With the new heaps it should be fairly easy to fix though;
> just change the fill_iter mempool to be allocating only the minheap data
> arrays and setup iter->heap.data properly with that instead.
Thank you, Matthew.
Not initializing the heap's data pointer was indeed my mistake.
Following your advice, I made the following modifications to the code
on the refactor-heap branch in my github repo. I hope this time it
works well.
Regards,
Kuan-Wei
diff --git a/drivers/md/bcache/btree.c b/drivers/md/bcache/btree.c
index a2bb86d52ad4..ce9d729bc8ff 100644
--- a/drivers/md/bcache/btree.c
+++ b/drivers/md/bcache/btree.c
@@ -149,19 +149,19 @@ void bch_btree_node_read_done(struct btree *b)
{
const char *err = "bad btree header";
struct bset *i = btree_bset_first(b);
- struct btree_iter *iter;
+ struct btree_iter iter;
/*
* c->fill_iter can allocate an iterator with more memory space
* than static MAX_BSETS.
* See the comment arount cache_set->fill_iter.
*/
- iter = mempool_alloc(&b->c->fill_iter, GFP_NOIO);
- iter->heap.size = b->c->cache->sb.bucket_size / b->c->cache->sb.block_size;
- iter->heap.nr = 0;
+ iter.heap.data = mempool_alloc(&b->c->fill_iter, GFP_NOIO);
+ iter.heap.size = b->c->cache->sb.bucket_size / b->c->cache->sb.block_size;
+ iter.heap.nr = 0;
#ifdef CONFIG_BCACHE_DEBUG
- iter->b = &b->keys;
+ iter.b = &b->keys;
#endif
if (!i->seq)
@@ -199,7 +199,7 @@ void bch_btree_node_read_done(struct btree *b)
if (i != b->keys.set[0].data && !i->keys)
goto err;
- bch_btree_iter_push(iter, i->start, bset_bkey_last(i));
+ bch_btree_iter_push(&iter, i->start, bset_bkey_last(i));
b->written += set_blocks(i, block_bytes(b->c->cache));
}
@@ -211,7 +211,7 @@ void bch_btree_node_read_done(struct btree *b)
if (i->seq == b->keys.set[0].data->seq)
goto err;
- bch_btree_sort_and_fix_extents(&b->keys, iter, &b->c->sort);
+ bch_btree_sort_and_fix_extents(&b->keys, &iter, &b->c->sort);
i = b->keys.set[0].data;
err = "short btree key";
@@ -223,7 +223,7 @@ void bch_btree_node_read_done(struct btree *b)
bch_bset_init_next(&b->keys, write_block(b),
bset_magic(&b->c->cache->sb));
out:
- mempool_free(iter, &b->c->fill_iter);
+ mempool_free(iter.heap.data, &b->c->fill_iter);
return;
err:
set_btree_node_io_error(b);
diff --git a/drivers/md/bcache/super.c b/drivers/md/bcache/super.c
index cba09660148a..c6f5592996a8 100644
--- a/drivers/md/bcache/super.c
+++ b/drivers/md/bcache/super.c
@@ -1914,8 +1914,7 @@ struct cache_set *bch_cache_set_alloc(struct cache_sb *sb)
INIT_LIST_HEAD(&c->btree_cache_freed);
INIT_LIST_HEAD(&c->data_buckets);
- iter_size = sizeof(struct btree_iter) +
- ((meta_bucket_pages(sb) * PAGE_SECTORS) / sb->block_size) *
+ iter_size = ((meta_bucket_pages(sb) * PAGE_SECTORS) / sb->block_size) *
sizeof(struct btree_iter_set);
c->devices = kcalloc(c->nr_uuids, sizeof(void *), GFP_KERNEL);
On Fri, May 10, 2024 at 05:11:02PM +0800, Kuan-Wei Chiu wrote:
> On Thu, May 09, 2024 at 11:46:18PM -0400, Matthew Mirvish wrote:
> > On Fri, May 10, 2024 at 11:07:11AM +0800, Kuan-Wei Chiu wrote:
> > > On Thu, May 09, 2024 at 07:16:31PM -0400, Kent Overstreet wrote:
> > > > On Fri, May 10, 2024 at 06:44:29AM +0800, Kuan-Wei Chiu wrote:
> > > > > On Thu, May 09, 2024 at 03:58:57PM -0400, Kent Overstreet wrote:
> > > > > > On Thu, May 09, 2024 at 03:27:45PM +1000, Stephen Rothwell wrote:
> > > > > > > Hi all,
> > > > > > >
> > > > > > > Today's linux-next merge of the refactor-heap tree got conflicts in:
> > > > > > >
> > > > > > > drivers/md/bcache/bset.c
> > > > > > > drivers/md/bcache/bset.h
> > > > > > > drivers/md/bcache/btree.c
> > > > > > > drivers/md/bcache/writeback.c
> > > > > > >
> > > > > > > between commit:
> > > > > > >
> > > > > > > 3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter")
> > > > > > >
> > > > > > > from the block tree and commit:
> > > > > > >
> > > > > > > afa5721abaaa ("bcache: Remove heap-related macros and switch to generic min_heap")
> > > > > > >
> > > > > > > from the refactor-heap tree.
> > > > > > >
> > > > > > > Ok, these conflicts are too extensive, so I am dropping the refactor-heap
> > > > > > > tree for today. I suggest you all get together and sort something out.
> > > > > >
> > > > > > Coli and Kuan, you guys will need to get this sorted out quick if we
> > > > > > want refactor-heap to make the merge window
> > > > >
> > > > > Hi Coli and Kent,
> > > > >
> > > > > If I understand correctly, the reported bug is because we attempted to
> > > > > point (heap)->data to a dynamically allocated memory , but at that time
> > > > > (heap)->data was not a regular pointer but a fixed size array with a
> > > > > length of MAX_BSETS.
> > > > >
> > > > > In my refactor heap patch series, I introduced a preallocated array and
> > > > > decided in min_heap_init() whether the data pointer should point to an
> > > > > incoming pointer or to the preallocated array. Therefore, I am
> > > > > wondering if my patch might have unintentionally fixed this bug?
> > > > >
> > > > > I am unsure how to reproduce the reported issue. Could you assist me in
> > > > > verifying whether my assumption is correct?
> > > >
> > > > This is a merge conflict, not a runtime. Can you rebase onto Coli's
> > > > tree? We'll have to retest.
> > >
> > > Oh, sorry for the misunderstanding I caused. When I mentioned "bug" [1]
> > > earlier, I was referring to the bug addressed in
> > > 3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter"),
> > > not a merge conflict.
> > >
> > > Here are the results after the rebase:
> > > https://github.com/visitorckw/linux.git refactor-heap
> > >
> > > [1]: https://bugs.launchpad.net/ubuntu/+source/linux/+bug/2039368
> >
> > The ubuntu kernels build with UBSAN now, and the bug reported is just a
> > UBSAN warning. The original implementation's iterator has a fixed size
> > sets array that is indexed out of bounds when the iterator is allocated
> > on the heap with more space -- the patch restructures it a bit to have a
> > single iterator type with a flexible array and then a larger "stack"
> > type which embeds the iterator along with the preallocated region.
> >
> > I took a brief look at the refactor-heap branch but I'm not entirely
> > sure what's going on with the new min heaps: in the one place where the
> > larger iterators are used (in bch_btree_node_read_done) it doesn't look
> > like the heap is ever initialized (perhaps since the old iter_init
> > wasn't used here because of the special case it got missed in the
> > refactor?) With the new heaps it should be fairly easy to fix though;
> > just change the fill_iter mempool to be allocating only the minheap data
> > arrays and setup iter->heap.data properly with that instead.
>
> Thank you, Matthew.
> Not initializing the heap's data pointer was indeed my mistake.
> Following your advice, I made the following modifications to the code
> on the refactor-heap branch in my github repo. I hope this time it
> works well.
>
Should I resend it as a patch series?
>
> diff --git a/drivers/md/bcache/btree.c b/drivers/md/bcache/btree.c
> index a2bb86d52ad4..ce9d729bc8ff 100644
> --- a/drivers/md/bcache/btree.c
> +++ b/drivers/md/bcache/btree.c
> @@ -149,19 +149,19 @@ void bch_btree_node_read_done(struct btree *b)
> {
> const char *err = "bad btree header";
> struct bset *i = btree_bset_first(b);
> - struct btree_iter *iter;
> + struct btree_iter iter;
>
> /*
> * c->fill_iter can allocate an iterator with more memory space
> * than static MAX_BSETS.
> * See the comment arount cache_set->fill_iter.
> */
> - iter = mempool_alloc(&b->c->fill_iter, GFP_NOIO);
> - iter->heap.size = b->c->cache->sb.bucket_size / b->c->cache->sb.block_size;
> - iter->heap.nr = 0;
> + iter.heap.data = mempool_alloc(&b->c->fill_iter, GFP_NOIO);
> + iter.heap.size = b->c->cache->sb.bucket_size / b->c->cache->sb.block_size;
> + iter.heap.nr = 0;
>
> #ifdef CONFIG_BCACHE_DEBUG
> - iter->b = &b->keys;
> + iter.b = &b->keys;
> #endif
>
> if (!i->seq)
> @@ -199,7 +199,7 @@ void bch_btree_node_read_done(struct btree *b)
> if (i != b->keys.set[0].data && !i->keys)
> goto err;
>
> - bch_btree_iter_push(iter, i->start, bset_bkey_last(i));
> + bch_btree_iter_push(&iter, i->start, bset_bkey_last(i));
>
> b->written += set_blocks(i, block_bytes(b->c->cache));
> }
> @@ -211,7 +211,7 @@ void bch_btree_node_read_done(struct btree *b)
> if (i->seq == b->keys.set[0].data->seq)
> goto err;
>
> - bch_btree_sort_and_fix_extents(&b->keys, iter, &b->c->sort);
> + bch_btree_sort_and_fix_extents(&b->keys, &iter, &b->c->sort);
>
> i = b->keys.set[0].data;
> err = "short btree key";
> @@ -223,7 +223,7 @@ void bch_btree_node_read_done(struct btree *b)
> bch_bset_init_next(&b->keys, write_block(b),
> bset_magic(&b->c->cache->sb));
> out:
> - mempool_free(iter, &b->c->fill_iter);
> + mempool_free(iter.heap.data, &b->c->fill_iter);
> return;
> err:
> set_btree_node_io_error(b);
> diff --git a/drivers/md/bcache/super.c b/drivers/md/bcache/super.c
> index cba09660148a..c6f5592996a8 100644
> --- a/drivers/md/bcache/super.c
> +++ b/drivers/md/bcache/super.c
> @@ -1914,8 +1914,7 @@ struct cache_set *bch_cache_set_alloc(struct cache_sb *sb)
> INIT_LIST_HEAD(&c->btree_cache_freed);
> INIT_LIST_HEAD(&c->data_buckets);
>
> - iter_size = sizeof(struct btree_iter) +
> - ((meta_bucket_pages(sb) * PAGE_SECTORS) / sb->block_size) *
> + iter_size = ((meta_bucket_pages(sb) * PAGE_SECTORS) / sb->block_size) *
> sizeof(struct btree_iter_set);
>
> c->devices = kcalloc(c->nr_uuids, sizeof(void *), GFP_KERNEL);
>
On Sun, May 12, 2024 at 03:24:47AM +0800, Kuan-Wei Chiu wrote:
> On Fri, May 10, 2024 at 05:11:02PM +0800, Kuan-Wei Chiu wrote:
> > On Thu, May 09, 2024 at 11:46:18PM -0400, Matthew Mirvish wrote:
> > > On Fri, May 10, 2024 at 11:07:11AM +0800, Kuan-Wei Chiu wrote:
> > > > On Thu, May 09, 2024 at 07:16:31PM -0400, Kent Overstreet wrote:
> > > > > On Fri, May 10, 2024 at 06:44:29AM +0800, Kuan-Wei Chiu wrote:
> > > > > > On Thu, May 09, 2024 at 03:58:57PM -0400, Kent Overstreet wrote:
> > > > > > > On Thu, May 09, 2024 at 03:27:45PM +1000, Stephen Rothwell wrote:
> > > > > > > > Hi all,
> > > > > > > >
> > > > > > > > Today's linux-next merge of the refactor-heap tree got conflicts in:
> > > > > > > >
> > > > > > > > drivers/md/bcache/bset.c
> > > > > > > > drivers/md/bcache/bset.h
> > > > > > > > drivers/md/bcache/btree.c
> > > > > > > > drivers/md/bcache/writeback.c
> > > > > > > >
> > > > > > > > between commit:
> > > > > > > >
> > > > > > > > 3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter")
> > > > > > > >
> > > > > > > > from the block tree and commit:
> > > > > > > >
> > > > > > > > afa5721abaaa ("bcache: Remove heap-related macros and switch to generic min_heap")
> > > > > > > >
> > > > > > > > from the refactor-heap tree.
> > > > > > > >
> > > > > > > > Ok, these conflicts are too extensive, so I am dropping the refactor-heap
> > > > > > > > tree for today. I suggest you all get together and sort something out.
> > > > > > >
> > > > > > > Coli and Kuan, you guys will need to get this sorted out quick if we
> > > > > > > want refactor-heap to make the merge window
> > > > > >
> > > > > > Hi Coli and Kent,
> > > > > >
> > > > > > If I understand correctly, the reported bug is because we attempted to
> > > > > > point (heap)->data to a dynamically allocated memory , but at that time
> > > > > > (heap)->data was not a regular pointer but a fixed size array with a
> > > > > > length of MAX_BSETS.
> > > > > >
> > > > > > In my refactor heap patch series, I introduced a preallocated array and
> > > > > > decided in min_heap_init() whether the data pointer should point to an
> > > > > > incoming pointer or to the preallocated array. Therefore, I am
> > > > > > wondering if my patch might have unintentionally fixed this bug?
> > > > > >
> > > > > > I am unsure how to reproduce the reported issue. Could you assist me in
> > > > > > verifying whether my assumption is correct?
> > > > >
> > > > > This is a merge conflict, not a runtime. Can you rebase onto Coli's
> > > > > tree? We'll have to retest.
> > > >
> > > > Oh, sorry for the misunderstanding I caused. When I mentioned "bug" [1]
> > > > earlier, I was referring to the bug addressed in
> > > > 3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter"),
> > > > not a merge conflict.
> > > >
> > > > Here are the results after the rebase:
> > > > https://github.com/visitorckw/linux.git refactor-heap
> > > >
> > > > [1]: https://bugs.launchpad.net/ubuntu/+source/linux/+bug/2039368
> > >
> > > The ubuntu kernels build with UBSAN now, and the bug reported is just a
> > > UBSAN warning. The original implementation's iterator has a fixed size
> > > sets array that is indexed out of bounds when the iterator is allocated
> > > on the heap with more space -- the patch restructures it a bit to have a
> > > single iterator type with a flexible array and then a larger "stack"
> > > type which embeds the iterator along with the preallocated region.
> > >
> > > I took a brief look at the refactor-heap branch but I'm not entirely
> > > sure what's going on with the new min heaps: in the one place where the
> > > larger iterators are used (in bch_btree_node_read_done) it doesn't look
> > > like the heap is ever initialized (perhaps since the old iter_init
> > > wasn't used here because of the special case it got missed in the
> > > refactor?) With the new heaps it should be fairly easy to fix though;
> > > just change the fill_iter mempool to be allocating only the minheap data
> > > arrays and setup iter->heap.data properly with that instead.
> >
> > Thank you, Matthew.
> > Not initializing the heap's data pointer was indeed my mistake.
> > Following your advice, I made the following modifications to the code
> > on the refactor-heap branch in my github repo. I hope this time it
> > works well.
> >
> Should I resend it as a patch series?
Go ahead.
--
An old man doll... just what I always wanted! - Clara
Hi all,
On Thu, 9 May 2024 15:27:45 +1000 Stephen Rothwell <[email protected]> wrote:
>
> Today's linux-next merge of the refactor-heap tree got conflicts in:
>
> drivers/md/bcache/bset.c
> drivers/md/bcache/bset.h
> drivers/md/bcache/btree.c
> drivers/md/bcache/writeback.c
>
> between commit:
>
> 3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter")
>
> from the block tree and commit:
>
> afa5721abaaa ("bcache: Remove heap-related macros and switch to generic min_heap")
>
> from the refactor-heap tree.
>
> Ok, these conflicts are too extensive, so I am dropping the refactor-heap
> tree for today. I suggest you all get together and sort something out.
I am still dropping the refactor-heap tree ...
--
Cheers,
Stephen Rothwell
On Tue, May 21, 2024 at 12:18:03PM +1000, Stephen Rothwell wrote:
> Hi all,
>
> On Thu, 9 May 2024 15:27:45 +1000 Stephen Rothwell <[email protected]> wrote:
> >
> > Today's linux-next merge of the refactor-heap tree got conflicts in:
> >
> > drivers/md/bcache/bset.c
> > drivers/md/bcache/bset.h
> > drivers/md/bcache/btree.c
> > drivers/md/bcache/writeback.c
> >
> > between commit:
> >
> > 3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter")
> >
> > from the block tree and commit:
> >
> > afa5721abaaa ("bcache: Remove heap-related macros and switch to generic min_heap")
> >
> > from the refactor-heap tree.
> >
> > Ok, these conflicts are too extensive, so I am dropping the refactor-heap
> > tree for today. I suggest you all get together and sort something out.
>
> I am still dropping the refactor-heap tree ...
Hi Kent,
Are you still planning to send the pull request in this merge window?
I've sent the v5 patch series [1] to resolve the conflicts some time ago.
Is there anything missing from my side?
[1]: https://lkml.kernel.org/[email protected]
Regards,
Kuan-Wei
On Tue, May 21, 2024 at 10:44:11AM +0800, Kuan-Wei Chiu wrote:
> On Tue, May 21, 2024 at 12:18:03PM +1000, Stephen Rothwell wrote:
> > Hi all,
> >
> > On Thu, 9 May 2024 15:27:45 +1000 Stephen Rothwell <[email protected]> wrote:
> > >
> > > Today's linux-next merge of the refactor-heap tree got conflicts in:
> > >
> > > drivers/md/bcache/bset.c
> > > drivers/md/bcache/bset.h
> > > drivers/md/bcache/btree.c
> > > drivers/md/bcache/writeback.c
> > >
> > > between commit:
> > >
> > > 3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter")
> > >
> > > from the block tree and commit:
> > >
> > > afa5721abaaa ("bcache: Remove heap-related macros and switch to generic min_heap")
> > >
> > > from the refactor-heap tree.
> > >
> > > Ok, these conflicts are too extensive, so I am dropping the refactor-heap
> > > tree for today. I suggest you all get together and sort something out.
> >
> > I am still dropping the refactor-heap tree ...
>
> Hi Kent,
>
> Are you still planning to send the pull request in this merge window?
> I've sent the v5 patch series [1] to resolve the conflicts some time ago.
> Is there anything missing from my side?
Unfortunately it's going to have to wait until next merge window, all
the conferences the past week have meant I've been pretty distracted,
still not fully caught back up.
Hi all,
On Thu, 9 May 2024 15:27:45 +1000 Stephen Rothwell <[email protected]> wrote:
>
> Today's linux-next merge of the refactor-heap tree got conflicts in:
>
> drivers/md/bcache/bset.c
> drivers/md/bcache/bset.h
> drivers/md/bcache/btree.c
> drivers/md/bcache/writeback.c
>
> between commit:
>
> 3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter")
>
> from the block tree and commit:
>
> afa5721abaaa ("bcache: Remove heap-related macros and switch to generic min_heap")
>
> from the refactor-heap tree.
>
> Ok, these conflicts are too extensive, so I am dropping the refactor-heap
> tree for today. I suggest you all get together and sort something out.
It looks as though the patches from the refactor-heap tree are now being
carried in the mm-nonmm-unstable branch of the mm tree. Should I
rmeove the refactor-heap tree from linux-next? It *will* be dropped for
today at least.
--
Cheers,
Stephen Rothwell
On Tue, May 28, 2024 at 11:07:37AM +1000, Stephen Rothwell wrote:
> Hi all,
>
> On Thu, 9 May 2024 15:27:45 +1000 Stephen Rothwell <[email protected]> wrote:
> >
> > Today's linux-next merge of the refactor-heap tree got conflicts in:
> >
> > drivers/md/bcache/bset.c
> > drivers/md/bcache/bset.h
> > drivers/md/bcache/btree.c
> > drivers/md/bcache/writeback.c
> >
> > between commit:
> >
> > 3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter")
> >
> > from the block tree and commit:
> >
> > afa5721abaaa ("bcache: Remove heap-related macros and switch to generic min_heap")
> >
> > from the refactor-heap tree.
> >
> > Ok, these conflicts are too extensive, so I am dropping the refactor-heap
> > tree for today. I suggest you all get together and sort something out.
>
> It looks as though the patches from the refactor-heap tree are now being
> carried in the mm-nonmm-unstable branch of the mm tree. Should I
> rmeove the refactor-heap tree from linux-next? It *will* be dropped for
> today at least.
Yeah, Andrew's got it