iova-tree prevents mapping of overlapping ranges, but range checks
inflate the effective size of regions by 1 byte, resulting in gaps
between regions in the iova address space.  If there are alignment
requirements for regions in the iova space, this can throw them off.

Adjust range checks to allow adjacent regions with no gap between them.

Signed-off-by: Connor Kite <connorkite@gmail.com>
---
 util/iova-tree.c | 26 +++++++++++++-------------
 1 file changed, 13 insertions(+), 13 deletions(-)

diff --git a/util/iova-tree.c b/util/iova-tree.c
index 5b0c95ff15..834ffab324 100644
--- a/util/iova-tree.c
+++ b/util/iova-tree.c
@@ -59,11 +59,11 @@ static int iova_tree_compare(gconstpointer a, gconstpointer b, gpointer data)
 {
     const DMAMap *m1 = a, *m2 = b;
 
-    if (m1->iova > m2->iova + m2->size) {
+    if (m1->iova >= m2->iova + m2->size) {
         return 1;
     }
 
-    if (m1->iova + m1->size < m2->iova) {
+    if (m1->iova + m1->size <= m2->iova) {
         return -1;
     }
 
@@ -96,8 +96,8 @@ static gboolean iova_tree_find_address_iterator(gpointer key, gpointer value,
     g_assert(key == value);
 
     needle = args->needle;
-    if (map->translated_addr + map->size < needle->translated_addr ||
-        needle->translated_addr + needle->size < map->translated_addr) {
+    if (map->translated_addr + map->size <= needle->translated_addr ||
+        needle->translated_addr + needle->size <= map->translated_addr) {
         return false;
     }
 
@@ -125,7 +125,7 @@ int iova_tree_insert(IOVATree *tree, const DMAMap *map)
 {
     DMAMap *new;
 
-    if (map->iova + map->size < map->iova || map->perm == IOMMU_NONE) {
+    if (map->iova + map->size <= map->iova || map->perm == IOMMU_NONE) {
         return IOVA_ERR_INVALID;
     }
 
@@ -174,14 +174,14 @@ static void iova_tree_alloc_map_in_hole(struct IOVATreeAllocArgs *args)
     const DMAMap *prev = args->prev, *this = args->this;
     uint64_t hole_start, hole_last;
 
-    if (this && this->iova + this->size < args->iova_begin) {
+    if (this && this->iova + this->size <= args->iova_begin) {
         return;
     }
 
-    hole_start = MAX(prev ? prev->iova + prev->size + 1 : 0, args->iova_begin);
-    hole_last = this ? this->iova : HWADDR_MAX;
+    hole_start = MAX(prev ? prev->iova + prev->size : 0, args->iova_begin);
+    hole_last = this ? this->iova - 1 : HWADDR_MAX;
 
-    if (hole_last - hole_start > args->new_size) {
+    if (hole_last - hole_start + 1 > args->new_size) {
         args->iova_result = hole_start;
         args->iova_found = true;
     }
@@ -244,7 +244,7 @@ int iova_tree_alloc_map(IOVATree *tree, DMAMap *map, hwaddr iova_begin,
         iova_tree_alloc_map_in_hole(&args);
     }
 
-    if (!args.iova_found || args.iova_result + map->size > iova_last) {
+    if (!args.iova_found || args.iova_result + map->size - 1 > iova_last) {
         return IOVA_ERR_NOMEM;
     }
 
@@ -262,11 +262,11 @@ static int gpa_tree_compare(gconstpointer a, gconstpointer b, gpointer data)
 {
     const DMAMap *m1 = a, *m2 = b;
 
-    if (m1->translated_addr > m2->translated_addr + m2->size) {
+    if (m1->translated_addr >= m2->translated_addr + m2->size) {
         return 1;
     }
 
-    if (m1->translated_addr + m1->size < m2->translated_addr) {
+    if (m1->translated_addr + m1->size <= m2->translated_addr) {
         return -1;
     }
 
@@ -287,7 +287,7 @@ int gpa_tree_insert(IOVATree *tree, const DMAMap *map)
 {
     DMAMap *new;
 
-    if (map->translated_addr + map->size < map->translated_addr ||
+    if (map->translated_addr + map->size <= map->translated_addr ||
         map->perm == IOMMU_NONE) {
         return IOVA_ERR_INVALID;
     }
-- 
2.43.0

On Wed, Jul 22, 2026 at 4:11 PM Connor Kite <connorkite@gmail.com> wrote:
>
> iova-tree prevents mapping of overlapping ranges, but range checks
> inflate the effective size of regions by 1 byte, resulting in gaps
> between regions in the iova address space.  If there are alignment
> requirements for regions in the iova space, this can throw them off.
>
> Adjust range checks to allow adjacent regions with no gap between them.
>
> Signed-off-by: Connor Kite <connorkite@gmail.com>
> ---
>  util/iova-tree.c | 26 +++++++++++++-------------
>  1 file changed, 13 insertions(+), 13 deletions(-)

I think iova-tree is fine as-is and the root cause is
vhost_svq_translate_addr() treating size as an open interval rather
than a closed interval.

The "qemu/iova-tree.h" DMAMap struct documents the size field as
"Inclusive" (i.e. closed interval where the size only goes up to the
last byte included in the interval) and the code touched in this patch
was written with that in mind.

Looking at other iova-tree users in the source tree, they all use size
- 1 (closed interval), which is consistent with the iova-tree API.

If you fix vhost_svq_translate_addr() to use a closed interval, then
no changes to iova-tree are necessary. I think this approach is
preferrable since this patch otherwise breaks the other iova-tree
users (vhost-vdpa, intel_iommu, amd_iommu).

By the way, I suspect the fundamental reason to use a closed interval
is that the entire address space can be covered (e.g. HWADDR_MAX)
using hwaddr or uint64_t. The open interval representation requires a
larger type or a special case (e.g. treating ~0 differently) to cover
the entire address space.

Stefan

Confirmed that your suggested root cause makes sense.  I did the following:
  1.   Reverted the changes to iova-tree on my end
  2.   Subtracted 1 from `needle.size` in `vhost_svq_translate_addr`
  3.   Refactored the vhost-user memory isolation code to use
inclusive size when dealing with vhost-iova-tree
  4.   Confirmed that region mapping and data transfer in isolation mode
have the same level of functionality

I was finishing up the RFC patch series for vhost-user isolation mode when
I saw your message, so I will update svq there, rendering this patch to
iova-tree unnecessary.

Thanks!
Connor

On Thu, Jul 23, 2026 at 7:05 AM Stefan Hajnoczi <stefanha@gmail.com> wrote:

> On Wed, Jul 22, 2026 at 4:11 PM Connor Kite <connorkite@gmail.com> wrote:
> >
> > iova-tree prevents mapping of overlapping ranges, but range checks
> > inflate the effective size of regions by 1 byte, resulting in gaps
> > between regions in the iova address space.  If there are alignment
> > requirements for regions in the iova space, this can throw them off.
> >
> > Adjust range checks to allow adjacent regions with no gap between them.
> >
> > Signed-off-by: Connor Kite <connorkite@gmail.com>
> > ---
> >  util/iova-tree.c | 26 +++++++++++++-------------
> >  1 file changed, 13 insertions(+), 13 deletions(-)
>
> I think iova-tree is fine as-is and the root cause is
> vhost_svq_translate_addr() treating size as an open interval rather
> than a closed interval.
>
> The "qemu/iova-tree.h" DMAMap struct documents the size field as
> "Inclusive" (i.e. closed interval where the size only goes up to the
> last byte included in the interval) and the code touched in this patch
> was written with that in mind.
>
> Looking at other iova-tree users in the source tree, they all use size
> - 1 (closed interval), which is consistent with the iova-tree API.
>
> If you fix vhost_svq_translate_addr() to use a closed interval, then
> no changes to iova-tree are necessary. I think this approach is
> preferrable since this patch otherwise breaks the other iova-tree
> users (vhost-vdpa, intel_iommu, amd_iommu).
>
> By the way, I suspect the fundamental reason to use a closed interval
> is that the entire address space can be covered (e.g. HWADDR_MAX)
> using hwaddr or uint64_t. The open interval representation requires a
> larger type or a special case (e.g. treating ~0 differently) to cover
> the entire address space.
>
> Stefan
>