1#include "mem/tests/test_internal.h"
2
3TEST_GROUP_DEFINE(rmap, .intensity_desc = {
4 .curve = SCALE_PIECEWISE_LOG,
5 .unit = "queries",
6 });
7
8/* rmap goes folio -> every (mm, va) mapping */
9
10#define RMAP_SEED 0x9A7C0FF1ULL
11#define RMAP_CHILDREN 40
12#define RMAP_QUERIES 2000
13
14#define RMAP_PROT (VMA_PROT_READ | VMA_PROT_WRITE)
15
16/* parent reservation, in pages: children carve sub-ranges from it */
17#define WIN_BASE_PG 0x40000UL /* 1 GiB >> 12 */
18#define WIN_SPAN_PG 0x1000UL /* 4096 pages */
19#define CHILD_MAX_PG 64
20
21struct range_rec {
22 struct mm *mm;
23 struct vma_range *vr;
24 size_t lo_pg; /* first covered page index (== vr->pgoff) */
25 size_t hi_pg; /* one past last */
26};
27
28struct visit_rec {
29 struct mm *mm[RMAP_CHILDREN + 1];
30 vaddr_t va[RMAP_CHILDREN + 1];
31 size_t n;
32};
33
34static void record_visit(struct mm *mm, vaddr_t va, struct folio *f,
35 void *priv) {
36 cc_ignore(f);
37 struct visit_rec *v = priv;
38 v->mm[v->n] = mm;
39 v->va[v->n] = va;
40 v->n++;
41}
42
43TEST_DEFINE_UNIT(rmap, fork_visibility) {
44 vaddr_t base = WIN_BASE_PG << PAGE_4K_SHIFT;
45 vaddr_t end = base + 16 * PAGE_SIZE;
46 vaddr_t va = base + 4 * PAGE_SIZE; /* page we fault */
47
48 struct mm *pmm = mm_alloc();
49 struct mm *cmm = mm_alloc();
50 TEST_ASSERT(pmm && cmm);
51
52 struct vma_range *pvr = vma_range_alloc(mm: pmm, start: base, end, RMAP_PROT);
53 TEST_ASSERT_NONNULL(pvr);
54 TEST_ASSERT_OK(vma_range_anon_prepare(pvr));
55
56 /* same geometry in the child then fork, the child's cloned AVC should
57 * be in parent's anon_vma, keyed by pgoff */
58 struct vma_range *cvr = vma_range_alloc(mm: cmm, start: base, end, RMAP_PROT);
59 TEST_ASSERT_NONNULL(cvr);
60 TEST_ASSERT_OK(anon_vma_fork(cvr, pvr));
61
62 /* a page faulted into the parent BEFORE fork is reachable from BOTH */
63 struct folio *shared = folio_alloc(0);
64 TEST_ASSERT_NONNULL(shared);
65 folio_add_anon_rmap_new(f: shared, vm_area: pvr, va);
66
67 struct visit_rec v = {0};
68 rmap_walk_anon(f: shared, visit: record_visit, private: &v);
69 TEST_ASSERT_EQ(v.n, 2);
70 bool saw_p = false, saw_c = false;
71 for (size_t i = 0; i < v.n; i++) {
72 TEST_ASSERT_EQ(v.va[i], va);
73 saw_p |= (v.mm[i] == pmm);
74 saw_c |= (v.mm[i] == cmm);
75 }
76 TEST_ASSERT(saw_p && saw_c);
77
78 struct folio *priv = folio_alloc(0);
79 TEST_ASSERT_NONNULL(priv);
80 folio_add_anon_rmap_new(f: priv, vm_area: cvr, va);
81
82 struct visit_rec v2 = {0};
83 rmap_walk_anon(f: priv, visit: record_visit, private: &v2);
84 TEST_ASSERT_EQ(v2.n, 1);
85 TEST_ASSERT(v2.mm[0] == cmm && v2.va[0] == va);
86
87 return TEST_SUCCESS;
88}
89
90TEST_DEFINE_UNIT(rmap, itree_differential, TEST_INTENSITY(200, 2000, 10000)) {
91 prng_seed(seed: ctx->seed ? ctx->seed : RMAP_SEED);
92
93 struct range_rec *r = vnews(r, (RMAP_CHILDREN + 1), ALLOC_ZERO);
94 TEST_ASSERT_NONNULL(r);
95
96 struct mm *pmm = mm_alloc();
97 TEST_ASSERT_NONNULL(pmm);
98 vaddr_t pbase = WIN_BASE_PG << PAGE_4K_SHIFT;
99 vaddr_t pend = (WIN_BASE_PG + WIN_SPAN_PG) << PAGE_4K_SHIFT;
100 struct vma_range *pvr = vma_range_alloc(mm: pmm, start: pbase, end: pend, RMAP_PROT);
101 TEST_ASSERT_NONNULL(pvr);
102 TEST_ASSERT_OK(vma_range_anon_prepare(pvr));
103 r[0] = (struct range_rec){pmm, pvr, WIN_BASE_PG, WIN_BASE_PG + WIN_SPAN_PG};
104
105 for (size_t i = 1; i <= RMAP_CHILDREN; i++) {
106 size_t off = prng_next() % (WIN_SPAN_PG - 1);
107 size_t len = 1 + (prng_next() % CHILD_MAX_PG);
108 if (off + len > WIN_SPAN_PG)
109 len = WIN_SPAN_PG - off;
110
111 size_t lo = WIN_BASE_PG + off;
112 size_t hi = lo + len;
113
114 struct mm *cmm = mm_alloc();
115 TEST_ASSERT_NONNULL(cmm);
116 struct vma_range *cvr = vma_range_alloc(mm: cmm, start: lo << PAGE_4K_SHIFT,
117 end: hi << PAGE_4K_SHIFT, RMAP_PROT);
118 TEST_ASSERT_NONNULL(cvr);
119 TEST_ASSERT_OK(anon_vma_fork(cvr, pvr));
120 r[i] = (struct range_rec){cmm, cvr, lo, hi};
121 }
122
123 /* one folio, faulted into parent's anon_vma, we move its index to
124 * probe different object offsets without re-faulting */
125 struct folio *f = folio_alloc(0);
126 TEST_ASSERT_NONNULL(f);
127 folio_add_anon_rmap_new(f, vm_area: pvr, va: pbase);
128
129 size_t queries = ctx->intensity_val ? ctx->intensity_val : RMAP_QUERIES;
130 for (size_t q = 0; q < queries; q++) {
131 size_t idx = WIN_BASE_PG + (prng_next() % WIN_SPAN_PG);
132 f->index = idx; /* order-0: walk probes exactly [idx, idx] */
133
134 struct visit_rec v = {0};
135 rmap_walk_anon(f, visit: record_visit, private: &v);
136
137 vaddr_t want_va = (vaddr_t) idx << PAGE_4K_SHIFT;
138 size_t expected = 0;
139 for (size_t j = 0; j <= RMAP_CHILDREN; j++) {
140 bool covers = idx >= r[j].lo_pg && idx < r[j].hi_pg;
141 if (covers)
142 expected++;
143
144 /* find this range's mm in visited set */
145 bool seen = false;
146 for (size_t k = 0; k < v.n; k++) {
147 if (v.mm[k] == r[j].mm) {
148 seen = true;
149 TEST_ASSERT_EQ(v.va[k], want_va);
150 break;
151 }
152 }
153 TEST_ASSERT_EQ(seen, covers);
154 }
155 /* no duplicates, no visits to ranges that don't cover idx */
156 TEST_ASSERT_EQ(v.n, expected);
157 }
158
159 vfree(r);
160 return TEST_SUCCESS;
161}
162