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()
336 	struct drm_buddy_block *block;  in alloc_range_bias()  local
351 		block = list_first_entry_or_null(&dfs,  in alloc_range_bias()
354 		if (!block)  in alloc_range_bias()
357 		list_del(&block->tmp_link);  in alloc_range_bias()
359 		if (drm_buddy_block_order(block) < order)  in alloc_range_bias()
362 		block_start = drm_buddy_block_offset(block);  in alloc_range_bias()
363 		block_end = block_start + drm_buddy_block_size(mm, block) - 1;  in alloc_range_bias()
368 		if (drm_buddy_block_is_allocated(block))  in alloc_range_bias()
381 		    order == drm_buddy_block_order(block)) {  in alloc_range_bias()
385 			if (drm_buddy_block_is_free(block))  in alloc_range_bias()
386 				return block;  in alloc_range_bias()
391 		if (!drm_buddy_block_is_split(block)) {  in alloc_range_bias()
392 			err = split_block(mm, block);  in alloc_range_bias()
397 		list_add(&block->right->tmp_link, &dfs);  in alloc_range_bias()
398 		list_add(&block->left->tmp_link, &dfs);  in alloc_range_bias()
409 	buddy = __get_buddy(block);  in alloc_range_bias()
411 	    (drm_buddy_block_is_free(block) &&  in alloc_range_bias()
413 		__drm_buddy_free(mm, block);  in alloc_range_bias()
448 	struct drm_buddy_block *block = NULL;  in alloc_from_freelist()  local
453 		block = get_maxblock(mm, order);  in alloc_from_freelist()
454 		if (block)  in alloc_from_freelist()
456 			tmp = drm_buddy_block_order(block);  in alloc_from_freelist()
460 				block = list_last_entry(&mm->free_list[tmp],  in alloc_from_freelist()
463 				if (block)  in alloc_from_freelist()
469 	if (!block)  in alloc_from_freelist()
472 	BUG_ON(!drm_buddy_block_is_free(block));  in alloc_from_freelist()
475 		err = split_block(mm, block);  in alloc_from_freelist()
479 		block = block->right;  in alloc_from_freelist()
482 	return block;  in alloc_from_freelist()
486 		__drm_buddy_free(mm, block);  in alloc_from_freelist()
495 	struct drm_buddy_block *block;  in __alloc_range()  local
507 		block = list_first_entry_or_null(dfs,  in __alloc_range()
510 		if (!block)  in __alloc_range()
513 		list_del(&block->tmp_link);  in __alloc_range()
515 		block_start = drm_buddy_block_offset(block);  in __alloc_range()
516 		block_end = block_start + drm_buddy_block_size(mm, block) - 1;  in __alloc_range()
521 		if (drm_buddy_block_is_allocated(block)) {  in __alloc_range()
527 			if (!drm_buddy_block_is_free(block)) {  in __alloc_range()
532 			mark_allocated(block);  in __alloc_range()
533 			mm->avail -= drm_buddy_block_size(mm, block);  in __alloc_range()
534 			list_add_tail(&block->link, &allocated);  in __alloc_range()
538 		if (!drm_buddy_block_is_split(block)) {  in __alloc_range()
539 			err = split_block(mm, block);  in __alloc_range()
544 		list_add(&block->right->tmp_link, dfs);  in __alloc_range()
545 		list_add(&block->left->tmp_link, dfs);  in __alloc_range()
557 	buddy = __get_buddy(block);  in __alloc_range()
559 	    (drm_buddy_block_is_free(block) &&  in __alloc_range()
561 		__drm_buddy_free(mm, block);  in __alloc_range()
605 	struct drm_buddy_block *block;  in drm_buddy_block_trim()  local
613 	block = list_first_entry(blocks,  in drm_buddy_block_trim()
617 	if (WARN_ON(!drm_buddy_block_is_allocated(block)))  in drm_buddy_block_trim()
620 	if (new_size > drm_buddy_block_size(mm, block))  in drm_buddy_block_trim()
626 	if (new_size == drm_buddy_block_size(mm, block))  in drm_buddy_block_trim()
629 	list_del(&block->link);  in drm_buddy_block_trim()
630 	mark_free(mm, block);  in drm_buddy_block_trim()
631 	mm->avail += drm_buddy_block_size(mm, block);  in drm_buddy_block_trim()
634 	parent = block->parent;  in drm_buddy_block_trim()
635 	block->parent = NULL;  in drm_buddy_block_trim()
637 	new_start = drm_buddy_block_offset(block);  in drm_buddy_block_trim()
638 	list_add(&block->tmp_link, &dfs);  in drm_buddy_block_trim()
641 		mark_allocated(block);  in drm_buddy_block_trim()
642 		mm->avail -= drm_buddy_block_size(mm, block);  in drm_buddy_block_trim()
643 		list_add(&block->link, blocks);  in drm_buddy_block_trim()
646 	block->parent = parent;  in drm_buddy_block_trim()
677 	struct drm_buddy_block *block = NULL;  in drm_buddy_alloc_blocks()  local
720 				block = alloc_range_bias(mm, start, end, order);  in drm_buddy_alloc_blocks()
723 				block = alloc_from_freelist(mm, order, flags);  in drm_buddy_alloc_blocks()
725 			if (!IS_ERR(block))  in drm_buddy_alloc_blocks()
734 		mark_allocated(block);  in drm_buddy_alloc_blocks()
735 		mm->avail -= drm_buddy_block_size(mm, block);  in drm_buddy_alloc_blocks()
736 		kmemleak_update_trace(block);  in drm_buddy_alloc_blocks()
737 		list_add_tail(&block->link, &allocated);  in drm_buddy_alloc_blocks()
762 			   struct drm_buddy_block *block,  in drm_buddy_block_print()  argument
765 	u64 start = drm_buddy_block_offset(block);  in drm_buddy_block_print()
766 	u64 size = drm_buddy_block_size(mm, block);  in drm_buddy_block_print()
786 		struct drm_buddy_block *block;  in drm_buddy_print()  local
789 		list_for_each_entry(block, &mm->free_list[order], link) {  in drm_buddy_print()
790 			BUG_ON(!drm_buddy_block_is_free(block));  in drm_buddy_print()