Lines Matching +full:left +full:- +full:input +full:- +full:single +full:- +full:end
1 // SPDX-License-Identifier: MIT
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()
47 head = &mm->free_list[drm_buddy_block_order(block)]; in list_insert_sorted()
49 list_add(&block->link, head); in list_insert_sorted()
57 __list_add(&block->link, node->link.prev, &node->link); in list_insert_sorted()
62 block->header &= ~DRM_BUDDY_HEADER_CLEAR; in clear_reset()
67 block->header |= DRM_BUDDY_HEADER_CLEAR; in mark_cleared()
72 block->header &= ~DRM_BUDDY_HEADER_STATE; in mark_allocated()
73 block->header |= DRM_BUDDY_ALLOCATED; in mark_allocated()
75 list_del(&block->link); in mark_allocated()
81 block->header &= ~DRM_BUDDY_HEADER_STATE; in mark_free()
82 block->header |= DRM_BUDDY_FREE; in mark_free()
89 block->header &= ~DRM_BUDDY_HEADER_STATE; in mark_split()
90 block->header |= DRM_BUDDY_SPLIT; in mark_split()
92 list_del(&block->link); in mark_split()
110 parent = block->parent; in __get_buddy()
114 if (parent->left == block) in __get_buddy()
115 return parent->right; in __get_buddy()
117 return parent->left; in __get_buddy()
127 while ((parent = block->parent)) { in __drm_buddy_free()
148 list_del(&buddy->link); in __drm_buddy_free()
150 mm->clear_avail -= drm_buddy_block_size(mm, buddy); in __drm_buddy_free()
166 u64 end, in __force_merge() argument
173 return -ENOMEM; in __force_merge()
175 if (min_order > mm->max_order) in __force_merge()
176 return -EINVAL; in __force_merge()
178 for (i = min_order - 1; i >= 0; i--) { in __force_merge()
181 list_for_each_entry_safe_reverse(block, prev, &mm->free_list[i], link) { in __force_merge()
185 if (!block->parent) in __force_merge()
189 block_end = block_start + drm_buddy_block_size(mm, block) - 1; in __force_merge()
191 if (!contains(start, end, block_start, block_end)) in __force_merge()
209 list_del(&block->link); in __force_merge()
211 mm->clear_avail -= drm_buddy_block_size(mm, block); in __force_merge()
219 return -ENOMEM; in __force_merge()
223 * drm_buddy_init - init memory manager
240 return -EINVAL; in drm_buddy_init()
243 return -EINVAL; in drm_buddy_init()
246 return -EINVAL; in drm_buddy_init()
250 mm->size = size; in drm_buddy_init()
251 mm->avail = size; in drm_buddy_init()
252 mm->clear_avail = 0; in drm_buddy_init()
253 mm->chunk_size = chunk_size; in drm_buddy_init()
254 mm->max_order = ilog2(size) - ilog2(chunk_size); in drm_buddy_init()
256 BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER); in drm_buddy_init()
258 mm->free_list = kmalloc_array(mm->max_order + 1, in drm_buddy_init()
261 if (!mm->free_list) in drm_buddy_init()
262 return -ENOMEM; in drm_buddy_init()
264 for (i = 0; i <= mm->max_order; ++i) in drm_buddy_init()
265 INIT_LIST_HEAD(&mm->free_list[i]); in drm_buddy_init()
267 mm->n_roots = hweight64(size); in drm_buddy_init()
269 mm->roots = kmalloc_array(mm->n_roots, in drm_buddy_init()
272 if (!mm->roots) in drm_buddy_init()
279 * Split into power-of-two blocks, in case we are given a size that is in drm_buddy_init()
280 * not itself a power-of-two. in drm_buddy_init()
287 order = ilog2(size) - ilog2(chunk_size); in drm_buddy_init()
296 BUG_ON(i > mm->max_order); in drm_buddy_init()
299 mm->roots[i] = root; in drm_buddy_init()
302 size -= root_size; in drm_buddy_init()
309 while (i--) in drm_buddy_init()
310 drm_block_free(mm, mm->roots[i]); in drm_buddy_init()
311 kfree(mm->roots); in drm_buddy_init()
313 kfree(mm->free_list); in drm_buddy_init()
314 return -ENOMEM; in drm_buddy_init()
319 * drm_buddy_fini - tear down the memory manager
331 size = mm->size; in drm_buddy_fini()
333 for (i = 0; i < mm->n_roots; ++i) { in drm_buddy_fini()
334 order = ilog2(size) - ilog2(mm->chunk_size); in drm_buddy_fini()
337 WARN_ON(!drm_buddy_block_is_free(mm->roots[i])); in drm_buddy_fini()
338 drm_block_free(mm, mm->roots[i]); in drm_buddy_fini()
340 root_size = mm->chunk_size << order; in drm_buddy_fini()
341 size -= root_size; in drm_buddy_fini()
344 WARN_ON(mm->avail != mm->size); in drm_buddy_fini()
346 kfree(mm->roots); in drm_buddy_fini()
347 kfree(mm->free_list); in drm_buddy_fini()
354 unsigned int block_order = drm_buddy_block_order(block) - 1; in split_block()
360 block->left = drm_block_alloc(mm, block, block_order, offset); in split_block()
361 if (!block->left) in split_block()
362 return -ENOMEM; in split_block()
364 block->right = drm_block_alloc(mm, block, block_order, in split_block()
365 offset + (mm->chunk_size << block_order)); in split_block()
366 if (!block->right) { in split_block()
367 drm_block_free(mm, block->left); in split_block()
368 return -ENOMEM; in split_block()
371 mark_free(mm, block->left); in split_block()
372 mark_free(mm, block->right); in split_block()
375 mark_cleared(block->left); in split_block()
376 mark_cleared(block->right); in split_block()
386 * drm_get_buddy - get buddy address
403 * drm_buddy_free_block - free a block
412 mm->avail += drm_buddy_block_size(mm, block); in drm_buddy_free_block()
414 mm->clear_avail += drm_buddy_block_size(mm, block); in drm_buddy_free_block()
452 * drm_buddy_free_list - free blocks
455 * @objects: input list head to free blocks
477 u64 start, u64 end, in __alloc_range_bias() argument
482 u64 req_size = mm->chunk_size << order; in __alloc_range_bias()
489 end = end - 1; in __alloc_range_bias()
491 for (i = 0; i < mm->n_roots; ++i) in __alloc_range_bias()
492 list_add_tail(&mm->roots[i]->tmp_link, &dfs); in __alloc_range_bias()
504 list_del(&block->tmp_link); in __alloc_range_bias()
510 block_end = block_start + drm_buddy_block_size(mm, block) - 1; in __alloc_range_bias()
512 if (!overlaps(start, end, block_start, block_end)) in __alloc_range_bias()
518 if (block_start < start || block_end > end) { in __alloc_range_bias()
520 u64 adjusted_end = min(block_end, end); in __alloc_range_bias()
530 if (contains(start, end, block_start, block_end) && in __alloc_range_bias()
547 list_add(&block->right->tmp_link, &dfs); in __alloc_range_bias()
548 list_add(&block->left->tmp_link, &dfs); in __alloc_range_bias()
551 return ERR_PTR(-ENOSPC); in __alloc_range_bias()
569 u64 start, u64 end, in __drm_buddy_alloc_range_bias() argument
576 block = __alloc_range_bias(mm, start, end, order, in __drm_buddy_alloc_range_bias()
579 return __alloc_range_bias(mm, start, end, order, in __drm_buddy_alloc_range_bias()
592 for (i = order; i <= mm->max_order; ++i) { in get_maxblock()
595 list_for_each_entry_reverse(tmp_block, &mm->free_list[i], link) { in get_maxblock()
635 for (tmp = order; tmp <= mm->max_order; ++tmp) { in alloc_from_freelist()
638 list_for_each_entry_reverse(tmp_block, &mm->free_list[tmp], link) { in alloc_from_freelist()
653 for (tmp = order; tmp <= mm->max_order; ++tmp) { in alloc_from_freelist()
654 if (!list_empty(&mm->free_list[tmp])) { in alloc_from_freelist()
655 block = list_last_entry(&mm->free_list[tmp], in alloc_from_freelist()
664 return ERR_PTR(-ENOSPC); in alloc_from_freelist()
674 block = block->right; in alloc_from_freelist()
675 tmp--; in alloc_from_freelist()
695 u64 end; in __alloc_range() local
698 end = start + size - 1; in __alloc_range()
710 list_del(&block->tmp_link); in __alloc_range()
713 block_end = block_start + drm_buddy_block_size(mm, block) - 1; in __alloc_range()
715 if (!overlaps(start, end, block_start, block_end)) in __alloc_range()
719 err = -ENOSPC; in __alloc_range()
723 if (contains(start, end, block_start, block_end)) { in __alloc_range()
727 mm->avail -= drm_buddy_block_size(mm, block); in __alloc_range()
729 mm->clear_avail -= drm_buddy_block_size(mm, block); in __alloc_range()
730 list_add_tail(&block->link, &allocated); in __alloc_range()
732 } else if (!mm->clear_avail) { in __alloc_range()
733 err = -ENOSPC; in __alloc_range()
744 list_add(&block->right->tmp_link, dfs); in __alloc_range()
745 list_add(&block->left->tmp_link, dfs); in __alloc_range()
749 err = -ENOSPC; in __alloc_range()
770 if (err == -ENOSPC && total_allocated_on_err) { in __alloc_range()
789 for (i = 0; i < mm->n_roots; ++i) in __drm_buddy_alloc_range()
790 list_add_tail(&mm->roots[i]->tmp_link, &dfs); in __drm_buddy_alloc_range()
811 pages = modify_size >> ilog2(mm->chunk_size); in __alloc_contig_try_harder()
812 order = fls(pages) - 1; in __alloc_contig_try_harder()
814 return -ENOSPC; in __alloc_contig_try_harder()
816 list = &mm->free_list[order]; in __alloc_contig_try_harder()
818 return -ENOSPC; in __alloc_contig_try_harder()
825 if (!err || err != -ENOSPC) in __alloc_contig_try_harder()
828 lhs_size = max((size - filled), min_block_size); in __alloc_contig_try_harder()
833 lhs_offset = drm_buddy_block_offset(block) - lhs_size; in __alloc_contig_try_harder()
839 } else if (err != -ENOSPC) { in __alloc_contig_try_harder()
847 return -ENOSPC; in __alloc_contig_try_harder()
851 * drm_buddy_block_trim - free unused pages
856 * @blocks: Input and output list of allocated blocks.
857 * MUST contain single block as input to be trimmed.
882 return -EINVAL; in drm_buddy_block_trim()
892 return -EINVAL; in drm_buddy_block_trim()
895 return -EINVAL; in drm_buddy_block_trim()
897 if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size)) in drm_buddy_block_trim()
898 return -EINVAL; in drm_buddy_block_trim()
908 return -EINVAL; in drm_buddy_block_trim()
910 if (!IS_ALIGNED(new_start, mm->chunk_size)) in drm_buddy_block_trim()
911 return -EINVAL; in drm_buddy_block_trim()
914 return -EINVAL; in drm_buddy_block_trim()
917 list_del(&block->link); in drm_buddy_block_trim()
919 mm->avail += drm_buddy_block_size(mm, block); in drm_buddy_block_trim()
921 mm->clear_avail += drm_buddy_block_size(mm, block); in drm_buddy_block_trim()
924 parent = block->parent; in drm_buddy_block_trim()
925 block->parent = NULL; in drm_buddy_block_trim()
927 list_add(&block->tmp_link, &dfs); in drm_buddy_block_trim()
931 mm->avail -= drm_buddy_block_size(mm, block); in drm_buddy_block_trim()
933 mm->clear_avail -= drm_buddy_block_size(mm, block); in drm_buddy_block_trim()
934 list_add(&block->link, blocks); in drm_buddy_block_trim()
937 block->parent = parent; in drm_buddy_block_trim()
944 u64 start, u64 end, in __drm_buddy_alloc_blocks() argument
950 return __drm_buddy_alloc_range_bias(mm, start, end, in __drm_buddy_alloc_blocks()
958 * drm_buddy_alloc_blocks - allocate power-of-two blocks
962 * @end: end of the allowed range for this block
978 u64 start, u64 end, u64 size, in drm_buddy_alloc_blocks() argument
990 if (size < mm->chunk_size) in drm_buddy_alloc_blocks()
991 return -EINVAL; in drm_buddy_alloc_blocks()
993 if (min_block_size < mm->chunk_size) in drm_buddy_alloc_blocks()
994 return -EINVAL; in drm_buddy_alloc_blocks()
997 return -EINVAL; in drm_buddy_alloc_blocks()
999 if (!IS_ALIGNED(start | end | size, mm->chunk_size)) in drm_buddy_alloc_blocks()
1000 return -EINVAL; in drm_buddy_alloc_blocks()
1002 if (end > mm->size) in drm_buddy_alloc_blocks()
1003 return -EINVAL; in drm_buddy_alloc_blocks()
1005 if (range_overflows(start, size, mm->size)) in drm_buddy_alloc_blocks()
1006 return -EINVAL; in drm_buddy_alloc_blocks()
1009 if (start + size == end) { in drm_buddy_alloc_blocks()
1010 if (!IS_ALIGNED(start | end, min_block_size)) in drm_buddy_alloc_blocks()
1011 return -EINVAL; in drm_buddy_alloc_blocks()
1028 pages = size >> ilog2(mm->chunk_size); in drm_buddy_alloc_blocks()
1029 order = fls(pages) - 1; in drm_buddy_alloc_blocks()
1030 min_order = ilog2(min_block_size) - ilog2(mm->chunk_size); in drm_buddy_alloc_blocks()
1033 order = min(order, (unsigned int)fls(pages) - 1); in drm_buddy_alloc_blocks()
1034 BUG_ON(order > mm->max_order); in drm_buddy_alloc_blocks()
1039 end, in drm_buddy_alloc_blocks()
1045 if (order-- == min_order) { in drm_buddy_alloc_blocks()
1047 if (mm->clear_avail && in drm_buddy_alloc_blocks()
1048 !__force_merge(mm, start, end, min_order)) { in drm_buddy_alloc_blocks()
1050 end, in drm_buddy_alloc_blocks()
1069 err = -ENOSPC; in drm_buddy_alloc_blocks()
1075 mm->avail -= drm_buddy_block_size(mm, block); in drm_buddy_alloc_blocks()
1077 mm->clear_avail -= drm_buddy_block_size(mm, block); in drm_buddy_alloc_blocks()
1079 list_add_tail(&block->link, &allocated); in drm_buddy_alloc_blocks()
1081 pages -= BIT(order); in drm_buddy_alloc_blocks()
1099 list_move(&block->link, &temp); in drm_buddy_alloc_blocks()
1101 trim_size = drm_buddy_block_size(mm, block) - in drm_buddy_alloc_blocks()
1102 (size - original_size); in drm_buddy_alloc_blocks()
1124 * drm_buddy_block_print - print block information
1137 drm_printf(p, "%#018llx-%#018llx: %llu\n", start, start + size, size); in drm_buddy_block_print()
1142 * drm_buddy_print - print allocator state
1152 mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20, mm->clear_avail >> 20); in drm_buddy_print()
1154 for (order = mm->max_order; order >= 0; order--) { in drm_buddy_print()
1158 list_for_each_entry(block, &mm->free_list[order], link) { in drm_buddy_print()
1163 drm_printf(p, "order-%2d ", order); in drm_buddy_print()
1165 free = count * (mm->chunk_size << order); in drm_buddy_print()
1185 return -ENOMEM; in drm_buddy_module_init()