drivers/gpu/drm/i915/i915_buddy.h

   1 /* SPDX-License-Identifier: MIT */
   2 /*
   3  * Copyright © 2021 Intel Corporation
   4  */
   5
   6 #ifndef __I915_BUDDY_H__
   7 #define __I915_BUDDY_H__
   8
   9 #include <linux/bitops.h>
  10 #include <linux/list.h>
  11 #include <linux/slab.h>
  12
  13 struct i915_buddy_block {
  14 #define I915_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12)
  15 #define I915_BUDDY_HEADER_STATE  GENMASK_ULL(11, 10)
  16 #define   I915_BUDDY_ALLOCATED     (1 << 10)
  17 #define   I915_BUDDY_FREE          (2 << 10)
  18 #define   I915_BUDDY_SPLIT         (3 << 10)
  19 /* Free to be used, if needed in the future */
  20 #define I915_BUDDY_HEADER_UNUSED GENMASK_ULL(9, 6)
  21 #define I915_BUDDY_HEADER_ORDER  GENMASK_ULL(5, 0)
  22         u64 header;
  23
  24         struct i915_buddy_block *left;
  25         struct i915_buddy_block *right;
  26         struct i915_buddy_block *parent;
  27
  28         void *private; /* owned by creator */
  29
  30         /*
  31          * While the block is allocated by the user through i915_buddy_alloc*,
  32          * the user has ownership of the link, for example to maintain within
  33          * a list, if so desired. As soon as the block is freed with
  34          * i915_buddy_free* ownership is given back to the mm.
  35          */
  36         struct list_head link;
  37         struct list_head tmp_link;
  38 };
  39
  40 /* Order-zero must be at least PAGE_SIZE */
  41 #define I915_BUDDY_MAX_ORDER (63 - PAGE_SHIFT)
  42
  43 /*
  44  * Binary Buddy System.
  45  *
  46  * Locking should be handled by the user, a simple mutex around
  47  * i915_buddy_alloc* and i915_buddy_free* should suffice.
  48  */
  49 struct i915_buddy_mm {
  50         /* Maintain a free list for each order. */
  51         struct list_head *free_list;
  52
  53         /*
  54          * Maintain explicit binary tree(s) to track the allocation of the
  55          * address space. This gives us a simple way of finding a buddy block
  56          * and performing the potentially recursive merge step when freeing a
  57          * block.  Nodes are either allocated or free, in which case they will
  58          * also exist on the respective free list.
  59          */
  60         struct i915_buddy_block **roots;
  61
  62         /*
  63          * Anything from here is public, and remains static for the lifetime of
  64          * the mm. Everything above is considered do-not-touch.
  65          */
  66         unsigned int n_roots;
  67         unsigned int max_order;
  68
  69         /* Must be at least PAGE_SIZE */
  70         u64 chunk_size;
  71         u64 size;
  72 };
  73
  74 static inline u64
  75 i915_buddy_block_offset(struct i915_buddy_block *block)
  76 {
  77         return block->header & I915_BUDDY_HEADER_OFFSET;
  78 }
  79
  80 static inline unsigned int
  81 i915_buddy_block_order(struct i915_buddy_block *block)
  82 {
  83         return block->header & I915_BUDDY_HEADER_ORDER;
  84 }
  85
  86 static inline unsigned int
  87 i915_buddy_block_state(struct i915_buddy_block *block)
  88 {
  89         return block->header & I915_BUDDY_HEADER_STATE;
  90 }
  91
  92 static inline bool
  93 i915_buddy_block_is_allocated(struct i915_buddy_block *block)
  94 {
  95         return i915_buddy_block_state(block) == I915_BUDDY_ALLOCATED;
  96 }
  97
  98 static inline bool
  99 i915_buddy_block_is_free(struct i915_buddy_block *block)
 100 {
 101         return i915_buddy_block_state(block) == I915_BUDDY_FREE;
 102 }
 103
 104 static inline bool
 105 i915_buddy_block_is_split(struct i915_buddy_block *block)
 106 {
 107         return i915_buddy_block_state(block) == I915_BUDDY_SPLIT;
 108 }
 109
 110 static inline u64
 111 i915_buddy_block_size(struct i915_buddy_mm *mm,
 112                       struct i915_buddy_block *block)
 113 {
 114         return mm->chunk_size << i915_buddy_block_order(block);
 115 }
 116
 117 int i915_buddy_init(struct i915_buddy_mm *mm, u64 size, u64 chunk_size);
 118
 119 void i915_buddy_fini(struct i915_buddy_mm *mm);
 120
 121 struct i915_buddy_block *
 122 i915_buddy_alloc(struct i915_buddy_mm *mm, unsigned int order);
 123
 124 int i915_buddy_alloc_range(struct i915_buddy_mm *mm,
 125                            struct list_head *blocks,
 126                            u64 start, u64 size);
 127
 128 void i915_buddy_free(struct i915_buddy_mm *mm, struct i915_buddy_block *block);
 129
 130 void i915_buddy_free_list(struct i915_buddy_mm *mm, struct list_head *objects);
 131
 132 void i915_buddy_module_exit(void);
 133 int i915_buddy_module_init(void);
 134
 135 #endif