iommu: remove lock contention in iova allocation

PATCH Superseded Shaohua Li 4 participants 14 messages Nov 24, 2015 – Dec 7, 2015 9 messages not in the archive

Subsystems (2)

IOMMU IOMMU DMA-API layer

lore

Share & tools

lore

Shaohua Li

author

2015-11-24 21:54 UTC #0 lore raw

cover iommu: remove lock contention in iova allocation

Hi,

The lock contention in iova allocation is very significant. In my iperf test with intel 10Gbps NIC card with 48 threads, I observed 99% cpu time is spending on the lock contention. In the test:

CPU utilization 100%, iperf reports ~1Gbps

The patches introduce a bitmap based approach for dma address allocation. It completetly avoids the lock contention. Run the same test:

CPU utilization 1%, iperf reports 9.3Gbps

I also tried the test with the patch, but disable bitmap. The result is the same as that without the patch.

The patches only work for DMA less than 8k, which is the most comman case we have highest request(DMA) per second. Bigger size DMA still fallback to rbtree based allocation. But if required and DAC is enabled by default, it's easy to support bigger size DMA in the bitmap allocation.

Thanks,
Shaohua

Shaohua Li (4):
iommu: alloc_iova returns a pfn
iommu: add a bitmap based dma address allocator
iommu: enable bitmap allocation for intel iommu
iommu: free_iova doesn't need lock twice

 drivers/iommu/dma-iommu.c   |  32 ++++-----
 drivers/iommu/intel-iommu.c |  96 ++++++++++++++++-----------
 drivers/iommu/iova.c        | 157 +++++++++++++++++++++++++++++++++-----------
 include/linux/iova.h        |  21 ++++--
 4 files changed, 210 insertions(+), 96 deletions(-)

Signature · 1 line

2.4.6

Shaohua Li

author

2015-11-24 21:54 UTC #2 lore raw

PATCH 1/4 iommu: alloc_iova returns a pfn

In reply to a message not in the archive

make alloc_iova return a pfn instead of iova. This is a preparation patch.

Cc Joerg Roedel <[email protected]>

Cc David Woodhouse <[email protected]>

Signed-off-by Shaohua Li <[email protected]>

---
 drivers/iommu/dma-iommu.c   | 30 ++++++++++----------
 drivers/iommu/intel-iommu.c | 67 ++++++++++++++++++++++++++-------------------
 drivers/iommu/iova.c        | 11 ++++----
 include/linux/iova.h        |  6 ++--
 4 files changed, 63 insertions(+), 51 deletions(-)

drivers/iommu/dma-iommu.c +15 ~~-15~~

index 3a20db4..a86291e 100644
@@ -148,7 +148,7 @@ int dma_direction_to_prot(enum dma_data_direction dir, bool coherent)
 	}
 }
 
-static struct iova *__alloc_iova(struct iova_domain *iovad, size_t size,
+static unsigned long __alloc_iova(struct iova_domain *iovad, size_t size,
 		dma_addr_t dma_limit)
 {
 	unsigned long shift = iova_shift(iovad);

@@ -279,7 +279,7 @@ struct page **iommu_dma_alloc(struct device *dev, size_t size,
 {
 	struct iommu_domain *domain = iommu_get_domain_for_dev(dev);
 	struct iova_domain *iovad = domain->iova_cookie;
-	struct iova *iova;
+	unsigned long iova_pfn;
 	struct page **pages;
 	struct sg_table sgt;
 	dma_addr_t dma_addr;

@@ -291,8 +291,8 @@ struct page **iommu_dma_alloc(struct device *dev, size_t size,
 	if (!pages)
 		return NULL;
 
-	iova = __alloc_iova(iovad, size, dev->coherent_dma_mask);
-	if (!iova)
+	iova_pfn = __alloc_iova(iovad, size, dev->coherent_dma_mask);
+	if (!iova_pfn)
 		goto out_free_pages;
 
 	size = iova_align(iovad, size);

@@ -311,7 +311,7 @@ struct page **iommu_dma_alloc(struct device *dev, size_t size,
 		sg_miter_stop(&miter);
 	}
 
-	dma_addr = iova_dma_addr(iovad, iova);
+	dma_addr = iova_dma_addr(iovad, iova_pfn);
 	if (iommu_map_sg(domain, dma_addr, sgt.sgl, sgt.orig_nents, prot)
 			< size)
 		goto out_free_sg;

@@ -323,7 +323,7 @@ struct page **iommu_dma_alloc(struct device *dev, size_t size,
 out_free_sg:
 	sg_free_table(&sgt);
 out_free_iova:
-	__free_iova(iovad, iova);
+	free_iova(iovad, iova_pfn);
 out_free_pages:
 	__iommu_dma_free_pages(pages, count);
 	return NULL;

@@ -363,14 +363,14 @@ dma_addr_t iommu_dma_map_page(struct device *dev, struct page *page,
 	phys_addr_t phys = page_to_phys(page) + offset;
 	size_t iova_off = iova_offset(iovad, phys);
 	size_t len = iova_align(iovad, size + iova_off);
-	struct iova *iova = __alloc_iova(iovad, len, dma_get_mask(dev));
+	unsigned long iova_pfn = __alloc_iova(iovad, len, dma_get_mask(dev));
 
-	if (!iova)
+	if (!iova_pfn)
 		return DMA_ERROR_CODE;
 
-	dma_addr = iova_dma_addr(iovad, iova);
+	dma_addr = iova_dma_addr(iovad, iova_pfn);
 	if (iommu_map(domain, dma_addr, phys - iova_off, len, prot)) {
-		__free_iova(iovad, iova);
+		free_iova(iovad, iova_pfn);
 		return DMA_ERROR_CODE;
 	}
 	return dma_addr + iova_off;

@@ -437,7 +437,7 @@ int iommu_dma_map_sg(struct device *dev, struct scatterlist *sg,
 {
 	struct iommu_domain *domain = iommu_get_domain_for_dev(dev);
 	struct iova_domain *iovad = domain->iova_cookie;
-	struct iova *iova;
+	unsigned long iova_pfn;
 	struct scatterlist *s, *prev = NULL;
 	dma_addr_t dma_addr;
 	size_t iova_len = 0;

@@ -477,22 +477,22 @@ int iommu_dma_map_sg(struct device *dev, struct scatterlist *sg,
 		prev = s;
 	}
 
-	iova = __alloc_iova(iovad, iova_len, dma_get_mask(dev));
-	if (!iova)
+	iova_pfn = __alloc_iova(iovad, iova_len, dma_get_mask(dev));
+	if (!iova_pfn)
 		goto out_restore_sg;
 
 	/*
 	 * We'll leave any physical concatenation to the IOMMU driver's
 	 * implementation - it knows better than we do.
 	 */
-	dma_addr = iova_dma_addr(iovad, iova);
+	dma_addr = iova_dma_addr(iovad, iova_pfn);
 	if (iommu_map_sg(domain, dma_addr, sg, nents, prot) < iova_len)
 		goto out_free_iova;
 
 	return __finalise_sg(dev, sg, nents, dma_addr);
 
 out_free_iova:
-	__free_iova(iovad, iova);
+	free_iova(iovad, iova_pfn);
 out_restore_sg:
 	__invalidate_sg(sg, nents);
 	return 0;

drivers/iommu/intel-iommu.c +39 ~~-28~~

183 lines not on this page · raw message

drivers/iommu/iova.c +6 -5

index fa0adef..2c5e197 100644
@@ -36,6 +36,8 @@ init_iova_domain(struct iova_domain *iovad, unsigned long granule,
 	iovad->rbroot = RB_ROOT;
 	iovad->cached32_node = NULL;
 	iovad->granule = granule;
+	if (start_pfn == 0)
+		start_pfn = 1;
 	iovad->start_pfn = start_pfn;
 	iovad->dma_32bit_pfn = pfn_32bit;
 }

@@ -267,7 +269,7 @@ EXPORT_SYMBOL_GPL(iova_cache_put);
  * flag is set then the allocated address iova->pfn_lo will be naturally
  * aligned on roundup_power_of_two(size).
  */
-struct iova *
+unsigned long
 alloc_iova(struct iova_domain *iovad, unsigned long size,
 	unsigned long limit_pfn,
 	bool size_aligned)

@@ -277,17 +279,17 @@ alloc_iova(struct iova_domain *iovad, unsigned long size,
 
 	new_iova = alloc_iova_mem();
 	if (!new_iova)
-		return NULL;
+		return 0;
 
 	ret = __alloc_and_insert_iova_range(iovad, size, limit_pfn,
 			new_iova, size_aligned);
 
 	if (ret) {
 		free_iova_mem(new_iova);
-		return NULL;
+		return 0;
 	}
 
-	return new_iova;
+	return new_iova->pfn_lo;
 }
 EXPORT_SYMBOL_GPL(alloc_iova);

@@ -365,7 +367,6 @@ free_iova(struct iova_domain *iovad, unsigned long pfn)
 
 	if (iova)
 		__free_iova(iovad, iova);
-
 }
 EXPORT_SYMBOL_GPL(free_iova);

include/linux/iova.h +3 -3

index 92f7177..cfe5ee9 100644
@@ -58,9 +58,9 @@ static inline size_t iova_align(struct iova_domain *iovad, size_t size)
 	return ALIGN(size, iovad->granule);
 }
 
-static inline dma_addr_t iova_dma_addr(struct iova_domain *iovad, struct iova *iova)
+static inline dma_addr_t iova_dma_addr(struct iova_domain *iovad, unsigned long iova_pfn)
 {
-	return (dma_addr_t)iova->pfn_lo << iova_shift(iovad);
+	return (dma_addr_t)iova_pfn << iova_shift(iovad);
 }
 
 static inline unsigned long iova_pfn(struct iova_domain *iovad, dma_addr_t iova)

@@ -75,7 +75,7 @@ struct iova *alloc_iova_mem(void);
 void free_iova_mem(struct iova *iova);
 void free_iova(struct iova_domain *iovad, unsigned long pfn);
 void __free_iova(struct iova_domain *iovad, struct iova *iova);
-struct iova *alloc_iova(struct iova_domain *iovad, unsigned long size,
+unsigned long alloc_iova(struct iova_domain *iovad, unsigned long size,
 	unsigned long limit_pfn,
 	bool size_aligned);
 struct iova *reserve_iova(struct iova_domain *iovad, unsigned long pfn_lo,

Signature · 1 line

2.4.6

Shaohua Li

author

2015-11-24 21:54 UTC #3 lore raw

PATCH 2/4 iommu: add a bitmap based dma address allocator

In reply to a message not in the archive

iovad rbtree spinlock contention is very significant. In a workload with netperf and 10Gb NIC, multithread workload shows 100% cpu utilization (99% cpu time on the lock) and the total throughput is less than 1Gbps.

This patch introduces a bitmap based allocator. We allocate a big chunk of DMA range and divide it into 8k chunks. Each bit in the bitmap present the 8k chunk. For any allocation with size less than 8k, we allocate 8k. The DMA address allocation then becomes an allocation one bit from a bitmap. We use percpu bitmap to speed up the bit allocation further.

With the bitmap allocation, the lock contention is completely avoided. In the workload above, the throughput is around 9.28Gbps and cpu utilization drops to 1%.

The only works for DMA less than 8k, but it's case with most heavy lock contention. If DAC is enabled by default on the future, we can allocate a bigger DMA range and bigger chunk size.

Cc Joerg Roedel <[email protected]>

Cc David Woodhouse <[email protected]>

Signed-off-by Shaohua Li <[email protected]>

---
 drivers/iommu/intel-iommu.c | 23 +++++++----
 drivers/iommu/iova.c        | 93 +++++++++++++++++++++++++++++++++++++++------
 include/linux/iova.h        | 13 +++++++
 3 files changed, 109 insertions(+), 20 deletions(-)

drivers/iommu/intel-iommu.c +15 -8

index 5c57b9a..6412297 100644
@@ -3595,7 +3595,7 @@ static void intel_unmap(struct device *dev, dma_addr_t dev_addr)
 {
 	struct dmar_domain *domain;
 	unsigned long start_pfn, last_pfn;
-	struct iova *iova;
+	struct iova *iova = NULL;
 	struct intel_iommu *iommu;
 	struct page *freelist;

@@ -3607,13 +3607,17 @@ static void intel_unmap(struct device *dev, dma_addr_t dev_addr)
 
 	iommu = domain_get_iommu(domain);
 
-	iova = find_iova(&domain->iovad, IOVA_PFN(dev_addr));
-	if (WARN_ONCE(!iova, "Driver unmaps unmatched page at PFN %llx\n",
+	if (iova_pfn_in_bitmap(&domain->iovad, IOVA_PFN(dev_addr))) {
+		start_pfn = IOVA_PFN(dev_addr);
+		last_pfn = start_pfn + IOVA_BITMAP_UNIT - 1;
+	} else {
+		iova = find_iova(&domain->iovad, IOVA_PFN(dev_addr));
+		if (WARN_ONCE(!iova, "Driver unmaps unmatched page at PFN %llx\n",
 		      (unsigned long long)dev_addr))
-		return;
-
-	start_pfn = mm_to_dma_pfn(iova->pfn_lo);
-	last_pfn = mm_to_dma_pfn(iova->pfn_hi + 1) - 1;
+			return;
+		start_pfn = mm_to_dma_pfn(iova->pfn_lo);
+		last_pfn = mm_to_dma_pfn(iova->pfn_hi + 1) - 1;
+	}
 
 	pr_debug("Device %s unmapping: pfn %lx-%lx\n",
 		 dev_name(dev), start_pfn, last_pfn);

@@ -3624,7 +3628,10 @@ static void intel_unmap(struct device *dev, dma_addr_t dev_addr)
 		iommu_flush_iotlb_psi(iommu, domain, start_pfn,
 				      last_pfn - start_pfn + 1, !freelist, 0);
 		/* free iova */
-		__free_iova(&domain->iovad, iova);
+		if (iova)
+			__free_iova(&domain->iovad, iova);
+		else
+			free_iova(&domain->iovad, start_pfn);
 		dma_free_pagelist(freelist);
 	} else {
 		add_unmap(domain, IOVA_PFN(dev_addr), last_pfn - start_pfn + 1,

drivers/iommu/iova.c +81 ~~-12~~

145 lines not on this page · raw message

include/linux/iova.h +13 -0

index cfe5ee9..63a81ef 100644
@@ -15,6 +15,7 @@
 #include <linux/kernel.h>
 #include <linux/rbtree.h>
 #include <linux/dma-mapping.h>
+#include <linux/percpu_ida.h>
 
 /* iova structure */
 struct iova {

@@ -23,6 +24,9 @@ struct iova {
 	unsigned long	pfn_lo; /* IOMMU dish out addr lo */
 };
 
+#define IOVA_BITMAP_UNIT ((8 * 1024) >> PAGE_SHIFT)
+#define IOVA_BITMAP_UNIT_LOG (ilog2(IOVA_BITMAP_UNIT))
+#define IOVA_BITMAP_SIZE ((1L * 1024 * 1024 * 1024) >> PAGE_SHIFT)
 /* holds all the iova translations for a domain */
 struct iova_domain {
 	spinlock_t	iova_rbtree_lock; /* Lock to protect update of rbtree */

@@ -31,6 +35,9 @@ struct iova_domain {
 	unsigned long	granule;	/* pfn granularity for this domain */
 	unsigned long	start_pfn;	/* Lower limit for this domain */
 	unsigned long	dma_32bit_pfn;
+	struct percpu_ida bitmap;
+	struct iova	*bitmap_iova;
+	bool		disable_bitmap;
 };
 
 static inline unsigned long iova_size(struct iova *iova)

@@ -68,6 +75,12 @@ static inline unsigned long iova_pfn(struct iova_domain *iovad, dma_addr_t iova)
 	return iova >> iova_shift(iovad);
 }
 
+static inline bool iova_pfn_in_bitmap(struct iova_domain *iovad, unsigned long pfn)
+{
+	return iovad->bitmap_iova && pfn >= iovad->bitmap_iova->pfn_lo &&
+	    pfn <= iovad->bitmap_iova->pfn_hi;
+}
+
 int iova_cache_get(void);
 void iova_cache_put(void);

Signature · 1 line

2.4.6

Shaohua Li

author

2015-11-24 21:54 UTC #20 lore raw

PATCH 3/4 iommu: enable bitmap allocation for intel iommu

In reply to a message not in the archive

I can't test the bitmap allocation for dma-iommu, so just enable it for intel iommu.

Cc Joerg Roedel <[email protected]>

Cc David Woodhouse <[email protected]>

Signed-off-by Shaohua Li <[email protected]>

---
 drivers/iommu/dma-iommu.c   | 2 +-
 drivers/iommu/intel-iommu.c | 6 +++---
 drivers/iommu/iova.c        | 4 ++--
 include/linux/iova.h        | 2 +-
 4 files changed, 7 insertions(+), 7 deletions(-)

drivers/iommu/dma-iommu.c +1 -1

index a86291e..a42c2a8 100644
@@ -119,7 +119,7 @@ int iommu_dma_init_domain(struct iommu_domain *domain, dma_addr_t base, u64 size
 		}
 		iovad->dma_32bit_pfn = end_pfn;
 	} else {
-		init_iova_domain(iovad, 1UL << order, base_pfn, end_pfn);
+		init_iova_domain(iovad, 1UL << order, base_pfn, end_pfn, true);
 	}
 	return 0;
 }

drivers/iommu/intel-iommu.c +3 -3

index 6412297..d0ce3e4 100644
@@ -1808,7 +1808,7 @@ static int dmar_init_reserved_ranges(void)
 	int i;
 
 	init_iova_domain(&reserved_iova_list, VTD_PAGE_SIZE, IOVA_START_PFN,
-			DMA_32BIT_PFN);
+			DMA_32BIT_PFN, false);
 
 	lockdep_set_class(&reserved_iova_list.iova_rbtree_lock,
 		&reserved_rbtree_key);

@@ -1867,7 +1867,7 @@ static int domain_init(struct dmar_domain *domain, struct intel_iommu *iommu,
 	unsigned long sagaw;
 
 	init_iova_domain(&domain->iovad, VTD_PAGE_SIZE, IOVA_START_PFN,
-			DMA_32BIT_PFN);
+			DMA_32BIT_PFN, false);
 	domain_reserve_special_ranges(domain);
 
 	/* calculate AGAW */

@@ -4749,7 +4749,7 @@ static int md_domain_init(struct dmar_domain *domain, int guest_width)
 	int adjust_width;
 
 	init_iova_domain(&domain->iovad, VTD_PAGE_SIZE, IOVA_START_PFN,
-			DMA_32BIT_PFN);
+			DMA_32BIT_PFN, false);
 	domain_reserve_special_ranges(domain);
 
 	/* calculate AGAW */

drivers/iommu/iova.c +2 -2

index 6d11caf..0d71be7 100644
@@ -24,7 +24,7 @@
 
 void
 init_iova_domain(struct iova_domain *iovad, unsigned long granule,
-	unsigned long start_pfn, unsigned long pfn_32bit)
+	unsigned long start_pfn, unsigned long pfn_32bit, bool disable_bitmap)
 {
 	/*
 	 * IOVA granularity will normally be equal to the smallest

@@ -43,7 +43,7 @@ init_iova_domain(struct iova_domain *iovad, unsigned long granule,
 	iovad->dma_32bit_pfn = pfn_32bit;
 	percpu_ida_init(&iovad->bitmap, IOVA_BITMAP_SIZE / IOVA_BITMAP_UNIT);
 	iovad->bitmap_iova = NULL;
-	iovad->disable_bitmap = true;
+	iovad->disable_bitmap = disable_bitmap;
 }
 EXPORT_SYMBOL_GPL(init_iova_domain);

include/linux/iova.h +1 -1

index 63a81ef..457f93b 100644
@@ -95,7 +95,7 @@ struct iova *reserve_iova(struct iova_domain *iovad, unsigned long pfn_lo,
 	unsigned long pfn_hi);
 void copy_reserved_iova(struct iova_domain *from, struct iova_domain *to);
 void init_iova_domain(struct iova_domain *iovad, unsigned long granule,
-	unsigned long start_pfn, unsigned long pfn_32bit);
+	unsigned long start_pfn, unsigned long pfn_32bit, bool disable_bitmap);
 struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn);
 void put_iova_domain(struct iova_domain *iovad);
 struct iova *split_and_remove_iova(struct iova_domain *iovad,

Signature · 1 line

2.4.6

Shaohua Li

author

2015-11-24 21:54 UTC #21 lore raw

PATCH 4/4 iommu: free_iova doesn't need lock twice

In reply to a message not in the archive

cleanup the code a bit. free_iova doesn't need lock twice.

Cc Joerg Roedel <[email protected]>

Cc David Woodhouse <[email protected]>

Signed-off-by Shaohua Li <[email protected]>

---
 drivers/iommu/iova.c | 57 ++++++++++++++++++++++++++++++++--------------------
 1 file changed, 35 insertions(+), 22 deletions(-)

drivers/iommu/iova.c +35 ~~-22~~

index 0d71be7..5f03c42 100644
@@ -348,33 +348,16 @@ alloc_iova(struct iova_domain *iovad, unsigned long size,
 }
 EXPORT_SYMBOL_GPL(alloc_iova);
 
-/**
- * find_iova - find's an iova for a given pfn
- * @iovad: - iova domain in question.
- * @pfn: - page frame number
- * This function finds and returns an iova belonging to the
- * given doamin which matches the given pfn.
- */
-struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn)
+static struct iova *__find_iova(struct iova_domain *iovad, unsigned long pfn)
 {
-	unsigned long flags;
 	struct rb_node *node;
 
-	/* Take the lock so that no other thread is manipulating the rbtree */
-	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
 	node = iovad->rbroot.rb_node;
 	while (node) {
 		struct iova *iova = container_of(node, struct iova, node);
 
 		/* If pfn falls within iova's range, return iova */
 		if ((pfn >= iova->pfn_lo) && (pfn <= iova->pfn_hi)) {
-			spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
-			/* We are not holding the lock while this iova
-			 * is referenced by the caller as the same thread
-			 * which called this function also calls __free_iova()
-			 * and it is by design that only one thread can possibly
-			 * reference a particular iova and hence no conflict.
-			 */
 			return iova;
 		}

@@ -384,9 +367,33 @@ struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn)
 			node = node->rb_right;
 	}
 
-	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 	return NULL;
 }
+
+/**
+ * find_iova - find's an iova for a given pfn
+ * @iovad: - iova domain in question.
+ * @pfn: - page frame number
+ * This function finds and returns an iova belonging to the
+ * given doamin which matches the given pfn.
+ */
+struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn)
+{
+	unsigned long flags;
+	struct iova *iova;
+
+	/* Take the lock so that no other thread is manipulating the rbtree */
+	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
+	iova = __find_iova(iovad, pfn);
+	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
+	/* We are not holding the lock while this iova
+	 * is referenced by the caller as the same thread
+	 * which called this function also calls __free_iova()
+	 * and it is by design that only one thread can possibly
+	 * reference a particular iova and hence no conflict.
+	 */
+	return iova;
+}
 EXPORT_SYMBOL_GPL(find_iova);
 
 /**

@@ -421,6 +428,7 @@ void
 free_iova(struct iova_domain *iovad, unsigned long pfn)
 {
 	struct iova *iova;
+	unsigned long flags;
 
 	if (iova_pfn_in_bitmap(iovad, pfn)) {
 		int tag;

@@ -431,9 +439,14 @@ free_iova(struct iova_domain *iovad, unsigned long pfn)
 		return;
 	}
 
-	iova = find_iova(iovad, pfn);
-	if (iova)
-		__free_iova(iovad, iova);
+	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
+	iova = __find_iova(iovad, pfn);
+	if (iova) {
+		__cached_rbnode_delete_update(iovad, iova);
+		rb_erase(&iova->node, &iovad->rbroot);
+	}
+	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
+	free_iova_mem(iova);
 }
 EXPORT_SYMBOL_GPL(free_iova);

Signature · 1 line

2.4.6

Woodhouse, David

2015-11-24 21:56 UTC #5 lore raw

Re: [PATCH 2/4] iommu: add a bitmap based dma address allocator

In reply to a message not in the archive

Quoted 2 lines · Shaohua Li

This patch introduces a bitmap based allocator.

Why not just use the one in lib/iommu-common.c? I'd like to see intel-iommu completely drop the iova.c code.

Signature · 2 lines

David Woodhouse                            Open Source Technology Centre
[email protected]                              Intel Corporation

Shaohua Li

author

2015-11-24 22:05 UTC #7 lore raw

Re: [PATCH 2/4] iommu: add a bitmap based dma address allocator

In reply to a message not in the archive

Quoted 6 lines · David

Quoted 2 lines · Shaohua Li
This patch introduces a bitmap based allocator.
Why not just use the one in lib/iommu-common.c? I'd like to see intel-iommu completely drop the iova.c code.

The lib/iommu-common.c uses a bitmap and a lock. This implementation actually uses a percpu_ida which completely avoids locking. It would be possible to make lib/iommu-common.c use percpu_ida too if somebody wants to do it, but I think this shouldn't be a blocker for these patches giving it has huge performance gain.

Thanks,
Shaohua

[email protected]

2015-11-25 14:46 UTC #9 lore raw

Re: [PATCH 2/4] iommu: add a bitmap based dma address allocator

In reply to a message not in the archive

Quoted 5 lines · Shaohua Li

The lib/iommu-common.c uses a bitmap and a lock. This implementation actually uses a percpu_ida which completely avoids locking. It would be possible to make lib/iommu-common.c use percpu_ida too if somebody wants to do it, but I think this shouldn't be a blocker for these patches giving it has huge performance gain.

It doesn't "completely avoids locking", the percpu_ida code uses a lock internally too. Also, what is the memory and device address space overhead per cpu?

Joerg

Woodhouse, David

2015-11-25 16:40 UTC #11 lore raw

Re: [PATCH 2/4] iommu: add a bitmap based dma address allocator

In reply to a message not in the archive

Quoted 10 lines · On Wed, 2015-11-25 at 15:46 +0100, [email protected] wrote:

Quoted 5 lines · Shaohua Li
The lib/iommu-common.c uses a bitmap and a lock. This implementation actually uses a percpu_ida which completely avoids locking. It would be possible to make lib/iommu-common.c use percpu_ida too if somebody wants to do it, but I think this shouldn't be a blocker for these patches giving it has huge performance gain.
It doesn't "completely avoids locking", the percpu_ida code uses a lock internally too. Also, what is the memory and device address space overhead per cpu?

A percpu lock doesn't bounce cachelines between CPUs very much, so from that point of view it might as well not exist :)

Signature · 4 lines

                  Sent with Evolution's ActiveSync support.

David Woodhouse                            Open Source Technology Centre
[email protected]                              Intel Corporation

Jens Axboe

2015-11-25 16:43 UTC #13 lore raw

Re: [PATCH 2/4] iommu: add a bitmap based dma address allocator

In reply to a message not in the archive

Quoted 8 lines · David

Quoted 7 lines · On Wed, 2015-11-25 at 15:46 +0100, [email protected] wrote:
Quoted 5 lines · Shaohua Li
The lib/iommu-common.c uses a bitmap and a lock. This implementation actually uses a percpu_ida which completely avoids locking. It would be possible to make lib/iommu-common.c use percpu_ida too if somebody wants to do it, but I think this shouldn't be a blocker for these patches giving it has huge performance gain.

Quoted 6 lines

Quoted 3 lines
It doesn't "completely avoids locking", the percpu_ida code uses a lock internally too. Also, what is the memory and device address space overhead per cpu?
A percpu lock doesn't bounce cachelines between CPUs very much, so from that point of view it might as well not exist :)

As long as the address space can remain more than ~50% empty, it is indeed practically lockless. Are we ever worried about higher utilization? If so, in my experience percpu_ida fails miserable near or at exhaustion.

Signature · 1 line

Jens Axboe

Shaohua Li

author

2015-11-25 17:33 UTC #15 lore raw

Re: [PATCH 2/4] iommu: add a bitmap based dma address allocator

In reply to a message not in the archive

Quoted 13 lines · Jens Axboe

Quoted 12 lines · David
Quoted 10 lines · On Wed, 2015-11-25 at 15:46 +0100, [email protected] wrote:
Quoted 5 lines · Shaohua Li
The lib/iommu-common.c uses a bitmap and a lock. This implementation actually uses a percpu_ida which completely avoids locking. It would be possible to make lib/iommu-common.c use percpu_ida too if somebody wants to do it, but I think this shouldn't be a blocker for these patches giving it has huge performance gain.
It doesn't "completely avoids locking", the percpu_ida code uses a lock internally too. Also, what is the memory and device address space overhead per cpu?

Quoted 7 lines

Quoted 2 lines
A percpu lock doesn't bounce cachelines between CPUs very much, so from that point of view it might as well not exist :)
As long as the address space can remain more than ~50% empty, it is indeed practically lockless. Are we ever worried about higher utilization? If so, in my experience percpu_ida fails miserable near or at exhaustion.

The patch uses TASK_RUNNING for tag allocation, so it doesn't wait. I thought it's ok, no?

Thanks,
Shaohua

Jens Axboe

2015-11-25 17:38 UTC #17 lore raw

Re: [PATCH 2/4] iommu: add a bitmap based dma address allocator

In reply to a message not in the archive

Quoted 17 lines · Shaohua Li

Quoted 16 lines · Jens Axboe
Quoted 14 lines · David
Quoted 10 lines · On Wed, 2015-11-25 at 15:46 +0100, [email protected] wrote:
Quoted 5 lines · Shaohua Li
The lib/iommu-common.c uses a bitmap and a lock. This implementation actually uses a percpu_ida which completely avoids locking. It would be possible to make lib/iommu-common.c use percpu_ida too if somebody wants to do it, but I think this shouldn't be a blocker for these patches giving it has huge performance gain.
It doesn't "completely avoids locking", the percpu_ida code uses a lock internally too. Also, what is the memory and device address space overhead per cpu?
A percpu lock doesn't bounce cachelines between CPUs very much, so from that point of view it might as well not exist :)

Quoted 7 lines

Quoted 4 lines
As long as the address space can remain more than ~50% empty, it is indeed practically lockless. Are we ever worried about higher utilization? If so, in my experience percpu_ida fails miserable near or at exhaustion.
The patch uses TASK_RUNNING for tag allocation, so it doesn't wait. I thought it's ok, no?

Even without the waiting it can end up sucking. If you are near exhaustion, multiple tasks allocating will end up stealing from each other.

Maybe it's not a concern here, if the space is big enough?

In any case, the pathological case isn't any worse than the normal case for the current code...

Signature · 1 line

Jens Axboe

Shaohua Li

author

2015-11-25 18:57 UTC #19 lore raw

Re: [PATCH 2/4] iommu: add a bitmap based dma address allocator

In reply to a message not in the archive

Quoted 23 lines · Jens Axboe

Quoted 22 lines · Shaohua Li
Quoted 20 lines · Jens Axboe
Quoted 8 lines · David
Quoted 7 lines · On Wed, 2015-11-25 at 15:46 +0100, [email protected] wrote:
Quoted 5 lines · Shaohua Li
The lib/iommu-common.c uses a bitmap and a lock. This implementation actually uses a percpu_ida which completely avoids locking. It would be possible to make lib/iommu-common.c use percpu_ida too if somebody wants to do it, but I think this shouldn't be a blocker for these patches giving it has huge performance gain.
Quoted 6 lines
Quoted 3 lines
It doesn't "completely avoids locking", the percpu_ida code uses a lock internally too. Also, what is the memory and device address space overhead per cpu?
A percpu lock doesn't bounce cachelines between CPUs very much, so from that point of view it might as well not exist :)
As long as the address space can remain more than ~50% empty, it is indeed practically lockless. Are we ever worried about higher utilization? If so, in my experience percpu_ida fails miserable near or at exhaustion.

Quoted 8 lines

Quoted 2 lines
The patch uses TASK_RUNNING for tag allocation, so it doesn't wait. I thought it's ok, no?
Even without the waiting it can end up sucking. If you are near exhaustion, multiple tasks allocating will end up stealing from each other.
Maybe it's not a concern here, if the space is big enough?

There are 128k tags. I think we can double it without problems within 32-bit DMA address space if necessary. But if driver holds the DMA address space, we will have space shortage. If 64-bit DMA address is on by default in the future, this will not be a concern.

Quoted 2 lines

In any case, the pathological case isn't any worse than the normal case for the current code...

Yep, it should be not worse than current spinlock.

Thanks,
Shaohua

Shaohua Li

author

2015-12-07 17:52 UTC #22 lore raw

In reply to a message not in the archive

Ping!

Quoted 40 lines · Shaohua Li

Hi,
The lock contention in iova allocation is very significant. In my iperf test with intel 10Gbps NIC card with 48 threads, I observed 99% cpu time is spending on the lock contention. In the test:
CPU utilization 100%, iperf reports ~1Gbps
The patches introduce a bitmap based approach for dma address allocation. It completetly avoids the lock contention. Run the same test:
CPU utilization 1%, iperf reports 9.3Gbps
I also tried the test with the patch, but disable bitmap. The result is the same as that without the patch.
The patches only work for DMA less than 8k, which is the most comman case we have highest request(DMA) per second. Bigger size DMA still fallback to rbtree based allocation. But if required and DAC is enabled by default, it's easy to support bigger size DMA in the bitmap allocation.
Thanks,
Shaohua
Shaohua Li (4):
iommu: alloc_iova returns a pfn
iommu: add a bitmap based dma address allocator
iommu: enable bitmap allocation for intel iommu
iommu: free_iova doesn't need lock twice
 drivers/iommu/dma-iommu.c   |  32 ++++-----
 drivers/iommu/intel-iommu.c |  96 ++++++++++++++++-----------
 drivers/iommu/iova.c        | 157 +++++++++++++++++++++++++++++++++-----------
 include/linux/iova.h        |  21 ++++--
 4 files changed, 210 insertions(+), 96 deletions(-)
Signature · 1 line
2.4.6