[rfc PATCH -next 0/5] rbtree: Cache leftmost node internally

[Davidlohr Bueso <dave@stgolabs.net>]

Hi,

Here's a proposal for extending rbtrees to internally cache the leftmost
node such that we can have fast overlap check optimization for all interval
tree users[1]. I've marked this rfc as I don't know how folks will react
to a new rb_root_cached structure; which is explained in patch 1. The
rest of the patches make use of the internal leftmost node in scheduler
and rtmutexes and finally patch 5 implements fast overlap checks for
interval trees.

The series has survived booting, kernel builds and pistress workloads.

Applies on top of 4.12-rc3 (next).

Thanks!

[1] https://lkml.org/lkml/2017/5/16/676

Davidlohr Bueso (5):
  rbtree: Cache leftmost node internally
  sched/fair: Replace cfs_rq->rb_leftmost
  locking/rtmutex: Replace top-waiter and pi_waiters leftmost caching
  sched/deadline: Replace earliest deadline and runqueue leftmost caching
  lib/interval_tree: Fast overlap detection

 drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c             |  8 ++--
 drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c             |  7 +--
 drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h             |  2 +-
 drivers/gpu/drm/drm_mm.c                           | 10 ++---
 drivers/gpu/drm/drm_vma_manager.c                  |  2 +-
 drivers/gpu/drm/i915/i915_gem_userptr.c            |  6 +--
 drivers/gpu/drm/radeon/radeon.h                    |  2 +-
 drivers/gpu/drm/radeon/radeon_mn.c                 |  8 ++--
 drivers/gpu/drm/radeon/radeon_vm.c                 |  7 +--
 drivers/infiniband/core/umem_rbtree.c              |  4 +-
 drivers/infiniband/core/uverbs_cmd.c               |  2 +-
 drivers/infiniband/hw/usnic/usnic_uiom.c           |  6 +--
 drivers/infiniband/hw/usnic/usnic_uiom.h           |  2 +-
 .../infiniband/hw/usnic/usnic_uiom_interval_tree.c | 15 ++++---
 .../infiniband/hw/usnic/usnic_uiom_interval_tree.h | 12 +++---
 drivers/vhost/vhost.c                              |  2 +-
 drivers/vhost/vhost.h                              |  2 +-
 fs/hugetlbfs/inode.c                               |  6 +--
 fs/inode.c                                         |  2 +-
 include/drm/drm_mm.h                               |  2 +-
 include/linux/fs.h                                 |  4 +-
 include/linux/init_task.h                          |  5 +--
 include/linux/interval_tree.h                      |  8 ++--
 include/linux/interval_tree_generic.h              | 46 +++++++++++++++-----
 include/linux/mm.h                                 | 17 ++++----
 include/linux/rbtree.h                             | 11 +++++
 include/linux/rbtree_augmented.h                   | 33 ++++++++++++--
 include/linux/rmap.h                               |  4 +-
 include/linux/rtmutex.h                            |  9 ++--
 include/linux/sched.h                              |  3 +-
 include/rdma/ib_umem_odp.h                         | 11 +++--
 include/rdma/ib_verbs.h                            |  2 +-
 kernel/fork.c                                      |  3 +-
 kernel/locking/rtmutex-debug.c                     |  2 +-
 kernel/locking/rtmutex.c                           | 36 ++++++----------
 kernel/locking/rtmutex_common.h                    | 10 ++---
 kernel/sched/deadline.c                            | 50 ++++++++--------------
 kernel/sched/debug.c                               |  2 +-
 kernel/sched/fair.c                                | 35 +++++----------
 kernel/sched/sched.h                               |  9 ++--
 lib/interval_tree_test.c                           |  4 +-
 lib/rbtree.c                                       | 34 ++++++++++++---
 mm/interval_tree.c                                 | 10 ++---
 mm/memory.c                                        |  4 +-
 mm/mmap.c                                          | 10 ++---
 mm/rmap.c                                          |  4 +-
 46 files changed, 264 insertions(+), 209 deletions(-)

-- 
2.12.0