[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH v6 09/15] util: add iova_tree_find_iova
From: |
Eugenio Pérez |
Subject: |
[PATCH v6 09/15] util: add iova_tree_find_iova |
Date: |
Mon, 14 Mar 2022 18:34:49 +0100 |
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 <eperezma@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 139626b46f..6dff29c1f6 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
*
@@ -81,6 +86,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
- [PATCH v6 01/15] vhost: Add VhostShadowVirtqueue, (continued)
- [PATCH v6 01/15] vhost: Add VhostShadowVirtqueue, Eugenio Pérez, 2022/03/14
- [PATCH v6 03/15] vhost: Add Shadow VirtQueue call forwarding capabilities, Eugenio Pérez, 2022/03/14
- [PATCH v6 10/15] vhost: Add VhostIOVATree, Eugenio Pérez, 2022/03/14
- [PATCH v6 14/15] vdpa: Expose VHOST_F_LOG_ALL on SVQ, Eugenio Pérez, 2022/03/14
- [PATCH v6 06/15] vdpa: adapt vhost_ops callbacks to svq, Eugenio Pérez, 2022/03/14
- [PATCH v6 02/15] vhost: Add Shadow VirtQueue kick forwarding capabilities, Eugenio Pérez, 2022/03/14
- [PATCH v6 11/15] vdpa: Add custom IOTLB translations to SVQ, Eugenio Pérez, 2022/03/14
- [PATCH v6 08/15] util: Add iova_tree_alloc_map, Eugenio Pérez, 2022/03/14
- [PATCH v6 04/15] vhost: Add vhost_svq_valid_features to shadow vq, Eugenio Pérez, 2022/03/14
- [PATCH v6 07/15] vhost: Shadow virtqueue buffers forwarding, Eugenio Pérez, 2022/03/14
- [PATCH v6 09/15] util: add iova_tree_find_iova,
Eugenio Pérez <=
- [PATCH v6 12/15] vdpa: Adapt vhost_vdpa_get_vring_base to SVQ, Eugenio Pérez, 2022/03/14
- [PATCH v6 05/15] virtio: Add vhost_svq_get_vring_addr, Eugenio Pérez, 2022/03/14
- [PATCH v6 13/15] vdpa: Never set log_base addr if SVQ is enabled, Eugenio Pérez, 2022/03/14
- [PATCH v6 15/15] vdpa: Add x-svq to NetdevVhostVDPAOptions, Eugenio Pérez, 2022/03/14