xref: /qemu/util/iova-tree.c (revision fc8c745d) 
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 static int iova_tree_compare(gconstpointer a, gconstpointer b, gpointer data)
20 {
21     const DMAMap *m1 = a, *m2 = b;
22 
23     if (m1->iova > m2->iova + m2->size) {
24         return 1;
25     }
26 
27     if (m1->iova + m1->size < m2->iova) {
28         return -1;
29     }
30 
31     /* Overlapped */
32     return 0;
33 }
34 
35 IOVATree *iova_tree_new(void)
36 {
37     IOVATree *iova_tree = g_new0(IOVATree, 1);
38 
39     /* We don't have values actually, no need to free */
40     iova_tree->tree = g_tree_new_full(iova_tree_compare, NULL, g_free, NULL);
41 
42     return iova_tree;
43 }
44 
45 DMAMap *iova_tree_find(IOVATree *tree, DMAMap *map)
46 {
47     return g_tree_lookup(tree->tree, map);
48 }
49 
50 DMAMap *iova_tree_find_address(IOVATree *tree, hwaddr iova)
51 {
52     DMAMap map = { .iova = iova, .size = 0 };
53 
54     return iova_tree_find(tree, &map);
55 }
56 
57 static inline void iova_tree_insert_internal(GTree *gtree, DMAMap *range)
58 {
59     /* Key and value are sharing the same range data */
60     g_tree_insert(gtree, range, range);
61 }
62 
63 int iova_tree_insert(IOVATree *tree, DMAMap *map)
64 {
65     DMAMap *new;
66 
67     if (map->iova + map->size < map->iova || map->perm == IOMMU_NONE) {
68         return IOVA_ERR_INVALID;
69     }
70 
71     /* We don't allow to insert range that overlaps with existings */
72     if (iova_tree_find(tree, map)) {
73         return IOVA_ERR_OVERLAP;
74     }
75 
76     new = g_new0(DMAMap, 1);
77     memcpy(new, map, sizeof(*new));
78     iova_tree_insert_internal(tree->tree, new);
79 
80     return IOVA_OK;
81 }
82 
83 static gboolean iova_tree_traverse(gpointer key, gpointer value,
84                                 gpointer data)
85 {
86     iova_tree_iterator iterator = data;
87     DMAMap *map = key;
88 
89     g_assert(key == value);
90 
91     return iterator(map);
92 }
93 
94 void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator)
95 {
96     g_tree_foreach(tree->tree, iova_tree_traverse, iterator);
97 }
98 
99 int iova_tree_remove(IOVATree *tree, DMAMap *map)
100 {
101     DMAMap *overlap;
102 
103     while ((overlap = iova_tree_find(tree, map))) {
104         g_tree_remove(tree->tree, overlap);
105     }
106 
107     return IOVA_OK;
108 }
109 
110 void iova_tree_destroy(IOVATree *tree)
111 {
112     g_tree_destroy(tree->tree);
113     g_free(tree);
114 }
115