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