From nobody Sat Jul 25 07:27:27 2026 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass(p=none dis=none) header.from=gmail.com ARC-Seal: i=1; a=rsa-sha256; t=1784751083; cv=none; d=zohomail.com; s=zohoarc; b=bxSryFT1n+6iwEBqGHSQ0cGMoxgloHfovlwBpqv/3TcN3PoYW9I4duJ28LRW8e7MJZtIf2rVrogSO/wbh2P4swVDxY9yxTDU5gguGcRWxDZzV/6MLoJh2K02a46SFWU81RwKhx/7ZVDb8fOgzlaT5SZp/x3Iy0BUsBUcgN1nrTI= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1784751083; h=Content-Transfer-Encoding:Cc:Cc:Date:Date:From:From:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:Sender:Subject:Subject:To:To:Message-Id:Reply-To; bh=YOILP0Pnl+nB+lm+CUiKOOV4KZnWh2wtQlwbvvyjiNg=; b=WcqTwR2bIbY0qPjvSCA5F5PiZoTlwFakLGoEGsMkCEAIs3AaPEZQQg7VyEd+g2Y5njG4mEVwafgRku1lJCUquLCsQ5UXyhLKZeIN4MerlPi/3YGcyiQ9r6uZ7JMVEvO8LxyC0MBJ6Dsl9R8g8QhpLLV3bnW/YHvitRD2BREz8i4= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass header.from= (p=none dis=none) Return-Path: Received: from lists1p.gnu.org (lists1p.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1784751083964929.3393930222979; Wed, 22 Jul 2026 13:11:23 -0700 (PDT) Received: from localhost ([::1] helo=lists1p.gnu.org) by lists1p.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1wmdHX-0002iI-3M; Wed, 22 Jul 2026 16:11:07 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists1p.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1wmdHS-0002h4-Qm for qemu-devel@nongnu.org; Wed, 22 Jul 2026 16:11:02 -0400 Received: from mail-yw1-x112a.google.com ([2607:f8b0:4864:20::112a]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1wmdHQ-0002W1-V8 for qemu-devel@nongnu.org; Wed, 22 Jul 2026 16:11:02 -0400 Received: by mail-yw1-x112a.google.com with SMTP id 00721157ae682-81ef8255cccso49964527b3.0 for ; Wed, 22 Jul 2026 13:10:58 -0700 (PDT) Received: from MacLin.attlocal.net ([2600:1700:e140:14d0:eb7d:6ac0:a76f:2c5f]) by smtp.gmail.com with ESMTPSA id 00721157ae682-81f40366af6sm10389407b3.43.2026.07.22.13.10.56 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Jul 2026 13:10:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1784751058; x=1785355858; darn=nongnu.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to:content-type; bh=YOILP0Pnl+nB+lm+CUiKOOV4KZnWh2wtQlwbvvyjiNg=; b=Jrdcd5FMFeXfWs6wPU5Ew9zc6xugtMBfJYI3Mao+0Q57xhGKlHgZIUmc9X200SYMCW efyUdxSvfHZCVgIuDI3XGoSlvuW9EPFPsbf20psFcQ2tZbINU7/djRV861he5o4uPJRS wQXLlbr47cbUbPcPcxvkN6IpuPcxAoOr23H5t4fVIP4QjAN4m4GL2aVNd1S2OGz7DtU2 hcZZPUhTgQJLFIURBZHbDPaVYRMHtvPVe5lt6D5CE832bW+K5Ir3PmX0e4xtvy6SQMzF DfDsUTeledvYwacGtnWEdr7tzzUquK7vXjD1Q1PhILqEXyUdgB2y2m1LIJtQ8kbDm9EU R37Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1784751058; x=1785355858; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-gg:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to:content-type; bh=YOILP0Pnl+nB+lm+CUiKOOV4KZnWh2wtQlwbvvyjiNg=; b=CondJtPFBSgXnfBls6a2oALLzbYuriM3mU/Lz70wSeVQIpO5pN+9wfOx8n+PtcVNfN 5fp2Viery4UB5iJNupZdifrhfSh3MgnZRj5VNVxeTTYNjBiJWemymnCTRguyKoHgFqVm tU+mQJx8TSwNgYAqsqMZGvRiMjGDlTeuqvZy1jJEKyjoxdpO8Yfxyr4MtleO2nqFELaf 0rLMYeCSFU9JzGP9Va77qMR8VgmD+CXzRS1Jdj3wTGnmi6pfI/wECpKPSHoABOTS4U0A jkprRtl9vROJl3WBeA49A9WP9tDr1oDI3+1HLfdkdPYHGf0carPgsQ1Uqw5yg7nL9pD4 h0iw== X-Gm-Message-State: AOJu0YxGclVvToAFKC1SGDITLMBt6XNqr7YtK7pDtcySl29449CPn0V6 FwPi+E/CPnd83N66Iqv5w1itHtIoHPCKw5ZEIqIcIweuS4g0mzJChkh4oTVranjd X-Gm-Gg: AR+sD129sTCBzt5mU0w+xveUJlNPYmVE9wsZcuekoiUGTDj42BYze3RDi3cmtlqdBvh 9lSe5rhCdBw4JnxebGsokDb6CbbXkkoQ7p+yo04+4+EGMb76bkvwzwXbblKoJ+FQyIN7XWI2JKy rSk4axvwiPED8P8MF1jl3xh0+AD2mGq9W+KmxVjv5iMRaPxMkxHwdsJ8Ecq+To3EetuCAQyqI82 6uXEGxvTCVV+BYcLumoUAyk6biLdSkk3mrcAUDipCp+kEGxanqq5opWZS+l2gGmoCsTsgUsqbDv Tbr1mbALe/ZzbG6tm9Mz+KkV4EIQKmYUCe36i57wN2hulIcnegdYuiCi6lHzCKRwU0QURM1K0i6 JTEPpEEsaREDD4YV9JIv5ChNct9w+VijNsEvzS/0tAX2A+q7fc+5BFcl1l5VzeDa71NJp9d21AP T97TdHRYr2BnVnmn0n3A== X-Received: by 2002:a05:690c:6712:b0:80c:8596:4653 with SMTP id 00721157ae682-81f4c3b4eadmr198207b3.69.1784751057969; Wed, 22 Jul 2026 13:10:57 -0700 (PDT) From: Connor Kite To: qemu-devel@nongnu.org Cc: peterx@redhat.com, stefanha@redhat.com, Connor Kite Subject: [PATCH] util/iova-tree: gapless map Date: Wed, 22 Jul 2026 13:07:05 -0700 Message-ID: <20260722200951.553764-2-connorkite@gmail.com> X-Mailer: git-send-email 2.43.0 MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists1p.gnu.org; Received-SPF: pass client-ip=2607:f8b0:4864:20::112a; envelope-from=connorkite@gmail.com; helo=mail-yw1-x112a.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: qemu development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: qemu-devel-bounces+importer=patchew.org@nongnu.org X-ZohoMail-DKIM: pass (identity @gmail.com) X-ZM-MESSAGEID: 1784751085803158501 Content-Type: text/plain; charset="utf-8" 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 --- 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, gconstpoi= nter b, gpointer data) { const DMAMap *m1 =3D a, *m2 =3D b; =20 - if (m1->iova > m2->iova + m2->size) { + if (m1->iova >=3D m2->iova + m2->size) { return 1; } =20 - if (m1->iova + m1->size < m2->iova) { + if (m1->iova + m1->size <=3D m2->iova) { return -1; } =20 @@ -96,8 +96,8 @@ static gboolean iova_tree_find_address_iterator(gpointer = key, gpointer value, g_assert(key =3D=3D value); =20 needle =3D 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 <=3D needle->translated_addr || + needle->translated_addr + needle->size <=3D map->translated_addr) { return false; } =20 @@ -125,7 +125,7 @@ int iova_tree_insert(IOVATree *tree, const DMAMap *map) { DMAMap *new; =20 - if (map->iova + map->size < map->iova || map->perm =3D=3D IOMMU_NONE) { + if (map->iova + map->size <=3D map->iova || map->perm =3D=3D IOMMU_NON= E) { return IOVA_ERR_INVALID; } =20 @@ -174,14 +174,14 @@ static void iova_tree_alloc_map_in_hole(struct IOVATr= eeAllocArgs *args) const DMAMap *prev =3D args->prev, *this =3D args->this; uint64_t hole_start, hole_last; =20 - if (this && this->iova + this->size < args->iova_begin) { + if (this && this->iova + this->size <=3D args->iova_begin) { return; } =20 - hole_start =3D MAX(prev ? prev->iova + prev->size + 1 : 0, args->iova_= begin); - hole_last =3D this ? this->iova : HWADDR_MAX; + hole_start =3D MAX(prev ? prev->iova + prev->size : 0, args->iova_begi= n); + hole_last =3D this ? this->iova - 1 : HWADDR_MAX; =20 - if (hole_last - hole_start > args->new_size) { + if (hole_last - hole_start + 1 > args->new_size) { args->iova_result =3D hole_start; args->iova_found =3D true; } @@ -244,7 +244,7 @@ int iova_tree_alloc_map(IOVATree *tree, DMAMap *map, hw= addr iova_begin, iova_tree_alloc_map_in_hole(&args); } =20 - 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; } =20 @@ -262,11 +262,11 @@ static int gpa_tree_compare(gconstpointer a, gconstpo= inter b, gpointer data) { const DMAMap *m1 =3D a, *m2 =3D b; =20 - if (m1->translated_addr > m2->translated_addr + m2->size) { + if (m1->translated_addr >=3D m2->translated_addr + m2->size) { return 1; } =20 - if (m1->translated_addr + m1->size < m2->translated_addr) { + if (m1->translated_addr + m1->size <=3D m2->translated_addr) { return -1; } =20 @@ -287,7 +287,7 @@ int gpa_tree_insert(IOVATree *tree, const DMAMap *map) { DMAMap *new; =20 - if (map->translated_addr + map->size < map->translated_addr || + if (map->translated_addr + map->size <=3D map->translated_addr || map->perm =3D=3D IOMMU_NONE) { return IOVA_ERR_INVALID; } --=20 2.43.0