Add struct iova_allocator, which gives tests a convenient way to generate
legally-accessible IOVAs to map.

This is based on Alex Williamson's patch series for adding an IOVA
allocator [1].

[1] https://lore.kernel.org/all/20251108212954.26477-1-alex@shazbot.org/

Signed-off-by: Alex Mastro <amastro@fb.com>
---
 .../testing/selftests/vfio/lib/include/vfio_util.h | 14 +++++
 tools/testing/selftests/vfio/lib/vfio_pci_device.c | 65 +++++++++++++++++++++-
 2 files changed, 78 insertions(+), 1 deletion(-)

diff --git a/tools/testing/selftests/vfio/lib/include/vfio_util.h b/tools/testing/selftests/vfio/lib/include/vfio_util.h
index fb5efec52316..bb1e7d39dfb9 100644
--- a/tools/testing/selftests/vfio/lib/include/vfio_util.h
+++ b/tools/testing/selftests/vfio/lib/include/vfio_util.h
@@ -13,6 +13,8 @@
 
 #include "../../../kselftest.h"
 
+#define ALIGN(x, a)	(((x) + (a - 1)) & (~((a) - 1)))
+
 #define VFIO_LOG_AND_EXIT(...) do {		\
 	fprintf(stderr, "  " __VA_ARGS__);	\
 	fprintf(stderr, "\n");			\
@@ -188,6 +190,13 @@ struct vfio_pci_device {
 	struct vfio_pci_driver driver;
 };
 
+struct iova_allocator {
+	struct iommu_iova_range *ranges;
+	size_t nranges;
+	size_t range_idx;
+	iova_t iova_next;
+};
+
 /*
  * Return the BDF string of the device that the test should use.
  *
@@ -212,6 +221,11 @@ void vfio_pci_device_reset(struct vfio_pci_device *device);
 struct iommu_iova_range *vfio_pci_iova_ranges(struct vfio_pci_device *device,
 					      size_t *nranges);
 
+int iova_allocator_init(struct vfio_pci_device *device,
+			    struct iova_allocator *allocator);
+void iova_allocator_deinit(struct iova_allocator *allocator);
+iova_t iova_allocator_alloc(struct iova_allocator *allocator, size_t size);
+
 int __vfio_pci_dma_map(struct vfio_pci_device *device,
 		       struct vfio_dma_region *region);
 int __vfio_pci_dma_unmap(struct vfio_pci_device *device,
diff --git a/tools/testing/selftests/vfio/lib/vfio_pci_device.c b/tools/testing/selftests/vfio/lib/vfio_pci_device.c
index 6bedbe65f0a1..a634feb1d378 100644
--- a/tools/testing/selftests/vfio/lib/vfio_pci_device.c
+++ b/tools/testing/selftests/vfio/lib/vfio_pci_device.c
@@ -12,11 +12,12 @@
 #include <sys/mman.h>
 
 #include <uapi/linux/types.h>
+#include <linux/iommufd.h>
 #include <linux/limits.h>
 #include <linux/mman.h>
+#include <linux/overflow.h>
 #include <linux/types.h>
 #include <linux/vfio.h>
-#include <linux/iommufd.h>
 
 #include "../../../kselftest.h"
 #include <vfio_util.h>
@@ -190,6 +191,68 @@ struct iommu_iova_range *vfio_pci_iova_ranges(struct vfio_pci_device *device,
 	return ranges;
 }
 
+int iova_allocator_init(struct vfio_pci_device *device,
+			struct iova_allocator *allocator)
+{
+	struct iommu_iova_range *ranges;
+	size_t nranges;
+
+	memset(allocator, 0, sizeof(*allocator));
+
+	ranges = vfio_pci_iova_ranges(device, &nranges);
+	if (!ranges)
+		return -ENOENT;
+
+	*allocator = (struct iova_allocator){
+		.ranges = ranges,
+		.nranges = nranges,
+		.range_idx = 0,
+		.iova_next = 0,
+	};
+
+	return 0;
+}
+
+void iova_allocator_deinit(struct iova_allocator *allocator)
+{
+	free(allocator->ranges);
+}
+
+iova_t iova_allocator_alloc(struct iova_allocator *allocator, size_t size)
+{
+	int idx = allocator->range_idx;
+	struct iommu_iova_range *range = &allocator->ranges[idx];
+
+	VFIO_ASSERT_LT(idx, allocator->nranges, "IOVA allocator out of space\n");
+	VFIO_ASSERT_GT(size, 0, "Invalid size arg, zero\n");
+	VFIO_ASSERT_EQ(size & (size - 1), 0, "Invalid size arg, non-power-of-2\n");
+
+	for (;;) {
+		iova_t iova, last;
+
+		iova = ALIGN(allocator->iova_next, size);
+
+		if (iova < allocator->iova_next || iova > range->last ||
+		    check_add_overflow(iova, size - 1, &last) ||
+		    last > range->last) {
+			allocator->range_idx = ++idx;
+			VFIO_ASSERT_LT(idx, allocator->nranges,
+				       "Out of ranges for allocation\n");
+			allocator->iova_next = (++range)->start;
+			continue;
+		}
+
+		if (check_add_overflow(last, (iova_t)1, &allocator->iova_next) ||
+		    allocator->iova_next > range->last) {
+			allocator->range_idx = ++idx;
+			if (idx < allocator->nranges)
+				allocator->iova_next = (++range)->start;
+		}
+
+		return iova;
+	}
+}
+
 iova_t __to_iova(struct vfio_pci_device *device, void *vaddr)
 {
 	struct vfio_dma_region *region;

-- 
2.47.3

On 2025-11-10 01:10 PM, Alex Mastro wrote:
> Add struct iova_allocator, which gives tests a convenient way to generate
> legally-accessible IOVAs to map.
> 
> This is based on Alex Williamson's patch series for adding an IOVA
> allocator [1].
> 
> [1] https://lore.kernel.org/all/20251108212954.26477-1-alex@shazbot.org/
> 
> Signed-off-by: Alex Mastro <amastro@fb.com>
> ---
>  .../testing/selftests/vfio/lib/include/vfio_util.h | 14 +++++
>  tools/testing/selftests/vfio/lib/vfio_pci_device.c | 65 +++++++++++++++++++++-
>  2 files changed, 78 insertions(+), 1 deletion(-)
> 
> diff --git a/tools/testing/selftests/vfio/lib/include/vfio_util.h b/tools/testing/selftests/vfio/lib/include/vfio_util.h
> index fb5efec52316..bb1e7d39dfb9 100644
> --- a/tools/testing/selftests/vfio/lib/include/vfio_util.h
> +++ b/tools/testing/selftests/vfio/lib/include/vfio_util.h
> @@ -13,6 +13,8 @@
>  
>  #include "../../../kselftest.h"
>  
> +#define ALIGN(x, a)	(((x) + (a - 1)) & (~((a) - 1)))

Please name this ALIGN_UP() so that it is clear it aligns x up and not
down.

> +
>  #define VFIO_LOG_AND_EXIT(...) do {		\
>  	fprintf(stderr, "  " __VA_ARGS__);	\
>  	fprintf(stderr, "\n");			\
> @@ -188,6 +190,13 @@ struct vfio_pci_device {
>  	struct vfio_pci_driver driver;
>  };
>  
> +struct iova_allocator {
> +	struct iommu_iova_range *ranges;
> +	size_t nranges;
> +	size_t range_idx;
> +	iova_t iova_next;
> +};
> +
>  /*
>   * Return the BDF string of the device that the test should use.
>   *
> @@ -212,6 +221,11 @@ void vfio_pci_device_reset(struct vfio_pci_device *device);
>  struct iommu_iova_range *vfio_pci_iova_ranges(struct vfio_pci_device *device,
>  					      size_t *nranges);
>  
> +int iova_allocator_init(struct vfio_pci_device *device,
> +			    struct iova_allocator *allocator);
> +void iova_allocator_deinit(struct iova_allocator *allocator);
> +iova_t iova_allocator_alloc(struct iova_allocator *allocator, size_t size);
> +
>  int __vfio_pci_dma_map(struct vfio_pci_device *device,
>  		       struct vfio_dma_region *region);
>  int __vfio_pci_dma_unmap(struct vfio_pci_device *device,
> diff --git a/tools/testing/selftests/vfio/lib/vfio_pci_device.c b/tools/testing/selftests/vfio/lib/vfio_pci_device.c
> index 6bedbe65f0a1..a634feb1d378 100644
> --- a/tools/testing/selftests/vfio/lib/vfio_pci_device.c
> +++ b/tools/testing/selftests/vfio/lib/vfio_pci_device.c
> @@ -12,11 +12,12 @@
>  #include <sys/mman.h>
>  
>  #include <uapi/linux/types.h>
> +#include <linux/iommufd.h>
>  #include <linux/limits.h>
>  #include <linux/mman.h>
> +#include <linux/overflow.h>
>  #include <linux/types.h>
>  #include <linux/vfio.h>
> -#include <linux/iommufd.h>
>  
>  #include "../../../kselftest.h"
>  #include <vfio_util.h>
> @@ -190,6 +191,68 @@ struct iommu_iova_range *vfio_pci_iova_ranges(struct vfio_pci_device *device,
>  	return ranges;
>  }
>  
> +int iova_allocator_init(struct vfio_pci_device *device,
> +			struct iova_allocator *allocator)
> +{
> +	struct iommu_iova_range *ranges;
> +	size_t nranges;
> +
> +	memset(allocator, 0, sizeof(*allocator));
> +
> +	ranges = vfio_pci_iova_ranges(device, &nranges);
> +	if (!ranges)
> +		return -ENOENT;
> +
> +	*allocator = (struct iova_allocator){
> +		.ranges = ranges,
> +		.nranges = nranges,
> +		.range_idx = 0,
> +		.iova_next = 0,
> +	};
> +
> +	return 0;
> +}
> +
> +void iova_allocator_deinit(struct iova_allocator *allocator)
> +{
> +	free(allocator->ranges);
> +}

I think it would be good to be consistent about how the library hands
out and initializes objects. e.g. For devices we have:

  device = vfio_pci_device_init(...);
  vfio_pci_device_cleanup(device);

So for allocator it would be:

  allocator = iova_allocator_init();
  iova_allocator_cleanup(allocator);

It's a small thing, but this way users of the library can always work
with pointers allocated by the library, there is a consistent meaning of
*_init() functions, and one doesn't have to distinguish between
*_deinit() and *_cleanup().

Forcing dynamic memory allocation is less efficient, but I think
simplicity and consistency matters more when it comes to tests.

> +
> +iova_t iova_allocator_alloc(struct iova_allocator *allocator, size_t size)
> +{
> +	int idx = allocator->range_idx;
> +	struct iommu_iova_range *range = &allocator->ranges[idx];
> +
> +	VFIO_ASSERT_LT(idx, allocator->nranges, "IOVA allocator out of space\n");
> +	VFIO_ASSERT_GT(size, 0, "Invalid size arg, zero\n");
> +	VFIO_ASSERT_EQ(size & (size - 1), 0, "Invalid size arg, non-power-of-2\n");

ALIGN() is what requires size to be a power of 2, so the assert should
probably go inside that macro.

> +
> +	for (;;) {
> +		iova_t iova, last;
> +
> +		iova = ALIGN(allocator->iova_next, size);
> +
> +		if (iova < allocator->iova_next || iova > range->last ||
> +		    check_add_overflow(iova, size - 1, &last) ||
> +		    last > range->last) {
> +			allocator->range_idx = ++idx;
> +			VFIO_ASSERT_LT(idx, allocator->nranges,
> +				       "Out of ranges for allocation\n");
> +			allocator->iova_next = (++range)->start;
> +			continue;
> +		}
> +
> +		if (check_add_overflow(last, (iova_t)1, &allocator->iova_next) ||
> +		    allocator->iova_next > range->last) {
> +			allocator->range_idx = ++idx;
> +			if (idx < allocator->nranges)
> +				allocator->iova_next = (++range)->start;
> +		}
> +
> +		return iova;
> +	}

I found this loop a bit hard to read. The if statements have 3-4
statements, and idx and range are managed deep in the loop. What about
something like this? It also avoids the need to check for overflow
(unless I missed something :).

diff --git a/tools/testing/selftests/vfio/lib/include/vfio_util.h b/tools/testing/selftests/vfio/lib/include/vfio_util.h
index bb1e7d39dfb9..63fce0ffe287 100644
--- a/tools/testing/selftests/vfio/lib/include/vfio_util.h
+++ b/tools/testing/selftests/vfio/lib/include/vfio_util.h
@@ -193,8 +193,10 @@ struct vfio_pci_device {
 struct iova_allocator {
 	struct iommu_iova_range *ranges;
 	size_t nranges;
+
+	/* The next range, and offset within it, from which to allocate. */
 	size_t range_idx;
-	iova_t iova_next;
+	iova_t range_offset;
 };

 /*
diff --git a/tools/testing/selftests/vfio/lib/vfio_pci_device.c b/tools/testing/selftests/vfio/lib/vfio_pci_device.c
index a634feb1d378..5b85005c4544 100644
--- a/tools/testing/selftests/vfio/lib/vfio_pci_device.c
+++ b/tools/testing/selftests/vfio/lib/vfio_pci_device.c
@@ -207,7 +207,7 @@ int iova_allocator_init(struct vfio_pci_device *device,
 		.ranges = ranges,
 		.nranges = nranges,
 		.range_idx = 0,
-		.iova_next = 0,
+		.range_offset = 0,
 	};

 	return 0;
@@ -220,37 +220,41 @@ void iova_allocator_deinit(struct iova_allocator *allocator)

 iova_t iova_allocator_alloc(struct iova_allocator *allocator, size_t size)
 {
-	int idx = allocator->range_idx;
-	struct iommu_iova_range *range = &allocator->ranges[idx];
+	int idx;

-	VFIO_ASSERT_LT(idx, allocator->nranges, "IOVA allocator out of space\n");
 	VFIO_ASSERT_GT(size, 0, "Invalid size arg, zero\n");
 	VFIO_ASSERT_EQ(size & (size - 1), 0, "Invalid size arg, non-power-of-2\n");

-	for (;;) {
+	for (idx = allocator->range_idx; idx < allocator->nranges; idx++) {
+		struct iommu_iova_range *range = &allocator->ranges[idx];
 		iova_t iova, last;

-		iova = ALIGN(allocator->iova_next, size);
+		if (idx == allocator->range_idx)
+			iova = ALIGN(range->start + allocator->range_offset, size);
+		else
+			iova = ALIGN(range->start, size);

-		if (iova < allocator->iova_next || iova > range->last ||
-		    check_add_overflow(iova, size - 1, &last) ||
-		    last > range->last) {
-			allocator->range_idx = ++idx;
-			VFIO_ASSERT_LT(idx, allocator->nranges,
-				       "Out of ranges for allocation\n");
-			allocator->iova_next = (++range)->start;
+		if (range->last - iova + 1 < size)
 			continue;
-		}

-		if (check_add_overflow(last, (iova_t)1, &allocator->iova_next) ||
-		    allocator->iova_next > range->last) {
-			allocator->range_idx = ++idx;
-			if (idx < allocator->nranges)
-				allocator->iova_next = (++range)->start;
+		/*
+		 * Found a range to hold the allocation. Update the allocator
+		 * for the next allocation.
+		 */
+		last = iova + (size - 1);
+
+		if (last < range->last) {
+			allocator->range_idx = idx;
+			allocator->range_offset = last - range->start + 1;
+		} else {
+			allocator->range_idx = idx + 1;
+			allocator->range_offset = 0;
 		}

 		return iova;
 	}
+
+	VFIO_FAIL("Failed to iova range of size 0x%lx\n", size);
 }

 iova_t __to_iova(struct vfio_pci_device *device, void *vaddr)

> +}
> +
>  iova_t __to_iova(struct vfio_pci_device *device, void *vaddr)
>  {
>  	struct vfio_dma_region *region;
> 
> -- 
> 2.47.3
>

On Mon, Nov 10, 2025 at 10:54:04PM +0000, David Matlack wrote:
> On 2025-11-10 01:10 PM, Alex Mastro wrote:
> > Add struct iova_allocator, which gives tests a convenient way to generate
> > legally-accessible IOVAs to map.
> > 
> > This is based on Alex Williamson's patch series for adding an IOVA
> > allocator [1].
> > 
> > [1] https://lore.kernel.org/all/20251108212954.26477-1-alex@shazbot.org/
> > 
> > Signed-off-by: Alex Mastro <amastro@fb.com>
> > ---
> >  .../testing/selftests/vfio/lib/include/vfio_util.h | 14 +++++
> >  tools/testing/selftests/vfio/lib/vfio_pci_device.c | 65 +++++++++++++++++++++-
> >  2 files changed, 78 insertions(+), 1 deletion(-)
> > 
> > diff --git a/tools/testing/selftests/vfio/lib/include/vfio_util.h b/tools/testing/selftests/vfio/lib/include/vfio_util.h
> > index fb5efec52316..bb1e7d39dfb9 100644
> > --- a/tools/testing/selftests/vfio/lib/include/vfio_util.h
> > +++ b/tools/testing/selftests/vfio/lib/include/vfio_util.h
> > @@ -13,6 +13,8 @@
> >  
> >  #include "../../../kselftest.h"
> >  
> > +#define ALIGN(x, a)	(((x) + (a - 1)) & (~((a) - 1)))
> 
> Please name this ALIGN_UP() so that it is clear it aligns x up and not
> down.

Ack.

> > +
> >  #define VFIO_LOG_AND_EXIT(...) do {		\
> >  	fprintf(stderr, "  " __VA_ARGS__);	\
> >  	fprintf(stderr, "\n");			\
> > @@ -188,6 +190,13 @@ struct vfio_pci_device {
> >  	struct vfio_pci_driver driver;
> >  };
> >  
> > +struct iova_allocator {
> > +	struct iommu_iova_range *ranges;
> > +	size_t nranges;
> > +	size_t range_idx;
> > +	iova_t iova_next;
> > +};
> > +
> >  /*
> >   * Return the BDF string of the device that the test should use.
> >   *
> > @@ -212,6 +221,11 @@ void vfio_pci_device_reset(struct vfio_pci_device *device);
> >  struct iommu_iova_range *vfio_pci_iova_ranges(struct vfio_pci_device *device,
> >  					      size_t *nranges);
> >  
> > +int iova_allocator_init(struct vfio_pci_device *device,
> > +			    struct iova_allocator *allocator);
> > +void iova_allocator_deinit(struct iova_allocator *allocator);
> > +iova_t iova_allocator_alloc(struct iova_allocator *allocator, size_t size);
> > +
> >  int __vfio_pci_dma_map(struct vfio_pci_device *device,
> >  		       struct vfio_dma_region *region);
> >  int __vfio_pci_dma_unmap(struct vfio_pci_device *device,
> > diff --git a/tools/testing/selftests/vfio/lib/vfio_pci_device.c b/tools/testing/selftests/vfio/lib/vfio_pci_device.c
> > index 6bedbe65f0a1..a634feb1d378 100644
> > --- a/tools/testing/selftests/vfio/lib/vfio_pci_device.c
> > +++ b/tools/testing/selftests/vfio/lib/vfio_pci_device.c
> > @@ -12,11 +12,12 @@
> >  #include <sys/mman.h>
> >  
> >  #include <uapi/linux/types.h>
> > +#include <linux/iommufd.h>
> >  #include <linux/limits.h>
> >  #include <linux/mman.h>
> > +#include <linux/overflow.h>
> >  #include <linux/types.h>
> >  #include <linux/vfio.h>
> > -#include <linux/iommufd.h>
> >  
> >  #include "../../../kselftest.h"
> >  #include <vfio_util.h>
> > @@ -190,6 +191,68 @@ struct iommu_iova_range *vfio_pci_iova_ranges(struct vfio_pci_device *device,
> >  	return ranges;
> >  }
> >  
> > +int iova_allocator_init(struct vfio_pci_device *device,
> > +			struct iova_allocator *allocator)
> > +{
> > +	struct iommu_iova_range *ranges;
> > +	size_t nranges;
> > +
> > +	memset(allocator, 0, sizeof(*allocator));
> > +
> > +	ranges = vfio_pci_iova_ranges(device, &nranges);
> > +	if (!ranges)
> > +		return -ENOENT;
> > +
> > +	*allocator = (struct iova_allocator){
> > +		.ranges = ranges,
> > +		.nranges = nranges,
> > +		.range_idx = 0,
> > +		.iova_next = 0,
> > +	};
> > +
> > +	return 0;
> > +}
> > +
> > +void iova_allocator_deinit(struct iova_allocator *allocator)
> > +{
> > +	free(allocator->ranges);
> > +}
> 
> I think it would be good to be consistent about how the library hands
> out and initializes objects. e.g. For devices we have:
> 
>   device = vfio_pci_device_init(...);
>   vfio_pci_device_cleanup(device);
> 
> So for allocator it would be:
> 
>   allocator = iova_allocator_init();
>   iova_allocator_cleanup(allocator);
> 
> It's a small thing, but this way users of the library can always work
> with pointers allocated by the library, there is a consistent meaning of
> *_init() functions, and one doesn't have to distinguish between
> *_deinit() and *_cleanup().
> 
> Forcing dynamic memory allocation is less efficient, but I think
> simplicity and consistency matters more when it comes to tests.

SGTM -- will change it to be like how you suggested for consistency.

> 
> > +
> > +iova_t iova_allocator_alloc(struct iova_allocator *allocator, size_t size)
> > +{
> > +	int idx = allocator->range_idx;
> > +	struct iommu_iova_range *range = &allocator->ranges[idx];
> > +
> > +	VFIO_ASSERT_LT(idx, allocator->nranges, "IOVA allocator out of space\n");
> > +	VFIO_ASSERT_GT(size, 0, "Invalid size arg, zero\n");
> > +	VFIO_ASSERT_EQ(size & (size - 1), 0, "Invalid size arg, non-power-of-2\n");
> 
> ALIGN() is what requires size to be a power of 2, so the assert should
> probably go inside that macro.

SGTM

> 
> > +
> > +	for (;;) {
> > +		iova_t iova, last;
> > +
> > +		iova = ALIGN(allocator->iova_next, size);
> > +
> > +		if (iova < allocator->iova_next || iova > range->last ||
> > +		    check_add_overflow(iova, size - 1, &last) ||
> > +		    last > range->last) {
> > +			allocator->range_idx = ++idx;
> > +			VFIO_ASSERT_LT(idx, allocator->nranges,
> > +				       "Out of ranges for allocation\n");
> > +			allocator->iova_next = (++range)->start;
> > +			continue;
> > +		}
> > +
> > +		if (check_add_overflow(last, (iova_t)1, &allocator->iova_next) ||
> > +		    allocator->iova_next > range->last) {
> > +			allocator->range_idx = ++idx;
> > +			if (idx < allocator->nranges)
> > +				allocator->iova_next = (++range)->start;
> > +		}
> > +
> > +		return iova;
> > +	}
> 
> I found this loop a bit hard to read. The if statements have 3-4
> statements, and idx and range are managed deep in the loop. What about
> something like this? It also avoids the need to check for overflow
> (unless I missed something :).

I'll take a closer look at your suggestions. Agree that it's terse. I
shamelessly lifted this verbatim from AlexW's patch, and it seemed ok from my
first pass squinting.

> 
> diff --git a/tools/testing/selftests/vfio/lib/include/vfio_util.h b/tools/testing/selftests/vfio/lib/include/vfio_util.h
> index bb1e7d39dfb9..63fce0ffe287 100644
> --- a/tools/testing/selftests/vfio/lib/include/vfio_util.h
> +++ b/tools/testing/selftests/vfio/lib/include/vfio_util.h
> @@ -193,8 +193,10 @@ struct vfio_pci_device {
>  struct iova_allocator {
>  	struct iommu_iova_range *ranges;
>  	size_t nranges;
> +
> +	/* The next range, and offset within it, from which to allocate. */
>  	size_t range_idx;
> -	iova_t iova_next;
> +	iova_t range_offset;
>  };
> 
>  /*
> diff --git a/tools/testing/selftests/vfio/lib/vfio_pci_device.c b/tools/testing/selftests/vfio/lib/vfio_pci_device.c
> index a634feb1d378..5b85005c4544 100644
> --- a/tools/testing/selftests/vfio/lib/vfio_pci_device.c
> +++ b/tools/testing/selftests/vfio/lib/vfio_pci_device.c
> @@ -207,7 +207,7 @@ int iova_allocator_init(struct vfio_pci_device *device,
>  		.ranges = ranges,
>  		.nranges = nranges,
>  		.range_idx = 0,
> -		.iova_next = 0,
> +		.range_offset = 0,
>  	};
> 
>  	return 0;
> @@ -220,37 +220,41 @@ void iova_allocator_deinit(struct iova_allocator *allocator)
> 
>  iova_t iova_allocator_alloc(struct iova_allocator *allocator, size_t size)
>  {
> -	int idx = allocator->range_idx;
> -	struct iommu_iova_range *range = &allocator->ranges[idx];
> +	int idx;
> 
> -	VFIO_ASSERT_LT(idx, allocator->nranges, "IOVA allocator out of space\n");
>  	VFIO_ASSERT_GT(size, 0, "Invalid size arg, zero\n");
>  	VFIO_ASSERT_EQ(size & (size - 1), 0, "Invalid size arg, non-power-of-2\n");
> 
> -	for (;;) {
> +	for (idx = allocator->range_idx; idx < allocator->nranges; idx++) {
> +		struct iommu_iova_range *range = &allocator->ranges[idx];
>  		iova_t iova, last;
> 
> -		iova = ALIGN(allocator->iova_next, size);
> +		if (idx == allocator->range_idx)
> +			iova = ALIGN(range->start + allocator->range_offset, size);
> +		else
> +			iova = ALIGN(range->start, size);
> 
> -		if (iova < allocator->iova_next || iova > range->last ||
> -		    check_add_overflow(iova, size - 1, &last) ||
> -		    last > range->last) {
> -			allocator->range_idx = ++idx;
> -			VFIO_ASSERT_LT(idx, allocator->nranges,
> -				       "Out of ranges for allocation\n");
> -			allocator->iova_next = (++range)->start;
> +		if (range->last - iova + 1 < size)
>  			continue;
> -		}
> 
> -		if (check_add_overflow(last, (iova_t)1, &allocator->iova_next) ||
> -		    allocator->iova_next > range->last) {
> -			allocator->range_idx = ++idx;
> -			if (idx < allocator->nranges)
> -				allocator->iova_next = (++range)->start;
> +		/*
> +		 * Found a range to hold the allocation. Update the allocator
> +		 * for the next allocation.
> +		 */
> +		last = iova + (size - 1);
> +
> +		if (last < range->last) {
> +			allocator->range_idx = idx;
> +			allocator->range_offset = last - range->start + 1;
> +		} else {
> +			allocator->range_idx = idx + 1;
> +			allocator->range_offset = 0;
>  		}
> 
>  		return iova;
>  	}
> +
> +	VFIO_FAIL("Failed to iova range of size 0x%lx\n", size);
>  }
> 
>  iova_t __to_iova(struct vfio_pci_device *device, void *vaddr)
> 
> > +}
> > +
> >  iova_t __to_iova(struct vfio_pci_device *device, void *vaddr)
> >  {
> >  	struct vfio_dma_region *region;
> > 
> > -- 
> > 2.47.3
> >

On Mon, 10 Nov 2025 13:10:43 -0800
Alex Mastro <amastro@fb.com> wrote:

> Add struct iova_allocator, which gives tests a convenient way to generate
> legally-accessible IOVAs to map.
> 
> This is based on Alex Williamson's patch series for adding an IOVA
> allocator [1].
> 
> [1] https://lore.kernel.org/all/20251108212954.26477-1-alex@shazbot.org/
> 
> Signed-off-by: Alex Mastro <amastro@fb.com>
> ---
>  .../testing/selftests/vfio/lib/include/vfio_util.h | 14 +++++
>  tools/testing/selftests/vfio/lib/vfio_pci_device.c | 65 +++++++++++++++++++++-
>  2 files changed, 78 insertions(+), 1 deletion(-)
> 
> diff --git a/tools/testing/selftests/vfio/lib/include/vfio_util.h b/tools/testing/selftests/vfio/lib/include/vfio_util.h
> index fb5efec52316..bb1e7d39dfb9 100644
> --- a/tools/testing/selftests/vfio/lib/include/vfio_util.h
> +++ b/tools/testing/selftests/vfio/lib/include/vfio_util.h
> @@ -13,6 +13,8 @@
>  
>  #include "../../../kselftest.h"
>  
> +#define ALIGN(x, a)	(((x) + (a - 1)) & (~((a) - 1)))
> +
>  #define VFIO_LOG_AND_EXIT(...) do {		\
>  	fprintf(stderr, "  " __VA_ARGS__);	\
>  	fprintf(stderr, "\n");			\
> @@ -188,6 +190,13 @@ struct vfio_pci_device {
>  	struct vfio_pci_driver driver;
>  };
>  
> +struct iova_allocator {
> +	struct iommu_iova_range *ranges;
> +	size_t nranges;
> +	size_t range_idx;
> +	iova_t iova_next;
> +};
> +
>  /*
>   * Return the BDF string of the device that the test should use.
>   *
> @@ -212,6 +221,11 @@ void vfio_pci_device_reset(struct vfio_pci_device *device);
>  struct iommu_iova_range *vfio_pci_iova_ranges(struct vfio_pci_device *device,
>  					      size_t *nranges);
>  
> +int iova_allocator_init(struct vfio_pci_device *device,
> +			    struct iova_allocator *allocator);
> +void iova_allocator_deinit(struct iova_allocator *allocator);
> +iova_t iova_allocator_alloc(struct iova_allocator *allocator, size_t size);
> +
>  int __vfio_pci_dma_map(struct vfio_pci_device *device,
>  		       struct vfio_dma_region *region);
>  int __vfio_pci_dma_unmap(struct vfio_pci_device *device,
> diff --git a/tools/testing/selftests/vfio/lib/vfio_pci_device.c b/tools/testing/selftests/vfio/lib/vfio_pci_device.c
> index 6bedbe65f0a1..a634feb1d378 100644
> --- a/tools/testing/selftests/vfio/lib/vfio_pci_device.c
> +++ b/tools/testing/selftests/vfio/lib/vfio_pci_device.c
> @@ -12,11 +12,12 @@
>  #include <sys/mman.h>
>  
>  #include <uapi/linux/types.h>
> +#include <linux/iommufd.h>
>  #include <linux/limits.h>
>  #include <linux/mman.h>
> +#include <linux/overflow.h>
>  #include <linux/types.h>
>  #include <linux/vfio.h>
> -#include <linux/iommufd.h>
>  
>  #include "../../../kselftest.h"
>  #include <vfio_util.h>
> @@ -190,6 +191,68 @@ struct iommu_iova_range *vfio_pci_iova_ranges(struct vfio_pci_device *device,
>  	return ranges;
>  }
>  
> +int iova_allocator_init(struct vfio_pci_device *device,
> +			struct iova_allocator *allocator)
> +{
> +	struct iommu_iova_range *ranges;
> +	size_t nranges;
> +
> +	memset(allocator, 0, sizeof(*allocator));
> +
> +	ranges = vfio_pci_iova_ranges(device, &nranges);
> +	if (!ranges)
> +		return -ENOENT;
> +
> +	*allocator = (struct iova_allocator){
> +		.ranges = ranges,
> +		.nranges = nranges,
> +		.range_idx = 0,
> +		.iova_next = 0,

iova_next needs to be initialized from ranges[0].start.  Thanks,

Alex

> +	};
> +
> +	return 0;
> +}
> +
> +void iova_allocator_deinit(struct iova_allocator *allocator)
> +{
> +	free(allocator->ranges);
> +}
> +
> +iova_t iova_allocator_alloc(struct iova_allocator *allocator, size_t size)
> +{
> +	int idx = allocator->range_idx;
> +	struct iommu_iova_range *range = &allocator->ranges[idx];
> +
> +	VFIO_ASSERT_LT(idx, allocator->nranges, "IOVA allocator out of space\n");
> +	VFIO_ASSERT_GT(size, 0, "Invalid size arg, zero\n");
> +	VFIO_ASSERT_EQ(size & (size - 1), 0, "Invalid size arg, non-power-of-2\n");
> +
> +	for (;;) {
> +		iova_t iova, last;
> +
> +		iova = ALIGN(allocator->iova_next, size);
> +
> +		if (iova < allocator->iova_next || iova > range->last ||
> +		    check_add_overflow(iova, size - 1, &last) ||
> +		    last > range->last) {
> +			allocator->range_idx = ++idx;
> +			VFIO_ASSERT_LT(idx, allocator->nranges,
> +				       "Out of ranges for allocation\n");
> +			allocator->iova_next = (++range)->start;
> +			continue;
> +		}
> +
> +		if (check_add_overflow(last, (iova_t)1, &allocator->iova_next) ||
> +		    allocator->iova_next > range->last) {
> +			allocator->range_idx = ++idx;
> +			if (idx < allocator->nranges)
> +				allocator->iova_next = (++range)->start;
> +		}
> +
> +		return iova;
> +	}
> +}
> +
>  iova_t __to_iova(struct vfio_pci_device *device, void *vaddr)
>  {
>  	struct vfio_dma_region *region;
>

On Mon, Nov 10, 2025 at 02:31:54PM -0700, Alex Williamson wrote:
> On Mon, 10 Nov 2025 13:10:43 -0800
> Alex Mastro <amastro@fb.com> wrote:
> 
> > Add struct iova_allocator, which gives tests a convenient way to generate
> > legally-accessible IOVAs to map.
> > 
> > This is based on Alex Williamson's patch series for adding an IOVA
> > allocator [1].
> > 
> > [1] https://lore.kernel.org/all/20251108212954.26477-1-alex@shazbot.org/
> > 
> > Signed-off-by: Alex Mastro <amastro@fb.com>
> > ---
> >  .../testing/selftests/vfio/lib/include/vfio_util.h | 14 +++++
> >  tools/testing/selftests/vfio/lib/vfio_pci_device.c | 65 +++++++++++++++++++++-
> >  2 files changed, 78 insertions(+), 1 deletion(-)
> > 
> > diff --git a/tools/testing/selftests/vfio/lib/include/vfio_util.h b/tools/testing/selftests/vfio/lib/include/vfio_util.h
> > index fb5efec52316..bb1e7d39dfb9 100644
> > --- a/tools/testing/selftests/vfio/lib/include/vfio_util.h
> > +++ b/tools/testing/selftests/vfio/lib/include/vfio_util.h
> > @@ -13,6 +13,8 @@
> >  
> >  #include "../../../kselftest.h"
> >  
> > +#define ALIGN(x, a)	(((x) + (a - 1)) & (~((a) - 1)))
> > +
> >  #define VFIO_LOG_AND_EXIT(...) do {		\
> >  	fprintf(stderr, "  " __VA_ARGS__);	\
> >  	fprintf(stderr, "\n");			\
> > @@ -188,6 +190,13 @@ struct vfio_pci_device {
> >  	struct vfio_pci_driver driver;
> >  };
> >  
> > +struct iova_allocator {
> > +	struct iommu_iova_range *ranges;
> > +	size_t nranges;
> > +	size_t range_idx;
> > +	iova_t iova_next;
> > +};
> > +
> >  /*
> >   * Return the BDF string of the device that the test should use.
> >   *
> > @@ -212,6 +221,11 @@ void vfio_pci_device_reset(struct vfio_pci_device *device);
> >  struct iommu_iova_range *vfio_pci_iova_ranges(struct vfio_pci_device *device,
> >  					      size_t *nranges);
> >  
> > +int iova_allocator_init(struct vfio_pci_device *device,
> > +			    struct iova_allocator *allocator);
> > +void iova_allocator_deinit(struct iova_allocator *allocator);
> > +iova_t iova_allocator_alloc(struct iova_allocator *allocator, size_t size);
> > +
> >  int __vfio_pci_dma_map(struct vfio_pci_device *device,
> >  		       struct vfio_dma_region *region);
> >  int __vfio_pci_dma_unmap(struct vfio_pci_device *device,
> > diff --git a/tools/testing/selftests/vfio/lib/vfio_pci_device.c b/tools/testing/selftests/vfio/lib/vfio_pci_device.c
> > index 6bedbe65f0a1..a634feb1d378 100644
> > --- a/tools/testing/selftests/vfio/lib/vfio_pci_device.c
> > +++ b/tools/testing/selftests/vfio/lib/vfio_pci_device.c
> > @@ -12,11 +12,12 @@
> >  #include <sys/mman.h>
> >  
> >  #include <uapi/linux/types.h>
> > +#include <linux/iommufd.h>
> >  #include <linux/limits.h>
> >  #include <linux/mman.h>
> > +#include <linux/overflow.h>
> >  #include <linux/types.h>
> >  #include <linux/vfio.h>
> > -#include <linux/iommufd.h>
> >  
> >  #include "../../../kselftest.h"
> >  #include <vfio_util.h>
> > @@ -190,6 +191,68 @@ struct iommu_iova_range *vfio_pci_iova_ranges(struct vfio_pci_device *device,
> >  	return ranges;
> >  }
> >  
> > +int iova_allocator_init(struct vfio_pci_device *device,
> > +			struct iova_allocator *allocator)
> > +{
> > +	struct iommu_iova_range *ranges;
> > +	size_t nranges;
> > +
> > +	memset(allocator, 0, sizeof(*allocator));
> > +
> > +	ranges = vfio_pci_iova_ranges(device, &nranges);
> > +	if (!ranges)
> > +		return -ENOENT;
> > +
> > +	*allocator = (struct iova_allocator){
> > +		.ranges = ranges,
> > +		.nranges = nranges,
> > +		.range_idx = 0,
> > +		.iova_next = 0,
> 
> iova_next needs to be initialized from ranges[0].start.  Thanks,

True. Thanks for catching this.

> Alex
> 
> > +	};
> > +
> > +	return 0;
> > +}
> > +
> > +void iova_allocator_deinit(struct iova_allocator *allocator)
> > +{
> > +	free(allocator->ranges);
> > +}
> > +
> > +iova_t iova_allocator_alloc(struct iova_allocator *allocator, size_t size)
> > +{
> > +	int idx = allocator->range_idx;
> > +	struct iommu_iova_range *range = &allocator->ranges[idx];
> > +
> > +	VFIO_ASSERT_LT(idx, allocator->nranges, "IOVA allocator out of space\n");
> > +	VFIO_ASSERT_GT(size, 0, "Invalid size arg, zero\n");
> > +	VFIO_ASSERT_EQ(size & (size - 1), 0, "Invalid size arg, non-power-of-2\n");
> > +
> > +	for (;;) {
> > +		iova_t iova, last;
> > +
> > +		iova = ALIGN(allocator->iova_next, size);
> > +
> > +		if (iova < allocator->iova_next || iova > range->last ||
> > +		    check_add_overflow(iova, size - 1, &last) ||
> > +		    last > range->last) {
> > +			allocator->range_idx = ++idx;
> > +			VFIO_ASSERT_LT(idx, allocator->nranges,
> > +				       "Out of ranges for allocation\n");
> > +			allocator->iova_next = (++range)->start;
> > +			continue;
> > +		}
> > +
> > +		if (check_add_overflow(last, (iova_t)1, &allocator->iova_next) ||
> > +		    allocator->iova_next > range->last) {
> > +			allocator->range_idx = ++idx;
> > +			if (idx < allocator->nranges)
> > +				allocator->iova_next = (++range)->start;
> > +		}
> > +
> > +		return iova;
> > +	}
> > +}
> > +
> >  iova_t __to_iova(struct vfio_pci_device *device, void *vaddr)
> >  {
> >  	struct vfio_dma_region *region;
> > 
>