// SPDX-License-Identifier: MIT/* * Copyright © 2019 Intel Corporation * Copyright © 2022 Maíra Canal <mairacanal@riseup.net> */ #include <kunit/test.h> #include <linux/prime_numbers.h>#include <linux/sched/signal.h>#include <linux/sizes.h> #include <linux/gpu_buddy.h> #include "gpu_random.h" static unsigned int random_seed; static inline u64 get_size(int order, u64 chunk_size){	return (1 << order) * chunk_size;} static void gpu_test_buddy_subtree_offset_alignment_stress(struct kunit *test){	struct gpu_buddy_block *block;	struct rb_node *node = NULL;	const u64 mm_size = SZ_2M;	const u64 alignments[] = {		SZ_1M,		SZ_512K,		SZ_256K,		SZ_128K,		SZ_64K,		SZ_32K,		SZ_16K,		SZ_8K,	};	struct list_head allocated[ARRAY_SIZE(alignments)];	unsigned int i, max_subtree_align = 0;	int ret, tree, order;	struct gpu_buddy mm; 	KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, SZ_4K),			       "buddy_init failed\n"); 	for (i = 0; i < ARRAY_SIZE(allocated); i++)		INIT_LIST_HEAD(&allocated[i]); 	/*	 * Exercise subtree_max_alignment tracking by allocating blocks with descending	 * alignment constraints and freeing them in reverse order. This verifies that	 * free-tree augmentation correctly propagates the maximum offset alignment	 * present in each subtree at every stage.	 */ 	for (i = 0; i < ARRAY_SIZE(alignments); i++) {		struct gpu_buddy_block *root = NULL;		unsigned int expected;		u64 align; 		align = alignments[i];		expected = ilog2(align) - 1; 		for (;;) {			ret = gpu_buddy_alloc_blocks(&mm,						     0, mm_size,						     SZ_4K, align,						     &allocated[i],						     0);			if (ret)				break; 			block = list_last_entry(&allocated[i],						struct gpu_buddy_block,						link);			KUNIT_EXPECT_TRUE(test, IS_ALIGNED(gpu_buddy_block_offset(block), align));		} 		for (order = mm.max_order; order >= 0 && !root; order--) {			for (tree = 0; tree < 2; tree++) {				node = mm.free_trees[tree][order].rb_node;				if (node) {					root = container_of(node,							    struct gpu_buddy_block,							    rb);					break;				}			}		} 		KUNIT_ASSERT_NOT_NULL(test, root);		KUNIT_EXPECT_EQ(test, root->subtree_max_alignment, expected);	} 	for (i = ARRAY_SIZE(alignments); i-- > 0; ) {		gpu_buddy_free_list(&mm, &allocated[i], 0); 		for (order = 0; order <= mm.max_order; order++) {			for (tree = 0; tree < 2; tree++) {				node = mm.free_trees[tree][order].rb_node;				if (!node)					continue; 				block = container_of(node, struct gpu_buddy_block, rb);				max_subtree_align = max(max_subtree_align,							block->subtree_max_alignment);			}		} 		KUNIT_EXPECT_GE(test, max_subtree_align, ilog2(alignments[i]));	} 	gpu_buddy_fini(&mm);} static void gpu_test_buddy_offset_aligned_allocation(struct kunit *test){	struct gpu_buddy_block *block, *tmp;	int num_blocks, i, count = 0;	LIST_HEAD(allocated);	struct gpu_buddy mm;	u64 mm_size = SZ_4M;	LIST_HEAD(freed); 	KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, SZ_4K),			       "buddy_init failed\n"); 	num_blocks = mm_size / SZ_256K;	/*	 * Allocate multiple sizes under a fixed offset alignment.	 * Ensures alignment handling is independent of allocation size and	 * exercises subtree max-alignment pruning for small requests.	 */	for (i = 0; i < num_blocks; i++)		KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_8K, SZ_256K,								    &allocated, 0),					"buddy_alloc hit an error size=%u\n", SZ_8K); 	list_for_each_entry(block, &allocated, link) {		/* Ensure the allocated block uses the expected 8 KB size */		KUNIT_EXPECT_EQ(test, gpu_buddy_block_size(&mm, block), SZ_8K);		/* Ensure the block starts at a 256 KB-aligned offset for proper alignment */		KUNIT_EXPECT_TRUE(test, IS_ALIGNED(gpu_buddy_block_offset(block), SZ_256K));	}	gpu_buddy_free_list(&mm, &allocated, 0); 	for (i = 0; i < num_blocks; i++)		KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_16K, SZ_256K,								    &allocated, 0),					"buddy_alloc hit an error size=%u\n", SZ_16K); 	list_for_each_entry(block, &allocated, link) {		/* Ensure the allocated block uses the expected 16 KB size */		KUNIT_EXPECT_EQ(test, gpu_buddy_block_size(&mm, block), SZ_16K);		/* Ensure the block starts at a 256 KB-aligned offset for proper alignment */		KUNIT_EXPECT_TRUE(test, IS_ALIGNED(gpu_buddy_block_offset(block), SZ_256K));	} 	/*	 * Free alternating aligned blocks to introduce fragmentation.	 * Ensures offset-aligned allocations remain valid after frees and	 * verifies subtree max-alignment metadata is correctly maintained.	 */	list_for_each_entry_safe(block, tmp, &allocated, link) {		if (count % 2 == 0)			list_move_tail(&block->link, &freed);		count++;	}	gpu_buddy_free_list(&mm, &freed, 0); 	for (i = 0; i < num_blocks / 2; i++)		KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_16K, SZ_256K,								    &allocated, 0),					"buddy_alloc hit an error size=%u\n", SZ_16K); 	/*	 * Allocate with offset alignment after all slots are used; must fail.	 * Confirms that no aligned offsets remain.	 */	KUNIT_ASSERT_TRUE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_16K, SZ_256K,							   &allocated, 0),			       "buddy_alloc hit an error size=%u\n", SZ_16K);	gpu_buddy_free_list(&mm, &allocated, 0);	gpu_buddy_fini(&mm);} static void gpu_test_buddy_fragmentation_performance(struct kunit *test){	struct gpu_buddy_block *block, *tmp;	int num_blocks, i, ret, count = 0;	LIST_HEAD(allocated_blocks);	unsigned long elapsed_ms;	LIST_HEAD(reverse_list);	LIST_HEAD(test_blocks);	LIST_HEAD(clear_list);	LIST_HEAD(dirty_list);	LIST_HEAD(free_list);	struct gpu_buddy mm;	u64 mm_size = SZ_4G;	ktime_t start, end; 	/*	 * Allocation under severe fragmentation	 *	 * Create severe fragmentation by allocating the entire 4 GiB address space	 * as tiny 8 KiB blocks but forcing a 64 KiB alignment. The resulting pattern	 * leaves many scattered holes. Split the allocations into two groups and	 * return them with different flags to block coalescing, then repeatedly	 * allocate and free 64 KiB blocks while timing the loop. This stresses how	 * quickly the allocator can satisfy larger, aligned requests from a pool of	 * highly fragmented space.	 */	KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, SZ_4K),			       "buddy_init failed\n"); 	num_blocks = mm_size / SZ_64K; 	start = ktime_get();	/* Allocate with maximum fragmentation - 8K blocks with 64K alignment */	for (i = 0; i < num_blocks; i++)		KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_8K, SZ_64K,								    &allocated_blocks, 0),					"buddy_alloc hit an error size=%u\n", SZ_8K); 	list_for_each_entry_safe(block, tmp, &allocated_blocks, link) {		if (count % 4 == 0 || count % 4 == 3)			list_move_tail(&block->link, &clear_list);		else			list_move_tail(&block->link, &dirty_list);		count++;	} 	/* Free with different flags to ensure no coalescing */	gpu_buddy_free_list(&mm, &clear_list, GPU_BUDDY_CLEARED);	gpu_buddy_free_list(&mm, &dirty_list, 0); 	for (i = 0; i < num_blocks; i++)		KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_64K, SZ_64K,								    &test_blocks, 0),					"buddy_alloc hit an error size=%u\n", SZ_64K);	gpu_buddy_free_list(&mm, &test_blocks, 0); 	end = ktime_get();	elapsed_ms = ktime_to_ms(ktime_sub(end, start)); 	kunit_info(test, "Fragmented allocation took %lu ms\n", elapsed_ms); 	gpu_buddy_fini(&mm); 	/*	 * Reverse free order under fragmentation	 *	 * Construct a fragmented 4 GiB space by allocating every 8 KiB block with	 * 64 KiB alignment, creating a dense scatter of small regions. Half of the	 * blocks are selectively freed to form sparse gaps, while the remaining	 * allocations are preserved, reordered in reverse, and released back with	 * the cleared flag. This models a pathological reverse-ordered free pattern	 * and measures how quickly the allocator can merge and reclaim space when	 * deallocation occurs in the opposite order of allocation, exposing the	 * cost difference between a linear freelist scan and an ordered tree lookup.	 */	ret = gpu_buddy_init(&mm, mm_size, SZ_4K);	KUNIT_ASSERT_EQ(test, ret, 0); 	start = ktime_get();	/* Allocate maximum fragmentation */	for (i = 0; i < num_blocks; i++)		KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_8K, SZ_64K,								    &allocated_blocks, 0),					"buddy_alloc hit an error size=%u\n", SZ_8K); 	list_for_each_entry_safe(block, tmp, &allocated_blocks, link) {		if (count % 2 == 0)			list_move_tail(&block->link, &free_list);		count++;	}	gpu_buddy_free_list(&mm, &free_list, GPU_BUDDY_CLEARED); 	list_for_each_entry_safe_reverse(block, tmp, &allocated_blocks, link)		list_move(&block->link, &reverse_list);	gpu_buddy_free_list(&mm, &reverse_list, GPU_BUDDY_CLEARED); 	end = ktime_get();	elapsed_ms = ktime_to_ms(ktime_sub(end, start)); 	kunit_info(test, "Reverse-ordered free took %lu ms\n", elapsed_ms); 	gpu_buddy_fini(&mm);} static void gpu_test_buddy_alloc_range_bias(struct kunit *test){	u32 mm_size, size, ps, bias_size, bias_start, bias_end, bias_rem;	GPU_RND_STATE(prng, random_seed);	unsigned int i, count, *order;	struct gpu_buddy_block *block;	unsigned long flags;	struct gpu_buddy mm;	LIST_HEAD(allocated); 	bias_size = SZ_1M;	ps = roundup_pow_of_two(prandom_u32_state(&prng) % bias_size);	ps = max(SZ_4K, ps);	mm_size = (SZ_8M-1) & ~(ps-1); /* Multiple roots */ 	kunit_info(test, "mm_size=%u, ps=%u\n", mm_size, ps); 	KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, ps),			       "buddy_init failed\n"); 	count = mm_size / bias_size;	order = gpu_random_order(count, &prng);	KUNIT_EXPECT_TRUE(test, order); 	/*	 * Idea is to split the address space into uniform bias ranges, and then	 * in some random order allocate within each bias, using various	 * patterns within. This should detect if allocations leak out from a	 * given bias, for example.	 */ 	for (i = 0; i < count; i++) {		LIST_HEAD(tmp);		u32 size; 		bias_start = order[i] * bias_size;		bias_end = bias_start + bias_size;		bias_rem = bias_size; 		/* internal round_up too big */		KUNIT_ASSERT_TRUE_MSG(test,				      gpu_buddy_alloc_blocks(&mm, bias_start,							     bias_end, bias_size + ps, bias_size,							     &allocated,							     GPU_BUDDY_RANGE_ALLOCATION),				      "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n",				      bias_start, bias_end, bias_size, bias_size); 		/* size too big */		KUNIT_ASSERT_TRUE_MSG(test,				      gpu_buddy_alloc_blocks(&mm, bias_start,							     bias_end, bias_size + ps, ps,							     &allocated,							     GPU_BUDDY_RANGE_ALLOCATION),				      "buddy_alloc didn't fail with bias(%x-%x), size=%u, ps=%u\n",				      bias_start, bias_end, bias_size + ps, ps); 		/* bias range too small for size */		KUNIT_ASSERT_TRUE_MSG(test,				      gpu_buddy_alloc_blocks(&mm, bias_start + ps,							     bias_end, bias_size, ps,							     &allocated,							     GPU_BUDDY_RANGE_ALLOCATION),				      "buddy_alloc didn't fail with bias(%x-%x), size=%u, ps=%u\n",				      bias_start + ps, bias_end, bias_size, ps); 		/* bias misaligned */		KUNIT_ASSERT_TRUE_MSG(test,				      gpu_buddy_alloc_blocks(&mm, bias_start + ps,							     bias_end - ps,							     bias_size >> 1, bias_size >> 1,							     &allocated,							     GPU_BUDDY_RANGE_ALLOCATION),				      "buddy_alloc h didn't fail with bias(%x-%x), size=%u, ps=%u\n",				      bias_start + ps, bias_end - ps, bias_size >> 1, bias_size >> 1); 		/* single big page */		KUNIT_ASSERT_FALSE_MSG(test,				       gpu_buddy_alloc_blocks(&mm, bias_start,							      bias_end, bias_size, bias_size,							      &tmp,							      GPU_BUDDY_RANGE_ALLOCATION),				       "buddy_alloc i failed with bias(%x-%x), size=%u, ps=%u\n",				       bias_start, bias_end, bias_size, bias_size);		gpu_buddy_free_list(&mm, &tmp, 0); 		/* single page with internal round_up */		KUNIT_ASSERT_FALSE_MSG(test,				       gpu_buddy_alloc_blocks(&mm, bias_start,							      bias_end, ps, bias_size,							      &tmp,							      GPU_BUDDY_RANGE_ALLOCATION),				       "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n",				       bias_start, bias_end, ps, bias_size);		gpu_buddy_free_list(&mm, &tmp, 0); 		/* random size within */		size = max(round_up(prandom_u32_state(&prng) % bias_rem, ps), ps);		if (size)			KUNIT_ASSERT_FALSE_MSG(test,					       gpu_buddy_alloc_blocks(&mm, bias_start,								      bias_end, size, ps,								      &tmp,								      GPU_BUDDY_RANGE_ALLOCATION),					       "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n",					       bias_start, bias_end, size, ps); 		bias_rem -= size;		/* too big for current avail */		KUNIT_ASSERT_TRUE_MSG(test,				      gpu_buddy_alloc_blocks(&mm, bias_start,							     bias_end, bias_rem + ps, ps,							     &allocated,							     GPU_BUDDY_RANGE_ALLOCATION),				      "buddy_alloc didn't fail with bias(%x-%x), size=%u, ps=%u\n",				      bias_start, bias_end, bias_rem + ps, ps); 		if (bias_rem) {			/* random fill of the remainder */			size = max(round_up(prandom_u32_state(&prng) % bias_rem, ps), ps);			size = max(size, ps); 			KUNIT_ASSERT_FALSE_MSG(test,					       gpu_buddy_alloc_blocks(&mm, bias_start,								      bias_end, size, ps,								      &allocated,								      GPU_BUDDY_RANGE_ALLOCATION),					       "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n",					       bias_start, bias_end, size, ps);			/*			 * Intentionally allow some space to be left			 * unallocated, and ideally not always on the bias			 * boundaries.			 */			gpu_buddy_free_list(&mm, &tmp, 0);		} else {			list_splice_tail(&tmp, &allocated);		}	} 	kfree(order);	gpu_buddy_free_list(&mm, &allocated, 0);	gpu_buddy_fini(&mm); 	/*	 * Something more free-form. Idea is to pick a random starting bias	 * range within the address space and then start filling it up. Also	 * randomly grow the bias range in both directions as we go along. This	 * should give us bias start/end which is not always uniform like above,	 * and in some cases will require the allocator to jump over already	 * allocated nodes in the middle of the address space.	 */ 	KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, ps),			       "buddy_init failed\n"); 	bias_start = round_up(prandom_u32_state(&prng) % (mm_size - ps), ps);	bias_end = round_up(bias_start + prandom_u32_state(&prng) % (mm_size - bias_start), ps);	bias_end = max(bias_end, bias_start + ps);	bias_rem = bias_end - bias_start; 	do {		u32 size = max(round_up(prandom_u32_state(&prng) % bias_rem, ps), ps); 		KUNIT_ASSERT_FALSE_MSG(test,				       gpu_buddy_alloc_blocks(&mm, bias_start,							      bias_end, size, ps,							      &allocated,							      GPU_BUDDY_RANGE_ALLOCATION),				       "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n",				       bias_start, bias_end, size, ps);		bias_rem -= size; 		/*		 * Try to randomly grow the bias range in both directions, or		 * only one, or perhaps don't grow at all.		 */		do {			u32 old_bias_start = bias_start;			u32 old_bias_end = bias_end; 			if (bias_start)				bias_start -= round_up(prandom_u32_state(&prng) % bias_start, ps);			if (bias_end != mm_size)				bias_end += round_up(prandom_u32_state(&prng) % (mm_size - bias_end), ps); 			bias_rem += old_bias_start - bias_start;			bias_rem += bias_end - old_bias_end;		} while (!bias_rem && (bias_start || bias_end != mm_size));	} while (bias_rem); 	KUNIT_ASSERT_EQ(test, bias_start, 0);	KUNIT_ASSERT_EQ(test, bias_end, mm_size);	KUNIT_ASSERT_TRUE_MSG(test,			      gpu_buddy_alloc_blocks(&mm, bias_start, bias_end,						     ps, ps,						     &allocated,						     GPU_BUDDY_RANGE_ALLOCATION),			      "buddy_alloc passed with bias(%x-%x), size=%u\n",			      bias_start, bias_end, ps); 	gpu_buddy_free_list(&mm, &allocated, 0);	gpu_buddy_fini(&mm); 	/*	 * Allocate cleared blocks in the bias range when the GPU buddy's clear avail is	 * zero. This will validate the bias range allocation in scenarios like system boot	 * when no cleared blocks are available and exercise the fallback path too. The resulting	 * blocks should always be dirty.

Lines 1–500 of 1516. Load more