Re: [PATCH v13 10/15] vfio/type1: Implement recursive vfio_find_dma_from_node

Alex Williamson
2016-10-06T20:19:00Z

On Thu, 6 Oct 2016 08:45:26 +0000
Eric Auger <eric.auger-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> 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 <eric.auger-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>

Acked-by: Alex Williamson <alex.williamson-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>

> ---
>
> 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;
> }
>
> /**