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 BIT(0)
26#define DRM_BUDDY_TOPDOWN_ALLOCATION BIT(1)
27#define DRM_BUDDY_CONTIGUOUS_ALLOCATION BIT(2)
28
29struct drm_buddy_block {
30#define DRM_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12)
31#define DRM_BUDDY_HEADER_STATE GENMASK_ULL(11, 10)
32#define DRM_BUDDY_ALLOCATED (1 << 10)
33#define DRM_BUDDY_FREE (2 << 10)
34#define DRM_BUDDY_SPLIT (3 << 10)
35/* Free to be used, if needed in the future */
36#define DRM_BUDDY_HEADER_UNUSED GENMASK_ULL(9, 6)
37#define DRM_BUDDY_HEADER_ORDER GENMASK_ULL(5, 0)
38 u64 header;
39
40 struct drm_buddy_block *left;
41 struct drm_buddy_block *right;
42 struct drm_buddy_block *parent;
43
44 void *private; /* owned by creator */
45
46 /*
47 * While the block is allocated by the user through drm_buddy_alloc*,
48 * the user has ownership of the link, for example to maintain within
49 * a list, if so desired. As soon as the block is freed with
50 * drm_buddy_free* ownership is given back to the mm.
51 */
52 struct list_head link;
53 struct list_head tmp_link;
54};
55
56/* Order-zero must be at least PAGE_SIZE */
57#define DRM_BUDDY_MAX_ORDER (63 - PAGE_SHIFT)
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 list_head *free_list;
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 PAGE_SIZE */
86 u64 chunk_size;
87 u64 size;
88 u64 avail;
89};
90
91static inline u64
92drm_buddy_block_offset(struct drm_buddy_block *block)
93{
94 return block->header & DRM_BUDDY_HEADER_OFFSET;
95}
96
97static inline unsigned int
98drm_buddy_block_order(struct drm_buddy_block *block)
99{
100 return block->header & DRM_BUDDY_HEADER_ORDER;
101}
102
103static inline unsigned int
104drm_buddy_block_state(struct drm_buddy_block *block)
105{
106 return block->header & DRM_BUDDY_HEADER_STATE;
107}
108
109static inline bool
110drm_buddy_block_is_allocated(struct drm_buddy_block *block)
111{
112 return drm_buddy_block_state(block) == DRM_BUDDY_ALLOCATED;
113}
114
115static inline bool
116drm_buddy_block_is_free(struct drm_buddy_block *block)
117{
118 return drm_buddy_block_state(block) == DRM_BUDDY_FREE;
119}
120
121static inline bool
122drm_buddy_block_is_split(struct drm_buddy_block *block)
123{
124 return drm_buddy_block_state(block) == DRM_BUDDY_SPLIT;
125}
126
127static inline u64
128drm_buddy_block_size(struct drm_buddy *mm,
129 struct drm_buddy_block *block)
130{
131 return mm->chunk_size << drm_buddy_block_order(block);
132}
133
134int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size);
135
136void drm_buddy_fini(struct drm_buddy *mm);
137
138struct drm_buddy_block *
139drm_get_buddy(struct drm_buddy_block *block);
140
141int drm_buddy_alloc_blocks(struct drm_buddy *mm,
142 u64 start, u64 end, u64 size,
143 u64 min_page_size,
144 struct list_head *blocks,
145 unsigned long flags);
146
147int drm_buddy_block_trim(struct drm_buddy *mm,
148 u64 new_size,
149 struct list_head *blocks);
150
151void drm_buddy_free_block(struct drm_buddy *mm, struct drm_buddy_block *block);
152
153void drm_buddy_free_list(struct drm_buddy *mm, struct list_head *objects);
154
155void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p);
156void drm_buddy_block_print(struct drm_buddy *mm,
157 struct drm_buddy_block *block,
158 struct drm_printer *p);
159#endif
160

source code of linux/include/drm/drm_buddy.h