1#ifdef TEST_MM
2
3#include <crypto/prng.h>
4#include <math/align.h>
5#include <mem/alloc.h>
6#include <mem/mm.h>
7#include <mem/page.h>
8#include <mem/vma_range.h>
9#include <stdint.h>
10#include <structures/rbit.h>
11#include <test.h>
12
13#define MM_TEST_VMAS 100
14#define MM_TEST_QUERIES 3000
15#define MM_TEST_SEED 0x5EED1234ULL
16
17#define MM_WIN_LOW 0x0000000000100000UL /* 1 MiB */
18#define MM_WIN_HIGH 0x0000000040000000UL /* 1 GiB */
19
20static vaddr_t brute_gap(struct mm *mm, size_t len, size_t align, vaddr_t low,
21 vaddr_t high) {
22 if (len == 0 || high <= low || high - low < len)
23 return 0;
24
25 vaddr_t floor = low;
26 struct rbit_node *n;
27 rbit_for_each(n, &mm->vma_range_tree) {
28 struct vma_range *v = rbit_entry(n, struct vma_range, mm_node);
29 if (vma_range_end(vma_range: v) <= low)
30 continue;
31 if (vma_range_start(vma_range: v) >= high)
32 break;
33 if (vma_range_start(vma_range: v) > floor) {
34 vaddr_t a = ALIGN_UP(floor, align);
35 if (a >= floor && a + len <= vma_range_start(vma_range: v) && a + len <= high)
36 return a;
37 }
38 if (vma_range_end(vma_range: v) > floor)
39 floor = vma_range_end(vma_range: v);
40 }
41 vaddr_t a = ALIGN_UP(floor, align);
42 if (a >= floor && a + len <= high)
43 return a;
44 return 0;
45}
46
47static size_t bf_max_high(struct rbit_node *n) {
48 if (!n)
49 return 0;
50 size_t m = n->interval.high;
51 size_t l = bf_max_high(n: n->left), r = bf_max_high(n: n->right);
52 if (l > m)
53 m = l;
54 if (r > m)
55 m = r;
56 return m;
57}
58
59static size_t bf_min_low(struct rbit_node *n) {
60 if (!n)
61 return SIZE_MAX;
62 size_t m = n->interval.low;
63 size_t l = bf_min_low(n: n->left), r = bf_min_low(n: n->right);
64 if (l < m)
65 m = l;
66 if (r < m)
67 m = r;
68 return m;
69}
70
71static size_t collect_inorder(struct rbit_node *n, struct rbit_node **out,
72 size_t idx) {
73 if (!n)
74 return idx;
75 idx = collect_inorder(n: n->left, out, idx);
76 out[idx++] = n;
77 return collect_inorder(n: n->right, out, idx);
78}
79
80static size_t bf_max_gap(struct rbit_node *root) {
81 static struct rbit_node *buf[MM_TEST_VMAS * 2 + 16];
82 size_t cnt = collect_inorder(n: root, out: buf, idx: 0);
83 size_t g = 0;
84 for (size_t i = 1; i < cnt; i++) {
85 size_t prev_end = buf[i - 1]->interval.high + 1;
86 size_t cur_low = buf[i]->interval.low;
87 if (cur_low > prev_end && cur_low - prev_end > g)
88 g = cur_low - prev_end;
89 }
90 return g;
91}
92
93static bool augment_ok(struct mm *mm) {
94 struct rbit_node *n;
95 rbit_for_each(n, &mm->vma_range_tree) {
96 struct vma_range *v = rbit_entry(n, struct vma_range, mm_node);
97 if (n->max != bf_max_high(n))
98 return false;
99 if (v->min_low != bf_min_low(n))
100 return false;
101 if (v->max_gap != bf_max_gap(root: n))
102 return false;
103 }
104 return true;
105}
106
107/* In-order VMAs are sorted by start and never overlap. */
108static bool tree_consistent(struct mm *mm) {
109 vaddr_t prev_end = 0;
110 struct rbit_node *n;
111 rbit_for_each(n, &mm->vma_range_tree) {
112 struct vma_range *v = rbit_entry(n, struct vma_range, mm_node);
113 if (vma_range_start(vma_range: v) < prev_end)
114 return false;
115 if (vma_range_end(vma_range: v) <= vma_range_start(vma_range: v))
116 return false;
117 prev_end = vma_range_end(vma_range: v);
118 }
119 return true;
120}
121
122static size_t build_random_vma_ranges(struct mm *mm) {
123 vaddr_t cursor = MM_WIN_LOW;
124 size_t placed = 0;
125 for (size_t i = 0; i < MM_TEST_VMAS; i++) {
126 vaddr_t gap = (1 + (prng_next() % 64)) * PAGE_SIZE;
127 vaddr_t len = (1 + (prng_next() % 32)) * PAGE_SIZE;
128 vaddr_t start = cursor + gap;
129 vaddr_t end = start + len;
130 if (end >= MM_WIN_HIGH)
131 break;
132 struct vma_range *v = vma_range_alloc(mm, start, end, prot: VMA_PROT_READ);
133 if (!v)
134 break;
135 mm_vma_range_insert(mm, vma_range: v);
136 cursor = end;
137 placed++;
138 }
139 return placed;
140}
141
142TEST_DECLARE(mm_gap_differential, .tier = TEST_TIER_UNIT) {
143 prng_seed(MM_TEST_SEED);
144 struct mm *mm = mm_alloc();
145 TEST_ASSERT(mm);
146
147 size_t placed = build_random_vma_ranges(mm);
148 TEST_ASSERT(placed > 0);
149 TEST_ASSERT(tree_consistent(mm));
150 TEST_ASSERT(augment_ok(mm));
151
152 for (size_t q = 0; q < MM_TEST_QUERIES; q++) {
153 size_t len = (1 + (prng_next() % 40)) * PAGE_SIZE;
154 size_t align = PAGE_SIZE << (prng_next() % 4);
155
156 vaddr_t low = MM_WIN_LOW;
157 vaddr_t high = MM_WIN_HIGH;
158 if (prng_next() & 1) {
159 low += (prng_next() % 0x4000) * PAGE_SIZE;
160 high -= (prng_next() % 0x4000) * PAGE_SIZE;
161 }
162
163 vaddr_t got = mm_vma_range_find_gap(mm, len, align, low, high);
164 vaddr_t want = brute_gap(mm, len, align, low, high);
165 TEST_ASSERT(got == want);
166
167 if (got) {
168 TEST_ASSERT(IS_ALIGNED(got, align));
169 TEST_ASSERT(got >= low && got + len <= high);
170 TEST_ASSERT(!mm_vma_range_find_intersection(mm, got, got + len));
171 }
172 }
173
174 return TEST_SUCCESS;
175}
176
177TEST_DECLARE(mm_map_consistency, .tier = TEST_TIER_UNIT) {
178 prng_seed(MM_TEST_SEED + 1);
179 struct mm *mm = mm_alloc();
180 TEST_ASSERT(mm);
181
182 for (size_t i = 0; i < 128; i++) {
183 size_t len = (1 + (prng_next() % 64)) * PAGE_SIZE;
184 vaddr_t a =
185 mm_map(mm, hint: 0, len, prot: VMA_PROT_READ | VMA_PROT_WRITE, flags: MM_MAP_ANON);
186 TEST_ASSERT(a != 0);
187 TEST_ASSERT(IS_PAGE_ALIGNED(a));
188 TEST_ASSERT(a >= 0x10000UL);
189 struct vma_range *v = vma_range_find(mm, addr: a);
190 TEST_ASSERT(v && vma_range_start(v) == a);
191 }
192
193 TEST_ASSERT(tree_consistent(mm));
194 TEST_ASSERT(augment_ok(mm));
195
196 return TEST_SUCCESS;
197}
198
199TEST_DECLARE(mm_vma_range_split, .tier = TEST_TIER_UNIT) {
200 struct mm *mm = mm_alloc();
201 TEST_ASSERT(mm);
202
203 vaddr_t base = MM_WIN_LOW;
204 vaddr_t end = base + 16 * PAGE_SIZE;
205 struct vma_range *orig = vma_range_alloc(mm, start: base, end, prot: VMA_PROT_READ);
206 TEST_ASSERT(orig);
207 mm_vma_range_insert(mm, vma_range: orig);
208
209 vaddr_t mid = base + 6 * PAGE_SIZE;
210 struct vma_range *hi = vma_range_split(vma_range: orig, addr: mid);
211 TEST_ASSERT(hi);
212
213 /* Boundaries: low half kept in orig, high half returned. */
214 TEST_ASSERT(vma_range_start(orig) == base && vma_range_end(orig) == mid);
215 TEST_ASSERT(vma_range_start(hi) == mid && vma_range_end(hi) == end);
216 /* pgoff of the high half follows from the original's. */
217 TEST_ASSERT(hi->pgoff == orig->pgoff + ((mid - base) >> PAGE_4K_SHIFT));
218
219 /* Lookups land in the right half. */
220 TEST_ASSERT(vma_range_find(mm, base) == orig);
221 TEST_ASSERT(vma_range_find(mm, mid - 1) == orig);
222 TEST_ASSERT(vma_range_find(mm, mid) == hi);
223 TEST_ASSERT(vma_range_find(mm, end - 1) == hi);
224 TEST_ASSERT(vma_range_find(mm, end) == NULL);
225
226 /* Navigation links the two halves. */
227 TEST_ASSERT(vma_range_next(orig) == hi);
228 TEST_ASSERT(vma_range_prev(hi) == orig);
229 TEST_ASSERT(vma_range_prev(orig) == NULL);
230 TEST_ASSERT(vma_range_next(hi) == NULL);
231
232 TEST_ASSERT(tree_consistent(mm));
233 TEST_ASSERT(augment_ok(mm));
234
235 /* Bad splits are rejected without disturbing the tree. */
236 TEST_ASSERT(vma_range_split(orig, base) == NULL); /* at start */
237 TEST_ASSERT(vma_range_split(orig, mid) == NULL); /* at end */
238 TEST_ASSERT(vma_range_split(orig, base + 1) == NULL); /* unaligned */
239 TEST_ASSERT(tree_consistent(mm));
240
241 return TEST_SUCCESS;
242}
243
244#endif
245