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