include/drm/drm_buddy.h

0001 /* SPDX-License-Identifier: MIT */
0002 /*
0003  * Copyright © 2021 Intel Corporation
0004  */
0005
0006 #ifndef __DRM_BUDDY_H__
0007 #define __DRM_BUDDY_H__
0008
0009 #include <linux/bitops.h>
0010 #include <linux/list.h>
0011 #include <linux/slab.h>
0012 #include <linux/sched.h>
0013
0014 #include <drm/drm_print.h>
0015
0016 #define range_overflows(start, size, max) ({ \
0017     typeof(start) start__ = (start); \
0018     typeof(size) size__ = (size); \
0019     typeof(max) max__ = (max); \
0020     (void)(&start__ == &size__); \
0021     (void)(&start__ == &max__); \
0022     start__ >= max__ || size__ > max__ - start__; \
0023 })
0024
0025 #define DRM_BUDDY_RANGE_ALLOCATION (1 << 0)
0026 #define DRM_BUDDY_TOPDOWN_ALLOCATION (1 << 1)
0027
0028 struct drm_buddy_block {
0029 #define DRM_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12)
0030 #define DRM_BUDDY_HEADER_STATE  GENMASK_ULL(11, 10)
0031 #define   DRM_BUDDY_ALLOCATED      (1 << 10)
0032 #define   DRM_BUDDY_FREE       (2 << 10)
0033 #define   DRM_BUDDY_SPLIT      (3 << 10)
0034 /* Free to be used, if needed in the future */
0035 #define DRM_BUDDY_HEADER_UNUSED GENMASK_ULL(9, 6)
0036 #define DRM_BUDDY_HEADER_ORDER  GENMASK_ULL(5, 0)
0037     u64 header;
0038
0039     struct drm_buddy_block *left;
0040     struct drm_buddy_block *right;
0041     struct drm_buddy_block *parent;
0042
0043     void *private; /* owned by creator */
0044
0045     /*
0046      * While the block is allocated by the user through drm_buddy_alloc*,
0047      * the user has ownership of the link, for example to maintain within
0048      * a list, if so desired. As soon as the block is freed with
0049      * drm_buddy_free* ownership is given back to the mm.
0050      */
0051     struct list_head link;
0052     struct list_head tmp_link;
0053 };
0054
0055 /* Order-zero must be at least PAGE_SIZE */
0056 #define DRM_BUDDY_MAX_ORDER (63 - PAGE_SHIFT)
0057
0058 /*
0059  * Binary Buddy System.
0060  *
0061  * Locking should be handled by the user, a simple mutex around
0062  * drm_buddy_alloc* and drm_buddy_free* should suffice.
0063  */
0064 struct drm_buddy {
0065     /* Maintain a free list for each order. */
0066     struct list_head *free_list;
0067
0068     /*
0069      * Maintain explicit binary tree(s) to track the allocation of the
0070      * address space. This gives us a simple way of finding a buddy block
0071      * and performing the potentially recursive merge step when freeing a
0072      * block.  Nodes are either allocated or free, in which case they will
0073      * also exist on the respective free list.
0074      */
0075     struct drm_buddy_block **roots;
0076
0077     /*
0078      * Anything from here is public, and remains static for the lifetime of
0079      * the mm. Everything above is considered do-not-touch.
0080      */
0081     unsigned int n_roots;
0082     unsigned int max_order;
0083
0084     /* Must be at least PAGE_SIZE */
0085     u64 chunk_size;
0086     u64 size;
0087     u64 avail;
0088 };
0089
0090 static inline u64
0091 drm_buddy_block_offset(struct drm_buddy_block *block)
0092 {
0093     return block->header & DRM_BUDDY_HEADER_OFFSET;
0094 }
0095
0096 static inline unsigned int
0097 drm_buddy_block_order(struct drm_buddy_block *block)
0098 {
0099     return block->header & DRM_BUDDY_HEADER_ORDER;
0100 }
0101
0102 static inline unsigned int
0103 drm_buddy_block_state(struct drm_buddy_block *block)
0104 {
0105     return block->header & DRM_BUDDY_HEADER_STATE;
0106 }
0107
0108 static inline bool
0109 drm_buddy_block_is_allocated(struct drm_buddy_block *block)
0110 {
0111     return drm_buddy_block_state(block) == DRM_BUDDY_ALLOCATED;
0112 }
0113
0114 static inline bool
0115 drm_buddy_block_is_free(struct drm_buddy_block *block)
0116 {
0117     return drm_buddy_block_state(block) == DRM_BUDDY_FREE;
0118 }
0119
0120 static inline bool
0121 drm_buddy_block_is_split(struct drm_buddy_block *block)
0122 {
0123     return drm_buddy_block_state(block) == DRM_BUDDY_SPLIT;
0124 }
0125
0126 static inline u64
0127 drm_buddy_block_size(struct drm_buddy *mm,
0128              struct drm_buddy_block *block)
0129 {
0130     return mm->chunk_size << drm_buddy_block_order(block);
0131 }
0132
0133 int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size);
0134
0135 void drm_buddy_fini(struct drm_buddy *mm);
0136
0137 struct drm_buddy_block *
0138 drm_get_buddy(struct drm_buddy_block *block);
0139
0140 int drm_buddy_alloc_blocks(struct drm_buddy *mm,
0141                u64 start, u64 end, u64 size,
0142                u64 min_page_size,
0143                struct list_head *blocks,
0144                unsigned long flags);
0145
0146 int drm_buddy_block_trim(struct drm_buddy *mm,
0147              u64 new_size,
0148              struct list_head *blocks);
0149
0150 void drm_buddy_free_block(struct drm_buddy *mm, struct drm_buddy_block *block);
0151
0152 void drm_buddy_free_list(struct drm_buddy *mm, struct list_head *objects);
0153
0154 void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p);
0155 void drm_buddy_block_print(struct drm_buddy *mm,
0156                struct drm_buddy_block *block,
0157                struct drm_printer *p);
0158
0159 #endif