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 | |
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 */ |
32 | |
33 | typedef struct IOVATree IOVATree; |
34 | typedef struct DMAMap { |
35 | hwaddr iova; |
36 | hwaddr translated_addr; |
37 | hwaddr size; /* Inclusive */ |
38 | IOMMUAccessFlags perm; |
39 | } QEMU_PACKED DMAMap; |
40 | typedef gboolean (*iova_tree_iterator)(DMAMap *map); |
41 | |
42 | /** |
43 | * iova_tree_new: |
44 | * |
45 | * Create a new iova tree. |
46 | * |
47 | * Returns: the tree pointer when succeeded, or NULL if error. |
48 | */ |
49 | IOVATree *iova_tree_new(void); |
50 | |
51 | /** |
52 | * iova_tree_insert: |
53 | * |
54 | * @tree: the iova tree to insert |
55 | * @map: the mapping to insert |
56 | * |
57 | * Insert an iova range to the tree. If there is overlapped |
58 | * ranges, IOVA_ERR_OVERLAP will be returned. |
59 | * |
60 | * Return: 0 if succeeded, or <0 if error. |
61 | */ |
62 | int iova_tree_insert(IOVATree *tree, DMAMap *map); |
63 | |
64 | /** |
65 | * iova_tree_remove: |
66 | * |
67 | * @tree: the iova tree to remove range from |
68 | * @map: the map range to remove |
69 | * |
70 | * Remove mappings from the tree that are covered by the map range |
71 | * provided. The range does not need to be exactly what has inserted, |
72 | * all the mappings that are included in the provided range will be |
73 | * removed from the tree. Here map->translated_addr is meaningless. |
74 | * |
75 | * Return: 0 if succeeded, or <0 if error. |
76 | */ |
77 | int iova_tree_remove(IOVATree *tree, DMAMap *map); |
78 | |
79 | /** |
80 | * iova_tree_find: |
81 | * |
82 | * @tree: the iova tree to search from |
83 | * @map: the mapping to search |
84 | * |
85 | * Search for a mapping in the iova tree that overlaps with the |
86 | * mapping range specified. Only the first found mapping will be |
87 | * returned. |
88 | * |
89 | * Return: DMAMap pointer if found, or NULL if not found. Note that |
90 | * the returned DMAMap pointer is maintained internally. User should |
91 | * only read the content but never modify or free the content. Also, |
92 | * user is responsible to make sure the pointer is valid (say, no |
93 | * concurrent deletion in progress). |
94 | */ |
95 | DMAMap *iova_tree_find(IOVATree *tree, DMAMap *map); |
96 | |
97 | /** |
98 | * iova_tree_find_address: |
99 | * |
100 | * @tree: the iova tree to search from |
101 | * @iova: the iova address to find |
102 | * |
103 | * Similar to iova_tree_find(), but it tries to find mapping with |
104 | * range iova=iova & size=0. |
105 | * |
106 | * Return: same as iova_tree_find(). |
107 | */ |
108 | DMAMap *iova_tree_find_address(IOVATree *tree, hwaddr iova); |
109 | |
110 | /** |
111 | * iova_tree_foreach: |
112 | * |
113 | * @tree: the iova tree to iterate on |
114 | * @iterator: the interator for the mappings, return true to stop |
115 | * |
116 | * Iterate over the iova tree. |
117 | * |
118 | * Return: 1 if found any overlap, 0 if not, <0 if error. |
119 | */ |
120 | void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator); |
121 | |
122 | /** |
123 | * iova_tree_destroy: |
124 | * |
125 | * @tree: the iova tree to destroy |
126 | * |
127 | * Destroy an existing iova tree. |
128 | * |
129 | * Return: None. |
130 | */ |
131 | void iova_tree_destroy(IOVATree *tree); |
132 | |
133 | #endif |
134 | |