Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S933592AbcJLNcn (ORCPT ); Wed, 12 Oct 2016 09:32:43 -0400 Received: from mx1.redhat.com ([209.132.183.28]:55942 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754751AbcJLNcD (ORCPT ); Wed, 12 Oct 2016 09:32:03 -0400 From: Eric Auger To: eric.auger@redhat.com, eric.auger.pro@gmail.com, christoffer.dall@linaro.org, marc.zyngier@arm.com, robin.murphy@arm.com, alex.williamson@redhat.com, will.deacon@arm.com, joro@8bytes.org, tglx@linutronix.de, jason@lakedaemon.net, linux-arm-kernel@lists.infradead.org Cc: kvm@vger.kernel.org, drjones@redhat.com, linux-kernel@vger.kernel.org, Bharat.Bhushan@freescale.com, pranav.sawargaonkar@gmail.com, p.fedin@samsung.com, iommu@lists.linux-foundation.org, Jean-Philippe.Brucker@arm.com, yehuday@marvell.com, Manish.Jaggi@caviumnetworks.com Subject: [PATCH v14 10/16] vfio/type1: vfio_find_dma accepting a type argument Date: Wed, 12 Oct 2016 13:22:18 +0000 Message-Id: <1476278544-3397-11-git-send-email-eric.auger@redhat.com> In-Reply-To: <1476278544-3397-1-git-send-email-eric.auger@redhat.com> References: <1476278544-3397-1-git-send-email-eric.auger@redhat.com> X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.25]); Wed, 12 Oct 2016 13:23:19 +0000 (UTC) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 3914 Lines: 127 In our RB-tree we get prepared to insert slots of different types (USER and RESERVED). It becomes useful to be able to search for dma slots of a specific type or any type. This patch introduces vfio_find_dma_from_node which starts the search from a given node and stops on the first node that matches the @start and @size parameters. If this node also matches the @type parameter, the node is returned else NULL is returned. At the moment we only have USER SLOTS so the type will always match. In a separate patch, this function will be enhanced to pursue the search recursively in case a node with a different type is encountered. Signed-off-by: Eric Auger --- v13 -> v14: - remove top_node variable --- drivers/vfio/vfio_iommu_type1.c | 52 +++++++++++++++++++++++++++++++++-------- 1 file changed, 42 insertions(+), 10 deletions(-) diff --git a/drivers/vfio/vfio_iommu_type1.c b/drivers/vfio/vfio_iommu_type1.c index a9f8b93..1bd16ff 100644 --- a/drivers/vfio/vfio_iommu_type1.c +++ b/drivers/vfio/vfio_iommu_type1.c @@ -94,25 +94,55 @@ struct vfio_group { * into DMA'ble space using the IOMMU */ -static struct vfio_dma *vfio_find_dma(struct vfio_iommu *iommu, - dma_addr_t start, size_t size) +/** + * vfio_find_dma_from_node: looks for a dma slot intersecting a window + * from a given rb tree node + * @top: top rb tree node where the search starts (including this node) + * @start: window start + * @size: window size + * @type: window type + */ +static struct vfio_dma *vfio_find_dma_from_node(struct rb_node *top, + dma_addr_t start, size_t size, + enum vfio_iova_type type) { - struct rb_node *node = iommu->dma_list.rb_node; + struct rb_node *node = top; + struct vfio_dma *dma; while (node) { - struct vfio_dma *dma = rb_entry(node, struct vfio_dma, node); - + dma = rb_entry(node, struct vfio_dma, node); if (start + size <= dma->iova) node = node->rb_left; else if (start >= dma->iova + dma->size) node = node->rb_right; else - return dma; + break; } + if (!node) + return NULL; + + /* a dma slot intersects our window, check the type also matches */ + if (type == VFIO_IOVA_ANY || dma->type == type) + return dma; return NULL; } +/** + * vfio_find_dma: find a dma slot intersecting a given window + * @iommu: vfio iommu handle + * @start: window base iova + * @size: window size + * @type: window type + */ +static struct vfio_dma *vfio_find_dma(struct vfio_iommu *iommu, + dma_addr_t start, size_t size, + enum vfio_iova_type type) +{ + return vfio_find_dma_from_node(iommu->dma_list.rb_node, + start, size, type); +} + static void vfio_link_dma(struct vfio_iommu *iommu, struct vfio_dma *new) { struct rb_node **link = &iommu->dma_list.rb_node, *parent = NULL; @@ -484,19 +514,21 @@ static int vfio_dma_do_unmap(struct vfio_iommu *iommu, * mappings within the range. */ if (iommu->v2) { - dma = vfio_find_dma(iommu, unmap->iova, 0); + dma = vfio_find_dma(iommu, unmap->iova, 0, VFIO_IOVA_USER); if (dma && dma->iova != unmap->iova) { ret = -EINVAL; goto unlock; } - dma = vfio_find_dma(iommu, unmap->iova + unmap->size - 1, 0); + dma = vfio_find_dma(iommu, unmap->iova + unmap->size - 1, 0, + VFIO_IOVA_USER); if (dma && dma->iova + dma->size != unmap->iova + unmap->size) { ret = -EINVAL; goto unlock; } } - while ((dma = vfio_find_dma(iommu, unmap->iova, unmap->size))) { + while ((dma = vfio_find_dma(iommu, unmap->iova, unmap->size, + VFIO_IOVA_USER))) { if (!iommu->v2 && unmap->iova > dma->iova) break; unmapped += dma->size; @@ -600,7 +632,7 @@ static int vfio_dma_do_map(struct vfio_iommu *iommu, mutex_lock(&iommu->lock); - if (vfio_find_dma(iommu, iova, size)) { + if (vfio_find_dma(iommu, iova, size, VFIO_IOVA_ANY)) { mutex_unlock(&iommu->lock); return -EEXIST; } -- 1.9.1