Skip to content

convert iova to maple tree

Rik van Riel linux-iommu lkml 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. 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 filesSizeRepliesApplied
1/3iova: convert from rbtree to maple treedrivers/iommu/iova.c include/linux/iova.h+133 -2520 replies
2/3iova: add KUnit test suitedrivers/iommu/.kunitconfig drivers/iommu/Kconfig drivers/iommu/Makefile +3 more+499 -00 replies
3/3iova: defer maple tree erase on GFP_ATOMIC failuredrivers/iommu/iova-kunit.c drivers/iommu/iova.c include/linux/iova.h+233 -142 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

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