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).
Changes since v2: Left the RBSTATIC and RBNAME arguments first in the
RB_DECLARE_CALLBACKS and RB_DECLARE_CALLBACKS_MAX macros as suggested
by Peter Zijlstra.
Changes since v1: I have added a new RB_DECLARE_CALLBACKS_MAX macro,
which generates augmented rbtree callbacks where the subtree information
can be expressed as max(f(node)). This covers all current uses, and thus
makes it easy to do the later RB_DECLARE_CALLBACKS definition change
as it's only currently used in RB_DECLARE_CALLBACKS_MAX.
I have also verified the compiled lib/interval_tree.o and mm/mmap.o
files to check that they didn't change. This held as expected for
interval_tree.o; mmap.o did have some changes which could be reverted
by marking __vma_link_rb as noinline. I did not add such a change to the
patchset; I felt it was reasonable enough to let the inlining decision
up to the compiler.
Michel Lespinasse (3):
augmented rbtree: add comments for RB_DECLARE_CALLBACKS macro
augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro
augmented rbtree: rework the RB_DECLARE_CALLBACKS macro definition
arch/x86/mm/pat_rbtree.c | 19 +-----
drivers/block/drbd/drbd_interval.c | 29 +--------
include/linux/interval_tree_generic.h | 22 +------
include/linux/rbtree_augmented.h | 88 ++++++++++++++++++++------
lib/rbtree_test.c | 22 +------
mm/mmap.c | 29 +++++----
tools/include/linux/rbtree_augmented.h | 88 ++++++++++++++++++++------
7 files changed, 163 insertions(+), 134 deletions(-)
--
2.22.0.410.gd8fdbe21b5-goog
Add RB_DECLARE_CALLBACKS_MAX, which generates augmented rbtree callbacks
for the case where the augmented value is a scalar whose definition
follows a max(f(node)) pattern. This actually covers all present uses
of RB_DECLARE_CALLBACKS, and saves some (source) code duplication in the
various RBCOMPUTE function definitions.
Signed-off-by: Michel Lespinasse <[email protected]>
---
arch/x86/mm/pat_rbtree.c | 19 +++-----------
drivers/block/drbd/drbd_interval.c | 29 +++------------------
include/linux/interval_tree_generic.h | 22 ++--------------
include/linux/rbtree_augmented.h | 36 +++++++++++++++++++++++++-
lib/rbtree_test.c | 22 +++-------------
mm/mmap.c | 29 +++++++++++++--------
tools/include/linux/rbtree_augmented.h | 36 +++++++++++++++++++++++++-
7 files changed, 99 insertions(+), 94 deletions(-)
diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c
index fa16036fa592..65ebe4b88f7c 100644
--- a/arch/x86/mm/pat_rbtree.c
+++ b/arch/x86/mm/pat_rbtree.c
@@ -54,23 +54,10 @@ static u64 get_subtree_max_end(struct rb_node *node)
return ret;
}
-static u64 compute_subtree_max_end(struct memtype *data)
-{
- u64 max_end = data->end, child_max_end;
-
- child_max_end = get_subtree_max_end(data->rb.rb_right);
- if (child_max_end > max_end)
- max_end = child_max_end;
-
- child_max_end = get_subtree_max_end(data->rb.rb_left);
- if (child_max_end > max_end)
- max_end = child_max_end;
-
- return max_end;
-}
+#define NODE_END(node) ((node)->end)
-RB_DECLARE_CALLBACKS(static, memtype_rb_augment_cb, struct memtype, rb,
- u64, subtree_max_end, compute_subtree_max_end)
+RB_DECLARE_CALLBACKS_MAX(static, memtype_rb_augment_cb,
+ struct memtype, rb, u64, subtree_max_end, NODE_END)
/* 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..651bd0236a99 100644
--- a/drivers/block/drbd/drbd_interval.c
+++ b/drivers/block/drbd/drbd_interval.c
@@ -13,33 +13,10 @@ sector_t interval_end(struct rb_node *node)
return this->end;
}
-/**
- * compute_subtree_last - compute end of @node
- *
- * The end of an interval is the highest (start + (size >> 9)) value of this
- * node and of its children. Called for @node and its parents whenever the end
- * may have changed.
- */
-static inline sector_t
-compute_subtree_last(struct drbd_interval *node)
-{
- sector_t max = node->sector + (node->size >> 9);
-
- if (node->rb.rb_left) {
- sector_t left = interval_end(node->rb.rb_left);
- if (left > max)
- max = left;
- }
- if (node->rb.rb_right) {
- sector_t right = interval_end(node->rb.rb_right);
- if (right > max)
- max = right;
- }
- return max;
-}
+#define NODE_END(node) ((node)->sector + ((node)->size >> 9))
-RB_DECLARE_CALLBACKS(static, augment_callbacks, struct drbd_interval, rb,
- sector_t, end, compute_subtree_last);
+RB_DECLARE_CALLBACKS_MAX(static, augment_callbacks,
+ struct drbd_interval, rb, sector_t, end, NODE_END);
/**
* 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..205218a941e1 100644
--- a/include/linux/interval_tree_generic.h
+++ b/include/linux/interval_tree_generic.h
@@ -42,26 +42,8 @@
\
/* Callbacks for augmented rbtree insert and remove */ \
\
-static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node) \
-{ \
- ITTYPE max = ITLAST(node), subtree_last; \
- if (node->ITRB.rb_left) { \
- subtree_last = rb_entry(node->ITRB.rb_left, \
- ITSTRUCT, ITRB)->ITSUBTREE; \
- if (max < subtree_last) \
- max = subtree_last; \
- } \
- if (node->ITRB.rb_right) { \
- subtree_last = rb_entry(node->ITRB.rb_right, \
- ITSTRUCT, ITRB)->ITSUBTREE; \
- if (max < subtree_last) \
- max = subtree_last; \
- } \
- return max; \
-} \
- \
-RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB, \
- ITTYPE, ITSUBTREE, ITPREFIX ## _compute_subtree_last) \
+RB_DECLARE_CALLBACKS_MAX(static, ITPREFIX ## _augment, \
+ ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, ITLAST) \
\
/* Insert / remove interval nodes from the tree */ \
\
diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
index 5923495276e0..c5379d762fa9 100644
--- a/include/linux/rbtree_augmented.h
+++ b/include/linux/rbtree_augmented.h
@@ -73,7 +73,7 @@ rb_insert_augmented_cached(struct rb_node *node,
}
/*
- * Template for declaring augmented rbtree callbacks
+ * Template for declaring augmented rbtree callbacks (generic case)
*
* RBSTATIC: 'static' or empty
* RBNAME: name of the rb_augment_callbacks structure
@@ -119,6 +119,40 @@ RBSTATIC const struct rb_augment_callbacks RBNAME = { \
.rotate = RBNAME ## _rotate \
};
+/*
+ * Template for declaring augmented rbtree callbacks,
+ * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
+ *
+ * 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 returns the per-node RBTYPE scalar
+ */
+
+#define RB_DECLARE_CALLBACKS_MAX(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \
+ RBTYPE, RBAUGMENTED, RBCOMPUTE) \
+static inline RBTYPE RBNAME ## _compute_max(RBSTRUCT *node) \
+{ \
+ RBSTRUCT *child; \
+ RBTYPE max = RBCOMPUTE(node); \
+ if (node->RBFIELD.rb_left) { \
+ child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD); \
+ if (child->RBAUGMENTED > max) \
+ max = child->RBAUGMENTED; \
+ } \
+ if (node->RBFIELD.rb_right) { \
+ child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD); \
+ if (child->RBAUGMENTED > max) \
+ max = child->RBAUGMENTED; \
+ } \
+ return max; \
+} \
+RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \
+ RBTYPE, RBAUGMENTED, RBNAME ## _compute_max)
+
#define RB_RED 0
#define RB_BLACK 1
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index b7055b2a07d3..2631bcaada41 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -76,26 +76,10 @@ static inline void erase_cached(struct test_node *node, struct rb_root_cached *r
}
-static inline u32 augment_recompute(struct test_node *node)
-{
- u32 max = node->val, child_augmented;
- if (node->rb.rb_left) {
- child_augmented = rb_entry(node->rb.rb_left, struct test_node,
- rb)->augmented;
- if (max < child_augmented)
- max = child_augmented;
- }
- if (node->rb.rb_right) {
- child_augmented = rb_entry(node->rb.rb_right, struct test_node,
- rb)->augmented;
- if (max < child_augmented)
- max = child_augmented;
- }
- return max;
-}
+#define NODE_VAL(node) ((node)->val)
-RB_DECLARE_CALLBACKS(static, augment_callbacks, struct test_node, rb,
- u32, augmented, augment_recompute)
+RB_DECLARE_CALLBACKS_MAX(static, augment_callbacks,
+ struct test_node, rb, u32, augmented, NODE_VAL)
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..39ce2acf4ec3 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -288,9 +288,9 @@ SYSCALL_DEFINE1(brk, unsigned long, brk)
return retval;
}
-static long vma_compute_subtree_gap(struct vm_area_struct *vma)
+static inline unsigned long vma_compute_gap(struct vm_area_struct *vma)
{
- unsigned long max, prev_end, subtree_gap;
+ unsigned long gap, prev_end;
/*
* Note: in the rare case of a VM_GROWSDOWN above a VM_GROWSUP, we
@@ -298,14 +298,21 @@ static long vma_compute_subtree_gap(struct vm_area_struct *vma)
* an unmapped area; whereas when expanding we only require one.
* That's a little inconsistent, but keeps the code here simpler.
*/
- max = vm_start_gap(vma);
+ gap = vm_start_gap(vma);
if (vma->vm_prev) {
prev_end = vm_end_gap(vma->vm_prev);
- if (max > prev_end)
- max -= prev_end;
+ if (gap > prev_end)
+ gap -= prev_end;
else
- max = 0;
+ gap = 0;
}
+ return gap;
+}
+
+#ifdef CONFIG_DEBUG_VM_RB
+static unsigned long vma_compute_subtree_gap(struct vm_area_struct *vma)
+{
+ unsigned long max = vma_compute_gap(vma), subtree_gap;
if (vma->vm_rb.rb_left) {
subtree_gap = rb_entry(vma->vm_rb.rb_left,
struct vm_area_struct, vm_rb)->rb_subtree_gap;
@@ -321,7 +328,6 @@ static long vma_compute_subtree_gap(struct vm_area_struct *vma)
return max;
}
-#ifdef CONFIG_DEBUG_VM_RB
static int browse_rb(struct mm_struct *mm)
{
struct rb_root *root = &mm->mm_rb;
@@ -427,8 +433,9 @@ static void validate_mm(struct mm_struct *mm)
#define validate_mm(mm) do { } while (0)
#endif
-RB_DECLARE_CALLBACKS(static, vma_gap_callbacks, struct vm_area_struct, vm_rb,
- unsigned long, rb_subtree_gap, vma_compute_subtree_gap)
+RB_DECLARE_CALLBACKS_MAX(static, vma_gap_callbacks,
+ struct vm_area_struct, vm_rb,
+ unsigned long, rb_subtree_gap, vma_compute_gap)
/*
* Update augmented rbtree rb_subtree_gap values after vma->vm_start or
@@ -438,8 +445,8 @@ RB_DECLARE_CALLBACKS(static, vma_gap_callbacks, struct vm_area_struct, vm_rb,
static void vma_gap_update(struct vm_area_struct *vma)
{
/*
- * As it turns out, RB_DECLARE_CALLBACKS() already created a callback
- * function that does exactly what we want.
+ * As it turns out, RB_DECLARE_CALLBACKS_MAX() already created
+ * a callback function that does exactly what we want.
*/
vma_gap_callbacks_propagate(&vma->vm_rb, NULL);
}
diff --git a/tools/include/linux/rbtree_augmented.h b/tools/include/linux/rbtree_augmented.h
index f46c1bf91f64..10a2f3f8c801 100644
--- a/tools/include/linux/rbtree_augmented.h
+++ b/tools/include/linux/rbtree_augmented.h
@@ -75,7 +75,7 @@ rb_insert_augmented_cached(struct rb_node *node,
}
/*
- * Template for declaring augmented rbtree callbacks
+ * Template for declaring augmented rbtree callbacks (generic case)
*
* RBSTATIC: 'static' or empty
* RBNAME: name of the rb_augment_callbacks structure
@@ -121,6 +121,40 @@ RBSTATIC const struct rb_augment_callbacks RBNAME = { \
.rotate = RBNAME ## _rotate \
};
+/*
+ * Template for declaring augmented rbtree callbacks,
+ * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
+ *
+ * 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 returns the per-node RBTYPE scalar
+ */
+
+#define RB_DECLARE_CALLBACKS_MAX(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \
+ RBTYPE, RBAUGMENTED, RBCOMPUTE) \
+static inline RBTYPE RBNAME ## _compute_max(RBSTRUCT *node) \
+{ \
+ RBSTRUCT *child; \
+ RBTYPE max = RBCOMPUTE(node); \
+ if (node->RBFIELD.rb_left) { \
+ child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD); \
+ if (child->RBAUGMENTED > max) \
+ max = child->RBAUGMENTED; \
+ } \
+ if (node->RBFIELD.rb_right) { \
+ child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD); \
+ if (child->RBAUGMENTED > max) \
+ max = child->RBAUGMENTED; \
+ } \
+ return max; \
+} \
+RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \
+ RBTYPE, RBAUGMENTED, RBNAME ## _compute_max)
+
#define RB_RED 0
#define RB_BLACK 1
--
2.22.0.410.gd8fdbe21b5-goog
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.
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 <[email protected]>
---
include/linux/rbtree_augmented.h | 24 ++++++++++++------------
tools/include/linux/rbtree_augmented.h | 24 ++++++++++++------------
2 files changed, 24 insertions(+), 24 deletions(-)
diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
index c5379d762fa9..b5e1c248d991 100644
--- a/include/linux/rbtree_augmented.h
+++ b/include/linux/rbtree_augmented.h
@@ -79,22 +79,19 @@ rb_insert_augmented_cached(struct rb_node *node,
* 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
*/
-#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \
- RBTYPE, RBAUGMENTED, RBCOMPUTE) \
+#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, \
+ RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE) \
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(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \
RBTYPE, RBAUGMENTED, RBCOMPUTE) \
-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(RBSTATIC, RBNAME, \
+ RBSTRUCT, RBFIELD, RBAUGMENTED, RBNAME ## _compute_max)
#define RB_RED 0
diff --git a/tools/include/linux/rbtree_augmented.h b/tools/include/linux/rbtree_augmented.h
index 10a2f3f8c801..6e21487fe33d 100644
--- a/tools/include/linux/rbtree_augmented.h
+++ b/tools/include/linux/rbtree_augmented.h
@@ -81,22 +81,19 @@ rb_insert_augmented_cached(struct rb_node *node,
* 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
*/
-#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \
- RBTYPE, RBAUGMENTED, RBCOMPUTE) \
+#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, \
+ RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE) \
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(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \
RBTYPE, RBAUGMENTED, RBCOMPUTE) \
-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(RBSTATIC, RBNAME, \
+ RBSTRUCT, RBFIELD, RBAUGMENTED, RBNAME ## _compute_max)
#define RB_RED 0
--
2.22.0.410.gd8fdbe21b5-goog
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 <[email protected]>
Acked-by: Davidlohr Bueso <[email protected]>
---
include/linux/rbtree_augmented.h | 54 ++++++++++++++++----------
tools/include/linux/rbtree_augmented.h | 54 ++++++++++++++++----------
2 files changed, 66 insertions(+), 42 deletions(-)
diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
index f1ed3fc80bbb..5923495276e0 100644
--- a/include/linux/rbtree_augmented.h
+++ b/include/linux/rbtree_augmented.h
@@ -72,39 +72,51 @@ rb_insert_augmented_cached(struct rb_node *node,
rb_insert_augmented(node, &root->rb_root, augment);
}
-#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
- rbtype, rbaugmented, rbcompute) \
+/*
+ * Template for declaring augmented rbtree callbacks
+ *
+ * RBSTATIC: 'static' or empty
+ * RBNAME: name of the rb_augment_callbacks structure
+ * RBSTRUCT: struct type of the tree nodes
+ * RBFIELD: name of struct rb_node field within RBSTRUCT
+ * RBTYPE: type of the RBAUGMENTED field
+ * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree
+ * RBCOMPUTE: name of function that recomputes the RBAUGMENTED data
+ */
+
+#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \
+ RBTYPE, RBAUGMENTED, RBCOMPUTE) \
static inline void \
-rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
+RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop) \
{ \
while (rb != stop) { \
- rbstruct *node = rb_entry(rb, rbstruct, rbfield); \
- rbtype augmented = rbcompute(node); \
- if (node->rbaugmented == augmented) \
+ RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD); \
+ RBTYPE augmented = RBCOMPUTE(node); \
+ if (node->RBAUGMENTED == augmented) \
break; \
- node->rbaugmented = augmented; \
- rb = rb_parent(&node->rbfield); \
+ node->RBAUGMENTED = augmented; \
+ rb = rb_parent(&node->RBFIELD); \
} \
} \
static inline void \
-rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
+RBNAME ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
{ \
- rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
- rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
- new->rbaugmented = old->rbaugmented; \
+ RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD); \
+ RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD); \
+ new->RBAUGMENTED = old->RBAUGMENTED; \
} \
static void \
-rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
+RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
{ \
- rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
- rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
- new->rbaugmented = old->rbaugmented; \
- old->rbaugmented = rbcompute(old); \
+ RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD); \
+ RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD); \
+ new->RBAUGMENTED = old->RBAUGMENTED; \
+ old->RBAUGMENTED = RBCOMPUTE(old); \
} \
-rbstatic const struct rb_augment_callbacks rbname = { \
- .propagate = rbname ## _propagate, \
- .copy = rbname ## _copy, \
- .rotate = rbname ## _rotate \
+RBSTATIC const struct rb_augment_callbacks RBNAME = { \
+ .propagate = RBNAME ## _propagate, \
+ .copy = RBNAME ## _copy, \
+ .rotate = RBNAME ## _rotate \
};
diff --git a/tools/include/linux/rbtree_augmented.h b/tools/include/linux/rbtree_augmented.h
index 372a539314af..f46c1bf91f64 100644
--- a/tools/include/linux/rbtree_augmented.h
+++ b/tools/include/linux/rbtree_augmented.h
@@ -74,39 +74,51 @@ rb_insert_augmented_cached(struct rb_node *node,
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
On Tue, Jul 02, 2019 at 09:01:53PM -0700, Michel Lespinasse wrote:
> 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).
>
> Changes since v2: Left the RBSTATIC and RBNAME arguments first in the
> RB_DECLARE_CALLBACKS and RB_DECLARE_CALLBACKS_MAX macros as suggested
> by Peter Zijlstra.
>
> 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
Thanks Michel, looking good now!
Acked-by: Peter Zijlstra (Intel) <[email protected]>
Syncing up with v5.2, I see that there is a new use for augmented
rbtrees in mm/vmalloc.c which does not compile after applying my
patchset.
It's an easy fix though:
diff --git mm/vmalloc.c mm/vmalloc.c
index 0f76cca32a1c..fe2e8892188b 100644
--- mm/vmalloc.c
+++ mm/vmalloc.c
@@ -391,9 +391,8 @@ compute_subtree_max_size(struct vmap_area *va)
get_subtree_max_size(va->rb_node.rb_right));
}
-RB_DECLARE_CALLBACKS(static, free_vmap_area_rb_augment_cb,
- struct vmap_area, rb_node, unsigned long, subtree_max_size,
- compute_subtree_max_size)
+RB_DECLARE_CALLBACKS_MAX(static, free_vmap_area_rb_augment_cb,
+ struct vmap_area, rb_node, unsigned long, subtree_max_size, va_size)
static void purge_vmap_area_lazy(void);
static BLOCKING_NOTIFIER_HEAD(vmap_notify_list);
(probably going to get mangled by gmail, but the gist of it is that
RB_DECLARE_CALLBACKS is replaced by RB_DECLARE_CALLBACKS_MAX and the
compute_subtree_max_size argument is replaced by va_size)
Note for Uladzislau Rezki, I noticed that the new augmented rbtree
code defines its own augment_tree_propagate_from function to update
the augmented subtree information after a node is modified; it would
probably be feasible to rely on the generated
free_vmap_area_rb_augment_cb_propagate function instead. mm/mmap.c
does something similar in vma_gap_update(), for a very similar use
case.
On Tue, Jul 2, 2019 at 9:02 PM Michel Lespinasse <[email protected]> wrote:
>
> Add RB_DECLARE_CALLBACKS_MAX, which generates augmented rbtree callbacks
> for the case where the augmented value is a scalar whose definition
> follows a max(f(node)) pattern. This actually covers all present uses
> of RB_DECLARE_CALLBACKS, and saves some (source) code duplication in the
> various RBCOMPUTE function definitions.
>
> Signed-off-by: Michel Lespinasse <[email protected]>
> ---
> arch/x86/mm/pat_rbtree.c | 19 +++-----------
> drivers/block/drbd/drbd_interval.c | 29 +++------------------
> include/linux/interval_tree_generic.h | 22 ++--------------
> include/linux/rbtree_augmented.h | 36 +++++++++++++++++++++++++-
> lib/rbtree_test.c | 22 +++-------------
> mm/mmap.c | 29 +++++++++++++--------
> tools/include/linux/rbtree_augmented.h | 36 +++++++++++++++++++++++++-
> 7 files changed, 99 insertions(+), 94 deletions(-)
>
> diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c
> index fa16036fa592..65ebe4b88f7c 100644
> --- a/arch/x86/mm/pat_rbtree.c
> +++ b/arch/x86/mm/pat_rbtree.c
> @@ -54,23 +54,10 @@ static u64 get_subtree_max_end(struct rb_node *node)
> return ret;
> }
>
> -static u64 compute_subtree_max_end(struct memtype *data)
> -{
> - u64 max_end = data->end, child_max_end;
> -
> - child_max_end = get_subtree_max_end(data->rb.rb_right);
> - if (child_max_end > max_end)
> - max_end = child_max_end;
> -
> - child_max_end = get_subtree_max_end(data->rb.rb_left);
> - if (child_max_end > max_end)
> - max_end = child_max_end;
> -
> - return max_end;
> -}
> +#define NODE_END(node) ((node)->end)
>
> -RB_DECLARE_CALLBACKS(static, memtype_rb_augment_cb, struct memtype, rb,
> - u64, subtree_max_end, compute_subtree_max_end)
> +RB_DECLARE_CALLBACKS_MAX(static, memtype_rb_augment_cb,
> + struct memtype, rb, u64, subtree_max_end, NODE_END)
>
> /* 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..651bd0236a99 100644
> --- a/drivers/block/drbd/drbd_interval.c
> +++ b/drivers/block/drbd/drbd_interval.c
> @@ -13,33 +13,10 @@ sector_t interval_end(struct rb_node *node)
> return this->end;
> }
>
> -/**
> - * compute_subtree_last - compute end of @node
> - *
> - * The end of an interval is the highest (start + (size >> 9)) value of this
> - * node and of its children. Called for @node and its parents whenever the end
> - * may have changed.
> - */
> -static inline sector_t
> -compute_subtree_last(struct drbd_interval *node)
> -{
> - sector_t max = node->sector + (node->size >> 9);
> -
> - if (node->rb.rb_left) {
> - sector_t left = interval_end(node->rb.rb_left);
> - if (left > max)
> - max = left;
> - }
> - if (node->rb.rb_right) {
> - sector_t right = interval_end(node->rb.rb_right);
> - if (right > max)
> - max = right;
> - }
> - return max;
> -}
> +#define NODE_END(node) ((node)->sector + ((node)->size >> 9))
>
> -RB_DECLARE_CALLBACKS(static, augment_callbacks, struct drbd_interval, rb,
> - sector_t, end, compute_subtree_last);
> +RB_DECLARE_CALLBACKS_MAX(static, augment_callbacks,
> + struct drbd_interval, rb, sector_t, end, NODE_END);
>
> /**
> * 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..205218a941e1 100644
> --- a/include/linux/interval_tree_generic.h
> +++ b/include/linux/interval_tree_generic.h
> @@ -42,26 +42,8 @@
> \
> /* Callbacks for augmented rbtree insert and remove */ \
> \
> -static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node) \
> -{ \
> - ITTYPE max = ITLAST(node), subtree_last; \
> - if (node->ITRB.rb_left) { \
> - subtree_last = rb_entry(node->ITRB.rb_left, \
> - ITSTRUCT, ITRB)->ITSUBTREE; \
> - if (max < subtree_last) \
> - max = subtree_last; \
> - } \
> - if (node->ITRB.rb_right) { \
> - subtree_last = rb_entry(node->ITRB.rb_right, \
> - ITSTRUCT, ITRB)->ITSUBTREE; \
> - if (max < subtree_last) \
> - max = subtree_last; \
> - } \
> - return max; \
> -} \
> - \
> -RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB, \
> - ITTYPE, ITSUBTREE, ITPREFIX ## _compute_subtree_last) \
> +RB_DECLARE_CALLBACKS_MAX(static, ITPREFIX ## _augment, \
> + ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, ITLAST) \
> \
> /* Insert / remove interval nodes from the tree */ \
> \
> diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
> index 5923495276e0..c5379d762fa9 100644
> --- a/include/linux/rbtree_augmented.h
> +++ b/include/linux/rbtree_augmented.h
> @@ -73,7 +73,7 @@ rb_insert_augmented_cached(struct rb_node *node,
> }
>
> /*
> - * Template for declaring augmented rbtree callbacks
> + * Template for declaring augmented rbtree callbacks (generic case)
> *
> * RBSTATIC: 'static' or empty
> * RBNAME: name of the rb_augment_callbacks structure
> @@ -119,6 +119,40 @@ RBSTATIC const struct rb_augment_callbacks RBNAME = { \
> .rotate = RBNAME ## _rotate \
> };
>
> +/*
> + * Template for declaring augmented rbtree callbacks,
> + * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
> + *
> + * 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 returns the per-node RBTYPE scalar
> + */
> +
> +#define RB_DECLARE_CALLBACKS_MAX(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \
> + RBTYPE, RBAUGMENTED, RBCOMPUTE) \
> +static inline RBTYPE RBNAME ## _compute_max(RBSTRUCT *node) \
> +{ \
> + RBSTRUCT *child; \
> + RBTYPE max = RBCOMPUTE(node); \
> + if (node->RBFIELD.rb_left) { \
> + child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD); \
> + if (child->RBAUGMENTED > max) \
> + max = child->RBAUGMENTED; \
> + } \
> + if (node->RBFIELD.rb_right) { \
> + child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD); \
> + if (child->RBAUGMENTED > max) \
> + max = child->RBAUGMENTED; \
> + } \
> + return max; \
> +} \
> +RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \
> + RBTYPE, RBAUGMENTED, RBNAME ## _compute_max)
> +
>
> #define RB_RED 0
> #define RB_BLACK 1
> diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
> index b7055b2a07d3..2631bcaada41 100644
> --- a/lib/rbtree_test.c
> +++ b/lib/rbtree_test.c
> @@ -76,26 +76,10 @@ static inline void erase_cached(struct test_node *node, struct rb_root_cached *r
> }
>
>
> -static inline u32 augment_recompute(struct test_node *node)
> -{
> - u32 max = node->val, child_augmented;
> - if (node->rb.rb_left) {
> - child_augmented = rb_entry(node->rb.rb_left, struct test_node,
> - rb)->augmented;
> - if (max < child_augmented)
> - max = child_augmented;
> - }
> - if (node->rb.rb_right) {
> - child_augmented = rb_entry(node->rb.rb_right, struct test_node,
> - rb)->augmented;
> - if (max < child_augmented)
> - max = child_augmented;
> - }
> - return max;
> -}
> +#define NODE_VAL(node) ((node)->val)
>
> -RB_DECLARE_CALLBACKS(static, augment_callbacks, struct test_node, rb,
> - u32, augmented, augment_recompute)
> +RB_DECLARE_CALLBACKS_MAX(static, augment_callbacks,
> + struct test_node, rb, u32, augmented, NODE_VAL)
>
> 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..39ce2acf4ec3 100644
> --- a/mm/mmap.c
> +++ b/mm/mmap.c
> @@ -288,9 +288,9 @@ SYSCALL_DEFINE1(brk, unsigned long, brk)
> return retval;
> }
>
> -static long vma_compute_subtree_gap(struct vm_area_struct *vma)
> +static inline unsigned long vma_compute_gap(struct vm_area_struct *vma)
> {
> - unsigned long max, prev_end, subtree_gap;
> + unsigned long gap, prev_end;
>
> /*
> * Note: in the rare case of a VM_GROWSDOWN above a VM_GROWSUP, we
> @@ -298,14 +298,21 @@ static long vma_compute_subtree_gap(struct vm_area_struct *vma)
> * an unmapped area; whereas when expanding we only require one.
> * That's a little inconsistent, but keeps the code here simpler.
> */
> - max = vm_start_gap(vma);
> + gap = vm_start_gap(vma);
> if (vma->vm_prev) {
> prev_end = vm_end_gap(vma->vm_prev);
> - if (max > prev_end)
> - max -= prev_end;
> + if (gap > prev_end)
> + gap -= prev_end;
> else
> - max = 0;
> + gap = 0;
> }
> + return gap;
> +}
> +
> +#ifdef CONFIG_DEBUG_VM_RB
> +static unsigned long vma_compute_subtree_gap(struct vm_area_struct *vma)
> +{
> + unsigned long max = vma_compute_gap(vma), subtree_gap;
> if (vma->vm_rb.rb_left) {
> subtree_gap = rb_entry(vma->vm_rb.rb_left,
> struct vm_area_struct, vm_rb)->rb_subtree_gap;
> @@ -321,7 +328,6 @@ static long vma_compute_subtree_gap(struct vm_area_struct *vma)
> return max;
> }
>
> -#ifdef CONFIG_DEBUG_VM_RB
> static int browse_rb(struct mm_struct *mm)
> {
> struct rb_root *root = &mm->mm_rb;
> @@ -427,8 +433,9 @@ static void validate_mm(struct mm_struct *mm)
> #define validate_mm(mm) do { } while (0)
> #endif
>
> -RB_DECLARE_CALLBACKS(static, vma_gap_callbacks, struct vm_area_struct, vm_rb,
> - unsigned long, rb_subtree_gap, vma_compute_subtree_gap)
> +RB_DECLARE_CALLBACKS_MAX(static, vma_gap_callbacks,
> + struct vm_area_struct, vm_rb,
> + unsigned long, rb_subtree_gap, vma_compute_gap)
>
> /*
> * Update augmented rbtree rb_subtree_gap values after vma->vm_start or
> @@ -438,8 +445,8 @@ RB_DECLARE_CALLBACKS(static, vma_gap_callbacks, struct vm_area_struct, vm_rb,
> static void vma_gap_update(struct vm_area_struct *vma)
> {
> /*
> - * As it turns out, RB_DECLARE_CALLBACKS() already created a callback
> - * function that does exactly what we want.
> + * As it turns out, RB_DECLARE_CALLBACKS_MAX() already created
> + * a callback function that does exactly what we want.
> */
> vma_gap_callbacks_propagate(&vma->vm_rb, NULL);
> }
> diff --git a/tools/include/linux/rbtree_augmented.h b/tools/include/linux/rbtree_augmented.h
> index f46c1bf91f64..10a2f3f8c801 100644
> --- a/tools/include/linux/rbtree_augmented.h
> +++ b/tools/include/linux/rbtree_augmented.h
> @@ -75,7 +75,7 @@ rb_insert_augmented_cached(struct rb_node *node,
> }
>
> /*
> - * Template for declaring augmented rbtree callbacks
> + * Template for declaring augmented rbtree callbacks (generic case)
> *
> * RBSTATIC: 'static' or empty
> * RBNAME: name of the rb_augment_callbacks structure
> @@ -121,6 +121,40 @@ RBSTATIC const struct rb_augment_callbacks RBNAME = { \
> .rotate = RBNAME ## _rotate \
> };
>
> +/*
> + * Template for declaring augmented rbtree callbacks,
> + * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
> + *
> + * 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 returns the per-node RBTYPE scalar
> + */
> +
> +#define RB_DECLARE_CALLBACKS_MAX(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \
> + RBTYPE, RBAUGMENTED, RBCOMPUTE) \
> +static inline RBTYPE RBNAME ## _compute_max(RBSTRUCT *node) \
> +{ \
> + RBSTRUCT *child; \
> + RBTYPE max = RBCOMPUTE(node); \
> + if (node->RBFIELD.rb_left) { \
> + child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD); \
> + if (child->RBAUGMENTED > max) \
> + max = child->RBAUGMENTED; \
> + } \
> + if (node->RBFIELD.rb_right) { \
> + child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD); \
> + if (child->RBAUGMENTED > max) \
> + max = child->RBAUGMENTED; \
> + } \
> + return max; \
> +} \
> +RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \
> + RBTYPE, RBAUGMENTED, RBNAME ## _compute_max)
> +
>
> #define RB_RED 0
> #define RB_BLACK 1
> --
> 2.22.0.410.gd8fdbe21b5-goog
>
--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
On Mon, 8 Jul 2019 05:24:09 -0700 Michel Lespinasse <[email protected]> wrote:
> Syncing up with v5.2, I see that there is a new use for augmented
> rbtrees in mm/vmalloc.c which does not compile after applying my
> patchset.
>
> It's an easy fix though:
It still doesn't build.
lib/rbtree_test.c: In function check_augmented:
lib/rbtree_test.c:225:35: error: implicit declaration of function augment_recompute [-Werror=implicit-function-declaration]
WARN_ON_ONCE(node->augmented != augment_recompute(node));
I think I'll just do this:
--- a/lib/rbtree_test.c~augmented-rbtree-add-new-rb_declare_callbacks_max-macro-fix-2
+++ a/lib/rbtree_test.c
@@ -220,10 +220,6 @@ static void check_augmented(int nr_nodes
struct rb_node *rb;
check(nr_nodes);
- for (rb = rb_first(&root.rb_root); rb; rb = rb_next(rb)) {
- struct test_node *node = rb_entry(rb, struct test_node, rb);
- WARN_ON_ONCE(node->augmented != augment_recompute(node));
- }
}
static int __init rbtree_test_init(void)
although there may be something we can do here to restore the lost
coverage?
On Fri, Jul 26, 2019 at 06:44:19PM -0700, Andrew Morton wrote:
> On Mon, 8 Jul 2019 05:24:09 -0700 Michel Lespinasse <[email protected]> wrote:
>
> > Syncing up with v5.2, I see that there is a new use for augmented
> > rbtrees in mm/vmalloc.c which does not compile after applying my
> > patchset.
> >
> > It's an easy fix though:
>
> It still doesn't build.
>
> lib/rbtree_test.c: In function check_augmented:
> lib/rbtree_test.c:225:35: error: implicit declaration of function augment_recompute [-Werror=implicit-function-declaration]
> WARN_ON_ONCE(node->augmented != augment_recompute(node));
grumpf, sorry about that. I thought I had rbtree_test enabled in my
build, but turned out I only had interval_tree_test :/
I would suggest the following fix, which reintroduces the code to compute
node->augmented as was previously done in augment_recompute():
----------- 8< ----------------
After introducing RB_DECLARE_CALLBACKS_MAX, we do not need the
augment_recompute function to recompute node->augmented during
rbtree rebalancing callbacks. However, this function was also
used in check_augmented() to verify that node->augmented was
correctly set, so we need to reintroduce the code for that check.
Signed-off-by: Michel Lespinasse <[email protected]>
---
lib/rbtree_test.c | 15 ++++++++++++++-
1 file changed, 14 insertions(+), 1 deletion(-)
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index 1939419ba869..41ae3c7570d3 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -222,7 +222,20 @@ static void check_augmented(int nr_nodes)
check(nr_nodes);
for (rb = rb_first(&root.rb_root); rb; rb = rb_next(rb)) {
struct test_node *node = rb_entry(rb, struct test_node, rb);
- WARN_ON_ONCE(node->augmented != augment_recompute(node));
+ u32 subtree, max = node->val;
+ if (node->rb.rb_left) {
+ subtree = rb_entry(node->rb.rb_left, struct test_node,
+ rb)->augmented;
+ if (max < subtree)
+ max = subtree;
+ }
+ if (node->rb.rb_right) {
+ subtree = rb_entry(node->rb.rb_right, struct test_node,
+ rb)->augmented;
+ if (max < subtree)
+ max = subtree;
+ }
+ WARN_ON_ONCE(node->augmented != max);
}
}
--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
>
> Note for Uladzislau Rezki, I noticed that the new augmented rbtree
> code defines its own augment_tree_propagate_from function to update
> the augmented subtree information after a node is modified; it would
> probably be feasible to rely on the generated
> free_vmap_area_rb_augment_cb_propagate function instead. mm/mmap.c
> does something similar in vma_gap_update(), for a very similar use
> case.
>
Just noticed this email due to vacation period, therefore it is a late
replay.
Yes i have my own "populate" function and i knew about generated one
because it is used during rotate operations. I a agree it makes sense
to go with generated one to reduce the code size and get rid of
duplication. I think we can rely on generated one otherwise it would
not work at all. But i will double check.
--
Vlad Rezki
>
> --- a/lib/rbtree_test.c~augmented-rbtree-add-new-rb_declare_callbacks_max-macro-fix-2
> +++ a/lib/rbtree_test.c
> @@ -220,10 +220,6 @@ static void check_augmented(int nr_nodes
> struct rb_node *rb;
>
> check(nr_nodes);
> - for (rb = rb_first(&root.rb_root); rb; rb = rb_next(rb)) {
> - struct test_node *node = rb_entry(rb, struct test_node, rb);
> - WARN_ON_ONCE(node->augmented != augment_recompute(node));
> - }
> }
>
I have a question here it is a bit out of this topic but still related :)
Can we move "check augmented" functionality to the rbtree_augmented.h
header file making it public?
I am asking because many users might need it, i mean to check that the
tree is correctly augmented and is correctly maintained. For example
in vmalloc i have my own implementation:
<snip>
#if DEBUG_AUGMENT_PROPAGATE_CHECK
static void
augment_tree_propagate_check(struct rb_node *n)
{
...
}
<snip>
in order to debug and check that nodes are augmented correctly across
the tree.
Thank you.
--
Vlad Rezki
On Mon, Jul 29, 2019 at 3:15 AM Uladzislau Rezki <[email protected]> wrote:
>
> >
> > --- a/lib/rbtree_test.c~augmented-rbtree-add-new-rb_declare_callbacks_max-macro-fix-2
> > +++ a/lib/rbtree_test.c
> > @@ -220,10 +220,6 @@ static void check_augmented(int nr_nodes
> > struct rb_node *rb;
> >
> > check(nr_nodes);
> > - for (rb = rb_first(&root.rb_root); rb; rb = rb_next(rb)) {
> > - struct test_node *node = rb_entry(rb, struct test_node, rb);
> > - WARN_ON_ONCE(node->augmented != augment_recompute(node));
> > - }
> > }
> >
> I have a question here it is a bit out of this topic but still related :)
>
> Can we move "check augmented" functionality to the rbtree_augmented.h
> header file making it public?
Hmmm, I had not thought about that. Agree that this can be useful -
there is already similar test code in rbtree_test.c and also
vma_compute_subtree_gap() in mmap.c, ...
With patch 3/3 of this series, the RBCOMPUTE function (typically
generated through the RB_DECLARE_CALLBACKS_MAX macro) will return a
bool indicating if the node's augmented value was already correctly
set. Maybe this can be used for test code, through in the false case,
the node's augmented value is already overwritten with the correct
value. Not sure if that is a problem though - the files I mentioned
above have test code that will dump the values if there is a mismatch,
but really I think in every realistic case just noting that there was
one would be just as helpful as being able to dump the old (incorrect)
value....
What do you think - is the RBCOMPUTE(node, true) function sufficient
for such debugging ?
Hello, Michel.
>
> Hmmm, I had not thought about that. Agree that this can be useful -
> there is already similar test code in rbtree_test.c and also
> vma_compute_subtree_gap() in mmap.c, ...
>
> With patch 3/3 of this series, the RBCOMPUTE function (typically
> generated through the RB_DECLARE_CALLBACKS_MAX macro) will return a
> bool indicating if the node's augmented value was already correctly
> set. Maybe this can be used for test code, through in the false case,
> the node's augmented value is already overwritten with the correct
> value. Not sure if that is a problem though - the files I mentioned
> above have test code that will dump the values if there is a mismatch,
> but really I think in every realistic case just noting that there was
> one would be just as helpful as being able to dump the old (incorrect)
> value....
>
> What do you think - is the RBCOMPUTE(node, true) function sufficient
> for such debugging ?
>
I think so, at least i do not see any issues with that. If it returns
"false" then it will indicate that the node was not correctly augmented.
Also, i see in many places across your patches there is below code:
<snip>
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; \
} \
if (exit && node->RBAUGMENTED == max) \
return true; \
node->RBAUGMENTED = max; \
return false;
<snip>
i think it can be simplified by using max3 macro. For example:
<snip>
get_subtree_max(struct rb_node *node)
{
struct something *foo;
va = rb_entry_safe(node, struct something, rb_node);
return foo ? foo->subtree_max : 0;
}
compute_subtree_max_size(struct vmap_area *va)
{
return max3(va_size(va),
get_subtree_max_size(va->rb_node.rb_left),
get_subtree_max_size(va->rb_node.rb_right));
}
<snip>
What do you think about that?
Thank you.
--
Vlad Rezki