// SPDX-License-Identifier: MIT /* * Copyright © 2021 Intel Corporation */ #include <linux/kmemleak.h> #include <linux/module.h> #include <linux/sizes.h> #include <drm/drm_buddy.h> static struct kmem_cache *slab_blocks; static struct drm_buddy_block *drm_block_alloc(struct drm_buddy *mm, struct drm_buddy_block *parent, unsigned int order, u64 offset) { struct drm_buddy_block *block; BUG_ON(order > DRM_BUDDY_MAX_ORDER); block = kmem_cache_zalloc(slab_blocks, GFP_KERNEL); if (!block) return NULL; block->header = offset; block->header |= order; block->parent = parent; BUG_ON(block->header & DRM_BUDDY_HEADER_UNUSED); return block; } static void drm_block_free(struct drm_buddy *mm, struct drm_buddy_block *block) { kmem_cache_free(slab_blocks, block); } static void mark_allocated(struct drm_buddy_block *block) { block->header &= ~DRM_BUDDY_HEADER_STATE; block->header |= DRM_BUDDY_ALLOCATED; list_del(&block->link); } static void mark_free(struct drm_buddy *mm, struct drm_buddy_block *block) { block->header &= ~DRM_BUDDY_HEADER_STATE; block->header |= DRM_BUDDY_FREE; list_add(&block->link, &mm->free_list[drm_buddy_block_order(block)]); } static void mark_split(struct drm_buddy_block *block) { block->header &= ~DRM_BUDDY_HEADER_STATE; block->header |= DRM_BUDDY_SPLIT; list_del(&block->link); } /** * drm_buddy_init - init memory manager * * @mm: DRM buddy manager to initialize * @size: size in bytes to manage * @chunk_size: minimum page size in bytes for our allocations * * Initializes the memory manager and its resources. * * Returns: * 0 on success, error code on failure. */ int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size) { unsigned int i; u64 offset; if (size < chunk_size) return -EINVAL; if (chunk_size < PAGE_SIZE) return -EINVAL; if (!is_power_of_2(chunk_size)) return -EINVAL; size = round_down(size, chunk_size); mm->size = size; mm->avail = size; mm->chunk_size = chunk_size; mm->max_order = ilog2(size) - ilog2(chunk_size); BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER); mm->free_list = kmalloc_array(mm->max_order + 1, sizeof(struct list_head), GFP_KERNEL); if (!mm->free_list) return -ENOMEM; for (i = 0; i <= mm->max_order; ++i) INIT_LIST_HEAD(&mm->free_list[i]); mm->n_roots = hweight64(size); mm->roots = kmalloc_array(mm->n_roots, sizeof(struct drm_buddy_block *), GFP_KERNEL); if (!mm->roots) goto out_free_list; offset = 0; i = 0; /* * Split into power-of-two blocks, in case we are given a size that is * not itself a power-of-two. */ do { struct drm_buddy_block *root; unsigned int order; u64 root_size; root_size = rounddown_pow_of_two(size); order = ilog2(root_size) - ilog2(chunk_size); root = drm_block_alloc(mm, NULL, order, offset); if (!root) goto out_free_roots; mark_free(mm, root); BUG_ON(i > mm->max_order); BUG_ON(drm_buddy_block_size(mm, root) < chunk_size); mm->roots[i] = root; offset += root_size; size -= root_size; i++; } while (size); return 0; out_free_roots: while (i--) drm_block_free(mm, mm->roots[i]); kfree(mm->roots); out_free_list: kfree(mm->free_list); return -ENOMEM; } EXPORT_SYMBOL(drm_buddy_init); /** * drm_buddy_fini - tear down the memory manager * * @mm: DRM buddy manager to free * * Cleanup memory manager resources and the freelist */ void drm_buddy_fini(struct drm_buddy *mm) { int i; for (i = 0; i < mm->n_roots; ++i) { WARN_ON(!drm_buddy_block_is_free(mm->roots[i])); drm_block_free(mm, mm->roots[i]); } WARN_ON(mm->avail != mm->size); kfree(mm->roots); kfree(mm->free_list); } EXPORT_SYMBOL(drm_buddy_fini); static int split_block(struct drm_buddy *mm, struct drm_buddy_block *block) { unsigned int block_order = drm_buddy_block_order(block) - 1; u64 offset = drm_buddy_block_offset(block); BUG_ON(!drm_buddy_block_is_free(block)); BUG_ON(!drm_buddy_block_order(block)); block->left = drm_block_alloc(mm, block, block_order, offset); if (!block->left) return -ENOMEM; block->right = drm_block_alloc(mm, block, block_order, offset + (mm->chunk_size << block_order)); if (!block->right) { drm_block_free(mm, block->left); return -ENOMEM; } mark_free(mm, block->left); mark_free(mm, block->right); mark_split(block); return 0; } static struct drm_buddy_block * __get_buddy(struct drm_buddy_block *block) { struct drm_buddy_block *parent; parent = block->parent; if (!parent) return NULL; if (parent->left == block) return parent->right; return parent->left; } /** * drm_get_buddy - get buddy address * * @block: DRM buddy block * * Returns the corresponding buddy block for @block, or NULL * if this is a root block and can't be merged further. * Requires some kind of locking to protect against * any concurrent allocate and free operations. */ struct drm_buddy_block * drm_get_buddy(struct drm_buddy_block *block) { return __get_buddy(block); } EXPORT_SYMBOL(drm_get_buddy); static void __drm_buddy_free(struct drm_buddy *mm, struct drm_buddy_block *block) { struct drm_buddy_block *parent; while ((parent = block->parent)) { struct drm_buddy_block *buddy; buddy = __get_buddy(block); if (!drm_buddy_block_is_free(buddy)) break; list_del(&buddy->link); drm_block_free(mm, block); drm_block_free(mm, buddy); block = parent; } mark_free(mm, block); } /** * drm_buddy_free_block - free a block * * @mm: DRM buddy manager * @block: block to be freed */ void drm_buddy_free_block(struct drm_buddy *mm, struct drm_buddy_block *block) { BUG_ON(!drm_buddy_block_is_allocated(block)); mm->avail += drm_buddy_block_size(mm, block); __drm_buddy_free(mm, block); } EXPORT_SYMBOL(drm_buddy_free_block); /** * drm_buddy_free_list - free blocks * * @mm: DRM buddy manager * @objects: input list head to free blocks */ void drm_buddy_free_list(struct drm_buddy *mm, struct list_head *objects) { struct drm_buddy_block *block, *on; list_for_each_entry_safe(block, on, objects, link) { drm_buddy_free_block(mm, block); cond_resched(); } INIT_LIST_HEAD(objects); } EXPORT_SYMBOL(drm_buddy_free_list); static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2) { return s1 <= e2 && e1 >= s2; } static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2) { return s1 <= s2 && e1 >= e2; } static struct drm_buddy_block * alloc_range_bias(struct drm_buddy *mm, u64 start, u64 end, unsigned int order) { struct drm_buddy_block *block; struct drm_buddy_block *buddy; LIST_HEAD(dfs); int err; int i; end = end - 1; for (i = 0; i < mm->n_roots; ++i) list_add_tail(&mm->roots[i]->tmp_link, &dfs); do { u64 block_start; u64 block_end; block = list_first_entry_or_null(&dfs, struct drm_buddy_block, tmp_link); if (!block) break; list_del(&block->tmp_link); if (drm_buddy_block_order(block) < order) continue; block_start = drm_buddy_block_offset(block); block_end = block_start + drm_buddy_block_size(mm, block) - 1; if (!overlaps(start, end, block_start, block_end)) continue; if (drm_buddy_block_is_allocated(block)) continue; if (contains(start, end, block_start, block_end) && order == drm_buddy_block_order(block)) { /* * Find the free block within the range. */ if (drm_buddy_block_is_free(block)) return block; continue; } if (!drm_buddy_block_is_split(block)) { err = split_block(mm, block); if (unlikely(err)) goto err_undo; } list_add(&block->right->tmp_link, &dfs); list_add(&block->left->tmp_link, &dfs); } while (1); return ERR_PTR(-ENOSPC); err_undo: /* * We really don't want to leave around a bunch of split blocks, since * bigger is better, so make sure we merge everything back before we * free the allocated blocks. */ buddy = __get_buddy(block); if (buddy && (drm_buddy_block_is_free(block) && drm_buddy_block_is_free(buddy))) __drm_buddy_free(mm, block); return ERR_PTR(err); } static struct drm_buddy_block * get_maxblock(struct list_head *head) { struct drm_buddy_block *max_block = NULL, *node; max_block = list_first_entry_or_null(head, struct drm_buddy_block, link); if (!max_block) return NULL; list_for_each_entry(node, head, link) { if (drm_buddy_block_offset(node) > drm_buddy_block_offset(max_block)) max_block = node; } return max_block; } static struct drm_buddy_block * alloc_from_freelist(struct drm_buddy *mm, unsigned int order, unsigned long flags) { struct drm_buddy_block *block = NULL; unsigned int i; int err; for (i = order; i <= mm->max_order; ++i) { if (flags & DRM_BUDDY_TOPDOWN_ALLOCATION) { block = get_maxblock(&mm->free_list[i]); if (block) break; } else { block = list_first_entry_or_null(&mm->free_list[i], struct drm_buddy_block, link); if (block) break; } } if (!block) return ERR_PTR(-ENOSPC); BUG_ON(!drm_buddy_block_is_free(block)); while (i != order) { err = split_block(mm, block); if (unlikely(err)) goto err_undo; block = block->right; i--; } return block; err_undo: if (i != order) __drm_buddy_free(mm, block); return ERR_PTR(err); } static int __alloc_range(struct drm_buddy *mm, struct list_head *dfs, u64 start, u64 size, struct list_head *blocks) { struct drm_buddy_block *block; struct drm_buddy_block *buddy; LIST_HEAD(allocated); u64 end; int err; end = start + size - 1; do { u64 block_start; u64 block_end; block = list_first_entry_or_null(dfs, struct drm_buddy_block, tmp_link); if (!block) break; list_del(&block->tmp_link); block_start = drm_buddy_block_offset(block); block_end = block_start + drm_buddy_block_size(mm, block) - 1; if (!overlaps(start, end, block_start, block_end)) continue; if (drm_buddy_block_is_allocated(block)) { err = -ENOSPC; goto err_free; } if (contains(start, end, block_start, block_end)) { if (!drm_buddy_block_is_free(block)) { err = -ENOSPC; goto err_free; } mark_allocated(block); mm->avail -= drm_buddy_block_size(mm, block); list_add_tail(&block->link, &allocated); continue; } if (!drm_buddy_block_is_split(block)) { err = split_block(mm, block); if (unlikely(err)) goto err_undo; } list_add(&block->right->tmp_link, dfs); list_add(&block->left->tmp_link, dfs); } while (1); list_splice_tail(&allocated, blocks); return 0; err_undo: /* * We really don't want to leave around a bunch of split blocks, since * bigger is better, so make sure we merge everything back before we * free the allocated blocks. */ buddy = __get_buddy(block); if (buddy && (drm_buddy_block_is_free(block) && drm_buddy_block_is_free(buddy))) __drm_buddy_free(mm, block); err_free: drm_buddy_free_list(mm, &allocated); return err; } static int __drm_buddy_alloc_range(struct drm_buddy *mm, u64 start, u64 size, struct list_head *blocks) { LIST_HEAD(dfs); int i; for (i = 0; i < mm->n_roots; ++i) list_add_tail(&mm->roots[i]->tmp_link, &dfs); return __alloc_range(mm, &dfs, start, size, blocks); } /** * drm_buddy_block_trim - free unused pages * * @mm: DRM buddy manager * @new_size: original size requested * @blocks: Input and output list of allocated blocks. * MUST contain single block as input to be trimmed. * On success will contain the newly allocated blocks * making up the @new_size. Blocks always appear in * ascending order * * For contiguous allocation, we round up the size to the nearest * power of two value, drivers consume *actual* size, so remaining * portions are unused and can be optionally freed with this function * * Returns: * 0 on success, error code on failure. */ int drm_buddy_block_trim(struct drm_buddy *mm, u64 new_size, struct list_head *blocks) { struct drm_buddy_block *parent; struct drm_buddy_block *block; LIST_HEAD(dfs); u64 new_start; int err; if (!list_is_singular(blocks)) return -EINVAL; block = list_first_entry(blocks, struct drm_buddy_block, link); if (WARN_ON(!drm_buddy_block_is_allocated(block))) return -EINVAL; if (new_size > drm_buddy_block_size(mm, block)) return -EINVAL; if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size)) return -EINVAL; if (new_size == drm_buddy_block_size(mm, block)) return 0; list_del(&block->link); mark_free(mm, block); mm->avail += drm_buddy_block_size(mm, block); /* Prevent recursively freeing this node */ parent = block->parent; block->parent = NULL; new_start = drm_buddy_block_offset(block); list_add(&block->tmp_link, &dfs); err = __alloc_range(mm, &dfs, new_start, new_size, blocks); if (err) { mark_allocated(block); mm->avail -= drm_buddy_block_size(mm, block); list_add(&block->link, blocks); } block->parent = parent; return err; } EXPORT_SYMBOL(drm_buddy_block_trim); /** * drm_buddy_alloc_blocks - allocate power-of-two blocks * * @mm: DRM buddy manager to allocate from * @start: start of the allowed range for this block * @end: end of the allowed range for this block * @size: size of the allocation * @min_page_size: alignment of the allocation * @blocks: output list head to add allocated blocks * @flags: DRM_BUDDY_*_ALLOCATION flags * * alloc_range_bias() called on range limitations, which traverses * the tree and returns the desired block. * * alloc_from_freelist() called when *no* range restrictions * are enforced, which picks the block from the freelist. * * Returns: * 0 on success, error code on failure. */ int drm_buddy_alloc_blocks(struct drm_buddy *mm, u64 start, u64 end, u64 size, u64 min_page_size, struct list_head *blocks, unsigned long flags) { struct drm_buddy_block *block = NULL; unsigned int min_order, order; unsigned long pages; LIST_HEAD(allocated); int err; if (size < mm->chunk_size) return -EINVAL; if (min_page_size < mm->chunk_size) return -EINVAL; if (!is_power_of_2(min_page_size)) return -EINVAL; if (!IS_ALIGNED(start | end | size, mm->chunk_size)) return -EINVAL; if (end > mm->size) return -EINVAL; if (range_overflows(start, size, mm->size)) return -EINVAL; /* Actual range allocation */ if (start + size == end) return __drm_buddy_alloc_range(mm, start, size, blocks); pages = size >> ilog2(mm->chunk_size); order = fls(pages) - 1; min_order = ilog2(min_page_size) - ilog2(mm->chunk_size); do { order = min(order, (unsigned int)fls(pages) - 1); BUG_ON(order > mm->max_order); BUG_ON(order < min_order); do { if (flags & DRM_BUDDY_RANGE_ALLOCATION) /* Allocate traversing within the range */ block = alloc_range_bias(mm, start, end, order); else /* Allocate from freelist */ block = alloc_from_freelist(mm, order, flags); if (!IS_ERR(block)) break; if (order-- == min_order) { err = -ENOSPC; goto err_free; } } while (1); mark_allocated(block); mm->avail -= drm_buddy_block_size(mm, block); kmemleak_update_trace(block); list_add_tail(&block->link, &allocated); pages -= BIT(order); if (!pages) break; } while (1); list_splice_tail(&allocated, blocks); return 0; err_free: drm_buddy_free_list(mm, &allocated); return err; } EXPORT_SYMBOL(drm_buddy_alloc_blocks); /** * drm_buddy_block_print - print block information * * @mm: DRM buddy manager * @block: DRM buddy block * @p: DRM printer to use */ void drm_buddy_block_print(struct drm_buddy *mm, struct drm_buddy_block *block, struct drm_printer *p) { u64 start = drm_buddy_block_offset(block); u64 size = drm_buddy_block_size(mm, block); drm_printf(p, "%#018llx-%#018llx: %llu\n", start, start + size, size); } EXPORT_SYMBOL(drm_buddy_block_print); /** * drm_buddy_print - print allocator state * * @mm: DRM buddy manager * @p: DRM printer to use */ void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p) { int order; drm_printf(p, "chunk_size: %lluKiB, total: %lluMiB, free: %lluMiB\n", mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20); for (order = mm->max_order; order >= 0; order--) { struct drm_buddy_block *block; u64 count = 0, free; list_for_each_entry(block, &mm->free_list[order], link) { BUG_ON(!drm_buddy_block_is_free(block)); count++; } drm_printf(p, "order-%d ", order); free = count * (mm->chunk_size << order); if (free < SZ_1M) drm_printf(p, "free: %lluKiB", free >> 10); else drm_printf(p, "free: %lluMiB", free >> 20); drm_printf(p, ", pages: %llu\n", count); } } EXPORT_SYMBOL(drm_buddy_print); static void drm_buddy_module_exit(void) { kmem_cache_destroy(slab_blocks); } static int __init drm_buddy_module_init(void) { slab_blocks = KMEM_CACHE(drm_buddy_block, 0); if (!slab_blocks) return -ENOMEM; return 0; } module_init(drm_buddy_module_init); module_exit(drm_buddy_module_exit); MODULE_DESCRIPTION("DRM Buddy Allocator"); MODULE_LICENSE("Dual MIT/GPL");