xref: /openbmc/qemu/util/iova-tree.c (revision 69292a8e)
1 /*
2  * IOVA tree implementation based on GTree.
3  *
4  * Copyright 2018 Red Hat, Inc.
5  *
6  * Authors:
7  *  Peter Xu <peterx@redhat.com>
8  *
9  * This work is licensed under the terms of the GNU GPL, version 2 or later.
10  */
11 
12 #include "qemu/osdep.h"
13 #include "qemu/iova-tree.h"
14 
15 struct IOVATree {
16     GTree *tree;
17 };
18 
19 /* Args to pass to iova_tree_alloc foreach function. */
20 struct IOVATreeAllocArgs {
21     /* Size of the desired allocation */
22     size_t new_size;
23 
24     /* The minimum address allowed in the allocation */
25     hwaddr iova_begin;
26 
27     /* Map at the left of the hole, can be NULL if "this" is first one */
28     const DMAMap *prev;
29 
30     /* Map at the right of the hole, can be NULL if "prev" is the last one */
31     const DMAMap *this;
32 
33     /* If found, we fill in the IOVA here */
34     hwaddr iova_result;
35 
36     /* Whether have we found a valid IOVA */
37     bool iova_found;
38 };
39 
40 typedef struct IOVATreeFindIOVAArgs {
41     const DMAMap *needle;
42     const DMAMap *result;
43 } IOVATreeFindIOVAArgs;
44 
45 /**
46  * Iterate args to the next hole
47  *
48  * @args: The alloc arguments
49  * @next: The next mapping in the tree. Can be NULL to signal the last one
50  */
iova_tree_alloc_args_iterate(struct IOVATreeAllocArgs * args,const DMAMap * next)51 static 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 
iova_tree_compare(gconstpointer a,gconstpointer b,gpointer data)58 static 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     /* Overlapped */
71     return 0;
72 }
73 
iova_tree_new(void)74 IOVATree *iova_tree_new(void)
75 {
76     IOVATree *iova_tree = g_new0(IOVATree, 1);
77 
78     /* We don't have values actually, no need to free */
79     iova_tree->tree = g_tree_new_full(iova_tree_compare, NULL, g_free, NULL);
80 
81     return iova_tree;
82 }
83 
iova_tree_find(const IOVATree * tree,const DMAMap * map)84 const DMAMap *iova_tree_find(const IOVATree *tree, const DMAMap *map)
85 {
86     return g_tree_lookup(tree->tree, map);
87 }
88 
iova_tree_find_address_iterator(gpointer key,gpointer value,gpointer data)89 static 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 
iova_tree_find_iova(const IOVATree * tree,const DMAMap * map)108 const 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 
iova_tree_find_address(const IOVATree * tree,hwaddr iova)118 const 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 
iova_tree_insert_internal(GTree * gtree,DMAMap * range)125 static inline void iova_tree_insert_internal(GTree *gtree, DMAMap *range)
126 {
127     /* Key and value are sharing the same range data */
128     g_tree_insert(gtree, range, range);
129 }
130 
iova_tree_insert(IOVATree * tree,const DMAMap * map)131 int 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     /* We don't allow to insert range that overlaps with existings */
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 
iova_tree_traverse(gpointer key,gpointer value,gpointer data)151 static 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 
iova_tree_foreach(IOVATree * tree,iova_tree_iterator iterator)162 void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator)
163 {
164     g_tree_foreach(tree->tree, iova_tree_traverse, iterator);
165 }
166 
iova_tree_remove(IOVATree * tree,DMAMap map)167 void 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  * Try to find an unallocated IOVA range between prev and this elements.
178  *
179  * @args: Arguments to allocation
180  *
181  * Cases:
182  *
183  * (1) !prev, !this: No entries allocated, always succeed
184  *
185  * (2) !prev, this: We're iterating at the 1st element.
186  *
187  * (3) prev, !this: We're iterating at the last element.
188  *
189  * (4) prev, this: this is the most common case, we'll try to find a hole
190  * between "prev" and "this" mapping.
191  *
192  * Note that this function assumes the last valid iova is HWADDR_MAX, but it
193  * searches linearly so it's easy to discard the result if it's not the case.
194  */
iova_tree_alloc_map_in_hole(struct IOVATreeAllocArgs * args)195 static 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  * Foreach dma node in the tree, compare if there is a hole with its previous
215  * node (or minimum iova address allowed) and the node.
216  *
217  * @key: Node iterating
218  * @value: Node iterating
219  * @pargs: Struct to communicate with the outside world
220  *
221  * Return: false to keep iterating, true if needs break.
222  */
iova_tree_alloc_traverse(gpointer key,gpointer value,gpointer pargs)223 static 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 
iova_tree_alloc_map(IOVATree * tree,DMAMap * map,hwaddr iova_begin,hwaddr iova_last)236 int 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      * Find a valid hole for the mapping
250      *
251      * Assuming low iova_begin, so no need to do a binary search to
252      * locate the first node.
253      *
254      * TODO: Replace all this with g_tree_node_first/next/last when available
255      * (from glib since 2.68). To do it with g_tree_foreach complicates the
256      * code a lot.
257      *
258      */
259     g_tree_foreach(tree->tree, iova_tree_alloc_traverse, &args);
260     if (!args.iova_found) {
261         /*
262          * Either tree is empty or the last hole is still not checked.
263          * g_tree_foreach does not compare (last, iova_last] range, so we check
264          * it here.
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 
iova_tree_destroy(IOVATree * tree)278 void iova_tree_destroy(IOVATree *tree)
279 {
280     g_tree_destroy(tree->tree);
281     g_free(tree);
282 }
283