projects/linux·blob assoc-array-fixes · refs

135 lines · 3.8 KiB

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 <[email protected]>
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
16INTERVAL_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
21void 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 */
28void 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
61void 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
67struct vm_area_struct *
68mapping_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
75struct vm_area_struct *
76mapping_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
84static pgoff_t avc_start_pgoff(struct anon_vma_chain *avc)
85{
86 return vma_start_anon_pgoff(avc->vma);
87}
88
89static pgoff_t avc_last_pgoff(struct anon_vma_chain *avc)
90{
91 return vma_last_anon_pgoff(avc->vma);
92}
93
94INTERVAL_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
98void 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
108void 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
114struct anon_vma_chain *
115anon_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
122struct anon_vma_chain *
123anon_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
130void 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