1
2
3
4
5
6
7
8
9
10
11
12
13
14#include <linux/mm.h>
15#include <linux/prio_tree.h>
16
17
18
19
20
21
22
23
24
25
26
27
28#define RADIX_INDEX(vma) ((vma)->vm_pgoff)
29#define VMA_SIZE(vma) (((vma)->vm_end - (vma)->vm_start) >> PAGE_SHIFT)
30
31#define HEAP_INDEX(vma) ((vma)->vm_pgoff + (VMA_SIZE(vma) - 1))
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75void vma_prio_tree_add(struct vm_area_struct *vma, struct vm_area_struct *old)
76{
77
78 BUG_ON(RADIX_INDEX(vma) != RADIX_INDEX(old));
79 BUG_ON(HEAP_INDEX(vma) != HEAP_INDEX(old));
80
81 vma->shared.vm_set.head = NULL;
82 vma->shared.vm_set.parent = NULL;
83
84 if (!old->shared.vm_set.parent)
85 list_add(&vma->shared.vm_set.list,
86 &old->shared.vm_set.list);
87 else if (old->shared.vm_set.head)
88 list_add_tail(&vma->shared.vm_set.list,
89 &old->shared.vm_set.head->shared.vm_set.list);
90 else {
91 INIT_LIST_HEAD(&vma->shared.vm_set.list);
92 vma->shared.vm_set.head = old;
93 old->shared.vm_set.head = vma;
94 }
95}
96
97void vma_prio_tree_insert(struct vm_area_struct *vma,
98 struct prio_tree_root *root)
99{
100 struct prio_tree_node *ptr;
101 struct vm_area_struct *old;
102
103 vma->shared.vm_set.head = NULL;
104
105 ptr = raw_prio_tree_insert(root, &vma->shared.prio_tree_node);
106 if (ptr != (struct prio_tree_node *) &vma->shared.prio_tree_node) {
107 old = prio_tree_entry(ptr, struct vm_area_struct,
108 shared.prio_tree_node);
109 vma_prio_tree_add(vma, old);
110 }
111}
112
113void vma_prio_tree_remove(struct vm_area_struct *vma,
114 struct prio_tree_root *root)
115{
116 struct vm_area_struct *node, *head, *new_head;
117
118 if (!vma->shared.vm_set.head) {
119 if (!vma->shared.vm_set.parent)
120 list_del_init(&vma->shared.vm_set.list);
121 else
122 raw_prio_tree_remove(root, &vma->shared.prio_tree_node);
123 } else {
124
125 BUG_ON(vma->shared.vm_set.head->shared.vm_set.head != vma);
126 if (vma->shared.vm_set.parent) {
127 head = vma->shared.vm_set.head;
128 if (!list_empty(&head->shared.vm_set.list)) {
129 new_head = list_entry(
130 head->shared.vm_set.list.next,
131 struct vm_area_struct,
132 shared.vm_set.list);
133 list_del_init(&head->shared.vm_set.list);
134 } else
135 new_head = NULL;
136
137 raw_prio_tree_replace(root, &vma->shared.prio_tree_node,
138 &head->shared.prio_tree_node);
139 head->shared.vm_set.head = new_head;
140 if (new_head)
141 new_head->shared.vm_set.head = head;
142
143 } else {
144 node = vma->shared.vm_set.head;
145 if (!list_empty(&vma->shared.vm_set.list)) {
146 new_head = list_entry(
147 vma->shared.vm_set.list.next,
148 struct vm_area_struct,
149 shared.vm_set.list);
150 list_del_init(&vma->shared.vm_set.list);
151 node->shared.vm_set.head = new_head;
152 new_head->shared.vm_set.head = node;
153 } else
154 node->shared.vm_set.head = NULL;
155 }
156 }
157}
158
159
160
161
162
163
164struct vm_area_struct *vma_prio_tree_next(struct vm_area_struct *vma,
165 struct prio_tree_iter *iter)
166{
167 struct prio_tree_node *ptr;
168 struct vm_area_struct *next;
169
170 if (!vma) {
171
172
173
174 ptr = prio_tree_next(iter);
175 if (ptr) {
176 next = prio_tree_entry(ptr, struct vm_area_struct,
177 shared.prio_tree_node);
178 prefetch(next->shared.vm_set.head);
179 return next;
180 } else
181 return NULL;
182 }
183
184 if (vma->shared.vm_set.parent) {
185 if (vma->shared.vm_set.head) {
186 next = vma->shared.vm_set.head;
187 prefetch(next->shared.vm_set.list.next);
188 return next;
189 }
190 } else {
191 next = list_entry(vma->shared.vm_set.list.next,
192 struct vm_area_struct, shared.vm_set.list);
193 if (!next->shared.vm_set.head) {
194 prefetch(next->shared.vm_set.list.next);
195 return next;
196 }
197 }
198
199 ptr = prio_tree_next(iter);
200 if (ptr) {
201 next = prio_tree_entry(ptr, struct vm_area_struct,
202 shared.prio_tree_node);
203 prefetch(next->shared.vm_set.head);
204 return next;
205 } else
206 return NULL;
207}
208