[RFC v3 22/29] vhost: Add iova_rev_maps_find_iova to IOVAReverseMaps

["Eugenio Pérez" <eperezma@redhat.com>]

Shadow virtqueue can translate addresses from guest's address to it's
own address space this way. It duplicates the array so it can search
efficiently both directions, and it will signal overlap if iova or the
translated address is present in it's each array.

Signed-off-by: Eugenio Pérez <eperezma@redhat.com>
---
 hw/virtio/vhost-iova-tree.h | 10 +++++++-
 hw/virtio/vhost-iova-tree.c | 49 ++++++++++++++++++++++++++++++++++---
 2 files changed, 55 insertions(+), 4 deletions(-)

diff --git a/hw/virtio/vhost-iova-tree.h b/hw/virtio/vhost-iova-tree.h
index 2a44af8b3a..589e86bd91 100644
--- a/hw/virtio/vhost-iova-tree.h
+++ b/hw/virtio/vhost-iova-tree.h
@@ -30,18 +30,26 @@ typedef enum VhostDMAMapNewRC {
 /**
  * VhostIOVATree
  *
- * Store and search IOVA -> Translated mappings.
+ * Store and search IOVA -> Translated mappings and the reverse, from
+ * translated address to IOVA.
  *
  * Note that it cannot remove nodes.
  */
 typedef struct VhostIOVATree {
     /* Ordered array of reverse translations, IOVA address to qemu memory. */
     GArray *iova_taddr_map;
+
+    /*
+     * Ordered array of translations from qemu virtual memory address to iova
+     */
+    GArray *taddr_iova_map;
 } VhostIOVATree;
 
 void vhost_iova_tree_new(VhostIOVATree *iova_rm);
 void vhost_iova_tree_destroy(VhostIOVATree *iova_rm);
 
+const VhostDMAMap *vhost_iova_tree_find_iova(const VhostIOVATree *iova_rm,
+                                             const VhostDMAMap *map);
 const VhostDMAMap *vhost_iova_tree_find_taddr(const VhostIOVATree *iova_rm,
                                               const VhostDMAMap *map);
 VhostDMAMapNewRC vhost_iova_tree_insert(VhostIOVATree *iova_rm,
diff --git a/hw/virtio/vhost-iova-tree.c b/hw/virtio/vhost-iova-tree.c
index dfd7e448b5..2900390a1e 100644
--- a/hw/virtio/vhost-iova-tree.c
+++ b/hw/virtio/vhost-iova-tree.c
@@ -39,6 +39,22 @@ static void vhost_iova_tree_insert_after(GArray *array,
     g_array_insert_val(array, pos, *map);
 }
 
+static gint vhost_iova_tree_cmp_taddr(gconstpointer a, gconstpointer b)
+{
+    const VhostDMAMap *m1 = a, *m2 = b;
+
+    if (m1->translated_addr > m2->translated_addr + m2->size) {
+        return 1;
+    }
+
+    if (m1->translated_addr + m1->size < m2->translated_addr) {
+        return -1;
+    }
+
+    /* Overlapped */
+    return 0;
+}
+
 static gint vhost_iova_tree_cmp_iova(gconstpointer a, gconstpointer b)
 {
     const VhostDMAMap *m1 = a, *m2 = b;
@@ -106,6 +122,9 @@ void vhost_iova_tree_new(VhostIOVATree *tree)
     tree->iova_taddr_map = g_array_new(G_ARRAY_NOT_ZERO_TERMINATED,
                                        G_ARRAY_NOT_CLEAR_ON_ALLOC,
                                        sizeof(VhostDMAMap));
+    tree->taddr_iova_map = g_array_new(G_ARRAY_NOT_ZERO_TERMINATED,
+                                       G_ARRAY_NOT_CLEAR_ON_ALLOC,
+                                       sizeof(VhostDMAMap));
 }
 
 /**
@@ -116,6 +135,7 @@ void vhost_iova_tree_new(VhostIOVATree *tree)
 void vhost_iova_tree_destroy(VhostIOVATree *tree)
 {
     g_array_unref(g_steal_pointer(&tree->iova_taddr_map));
+    g_array_unref(g_steal_pointer(&tree->taddr_iova_map));
 }
 
 /**
@@ -137,6 +157,21 @@ static const VhostDMAMap *vhost_iova_tree_bsearch(const GArray *array,
     return bsearch(map, array->data, array->len, sizeof(*map), compare_func);
 }
 
+/**
+ * Find the IOVA address stored from a memory address
+ *
+ * @tree     The iova tree
+ * @map      The map with the memory address
+ *
+ * Return the stored mapping, or NULL if not found.
+ */
+const VhostDMAMap *vhost_iova_tree_find_iova(const VhostIOVATree *tree,
+                                             const VhostDMAMap *map)
+{
+    return vhost_iova_tree_bsearch(tree->taddr_iova_map, map,
+                                   vhost_iova_tree_cmp_taddr);
+}
+
 /**
  * Find the translated address stored from a IOVA address
  *
@@ -167,7 +202,7 @@ const VhostDMAMap *vhost_iova_tree_find_taddr(const VhostIOVATree *tree,
 VhostDMAMapNewRC vhost_iova_tree_insert(VhostIOVATree *tree,
                                         VhostDMAMap *map)
 {
-    const VhostDMAMap *prev;
+    const VhostDMAMap *qemu_prev, *iova_prev;
     int find_prev_rc;
 
     if (map->translated_addr + map->size < map->translated_addr ||
@@ -178,11 +213,19 @@ VhostDMAMapNewRC vhost_iova_tree_insert(VhostIOVATree *tree,
     /* Check for duplicates, and save position for insertion */
     find_prev_rc = vhost_iova_tree_find_prev(tree->iova_taddr_map,
                                              vhost_iova_tree_cmp_iova, map,
-                                             &prev);
+                                             &iova_prev);
+    if (find_prev_rc == VHOST_DMA_MAP_OVERLAP) {
+        return VHOST_DMA_MAP_OVERLAP;
+    }
+
+    find_prev_rc = vhost_iova_tree_find_prev(tree->taddr_iova_map,
+                                             vhost_iova_tree_cmp_taddr, map,
+                                             &qemu_prev);
     if (find_prev_rc == VHOST_DMA_MAP_OVERLAP) {
         return VHOST_DMA_MAP_OVERLAP;
     }
 
-    vhost_iova_tree_insert_after(tree->iova_taddr_map, prev, map);
+    vhost_iova_tree_insert_after(tree->iova_taddr_map, iova_prev, map);
+    vhost_iova_tree_insert_after(tree->taddr_iova_map, qemu_prev, map);
     return VHOST_DMA_MAP_OK;
 }
-- 
2.27.0