1
2
3
4
5
6
7
8
9
10
11
12#include "qemu/osdep.h"
13#include "qemu/iova-tree.h"
14
15struct IOVATree {
16 GTree *tree;
17};
18
19
20struct IOVATreeAllocArgs {
21
22 size_t new_size;
23
24
25 hwaddr iova_begin;
26
27
28 const DMAMap *prev;
29
30
31 const DMAMap *this;
32
33
34 hwaddr iova_result;
35
36
37 bool iova_found;
38};
39
40typedef struct IOVATreeFindIOVAArgs {
41 const DMAMap *needle;
42 const DMAMap *result;
43} IOVATreeFindIOVAArgs;
44
45
46
47
48
49
50
51static void iova_tree_alloc_args_iterate(struct IOVATreeAllocArgs *args,
52 const DMAMap *next)
53{
54 args->prev = args->this;
55 args->this = next;
56}
57
58static int iova_tree_compare(gconstpointer a, gconstpointer b, gpointer data)
59{
60 const DMAMap *m1 = a, *m2 = b;
61
62 if (m1->iova > m2->iova + m2->size) {
63 return 1;
64 }
65
66 if (m1->iova + m1->size < m2->iova) {
67 return -1;
68 }
69
70
71 return 0;
72}
73
74IOVATree *iova_tree_new(void)
75{
76 IOVATree *iova_tree = g_new0(IOVATree, 1);
77
78
79 iova_tree->tree = g_tree_new_full(iova_tree_compare, NULL, g_free, NULL);
80
81 return iova_tree;
82}
83
84const DMAMap *iova_tree_find(const IOVATree *tree, const DMAMap *map)
85{
86 return g_tree_lookup(tree->tree, map);
87}
88
89static gboolean iova_tree_find_address_iterator(gpointer key, gpointer value,
90 gpointer data)
91{
92 const DMAMap *map = key;
93 IOVATreeFindIOVAArgs *args = data;
94 const DMAMap *needle;
95
96 g_assert(key == value);
97
98 needle = args->needle;
99 if (map->translated_addr + map->size < needle->translated_addr ||
100 needle->translated_addr + needle->size < map->translated_addr) {
101 return false;
102 }
103
104 args->result = map;
105 return true;
106}
107
108const DMAMap *iova_tree_find_iova(const IOVATree *tree, const DMAMap *map)
109{
110 IOVATreeFindIOVAArgs args = {
111 .needle = map,
112 };
113
114 g_tree_foreach(tree->tree, iova_tree_find_address_iterator, &args);
115 return args.result;
116}
117
118const DMAMap *iova_tree_find_address(const IOVATree *tree, hwaddr iova)
119{
120 const DMAMap map = { .iova = iova, .size = 0 };
121
122 return iova_tree_find(tree, &map);
123}
124
125static inline void iova_tree_insert_internal(GTree *gtree, DMAMap *range)
126{
127
128 g_tree_insert(gtree, range, range);
129}
130
131int iova_tree_insert(IOVATree *tree, const DMAMap *map)
132{
133 DMAMap *new;
134
135 if (map->iova + map->size < map->iova || map->perm == IOMMU_NONE) {
136 return IOVA_ERR_INVALID;
137 }
138
139
140 if (iova_tree_find(tree, map)) {
141 return IOVA_ERR_OVERLAP;
142 }
143
144 new = g_new0(DMAMap, 1);
145 memcpy(new, map, sizeof(*new));
146 iova_tree_insert_internal(tree->tree, new);
147
148 return IOVA_OK;
149}
150
151static gboolean iova_tree_traverse(gpointer key, gpointer value,
152 gpointer data)
153{
154 iova_tree_iterator iterator = data;
155 DMAMap *map = key;
156
157 g_assert(key == value);
158
159 return iterator(map);
160}
161
162void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator)
163{
164 g_tree_foreach(tree->tree, iova_tree_traverse, iterator);
165}
166
167void iova_tree_remove(IOVATree *tree, DMAMap map)
168{
169 const DMAMap *overlap;
170
171 while ((overlap = iova_tree_find(tree, &map))) {
172 g_tree_remove(tree->tree, overlap);
173 }
174}
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195static void iova_tree_alloc_map_in_hole(struct IOVATreeAllocArgs *args)
196{
197 const DMAMap *prev = args->prev, *this = args->this;
198 uint64_t hole_start, hole_last;
199
200 if (this && this->iova + this->size < args->iova_begin) {
201 return;
202 }
203
204 hole_start = MAX(prev ? prev->iova + prev->size + 1 : 0, args->iova_begin);
205 hole_last = this ? this->iova : HWADDR_MAX;
206
207 if (hole_last - hole_start > args->new_size) {
208 args->iova_result = hole_start;
209 args->iova_found = true;
210 }
211}
212
213
214
215
216
217
218
219
220
221
222
223static gboolean iova_tree_alloc_traverse(gpointer key, gpointer value,
224 gpointer pargs)
225{
226 struct IOVATreeAllocArgs *args = pargs;
227 DMAMap *node = value;
228
229 assert(key == value);
230
231 iova_tree_alloc_args_iterate(args, node);
232 iova_tree_alloc_map_in_hole(args);
233 return args->iova_found;
234}
235
236int iova_tree_alloc_map(IOVATree *tree, DMAMap *map, hwaddr iova_begin,
237 hwaddr iova_last)
238{
239 struct IOVATreeAllocArgs args = {
240 .new_size = map->size,
241 .iova_begin = iova_begin,
242 };
243
244 if (unlikely(iova_last < iova_begin)) {
245 return IOVA_ERR_INVALID;
246 }
247
248
249
250
251
252
253
254
255
256
257
258
259 g_tree_foreach(tree->tree, iova_tree_alloc_traverse, &args);
260 if (!args.iova_found) {
261
262
263
264
265
266 iova_tree_alloc_args_iterate(&args, NULL);
267 iova_tree_alloc_map_in_hole(&args);
268 }
269
270 if (!args.iova_found || args.iova_result + map->size > iova_last) {
271 return IOVA_ERR_NOMEM;
272 }
273
274 map->iova = args.iova_result;
275 return iova_tree_insert(tree, map);
276}
277
278void iova_tree_destroy(IOVATree *tree)
279{
280 g_tree_destroy(tree->tree);
281 g_free(tree);
282}
283