1#include "mem/tests/test_internal.h"
2
3TEST_GROUP_DECLARE(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 (void) 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_DECLARE_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_DECLARE_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 =
94 kmalloc(sizeof(*r) * (RMAP_CHILDREN + 1), ALLOC_FLAGS_ZERO);
95 TEST_ASSERT_NONNULL(r);
96
97 struct mm *pmm = mm_alloc();
98 TEST_ASSERT_NONNULL(pmm);
99 vaddr_t pbase = WIN_BASE_PG << PAGE_4K_SHIFT;
100 vaddr_t pend = (WIN_BASE_PG + WIN_SPAN_PG) << PAGE_4K_SHIFT;
101 struct vma_range *pvr = vma_range_alloc(mm: pmm, start: pbase, end: pend, RMAP_PROT);
102 TEST_ASSERT_NONNULL(pvr);
103 TEST_ASSERT_OK(vma_range_anon_prepare(pvr));
104 r[0] = (struct range_rec){pmm, pvr, WIN_BASE_PG, WIN_BASE_PG + WIN_SPAN_PG};
105
106 for (size_t i = 1; i <= RMAP_CHILDREN; i++) {
107 size_t off = prng_next() % (WIN_SPAN_PG - 1);
108 size_t len = 1 + (prng_next() % CHILD_MAX_PG);
109 if (off + len > WIN_SPAN_PG)
110 len = WIN_SPAN_PG - off;
111
112 size_t lo = WIN_BASE_PG + off;
113 size_t hi = lo + len;
114
115 struct mm *cmm = mm_alloc();
116 TEST_ASSERT_NONNULL(cmm);
117 struct vma_range *cvr = vma_range_alloc(mm: cmm, start: lo << PAGE_4K_SHIFT,
118 end: hi << PAGE_4K_SHIFT, RMAP_PROT);
119 TEST_ASSERT_NONNULL(cvr);
120 TEST_ASSERT_OK(anon_vma_fork(cvr, pvr));
121 r[i] = (struct range_rec){cmm, cvr, lo, hi};
122 }
123
124 /* one folio, faulted into parent's anon_vma, we move its index to
125 * probe different object offsets without re-faulting */
126 struct folio *f = folio_alloc(0);
127 TEST_ASSERT_NONNULL(f);
128 folio_add_anon_rmap_new(f, vm_area: pvr, va: pbase);
129
130 size_t queries = ctx->intensity_val ? ctx->intensity_val : RMAP_QUERIES;
131 for (size_t q = 0; q < queries; q++) {
132 size_t idx = WIN_BASE_PG + (prng_next() % WIN_SPAN_PG);
133 f->index = idx; /* order-0: walk probes exactly [idx, idx] */
134
135 struct visit_rec v = {0};
136 rmap_walk_anon(f, visit: record_visit, private: &v);
137
138 vaddr_t want_va = (vaddr_t) idx << PAGE_4K_SHIFT;
139 size_t expected = 0;
140 for (size_t j = 0; j <= RMAP_CHILDREN; j++) {
141 bool covers = idx >= r[j].lo_pg && idx < r[j].hi_pg;
142 if (covers)
143 expected++;
144
145 /* find this range's mm in visited set */
146 bool seen = false;
147 for (size_t k = 0; k < v.n; k++) {
148 if (v.mm[k] == r[j].mm) {
149 seen = true;
150 TEST_ASSERT_EQ(v.va[k], want_va);
151 break;
152 }
153 }
154 TEST_ASSERT_EQ(seen, covers);
155 }
156 /* no duplicates, no visits to ranges that don't cover idx */
157 TEST_ASSERT_EQ(v.n, expected);
158 }
159
160 kfree(r);
161 return TEST_SUCCESS;
162}
163