Peter Xu | eecf5ee | 2018-05-18 15:25:16 +0800 | [diff] [blame] | 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 | |
Daniel P. Berrangé | c5f1d0c | 2018-06-06 18:15:38 +0100 | [diff] [blame] | 12 | #include "qemu/osdep.h" |
Peter Xu | eecf5ee | 2018-05-18 15:25:16 +0800 | [diff] [blame] | 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 | DMAMap *iova_tree_find(IOVATree *tree, DMAMap *map) |
| 46 | { |
| 47 | return g_tree_lookup(tree->tree, map); |
| 48 | } |
| 49 | |
| 50 | DMAMap *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 | |
| 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, 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, 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 | |
| 110 | void iova_tree_destroy(IOVATree *tree) |
| 111 | { |
| 112 | g_tree_destroy(tree->tree); |
| 113 | g_free(tree); |
| 114 | } |