April 2010 - Bird-users - Mailing Lists

[PATCH 0/5] IP checksum improvements
by Joakim Tjernlund 27 Apr '10

27 Apr '10

Here are a series of performance improvements on the Internet checksum. With these changes applied I get about 20-30% better performance on x86 and PowerPC. Even though we got off on the wrong foot I got curious enough to do some more investigation and I leared more about "add with carry" and how gcc handle them. Feel free to ignore these patches, I just wanted to at least document my findings in patch form. Joakim Tjernlund (5): checksum: improve add32 checksum: Optimize add32() for PowerPC checksum: use pre increment. checksum: optimize loop and get rid of add16() checksum: Optimize first addition. lib/checksum.c | 61 ++++++++++++++++++++++++++++++++----------------------- 1 files changed, 35 insertions(+), 26 deletions(-)

6 19

OSPF performance/SPF calculations
by Joakim Tjernlund 26 Apr '10

26 Apr '10

I am using Quagga ATM but I had a quick look at BIRD and I got a few observations. The LSA/checksum code seem very inefficient. LSAs are built allocating/reallocing bits of memory. This is slow and will case memory fragmentation. The fletcher checksum is very slow as it has extra tests in the hot path and also flips endian in the LSA back and forth. I can't work out how the SPF next hop works(calc_next_hop). I tried to compare it with Quagga's ospf_nexthop_calculation() but the structure is too different. The reason for me looking into this was to see how much work it would be to add unnumbered ppp links but as I can't work out how nexthop is working I didn't get very far. I have impl. unnumbered ppp link for Quagga that works really well but this work hasn't been accepted into Quagga yet since Quagga development has stalled. I could show you how I did it Quagga though. Jocke

5 30

VRRP, OSPF and 1-way state.
by Rob Epping 25 Apr '10

25 Apr '10

Hi list, Today I spend a lot of time debugging why BIRD doesn't get our IPSO VRRP cluster in 2WAY state, while junos and IOS routers do. Here's the setup. 1 VLAN with all OSPF routers. Network is X.Y.0.0/28 .1 and .2 are the IPSO nodes, .3 is the VRRP address. IPSO nodes run OSPF priority 0. At this moment .2 is the VRRP "master". .4 and .5 are junos routers and are DR and BDR respectively. .7 is an IOS Version 12.0(28c) router .8 is an other junos router. .14 is Debian linux + BIRD. Both IPSO routers send OSPF messages with RID .3, see below. 17:45:37.773176 O 802.1Q vlan#10 P0 X.53.0.1 > X.53.0.4: OSPFv2-ls_upd 64: RID X.Y.0.3 backbone { rtr X.Y.0.3 E S 80023430 age 6 } [|ospf] [tos 0xc0] [ttl 1] (id 6121) 17:47:57.888864 O 802.1Q vlan#10 P0 X.Y.0.2 > X.Y.0.4: OSPFv2-ls_upd 64: RID X.Y.0.3 backbone { rtr X.Y.0.3 E S 80023467 age 4 } [|ospf] [tos 0xc0] [ttl 1] (id 35846) Bird doesn't handle this setup.... bird> show ospf neighbors MyOSPF: Router ID Pri State DTime Interface Router IP X.Y.0.8 0 2way/other 00:32 eth0 X.Y.0.8 X.Y.0.3 0 init/other 00:39 eth0 X.Y.0.1 X.Y.0.7 0 2way/other 00:32 eth0 X.Y.0.7 X.Y.0.5 128 full/dr 00:39 eth0 X.Y.0.5 X.Y.0.4 128 full/bdr 00:39 eth0 X.Y.0.4 bird> And in the logs 25-04-2010 17:58:03 <TRACE> MyOSPF: LSA Type: 0001, Id: X.Y.0.3, Rt: X.Y.0.3, Age: 2, Seq: 80023552, Sum: 8856 Working on router X.Y.0.3 Found :-) Next hop calculating for id: X.Y.0.3 rt: X.Y.0.3 type: 1 25-04-2010 17:58:05 <WARN> Cannot find next hop for LSA (Type: 0001, Id: X.Y.0.3, Rt: X.Y.0.3) Working on router X.Y.0.3 Found :-) Next hop calculating for id: X.Y.0.3 rt: X.Y.0.3 type: 1 and OSPF: RX hook called (iface eth0, src X.Y.0.2, dst 224.0.0.5) 25-04-2010 18:00:45 <TRACE> MyOSPF: HELLO packet received from X.Y.0.2 via eth0 Neighbor state machine for neighbor X.Y.0.1, event 'hello received' Neighbor state machine for neighbor X.Y.0.1, event '1-way received' Neighbor state machine for neighbor X.Y.0.1, event 'hello received' MyOSPF: RXMT timer fired on interface eth0 for neigh: X.Y.0.1. OSPF: RX hook called (iface eth0, src X.Y.0.1, dst 224.0.0.5) 25-04-2010 18:00:49 <TRACE> MyOSPF: HELLO packet received from X.Y.0.1 via eth0 Neighbor state machine for neighbor X.Y.0.1, event 'hello received' Neighbor state machine for neighbor X.Y.0.1, event '1-way received' Neighbor state machine for neighbor X.Y.0.1, event 'hello received' MyOSPF: RXMT timer fired on interface eth0 for neigh: X.Y.0.1. My guess is that neighbors are created based on their address instead of their RID. Looking at the info below I'm guessing this is not correct. Can this be fixed? from junos epping@BR1> show ospf neighbor X.Y.0.3 extensive Address Interface State ID Pri Dead X.Y.0.1 ge-0/0/0.0 Full X.Y.0.3 0 32 Area 0.0.0.0, opt 0x2, DR X.Y.0.5, BDR X.Y.0.4 Up 00:24:38, adjacent 00:24:33 X.Y.0.2 ge-0/0/0.0 Full X.Y.0.3 0 37 Area 0.0.0.0, opt 0x2, DR X.Y.0.5, BDR X.Y.0.4 Up 4d 05:22:13, adjacent 4d 05:22:13 Link state retransmission list: Type LSA ID Adv rtr Seq Router X.Y.0.3 X.Y.0.3 0x8002349e epping@BR1> and IOS BR3#sh ip ospf neighbor detail X.Y.0.3 Neighbor X.Y.0.3, interface address X.Y.0.2 In the area 0.0.0.0 via interface Ethernet0 Neighbor priority is 0, State is 2WAY, 2 state changes DR is X.Y.0.5 BDR is X.Y.0.4 Options 2 Dead timer due in 00:00:30 Neighbor X.Y.0.3, interface address X.Y.0.1 In the area 0.0.0.0 via interface Ethernet0 Neighbor priority is 0, State is 2WAY, 2 state changes DR is X.Y.0.5 BDR is X.Y.0.4 Options 2 Dead timer due in 00:00:35 BR3# GRTNX, RobJE -- Home is near Enter. ((c) RonA) ======================================================================== Tel: +31 - 317 - 399800 s-mail: P.O. box 617 Fax: +31 - 317 - 423164 6700 AP Wageningen MailTo: r.epping(a)meteo.nl WWW: http://www.meteo.nl/ -- This e-mail is from Meteo Consult B.V., a MeteoGroup company. For more information, see http://www.weer.nl/gebruiksvoorwaarden. This e-mail may contain confidential information. Only the addressee is permitted to read, copy, distribute or otherwise use this e-mail or any attachments. If you have received it in error, please contact the sender immediately. Any opinion expressed in this e-mail is personal to the sender and may not reflect the opinion of MeteoGroup. Any e-mail reply to this address may be subject to interception or monitoring for operational reasons or for lawful business practices.

2 1

[PATCH 4/5 v2] checksum: optimize loop and get rid of add16()
by Joakim Tjernlund 25 Apr '10

25 Apr '10

Use some better vaiable names and get rid of add16 as add32 will do just as well. Fold the 32 bit checkum into 16 bits in the end. --- v2 - bug fix lib/checksum.c | 47 +++++++++++++++++++++++------------------------ 1 files changed, 23 insertions(+), 24 deletions(-) diff --git a/lib/checksum.c b/lib/checksum.c index 2e427a2..9e30bdc 100644 --- a/lib/checksum.c +++ b/lib/checksum.c @@ -15,12 +15,6 @@ #include "nest/bird.h" #include "checksum.h" -static u16 /* One-complement addition */ -add16(u16 sum, u16 x) -{ - u16 z = sum + x; - return z + (z < sum); -} #ifdef __powerpc__ static u32 @@ -42,10 +36,10 @@ add32(u32 sum, u32 x) #endif static u16 -ipsum_calc_block(u16 *x, unsigned len, u16 sum) +ipsum_calc_block(u16 *buf, unsigned len, u16 sum) { int rest; - u32 tmp, *xx; + u32 acc_sum, *buf_u32; /* * A few simple facts about the IP checksum (see RFC 1071 for detailed @@ -62,23 +56,28 @@ ipsum_calc_block(u16 *x, unsigned len, u16 sum) ASSERT(!(len % 2)); if (!len) return sum; - len >>= 1; - if ((unsigned long) x & 2) /* Align to 32-bit boundary */ - { - sum = add16(sum, *x++); - len--; - } + + acc_sum = sum; + if ((u32) buf & 2) { /* Align to 32-bit boundary */ + acc_sum = add32(acc_sum, *buf++); + len =- 2; + } rest = len & 1; - len >>= 1; - tmp = 0; - xx = (u32 *) x; - for (xx--; len; --len); - tmp = add32(tmp, *++xx); - xx++; - sum = add16(sum, add16(tmp & 0xffff, tmp >> 16U)); - if (rest) - sum = add16(sum, *(u16 *) xx); - return sum; + len >>= 2; + buf_u32 = (u32 *) buf; + for(buf_u32--; len; --len) + acc_sum = add32(acc_sum, *++buf_u32); + + if (rest) { + buf = (u16 *)(buf_u32++); + acc_sum = add32(acc_sum, *buf); + } + + /* Add back carry outs from top 16 bits to low 16 bits. + */ + acc_sum = (acc_sum >> 16) + (acc_sum & 0xffff); /* add high-16 to low-16 */ + acc_sum += (acc_sum >> 16); /* add carry */ + return acc_sum; } static u16 -- 1.6.4.4

1 1

[PATCH 4/5] checksum: optimize loop and get rid of add16()
by Joakim Tjernlund 25 Apr '10

25 Apr '10

Use some better vaiable names and get rid of add16 as add32 will do just as well. Fold the 32 bit checkum into 16 bits in the end. Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund(a)transmode.se> --- lib/checksum.c | 47 +++++++++++++++++++++++------------------------ 1 files changed, 23 insertions(+), 24 deletions(-) diff --git a/lib/checksum.c b/lib/checksum.c index 2e427a2..7b183d9 100644 --- a/lib/checksum.c +++ b/lib/checksum.c @@ -15,12 +15,6 @@ #include "nest/bird.h" #include "checksum.h" -static u16 /* One-complement addition */ -add16(u16 sum, u16 x) -{ - u16 z = sum + x; - return z + (z < sum); -} #ifdef __powerpc__ static u32 @@ -42,10 +36,10 @@ add32(u32 sum, u32 x) #endif static u16 -ipsum_calc_block(u16 *x, unsigned len, u16 sum) +ipsum_calc_block(u16 *buf, unsigned len, u16 sum) { int rest; - u32 tmp, *xx; + u32 acc_sum, *buf_u32; /* * A few simple facts about the IP checksum (see RFC 1071 for detailed @@ -62,23 +56,28 @@ ipsum_calc_block(u16 *x, unsigned len, u16 sum) ASSERT(!(len % 2)); if (!len) return sum; - len >>= 1; - if ((unsigned long) x & 2) /* Align to 32-bit boundary */ - { - sum = add16(sum, *x++); - len--; - } + + acc_sum = sum; + if ((u32) buf & 2) { /* Align to 32-bit boundary */ + add32(acc_sum, *buf++); + len =- 2; + } rest = len & 1; - len >>= 1; - tmp = 0; - xx = (u32 *) x; - for (xx--; len; --len); - tmp = add32(tmp, *++xx); - xx++; - sum = add16(sum, add16(tmp & 0xffff, tmp >> 16U)); - if (rest) - sum = add16(sum, *(u16 *) xx); - return sum; + len >>= 2; + buf_u32 = (u32 *) buf; + for(buf_u32--; len; --len) + acc_sum = add32(acc_sum, *++buf_u32); + + if (rest) { + buf = (u16 *)(buf_u32++); + add32(acc_sum, *buf); + } + + /* Add back carry outs from top 16 bits to low 16 bits. + */ + acc_sum = (acc_sum >> 16) + (acc_sum & 0xffff); /* add high-16 to low-16 */ + acc_sum += (acc_sum >> 16); /* add carry */ + return acc_sum; } static u16 -- 1.6.4.4

1 1

[PATCH] ipsum_calc_block: Optimize size and speed
by Joakim Tjernlund 23 Apr '10

23 Apr '10

This is a much simpler and efficent impl. of the IP checksum. It is a dry port from Quagga and I have not tested it. --- lib/checksum.c | 44 +++++++++++--------------------------------- 1 files changed, 11 insertions(+), 33 deletions(-) diff --git a/lib/checksum.c b/lib/checksum.c index 33cb386..b836bdb 100644 --- a/lib/checksum.c +++ b/lib/checksum.c @@ -15,25 +15,10 @@ #include "nest/bird.h" #include "checksum.h" -static u16 /* One-complement addition */ -add16(u16 sum, u16 x) -{ - u16 z = sum + x; - return z + (z < sum); -} - -static u32 -add32(u32 sum, u32 x) -{ - u32 z = sum + x; - return z + (z < sum); -} - static u16 ipsum_calc_block(u16 *x, unsigned len, u16 sum) { - int rest; - u32 tmp, *xx; + u32 tmp; /* * A few simple facts about the IP checksum (see RFC 1071 for detailed @@ -51,23 +36,16 @@ ipsum_calc_block(u16 *x, unsigned len, u16 sum) if (!len) return sum; len >>= 1; - if ((unsigned long) x & 2) /* Align to 32-bit boundary */ - { - sum = add16(sum, *x++); - len--; - } - rest = len & 1; - len >>= 1; - tmp = 0; - xx = (u32 *) x; - while (len) - { - tmp = add32(tmp, *xx++); - len--; - } - sum = add16(sum, add16(tmp & 0xffff, tmp >> 16U)); - if (rest) - sum = add16(sum, *(u16 *) xx); + tmp = sum; + for(x--; len; --len) + tmp += *++x; + /* + * Add back carry outs from top 16 bits to low 16 bits. + */ + tmp = (tmp >> 16) + (tmp & 0xffff); /* add high-16 to low-16 */ + tmp += (tmp >> 16); /* add carry */ + sum = ~tmp; /* ones-complement, then truncate to 16 bits */ + return sum; } -- 1.6.4.4

5 28

Re: OSPF performance/SPF calculations
by Joakim Tjernlund 23 Apr '10

23 Apr '10

Joakim Tjernlund/Transmode wrote on 2010/04/21 22:04:06: > > Ondrej Zajicek <santiago(a)crfreenet.org> wrote on 2010/04/21 20:15:07: > > On Wed, Apr 21, 2010 at 09:41:47AM +0200, Joakim Tjernlund wrote: > > > I am using Quagga ATM but I had a quick look at BIRD and I got a few > > > observations. > > > > Hello. Thank you for your tips and notes. > > > > > The LSA/checksum code seem very inefficient. > > > LSAs are built allocating/reallocing bits > > > of memory. This is slow and will case memory fragmentation. > > > > You mean lsab_alloc() in originate_rt_lsa_body()? > > This allocation is just a sequential allocation in a persistent memory buffer, > > therefore it is very efficient (in most cases just increase of lsab_used counter) > > and there si no memory fragmentation (all is done inside a persistent memory buffer). > > Yes, you do realloc on small amounts of memory. Also, receives LSAs > seems to be impl. differently so you need handle these somewhat > differently. > > > > > The fletcher checksum is very slow as it has extra tests in the hot path and also > > > flips endian in the LSA back and forth. > > > > Do you have some suggestions for a better algorithm, or just a better > > implementation? Yes, the problem with flipping endianity is known. > > I do not studied this part of the code yet (the checksum algorithm). > > Yes, but not at the moment. The endian problem should be addressed when you > build the lsa. Does this help at all? In any case, the (int) cast should be there.

2 8

Re: [PATCH] ipsum_calc_block: Optimize size and speed
by Joakim Tjernlund 23 Apr '10

23 Apr '10

Joakim Tjernlund/Transmode wrote on 2010/04/23 16:14:58: > > > > > Hello! > > > > > But you can't get rid of: > > > z + (z < sum) > > > which is the real bottleneck. Perhaps this doesn't cost much > > > on high end CPUs but it sure does on embedded CPUs > > > > Why should it be? It can be compiled as a sequence of "add with carry" > > instructions, can't it? > Yes, but have you seen gcc do that? I havn't, perhaps gcc has become smarter > recently? > > Jocke Just tried this and it didn't with gcc 3.4.3 on PowerPC Some arch does not have an add with carry insn(MIPS?) Jocke unsigned long add32(unsigned long sum, unsigned long x) { unsigned long z = sum + x; return z + (z < sum); } /* gcc -O3 -S gives: .file "addc.c" .gnu_attribute 4, 2 .gnu_attribute 8, 1 .section ".text" .align 2 .globl add32 .type add32, @function

2 2

possible bug: bgp md5 authentication and multiple source ip addresses
by Wolfgang Hennerbichler 23 Apr '10

23 Apr '10

Fellow BIRD users, The Vienna Internet Exchange is using BIRD now in production mode. No issues so far, BIRD runs perfectly smooth. Additionally I have now deployed a quarantine route server that would simulate real peerings in a quarantine setup, in order to check stuff on new peers. by doing so, I've setup one instance that should simulate 3 different BGP Peerings on each address-family. ip setup as follows: quarantine:/etc# ip addr sho dev eth1 3: eth1: <BROADCAST,MULTICAST,PROMISC,UP,LOWER_UP> mtu 1500 qdisc pfifo_fast state UP qlen 1000 link/ether 00:16:3e:99:02:51 brd ff:ff:ff:ff:ff:ff inet 193.203.0.1/24 scope global eth1 inet 193.203.0.2/24 scope global secondary eth1 inet 193.203.0.25/24 scope global secondary eth1 inet6 2001:7f8:30:0:1:1:0:1120/64 scope global valid_lft forever preferred_lft forever inet6 2001:7f8:30:0:1:1:0:1853/64 scope global valid_lft forever preferred_lft forever inet6 fe80::216:3eff:fe99:251/64 scope link valid_lft forever preferred_lft forever we see the first IP 193.203.0.1 is considered the 'primary' IP on linux. now I've setup BIRD to peer on the different source interfaces and from different ASes to simulate productive routers: protocol bgp R1 { debug all; local as 1120; neighbor 193.203.0.3 as 1267; import all; export none; table T1; password "xyz"; source address 193.203.0.1; route limit 15000; start delay time 1; } protocol bgp R2 { debug all; local as 1121; neighbor 193.203.0.3 as 1267; import all; export none; table T2; password "xyz"; source address 193.203.0.2; route limit 15000; start delay time 1; } ... nevertheless only the peering with source 193.203.0.1 - the primary IP - comes up, source 193.203.0.2 stays down, I see in the tcpdump log that MD5 can't be checked. This works on IPv6, but it seems that IPv4 somehow doesn't honour the source address field when generating the md5 hashes. Can you confirm this is a bug? Am I overseeing something? I am using linux 2.6.33.2 Wolfgang -- www.vix.at | www.aco.net wh(a)univie.ac.at | WH844-RIPE Vienna University Computer Center

3 4

[PATCH] fix cross compilation
by Joakim Tjernlund 23 Apr '10

23 Apr '10

Make ./configure --host=powerpc-softfloat-linux-gnu use the detected cross compiler to do incremental linking. Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund(a)transmode.se> --- tools/Rules.in | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/tools/Rules.in b/tools/Rules.in index 79a15fa..e4598e2 100644 --- a/tools/Rules.in +++ b/tools/Rules.in @@ -66,7 +66,7 @@ else subdir: all.o all.o: $(objs) - $(LD) -r -o $@ $^ + $(CC) -nostdlib -Wl,-r -o $@ $^ endif -- 1.6.4.4

1 0