[PATCH] Multiple & vs. && and | vs. || bugs in 2.4.20

[PATCH] Multiple & vs. && and | vs. || bugs in 2.4.20

[Norbert Kiesel]

Hi,

here are patches for some | vs. || and & vs. && bugs found with
find ${1:-.} -name \*.c | xargs grep -En \
 '![a-zA-Z0-9_ ]+(\|[^|]|\&[^&])|([^|]\||[^&]\&) *!'

I also emailed them to the maintainers/authors if I could find them, but
failed for some (e.g. gus_xxx.c).

so long
	Norbert

--- linux-2.4.20/drivers/usb/acm.c~	2002-12-03 00:17:50.000000000 -0800
+++ linux-2.4.20/drivers/usb/acm.c	2003-03-02 03:03:34.000000000 -0800
@@ -240,7 +240,7 @@
 	if (urb->status)
 		dbg("nonzero read bulk status received: %d", urb->status);
 
-	if (!urb->status & !acm->throttle)  {
+	if (!urb->status && !acm->throttle)  {
 		for (i = 0; i < urb->actual_length && !acm->throttle; i++) {
 			/* if we insert more than TTY_FLIPBUF_SIZE characters,
 			 * we drop them. */
--- linux-2.4.20/drivers/net/aironet4500_core.c~	2001-09-30 12:26:06.000000000 -0700
+++ linux-2.4.20/drivers/net/aironet4500_core.c	2003-03-02 03:03:35.000000000 -0800
@@ -2676,10 +2676,8 @@
 #endif
 	//awc_dump_registers(dev);
 
-	if (adhoc & !max_mtu)
-		max_mtu= 2250;
-	else if (!max_mtu)
-		max_mtu= 1500;
+	if (!max_mtu)
+		max_mtu= adhoc ? 2250 : 1500;
 			
         priv->sleeping_bap = 1;
         	
--- linux-2.4.20/drivers/video/aty128fb.c~	2002-12-03 00:17:56.000000000 -0800
+++ linux-2.4.20/drivers/video/aty128fb.c	2003-03-02 03:05:44.000000000 -0800
@@ -2531,7 +2531,7 @@
 	reg |= LVDS_BL_MOD_EN | LVDS_BLON;
 	if (on && level > BACKLIGHT_OFF) {
 		reg |= LVDS_DIGION;
-		if (!reg & LVDS_ON) {
+		if ((reg & LVDS_ON) == 0) {
 			reg &= ~LVDS_BLON;
 			aty_st_le32(LVDS_GEN_CNTL, reg);
 			(void)aty_ld_le32(LVDS_GEN_CNTL);
--- linux-2.4.20/drivers/sound/gus_midi.c~	2001-03-06 19:28:32.000000000 -0800
+++ linux-2.4.20/drivers/sound/gus_midi.c	2003-03-02 03:03:35.000000000 -0800
@@ -183,7 +183,7 @@
 		qhead++;
 	}
 	restore_flags(flags);
-	return (qlen > 0) | !(GUS_MIDI_STATUS() & MIDI_XMIT_EMPTY);
+	return (qlen > 0) || !(GUS_MIDI_STATUS() & MIDI_XMIT_EMPTY);
 }
 
 #define MIDI_SYNTH_NAME	"Gravis Ultrasound Midi"
--- linux-2.4.20/drivers/sound/gus_wave.c~	2001-09-14 14:40:00.000000000 -0700
+++ linux-2.4.20/drivers/sound/gus_wave.c	2003-03-02 03:03:35.000000000 -0800
@@ -3123,7 +3123,7 @@
 
 	gus_initialize();
 	
-	if ((gus_mem_size > 0) & !gus_no_wave_dma)
+	if ((gus_mem_size > 0) && !gus_no_wave_dma)
 	{
 		hw_config->slots[4] = -1;
 		if ((gus_devnum = sound_install_audiodrv(AUDIO_DRIVER_VERSION,
--- linux-2.4.20/drivers/i2c/i2c-proc.c~	2002-03-11 01:07:21.000000000 -0800
+++ linux-2.4.20/drivers/i2c/i2c-proc.c	2003-03-02 03:03:34.000000000 -0800
@@ -729,7 +729,7 @@
 			     ||
 			     ((address_data->
 			       ignore_range[i] ==
-			       SENSORS_ANY_I2C_BUS) & !is_isa))
+			       SENSORS_ANY_I2C_BUS) && !is_isa))
 			    && (addr >= address_data->ignore_range[i + 1])
 			    && (addr <= address_data->ignore_range[i + 2])) {
 #ifdef DEBUG
@@ -818,7 +818,7 @@
 		     i += 2) {
 			if (((adapter_id == address_data->probe[i]) ||
 			     ((address_data->
-			       probe[i] == SENSORS_ANY_I2C_BUS) & !is_isa))
+			       probe[i] == SENSORS_ANY_I2C_BUS) && !is_isa))
 			    && (addr == address_data->probe[i + 1])) {
 #ifdef DEBUG
 				printk
@@ -835,7 +835,7 @@
 			    ((adapter_id == address_data->probe_range[i])
 			     ||
 			     ((address_data->probe_range[i] ==
-			       SENSORS_ANY_I2C_BUS) & !is_isa))
+			       SENSORS_ANY_I2C_BUS) && !is_isa))
 			    && (addr >= address_data->probe_range[i + 1])
 			    && (addr <= address_data->probe_range[i + 2])) {
 				found = 1;
--- linux-2.4.20/drivers/sound/maestro.c~	2002-08-25 03:12:46.000000000 -0700
+++ linux-2.4.20/drivers/sound/maestro.c	2003-03-02 03:03:34.000000000 -0800
@@ -3359,7 +3359,7 @@
 	/* check to see if we have a capabilities list in
 		the config register */
 	pci_read_config_word(pcidev, PCI_STATUS, &w);
-	if(! w & PCI_STATUS_CAP_LIST) return 0;
+	if(!(w & PCI_STATUS_CAP_LIST)) return 0;
 
 	/* walk the list, starting at the head. */
 	pci_read_config_byte(pcidev,PCI_CAPABILITY_LIST,&next);
--- linux-2.4.20/drivers/video/radeonfb.c~	2002-12-03 00:17:56.000000000 -0800
+++ linux-2.4.20/drivers/video/radeonfb.c	2003-03-02 03:05:42.000000000 -0800
@@ -2778,7 +2778,7 @@
 	lvds_gen_cntl |= (LVDS_BL_MOD_EN | LVDS_BLON);
 	if (on && (level > BACKLIGHT_OFF)) {
 		lvds_gen_cntl |= LVDS_DIGON;
-		if (!lvds_gen_cntl & LVDS_ON) {
+		if ((lvds_gen_cntl & LVDS_ON) == 0) {
 			lvds_gen_cntl &= ~LVDS_BLON;
 			OUTREG(LVDS_GEN_CNTL, lvds_gen_cntl);
 			(void)INREG(LVDS_GEN_CNTL);

Re: [PATCH] Multiple & vs. && and | vs. || bugs in 2.4.20

[Ulrich Drepper]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Norbert Kiesel wrote:

> --- linux-2.4.20/drivers/usb/acm.c~	2002-12-03 00:17:50.000000000 -0800
> +++ linux-2.4.20/drivers/usb/acm.c	2003-03-02 03:03:34.000000000 -0800
> @@ -240,7 +240,7 @@
>  	if (urb->status)
>  		dbg("nonzero read bulk status received: %d", urb->status);
>  
> -	if (!urb->status & !acm->throttle)  {
> +	if (!urb->status && !acm->throttle)  {
>  		for (i = 0; i < urb->actual_length && !acm->throttle; i++) {
>  			/* if we insert more than TTY_FLIPBUF_SIZE characters,
>  			 * we drop them. */

Have you really looked at detail at all these cases?  The problem is
that you have made the code less efficient on some platforms.  The use
of && requires shortcut evaluation.  I.e., the compiler is forced to not
evaluate !acm->throttle if !urb->status is true.  The causes, unless the
architecture has condition bits, a conditional jump.

The original code didn't need and normally has no jump and thi specific
case was certainly fine before since the result of the ! operator is
either 0 or 1 and therefore the & operator has no strange side effects.

As an example, here is how the code for x86 could have looked before

   movl   status(%edx), %edx
   testl  %edx, %edx
   movl   throttle(%eax), %eax
   sete   %dl
   testl  %eax, %eax
   sete   %al
   andb   %dl, %al
   jne    ...
   [if code]

After the change the code must look something like this:

   movl   status(%edx), %edx
   testl  %edx, %edx
   jne    ...
   movl   throttle(%eax), %eax
   testl  %eax, %eax
   jne    ...
   [if code]


Observe the extra 'jne' and the fact that the value of 'throttle'
element cannot be loaded until after the conditional jump.   Not even
out of order execution can arrange that.


To summarize, I'd probably not be amused if you would change any of my
code which takes advantage of such programming finess.  I would probably
have added appropriate comments to explain the code but nevertheless,
replacing the more efficient code with some which is easier to
understand should probably be considered on a case by case basis.
Incorrect branch prediction is costly.

- -- 
- --------------.                        ,-.            444 Castro Street
Ulrich Drepper \    ,-----------------'   \ Mountain View, CA 94041 USA
Red Hat         `--' drepper at redhat.com `---------------------------
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQE+Ykf82ijCOnn/RHQRApJaAKCxM4hwu12mJVbQuD3o+t13YVxrsACgsnVH
RZmgjNB5KP3Qu27iqpf5aiU=
=l7xl
-----END PGP SIGNATURE-----

Re: [PATCH] Multiple & vs. && and | vs. || bugs in 2.4.20

[Roman Zippel]

Hi,

On Sun, 2 Mar 2003, Ulrich Drepper wrote:

> > -	if (!urb->status & !acm->throttle)  {
> > +	if (!urb->status && !acm->throttle)  {
> 
> [...]
> 
> Observe the extra 'jne' and the fact that the value of 'throttle'
> element cannot be loaded until after the conditional jump.   Not even
> out of order execution can arrange that.

But speculative execution can arrange that (providing the cpu predicted 
the jump target correctly).

> To summarize, I'd probably not be amused if you would change any of my
> code which takes advantage of such programming finess.

If that was really intentional, I would assume to see something like this:

	if (!(urb->status | acm->throttle)) {

bye, Roman

Re: [PATCH] Multiple & vs. && and | vs. || bugs in 2.4.20

[Werner Almesberger]

Ulrich Drepper wrote:
> > -	if (!urb->status & !acm->throttle)  {
> > +	if (!urb->status && !acm->throttle)  {
[...]
> Have you really looked at detail at all these cases?  The problem is
> that you have made the code less efficient on some platforms.  The use
> of && requires shortcut evaluation.  I.e., the compiler is forced to not

While I agree with your observation in general, this is actually
something the compiler should be able to figure out by itself:

 - there's only a side-effect if acm is NULL
 - in ACM_READY, we've already tested acm for NULL, and subsequently
   de-referenced it
 - acm is a local variable, and not aliased, so the dbg() can't
   change it

So, given the negations, || and | are equivalent in this case, and
whether a jump, conditional execution, a bit operation, or something
else yields better code is compiler, machine, and context specific.

- Werner

-- 
  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina         wa@almesberger.net /
/_http://www.almesberger.net/____________________________________________/

Re: [PATCH] Multiple & vs. && and | vs. || bugs in 2.4.20

[Richard Henderson]

On Sun, Mar 02, 2003 at 06:41:14PM -0300, Werner Almesberger wrote:
> While I agree with your observation in general, this is actually
> something the compiler should be able to figure out by itself:
> 
>  - there's only a side-effect if acm is NULL

In general there's also a side effect if acm is uninitialized.
I didn't look at the code in question here.

As for the rest, it's true that we should be able to do this,
but we don't currently have a pass that globally propagates
"trapiness" of memory references.  It would be a useful thing
to have though, particularly for Java, which is required to
arrange for these traps to be able to be caught with exceptions,
and other horrible reordering issues.


r~

Re: [PATCH] Multiple & vs. && and | vs. || bugs in 2.4.20

[Norbert Kiesel]

[-- Attachment #1: Type: text/plain, Size: 3575 bytes --]

Hi,
yes I agree that the code will be slightly less efficient in this case
(though looking a bit around, there are way more places which could be
optimized, e.g. the useless "&& !acm->throttle" in the next line). 
What's IMHO more important is that the original code was producing the
correct result, so the patch for acm.c is not really necessary.  This is
also true for the patches for gus_midi.c, gus-wave.c, and i2c-proc.c.

OTOH, I still think that in most (all?) of this cases the bit-op was not
intended.

Anyway, I'll wait another day or two to collect replies from the
maintainers and then resend the remaining patches where the code really
produces wrong results.

so long
	Norbert

On Sun, 2003-03-02 at 10:05, Ulrich Drepper wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Norbert Kiesel wrote:
> 
> > --- linux-2.4.20/drivers/usb/acm.c~	2002-12-03 00:17:50.000000000 -0800
> > +++ linux-2.4.20/drivers/usb/acm.c	2003-03-02 03:03:34.000000000 -0800
> > @@ -240,7 +240,7 @@
> >  	if (urb->status)
> >  		dbg("nonzero read bulk status received: %d", urb->status);
> >  
> > -	if (!urb->status & !acm->throttle)  {
> > +	if (!urb->status && !acm->throttle)  {
> >  		for (i = 0; i < urb->actual_length && !acm->throttle; i++) {
> >  			/* if we insert more than TTY_FLIPBUF_SIZE characters,
> >  			 * we drop them. */
> 
> Have you really looked at detail at all these cases?  The problem is
> that you have made the code less efficient on some platforms.  The use
> of && requires shortcut evaluation.  I.e., the compiler is forced to not
> evaluate !acm->throttle if !urb->status is true.  The causes, unless the
> architecture has condition bits, a conditional jump.
> 
> The original code didn't need and normally has no jump and thi specific
> case was certainly fine before since the result of the ! operator is
> either 0 or 1 and therefore the & operator has no strange side effects.
> 
> As an example, here is how the code for x86 could have looked before
> 
>    movl   status(%edx), %edx
>    testl  %edx, %edx
>    movl   throttle(%eax), %eax
>    sete   %dl
>    testl  %eax, %eax
>    sete   %al
>    andb   %dl, %al
>    jne    ...
>    [if code]
> 
> After the change the code must look something like this:
> 
>    movl   status(%edx), %edx
>    testl  %edx, %edx
>    jne    ...
>    movl   throttle(%eax), %eax
>    testl  %eax, %eax
>    jne    ...
>    [if code]
> 
> 
> Observe the extra 'jne' and the fact that the value of 'throttle'
> element cannot be loaded until after the conditional jump.   Not even
> out of order execution can arrange that.
> 
> 
> To summarize, I'd probably not be amused if you would change any of my
> code which takes advantage of such programming finess.  I would probably
> have added appropriate comments to explain the code but nevertheless,
> replacing the more efficient code with some which is easier to
> understand should probably be considered on a case by case basis.
> Incorrect branch prediction is costly.
> 
> - -- 
> - --------------.                        ,-.            444 Castro Street
> Ulrich Drepper \    ,-----------------'   \ Mountain View, CA 94041 USA
> Red Hat         `--' drepper at redhat.com `---------------------------
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.1 (GNU/Linux)
> 
> iD8DBQE+Ykf82ijCOnn/RHQRApJaAKCxM4hwu12mJVbQuD3o+t13YVxrsACgsnVH
> RZmgjNB5KP3Qu27iqpf5aiU=
> =l7xl
> -----END PGP SIGNATURE-----
-- 
Norbert Kiesel <nkiesel@tbdnetworks.com>

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] Multiple & vs. && and | vs. || bugs in 2.4.20

[John Levon]

On Sun, Mar 02, 2003 at 06:03:57PM -0800, Norbert Kiesel wrote:

> What's IMHO more important is that the original code was producing the
> correct result, so the patch for acm.c is not really necessary.  This is
> also true for the patches for gus_midi.c, gus-wave.c, and i2c-proc.c.

Even the patch isn't *necessary* (i.e. does not change behaviour) it's
still a good idea.

I've been working on a -Wboolean-bitops. It seems to work at least a
bit, but I don't really know anything about gcc so it's probably
brain-damaged. Alas, current gcc CVS seems to have real issues with the
kernel ATM (as in, segfaults on scripts/empty.c immediately).

regards
john

Re: [PATCH] Multiple & vs. && and | vs. || bugs in 2.4.20

[Pavel Machek]

Hi!

> >  
> > -	if (!urb->status & !acm->throttle)  {
> > +	if (!urb->status && !acm->throttle)  {
> >  		for (i = 0; i < urb->actual_length && !acm->throttle; i++) {

> To summarize, I'd probably not be amused if you would change any of my
> code which takes advantage of such programming finess.  I would probably
> have added appropriate comments to explain the code but nevertheless,
> replacing the more efficient code with some which is easier to
> understand should probably be considered on a case by case basis.

Actually I feel co-responsible for acm.c,
and this *is* typo. acm is for modems,
thats *not* performance critical, and certainly
not worth code obfuscation.
-- 
				Pavel
Written on sharp zaurus, because my Velo1 broke. If you have Velo you don't need...

Re: [PATCH] Multiple & vs. && and | vs. || bugs in 2.4.20

[Norbert Kiesel]

Hi,

Alan included my 2.4.20 patches - including the one for acm.c - in
2.4.21-pre5-ac1, so I expect them to show up in mainline someday.  Still
working on delivering some of the 2.5.x ones...

--nk

On Thu, 2003-03-06 at 11:58, Pavel Machek wrote:
> Hi!
> 
> > >  
> > > -	if (!urb->status & !acm->throttle)  {
> > > +	if (!urb->status && !acm->throttle)  {
> > >  		for (i = 0; i < urb->actual_length && !acm->throttle; i++) {
> 
> > To summarize, I'd probably not be amused if you would change any of my
> > code which takes advantage of such programming finess.  I would probably
> > have added appropriate comments to explain the code but nevertheless,
> > replacing the more efficient code with some which is easier to
> > understand should probably be considered on a case by case basis.
> 
> Actually I feel co-responsible for acm.c,
> and this *is* typo. acm is for modems,
> thats *not* performance critical, and certainly
> not worth code obfuscation.
-- 
Norbert Kiesel <nkiesel@tbdnetworks.com>
TBD Networks