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