1eecf5eedSPeter Xu /*
2eecf5eedSPeter Xu * IOVA tree implementation based on GTree.
3eecf5eedSPeter Xu *
4eecf5eedSPeter Xu * Copyright 2018 Red Hat, Inc.
5eecf5eedSPeter Xu *
6eecf5eedSPeter Xu * Authors:
7eecf5eedSPeter Xu * Peter Xu <peterx@redhat.com>
8eecf5eedSPeter Xu *
9eecf5eedSPeter Xu * This work is licensed under the terms of the GNU GPL, version 2 or later.
10eecf5eedSPeter Xu */
11eecf5eedSPeter Xu
12c5f1d0c4SDaniel P. Berrangé #include "qemu/osdep.h"
13eecf5eedSPeter Xu #include "qemu/iova-tree.h"
14eecf5eedSPeter Xu
15eecf5eedSPeter Xu struct IOVATree {
16eecf5eedSPeter Xu GTree *tree;
17eecf5eedSPeter Xu };
18eecf5eedSPeter Xu
199376bde8SEugenio Pérez /* Args to pass to iova_tree_alloc foreach function. */
209376bde8SEugenio Pérez struct IOVATreeAllocArgs {
219376bde8SEugenio Pérez /* Size of the desired allocation */
229376bde8SEugenio Pérez size_t new_size;
239376bde8SEugenio Pérez
249376bde8SEugenio Pérez /* The minimum address allowed in the allocation */
259376bde8SEugenio Pérez hwaddr iova_begin;
269376bde8SEugenio Pérez
279376bde8SEugenio Pérez /* Map at the left of the hole, can be NULL if "this" is first one */
289376bde8SEugenio Pérez const DMAMap *prev;
299376bde8SEugenio Pérez
309376bde8SEugenio Pérez /* Map at the right of the hole, can be NULL if "prev" is the last one */
319376bde8SEugenio Pérez const DMAMap *this;
329376bde8SEugenio Pérez
339376bde8SEugenio Pérez /* If found, we fill in the IOVA here */
349376bde8SEugenio Pérez hwaddr iova_result;
359376bde8SEugenio Pérez
369376bde8SEugenio Pérez /* Whether have we found a valid IOVA */
379376bde8SEugenio Pérez bool iova_found;
389376bde8SEugenio Pérez };
399376bde8SEugenio Pérez
40193d17beSEugenio Pérez typedef struct IOVATreeFindIOVAArgs {
41193d17beSEugenio Pérez const DMAMap *needle;
42193d17beSEugenio Pérez const DMAMap *result;
43193d17beSEugenio Pérez } IOVATreeFindIOVAArgs;
44193d17beSEugenio Pérez
459376bde8SEugenio Pérez /**
469376bde8SEugenio Pérez * Iterate args to the next hole
479376bde8SEugenio Pérez *
489376bde8SEugenio Pérez * @args: The alloc arguments
499376bde8SEugenio Pérez * @next: The next mapping in the tree. Can be NULL to signal the last one
509376bde8SEugenio Pérez */
iova_tree_alloc_args_iterate(struct IOVATreeAllocArgs * args,const DMAMap * next)519376bde8SEugenio Pérez static void iova_tree_alloc_args_iterate(struct IOVATreeAllocArgs *args,
529376bde8SEugenio Pérez const DMAMap *next)
539376bde8SEugenio Pérez {
549376bde8SEugenio Pérez args->prev = args->this;
559376bde8SEugenio Pérez args->this = next;
569376bde8SEugenio Pérez }
579376bde8SEugenio Pérez
iova_tree_compare(gconstpointer a,gconstpointer b,gpointer data)58eecf5eedSPeter Xu static int iova_tree_compare(gconstpointer a, gconstpointer b, gpointer data)
59eecf5eedSPeter Xu {
60eecf5eedSPeter Xu const DMAMap *m1 = a, *m2 = b;
61eecf5eedSPeter Xu
62eecf5eedSPeter Xu if (m1->iova > m2->iova + m2->size) {
63eecf5eedSPeter Xu return 1;
64eecf5eedSPeter Xu }
65eecf5eedSPeter Xu
66eecf5eedSPeter Xu if (m1->iova + m1->size < m2->iova) {
67eecf5eedSPeter Xu return -1;
68eecf5eedSPeter Xu }
69eecf5eedSPeter Xu
70eecf5eedSPeter Xu /* Overlapped */
71eecf5eedSPeter Xu return 0;
72eecf5eedSPeter Xu }
73eecf5eedSPeter Xu
iova_tree_new(void)74eecf5eedSPeter Xu IOVATree *iova_tree_new(void)
75eecf5eedSPeter Xu {
76eecf5eedSPeter Xu IOVATree *iova_tree = g_new0(IOVATree, 1);
77eecf5eedSPeter Xu
78eecf5eedSPeter Xu /* We don't have values actually, no need to free */
79eecf5eedSPeter Xu iova_tree->tree = g_tree_new_full(iova_tree_compare, NULL, g_free, NULL);
80eecf5eedSPeter Xu
81eecf5eedSPeter Xu return iova_tree;
82eecf5eedSPeter Xu }
83eecf5eedSPeter Xu
iova_tree_find(const IOVATree * tree,const DMAMap * map)84a89b34beSEugenio Pérez const DMAMap *iova_tree_find(const IOVATree *tree, const DMAMap *map)
85eecf5eedSPeter Xu {
86eecf5eedSPeter Xu return g_tree_lookup(tree->tree, map);
87eecf5eedSPeter Xu }
88eecf5eedSPeter Xu
iova_tree_find_address_iterator(gpointer key,gpointer value,gpointer data)89193d17beSEugenio Pérez static gboolean iova_tree_find_address_iterator(gpointer key, gpointer value,
90193d17beSEugenio Pérez gpointer data)
91193d17beSEugenio Pérez {
92193d17beSEugenio Pérez const DMAMap *map = key;
93193d17beSEugenio Pérez IOVATreeFindIOVAArgs *args = data;
94193d17beSEugenio Pérez const DMAMap *needle;
95193d17beSEugenio Pérez
96193d17beSEugenio Pérez g_assert(key == value);
97193d17beSEugenio Pérez
98193d17beSEugenio Pérez needle = args->needle;
99193d17beSEugenio Pérez if (map->translated_addr + map->size < needle->translated_addr ||
100193d17beSEugenio Pérez needle->translated_addr + needle->size < map->translated_addr) {
101193d17beSEugenio Pérez return false;
102193d17beSEugenio Pérez }
103193d17beSEugenio Pérez
104193d17beSEugenio Pérez args->result = map;
105193d17beSEugenio Pérez return true;
106193d17beSEugenio Pérez }
107193d17beSEugenio Pérez
iova_tree_find_iova(const IOVATree * tree,const DMAMap * map)108193d17beSEugenio Pérez const DMAMap *iova_tree_find_iova(const IOVATree *tree, const DMAMap *map)
109193d17beSEugenio Pérez {
110193d17beSEugenio Pérez IOVATreeFindIOVAArgs args = {
111193d17beSEugenio Pérez .needle = map,
112193d17beSEugenio Pérez };
113193d17beSEugenio Pérez
114193d17beSEugenio Pérez g_tree_foreach(tree->tree, iova_tree_find_address_iterator, &args);
115193d17beSEugenio Pérez return args.result;
116193d17beSEugenio Pérez }
117193d17beSEugenio Pérez
iova_tree_find_address(const IOVATree * tree,hwaddr iova)118a89b34beSEugenio Pérez const DMAMap *iova_tree_find_address(const IOVATree *tree, hwaddr iova)
119eecf5eedSPeter Xu {
120a89b34beSEugenio Pérez const DMAMap map = { .iova = iova, .size = 0 };
121eecf5eedSPeter Xu
122eecf5eedSPeter Xu return iova_tree_find(tree, &map);
123eecf5eedSPeter Xu }
124eecf5eedSPeter Xu
iova_tree_insert_internal(GTree * gtree,DMAMap * range)125eecf5eedSPeter Xu static inline void iova_tree_insert_internal(GTree *gtree, DMAMap *range)
126eecf5eedSPeter Xu {
127eecf5eedSPeter Xu /* Key and value are sharing the same range data */
128eecf5eedSPeter Xu g_tree_insert(gtree, range, range);
129eecf5eedSPeter Xu }
130eecf5eedSPeter Xu
iova_tree_insert(IOVATree * tree,const DMAMap * map)131a89b34beSEugenio Pérez int iova_tree_insert(IOVATree *tree, const DMAMap *map)
132eecf5eedSPeter Xu {
133eecf5eedSPeter Xu DMAMap *new;
134eecf5eedSPeter Xu
135eecf5eedSPeter Xu if (map->iova + map->size < map->iova || map->perm == IOMMU_NONE) {
136eecf5eedSPeter Xu return IOVA_ERR_INVALID;
137eecf5eedSPeter Xu }
138eecf5eedSPeter Xu
139eecf5eedSPeter Xu /* We don't allow to insert range that overlaps with existings */
140eecf5eedSPeter Xu if (iova_tree_find(tree, map)) {
141eecf5eedSPeter Xu return IOVA_ERR_OVERLAP;
142eecf5eedSPeter Xu }
143eecf5eedSPeter Xu
144eecf5eedSPeter Xu new = g_new0(DMAMap, 1);
145eecf5eedSPeter Xu memcpy(new, map, sizeof(*new));
146eecf5eedSPeter Xu iova_tree_insert_internal(tree->tree, new);
147eecf5eedSPeter Xu
148eecf5eedSPeter Xu return IOVA_OK;
149eecf5eedSPeter Xu }
150eecf5eedSPeter Xu
iova_tree_traverse(gpointer key,gpointer value,gpointer data)151eecf5eedSPeter Xu static gboolean iova_tree_traverse(gpointer key, gpointer value,
152eecf5eedSPeter Xu gpointer data)
153eecf5eedSPeter Xu {
154eecf5eedSPeter Xu iova_tree_iterator iterator = data;
155eecf5eedSPeter Xu DMAMap *map = key;
156eecf5eedSPeter Xu
157eecf5eedSPeter Xu g_assert(key == value);
158eecf5eedSPeter Xu
159eecf5eedSPeter Xu return iterator(map);
160eecf5eedSPeter Xu }
161eecf5eedSPeter Xu
iova_tree_foreach(IOVATree * tree,iova_tree_iterator iterator)162eecf5eedSPeter Xu void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator)
163eecf5eedSPeter Xu {
164eecf5eedSPeter Xu g_tree_foreach(tree->tree, iova_tree_traverse, iterator);
165eecf5eedSPeter Xu }
166eecf5eedSPeter Xu
iova_tree_remove(IOVATree * tree,DMAMap map)167*69292a8eSEugenio Pérez void iova_tree_remove(IOVATree *tree, DMAMap map)
168eecf5eedSPeter Xu {
169a89b34beSEugenio Pérez const DMAMap *overlap;
170eecf5eedSPeter Xu
171*69292a8eSEugenio Pérez while ((overlap = iova_tree_find(tree, &map))) {
172eecf5eedSPeter Xu g_tree_remove(tree->tree, overlap);
173eecf5eedSPeter Xu }
174eecf5eedSPeter Xu }
175eecf5eedSPeter Xu
1769376bde8SEugenio Pérez /**
1779376bde8SEugenio Pérez * Try to find an unallocated IOVA range between prev and this elements.
1789376bde8SEugenio Pérez *
1799376bde8SEugenio Pérez * @args: Arguments to allocation
1809376bde8SEugenio Pérez *
1819376bde8SEugenio Pérez * Cases:
1829376bde8SEugenio Pérez *
1839376bde8SEugenio Pérez * (1) !prev, !this: No entries allocated, always succeed
1849376bde8SEugenio Pérez *
1859376bde8SEugenio Pérez * (2) !prev, this: We're iterating at the 1st element.
1869376bde8SEugenio Pérez *
1879376bde8SEugenio Pérez * (3) prev, !this: We're iterating at the last element.
1889376bde8SEugenio Pérez *
1899376bde8SEugenio Pérez * (4) prev, this: this is the most common case, we'll try to find a hole
1909376bde8SEugenio Pérez * between "prev" and "this" mapping.
1919376bde8SEugenio Pérez *
1929376bde8SEugenio Pérez * Note that this function assumes the last valid iova is HWADDR_MAX, but it
1939376bde8SEugenio Pérez * searches linearly so it's easy to discard the result if it's not the case.
1949376bde8SEugenio Pérez */
iova_tree_alloc_map_in_hole(struct IOVATreeAllocArgs * args)1959376bde8SEugenio Pérez static void iova_tree_alloc_map_in_hole(struct IOVATreeAllocArgs *args)
1969376bde8SEugenio Pérez {
1979376bde8SEugenio Pérez const DMAMap *prev = args->prev, *this = args->this;
1989376bde8SEugenio Pérez uint64_t hole_start, hole_last;
1999376bde8SEugenio Pérez
2009376bde8SEugenio Pérez if (this && this->iova + this->size < args->iova_begin) {
2019376bde8SEugenio Pérez return;
2029376bde8SEugenio Pérez }
2039376bde8SEugenio Pérez
2049376bde8SEugenio Pérez hole_start = MAX(prev ? prev->iova + prev->size + 1 : 0, args->iova_begin);
2059376bde8SEugenio Pérez hole_last = this ? this->iova : HWADDR_MAX;
2069376bde8SEugenio Pérez
2079376bde8SEugenio Pérez if (hole_last - hole_start > args->new_size) {
2089376bde8SEugenio Pérez args->iova_result = hole_start;
2099376bde8SEugenio Pérez args->iova_found = true;
2109376bde8SEugenio Pérez }
2119376bde8SEugenio Pérez }
2129376bde8SEugenio Pérez
2139376bde8SEugenio Pérez /**
2149376bde8SEugenio Pérez * Foreach dma node in the tree, compare if there is a hole with its previous
2159376bde8SEugenio Pérez * node (or minimum iova address allowed) and the node.
2169376bde8SEugenio Pérez *
2179376bde8SEugenio Pérez * @key: Node iterating
2189376bde8SEugenio Pérez * @value: Node iterating
2199376bde8SEugenio Pérez * @pargs: Struct to communicate with the outside world
2209376bde8SEugenio Pérez *
2219376bde8SEugenio Pérez * Return: false to keep iterating, true if needs break.
2229376bde8SEugenio Pérez */
iova_tree_alloc_traverse(gpointer key,gpointer value,gpointer pargs)2239376bde8SEugenio Pérez static gboolean iova_tree_alloc_traverse(gpointer key, gpointer value,
2249376bde8SEugenio Pérez gpointer pargs)
2259376bde8SEugenio Pérez {
2269376bde8SEugenio Pérez struct IOVATreeAllocArgs *args = pargs;
2279376bde8SEugenio Pérez DMAMap *node = value;
2289376bde8SEugenio Pérez
2299376bde8SEugenio Pérez assert(key == value);
2309376bde8SEugenio Pérez
2319376bde8SEugenio Pérez iova_tree_alloc_args_iterate(args, node);
2329376bde8SEugenio Pérez iova_tree_alloc_map_in_hole(args);
2339376bde8SEugenio Pérez return args->iova_found;
2349376bde8SEugenio Pérez }
2359376bde8SEugenio Pérez
iova_tree_alloc_map(IOVATree * tree,DMAMap * map,hwaddr iova_begin,hwaddr iova_last)2369376bde8SEugenio Pérez int iova_tree_alloc_map(IOVATree *tree, DMAMap *map, hwaddr iova_begin,
2379376bde8SEugenio Pérez hwaddr iova_last)
2389376bde8SEugenio Pérez {
2399376bde8SEugenio Pérez struct IOVATreeAllocArgs args = {
2409376bde8SEugenio Pérez .new_size = map->size,
2419376bde8SEugenio Pérez .iova_begin = iova_begin,
2429376bde8SEugenio Pérez };
2439376bde8SEugenio Pérez
2449376bde8SEugenio Pérez if (unlikely(iova_last < iova_begin)) {
2459376bde8SEugenio Pérez return IOVA_ERR_INVALID;
2469376bde8SEugenio Pérez }
2479376bde8SEugenio Pérez
2489376bde8SEugenio Pérez /*
2499376bde8SEugenio Pérez * Find a valid hole for the mapping
2509376bde8SEugenio Pérez *
2519376bde8SEugenio Pérez * Assuming low iova_begin, so no need to do a binary search to
2529376bde8SEugenio Pérez * locate the first node.
2539376bde8SEugenio Pérez *
2549376bde8SEugenio Pérez * TODO: Replace all this with g_tree_node_first/next/last when available
2559376bde8SEugenio Pérez * (from glib since 2.68). To do it with g_tree_foreach complicates the
2569376bde8SEugenio Pérez * code a lot.
2579376bde8SEugenio Pérez *
2589376bde8SEugenio Pérez */
2599376bde8SEugenio Pérez g_tree_foreach(tree->tree, iova_tree_alloc_traverse, &args);
2609376bde8SEugenio Pérez if (!args.iova_found) {
2619376bde8SEugenio Pérez /*
2629376bde8SEugenio Pérez * Either tree is empty or the last hole is still not checked.
2639376bde8SEugenio Pérez * g_tree_foreach does not compare (last, iova_last] range, so we check
2649376bde8SEugenio Pérez * it here.
2659376bde8SEugenio Pérez */
2669376bde8SEugenio Pérez iova_tree_alloc_args_iterate(&args, NULL);
2679376bde8SEugenio Pérez iova_tree_alloc_map_in_hole(&args);
2689376bde8SEugenio Pérez }
2699376bde8SEugenio Pérez
2709376bde8SEugenio Pérez if (!args.iova_found || args.iova_result + map->size > iova_last) {
2719376bde8SEugenio Pérez return IOVA_ERR_NOMEM;
2729376bde8SEugenio Pérez }
2739376bde8SEugenio Pérez
2749376bde8SEugenio Pérez map->iova = args.iova_result;
2759376bde8SEugenio Pérez return iova_tree_insert(tree, map);
2769376bde8SEugenio Pérez }
2779376bde8SEugenio Pérez
iova_tree_destroy(IOVATree * tree)278eecf5eedSPeter Xu void iova_tree_destroy(IOVATree *tree)
279eecf5eedSPeter Xu {
280eecf5eedSPeter Xu g_tree_destroy(tree->tree);
281eecf5eedSPeter Xu g_free(tree);
282eecf5eedSPeter Xu }
283