[PATCH v3 2/2] Add the Babel routing protocol (RFC6126).

This patch set implements the IPv6 subset of RFC6126, but does not implement any of the extensions. It will, however, peacefully coexist with a Babel implementation that does implement extensions (while ignoring the extension TLVs). Signed-off-by: Toke Høiland-Jørgensen <toke@toke.dk> --- .gitignore | 13 + configure.in | 3 + doc/bird.sgml | 93 +++ lib/bitops.h | 3 +- lib/ip.h | 1 + nest/proto.c | 3 + nest/protocol.h | 2 +- nest/route.h | 11 +- proto/Doc | 1 + proto/babel/Doc | 2 + proto/babel/Makefile | 5 + proto/babel/babel.c | 1945 ++++++++++++++++++++++++++++++++++++++++++++++++++ proto/babel/babel.h | 349 +++++++++ proto/babel/config.Y | 129 ++++ proto/babel/packet.c | 871 ++++++++++++++++++++++ proto/babel/packet.h | 127 ++++ sysdep/autoconf.h.in | 1 + 17 files changed, 3556 insertions(+), 3 deletions(-) create mode 100644 .gitignore 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 create mode 100644 proto/babel/packet.h diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..d31792b --- /dev/null +++ b/.gitignore @@ -0,0 +1,13 @@ +doc/*.html +doc/prog.sgml +doc/prog.log +obj/ +autom4te.cache +bird +birdc +birdcl +config.* +configure +cscope.files +patches +Makefile diff --git a/configure.in b/configure.in index b9220a1..16a0b41 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/doc/bird.sgml b/doc/bird.sgml index 5e5aeee..b94d6cc 100644 --- a/doc/bird.sgml +++ b/doc/bird.sgml @@ -1369,6 +1369,99 @@ corresponding protocol sections. <chapt>Protocols +<sect>Babel + +<sect1>Introduction + +<p>The Babel protocol (RFC6126) is a loop-avoiding distance-vector routing +protocol that is robust and efficient both in ordinary wired networks and in +wireless mesh networks. Babel is conceptually very simple in its operation and +"just works" in its default configuration, though some configuration is possible +and in some cases desirable. + +<p>While the Babel protocol is dual stack (i.e. can carry both IPv4 and IPv6 +routes over the same IPv6 transport), Bird presently implements only the IPv6 +subset of the protocol. No Babel extensions are implemented, but the Bird +implementation can coexist with implementations using the extensions (and will +just ignore extension messages). + +<sect1>Configuration + +<p>Babel supports no global configuration options apart from those common to all +other protocols, but supports the following per-interface configuration options: + +<code> +protocol babel [<name>] { + interface <interface pattern> { + type <wired|wireless>; + rxcost <number>; + hello interval <number>; + update interval <number>; + port <number>; + tx class|dscp <number>; + tx priority <number>; + rx buffer <number>; + tx length <number>; + check link <switch>; + }; +} +</code> + +<descrip> + <tag>type wired|wireless </tag> + This option specifies the interface type: Wired or wireless. Wired + interfaces are considered more reliable, and so the default hello + interval is higher, and a neighbour is considered unreachable after only + a small number of "hello" packets are lost. On wireless interfaces, + hello packets are sent more often, and the ETX link quality estimation + technique is used to compute the metrics of routes discovered over this + interface. This technique will gradually degrade the metric of routes + when packets are lost rather than the more binary up/down mechanism of + wired type links. Default: <cf/wired/. + + <tag>rxcost <m/num/</tag> + This specifies the RX cost of the interface. The route metrics will be + computed from this value with a mechanism determined by the interface + <cf/type/. Default: 96 for wired interfaces, 256 for wireless. + + <tag>hello interval <m/num/</tag> + Interval at which periodic "hello" messages are sent on this interface, + in seconds. Default: 4 seconds. + + <tag>update interval <m/num/</tag> + Interval at which periodic (full) updates are sent. Default: 4 times the + hello interval. + + <tag>port <m/number/</tag> + This option selects an UDP port to operate on. The default is to operate + on port 6696 as specified in the Babel RFC. + + <tag>tx class|dscp|priority <m/number/</tag> + These options specify the ToS/DiffServ/Traffic class/Priority of the + outgoing Babel packets. See <ref id="dsc-prio" name="tx class"> common + option for detailed description. + + <tag>rx buffer <m/number/</tag> + This option specifies the size of buffers used for packet processing. + The buffer size should be bigger than maximal size of received packets. + The default value is the interface MTU, and the value will be clamped to a + minimum of 512 bytes + IP packet overhead. + + <tag>tx length <m/number/</tag> + This option specifies the maximum length of generated Babel packets. To + avoid IP fragmentation, it should not exceed the interface MTU value. + The default value is the interface MTU value, and the value will be + clamped to a minimum of 512 bytes + IP packet overhead. + + <tag>check link <m/switch/</tag> + If set, the hardware link state (as reported by OS) is taken into + consideration. When the link disappears (e.g. an ethernet cable is + unplugged), neighbors are immediately considered unreachable and all + routes received from them are withdrawn. It is possible that some + hardware drivers or platforms do not implement this feature. Default: + yes. +</descrip> + <sect><label id="sect-bfd">BFD <sect1>Introduction diff --git a/lib/bitops.h b/lib/bitops.h index c0ad1a7..ab1ae9a 100644 --- a/lib/bitops.h +++ b/lib/bitops.h @@ -25,5 +25,6 @@ u32 u32_log2(u32 v); static inline u32 u32_hash(u32 v) { return v * 2902958171u; } -#endif +static inline u8 u16_popcount(u16 v) { return __builtin_popcount(v); } +#endif diff --git a/lib/ip.h b/lib/ip.h index 5bc44e0..978eb11 100644 --- a/lib/ip.h +++ b/lib/ip.h @@ -26,6 +26,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 d04da33..0ae0ff3 100644 --- a/nest/proto.c +++ b/nest/proto.c @@ -919,6 +919,9 @@ protos_build(void) proto_build(&proto_bfd); bfd_init_all(); #endif +#ifdef CONFIG_BABEL + proto_build(&proto_babel); +#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 c435b9e..918a6e5 100644 --- a/nest/route.h +++ b/nest/route.h @@ -220,6 +220,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 */ @@ -374,6 +380,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 @@ -422,7 +429,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) @@ -547,6 +555,7 @@ extern struct protocol *attr_class_to_protocol[EAP_MAX]; #define DEF_PREF_DIRECT 240 /* Directly connected */ #define DEF_PREF_STATIC 200 /* Static route */ #define DEF_PREF_OSPF 150 /* OSPF intra-area, inter-area and type 1 external routes */ +#define DEF_PREF_BABEL 130 /* Babel */ #define DEF_PREF_RIP 120 /* RIP */ #define DEF_PREF_BGP 100 /* BGP */ #define DEF_PREF_PIPE 70 /* Routes piped from other tables */ 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..8c64baa --- /dev/null +++ b/proto/babel/babel.c @@ -0,0 +1,1945 @@ +/* -*- c-file-style: "gnu"; indent-tabs-mode: nil; -*- + * + * The Babel protocol + * + * Copyright (c) 2015-2016 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 times 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 entry is updated by receiving updates from the network or when modified by + * internal timers. It performs feasibility checks on the available routes for + * the prefix and selects the one with the lowest metric to be announced to the + * core. + */ + +#undef LOCAL_DEBUG +#define LOCAL_DEBUG 1 + +#include <stdlib.h> +#include "babel.h" + + +#define BAD(x) { log(L_REMOTE "%s: " x, p->p.name); return 1; } +#define OUR_ROUTE(r) (r->neigh == NULL) + +/* Is one number larger than another mod 2^16? This is based on the definition + of serial number space in RFC1982. + + The simple comparison works because if b - a > 0x8000 then (since the u16 + values wrap) either b is larger than a by more than 2**15 (which means a > b + in sequence number space), OR a is larger than b by LESS than 2**15 (which + also means that a > b in sequence number space.*/ +static inline u16 ge_mod64k(u16 a, u16 b) +{ + return (a == b || b - a > 0x8000); +} + +static void babel_expire_hello(struct babel_neighbor *n); +static void babel_expire_ihu(struct babel_neighbor *n); +static void babel_expire_sources(struct babel_entry *e); +static void babel_expire_route(struct babel_route *r); +static void babel_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 void babel_send_wildcard_request(struct babel_iface *ifa); +static int babel_cache_seqno_request(struct babel_proto *p, ip_addr prefix, u8 plen, + u64 router_id, u16 seqno); +static void babel_trigger_iface_update(struct babel_iface *ifa); +static void babel_trigger_update(struct babel_proto *p); +static void babel_send_seqno_request(struct babel_entry *e); +static inline void babel_kick_timer(struct babel_proto *p); +static inline void babel_iface_kick_timer(struct babel_iface *ifa); + +/** Functions to maintain data structures **/ + +static void +babel_init_entry(struct fib_node *n) +{ + struct babel_entry *e = (struct babel_entry *)n; + e->proto = NULL; + e->selected_in = NULL; + e->selected_out = NULL; + e->updated = now; + 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 = 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); + 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->seqno = 0; + s->metric = BABEL_INFINITY; + add_tail(&e->sources, NODE s); + return s; +} + +static void +babel_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); + } + } +} + +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("Babel: Flush route %I/%d router_id %lR 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_in == r) r->e->selected_in = NULL; + if (r->e->selected_out == r) r->e->selected_out = NULL; + sl_free(p->route_slab, r); +} + +static void +babel_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 %lR 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 +babel_refresh_route(struct babel_route *r) +{ + if (OUR_ROUTE(r) || r != r->e->selected_in) 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; + struct fib_iterator fit; + FIB_ITERATE_INIT(&fit, &p->rtable); + loop: + FIB_ITERATE_START(&p->rtable, &fit, n) + { + e = (struct babel_entry *)n; + WALK_LIST_DELSAFE(r, rx, e->routes) + { + if (r->refresh_time && r->refresh_time <= now) + { + babel_refresh_route(r); + r->refresh_time = 0; + } + if (r->expires && r->expires <= now) { + /* + * We have to restart the iteration because there may be a cascade of + * synchronous events babel_select_route() -> nest table change -> + * babel_rt_notify() -> p->rtable change, invalidating hidden variables. + */ + FIB_ITERATE_PUT(&fit, n); + babel_expire_route(r); + goto loop; + } + } + babel_expire_sources(e); + if (EMPTY_LIST(e->sources) && EMPTY_LIST(e->routes)) { + FIB_ITERATE_PUT(&fit, n); + babel_flush_entry(e); + goto loop; + } + } + FIB_ITERATE_END(n); +} + +static struct babel_neighbor * +babel_find_neighbor(struct babel_iface *ifa, ip_addr addr) +{ + struct babel_neighbor *n; + WALK_LIST(n, ifa->neigh_list) + if (ipa_equal(n->addr, addr)) + return n; + return NULL; +} + +static struct babel_neighbor * +babel_get_neighbor(struct babel_iface *ifa, ip_addr addr) +{ + struct babel_neighbor *n = babel_find_neighbor(ifa, addr); + if (n) return n; + n = mb_allocz(ifa->pool, sizeof(struct babel_neighbor)); + n->ifa = ifa; + n->addr = addr; + n->txcost = BABEL_INFINITY; + init_list(&n->routes); + add_tail(&ifa->neigh_list, NODE n); + return n; +} + +static void +babel_flush_neighbor(struct babel_neighbor *n) +{ + struct babel_proto *p = n->ifa->proto; + struct babel_route *r; + node *nod; + TRACE(D_EVENTS, "Flushing neighbor %I", n->addr); + rem_node(NODE n); + WALK_LIST_FIRST(nod, n->routes) + { + r = SKIP_BACK(struct babel_route, neigh_route, nod); + babel_flush_route(r); + } + mb_free(n); +} + +static void +babel_expire_neighbors(struct babel_proto *p) +{ + struct babel_iface *ifa; + struct babel_neighbor *n, *bnx; + WALK_LIST(ifa, p->interfaces) + { + WALK_LIST_DELSAFE(n, bnx, ifa->neigh_list) + { + if (n->ihu_expiry && n->ihu_expiry <= now) + babel_expire_ihu(n); + if (n->hello_expiry && n->hello_expiry <= now) + babel_expire_hello(n); + } + } +} + +static void +babel_expire_hello(struct babel_neighbor *n) +{ + n->hello_map <<= 1; + if (n->hello_cnt < 16) n->hello_cnt++; + if (!n->hello_map) + { + babel_flush_neighbor(n); + } +} + +static void +babel_expire_ihu(struct babel_neighbor *n) +{ + n->txcost = BABEL_INFINITY; +} + + +/** Functions to select routes **/ + + +/** + 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 +babel_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 *n) +{ + struct babel_iface *ifa = n->ifa; + u8 cnt, missed; + u16 map=n->hello_map; + + if (!map) return BABEL_INFINITY; + cnt = u16_popcount(map); // number of bits set + missed = n->hello_cnt-cnt; + + if (ifa->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/n->hello_cnt = cnt/n->hello_cnt + Then: rxcost = BABEL_RXCOST_WIRELESS * n->hello_cnt / cnt + */ + if (!cnt) return BABEL_INFINITY; + return BABEL_RXCOST_WIRELESS * n->hello_cnt / cnt; + } + else + { + /* k-out-of-j selection - Appendix 2.1 in the RFC. */ + DBG("Babel: Missed %d hellos from %I\n", missed, n->addr); + /* Link is bad if more than half the expected hellos were lost */ + return (missed > n->hello_cnt/2) ? BABEL_INFINITY : ifa->cf->rxcost; + } +} + + +static u16 +babel_compute_cost(struct babel_neighbor *n) +{ + struct babel_iface *ifa = n->ifa; + u16 rxcost = babel_compute_rxcost(n); + if (rxcost == BABEL_INFINITY) return rxcost; + else if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS) + { + /* ETX - Appendix 2.2 in the RFC */ + return (MAX(n->txcost, BABEL_RXCOST_WIRELESS) * rxcost)/BABEL_RXCOST_WIRELESS; + } + else + { + /* k-out-of-j selection - Appendix 2.1 in the RFC. */ + return n->txcost; + } +} + +/* Simple additive metric - Appendix 3.1 in the RFC */ +static u16 +babel_compute_metric(struct babel_neighbor *n, uint metric) +{ + metric += babel_compute_cost(n); + return MIN(metric, BABEL_INFINITY); +} + + +/** + * babel_announce_rte - announce entry to the core. + * @p: Babel protocol entry. + * @e: Babel entry to select the best route for. + * + * This function announces a Babel entry to the core if it has a selected + * incoming path, and retracts it otherwise. If the selected entry has infinite + * metric, the route is announced as unreachable. + */ +static void +babel_announce_rte(struct babel_proto *p, struct babel_entry *e) +{ + struct babel_route *r = e->selected_in; + if (r) + { + net *n = net_get(p->p.table, e->n.prefix, e->n.pxlen); + 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, + .from = r->neigh->addr, + .iface = r->neigh->ifa->iface, + }; + + if (r->metric < BABEL_INFINITY) + A.gw = r->next_hop; + + rta *a = rta_lookup(&A); + rte *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; + + rte_update(&p->p, n, rte); + } + else + { + /* retraction */ + net *n = net_find(p->p.table, e->n.prefix, e->n.pxlen); + rte_update(&p->p, n, NULL); + } +} + +/** + * babel_select_route: + * @e: Babel entry to select the best route for. + * + * Select the best feasible route for a given prefix among the routes received + * from peers, and propagate it to the nest. This just selects the feasible + * route with the lowest metric. + * + * 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; + struct babel_route *r, *cur = e->selected_in; + + /* try to find the best feasible route */ + WALK_LIST(r, e->routes) + if ((!cur || r->metric < cur->metric) + && !OUR_ROUTE(r) /* prevent propagating our own routes back to core */ + && babel_is_feasible(babel_find_source(e, r->router_id), + r->seqno, r->advert_metric)) + cur = r; + + if (cur && !OUR_ROUTE(cur) && ((!e->selected_in && cur->metric < BABEL_INFINITY) + || (e->selected_in && cur->metric < e->selected_in->metric))) + { + TRACE(D_EVENTS, "Picked new route for prefix %I/%d: router id %lR metric %d", + e->n.prefix, e->n.pxlen, cur->router_id, cur->metric); + + e->selected_in = cur; + e->updated = now; + babel_announce_rte(p, e); + } + 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_in) + { + TRACE(D_EVENTS, "Lost feasible route for prefix %I/%d. Sending seqno request", + e->n.prefix, e->n.pxlen); + e->selected_in->metric = BABEL_INFINITY; + e->updated = now; + + babel_send_seqno_request(e); + babel_announce_rte(p, 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_in = NULL; + e->updated = now; + babel_announce_rte(p, e); + } + } +} + + +/** Functions to send replies **/ + + +static void +babel_send_seqno_request(struct babel_entry *e) +{ + struct babel_proto *p = e->proto; + struct babel_route *r = e->selected_in; + struct babel_source *s = babel_find_source(e, r->router_id); + struct babel_iface *ifa; + union babel_tlv tlv = {}; + + if (s && babel_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 %lR", + e->n.prefix, e->n.pxlen, r->router_id); + + tlv.type = BABEL_TLV_SEQNO_REQUEST; + tlv.seqno_request.plen = e->n.pxlen; + tlv.seqno_request.seqno = s->seqno + 1; + tlv.seqno_request.hop_count = BABEL_INITIAL_HOP_COUNT; + tlv.seqno_request.router_id = r->router_id; + tlv.seqno_request.prefix = e->n.prefix; + + WALK_LIST(ifa, p->interfaces) + { + babel_enqueue(&tlv, ifa); + } + } +} + +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 *ifa = r->neigh->ifa; + union babel_tlv tlv = {}; + if (s && babel_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 %lR", + e->n.prefix, e->n.pxlen, r->router_id); + + tlv.type = BABEL_TLV_SEQNO_REQUEST; + tlv.seqno_request.plen = e->n.pxlen; + tlv.seqno_request.seqno = s->seqno + 1; + tlv.seqno_request.hop_count = BABEL_INITIAL_HOP_COUNT; + tlv.seqno_request.router_id = r->router_id; + tlv.seqno_request.prefix = e->n.prefix; + babel_send_unicast(&tlv, ifa, r->neigh->addr); + } +} + +static void +babel_send_route_request(struct babel_entry *e, struct babel_neighbor *n) +{ + struct babel_iface *ifa = n->ifa; + struct babel_proto *p = e->proto; + union babel_tlv tlv = {}; + TRACE(D_PACKETS, "Sending route request for %I/%d to %I", + e->n.prefix, e->n.pxlen, n->addr); + tlv.type = BABEL_TLV_ROUTE_REQUEST; + tlv.route_request.prefix = e->n.prefix; + tlv.route_request.plen = e->n.pxlen; + babel_send_unicast(&tlv, ifa, n->addr); +} + +static void +babel_send_wildcard_request(struct babel_iface *ifa) +{ + struct babel_proto *p = ifa->proto; + union babel_tlv tlv = {}; + TRACE(D_PACKETS, "Sending wildcard route request on %s", ifa->ifname); + tlv.type = BABEL_TLV_ROUTE_REQUEST; /* 0-initialisation is wildcard */ + babel_enqueue(&tlv, ifa); +} + + +static void +babel_send_ack(struct babel_iface *ifa, ip_addr dest, u16 nonce) +{ + struct babel_proto *p = ifa->proto; + union babel_tlv tlv = {}; + TRACE(D_PACKETS, "Sending ACK to %I with nonce %d", dest, nonce); + tlv.type = BABEL_TLV_ACK; + tlv.ack.nonce = nonce; + babel_send_unicast(&tlv, ifa, dest); +} + +static void +babel_build_ihu(union babel_tlv *tlv, struct babel_iface *ifa, struct babel_neighbor *n) +{ + struct babel_proto *p = ifa->proto; + tlv->type = BABEL_TLV_IHU; + tlv->ihu.addr = n->addr; + tlv->ihu.rxcost = babel_compute_rxcost(n); + tlv->ihu.interval = ifa->cf->ihu_interval; + TRACE(D_PACKETS, "Sending IHU to %I with rxcost %d interval %d", + tlv->ihu.addr, tlv->ihu.rxcost, tlv->ihu.interval); +} + +static void +babel_queue_ihus(struct babel_iface *ifa) +{ + struct babel_neighbor *n; + WALK_LIST(n, ifa->neigh_list) { + union babel_tlv tlv = {}; + babel_build_ihu(&tlv, ifa, n); + babel_enqueue(&tlv, ifa); + } +} + +static void +babel_send_ihu(struct babel_iface *ifa, struct babel_neighbor *n) +{ + struct babel_proto *p = ifa->proto; + TRACE(D_PACKETS, "Sending IHUs"); + union babel_tlv tlv = {}; + babel_build_ihu(&tlv, ifa, n); + babel_send_unicast(&tlv, ifa, n->addr); +} + +void +babel_send_hello(struct babel_iface *ifa, u8 send_ihu) +{ + struct babel_proto *p = ifa->proto; + union babel_tlv tlv = {}; + TRACE(D_PACKETS, "Sending hello on interface %s", ifa->ifname); + tlv.type = BABEL_TLV_HELLO; + tlv.hello.seqno = ifa->hello_seqno++; + tlv.hello.interval = ifa->cf->hello_interval; + babel_enqueue(&tlv, ifa); + + if (send_ihu) babel_queue_ihus(ifa); +} + + +/** + * babel_send_update - send route table updates. + * @ifa: Interface to transmit on. + * @changed: Only send entries changed since this time. + * + * This function produces update TLVs for all entries changed since the time + * indicated by the &changed parameter and queues them for transmission on the + * selected interface. In the process, the feasibility distance for each + * transmitted entry is updated. + */ +void +babel_send_update(struct babel_iface *ifa, bird_clock_t changed) +{ + struct babel_proto *p = ifa->proto; + struct babel_entry *e; + struct babel_route *r; + struct babel_source *s; + FIB_WALK(&p->rtable, n) + { + union babel_tlv tlv = {}; + tlv.type = BABEL_TLV_UPDATE; + e = (struct babel_entry *)n; + r = e->selected_out; + if (!r) continue; + + + /* 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; + e->updated = now; + } + + /* skip routes that weren't updated since 'changed' time */ + if (e->updated < changed) + continue; + + tlv.update.plen = e->n.pxlen; + tlv.update.interval = ifa->cf->update_interval; + tlv.update.seqno = r->seqno; + tlv.update.metric = r->metric; + tlv.update.prefix = e->n.prefix; + tlv.update.router_id = r->router_id; + + /* Update feasibility distance. */ + s = babel_get_source(e, r->router_id); + s->expires = now + BABEL_GARBAGE_INTERVAL; + if (tlv.update.seqno > s->seqno + || (tlv.update.seqno == s->seqno && tlv.update.metric < s->metric)) + { + s->seqno = tlv.update.seqno; + s->metric = tlv.update.metric; + } + babel_enqueue(&tlv, ifa); + } FIB_WALK_END; +} + +static void +babel_trigger_iface_update(struct babel_iface *ifa) +{ + if (ifa->up && !ifa->want_triggered) + { + ifa->want_triggered = now; + babel_iface_kick_timer(ifa); + } +} + +/* Sends and update on all interfaces. */ +static void +babel_trigger_update(struct babel_proto *p) +{ + if (p->triggered) + return; + struct babel_iface *ifa; + TRACE(D_EVENTS, "Sending global update. Seqno %d", p->update_seqno); + + WALK_LIST(ifa, p->interfaces) + babel_trigger_iface_update(ifa); + + p->triggered = 1; +} + +/** TLV handler helpers **/ + + + +/* update hello history according to Appendix A1 of the RFC */ +static void +babel_update_hello_history(struct babel_neighbor *n, u16 seqno, u16 interval) +{ + u16 delta = ((u16) seqno - n->next_hello_seqno); + if (delta == 0) {/* do nothing */} + /* if the expected and seen seqnos are within 16 of each other (mod 2^16), + 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 (delta <= 16) + { + /* sending node decreased interval; fast-forward */ + n->hello_map <<= delta; + n->hello_cnt = MIN(n->hello_cnt + delta, 16); + } + else if (delta >= 0xfff0) + { + u8 diff = (0xffff - delta); + /* sending node increased interval; reverse history */ + n->hello_map >>= diff; + n->hello_cnt = (diff < n->hello_cnt) ? n->hello_cnt - diff : 0; + } + else + { + /* note state reset - flush entries */ + n->hello_map = n->hello_cnt = 0; + } + + /* current entry */ + n->hello_map = (n->hello_map << 1) | 1; + n->next_hello_seqno = seqno+1; + if (n->hello_cnt < 16) n->hello_cnt++; + n->hello_expiry = now + (BABEL_HELLO_EXPIRY_FACTOR*interval); +} + + + +/* A retraction is an update with an infinite metric. */ +static void +babel_send_retraction(struct babel_iface *ifa, ip_addr prefix, int plen) +{ + struct babel_proto *p = ifa->proto; + union babel_tlv tlv = {}; + tlv.type = BABEL_TLV_UPDATE; + tlv.update.plen = plen; + tlv.update.interval = ifa->cf->update_interval; + tlv.update.seqno = p->update_seqno; + tlv.update.metric = BABEL_INFINITY; + tlv.update.prefix = prefix; + tlv.update.router_id = p->router_id; + babel_enqueue(&tlv, ifa); +} + +static void +babel_expire_seqno_requests(struct babel_proto *p) +{ + struct babel_seqno_request *n, *nx; + WALK_LIST_DELSAFE(n, nx, p->seqno_cache) + { + if (n->updated + BABEL_SEQNO_REQUEST_EXPIRY <= now) + { + rem_node(NODE n); + sl_free(p->seqno_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 +babel_cache_seqno_request(struct babel_proto *p, ip_addr prefix, u8 plen, + u64 router_id, u16 seqno) +{ + struct babel_seqno_request *r; + WALK_LIST(r, p->seqno_cache) + { + 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(p->seqno_slab); + r->prefix = prefix; + r->plen = plen; + r->router_id = router_id; + r->seqno = seqno; + r->updated = now; + add_tail(&p->seqno_cache, 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; + TRACE(D_PACKETS, "Forwarding seqno request for %I/%d router_id %lR", + e->n.prefix, e->n.pxlen, in->router_id); + WALK_LIST(r, e->routes) + { + if (r->router_id == in->router_id && !OUR_ROUTE(r) + && !ipa_equal(r->neigh->addr,sender)) + { + if (!babel_cache_seqno_request(p, e->n.prefix, e->n.pxlen, in->router_id, in->seqno)) + return; + union babel_tlv tlv = {}; + tlv.type = BABEL_TLV_SEQNO_REQUEST; + tlv.seqno_request.plen = in->plen; + tlv.seqno_request.seqno = in->seqno; + tlv.seqno_request.hop_count = in->hop_count-1; + tlv.seqno_request.router_id = in->router_id; + tlv.seqno_request.prefix = e->n.prefix; + babel_send_unicast(&tlv, r->neigh->ifa, r->neigh->addr); + return; + } + } +} + + +/** TLV handlers **/ + +void +babel_handle_ack_req(union babel_tlv *inc, struct babel_iface *ifa) +{ + struct babel_proto *p = ifa->proto; + struct babel_tlv_ack_req *tlv = &inc->ack_req; + TRACE(D_PACKETS, "Received ACK req nonce %d interval %d", tlv->nonce, tlv->interval); + if (tlv->interval) + { + babel_send_ack(ifa, tlv->sender, tlv->nonce); + } + } + + +void +babel_handle_hello(union babel_tlv *inc, struct babel_iface *ifa) +{ + struct babel_proto *p = ifa->proto; + struct babel_tlv_hello *tlv = &inc->hello; + struct babel_neighbor *n = babel_get_neighbor(ifa, tlv->sender); + TRACE(D_PACKETS, "Handling hello seqno %d interval %d", tlv->seqno, + tlv->interval, tlv->sender); + babel_update_hello_history(n, tlv->seqno, tlv->interval); + if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS) + babel_send_ihu(ifa, n); +} + +void +babel_handle_ihu(union babel_tlv *inc, struct babel_iface *ifa) +{ + struct babel_tlv_ihu *tlv = &inc->ihu; + struct babel_proto *p = ifa->proto; + + /* we don't speak no IPv4 */ + if (tlv->ae == BABEL_AE_IP4) return; + + if (tlv->ae != BABEL_AE_WILDCARD && !ipa_equal(tlv->addr, ifa->addr)) + return; // not for us + TRACE(D_PACKETS, "Handling IHU rxcost %d interval %d", tlv->rxcost, + tlv->interval); + struct babel_neighbor *n = babel_get_neighbor(ifa, tlv->sender); + n->txcost = tlv->rxcost; + n->ihu_expiry = now + (3*tlv->interval)/2; // 1.5*interval +} + + +/** + * babel_handle_update - handle incoming route updates. + * @inc: Incoming update TLV. + * @ifa: Interface the update was received on. + * + * This function is called as a handler for update TLVs and handles the updating + * and maintenance of route entries in Babel's internal routing cache. The + * handling follows the actions described in the Babel RFC, and at the end of + * each update handling, babel_select_route() is called on the affected entry to + * optionally update the selected routes and propagate them to the core. + */ +void +babel_handle_update(union babel_tlv *inc, struct babel_iface *ifa) +{ + struct babel_tlv_update *tlv = &inc->update; + struct babel_proto *p = ifa->proto; + struct babel_neighbor *n; + struct babel_entry *e; + struct babel_source *s; + struct babel_route *r; + + int feasible; + TRACE(D_PACKETS, "Handling update for %I/%d with seqno %d metric %d", + tlv->prefix, tlv->plen, tlv->seqno, tlv->metric); + + n = babel_find_neighbor(ifa, tlv->sender); + if (!n) + { + DBG("Babel: Haven't heard from neighbor %I; ignoring update.\n", tlv->sender); + return; + } + + if (tlv->router_id == p->router_id) + { + DBG("Babel: Ignoring update for our own router ID.\n"); + return; + } + + /* we don't speak no IPv4 */ + if (tlv->ae == BABEL_AE_IP4) { + DBG("Babel: Ignoring update for IPv4 address.\n"); + return; + } + + /* 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, tlv->prefix, tlv->plen); + if (!e && tlv->metric == BABEL_INFINITY) + return; + + if (!e) e = babel_get_entry(p, tlv->prefix, tlv->plen); + + s = babel_find_source(e, tlv->router_id); /* for feasibility */ + r = babel_find_route(e, n); /* the route entry indexed by neighbour */ + feasible = babel_is_feasible(s, tlv->seqno, tlv->metric); + + if (!r) + { + + if (!feasible || tlv->metric == BABEL_INFINITY) + return; + + r = babel_get_route(e, n); + r->advert_metric = tlv->metric; + r->router_id = tlv->router_id; + r->metric = babel_compute_metric(n, tlv->metric); + r->next_hop = tlv->next_hop; + r->seqno = tlv->seqno; + } + else if (r == r->e->selected_in && !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 (tlv->router_id == s->router_id) return; + r->metric = BABEL_INFINITY; /* retraction */ + } + else + { + /* last point above - update entry */ + r->advert_metric = tlv->metric; + r->metric = babel_compute_metric(n, tlv->metric); + r->router_id = tlv->router_id; + r->next_hop = tlv->next_hop; + r->seqno = tlv->seqno; + if (tlv->metric != BABEL_INFINITY) + { + r->expiry_interval = (BABEL_ROUTE_EXPIRY_FACTOR*tlv->interval); + 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); +} + +void +babel_handle_route_request(union babel_tlv *inc, struct babel_iface *ifa) +{ + struct babel_tlv_route_request *tlv = &inc->route_request; + struct babel_proto *p = ifa->proto; + struct babel_entry *e; + + TRACE(D_PACKETS, "Handling route request for %I/%d on interface %s", + tlv->prefix, tlv->plen, ifa->ifname); + + /* we don't speak no IPv4 */ + if (tlv->ae == BABEL_AE_IP4) return; + + /* Wildcard request - full update on the interface */ + if (ipa_equal(tlv->prefix,IPA_NONE)) + { + ifa->want_triggered = 1; + return; + } + /* 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, tlv->prefix, tlv->plen); + if (!e) + { + babel_send_retraction(ifa, tlv->prefix, tlv->plen); + } + else + { + babel_trigger_iface_update(ifa); + e->updated = now; + } +} + +/* This follows the RFC, section 3.8.1.2 on seqno requests. */ +void +babel_handle_seqno_request(union babel_tlv *inc, struct babel_iface *ifa) +{ + struct babel_proto *p = ifa->proto; + struct babel_tlv_seqno_request *tlv = &inc->seqno_request; + struct babel_entry *e; + struct babel_route *r; + + /* we don't speak no IPv4 */ + if (tlv->ae == BABEL_AE_IP4) return; + + TRACE(D_PACKETS, "Handling seqno request for %I/%d router_id %lR seqno %d hop count %d", + tlv->prefix, tlv->plen, tlv->router_id, tlv->seqno, tlv->hop_count); + + /* ignore if we have no such entry or entry has infinite metric */ + e = babel_find_entry(p, tlv->prefix, tlv->plen); + if (!e || !e->selected_out || e->selected_out->metric == BABEL_INFINITY) return; + + /* trigger update on incoming interface if we have a selected route with + different router id or seqno no smaller than requested */ + r = e->selected_out; + if (r->router_id != tlv->router_id || ge_mod64k(r->seqno, tlv->seqno)) + { + babel_trigger_iface_update(ifa); + e->updated = now; + return; + } + + /* seqno is larger; check if we own the router id */ + if (tlv->router_id == p->router_id) + { + /* ours; update seqno and trigger global update */ + p->update_seqno++; + babel_trigger_update(p); + } + /* not ours; forward if TTL allows */ + else if (tlv->hop_count > 1) + { + babel_forward_seqno_request(e, tlv, tlv->sender); + } + +} + + + +/** Interface handlers **/ + + +/** + * babel_iface_timer - per-interface timer handler. + * @t: Timer. + * + * This function is called by the per-interface timer and triggers sending of + * periodic Hello's and both triggered and periodic updates. Periodic Hello's + * and updates are simply handled by setting the next_{hello,regular} variables + * on the interface, and triggering an update (and resetting the variable) + * whenever 'now' exceeds that value. + * + * For triggered updates, babel_trigger_iface_update() will set the + * want_triggered field on the interface to a timestamp value. If this is set + * (and the next_triggered time has passed; this is a rate limiting mechanism), + * babel_send_update() will be called with this timestamp as the second + * parameter. This causes updates to be send consisting of only the routes that + * have changed since the time saved in want_triggered. + * + * Mostly when an update is triggered, the route being modified will be set to + * the value of 'now' at the time of the trigger; the >= comparison for + * selecting which routes to send in the update will make sure this is included. + */ +static void +babel_iface_timer(timer *t) +{ + struct babel_iface *ifa = t->data; + struct babel_proto *p = ifa->proto; + bird_clock_t hello_period = ifa->cf->hello_interval; + bird_clock_t update_period = ifa->cf->update_interval; + + if (now >= ifa->next_hello) { + babel_send_hello(ifa, (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS || + ifa->hello_seqno % BABEL_IHU_INTERVAL_FACTOR == 0)); + ifa->next_hello += hello_period * (1 + (now - ifa->next_hello) / hello_period); + } + + if (now >= ifa->next_regular) { + TRACE(D_EVENTS, "Sending regular update on interface %s", ifa->ifname); + babel_send_update(ifa, 0); + ifa->next_regular += update_period * (1 + (now - ifa->next_regular) / update_period); + ifa->want_triggered = 0; + p->triggered = 0; + } else if (ifa->want_triggered && now >= ifa->next_triggered) { + TRACE(D_EVENTS, "Sending triggered update on interface %s", ifa->ifname); + babel_send_update(ifa, ifa->want_triggered); + ifa->next_triggered = now + MIN(5, update_period / 2 + 1); + ifa->want_triggered = 0; + p->triggered = 0; + } + tm_start(ifa->timer, ifa->want_triggered ? 1 : MIN(ifa->next_regular, + ifa->next_hello) - now); +} + +static inline void +babel_iface_kick_timer(struct babel_iface *ifa) +{ + if (ifa->timer->expires > (now + 1)) + tm_start(ifa->timer, 1); +} + + +static void +babel_iface_start(struct babel_iface *ifa) +{ + struct babel_proto *p = ifa->proto; + TRACE(D_EVENTS, "Starting interface %s", ifa->ifname); + ifa->next_hello = now + (random() % ifa->cf->hello_interval) + 1; + ifa->next_regular = now + (random() % ifa->cf->update_interval) + 1; + ifa->next_triggered = now + MIN(5, ifa->cf->update_interval / 2 + 1); + ifa->want_triggered = 0; /* We send an immediate update (below). */ + + tm_start(ifa->timer, 1); + ifa->up = 1; + + babel_send_hello(ifa, 0); + babel_send_wildcard_request(ifa); + babel_send_update(ifa, 0); /* full update */ +} + +static void +babel_iface_stop(struct babel_iface *ifa) +{ + struct babel_proto *p = ifa->proto; + TRACE(D_EVENTS, "Stopping interface %s", ifa->ifname); + + struct babel_neighbor *n; + struct babel_route *r; + node *nod; + + /* Rather than just flushing the neighbours, we set the metric of their routes + to infinity. This allows us to keep the neighbour hello state for when the + interface comes back up. The routes will also be kept until they expire. */ + WALK_LIST(n, ifa->neigh_list) + { + WALK_LIST(nod, n->routes) + { + r = SKIP_BACK(struct babel_route, neigh_route, nod); + r->metric = BABEL_INFINITY; + r->expires = now + r->expiry_interval; + babel_select_route(r->e); + } + } + + tm_stop(ifa->timer); + ifa->up = 0; +} + +static inline int +babel_iface_link_up(struct babel_iface *ifa) +{ + return !ifa->cf->check_link || (ifa->iface->flags & IF_LINK_UP); +} + +static void +babel_iface_update_state(struct babel_iface *ifa) +{ + int up = ifa->sk && babel_iface_link_up(ifa); + + if (up == ifa->up) + return; + + if (up) + babel_iface_start(ifa); + else + babel_iface_stop(ifa); +} + + +static void +babel_iface_update_buffers(struct babel_iface *ifa) +{ + if (!ifa->sk) + return; + + uint rbsize = ifa->cf->rx_buffer ?: MAX(BABEL_MIN_MTU, ifa->iface->mtu); + uint tbsize = ifa->cf->tx_length ?: MAX(BABEL_MIN_MTU, ifa->iface->mtu); + rbsize = MAX(rbsize, tbsize); + + sk_set_rbsize(ifa->sk, rbsize); + sk_set_tbsize(ifa->sk, tbsize); + + ifa->max_pkt_len = tbsize - BABEL_OVERHEAD; +} + + +static struct babel_iface* +babel_find_iface(struct babel_proto *p, struct iface *what) +{ + struct babel_iface *ifa; + + WALK_LIST (ifa, p->interfaces) + if (ifa->iface == what) + return ifa; + + return NULL; +} + +static void +babel_remove_iface(struct babel_proto *p, struct babel_iface *ifa) +{ + TRACE(D_EVENTS, "Removing interface %s", ifa->iface->name); + + struct babel_neighbor *n; + WALK_LIST_FIRST(n, ifa->neigh_list) + babel_flush_neighbor(n); + + rem_node(NODE ifa); + + rfree(ifa->pool); /* contains ifa itself, locks, socket, etc */ +} + + +static void +babel_iface_locked(struct object_lock *lock) +{ + struct babel_iface *ifa = lock->data; + struct babel_proto *p = ifa->proto; + + if (!babel_open_socket(ifa)) + { + log(L_ERR "%s: Cannot open socket for %s", p->p.name, ifa->iface->name); + } + + babel_iface_update_buffers(ifa); + babel_iface_update_state(ifa); +} + + + +static void +babel_add_iface(struct babel_proto *p, struct iface *new, struct babel_iface_config *ic) +{ + struct babel_iface * ifa; + struct object_lock *lock; + pool *pool; + DBG("Babel: New interface %s\n", new->name); + + if (!new) return; + + pool = rp_new(p->p.pool, new->name); + + ifa = mb_allocz(pool, sizeof(struct babel_iface)); + ifa->iface = new; + ifa->ifname = new->name; + ifa->proto = p; + ifa->cf = ic; + ifa->pool = pool; + + add_tail(&p->interfaces, NODE ifa); + + struct ifa* iface; + WALK_LIST(iface, new->addrs) + if (ipa_is_link_local(iface->ip)) + ifa->addr = iface->ip; + + init_list(&ifa->neigh_list); + ifa->hello_seqno = 1; + + ifa->timer = tm_new_set(ifa->pool, babel_iface_timer, ifa, 0, 0); + + init_list(&ifa->tlv_queue); + ifa->send_event = ev_new(ifa->pool); + ifa->send_event->hook = babel_send_queue; + ifa->send_event->data = ifa; + + lock = olock_new(ifa->pool); + lock->addr = IP6_BABEL_ROUTERS; + lock->port = ifa->cf->port; + lock->iface = ifa->iface; + lock->hook = babel_iface_locked; + lock->data = ifa; + lock->type = OBJLOCK_UDP; + + olock_acquire(lock); +} + +static void +babel_if_notify(struct proto *P, unsigned flags, 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 (flags & IF_CHANGE_UP) + { + struct babel_iface_config *ic = (void *) iface_patt_find(&cf->iface_list, iface, iface->addr); + + /* we only speak multicast */ + if (!(iface->flags & IF_MULTICAST)) return; + + if (ic) + babel_add_iface(p, iface, ic); + + return; + } + + struct babel_iface *ifa = babel_find_iface(p, iface); + + if (!ifa) + return; + + if (flags & IF_CHANGE_DOWN) + { + babel_remove_iface(p, ifa); + return; + } + + + if (flags & IF_CHANGE_MTU) + babel_iface_update_buffers(ifa); + + if (flags & IF_CHANGE_LINK) + babel_iface_update_state(ifa); + +} + +static int +babel_reconfigure_iface(struct babel_proto *p, struct babel_iface *ifa, struct babel_iface_config *new) +{ + struct babel_iface_config *old = ifa->cf; + + /* Change of these options would require to reset the iface socket */ + if ((new->port != old->port) || + (new->tx_tos != old->tx_tos) || + (new->tx_priority != old->tx_priority)) + return 0; + + TRACE(D_EVENTS, "Reconfiguring interface %s", ifa->iface->name); + + ifa->cf = new; + + if (ifa->next_regular > (now + new->update_interval)) + ifa->next_regular = now + (random() % new->update_interval) + 1; + + if ((new->tx_length != old->tx_length) || (new->rx_buffer != old->rx_buffer)) + babel_iface_update_buffers(ifa); + + if (new->check_link != old->check_link) + babel_iface_update_state(ifa); + + if (ifa->up) + babel_iface_kick_timer(ifa); + + return 1; +} + +static void +babel_reconfigure_ifaces(struct babel_proto *p, struct babel_config *cf) +{ + struct iface *iface; + + WALK_LIST(iface, iface_list) + { + if (! (iface->flags & IF_UP)) + continue; + + struct babel_iface *ifa = babel_find_iface(p, iface); + struct babel_iface_config *ic = (void *) iface_patt_find(&cf->iface_list, iface, NULL); + + if (ifa && ic) + { + if (babel_reconfigure_iface(p, ifa, ic)) + continue; + + /* Hard restart */ + log(L_INFO "%s: Restarting interface %s", p->p.name, ifa->iface->name); + babel_remove_iface(p, ifa); + babel_add_iface(p, iface, ic); + } + + if (ifa && !ic) + babel_remove_iface(p, ifa); + + if (!ifa && ic) + babel_add_iface(p, iface, ic); + } +} + + + + + +/** Debugging and info output functions **/ + + +static void +babel_dump_source(struct babel_source *s) +{ + debug("Source router_id %lR 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 %lR expires %d\n", + r->neigh ? r->neigh->addr : IPA_NONE, + r->neigh ? r->neigh->ifa->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(" "); + if (r==e->selected_out) debug("*"); + if (r==e->selected_in) debug("+"); + babel_dump_route(r); + } +} + +static void +babel_dump_neighbor(struct babel_neighbor *n) +{ + debug("Neighbor %I txcost %d hello_map %x next seqno %d expires %d/%d\n", + n->addr, n->txcost, n->hello_map, n->next_hello_seqno, + n->hello_expiry ? n->hello_expiry - now : 0, + n->ihu_expiry ? n->ihu_expiry - now : 0); +} + +static void +babel_dump_iface(struct babel_iface *ifa) +{ + struct babel_neighbor *n; + debug("Babel: Interface %s addr %I rxcost %d type %d hello seqno %d intervals %d %d\n", + ifa->ifname, ifa->addr, ifa->cf->rxcost, ifa->cf->type, ifa->hello_seqno, + ifa->cf->hello_interval, ifa->cf->update_interval); + WALK_LIST(n,ifa->neigh_list) { debug(" "); babel_dump_neighbor(n); } + +} + +static void +babel_dump(struct proto *P) +{ + struct babel_proto *p = (struct babel_proto *) P; + struct babel_entry *e; + struct babel_iface *ifa; + debug("Babel: router id %lR update seqno %d\n", p->router_id, p->update_seqno); + WALK_LIST(ifa, p->interfaces) {babel_dump_iface(ifa);} + FIB_WALK(&p->rtable, n) + { + e = (struct babel_entry *)n; + babel_dump_entry(e); + } FIB_WALK_END; +} + +static void +babel_get_route_info(rte *rte, byte *buf, ea_list *attrs) +{ + buf += bsprintf(buf, " (%d/%d) [%lR]", rte->pref, 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; + case EA_BABEL_ROUTER_ID: bsprintf(buf, "router id: %lR", a->u.data); return GA_FULL; + default: return GA_UNKNOWN; + } +} + +void +babel_show_interfaces(struct proto *P, char *iff) +{ + struct babel_proto *p = (void *) P; + struct babel_iface *ifa = NULL; + struct babel_neighbor *n = NULL; + + if (p->p.proto_state != PS_UP) + { + cli_msg(-1021, "%s: is not up", p->p.name); + cli_msg(0, ""); + return; + } + + cli_msg(-1021, "%s:", p->p.name); + cli_msg(-1021, "%-10s %-6s %7s %6s %6s", + "Interface", "State", "RX cost", "Nbrs", "Timer"); + + WALK_LIST(ifa, p->interfaces) + { + if (iff && !patmatch(iff, ifa->iface->name)) + continue; + + int nbrs = 0; + WALK_LIST(n, ifa->neigh_list) + nbrs++; + + int timer = MAX(MIN(ifa->next_regular, ifa->next_hello) - now, 0); + cli_msg(-1021, "%-10s %-6s %7u %6u %6u", + ifa->iface->name, (ifa->up ? "Up" : "Down"), ifa->cf->rxcost, nbrs, timer); + } + + cli_msg(0, ""); +} + +void +babel_show_neighbors(struct proto *P, char *iff) +{ + struct babel_proto *p = (void *) P; + struct babel_iface *ifa = NULL; + struct babel_neighbor *n = NULL; + struct babel_route *r = NULL; + + if (p->p.proto_state != PS_UP) + { + cli_msg(-1022, "%s: is not up", p->p.name); + cli_msg(0, ""); + return; + } + + cli_msg(-1022, "%s:", p->p.name); + cli_msg(-1022, "%-25s %-10s %6s %6s %10s", + "IP address", "Interface", "Metric", "Routes", "Next hello"); + + WALK_LIST(ifa, p->interfaces) + { + if (iff && !patmatch(iff, ifa->iface->name)) + continue; + + WALK_LIST(n, ifa->neigh_list) + { + int rts = 0; + WALK_LIST(r, n->routes) + rts++; + int timer = n->hello_expiry - now; + cli_msg(-1022, "%-25I %-10s %6u %6u %10u", + n->addr, ifa->iface->name, n->txcost, rts, timer); + } + } + + cli_msg(0, ""); +} + +void +babel_show_entries(struct proto *P, char *ent) +{ + struct babel_proto *p = (void *) P; + struct babel_entry *e = NULL; + struct babel_source *s = NULL; + struct babel_route *r = NULL; + + char ipbuf[STD_ADDRESS_P_LENGTH+5]; + char ridbuf[ROUTER_ID_64_LENGTH+1]; + + if (p->p.proto_state != PS_UP) + { + cli_msg(-1022, "%s: is not up", p->p.name); + cli_msg(0, ""); + return; + } + + cli_msg(-1022, "%s:", p->p.name); + cli_msg(-1022, "%-29s %-23s %6s %5s %7s %7s", + "Prefix", "Router ID", "Metric", "Seqno", "Expires", "Sources"); + + FIB_WALK(&p->rtable, n) + { + e = (struct babel_entry *)n; + r = e->selected_in ? e->selected_in : e->selected_out; + int srcs = 0; + WALK_LIST(s, e->sources) + srcs++; + + bsprintf(ipbuf, "%I/%u", e->n.prefix, e->n.pxlen); + + if (ent && !patmatch(ent, ipbuf)) + continue; + + if (r) { + + if (r->router_id == p->router_id) + bsprintf(ridbuf, "%s", "<self>"); + else + bsprintf(ridbuf, "%lR", r->router_id); + + int time = r->expires ? r->expires - now : 0; + + cli_msg(-1022, "%-29s %-23s %6u %5u %7u %7u", + ipbuf, ridbuf, r->metric, r->seqno, time, srcs); + + } else { + + cli_msg(-1022, "%-29s %-45s %7u", ipbuf, "<pending>", srcs); + + } + + } FIB_WALK_END; + + cli_msg(0, ""); +} + + +/** Interaction with Bird core **/ + + +/** + * babel_timer - global timer hook. + * @t: Timer. + * + * This function is called by the global protocol instance timer and handles + * expiration of routes and neighbours as well as pruning of the seqno request + * cache. + */ +static void +babel_timer(timer *t) +{ + struct babel_proto *p = t->data; + babel_expire_routes(p); + babel_expire_seqno_requests(p); + babel_expire_neighbors(p); +} + +static inline void +babel_kick_timer(struct babel_proto *p) +{ + if (p->timer->expires > (now + 1)) + tm_start(p->timer, 1); +} + + +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 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) +{ + 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; + u8 trigger_upd = 0; + + if (new) + { + TRACE(D_EVENTS, "Got route from nest: %I/%d", net->n.prefix, net->n.pxlen); + e = babel_get_entry(p, net->n.prefix, net->n.pxlen); + r = (new->attrs->src->proto == P) ? e->selected_in : babel_get_route(e, NULL); + + if (OUR_ROUTE(r)) + { + r->seqno = p->update_seqno; + r->router_id = p->router_id; + r->metric = 0; + } + + if (r != e->selected_out) { + e->selected_out = r; + e->updated = now; + trigger_upd = 1; + } + } + else + { + TRACE(D_EVENTS, "Lost route from nest: %I/%d", net->n.prefix, net->n.pxlen); + e = babel_find_entry(p, net->n.prefix, net->n.pxlen); + if (e && e->selected_out) + { + if(OUR_ROUTE(e->selected_out)) { + /* We originate this route, so set its metric to infinity and set an + expiry time. This causes a retraction to be sent, and later the route + to be flushed once the hold time has passed. */ + e->selected_out->metric = BABEL_INFINITY; + e->selected_out->expires = now + BABEL_HOLD_TIME; + trigger_upd = 1; + } else { + /* This is a route originating from someone else that was lost; + presumably because an export filter was updated to filter it. This + means we can't set the metric to infinity (it would be overridden on + subsequent updates from the peer originating the route), so just + clear the exported route. + + This causes peers to expire the route after a while (like if we just + shut down), but it's the best we can do in these circumstances; and + since export filters presumably aren't updated that often this is + acceptable. */ + e->selected_out = NULL; + } + e->updated = now; + } + } + + if(trigger_upd) + babel_trigger_update(p); +} + +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; +} + + +/** Init and reconfigure **/ + + +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->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; +} + + +static int +babel_reconfigure(struct proto *P, struct proto_config *c) +{ + struct babel_proto *p = (void *) P; + struct babel_config *new = (void *) c; + TRACE(D_EVENTS, "Reconfiguring"); + + p->p.cf = c; + babel_reconfigure_ifaces(p, new); + + babel_trigger_update(p); + babel_kick_timer(p); + return 1; +} + +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); + 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->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->tlv_slab = sl_new(P->pool, sizeof(struct babel_tlv_node)); + p->seqno_slab = sl_new(P->pool, sizeof(struct babel_seqno_request)); + init_list(&p->seqno_cache); + 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, + .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..6f65e97 --- /dev/null +++ b/proto/babel/babel.h @@ -0,0 +1,349 @@ +/* -*- c-file-style: "gnu"; indent-tabs-mode: nil; -*- + * + * The Babel protocol + * + * Copyright (c) 2015-2016 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/cli.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 4 +#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_TIME_UNITS 100 /* On-wire times are counted in centiseconds */ + +#define BABEL_SEQNO_REQUEST_EXPIRY 60 +#define BABEL_GARBAGE_INTERVAL 300 + +/* ip header + udp header + babel header */ +#define BABEL_OVERHEAD (SIZE_OF_IP_HEADER+UDP_HEADER_LENGTH+sizeof(struct babel_pkt_header)) +#define BABEL_MIN_MTU (512 + BABEL_OVERHEAD) + +struct babel_pkt_header { + u8 magic; + u8 version; + u16 length; +}; + + + +enum babel_tlv_type { + BABEL_TLV_PAD0 = 0, + BABEL_TLV_PADN = 1, + BABEL_TLV_ACK_REQ = 2, + BABEL_TLV_ACK = 3, + BABEL_TLV_HELLO = 4, + BABEL_TLV_IHU = 5, + BABEL_TLV_ROUTER_ID = 6, + BABEL_TLV_NEXT_HOP = 7, + BABEL_TLV_UPDATE = 8, + BABEL_TLV_ROUTE_REQUEST = 9, + BABEL_TLV_SEQNO_REQUEST = 10, + /* extensions - not implemented + BABEL_TLV_TS_PC = 11, + BABEL_TLV_HMAC = 12, + BABEL_TLV_SS_UPDATE = 13, + BABEL_TLV_SS_REQUEST = 14, + BABEL_TLV_SS_SEQNO_REQUEST = 15, + */ + BABEL_TLV_MAX +}; + +enum babel_iface_type { + /* In practice, UNDEF and WIRED give equivalent behaviour */ + BABEL_IFACE_TYPE_UNDEF = 0, + BABEL_IFACE_TYPE_WIRED = 1, + BABEL_IFACE_TYPE_WIRELESS = 2, + BABEL_IFACE_TYPE_MAX +}; + +enum babel_ae_type { + BABEL_AE_WILDCARD = 0, + BABEL_AE_IP4 = 1, + BABEL_AE_IP6 = 2, + BABEL_AE_IP6_LL = 3, + BABEL_AE_MAX +}; + + + +struct babel_tlv_ack_req { + u8 type; + u16 nonce; + u16 interval; + ip_addr sender; +}; + +struct babel_tlv_ack { + u8 type; + u16 nonce; +}; + +struct babel_tlv_hello { + u8 type; + u16 seqno; + u16 interval; + ip_addr sender; +}; + +struct babel_tlv_ihu { + u8 type; + u8 ae; + u16 rxcost; + u16 interval; + ip_addr addr; + ip_addr sender; +}; + +struct babel_tlv_update { + u8 type; + u8 ae; + u8 plen; + u16 interval; + u16 seqno; + u16 metric; + ip_addr prefix; + u64 router_id; + ip_addr next_hop; + ip_addr sender; +}; + +struct babel_tlv_route_request { + u8 type; + u8 ae; + u8 plen; + ip_addr prefix; +}; + +struct babel_tlv_seqno_request { + u8 type; + u8 ae; + u8 plen; + u16 seqno; + u8 hop_count; + u64 router_id; + ip_addr prefix; + ip_addr sender; +}; + +union babel_tlv { + u8 type; + struct babel_tlv_ack_req ack_req; + struct babel_tlv_ack ack; + struct babel_tlv_hello hello; + struct babel_tlv_ihu ihu; + struct babel_tlv_update update; + struct babel_tlv_route_request route_request; + struct babel_tlv_seqno_request seqno_request; +}; + + + +/* 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_iface { + node n; + + struct babel_proto *proto; + struct iface *iface; + struct object_lock *lock; + + struct babel_iface_config *cf; + + u8 up; + + pool *pool; + char *ifname; + sock *sk; + ip_addr addr; + int max_pkt_len; + list neigh_list; /* List of neighbors seen on this iface (struct babel_neighbor) */ + list tlv_queue; + + u16 hello_seqno; /* To be increased on each hello */ + + bird_clock_t next_hello; + bird_clock_t next_regular; + bird_clock_t next_triggered; + bird_clock_t want_triggered; + + timer *timer; + event *send_event; + +}; + +struct babel_iface_config { + struct iface_patt i; + + u16 rxcost; + u8 type; + u8 check_link; + int port; + u16 hello_interval; + u16 ihu_interval; + u16 update_interval; + + u16 rx_buffer; /* RX buffer size, 0 for MTU */ + u16 tx_length; /* TX packet length limit (including headers), 0 for MTU */ + int tx_tos; + int tx_priority; + +}; + +struct babel_neighbor { + node n; + struct babel_iface *ifa; + + ip_addr addr; + u16 txcost; + u8 hello_cnt; + 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; + + 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; + struct babel_proto *proto; + struct babel_route *selected_in; + struct babel_route *selected_out; + + bird_clock_t updated; + + 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 */ +}; + +struct babel_proto { + struct proto p; + timer *timer; + struct fib rtable; + list interfaces; /* Interfaces we really know about (struct babel_iface) */ + u16 update_seqno; /* To be increased on request */ + u64 router_id; + u8 triggered; /* For triggering global updates */ + + slab *entry_slab; + slab *route_slab; + slab *source_slab; + slab *tlv_slab; + + slab *seqno_slab; + list seqno_cache; /* Seqno requests in the cache (struct babel_seqno_request) */ +}; + + + +void babel_init_config(struct babel_config *c); + +/* Handlers */ + +void babel_handle_ack_req(union babel_tlv *tlv, struct babel_iface *ifa); +void babel_handle_ack(union babel_tlv *tlv, struct babel_iface *ifa); +void babel_handle_hello(union babel_tlv *tlv, struct babel_iface *ifa); +void babel_handle_ihu(union babel_tlv *tlv, struct babel_iface *ifa); +void babel_handle_router_id(union babel_tlv *tlv, struct babel_iface *ifa); +void babel_handle_update(union babel_tlv *tlv, struct babel_iface *ifa); +void babel_handle_route_request(union babel_tlv *tlv, struct babel_iface *ifa); +void babel_handle_seqno_request(union babel_tlv *tlv, struct babel_iface *ifa); + + +/* Packet mangling code - packet.c */ +struct babel_tlv_node { + node n; + union babel_tlv tlv; +}; + +void babel_enqueue(union babel_tlv *tlv, struct babel_iface *ifa); +void babel_send_unicast(union babel_tlv *tlv, struct babel_iface *ifa, ip_addr dest); +int babel_open_socket(struct babel_iface *ifa); +void babel_send_queue(void *arg); + +void babel_show_interfaces(struct proto *P, char *iff); +void babel_show_neighbors(struct proto *P, char *iff); +void babel_show_entries(struct proto *P, char *iff); diff --git a/proto/babel/config.Y b/proto/babel/config.Y new file mode 100644 index 0000000..f3b297f --- /dev/null +++ b/proto/babel/config.Y @@ -0,0 +1,129 @@ +/* + * BIRD -- Babel Configuration + * + * Copyright (c) 2015-2016 Toke Høiland-Jørgensen + * + * 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 ((struct babel_iface_config *) this_ipatt) + +CF_DECLS + +CF_KEYWORDS(BABEL, METRIC, RXCOST, HELLO, UPDATE, INTERVAL, PORT, WIRED, +WIRELESS, RX, TX, BUFFER, LENGTH, CHECK, LINK, BABEL_METRIC) + +CF_GRAMMAR + +CF_ADDTO(proto, babel_proto) + +babel_proto_start: proto_start BABEL +{ + this_proto = proto_config_new(&proto_babel, $1); + init_list(&BABEL_CFG->iface_list); +}; + +babel_proto_item: + proto_item + | INTERFACE babel_iface + ; + +babel_proto_opts: + /* empty */ + | babel_proto_opts babel_proto_item ';' + ; + +babel_proto: + babel_proto_start proto_name '{' babel_proto_opts '}'; + + +babel_iface_start: +{ + 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->port = BABEL_PORT; + BABEL_IFACE->type = BABEL_IFACE_TYPE_WIRED; + BABEL_IFACE->tx_tos = IP_PREC_INTERNET_CONTROL; + BABEL_IFACE->tx_priority = sk_priority_control; + BABEL_IFACE->check_link = 1; +}; + + +babel_iface_finish: +{ + if (BABEL_IFACE->type == BABEL_IFACE_TYPE_WIRELESS) + { + if (!BABEL_IFACE->hello_interval) + BABEL_IFACE->hello_interval = BABEL_HELLO_INTERVAL_WIRELESS; + if (!BABEL_IFACE->rxcost) + BABEL_IFACE->rxcost = BABEL_RXCOST_WIRELESS; + } + else + { + if (!BABEL_IFACE->hello_interval) + BABEL_IFACE->hello_interval = BABEL_HELLO_INTERVAL_WIRED; + if (!BABEL_IFACE->rxcost) + BABEL_IFACE->rxcost = BABEL_RXCOST_WIRED; + } + + if (!BABEL_IFACE->update_interval) + BABEL_IFACE->update_interval = BABEL_IFACE->hello_interval*BABEL_UPDATE_INTERVAL_FACTOR; + BABEL_IFACE->ihu_interval = BABEL_IFACE->hello_interval*BABEL_IHU_INTERVAL_FACTOR; +}; + + +babel_iface_item: + | PORT expr { BABEL_IFACE->port = $2; if (($2<1) || ($2>65535)) cf_error("Invalid port number"); } + | RXCOST expr { BABEL_IFACE->rxcost = $2; if (($2<1) || ($2>65535)) cf_error("Invalid rxcost"); } + | HELLO INTERVAL expr { BABEL_IFACE->hello_interval = $3; if (($3<1) || ($3>65535)) cf_error("Invalid hello interval"); } + | UPDATE INTERVAL expr { BABEL_IFACE->update_interval = $3; if (($3<1) || ($3>65535)) cf_error("Invalid hello interval"); } + | TYPE WIRED { BABEL_IFACE->type = BABEL_IFACE_TYPE_WIRED; } + | TYPE WIRELESS { BABEL_IFACE->type = BABEL_IFACE_TYPE_WIRELESS; } + | RX BUFFER expr { BABEL_IFACE->rx_buffer = $3; if (($3<256) || ($3>65535)) cf_error("RX buffer must be in range 256-65535"); } + | TX LENGTH expr { BABEL_IFACE->tx_length = $3; if (($3<256) || ($3>65535)) cf_error("TX length must be in range 256-65535"); } + | TX tos { BABEL_IFACE->tx_tos = $2; } + | TX PRIORITY expr { BABEL_IFACE->tx_priority = $3; } + | CHECK LINK bool { BABEL_IFACE->check_link = $3; } + ; + +babel_iface_opts: + /* empty */ + | babel_iface_opts babel_iface_item ';' + ; + +babel_iface_opt_list: + /* empty */ + | '{' babel_iface_opts '}' + ; + + +babel_iface: + babel_iface_start iface_patt_list_nopx babel_iface_opt_list babel_iface_finish; + +CF_ADDTO(dynamic_attr, BABEL_METRIC { $$ = f_new_dynamic_attr(EAF_TYPE_INT | EAF_TEMP, T_INT, EA_BABEL_METRIC); }) + +CF_CLI_HELP(SHOW BABEL, ..., [[Show information about Babel protocol]]); + +CF_CLI(SHOW BABEL INTERFACES, optsym opttext, [<name>] [\"<interface>\"], [[Show information about Babel interfaces]]) +{ babel_show_interfaces(proto_get_named($4, &proto_babel), $5); }; + +CF_CLI(SHOW BABEL NEIGHBORS, optsym opttext, [<name>] [\"<interface>\"], [[Show information about Babel neighbors]]) +{ babel_show_neighbors(proto_get_named($4, &proto_babel), $5); }; + +CF_CLI(SHOW BABEL ENTRIES, optsym opttext, [<name>] [\"<prefix>\"], [[Show information about Babel prefix entries]]) +{ babel_show_entries(proto_get_named($4, &proto_babel), $5); }; + +CF_CODE + +CF_END diff --git a/proto/babel/packet.c b/proto/babel/packet.c new file mode 100644 index 0000000..799e73b --- /dev/null +++ b/proto/babel/packet.c @@ -0,0 +1,871 @@ +/** -*- c-file-style: "gnu"; indent-tabs-mode: nil; -*- + * + * The Babel protocol + * + * Copyright (c) 2015-2016 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" +#include "packet.h" + +#define BAD(x) { log(L_REMOTE "%s: " x, p->p.name); return 1; } +#define FIRST_TLV(p) ((struct babel_pkt_tlv_header *)(((struct babel_pkt_header *) p) + 1)) +#define NEXT_TLV(t) (t = (void *)((byte *)t) + TLV_SIZE(t)) +#define TLV_SIZE(t) (t->type == BABEL_TLV_PAD0 ? 1 : t->length + sizeof(struct babel_pkt_tlv_header)) + + +static inline ip6_addr +get_ip6_ll(void *p) +{ + return ipa_build6(0xfe800000,0,get_u32(p),get_u32(p+sizeof(u32))); +} + +static inline void +put_ip6_ll(void *p, ip6_addr addr) +{ + put_u32(p, _I2(addr)); + put_u32(p+sizeof(u32), _I3(addr)); +} + + +static enum parse_result +babel_read_ack_req(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_parse_state *state); +static enum parse_result +babel_read_hello(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_parse_state *state); +static enum parse_result +babel_read_ihu(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_parse_state *state); +static enum parse_result +babel_read_router_id(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_parse_state *state); +static enum parse_result +babel_read_next_hop(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_parse_state *state); +static enum parse_result +babel_read_update(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_parse_state *state); +static enum parse_result +babel_read_route_request(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_parse_state *state); +static enum parse_result +babel_read_seqno_request(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_parse_state *state); + + +static int +babel_write_ack(struct babel_pkt_tlv_header *hdr, union babel_tlv *tlv, + struct babel_write_state *state, int max_len); +static int +babel_write_hello(struct babel_pkt_tlv_header *hdr, union babel_tlv *tlv, + struct babel_write_state *state, int max_len); +static int +babel_write_ihu(struct babel_pkt_tlv_header *hdr, union babel_tlv *tlv, + struct babel_write_state *state, int max_len); +static int +babel_write_update(struct babel_pkt_tlv_header *hdr, union babel_tlv *tlv, + struct babel_write_state *state, int max_len); +static int +babel_write_route_request(struct babel_pkt_tlv_header *hdr, union babel_tlv *tlv, + struct babel_write_state *state, int max_len); +static int +babel_write_seqno_request(struct babel_pkt_tlv_header *hdr, union babel_tlv *tlv, + struct babel_write_state *state, int max_len); + +struct babel_pkt_tlv_data { + u8 min_size; + enum parse_result (*read_tlv)(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, struct babel_parse_state *state); + int (*write_tlv)(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, struct babel_write_state *state, int max_len); + void (*handle_tlv)(union babel_tlv *tlv, struct babel_iface *ifa); +}; + +const static struct babel_pkt_tlv_data tlv_data[BABEL_TLV_MAX] = { + [BABEL_TLV_PAD0] = {0, NULL,NULL,NULL}, + [BABEL_TLV_PADN] = {0, NULL,NULL,NULL}, + [BABEL_TLV_ACK_REQ] = {sizeof(struct babel_pkt_tlv_ack_req), + babel_read_ack_req, + NULL, + babel_handle_ack_req}, + [BABEL_TLV_ACK] = {0, NULL, + babel_write_ack, + NULL}, + [BABEL_TLV_HELLO] = {sizeof(struct babel_pkt_tlv_hello), + babel_read_hello, + babel_write_hello, + babel_handle_hello}, + [BABEL_TLV_IHU] = {sizeof(struct babel_pkt_tlv_ihu), + babel_read_ihu, + babel_write_ihu, + babel_handle_ihu}, + [BABEL_TLV_ROUTER_ID] = {sizeof(struct babel_pkt_tlv_router_id), + babel_read_router_id, + NULL, + NULL}, + [BABEL_TLV_NEXT_HOP] = {sizeof(struct babel_pkt_tlv_next_hop), + babel_read_next_hop, + NULL, + NULL}, + [BABEL_TLV_UPDATE] = {sizeof(struct babel_pkt_tlv_update), + babel_read_update, + babel_write_update, + babel_handle_update}, + [BABEL_TLV_ROUTE_REQUEST] = {sizeof(struct babel_pkt_tlv_route_request), + babel_read_route_request, + babel_write_route_request, + babel_handle_route_request}, + [BABEL_TLV_SEQNO_REQUEST] = {sizeof(struct babel_pkt_tlv_seqno_request), + babel_read_seqno_request, + babel_write_seqno_request, + babel_handle_seqno_request}, +}; + +static inline int +babel_read_tlv(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_parse_state *state) +{ + if (hdr->type <= BABEL_TLV_PADN || + hdr->type >= BABEL_TLV_MAX || + tlv_data[hdr->type].read_tlv == NULL) + return PARSE_IGNORE; + + if (TLV_SIZE(hdr) < tlv_data[hdr->type].min_size) + return PARSE_ERROR; + + return tlv_data[hdr->type].read_tlv(hdr, tlv, state); +} + +static enum parse_result +babel_read_ack_req(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_parse_state *state) +{ + struct babel_pkt_tlv_ack_req * pkt_tlv = (struct babel_pkt_tlv_ack_req *) hdr; + tlv->ack_req.nonce = get_u16(&pkt_tlv->nonce); + tlv->ack_req.interval = MAX(1,get_u16(&pkt_tlv->interval)/BABEL_TIME_UNITS); + tlv->ack_req.sender = state->saddr; + return PARSE_SUCCESS; +} + + +static enum parse_result +babel_read_hello(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_parse_state *state) +{ + struct babel_pkt_tlv_hello * pkt_tlv = (struct babel_pkt_tlv_hello *) hdr; + tlv->hello.seqno = get_u16(&pkt_tlv->seqno); + tlv->hello.interval = MAX(1,get_u16(&pkt_tlv->interval)/BABEL_TIME_UNITS); + tlv->hello.sender = state->saddr; + return PARSE_SUCCESS; +} + + +static enum parse_result +babel_read_ihu(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_parse_state *state) +{ + struct babel_pkt_tlv_ihu * pkt_tlv = (struct babel_pkt_tlv_ihu *) hdr; + tlv->ihu.ae = pkt_tlv->ae; + tlv->ihu.rxcost = get_u16(&pkt_tlv->rxcost); + tlv->ihu.interval = MAX(1,get_u16(&pkt_tlv->interval)/BABEL_TIME_UNITS); + + if (tlv->ihu.ae >= BABEL_AE_MAX) + return PARSE_IGNORE; + + // We handle link-local IPs. In every other case, the addr field will be 0 but + // validation will succeed. The handler takes care of these cases. + if (tlv->ihu.ae == BABEL_AE_IP6_LL) + { + if (TLV_SIZE(hdr) < sizeof(struct babel_pkt_tlv_ihu)+8) return PARSE_ERROR; + tlv->ihu.addr = get_ip6_ll(&pkt_tlv->addr); + } + tlv->ihu.sender = state->saddr; + return PARSE_SUCCESS; +} + + +static enum parse_result +babel_read_router_id(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_parse_state *state) +{ + struct babel_pkt_tlv_router_id * pkt_tlv = (struct babel_pkt_tlv_router_id *) hdr; + state->router_id = pkt_tlv->router_id; + state->router_id_seen = 1; + return PARSE_SUCCESS; +} + +static enum parse_result +babel_read_next_hop(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_parse_state *state) +{ + struct babel_pkt_tlv_next_hop * pkt_tlv = (struct babel_pkt_tlv_next_hop *) hdr; + + if (pkt_tlv->ae >= BABEL_AE_MAX) + return PARSE_IGNORE; + + if (pkt_tlv->ae == BABEL_AE_IP6_LL) + { + if (TLV_SIZE(hdr) < sizeof(struct babel_pkt_tlv_next_hop)+8) return PARSE_ERROR; + state->next_hop = get_ip6_ll(&pkt_tlv->addr); + } else if (pkt_tlv->ae == BABEL_AE_IP6) { + if (TLV_SIZE(hdr) < sizeof(struct babel_pkt_tlv_next_hop)+sizeof(ip6_addr)) + return PARSE_ERROR; + state->next_hop = get_ip6(&pkt_tlv->addr); + } + return PARSE_SUCCESS; +} + +static enum parse_result +babel_read_update(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_parse_state *state) +{ + struct babel_pkt_tlv_update * pkt_tlv = (struct babel_pkt_tlv_update *) hdr; + char buf[16] = {}; + u8 len = (pkt_tlv->plen + 7)/8; + tlv->update.ae = pkt_tlv->ae; + tlv->update.plen = pkt_tlv->plen; + tlv->update.interval = MAX(1,get_u16(&pkt_tlv->interval)/BABEL_TIME_UNITS); + tlv->update.seqno = get_u16(&pkt_tlv->seqno); + tlv->update.metric = get_u16(&pkt_tlv->metric); + + if (tlv->update.plen > MAX_PREFIX_LENGTH) + return PARSE_ERROR; + + if (tlv->update.ae >= BABEL_AE_MAX) + return PARSE_IGNORE; + /* Can only omit bits if a previous update defined a prefix to take them from */ + if (pkt_tlv->omitted && ipa_equal(state->prefix, IPA_NONE)) + return PARSE_ERROR; + + /* TLV should be large enough to hold the entire prefix */ + if (TLV_SIZE(hdr) < sizeof(struct babel_pkt_tlv_update) + len - pkt_tlv->omitted) + return PARSE_ERROR; + + /* IP address decoding */ + if (tlv->update.ae == BABEL_AE_WILDCARD || tlv->update.ae == BABEL_AE_IP4) + { + tlv->update.prefix = IPA_NONE; + } + else if (tlv->update.ae == BABEL_AE_IP6_LL) + { + tlv->update.prefix = get_ip6_ll(&pkt_tlv->addr); + } + else + { + /* if we have omitted bytes, get them from previous prefix */ + if (pkt_tlv->omitted) put_ipa(buf, state->prefix); + /* if the prefix is longer than the omitted octets, copy the rest */ + if (pkt_tlv->omitted < len) memcpy(buf+pkt_tlv->omitted, + &pkt_tlv->addr, + len - pkt_tlv->omitted); + /* make sure the tail is zeroed */ + if (len < 16) memset(buf+len, 0, 16-len); + tlv->update.prefix = get_ip6(buf); + } + if (pkt_tlv->flags & BABEL_FLAG_DEF_PREFIX) + { + state->prefix = tlv->update.prefix; + } + if (pkt_tlv->flags & BABEL_FLAG_ROUTER_ID) + { + if (pkt_tlv->ae == BABEL_AE_IP4) return PARSE_ERROR; + state->router_id = ((u64) _I2(tlv->update.prefix)) << 32 | _I3(tlv->update.prefix); + state->router_id_seen = 1; + } + if (!state->router_id_seen) + { + DBG("Babel: No router ID seen before update\n"); + return PARSE_ERROR; + } + + tlv->update.router_id = state->router_id; + tlv->update.next_hop = state->next_hop; + tlv->update.sender = state->saddr; + return PARSE_SUCCESS; +} + + +static enum parse_result +babel_read_route_request(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_parse_state *state) +{ + struct babel_pkt_tlv_route_request * pkt_tlv = (struct babel_pkt_tlv_route_request *) hdr; + u8 len = (pkt_tlv->plen + 7)/8; + char buf[16] = {}; + tlv->route_request.ae = pkt_tlv->ae; + tlv->route_request.plen = pkt_tlv->plen; + + if (tlv->route_request.plen > MAX_PREFIX_LENGTH) + return PARSE_ERROR; + + /* Prefixes cannot be link-local addresses. */ + if (tlv->route_request.ae >= BABEL_AE_IP6_LL) + return PARSE_ERROR; + + /* enough space to hold the prefix */ + if (TLV_SIZE(hdr) < sizeof(struct babel_pkt_tlv_route_request) + len) + return PARSE_ERROR; + + /* wildcard requests must have plen 0, others must not */ + if ((tlv->route_request.ae == BABEL_AE_WILDCARD && tlv->route_request.plen > 0) || + (tlv->route_request.ae != BABEL_AE_WILDCARD && tlv->route_request.plen == 0)) + return PARSE_ERROR; + + /* IP address decoding */ + if (tlv->route_request.ae == BABEL_AE_WILDCARD || tlv->route_request.ae == BABEL_AE_IP4) + { + tlv->route_request.prefix = IPA_NONE; + } + else + { + memcpy(buf, &pkt_tlv->addr, len); + tlv->route_request.prefix = get_ip6(buf); + } + + return PARSE_SUCCESS; +} + +static enum parse_result +babel_read_seqno_request(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_parse_state *state) +{ + struct babel_pkt_tlv_seqno_request * pkt_tlv = (struct babel_pkt_tlv_seqno_request *) hdr; + u8 len = (pkt_tlv->plen + 7)/8; + char buf[16] = {}; + tlv->seqno_request.ae = pkt_tlv->ae; + tlv->seqno_request.plen = pkt_tlv->plen; + tlv->seqno_request.seqno = get_u16(&pkt_tlv->seqno); + tlv->seqno_request.hop_count = pkt_tlv->hop_count; + tlv->seqno_request.router_id = get_u64(&pkt_tlv->router_id); + + if (tlv->seqno_request.plen > MAX_PREFIX_LENGTH) { + DBG("Babel: Prefix len too long\n"); + return PARSE_ERROR; + } + + /* Prefixes cannot be link-local addresses. */ + if (tlv->seqno_request.ae >= BABEL_AE_IP6_LL) { + DBG("Babel: Invalid AE\n"); + return PARSE_ERROR; + } + + /* enough space to hold the prefix */ + if (TLV_SIZE(hdr) < sizeof(struct babel_pkt_tlv_seqno_request) + len) { + DBG("Babel: TLV size too small\n"); + return PARSE_ERROR; + } + + /* wildcard requests not allowed */ + if (tlv->seqno_request.ae == BABEL_AE_WILDCARD) { + DBG("Babel: Wildcard request disallowed\n"); + return PARSE_ERROR; + } + + /* IP address decoding */ + if (tlv->seqno_request.plen == 0 || tlv->seqno_request.ae == BABEL_AE_IP4) + { + tlv->seqno_request.prefix = IPA_NONE; + } + else + { + memcpy(buf, &pkt_tlv->addr, len); + tlv->seqno_request.prefix = get_ip6(buf); + } + + tlv->seqno_request.sender = state->saddr; + return PARSE_SUCCESS; + +} + +static int +babel_write_tlv(struct babel_pkt_tlv_header *hdr, + union babel_tlv *tlv, + struct babel_write_state *state, + int max_len) +{ + if (tlv->type <= BABEL_TLV_PADN || + tlv->type >= BABEL_TLV_MAX || + tlv_data[tlv->type].write_tlv == NULL) + return 0; + + if (max_len < tlv_data[tlv->type].min_size) + return 0; + + memset(hdr, 0, tlv_data[tlv->type].min_size); + return tlv_data[tlv->type].write_tlv(hdr, tlv, state, max_len); +} + + +static int +babel_write_ack(struct babel_pkt_tlv_header *hdr, union babel_tlv *tlv, + struct babel_write_state *state, int max_len) +{ + struct babel_pkt_tlv_ack * pkt_tlv = (struct babel_pkt_tlv_ack *) hdr; + hdr->type = BABEL_TLV_ACK; + hdr->length = sizeof(struct babel_pkt_tlv_ack) - sizeof(struct babel_pkt_tlv_header); + put_u16(&pkt_tlv->nonce, tlv->ack.nonce); + return sizeof(struct babel_pkt_tlv_ack); +} + +static int +babel_write_hello(struct babel_pkt_tlv_header *hdr, union babel_tlv *tlv, + struct babel_write_state *state, int max_len) +{ + struct babel_pkt_tlv_hello * pkt_tlv = (struct babel_pkt_tlv_hello *) hdr; + hdr->type = BABEL_TLV_HELLO; + hdr->length = sizeof(struct babel_pkt_tlv_hello) - sizeof(struct babel_pkt_tlv_header); + put_u16(&pkt_tlv->seqno, tlv->hello.seqno); + put_u16(&pkt_tlv->interval, tlv->hello.interval*BABEL_TIME_UNITS); + return sizeof(struct babel_pkt_tlv_hello); +} + +static int +babel_write_ihu(struct babel_pkt_tlv_header *hdr, union babel_tlv *tlv, + struct babel_write_state *state, int max_len) +{ + + struct babel_pkt_tlv_ihu * pkt_tlv = (struct babel_pkt_tlv_ihu *) hdr; + + if (ipa_is_link_local(tlv->ihu.addr) && max_len < sizeof(struct babel_pkt_tlv_ihu) + 8) + return 0; + + hdr->type = BABEL_TLV_IHU; + hdr->length = sizeof(struct babel_pkt_tlv_ihu) - sizeof(struct babel_pkt_tlv_header); + put_u16(&pkt_tlv->rxcost, tlv->ihu.rxcost); + put_u16(&pkt_tlv->interval, tlv->ihu.interval*BABEL_TIME_UNITS); + if (!ipa_is_link_local(tlv->ihu.addr)) + { + pkt_tlv->ae = BABEL_AE_WILDCARD; + return sizeof(struct babel_pkt_tlv_ihu); + } + put_ip6_ll(&pkt_tlv->addr, tlv->ihu.addr); + pkt_tlv->ae = BABEL_AE_IP6_LL; + hdr->length += 8; + return sizeof(struct babel_pkt_tlv_ihu) + 8; +} + +static int +babel_write_update(struct babel_pkt_tlv_header *hdr, union babel_tlv *tlv, + struct babel_write_state *state, int max_len) +{ + + struct babel_pkt_tlv_update * pkt_tlv = (struct babel_pkt_tlv_update *) hdr; + struct babel_pkt_tlv_router_id * router_id; + char buf[16] = {}; + u8 size, len = (tlv->update.plen + 7)/8; + size = sizeof(struct babel_pkt_tlv_update) + len; + + /* If we haven't added the right router ID previous to this update, we really + add two TLVs to the packet buffer. Check that we have space for this (if + relevant), and also if we have space for the update TLV itself.. */ + if (max_len < size || ((!state->router_id_seen || + state->router_id != tlv->update.router_id) && + max_len < size + sizeof(struct babel_pkt_tlv_router_id))) + return 0; + put_ipa(buf, tlv->update.prefix); + + if (!state->router_id_seen || state->router_id != tlv->update.router_id) { + hdr->type = BABEL_TLV_ROUTER_ID; + hdr->length = sizeof(struct babel_pkt_tlv_router_id) - sizeof(struct babel_pkt_tlv_header); + router_id = (struct babel_pkt_tlv_router_id *)hdr; + put_u64(&router_id->router_id, tlv->update.router_id); + NEXT_TLV(hdr); + pkt_tlv = (struct babel_pkt_tlv_update *) hdr; + memset(hdr, 0, size); + size += sizeof(struct babel_pkt_tlv_router_id); + state->router_id = tlv->update.router_id; + state->router_id_seen = 1; + } + + hdr->type = BABEL_TLV_UPDATE; + hdr->length = sizeof(struct babel_pkt_tlv_update) - sizeof(struct babel_pkt_tlv_header) + len; + pkt_tlv->ae = BABEL_AE_IP6; + pkt_tlv->plen = tlv->update.plen; + put_u16(&pkt_tlv->interval, tlv->update.interval*BABEL_TIME_UNITS); + put_u16(&pkt_tlv->seqno, tlv->update.seqno); + put_u16(&pkt_tlv->metric, tlv->update.metric); + memcpy(pkt_tlv->addr, buf, len); + + return size; +} + +static int +babel_write_route_request(struct babel_pkt_tlv_header *hdr, union babel_tlv *tlv, + struct babel_write_state *state, int max_len) +{ + + struct babel_pkt_tlv_route_request * pkt_tlv = (struct babel_pkt_tlv_route_request *) hdr; + char buf[16] = {}; + u8 size, len = (tlv->route_request.plen + 7)/8; + size = sizeof(struct babel_pkt_tlv_route_request) + len; + if (max_len < size) + return 0; + + hdr->type = BABEL_TLV_ROUTE_REQUEST; + hdr->length = size - sizeof(struct babel_pkt_tlv_header); + + if (tlv->route_request.plen > 0) + { + pkt_tlv->ae = BABEL_AE_IP6; + pkt_tlv->plen = tlv->route_request.plen; + put_ipa(buf, tlv->route_request.prefix); + memcpy(pkt_tlv->addr, buf, len); + } + else + { + pkt_tlv->ae = BABEL_AE_WILDCARD; + } + + return size; +} + +static int +babel_write_seqno_request(struct babel_pkt_tlv_header *hdr, union babel_tlv *tlv, + struct babel_write_state *state, int max_len) +{ + + struct babel_pkt_tlv_seqno_request * pkt_tlv = (struct babel_pkt_tlv_seqno_request *) hdr; + char buf[16] = {}; + u8 size, len = (tlv->seqno_request.plen + 7)/8; + size = sizeof(struct babel_pkt_tlv_seqno_request) + len; + if (max_len < size) + return 0; + put_ipa(buf, tlv->seqno_request.prefix); + + hdr->type = BABEL_TLV_SEQNO_REQUEST; + hdr->length = size - sizeof(struct babel_pkt_tlv_header); + pkt_tlv->ae = BABEL_AE_IP6; + pkt_tlv->plen = tlv->seqno_request.plen; + put_u16(&pkt_tlv->seqno, tlv->seqno_request.seqno); + pkt_tlv->hop_count = tlv->seqno_request.hop_count; + put_u64(&pkt_tlv->router_id, tlv->seqno_request.router_id); + memcpy(pkt_tlv->addr, buf, len); + return size; +} + + +void +babel_init_packet(void *buf) +{ + struct babel_pkt_header *hdr = buf; + memset(hdr, 0, sizeof(struct babel_pkt_header)); + hdr->magic = BABEL_MAGIC; + hdr->version = BABEL_VERSION; +} + +static int +babel_send_to(struct babel_iface *ifa, ip_addr dest) +{ + sock *sk = ifa->sk; + struct babel_pkt_header *hdr = (void *) sk->tbuf; + int len = get_u16(&hdr->length)+sizeof(struct babel_pkt_header); + + DBG("Babel: Sending %d bytes to %I\n", len, dest); + return sk_send_to(sk, len, dest, 0); +} + +/** + * babel_write_queue - Write a TLV queue to a transmission buffer. + * @ifa: Interface holding the transmission buffer. + * @queue: TLV queue to write (containing internal-format TLVs). + * + * This function writes a packet to the interface transmission buffer with as + * many TLVs from the &queue as will fit in the buffer. It returns the number of + * bytes written (NOT counting the packet header). The function is called by + * babel_send_queue() and babel_send_unicast() to construct packets for + * transmission, and uses per-TLV helper functions to convert the + * internal-format TLVs to their wire representations. + * + * The TLVs in the queue are freed after they are written to the buffer. + */ +static int babel_write_queue(struct babel_iface *ifa, list queue) +{ + struct babel_proto *p = ifa->proto; + struct babel_pkt_header *dst = (void *)ifa->sk->tbuf; + struct babel_pkt_tlv_header *hdr; + struct babel_tlv_node *cur; + struct babel_write_state state = {}; + u16 written, len = 0; + + if (EMPTY_LIST(queue)) + return 0; + + babel_init_packet(dst); + hdr = FIRST_TLV(dst); + WALK_LIST_FIRST(cur, ifa->tlv_queue) { + if ((written = babel_write_tlv(hdr, &cur->tlv, &state, + ifa->max_pkt_len - ((byte *)hdr-(byte *)dst))) == 0) + break; + len += written; + hdr = (void *)((byte *) hdr + written); + rem_node(NODE cur); + sl_free(p->tlv_slab, cur); + } + put_u16(&dst->length, len); + return len; +} + +void +babel_send_queue(void *arg) +{ + struct babel_iface *ifa = arg; + while (babel_write_queue(ifa, ifa->tlv_queue) > 0 && + babel_send_to(ifa, IP6_BABEL_ROUTERS) > 0) ; +} + + +/** + * babel_send_unicast - send a single TLV via unicast to a destination. + * @tlv: TLV to send. + * @ifa: Interface to send via. + * @dest: Destination of the TLV. + * + * This function is used to send a single TLV via unicast to a designated + * receiver. This is used for replying to certain incoming requests, and for + * sending unicast requests to refresh routes before they expire. + */ +void +babel_send_unicast(union babel_tlv *tlv, struct babel_iface *ifa, ip_addr dest) +{ + list queue; + struct babel_proto *p = ifa->proto; + struct babel_tlv_node *tlvn = sl_alloc(p->tlv_slab); + init_list(&queue); + + tlvn->tlv = *tlv; + add_tail(&queue, NODE tlvn); + babel_write_queue(ifa, queue); + babel_send_to(ifa, dest); +} + + +/** + * babel_enqueue - enqueue a TLV for transmission on an interface. + * @tlv: TLV to enqueue (in internal TLV format). + * @ifa: Interface to enqueue to. + * + * This function is called to enqueue a TLV for subsequent transmission on an + * interface. The transmission event is triggered whenever a TLV is enqueued; + * this ensures that TLVs will be transmitted in a timely manner, but that TLVs + * which are enqueued in rapid succession can be transmitted together in one + * packet. + */ +void +babel_enqueue(union babel_tlv *tlv, struct babel_iface *ifa) +{ + struct babel_proto *p = ifa->proto; + struct babel_tlv_node *tlvn = sl_alloc(p->tlv_slab); + tlvn->tlv = *tlv; + add_tail(&ifa->tlv_queue, NODE tlvn); + + /* Only schedule send if there's not already data in the socket buffer. + Otherwise we may overwrite the data already in the buffer. */ + if(ifa->sk->tbuf == ifa->sk->tpos) + ev_schedule(ifa->send_event); +} + + + +/** + * babel_process_packet - process incoming data packet. + * @pkt: Pointer to the packet data. + * @size: Size of received packet. + * @saddr: Address of packet sender. + * @ifa: Interface packet was received on. + * + * This function is the main processing hook of incoming Babel packets. It + * checks that the packet header is well-formed, then processes the TLVs + * contained in the packet. This is done in two passes: First all TLVs are + * parsed into the internal TLV format. If a TLV parser fails, processing of the + * rest of the packet is aborted. + * + * After the parsing step, the TLV handlers are called for each parsed TLV in + * order. + */ +void +babel_process_packet(struct babel_pkt_header *pkt, int size, + ip_addr saddr, struct babel_iface *ifa) +{ + struct babel_pkt_tlv_header *tlv = FIRST_TLV(pkt); + struct babel_proto *proto = ifa->proto; + struct babel_parse_state state = { + .proto = proto, + .ifa = ifa, + .saddr = saddr, + .next_hop = saddr, + }; + byte *ptr = (byte *)tlv; + u16 len = get_u16(&pkt->length); + struct babel_tlv_node *cur; + enum parse_result res; + list tlvs; + init_list(&tlvs); + + if (pkt->magic != BABEL_MAGIC + || pkt->version != BABEL_VERSION + || len + sizeof(struct babel_pkt_header) > size) + { + log(L_ERR "Babel: Invalid packet: magic %d version %d length %d size %d\n", + pkt->magic, pkt->version, pkt->length, size); + return; + } + + + /* First pass through the packet TLV by TLV, parsing each into internal data + structures. */ + for (cur = sl_alloc(proto->tlv_slab); + (byte *)tlv < ptr + len; + NEXT_TLV(tlv)) + { + if ((byte *)tlv + tlv->length > ptr + len) { + log(L_ERR "Babel: Framing error: TLV type %d length %d exceeds end of packet\n", + tlv->type, tlv->length); + sl_free(proto->tlv_slab, cur); + break; + } + + if ((res = babel_read_tlv(tlv, &cur->tlv, &state)) == PARSE_SUCCESS) + { + cur->tlv.type = tlv->type; + add_tail(&tlvs, NODE cur); + cur = sl_alloc(proto->tlv_slab); + } + else if (res == PARSE_IGNORE) + { + DBG("Babel: Ignoring TLV of type %d\n",tlv->type); + } + else + { + DBG("Babel: TLV read error for type %d\n",tlv->type); + sl_free(proto->tlv_slab, cur); + break; + } + } + + /* Parsing done, handle all parsed TLVs */ + WALK_LIST_FIRST(cur, tlvs) { + if (tlv_data[cur->tlv.type].handle_tlv != NULL) + tlv_data[cur->tlv.type].handle_tlv(&cur->tlv, ifa); + rem_node(NODE cur); + sl_free(proto->tlv_slab, cur); + } +} + +static void +babel_err_hook(sock *sk, int err) +{ + struct babel_iface *ifa = sk->data; + struct babel_proto *p = ifa->proto; + + log(L_ERR "%s: Socket error on %s: %M", p->p.name, ifa->iface->name, err); + /* FIXME: Drop queued TLVs here? */ +} + + +static void +babel_tx_hook(sock *sk) +{ + struct babel_iface *ifa = sk->data; + + DBG("Babel: TX hook called (iface %s, src %I, dst %I)\n", + sk->iface->name, sk->saddr, sk->daddr); + + babel_send_queue(ifa); +} + + +static int +babel_rx_hook(sock *sk, int size) +{ + struct babel_iface *ifa = sk->data; + struct babel_proto *p = ifa->proto; + if (!ifa->iface || sk->lifindex != ifa->iface->index) + return 1; + + TRACE(D_PACKETS, "Incoming packet: %d bytes from %I port %d via %s", + size, sk->faddr, sk->fport, ifa->iface->name); + if (size < sizeof(struct babel_pkt_header)) BAD("Too small packet"); + + if (ipa_equal(ifa->iface->addr->ip, sk->faddr)) + { + DBG("Babel: My own packet\n"); + return 1; + } + + if (!ipa_is_link_local(sk->faddr)) { BAD("Non-link local sender"); } + + if (sk->fport != ifa->cf->port) { BAD("Packet received on wrong port"); } + + babel_process_packet((struct babel_pkt_header *) sk->rbuf, size, sk->faddr, ifa); + return 1; +} + +int +babel_open_socket(struct babel_iface *ifa) +{ + struct babel_proto *p = ifa->proto; + + sock *sk; + sk = sk_new(ifa->pool); + sk->type = SK_UDP; + sk->sport = ifa->cf->port; + sk->dport = ifa->cf->port; + sk->iface = ifa->iface; + + sk->daddr = IP6_BABEL_ROUTERS; + + sk->rx_hook = babel_rx_hook; + sk->tx_hook = babel_tx_hook; + sk->err_hook = babel_err_hook; + sk->data = ifa; + + + sk->tos = ifa->cf->tx_tos; + sk->priority = ifa->cf->tx_priority; + sk->flags = SKF_LADDR_RX; + + if (sk_open(sk) < 0) + goto err; + if (sk_setup_multicast(sk) < 0) + goto err; + if (sk_join_group(sk, sk->daddr) < 0) + goto err; + + TRACE(D_EVENTS, "Listening on %s, port %d, mode multicast (%I)", + ifa->iface->name, ifa->cf->port, sk->daddr); + + ifa->sk = sk; + + return 1; + + err: + sk_log_error(sk, p->p.name); + rfree(sk); + return 0; + +} diff --git a/proto/babel/packet.h b/proto/babel/packet.h new file mode 100644 index 0000000..bcd193a --- /dev/null +++ b/proto/babel/packet.h @@ -0,0 +1,127 @@ +/* -*- c-file-style: "gnu"; indent-tabs-mode: nil; -*- + * + * The Babel protocol + * + * Copyright (c) 2015-2016 Toke Høiland-Jørgensen + * + * Can be freely distributed and used under the terms of the GNU GPL. + * + * This file contains the on-wire data structures (i.e. TLVs and packet + * format) used by the Babel protocol. + */ + +struct babel_parse_state { + struct babel_proto *proto; + struct babel_iface *ifa; + ip_addr saddr; + u64 router_id; + /* A router_id may be 0, so we need a separate variable to track whether we + have seen a router_id */ + u8 router_id_seen; + ip_addr prefix; + ip_addr next_hop; +}; + +enum parse_result { + PARSE_SUCCESS, + PARSE_ERROR, + PARSE_IGNORE, +}; + +struct babel_write_state { + u64 router_id; + u8 router_id_seen; + ip_addr next_hop; +}; + + +struct babel_pkt_tlv_header { + u8 type; + u8 length; +}; + +struct babel_pkt_tlv_ack_req { + struct babel_pkt_tlv_header header; + u16 reserved; + u16 nonce; + u16 interval; +}; + +struct babel_pkt_tlv_ack { + struct babel_pkt_tlv_header header; + u16 nonce; +}; + +struct babel_pkt_tlv_hello { + struct babel_pkt_tlv_header header; + u16 reserved; + u16 seqno; + u16 interval; +}; + +struct babel_pkt_tlv_ihu { + struct babel_pkt_tlv_header header; + u8 ae; + u8 reserved; + u16 rxcost; + u16 interval; + u8 addr[0]; +} __attribute__((packed)); + +struct babel_pkt_tlv_router_id { + struct babel_pkt_tlv_header header; + u16 reserved; + u64 router_id; +} __attribute__((packed)); + +struct babel_pkt_tlv_next_hop { + struct babel_pkt_tlv_header header; + u8 ae; + u8 reserved; + u8 addr[0]; +} __attribute__((packed)); + +struct babel_pkt_tlv_update { + struct babel_pkt_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; + u8 addr[0]; +} __attribute__((packed)); + +struct babel_pkt_tlv_route_request { + struct babel_pkt_tlv_header header; + u8 ae; + u8 plen; + u8 addr[0]; +} __attribute__((packed)); + +struct babel_pkt_tlv_seqno_request { + struct babel_pkt_tlv_header header; + u8 ae; + u8 plen; + u16 seqno; + u8 hop_count; + u8 reserved; + u64 router_id; + u8 addr[0]; +} __attribute__((packed)); + +union babel_pkt_tlv { + struct babel_pkt_tlv_header header; + struct babel_pkt_tlv_ack_req ack_req; + struct babel_pkt_tlv_ack ack; + struct babel_pkt_tlv_hello hello; + struct babel_pkt_tlv_ihu ihu; + struct babel_pkt_tlv_router_id router_id; + struct babel_pkt_tlv_next_hop next_hop; + struct babel_pkt_tlv_update update; + struct babel_pkt_tlv_route_request route_request; + struct babel_pkt_tlv_seqno_request seqno_request; +}; 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.8.0