/* * An very simplified iova tree implementation based on GTree. * * Copyright 2018 Red Hat, Inc. * * Authors: * Peter Xu <peterx@redhat.com> * * This work is licensed under the terms of the GNU GPL, version 2 or later. */ #ifndef IOVA_TREE_H #define IOVA_TREE_H /* * Currently the iova tree will only allow to keep ranges * information, and no extra user data is allowed for each element. A * benefit is that we can merge adjacent ranges internally within the * tree. It can save a lot of memory when the ranges are splitted but * mostly continuous. * * Note that current implementation does not provide any thread * protections. Callers of the iova tree should be responsible * for the thread safety issue. */ #include "exec/memory.h" #include "exec/hwaddr.h" #define IOVA_OK (0) #define IOVA_ERR_INVALID (-1) /* Invalid parameters */ #define IOVA_ERR_OVERLAP (-2) /* IOVA range overlapped */ typedef struct IOVATree IOVATree; typedef struct DMAMap { hwaddr iova; hwaddr translated_addr; hwaddr size; /* Inclusive */ IOMMUAccessFlags perm; } QEMU_PACKED DMAMap; typedef gboolean (*iova_tree_iterator)(DMAMap *map); /** * iova_tree_new: * * Create a new iova tree. * * Returns: the tree pointer when succeeded, or NULL if error. */ IOVATree *iova_tree_new(void); /** * iova_tree_insert: * * @tree: the iova tree to insert * @map: the mapping to insert * * Insert an iova range to the tree. If there is overlapped * ranges, IOVA_ERR_OVERLAP will be returned. * * Return: 0 if succeeded, or <0 if error. */ int iova_tree_insert(IOVATree *tree, DMAMap *map); /** * iova_tree_remove: * * @tree: the iova tree to remove range from * @map: the map range to remove * * Remove mappings from the tree that are covered by the map range * provided. The range does not need to be exactly what has inserted, * all the mappings that are included in the provided range will be * removed from the tree. Here map->translated_addr is meaningless. * * Return: 0 if succeeded, or <0 if error. */ int iova_tree_remove(IOVATree *tree, DMAMap *map); /** * iova_tree_find: * * @tree: the iova tree to search from * @map: the mapping to search * * Search for a mapping in the iova tree that overlaps with the * mapping range specified. Only the first found mapping will be * returned. * * Return: DMAMap pointer if found, or NULL if not found. Note that * the returned DMAMap pointer is maintained internally. User should * only read the content but never modify or free the content. Also, * user is responsible to make sure the pointer is valid (say, no * concurrent deletion in progress). */ DMAMap *iova_tree_find(IOVATree *tree, DMAMap *map); /** * iova_tree_find_address: * * @tree: the iova tree to search from * @iova: the iova address to find * * Similar to iova_tree_find(), but it tries to find mapping with * range iova=iova & size=0. * * Return: same as iova_tree_find(). */ DMAMap *iova_tree_find_address(IOVATree *tree, hwaddr iova); /** * iova_tree_foreach: * * @tree: the iova tree to iterate on * @iterator: the interator for the mappings, return true to stop * * Iterate over the iova tree. * * Return: 1 if found any overlap, 0 if not, <0 if error. */ void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator); /** * iova_tree_destroy: * * @tree: the iova tree to destroy * * Destroy an existing iova tree. * * Return: None. */ void iova_tree_destroy(IOVATree *tree); #endif