convert iova to maple tree
Get series with b4
b4 am [email protected]Versions newest first
- v1 Latest3 patches 3 repliesIn review
v4 from the cover letter
- reduce the size of struct iova to 16 bytes
- simplify the (hopefully rare) remove_iova GFP_ATOMIC failure path
- test case for the deferred free code
Patches in v1 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/3 | iova: convert from rbtree to maple treedrivers/ include/ | +133 | 0 replies | |
| 2/3 | iova: add KUnit test suitedrivers/ drivers/ drivers/ +3 more | +499 | 0 replies | |
| 3/3 | iova: defer maple tree erase on GFP_ATOMIC failuredrivers/ drivers/ include/ | +233 | 2 replies |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.
Cover letter [PATCH 0/3] convert iova to maple tree
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 uses a maple tree to index the iova ranges. This allows alloc_iova() to have O(log n) complexity, while memory use stays about the same as before.
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
v4:
- reduce the size of struct iova to 16 bytes
- simplify the (hopefully rare) remove_iova GFP_ATOMIC failure path
- test case for the deferred free code
v3:
- switch to maple tree (suggested by Robin Murphy)
v2:
- clean up selftests (thanks Jason Gunthorpe)
- address Sashiko concerns
- drop the search-with-alignment, since most iova requests should be of similar sizes, so the worst case behavior is unlikely to hit once ranges are excluded by the augmented rbtree