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