Skip to contentSkip to conversation

make RB_DECLARE_CALLBACKS more generic

PATCH Superseded Michel Lespinasse 3 participants 11 messages Jul 2, 2019 – Aug 21, 2019

Subsystems (7)

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

v2 cover make RB_DECLARE_CALLBACKS more generic

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(-)
Signature · 1 line
2.22.0.410.gd8fdbe21b5-goog
#1 lore raw

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

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.

---
 include/linux/rbtree_augmented.h       | 54 ++++++++++++++++----------
 tools/include/linux/rbtree_augmented.h | 54 ++++++++++++++++----------
 2 files changed, 66 insertions(+), 42 deletions(-)
include/linux/rbtree_augmented.h +33 -21
index f1ed3fc80bbb..5923495276e0 100644
@@ -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					\
 };
 
 
tools/include/linux/rbtree_augmented.h +33 -21

72 lines not on this page · raw message

Signature · 1 line
2.22.0.410.gd8fdbe21b5-goog
Acked-by on v2 1/3
#2 lore raw

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

Quoted 7 lines · 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.

#3 lore raw

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

In reply to 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.

---
 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(-)
arch/x86/mm/pat_rbtree.c +3 -16
index fa16036fa592..2afad8e869fc 100644
@@ -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,
drivers/block/drbd/drbd_interval.c +3 -26
index c58986556161..3a507a1fd1e3 100644
@@ -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
include/linux/interval_tree_generic.h +2 -20
index 1f97ce26cccc..8a9fcfb25157 100644
@@ -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 */			      \
 									      \
include/linux/rbtree_augmented.h +35 -1
index 5923495276e0..a471702c01e7 100644
@@ -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
lib/rbtree_test.c +3 -19
index b7055b2a07d3..b876f8e73897 100644
@@ -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)
mm/mmap.c +18 -11
index bd7b9f293b39..cd293c794975 100644
@@ -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);
 }
tools/include/linux/rbtree_augmented.h +35 -1
index ca25818714d3..4db1dcaf90b2 100644
@@ -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
Signature · 1 line
2.22.0.410.gd8fdbe21b5-goog
#4 lore raw

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

Quoted 18 lines · Michel Lespinasse
arch/x86/mm/pat_rbtree.c +0 -10
index fa16036fa592..2afad8e869fc 100644
@@ -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)

arch/x86/mm/pat_rbtree.c static u64 get_subtree_max_end(struct rb_node *node) · line 60

Quoted 10 lines
arch/x86/mm/pat_rbtree.c +3 -6
-		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

#5 lore raw

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

Quoted 44 lines · Davidlohr Bueso
Quoted 18 lines · Michel Lespinasse
arch/x86/mm/pat_rbtree.c +0 -10
index fa16036fa592..2afad8e869fc 100644
@@ -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)

arch/x86/mm/pat_rbtree.c static u64 get_subtree_max_end(struct rb_node *node) · line 60

Quoted 10 lines
arch/x86/mm/pat_rbtree.c +3 -6
-              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.

Quoted 4 lines

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 ?

Signature · 2 lines
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
#6 lore raw

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

Quoted 2 lines · Michel Lespinasse

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.

Quoted 16 lines

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

Quoted 24 lines

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

Quoted 8 lines

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

Quoted 9 lines

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

#7 lore raw

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

Quoted 17 lines · Davidlohr Bueso
Quoted 7 lines · Michel Lespinasse

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

Quoted 8 lines

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.

Quoted 1 line

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.

Quoted 11 lines
Quoted 11 lines

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

Signature · 2 lines
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
#8 lore raw

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

In reply to 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.

---
 include/linux/rbtree_augmented.h       | 28 +++++++++++++-------------
 tools/include/linux/rbtree_augmented.h | 28 +++++++++++++-------------
 2 files changed, 28 insertions(+), 28 deletions(-)
include/linux/rbtree_augmented.h +14 -14
index a471702c01e7..f8780a67ec04 100644
@@ -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
tools/include/linux/rbtree_augmented.h +14 -14
index 4db1dcaf90b2..b5845898c2d8 100644
@@ -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
Signature · 1 line
2.22.0.410.gd8fdbe21b5-goog
maintainer
#9 lore raw

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

Quoted 9 lines · 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.

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

Quoted 3 lines

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

Quoted 2 lines

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.

#10 lore raw

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

Quoted 7 lines · Peter Zijlstra
Quoted 3 lines

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

Signature · 2 lines
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.