Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Message-ID: <8a7be6b8d2601dcd0b570c1456ae3dbcc3782bb7.camel@mailbox.org>
Subject: Re: Library: [RFC PATCH] btree_blue - A simple btree with fast
 linear travesal and more. V4. and test data
From:   liuwf <liuwf@mailbox.org>
To:     Uladzislau Rezki <urezki@gmail.com>
Cc:     linux-kernel@vger.kernel.org, joern@purestorage.com,
        torvalds@linux-foundation.org
Date:   Mon, 08 May 2023 22:29:48 -0400
In-Reply-To: <ZFY9IFM9zjFhvyPF@pc636>
References: <48d6f5a9788af056a212d0d5ba08219fdd592fbb.camel@mailbox.org>
         <ZFY9IFM9zjFhvyPF@pc636>
Content-Type: text/plain; charset="UTF-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Precedence: bulk

On Sat, 2023-05-06 at 13:42 +0200, Uladzislau Rezki wrote:
> Hello, Liu.
> 
> Just one question. I tried to run your test-suite that compares
> mapple_tree, btree, rb-tree and btree_blue. Also i wanted to have a
> look at its performance in other workloads. Thus, i have one question:
> 
> > 
> > +void *btree_blue_remove(struct btree_blue_head *head, unsigned long *key)
> > +{
> > +       if (head->height == 0)
> > +               return NULL;
> > +
> > +       return btree_blue_remove_level(head, key, 1);
> > +}
> > +EXPORT_SYMBOL_GPL(btree_blue_remove);
> > 
> I added a small change:
> 
> <snip>
> diff --git a/lib/btree_blue_test.c b/lib/btree_blue_test.c
> index b0a73836523d..9dfbe9e6b8d5 100644
> --- a/lib/btree_blue_test.c
> +++ b/lib/btree_blue_test.c
> @@ -530,6 +530,7 @@ static int btree_blue_test_init(void)
>  
>         t0 = ktime_get_ns();
>         for (long i = 0; i < RANDOM_NR; i++) {
> +               unsigned long *tmp_ptr;
>                 val_ptr =
>                         btree_blue_remove(&btree_blue_root, &(data_set_2[i].k));
>                 if (!val_ptr) {
> @@ -539,6 +540,14 @@ static int btree_blue_test_init(void)
>                                i);
>                         goto exit;
>                 }
> +
> +               tmp_ptr = btree_blue_remove(&btree_blue_root, &(data_set_2[i].k));
> +               if (tmp_ptr) {
> +                       err = -1;
> +                       pr_err("btree_blue_remove %ld, val_ptr: 0x%lu, tmp_ptr: 0x%lu\n",
> +                               i, (unsigned long) val_ptr, (unsigned long) tmp_ptr);
> +                       goto exit;
> +               }
>         }
>         t0 = ktime_get_ns() - t0;
>         printk(KERN_EMERG "btree_blue %lu deletes use time: %lu ns\n",
> <snip>
> 
> it removes two times same key. On a second removal i suspect
> a ptr_val to be NULL but it is not:
> 
> <snip>
> [   20.598023] btree 1000000 deletes use time: 251484314 ns
> [   20.599360] btree_blue_remove 0, val_ptr: 0x17259549162592618731, tmp_ptr: 0x18273237390749509852
> <snip>
> 
> Any thoughts?
> 
> Thanks!
> 
> --
> Uladzislau Rezki

Hi Uladzislau Rezki

	Thank you very much for testing and feedback. The issue you
found is related with a bug in btree_blue code. The bug let remove 
function to see a phantom of a removed key A in some cases, which if
is really removed by second time, will bring an error and result in 
the removing of another key B.

I saw your report half day ago and I have fixed the bug now, thanks a
lot! 

BTY, the lastest version of btree_blue is also posted this time, which
is V7.2 and would be better after V4, V5, V6, V7.


Liu Weifeng