Lines Matching full:block
39 gpu_buddy_block_state(struct gpu_buddy_block *block) in gpu_buddy_block_state() argument
41 return block->header & GPU_BUDDY_HEADER_STATE; in gpu_buddy_block_state()
45 gpu_buddy_block_is_allocated(struct gpu_buddy_block *block) in gpu_buddy_block_is_allocated() argument
47 return gpu_buddy_block_state(block) == GPU_BUDDY_ALLOCATED; in gpu_buddy_block_is_allocated()
51 gpu_buddy_block_is_split(struct gpu_buddy_block *block) in gpu_buddy_block_is_split() argument
53 return gpu_buddy_block_state(block) == GPU_BUDDY_SPLIT; in gpu_buddy_block_is_split()
56 static unsigned int gpu_buddy_block_offset_alignment(struct gpu_buddy_block *block) in gpu_buddy_block_offset_alignment() argument
58 u64 offset = gpu_buddy_block_offset(block); in gpu_buddy_block_offset_alignment()
80 struct gpu_buddy_block *block; in gpu_block_alloc() local
84 block = kmem_cache_zalloc(slab_blocks, GFP_KERNEL); in gpu_block_alloc()
85 if (!block) in gpu_block_alloc()
88 block->header = offset; in gpu_block_alloc()
89 block->header |= order; in gpu_block_alloc()
90 block->parent = parent; in gpu_block_alloc()
92 RB_CLEAR_NODE(&block->rb); in gpu_block_alloc()
94 BUG_ON(block->header & GPU_BUDDY_HEADER_UNUSED); in gpu_block_alloc()
95 return block; in gpu_block_alloc()
99 struct gpu_buddy_block *block) in gpu_block_free() argument
101 kmem_cache_free(slab_blocks, block); in gpu_block_free()
105 get_block_tree(struct gpu_buddy_block *block) in get_block_tree() argument
107 return gpu_buddy_block_is_clear(block) ? in get_block_tree()
129 struct gpu_buddy_block *block, in rbtree_insert() argument
137 order = gpu_buddy_block_order(block); in rbtree_insert()
138 block_alignment = gpu_buddy_block_offset_alignment(block); in rbtree_insert()
155 if (gpu_buddy_block_offset(block) < gpu_buddy_block_offset(node)) in rbtree_insert()
161 block->subtree_max_alignment = block_alignment; in rbtree_insert()
162 rb_link_node(&block->rb, parent, link); in rbtree_insert()
163 rb_insert_augmented(&block->rb, root, &gpu_buddy_augment_cb); in rbtree_insert()
167 struct gpu_buddy_block *block) in rbtree_remove() argument
169 unsigned int order = gpu_buddy_block_order(block); in rbtree_remove()
173 tree = get_block_tree(block); in rbtree_remove()
176 rb_erase_augmented(&block->rb, root, &gpu_buddy_augment_cb); in rbtree_remove()
177 RB_CLEAR_NODE(&block->rb); in rbtree_remove()
180 static void clear_reset(struct gpu_buddy_block *block) in clear_reset() argument
182 block->header &= ~GPU_BUDDY_HEADER_CLEAR; in clear_reset()
185 static void mark_cleared(struct gpu_buddy_block *block) in mark_cleared() argument
187 block->header |= GPU_BUDDY_HEADER_CLEAR; in mark_cleared()
191 struct gpu_buddy_block *block) in mark_allocated() argument
193 block->header &= ~GPU_BUDDY_HEADER_STATE; in mark_allocated()
194 block->header |= GPU_BUDDY_ALLOCATED; in mark_allocated()
196 rbtree_remove(mm, block); in mark_allocated()
200 struct gpu_buddy_block *block) in mark_free() argument
204 block->header &= ~GPU_BUDDY_HEADER_STATE; in mark_free()
205 block->header |= GPU_BUDDY_FREE; in mark_free()
207 tree = get_block_tree(block); in mark_free()
208 rbtree_insert(mm, block, tree); in mark_free()
212 struct gpu_buddy_block *block) in mark_split() argument
214 block->header &= ~GPU_BUDDY_HEADER_STATE; in mark_split()
215 block->header |= GPU_BUDDY_SPLIT; in mark_split()
217 rbtree_remove(mm, block); in mark_split()
231 __get_buddy(struct gpu_buddy_block *block) in __get_buddy() argument
235 parent = block->parent; in __get_buddy()
239 if (parent->left == block) in __get_buddy()
246 struct gpu_buddy_block *block, in __gpu_buddy_free() argument
252 while ((parent = block->parent)) { in __gpu_buddy_free()
255 buddy = __get_buddy(block); in __gpu_buddy_free()
262 * Check the block and its buddy clear state and exit in __gpu_buddy_free()
265 if (gpu_buddy_block_is_clear(block) != in __gpu_buddy_free()
269 if (gpu_buddy_block_is_clear(block)) in __gpu_buddy_free()
277 gpu_block_free(mm, block); in __gpu_buddy_free()
280 block = parent; in __gpu_buddy_free()
283 order = gpu_buddy_block_order(block); in __gpu_buddy_free()
284 mark_free(mm, block); in __gpu_buddy_free()
308 struct gpu_buddy_block *block, *buddy; in __force_merge() local
311 block = rbtree_get_free_block(iter); in __force_merge()
314 if (!block || !block->parent) in __force_merge()
317 block_start = gpu_buddy_block_offset(block); in __force_merge()
318 block_end = block_start + gpu_buddy_block_size(mm, block) - 1; in __force_merge()
323 buddy = __get_buddy(block); in __force_merge()
327 gpu_buddy_assert(gpu_buddy_block_is_clear(block) != in __force_merge()
332 * as freeing the block will also remove its buddy from the tree. in __force_merge()
337 rbtree_remove(mm, block); in __force_merge()
338 if (gpu_buddy_block_is_clear(block)) in __force_merge()
339 mm->clear_avail -= gpu_buddy_block_size(mm, block); in __force_merge()
341 order = __gpu_buddy_free(mm, block, true); in __force_merge()
495 struct gpu_buddy_block *block) in split_block() argument
497 unsigned int block_order = gpu_buddy_block_order(block) - 1; in split_block()
498 u64 offset = gpu_buddy_block_offset(block); in split_block()
500 BUG_ON(!gpu_buddy_block_is_free(block)); in split_block()
501 BUG_ON(!gpu_buddy_block_order(block)); in split_block()
503 block->left = gpu_block_alloc(mm, block, block_order, offset); in split_block()
504 if (!block->left) in split_block()
507 block->right = gpu_block_alloc(mm, block, block_order, in split_block()
509 if (!block->right) { in split_block()
510 gpu_block_free(mm, block->left); in split_block()
514 mark_split(mm, block); in split_block()
516 if (gpu_buddy_block_is_clear(block)) { in split_block()
517 mark_cleared(block->left); in split_block()
518 mark_cleared(block->right); in split_block()
519 clear_reset(block); in split_block()
522 mark_free(mm, block->left); in split_block()
523 mark_free(mm, block->right); in split_block()
534 * Reset the clear state based on @is_clear value for each block
560 struct gpu_buddy_block *block, *tmp; in gpu_buddy_reset_clear() local
562 rbtree_postorder_for_each_entry_safe(block, tmp, root, rb) { in gpu_buddy_reset_clear()
563 rbtree_remove(mm, block); in gpu_buddy_reset_clear()
565 mark_cleared(block); in gpu_buddy_reset_clear()
566 mm->clear_avail += gpu_buddy_block_size(mm, block); in gpu_buddy_reset_clear()
568 clear_reset(block); in gpu_buddy_reset_clear()
569 mm->clear_avail -= gpu_buddy_block_size(mm, block); in gpu_buddy_reset_clear()
572 rbtree_insert(mm, block, dst_tree); in gpu_buddy_reset_clear()
579 * gpu_buddy_free_block - free a block
582 * @block: block to be freed
585 struct gpu_buddy_block *block) in gpu_buddy_free_block() argument
588 BUG_ON(!gpu_buddy_block_is_allocated(block)); in gpu_buddy_free_block()
589 mm->avail += gpu_buddy_block_size(mm, block); in gpu_buddy_free_block()
590 if (gpu_buddy_block_is_clear(block)) in gpu_buddy_free_block()
591 mm->clear_avail += gpu_buddy_block_size(mm, block); in gpu_buddy_free_block()
593 __gpu_buddy_free(mm, block, false); in gpu_buddy_free_block()
602 struct gpu_buddy_block *block, *on; in __gpu_buddy_free_list() local
606 list_for_each_entry_safe(block, on, objects, link) { in __gpu_buddy_free_list()
608 mark_cleared(block); in __gpu_buddy_free_list()
610 clear_reset(block); in __gpu_buddy_free_list()
611 gpu_buddy_free_block(mm, block); in __gpu_buddy_free_list()
646 static bool block_incompatible(struct gpu_buddy_block *block, unsigned int flags) in block_incompatible() argument
650 return needs_clear != gpu_buddy_block_is_clear(block); in block_incompatible()
661 struct gpu_buddy_block *block; in __alloc_range_bias() local
676 block = list_first_entry_or_null(&dfs, in __alloc_range_bias()
679 if (!block) in __alloc_range_bias()
682 list_del(&block->tmp_link); in __alloc_range_bias()
684 if (gpu_buddy_block_order(block) < order) in __alloc_range_bias()
687 block_start = gpu_buddy_block_offset(block); in __alloc_range_bias()
688 block_end = block_start + gpu_buddy_block_size(mm, block) - 1; in __alloc_range_bias()
693 if (gpu_buddy_block_is_allocated(block)) in __alloc_range_bias()
705 if (!fallback && block_incompatible(block, flags)) in __alloc_range_bias()
709 order == gpu_buddy_block_order(block)) { in __alloc_range_bias()
711 * Find the free block within the range. in __alloc_range_bias()
713 if (gpu_buddy_block_is_free(block)) in __alloc_range_bias()
714 return block; in __alloc_range_bias()
719 if (!gpu_buddy_block_is_split(block)) { in __alloc_range_bias()
720 err = split_block(mm, block); in __alloc_range_bias()
725 list_add(&block->right->tmp_link, &dfs); in __alloc_range_bias()
726 list_add(&block->left->tmp_link, &dfs); in __alloc_range_bias()
737 buddy = __get_buddy(block); in __alloc_range_bias()
739 (gpu_buddy_block_is_free(block) && in __alloc_range_bias()
741 __gpu_buddy_free(mm, block, false); in __alloc_range_bias()
751 struct gpu_buddy_block *block; in __gpu_buddy_alloc_range_bias() local
754 block = __alloc_range_bias(mm, start, end, order, in __gpu_buddy_alloc_range_bias()
756 if (IS_ERR(block)) in __gpu_buddy_alloc_range_bias()
760 return block; in __gpu_buddy_alloc_range_bias()
768 struct gpu_buddy_block *max_block = NULL, *block = NULL; in get_maxblock() local
774 block = rbtree_last_free_block(root); in get_maxblock()
775 if (!block) in get_maxblock()
779 max_block = block; in get_maxblock()
783 if (gpu_buddy_block_offset(block) > in get_maxblock()
785 max_block = block; in get_maxblock()
797 struct gpu_buddy_block *block = NULL; in alloc_from_freetree() local
807 block = get_maxblock(mm, order, tree); in alloc_from_freetree()
808 if (block) in alloc_from_freetree()
809 /* Store the obtained block order */ in alloc_from_freetree()
810 tmp = gpu_buddy_block_order(block); in alloc_from_freetree()
815 block = rbtree_last_free_block(root); in alloc_from_freetree()
816 if (block) in alloc_from_freetree()
821 if (!block) { in alloc_from_freetree()
828 block = rbtree_last_free_block(root); in alloc_from_freetree()
829 if (block) in alloc_from_freetree()
833 if (!block) in alloc_from_freetree()
837 BUG_ON(!gpu_buddy_block_is_free(block)); in alloc_from_freetree()
840 err = split_block(mm, block); in alloc_from_freetree()
844 block = block->right; in alloc_from_freetree()
847 return block; in alloc_from_freetree()
851 __gpu_buddy_free(mm, block, false); in alloc_from_freetree()
864 struct gpu_buddy_block *block; in gpu_buddy_subtree_can_satisfy() local
866 block = rbtree_get_free_block(node); in gpu_buddy_subtree_can_satisfy()
867 return block->subtree_max_alignment >= alignment; in gpu_buddy_subtree_can_satisfy()
881 struct gpu_buddy_block *block = rbtree_get_free_block(rb); in gpu_buddy_find_block_aligned() local
891 if (gpu_buddy_block_offset_alignment(block) >= alignment) in gpu_buddy_find_block_aligned()
892 return block; in gpu_buddy_find_block_aligned()
913 struct gpu_buddy_block *block = NULL; in gpu_buddy_offset_aligned_allocation() local
928 block = gpu_buddy_find_block_aligned(mm, tree, tmp, in gpu_buddy_offset_aligned_allocation()
930 if (!block) { in gpu_buddy_offset_aligned_allocation()
933 block = gpu_buddy_find_block_aligned(mm, tree, tmp, in gpu_buddy_offset_aligned_allocation()
937 if (block) in gpu_buddy_offset_aligned_allocation()
941 if (!block) in gpu_buddy_offset_aligned_allocation()
944 while (gpu_buddy_block_order(block) > order) { in gpu_buddy_offset_aligned_allocation()
947 err = split_block(mm, block); in gpu_buddy_offset_aligned_allocation()
951 left = block->left; in gpu_buddy_offset_aligned_allocation()
952 right = block->right; in gpu_buddy_offset_aligned_allocation()
955 block = right; in gpu_buddy_offset_aligned_allocation()
957 block = left; in gpu_buddy_offset_aligned_allocation()
960 return block; in gpu_buddy_offset_aligned_allocation()
968 buddy = __get_buddy(block); in gpu_buddy_offset_aligned_allocation()
970 (gpu_buddy_block_is_free(block) && in gpu_buddy_offset_aligned_allocation()
972 __gpu_buddy_free(mm, block, false); in gpu_buddy_offset_aligned_allocation()
982 struct gpu_buddy_block *block; in __alloc_range() local
995 block = list_first_entry_or_null(dfs, in __alloc_range()
998 if (!block) in __alloc_range()
1001 list_del(&block->tmp_link); in __alloc_range()
1003 block_start = gpu_buddy_block_offset(block); in __alloc_range()
1004 block_end = block_start + gpu_buddy_block_size(mm, block) - 1; in __alloc_range()
1009 if (gpu_buddy_block_is_allocated(block)) { in __alloc_range()
1015 if (gpu_buddy_block_is_free(block)) { in __alloc_range()
1016 mark_allocated(mm, block); in __alloc_range()
1017 total_allocated += gpu_buddy_block_size(mm, block); in __alloc_range()
1018 mm->avail -= gpu_buddy_block_size(mm, block); in __alloc_range()
1019 if (gpu_buddy_block_is_clear(block)) in __alloc_range()
1020 mm->clear_avail -= gpu_buddy_block_size(mm, block); in __alloc_range()
1021 list_add_tail(&block->link, &allocated); in __alloc_range()
1029 if (!gpu_buddy_block_is_split(block)) { in __alloc_range()
1030 err = split_block(mm, block); in __alloc_range()
1035 list_add(&block->right->tmp_link, dfs); in __alloc_range()
1036 list_add(&block->left->tmp_link, dfs); in __alloc_range()
1054 buddy = __get_buddy(block); in __alloc_range()
1056 (gpu_buddy_block_is_free(block) && in __alloc_range()
1058 __gpu_buddy_free(mm, block, false); in __alloc_range()
1104 struct gpu_buddy_block *block; in __alloc_contig_try_harder() local
1124 block = rbtree_get_free_block(iter); in __alloc_contig_try_harder()
1126 rhs_offset = gpu_buddy_block_offset(block); in __alloc_contig_try_harder()
1182 * MUST contain single block as input to be trimmed.
1200 struct gpu_buddy_block *block; in gpu_buddy_block_trim() local
1211 block = list_first_entry(blocks, in gpu_buddy_block_trim()
1215 block_start = gpu_buddy_block_offset(block); in gpu_buddy_block_trim()
1216 block_end = block_start + gpu_buddy_block_size(mm, block); in gpu_buddy_block_trim()
1218 if (WARN_ON(!gpu_buddy_block_is_allocated(block))) in gpu_buddy_block_trim()
1221 if (new_size > gpu_buddy_block_size(mm, block)) in gpu_buddy_block_trim()
1227 if (new_size == gpu_buddy_block_size(mm, block)) in gpu_buddy_block_trim()
1244 list_del(&block->link); in gpu_buddy_block_trim()
1245 mark_free(mm, block); in gpu_buddy_block_trim()
1246 mm->avail += gpu_buddy_block_size(mm, block); in gpu_buddy_block_trim()
1247 if (gpu_buddy_block_is_clear(block)) in gpu_buddy_block_trim()
1248 mm->clear_avail += gpu_buddy_block_size(mm, block); in gpu_buddy_block_trim()
1251 parent = block->parent; in gpu_buddy_block_trim()
1252 block->parent = NULL; in gpu_buddy_block_trim()
1254 list_add(&block->tmp_link, &dfs); in gpu_buddy_block_trim()
1257 mark_allocated(mm, block); in gpu_buddy_block_trim()
1258 mm->avail -= gpu_buddy_block_size(mm, block); in gpu_buddy_block_trim()
1259 if (gpu_buddy_block_is_clear(block)) in gpu_buddy_block_trim()
1260 mm->clear_avail -= gpu_buddy_block_size(mm, block); in gpu_buddy_block_trim()
1261 list_add(&block->link, blocks); in gpu_buddy_block_trim()
1264 block->parent = parent; in gpu_buddy_block_trim()
1294 * @start: start of the allowed range for this block
1295 * @end: end of the allowed range for this block
1302 * the tree and returns the desired block.
1305 * are enforced, which picks the block from the freetree.
1316 struct gpu_buddy_block *block = NULL; in gpu_buddy_alloc_blocks() local
1391 block = __gpu_buddy_alloc_blocks(mm, start, in gpu_buddy_alloc_blocks()
1397 if (!IS_ERR(block)) in gpu_buddy_alloc_blocks()
1412 block = __gpu_buddy_alloc_blocks(mm, start, in gpu_buddy_alloc_blocks()
1418 if (!IS_ERR(block)) { in gpu_buddy_alloc_blocks()
1425 * Try contiguous block allocation through in gpu_buddy_alloc_blocks()
1438 mark_allocated(mm, block); in gpu_buddy_alloc_blocks()
1439 mm->avail -= gpu_buddy_block_size(mm, block); in gpu_buddy_alloc_blocks()
1440 if (gpu_buddy_block_is_clear(block)) in gpu_buddy_alloc_blocks()
1441 mm->clear_avail -= gpu_buddy_block_size(mm, block); in gpu_buddy_alloc_blocks()
1442 kmemleak_update_trace(block); in gpu_buddy_alloc_blocks()
1443 list_add_tail(&block->link, &allocated); in gpu_buddy_alloc_blocks()
1451 /* Trim the allocated block to the required size */ in gpu_buddy_alloc_blocks()
1462 block = list_last_entry(&allocated, typeof(*block), link); in gpu_buddy_alloc_blocks()
1463 list_move(&block->link, &temp); in gpu_buddy_alloc_blocks()
1465 trim_size = gpu_buddy_block_size(mm, block) - in gpu_buddy_alloc_blocks()
1488 * gpu_buddy_block_print - print block information
1491 * @block: GPU buddy block
1494 struct gpu_buddy_block *block) in gpu_buddy_block_print() argument
1496 u64 start = gpu_buddy_block_offset(block); in gpu_buddy_block_print()
1497 u64 size = gpu_buddy_block_size(mm, block); in gpu_buddy_block_print()
1518 struct gpu_buddy_block *block, *tmp; in gpu_buddy_print() local
1526 rbtree_postorder_for_each_entry_safe(block, tmp, root, rb) { in gpu_buddy_print()
1527 BUG_ON(!gpu_buddy_block_is_free(block)); in gpu_buddy_print()