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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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 int memblock_alloc_checks(void)
415 {
416 	reset_memblock_attributes();
417 	dummy_physical_memory_init();
418 
419 	alloc_top_down_simple_check();
420 	alloc_top_down_disjoint_check();
421 	alloc_top_down_before_check();
422 	alloc_top_down_after_check();
423 	alloc_top_down_second_fit_check();
424 	alloc_in_between_generic_check();
425 	alloc_small_gaps_generic_check();
426 	alloc_all_reserved_generic_check();
427 	alloc_no_space_generic_check();
428 	alloc_limited_space_generic_check();
429 	alloc_no_memory_generic_check();
430 
431 	dummy_physical_memory_cleanup();
432 
433 	return 0;
434 }
435