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 } 115