Messages in this thread Patch in this message | | | Date | Wed, 21 Aug 2019 21:49:36 -0700 | From | Davidlohr Bueso <> | Subject | Re: [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
| |