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