LXR linux/drivers/gpu/drm/i915/i915

   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
  12struct 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 */
  45struct 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
  70static inline u64
  71i915_buddy_block_offset(struct i915_buddy_block *block)
  72{
  73        return block->header & I915_BUDDY_HEADER_OFFSET;
  74}
  75
  76static inline unsigned int
  77i915_buddy_block_order(struct i915_buddy_block *block)
  78{
  79        return block->header & I915_BUDDY_HEADER_ORDER;
  80}
  81
  82static inline unsigned int
  83i915_buddy_block_state(struct i915_buddy_block *block)
  84{
  85        return block->header & I915_BUDDY_HEADER_STATE;
  86}
  87
  88static inline bool
  89i915_buddy_block_is_allocated(struct i915_buddy_block *block)
  90{
  91        return i915_buddy_block_state(block) == I915_BUDDY_ALLOCATED;
  92}
  93
  94static inline bool
  95i915_buddy_block_is_free(struct i915_buddy_block *block)
  96{
  97        return i915_buddy_block_state(block) == I915_BUDDY_FREE;
  98}
  99
 100static inline bool
 101i915_buddy_block_is_split(struct i915_buddy_block *block)
 102{
 103        return i915_buddy_block_state(block) == I915_BUDDY_SPLIT;
 104}
 105
 106static inline u64
 107i915_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
 113int i915_buddy_init(struct i915_buddy_mm *mm, u64 size, u64 chunk_size);
 114
 115void i915_buddy_fini(struct i915_buddy_mm *mm);
 116
 117struct i915_buddy_block *
 118i915_buddy_alloc(struct i915_buddy_mm *mm, unsigned int order);
 119
 120int i915_buddy_alloc_range(struct i915_buddy_mm *mm,
 121                           struct list_head *blocks,
 122                           u64 start, u64 size);
 123
 124void i915_buddy_free(struct i915_buddy_mm *mm, struct i915_buddy_block *block);
 125
 126void i915_buddy_free_list(struct i915_buddy_mm *mm, struct list_head *objects);
 127
 128#endif
 129