From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1750942AbdE3CKe (ORCPT ); Mon, 29 May 2017 22:10:34 -0400 Received: from smtp2.provo.novell.com ([137.65.250.81]:36232 "EHLO smtp2.provo.novell.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750839AbdE3CKd (ORCPT ); Mon, 29 May 2017 22:10:33 -0400 From: Davidlohr Bueso To: mingo@kernel.org, peterz@infradead.org, akpm@linux-foundation.org Cc: jack@suse.cz, kirill.shutemov@linux.intel.com, ldufour@linux.vnet.ibm.com, mhocko@suse.com, mgorman@techsingularity.net, dave@stgolabs.net, linux-kernel@vger.kernel.org Subject: [rfc PATCH -next 0/5] rbtree: Cache leftmost node internally Date: Mon, 29 May 2017 19:09:35 -0700 Message-Id: <20170530020940.7918-1-dave@stgolabs.net> X-Mailer: git-send-email 2.12.0 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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