[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 20/31] util: Store DMA entries in a list
From: |
Eugenio Pérez |
Subject: |
[PATCH 20/31] util: Store DMA entries in a list |
Date: |
Fri, 21 Jan 2022 21:27:22 +0100 |
SVQ need to allocate iova entries, traversing the list looking for
holes.
GLib offers methods to both transverse the list and look for entries
upper than a key since version 2.68. However qemu may need to compile
with earlier versions, so we replicate both methods here.
Signed-off-by: Eugenio Pérez <eperezma@redhat.com>
---
util/iova-tree.c | 42 +++++++++++++++++++++++++++++++++++++++++-
1 file changed, 41 insertions(+), 1 deletion(-)
diff --git a/util/iova-tree.c b/util/iova-tree.c
index ac089101c4..5063a256dd 100644
--- a/util/iova-tree.c
+++ b/util/iova-tree.c
@@ -11,15 +11,44 @@
#include "qemu/osdep.h"
#include "qemu/iova-tree.h"
+#include "qemu/queue.h"
typedef struct DMAMapInternal {
DMAMap map;
+ QTAILQ_ENTRY(DMAMapInternal) entry;
} DMAMapInternal;
struct IOVATree {
GTree *tree;
+ QTAILQ_HEAD(, DMAMapInternal) list;
};
+/**
+ * Search function for the upper bound of a given needle.
+ *
+ * The upper bound is the first node that has its key strictly greater than the
+ * searched key.
+ *
+ * TODO: A specialized function is available in GTree since Glib 2.68. Replace
+ * when Glib minimal version is raised.
+ */
+static int iova_tree_compare_upper_bound(gconstpointer a, gconstpointer b)
+{
+ const DMAMapInternal *haystack = a, *needle = b, *prev;
+
+ if (needle->map.iova >= haystack->map.iova) {
+ return 1;
+ }
+
+ prev = QTAILQ_PREV(haystack, entry);
+ if (!prev || prev->map.iova < needle->map.iova) {
+ return 0;
+ }
+
+ /* More data to the left or end of data */
+ return -1;
+}
+
static int iova_tree_compare(gconstpointer a, gconstpointer b, gpointer data)
{
const DMAMapInternal *i1 = a, *i2 = b;
@@ -43,6 +72,7 @@ IOVATree *iova_tree_new(void)
/* We don't have values actually, no need to free */
iova_tree->tree = g_tree_new_full(iova_tree_compare, NULL, g_free, NULL);
+ QTAILQ_INIT(&iova_tree->list);
return iova_tree;
}
@@ -77,7 +107,7 @@ static inline void iova_tree_insert_internal(GTree *gtree,
int iova_tree_insert(IOVATree *tree, const DMAMap *map)
{
- DMAMapInternal *new;
+ DMAMapInternal *new, *right;
if (map->iova + map->size < map->iova || map->perm == IOMMU_NONE) {
return IOVA_ERR_INVALID;
@@ -92,6 +122,15 @@ int iova_tree_insert(IOVATree *tree, const DMAMap *map)
memcpy(&new->map, map, sizeof(new->map));
iova_tree_insert_internal(tree->tree, new);
+ /* Ordered insertion */
+ right = g_tree_search(tree->tree, iova_tree_compare_upper_bound, new);
+ if (!right) {
+ /* Empty or bigger than any other entry */
+ QTAILQ_INSERT_TAIL(&tree->list, new, entry);
+ } else {
+ QTAILQ_INSERT_BEFORE(right, new, entry);
+ }
+
return IOVA_OK;
}
@@ -116,6 +155,7 @@ int iova_tree_remove(IOVATree *tree, const DMAMap *map)
DMAMapInternal *overlap_internal;
while ((overlap_internal = iova_tree_find_internal(tree, map))) {
+ QTAILQ_REMOVE(&tree->list, overlap_internal, entry);
g_tree_remove(tree->tree, overlap_internal);
}
--
2.27.0
- Re: [PATCH 21/31] util: Add iova_tree_alloc, (continued)
- Re: [PATCH 21/31] util: Add iova_tree_alloc, Peter Xu, 2022/01/23
- Re: [PATCH 21/31] util: Add iova_tree_alloc, Eugenio Perez Martin, 2022/01/24
- Re: [PATCH 21/31] util: Add iova_tree_alloc, Peter Xu, 2022/01/24
- Re: [PATCH 21/31] util: Add iova_tree_alloc, Eugenio Perez Martin, 2022/01/25
- Re: [PATCH 21/31] util: Add iova_tree_alloc, Peter Xu, 2022/01/27
- Re: [PATCH 21/31] util: Add iova_tree_alloc, Eugenio Perez Martin, 2022/01/27
- Re: [PATCH 21/31] util: Add iova_tree_alloc, Peter Xu, 2022/01/27
- Re: [PATCH 21/31] util: Add iova_tree_alloc, Jason Wang, 2022/01/28
- Re: [PATCH 21/31] util: Add iova_tree_alloc, Eugenio Perez Martin, 2022/01/28
- Re: [PATCH 21/31] util: Add iova_tree_alloc, Jason Wang, 2022/01/30
[PATCH 20/31] util: Store DMA entries in a list,
Eugenio Pérez <=
[PATCH 22/31] vhost: Add VhostIOVATree, Eugenio Pérez, 2022/01/21
[PATCH 24/31] vhost: Add vhost_svq_get_last_used_idx, Eugenio Pérez, 2022/01/21
[PATCH 23/31] vdpa: Add custom IOTLB translations to SVQ, Eugenio Pérez, 2022/01/21
[PATCH 25/31] vdpa: Adapt vhost_vdpa_get_vring_base to SVQ, Eugenio Pérez, 2022/01/21
[PATCH 26/31] vdpa: Clear VHOST_VRING_F_LOG at vhost_vdpa_set_vring_addr in SVQ, Eugenio Pérez, 2022/01/21
[PATCH 27/31] vdpa: Never set log_base addr if SVQ is enabled, Eugenio Pérez, 2022/01/21
[PATCH 28/31] vdpa: Expose VHOST_F_LOG_ALL on SVQ, Eugenio Pérez, 2022/01/21