gpu/drm/drm_buddy.c

19 	struct drm_buddy_block *block;
23 	block = kmem_cache_zalloc(slab_blocks, GFP_KERNEL);
24 	if (!block)
27 	block->header = offset;
28 	block->header |= order;
29 	block->parent = parent;
31 	BUG_ON(block->header & DRM_BUDDY_HEADER_UNUSED);
32 	return block;
36 			   struct drm_buddy_block *block)
38 	kmem_cache_free(slab_blocks, block);
42 			       struct drm_buddy_block *block)
47 	head = &mm->free_list[drm_buddy_block_order(block)];
49 		list_add(&block->link, head);
54 		if (drm_buddy_block_offset(block) < drm_buddy_block_offset(node))
57 	__list_add(&block->link, node->link.prev, &node->link);
60 static void mark_allocated(struct drm_buddy_block *block)
62 	block->header &= ~DRM_BUDDY_HEADER_STATE;
63 	block->header |= DRM_BUDDY_ALLOCATED;
65 	list_del(&block->link);
69 		      struct drm_buddy_block *block)
71 	block->header &= ~DRM_BUDDY_HEADER_STATE;
72 	block->header |= DRM_BUDDY_FREE;
74 	list_insert_sorted(mm, block);
77 static void mark_split(struct drm_buddy_block *block)
79 	block->header &= ~DRM_BUDDY_HEADER_STATE;
80 	block->header |= DRM_BUDDY_SPLIT;
82 	list_del(&block->link);
204 		       struct drm_buddy_block *block)
206 	unsigned int block_order = drm_buddy_block_order(block) - 1;
207 	u64 offset = drm_buddy_block_offset(block);
209 	BUG_ON(!drm_buddy_block_is_free(block));
210 	BUG_ON(!drm_buddy_block_order(block));
212 	block->left = drm_block_alloc(mm, block, block_order, offset);
213 	if (!block->left)
216 	block->right = drm_block_alloc(mm, block, block_order,
218 	if (!block->right) {
219 		drm_block_free(mm, block->left);
223 	mark_free(mm, block->left);
224 	mark_free(mm, block->right);
226 	mark_split(block);
232 __get_buddy(struct drm_buddy_block *block)
236 	parent = block->parent;
240 	if (parent->left == block)
249  * @block: DRM buddy block
251  * Returns the corresponding buddy block for @block, or NULL
252  * if this is a root block and can't be merged further.
257 drm_get_buddy(struct drm_buddy_block *block)
259 	return __get_buddy(block);
264 			     struct drm_buddy_block *block)
268 	while ((parent = block->parent)) {
271 		buddy = __get_buddy(block);
278 		drm_block_free(mm, block);
281 		block = parent;
284 	mark_free(mm, block);
288  * drm_buddy_free_block - free a block
291  * @block: block to be freed
294 			  struct drm_buddy_block *block)
296 	BUG_ON(!drm_buddy_block_is_allocated(block));
297 	mm->avail += drm_buddy_block_size(mm, block);
298 	__drm_buddy_free(mm, block);
310 	struct drm_buddy_block *block, *on;
312 	list_for_each_entry_safe(block, on, objects, link) {
313 		drm_buddy_free_block(mm, block);
336 	struct drm_buddy_block *block;
351 		block = list_first_entry_or_null(&dfs,
354 		if (!block)
357 		list_del(&block->tmp_link);
359 		if (drm_buddy_block_order(block) < order)
362 		block_start = drm_buddy_block_offset(block);
363 		block_end = block_start + drm_buddy_block_size(mm, block) - 1;
368 		if (drm_buddy_block_is_allocated(block))
381 		    order == drm_buddy_block_order(block)) {
383 			 * Find the free block within the range.
385 			if (drm_buddy_block_is_free(block))
386 				return block;
391 		if (!drm_buddy_block_is_split(block)) {
392 			err = split_block(mm, block);
397 		list_add(&block->right->tmp_link, &dfs);
398 		list_add(&block->left->tmp_link, &dfs);
409 	buddy = __get_buddy(block);
411 	    (drm_buddy_block_is_free(block) &&
413 		__drm_buddy_free(mm, block);
448 	struct drm_buddy_block *block = NULL;
453 		block = get_maxblock(mm, order);
454 		if (block)
455 			/* Store the obtained block order */
456 			tmp = drm_buddy_block_order(block);
460 				block = list_last_entry(&mm->free_list[tmp],
463 				if (block)
469 	if (!block)
472 	BUG_ON(!drm_buddy_block_is_free(block));
475 		err = split_block(mm, block);
479 		block = block->right;
482 	return block;
486 		__drm_buddy_free(mm, block);
496 	struct drm_buddy_block *block;
509 		block = list_first_entry_or_null(dfs,
512 		if (!block)
515 		list_del(&block->tmp_link);
517 		block_start = drm_buddy_block_offset(block);
518 		block_end = block_start + drm_buddy_block_size(mm, block) - 1;
523 		if (drm_buddy_block_is_allocated(block)) {
529 			if (!drm_buddy_block_is_free(block)) {
534 			mark_allocated(block);
535 			total_allocated += drm_buddy_block_size(mm, block);
536 			mm->avail -= drm_buddy_block_size(mm, block);
537 			list_add_tail(&block->link, &allocated);
541 		if (!drm_buddy_block_is_split(block)) {
542 			err = split_block(mm, block);
547 		list_add(&block->right->tmp_link, dfs);
548 		list_add(&block->left->tmp_link, dfs);
566 	buddy = __get_buddy(block);
568 	    (drm_buddy_block_is_free(block) &&
570 		__drm_buddy_free(mm, block);
605 	struct drm_buddy_block *block;
623 	list_for_each_entry_reverse(block, list, link) {
625 		rhs_offset = drm_buddy_block_offset(block);
636 		lhs_offset = drm_buddy_block_offset(block) - lhs_size;
659  * MUST contain single block as input to be trimmed.
676 	struct drm_buddy_block *block;
684 	block = list_first_entry(blocks,
688 	if (WARN_ON(!drm_buddy_block_is_allocated(block)))
691 	if (new_size > drm_buddy_block_size(mm, block))
697 	if (new_size == drm_buddy_block_size(mm, block))
700 	list_del(&block->link);
701 	mark_free(mm, block);
702 	mm->avail += drm_buddy_block_size(mm, block);
705 	parent = block->parent;
706 	block->parent = NULL;
708 	new_start = drm_buddy_block_offset(block);
709 	list_add(&block->tmp_link, &dfs);
712 		mark_allocated(block);
713 		mm->avail -= drm_buddy_block_size(mm, block);
714 		list_add(&block->link, blocks);
717 	block->parent = parent;
726  * @start: start of the allowed range for this block
727  * @end: end of the allowed range for this block
734  * the tree and returns the desired block.
737  * are enforced, which picks the block from the freelist.
748 	struct drm_buddy_block *block = NULL;
805 				block = alloc_range_bias(mm, start, end, order);
808 				block = alloc_from_freelist(mm, order, flags);
810 			if (!IS_ERR(block))
817 					 * Try contiguous block allocation through
829 		mark_allocated(block);
830 		mm->avail -= drm_buddy_block_size(mm, block);
831 		kmemleak_update_trace(block);
832 		list_add_tail(&block->link, &allocated);
840 	/* Trim the allocated block to the required size */
850 			block = list_last_entry(&allocated, typeof(*block), link);
851 			list_move(&block->link, &temp);
853 			trim_size = drm_buddy_block_size(mm, block) -
875  * drm_buddy_block_print - print block information
878  * @block: DRM buddy block
882 			   struct drm_buddy_block *block,
885 	u64 start = drm_buddy_block_offset(block);
886 	u64 size = drm_buddy_block_size(mm, block);
906 		struct drm_buddy_block *block;
909 		list_for_each_entry(block, &mm->free_list[order], link) {
910 			BUG_ON(!drm_buddy_block_is_free(block));