[PATCH 0/2] make RB_DECLARE_CALLBACKS more generic

[PATCH 0/2] 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().

Michel Lespinasse (2):
  augmented rbtree: add comments for RB_DECLARE_CALLBACKS macro
  augmented rbtree: rework the RB_DECLARE_CALLBACKS macro definition

 arch/x86/mm/pat_rbtree.c               | 11 ++++--
 drivers/block/drbd/drbd_interval.c     | 13 ++++---
 include/linux/interval_tree_generic.h  | 13 +++++--
 include/linux/rbtree_augmented.h       | 51 +++++++++++++++-----------
 lib/rbtree_test.c                      | 11 ++++--
 mm/mmap.c                              | 26 ++++++++-----
 tools/include/linux/rbtree_augmented.h | 51 +++++++++++++++-----------
 7 files changed, 107 insertions(+), 69 deletions(-)

-- 
2.22.0.410.gd8fdbe21b5-goog

[PATCH 1/2] 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 +++++++++++++++++++-------------
 1 file changed, 33 insertions(+), 21 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					\
 };
 
 
-- 
2.22.0.410.gd8fdbe21b5-goog

[PATCH 2/2] 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 generated code should not change when the RBCOMPUTE function is inlined,
which is the typical / intended case.

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>
---
 arch/x86/mm/pat_rbtree.c               | 11 ++++--
 drivers/block/drbd/drbd_interval.c     | 13 ++++---
 include/linux/interval_tree_generic.h  | 13 +++++--
 include/linux/rbtree_augmented.h       | 17 ++++-----
 lib/rbtree_test.c                      | 11 ++++--
 mm/mmap.c                              | 26 ++++++++-----
 tools/include/linux/rbtree_augmented.h | 51 +++++++++++++++-----------
 7 files changed, 84 insertions(+), 58 deletions(-)

diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c
index fa16036fa592..f1701f6e3c49 100644
--- a/arch/x86/mm/pat_rbtree.c
+++ b/arch/x86/mm/pat_rbtree.c
@@ -54,7 +54,7 @@ static u64 get_subtree_max_end(struct rb_node *node)
 	return ret;
 }
 
-static u64 compute_subtree_max_end(struct memtype *data)
+static inline bool compute_subtree_max_end(struct memtype *data, bool exit)
 {
 	u64 max_end = data->end, child_max_end;
 
@@ -66,11 +66,14 @@ static u64 compute_subtree_max_end(struct memtype *data)
 	if (child_max_end > max_end)
 		max_end = child_max_end;
 
-	return max_end;
+	if (exit && data->subtree_max_end == max_end)
+		return true;
+	data->subtree_max_end = max_end;
+	return false;
 }
 
-RB_DECLARE_CALLBACKS(static, memtype_rb_augment_cb, struct memtype, rb,
-		     u64, subtree_max_end, compute_subtree_max_end)
+RB_DECLARE_CALLBACKS(struct memtype, rb, subtree_max_end,
+		     compute_subtree_max_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..6decee82a797 100644
--- a/drivers/block/drbd/drbd_interval.c
+++ b/drivers/block/drbd/drbd_interval.c
@@ -20,8 +20,8 @@ sector_t interval_end(struct rb_node *node)
  * 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)
+static inline bool
+compute_subtree_last(struct drbd_interval *node, bool exit)
 {
 	sector_t max = node->sector + (node->size >> 9);
 
@@ -35,11 +35,14 @@ compute_subtree_last(struct drbd_interval *node)
 		if (right > max)
 			max = right;
 	}
-	return max;
+	if (exit && node->end == max)
+		return true;
+	node->end = max;
+	return false;
 }
 
-RB_DECLARE_CALLBACKS(static, augment_callbacks, struct drbd_interval, rb,
-		     sector_t, end, compute_subtree_last);
+RB_DECLARE_CALLBACKS(struct drbd_interval, rb, end, compute_subtree_last,
+		     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..c54ce9ea152d 100644
--- a/include/linux/interval_tree_generic.h
+++ b/include/linux/interval_tree_generic.h
@@ -42,7 +42,8 @@
 									      \
 /* Callbacks for augmented rbtree insert and remove */			      \
 									      \
-static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node)	      \
+static inline bool ITPREFIX ## _compute_subtree_last(ITSTRUCT *node,	      \
+						     bool exit)		      \
 {									      \
 	ITTYPE max = ITLAST(node), subtree_last;			      \
 	if (node->ITRB.rb_left) {					      \
@@ -57,11 +58,15 @@ static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node)	      \
 		if (max < subtree_last)					      \
 			max = subtree_last;				      \
 	}								      \
-	return max;							      \
+	if (exit && node->ITSUBTREE == max)				      \
+		return true;						      \
+	node->ITSUBTREE = max;						      \
+	return false;							      \
 }									      \
 									      \
-RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB,	      \
-		     ITTYPE, ITSUBTREE, ITPREFIX ## _compute_subtree_last)    \
+RB_DECLARE_CALLBACKS(ITSTRUCT, ITRB, ITSUBTREE,				      \
+		     ITPREFIX ## _compute_subtree_last,			      \
+		     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..a490ba61a1d0 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
  *
- * 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,				\
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index b7055b2a07d3..759cce3d6763 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -76,7 +76,7 @@ static inline void erase_cached(struct test_node *node, struct rb_root_cached *r
 }
 
 
-static inline u32 augment_recompute(struct test_node *node)
+static inline bool augment_recompute(struct test_node *node, bool exit)
 {
 	u32 max = node->val, child_augmented;
 	if (node->rb.rb_left) {
@@ -91,11 +91,14 @@ static inline u32 augment_recompute(struct test_node *node)
 		if (max < child_augmented)
 			max = child_augmented;
 	}
-	return max;
+	if (exit && node->augmented == max)
+		return true;
+	node->augmented = max;
+	return false;
 }
 
-RB_DECLARE_CALLBACKS(static, augment_callbacks, struct test_node, rb,
-		     u32, augmented, augment_recompute)
+RB_DECLARE_CALLBACKS(struct test_node, rb, augmented, augment_recompute,
+		     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..f55a0e92c9b6 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -288,7 +288,7 @@ SYSCALL_DEFINE1(brk, unsigned long, brk)
 	return retval;
 }
 
-static long vma_compute_subtree_gap(struct vm_area_struct *vma)
+static bool vma_compute_subtree_gap(struct vm_area_struct *vma, bool exit)
 {
 	unsigned long max, prev_end, subtree_gap;
 
@@ -318,7 +318,10 @@ static long vma_compute_subtree_gap(struct vm_area_struct *vma)
 		if (subtree_gap > max)
 			max = subtree_gap;
 	}
-	return max;
+	if (exit && vma->rb_subtree_gap == max)
+		return true;
+	vma->rb_subtree_gap = max;
+	return false;
 }
 
 #ifdef CONFIG_DEBUG_VM_RB
@@ -330,6 +333,7 @@ static int browse_rb(struct mm_struct *mm)
 	unsigned long prev = 0, pend = 0;
 
 	for (nd = rb_first(root); nd; nd = rb_next(nd)) {
+		unsigned long gap;
 		struct vm_area_struct *vma;
 		vma = rb_entry(nd, struct vm_area_struct, vm_rb);
 		if (vma->vm_start < prev) {
@@ -348,10 +352,10 @@ static int browse_rb(struct mm_struct *mm)
 			bug = 1;
 		}
 		spin_lock(&mm->page_table_lock);
-		if (vma->rb_subtree_gap != vma_compute_subtree_gap(vma)) {
+		gap = vma->rb_subtree_gap;
+		if (!vma_compute_subtree_gap(vma, true)) {
 			pr_emerg("free gap %lx, correct %lx\n",
-			       vma->rb_subtree_gap,
-			       vma_compute_subtree_gap(vma));
+				gap, vma->rb_subtree_gap);
 			bug = 1;
 		}
 		spin_unlock(&mm->page_table_lock);
@@ -375,11 +379,13 @@ static void validate_mm_rb(struct rb_root *root, struct vm_area_struct *ignore)
 	struct rb_node *nd;
 
 	for (nd = rb_first(root); nd; nd = rb_next(nd)) {
+		unsigned long gap;
 		struct vm_area_struct *vma;
 		vma = rb_entry(nd, struct vm_area_struct, vm_rb);
-		VM_BUG_ON_VMA(vma != ignore &&
-			vma->rb_subtree_gap != vma_compute_subtree_gap(vma),
-			vma);
+		if (vma == ignore)
+			continue;
+		gap = vma->rb_subtree_gap;
+		VM_BUG_ON_VMA(!vma_compute_subtree_gap(vma, true), vma);
 	}
 }
 
@@ -427,8 +433,8 @@ 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(struct vm_area_struct, vm_rb, rb_subtree_gap,
+		     vma_compute_subtree_gap, static, vma_gap_callbacks)
 
 /*
  * Update augmented rbtree rb_subtree_gap values after vma->vm_start or
diff --git a/tools/include/linux/rbtree_augmented.h b/tools/include/linux/rbtree_augmented.h
index d008e1404580..ec60d1509efc 100644
--- a/tools/include/linux/rbtree_augmented.h
+++ b/tools/include/linux/rbtree_augmented.h
@@ -74,39 +74,48 @@ 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
+ *
+ * RBSTRUCT:    struct type of the tree nodes
+ * RBFIELD:     name of struct rb_node field within RBSTRUCT
+ * 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(RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE,	\
+			     RBSTATIC, RBNAME)				\
 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);	\
+		if (RBCOMPUTE(node, true))				\
 			break;						\
-		node->rbaugmented = augmented;				\
-		rb = rb_parent(&node->rbfield);				\
+		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;				\
+	RBCOMPUTE(old, false);						\
 }									\
-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

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

[Peter Zijlstra]

On Fri, Jun 28, 2019 at 05:49:52PM -0700, Michel Lespinasse wrote:
> --- a/tools/include/linux/rbtree_augmented.h
> +++ b/tools/include/linux/rbtree_augmented.h
> @@ -74,39 +74,48 @@ 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
> + *
> + * RBSTRUCT:    struct type of the tree nodes
> + * RBFIELD:     name of struct rb_node field within RBSTRUCT
> + * 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(RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE,	\
> +			     RBSTATIC, RBNAME)				\
>  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);	\
> +		if (RBCOMPUTE(node, true))				\
>  			break;						\
> -		node->rbaugmented = augmented;				\
> -		rb = rb_parent(&node->rbfield);				\
> +		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;				\
> +	RBCOMPUTE(old, false);						\
>  }									\
> -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					\
>  };

I'm thinking that should've been in the previous patch.

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

[Peter Zijlstra]

On Fri, Jun 28, 2019 at 05:49:52PM -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.
> 
> - 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 generated code should not change when the RBCOMPUTE function is inlined,
> which is the typical / intended case.

This seems something that shoud (:-) be easy to verify; no reason to be
uncertain about this. Either it does or does not change generated code.

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

> @@ -66,11 +66,14 @@ static u64 compute_subtree_max_end(struct memtype *data)
>  	if (child_max_end > max_end)
>  		max_end = child_max_end;
>  
> -	return max_end;
> +	if (exit && data->subtree_max_end == max_end)
> +		return true;
> +	data->subtree_max_end = max_end;
> +	return false;
>  }

> @@ -35,11 +35,14 @@ compute_subtree_last(struct drbd_interval *node)
>  		if (right > max)
>  			max = right;
>  	}
> -	return max;
> +	if (exit && node->end == max)
> +		return true;
> +	node->end = max;
> +	return false;
>  }

> @@ -57,11 +58,15 @@ static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node)	      \
>  		if (max < subtree_last)					      \
>  			max = subtree_last;				      \
>  	}								      \
> -	return max;							      \
> +	if (exit && node->ITSUBTREE == max)				      \
> +		return true;						      \
> +	node->ITSUBTREE = max;						      \
> +	return false;							      \
>  }									      \

> @@ -91,11 +91,14 @@ static inline u32 augment_recompute(struct test_node *node)
>  		if (max < child_augmented)
>  			max = child_augmented;
>  	}
> -	return max;
> +	if (exit && node->augmented == max)
> +		return true;
> +	node->augmented = max;
> +	return false;
>  }

> @@ -318,7 +318,10 @@ static long vma_compute_subtree_gap(struct vm_area_struct *vma)
>  		if (subtree_gap > max)
>  			max = subtree_gap;
>  	}
> -	return max;
> +	if (exit && vma->rb_subtree_gap == max)
> +		return true;
> +	vma->rb_subtree_gap = max;
> +	return false;
>  }

And that is _really_ unfortunate, as in 5 copies of exactly the same
logic sucks.

Can't we have a helper macro that converts an old (scalar) style compute
into a new style compute and avoid this unfortunate and error prone
copy/pasta ?

Something like:

#define RBCOMPUTE_SCALAR(_comp, _rb _exit)
({
	RBSTRUCT *node = rb_entry((_rb), RBSTRUCT, RBFIELD);
	RBTYPE augmented = _comp(node);
	bool ret = true;
	if (!((_exit) && node->RBAUGMENTED == augmented)) {
		node->RBAUGMENTED = augmented;
		ret = false;
	}
	ret;
})

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

[Peter Zijlstra]

On Mon, Jul 01, 2019 at 09:46:30AM +0200, Peter Zijlstra wrote:
> On Fri, Jun 28, 2019 at 05:49:52PM -0700, Michel Lespinasse wrote:

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

> Can't we have a helper macro that converts an old (scalar) style compute
> into a new style compute and avoid this unfortunate and error prone
> copy/pasta ?

Or add a RBEQUAL argument that does:

-		if (node->RBAUGMENTED == augmented)
+		if (RBEQUAL(&node->RBAUGMENTED, &augmented))

With a bit of foo you can even provide a default implementation that
does: *a == *b.

See GEN_UNARY_RMWcc() for how to do that.

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

[Michel Lespinasse]

I don't like adding additional levels of macros to build the augmented
rbtree callbacks. OTOH, all of the existing callbacks compute the max
(within the subtree) of a per-node scalar property. So, I guess I
could do a RB_DECLARE_MAX_CALLBACKS, and one of its arguments would
tell it how to compute the per-node scalar property, and it would
generate the code that both computes the max within the subtree and
assigns it into the augmented variable for the subtree's root. I will
prepare a v2 version of this patchset that does that.

On Mon, Jul 1, 2019 at 7:40 AM Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Mon, Jul 01, 2019 at 09:46:30AM +0200, Peter Zijlstra wrote:
> > On Fri, Jun 28, 2019 at 05:49:52PM -0700, Michel Lespinasse wrote:
>
> > > 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.
>
> > Can't we have a helper macro that converts an old (scalar) style compute
> > into a new style compute and avoid this unfortunate and error prone
> > copy/pasta ?
>
> Or add a RBEQUAL argument that does:
>
> -               if (node->RBAUGMENTED == augmented)
> +               if (RBEQUAL(&node->RBAUGMENTED, &augmented))
>
> With a bit of foo you can even provide a default implementation that
> does: *a == *b.
>
> See GEN_UNARY_RMWcc() for how to do that.



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