Re: [PATCH v4] vfio/type1: optimize vfio_pin_pages_remote() for large folio

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

On Mon, 26 May 2025 11:37:37 +0800
lizhe.67@bytedance.com wrote:

> On Fri, 23 May 2025 08:54:15 -0600, alex.williamson@redhat.com wrote: 
> 
> > > > +static long vpfn_pages(struct vfio_dma *dma,
> > > > +		       dma_addr_t iova_start, long nr_pages)
> > > > +{
> > > > +	dma_addr_t iova_end = iova_start + (nr_pages << PAGE_SHIFT);
> > > > +	struct vfio_pfn *vpfn;
> > > > +	long count = 0;
> > > > +
> > > > +	do {
> > > > +		vpfn = vfio_find_vpfn_range(dma, iova_start, iova_end);  
> > > 
> > > I am somehow confused here. Function vfio_find_vpfn_range()is designed
> > > to find, through the rbtree, the node that is closest to the root node
> > > and satisfies the condition within the range [iova_start, iova_end),
> > > rather than the node closest to iova_start? Or perhaps I have
> > > misunderstood something?  
> > 
> > Sorry, that's an oversight on my part.  We might forego the _range
> > version and just do an inline walk of the tree counting the number of
> > already accounted pfns within the range.  Thanks,
> > 
> > Alex
> >   
> > > > +		if (likely(!vpfn))
> > > > +			break;
> > > > +
> > > > +		count++;
> > > > +		iova_start = vpfn->iova + PAGE_SIZE;
> > > > +	} while (iova_start < iova_end);
> > > > +
> > > > +	return count;
> > > > +}  
> 
> The utilization of the function vpfn_pages() is undoubtedly a
> good idea. It can swiftly determine the num of vpfn pages
> within a specified range, which will evidently expedite the
> process of vfio_pin_pages_remote(). Given that the function
> vfio_find_vpfn_range() returns the "top" node in the rb tree
> that satisfies the condition within the range
> [iova_start, iova_end), might we consider implementing the
> functionality of vpfn_pages() using the following approach?
> 
> +static long _vpfn_pages(struct vfio_pfn *vpfn,
> +               dma_addr_t iova_start, dma_addr_t iova_end)
> +{
> +       struct vfio_pfn *left;
> +       struct vfio_pfn *right;
> +
> +       if (!vpfn)
> +               return 0;
> +
> +       left = vpfn->node.rb_left ?
> +               rb_entry(vpfn->node.rb_left, struct vfio_pfn, node) : NULL;
> +       right = vpfn->node.rb_right ?
> +               rb_entry(vpfn->node.rb_right, struct vfio_pfn, node) : NULL;
> +
> +       if ((vpfn->iova >= iova_start) && (vpfn->iova < iova_end))
> +               return 1 + _vpfn_pages(left, iova_start, iova_end) +
> +                               _vpfn_pages(right, iova_start, iova_end);
> +
> +       if (vpfn->iova >= iova_end)
> +               return _vpfn_pages(left, iova_start, iova_end);
> +
> +       return _vpfn_pages(right, iova_start, iova_end);
> +}

Recursion doesn't seem like a good fit here, the depth is practically
unbounded.  Why not just use the new range function to find the highest
point in the tree that intersects, then search each direction in
separate loops (rb_next/rb_prev), counting additional entries within
the range?  Thanks,

Alex

> +
> +static long vpfn_pages(struct vfio_dma *dma,
> +               dma_addr_t iova_start, long nr_pages)
> +{
> +       dma_addr_t iova_end = iova_start + (nr_pages << PAGE_SHIFT);
> +       struct vfio_pfn *top = vfio_find_vpfn_range(dma, iova_start, iova_end);
> +
> +       return _vpfn_pages(top, iova_start, iova_end);
> +}
> 
> Thanks,
> Zhe
>