1*8092f73cSThomas Gleixner // SPDX-License-Identifier: GPL-2.0-only 26b2dbba8SMichel Lespinasse /* 36b2dbba8SMichel Lespinasse * mm/interval_tree.c - interval tree for mapping->i_mmap 46b2dbba8SMichel Lespinasse * 56b2dbba8SMichel Lespinasse * Copyright (C) 2012, Michel Lespinasse <walken@google.com> 66b2dbba8SMichel Lespinasse */ 76b2dbba8SMichel Lespinasse 86b2dbba8SMichel Lespinasse #include <linux/mm.h> 96b2dbba8SMichel Lespinasse #include <linux/fs.h> 10bf181b9fSMichel Lespinasse #include <linux/rmap.h> 119826a516SMichel Lespinasse #include <linux/interval_tree_generic.h> 126b2dbba8SMichel Lespinasse 139826a516SMichel Lespinasse static inline unsigned long vma_start_pgoff(struct vm_area_struct *v) 149826a516SMichel Lespinasse { 159826a516SMichel Lespinasse return v->vm_pgoff; 169826a516SMichel Lespinasse } 176b2dbba8SMichel Lespinasse 189826a516SMichel Lespinasse static inline unsigned long vma_last_pgoff(struct vm_area_struct *v) 199826a516SMichel Lespinasse { 20e025f059SVasyl Gomonovych return v->vm_pgoff + vma_pages(v) - 1; 219826a516SMichel Lespinasse } 226b2dbba8SMichel Lespinasse 23ac51b934SKirill A. Shutemov INTERVAL_TREE_DEFINE(struct vm_area_struct, shared.rb, 24ac51b934SKirill A. Shutemov unsigned long, shared.rb_subtree_last, 259826a516SMichel Lespinasse vma_start_pgoff, vma_last_pgoff,, vma_interval_tree) 269826a516SMichel Lespinasse 279826a516SMichel Lespinasse /* Insert node immediately after prev in the interval tree */ 289826a516SMichel Lespinasse void vma_interval_tree_insert_after(struct vm_area_struct *node, 299826a516SMichel Lespinasse struct vm_area_struct *prev, 30f808c13fSDavidlohr Bueso struct rb_root_cached *root) 316b2dbba8SMichel Lespinasse { 326b2dbba8SMichel Lespinasse struct rb_node **link; 336b2dbba8SMichel Lespinasse struct vm_area_struct *parent; 349826a516SMichel Lespinasse unsigned long last = vma_last_pgoff(node); 356b2dbba8SMichel Lespinasse 3681d1b09cSSasha Levin VM_BUG_ON_VMA(vma_start_pgoff(node) != vma_start_pgoff(prev), node); 376b2dbba8SMichel Lespinasse 38ac51b934SKirill A. Shutemov if (!prev->shared.rb.rb_right) { 399826a516SMichel Lespinasse parent = prev; 40ac51b934SKirill A. Shutemov link = &prev->shared.rb.rb_right; 416b2dbba8SMichel Lespinasse } else { 42ac51b934SKirill A. Shutemov parent = rb_entry(prev->shared.rb.rb_right, 43ac51b934SKirill A. Shutemov struct vm_area_struct, shared.rb); 44ac51b934SKirill A. Shutemov if (parent->shared.rb_subtree_last < last) 45ac51b934SKirill A. Shutemov parent->shared.rb_subtree_last = last; 46ac51b934SKirill A. Shutemov while (parent->shared.rb.rb_left) { 47ac51b934SKirill A. Shutemov parent = rb_entry(parent->shared.rb.rb_left, 48ac51b934SKirill A. Shutemov struct vm_area_struct, shared.rb); 49ac51b934SKirill A. Shutemov if (parent->shared.rb_subtree_last < last) 50ac51b934SKirill A. Shutemov parent->shared.rb_subtree_last = last; 516b2dbba8SMichel Lespinasse } 52ac51b934SKirill A. Shutemov link = &parent->shared.rb.rb_left; 536b2dbba8SMichel Lespinasse } 546b2dbba8SMichel Lespinasse 55ac51b934SKirill A. Shutemov node->shared.rb_subtree_last = last; 56ac51b934SKirill A. Shutemov rb_link_node(&node->shared.rb, &parent->shared.rb, link); 57f808c13fSDavidlohr Bueso rb_insert_augmented(&node->shared.rb, &root->rb_root, 589826a516SMichel Lespinasse &vma_interval_tree_augment); 596b2dbba8SMichel Lespinasse } 60bf181b9fSMichel Lespinasse 61bf181b9fSMichel Lespinasse static inline unsigned long avc_start_pgoff(struct anon_vma_chain *avc) 62bf181b9fSMichel Lespinasse { 63bf181b9fSMichel Lespinasse return vma_start_pgoff(avc->vma); 64bf181b9fSMichel Lespinasse } 65bf181b9fSMichel Lespinasse 66bf181b9fSMichel Lespinasse static inline unsigned long avc_last_pgoff(struct anon_vma_chain *avc) 67bf181b9fSMichel Lespinasse { 68bf181b9fSMichel Lespinasse return vma_last_pgoff(avc->vma); 69bf181b9fSMichel Lespinasse } 70bf181b9fSMichel Lespinasse 71bf181b9fSMichel Lespinasse INTERVAL_TREE_DEFINE(struct anon_vma_chain, rb, unsigned long, rb_subtree_last, 72ed8ea815SMichel Lespinasse avc_start_pgoff, avc_last_pgoff, 73ed8ea815SMichel Lespinasse static inline, __anon_vma_interval_tree) 74ed8ea815SMichel Lespinasse 75ed8ea815SMichel Lespinasse void anon_vma_interval_tree_insert(struct anon_vma_chain *node, 76f808c13fSDavidlohr Bueso struct rb_root_cached *root) 77ed8ea815SMichel Lespinasse { 78ed8ea815SMichel Lespinasse #ifdef CONFIG_DEBUG_VM_RB 79ed8ea815SMichel Lespinasse node->cached_vma_start = avc_start_pgoff(node); 80ed8ea815SMichel Lespinasse node->cached_vma_last = avc_last_pgoff(node); 81ed8ea815SMichel Lespinasse #endif 82ed8ea815SMichel Lespinasse __anon_vma_interval_tree_insert(node, root); 83ed8ea815SMichel Lespinasse } 84ed8ea815SMichel Lespinasse 85ed8ea815SMichel Lespinasse void anon_vma_interval_tree_remove(struct anon_vma_chain *node, 86f808c13fSDavidlohr Bueso struct rb_root_cached *root) 87ed8ea815SMichel Lespinasse { 88ed8ea815SMichel Lespinasse __anon_vma_interval_tree_remove(node, root); 89ed8ea815SMichel Lespinasse } 90ed8ea815SMichel Lespinasse 91ed8ea815SMichel Lespinasse struct anon_vma_chain * 92f808c13fSDavidlohr Bueso anon_vma_interval_tree_iter_first(struct rb_root_cached *root, 93ed8ea815SMichel Lespinasse unsigned long first, unsigned long last) 94ed8ea815SMichel Lespinasse { 95ed8ea815SMichel Lespinasse return __anon_vma_interval_tree_iter_first(root, first, last); 96ed8ea815SMichel Lespinasse } 97ed8ea815SMichel Lespinasse 98ed8ea815SMichel Lespinasse struct anon_vma_chain * 99ed8ea815SMichel Lespinasse anon_vma_interval_tree_iter_next(struct anon_vma_chain *node, 100ed8ea815SMichel Lespinasse unsigned long first, unsigned long last) 101ed8ea815SMichel Lespinasse { 102ed8ea815SMichel Lespinasse return __anon_vma_interval_tree_iter_next(node, first, last); 103ed8ea815SMichel Lespinasse } 104ed8ea815SMichel Lespinasse 105ed8ea815SMichel Lespinasse #ifdef CONFIG_DEBUG_VM_RB 106ed8ea815SMichel Lespinasse void anon_vma_interval_tree_verify(struct anon_vma_chain *node) 107ed8ea815SMichel Lespinasse { 108ed8ea815SMichel Lespinasse WARN_ON_ONCE(node->cached_vma_start != avc_start_pgoff(node)); 109ed8ea815SMichel Lespinasse WARN_ON_ONCE(node->cached_vma_last != avc_last_pgoff(node)); 110ed8ea815SMichel Lespinasse } 111ed8ea815SMichel Lespinasse #endif 112