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

[Steven Sistare <steven.sistare@oracle.com>]

On 1/5/2021 7:02 PM, Alex Williamson wrote:
> 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.

Agreed.  Bad explanation on my part.

>> 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,

Sure, will do.

- Steve

> 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;
>