39 gpu_buddy_block_state(struct gpu_buddy_block *block)  in gpu_buddy_block_state()  argument
41 	return block->header & GPU_BUDDY_HEADER_STATE;  in gpu_buddy_block_state()
45 gpu_buddy_block_is_allocated(struct gpu_buddy_block *block)  in gpu_buddy_block_is_allocated()  argument
47 	return gpu_buddy_block_state(block) == GPU_BUDDY_ALLOCATED;  in gpu_buddy_block_is_allocated()
51 gpu_buddy_block_is_split(struct gpu_buddy_block *block)  in gpu_buddy_block_is_split()  argument
53 	return gpu_buddy_block_state(block) == GPU_BUDDY_SPLIT;  in gpu_buddy_block_is_split()
56 static unsigned int gpu_buddy_block_offset_alignment(struct gpu_buddy_block *block)  in gpu_buddy_block_offset_alignment()  argument
58 	u64 offset = gpu_buddy_block_offset(block);  in gpu_buddy_block_offset_alignment()
80 	struct gpu_buddy_block *block;  in gpu_block_alloc()  local
84 	block = kmem_cache_zalloc(slab_blocks, GFP_KERNEL);  in gpu_block_alloc()
85 	if (!block)  in gpu_block_alloc()
88 	block->header = offset;  in gpu_block_alloc()
89 	block->header |= order;  in gpu_block_alloc()
90 	block->parent = parent;  in gpu_block_alloc()
92 	RB_CLEAR_NODE(&block->rb);  in gpu_block_alloc()
94 	BUG_ON(block->header & GPU_BUDDY_HEADER_UNUSED);  in gpu_block_alloc()
95 	return block;  in gpu_block_alloc()
99 			   struct gpu_buddy_block *block)  in gpu_block_free()  argument
101 	kmem_cache_free(slab_blocks, block);  in gpu_block_free()
105 get_block_tree(struct gpu_buddy_block *block)  in get_block_tree()  argument
107 	return gpu_buddy_block_is_clear(block) ?  in get_block_tree()
129 			  struct gpu_buddy_block *block,  in rbtree_insert()  argument
137 	order = gpu_buddy_block_order(block);  in rbtree_insert()
138 	block_alignment = gpu_buddy_block_offset_alignment(block);  in rbtree_insert()
155 		if (gpu_buddy_block_offset(block) < gpu_buddy_block_offset(node))  in rbtree_insert()
161 	block->subtree_max_alignment = block_alignment;  in rbtree_insert()
162 	rb_link_node(&block->rb, parent, link);  in rbtree_insert()
163 	rb_insert_augmented(&block->rb, root, &gpu_buddy_augment_cb);  in rbtree_insert()
167 			  struct gpu_buddy_block *block)  in rbtree_remove()  argument
169 	unsigned int order = gpu_buddy_block_order(block);  in rbtree_remove()
173 	tree = get_block_tree(block);  in rbtree_remove()
176 	rb_erase_augmented(&block->rb, root, &gpu_buddy_augment_cb);  in rbtree_remove()
177 	RB_CLEAR_NODE(&block->rb);  in rbtree_remove()
180 static void clear_reset(struct gpu_buddy_block *block)  in clear_reset()  argument
182 	block->header &= ~GPU_BUDDY_HEADER_CLEAR;  in clear_reset()
185 static void mark_cleared(struct gpu_buddy_block *block)  in mark_cleared()  argument
187 	block->header |= GPU_BUDDY_HEADER_CLEAR;  in mark_cleared()
191 			   struct gpu_buddy_block *block)  in mark_allocated()  argument
193 	block->header &= ~GPU_BUDDY_HEADER_STATE;  in mark_allocated()
194 	block->header |= GPU_BUDDY_ALLOCATED;  in mark_allocated()
196 	mm->free_scoreboard[gpu_buddy_block_order(block)]--;  in mark_allocated()
197 	mm->used_scoreboard[gpu_buddy_block_order(block)]++;  in mark_allocated()
199 	rbtree_remove(mm, block);  in mark_allocated()
203 		      struct gpu_buddy_block *block)  in mark_free()  argument
207 	if (gpu_buddy_block_is_allocated(block))  in mark_free()
208 		mm->used_scoreboard[gpu_buddy_block_order(block)]--;  in mark_free()
210 	block->header &= ~GPU_BUDDY_HEADER_STATE;  in mark_free()
211 	block->header |= GPU_BUDDY_FREE;  in mark_free()
213 	mm->free_scoreboard[gpu_buddy_block_order(block)]++;  in mark_free()
215 	tree = get_block_tree(block);  in mark_free()
216 	rbtree_insert(mm, block, tree);  in mark_free()
220 		       struct gpu_buddy_block *block)  in mark_split()  argument
222 	block->header &= ~GPU_BUDDY_HEADER_STATE;  in mark_split()
223 	block->header |= GPU_BUDDY_SPLIT;  in mark_split()
225 	mm->free_scoreboard[gpu_buddy_block_order(block)]--;  in mark_split()
227 	rbtree_remove(mm, block);  in mark_split()
241 __get_buddy(struct gpu_buddy_block *block)  in __get_buddy()  argument
245 	parent = block->parent;  in __get_buddy()
249 	if (parent->left == block)  in __get_buddy()
256 				     struct gpu_buddy_block *block,  in __gpu_buddy_free()  argument
262 	while ((parent = block->parent)) {  in __gpu_buddy_free()
265 		buddy = __get_buddy(block);  in __gpu_buddy_free()
275 			if (gpu_buddy_block_is_clear(block) !=  in __gpu_buddy_free()
279 			if (gpu_buddy_block_is_clear(block))  in __gpu_buddy_free()
288 		if (gpu_buddy_block_is_allocated(block))  in __gpu_buddy_free()
289 			mm->used_scoreboard[gpu_buddy_block_order(block)]--;  in __gpu_buddy_free()
291 		gpu_block_free(mm, block);  in __gpu_buddy_free()
294 		block = parent;  in __gpu_buddy_free()
297 	order = gpu_buddy_block_order(block);  in __gpu_buddy_free()
298 	mark_free(mm, block);  in __gpu_buddy_free()
322 				struct gpu_buddy_block *block, *buddy;  in __force_merge()  local
325 				block = rbtree_get_free_block(iter);  in __force_merge()
328 				if (!block || !block->parent)  in __force_merge()
331 				block_start = gpu_buddy_block_offset(block);  in __force_merge()
332 				block_end = block_start + gpu_buddy_block_size(mm, block) - 1;  in __force_merge()
337 				buddy = __get_buddy(block);  in __force_merge()
341 				gpu_buddy_assert(gpu_buddy_block_is_clear(block) !=  in __force_merge()
351 				rbtree_remove(mm, block);  in __force_merge()
352 				mm->free_scoreboard[gpu_buddy_block_order(block)]--;  in __force_merge()
353 				if (gpu_buddy_block_is_clear(block))  in __force_merge()
354 					mm->clear_avail -= gpu_buddy_block_size(mm, block);  in __force_merge()
356 				order = __gpu_buddy_free(mm, block, true);  in __force_merge()
526 		       struct gpu_buddy_block *block)  in split_block()  argument
528 	unsigned int block_order = gpu_buddy_block_order(block) - 1;  in split_block()
529 	u64 offset = gpu_buddy_block_offset(block);  in split_block()
531 	BUG_ON(!gpu_buddy_block_is_free(block));  in split_block()
532 	BUG_ON(!gpu_buddy_block_order(block));  in split_block()
534 	block->left = gpu_block_alloc(mm, block, block_order, offset);  in split_block()
535 	if (!block->left)  in split_block()
538 	block->right = gpu_block_alloc(mm, block, block_order,  in split_block()
540 	if (!block->right) {  in split_block()
541 		gpu_block_free(mm, block->left);  in split_block()
545 	mark_split(mm, block);  in split_block()
547 	if (gpu_buddy_block_is_clear(block)) {  in split_block()
548 		mark_cleared(block->left);  in split_block()
549 		mark_cleared(block->right);  in split_block()
550 		clear_reset(block);  in split_block()
553 	mark_free(mm, block->left);  in split_block()
554 	mark_free(mm, block->right);  in split_block()
591 		struct gpu_buddy_block *block, *tmp;  in gpu_buddy_reset_clear()  local
593 		rbtree_postorder_for_each_entry_safe(block, tmp, root, rb) {  in gpu_buddy_reset_clear()
594 			rbtree_remove(mm, block);  in gpu_buddy_reset_clear()
596 				mark_cleared(block);  in gpu_buddy_reset_clear()
597 				mm->clear_avail += gpu_buddy_block_size(mm, block);  in gpu_buddy_reset_clear()
599 				clear_reset(block);  in gpu_buddy_reset_clear()
600 				mm->clear_avail -= gpu_buddy_block_size(mm, block);  in gpu_buddy_reset_clear()
603 			rbtree_insert(mm, block, dst_tree);  in gpu_buddy_reset_clear()
616 			  struct gpu_buddy_block *block)  in gpu_buddy_free_block()  argument
619 	BUG_ON(!gpu_buddy_block_is_allocated(block));  in gpu_buddy_free_block()
620 	mm->avail += gpu_buddy_block_size(mm, block);  in gpu_buddy_free_block()
621 	if (gpu_buddy_block_is_clear(block))  in gpu_buddy_free_block()
622 		mm->clear_avail += gpu_buddy_block_size(mm, block);  in gpu_buddy_free_block()
624 	__gpu_buddy_free(mm, block, false);  in gpu_buddy_free_block()
639 	struct gpu_buddy_block *block;  in gpu_buddy_allocated_addr_to_block()  local
654 		block = list_first_entry_or_null(&dfs,  in gpu_buddy_allocated_addr_to_block()
657 		if (!block)  in gpu_buddy_allocated_addr_to_block()
660 		list_del(&block->tmp_link);  in gpu_buddy_allocated_addr_to_block()
662 		block_start = gpu_buddy_block_offset(block);  in gpu_buddy_allocated_addr_to_block()
663 		block_end = block_start + gpu_buddy_block_size(mm, block) - 1;  in gpu_buddy_allocated_addr_to_block()
668 		if (gpu_buddy_block_is_allocated(block))  in gpu_buddy_allocated_addr_to_block()
669 			return block;  in gpu_buddy_allocated_addr_to_block()
670 		else if (gpu_buddy_block_is_free(block))  in gpu_buddy_allocated_addr_to_block()
673 		list_add(&block->right->tmp_link, &dfs);  in gpu_buddy_allocated_addr_to_block()
674 		list_add(&block->left->tmp_link, &dfs);  in gpu_buddy_allocated_addr_to_block()
686 	struct gpu_buddy_block *block, *on;  in __gpu_buddy_free_list()  local
690 	list_for_each_entry_safe(block, on, objects, link) {  in __gpu_buddy_free_list()
692 			mark_cleared(block);  in __gpu_buddy_free_list()
694 			clear_reset(block);  in __gpu_buddy_free_list()
695 		gpu_buddy_free_block(mm, block);  in __gpu_buddy_free_list()
730 static bool block_incompatible(struct gpu_buddy_block *block, unsigned int flags)  in block_incompatible()  argument
734 	return needs_clear != gpu_buddy_block_is_clear(block);  in block_incompatible()
738 				    struct gpu_buddy_block *block)  in __gpu_buddy_undo_splits()  argument
740 	struct gpu_buddy_block *buddy = __get_buddy(block);  in __gpu_buddy_undo_splits()
743 	    (gpu_buddy_block_is_free(block) &&  in __gpu_buddy_undo_splits()
745 		rbtree_remove(mm, block);  in __gpu_buddy_undo_splits()
746 		mm->free_scoreboard[gpu_buddy_block_order(block)]--;  in __gpu_buddy_undo_splits()
747 		__gpu_buddy_free(mm, block, false);  in __gpu_buddy_undo_splits()
759 	struct gpu_buddy_block *block;  in __alloc_range_bias()  local
773 		block = list_first_entry_or_null(&dfs,  in __alloc_range_bias()
776 		if (!block)  in __alloc_range_bias()
779 		list_del(&block->tmp_link);  in __alloc_range_bias()
781 		if (gpu_buddy_block_order(block) < order)  in __alloc_range_bias()
784 		block_start = gpu_buddy_block_offset(block);  in __alloc_range_bias()
785 		block_end = block_start + gpu_buddy_block_size(mm, block) - 1;  in __alloc_range_bias()
790 		if (gpu_buddy_block_is_allocated(block))  in __alloc_range_bias()
802 		if (!fallback && block_incompatible(block, flags))  in __alloc_range_bias()
806 		    order == gpu_buddy_block_order(block)) {  in __alloc_range_bias()
810 			if (gpu_buddy_block_is_free(block))  in __alloc_range_bias()
811 				return block;  in __alloc_range_bias()
816 		if (!gpu_buddy_block_is_split(block)) {  in __alloc_range_bias()
817 			err = split_block(mm, block);  in __alloc_range_bias()
822 		list_add(&block->right->tmp_link, &dfs);  in __alloc_range_bias()
823 		list_add(&block->left->tmp_link, &dfs);  in __alloc_range_bias()
834 	__gpu_buddy_undo_splits(mm, block);  in __alloc_range_bias()
844 	struct gpu_buddy_block *block;  in __gpu_buddy_alloc_range_bias()  local
847 	block = __alloc_range_bias(mm, start, end, order,  in __gpu_buddy_alloc_range_bias()
849 	if (IS_ERR(block))  in __gpu_buddy_alloc_range_bias()
853 	return block;  in __gpu_buddy_alloc_range_bias()
861 	struct gpu_buddy_block *max_block = NULL, *block = NULL;  in get_maxblock()  local
867 		block = rbtree_last_free_block(root);  in get_maxblock()
868 		if (!block)  in get_maxblock()
872 			max_block = block;  in get_maxblock()
876 		if (gpu_buddy_block_offset(block) >  in get_maxblock()
878 			max_block = block;  in get_maxblock()
890 	struct gpu_buddy_block *block = NULL;  in alloc_from_freetree()  local
900 		block = get_maxblock(mm, order, tree);  in alloc_from_freetree()
901 		if (block)  in alloc_from_freetree()
903 			tmp = gpu_buddy_block_order(block);  in alloc_from_freetree()
908 			block = rbtree_last_free_block(root);  in alloc_from_freetree()
909 			if (block)  in alloc_from_freetree()
914 	if (!block) {  in alloc_from_freetree()
921 			block = rbtree_last_free_block(root);  in alloc_from_freetree()
922 			if (block)  in alloc_from_freetree()
926 		if (!block)  in alloc_from_freetree()
930 	BUG_ON(!gpu_buddy_block_is_free(block));  in alloc_from_freetree()
933 		err = split_block(mm, block);  in alloc_from_freetree()
937 		block = block->right;  in alloc_from_freetree()
940 	return block;  in alloc_from_freetree()
943 	__gpu_buddy_undo_splits(mm, block);  in alloc_from_freetree()
956 	struct gpu_buddy_block *block;  in gpu_buddy_subtree_can_satisfy()  local
958 	block = rbtree_get_free_block(node);  in gpu_buddy_subtree_can_satisfy()
959 	return block->subtree_max_alignment >= alignment;  in gpu_buddy_subtree_can_satisfy()
973 		struct gpu_buddy_block *block = rbtree_get_free_block(rb);  in gpu_buddy_find_block_aligned()  local
983 		if (gpu_buddy_block_offset_alignment(block) >= alignment)  in gpu_buddy_find_block_aligned()
984 			return block;  in gpu_buddy_find_block_aligned()
1005 	struct gpu_buddy_block *block = NULL;  in gpu_buddy_offset_aligned_allocation()  local
1019 		block = gpu_buddy_find_block_aligned(mm, tree, tmp,  in gpu_buddy_offset_aligned_allocation()
1021 		if (!block) {  in gpu_buddy_offset_aligned_allocation()
1024 			block = gpu_buddy_find_block_aligned(mm, tree, tmp,  in gpu_buddy_offset_aligned_allocation()
1028 		if (block)  in gpu_buddy_offset_aligned_allocation()
1032 	if (!block)  in gpu_buddy_offset_aligned_allocation()
1035 	while (gpu_buddy_block_order(block) > order) {  in gpu_buddy_offset_aligned_allocation()
1038 		err = split_block(mm, block);  in gpu_buddy_offset_aligned_allocation()
1042 		left  = block->left;  in gpu_buddy_offset_aligned_allocation()
1043 		right = block->right;  in gpu_buddy_offset_aligned_allocation()
1046 			block = right;  in gpu_buddy_offset_aligned_allocation()
1048 			block = left;  in gpu_buddy_offset_aligned_allocation()
1051 	return block;  in gpu_buddy_offset_aligned_allocation()
1059 	__gpu_buddy_undo_splits(mm, block);  in gpu_buddy_offset_aligned_allocation()
1069 	struct gpu_buddy_block *block;  in __alloc_range()  local
1081 		block = list_first_entry_or_null(dfs,  in __alloc_range()
1084 		if (!block)  in __alloc_range()
1087 		list_del(&block->tmp_link);  in __alloc_range()
1089 		block_start = gpu_buddy_block_offset(block);  in __alloc_range()
1090 		block_end = block_start + gpu_buddy_block_size(mm, block) - 1;  in __alloc_range()
1095 		if (gpu_buddy_block_is_allocated(block)) {  in __alloc_range()
1101 			if (gpu_buddy_block_is_free(block)) {  in __alloc_range()
1102 				mark_allocated(mm, block);  in __alloc_range()
1103 				total_allocated += gpu_buddy_block_size(mm, block);  in __alloc_range()
1104 				mm->avail -= gpu_buddy_block_size(mm, block);  in __alloc_range()
1105 				if (gpu_buddy_block_is_clear(block))  in __alloc_range()
1106 					mm->clear_avail -= gpu_buddy_block_size(mm, block);  in __alloc_range()
1107 				list_add_tail(&block->link, &allocated);  in __alloc_range()
1115 		if (!gpu_buddy_block_is_split(block)) {  in __alloc_range()
1116 			err = split_block(mm, block);  in __alloc_range()
1121 		list_add(&block->right->tmp_link, dfs);  in __alloc_range()
1122 		list_add(&block->left->tmp_link, dfs);  in __alloc_range()
1140 	__gpu_buddy_undo_splits(mm, block);  in __alloc_range()
1186 	struct gpu_buddy_block *block;  in __alloc_contig_try_harder()  local
1206 			block = rbtree_get_free_block(iter);  in __alloc_contig_try_harder()
1208 			rhs_offset = gpu_buddy_block_offset(block);  in __alloc_contig_try_harder()
1282 	struct gpu_buddy_block *block;  in gpu_buddy_block_trim()  local
1293 	block = list_first_entry(blocks,  in gpu_buddy_block_trim()
1297 	block_start = gpu_buddy_block_offset(block);  in gpu_buddy_block_trim()
1298 	block_end = block_start + gpu_buddy_block_size(mm, block);  in gpu_buddy_block_trim()
1300 	if (WARN_ON(!gpu_buddy_block_is_allocated(block)))  in gpu_buddy_block_trim()
1303 	if (new_size > gpu_buddy_block_size(mm, block))  in gpu_buddy_block_trim()
1309 	if (new_size == gpu_buddy_block_size(mm, block))  in gpu_buddy_block_trim()
1326 	list_del(&block->link);  in gpu_buddy_block_trim()
1327 	mark_free(mm, block);  in gpu_buddy_block_trim()
1328 	mm->avail += gpu_buddy_block_size(mm, block);  in gpu_buddy_block_trim()
1329 	if (gpu_buddy_block_is_clear(block))  in gpu_buddy_block_trim()
1330 		mm->clear_avail += gpu_buddy_block_size(mm, block);  in gpu_buddy_block_trim()
1333 	parent = block->parent;  in gpu_buddy_block_trim()
1334 	block->parent = NULL;  in gpu_buddy_block_trim()
1336 	list_add(&block->tmp_link, &dfs);  in gpu_buddy_block_trim()
1339 		mark_allocated(mm, block);  in gpu_buddy_block_trim()
1340 		mm->avail -= gpu_buddy_block_size(mm, block);  in gpu_buddy_block_trim()
1341 		if (gpu_buddy_block_is_clear(block))  in gpu_buddy_block_trim()
1342 			mm->clear_avail -= gpu_buddy_block_size(mm, block);  in gpu_buddy_block_trim()
1343 		list_add(&block->link, blocks);  in gpu_buddy_block_trim()
1346 	block->parent = parent;  in gpu_buddy_block_trim()
1398 	struct gpu_buddy_block *block = NULL;  in gpu_buddy_alloc_blocks()  local
1473 			block = __gpu_buddy_alloc_blocks(mm, start,  in gpu_buddy_alloc_blocks()
1479 			if (!IS_ERR(block))  in gpu_buddy_alloc_blocks()
1494 				block = __gpu_buddy_alloc_blocks(mm, start,  in gpu_buddy_alloc_blocks()
1500 				if (!IS_ERR(block)) {  in gpu_buddy_alloc_blocks()
1520 		mark_allocated(mm, block);  in gpu_buddy_alloc_blocks()
1521 		mm->avail -= gpu_buddy_block_size(mm, block);  in gpu_buddy_alloc_blocks()
1522 		if (gpu_buddy_block_is_clear(block))  in gpu_buddy_alloc_blocks()
1523 			mm->clear_avail -= gpu_buddy_block_size(mm, block);  in gpu_buddy_alloc_blocks()
1524 		kmemleak_update_trace(block);  in gpu_buddy_alloc_blocks()
1525 		list_add_tail(&block->link, &allocated);  in gpu_buddy_alloc_blocks()
1544 			block = list_last_entry(&allocated, typeof(*block), link);  in gpu_buddy_alloc_blocks()
1545 			list_move(&block->link, &temp);  in gpu_buddy_alloc_blocks()
1547 			trim_size = gpu_buddy_block_size(mm, block) -  in gpu_buddy_alloc_blocks()
1576 			   struct gpu_buddy_block *block)  in gpu_buddy_block_print()  argument
1578 	u64 start = gpu_buddy_block_offset(block);  in gpu_buddy_block_print()
1579 	u64 size = gpu_buddy_block_size(mm, block);  in gpu_buddy_block_print()