[PATCH v2 0/3] make RB_DECLARE_CALLBACKS more generic

[PATCH v2 0/3] make RB_DECLARE_CALLBACKS more generic

[Michel Lespinasse]

These changes are intended to make the RB_DECLARE_CALLBACKS macro
more generic (allowing the aubmented subtree information to be a struct
instead of a scalar) and tweak the macro arguments to be more similar
to INTERVAL_TREE_DEFINE().

Changes since v1: I have added a new RB_DECLARE_CALLBACKS_MAX macro,
which generates augmented rbtree callbacks where the subtree information
can be expressed as max(f(node)). This covers all current uses, and thus
makes it easy to do the later RB_DECLARE_CALLBACKS definition change
as it's only currently used in RB_DECLARE_CALLBACKS_MAX.

I have also verified the compiled lib/interval_tree.o and mm/mmap.o
files to check that they didn't change. This held as expected for
interval_tree.o; mmap.o did have some changes which could be reverted
by marking __vma_link_rb as noinline. I did not add such a change to the
patchset; I felt it was reasonable enough to let the inlining decision
up to the compiler.

Michel Lespinasse (3):
  augmented rbtree: add comments for RB_DECLARE_CALLBACKS macro
  augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro
  augmented rbtree: rework the RB_DECLARE_CALLBACKS macro definition

 arch/x86/mm/pat_rbtree.c               | 19 +-----
 drivers/block/drbd/drbd_interval.c     | 29 +--------
 include/linux/interval_tree_generic.h  | 22 +------
 include/linux/rbtree_augmented.h       | 88 ++++++++++++++++++++------
 lib/rbtree_test.c                      | 22 +------
 mm/mmap.c                              | 29 +++++----
 tools/include/linux/rbtree_augmented.h | 88 ++++++++++++++++++++------
 7 files changed, 163 insertions(+), 134 deletions(-)

-- 
2.22.0.410.gd8fdbe21b5-goog

[PATCH v2 1/3] augmented rbtree: add comments for RB_DECLARE_CALLBACKS macro

[Michel Lespinasse]

Add a short comment summarizing the arguments to RB_DECLARE_CALLBACKS.
The arguments are also now capitalized. This copies the style of the
INTERVAL_TREE_DEFINE macro.

No functional changes in this commit, only comments and capitalization.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 include/linux/rbtree_augmented.h       | 54 ++++++++++++++++----------
 tools/include/linux/rbtree_augmented.h | 54 ++++++++++++++++----------
 2 files changed, 66 insertions(+), 42 deletions(-)

diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
index f1ed3fc80bbb..5923495276e0 100644
--- a/include/linux/rbtree_augmented.h
+++ b/include/linux/rbtree_augmented.h
@@ -72,39 +72,51 @@ rb_insert_augmented_cached(struct rb_node *node,
 	rb_insert_augmented(node, &root->rb_root, augment);
 }
 
-#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield,	\
-			     rbtype, rbaugmented, rbcompute)		\
+/*
+ * Template for declaring augmented rbtree callbacks
+ *
+ * RBSTATIC:    'static' or empty
+ * RBNAME:      name of the rb_augment_callbacks structure
+ * RBSTRUCT:    struct type of the tree nodes
+ * RBFIELD:     name of struct rb_node field within RBSTRUCT
+ * RBTYPE:      type of the RBAUGMENTED field
+ * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree
+ * RBCOMPUTE:   name of function that recomputes the RBAUGMENTED data
+ */
+
+#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD,	\
+			     RBTYPE, RBAUGMENTED, RBCOMPUTE)		\
 static inline void							\
-rbname ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
+RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
 {									\
 	while (rb != stop) {						\
-		rbstruct *node = rb_entry(rb, rbstruct, rbfield);	\
-		rbtype augmented = rbcompute(node);			\
-		if (node->rbaugmented == augmented)			\
+		RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD);	\
+		RBTYPE augmented = RBCOMPUTE(node);			\
+		if (node->RBAUGMENTED == augmented)			\
 			break;						\
-		node->rbaugmented = augmented;				\
-		rb = rb_parent(&node->rbfield);				\
+		node->RBAUGMENTED = augmented;				\
+		rb = rb_parent(&node->RBFIELD);				\
 	}								\
 }									\
 static inline void							\
-rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
+RBNAME ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
 {									\
-	rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\
-	rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\
-	new->rbaugmented = old->rbaugmented;				\
+	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
+	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
+	new->RBAUGMENTED = old->RBAUGMENTED;				\
 }									\
 static void								\
-rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
+RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
 {									\
-	rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\
-	rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\
-	new->rbaugmented = old->rbaugmented;				\
-	old->rbaugmented = rbcompute(old);				\
+	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
+	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
+	new->RBAUGMENTED = old->RBAUGMENTED;				\
+	old->RBAUGMENTED = RBCOMPUTE(old);				\
 }									\
-rbstatic const struct rb_augment_callbacks rbname = {			\
-	.propagate = rbname ## _propagate,				\
-	.copy = rbname ## _copy,					\
-	.rotate = rbname ## _rotate					\
+RBSTATIC const struct rb_augment_callbacks RBNAME = {			\
+	.propagate = RBNAME ## _propagate,				\
+	.copy = RBNAME ## _copy,					\
+	.rotate = RBNAME ## _rotate					\
 };
 
 
diff --git a/tools/include/linux/rbtree_augmented.h b/tools/include/linux/rbtree_augmented.h
index d008e1404580..ca25818714d3 100644
--- a/tools/include/linux/rbtree_augmented.h
+++ b/tools/include/linux/rbtree_augmented.h
@@ -74,39 +74,51 @@ rb_insert_augmented_cached(struct rb_node *node,
 			      newleft, &root->rb_leftmost, augment->rotate);
 }
 
-#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield,	\
-			     rbtype, rbaugmented, rbcompute)		\
+/*
+ * Template for declaring augmented rbtree callbacks
+ *
+ * RBSTATIC:    'static' or empty
+ * RBNAME:      name of the rb_augment_callbacks structure
+ * RBSTRUCT:    struct type of the tree nodes
+ * RBFIELD:     name of struct rb_node field within RBSTRUCT
+ * RBTYPE:      type of the RBAUGMENTED field
+ * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree
+ * RBCOMPUTE:   name of function that recomputes the RBAUGMENTED data
+ */
+
+#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD,	\
+			     RBTYPE, RBAUGMENTED, RBCOMPUTE)		\
 static inline void							\
-rbname ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
+RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
 {									\
 	while (rb != stop) {						\
-		rbstruct *node = rb_entry(rb, rbstruct, rbfield);	\
-		rbtype augmented = rbcompute(node);			\
-		if (node->rbaugmented == augmented)			\
+		RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD);	\
+		RBTYPE augmented = RBCOMPUTE(node);			\
+		if (node->RBAUGMENTED == augmented)			\
 			break;						\
-		node->rbaugmented = augmented;				\
-		rb = rb_parent(&node->rbfield);				\
+		node->RBAUGMENTED = augmented;				\
+		rb = rb_parent(&node->RBFIELD);				\
 	}								\
 }									\
 static inline void							\
-rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
+RBNAME ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
 {									\
-	rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\
-	rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\
-	new->rbaugmented = old->rbaugmented;				\
+	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
+	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
+	new->RBAUGMENTED = old->RBAUGMENTED;				\
 }									\
 static void								\
-rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
+RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
 {									\
-	rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\
-	rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\
-	new->rbaugmented = old->rbaugmented;				\
-	old->rbaugmented = rbcompute(old);				\
+	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
+	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
+	new->RBAUGMENTED = old->RBAUGMENTED;				\
+	old->RBAUGMENTED = RBCOMPUTE(old);				\
 }									\
-rbstatic const struct rb_augment_callbacks rbname = {			\
-	.propagate = rbname ## _propagate,				\
-	.copy = rbname ## _copy,					\
-	.rotate = rbname ## _rotate					\
+RBSTATIC const struct rb_augment_callbacks RBNAME = {			\
+	.propagate = RBNAME ## _propagate,				\
+	.copy = RBNAME ## _copy,					\
+	.rotate = RBNAME ## _rotate					\
 };
 
 
-- 
2.22.0.410.gd8fdbe21b5-goog

[PATCH v2 2/3] augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro

[Michel Lespinasse]

Add RB_DECLARE_CALLBACKS_MAX, which generates augmented rbtree callbacks
for the case where the augmented value is a scalar whose definition
follows a max(f(node)) pattern. This actually covers all present uses
of RB_DECLARE_CALLBACKS, and saves some (source) code duplication in the
various RBCOMPUTE function definitions.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 arch/x86/mm/pat_rbtree.c               | 19 +++-----------
 drivers/block/drbd/drbd_interval.c     | 29 +++------------------
 include/linux/interval_tree_generic.h  | 22 ++--------------
 include/linux/rbtree_augmented.h       | 36 +++++++++++++++++++++++++-
 lib/rbtree_test.c                      | 22 +++-------------
 mm/mmap.c                              | 29 +++++++++++++--------
 tools/include/linux/rbtree_augmented.h | 36 +++++++++++++++++++++++++-
 7 files changed, 99 insertions(+), 94 deletions(-)

diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c
index fa16036fa592..2afad8e869fc 100644
--- a/arch/x86/mm/pat_rbtree.c
+++ b/arch/x86/mm/pat_rbtree.c
@@ -54,23 +54,10 @@ static u64 get_subtree_max_end(struct rb_node *node)
 	return ret;
 }
 
-static u64 compute_subtree_max_end(struct memtype *data)
-{
-	u64 max_end = data->end, child_max_end;
-
-	child_max_end = get_subtree_max_end(data->rb.rb_right);
-	if (child_max_end > max_end)
-		max_end = child_max_end;
-
-	child_max_end = get_subtree_max_end(data->rb.rb_left);
-	if (child_max_end > max_end)
-		max_end = child_max_end;
-
-	return max_end;
-}
+#define NODE_END(node) ((node)->end)
 
-RB_DECLARE_CALLBACKS(static, memtype_rb_augment_cb, struct memtype, rb,
-		     u64, subtree_max_end, compute_subtree_max_end)
+RB_DECLARE_CALLBACKS_MAX(struct memtype, rb, u64, subtree_max_end, NODE_END,
+			 static, memtype_rb_augment_cb)
 
 /* Find the first (lowest start addr) overlapping range from rb tree */
 static struct memtype *memtype_rb_lowest_match(struct rb_root *root,
diff --git a/drivers/block/drbd/drbd_interval.c b/drivers/block/drbd/drbd_interval.c
index c58986556161..3a507a1fd1e3 100644
--- a/drivers/block/drbd/drbd_interval.c
+++ b/drivers/block/drbd/drbd_interval.c
@@ -13,33 +13,10 @@ sector_t interval_end(struct rb_node *node)
 	return this->end;
 }
 
-/**
- * compute_subtree_last  -  compute end of @node
- *
- * The end of an interval is the highest (start + (size >> 9)) value of this
- * node and of its children.  Called for @node and its parents whenever the end
- * may have changed.
- */
-static inline sector_t
-compute_subtree_last(struct drbd_interval *node)
-{
-	sector_t max = node->sector + (node->size >> 9);
-
-	if (node->rb.rb_left) {
-		sector_t left = interval_end(node->rb.rb_left);
-		if (left > max)
-			max = left;
-	}
-	if (node->rb.rb_right) {
-		sector_t right = interval_end(node->rb.rb_right);
-		if (right > max)
-			max = right;
-	}
-	return max;
-}
+#define NODE_END(node) ((node)->sector + ((node)->size >> 9))
 
-RB_DECLARE_CALLBACKS(static, augment_callbacks, struct drbd_interval, rb,
-		     sector_t, end, compute_subtree_last);
+RB_DECLARE_CALLBACKS_MAX(struct drbd_interval, rb, sector_t, end, NODE_END,
+			 static, augment_callbacks);
 
 /**
  * drbd_insert_interval  -  insert a new interval into a tree
diff --git a/include/linux/interval_tree_generic.h b/include/linux/interval_tree_generic.h
index 1f97ce26cccc..8a9fcfb25157 100644
--- a/include/linux/interval_tree_generic.h
+++ b/include/linux/interval_tree_generic.h
@@ -42,26 +42,8 @@
 									      \
 /* Callbacks for augmented rbtree insert and remove */			      \
 									      \
-static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node)	      \
-{									      \
-	ITTYPE max = ITLAST(node), subtree_last;			      \
-	if (node->ITRB.rb_left) {					      \
-		subtree_last = rb_entry(node->ITRB.rb_left,		      \
-					ITSTRUCT, ITRB)->ITSUBTREE;	      \
-		if (max < subtree_last)					      \
-			max = subtree_last;				      \
-	}								      \
-	if (node->ITRB.rb_right) {					      \
-		subtree_last = rb_entry(node->ITRB.rb_right,		      \
-					ITSTRUCT, ITRB)->ITSUBTREE;	      \
-		if (max < subtree_last)					      \
-			max = subtree_last;				      \
-	}								      \
-	return max;							      \
-}									      \
-									      \
-RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB,	      \
-		     ITTYPE, ITSUBTREE, ITPREFIX ## _compute_subtree_last)    \
+RB_DECLARE_CALLBACKS_MAX(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, ITLAST,	      \
+			 static, ITPREFIX ## _augment)			      \
 									      \
 /* Insert / remove interval nodes from the tree */			      \
 									      \
diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
index 5923495276e0..a471702c01e7 100644
--- a/include/linux/rbtree_augmented.h
+++ b/include/linux/rbtree_augmented.h
@@ -73,7 +73,7 @@ rb_insert_augmented_cached(struct rb_node *node,
 }
 
 /*
- * Template for declaring augmented rbtree callbacks
+ * Template for declaring augmented rbtree callbacks (generic case)
  *
  * RBSTATIC:    'static' or empty
  * RBNAME:      name of the rb_augment_callbacks structure
@@ -119,6 +119,40 @@ RBSTATIC const struct rb_augment_callbacks RBNAME = {			\
 	.rotate = RBNAME ## _rotate					\
 };
 
+/*
+ * Template for declaring augmented rbtree callbacks,
+ * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
+ *
+ * RBSTRUCT:    struct type of the tree nodes
+ * RBFIELD:     name of struct rb_node field within RBSTRUCT
+ * RBTYPE:      type of the RBAUGMENTED field
+ * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree
+ * RBCOMPUTE:   name of function that returns the per-node RBTYPE scalar
+ * RBSTATIC:    'static' or empty
+ * RBNAME:      name of the rb_augment_callbacks structure
+ */
+
+#define RB_DECLARE_CALLBACKS_MAX(RBSTRUCT, RBFIELD, RBTYPE, RBAUGMENTED,      \
+			     RBCOMPUTE, RBSTATIC, RBNAME)		      \
+static inline RBTYPE RBNAME ## _compute_max(RBSTRUCT *node)		      \
+{									      \
+	RBSTRUCT *child;						      \
+	RBTYPE max = RBCOMPUTE(node);					      \
+	if (node->RBFIELD.rb_left) {					      \
+		child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD);   \
+		if (child->RBAUGMENTED > max)				      \
+			max = child->RBAUGMENTED;			      \
+	}								      \
+	if (node->RBFIELD.rb_right) {					      \
+		child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD);  \
+		if (child->RBAUGMENTED > max)				      \
+			max = child->RBAUGMENTED;			      \
+	}								      \
+	return max;							      \
+}									      \
+RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD,		      \
+		     RBTYPE, RBAUGMENTED, RBNAME ## _compute_max)
+
 
 #define	RB_RED		0
 #define	RB_BLACK	1
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index b7055b2a07d3..b876f8e73897 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -76,26 +76,10 @@ static inline void erase_cached(struct test_node *node, struct rb_root_cached *r
 }
 
 
-static inline u32 augment_recompute(struct test_node *node)
-{
-	u32 max = node->val, child_augmented;
-	if (node->rb.rb_left) {
-		child_augmented = rb_entry(node->rb.rb_left, struct test_node,
-					   rb)->augmented;
-		if (max < child_augmented)
-			max = child_augmented;
-	}
-	if (node->rb.rb_right) {
-		child_augmented = rb_entry(node->rb.rb_right, struct test_node,
-					   rb)->augmented;
-		if (max < child_augmented)
-			max = child_augmented;
-	}
-	return max;
-}
+#define NODE_VAL(node) ((node)->val)
 
-RB_DECLARE_CALLBACKS(static, augment_callbacks, struct test_node, rb,
-		     u32, augmented, augment_recompute)
+RB_DECLARE_CALLBACKS_MAX(struct test_node, rb, u32, augmented, NODE_VAL,
+			 static, augment_callbacks)
 
 static void insert_augmented(struct test_node *node,
 			     struct rb_root_cached *root)
diff --git a/mm/mmap.c b/mm/mmap.c
index bd7b9f293b39..cd293c794975 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -288,9 +288,9 @@ SYSCALL_DEFINE1(brk, unsigned long, brk)
 	return retval;
 }
 
-static long vma_compute_subtree_gap(struct vm_area_struct *vma)
+static inline unsigned long vma_compute_gap(struct vm_area_struct *vma)
 {
-	unsigned long max, prev_end, subtree_gap;
+	unsigned long gap, prev_end;
 
 	/*
 	 * Note: in the rare case of a VM_GROWSDOWN above a VM_GROWSUP, we
@@ -298,14 +298,21 @@ static long vma_compute_subtree_gap(struct vm_area_struct *vma)
 	 * an unmapped area; whereas when expanding we only require one.
 	 * That's a little inconsistent, but keeps the code here simpler.
 	 */
-	max = vm_start_gap(vma);
+	gap = vm_start_gap(vma);
 	if (vma->vm_prev) {
 		prev_end = vm_end_gap(vma->vm_prev);
-		if (max > prev_end)
-			max -= prev_end;
+		if (gap > prev_end)
+			gap -= prev_end;
 		else
-			max = 0;
+			gap = 0;
 	}
+	return gap;
+}
+
+#ifdef CONFIG_DEBUG_VM_RB
+static unsigned long vma_compute_subtree_gap(struct vm_area_struct *vma)
+{
+	unsigned long max = vma_compute_gap(vma), subtree_gap;
 	if (vma->vm_rb.rb_left) {
 		subtree_gap = rb_entry(vma->vm_rb.rb_left,
 				struct vm_area_struct, vm_rb)->rb_subtree_gap;
@@ -321,7 +328,6 @@ static long vma_compute_subtree_gap(struct vm_area_struct *vma)
 	return max;
 }
 
-#ifdef CONFIG_DEBUG_VM_RB
 static int browse_rb(struct mm_struct *mm)
 {
 	struct rb_root *root = &mm->mm_rb;
@@ -427,8 +433,9 @@ static void validate_mm(struct mm_struct *mm)
 #define validate_mm(mm) do { } while (0)
 #endif
 
-RB_DECLARE_CALLBACKS(static, vma_gap_callbacks, struct vm_area_struct, vm_rb,
-		     unsigned long, rb_subtree_gap, vma_compute_subtree_gap)
+RB_DECLARE_CALLBACKS_MAX(struct vm_area_struct, vm_rb,
+			 unsigned long, rb_subtree_gap, vma_compute_gap,
+			 static, vma_gap_callbacks)
 
 /*
  * Update augmented rbtree rb_subtree_gap values after vma->vm_start or
@@ -438,8 +445,8 @@ RB_DECLARE_CALLBACKS(static, vma_gap_callbacks, struct vm_area_struct, vm_rb,
 static void vma_gap_update(struct vm_area_struct *vma)
 {
 	/*
-	 * As it turns out, RB_DECLARE_CALLBACKS() already created a callback
-	 * function that does exactly what we want.
+	 * As it turns out, RB_DECLARE_CALLBACKS_MAX() already created
+	 * a callback function that does exactly what we want.
 	 */
 	vma_gap_callbacks_propagate(&vma->vm_rb, NULL);
 }
diff --git a/tools/include/linux/rbtree_augmented.h b/tools/include/linux/rbtree_augmented.h
index ca25818714d3..4db1dcaf90b2 100644
--- a/tools/include/linux/rbtree_augmented.h
+++ b/tools/include/linux/rbtree_augmented.h
@@ -75,7 +75,7 @@ rb_insert_augmented_cached(struct rb_node *node,
 }
 
 /*
- * Template for declaring augmented rbtree callbacks
+ * Template for declaring augmented rbtree callbacks (generic case)
  *
  * RBSTATIC:    'static' or empty
  * RBNAME:      name of the rb_augment_callbacks structure
@@ -121,6 +121,40 @@ RBSTATIC const struct rb_augment_callbacks RBNAME = {			\
 	.rotate = RBNAME ## _rotate					\
 };
 
+/*
+ * Template for declaring augmented rbtree callbacks,
+ * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
+ *
+ * RBSTRUCT:    struct type of the tree nodes
+ * RBFIELD:     name of struct rb_node field within RBSTRUCT
+ * RBTYPE:      type of the RBAUGMENTED field
+ * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree
+ * RBCOMPUTE:   name of function that returns the per-node RBTYPE scalar
+ * RBSTATIC:    'static' or empty
+ * RBNAME:      name of the rb_augment_callbacks structure
+ */
+
+#define RB_DECLARE_CALLBACKS_MAX(RBSTRUCT, RBFIELD, RBTYPE, RBAUGMENTED,      \
+			     RBCOMPUTE, RBSTATIC, RBNAME)		      \
+static inline RBTYPE RBNAME ## _compute_max(RBSTRUCT *node)		      \
+{									      \
+	RBSTRUCT *child;						      \
+	RBTYPE max = RBCOMPUTE(node);					      \
+	if (node->RBFIELD.rb_left) {					      \
+		child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD);   \
+		if (child->RBAUGMENTED > max)				      \
+			max = child->RBAUGMENTED;			      \
+	}								      \
+	if (node->RBFIELD.rb_right) {					      \
+		child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD);  \
+		if (child->RBAUGMENTED > max)				      \
+			max = child->RBAUGMENTED;			      \
+	}								      \
+	return max;							      \
+}									      \
+RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD,		      \
+		     RBTYPE, RBAUGMENTED, RBNAME ## _compute_max)
+
 
 #define	RB_RED		0
 #define	RB_BLACK	1
-- 
2.22.0.410.gd8fdbe21b5-goog

[PATCH v2 3/3] augmented rbtree: rework the RB_DECLARE_CALLBACKS macro definition

[Michel Lespinasse]

- Change the definition of the RBCOMPUTE function. The propagate
  callback repeatedly calls RBCOMPUTE as it moves from leaf to root.
  it wants to stop recomputing once the augmented subtree information
  doesn't change. This was previously checked using the == operator,
  but that only works when the augmented subtree information is a
  scalar field. This commit modifies the RBCOMPUTE function so that
  it now sets the augmented subtree information instead of returning it,
  and returns a boolean value indicating if the propagate callback
  should stop.

- Reorder the RB_DECLARE_CALLBACKS macro arguments, following the
  style of the INTERVAL_TREE_DEFINE macro, so that RBSTATIC and RBNAME
  are passed last.

The motivation for this change is that I want to introduce augmented rbtree
uses where the augmented data for the subtree is a struct instead of a scalar.

Signed-off-by: Michel Lespinasse <walken@google.com>
---
 include/linux/rbtree_augmented.h       | 28 +++++++++++++-------------
 tools/include/linux/rbtree_augmented.h | 28 +++++++++++++-------------
 2 files changed, 28 insertions(+), 28 deletions(-)

diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
index a471702c01e7..f8780a67ec04 100644
--- a/include/linux/rbtree_augmented.h
+++ b/include/linux/rbtree_augmented.h
@@ -75,26 +75,23 @@ rb_insert_augmented_cached(struct rb_node *node,
 /*
  * Template for declaring augmented rbtree callbacks (generic case)
  *
- * RBSTATIC:    'static' or empty
- * RBNAME:      name of the rb_augment_callbacks structure
  * RBSTRUCT:    struct type of the tree nodes
  * RBFIELD:     name of struct rb_node field within RBSTRUCT
- * RBTYPE:      type of the RBAUGMENTED field
- * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree
+ * RBAUGMENTED: name of field within RBSTRUCT holding data for subtree
  * RBCOMPUTE:   name of function that recomputes the RBAUGMENTED data
+ * RBSTATIC:    'static' or empty
+ * RBNAME:      name of the rb_augment_callbacks structure
  */
 
-#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD,	\
-			     RBTYPE, RBAUGMENTED, RBCOMPUTE)		\
+#define RB_DECLARE_CALLBACKS(RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE,	\
+			     RBSTATIC, RBNAME)				\
 static inline void							\
 RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
 {									\
 	while (rb != stop) {						\
 		RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD);	\
-		RBTYPE augmented = RBCOMPUTE(node);			\
-		if (node->RBAUGMENTED == augmented)			\
+		if (RBCOMPUTE(node, true))				\
 			break;						\
-		node->RBAUGMENTED = augmented;				\
 		rb = rb_parent(&node->RBFIELD);				\
 	}								\
 }									\
@@ -111,7 +108,7 @@ RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
 	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
 	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
 	new->RBAUGMENTED = old->RBAUGMENTED;				\
-	old->RBAUGMENTED = RBCOMPUTE(old);				\
+	RBCOMPUTE(old, false);						\
 }									\
 RBSTATIC const struct rb_augment_callbacks RBNAME = {			\
 	.propagate = RBNAME ## _propagate,				\
@@ -134,7 +131,7 @@ RBSTATIC const struct rb_augment_callbacks RBNAME = {			\
 
 #define RB_DECLARE_CALLBACKS_MAX(RBSTRUCT, RBFIELD, RBTYPE, RBAUGMENTED,      \
 			     RBCOMPUTE, RBSTATIC, RBNAME)		      \
-static inline RBTYPE RBNAME ## _compute_max(RBSTRUCT *node)		      \
+static inline bool RBNAME ## _compute_max(RBSTRUCT *node, bool exit)	      \
 {									      \
 	RBSTRUCT *child;						      \
 	RBTYPE max = RBCOMPUTE(node);					      \
@@ -148,10 +145,13 @@ static inline RBTYPE RBNAME ## _compute_max(RBSTRUCT *node)		      \
 		if (child->RBAUGMENTED > max)				      \
 			max = child->RBAUGMENTED;			      \
 	}								      \
-	return max;							      \
+	if (exit && node->RBAUGMENTED == max)				      \
+		return true;						      \
+	node->RBAUGMENTED = max;					      \
+	return false;							      \
 }									      \
-RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD,		      \
-		     RBTYPE, RBAUGMENTED, RBNAME ## _compute_max)
+RB_DECLARE_CALLBACKS(RBSTRUCT, RBFIELD, RBAUGMENTED, RBNAME ## _compute_max,  \
+		     RBSTATIC, RBNAME)
 
 
 #define	RB_RED		0
diff --git a/tools/include/linux/rbtree_augmented.h b/tools/include/linux/rbtree_augmented.h
index 4db1dcaf90b2..b5845898c2d8 100644
--- a/tools/include/linux/rbtree_augmented.h
+++ b/tools/include/linux/rbtree_augmented.h
@@ -77,26 +77,23 @@ rb_insert_augmented_cached(struct rb_node *node,
 /*
  * Template for declaring augmented rbtree callbacks (generic case)
  *
- * RBSTATIC:    'static' or empty
- * RBNAME:      name of the rb_augment_callbacks structure
  * RBSTRUCT:    struct type of the tree nodes
  * RBFIELD:     name of struct rb_node field within RBSTRUCT
- * RBTYPE:      type of the RBAUGMENTED field
- * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree
+ * RBAUGMENTED: name of field within RBSTRUCT holding data for subtree
  * RBCOMPUTE:   name of function that recomputes the RBAUGMENTED data
+ * RBSTATIC:    'static' or empty
+ * RBNAME:      name of the rb_augment_callbacks structure
  */
 
-#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD,	\
-			     RBTYPE, RBAUGMENTED, RBCOMPUTE)		\
+#define RB_DECLARE_CALLBACKS(RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE,	\
+			     RBSTATIC, RBNAME)				\
 static inline void							\
 RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
 {									\
 	while (rb != stop) {						\
 		RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD);	\
-		RBTYPE augmented = RBCOMPUTE(node);			\
-		if (node->RBAUGMENTED == augmented)			\
+		if (RBCOMPUTE(node, true))				\
 			break;						\
-		node->RBAUGMENTED = augmented;				\
 		rb = rb_parent(&node->RBFIELD);				\
 	}								\
 }									\
@@ -113,7 +110,7 @@ RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
 	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
 	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
 	new->RBAUGMENTED = old->RBAUGMENTED;				\
-	old->RBAUGMENTED = RBCOMPUTE(old);				\
+	RBCOMPUTE(old, false);						\
 }									\
 RBSTATIC const struct rb_augment_callbacks RBNAME = {			\
 	.propagate = RBNAME ## _propagate,				\
@@ -136,7 +133,7 @@ RBSTATIC const struct rb_augment_callbacks RBNAME = {			\
 
 #define RB_DECLARE_CALLBACKS_MAX(RBSTRUCT, RBFIELD, RBTYPE, RBAUGMENTED,      \
 			     RBCOMPUTE, RBSTATIC, RBNAME)		      \
-static inline RBTYPE RBNAME ## _compute_max(RBSTRUCT *node)		      \
+static inline bool RBNAME ## _compute_max(RBSTRUCT *node, bool exit)	      \
 {									      \
 	RBSTRUCT *child;						      \
 	RBTYPE max = RBCOMPUTE(node);					      \
@@ -150,10 +147,13 @@ static inline RBTYPE RBNAME ## _compute_max(RBSTRUCT *node)		      \
 		if (child->RBAUGMENTED > max)				      \
 			max = child->RBAUGMENTED;			      \
 	}								      \
-	return max;							      \
+	if (exit && node->RBAUGMENTED == max)				      \
+		return true;						      \
+	node->RBAUGMENTED = max;					      \
+	return false;							      \
 }									      \
-RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD,		      \
-		     RBTYPE, RBAUGMENTED, RBNAME ## _compute_max)
+RB_DECLARE_CALLBACKS(RBSTRUCT, RBFIELD, RBAUGMENTED, RBNAME ## _compute_max,  \
+		     RBSTATIC, RBNAME)
 
 
 #define	RB_RED		0
-- 
2.22.0.410.gd8fdbe21b5-goog

Re: [PATCH v2 3/3] augmented rbtree: rework the RB_DECLARE_CALLBACKS macro definition

[Peter Zijlstra]

On Tue, Jul 02, 2019 at 12:58:19AM -0700, Michel Lespinasse wrote:
> - Change the definition of the RBCOMPUTE function. The propagate
>   callback repeatedly calls RBCOMPUTE as it moves from leaf to root.
>   it wants to stop recomputing once the augmented subtree information
>   doesn't change. This was previously checked using the == operator,
>   but that only works when the augmented subtree information is a
>   scalar field. This commit modifies the RBCOMPUTE function so that
>   it now sets the augmented subtree information instead of returning it,
>   and returns a boolean value indicating if the propagate callback
>   should stop.

I suppose that makes sense and saves a copy over adding RBEQUAL() like I
proposed earlier.

> - Reorder the RB_DECLARE_CALLBACKS macro arguments, following the
>   style of the INTERVAL_TREE_DEFINE macro, so that RBSTATIC and RBNAME
>   are passed last.

That's, IMO, a weird change. C has storage type and name first, why
would you want to put that last. If anything, change
INTERVAL_TREE_DEFINE().

Also; this is two changes and one patch; ISTR we have rules about those
things :-)

> The motivation for this change is that I want to introduce augmented rbtree
> uses where the augmented data for the subtree is a struct instead of a scalar.

I'm not seeing how this justifies the second thing.

Re: [PATCH v2 2/3] augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro

[Davidlohr Bueso]

On Tue, 02 Jul 2019, Michel Lespinasse wrote:

>diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c
>index fa16036fa592..2afad8e869fc 100644
>--- a/arch/x86/mm/pat_rbtree.c
>+++ b/arch/x86/mm/pat_rbtree.c
>@@ -54,23 +54,10 @@ static u64 get_subtree_max_end(struct rb_node *node)
> 	return ret;
> }
>
>-static u64 compute_subtree_max_end(struct memtype *data)
>-{
>-	u64 max_end = data->end, child_max_end;
>-
>-	child_max_end = get_subtree_max_end(data->rb.rb_right);
>-	if (child_max_end > max_end)
>-		max_end = child_max_end;
>-
>-	child_max_end = get_subtree_max_end(data->rb.rb_left);
>-	if (child_max_end > max_end)
>-		max_end = child_max_end;
>-
>-	return max_end;
>-}
>+#define NODE_END(node) ((node)->end)
>
>-RB_DECLARE_CALLBACKS(static, memtype_rb_augment_cb, struct memtype, rb,
>-		     u64, subtree_max_end, compute_subtree_max_end)
>+RB_DECLARE_CALLBACKS_MAX(struct memtype, rb, u64, subtree_max_end, NODE_END,
>+			 static, memtype_rb_augment_cb)

(unrelated to this patch)

So fyi I've recently been looking at having the whole pat_rbtree use the (generic)
interval tree api, which would mean less code and more optimized. Of course,
unfortunately they aren't 100% compatible. Fundamentally the concept of overlaps
are different (pat_rbtree is does not consider overlap when 'node->start == end' -
same for the test to the right of the node). Thus for example interval_tree_iter_first()
won't necessarily return the same node as memtype_rb_lowest_match(). Similarly,
inserting a node with key collisions will have differences wrt what path to take;
equal 'start' in pat will go to the left, interval_tree to the right. All this,
I suspect, is inherited from how pat used to work with rbtree+list.

So generic ones cannot be used and if we just use INTERVAL_TREE_DEFINE template for
pat and add the ad-hoc code does not make sense wrt cleanup, nor do we get the
optimizations. We could of course, add them manually (by using cached rbtrees, for
example) and forget about interval_tree altogether; just seems a shame.

Thanks,
Davidlohr

Re: [PATCH v2 1/3] augmented rbtree: add comments for RB_DECLARE_CALLBACKS macro

[Davidlohr Bueso]

On Tue, 02 Jul 2019, Michel Lespinasse wrote:

>Add a short comment summarizing the arguments to RB_DECLARE_CALLBACKS.
>The arguments are also now capitalized. This copies the style of the
>INTERVAL_TREE_DEFINE macro.
>
>No functional changes in this commit, only comments and capitalization.
>
>Signed-off-by: Michel Lespinasse <walken@google.com>

Acked-by: Davidlohr Bueso <dbueso@suse.de>

Re: [PATCH v2 3/3] augmented rbtree: rework the RB_DECLARE_CALLBACKS macro definition

[Michel Lespinasse]

On Tue, Jul 2, 2019 at 4:52 AM Peter Zijlstra <peterz@infradead.org> wrote:
> > - Reorder the RB_DECLARE_CALLBACKS macro arguments, following the
> >   style of the INTERVAL_TREE_DEFINE macro, so that RBSTATIC and RBNAME
> >   are passed last.
>
> That's, IMO, a weird change. C has storage type and name first, why
> would you want to put that last. If anything, change
> INTERVAL_TREE_DEFINE().

Makes sense, will do. I'll have to make it a v3 of the patchset
because RB_DECLARE_CALLBACKS_MAX was introduced with the opposite
argument order. Oh well, no big deal.

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Re: [PATCH v2 2/3] augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro

[Michel Lespinasse]

On Tue, Jul 2, 2019 at 9:09 AM Davidlohr Bueso <dave@stgolabs.net> wrote:
>
> On Tue, 02 Jul 2019, Michel Lespinasse wrote:
>
> >diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c
> >index fa16036fa592..2afad8e869fc 100644
> >--- a/arch/x86/mm/pat_rbtree.c
> >+++ b/arch/x86/mm/pat_rbtree.c
> >@@ -54,23 +54,10 @@ static u64 get_subtree_max_end(struct rb_node *node)
> >       return ret;
> > }
> >
> >-static u64 compute_subtree_max_end(struct memtype *data)
> >-{
> >-      u64 max_end = data->end, child_max_end;
> >-
> >-      child_max_end = get_subtree_max_end(data->rb.rb_right);
> >-      if (child_max_end > max_end)
> >-              max_end = child_max_end;
> >-
> >-      child_max_end = get_subtree_max_end(data->rb.rb_left);
> >-      if (child_max_end > max_end)
> >-              max_end = child_max_end;
> >-
> >-      return max_end;
> >-}
> >+#define NODE_END(node) ((node)->end)
> >
> >-RB_DECLARE_CALLBACKS(static, memtype_rb_augment_cb, struct memtype, rb,
> >-                   u64, subtree_max_end, compute_subtree_max_end)
> >+RB_DECLARE_CALLBACKS_MAX(struct memtype, rb, u64, subtree_max_end, NODE_END,
> >+                       static, memtype_rb_augment_cb)
>
> (unrelated to this patch)
>
> So fyi I've recently been looking at having the whole pat_rbtree use the (generic)
> interval tree api, which would mean less code and more optimized. Of course,
> unfortunately they aren't 100% compatible. Fundamentally the concept of overlaps
> are different (pat_rbtree is does not consider overlap when 'node->start == end' -
> same for the test to the right of the node). Thus for example interval_tree_iter_first()
> won't necessarily return the same node as memtype_rb_lowest_match(). Similarly,
> inserting a node with key collisions will have differences wrt what path to take;
> equal 'start' in pat will go to the left, interval_tree to the right. All this,
> I suspect, is inherited from how pat used to work with rbtree+list.
>
> So generic ones cannot be used and if we just use INTERVAL_TREE_DEFINE template for
> pat and add the ad-hoc code does not make sense wrt cleanup, nor do we get the
> optimizations. We could of course, add them manually (by using cached rbtrees, for
> example) and forget about interval_tree altogether; just seems a shame.

Ehhh, I have my own list of gripes about interval tree (I'm
responsible for some of these too):

- The majority of interval tree users (though either the
interval_tree.h or the interval_tree_generic.h API) do not store any
overlapping intervals, and as such they really don't have any reason
to use an augmented rbtree in the first place. This seems to be true
for at least drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c,
drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c, drivers/gpu/drm/drm_mm.c,
drivers/gpu/drm/radeon/radeon_mn.c,
drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c, and probably
(not 100% sure) also drivers/infiniband/hw/hfi1/mmu_rb.c and
drivers/vhost/vhost.c. I think the reason they do that is because they
like to have the auto-generated insert / remove / iter functions
rather than writing their own as they would have to do through the
base rbtree API. Not necessarily a huge problem but it is annoying
when working on inteval tree to consider that the data structure is
not optimal for most of its users.

- The intervals are represented as [start, last], where most
everything else in the kernel uses [start, end[ (with last == end -
1). The reason it was done that way was for stabbing queries - I
thought these would be nicer to represent as a [stab, stab] interval
rather than [stab, stab+1[. But, things didn't turn out that way
because of huge pages, and we end up with stabbing queries in the
[stab, stab + page_size - 1] format, at which point we could just as
easily go for [stab, stab + page_size[ representation. Having looked
into it, my understanding is that *all* current users of the interval
tree API would be better served if the intervals were represented as
[start, end[ like everywhere else in the kernel.

- interval_tree_generic.h refers to interval_tree.h as being the
generic one. I think this is quite confusing. To me
interval_tree_generic is the generic implementation (it works with any
scalar ITTYPE), and interval_tree.h is the specialized version (it
works with unsigned long keys only). Fun fact, interval_tree.[c,h] was
initially only meant as sample / test code - I thought everyone would
use the generic version. Not a big deal, it's probably better for
everyone to use the specialized version when applicable (unless they
don't really need overlapping intervals in the first place, but that's
a separate gripe).

- I don't like that interval tree API forces rb_leftmost caching on
its users. I'm not sure what was the use case that motivated it, but I
don' think it's a relevant optimization for most users - I can only
see a benefit if people are frequently calling the iter_first function
with a search interval that is to the left of the leftmost entry, and
that doesn't seem to be relevant to the general case (in the general
case, maintaining leftmost has a O(1) cost and its benefit is only
expected to show up in 1/N cases, ....)

Going back to your specific pat_rbtree.c comment, I think using
interval trees could still work. The issue with end is the typical one
([start, last] vs [start, end[) which can be worked around by
adjusting the end by 1 (still hate having to do that though). The
issue with insertion order may possibly not matter, as
memtype_rb_check_conflict verifies that any overlapping ranges will
have the same configured memory type. So maybe the order doesn't
matter in the end ??? Not 100% sure about that one.

Do you have any comments on the above gripes and do you think they
would be worth addressing ?

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Re: [PATCH v2 2/3] augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro

[Davidlohr Bueso]

On Tue, 02 Jul 2019, Michel Lespinasse wrote:
>Ehhh, I have my own list of gripes about interval tree (I'm
>responsible for some of these too):

Sorry just getting back to this.

>
>- The majority of interval tree users (though either the
>interval_tree.h or the interval_tree_generic.h API) do not store any
>overlapping intervals, and as such they really don't have any reason
>to use an augmented rbtree in the first place. This seems to be true
>for at least drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c,
>drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c, drivers/gpu/drm/drm_mm.c,
>drivers/gpu/drm/radeon/radeon_mn.c,
>drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c, and probably
>(not 100% sure) also drivers/infiniband/hw/hfi1/mmu_rb.c and
>drivers/vhost/vhost.c. I think the reason they do that is because they
>like to have the auto-generated insert / remove / iter functions
>rather than writing their own as they would have to do through the
>base rbtree API. Not necessarily a huge problem but it is annoying
>when working on inteval tree to consider that the data structure is
>not optimal for most of its users.

I think the patch I sent earlier will add to your unhappiness.

>
>- The intervals are represented as [start, last], where most
>everything else in the kernel uses [start, end[ (with last == end -
>1). The reason it was done that way was for stabbing queries - I
>thought these would be nicer to represent as a [stab, stab] interval
>rather than [stab, stab+1[. But, things didn't turn out that way
>because of huge pages, and we end up with stabbing queries in the
>[stab, stab + page_size - 1] format, at which point we could just as
>easily go for [stab, stab + page_size[ representation. Having looked
>into it, my understanding is that *all* current users of the interval
>tree API would be better served if the intervals were represented as
>[start, end[ like everywhere else in the kernel.
>
>- interval_tree_generic.h refers to interval_tree.h as being the
>generic one. I think this is quite confusing. To me
>interval_tree_generic is the generic implementation (it works with any
>scalar ITTYPE), and interval_tree.h is the specialized version (it
>works with unsigned long keys only). Fun fact, interval_tree.[c,h] was
>initially only meant as sample / test code - I thought everyone would
>use the generic version. Not a big deal, it's probably better for
>everyone to use the specialized version when applicable (unless they
>don't really need overlapping intervals in the first place, but that's
>a separate gripe).
>
>- I don't like that interval tree API forces rb_leftmost caching on
>its users. I'm not sure what was the use case that motivated it, but I
>don' think it's a relevant optimization for most users - I can only
>see a benefit if people are frequently calling the iter_first function
>with a search interval that is to the left of the leftmost entry, and
>that doesn't seem to be relevant to the general case (in the general
>case, maintaining leftmost has a O(1) cost and its benefit is only
>expected to show up in 1/N cases, ....)

Right, so this was done originally for optimizing range locking which
needed to do the iter_first a lot. fwiw pat_rbtree tree could also use
it before insertion. While I did not examine the other users of interval_tree,
I considered it overall worthwhile having; it comes at pretty
much no cost and the extra footprint has not been a problem so far for
users.

>
>Going back to your specific pat_rbtree.c comment, I think using
>interval trees could still work. The issue with end is the typical one
>([start, last] vs [start, end[) which can be worked around by
>adjusting the end by 1 (still hate having to do that though). The
>issue with insertion order may possibly not matter, as
>memtype_rb_check_conflict verifies that any overlapping ranges will
>have the same configured memory type. So maybe the order doesn't
>matter in the end ??? Not 100% sure about that one.

I've sent out a patch.

Thanks,
Davidlohr

Re: [PATCH v2 2/3] augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro

[Michel Lespinasse]

On Tue, Aug 13, 2019 at 05:06:16PM -0700, Davidlohr Bueso wrote:
> On Tue, 02 Jul 2019, Michel Lespinasse wrote:
> > - The majority of interval tree users (though either the
> > interval_tree.h or the interval_tree_generic.h API) do not store any
> > overlapping intervals, and as such they really don't have any reason
> > to use an augmented rbtree in the first place. This seems to be true
> > for at least drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c,
> > drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c, drivers/gpu/drm/drm_mm.c,
> > drivers/gpu/drm/radeon/radeon_mn.c,
> > drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c, and probably
> > (not 100% sure) also drivers/infiniband/hw/hfi1/mmu_rb.c and
> > drivers/vhost/vhost.c. I think the reason they do that is because they
> > like to have the auto-generated insert / remove / iter functions
> > rather than writing their own as they would have to do through the
> > base rbtree API. Not necessarily a huge problem but it is annoying
> > when working on inteval tree to consider that the data structure is
> > not optimal for most of its users.
> 
> I think the patch I sent earlier will add to your unhappiness.

Not really, I think the pat conversion is a good idea though I am
confused about the interval definitions (open or closed ?) in your
patch set.

> > - The intervals are represented as [start, last], where most
> > everything else in the kernel uses [start, end[ (with last == end -
> > 1). The reason it was done that way was for stabbing queries - I
> > thought these would be nicer to represent as a [stab, stab] interval
> > rather than [stab, stab+1[. But, things didn't turn out that way
> > because of huge pages, and we end up with stabbing queries in the
> > [stab, stab + page_size - 1] format, at which point we could just as
> > easily go for [stab, stab + page_size[ representation. Having looked
> > into it, my understanding is that *all* current users of the interval
> > tree API would be better served if the intervals were represented as
> > [start, end[ like everywhere else in the kernel.

Do you have any thoughts about changing the interval tree definitions
to use half-open intervals like everywhere else in the kernel ?

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.