[PATCH v3 2/2] Add the Babel routing protocol (RFC6126).
Toke Høiland-Jørgensen
toke at toke.dk
Mon Apr 4 19:13:31 CEST 2016
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 at 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
More information about the Bird-users
mailing list