Re: [PATCH V1 1/5] vfio: maintain dma_list order

[Alex Williamson <alex.williamson@redhat.com>]

Hi Steven,

On Tue,  5 Jan 2021 07:36:49 -0800
Steve Sistare <steven.sistare@oracle.com> wrote:

> Keep entries properly sorted in the dma_list rb_tree

Nothing here changes the order of entries in the tree, they're already
sorted.  The second chunk is the only thing that touches the tree
construction, but that appears to be just a micro optimization that
we've already used vfio_find_dma() to verify that a new entry doesn't
overlap any existing entries, therefore if the start of the new entry
is less than the test entry, the end must also be less.  The tree is
not changed afaict.

> so that iterating
> over multiple entries across a range with gaps works, without requiring
> one to delete each visited entry as in vfio_dma_do_unmap.

As above, I don't see that the tree is changed, so this is just a
manipulation of our search function, changing it from a "find any
vfio_dma within this range" to a "find the vfio_dma with the lowest
iova with this range".  But find-any and find-first are computationally
different, so I don't think we should blindly replace one with the
other.  Wouldn't it make more sense to add a vfio_find_first_dma()
function in patch 4/ to handle this case?  Thanks,

Alex

> Signed-off-by: Steve Sistare <steven.sistare@oracle.com>
> ---
>  drivers/vfio/vfio_iommu_type1.c | 18 +++++++++++-------
>  1 file changed, 11 insertions(+), 7 deletions(-)
> 
> diff --git a/drivers/vfio/vfio_iommu_type1.c b/drivers/vfio/vfio_iommu_type1.c
> index 5fbf0c1..02228d0 100644
> --- a/drivers/vfio/vfio_iommu_type1.c
> +++ b/drivers/vfio/vfio_iommu_type1.c
> @@ -157,20 +157,24 @@ static struct vfio_group *vfio_iommu_find_iommu_group(struct vfio_iommu *iommu,
>  static struct vfio_dma *vfio_find_dma(struct vfio_iommu *iommu,
>  				      dma_addr_t start, size_t size)
>  {
> +	struct vfio_dma *res = 0;
>  	struct rb_node *node = iommu->dma_list.rb_node;
>  
>  	while (node) {
>  		struct vfio_dma *dma = rb_entry(node, struct vfio_dma, node);
>  
> -		if (start + size <= dma->iova)
> +		if (start < dma->iova + dma->size) {
> +			res = dma;
> +			if (start >= dma->iova)
> +				break;
>  			node = node->rb_left;
> -		else if (start >= dma->iova + dma->size)
> +		} else {
>  			node = node->rb_right;
> -		else
> -			return dma;
> +		}
>  	}
> -
> -	return NULL;
> +	if (res && size && res->iova >= start + size)
> +		res = 0;
> +	return res;
>  }
>  
>  static void vfio_link_dma(struct vfio_iommu *iommu, struct vfio_dma *new)
> @@ -182,7 +186,7 @@ static void vfio_link_dma(struct vfio_iommu *iommu, struct vfio_dma *new)
>  		parent = *link;
>  		dma = rb_entry(parent, struct vfio_dma, node);
>  
> -		if (new->iova + new->size <= dma->iova)
> +		if (new->iova < dma->iova)
>  			link = &(*link)->rb_left;
>  		else
>  			link = &(*link)->rb_right;