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.

[walken@google.com: fix mm/vmalloc.c]
  Link: http://lkml.kernel.org/r/CANN689FXgK13wDYNh1zKxdipeTuALG4eKvKpsdZqKFJ-rvtGiQ@mail.gmail.com
[walken@google.com: re-add check to check_augmented()]
  Link: http://lkml.kernel.org/r/20190727022027.GA86863@google.com
Link: http://lkml.kernel.org/r/20190703040156.56953-3-walken@google.com
Signed-off-by: Michel Lespinasse <walken@google.com>
Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Cc: David Howells <dhowells@redhat.com>
Cc: Davidlohr Bueso <dbueso@suse.de>
Cc: Uladzislau Rezki <urezki@gmail.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

1 files changed, 17 insertions, 20 deletions

diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index 62b8ee92643d..41ae3c7570d3 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -77,26 +77,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)
@@ -238,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);
         }
 }