1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3 * mm/interval_tree.c - interval tree for address_space->i_mmap and
4 * anon_vma->rb_root
5 *
6 * Copyright (C) 2012, Michel Lespinasse <walken@google.com>
7 */
8
9 #include <linux/mm.h>
10 #include <linux/fs.h>
11 #include <linux/rmap.h>
12 #include <linux/interval_tree_generic.h>
13
14 /* File-backed interval tree (address_space->i_mmap) */
15
16 INTERVAL_TREE_DEFINE(struct vm_area_struct, shared.rb,
17 pgoff_t, shared.rb_subtree_last,
18 vma_start_pgoff, vma_last_pgoff, static,
19 __mapping_rmap_tree)
20
mapping_rmap_tree_insert(struct vm_area_struct * vma,struct address_space * mapping)21 void mapping_rmap_tree_insert(struct vm_area_struct *vma,
22 struct address_space *mapping)
23 {
24 __mapping_rmap_tree_insert(vma, &mapping->i_mmap);
25 }
26
27 /* Insert vma immediately after prev in the interval tree */
mapping_rmap_tree_insert_after(struct vm_area_struct * vma,struct vm_area_struct * prev,struct address_space * mapping)28 void mapping_rmap_tree_insert_after(struct vm_area_struct *vma,
29 struct vm_area_struct *prev,
30 struct address_space *mapping)
31 {
32 struct rb_node **link;
33 struct vm_area_struct *parent;
34 const pgoff_t pgoff_last = vma_last_pgoff(vma);
35
36 VM_WARN_ON_ONCE_VMA(vma_start_pgoff(vma) != vma_start_pgoff(prev), vma);
37
38 if (!prev->shared.rb.rb_right) {
39 parent = prev;
40 link = &prev->shared.rb.rb_right;
41 } else {
42 parent = rb_entry(prev->shared.rb.rb_right,
43 struct vm_area_struct, shared.rb);
44 if (parent->shared.rb_subtree_last < pgoff_last)
45 parent->shared.rb_subtree_last = pgoff_last;
46 while (parent->shared.rb.rb_left) {
47 parent = rb_entry(parent->shared.rb.rb_left,
48 struct vm_area_struct, shared.rb);
49 if (parent->shared.rb_subtree_last < pgoff_last)
50 parent->shared.rb_subtree_last = pgoff_last;
51 }
52 link = &parent->shared.rb.rb_left;
53 }
54
55 vma->shared.rb_subtree_last = pgoff_last;
56 rb_link_node(&vma->shared.rb, &parent->shared.rb, link);
57 rb_insert_augmented(&vma->shared.rb, &mapping->i_mmap.rb_root,
58 &__mapping_rmap_tree_augment);
59 }
60
mapping_rmap_tree_remove(struct vm_area_struct * vma,struct address_space * mapping)61 void mapping_rmap_tree_remove(struct vm_area_struct *vma,
62 struct address_space *mapping)
63 {
64 __mapping_rmap_tree_remove(vma, &mapping->i_mmap);
65 }
66
67 struct vm_area_struct *
mapping_rmap_tree_iter_first(struct address_space * mapping,pgoff_t pgoff_start,pgoff_t pgoff_last)68 mapping_rmap_tree_iter_first(struct address_space *mapping,
69 pgoff_t pgoff_start, pgoff_t pgoff_last)
70 {
71 return __mapping_rmap_tree_iter_first(&mapping->i_mmap,
72 pgoff_start, pgoff_last);
73 }
74
75 struct vm_area_struct *
mapping_rmap_tree_iter_next(struct vm_area_struct * vma,pgoff_t pgoff_start,pgoff_t pgoff_last)76 mapping_rmap_tree_iter_next(struct vm_area_struct *vma,
77 pgoff_t pgoff_start, pgoff_t pgoff_last)
78 {
79 return __mapping_rmap_tree_iter_next(vma, pgoff_start, pgoff_last);
80 }
81
82 /* Anonymous interval tree (anon_vma->rb_root) */
83
avc_start_pgoff(struct anon_vma_chain * avc)84 static pgoff_t avc_start_pgoff(struct anon_vma_chain *avc)
85 {
86 return vma_start_anon_pgoff(avc->vma);
87 }
88
avc_last_pgoff(struct anon_vma_chain * avc)89 static pgoff_t avc_last_pgoff(struct anon_vma_chain *avc)
90 {
91 return vma_last_anon_pgoff(avc->vma);
92 }
93
INTERVAL_TREE_DEFINE(struct anon_vma_chain,rb,pgoff_t,rb_subtree_last,avc_start_pgoff,avc_last_pgoff,static,__anon_rmap_tree)94 INTERVAL_TREE_DEFINE(struct anon_vma_chain, rb, pgoff_t, rb_subtree_last,
95 avc_start_pgoff, avc_last_pgoff,
96 static, __anon_rmap_tree)
97
98 void anon_rmap_tree_insert(struct anon_vma_chain *avc,
99 struct anon_vma *anon_vma)
100 {
101 #ifdef CONFIG_DEBUG_VM_RB
102 avc->cached_vma_start = avc_start_pgoff(avc);
103 avc->cached_vma_last = avc_last_pgoff(avc);
104 #endif
105 __anon_rmap_tree_insert(avc, &anon_vma->rb_root);
106 }
107
anon_rmap_tree_remove(struct anon_vma_chain * avc,struct anon_vma * anon_vma)108 void anon_rmap_tree_remove(struct anon_vma_chain *avc,
109 struct anon_vma *anon_vma)
110 {
111 __anon_rmap_tree_remove(avc, &anon_vma->rb_root);
112 }
113
114 struct anon_vma_chain *
anon_rmap_tree_iter_first(struct anon_vma * anon_vma,pgoff_t pgoff_start,pgoff_t pgoff_last)115 anon_rmap_tree_iter_first(struct anon_vma *anon_vma,
116 pgoff_t pgoff_start, pgoff_t pgoff_last)
117 {
118 return __anon_rmap_tree_iter_first(&anon_vma->rb_root,
119 pgoff_start, pgoff_last);
120 }
121
122 struct anon_vma_chain *
anon_rmap_tree_iter_next(struct anon_vma_chain * avc,pgoff_t pgoff_start,pgoff_t pgoff_last)123 anon_rmap_tree_iter_next(struct anon_vma_chain *avc,
124 pgoff_t pgoff_start, pgoff_t pgoff_last)
125 {
126 return __anon_rmap_tree_iter_next(avc, pgoff_start, pgoff_last);
127 }
128
129 #ifdef CONFIG_DEBUG_VM_RB
anon_rmap_tree_verify(struct anon_vma_chain * avc)130 void anon_rmap_tree_verify(struct anon_vma_chain *avc)
131 {
132 WARN_ON_ONCE(avc->cached_vma_start != avc_start_pgoff(avc));
133 WARN_ON_ONCE(avc->cached_vma_last != avc_last_pgoff(avc));
134 }
135 #endif
136