Re: [PATCH 11/17] lib/interval_tree: fast overlap detection
From: Michael S. Tsirkin
Date: Tue Aug 01 2017 - 13:16:47 EST
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@xxxxxxxx>
> Cc: dri-devel@xxxxxxxxxxxxxxxxxxxxx
> Cc: "Michael S. Tsirkin" <mst@xxxxxxxxxx>
> Cc: Jason Wang <jasowang@xxxxxxxxxx>
> Cc: Doug Ledford <dledford@xxxxxxxxxx>
> Cc: Christian Benvenuti <benve@xxxxxxxxx>
> Cc: linux-rdma@xxxxxxxxxxxxxxx
> Acked-by: Christian König <christian.koenig@xxxxxxx>
> Acked-by: Peter Zijlstra (Intel) <peterz@xxxxxxxxxxxxx>
> Signed-off-by: Davidlohr Bueso <dbueso@xxxxxxx>
For vhost bits:
Acked-by: Michael S. Tsirkin <mst@xxxxxxxxxx>
> ---
> 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