]>
Commit | Line | Data |
---|---|---|
eecf5eed PX |
1 | /* |
2 | * An very simplified 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 | #ifndef IOVA_TREE_H | |
12 | #define IOVA_TREE_H | |
13 | ||
14 | /* | |
15 | * Currently the iova tree will only allow to keep ranges | |
16 | * information, and no extra user data is allowed for each element. A | |
17 | * benefit is that we can merge adjacent ranges internally within the | |
18 | * tree. It can save a lot of memory when the ranges are splitted but | |
19 | * mostly continuous. | |
20 | * | |
21 | * Note that current implementation does not provide any thread | |
22 | * protections. Callers of the iova tree should be responsible | |
23 | * for the thread safety issue. | |
24 | */ | |
25 | ||
eecf5eed PX |
26 | #include "exec/memory.h" |
27 | #include "exec/hwaddr.h" | |
28 | ||
29 | #define IOVA_OK (0) | |
30 | #define IOVA_ERR_INVALID (-1) /* Invalid parameters */ | |
31 | #define IOVA_ERR_OVERLAP (-2) /* IOVA range overlapped */ | |
9376bde8 | 32 | #define IOVA_ERR_NOMEM (-3) /* Cannot allocate */ |
eecf5eed PX |
33 | |
34 | typedef struct IOVATree IOVATree; | |
35 | typedef struct DMAMap { | |
36 | hwaddr iova; | |
37 | hwaddr translated_addr; | |
38 | hwaddr size; /* Inclusive */ | |
39 | IOMMUAccessFlags perm; | |
40 | } QEMU_PACKED DMAMap; | |
41 | typedef gboolean (*iova_tree_iterator)(DMAMap *map); | |
42 | ||
43 | /** | |
44 | * iova_tree_new: | |
45 | * | |
46 | * Create a new iova tree. | |
47 | * | |
48 | * Returns: the tree pointer when succeeded, or NULL if error. | |
49 | */ | |
50 | IOVATree *iova_tree_new(void); | |
51 | ||
52 | /** | |
53 | * iova_tree_insert: | |
54 | * | |
55 | * @tree: the iova tree to insert | |
56 | * @map: the mapping to insert | |
57 | * | |
58 | * Insert an iova range to the tree. If there is overlapped | |
59 | * ranges, IOVA_ERR_OVERLAP will be returned. | |
60 | * | |
61 | * Return: 0 if succeeded, or <0 if error. | |
62 | */ | |
a89b34be | 63 | int iova_tree_insert(IOVATree *tree, const DMAMap *map); |
eecf5eed PX |
64 | |
65 | /** | |
66 | * iova_tree_remove: | |
67 | * | |
68 | * @tree: the iova tree to remove range from | |
69 | * @map: the map range to remove | |
70 | * | |
71 | * Remove mappings from the tree that are covered by the map range | |
72 | * provided. The range does not need to be exactly what has inserted, | |
73 | * all the mappings that are included in the provided range will be | |
74 | * removed from the tree. Here map->translated_addr is meaningless. | |
eecf5eed | 75 | */ |
832fef7c | 76 | void iova_tree_remove(IOVATree *tree, const DMAMap *map); |
eecf5eed PX |
77 | |
78 | /** | |
79 | * iova_tree_find: | |
80 | * | |
81 | * @tree: the iova tree to search from | |
82 | * @map: the mapping to search | |
83 | * | |
193d17be | 84 | * Search for a mapping in the iova tree that iova overlaps with the |
eecf5eed PX |
85 | * mapping range specified. Only the first found mapping will be |
86 | * returned. | |
87 | * | |
88 | * Return: DMAMap pointer if found, or NULL if not found. Note that | |
89 | * the returned DMAMap pointer is maintained internally. User should | |
90 | * only read the content but never modify or free the content. Also, | |
91 | * user is responsible to make sure the pointer is valid (say, no | |
92 | * concurrent deletion in progress). | |
93 | */ | |
a89b34be | 94 | const DMAMap *iova_tree_find(const IOVATree *tree, const DMAMap *map); |
eecf5eed | 95 | |
193d17be EP |
96 | /** |
97 | * iova_tree_find_iova: | |
98 | * | |
99 | * @tree: the iova tree to search from | |
100 | * @map: the mapping to search | |
101 | * | |
102 | * Search for a mapping in the iova tree that translated_addr overlaps with the | |
103 | * mapping range specified. Only the first found mapping will be | |
104 | * returned. | |
105 | * | |
106 | * Return: DMAMap pointer if found, or NULL if not found. Note that | |
107 | * the returned DMAMap pointer is maintained internally. User should | |
108 | * only read the content but never modify or free the content. Also, | |
109 | * user is responsible to make sure the pointer is valid (say, no | |
110 | * concurrent deletion in progress). | |
111 | */ | |
112 | const DMAMap *iova_tree_find_iova(const IOVATree *tree, const DMAMap *map); | |
113 | ||
eecf5eed PX |
114 | /** |
115 | * iova_tree_find_address: | |
116 | * | |
117 | * @tree: the iova tree to search from | |
118 | * @iova: the iova address to find | |
119 | * | |
120 | * Similar to iova_tree_find(), but it tries to find mapping with | |
121 | * range iova=iova & size=0. | |
122 | * | |
123 | * Return: same as iova_tree_find(). | |
124 | */ | |
a89b34be | 125 | const DMAMap *iova_tree_find_address(const IOVATree *tree, hwaddr iova); |
eecf5eed PX |
126 | |
127 | /** | |
128 | * iova_tree_foreach: | |
129 | * | |
130 | * @tree: the iova tree to iterate on | |
131 | * @iterator: the interator for the mappings, return true to stop | |
132 | * | |
133 | * Iterate over the iova tree. | |
134 | * | |
135 | * Return: 1 if found any overlap, 0 if not, <0 if error. | |
136 | */ | |
137 | void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator); | |
138 | ||
9376bde8 EP |
139 | /** |
140 | * iova_tree_alloc_map: | |
141 | * | |
142 | * @tree: the iova tree to allocate from | |
143 | * @map: the new map (as translated addr & size) to allocate in the iova region | |
144 | * @iova_begin: the minimum address of the allocation | |
145 | * @iova_end: the maximum addressable direction of the allocation | |
146 | * | |
147 | * Allocates a new region of a given size, between iova_min and iova_max. | |
148 | * | |
149 | * Return: Same as iova_tree_insert, but cannot overlap and can return error if | |
150 | * iova tree is out of free contiguous range. The caller gets the assigned iova | |
151 | * in map->iova. | |
152 | */ | |
153 | int iova_tree_alloc_map(IOVATree *tree, DMAMap *map, hwaddr iova_begin, | |
154 | hwaddr iova_end); | |
155 | ||
eecf5eed PX |
156 | /** |
157 | * iova_tree_destroy: | |
158 | * | |
159 | * @tree: the iova tree to destroy | |
160 | * | |
161 | * Destroy an existing iova tree. | |
162 | * | |
163 | * Return: None. | |
164 | */ | |
165 | void iova_tree_destroy(IOVATree *tree); | |
166 | ||
167 | #endif |