[PATCH] avoid endless loops in lib/swiotlb.c

[PATCH] avoid endless loops in lib/swiotlb.c

[Jan Beulich]

Commit 681cc5cd3efbeafca6386114070e0bfb5012e249 introduced two
possibilities for entering an endless loop in lib/swiotlb.c:

- if max_slots is zero (possible if mask is ~0UL)
- if the number of slots requested fits into a swiotlb segment, but is
  too large for the part of a segment which remains after considering
  offset_slots

Signed-off-by: Jan Beulich <jbeulich@novell.com>
Cc: FUJITA Tomonori <fujita.tomonori@lab.ntt.co.jp>
Cc: Andrew Morton <akpm@linux-foundation.org>

---
 lib/swiotlb.c |   30 ++++++++++++++++--------------
 1 file changed, 16 insertions(+), 14 deletions(-)

--- linux-2.6.25-rc5/lib/swiotlb.c	2008-03-13 09:53:50.000000000 +0100
+++ 2.6.25-rc5-swiotlb-endless-loop/lib/swiotlb.c	2008-03-12 15:17:49.000000000 +0100
@@ -310,7 +310,9 @@ map_single(struct device *hwdev, char *b
 	start_dma_addr = virt_to_bus(io_tlb_start) & mask;
 
 	offset_slots = ALIGN(start_dma_addr, 1 << IO_TLB_SHIFT) >> IO_TLB_SHIFT;
-	max_slots = ALIGN(mask + 1, 1 << IO_TLB_SHIFT) >> IO_TLB_SHIFT;
+	max_slots = mask + 1
+		    ? ALIGN(mask + 1, 1 << IO_TLB_SHIFT) >> IO_TLB_SHIFT
+		    : 1UL << (BITS_PER_LONG - IO_TLB_SHIFT);
 
 	/*
 	 * For mappings greater than a page, we limit the stride (and
@@ -333,16 +335,18 @@ map_single(struct device *hwdev, char *b
 		index = ALIGN(io_tlb_index, stride);
 		if (index >= io_tlb_nslabs)
 			index = 0;
-
-		while (is_span_boundary(index, nslots, offset_slots,
-					max_slots)) {
-			index += stride;
-			if (index >= io_tlb_nslabs)
-				index = 0;
-		}
 		wrap = index;
 
 		do {
+			while (is_span_boundary(index, nslots, offset_slots,
+						max_slots)) {
+				index += stride;
+				if (index >= io_tlb_nslabs)
+					index = 0;
+				if (index == wrap)
+					goto not_found;
+			}
+
 			/*
 			 * If we find a slot that indicates we have 'nslots'
 			 * number of contiguous buffers, we allocate the
@@ -367,14 +371,12 @@ map_single(struct device *hwdev, char *b
 
 				goto found;
 			}
-			do {
-				index += stride;
-				if (index >= io_tlb_nslabs)
-					index = 0;
-			} while (is_span_boundary(index, nslots, offset_slots,
-						  max_slots));
+			index += stride;
+			if (index >= io_tlb_nslabs)
+				index = 0;
 		} while (index != wrap);
 
+  not_found:
 		spin_unlock_irqrestore(&io_tlb_lock, flags);
 		return NULL;
 	}

Re: [PATCH] avoid endless loops in lib/swiotlb.c

[FUJITA Tomonori]

On Thu, 13 Mar 2008 09:13:30 +0000
"Jan Beulich" <jbeulich@novell.com> wrote:

> Commit 681cc5cd3efbeafca6386114070e0bfb5012e249 introduced two
> possibilities for entering an endless loop in lib/swiotlb.c:
> 
> - if max_slots is zero (possible if mask is ~0UL)

Yeah, max_slots can not be zero. There are no drivers that have such
mask. I'm not sure that we will have.

I exported a function, iommu_is_span_boundary in lib/iommu-helper.c
that does the same thing that is_span_boundary does for SPARC and
PARISC IOMMUs. iommu_is_span_boundary does this checking. I've
attached a patch to convert swiotlb to use it.

If we need to think about the possibility of handling such mask, I
think that it would be better to create a helper function to handle
this in lib/iommu-helper.c since several IOMMUs do the same thing.


> - if the number of slots requested fits into a swiotlb segment, but is
>   too large for the part of a segment which remains after considering
>   offset_slots

Sorry, I'm not sure what you mean. Can you give me an actual example
numbers that leads to that?


=
From: FUJITA Tomonori <fujita.tomonori@lab.ntt.co.jp>
Subject: [PATCH] SWIOTLB: use iommu_is_span_boundary helper function

iommu_is_span_boundary in lib/iommu-helper.c was exported for PARISC
IOMMUs (commit 3715863aa142c4f4c5208f5f3e5e9bac06006d2f). SWIOTLB can
use it.

Signed-off-by: FUJITA Tomonori <fujita.tomonori@lab.ntt.co.jp>
---
 arch/ia64/Kconfig |    3 +++
 arch/x86/Kconfig  |    5 ++---
 lib/swiotlb.c     |   19 ++++++-------------
 3 files changed, 11 insertions(+), 16 deletions(-)

diff --git a/arch/ia64/Kconfig b/arch/ia64/Kconfig
index 8fa3faf..a33d7ed 100644
--- a/arch/ia64/Kconfig
+++ b/arch/ia64/Kconfig
@@ -46,6 +46,9 @@ config MMU
 config SWIOTLB
        bool
 
+config IOMMU_HELPER
+       bool
+
 config GENERIC_LOCKBREAK
 	bool
 	default y
diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index 237fc12..aff96a7 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -477,9 +477,6 @@ config CALGARY_IOMMU_ENABLED_BY_DEFAULT
 	  Calgary anyway, pass 'iommu=calgary' on the kernel command line.
 	  If unsure, say Y.
 
-config IOMMU_HELPER
-	def_bool (CALGARY_IOMMU || GART_IOMMU)
-
 # need this always selected by IOMMU for the VIA workaround
 config SWIOTLB
 	bool
@@ -490,6 +487,8 @@ config SWIOTLB
 	  access 32-bits of memory can be used on systems with more than
 	  3 GB of memory. If unsure, say Y.
 
+config IOMMU_HELPER
+	def_bool (CALGARY_IOMMU || GART_IOMMU || SWIOTLB)
 
 config NR_CPUS
 	int "Maximum number of CPUs (2-255)"
diff --git a/lib/swiotlb.c b/lib/swiotlb.c
index 4bb5a11..2c6392a 100644
--- a/lib/swiotlb.c
+++ b/lib/swiotlb.c
@@ -31,6 +31,7 @@
 
 #include <linux/init.h>
 #include <linux/bootmem.h>
+#include <linux/iommu-helper.h>
 
 #define OFFSET(val,align) ((unsigned long)	\
 	                   ( (val) & ( (align) - 1)))
@@ -282,15 +283,6 @@ address_needs_mapping(struct device *hwdev, dma_addr_t addr)
 	return (addr & ~mask) != 0;
 }
 
-static inline unsigned int is_span_boundary(unsigned int index,
-					    unsigned int nslots,
-					    unsigned long offset_slots,
-					    unsigned long max_slots)
-{
-	unsigned long offset = (offset_slots + index) & (max_slots - 1);
-	return offset + nslots > max_slots;
-}
-
 /*
  * Allocates bounce buffer and returns its kernel virtual address.
  */
@@ -334,8 +326,8 @@ map_single(struct device *hwdev, char *buffer, size_t size, int dir)
 		if (index >= io_tlb_nslabs)
 			index = 0;
 
-		while (is_span_boundary(index, nslots, offset_slots,
-					max_slots)) {
+		while (iommu_is_span_boundary(index, nslots, offset_slots,
+					      max_slots)) {
 			index += stride;
 			if (index >= io_tlb_nslabs)
 				index = 0;
@@ -371,8 +363,9 @@ map_single(struct device *hwdev, char *buffer, size_t size, int dir)
 				index += stride;
 				if (index >= io_tlb_nslabs)
 					index = 0;
-			} while (is_span_boundary(index, nslots, offset_slots,
-						  max_slots));
+			} while (iommu_is_span_boundary(index, nslots,
+							offset_slots,
+							max_slots));
 		} while (index != wrap);
 
 		spin_unlock_irqrestore(&io_tlb_lock, flags);
-- 
1.5.3.7

Re: [PATCH] avoid endless loops in lib/swiotlb.c

[Jan Beulich]

>>> FUJITA Tomonori <tomof@acm.org> 14.03.08 10:35 >>>
>On Thu, 13 Mar 2008 09:13:30 +0000
>"Jan Beulich" <jbeulich@novell.com> wrote:
>
>> Commit 681cc5cd3efbeafca6386114070e0bfb5012e249 introduced two
>> possibilities for entering an endless loop in lib/swiotlb.c:
>> 
>> - if max_slots is zero (possible if mask is ~0UL)
>
>Yeah, max_slots can not be zero. There are no drivers that have such
>mask. I'm not sure that we will have.

You mean no current, in-tree drivers do this, and you imply the code
is only used on 64-bits. Since Xen uses this file even for 32-bits, I had
run into the case, and there's nothing preventing an in-tree driver
from setting the mask to ~0UL, which would then result in a perhaps
difficult to debug hang. For that reason, it seems better to me to fix
this latent bug right away.

>...
>
>> - if the number of slots requested fits into a swiotlb segment, but is
>>   too large for the part of a segment which remains after considering
>>   offset_slots
>
>Sorry, I'm not sure what you mean. Can you give me an actual example
>numbers that leads to that?

For one part, it can happen if nslots > max_slots (which is a driver
error [except for the case above where max_slots erroneously got set
to zero], but shouldn't lead to a silent hang, especially as it didn't do so
before).

For another part, requesting e.g. a transfer of 128k with a segment
mask of 128k when the IOTLB isn't aligned to a 128k boundary would
again lead to a silent hang, as would various cases where the request
exceeds the segment size (and the segment mask is sufficiently small).
Neither of these cases got stuck in the old code.

Beyond that, maybe I was too quick in concluding this could happen
even in less unusual cases - I think I didn't pay close enough attention
to the fact that offset_slots + index gets masked by max_slots - 1.
But even then I think the code looks simpler/safer and is smaller with
the adjusted logic.

Jan

Re: [PATCH] avoid endless loops in lib/swiotlb.c

[FUJITA Tomonori]

On Fri, 14 Mar 2008 10:18:09 +0000
"Jan Beulich" <jbeulich@novell.com> wrote:

> >> - if the number of slots requested fits into a swiotlb segment, but is
> >>   too large for the part of a segment which remains after considering
> >>   offset_slots
> >
> >Sorry, I'm not sure what you mean. Can you give me an actual example
> >numbers that leads to that?
> 
> For one part, it can happen if nslots > max_slots (which is a driver
> error [except for the case above where max_slots erroneously got set
> to zero], but shouldn't lead to a silent hang, especially as it didn't do so
> before).
> 
> For another part, requesting e.g. a transfer of 128k with a segment
> mask of 128k when the IOTLB isn't aligned to a 128k boundary would
> again lead to a silent hang, as would various cases where the request
> exceeds the segment size (and the segment mask is sufficiently small).
> Neither of these cases got stuck in the old code.
> 
> Beyond that, maybe I was too quick in concluding this could happen
> even in less unusual cases - I think I didn't pay close enough attention
> to the fact that offset_slots + index gets masked by max_slots - 1.
> But even then I think the code looks simpler/safer and is smaller with
> the adjusted logic.

I don't think that the old code hits the problems (endless loops or
silent hang) that you explained, but I agree that the patch made the
code simpler a bit.

Thanks,