From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.8 required=3.0 tests=HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY,SPF_HELO_NONE,SPF_PASS, USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id E60BDC10F14 for ; Thu, 3 Oct 2019 20:20:36 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 90C3B20862 for ; Thu, 3 Oct 2019 20:20:36 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 90C3B20862 Authentication-Results: mail.kernel.org; dmarc=none (p=none dis=none) header.from=stgolabs.net Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id 444BD6B0269; Thu, 3 Oct 2019 16:20:36 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 3F3456B026A; Thu, 3 Oct 2019 16:20:36 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2E1CC8E0003; Thu, 3 Oct 2019 16:20:36 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0180.hostedemail.com [216.40.44.180]) by kanga.kvack.org (Postfix) with ESMTP id 064E06B0269 for ; Thu, 3 Oct 2019 16:20:35 -0400 (EDT) Received: from smtpin27.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay02.hostedemail.com (Postfix) with SMTP id 99F2387F3 for ; Thu, 3 Oct 2019 20:20:35 +0000 (UTC) X-FDA: 76003591230.27.ship30_51a93bd1b408 X-HE-Tag: ship30_51a93bd1b408 X-Filterd-Recvd-Size: 17605 Received: from mx1.suse.de (mx2.suse.de [195.135.220.15]) by imf19.hostedemail.com (Postfix) with ESMTP for ; Thu, 3 Oct 2019 20:20:34 +0000 (UTC) X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id AEAD4B03B; Thu, 3 Oct 2019 20:20:33 +0000 (UTC) From: Davidlohr Bueso To: akpm@linux-foundation.org Cc: walken@google.com, peterz@infradead.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, dri-devel@lists.freedesktop.org, linux-rdma@vger.kernel.org, dave@stgolabs.net, =?UTF-8?q?Christian=20K=C3=B6nig?= , Alex Deucher , David Airlie , Daniel Vetter , Doug Ledford , Joerg Roedel , =?UTF-8?q?J=C3=A9r=C3=B4me=20Glisse?= , Davidlohr Bueso Subject: [PATCH 09/11] lib/interval-tree: convert interval_tree to half closed intervals Date: Thu, 3 Oct 2019 13:18:56 -0700 Message-Id: <20191003201858.11666-10-dave@stgolabs.net> X-Mailer: git-send-email 2.16.4 In-Reply-To: <20191003201858.11666-1-dave@stgolabs.net> References: <20191003201858.11666-1-dave@stgolabs.net> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 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=C3=B6nig" Cc: Alex Deucher Cc: David Airlie Cc: Daniel Vetter Cc: Doug Ledford Cc: Joerg Roedel Cc: "J=C3=A9r=C3=B4me Glisse" Cc: dri-devel@lists.freedesktop.org Cc: linux-rdma@vger.kernel.org Signed-off-by: Davidlohr Bueso --- 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 *mirr= or, bool blockable =3D mmu_notifier_range_blockable(update); struct interval_tree_node *it; =20 - /* notification is exclusive, but interval is inclusive */ - end -=3D 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 *mirr= or, bool blockable =3D mmu_notifier_range_blockable(update); struct interval_tree_node *it; =20 - /* notification is exclusive, but interval is inclusive */ - end -=3D 1; - if (amdgpu_mn_read_lock(amn, blockable)) return -EAGAIN; =20 @@ -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 =3D addr + amdgpu_bo_size(bo) - 1; + unsigned long end =3D addr + amdgpu_bo_size(bo); struct amdgpu_device *adev =3D amdgpu_ttm_adev(bo->tbo.bdev); enum amdgpu_mn_type type =3D 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 =3D container_of(it, struct amdgpu_mn_node, it); interval_tree_remove(&node->it, &amn->objects); addr =3D min(it->start, addr); - end =3D max(it->last, end); + end =3D max(it->end, end); list_splice(&node->bos, &bos); } =20 @@ -412,7 +406,7 @@ int amdgpu_mn_register(struct amdgpu_bo *bo, unsigned= long addr) bo->mn =3D amn; =20 node->it.start =3D addr; - node->it.last =3D end; + node->it.end =3D 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/dr= m/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; =20 - /* interval ranges are inclusive, but invalidate range is exclusive */ - end =3D range->end - 1; - spin_lock(&mn->lock); it =3D interval_tree_iter_first(&mn->objects, range->start, end); while (it) { @@ -275,7 +272,7 @@ i915_gem_userptr_init__mmu_notifier(struct drm_i915_g= em_object *obj, mo->mn =3D mn; mo->obj =3D obj; mo->it.start =3D obj->userptr.ptr; - mo->it.last =3D obj->userptr.ptr + obj->base.size - 1; + mo->it.end =3D obj->userptr.ptr + obj->base.size; RB_CLEAR_NODE(&mo->it.rb); =20 obj->userptr.mmu_object =3D 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 =3D container_of(mn, struct radeon_mn, mn); struct ttm_operation_ctx ctx =3D { false, false }; struct interval_tree_node *it; - unsigned long end; + unsigned long end =3D range->end; int ret =3D 0; =20 - /* notification is exclusive, but interval is inclusive */ - end =3D 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 =3D= { */ int radeon_mn_register(struct radeon_bo *bo, unsigned long addr) { - unsigned long end =3D addr + radeon_bo_size(bo) - 1; + unsigned long end =3D addr + radeon_bo_size(bo); struct mmu_notifier *mn; struct radeon_mn *rmn; struct radeon_mn_node *node =3D NULL; @@ -195,7 +192,7 @@ int radeon_mn_register(struct radeon_bo *bo, unsigned= long addr) node =3D container_of(it, struct radeon_mn_node, it); interval_tree_remove(&node->it, &rmn->objects); addr =3D min(it->start, addr); - end =3D max(it->last, end); + end =3D max(it->end, end); list_splice(&node->bos, &bos); } =20 @@ -210,7 +207,7 @@ int radeon_mn_register(struct radeon_bo *bo, unsigned= long addr) bo->mn =3D rmn; =20 node->it.start =3D addr; - node->it.last =3D end; + node->it.end =3D 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/rade= on/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, =20 TP_fast_assign( __entry->soffset =3D bo_va->it.start; - __entry->eoffset =3D bo_va->it.last + 1; + __entry->eoffset =3D bo_va->it.end; __entry->flags =3D bo_va->flags; ), TP_printk("soffs=3D%010llx, eoffs=3D%010llx, flags=3D%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_d= evice *rdev, bo_va->vm =3D vm; bo_va->bo =3D bo; bo_va->it.start =3D 0; - bo_va->it.last =3D 0; + bo_va->it.end =3D 0; bo_va->flags =3D 0; bo_va->ref_count =3D 1; INIT_LIST_HEAD(&bo_va->bo_list); @@ -456,7 +456,7 @@ int radeon_vm_bo_set_addr(struct radeon_device *rdev, =20 if (soffset) { /* make sure object fit at this offset */ - eoffset =3D soffset + size - 1; + eoffset =3D soffset + size; if (soffset >=3D eoffset) { r =3D -EINVAL; goto error_unreserve; @@ -486,14 +486,14 @@ int radeon_vm_bo_set_addr(struct radeon_device *rde= v, /* 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 =3D -EINVAL; goto error_unreserve; } } =20 - 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 =3D kzalloc(sizeof(struct radeon_bo_va), GFP_KERNEL); @@ -503,14 +503,14 @@ int radeon_vm_bo_set_addr(struct radeon_device *rde= v, goto error_unreserve; } tmp->it.start =3D bo_va->it.start; - tmp->it.last =3D bo_va->it.last; + tmp->it.end =3D bo_va->it.end; tmp->vm =3D vm; tmp->bo =3D radeon_bo_ref(bo_va->bo); =20 interval_tree_remove(&bo_va->it, &vm->va); spin_lock(&vm->status_lock); bo_va->it.start =3D 0; - bo_va->it.last =3D 0; + bo_va->it.end =3D 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 =3D soffset; - bo_va->it.last =3D eoffset; + bo_va->it.end =3D 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, =20 trace_radeon_vm_bo_update(bo_va); =20 - nptes =3D bo_va->it.last - bo_va->it.start + 1; + nptes =3D bo_va->it.end - bo_va->it.start; =20 /* 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, } =20 r =3D 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 =3D 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 =3D 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); =20 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); =20 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 =3D 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_o= dp *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 =3D - ALIGN(umem_odp->interval_tree.last, page_size); - if (unlikely(umem_odp->interval_tree.last < page_size)) + umem_odp->interval_tree.end =3D + ALIGN(umem_odp->interval_tree.end, page_size); + if (unlikely(umem_odp->interval_tree.end < page_size)) return -EOVERFLOW; =20 - pages =3D (umem_odp->interval_tree.last - + pages =3D (umem_odp->interval_tree.end - umem_odp->interval_tree.start) >> umem_odp->page_shift; if (!pages) return -EINVAL; =20 - /* - * 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 =3D 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_ca= ched *root, if (unlikely(start =3D=3D last)) return ret_val; =20 - for (node =3D interval_tree_iter_first(root, start, last - 1); + for (node =3D interval_tree_iter_first(root, start, last); node; node =3D next) { /* TODO move the blockable decision up to the callback */ if (!blockable) return -EAGAIN; - next =3D interval_tree_iter_next(node, start, last - 1); + next =3D interval_tree_iter_next(node, start, last); umem =3D container_of(node, struct ib_umem_odp, interval_tree); ret_val =3D 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 *v= domain, unsigned long iova, =20 mapping->paddr =3D paddr; mapping->iova.start =3D iova; - mapping->iova.last =3D iova + size - 1; + mapping->iova.end =3D iova + size; mapping->flags =3D flags; =20 spin_lock_irqsave(&vdomain->mappings_lock, irqflags); @@ -348,7 +348,7 @@ static size_t viommu_del_mappings(struct viommu_domai= n *vdomain, { size_t unmapped =3D 0; unsigned long flags; - unsigned long last =3D iova + size - 1; + unsigned long last =3D iova + size; struct viommu_mapping *mapping =3D NULL; struct interval_tree_node *node, *next; =20 @@ -367,7 +367,7 @@ static size_t viommu_del_mappings(struct viommu_domai= n *vdomain, * Virtio-iommu doesn't allow UNMAP to split a mapping created * with a single MAP request, so remove the full mapping. */ - unmapped +=3D mapping->iova.last - mapping->iova.start + 1; + unmapped +=3D mapping->iova.end - mapping->iova.start; =20 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; }; =20 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_ume= m_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; } =20 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 a= ddr, u64 length) { struct interval_tree_node *node; =20 - node =3D interval_tree_iter_first(root, addr, addr + length - 1); + node =3D 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 -#include +#include #include #include =20 #define START(node) ((node)->start) -#define LAST(node) ((node)->last) +#define END(node) ((node)->end) =20 INTERVAL_TREE_DEFINE(struct interval_tree_node, rb, unsigned long, __subtree_last, - START, LAST,, interval_tree) + START, END,, interval_tree) =20 EXPORT_SYMBOL_GPL(interval_tree_insert); EXPORT_SYMBOL_GPL(interval_tree_remove); --=20 2.16.4