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()
41 static void mark_allocated(struct drm_buddy_block *block)  in mark_allocated()  argument
43 	block->header &= ~DRM_BUDDY_HEADER_STATE;  in mark_allocated()
44 	block->header |= DRM_BUDDY_ALLOCATED;  in mark_allocated()
46 	list_del(&block->link);  in mark_allocated()
50 		      struct drm_buddy_block *block)  in mark_free()  argument
52 	block->header &= ~DRM_BUDDY_HEADER_STATE;  in mark_free()
53 	block->header |= DRM_BUDDY_FREE;  in mark_free()
55 	list_add(&block->link,  in mark_free()
56 		 &mm->free_list[drm_buddy_block_order(block)]);  in mark_free()
59 static void mark_split(struct drm_buddy_block *block)  in mark_split()  argument
61 	block->header &= ~DRM_BUDDY_HEADER_STATE;  in mark_split()
62 	block->header |= DRM_BUDDY_SPLIT;  in mark_split()
64 	list_del(&block->link);  in mark_split()
186 		       struct drm_buddy_block *block)  in split_block()  argument
188 	unsigned int block_order = drm_buddy_block_order(block) - 1;  in split_block()
189 	u64 offset = drm_buddy_block_offset(block);  in split_block()
191 	BUG_ON(!drm_buddy_block_is_free(block));  in split_block()
192 	BUG_ON(!drm_buddy_block_order(block));  in split_block()
194 	block->left = drm_block_alloc(mm, block, block_order, offset);  in split_block()
195 	if (!block->left)  in split_block()
198 	block->right = drm_block_alloc(mm, block, block_order,  in split_block()
200 	if (!block->right) {  in split_block()
201 		drm_block_free(mm, block->left);  in split_block()
205 	mark_free(mm, block->left);  in split_block()
206 	mark_free(mm, block->right);  in split_block()
208 	mark_split(block);  in split_block()
214 __get_buddy(struct drm_buddy_block *block)  in __get_buddy()  argument
218 	parent = block->parent;  in __get_buddy()
222 	if (parent->left == block)  in __get_buddy()
231  * @block: DRM buddy block
233  * Returns the corresponding buddy block for @block, or NULL
234  * if this is a root block and can't be merged further.
239 drm_get_buddy(struct drm_buddy_block *block)  in drm_get_buddy()  argument
241 	return __get_buddy(block);  in drm_get_buddy()
246 			     struct drm_buddy_block *block)  in __drm_buddy_free()  argument
250 	while ((parent = block->parent)) {  in __drm_buddy_free()
253 		buddy = __get_buddy(block);  in __drm_buddy_free()
260 		drm_block_free(mm, block);  in __drm_buddy_free()
263 		block = parent;  in __drm_buddy_free()
266 	mark_free(mm, block);  in __drm_buddy_free()
270  * drm_buddy_free_block - free a block
273  * @block: block to be freed
276 			  struct drm_buddy_block *block)  in drm_buddy_free_block()  argument
278 	BUG_ON(!drm_buddy_block_is_allocated(block));  in drm_buddy_free_block()
279 	mm->avail += drm_buddy_block_size(mm, block);  in drm_buddy_free_block()
280 	__drm_buddy_free(mm, block);  in drm_buddy_free_block()
292 	struct drm_buddy_block *block, *on;  in drm_buddy_free_list()  local
294 	list_for_each_entry_safe(block, on, objects, link) {  in drm_buddy_free_list()
295 		drm_buddy_free_block(mm, block);  in drm_buddy_free_list()
317 	struct drm_buddy_block *block;  in alloc_range_bias()  local
332 		block = list_first_entry_or_null(&dfs,  in alloc_range_bias()
335 		if (!block)  in alloc_range_bias()
338 		list_del(&block->tmp_link);  in alloc_range_bias()
340 		if (drm_buddy_block_order(block) < order)  in alloc_range_bias()
343 		block_start = drm_buddy_block_offset(block);  in alloc_range_bias()
344 		block_end = block_start + drm_buddy_block_size(mm, block) - 1;  in alloc_range_bias()
349 		if (drm_buddy_block_is_allocated(block))  in alloc_range_bias()
353 		    order == drm_buddy_block_order(block)) {  in alloc_range_bias()
355 			 * Find the free block within the range.  in alloc_range_bias()
357 			if (drm_buddy_block_is_free(block))  in alloc_range_bias()
358 				return block;  in alloc_range_bias()
363 		if (!drm_buddy_block_is_split(block)) {  in alloc_range_bias()
364 			err = split_block(mm, block);  in alloc_range_bias()
369 		list_add(&block->right->tmp_link, &dfs);  in alloc_range_bias()
370 		list_add(&block->left->tmp_link, &dfs);  in alloc_range_bias()
381 	buddy = __get_buddy(block);  in alloc_range_bias()
383 	    (drm_buddy_block_is_free(block) &&  in alloc_range_bias()
385 		__drm_buddy_free(mm, block);  in alloc_range_bias()
414 	struct drm_buddy_block *block = NULL;  in alloc_from_freelist()  local
420 			block = get_maxblock(&mm->free_list[i]);  in alloc_from_freelist()
421 			if (block)  in alloc_from_freelist()
424 			block = list_first_entry_or_null(&mm->free_list[i],  in alloc_from_freelist()
427 			if (block)  in alloc_from_freelist()
432 	if (!block)  in alloc_from_freelist()
435 	BUG_ON(!drm_buddy_block_is_free(block));  in alloc_from_freelist()
438 		err = split_block(mm, block);  in alloc_from_freelist()
442 		block = block->right;  in alloc_from_freelist()
445 	return block;  in alloc_from_freelist()
449 		__drm_buddy_free(mm, block);  in alloc_from_freelist()
458 	struct drm_buddy_block *block;  in __alloc_range()  local
470 		block = list_first_entry_or_null(dfs,  in __alloc_range()
473 		if (!block)  in __alloc_range()
476 		list_del(&block->tmp_link);  in __alloc_range()
478 		block_start = drm_buddy_block_offset(block);  in __alloc_range()
479 		block_end = block_start + drm_buddy_block_size(mm, block) - 1;  in __alloc_range()
484 		if (drm_buddy_block_is_allocated(block)) {  in __alloc_range()
490 			if (!drm_buddy_block_is_free(block)) {  in __alloc_range()
495 			mark_allocated(block);  in __alloc_range()
496 			mm->avail -= drm_buddy_block_size(mm, block);  in __alloc_range()
497 			list_add_tail(&block->link, &allocated);  in __alloc_range()
501 		if (!drm_buddy_block_is_split(block)) {  in __alloc_range()
502 			err = split_block(mm, block);  in __alloc_range()
507 		list_add(&block->right->tmp_link, dfs);  in __alloc_range()
508 		list_add(&block->left->tmp_link, dfs);  in __alloc_range()
520 	buddy = __get_buddy(block);  in __alloc_range()
522 	    (drm_buddy_block_is_free(block) &&  in __alloc_range()
524 		__drm_buddy_free(mm, block);  in __alloc_range()
551  * MUST contain single block as input to be trimmed.
568 	struct drm_buddy_block *block;  in drm_buddy_block_trim()  local
576 	block = list_first_entry(blocks,  in drm_buddy_block_trim()
580 	if (WARN_ON(!drm_buddy_block_is_allocated(block)))  in drm_buddy_block_trim()
583 	if (new_size > drm_buddy_block_size(mm, block))  in drm_buddy_block_trim()
589 	if (new_size == drm_buddy_block_size(mm, block))  in drm_buddy_block_trim()
592 	list_del(&block->link);  in drm_buddy_block_trim()
593 	mark_free(mm, block);  in drm_buddy_block_trim()
594 	mm->avail += drm_buddy_block_size(mm, block);  in drm_buddy_block_trim()
597 	parent = block->parent;  in drm_buddy_block_trim()
598 	block->parent = NULL;  in drm_buddy_block_trim()
600 	new_start = drm_buddy_block_offset(block);  in drm_buddy_block_trim()
601 	list_add(&block->tmp_link, &dfs);  in drm_buddy_block_trim()
604 		mark_allocated(block);  in drm_buddy_block_trim()
605 		mm->avail -= drm_buddy_block_size(mm, block);  in drm_buddy_block_trim()
606 		list_add(&block->link, blocks);  in drm_buddy_block_trim()
609 	block->parent = parent;  in drm_buddy_block_trim()
618  * @start: start of the allowed range for this block
619  * @end: end of the allowed range for this block
626  * the tree and returns the desired block.
629  * are enforced, which picks the block from the freelist.
640 	struct drm_buddy_block *block = NULL;  in drm_buddy_alloc_blocks()  local
683 				block = alloc_range_bias(mm, start, end, order);  in drm_buddy_alloc_blocks()
686 				block = alloc_from_freelist(mm, order, flags);  in drm_buddy_alloc_blocks()
688 			if (!IS_ERR(block))  in drm_buddy_alloc_blocks()
697 		mark_allocated(block);  in drm_buddy_alloc_blocks()
698 		mm->avail -= drm_buddy_block_size(mm, block);  in drm_buddy_alloc_blocks()
699 		kmemleak_update_trace(block);  in drm_buddy_alloc_blocks()
700 		list_add_tail(&block->link, &allocated);  in drm_buddy_alloc_blocks()
718  * drm_buddy_block_print - print block information
721  * @block: DRM buddy block
725 			   struct drm_buddy_block *block,  in drm_buddy_block_print()  argument
728 	u64 start = drm_buddy_block_offset(block);  in drm_buddy_block_print()
729 	u64 size = drm_buddy_block_size(mm, block);  in drm_buddy_block_print()
749 		struct drm_buddy_block *block;  in drm_buddy_print()  local
752 		list_for_each_entry(block, &mm->free_list[order], link) {  in drm_buddy_print()
753 			BUG_ON(!drm_buddy_block_is_free(block));  in drm_buddy_print()