19 	struct drm_buddy_block *block;  in drm_block_alloc()  local
23 	block = kmem_cache_zalloc(slab_blocks, GFP_KERNEL);  in drm_block_alloc()
24 	if (!block)  in drm_block_alloc()
27 	block->header = offset;  in drm_block_alloc()
28 	block->header |= order;  in drm_block_alloc()
29 	block->parent = parent;  in drm_block_alloc()
31 	BUG_ON(block->header & DRM_BUDDY_HEADER_UNUSED);  in drm_block_alloc()
32 	return block;  in drm_block_alloc()
36 			   struct drm_buddy_block *block)  in drm_block_free()  argument
38 	kmem_cache_free(slab_blocks, block);  in drm_block_free()
42 			       struct drm_buddy_block *block)  in list_insert_sorted()  argument
47 	head = &mm->free_list[drm_buddy_block_order(block)];  in list_insert_sorted()
49 		list_add(&block->link, head);  in list_insert_sorted()
54 		if (drm_buddy_block_offset(block) < drm_buddy_block_offset(node))  in list_insert_sorted()
57 	__list_add(&block->link, node->link.prev, &node->link);  in list_insert_sorted()
60 static void mark_allocated(struct drm_buddy_block *block)  in mark_allocated()  argument
62 	block->header &= ~DRM_BUDDY_HEADER_STATE;  in mark_allocated()
63 	block->header |= DRM_BUDDY_ALLOCATED;  in mark_allocated()
65 	list_del(&block->link);  in mark_allocated()
69 		      struct drm_buddy_block *block)  in mark_free()  argument
71 	block->header &= ~DRM_BUDDY_HEADER_STATE;  in mark_free()
72 	block->header |= DRM_BUDDY_FREE;  in mark_free()
74 	list_insert_sorted(mm, block);  in mark_free()
77 static void mark_split(struct drm_buddy_block *block)  in mark_split()  argument
79 	block->header &= ~DRM_BUDDY_HEADER_STATE;  in mark_split()
80 	block->header |= DRM_BUDDY_SPLIT;  in mark_split()
82 	list_del(&block->link);  in mark_split()
204 		       struct drm_buddy_block *block)  in split_block()  argument
206 	unsigned int block_order = drm_buddy_block_order(block) - 1;  in split_block()
207 	u64 offset = drm_buddy_block_offset(block);  in split_block()
209 	BUG_ON(!drm_buddy_block_is_free(block));  in split_block()
210 	BUG_ON(!drm_buddy_block_order(block));  in split_block()
212 	block->left = drm_block_alloc(mm, block, block_order, offset);  in split_block()
213 	if (!block->left)  in split_block()
216 	block->right = drm_block_alloc(mm, block, block_order,  in split_block()
218 	if (!block->right) {  in split_block()
219 		drm_block_free(mm, block->left);  in split_block()
223 	mark_free(mm, block->left);  in split_block()
224 	mark_free(mm, block->right);  in split_block()
226 	mark_split(block);  in split_block()
232 __get_buddy(struct drm_buddy_block *block)  in __get_buddy()  argument
236 	parent = block->parent;  in __get_buddy()
240 	if (parent->left == block)  in __get_buddy()
257 drm_get_buddy(struct drm_buddy_block *block)  in drm_get_buddy()  argument
259 	return __get_buddy(block);  in drm_get_buddy()
264 			     struct drm_buddy_block *block)  in __drm_buddy_free()  argument
268 	while ((parent = block->parent)) {  in __drm_buddy_free()
271 		buddy = __get_buddy(block);  in __drm_buddy_free()
278 		drm_block_free(mm, block);  in __drm_buddy_free()
281 		block = parent;  in __drm_buddy_free()
284 	mark_free(mm, block);  in __drm_buddy_free()
294 			  struct drm_buddy_block *block)  in drm_buddy_free_block()  argument
296 	BUG_ON(!drm_buddy_block_is_allocated(block));  in drm_buddy_free_block()
297 	mm->avail += drm_buddy_block_size(mm, block);  in drm_buddy_free_block()
298 	__drm_buddy_free(mm, block);  in drm_buddy_free_block()
310 	struct drm_buddy_block *block, *on;  in drm_buddy_free_list()  local
312 	list_for_each_entry_safe(block, on, objects, link) {  in drm_buddy_free_list()
313 		drm_buddy_free_block(mm, block);  in drm_buddy_free_list()
335 	struct drm_buddy_block *block;  in alloc_range_bias()  local
350 		block = list_first_entry_or_null(&dfs,  in alloc_range_bias()
353 		if (!block)  in alloc_range_bias()
356 		list_del(&block->tmp_link);  in alloc_range_bias()
358 		if (drm_buddy_block_order(block) < order)  in alloc_range_bias()
361 		block_start = drm_buddy_block_offset(block);  in alloc_range_bias()
362 		block_end = block_start + drm_buddy_block_size(mm, block) - 1;  in alloc_range_bias()
367 		if (drm_buddy_block_is_allocated(block))  in alloc_range_bias()
371 		    order == drm_buddy_block_order(block)) {  in alloc_range_bias()
375 			if (drm_buddy_block_is_free(block))  in alloc_range_bias()
376 				return block;  in alloc_range_bias()
381 		if (!drm_buddy_block_is_split(block)) {  in alloc_range_bias()
382 			err = split_block(mm, block);  in alloc_range_bias()
387 		list_add(&block->right->tmp_link, &dfs);  in alloc_range_bias()
388 		list_add(&block->left->tmp_link, &dfs);  in alloc_range_bias()
399 	buddy = __get_buddy(block);  in alloc_range_bias()
401 	    (drm_buddy_block_is_free(block) &&  in alloc_range_bias()
403 		__drm_buddy_free(mm, block);  in alloc_range_bias()
438 	struct drm_buddy_block *block = NULL;  in alloc_from_freelist()  local
443 		block = get_maxblock(mm, order);  in alloc_from_freelist()
444 		if (block)  in alloc_from_freelist()
446 			tmp = drm_buddy_block_order(block);  in alloc_from_freelist()
450 				block = list_last_entry(&mm->free_list[tmp],  in alloc_from_freelist()
453 				if (block)  in alloc_from_freelist()
459 	if (!block)  in alloc_from_freelist()
462 	BUG_ON(!drm_buddy_block_is_free(block));  in alloc_from_freelist()
465 		err = split_block(mm, block);  in alloc_from_freelist()
469 		block = block->right;  in alloc_from_freelist()
472 	return block;  in alloc_from_freelist()
476 		__drm_buddy_free(mm, block);  in alloc_from_freelist()
485 	struct drm_buddy_block *block;  in __alloc_range()  local
497 		block = list_first_entry_or_null(dfs,  in __alloc_range()
500 		if (!block)  in __alloc_range()
503 		list_del(&block->tmp_link);  in __alloc_range()
505 		block_start = drm_buddy_block_offset(block);  in __alloc_range()
506 		block_end = block_start + drm_buddy_block_size(mm, block) - 1;  in __alloc_range()
511 		if (drm_buddy_block_is_allocated(block)) {  in __alloc_range()
517 			if (!drm_buddy_block_is_free(block)) {  in __alloc_range()
522 			mark_allocated(block);  in __alloc_range()
523 			mm->avail -= drm_buddy_block_size(mm, block);  in __alloc_range()
524 			list_add_tail(&block->link, &allocated);  in __alloc_range()
528 		if (!drm_buddy_block_is_split(block)) {  in __alloc_range()
529 			err = split_block(mm, block);  in __alloc_range()
534 		list_add(&block->right->tmp_link, dfs);  in __alloc_range()
535 		list_add(&block->left->tmp_link, dfs);  in __alloc_range()
547 	buddy = __get_buddy(block);  in __alloc_range()
549 	    (drm_buddy_block_is_free(block) &&  in __alloc_range()
551 		__drm_buddy_free(mm, block);  in __alloc_range()
595 	struct drm_buddy_block *block;  in drm_buddy_block_trim()  local
603 	block = list_first_entry(blocks,  in drm_buddy_block_trim()
607 	if (WARN_ON(!drm_buddy_block_is_allocated(block)))  in drm_buddy_block_trim()
610 	if (new_size > drm_buddy_block_size(mm, block))  in drm_buddy_block_trim()
616 	if (new_size == drm_buddy_block_size(mm, block))  in drm_buddy_block_trim()
619 	list_del(&block->link);  in drm_buddy_block_trim()
620 	mark_free(mm, block);  in drm_buddy_block_trim()
621 	mm->avail += drm_buddy_block_size(mm, block);  in drm_buddy_block_trim()
624 	parent = block->parent;  in drm_buddy_block_trim()
625 	block->parent = NULL;  in drm_buddy_block_trim()
627 	new_start = drm_buddy_block_offset(block);  in drm_buddy_block_trim()
628 	list_add(&block->tmp_link, &dfs);  in drm_buddy_block_trim()
631 		mark_allocated(block);  in drm_buddy_block_trim()
632 		mm->avail -= drm_buddy_block_size(mm, block);  in drm_buddy_block_trim()
633 		list_add(&block->link, blocks);  in drm_buddy_block_trim()
636 	block->parent = parent;  in drm_buddy_block_trim()
667 	struct drm_buddy_block *block = NULL;  in drm_buddy_alloc_blocks()  local
710 				block = alloc_range_bias(mm, start, end, order);  in drm_buddy_alloc_blocks()
713 				block = alloc_from_freelist(mm, order, flags);  in drm_buddy_alloc_blocks()
715 			if (!IS_ERR(block))  in drm_buddy_alloc_blocks()
724 		mark_allocated(block);  in drm_buddy_alloc_blocks()
725 		mm->avail -= drm_buddy_block_size(mm, block);  in drm_buddy_alloc_blocks()
726 		kmemleak_update_trace(block);  in drm_buddy_alloc_blocks()
727 		list_add_tail(&block->link, &allocated);  in drm_buddy_alloc_blocks()
752 			   struct drm_buddy_block *block,  in drm_buddy_block_print()  argument
755 	u64 start = drm_buddy_block_offset(block);  in drm_buddy_block_print()
756 	u64 size = drm_buddy_block_size(mm, block);  in drm_buddy_block_print()
776 		struct drm_buddy_block *block;  in drm_buddy_print()  local
779 		list_for_each_entry(block, &mm->free_list[order], link) {  in drm_buddy_print()
780 			BUG_ON(!drm_buddy_block_is_free(block));  in drm_buddy_print()