| /* |
| * IOVA tree implementation based on GTree. |
| * |
| * Copyright 2018 Red Hat, Inc. |
| * |
| * Authors: |
| * Peter Xu <peterx@redhat.com> |
| * |
| * This work is licensed under the terms of the GNU GPL, version 2 or later. |
| */ |
| |
| #include <glib.h> |
| #include "qemu/iova-tree.h" |
| |
| struct IOVATree { |
| GTree *tree; |
| }; |
| |
| static int iova_tree_compare(gconstpointer a, gconstpointer b, gpointer data) |
| { |
| const DMAMap *m1 = a, *m2 = b; |
| |
| if (m1->iova > m2->iova + m2->size) { |
| return 1; |
| } |
| |
| if (m1->iova + m1->size < m2->iova) { |
| return -1; |
| } |
| |
| /* Overlapped */ |
| return 0; |
| } |
| |
| IOVATree *iova_tree_new(void) |
| { |
| IOVATree *iova_tree = g_new0(IOVATree, 1); |
| |
| /* We don't have values actually, no need to free */ |
| iova_tree->tree = g_tree_new_full(iova_tree_compare, NULL, g_free, NULL); |
| |
| return iova_tree; |
| } |
| |
| DMAMap *iova_tree_find(IOVATree *tree, DMAMap *map) |
| { |
| return g_tree_lookup(tree->tree, map); |
| } |
| |
| DMAMap *iova_tree_find_address(IOVATree *tree, hwaddr iova) |
| { |
| DMAMap map = { .iova = iova, .size = 0 }; |
| |
| return iova_tree_find(tree, &map); |
| } |
| |
| static inline void iova_tree_insert_internal(GTree *gtree, DMAMap *range) |
| { |
| /* Key and value are sharing the same range data */ |
| g_tree_insert(gtree, range, range); |
| } |
| |
| int iova_tree_insert(IOVATree *tree, DMAMap *map) |
| { |
| DMAMap *new; |
| |
| if (map->iova + map->size < map->iova || map->perm == IOMMU_NONE) { |
| return IOVA_ERR_INVALID; |
| } |
| |
| /* We don't allow to insert range that overlaps with existings */ |
| if (iova_tree_find(tree, map)) { |
| return IOVA_ERR_OVERLAP; |
| } |
| |
| new = g_new0(DMAMap, 1); |
| memcpy(new, map, sizeof(*new)); |
| iova_tree_insert_internal(tree->tree, new); |
| |
| return IOVA_OK; |
| } |
| |
| static gboolean iova_tree_traverse(gpointer key, gpointer value, |
| gpointer data) |
| { |
| iova_tree_iterator iterator = data; |
| DMAMap *map = key; |
| |
| g_assert(key == value); |
| |
| return iterator(map); |
| } |
| |
| void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator) |
| { |
| g_tree_foreach(tree->tree, iova_tree_traverse, iterator); |
| } |
| |
| int iova_tree_remove(IOVATree *tree, DMAMap *map) |
| { |
| DMAMap *overlap; |
| |
| while ((overlap = iova_tree_find(tree, map))) { |
| g_tree_remove(tree->tree, overlap); |
| } |
| |
| return IOVA_OK; |
| } |
| |
| void iova_tree_destroy(IOVATree *tree) |
| { |
| g_tree_destroy(tree->tree); |
| g_free(tree); |
| } |