Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1661537
| From | Davidlohr Bueso <dave@stgolabs.net> |
|---|---|
| Newsgroups | linux.kernel |
| Subject | [PATCH -next v2 0/8] rbtree: Cache leftmost node internally |
| Date | 2017-06-08 20:10 +0200 |
| Message-ID | <tQa2C-7DP-3@gated-at.bofh.it> (permalink) |
| Organization | linux.* mail to news gateway |
Changes from v1 (https://marc.info/?l=linux-kernel&m=149611025616685): - No longer rfc. - Removed bogus semimcolon in rb_first_cached() - Updated missing interval tree user drivers/infiniband/hw/hfi1/ - Removed redundant @cached arg in when erasing a node. - Added more patches that make use of rb_first_cached(), which I thought might be worth it: procfs and epoll. - Cc more people for patch 5, which touches drivers such as infiniband and gpu. The rest of the changes are pretty covered with the current Cc'ed maintainers and mm folks. 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]. Patch 1: Layout the rb machinery. Patches 2,3, 4: Make use of the internal leftmost node in scheduler and rt mutexes. Patch 5: Implements fast overlap checks for interval trees. Patch 6: rocket science. Patches 7,8: New patches that convert to O(1) rb_first_cached(). The series has survived booting, kernel builds and pistress workloads. Applies on top of 4.12-rc4 (next). Thanks! Davidlohr Bueso (8): rbtree: Cache leftmost node internally sched/fair: Replace cfs_rq->rb_leftmost sched/deadline: Replace earliest dl and rq leftmost caching locking/rtmutex: Replace top-waiter and pi_waiters leftmost caching lib/interval_tree: Fast overlap detection lib/interval-tree: Correct comment wrt generic flavor procfs: Use faster rb_first_cached() fs/epoll: Use faster rb_first_cached() 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/hfi1/mmu_rb.c | 10 ++--- 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/eventpoll.c | 30 +++++++------ fs/hugetlbfs/inode.c | 6 +-- fs/inode.c | 2 +- fs/proc/generic.c | 26 +++++------ fs/proc/internal.h | 2 +- fs/proc/proc_net.c | 2 +- fs/proc/root.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 | 48 ++++++++++++++++----- 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 +- 52 files changed, 303 insertions(+), 244 deletions(-) -- 2.12.0
Back to linux.kernel | Previous | Next — Next in thread | Find similar | Unroll thread
[PATCH -next v2 0/8] rbtree: Cache leftmost node internally Davidlohr Bueso <dave@stgolabs.net> - 2017-06-08 20:10 +0200
[PATCH 2/8] sched/fair: Replace cfs_rq->rb_leftmost Davidlohr Bueso <dave@stgolabs.net> - 2017-06-08 20:10 +0200
[PATCH 1/8] rbtree: Cache leftmost node internally Davidlohr Bueso <dave@stgolabs.net> - 2017-06-08 20:10 +0200
Re: [PATCH 1/8] rbtree: Cache leftmost node internally Jan Kara <jack@suse.cz> - 2017-06-09 09:50 +0200
Re: [PATCH 1/8] rbtree: Cache leftmost node internally Davidlohr Bueso <dave@stgolabs.net> - 2017-06-09 16:40 +0200
Re: [PATCH 1/8] rbtree: Cache leftmost node internally Jan Kara <jack@suse.cz> - 2017-06-12 11:50 +0200
[PATCH 8/8] fs/epoll: Use faster rb_first_cached() Davidlohr Bueso <dave@stgolabs.net> - 2017-06-08 20:10 +0200
[PATCH 5/8] lib/interval_tree: Fast overlap detection Davidlohr Bueso <dave@stgolabs.net> - 2017-06-08 20:10 +0200
[PATCH 6/8] lib/interval-tree: Correct comment wrt generic flavor Davidlohr Bueso <dave@stgolabs.net> - 2017-06-08 20:10 +0200
[PATCH 7/8] procfs: Use faster rb_first_cached() Davidlohr Bueso <dave@stgolabs.net> - 2017-06-08 20:10 +0200
[PATCH 4/8] locking/rtmutex: Replace top-waiter and pi_waiters leftmost caching Davidlohr Bueso <dave@stgolabs.net> - 2017-06-08 20:10 +0200
csiph-web