18092f73cSThomas 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
vma_start_pgoff(struct vm_area_struct * v)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
vma_last_pgoff(struct vm_area_struct * v)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,
25*0c1dcb05SZhiyuan Dai vma_start_pgoff, vma_last_pgoff, /* empty */, vma_interval_tree)
269826a516SMichel Lespinasse
279826a516SMichel Lespinasse /* Insert node immediately after prev in the interval tree */
vma_interval_tree_insert_after(struct vm_area_struct * node,struct vm_area_struct * prev,struct rb_root_cached * root)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
avc_start_pgoff(struct anon_vma_chain * avc)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
avc_last_pgoff(struct anon_vma_chain * avc)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
INTERVAL_TREE_DEFINE(struct anon_vma_chain,rb,unsigned long,rb_subtree_last,avc_start_pgoff,avc_last_pgoff,static inline,__anon_vma_interval_tree)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
anon_vma_interval_tree_remove(struct anon_vma_chain * node,struct rb_root_cached * root)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 *
anon_vma_interval_tree_iter_first(struct rb_root_cached * root,unsigned long first,unsigned long last)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 *
anon_vma_interval_tree_iter_next(struct anon_vma_chain * node,unsigned long first,unsigned long last)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
anon_vma_interval_tree_verify(struct anon_vma_chain * node)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