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