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

[Davidlohr Bueso <dave@stgolabs.net>]

On Wed, 21 Aug 2019, Michel Lespinasse wrote:

>On Tue, Aug 13, 2019 at 03:46:18PM -0700, Davidlohr Bueso wrote:
>> o The border cases for overlapping differ -- interval trees are closed,
>> while memtype intervals are open. We need to maintain semantics such
>> that conflict detection and getting the lowest match does not change.
>
>Agree on the need to maintain semantics.
>
>As I had commented some time ago, I wish the interval trees used [start,end)
>intervals instead of [start,last] - it would be a better fit for basically
>all of the current interval tree users.

Yes, after going through all the users of interval-tree,  I agree that
they all want to use [start,end intervals.

>
>I'm not sure where to go with this - would it make sense to add a new
>interval tree header file that uses [start,end) intervals (with the
>thought of eventually converting all current interval tree users to it)
>instead of adding one more use of the less-natural [start,last]
>interval trees ?

It might be the safest way, although I really hate having another
header file for interval_tree... The following is a diffstat of a
tentative conversion (I'll send the patch separately); I'm not sure
if a single shot conversion would be acceptable, albeit with relevant
maintainer acks.

 drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c      |  8 +-------
 drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c      |  5 +++--
 drivers/gpu/drm/drm_mm.c                    |  2 +-
 drivers/gpu/drm/i915/gem/i915_gem_userptr.c | 13 +++++--------
 drivers/gpu/drm/radeon/radeon_mn.c          | 10 +++-------
 drivers/gpu/drm/radeon/radeon_vm.c          |  2 +-
 drivers/infiniband/hw/hfi1/mmu_rb.c         | 12 ++++++------
 drivers/iommu/virtio-iommu.c                |  4 ++--
 drivers/vhost/vhost.c                       |  6 +++---
 include/drm/drm_mm.h                        |  2 +-
 include/linux/interval_tree_generic.h       | 28 ++++++++++++++--------------
 mm/interval_tree.c                          |  2 +-
 mm/rmap.c                                   |  2 +-
 13 files changed, 42 insertions(+), 54 deletions(-)

This gets rid of 'end - 1' trick from the users and converts
cond1 and cond2 checks in interval_tree_generic.h

Note that I think amdgpu_vm.c actually uses fully open intervals.

>
>> 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
>> @@ -12,7 +12,7 @@
>>  #include <linux/seq_file.h>
>>  #include <linux/debugfs.h>
>>  #include <linux/kernel.h>
>> -#include <linux/rbtree_augmented.h>
>> +#include <linux/interval_tree_generic.h>
>>  #include <linux/sched.h>
>>  #include <linux/gfp.h>
>>
>> @@ -34,68 +34,41 @@
>>   * memtype_lock protects the rbtree.
>>   */
>>
>> -static struct rb_root memtype_rbroot = RB_ROOT;
>> +static struct rb_root_cached memtype_rbroot = RB_ROOT_CACHED;
>> +
>> +#define START(node) ((node)->start)
>> +#define END(node)  ((node)->end)
>> +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)
>>  {
>> -	if (node->start >= end || node->end <= start)
>> +	/*
>> +	 * Unlike generic interval trees, the memtype nodes are ]a, b[
>
>I think the memtype nodes are [a, b)  (which one could also write as [a, b[
>depending on their local customs - but either way, closed on the start side
>and open on the end side) ?
>
>> +	 * 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;
>>  }
>
>All right, now I am *really* confused.
>
>My understanding is as follows:
>* the PAT code wants to use [start, end( intervals
>* interval trees are defined to use [start, last] intervals with last == end-1

Yes, we're talking about the same thing, but I overcomplicated things by
considering memtype lookups to be different than the nodes in the tree;
which obviously doesn't make sense... it is actually [a,b[ as you mention.

>
>At first, I thought that you were handling that by removing 1 from the
>end of the interval, to adjust between the PAT and interval tree
>definitions. But, I don't see you doing that anywhere.

This should have been my first approach.

>
>Then, I thought that you were using [start, end( intervals everywhere,
>and the interval tree functions memtype_interval_iter_first and
>memtype_interval_iter_next would just return too many candidate
>matches as as you are passing "end" instead of "last" == end-1 as the
>interval endpoint, but then you would filter out the extra intervals
>using is_node_overlap(). But, if that is the case, then I don't
>understand why you need to redefine is_node_overlap() here.

My original expectation was to actually remove a lot more of pat_rbtree,
including the is_node_overlap() and the filtering. Yes, I think this can
be done if the interval-tree is converted to [a,b[ and we can thus
just iterate the tree seamlessly.

>
>Could you help me out by defining if the intervals are open or closed,
>both when stored in the node->start and node->end values, and when
>passed as start and end arguments to the functions in this file ?

No, no endpoints are modified in pat.

>
>Generally, I think using the interval tree code in this file is a good idea,
>but 1- I do not understand how you are handling the differences in interval
>definitions in this change, and 2- I wonder if it'd be better to just have
>a version of the interval tree code that handles [start,end( half-open
>intervals like we do everywhere else in the kernel.

I think doing the conversion you suggested to [a,b[ for all users, then
redoing this series on top of that would be the way to move forward.

Thanks,
Davidlohr