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 | |