1 /* 2 * An very simplified 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 #ifndef IOVA_TREE_H 12 #define IOVA_TREE_H 13 14 /* 15 * Currently the iova tree will only allow to keep ranges 16 * information, and no extra user data is allowed for each element. A 17 * benefit is that we can merge adjacent ranges internally within the 18 * tree. It can save a lot of memory when the ranges are splitted but 19 * mostly continuous. 20 * 21 * Note that current implementation does not provide any thread 22 * protections. Callers of the iova tree should be responsible 23 * for the thread safety issue. 24 */ 25 26 #include "qemu/osdep.h" 27 #include "exec/memory.h" 28 #include "exec/hwaddr.h" 29 30 #define IOVA_OK (0) 31 #define IOVA_ERR_INVALID (-1) /* Invalid parameters */ 32 #define IOVA_ERR_OVERLAP (-2) /* IOVA range overlapped */ 33 34 typedef struct IOVATree IOVATree; 35 typedef struct DMAMap { 36 hwaddr iova; 37 hwaddr translated_addr; 38 hwaddr size; /* Inclusive */ 39 IOMMUAccessFlags perm; 40 } QEMU_PACKED DMAMap; 41 typedef gboolean (*iova_tree_iterator)(DMAMap *map); 42 43 /** 44 * iova_tree_new: 45 * 46 * Create a new iova tree. 47 * 48 * Returns: the tree pointer when succeeded, or NULL if error. 49 */ 50 IOVATree *iova_tree_new(void); 51 52 /** 53 * iova_tree_insert: 54 * 55 * @tree: the iova tree to insert 56 * @map: the mapping to insert 57 * 58 * Insert an iova range to the tree. If there is overlapped 59 * ranges, IOVA_ERR_OVERLAP will be returned. 60 * 61 * Return: 0 if succeeded, or <0 if error. 62 */ 63 int iova_tree_insert(IOVATree *tree, DMAMap *map); 64 65 /** 66 * iova_tree_remove: 67 * 68 * @tree: the iova tree to remove range from 69 * @map: the map range to remove 70 * 71 * Remove mappings from the tree that are covered by the map range 72 * provided. The range does not need to be exactly what has inserted, 73 * all the mappings that are included in the provided range will be 74 * removed from the tree. Here map->translated_addr is meaningless. 75 * 76 * Return: 0 if succeeded, or <0 if error. 77 */ 78 int iova_tree_remove(IOVATree *tree, DMAMap *map); 79 80 /** 81 * iova_tree_find: 82 * 83 * @tree: the iova tree to search from 84 * @map: the mapping to search 85 * 86 * Search for a mapping in the iova tree that overlaps with the 87 * mapping range specified. Only the first found mapping will be 88 * returned. 89 * 90 * Return: DMAMap pointer if found, or NULL if not found. Note that 91 * the returned DMAMap pointer is maintained internally. User should 92 * only read the content but never modify or free the content. Also, 93 * user is responsible to make sure the pointer is valid (say, no 94 * concurrent deletion in progress). 95 */ 96 DMAMap *iova_tree_find(IOVATree *tree, DMAMap *map); 97 98 /** 99 * iova_tree_find_address: 100 * 101 * @tree: the iova tree to search from 102 * @iova: the iova address to find 103 * 104 * Similar to iova_tree_find(), but it tries to find mapping with 105 * range iova=iova & size=0. 106 * 107 * Return: same as iova_tree_find(). 108 */ 109 DMAMap *iova_tree_find_address(IOVATree *tree, hwaddr iova); 110 111 /** 112 * iova_tree_foreach: 113 * 114 * @tree: the iova tree to iterate on 115 * @iterator: the interator for the mappings, return true to stop 116 * 117 * Iterate over the iova tree. 118 * 119 * Return: 1 if found any overlap, 0 if not, <0 if error. 120 */ 121 void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator); 122 123 /** 124 * iova_tree_destroy: 125 * 126 * @tree: the iova tree to destroy 127 * 128 * Destroy an existing iova tree. 129 * 130 * Return: None. 131 */ 132 void iova_tree_destroy(IOVATree *tree); 133 134 #endif 135