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 33 typedef struct IOVATree IOVATree; 34 typedef struct DMAMap { 35 hwaddr iova; 36 hwaddr translated_addr; 37 hwaddr size; /* Inclusive */ 38 IOMMUAccessFlags perm; 39 } QEMU_PACKED DMAMap; 40 typedef gboolean (*iova_tree_iterator)(DMAMap *map); 41 42 /** 43 * iova_tree_new: 44 * 45 * Create a new iova tree. 46 * 47 * Returns: the tree pointer when succeeded, or NULL if error. 48 */ 49 IOVATree *iova_tree_new(void); 50 51 /** 52 * iova_tree_insert: 53 * 54 * @tree: the iova tree to insert 55 * @map: the mapping to insert 56 * 57 * Insert an iova range to the tree. If there is overlapped 58 * ranges, IOVA_ERR_OVERLAP will be returned. 59 * 60 * Return: 0 if succeeded, or <0 if error. 61 */ 62 int iova_tree_insert(IOVATree *tree, DMAMap *map); 63 64 /** 65 * iova_tree_remove: 66 * 67 * @tree: the iova tree to remove range from 68 * @map: the map range to remove 69 * 70 * Remove mappings from the tree that are covered by the map range 71 * provided. The range does not need to be exactly what has inserted, 72 * all the mappings that are included in the provided range will be 73 * removed from the tree. Here map->translated_addr is meaningless. 74 * 75 * Return: 0 if succeeded, or <0 if error. 76 */ 77 int iova_tree_remove(IOVATree *tree, DMAMap *map); 78 79 /** 80 * iova_tree_find: 81 * 82 * @tree: the iova tree to search from 83 * @map: the mapping to search 84 * 85 * Search for a mapping in the iova tree that overlaps with the 86 * mapping range specified. Only the first found mapping will be 87 * returned. 88 * 89 * Return: DMAMap pointer if found, or NULL if not found. Note that 90 * the returned DMAMap pointer is maintained internally. User should 91 * only read the content but never modify or free the content. Also, 92 * user is responsible to make sure the pointer is valid (say, no 93 * concurrent deletion in progress). 94 */ 95 DMAMap *iova_tree_find(IOVATree *tree, DMAMap *map); 96 97 /** 98 * iova_tree_find_address: 99 * 100 * @tree: the iova tree to search from 101 * @iova: the iova address to find 102 * 103 * Similar to iova_tree_find(), but it tries to find mapping with 104 * range iova=iova & size=0. 105 * 106 * Return: same as iova_tree_find(). 107 */ 108 DMAMap *iova_tree_find_address(IOVATree *tree, hwaddr iova); 109 110 /** 111 * iova_tree_foreach: 112 * 113 * @tree: the iova tree to iterate on 114 * @iterator: the interator for the mappings, return true to stop 115 * 116 * Iterate over the iova tree. 117 * 118 * Return: 1 if found any overlap, 0 if not, <0 if error. 119 */ 120 void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator); 121 122 /** 123 * iova_tree_destroy: 124 * 125 * @tree: the iova tree to destroy 126 * 127 * Destroy an existing iova tree. 128 * 129 * Return: None. 130 */ 131 void iova_tree_destroy(IOVATree *tree); 132 133 #endif 134