[09/11] lib/interval-tree: convert interval_tree to half closed intervals
diff mbox series

Message ID 20191003201858.11666-10-dave@stgolabs.net
State New
Headers show
Series
  • lib/interval-tree: move to half closed intervals
Related show

Commit Message

Davidlohr Bueso Oct. 3, 2019, 8:18 p.m. UTC
The generic tree tree really wants [a, b) intervals, not fully closed.
As such convert it to use the new interval_tree_gen.h. Most of the
conversions are straightforward, with the exception of perhaps
radeon_vm_bo_set_addr(), but semantics have been tried to be left
untouched.

Cc: "Christian König" <christian.koenig@amd.com>
Cc: Alex Deucher <alexander.deucher@amd.com>
Cc: David Airlie <airlied@linux.ie>
Cc: Daniel Vetter <daniel@ffwll.ch>
Cc: Doug Ledford <dledford@redhat.com>
Cc: Joerg Roedel <joro@8bytes.org>
Cc: "Jérôme Glisse" <jglisse@redhat.com>
Cc: dri-devel@lists.freedesktop.org
Cc: linux-rdma@vger.kernel.org
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
 drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c      | 12 +++---------
 drivers/gpu/drm/i915/gem/i915_gem_userptr.c |  5 +----
 drivers/gpu/drm/radeon/radeon_mn.c          | 11 ++++-------
 drivers/gpu/drm/radeon/radeon_trace.h       |  2 +-
 drivers/gpu/drm/radeon/radeon_vm.c          | 26 +++++++++++++-------------
 drivers/infiniband/core/umem_odp.c          | 21 +++++++--------------
 drivers/iommu/virtio-iommu.c                |  6 +++---
 include/linux/interval_tree.h               |  2 +-
 include/rdma/ib_umem_odp.h                  |  4 ++--
 lib/interval_tree.c                         |  6 +++---
 10 files changed, 38 insertions(+), 57 deletions(-)

Comments

Christian König Oct. 4, 2019, 6:57 a.m. UTC | #1
Am 03.10.19 um 22:18 schrieb Davidlohr Bueso:
> The generic tree tree really wants [a, b) intervals, not fully closed.
> As such convert it to use the new interval_tree_gen.h. Most of the
> conversions are straightforward, with the exception of perhaps
> radeon_vm_bo_set_addr(), but semantics have been tried to be left
> untouched.

NAK, the whole thing won't work.

See we need to handle the full device address space which means we have 
values in the range of 0x0-0xffffffff.

If you make this a closed interval then the end would wrap around to 0x0 
if long is only 32bit.

Regards,
Christian.

>
> Cc: "Christian König" <christian.koenig@amd.com>
> Cc: Alex Deucher <alexander.deucher@amd.com>
> Cc: David Airlie <airlied@linux.ie>
> Cc: Daniel Vetter <daniel@ffwll.ch>
> Cc: Doug Ledford <dledford@redhat.com>
> Cc: Joerg Roedel <joro@8bytes.org>
> Cc: "Jérôme Glisse" <jglisse@redhat.com>
> Cc: dri-devel@lists.freedesktop.org
> Cc: linux-rdma@vger.kernel.org
> Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
> ---
>   drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c      | 12 +++---------
>   drivers/gpu/drm/i915/gem/i915_gem_userptr.c |  5 +----
>   drivers/gpu/drm/radeon/radeon_mn.c          | 11 ++++-------
>   drivers/gpu/drm/radeon/radeon_trace.h       |  2 +-
>   drivers/gpu/drm/radeon/radeon_vm.c          | 26 +++++++++++++-------------
>   drivers/infiniband/core/umem_odp.c          | 21 +++++++--------------
>   drivers/iommu/virtio-iommu.c                |  6 +++---
>   include/linux/interval_tree.h               |  2 +-
>   include/rdma/ib_umem_odp.h                  |  4 ++--
>   lib/interval_tree.c                         |  6 +++---
>   10 files changed, 38 insertions(+), 57 deletions(-)
>
> diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c b/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c
> index 31d4deb5d294..4bbaa9ffa570 100644
> --- a/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c
> +++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c
> @@ -205,9 +205,6 @@ amdgpu_mn_sync_pagetables_gfx(struct hmm_mirror *mirror,
>   	bool blockable = mmu_notifier_range_blockable(update);
>   	struct interval_tree_node *it;
>   
> -	/* notification is exclusive, but interval is inclusive */
> -	end -= 1;
> -
>   	/* TODO we should be able to split locking for interval tree and
>   	 * amdgpu_mn_invalidate_node
>   	 */
> @@ -254,9 +251,6 @@ amdgpu_mn_sync_pagetables_hsa(struct hmm_mirror *mirror,
>   	bool blockable = mmu_notifier_range_blockable(update);
>   	struct interval_tree_node *it;
>   
> -	/* notification is exclusive, but interval is inclusive */
> -	end -= 1;
> -
>   	if (amdgpu_mn_read_lock(amn, blockable))
>   		return -EAGAIN;
>   
> @@ -374,7 +368,7 @@ struct amdgpu_mn *amdgpu_mn_get(struct amdgpu_device *adev,
>    */
>   int amdgpu_mn_register(struct amdgpu_bo *bo, unsigned long addr)
>   {
> -	unsigned long end = addr + amdgpu_bo_size(bo) - 1;
> +	unsigned long end = addr + amdgpu_bo_size(bo);
>   	struct amdgpu_device *adev = amdgpu_ttm_adev(bo->tbo.bdev);
>   	enum amdgpu_mn_type type =
>   		bo->kfd_bo ? AMDGPU_MN_TYPE_HSA : AMDGPU_MN_TYPE_GFX;
> @@ -400,7 +394,7 @@ int amdgpu_mn_register(struct amdgpu_bo *bo, unsigned long addr)
>   		node = container_of(it, struct amdgpu_mn_node, it);
>   		interval_tree_remove(&node->it, &amn->objects);
>   		addr = min(it->start, addr);
> -		end = max(it->last, end);
> +		end = max(it->end, end);
>   		list_splice(&node->bos, &bos);
>   	}
>   
> @@ -412,7 +406,7 @@ int amdgpu_mn_register(struct amdgpu_bo *bo, unsigned long addr)
>   	bo->mn = amn;
>   
>   	node->it.start = addr;
> -	node->it.last = end;
> +	node->it.end = end;
>   	INIT_LIST_HEAD(&node->bos);
>   	list_splice(&bos, &node->bos);
>   	list_add(&bo->mn_list, &node->bos);
> diff --git a/drivers/gpu/drm/i915/gem/i915_gem_userptr.c b/drivers/gpu/drm/i915/gem/i915_gem_userptr.c
> index 11b231c187c5..818ff6b33102 100644
> --- a/drivers/gpu/drm/i915/gem/i915_gem_userptr.c
> +++ b/drivers/gpu/drm/i915/gem/i915_gem_userptr.c
> @@ -99,9 +99,6 @@ userptr_mn_invalidate_range_start(struct mmu_notifier *_mn,
>   	if (RB_EMPTY_ROOT(&mn->objects.rb_root))
>   		return 0;
>   
> -	/* interval ranges are inclusive, but invalidate range is exclusive */
> -	end = range->end - 1;
> -
>   	spin_lock(&mn->lock);
>   	it = interval_tree_iter_first(&mn->objects, range->start, end);
>   	while (it) {
> @@ -275,7 +272,7 @@ i915_gem_userptr_init__mmu_notifier(struct drm_i915_gem_object *obj,
>   	mo->mn = mn;
>   	mo->obj = obj;
>   	mo->it.start = obj->userptr.ptr;
> -	mo->it.last = obj->userptr.ptr + obj->base.size - 1;
> +	mo->it.end = obj->userptr.ptr + obj->base.size;
>   	RB_CLEAR_NODE(&mo->it.rb);
>   
>   	obj->userptr.mmu_object = mo;
> diff --git a/drivers/gpu/drm/radeon/radeon_mn.c b/drivers/gpu/drm/radeon/radeon_mn.c
> index dbab9a3a969b..4810421dacc2 100644
> --- a/drivers/gpu/drm/radeon/radeon_mn.c
> +++ b/drivers/gpu/drm/radeon/radeon_mn.c
> @@ -66,12 +66,9 @@ static int radeon_mn_invalidate_range_start(struct mmu_notifier *mn,
>   	struct radeon_mn *rmn = container_of(mn, struct radeon_mn, mn);
>   	struct ttm_operation_ctx ctx = { false, false };
>   	struct interval_tree_node *it;
> -	unsigned long end;
> +	unsigned long end = range->end;
>   	int ret = 0;
>   
> -	/* notification is exclusive, but interval is inclusive */
> -	end = range->end - 1;
> -
>   	/* TODO we should be able to split locking for interval tree and
>   	 * the tear down.
>   	 */
> @@ -174,7 +171,7 @@ static const struct mmu_notifier_ops radeon_mn_ops = {
>    */
>   int radeon_mn_register(struct radeon_bo *bo, unsigned long addr)
>   {
> -	unsigned long end = addr + radeon_bo_size(bo) - 1;
> +	unsigned long end = addr + radeon_bo_size(bo);
>   	struct mmu_notifier *mn;
>   	struct radeon_mn *rmn;
>   	struct radeon_mn_node *node = NULL;
> @@ -195,7 +192,7 @@ int radeon_mn_register(struct radeon_bo *bo, unsigned long addr)
>   		node = container_of(it, struct radeon_mn_node, it);
>   		interval_tree_remove(&node->it, &rmn->objects);
>   		addr = min(it->start, addr);
> -		end = max(it->last, end);
> +		end = max(it->end, end);
>   		list_splice(&node->bos, &bos);
>   	}
>   
> @@ -210,7 +207,7 @@ int radeon_mn_register(struct radeon_bo *bo, unsigned long addr)
>   	bo->mn = rmn;
>   
>   	node->it.start = addr;
> -	node->it.last = end;
> +	node->it.end = end;
>   	INIT_LIST_HEAD(&node->bos);
>   	list_splice(&bos, &node->bos);
>   	list_add(&bo->mn_list, &node->bos);
> diff --git a/drivers/gpu/drm/radeon/radeon_trace.h b/drivers/gpu/drm/radeon/radeon_trace.h
> index c93f3ab3c4e3..4324f3fc5d82 100644
> --- a/drivers/gpu/drm/radeon/radeon_trace.h
> +++ b/drivers/gpu/drm/radeon/radeon_trace.h
> @@ -73,7 +73,7 @@ TRACE_EVENT(radeon_vm_bo_update,
>   
>   	    TP_fast_assign(
>   			   __entry->soffset = bo_va->it.start;
> -			   __entry->eoffset = bo_va->it.last + 1;
> +			   __entry->eoffset = bo_va->it.end;
>   			   __entry->flags = bo_va->flags;
>   			   ),
>   	    TP_printk("soffs=%010llx, eoffs=%010llx, flags=%08x",
> diff --git a/drivers/gpu/drm/radeon/radeon_vm.c b/drivers/gpu/drm/radeon/radeon_vm.c
> index e0ad547786e8..b2a54aff21f4 100644
> --- a/drivers/gpu/drm/radeon/radeon_vm.c
> +++ b/drivers/gpu/drm/radeon/radeon_vm.c
> @@ -329,7 +329,7 @@ struct radeon_bo_va *radeon_vm_bo_add(struct radeon_device *rdev,
>   	bo_va->vm = vm;
>   	bo_va->bo = bo;
>   	bo_va->it.start = 0;
> -	bo_va->it.last = 0;
> +	bo_va->it.end = 0;
>   	bo_va->flags = 0;
>   	bo_va->ref_count = 1;
>   	INIT_LIST_HEAD(&bo_va->bo_list);
> @@ -456,7 +456,7 @@ int radeon_vm_bo_set_addr(struct radeon_device *rdev,
>   
>   	if (soffset) {
>   		/* make sure object fit at this offset */
> -		eoffset = soffset + size - 1;
> +		eoffset = soffset + size;
>   		if (soffset >= eoffset) {
>   			r = -EINVAL;
>   			goto error_unreserve;
> @@ -486,14 +486,14 @@ int radeon_vm_bo_set_addr(struct radeon_device *rdev,
>   			/* bo and tmp overlap, invalid offset */
>   			dev_err(rdev->dev, "bo %p va 0x%010Lx conflict with "
>   				"(bo %p 0x%010lx 0x%010lx)\n", bo_va->bo,
> -				soffset, tmp->bo, tmp->it.start, tmp->it.last);
> +				soffset, tmp->bo, tmp->it.start, tmp->it.end);
>   			mutex_unlock(&vm->mutex);
>   			r = -EINVAL;
>   			goto error_unreserve;
>   		}
>   	}
>   
> -	if (bo_va->it.start || bo_va->it.last) {
> +	if (bo_va->it.start || bo_va->it.end) {
>   		/* add a clone of the bo_va to clear the old address */
>   		struct radeon_bo_va *tmp;
>   		tmp = kzalloc(sizeof(struct radeon_bo_va), GFP_KERNEL);
> @@ -503,14 +503,14 @@ int radeon_vm_bo_set_addr(struct radeon_device *rdev,
>   			goto error_unreserve;
>   		}
>   		tmp->it.start = bo_va->it.start;
> -		tmp->it.last = bo_va->it.last;
> +		tmp->it.end = bo_va->it.end;
>   		tmp->vm = vm;
>   		tmp->bo = radeon_bo_ref(bo_va->bo);
>   
>   		interval_tree_remove(&bo_va->it, &vm->va);
>   		spin_lock(&vm->status_lock);
>   		bo_va->it.start = 0;
> -		bo_va->it.last = 0;
> +		bo_va->it.end = 0;
>   		list_del_init(&bo_va->vm_status);
>   		list_add(&tmp->vm_status, &vm->freed);
>   		spin_unlock(&vm->status_lock);
> @@ -519,7 +519,7 @@ int radeon_vm_bo_set_addr(struct radeon_device *rdev,
>   	if (soffset || eoffset) {
>   		spin_lock(&vm->status_lock);
>   		bo_va->it.start = soffset;
> -		bo_va->it.last = eoffset;
> +		bo_va->it.end = eoffset;
>   		list_add(&bo_va->vm_status, &vm->cleared);
>   		spin_unlock(&vm->status_lock);
>   		interval_tree_insert(&bo_va->it, &vm->va);
> @@ -964,7 +964,7 @@ int radeon_vm_bo_update(struct radeon_device *rdev,
>   
>   	trace_radeon_vm_bo_update(bo_va);
>   
> -	nptes = bo_va->it.last - bo_va->it.start + 1;
> +	nptes = bo_va->it.end - bo_va->it.start;
>   
>   	/* reserve space for one command every (1 << BLOCK_SIZE) entries
>   	   or 2k dwords (whatever is smaller) */
> @@ -1010,7 +1010,7 @@ int radeon_vm_bo_update(struct radeon_device *rdev,
>   	}
>   
>   	r = radeon_vm_update_ptes(rdev, vm, &ib, bo_va->it.start,
> -				  bo_va->it.last + 1, addr,
> +				  bo_va->it.end, addr,
>   				  radeon_vm_page_flags(bo_va->flags));
>   	if (r) {
>   		radeon_ib_free(rdev, &ib);
> @@ -1026,7 +1026,7 @@ int radeon_vm_bo_update(struct radeon_device *rdev,
>   		return r;
>   	}
>   	ib.fence->is_vm_update = true;
> -	radeon_vm_fence_pts(vm, bo_va->it.start, bo_va->it.last + 1, ib.fence);
> +	radeon_vm_fence_pts(vm, bo_va->it.start, bo_va->it.end, ib.fence);
>   	radeon_fence_unref(&bo_va->last_pt_update);
>   	bo_va->last_pt_update = radeon_fence_ref(ib.fence);
>   	radeon_ib_free(rdev, &ib);
> @@ -1124,12 +1124,12 @@ void radeon_vm_bo_rmv(struct radeon_device *rdev,
>   	list_del(&bo_va->bo_list);
>   
>   	mutex_lock(&vm->mutex);
> -	if (bo_va->it.start || bo_va->it.last)
> +	if (bo_va->it.start || bo_va->it.end)
>   		interval_tree_remove(&bo_va->it, &vm->va);
>   
>   	spin_lock(&vm->status_lock);
>   	list_del(&bo_va->vm_status);
> -	if (bo_va->it.start || bo_va->it.last) {
> +	if (bo_va->it.start || bo_va->it.end) {
>   		bo_va->bo = radeon_bo_ref(bo_va->bo);
>   		list_add(&bo_va->vm_status, &vm->freed);
>   	} else {
> @@ -1158,7 +1158,7 @@ void radeon_vm_bo_invalidate(struct radeon_device *rdev,
>   	list_for_each_entry(bo_va, &bo->va, bo_list) {
>   		spin_lock(&bo_va->vm->status_lock);
>   		if (list_empty(&bo_va->vm_status) &&
> -		    (bo_va->it.start || bo_va->it.last))
> +		    (bo_va->it.start || bo_va->it.end))
>   			list_add(&bo_va->vm_status, &bo_va->vm->invalidated);
>   		spin_unlock(&bo_va->vm->status_lock);
>   	}
> diff --git a/drivers/infiniband/core/umem_odp.c b/drivers/infiniband/core/umem_odp.c
> index f67a30fda1ed..9b7ac93223d6 100644
> --- a/drivers/infiniband/core/umem_odp.c
> +++ b/drivers/infiniband/core/umem_odp.c
> @@ -219,26 +219,19 @@ static inline int ib_init_umem_odp(struct ib_umem_odp *umem_odp)
>   			ALIGN_DOWN(umem_odp->umem.address, page_size);
>   		if (check_add_overflow(umem_odp->umem.address,
>   				       (unsigned long)umem_odp->umem.length,
> -				       &umem_odp->interval_tree.last))
> +				       &umem_odp->interval_tree.end))
>   			return -EOVERFLOW;
> -		umem_odp->interval_tree.last =
> -			ALIGN(umem_odp->interval_tree.last, page_size);
> -		if (unlikely(umem_odp->interval_tree.last < page_size))
> +		umem_odp->interval_tree.end =
> +			ALIGN(umem_odp->interval_tree.end, page_size);
> +		if (unlikely(umem_odp->interval_tree.end < page_size))
>   			return -EOVERFLOW;
>   
> -		pages = (umem_odp->interval_tree.last -
> +		pages = (umem_odp->interval_tree.end -
>   			 umem_odp->interval_tree.start) >>
>   			umem_odp->page_shift;
>   		if (!pages)
>   			return -EINVAL;
>   
> -		/*
> -		 * Note that the representation of the intervals in the
> -		 * interval tree considers the ending point as contained in
> -		 * the interval.
> -		 */
> -		umem_odp->interval_tree.last--;
> -
>   		umem_odp->page_list = kvcalloc(
>   			pages, sizeof(*umem_odp->page_list), GFP_KERNEL);
>   		if (!umem_odp->page_list)
> @@ -777,12 +770,12 @@ int rbt_ib_umem_for_each_in_range(struct rb_root_cached *root,
>   	if (unlikely(start == last))
>   		return ret_val;
>   
> -	for (node = interval_tree_iter_first(root, start, last - 1);
> +	for (node = interval_tree_iter_first(root, start, last);
>   			node; node = next) {
>   		/* TODO move the blockable decision up to the callback */
>   		if (!blockable)
>   			return -EAGAIN;
> -		next = interval_tree_iter_next(node, start, last - 1);
> +		next = interval_tree_iter_next(node, start, last);
>   		umem = container_of(node, struct ib_umem_odp, interval_tree);
>   		ret_val = cb(umem, start, last, cookie) || ret_val;
>   	}
> diff --git a/drivers/iommu/virtio-iommu.c b/drivers/iommu/virtio-iommu.c
> index 3ea9d7682999..771740981f43 100644
> --- a/drivers/iommu/virtio-iommu.c
> +++ b/drivers/iommu/virtio-iommu.c
> @@ -323,7 +323,7 @@ static int viommu_add_mapping(struct viommu_domain *vdomain, unsigned long iova,
>   
>   	mapping->paddr		= paddr;
>   	mapping->iova.start	= iova;
> -	mapping->iova.last	= iova + size - 1;
> +	mapping->iova.end	= iova + size;
>   	mapping->flags		= flags;
>   
>   	spin_lock_irqsave(&vdomain->mappings_lock, irqflags);
> @@ -348,7 +348,7 @@ static size_t viommu_del_mappings(struct viommu_domain *vdomain,
>   {
>   	size_t unmapped = 0;
>   	unsigned long flags;
> -	unsigned long last = iova + size - 1;
> +	unsigned long last = iova + size;
>   	struct viommu_mapping *mapping = NULL;
>   	struct interval_tree_node *node, *next;
>   
> @@ -367,7 +367,7 @@ static size_t viommu_del_mappings(struct viommu_domain *vdomain,
>   		 * Virtio-iommu doesn't allow UNMAP to split a mapping created
>   		 * with a single MAP request, so remove the full mapping.
>   		 */
> -		unmapped += mapping->iova.last - mapping->iova.start + 1;
> +		unmapped += mapping->iova.end - mapping->iova.start;
>   
>   		interval_tree_remove(node, &vdomain->mappings);
>   		kfree(mapping);
> diff --git a/include/linux/interval_tree.h b/include/linux/interval_tree.h
> index 288c26f50732..f3d1ea9e4003 100644
> --- a/include/linux/interval_tree.h
> +++ b/include/linux/interval_tree.h
> @@ -7,7 +7,7 @@
>   struct interval_tree_node {
>   	struct rb_node rb;
>   	unsigned long start;	/* Start of interval */
> -	unsigned long last;	/* Last location _in_ interval */
> +	unsigned long end;	/* Last location _outside_ interval */
>   	unsigned long __subtree_last;
>   };
>   
> diff --git a/include/rdma/ib_umem_odp.h b/include/rdma/ib_umem_odp.h
> index 253df1a1fa54..d0ae7aa2139b 100644
> --- a/include/rdma/ib_umem_odp.h
> +++ b/include/rdma/ib_umem_odp.h
> @@ -97,7 +97,7 @@ static inline unsigned long ib_umem_start(struct ib_umem_odp *umem_odp)
>   /* Returns the address of the page after the last one of an ODP umem. */
>   static inline unsigned long ib_umem_end(struct ib_umem_odp *umem_odp)
>   {
> -	return umem_odp->interval_tree.last + 1;
> +	return umem_odp->interval_tree.end;
>   }
>   
>   static inline size_t ib_umem_odp_num_pages(struct ib_umem_odp *umem_odp)
> @@ -165,7 +165,7 @@ rbt_ib_umem_lookup(struct rb_root_cached *root, u64 addr, u64 length)
>   {
>   	struct interval_tree_node *node;
>   
> -	node = interval_tree_iter_first(root, addr, addr + length - 1);
> +	node = interval_tree_iter_first(root, addr, addr + length);
>   	if (!node)
>   		return NULL;
>   	return container_of(node, struct ib_umem_odp, interval_tree);
> diff --git a/lib/interval_tree.c b/lib/interval_tree.c
> index 593ce56ece50..336ec5113a28 100644
> --- a/lib/interval_tree.c
> +++ b/lib/interval_tree.c
> @@ -1,15 +1,15 @@
>   // SPDX-License-Identifier: GPL-2.0-only
>   #include <linux/interval_tree.h>
> -#include <linux/interval_tree_generic.h>
> +#include <linux/interval_tree_gen.h>
>   #include <linux/compiler.h>
>   #include <linux/export.h>
>   
>   #define START(node) ((node)->start)
> -#define LAST(node)  ((node)->last)
> +#define END(node)  ((node)->end)
>   
>   INTERVAL_TREE_DEFINE(struct interval_tree_node, rb,
>   		     unsigned long, __subtree_last,
> -		     START, LAST,, interval_tree)
> +		     START, END,, interval_tree)
>   
>   EXPORT_SYMBOL_GPL(interval_tree_insert);
>   EXPORT_SYMBOL_GPL(interval_tree_remove);
Christian König Oct. 4, 2019, 7:20 a.m. UTC | #2
Am 04.10.19 um 08:57 schrieb Christian König:
> Am 03.10.19 um 22:18 schrieb Davidlohr Bueso:
>> The generic tree tree really wants [a, b) intervals, not fully closed.
>> As such convert it to use the new interval_tree_gen.h. Most of the
>> conversions are straightforward, with the exception of perhaps
>> radeon_vm_bo_set_addr(), but semantics have been tried to be left
>> untouched.
>
> NAK, the whole thing won't work.
>
> See we need to handle the full device address space which means we 
> have values in the range of 0x0-0xffffffff.
>
> If you make this a closed interval then the end would wrap around to 
> 0x0 if long is only 32bit.

Well I've just now re-read the subject line. From that it sounds like 
you are actually trying to fix the interval tree to use a half closed 
interval, e.g. something like [a, b[

But your code changes sometimes doesn't seem to reflect that.

Regards,
Christian.

>
> Regards,
> Christian.
>
>>
>> Cc: "Christian König" <christian.koenig@amd.com>
>> Cc: Alex Deucher <alexander.deucher@amd.com>
>> Cc: David Airlie <airlied@linux.ie>
>> Cc: Daniel Vetter <daniel@ffwll.ch>
>> Cc: Doug Ledford <dledford@redhat.com>
>> Cc: Joerg Roedel <joro@8bytes.org>
>> Cc: "Jérôme Glisse" <jglisse@redhat.com>
>> Cc: dri-devel@lists.freedesktop.org
>> Cc: linux-rdma@vger.kernel.org
>> Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
>> ---
>>   drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c      | 12 +++---------
>>   drivers/gpu/drm/i915/gem/i915_gem_userptr.c |  5 +----
>>   drivers/gpu/drm/radeon/radeon_mn.c          | 11 ++++-------
>>   drivers/gpu/drm/radeon/radeon_trace.h       |  2 +-
>>   drivers/gpu/drm/radeon/radeon_vm.c          | 26 
>> +++++++++++++-------------
>>   drivers/infiniband/core/umem_odp.c          | 21 +++++++--------------
>>   drivers/iommu/virtio-iommu.c                |  6 +++---
>>   include/linux/interval_tree.h               |  2 +-
>>   include/rdma/ib_umem_odp.h                  |  4 ++--
>>   lib/interval_tree.c                         |  6 +++---
>>   10 files changed, 38 insertions(+), 57 deletions(-)
>>
>> diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c 
>> b/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c
>> index 31d4deb5d294..4bbaa9ffa570 100644
>> --- a/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c
>> +++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c
>> @@ -205,9 +205,6 @@ amdgpu_mn_sync_pagetables_gfx(struct hmm_mirror 
>> *mirror,
>>       bool blockable = mmu_notifier_range_blockable(update);
>>       struct interval_tree_node *it;
>>   -    /* notification is exclusive, but interval is inclusive */
>> -    end -= 1;
>> -
>>       /* TODO we should be able to split locking for interval tree and
>>        * amdgpu_mn_invalidate_node
>>        */
>> @@ -254,9 +251,6 @@ amdgpu_mn_sync_pagetables_hsa(struct hmm_mirror 
>> *mirror,
>>       bool blockable = mmu_notifier_range_blockable(update);
>>       struct interval_tree_node *it;
>>   -    /* notification is exclusive, but interval is inclusive */
>> -    end -= 1;
>> -
>>       if (amdgpu_mn_read_lock(amn, blockable))
>>           return -EAGAIN;
>>   @@ -374,7 +368,7 @@ struct amdgpu_mn *amdgpu_mn_get(struct 
>> amdgpu_device *adev,
>>    */
>>   int amdgpu_mn_register(struct amdgpu_bo *bo, unsigned long addr)
>>   {
>> -    unsigned long end = addr + amdgpu_bo_size(bo) - 1;
>> +    unsigned long end = addr + amdgpu_bo_size(bo);
>>       struct amdgpu_device *adev = amdgpu_ttm_adev(bo->tbo.bdev);
>>       enum amdgpu_mn_type type =
>>           bo->kfd_bo ? AMDGPU_MN_TYPE_HSA : AMDGPU_MN_TYPE_GFX;
>> @@ -400,7 +394,7 @@ int amdgpu_mn_register(struct amdgpu_bo *bo, 
>> unsigned long addr)
>>           node = container_of(it, struct amdgpu_mn_node, it);
>>           interval_tree_remove(&node->it, &amn->objects);
>>           addr = min(it->start, addr);
>> -        end = max(it->last, end);
>> +        end = max(it->end, end);
>>           list_splice(&node->bos, &bos);
>>       }
>>   @@ -412,7 +406,7 @@ int amdgpu_mn_register(struct amdgpu_bo *bo, 
>> unsigned long addr)
>>       bo->mn = amn;
>>         node->it.start = addr;
>> -    node->it.last = end;
>> +    node->it.end = end;
>>       INIT_LIST_HEAD(&node->bos);
>>       list_splice(&bos, &node->bos);
>>       list_add(&bo->mn_list, &node->bos);
>> diff --git a/drivers/gpu/drm/i915/gem/i915_gem_userptr.c 
>> b/drivers/gpu/drm/i915/gem/i915_gem_userptr.c
>> index 11b231c187c5..818ff6b33102 100644
>> --- a/drivers/gpu/drm/i915/gem/i915_gem_userptr.c
>> +++ b/drivers/gpu/drm/i915/gem/i915_gem_userptr.c
>> @@ -99,9 +99,6 @@ userptr_mn_invalidate_range_start(struct 
>> mmu_notifier *_mn,
>>       if (RB_EMPTY_ROOT(&mn->objects.rb_root))
>>           return 0;
>>   -    /* interval ranges are inclusive, but invalidate range is 
>> exclusive */
>> -    end = range->end - 1;
>> -
>>       spin_lock(&mn->lock);
>>       it = interval_tree_iter_first(&mn->objects, range->start, end);
>>       while (it) {
>> @@ -275,7 +272,7 @@ i915_gem_userptr_init__mmu_notifier(struct 
>> drm_i915_gem_object *obj,
>>       mo->mn = mn;
>>       mo->obj = obj;
>>       mo->it.start = obj->userptr.ptr;
>> -    mo->it.last = obj->userptr.ptr + obj->base.size - 1;
>> +    mo->it.end = obj->userptr.ptr + obj->base.size;
>>       RB_CLEAR_NODE(&mo->it.rb);
>>         obj->userptr.mmu_object = mo;
>> diff --git a/drivers/gpu/drm/radeon/radeon_mn.c 
>> b/drivers/gpu/drm/radeon/radeon_mn.c
>> index dbab9a3a969b..4810421dacc2 100644
>> --- a/drivers/gpu/drm/radeon/radeon_mn.c
>> +++ b/drivers/gpu/drm/radeon/radeon_mn.c
>> @@ -66,12 +66,9 @@ static int radeon_mn_invalidate_range_start(struct 
>> mmu_notifier *mn,
>>       struct radeon_mn *rmn = container_of(mn, struct radeon_mn, mn);
>>       struct ttm_operation_ctx ctx = { false, false };
>>       struct interval_tree_node *it;
>> -    unsigned long end;
>> +    unsigned long end = range->end;
>>       int ret = 0;
>>   -    /* notification is exclusive, but interval is inclusive */
>> -    end = range->end - 1;
>> -
>>       /* TODO we should be able to split locking for interval tree and
>>        * the tear down.
>>        */
>> @@ -174,7 +171,7 @@ static const struct mmu_notifier_ops 
>> radeon_mn_ops = {
>>    */
>>   int radeon_mn_register(struct radeon_bo *bo, unsigned long addr)
>>   {
>> -    unsigned long end = addr + radeon_bo_size(bo) - 1;
>> +    unsigned long end = addr + radeon_bo_size(bo);
>>       struct mmu_notifier *mn;
>>       struct radeon_mn *rmn;
>>       struct radeon_mn_node *node = NULL;
>> @@ -195,7 +192,7 @@ int radeon_mn_register(struct radeon_bo *bo, 
>> unsigned long addr)
>>           node = container_of(it, struct radeon_mn_node, it);
>>           interval_tree_remove(&node->it, &rmn->objects);
>>           addr = min(it->start, addr);
>> -        end = max(it->last, end);
>> +        end = max(it->end, end);
>>           list_splice(&node->bos, &bos);
>>       }
>>   @@ -210,7 +207,7 @@ int radeon_mn_register(struct radeon_bo *bo, 
>> unsigned long addr)
>>       bo->mn = rmn;
>>         node->it.start = addr;
>> -    node->it.last = end;
>> +    node->it.end = end;
>>       INIT_LIST_HEAD(&node->bos);
>>       list_splice(&bos, &node->bos);
>>       list_add(&bo->mn_list, &node->bos);
>> diff --git a/drivers/gpu/drm/radeon/radeon_trace.h 
>> b/drivers/gpu/drm/radeon/radeon_trace.h
>> index c93f3ab3c4e3..4324f3fc5d82 100644
>> --- a/drivers/gpu/drm/radeon/radeon_trace.h
>> +++ b/drivers/gpu/drm/radeon/radeon_trace.h
>> @@ -73,7 +73,7 @@ TRACE_EVENT(radeon_vm_bo_update,
>>             TP_fast_assign(
>>                  __entry->soffset = bo_va->it.start;
>> -               __entry->eoffset = bo_va->it.last + 1;
>> +               __entry->eoffset = bo_va->it.end;
>>                  __entry->flags = bo_va->flags;
>>                  ),
>>           TP_printk("soffs=%010llx, eoffs=%010llx, flags=%08x",
>> diff --git a/drivers/gpu/drm/radeon/radeon_vm.c 
>> b/drivers/gpu/drm/radeon/radeon_vm.c
>> index e0ad547786e8..b2a54aff21f4 100644
>> --- a/drivers/gpu/drm/radeon/radeon_vm.c
>> +++ b/drivers/gpu/drm/radeon/radeon_vm.c
>> @@ -329,7 +329,7 @@ struct radeon_bo_va *radeon_vm_bo_add(struct 
>> radeon_device *rdev,
>>       bo_va->vm = vm;
>>       bo_va->bo = bo;
>>       bo_va->it.start = 0;
>> -    bo_va->it.last = 0;
>> +    bo_va->it.end = 0;
>>       bo_va->flags = 0;
>>       bo_va->ref_count = 1;
>>       INIT_LIST_HEAD(&bo_va->bo_list);
>> @@ -456,7 +456,7 @@ int radeon_vm_bo_set_addr(struct radeon_device 
>> *rdev,
>>         if (soffset) {
>>           /* make sure object fit at this offset */
>> -        eoffset = soffset + size - 1;
>> +        eoffset = soffset + size;
>>           if (soffset >= eoffset) {
>>               r = -EINVAL;
>>               goto error_unreserve;
>> @@ -486,14 +486,14 @@ int radeon_vm_bo_set_addr(struct radeon_device 
>> *rdev,
>>               /* bo and tmp overlap, invalid offset */
>>               dev_err(rdev->dev, "bo %p va 0x%010Lx conflict with "
>>                   "(bo %p 0x%010lx 0x%010lx)\n", bo_va->bo,
>> -                soffset, tmp->bo, tmp->it.start, tmp->it.last);
>> +                soffset, tmp->bo, tmp->it.start, tmp->it.end);
>>               mutex_unlock(&vm->mutex);
>>               r = -EINVAL;
>>               goto error_unreserve;
>>           }
>>       }
>>   -    if (bo_va->it.start || bo_va->it.last) {
>> +    if (bo_va->it.start || bo_va->it.end) {
>>           /* add a clone of the bo_va to clear the old address */
>>           struct radeon_bo_va *tmp;
>>           tmp = kzalloc(sizeof(struct radeon_bo_va), GFP_KERNEL);
>> @@ -503,14 +503,14 @@ int radeon_vm_bo_set_addr(struct radeon_device 
>> *rdev,
>>               goto error_unreserve;
>>           }
>>           tmp->it.start = bo_va->it.start;
>> -        tmp->it.last = bo_va->it.last;
>> +        tmp->it.end = bo_va->it.end;
>>           tmp->vm = vm;
>>           tmp->bo = radeon_bo_ref(bo_va->bo);
>>             interval_tree_remove(&bo_va->it, &vm->va);
>>           spin_lock(&vm->status_lock);
>>           bo_va->it.start = 0;
>> -        bo_va->it.last = 0;
>> +        bo_va->it.end = 0;
>>           list_del_init(&bo_va->vm_status);
>>           list_add(&tmp->vm_status, &vm->freed);
>>           spin_unlock(&vm->status_lock);
>> @@ -519,7 +519,7 @@ int radeon_vm_bo_set_addr(struct radeon_device 
>> *rdev,
>>       if (soffset || eoffset) {
>>           spin_lock(&vm->status_lock);
>>           bo_va->it.start = soffset;
>> -        bo_va->it.last = eoffset;
>> +        bo_va->it.end = eoffset;
>>           list_add(&bo_va->vm_status, &vm->cleared);
>>           spin_unlock(&vm->status_lock);
>>           interval_tree_insert(&bo_va->it, &vm->va);
>> @@ -964,7 +964,7 @@ int radeon_vm_bo_update(struct radeon_device *rdev,
>>         trace_radeon_vm_bo_update(bo_va);
>>   -    nptes = bo_va->it.last - bo_va->it.start + 1;
>> +    nptes = bo_va->it.end - bo_va->it.start;
>>         /* reserve space for one command every (1 << BLOCK_SIZE) entries
>>          or 2k dwords (whatever is smaller) */
>> @@ -1010,7 +1010,7 @@ int radeon_vm_bo_update(struct radeon_device 
>> *rdev,
>>       }
>>         r = radeon_vm_update_ptes(rdev, vm, &ib, bo_va->it.start,
>> -                  bo_va->it.last + 1, addr,
>> +                  bo_va->it.end, addr,
>>                     radeon_vm_page_flags(bo_va->flags));
>>       if (r) {
>>           radeon_ib_free(rdev, &ib);
>> @@ -1026,7 +1026,7 @@ int radeon_vm_bo_update(struct radeon_device 
>> *rdev,
>>           return r;
>>       }
>>       ib.fence->is_vm_update = true;
>> -    radeon_vm_fence_pts(vm, bo_va->it.start, bo_va->it.last + 1, 
>> ib.fence);
>> +    radeon_vm_fence_pts(vm, bo_va->it.start, bo_va->it.end, ib.fence);
>>       radeon_fence_unref(&bo_va->last_pt_update);
>>       bo_va->last_pt_update = radeon_fence_ref(ib.fence);
>>       radeon_ib_free(rdev, &ib);
>> @@ -1124,12 +1124,12 @@ void radeon_vm_bo_rmv(struct radeon_device 
>> *rdev,
>>       list_del(&bo_va->bo_list);
>>         mutex_lock(&vm->mutex);
>> -    if (bo_va->it.start || bo_va->it.last)
>> +    if (bo_va->it.start || bo_va->it.end)
>>           interval_tree_remove(&bo_va->it, &vm->va);
>>         spin_lock(&vm->status_lock);
>>       list_del(&bo_va->vm_status);
>> -    if (bo_va->it.start || bo_va->it.last) {
>> +    if (bo_va->it.start || bo_va->it.end) {
>>           bo_va->bo = radeon_bo_ref(bo_va->bo);
>>           list_add(&bo_va->vm_status, &vm->freed);
>>       } else {
>> @@ -1158,7 +1158,7 @@ void radeon_vm_bo_invalidate(struct 
>> radeon_device *rdev,
>>       list_for_each_entry(bo_va, &bo->va, bo_list) {
>>           spin_lock(&bo_va->vm->status_lock);
>>           if (list_empty(&bo_va->vm_status) &&
>> -            (bo_va->it.start || bo_va->it.last))
>> +            (bo_va->it.start || bo_va->it.end))
>>               list_add(&bo_va->vm_status, &bo_va->vm->invalidated);
>>           spin_unlock(&bo_va->vm->status_lock);
>>       }
>> diff --git a/drivers/infiniband/core/umem_odp.c 
>> b/drivers/infiniband/core/umem_odp.c
>> index f67a30fda1ed..9b7ac93223d6 100644
>> --- a/drivers/infiniband/core/umem_odp.c
>> +++ b/drivers/infiniband/core/umem_odp.c
>> @@ -219,26 +219,19 @@ static inline int ib_init_umem_odp(struct 
>> ib_umem_odp *umem_odp)
>>               ALIGN_DOWN(umem_odp->umem.address, page_size);
>>           if (check_add_overflow(umem_odp->umem.address,
>>                          (unsigned long)umem_odp->umem.length,
>> -                       &umem_odp->interval_tree.last))
>> +                       &umem_odp->interval_tree.end))
>>               return -EOVERFLOW;
>> -        umem_odp->interval_tree.last =
>> -            ALIGN(umem_odp->interval_tree.last, page_size);
>> -        if (unlikely(umem_odp->interval_tree.last < page_size))
>> +        umem_odp->interval_tree.end =
>> +            ALIGN(umem_odp->interval_tree.end, page_size);
>> +        if (unlikely(umem_odp->interval_tree.end < page_size))
>>               return -EOVERFLOW;
>>   -        pages = (umem_odp->interval_tree.last -
>> +        pages = (umem_odp->interval_tree.end -
>>                umem_odp->interval_tree.start) >>
>>               umem_odp->page_shift;
>>           if (!pages)
>>               return -EINVAL;
>>   -        /*
>> -         * Note that the representation of the intervals in the
>> -         * interval tree considers the ending point as contained in
>> -         * the interval.
>> -         */
>> -        umem_odp->interval_tree.last--;
>> -
>>           umem_odp->page_list = kvcalloc(
>>               pages, sizeof(*umem_odp->page_list), GFP_KERNEL);
>>           if (!umem_odp->page_list)
>> @@ -777,12 +770,12 @@ int rbt_ib_umem_for_each_in_range(struct 
>> rb_root_cached *root,
>>       if (unlikely(start == last))
>>           return ret_val;
>>   -    for (node = interval_tree_iter_first(root, start, last - 1);
>> +    for (node = interval_tree_iter_first(root, start, last);
>>               node; node = next) {
>>           /* TODO move the blockable decision up to the callback */
>>           if (!blockable)
>>               return -EAGAIN;
>> -        next = interval_tree_iter_next(node, start, last - 1);
>> +        next = interval_tree_iter_next(node, start, last);
>>           umem = container_of(node, struct ib_umem_odp, interval_tree);
>>           ret_val = cb(umem, start, last, cookie) || ret_val;
>>       }
>> diff --git a/drivers/iommu/virtio-iommu.c b/drivers/iommu/virtio-iommu.c
>> index 3ea9d7682999..771740981f43 100644
>> --- a/drivers/iommu/virtio-iommu.c
>> +++ b/drivers/iommu/virtio-iommu.c
>> @@ -323,7 +323,7 @@ static int viommu_add_mapping(struct 
>> viommu_domain *vdomain, unsigned long iova,
>>         mapping->paddr        = paddr;
>>       mapping->iova.start    = iova;
>> -    mapping->iova.last    = iova + size - 1;
>> +    mapping->iova.end    = iova + size;
>>       mapping->flags        = flags;
>>         spin_lock_irqsave(&vdomain->mappings_lock, irqflags);
>> @@ -348,7 +348,7 @@ static size_t viommu_del_mappings(struct 
>> viommu_domain *vdomain,
>>   {
>>       size_t unmapped = 0;
>>       unsigned long flags;
>> -    unsigned long last = iova + size - 1;
>> +    unsigned long last = iova + size;
>>       struct viommu_mapping *mapping = NULL;
>>       struct interval_tree_node *node, *next;
>>   @@ -367,7 +367,7 @@ static size_t viommu_del_mappings(struct 
>> viommu_domain *vdomain,
>>            * Virtio-iommu doesn't allow UNMAP to split a mapping created
>>            * with a single MAP request, so remove the full mapping.
>>            */
>> -        unmapped += mapping->iova.last - mapping->iova.start + 1;
>> +        unmapped += mapping->iova.end - mapping->iova.start;
>>             interval_tree_remove(node, &vdomain->mappings);
>>           kfree(mapping);
>> diff --git a/include/linux/interval_tree.h 
>> b/include/linux/interval_tree.h
>> index 288c26f50732..f3d1ea9e4003 100644
>> --- a/include/linux/interval_tree.h
>> +++ b/include/linux/interval_tree.h
>> @@ -7,7 +7,7 @@
>>   struct interval_tree_node {
>>       struct rb_node rb;
>>       unsigned long start;    /* Start of interval */
>> -    unsigned long last;    /* Last location _in_ interval */
>> +    unsigned long end;    /* Last location _outside_ interval */
>>       unsigned long __subtree_last;
>>   };
>>   diff --git a/include/rdma/ib_umem_odp.h b/include/rdma/ib_umem_odp.h
>> index 253df1a1fa54..d0ae7aa2139b 100644
>> --- a/include/rdma/ib_umem_odp.h
>> +++ b/include/rdma/ib_umem_odp.h
>> @@ -97,7 +97,7 @@ static inline unsigned long ib_umem_start(struct 
>> ib_umem_odp *umem_odp)
>>   /* Returns the address of the page after the last one of an ODP 
>> umem. */
>>   static inline unsigned long ib_umem_end(struct ib_umem_odp *umem_odp)
>>   {
>> -    return umem_odp->interval_tree.last + 1;
>> +    return umem_odp->interval_tree.end;
>>   }
>>     static inline size_t ib_umem_odp_num_pages(struct ib_umem_odp 
>> *umem_odp)
>> @@ -165,7 +165,7 @@ rbt_ib_umem_lookup(struct rb_root_cached *root, 
>> u64 addr, u64 length)
>>   {
>>       struct interval_tree_node *node;
>>   -    node = interval_tree_iter_first(root, addr, addr + length - 1);
>> +    node = interval_tree_iter_first(root, addr, addr + length);
>>       if (!node)
>>           return NULL;
>>       return container_of(node, struct ib_umem_odp, interval_tree);
>> diff --git a/lib/interval_tree.c b/lib/interval_tree.c
>> index 593ce56ece50..336ec5113a28 100644
>> --- a/lib/interval_tree.c
>> +++ b/lib/interval_tree.c
>> @@ -1,15 +1,15 @@
>>   // SPDX-License-Identifier: GPL-2.0-only
>>   #include <linux/interval_tree.h>
>> -#include <linux/interval_tree_generic.h>
>> +#include <linux/interval_tree_gen.h>
>>   #include <linux/compiler.h>
>>   #include <linux/export.h>
>>     #define START(node) ((node)->start)
>> -#define LAST(node)  ((node)->last)
>> +#define END(node)  ((node)->end)
>>     INTERVAL_TREE_DEFINE(struct interval_tree_node, rb,
>>                unsigned long, __subtree_last,
>> -             START, LAST,, interval_tree)
>> +             START, END,, interval_tree)
>>     EXPORT_SYMBOL_GPL(interval_tree_insert);
>>   EXPORT_SYMBOL_GPL(interval_tree_remove);
>
Davidlohr Bueso Oct. 8, 2019, 4:59 p.m. UTC | #3
On Fri, 04 Oct 2019, Koenig, Christian wrote:

>Am 04.10.19 um 08:57 schrieb Christian König:
>> Am 03.10.19 um 22:18 schrieb Davidlohr Bueso:
>>> The generic tree tree really wants [a, b) intervals, not fully closed.
>>> As such convert it to use the new interval_tree_gen.h. Most of the
>>> conversions are straightforward, with the exception of perhaps
>>> radeon_vm_bo_set_addr(), but semantics have been tried to be left
>>> untouched.
>>
>> NAK, the whole thing won't work.
>>
>> See we need to handle the full device address space which means we
>> have values in the range of 0x0-0xffffffff.
>>
>> If you make this a closed interval then the end would wrap around to
>> 0x0 if long is only 32bit.
>
>Well I've just now re-read the subject line. From that it sounds like
>you are actually trying to fix the interval tree to use a half closed
>interval, e.g. something like [a, b[

Correct.

>
>But your code changes sometimes doesn't seem to reflect that.

Hmm the change simply aims at avoiding the end - 1 trick when dealing
with interval_tree insertions and lookups; the rest of the series
converts other interval tree users in a similar way, albeit some errors
which will be updated. What are your concerns about this patch?

Thanks,
Davidlohr

Patch
diff mbox series

diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c b/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c
index 31d4deb5d294..4bbaa9ffa570 100644
--- a/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c
+++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c
@@ -205,9 +205,6 @@  amdgpu_mn_sync_pagetables_gfx(struct hmm_mirror *mirror,
 	bool blockable = mmu_notifier_range_blockable(update);
 	struct interval_tree_node *it;
 
-	/* notification is exclusive, but interval is inclusive */
-	end -= 1;
-
 	/* TODO we should be able to split locking for interval tree and
 	 * amdgpu_mn_invalidate_node
 	 */
@@ -254,9 +251,6 @@  amdgpu_mn_sync_pagetables_hsa(struct hmm_mirror *mirror,
 	bool blockable = mmu_notifier_range_blockable(update);
 	struct interval_tree_node *it;
 
-	/* notification is exclusive, but interval is inclusive */
-	end -= 1;
-
 	if (amdgpu_mn_read_lock(amn, blockable))
 		return -EAGAIN;
 
@@ -374,7 +368,7 @@  struct amdgpu_mn *amdgpu_mn_get(struct amdgpu_device *adev,
  */
 int amdgpu_mn_register(struct amdgpu_bo *bo, unsigned long addr)
 {
-	unsigned long end = addr + amdgpu_bo_size(bo) - 1;
+	unsigned long end = addr + amdgpu_bo_size(bo);
 	struct amdgpu_device *adev = amdgpu_ttm_adev(bo->tbo.bdev);
 	enum amdgpu_mn_type type =
 		bo->kfd_bo ? AMDGPU_MN_TYPE_HSA : AMDGPU_MN_TYPE_GFX;
@@ -400,7 +394,7 @@  int amdgpu_mn_register(struct amdgpu_bo *bo, unsigned long addr)
 		node = container_of(it, struct amdgpu_mn_node, it);
 		interval_tree_remove(&node->it, &amn->objects);
 		addr = min(it->start, addr);
-		end = max(it->last, end);
+		end = max(it->end, end);
 		list_splice(&node->bos, &bos);
 	}
 
@@ -412,7 +406,7 @@  int amdgpu_mn_register(struct amdgpu_bo *bo, unsigned long addr)
 	bo->mn = amn;
 
 	node->it.start = addr;
-	node->it.last = end;
+	node->it.end = end;
 	INIT_LIST_HEAD(&node->bos);
 	list_splice(&bos, &node->bos);
 	list_add(&bo->mn_list, &node->bos);
diff --git a/drivers/gpu/drm/i915/gem/i915_gem_userptr.c b/drivers/gpu/drm/i915/gem/i915_gem_userptr.c
index 11b231c187c5..818ff6b33102 100644
--- a/drivers/gpu/drm/i915/gem/i915_gem_userptr.c
+++ b/drivers/gpu/drm/i915/gem/i915_gem_userptr.c
@@ -99,9 +99,6 @@  userptr_mn_invalidate_range_start(struct mmu_notifier *_mn,
 	if (RB_EMPTY_ROOT(&mn->objects.rb_root))
 		return 0;
 
-	/* interval ranges are inclusive, but invalidate range is exclusive */
-	end = range->end - 1;
-
 	spin_lock(&mn->lock);
 	it = interval_tree_iter_first(&mn->objects, range->start, end);
 	while (it) {
@@ -275,7 +272,7 @@  i915_gem_userptr_init__mmu_notifier(struct drm_i915_gem_object *obj,
 	mo->mn = mn;
 	mo->obj = obj;
 	mo->it.start = obj->userptr.ptr;
-	mo->it.last = obj->userptr.ptr + obj->base.size - 1;
+	mo->it.end = obj->userptr.ptr + obj->base.size;
 	RB_CLEAR_NODE(&mo->it.rb);
 
 	obj->userptr.mmu_object = mo;
diff --git a/drivers/gpu/drm/radeon/radeon_mn.c b/drivers/gpu/drm/radeon/radeon_mn.c
index dbab9a3a969b..4810421dacc2 100644
--- a/drivers/gpu/drm/radeon/radeon_mn.c
+++ b/drivers/gpu/drm/radeon/radeon_mn.c
@@ -66,12 +66,9 @@  static int radeon_mn_invalidate_range_start(struct mmu_notifier *mn,
 	struct radeon_mn *rmn = container_of(mn, struct radeon_mn, mn);
 	struct ttm_operation_ctx ctx = { false, false };
 	struct interval_tree_node *it;
-	unsigned long end;
+	unsigned long end = range->end;
 	int ret = 0;
 
-	/* notification is exclusive, but interval is inclusive */
-	end = range->end - 1;
-
 	/* TODO we should be able to split locking for interval tree and
 	 * the tear down.
 	 */
@@ -174,7 +171,7 @@  static const struct mmu_notifier_ops radeon_mn_ops = {
  */
 int radeon_mn_register(struct radeon_bo *bo, unsigned long addr)
 {
-	unsigned long end = addr + radeon_bo_size(bo) - 1;
+	unsigned long end = addr + radeon_bo_size(bo);
 	struct mmu_notifier *mn;
 	struct radeon_mn *rmn;
 	struct radeon_mn_node *node = NULL;
@@ -195,7 +192,7 @@  int radeon_mn_register(struct radeon_bo *bo, unsigned long addr)
 		node = container_of(it, struct radeon_mn_node, it);
 		interval_tree_remove(&node->it, &rmn->objects);
 		addr = min(it->start, addr);
-		end = max(it->last, end);
+		end = max(it->end, end);
 		list_splice(&node->bos, &bos);
 	}
 
@@ -210,7 +207,7 @@  int radeon_mn_register(struct radeon_bo *bo, unsigned long addr)
 	bo->mn = rmn;
 
 	node->it.start = addr;
-	node->it.last = end;
+	node->it.end = end;
 	INIT_LIST_HEAD(&node->bos);
 	list_splice(&bos, &node->bos);
 	list_add(&bo->mn_list, &node->bos);
diff --git a/drivers/gpu/drm/radeon/radeon_trace.h b/drivers/gpu/drm/radeon/radeon_trace.h
index c93f3ab3c4e3..4324f3fc5d82 100644
--- a/drivers/gpu/drm/radeon/radeon_trace.h
+++ b/drivers/gpu/drm/radeon/radeon_trace.h
@@ -73,7 +73,7 @@  TRACE_EVENT(radeon_vm_bo_update,
 
 	    TP_fast_assign(
 			   __entry->soffset = bo_va->it.start;
-			   __entry->eoffset = bo_va->it.last + 1;
+			   __entry->eoffset = bo_va->it.end;
 			   __entry->flags = bo_va->flags;
 			   ),
 	    TP_printk("soffs=%010llx, eoffs=%010llx, flags=%08x",
diff --git a/drivers/gpu/drm/radeon/radeon_vm.c b/drivers/gpu/drm/radeon/radeon_vm.c
index e0ad547786e8..b2a54aff21f4 100644
--- a/drivers/gpu/drm/radeon/radeon_vm.c
+++ b/drivers/gpu/drm/radeon/radeon_vm.c
@@ -329,7 +329,7 @@  struct radeon_bo_va *radeon_vm_bo_add(struct radeon_device *rdev,
 	bo_va->vm = vm;
 	bo_va->bo = bo;
 	bo_va->it.start = 0;
-	bo_va->it.last = 0;
+	bo_va->it.end = 0;
 	bo_va->flags = 0;
 	bo_va->ref_count = 1;
 	INIT_LIST_HEAD(&bo_va->bo_list);
@@ -456,7 +456,7 @@  int radeon_vm_bo_set_addr(struct radeon_device *rdev,
 
 	if (soffset) {
 		/* make sure object fit at this offset */
-		eoffset = soffset + size - 1;
+		eoffset = soffset + size;
 		if (soffset >= eoffset) {
 			r = -EINVAL;
 			goto error_unreserve;
@@ -486,14 +486,14 @@  int radeon_vm_bo_set_addr(struct radeon_device *rdev,
 			/* bo and tmp overlap, invalid offset */
 			dev_err(rdev->dev, "bo %p va 0x%010Lx conflict with "
 				"(bo %p 0x%010lx 0x%010lx)\n", bo_va->bo,
-				soffset, tmp->bo, tmp->it.start, tmp->it.last);
+				soffset, tmp->bo, tmp->it.start, tmp->it.end);
 			mutex_unlock(&vm->mutex);
 			r = -EINVAL;
 			goto error_unreserve;
 		}
 	}
 
-	if (bo_va->it.start || bo_va->it.last) {
+	if (bo_va->it.start || bo_va->it.end) {
 		/* add a clone of the bo_va to clear the old address */
 		struct radeon_bo_va *tmp;
 		tmp = kzalloc(sizeof(struct radeon_bo_va), GFP_KERNEL);
@@ -503,14 +503,14 @@  int radeon_vm_bo_set_addr(struct radeon_device *rdev,
 			goto error_unreserve;
 		}
 		tmp->it.start = bo_va->it.start;
-		tmp->it.last = bo_va->it.last;
+		tmp->it.end = bo_va->it.end;
 		tmp->vm = vm;
 		tmp->bo = radeon_bo_ref(bo_va->bo);
 
 		interval_tree_remove(&bo_va->it, &vm->va);
 		spin_lock(&vm->status_lock);
 		bo_va->it.start = 0;
-		bo_va->it.last = 0;
+		bo_va->it.end = 0;
 		list_del_init(&bo_va->vm_status);
 		list_add(&tmp->vm_status, &vm->freed);
 		spin_unlock(&vm->status_lock);
@@ -519,7 +519,7 @@  int radeon_vm_bo_set_addr(struct radeon_device *rdev,
 	if (soffset || eoffset) {
 		spin_lock(&vm->status_lock);
 		bo_va->it.start = soffset;
-		bo_va->it.last = eoffset;
+		bo_va->it.end = eoffset;
 		list_add(&bo_va->vm_status, &vm->cleared);
 		spin_unlock(&vm->status_lock);
 		interval_tree_insert(&bo_va->it, &vm->va);
@@ -964,7 +964,7 @@  int radeon_vm_bo_update(struct radeon_device *rdev,
 
 	trace_radeon_vm_bo_update(bo_va);
 
-	nptes = bo_va->it.last - bo_va->it.start + 1;
+	nptes = bo_va->it.end - bo_va->it.start;
 
 	/* reserve space for one command every (1 << BLOCK_SIZE) entries
 	   or 2k dwords (whatever is smaller) */
@@ -1010,7 +1010,7 @@  int radeon_vm_bo_update(struct radeon_device *rdev,
 	}
 
 	r = radeon_vm_update_ptes(rdev, vm, &ib, bo_va->it.start,
-				  bo_va->it.last + 1, addr,
+				  bo_va->it.end, addr,
 				  radeon_vm_page_flags(bo_va->flags));
 	if (r) {
 		radeon_ib_free(rdev, &ib);
@@ -1026,7 +1026,7 @@  int radeon_vm_bo_update(struct radeon_device *rdev,
 		return r;
 	}
 	ib.fence->is_vm_update = true;
-	radeon_vm_fence_pts(vm, bo_va->it.start, bo_va->it.last + 1, ib.fence);
+	radeon_vm_fence_pts(vm, bo_va->it.start, bo_va->it.end, ib.fence);
 	radeon_fence_unref(&bo_va->last_pt_update);
 	bo_va->last_pt_update = radeon_fence_ref(ib.fence);
 	radeon_ib_free(rdev, &ib);
@@ -1124,12 +1124,12 @@  void radeon_vm_bo_rmv(struct radeon_device *rdev,
 	list_del(&bo_va->bo_list);
 
 	mutex_lock(&vm->mutex);
-	if (bo_va->it.start || bo_va->it.last)
+	if (bo_va->it.start || bo_va->it.end)
 		interval_tree_remove(&bo_va->it, &vm->va);
 
 	spin_lock(&vm->status_lock);
 	list_del(&bo_va->vm_status);
-	if (bo_va->it.start || bo_va->it.last) {
+	if (bo_va->it.start || bo_va->it.end) {
 		bo_va->bo = radeon_bo_ref(bo_va->bo);
 		list_add(&bo_va->vm_status, &vm->freed);
 	} else {
@@ -1158,7 +1158,7 @@  void radeon_vm_bo_invalidate(struct radeon_device *rdev,
 	list_for_each_entry(bo_va, &bo->va, bo_list) {
 		spin_lock(&bo_va->vm->status_lock);
 		if (list_empty(&bo_va->vm_status) &&
-		    (bo_va->it.start || bo_va->it.last))
+		    (bo_va->it.start || bo_va->it.end))
 			list_add(&bo_va->vm_status, &bo_va->vm->invalidated);
 		spin_unlock(&bo_va->vm->status_lock);
 	}
diff --git a/drivers/infiniband/core/umem_odp.c b/drivers/infiniband/core/umem_odp.c
index f67a30fda1ed..9b7ac93223d6 100644
--- a/drivers/infiniband/core/umem_odp.c
+++ b/drivers/infiniband/core/umem_odp.c
@@ -219,26 +219,19 @@  static inline int ib_init_umem_odp(struct ib_umem_odp *umem_odp)
 			ALIGN_DOWN(umem_odp->umem.address, page_size);
 		if (check_add_overflow(umem_odp->umem.address,
 				       (unsigned long)umem_odp->umem.length,
-				       &umem_odp->interval_tree.last))
+				       &umem_odp->interval_tree.end))
 			return -EOVERFLOW;
-		umem_odp->interval_tree.last =
-			ALIGN(umem_odp->interval_tree.last, page_size);
-		if (unlikely(umem_odp->interval_tree.last < page_size))
+		umem_odp->interval_tree.end =
+			ALIGN(umem_odp->interval_tree.end, page_size);
+		if (unlikely(umem_odp->interval_tree.end < page_size))
 			return -EOVERFLOW;
 
-		pages = (umem_odp->interval_tree.last -
+		pages = (umem_odp->interval_tree.end -
 			 umem_odp->interval_tree.start) >>
 			umem_odp->page_shift;
 		if (!pages)
 			return -EINVAL;
 
-		/*
-		 * Note that the representation of the intervals in the
-		 * interval tree considers the ending point as contained in
-		 * the interval.
-		 */
-		umem_odp->interval_tree.last--;
-
 		umem_odp->page_list = kvcalloc(
 			pages, sizeof(*umem_odp->page_list), GFP_KERNEL);
 		if (!umem_odp->page_list)
@@ -777,12 +770,12 @@  int rbt_ib_umem_for_each_in_range(struct rb_root_cached *root,
 	if (unlikely(start == last))
 		return ret_val;
 
-	for (node = interval_tree_iter_first(root, start, last - 1);
+	for (node = interval_tree_iter_first(root, start, last);
 			node; node = next) {
 		/* TODO move the blockable decision up to the callback */
 		if (!blockable)
 			return -EAGAIN;
-		next = interval_tree_iter_next(node, start, last - 1);
+		next = interval_tree_iter_next(node, start, last);
 		umem = container_of(node, struct ib_umem_odp, interval_tree);
 		ret_val = cb(umem, start, last, cookie) || ret_val;
 	}
diff --git a/drivers/iommu/virtio-iommu.c b/drivers/iommu/virtio-iommu.c
index 3ea9d7682999..771740981f43 100644
--- a/drivers/iommu/virtio-iommu.c
+++ b/drivers/iommu/virtio-iommu.c
@@ -323,7 +323,7 @@  static int viommu_add_mapping(struct viommu_domain *vdomain, unsigned long iova,
 
 	mapping->paddr		= paddr;
 	mapping->iova.start	= iova;
-	mapping->iova.last	= iova + size - 1;
+	mapping->iova.end	= iova + size;
 	mapping->flags		= flags;
 
 	spin_lock_irqsave(&vdomain->mappings_lock, irqflags);
@@ -348,7 +348,7 @@  static size_t viommu_del_mappings(struct viommu_domain *vdomain,
 {
 	size_t unmapped = 0;
 	unsigned long flags;
-	unsigned long last = iova + size - 1;
+	unsigned long last = iova + size;
 	struct viommu_mapping *mapping = NULL;
 	struct interval_tree_node *node, *next;
 
@@ -367,7 +367,7 @@  static size_t viommu_del_mappings(struct viommu_domain *vdomain,
 		 * Virtio-iommu doesn't allow UNMAP to split a mapping created
 		 * with a single MAP request, so remove the full mapping.
 		 */
-		unmapped += mapping->iova.last - mapping->iova.start + 1;
+		unmapped += mapping->iova.end - mapping->iova.start;
 
 		interval_tree_remove(node, &vdomain->mappings);
 		kfree(mapping);
diff --git a/include/linux/interval_tree.h b/include/linux/interval_tree.h
index 288c26f50732..f3d1ea9e4003 100644
--- a/include/linux/interval_tree.h
+++ b/include/linux/interval_tree.h
@@ -7,7 +7,7 @@ 
 struct interval_tree_node {
 	struct rb_node rb;
 	unsigned long start;	/* Start of interval */
-	unsigned long last;	/* Last location _in_ interval */
+	unsigned long end;	/* Last location _outside_ interval */
 	unsigned long __subtree_last;
 };
 
diff --git a/include/rdma/ib_umem_odp.h b/include/rdma/ib_umem_odp.h
index 253df1a1fa54..d0ae7aa2139b 100644
--- a/include/rdma/ib_umem_odp.h
+++ b/include/rdma/ib_umem_odp.h
@@ -97,7 +97,7 @@  static inline unsigned long ib_umem_start(struct ib_umem_odp *umem_odp)
 /* Returns the address of the page after the last one of an ODP umem. */
 static inline unsigned long ib_umem_end(struct ib_umem_odp *umem_odp)
 {
-	return umem_odp->interval_tree.last + 1;
+	return umem_odp->interval_tree.end;
 }
 
 static inline size_t ib_umem_odp_num_pages(struct ib_umem_odp *umem_odp)
@@ -165,7 +165,7 @@  rbt_ib_umem_lookup(struct rb_root_cached *root, u64 addr, u64 length)
 {
 	struct interval_tree_node *node;
 
-	node = interval_tree_iter_first(root, addr, addr + length - 1);
+	node = interval_tree_iter_first(root, addr, addr + length);
 	if (!node)
 		return NULL;
 	return container_of(node, struct ib_umem_odp, interval_tree);
diff --git a/lib/interval_tree.c b/lib/interval_tree.c
index 593ce56ece50..336ec5113a28 100644
--- a/lib/interval_tree.c
+++ b/lib/interval_tree.c
@@ -1,15 +1,15 @@ 
 // SPDX-License-Identifier: GPL-2.0-only
 #include <linux/interval_tree.h>
-#include <linux/interval_tree_generic.h>
+#include <linux/interval_tree_gen.h>
 #include <linux/compiler.h>
 #include <linux/export.h>
 
 #define START(node) ((node)->start)
-#define LAST(node)  ((node)->last)
+#define END(node)  ((node)->end)
 
 INTERVAL_TREE_DEFINE(struct interval_tree_node, rb,
 		     unsigned long, __subtree_last,
-		     START, LAST,, interval_tree)
+		     START, END,, interval_tree)
 
 EXPORT_SYMBOL_GPL(interval_tree_insert);
 EXPORT_SYMBOL_GPL(interval_tree_remove);