From mboxrd@z Thu Jan 1 00:00:00 1970 From: Alex Williamson Subject: Re: [PATCH v13 10/15] vfio/type1: Implement recursive vfio_find_dma_from_node Date: Thu, 6 Oct 2016 14:19:00 -0600 Message-ID: <20161006141900.6245f1f1@t450s.home> 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 Return-path: In-Reply-To: <1475743531-4780-11-git-send-email-eric.auger-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: iommu-bounces-cunTk1MwBs9QetFLy7KEm3xJsTq8ys+cHZ5vskTnxNA@public.gmane.org Errors-To: iommu-bounces-cunTk1MwBs9QetFLy7KEm3xJsTq8ys+cHZ5vskTnxNA@public.gmane.org To: Eric Auger Cc: yehuday-eYqpPyKDWXRBDgjK7y7TUQ@public.gmane.org, drjones-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org, jason-NLaQJdtUoK4Be96aLqz0jA@public.gmane.org, kvm-u79uwXL29TY76Z2rM5mHXA@public.gmane.org, marc.zyngier-5wv7dgnIgG8@public.gmane.org, p.fedin-Sze3O3UU22JBDgjK7y7TUQ@public.gmane.org, will.deacon-5wv7dgnIgG8@public.gmane.org, linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org, iommu-cunTk1MwBs9QetFLy7KEm3xJsTq8ys+cHZ5vskTnxNA@public.gmane.org, pranav.sawargaonkar-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org, linux-arm-kernel-IAPFreCvJWM7uuMidbF8XUB+6BGkLq7r@public.gmane.org, tglx-hfZtesqFncYOwBW4kG4KsQ@public.gmane.org, Manish.Jaggi-M3mlKVOIwJVv6pq1l3V1OdBPR1lH4CV8@public.gmane.org, christoffer.dall-QSEj5FYQhm4dnm+yROfE0A@public.gmane.org, eric.auger.pro-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org List-Id: iommu@lists.linux-foundation.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; > } > > /**