[PATCH 20/31] util: Store DMA entries in a list

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

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