drm_buddy.h

  1/* SPDX-License-Identifier: MIT */
  2/*
  3 * Copyright © 2021 Intel Corporation
  4 */
  5
  6#ifndef __DRM_BUDDY_H__
  7#define __DRM_BUDDY_H__
  8
  9#include <linux/bitops.h>
 10#include <linux/list.h>
 11#include <linux/slab.h>
 12#include <linux/sched.h>
 13#include <linux/rbtree.h>
 14
 15struct drm_printer;
 16
 17#define DRM_BUDDY_RANGE_ALLOCATION		BIT(0)
 18#define DRM_BUDDY_TOPDOWN_ALLOCATION		BIT(1)
 19#define DRM_BUDDY_CONTIGUOUS_ALLOCATION		BIT(2)
 20#define DRM_BUDDY_CLEAR_ALLOCATION		BIT(3)
 21#define DRM_BUDDY_CLEARED			BIT(4)
 22#define DRM_BUDDY_TRIM_DISABLE			BIT(5)
 23
 24struct drm_buddy_block {
 25#define DRM_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12)
 26#define DRM_BUDDY_HEADER_STATE  GENMASK_ULL(11, 10)
 27#define   DRM_BUDDY_ALLOCATED	   (1 << 10)
 28#define   DRM_BUDDY_FREE	   (2 << 10)
 29#define   DRM_BUDDY_SPLIT	   (3 << 10)
 30#define DRM_BUDDY_HEADER_CLEAR  GENMASK_ULL(9, 9)
 31/* Free to be used, if needed in the future */
 32#define DRM_BUDDY_HEADER_UNUSED GENMASK_ULL(8, 6)
 33#define DRM_BUDDY_HEADER_ORDER  GENMASK_ULL(5, 0)
 34	u64 header;
 35
 36	struct drm_buddy_block *left;
 37	struct drm_buddy_block *right;
 38	struct drm_buddy_block *parent;
 39
 40	void *private; /* owned by creator */
 41
 42	/*
 43	 * While the block is allocated by the user through drm_buddy_alloc*,
 44	 * the user has ownership of the link, for example to maintain within
 45	 * a list, if so desired. As soon as the block is freed with
 46	 * drm_buddy_free* ownership is given back to the mm.
 47	 */
 48	union {
 49		struct rb_node rb;
 50		struct list_head link;
 51	};
 52
 53	struct list_head tmp_link;
 54};
 55
 56/* Order-zero must be at least SZ_4K */
 57#define DRM_BUDDY_MAX_ORDER (63 - 12)
 58
 59/*
 60 * Binary Buddy System.
 61 *
 62 * Locking should be handled by the user, a simple mutex around
 63 * drm_buddy_alloc* and drm_buddy_free* should suffice.
 64 */
 65struct drm_buddy {
 66	/* Maintain a free list for each order. */
 67	struct rb_root **free_trees;
 68
 69	/*
 70	 * Maintain explicit binary tree(s) to track the allocation of the
 71	 * address space. This gives us a simple way of finding a buddy block
 72	 * and performing the potentially recursive merge step when freeing a
 73	 * block.  Nodes are either allocated or free, in which case they will
 74	 * also exist on the respective free list.
 75	 */
 76	struct drm_buddy_block **roots;
 77
 78	/*
 79	 * Anything from here is public, and remains static for the lifetime of
 80	 * the mm. Everything above is considered do-not-touch.
 81	 */
 82	unsigned int n_roots;
 83	unsigned int max_order;
 84
 85	/* Must be at least SZ_4K */
 86	u64 chunk_size;
 87	u64 size;
 88	u64 avail;
 89	u64 clear_avail;
 90};
 91
 92static inline u64
 93drm_buddy_block_offset(const struct drm_buddy_block *block)
 94{
 95	return block->header & DRM_BUDDY_HEADER_OFFSET;
 96}
 97
 98static inline unsigned int
 99drm_buddy_block_order(struct drm_buddy_block *block)
100{
101	return block->header & DRM_BUDDY_HEADER_ORDER;
102}
103
104static inline unsigned int
105drm_buddy_block_state(struct drm_buddy_block *block)
106{
107	return block->header & DRM_BUDDY_HEADER_STATE;
108}
109
110static inline bool
111drm_buddy_block_is_allocated(struct drm_buddy_block *block)
112{
113	return drm_buddy_block_state(block) == DRM_BUDDY_ALLOCATED;
114}
115
116static inline bool
117drm_buddy_block_is_clear(struct drm_buddy_block *block)
118{
119	return block->header & DRM_BUDDY_HEADER_CLEAR;
120}
121
122static inline bool
123drm_buddy_block_is_free(struct drm_buddy_block *block)
124{
125	return drm_buddy_block_state(block) == DRM_BUDDY_FREE;
126}
127
128static inline bool
129drm_buddy_block_is_split(struct drm_buddy_block *block)
130{
131	return drm_buddy_block_state(block) == DRM_BUDDY_SPLIT;
132}
133
134static inline u64
135drm_buddy_block_size(struct drm_buddy *mm,
136		     struct drm_buddy_block *block)
137{
138	return mm->chunk_size << drm_buddy_block_order(block);
139}
140
141int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size);
142
143void drm_buddy_fini(struct drm_buddy *mm);
144
145struct drm_buddy_block *
146drm_get_buddy(struct drm_buddy_block *block);
147
148int drm_buddy_alloc_blocks(struct drm_buddy *mm,
149			   u64 start, u64 end, u64 size,
150			   u64 min_page_size,
151			   struct list_head *blocks,
152			   unsigned long flags);
153
154int drm_buddy_block_trim(struct drm_buddy *mm,
155			 u64 *start,
156			 u64 new_size,
157			 struct list_head *blocks);
158
159void drm_buddy_reset_clear(struct drm_buddy *mm, bool is_clear);
160
161void drm_buddy_free_block(struct drm_buddy *mm, struct drm_buddy_block *block);
162
163void drm_buddy_free_list(struct drm_buddy *mm,
164			 struct list_head *objects,
165			 unsigned int flags);
166
167void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p);
168void drm_buddy_block_print(struct drm_buddy *mm,
169			   struct drm_buddy_block *block,
170			   struct drm_printer *p);
171#endif