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