use safer test on the result of find_first_zero_bit

Started by Julia Lawall on Jun 4, 2014 · 14 messages from 4 authors · Last reply Jun 24, 2014

Series

10 patches, 10 files

+12 −12

Subsystems (14)

Show 11 more

Maintainers (23)

Show 19 more
STALE4528d

open the first message on its own page

  1. [PATCH 3/10] video: use safer test on the result of find_first_zero_bit
    Related patches
Message details and related content
Find_first_zero_bit considers BITS_PER_LONG bits at a time, and thus may
return a larger number than the maximum position argument if that position
is not a multiple of BITS_PER_LONG.

[PATCH 3/10] video: use safer test on the result of find_first_zero_bit

Message details and related content
From: Julia Lawall <redacted>

Find_first_zero_bit considers BITS_PER_LONG bits at a time, and thus may
return a larger number than the maximum position argument if that position
is not a multiple of BITS_PER_LONG.

The semantic match that finds this problem is as follows:
(http://coccinelle.lip6.fr/)

// <smpl>
@@
expression e1,e2,e3;
statement S1,S2;
@@

e1 = find_first_zero_bit(e2,e3)
...
if (e1 
- =
+ >  e3)
S1 else S2
// </smpl>

Signed-off-by: Julia Lawall <redacted>

---
 drivers/video/fbdev/sh_mobile_meram.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff -u -p a/drivers/video/fbdev/sh_mobile_meram.c b/drivers/video/fbdev/sh_mobile_meram.c
--- a/drivers/video/fbdev/sh_mobile_meram.c
+++ b/drivers/video/fbdev/sh_mobile_meram.c
@@ -222,7 +222,7 @@ static int meram_plane_alloc(struct sh_m
 	unsigned long idx;
 
 	idx = find_first_zero_bit(&priv->used_icb, 28);
-	if (idx = 28)
+	if (idx >= 28)
 		return -ENOMEM;
 	plane->cache = &priv->icbs[idx];
 
Message details and related content
Hi Julia,

On Wed, Jun 4, 2014 at 11:07 AM, Julia Lawall [off-list ref] wrote:
Find_first_zero_bit considers BITS_PER_LONG bits at a time, and thus may
return a larger number than the maximum position argument if that position
is not a multiple of BITS_PER_LONG.
Shouldn't this be fixed in find_first_zero_bit() instead?

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds
Message details and related content

On Wed, 4 Jun 2014, Geert Uytterhoeven wrote:
Hi Julia,

On Wed, Jun 4, 2014 at 11:07 AM, Julia Lawall [off-list ref] wrote:
quoted
Find_first_zero_bit considers BITS_PER_LONG bits at a time, and thus may
return a larger number than the maximum position argument if that position
is not a multiple of BITS_PER_LONG.
Shouldn't this be fixed in find_first_zero_bit() instead?
OK, I could do that as well.  Most of the callers currently test with >=.
Should they be left as is, or changed to use =?

julia
Message details and related content
From: Julia Lawall
On Wed, 4 Jun 2014, Geert Uytterhoeven wrote:
quoted
Hi Julia,

On Wed, Jun 4, 2014 at 11:07 AM, Julia Lawall [off-list ref] wrote:
quoted
Find_first_zero_bit considers BITS_PER_LONG bits at a time, and thus may
return a larger number than the maximum position argument if that position
is not a multiple of BITS_PER_LONG.
Shouldn't this be fixed in find_first_zero_bit() instead?
OK, I could do that as well.  Most of the callers currently test with >=.
Should they be left as is, or changed to use =?
Do we want to add an extra test to find_first_zero_bit() and effectively
slow down all the calls - especially those where the length is a
multiple of 8 (probably the most common).

Maybe the documented return code should be changed to allow for the
existing behaviour.

	David


Message details and related content

On Wed, 4 Jun 2014, David Laight wrote:
From: Julia Lawall
quoted
On Wed, 4 Jun 2014, Geert Uytterhoeven wrote:
quoted
Hi Julia,

On Wed, Jun 4, 2014 at 11:07 AM, Julia Lawall [off-list ref] wrote:
quoted
Find_first_zero_bit considers BITS_PER_LONG bits at a time, and thus may
return a larger number than the maximum position argument if that position
is not a multiple of BITS_PER_LONG.
Shouldn't this be fixed in find_first_zero_bit() instead?
OK, I could do that as well.  Most of the callers currently test with >=.
Should they be left as is, or changed to use =?
Do we want to add an extra test to find_first_zero_bit() and effectively
slow down all the calls - especially those where the length is a
multiple of 8 (probably the most common).
Currently, most of the calls test with >=, and most of the others seem to
need to (either the size value did not look like a multiple of anything in
particular, or it was eg read from a device).

Note that it is BITS_PER_LONG, so it seems like it is typically 32 or 64,
not 8.
Maybe the documented return code should be changed to allow for the
existing behaviour.
Sorry, I'm not sure to understand what you suggest here.

thanks,
julia
Message details and related content
Hi Julia,

On Wed, Jun 4, 2014 at 11:52 AM, Julia Lawall [off-list ref] wrote:
quoted
Maybe the documented return code should be changed to allow for the
existing behaviour.
Sorry, I'm not sure to understand what you suggest here.
include/asm-generic/bitops/find.h:

| /**
|  * find_first_zero_bit - find the first cleared bit in a memory region
|  * @addr: The address to start the search at
|  * @size: The maximum number of bits to search
|  *
|  * Returns the bit number of the first cleared bit.
|  * If no bits are zero, returns @size.

"If no bits are zero, returns @size or a number larger than @size."

|  */
| extern unsigned long find_first_zero_bit(const unsigned long *addr,
|                                          unsigned long size);

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds
Message details and related content

On Wed, 4 Jun 2014, Geert Uytterhoeven wrote:
Hi Julia,

On Wed, Jun 4, 2014 at 11:52 AM, Julia Lawall [off-list ref] wrote:
quoted
quoted
Maybe the documented return code should be changed to allow for the
existing behaviour.
Sorry, I'm not sure to understand what you suggest here.
include/asm-generic/bitops/find.h:

| /**
|  * find_first_zero_bit - find the first cleared bit in a memory region
|  * @addr: The address to start the search at
|  * @size: The maximum number of bits to search
|  *
|  * Returns the bit number of the first cleared bit.
|  * If no bits are zero, returns @size.

"If no bits are zero, returns @size or a number larger than @size."
OK, thanks.  I was only looking at the C code.

But the C code contains a loop that is followed by:

        if (!size)
                return result;
        tmp = *p;

found_first:
        tmp |= ~0UL << size;
        if (tmp = ~0UL)        /* Are any bits zero? */
                return result + size;   /* Nope. */

In the first return, it would seem that result = size.  Could the second
one be changed to just return size?  It should not hurt performance.

julia
|  */
| extern unsigned long find_first_zero_bit(const unsigned long *addr,
|                                          unsigned long size);

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds
Message details and related content
Hi Julia,

On Wed, Jun 4, 2014 at 1:00 PM, Julia Lawall [off-list ref] wrote:
OK, thanks.  I was only looking at the C code.

But the C code contains a loop that is followed by:

        if (!size)
                return result;
        tmp = *p;

found_first:
        tmp |= ~0UL << size;
        if (tmp = ~0UL)        /* Are any bits zero? */
                return result + size;   /* Nope. */

In the first return, it would seem that result = size.  Could the second
one be changed to just return size?  It should not hurt performance.
"size" may have been changed between function entry and this line.
So you have to store it in a temporary.

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds
Message details and related content

On Wed, 4 Jun 2014, Geert Uytterhoeven wrote:
Hi Julia,

On Wed, Jun 4, 2014 at 1:00 PM, Julia Lawall [off-list ref] wrote:
quoted
OK, thanks.  I was only looking at the C code.

But the C code contains a loop that is followed by:

        if (!size)
                return result;
        tmp = *p;

found_first:
        tmp |= ~0UL << size;
        if (tmp = ~0UL)        /* Are any bits zero? */
                return result + size;   /* Nope. */

In the first return, it would seem that result = size.  Could the second
one be changed to just return size?  It should not hurt performance.
"size" may have been changed between function entry and this line.
So you have to store it in a temporary.
Sorry, after reflection it seems that indeed size + result is always the
original size, so it is actually all of the code that uses >= that is
doing something unnecessary.  = for the failure test is fine.

julia
Message details and related content
From: Julia Lawall
On Wed, 4 Jun 2014, Geert Uytterhoeven wrote:
quoted
Hi Julia,

On Wed, Jun 4, 2014 at 1:00 PM, Julia Lawall [off-list ref] wrote:
quoted
OK, thanks.  I was only looking at the C code.

But the C code contains a loop that is followed by:

        if (!size)
                return result;
        tmp = *p;

found_first:
        tmp |= ~0UL << size;
        if (tmp = ~0UL)        /* Are any bits zero? */
                return result + size;   /* Nope. */

In the first return, it would seem that result = size.  Could the second
one be changed to just return size?  It should not hurt performance.
"size" may have been changed between function entry and this line.
So you have to store it in a temporary.
Sorry, after reflection it seems that indeed size + result is always the
original size, so it is actually all of the code that uses >= that is
doing something unnecessary.  = for the failure test is fine.
There is nothing wrong with defensive coding.
The 'tmp |= ~0UL << size' ensures that the return value is 'correct'
when there are no bits set.
The function could have been defined so that this wasn't needed.

If you assume that the 'no zero bits' is unlikely, then checking the
return value from ffz() could well be slightly faster.
Not that anything is likely to notice.

	David


Re: [PATCH 3/10] video: use safer test on the result of find_first_zero_bit

Message details and related content
On Mon, 23 Jun 2014, Tomi Valkeinen wrote:
On 04/06/14 12:07, Julia Lawall wrote:
quoted
From: Julia Lawall <redacted>

Find_first_zero_bit considers BITS_PER_LONG bits at a time, and thus may
return a larger number than the maximum position argument if that position
is not a multiple of BITS_PER_LONG.
Thanks, queued for 3.17.
No, sorry you can drop it.  It doesn't hurt anything, but it is not
necessary either.  Returning a larger number is actually not possible.

julia

Re: [PATCH 3/10] video: use safer test on the result of find_first_zero_bit

Message details and related content
On 23/06/14 17:12, Julia Lawall wrote:
On Mon, 23 Jun 2014, Tomi Valkeinen wrote:
quoted
On 04/06/14 12:07, Julia Lawall wrote:
quoted
From: Julia Lawall <redacted>

Find_first_zero_bit considers BITS_PER_LONG bits at a time, and thus may
return a larger number than the maximum position argument if that position
is not a multiple of BITS_PER_LONG.
Thanks, queued for 3.17.
No, sorry you can drop it.  It doesn't hurt anything, but it is not
necessary either.  Returning a larger number is actually not possible.
Ok, dropped.

 Tomi

Keyboard shortcuts
hback out one level
jnext message in thread / next series-diff position
kprevious message in thread / previous series-diff position
ldrill in
Escclose help / fold thread tree
?toggle this help