Skip to contentSkip to conversation

lib/interval-tree: move to half closed intervals

PATCH NAK Davidlohr Bueso 9 participants 40 messages Oct 3, 2019 – Oct 21, 2019

Subsystems (28)
lore
Share & tools
lore
#0 lore raw

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
#1 lore raw

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
index ae857f41f68d..85bb69f1decb 100644
@@ -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
index 6d89db7895d1..b04384406c0f 100644
@@ -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
index 65de1bd6a760..8abe26b8e29d 100644
@@ -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
index a82b3eaa5398..c5f8aab749c1 100644
@@ -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
index 6bf81f931de3..f24c035defb7 100644
@@ -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
index cc292273e6ba..53f9784d917d 100644
@@ -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
index 94d38a39d72e..6a70dbe0b4b2 100644
@@ -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
index ef37c85423a5..1a6b133ca66d 100644
@@ -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
index 0a1b4b484ac5..24b66416fde0 100644
@@ -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
index 7ef849da8278..79934fd00146 100644
@@ -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
#2 lore raw

PATCH 2/11 lib/interval-tree: add an equivalent tree with [a,b) intervals

In reply to Davidlohr Bueso

While 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
new file mode 100644
index 000000000000..5d446c0bd89a
@@ -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
Reviewed-by on v1 2/11
#3 lore raw

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.
#4 lore raw

PATCH 3/11 drm/amdgpu: convert amdgpu_vm_it to half closed intervals

In reply to Davidlohr Bueso

The 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.

Cc Jerome Glisse <[email protected]>
Cc Alex Deucher <[email protected]>
Cc "Christian König" <[email protected]>
Cc Daniel Vetter <[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
index 49b767b7238f..290bfe820890 100644
@@ -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
index 7e99f6c58c48..60b73bc4d11a 100644
@@ -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
index 8227ebd0f511..c5b0e88d019c 100644
@@ -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
index b2c364b8695f..8094dd0b0332 100644
@@ -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
index b70b3c45bb29..d6511bf446df 100644
@@ -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
maintainer NAK
#5 lore raw

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_vm interval 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]>
---
  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
index 49b767b7238f..290bfe820890 100644
@@ -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
index 7e99f6c58c48..60b73bc4d11a 100644
@@ -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
index 8227ebd0f511..c5b0e88d019c 100644
@@ -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
index b2c364b8695f..8094dd0b0332 100644
@@ -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
index b70b3c45bb29..d6511bf446df 100644
@@ -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
index a2c797e34a29..2f618017617e 100644
@@ -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

#6 lore raw

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_vm interval 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.
#7 lore raw

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_vm interval 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,

#8 lore raw

PATCH 4/11 drm: convert drm_mm_interval_tree to half closed intervals

In reply to Davidlohr Bueso

The 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
index 4581c5387372..17feb00e7d80 100644
@@ -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
index 3e6f4a65d356..af40d3bfa065 100644
@@ -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
index 388f9844f4ba..f34f975c1570 100644
@@ -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
index 2c3bbb43c7d1..0eda6180e1ef 100644
@@ -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
#9 lore raw

PATCH 5/11 IB/hfi1: convert __mmu_int_rb to half closed intervals

In reply to Davidlohr Bueso

The __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.

Cc Mike Marciniszyn <[email protected]>
Cc Dennis Dalessandro <[email protected]>
Cc Doug Ledford <[email protected]>
---
 drivers/infiniband/hw/hfi1/mmu_rb.c | 15 +++++++--------
 1 file changed, 7 insertions(+), 8 deletions(-)
drivers/infiniband/hw/hfi1/mmu_rb.c +7 -8
index 14d2a90964c3..fb6382b2d44e 100644
@@ -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
Reviewed-by on v1 5/11
#10 lore raw

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
index 14d2a90964c3..fb6382b2d44e 100644
@@ -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.
#11 lore raw

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
index 14d2a90964c3..fb6382b2d44e 100644
@@ -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 -1
 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.

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.

Thanks,
Davidlohr

#12 lore raw

PATCH 6/11 IB,usnic: convert usnic_uiom_interval_tree to half closed intervals

In reply to Davidlohr Bueso

The 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.

Cc Christian Benvenuti <[email protected]>
Cc Nelson Escobar <[email protected]>
Cc Doug Ledford <[email protected]>
Cc Jason Gunthorpe <[email protected]>
---
 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
index 62e6ffa9ad78..14f607c398a8 100644
@@ -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
index d399523206c7..12c968447673 100644
@@ -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
index 1d7fc3226bca..496edc9758c1 100644
@@ -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
#13 lore raw

PATCH 7/11 vhost: convert vhost_umem_interval_tree to half closed intervals

In reply to Davidlohr Bueso

The 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
index 36ca2cf419bf..80c3cca24dc7 100644
@@ -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
index e9ed2722b633..bb36cb9ed5ec 100644
@@ -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
#14 lore raw

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
index e9ed2722b633..bb36cb9ed5ec 100644
@@ -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 -1
 
 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;

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.
#15 lore raw

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
index e9ed2722b633..bb36cb9ed5ec 100644
@@ -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 -1
 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;

Preferably also rename __subtree_last to __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

Reviewed-by on v1 7/11
#16 lore raw

Re: [PATCH 07/11] vhost: convert vhost_umem_interval_tree to half closed intervals

In reply to Davidlohr Bueso
Quoted 111 lines · Davidlohr Bueso

The 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
index 36ca2cf419bf..80c3cca24dc7 100644
@@ -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
index e9ed2722b633..bb36cb9ed5ec 100644
@@ -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 -1
 
  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;

_______________________________________________
Virtualization mailing list
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/virtualization

Reviewed-by on v1 7/11
#17 lore raw

Re: [PATCH 07/11] vhost: convert vhost_umem_interval_tree to half closed intervals

In reply to Davidlohr Bueso
Quoted 111 lines · Davidlohr Bueso

The 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
index 36ca2cf419bf..80c3cca24dc7 100644
@@ -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
index e9ed2722b633..bb36cb9ed5ec 100644
@@ -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 -1
 
  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;

_______________________________________________
dri-devel mailing list
[email protected]
https://lists.freedesktop.org/mailman/listinfo/dri-devel

#18 lore raw

PATCH 7/11 vhost: convert vhost_umem_interval_tree to half closed intervals

In reply to Davidlohr Bueso

The 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
index 36ca2cf419bf..80c3cca24dc7 100644
@@ -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
index e9ed2722b633..bb36cb9ed5ec 100644
@@ -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
#19 lore raw

PATCH 8/11 mm: convert vma_interval_tree to half closed intervals

In reply to 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 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
index 53f9784d917d..3bc06e1de40c 100644
@@ -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
index 11c75fb07584..1f8a7c122dd7 100644
@@ -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
index b1ca51a079f2..8f6978abf64a 100644
@@ -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
index 99b7ec318824..284c2a948d79 100644
@@ -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
index d9a23bb773bf..48ca7d1a06b5 100644
@@ -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
#20 lore raw

Re: [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.c

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;

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;
#21 lore raw

Re: [PATCH 08/11] mm: convert vma_interval_tree to half closed intervals

In reply to Davidlohr Bueso
Quoted 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 of vma_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.
#22 lore raw

PATCH 9/11 lib/interval-tree: convert interval_tree to half closed intervals

In reply to Davidlohr Bueso

The generic tree tree really wants [a, b) intervals, not fully closed. As such convert it to use the new interval_tree_gen.h. Most of the conversions are straightforward, with the exception of perhaps radeon_vm_bo_set_addr(), but semantics have been tried to be left untouched.

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]>
---
 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
index 31d4deb5d294..4bbaa9ffa570 100644
@@ -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
index 11b231c187c5..818ff6b33102 100644
@@ -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
index dbab9a3a969b..4810421dacc2 100644
@@ -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
index c93f3ab3c4e3..4324f3fc5d82 100644
@@ -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
index e0ad547786e8..b2a54aff21f4 100644
@@ -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
index f67a30fda1ed..9b7ac93223d6 100644
@@ -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
index 3ea9d7682999..771740981f43 100644
@@ -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
index 288c26f50732..f3d1ea9e4003 100644
@@ -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
index 253df1a1fa54..d0ae7aa2139b 100644
@@ -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
index 593ce56ece50..336ec5113a28 100644
@@ -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
#23 lore raw

Re: [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

maintainer NAK
#24 lore raw

Re: [PATCH 09/11] lib/interval-tree: convert interval_tree to half closed intervals

In reply to Davidlohr Bueso

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 perhaps radeon_vm_bo_set_addr(), but semantics have been tried to be left untouched.

NAK, the whole thing won't work.

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

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

Regards,
Christian.

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]>
---
  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
index 31d4deb5d294..4bbaa9ffa570 100644
@@ -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
index 11b231c187c5..818ff6b33102 100644
@@ -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
index dbab9a3a969b..4810421dacc2 100644
@@ -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
index c93f3ab3c4e3..4324f3fc5d82 100644
@@ -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
index e0ad547786e8..b2a54aff21f4 100644
@@ -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
index f67a30fda1ed..9b7ac93223d6 100644
@@ -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
index 3ea9d7682999..771740981f43 100644
@@ -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
index 288c26f50732..f3d1ea9e4003 100644
@@ -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
index 253df1a1fa54..d0ae7aa2139b 100644
@@ -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
index 593ce56ece50..336ec5113a28 100644
@@ -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

#25 lore raw

Re: [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 perhaps radeon_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 0x0 if long is only 32bit.

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

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

Regards,
Christian.

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]>

---
  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
index 31d4deb5d294..4bbaa9ffa570 100644
@@ -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 @@ 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;

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
index 11b231c187c5..818ff6b33102 100644
@@ -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(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 +1 -1
index dbab9a3a969b..4810421dacc2 100644
@@ -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_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;

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
index c93f3ab3c4e3..4324f3fc5d82 100644
@@ -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
index e0ad547786e8..b2a54aff21f4 100644
@@ -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);

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;
              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);

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) entries

         or 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(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 +4 -4
index f67a30fda1ed..9b7ac93223d6 100644
@@ -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(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 +2 -2
index 3ea9d7682999..771740981f43 100644
@@ -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 +0 -0
index 288c26f50732..f3d1ea9e4003 100644
@@ -7,7 +7,7 @@
   struct interval_tree_node {
       struct rb_node rb;

      unsigned long start;    /* Start of interval */
-    unsigned long last;    /* Last location _in_ interval */ +    unsigned long end;    /* Last location _outside_ interval */ unsigned long __subtree_last;
  };
  diff --git a/include/rdma/ib_umem_odp.h b/include/rdma/ib_umem_odp.h index 253df1a1fa54..d0ae7aa2139b 100644

include/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 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)

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
index 593ce56ece50..336ec5113a28 100644
@@ -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

#26 lore raw

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 perhaps radeon_vm_bo_set_addr(), but semantics have been tried to be left untouched.

NAK, the whole thing won't work.

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

Quoted 6 lines
Quoted 2 lines

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

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

Correct.

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

#27 lore raw

PATCH 10/11 lib: drop interval_tree_generic.h

In reply to Davidlohr Bueso

Now 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
deleted file mode 100644
index aaa8a0767aa3..000000000000
@@ -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
#28 lore raw

PATCH 11/11 x86/mm, pat: convert pat tree to generic interval tree

In reply to Davidlohr Bueso

With 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.

Cc Peter Zijlstra <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
---
 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
index d9fbd4f69920..a3d47b5db704 100644
@@ -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
Acked-by on v1 11/11
#29 lore raw

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_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.

Cc Peter Zijlstra <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[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

#30 lore raw

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

#31 lore raw
In reply to Davidlohr Bueso
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_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.

#32 lore raw
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_MAX to ULONG_MAX now?

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_MAX or UINT_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_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.

I agree.

Thanks,
Davidlohr

#33 lore raw
In reply to Matthew Wilcox
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_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.

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.
#34 lore raw
In reply to Davidlohr Bueso
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.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).

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

#35 lore raw
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.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).

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.

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

#36 lore raw
In reply to Jason Gunthorpe

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_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.

Quoted 8 lines

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.

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 where ULONG_MAX is 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.
#37 lore raw
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.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.

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.

#38 lore raw
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.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.

Quoted 4 lines

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.

Right, we should not have two implementations.

Thanks,
Davidlohr

#39 lore raw
In reply to Michel Lespinasse
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