On Tue, 27 May 2025 13:14:50 -0600, alex.williamson@xxxxxxxxxx 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;
+}
Thanks,
Zhe
