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