Lines Matching +full:mm +full:- +full:0
1 // SPDX-License-Identifier: MIT
6 #include <kunit/test-bug.h>
16 static struct drm_buddy_block *drm_block_alloc(struct drm_buddy *mm, in drm_block_alloc() argument
29 block->header = offset; in drm_block_alloc()
30 block->header |= order; in drm_block_alloc()
31 block->parent = parent; in drm_block_alloc()
33 BUG_ON(block->header & DRM_BUDDY_HEADER_UNUSED); in drm_block_alloc()
37 static void drm_block_free(struct drm_buddy *mm, in drm_block_free() argument
43 static void list_insert_sorted(struct drm_buddy *mm, in list_insert_sorted() argument
49 head = &mm->free_list[drm_buddy_block_order(block)]; in list_insert_sorted()
51 list_add(&block->link, head); in list_insert_sorted()
59 __list_add(&block->link, node->link.prev, &node->link); in list_insert_sorted()
64 block->header &= ~DRM_BUDDY_HEADER_CLEAR; in clear_reset()
69 block->header |= DRM_BUDDY_HEADER_CLEAR; in mark_cleared()
74 block->header &= ~DRM_BUDDY_HEADER_STATE; in mark_allocated()
75 block->header |= DRM_BUDDY_ALLOCATED; in mark_allocated()
77 list_del(&block->link); in mark_allocated()
80 static void mark_free(struct drm_buddy *mm, in mark_free() argument
83 block->header &= ~DRM_BUDDY_HEADER_STATE; in mark_free()
84 block->header |= DRM_BUDDY_FREE; in mark_free()
86 list_insert_sorted(mm, block); in mark_free()
91 block->header &= ~DRM_BUDDY_HEADER_STATE; in mark_split()
92 block->header |= DRM_BUDDY_SPLIT; in mark_split()
94 list_del(&block->link); in mark_split()
112 parent = block->parent; in __get_buddy()
116 if (parent->left == block) in __get_buddy()
117 return parent->right; in __get_buddy()
119 return parent->left; in __get_buddy()
122 static unsigned int __drm_buddy_free(struct drm_buddy *mm, in __drm_buddy_free() argument
129 while ((parent = block->parent)) { in __drm_buddy_free()
150 list_del(&buddy->link); in __drm_buddy_free()
152 mm->clear_avail -= drm_buddy_block_size(mm, buddy); in __drm_buddy_free()
154 drm_block_free(mm, block); in __drm_buddy_free()
155 drm_block_free(mm, buddy); in __drm_buddy_free()
161 mark_free(mm, block); in __drm_buddy_free()
166 static int __force_merge(struct drm_buddy *mm, in __force_merge() argument
175 return -ENOMEM; in __force_merge()
177 if (min_order > mm->max_order) in __force_merge()
178 return -EINVAL; in __force_merge()
180 for (i = min_order - 1; i >= 0; i--) { in __force_merge()
183 list_for_each_entry_safe_reverse(block, prev, &mm->free_list[i], link) { in __force_merge()
187 if (!block->parent) in __force_merge()
191 block_end = block_start + drm_buddy_block_size(mm, block) - 1; in __force_merge()
211 list_del(&block->link); in __force_merge()
213 mm->clear_avail -= drm_buddy_block_size(mm, block); in __force_merge()
215 order = __drm_buddy_free(mm, block, true); in __force_merge()
217 return 0; in __force_merge()
221 return -ENOMEM; in __force_merge()
225 * drm_buddy_init - init memory manager
227 * @mm: DRM buddy manager to initialize
234 * 0 on success, error code on failure.
236 int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size) in drm_buddy_init() argument
242 return -EINVAL; in drm_buddy_init()
245 return -EINVAL; in drm_buddy_init()
248 return -EINVAL; in drm_buddy_init()
252 mm->size = size; in drm_buddy_init()
253 mm->avail = size; in drm_buddy_init()
254 mm->clear_avail = 0; in drm_buddy_init()
255 mm->chunk_size = chunk_size; in drm_buddy_init()
256 mm->max_order = ilog2(size) - ilog2(chunk_size); in drm_buddy_init()
258 BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER); in drm_buddy_init()
260 mm->free_list = kmalloc_array(mm->max_order + 1, in drm_buddy_init()
263 if (!mm->free_list) in drm_buddy_init()
264 return -ENOMEM; in drm_buddy_init()
266 for (i = 0; i <= mm->max_order; ++i) in drm_buddy_init()
267 INIT_LIST_HEAD(&mm->free_list[i]); in drm_buddy_init()
269 mm->n_roots = hweight64(size); in drm_buddy_init()
271 mm->roots = kmalloc_array(mm->n_roots, in drm_buddy_init()
274 if (!mm->roots) in drm_buddy_init()
277 offset = 0; in drm_buddy_init()
278 i = 0; in drm_buddy_init()
281 * Split into power-of-two blocks, in case we are given a size that is in drm_buddy_init()
282 * not itself a power-of-two. in drm_buddy_init()
289 order = ilog2(size) - ilog2(chunk_size); in drm_buddy_init()
292 root = drm_block_alloc(mm, NULL, order, offset); in drm_buddy_init()
296 mark_free(mm, root); in drm_buddy_init()
298 BUG_ON(i > mm->max_order); in drm_buddy_init()
299 BUG_ON(drm_buddy_block_size(mm, root) < chunk_size); in drm_buddy_init()
301 mm->roots[i] = root; in drm_buddy_init()
304 size -= root_size; in drm_buddy_init()
308 return 0; in drm_buddy_init()
311 while (i--) in drm_buddy_init()
312 drm_block_free(mm, mm->roots[i]); in drm_buddy_init()
313 kfree(mm->roots); in drm_buddy_init()
315 kfree(mm->free_list); in drm_buddy_init()
316 return -ENOMEM; in drm_buddy_init()
321 * drm_buddy_fini - tear down the memory manager
323 * @mm: DRM buddy manager to free
327 void drm_buddy_fini(struct drm_buddy *mm) in drm_buddy_fini() argument
333 size = mm->size; in drm_buddy_fini()
335 for (i = 0; i < mm->n_roots; ++i) { in drm_buddy_fini()
336 order = ilog2(size) - ilog2(mm->chunk_size); in drm_buddy_fini()
337 start = drm_buddy_block_offset(mm->roots[i]); in drm_buddy_fini()
338 __force_merge(mm, start, start + size, order); in drm_buddy_fini()
340 if (WARN_ON(!drm_buddy_block_is_free(mm->roots[i]))) in drm_buddy_fini()
343 drm_block_free(mm, mm->roots[i]); in drm_buddy_fini()
345 root_size = mm->chunk_size << order; in drm_buddy_fini()
346 size -= root_size; in drm_buddy_fini()
349 WARN_ON(mm->avail != mm->size); in drm_buddy_fini()
351 kfree(mm->roots); in drm_buddy_fini()
352 kfree(mm->free_list); in drm_buddy_fini()
356 static int split_block(struct drm_buddy *mm, in split_block() argument
359 unsigned int block_order = drm_buddy_block_order(block) - 1; in split_block()
365 block->left = drm_block_alloc(mm, block, block_order, offset); in split_block()
366 if (!block->left) in split_block()
367 return -ENOMEM; in split_block()
369 block->right = drm_block_alloc(mm, block, block_order, in split_block()
370 offset + (mm->chunk_size << block_order)); in split_block()
371 if (!block->right) { in split_block()
372 drm_block_free(mm, block->left); in split_block()
373 return -ENOMEM; in split_block()
376 mark_free(mm, block->left); in split_block()
377 mark_free(mm, block->right); in split_block()
380 mark_cleared(block->left); in split_block()
381 mark_cleared(block->right); in split_block()
387 return 0; in split_block()
391 * drm_get_buddy - get buddy address
408 * drm_buddy_free_block - free a block
410 * @mm: DRM buddy manager
413 void drm_buddy_free_block(struct drm_buddy *mm, in drm_buddy_free_block() argument
417 mm->avail += drm_buddy_block_size(mm, block); in drm_buddy_free_block()
419 mm->clear_avail += drm_buddy_block_size(mm, block); in drm_buddy_free_block()
421 __drm_buddy_free(mm, block, false); in drm_buddy_free_block()
425 static void __drm_buddy_free_list(struct drm_buddy *mm, in __drm_buddy_free_list() argument
439 drm_buddy_free_block(mm, block); in __drm_buddy_free_list()
445 static void drm_buddy_free_list_internal(struct drm_buddy *mm, in drm_buddy_free_list_internal() argument
453 __drm_buddy_free_list(mm, objects, false, false); in drm_buddy_free_list_internal()
457 * drm_buddy_free_list - free blocks
459 * @mm: DRM buddy manager
463 void drm_buddy_free_list(struct drm_buddy *mm, in drm_buddy_free_list() argument
469 __drm_buddy_free_list(mm, objects, mark_clear, !mark_clear); in drm_buddy_free_list()
481 __alloc_range_bias(struct drm_buddy *mm, in __alloc_range_bias() argument
487 u64 req_size = mm->chunk_size << order; in __alloc_range_bias()
494 end = end - 1; in __alloc_range_bias()
496 for (i = 0; i < mm->n_roots; ++i) in __alloc_range_bias()
497 list_add_tail(&mm->roots[i]->tmp_link, &dfs); in __alloc_range_bias()
509 list_del(&block->tmp_link); in __alloc_range_bias()
515 block_end = block_start + drm_buddy_block_size(mm, block) - 1; in __alloc_range_bias()
547 err = split_block(mm, block); in __alloc_range_bias()
552 list_add(&block->right->tmp_link, &dfs); in __alloc_range_bias()
553 list_add(&block->left->tmp_link, &dfs); in __alloc_range_bias()
556 return ERR_PTR(-ENOSPC); in __alloc_range_bias()
568 __drm_buddy_free(mm, block, false); in __alloc_range_bias()
573 __drm_buddy_alloc_range_bias(struct drm_buddy *mm, in __drm_buddy_alloc_range_bias() argument
581 block = __alloc_range_bias(mm, start, end, order, in __drm_buddy_alloc_range_bias()
584 return __alloc_range_bias(mm, start, end, order, in __drm_buddy_alloc_range_bias()
591 get_maxblock(struct drm_buddy *mm, unsigned int order, in get_maxblock() argument
597 for (i = order; i <= mm->max_order; ++i) { in get_maxblock()
600 list_for_each_entry_reverse(tmp_block, &mm->free_list[i], link) { in get_maxblock()
626 alloc_from_freelist(struct drm_buddy *mm, in alloc_from_freelist() argument
635 block = get_maxblock(mm, order, flags); in alloc_from_freelist()
640 for (tmp = order; tmp <= mm->max_order; ++tmp) { in alloc_from_freelist()
643 list_for_each_entry_reverse(tmp_block, &mm->free_list[tmp], link) { in alloc_from_freelist()
658 for (tmp = order; tmp <= mm->max_order; ++tmp) { in alloc_from_freelist()
659 if (!list_empty(&mm->free_list[tmp])) { in alloc_from_freelist()
660 block = list_last_entry(&mm->free_list[tmp], in alloc_from_freelist()
669 return ERR_PTR(-ENOSPC); in alloc_from_freelist()
675 err = split_block(mm, block); in alloc_from_freelist()
679 block = block->right; in alloc_from_freelist()
680 tmp--; in alloc_from_freelist()
686 __drm_buddy_free(mm, block, false); in alloc_from_freelist()
690 static int __alloc_range(struct drm_buddy *mm, in __alloc_range() argument
698 u64 total_allocated = 0; in __alloc_range()
703 end = start + size - 1; in __alloc_range()
715 list_del(&block->tmp_link); in __alloc_range()
718 block_end = block_start + drm_buddy_block_size(mm, block) - 1; in __alloc_range()
724 err = -ENOSPC; in __alloc_range()
731 total_allocated += drm_buddy_block_size(mm, block); in __alloc_range()
732 mm->avail -= drm_buddy_block_size(mm, block); in __alloc_range()
734 mm->clear_avail -= drm_buddy_block_size(mm, block); in __alloc_range()
735 list_add_tail(&block->link, &allocated); in __alloc_range()
737 } else if (!mm->clear_avail) { in __alloc_range()
738 err = -ENOSPC; in __alloc_range()
744 err = split_block(mm, block); in __alloc_range()
749 list_add(&block->right->tmp_link, dfs); in __alloc_range()
750 list_add(&block->left->tmp_link, dfs); in __alloc_range()
754 err = -ENOSPC; in __alloc_range()
760 return 0; in __alloc_range()
772 __drm_buddy_free(mm, block, false); in __alloc_range()
775 if (err == -ENOSPC && total_allocated_on_err) { in __alloc_range()
779 drm_buddy_free_list_internal(mm, &allocated); in __alloc_range()
785 static int __drm_buddy_alloc_range(struct drm_buddy *mm, in __drm_buddy_alloc_range() argument
794 for (i = 0; i < mm->n_roots; ++i) in __drm_buddy_alloc_range()
795 list_add_tail(&mm->roots[i]->tmp_link, &dfs); in __drm_buddy_alloc_range()
797 return __alloc_range(mm, &dfs, start, size, in __drm_buddy_alloc_range()
801 static int __alloc_contig_try_harder(struct drm_buddy *mm, in __alloc_contig_try_harder() argument
816 pages = modify_size >> ilog2(mm->chunk_size); in __alloc_contig_try_harder()
817 order = fls(pages) - 1; in __alloc_contig_try_harder()
818 if (order == 0) in __alloc_contig_try_harder()
819 return -ENOSPC; in __alloc_contig_try_harder()
821 list = &mm->free_list[order]; in __alloc_contig_try_harder()
823 return -ENOSPC; in __alloc_contig_try_harder()
828 err = __drm_buddy_alloc_range(mm, rhs_offset, size, in __alloc_contig_try_harder()
830 if (!err || err != -ENOSPC) in __alloc_contig_try_harder()
833 lhs_size = max((size - filled), min_block_size); in __alloc_contig_try_harder()
838 lhs_offset = drm_buddy_block_offset(block) - lhs_size; in __alloc_contig_try_harder()
839 err = __drm_buddy_alloc_range(mm, lhs_offset, lhs_size, in __alloc_contig_try_harder()
843 return 0; in __alloc_contig_try_harder()
844 } else if (err != -ENOSPC) { in __alloc_contig_try_harder()
845 drm_buddy_free_list_internal(mm, blocks); in __alloc_contig_try_harder()
849 drm_buddy_free_list_internal(mm, blocks); in __alloc_contig_try_harder()
852 return -ENOSPC; in __alloc_contig_try_harder()
856 * drm_buddy_block_trim - free unused pages
858 * @mm: DRM buddy manager
872 * 0 on success, error code on failure.
874 int drm_buddy_block_trim(struct drm_buddy *mm, in drm_buddy_block_trim() argument
887 return -EINVAL; in drm_buddy_block_trim()
894 block_end = block_start + drm_buddy_block_size(mm, block); in drm_buddy_block_trim()
897 return -EINVAL; in drm_buddy_block_trim()
899 if (new_size > drm_buddy_block_size(mm, block)) in drm_buddy_block_trim()
900 return -EINVAL; in drm_buddy_block_trim()
902 if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size)) in drm_buddy_block_trim()
903 return -EINVAL; in drm_buddy_block_trim()
905 if (new_size == drm_buddy_block_size(mm, block)) in drm_buddy_block_trim()
906 return 0; in drm_buddy_block_trim()
913 return -EINVAL; in drm_buddy_block_trim()
915 if (!IS_ALIGNED(new_start, mm->chunk_size)) in drm_buddy_block_trim()
916 return -EINVAL; in drm_buddy_block_trim()
919 return -EINVAL; in drm_buddy_block_trim()
922 list_del(&block->link); in drm_buddy_block_trim()
923 mark_free(mm, block); in drm_buddy_block_trim()
924 mm->avail += drm_buddy_block_size(mm, block); in drm_buddy_block_trim()
926 mm->clear_avail += drm_buddy_block_size(mm, block); in drm_buddy_block_trim()
929 parent = block->parent; in drm_buddy_block_trim()
930 block->parent = NULL; in drm_buddy_block_trim()
932 list_add(&block->tmp_link, &dfs); in drm_buddy_block_trim()
933 err = __alloc_range(mm, &dfs, new_start, new_size, blocks, NULL); in drm_buddy_block_trim()
936 mm->avail -= drm_buddy_block_size(mm, block); in drm_buddy_block_trim()
938 mm->clear_avail -= drm_buddy_block_size(mm, block); in drm_buddy_block_trim()
939 list_add(&block->link, blocks); in drm_buddy_block_trim()
942 block->parent = parent; in drm_buddy_block_trim()
948 __drm_buddy_alloc_blocks(struct drm_buddy *mm, in __drm_buddy_alloc_blocks() argument
955 return __drm_buddy_alloc_range_bias(mm, start, end, in __drm_buddy_alloc_blocks()
959 return alloc_from_freelist(mm, order, flags); in __drm_buddy_alloc_blocks()
963 * drm_buddy_alloc_blocks - allocate power-of-two blocks
965 * @mm: DRM buddy manager to allocate from
980 * 0 on success, error code on failure.
982 int drm_buddy_alloc_blocks(struct drm_buddy *mm, in drm_buddy_alloc_blocks() argument
995 if (size < mm->chunk_size) in drm_buddy_alloc_blocks()
996 return -EINVAL; in drm_buddy_alloc_blocks()
998 if (min_block_size < mm->chunk_size) in drm_buddy_alloc_blocks()
999 return -EINVAL; in drm_buddy_alloc_blocks()
1002 return -EINVAL; in drm_buddy_alloc_blocks()
1004 if (!IS_ALIGNED(start | end | size, mm->chunk_size)) in drm_buddy_alloc_blocks()
1005 return -EINVAL; in drm_buddy_alloc_blocks()
1007 if (end > mm->size) in drm_buddy_alloc_blocks()
1008 return -EINVAL; in drm_buddy_alloc_blocks()
1010 if (range_overflows(start, size, mm->size)) in drm_buddy_alloc_blocks()
1011 return -EINVAL; in drm_buddy_alloc_blocks()
1016 return -EINVAL; in drm_buddy_alloc_blocks()
1018 return __drm_buddy_alloc_range(mm, start, size, NULL, blocks); in drm_buddy_alloc_blocks()
1033 pages = size >> ilog2(mm->chunk_size); in drm_buddy_alloc_blocks()
1034 order = fls(pages) - 1; in drm_buddy_alloc_blocks()
1035 min_order = ilog2(min_block_size) - ilog2(mm->chunk_size); in drm_buddy_alloc_blocks()
1038 order = min(order, (unsigned int)fls(pages) - 1); in drm_buddy_alloc_blocks()
1039 BUG_ON(order > mm->max_order); in drm_buddy_alloc_blocks()
1043 block = __drm_buddy_alloc_blocks(mm, start, in drm_buddy_alloc_blocks()
1050 if (order-- == min_order) { in drm_buddy_alloc_blocks()
1052 if (mm->clear_avail && in drm_buddy_alloc_blocks()
1053 !__force_merge(mm, start, end, min_order)) { in drm_buddy_alloc_blocks()
1054 block = __drm_buddy_alloc_blocks(mm, start, in drm_buddy_alloc_blocks()
1070 return __alloc_contig_try_harder(mm, in drm_buddy_alloc_blocks()
1074 err = -ENOSPC; in drm_buddy_alloc_blocks()
1080 mm->avail -= drm_buddy_block_size(mm, block); in drm_buddy_alloc_blocks()
1082 mm->clear_avail -= drm_buddy_block_size(mm, block); in drm_buddy_alloc_blocks()
1084 list_add_tail(&block->link, &allocated); in drm_buddy_alloc_blocks()
1086 pages -= BIT(order); in drm_buddy_alloc_blocks()
1104 list_move(&block->link, &temp); in drm_buddy_alloc_blocks()
1106 trim_size = drm_buddy_block_size(mm, block) - in drm_buddy_alloc_blocks()
1107 (size - original_size); in drm_buddy_alloc_blocks()
1110 drm_buddy_block_trim(mm, in drm_buddy_alloc_blocks()
1120 return 0; in drm_buddy_alloc_blocks()
1123 drm_buddy_free_list_internal(mm, &allocated); in drm_buddy_alloc_blocks()
1129 * drm_buddy_block_print - print block information
1131 * @mm: DRM buddy manager
1135 void drm_buddy_block_print(struct drm_buddy *mm, in drm_buddy_block_print() argument
1140 u64 size = drm_buddy_block_size(mm, block); in drm_buddy_block_print()
1142 drm_printf(p, "%#018llx-%#018llx: %llu\n", start, start + size, size); in drm_buddy_block_print()
1147 * drm_buddy_print - print allocator state
1149 * @mm: DRM buddy manager
1152 void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p) in drm_buddy_print() argument
1157 mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20, mm->clear_avail >> 20); in drm_buddy_print()
1159 for (order = mm->max_order; order >= 0; order--) { in drm_buddy_print()
1161 u64 count = 0, free; in drm_buddy_print()
1163 list_for_each_entry(block, &mm->free_list[order], link) { in drm_buddy_print()
1168 drm_printf(p, "order-%2d ", order); in drm_buddy_print()
1170 free = count * (mm->chunk_size << order); in drm_buddy_print()
1188 slab_blocks = KMEM_CACHE(drm_buddy_block, 0); in drm_buddy_module_init()
1190 return -ENOMEM; in drm_buddy_module_init()
1192 return 0; in drm_buddy_module_init()