From: Rik van Riel <riel@surriel.com>
To: linux-kernel@vger.kernel.org
Cc: robin.murphy@arm.com, joro@8bytes.org, will@kernel.org,
iommu@lists.linux.dev, kyle@mcmartin.ca, kernel-team@meta.com
Subject: [PATCH 0/5] iova augmented rbtree O(log n) alloc_iova
Date: Tue, 12 May 2026 22:00:17 -0400 [thread overview]
Message-ID: <20260513020304.1528751-1-riel@surriel.com> (raw)
Occasionally production workloads at Meta run into the linear search
in alloc_iova() in ways that cause real issues. For example, when
enough CPUs at a time fall into the linear search trap, systems
have been known to get stuck for so long that it causes soft lockups.
With the old code, free_iova, find_iova, reserve_iova, iova_insert_rbtree,
and remove_iova were all O(log n) already. They stay that way with these
patches.
This patch series turns the iova rbtree into an augmented rbtree,
which allows alloc_iova to also be O(log n).
It also adds some self tests for the iova code.
The code was written by Claude, and nitpicked by myself.
Don't be shy if there are more nitpicks remaining.
It was tested both in a VM (running the selftests), and on an
AMD Bergamo system with IOMMU enabled.
Unfortunately I do not know of any way to reproduce the linear
search soft lockups at will, so I have not been able to verify
that scenary in practice.
Based on 5d6919055dec Linux 7.1-rc3
next reply other threads:[~2026-05-13 2:03 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-05-13 2:00 Rik van Riel [this message]
2026-05-13 2:00 ` [PATCH 1/5] iova: switch to augmented rbtree for log(n) allocation Rik van Riel
2026-05-13 2:00 ` [PATCH 2/5] iova: drop dead cached_node / cached32_node infrastructure Rik van Riel
2026-05-13 2:00 ` [PATCH 3/5] iova: limit_pfn-aware augmentation for log(n) 32-bit alloc Rik van Riel
2026-05-13 2:00 ` [PATCH 4/5] iova: alignment-aware two-phase search for log(n) aligned alloc Rik van Riel
2026-05-13 2:00 ` [PATCH 5/5] iova: add KUnit test suite Rik van Riel
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20260513020304.1528751-1-riel@surriel.com \
--to=riel@surriel.com \
--cc=iommu@lists.linux.dev \
--cc=joro@8bytes.org \
--cc=kernel-team@meta.com \
--cc=kyle@mcmartin.ca \
--cc=linux-kernel@vger.kernel.org \
--cc=robin.murphy@arm.com \
--cc=will@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox