1 // SPDX-License-Identifier: GPL-2.0-or-later
2 #include "alloc_api.h"
3
4 /*
5 * A simple test that tries to allocate a small memory region.
6 * Expect to allocate an aligned region near the end of the available memory.
7 */
alloc_top_down_simple_check(void)8 static int alloc_top_down_simple_check(void)
9 {
10 struct memblock_region *rgn = &memblock.reserved.regions[0];
11 void *allocated_ptr = NULL;
12
13 phys_addr_t size = SZ_2;
14 phys_addr_t expected_start;
15
16 setup_memblock();
17
18 expected_start = memblock_end_of_DRAM() - SMP_CACHE_BYTES;
19
20 allocated_ptr = memblock_alloc(size, SMP_CACHE_BYTES);
21
22 assert(allocated_ptr);
23 assert(rgn->size == size);
24 assert(rgn->base == expected_start);
25
26 assert(memblock.reserved.cnt == 1);
27 assert(memblock.reserved.total_size == size);
28
29 return 0;
30 }
31
32 /*
33 * A test that tries to allocate memory next to a reserved region that starts at
34 * the misaligned address. Expect to create two separate entries, with the new
35 * entry aligned to the provided alignment:
36 *
37 * +
38 * | +--------+ +--------|
39 * | | rgn2 | | rgn1 |
40 * +------------+--------+---------+--------+
41 * ^
42 * |
43 * Aligned address boundary
44 *
45 * The allocation direction is top-down and region arrays are sorted from lower
46 * to higher addresses, so the new region will be the first entry in
47 * memory.reserved array. The previously reserved region does not get modified.
48 * Region counter and total size get updated.
49 */
alloc_top_down_disjoint_check(void)50 static int alloc_top_down_disjoint_check(void)
51 {
52 /* After allocation, this will point to the "old" region */
53 struct memblock_region *rgn1 = &memblock.reserved.regions[1];
54 struct memblock_region *rgn2 = &memblock.reserved.regions[0];
55 struct region r1;
56 void *allocated_ptr = NULL;
57
58 phys_addr_t r2_size = SZ_16;
59 /* Use custom alignment */
60 phys_addr_t alignment = SMP_CACHE_BYTES * 2;
61 phys_addr_t total_size;
62 phys_addr_t expected_start;
63
64 setup_memblock();
65
66 r1.base = memblock_end_of_DRAM() - SZ_2;
67 r1.size = SZ_2;
68
69 total_size = r1.size + r2_size;
70 expected_start = memblock_end_of_DRAM() - alignment;
71
72 memblock_reserve(r1.base, r1.size);
73
74 allocated_ptr = memblock_alloc(r2_size, alignment);
75
76 assert(allocated_ptr);
77 assert(rgn1->size == r1.size);
78 assert(rgn1->base == r1.base);
79
80 assert(rgn2->size == r2_size);
81 assert(rgn2->base == expected_start);
82
83 assert(memblock.reserved.cnt == 2);
84 assert(memblock.reserved.total_size == total_size);
85
86 return 0;
87 }
88
89 /*
90 * A test that tries to allocate memory when there is enough space at the end
91 * of the previously reserved block (i.e. first fit):
92 *
93 * | +--------+--------------|
94 * | | r1 | r2 |
95 * +--------------+--------+--------------+
96 *
97 * Expect a merge of both regions. Only the region size gets updated.
98 */
alloc_top_down_before_check(void)99 static int alloc_top_down_before_check(void)
100 {
101 struct memblock_region *rgn = &memblock.reserved.regions[0];
102 void *allocated_ptr = NULL;
103
104 /*
105 * The first region ends at the aligned address to test region merging
106 */
107 phys_addr_t r1_size = SMP_CACHE_BYTES;
108 phys_addr_t r2_size = SZ_512;
109 phys_addr_t total_size = r1_size + r2_size;
110
111 setup_memblock();
112
113 memblock_reserve(memblock_end_of_DRAM() - total_size, r1_size);
114
115 allocated_ptr = memblock_alloc(r2_size, SMP_CACHE_BYTES);
116
117 assert(allocated_ptr);
118 assert(rgn->size == total_size);
119 assert(rgn->base == memblock_end_of_DRAM() - total_size);
120
121 assert(memblock.reserved.cnt == 1);
122 assert(memblock.reserved.total_size == total_size);
123
124 return 0;
125 }
126
127 /*
128 * A test that tries to allocate memory when there is not enough space at the
129 * end of the previously reserved block (i.e. second fit):
130 *
131 * | +-----------+------+ |
132 * | | r2 | r1 | |
133 * +------------+-----------+------+-----+
134 *
135 * Expect a merge of both regions. Both the base address and size of the region
136 * get updated.
137 */
alloc_top_down_after_check(void)138 static int alloc_top_down_after_check(void)
139 {
140 struct memblock_region *rgn = &memblock.reserved.regions[0];
141 struct region r1;
142 void *allocated_ptr = NULL;
143
144 phys_addr_t r2_size = SZ_512;
145 phys_addr_t total_size;
146
147 setup_memblock();
148
149 /*
150 * The first region starts at the aligned address to test region merging
151 */
152 r1.base = memblock_end_of_DRAM() - SMP_CACHE_BYTES;
153 r1.size = SZ_8;
154
155 total_size = r1.size + r2_size;
156
157 memblock_reserve(r1.base, r1.size);
158
159 allocated_ptr = memblock_alloc(r2_size, SMP_CACHE_BYTES);
160
161 assert(allocated_ptr);
162 assert(rgn->size == total_size);
163 assert(rgn->base == r1.base - r2_size);
164
165 assert(memblock.reserved.cnt == 1);
166 assert(memblock.reserved.total_size == total_size);
167
168 return 0;
169 }
170
171 /*
172 * A test that tries to allocate memory when there are two reserved regions with
173 * a gap too small to fit the new region:
174 *
175 * | +--------+----------+ +------|
176 * | | r3 | r2 | | r1 |
177 * +-------+--------+----------+---+------+
178 *
179 * Expect to allocate a region before the one that starts at the lower address,
180 * and merge them into one. The region counter and total size fields get
181 * updated.
182 */
alloc_top_down_second_fit_check(void)183 static int alloc_top_down_second_fit_check(void)
184 {
185 struct memblock_region *rgn = &memblock.reserved.regions[0];
186 struct region r1, r2;
187 void *allocated_ptr = NULL;
188
189 phys_addr_t r3_size = SZ_1K;
190 phys_addr_t total_size;
191
192 setup_memblock();
193
194 r1.base = memblock_end_of_DRAM() - SZ_512;
195 r1.size = SZ_512;
196
197 r2.base = r1.base - SZ_512;
198 r2.size = SZ_256;
199
200 total_size = r1.size + r2.size + r3_size;
201
202 memblock_reserve(r1.base, r1.size);
203 memblock_reserve(r2.base, r2.size);
204
205 allocated_ptr = memblock_alloc(r3_size, SMP_CACHE_BYTES);
206
207 assert(allocated_ptr);
208 assert(rgn->size == r2.size + r3_size);
209 assert(rgn->base == r2.base - r3_size);
210
211 assert(memblock.reserved.cnt == 2);
212 assert(memblock.reserved.total_size == total_size);
213
214 return 0;
215 }
216
217 /*
218 * A test that tries to allocate memory when there are two reserved regions with
219 * a gap big enough to accommodate the new region:
220 *
221 * | +--------+--------+--------+ |
222 * | | r2 | r3 | r1 | |
223 * +-----+--------+--------+--------+-----+
224 *
225 * Expect to merge all of them, creating one big entry in memblock.reserved
226 * array. The region counter and total size fields get updated.
227 */
alloc_in_between_generic_check(void)228 static int alloc_in_between_generic_check(void)
229 {
230 struct memblock_region *rgn = &memblock.reserved.regions[0];
231 struct region r1, r2;
232 void *allocated_ptr = NULL;
233
234 phys_addr_t gap_size = SMP_CACHE_BYTES;
235 phys_addr_t r3_size = SZ_64;
236 /*
237 * Calculate regions size so there's just enough space for the new entry
238 */
239 phys_addr_t rgn_size = (MEM_SIZE - (2 * gap_size + r3_size)) / 2;
240 phys_addr_t total_size;
241
242 setup_memblock();
243
244 r1.size = rgn_size;
245 r1.base = memblock_end_of_DRAM() - (gap_size + rgn_size);
246
247 r2.size = rgn_size;
248 r2.base = memblock_start_of_DRAM() + gap_size;
249
250 total_size = r1.size + r2.size + r3_size;
251
252 memblock_reserve(r1.base, r1.size);
253 memblock_reserve(r2.base, r2.size);
254
255 allocated_ptr = memblock_alloc(r3_size, SMP_CACHE_BYTES);
256
257 assert(allocated_ptr);
258 assert(rgn->size == total_size);
259 assert(rgn->base == r1.base - r2.size - r3_size);
260
261 assert(memblock.reserved.cnt == 1);
262 assert(memblock.reserved.total_size == total_size);
263
264 return 0;
265 }
266
267 /*
268 * A test that tries to allocate memory when the memory is filled with reserved
269 * regions with memory gaps too small to fit the new region:
270 *
271 * +-------+
272 * | new |
273 * +--+----+
274 * | +-----+ +-----+ +-----+ |
275 * | | res | | res | | res | |
276 * +----+-----+----+-----+----+-----+----+
277 *
278 * Expect no allocation to happen.
279 */
alloc_small_gaps_generic_check(void)280 static int alloc_small_gaps_generic_check(void)
281 {
282 void *allocated_ptr = NULL;
283
284 phys_addr_t region_size = SZ_1K;
285 phys_addr_t gap_size = SZ_256;
286 phys_addr_t region_end;
287
288 setup_memblock();
289
290 region_end = memblock_start_of_DRAM();
291
292 while (region_end < memblock_end_of_DRAM()) {
293 memblock_reserve(region_end + gap_size, region_size);
294 region_end += gap_size + region_size;
295 }
296
297 allocated_ptr = memblock_alloc(region_size, SMP_CACHE_BYTES);
298
299 assert(!allocated_ptr);
300
301 return 0;
302 }
303
304 /*
305 * A test that tries to allocate memory when all memory is reserved.
306 * Expect no allocation to happen.
307 */
alloc_all_reserved_generic_check(void)308 static int alloc_all_reserved_generic_check(void)
309 {
310 void *allocated_ptr = NULL;
311
312 setup_memblock();
313
314 /* Simulate full memory */
315 memblock_reserve(memblock_start_of_DRAM(), MEM_SIZE);
316
317 allocated_ptr = memblock_alloc(SZ_256, SMP_CACHE_BYTES);
318
319 assert(!allocated_ptr);
320
321 return 0;
322 }
323
324 /*
325 * A test that tries to allocate memory when the memory is almost full,
326 * with not enough space left for the new region:
327 *
328 * +-------+
329 * | new |
330 * +-------+
331 * |-----------------------------+ |
332 * | reserved | |
333 * +-----------------------------+---+
334 *
335 * Expect no allocation to happen.
336 */
alloc_no_space_generic_check(void)337 static int alloc_no_space_generic_check(void)
338 {
339 void *allocated_ptr = NULL;
340
341 setup_memblock();
342
343 phys_addr_t available_size = SZ_256;
344 phys_addr_t reserved_size = MEM_SIZE - available_size;
345
346 /* Simulate almost-full memory */
347 memblock_reserve(memblock_start_of_DRAM(), reserved_size);
348
349 allocated_ptr = memblock_alloc(SZ_1K, SMP_CACHE_BYTES);
350
351 assert(!allocated_ptr);
352
353 return 0;
354 }
355
356 /*
357 * A test that tries to allocate memory when the memory is almost full,
358 * but there is just enough space left:
359 *
360 * |---------------------------+---------|
361 * | reserved | new |
362 * +---------------------------+---------+
363 *
364 * Expect to allocate memory and merge all the regions. The total size field
365 * gets updated.
366 */
alloc_limited_space_generic_check(void)367 static int alloc_limited_space_generic_check(void)
368 {
369 struct memblock_region *rgn = &memblock.reserved.regions[0];
370 void *allocated_ptr = NULL;
371
372 phys_addr_t available_size = SZ_256;
373 phys_addr_t reserved_size = MEM_SIZE - available_size;
374
375 setup_memblock();
376
377 /* Simulate almost-full memory */
378 memblock_reserve(memblock_start_of_DRAM(), reserved_size);
379
380 allocated_ptr = memblock_alloc(available_size, SMP_CACHE_BYTES);
381
382 assert(allocated_ptr);
383 assert(rgn->size == MEM_SIZE);
384 assert(rgn->base == memblock_start_of_DRAM());
385
386 assert(memblock.reserved.cnt == 1);
387 assert(memblock.reserved.total_size == MEM_SIZE);
388
389 return 0;
390 }
391
392 /*
393 * A test that tries to allocate memory when there is no available memory
394 * registered (i.e. memblock.memory has only a dummy entry).
395 * Expect no allocation to happen.
396 */
alloc_no_memory_generic_check(void)397 static int alloc_no_memory_generic_check(void)
398 {
399 struct memblock_region *rgn = &memblock.reserved.regions[0];
400 void *allocated_ptr = NULL;
401
402 reset_memblock_regions();
403
404 allocated_ptr = memblock_alloc(SZ_1K, SMP_CACHE_BYTES);
405
406 assert(!allocated_ptr);
407 assert(rgn->size == 0);
408 assert(rgn->base == 0);
409 assert(memblock.reserved.total_size == 0);
410
411 return 0;
412 }
413
414 /*
415 * A simple test that tries to allocate a small memory region.
416 * Expect to allocate an aligned region at the beginning of the available
417 * memory.
418 */
alloc_bottom_up_simple_check(void)419 static int alloc_bottom_up_simple_check(void)
420 {
421 struct memblock_region *rgn = &memblock.reserved.regions[0];
422 void *allocated_ptr = NULL;
423
424 setup_memblock();
425
426 allocated_ptr = memblock_alloc(SZ_2, SMP_CACHE_BYTES);
427
428 assert(allocated_ptr);
429 assert(rgn->size == SZ_2);
430 assert(rgn->base == memblock_start_of_DRAM());
431
432 assert(memblock.reserved.cnt == 1);
433 assert(memblock.reserved.total_size == SZ_2);
434
435 return 0;
436 }
437
438 /*
439 * A test that tries to allocate memory next to a reserved region that starts at
440 * the misaligned address. Expect to create two separate entries, with the new
441 * entry aligned to the provided alignment:
442 *
443 * +
444 * | +----------+ +----------+ |
445 * | | rgn1 | | rgn2 | |
446 * +----+----------+---+----------+-----+
447 * ^
448 * |
449 * Aligned address boundary
450 *
451 * The allocation direction is bottom-up, so the new region will be the second
452 * entry in memory.reserved array. The previously reserved region does not get
453 * modified. Region counter and total size get updated.
454 */
alloc_bottom_up_disjoint_check(void)455 static int alloc_bottom_up_disjoint_check(void)
456 {
457 struct memblock_region *rgn1 = &memblock.reserved.regions[0];
458 struct memblock_region *rgn2 = &memblock.reserved.regions[1];
459 struct region r1;
460 void *allocated_ptr = NULL;
461
462 phys_addr_t r2_size = SZ_16;
463 /* Use custom alignment */
464 phys_addr_t alignment = SMP_CACHE_BYTES * 2;
465 phys_addr_t total_size;
466 phys_addr_t expected_start;
467
468 setup_memblock();
469
470 r1.base = memblock_start_of_DRAM() + SZ_2;
471 r1.size = SZ_2;
472
473 total_size = r1.size + r2_size;
474 expected_start = memblock_start_of_DRAM() + alignment;
475
476 memblock_reserve(r1.base, r1.size);
477
478 allocated_ptr = memblock_alloc(r2_size, alignment);
479
480 assert(allocated_ptr);
481
482 assert(rgn1->size == r1.size);
483 assert(rgn1->base == r1.base);
484
485 assert(rgn2->size == r2_size);
486 assert(rgn2->base == expected_start);
487
488 assert(memblock.reserved.cnt == 2);
489 assert(memblock.reserved.total_size == total_size);
490
491 return 0;
492 }
493
494 /*
495 * A test that tries to allocate memory when there is enough space at
496 * the beginning of the previously reserved block (i.e. first fit):
497 *
498 * |------------------+--------+ |
499 * | r1 | r2 | |
500 * +------------------+--------+---------+
501 *
502 * Expect a merge of both regions. Only the region size gets updated.
503 */
alloc_bottom_up_before_check(void)504 static int alloc_bottom_up_before_check(void)
505 {
506 struct memblock_region *rgn = &memblock.reserved.regions[0];
507 void *allocated_ptr = NULL;
508
509 phys_addr_t r1_size = SZ_512;
510 phys_addr_t r2_size = SZ_128;
511 phys_addr_t total_size = r1_size + r2_size;
512
513 setup_memblock();
514
515 memblock_reserve(memblock_start_of_DRAM() + r1_size, r2_size);
516
517 allocated_ptr = memblock_alloc(r1_size, SMP_CACHE_BYTES);
518
519 assert(allocated_ptr);
520 assert(rgn->size == total_size);
521 assert(rgn->base == memblock_start_of_DRAM());
522
523 assert(memblock.reserved.cnt == 1);
524 assert(memblock.reserved.total_size == total_size);
525
526 return 0;
527 }
528
529 /*
530 * A test that tries to allocate memory when there is not enough space at
531 * the beginning of the previously reserved block (i.e. second fit):
532 *
533 * | +--------+--------------+ |
534 * | | r1 | r2 | |
535 * +----+--------+--------------+---------+
536 *
537 * Expect a merge of both regions. Only the region size gets updated.
538 */
alloc_bottom_up_after_check(void)539 static int alloc_bottom_up_after_check(void)
540 {
541 struct memblock_region *rgn = &memblock.reserved.regions[0];
542 struct region r1;
543 void *allocated_ptr = NULL;
544
545 phys_addr_t r2_size = SZ_512;
546 phys_addr_t total_size;
547
548 setup_memblock();
549
550 /*
551 * The first region starts at the aligned address to test region merging
552 */
553 r1.base = memblock_start_of_DRAM() + SMP_CACHE_BYTES;
554 r1.size = SZ_64;
555
556 total_size = r1.size + r2_size;
557
558 memblock_reserve(r1.base, r1.size);
559
560 allocated_ptr = memblock_alloc(r2_size, SMP_CACHE_BYTES);
561
562 assert(allocated_ptr);
563 assert(rgn->size == total_size);
564 assert(rgn->base == r1.base);
565
566 assert(memblock.reserved.cnt == 1);
567 assert(memblock.reserved.total_size == total_size);
568
569 return 0;
570 }
571
572 /*
573 * A test that tries to allocate memory when there are two reserved regions, the
574 * first one starting at the beginning of the available memory, with a gap too
575 * small to fit the new region:
576 *
577 * |------------+ +--------+--------+ |
578 * | r1 | | r2 | r3 | |
579 * +------------+-----+--------+--------+--+
580 *
581 * Expect to allocate after the second region, which starts at the higher
582 * address, and merge them into one. The region counter and total size fields
583 * get updated.
584 */
alloc_bottom_up_second_fit_check(void)585 static int alloc_bottom_up_second_fit_check(void)
586 {
587 struct memblock_region *rgn = &memblock.reserved.regions[1];
588 struct region r1, r2;
589 void *allocated_ptr = NULL;
590
591 phys_addr_t r3_size = SZ_1K;
592 phys_addr_t total_size;
593
594 setup_memblock();
595
596 r1.base = memblock_start_of_DRAM();
597 r1.size = SZ_512;
598
599 r2.base = r1.base + r1.size + SZ_512;
600 r2.size = SZ_256;
601
602 total_size = r1.size + r2.size + r3_size;
603
604 memblock_reserve(r1.base, r1.size);
605 memblock_reserve(r2.base, r2.size);
606
607 allocated_ptr = memblock_alloc(r3_size, SMP_CACHE_BYTES);
608
609 assert(allocated_ptr);
610 assert(rgn->size == r2.size + r3_size);
611 assert(rgn->base == r2.base);
612
613 assert(memblock.reserved.cnt == 2);
614 assert(memblock.reserved.total_size == total_size);
615
616 return 0;
617 }
618
619 /* Test case wrappers */
alloc_simple_check(void)620 static int alloc_simple_check(void)
621 {
622 memblock_set_bottom_up(false);
623 alloc_top_down_simple_check();
624 memblock_set_bottom_up(true);
625 alloc_bottom_up_simple_check();
626
627 return 0;
628 }
629
alloc_disjoint_check(void)630 static int alloc_disjoint_check(void)
631 {
632 memblock_set_bottom_up(false);
633 alloc_top_down_disjoint_check();
634 memblock_set_bottom_up(true);
635 alloc_bottom_up_disjoint_check();
636
637 return 0;
638 }
639
alloc_before_check(void)640 static int alloc_before_check(void)
641 {
642 memblock_set_bottom_up(false);
643 alloc_top_down_before_check();
644 memblock_set_bottom_up(true);
645 alloc_bottom_up_before_check();
646
647 return 0;
648 }
649
alloc_after_check(void)650 static int alloc_after_check(void)
651 {
652 memblock_set_bottom_up(false);
653 alloc_top_down_after_check();
654 memblock_set_bottom_up(true);
655 alloc_bottom_up_after_check();
656
657 return 0;
658 }
659
alloc_in_between_check(void)660 static int alloc_in_between_check(void)
661 {
662 memblock_set_bottom_up(false);
663 alloc_in_between_generic_check();
664 memblock_set_bottom_up(true);
665 alloc_in_between_generic_check();
666
667 return 0;
668 }
669
alloc_second_fit_check(void)670 static int alloc_second_fit_check(void)
671 {
672 memblock_set_bottom_up(false);
673 alloc_top_down_second_fit_check();
674 memblock_set_bottom_up(true);
675 alloc_bottom_up_second_fit_check();
676
677 return 0;
678 }
679
alloc_small_gaps_check(void)680 static int alloc_small_gaps_check(void)
681 {
682 memblock_set_bottom_up(false);
683 alloc_small_gaps_generic_check();
684 memblock_set_bottom_up(true);
685 alloc_small_gaps_generic_check();
686
687 return 0;
688 }
689
alloc_all_reserved_check(void)690 static int alloc_all_reserved_check(void)
691 {
692 memblock_set_bottom_up(false);
693 alloc_all_reserved_generic_check();
694 memblock_set_bottom_up(true);
695 alloc_all_reserved_generic_check();
696
697 return 0;
698 }
699
alloc_no_space_check(void)700 static int alloc_no_space_check(void)
701 {
702 memblock_set_bottom_up(false);
703 alloc_no_space_generic_check();
704 memblock_set_bottom_up(true);
705 alloc_no_space_generic_check();
706
707 return 0;
708 }
709
alloc_limited_space_check(void)710 static int alloc_limited_space_check(void)
711 {
712 memblock_set_bottom_up(false);
713 alloc_limited_space_generic_check();
714 memblock_set_bottom_up(true);
715 alloc_limited_space_generic_check();
716
717 return 0;
718 }
719
alloc_no_memory_check(void)720 static int alloc_no_memory_check(void)
721 {
722 memblock_set_bottom_up(false);
723 alloc_no_memory_generic_check();
724 memblock_set_bottom_up(true);
725 alloc_no_memory_generic_check();
726
727 return 0;
728 }
729
memblock_alloc_checks(void)730 int memblock_alloc_checks(void)
731 {
732 reset_memblock_attributes();
733 dummy_physical_memory_init();
734
735 alloc_simple_check();
736 alloc_disjoint_check();
737 alloc_before_check();
738 alloc_after_check();
739 alloc_second_fit_check();
740 alloc_small_gaps_check();
741 alloc_in_between_check();
742 alloc_all_reserved_check();
743 alloc_no_space_check();
744 alloc_limited_space_check();
745 alloc_no_memory_check();
746
747 dummy_physical_memory_cleanup();
748
749 return 0;
750 }
751