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

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

On Wed, 28 May 2025 12:21:24 +0800
lizhe.67@bytedance.com wrote:

> On Tue, 27 May 2025 13:14:50 -0600, alex.williamson@redhat.com wrote: 
> 
> > > 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  
> 
> Oh, I see what you mean. So the implementation of vpfn_pages() might be
> something like this.
> 
> +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);
> +       long ret = 1;
> +       struct vfio_pfn *vpfn;
> +       struct rb_node *prev;
> +       struct rb_node *next;
> +
> +       if (likely(!top))
> +               return 0;
> +
> +       prev = next = &top->node;
> +
> +       while ((prev = rb_prev(prev))) {
> +               vpfn = rb_entry(prev, struct vfio_pfn, node);
> +               if (vpfn->iova < iova_start)
> +                       break;
> +               ret++;
> +       }
> +
> +       while ((next = rb_next(next))) {
> +               vpfn = rb_entry(next, struct vfio_pfn, node);
> +               if (vpfn->iova >= iova_end)
> +                       break;
> +               ret++;
> +       }
> +
> +       return ret;
> +}

Yes, that looks like it should work to me.  Thanks,

Alex