From: "Eugenio Pérez" <eperezma@redhat.com>
To: qemu-devel@nongnu.org
Cc: Parav Pandit <parav@mellanox.com>,
"Michael S. Tsirkin" <mst@redhat.com>,
Jason Wang <jasowang@redhat.com>,
Juan Quintela <quintela@redhat.com>,
Markus Armbruster <armbru@redhat.com>,
virtualization@lists.linux-foundation.org,
Harpreet Singh Anand <hanand@xilinx.com>,
Xiao W Wang <xiao.w.wang@intel.com>,
Stefan Hajnoczi <stefanha@redhat.com>,
Eli Cohen <eli@mellanox.com>, Michael Lilja <ml@napatech.com>,
Stefano Garzarella <sgarzare@redhat.com>
Subject: [RFC v3 21/29] vhost: Add VhostIOVATree
Date: Wed, 19 May 2021 18:28:55 +0200 [thread overview]
Message-ID: <20210519162903.1172366-22-eperezma@redhat.com> (raw)
In-Reply-To: <20210519162903.1172366-1-eperezma@redhat.com>
This tree is able to look for a translated address from a IOVA address.
At first glance is similar to util/iova-tree. However, SVQ working on
devices with limited IOVA space need more capabilities, like allocating
IOVA chunks or perform reverse translations (qemu addresses to iova).
Starting a sepparated implementation. Knowing than insertions/deletions
will not be as frequent as searches, it uses an ordered array at
implementation. A different name could be used, but ordered
searchable array is a little bit long though.
Signed-off-by: Eugenio Pérez <eperezma@redhat.com>
---
hw/virtio/vhost-iova-tree.h | 50 ++++++++++
hw/virtio/vhost-iova-tree.c | 188 ++++++++++++++++++++++++++++++++++++
hw/virtio/meson.build | 2 +-
3 files changed, 239 insertions(+), 1 deletion(-)
create mode 100644 hw/virtio/vhost-iova-tree.h
create mode 100644 hw/virtio/vhost-iova-tree.c
diff --git a/hw/virtio/vhost-iova-tree.h b/hw/virtio/vhost-iova-tree.h
new file mode 100644
index 0000000000..2a44af8b3a
--- /dev/null
+++ b/hw/virtio/vhost-iova-tree.h
@@ -0,0 +1,50 @@
+/*
+ * vhost software live migration ring
+ *
+ * SPDX-FileCopyrightText: Red Hat, Inc. 2021
+ * SPDX-FileContributor: Author: Eugenio Pérez <eperezma@redhat.com>
+ *
+ * SPDX-License-Identifier: GPL-2.0-or-later
+ */
+
+#ifndef HW_VIRTIO_VHOST_IOVA_TREE_H
+#define HW_VIRTIO_VHOST_IOVA_TREE_H
+
+#include <gmodule.h>
+
+#include "exec/memory.h"
+
+typedef struct VhostDMAMap {
+ void *translated_addr;
+ hwaddr iova;
+ hwaddr size; /* Inclusive */
+ IOMMUAccessFlags perm;
+} VhostDMAMap;
+
+typedef enum VhostDMAMapNewRC {
+ VHOST_DMA_MAP_OVERLAP = -2,
+ VHOST_DMA_MAP_INVALID = -1,
+ VHOST_DMA_MAP_OK = 0,
+} VhostDMAMapNewRC;
+
+/**
+ * VhostIOVATree
+ *
+ * Store and search IOVA -> Translated mappings.
+ *
+ * Note that it cannot remove nodes.
+ */
+typedef struct VhostIOVATree {
+ /* Ordered array of reverse translations, IOVA address to qemu memory. */
+ GArray *iova_taddr_map;
+} VhostIOVATree;
+
+void vhost_iova_tree_new(VhostIOVATree *iova_rm);
+void vhost_iova_tree_destroy(VhostIOVATree *iova_rm);
+
+const VhostDMAMap *vhost_iova_tree_find_taddr(const VhostIOVATree *iova_rm,
+ const VhostDMAMap *map);
+VhostDMAMapNewRC vhost_iova_tree_insert(VhostIOVATree *iova_rm,
+ VhostDMAMap *map);
+
+#endif
diff --git a/hw/virtio/vhost-iova-tree.c b/hw/virtio/vhost-iova-tree.c
new file mode 100644
index 0000000000..dfd7e448b5
--- /dev/null
+++ b/hw/virtio/vhost-iova-tree.c
@@ -0,0 +1,188 @@
+/*
+ * vhost software live migration ring
+ *
+ * SPDX-FileCopyrightText: Red Hat, Inc. 2021
+ * SPDX-FileContributor: Author: Eugenio Pérez <eperezma@redhat.com>
+ *
+ * SPDX-License-Identifier: GPL-2.0-or-later
+ */
+
+#include "qemu/osdep.h"
+#include "vhost-iova-tree.h"
+
+#define G_ARRAY_NOT_ZERO_TERMINATED false
+#define G_ARRAY_NOT_CLEAR_ON_ALLOC false
+
+/**
+ * Inserts an element after an existing one in garray.
+ *
+ * @array The array
+ * @prev_elem The previous element of array of NULL if prepending
+ * @map The DMA map
+ *
+ * It provides the aditional advantage of being type safe over
+ * g_array_insert_val, which accepts a reference pointer instead of a value
+ * with no complains.
+ */
+static void vhost_iova_tree_insert_after(GArray *array,
+ const VhostDMAMap *prev_elem,
+ const VhostDMAMap *map)
+{
+ size_t pos;
+
+ if (!prev_elem) {
+ pos = 0;
+ } else {
+ pos = prev_elem - &g_array_index(array, typeof(*prev_elem), 0) + 1;
+ }
+
+ g_array_insert_val(array, pos, *map);
+}
+
+static gint vhost_iova_tree_cmp_iova(gconstpointer a, gconstpointer b)
+{
+ const VhostDMAMap *m1 = a, *m2 = b;
+
+ if (m1->iova > m2->iova + m2->size) {
+ return 1;
+ }
+
+ if (m1->iova + m1->size < m2->iova) {
+ return -1;
+ }
+
+ /* Overlapped */
+ return 0;
+}
+
+/**
+ * Find the previous node to a given iova
+ *
+ * @array The ascending ordered-by-translated-addr array of VhostDMAMap
+ * @map The map to insert
+ * @prev Returned location of the previous map
+ *
+ * Return VHOST_DMA_MAP_OK if everything went well, or VHOST_DMA_MAP_OVERLAP if
+ * it already exists. It is ok to use this function to check if a given range
+ * exists, but it will use a linear search.
+ *
+ * TODO: We can use bsearch to locate the entry if we save the state in the
+ * needle, knowing that the needle is always the first argument to
+ * compare_func.
+ */
+static VhostDMAMapNewRC vhost_iova_tree_find_prev(const GArray *array,
+ GCompareFunc compare_func,
+ const VhostDMAMap *map,
+ const VhostDMAMap **prev)
+{
+ size_t i;
+ int r;
+
+ *prev = NULL;
+ for (i = 0; i < array->len; ++i) {
+ r = compare_func(map, &g_array_index(array, typeof(*map), i));
+ if (r == 0) {
+ return VHOST_DMA_MAP_OVERLAP;
+ }
+ if (r < 0) {
+ return VHOST_DMA_MAP_OK;
+ }
+
+ *prev = &g_array_index(array, typeof(**prev), i);
+ }
+
+ return VHOST_DMA_MAP_OK;
+}
+
+/**
+ * Create a new IOVA tree
+ *
+ * @tree The IOVA tree
+ */
+void vhost_iova_tree_new(VhostIOVATree *tree)
+{
+ assert(tree);
+
+ tree->iova_taddr_map = g_array_new(G_ARRAY_NOT_ZERO_TERMINATED,
+ G_ARRAY_NOT_CLEAR_ON_ALLOC,
+ sizeof(VhostDMAMap));
+}
+
+/**
+ * Destroy an IOVA tree
+ *
+ * @tree The iova tree
+ */
+void vhost_iova_tree_destroy(VhostIOVATree *tree)
+{
+ g_array_unref(g_steal_pointer(&tree->iova_taddr_map));
+}
+
+/**
+ * Perform a search on a GArray.
+ *
+ * @array Glib array
+ * @map Map to look up
+ * @compare_func Compare function to use
+ *
+ * Return The found element or NULL if not found.
+ *
+ * This can be replaced with g_array_binary_search (Since glib 2.62) when that
+ * is common enough.
+ */
+static const VhostDMAMap *vhost_iova_tree_bsearch(const GArray *array,
+ const VhostDMAMap *map,
+ GCompareFunc compare_func)
+{
+ return bsearch(map, array->data, array->len, sizeof(*map), compare_func);
+}
+
+/**
+ * Find the translated address stored from a IOVA 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_taddr(const VhostIOVATree *tree,
+ const VhostDMAMap *map)
+{
+ return vhost_iova_tree_bsearch(tree->iova_taddr_map, map,
+ vhost_iova_tree_cmp_iova);
+}
+
+/**
+ * Insert a new map
+ *
+ * @tree The iova tree
+ * @map The iova map
+ *
+ * Returns:
+ * - VHOST_DMA_MAP_OK if the map fits in the container
+ * - VHOST_DMA_MAP_INVALID if the map does not make sense (like size overflow)
+ * - VHOST_DMA_MAP_OVERLAP if the tree already contains that map
+ * Can query the assignated iova in map.
+ */
+VhostDMAMapNewRC vhost_iova_tree_insert(VhostIOVATree *tree,
+ VhostDMAMap *map)
+{
+ const VhostDMAMap *prev;
+ int find_prev_rc;
+
+ if (map->translated_addr + map->size < map->translated_addr ||
+ map->iova + map->size < map->iova || map->perm == IOMMU_NONE) {
+ return VHOST_DMA_MAP_INVALID;
+ }
+
+ /* 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);
+ if (find_prev_rc == VHOST_DMA_MAP_OVERLAP) {
+ return VHOST_DMA_MAP_OVERLAP;
+ }
+
+ vhost_iova_tree_insert_after(tree->iova_taddr_map, prev, map);
+ return VHOST_DMA_MAP_OK;
+}
diff --git a/hw/virtio/meson.build b/hw/virtio/meson.build
index 8b5a0225fe..cb306b83c6 100644
--- a/hw/virtio/meson.build
+++ b/hw/virtio/meson.build
@@ -11,7 +11,7 @@ softmmu_ss.add(when: 'CONFIG_ALL', if_true: files('vhost-stub.c'))
virtio_ss = ss.source_set()
virtio_ss.add(files('virtio.c'))
-virtio_ss.add(when: 'CONFIG_VHOST', if_true: files('vhost.c', 'vhost-backend.c', 'vhost-shadow-virtqueue.c'))
+virtio_ss.add(when: 'CONFIG_VHOST', if_true: files('vhost.c', 'vhost-backend.c', 'vhost-shadow-virtqueue.c', 'vhost-iova-tree.c'))
virtio_ss.add(when: 'CONFIG_VHOST_USER', if_true: files('vhost-user.c'))
virtio_ss.add(when: 'CONFIG_VHOST_VDPA', if_true: files('vhost-vdpa.c'))
virtio_ss.add(when: 'CONFIG_VIRTIO_BALLOON', if_true: files('virtio-balloon.c'))
--
2.27.0
next prev parent reply other threads:[~2021-05-19 16:50 UTC|newest]
Thread overview: 67+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-05-19 16:28 [RFC v3 00/29] vDPA software assisted live migration Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 01/29] virtio: Add virtio_queue_is_host_notifier_enabled Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 02/29] vhost: Save masked_notifier state Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 03/29] vhost: Add VhostShadowVirtqueue Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 04/29] vhost: Add x-vhost-enable-shadow-vq qmp Eugenio Pérez
2021-05-21 7:05 ` Markus Armbruster
2021-05-24 7:13 ` Eugenio Perez Martin
2021-06-08 14:23 ` Markus Armbruster
2021-06-08 15:26 ` Eugenio Perez Martin
2021-06-09 11:46 ` Markus Armbruster
2021-06-09 14:06 ` Eugenio Perez Martin
2021-05-19 16:28 ` [RFC v3 05/29] virtio: Add VIRTIO_F_QUEUE_STATE Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 06/29] virtio-net: Honor VIRTIO_CONFIG_S_DEVICE_STOPPED Eugenio Pérez
2021-05-26 1:06 ` Jason Wang
2021-05-26 1:10 ` Jason Wang
2021-06-01 7:13 ` Eugenio Perez Martin
2021-06-03 3:12 ` Jason Wang
2021-05-19 16:28 ` [RFC v3 07/29] vhost: Route guest->host notification through shadow virtqueue Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 08/29] vhost: Route host->guest " Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 09/29] vhost: Avoid re-set masked notifier in shadow vq Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 10/29] virtio: Add vhost_shadow_vq_get_vring_addr Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 11/29] vhost: Add vhost_vring_pause operation Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 12/29] vhost: add vhost_kernel_vring_pause Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 13/29] vhost: Add vhost_get_iova_range operation Eugenio Pérez
2021-05-26 1:14 ` Jason Wang
2021-05-26 17:49 ` Eugenio Perez Martin
2021-05-27 4:51 ` Jason Wang
2021-06-01 7:17 ` Eugenio Perez Martin
2021-06-03 3:13 ` Jason Wang
2021-05-19 16:28 ` [RFC v3 14/29] vhost: add vhost_has_limited_iova_range Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 15/29] vhost: Add enable_custom_iommu to VhostOps Eugenio Pérez
2021-05-31 9:01 ` Jason Wang
2021-06-01 7:49 ` Eugenio Perez Martin
2021-05-19 16:28 ` [RFC v3 16/29] vhost-vdpa: Add vhost_vdpa_enable_custom_iommu Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 17/29] vhost: Shadow virtqueue buffers forwarding Eugenio Pérez
2021-06-02 9:50 ` Jason Wang
2021-06-02 17:18 ` Eugenio Perez Martin
2021-06-03 3:34 ` Jason Wang
2021-06-04 8:37 ` Eugenio Perez Martin
2021-05-19 16:28 ` [RFC v3 18/29] vhost: Use vhost_enable_custom_iommu to unmap everything if available Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 19/29] vhost: Check for device VRING_USED_F_NO_NOTIFY at shadow virtqueue kick Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 20/29] vhost: Use VRING_AVAIL_F_NO_INTERRUPT at device call on shadow virtqueue Eugenio Pérez
2021-05-19 16:28 ` Eugenio Pérez [this message]
2021-05-31 9:40 ` [RFC v3 21/29] vhost: Add VhostIOVATree Jason Wang
2021-06-01 8:15 ` Eugenio Perez Martin
2021-07-14 3:04 ` Jason Wang
2021-07-14 6:54 ` Eugenio Perez Martin
2021-07-14 9:14 ` Eugenio Perez Martin
2021-07-14 9:33 ` Jason Wang
2021-05-19 16:28 ` [RFC v3 22/29] vhost: Add iova_rev_maps_find_iova to IOVAReverseMaps Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 23/29] vhost: Use a tree to store memory mappings Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 24/29] vhost: Add iova_rev_maps_alloc Eugenio Pérez
2021-05-19 16:28 ` [RFC v3 25/29] vhost: Add custom IOTLB translations to SVQ Eugenio Pérez
2021-06-02 9:51 ` Jason Wang
2021-06-02 17:51 ` Eugenio Perez Martin
2021-06-03 3:39 ` Jason Wang
2021-06-04 9:07 ` Eugenio Perez Martin
2021-05-19 16:29 ` [RFC v3 26/29] vhost: Map in vdpa-dev Eugenio Pérez
2021-05-19 16:29 ` [RFC v3 27/29] vhost-vdpa: Implement vhost_vdpa_vring_pause operation Eugenio Pérez
2021-05-19 16:29 ` [RFC v3 28/29] vhost-vdpa: never map with vDPA listener Eugenio Pérez
2021-05-19 16:29 ` [RFC v3 29/29] vhost: Start vhost-vdpa SVQ directly Eugenio Pérez
2021-05-24 9:38 ` [RFC v3 00/29] vDPA software assisted live migration Michael S. Tsirkin
2021-05-24 10:37 ` Eugenio Perez Martin
2021-05-24 11:29 ` Michael S. Tsirkin
2021-07-19 14:13 ` Stefan Hajnoczi
2021-05-25 0:09 ` Jason Wang
2021-06-02 9:59 ` Jason Wang
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20210519162903.1172366-22-eperezma@redhat.com \
--to=eperezma@redhat.com \
--cc=armbru@redhat.com \
--cc=eli@mellanox.com \
--cc=hanand@xilinx.com \
--cc=jasowang@redhat.com \
--cc=ml@napatech.com \
--cc=mst@redhat.com \
--cc=parav@mellanox.com \
--cc=qemu-devel@nongnu.org \
--cc=quintela@redhat.com \
--cc=sgarzare@redhat.com \
--cc=stefanha@redhat.com \
--cc=virtualization@lists.linux-foundation.org \
--cc=xiao.w.wang@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).