removing gotos considered harmful...

removing gotos considered harmful...

[David Miller]

Because of massively painful regressions like the following,
I absolutely refuse to apply "cleanup" patches to remove gotos
for "clarity".  All such patches do is change the code and
potentially add bugs, they don't help in any way at all.

Gerrit, please be more careful next time, and resist the urge to "fix"
stuff that isn't broken just to satisfy your own personal coding
tastes during a conversion.  This is a locally exploitable hole,
all someone has to do is open a few hundred UDP sockets to a
particular destination port and then nobody, not even root, can
so much as run ping successfully.

Arnaldo, sorry I originally thought this bug was added by you, you're
totally innocent this time :-)))

I've submitted this fix to Linus and 2.6.19-stable.

Thanks.

[UDP]: Fix reversed logic in udp_get_port().

When this code was converted to use sk_for_each() the
logic for the "best hash chain length" code was reversed,
breaking everything.

The original code was of the form:

			size = 0;
			do {
				if (++size >= best_size_so_far)
					goto next;
			} while ((sk = sk->next) != NULL);
			best_size_so_far = size;
			best = result;
		next:;

and this got converted into:

			sk_for_each(sk2, node, head)
				if (++size < best_size_so_far) {
					best_size_so_far = size;
					best = result;
				}

Which does something very very different from the original.

Signed-off-by: David S. Miller <davem@davemloft.net>

diff --git a/net/ipv4/udp.c b/net/ipv4/udp.c
index 9e1bd37..404dd21 100644
--- a/net/ipv4/udp.c
+++ b/net/ipv4/udp.c
@@ -167,11 +167,14 @@ int udp_get_port(struct sock *sk, unsigned short snum,
 				goto gotit;
 			}
 			size = 0;
-			sk_for_each(sk2, node, head)
-				if (++size < best_size_so_far) {
-					best_size_so_far = size;
-					best = result;
-				}
+			sk_for_each(sk2, node, head) {
+				if (++size >= best_size_so_far)
+					goto next;
+			}
+			best_size_so_far = size;
+			best = result;
+		next:
+			;
 		}
 		result = best;
 		for(i = 0; i < (1 << 16) / UDP_HTABLE_SIZE; i++, result += UDP_HTABLE_SIZE) {

Re: removing gotos considered harmful...

[Arnaldo Carvalho de Melo]

On 12/22/06, David Miller <davem@davemloft.net> wrote:
>
> Because of massively painful regressions like the following,
> I absolutely refuse to apply "cleanup" patches to remove gotos
> for "clarity".  All such patches do is change the code and
> potentially add bugs, they don't help in any way at all.
>
> Gerrit, please be more careful next time, and resist the urge to "fix"
> stuff that isn't broken just to satisfy your own personal coding
> tastes during a conversion.  This is a locally exploitable hole,
> all someone has to do is open a few hundred UDP sockets to a
> particular destination port and then nobody, not even root, can
> so much as run ping successfully.
>
> Arnaldo, sorry I originally thought this bug was added by you, you're
> totally innocent this time :-)))

Was so fast I wasn't even able to plead "not guilty!" :-)

- Arnaldo

Re: removing gotos considered harmful...

[Gerrit Renker]

Hi Dave,

first of all - I take my hat off to such astuteness in the light of a mailing
list with an average of 100 postings per day and a massive throughput of patch
submissions. It is clearly awesome to be able to relate individual changes
in light of such a massive flood of patches.

However, I would also like to plead non-guilty. I have checked - what you
are quoting is not the original patch. If you look at e.g. 2.6.17-mm1, the 
previous code had the form (this is copied from 2.6.17-mm1 original):

			size = 0;
			sk_for_each(sk2, node, list)
				if (++size >= best_size_so_far)
					goto next;
			best_size_so_far = size;
			best = result;
		next:;

  
|  and this got converted into:
|  
|  			sk_for_each(sk2, node, head)
|  				if (++size < best_size_so_far) {
|  					best_size_so_far = size;
|  					best = result;
|  				}
|  
|  Which does something very very different from the original.
===> Sorry, I fail to see where the two differ. They have the same postcondition
     upon loop exit; sk2, node, size, and head are not referenced anywhere in the 
     code that follows.
     

  
|  Signed-off-by: David S. Miller <davem@davemloft.net>
|  
|  diff --git a/net/ipv4/udp.c b/net/ipv4/udp.c
|  index 9e1bd37..404dd21 100644
|  --- a/net/ipv4/udp.c
|  +++ b/net/ipv4/udp.c
|  @@ -167,11 +167,14 @@ int udp_get_port(struct sock *sk, unsigned short snum,
|   				goto gotit;
|   			}
|   			size = 0;
|  -			sk_for_each(sk2, node, head)
|  -				if (++size < best_size_so_far) {
|  -					best_size_so_far = size;
|  -					best = result;
|  -				}
|  +			sk_for_each(sk2, node, head) {
|  +				if (++size >= best_size_so_far)
|  +					goto next;
|  +			}
|  +			best_size_so_far = size;
|  +			best = result;
|  +		next:
|  +			;
|   		}
|   		result = best;
|   		for(i = 0; i < (1 << 16) / UDP_HTABLE_SIZE; i++, result += UDP_HTABLE_SIZE) {
|  
|  

Re: removing gotos considered harmful...

[Herbert Xu]

Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> 
>                        size = 0;
>                        sk_for_each(sk2, node, list)
>                                if (++size >= best_size_so_far)
>                                        goto next;
>                        best_size_so_far = size;
>                        best = result;
>                next:;
> 
>  
> |  and this got converted into:
> |  
> |                       sk_for_each(sk2, node, head)
> |                               if (++size < best_size_so_far) {
> |                                       best_size_so_far = size;
> |                                       best = result;
> |                               }
> |  
> |  Which does something very very different from the original.
> ===> Sorry, I fail to see where the two differ. They have the same postcondition
>     upon loop exit; sk2, node, size, and head are not referenced anywhere in the 
>     code that follows.

They're different because the former only updates best_size_so_far
after termination while the latter does it from the start.  It's
like moving the goal-posts while someone's trying to shoot :)

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: removing gotos considered harmful...

[David Miller]

From: Gerrit Renker <gerrit@erg.abdn.ac.uk>
Date: Wed, 3 Jan 2007 08:08:08 +0000

> However, I would also like to plead non-guilty. I have checked - what you
> are quoting is not the original patch. If you look at e.g. 2.6.17-mm1, the 
> previous code had the form (this is copied from 2.6.17-mm1 original):
> 
> 			size = 0;
> 			sk_for_each(sk2, node, list)
> 				if (++size >= best_size_so_far)
> 					goto next;
> 			best_size_so_far = size;
> 			best = result;
> 		next:;
> 
> |  and this got converted into:
> |  
> |  			sk_for_each(sk2, node, head)
> |  				if (++size < best_size_so_far) {
> |  					best_size_so_far = size;
> |  					best = result;
> |  				}
> |  
> |  Which does something very very different from the original.
>
> ===> Sorry, I fail to see where the two differ. They have the same postcondition
>      upon loop exit; sk2, node, size, and head are not referenced anywhere in the 
>      code that follows.
>      

Please go buy a pair of glasses then :-)

They are not at all the same.  Consider in what circumstances the two
variables "best_size_so_far" and "best" get updated in the two cases,
it's massively different.

You _ALWAYS_ update those two variables in your version if the loop
executes at least once, that's wrong and that's not what the original
code was trying to do.

It ONLY wants to update those two variables when we walk
a complete hash chain which is smaller than "best_size_so_far".

The fact that you continue to try and defend your version shows
that you really had no idea what you were doing when you made this
change.

You added an exploitable hole to our UDP protocol implementation
because you didn't understand this snippet of code and wanted to
'clean up the logic'.

Re: removing gotos considered harmful...

[Gerrit Renker]

|  > previous code had the form (this is copied from 2.6.17-mm1 original):
|  > 
|  > 			size = 0;
|  > 			sk_for_each(sk2, node, list)
|  > 				if (++size >= best_size_so_far)
|  > 					goto next;
|  > 			best_size_so_far = size;
|  > 			best = result;
|  > 		next:;
|  > 
|  > |  and this got converted into:
|  > |  
|  > |  			sk_for_each(sk2, node, head)
|  > |  				if (++size < best_size_so_far) {
|  > |  					best_size_so_far = size;
|  > |  					best = result;
|  > |  				}
|  > |  
|  > |  Which does something very very different from the original.
|  >
|  > ===> Sorry, I fail to see where the two differ. They have the same postcondition
|  >      upon loop exit; sk2, node, size, and head are not referenced anywhere in the 
|  >      code that follows.
|  >      
|  
|  Please go buy a pair of glasses then :-)
|  
|  They are not at all the same.  Consider in what circumstances the two
|  variables "best_size_so_far" and "best" get updated in the two cases,
|  it's massively different.
|  
|  You _ALWAYS_ update those two variables in your version if the loop
|  executes at least once, that's wrong and that's not what the original
|  code was trying to do.
|  
|  It ONLY wants to update those two variables when we walk
|  a complete hash chain which is smaller than "best_size_so_far".
|  
|  The fact that you continue to try and defend your version shows
|  that you really had no idea what you were doing when you made this
|  change.
|  
|  You added an exploitable hole to our UDP protocol implementation
|  because you didn't understand this snippet of code and wanted to
|  'clean up the logic'.
|  
|  
You are right, I made a stupid error by considering a single construct out of context.

I only understood fully what you were saying above after doing a lengthy paper-and-pencil
analysis of the entire algorithm: the exploit is in the assignment of `best', I was arguing
about `best_size_so_far', which is of no consequence here. 

I apologise for the regression that this caused - in future submissions I make sure that I
do the paper and pencil analysis before. Thanks for patience with the explanation.