1#ifdef TEST_MEM
2
3#include <crypto/prng.h>
4#include <mem/alloc.h>
5#include <mem/elcm.h>
6#include <mem/page_alloc.h>
7#include <mem/pmm.h>
8#include <mem/slab.h>
9#include <mem/tlb.h>
10#include <mem/vmm.h>
11#include <sch/sched.h>
12#include <stdbool.h>
13#include <stddef.h>
14#include <stdint.h>
15#include <string.h>
16#include <test.h>
17#include <thread/thread.h>
18
19TEST_DECLARE(pmm_alloc_test, .tier = TEST_TIER_UNIT) {
20 ABORT_IF_RAM_LOW();
21
22 paddr_t p = pmm_alloc_page();
23 TEST_ASSERT(p);
24 return TEST_SUCCESS;
25}
26
27TEST_DECLARE(vmm_map_test, .tier = TEST_TIER_UNIT) {
28 ABORT_IF_RAM_LOW();
29
30 uint64_t p = pmm_alloc_page();
31 TEST_ASSERT(p != 0);
32 void *ptr = vmm_map_bump(p, PAGE_SIZE, 0);
33 TEST_ASSERT(ptr != NULL);
34 vmm_unmap_virt(addr: ptr, PAGE_SIZE, vflags: VMM_FLAG_NONE);
35 TEST_ASSERT(vmm_get_phys((uint64_t) ptr, VMM_FLAG_NONE) == (uint64_t) -1);
36 return TEST_SUCCESS;
37}
38
39/* probably don't need these at all but I'll keep
40 * them in case something decides to be funny */
41#define ALIGNED_ALLOC_TIMES 512
42
43#define ASSERT_ALIGNED(ptr, alignment) \
44 TEST_ASSERT(((uintptr_t) (ptr) & ((alignment) - 1)) == 0)
45
46#define KMALLOC_ALIGNMENT_TEST(name, align) \
47 TEST_DECLARE(kmalloc_aligned_##name##_test, .tier = TEST_TIER_UNIT) { \
48 ABORT_IF_RAM_LOW(); \
49 for (uint64_t i = 0; i < ALIGNED_ALLOC_TIMES; i++) { \
50 void *ptr = kmalloc_aligned(align, align); \
51 TEST_ASSERT(ptr != NULL); \
52 ASSERT_ALIGNED(ptr, align); \
53 } \
54 return TEST_SUCCESS; \
55 }
56
57KMALLOC_ALIGNMENT_TEST(32, 32)
58KMALLOC_ALIGNMENT_TEST(64, 64)
59KMALLOC_ALIGNMENT_TEST(128, 128)
60KMALLOC_ALIGNMENT_TEST(256, 256)
61
62#define STRESS_ALLOC_TIMES 2048
63
64static paddr_t pmm_stress_test_ptrs[STRESS_ALLOC_TIMES];
65TEST_DECLARE(pmm_stress_alloc_free_test, .tier = TEST_TIER_UNIT) {
66 ABORT_IF_RAM_LOW();
67
68 for (uint64_t i = 0; i < STRESS_ALLOC_TIMES; i++) {
69 pmm_stress_test_ptrs[i] = pmm_alloc_page();
70 TEST_ASSERT(pmm_stress_test_ptrs[i] != 0);
71 }
72
73 for (int64_t i = STRESS_ALLOC_TIMES - 1; i >= 0; i--) {
74 pmm_free_page(addr: pmm_stress_test_ptrs[i]);
75 }
76
77 return TEST_SUCCESS;
78}
79
80static void *stress_alloc_free_ptrs[STRESS_ALLOC_TIMES] = {0};
81TEST_DECLARE(kmalloc_stress_alloc_free_test, .tier = TEST_TIER_UNIT) {
82 ABORT_IF_RAM_LOW();
83
84 for (uint64_t i = 0; i < STRESS_ALLOC_TIMES; i++) {
85 stress_alloc_free_ptrs[i] = kmalloc(64);
86 TEST_ASSERT(stress_alloc_free_ptrs[i] != NULL);
87 }
88
89 for (uint64_t i = 0; i < STRESS_ALLOC_TIMES; i++) {
90 uint64_t idx = prng_next() % STRESS_ALLOC_TIMES;
91 if (stress_alloc_free_ptrs[idx]) {
92 kfree(stress_alloc_free_ptrs[idx]);
93 stress_alloc_free_ptrs[idx] = NULL;
94 }
95 }
96
97 for (uint64_t i = 0; i < STRESS_ALLOC_TIMES; i++) {
98 if (stress_alloc_free_ptrs[i]) {
99 kfree(stress_alloc_free_ptrs[i]);
100 }
101 }
102
103 return TEST_SUCCESS;
104}
105
106/* Put it here to avoid it eating things up */
107static void *mixed_stress_test_ptrs[STRESS_ALLOC_TIMES] = {0};
108TEST_DECLARE(kmalloc_mixed_stress_test, .tier = TEST_TIER_UNIT) {
109 ABORT_IF_RAM_LOW();
110
111 for (uint64_t i = 0; i < STRESS_ALLOC_TIMES; i++) {
112 mixed_stress_test_ptrs[i] = kmalloc(128);
113 TEST_ASSERT(mixed_stress_test_ptrs[i] != NULL);
114 }
115
116 for (uint64_t i = 0; i < STRESS_ALLOC_TIMES; i++) {
117 kfree(mixed_stress_test_ptrs[i]);
118 }
119
120 return TEST_SUCCESS;
121}
122
123#define MT_THREAD_COUNT 8
124#define MT_ALLOC_TIMES 1024
125
126static volatile int kmalloc_done = 0;
127
128static void mt_kmalloc_worker(void *) {
129 void *ptrs[MT_ALLOC_TIMES] = {0};
130
131 for (uint64_t i = 0; i < MT_ALLOC_TIMES; i++) {
132 ptrs[i] = kmalloc(64);
133 TEST_ASSERT_VOID(ptrs[i] != NULL);
134 }
135
136 for (uint64_t i = 0; i < MT_ALLOC_TIMES; i++) {
137 uint64_t idx = prng_next() % MT_ALLOC_TIMES;
138
139 kfree(ptrs[idx]);
140 ptrs[idx] = NULL;
141 }
142
143 for (uint64_t i = 0; i < MT_ALLOC_TIMES; i++) {
144 kfree(ptrs[i]);
145 }
146
147 kmalloc_done++;
148}
149
150TEST_DECLARE(kmalloc_multithreaded_test, .tier = TEST_TIER_UNIT) {
151 ABORT_IF_RAM_LOW();
152
153 struct thread *threads[MT_THREAD_COUNT];
154
155 for (int i = 0; i < MT_THREAD_COUNT; i++) {
156 threads[i] = thread_spawn_custom_stack(
157 name: "mt_kmalloc_thread", entry: mt_kmalloc_worker, NULL, PAGE_SIZE * 16);
158 TEST_ASSERT(threads[i] != NULL);
159 }
160
161 while (kmalloc_done < MT_THREAD_COUNT)
162 scheduler_yield();
163
164 return TEST_SUCCESS;
165}
166
167static char hooray[128] = {0};
168TEST_DECLARE(kmalloc_new_test, .tier = TEST_TIER_UNIT) {
169
170 void *p = kmalloc_new(size: 67, ALLOC_FLAGS_DEFAULT, behavior: ALLOC_BEHAVIOR_NORMAL);
171
172 time_t ms = time_get_ms();
173 kfree_new(ptr: p, behavior: ALLOC_BEHAVIOR_NORMAL);
174 ms = time_get_ms() - ms;
175
176 snprintf(buffer: hooray, buffer_len: 128, format: "allocated %p and free took %u ms", p, ms);
177
178 test_info(hooray);
179 return TEST_SUCCESS;
180}
181
182#ifndef CACHE_LINE_SIZE
183#define CACHE_LINE_SIZE 64
184#endif
185
186static char a_msg[128];
187TEST_DECLARE(kmalloc_new_basic_test, .tier = TEST_TIER_UNIT) {
188
189 void *p1 = kmalloc_new(size: 1, ALLOC_FLAGS_DEFAULT, behavior: ALLOC_BEHAVIOR_NORMAL);
190 void *p2 = kmalloc_new(size: 64, ALLOC_FLAGS_DEFAULT, behavior: ALLOC_BEHAVIOR_NORMAL);
191 void *p3 = kmalloc_new(size: 4096, ALLOC_FLAGS_DEFAULT, behavior: ALLOC_BEHAVIOR_NORMAL);
192
193 if (!p1 || !p2 || !p3) {
194 test_info("kmalloc_new returned NULL for a valid request");
195 return TEST_FAIL(NULL);
196 }
197
198 /* Write/read back small pattern to verify memory usable */
199 memset(p1, 0xA5, 1);
200 memset(p2, 0x5A, 64);
201 memset(p3, 0xFF, 4096);
202
203 if (((uint8_t *) p1)[0] != 0xA5 || ((uint8_t *) p2)[0] != 0x5A ||
204 ((uint8_t *) p3)[0] != 0xFF) {
205 test_info("Memory pattern check failed");
206 return TEST_FAIL(NULL);
207 }
208
209 /* timed free to check that kfree_new returns quickly */
210 time_t start = time_get_ms();
211 kfree_new(ptr: p1, behavior: ALLOC_BEHAVIOR_NORMAL);
212 kfree_new(ptr: p2, behavior: ALLOC_BEHAVIOR_NORMAL);
213 kfree_new(ptr: p3, behavior: ALLOC_BEHAVIOR_NORMAL);
214 time_t elapsed = time_get_ms() - start;
215
216 snprintf(buffer: a_msg, buffer_len: sizeof(a_msg), format: "basic alloc/free OK (free took %u ms)",
217 (unsigned) elapsed);
218 test_info(a_msg);
219 return TEST_SUCCESS;
220}
221
222/*
223-------------------- Alignment preference test --------------------
224
225TEST_DECLARE(kmalloc_new_cache_align_test, .tier = TEST_TIER_UNIT) {
226 Request cache-aligned memory
227 uint16_t flags = ALLOC_FLAG_PREFER_CACHE_ALIGNED | ALLOC_FLAG_NONMOVABLE |
228 ALLOC_FLAG_NONPAGEABLE | ALLOC_FLAG_CLASS_DEFAULT;
229 void *p = kmalloc_new(128, flags, ALLOC_BEHAVIOR_NORMAL);
230 if (!p) {
231 test_info("kmalloc_new returned NULL for cache-aligned request");
232 return TEST_FAIL(NULL);
233 }
234
235 if (((uintptr_t) p % CACHE_LINE_SIZE) != 0) {
236 char msg[128];
237 snprintf(msg, sizeof(msg), "pointer %p is not cache-line aligned", p);
238 test_info(msg);
239 kfree_new(p, ALLOC_BEHAVIOR_NORMAL);
240 return TEST_FAIL(NULL);
241 }
242
243 kfree_new(p, ALLOC_BEHAVIOR_NORMAL);
244 test_info("cache alignment check passed");
245 return TEST_SUCCESS;
246}
247*/
248
249/* -------------------- Behavior flag verification test -------------------- */
250
251TEST_DECLARE(kmalloc_new_behavior_test, .tier = TEST_TIER_UNIT) {
252 /* ALLOC_BEHAVIOR_ATOMIC should require nonpageable/nonmovable - allocator
253 or sanitizers might coerce flags. This test ensures allocation doesn't
254 return NULL for such a request. */
255 return TEST_SUCCESS;
256
257 uint16_t f = ALLOC_FLAG_NONPAGEABLE | ALLOC_FLAG_NONMOVABLE |
258 ALLOC_FLAG_NO_CACHE_ALIGN;
259 void *p = kmalloc_new(size: 256, flags: f, behavior: ALLOC_BEHAVIOR_ATOMIC);
260 if (!p) {
261 test_info("kmalloc_new failed for ATOMIC nonpageable request");
262 return TEST_FAIL(NULL);
263 }
264 /* Do a quick write */
265 volatile uint8_t *b = p;
266 b[0] = 0x7E;
267 if (b[0] != 0x7E) {
268 test_info("atomic allocation memory check failed");
269 kfree_new(ptr: p, behavior: ALLOC_BEHAVIOR_NORMAL);
270 return TEST_FAIL(NULL);
271 }
272 kfree_new(ptr: p, behavior: ALLOC_BEHAVIOR_NORMAL);
273 test_info("behavior (ATOMIC) allocation passed");
274 return TEST_SUCCESS;
275}
276
277/* -------------------- Multithreaded stress test -------------------- */
278
279#define STRESS_THREADS 7
280#define STRESS_ITERS 50000
281#define MAX_LIVE_ALLOCS 1024
282#define SHOULD_FREE true
283
284static atomic_bool all_ready = false;
285
286struct stress_arg {
287 int id;
288 volatile int *done_flag;
289};
290
291static void stress_worker(void *) {
292 struct stress_arg *a = NULL;
293 /* wait until private field is visible */
294 while (!(a = thread_get_current()->private))
295 ;
296
297 while (!all_ready)
298 ;
299
300 /* allocate small tracking table dynamically */
301 void **live_ptrs = kmalloc(sizeof(void *) * MAX_LIVE_ALLOCS);
302 memset(live_ptrs, 0, sizeof(void *) * MAX_LIVE_ALLOCS);
303
304 for (int iter = 0; iter < STRESS_ITERS; ++iter) {
305 /* 1 in 8 chance to free something early (chaotic order) */
306 if ((prng_next() & 7) == 0) {
307 int idx = prng_next() % MAX_LIVE_ALLOCS;
308 if (live_ptrs[idx]) {
309 kfree_new(ptr: live_ptrs[idx], behavior: ALLOC_BEHAVIOR_NORMAL);
310 live_ptrs[idx] = NULL;
311 }
312 }
313
314 /* Allocate with randomized size and flags */
315 size_t sz = 8 + (prng_next() % 512); /* small to moderate allocations */
316 uint16_t flags = ALLOC_FLAGS_DEFAULT;
317
318 if (prng_next() & 1) {
319 flags |= ALLOC_FLAG_PREFER_CACHE_ALIGNED;
320 flags &= ~ALLOC_FLAG_NO_CACHE_ALIGN;
321 }
322 if (prng_next() & 2) {
323 flags |= ALLOC_FLAG_NONMOVABLE;
324 flags &= ~ALLOC_FLAG_MOVABLE;
325 } else {
326 flags |= ALLOC_FLAG_MOVABLE;
327 flags &= ~ALLOC_FLAG_NONMOVABLE;
328 }
329
330 enum alloc_behavior behavior = (prng_next() & 3)
331 ? ALLOC_BEHAVIOR_NORMAL
332 : ALLOC_BEHAVIOR_NO_RECLAIM;
333
334 void *p = kmalloc(sz, flags, behavior);
335 if (!p)
336 continue;
337
338 /* write simple pattern to verify memory */
339 ((uint8_t *) p)[0] = (uint8_t) (a->id + iter);
340 ((uint8_t *) p)[sz - 1] = (uint8_t) (a->id ^ iter);
341
342 /* randomly decide where to place it */
343 int idx = prng_next() % MAX_LIVE_ALLOCS;
344
345 if (live_ptrs[idx] && SHOULD_FREE)
346 kfree(live_ptrs[idx], ALLOC_BEHAVIOR_NORMAL);
347 live_ptrs[idx] = p;
348 }
349
350 /* Final cleanup */
351 for (int i = 0; i < MAX_LIVE_ALLOCS; ++i) {
352 if (live_ptrs[i])
353 kfree_new(ptr: live_ptrs[i], behavior: ALLOC_BEHAVIOR_NORMAL);
354 }
355
356 kfree(live_ptrs);
357 *a->done_flag = 1;
358}
359
360volatile int done[STRESS_THREADS];
361struct stress_arg args[STRESS_THREADS];
362static char msg[128];
363
364TEST_DECLARE(kmalloc_new_concurrency_stress_test, .tier = TEST_TIER_UNIT) {
365 memset((void *) done, 0, sizeof(done));
366
367 enum irql irql = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
368 for (int i = 0; i < STRESS_THREADS; ++i) {
369 args[i].id = i;
370 args[i].done_flag = &done[i];
371 struct thread *goofy =
372 thread_spawn(name: "kmalloc_new_stress_worker", entry: stress_worker, NULL);
373
374 goofy->private = &args[i];
375 }
376 irql_lower(old_level: irql);
377
378 all_ready = true;
379
380 time_t start = time_get_ms();
381 const time_t timeout_ms = 30 * 1000;
382 while (time_get_ms() - start < timeout_ms) {
383 int all = 1;
384 for (int i = 0; i < STRESS_THREADS; ++i) {
385 if (!done[i]) {
386 all = 0;
387 break;
388 }
389 }
390 if (all)
391 break;
392 }
393
394 for (int i = 0; i < STRESS_THREADS; ++i) {
395 if (!done[i]) {
396 snprintf(buffer: msg, buffer_len: sizeof(msg), format: "thread %d did not complete in time", i);
397 test_info(msg);
398 return TEST_SUCCESS;
399 }
400 }
401
402 test_info("aggressive concurrency stress test completed");
403 return TEST_SUCCESS;
404}
405
406/* -------------------- Small reallocation-like smoke test --------------------
407 */
408
409TEST_DECLARE(kmalloc_new_alloc_free_sequence_test, .tier = TEST_TIER_UNIT) {
410
411 void *blocks[16];
412 for (size_t i = 0; i < sizeof(blocks) / sizeof(blocks[0]); ++i) {
413 blocks[i] = kmalloc_new(size: 64 + (i * 8), ALLOC_FLAGS_DEFAULT,
414 behavior: ALLOC_BEHAVIOR_NORMAL);
415 if (!blocks[i]) {
416 test_info("failed to allocate block in sequence");
417 /* free what we did get */
418 for (size_t j = 0; j < i; ++j)
419 kfree_new(ptr: blocks[j], behavior: ALLOC_BEHAVIOR_NORMAL);
420 return TEST_FAIL(NULL);
421 }
422 }
423
424 /* free every other block first */
425 for (size_t i = 0; i < sizeof(blocks) / sizeof(blocks[0]); i += 2)
426 kfree_new(ptr: blocks[i], behavior: ALLOC_BEHAVIOR_NORMAL);
427
428 /* then free remaining */
429 for (size_t i = 1; i < sizeof(blocks) / sizeof(blocks[0]); i += 2)
430 kfree_new(ptr: blocks[i], behavior: ALLOC_BEHAVIOR_NORMAL);
431
432 test_info("alloc/free sequence test passed");
433 return TEST_SUCCESS;
434}
435
436TEST_DECLARE(tlb_shootdown_single_cpu_test, .tier = TEST_TIER_UNIT) {
437 ABORT_IF_RAM_LOW();
438
439 paddr_t p1 = pmm_alloc_page();
440 paddr_t p2 = pmm_alloc_page();
441 TEST_ASSERT(p1 && p2);
442
443 void *va = vmm_map_bump(p1, PAGE_SIZE, 0);
444 TEST_ASSERT(va);
445
446 *(volatile uint64_t *) va = 0x11111111;
447
448 vmm_unmap_virt(addr: va, PAGE_SIZE, vflags: VMM_FLAG_NONE);
449 va = vmm_map_bump(p2, PAGE_SIZE, 0);
450
451 tlb_shootdown(addr: (uintptr_t) va, true);
452
453 *(volatile uint64_t *) va = 0x22222222;
454 TEST_ASSERT(*(volatile uint64_t *) va == 0x22222222);
455
456 return TEST_SUCCESS;
457}
458
459#define TLB_TEST_THREADS 4
460
461static volatile uint64_t tlb_seen[TLB_TEST_THREADS];
462static atomic_bool tlb_go = false;
463static atomic_uint tlb_threads_done = 0;
464
465static void tlb_reader(void *arg) {
466 size_t id = (size_t) arg;
467
468 while (!atomic_load(&tlb_go))
469 cpu_relax();
470
471 volatile uint64_t *va = thread_get_current()->private;
472 tlb_seen[id] = *va;
473 atomic_fetch_add(&tlb_threads_done, 1);
474}
475
476TEST_DECLARE(tlb_shootdown_synchronous_test, .tier = TEST_TIER_UNIT) {
477 ABORT_IF_RAM_LOW();
478
479 paddr_t p1 = pmm_alloc_page();
480 paddr_t p2 = pmm_alloc_page();
481 TEST_ASSERT(p1 && p2);
482
483 void *va = vmm_map_bump(p1, PAGE_SIZE, 0);
484 TEST_ASSERT(va);
485
486 *(volatile uint64_t *) va = 0xAAAAAAAA;
487
488 struct thread *t[TLB_TEST_THREADS];
489 for (size_t i = 0; i < TLB_TEST_THREADS; i++) {
490 t[i] = thread_spawn(name: "tlb_reader", entry: tlb_reader, arg: (void *) i);
491 t[i]->private = va;
492 }
493
494 vmm_unmap_virt(addr: va, PAGE_SIZE, vflags: VMM_FLAG_NONE);
495 vmm_map_page((vaddr_t) va, p2, PAGE_WRITE);
496 *(volatile uint64_t *) va = 0xBBBBBBBB;
497
498 atomic_store(&tlb_go, true);
499 tlb_shootdown(addr: (uintptr_t) va, true);
500
501 while (atomic_load(&tlb_threads_done) < TLB_TEST_THREADS)
502 cpu_relax();
503
504 for (size_t i = 0; i < TLB_TEST_THREADS; i++) {
505 TEST_ASSERT(tlb_seen[i] == 0xBBBBBBBB);
506 }
507
508 return TEST_SUCCESS;
509}
510
511TEST_DECLARE(tlb_shootdown_async_eventual_test, .tier = TEST_TIER_UNIT) {
512 ABORT_IF_RAM_LOW();
513
514 paddr_t p1 = pmm_alloc_page();
515 paddr_t p2 = pmm_alloc_page();
516 TEST_ASSERT(p1 && p2);
517
518 void *va = vmm_map_bump(p1, PAGE_SIZE, 0);
519 *(volatile uint64_t *) va = 0x1234;
520
521 vmm_unmap_virt(addr: va, PAGE_SIZE, vflags: VMM_FLAG_NONE);
522 va = vmm_map_bump(p2, PAGE_SIZE, 0);
523 *(volatile uint64_t *) va = 0x5678;
524
525 tlb_shootdown(addr: (uintptr_t) va, false);
526
527 /* Wait for IPIs to land */
528 time_t start = time_get_ms();
529 while (time_get_ms() - start < 100) {
530 if (*(volatile uint64_t *) va == 0x5678)
531 return TEST_SUCCESS;
532 scheduler_yield();
533 }
534
535 test_info("async TLB shootdown did not converge");
536 return TEST_SUCCESS;
537}
538
539TEST_DECLARE(tlb_shootdown_flush_all_test, .tier = TEST_TIER_UNIT) {
540 ABORT_IF_RAM_LOW();
541
542 paddr_t p = pmm_alloc_page();
543 TEST_ASSERT(p);
544
545 void *va = vmm_map_bump(p, PAGE_SIZE, 0);
546
547 /* Flood shootdown queue */
548 for (size_t i = 0; i < TLB_QUEUE_SIZE * 4; i++) {
549 tlb_shootdown(addr: (uintptr_t) va, false);
550 }
551
552 /* Now do a real remap */
553 paddr_t p2 = pmm_alloc_page();
554 vmm_unmap_virt(addr: va, PAGE_SIZE, vflags: VMM_FLAG_NONE);
555 va = vmm_map_bump(p2, PAGE_SIZE, 0);
556 *(volatile uint64_t *) va = 0xDEADBEEF;
557
558 tlb_shootdown(addr: (uintptr_t) va, true);
559
560 TEST_ASSERT(*(volatile uint64_t *) va == 0xDEADBEEF);
561 return TEST_SUCCESS;
562}
563
564static void tlb_spammer(void *) {
565 paddr_t p = pmm_alloc_page();
566 void *va = vmm_map_bump(p, PAGE_SIZE, 0);
567
568 for (int i = 0; i < 1000; i++) {
569 tlb_shootdown(addr: (uintptr_t) va, false);
570 }
571}
572
573TEST_DECLARE(tlb_shootdown_contention_test, .tier = TEST_TIER_UNIT) {
574 for (int i = 0; i < 4; i++)
575 thread_spawn(name: "tlb_spammer", entry: tlb_spammer, NULL);
576
577 time_t start = time_get_ms();
578 while (time_get_ms() - start < 200)
579 scheduler_yield();
580
581 test_info("concurrent shootdown stress completed");
582 return TEST_SUCCESS;
583}
584
585static void print_cand(struct elcm_candidate c) {
586 test_info("C(s=%F, p=%u, w=%u, W=%F, d=%u, b=%u, o=%u)", c.score_value,
587 c.pages, c.wasted, c.wastage, c.distance, c.bitmap_bytes,
588 c.obj_count);
589}
590
591TEST_DECLARE(elcm_test, .tier = TEST_TIER_UNIT) {
592 struct elcm_params params = {
593 .obj_size = 938,
594 .max_wastage_pct = ELCM_MAX_WASTAGE_DEFAULT,
595 .max_pages = SIZE_MAX,
596 .bias_towards_pow2 = true,
597 .metadata_size_bytes = 96,
598 .metadata_bits_per_obj = 1,
599 };
600
601 elcm(params: &params);
602 print_cand(c: params.out);
603 params.bias_towards_pow2 = false;
604 elcm(params: &params);
605 print_cand(c: params.out);
606
607 return TEST_SUCCESS;
608}
609
610#define KFREE_IRQ_TEST_ALLOC_COUNT 2048
611#define KFREE_IRQ_TEST_FREES_PER_IRQ_MIDRANGE (KFREE_IRQ_TEST_ALLOC_COUNT / 128)
612#define KFREE_IRQ_TEST_SPIN_MASK UINT8_MAX
613
614static void *kfree_irq_allocs[KFREE_IRQ_TEST_ALLOC_COUNT] = {0};
615static atomic_size_t kfree_irq_test_consumed = 0;
616
617static enum irq_result kfree_irq_test_irq(void *arg, irq_t irq,
618 struct irq_context *irqc) {
619 /* Non-ordered load here is OK, we are the only modifier (this CPU) */
620 uint8_t seed = prng_next() & 0xF;
621 int delta = seed > 0x7 ? -(seed & 0x7) : (seed & 0x7);
622 int possible = KFREE_IRQ_TEST_FREES_PER_IRQ_MIDRANGE + delta;
623 if (possible < 0)
624 possible = KFREE_IRQ_TEST_FREES_PER_IRQ_MIDRANGE;
625
626 if (possible + kfree_irq_test_consumed > KFREE_IRQ_TEST_ALLOC_COUNT)
627 possible = KFREE_IRQ_TEST_ALLOC_COUNT - kfree_irq_test_consumed;
628
629 for (int i = 0; i < possible; i++) {
630 kassert(kfree_irq_test_consumed < KFREE_IRQ_TEST_ALLOC_COUNT);
631 int idx = atomic_fetch_add(&kfree_irq_test_consumed, 1);
632 kfree_defer_irq(ptr: kfree_irq_allocs[idx]);
633 int spins = prng_next() & KFREE_IRQ_TEST_SPIN_MASK;
634
635 while (spins) {
636 cpu_relax();
637 spins--;
638 }
639 }
640
641 return IRQ_HANDLED;
642}
643
644TEST_DECLARE(kfree_defer_irq_test, .tier = TEST_TIER_UNIT) {
645 if (global.core_count < 4) {
646 return TEST_SKIP(TEST_SKIP_NONE);
647 }
648
649 irq_t irq = irq_alloc_entry();
650 irq_register(name: "kfree_defer_irq_test", vector: irq, handler: kfree_irq_test_irq, NULL,
651 flags: IRQ_FLAG_NONE);
652 irq_set_chip(vector: irq, chip: lapic_get_chip(), NULL);
653
654 for (int i = 0; i < KFREE_IRQ_TEST_ALLOC_COUNT; i++) {
655 kfree_irq_allocs[i] = kmalloc(64);
656 }
657
658 while (atomic_load(&kfree_irq_test_consumed) < KFREE_IRQ_TEST_ALLOC_COUNT) {
659 ipi_send(apic_id: 3, vector: irq);
660 int spins = prng_next() & KFREE_IRQ_TEST_SPIN_MASK;
661
662 while (spins) {
663 cpu_relax();
664 spins--;
665 }
666 }
667 return TEST_SUCCESS;
668}
669
670TEST_DECLARE(page_alloc_demand_test, .tier = TEST_TIER_UNIT) {
671 void *ptr = page_alloc_demand(8, ALLOC_FLAGS_ZERO);
672 memset(ptr, 67, PAGE_SIZE);
673 test_info("successfully demand allocated and memsetted memory");
674 return TEST_SUCCESS;
675}
676
677#define DP_PAGES 16
678#define DP_STRIDE (PAGE_SIZE / sizeof(uint64_t))
679#define DP_MAX_BUFS 8
680#define DP_MAX_THREADS 64
681
682struct dp_worker {
683 _Atomic uint64_t **bufs; /* nbuf demand buffers, counter at page head */
684 size_t nbuf;
685 size_t pages;
686 atomic_uint *done;
687};
688
689static void dp_hammer(void *arg) {
690 struct dp_worker *w = arg;
691
692 /* touch every page of every buffer; first touch faults the zero frame in,
693 * the atomic add is the lost-update probe */
694 for (size_t b = 0; b < w->nbuf; b++)
695 for (size_t p = 0; p < w->pages; p++)
696 atomic_fetch_add_explicit(&w->bufs[b][p * DP_STRIDE], 1,
697 memory_order_relaxed);
698
699 atomic_fetch_add(w->done, 1);
700}
701
702static bool dp_alloc_bufs(_Atomic uint64_t **bufs, size_t nbuf, size_t pages) {
703 for (size_t b = 0; b < nbuf; b++) {
704 bufs[b] = page_alloc_demand(pages, ALLOC_FLAGS_ZERO);
705 if (!bufs[b]) {
706 for (size_t j = 0; j < b; j++)
707 page_free((void *) bufs[j], pages);
708 return false;
709 }
710 }
711 return true;
712}
713
714/* every page was faulted in by the workers, so all frames are present here */
715static void dp_free_bufs(_Atomic uint64_t **bufs, size_t nbuf, size_t pages) {
716 for (size_t b = 0; b < nbuf; b++)
717 page_free((void *) bufs[b], pages);
718}
719
720static bool dp_verify(_Atomic uint64_t **bufs, size_t nbuf, size_t pages,
721 uint64_t expect) {
722 for (size_t b = 0; b < nbuf; b++)
723 for (size_t p = 0; p < pages; p++)
724 if (atomic_load(&bufs[b][p * DP_STRIDE]) != expect)
725 return false;
726
727 return true;
728}
729
730/* Spawn nthreads workers over the shared buffer set. single_core pins them all
731 * to core 0 (the race is then preemption inside the fault handler); otherwise
732 * they spread round-robin across every CPU (true parallel faults) */
733static void dp_spawn(struct thread **t, size_t nthreads, struct dp_worker *w,
734 bool single_core) {
735 for (size_t i = 0; i < nthreads; i++) {
736 uint64_t core = single_core ? 0 : (i % global.core_count);
737 t[i] = thread_spawn_on_core(name: "dp_hammer", entry: dp_hammer, arg: w, core_id: core);
738 if (single_core)
739 thread_pin(t: t[i]);
740 }
741}
742
743/* 1 buffer, N threads, 1 CPU: serialized faults + preemption mid-handler */
744TEST_DECLARE(demand_1buf_Nthreads_1cpu_test, .tier = TEST_TIER_UNIT) {
745 ABORT_IF_RAM_LOW();
746
747 const size_t pages = DP_PAGES, nthreads = 8, nbuf = 1;
748 _Atomic uint64_t *bufs[1];
749 TEST_ASSERT(dp_alloc_bufs(bufs, nbuf, pages));
750
751 atomic_uint done = 0;
752 struct dp_worker w = {bufs, nbuf, pages, &done};
753 struct thread *t[DP_MAX_THREADS];
754 dp_spawn(t, nthreads, w: &w, /*single_core=*/true);
755
756 while (atomic_load(&done) < nthreads)
757 scheduler_yield();
758
759 TEST_ASSERT(dp_verify(bufs, nbuf, pages, nthreads));
760 dp_free_bufs(bufs, nbuf, pages);
761 return TEST_SUCCESS;
762}
763
764/* 1 buffer, N threads, N CPUs: many CPUs racing the same demand PTEs */
765TEST_DECLARE(demand_1buf_Nthreads_Ncpu_test, .tier = TEST_TIER_UNIT) {
766 ABORT_IF_RAM_LOW();
767
768 if (global.core_count < 2) {
769 return TEST_SKIP(TEST_SKIP_NONE);
770 }
771
772 const size_t pages = DP_PAGES, nbuf = 1;
773 size_t nthreads = global.core_count;
774 if (nthreads > DP_MAX_THREADS)
775 nthreads = DP_MAX_THREADS;
776
777 _Atomic uint64_t *bufs[1];
778 TEST_ASSERT(dp_alloc_bufs(bufs, nbuf, pages));
779
780 atomic_uint done = 0;
781 struct dp_worker w = {bufs, nbuf, pages, &done};
782 struct thread *t[DP_MAX_THREADS];
783 dp_spawn(t, nthreads, w: &w, /*single_core=*/false);
784
785 while (atomic_load(&done) < nthreads)
786 scheduler_yield();
787
788 TEST_ASSERT(dp_verify(bufs, nbuf, pages, nthreads));
789 dp_free_bufs(bufs, nbuf, pages);
790 return TEST_SUCCESS;
791}
792
793/* N buffers, M threads (M > N), N CPUs: contention spread over many regions */
794TEST_DECLARE(demand_Nbuf_Mthreads_Ncpu_test, .tier = TEST_TIER_UNIT) {
795 ABORT_IF_RAM_LOW();
796
797 if (global.core_count < 2) {
798 return TEST_SKIP(TEST_SKIP_NONE);
799 }
800
801 const size_t pages = DP_PAGES;
802 size_t nbuf = global.core_count;
803 if (nbuf > DP_MAX_BUFS)
804 nbuf = DP_MAX_BUFS;
805 size_t nthreads = 2 * nbuf; /* M > N */
806 if (nthreads > DP_MAX_THREADS)
807 nthreads = DP_MAX_THREADS;
808
809 _Atomic uint64_t *bufs[DP_MAX_BUFS];
810 TEST_ASSERT(dp_alloc_bufs(bufs, nbuf, pages));
811
812 atomic_uint done = 0;
813 struct dp_worker w = {bufs, nbuf, pages, &done};
814 struct thread *t[DP_MAX_THREADS];
815 dp_spawn(t, nthreads, w: &w, /*single_core=*/false);
816
817 while (atomic_load(&done) < nthreads)
818 scheduler_yield();
819
820 TEST_ASSERT(dp_verify(bufs, nbuf, pages, nthreads));
821 dp_free_bufs(bufs, nbuf, pages);
822 return TEST_SUCCESS;
823}
824
825TEST_DECLARE(slab_demand_test, .tier = TEST_TIER_UNIT) {
826 /* One of these should eventually touch the demand page */
827 for (size_t i = 0; i < 5000; i++) {
828 void *p = kmalloc(500, ALLOC_FLAGS_ZERO | ALLOC_FLAG_PAGEABLE);
829 memset(p, 0, 500);
830 }
831
832 return TEST_SUCCESS;
833}
834
835#endif
836