1eecf5eedSPeter Xu /* 2eecf5eedSPeter Xu * An very simplified iova tree implementation based on GTree. 3eecf5eedSPeter Xu * 4eecf5eedSPeter Xu * Copyright 2018 Red Hat, Inc. 5eecf5eedSPeter Xu * 6eecf5eedSPeter Xu * Authors: 7eecf5eedSPeter Xu * Peter Xu <peterx@redhat.com> 8eecf5eedSPeter Xu * 9eecf5eedSPeter Xu * This work is licensed under the terms of the GNU GPL, version 2 or later. 10eecf5eedSPeter Xu */ 11eecf5eedSPeter Xu #ifndef IOVA_TREE_H 12eecf5eedSPeter Xu #define IOVA_TREE_H 13eecf5eedSPeter Xu 14eecf5eedSPeter Xu /* 15eecf5eedSPeter Xu * Currently the iova tree will only allow to keep ranges 16eecf5eedSPeter Xu * information, and no extra user data is allowed for each element. A 17eecf5eedSPeter Xu * benefit is that we can merge adjacent ranges internally within the 18*d02d06f8SMichael Tokarev * tree. It can save a lot of memory when the ranges are split but 19eecf5eedSPeter Xu * mostly continuous. 20eecf5eedSPeter Xu * 21eecf5eedSPeter Xu * Note that current implementation does not provide any thread 22eecf5eedSPeter Xu * protections. Callers of the iova tree should be responsible 23eecf5eedSPeter Xu * for the thread safety issue. 24eecf5eedSPeter Xu */ 25eecf5eedSPeter Xu 26eecf5eedSPeter Xu #include "exec/memory.h" 27eecf5eedSPeter Xu #include "exec/hwaddr.h" 28eecf5eedSPeter Xu 29eecf5eedSPeter Xu #define IOVA_OK (0) 30eecf5eedSPeter Xu #define IOVA_ERR_INVALID (-1) /* Invalid parameters */ 31eecf5eedSPeter Xu #define IOVA_ERR_OVERLAP (-2) /* IOVA range overlapped */ 329376bde8SEugenio Pérez #define IOVA_ERR_NOMEM (-3) /* Cannot allocate */ 33eecf5eedSPeter Xu 34eecf5eedSPeter Xu typedef struct IOVATree IOVATree; 35eecf5eedSPeter Xu typedef struct DMAMap { 36eecf5eedSPeter Xu hwaddr iova; 37eecf5eedSPeter Xu hwaddr translated_addr; 38eecf5eedSPeter Xu hwaddr size; /* Inclusive */ 39eecf5eedSPeter Xu IOMMUAccessFlags perm; 40eecf5eedSPeter Xu } QEMU_PACKED DMAMap; 41eecf5eedSPeter Xu typedef gboolean (*iova_tree_iterator)(DMAMap *map); 42eecf5eedSPeter Xu 43eecf5eedSPeter Xu /** 44eecf5eedSPeter Xu * iova_tree_new: 45eecf5eedSPeter Xu * 46eecf5eedSPeter Xu * Create a new iova tree. 47eecf5eedSPeter Xu * 48eecf5eedSPeter Xu * Returns: the tree pointer when succeeded, or NULL if error. 49eecf5eedSPeter Xu */ 50eecf5eedSPeter Xu IOVATree *iova_tree_new(void); 51eecf5eedSPeter Xu 52eecf5eedSPeter Xu /** 53eecf5eedSPeter Xu * iova_tree_insert: 54eecf5eedSPeter Xu * 55eecf5eedSPeter Xu * @tree: the iova tree to insert 56eecf5eedSPeter Xu * @map: the mapping to insert 57eecf5eedSPeter Xu * 58eecf5eedSPeter Xu * Insert an iova range to the tree. If there is overlapped 59eecf5eedSPeter Xu * ranges, IOVA_ERR_OVERLAP will be returned. 60eecf5eedSPeter Xu * 61eecf5eedSPeter Xu * Return: 0 if succeeded, or <0 if error. 62eecf5eedSPeter Xu */ 63a89b34beSEugenio Pérez int iova_tree_insert(IOVATree *tree, const DMAMap *map); 64eecf5eedSPeter Xu 65eecf5eedSPeter Xu /** 66eecf5eedSPeter Xu * iova_tree_remove: 67eecf5eedSPeter Xu * 68eecf5eedSPeter Xu * @tree: the iova tree to remove range from 69eecf5eedSPeter Xu * @map: the map range to remove 70eecf5eedSPeter Xu * 71eecf5eedSPeter Xu * Remove mappings from the tree that are covered by the map range 72eecf5eedSPeter Xu * provided. The range does not need to be exactly what has inserted, 73eecf5eedSPeter Xu * all the mappings that are included in the provided range will be 74eecf5eedSPeter Xu * removed from the tree. Here map->translated_addr is meaningless. 75eecf5eedSPeter Xu */ 7669292a8eSEugenio Pérez void iova_tree_remove(IOVATree *tree, DMAMap map); 77eecf5eedSPeter Xu 78eecf5eedSPeter Xu /** 79eecf5eedSPeter Xu * iova_tree_find: 80eecf5eedSPeter Xu * 81eecf5eedSPeter Xu * @tree: the iova tree to search from 82eecf5eedSPeter Xu * @map: the mapping to search 83eecf5eedSPeter Xu * 84193d17beSEugenio Pérez * Search for a mapping in the iova tree that iova overlaps with the 85eecf5eedSPeter Xu * mapping range specified. Only the first found mapping will be 86eecf5eedSPeter Xu * returned. 87eecf5eedSPeter Xu * 88eecf5eedSPeter Xu * Return: DMAMap pointer if found, or NULL if not found. Note that 89eecf5eedSPeter Xu * the returned DMAMap pointer is maintained internally. User should 90eecf5eedSPeter Xu * only read the content but never modify or free the content. Also, 91eecf5eedSPeter Xu * user is responsible to make sure the pointer is valid (say, no 92eecf5eedSPeter Xu * concurrent deletion in progress). 93eecf5eedSPeter Xu */ 94a89b34beSEugenio Pérez const DMAMap *iova_tree_find(const IOVATree *tree, const DMAMap *map); 95eecf5eedSPeter Xu 96eecf5eedSPeter Xu /** 97193d17beSEugenio Pérez * iova_tree_find_iova: 98193d17beSEugenio Pérez * 99193d17beSEugenio Pérez * @tree: the iova tree to search from 100193d17beSEugenio Pérez * @map: the mapping to search 101193d17beSEugenio Pérez * 102193d17beSEugenio Pérez * Search for a mapping in the iova tree that translated_addr overlaps with the 103193d17beSEugenio Pérez * mapping range specified. Only the first found mapping will be 104193d17beSEugenio Pérez * returned. 105193d17beSEugenio Pérez * 106193d17beSEugenio Pérez * Return: DMAMap pointer if found, or NULL if not found. Note that 107193d17beSEugenio Pérez * the returned DMAMap pointer is maintained internally. User should 108193d17beSEugenio Pérez * only read the content but never modify or free the content. Also, 109193d17beSEugenio Pérez * user is responsible to make sure the pointer is valid (say, no 110193d17beSEugenio Pérez * concurrent deletion in progress). 111193d17beSEugenio Pérez */ 112193d17beSEugenio Pérez const DMAMap *iova_tree_find_iova(const IOVATree *tree, const DMAMap *map); 113193d17beSEugenio Pérez 114193d17beSEugenio Pérez /** 115eecf5eedSPeter Xu * iova_tree_find_address: 116eecf5eedSPeter Xu * 117eecf5eedSPeter Xu * @tree: the iova tree to search from 118eecf5eedSPeter Xu * @iova: the iova address to find 119eecf5eedSPeter Xu * 120eecf5eedSPeter Xu * Similar to iova_tree_find(), but it tries to find mapping with 121eecf5eedSPeter Xu * range iova=iova & size=0. 122eecf5eedSPeter Xu * 123eecf5eedSPeter Xu * Return: same as iova_tree_find(). 124eecf5eedSPeter Xu */ 125a89b34beSEugenio Pérez const DMAMap *iova_tree_find_address(const IOVATree *tree, hwaddr iova); 126eecf5eedSPeter Xu 127eecf5eedSPeter Xu /** 128eecf5eedSPeter Xu * iova_tree_foreach: 129eecf5eedSPeter Xu * 130eecf5eedSPeter Xu * @tree: the iova tree to iterate on 131*d02d06f8SMichael Tokarev * @iterator: the iterator for the mappings, return true to stop 132eecf5eedSPeter Xu * 133eecf5eedSPeter Xu * Iterate over the iova tree. 134eecf5eedSPeter Xu * 135eecf5eedSPeter Xu * Return: 1 if found any overlap, 0 if not, <0 if error. 136eecf5eedSPeter Xu */ 137eecf5eedSPeter Xu void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator); 138eecf5eedSPeter Xu 139eecf5eedSPeter Xu /** 1409376bde8SEugenio Pérez * iova_tree_alloc_map: 1419376bde8SEugenio Pérez * 1429376bde8SEugenio Pérez * @tree: the iova tree to allocate from 1439376bde8SEugenio Pérez * @map: the new map (as translated addr & size) to allocate in the iova region 1449376bde8SEugenio Pérez * @iova_begin: the minimum address of the allocation 1459376bde8SEugenio Pérez * @iova_end: the maximum addressable direction of the allocation 1469376bde8SEugenio Pérez * 1479376bde8SEugenio Pérez * Allocates a new region of a given size, between iova_min and iova_max. 1489376bde8SEugenio Pérez * 1499376bde8SEugenio Pérez * Return: Same as iova_tree_insert, but cannot overlap and can return error if 1509376bde8SEugenio Pérez * iova tree is out of free contiguous range. The caller gets the assigned iova 1519376bde8SEugenio Pérez * in map->iova. 1529376bde8SEugenio Pérez */ 1539376bde8SEugenio Pérez int iova_tree_alloc_map(IOVATree *tree, DMAMap *map, hwaddr iova_begin, 1549376bde8SEugenio Pérez hwaddr iova_end); 1559376bde8SEugenio Pérez 1569376bde8SEugenio Pérez /** 157eecf5eedSPeter Xu * iova_tree_destroy: 158eecf5eedSPeter Xu * 159eecf5eedSPeter Xu * @tree: the iova tree to destroy 160eecf5eedSPeter Xu * 161eecf5eedSPeter Xu * Destroy an existing iova tree. 162eecf5eedSPeter Xu * 163eecf5eedSPeter Xu * Return: None. 164eecf5eedSPeter Xu */ 165eecf5eedSPeter Xu void iova_tree_destroy(IOVATree *tree); 166eecf5eedSPeter Xu 167eecf5eedSPeter Xu #endif 168