From 193d17be0b84cce87db4426622cd4e6b827cae2a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Eugenio=20P=C3=A9rez?= Date: Mon, 14 Mar 2022 18:34:49 +0100 Subject: util: add iova_tree_find_iova MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit This function does the reverse operation of iova_tree_find: To look for a mapping that match a translated address so we can do the reverse. This have linear complexity instead of logarithmic, but it supports overlapping HVA. Future developments could reduce it. Signed-off-by: Eugenio Pérez Acked-by: Michael S. Tsirkin Signed-off-by: Jason Wang --- util/iova-tree.c | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) (limited to 'util') diff --git a/util/iova-tree.c b/util/iova-tree.c index 139626b46f..6dff29c1f6 100644 --- a/util/iova-tree.c +++ b/util/iova-tree.c @@ -37,6 +37,11 @@ struct IOVATreeAllocArgs { bool iova_found; }; +typedef struct IOVATreeFindIOVAArgs { + const DMAMap *needle; + const DMAMap *result; +} IOVATreeFindIOVAArgs; + /** * Iterate args to the next hole * @@ -81,6 +86,35 @@ const DMAMap *iova_tree_find(const IOVATree *tree, const DMAMap *map) return g_tree_lookup(tree->tree, map); } +static gboolean iova_tree_find_address_iterator(gpointer key, gpointer value, + gpointer data) +{ + const DMAMap *map = key; + IOVATreeFindIOVAArgs *args = data; + const DMAMap *needle; + + g_assert(key == value); + + needle = args->needle; + if (map->translated_addr + map->size < needle->translated_addr || + needle->translated_addr + needle->size < map->translated_addr) { + return false; + } + + args->result = map; + return true; +} + +const DMAMap *iova_tree_find_iova(const IOVATree *tree, const DMAMap *map) +{ + IOVATreeFindIOVAArgs args = { + .needle = map, + }; + + g_tree_foreach(tree->tree, iova_tree_find_address_iterator, &args); + return args.result; +} + const DMAMap *iova_tree_find_address(const IOVATree *tree, hwaddr iova) { const DMAMap map = { .iova = iova, .size = 0 }; -- cgit v1.2.3