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 "exec/memory.h" 27 #include "exec/hwaddr.h" 28 29 #define IOVA_OK (0) 30 #define IOVA_ERR_INVALID (-1) /* Invalid parameters */ 31 #define IOVA_ERR_OVERLAP (-2) /* IOVA range overlapped */ 32 #define IOVA_ERR_NOMEM (-3) /* Cannot allocate */ 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, const 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 void iova_tree_remove(IOVATree *tree, DMAMap map); 77 78 /** 79 * iova_tree_find: 80 * 81 * @tree: the iova tree to search from 82 * @map: the mapping to search 83 * 84 * Search for a mapping in the iova tree that iova overlaps with the 85 * mapping range specified. Only the first found mapping will be 86 * returned. 87 * 88 * Return: DMAMap pointer if found, or NULL if not found. Note that 89 * the returned DMAMap pointer is maintained internally. User should 90 * only read the content but never modify or free the content. Also, 91 * user is responsible to make sure the pointer is valid (say, no 92 * concurrent deletion in progress). 93 */ 94 const DMAMap *iova_tree_find(const IOVATree *tree, const DMAMap *map); 95 96 /** 97 * iova_tree_find_iova: 98 * 99 * @tree: the iova tree to search from 100 * @map: the mapping to search 101 * 102 * Search for a mapping in the iova tree that translated_addr overlaps with the 103 * mapping range specified. Only the first found mapping will be 104 * returned. 105 * 106 * Return: DMAMap pointer if found, or NULL if not found. Note that 107 * the returned DMAMap pointer is maintained internally. User should 108 * only read the content but never modify or free the content. Also, 109 * user is responsible to make sure the pointer is valid (say, no 110 * concurrent deletion in progress). 111 */ 112 const DMAMap *iova_tree_find_iova(const IOVATree *tree, const DMAMap *map); 113 114 /** 115 * iova_tree_find_address: 116 * 117 * @tree: the iova tree to search from 118 * @iova: the iova address to find 119 * 120 * Similar to iova_tree_find(), but it tries to find mapping with 121 * range iova=iova & size=0. 122 * 123 * Return: same as iova_tree_find(). 124 */ 125 const DMAMap *iova_tree_find_address(const IOVATree *tree, hwaddr iova); 126 127 /** 128 * iova_tree_foreach: 129 * 130 * @tree: the iova tree to iterate on 131 * @iterator: the interator for the mappings, return true to stop 132 * 133 * Iterate over the iova tree. 134 * 135 * Return: 1 if found any overlap, 0 if not, <0 if error. 136 */ 137 void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator); 138 139 /** 140 * iova_tree_alloc_map: 141 * 142 * @tree: the iova tree to allocate from 143 * @map: the new map (as translated addr & size) to allocate in the iova region 144 * @iova_begin: the minimum address of the allocation 145 * @iova_end: the maximum addressable direction of the allocation 146 * 147 * Allocates a new region of a given size, between iova_min and iova_max. 148 * 149 * Return: Same as iova_tree_insert, but cannot overlap and can return error if 150 * iova tree is out of free contiguous range. The caller gets the assigned iova 151 * in map->iova. 152 */ 153 int iova_tree_alloc_map(IOVATree *tree, DMAMap *map, hwaddr iova_begin, 154 hwaddr iova_end); 155 156 /** 157 * iova_tree_destroy: 158 * 159 * @tree: the iova tree to destroy 160 * 161 * Destroy an existing iova tree. 162 * 163 * Return: None. 164 */ 165 void iova_tree_destroy(IOVATree *tree); 166 167 #endif 168