util/iova-tree.c

   1 /*
   2  * IOVA tree implementation based on GTree.
   3  *
   4  * Copyright 2018 Red Hat, Inc.
   5  *
   6  * Authors:
   7  *  Peter Xu <peterx@redhat.com>
   8  *
   9  * This work is licensed under the terms of the GNU GPL, version 2 or later.
  10  */
  11
  12 #include "qemu/osdep.h"
  13 #include "qemu/iova-tree.h"
  14
  15 struct IOVATree {
  16     GTree *tree;
  17 };
  18
  19 static int iova_tree_compare(gconstpointer a, gconstpointer b, gpointer data)
  20 {
  21     const DMAMap *m1 = a, *m2 = b;
  22
  23     if (m1->iova > m2->iova + m2->size) {
  24         return 1;
  25     }
  26
  27     if (m1->iova + m1->size < m2->iova) {
  28         return -1;
  29     }
  30
  31     /* Overlapped */
  32     return 0;
  33 }
  34
  35 IOVATree *iova_tree_new(void)
  36 {
  37     IOVATree *iova_tree = g_new0(IOVATree, 1);
  38
  39     /* We don't have values actually, no need to free */
  40     iova_tree->tree = g_tree_new_full(iova_tree_compare, NULL, g_free, NULL);
  41
  42     return iova_tree;
  43 }
  44
  45 const DMAMap *iova_tree_find(const IOVATree *tree, const DMAMap *map)
  46 {
  47     return g_tree_lookup(tree->tree, map);
  48 }
  49
  50 const DMAMap *iova_tree_find_address(const IOVATree *tree, hwaddr iova)
  51 {
  52     const DMAMap map = { .iova = iova, .size = 0 };
  53
  54     return iova_tree_find(tree, &map);
  55 }
  56
  57 static inline void iova_tree_insert_internal(GTree *gtree, DMAMap *range)
  58 {
  59     /* Key and value are sharing the same range data */
  60     g_tree_insert(gtree, range, range);
  61 }
  62
  63 int iova_tree_insert(IOVATree *tree, const DMAMap *map)
  64 {
  65     DMAMap *new;
  66
  67     if (map->iova + map->size < map->iova || map->perm == IOMMU_NONE) {
  68         return IOVA_ERR_INVALID;
  69     }
  70
  71     /* We don't allow to insert range that overlaps with existings */
  72     if (iova_tree_find(tree, map)) {
  73         return IOVA_ERR_OVERLAP;
  74     }
  75
  76     new = g_new0(DMAMap, 1);
  77     memcpy(new, map, sizeof(*new));
  78     iova_tree_insert_internal(tree->tree, new);
  79
  80     return IOVA_OK;
  81 }
  82
  83 static gboolean iova_tree_traverse(gpointer key, gpointer value,
  84                                 gpointer data)
  85 {
  86     iova_tree_iterator iterator = data;
  87     DMAMap *map = key;
  88
  89     g_assert(key == value);
  90
  91     return iterator(map);
  92 }
  93
  94 void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator)
  95 {
  96     g_tree_foreach(tree->tree, iova_tree_traverse, iterator);
  97 }
  98
  99 int iova_tree_remove(IOVATree *tree, const DMAMap *map)
 100 {
 101     const DMAMap *overlap;
 102
 103     while ((overlap = iova_tree_find(tree, map))) {
 104         g_tree_remove(tree->tree, overlap);
 105     }
 106
 107     return IOVA_OK;
 108 }
 109
 110 void iova_tree_destroy(IOVATree *tree)
 111 {
 112     g_tree_destroy(tree->tree);
 113     g_free(tree);
 114 }