From nobody Sun Feb 8 18:30:14 2026 Delivered-To: importer@patchew.org Received-SPF: pass (zoho.com: domain of gnu.org designates 208.118.235.17 as permitted sender) client-ip=208.118.235.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Authentication-Results: mx.zohomail.com; dkim=fail; spf=pass (zoho.com: domain of gnu.org designates 208.118.235.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org Return-Path: Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) by mx.zohomail.com with SMTPS id 153237824330336.01634027194109; Mon, 23 Jul 2018 13:37:23 -0700 (PDT) Received: from localhost ([::1]:36433 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fhha5-0000vG-Rf for importer@patchew.org; Mon, 23 Jul 2018 16:37:21 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:41322) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fhhIx-00028I-9Y for qemu-devel@nongnu.org; Mon, 23 Jul 2018 16:19:42 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fhhIv-0003c6-Hi for qemu-devel@nongnu.org; Mon, 23 Jul 2018 16:19:39 -0400 Received: from mail-oi0-x244.google.com ([2607:f8b0:4003:c06::244]:46626) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1fhhIv-0003bJ-AV; Mon, 23 Jul 2018 16:19:37 -0400 Received: by mail-oi0-x244.google.com with SMTP id y207-v6so3454222oie.13; Mon, 23 Jul 2018 13:19:37 -0700 (PDT) Received: from localhost (76-251-165-188.lightspeed.austtx.sbcglobal.net. [76.251.165.188]) by smtp.gmail.com with ESMTPSA id o206-v6sm8218641oif.7.2018.07.23.13.19.34 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Mon, 23 Jul 2018 13:19:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=sender:from:to:cc:subject:date:message-id:in-reply-to:references; bh=rAyHxefDtpGxJaBShyBX1rBK6cXw7xKm2QP+sdhWplQ=; b=YjkV1NHGNyXDgbbAYHJXFOpn30H6j09xBEzOqQ5OjspUo1/taJNlDOr4z8+urJ4wVR LCtF8eY2+zJ9EGOd/pSycvnnyDjhsmyXY/GN8rI0xbfiAS/I7K+VBW7HhDOPinwcnhmF adveOuJxx5PQqByGZC/PpqV6U9/57nxIVFDuyqxwua0gAYvvZlvwz01aCxYyCogOAoiC 81aBvwRHQ2yhprAB9wODpkwZfPqAGBbcJoPrgra8im8VciVyCOYrg8162LIz4WjetyPQ kg5W1VABPDTMvh9dIprOJ/AZfvPscV80bQ8ynjqO3EzALT+UPjRrVBjeexIiSye5iOCP Cs4A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:from:to:cc:subject:date:message-id :in-reply-to:references; bh=rAyHxefDtpGxJaBShyBX1rBK6cXw7xKm2QP+sdhWplQ=; b=HTgl07ZTbkcmoko8QQdkjYtEurxVj4F+Mtxr4zBgG3cd5/eM6lE0UsMIzjQMmbd3ca Huc4um1XYU8BSZCOUUa1jJOTrkRPtQoN/yBFDntU0/QBB8qPju3eywNC/l9YF8+JOYru Ut2pZKTlje1Gjqkl9oCWlHR2LOT8WlteDHyr+QhoixJrEq0+hNyDvgpqO35eV9DoNW3E El1Lbcqf0WMh52CmB7/jjQcZfPfOF9uAGBE1iYJPUaMRahWVKM5rIPtb7MSzgIAsu7QO sPuw4jZzFiDvUyf2BJmqEvBOfZsoxR1wfe1YVfmM/xHJ4F8PJ5R7UtaesvFZk6+LyUHX eJiQ== X-Gm-Message-State: AOUpUlHdkFQKVtsv1GnE5P89DlGPyypQmGxo3AKZQPgkWWY7ZQRzStFj NVfLnC3tTu7Xhq1/OCVtk/EmsxUXsac= X-Google-Smtp-Source: AAOMgpefsfi0Pqg+IPij1TvYSNisFdo8XFd2mxyS4Ty/j8ur9y8ayL6r0Ow6mCrySP1GXcSLR110pg== X-Received: by 2002:aca:5354:: with SMTP id h81-v6mr246002oib.299.1532377176082; Mon, 23 Jul 2018 13:19:36 -0700 (PDT) From: Michael Roth To: qemu-devel@nongnu.org Date: Mon, 23 Jul 2018 15:16:41 -0500 Message-Id: <20180723201748.25573-33-mdroth@linux.vnet.ibm.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180723201748.25573-1-mdroth@linux.vnet.ibm.com> References: <20180723201748.25573-1-mdroth@linux.vnet.ibm.com> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2607:f8b0:4003:c06::244 Subject: [Qemu-devel] [PATCH 32/99] util: implement simple iova tree X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: qemu-stable@nongnu.org, Peter Xu , "Michael S . Tsirkin" Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: fail (Header signature does not verify) X-ZohoMail: RDKM_2 RSF_0 Z_629925259 SPT_0 Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" From: Peter Xu Introduce a simplest iova tree implementation based on GTree. CC: QEMU Stable Signed-off-by: Peter Xu Reviewed-by: Michael S. Tsirkin Signed-off-by: Michael S. Tsirkin (cherry picked from commit eecf5eedbdc0fc04f39abcf3afeedfbf21b25ca4) Signed-off-by: Michael Roth --- MAINTAINERS | 6 ++ include/qemu/iova-tree.h | 134 +++++++++++++++++++++++++++++++++++++++ util/Makefile.objs | 1 + util/iova-tree.c | 114 +++++++++++++++++++++++++++++++++ 4 files changed, 255 insertions(+) create mode 100644 include/qemu/iova-tree.h create mode 100644 util/iova-tree.c diff --git a/MAINTAINERS b/MAINTAINERS index 24b70169bc..ada7c33485 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -1781,6 +1781,12 @@ F: include/sysemu/replay.h F: docs/replay.txt F: stubs/replay.c =20 +IOVA Tree +M: Peter Xu +S: Maintained +F: include/qemu/iova-tree.h +F: util/iova-tree.c + Usermode Emulation ------------------ Overall diff --git a/include/qemu/iova-tree.h b/include/qemu/iova-tree.h new file mode 100644 index 0000000000..b061932097 --- /dev/null +++ b/include/qemu/iova-tree.h @@ -0,0 +1,134 @@ +/* + * An very simplified iova tree implementation based on GTree. + * + * Copyright 2018 Red Hat, Inc. + * + * Authors: + * Peter Xu + * + * This work is licensed under the terms of the GNU GPL, version 2 or late= r. + */ +#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 "qemu/osdep.h" +#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=3Diova & size=3D0. + * + * 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 diff --git a/util/Makefile.objs b/util/Makefile.objs index 728c3541db..e1c3fed4dc 100644 --- a/util/Makefile.objs +++ b/util/Makefile.objs @@ -47,4 +47,5 @@ util-obj-y +=3D qht.o util-obj-y +=3D range.o util-obj-y +=3D stats64.o util-obj-y +=3D systemd.o +util-obj-y +=3D iova-tree.o util-obj-$(CONFIG_LINUX) +=3D vfio-helpers.o diff --git a/util/iova-tree.c b/util/iova-tree.c new file mode 100644 index 0000000000..2d9cebfc89 --- /dev/null +++ b/util/iova-tree.c @@ -0,0 +1,114 @@ +/* + * IOVA tree implementation based on GTree. + * + * Copyright 2018 Red Hat, Inc. + * + * Authors: + * Peter Xu + * + * This work is licensed under the terms of the GNU GPL, version 2 or late= r. + */ + +#include +#include "qemu/iova-tree.h" + +struct IOVATree { + GTree *tree; +}; + +static int iova_tree_compare(gconstpointer a, gconstpointer b, gpointer da= ta) +{ + const DMAMap *m1 =3D a, *m2 =3D b; + + if (m1->iova > m2->iova + m2->size) { + return 1; + } + + if (m1->iova + m1->size < m2->iova) { + return -1; + } + + /* Overlapped */ + return 0; +} + +IOVATree *iova_tree_new(void) +{ + IOVATree *iova_tree =3D g_new0(IOVATree, 1); + + /* We don't have values actually, no need to free */ + iova_tree->tree =3D g_tree_new_full(iova_tree_compare, NULL, g_free, N= ULL); + + return iova_tree; +} + +DMAMap *iova_tree_find(IOVATree *tree, DMAMap *map) +{ + return g_tree_lookup(tree->tree, map); +} + +DMAMap *iova_tree_find_address(IOVATree *tree, hwaddr iova) +{ + DMAMap map =3D { .iova =3D iova, .size =3D 0 }; + + return iova_tree_find(tree, &map); +} + +static inline void iova_tree_insert_internal(GTree *gtree, DMAMap *range) +{ + /* Key and value are sharing the same range data */ + g_tree_insert(gtree, range, range); +} + +int iova_tree_insert(IOVATree *tree, DMAMap *map) +{ + DMAMap *new; + + if (map->iova + map->size < map->iova || map->perm =3D=3D IOMMU_NONE) { + return IOVA_ERR_INVALID; + } + + /* We don't allow to insert range that overlaps with existings */ + if (iova_tree_find(tree, map)) { + return IOVA_ERR_OVERLAP; + } + + new =3D g_new0(DMAMap, 1); + memcpy(new, map, sizeof(*new)); + iova_tree_insert_internal(tree->tree, new); + + return IOVA_OK; +} + +static gboolean iova_tree_traverse(gpointer key, gpointer value, + gpointer data) +{ + iova_tree_iterator iterator =3D data; + DMAMap *map =3D key; + + g_assert(key =3D=3D value); + + return iterator(map); +} + +void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator) +{ + g_tree_foreach(tree->tree, iova_tree_traverse, iterator); +} + +int iova_tree_remove(IOVATree *tree, DMAMap *map) +{ + DMAMap *overlap; + + while ((overlap =3D iova_tree_find(tree, map))) { + g_tree_remove(tree->tree, overlap); + } + + return IOVA_OK; +} + +void iova_tree_destroy(IOVATree *tree) +{ + g_tree_destroy(tree->tree); + g_free(tree); +} --=20 2.17.1