75 static struct gpu_buddy_block *gpu_block_alloc(struct gpu_buddy *mm,  in gpu_block_alloc()  argument
98 static void gpu_block_free(struct gpu_buddy *mm,  in gpu_block_free()  argument
128 static void rbtree_insert(struct gpu_buddy *mm,  in rbtree_insert()  argument
140 	root = &mm->free_trees[tree][order];  in rbtree_insert()
166 static void rbtree_remove(struct gpu_buddy *mm,  in rbtree_remove()  argument
174 	root = &mm->free_trees[tree][order];  in rbtree_remove()
190 static void mark_allocated(struct gpu_buddy *mm,  in mark_allocated()  argument
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()
202 static void mark_free(struct gpu_buddy *mm,  in mark_free()  argument
208 		mm->used_scoreboard[gpu_buddy_block_order(block)]--;  in mark_free()
213 	mm->free_scoreboard[gpu_buddy_block_order(block)]++;  in mark_free()
216 	rbtree_insert(mm, block, tree);  in mark_free()
219 static void mark_split(struct gpu_buddy *mm,  in mark_split()  argument
225 	mm->free_scoreboard[gpu_buddy_block_order(block)]--;  in mark_split()
227 	rbtree_remove(mm, block);  in mark_split()
255 static unsigned int __gpu_buddy_free(struct gpu_buddy *mm,  in __gpu_buddy_free()  argument
283 		rbtree_remove(mm, buddy);  in __gpu_buddy_free()
284 		mm->free_scoreboard[gpu_buddy_block_order(buddy)]--;  in __gpu_buddy_free()
286 			mm->clear_avail -= gpu_buddy_block_size(mm, buddy);  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()
292 		gpu_block_free(mm, buddy);  in __gpu_buddy_free()
298 	mark_free(mm, block);  in __gpu_buddy_free()
303 static int __force_merge(struct gpu_buddy *mm,  in __force_merge()  argument
314 	if (min_order > mm->max_order)  in __force_merge()
319 			struct rb_node *iter = rb_last(&mm->free_trees[tree][i]);  in __force_merge()
332 				block_end = block_start + gpu_buddy_block_size(mm, block) - 1;  in __force_merge()
351 				rbtree_remove(mm, block);  in __force_merge()
352 				mm->free_scoreboard[gpu_buddy_block_order(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()
378 int gpu_buddy_init(struct gpu_buddy *mm, u64 size, u64 chunk_size)  in gpu_buddy_init()  argument
394 	mm->size = size;  in gpu_buddy_init()
395 	mm->avail = size;  in gpu_buddy_init()
396 	mm->clear_avail = 0;  in gpu_buddy_init()
397 	mm->chunk_size = chunk_size;  in gpu_buddy_init()
398 	mm->max_order = ilog2(size) - ilog2(chunk_size);  in gpu_buddy_init()
400 	BUG_ON(mm->max_order > GPU_BUDDY_MAX_ORDER);  in gpu_buddy_init()
402 	mm->free_scoreboard = kcalloc(mm->max_order + 1,  in gpu_buddy_init()
403 				      sizeof(*mm->free_scoreboard),  in gpu_buddy_init()
405 	if (!mm->free_scoreboard)  in gpu_buddy_init()
408 	mm->used_scoreboard = kcalloc(mm->max_order + 1,  in gpu_buddy_init()
409 				      sizeof(*mm->used_scoreboard),  in gpu_buddy_init()
411 	if (!mm->used_scoreboard)  in gpu_buddy_init()
414 	mm->free_trees = kmalloc_objs(*mm->free_trees, GPU_BUDDY_MAX_FREE_TREES);  in gpu_buddy_init()
415 	if (!mm->free_trees)  in gpu_buddy_init()
419 		mm->free_trees[i] = kmalloc_objs(struct rb_root,  in gpu_buddy_init()
420 						 mm->max_order + 1);  in gpu_buddy_init()
421 		if (!mm->free_trees[i])  in gpu_buddy_init()
424 		for (j = 0; j <= mm->max_order; ++j)  in gpu_buddy_init()
425 			mm->free_trees[i][j] = RB_ROOT;  in gpu_buddy_init()
428 	mm->n_roots = hweight64(size);  in gpu_buddy_init()
430 	mm->roots = kmalloc_objs(struct gpu_buddy_block *, mm->n_roots);  in gpu_buddy_init()
431 	if (!mm->roots)  in gpu_buddy_init()
446 		root = gpu_block_alloc(mm, NULL, order, offset);  in gpu_buddy_init()
450 		mark_free(mm, root);  in gpu_buddy_init()
452 		BUG_ON(root_count > mm->max_order);  in gpu_buddy_init()
453 		BUG_ON(gpu_buddy_block_size(mm, root) < chunk_size);  in gpu_buddy_init()
455 		mm->roots[root_count] = root;  in gpu_buddy_init()
463 	mm->lock_dep_map = NULL;  in gpu_buddy_init()
469 		gpu_block_free(mm, mm->roots[root_count]);  in gpu_buddy_init()
470 	kfree(mm->roots);  in gpu_buddy_init()
473 		kfree(mm->free_trees[i]);  in gpu_buddy_init()
474 	kfree(mm->free_trees);  in gpu_buddy_init()
476 	kfree(mm->used_scoreboard);  in gpu_buddy_init()
478 	kfree(mm->free_scoreboard);  in gpu_buddy_init()
490 void gpu_buddy_fini(struct gpu_buddy *mm)  in gpu_buddy_fini()  argument
496 	size = mm->size;  in gpu_buddy_fini()
498 	for (i = 0; i < mm->n_roots; ++i) {  in gpu_buddy_fini()
499 		order = ilog2(size) - ilog2(mm->chunk_size);  in gpu_buddy_fini()
500 		start = gpu_buddy_block_offset(mm->roots[i]);  in gpu_buddy_fini()
501 		__force_merge(mm, start, start + size, order);  in gpu_buddy_fini()
503 		gpu_buddy_assert(gpu_buddy_block_is_free(mm->roots[i]));  in gpu_buddy_fini()
505 		gpu_block_free(mm, mm->roots[i]);  in gpu_buddy_fini()
507 		root_size = mm->chunk_size << order;  in gpu_buddy_fini()
511 	gpu_buddy_assert(mm->avail == mm->size);  in gpu_buddy_fini()
513 	for (i = 0; i <= mm->max_order; ++i)  in gpu_buddy_fini()
514 		gpu_buddy_assert(!mm->used_scoreboard[i]);  in gpu_buddy_fini()
517 		kfree(mm->free_trees[i]);  in gpu_buddy_fini()
518 	kfree(mm->free_trees);  in gpu_buddy_fini()
519 	kfree(mm->roots);  in gpu_buddy_fini()
520 	kfree(mm->free_scoreboard);  in gpu_buddy_fini()
521 	kfree(mm->used_scoreboard);  in gpu_buddy_fini()
525 static int split_block(struct gpu_buddy *mm,  in split_block()  argument
534 	block->left = gpu_block_alloc(mm, block, block_order, offset);  in split_block()
538 	block->right = gpu_block_alloc(mm, block, block_order,  in split_block()
539 				       offset + (mm->chunk_size << block_order));  in split_block()
541 		gpu_block_free(mm, block->left);  in split_block()
545 	mark_split(mm, block);  in split_block()
553 	mark_free(mm, block->left);  in split_block()
554 	mark_free(mm, block->right);  in split_block()
568 void gpu_buddy_reset_clear(struct gpu_buddy *mm, bool is_clear)  in gpu_buddy_reset_clear()  argument
575 	gpu_buddy_driver_lock_held(mm);  in gpu_buddy_reset_clear()
576 	size = mm->size;  in gpu_buddy_reset_clear()
577 	for (i = 0; i < mm->n_roots; ++i) {  in gpu_buddy_reset_clear()
578 		order = ilog2(size) - ilog2(mm->chunk_size);  in gpu_buddy_reset_clear()
579 		start = gpu_buddy_block_offset(mm->roots[i]);  in gpu_buddy_reset_clear()
580 		__force_merge(mm, start, start + size, order);  in gpu_buddy_reset_clear()
582 		root_size = mm->chunk_size << order;  in gpu_buddy_reset_clear()
589 	for (i = 0; i <= mm->max_order; ++i) {  in gpu_buddy_reset_clear()
590 		struct rb_root *root = &mm->free_trees[src_tree][i];  in gpu_buddy_reset_clear()
594 			rbtree_remove(mm, block);  in gpu_buddy_reset_clear()
597 				mm->clear_avail += gpu_buddy_block_size(mm, 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()
615 void gpu_buddy_free_block(struct gpu_buddy *mm,  in gpu_buddy_free_block()  argument
618 	gpu_buddy_driver_lock_held(mm);  in gpu_buddy_free_block()
620 	mm->avail += gpu_buddy_block_size(mm, 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()
637 struct gpu_buddy_block *gpu_buddy_allocated_addr_to_block(struct gpu_buddy *mm, u64 addr)  in gpu_buddy_allocated_addr_to_block()  argument
644 	gpu_buddy_driver_lock_held(mm);  in gpu_buddy_allocated_addr_to_block()
646 	end = addr + mm->chunk_size - 1;  in gpu_buddy_allocated_addr_to_block()
647 	for (i = 0; i < mm->n_roots; ++i)  in gpu_buddy_allocated_addr_to_block()
648 		list_add_tail(&mm->roots[i]->tmp_link, &dfs);  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()
681 static void __gpu_buddy_free_list(struct gpu_buddy *mm,  in __gpu_buddy_free_list()  argument
695 		gpu_buddy_free_block(mm, block);  in __gpu_buddy_free_list()
701 static void gpu_buddy_free_list_internal(struct gpu_buddy *mm,  in gpu_buddy_free_list_internal()  argument
709 	__gpu_buddy_free_list(mm, objects, false, false);  in gpu_buddy_free_list_internal()
719 void gpu_buddy_free_list(struct gpu_buddy *mm,  in gpu_buddy_free_list()  argument
725 	gpu_buddy_driver_lock_held(mm);  in gpu_buddy_free_list()
726 	__gpu_buddy_free_list(mm, objects, mark_clear, !mark_clear);  in gpu_buddy_free_list()
737 static void __gpu_buddy_undo_splits(struct gpu_buddy *mm,  in __gpu_buddy_undo_splits()  argument
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()
752 __alloc_range_bias(struct gpu_buddy *mm,  in __alloc_range_bias()  argument
758 	u64 req_size = mm->chunk_size << order;  in __alloc_range_bias()
766 	for (i = 0; i < mm->n_roots; ++i)  in __alloc_range_bias()
767 		list_add_tail(&mm->roots[i]->tmp_link, &dfs);  in __alloc_range_bias()
785 		block_end = block_start + gpu_buddy_block_size(mm, block) - 1;  in __alloc_range_bias()
817 			err = split_block(mm, block);  in __alloc_range_bias()
834 	__gpu_buddy_undo_splits(mm, block);  in __alloc_range_bias()
839 __gpu_buddy_alloc_range_bias(struct gpu_buddy *mm,  in __gpu_buddy_alloc_range_bias()  argument
847 	block = __alloc_range_bias(mm, start, end, order,  in __gpu_buddy_alloc_range_bias()
850 		return __alloc_range_bias(mm, start, end, order,  in __gpu_buddy_alloc_range_bias()
857 get_maxblock(struct gpu_buddy *mm,  in get_maxblock()  argument
865 	for (i = order; i <= mm->max_order; ++i) {  in get_maxblock()
866 		root = &mm->free_trees[tree][i];  in get_maxblock()
886 alloc_from_freetree(struct gpu_buddy *mm,  in alloc_from_freetree()  argument
900 		block = get_maxblock(mm, order, tree);  in alloc_from_freetree()
905 		for (tmp = order; tmp <= mm->max_order; ++tmp) {  in alloc_from_freetree()
907 			root = &mm->free_trees[tree][tmp];  in alloc_from_freetree()
919 		for (tmp = order; tmp <= mm->max_order; ++tmp) {  in alloc_from_freetree()
920 			root = &mm->free_trees[tree][tmp];  in alloc_from_freetree()
933 		err = split_block(mm, block);  in alloc_from_freetree()
943 	__gpu_buddy_undo_splits(mm, block);  in alloc_from_freetree()
963 gpu_buddy_find_block_aligned(struct gpu_buddy *mm,  in gpu_buddy_find_block_aligned()  argument
969 	struct rb_root *root = &mm->free_trees[tree][order];  in gpu_buddy_find_block_aligned()
1000 gpu_buddy_offset_aligned_allocation(struct gpu_buddy *mm,  in gpu_buddy_offset_aligned_allocation()  argument
1012 	pages = size >> ilog2(mm->chunk_size);  in gpu_buddy_offset_aligned_allocation()
1018 	for (tmp = order; tmp <= mm->max_order; ++tmp) {  in gpu_buddy_offset_aligned_allocation()
1019 		block = gpu_buddy_find_block_aligned(mm, tree, tmp,  in gpu_buddy_offset_aligned_allocation()
1024 			block = gpu_buddy_find_block_aligned(mm, tree, tmp,  in gpu_buddy_offset_aligned_allocation()
1038 		err = split_block(mm, block);  in gpu_buddy_offset_aligned_allocation()
1059 	__gpu_buddy_undo_splits(mm, block);  in gpu_buddy_offset_aligned_allocation()
1063 static int __alloc_range(struct gpu_buddy *mm,  in __alloc_range()  argument
1090 		block_end = block_start + gpu_buddy_block_size(mm, block) - 1;  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()
1106 					mm->clear_avail -= gpu_buddy_block_size(mm, block);  in __alloc_range()
1109 			} else if (!mm->clear_avail) {  in __alloc_range()
1116 			err = split_block(mm, block);  in __alloc_range()
1140 	__gpu_buddy_undo_splits(mm, block);  in __alloc_range()
1147 		gpu_buddy_free_list_internal(mm, &allocated);  in __alloc_range()
1153 static int __gpu_buddy_alloc_range(struct gpu_buddy *mm,  in __gpu_buddy_alloc_range()  argument
1162 	for (i = 0; i < mm->n_roots; ++i)  in __gpu_buddy_alloc_range()
1163 		list_add_tail(&mm->roots[i]->tmp_link, &dfs);  in __gpu_buddy_alloc_range()
1165 	return __alloc_range(mm, &dfs, start, size,  in __gpu_buddy_alloc_range()
1169 static int __alloc_contig_aligned_retry(struct gpu_buddy *mm,  in __alloc_contig_aligned_retry()  argument
1177 	return __gpu_buddy_alloc_range(mm, aligned_offset, size, NULL, blocks);  in __alloc_contig_aligned_retry()
1180 static int __alloc_contig_try_harder(struct gpu_buddy *mm,  in __alloc_contig_try_harder()  argument
1192 	order = ilog2(modify_size) - ilog2(mm->chunk_size);  in __alloc_contig_try_harder()
1200 		root = &mm->free_trees[tree][order];  in __alloc_contig_try_harder()
1211 			err =  __gpu_buddy_alloc_range(mm, rhs_offset, size,  in __alloc_contig_try_harder()
1219 				gpu_buddy_free_list_internal(mm, blocks);  in __alloc_contig_try_harder()
1220 				err = __alloc_contig_aligned_retry(mm, rhs_offset,  in __alloc_contig_try_harder()
1227 					gpu_buddy_free_list_internal(mm, blocks);  in __alloc_contig_try_harder()
1239 			gpu_buddy_free_list_internal(mm, blocks);  in __alloc_contig_try_harder()
1240 			err = __alloc_contig_aligned_retry(mm, lhs_offset, size,  in __alloc_contig_try_harder()
1245 				gpu_buddy_free_list_internal(mm, blocks);  in __alloc_contig_try_harder()
1249 			gpu_buddy_free_list_internal(mm, blocks);  in __alloc_contig_try_harder()
1276 int gpu_buddy_block_trim(struct gpu_buddy *mm,  in gpu_buddy_block_trim()  argument
1288 	gpu_buddy_driver_lock_held(mm);  in gpu_buddy_block_trim()
1298 	block_end = block_start + gpu_buddy_block_size(mm, block);  in gpu_buddy_block_trim()
1303 	if (new_size > gpu_buddy_block_size(mm, block))  in gpu_buddy_block_trim()
1306 	if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size))  in gpu_buddy_block_trim()
1309 	if (new_size == gpu_buddy_block_size(mm, block))  in gpu_buddy_block_trim()
1319 		if (!IS_ALIGNED(new_start, mm->chunk_size))  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()
1330 		mm->clear_avail += gpu_buddy_block_size(mm, block);  in gpu_buddy_block_trim()
1337 	err =  __alloc_range(mm, &dfs, new_start, new_size, blocks, NULL);  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()
1342 			mm->clear_avail -= gpu_buddy_block_size(mm, block);  in gpu_buddy_block_trim()
1352 __gpu_buddy_alloc_blocks(struct gpu_buddy *mm,  in __gpu_buddy_alloc_blocks()  argument
1360 		return  __gpu_buddy_alloc_range_bias(mm, start, end,  in __gpu_buddy_alloc_blocks()
1364 		return gpu_buddy_offset_aligned_allocation(mm, size,  in __gpu_buddy_alloc_blocks()
1369 		return alloc_from_freetree(mm, order, flags);  in __gpu_buddy_alloc_blocks()
1392 int gpu_buddy_alloc_blocks(struct gpu_buddy *mm,  in gpu_buddy_alloc_blocks()  argument
1405 	gpu_buddy_driver_lock_held(mm);  in gpu_buddy_alloc_blocks()
1407 	if (size < mm->chunk_size)  in gpu_buddy_alloc_blocks()
1410 	if (min_block_size < mm->chunk_size)  in gpu_buddy_alloc_blocks()
1416 	if (!IS_ALIGNED(start | end | size, mm->chunk_size))  in gpu_buddy_alloc_blocks()
1419 	if (end > mm->size)  in gpu_buddy_alloc_blocks()
1422 	if (range_overflows(start, size, mm->size))  in gpu_buddy_alloc_blocks()
1430 		return __gpu_buddy_alloc_range(mm, start, size, NULL, blocks);  in gpu_buddy_alloc_blocks()
1448 	pages = size >> ilog2(mm->chunk_size);  in gpu_buddy_alloc_blocks()
1450 	min_order = ilog2(min_block_size) - ilog2(mm->chunk_size);  in gpu_buddy_alloc_blocks()
1452 	if (order > mm->max_order || size > mm->size) {  in gpu_buddy_alloc_blocks()
1455 			return __alloc_contig_try_harder(mm, original_size,  in gpu_buddy_alloc_blocks()
1463 		BUG_ON(order > mm->max_order);  in gpu_buddy_alloc_blocks()
1473 			block = __gpu_buddy_alloc_blocks(mm, start,  in gpu_buddy_alloc_blocks()
1492 			if (mm->clear_avail &&  in gpu_buddy_alloc_blocks()
1493 			    !__force_merge(mm, start, end, fallback_order)) {  in gpu_buddy_alloc_blocks()
1494 				block = __gpu_buddy_alloc_blocks(mm, start,  in gpu_buddy_alloc_blocks()
1512 				return __alloc_contig_try_harder(mm,  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()
1523 			mm->clear_avail -= gpu_buddy_block_size(mm, block);  in gpu_buddy_alloc_blocks()
1547 			trim_size = gpu_buddy_block_size(mm, block) -  in gpu_buddy_alloc_blocks()
1551 		gpu_buddy_block_trim(mm,  in gpu_buddy_alloc_blocks()
1564 	gpu_buddy_free_list_internal(mm, &allocated);  in gpu_buddy_alloc_blocks()
1575 void gpu_buddy_block_print(struct gpu_buddy *mm,  in gpu_buddy_block_print()  argument
1579 	u64 size = gpu_buddy_block_size(mm, block);  in gpu_buddy_block_print()
1591 void gpu_buddy_print(struct gpu_buddy *mm)  in gpu_buddy_print()  argument
1595 	gpu_buddy_driver_lock_held(mm);  in gpu_buddy_print()
1597 		mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20, mm->clear_avail >> 20);  in gpu_buddy_print()
1599 	for (order = mm->max_order; order >= 0; order--) {  in gpu_buddy_print()
1600 		u64 free_count = mm->free_scoreboard[order];  in gpu_buddy_print()
1601 		u64 used_count = mm->used_scoreboard[order];  in gpu_buddy_print()
1602 		u64 block_size = mm->chunk_size << order;  in gpu_buddy_print()