[PATCH 0/3] rbtree: fix rb_add_augmented_cached() descent and exercise rb_add*() helpers in rbtree_test

[Yiwei Lin]

rbtree_test open-codes the insertion of every flavour of rbtree it
exercises, while the generic rb_add*() helpers have been the way most
users insert nodes for years now.  Patches 1 and 3 make the test use the
helpers where the helper does exactly what the test did, so the helpers
themselves get covered.

Converting the cached augmented test exposed the cost of the
"suboptimal" propagate-from-parent path in rb_add_augmented_cached():
2-3% on a Raspberry Pi 4 and 5-7% on an x86-64 KVM guest on the
augmented insert+delete benchmark, against the documented
update-on-the-way-down pattern.  Patch 2 adds a ->merge() callback to
struct rb_augment_callbacks and uses it during the descent, which gets
the helper to parity before the test starts relying on it.
sched/eevdf, its only user, supplies the callback from its existing
per-field helpers; the resulting kernel boots and runs on the Pi.

The augmented invariant checks pass at every step.

Yiwei Lin (3):
  rbtree_test: use rb_add() and rb_add_cached() for the basic tests
  rbtree: update augmented data on the way down in
    rb_add_augmented_cached()
  rbtree_test: use rb_add_augmented_cached() for the cached augmented
    test

 Documentation/core-api/rbtree.rst | 27 ++++++++++++--
 include/linux/rbtree_augmented.h  | 40 +++++++++++++++++---
 kernel/sched/fair.c               | 13 ++++++-
 lib/rbtree_test.c                 | 62 +++++--------------------------
 4 files changed, 80 insertions(+), 62 deletions(-)

-- 
2.34.1