make RB_DECLARE_CALLBACKS more generic
Subsystems (7)
v3 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).
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(-)
Signature · 1 line
2.22.0.410.gd8fdbe21b5-goog
PATCH v3 1/3 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 ++++++++++++++++---------- tools/include/linux/rbtree_augmented.h | 54 ++++++++++++++++---------- 2 files changed, 66 insertions(+), 42 deletions(-)
include/linux/rbtree_augmented.h +33 -21
@@ -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 \ };
tools/include/linux/rbtree_augmented.h +33 -21
72 lines not on this page · raw message
Signature · 1 line
2.22.0.410.gd8fdbe21b5-goog
PATCH v3 2/3 augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro
In reply to Michel LespinasseAdd 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.
--- 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(-)
arch/x86/mm/pat_rbtree.c +3 -16
@@ -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,
drivers/block/drbd/drbd_interval.c +3 -26
@@ -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
include/linux/interval_tree_generic.h +2 -20
@@ -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 */ \ \
include/linux/rbtree_augmented.h +35 -1
@@ -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
lib/rbtree_test.c +3 -19
@@ -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)
mm/mmap.c +18 -11
@@ -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 ); }
tools/include/linux/rbtree_augmented.h +35 -1
@@ -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
Signature · 1 line
2.22.0.410.gd8fdbe21b5-goog
Re: [PATCH v3 2/3] augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro
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:
vmalloc.c +2 -3
@@ -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.
Quoted 341 lines · Michel Lespinasse
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 ofRB_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(-)arch/x86/mm/pat_rbtree.c +3
-16@@ -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,drivers/block/drbd/drbd_interval.c +3
-26@@ -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 include/linux/interval_tree_generic.h +2
-20@@ -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 */ \ \include/linux/rbtree_augmented.h +35
-1@@ -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 1lib/rbtree_test.c +3
-19@@ -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)mm/mmap.c +18
-11@@ -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 ); }tools/include/linux/rbtree_augmented.h +35
-2@@ -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
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
Andrew Morton
maintainerRe: [PATCH v3 2/3] augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro
Quoted 5 lines · 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.cwhich 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:
lib/rbtree_test.c renamed from lib/rbtree_test.c~augmented-rbtree-add-new-rb_declare_callbacks_max-macro-fix-2 +0 -4
@@ -220,10 +220,6 @@ static void check_augmented(int nr_nodesstruct 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?
Re: [PATCH v3 2/3] augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro
Quoted 6 lines · Andrew Morton
Quoted 4 lines · 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.cwhich does not compile after applying my patchset.
Quoted 7 lines
Quoted 1 line
It's an easy fix though:
It still doesn't build.
lib/rbtree_test.c: In functioncheck_augmented:lib/rbtree_test.c:225:35: error: implicit declaration of functionaugment_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.
--- lib/rbtree_test.c | 15 ++++++++++++++- 1 file changed, 14 insertions(+), 1 deletion(-)
lib/rbtree_test.c +14 -1
@@ -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); } }
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
Re: [PATCH v3 2/3] augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro
In reply to Andrew Mortonlib/rbtree_test.c static void check_augmented(int nr_nodes · line 224
Quoted 13 lines
lib/rbtree_test.c renamed from lib/rbtree_test.c~augmented-rbtree-add-new-rb_declare_callbacks_max-macro-fix-2 +0
-4@@ -220,10 +220,6 @@ static void check_augmented(int nr_nodesstruct 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 voidaugment_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
Re: [PATCH v3 2/3] augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro
Quoted 16 lines · Uladzislau Rezki
Quoted 5 lines
lib/rbtree_test.c static void check_augmented(int nr_nodes · line 224
Quoted 9 lines
lib/rbtree_test.c renamed from lib/rbtree_test.c~augmented-rbtree-add-new-rb_declare_callbacks_max-macro-fix-2 +0
-4@@ -220,10 +220,6 @@ static void check_augmented(int nr_nodesstruct 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 :)
Quoted 2 lines
Can we move "check augmented" functionality to the
rbtree_augmented.hheader 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 ?
Re: [PATCH v3 2/3] augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro
Hello, Michel.
Quoted 16 lines
Hmmm, I had not thought about that. Agree that this can be useful - there is already similar test code in
rbtree_test.cand alsovma_compute_subtree_gap()inmmap.c, ...With patch 3/3 of this series, the RBCOMPUTE function (typically generated through the
RB_DECLARE_CALLBACKS_MAXmacro) 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....
Quoted 3 lines
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
Re: [PATCH v3 2/3] augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro
In reply to Michel LespinasseQuoted 9 lines
Note for Uladzislau Rezki, I noticed that the new augmented rbtree code defines its own
augment_tree_propagate_fromfunction to update the augmented subtree information after a node is modified; it would probably be feasible to rely on the generatedfree_vmap_area_rb_augment_cb_propagatefunction instead.mm/mmap.cdoes something similar invma_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
PATCH v3 3/3 augmented rbtree: rework the RB_DECLARE_CALLBACKS macro definition
In reply to Michel LespinasseChange 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.
--- include/linux/rbtree_augmented.h | 24 ++++++++++++------------ tools/include/linux/rbtree_augmented.h | 24 ++++++++++++------------ 2 files changed, 24 insertions(+), 24 deletions(-)
include/linux/rbtree_augmented.h +12 -12
@@ -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
tools/include/linux/rbtree_augmented.h +12 -12
@@ -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
Signature · 1 line
2.22.0.410.gd8fdbe21b5-goog
Quoted 21 lines · Michel Lespinasse
These changes are intended to make the
RB_DECLARE_CALLBACKSmacro 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_CALLBACKSandRB_DECLARE_CALLBACKS_MAXmacros as suggested by Peter Zijlstra.Changes since v1: I have added a new
RB_DECLARE_CALLBACKS_MAXmacro, 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 laterRB_DECLARE_CALLBACKSdefinition change as it's only currently used inRB_DECLARE_CALLBACKS_MAX.I have also verified the compiled
lib/interval_tree.oandmm/mmap.ofiles 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_rbas 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.
Quoted 4 lines
Michel Lespinasse (3):
augmented rbtree: add comments forRB_DECLARE_CALLBACKSmacro augmented rbtree: add newRB_DECLARE_CALLBACKS_MAXmacro augmented rbtree: rework theRB_DECLARE_CALLBACKSmacro definition
Thanks Michel, looking good now!