16 static struct drm_buddy_block *drm_block_alloc(struct drm_buddy *mm,  in drm_block_alloc()  argument
37 static void drm_block_free(struct drm_buddy *mm,  in drm_block_free()  argument
43 static void list_insert_sorted(struct drm_buddy *mm,  in list_insert_sorted()  argument
49 	head = &mm->free_list[drm_buddy_block_order(block)];  in list_insert_sorted()
80 static void mark_free(struct drm_buddy *mm,  in mark_free()  argument
86 	list_insert_sorted(mm, block);  in mark_free()
122 static unsigned int __drm_buddy_free(struct drm_buddy *mm,  in __drm_buddy_free()  argument
152 			mm->clear_avail -= drm_buddy_block_size(mm, buddy);  in __drm_buddy_free()
154 		drm_block_free(mm, block);  in __drm_buddy_free()
155 		drm_block_free(mm, buddy);  in __drm_buddy_free()
161 	mark_free(mm, block);  in __drm_buddy_free()
166 static int __force_merge(struct drm_buddy *mm,  in __force_merge()  argument
177 	if (min_order > mm->max_order)  in __force_merge()
183 		list_for_each_entry_safe_reverse(block, prev, &mm->free_list[i], link) {  in __force_merge()
191 			block_end = block_start + drm_buddy_block_size(mm, block) - 1;  in __force_merge()
213 				mm->clear_avail -= drm_buddy_block_size(mm, block);  in __force_merge()
215 			order = __drm_buddy_free(mm, block, true);  in __force_merge()
236 int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size)  in drm_buddy_init()  argument
252 	mm->size = size;  in drm_buddy_init()
253 	mm->avail = size;  in drm_buddy_init()
254 	mm->clear_avail = 0;  in drm_buddy_init()
255 	mm->chunk_size = chunk_size;  in drm_buddy_init()
256 	mm->max_order = ilog2(size) - ilog2(chunk_size);  in drm_buddy_init()
258 	BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER);  in drm_buddy_init()
260 	mm->free_list = kmalloc_array(mm->max_order + 1,  in drm_buddy_init()
263 	if (!mm->free_list)  in drm_buddy_init()
266 	for (i = 0; i <= mm->max_order; ++i)  in drm_buddy_init()
267 		INIT_LIST_HEAD(&mm->free_list[i]);  in drm_buddy_init()
269 	mm->n_roots = hweight64(size);  in drm_buddy_init()
271 	mm->roots = kmalloc_array(mm->n_roots,  in drm_buddy_init()
274 	if (!mm->roots)  in drm_buddy_init()
292 		root = drm_block_alloc(mm, NULL, order, offset);  in drm_buddy_init()
296 		mark_free(mm, root);  in drm_buddy_init()
298 		BUG_ON(i > mm->max_order);  in drm_buddy_init()
299 		BUG_ON(drm_buddy_block_size(mm, root) < chunk_size);  in drm_buddy_init()
301 		mm->roots[i] = root;  in drm_buddy_init()
312 		drm_block_free(mm, mm->roots[i]);  in drm_buddy_init()
313 	kfree(mm->roots);  in drm_buddy_init()
315 	kfree(mm->free_list);  in drm_buddy_init()
327 void drm_buddy_fini(struct drm_buddy *mm)  in drm_buddy_fini()  argument
333 	size = mm->size;  in drm_buddy_fini()
335 	for (i = 0; i < mm->n_roots; ++i) {  in drm_buddy_fini()
336 		order = ilog2(size) - ilog2(mm->chunk_size);  in drm_buddy_fini()
337 		start = drm_buddy_block_offset(mm->roots[i]);  in drm_buddy_fini()
338 		__force_merge(mm, start, start + size, order);  in drm_buddy_fini()
340 		if (WARN_ON(!drm_buddy_block_is_free(mm->roots[i])))  in drm_buddy_fini()
343 		drm_block_free(mm, mm->roots[i]);  in drm_buddy_fini()
345 		root_size = mm->chunk_size << order;  in drm_buddy_fini()
349 	WARN_ON(mm->avail != mm->size);  in drm_buddy_fini()
351 	kfree(mm->roots);  in drm_buddy_fini()
352 	kfree(mm->free_list);  in drm_buddy_fini()
356 static int split_block(struct drm_buddy *mm,  in split_block()  argument
365 	block->left = drm_block_alloc(mm, block, block_order, offset);  in split_block()
369 	block->right = drm_block_alloc(mm, block, block_order,  in split_block()
370 				       offset + (mm->chunk_size << block_order));  in split_block()
372 		drm_block_free(mm, block->left);  in split_block()
376 	mark_free(mm, block->left);  in split_block()
377 	mark_free(mm, block->right);  in split_block()
413 void drm_buddy_free_block(struct drm_buddy *mm,  in drm_buddy_free_block()  argument
417 	mm->avail += drm_buddy_block_size(mm, block);  in drm_buddy_free_block()
419 		mm->clear_avail += drm_buddy_block_size(mm, block);  in drm_buddy_free_block()
421 	__drm_buddy_free(mm, block, false);  in drm_buddy_free_block()
425 static void __drm_buddy_free_list(struct drm_buddy *mm,  in __drm_buddy_free_list()  argument
439 		drm_buddy_free_block(mm, block);  in __drm_buddy_free_list()
445 static void drm_buddy_free_list_internal(struct drm_buddy *mm,  in drm_buddy_free_list_internal()  argument
453 	__drm_buddy_free_list(mm, objects, false, false);  in drm_buddy_free_list_internal()
463 void drm_buddy_free_list(struct drm_buddy *mm,  in drm_buddy_free_list()  argument
469 	__drm_buddy_free_list(mm, objects, mark_clear, !mark_clear);  in drm_buddy_free_list()
481 __alloc_range_bias(struct drm_buddy *mm,  in __alloc_range_bias()  argument
487 	u64 req_size = mm->chunk_size << order;  in __alloc_range_bias()
496 	for (i = 0; i < mm->n_roots; ++i)  in __alloc_range_bias()
497 		list_add_tail(&mm->roots[i]->tmp_link, &dfs);  in __alloc_range_bias()
515 		block_end = block_start + drm_buddy_block_size(mm, block) - 1;  in __alloc_range_bias()
547 			err = split_block(mm, block);  in __alloc_range_bias()
568 		__drm_buddy_free(mm, block, false);  in __alloc_range_bias()
573 __drm_buddy_alloc_range_bias(struct drm_buddy *mm,  in __drm_buddy_alloc_range_bias()  argument
581 	block = __alloc_range_bias(mm, start, end, order,  in __drm_buddy_alloc_range_bias()
584 		return __alloc_range_bias(mm, start, end, order,  in __drm_buddy_alloc_range_bias()
591 get_maxblock(struct drm_buddy *mm, unsigned int order,  in get_maxblock()  argument
597 	for (i = order; i <= mm->max_order; ++i) {  in get_maxblock()
600 		list_for_each_entry_reverse(tmp_block, &mm->free_list[i], link) {  in get_maxblock()
626 alloc_from_freelist(struct drm_buddy *mm,  in alloc_from_freelist()  argument
635 		block = get_maxblock(mm, order, flags);  in alloc_from_freelist()
640 		for (tmp = order; tmp <= mm->max_order; ++tmp) {  in alloc_from_freelist()
643 			list_for_each_entry_reverse(tmp_block, &mm->free_list[tmp], link) {  in alloc_from_freelist()
658 		for (tmp = order; tmp <= mm->max_order; ++tmp) {  in alloc_from_freelist()
659 			if (!list_empty(&mm->free_list[tmp])) {  in alloc_from_freelist()
660 				block = list_last_entry(&mm->free_list[tmp],  in alloc_from_freelist()
675 		err = split_block(mm, block);  in alloc_from_freelist()
686 		__drm_buddy_free(mm, block, false);  in alloc_from_freelist()
690 static int __alloc_range(struct drm_buddy *mm,  in __alloc_range()  argument
718 		block_end = block_start + drm_buddy_block_size(mm, block) - 1;  in __alloc_range()
731 				total_allocated += drm_buddy_block_size(mm, block);  in __alloc_range()
732 				mm->avail -= drm_buddy_block_size(mm, block);  in __alloc_range()
734 					mm->clear_avail -= drm_buddy_block_size(mm, block);  in __alloc_range()
737 			} else if (!mm->clear_avail) {  in __alloc_range()
744 			err = split_block(mm, block);  in __alloc_range()
772 		__drm_buddy_free(mm, block, false);  in __alloc_range()
779 		drm_buddy_free_list_internal(mm, &allocated);  in __alloc_range()
785 static int __drm_buddy_alloc_range(struct drm_buddy *mm,  in __drm_buddy_alloc_range()  argument
794 	for (i = 0; i < mm->n_roots; ++i)  in __drm_buddy_alloc_range()
795 		list_add_tail(&mm->roots[i]->tmp_link, &dfs);  in __drm_buddy_alloc_range()
797 	return __alloc_range(mm, &dfs, start, size,  in __drm_buddy_alloc_range()
801 static int __alloc_contig_try_harder(struct drm_buddy *mm,  in __alloc_contig_try_harder()  argument
816 	pages = modify_size >> ilog2(mm->chunk_size);  in __alloc_contig_try_harder()
821 	list = &mm->free_list[order];  in __alloc_contig_try_harder()
828 		err =  __drm_buddy_alloc_range(mm, rhs_offset, size,  in __alloc_contig_try_harder()
839 		err =  __drm_buddy_alloc_range(mm, lhs_offset, lhs_size,  in __alloc_contig_try_harder()
845 			drm_buddy_free_list_internal(mm, blocks);  in __alloc_contig_try_harder()
849 		drm_buddy_free_list_internal(mm, blocks);  in __alloc_contig_try_harder()
874 int drm_buddy_block_trim(struct drm_buddy *mm,  in drm_buddy_block_trim()  argument
894 	block_end = block_start + drm_buddy_block_size(mm, block);  in drm_buddy_block_trim()
899 	if (new_size > drm_buddy_block_size(mm, block))  in drm_buddy_block_trim()
902 	if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size))  in drm_buddy_block_trim()
905 	if (new_size == drm_buddy_block_size(mm, block))  in drm_buddy_block_trim()
915 		if (!IS_ALIGNED(new_start, mm->chunk_size))  in drm_buddy_block_trim()
923 	mark_free(mm, block);  in drm_buddy_block_trim()
924 	mm->avail += drm_buddy_block_size(mm, block);  in drm_buddy_block_trim()
926 		mm->clear_avail += drm_buddy_block_size(mm, block);  in drm_buddy_block_trim()
933 	err =  __alloc_range(mm, &dfs, new_start, new_size, blocks, NULL);  in drm_buddy_block_trim()
936 		mm->avail -= drm_buddy_block_size(mm, block);  in drm_buddy_block_trim()
938 			mm->clear_avail -= drm_buddy_block_size(mm, block);  in drm_buddy_block_trim()
948 __drm_buddy_alloc_blocks(struct drm_buddy *mm,  in __drm_buddy_alloc_blocks()  argument
955 		return  __drm_buddy_alloc_range_bias(mm, start, end,  in __drm_buddy_alloc_blocks()
959 		return alloc_from_freelist(mm, order, flags);  in __drm_buddy_alloc_blocks()
982 int drm_buddy_alloc_blocks(struct drm_buddy *mm,  in drm_buddy_alloc_blocks()  argument
995 	if (size < mm->chunk_size)  in drm_buddy_alloc_blocks()
998 	if (min_block_size < mm->chunk_size)  in drm_buddy_alloc_blocks()
1004 	if (!IS_ALIGNED(start | end | size, mm->chunk_size))  in drm_buddy_alloc_blocks()
1007 	if (end > mm->size)  in drm_buddy_alloc_blocks()
1010 	if (range_overflows(start, size, mm->size))  in drm_buddy_alloc_blocks()
1018 		return __drm_buddy_alloc_range(mm, start, size, NULL, blocks);  in drm_buddy_alloc_blocks()
1033 	pages = size >> ilog2(mm->chunk_size);  in drm_buddy_alloc_blocks()
1035 	min_order = ilog2(min_block_size) - ilog2(mm->chunk_size);  in drm_buddy_alloc_blocks()
1039 		BUG_ON(order > mm->max_order);  in drm_buddy_alloc_blocks()
1043 			block = __drm_buddy_alloc_blocks(mm, start,  in drm_buddy_alloc_blocks()
1052 				if (mm->clear_avail &&  in drm_buddy_alloc_blocks()
1053 				    !__force_merge(mm, start, end, min_order)) {  in drm_buddy_alloc_blocks()
1054 					block = __drm_buddy_alloc_blocks(mm, start,  in drm_buddy_alloc_blocks()
1070 					return __alloc_contig_try_harder(mm,  in drm_buddy_alloc_blocks()
1080 		mm->avail -= drm_buddy_block_size(mm, block);  in drm_buddy_alloc_blocks()
1082 			mm->clear_avail -= drm_buddy_block_size(mm, block);  in drm_buddy_alloc_blocks()
1106 			trim_size = drm_buddy_block_size(mm, block) -  in drm_buddy_alloc_blocks()
1110 		drm_buddy_block_trim(mm,  in drm_buddy_alloc_blocks()
1123 	drm_buddy_free_list_internal(mm, &allocated);  in drm_buddy_alloc_blocks()
1135 void drm_buddy_block_print(struct drm_buddy *mm,  in drm_buddy_block_print()  argument
1140 	u64 size = drm_buddy_block_size(mm, block);  in drm_buddy_block_print()
1152 void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p)  in drm_buddy_print()  argument
1157 		   mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20, mm->clear_avail >> 20);  in drm_buddy_print()
1159 	for (order = mm->max_order; order >= 0; order--) {  in drm_buddy_print()
1163 		list_for_each_entry(block, &mm->free_list[order], link) {  in drm_buddy_print()
1170 		free = count * (mm->chunk_size << order);  in drm_buddy_print()