1#ifdef TEST_RMAP
2
3#include <crypto/prng.h>
4#include <errno.h>
5#include <mem/alloc.h>
6#include <mem/anon_vma.h>
7#include <mem/folio.h>
8#include <mem/mm.h>
9#include <mem/rmap.h>
10#include <mem/vma_range.h>
11#include <stdint.h>
12#include <test.h>
13
14/* rmap is the dangerous direction: folio -> every (mm, va) that maps it
15 *
16 * A miss here means a swapped/COWed/unmapped page leaves a live PTE behind
17 *
18 * The walk rides anon_vma_itree_first/next, so it has a differential test:
19 * cross-check the visited set against a trivially-correct O(n) cover scan */
20
21#define RMAP_SEED 0x9A7C0FF1ULL
22#define RMAP_CHILDREN 40
23#define RMAP_QUERIES 2000
24
25#define RMAP_PROT (VMA_PROT_READ | VMA_PROT_WRITE)
26
27/* parent reservation, in pages: children carve random sub-ranges out of it */
28#define WIN_BASE_PG 0x40000UL /* 1 GiB >> 12 */
29#define WIN_SPAN_PG 0x1000UL /* 4096 pages */
30#define CHILD_MAX_PG 64
31
32struct range_rec {
33 struct mm *mm;
34 struct vma_range *vr;
35 size_t lo_pg; /* first covered page index (== vr->pgoff) */
36 size_t hi_pg; /* one past last */
37};
38
39struct visit_rec {
40 struct mm *mm[RMAP_CHILDREN + 1];
41 vaddr_t va[RMAP_CHILDREN + 1];
42 size_t n;
43};
44
45static void record_visit(struct mm *mm, vaddr_t va, struct folio *f,
46 void *priv) {
47 (void) f;
48 struct visit_rec *v = priv;
49 v->mm[v->n] = mm;
50 v->va[v->n] = va;
51 v->n++;
52}
53
54TEST_DECLARE(rmap_fork_visibility, .tier = TEST_TIER_UNIT) {
55 vaddr_t base = WIN_BASE_PG << PAGE_4K_SHIFT;
56 vaddr_t end = base + 16 * PAGE_SIZE;
57 vaddr_t va = base + 4 * PAGE_SIZE; /* the page we fault */
58
59 struct mm *pmm = mm_alloc();
60 struct mm *cmm = mm_alloc();
61 TEST_ASSERT(pmm && cmm);
62
63 struct vma_range *pvr = vma_range_alloc(mm: pmm, start: base, end, RMAP_PROT);
64 TEST_ASSERT(pvr);
65 TEST_ASSERT(vma_range_anon_prepare(pvr) == ERR_OK);
66
67 /* same geometry in the child (stands in for vma_range_dup) then fork: the
68 * child's cloned AVC lands in the parent's anon_vma keyed by its pgoff */
69 struct vma_range *cvr = vma_range_alloc(mm: cmm, start: base, end, RMAP_PROT);
70 TEST_ASSERT(cvr);
71 TEST_ASSERT(anon_vma_fork(cvr, pvr) == ERR_OK);
72
73 /* a page faulted into the parent BEFORE fork is reachable from BOTH */
74 struct folio *shared = folio_alloc(0);
75 TEST_ASSERT(shared);
76 folio_add_anon_rmap_new(f: shared, vm_area: pvr, va);
77
78 struct visit_rec v = {0};
79 rmap_walk_anon(f: shared, visit: record_visit, private: &v);
80 TEST_ASSERT(v.n == 2);
81 bool saw_p = false, saw_c = false;
82 for (size_t i = 0; i < v.n; i++) {
83 TEST_ASSERT(v.va[i] == va);
84 saw_p |= (v.mm[i] == pmm);
85 saw_c |= (v.mm[i] == cmm);
86 }
87 TEST_ASSERT(saw_p && saw_c);
88
89 struct folio *priv = folio_alloc(0);
90 TEST_ASSERT(priv);
91 folio_add_anon_rmap_new(f: priv, vm_area: cvr, va);
92
93 struct visit_rec v2 = {0};
94 rmap_walk_anon(f: priv, visit: record_visit, private: &v2);
95 TEST_ASSERT(v2.n == 1);
96 TEST_ASSERT(v2.mm[0] == cmm && v2.va[0] == va);
97
98 return TEST_SUCCESS;
99}
100
101TEST_DECLARE(rmap_itree_differential, .tier = TEST_TIER_UNIT) {
102 prng_seed(RMAP_SEED);
103
104 struct range_rec *r =
105 kmalloc(sizeof(*r) * (RMAP_CHILDREN + 1), ALLOC_FLAGS_ZERO);
106 TEST_ASSERT(r);
107
108 struct mm *pmm = mm_alloc();
109 TEST_ASSERT(pmm);
110 vaddr_t pbase = WIN_BASE_PG << PAGE_4K_SHIFT;
111 vaddr_t pend = (WIN_BASE_PG + WIN_SPAN_PG) << PAGE_4K_SHIFT;
112 struct vma_range *pvr = vma_range_alloc(mm: pmm, start: pbase, end: pend, RMAP_PROT);
113 TEST_ASSERT(pvr);
114 TEST_ASSERT(vma_range_anon_prepare(pvr) == ERR_OK);
115 r[0] = (struct range_rec){pmm, pvr, WIN_BASE_PG, WIN_BASE_PG + WIN_SPAN_PG};
116
117 for (size_t i = 1; i <= RMAP_CHILDREN; i++) {
118 size_t off = prng_next() % (WIN_SPAN_PG - 1);
119 size_t len = 1 + (prng_next() % CHILD_MAX_PG);
120 if (off + len > WIN_SPAN_PG)
121 len = WIN_SPAN_PG - off;
122
123 size_t lo = WIN_BASE_PG + off;
124 size_t hi = lo + len;
125
126 struct mm *cmm = mm_alloc();
127 TEST_ASSERT(cmm);
128 struct vma_range *cvr = vma_range_alloc(mm: cmm, start: lo << PAGE_4K_SHIFT,
129 end: hi << PAGE_4K_SHIFT, RMAP_PROT);
130 TEST_ASSERT(cvr);
131 TEST_ASSERT(anon_vma_fork(cvr, pvr) == ERR_OK);
132 r[i] = (struct range_rec){cmm, cvr, lo, hi};
133 }
134
135 /* one folio, faulted into the parent's anon_vma; we move its index around
136 * to probe different object offsets without re-faulting */
137
138 struct folio *f = folio_alloc(0);
139 TEST_ASSERT(f);
140 folio_add_anon_rmap_new(f, vm_area: pvr, va: pbase);
141
142 for (size_t q = 0; q < RMAP_QUERIES; q++) {
143 size_t idx = WIN_BASE_PG + (prng_next() % WIN_SPAN_PG);
144 f->index = idx; /* order-0: walk probes exactly [idx, idx] */
145
146 struct visit_rec v = {0};
147 rmap_walk_anon(f, visit: record_visit, private: &v);
148
149 vaddr_t want_va = (vaddr_t) idx << PAGE_4K_SHIFT;
150 size_t expected = 0;
151 for (size_t j = 0; j <= RMAP_CHILDREN; j++) {
152 bool covers = idx >= r[j].lo_pg && idx < r[j].hi_pg;
153 if (covers)
154 expected++;
155
156 /* find this range's mm in the visited set */
157 bool seen = false;
158 for (size_t k = 0; k < v.n; k++) {
159 if (v.mm[k] == r[j].mm) {
160 seen = true;
161 TEST_ASSERT(v.va[k] == want_va);
162 break;
163 }
164 }
165 TEST_ASSERT(seen == covers);
166 }
167 /* exact: no duplicates, no visits to ranges that don't cover idx */
168 TEST_ASSERT(v.n == expected);
169 }
170
171 return TEST_SUCCESS;
172}
173
174#endif
175