1#include <mem/anon_vma.h>
2#include <mem/avc.h>
3#include <mem/fixed_size_alloc.h>
4#include <mem/vma_range.h>
5#include <smp/perdomain.h>
6#include <structures/list.h>
7#include <types/refcount.h>
8
9FIXED_SIZE_RANGE_PERDOMAIN_DECLARE(anon_vma,
10 .obj_size = sizeof(struct anon_vma),
11 .obj_align = _Alignof(struct anon_vma));
12
13struct anon_vma *anon_vma_alloc() {
14 struct anon_vma *av = FSR_PERDOMAIN_ALLOC(anon_vma);
15 if (!av)
16 return NULL;
17
18 rbit_init(rbit: &av->tree);
19
20 /* Faults touch anon_vmas from every thread priority, so we gotta
21 * set the PI ceiling to URGENT... NOTE: if PI design narrows
22 * down who can fault, we can lower this. Best not to spam URGENTs */
23 rwlock_init(lock: &av->lock, ceiling: THREAD_PRIO_CLASS_URGENT);
24
25 /* New anon_vma is its own root and base of fork hierarchy */
26 av->root = av;
27 av->parent = NULL;
28
29 /* No AVC or folio references, first link bumps */
30 refcount_init(rc: &av->refcount, val: 0);
31 return av;
32}
33
34void anon_vma_free(struct anon_vma *f) {
35 return FSR_PERDOMAIN_FREE(anon_vma, f);
36}
37
38/* The big tree iteration
39 *
40 * Return in object/pgoff order every AVC whose VMA covers any page in the
41 * [first, last] interval
42 *
43 * Augmented interval tree search (classically from CLRS), every rbit_node
44 * carries `max`, letting us prune subtrees that cannot overlap
45 *
46 * NOTE: these don't take anon_vma's lock. it's the caller's job to hold
47 * the read lock across the entire first()..next()..NULL walk */
48static struct rbit_node *itree_subtree_search(struct rbit_node *node,
49 pgoff_t first, pgoff_t last) {
50 /* invariant: first <= node->max, so an overlap exists below */
51 while (true) {
52 if (node->left && first <= node->left->max) {
53 node = node->left; /* leftmost lives in the left subtree */
54 continue;
55 }
56
57 if (node->interval.low <= last) { /* node starts at/under the window */
58
59 if (first <= node->interval.high) /* ...ends at or over it -> hit */
60 return node;
61
62 if (node->right && first <= node->right->max) {
63 node = node->right;
64 continue;
65 }
66 }
67
68 return NULL;
69 }
70}
71
72struct anon_vma_chain *anon_vma_itree_first(struct anon_vma *av, pgoff_t first,
73 pgoff_t last) {
74 struct rbit_node *root = av->tree.root;
75 if (!root || root->max < first)
76 return NULL;
77
78 struct rbit_node *n = itree_subtree_search(node: root, first, last);
79 return n ? rbit_entry(n, struct anon_vma_chain, itnode) : NULL;
80}
81
82struct anon_vma_chain *anon_vma_itree_next(struct anon_vma_chain *avc,
83 pgoff_t first, pgoff_t last) {
84 struct rbit_node *node = &avc->itnode;
85 struct rbit_node *rb = node->right;
86 struct rbit_node *prev;
87
88 while (true) {
89 /* invariant: node->interval.low <= last; rb == node->right */
90
91 /* the next overlap in-order is either in the right subtree... */
92 if (rb && first <= rb->max) {
93 struct rbit_node *n = itree_subtree_search(node: rb, first, last);
94 return n ? rbit_entry(n, struct anon_vma_chain, itnode) : NULL;
95 }
96
97 /* ...or up the tree at the first ancestor we reach from its left */
98 do {
99 prev = node;
100 node = node->parent;
101
102 if (!node)
103 return NULL;
104
105 rb = node->right;
106 } while (prev == rb);
107
108 /* lows are sorted, so once an ancestor starts past
109 * `last`, so does everything after it */
110
111 /* the walk is finished */
112 if (last < node->interval.low)
113 return NULL;
114
115 if (first <= node->interval.high)
116 return rbit_entry(node, struct anon_vma_chain, itnode);
117
118 /* else: ancestor's interval misses, fall through and probe its right */
119 }
120}
121
122/* Here, we attach `dst` to every anon_vma that `src` is linked to,
123 * so that a child VMA's rmap can find pages that were faulted before the fork
124 *
125 * One fresh AVC per source link, each holds a reference on the
126 * anon_vma it points at */
127enum errno anon_vma_clone(struct vma_range *dst, struct vma_range *src) {
128 struct anon_vma_chain *src_avc;
129 list_for_each_entry(src_avc, &src->anon_vma_chain, same_vma_range) {
130 struct anon_vma *av = src_avc->anon_vma;
131
132 struct anon_vma_chain *avc = avc_alloc();
133 if (!avc)
134 goto enomem;
135
136 refcount_inc(rc: &av->refcount); /* dst's new AVC pins this */
137 avc_link(vma_range: dst, av, avc);
138 }
139 return ERR_OK;
140
141enomem:
142
143 /* undo the partial chain so `dst` is left as we found it */
144 vma_range_unlink_anon_vmas(vma_range: dst);
145 return ERR_NO_MEM;
146}
147
148enum errno anon_vma_fork(struct vma_range *child, struct vma_range *parent) {
149 /* inherit parent's anon_vmas so already mapped (about
150 * to be COW) pages stay reachable from the child */
151 enum errno err = anon_vma_clone(dst: child, src: parent);
152 if (err != ERR_OK)
153 return err;
154
155 /* no anon stuff in parent, child is unaffected, stays lazy */
156 struct anon_vma *pav = parent->anon_vma;
157 if (!pav)
158 return ERR_OK;
159
160 /* give child its own anon_vma, where future COWed pages will live,
161 * sharing the root lock, hanging off parent in fork hierarchy */
162 struct anon_vma *av = anon_vma_alloc();
163 if (!av)
164 goto enomem;
165
166 struct anon_vma_chain *avc = avc_alloc();
167 if (!avc) {
168 anon_vma_free(f: av); /* never linked, refcount 0 */
169 goto enomem;
170 }
171
172 av->parent = pav;
173 av->root = pav->root;
174 refcount_inc(rc: &av->root->refcount); /* pin root: the lock lives there */
175
176 child->anon_vma = av;
177 refcount_inc(rc: &av->refcount); /* AVC we're about to link */
178 avc_link(vma_range: child, av, avc);
179 return ERR_OK;
180
181enomem:
182 vma_range_unlink_anon_vmas(vma_range: child);
183 return ERR_NO_MEM;
184}
185
186/* Drop every AVC on `vma_range`, releasing all the anon_vma references
187 *
188 * The VMA is anonymous-clean, any anon_vma whose last link/folio went
189 * away is freed (going up to the pinned root eventually) */
190void vma_range_unlink_anon_vmas(struct vma_range *vma_range) {
191 struct anon_vma_chain *avc, *next;
192
193 list_for_each_entry_safe(avc, next, &vma_range->anon_vma_chain,
194 same_vma_range) {
195 struct anon_vma *av = avc->anon_vma;
196 avc_unlink(avc);
197 avc_free(avc);
198 anon_vm_area_put(av);
199 }
200
201 vma_range->anon_vma = NULL;
202}
203