lib/interval-tree: move to half closed intervals
Subsystems (28)
cover lib/interval-tree: move to half closed intervals
Hi,
It has been discussed[1,2] that almost all users of interval trees would better be served if the intervals were actually not [a,b], but instead [a, b). This series attempts to convert all callers by way of transitioning from using "interval_tree_generic.h" to "interval_tree_gen.h". Once all users are converted, we remove the former.
Patch 1: adds a call that will make patch 8 easier to review by introducing stab
queries for the vma interval tree.
Patch 2: adds the new interval_tree_gen.h which is the same as the old one but
uses [a,b) intervals.
Patch 3-9: converts, in baby steps (as much as possible), each interval tree to
the new [a,b) one. It is done this way also to maintain bisectability. Most conversions are pretty straightforward, however, there are some creative ways in which some callers use the interval 'end' when going through intersecting ranges within a tree. Ie: patch 3, 6 and 9.
Patch 10: deletes the interval_tree_generic.h header; there are no longer any users.
Patch 11: finally simplifies x86 pat tree to use the new interval tree machinery.
This has been lightly tested, and certainly not on driver paths that do non trivial conversions. Also needs more eyeballs as conversions can be easily missed (even when I've tried mitigating this by renaming the endpoint from 'last' to 'end' in each corresponding structure).
Because this touches a lot of drivers, I'm Cc'ing the whole thing to a couple of relevant lists (mm, dri, rdma); sorry if you consider this spam.
Applies on top of today's linux-next tree. Please consider for v5.5.
Thanks!
[1] https://lore.kernel.org/lkml/CANN689HVDJXKEwB80yPAVwvRwnV4HfiucQVAho=dupKM_iKozw@mail.gmail.com/
[2] https://lore.kernel.org/patchwork/patch/1114629/
Davidlohr Bueso (11):
mm: introduce vma_interval_tree_foreach_stab() lib/interval-tree: add an equivalent tree with [a,b) intervals drm/amdgpu: convert amdgpu_vm_it to half closed intervals
drm: convert drm_mm_interval_tree to half closed intervals IB/hfi1: convert __mmu_int_rb to half closed intervals IB,usnic: convert usnic_uiom_interval_tree to half closed intervals
vhost: convert vhost_umem_interval_tree to half closed intervals
mm: convert vma_interval_tree to half closed intervals lib/interval-tree: convert interval_tree to half closed intervals
lib: drop interval_tree_generic.h
x86/mm, pat: convert pat tree to generic interval tree
arch/arm/mm/fault-armv.c | 2 +-
arch/arm/mm/flush.c | 2 +-
arch/nios2/mm/cacheflush.c | 2 +-
arch/parisc/kernel/cache.c | 2 +-
arch/x86/mm/pat.c | 22 +--
arch/x86/mm/pat_rbtree.c | 151 +++++----------------
drivers/gpu/drm/amd/amdgpu/amdgpu_cs.c | 2 +-
drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c | 12 +-
drivers/gpu/drm/amd/amdgpu/amdgpu_object.h | 2 +-
drivers/gpu/drm/amd/amdgpu/amdgpu_trace.h | 18 +--
drivers/gpu/drm/amd/amdgpu/amdgpu_uvd.c | 2 +-
drivers/gpu/drm/amd/amdgpu/amdgpu_vce.c | 3 +-
drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c | 47 ++++---
drivers/gpu/drm/drm_mm.c | 8 +-
drivers/gpu/drm/i915/gem/i915_gem_userptr.c | 5 +-
.../gpu/drm/i915/gem/selftests/i915_gem_context.c | 2 +-
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/gpu/drm/selftests/test-drm_mm.c | 2 +-
drivers/infiniband/core/umem_odp.c | 21 +--
drivers/infiniband/hw/hfi1/mmu_rb.c | 15 +-
drivers/infiniband/hw/usnic/usnic_uiom.c | 8 +-
.../infiniband/hw/usnic/usnic_uiom_interval_tree.c | 26 ++--
.../infiniband/hw/usnic/usnic_uiom_interval_tree.h | 2 +-
drivers/iommu/virtio-iommu.c | 6 +-
drivers/vhost/vhost.c | 19 ++-
drivers/vhost/vhost.h | 4 +-
fs/dax.c | 2 +-
include/drm/drm_mm.h | 6 +-
include/linux/interval_tree.h | 2 +-
...interval_tree_generic.h => interval_tree_gen.h} | 72 +++++-----
include/linux/mm.h | 6 +
include/rdma/ib_umem_odp.h | 4 +-
kernel/events/uprobes.c | 2 +-
lib/interval_tree.c | 6 +-
mm/hugetlb.c | 4 +-
mm/interval_tree.c | 4 +-
mm/khugepaged.c | 2 +-
mm/memory-failure.c | 6 +-
mm/memory.c | 2 +-
mm/nommu.c | 2 +-
mm/rmap.c | 6 +-
43 files changed, 217 insertions(+), 333 deletions(-)
rename include/linux/{interval_tree_generic.h => interval_tree_gen.h} (72%)Signature · 1 line
2.16.4
PATCH 1/11 mm: introduce vma_interval_tree_foreach_stab()
This documents better the nature of the stab lookup/query.
In addition, this is a step that will make the conversion of interval tree nodes from [a,b] to [a,b) easier to review.
For symmetry with vma_interval_tree, the anon equivalent is also introduced, albeit a single user. This patch does not change any semantics.
--- arch/arm/mm/fault-armv.c | 2 +- arch/arm/mm/flush.c | 2 +- arch/nios2/mm/cacheflush.c | 2 +- arch/parisc/kernel/cache.c | 2 +- fs/dax.c | 2 +- include/linux/mm.h | 6 ++++++ kernel/events/uprobes.c | 2 +- mm/hugetlb.c | 4 ++-- mm/khugepaged.c | 2 +- mm/memory-failure.c | 6 ++---- 10 files changed, 17 insertions(+), 13 deletions(-)
arch/arm/mm/fault-armv.c +1 -1
@@ -143,7 +143,7 @@ make_coherent(struct address_space *mapping, struct vm_area_struct *vma,* cache coherency. */ flush_dcache_mmap_lock (mapping); - vma_interval_tree_foreach(mpnt, &mapping->i_mmap, pgoff, pgoff) { + vma_interval_tree_foreach_stab(mpnt, &mapping->i_mmap, pgoff) {/* * If this VMA is not in our MM, we can ignore it. * Note that we intentionally mask out the VMA
arch/arm/mm/flush.c +1 -1
@@ -249,7 +249,7 @@ static void __flush_dcache_aliases(struct address_space *mapping, struct page *p pgoff = page->index;flush_dcache_mmap_lock (mapping); - vma_interval_tree_foreach(mpnt, &mapping->i_mmap, pgoff, pgoff) { + vma_interval_tree_foreach_stab(mpnt, &mapping->i_mmap, pgoff) {unsigned long offset;/*
arch/nios2/mm/cacheflush.c +1 -1
@@ -79,7 +79,7 @@ static void flush_aliases(struct address_space *mapping, struct page *page) pgoff = page->index;flush_dcache_mmap_lock (mapping); - vma_interval_tree_foreach(mpnt, &mapping->i_mmap, pgoff, pgoff) { + vma_interval_tree_foreach_stab(mpnt, &mapping->i_mmap, pgoff) {unsigned long offset;if (mpnt->vm_mm != mm)
arch/parisc/kernel/cache.c +1 -1
@@ -348,7 +348,7 @@ void flush_dcache_page(struct page *page)* to flush one address here for them all to become coherent */ flush_dcache_mmap_lock (mapping); - vma_interval_tree_foreach(mpnt, &mapping->i_mmap, pgoff, pgoff) { + vma_interval_tree_foreach_stab(mpnt, &mapping->i_mmap, pgoff) { offset = (pgoff - mpnt->vm_pgoff) <<PAGE_SHIFT ; addr = mpnt->vm_start + offset;
fs/dax.c +1 -1
@@ -781,7 +781,7 @@ static void dax_entry_mkclean(struct address_space *mapping, pgoff_t index,spinlock_t *ptl;i_mmap_lock_read (mapping); - vma_interval_tree_foreach(vma, &mapping->i_mmap, index, index) { + vma_interval_tree_foreach_stab(vma, &mapping->i_mmap, index) {struct mmu_notifier_range range;unsigned long address;
include/linux/mm.h +6 -0
@@ -2248,6 +2248,9 @@ struct vm_area_struct *vma_interval_tree_iter_next(struct vm_area_struct *node,for (vma =vma_interval_tree_iter_first (root, start, last); \ vma; vma = vma_interval_tree_iter_next(vma, start, last)) +#define vma_interval_tree_foreach_stab (vma, root, start) \ + vma_interval_tree_foreach(vma, root, start, start) +void anon_vma_interval_tree_insert (struct anon_vma_chain *node,struct rb_root_cached *root); void anon_vma_interval_tree_remove(struct anon_vma_chain *node,
@@ -2265,6 +2268,9 @@ void anon_vma_interval_tree_verify(struct anon_vma_chain *node);for (avc =anon_vma_interval_tree_iter_first (root, start, last); \ avc; avc = anon_vma_interval_tree_iter_next(avc, start, last)) +#define anon_vma_interval_tree_foreach_stab (vma, root, start) \ + anon_vma_interval_tree_foreach(vma, root, start, start) +/* mmap.c */ extern int __vm_enough_memory (struct mm_struct *mm,long pages,int cap_sys_admin); extern int __vma_adjust(struct vm_area_struct *vma, unsigned long start,
kernel/events/uprobes.c +1 -1
@@ -975,7 +975,7 @@ build_map_info(struct address_space *mapping, loff_t offset, bool is_register) again:i_mmap_lock_read (mapping); - vma_interval_tree_foreach(vma, &mapping->i_mmap, pgoff, pgoff) { + vma_interval_tree_foreach_stab(vma, &mapping->i_mmap, pgoff) {if (!valid_vma (vma, is_register))continue ;
mm/hugetlb.c +2 -2
@@ -3643,7 +3643,7 @@ static void unmap_ref_private(struct mm_struct *mm, struct vm_area_struct *vma,* __unmap_hugepage_range() is called as the lock is already held */ i_mmap_lock_write (mapping); - vma_interval_tree_foreach(iter_vma, &mapping->i_mmap, pgoff, pgoff) { + vma_interval_tree_foreach_stab(iter_vma, &mapping->i_mmap, pgoff) {/* Do not unmap the current VMA */ if (iter_vma == vma)continue ;
@@ -4844,7 +4844,7 @@ pte_t *huge_pmd_share(struct mm_struct *mm, unsigned long addr, pud_t *pud)return (pte_t *)pmd_alloc (mm, pud, addr);i_mmap_lock_write (mapping); - vma_interval_tree_foreach(svma, &mapping->i_mmap, idx, idx) { + vma_interval_tree_foreach_stab(svma, &mapping->i_mmap, idx) {if (svma == vma)continue ;
mm/khugepaged.c +1 -1
@@ -1420,7 +1420,7 @@ static void retract_page_tables(struct address_space *mapping, pgoff_t pgoff)pmd_t *pmd, _pmd;i_mmap_lock_write (mapping); - vma_interval_tree_foreach(vma, &mapping->i_mmap, pgoff, pgoff) { + vma_interval_tree_foreach_stab(vma, &mapping->i_mmap, pgoff) {/* * Check vma->anon_vma to exclude MAP_PRIVATE mappings that * got written to. These VMAs are likely not worth investing
mm/memory-failure.c +2 -4
@@ -451,8 +451,7 @@ static void collect_procs_anon(struct page *page, struct list_head *to_kill,if (!t)continue ; -anon_vma_interval_tree_foreach (vmac, &av->rb_root, - pgoff, pgoff) { + anon_vma_interval_tree_foreach_stab(vmac, &av->rb_root, pgoff) { vma = vmac->vma;if (!page_mapped_in_vma (page, vma))continue ;
@@ -482,8 +481,7 @@ static void collect_procs_file(struct page *page, struct list_head *to_kill,if (!t)continue ; -vma_interval_tree_foreach (vma, &mapping->i_mmap, pgoff, - pgoff) { + vma_interval_tree_foreach_stab(vma, &mapping->i_mmap, pgoff) {/* * Send early kill signal to tasks where a vma covers * the page but the corrupted page is not necessarily
Signature · 1 line
2.16.4
PATCH 2/11 lib/interval-tree: add an equivalent tree with [a,b) intervals
In reply to Davidlohr BuesoWhile the kernel's interval tree implementation uses closed intervals, all users (with the exception of query stabbing) really want half closed intervals, specifically [a, b), and will explicitly correct this before calling the tree api.
This patch simply duplicates the include/linuxinterval_tree_generic.h header into a interval_tree_gen.h (gen as in 'generic' and 'generate' :-) with two differences:
- The 'last' endpoint is renamed 'end'; this is something lib/interval_tree.c will also need to update, but that is later in the series.
- The lookup calls have been adapted accordingly, such that users need not need to do the subtraction by one fixup.
No users are ported over in this patch.
--- include/linux/interval_tree_gen.h | 179 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 179 insertions(+) create mode 100644 include/linux/interval_tree_gen.h
include/linux/interval_tree_gen.h new file +179 -0
@@ -0,0 +1,179 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* +Interval Trees +(C) 2012 Michel Lespinasse <[email protected]> +*/ + +#include <linux/rbtree_augmented.h> + +/* +* Template for implementing interval trees +* +* ITSTRUCT: struct type of the interval tree nodes +* ITRB: name of struct rb_node field within ITSTRUCT +* ITTYPE: type of the interval endpoints +* ITSUBTREE: name of ITTYPE field within ITSTRUCT holding end-in-subtree +* ITSTART(n): start endpoint of ITSTRUCT node n +* ITEND(n): end/last endpoint of ITSTRUCT node n +* ITSTATIC: 'static' or empty +* ITPREFIX: prefix to use for the inline tree definitions +* +* Note - before using this, please consider if generic version +* (interval_tree.h) would work for you... +*/ + +#define INTERVAL_TREE_DEFINE (ITSTRUCT ,ITRB ,ITTYPE ,ITSUBTREE , \ +ITSTART ,ITEND ,ITSTATIC ,ITPREFIX ) \ + \ +/* Callbacks for augmented rbtree insert and remove */ \ + \ +RB_DECLARE_CALLBACKS_MAX(static, ITPREFIX ## _augment, \ + ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, ITEND) \ + \ +/* Insert / remove interval nodes from the tree */ \ + \ +ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, \ +struct rb_root_cached *root) \ +{ \ +struct rb_node **link = &root->rb_root.rb_node, *rb_parent =NULL ; \ +ITTYPE start =ITSTART (node), end =ITEND (node); \ +ITSTRUCT *parent; \ +bool leftmost = true; \ + \ +while (*link) { \ + rb_parent = *link; \ + parent =rb_entry (rb_parent,ITSTRUCT ,ITRB ); \ +if (parent->ITSUBTREE < end) \ + parent->ITSUBTREE = end; \ +if (start <ITSTART (parent)) \ + link = &parent->ITRB.rb_left; \ +else { \ + link = &parent->ITRB.rb_right; \ + leftmost = false; \ + } \ + } \ + \ + node->ITSUBTREE = end; \ +rb_link_node (&node->ITRB, rb_parent, link); \ +rb_insert_augmented_cached (&node->ITRB, root, \ + leftmost, &ITPREFIX ## _augment); \ +} \ + \ +ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, \ +struct rb_root_cached *root) \ +{ \ + rb_erase_augmented_cached(&node->ITRB, root, &ITPREFIX ## _augment); \ +} \ + \ +/* \ +* Iterate over intervals intersecting [start;end) \ +* \ +* Note that a node's interval intersects [start;end) iff: \ +* Cond1: ITSTART(node) < end \ +* and \ +* Cond2: start < ITEND(node) \ +*/ \ + \ +static ITSTRUCT * \ +ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE end) \ +{ \ +while (true) { \ +/* \ +* Loop invariant: start <= node->ITSUBTREE \ +* (Cond2 is satisfied by one of the subtree nodes) \ +*/ \ +if (node->ITRB.rb_left) { \ +ITSTRUCT *left =rb_entry (node->ITRB.rb_left, \ +ITSTRUCT ,ITRB ); \ +if (start < left->ITSUBTREE) { \ +/* \ +* Some nodes in left subtree satisfy Cond2. \ +* Iterate to find the leftmost such node N. \ +* If it also satisfies Cond1, that's the \ +* match we are looking for. Otherwise, there \ +* is no matching interval as nodes to the \ +* right of N can't satisfy Cond1 either. \ +*/ \ + node = left; \ +continue ; \ + } \ + } \ +if (ITSTART (node) < end) {/* Cond1 */ \ +if (start <ITEND (node))/* Cond2 */ \ +return node;/* node is leftmost match */ \ +if (node->ITRB.rb_right) { \ + node =rb_entry (node->ITRB.rb_right, \ +ITSTRUCT ,ITRB ); \ +if (start <= node->ITSUBTREE) \ +continue ; \ + } \ + } \ +return NULL ;/* No match */ \ + } \ +} \ + \ +ITSTATIC ITSTRUCT * \ +ITPREFIX ## _iter_first(struct rb_root_cached *root, \ +ITTYPE start,ITTYPE end) \ +{ \ +ITSTRUCT *node, *leftmost; \ + \ +if (!root->rb_root.rb_node) \ +return NULL ; \ + \ +/* \ +* Fastpath range intersection/overlap where we compare the \ +* smallest 'start' and largest 'end' in the tree. For the latter, \ +* we rely on the root node, which by augmented interval tree \ +* property, holds the largest value in its end-in-subtree. \ +* This allows mitigating some of the tree walk overhead for \ +* for non-intersecting ranges, maintained and consulted in O(1). \ +*/ \ + node =rb_entry (root->rb_root.rb_node,ITSTRUCT ,ITRB ); \ +if (node->ITSUBTREE <= start)/* !Cond2 */ \ +return NULL ; \ + \ + leftmost =rb_entry (root->rb_leftmost,ITSTRUCT ,ITRB ); \ +if (ITSTART (leftmost) >= end)/* !Cond1 */ \ +return NULL ; \ + \ + return ITPREFIX ## _subtree_search(node, start, end); \ +} \ + \ +ITSTATIC ITSTRUCT * \ +ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE end) \ +{ \ +struct rb_node *rb = node->ITRB.rb_right, *prev; \ + \ +while (true) { \ +/* \ +* Loop invariants: \ +* Cond1: ITSTART(node) < end \ +* rb == node->ITRB.rb_right \ +* \ +* First, search right subtree if suitable \ +*/ \ +if (rb) { \ +ITSTRUCT *right =rb_entry (rb,ITSTRUCT ,ITRB ); \ +if (start < right->ITSUBTREE) \ + return ITPREFIX ## _subtree_search(right, \ + start, end); \ + } \ + \ +/* Move up the tree until we come from a node's left child */ \ +do { \ + rb =rb_parent (&node->ITRB); \ +if (!rb) \ +return NULL ; \ + prev = &node->ITRB; \ + node =rb_entry (rb,ITSTRUCT ,ITRB ); \ + rb = node->ITRB.rb_right; \ + }while (prev == rb); \ + \ +/* Check if the node intersects [start;end) */ \ +if (end <=ITSTART (node))/* !Cond1 */ \ +return NULL ; \ +else if (start <ITEND (node))/* Cond2 */ \ +return node; \ + } \ +}
Signature · 1 line
2.16.4
Re: [PATCH 02/11] lib/interval-tree: add an equivalent tree with [a,b) intervals
Quoted 5 lines · Davidlohr Bueso
include/linux/interval_tree_gen.h new file +5
-0+/* \ +* Iterate over intervals intersecting [start;end) \ +* \ +* Note that a node's interval intersects [start;end) iff: \ +* Cond1: ITSTART(node) < end \
include/linux/interval_tree_gen.h line 82
Quoted 10 lines
include/linux/interval_tree_gen.h new file +10
-0+* and \ +* Cond2: start < ITEND(node) \ +*/ \ + \ +static ITSTRUCT * \ +ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE end) \ +{ \ +while (true) { \ +/* \ +* Loop invariant: start <= node->ITSUBTREE \
Should be start < node->ITSUBTREE
Quoted 15 lines
include/linux/interval_tree_gen.h new file +15
-0+* (Cond2 is satisfied by one of the subtree nodes) \ +*/ \ +if (node->ITRB.rb_left) { \ +ITSTRUCT *left =rb_entry (node->ITRB.rb_left, \ +ITSTRUCT ,ITRB ); \ +if (start < left->ITSUBTREE) { \ +/* \ +* Some nodes in left subtree satisfy Cond2. \ +* Iterate to find the leftmost such node N. \ +* If it also satisfies Cond1, that's the \ +* match we are looking for. Otherwise, there \ +* is no matching interval as nodes to the \ +* right of N can't satisfy Cond1 either. \ +*/ \ + node = left; \
include/linux/interval_tree_gen.h line 107
Quoted 10 lines
include/linux/interval_tree_gen.h new file +10
-0+continue ; \ + } \ + } \ +if (ITSTART (node) < end) {/* Cond1 */ \ +if (start <ITEND (node))/* Cond2 */ \ +return node;/* node is leftmost match */ \ +if (node->ITRB.rb_right) { \ + node =rb_entry (node->ITRB.rb_right, \ +ITSTRUCT ,ITRB ); \ +if (start <= node->ITSUBTREE) \
Should be start < node->ITSUBTREE
include/linux/interval_tree_gen.h line 113
Quoted 6 lines
include/linux/interval_tree_gen.h new file +6
-0+continue ; \ + } \ + } \ +return NULL ;/* No match */ \ + } \ +} \
Other than that, the change looks good to me.
This is something I might use, regardless of the status of converting other current users.
The name "interval_tree_gen.h" makes it ambiguous wether gen stands for "generic" or "generator". This may sounds like a criticism, but it's not - I think it really stands for both :)
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
PATCH 3/11 drm/amdgpu: convert amdgpu_vm_it to half closed intervals
In reply to Davidlohr BuesoThe amdgpu_vm interval tree really wants [a, b) intervals, not fully closed ones. As such convert it to use the new interval_tree_gen.h, and also rename the 'last' endpoint in the node to 'end', which is both a more suitable name for the half closed interval and also reduces the chances of missing a conversion when doing insertion or lookup.
--- drivers/gpu/drm/amd/amdgpu/amdgpu_cs.c | 2 +- drivers/gpu/drm/amd/amdgpu/amdgpu_object.h | 2 +- drivers/gpu/drm/amd/amdgpu/amdgpu_trace.h | 18 ++++++------ drivers/gpu/drm/amd/amdgpu/amdgpu_uvd.c | 2 +- drivers/gpu/drm/amd/amdgpu/amdgpu_vce.c | 3 +- drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c | 46 +++++++++++++++--------------- 6 files changed, 36 insertions(+), 37 deletions(-)
drivers/gpu/drm/amd/amdgpu/amdgpu_cs.c +1 -1
@@ -756,7 +756,7 @@ static int amdgpu_cs_vm_handling(struct amdgpu_cs_parser *p) }if ((va_start + chunk_ib->ib_bytes) > - (m->last +1 ) *AMDGPU_GPU_PAGE_SIZE ) { + m->end *AMDGPU_GPU_PAGE_SIZE ) {DRM_ERROR ("IB va_start+ib_bytes is invalid\n" );return -EINVAL ; }
drivers/gpu/drm/amd/amdgpu/amdgpu_object.h +1 -1
@@ -51,7 +51,7 @@ struct amdgpu_bo_va_mapping {struct list_head list;struct rb_node rb;uint64_t start; -uint64_t last; +uint64_t end;uint64_t __subtree_last;uint64_t offset;uint64_t flags;
drivers/gpu/drm/amd/amdgpu/amdgpu_trace.h +9 -9
@@ -247,7 +247,7 @@ TRACE_EVENT(amdgpu_vm_bo_map,TP_STRUCT__entry (__field (struct amdgpu_bo *,bo )__field (long, start) -__field (long, last) +__field (long, end)__field (u64, offset)__field (u64, flags) ),
@@ -255,12 +255,12 @@ TRACE_EVENT(amdgpu_vm_bo_map,TP_fast_assign ( __entry->bo = bo_va ? bo_va->base.bo : NULL; __entry->start = mapping->start; - __entry->last = mapping->last; + __entry->end = mapping->end; __entry->offset = mapping->offset; __entry->flags = mapping->flags; ), -TP_printk ("bo=%p, start=%lx, last=%lx, offset=%010llx, flags=%llx" , - __entry->bo, __entry->start, __entry->last, +TP_printk ("bo=%p, start=%lx, end=%lx, offset=%010llx, flags=%llx" , + __entry->bo, __entry->start, __entry->end, __entry->offset, __entry->flags) );
@@ -271,7 +271,7 @@ TRACE_EVENT(amdgpu_vm_bo_unmap,TP_STRUCT__entry (__field (struct amdgpu_bo *,bo )__field (long, start) -__field (long, last) +__field (long, end)__field (u64, offset)__field (u64, flags) ),
@@ -279,12 +279,12 @@ TRACE_EVENT(amdgpu_vm_bo_unmap,TP_fast_assign ( __entry->bo = bo_va ? bo_va->base.bo : NULL; __entry->start = mapping->start; - __entry->last = mapping->last; + __entry->end = mapping->end; __entry->offset = mapping->offset; __entry->flags = mapping->flags; ), -TP_printk ("bo=%p, start=%lx, last=%lx, offset=%010llx, flags=%llx" , - __entry->bo, __entry->start, __entry->last, +TP_printk ("bo=%p, start=%lx, end=%lx, offset=%010llx, flags=%llx" , + __entry->bo, __entry->start, __entry->end, __entry->offset, __entry->flags) );
@@ -299,7 +299,7 @@ DECLARE_EVENT_CLASS(amdgpu_vm_mapping,TP_fast_assign ( __entry->soffset = mapping->start; - __entry->eoffset = mapping->last +1 ; + __entry->eoffset = mapping->end; __entry->flags = mapping->flags; ), TP_printk("soffs=%010llx, eoffs=%010llx, flags=%llx",
drivers/gpu/drm/amd/amdgpu/amdgpu_uvd.c +1 -1
@@ -819,7 +819,7 @@ static int amdgpu_uvd_cs_pass2(struct amdgpu_uvd_cs_ctx *ctx) start =amdgpu_bo_gpu_offset (bo); - end = (mapping->last +1 - mapping->start); + end = mapping->end - mapping->start; end = end *AMDGPU_GPU_PAGE_SIZE + start; addr -= mapping->start *AMDGPU_GPU_PAGE_SIZE ;
drivers/gpu/drm/amd/amdgpu/amdgpu_vce.c +1 -2
@@ -642,8 +642,7 @@ static int amdgpu_vce_cs_reloc(struct amdgpu_cs_parser *p, uint32_t ib_idx,return r; } -if ((addr + (uint64_t )size) > - (mapping->last +1 ) *AMDGPU_GPU_PAGE_SIZE ) { +if ((addr + (uint64_t )size) > mapping->end *AMDGPU_GPU_PAGE_SIZE ) {DRM_ERROR ("BO to small for addr 0x%010Lx %d %d\n" , addr, lo, hi);return -EINVAL ;
drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c +23 -23
144 lines not on this page · raw message
Signature · 1 line
2.16.4
Re: [PATCH 03/11] drm/amdgpu: convert amdgpu_vm_it to half closed intervals
Am 03.10.19 um 22:18 schrieb Davidlohr Bueso:
Quoted 1 line
The
amdgpu_vminterval tree really wants [a, b) intervals,
NAK, we explicitly do need an [a, b[ interval here.
Regards,
Christian.
Quoted 289 lines
not fully closed ones. As such convert it to use the new
interval_tree_gen.h, and also rename the 'last' endpoint in the node to 'end', which is both a more suitable name for the half closed interval and also reduces the chances of missing a conversion when doing insertion or lookup.Cc Jerome Glisse <[email protected]>Cc Alex Deucher <[email protected]>Cc "Christian König" <[email protected]>Cc Daniel Vetter <[email protected]>Signed-off-by Davidlohr Bueso <[email protected]>--- drivers/gpu/drm/amd/amdgpu/amdgpu_cs.c | 2 +- drivers/gpu/drm/amd/amdgpu/amdgpu_object.h | 2 +- drivers/gpu/drm/amd/amdgpu/amdgpu_trace.h | 18 ++++++------ drivers/gpu/drm/amd/amdgpu/amdgpu_uvd.c | 2 +- drivers/gpu/drm/amd/amdgpu/amdgpu_vce.c | 3 +- drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c | 46 +++++++++++++++--------------- 6 files changed, 36 insertions(+), 37 deletions(-)drivers/gpu/drm/amd/amdgpu/amdgpu_cs.c +1
-1@@ -756,7 +756,7 @@ static int amdgpu_cs_vm_handling(struct amdgpu_cs_parser *p) }if ((va_start + chunk_ib->ib_bytes) > - (m->last +1 ) *AMDGPU_GPU_PAGE_SIZE ) { + m->end *AMDGPU_GPU_PAGE_SIZE ) {DRM_ERROR ("IB va_start+ib_bytes is invalid\n" );return -EINVAL ; }drivers/gpu/drm/amd/amdgpu/amdgpu_object.h +1
-1@@ -51,7 +51,7 @@ struct amdgpu_bo_va_mapping {struct list_head list;struct rb_node rb;uint64_t start; -uint64_t last; +uint64_t end;uint64_t __subtree_last;uint64_t offset;uint64_t flags;drivers/gpu/drm/amd/amdgpu/amdgpu_trace.h +9
-9@@ -247,7 +247,7 @@ TRACE_EVENT(amdgpu_vm_bo_map,TP_STRUCT__entry (__field (struct amdgpu_bo *,bo )__field (long, start) -__field (long, last) +__field (long, end)__field (u64, offset)__field (u64, flags) ),@@ -255,12 +255,12 @@ TRACE_EVENT(amdgpu_vm_bo_map,TP_fast_assign ( __entry->bo = bo_va ? bo_va->base.bo : NULL; __entry->start = mapping->start; - __entry->last = mapping->last; + __entry->end = mapping->end; __entry->offset = mapping->offset; __entry->flags = mapping->flags; ), -TP_printk ("bo=%p, start=%lx, last=%lx, offset=%010llx, flags=%llx" , - __entry->bo, __entry->start, __entry->last, +TP_printk ("bo=%p, start=%lx, end=%lx, offset=%010llx, flags=%llx" , + __entry->bo, __entry->start, __entry->end, __entry->offset, __entry->flags) );@@ -271,7 +271,7 @@ TRACE_EVENT(amdgpu_vm_bo_unmap,TP_STRUCT__entry (__field (struct amdgpu_bo *,bo )__field (long, start) -__field (long, last) +__field (long, end)__field (u64, offset)__field (u64, flags) ),@@ -279,12 +279,12 @@ TRACE_EVENT(amdgpu_vm_bo_unmap,TP_fast_assign ( __entry->bo = bo_va ? bo_va->base.bo : NULL; __entry->start = mapping->start; - __entry->last = mapping->last; + __entry->end = mapping->end; __entry->offset = mapping->offset; __entry->flags = mapping->flags; ), -TP_printk ("bo=%p, start=%lx, last=%lx, offset=%010llx, flags=%llx" , - __entry->bo, __entry->start, __entry->last, +TP_printk ("bo=%p, start=%lx, end=%lx, offset=%010llx, flags=%llx" , + __entry->bo, __entry->start, __entry->end, __entry->offset, __entry->flags) );@@ -299,7 +299,7 @@ DECLARE_EVENT_CLASS(amdgpu_vm_mapping,TP_fast_assign ( __entry->soffset = mapping->start; - __entry->eoffset = mapping->last +1 ; + __entry->eoffset = mapping->end; __entry->flags = mapping->flags; ), TP_printk("soffs=%010llx, eoffs=%010llx, flags=%llx",drivers/gpu/drm/amd/amdgpu/amdgpu_uvd.c +1
-1@@ -819,7 +819,7 @@ static int amdgpu_uvd_cs_pass2(struct amdgpu_uvd_cs_ctx *ctx) start =amdgpu_bo_gpu_offset (bo); - end = (mapping->last +1 - mapping->start); + end = mapping->end - mapping->start; end = end *AMDGPU_GPU_PAGE_SIZE + start; addr -= mapping->start *AMDGPU_GPU_PAGE_SIZE ;drivers/gpu/drm/amd/amdgpu/amdgpu_vce.c +1
-2@@ -642,8 +642,7 @@ static int amdgpu_vce_cs_reloc(struct amdgpu_cs_parser *p, uint32_t ib_idx,return r; } -if ((addr + (uint64_t )size) > - (mapping->last +1 ) *AMDGPU_GPU_PAGE_SIZE ) { +if ((addr + (uint64_t )size) > mapping->end *AMDGPU_GPU_PAGE_SIZE ) {DRM_ERROR ("BO to small for addr 0x%010Lx %d %d\n" , addr, lo, hi);return -EINVAL ;drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c +21
-21@@ -26,7 +26,7 @@* Jerome Glisse */ #include <linux/dma-fence-array.h> -#include <linux/interval_tree_generic.h> +#include <linux/interval_tree_gen.h> #include <linux/idr.h> #include <drm/amdgpu_drm.h> @@ -58,13 +58,13 @@*/ #define START (node) ((node)->start) -#define LAST (node) ((node)->last) +#define END (node) ((node)->end) INTERVAL_TREE_DEFINE(struct amdgpu_bo_va_mapping, rb, uint64_t, __subtree_last, - START, LAST, static, amdgpu_vm_it) + START, END, static, amdgpu_vm_it)#undef START -#undef LAST +#undef END/** * struct amdgpu_prt_cb - Helper to disable partial resident texture feature from a fence callback @@ -1616,7 +1616,7 @@ static int amdgpu_vm_bo_split_mapping(struct amdgpu_device *adev, do { dma_addr_t *dma_addr = NULL; uint64_t max_entries; - uint64_t addr, last; + uint64_t addr, end; if (nodes) { addr = nodes->start << PAGE_SHIFT;@@ -1654,21 +1654,21 @@ static int amdgpu_vm_bo_split_mapping(struct amdgpu_device *adev, addr += pfn <<PAGE_SHIFT ; } - last =min ((uint64_t )mapping->last, start + max_entries -1 ); + end =min ((uint64_t )mapping->end, start + max_entries); r =amdgpu_vm_bo_update_mapping (adev, vm, false, exclusive, - start, last, flags, addr, + start, end, flags, addr, dma_addr, fence);if (r)return r; - pfn += (last - start +1 ) /AMDGPU_GPU_PAGES_IN_CPU_PAGE ; + pfn += (end - start) /AMDGPU_GPU_PAGES_IN_CPU_PAGE ;if (nodes && nodes->size == pfn) { pfn =0 ; ++nodes; } - start = last +1 ; + start = end; - }while (unlikely (start != mapping->last +1 )); + }while (unlikely (start != mapping->end));return 0 ; }@@ -1946,7 +1946,7 @@ int amdgpu_vm_clear_freed(struct amdgpu_device *adev, init_pte_value =AMDGPU_PTE_DEFAULT_ATC ; r =amdgpu_vm_bo_update_mapping (adev, vm, false,NULL , - mapping->start, mapping->last, + mapping->start, mapping->end, init_pte_value,0 ,NULL , &f);amdgpu_vm_free_mapping (adev, vm, mapping, f);if (r) {@@ -2129,7 +2129,7 @@ int amdgpu_vm_bo_map(struct amdgpu_device *adev,return -EINVAL ;/* make sure object fit at this offset */ - eaddr = saddr + size -1 ; + eaddr = saddr + size;if (saddr >= eaddr || (bo && offset + size >amdgpu_bo_size (bo)))return -EINVAL ;@@ -2142,7 +2142,7 @@ int amdgpu_vm_bo_map(struct amdgpu_device *adev,/* bo and tmp overlap, invalid addr */ dev_err (adev->dev,"bo %p va 0x%010Lx-0x%010Lx conflict with " "0x%010Lx-0x%010Lx\n" , bo, saddr, eaddr, - tmp->start, tmp->last +1 ); + tmp->start, tmp->end);return -EINVAL ; }@@ -2151,7 +2151,7 @@ int amdgpu_vm_bo_map(struct amdgpu_device *adev,return -ENOMEM ; mapping->start = saddr; - mapping->last = eaddr; + mapping->end = eaddr; mapping->offset = offset; mapping->flags = flags;@@ -2194,7 +2194,7 @@ int amdgpu_vm_bo_replace_map(struct amdgpu_device *adev,return -EINVAL ;/* make sure object fit at this offset */ - eaddr = saddr + size -1 ; + eaddr = saddr + size;if (saddr >= eaddr || (bo && offset + size >amdgpu_bo_size (bo)))return -EINVAL ;@@ -2214,7 +2214,7 @@ int amdgpu_vm_bo_replace_map(struct amdgpu_device *adev, eaddr /=AMDGPU_GPU_PAGE_SIZE ; mapping->start = saddr; - mapping->last = eaddr; + mapping->end = eaddr; mapping->offset = offset; mapping->flags = flags;@@ -2299,7 +2299,7 @@ int amdgpu_vm_bo_clear_mappings(struct amdgpu_device *adev,LIST_HEAD (removed);uint64_t eaddr; - eaddr = saddr + size -1 ; + eaddr = saddr + size; saddr /=AMDGPU_GPU_PAGE_SIZE ; eaddr /=AMDGPU_GPU_PAGE_SIZE ;@@ -2322,7 +2322,7 @@ int amdgpu_vm_bo_clear_mappings(struct amdgpu_device *adev,/* Remember mapping split at the start */ if (tmp->start < saddr) { before->start = tmp->start; - before->last = saddr -1 ; + before->end = saddr; before->offset = tmp->offset; before->flags = tmp->flags; before->bo_va = tmp->bo_va;@@ -2330,9 +2330,9 @@ int amdgpu_vm_bo_clear_mappings(struct amdgpu_device *adev, }/* Remember mapping split at the end */ -if (tmp->last > eaddr) { - after->start = eaddr +1 ; - after->last = tmp->last; +if (tmp->end > eaddr) { + after->start = eaddr; + after->end = tmp->end; after->offset = tmp->offset; after->offset += after->start - tmp->start; after->flags = tmp->flags;
drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c int amdgpu_vm_bo_clear_mappings(struct amdgpu_device *adev, · line 2360
Quoted 10 lines
drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c +2
-2@@ -2353,8 +2353,8 @@ int amdgpu_vm_bo_clear_mappings(struct amdgpu_device *adev,if (tmp->start < saddr) tmp->start = saddr; -if (tmp->last > eaddr) - tmp->last = eaddr; +if (tmp->end > eaddr) + tmp->end = eaddr; tmp->bo_va =NULL ;list_add (&tmp->list, &vm->freed);
_______________________________________________
amd-gfx mailing list
[email protected]
https://lists.freedesktop.org/mailman/listinfo/amd-gfx
Re: [PATCH 03/11] drm/amdgpu: convert amdgpu_vm_it to half closed intervals
Quoted 4 lines · Christian
Am 03.10.19 um 22:18 schrieb Davidlohr Bueso:
Quoted 1 line
The
amdgpu_vminterval tree really wants [a, b) intervals,NAK, we explicitly do need an [a, b[ interval here.
Hi Christian,
Just wanted to confirm where you stand on this patch, since I think you reconsidered your initial position after first looking at 9/11 from this series.
I do not know the amdgpu code well, but I think the changes should be fine - in struct amdgpu_bo_va_mapping, the "end" field will hold what was previously stored in the "last" field, plus one. The expectation is that overflows should not be an issue there, as "end" is explicitly declared as an uint64, and as the code was previously computing "last + 1" in many places.
Does that seem workable to you ?
Thanks,
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
Re: [PATCH 03/11] drm/amdgpu: convert amdgpu_vm_it to half closed intervals
Hi Michel,
Am 04.10.19 um 13:36 schrieb Michel Lespinasse:
Quoted 10 lines · Christian
Quoted 3 lines
Am 03.10.19 um 22:18 schrieb Davidlohr Bueso:
Quoted 1 line
The
amdgpu_vminterval tree really wants [a, b) intervals,NAK, we explicitly do need an [a, b[ interval here.
Hi Christian,
Just wanted to confirm where you stand on this patch, since I think you reconsidered your initial position after first looking at 9/11 from this series.
Quoted 8 lines
I do not know the amdgpu code well, but I think the changes should be fine - in struct
amdgpu_bo_va_mapping, the "end" field will hold what was previously stored in the "last" field, plus one. The expectation is that overflows should not be an issue there, as "end" is explicitly declared as an uint64, and as the code was previously computing "last + 1" in many places.Does that seem workable to you ?
No, we computed last + 1 in a couple of debug places were it doesn't hurt us and IIRC we currently cheat a bit because we use pfn instead of addresses on some other places.
But that is only a leftover from radeon and we need to fix that sooner or later, cause essentially the physical address space of the device is really full 64bits, e.g. 0x0-0xffffffffffffffff.
So that only fits into a 64bit int when we use half open/closed intervals, but would wrap around to zero if we use a closed interval.
I initially thought that the set was changing the interval tree into always using a closed interval, but that seems to have been a misunderstanding.
Regards,
Christian.
Quoted 3 lines
Thanks,
PATCH 4/11 drm: convert drm_mm_interval_tree to half closed intervals
In reply to Davidlohr BuesoThe drm_mm interval tree really wants [a, b) intervals, not fully closed as it is now. As such convert it to use the new interval_tree_gen.h.
--- drivers/gpu/drm/drm_mm.c | 8 ++++---- drivers/gpu/drm/i915/gem/selftests/i915_gem_context.c | 2 +- drivers/gpu/drm/selftests/test-drm_mm.c | 2 +- include/drm/drm_mm.h | 6 +++--- 4 files changed, 9 insertions(+), 9 deletions(-)
drivers/gpu/drm/drm_mm.c +4 -4
@@ -43,7 +43,7 @@*/ #include <linux/export.h> -#include <linux/interval_tree_generic.h> +#include <linux/interval_tree_gen.h> #include <linux/seq_file.h> #include <linux/slab.h> #include <linux/stacktrace.h>
@@ -150,11 +150,11 @@ static void show_leaks(struct drm_mm *mm) { }#endif #define START (node) ((node)->start) -#define LAST (node) ((node)->start + (node)->size - 1) +#define END (node) ((node)->start + (node)->size) INTERVAL_TREE_DEFINE(struct drm_mm_node, rb, u64, __subtree_last, - START, LAST, static inline, drm_mm_interval_tree) + START, END, static inline, drm_mm_interval_tree)struct drm_mm_node *__drm_mm_interval_first (const struct drm_mm *mm,u64 start,u64 last)
@@ -172,7 +172,7 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node,struct drm_mm_node *parent;bool leftmost; - node->__subtree_last =LAST (node); + node->__subtree_last =END (node);if (hole_node->allocated) { rb = &hole_node->rb;
drivers/gpu/drm/i915/gem/selftests/i915_gem_context.c +1 -1
@@ -1150,7 +1150,7 @@ static int check_scratch(struct i915_gem_context *ctx, u64 offset) {struct drm_mm_node *node =__drm_mm_interval_first (&ctx->vm->mm, - offset, offset +sizeof (u32) -1 ); + offset, offset +sizeof (u32));if (!node || node->start > offset)return 0 ;
drivers/gpu/drm/selftests/test-drm_mm.c +1 -1
@@ -853,7 +853,7 @@ static bool assert_contiguous_in_range(struct drm_mm *mm, }if (start >0 ) { - node =__drm_mm_interval_first (mm,0 , start -1 ); + node =__drm_mm_interval_first (mm,0 , start);if (node->allocated) {pr_err ("node before start: node=%llx+%llu, start=%llx\n" , node->start, node->size, start);
include/drm/drm_mm.h +3 -3
@@ -485,19 +485,19 @@ __drm_mm_interval_first(const struct drm_mm *mm, u64 start, u64 last);* @node__: drm_mm_node structure to assign to in each iteration step * @mm__: drm_mm allocator to walk * @start__: starting offset, the first node will overlap this -* @end__: ending offset, the last node will start before this (but may overlap) +* @end__: ending offset, the last node will start before this * * This iterator walks over all nodes in the range allocator that lie * between @start and @end. It is implemented similarly to list_for_each(), * but using the internal interval tree to accelerate the search for the * starting node, and so not safe against removal of elements. It assumes * that @end is within (or is the upper limit of) the drm_mm allocator. -* If [@start, @end] are beyond the range of the drm_mm, the iterator may walk +* If [@start, @end) are beyond the range of the drm_mm, the iterator may walk * over the special _unallocated_ &drm_mm.head_node, and may even continue * indefinitely. */ #define drm_mm_for_each_node_in_range (node__, mm__, start__, end__) \ - for (node__ = __drm_mm_interval_first((mm__), (start__), (end__)-1); \ + for (node__ = __drm_mm_interval_first((mm__), (start__), (end__)); \ node__->start < (end__); \ node__ = list_next_entry(node__, node_list))
Signature · 6 lines
2.16.4 _______________________________________________ Intel-gfx mailing list [email protected] https://lists.freedesktop.org/mailman/listinfo/intel-gfx
PATCH 5/11 IB/hfi1: convert __mmu_int_rb to half closed intervals
In reply to Davidlohr BuesoThe __mmu_int_rb interval tree really wants [a, b) intervals, not fully closed as currently. As such convert it to use the new interval_tree_gen.h.
--- drivers/infiniband/hw/hfi1/mmu_rb.c | 15 +++++++-------- 1 file changed, 7 insertions(+), 8 deletions(-)
drivers/infiniband/hw/hfi1/mmu_rb.c +7 -8
@@ -47,7 +47,7 @@#include <linux/list.h> #include <linux/rculist.h> #include <linux/mmu_notifier.h> -#include <linux/interval_tree_generic.h> +#include <linux/interval_tree_gen.h> #include "mmu_rb.h" #include "trace.h"
@@ -89,7 +89,7 @@ static unsigned long mmu_node_start(struct mmu_rb_node *node)static unsigned long mmu_node_last (struct mmu_rb_node *node) { -return PAGE_ALIGN (node->addr + node->len) -1 ; +return PAGE_ALIGN (node->addr + node->len); } int hfi1_mmu_rb_register(void *ops_arg, struct mm_struct *mm,
@@ -195,13 +195,13 @@ static struct mmu_rb_node *__mmu_rb_search(struct mmu_rb_handler *handler,trace_hfi1_mmu_rb_search (addr, len);if (!handler->ops->filter) { node =__mmu_int_rb_iter_first (&handler->root, addr, - (addr + len) -1 ); + addr + len); }else {for (node =__mmu_int_rb_iter_first (&handler->root, addr, - (addr + len) -1 ); + addr + len); node; node =__mmu_int_rb_iter_next (node, addr, - (addr + len) -1 )) { + addr + len)) {if (handler->ops->filter (node, addr, len))return node; }
@@ -293,11 +293,10 @@ static int mmu_notifier_range_start(struct mmu_notifier *mn,bool added = false;spin_lock_irqsave (&handler->lock, flags); -for (node =__mmu_int_rb_iter_first (root, range->start, range->end-1 ); +for (node =__mmu_int_rb_iter_first (root, range->start, range->end); node; node = ptr) {/* Guard against node removal. */ - ptr =__mmu_int_rb_iter_next (node, range->start, - range->end -1 ); + ptr =__mmu_int_rb_iter_next (node, range->start, range->end);trace_hfi1_mmu_mem_invalidate (node->addr, node->len);if (handler->ops->invalidate (handler->ops_arg, node)) {__mmu_int_rb_remove (node, root);
Signature · 1 line
2.16.4
Re: [PATCH 05/11] IB/hfi1: convert __mmu_int_rb to half closed intervals
Quoted 14 lines · Davidlohr Bueso
drivers/infiniband/hw/hfi1/mmu_rb.c +1
-1@@ -47,7 +47,7 @@#include <linux/list.h> #include <linux/rculist.h> #include <linux/mmu_notifier.h> -#include <linux/interval_tree_generic.h> +#include <linux/interval_tree_gen.h> #include "mmu_rb.h" #include "trace.h"
drivers/infiniband/hw/hfi1/mmu_rb.c static unsigned long mmu_node_start(struct mmu_rb_node *node) · line 93
Quoted 6 lines
drivers/infiniband/hw/hfi1/mmu_rb.c +1
-1@@ -89,7 +89,7 @@ static unsigned long mmu_node_start(struct mmu_rb_node *node)static unsigned long mmu_node_last (struct mmu_rb_node *node) { -return PAGE_ALIGN (node->addr + node->len) -1 ; +return PAGE_ALIGN (node->addr + node->len); }
May as well rename the function mmu_node_end(). I was worried if it was used anywhere else, but it turned out it's only used when defining the interval tree.
I would also suggest moving this function (as well as mmu_node_first) right before its use, rather than just after, which would allow you to also remove the function prototype a few lines earlier.
Looks good to me otherwise.
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
Re: [PATCH 05/11] IB/hfi1: convert __mmu_int_rb to half closed intervals
Quoted 16 lines · Michel Lespinasse
Quoted 15 lines · Davidlohr Bueso
drivers/infiniband/hw/hfi1/mmu_rb.c +1
-1@@ -47,7 +47,7 @@#include <linux/list.h> #include <linux/rculist.h> #include <linux/mmu_notifier.h> -#include <linux/interval_tree_generic.h> +#include <linux/interval_tree_gen.h> #include "mmu_rb.h" #include "trace.h" @@ -89,7 +89,7 @@ static unsigned long mmu_node_start(struct mmu_rb_node *node)
Quoted 9 lines
drivers/infiniband/hw/hfi1/mmu_rb.c static unsigned long mmu_node_start(struct mmu_rb_node *node) · line 93
Quoted 5 lines
drivers/infiniband/hw/hfi1/mmu_rb.c +1
-1static unsigned long mmu_node_last (struct mmu_rb_node *node) { -return PAGE_ALIGN (node->addr + node->len) -1 ; +return PAGE_ALIGN (node->addr + node->len); }May as well rename the function
mmu_node_end(). I was worried if it was used anywhere else, but it turned out it's only used when defining the interval tree.
Right.
In general I tried not to rename everything to end because I wanted to avoid bloating the diffstat, albeit having naming discrepancies within the code (which isn't new either fwiw).
Quoted 4 lines
I would also suggest moving this function (as well as
mmu_node_first) right before its use, rather than just after, which would allow you to also remove the function prototype a few lines earlier.
Indeed, but again I don't want to unnecessarily grow the patch. I have several notes to come back to once/if this series is settled.
Quoted 4 lines
Looks good to me otherwise.
Reviewed-by Michel Lespinasse <[email protected]>
Thanks,
Davidlohr
PATCH 6/11 IB,usnic: convert usnic_uiom_interval_tree to half closed intervals
In reply to Davidlohr BuesoThe usnic_uiom interval tree really wants [a, b) intervals, not fully closed. As such convert it to use the new interval_tree_gen.h, and also rename the 'last' endpoint in the node to 'end', which both a more suitable name for the half closed interval and also reduces the chances of some caller being missed.
The conversion can get non-trivial when calling into things like:
- find_intervals_intersection_sorted()
- usnic_uiom_insert_interval()
which have been converted to no longer subtracting one from the interval->end, hoping that the semantics of ad-hoc usage remain untouched.
--- drivers/infiniband/hw/usnic/usnic_uiom.c | 8 +++---- .../infiniband/hw/usnic/usnic_uiom_interval_tree.c | 26 ++++++++++------------ .../infiniband/hw/usnic/usnic_uiom_interval_tree.h | 2 +- 3 files changed, 17 insertions(+), 19 deletions(-)
drivers/infiniband/hw/usnic/usnic_uiom.c +4 -4
@@ -200,7 +200,7 @@ static void usnic_uiom_unmap_sorted_intervals(struct list_head *intervals,list_for_each_entry_safe (interval, tmp, intervals, link) { va = interval->start <<PAGE_SHIFT ; - size = ((interval->last - interval->start) +1 ) <<PAGE_SHIFT ; + size = (interval->end - interval->start) <<PAGE_SHIFT ;while (size >0 ) {/* Workaround for RH 970401 */ usnic_dbg ("va 0x%lx size 0x%lx" , va,PAGE_SIZE );
@@ -223,7 +223,7 @@ static void __usnic_uiom_reg_release(struct usnic_uiom_pd *pd, npages =PAGE_ALIGN (uiomr->length + uiomr->offset) >>PAGE_SHIFT ; vpn_start = (uiomr->va &PAGE_MASK ) >>PAGE_SHIFT ; - vpn_last = vpn_start + npages -1 ; + vpn_last = vpn_start + npages;spin_lock (&pd->lock); usnic_uiom_remove_interval(&pd->root, vpn_start,
@@ -293,7 +293,7 @@ static int usnic_uiom_map_sorted_intervals(struct list_head *intervals, pa_end = pa; } -if ((va >>PAGE_SHIFT ) == interval_node->last) { +if ((va >>PAGE_SHIFT ) == interval_node->end) {/* Last page of the interval */ size = pa - pa_start +PAGE_SIZE ; usnic_dbg("va 0x%lx pa %pa size 0x%zx flags 0x%x\n",
@@ -354,7 +354,7 @@ struct usnic_uiom_reg *usnic_uiom_reg_get(struct usnic_uiom_pd *pd, offset = addr & ~PAGE_MASK ; npages =PAGE_ALIGN (size + offset) >>PAGE_SHIFT ; vpn_start = (addr &PAGE_MASK ) >>PAGE_SHIFT ; - vpn_last = vpn_start + npages -1 ; + vpn_last = vpn_start + npages; uiomr =kmalloc (sizeof (*uiomr),GFP_KERNEL );if (!uiomr)
drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c +12 -14
@@ -36,11 +36,11 @@#include <linux/slab.h> #include <linux/list_sort.h> -#include <linux/interval_tree_generic.h> +#include <linux/interval_tree_gen.h> #include "usnic_uiom_interval_tree.h" #define START (node) ((node)->start) -#define LAST (node) ((node)->last) +#define END (node) ((node)->end)#define MAKE_NODE (node, start, end, ref_cnt, flags, err, err_out) \ do { \
@@ -76,7 +76,7 @@ usnic_uiom_interval_node_alloc(long int start, long int last, int ref_cnt,return NULL ; interval->start = start; - interval->last = last; + interval->end = last; interval->flags = flags; interval->ref_cnt = ref_cnt;
@@ -133,7 +133,7 @@ int usnic_uiom_get_intervals_diff(unsigned long start, unsigned long last,list_for_each_entry (interval, &intersection_set, link) {if (pivot < interval->start) { -MAKE_NODE_AND_APPEND (tmp, pivot, interval->start -1 , +MAKE_NODE_AND_APPEND (tmp, pivot, interval->start,1 , flags, err, err_out, diff_set); pivot = interval->start;
@@ -144,12 +144,10 @@ int usnic_uiom_get_intervals_diff(unsigned long start, unsigned long last,* but not in both. */ -if (pivot > interval->last) { +if (pivot > interval->end -1 ) {continue ; - }else if (pivot <= interval->last && -FLAGS_EQUAL (interval->flags, flags, - flag_mask)) { - pivot = interval->last +1 ; + }else if (FLAGS_EQUAL (interval->flags, flags, flag_mask)) { + pivot = interval->end; } }
@@ -195,15 +193,15 @@ int usnic_uiom_insert_interval(struct rb_root_cached *root, unsigned long start,* inserted */ istart = interval->start; - ilast = interval->last; + ilast = interval->end -1 ; iref_cnt = interval->ref_cnt; iflags = interval->flags;if (istart < lpivot) { -MAKE_NODE_AND_APPEND (tmp, istart, lpivot -1 , iref_cnt, +MAKE_NODE_AND_APPEND (tmp, istart, lpivot, iref_cnt, iflags, err, err_out, &to_add); }else if (istart > lpivot) { -MAKE_NODE_AND_APPEND (tmp, lpivot, istart -1 ,1 , flags, +MAKE_NODE_AND_APPEND (tmp, lpivot, istart,1 , flags, err, err_out, &to_add); lpivot = istart; }else {
@@ -222,7 +220,7 @@ int usnic_uiom_insert_interval(struct rb_root_cached *root, unsigned long start, &to_add); } - lpivot = ilast +1 ; + lpivot = interval->end; }if (lpivot <= last)
@@ -267,4 +265,4 @@ void usnic_uiom_remove_interval(struct rb_root_cached *root, INTERVAL_TREE_DEFINE(struct usnic_uiom_interval_node, rb, unsigned long, __subtree_last, - START, LAST, , usnic_uiom_interval_tree) + START, END, , usnic_uiom_interval_tree)
drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.h +1 -1
@@ -40,7 +40,7 @@ struct usnic_uiom_interval_node {struct rb_node rb;struct list_head link;unsigned long start; -unsigned long last; +unsigned long end;unsigned long __subtree_last;unsigned int ref_cnt;int flags;
Signature · 1 line
2.16.4
PATCH 7/11 vhost: convert vhost_umem_interval_tree to half closed intervals
In reply to Davidlohr BuesoThe vhost_umem interval tree really wants [a, b) intervals, not fully closed as currently. As such convert it to use the new interval_tree_gen.h, and also rename the 'last' endpoint in the node to 'end', which both a more suitable name for the half closed interval and also reduces the chances of some caller being missed.
--- drivers/vhost/vhost.c | 19 +++++++++---------- drivers/vhost/vhost.h | 4 ++-- 2 files changed, 11 insertions(+), 12 deletions(-)
drivers/vhost/vhost.c +9 -10
@@ -28,7 +28,7 @@#include <linux/sort.h> #include <linux/sched/mm.h> #include <linux/sched/signal.h> -#include <linux/interval_tree_generic.h> +#include <linux/interval_tree_gen.h> #include <linux/nospec.h> #include "vhost.h"
@@ -51,7 +51,7 @@ enum { INTERVAL_TREE_DEFINE(struct vhost_umem_node, rb, __u64, __subtree_last, - START, LAST, static inline, vhost_umem_interval_tree); + START, END, static inline, vhost_umem_interval_tree);#ifdef CONFIG_VHOST_CROSS_ENDIAN_LEGACY static void vhost_disable_cross_endian (struct vhost_virtqueue *vq)
@@ -1034,7 +1034,7 @@ static int vhost_new_umem_range(struct vhost_umem *umem, node->start = start; node->size = size; - node->last = end; + node->end = end; node->userspace_addr = userspace_addr; node->perm = perm;INIT_LIST_HEAD (&node->link);
@@ -1112,7 +1112,7 @@ static int vhost_process_iotlb_msg(struct vhost_dev *dev, }vhost_vq_meta_reset (dev);if (vhost_new_umem_range (dev->iotlb, msg->iova, msg->size, - msg->iova + msg->size -1 , + msg->iova + msg->size, msg->uaddr, msg->perm)) { ret = -ENOMEM ;break ;
@@ -1126,7 +1126,7 @@ static int vhost_process_iotlb_msg(struct vhost_dev *dev, }vhost_vq_meta_reset (dev);vhost_del_umem_range (dev->iotlb, msg->iova, - msg->iova + msg->size -1 ); + msg->iova + msg->size);break ;default : ret = -EINVAL ;
@@ -1320,15 +1320,14 @@ static bool iotlb_access_ok(struct vhost_virtqueue *vq, {const struct vhost_umem_node *node;struct vhost_umem *umem = vq->iotlb; -u64 s =0 , size, orig_addr = addr, last = addr + len -1 ; +u64 s =0 , size, orig_addr = addr, last = addr + len;if (vhost_vq_meta_fetch (vq, addr, len, type))return true;while (len > s) { node =vhost_umem_interval_tree_iter_first (&umem->umem_tree, - addr, - last); + addr, last);if (node ==NULL || node->start > addr) {vhost_iotlb_miss (vq, addr, access);return false;
@@ -1455,7 +1454,7 @@ static long vhost_set_memory(struct vhost_dev *d, struct vhost_memory __user *m) region->guest_phys_addr, region->memory_size, region->guest_phys_addr + - region->memory_size -1 , + region->memory_size, region->userspace_addr, VHOST_ACCESS_RW)) goto err;
@@ -2055,7 +2054,7 @@ static int translate_desc(struct vhost_virtqueue *vq, u64 addr, u32 len, } node =vhost_umem_interval_tree_iter_first (&umem->umem_tree, - addr, addr + len -1 ); + addr, addr + len);if (node ==NULL || node->start > addr) {if (umem != dev->iotlb) { ret = -EFAULT ;
drivers/vhost/vhost.h +2 -2
@@ -53,13 +53,13 @@ struct vhost_log { };#define START (node) ((node)->start) -#define LAST (node) ((node)->last) +#define END (node) ((node)->end)struct vhost_umem_node {struct rb_node rb;struct list_head link;__u64 start; -__u64 last; +__u64 end;__u64 size;__u64 userspace_addr;__u32 perm;
Signature · 1 line
2.16.4
Re: [PATCH 07/11] vhost: convert vhost_umem_interval_tree to half closed intervals
drivers/vhost/vhost.c static bool iotlb_access_ok(struct vhost_virtqueue *vq, · line 1323
Quoted 6 lines · Davidlohr Bueso
drivers/vhost/vhost.c +1
-1@@ -1320,15 +1320,14 @@ static bool iotlb_access_ok(struct vhost_virtqueue *vq, {const struct vhost_umem_node *node;struct vhost_umem *umem = vq->iotlb; -u64 s =0 , size, orig_addr = addr, last = addr + len -1 ; +u64 s =0 , size, orig_addr = addr, last = addr + len;
maybe "end" or "end_addr" instead of "last".
Quoted 10 lines
drivers/vhost/vhost.h +1
-1@@ -53,13 +53,13 @@ struct vhost_log { };#define START (node) ((node)->start) -#define LAST (node) ((node)->last) +#define END (node) ((node)->end)
drivers/vhost/vhost.h struct vhost_log { · line 65
Quoted 10 lines
drivers/vhost/vhost.h +1
-1struct vhost_umem_node {struct rb_node rb;struct list_head link;__u64 start; -__u64 last; +__u64 end;__u64 size;__u64 userspace_addr;__u32 perm;
Preferably also rename __subtree_last to __subtree_end
Looks good to me otherwise.
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
Re: [PATCH 07/11] vhost: convert vhost_umem_interval_tree to half closed intervals
Quoted 21 lines · Michel Lespinasse
drivers/vhost/vhost.c static bool iotlb_access_ok(struct vhost_virtqueue *vq, · line 1323
Quoted 6 lines · Davidlohr Bueso
drivers/vhost/vhost.c +1
-1@@ -1320,15 +1320,14 @@ static bool iotlb_access_ok(struct vhost_virtqueue *vq, {const struct vhost_umem_node *node;struct vhost_umem *umem = vq->iotlb; -u64 s =0 , size, orig_addr = addr, last = addr + len -1 ; +u64 s =0 , size, orig_addr = addr, last = addr + len;maybe "end" or "
end_addr" instead of "last".Quoted 11 lines
drivers/vhost/vhost.h +1
-1@@ -53,13 +53,13 @@ struct vhost_log { };#define START (node) ((node)->start) -#define LAST (node) ((node)->last) +#define END (node) ((node)->end)
Quoted 11 lines
drivers/vhost/vhost.h struct vhost_log { · line 65
Quoted 9 lines
drivers/vhost/vhost.h +1
-1struct vhost_umem_node {struct rb_node rb;struct list_head link;__u64 start; -__u64 last; +__u64 end;__u64 size;__u64 userspace_addr;__u32 perm;Preferably also rename
__subtree_lastto__subtree_end
Yes, this was was another one that I had in mind renaming, but didn't want to grow the series -- all custom interval trees name _last for the subtree iirc. Like my previous reply, I'd rather leave this stuff for a followup series.
Thanks,
Davidlohr
Re: [PATCH 07/11] vhost: convert vhost_umem_interval_tree to half closed intervals
In reply to Davidlohr BuesoQuoted 111 lines · Davidlohr Bueso
The
vhost_umeminterval tree really wants [a, b) intervals, not fully closed as currently. As such convert it to use the newinterval_tree_gen.h, and also rename the 'last' endpoint in the node to 'end', which both a more suitable name for the half closed interval and also reduces the chances of some caller being missed.Cc Michael S. Tsirkin" <[email protected]>Cc Jason Wang <[email protected]>Signed-off-by Davidlohr Bueso <[email protected]>--- drivers/vhost/vhost.c | 19 +++++++++---------- drivers/vhost/vhost.h | 4 ++-- 2 files changed, 11 insertions(+), 12 deletions(-)drivers/vhost/vhost.c +9
-10@@ -28,7 +28,7 @@#include <linux/sort.h> #include <linux/sched/mm.h> #include <linux/sched/signal.h> -#include <linux/interval_tree_generic.h> +#include <linux/interval_tree_gen.h> #include <linux/nospec.h> #include "vhost.h" @@ -51,7 +51,7 @@ enum { INTERVAL_TREE_DEFINE(struct vhost_umem_node, rb, __u64, __subtree_last, - START, LAST, static inline, vhost_umem_interval_tree); + START, END, static inline, vhost_umem_interval_tree);#ifdef CONFIG_VHOST_CROSS_ENDIAN_LEGACY static void vhost_disable_cross_endian (struct vhost_virtqueue *vq)@@ -1034,7 +1034,7 @@ static int vhost_new_umem_range(struct vhost_umem *umem, node->start = start; node->size = size; - node->last = end; + node->end = end; node->userspace_addr = userspace_addr; node->perm = perm;INIT_LIST_HEAD (&node->link);@@ -1112,7 +1112,7 @@ static int vhost_process_iotlb_msg(struct vhost_dev *dev, }vhost_vq_meta_reset (dev);if (vhost_new_umem_range (dev->iotlb, msg->iova, msg->size, - msg->iova + msg->size -1 , + msg->iova + msg->size, msg->uaddr, msg->perm)) { ret = -ENOMEM ;break ;@@ -1126,7 +1126,7 @@ static int vhost_process_iotlb_msg(struct vhost_dev *dev, }vhost_vq_meta_reset (dev);vhost_del_umem_range (dev->iotlb, msg->iova, - msg->iova + msg->size -1 ); + msg->iova + msg->size);break ;default : ret = -EINVAL ;@@ -1320,15 +1320,14 @@ static bool iotlb_access_ok(struct vhost_virtqueue *vq, {const struct vhost_umem_node *node;struct vhost_umem *umem = vq->iotlb; -u64 s =0 , size, orig_addr = addr, last = addr + len -1 ; +u64 s =0 , size, orig_addr = addr, last = addr + len;if (vhost_vq_meta_fetch (vq, addr, len, type))return true;while (len > s) { node =vhost_umem_interval_tree_iter_first (&umem->umem_tree, - addr, - last); + addr, last);if (node ==NULL || node->start > addr) {vhost_iotlb_miss (vq, addr, access);return false;@@ -1455,7 +1454,7 @@ static long vhost_set_memory(struct vhost_dev *d, struct vhost_memory __user *m) region->guest_phys_addr, region->memory_size, region->guest_phys_addr + - region->memory_size -1 , + region->memory_size, region->userspace_addr, VHOST_ACCESS_RW)) goto err;@@ -2055,7 +2054,7 @@ static int translate_desc(struct vhost_virtqueue *vq, u64 addr, u32 len, } node =vhost_umem_interval_tree_iter_first (&umem->umem_tree, - addr, addr + len -1 ); + addr, addr + len);if (node ==NULL || node->start > addr) {if (umem != dev->iotlb) { ret = -EFAULT ;drivers/vhost/vhost.h +1
-1@@ -53,13 +53,13 @@ struct vhost_log { };#define START (node) ((node)->start) -#define LAST (node) ((node)->last) +#define END (node) ((node)->end)
drivers/vhost/vhost.h struct vhost_log { · line 65
Quoted 10 lines
drivers/vhost/vhost.h +1
-1struct vhost_umem_node {struct rb_node rb;struct list_head link;__u64 start; -__u64 last; +__u64 end;__u64 size;__u64 userspace_addr;__u32 perm;
_______________________________________________
Virtualization mailing list
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/virtualization
Re: [PATCH 07/11] vhost: convert vhost_umem_interval_tree to half closed intervals
In reply to Davidlohr BuesoQuoted 111 lines · Davidlohr Bueso
The
vhost_umeminterval tree really wants [a, b) intervals, not fully closed as currently. As such convert it to use the newinterval_tree_gen.h, and also rename the 'last' endpoint in the node to 'end', which both a more suitable name for the half closed interval and also reduces the chances of some caller being missed.Cc Michael S. Tsirkin" <[email protected]>Cc Jason Wang <[email protected]>Signed-off-by Davidlohr Bueso <[email protected]>--- drivers/vhost/vhost.c | 19 +++++++++---------- drivers/vhost/vhost.h | 4 ++-- 2 files changed, 11 insertions(+), 12 deletions(-)drivers/vhost/vhost.c +9
-10@@ -28,7 +28,7 @@#include <linux/sort.h> #include <linux/sched/mm.h> #include <linux/sched/signal.h> -#include <linux/interval_tree_generic.h> +#include <linux/interval_tree_gen.h> #include <linux/nospec.h> #include "vhost.h" @@ -51,7 +51,7 @@ enum { INTERVAL_TREE_DEFINE(struct vhost_umem_node, rb, __u64, __subtree_last, - START, LAST, static inline, vhost_umem_interval_tree); + START, END, static inline, vhost_umem_interval_tree);#ifdef CONFIG_VHOST_CROSS_ENDIAN_LEGACY static void vhost_disable_cross_endian (struct vhost_virtqueue *vq)@@ -1034,7 +1034,7 @@ static int vhost_new_umem_range(struct vhost_umem *umem, node->start = start; node->size = size; - node->last = end; + node->end = end; node->userspace_addr = userspace_addr; node->perm = perm;INIT_LIST_HEAD (&node->link);@@ -1112,7 +1112,7 @@ static int vhost_process_iotlb_msg(struct vhost_dev *dev, }vhost_vq_meta_reset (dev);if (vhost_new_umem_range (dev->iotlb, msg->iova, msg->size, - msg->iova + msg->size -1 , + msg->iova + msg->size, msg->uaddr, msg->perm)) { ret = -ENOMEM ;break ;@@ -1126,7 +1126,7 @@ static int vhost_process_iotlb_msg(struct vhost_dev *dev, }vhost_vq_meta_reset (dev);vhost_del_umem_range (dev->iotlb, msg->iova, - msg->iova + msg->size -1 ); + msg->iova + msg->size);break ;default : ret = -EINVAL ;@@ -1320,15 +1320,14 @@ static bool iotlb_access_ok(struct vhost_virtqueue *vq, {const struct vhost_umem_node *node;struct vhost_umem *umem = vq->iotlb; -u64 s =0 , size, orig_addr = addr, last = addr + len -1 ; +u64 s =0 , size, orig_addr = addr, last = addr + len;if (vhost_vq_meta_fetch (vq, addr, len, type))return true;while (len > s) { node =vhost_umem_interval_tree_iter_first (&umem->umem_tree, - addr, - last); + addr, last);if (node ==NULL || node->start > addr) {vhost_iotlb_miss (vq, addr, access);return false;@@ -1455,7 +1454,7 @@ static long vhost_set_memory(struct vhost_dev *d, struct vhost_memory __user *m) region->guest_phys_addr, region->memory_size, region->guest_phys_addr + - region->memory_size -1 , + region->memory_size, region->userspace_addr, VHOST_ACCESS_RW)) goto err;@@ -2055,7 +2054,7 @@ static int translate_desc(struct vhost_virtqueue *vq, u64 addr, u32 len, } node =vhost_umem_interval_tree_iter_first (&umem->umem_tree, - addr, addr + len -1 ); + addr, addr + len);if (node ==NULL || node->start > addr) {if (umem != dev->iotlb) { ret = -EFAULT ;drivers/vhost/vhost.h +1
-1@@ -53,13 +53,13 @@ struct vhost_log { };#define START (node) ((node)->start) -#define LAST (node) ((node)->last) +#define END (node) ((node)->end)
drivers/vhost/vhost.h struct vhost_log { · line 65
Quoted 10 lines
drivers/vhost/vhost.h +1
-1struct vhost_umem_node {struct rb_node rb;struct list_head link;__u64 start; -__u64 last; +__u64 end;__u64 size;__u64 userspace_addr;__u32 perm;
_______________________________________________
dri-devel mailing list
[email protected]
https://lists.freedesktop.org/mailman/listinfo/dri-devel
PATCH 7/11 vhost: convert vhost_umem_interval_tree to half closed intervals
In reply to Davidlohr BuesoThe vhost_umem interval tree really wants [a, b) intervals, not fully closed as currently. As such convert it to use the new interval_tree_gen.h, and also rename the 'last' endpoint in the node to 'end', which both a more suitable name for the half closed interval and also reduces the chances of some caller being missed.
--- drivers/vhost/vhost.c | 19 +++++++++---------- drivers/vhost/vhost.h | 4 ++-- 2 files changed, 11 insertions(+), 12 deletions(-)
drivers/vhost/vhost.c +9 -10
@@ -28,7 +28,7 @@#include <linux/sort.h> #include <linux/sched/mm.h> #include <linux/sched/signal.h> -#include <linux/interval_tree_generic.h> +#include <linux/interval_tree_gen.h> #include <linux/nospec.h> #include "vhost.h"
@@ -51,7 +51,7 @@ enum { INTERVAL_TREE_DEFINE(struct vhost_umem_node, rb, __u64, __subtree_last, - START, LAST, static inline, vhost_umem_interval_tree); + START, END, static inline, vhost_umem_interval_tree);#ifdef CONFIG_VHOST_CROSS_ENDIAN_LEGACY static void vhost_disable_cross_endian (struct vhost_virtqueue *vq)
@@ -1034,7 +1034,7 @@ static int vhost_new_umem_range(struct vhost_umem *umem, node->start = start; node->size = size; - node->last = end; + node->end = end; node->userspace_addr = userspace_addr; node->perm = perm;INIT_LIST_HEAD (&node->link);
@@ -1112,7 +1112,7 @@ static int vhost_process_iotlb_msg(struct vhost_dev *dev, }vhost_vq_meta_reset (dev);if (vhost_new_umem_range (dev->iotlb, msg->iova, msg->size, - msg->iova + msg->size -1 , + msg->iova + msg->size, msg->uaddr, msg->perm)) { ret = -ENOMEM ;break ;
@@ -1126,7 +1126,7 @@ static int vhost_process_iotlb_msg(struct vhost_dev *dev, }vhost_vq_meta_reset (dev);vhost_del_umem_range (dev->iotlb, msg->iova, - msg->iova + msg->size -1 ); + msg->iova + msg->size);break ;default : ret = -EINVAL ;
@@ -1320,15 +1320,14 @@ static bool iotlb_access_ok(struct vhost_virtqueue *vq, {const struct vhost_umem_node *node;struct vhost_umem *umem = vq->iotlb; -u64 s =0 , size, orig_addr = addr, last = addr + len -1 ; +u64 s =0 , size, orig_addr = addr, last = addr + len;if (vhost_vq_meta_fetch (vq, addr, len, type))return true;while (len > s) { node =vhost_umem_interval_tree_iter_first (&umem->umem_tree, - addr, - last); + addr, last);if (node ==NULL || node->start > addr) {vhost_iotlb_miss (vq, addr, access);return false;
@@ -1455,7 +1454,7 @@ static long vhost_set_memory(struct vhost_dev *d, struct vhost_memory __user *m) region->guest_phys_addr, region->memory_size, region->guest_phys_addr + - region->memory_size -1 , + region->memory_size, region->userspace_addr, VHOST_ACCESS_RW)) goto err;
@@ -2055,7 +2054,7 @@ static int translate_desc(struct vhost_virtqueue *vq, u64 addr, u32 len, } node =vhost_umem_interval_tree_iter_first (&umem->umem_tree, - addr, addr + len -1 ); + addr, addr + len);if (node ==NULL || node->start > addr) {if (umem != dev->iotlb) { ret = -EFAULT ;
drivers/vhost/vhost.h +2 -2
@@ -53,13 +53,13 @@ struct vhost_log { };#define START (node) ((node)->start) -#define LAST (node) ((node)->last) +#define END (node) ((node)->end)struct vhost_umem_node {struct rb_node rb;struct list_head link;__u64 start; -__u64 last; +__u64 end;__u64 size;__u64 userspace_addr;__u32 perm;
Signature · 1 line
2.16.4
PATCH 8/11 mm: convert vma_interval_tree to half closed intervals
In reply to Davidlohr BuesoThe vma and anon vma interval tree really wants [a, b) intervals, not fully closed. As such convert it to use the new interval_tree_gen.h. Because of vma_last_pgoff(), the conversion is quite straightforward.
--- include/linux/mm.h | 4 ++-- mm/interval_tree.c | 4 ++-- mm/memory.c | 2 +- mm/nommu.c | 2 +- mm/rmap.c | 6 +++--- 5 files changed, 9 insertions(+), 9 deletions(-)
include/linux/mm.h +2 -2
@@ -2249,7 +2249,7 @@ struct vm_area_struct *vma_interval_tree_iter_next(struct vm_area_struct *node, vma; vma = vma_interval_tree_iter_next(vma, start, last))#define vma_interval_tree_foreach_stab (vma, root, start) \ - vma_interval_tree_foreach(vma, root, start, start) + vma_interval_tree_foreach(vma, root, start, start + 1)void anon_vma_interval_tree_insert (struct anon_vma_chain *node,struct rb_root_cached *root);
@@ -2269,7 +2269,7 @@ void anon_vma_interval_tree_verify(struct anon_vma_chain *node); avc; avc = anon_vma_interval_tree_iter_next(avc, start, last))#define anon_vma_interval_tree_foreach_stab (vma, root, start) \ - anon_vma_interval_tree_foreach(vma, root, start, start) + anon_vma_interval_tree_foreach(vma, root, start, start + 1)/* mmap.c */ extern int __vm_enough_memory (struct mm_struct *mm,long pages,int cap_sys_admin);
mm/interval_tree.c +2 -2
@@ -8,7 +8,7 @@#include <linux/mm.h> #include <linux/fs.h> #include <linux/rmap.h> -#include <linux/interval_tree_generic.h> +#include <linux/interval_tree_gen.h> static inline unsigned long vma_start_pgoff (struct vm_area_struct *v) {
@@ -17,7 +17,7 @@ static inline unsigned long vma_start_pgoff(struct vm_area_struct *v)static inline unsigned long vma_last_pgoff (struct vm_area_struct *v) { -return v->vm_pgoff +vma_pages (v) -1 ; +return v->vm_pgoff +vma_pages (v); } INTERVAL_TREE_DEFINE(struct vm_area_struct, shared.rb,
mm/memory.c +1 -1
@@ -2679,7 +2679,7 @@ void unmap_mapping_pages(struct address_space *mapping, pgoff_t start, details.check_mapping = even_cows ?NULL : mapping; details.first_index = start; - details.last_index = start + nr -1 ; + details.last_index = start + nr;if (details.last_index < details.first_index) details.last_index =ULONG_MAX ;
mm/nommu.c +1 -1
@@ -1793,7 +1793,7 @@ int nommu_shrink_inode_mappings(struct inode *inode, size_t size,size_t r_size, r_top; low = newsize >>PAGE_SHIFT ; - high = (size +PAGE_SIZE -1 ) >>PAGE_SHIFT ; + high = (size +PAGE_SIZE ) >>PAGE_SHIFT ;down_write (&nommu_region_sem);i_mmap_lock_read (inode->i_mapping);
mm/rmap.c +3 -3
@@ -1826,7 +1826,7 @@ static void rmap_walk_anon(struct page *page, struct rmap_walk_control *rwc,return ; pgoff_start =page_to_pgoff (page); - pgoff_end = pgoff_start +hpage_nr_pages (page) -1 ; + pgoff_end = pgoff_start +hpage_nr_pages (page);anon_vma_interval_tree_foreach (avc, &anon_vma->rb_root, pgoff_start, pgoff_end) {struct vm_area_struct *vma = avc->vma;
@@ -1879,11 +1879,11 @@ static void rmap_walk_file(struct page *page, struct rmap_walk_control *rwc,return ; pgoff_start =page_to_pgoff (page); - pgoff_end = pgoff_start +hpage_nr_pages (page) -1 ; + pgoff_end = pgoff_start +hpage_nr_pages (page);if (!locked)i_mmap_lock_read (mapping);vma_interval_tree_foreach (vma, &mapping->i_mmap, - pgoff_start, pgoff_end) { + pgoff_start, pgoff_end) {unsigned long address =vma_address (page, vma);cond_resched ();
Signature · 1 line
2.16.4
Matthew Wilcox
reviewerRe: [PATCH 08/11] mm: convert vma_interval_tree to half closed intervals
mm/nommu.c int nommu_shrink_inode_mappings(struct inode *inode, size_t size, · line 1796
Quoted 7 lines · Davidlohr Bueso
+++
b/mm/nommu.cmm/nommu.c +1
-1@@ -1793,7 +1793,7 @@ int nommu_shrink_inode_mappings(struct inode *inode, size_t size,size_t r_size, r_top; low = newsize >>PAGE_SHIFT ; - high = (size +PAGE_SIZE -1 ) >>PAGE_SHIFT ; + high = (size +PAGE_SIZE ) >>PAGE_SHIFT ;
Uhh ... are you sure about this? size is in bytes here, and we're rounding up to the next page size. So if size is [1-4096], then we add on 4095 and get the answer 1. With your patch, if size is [0-4095], we get the answer 1. I think you meant:
high = ((size + PAGE_SIZE - 1) >> PAGE_SHIFT) + 1;
Re: [PATCH 08/11] mm: convert vma_interval_tree to half closed intervals
In reply to Davidlohr BuesoQuoted 4 lines · Davidlohr Bueso
The vma and anon vma interval tree really wants [a, b) intervals, not fully closed. As such convert it to use the new
interval_tree_gen.h. Because ofvma_last_pgoff(), the conversion is quite straightforward.
I am not certain if we need to worry about integer overflow here. The problem case would be accessing the last block of a file that is exactly 16TB long, on an arch where long (and thus pgoff_t) is 32-bit. Maybe FS folks can tell us whether that case is currently supported, or if we can just not worry about it ?
I would also want to rename the fields in struct zap_details into start_index and end_index so we can verify we don't leave any off-by-one uses.
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
PATCH 9/11 lib/interval-tree: convert interval_tree to half closed intervals
In reply to Davidlohr BuesoThe 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.
--- 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(-)
drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c +3 -9
@@ -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);
drivers/gpu/drm/i915/gem/i915_gem_userptr.c +1 -4
@@ -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;
drivers/gpu/drm/radeon/radeon_mn.c +4 -7
@@ -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);
drivers/gpu/drm/radeon/radeon_trace.h +1 -1
@@ -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",
drivers/gpu/drm/radeon/radeon_vm.c +13 -13
@@ -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); }
drivers/infiniband/core/umem_odp.c +7 -14
@@ -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; }
drivers/iommu/virtio-iommu.c +3 -3
@@ -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);
include/linux/interval_tree.h +1 -1
@@ -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; };
include/rdma/ib_umem_odp.h +2 -2
@@ -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);
lib/interval_tree.c +3 -3
@@ -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);
Signature · 1 line
2.16.4
kbuild test robot
build botRe: [PATCH 09/11] lib/interval-tree: convert interval_tree to half closed intervals
I love your patch! Yet something to improve:
Hi Davidlohr,
I love your patch! Yet something to improve:
[auto build test ERROR on next-20191003]
url: https://github.com/0day-ci/linux/commits/Davidlohr-Bueso/lib-interval-tree-move-to-half-closed-intervals/20191004-042411
config: arm64-allyesconfig (attached as .config)
compiler: aarch64-linux-gcc (GCC) 7.4.0
reproduce:
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
GCC_VERSION=7.4.0 make.cross ARCH=arm64
If you fix the issue, kindly add following tag
All error/warnings (new ones prefixed by >>):
In file included from include/linux/swab.h:5:0,
from include/uapi/linux/byteorder/big_endian.h:13,
from include/linux/byteorder/big_endian.h:5,
from arch/arm64/include/uapi/asm/byteorder.h:21,
from include/asm-generic/bitops/le.h:6,
from arch/arm64/include/asm/bitops.h:29,
from include/linux/bitops.h:26,
from include/linux/kernel.h:12,
from include/linux/clk.h:13,
from include/linux/amba/bus.h:14,
from drivers//iommu/virtio-iommu.c:10:
drivers//iommu/virtio-iommu.c: In function 'viommu_replay_mappings':
>> drivers//iommu/virtio-iommu.c:403:41: error: 'struct interval_tree_node' has no member named 'last'
.virt_end = cpu_to_le64(mapping->iova.last),
^
include/uapi/linux/swab.h:130:32: note: in definition of macro '__swab64'
(__builtin_constant_p((__u64)(x)) ? \
^
>> include/linux/byteorder/generic.h:86:21: note: in expansion of macro '__cpu_to_le64'
#define cpu_to_le64 __cpu_to_le64
^~~~~~~~~~~~~
>> drivers//iommu/virtio-iommu.c:403:16: note: in expansion of macro 'cpu_to_le64'
.virt_end = cpu_to_le64(mapping->iova.last),
^~~~~~~~~~~
>> drivers//iommu/virtio-iommu.c:403:41: error: 'struct interval_tree_node' has no member named 'last'
.virt_end = cpu_to_le64(mapping->iova.last),
^
include/uapi/linux/swab.h:24:12: note: in definition of macro '___constant_swab64'
(((__u64)(x) & (__u64)0x00000000000000ffULL) << 56) | \
^
>> include/uapi/linux/byteorder/big_endian.h:31:43: note: in expansion of macro '__swab64'
#define __cpu_to_le64(x) ((__force __le64)__swab64((x)))
^~~~~~~~
>> include/linux/byteorder/generic.h:86:21: note: in expansion of macro '__cpu_to_le64'
#define cpu_to_le64 __cpu_to_le64
^~~~~~~~~~~~~
>> drivers//iommu/virtio-iommu.c:403:16: note: in expansion of macro 'cpu_to_le64'
.virt_end = cpu_to_le64(mapping->iova.last),
^~~~~~~~~~~
>> drivers//iommu/virtio-iommu.c:403:41: error: 'struct interval_tree_node' has no member named 'last'
.virt_end = cpu_to_le64(mapping->iova.last),
^
include/uapi/linux/swab.h:25:12: note: in definition of macro '___constant_swab64'
(((__u64)(x) & (__u64)0x000000000000ff00ULL) << 40) | \
^
>> include/uapi/linux/byteorder/big_endian.h:31:43: note: in expansion of macro '__swab64'
#define __cpu_to_le64(x) ((__force __le64)__swab64((x)))
^~~~~~~~
>> include/linux/byteorder/generic.h:86:21: note: in expansion of macro '__cpu_to_le64'
#define cpu_to_le64 __cpu_to_le64
^~~~~~~~~~~~~
>> drivers//iommu/virtio-iommu.c:403:16: note: in expansion of macro 'cpu_to_le64'
.virt_end = cpu_to_le64(mapping->iova.last),
^~~~~~~~~~~
>> drivers//iommu/virtio-iommu.c:403:41: error: 'struct interval_tree_node' has no member named 'last'
.virt_end = cpu_to_le64(mapping->iova.last),
^
include/uapi/linux/swab.h:26:12: note: in definition of macro '___constant_swab64'
(((__u64)(x) & (__u64)0x0000000000ff0000ULL) << 24) | \
^
>> include/uapi/linux/byteorder/big_endian.h:31:43: note: in expansion of macro '__swab64'
#define __cpu_to_le64(x) ((__force __le64)__swab64((x)))
^~~~~~~~
>> include/linux/byteorder/generic.h:86:21: note: in expansion of macro '__cpu_to_le64'
#define cpu_to_le64 __cpu_to_le64
^~~~~~~~~~~~~
>> drivers//iommu/virtio-iommu.c:403:16: note: in expansion of macro 'cpu_to_le64'
.virt_end = cpu_to_le64(mapping->iova.last),
^~~~~~~~~~~
>> drivers//iommu/virtio-iommu.c:403:41: error: 'struct interval_tree_node' has no member named 'last'
.virt_end = cpu_to_le64(mapping->iova.last),
^
include/uapi/linux/swab.h:27:12: note: in definition of macro '___constant_swab64'
(((__u64)(x) & (__u64)0x00000000ff000000ULL) << 8) | \
^
>> include/uapi/linux/byteorder/big_endian.h:31:43: note: in expansion of macro '__swab64'
#define __cpu_to_le64(x) ((__force __le64)__swab64((x)))
^~~~~~~~
>> include/linux/byteorder/generic.h:86:21: note: in expansion of macro '__cpu_to_le64'
#define cpu_to_le64 __cpu_to_le64
^~~~~~~~~~~~~
>> drivers//iommu/virtio-iommu.c:403:16: note: in expansion of macro 'cpu_to_le64'
.virt_end = cpu_to_le64(mapping->iova.last),
^~~~~~~~~~~
>> drivers//iommu/virtio-iommu.c:403:41: error: 'struct interval_tree_node' has no member named 'last'
.virt_end = cpu_to_le64(mapping->iova.last),
^
include/uapi/linux/swab.h:28:12: note: in definition of macro '___constant_swab64'
(((__u64)(x) & (__u64)0x000000ff00000000ULL) >> 8) | \
^
--
In file included from include/linux/swab.h:5:0,
from include/uapi/linux/byteorder/big_endian.h:13,
from include/linux/byteorder/big_endian.h:5,
from arch/arm64/include/uapi/asm/byteorder.h:21,
from include/asm-generic/bitops/le.h:6,
from arch/arm64/include/asm/bitops.h:29,
from include/linux/bitops.h:26,
from include/linux/kernel.h:12,
from include/linux/clk.h:13,
from include/linux/amba/bus.h:14,
from drivers/iommu/virtio-iommu.c:10:
drivers/iommu/virtio-iommu.c: In function 'viommu_replay_mappings':
drivers/iommu/virtio-iommu.c:403:41: error: 'struct interval_tree_node' has no member named 'last'
.virt_end = cpu_to_le64(mapping->iova.last),
^
include/uapi/linux/swab.h:130:32: note: in definition of macro '__swab64'
(__builtin_constant_p((__u64)(x)) ? \
^
>> include/linux/byteorder/generic.h:86:21: note: in expansion of macro '__cpu_to_le64'
#define cpu_to_le64 __cpu_to_le64
^~~~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:16: note: in expansion of macro 'cpu_to_le64'
.virt_end = cpu_to_le64(mapping->iova.last),
^~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:41: error: 'struct interval_tree_node' has no member named 'last'
.virt_end = cpu_to_le64(mapping->iova.last),
^
include/uapi/linux/swab.h:24:12: note: in definition of macro '___constant_swab64'
(((__u64)(x) & (__u64)0x00000000000000ffULL) << 56) | \
^
>> include/uapi/linux/byteorder/big_endian.h:31:43: note: in expansion of macro '__swab64'
#define __cpu_to_le64(x) ((__force __le64)__swab64((x)))
^~~~~~~~
>> include/linux/byteorder/generic.h:86:21: note: in expansion of macro '__cpu_to_le64'
#define cpu_to_le64 __cpu_to_le64
^~~~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:16: note: in expansion of macro 'cpu_to_le64'
.virt_end = cpu_to_le64(mapping->iova.last),
^~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:41: error: 'struct interval_tree_node' has no member named 'last'
.virt_end = cpu_to_le64(mapping->iova.last),
^
include/uapi/linux/swab.h:25:12: note: in definition of macro '___constant_swab64'
(((__u64)(x) & (__u64)0x000000000000ff00ULL) << 40) | \
^
>> include/uapi/linux/byteorder/big_endian.h:31:43: note: in expansion of macro '__swab64'
#define __cpu_to_le64(x) ((__force __le64)__swab64((x)))
^~~~~~~~
>> include/linux/byteorder/generic.h:86:21: note: in expansion of macro '__cpu_to_le64'
#define cpu_to_le64 __cpu_to_le64
^~~~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:16: note: in expansion of macro 'cpu_to_le64'
.virt_end = cpu_to_le64(mapping->iova.last),
^~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:41: error: 'struct interval_tree_node' has no member named 'last'
.virt_end = cpu_to_le64(mapping->iova.last),
^
include/uapi/linux/swab.h:26:12: note: in definition of macro '___constant_swab64'
(((__u64)(x) & (__u64)0x0000000000ff0000ULL) << 24) | \
^
>> include/uapi/linux/byteorder/big_endian.h:31:43: note: in expansion of macro '__swab64'
#define __cpu_to_le64(x) ((__force __le64)__swab64((x)))
^~~~~~~~
>> include/linux/byteorder/generic.h:86:21: note: in expansion of macro '__cpu_to_le64'
#define cpu_to_le64 __cpu_to_le64
^~~~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:16: note: in expansion of macro 'cpu_to_le64'
.virt_end = cpu_to_le64(mapping->iova.last),
^~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:41: error: 'struct interval_tree_node' has no member named 'last'
.virt_end = cpu_to_le64(mapping->iova.last),
^
include/uapi/linux/swab.h:27:12: note: in definition of macro '___constant_swab64'
(((__u64)(x) & (__u64)0x00000000ff000000ULL) << 8) | \
^
>> include/uapi/linux/byteorder/big_endian.h:31:43: note: in expansion of macro '__swab64'
#define __cpu_to_le64(x) ((__force __le64)__swab64((x)))
^~~~~~~~
>> include/linux/byteorder/generic.h:86:21: note: in expansion of macro '__cpu_to_le64'
#define cpu_to_le64 __cpu_to_le64
^~~~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:16: note: in expansion of macro 'cpu_to_le64'
.virt_end = cpu_to_le64(mapping->iova.last),
^~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:41: error: 'struct interval_tree_node' has no member named 'last'
.virt_end = cpu_to_le64(mapping->iova.last),
^
include/uapi/linux/swab.h:28:12: note: in definition of macro '___constant_swab64'
(((__u64)(x) & (__u64)0x000000ff00000000ULL) >> 8) | \
^
>> include/uapi/linux/byteorder/big_endian.h:31:43: note: in expansion of macro '__swab64'
#define __cpu_to_le64(x) ((__force __le64)__swab64((x)))
^~~~~~~~
>> include/linux/byteorder/generic.h:86:21: note: in expansion of macro '__cpu_to_le64'
#define cpu_to_le64 __cpu_to_le64
^~~~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:16: note: in expansion of macro 'cpu_to_le64'
.virt_end = cpu_to_le64(mapping->iova.last),
^~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:41: error: 'struct interval_tree_node' has no member named 'last'
.virt_end = cpu_to_le64(mapping->iova.last),
^
include/uapi/linux/swab.h:29:12: note: in definition of macro '___constant_swab64'
(((__u64)(x) & (__u64)0x0000ff0000000000ULL) >> 24) | \
^
>> include/uapi/linux/byteorder/big_endian.h:31:43: note: in expansion of macro '__swab64'
#define __cpu_to_le64(x) ((__force __le64)__swab64((x)))
^~~~~~~~
>> include/linux/byteorder/generic.h:86:21: note: in expansion of macro '__cpu_to_le64'
#define cpu_to_le64 __cpu_to_le64
^~~~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:16: note: in expansion of macro 'cpu_to_le64'
.virt_end = cpu_to_le64(mapping->iova.last),
^~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:41: error: 'struct interval_tree_node' has no member named 'last'
.virt_end = cpu_to_le64(mapping->iova.last),
^
include/uapi/linux/swab.h:30:12: note: in definition of macro '___constant_swab64'
(((__u64)(x) & (__u64)0x00ff000000000000ULL) >> 40) | \
^
>> include/uapi/linux/byteorder/big_endian.h:31:43: note: in expansion of macro '__swab64'
#define __cpu_to_le64(x) ((__force __le64)__swab64((x)))
^~~~~~~~
>> include/linux/byteorder/generic.h:86:21: note: in expansion of macro '__cpu_to_le64'
#define cpu_to_le64 __cpu_to_le64
^~~~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:16: note: in expansion of macro 'cpu_to_le64'
.virt_end = cpu_to_le64(mapping->iova.last),
^~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:41: error: 'struct interval_tree_node' has no member named 'last'
.virt_end = cpu_to_le64(mapping->iova.last),
^
include/uapi/linux/swab.h:31:12: note: in definition of macro '___constant_swab64'
(((__u64)(x) & (__u64)0xff00000000000000ULL) >> 56)))
^
>> include/uapi/linux/byteorder/big_endian.h:31:43: note: in expansion of macro '__swab64'
#define __cpu_to_le64(x) ((__force __le64)__swab64((x)))
^~~~~~~~
>> include/linux/byteorder/generic.h:86:21: note: in expansion of macro '__cpu_to_le64'
#define cpu_to_le64 __cpu_to_le64
^~~~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:16: note: in expansion of macro 'cpu_to_le64'
.virt_end = cpu_to_le64(mapping->iova.last),
^~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:41: error: 'struct interval_tree_node' has no member named 'last'
.virt_end = cpu_to_le64(mapping->iova.last),
^
include/uapi/linux/swab.h:132:12: note: in definition of macro '__swab64'
__fswab64(x))
^
>> include/linux/byteorder/generic.h:86:21: note: in expansion of macro '__cpu_to_le64'
#define cpu_to_le64 __cpu_to_le64
^~~~~~~~~~~~~
drivers/iommu/virtio-iommu.c:403:16: note: in expansion of macro 'cpu_to_le64'
.virt_end = cpu_to_le64(mapping->iova.last),
^~~~~~~~~~~vim +403 drivers//iommu/virtio-iommu.c
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 379
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 380 /*
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 381 * viommu_replay_mappings - re-send MAP requests
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 382 *
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 383 * When reattaching a domain that was previously detached from all endpoints,
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 384 * mappings were deleted from the device. Re-create the mappings available in
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 385 * the internal tree.
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 386 */
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 387 static int viommu_replay_mappings(struct viommu_domain *vdomain)
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 388 {
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 389 int ret = 0;
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 390 unsigned long flags;
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 391 struct viommu_mapping *mapping;
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 392 struct interval_tree_node *node;
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 393 struct virtio_iommu_req_map map;
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 394
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 395 spin_lock_irqsave(&vdomain->mappings_lock, flags);
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 396 node = interval_tree_iter_first(&vdomain->mappings, 0, -1UL);
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 397 while (node) {
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 398 mapping = container_of(node, struct viommu_mapping, iova);
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 399 map = (struct virtio_iommu_req_map) {
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 400 .head.type = VIRTIO_IOMMU_T_MAP,
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 401 .domain = cpu_to_le32(vdomain->id),
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 402 .virt_start = cpu_to_le64(mapping->iova.start),
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 @403 .virt_end = cpu_to_le64(mapping->iova.last),
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 404 .phys_start = cpu_to_le64(mapping->paddr),
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 405 .flags = cpu_to_le32(mapping->flags),
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 406 };
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 407
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 408 ret = viommu_send_req_sync(vdomain->viommu, &map, sizeof(map));
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 409 if (ret)
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 410 break;
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 411
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 412 node = interval_tree_iter_next(node, 0, -1UL);
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 413 }
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 414 spin_unlock_irqrestore(&vdomain->mappings_lock, flags);
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 415
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 416 return ret;
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 417 }
edcd69ab9a323b Jean-Philippe Brucker 2019-01-15 418 :::::: The code at line 403 was first introduced by commit
:::::: edcd69ab9a323b7ac7a86e1c44b6c9c46598391f iommu: Add virtio-iommu driver
:::::: TO: Jean-Philippe Brucker <[email protected]> :::::: CC: Michael S. Tsirkin <[email protected]>
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
Re: [PATCH 09/11] lib/interval-tree: convert interval_tree to half closed intervals
In reply to Davidlohr BuesoAm 03.10.19 um 22:18 schrieb Davidlohr Bueso:
Quoted 5 lines
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 perhapsradeon_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.
Quoted 402 lines
Cc "Christian König" <[email protected]>Cc Alex Deucher <[email protected]>Cc David Airlie <[email protected]>Cc Daniel Vetter <[email protected]>Cc Doug Ledford <[email protected]>Cc Joerg Roedel <[email protected]>Cc "Jérôme Glisse" <[email protected]>Signed-off-by Davidlohr Bueso <[email protected]>--- 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(-)drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c +3
-9@@ -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);drivers/gpu/drm/i915/gem/i915_gem_userptr.c +1
-4@@ -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;drivers/gpu/drm/radeon/radeon_mn.c +4
-7@@ -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);drivers/gpu/drm/radeon/radeon_trace.h +1
-1@@ -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",drivers/gpu/drm/radeon/radeon_vm.c +13
-13@@ -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); }drivers/infiniband/core/umem_odp.c +7
-14@@ -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; }drivers/iommu/virtio-iommu.c +3
-3@@ -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);include/linux/interval_tree.h +1
-1@@ -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; };include/rdma/ib_umem_odp.h +2
-2@@ -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);lib/interval_tree.c +1
-1@@ -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)
lib/interval_tree.c line 15
Quoted 10 lines
lib/interval_tree.c +2
-2-#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);
_______________________________________________
dri-devel mailing list
[email protected]
https://lists.freedesktop.org/mailman/listinfo/dri-devel
Koenig, Christian
maintainerRe: [PATCH 09/11] lib/interval-tree: convert interval_tree to half closed intervals
Am 04.10.19 um 08:57 schrieb Christian König:
Quoted 7 lines
Am 03.10.19 um 22:18 schrieb Davidlohr Bueso:
Quoted 5 lines
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 perhapsradeon_vm_bo_set_addr(), but semantics have been tried to be left untouched.
Quoted 7 lines
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
0x0if 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.
Quoted 414 lines
Regards,
Christian.Quoted 410 lines
Cc "Christian König" <[email protected]>Cc Alex Deucher <[email protected]>Cc David Airlie <[email protected]>Cc Daniel Vetter <[email protected]>Cc Doug Ledford <[email protected]>Cc Joerg Roedel <[email protected]>Cc "Jérôme Glisse" <[email protected]>Signed-off-by Davidlohr Bueso <[email protected]>---
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(-)drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c +0
-0@@ -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
*/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c +0
-0@@ -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 @@ structamdgpu_mn*amdgpu_mn_get(structamdgpu_device*adev,
*/
intamdgpu_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); structamdgpu_device*adev =amdgpu_ttm_adev(bo->tbo.bdev); enumamdgpu_mn_typetype =
bo->kfd_bo?AMDGPU_MN_TYPE_HSA:AMDGPU_MN_TYPE_GFX;drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c +1
-1@@ -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);drivers/gpu/drm/i915/gem/i915_gem_userptr.c +0
-0@@ -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) {drivers/gpu/drm/i915/gem/i915_gem_userptr.c +1
-1@@ -275,7 +272,7 @@ i915_gem_userptr_init__mmu_notifier(structdrm_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;drivers/gpu/drm/radeon/radeon_mn.c +1
-1@@ -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.
*/drivers/gpu/drm/radeon/radeon_mn.c +1
-1@@ -174,7 +171,7 @@ static const struct mmu_notifier_opsradeon_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;drivers/gpu/drm/radeon/radeon_mn.c +1
-1@@ -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);drivers/gpu/drm/radeon/radeon_trace.h +0
-0@@ -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",drivers/gpu/drm/radeon/radeon_vm.c +1
-1@@ -329,7 +329,7 @@ struct radeon_bo_va *radeon_vm_bo_add(structradeon_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);drivers/gpu/drm/radeon/radeon_vm.c +1
-1@@ -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;
gotoerror_unreserve;
}
}
- if (bo_va->it.start||bo_va->it.last) {
+ if (bo_va->it.start||bo_va->it.end) {
/* add a clone of thebo_vato clear the old address */ structradeon_bo_va*tmp;
tmp =kzalloc(sizeof(struct radeon_bo_va), GFP_KERNEL);drivers/gpu/drm/radeon/radeon_vm.c +3
-3@@ -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);drivers/gpu/drm/radeon/radeon_vm.c +1
-0@@ -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) entriesor 2k dwords (whatever is smaller) */
drivers/gpu/drm/radeon/radeon_vm.c +2
-2@@ -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);drivers/gpu/drm/radeon/radeon_vm.c +2
-2@@ -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(structradeon_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);
}drivers/infiniband/core/umem_odp.c +4
-4@@ -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)drivers/infiniband/core/umem_odp.c +2
-1@@ -777,12 +770,12 @@ int rbt_ib_umem_for_each_in_range(structrb_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;}
drivers/iommu/virtio-iommu.c +2
-2@@ -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(structviommu_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_tviommu_del_mappings(structviommu_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);include/linux/interval_tree.h +0
-0@@ -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 --gita/include/rdma/ib_umem_odp.hb/include/rdma/ib_umem_odp.hindex253df1a1fa54..d0ae7aa2139b100644include/rdma/ib_umem_odp.h +0
-0@@ -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 ODPumem. */
static inline unsigned longib_umem_end(struct ib_umem_odp *umem_odp){
- returnumem_odp->interval_tree.last+ 1;
+ returnumem_odp->interval_tree.end;
}
static inlinesize_tib_umem_odp_num_pages(struct ib_umem_odp *umem_odp)include/rdma/ib_umem_odp.h +1
-0@@ -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);lib/interval_tree.c +1
-1@@ -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)
Quoted 9 lines
lib/interval_tree.c line 15
Quoted 8 lines
lib/interval_tree.c +2
-2-#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);
_______________________________________________
dri-devel mailing list
[email protected]
https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH 09/11] lib/interval-tree: convert interval_tree to half closed intervals
Quoted 13 lines · Christian
Am 04.10.19 um 08:57 schrieb Christian König:
Quoted 12 lines
Am 03.10.19 um 22:18 schrieb Davidlohr Bueso:
Quoted 5 lines
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 perhapsradeon_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.
Quoted 6 lines
Quoted 2 lines
If you make this a closed interval then the end would wrap around to
0x0if 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.
Quoted 2 lines
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 10/11 lib: drop interval_tree_generic.h
In reply to Davidlohr BuesoNow that we have the semi-open equivalent, interval_tree_gen.h, and all users updated, we can do without this header file.
--- include/linux/interval_tree_generic.h | 187 ---------------------------------- 1 file changed, 187 deletions(-) delete mode 100644 include/linux/interval_tree_generic.h
include/linux/interval_tree_generic.h deleted +0 -187
@@ -1,187 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0-or-later */ -/* -Interval Trees -(C) 2012 Michel Lespinasse <[email protected]> - - -include/linux/interval_tree_generic.h -*/ - -#include <linux/rbtree_augmented.h> - -/* -* Template for implementing interval trees -* -* ITSTRUCT: struct type of the interval tree nodes -* ITRB: name of struct rb_node field within ITSTRUCT -* ITTYPE: type of the interval endpoints -* ITSUBTREE: name of ITTYPE field within ITSTRUCT holding last-in-subtree -* ITSTART(n): start endpoint of ITSTRUCT node n -* ITLAST(n): last endpoint of ITSTRUCT node n -* ITSTATIC: 'static' or empty -* ITPREFIX: prefix to use for the inline tree definitions -* -* Note - before using this, please consider if generic version -* (interval_tree.h) would work for you... -*/ - -#define INTERVAL_TREE_DEFINE (ITSTRUCT ,ITRB ,ITTYPE ,ITSUBTREE , \ -ITSTART ,ITLAST ,ITSTATIC ,ITPREFIX ) \ - \ -/* Callbacks for augmented rbtree insert and remove */ \ - \ -RB_DECLARE_CALLBACKS_MAX(static, ITPREFIX ## _augment, \ - ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, ITLAST) \ - \ -/* Insert / remove interval nodes from the tree */ \ - \ -ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, \ -struct rb_root_cached *root) \ -{ \ -struct rb_node **link = &root->rb_root.rb_node, *rb_parent =NULL ; \ -ITTYPE start =ITSTART (node), last =ITLAST (node); \ -ITSTRUCT *parent; \ -bool leftmost = true; \ - \ -while (*link) { \ - rb_parent = *link; \ - parent =rb_entry (rb_parent,ITSTRUCT ,ITRB ); \ -if (parent->ITSUBTREE < last) \ - parent->ITSUBTREE = last; \ -if (start <ITSTART (parent)) \ - link = &parent->ITRB.rb_left; \ -else { \ - link = &parent->ITRB.rb_right; \ - leftmost = false; \ - } \ - } \ - \ - node->ITSUBTREE = last; \ -rb_link_node (&node->ITRB, rb_parent, link); \ -rb_insert_augmented_cached (&node->ITRB, root, \ - leftmost, &ITPREFIX ## _augment); \ -} \ - \ -ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, \ -struct rb_root_cached *root) \ -{ \ - rb_erase_augmented_cached(&node->ITRB, root, &ITPREFIX ## _augment); \ -} \ - \ -/* \ -* Iterate over intervals intersecting [start;last] \ -* \ -* Note that a node's interval intersects [start;last] iff: \ -* Cond1: ITSTART(node) <= last \ -* and \ -* Cond2: start <= ITLAST(node) \ -*/ \ - \ -static ITSTRUCT * \ -ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ -{ \ -while (true) { \ -/* \ -* Loop invariant: start <= node->ITSUBTREE \ -* (Cond2 is satisfied by one of the subtree nodes) \ -*/ \ -if (node->ITRB.rb_left) { \ -ITSTRUCT *left =rb_entry (node->ITRB.rb_left, \ -ITSTRUCT ,ITRB ); \ -if (start <= left->ITSUBTREE) { \ -/* \ -* Some nodes in left subtree satisfy Cond2. \ -* Iterate to find the leftmost such node N. \ -* If it also satisfies Cond1, that's the \ -* match we are looking for. Otherwise, there \ -* is no matching interval as nodes to the \ -* right of N can't satisfy Cond1 either. \ -*/ \ - node = left; \ -continue ; \ - } \ - } \ -if (ITSTART (node) <= last) {/* Cond1 */ \ -if (start <=ITLAST (node))/* Cond2 */ \ -return node;/* node is leftmost match */ \ -if (node->ITRB.rb_right) { \ - node =rb_entry (node->ITRB.rb_right, \ -ITSTRUCT ,ITRB ); \ -if (start <= node->ITSUBTREE) \ -continue ; \ - } \ - } \ -return NULL ;/* No match */ \ - } \ -} \ - \ -ITSTATIC ITSTRUCT * \ -ITPREFIX ## _iter_first(struct rb_root_cached *root, \ -ITTYPE start,ITTYPE last) \ -{ \ -ITSTRUCT *node, *leftmost; \ - \ -if (!root->rb_root.rb_node) \ -return NULL ; \ - \ -/* \ -* Fastpath range intersection/overlap between A: [a0, a1] and \ -* B: [b0, b1] is given by: \ -* \ -* a0 <= b1 && b0 <= a1 \ -* \ -* ... where A holds the lock range and B holds the smallest \ -* 'start' and largest 'last' in the tree. For the later, we \ -* rely on the root node, which by augmented interval tree \ -* property, holds the largest value in its last-in-subtree. \ -* This allows mitigating some of the tree walk overhead for \ -* for non-intersecting ranges, maintained and consulted in O(1). \ -*/ \ - node =rb_entry (root->rb_root.rb_node,ITSTRUCT ,ITRB ); \ -if (node->ITSUBTREE < start) \ -return NULL ; \ - \ - leftmost =rb_entry (root->rb_leftmost,ITSTRUCT ,ITRB ); \ -if (ITSTART (leftmost) > last) \ -return NULL ; \ - \ - return ITPREFIX ## _subtree_search(node, start, last); \ -} \ - \ -ITSTATIC ITSTRUCT * \ -ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ -{ \ -struct rb_node *rb = node->ITRB.rb_right, *prev; \ - \ -while (true) { \ -/* \ -* Loop invariants: \ -* Cond1: ITSTART(node) <= last \ -* rb == node->ITRB.rb_right \ -* \ -* First, search right subtree if suitable \ -*/ \ -if (rb) { \ -ITSTRUCT *right =rb_entry (rb,ITSTRUCT ,ITRB ); \ -if (start <= right->ITSUBTREE) \ - return ITPREFIX ## _subtree_search(right, \ - start, last); \ - } \ - \ -/* Move up the tree until we come from a node's left child */ \ -do { \ - rb =rb_parent (&node->ITRB); \ -if (!rb) \ -return NULL ; \ - prev = &node->ITRB; \ - node =rb_entry (rb,ITSTRUCT ,ITRB ); \ - rb = node->ITRB.rb_right; \ - }while (prev == rb); \ - \ -/* Check if the node intersects [start;last] */ \ -if (last <ITSTART (node))/* !Cond1 */ \ -return NULL ; \ -else if (start <=ITLAST (node))/* Cond2 */ \ -return node; \ - } \ -}
Signature · 1 line
2.16.4
PATCH 11/11 x86/mm, pat: convert pat tree to generic interval tree
In reply to Davidlohr BuesoWith some considerations, the custom pat_rbtree implementation can be simplified to use most of the generic interval_tree machinery.
o The tree inorder traversal can slightly differ when there are key ('start') collisions in the tree due to one going left and another right. This, however, only affects the output of debugfs' pat_memtype_list file.
o Generic interval trees are now semi open [a,b), which suits well with what pat wants.
o Erasing logic must remain untouched as well.
In order for the types to remain u64, the 'memtype_interval' calls are introduced, as opposed to simply using struct interval_tree.
In addition, pat tree might potentially also benefit by the fast overlap detection for the insertion case when looking up the first overlapping node in the tree.
Finally, I've tested this on various servers, via sanity warnings, running side by side with the current version and so far see no differences in the returned pointer node when doing memtype_rb_lowest_match() lookups.
--- arch/x86/mm/pat.c | 22 +++---- arch/x86/mm/pat_rbtree.c | 151 ++++++++++------------------------------------- 2 files changed, 43 insertions(+), 130 deletions(-)
arch/x86/mm/pat.c +11 -11
@@ -482,8 +482,8 @@ static int reserve_ram_pages_type(u64 start, u64 end, page =pfn_to_page (pfn); type =get_page_memtype (page);if (type != _PAGE_CACHE_MODE_WB) { -pr_info ("x86/PAT: reserve_ram_pages_type failed [mem %#010Lx-%#010Lx], track 0x%x, req 0x%x\n" , - start, end -1 , type, req_type); +pr_info ("x86/PAT: reserve_ram_pages_type failed [mem %#010Lx-%#010Lx), track 0x%x, req 0x%x\n" , + start, end, type, req_type);if (new_type) *new_type = type;
@@ -553,8 +553,8 @@ int reserve_memtype(u64 start, u64 end, enum page_cache_mode req_type, start =sanitize_phys (start); end =sanitize_phys (end);if (start >= end) { -WARN (1 ,"%s failed: [mem %#010Lx-%#010Lx], req %s\n" , __func__, - start, end -1 ,cattr_name (req_type)); +WARN (1 ,"%s failed: [mem %#010Lx-%#010Lx), req %s\n" , __func__, + start, end,cattr_name (req_type));return -EINVAL ; }
@@ -605,8 +605,8 @@ int reserve_memtype(u64 start, u64 end, enum page_cache_mode req_type, err =rbt_memtype_check_insert (new, new_type);if (err) { -pr_info ("x86/PAT: reserve_memtype failed [mem %#010Lx-%#010Lx], track %s, req %s\n" , - start, end -1 , +pr_info ("x86/PAT: reserve_memtype failed [mem %#010Lx-%#010Lx), track %s, req %s\n" , + start, end,cattr_name (new->type),cattr_name (req_type));kfree (new);spin_unlock (&memtype_lock);
@@ -616,8 +616,8 @@ int reserve_memtype(u64 start, u64 end, enum page_cache_mode req_type,spin_unlock (&memtype_lock); -dprintk ("reserve_memtype added [mem %#010Lx-%#010Lx], track %s, req %s, ret %s\n" , - start, end -1 ,cattr_name (new->type),cattr_name (req_type), +dprintk ("reserve_memtype added [mem %#010Lx-%#010Lx), track %s, req %s, ret %s\n" , + start, end,cattr_name (new->type),cattr_name (req_type), new_type ?cattr_name (*new_type) :"-" );return err;
@@ -654,14 +654,14 @@ int free_memtype(u64 start, u64 end)spin_unlock (&memtype_lock);if (IS_ERR (entry)) { -pr_info ("x86/PAT: %s:%d freeing invalid memtype [mem %#010Lx-%#010Lx]\n" , - current->comm, current->pid, start, end -1 ); +pr_info ("x86/PAT: %s:%d freeing invalid memtype [mem %#010Lx-%#010Lx)\n" , + current->comm, current->pid, start, end);return -EINVAL ; }kfree (entry); -dprintk ("free_memtype request [mem %#010Lx-%#010Lx]\n" , start, end -1 ); +dprintk ("free_memtype request [mem %#010Lx-%#010Lx)\n" , start, end);return 0 ; }
arch/x86/mm/pat_rbtree.c +32 -119
244 lines not on this page · raw message
Signature · 1 line
2.16.4
Re: [PATCH 11/11] x86/mm, pat: convert pat tree to generic interval tree
Quoted 29 lines · Davidlohr Bueso
With some considerations, the custom
pat_rbtreeimplementation can be simplified to use most of the genericinterval_treemachinery.o The tree inorder traversal can slightly differ when there are key ('start') collisions in the tree due to one going left and another right. This, however, only affects the output of debugfs'
pat_memtype_listfile.o Generic interval trees are now semi open [a,b), which suits well with what pat wants.
o Erasing logic must remain untouched as well.
In order for the types to remain u64, the '
memtype_interval' calls are introduced, as opposed to simply using structinterval_tree.In addition, pat tree might potentially also benefit by the fast overlap detection for the insertion case when looking up the first overlapping node in the tree.
Finally, I've tested this on various servers, via sanity warnings, running side by side with the current version and so far see no differences in the returned pointer node when doing
memtype_rb_lowest_match()lookups.Cc Peter Zijlstra <[email protected]>Cc Thomas Gleixner <[email protected]>Cc Ingo Molnar <[email protected]>Cc Borislav Petkov <[email protected]>Signed-off-by Davidlohr Bueso <[email protected]>
Quoted 4 lines
--- arch/x86/mm/pat.c | 22 +++---- arch/x86/mm/pat_rbtree.c | 151 ++++++++++------------------------------------- 2 files changed, 43 insertions(+), 130 deletions(-)
I suppose this will be carried in -mm?
If so and if this patch is regression free, then:
Thanks,
Ingo
_______________________________________________
dri-devel mailing list
[email protected]
https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH 11/11] x86/mm, pat: convert pat tree to generic interval tree
Quoted 1 line · Ingo Molnar
I suppose this will be carried in -mm?
I've just sent out a new patchset for -tip that only modified the pat tree. It seems that this series will at least take some more time due to the mmu_notifier rework being done - and there was some worries about the corner case details. I think it makes sense to just port the pat tree to the current interval tree machineary and just be done with all this. Any future versions of this series would require a trivial two liner for pat.
Thanks,
Davidlohr
Matthew Wilcox
reviewerQuoted 2 lines · Davidlohr Bueso
It has been discussed[1,2] that almost all users of interval trees would better be served if the intervals were actually not [a,b], but instead [a, b). This
So how does a user represent a range from ULONG_MAX to ULONG_MAX now?
I think the problem is that large parts of the kernel just don't consider integer overflow. Because we write in C, it's natural to write:
for (i = start; i < end; i++)
and just assume that we never need to hit ULONG_MAX or UINT_MAX. If we're storing addresses, that's generally true -- most architectures don't allow addresses in the -PAGE_SIZE to ULONG_MAX range (or they'd have trouble with PTR_ERR). If you're looking at file sizes, that's not true on 32-bit machines, and we've definitely seen filesystem bugs with files nudging up on 16TB (on 32 bit with 4k page size). Or block driver bugs with similarly sized block devices.
So, yeah, easier to use. But damning corner cases.
Quoted 5 lines · Matthew Wilcox
Quoted 2 lines · Davidlohr Bueso
It has been discussed[1,2] that almost all users of interval trees would better be served if the intervals were actually not [a,b], but instead [a, b). This
So how does a user represent a range from
ULONG_MAXtoULONG_MAXnow?
I would assume that any such lookups would be stab queries (anon/vma interval tree). So both anon and files. And yeah, I blissfully ignored any overflow scenarios. This should at least be documented.
Quoted 7 lines
I think the problem is that large parts of the kernel just don't consider integer overflow. Because we write in C, it's natural to write:
for (i = start; i < end; i++)and just assume that we never need to hit
ULONG_MAXorUINT_MAX.
Similarly, I did not adjust queries such as 0 to ULONG_MAX, which are actually real, then again any intersecting ranges will most likely not even be close to end.
Quoted 8 lines
If we're storing addresses, that's generally true -- most architectures don't allow addresses in the -PAGE_SIZE to
ULONG_MAXrange (or they'd have trouble withPTR_ERR). If you're looking at file sizes, that's not true on 32-bit machines, and we've definitely seen filesystem bugs with files nudging up on 16TB (on 32 bit with 4k page size). Or block driver bugs with similarly sized block devices.So, yeah, easier to use. But damning corner cases.
I agree.
Thanks,
Davidlohr
Quoted 19 lines · Matthew Wilcox
Quoted 2 lines · Davidlohr Bueso
It has been discussed[1,2] that almost all users of interval trees would better be served if the intervals were actually not [a,b], but instead [a, b). This
So how does a user represent a range from
ULONG_MAXtoULONG_MAXnow?I think the problem is that large parts of the kernel just don't consider integer overflow. Because we write in C, it's natural to write:
for (i = start; i < end; i++)and just assume that we never need to hit
ULONG_MAXorUINT_MAX. If we're storing addresses, that's generally true -- most architectures don't allow addresses in the -PAGE_SIZE toULONG_MAXrange (or they'd have trouble withPTR_ERR). If you're looking at file sizes, that's not true on 32-bit machines, and we've definitely seen filesystem bugs with files nudging up on 16TB (on 32 bit with 4k page size). Or block driver bugs with similarly sized block devices.
Quoted 1 line
So, yeah, easier to use. But damning corner cases.
Yeah, I wanted to ask - is the case where pgoff == ULONG_MAX (i.e., last block of a file that is exactly 16TB) currently supported on 32-bit archs ?
I have no idea if I am supposed to care about this or not...
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
Quoted 29 lines · Davidlohr Bueso
Hi,
It has been discussed[1,2] that almost all users of interval trees would better be served if the intervals were actually not [a,b], but instead [a, b). This series attempts to convert all callers by way of transitioning from using "
interval_tree_generic.h" to "interval_tree_gen.h". Once all users are converted, we remove the former.Patch 1: adds a call that will make patch 8 easier to review by introducing stab
queries for the vma interval tree.Patch 2: adds the new
interval_tree_gen.hwhich is the same as the old one but
uses [a,b) intervals.Patch 3-9: converts, in baby steps (as much as possible), each interval tree to
the new [a,b) one. It is done this way also to maintain bisectability. Most conversions are pretty straightforward, however, there are some creative ways in which some callers use the interval 'end' when going through intersecting ranges within a tree. Ie: patch 3, 6 and 9.Patch 10: deletes the
interval_tree_generic.hheader; there are no longer any users.Patch 11: finally simplifies x86 pat tree to use the new interval tree machinery.
This has been lightly tested, and certainly not on driver paths that do non trivial conversions. Also needs more eyeballs as conversions can be easily missed (even when I've tried mitigating this by renaming the endpoint from 'last' to 'end' in each corresponding structure).
Quoted 8 lines
Because this touches a lot of drivers, I'm Cc'ing the whole thing to a couple of relevant lists (mm, dri, rdma); sorry if you consider this spam.
Applies on top of today's linux-next tree. Please consider for v5.5.
Thanks!
[1] https://lore.kernel.org/lkml/CANN689HVDJXKEwB80yPAVwvRwnV4HfiucQVAho=dupKM_iKozw@mail.gmail.com/
Hurm, this is not entirely accurate. Most users do actually want overlapping and multiple ranges. I just studied this extensively:
radeon_mn actually wants overlapping but seems to mis-understand the interval_tree API and actively tries hard to prevent overlapping at great cost and complexity. I have a patch to delete all of this and just be overlapping.
amdgpu_mn copied the wrongness from radeon_mn
All the DRM drivers are basically the same here, tracking userspace controlled VAs, so overlapping is essential
hfi1/mmu_rb definitely needs overlapping as it is dealing with userspace VA ranges under control of userspace. As do the other infiniband users.
vhost probably doesn't overlap in the normal case, but again userspace could trigger overlap in some pathalogical case.
The [start,last] allows the interval to cover up to ULONG_MAX. I don't know if this is needed however. Many users are using userspace VAs here. Is there any kernel configuration where ULONG_MAX is a valid userspace pointer? Ie 32 bit 4G userspace? I don't know.
Many users seemed to have bugs where they were taking a userspace controlled start + length and converting them into a start/end for interval tree without overflow protection (woops)
Also I have a series already cooking to delete several of these interval tree users, which will terribly conflict with this :\
Is it really necessary to make such churn for such a tiny API change?
Jason
Quoted 64 lines · Jason Gunthorpe
Quoted 29 lines · Davidlohr Bueso
Hi,
It has been discussed[1,2] that almost all users of interval trees would better be served if the intervals were actually not [a,b], but instead [a, b). This series attempts to convert all callers by way of transitioning from using "
interval_tree_generic.h" to "interval_tree_gen.h". Once all users are converted, we remove the former.Patch 1: adds a call that will make patch 8 easier to review by introducing stab
queries for the vma interval tree.Patch 2: adds the new
interval_tree_gen.hwhich is the same as the old one but
uses [a,b) intervals.Patch 3-9: converts, in baby steps (as much as possible), each interval tree to
the new [a,b) one. It is done this way also to maintain bisectability. Most conversions are pretty straightforward, however, there are some creative ways in which some callers use the interval 'end' when going through intersecting ranges within a tree. Ie: patch 3, 6 and 9.Patch 10: deletes the
interval_tree_generic.hheader; there are no longer any users.Patch 11: finally simplifies x86 pat tree to use the new interval tree machinery.
This has been lightly tested, and certainly not on driver paths that do non trivial conversions. Also needs more eyeballs as conversions can be easily missed (even when I've tried mitigating this by renaming the endpoint from 'last' to 'end' in each corresponding structure).
Quoted 8 lines
Because this touches a lot of drivers, I'm Cc'ing the whole thing to a couple of relevant lists (mm, dri, rdma); sorry if you consider this spam.
Applies on top of today's linux-next tree. Please consider for v5.5.
Thanks!
[1] https://lore.kernel.org/lkml/CANN689HVDJXKEwB80yPAVwvRwnV4HfiucQVAho=dupKM_iKozw@mail.gmail.com/
Hurm, this is not entirely accurate. Most users do actually want overlapping and multiple ranges. I just studied this extensively:
radeon_mnactually wants overlapping but seems to mis-understand theinterval_treeAPI and actively tries hard to prevent overlapping at great cost and complexity. I have a patch to delete all of this and just be overlapping.
amdgpu_mncopied the wrongness fromradeon_mnAll the DRM drivers are basically the same here, tracking userspace controlled VAs, so overlapping is essential
hfi1/mmu_rb definitely needs overlapping as it is dealing with userspace VA ranges under control of userspace. As do the other infiniband users.
vhost probably doesn't overlap in the normal case, but again userspace could trigger overlap in some pathalogical case.
The [start,last] allows the interval to cover up to
ULONG_MAX. I don't know if this is needed however. Many users are using userspace VAs here. Is there any kernel configuration whereULONG_MAXis a valid userspace pointer? Ie 32 bit 4G userspace? I don't know.
Quoted 6 lines
Many users seemed to have bugs where they were taking a userspace controlled start + length and converting them into a start/end for interval tree without overflow protection (woops)
Also I have a series already cooking to delete several of these interval tree users, which will terribly conflict with this :\
I have no problem redoing after your changes; if it's worth it at all.
Quoted 2 lines
Is it really necessary to make such churn for such a tiny API change?
I agree, and was kind of expecting this. In general the diffstat ended up being larger than I initially hoped for. Maybe after your removals I can look into this again.
Thanks,
Davidlohr
Hi Jason,
Quoted 2 lines · Jason Gunthorpe
Hurm, this is not entirely accurate. Most users do actually want overlapping and multiple ranges. I just studied this extensively:
(Just curious, are you the person we discussed this with after the Maple Tree talk at LPC 2019 ?)
I think we have two separate API problems there:
- overlapping vs non-overlapping intervals (the interval tree API supports overlapping intervals, but some users are confused about this)
- closed vs half-open interval definitions
It looks like you have been looking mostly at the first issue, which I expect could simplify several interval tree users considerably, while Davidlohr is addressing the second issue here.
Quoted 5 lines
radeon_mnactually wants overlapping but seems to mis-understand theinterval_treeAPI and actively tries hard to prevent overlapping at great cost and complexity. I have a patch to delete all of this and just be overlapping.
Quoted 8 lines
amdgpu_mncopied the wrongness fromradeon_mnAll the DRM drivers are basically the same here, tracking userspace controlled VAs, so overlapping is essential
hfi1/mmu_rb definitely needs overlapping as it is dealing with userspace VA ranges under control of userspace. As do the other infiniband users.
Do you have a handle on what usnic is doing with its intervals ? usnic_uiom_insert_interval() has some complicated logic to avoid having overlapping intervals, which is very confusing to me.
Quoted 8 lines
vhost probably doesn't overlap in the normal case, but again userspace could trigger overlap in some pathalogical case.
The [start,last] allows the interval to cover up to
ULONG_MAX. I don't know if this is needed however. Many users are using userspace VAs here. Is there any kernel configuration whereULONG_MAXis a valid userspace pointer? Ie 32 bit 4G userspace? I don't know.
Quoted 8 lines
Many users seemed to have bugs where they were taking a userspace controlled start + length and converting them into a start/end for interval tree without overflow protection (woops)
Also I have a series already cooking to delete several of these interval tree users, which will terribly conflict with this :\
Is it really necessary to make such churn for such a tiny API change?
My take is that this (Davidlohr's) patch series does not necessarily need to be applied all at once - we could get the first change in (adding the interval_tree_gen.h header), and convert the first few users, without getting them all at once, as long as we have a plan for finishing the work. So, if you have cleanups in progress in some of the files, just tell us which ones and we can leave them out from the first pass.
Thanks,
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
Matthew Wilcox
reviewerQuoted 7 lines · Michel Lespinasse
My take is that this (Davidlohr's) patch series does not necessarily need to be applied all at once - we could get the first change in (adding the
interval_tree_gen.hheader), and convert the first few users, without getting them all at once, as long as we have a plan for finishing the work. So, if you have cleanups in progress in some of the files, just tell us which ones and we can leave them out from the first pass.
Since we have users which do need to use the full ULONG_MAX range (as pointed out by Christian Koenig), I don't think adding a second implementation which is half-open is a good idea. It'll only lead to confusion.
Quoted 9 lines · Matthew Wilcox
Quoted 7 lines · Michel Lespinasse
My take is that this (Davidlohr's) patch series does not necessarily need to be applied all at once - we could get the first change in (adding the
interval_tree_gen.hheader), and convert the first few users, without getting them all at once, as long as we have a plan for finishing the work. So, if you have cleanups in progress in some of the files, just tell us which ones and we can leave them out from the first pass.
Quoted 4 lines
Since we have users which do need to use the full
ULONG_MAXrange (as pointed out by Christian Koenig), I don't think adding a second implementation which is half-open is a good idea. It'll only lead to confusion.
Right, we should not have two implementations.
Thanks,
Davidlohr
Quoted 8 lines · Michel Lespinasse
Hi Jason,
Quoted 2 lines · Jason Gunthorpe
Hurm, this is not entirely accurate. Most users do actually want overlapping and multiple ranges. I just studied this extensively:
(Just curious, are you the person we discussed this with after the Maple Tree talk at LPC 2019 ?)
Possibly!
Quoted 4 lines
I think we have two separate API problems there:
- overlapping vs non-overlapping intervals (the interval tree API supports overlapping intervals, but some users are confused about this)
I think we just have a bunch of confused drivers, ie the two drm drivers sure look confused to me.
Quoted 1 line
- closed vs half-open interval definitions
I'm not sure why this is a big problem..
We may actually just have bugs in handling the '-1' as it is supposed to be written as start + (size-1) so that start + size == ULONG_MAX+1 works properly.
Quoted 7 lines
Quoted 3 lines
hfi1/mmu_rb definitely needs overlapping as it is dealing with userspace VA ranges under control of userspace. As do the other infiniband users.
Do you have a handle on what usnic is doing with its intervals ?
usnic_uiom_insert_interval()has some complicated logic to avoid having overlapping intervals, which is very confusing to me.
I don't know why it is so complicated, but I can say that it is storing userspace VA's in that tree.
I have some feeling this driver is trying to use the IOMMU to create a mirror of the userspace VA
Userspace can request the HW be able to access any set of overlapping regions and so the driver must intersect all the ranges and compute a list of VA pages to IOMMU map. Just guessing.
Jason