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