Re: [PATCH 1/3] x86,mm/pat: Use generic interval trees

[Peter Zijlstra]

On Tue, Aug 13, 2019 at 03:46:18PM -0700, Davidlohr Bueso wrote:

> diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c
> index fa16036fa592..1be4d1856a9b 100644
> --- a/arch/x86/mm/pat_rbtree.c
> +++ b/arch/x86/mm/pat_rbtree.c

> @@ -34,68 +34,41 @@
>   * memtype_lock protects the rbtree.
>   */
>  
> +static struct rb_root_cached memtype_rbroot = RB_ROOT_CACHED;
> +
> +#define START(node) ((node)->start)
> +#define END(node)  ((node)->end)

Afaict these could actually be inlines, but I see other interval tree
users also use macros for them, albeit with END called LAST.

> +INTERVAL_TREE_DEFINE(struct memtype, rb, u64, subtree_max_end,
> +		     START, END, static, memtype_interval)
>  
>  static int is_node_overlap(struct memtype *node, u64 start, u64 end)
>  {
> +	/*
> +	 * Unlike generic interval trees, the memtype nodes are ]a, b[
> +	 * therefore we need to adjust the ranges accordingly. Missing
> +	 * an overlap can lead to incorrectly detecting conflicts,
> +	 * for example.
> +	 */
> +	if (node->start + 1 >= end || node->end - 1 <= start)
>  		return 0;
>  
>  	return 1;
>  }

I've not looked yet; but how horrible would it be to change that
weirdness?

> @@ -149,10 +116,8 @@ static int memtype_rb_check_conflict(struct rb_root *root,
>  	dprintk("Overlap at 0x%Lx-0x%Lx\n", match->start, match->end);
>  	found_type = match->type;
>  
> +        match = memtype_interval_iter_next(match, start, end);
> +	while (match) {

whilespace fail

>  		if (match->start >= end) /* Checked all possible matches */
>  			goto success;
>  

> @@ -176,43 +141,21 @@ static int memtype_rb_check_conflict(struct rb_root *root,
>  	return -EBUSY;
>  }
>  
>  int rbt_memtype_check_insert(struct memtype *new,
>  			     enum page_cache_mode *ret_type)
>  {
> +	int err;
>  
> +	err =  memtype_rb_check_conflict(&memtype_rbroot,
> +					 new->start, new->end,
> +					 new->type, ret_type);

whitespace fail

> +	if (err)
> +		return err;
>  
> +	if (ret_type)
> +		new->type = *ret_type;
>  
> +	memtype_interval_insert(new, &memtype_rbroot);
>  	return err;
>  }
>