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