[PATCH] bitmap: fix bitmap_find_free_region()

[PATCH] bitmap: fix bitmap_find_free_region()

[Guennadi Liakhovetski]

Currently bitmap_find_free_region() assumes, that the requested region 
size is smaller than the entire bitmap. If this is not the case it fails 
to detect it and returns success, while pointing at a position outside of 
the region.

Signed-off-by: Guennadi Liakhovetski <lg@denx.de>
Cc: Andrew Morton <akpm@linux-foundation.org>
---
It is hard to believe, that this is a bug, last time this code was touched 
in 2006... Or should the caller guarantee, that the requested region is 
not larger than the bitmap? Then dma_alloc_from_coherent() is buggy, which 
is where I hit this bug. But it seems to me bitmap_find_free_region() 
should be fixed.

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 1338469..079c5e3 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -950,6 +950,9 @@ int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
 {
 	int pos;		/* scans bitmap by regions of size order */
 
+	if (bits < 1 << order)
+		return -ENOMEM;
+
 	for (pos = 0; pos < bits; pos += (1 << order))
 		if (__reg_op(bitmap, pos, order, REG_OP_ISFREE))
 			break;

Re: [PATCH] bitmap: fix bitmap_find_free_region()

[Johannes Weiner]

On Fri, Dec 19, 2008 at 12:26:41PM +0100, Guennadi Liakhovetski wrote:
> Currently bitmap_find_free_region() assumes, that the requested region 
> size is smaller than the entire bitmap. If this is not the case it fails 
> to detect it and returns success, while pointing at a position outside of 
> the region.
> 
> Signed-off-by: Guennadi Liakhovetski <lg@denx.de>
> Cc: Andrew Morton <akpm@linux-foundation.org>
> ---
> It is hard to believe, that this is a bug, last time this code was touched 
> in 2006... Or should the caller guarantee, that the requested region is 
> not larger than the bitmap? Then dma_alloc_from_coherent() is buggy, which 
> is where I hit this bug. But it seems to me bitmap_find_free_region() 
> should be fixed.
> 
> diff --git a/lib/bitmap.c b/lib/bitmap.c
> index 1338469..079c5e3 100644
> --- a/lib/bitmap.c
> +++ b/lib/bitmap.c
> @@ -950,6 +950,9 @@ int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
>  {
>  	int pos;		/* scans bitmap by regions of size order */
>  
> +	if (bits < 1 << order)
> +		return -ENOMEM;

I think this is an error on the callsite, so a WARN_ON() might be good
to spot these.  I would be interested in the callpath that triggered
this bug for you.

And return -ENOSPC?

	Hannes

Re: [PATCH] bitmap: fix bitmap_find_free_region()

[Guennadi Liakhovetski]

On Fri, 19 Dec 2008, Johannes Weiner wrote:

> On Fri, Dec 19, 2008 at 12:26:41PM +0100, Guennadi Liakhovetski wrote:
> > Currently bitmap_find_free_region() assumes, that the requested region 
> > size is smaller than the entire bitmap. If this is not the case it fails 
> > to detect it and returns success, while pointing at a position outside of 
> > the region.
> > 
> > Signed-off-by: Guennadi Liakhovetski <lg@denx.de>
> > Cc: Andrew Morton <akpm@linux-foundation.org>
> > ---
> > It is hard to believe, that this is a bug, last time this code was touched 
> > in 2006... Or should the caller guarantee, that the requested region is 
> > not larger than the bitmap? Then dma_alloc_from_coherent() is buggy, which 
> > is where I hit this bug. But it seems to me bitmap_find_free_region() 
> > should be fixed.
> > 
> > diff --git a/lib/bitmap.c b/lib/bitmap.c
> > index 1338469..079c5e3 100644
> > --- a/lib/bitmap.c
> > +++ b/lib/bitmap.c
> > @@ -950,6 +950,9 @@ int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
> >  {
> >  	int pos;		/* scans bitmap by regions of size order */
> >  
> > +	if (bits < 1 << order)
> > +		return -ENOMEM;
> 
> I think this is an error on the callsite, so a WARN_ON() might be good
> to spot these.  I would be interested in the callpath that triggered
> this bug for you.

As I said above it's called from dma_alloc_from_coherent() from 
dma_alloc_coherent().

> And return -ENOSPC?

So, you agree that a check should be added to bitmap_find_free_region()? 
As for details - to warn or not to warn and what error code to return, 
that can be discussed, although "No space left on device" doesn't seem to 
fit very well IMHO:-)

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] bitmap: fix bitmap_find_free_region()

[Pekka Enberg]

On Fri, 19 Dec 2008, Johannes Weiner wrote:
>> And return -ENOSPC?

On Fri, Dec 19, 2008 at 3:18 PM, Guennadi Liakhovetski <lg@denx.de> wrote:
> So, you agree that a check should be added to bitmap_find_free_region()?
> As for details - to warn or not to warn and what error code to return,
> that can be discussed, although "No space left on device" doesn't seem to
> fit very well IMHO:-)

Yeah, but ENOMEM, on the other had, is mostly for out-of-memory
conditions so EINVAL might be more appropriate.

Re: [PATCH] bitmap: fix bitmap_find_free_region()

[Johannes Weiner]

On Fri, Dec 19, 2008 at 02:18:22PM +0100, Guennadi Liakhovetski wrote:
> On Fri, 19 Dec 2008, Johannes Weiner wrote:
> 
> > On Fri, Dec 19, 2008 at 12:26:41PM +0100, Guennadi Liakhovetski wrote:
> > > Currently bitmap_find_free_region() assumes, that the requested region 
> > > size is smaller than the entire bitmap. If this is not the case it fails 
> > > to detect it and returns success, while pointing at a position outside of 
> > > the region.
> > > 
> > > Signed-off-by: Guennadi Liakhovetski <lg@denx.de>
> > > Cc: Andrew Morton <akpm@linux-foundation.org>
> > > ---
> > > It is hard to believe, that this is a bug, last time this code was touched 
> > > in 2006... Or should the caller guarantee, that the requested region is 
> > > not larger than the bitmap? Then dma_alloc_from_coherent() is buggy, which 
> > > is where I hit this bug. But it seems to me bitmap_find_free_region() 
> > > should be fixed.
> > > 
> > > diff --git a/lib/bitmap.c b/lib/bitmap.c
> > > index 1338469..079c5e3 100644
> > > --- a/lib/bitmap.c
> > > +++ b/lib/bitmap.c
> > > @@ -950,6 +950,9 @@ int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
> > >  {
> > >  	int pos;		/* scans bitmap by regions of size order */
> > >  
> > > +	if (bits < 1 << order)
> > > +		return -ENOMEM;
> > 
> > I think this is an error on the callsite, so a WARN_ON() might be good
> > to spot these.  I would be interested in the callpath that triggered
> > this bug for you.
> 
> As I said above it's called from dma_alloc_from_coherent() from 
> dma_alloc_coherent().

Sure, but someone must have done dma_declare_coherent_memory() before
with a size smaller than it later passed to dma_alloc_coherent(), no?

I think we should add the check, WARN if it's true and return an
appropriate error number.  It will be handled gracefully then and we
still know which callsite screwed up.

	Hannes

Re: [PATCH] bitmap: fix bitmap_find_free_region()

[Guennadi Liakhovetski]

On Fri, 19 Dec 2008, Johannes Weiner wrote:

> On Fri, Dec 19, 2008 at 02:18:22PM +0100, Guennadi Liakhovetski wrote:
> > On Fri, 19 Dec 2008, Johannes Weiner wrote:
> > 
> > > On Fri, Dec 19, 2008 at 12:26:41PM +0100, Guennadi Liakhovetski wrote:
> > > > Currently bitmap_find_free_region() assumes, that the requested region 
> > > > size is smaller than the entire bitmap. If this is not the case it fails 
> > > > to detect it and returns success, while pointing at a position outside of 
> > > > the region.
> > > > 
> > > > Signed-off-by: Guennadi Liakhovetski <lg@denx.de>
> > > > Cc: Andrew Morton <akpm@linux-foundation.org>
> > > > ---
> > > > It is hard to believe, that this is a bug, last time this code was touched 
> > > > in 2006... Or should the caller guarantee, that the requested region is 
> > > > not larger than the bitmap? Then dma_alloc_from_coherent() is buggy, which 
> > > > is where I hit this bug. But it seems to me bitmap_find_free_region() 
> > > > should be fixed.
> > > > 
> > > > diff --git a/lib/bitmap.c b/lib/bitmap.c
> > > > index 1338469..079c5e3 100644
> > > > --- a/lib/bitmap.c
> > > > +++ b/lib/bitmap.c
> > > > @@ -950,6 +950,9 @@ int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
> > > >  {
> > > >  	int pos;		/* scans bitmap by regions of size order */
> > > >  
> > > > +	if (bits < 1 << order)
> > > > +		return -ENOMEM;
> > > 
> > > I think this is an error on the callsite, so a WARN_ON() might be good
> > > to spot these.  I would be interested in the callpath that triggered
> > > this bug for you.
> > 
> > As I said above it's called from dma_alloc_from_coherent() from 
> > dma_alloc_coherent().
> 
> Sure, but someone must have done dma_declare_coherent_memory() before
> with a size smaller than it later passed to dma_alloc_coherent(), no?

Yes, this is the i.MX31 video capture driver (patch has once been 
submitted, new version in work). The thing is, we reserve and declare a 
fixed size coherent region in the board code at start-up, but then what 
the driver allocates depends on what a user-space application requests - 
what size video frame and how many buffers. And the driver does not check 
how much coherent memory it has available, it relies on 
dma_alloc_coherent() to tell. In fact, the actual i.MX31 camera driver 
knows nothing about this allocation, this all happens automatically in 
soc_camera.c::soc_camera_mmap() -> 
videobuf-dma-contig.c::__videobuf_mmap_mapper().

> I think we should add the check, WARN if it's true and return an
> appropriate error number.  It will be handled gracefully then and we
> still know which callsite screwed up.

Well, given above you'd get warning each time the user requests too big a 
frame or too many buffers, which is not nice.

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] bitmap: fix bitmap_find_free_region()

[Johannes Weiner]

On Fri, Dec 19, 2008 at 04:09:42PM +0100, Guennadi Liakhovetski wrote:
> Yes, this is the i.MX31 video capture driver (patch has once been 
> submitted, new version in work). The thing is, we reserve and declare a 
> fixed size coherent region in the board code at start-up, but then what 
> the driver allocates depends on what a user-space application requests - 
> what size video frame and how many buffers. And the driver does not check 
> how much coherent memory it has available, it relies on 
> dma_alloc_coherent() to tell. In fact, the actual i.MX31 camera driver 
> knows nothing about this allocation, this all happens automatically in 
> soc_camera.c::soc_camera_mmap() -> 
> videobuf-dma-contig.c::__videobuf_mmap_mapper().
> 
> > I think we should add the check, WARN if it's true and return an
> > appropriate error number.  It will be handled gracefully then and we
> > still know which callsite screwed up.
> 
> Well, given above you'd get warning each time the user requests too big a 
> frame or too many buffers, which is not nice.

Indeed, that's BS then.

The region size information is local to the dma-coherent code.  So
either the callsite keeps track of the size itself or, if it can not
as in your case, we should check for the correct size on exactly that
layer of code, as well.  Does that sound reasonable?

Why do other driver not need this?  I will look further into it.  If
it's any use, here is a patch that does the check on the allocation
level.

---
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>
---

diff --git a/kernel/dma-coherent.c b/kernel/dma-coherent.c
index f013a0c..56ea73e 100644
--- a/kernel/dma-coherent.c
+++ b/kernel/dma-coherent.c
@@ -112,6 +112,9 @@ int dma_alloc_from_coherent(struct device *dev, ssize_t size,
 	struct dma_coherent_mem *mem = dev ? dev->dma_mem : NULL;
 	int order = get_order(size);
 
+	if (unlikely(size > mem->size))
+		return 0;
+
 	if (mem) {
 		int page = bitmap_find_free_region(mem->bitmap, mem->size,
 						     order);

Re: [PATCH] bitmap: fix bitmap_find_free_region()

[Guennadi Liakhovetski]

On Fri, 19 Dec 2008, Johannes Weiner wrote:

> On Fri, Dec 19, 2008 at 04:09:42PM +0100, Guennadi Liakhovetski wrote:
> > Yes, this is the i.MX31 video capture driver (patch has once been 
> > submitted, new version in work). The thing is, we reserve and declare a 
> > fixed size coherent region in the board code at start-up, but then what 
> > the driver allocates depends on what a user-space application requests - 
> > what size video frame and how many buffers. And the driver does not check 
> > how much coherent memory it has available, it relies on 
> > dma_alloc_coherent() to tell. In fact, the actual i.MX31 camera driver 
> > knows nothing about this allocation, this all happens automatically in 
> > soc_camera.c::soc_camera_mmap() -> 
> > videobuf-dma-contig.c::__videobuf_mmap_mapper().
> > 
> > > I think we should add the check, WARN if it's true and return an
> > > appropriate error number.  It will be handled gracefully then and we
> > > still know which callsite screwed up.
> > 
> > Well, given above you'd get warning each time the user requests too big a 
> > frame or too many buffers, which is not nice.
> 
> Indeed, that's BS then.
> 
> The region size information is local to the dma-coherent code.  So
> either the callsite keeps track of the size itself or, if it can not
> as in your case, we should check for the correct size on exactly that
> layer of code, as well.  Does that sound reasonable?
> 
> Why do other driver not need this?  I will look further into it.  If
> it's any use, here is a patch that does the check on the allocation
> level.

Well, I don't quite understand. Doesn't bitmap_find_free_region() _have_ 
to return an error if the request cannot be satisfied? Isn't it what it 
does if after scanning the bitmap no suitable free region is found? What's 
the difference? Why don't we want to fix _that_ function? It also has 
other users - currently I see 3 of them in the kernel:

mm/vmalloc.c
arch/powerpc/sysdev/msi_bitmap.c (5 occurrences)
arch/sh/kernel/cpu/sh4/sq.c

are we sure that they all are safe wrt to this problem?

Yes, I understand that the caller _can_ verify whether the requested 
region at all fits into the bitmap, but from the PoV of offering a 
consistent API this seems strange.

Thanks
Guennadi

> 
> ---
> 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>
> ---
> 
> diff --git a/kernel/dma-coherent.c b/kernel/dma-coherent.c
> index f013a0c..56ea73e 100644
> --- a/kernel/dma-coherent.c
> +++ b/kernel/dma-coherent.c
> @@ -112,6 +112,9 @@ int dma_alloc_from_coherent(struct device *dev, ssize_t size,
>  	struct dma_coherent_mem *mem = dev ? dev->dma_mem : NULL;
>  	int order = get_order(size);
>  
> +	if (unlikely(size > mem->size))
> +		return 0;
> +
>  	if (mem) {
>  		int page = bitmap_find_free_region(mem->bitmap, mem->size,
>  						     order);
> 
> 

---
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] bitmap: fix bitmap_find_free_region()

[Johannes Weiner]

On Sat, Dec 20, 2008 at 12:19:46AM +0100, Guennadi Liakhovetski wrote:
> Well, I don't quite understand. Doesn't bitmap_find_free_region() _have_ 
> to return an error if the request cannot be satisfied? Isn't it what it 
> does if after scanning the bitmap no suitable free region is found?

There is a difference here.  In the case it already checks, the
request was sane but couldn't be satisfied due to prior requests.
This is an expected situation on the bitmap allocator level.

The check you want to add is for fixing up the caller.

This API is especially clear on that separation because the caller
even has to pass in the size of the bitmap, so itself should ensure
that the combination of bitmap size and request size is sane.

> What's the difference? Why don't we want to fix _that_ function? It
> also has other users - currently I see 3 of them in the kernel:
> 
> mm/vmalloc.c

This has its own sanity checks.  It's a bug for the user of vb_alloc()
to pass a size that is larger than VMAP_MAX_ALLOC pages and the bitmap
has a minimum of VMAP_MAX_ALLOC * 2 bits.

> arch/powerpc/sysdev/msi_bitmap.c (5 occurrences)

The users allocating irqs from there seem all sane and doing only low
orders.  Not yet quite through, though.

> arch/sh/kernel/cpu/sh4/sq.c

Not yet looked into it.

> Yes, I understand that the caller _can_ verify whether the requested 
> region at all fits into the bitmap, but from the PoV of offering a 
> consistent API this seems strange.

Not really.  The user that is supposed to use the bitmap also sets it
up.  If the requests are bogus wrt the original parameters it's the
users fault, not that of the API.

> Thanks
> Guennadi

	Hannes