| 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 "system/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 |