2 * An very simplified iova tree implementation based on GTree.
4 * Copyright 2018 Red Hat, Inc.
7 * Peter Xu <peterx@redhat.com>
9 * This work is licensed under the terms of the GNU GPL, version 2 or later.
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
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.
26 #include "exec/memory.h"
27 #include "exec/hwaddr.h"
30 #define IOVA_ERR_INVALID (-1) /* Invalid parameters */
31 #define IOVA_ERR_OVERLAP (-2) /* IOVA range overlapped */
33 typedef struct IOVATree IOVATree
;
34 typedef struct DMAMap
{
36 hwaddr translated_addr
;
37 hwaddr size
; /* Inclusive */
38 IOMMUAccessFlags perm
;
40 typedef gboolean (*iova_tree_iterator
)(DMAMap
*map
);
45 * Create a new iova tree.
47 * Returns: the tree pointer when succeeded, or NULL if error.
49 IOVATree
*iova_tree_new(void);
54 * @tree: the iova tree to insert
55 * @map: the mapping to insert
57 * Insert an iova range to the tree. If there is overlapped
58 * ranges, IOVA_ERR_OVERLAP will be returned.
60 * Return: 0 if succeeded, or <0 if error.
62 int iova_tree_insert(IOVATree
*tree
, const DMAMap
*map
);
67 * @tree: the iova tree to remove range from
68 * @map: the map range to remove
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.
75 * Return: 0 if succeeded, or <0 if error.
77 int iova_tree_remove(IOVATree
*tree
, const DMAMap
*map
);
82 * @tree: the iova tree to search from
83 * @map: the mapping to search
85 * Search for a mapping in the iova tree that overlaps with the
86 * mapping range specified. Only the first found mapping will be
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).
95 const DMAMap
*iova_tree_find(const IOVATree
*tree
, const DMAMap
*map
);
98 * iova_tree_find_address:
100 * @tree: the iova tree to search from
101 * @iova: the iova address to find
103 * Similar to iova_tree_find(), but it tries to find mapping with
104 * range iova=iova & size=0.
106 * Return: same as iova_tree_find().
108 const DMAMap
*iova_tree_find_address(const IOVATree
*tree
, hwaddr iova
);
113 * @tree: the iova tree to iterate on
114 * @iterator: the interator for the mappings, return true to stop
116 * Iterate over the iova tree.
118 * Return: 1 if found any overlap, 0 if not, <0 if error.
120 void iova_tree_foreach(IOVATree
*tree
, iova_tree_iterator iterator
);
125 * @tree: the iova tree to destroy
127 * Destroy an existing iova tree.
131 void iova_tree_destroy(IOVATree
*tree
);