cachepc-qemu

Fork of AMDESE/qemu with changes for cachepc side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-qemu
Log | Files | Refs | Submodules | LICENSE | sfeed.txt

iova-tree.c (2393B)

      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}