Messages in this thread | | | From | Davidlohr Bueso <> | Subject | [rfc PATCH -next 0/5] rbtree: Cache leftmost node internally | Date | Mon, 29 May 2017 19:09:35 -0700 |
| |
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
| |