Lines Matching +full:mm +full:- +full:0
1 // SPDX-License-Identifier: MIT
14 static struct drm_buddy_block *drm_block_alloc(struct drm_buddy *mm, in drm_block_alloc() argument
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()
35 static void drm_block_free(struct drm_buddy *mm, in drm_block_free() argument
41 static void list_insert_sorted(struct drm_buddy *mm, 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()
57 __list_add(&block->link, node->link.prev, &node->link); in list_insert_sorted()
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()
68 static void mark_free(struct drm_buddy *mm, 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()
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()
86 * drm_buddy_init - init memory manager
88 * @mm: DRM buddy manager to initialize
95 * 0 on success, error code on failure.
97 int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size) in drm_buddy_init() argument
103 return -EINVAL; in drm_buddy_init()
106 return -EINVAL; in drm_buddy_init()
109 return -EINVAL; in drm_buddy_init()
113 mm->size = size; in drm_buddy_init()
114 mm->avail = size; in drm_buddy_init()
115 mm->chunk_size = chunk_size; in drm_buddy_init()
116 mm->max_order = ilog2(size) - ilog2(chunk_size); in drm_buddy_init()
118 BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER); in drm_buddy_init()
120 mm->free_list = kmalloc_array(mm->max_order + 1, in drm_buddy_init()
123 if (!mm->free_list) in drm_buddy_init()
124 return -ENOMEM; in drm_buddy_init()
126 for (i = 0; i <= mm->max_order; ++i) in drm_buddy_init()
127 INIT_LIST_HEAD(&mm->free_list[i]); in drm_buddy_init()
129 mm->n_roots = hweight64(size); in drm_buddy_init()
131 mm->roots = kmalloc_array(mm->n_roots, in drm_buddy_init()
134 if (!mm->roots) in drm_buddy_init()
137 offset = 0; in drm_buddy_init()
138 i = 0; in drm_buddy_init()
141 * Split into power-of-two blocks, in case we are given a size that is in drm_buddy_init()
142 * not itself a power-of-two. in drm_buddy_init()
149 order = ilog2(size) - ilog2(chunk_size); in drm_buddy_init()
152 root = drm_block_alloc(mm, NULL, order, offset); in drm_buddy_init()
156 mark_free(mm, root); in drm_buddy_init()
158 BUG_ON(i > mm->max_order); in drm_buddy_init()
159 BUG_ON(drm_buddy_block_size(mm, root) < chunk_size); in drm_buddy_init()
161 mm->roots[i] = root; in drm_buddy_init()
164 size -= root_size; in drm_buddy_init()
168 return 0; in drm_buddy_init()
171 while (i--) in drm_buddy_init()
172 drm_block_free(mm, mm->roots[i]); in drm_buddy_init()
173 kfree(mm->roots); in drm_buddy_init()
175 kfree(mm->free_list); in drm_buddy_init()
176 return -ENOMEM; in drm_buddy_init()
181 * drm_buddy_fini - tear down the memory manager
183 * @mm: DRM buddy manager to free
187 void drm_buddy_fini(struct drm_buddy *mm) in drm_buddy_fini() argument
191 for (i = 0; i < mm->n_roots; ++i) { in drm_buddy_fini()
192 WARN_ON(!drm_buddy_block_is_free(mm->roots[i])); in drm_buddy_fini()
193 drm_block_free(mm, mm->roots[i]); in drm_buddy_fini()
196 WARN_ON(mm->avail != mm->size); in drm_buddy_fini()
198 kfree(mm->roots); in drm_buddy_fini()
199 kfree(mm->free_list); in drm_buddy_fini()
203 static int split_block(struct drm_buddy *mm, in split_block() argument
206 unsigned int block_order = drm_buddy_block_order(block) - 1; in split_block()
212 block->left = drm_block_alloc(mm, block, block_order, offset); in split_block()
213 if (!block->left) in split_block()
214 return -ENOMEM; in split_block()
216 block->right = drm_block_alloc(mm, block, block_order, in split_block()
217 offset + (mm->chunk_size << block_order)); in split_block()
218 if (!block->right) { in split_block()
219 drm_block_free(mm, block->left); in split_block()
220 return -ENOMEM; in split_block()
223 mark_free(mm, block->left); in split_block()
224 mark_free(mm, block->right); in split_block()
228 return 0; in split_block()
236 parent = block->parent; in __get_buddy()
240 if (parent->left == block) in __get_buddy()
241 return parent->right; in __get_buddy()
243 return parent->left; in __get_buddy()
247 * drm_get_buddy - get buddy address
263 static void __drm_buddy_free(struct drm_buddy *mm, in __drm_buddy_free() argument
268 while ((parent = block->parent)) { in __drm_buddy_free()
276 list_del(&buddy->link); in __drm_buddy_free()
278 drm_block_free(mm, block); in __drm_buddy_free()
279 drm_block_free(mm, buddy); in __drm_buddy_free()
284 mark_free(mm, block); in __drm_buddy_free()
288 * drm_buddy_free_block - free a block
290 * @mm: DRM buddy manager
293 void drm_buddy_free_block(struct drm_buddy *mm, in drm_buddy_free_block() argument
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()
303 * drm_buddy_free_list - free blocks
305 * @mm: DRM buddy manager
308 void drm_buddy_free_list(struct drm_buddy *mm, struct list_head *objects) in drm_buddy_free_list() argument
313 drm_buddy_free_block(mm, block); in drm_buddy_free_list()
331 alloc_range_bias(struct drm_buddy *mm, in alloc_range_bias() argument
335 u64 req_size = mm->chunk_size << order; in alloc_range_bias()
342 end = end - 1; in alloc_range_bias()
344 for (i = 0; i < mm->n_roots; ++i) in alloc_range_bias()
345 list_add_tail(&mm->roots[i]->tmp_link, &dfs); in alloc_range_bias()
357 list_del(&block->tmp_link); in alloc_range_bias()
363 block_end = block_start + drm_buddy_block_size(mm, block) - 1; 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()
401 return ERR_PTR(-ENOSPC); in alloc_range_bias()
413 __drm_buddy_free(mm, block); in alloc_range_bias()
418 get_maxblock(struct drm_buddy *mm, unsigned int order) in get_maxblock() argument
423 for (i = order; i <= mm->max_order; ++i) { in get_maxblock()
424 if (!list_empty(&mm->free_list[i])) { in get_maxblock()
425 node = list_last_entry(&mm->free_list[i], in get_maxblock()
444 alloc_from_freelist(struct drm_buddy *mm, in alloc_from_freelist() argument
453 block = get_maxblock(mm, order); in alloc_from_freelist()
458 for (tmp = order; tmp <= mm->max_order; ++tmp) { in alloc_from_freelist()
459 if (!list_empty(&mm->free_list[tmp])) { in alloc_from_freelist()
460 block = list_last_entry(&mm->free_list[tmp], in alloc_from_freelist()
470 return ERR_PTR(-ENOSPC); in alloc_from_freelist()
475 err = split_block(mm, block); in alloc_from_freelist()
479 block = block->right; in alloc_from_freelist()
480 tmp--; in alloc_from_freelist()
486 __drm_buddy_free(mm, block); in alloc_from_freelist()
490 static int __alloc_range(struct drm_buddy *mm, in __alloc_range() argument
501 end = start + size - 1; in __alloc_range()
513 list_del(&block->tmp_link); in __alloc_range()
516 block_end = block_start + drm_buddy_block_size(mm, block) - 1; in __alloc_range()
522 err = -ENOSPC; in __alloc_range()
528 err = -ENOSPC; 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()
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()
549 return 0; in __alloc_range()
561 __drm_buddy_free(mm, block); in __alloc_range()
564 drm_buddy_free_list(mm, &allocated); in __alloc_range()
568 static int __drm_buddy_alloc_range(struct drm_buddy *mm, in __drm_buddy_alloc_range() argument
576 for (i = 0; i < mm->n_roots; ++i) in __drm_buddy_alloc_range()
577 list_add_tail(&mm->roots[i]->tmp_link, &dfs); in __drm_buddy_alloc_range()
579 return __alloc_range(mm, &dfs, start, size, blocks); in __drm_buddy_alloc_range()
583 * drm_buddy_block_trim - free unused pages
585 * @mm: DRM buddy manager
598 * 0 on success, error code on failure.
600 int drm_buddy_block_trim(struct drm_buddy *mm, in drm_buddy_block_trim() argument
611 return -EINVAL; in drm_buddy_block_trim()
618 return -EINVAL; in drm_buddy_block_trim()
620 if (new_size > drm_buddy_block_size(mm, block)) in drm_buddy_block_trim()
621 return -EINVAL; in drm_buddy_block_trim()
623 if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size)) in drm_buddy_block_trim()
624 return -EINVAL; in drm_buddy_block_trim()
626 if (new_size == drm_buddy_block_size(mm, block)) in drm_buddy_block_trim()
627 return 0; 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()
638 list_add(&block->tmp_link, &dfs); in drm_buddy_block_trim()
639 err = __alloc_range(mm, &dfs, new_start, new_size, blocks); 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()
652 * drm_buddy_alloc_blocks - allocate power-of-two blocks
654 * @mm: DRM buddy manager to allocate from
669 * 0 on success, error code on failure.
671 int drm_buddy_alloc_blocks(struct drm_buddy *mm, in drm_buddy_alloc_blocks() argument
683 if (size < mm->chunk_size) in drm_buddy_alloc_blocks()
684 return -EINVAL; in drm_buddy_alloc_blocks()
686 if (min_page_size < mm->chunk_size) in drm_buddy_alloc_blocks()
687 return -EINVAL; in drm_buddy_alloc_blocks()
690 return -EINVAL; in drm_buddy_alloc_blocks()
692 if (!IS_ALIGNED(start | end | size, mm->chunk_size)) in drm_buddy_alloc_blocks()
693 return -EINVAL; in drm_buddy_alloc_blocks()
695 if (end > mm->size) in drm_buddy_alloc_blocks()
696 return -EINVAL; in drm_buddy_alloc_blocks()
698 if (range_overflows(start, size, mm->size)) in drm_buddy_alloc_blocks()
699 return -EINVAL; in drm_buddy_alloc_blocks()
703 return __drm_buddy_alloc_range(mm, start, size, blocks); in drm_buddy_alloc_blocks()
706 return -EINVAL; in drm_buddy_alloc_blocks()
708 pages = size >> ilog2(mm->chunk_size); in drm_buddy_alloc_blocks()
709 order = fls(pages) - 1; in drm_buddy_alloc_blocks()
710 min_order = ilog2(min_page_size) - ilog2(mm->chunk_size); in drm_buddy_alloc_blocks()
713 order = min(order, (unsigned int)fls(pages) - 1); in drm_buddy_alloc_blocks()
714 BUG_ON(order > mm->max_order); in drm_buddy_alloc_blocks()
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()
728 if (order-- == min_order) { in drm_buddy_alloc_blocks()
729 err = -ENOSPC; in drm_buddy_alloc_blocks()
735 mm->avail -= drm_buddy_block_size(mm, block); in drm_buddy_alloc_blocks()
737 list_add_tail(&block->link, &allocated); in drm_buddy_alloc_blocks()
739 pages -= BIT(order); in drm_buddy_alloc_blocks()
746 return 0; in drm_buddy_alloc_blocks()
749 drm_buddy_free_list(mm, &allocated); in drm_buddy_alloc_blocks()
755 * drm_buddy_block_print - print block information
757 * @mm: DRM buddy manager
761 void drm_buddy_block_print(struct drm_buddy *mm, in drm_buddy_block_print() argument
766 u64 size = drm_buddy_block_size(mm, block); in drm_buddy_block_print()
768 drm_printf(p, "%#018llx-%#018llx: %llu\n", start, start + size, size); in drm_buddy_block_print()
773 * drm_buddy_print - print allocator state
775 * @mm: DRM buddy manager
778 void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p) in drm_buddy_print() argument
783 mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20); in drm_buddy_print()
785 for (order = mm->max_order; order >= 0; order--) { in drm_buddy_print()
787 u64 count = 0, free; in drm_buddy_print()
789 list_for_each_entry(block, &mm->free_list[order], link) { in drm_buddy_print()
794 drm_printf(p, "order-%2d ", order); in drm_buddy_print()
796 free = count * (mm->chunk_size << order); in drm_buddy_print()
814 slab_blocks = KMEM_CACHE(drm_buddy_block, 0); in drm_buddy_module_init()
816 return -ENOMEM; in drm_buddy_module_init()
818 return 0; in drm_buddy_module_init()