Skip to contentSkip to conversation

make RB_DECLARE_CALLBACKS more generic

PATCH Superseded Michel Lespinasse 2 participants 7 messages Jun 29, 2019 – Jul 2, 2019

Subsystems (7)

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

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

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

PATCH 1/2 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 +++++++++++++++++++-------------
 1 file changed, 33 insertions(+), 21 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					\
 };
 
 
Signature · 1 line
2.22.0.410.gd8fdbe21b5-goog
#2 lore raw

PATCH 2/2 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 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.

---
 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(-)
arch/x86/mm/pat_rbtree.c +7 -4
index fa16036fa592..f1701f6e3c49 100644
@@ -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,
drivers/block/drbd/drbd_interval.c +8 -5
index c58986556161..6decee82a797 100644
@@ -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
include/linux/interval_tree_generic.h +9 -4
index 1f97ce26cccc..c54ce9ea152d 100644
@@ -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 */			      \
 									      \
include/linux/rbtree_augmented.h +7 -10
index 5923495276e0..a490ba61a1d0 100644
@@ -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,				\
lib/rbtree_test.c +7 -4
index b7055b2a07d3..759cce3d6763 100644
@@ -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)
mm/mmap.c +16 -10
index bd7b9f293b39..f55a0e92c9b6 100644
@@ -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
tools/include/linux/rbtree_augmented.h +30 -21

69 lines not on this page · raw message

Signature · 1 line
2.22.0.410.gd8fdbe21b5-goog
maintainer
#3 lore raw

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

Quoted 60 lines · Michel Lespinasse
tools/include/linux/rbtree_augmented.h +26 -17
@@ -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);						\

tools/include/linux/rbtree_augmented.h rb_insert_augmented_cached(struct rb_node *node, · line 119

Quoted 10 lines
tools/include/linux/rbtree_augmented.h +4 -4
 }									\
-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.

maintainer
#4 lore raw

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

In reply to Michel Lespinasse
Quoted 10 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.

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

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.

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

arch/x86/mm/pat_rbtree.c +16 -4
@@ -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;
 }
 

arch/x86/mm/pat_rbtree.c static long vma_compute_subtree_gap(struct vm_area_struct *vma) · line 325

Quoted 9 lines
arch/x86/mm/pat_rbtree.c +4 -1
@@ -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;
})
maintainer
#5 lore raw

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

Quoted 8 lines · Peter Zijlstra
Quoted 2 lines · Michel Lespinasse

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.

#6 lore raw

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

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.

Quoted 20 lines · Peter Zijlstra
Quoted 8 lines · Peter Zijlstra
Quoted 2 lines · Michel Lespinasse

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:

(quoted diff) +1 -1
-               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.

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