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] [thread-next>] [day] [month] [year] [list]

Date:   Sat, 6 May 2023 13:42:24 +0200
From:   Uladzislau Rezki <urezki@...il.com>
To:     liuwf <liuwf@...lbox.org>
Cc:     linux-kernel@...r.kernel.org, joern@...estorage.com,
        torvalds@...ux-foundation.org, urezki@...il.com
Subject: Re: Library: [RFC PATCH] btree_blue - A simple btree with fast
 linear travesal and more. V4. and test data

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