Mailing List Archive: Quagga: Dev

[PATCH 1/2] lib: fix endianness bug in prefix.c

Index | Next | Previous | View Threaded

renatowestphal at gmail

Mar 23, 2012, 12:27 PM

Post #1 of 23 (687 views)
Permalink

[PATCH 1/2] lib: fix endianness bug in prefix.c

Use preprocessor macros to avoid the somewhat expensive
htonl/ntohl macros.
---
lib/prefix.c | 18 ++++++++++++++----
1 files changed, 14 insertions(+), 4 deletions(-)

diff --git a/lib/prefix.c b/lib/prefix.c
index 5e8cff0..fa2d2eb 100644
--- a/lib/prefix.c
+++ b/lib/prefix.c
@@ -31,7 +31,7 @@
/* Maskbit. */
static const u_char maskbit[] = {0x00, 0x80, 0xc0, 0xe0, 0xf0,
0xf8, 0xfc, 0xfe, 0xff};
-static const u_int32_t maskbytes_host[] =
+static const u_int32_t maskbytes_big_endian[] =
{
0x00000000, /* /0 0.0.0.0 */
0x80000000, /* /1 128.0.0.0 */
@@ -67,7 +67,8 @@ static const u_int32_t maskbytes_host[] =
0xfffffffe, /* /31 255.255.255.254 */
0xffffffff /* /32 255.255.255.255 */
};
-static const u_int32_t maskbytes_network[] =
+
+static const u_int32_t maskbytes_little_endian[] =
{
0x00000000, /* /0 0.0.0.0 */
0x00000080, /* /1 128.0.0.0 */
@@ -103,6 +104,7 @@ static const u_int32_t maskbytes_network[] =
0xfeffffff, /* /31 255.255.255.254 */
0xffffffff /* /32 255.255.255.255 */
};
+
static const struct in6_addr maskbytes6[] =
{
/* /0 */ { { { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } } },
@@ -2599,7 +2601,11 @@ void
masklen2ip (const int masklen, struct in_addr *netmask)
{
assert (masklen >= 0 && masklen <= IPV4_MAX_BITLEN);
- netmask->s_addr = maskbytes_network[masklen];
+#if (BYTE_ORDER == LITTLE_ENDIAN)
+ netmask->s_addr = maskbytes_little_endian[masklen];
+#elif (BYTE_ORDER == BIG_ENDIAN)
+ netmask->s_addr = maskbytes_big_endian[masklen];
+#endif
}

/* Convert IP address's netmask into integer. We assume netmask is
@@ -2621,7 +2627,11 @@ void
apply_mask_ipv4 (struct prefix_ipv4 *p)
{
assert (p->prefixlen >= 0 && p->prefixlen <= IPV4_MAX_BITLEN);
- p->prefix.s_addr &= maskbytes_network[p->prefixlen];
+#if (BYTE_ORDER == LITTLE_ENDIAN)
+ p->prefix.s_addr &= maskbytes_little_endian[p->prefixlen];
+#elif (BYTE_ORDER == BIG_ENDIAN)
+ p->prefix.s_addr &= maskbytes_big_endian[p->prefixlen];
+#endif
}

/* If prefix is 0.0.0.0/0 then return 1 else return 0. */
--
1.7.1

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

equinox at diac24

Mar 23, 2012, 12:57 PM

Post #2 of 23 (663 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

On Fri, Mar 23, 2012 at 04:27:40PM -0300, Renato Westphal wrote:
> Subject: [PATCH 1/2] lib: fix endianness bug in prefix.c

Whoa. Ugh. Very good catch.

I will be reviewing the entire file. Particularly, the 2000-line
agglomeration of constants is a gigantic fnord.

> Use preprocessor macros to avoid the somewhat expensive
> htonl/ntohl macros.

A little more verbose patch description would've been nice. I'll fix it
on commit.

> --- a/lib/prefix.c
> +++ b/lib/prefix.c
> @@ -31,7 +31,7 @@
> /* Maskbit. */
> static const u_char maskbit[] = {0x00, 0x80, 0xc0, 0xe0, 0xf0,
> 0xf8, 0xfc, 0xfe, 0xff};
> -static const u_int32_t maskbytes_host[] =

Funnily, maskbytes_host wasn't used anywhere...

Thanks, applied.

David

P.S.: did patch 2/2 get lost or is the mailing list just slow?
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

renatowestphal at gmail

Mar 23, 2012, 1:14 PM

Post #3 of 23 (663 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

2012/3/23 David Lamparter <equinox [at] diac24>:
> On Fri, Mar 23, 2012 at 04:27:40PM -0300, Renato Westphal wrote:
>> Subject: [PATCH 1/2] lib: fix endianness bug in prefix.c
>
> Whoa. Ugh. Very good catch.
>
> I will be reviewing the entire file. Particularly, the 2000-line
> agglomeration of constants is a gigantic fnord.
>
>> Use preprocessor macros to avoid the somewhat expensive
>> htonl/ntohl macros.
>
> A little more verbose patch description would've been nice. I'll fix it
> on commit.

Ok..

>> --- a/lib/prefix.c
>> +++ b/lib/prefix.c
>> @@ -31,7 +31,7 @@
>> /* Maskbit. */
>> static const u_char maskbit[] = {0x00, 0x80, 0xc0, 0xe0, 0xf0,
>> 0xf8, 0xfc, 0xfe, 0xff};
>> -static const u_int32_t maskbytes_host[] =
>
> Funnily, maskbytes_host wasn't used anywhere...
>
> Thanks, applied.
>
>
> David
>
> P.S.: did patch 2/2 get lost or is the mailing list just slow?

The second patch exceeded the 400 KB limit and is "waiting moderator
approval". I'll forward it to you now.

Both patches were tested on x86 and powerpc with success.

--
Renato Westphal

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

equinox at diac24

Mar 23, 2012, 1:31 PM

Post #4 of 23 (663 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

On Fri, Mar 23, 2012 at 05:14:06PM -0300, Renato Westphal wrote:
> > P.S.: did patch 2/2 get lost or is the mailing list just slow?
>
> The second patch exceeded the 400 KB limit and is "waiting moderator
> approval". I'll forward it to you now.

Thanks, I can see why. I'm not going to apply the second one; That
entire 2000-line monster is a giant WTF on its own and needs to be
replaced with something like __builtin_ffs. I'm checking the gcc
documentation for a suitable builtin.

-David

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

renatowestphal at gmail

Mar 23, 2012, 1:56 PM

Post #5 of 23 (665 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

2012/3/23 David Lamparter <equinox [at] diac24>:
> On Fri, Mar 23, 2012 at 05:14:06PM -0300, Renato Westphal wrote:
>> > P.S.: did patch 2/2 get lost or is the mailing list just slow?
>>
>> The second patch exceeded the 400 KB limit and is "waiting moderator
>> approval". I'll forward it to you now.
>
> Thanks, I can see why. I'm not going to apply the second one; That
> entire 2000-line monster is a giant WTF on its own and needs to be
> replaced with something like __builtin_ffs. I'm checking the gcc
> documentation for a suitable builtin.

Agreed. You may also try using a 8 bits version of the mapping table:
{
0, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
2, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
3, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1,
4, -1, -1, -1, -1, -1, -1, -1,
5, -1, -1, -1, 6, -1, 7, 8,
};

In this case you would sum the mask length of each of the 4 bytes of a
IPv4 prefix. Still pretty fast but with much less code..

>
> -David
>
> _______________________________________________
> Quagga-dev mailing list
> Quagga-dev [at] lists
> http://lists.quagga.net/mailman/listinfo/quagga-dev

--
Renato Westphal
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

infrastation at yandex

Mar 24, 2012, 8:27 AM

Post #6 of 23 (653 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

23.03.2012, 23:27, "Renato Westphal" <renatowestphal [at] gmail>:
> Use preprocessor macros to avoid the somewhat expensive
> htonl/ntohl macros.
> ---
> šlib/prefix.c | šš18 ++++++++++++++----
> š1 files changed, 14 insertions(+), 4 deletions(-)

Renato,

this BYTE_ORDER change adds the missing finish to this optimization, thank you. I didn't have the hardware to test the other endianness, hence the unused second helper array. Which htonl()/ntohl() calls do you mean in the commit message?

The longer 16-bit array isn't a "WTF", it is precisely designed for one specific task, if you are interested. At least for one given endianness. The array pisses people off at times, but it remains the best solution regardless, many things considered. At least I think I can defend this point of view. What is the other 400K patch?

--
Denis Ovsienko
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

me at dogonthesun

Mar 24, 2012, 10:39 AM

Post #7 of 23 (652 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

http://www.kernel.org/doc/man-pages/online/pages/man3/ffs.3.html

This function is compiled with modern gcc into "bsfl" instruction.
http://web.itu.edu.tr/kesgin/mul06/intel/instr/bsf.html

Also, we shouldn't think about byteorder in the code every time when do things with masks, prefixes and other. Renato, look into the /usr/include/netinet/in.h, where htonl, htons, etc. are defined. When we use any optimization with gcc, htonl's behaviour depends on current byte order.

There is my version of ip_masklen http://pastebin.com/s2eDA3Cp
It checks if mask is continuous and returns length of mask. In other case it returns -1, if mask isn't continuous.

24.03.2012, 19:27, "Denis Ovsienko" <infrastation [at] yandex>:
> 23.03.2012, 23:27, "Renato Westphal" <renatowestphal [at] gmail>:
>
>> šUse preprocessor macros to avoid the somewhat expensive
>> šhtonl/ntohl macros.
>> š---
>> ššlib/prefix.c | šš18 ++++++++++++++----
>> šš1 files changed, 14 insertions(+), 4 deletions(-)
>
> Renato,
>
> this BYTE_ORDER change adds the missing finish to this optimization, thank you. I didn't have the hardware to test the other endianness, hence the unused second helper array. Which htonl()/ntohl() calls do you mean in the commit message?
>
> The longer 16-bit array isn't a "WTF", it is precisely designed for one specific task, if you are interested. At least for one given endianness. The array pisses people off at times, but it remains the best solution regardless, many things considered. At least I think I can defend this point of view. What is the other 400K patch?
>
> --
> šššDenis Ovsienko
> _______________________________________________
> Quagga-dev mailing list
> Quagga-dev [at] lists
> http://lists.quagga.net/mailman/listinfo/quagga-dev
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

me at dogonthesun

Mar 24, 2012, 10:43 AM

Post #8 of 23 (655 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

Sorry, I forgot about two headers:

+#include <arpa/inet.h>
+#include <strings.h>

24.03.2012, 21:39, "me [at] dogonthesun" <me [at] dogonthesun>:
> http://www.kernel.org/doc/man-pages/online/pages/man3/ffs.3.html
>
> This function is compiled with modern gcc into "bsfl" instruction.
> http://web.itu.edu.tr/kesgin/mul06/intel/instr/bsf.html
>
> Also, we shouldn't think about byteorder in the code every time when do things with masks, prefixes and other. Renato, look into the /usr/include/netinet/in.h, where htonl, htons, etc. are defined. When we use any optimization with gcc, htonl's behaviour depends on current byte order.
>
> There is my version of ip_masklen http://pastebin.com/s2eDA3Cp
> It checks if mask is continuous and returns length of mask. In other case it returns -1, if mask isn't continuous.
>
> 24.03.2012, 19:27, "Denis Ovsienko" <infrastation [at] yandex>:
>
>> š23.03.2012, 23:27, "Renato Westphal" <renatowestphal [at] gmail>:
>>> ššUse preprocessor macros to avoid the somewhat expensive
>>> ššhtonl/ntohl macros.
>>> šš---
>>> šššlib/prefix.c | šš18 ++++++++++++++----
>>> ššš1 files changed, 14 insertions(+), 4 deletions(-)
>> šRenato,
>>
>> šthis BYTE_ORDER change adds the missing finish to this optimization, thank you. I didn't have the hardware to test the other endianness, hence the unused second helper array. Which htonl()/ntohl() calls do you mean in the commit message?
>>
>> šThe longer 16-bit array isn't a "WTF", it is precisely designed for one specific task, if you are interested. At least for one given endianness. The array pisses people off at times, but it remains the best solution regardless, many things considered. At least I think I can defend this point of view. What is the other 400K patch?
>>
>> š--
>> ššššDenis Ovsienko
>> š_______________________________________________
>> šQuagga-dev mailing list
>> šQuagga-dev [at] lists
>> šhttp://lists.quagga.net/mailman/listinfo/quagga-dev
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

equinox at diac24

Mar 24, 2012, 2:15 PM

Post #9 of 23 (654 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

On Sat, Mar 24, 2012 at 09:39:47PM +0400, me [at] dogonthesun wrote:
> http://www.kernel.org/doc/man-pages/online/pages/man3/ffs.3.html
>
> This function is compiled with modern gcc into "bsfl" instruction.
> http://web.itu.edu.tr/kesgin/mul06/intel/instr/bsf.html

Yes. gcc exports it as __builtin_clz. I already have code on my disk for
it, but I want to make sure it works on more architectures than x86.
(ARM, PowerPC, MIPS, x86 all have machine instructions for it)

> Also, we shouldn't think about byteorder in the code every time when
> do things with masks, prefixes and other. Renato, look into the
> /usr/include/netinet/in.h, where htonl, htons, etc. are defined. When
> we use any optimization with gcc, htonl's behaviour depends on current
> byte order.

Yes, and no. If it's a constant table, it's reasonable to have the table
itself be endian-dependent (though I would've done it in the definition
of the table itself, instead of the code referencing it.)

> There is my version of ip_masklen http://pastebin.com/s2eDA3Cp
> It checks if mask is continuous and returns length of mask. In other
> case it returns -1, if mask isn't continuous.

The previous code didn't account for broken masks, so we don't need to
either. A simple:
~input ? __builtin_clz(ntohl(~input)) : 32;

suffices, and that's what I'll be adding as soon as I'm confident it
works everywhere. (We already depend on GCCisms in other places, so
__builtin_ isn't much of a problem either.)

-David
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

nick at inex

Mar 24, 2012, 5:19 PM

Post #10 of 23 (656 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

On 24/03/2012 21:15, David Lamparter wrote:
> works everywhere. (We already depend on GCCisms in other places, so
> __builtin_ isn't much of a problem either.)

not sure if continuing to support gccisms is really a good idea. There are
other viable compilers out there for quagga's target operating systems
(e.g. llvm and icc).

Nick

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

chris.hall.list at highwayman

Mar 24, 2012, 6:56 PM

Post #11 of 23 (652 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

me [at] dogonthesun wrote (on Sat 24-Mar-2012 at 17:40 +0000):
> There is my version of ip_masklen http://pastebin.com/s2eDA3Cp It
> checks if mask is continuous and returns length of mask. In other
> case it returns -1, if mask isn't continuous.

That's:

int
ip_masklen (struct in_addr inp)
{
uint32_t n = ffs (htonl (inp.s_addr));
return inp.s_addr ? ((~htonl (inp.s_addr) + 1) - (1 << (n - 1))) ?
-1 : (33 - n) : 0;
}

I think you need to deal with inp.s_addr == 0 specially.

The behaviour on invalid mask is different to the original
ip_masklen() -- as was the version that used the big table !

The test for a valid mask can be shorter: (x | (x - 1)) == 0xFFFFFFFF
means x is a valid mask.

Using __builtin_clz() -- as suggested by David Lamparter -- works
better, and preserves the original behaviour on invalid masks.

If you want something using ffs() to be OK under POSIX without
__GNUC__ then:

u_char
n32_masklen (uint32_t mask_n)
{
uint32_t mask_h ;

mask_h = ntohl(mask_n) ;

#if __GNUC__

return (mask_h != 0xFFFFFFFF) ? __builtin_clz(~mask_h) : 32 ;

#else

while (1)
{
uint32_t t ;

if (mask_h == 0)
return 0 ;

t = (mask_h | (mask_h - 1)) - 0xFFFFFFFF ;

if (t == 0)
return 33 - ffs(mask_h) ;

mask_h &= t ;
}
#endif
} ;

Gives the same result, with or without __GNUC__.

Chris

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

equinox at diac24

Mar 25, 2012, 11:35 AM

Post #12 of 23 (652 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

On Sun, Mar 25, 2012 at 12:19:06AM +0000, Nick Hilliard wrote:
> On 24/03/2012 21:15, David Lamparter wrote:
> > works everywhere. (We already depend on GCCisms in other places, so
> > __builtin_ isn't much of a problem either.)
>
> not sure if continuing to support gccisms is really a good idea. There are
> other viable compilers out there for quagga's target operating systems
> (e.g. llvm and icc).

LLVM and icc both support these

-David
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

chris.hall.list at highwayman

Mar 25, 2012, 11:57 AM

Post #13 of 23 (653 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

Chris Hall wrote (on Sun 25-Mar-2012 at 02:57 +0100):
...

>> uint32_t n = ffs (htonl (inp.s_addr));
>> return inp.s_addr ? ((~htonl (inp.s_addr) + 1) - (1 << (n - 1))) ?
>> -1 : (33 - n) : 0;

> I think you need to deal with inp.s_addr == 0 specially.

Sorry... the code did that already. I failed to read the nested x ?
y : z -- something which I find difficult at the best of times, and
2am is clearly not one of those :-(

Chris

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

renatowestphal at gmail

Mar 26, 2012, 6:19 AM

Post #14 of 23 (640 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

2012/3/24 Denis Ovsienko <infrastation [at] yandex>:
> 23.03.2012, 23:27, "Renato Westphal" <renatowestphal [at] gmail>:
>> Use preprocessor macros to avoid the somewhat expensive
>> htonl/ntohl macros.
>> ---
>> šlib/prefix.c | šš18 ++++++++++++++----
>> š1 files changed, 14 insertions(+), 4 deletions(-)
>
> Renato,
>
> this BYTE_ORDER change adds the missing finish to this optimization, thank you. I didn't have the hardware to test the other endianness, hence the unused second helper array. Which htonl()/ntohl() calls do you mean in the commit message?

Sorry for the poor commit message. I meant that we could use this:

p->prefix.s_addr = ntohl (htonl (p->prefix.s_addr) &
maskbytes_network[p->prefixlen]);

Instead of this:

#if (BYTE_ORDER == LITTLE_ENDIAN)
p->prefix.s_addr &= maskbytes_little_endian[p->prefixlen];
#elif (BYTE_ORDER == BIG_ENDIAN)
p->prefix.s_addr &= maskbytes_big_endian[p->prefixlen];
#endif

Both options work, but the second one is theoretically faster because
it avoids byte swapping with the htonl/ntohl macros.

> The longer 16-bit array isn't a "WTF", it is precisely designed for one specific task, if you are interested. At least for one given endianness. The array pisses people off at times, but it remains the best solution regardless, many things considered. At least I think I can defend this point of view. What is the other 400K patch?

The second patch fix an endianness bug in the ip_masklen() function.
In short, the map64kto17_nbo array was little endian specific when it
should be big endian specific (htonl/ntohl works in x86, but in big
endian processors they're just NOP's)... I'll forward the patch to you
too. Despite the fix, I think we should use the __builtin_clz function
proposed by David instead of applying this second patch.

--
Renato Westphal

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

renatowestphal at gmail

Mar 26, 2012, 6:22 AM

Post #15 of 23 (638 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

2012/3/24 David Lamparter <equinox [at] diac24>:
> The previous code didn't account for broken masks, so we don't need to
> either.

Yes, the previous code didn't account for broken masks, but I think it
should. If someone tries to create a route using "ip route 10.0.30.0
255.255.233.0 eth0" I think zebra should warn the user with something
like "% Inconsistent address and mask" instead of creating an
erroneous route...

--
Renato Westphal
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

john at op-sec

Mar 26, 2012, 6:53 AM

Post #16 of 23 (639 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

That's not the only thing that Quagga should complain about that in the
case of that route attempt. It should complain about a route pointed at an
interface rather than nexthop + interface. While nexthop alone will work,
it is poor networking practice and has a high probability of leading to
routing loops. It's not as bad as pointing a route at an interface alone
though. Think of all of the ARP that is going to be occurring on eth0.

On Mon, Mar 26, 2012 at 9:22 AM, Renato Westphal
<renatowestphal [at] gmail>wrote:

> 2012/3/24 David Lamparter <equinox [at] diac24>:
> > The previous code didn't account for broken masks, so we don't need to
> > either.
>
> Yes, the previous code didn't account for broken masks, but I think it
> should. If someone tries to create a route using "ip route 10.0.30.0
> 255.255.233.0 eth0" I think zebra should warn the user with something
> like "% Inconsistent address and mask" instead of creating an
> erroneous route...
>
> --
> Renato Westphal
> _______________________________________________
> Quagga-dev mailing list
> Quagga-dev [at] lists
> http://lists.quagga.net/mailman/listinfo/quagga-dev
>

joakim.tjernlund at transmode

Mar 26, 2012, 7:08 AM

Post #17 of 23 (639 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

>
> 2012/3/24 Denis Ovsienko <infrastation [at] yandex>:
> > 23.03.2012, 23:27, "Renato Westphal" <renatowestphal [at] gmail>:
> >> Use preprocessor macros to avoid the somewhat expensive
> >> htonl/ntohl macros.
> >> ---
> >> lib/prefix.c | 18 ++++++++++++++----
> >> 1 files changed, 14 insertions(+), 4 deletions(-)
> >
> > Renato,
> >
> > this BYTE_ORDER change adds the missing finish to this optimization, thank you. I didn't have the hardware to test the other endianness, hence the unused second helper array. Which htonl()/ntohl() calls do you mean in the commit message?
>
> Sorry for the poor commit message. I meant that we could use this:
>
> p->prefix.s_addr = ntohl (htonl (p->prefix.s_addr) &
> maskbytes_network[p->prefixlen]);
>
> Instead of this:
>
> #if (BYTE_ORDER == LITTLE_ENDIAN)
> p->prefix.s_addr &= maskbytes_little_endian[p->prefixlen];
> #elif (BYTE_ORDER == BIG_ENDIAN)
> p->prefix.s_addr &= maskbytes_big_endian[p->prefixlen];
> #endif

2 identical tables were only byteorder differs is a waste and harder to maintain. One table wrapped in a suitable
macro is much cleaner, see crc32 table in Linux kernel:
static const u32 crc32table_le[4][256] = {{
tole(0x00000000L), tole(0x77073096L), tole(0xee0e612cL),

tole() is a macro with either does noting or swaps byteorder(the compiler will do it for you).

Jocke

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

infrastation at yandex

Mar 26, 2012, 7:18 AM

Post #18 of 23 (639 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

26.03.2012, 17:22, "Renato Westphal" <renatowestphal [at] gmail>:
> 2012/3/24 David Lamparter <equinox [at] diac24>:
>
>> šThe previous code didn't account for broken masks, so we don't need to
>> šeither.
>
> Yes, the previous code didn't account for broken masks, but I think it
> should. If someone tries to create a route using "ip route 10.0.30.0
> 255.255.233.0 eth0" I think zebra should warn the user with something
> like "% Inconsistent address and mask" instead of creating an
> erroneous route...

Yes, exactly. I am glad to see the thread got beyond ffs(). Non-contiguous netmasks are the real problem, I've been studying it for some time. The solution is on its way.

--
Denis Ovsienko
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

carlsonj at workingcode

Mar 27, 2012, 4:33 AM

Post #19 of 23 (632 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

John Fraizer wrote:
>
> That's not the only thing that Quagga should complain about that in the
> case of that route attempt. It should complain about a route pointed at
> an interface rather than nexthop + interface. While nexthop alone will
> work, it is poor networking practice and has a high probability of
> leading to routing loops. It's not as bad as pointing a route at an
> interface alone though. Think of all of the ARP that is going to be
> occurring on eth0.

Using an interface alone as the output is perfectly reasonable if the
interface happens to be point-to-point. In fact, for that case, you
don't much want that next-hop address.

--
James Carlson 42.703N 71.076W <carlsonj [at] workingcode>
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

joakim.tjernlund at transmode

Mar 27, 2012, 5:28 AM

Post #20 of 23 (633 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

>
> John Fraizer wrote:
> >
> > That's not the only thing that Quagga should complain about that in the
> > case of that route attempt. It should complain about a route pointed at
> > an interface rather than nexthop + interface. While nexthop alone will
> > work, it is poor networking practice and has a high probability of
> > leading to routing loops. It's not as bad as pointing a route at an
> > interface alone though. Think of all of the ARP that is going to be
> > occurring on eth0.
>
> Using an interface alone as the output is perfectly reasonable if the
> interface happens to be point-to-point. In fact, for that case, you
> don't much want that next-hop address.

Yes, and OSPF actually specifies that each OSPF route should be interface only or
interface + nexthop, something Quagga OSFP doesn't respect now.

Jocke

_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

equinox at diac24

Mar 31, 2012, 10:55 PM

Post #21 of 23 (562 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

On Mon, Mar 26, 2012 at 06:18:47PM +0400, Denis Ovsienko wrote:
> 26.03.2012, 17:22, "Renato Westphal" <renatowestphal [at] gmail>:
> > 2012/3/24 David Lamparter <equinox [at] diac24>:
> >
> >> Â The previous code didn't account for broken masks, so we don't need to
> >> Â either.
> >
> > Yes, the previous code didn't account for broken masks, but I think it
> > should. If someone tries to create a route using "ip route 10.0.30.0
> > 255.255.233.0 eth0" I think zebra should warn the user with something
> > like "% Inconsistent address and mask" instead of creating an
> > erroneous route...
>
> Yes, exactly. I am glad to see the thread got beyond ffs().
> Non-contiguous netmasks are the real problem, I've been studying it
> for some time. The solution is on its way.

Yes, non-continguous netmask are invalid input. That kind of invalid
input, however, needs handling by the routing daemons in question.

Changing the helper functions and adding a "broken mask" return value
may be _part_ of a solution. Then, all callers need to be adapted to
this and then take appropriate action (drop peer/neighbor, ignore route,
whatever appropriate for the occasion...).
The cleanest way to do it is probably to add a separate
"ip_masklen_verify" function and then incrementally update callers. Or,
even simpler, check "masklen2ip(ip_masklen) == mask"?

The addition of an "invalid" return value to ip_masklen on its own is a
big danger for bugs (or even security issues). The existing code does
not expect this and may behave undefinedly.

-David

Attachments:

signature.asc (0.22 KB)

infrastation at yandex

Apr 4, 2012, 6:34 AM

Post #22 of 23 (547 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

>> šYes, exactly. I am glad to see the thread got beyond ffs().
>> šNon-contiguous netmasks are the real problem, I've been studying it
>> šfor some time. The solution is on its way.
>
> Yes, non-continguous netmask are invalid input. That kind of invalid
> input, however, needs handling by the routing daemons in question.

This is true.

>
> Changing the helper functions and adding a "broken mask" return value
> may be _part_ of a solution. Then, all callers need to be adapted to
> this and then take appropriate action (drop peer/neighbor, ignore route,
> whatever appropriate for the occasion...).
> The cleanest way to do it is probably to add a separate
> "ip_masklen_verify" function and then incrementally update callers. Or,
> even simpler, check "masklen2ip(ip_masklen) == mask"?

This is also true.

>
> The addition of an "invalid" return value to ip_masklen on its own is a
> big danger for bugs (or even security issues). The existing code does
> not expect this and may behave undefinedly.

And this is true.

It took several weeks to map the problem appropriately. By now the solution is, to my imperfect knowledge, complete, but I would be interested in seeing any evidence of the opposite.

It has been smoketested and committed to RE-testing-0.99 branch.

--
Denis Ovsienko
_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

equinox at diac24

Apr 4, 2012, 11:52 AM

Post #23 of 23 (538 views)
Permalink

Re: [PATCH 1/2] lib: fix endianness bug in prefix.c [In reply to]

On Wed, Apr 04, 2012 at 05:34:47PM +0400, Denis Ovsienko wrote:
> > The addition of an "invalid" return value to ip_masklen on its own is a
> > big danger for bugs (or even security issues). The existing code does
> > not expect this and may behave undefinedly.
>
> And this is true.
>
> It took several weeks to map the problem appropriately. By now the
> solution is, to my imperfect knowledge, complete, but I would be
> interested in seeing any evidence of the opposite.
>
> It has been smoketested and committed to RE-testing-0.99 branch.

I've scrolled over it and it seems to be the right thing to do. I'll
do some proper review and figure out how I can merge it.

-David

Attachments:

signature.asc (0.22 KB)

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact Gossamer Threads