Re: [PATCH v2 2/3] augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro

[Davidlohr Bueso]

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