1 /*
2 * Copyright (c) 2024 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28
29 #include <darwintest.h>
30 #include <darwintest_utils.h>
31 #include <stdio.h>
32 #include <assert.h>
33 #include <setjmp.h>
34 #include <stdlib.h>
35 #include <sys/queue.h>
36 #include <os/overflow.h>
37
38 #pragma clang attribute push(__attribute__((noinline, optnone)), apply_to=function)
39
40 #include "../osfmk/kern/bits.h"
41
42 T_GLOBAL_META(
43 T_META_NAMESPACE("xnu.vm.mteinfo"),
44 T_META_RADAR_COMPONENT_NAME("xnu"),
45 T_META_RADAR_COMPONENT_VERSION("VM"),
46 T_META_RUN_CONCURRENTLY(true),
47 T_META_TAG_VM_PREFERRED);
48
49 #define DEVELOPMENT 0
50 #define DEBUG 0
51 #define XNU_KERNEL_PRIVATE 1
52 #define HAS_MTE 1
53 #define VM_MTE_FF_VERIFY 1
54 #define VM_PAGE_PACKED_ALIGNED
55 #define VMP_FREE_BATCH_SIZE 64
56
57 /* Fake out some common XNU macros and defines. */
58 #define SECURITY_READ_ONLY_LATE(type) __used type
59 #define __startup_func
60 #define MTE_PAGES_PER_TAG_PAGE 32
61 #define MAX_COLORS 128
62
63 TAILQ_HEAD(vm_page_queue_head, vm_page);
64 typedef struct vm_page_queue_head vm_page_queue_head_t;
65 typedef struct vm_page_queue_head *vm_page_queue_t;
66 typedef struct vm_page_queue_free_head {
67 vm_page_queue_head_t qhead;
68 } *vm_page_queue_free_head_t;
69
70 typedef struct vm_page_free_queue {
71 struct vm_page_queue_free_head vmpfq_queues[MAX_COLORS];
72 uint32_t vmpfq_count;
73 } *vm_page_free_queue_t;
74
75 #define TUNABLE(t, var, name, value) t var = value
76
77 typedef struct vm_page {
78 TAILQ_ENTRY(vm_page) vmp_pageq;
79 uint16_t vmp_mtefq_sel;
80 uint16_t vmp_using_mte;
81 ppnum_t ppnum;
82 } *vm_page_t;
83
84 #define vm_page_queue_init(q) TAILQ_INIT(q)
85 #define vm_page_queue_empty(q) TAILQ_EMPTY(q)
86 #define vm_page_queue_remove(q, e, link) TAILQ_REMOVE(q, e, link)
87 #define vm_page_queue_remove_first(q, e, link) ({ (e) = TAILQ_FIRST(q); TAILQ_REMOVE(q, e, link); })
88 #define vm_page_queue_enter(q, e, link) TAILQ_INSERT_TAIL(q, e, link)
89 #define vm_page_queue_enter_first(q, e, link) TAILQ_INSERT_HEAD(q, e, link)
90
91 #define release_assert(...) assert(__VA_ARGS__)
92
93 #define VM_PAGE_NULL ((vm_page_t)0)
94 #define VM_PAGE_GET_PHYS_PAGE(page) \
95 (page)->ppnum
96
97 #define VM_COUNTER_SUB(counter, value) ({ \
98 __auto_type __counter = (counter); \
99 T_QUIET; T_ASSERT_FALSE(os_sub_overflow(*__counter, value, __counter), \
100 "no overflow"); \
101 *__counter; \
102 })
103
104 #define VM_COUNTER_ADD(counter, value) ({ \
105 __auto_type __counter = (counter); \
106 T_QUIET; T_ASSERT_FALSE(os_add_overflow(*__counter, value, __counter), \
107 "no overflow"); \
108 *__counter; \
109 })
110
111 #define VM_COUNTER_DEC(counter) VM_COUNTER_SUB(counter, 1)
112 #define VM_COUNTER_INC(counter) VM_COUNTER_ADD(counter, 1)
113
114 #define ptoa(x) ((unsigned long long)(x) << 14)
115 #define atop(x) ((unsigned long long)(x) >> 14)
116
117 static void
__queue_element_linkage_invalid(void * e)118 __queue_element_linkage_invalid(void *e)
119 {
120 T_ASSERT_FAIL("Invalid queue linkage at %p", e);
121 }
122
123 /*
124 * MTE and VM globals taken over by the test. A few values are chosen
125 * deliberately, but most are arbitrary.
126 */
127
128 /* A stand-in for gDramBase. Make it non-zero to be nontrivial. */
129 static const ppnum_t pmap_first_pnum = 42 * MAX_COLORS;
130
131 /*
132 * Fake the vm pages array
133 *
134 * For the sake of the test we pretend everything is in the array,
135 * in the real kernel the data structure needs lookups for the
136 * [pmap_first_pnum, vm_pages_first_pnum) range.
137 *
138 * It doesn't affect testing materially though.
139 */
140 static const uint32_t vm_pages_count = 8 * 1024;
141 static struct vm_page vm_pages[vm_pages_count];
142 static const vm_page_t vm_pages_end = vm_pages + vm_pages_count;
143 static const uint32_t vm_color_mask = 63;
144
145 static const uint32_t mte_tag_storage_count = vm_pages_count / MTE_PAGES_PER_TAG_PAGE;
146 static const uint32_t mte_tag_storage_start_pnum = pmap_first_pnum + vm_pages_count - mte_tag_storage_count;
147 static const uint64_t mte_tag_storage_start = ptoa(mte_tag_storage_start_pnum);
148 static const uint64_t mte_tag_storage_end = ptoa(pmap_first_pnum + vm_pages_count);
149 static const vm_page_t vm_pages_tag_storage = vm_pages_end - mte_tag_storage_count;
150
151 /* This tag storage page will always be disabled due to an ECC error. */
152 static const ppnum_t mte_tag_storage_ecc_disabled = atop(mte_tag_storage_start) + 200;
153
154 static uint32_t vm_page_free_count;
155
156 static bool
pmap_in_tag_storage_range(ppnum_t pnum)157 pmap_in_tag_storage_range(ppnum_t pnum)
158 {
159 uint64_t addr = ptoa(pnum);
160
161 return (mte_tag_storage_start <= addr) && (addr < mte_tag_storage_end);
162 }
163
164 static void *
pmap_steal_memory(vm_size_t size,vm_size_t align)165 pmap_steal_memory(vm_size_t size, vm_size_t align)
166 {
167 void *ptr = NULL;
168
169 if (posix_memalign(&ptr, align, size) == 0) {
170 return ptr;
171 }
172
173 return NULL;
174 }
175
176
177 __pure2
178 static inline vm_page_t
vm_pages_tag_storage_array_internal(void)179 vm_pages_tag_storage_array_internal(void)
180 {
181 return vm_pages_tag_storage;
182 }
183
184 __pure2
185 static inline vm_page_t
vm_tag_storage_page_get(uint32_t i)186 vm_tag_storage_page_get(uint32_t i)
187 {
188 return &vm_pages_tag_storage[i];
189 }
190
191 static inline struct vm_page *
vm_page_find_canonical(ppnum_t pnum)192 vm_page_find_canonical(ppnum_t pnum)
193 {
194 return &vm_pages[pnum - pmap_first_pnum];
195 }
196
197 /*
198 * Now that the necessary gunk is in place to pretend we are the kernel...
199 * directly include the kernel mteinfo files.
200 */
201 #include "../osfmk/vm/vm_mteinfo_internal.h"
202 #include "../osfmk/vm/vm_mteinfo.c"
203
204 static char const *const cell_states[] = {
205 [MTE_STATE_DISABLED] = "disabled",
206 [MTE_STATE_PINNED] = "pinned",
207 [MTE_STATE_DEACTIVATING] = "deactivating",
208 [MTE_STATE_CLAIMED] = "claimed",
209 [MTE_STATE_INACTIVE] = "inactive",
210 [MTE_STATE_RECLAIMING] = "reclaiming",
211 [MTE_STATE_ACTIVATING] = "activating",
212 [MTE_STATE_ACTIVE] = "active",
213 };
214
215 static bool
cell_queue_empty(mte_cell_queue_t queue)216 cell_queue_empty(mte_cell_queue_t queue)
217 {
218 return cell_idx_is_queue(queue->head.next);
219 }
220
221 static mte_cell_state_t
cell_state_from_list_idx(mte_cell_list_idx_t idx)222 cell_state_from_list_idx(mte_cell_list_idx_t idx)
223 {
224 if (idx < MTE_LIST_ACTIVE_0_IDX) {
225 return (mte_cell_state_t)idx;
226 }
227
228 return MTE_STATE_ACTIVE;
229 }
230
231 static ppnum_t
covered_page(cell_idx_t idx,uint32_t slot)232 covered_page(cell_idx_t idx, uint32_t slot)
233 {
234 ppnum_t pnum = pmap_first_pnum + (idx * MTE_PAGES_PER_TAG_PAGE);
235
236 assert(pnum >= pmap_first_pnum);
237 assert(pnum < pmap_first_pnum + vm_pages_count);
238
239 return pnum + slot;
240 }
241
242 static void
verify_cell_mark(cell_t * cell,mte_cell_state_t state)243 verify_cell_mark(cell_t *cell, mte_cell_state_t state)
244 {
245 T_QUIET; T_ASSERT_EQ(state, (int)cell->state,
246 "correct state for cell %p", cell);
247 T_QUIET; T_ASSERT_FALSE(cell->__unused_bits,
248 "cell %p not seen yet", cell);
249 cell->__unused_bits = true;
250 }
251
252 static void
verify_cell_clear(cell_t * cell)253 verify_cell_clear(cell_t *cell)
254 {
255 T_QUIET; T_ASSERT_TRUE(cell->__unused_bits,
256 "cell %p already seen", cell);
257 cell->__unused_bits = false;
258 }
259
260 static void
verify_cell_mte_page_count(cell_t * cell,mte_cell_list_idx_t lidx)261 verify_cell_mte_page_count(cell_t *cell, mte_cell_list_idx_t lidx)
262 {
263 switch (cell->state) {
264 case MTE_STATE_DISABLED:
265 case MTE_STATE_PINNED:
266 case MTE_STATE_DEACTIVATING:
267 case MTE_STATE_RECLAIMING:
268 case MTE_STATE_ACTIVATING:
269 /* can be any mte count */
270 break;
271
272 case MTE_STATE_CLAIMED:
273 case MTE_STATE_INACTIVE:
274 T_QUIET; T_ASSERT_EQ(0, (int)cell->mte_page_count,
275 "correct mte page count (cell %d)", cell_idx(cell));
276 break;
277 default:
278 T_QUIET; T_ASSERT_EQ(lidx - MTE_LIST_ACTIVE_0_IDX,
279 (int)cell->mte_page_count != 0,
280 "correct mte page count (cell %d)", cell_idx(cell));
281 break;
282 }
283 }
284
285 static void
verify_cell_queue(mte_cell_queue_t queue,mte_cell_state_t state,mte_cell_list_idx_t lidx,mte_cell_bucket_t bucket)286 verify_cell_queue(
287 mte_cell_queue_t queue,
288 mte_cell_state_t state,
289 mte_cell_list_idx_t lidx,
290 mte_cell_bucket_t bucket)
291 {
292 cell_t *head = &queue->head;
293 cell_t *prev = head;
294
295 verify_cell_mark(head, state);
296
297 T_QUIET; T_ASSERT_EQ(0, (int)head->mte_page_count,
298 "correct mte page count (cell %d)", cell_idx(head));
299
300 cell_queue_foreach(cell, queue) {
301 verify_cell_mark(cell, state);
302
303 T_QUIET; T_ASSERT_EQ(prev, cell_from_idx(cell->prev),
304 "valid linkage");
305 verify_cell_mte_page_count(cell, lidx);
306
307 prev = cell;
308 }
309 }
310
311 static void
verify_cell_list(mte_cell_state_t state,mte_cell_list_idx_t idx)312 verify_cell_list(mte_cell_state_t state, mte_cell_list_idx_t idx)
313 {
314 mte_cell_bucket_t n = cell_list_idx_buckets(idx);
315 mte_cell_list_t list = &mte_info_lists[idx];
316
317 T_QUIET; T_ASSERT_LE(list->mask, (uint32_t)mask(n),
318 "mask has less than %d bits set", n);
319
320 for (mte_cell_bucket_t i = 0; i < n; i++) {
321 mte_cell_queue_t q = &list->buckets[i];
322
323 if (cell_queue_empty(q)) {
324 T_QUIET; T_ASSERT_FALSE(list->mask & BIT(i),
325 "bucket %d.%d is empty", idx, i);
326 } else {
327 T_QUIET; T_ASSERT_TRUE(list->mask & BIT(i),
328 "bucket %d.%d is non empty", idx, i);
329 }
330
331 verify_cell_queue(q, state, idx, i);
332 }
333 }
334
335 static void
verify_mte_info(void)336 verify_mte_info(void)
337 {
338 uint64_t count = 0;
339
340 verify_cell_list(MTE_STATE_DISABLED, MTE_LIST_DISABLED_IDX);
341 verify_cell_list(MTE_STATE_PINNED, MTE_LIST_PINNED_IDX);
342 verify_cell_list(MTE_STATE_DEACTIVATING, MTE_LIST_DEACTIVATING_IDX);
343 verify_cell_list(MTE_STATE_CLAIMED, MTE_LIST_CLAIMED_IDX);
344 verify_cell_list(MTE_STATE_INACTIVE, MTE_LIST_INACTIVE_IDX);
345 verify_cell_list(MTE_STATE_RECLAIMING, MTE_LIST_RECLAIMING_IDX);
346 verify_cell_list(MTE_STATE_ACTIVATING, MTE_LIST_ACTIVATING_IDX);
347 verify_cell_list(MTE_STATE_ACTIVE, MTE_LIST_ACTIVE_0_IDX);
348 verify_cell_list(MTE_STATE_ACTIVE, MTE_LIST_ACTIVE_IDX);
349
350 for (cell_idx_t i = -MTE_QUEUES_COUNT; i < (cell_idx_t)mte_tag_storage_count; i++) {
351 verify_cell_clear(cell_from_idx(i));
352 }
353
354 for (uint32_t i = 0; i < MTE_LISTS_COUNT; i++) {
355 count += mte_info_lists[i].count;
356 }
357 T_QUIET; T_ASSERT_EQ(count, (uint64_t)mte_tag_storage_count, "cell count");
358 }
359
360 static void
verify_cell_in_list(cell_t * cell,mte_cell_list_idx_t idx)361 verify_cell_in_list(cell_t *cell, mte_cell_list_idx_t idx)
362 {
363 mte_cell_bucket_t bucket = cell_list_bucket(*cell);
364 mte_cell_queue_t queue = &mte_info_lists[idx].buckets[bucket];
365
366 T_QUIET; T_ASSERT_EQ(cell_state_from_list_idx(idx), (int)cell->state,
367 "correct state for cell %p", cell);
368
369 cell_queue_foreach(it, queue) {
370 if (cell == it) {
371 T_PASS("cell %p found in list %d.%d", cell, idx, bucket);
372 return;
373 }
374 }
375
376 T_ASSERT_FAIL("cell %p not found in list %d.%d", cell, idx, bucket);
377 }
378
379 static void
print_cell(cell_t * cellp)380 print_cell(cell_t *cellp)
381 {
382 printf(" cell (%p) { index: %d, free: %d, mte: %d, next: %d, prev: %d }\n",
383 cellp, cell_idx(cellp), cell_free_page_count(*cellp), cellp->mte_page_count,
384 cellp->next, cellp->prev);
385 }
386
387 static void
print_cell_queue(mte_cell_list_idx_t idx,mte_cell_queue_t queue,mte_cell_bucket_t bucket)388 print_cell_queue(mte_cell_list_idx_t idx, mte_cell_queue_t queue, mte_cell_bucket_t bucket)
389 {
390 cell_t head = queue->head;
391
392 printf(" %s[%d.%d] queue (%p) { index: %d, next: %d, prev: %d }\n",
393 cell_states[head.state], idx, bucket,
394 queue, cell_idx(queue), head.next, head.prev);
395
396 cell_queue_foreach(cell, queue) {
397 print_cell(cell);
398 }
399 }
400
401 static void
print_cell_list(mte_cell_list_idx_t idx)402 print_cell_list(mte_cell_list_idx_t idx)
403 {
404 mte_cell_bucket_t n = cell_list_idx_buckets(idx);
405 mte_cell_list_t list = &mte_info_lists[idx];
406 cell_t head = list->buckets[0].head;
407
408 printf(" %s[%d] list (%p) { mask: 0x%08x }\n",
409 cell_states[head.state], idx, list, list->mask);
410
411 for (mte_cell_bucket_t i = 0; i < n; i++) {
412 print_cell_queue(idx, &list->buckets[i], i);
413 }
414
415 printf("\n");
416 }
417
418 static void
print_mte_info(void)419 print_mte_info(void)
420 {
421 printf("MTE Info\n");
422
423 print_cell_list(MTE_LIST_DISABLED_IDX);
424 print_cell_list(MTE_LIST_PINNED_IDX);
425 print_cell_list(MTE_LIST_CLAIMED_IDX);
426 print_cell_list(MTE_LIST_INACTIVE_IDX);
427 print_cell_list(MTE_LIST_DEACTIVATING_IDX);
428 print_cell_list(MTE_LIST_RECLAIMING_IDX);
429 print_cell_list(MTE_LIST_ACTIVATING_IDX);
430 print_cell_list(MTE_LIST_ACTIVE_0_IDX);
431 print_cell_list(MTE_LIST_ACTIVE_IDX);
432 }
433
434 static void
print_mte_info_on_failure(void)435 print_mte_info_on_failure(void)
436 {
437 if (mte_info_cells) {
438 print_mte_info();
439 }
440 }
441
442 static void
test_setup(bool skip_free_pages)443 test_setup(bool skip_free_pages)
444 {
445 static bool atend_done;
446
447 /*
448 * This a hack: if the test asserts in the middle, mte_info_cells will
449 * not be freed, and be printed.
450 */
451 if (!atend_done) {
452 T_ATEND(print_mte_info_on_failure);
453 atend_done = true;
454 }
455
456 T_QUIET; T_ASSERT_FALSE(mte_info_cells, "test_teardown was forgotten");
457
458 mteinfo_init(mte_tag_storage_count);
459
460 /* Simulate vm_page_release_startup() */
461 for (uint32_t i = 0; i < vm_pages_count; i++) {
462 ppnum_t pnum = i + pmap_first_pnum;
463 vm_page_t mem = &vm_pages[i];
464
465 mem->ppnum = pnum;
466
467 if (pnum == mte_tag_storage_ecc_disabled) {
468 /* Skip this page; it is "broken." */
469 } else if (pmap_in_tag_storage_range(pnum)) {
470 /* TODO: Simulate early boot pre-set pages. */
471 mteinfo_tag_storage_set_inactive(mem, true);
472 } else if (!skip_free_pages) {
473 mteinfo_covered_page_set_free(pnum, false);
474 }
475 }
476 }
477
478 static void
test_teardown(void)479 test_teardown(void)
480 {
481 free(mte_info_cells - MTE_QUEUES_COUNT);
482 mte_info_cells = NULL;
483 }
484
485 static void
t_set_activating(cell_idx_t idx)486 t_set_activating(cell_idx_t idx)
487 {
488 cell_t *cell = cell_from_idx(idx);
489 vm_page_t tag_page = vm_tag_storage_page_get(idx);
490
491 assert_cell_state(cell, MTE_MASK_INACTIVE);
492
493 CELL_UPDATE(cell, tag_page, false, {
494 cell->state = MTE_STATE_ACTIVATING;
495 });
496 }
497
498 static void
t_set_deactivating(cell_idx_t idx)499 t_set_deactivating(cell_idx_t idx)
500 {
501 cell_t *cell = cell_from_idx(idx);
502 vm_page_t tag_page = vm_tag_storage_page_get(idx);
503
504 assert_cell_state(cell, MTE_MASK_ACTIVE);
505
506 CELL_UPDATE(cell, tag_page, false, {
507 cell->state = MTE_STATE_DEACTIVATING;
508 });
509 }
510
511 static void
t_set_reclaiming(cell_idx_t idx)512 t_set_reclaiming(cell_idx_t idx)
513 {
514 cell_t *cell = cell_from_idx(idx);
515 vm_page_t tag_page = vm_tag_storage_page_get(idx);
516
517 mteinfo_tag_storage_set_reclaiming(cell, tag_page);
518 }
519
520
521 T_DECL(init, "check that initialization sets up the data structure correctly")
522 {
523 vm_page_t tag_page;
524 cell_t *cell;
525
526 test_setup(false);
527
528 verify_mte_info();
529
530 verify_cell_in_list(cell_from_covered_ppnum(pmap_first_pnum),
531 MTE_LIST_INACTIVE_IDX);
532
533 tag_page = vm_page_find_canonical(mte_tag_storage_ecc_disabled);
534 verify_cell_in_list(cell_from_tag_storage_page(tag_page),
535 MTE_LIST_DISABLED_IDX);
536
537 cell = cell_from_covered_ppnum(mte_tag_storage_start_pnum) - 1;
538 /* cell before last first tag storage is normal */
539 verify_cell_in_list(cell, MTE_LIST_INACTIVE_IDX);
540 /* first self referential page has "nothing free" (for now) */
541 verify_cell_in_list(cell + 1, MTE_LIST_INACTIVE_IDX);
542
543 verify_cell_in_list(cell_from_idx(100), MTE_LIST_INACTIVE_IDX);
544
545 test_teardown();
546 }
547
548 T_DECL(cell_list, "checks cells migrations between lists")
549 {
550 cell_idx_t cidx = 0;
551
552 test_setup(false);
553
554 T_LOG("active <-> inactive transitions");
555 {
556 cidx = 100;
557 t_set_activating(cidx);
558 mteinfo_tag_storage_set_active(&vm_pages_tag_storage[cidx], 0, false);
559 verify_mte_info();
560 verify_cell_in_list(cell_from_idx(cidx), MTE_LIST_ACTIVE_0_IDX);
561
562 t_set_deactivating(cidx);
563 mteinfo_tag_storage_set_inactive(&vm_pages_tag_storage[cidx], false);
564 verify_mte_info();
565 verify_cell_in_list(cell_from_idx(cidx), MTE_LIST_INACTIVE_IDX);
566
567 cidx = 101;
568 t_set_activating(cidx);
569 mteinfo_tag_storage_set_active(&vm_pages_tag_storage[cidx], 0, false);
570 verify_mte_info();
571 verify_cell_in_list(cell_from_idx(cidx), MTE_LIST_ACTIVE_0_IDX);
572
573 cidx = 102;
574 t_set_activating(cidx);
575 mteinfo_tag_storage_set_active(&vm_pages_tag_storage[cidx], 0, false);
576 verify_mte_info();
577 verify_cell_in_list(cell_from_idx(cidx), MTE_LIST_ACTIVE_0_IDX);
578
579 cidx = 103;
580 t_set_activating(cidx);
581 mteinfo_tag_storage_set_active(&vm_pages_tag_storage[cidx], 0, false);
582 verify_mte_info();
583 verify_cell_in_list(cell_from_idx(cidx), MTE_LIST_ACTIVE_0_IDX);
584
585 cidx = 101;
586 t_set_deactivating(cidx);
587 mteinfo_tag_storage_set_inactive(&vm_pages_tag_storage[cidx], false);
588 verify_mte_info();
589 verify_cell_in_list(cell_from_idx(cidx), MTE_LIST_INACTIVE_IDX);
590 }
591
592 T_LOG("inactive <-> claimed <-> reclaiming transitions");
593 {
594 for (cidx = 110; cidx < 120; cidx++) {
595 mteinfo_tag_storage_set_claimed(&vm_pages_tag_storage[cidx]);
596 verify_mte_info();
597 verify_cell_in_list(cell_from_idx(cidx), MTE_LIST_CLAIMED_IDX);
598 }
599
600 cidx = 111;
601 mteinfo_tag_storage_set_inactive(&vm_pages_tag_storage[cidx], false);
602 verify_mte_info();
603 verify_cell_in_list(cell_from_idx(cidx), MTE_LIST_INACTIVE_IDX);
604
605 for (cidx = 115; cidx < 120; cidx++) {
606 t_set_reclaiming(cidx);
607 verify_mte_info();
608 verify_cell_in_list(cell_from_idx(cidx), MTE_LIST_RECLAIMING_IDX);
609 }
610
611 cidx = 115;
612 mteinfo_tag_storage_set_inactive(&vm_pages_tag_storage[cidx], false);
613 verify_mte_info();
614 verify_cell_in_list(cell_from_idx(cidx), MTE_LIST_INACTIVE_IDX);
615
616 mteinfo_tag_storage_flush_reclaiming();
617 verify_mte_info();
618 for (cidx = 116; cidx < 120; cidx++) {
619 verify_cell_in_list(cell_from_idx(cidx), MTE_LIST_CLAIMED_IDX);
620 }
621 }
622
623 test_teardown();
624 }
625
626 static void
test_cell_queue_add_rm_free_pages(cell_idx_t cidx,mte_cell_list_idx_t lidx)627 test_cell_queue_add_rm_free_pages(cell_idx_t cidx, mte_cell_list_idx_t lidx)
628 {
629 cell_t *cell = cell_from_idx(cidx);
630
631 for (int i = MTE_PAGES_PER_TAG_PAGE - cell->mte_page_count; i-- > 0;) {
632 mteinfo_covered_page_set_used(covered_page(cidx, i), false);
633 verify_mte_info();
634 verify_cell_in_list(cell, lidx);
635 }
636
637 for (int i = 0; i < MTE_PAGES_PER_TAG_PAGE - cell->mte_page_count; i++) {
638 mteinfo_covered_page_set_free(covered_page(cidx, i), false);
639 verify_mte_info();
640 verify_cell_in_list(cell, lidx);
641 }
642 }
643
644 T_DECL(cell_queue, "checks cells migrations between queues")
645 {
646 cell_idx_t cidx = 100;
647
648 test_setup(false);
649
650 T_LOG("disabled");
651 test_cell_queue_add_rm_free_pages(200, MTE_LIST_DISABLED_IDX);
652
653 T_LOG("inactive");
654 test_cell_queue_add_rm_free_pages(cidx, MTE_LIST_INACTIVE_IDX);
655
656 T_LOG("claimed");
657 mteinfo_tag_storage_set_claimed(&vm_pages_tag_storage[cidx]);
658 test_cell_queue_add_rm_free_pages(cidx, MTE_LIST_CLAIMED_IDX);
659
660 T_LOG("reclaiming");
661 t_set_reclaiming(cidx);
662 test_cell_queue_add_rm_free_pages(cidx, MTE_LIST_RECLAIMING_IDX);
663
664 mteinfo_tag_storage_set_inactive(&vm_pages_tag_storage[cidx], false);
665
666 t_set_activating(cidx);
667 mteinfo_tag_storage_set_active(&vm_pages_tag_storage[cidx], 0, false);
668
669 for (int i = 0; i <= MTE_PAGES_PER_TAG_PAGE; i++) {
670 T_LOG("active[%d]", i);
671
672 if (i != 0) {
673 mteinfo_covered_page_set_used(covered_page(cidx,
674 MTE_PAGES_PER_TAG_PAGE - i), true);
675 }
676
677 test_cell_queue_add_rm_free_pages(cidx,
678 i ? MTE_LIST_ACTIVE_IDX : MTE_LIST_ACTIVE_0_IDX);
679 verify_mte_info();
680
681 if (i == MTE_PAGES_PER_TAG_PAGE) {
682 verify_cell_in_list(cell_from_idx(cidx),
683 MTE_LIST_ACTIVE_IDX);
684 }
685 }
686
687 test_teardown();
688 }
689
690 T_DECL(find_tag, "validate the policies around finding tag storage pages")
691 {
692 #define T_ASSERT_FIND_TAG(how, idx, msg, ...) \
693 T_ASSERT_EQ((long)idx, cell_list_find_last_page(MTE_LIST_##how##_IDX, 1, &tag_page) - \
694 mte_info_cells, msg, ## __VA_ARGS__)
695
696 #define T_ASSERT_FIND_NO_TAG(how, msg, ...) \
697 T_ASSERT_EQ(NULL, cell_list_find_last_page(MTE_LIST_##how##_IDX, 1, &tag_page), \
698 msg, ## __VA_ARGS__)
699
700 /* We set no pages as "free." */
701 test_setup(true);
702 vm_page_t tag_page;
703
704 T_ASSERT_FIND_NO_TAG(CLAIMED, "nothing to find");
705 T_ASSERT_FIND_NO_TAG(INACTIVE, "nothing to find");
706
707 /* Play with claimed pages. */
708 mteinfo_tag_storage_set_claimed(&vm_pages_tag_storage[30]);
709 T_ASSERT_FIND_NO_TAG(CLAIMED, "nothing to find");
710
711 mteinfo_covered_page_set_free(covered_page(30, 0), false);
712 T_ASSERT_FIND_TAG(CLAIMED, 30, "should find claimed %d", 30);
713
714 mteinfo_tag_storage_set_claimed(&vm_pages_tag_storage[31]);
715 for (uint32_t i = 0; i < 8; i++) {
716 mteinfo_covered_page_set_free(covered_page(31, i), false);
717 T_ASSERT_FIND_TAG(CLAIMED, 30, "should still find claimed %d", 30);
718 }
719
720 mteinfo_covered_page_set_free(covered_page(31, 16), false);
721 T_ASSERT_FIND_TAG(CLAIMED, 31, "should now find claimed %d", 31);
722
723 /* Play with inactive pages. */
724 verify_cell_in_list(cell_from_idx(40), MTE_LIST_INACTIVE_IDX);
725 verify_cell_in_list(cell_from_idx(41), MTE_LIST_INACTIVE_IDX);
726 T_ASSERT_FIND_NO_TAG(INACTIVE, "nothing to find");
727
728 mteinfo_covered_page_set_free(covered_page(40, 0), false);
729 T_ASSERT_FIND_TAG(INACTIVE, 40, "should find inactive %d", 40);
730
731 /* More free pages. */
732 for (uint32_t i = 0; i < 8; i++) {
733 mteinfo_covered_page_set_free(covered_page(41, i), false);
734 T_ASSERT_FIND_TAG(INACTIVE, 40, "should still find inactive %d", 40);
735 }
736
737 mteinfo_covered_page_set_free(covered_page(41, 16), false);
738 T_ASSERT_FIND_TAG(INACTIVE, 41, "should now find inactive %d", 41);
739
740 test_teardown();
741 #undef T_ASSERT_FIND_TAG
742 #undef T_ASSERT_FIND_NO_TAG
743 }
744
745 #pragma clang attribute pop
746
747 static cell_t
cell_with(uint32_t tagged,uint32_t free)748 cell_with(uint32_t tagged, uint32_t free)
749 {
750 return (cell_t){
751 .mte_page_count = tagged,
752 .free_mask = (uint32_t)mask(free),
753 .state = MTE_STATE_ACTIVE,
754 };
755 }
756
757 static mte_free_queue_idx_t
t_active_bucket(cell_t cell)758 t_active_bucket(cell_t cell)
759 {
760 #if 1
761 uint32_t free = cell_free_page_count(cell);
762 uint32_t tagged = cell.mte_page_count;
763 uint32_t used = 32 - tagged - free;
764 uint32_t n;
765
766 n = tagged + free / 3;
767 n -= MIN(n, used) / 2;
768 return MTE_FREE_ACTIVE_0 + fls(n / 4);
769 #else
770 return mteinfo_free_queue_idx(cell);
771 #endif
772 }
773
774 static int
t_bucket_to_color(unsigned bucket)775 t_bucket_to_color(unsigned bucket)
776 {
777 if (bucket < MTE_FREE_ACTIVE_0 ||
778 bucket >= MTE_FREE_UNTAGGABLE_ACTIVATING) {
779 return 1; /* dark red */
780 }
781 return bucket - MTE_FREE_ACTIVE_0 + 2;
782 }
783
784 T_DECL(active_buckets, "helper to print/chose buckets", T_META_ENABLED(false))
785 {
786 /*
787 * 64 is enough for everybody,
788 * we're not doing security here after all are we?
789 */
790 char buf[64];
791
792 for (unsigned tagged = 0; tagged < 32; tagged++) {
793 for (unsigned free = 1; free <= 32 - tagged; free++) {
794 cell_t cell = cell_with(tagged, free);
795 mte_free_queue_idx_t b = t_active_bucket(cell);
796
797 T_QUIET; T_EXPECT_GE(b, MTE_FREE_ACTIVE_0,
798 "valid bucket for %d.%d", tagged, free);
799 T_QUIET; T_EXPECT_LT(b, MTE_FREE_UNTAGGABLE_ACTIVATING,
800 "valid bucket for %d.%d", tagged, free);
801 }
802 }
803
804 for (mte_free_queue_idx_t b = MTE_FREE_ACTIVE_0;
805 b < MTE_FREE_UNTAGGABLE_ACTIVATING; b++) {
806 unsigned column = 0;
807
808 printf("\n\033[38;5;%d;mBucket %d:\033[0m",
809 t_bucket_to_color(b), b - MTE_FREE_ACTIVE_0);
810
811 for (unsigned tagged = 0; tagged < 32; tagged++) {
812 unsigned first_free = ~0u, last_free = 0;
813
814 for (unsigned free = 1; free <= 32 - tagged; free++) {
815 cell_t cell = cell_with(tagged, free);
816
817 if (t_active_bucket(cell) == b) {
818 last_free = free;
819 first_free = MIN(free, first_free);
820 }
821 }
822
823 if (first_free > 32) {
824 continue;
825 }
826
827 if (column == 0) {
828 puts("");
829 }
830
831 if (first_free == 1 && tagged + last_free == 32) {
832 snprintf(buf, sizeof(buf), "%2d.*", tagged);
833 } else if (first_free == last_free) {
834 snprintf(buf, sizeof(buf), "%2d.%d",
835 tagged, first_free);
836 } else if (tagged + last_free == 32) {
837 snprintf(buf, sizeof(buf), "%2d.%d+",
838 tagged, first_free);
839 } else {
840 snprintf(buf, sizeof(buf), "%2d.[%d-%d]",
841 tagged, first_free, last_free);
842 }
843 printf(" %-10s", buf);
844
845 if (++column == 6) {
846 column = 0;
847 }
848 }
849 puts("");
850 }
851
852 puts("\n"
853 " \033[1mfree pages\033[0m\n"
854 " 1 2 3\n"
855 " \033[1mmte\033[0m ....5....0....5....0....5....0.2");
856
857 for (unsigned tagged = 0; tagged < 32; tagged += 2) {
858 printf(" %2d-%-2d ", tagged, tagged + 1);
859
860 for (unsigned free = 1;; free++) {
861 unsigned b_0, b_1;
862
863 b_0 = t_active_bucket(cell_with(tagged, free));
864 if (tagged + 1 + free > 32) {
865 printf("\033[49;38;5;%d;m▀\033[0m\n",
866 t_bucket_to_color(b_0));
867 break;
868 }
869
870 b_1 = t_active_bucket(cell_with(tagged + 1, free));
871 printf("\033[38;5;%d;48;5;%d;m▀",
872 t_bucket_to_color(b_0),
873 t_bucket_to_color(b_1));
874 }
875 }
876
877 puts("\033[0m");
878 }
879