linux-kernel - Re: Library: [RFC PATCH] btree_blue - A simple btree with fast linear travesal and more. V4. and test data

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <8a7be6b8d2601dcd0b570c1456ae3dbcc3782bb7.camel@mailbox.org>
Date:   Mon, 08 May 2023 22:29:48 -0400
From:   liuwf <liuwf@...lbox.org>
To:     Uladzislau Rezki <urezki@...il.com>
Cc:     linux-kernel@...r.kernel.org, joern@...estorage.com,
        torvalds@...ux-foundation.org
Subject: Re: Library: [RFC PATCH] btree_blue - A simple btree with fast
 linear travesal and more. V4. and test data

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