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
15struct IOVATree {
16 GTree *tree;
17};
18
19static 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
35IOVATree *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
45DMAMap *iova_tree_find(IOVATree *tree, DMAMap *map)
46{
47 return g_tree_lookup(tree->tree, map);
48}
49
50DMAMap *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
57static 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
63int 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
83static 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
94void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator)
95{
96 g_tree_foreach(tree->tree, iova_tree_traverse, iterator);
97}
98
99int 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
110void iova_tree_destroy(IOVATree *tree)
111{
112 g_tree_destroy(tree->tree);
113 g_free(tree);
114}
115