On Thu, Feb 15, 2024 at 03:22:48PM +0800, Lu Baolu wrote:
Use a red-black tree(rbtree) to track devices probed by the driver'sReviewed-by: Jason Gunthorpe<jgg@xxxxxxxxxx>
probe_device callback. These devices need to be looked up quickly by
a source ID when the hardware reports a fault, either recoverable or
unrecoverable.
Fault reporting paths are critical. Searching a list in this scenario
is inefficient, with an algorithm complexity of O(n). An rbtree is a
self-balancing binary search tree, offering an average search time
complexity of O(log(n)). This significant performance improvement
makes rbtrees a better choice.
Furthermore, rbtrees are implemented on a per-iommu basis, eliminating
the need for global searches and further enhancing efficiency in
critical fault paths. The rbtree is protected by a spin lock with
interrupts disabled to ensure thread-safe access even within interrupt
contexts.
Co-developed-by: Huang Jiaqing<jiaqing.huang@xxxxxxxxx>
Signed-off-by: Huang Jiaqing<jiaqing.huang@xxxxxxxxx>
Signed-off-by: Lu Baolu<baolu.lu@xxxxxxxxxxxxxxx>
---
drivers/iommu/intel/iommu.h | 7 +++++
drivers/iommu/intel/dmar.c | 3 +-
drivers/iommu/intel/iommu.c | 62 +++++++++++++++++++++++++++++++++++--
3 files changed, 69 insertions(+), 3 deletions(-)
+static int device_rbtree_insert(struct intel_iommu *iommu,I would suggest
+ struct device_domain_info *info)
+{
+ struct rb_node *curr;
+ unsigned long flags;
+
+ spin_lock_irqsave(&iommu->device_rbtree_lock, flags);
+ curr = rb_find_add(&info->node, &iommu->device_rbtree, device_rid_cmp);
+ spin_unlock_irqrestore(&iommu->device_rbtree_lock, flags);
+ if (curr)
+ dev_warn(info->dev, "device already in rbtree\n");
WARN_ON(curr);
Something has gone really wonky at this point, right?