From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S935072AbcJFUT5 (ORCPT ); Thu, 6 Oct 2016 16:19:57 -0400 Received: from mx1.redhat.com ([209.132.183.28]:40934 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752315AbcJFUTt (ORCPT ); Thu, 6 Oct 2016 16:19:49 -0400 Date: Thu, 6 Oct 2016 14:19:00 -0600 From: Alex Williamson To: Eric Auger Cc: eric.auger.pro@gmail.com, christoffer.dall@linaro.org, marc.zyngier@arm.com, robin.murphy@arm.com, will.deacon@arm.com, joro@8bytes.org, tglx@linutronix.de, jason@lakedaemon.net, linux-arm-kernel@lists.infradead.org, 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: Re: [PATCH v13 10/15] vfio/type1: Implement recursive vfio_find_dma_from_node Message-ID: <20161006141900.6245f1f1@t450s.home> In-Reply-To: <1475743531-4780-11-git-send-email-eric.auger@redhat.com> References: <1475743531-4780-1-git-send-email-eric.auger@redhat.com> <1475743531-4780-11-git-send-email-eric.auger@redhat.com> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.30]); Thu, 06 Oct 2016 20:19:02 +0000 (UTC) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Thu, 6 Oct 2016 08:45:26 +0000 Eric Auger wrote: > This patch handles the case where a node is encountered, matching > @start and @size arguments but not matching the @type argument. > In that case, we need to skip that node and pursue the search in the > node's leaves. In case @start is inferior to the node's base, we > resume the search on the left leaf. If the recursive search on the left > leaves did not produce any match, we search the right leaves recursively. > > Signed-off-by: Eric Auger Acked-by: Alex Williamson > --- > > v10: creation > --- > drivers/vfio/vfio_iommu_type1.c | 12 +++++++++++- > 1 file changed, 11 insertions(+), 1 deletion(-) > > diff --git a/drivers/vfio/vfio_iommu_type1.c b/drivers/vfio/vfio_iommu_type1.c > index cb7267a..65a4038 100644 > --- a/drivers/vfio/vfio_iommu_type1.c > +++ b/drivers/vfio/vfio_iommu_type1.c > @@ -125,7 +125,17 @@ static struct vfio_dma *vfio_find_dma_from_node(struct rb_node *top, > if (type == VFIO_IOVA_ANY || dma->type == type) > return dma; > > - return NULL; > + /* restart 2 searches skipping the current node */ > + if (start < dma->iova) { > + dma = vfio_find_dma_from_node(node->rb_left, start, > + size, type); > + if (dma) > + return dma; > + } > + if (start + size > dma->iova + dma->size) > + dma = vfio_find_dma_from_node(node->rb_right, start, > + size, type); > + return dma; > } > > /**