This function does the reverse operation of iova_tree_find: To look for
a mapping that match a translated address so we can do the reverse.
This have linear complexity instead of logarithmic, but it supports
overlapping HVA. Future developments could reduce it.
Signed-off-by: Eugenio Pérez <epere...@redhat.com>
---
include/qemu/iova-tree.h | 20 +++++++++++++++++++-
util/iova-tree.c | 34 ++++++++++++++++++++++++++++++++++
2 files changed, 53 insertions(+), 1 deletion(-)
diff --git a/include/qemu/iova-tree.h b/include/qemu/iova-tree.h
index d066400f09..c938fb0793 100644
--- a/include/qemu/iova-tree.h
+++ b/include/qemu/iova-tree.h
@@ -83,7 +83,7 @@ int iova_tree_remove(IOVATree *tree, const DMAMap *map);
* @tree: the iova tree to search from
* @map: the mapping to search
*
- * Search for a mapping in the iova tree that overlaps with the
+ * Search for a mapping in the iova tree that iova overlaps with the
* mapping range specified. Only the first found mapping will be
* returned.
*
@@ -95,6 +95,24 @@ int iova_tree_remove(IOVATree *tree, const DMAMap *map);
*/
const DMAMap *iova_tree_find(const IOVATree *tree, const DMAMap *map);
+/**
+ * iova_tree_find_iova:
+ *
+ * @tree: the iova tree to search from
+ * @map: the mapping to search
+ *
+ * Search for a mapping in the iova tree that translated_addr overlaps with the
+ * mapping range specified. Only the first found mapping will be
+ * returned.
+ *
+ * Return: DMAMap pointer if found, or NULL if not found. Note that
+ * the returned DMAMap pointer is maintained internally. User should
+ * only read the content but never modify or free the content. Also,
+ * user is responsible to make sure the pointer is valid (say, no
+ * concurrent deletion in progress).
+ */
+const DMAMap *iova_tree_find_iova(const IOVATree *tree, const DMAMap *map);
+
/**
* iova_tree_find_address:
*
diff --git a/util/iova-tree.c b/util/iova-tree.c
index 3160c50d3b..f015598977 100644
--- a/util/iova-tree.c
+++ b/util/iova-tree.c
@@ -37,6 +37,11 @@ struct IOVATreeAllocArgs {
bool iova_found;
};
+typedef struct IOVATreeFindIOVAArgs {
+ const DMAMap *needle;
+ const DMAMap *result;
+} IOVATreeFindIOVAArgs;
+
/**
* Iterate args to the next hole
*
@@ -80,6 +85,35 @@ const DMAMap *iova_tree_find(const IOVATree *tree, const
DMAMap *map)
return g_tree_lookup(tree->tree, map);
}
+static gboolean iova_tree_find_address_iterator(gpointer key, gpointer value,
+ gpointer data)
+{
+ const DMAMap *map = key;
+ IOVATreeFindIOVAArgs *args = data;
+ const DMAMap *needle;
+
+ g_assert(key == value);
+
+ needle = args->needle;
+ if (map->translated_addr + map->size < needle->translated_addr ||
+ needle->translated_addr + needle->size < map->translated_addr) {
+ return false;
+ }
+
+ args->result = map;
+ return true;
+}
+
+const DMAMap *iova_tree_find_iova(const IOVATree *tree, const DMAMap *map)
+{
+ IOVATreeFindIOVAArgs args = {
+ .needle = map,
+ };
+
+ g_tree_foreach(tree->tree, iova_tree_find_address_iterator, &args);
+ return args.result;
+}
+
const DMAMap *iova_tree_find_address(const IOVATree *tree, hwaddr iova)
{
const DMAMap map = { .iova = iova, .size = 0 };
--
2.27.0
