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

From: Michel Lespinasse
Date: Mon Jul 08 2019 - 08:24:27 EST

Next message: Jose Abreu: "[PATCH net] net: stmmac: Re-work the queue selection for TSO packets"
Previous message: Max Kellermann: "Re: Kernel 5.1.15 stuck in compaction"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

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 <walken@xxxxxxxxxx> 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 <walken@xxxxxxxxxx>
> ---
> 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.

Next message: Jose Abreu: "[PATCH net] net: stmmac: Re-work the queue selection for TSO packets"
Previous message: Max Kellermann: "Re: Kernel 5.1.15 stuck in compaction"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]