[dm-devel] [PATCH] persistent-data: fix bug about btree of updating internal node's minima key in btree_split_beneath.

[monty]

Look forward to your test result. The scene I found with problem as follows:
note:
	1. key size: 8;
	2. value size: 8;
	3. max_entries=252;
	4. one level btree's root is A.
operations:
1. A's info:
	nr_entries=252
	keys:127-378
2. insert 379 to btree
		A'(127,253)
			|
	-------- ---------
	|				  |
	B(127-252)        C(253-379)
3. insert 1-126 to btree
		A'(127,253)
			|
	-------- ----------
	|				  |
	B(1-252)        C(253-379)
3. insert 0 to btree
		A'(127,127,253)
			|
	-------- -----------------
	|				  |      |
	B(0-126)    B'(127-252)   C(253-379)
4.lookup(key=127), we can not find 127 in btree.

On Mon, Dec 18, 2017 at 05:34:09PM +0000, Joe Thornber wrote:
> 
> On Mon, Dec 18, 2017 at 05:13:08PM +0000, Joe Thornber wrote:
> > Hi Monty,
> > 
> > On Mon, Dec 18, 2017 at 04:27:58PM -0500, monty wrote:
> > > Subject: [PATCH] persistent-data: fix bug about btree of updating internal node's minima
> > >  key in btree_split_beneath.
> > > 
> > >  fix bug about btree_split_beneath func, this bug may cause a key had
> > >  been inserted to btree, but dm_btree_lookup can not find the key in
> > >  btree later.
> > 
> > I think you've spotted a real issue, but I don't like where you've
> > fixed up the btree_split_beneath() function.  I'll post a patch in a
> > bit.
> 
> Patch below.  This is completely untested.  I'll test tomorrow and update.
> 
> Instead of fiddling with the spine we unlock both the new children and
> let the current spine entry (which now has just two entries) continue.
> That way the bounds on the lowest key is adjusted within the main loop
> of btree_insert_raw().
> 
> - Joe
> 
> 
> 
> diff --git a/drivers/md/persistent-data/dm-btree.c b/drivers/md/persistent-data/dm-btree.c
> index 416060c2570..ee2c01685f5 100644
> --- a/drivers/md/persistent-data/dm-btree.c
> +++ b/drivers/md/persistent-data/dm-btree.c
> @@ -572,23 +572,8 @@ static int btree_split_beneath(struct shadow_spine *s, uint64_t key)
>         pn->keys[1] = rn->keys[0];
> 	        memcpy_disk(value_ptr(pn, 1), &val, sizeof(__le64));
> 
> -       /*
> -        * rejig the spine.  This is ugly, since it knows too
> -        * much about the spine
> -        */
> -       if (s->nodes[0] != new_parent) {
> -               unlock_block(s->info, s->nodes[0]);
> -               s->nodes[0] = new_parent;
> -       }
> -       if (key < le64_to_cpu(rn->keys[0])) {
> -               unlock_block(s->info, right);
> -               s->nodes[1] = left;
> -       } else {
> -               unlock_block(s->info, left);
> -               s->nodes[1] = right;
> -       }
> -       s->count = 2;
> -
> +       unlock_block(s->info, left);
> +       unlock_block(s->info, right);
>         return 0;
> }
> 
> 
> 
>