linux-kernel - Re: [PATCH v2 2/3] augmented rbtree: add new RB_DECLARE_CALLBACKS

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:   Tue, 2 Jul 2019 09:09:13 -0700
From:   Davidlohr Bueso <dave@...olabs.net>
To:     Michel Lespinasse <walken@...gle.com>
Cc:     Peter Zijlstra <peterz@...radead.org>,
        David Howells <dhowells@...hat.com>,
        Andrew Morton <akpm@...ux-foundation.org>,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH v2 2/3] augmented rbtree: add new
 RB_DECLARE_CALLBACKS_MAX macro

On Tue, 02 Jul 2019, Michel Lespinasse wrote:

>diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c
>index fa16036fa592..2afad8e869fc 100644
>--- a/arch/x86/mm/pat_rbtree.c
>+++ b/arch/x86/mm/pat_rbtree.c
>@@ -54,23 +54,10 @@ static u64 get_subtree_max_end(struct rb_node *node)
> 	return ret;
> }
>
>-static u64 compute_subtree_max_end(struct memtype *data)
>-{
>-	u64 max_end = data->end, child_max_end;
>-
>-	child_max_end = get_subtree_max_end(data->rb.rb_right);
>-	if (child_max_end > max_end)
>-		max_end = child_max_end;
>-
>-	child_max_end = get_subtree_max_end(data->rb.rb_left);
>-	if (child_max_end > max_end)
>-		max_end = child_max_end;
>-
>-	return max_end;
>-}
>+#define NODE_END(node) ((node)->end)
>
>-RB_DECLARE_CALLBACKS(static, memtype_rb_augment_cb, struct memtype, rb,
>-		     u64, subtree_max_end, compute_subtree_max_end)
>+RB_DECLARE_CALLBACKS_MAX(struct memtype, rb, u64, subtree_max_end, NODE_END,
>+			 static, memtype_rb_augment_cb)

(unrelated to this patch)

So fyi I've recently been looking at having the whole pat_rbtree use the (generic)
interval tree api, which would mean less code and more optimized. Of course,
unfortunately they aren't 100% compatible. Fundamentally the concept of overlaps
are different (pat_rbtree is does not consider overlap when 'node->start == end' -
same for the test to the right of the node). Thus for example interval_tree_iter_first()
won't necessarily return the same node as memtype_rb_lowest_match(). Similarly,
inserting a node with key collisions will have differences wrt what path to take;
equal 'start' in pat will go to the left, interval_tree to the right. All this,
I suspect, is inherited from how pat used to work with rbtree+list.

So generic ones cannot be used and if we just use INTERVAL_TREE_DEFINE template for
pat and add the ad-hoc code does not make sense wrt cleanup, nor do we get the
optimizations. We could of course, add them manually (by using cached rbtrees, for
example) and forget about interval_tree altogether; just seems a shame.

Thanks,
Davidlohr