[PATCH] dma: fix up broken comparison in dma_alloc_from_coherent

[PATCH] dma: fix up broken comparison in dma_alloc_from_coherent

[Adrian McMenamin]

Currently this code compares a size in bytes with a size in pages.
This patch makes both sides of the comparison bytes.


Previous code (introduced in commit
58c6d3dfe436eb8cfb451981d8fdc9044eaf42da) brakes Dreamcast, this code
has been tested and works on the Dreamcast.

Signed-off-by: Adrian McMenamin <adrian@mcmen.demon.co.uk>
---

diff --git a/kernel/dma-coherent.c b/kernel/dma-coherent.c
index 0387074..8114dd7 100644
--- a/kernel/dma-coherent.c
+++ b/kernel/dma-coherent.c
@@ -112,13 +112,13 @@ int dma_alloc_from_coherent(struct device *dev,
ssize_t size,
 	struct dma_coherent_mem *mem;
 	int order = get_order(size);
 	int pageno;

 	if (!dev)
 		return 0;
 	mem = dev->dma_mem;
 	if (!mem)
 		return 0;
-	if (unlikely(size > mem->size))
+	if (unlikely(size > mem->size << PAGE_SHIFT))
  		return 0;

 	pageno = bitmap_find_free_region(mem->bitmap, mem->size, order);

Re: [PATCH] dma: fix up broken comparison in dma_alloc_from_coherent

[Adrian McMenamin]

On Tue, 2009-01-20 at 21:48 +0000, Adrian McMenamin wrote:
> Currently this code compares a size in bytes with a size in pages.
> This patch makes both sides of the comparison bytes.

Apologies, here it is without the line wrap.

Currently this comparison is made between bytes and pages. This patch
ensures it is bytes on both side of the comparison.

Signed-off-by: Adrian McMenamin <adrian@mcmen.demon.co.uk>
---

--- a/kernel/dma-coherent.c
+++ b/kernel/dma-coherent.c
@@ -118,7 +118,7 @@ int dma_alloc_from_coherent(struct device *dev, ssize_t size,
 	mem = dev->dma_mem;
 	if (!mem)
 		return 0;
-	if (unlikely(size > mem->size))
+	if (unlikely(size > mem->size << PAGE_SHIFT))
  		return 0;
 
 	pageno = bitmap_find_free_region(mem->bitmap, mem->size, order);

Re: [PATCH] dma: fix up broken comparison in dma_alloc_from_coherent

[Paul Mundt]

On Tue, Jan 20, 2009 at 09:55:07PM +0000, Adrian McMenamin wrote:
> On Tue, 2009-01-20 at 21:48 +0000, Adrian McMenamin wrote:
> > Currently this code compares a size in bytes with a size in pages.
> > This patch makes both sides of the comparison bytes.
> 
> Apologies, here it is without the line wrap.
> 
> Currently this comparison is made between bytes and pages. This patch
> ensures it is bytes on both side of the comparison.
> 
> Signed-off-by: Adrian McMenamin <adrian@mcmen.demon.co.uk>
> ---
> 
> --- a/kernel/dma-coherent.c
> +++ b/kernel/dma-coherent.c
> @@ -118,7 +118,7 @@ int dma_alloc_from_coherent(struct device *dev, ssize_t size,
>  	mem = dev->dma_mem;
>  	if (!mem)
>  		return 0;
> -	if (unlikely(size > mem->size))
> +	if (unlikely(size > mem->size << PAGE_SHIFT))
>   		return 0;
>  
>  	pageno = bitmap_find_free_region(mem->bitmap, mem->size, order);
> 
What is more concerning is that the change that introduced this:

commit 58c6d3dfe436eb8cfb451981d8fdc9044eaf42da
Author: Johannes Weiner <hannes@cmpxchg.org>
Date:   Tue Jan 6 14:43:10 2009 -0800

    dma-coherent: catch oversized requests to dma_alloc_from_coherent()

    Prevent passing an order to bitmap_find_free_region() that is larger than
    the actual bitmap can represent.

    These requests can come from device drivers that have no idea how big the
    dma region is and need to rely on dma_alloc_from_coherent() to sort it out
    for them.

    Reported-by: Guennadi Liakhovetski <lg@denx.de>
    Signed-off-by: Johannes Weiner <hannes@cmpxchg.org>
...

Claims to fix a problem that doesn't exist anywhere in-tree today, and was
obviously never tested. This looks like a sanity thing for drivers that derive
their coherent pool from passed in platform device resources.

It is equally impressive that the author of this patch modified a code path
that is only hit by platforms that provide dma_declare_coherent_memory() (sh,
arm, mips, and x86_32) and subsequently failed to Cc the primary users of the
interface.

I'll add your patch to my queue and send it off to Linus later today, thanks.

Re: [PATCH] dma: fix up broken comparison in dma_alloc_from_coherent

[Paul Mundt]

On Wed, Jan 21, 2009 at 12:39:52PM +0900, Paul Mundt wrote:
> On Tue, Jan 20, 2009 at 09:55:07PM +0000, Adrian McMenamin wrote:
> > On Tue, 2009-01-20 at 21:48 +0000, Adrian McMenamin wrote:
> > > Currently this code compares a size in bytes with a size in pages.
> > > This patch makes both sides of the comparison bytes.
> > 
> > Apologies, here it is without the line wrap.
> > 
> > Currently this comparison is made between bytes and pages. This patch
> > ensures it is bytes on both side of the comparison.
> > 
> > Signed-off-by: Adrian McMenamin <adrian@mcmen.demon.co.uk>
> > ---
> > 
> > --- a/kernel/dma-coherent.c
> > +++ b/kernel/dma-coherent.c
> > @@ -118,7 +118,7 @@ int dma_alloc_from_coherent(struct device *dev, ssize_t size,
> >  	mem = dev->dma_mem;
> >  	if (!mem)
> >  		return 0;
> > -	if (unlikely(size > mem->size))
> > +	if (unlikely(size > mem->size << PAGE_SHIFT))
> >   		return 0;
> >  
> >  	pageno = bitmap_find_free_region(mem->bitmap, mem->size, order);
> > 
And to make matters worse, this completely changes the underlying
semantics for systems that _require_ exclusive use of the per-device
region and don't permit fallback to the generic allocator. Returning 0
from dma_alloc_from_coherent() indicates that the generic allocator is
safe to fall back on, which is totally bogus in the DMA_MEMORY_EXCLUSIVE
case. This is what causes 8139too to successfully allocate memory on the
Dreamcast from totally bogus locations, which causes the generally
unhelpful error messages. If the fallback hadn't been made silently, it
would have errored out on allocating the buffers immediately.

So, something like the following should do it:

---

diff --git a/kernel/dma-coherent.c b/kernel/dma-coherent.c
index 0387074..3a2156a 100644
--- a/kernel/dma-coherent.c
+++ b/kernel/dma-coherent.c
@@ -98,7 +98,7 @@ EXPORT_SYMBOL(dma_mark_declared_memory_occupied);
  * @size:	size of requested memory area
  * @dma_handle:	This will be filled with the correct dma handle
  * @ret:	This pointer will be filled with the virtual address
- * 		to allocated area.
+ *		to allocated area.
  *
  * This function should be only called from per-arch dma_alloc_coherent()
  * to support allocation from per-device coherent memory pools.
@@ -118,31 +118,32 @@ int dma_alloc_from_coherent(struct device *dev, ssize_t size,
 	mem = dev->dma_mem;
 	if (!mem)
 		return 0;
-	if (unlikely(size > mem->size))
- 		return 0;
+
+	*ret = NULL;
+
+	if (unlikely(size > (mem->size << PAGE_SHIFT)))
+		goto err;
 
 	pageno = bitmap_find_free_region(mem->bitmap, mem->size, order);
-	if (pageno >= 0) {
-		/*
-		 * Memory was found in the per-device arena.
-		 */
-		*dma_handle = mem->device_base + (pageno << PAGE_SHIFT);
-		*ret = mem->virt_base + (pageno << PAGE_SHIFT);
-		memset(*ret, 0, size);
-	} else if (mem->flags & DMA_MEMORY_EXCLUSIVE) {
-		/*
-		 * The per-device arena is exhausted and we are not
-		 * permitted to fall back to generic memory.
-		 */
-		*ret = NULL;
-	} else {
-		/*
-		 * The per-device arena is exhausted and we are
-		 * permitted to fall back to generic memory.
-		 */
-		 return 0;
-	}
+	if (unlikely(pageno < 0))
+		goto err;
+
+	/*
+	 * Memory was found in the per-device arena.
+	 */
+	*dma_handle = mem->device_base + (pageno << PAGE_SHIFT);
+	*ret = mem->virt_base + (pageno << PAGE_SHIFT);
+	memset(*ret, 0, size);
+
 	return 1;
+
+err:
+	/*
+	 * In the case where the allocation can not be satisfied from the
+	 * per-device area, try to fall back to generic memory if the
+	 * constraints allow it.
+	 */
+	return mem->flags & DMA_MEMORY_EXCLUSIVE;
 }
 EXPORT_SYMBOL(dma_alloc_from_coherent);
 

Re: [PATCH] dma: fix up broken comparison in dma_alloc_from_coherent

[Guennadi Liakhovetski]

Nitpick:

On Wed, 21 Jan 2009, Paul Mundt wrote:

> +	/*
> +	 * Memory was found in the per-device arena.
> +	 */

s/arena/area/ ?

Thanks
Guennadi
---
Guennadi Liakhovetski, Ph.D.

DENX Software Engineering GmbH,     MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: +49-8142-66989-0 Fax: +49-8142-66989-80  Email: office@denx.de

Re: [PATCH] dma: fix up broken comparison in dma_alloc_from_coherent

[Paul Mundt]

On Wed, Jan 21, 2009 at 09:29:39AM +0100, Guennadi Liakhovetski wrote:
> Nitpick:
> 
> On Wed, 21 Jan 2009, Paul Mundt wrote:
> 
> > +	/*
> > +	 * Memory was found in the per-device arena.
> > +	 */
> 
> s/arena/area/ ?
> 
That was in the original, I'll fix it up before sending it off.

Re: [PATCH] dma: fix up broken comparison in dma_alloc_from_coherent

[Andrew Morton]

On Wed, 21 Jan 2009 17:11:19 +0900
Paul Mundt <lethal@linux-sh.org> wrote:

> @@ -118,31 +118,32 @@ int dma_alloc_from_coherent(struct device *dev, ssize_t size,
>  	mem = dev->dma_mem;
>  	if (!mem)
>  		return 0;
> -	if (unlikely(size > mem->size))
> - 		return 0;
> +
> +	*ret = NULL;
> +
> +	if (unlikely(size > (mem->size << PAGE_SHIFT)))
> +		goto err;

Looks a bit broken on 64-bit.

`size' is ssize_t (long).

`mem->size' is `int'.

The left shift can overflow and cause badnesses.

> +	*dma_handle = mem->device_base + (pageno << PAGE_SHIFT);
> +	*ret = mem->virt_base + (pageno << PAGE_SHIFT);

Ditto.


Maybe it's a can't-happen (why?), but...

Re: [PATCH] dma: fix up broken comparison in dma_alloc_from_coherent

[Paul Mundt]

On Tue, Jan 27, 2009 at 01:48:31PM -0800, Andrew Morton wrote:
> On Wed, 21 Jan 2009 17:11:19 +0900
> Paul Mundt <lethal@linux-sh.org> wrote:
> 
> > @@ -118,31 +118,32 @@ int dma_alloc_from_coherent(struct device *dev, ssize_t size,
> >  	mem = dev->dma_mem;
> >  	if (!mem)
> >  		return 0;
> > -	if (unlikely(size > mem->size))
> > - 		return 0;
> > +
> > +	*ret = NULL;
> > +
> > +	if (unlikely(size > (mem->size << PAGE_SHIFT)))
> > +		goto err;
> 
> Looks a bit broken on 64-bit.
> 
> `size' is ssize_t (long).
> 
> `mem->size' is `int'.
> 
> The left shift can overflow and cause badnesses.
> 
> > +	*dma_handle = mem->device_base + (pageno << PAGE_SHIFT);
> > +	*ret = mem->virt_base + (pageno << PAGE_SHIFT);
> 
> Ditto.
> 
> 
> Maybe it's a can't-happen (why?), but...

It is probably worth adding casts to avoid the potential for overflow,
but it's not likely that this would ever be a problem in practice.
Someone would need a pretty big per-device memory area for this to ever
overflow anyways, and if the device has that much memory, people are
probably going to want to do something else with it besides designating
all of it for DMA buffer usage ;-)

Re: [PATCH] dma: fix up broken comparison in dma_alloc_from_coherent

[Guennadi Liakhovetski]

On Wed, 28 Jan 2009, Paul Mundt wrote:

> On Tue, Jan 27, 2009 at 01:48:31PM -0800, Andrew Morton wrote:
> > On Wed, 21 Jan 2009 17:11:19 +0900
> > Paul Mundt <lethal@linux-sh.org> wrote:
> > 
> > > @@ -118,31 +118,32 @@ int dma_alloc_from_coherent(struct device *dev, ssize_t size,
> > >  	mem = dev->dma_mem;
> > >  	if (!mem)
> > >  		return 0;
> > > -	if (unlikely(size > mem->size))
> > > - 		return 0;
> > > +
> > > +	*ret = NULL;
> > > +
> > > +	if (unlikely(size > (mem->size << PAGE_SHIFT)))
> > > +		goto err;
> > 
> > Looks a bit broken on 64-bit.

Not related to the 64-bit dangers, but using bitmap_find_free_region() in 
dma_alloc_from_coherent() breaks in most non-spectacular ways again and 
again. This loop and test in bitmap_find_free_region()

	for (pos = 0; pos < bits; pos += (1 << order))
		if (__reg_op(bitmap, pos, order, REG_OP_ISFREE))
			break;
	if (pos == bits)
		return -ENOMEM;

can only return an error (-ENOMEM) if bits is a multiple of (1 << order), 
which is, for instance, true, if bits is (also) a power of 2. Which 
doesn't seem to be necessarily the case with dma_alloc_from_coherent(). 
Where shall this one be fixed - in bitmap or in DMA? The correct test in 
bitmap code seems to be

	if (pos + (1 << order) > bits)
		return -ENOMEM;

and I don't see a way to fix this in dma. Checking afterwards is too late 
- the current bitmap_find_free_region() will (with a bit of luck) quietly 
overwrite data beyond bits.

Thanks
Guennadi
---
Guennadi Liakhovetski, Ph.D.

DENX Software Engineering GmbH,     MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: +49-8142-66989-0 Fax: +49-8142-66989-80  Email: office@denx.de

[PATCH] fix broken size test in bitmap_find_free_region()

[Guennadi Liakhovetski]

This loop and test in bitmap_find_free_region()

	for (pos = 0; pos < bits; pos += (1 << order))
		if (__reg_op(bitmap, pos, order, REG_OP_ISFREE))
			break;
	if (pos == bits)
		return -ENOMEM;

can only return an error (-ENOMEM) if bits is a multiple of (1 << order), 
which is, for instance, true, if bits is (also) a power of 2. This 
is not necessarily the case with dma_alloc_from_coherent(). A failure to 
recognise too large a request leads in dma_alloc_from_coherent() to 
accessing beyond available memory, and to writing beyond the bitmap.

Signed-off-by: Guennadi Liakhovetski <lg@denx.de>
---

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 1338469..d49c37f 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -953,7 +953,7 @@ int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
 	for (pos = 0; pos < bits; pos += (1 << order))
 		if (__reg_op(bitmap, pos, order, REG_OP_ISFREE))
 			break;
-	if (pos == bits)
+	if (pos + (1 << order) > bits)
 		return -ENOMEM;
 	__reg_op(bitmap, pos, order, REG_OP_ALLOC);
 	return pos;

Re: [PATCH] fix broken size test in bitmap_find_free_region()

[Andrew Morton]

On Fri, 6 Feb 2009 13:22:33 +0100 (CET)
Guennadi Liakhovetski <lg@denx.de> wrote:

> This loop and test in bitmap_find_free_region()
> 
> 	for (pos = 0; pos < bits; pos += (1 << order))
> 		if (__reg_op(bitmap, pos, order, REG_OP_ISFREE))
> 			break;
> 	if (pos == bits)
> 		return -ENOMEM;
> 
> can only return an error (-ENOMEM) if bits is a multiple of (1 << order), 
> which is, for instance, true, if bits is (also) a power of 2. This 
> is not necessarily the case with dma_alloc_from_coherent(). A failure to 
> recognise too large a request leads in dma_alloc_from_coherent() to 
> accessing beyond available memory, and to writing beyond the bitmap.
> 

Do we have any reports of dma_alloc_from_coherent() actually behaving
in that way?


> ---
> 
> diff --git a/lib/bitmap.c b/lib/bitmap.c
> index 1338469..d49c37f 100644
> --- a/lib/bitmap.c
> +++ b/lib/bitmap.c
> @@ -953,7 +953,7 @@ int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
>  	for (pos = 0; pos < bits; pos += (1 << order))
>  		if (__reg_op(bitmap, pos, order, REG_OP_ISFREE))
>  			break;
> -	if (pos == bits)
> +	if (pos + (1 << order) > bits)
>  		return -ENOMEM;
>  	__reg_op(bitmap, pos, order, REG_OP_ALLOC);
>  	return pos;

Re: [PATCH] fix broken size test in bitmap_find_free_region()

[Guennadi Liakhovetski]

On Fri, 6 Feb 2009, Andrew Morton wrote:

> On Fri, 6 Feb 2009 13:22:33 +0100 (CET)
> Guennadi Liakhovetski <lg@denx.de> wrote:
> 
> > This loop and test in bitmap_find_free_region()
> > 
> > 	for (pos = 0; pos < bits; pos += (1 << order))
> > 		if (__reg_op(bitmap, pos, order, REG_OP_ISFREE))
> > 			break;
> > 	if (pos == bits)
> > 		return -ENOMEM;
> > 
> > can only return an error (-ENOMEM) if bits is a multiple of (1 << order), 
> > which is, for instance, true, if bits is (also) a power of 2. This 
> > is not necessarily the case with dma_alloc_from_coherent(). A failure to 
> > recognise too large a request leads in dma_alloc_from_coherent() to 
> > accessing beyond available memory, and to writing beyond the bitmap.
> > 
> 
> Do we have any reports of dma_alloc_from_coherent() actually behaving
> in that way?

Does this count:

http://marc.info/?l=linux-kernel&m=123313185800954&w=2

Yes, I did see this behaviour with a video driver, that's still not in the 
mainline (expected in the next cycle), using videobuf-dma-contig.c in the 
__videobuf_mmap_mapper() function.

Thanks
Guennadi
---
Guennadi Liakhovetski, Ph.D.

DENX Software Engineering GmbH,     MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: +49-8142-66989-0 Fax: +49-8142-66989-80  Email: office@denx.de