- Bird-users - Mailing Lists

bird: KIF: Invalid broadcast address 255.255.255.255 for em1
by Job Snijders 10 Nov '15

10 Nov '15

Hi Fellow BIRD users, It appears that BIRD does not fully appreciate RFC3021 style addresses on Ubuntu 15.04, when I start BIRD: syslog:Nov 10 15:25:15 eunetworks-2 bird: KIF: Invalid broadcast address 255.255.255.255 for em1 syslog:Nov 10 15:25:15 eunetworks-2 bird: KIF: Invalid broadcast address 255.255.255.255 for p2p2.1003 syslog:Nov 10 15:25:15 eunetworks-2 bird: Started root@eunetworks-2: # ip -4 addr show dev em1 2: em1: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc mq state UP group default qlen 1000 inet 94.142.247.237/31 brd 255.255.255.255 scope global em1 valid_lft forever preferred_lft forever root@eunetworks-2: # ip -4 addr show dev p2p2.1003 14: p2p2.1003@p2p2: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UP group default inet 78.152.32.177/31 brd 255.255.255.255 scope global p2p2.1003 valid_lft forever preferred_lft forever Should I configure the Linux side of things differently or is this something that needs resolving in BIRD itself? root@eunetworks-2:~# uname -a Linux eunetworks-2 3.19.0-32-generic #37-Ubuntu SMP Wed Oct 21 10:23:06 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux root@eunetworks-2:~# dpkg -l | grep bird ii bird 1.5.0-1+vivid+1 amd64 Internet Routing Daemon root@eunetworks-2:~# lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 15.04 Release: 15.04 Codename: vivid Kind regards, Job

2 2

bird scalability
by Иван Разин 10 Nov '15

10 Nov '15

Hello! We quite successfully use Bird in our infrastructure and now want to expand it. I would like to know how it will behave in the following conditions are met: 4 BGP full view 70 Bird ospf routers in the same area 10000 ospf routes Did someone experience in the deployment of such a scheme and whether there were any difficulties or problems? -- Razin Ivan

2 1

'Aggregate' pipe protocol - is it planned?
by Andrew 10 Nov '15

10 Nov '15

Hi all. IMHO it'll be good to have 'aggregate' protocol (like 'pipe' one) for route count decreasing in system routing table (which results in routing performance increase)) and for using bird server as routing server for hardware routers/L3 switches which usually have not too big TCAM. Is such protocol planned for future?

1 0

1024 sessions problem
by Alexander V. Chernikov 03 Nov '15

03 Nov '15

3 3

Route update question
by Jigar Mehta 31 Oct '15

31 Oct '15

I am using my own protocol and wanted to understand more about handling of route update. When my protocol receives a route, I inform the core using rte_update() and pass on the new route and when I need to delete I set new = NULL and call rte_update(). Problem : 1. This is the initial route that was installed in the table. Route1 10.0.1.0/24 Metric : 10 2. Received a better route with Metric as 5, so i call rte_update and pass on the new route. So now, I have Route1 10.0.1.0/24 Metric: 5 3. Protocol again receives an update to delete the cost 5 route (step 2) . However when I do that, I see that I no longer have any route to 10.0.1.0/24 instead of having a higher cost route (cost 10 ). When I enable debug, I see that during delete, when we fall through rte_recalculate() in core code, net->routes is being set to null and so we never do recalculation for new optimal route. Is there something I need to do after we call rte_update() to install route so I save the old_best route. Thanks, -- Jigar Mehta

2 1

bird 1.5.0-4 ospf Inactivity timer expired.
by Andrey Kitsul 29 Oct '15

29 Oct '15

Hello, I have three Ubuntu physical machines with quagga (ospf area0/bgp with full route table on 2-4 uplink) and one whit bird (ospf only). On one of the routers (ospf/bgp) replace quagga on bird. Configuration bird attachment. After replacing the CPU load there is increased by 10-15%. On top Bird periodically consumes up to 90% of the CPU, and at a given time is restarted ospf: Inactivity timer expired for nbr. On one interfaces eth1.2508 to another bird router, I increased the Dead interval to 10 seconds. And it helped. What could be my problem? Large filters BGP, smallest ospf hello/dead interval or something else? One of restarts occurred at 13:13:13, OSPF trace in attachment, OSPF net packet in attachment. -- Кицул Андрей администратор Unix-систем ЗАО "НГС" +7-923-111-3940

2 16

build failure with -D_FORTIFY_SOURCE=2
by Vladimir Lettiev 26 Oct '15

26 Oct '15

Hi. Just got a build failure with recent gcc with enabled option FORTIFY_SOURCE=2: In function 'strncpy', inlined from 'rip_outgoing_authentication' at ../../../proto/rip/auth.c:134:5: /usr/include/bits/string3.h:120:10: error: call to __builtin___strncpy_chk will always overflow destination buff er return __builtin___strncpy_chk (__dest, __src, __len, __bos (__dest)); ^ make[1]: *** [auth.o] Error 1 make[1]: *** Waiting for unfinished jobs.... make[1]: Leaving directory `/usr/src/RPM/BUILD/bird-1.5.0/build-bird6/proto/rip' make: *** [subdir] Error 2 make: Leaving directory `/usr/src/RPM/BUILD/bird-1.5.0/build-bird6' There is proto/rip/auth.c:134: strncpy( (char *) (&block->packetlen), passwd->password, 16); destination packetlen is u16, so gcc thinks it is overflow. Is it possible to change strncpy with memcpy? -- Vladimir Lettiev aka crux ✉ theCrux(a)gmail.com

2 2

Does Bird has NetConf support?
by FABIO ZACCANTTE 23 Oct '15

23 Oct '15

Hi everyone, I am new in Bird, i would like know if Bird have NetConf support? Regards, Fabio.

3 3

OSPF interfaces issue
by Jigar Mehta 11 Oct '15

11 Oct '15

Hi, I wanted some help regarding a problem I was seeing when i had multiple interfaces with same ip address . I have multiple routing domains setup so i have valid cases to have same ip address on different interfaces (so i have seperate routing tables for each instance). When I do a show ospf interface for each ospf protocol instance, it seems to correctly dump the interface . When I did a packet capture, it shows incoming/outgoing hello packets, but when I enabled debug, i can see that it never prints a "hello packet received" message(but prints "hello packet sent") although, i can see the peer sending ospf hello packets. This seems to be a problem with only one instance and not both. Any help or assistance on this is highly appreciated. Setup : BIRD 1.4.5 ready. bird> show interface eth-0 up (index=1424) MultiAccess Broadcast Multicast AdminUp LinkUp MTU=1500 10.0.1.11/24 (Primary, scope site) eth-1 up (index=1425) MultiAccess Broadcast Multicast AdminUp LinkUp MTU=1500 10.0.130.11/24 (Primary, scope site) eth-2 up (index=1426) MultiAccess Broadcast Multicast AdminUp LinkUp MTU=1500 10.0.1.11/24 (Primary, scope site) Config : <snipped> protocol ospf ospf_0 { table T0; import all; export all; area 0 { interface "eth-2" { hello 10; dead 40; priority 0; }; }; } protocol ospf ospf_1 { table T1; import all; export all; area 0 { interface "eth-0" { hello 10; dead 40; priority 0; }; }; area 10 { interface "eth-1" { hello 10; dead 40; priority 0; }; }; } -- Jigar Mehta

2 2

[PATCH] Add the Babel routing protocol to Bird
by Toke Høiland-Jørgensen 09 Oct '15

09 Oct '15

This adds the Babel routing protocol (RFC6126) to Bird. It is a complete implementation of the IPv6 subset of RFC6126, but does not implement any of the extensions. Compared to the RFC patch posted earlier, this patch implements several more SHOULD parts of the protocol, has updated interactions with the Bird core, and uses fewer timers and resource pools. In addition, several other tweaks and fixes have been made following interoperability testing with the official babeld. The implementation of the protocol is now, to the best of my knowledge, complete. The only exception is the propagation of IPv4 routes which has deliberately been left out due to Bird's lack of support for a dual-stack operation mode. Juliusz Chroboczek, the author of the Babel spec, has expressed a preference to not have an IPv4-only implementation of Babel, so as to avoid fragmenting the community. I have followed that preference, and so this implementation ignores IPv4 route TLVs entirely. As far as interactions with Bird core is concerned, the main thing missing is the reconfiguration support; I still haven't decided exactly what is the right thing to do here. But probably some variant of the OSPF protocol's logic is needed. And of course documentation of the configuration options. But since I expect to have to do at least another iteration on this, I decided to defer that in the interest of keeping the ball rolling. Signed-off-by: Toke Høiland-Jørgensen <toke(a)toke.dk> Cc: babel-users(a)lists.alioth.debian.org --- configure.in | 3 + lib/ip.h | 1 + nest/proto.c | 4 + nest/protocol.h | 2 +- nest/route.h | 11 +- proto/Doc | 1 + proto/babel/Doc | 2 + proto/babel/Makefile | 5 + proto/babel/babel.c | 1558 ++++++++++++++++++++++++++++++++++++++++++++++++++ proto/babel/babel.h | 434 ++++++++++++++ proto/babel/config.Y | 84 +++ proto/babel/packet.c | 636 +++++++++++++++++++++ sysdep/autoconf.h.in | 1 + 13 files changed, 2740 insertions(+), 2 deletions(-) create mode 100644 proto/babel/Doc create mode 100644 proto/babel/Makefile create mode 100644 proto/babel/babel.c create mode 100644 proto/babel/babel.h create mode 100644 proto/babel/config.Y create mode 100644 proto/babel/packet.c diff --git a/configure.in b/configure.in index c81709e..1265565 100644 --- a/configure.in +++ b/configure.in @@ -206,6 +206,9 @@ fi AC_SUBST(iproutedir) all_protocols="$proto_bfd bgp ospf pipe $proto_radv rip static" +if test "$ip" = ipv6 ; then + all_protocols="$all_protocols babel" +fi all_protocols=`echo $all_protocols | sed 's/ /,/g'` if test "$with_protocols" = all ; then diff --git a/lib/ip.h b/lib/ip.h index 90bb7f8..fa18da1 100644 --- a/lib/ip.h +++ b/lib/ip.h @@ -23,6 +23,7 @@ #define IP6_OSPF_ALL_ROUTERS ipa_build6(0xFF020000, 0, 0, 5) #define IP6_OSPF_DES_ROUTERS ipa_build6(0xFF020000, 0, 0, 6) #define IP6_RIP_ROUTERS ipa_build6(0xFF020000, 0, 0, 9) +#define IP6_BABEL_ROUTERS ipa_build6(0xFF020000, 0, 0, 0x00010006) #define IP4_NONE _MI4(0) #define IP6_NONE _MI6(0,0,0,0) diff --git a/nest/proto.c b/nest/proto.c index 6531083..5804b73 100644 --- a/nest/proto.c +++ b/nest/proto.c @@ -919,6 +919,10 @@ protos_build(void) proto_build(&proto_bfd); bfd_init_all(); #endif +#ifdef CONFIG_BABEL + proto_build(&proto_babel); + bfd_init_all(); +#endif proto_pool = rp_new(&root_pool, "Protocols"); proto_flush_event = ev_new(proto_pool); diff --git a/nest/protocol.h b/nest/protocol.h index 8c49154..ec78735 100644 --- a/nest/protocol.h +++ b/nest/protocol.h @@ -76,7 +76,7 @@ void protos_dump_all(void); extern struct protocol proto_device, proto_radv, proto_rip, proto_static, - proto_ospf, proto_pipe, proto_bgp, proto_bfd; + proto_ospf, proto_pipe, proto_bgp, proto_bfd, proto_babel; /* * Routing Protocol Instance diff --git a/nest/route.h b/nest/route.h index 6067526..a5d71a8 100644 --- a/nest/route.h +++ b/nest/route.h @@ -214,6 +214,12 @@ typedef struct rte { u8 suppressed; /* Used for deterministic MED comparison */ } bgp; #endif +#ifdef CONFIG_BABEL + struct { + u16 metric; /* Babel metric */ + u64 router_id; /* Babel router id */ + } babel; +#endif struct { /* Routes generated by krt sync (both temporary and inherited ones) */ s8 src; /* Alleged route source (see krt.h) */ u8 proto; /* Kernel source protocol ID */ @@ -368,6 +374,7 @@ typedef struct rta { #define RTS_OSPF_EXT2 10 /* OSPF external route type 2 */ #define RTS_BGP 11 /* BGP route */ #define RTS_PIPE 12 /* Inter-table wormhole */ +#define RTS_BABEL 13 /* Babel route */ #define RTC_UNICAST 0 #define RTC_BROADCAST 1 @@ -416,7 +423,8 @@ typedef struct eattr { #define EAP_RIP 2 /* RIP */ #define EAP_OSPF 3 /* OSPF */ #define EAP_KRT 4 /* Kernel route attributes */ -#define EAP_MAX 5 +#define EAP_BABEL 5 /* Babel attributes */ +#define EAP_MAX 6 #define EA_CODE(proto,id) (((proto) << 8) | (id)) #define EA_PROTO(ea) ((ea) >> 8) @@ -538,6 +546,7 @@ extern struct protocol *attr_class_to_protocol[EAP_MAX]; #define DEF_PREF_RIP 120 /* RIP */ #define DEF_PREF_BGP 100 /* BGP */ #define DEF_PREF_PIPE 70 /* Routes piped from other tables */ +#define DEF_PREF_BABEL 42 /* Babel */ #define DEF_PREF_INHERITED 10 /* Routes inherited from other routing daemons */ diff --git a/proto/Doc b/proto/Doc index 7863472..04c25bc 100644 --- a/proto/Doc +++ b/proto/Doc @@ -1,4 +1,5 @@ H Protocols +C babel C bfd C bgp C ospf diff --git a/proto/babel/Doc b/proto/babel/Doc new file mode 100644 index 0000000..2480239 --- /dev/null +++ b/proto/babel/Doc @@ -0,0 +1,2 @@ +S babel.c +S packet.c diff --git a/proto/babel/Makefile b/proto/babel/Makefile new file mode 100644 index 0000000..a27b010 --- /dev/null +++ b/proto/babel/Makefile @@ -0,0 +1,5 @@ +source=babel.c packet.c +root-rel=../../ +dir-name=proto/babel + +include ../../Rules diff --git a/proto/babel/babel.c b/proto/babel/babel.c new file mode 100644 index 0000000..d991b35 --- /dev/null +++ b/proto/babel/babel.c @@ -0,0 +1,1558 @@ +/* -*- c-file-style: "gnu"; indent-tabs-mode: nil; -*- + * + * The Babel protocol + * + * Copyright (c) 2015 Toke Høiland-Jørgensen + * + * Can be freely distributed and used under the terms of the GNU GPL. + * + * This file contains the main routines for handling and sending TLVs, as + * well as timers and interaction with the nest. + */ + +/** + * DOC: The Babel protocol + * + * Babel (RFC6126) is a loop-avoiding distance-vector routing protocol that is + * robust and efficient both in ordinary wired networks and in wireless mesh + * networks. + * + * The Babel protocol keeps state for each neighbour in a &babel_neighbor + * struct, tracking received hellos and I Heard You (IHU) messages. A + * &babel_interface struct keeps hello and update timers for each interface, and + * a separate hello seqno is maintained for each interface. + * + * For each prefix, Babel keeps track of both the possible routes + * (with next hop and router IDs), as well as the feasibility distance for each + * prefix and router id. The prefix itself is tracked in a &babel_entry struct, + * while the possible routes for the prefix are tracked as &babel_route entries + * and the feasibility distance is maintained through &babel_source structures. + * + * The main route selection is done in babel_select_route(). This is called when + * an update for a prefix is received, when a new prefix is received from the + * nest, and when a prefix expiry timer fires. It performs feasibility checks on + * the available routes for the prefix and selects the one with the lowest + * metric. + */ + +#undef LOCAL_DEBUG +#define LOCAL_DEBUG 1 + +#include "babel.h" + + +#undef TRACE +#define TRACE(level, msg, args...) do { if (p->p.debug & level) { log(L_TRACE "%s: " msg, p->p.name , ## args); } } while(0) +#define BAD( x ) { log( L_REMOTE "%s: " x, p->p.name ); return 1; } + +/* computes a-b % 65535 for u16 datatypes */ +static inline u16 +diff_mod64k(u16 a, u16 b) +{ + return a >= b ? a-b : 0xffff-b+a; +} +/* Is one number larger than another mod 65535? Since diff_mod64k is always >= + 0, just use a simple cutoff value to determine if the difference is small + enough that one is really larger. Since these comparisons are only made for + values that should not differ by more than a few numbers, this should be + safe.*/ +static inline u16 ge_mod64k(u16 a, u16 b) +{ + return diff_mod64k(a,b) < 0xfff0; +} + +static void babel_new_interface(struct babel_proto *p, struct iface *new, + unsigned long flags, struct iface_patt *patt); +static void expire_hello(struct babel_neighbor *bn); +static void expire_ihu(struct babel_neighbor *bn); +static void expire_sources(struct babel_entry *e); +static void expire_route(struct babel_route *r); +static void refresh_route(struct babel_route *r); +static void babel_dump_entry(struct babel_entry *e); +static void babel_dump_route(struct babel_route *r); +static void babel_select_route(struct babel_entry *e); +static void babel_send_route_request(struct babel_entry *e, struct babel_neighbor *n); +static int cache_seqno_request(struct babel_proto *p, ip_addr prefix, u8 plen, + u64 router_id, u16 seqno); + + +static void +babel_init_entry(struct fib_node *n) +{ + struct babel_entry *e = (struct babel_entry *)n; + e->proto = NULL; + e->selected = NULL; + init_list(&e->sources); + init_list(&e->routes); +} + + +static inline struct babel_entry * +babel_find_entry(struct babel_proto *p, ip_addr prefix, u8 plen) +{ + return fib_find(&p->rtable, &prefix, plen); +} + +static struct babel_entry * +babel_get_entry(struct babel_proto *p, ip_addr prefix, u8 plen) +{ + struct babel_entry *e = babel_find_entry(p, prefix, plen); + if(e) return e; + e = fib_get(&p->rtable, &prefix, plen); + e->proto = p; + return e; +} + +void +babel_flush_entry(struct babel_entry *e) +{ + struct babel_proto *p = e->proto; + TRACE(D_EVENTS, "Flushing entry %I/%d", e->n.prefix, e->n.pxlen); + rem_node(&e->garbage_node); + if(p) fib_delete(&p->rtable, e); +} + +static struct babel_source * +babel_find_source(struct babel_entry *e, u64 router_id) +{ + struct babel_source *s; + WALK_LIST(s, e->sources) + if(s->router_id == router_id) + return s; + return NULL; +} + +static struct babel_source * +babel_get_source(struct babel_entry *e, u64 router_id) +{ + struct babel_proto *p = e->proto; + struct babel_source *s = babel_find_source(e, router_id); + if(s) return s; + s = sl_alloc(p->source_slab); + s->router_id = router_id; + s->expires = now + BABEL_GARBAGE_INTERVAL; + s->e = e; + s->seqno = 0; + s->metric = BABEL_INFINITY; + add_tail(&e->sources, NODE s); + return s; +} + +static void +expire_sources(struct babel_entry *e) +{ + struct babel_proto *p = e->proto; + struct babel_source *n, *nx; + WALK_LIST_DELSAFE(n, nx, e->sources) { + if(n->expires && n->expires <= now) { + rem_node(NODE n); + sl_free(p->source_slab, n); + } + } + if(EMPTY_LIST(e->sources) && EMPTY_LIST(e->routes)) + add_tail(&p->garbage, &e->garbage_node); /* to be removed later */ +} + +static struct babel_route * +babel_find_route(struct babel_entry *e, struct babel_neighbor *n) +{ + struct babel_route *r; + WALK_LIST(r, e->routes) + if(r->neigh == n) + return r; + return NULL; +} + +static struct babel_route * +babel_get_route(struct babel_entry *e, struct babel_neighbor *n) +{ + struct babel_proto *p = e->proto; + struct babel_route *r = babel_find_route(e,n); + if(r) return r; + r = sl_alloc(p->route_slab); + memset(r, 0, sizeof(*r)); + r->neigh = n; + r->e = e; + if(n) + r->expires = now + BABEL_GARBAGE_INTERVAL; /* default until we get updates to set expiry time */ + add_tail(&e->routes, NODE r); + if(n) add_tail(&n->routes, NODE &r->neigh_route); + return r; +} + +static void +babel_flush_route(struct babel_route *r) +{ + struct babel_proto *p = r->e->proto; + DBG("Flush route %I/%d router_id %0lx neigh %I\n", + r->e->n.prefix, r->e->n.pxlen, r->router_id, r->neigh ? r->neigh->addr : IPA_NONE); + rem_node(NODE r); + if(r->neigh) rem_node(&r->neigh_route); + if(r->e->selected == r) r->e->selected = NULL; + sl_free(p->route_slab, r); +} + +static void +expire_route(struct babel_route *r) +{ + struct babel_entry *e = r->e; + struct babel_proto *p = r->e->proto; + TRACE(D_EVENTS, "Route expiry timer for %I/%d router_id %0lx fired", + r->e->n.prefix, r->e->n.pxlen, r->router_id); + if(r->metric < BABEL_INFINITY) { + r->metric = BABEL_INFINITY; + r->expires = now + r->expiry_interval; + } else { + babel_flush_route(r); + } + + babel_select_route(e); +} + +static void +refresh_route(struct babel_route *r) +{ + if(!r->neigh || r != r->e->selected) return; + babel_send_route_request(r->e, r->neigh); +} + +static void +babel_expire_routes(struct babel_proto *p) +{ + struct babel_entry *e; + struct babel_route *r, *rx; + node *n; + FIB_WALK(&p->rtable, n) { + e = (struct babel_entry *)n; + WALK_LIST_DELSAFE(r, rx, e->routes) { + if(r->refresh_time && r->refresh_time <= now) { + refresh_route(r); + r->refresh_time = 0; + } + if(r->expires && r->expires <= now) + expire_route(r); + } + expire_sources(e); + } FIB_WALK_END; + WALK_LIST_FIRST(n, p->garbage) { + e = SKIP_BACK(struct babel_entry, garbage_node, n); + babel_flush_entry(e); + } +} + +static struct babel_neighbor * +babel_find_neighbor(struct babel_iface *bif, ip_addr addr) +{ + struct babel_neighbor *bn; + WALK_LIST(bn, bif->neigh_list) + if(ipa_equal(bn->addr, addr)) + return bn; + return NULL; +} + +static struct babel_neighbor * +babel_get_neighbor(struct babel_iface *bif, ip_addr addr) +{ + struct babel_neighbor *bn = babel_find_neighbor(bif, addr); + if(bn) return bn; + bn = mb_allocz(bif->pool, sizeof(struct babel_neighbor)); + bn->bif = bif; + bn->addr = addr; + bn->txcost = BABEL_INFINITY; + init_list(&bn->routes); + add_tail(&bif->neigh_list, NODE bn); + return bn; +} + +static void +babel_expire_neighbors(struct babel_proto *p) +{ + struct babel_iface *bif; + struct babel_neighbor *bn, *bnx; + WALK_LIST(bif, p->interfaces) { + WALK_LIST_DELSAFE(bn, bnx, bif->neigh_list) { + if(bn->hello_expiry && bn->hello_expiry <= now) + expire_hello(bn); + if(bn->ihu_expiry && bn->ihu_expiry <= now) + expire_ihu(bn); + } + } +} + + +/** + From the RFC (section 3.5.1): + + a route advertisement carrying the quintuple (prefix, plen, router-id, seqno, + metric) is feasible if one of the following conditions holds: + + - metric is infinite; or + + - no entry exists in the source table indexed by (id, prefix, plen); or + + - an entry (prefix, plen, router-id, seqno', metric') exists in the source + table, and either + + - seqno' < seqno or + - seqno = seqno' and metric < metric'. +*/ +static inline int +is_feasible(struct babel_source *s, u16 seqno, u16 metric) +{ + if(!s || metric == BABEL_INFINITY) return 1; + return (seqno > s->seqno + || (seqno == s->seqno && metric < s->metric)); +} + +static u16 +babel_compute_rxcost(struct babel_neighbor *bn) +{ + struct babel_iface *bif = bn->bif; + struct babel_proto *p = bif->proto; + u8 n, missed; + u16 map=bn->hello_map; + + if(!map) return BABEL_INFINITY; + n = __builtin_popcount(map); // number of bits set + missed = bn->hello_n-n; + + if(bif->cf->type == BABEL_IFACE_TYPE_WIRED) { + /* k-out-of-j selection - Appendix 2.1 in the RFC. */ + DBG("Missed %d hellos from %I\n", missed, bn->addr); + /* Link is bad if more than half the expected hellos were lost */ + return (missed > 0 && n/missed < 2) ? BABEL_INFINITY : bif->cf->rxcost; + } else if(bif->cf->type == BABEL_IFACE_TYPE_WIRELESS) { + /* ETX - Appendix 2.2 in the RFC. + + beta = prob. of successful transmission. + rxcost = BABEL_RXCOST_WIRELESS/beta + + Since: beta = 1-missed/bn->hello_n = n/bn->hello_n + Then: rxcost = BABEL_RXCOST_WIRELESS * bn->hello_n / n + */ + if(!n) return BABEL_INFINITY; + return BABEL_RXCOST_WIRELESS * bn->hello_n / n; + } else { + BAD("Unknown interface type!"); + } +} + + +static u16 +compute_cost(struct babel_neighbor *bn) +{ + struct babel_iface *bif = bn->bif; + struct babel_proto *p = bif->proto; + u16 rxcost = babel_compute_rxcost(bn); + if(rxcost == BABEL_INFINITY) return rxcost; + else if(bif->cf->type == BABEL_IFACE_TYPE_WIRED) { + /* k-out-of-j selection - Appendix 2.1 in the RFC. */ + return bn->txcost; + } else if(bif->cf->type == BABEL_IFACE_TYPE_WIRELESS) { + /* ETX - Appendix 2.2 in the RFC */ + return (MAX(bn->txcost, BABEL_RXCOST_WIRELESS) * rxcost)/BABEL_RXCOST_WIRELESS; + } else { + BAD("Unknown interface type!"); + } +} + +/* Simple additive metric - Appendix 3.1 in the RFC */ +static u16 +compute_metric(struct babel_neighbor *bn, u16 metric) +{ + u16 cost = compute_cost(bn); + return (cost == BABEL_INFINITY) ? cost : cost+metric; +} + +static rte * +babel_build_rte(struct babel_proto *p, net *n, struct babel_route *r) +{ + rta *a; + rte *rte; + + rta A = { + .src = p->p.main_source, + .source = RTS_BABEL, + .scope = SCOPE_UNIVERSE, + .cast = RTC_UNICAST, + .dest = r->metric == BABEL_INFINITY ? RTD_UNREACHABLE : RTD_ROUTER, + .flags = 0, + .gw = r->next_hop, + }; + + if(r->neigh) { + A.from = r->neigh->addr; + A.iface = r->neigh->bif->iface; + } + + a = rta_lookup(&A); + rte = rte_get_temp(a); + rte->u.babel.metric = r->metric; + rte->u.babel.router_id = r->router_id; + rte->net = n; + rte->pflags = 0; + return rte; +} + +static void +babel_send_seqno_request(struct babel_entry *e) +{ + struct babel_proto *p = e->proto; + struct babel_route *r = e->selected; + struct babel_source *s = babel_find_source(e, r->router_id); + struct babel_iface *bif; + struct babel_tlv_seqno_request *tlv; + + if(s && cache_seqno_request(p, e->n.prefix, e->n.pxlen, r->router_id, s->seqno+1)) { + TRACE(D_EVENTS, "Sending seqno request for %I/%d router_id %0lx", + e->n.prefix, e->n.pxlen, r->router_id); + + WALK_LIST(bif, p->interfaces) { + tlv = babel_add_tlv_seqno_request(bif); + tlv->plen = e->n.pxlen; + tlv->seqno = s->seqno + 1; + tlv->hop_count = BABEL_INITIAL_HOP_COUNT; + tlv->router_id = r->router_id; + babel_put_addr(&tlv->header, e->n.prefix); + } + } +} + +static void +babel_unicast_seqno_request(struct babel_route *r) +{ + struct babel_entry *e = r->e; + struct babel_proto *p = e->proto; + struct babel_source *s = babel_find_source(e, r->router_id); + struct babel_iface *bif = r->neigh->bif; + struct babel_tlv_seqno_request *tlv; + if(s && cache_seqno_request(p, e->n.prefix, e->n.pxlen, r->router_id, s->seqno+1)) { + TRACE(D_EVENTS, "Sending seqno request for %I/%d router_id %0lx", + e->n.prefix, e->n.pxlen, r->router_id); + babel_new_unicast(bif); + tlv = babel_add_tlv_seqno_request(bif); + tlv->plen = e->n.pxlen; + tlv->seqno = s->seqno + 1; + tlv->hop_count = BABEL_INITIAL_HOP_COUNT; + tlv->router_id = r->router_id; + babel_put_addr(&tlv->header, e->n.prefix); + babel_send_unicast(bif, r->neigh->addr); + } +} + +static void +babel_send_route_request(struct babel_entry *e, struct babel_neighbor *n) +{ + struct babel_iface *bif = n->bif; + struct babel_proto *p = e->proto; + struct babel_tlv_route_request *tlv; + TRACE(D_PACKETS, "Babel: Sending route request for %I/%d to %I\n", + e->n.prefix, e->n.pxlen, n->addr); + babel_new_unicast(bif); + tlv = babel_add_tlv_route_request(bif); + babel_put_addr(&tlv->header, e->n.prefix); + tlv->plen = e->n.pxlen; + babel_send_unicast(bif, n->addr); +} + + +/** + * babel_select_route: + * @e: Babel entry to select the best route for. + * + * Select the best feasible route for a given prefix. This just selects the + * feasible route with the lowest metric. If this results in switching upstream + * router (identified by router id), the nest is notified of the new route. + * + * If no feasible route is available for a prefix that previously had a route + * selected, a seqno request is sent to try to get a valid route. In the + * meantime, the route is marked as infeasible in the nest (to blackhole packets + * going to it, as per the RFC). + * + * If no feasible route is available, and no previous route is selected, the + * route is removed from the nest entirely. + */ +static void +babel_select_route(struct babel_entry *e) +{ + struct babel_proto *p = e->proto; + net *n = net_get(p->p.table, e->n.prefix, e->n.pxlen); + struct babel_route *r, *cur = e->selected; + + /* try to find the best feasible route */ + WALK_LIST(r, e->routes) + if((!cur || r->metric < cur->metric) + && is_feasible(babel_find_source(e, r->router_id), + r->seqno, r->advert_metric)) + cur = r; + + if(cur && cur->neigh && ((!e->selected && cur->metric < BABEL_INFINITY) + || (e->selected && cur->metric < e->selected->metric))) { + TRACE(D_EVENTS, "Picked new route for prefix %I/%d: router id %0lx metric %d", + e->n.prefix, e->n.pxlen, cur->router_id, cur->metric); + /* Notify the nest of the update. If we change router ID, we also trigger + a global update. */ + if(!e->selected || + e->selected->metric == BABEL_INFINITY || + e->selected->router_id != cur->router_id) + + ev_schedule(p->update_event); + + e->selected = cur; + rte_update(&p->p, n, babel_build_rte(p, n, cur)); + } else if(!cur || cur->metric == BABEL_INFINITY) { + /* Couldn't find a feasible route. If we have a selected route, that means + it just became infeasible; so set it's metric to infinite and install it + (as unreachable), then send a seqno request. + + babel_build_rte() will set the unreachable flag if the metric is BABEL_INFINITY.*/ + if(e->selected) { + TRACE(D_EVENTS, "Lost feasible route for prefix %I/%d: sending update and seqno request", + e->n.prefix, e->n.pxlen); + e->selected->metric = BABEL_INFINITY; + rte_update(&p->p, n, babel_build_rte(p, n, e->selected)); + + ev_schedule(p->update_event); + babel_send_seqno_request(e); + } else { + /* No route currently selected, and no new one selected; this means we + don't have a route to this destination anymore (and were probably + called from an expiry timer). Remove the route from the nest. */ + TRACE(D_EVENTS, "Flushing route for prefix %I/%d", e->n.prefix, e->n.pxlen); + e->selected = NULL; + rte_update(&p->p, n, NULL); + } + } +} + +static void +babel_send_ack(struct babel_iface *bif, ip_addr dest, u16 nonce) +{ + struct babel_proto *p = bif->proto; + struct babel_tlv_ack *tlv; + TRACE(D_PACKETS, "Babel: Sending ACK to %I with nonce %d\n", dest, nonce); + babel_new_unicast(bif); + tlv = babel_add_tlv_ack(bif); + tlv->nonce = nonce; + babel_send_unicast(bif, dest); +} + +static void +babel_add_ihu(struct babel_iface *bif, struct babel_neighbor *bn) +{ + struct babel_tlv_ihu *tlv = babel_add_tlv_ihu(bif); + babel_put_addr_ihu(&tlv->header, bn->addr); + tlv->rxcost = babel_compute_rxcost(bn); + tlv->interval = bif->cf->ihu_interval*100; +} + +static void +babel_add_ihus(struct babel_iface *bif) +{ + struct babel_neighbor *bn; + WALK_LIST(bn, bif->neigh_list) + babel_add_ihu(bif,bn); +} + +static void +babel_send_ihu(struct babel_iface *bif, struct babel_neighbor *bn) +{ + struct babel_proto *p = bif->proto; + TRACE(D_PACKETS, "Babel: Sending IHUs"); + babel_new_unicast(bif); + babel_add_ihu(bif, bn); + babel_send_unicast(bif, bn->addr); +} + +void +babel_send_hello(struct babel_iface *bif, u8 send_ihu) +{ + struct babel_proto *p = bif->proto; + struct babel_tlv_hello *tlv; + TRACE(D_PACKETS, "Babel: Sending hello on interface %s", bif->ifname); + tlv = babel_add_tlv_hello(bif); + tlv->seqno = bif->hello_seqno++; + tlv->interval = bif->cf->hello_interval*100; + + if(send_ihu) babel_add_ihus(bif); +} + +static void +babel_hello_timer(timer *t) +{ + struct babel_iface *bif = t->data; + babel_send_hello(bif, (bif->cf->type == BABEL_IFACE_TYPE_WIRED && + bif->hello_seqno % BABEL_IHU_INTERVAL_FACTOR == 0)); +} + +/* Function to add router_id -- a router id TLV is always followed by an update + TLV, so add both atomically (which may send the queue), then fill in the + router ID and return the update TLV position. + + This prevents a full queue causing a packet to be sent with a router id TLV + as the last TLV (and so the update TLV in the next packet missing a router + id).*/ +static struct babel_tlv_update * +babel_add_router_id(struct babel_iface *bif, u64 router_id) +{ + struct babel_tlv_router_id *rid; + struct babel_tlv_update *upd; + rid = (struct babel_tlv_router_id *) babel_add_tlv_size(bif, + BABEL_TYPE_ROUTER_ID, + (sizeof(struct babel_tlv_router_id) + + sizeof(struct babel_tlv_update))); + rid->router_id = router_id; + upd = (struct babel_tlv_update *)(rid+1); + upd->header.type = BABEL_TYPE_UPDATE; + upd->header.length = sizeof(struct babel_tlv_update) - sizeof(struct babel_tlv_header); + return upd; +} + +void +babel_send_update(struct babel_iface *bif) +{ + struct babel_proto *p = bif->proto; + struct babel_tlv_update *upd; + struct babel_entry *e; + struct babel_route *r; + struct babel_source *s; + u64 router_id = 0; + TRACE(D_PACKETS, "Sending update on %s", bif->ifname); + FIB_WALK(&p->rtable, n) { + e = (struct babel_entry *)n; + r = e->selected; + if(!r) continue; + + if(r->router_id != router_id) { + upd = babel_add_router_id(bif, r->router_id); + router_id = r->router_id; + } else { + upd = babel_add_tlv_update(bif); + } + + /* Our own seqno might have changed, in which case we update the routes we + originate. */ + if(r->router_id == p->router_id && r->seqno < p->update_seqno) + r->seqno = p->update_seqno; + upd->plen = e->n.pxlen; + upd->interval = bif->cf->update_interval*100; + upd->seqno = r->seqno; + upd->metric = r->metric; + babel_put_addr(&upd->header, e->n.prefix); + + /* Update feasibility distance. */ + s = babel_get_source(e, r->router_id); + s->expires = now + BABEL_GARBAGE_INTERVAL; + if(upd->seqno > s->seqno + || (upd->seqno == s->seqno && upd->metric < s->metric)) { + s->seqno = upd->seqno; + s->metric = upd->metric; + } + } FIB_WALK_END; +} + +/* Sends and update on all interfaces. */ +static void +babel_global_update(void *arg) +{ + struct babel_proto *p = arg; + struct babel_iface *bif; + TRACE(D_EVENTS, "Sending global update. Seqno %d", p->update_seqno); + WALK_LIST(bif, p->interfaces) + bif->update_triggered = 1; +} + +static void +babel_update_timer(timer *t) +{ + struct babel_iface *bif = t->data; + struct babel_proto *p = bif->proto; + TRACE(D_EVENTS, "Update timer firing"); + bif->update_triggered = 1; +} + + +int +babel_handle_ack_req(struct babel_tlv_header *hdr, struct babel_parse_state *state) +{ + struct babel_tlv_ack_req *tlv = (struct babel_tlv_ack_req *)hdr; + struct babel_proto *p = state->proto; + TRACE(D_PACKETS, "Received ACK req nonce %d interval %d", tlv->nonce, tlv->interval); + if(tlv->interval) { + babel_send_ack(state->bif, state->saddr, tlv->nonce); + } + return 1; +} + +int +babel_handle_ack(struct babel_tlv_header *hdr, struct babel_parse_state *state) +{ + struct babel_tlv_ack *tlv = (struct babel_tlv_ack *)hdr; + struct babel_proto *p = state->proto; + TRACE(D_PACKETS, "Received ACK nonce %d", tlv->nonce); + /* We don't send any ACK requests, so no need to do anything with ACKs. */ + return 1; +} + +static void +babel_flush_neighbor(struct babel_neighbor *bn) +{ + struct babel_proto *p = bn->bif->proto; + struct babel_route *r; + node *n; + TRACE(D_EVENTS, "Flushing neighbor %I", bn->addr); + rem_node(NODE bn); + WALK_LIST_FIRST(n, bn->routes) { + r = SKIP_BACK(struct babel_route, neigh_route, n); + babel_flush_route(r); + } + mb_free(bn); +} + +static void +expire_hello(struct babel_neighbor *bn) +{ + bn->hello_map <<= 1; + if(bn->hello_n < 16) bn->hello_n++; + if(!bn->hello_map) { + babel_flush_neighbor(bn); + } +} + +static void +expire_ihu(struct babel_neighbor *bn) +{ + bn->txcost = BABEL_INFINITY; +} + + +/* update hello history according to Appendix A1 of the RFC */ +static void +update_hello_history(struct babel_neighbor *bn, u16 seqno, u16 interval) +{ + u8 diff; + if(seqno == bn->next_hello_seqno) {/* do nothing */} + /* if the expected and seen seqnos are within 16 of each other (mod 65535), + the modular difference is going to be less than 16 for one of the + directions. Otherwise, the values differ too much, so just reset. */ + else if(diff_mod64k(seqno, bn->next_hello_seqno) > 16 && + diff_mod64k(bn->next_hello_seqno,seqno) > 16) { + /* note state reset - flush entries */ + bn->hello_map = bn->hello_n = 0; + } else if((diff = diff_mod64k(bn->next_hello_seqno,seqno)) <= 16) { + /* sending node increased interval; reverse history */ + bn->hello_map >>= diff; + bn->hello_n = (diff < bn->hello_n) ? bn->hello_n - diff : 0; + } else if((diff = diff_mod64k(seqno,bn->next_hello_seqno)) <= 16) { + /* sending node decreased interval; fast-forward */ + bn->hello_map <<= diff; + bn->hello_n = MIN(bn->hello_n + diff, 16); + } + /* current entry */ + bn->hello_map = (bn->hello_map << 1) | 1; + bn->next_hello_seqno = seqno+1; + if(bn->hello_n < 16) bn->hello_n++; + bn->hello_expiry = now + (BABEL_HELLO_EXPIRY_FACTOR*interval)/100; +} + + +int +babel_handle_hello(struct babel_tlv_header *hdr, struct babel_parse_state *state) +{ + struct babel_tlv_hello *tlv = (struct babel_tlv_hello *)hdr; + struct babel_proto *p = state->proto; + struct babel_iface *bif = state->bif; + struct babel_neighbor *bn = babel_get_neighbor(bif, state->saddr); + TRACE(D_PACKETS, "Handling hello seqno %d interval %d", tlv->seqno, + tlv->interval, state->saddr); + update_hello_history(bn, tlv->seqno, tlv->interval); + if(bif->cf->type == BABEL_IFACE_TYPE_WIRELESS) + babel_send_ihu(bif, bn); + return 0; +} + +int +babel_handle_ihu(struct babel_tlv_header *hdr, struct babel_parse_state *state) +{ + struct babel_tlv_ihu *tlv = (struct babel_tlv_ihu *)hdr; + struct babel_proto *p = state->proto; + struct babel_iface *bif = state->bif; + ip_addr addr = babel_get_addr(hdr, state); + + if(!ipa_equal(addr, bif->addr)) return 1; // not for us + TRACE(D_PACKETS, "Handling IHU rxcost %d interval %d", tlv->rxcost, + tlv->interval); + struct babel_neighbor *bn = babel_get_neighbor(bif, state->saddr); + bn->txcost = tlv->rxcost; + bn->ihu_expiry = now + 1.5*(tlv->interval/100); + return 0; +} + +int +babel_handle_router_id(struct babel_tlv_header *hdr, struct babel_parse_state *state) +{ + struct babel_tlv_router_id *tlv = (struct babel_tlv_router_id *)hdr; + struct babel_proto *p = state->proto; + state->router_id = tlv->router_id; + TRACE(D_PACKETS, "Handling router ID %016lx", state->router_id); + return 0; +} + +int +babel_handle_next_hop(struct babel_tlv_header *hdr, struct babel_parse_state *state) +{ + state->next_hop = babel_get_addr(hdr, state); + return 0; +} + +int +babel_handle_update(struct babel_tlv_header *hdr, struct babel_parse_state *state) +{ + struct babel_tlv_update *tlv = (struct babel_tlv_update *)hdr; + struct babel_iface *bif = state->bif; + struct babel_proto *p = state->proto; + struct babel_neighbor *n; + struct babel_entry *e; + struct babel_source *s; + struct babel_route *r; + ip_addr prefix = babel_get_addr(hdr, state); + int feasible; + TRACE(D_PACKETS, "Handling update for %I/%d with seqno %d metric %d", + prefix, tlv->plen, tlv->seqno, tlv->metric); + if(tlv->flags & BABEL_FLAG_DEF_PREFIX) { + state->prefix = prefix; + } + if(tlv->flags & BABEL_FLAG_ROUTER_ID) { + u64 *buf = (u64*)&prefix; + memcpy(&state->router_id, buf+1, sizeof(u64)); + } + if(!state->router_id) + log(L_WARN "%s: Received update on %s with no preceding router id", p->p.name, bif->ifname); + + n = babel_find_neighbor(bif, state->saddr); + if(!n) { + DBG("Haven't heard from neighbor %I; ignoring update.\n", state->saddr); + return 1; + } + + if(state->router_id == p->router_id) { + DBG("Ignoring update for our own router ID.\n"); + return 1; + } + + /* RFC section 3.5.4: + + When a Babel node receives an update (id, prefix, seqno, metric) from a + neighbour neigh with a link cost value equal to cost, it checks whether it + already has a routing table entry indexed by (neigh, id, prefix). + + If no such entry exists: + + o if the update is unfeasible, it is ignored; + + o if the metric is infinite (the update is a retraction), the update is + ignored; + + o otherwise, a new route table entry is created, indexed by (neigh, id, + prefix), with seqno equal to seqno and an advertised metric equal to the + metric carried by the update. + + If such an entry exists: + + o if the entry is currently installed and the update is unfeasible, then + the behaviour depends on whether the router-ids of the two entries match. + If the router-ids are different, the update is treated as though it were + a retraction (i.e., as though the metric were FFFF hexadecimal). If the + router-ids are equal, the update is ignored; + + o otherwise (i.e., if either the update is feasible or the entry is not + currently installed), then the entry's sequence number, advertised + metric, metric, and router-id are updated and, unless the advertised + metric is infinite, the route's expiry timer is reset to a small multiple + of the Interval value included in the update. + +*/ + e = babel_find_entry(p, prefix, tlv->plen); + if(!e && tlv->metric == BABEL_INFINITY) + return 1; + + if(!e) e = babel_get_entry(p, prefix, tlv->plen); + + s = babel_find_source(e, state->router_id); /* for feasibility */ + r = babel_find_route(e, n); /* the route entry indexed by neighbour */ + feasible = is_feasible(s, tlv->seqno, tlv->metric); + + if(!r) { + + if(!feasible || tlv->metric == BABEL_INFINITY) + return 1; + + r = babel_get_route(e, n); + r->advert_metric = tlv->metric; + r->router_id = state->router_id; + r->metric = compute_metric(n, tlv->metric); + r->next_hop = state->next_hop; + r->seqno = tlv->seqno; + } else if(r == r->e->selected + && !feasible) { + + /* route is installed and update is infeasible - we may lose the route, so + send a unicast seqno request (section 3.8.2.2 second paragraph). */ + babel_unicast_seqno_request(r); + + if(state->router_id == s->router_id) return 1; + r->metric = BABEL_INFINITY; /* retraction */ + } else { + /* last point above - update entry */ + r->advert_metric = tlv->metric; + r->metric = compute_metric(n, tlv->metric); + r->router_id = state->router_id; + r->next_hop = state->next_hop; + r->seqno = tlv->seqno; + if(tlv->metric != BABEL_INFINITY) { + r->expiry_interval = (BABEL_ROUTE_EXPIRY_FACTOR*tlv->interval)/100; + r->expires = now + r->expiry_interval; + if(r->expiry_interval > BABEL_ROUTE_REFRESH_INTERVAL) + r->refresh_time = now + r->expiry_interval - BABEL_ROUTE_REFRESH_INTERVAL; + } + /* If the route is not feasible at this point, it means it is from another + neighbour than the one currently selected; so send a unicast seqno + request to try to get a better route (section 3.8.2.2 last paragraph). */ + if(!feasible) + babel_unicast_seqno_request(r); + } + babel_select_route(e); + return 0; +} + +/* A retraction is an update with an infinite metric. */ +static void babel_send_retraction(struct babel_iface *bif, ip_addr prefix, int plen) +{ + struct babel_proto *p = bif->proto; + struct babel_tlv_update *upd; + upd = babel_add_router_id(bif, p->router_id); + upd->plen = plen; + upd->interval = bif->cf->update_interval*100; + upd->seqno = p->update_seqno; + upd->metric = BABEL_INFINITY; + babel_put_addr(&upd->header, prefix); +} + +int +babel_handle_route_request(struct babel_tlv_header *hdr, + struct babel_parse_state *state) +{ + struct babel_tlv_route_request *tlv = (struct babel_tlv_route_request *)hdr; + struct babel_iface *bif = state->bif; + struct babel_proto *p = state->proto; + ip_addr prefix = babel_get_addr(hdr, state); + struct babel_entry *e; + + TRACE(D_PACKETS, "Handling route request for %I/%d on interface %s", + prefix, tlv->plen, bif->ifname); + + /* Wildcard request - full update on the interface */ + if(ipa_equal(prefix,IPA_NONE)) { + state->needs_update = 1; + return 0; + } + /* Non-wildcard request - see if we have an entry for the route. If not, send + a retraction, otherwise send an update. */ + e = babel_find_entry(p, prefix, tlv->plen); + if(!e) { + babel_send_retraction(bif, prefix, tlv->plen); + } else { + state->needs_update = 1; + } + return 0; +} + +static void +expire_seqno_requests(struct babel_seqno_request_cache *c) { + struct babel_seqno_request *n, *nx; + WALK_LIST_DELSAFE(n, nx, c->entries) { + if(n->updated < now-BABEL_SEQNO_REQUEST_EXPIRY) { + rem_node(NODE n); + sl_free(c->slab, n); + } + } +} + +/* Checks the seqno request cache for a matching request and returns failure if + found. Otherwise, a new entry is stored in the cache. */ +static int +cache_seqno_request(struct babel_proto *p, ip_addr prefix, u8 plen, + u64 router_id, u16 seqno) +{ + struct babel_seqno_request_cache *c = p->seqno_cache; + struct babel_seqno_request *r; + WALK_LIST(r, c->entries) { + if(ipa_equal(r->prefix, prefix) && r->plen == plen && + r->router_id == router_id && r->seqno == seqno) + return 0; + } + + /* no entries found */ + r = sl_alloc(c->slab); + r->prefix = prefix; + r->plen = plen; + r->router_id = router_id; + r->seqno = seqno; + r->updated = now; + add_tail(&c->entries, NODE r); + return 1; +} + +void +babel_forward_seqno_request(struct babel_entry *e, + struct babel_tlv_seqno_request *in, + ip_addr sender) +{ + struct babel_proto *p = e->proto; + struct babel_route *r; + struct babel_iface *bif; + struct babel_tlv_seqno_request *out; + TRACE(D_PACKETS, "Forwarding seqno request for %I/%d router_id %0lx", + e->n.prefix, e->n.pxlen, in->router_id); + WALK_LIST(r, e->routes) { + if(r->router_id == in->router_id && r->neigh + && !ipa_equal(r->neigh->addr,sender)) { + if(!cache_seqno_request(p, e->n.prefix, e->n.pxlen, in->router_id, in->seqno)) + return; + bif = r->neigh->bif; + babel_new_unicast(bif); + out = babel_add_tlv_seqno_request(bif); + out->plen = in->plen; + out->seqno = in->seqno; + out->hop_count = in->hop_count-1; + out->router_id = in->router_id; + babel_put_addr(&out->header, e->n.prefix); + babel_send_unicast(bif, r->neigh->addr); + return; + } + } +} + +/* The RFC section 3.8.1.2 on seqno requests: + + When a node receives a seqno request for a given router-id and sequence + number, it checks whether its routing table contains a selected entry for + that prefix; if no such entry exists, or the entry has infinite metric, it + ignores the request. + + If a selected route for the given prefix exists, and either the router-ids + are different or the router-ids are equal and the entry's sequence number is + no smaller than the requested sequence number, it MUST send an update for the + given prefix. + + If the router-ids match but the requested seqno is larger than the route + entry's, the node compares the router-id against its own router-id. If the + router-id is its own, then it increases its sequence number by 1 and sends an + update. A node MUST NOT increase its sequence number by more than 1 in + response to a route request. + + If the requested router-id is not its own, the received request's hop count + is 2 or more, and the node has a route (not necessarily a feasible one) for + the requested prefix that does not use the requestor as a next hop, the node + SHOULD forward the request. It does so by decreasing the hop count and + sending the request in a unicast packet destined to a neighbour that + advertises the given prefix (not necessarily the selected neighbour) and that + is distinct from the neighbour from which the request was received. + + A node SHOULD maintain a list of recently forwarded requests and forward the + reply in a timely manner. A node SHOULD compare every incoming request + against its list of recently forwarded requests and avoid forwarding it if it + is redundant. +*/ +int +babel_handle_seqno_request(struct babel_tlv_header *hdr, + struct babel_parse_state *state) +{ + struct babel_tlv_seqno_request *tlv = (struct babel_tlv_seqno_request *)hdr; + struct babel_proto *p = state->proto; + ip_addr prefix = babel_get_addr(hdr, state); + struct babel_entry *e; + struct babel_route *r; + + TRACE(D_PACKETS, "Handling seqno request for %I/%d router_id %0lx seqno %d hop count %d", + prefix, tlv->plen, tlv->router_id, tlv->seqno, tlv->hop_count); + + e = babel_find_entry(p, prefix, tlv->plen); + if(!e || !e->selected || e->selected->metric == BABEL_INFINITY) return 1; + + r = e->selected; + if(r->router_id != tlv->router_id || ge_mod64k(r->seqno, tlv->seqno)) { + state->needs_update = 1; + return 0; + } + + /* seqno is larger; check if we own the router id */ + if(tlv->router_id == p->router_id) { + p->update_seqno++; + ev_schedule(p->update_event); + return 0; + } + + if(tlv->hop_count > 1) { + babel_forward_seqno_request(e, tlv, state->saddr); + } + + return 1; + +} + +static void +babel_dump_source(struct babel_source *s) +{ + debug("Source router_id %0lx seqno %d metric %d expires %d\n", + s->router_id, s->seqno, s->metric, s->expires ? s->expires-now : 0); +} + +static void +babel_dump_route(struct babel_route *r) +{ + debug("Route neigh %I if %s seqno %d metric %d/%d router_id %0lx expires %d\n", + r->neigh ? r->neigh->addr : IPA_NONE, + r->neigh ? r->neigh->bif->ifname : "(none)", + r->seqno, r->advert_metric, + r->metric, r->router_id, r->expires ? r->expires-now : 0); +} + +static void +babel_dump_entry(struct babel_entry *e) +{ + debug("Babel: Entry %I/%d:\n", e->n.prefix, e->n.pxlen); + struct babel_source *s; struct babel_route *r; + WALK_LIST(s,e->sources) { debug(" "); babel_dump_source(s); } + WALK_LIST(r,e->routes) { debug(r==e->selected?" * " : " "); babel_dump_route(r); } +} + +static void +babel_dump_neighbor(struct babel_neighbor *bn) +{ + debug("Neighbor %I txcost %d hello_map %x next seqno %d expires %d/%d\n", + bn->addr, bn->txcost, bn->hello_map, bn->next_hello_seqno, + bn->hello_expiry ? bn->hello_expiry - now : 0, + bn->ihu_expiry ? bn->ihu_expiry - now : 0); +} + +static void +babel_dump_interface(struct babel_iface *bif) +{ + struct babel_neighbor *bn; + debug("Babel: Interface %s addr %I rxcost %d type %d hello seqno %d intervals %d %d\n", + bif->ifname, bif->addr, bif->cf->rxcost, bif->cf->type, bif->hello_seqno, + bif->cf->hello_interval, bif->cf->update_interval); + WALK_LIST(bn,bif->neigh_list) { debug(" "); babel_dump_neighbor(bn); } + +} + +static void +babel_dump(struct proto *P) +{ + struct babel_proto *p = (struct babel_proto *) P; + struct babel_entry *e; + struct babel_iface *bif; + debug("Babel: router id %0lx update seqno %d\n", p->router_id, p->update_seqno); + WALK_LIST(bif, p->interfaces) {babel_dump_interface(bif);} + FIB_WALK(&p->rtable, n) { + e = (struct babel_entry *)n; + babel_dump_entry(e); + } FIB_WALK_END; +} + + +static struct babel_iface* +babel_find_interface(struct babel_proto *p, struct iface *what) +{ + struct babel_iface *bif; + + WALK_LIST (bif, p->interfaces) + if (bif->iface == what) + return bif; + return NULL; +} + +static void +kill_iface(struct babel_iface *bif) +{ + DBG( "Babel: Interface %s disappeared\n", bif->iface->name); + struct babel_neighbor *bn; + WALK_LIST_FIRST(bn, bif->neigh_list) + babel_flush_neighbor(bn); + rfree(bif->pool); +} + +static void +babel_iface_linkdown(struct babel_iface *bif) +{ + struct babel_neighbor *bn; + struct babel_route *r; + node *n; + WALK_LIST(bn, bif->neigh_list) { + WALK_LIST(n, bn->routes) { + r = SKIP_BACK(struct babel_route, neigh_route, n); + r->metric = BABEL_INFINITY; + r->expires = now + r->expiry_interval; + babel_select_route(r->e); + } + } + +} + + + +static void +babel_open_interface(struct object_lock *lock) +{ + struct babel_iface *bif = lock->data; + struct babel_proto *p = bif->proto; + + if(!babel_open_socket(bif)) { + log(L_ERR "%s: Cannot open socket for %s", p->p.name, bif->iface->name); + } +} + + + +static void +babel_if_notify(struct proto *P, unsigned c, struct iface *iface) +{ + struct babel_proto *p = (struct babel_proto *) P; + struct babel_config *cf = (struct babel_config *) P->cf; + DBG("Babel: if notify: %s flags %x\n", iface->name, iface->flags); + if (iface->flags & IF_IGNORE) + return; + if (c & IF_CHANGE_UP) { + struct iface_patt *k = iface_patt_find(&cf->iface_list, iface, iface->addr); + + /* we only speak multicast */ + if(!(iface->flags & IF_MULTICAST)) return; + + if (!k) return; /* We are not interested in this interface */ + + babel_new_interface(p, iface, iface->flags, k); + + } + struct babel_iface *bif = babel_find_interface(p, iface); + + if(!bif) + return; + + if(!(iface->flags & IF_CHANGE_LINK)) { + TRACE(D_EVENTS, "Interface %s lost link", iface->name); + babel_iface_linkdown(bif); + } + + if (c & IF_CHANGE_DOWN) { + rem_node(NODE bif); + rfree(bif->lock); + kill_iface(bif); + } +} + +void +babel_queue_timer(timer *t) +{ + struct babel_iface *bif = t->data; + if(bif->update_triggered) { + babel_send_update(bif); + bif->update_triggered = 0; + } + ev_schedule(bif->send_event); +} + +static void +babel_new_interface(struct babel_proto *p, struct iface *new, + unsigned long flags, struct iface_patt *patt) +{ + struct babel_config *cf = (struct babel_config *) p->p.cf; + struct babel_iface * bif; + struct babel_iface_config *iface_cf = (struct babel_iface_config *) patt; + struct object_lock *lock; + pool *pool; + DBG("New interface %s\n", new->name); + + if(!new) return NULL; + + pool = rp_new(p->p.pool, new->name); + bif = mb_allocz(pool, sizeof( struct babel_iface )); + add_tail(&p->interfaces, NODE bif); + bif->pool = pool; + bif->iface = new; + bif->ifname = new->name; + bif->proto = p; + struct ifa* ifa; + WALK_LIST(ifa, new->addrs) + if(ipa_is_link_local(ifa->ip)) + bif->addr = ifa->ip; + if (iface_cf) { + bif->cf = iface_cf; + + if(bif->cf->type == BABEL_IFACE_TYPE_WIRED) { + if(bif->cf->hello_interval == BABEL_INFINITY) + bif->cf->hello_interval = BABEL_HELLO_INTERVAL_WIRED; + if(bif->cf->rxcost == BABEL_INFINITY) + bif->cf->rxcost = BABEL_RXCOST_WIRED; + } else if(bif->cf->type == BABEL_IFACE_TYPE_WIRELESS) { + if(bif->cf->hello_interval == BABEL_INFINITY) + bif->cf->hello_interval = BABEL_HELLO_INTERVAL_WIRELESS; + if(bif->cf->rxcost == BABEL_INFINITY) + bif->cf->rxcost = BABEL_RXCOST_WIRELESS; + } + if(bif->cf->update_interval == BABEL_INFINITY) { + bif->cf->update_interval = bif->cf->hello_interval*BABEL_UPDATE_INTERVAL_FACTOR; + } + bif->cf->ihu_interval = bif->cf->hello_interval*BABEL_IHU_INTERVAL_FACTOR; + } + init_list(&bif->neigh_list); + bif->hello_seqno = 1; + bif->max_pkt_len = new->mtu - BABEL_OVERHEAD; + + bif->hello_timer = tm_new_set(bif->pool, babel_hello_timer, bif, 0, bif->cf->hello_interval); + bif->update_timer = tm_new_set(bif->pool, babel_update_timer, bif, 0, bif->cf->update_interval); + bif->packet_timer = tm_new_set(bif->pool, babel_queue_timer, bif, BABEL_MAX_SEND_INTERVAL, 1); + + + bif->tlv_buf = bif->current_buf = mb_alloc(bif->pool, new->mtu); + babel_init_packet(bif->tlv_buf); + bif->send_event = ev_new(bif->pool); + bif->send_event->hook = babel_send_queue; + bif->send_event->data = bif; + + lock = olock_new( bif->pool ); + lock->addr = IP6_BABEL_ROUTERS; + lock->port = cf->port; + lock->iface = bif->iface; + lock->hook = babel_open_interface; + lock->data = bif; + lock->type = OBJLOCK_UDP; + olock_acquire(lock); +} + + +static struct ea_list * +babel_gen_attrs(struct linpool *pool, int metric, u64 router_id) +{ + struct ea_list *l = lp_alloc(pool, sizeof(struct ea_list) + 2*sizeof(eattr)); + struct adata *rid = lp_alloc(pool, sizeof(struct adata) + sizeof(u64)); + rid->length = sizeof(u64); + memcpy(&rid->data, &router_id, sizeof(u64)); + + l->next = NULL; + l->flags = EALF_SORTED; + l->count = 2; + l->attrs[0].id = EA_BABEL_METRIC; + l->attrs[0].flags = 0; + l->attrs[0].type = EAF_TYPE_INT | EAF_TEMP; + l->attrs[0].u.data = metric; + l->attrs[1].id = EA_BABEL_ROUTER_ID; + l->attrs[1].flags = 0; + l->attrs[1].type = EAF_TYPE_OPAQUE | EAF_TEMP; + l->attrs[1].u.ptr = rid; + return l; +} + +static void +babel_timer(timer *t) +{ + struct babel_proto *p = t->data; + babel_expire_routes(p); + expire_seqno_requests(p->seqno_cache); + babel_expire_neighbors(p); +} + + +static int +babel_import_control(struct proto *P, struct rte **rt, struct ea_list **attrs, struct linpool *pool) +{ + struct babel_proto *p = (struct babel_proto *)P; + + if ((*rt)->attrs->source != RTS_BABEL) { + struct ea_list *new = babel_gen_attrs(pool, 1, p->router_id); + new->next = *attrs; + *attrs = new; + } + return 0; +} + +static struct ea_list * +babel_make_tmp_attrs(struct rte *rt, struct linpool *pool) +{ + return babel_gen_attrs(pool, rt->u.babel.metric, rt->u.babel.router_id); +} + +static void +babel_store_tmp_attrs(struct rte *rt, struct ea_list *attrs) +{ + eattr *rid = ea_find(attrs, EA_BABEL_ROUTER_ID); + rt->u.babel.router_id = rid ? *((u64*) rid->u.ptr->data) : 0; + rt->u.babel.metric = ea_get_int(attrs, EA_BABEL_METRIC, 0); +} + +/* + * babel_rt_notify - core tells us about new route (possibly our + * own), so store it into our data structures. + */ +static void +babel_rt_notify(struct proto *P, struct rtable *table UNUSED, struct network *net, + struct rte *new, struct rte *old, struct ea_list *attrs) +{ + struct babel_proto *p = (struct babel_proto *)P; + struct babel_entry *e; + struct babel_route *r; + + TRACE(D_EVENTS, "Got route from nest: %I/%d", net->n.prefix, net->n.pxlen); + if(new) { + e = babel_get_entry(p, net->n.prefix, net->n.pxlen); + r = (e->selected) ? e->selected : babel_get_route(e, NULL); + + if(!r->neigh) { + r->seqno = p->update_seqno; + r->router_id = p->router_id; + r->metric = 0; + e->selected = r; + } + } else if(old) { + /* route has gone away; send retraction */ + e = babel_find_entry(p, net->n.prefix, net->n.pxlen); + if(e && e->selected && !e->selected->neigh) { + /* no neighbour, so our route */ + e->selected->metric = BABEL_INFINITY; + e->selected->expires = now + BABEL_HOLD_TIME; + babel_select_route(e); + } + } else { + return; + } + ev_schedule(p->update_event); +} + +static void babel_neigh_notify(neighbor *n) +{ + struct babel_proto *p = (struct babel_proto *)n->proto; + struct babel_neighbor *bn = n->data; + DBG("Neighbor: bn %d scope %d flags %d\n", bn, n->scope, n->flags); + if(n->scope <= 0) { + TRACE(D_EVENTS, "Babel: Neighbor lost"); + } else { + TRACE(D_EVENTS, "Babel: Neighbor ready"); + } +} + +static int +babel_rte_same(struct rte *new, struct rte *old) +{ + return ((new->u.babel.router_id == old->u.babel.router_id) && + (new->u.babel.metric == old->u.babel.metric)); +} + + +static int +babel_rte_better(struct rte *new, struct rte *old) +{ + return new->u.babel.metric < old->u.babel.metric; +} + + +static struct proto * +babel_init(struct proto_config *cfg) +{ + struct proto *p = proto_new(cfg, sizeof(struct babel_proto)); + + p->accept_ra_types = RA_OPTIMAL; + p->if_notify = babel_if_notify; + p->rt_notify = babel_rt_notify; + p->neigh_notify = babel_neigh_notify; + p->import_control = babel_import_control; + p->make_tmp_attrs = babel_make_tmp_attrs; + p->store_tmp_attrs = babel_store_tmp_attrs; + p->rte_better = babel_rte_better; + p->rte_same = babel_rte_same; + + return p; +} + +void +babel_init_config(struct babel_config *c) +{ + init_list(&c->iface_list); + c->port = BABEL_PORT; +} + +static void +babel_get_route_info(rte *rte, byte *buf, ea_list *attrs) +{ + buf += bsprintf(buf, " (%d/%0lx)", rte->u.babel.metric, rte->u.babel.router_id); +} + +static int +babel_get_attr(eattr *a, byte *buf, int buflen UNUSED) +{ + switch (a->id) { + case EA_BABEL_METRIC: bsprintf( buf, "metric: %d", a->u.data ); return GA_FULL; + default: return GA_UNKNOWN; + } +} + +static int +babel_reconfigure(struct proto *p, struct proto_config *c) +{ + return 0; +} + +static void +babel_copy_config(struct proto_config *dest, struct proto_config *src) +{ + struct babel_config *b = (struct babel_config *) dest; + /* Shallow copy of everything */ + proto_copy_rest(dest, src, sizeof(struct babel_config)); + + /* We clean up iface_list, ifaces are non-sharable */ + init_list(&b->iface_list); +} + +static int +babel_start(struct proto *P) +{ + struct babel_proto *p = (struct babel_proto *) P; + struct babel_config *cf = (struct babel_config *) P->cf; + DBG( "Babel: starting instance...\n" ); + fib_init( &p->rtable, P->pool, sizeof( struct babel_entry ), 0, babel_init_entry ); + init_list( &p->interfaces ); + init_list( &p->garbage ); + p->timer = tm_new_set(P->pool, babel_timer, p, 0, 1); + tm_start( p->timer, 2 ); + p->update_seqno = 1; + p->router_id = proto_get_router_id(&cf->c); + p->update_event = ev_new(P->pool); + p->update_event->hook = babel_global_update; + p->update_event->data = p; + + p->entry_slab = sl_new(P->pool, sizeof(struct babel_entry)); + p->route_slab = sl_new(P->pool, sizeof(struct babel_route)); + p->source_slab = sl_new(P->pool, sizeof(struct babel_source)); + + p->seqno_cache = mb_allocz(P->pool, sizeof(struct babel_seqno_request_cache)); + p->seqno_cache->slab = sl_new(P->pool, sizeof(struct babel_seqno_request)); + init_list(&p->seqno_cache->entries); + DBG( "Babel: ...done\n"); + return PS_UP; +} + + + +struct protocol proto_babel = { + .name = "Babel", + .template = "babel%d", + .attr_class = EAP_BABEL, + .preference = DEF_PREF_BABEL, + .config_size = sizeof(struct babel_config), + .init = babel_init, + .dump = babel_dump, + .start = babel_start, + .reconfigure = babel_reconfigure, + .copy_config = babel_copy_config, + .get_route_info = babel_get_route_info, + .get_attr = babel_get_attr +}; diff --git a/proto/babel/babel.h b/proto/babel/babel.h new file mode 100644 index 0000000..d8cbeaa --- /dev/null +++ b/proto/babel/babel.h @@ -0,0 +1,434 @@ +/* -*- c-file-style: "gnu"; indent-tabs-mode: nil; -*- + * + * The Babel protocol + * + * Copyright (c) 2015 Toke Høiland-Jørgensen + * + * Can be freely distributed and used under the terms of the GNU GPL. + * + * This file contains the data structures used by Babel. + */ + +#include "nest/bird.h" +#include "nest/iface.h" +#include "nest/route.h" +#include "nest/protocol.h" +#include "nest/locks.h" +#include "lib/resource.h" +#include "lib/lists.h" +#include "lib/socket.h" +#include "lib/string.h" +#include "lib/timer.h" + +#ifndef IPV6 +#error "The Babel protocol only speaks IPv6" +#endif + +#define EA_BABEL_METRIC EA_CODE(EAP_BABEL, 0) +#define EA_BABEL_ROUTER_ID EA_CODE(EAP_BABEL, 1) + +#define BABEL_MAGIC 42 +#define BABEL_VERSION 2 +#define BABEL_PORT 6696 +#define BABEL_INFINITY 0xFFFF + + /* default hello intervals in seconds */ +#define BABEL_HELLO_INTERVAL_WIRED 20 +#define BABEL_HELLO_INTERVAL_WIRELESS 4 +#define BABEL_UPDATE_INTERVAL_FACTOR 4 +#define BABEL_IHU_INTERVAL_FACTOR 3 +#define BABEL_HELLO_EXPIRY_FACTOR 1.5 +#define BABEL_ROUTE_EXPIRY_FACTOR 3.5 +#define BABEL_ROUTE_REFRESH_INTERVAL 2 /* seconds before route expiry to send route request */ +#define BABEL_HOLD_TIME 10 /* expiry time for our own routes */ +#define BABEL_RXCOST_WIRED 96 +#define BABEL_RXCOST_WIRELESS 256 +#define BABEL_INITIAL_HOP_COUNT 255 +#define BABEL_MAX_SEND_INTERVAL 5 + +#define BABEL_SEQNO_REQUEST_EXPIRY 60 +#define BABEL_GARBAGE_INTERVAL 300 + +/* ip header + udp header + babel header */ +#define BABEL_OVERHEAD (SIZE_OF_IP_HEADER+8+sizeof(struct babel_header)) + +struct babel_header { + u8 magic; + u8 version; + u16 length; +}; + +enum babel_tlv_type_t { + BABEL_TYPE_PAD0 = 0, + BABEL_TYPE_PADN = 1, + BABEL_TYPE_ACK_REQ = 2, + BABEL_TYPE_ACK = 3, + BABEL_TYPE_HELLO = 4, + BABEL_TYPE_IHU = 5, + BABEL_TYPE_ROUTER_ID = 6, + BABEL_TYPE_NEXT_HOP = 7, + BABEL_TYPE_UPDATE = 8, + BABEL_TYPE_ROUTE_REQUEST = 9, + BABEL_TYPE_SEQNO_REQUEST = 10, + /* extensions - not implemented + BABEL_TYPE_TS_PC = 11, + BABEL_TYPE_HMAC = 12, + BABEL_TYPE_SS_UPDATE = 13, + BABEL_TYPE_SS_REQUEST = 14, + BABEL_TYPE_SS_SEQNO_REQUEST = 15, + */ + BABEL_TYPE_MAX +}; + +enum babel_iface_type_t { + BABEL_IFACE_TYPE_WIRED, + BABEL_IFACE_TYPE_WIRELESS, + BABEL_IFACE_TYPE_MAX +}; + +enum babel_ae_type_t { + BABEL_AE_WILDCARD = 0, + BABEL_AE_IP4 = 1, + BABEL_AE_IP6 = 2, + BABEL_AE_IP6_LL = 3, + BABEL_AE_MAX +}; + + +struct babel_parse_state { + struct babel_proto *proto; + struct babel_iface *bif; + ip_addr saddr; + u64 router_id; + ip_addr prefix; + ip_addr next_hop; + u8 needs_update; +}; + + + + +struct babel_tlv_header { + u8 type; + u8 length; +}; + +struct babel_tlv_ack_req { + struct babel_tlv_header header; + u16 reserved; + u16 nonce; + u16 interval; +}; + +void babel_hton_ack_req(struct babel_tlv_header *tlv); +void babel_ntoh_ack_req(struct babel_tlv_header *tlv); + +struct babel_tlv_ack { + struct babel_tlv_header header; + u16 nonce; +}; + +struct babel_tlv_hello { + struct babel_tlv_header header; + u16 reserved; + u16 seqno; + u16 interval; +}; + +void babel_hton_hello(struct babel_tlv_header *tlv); +void babel_ntoh_hello(struct babel_tlv_header *tlv); + + +struct babel_tlv_ihu { + struct babel_tlv_header header; + u8 ae; + u8 reserved; + u16 rxcost; + u16 interval; + u32 addr[2]; +}; +void babel_hton_ihu(struct babel_tlv_header *tlv); +void babel_ntoh_ihu(struct babel_tlv_header *tlv); +ip_addr babel_get_addr_ihu(struct babel_tlv_header *tlv, struct babel_parse_state *state); +void babel_put_addr_ihu(struct babel_tlv_header *tlv, ip_addr addr); + + +struct babel_tlv_router_id { + struct babel_tlv_header header; + u16 reserved; + u64 router_id __attribute__((packed)); +}; +void babel_hton_router_id(struct babel_tlv_header *tlv); +void babel_ntoh_router_id(struct babel_tlv_header *tlv); + +struct babel_tlv_next_hop { + struct babel_tlv_header header; + u8 ae; + u8 reserved; + u32 addr[2]; +}; +ip_addr babel_get_addr_next_hop(struct babel_tlv_header *tlv, struct babel_parse_state *state); +void babel_put_addr_next_hop(struct babel_tlv_header *tlv, ip_addr addr); + +struct babel_tlv_update { + struct babel_tlv_header header; + u8 ae; +#define BABEL_FLAG_DEF_PREFIX 0x80 +#define BABEL_FLAG_ROUTER_ID 0x40 + u8 flags; + u8 plen; + u8 omitted; + u16 interval; + u16 seqno; + u16 metric; + u32 addr[4]; +}; +void babel_hton_update(struct babel_tlv_header *tlv); +void babel_ntoh_update(struct babel_tlv_header *tlv); +ip_addr babel_get_addr_update(struct babel_tlv_header *tlv, struct babel_parse_state *state); +void babel_put_addr_update(struct babel_tlv_header *tlv, ip_addr addr); + +struct babel_tlv_route_request { + struct babel_tlv_header header; + u8 ae; + u8 plen; + u32 addr[4]; +}; +/* works for both types of request */ +ip_addr babel_get_addr_request(struct babel_tlv_header *tlv, + struct babel_parse_state *state); +void babel_put_addr_request(struct babel_tlv_header *tlv, ip_addr addr); + +struct babel_tlv_seqno_request { + struct babel_tlv_header header; + u8 ae; + u8 plen; + u16 seqno; + u8 hop_count; + u8 reserved; + u64 router_id __attribute__((packed)); + u32 addr[4]; +}; +void babel_hton_seqno_request(struct babel_tlv_header *tlv); +void babel_ntoh_seqno_request(struct babel_tlv_header *tlv); + + +/* Handlers */ + +int babel_validate_length(struct babel_tlv_header *tlv, struct babel_parse_state *state); +int babel_handle_ack_req(struct babel_tlv_header *tlv, struct babel_parse_state *state); +int babel_handle_ack(struct babel_tlv_header *tlv, struct babel_parse_state *state); +int babel_handle_hello(struct babel_tlv_header *tlv, struct babel_parse_state *state); +int babel_handle_ihu(struct babel_tlv_header *tlv, struct babel_parse_state *state); +int babel_validate_ihu(struct babel_tlv_header *hdr, struct babel_parse_state *state); +int babel_handle_router_id(struct babel_tlv_header *tlv, struct babel_parse_state *state); +int babel_handle_next_hop(struct babel_tlv_header *tlv, struct babel_parse_state *state); +int babel_validate_next_hop(struct babel_tlv_header *hdr, struct babel_parse_state *state); +int babel_handle_update(struct babel_tlv_header *tlv, struct babel_parse_state *state); +int babel_validate_update(struct babel_tlv_header *hdr, struct babel_parse_state *state); +int babel_handle_route_request(struct babel_tlv_header *tlv, + struct babel_parse_state *state); +int babel_validate_request(struct babel_tlv_header *hdr, struct babel_parse_state *state); +int babel_handle_seqno_request(struct babel_tlv_header *tlv, + struct babel_parse_state *state); + +/* Stores forwarded seqno requests for duplicate suppression. */ +struct babel_seqno_request { + node n; + ip_addr prefix; + u8 plen; + u64 router_id; + u16 seqno; + bird_clock_t updated; +}; + +struct babel_seqno_request_cache { + slab *slab; + list entries; /* Seqno requests in the cache (struct babel_seqno_request) */ +}; + + +struct babel_iface { + node n; + + struct babel_proto *proto; + struct iface *iface; + struct object_lock *lock; + + struct babel_iface_config *cf; + + pool *pool; + char *ifname; + sock *sock; + ip_addr addr; + int max_pkt_len; + list neigh_list; /* List of neighbors seen on this iface (struct babel_neighbor) */ + + void *tlv_buf; + void *current_buf; + int update_triggered; + + u16 hello_seqno; /* To be increased on each hello */ + + timer *hello_timer; + timer *update_timer; + timer *packet_timer; + event *send_event; + +}; + +struct babel_iface_config { + struct iface_patt i; + + u16 rxcost; + int type; + int tx_tos; + int tx_priority; + u16 hello_interval; + u16 ihu_interval; + u16 update_interval; +}; + +struct babel_neighbor { + node n; + struct babel_iface *bif; + + ip_addr addr; + u16 txcost; + u8 hello_n; + u16 hello_map; + u16 next_hello_seqno; + /* expiry timers */ + bird_clock_t hello_expiry; + bird_clock_t ihu_expiry; + + list routes; /* Routes this neighbour has sent us (struct babel_route) */ +}; + +struct babel_entry; + +struct babel_source { + node n; + struct babel_entry *e; + + u64 router_id; + u16 seqno; + u16 metric; + bird_clock_t expires; +}; + +struct babel_route { + node n; + node neigh_route; + struct babel_entry *e; + struct babel_neighbor *neigh; + + u16 seqno; + u16 advert_metric; + u16 metric; + u64 router_id; + ip_addr next_hop; + bird_clock_t refresh_time; + bird_clock_t expires; + u16 expiry_interval; +}; + + +struct babel_entry { + struct fib_node n; + node garbage_node; + struct babel_proto *proto; + struct babel_route *selected; + + list sources; /* Source table entries for this prefix (struct babel_source). */ + list routes; /* Routes for this prefix (struct babel_route). */ +}; + + + +struct babel_config { + struct proto_config c; + + list iface_list; /* Patterns configured -- keep it first; see babel_reconfigure why */ + int port; +}; + +struct babel_proto { + struct proto p; + timer *timer; + struct fib rtable; + list garbage; /* Entries to be garbage collected (struct babel_entry) */ + list interfaces; /* Interfaces we really know about (struct babel_iface) */ + u16 update_seqno; /* To be increased on request */ + u64 router_id; + event *update_event; /* For triggering global updates */ + + slab *entry_slab; + slab *route_slab; + slab *source_slab; + + struct babel_seqno_request_cache *seqno_cache; +}; + + + +void babel_init_config(struct babel_config *c); + +/* Packet mangling code - packet.c */ +void babel_send_hello(struct babel_iface *bif, u8 send_ihu); +void babel_send_unicast( struct babel_iface *bif, ip_addr dest ); +void babel_send_queue(void *arg); +void babel_send_update(struct babel_iface *bif); +void babel_init_packet(void *buf); +int babel_open_socket(struct babel_iface *bif); +int babel_process_packet(struct babel_header *pkt, int size, + ip_addr saddr, int port, struct babel_iface *bif); +ip_addr babel_get_addr(struct babel_tlv_header *hdr, struct babel_parse_state *state); +void babel_put_addr(struct babel_tlv_header *hdr, ip_addr addr); +void babel_new_unicast(struct babel_iface *bif); +struct babel_tlv_header * babel_add_tlv_size(struct babel_iface *bif, u16 type, int size); +struct babel_tlv_header * babel_add_tlv(struct babel_iface *bif, u16 len); +#define BABEL_ADD_TLV_SEND(tlv,bif,func,addr) do { \ + tlv=func(bif); \ + if(!tlv) { \ + babel_send_to(bif,addr); \ + babel_new_packet(bif); \ + tlv=func(bif); \ + }} while (0); + +inline struct babel_tlv_ack_req * babel_add_tlv_ack_req(struct babel_iface *bif) +{ + return (struct babel_tlv_ack_req *) babel_add_tlv(bif, BABEL_TYPE_ACK_REQ); +} +inline struct babel_tlv_ack * babel_add_tlv_ack(struct babel_iface *bif) +{ + return (struct babel_tlv_ack *) babel_add_tlv(bif, BABEL_TYPE_ACK); +} +inline struct babel_tlv_hello * babel_add_tlv_hello(struct babel_iface *bif) +{ + return (struct babel_tlv_hello *) babel_add_tlv(bif, BABEL_TYPE_HELLO); +} +inline struct babel_tlv_ihu * babel_add_tlv_ihu(struct babel_iface *bif) +{ + return (struct babel_tlv_ihu *) babel_add_tlv(bif, BABEL_TYPE_IHU); +} +inline struct babel_tlv_router_id * babel_add_tlv_router_id(struct babel_iface *bif) +{ + return (struct babel_tlv_router_id *) babel_add_tlv(bif, BABEL_TYPE_ROUTER_ID); +} +inline struct babel_tlv_next_hop * babel_add_tlv_next_hop(struct babel_iface *bif) +{ + return (struct babel_tlv_next_hop *) babel_add_tlv(bif, BABEL_TYPE_NEXT_HOP); +} +inline struct babel_tlv_update * babel_add_tlv_update(struct babel_iface *bif) +{ + return (struct babel_tlv_update *) babel_add_tlv(bif, BABEL_TYPE_UPDATE); +} +inline struct babel_tlv_route_request * babel_add_tlv_route_request(struct babel_iface *bif) +{ + return (struct babel_tlv_route_request *) babel_add_tlv(bif, BABEL_TYPE_ROUTE_REQUEST); +} +inline struct babel_tlv_seqno_request * babel_add_tlv_seqno_request(struct babel_iface *bif) +{ + return (struct babel_tlv_seqno_request *) babel_add_tlv(bif, BABEL_TYPE_SEQNO_REQUEST); +} diff --git a/proto/babel/config.Y b/proto/babel/config.Y new file mode 100644 index 0000000..b66705a --- /dev/null +++ b/proto/babel/config.Y @@ -0,0 +1,84 @@ +/* + * BIRD -- Babel Configuration + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + + + +CF_HDR + +#include "proto/babel/babel.h" +#include "nest/iface.h" + +CF_DEFINES + +#define BABEL_CFG ((struct babel_config *) this_proto) +#define BABEL_IFACE_CFG ((struct babel_iface_config *) this_ipatt) + +CF_DECLS + +CF_KEYWORDS(BABEL, METRIC, RXCOST, HELLO_INTERVAL, UPDATE_INTERVAL, PORT, WIRED, +WIRELESS, BABEL_METRIC) + +CF_GRAMMAR + +CF_ADDTO(proto, babel_cfg '}' { } ) + +babel_cfg_start: proto_start BABEL { + this_proto = proto_config_new(&proto_babel, $1); + babel_init_config(BABEL_CFG); + } + ; + +babel_cfg: + babel_cfg_start proto_name '{' + | babel_cfg proto_item ';' + | babel_cfg PORT expr ';' { BABEL_CFG->port = $3; } + | babel_cfg INTERFACE babel_iface ';' + ; + + +babel_iface_item: + | RXCOST expr { BABEL_IFACE_CFG->rxcost = $2; } + | TX tos { BABEL_IFACE_CFG->tx_tos = $2; } + | TX PRIORITY expr { BABEL_IFACE_CFG->tx_priority = $3; } + | TYPE WIRED { BABEL_IFACE_CFG->type = BABEL_IFACE_TYPE_WIRED; } + | TYPE WIRELESS { BABEL_IFACE_CFG->type = BABEL_IFACE_TYPE_WIRELESS; } + | HELLO_INTERVAL expr { BABEL_IFACE_CFG->hello_interval = $2; } + | UPDATE_INTERVAL expr { BABEL_IFACE_CFG->update_interval = $2; } + ; + +babel_iface_opts: + /* empty */ + | babel_iface_opts babel_iface_item ';' + ; + +babel_iface_opt_list: + /* empty */ + | '{' babel_iface_opts '}' + ; + +babel_iface_init: + /* EMPTY */ { + this_ipatt = cfg_allocz(sizeof(struct babel_iface_config)); + add_tail(&BABEL_CFG->iface_list, NODE this_ipatt); + init_list(&this_ipatt->ipn_list); + BABEL_IFACE_CFG->rxcost = BABEL_INFINITY; + BABEL_IFACE_CFG->type = BABEL_IFACE_TYPE_WIRED; + BABEL_IFACE_CFG->tx_tos = IP_PREC_INTERNET_CONTROL; + BABEL_IFACE_CFG->tx_priority = sk_priority_control; + BABEL_IFACE_CFG->hello_interval = BABEL_INFINITY; + BABEL_IFACE_CFG->update_interval = BABEL_INFINITY; + } + ; + +babel_iface: /* TODO: switch to iface_patt_list_nopx */ + babel_iface_init iface_patt_list babel_iface_opt_list + ; + +CF_ADDTO(dynamic_attr, BABEL_METRIC { $$ = f_new_dynamic_attr(EAF_TYPE_INT | EAF_TEMP, T_INT, EA_BABEL_METRIC); }) + +CF_CODE + +CF_END diff --git a/proto/babel/packet.c b/proto/babel/packet.c new file mode 100644 index 0000000..54f256b --- /dev/null +++ b/proto/babel/packet.c @@ -0,0 +1,636 @@ +/** -*- c-file-style: "gnu"; indent-tabs-mode: nil; -*- + * + * The Babel protocol + * + * Copyright (c) 2015 Toke Høiland-Jørgensen + * + * Can be freely distributed and used under the terms of the GNU GPL. + * + * This files contains the packet and TLV handling routines for the protocol. + */ + +#undef LOCAL_DEBUG +#define LOCAL_DEBUG 1 + +#include "babel.h" + +#undef TRACE +#define TRACE(level, msg, args...) do { if (p->p.debug & level) { log(L_TRACE "%s: " msg, p->p.name , ## args); } } while(0) +#define BAD( x ) { log( L_REMOTE "%s: " x, p->p.name ); return 1; } + +#define FIRST_TLV(p) ((struct babel_tlv_header *)(((struct babel_header *) p) + 1)) +#define NEXT_TLV(t) (t = (void *)((char *)t) + TLV_SIZE(t)) +#define TLV_SIZE(t) (t->type == BABEL_TYPE_PAD0 ? 1 : t->length + sizeof(struct babel_tlv_header)) +#define TLV_LENGTH(t) (tlv_data[t].struct_length-sizeof(struct babel_tlv_header)) + +static void babel_send_to(struct babel_iface *bif, ip_addr dest); + +static inline ip_addr +get_ip6_ll(u32 *addr) +{ + return ip6_or(ipa_build6(0xfe800000,0,0,0), + ipa_build6(0,0,ntohl(addr[0]),ntohl(addr[1]))); +} + + +struct babel_tlv_data { + int struct_length; + int (*handle)(struct babel_tlv_header *tlv, + struct babel_parse_state *state); + int (*validate)(struct babel_tlv_header *tlv, + struct babel_parse_state *state); + void (*hton)(struct babel_tlv_header *tlv); + void (*ntoh)(struct babel_tlv_header *tlv); + ip_addr (*get_addr)(struct babel_tlv_header *tlv, + struct babel_parse_state *state); + void (*put_addr)(struct babel_tlv_header *tlv, ip_addr addr); +}; + +static struct babel_tlv_data tlv_data[BABEL_TYPE_MAX] = { + {1, NULL,NULL,NULL,NULL,NULL}, + {3, NULL,NULL,NULL,NULL,NULL}, + {sizeof(struct babel_tlv_ack_req), + babel_handle_ack_req, babel_validate_length, + babel_hton_ack_req, babel_ntoh_ack_req, + NULL,NULL}, + {sizeof(struct babel_tlv_ack), + babel_handle_ack, babel_validate_length, + NULL, NULL, + NULL, NULL}, + {sizeof(struct babel_tlv_hello), + babel_handle_hello, babel_validate_length, + babel_hton_hello, babel_ntoh_hello, + NULL, NULL}, + {sizeof(struct babel_tlv_ihu), + babel_handle_ihu, babel_validate_ihu, + babel_hton_ihu, babel_ntoh_ihu, + babel_get_addr_ihu, babel_put_addr_ihu}, + {sizeof(struct babel_tlv_router_id), + babel_handle_router_id, babel_validate_length, + babel_hton_router_id, babel_ntoh_router_id, + NULL, NULL}, + {sizeof(struct babel_tlv_next_hop), + babel_handle_next_hop, babel_validate_next_hop, + NULL, NULL, + babel_get_addr_next_hop, NULL}, + {sizeof(struct babel_tlv_update), + babel_handle_update, babel_validate_update, + babel_hton_update, babel_ntoh_update, + babel_get_addr_update, babel_put_addr_update}, + {sizeof(struct babel_tlv_route_request), + babel_handle_route_request, babel_validate_request, + NULL, NULL, + babel_get_addr_request, babel_put_addr_request}, + {sizeof(struct babel_tlv_seqno_request), + babel_handle_seqno_request, babel_validate_request, + babel_hton_seqno_request, babel_ntoh_seqno_request, + babel_get_addr_request, babel_put_addr_request}, +}; + +static inline int +validate_tlv(struct babel_tlv_header *tlv, struct babel_parse_state *state) +{ + return (tlv_data[tlv->type].validate != NULL && tlv_data[tlv->type].validate(tlv, state)); +} + +void +babel_hton_ack_req(struct babel_tlv_header *hdr) +{ + struct babel_tlv_ack_req *tlv = (struct babel_tlv_ack_req *)hdr; + tlv->interval = htons(tlv->interval); +} + +void +babel_ntoh_ack_req(struct babel_tlv_header *hdr) +{ + struct babel_tlv_ack_req *tlv = (struct babel_tlv_ack_req *)hdr; + tlv->interval = ntohs(tlv->interval); +} + +void +babel_hton_hello(struct babel_tlv_header *hdr) +{ + struct babel_tlv_hello *tlv = (struct babel_tlv_hello *)hdr; + tlv->seqno = htons(tlv->seqno); + tlv->interval = htons(tlv->interval); +} + +void +babel_ntoh_hello(struct babel_tlv_header *hdr) +{ + struct babel_tlv_hello *tlv = (struct babel_tlv_hello *)hdr; + tlv->seqno = ntohs(tlv->seqno); + tlv->interval = ntohs(tlv->interval); +} + +int +babel_validate_ihu(struct babel_tlv_header *hdr, struct babel_parse_state *state) +{ + struct babel_tlv_ihu *tlv = (struct babel_tlv_ihu *)hdr; + if(hdr->length < TLV_LENGTH(BABEL_TYPE_IHU)-sizeof(tlv->addr)) return 0; + return (tlv->ae == BABEL_AE_WILDCARD + || (tlv->ae == BABEL_AE_IP6_LL && hdr->length >= TLV_LENGTH(BABEL_TYPE_IHU))); +} + +void +babel_hton_ihu(struct babel_tlv_header *hdr) +{ + struct babel_tlv_ihu *tlv = (struct babel_tlv_ihu *)hdr; + tlv->rxcost = htons(tlv->rxcost); + tlv->interval = htons(tlv->interval); +} + +void +babel_ntoh_ihu(struct babel_tlv_header *hdr) +{ + struct babel_tlv_ihu *tlv = (struct babel_tlv_ihu *)hdr; + tlv->rxcost = ntohs(tlv->rxcost); + tlv->interval = ntohs(tlv->interval); +} + +ip_addr +babel_get_addr_ihu(struct babel_tlv_header *hdr, struct babel_parse_state *state) +{ + struct babel_tlv_ihu *tlv = (struct babel_tlv_ihu *)hdr; + struct babel_iface *bif = state->bif; + if(tlv->ae == BABEL_AE_WILDCARD) { + return bif->iface->addr->ip; /* FIXME: Correct? */ + } else if(tlv->ae == BABEL_AE_IP6_LL) { + return get_ip6_ll(tlv->addr); + } + return IPA_NONE; +} + +void +babel_put_addr_ihu(struct babel_tlv_header *hdr, ip_addr addr) +{ + char buf[16]; + struct babel_tlv_ihu *tlv = (struct babel_tlv_ihu *)hdr; + if(!ipa_is_link_local(addr)) { + tlv->ae = BABEL_AE_WILDCARD; + return; + } + put_ip6(buf,addr); + memcpy(tlv->addr, buf+8, 8); + tlv->ae = BABEL_AE_IP6_LL; +} + +void +babel_hton_router_id(struct babel_tlv_header *hdr) +{ + struct babel_tlv_router_id *tlv = (struct babel_tlv_router_id *)hdr; + tlv->router_id = htobe64(tlv->router_id); +} + +void +babel_ntoh_router_id(struct babel_tlv_header *hdr) +{ + struct babel_tlv_router_id *tlv = (struct babel_tlv_router_id *)hdr; + tlv->router_id = be64toh(tlv->router_id); +} + +int +babel_validate_next_hop(struct babel_tlv_header *hdr, struct babel_parse_state *state) +{ + struct babel_tlv_next_hop *tlv = (struct babel_tlv_next_hop *)hdr; + /* We don't speak IPv4, so only recognise IP6 LL next hops */ + if(tlv->ae != BABEL_AE_IP6_LL) return 0; + return babel_validate_length(hdr, state); +} + +ip_addr +babel_get_addr_next_hop(struct babel_tlv_header *hdr, struct babel_parse_state *state) +{ + struct babel_tlv_next_hop *tlv = (struct babel_tlv_next_hop *)hdr; + return get_ip6_ll(tlv->addr); +} + +int +babel_validate_update(struct babel_tlv_header *hdr, struct babel_parse_state *state) +{ + struct babel_tlv_update *tlv = (struct babel_tlv_update *)hdr; + int min_length = TLV_LENGTH(BABEL_TYPE_UPDATE)-sizeof(tlv->addr); + u8 len = tlv->plen/8; + if(tlv->plen % 8) len++; + + if(tlv->plen > MAX_PREFIX_LENGTH) + return 0; + + if(hdr->length < min_length) return 0; + if(tlv->ae == BABEL_AE_IP4 /* we don't speak IPv4 */ + || tlv->ae >= BABEL_AE_MAX) /* invalid */ + return 0; + /* Can only omit bits if a previous update defined a prefix to take them from */ + if(tlv->omitted && ipa_equal(state->prefix, IPA_NONE)) + return 0; + + /* TLV should be large enough to old the entire prefix */ + if(hdr->length < min_length + len-tlv->omitted) + return 0; + + return 1; +} + +void +babel_hton_update(struct babel_tlv_header *hdr) +{ + struct babel_tlv_update *tlv = (struct babel_tlv_update *)hdr; + tlv->interval = htons(tlv->interval); + tlv->seqno = htons(tlv->seqno); + tlv->metric = htons(tlv->metric); +} + +void +babel_ntoh_update(struct babel_tlv_header *hdr) +{ + struct babel_tlv_update *tlv = (struct babel_tlv_update *)hdr; + tlv->interval = ntohs(tlv->interval); + tlv->seqno = ntohs(tlv->seqno); + tlv->metric = ntohs(tlv->metric); +} + +ip_addr +babel_get_addr_update(struct babel_tlv_header *hdr, struct babel_parse_state *state) +{ + struct babel_tlv_update *tlv = (struct babel_tlv_update *)hdr; + char buf[16] = {0}; + u8 len = tlv->plen/8; + if(tlv->plen % 8) len++; + + /* fixed encodings */ + if(tlv->ae == BABEL_AE_WILDCARD) return IPA_NONE; + if(tlv->ae == BABEL_AE_IP6_LL) return get_ip6_ll(tlv->addr); + + /* if we have omitted bytes, get them from previous prefix */ + if(tlv->omitted) put_ipa(buf, state->prefix); + /* if the prefix is longer than the omitted octets, copy the rest */ + if(tlv->omitted < len) memcpy(buf+tlv->omitted, tlv->addr, len-tlv->omitted); + /* make sure the tail is zeroed */ + if(len < 16) memset(buf+len, 0, 16-len); + return get_ipa(buf); +} + +void babel_put_addr_update(struct babel_tlv_header *hdr, ip_addr addr) +{ + struct babel_tlv_update *tlv = (struct babel_tlv_update *)hdr; + tlv->ae = BABEL_AE_IP6; + put_ipa(&tlv->addr, addr); +} + +int +babel_validate_request(struct babel_tlv_header *hdr, + struct babel_parse_state *state) +{ + /* Validates both seqno and route_request. Works because ae and plen fields + are in the same place. */ + struct babel_tlv_route_request *tlv = (struct babel_tlv_route_request *)hdr; + u8 len = tlv->plen/8; + if(tlv->plen % 8) len++; + + if(tlv->plen > MAX_PREFIX_LENGTH) + return 0; + + /* enough space to hold the prefix */ + if(hdr->length < TLV_LENGTH(hdr->type) - sizeof(tlv->addr) + len) + return 0; + /* wildcard requests must have plen 0 */ + if(tlv->ae == BABEL_AE_WILDCARD && tlv->plen > 0) + return 0; + + /* We don't speak IPv4, and prefixes cannot be link-local addresses. */ + if(tlv->ae != BABEL_AE_IP6 && tlv->ae != BABEL_AE_WILDCARD) + return 0; + + return 1; +} + +ip_addr +babel_get_addr_request(struct babel_tlv_header *hdr, + struct babel_parse_state *state) +{ + struct babel_tlv_route_request *tlv = (struct babel_tlv_route_request *)hdr; + char buf[16] = {0}; + u8 len = tlv->plen/8; + if(tlv->plen % 8) len++; + + /* fixed encoding */ + if(tlv->ae == BABEL_AE_WILDCARD) return IPA_NONE; + if(hdr->type == BABEL_TYPE_SEQNO_REQUEST) + memcpy(buf, ((struct babel_tlv_seqno_request *)tlv)->addr, len); + else + memcpy(buf, tlv->addr, len); + return get_ipa(buf); +} + +void +babel_put_addr_request(struct babel_tlv_header *hdr, ip_addr addr) +{ + struct babel_tlv_route_request *tlv = (struct babel_tlv_route_request *)hdr; + char buf[16] = {0}; + u8 len = tlv->plen/8; + if(tlv->plen % 8) len++; + put_ipa(buf, addr); + memcpy(tlv->addr, buf, len); +} + +void +babel_hton_seqno_request(struct babel_tlv_header *hdr) +{ + struct babel_tlv_seqno_request *tlv = (struct babel_tlv_seqno_request *)hdr; + tlv->seqno = htons(tlv->seqno); + tlv->router_id = htobe64(tlv->router_id); +} + +void +babel_ntoh_seqno_request(struct babel_tlv_header *hdr) +{ + struct babel_tlv_seqno_request *tlv = (struct babel_tlv_seqno_request *)hdr; + tlv->seqno = ntohs(tlv->seqno); + tlv->router_id = be64toh(tlv->router_id); +} + +static void +babel_tlv_hton(struct babel_tlv_header *hdr) +{ + if(tlv_data[hdr->type].hton) { + tlv_data[hdr->type].hton(hdr); + } +} + +static void +babel_tlv_ntoh(struct babel_tlv_header *hdr) +{ + if(tlv_data[hdr->type].ntoh) { + tlv_data[hdr->type].ntoh(hdr); + } +} + +static void +babel_packet_hton(struct babel_header *hdr) +{ + struct babel_tlv_header *tlv = FIRST_TLV(hdr); + int len = hdr->length+sizeof(struct babel_header); + char *p = (char *)hdr; + while((char *)tlv < p+len) { + babel_tlv_hton(tlv); + NEXT_TLV(tlv); + } + hdr->length = htons(hdr->length); +} + +ip_addr +babel_get_addr(struct babel_tlv_header *hdr, struct babel_parse_state *state) +{ + if(tlv_data[hdr->type].get_addr) { + return tlv_data[hdr->type].get_addr(hdr, state); + } + return IPA_NONE; +} + +void +babel_put_addr(struct babel_tlv_header *hdr, ip_addr addr) +{ + if(tlv_data[hdr->type].put_addr) { + tlv_data[hdr->type].put_addr(hdr, addr); + } +} + + +void +babel_init_packet(void *buf) +{ + struct babel_header *hdr = buf; + memset(hdr, 0, sizeof(struct babel_header)); + hdr->magic = BABEL_MAGIC; + hdr->version = BABEL_VERSION; +} + +void +babel_new_unicast(struct babel_iface *bif) +{ + babel_init_packet(bif->sock->tbuf); + bif->current_buf = bif->sock->tbuf; +} + +void +babel_send_unicast(struct babel_iface *bif, ip_addr dest) +{ + babel_send_to(bif, dest); + bif->current_buf = bif->tlv_buf; +} + + +struct babel_tlv_header * +babel_add_tlv_size(struct babel_iface *bif, u16 type, int len) +{ + struct babel_header *hdr = bif->current_buf; + struct babel_tlv_header *tlv; + int pktlen = sizeof(struct babel_header)+hdr->length; + if(pktlen+len > bif->max_pkt_len) { + babel_send_queue(bif); + pktlen = sizeof(struct babel_header)+hdr->length; + } + hdr->length+=len; + tlv = (struct babel_tlv_header *)((char*)hdr+pktlen); + memset(tlv, 0, len); + tlv->type = type; + tlv->length = TLV_LENGTH(type); + return tlv; +} + +struct babel_tlv_header * +babel_add_tlv(struct babel_iface *bif, u16 type) +{ + return babel_add_tlv_size(bif, type, tlv_data[type].struct_length); +} + + +static int +babel_copy_tlv(void *buf, struct babel_tlv_header *src, int max_len) +{ + struct babel_header *dst = buf; + int pktlen = sizeof(struct babel_header)+dst->length; + int len = tlv_data[src->type].struct_length; + if(pktlen+len > max_len) + return 0; + + memcpy((char *)dst + pktlen, src, len); + dst->length += len; + return 1; +} + + +static void +babel_send_to(struct babel_iface *bif, ip_addr dest) +{ + sock *s = bif->sock; + struct babel_header *hdr = (void *) s->tbuf; + int len = hdr->length+sizeof(struct babel_header); + int done; + + babel_packet_hton(hdr); + + DBG( "Sending %d bytes to %I\n", len, dest); + done = sk_send_to(s, len, dest, 0); + if(!done) + log(L_WARN "Babel: TX queue full on %s", bif->ifname); +} + +static void +babel_send(struct babel_iface *bif) +{ + babel_send_to(bif, IP6_BABEL_ROUTERS); +} + +void +babel_send_queue(void *arg) +{ + struct babel_iface *bif = arg; + struct babel_header *dst = (void *)bif->sock->tbuf; + struct babel_header *src = (void *)bif->tlv_buf; + struct babel_tlv_header *hdr; + char *p; + int moved; + if(!src->length) return; + + babel_init_packet(dst); + hdr = FIRST_TLV(bif->tlv_buf); + p = (char *) hdr; + while((char *)hdr < p + src->length && babel_copy_tlv(dst, hdr, bif->max_pkt_len)) { + NEXT_TLV(hdr); + } + moved = (char *)hdr - p; + if(moved && moved < src->length) { + memmove(p, hdr, src->length - moved); + } + src->length -= moved; + babel_send(bif); + + /* re-schedule if we still have data to send */ + if(src->length) + ev_schedule(bif->send_event); +} + + +int +babel_process_packet(struct babel_header *pkt, int size, + ip_addr saddr, int port, struct babel_iface *bif) +{ + struct babel_tlv_header *tlv = FIRST_TLV(pkt); + struct babel_proto *proto = bif->proto; + struct babel_parse_state state = { + .proto = proto, + .bif = bif, + .saddr = saddr, + .prefix = IPA_NONE, + .next_hop = saddr, + }; + char *p = (char *)pkt; + int res = 0; + + pkt->length = ntohs(pkt->length); + if(pkt->magic != BABEL_MAGIC + || pkt->version != BABEL_VERSION + || pkt->length > size - sizeof(struct babel_header)) { + DBG("Invalid packet: magic %d version %d length %d size %d\n", + pkt->magic, pkt->version, pkt->length, size); + return 1; + } + + while((char *)tlv < p+size) { + if(tlv->type > BABEL_TYPE_PADN + && tlv->type < BABEL_TYPE_MAX + && validate_tlv(tlv, &state)) { + babel_tlv_ntoh(tlv); + res &= tlv_data[tlv->type].handle(tlv, &state); + } else { + DBG("Unknown or invalid TLV of type %d\n",tlv->type); + } + NEXT_TLV(tlv); + } + if(state.needs_update) + bif->update_triggered = 1; + return res; +} + +int +babel_validate_length(struct babel_tlv_header *hdr, struct babel_parse_state *state) +{ + /*DBG("Validate type: %d length: %d needed: %d\n", hdr->type, hdr->length, + tlv_data[hdr->type].struct_length - sizeof(struct babel_tlv_header));*/ + return (hdr->length >= tlv_data[hdr->type].struct_length - sizeof(struct babel_tlv_header)); +} + +static void +babel_tx_err( sock *s, int err ) +{ + log( L_ERR ": Unexpected error at Babel transmit: %M", err ); +} + + +static int +babel_rx(sock *s, int size) +{ + struct babel_iface *bif = s->data; + struct babel_proto *p = bif->proto; + if (! bif->iface || s->lifindex != bif->iface->index) + return 1; + + DBG("Babel: incoming packet: %d bytes from %I via %s\n", size, s->faddr, bif->iface->name); + if (size < sizeof(struct babel_header)) BAD( "Too small packet" ); + + if (ipa_equal(bif->iface->addr->ip, s->faddr)) { + DBG("My own packet\n"); + return 1; + } + + if (!ipa_is_link_local(s->faddr)) { BAD("Non-link local sender"); } + + babel_process_packet((struct babel_header *) s->rbuf, size, s->faddr, s->fport, bif ); + return 1; +} + +int +babel_open_socket(struct babel_iface *bif) +{ + struct babel_proto *p = bif->proto; + struct babel_config *cf = (struct babel_config *) p->p.cf; + bif->sock = sk_new( bif->pool ); + bif->sock->type = SK_UDP; + bif->sock->sport = cf->port; + bif->sock->rx_hook = babel_rx; + bif->sock->data = bif; + bif->sock->rbsize = 10240; + bif->sock->iface = bif->iface; + bif->sock->tbuf = mb_alloc( bif->pool, bif->iface->mtu); + bif->sock->err_hook = babel_tx_err; + bif->sock->dport = cf->port; + bif->sock->daddr = IP6_BABEL_ROUTERS; + + bif->sock->tos = bif->cf->tx_tos; + bif->sock->priority = bif->cf->tx_priority; + bif->sock->flags = SKF_LADDR_RX; + if (sk_open( bif->sock) < 0) + goto err; + if (sk_setup_multicast( bif->sock) < 0) + goto err; + if (sk_join_group( bif->sock, bif->sock->daddr) < 0) + goto err; + TRACE(D_EVENTS, "Listening on %s, port %d, mode multicast (%I)", bif->iface->name, cf->port, bif->sock->daddr ); + + tm_start(bif->hello_timer, bif->cf->hello_interval); + tm_start(bif->update_timer, bif->cf->update_interval); + tm_start(bif->packet_timer, 1); + + babel_send_hello(bif,0); + babel_send_queue(bif); + + return 1; + + err: + sk_log_error(bif->sock, p->p.name); + log(L_ERR "%s: Cannot open socket for %s", p->p.name, bif->iface->name); + rfree(bif->sock); + return 0; + +} diff --git a/sysdep/autoconf.h.in b/sysdep/autoconf.h.in index a9e46e2..c73270c 100644 --- a/sysdep/autoconf.h.in +++ b/sysdep/autoconf.h.in @@ -43,6 +43,7 @@ #undef CONFIG_BGP #undef CONFIG_OSPF #undef CONFIG_PIPE +#undef CONFIG_BABEL /* We use multithreading */ #undef USE_PTHREADS -- 2.5.1

2 6