xref: /openbmc/qemu/include/qemu/iova-tree.h (revision d02d06f8)
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 split 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 #define  IOVA_ERR_NOMEM    (-3) /* Cannot allocate */
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  */
63 int iova_tree_insert(IOVATree *tree, const DMAMap *map);
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.
75  */
76 void iova_tree_remove(IOVATree *tree, DMAMap map);
77 
78 /**
79  * iova_tree_find:
80  *
81  * @tree: the iova tree to search from
82  * @map: the mapping to search
83  *
84  * Search for a mapping in the iova tree that iova overlaps with the
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  */
94 const DMAMap *iova_tree_find(const IOVATree *tree, const DMAMap *map);
95 
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 
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  */
125 const DMAMap *iova_tree_find_address(const IOVATree *tree, hwaddr iova);
126 
127 /**
128  * iova_tree_foreach:
129  *
130  * @tree: the iova tree to iterate on
131  * @iterator: the iterator 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 
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 
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
168