From nobody Mon Feb 9 15:11:05 2026 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=redhat.com ARC-Seal: i=1; a=rsa-sha256; t=1621443217; cv=none; d=zohomail.com; s=zohoarc; b=jRqOPO6EfgXRqQz8ZTyVkQDxTEOTQLCDGoCBpv81COyMCtzZiY+Qq4BY3a3fq4qvJZwy7rMc+zb/B0fyjquK+4OZVqehedJjAREfc5XnvvWB451xMkseKrZPBpUNpbf9muOTHydbeg7UTRRdxPlAK4mKEWQVEVEtKhqHnN7wvTw= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1621443217; h=Content-Type:Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=uP4UtvtAVqjJFYeWJ8J8gGnTPjK6WSRqP+XvyKxXAtY=; b=U/ROKo85eUg3V3XzXzw8WBSDTL4yPaz9qx4mw4RWIdrpO2yFobJHJBlWEElxbrqUxCkp3SVMmBiTEryiW6+7rNz9uusy1vRNb2gp5JwJbJrMFzQ3W0CyDemkt70YrHolW7TJrTiSWgCpTi8hd0Y4yXX0nQvxlnvmToyQuu8YB8s= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=fail; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail header.from= (p=none dis=none) header.from= Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1621443217397412.00789993695594; Wed, 19 May 2021 09:53:37 -0700 (PDT) Received: from localhost ([::1]:53142 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ljPRw-0007hY-HU for importer@patchew.org; Wed, 19 May 2021 12:53:36 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:35308) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ljP7B-0006Ov-Fe for qemu-devel@nongnu.org; Wed, 19 May 2021 12:32:09 -0400 Received: from us-smtp-delivery-124.mimecast.com ([216.205.24.124]:53023) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ljP72-00062D-7U for qemu-devel@nongnu.org; Wed, 19 May 2021 12:32:09 -0400 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-181-pXOuTORTNKqDLRTZ1BdAgA-1; Wed, 19 May 2021 12:31:56 -0400 Received: from smtp.corp.redhat.com (int-mx05.intmail.prod.int.phx2.redhat.com [10.5.11.15]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 6E030107ACC7; Wed, 19 May 2021 16:31:54 +0000 (UTC) Received: from eperezma.remote.csb (ovpn-113-65.ams2.redhat.com [10.36.113.65]) by smtp.corp.redhat.com (Postfix) with ESMTP id 3C43F5D6AC; Wed, 19 May 2021 16:31:51 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1621441919; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=uP4UtvtAVqjJFYeWJ8J8gGnTPjK6WSRqP+XvyKxXAtY=; b=dio4liD2o2WwwhJKk7Ub+RtXB2TwgES1trRkYHhR5beaKQg7PINuyX8wKhrvymwBORu00p Kpzqh4odqhqSaw0NsaHJNCFzk6tGfQ419xNVQGA46KVzf6YwRkUCzWvGDDRBG6UM5dLGlY q3ZicqdEmJ/YnbluEGYDHHoXf7/fGEA= X-MC-Unique: pXOuTORTNKqDLRTZ1BdAgA-1 From: =?UTF-8?q?Eugenio=20P=C3=A9rez?= To: qemu-devel@nongnu.org Subject: [RFC v3 22/29] vhost: Add iova_rev_maps_find_iova to IOVAReverseMaps Date: Wed, 19 May 2021 18:28:56 +0200 Message-Id: <20210519162903.1172366-23-eperezma@redhat.com> In-Reply-To: <20210519162903.1172366-1-eperezma@redhat.com> References: <20210519162903.1172366-1-eperezma@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.15 Authentication-Results: relay.mimecast.com; auth=pass smtp.auth=CUSA124A263 smtp.mailfrom=eperezma@redhat.com X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Received-SPF: pass client-ip=216.205.24.124; envelope-from=eperezma@redhat.com; helo=us-smtp-delivery-124.mimecast.com X-Spam_score_int: -31 X-Spam_score: -3.2 X-Spam_bar: --- X-Spam_report: (-3.2 / 5.0 requ) BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.39, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Parav Pandit , "Michael S. Tsirkin" , Jason Wang , Juan Quintela , Markus Armbruster , virtualization@lists.linux-foundation.org, Harpreet Singh Anand , Xiao W Wang , Stefan Hajnoczi , Eli Cohen , Michael Lilja , Stefano Garzarella Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: fail (Header signature does not verify) Shadow virtqueue can translate addresses from guest's address to it's own address space this way. It duplicates the array so it can search efficiently both directions, and it will signal overlap if iova or the translated address is present in it's each array. Signed-off-by: Eugenio P=C3=A9rez --- hw/virtio/vhost-iova-tree.h | 10 +++++++- hw/virtio/vhost-iova-tree.c | 49 ++++++++++++++++++++++++++++++++++--- 2 files changed, 55 insertions(+), 4 deletions(-) diff --git a/hw/virtio/vhost-iova-tree.h b/hw/virtio/vhost-iova-tree.h index 2a44af8b3a..589e86bd91 100644 --- a/hw/virtio/vhost-iova-tree.h +++ b/hw/virtio/vhost-iova-tree.h @@ -30,18 +30,26 @@ typedef enum VhostDMAMapNewRC { /** * VhostIOVATree * - * Store and search IOVA -> Translated mappings. + * Store and search IOVA -> Translated mappings and the reverse, from + * translated address to IOVA. * * Note that it cannot remove nodes. */ typedef struct VhostIOVATree { /* Ordered array of reverse translations, IOVA address to qemu memory.= */ GArray *iova_taddr_map; + + /* + * Ordered array of translations from qemu virtual memory address to i= ova + */ + GArray *taddr_iova_map; } VhostIOVATree; =20 void vhost_iova_tree_new(VhostIOVATree *iova_rm); void vhost_iova_tree_destroy(VhostIOVATree *iova_rm); =20 +const VhostDMAMap *vhost_iova_tree_find_iova(const VhostIOVATree *iova_rm, + const VhostDMAMap *map); const VhostDMAMap *vhost_iova_tree_find_taddr(const VhostIOVATree *iova_rm, const VhostDMAMap *map); VhostDMAMapNewRC vhost_iova_tree_insert(VhostIOVATree *iova_rm, diff --git a/hw/virtio/vhost-iova-tree.c b/hw/virtio/vhost-iova-tree.c index dfd7e448b5..2900390a1e 100644 --- a/hw/virtio/vhost-iova-tree.c +++ b/hw/virtio/vhost-iova-tree.c @@ -39,6 +39,22 @@ static void vhost_iova_tree_insert_after(GArray *array, g_array_insert_val(array, pos, *map); } =20 +static gint vhost_iova_tree_cmp_taddr(gconstpointer a, gconstpointer b) +{ + const VhostDMAMap *m1 =3D a, *m2 =3D b; + + if (m1->translated_addr > m2->translated_addr + m2->size) { + return 1; + } + + if (m1->translated_addr + m1->size < m2->translated_addr) { + return -1; + } + + /* Overlapped */ + return 0; +} + static gint vhost_iova_tree_cmp_iova(gconstpointer a, gconstpointer b) { const VhostDMAMap *m1 =3D a, *m2 =3D b; @@ -106,6 +122,9 @@ void vhost_iova_tree_new(VhostIOVATree *tree) tree->iova_taddr_map =3D g_array_new(G_ARRAY_NOT_ZERO_TERMINATED, G_ARRAY_NOT_CLEAR_ON_ALLOC, sizeof(VhostDMAMap)); + tree->taddr_iova_map =3D g_array_new(G_ARRAY_NOT_ZERO_TERMINATED, + G_ARRAY_NOT_CLEAR_ON_ALLOC, + sizeof(VhostDMAMap)); } =20 /** @@ -116,6 +135,7 @@ void vhost_iova_tree_new(VhostIOVATree *tree) void vhost_iova_tree_destroy(VhostIOVATree *tree) { g_array_unref(g_steal_pointer(&tree->iova_taddr_map)); + g_array_unref(g_steal_pointer(&tree->taddr_iova_map)); } =20 /** @@ -137,6 +157,21 @@ static const VhostDMAMap *vhost_iova_tree_bsearch(cons= t GArray *array, return bsearch(map, array->data, array->len, sizeof(*map), compare_fun= c); } =20 +/** + * Find the IOVA address stored from a memory address + * + * @tree The iova tree + * @map The map with the memory address + * + * Return the stored mapping, or NULL if not found. + */ +const VhostDMAMap *vhost_iova_tree_find_iova(const VhostIOVATree *tree, + const VhostDMAMap *map) +{ + return vhost_iova_tree_bsearch(tree->taddr_iova_map, map, + vhost_iova_tree_cmp_taddr); +} + /** * Find the translated address stored from a IOVA address * @@ -167,7 +202,7 @@ const VhostDMAMap *vhost_iova_tree_find_taddr(const Vho= stIOVATree *tree, VhostDMAMapNewRC vhost_iova_tree_insert(VhostIOVATree *tree, VhostDMAMap *map) { - const VhostDMAMap *prev; + const VhostDMAMap *qemu_prev, *iova_prev; int find_prev_rc; =20 if (map->translated_addr + map->size < map->translated_addr || @@ -178,11 +213,19 @@ VhostDMAMapNewRC vhost_iova_tree_insert(VhostIOVATree= *tree, /* Check for duplicates, and save position for insertion */ find_prev_rc =3D vhost_iova_tree_find_prev(tree->iova_taddr_map, vhost_iova_tree_cmp_iova, map, - &prev); + &iova_prev); + if (find_prev_rc =3D=3D VHOST_DMA_MAP_OVERLAP) { + return VHOST_DMA_MAP_OVERLAP; + } + + find_prev_rc =3D vhost_iova_tree_find_prev(tree->taddr_iova_map, + vhost_iova_tree_cmp_taddr, ma= p, + &qemu_prev); if (find_prev_rc =3D=3D VHOST_DMA_MAP_OVERLAP) { return VHOST_DMA_MAP_OVERLAP; } =20 - vhost_iova_tree_insert_after(tree->iova_taddr_map, prev, map); + vhost_iova_tree_insert_after(tree->iova_taddr_map, iova_prev, map); + vhost_iova_tree_insert_after(tree->taddr_iova_map, qemu_prev, map); return VHOST_DMA_MAP_OK; } --=20 2.27.0