September 2015 - Bird-users

New in BIRD
by Ilias Pallikarakis 23 Aug '16

23 Aug '16

Hi, I recently started trying to learn BIRD. I should also mention I have no previous experience with any other Routing daemon either. I want to configure a bgp monitor for both ipv4 and ipv6. I am running BIRD in a Ubuntu 13.10 VM. I managed to install both bird and bird6 but I have some problems with the configurations. In ipv4 : I created a very simple configuration which I attach. The conf is compiled but in birdc the bgp session is considered idle. I tried to do a tcpdump and found that the router sends a TCP SYN on the VM's bgp port but the VM responds with a RST and never tries to set a BGP session itself. In ipv6 : No matter the configuration (my configuration or the sample coming with bird6 or examples found on the web) the configuration is not compiled giving the following error : BIRD ipv6 doesn't run (bird: /usr/local/etc/bird6.conf, line 1: Router ID must be configured manually on IPv6 routers) Could anyone give me some pointers on what I am doing wrong ? Thank you for your help, Ilias Pallikarakis

5 8

OSPF state inconsistency
by Przemyslaw Frasunek 21 Feb '16

21 Feb '16

Dear all, we are using BIRD 1.4.5 with OSPF on PPPoE access servers running FreeBSD 9.3 and mpd 5.7. In order to achieve fail-over, each access server is listening on the same VLANs. The user connects to access server which first responds with PPPoE PADO. Some of our subscribers need additional IPv4 prefix, which is routed via address assigned from pool. Such route is added by mpd on connect and deleted on disconnect or LCP timeout. Unfortunately, we are experiencing OSPF state inconsistency between access servers, when user quickly disconnects from one node and connects to another. This is such example, which caused routing loop: (on 193.138.118.89) # birdc show route for 46.21.220.80/28 BIRD 1.4.5 ready. 46.21.220.80/28 via 193.138.118.90 on vlan0 [ospf1 13:08:12] * E2 (10/10/10000) [193.138.118.90] (on 193.138.118.90) # birdc show route for 46.21.220.80/28 BIRD 1.4.5 ready. 46.21.220.80/28 via 193.138.118.89 on vlan0 [ospf1 13:12:32] * E2 (10/10/10000) [193.138.118.89] Any ideas, how to fix it? This is our bird.conf: log syslog { remote, error, auth, fatal, bug }; router id 193.138.118.90; protocol kernel { learn; scan time 20; export filter { if proto = "static_bgp" then reject; accept; }; } protocol device { scan time 10; } protocol ospf { preference 10; import filter { accept; }; export filter { if net.ip = 0.0.0.0 then reject; if source = RTS_STATIC then accept; if proto = "kernel1" then accept; if proto = "direct1" then accept; reject; }; area 0 { interface "vlan0" { }; interface "vlan*" { stub; }; interface "carp*" { stub; cost 1000; }; }; } protocol direct { import filter { accept; }; };

2 5

Bird as an MPLS RR
by Evelio VILA 16 Feb '16

16 Feb '16

Hi guys, I'm following the instructions from http://bird.mpls.in/projects/mpls-bird/wiki/Bird_rr but I get a syntax error when adding the table statements. I'm using Bird 1.4.5 for Ubuntu utopic installed from this ppa: deb http://ppa.launchpad.net/cz.nic-labs/bird/ubuntu utopic main deb-src http://ppa.launchpad.net/cz.nic-labs/bird/ubuntu utopic main But it seems that version is not yet compiled for VPNv4 (AFI/SAFI 1/128) capabilities. already checked this link with no luck... https://www.mail-archive.com/bird-users%40atrey.karlin.mff.cuni.cz/msg03141… any ideas? Thanks! Evelio Vila

3 2

segfault with BFD
by Michal Humpula 11 Dec '15

11 Dec '15

Hi, I came across this lovely segfault when using BFD in Bird v1.4.5 and v1.5: (gdb) bt #0 bfd_send_ctl (p=0x5555557cf840, s=0x5555557e2cf8, final=0) at ../../../proto/bfd/packets.c:66 #1 0x000055555556fc86 in timers_fire (loop=loop@entry=0x5555557dfba0) at ../../../proto/bfd/io.c:437 #2 0x000055555556fe24 in birdloop_main (arg=0x5555557dfba0) at ../../../proto/bfd/io.c:759 #3 0x00007ffff7bc4182 in start_thread () from /lib/x86_64-linux-gnu/libpthread.so.0 #4 0x00007ffff78f147d in clone () from /lib/x86_64-linux-gnu/libc.so.6 Any idea if this is fixed in latest master or that it might be result of misconfiguration? Cheers Michal

3 5

Socket error: TCP_MD5SIG: Cannot allocate memory
by Brian Rak 19 Nov '15

19 Nov '15

I have a machine running BIRD 1.4.5, and I'm seeing a lot of these messages when I start it up: 2015-08-24 15:54:26 <ERR> xxxx: Socket error: TCP_MD5SIG: Cannot allocate memory 2015-08-24 15:54:26 <ERR> yyyy: Socket error: TCP_MD5SIG: Cannot allocate memory It also seems like the sessions that report that error do not come up, and show a status of 'Error: Kernel MD5 auth failed'. I'm only trying to configure around 200 BGP sessions here, most of which are advertising a very small number of prefixes. I don't really see any tunable settings here, any suggestions as to how I can correct this?

4 7

[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

BIRD memory usage
by Alexander Frolkin 01 Oct '15

01 Oct '15

Hello, We are running BIRD on a number of servers. It is configured with two BGP peers. We are seeing BIRD using over a gig of memory, and this seems excessive, especially given the number of routes. BIRD 1.5.0 ready. bird> show memory BIRD memory usage Routing tables: 1142 MB Route attributes: 48 kB ROA tables: 192 B Protocols: 45 kB Total: 1142 MB bird> show route count 656 of 656 routes for 333 networks The memory usage goes up slowly, starting from a few MB; this particular instance has been up for 3 days and 2 hours. Is there something we can do to reduce the memory usage? Or could this be a memory leak bug? The config is attached. Let me know if you need any more information. Thanks in advance! Alex

2 4

OSPF: directly attached summarized networks announced with metric 0 when link goes down
by Israel G. Lugo 01 Oct '15

01 Oct '15

Hello, I have a question regarding BIRD's OSPF and summarized networks. Not sure if I'm doing the right thing. I've got access routers running BIRD, configured as ABR between area 0 and their respective user-facing areas. Access networks are VLAN interfaces, e.g. eth0.161. Backbone connection is a separate physical interface (eth1). If the physical access interface (eth0) goes link down for some reason, BIRD changes the VLAN OSPF interfaces (eth0.161) to Loopback state. It stops announcing the directly connected prefixes on the VLAN interfaces, but it keeps announcing a /32 for the interface's IP, with a metric of 0. That in itself isn't the problem. It makes sense, as the IP belongs to the machine. The problem is, if I use the "network" option (to define summary LSAs), the /32 will be summarized to the entire prefix, making it be announced again. What's worse, it is now announced with a metric of 0, which means it will override any redundant routers I might have. Perhaps a simplified example will help explain: protocol ospf campus { tick 1; ecmp yes; area 0.0.0.0 { stub no; interface "eth1" { check link yes; }; # export loopback address into OSPF interface "lo" { stub; }; } area 0.0.161.0 { stub yes; summary yes; interface "eth0.161", "eth0.197" { stub; check link yes; }; networks { # eth0.161 A.B.C.0/24; # eth0.197 D.E.F.0/24; } } Access interfaces are eth0.161 and eth0.197, respectively with IPs A.B.C.253/24 and D.E.F.253/24. These networks are announced as A.B.C.0/24 and D.E.F.0/24, with a default metric of 10. Now, if I physically pull the cable from eth0, the result is that A.B.C.0/24 and D.E.F.0/24 start to be announced with metric 0, effectively sinking all traffic to those networks. [1] If I remove the "networks" option, no summarization is done, and things work: when I remove the cable from eth0, BIRD stops announcing the /24's and starts announcing A.B.C.253/32 and D.E.F.253/32 (with metric 0). I understand that literally, BIRD is doing what I asked it to do: summarize A.B.C.0/24. As long as it has some valid route inside that prefix (in this case the /32), it will announce the whole summarized network, with a metric equal to the largest cost (RFC 2328, 12.4.3). It would seem to me, though, that this case warrants special treatment. The /32 only exists because the interface transited to Loopback state when it lost the link. Perhaps I am looking at this the wrong way. I would like to summarize my networks, since I have several more complex cases where a shorter prefix is subnetted into several longer ones. However, I would also like to not announce dead routes from downed links. I am used to things working like this from other routers (Quagga, for example) [2], but perhaps there is a better way to do it in BIRD? Is there something I should be doing differently? Or could this perhaps be a bug, and not intended behavior? [1] As far as I can ascertain, what's happening is: eth0 goes link DOWN, eth0.161 and eth0.197 go LOWERLAYERDOWN, and BIRD puts them in Loopback state. As such, BIRD starts announcing their IPs as /32 with metric 0. Since it now has a /32 inside the summary network, it will start announcing the entire summary network, with the metric of 0. [2] In the case of Quagga for example, when the physical interface goes link down, all directly attached routes are removed. The /32 loopback addresses are not left behind. Hence, there is nothing to summarize, hence it will not announce the faulty prefix. Regards, -- Israel G. Lugo Núcleo de Redes e Comunicações Direcção de Serviços de Informática Instituto Superior Técnico

3 7

Support for RFC5838
by Ruben Herold 30 Sep '15

30 Sep '15

hi, I haven't found anything in the documentation. So I will ask the list, is there support for RFC5838 (Support of Address Families in OSPFv3) in bird? thx Ruben -- Ruben Herold ruben(a)insecure.pw

2 1

Missing BFD session with OSPFv3 and same link-local addresses.
by Christos Trochalakis 29 Sep '15

29 Sep '15

Hello all, Our issue is reproducible with 2 routers connected with 2 links. Those links are tagged vlans on the same physical interface (so both links share the same macaddress). bird> show ospf neighbors ospf1: Router ID Pri State DTime Interface Router IP B.B.B.B 1 full/other 00:08 vlan3509 fe80::d6ae:52ff:febf:74a6 B.B.B.B 1 full/dr 00:08 vlan106 fe80::d6ae:52ff:febf:74a6 bird> show bfd sessions bfd1: IP address Interface State Since Interval Timeout fe80::d6ae:52ff:febf:74a6 vlan3509 Up 2015-09-23 0.100 0.500 There is only one bfd session instead of two (one for each link). After digging a bit in the source code, it seems that the OSPF protocol calls `bfd_request_session()` which leads to a call to `bfd_add_request()`. `bfd_add_request()` tries to reuse an already established session with **the same destination address** before creating a new one. But B.B.B.B has the same link-local address on both interfaces (they share the same mac) so the second session is never created and the first one is returned. Perhaps a better approach would be to use the (address, iface) pair when trying to reuse a session. thank you, chris

2 1