LXR qemu/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
  15struct IOVATree {
  16    GTree *tree;
  17};
  18
  19static 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
  35IOVATree *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
  45DMAMap *iova_tree_find(IOVATree *tree, DMAMap *map)
  46{
  47    return g_tree_lookup(tree->tree, map);
  48}
  49
  50DMAMap *iova_tree_find_address(IOVATree *tree, hwaddr iova)
  51{
  52    DMAMap map = { .iova = iova, .size = 0 };
  53
  54    return iova_tree_find(tree, &map);
  55}
  56
  57static 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
  63int iova_tree_insert(IOVATree *tree, 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
  83static 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
  94void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator)
  95{
  96    g_tree_foreach(tree->tree, iova_tree_traverse, iterator);
  97}
  98
  99int iova_tree_remove(IOVATree *tree, DMAMap *map)
 100{
 101    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
 110void iova_tree_destroy(IOVATree *tree)
 111{
 112    g_tree_destroy(tree->tree);
 113    g_free(tree);
 114}
 115