lkml.org 
[lkml]   [2019]   [Aug]   [22]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
SubjectRe: [PATCH 1/3] x86,mm/pat: Use generic interval trees
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

\
 
 \ /
  Last update: 2019-08-22 06:50    [W:0.084 / U:0.644 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site