The patch titled
Subject: augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro
has been added to the -mm tree. Its filename is
augmented-rbtree-add-new-rb_declare_callbacks_max-macro.patch
This patch should soon appear at
http://ozlabs.org/~akpm/mmots/broken-out/augmented-rbtree-add-new-rb_declare_callbacks_max-macro.patch
and later at
http://ozlabs.org/~akpm/mmotm/broken-out/augmented-rbtree-add-new-rb_declare_callbacks_max-macro.patch
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next and is updated
there every 3-4 working days
------------------------------------------------------
From: Michel Lespinasse <walken@xxxxxxxxxx>
Subject: augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro
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.
Link: http://lkml.kernel.org/r/20190703040156.56953-3-walken@xxxxxxxxxx
Signed-off-by: Michel Lespinasse <walken@xxxxxxxxxx>
Acked-by: Peter Zijlstra (Intel) <peterz@xxxxxxxxxxxxx>
Cc: David Howells <dhowells@xxxxxxxxxx>
Cc: Davidlohr Bueso <dbueso@xxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
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(-)
--- a/arch/x86/mm/pat_rbtree.c~augmented-rbtree-add-new-rb_declare_callbacks_max-macro
+++ a/arch/x86/mm/pat_rbtree.c
@@ -54,23 +54,10 @@ static u64 get_subtree_max_end(struct rb
return ret;
}
-static u64 compute_subtree_max_end(struct memtype *data)
-{
- u64 max_end = data->end, child_max_end;
+#define NODE_END(node) ((node)->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;
-}
-
-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,
--- a/drivers/block/drbd/drbd_interval.c~augmented-rbtree-add-new-rb_declare_callbacks_max-macro
+++ a/drivers/block/drbd/drbd_interval.c
@@ -13,33 +13,10 @@ sector_t interval_end(struct rb_node *no
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
--- a/include/linux/interval_tree_generic.h~augmented-rbtree-add-new-rb_declare_callbacks_max-macro
+++ a/include/linux/interval_tree_generic.h
@@ -30,26 +30,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 */ \
\
--- a/include/linux/rbtree_augmented.h~augmented-rbtree-add-new-rb_declare_callbacks_max-macro
+++ a/include/linux/rbtree_augmented.h
@@ -61,7 +61,7 @@ rb_insert_augmented_cached(struct rb_nod
}
/*
- * 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
@@ -107,6 +107,40 @@ RBSTATIC const struct rb_augment_callbac
.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
--- a/lib/rbtree_test.c~augmented-rbtree-add-new-rb_declare_callbacks_max-macro
+++ a/lib/rbtree_test.c
@@ -77,26 +77,10 @@ static inline void erase_cached(struct t
}
-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)
--- a/mm/mmap.c~augmented-rbtree-add-new-rb_declare_callbacks_max-macro
+++ a/mm/mmap.c
@@ -289,9 +289,9 @@ out:
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
@@ -299,14 +299,21 @@ static long vma_compute_subtree_gap(stru
* 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;
@@ -322,7 +329,6 @@ static long vma_compute_subtree_gap(stru
return max;
}
-#ifdef CONFIG_DEBUG_VM_RB
static int browse_rb(struct mm_struct *mm)
{
struct rb_root *root = &mm->mm_rb;
@@ -428,8 +434,9 @@ static void validate_mm(struct mm_struct
#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
@@ -439,8 +446,8 @@ RB_DECLARE_CALLBACKS(static, vma_gap_cal
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);
}
--- a/tools/include/linux/rbtree_augmented.h~augmented-rbtree-add-new-rb_declare_callbacks_max-macro
+++ a/tools/include/linux/rbtree_augmented.h
@@ -63,7 +63,7 @@ rb_insert_augmented_cached(struct rb_nod
}
/*
- * 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
@@ -109,6 +109,40 @@ RBSTATIC const struct rb_augment_callbac
.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
_
Patches currently in -mm which might be from walken@xxxxxxxxxx are
rbtree-sync-up-the-tools-copy-of-the-code-with-the-main-one.patch
augmented-rbtree-add-comments-for-rb_declare_callbacks-macro.patch
augmented-rbtree-add-new-rb_declare_callbacks_max-macro.patch
augmented-rbtree-rework-the-rb_declare_callbacks-macro-definition.patch
