1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
/*
* IOVA tree implementation based on GTree.
*
* Copyright 2018 Red Hat, Inc.
*
* Authors:
* Peter Xu <peterx@redhat.com>
*
* This work is licensed under the terms of the GNU GPL, version 2 or later.
*/
#include <glib.h>
#include "qemu/iova-tree.h"
struct IOVATree {
GTree *tree;
};
static int iova_tree_compare(gconstpointer a, gconstpointer b, gpointer data)
{
const DMAMap *m1 = a, *m2 = b;
if (m1->iova > m2->iova + m2->size) {
return 1;
}
if (m1->iova + m1->size < m2->iova) {
return -1;
}
/* Overlapped */
return 0;
}
IOVATree *iova_tree_new(void)
{
IOVATree *iova_tree = g_new0(IOVATree, 1);
/* We don't have values actually, no need to free */
iova_tree->tree = g_tree_new_full(iova_tree_compare, NULL, g_free, NULL);
return iova_tree;
}
DMAMap *iova_tree_find(IOVATree *tree, DMAMap *map)
{
return g_tree_lookup(tree->tree, map);
}
DMAMap *iova_tree_find_address(IOVATree *tree, hwaddr iova)
{
DMAMap map = { .iova = iova, .size = 0 };
return iova_tree_find(tree, &map);
}
static inline void iova_tree_insert_internal(GTree *gtree, DMAMap *range)
{
/* Key and value are sharing the same range data */
g_tree_insert(gtree, range, range);
}
int iova_tree_insert(IOVATree *tree, DMAMap *map)
{
DMAMap *new;
if (map->iova + map->size < map->iova || map->perm == IOMMU_NONE) {
return IOVA_ERR_INVALID;
}
/* We don't allow to insert range that overlaps with existings */
if (iova_tree_find(tree, map)) {
return IOVA_ERR_OVERLAP;
}
new = g_new0(DMAMap, 1);
memcpy(new, map, sizeof(*new));
iova_tree_insert_internal(tree->tree, new);
return IOVA_OK;
}
static gboolean iova_tree_traverse(gpointer key, gpointer value,
gpointer data)
{
iova_tree_iterator iterator = data;
DMAMap *map = key;
g_assert(key == value);
return iterator(map);
}
void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator)
{
g_tree_foreach(tree->tree, iova_tree_traverse, iterator);
}
int iova_tree_remove(IOVATree *tree, DMAMap *map)
{
DMAMap *overlap;
while ((overlap = iova_tree_find(tree, map))) {
g_tree_remove(tree->tree, overlap);
}
return IOVA_OK;
}
void iova_tree_destroy(IOVATree *tree)
{
g_tree_destroy(tree->tree);
g_free(tree);
}
|
