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 split 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 * gpa_tree_new: 45 * 46 * Create a new GPA->IOVA tree. 47 * 48 * Returns: the tree point on success, or NULL otherwise. 49 */ 50 IOVATree *gpa_tree_new(void); 51 52 /** 53 * gpa_tree_insert: 54 * 55 * @tree: The GPA->IOVA tree we're inserting the mapping to 56 * @map: The GPA->IOVA mapping to insert 57 * 58 * Inserts a GPA range to the GPA->IOVA tree. If there are overlapped 59 * ranges, IOVA_ERR_OVERLAP will be returned. 60 * 61 * Return: 0 if successful, < 0 otherwise. 62 */ 63 int gpa_tree_insert(IOVATree *tree, const DMAMap *map); 64 65 /** 66 * iova_tree_new: 67 * 68 * Create a new iova tree. 69 * 70 * Returns: the tree pointer when succeeded, or NULL if error. 71 */ 72 IOVATree *iova_tree_new(void); 73 74 /** 75 * iova_tree_insert: 76 * 77 * @tree: the iova tree to insert 78 * @map: the mapping to insert 79 * 80 * Insert an iova range to the tree. If there is overlapped 81 * ranges, IOVA_ERR_OVERLAP will be returned. 82 * 83 * Return: 0 if succeeded, or <0 if error. 84 */ 85 int iova_tree_insert(IOVATree *tree, const DMAMap *map); 86 87 /** 88 * iova_tree_remove: 89 * 90 * @tree: the iova tree to remove range from 91 * @map: the map range to remove 92 * 93 * Remove mappings from the tree that are covered by the map range 94 * provided. The range does not need to be exactly what has inserted, 95 * all the mappings that are included in the provided range will be 96 * removed from the tree. Here map->translated_addr is meaningless. 97 */ 98 void iova_tree_remove(IOVATree *tree, DMAMap map); 99 100 /** 101 * iova_tree_find: 102 * 103 * @tree: the iova tree to search from 104 * @map: the mapping to search 105 * 106 * Search for a mapping in the iova tree that iova overlaps with the 107 * mapping range specified. Only the first found mapping will be 108 * returned. 109 * 110 * Return: DMAMap pointer if found, or NULL if not found. Note that 111 * the returned DMAMap pointer is maintained internally. User should 112 * only read the content but never modify or free the content. Also, 113 * user is responsible to make sure the pointer is valid (say, no 114 * concurrent deletion in progress). 115 */ 116 const DMAMap *iova_tree_find(const IOVATree *tree, const DMAMap *map); 117 118 /** 119 * iova_tree_find_iova: 120 * 121 * @tree: the iova tree to search from 122 * @map: the mapping to search 123 * 124 * Search for a mapping in the iova tree that translated_addr overlaps with the 125 * mapping range specified. Only the first found mapping will be 126 * returned. 127 * 128 * Return: DMAMap pointer if found, or NULL if not found. Note that 129 * the returned DMAMap pointer is maintained internally. User should 130 * only read the content but never modify or free the content. Also, 131 * user is responsible to make sure the pointer is valid (say, no 132 * concurrent deletion in progress). 133 */ 134 const DMAMap *iova_tree_find_iova(const IOVATree *tree, const DMAMap *map); 135 136 /** 137 * iova_tree_alloc_map: 138 * 139 * @tree: the iova tree to allocate from 140 * @map: the new map (as translated addr & size) to allocate in the iova region 141 * @iova_begin: the minimum address of the allocation 142 * @iova_end: the maximum addressable direction of the allocation 143 * 144 * Allocates a new region of a given size, between iova_min and iova_max. 145 * 146 * Return: Same as iova_tree_insert, but cannot overlap and can return error if 147 * iova tree is out of free contiguous range. The caller gets the assigned iova 148 * in map->iova. 149 */ 150 int iova_tree_alloc_map(IOVATree *tree, DMAMap *map, hwaddr iova_begin, 151 hwaddr iova_end); 152 153 /** 154 * iova_tree_destroy: 155 * 156 * @tree: the iova tree to destroy 157 * 158 * Destroy an existing iova tree. 159 * 160 * Return: None. 161 */ 162 void iova_tree_destroy(IOVATree *tree); 163 164 #endif 165