diff mbox series

[V1,1/5] vfio: maintain dma_list order

Message ID 1609861013-129801-2-git-send-email-steven.sistare@oracle.com (mailing list archive)
State New, archived
Headers show
Series vfio virtual address update | expand

Commit Message

Steve Sistare Jan. 5, 2021, 3:36 p.m. UTC
Keep entries properly sorted in the dma_list rb_tree 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.

Signed-off-by: Steve Sistare <steven.sistare@oracle.com>
---
 drivers/vfio/vfio_iommu_type1.c | 18 +++++++++++-------
 1 file changed, 11 insertions(+), 7 deletions(-)

Comments

kernel test robot Jan. 5, 2021, 6:48 p.m. UTC | #1
Hi Steve,

Thank you for the patch! Perhaps something to improve:

[auto build test WARNING on vfio/next]
[also build test WARNING on v5.11-rc2 next-20210104]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch]

url:    https://github.com/0day-ci/linux/commits/Steve-Sistare/vfio-virtual-address-update/20210106-000752
base:   https://github.com/awilliam/linux-vfio.git next
config: x86_64-randconfig-s022-20210105 (attached as .config)
compiler: gcc-9 (Debian 9.3.0-15) 9.3.0
reproduce:
        # apt-get install sparse
        # sparse version: v0.6.3-208-g46a52ca4-dirty
        # https://github.com/0day-ci/linux/commit/c7f4454de15f02ea6be7591e8ab4520e21da646e
        git remote add linux-review https://github.com/0day-ci/linux
        git fetch --no-tags linux-review Steve-Sistare/vfio-virtual-address-update/20210106-000752
        git checkout c7f4454de15f02ea6be7591e8ab4520e21da646e
        # save the attached .config to linux build tree
        make W=1 C=1 CF='-fdiagnostic-prefix -D__CHECK_ENDIAN__' ARCH=x86_64 

If you fix the issue, kindly add following tag as appropriate
Reported-by: kernel test robot <lkp@intel.com>


"sparse warnings: (new ones prefixed by >>)"
>> drivers/vfio/vfio_iommu_type1.c:160:32: sparse: sparse: Using plain integer as NULL pointer
   drivers/vfio/vfio_iommu_type1.c:176:23: sparse: sparse: Using plain integer as NULL pointer

vim +160 drivers/vfio/vfio_iommu_type1.c

   147	
   148	static struct vfio_group *vfio_iommu_find_iommu_group(struct vfio_iommu *iommu,
   149						       struct iommu_group *iommu_group);
   150	
   151	static void update_pinned_page_dirty_scope(struct vfio_iommu *iommu);
   152	/*
   153	 * This code handles mapping and unmapping of user data buffers
   154	 * into DMA'ble space using the IOMMU
   155	 */
   156	
   157	static struct vfio_dma *vfio_find_dma(struct vfio_iommu *iommu,
   158					      dma_addr_t start, size_t size)
   159	{
 > 160		struct vfio_dma *res = 0;
   161		struct rb_node *node = iommu->dma_list.rb_node;
   162	
   163		while (node) {
   164			struct vfio_dma *dma = rb_entry(node, struct vfio_dma, node);
   165	
   166			if (start < dma->iova + dma->size) {
   167				res = dma;
   168				if (start >= dma->iova)
   169					break;
   170				node = node->rb_left;
   171			} else {
   172				node = node->rb_right;
   173			}
   174		}
   175		if (res && size && res->iova >= start + size)
   176			res = 0;
   177		return res;
   178	}
   179	

---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all@lists.01.org
Alex Williamson Jan. 6, 2021, 12:02 a.m. UTC | #2
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;
Steve Sistare Jan. 6, 2021, 2:50 p.m. UTC | #3
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;
>
diff mbox series

Patch

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;