include/drm/drm_buddy.h

   1 /* SPDX-License-Identifier: MIT */
   2 /*
   3  * Copyright © 2021 Intel Corporation
   4  */
   5
   6 #ifndef __DRM_BUDDY_H__
   7 #define __DRM_BUDDY_H__
   8
   9 #include <linux/bitops.h>
  10 #include <linux/list.h>
  11 #include <linux/slab.h>
  12 #include <linux/sched.h>
  13
  14 #include <drm/drm_print.h>
  15
  16 #define range_overflows(start, size, max) ({ \
  17         typeof(start) start__ = (start); \
  18         typeof(size) size__ = (size); \
  19         typeof(max) max__ = (max); \
  20         (void)(&start__ == &size__); \
  21         (void)(&start__ == &max__); \
  22         start__ >= max__ || size__ > max__ - start__; \
  23 })
  24
  25 #define DRM_BUDDY_RANGE_ALLOCATION              BIT(0)
  26 #define DRM_BUDDY_TOPDOWN_ALLOCATION            BIT(1)
  27 #define DRM_BUDDY_CONTIGUOUS_ALLOCATION         BIT(2)
  28 #define DRM_BUDDY_CLEAR_ALLOCATION              BIT(3)
  29 #define DRM_BUDDY_CLEARED                       BIT(4)
  30 #define DRM_BUDDY_TRIM_DISABLE                  BIT(5)
  31
  32 struct drm_buddy_block {
  33 #define DRM_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12)
  34 #define DRM_BUDDY_HEADER_STATE  GENMASK_ULL(11, 10)
  35 #define   DRM_BUDDY_ALLOCATED      (1 << 10)
  36 #define   DRM_BUDDY_FREE           (2 << 10)
  37 #define   DRM_BUDDY_SPLIT          (3 << 10)
  38 #define DRM_BUDDY_HEADER_CLEAR  GENMASK_ULL(9, 9)
  39 /* Free to be used, if needed in the future */
  40 #define DRM_BUDDY_HEADER_UNUSED GENMASK_ULL(8, 6)
  41 #define DRM_BUDDY_HEADER_ORDER  GENMASK_ULL(5, 0)
  42         u64 header;
  43
  44         struct drm_buddy_block *left;
  45         struct drm_buddy_block *right;
  46         struct drm_buddy_block *parent;
  47
  48         void *private; /* owned by creator */
  49
  50         /*
  51          * While the block is allocated by the user through drm_buddy_alloc*,
  52          * the user has ownership of the link, for example to maintain within
  53          * a list, if so desired. As soon as the block is freed with
  54          * drm_buddy_free* ownership is given back to the mm.
  55          */
  56         struct list_head link;
  57         struct list_head tmp_link;
  58 };
  59
  60 /* Order-zero must be at least SZ_4K */
  61 #define DRM_BUDDY_MAX_ORDER (63 - 12)
  62
  63 /*
  64  * Binary Buddy System.
  65  *
  66  * Locking should be handled by the user, a simple mutex around
  67  * drm_buddy_alloc* and drm_buddy_free* should suffice.
  68  */
  69 struct drm_buddy {
  70         /* Maintain a free list for each order. */
  71         struct list_head *free_list;
  72
  73         /*
  74          * Maintain explicit binary tree(s) to track the allocation of the
  75          * address space. This gives us a simple way of finding a buddy block
  76          * and performing the potentially recursive merge step when freeing a
  77          * block.  Nodes are either allocated or free, in which case they will
  78          * also exist on the respective free list.
  79          */
  80         struct drm_buddy_block **roots;
  81
  82         /*
  83          * Anything from here is public, and remains static for the lifetime of
  84          * the mm. Everything above is considered do-not-touch.
  85          */
  86         unsigned int n_roots;
  87         unsigned int max_order;
  88
  89         /* Must be at least SZ_4K */
  90         u64 chunk_size;
  91         u64 size;
  92         u64 avail;
  93         u64 clear_avail;
  94 };
  95
  96 static inline u64
  97 drm_buddy_block_offset(struct drm_buddy_block *block)
  98 {
  99         return block->header & DRM_BUDDY_HEADER_OFFSET;
 100 }
 101
 102 static inline unsigned int
 103 drm_buddy_block_order(struct drm_buddy_block *block)
 104 {
 105         return block->header & DRM_BUDDY_HEADER_ORDER;
 106 }
 107
 108 static inline unsigned int
 109 drm_buddy_block_state(struct drm_buddy_block *block)
 110 {
 111         return block->header & DRM_BUDDY_HEADER_STATE;
 112 }
 113
 114 static inline bool
 115 drm_buddy_block_is_allocated(struct drm_buddy_block *block)
 116 {
 117         return drm_buddy_block_state(block) == DRM_BUDDY_ALLOCATED;
 118 }
 119
 120 static inline bool
 121 drm_buddy_block_is_clear(struct drm_buddy_block *block)
 122 {
 123         return block->header & DRM_BUDDY_HEADER_CLEAR;
 124 }
 125
 126 static inline bool
 127 drm_buddy_block_is_free(struct drm_buddy_block *block)
 128 {
 129         return drm_buddy_block_state(block) == DRM_BUDDY_FREE;
 130 }
 131
 132 static inline bool
 133 drm_buddy_block_is_split(struct drm_buddy_block *block)
 134 {
 135         return drm_buddy_block_state(block) == DRM_BUDDY_SPLIT;
 136 }
 137
 138 static inline u64
 139 drm_buddy_block_size(struct drm_buddy *mm,
 140                      struct drm_buddy_block *block)
 141 {
 142         return mm->chunk_size << drm_buddy_block_order(block);
 143 }
 144
 145 int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size);
 146
 147 void drm_buddy_fini(struct drm_buddy *mm);
 148
 149 struct drm_buddy_block *
 150 drm_get_buddy(struct drm_buddy_block *block);
 151
 152 int drm_buddy_alloc_blocks(struct drm_buddy *mm,
 153                            u64 start, u64 end, u64 size,
 154                            u64 min_page_size,
 155                            struct list_head *blocks,
 156                            unsigned long flags);
 157
 158 int drm_buddy_block_trim(struct drm_buddy *mm,
 159                          u64 *start,
 160                          u64 new_size,
 161                          struct list_head *blocks);
 162
 163 void drm_buddy_free_block(struct drm_buddy *mm, struct drm_buddy_block *block);
 164
 165 void drm_buddy_free_list(struct drm_buddy *mm,
 166                          struct list_head *objects,
 167                          unsigned int flags);
 168
 169 void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p);
 170 void drm_buddy_block_print(struct drm_buddy *mm,
 171                            struct drm_buddy_block *block,
 172                            struct drm_printer *p);
 173 #endif