| Message ID | 20170719014603.19029-12-dave@stgolabs.net (mailing list archive) |
|---|---|
| State | Not Applicable |
| Headers | show |
On 7/18/2017 9:45 PM, Davidlohr Bueso wrote: > Allow interval trees to quickly check for overlaps to avoid > unnecesary tree lookups in interval_tree_iter_first(). > > As of this patch, all interval tree flavors will require > using a 'rb_root_cached' such that we can have the leftmost > node easily available. While most users will make use of this > feature, those with special functions (in addition to the generic > insert, delete, search calls) will avoid using the cached > option as they can do funky things with insertions -- for example, > vma_interval_tree_insert_after(). > > Cc: David Airlie <airlied@linux.ie> > Cc: dri-devel@lists.freedesktop.org > Cc: "Michael S. Tsirkin" <mst@redhat.com> > Cc: Jason Wang <jasowang@redhat.com> > Cc: Doug Ledford <dledford@redhat.com> > Cc: Christian Benvenuti <benve@cisco.com> > Cc: linux-rdma@vger.kernel.org > Acked-by: Christian König <christian.koenig@amd.com> > Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org> > Signed-off-by: Davidlohr Bueso <dbueso@suse.de> Ack for the RDMA parts. Acked-by: Doug Ledford <dledford@redhat.com>
On Tue, Jul 18, 2017 at 06:45:57PM -0700, Davidlohr Bueso wrote: > Allow interval trees to quickly check for overlaps to avoid > unnecesary tree lookups in interval_tree_iter_first(). > > As of this patch, all interval tree flavors will require > using a 'rb_root_cached' such that we can have the leftmost > node easily available. While most users will make use of this > feature, those with special functions (in addition to the generic > insert, delete, search calls) will avoid using the cached > option as they can do funky things with insertions -- for example, > vma_interval_tree_insert_after(). > > Cc: David Airlie <airlied@linux.ie> > Cc: dri-devel@lists.freedesktop.org > Cc: "Michael S. Tsirkin" <mst@redhat.com> > Cc: Jason Wang <jasowang@redhat.com> > Cc: Doug Ledford <dledford@redhat.com> > Cc: Christian Benvenuti <benve@cisco.com> > Cc: linux-rdma@vger.kernel.org > Acked-by: Christian König <christian.koenig@amd.com> > Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org> > Signed-off-by: Davidlohr Bueso <dbueso@suse.de> For vhost bits: Acked-by: Michael S. Tsirkin <mst@redhat.com> > --- > 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 | 19 +++++---- > 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/hugetlbfs/inode.c | 6 +-- > fs/inode.c | 2 +- > include/drm/drm_mm.h | 2 +- > include/linux/fs.h | 4 +- > include/linux/interval_tree.h | 8 ++-- > include/linux/interval_tree_generic.h | 46 +++++++++++++++++----- > include/linux/mm.h | 17 ++++---- > include/linux/rmap.h | 4 +- > include/rdma/ib_umem_odp.h | 11 ++++-- > include/rdma/ib_verbs.h | 2 +- > lib/interval_tree_test.c | 4 +- > mm/interval_tree.c | 10 ++--- > mm/memory.c | 4 +- > mm/mmap.c | 10 ++--- > mm/rmap.c | 4 +- > 33 files changed, 145 insertions(+), 105 deletions(-) > > diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c b/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c > index 38f739fb727b..3f8aef21b9a6 100644 > --- a/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c > +++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c > @@ -51,7 +51,7 @@ struct amdgpu_mn { > > /* objects protected by lock */ > struct mutex lock; > - struct rb_root objects; > + struct rb_root_cached objects; > }; > > struct amdgpu_mn_node { > @@ -76,8 +76,8 @@ static void amdgpu_mn_destroy(struct work_struct *work) > mutex_lock(&adev->mn_lock); > mutex_lock(&rmn->lock); > hash_del(&rmn->node); > - rbtree_postorder_for_each_entry_safe(node, next_node, &rmn->objects, > - it.rb) { > + rbtree_postorder_for_each_entry_safe(node, next_node, > + &rmn->objects.rb_root, it.rb) { > list_for_each_entry_safe(bo, next_bo, &node->bos, mn_list) { > bo->mn = NULL; > list_del_init(&bo->mn_list); > @@ -252,7 +252,7 @@ static struct amdgpu_mn *amdgpu_mn_get(struct amdgpu_device *adev) > rmn->mm = mm; > rmn->mn.ops = &amdgpu_mn_ops; > mutex_init(&rmn->lock); > - rmn->objects = RB_ROOT; > + rmn->objects = RB_ROOT_CACHED; > > r = __mmu_notifier_register(&rmn->mn, mm); > if (r) > diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c b/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c > index 5795f81369f0..f872e2179bbd 100644 > --- a/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c > +++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c > @@ -2405,7 +2405,7 @@ int amdgpu_vm_init(struct amdgpu_device *adev, struct amdgpu_vm *vm, > int r, i; > u64 flags; > > - vm->va = RB_ROOT; > + vm->va = RB_ROOT_CACHED; > vm->client_id = atomic64_inc_return(&adev->vm_manager.client_counter); > for (i = 0; i < AMDGPU_MAX_VMHUBS; i++) > vm->reserved_vmid[i] = NULL; > @@ -2512,10 +2512,11 @@ void amdgpu_vm_fini(struct amdgpu_device *adev, struct amdgpu_vm *vm) > > amd_sched_entity_fini(vm->entity.sched, &vm->entity); > > - if (!RB_EMPTY_ROOT(&vm->va)) { > + if (!RB_EMPTY_ROOT(&vm->va.rb_root)) { > dev_err(adev->dev, "still active bo inside vm\n"); > } > - rbtree_postorder_for_each_entry_safe(mapping, tmp, &vm->va, rb) { > + rbtree_postorder_for_each_entry_safe(mapping, tmp, > + &vm->va.rb_root, rb) { > list_del(&mapping->list); > amdgpu_vm_it_remove(mapping, &vm->va); > kfree(mapping); > diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h b/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h > index 936f158bc5ec..ebffc1253f85 100644 > --- a/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h > +++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h > @@ -106,7 +106,7 @@ struct amdgpu_vm_pt { > > struct amdgpu_vm { > /* tree of virtual addresses mapped */ > - struct rb_root va; > + struct rb_root_cached va; > > /* protecting invalidated */ > spinlock_t status_lock; > diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c > index f794089d30ac..61a1c8ea74bc 100644 > --- a/drivers/gpu/drm/drm_mm.c > +++ b/drivers/gpu/drm/drm_mm.c > @@ -169,7 +169,7 @@ INTERVAL_TREE_DEFINE(struct drm_mm_node, rb, > struct drm_mm_node * > __drm_mm_interval_first(const struct drm_mm *mm, u64 start, u64 last) > { > - return drm_mm_interval_tree_iter_first((struct rb_root *)&mm->interval_tree, > + return drm_mm_interval_tree_iter_first((struct rb_root_cached *)&mm->interval_tree, > start, last) ?: (struct drm_mm_node *)&mm->head_node; > } > EXPORT_SYMBOL(__drm_mm_interval_first); > @@ -180,6 +180,7 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, > struct drm_mm *mm = hole_node->mm; > struct rb_node **link, *rb; > struct drm_mm_node *parent; > + bool leftmost = true; > > node->__subtree_last = LAST(node); > > @@ -196,9 +197,10 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, > > rb = &hole_node->rb; > link = &hole_node->rb.rb_right; > + leftmost = false; > } else { > rb = NULL; > - link = &mm->interval_tree.rb_node; > + link = &mm->interval_tree.rb_root.rb_node; > } > > while (*link) { > @@ -208,14 +210,15 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, > parent->__subtree_last = node->__subtree_last; > if (node->start < parent->start) > link = &parent->rb.rb_left; > - else > + else { > link = &parent->rb.rb_right; > + leftmost = true; > + } > } > > rb_link_node(&node->rb, rb, link); > - rb_insert_augmented(&node->rb, > - &mm->interval_tree, > - &drm_mm_interval_tree_augment); > + rb_insert_augmented_cached(&node->rb, &mm->interval_tree, leftmost, > + &drm_mm_interval_tree_augment); > } > > #define RB_INSERT(root, member, expr) do { \ > @@ -577,7 +580,7 @@ void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new) > *new = *old; > > list_replace(&old->node_list, &new->node_list); > - rb_replace_node(&old->rb, &new->rb, &old->mm->interval_tree); > + rb_replace_node(&old->rb, &new->rb, &old->mm->interval_tree.rb_root); > > if (drm_mm_hole_follows(old)) { > list_replace(&old->hole_stack, &new->hole_stack); > @@ -863,7 +866,7 @@ void drm_mm_init(struct drm_mm *mm, u64 start, u64 size) > mm->color_adjust = NULL; > > INIT_LIST_HEAD(&mm->hole_stack); > - mm->interval_tree = RB_ROOT; > + mm->interval_tree = RB_ROOT_CACHED; > mm->holes_size = RB_ROOT; > mm->holes_addr = RB_ROOT; > > diff --git a/drivers/gpu/drm/drm_vma_manager.c b/drivers/gpu/drm/drm_vma_manager.c > index d9100b565198..28f1226576f8 100644 > --- a/drivers/gpu/drm/drm_vma_manager.c > +++ b/drivers/gpu/drm/drm_vma_manager.c > @@ -147,7 +147,7 @@ struct drm_vma_offset_node *drm_vma_offset_lookup_locked(struct drm_vma_offset_m > struct rb_node *iter; > unsigned long offset; > > - iter = mgr->vm_addr_space_mm.interval_tree.rb_node; > + iter = mgr->vm_addr_space_mm.interval_tree.rb_root.rb_node; > best = NULL; > > while (likely(iter)) { > diff --git a/drivers/gpu/drm/i915/i915_gem_userptr.c b/drivers/gpu/drm/i915/i915_gem_userptr.c > index ccd09e8419f5..71dddf66baaa 100644 > --- a/drivers/gpu/drm/i915/i915_gem_userptr.c > +++ b/drivers/gpu/drm/i915/i915_gem_userptr.c > @@ -49,7 +49,7 @@ struct i915_mmu_notifier { > spinlock_t lock; > struct hlist_node node; > struct mmu_notifier mn; > - struct rb_root objects; > + struct rb_root_cached objects; > struct workqueue_struct *wq; > }; > > @@ -123,7 +123,7 @@ static void i915_gem_userptr_mn_invalidate_range_start(struct mmu_notifier *_mn, > struct interval_tree_node *it; > LIST_HEAD(cancelled); > > - if (RB_EMPTY_ROOT(&mn->objects)) > + if (RB_EMPTY_ROOT(&mn->objects.rb_root)) > return; > > /* interval ranges are inclusive, but invalidate range is exclusive */ > @@ -172,7 +172,7 @@ i915_mmu_notifier_create(struct mm_struct *mm) > > spin_lock_init(&mn->lock); > mn->mn.ops = &i915_gem_userptr_notifier; > - mn->objects = RB_ROOT; > + mn->objects = RB_ROOT_CACHED; > mn->wq = alloc_workqueue("i915-userptr-release", WQ_UNBOUND, 0); > if (mn->wq == NULL) { > kfree(mn); > diff --git a/drivers/gpu/drm/radeon/radeon.h b/drivers/gpu/drm/radeon/radeon.h > index 5008f3d4cccc..10d0dd146808 100644 > --- a/drivers/gpu/drm/radeon/radeon.h > +++ b/drivers/gpu/drm/radeon/radeon.h > @@ -924,7 +924,7 @@ struct radeon_vm_id { > struct radeon_vm { > struct mutex mutex; > > - struct rb_root va; > + struct rb_root_cached va; > > /* protecting invalidated and freed */ > spinlock_t status_lock; > diff --git a/drivers/gpu/drm/radeon/radeon_mn.c b/drivers/gpu/drm/radeon/radeon_mn.c > index 896f2cf51e4e..1d62288b7ee3 100644 > --- a/drivers/gpu/drm/radeon/radeon_mn.c > +++ b/drivers/gpu/drm/radeon/radeon_mn.c > @@ -50,7 +50,7 @@ struct radeon_mn { > > /* objects protected by lock */ > struct mutex lock; > - struct rb_root objects; > + struct rb_root_cached objects; > }; > > struct radeon_mn_node { > @@ -75,8 +75,8 @@ static void radeon_mn_destroy(struct work_struct *work) > mutex_lock(&rdev->mn_lock); > mutex_lock(&rmn->lock); > hash_del(&rmn->node); > - rbtree_postorder_for_each_entry_safe(node, next_node, &rmn->objects, > - it.rb) { > + rbtree_postorder_for_each_entry_safe(node, next_node, > + &rmn->objects.rb_root, it.rb) { > > interval_tree_remove(&node->it, &rmn->objects); > list_for_each_entry_safe(bo, next_bo, &node->bos, mn_list) { > @@ -205,7 +205,7 @@ static struct radeon_mn *radeon_mn_get(struct radeon_device *rdev) > rmn->mm = mm; > rmn->mn.ops = &radeon_mn_ops; > mutex_init(&rmn->lock); > - rmn->objects = RB_ROOT; > + rmn->objects = RB_ROOT_CACHED; > > r = __mmu_notifier_register(&rmn->mn, mm); > if (r) > diff --git a/drivers/gpu/drm/radeon/radeon_vm.c b/drivers/gpu/drm/radeon/radeon_vm.c > index 5f68245579a3..f44777a6c2e8 100644 > --- a/drivers/gpu/drm/radeon/radeon_vm.c > +++ b/drivers/gpu/drm/radeon/radeon_vm.c > @@ -1185,7 +1185,7 @@ int radeon_vm_init(struct radeon_device *rdev, struct radeon_vm *vm) > vm->ids[i].last_id_use = NULL; > } > mutex_init(&vm->mutex); > - vm->va = RB_ROOT; > + vm->va = RB_ROOT_CACHED; > spin_lock_init(&vm->status_lock); > INIT_LIST_HEAD(&vm->invalidated); > INIT_LIST_HEAD(&vm->freed); > @@ -1232,10 +1232,11 @@ void radeon_vm_fini(struct radeon_device *rdev, struct radeon_vm *vm) > struct radeon_bo_va *bo_va, *tmp; > int i, r; > > - if (!RB_EMPTY_ROOT(&vm->va)) { > + if (!RB_EMPTY_ROOT(&vm->va.rb_root)) { > dev_err(rdev->dev, "still active bo inside vm\n"); > } > - rbtree_postorder_for_each_entry_safe(bo_va, tmp, &vm->va, it.rb) { > + rbtree_postorder_for_each_entry_safe(bo_va, tmp, > + &vm->va.rb_root, it.rb) { > interval_tree_remove(&bo_va->it, &vm->va); > r = radeon_bo_reserve(bo_va->bo, false); > if (!r) { > diff --git a/drivers/infiniband/core/umem_rbtree.c b/drivers/infiniband/core/umem_rbtree.c > index d176597b4d78..fc801920e341 100644 > --- a/drivers/infiniband/core/umem_rbtree.c > +++ b/drivers/infiniband/core/umem_rbtree.c > @@ -72,7 +72,7 @@ INTERVAL_TREE_DEFINE(struct umem_odp_node, rb, u64, __subtree_last, > /* @last is not a part of the interval. See comment for function > * node_last. > */ > -int rbt_ib_umem_for_each_in_range(struct rb_root *root, > +int rbt_ib_umem_for_each_in_range(struct rb_root_cached *root, > u64 start, u64 last, > umem_call_back cb, > void *cookie) > @@ -95,7 +95,7 @@ int rbt_ib_umem_for_each_in_range(struct rb_root *root, > } > EXPORT_SYMBOL(rbt_ib_umem_for_each_in_range); > > -struct ib_umem_odp *rbt_ib_umem_lookup(struct rb_root *root, > +struct ib_umem_odp *rbt_ib_umem_lookup(struct rb_root_cached *root, > u64 addr, u64 length) > { > struct umem_odp_node *node; > diff --git a/drivers/infiniband/core/uverbs_cmd.c b/drivers/infiniband/core/uverbs_cmd.c > index 3f55d18a3791..5321c6ae2c0c 100644 > --- a/drivers/infiniband/core/uverbs_cmd.c > +++ b/drivers/infiniband/core/uverbs_cmd.c > @@ -117,7 +117,7 @@ ssize_t ib_uverbs_get_context(struct ib_uverbs_file *file, > ucontext->closing = 0; > > #ifdef CONFIG_INFINIBAND_ON_DEMAND_PAGING > - ucontext->umem_tree = RB_ROOT; > + ucontext->umem_tree = RB_ROOT_CACHED; > init_rwsem(&ucontext->umem_rwsem); > ucontext->odp_mrs_count = 0; > INIT_LIST_HEAD(&ucontext->no_private_counters); > diff --git a/drivers/infiniband/hw/hfi1/mmu_rb.c b/drivers/infiniband/hw/hfi1/mmu_rb.c > index d41fd87a39f2..5b6626f8feb6 100644 > --- a/drivers/infiniband/hw/hfi1/mmu_rb.c > +++ b/drivers/infiniband/hw/hfi1/mmu_rb.c > @@ -54,7 +54,7 @@ > > struct mmu_rb_handler { > struct mmu_notifier mn; > - struct rb_root root; > + struct rb_root_cached root; > void *ops_arg; > spinlock_t lock; /* protect the RB tree */ > struct mmu_rb_ops *ops; > @@ -111,7 +111,7 @@ int hfi1_mmu_rb_register(void *ops_arg, struct mm_struct *mm, > if (!handlr) > return -ENOMEM; > > - handlr->root = RB_ROOT; > + handlr->root = RB_ROOT_CACHED; > handlr->ops = ops; > handlr->ops_arg = ops_arg; > INIT_HLIST_NODE(&handlr->mn.hlist); > @@ -152,9 +152,9 @@ void hfi1_mmu_rb_unregister(struct mmu_rb_handler *handler) > INIT_LIST_HEAD(&del_list); > > spin_lock_irqsave(&handler->lock, flags); > - while ((node = rb_first(&handler->root))) { > + while ((node = rb_first_cached(&handler->root))) { > rbnode = rb_entry(node, struct mmu_rb_node, node); > - rb_erase(node, &handler->root); > + rb_erase_cached(node, &handler->root); > /* move from LRU list to delete list */ > list_move(&rbnode->list, &del_list); > } > @@ -311,7 +311,7 @@ static void mmu_notifier_mem_invalidate(struct mmu_notifier *mn, > { > struct mmu_rb_handler *handler = > container_of(mn, struct mmu_rb_handler, mn); > - struct rb_root *root = &handler->root; > + struct rb_root_cached *root = &handler->root; > struct mmu_rb_node *node, *ptr = NULL; > unsigned long flags; > bool added = false; > diff --git a/drivers/infiniband/hw/usnic/usnic_uiom.c b/drivers/infiniband/hw/usnic/usnic_uiom.c > index c49db7c33979..4381c0a9a873 100644 > --- a/drivers/infiniband/hw/usnic/usnic_uiom.c > +++ b/drivers/infiniband/hw/usnic/usnic_uiom.c > @@ -227,7 +227,7 @@ static void __usnic_uiom_reg_release(struct usnic_uiom_pd *pd, > vpn_last = vpn_start + npages - 1; > > spin_lock(&pd->lock); > - usnic_uiom_remove_interval(&pd->rb_root, vpn_start, > + usnic_uiom_remove_interval(&pd->root, vpn_start, > vpn_last, &rm_intervals); > usnic_uiom_unmap_sorted_intervals(&rm_intervals, pd); > > @@ -379,7 +379,7 @@ struct usnic_uiom_reg *usnic_uiom_reg_get(struct usnic_uiom_pd *pd, > err = usnic_uiom_get_intervals_diff(vpn_start, vpn_last, > (writable) ? IOMMU_WRITE : 0, > IOMMU_WRITE, > - &pd->rb_root, > + &pd->root, > &sorted_diff_intervals); > if (err) { > usnic_err("Failed disjoint interval vpn [0x%lx,0x%lx] err %d\n", > @@ -395,7 +395,7 @@ struct usnic_uiom_reg *usnic_uiom_reg_get(struct usnic_uiom_pd *pd, > > } > > - err = usnic_uiom_insert_interval(&pd->rb_root, vpn_start, vpn_last, > + err = usnic_uiom_insert_interval(&pd->root, vpn_start, vpn_last, > (writable) ? IOMMU_WRITE : 0); > if (err) { > usnic_err("Failed insert interval vpn [0x%lx,0x%lx] err %d\n", > diff --git a/drivers/infiniband/hw/usnic/usnic_uiom.h b/drivers/infiniband/hw/usnic/usnic_uiom.h > index 45ca7c1613a7..431efe4143f4 100644 > --- a/drivers/infiniband/hw/usnic/usnic_uiom.h > +++ b/drivers/infiniband/hw/usnic/usnic_uiom.h > @@ -55,7 +55,7 @@ struct usnic_uiom_dev { > struct usnic_uiom_pd { > struct iommu_domain *domain; > spinlock_t lock; > - struct rb_root rb_root; > + struct rb_root_cached root; > struct list_head devs; > int dev_cnt; > }; > diff --git a/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c b/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c > index 42b4b4c4e452..d399523206c7 100644 > --- a/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c > +++ b/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c > @@ -100,9 +100,9 @@ static int interval_cmp(void *priv, struct list_head *a, struct list_head *b) > } > > static void > -find_intervals_intersection_sorted(struct rb_root *root, unsigned long start, > - unsigned long last, > - struct list_head *list) > +find_intervals_intersection_sorted(struct rb_root_cached *root, > + unsigned long start, unsigned long last, > + struct list_head *list) > { > struct usnic_uiom_interval_node *node; > > @@ -118,7 +118,7 @@ find_intervals_intersection_sorted(struct rb_root *root, unsigned long start, > > int usnic_uiom_get_intervals_diff(unsigned long start, unsigned long last, > int flags, int flag_mask, > - struct rb_root *root, > + struct rb_root_cached *root, > struct list_head *diff_set) > { > struct usnic_uiom_interval_node *interval, *tmp; > @@ -175,7 +175,7 @@ void usnic_uiom_put_interval_set(struct list_head *intervals) > kfree(interval); > } > > -int usnic_uiom_insert_interval(struct rb_root *root, unsigned long start, > +int usnic_uiom_insert_interval(struct rb_root_cached *root, unsigned long start, > unsigned long last, int flags) > { > struct usnic_uiom_interval_node *interval, *tmp; > @@ -246,8 +246,9 @@ int usnic_uiom_insert_interval(struct rb_root *root, unsigned long start, > return err; > } > > -void usnic_uiom_remove_interval(struct rb_root *root, unsigned long start, > - unsigned long last, struct list_head *removed) > +void usnic_uiom_remove_interval(struct rb_root_cached *root, > + unsigned long start, unsigned long last, > + struct list_head *removed) > { > struct usnic_uiom_interval_node *interval; > > diff --git a/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.h b/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.h > index c0b0b876ab90..1d7fc3226bca 100644 > --- a/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.h > +++ b/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.h > @@ -48,12 +48,12 @@ struct usnic_uiom_interval_node { > > extern void > usnic_uiom_interval_tree_insert(struct usnic_uiom_interval_node *node, > - struct rb_root *root); > + struct rb_root_cached *root); > extern void > usnic_uiom_interval_tree_remove(struct usnic_uiom_interval_node *node, > - struct rb_root *root); > + struct rb_root_cached *root); > extern struct usnic_uiom_interval_node * > -usnic_uiom_interval_tree_iter_first(struct rb_root *root, > +usnic_uiom_interval_tree_iter_first(struct rb_root_cached *root, > unsigned long start, > unsigned long last); > extern struct usnic_uiom_interval_node * > @@ -63,7 +63,7 @@ usnic_uiom_interval_tree_iter_next(struct usnic_uiom_interval_node *node, > * Inserts {start...last} into {root}. If there are overlaps, > * nodes will be broken up and merged > */ > -int usnic_uiom_insert_interval(struct rb_root *root, > +int usnic_uiom_insert_interval(struct rb_root_cached *root, > unsigned long start, unsigned long last, > int flags); > /* > @@ -71,7 +71,7 @@ int usnic_uiom_insert_interval(struct rb_root *root, > * 'removed.' The caller is responsibile for freeing memory of nodes in > * 'removed.' > */ > -void usnic_uiom_remove_interval(struct rb_root *root, > +void usnic_uiom_remove_interval(struct rb_root_cached *root, > unsigned long start, unsigned long last, > struct list_head *removed); > /* > @@ -81,7 +81,7 @@ void usnic_uiom_remove_interval(struct rb_root *root, > int usnic_uiom_get_intervals_diff(unsigned long start, > unsigned long last, int flags, > int flag_mask, > - struct rb_root *root, > + struct rb_root_cached *root, > struct list_head *diff_set); > /* Call this to free diff_set returned by usnic_uiom_get_intervals_diff */ > void usnic_uiom_put_interval_set(struct list_head *intervals); > diff --git a/drivers/vhost/vhost.c b/drivers/vhost/vhost.c > index e4613a3c362d..88dc214de068 100644 > --- a/drivers/vhost/vhost.c > +++ b/drivers/vhost/vhost.c > @@ -1272,7 +1272,7 @@ static struct vhost_umem *vhost_umem_alloc(void) > if (!umem) > return NULL; > > - umem->umem_tree = RB_ROOT; > + umem->umem_tree = RB_ROOT_CACHED; > umem->numem = 0; > INIT_LIST_HEAD(&umem->umem_list); > > diff --git a/drivers/vhost/vhost.h b/drivers/vhost/vhost.h > index f72095868b93..a0278ba6a8b4 100644 > --- a/drivers/vhost/vhost.h > +++ b/drivers/vhost/vhost.h > @@ -71,7 +71,7 @@ struct vhost_umem_node { > }; > > struct vhost_umem { > - struct rb_root umem_tree; > + struct rb_root_cached umem_tree; > struct list_head umem_list; > int numem; > }; > diff --git a/fs/hugetlbfs/inode.c b/fs/hugetlbfs/inode.c > index 28d2753be094..e61b91e6adf4 100644 > --- a/fs/hugetlbfs/inode.c > +++ b/fs/hugetlbfs/inode.c > @@ -334,7 +334,7 @@ static void remove_huge_page(struct page *page) > } > > static void > -hugetlb_vmdelete_list(struct rb_root *root, pgoff_t start, pgoff_t end) > +hugetlb_vmdelete_list(struct rb_root_cached *root, pgoff_t start, pgoff_t end) > { > struct vm_area_struct *vma; > > @@ -514,7 +514,7 @@ static int hugetlb_vmtruncate(struct inode *inode, loff_t offset) > > i_size_write(inode, offset); > i_mmap_lock_write(mapping); > - if (!RB_EMPTY_ROOT(&mapping->i_mmap)) > + if (!RB_EMPTY_ROOT(&mapping->i_mmap.rb_root)) > hugetlb_vmdelete_list(&mapping->i_mmap, pgoff, 0); > i_mmap_unlock_write(mapping); > remove_inode_hugepages(inode, offset, LLONG_MAX); > @@ -539,7 +539,7 @@ static long hugetlbfs_punch_hole(struct inode *inode, loff_t offset, loff_t len) > > inode_lock(inode); > i_mmap_lock_write(mapping); > - if (!RB_EMPTY_ROOT(&mapping->i_mmap)) > + if (!RB_EMPTY_ROOT(&mapping->i_mmap.rb_root)) > hugetlb_vmdelete_list(&mapping->i_mmap, > hole_start >> PAGE_SHIFT, > hole_end >> PAGE_SHIFT); > diff --git a/fs/inode.c b/fs/inode.c > index 50370599e371..5ddb808ea934 100644 > --- a/fs/inode.c > +++ b/fs/inode.c > @@ -353,7 +353,7 @@ void address_space_init_once(struct address_space *mapping) > init_rwsem(&mapping->i_mmap_rwsem); > INIT_LIST_HEAD(&mapping->private_list); > spin_lock_init(&mapping->private_lock); > - mapping->i_mmap = RB_ROOT; > + mapping->i_mmap = RB_ROOT_CACHED; > } > EXPORT_SYMBOL(address_space_init_once); > > diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h > index 49b292e98fec..8d10fc97801c 100644 > --- a/include/drm/drm_mm.h > +++ b/include/drm/drm_mm.h > @@ -172,7 +172,7 @@ struct drm_mm { > * according to the (increasing) start address of the memory node. */ > struct drm_mm_node head_node; > /* Keep an interval_tree for fast lookup of drm_mm_nodes by address. */ > - struct rb_root interval_tree; > + struct rb_root_cached interval_tree; > struct rb_root holes_size; > struct rb_root holes_addr; > > diff --git a/include/linux/fs.h b/include/linux/fs.h > index ed8798255872..d1d521c5025b 100644 > --- a/include/linux/fs.h > +++ b/include/linux/fs.h > @@ -392,7 +392,7 @@ struct address_space { > struct radix_tree_root page_tree; /* radix tree of all pages */ > spinlock_t tree_lock; /* and lock protecting it */ > atomic_t i_mmap_writable;/* count VM_SHARED mappings */ > - struct rb_root i_mmap; /* tree of private and shared mappings */ > + struct rb_root_cached i_mmap; /* tree of private and shared mappings */ > struct rw_semaphore i_mmap_rwsem; /* protect tree, count, list */ > /* Protected by tree_lock together with the radix tree */ > unsigned long nrpages; /* number of total pages */ > @@ -486,7 +486,7 @@ static inline void i_mmap_unlock_read(struct address_space *mapping) > */ > static inline int mapping_mapped(struct address_space *mapping) > { > - return !RB_EMPTY_ROOT(&mapping->i_mmap); > + return !RB_EMPTY_ROOT(&mapping->i_mmap.rb_root); > } > > /* > diff --git a/include/linux/interval_tree.h b/include/linux/interval_tree.h > index 724556aa3c95..202ee1283f4b 100644 > --- a/include/linux/interval_tree.h > +++ b/include/linux/interval_tree.h > @@ -11,13 +11,15 @@ struct interval_tree_node { > }; > > extern void > -interval_tree_insert(struct interval_tree_node *node, struct rb_root *root); > +interval_tree_insert(struct interval_tree_node *node, > + struct rb_root_cached *root); > > extern void > -interval_tree_remove(struct interval_tree_node *node, struct rb_root *root); > +interval_tree_remove(struct interval_tree_node *node, > + struct rb_root_cached *root); > > extern struct interval_tree_node * > -interval_tree_iter_first(struct rb_root *root, > +interval_tree_iter_first(struct rb_root_cached *root, > unsigned long start, unsigned long last); > > extern struct interval_tree_node * > diff --git a/include/linux/interval_tree_generic.h b/include/linux/interval_tree_generic.h > index 58370e1862ad..f096423c8cbd 100644 > --- a/include/linux/interval_tree_generic.h > +++ b/include/linux/interval_tree_generic.h > @@ -65,11 +65,13 @@ RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB, \ > \ > /* Insert / remove interval nodes from the tree */ \ > \ > -ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, struct rb_root *root) \ > +ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, \ > + struct rb_root_cached *root) \ > { \ > - struct rb_node **link = &root->rb_node, *rb_parent = NULL; \ > + struct rb_node **link = &root->rb_root.rb_node, *rb_parent = NULL; \ > ITTYPE start = ITSTART(node), last = ITLAST(node); \ > ITSTRUCT *parent; \ > + bool leftmost = true; \ > \ > while (*link) { \ > rb_parent = *link; \ > @@ -78,18 +80,22 @@ ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, struct rb_root *root) \ > parent->ITSUBTREE = last; \ > if (start < ITSTART(parent)) \ > link = &parent->ITRB.rb_left; \ > - else \ > + else { \ > link = &parent->ITRB.rb_right; \ > + leftmost = false; \ > + } \ > } \ > \ > node->ITSUBTREE = last; \ > rb_link_node(&node->ITRB, rb_parent, link); \ > - rb_insert_augmented(&node->ITRB, root, &ITPREFIX ## _augment); \ > + rb_insert_augmented_cached(&node->ITRB, root, \ > + leftmost, &ITPREFIX ## _augment); \ > } \ > \ > -ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, struct rb_root *root) \ > +ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, \ > + struct rb_root_cached *root) \ > { \ > - rb_erase_augmented(&node->ITRB, root, &ITPREFIX ## _augment); \ > + rb_erase_augmented_cached(&node->ITRB, root, &ITPREFIX ## _augment); \ > } \ > \ > /* \ > @@ -140,15 +146,35 @@ ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ > } \ > \ > ITSTATIC ITSTRUCT * \ > -ITPREFIX ## _iter_first(struct rb_root *root, ITTYPE start, ITTYPE last) \ > +ITPREFIX ## _iter_first(struct rb_root_cached *root, \ > + ITTYPE start, ITTYPE last) \ > { \ > - ITSTRUCT *node; \ > + ITSTRUCT *node, *leftmost; \ > \ > - if (!root->rb_node) \ > + if (!root->rb_root.rb_node) \ > return NULL; \ > - node = rb_entry(root->rb_node, ITSTRUCT, ITRB); \ > + \ > + /* \ > + * Fastpath range intersection/overlap between A: [a0, a1] and \ > + * B: [b0, b1] is given by: \ > + * \ > + * a0 <= b1 && b0 <= a1 \ > + * \ > + * ... where A holds the lock range and B holds the smallest \ > + * 'start' and largest 'last' in the tree. For the later, we \ > + * rely on the root node, which by augmented interval tree \ > + * property, holds the largest value in its last-in-subtree. \ > + * This allows mitigating some of the tree walk overhead for \ > + * for non-intersecting ranges, maintained and consulted in O(1). \ > + */ \ > + node = rb_entry(root->rb_root.rb_node, ITSTRUCT, ITRB); \ > if (node->ITSUBTREE < start) \ > return NULL; \ > + \ > + leftmost = rb_entry(root->rb_leftmost, ITSTRUCT, ITRB); \ > + if (ITSTART(leftmost) > last) \ > + return NULL; \ > + \ > return ITPREFIX ## _subtree_search(node, start, last); \ > } \ > \ > diff --git a/include/linux/mm.h b/include/linux/mm.h > index 46b9ac5e8569..3a2652efbbfb 100644 > --- a/include/linux/mm.h > +++ b/include/linux/mm.h > @@ -1992,13 +1992,13 @@ extern int nommu_shrink_inode_mappings(struct inode *, size_t, size_t); > > /* interval_tree.c */ > void vma_interval_tree_insert(struct vm_area_struct *node, > - struct rb_root *root); > + struct rb_root_cached *root); > void vma_interval_tree_insert_after(struct vm_area_struct *node, > struct vm_area_struct *prev, > - struct rb_root *root); > + struct rb_root_cached *root); > void vma_interval_tree_remove(struct vm_area_struct *node, > - struct rb_root *root); > -struct vm_area_struct *vma_interval_tree_iter_first(struct rb_root *root, > + struct rb_root_cached *root); > +struct vm_area_struct *vma_interval_tree_iter_first(struct rb_root_cached *root, > unsigned long start, unsigned long last); > struct vm_area_struct *vma_interval_tree_iter_next(struct vm_area_struct *node, > unsigned long start, unsigned long last); > @@ -2008,11 +2008,12 @@ struct vm_area_struct *vma_interval_tree_iter_next(struct vm_area_struct *node, > vma; vma = vma_interval_tree_iter_next(vma, start, last)) > > void anon_vma_interval_tree_insert(struct anon_vma_chain *node, > - struct rb_root *root); > + struct rb_root_cached *root); > void anon_vma_interval_tree_remove(struct anon_vma_chain *node, > - struct rb_root *root); > -struct anon_vma_chain *anon_vma_interval_tree_iter_first( > - struct rb_root *root, unsigned long start, unsigned long last); > + struct rb_root_cached *root); > +struct anon_vma_chain * > +anon_vma_interval_tree_iter_first(struct rb_root_cached *root, > + unsigned long start, unsigned long last); > struct anon_vma_chain *anon_vma_interval_tree_iter_next( > struct anon_vma_chain *node, unsigned long start, unsigned long last); > #ifdef CONFIG_DEBUG_VM_RB > diff --git a/include/linux/rmap.h b/include/linux/rmap.h > index 43ef2c30cb0f..22c298c6cc26 100644 > --- a/include/linux/rmap.h > +++ b/include/linux/rmap.h > @@ -55,7 +55,9 @@ struct anon_vma { > * is serialized by a system wide lock only visible to > * mm_take_all_locks() (mm_all_locks_mutex). > */ > - struct rb_root rb_root; /* Interval tree of private "related" vmas */ > + > + /* Interval tree of private "related" vmas */ > + struct rb_root_cached rb_root; > }; > > /* > diff --git a/include/rdma/ib_umem_odp.h b/include/rdma/ib_umem_odp.h > index fb67554aabd6..5eb7f5bc8248 100644 > --- a/include/rdma/ib_umem_odp.h > +++ b/include/rdma/ib_umem_odp.h > @@ -111,22 +111,25 @@ int ib_umem_odp_map_dma_pages(struct ib_umem *umem, u64 start_offset, u64 bcnt, > void ib_umem_odp_unmap_dma_pages(struct ib_umem *umem, u64 start_offset, > u64 bound); > > -void rbt_ib_umem_insert(struct umem_odp_node *node, struct rb_root *root); > -void rbt_ib_umem_remove(struct umem_odp_node *node, struct rb_root *root); > +void rbt_ib_umem_insert(struct umem_odp_node *node, > + struct rb_root_cached *root); > +void rbt_ib_umem_remove(struct umem_odp_node *node, > + struct rb_root_cached *root); > typedef int (*umem_call_back)(struct ib_umem *item, u64 start, u64 end, > void *cookie); > /* > * Call the callback on each ib_umem in the range. Returns the logical or of > * the return values of the functions called. > */ > -int rbt_ib_umem_for_each_in_range(struct rb_root *root, u64 start, u64 end, > +int rbt_ib_umem_for_each_in_range(struct rb_root_cached *root, > + u64 start, u64 end, > umem_call_back cb, void *cookie); > > /* > * Find first region intersecting with address range. > * Return NULL if not found > */ > -struct ib_umem_odp *rbt_ib_umem_lookup(struct rb_root *root, > +struct ib_umem_odp *rbt_ib_umem_lookup(struct rb_root_cached *root, > u64 addr, u64 length); > > static inline int ib_umem_mmu_notifier_retry(struct ib_umem *item, > diff --git a/include/rdma/ib_verbs.h b/include/rdma/ib_verbs.h > index 593ad2640d2f..81665480a4ab 100644 > --- a/include/rdma/ib_verbs.h > +++ b/include/rdma/ib_verbs.h > @@ -1420,7 +1420,7 @@ struct ib_ucontext { > > struct pid *tgid; > #ifdef CONFIG_INFINIBAND_ON_DEMAND_PAGING > - struct rb_root umem_tree; > + struct rb_root_cached umem_tree; > /* > * Protects .umem_rbroot and tree, as well as odp_mrs_count and > * mmu notifiers registration. > diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c > index df495fe81421..0e343fd29570 100644 > --- a/lib/interval_tree_test.c > +++ b/lib/interval_tree_test.c > @@ -19,14 +19,14 @@ __param(bool, search_all, false, "Searches will iterate all nodes in the tree"); > > __param(uint, max_endpoint, ~0, "Largest value for the interval's endpoint"); > > -static struct rb_root root = RB_ROOT; > +static struct rb_root_cached root = RB_ROOT_CACHED; > static struct interval_tree_node *nodes = NULL; > static u32 *queries = NULL; > > static struct rnd_state rnd; > > static inline unsigned long > -search(struct rb_root *root, unsigned long start, unsigned long last) > +search(struct rb_root_cached *root, unsigned long start, unsigned long last) > { > struct interval_tree_node *node; > unsigned long results = 0; > diff --git a/mm/interval_tree.c b/mm/interval_tree.c > index f2c2492681bf..b47664358796 100644 > --- a/mm/interval_tree.c > +++ b/mm/interval_tree.c > @@ -28,7 +28,7 @@ INTERVAL_TREE_DEFINE(struct vm_area_struct, shared.rb, > /* Insert node immediately after prev in the interval tree */ > void vma_interval_tree_insert_after(struct vm_area_struct *node, > struct vm_area_struct *prev, > - struct rb_root *root) > + struct rb_root_cached *root) > { > struct rb_node **link; > struct vm_area_struct *parent; > @@ -55,7 +55,7 @@ void vma_interval_tree_insert_after(struct vm_area_struct *node, > > node->shared.rb_subtree_last = last; > rb_link_node(&node->shared.rb, &parent->shared.rb, link); > - rb_insert_augmented(&node->shared.rb, root, > + rb_insert_augmented(&node->shared.rb, &root->rb_root, > &vma_interval_tree_augment); > } > > @@ -74,7 +74,7 @@ INTERVAL_TREE_DEFINE(struct anon_vma_chain, rb, unsigned long, rb_subtree_last, > static inline, __anon_vma_interval_tree) > > void anon_vma_interval_tree_insert(struct anon_vma_chain *node, > - struct rb_root *root) > + struct rb_root_cached *root) > { > #ifdef CONFIG_DEBUG_VM_RB > node->cached_vma_start = avc_start_pgoff(node); > @@ -84,13 +84,13 @@ void anon_vma_interval_tree_insert(struct anon_vma_chain *node, > } > > void anon_vma_interval_tree_remove(struct anon_vma_chain *node, > - struct rb_root *root) > + struct rb_root_cached *root) > { > __anon_vma_interval_tree_remove(node, root); > } > > struct anon_vma_chain * > -anon_vma_interval_tree_iter_first(struct rb_root *root, > +anon_vma_interval_tree_iter_first(struct rb_root_cached *root, > unsigned long first, unsigned long last) > { > return __anon_vma_interval_tree_iter_first(root, first, last); > diff --git a/mm/memory.c b/mm/memory.c > index 0e517be91a89..33cb79f73394 100644 > --- a/mm/memory.c > +++ b/mm/memory.c > @@ -2593,7 +2593,7 @@ static void unmap_mapping_range_vma(struct vm_area_struct *vma, > zap_page_range_single(vma, start_addr, end_addr - start_addr, details); > } > > -static inline void unmap_mapping_range_tree(struct rb_root *root, > +static inline void unmap_mapping_range_tree(struct rb_root_cached *root, > struct zap_details *details) > { > struct vm_area_struct *vma; > @@ -2657,7 +2657,7 @@ void unmap_mapping_range(struct address_space *mapping, > details.last_index = ULONG_MAX; > > i_mmap_lock_write(mapping); > - if (unlikely(!RB_EMPTY_ROOT(&mapping->i_mmap))) > + if (unlikely(!RB_EMPTY_ROOT(&mapping->i_mmap.rb_root))) > unmap_mapping_range_tree(&mapping->i_mmap, &details); > i_mmap_unlock_write(mapping); > } > diff --git a/mm/mmap.c b/mm/mmap.c > index f19efcf75418..8121c70df96f 100644 > --- a/mm/mmap.c > +++ b/mm/mmap.c > @@ -684,7 +684,7 @@ int __vma_adjust(struct vm_area_struct *vma, unsigned long start, > struct mm_struct *mm = vma->vm_mm; > struct vm_area_struct *next = vma->vm_next, *orig_vma = vma; > struct address_space *mapping = NULL; > - struct rb_root *root = NULL; > + struct rb_root_cached *root = NULL; > struct anon_vma *anon_vma = NULL; > struct file *file = vma->vm_file; > bool start_changed = false, end_changed = false; > @@ -3314,7 +3314,7 @@ static DEFINE_MUTEX(mm_all_locks_mutex); > > static void vm_lock_anon_vma(struct mm_struct *mm, struct anon_vma *anon_vma) > { > - if (!test_bit(0, (unsigned long *) &anon_vma->root->rb_root.rb_node)) { > + if (!test_bit(0, (unsigned long *) &anon_vma->rb_root.rb_root.rb_node)) { > /* > * The LSB of head.next can't change from under us > * because we hold the mm_all_locks_mutex. > @@ -3330,7 +3330,7 @@ static void vm_lock_anon_vma(struct mm_struct *mm, struct anon_vma *anon_vma) > * anon_vma->root->rwsem. > */ > if (__test_and_set_bit(0, (unsigned long *) > - &anon_vma->root->rb_root.rb_node)) > + &anon_vma->root->rb_root.rb_root.rb_node)) > BUG(); > } > } > @@ -3432,7 +3432,7 @@ int mm_take_all_locks(struct mm_struct *mm) > > static void vm_unlock_anon_vma(struct anon_vma *anon_vma) > { > - if (test_bit(0, (unsigned long *) &anon_vma->root->rb_root.rb_node)) { > + if (test_bit(0, (unsigned long *) &anon_vma->root->rb_root.rb_root.rb_node)) { > /* > * The LSB of head.next can't change to 0 from under > * us because we hold the mm_all_locks_mutex. > @@ -3446,7 +3446,7 @@ static void vm_unlock_anon_vma(struct anon_vma *anon_vma) > * anon_vma->root->rwsem. > */ > if (!__test_and_clear_bit(0, (unsigned long *) > - &anon_vma->root->rb_root.rb_node)) > + &anon_vma->root->rb_root.rb_root.rb_node)) > BUG(); > anon_vma_unlock_write(anon_vma); > } > diff --git a/mm/rmap.c b/mm/rmap.c > index ced14f1af6dc..ad479e5e081d 100644 > --- a/mm/rmap.c > +++ b/mm/rmap.c > @@ -390,7 +390,7 @@ void unlink_anon_vmas(struct vm_area_struct *vma) > * Leave empty anon_vmas on the list - we'll need > * to free them outside the lock. > */ > - if (RB_EMPTY_ROOT(&anon_vma->rb_root)) { > + if (RB_EMPTY_ROOT(&anon_vma->rb_root.rb_root)) { > anon_vma->parent->degree--; > continue; > } > @@ -424,7 +424,7 @@ static void anon_vma_ctor(void *data) > > init_rwsem(&anon_vma->rwsem); > atomic_set(&anon_vma->refcount, 0); > - anon_vma->rb_root = RB_ROOT; > + anon_vma->rb_root = RB_ROOT_CACHED; > } > > void __init anon_vma_init(void) > -- > 2.12.0 -- To unsubscribe from this list: send the line "unsubscribe linux-rdma" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c b/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c index 38f739fb727b..3f8aef21b9a6 100644 --- a/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c +++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c @@ -51,7 +51,7 @@ struct amdgpu_mn { /* objects protected by lock */ struct mutex lock; - struct rb_root objects; + struct rb_root_cached objects; }; struct amdgpu_mn_node { @@ -76,8 +76,8 @@ static void amdgpu_mn_destroy(struct work_struct *work) mutex_lock(&adev->mn_lock); mutex_lock(&rmn->lock); hash_del(&rmn->node); - rbtree_postorder_for_each_entry_safe(node, next_node, &rmn->objects, - it.rb) { + rbtree_postorder_for_each_entry_safe(node, next_node, + &rmn->objects.rb_root, it.rb) { list_for_each_entry_safe(bo, next_bo, &node->bos, mn_list) { bo->mn = NULL; list_del_init(&bo->mn_list); @@ -252,7 +252,7 @@ static struct amdgpu_mn *amdgpu_mn_get(struct amdgpu_device *adev) rmn->mm = mm; rmn->mn.ops = &amdgpu_mn_ops; mutex_init(&rmn->lock); - rmn->objects = RB_ROOT; + rmn->objects = RB_ROOT_CACHED; r = __mmu_notifier_register(&rmn->mn, mm); if (r) diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c b/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c index 5795f81369f0..f872e2179bbd 100644 --- a/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c +++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c @@ -2405,7 +2405,7 @@ int amdgpu_vm_init(struct amdgpu_device *adev, struct amdgpu_vm *vm, int r, i; u64 flags; - vm->va = RB_ROOT; + vm->va = RB_ROOT_CACHED; vm->client_id = atomic64_inc_return(&adev->vm_manager.client_counter); for (i = 0; i < AMDGPU_MAX_VMHUBS; i++) vm->reserved_vmid[i] = NULL; @@ -2512,10 +2512,11 @@ void amdgpu_vm_fini(struct amdgpu_device *adev, struct amdgpu_vm *vm) amd_sched_entity_fini(vm->entity.sched, &vm->entity); - if (!RB_EMPTY_ROOT(&vm->va)) { + if (!RB_EMPTY_ROOT(&vm->va.rb_root)) { dev_err(adev->dev, "still active bo inside vm\n"); } - rbtree_postorder_for_each_entry_safe(mapping, tmp, &vm->va, rb) { + rbtree_postorder_for_each_entry_safe(mapping, tmp, + &vm->va.rb_root, rb) { list_del(&mapping->list); amdgpu_vm_it_remove(mapping, &vm->va); kfree(mapping); diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h b/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h index 936f158bc5ec..ebffc1253f85 100644 --- a/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h +++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h @@ -106,7 +106,7 @@ struct amdgpu_vm_pt { struct amdgpu_vm { /* tree of virtual addresses mapped */ - struct rb_root va; + struct rb_root_cached va; /* protecting invalidated */ spinlock_t status_lock; diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index f794089d30ac..61a1c8ea74bc 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -169,7 +169,7 @@ INTERVAL_TREE_DEFINE(struct drm_mm_node, rb, struct drm_mm_node * __drm_mm_interval_first(const struct drm_mm *mm, u64 start, u64 last) { - return drm_mm_interval_tree_iter_first((struct rb_root *)&mm->interval_tree, + return drm_mm_interval_tree_iter_first((struct rb_root_cached *)&mm->interval_tree, start, last) ?: (struct drm_mm_node *)&mm->head_node; } EXPORT_SYMBOL(__drm_mm_interval_first); @@ -180,6 +180,7 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, struct drm_mm *mm = hole_node->mm; struct rb_node **link, *rb; struct drm_mm_node *parent; + bool leftmost = true; node->__subtree_last = LAST(node); @@ -196,9 +197,10 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, rb = &hole_node->rb; link = &hole_node->rb.rb_right; + leftmost = false; } else { rb = NULL; - link = &mm->interval_tree.rb_node; + link = &mm->interval_tree.rb_root.rb_node; } while (*link) { @@ -208,14 +210,15 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, parent->__subtree_last = node->__subtree_last; if (node->start < parent->start) link = &parent->rb.rb_left; - else + else { link = &parent->rb.rb_right; + leftmost = true; + } } rb_link_node(&node->rb, rb, link); - rb_insert_augmented(&node->rb, - &mm->interval_tree, - &drm_mm_interval_tree_augment); + rb_insert_augmented_cached(&node->rb, &mm->interval_tree, leftmost, + &drm_mm_interval_tree_augment); } #define RB_INSERT(root, member, expr) do { \ @@ -577,7 +580,7 @@ void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new) *new = *old; list_replace(&old->node_list, &new->node_list); - rb_replace_node(&old->rb, &new->rb, &old->mm->interval_tree); + rb_replace_node(&old->rb, &new->rb, &old->mm->interval_tree.rb_root); if (drm_mm_hole_follows(old)) { list_replace(&old->hole_stack, &new->hole_stack); @@ -863,7 +866,7 @@ void drm_mm_init(struct drm_mm *mm, u64 start, u64 size) mm->color_adjust = NULL; INIT_LIST_HEAD(&mm->hole_stack); - mm->interval_tree = RB_ROOT; + mm->interval_tree = RB_ROOT_CACHED; mm->holes_size = RB_ROOT; mm->holes_addr = RB_ROOT; diff --git a/drivers/gpu/drm/drm_vma_manager.c b/drivers/gpu/drm/drm_vma_manager.c index d9100b565198..28f1226576f8 100644 --- a/drivers/gpu/drm/drm_vma_manager.c +++ b/drivers/gpu/drm/drm_vma_manager.c @@ -147,7 +147,7 @@ struct drm_vma_offset_node *drm_vma_offset_lookup_locked(struct drm_vma_offset_m struct rb_node *iter; unsigned long offset; - iter = mgr->vm_addr_space_mm.interval_tree.rb_node; + iter = mgr->vm_addr_space_mm.interval_tree.rb_root.rb_node; best = NULL; while (likely(iter)) { diff --git a/drivers/gpu/drm/i915/i915_gem_userptr.c b/drivers/gpu/drm/i915/i915_gem_userptr.c index ccd09e8419f5..71dddf66baaa 100644 --- a/drivers/gpu/drm/i915/i915_gem_userptr.c +++ b/drivers/gpu/drm/i915/i915_gem_userptr.c @@ -49,7 +49,7 @@ struct i915_mmu_notifier { spinlock_t lock; struct hlist_node node; struct mmu_notifier mn; - struct rb_root objects; + struct rb_root_cached objects; struct workqueue_struct *wq; }; @@ -123,7 +123,7 @@ static void i915_gem_userptr_mn_invalidate_range_start(struct mmu_notifier *_mn, struct interval_tree_node *it; LIST_HEAD(cancelled); - if (RB_EMPTY_ROOT(&mn->objects)) + if (RB_EMPTY_ROOT(&mn->objects.rb_root)) return; /* interval ranges are inclusive, but invalidate range is exclusive */ @@ -172,7 +172,7 @@ i915_mmu_notifier_create(struct mm_struct *mm) spin_lock_init(&mn->lock); mn->mn.ops = &i915_gem_userptr_notifier; - mn->objects = RB_ROOT; + mn->objects = RB_ROOT_CACHED; mn->wq = alloc_workqueue("i915-userptr-release", WQ_UNBOUND, 0); if (mn->wq == NULL) { kfree(mn); diff --git a/drivers/gpu/drm/radeon/radeon.h b/drivers/gpu/drm/radeon/radeon.h index 5008f3d4cccc..10d0dd146808 100644 --- a/drivers/gpu/drm/radeon/radeon.h +++ b/drivers/gpu/drm/radeon/radeon.h @@ -924,7 +924,7 @@ struct radeon_vm_id { struct radeon_vm { struct mutex mutex; - struct rb_root va; + struct rb_root_cached va; /* protecting invalidated and freed */ spinlock_t status_lock; diff --git a/drivers/gpu/drm/radeon/radeon_mn.c b/drivers/gpu/drm/radeon/radeon_mn.c index 896f2cf51e4e..1d62288b7ee3 100644 --- a/drivers/gpu/drm/radeon/radeon_mn.c +++ b/drivers/gpu/drm/radeon/radeon_mn.c @@ -50,7 +50,7 @@ struct radeon_mn { /* objects protected by lock */ struct mutex lock; - struct rb_root objects; + struct rb_root_cached objects; }; struct radeon_mn_node { @@ -75,8 +75,8 @@ static void radeon_mn_destroy(struct work_struct *work) mutex_lock(&rdev->mn_lock); mutex_lock(&rmn->lock); hash_del(&rmn->node); - rbtree_postorder_for_each_entry_safe(node, next_node, &rmn->objects, - it.rb) { + rbtree_postorder_for_each_entry_safe(node, next_node, + &rmn->objects.rb_root, it.rb) { interval_tree_remove(&node->it, &rmn->objects); list_for_each_entry_safe(bo, next_bo, &node->bos, mn_list) { @@ -205,7 +205,7 @@ static struct radeon_mn *radeon_mn_get(struct radeon_device *rdev) rmn->mm = mm; rmn->mn.ops = &radeon_mn_ops; mutex_init(&rmn->lock); - rmn->objects = RB_ROOT; + rmn->objects = RB_ROOT_CACHED; r = __mmu_notifier_register(&rmn->mn, mm); if (r) diff --git a/drivers/gpu/drm/radeon/radeon_vm.c b/drivers/gpu/drm/radeon/radeon_vm.c index 5f68245579a3..f44777a6c2e8 100644 --- a/drivers/gpu/drm/radeon/radeon_vm.c +++ b/drivers/gpu/drm/radeon/radeon_vm.c @@ -1185,7 +1185,7 @@ int radeon_vm_init(struct radeon_device *rdev, struct radeon_vm *vm) vm->ids[i].last_id_use = NULL; } mutex_init(&vm->mutex); - vm->va = RB_ROOT; + vm->va = RB_ROOT_CACHED; spin_lock_init(&vm->status_lock); INIT_LIST_HEAD(&vm->invalidated); INIT_LIST_HEAD(&vm->freed); @@ -1232,10 +1232,11 @@ void radeon_vm_fini(struct radeon_device *rdev, struct radeon_vm *vm) struct radeon_bo_va *bo_va, *tmp; int i, r; - if (!RB_EMPTY_ROOT(&vm->va)) { + if (!RB_EMPTY_ROOT(&vm->va.rb_root)) { dev_err(rdev->dev, "still active bo inside vm\n"); } - rbtree_postorder_for_each_entry_safe(bo_va, tmp, &vm->va, it.rb) { + rbtree_postorder_for_each_entry_safe(bo_va, tmp, + &vm->va.rb_root, it.rb) { interval_tree_remove(&bo_va->it, &vm->va); r = radeon_bo_reserve(bo_va->bo, false); if (!r) { diff --git a/drivers/infiniband/core/umem_rbtree.c b/drivers/infiniband/core/umem_rbtree.c index d176597b4d78..fc801920e341 100644 --- a/drivers/infiniband/core/umem_rbtree.c +++ b/drivers/infiniband/core/umem_rbtree.c @@ -72,7 +72,7 @@ INTERVAL_TREE_DEFINE(struct umem_odp_node, rb, u64, __subtree_last, /* @last is not a part of the interval. See comment for function * node_last. */ -int rbt_ib_umem_for_each_in_range(struct rb_root *root, +int rbt_ib_umem_for_each_in_range(struct rb_root_cached *root, u64 start, u64 last, umem_call_back cb, void *cookie) @@ -95,7 +95,7 @@ int rbt_ib_umem_for_each_in_range(struct rb_root *root, } EXPORT_SYMBOL(rbt_ib_umem_for_each_in_range); -struct ib_umem_odp *rbt_ib_umem_lookup(struct rb_root *root, +struct ib_umem_odp *rbt_ib_umem_lookup(struct rb_root_cached *root, u64 addr, u64 length) { struct umem_odp_node *node; diff --git a/drivers/infiniband/core/uverbs_cmd.c b/drivers/infiniband/core/uverbs_cmd.c index 3f55d18a3791..5321c6ae2c0c 100644 --- a/drivers/infiniband/core/uverbs_cmd.c +++ b/drivers/infiniband/core/uverbs_cmd.c @@ -117,7 +117,7 @@ ssize_t ib_uverbs_get_context(struct ib_uverbs_file *file, ucontext->closing = 0; #ifdef CONFIG_INFINIBAND_ON_DEMAND_PAGING - ucontext->umem_tree = RB_ROOT; + ucontext->umem_tree = RB_ROOT_CACHED; init_rwsem(&ucontext->umem_rwsem); ucontext->odp_mrs_count = 0; INIT_LIST_HEAD(&ucontext->no_private_counters); diff --git a/drivers/infiniband/hw/hfi1/mmu_rb.c b/drivers/infiniband/hw/hfi1/mmu_rb.c index d41fd87a39f2..5b6626f8feb6 100644 --- a/drivers/infiniband/hw/hfi1/mmu_rb.c +++ b/drivers/infiniband/hw/hfi1/mmu_rb.c @@ -54,7 +54,7 @@ struct mmu_rb_handler { struct mmu_notifier mn; - struct rb_root root; + struct rb_root_cached root; void *ops_arg; spinlock_t lock; /* protect the RB tree */ struct mmu_rb_ops *ops; @@ -111,7 +111,7 @@ int hfi1_mmu_rb_register(void *ops_arg, struct mm_struct *mm, if (!handlr) return -ENOMEM; - handlr->root = RB_ROOT; + handlr->root = RB_ROOT_CACHED; handlr->ops = ops; handlr->ops_arg = ops_arg; INIT_HLIST_NODE(&handlr->mn.hlist); @@ -152,9 +152,9 @@ void hfi1_mmu_rb_unregister(struct mmu_rb_handler *handler) INIT_LIST_HEAD(&del_list); spin_lock_irqsave(&handler->lock, flags); - while ((node = rb_first(&handler->root))) { + while ((node = rb_first_cached(&handler->root))) { rbnode = rb_entry(node, struct mmu_rb_node, node); - rb_erase(node, &handler->root); + rb_erase_cached(node, &handler->root); /* move from LRU list to delete list */ list_move(&rbnode->list, &del_list); } @@ -311,7 +311,7 @@ static void mmu_notifier_mem_invalidate(struct mmu_notifier *mn, { struct mmu_rb_handler *handler = container_of(mn, struct mmu_rb_handler, mn); - struct rb_root *root = &handler->root; + struct rb_root_cached *root = &handler->root; struct mmu_rb_node *node, *ptr = NULL; unsigned long flags; bool added = false; diff --git a/drivers/infiniband/hw/usnic/usnic_uiom.c b/drivers/infiniband/hw/usnic/usnic_uiom.c index c49db7c33979..4381c0a9a873 100644 --- a/drivers/infiniband/hw/usnic/usnic_uiom.c +++ b/drivers/infiniband/hw/usnic/usnic_uiom.c @@ -227,7 +227,7 @@ static void __usnic_uiom_reg_release(struct usnic_uiom_pd *pd, vpn_last = vpn_start + npages - 1; spin_lock(&pd->lock); - usnic_uiom_remove_interval(&pd->rb_root, vpn_start, + usnic_uiom_remove_interval(&pd->root, vpn_start, vpn_last, &rm_intervals); usnic_uiom_unmap_sorted_intervals(&rm_intervals, pd); @@ -379,7 +379,7 @@ struct usnic_uiom_reg *usnic_uiom_reg_get(struct usnic_uiom_pd *pd, err = usnic_uiom_get_intervals_diff(vpn_start, vpn_last, (writable) ? IOMMU_WRITE : 0, IOMMU_WRITE, - &pd->rb_root, + &pd->root, &sorted_diff_intervals); if (err) { usnic_err("Failed disjoint interval vpn [0x%lx,0x%lx] err %d\n", @@ -395,7 +395,7 @@ struct usnic_uiom_reg *usnic_uiom_reg_get(struct usnic_uiom_pd *pd, } - err = usnic_uiom_insert_interval(&pd->rb_root, vpn_start, vpn_last, + err = usnic_uiom_insert_interval(&pd->root, vpn_start, vpn_last, (writable) ? IOMMU_WRITE : 0); if (err) { usnic_err("Failed insert interval vpn [0x%lx,0x%lx] err %d\n", diff --git a/drivers/infiniband/hw/usnic/usnic_uiom.h b/drivers/infiniband/hw/usnic/usnic_uiom.h index 45ca7c1613a7..431efe4143f4 100644 --- a/drivers/infiniband/hw/usnic/usnic_uiom.h +++ b/drivers/infiniband/hw/usnic/usnic_uiom.h @@ -55,7 +55,7 @@ struct usnic_uiom_dev { struct usnic_uiom_pd { struct iommu_domain *domain; spinlock_t lock; - struct rb_root rb_root; + struct rb_root_cached root; struct list_head devs; int dev_cnt; }; diff --git a/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c b/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c index 42b4b4c4e452..d399523206c7 100644 --- a/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c +++ b/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c @@ -100,9 +100,9 @@ static int interval_cmp(void *priv, struct list_head *a, struct list_head *b) } static void -find_intervals_intersection_sorted(struct rb_root *root, unsigned long start, - unsigned long last, - struct list_head *list) +find_intervals_intersection_sorted(struct rb_root_cached *root, + unsigned long start, unsigned long last, + struct list_head *list) { struct usnic_uiom_interval_node *node; @@ -118,7 +118,7 @@ find_intervals_intersection_sorted(struct rb_root *root, unsigned long start, int usnic_uiom_get_intervals_diff(unsigned long start, unsigned long last, int flags, int flag_mask, - struct rb_root *root, + struct rb_root_cached *root, struct list_head *diff_set) { struct usnic_uiom_interval_node *interval, *tmp; @@ -175,7 +175,7 @@ void usnic_uiom_put_interval_set(struct list_head *intervals) kfree(interval); } -int usnic_uiom_insert_interval(struct rb_root *root, unsigned long start, +int usnic_uiom_insert_interval(struct rb_root_cached *root, unsigned long start, unsigned long last, int flags) { struct usnic_uiom_interval_node *interval, *tmp; @@ -246,8 +246,9 @@ int usnic_uiom_insert_interval(struct rb_root *root, unsigned long start, return err; } -void usnic_uiom_remove_interval(struct rb_root *root, unsigned long start, - unsigned long last, struct list_head *removed) +void usnic_uiom_remove_interval(struct rb_root_cached *root, + unsigned long start, unsigned long last, + struct list_head *removed) { struct usnic_uiom_interval_node *interval; diff --git a/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.h b/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.h index c0b0b876ab90..1d7fc3226bca 100644 --- a/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.h +++ b/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.h @@ -48,12 +48,12 @@ struct usnic_uiom_interval_node { extern void usnic_uiom_interval_tree_insert(struct usnic_uiom_interval_node *node, - struct rb_root *root); + struct rb_root_cached *root); extern void usnic_uiom_interval_tree_remove(struct usnic_uiom_interval_node *node, - struct rb_root *root); + struct rb_root_cached *root); extern struct usnic_uiom_interval_node * -usnic_uiom_interval_tree_iter_first(struct rb_root *root, +usnic_uiom_interval_tree_iter_first(struct rb_root_cached *root, unsigned long start, unsigned long last); extern struct usnic_uiom_interval_node * @@ -63,7 +63,7 @@ usnic_uiom_interval_tree_iter_next(struct usnic_uiom_interval_node *node, * Inserts {start...last} into {root}. If there are overlaps, * nodes will be broken up and merged */ -int usnic_uiom_insert_interval(struct rb_root *root, +int usnic_uiom_insert_interval(struct rb_root_cached *root, unsigned long start, unsigned long last, int flags); /* @@ -71,7 +71,7 @@ int usnic_uiom_insert_interval(struct rb_root *root, * 'removed.' The caller is responsibile for freeing memory of nodes in * 'removed.' */ -void usnic_uiom_remove_interval(struct rb_root *root, +void usnic_uiom_remove_interval(struct rb_root_cached *root, unsigned long start, unsigned long last, struct list_head *removed); /* @@ -81,7 +81,7 @@ void usnic_uiom_remove_interval(struct rb_root *root, int usnic_uiom_get_intervals_diff(unsigned long start, unsigned long last, int flags, int flag_mask, - struct rb_root *root, + struct rb_root_cached *root, struct list_head *diff_set); /* Call this to free diff_set returned by usnic_uiom_get_intervals_diff */ void usnic_uiom_put_interval_set(struct list_head *intervals); diff --git a/drivers/vhost/vhost.c b/drivers/vhost/vhost.c index e4613a3c362d..88dc214de068 100644 --- a/drivers/vhost/vhost.c +++ b/drivers/vhost/vhost.c @@ -1272,7 +1272,7 @@ static struct vhost_umem *vhost_umem_alloc(void) if (!umem) return NULL; - umem->umem_tree = RB_ROOT; + umem->umem_tree = RB_ROOT_CACHED; umem->numem = 0; INIT_LIST_HEAD(&umem->umem_list); diff --git a/drivers/vhost/vhost.h b/drivers/vhost/vhost.h index f72095868b93..a0278ba6a8b4 100644 --- a/drivers/vhost/vhost.h +++ b/drivers/vhost/vhost.h @@ -71,7 +71,7 @@ struct vhost_umem_node { }; struct vhost_umem { - struct rb_root umem_tree; + struct rb_root_cached umem_tree; struct list_head umem_list; int numem; }; diff --git a/fs/hugetlbfs/inode.c b/fs/hugetlbfs/inode.c index 28d2753be094..e61b91e6adf4 100644 --- a/fs/hugetlbfs/inode.c +++ b/fs/hugetlbfs/inode.c @@ -334,7 +334,7 @@ static void remove_huge_page(struct page *page) } static void -hugetlb_vmdelete_list(struct rb_root *root, pgoff_t start, pgoff_t end) +hugetlb_vmdelete_list(struct rb_root_cached *root, pgoff_t start, pgoff_t end) { struct vm_area_struct *vma; @@ -514,7 +514,7 @@ static int hugetlb_vmtruncate(struct inode *inode, loff_t offset) i_size_write(inode, offset); i_mmap_lock_write(mapping); - if (!RB_EMPTY_ROOT(&mapping->i_mmap)) + if (!RB_EMPTY_ROOT(&mapping->i_mmap.rb_root)) hugetlb_vmdelete_list(&mapping->i_mmap, pgoff, 0); i_mmap_unlock_write(mapping); remove_inode_hugepages(inode, offset, LLONG_MAX); @@ -539,7 +539,7 @@ static long hugetlbfs_punch_hole(struct inode *inode, loff_t offset, loff_t len) inode_lock(inode); i_mmap_lock_write(mapping); - if (!RB_EMPTY_ROOT(&mapping->i_mmap)) + if (!RB_EMPTY_ROOT(&mapping->i_mmap.rb_root)) hugetlb_vmdelete_list(&mapping->i_mmap, hole_start >> PAGE_SHIFT, hole_end >> PAGE_SHIFT); diff --git a/fs/inode.c b/fs/inode.c index 50370599e371..5ddb808ea934 100644 --- a/fs/inode.c +++ b/fs/inode.c @@ -353,7 +353,7 @@ void address_space_init_once(struct address_space *mapping) init_rwsem(&mapping->i_mmap_rwsem); INIT_LIST_HEAD(&mapping->private_list); spin_lock_init(&mapping->private_lock); - mapping->i_mmap = RB_ROOT; + mapping->i_mmap = RB_ROOT_CACHED; } EXPORT_SYMBOL(address_space_init_once); diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h index 49b292e98fec..8d10fc97801c 100644 --- a/include/drm/drm_mm.h +++ b/include/drm/drm_mm.h @@ -172,7 +172,7 @@ struct drm_mm { * according to the (increasing) start address of the memory node. */ struct drm_mm_node head_node; /* Keep an interval_tree for fast lookup of drm_mm_nodes by address. */ - struct rb_root interval_tree; + struct rb_root_cached interval_tree; struct rb_root holes_size; struct rb_root holes_addr; diff --git a/include/linux/fs.h b/include/linux/fs.h index ed8798255872..d1d521c5025b 100644 --- a/include/linux/fs.h +++ b/include/linux/fs.h @@ -392,7 +392,7 @@ struct address_space { struct radix_tree_root page_tree; /* radix tree of all pages */ spinlock_t tree_lock; /* and lock protecting it */ atomic_t i_mmap_writable;/* count VM_SHARED mappings */ - struct rb_root i_mmap; /* tree of private and shared mappings */ + struct rb_root_cached i_mmap; /* tree of private and shared mappings */ struct rw_semaphore i_mmap_rwsem; /* protect tree, count, list */ /* Protected by tree_lock together with the radix tree */ unsigned long nrpages; /* number of total pages */ @@ -486,7 +486,7 @@ static inline void i_mmap_unlock_read(struct address_space *mapping) */ static inline int mapping_mapped(struct address_space *mapping) { - return !RB_EMPTY_ROOT(&mapping->i_mmap); + return !RB_EMPTY_ROOT(&mapping->i_mmap.rb_root); } /* diff --git a/include/linux/interval_tree.h b/include/linux/interval_tree.h index 724556aa3c95..202ee1283f4b 100644 --- a/include/linux/interval_tree.h +++ b/include/linux/interval_tree.h @@ -11,13 +11,15 @@ struct interval_tree_node { }; extern void -interval_tree_insert(struct interval_tree_node *node, struct rb_root *root); +interval_tree_insert(struct interval_tree_node *node, + struct rb_root_cached *root); extern void -interval_tree_remove(struct interval_tree_node *node, struct rb_root *root); +interval_tree_remove(struct interval_tree_node *node, + struct rb_root_cached *root); extern struct interval_tree_node * -interval_tree_iter_first(struct rb_root *root, +interval_tree_iter_first(struct rb_root_cached *root, unsigned long start, unsigned long last); extern struct interval_tree_node * diff --git a/include/linux/interval_tree_generic.h b/include/linux/interval_tree_generic.h index 58370e1862ad..f096423c8cbd 100644 --- a/include/linux/interval_tree_generic.h +++ b/include/linux/interval_tree_generic.h @@ -65,11 +65,13 @@ RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB, \ \ /* Insert / remove interval nodes from the tree */ \ \ -ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, struct rb_root *root) \ +ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, \ + struct rb_root_cached *root) \ { \ - struct rb_node **link = &root->rb_node, *rb_parent = NULL; \ + struct rb_node **link = &root->rb_root.rb_node, *rb_parent = NULL; \ ITTYPE start = ITSTART(node), last = ITLAST(node); \ ITSTRUCT *parent; \ + bool leftmost = true; \ \ while (*link) { \ rb_parent = *link; \ @@ -78,18 +80,22 @@ ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, struct rb_root *root) \ parent->ITSUBTREE = last; \ if (start < ITSTART(parent)) \ link = &parent->ITRB.rb_left; \ - else \ + else { \ link = &parent->ITRB.rb_right; \ + leftmost = false; \ + } \ } \ \ node->ITSUBTREE = last; \ rb_link_node(&node->ITRB, rb_parent, link); \ - rb_insert_augmented(&node->ITRB, root, &ITPREFIX ## _augment); \ + rb_insert_augmented_cached(&node->ITRB, root, \ + leftmost, &ITPREFIX ## _augment); \ } \ \ -ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, struct rb_root *root) \ +ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, \ + struct rb_root_cached *root) \ { \ - rb_erase_augmented(&node->ITRB, root, &ITPREFIX ## _augment); \ + rb_erase_augmented_cached(&node->ITRB, root, &ITPREFIX ## _augment); \ } \ \ /* \ @@ -140,15 +146,35 @@ ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ } \ \ ITSTATIC ITSTRUCT * \ -ITPREFIX ## _iter_first(struct rb_root *root, ITTYPE start, ITTYPE last) \ +ITPREFIX ## _iter_first(struct rb_root_cached *root, \ + ITTYPE start, ITTYPE last) \ { \ - ITSTRUCT *node; \ + ITSTRUCT *node, *leftmost; \ \ - if (!root->rb_node) \ + if (!root->rb_root.rb_node) \ return NULL; \ - node = rb_entry(root->rb_node, ITSTRUCT, ITRB); \ + \ + /* \ + * Fastpath range intersection/overlap between A: [a0, a1] and \ + * B: [b0, b1] is given by: \ + * \ + * a0 <= b1 && b0 <= a1 \ + * \ + * ... where A holds the lock range and B holds the smallest \ + * 'start' and largest 'last' in the tree. For the later, we \ + * rely on the root node, which by augmented interval tree \ + * property, holds the largest value in its last-in-subtree. \ + * This allows mitigating some of the tree walk overhead for \ + * for non-intersecting ranges, maintained and consulted in O(1). \ + */ \ + node = rb_entry(root->rb_root.rb_node, ITSTRUCT, ITRB); \ if (node->ITSUBTREE < start) \ return NULL; \ + \ + leftmost = rb_entry(root->rb_leftmost, ITSTRUCT, ITRB); \ + if (ITSTART(leftmost) > last) \ + return NULL; \ + \ return ITPREFIX ## _subtree_search(node, start, last); \ } \ \ diff --git a/include/linux/mm.h b/include/linux/mm.h index 46b9ac5e8569..3a2652efbbfb 100644 --- a/include/linux/mm.h +++ b/include/linux/mm.h @@ -1992,13 +1992,13 @@ extern int nommu_shrink_inode_mappings(struct inode *, size_t, size_t); /* interval_tree.c */ void vma_interval_tree_insert(struct vm_area_struct *node, - struct rb_root *root); + struct rb_root_cached *root); void vma_interval_tree_insert_after(struct vm_area_struct *node, struct vm_area_struct *prev, - struct rb_root *root); + struct rb_root_cached *root); void vma_interval_tree_remove(struct vm_area_struct *node, - struct rb_root *root); -struct vm_area_struct *vma_interval_tree_iter_first(struct rb_root *root, + struct rb_root_cached *root); +struct vm_area_struct *vma_interval_tree_iter_first(struct rb_root_cached *root, unsigned long start, unsigned long last); struct vm_area_struct *vma_interval_tree_iter_next(struct vm_area_struct *node, unsigned long start, unsigned long last); @@ -2008,11 +2008,12 @@ struct vm_area_struct *vma_interval_tree_iter_next(struct vm_area_struct *node, vma; vma = vma_interval_tree_iter_next(vma, start, last)) void anon_vma_interval_tree_insert(struct anon_vma_chain *node, - struct rb_root *root); + struct rb_root_cached *root); void anon_vma_interval_tree_remove(struct anon_vma_chain *node, - struct rb_root *root); -struct anon_vma_chain *anon_vma_interval_tree_iter_first( - struct rb_root *root, unsigned long start, unsigned long last); + struct rb_root_cached *root); +struct anon_vma_chain * +anon_vma_interval_tree_iter_first(struct rb_root_cached *root, + unsigned long start, unsigned long last); struct anon_vma_chain *anon_vma_interval_tree_iter_next( struct anon_vma_chain *node, unsigned long start, unsigned long last); #ifdef CONFIG_DEBUG_VM_RB diff --git a/include/linux/rmap.h b/include/linux/rmap.h index 43ef2c30cb0f..22c298c6cc26 100644 --- a/include/linux/rmap.h +++ b/include/linux/rmap.h @@ -55,7 +55,9 @@ struct anon_vma { * is serialized by a system wide lock only visible to * mm_take_all_locks() (mm_all_locks_mutex). */ - struct rb_root rb_root; /* Interval tree of private "related" vmas */ + + /* Interval tree of private "related" vmas */ + struct rb_root_cached rb_root; }; /* diff --git a/include/rdma/ib_umem_odp.h b/include/rdma/ib_umem_odp.h index fb67554aabd6..5eb7f5bc8248 100644 --- a/include/rdma/ib_umem_odp.h +++ b/include/rdma/ib_umem_odp.h @@ -111,22 +111,25 @@ int ib_umem_odp_map_dma_pages(struct ib_umem *umem, u64 start_offset, u64 bcnt, void ib_umem_odp_unmap_dma_pages(struct ib_umem *umem, u64 start_offset, u64 bound); -void rbt_ib_umem_insert(struct umem_odp_node *node, struct rb_root *root); -void rbt_ib_umem_remove(struct umem_odp_node *node, struct rb_root *root); +void rbt_ib_umem_insert(struct umem_odp_node *node, + struct rb_root_cached *root); +void rbt_ib_umem_remove(struct umem_odp_node *node, + struct rb_root_cached *root); typedef int (*umem_call_back)(struct ib_umem *item, u64 start, u64 end, void *cookie); /* * Call the callback on each ib_umem in the range. Returns the logical or of * the return values of the functions called. */ -int rbt_ib_umem_for_each_in_range(struct rb_root *root, u64 start, u64 end, +int rbt_ib_umem_for_each_in_range(struct rb_root_cached *root, + u64 start, u64 end, umem_call_back cb, void *cookie); /* * Find first region intersecting with address range. * Return NULL if not found */ -struct ib_umem_odp *rbt_ib_umem_lookup(struct rb_root *root, +struct ib_umem_odp *rbt_ib_umem_lookup(struct rb_root_cached *root, u64 addr, u64 length); static inline int ib_umem_mmu_notifier_retry(struct ib_umem *item, diff --git a/include/rdma/ib_verbs.h b/include/rdma/ib_verbs.h index 593ad2640d2f..81665480a4ab 100644 --- a/include/rdma/ib_verbs.h +++ b/include/rdma/ib_verbs.h @@ -1420,7 +1420,7 @@ struct ib_ucontext { struct pid *tgid; #ifdef CONFIG_INFINIBAND_ON_DEMAND_PAGING - struct rb_root umem_tree; + struct rb_root_cached umem_tree; /* * Protects .umem_rbroot and tree, as well as odp_mrs_count and * mmu notifiers registration. diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c index df495fe81421..0e343fd29570 100644 --- a/lib/interval_tree_test.c +++ b/lib/interval_tree_test.c @@ -19,14 +19,14 @@ __param(bool, search_all, false, "Searches will iterate all nodes in the tree"); __param(uint, max_endpoint, ~0, "Largest value for the interval's endpoint"); -static struct rb_root root = RB_ROOT; +static struct rb_root_cached root = RB_ROOT_CACHED; static struct interval_tree_node *nodes = NULL; static u32 *queries = NULL; static struct rnd_state rnd; static inline unsigned long -search(struct rb_root *root, unsigned long start, unsigned long last) +search(struct rb_root_cached *root, unsigned long start, unsigned long last) { struct interval_tree_node *node; unsigned long results = 0; diff --git a/mm/interval_tree.c b/mm/interval_tree.c index f2c2492681bf..b47664358796 100644 --- a/mm/interval_tree.c +++ b/mm/interval_tree.c @@ -28,7 +28,7 @@ INTERVAL_TREE_DEFINE(struct vm_area_struct, shared.rb, /* Insert node immediately after prev in the interval tree */ void vma_interval_tree_insert_after(struct vm_area_struct *node, struct vm_area_struct *prev, - struct rb_root *root) + struct rb_root_cached *root) { struct rb_node **link; struct vm_area_struct *parent; @@ -55,7 +55,7 @@ void vma_interval_tree_insert_after(struct vm_area_struct *node, node->shared.rb_subtree_last = last; rb_link_node(&node->shared.rb, &parent->shared.rb, link); - rb_insert_augmented(&node->shared.rb, root, + rb_insert_augmented(&node->shared.rb, &root->rb_root, &vma_interval_tree_augment); } @@ -74,7 +74,7 @@ INTERVAL_TREE_DEFINE(struct anon_vma_chain, rb, unsigned long, rb_subtree_last, static inline, __anon_vma_interval_tree) void anon_vma_interval_tree_insert(struct anon_vma_chain *node, - struct rb_root *root) + struct rb_root_cached *root) { #ifdef CONFIG_DEBUG_VM_RB node->cached_vma_start = avc_start_pgoff(node); @@ -84,13 +84,13 @@ void anon_vma_interval_tree_insert(struct anon_vma_chain *node, } void anon_vma_interval_tree_remove(struct anon_vma_chain *node, - struct rb_root *root) + struct rb_root_cached *root) { __anon_vma_interval_tree_remove(node, root); } struct anon_vma_chain * -anon_vma_interval_tree_iter_first(struct rb_root *root, +anon_vma_interval_tree_iter_first(struct rb_root_cached *root, unsigned long first, unsigned long last) { return __anon_vma_interval_tree_iter_first(root, first, last); diff --git a/mm/memory.c b/mm/memory.c index 0e517be91a89..33cb79f73394 100644 --- a/mm/memory.c +++ b/mm/memory.c @@ -2593,7 +2593,7 @@ static void unmap_mapping_range_vma(struct vm_area_struct *vma, zap_page_range_single(vma, start_addr, end_addr - start_addr, details); } -static inline void unmap_mapping_range_tree(struct rb_root *root, +static inline void unmap_mapping_range_tree(struct rb_root_cached *root, struct zap_details *details) { struct vm_area_struct *vma; @@ -2657,7 +2657,7 @@ void unmap_mapping_range(struct address_space *mapping, details.last_index = ULONG_MAX; i_mmap_lock_write(mapping); - if (unlikely(!RB_EMPTY_ROOT(&mapping->i_mmap))) + if (unlikely(!RB_EMPTY_ROOT(&mapping->i_mmap.rb_root))) unmap_mapping_range_tree(&mapping->i_mmap, &details); i_mmap_unlock_write(mapping); } diff --git a/mm/mmap.c b/mm/mmap.c index f19efcf75418..8121c70df96f 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -684,7 +684,7 @@ int __vma_adjust(struct vm_area_struct *vma, unsigned long start, struct mm_struct *mm = vma->vm_mm; struct vm_area_struct *next = vma->vm_next, *orig_vma = vma; struct address_space *mapping = NULL; - struct rb_root *root = NULL; + struct rb_root_cached *root = NULL; struct anon_vma *anon_vma = NULL; struct file *file = vma->vm_file; bool start_changed = false, end_changed = false; @@ -3314,7 +3314,7 @@ static DEFINE_MUTEX(mm_all_locks_mutex); static void vm_lock_anon_vma(struct mm_struct *mm, struct anon_vma *anon_vma) { - if (!test_bit(0, (unsigned long *) &anon_vma->root->rb_root.rb_node)) { + if (!test_bit(0, (unsigned long *) &anon_vma->rb_root.rb_root.rb_node)) { /* * The LSB of head.next can't change from under us * because we hold the mm_all_locks_mutex. @@ -3330,7 +3330,7 @@ static void vm_lock_anon_vma(struct mm_struct *mm, struct anon_vma *anon_vma) * anon_vma->root->rwsem. */ if (__test_and_set_bit(0, (unsigned long *) - &anon_vma->root->rb_root.rb_node)) + &anon_vma->root->rb_root.rb_root.rb_node)) BUG(); } } @@ -3432,7 +3432,7 @@ int mm_take_all_locks(struct mm_struct *mm) static void vm_unlock_anon_vma(struct anon_vma *anon_vma) { - if (test_bit(0, (unsigned long *) &anon_vma->root->rb_root.rb_node)) { + if (test_bit(0, (unsigned long *) &anon_vma->root->rb_root.rb_root.rb_node)) { /* * The LSB of head.next can't change to 0 from under * us because we hold the mm_all_locks_mutex. @@ -3446,7 +3446,7 @@ static void vm_unlock_anon_vma(struct anon_vma *anon_vma) * anon_vma->root->rwsem. */ if (!__test_and_clear_bit(0, (unsigned long *) - &anon_vma->root->rb_root.rb_node)) + &anon_vma->root->rb_root.rb_root.rb_node)) BUG(); anon_vma_unlock_write(anon_vma); } diff --git a/mm/rmap.c b/mm/rmap.c index ced14f1af6dc..ad479e5e081d 100644 --- a/mm/rmap.c +++ b/mm/rmap.c @@ -390,7 +390,7 @@ void unlink_anon_vmas(struct vm_area_struct *vma) * Leave empty anon_vmas on the list - we'll need * to free them outside the lock. */ - if (RB_EMPTY_ROOT(&anon_vma->rb_root)) { + if (RB_EMPTY_ROOT(&anon_vma->rb_root.rb_root)) { anon_vma->parent->degree--; continue; } @@ -424,7 +424,7 @@ static void anon_vma_ctor(void *data) init_rwsem(&anon_vma->rwsem); atomic_set(&anon_vma->refcount, 0); - anon_vma->rb_root = RB_ROOT; + anon_vma->rb_root = RB_ROOT_CACHED; } void __init anon_vma_init(void)