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