drivers/gpu/drm/i915/i915_buddy.h

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