[PATCH v2 2/2] Add the Babel protocol.
Toke Høiland-Jørgensen
toke at toke.dk
Thu Jan 14 23:24:59 CET 2016
This adds the Babel routing protocol (RFC6126) to Bird.
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>
---
configure.in | 3 +
doc/bird.sgml | 91 +++
lib/bitops.h | 3 +-
lib/ip.h | 3 +
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 | 1905 ++++++++++++++++++++++++++++++++++++++++++++++++++
proto/babel/babel.h | 348 +++++++++
proto/babel/config.Y | 127 ++++
proto/babel/packet.c | 863 +++++++++++++++++++++++
proto/babel/packet.h | 127 ++++
sysdep/autoconf.h.in | 1 +
16 files changed, 3492 insertions(+), 3 deletions(-)
create mode 100644 proto/babel/Doc
create mode 100644 proto/babel/Makefile
create mode 100644 proto/babel/babel.c
create mode 100644 proto/babel/babel.h
create mode 100644 proto/babel/config.Y
create mode 100644 proto/babel/packet.c
create mode 100644 proto/babel/packet.h
diff --git a/configure.in b/configure.in
index c81709e..1265565 100644
--- a/configure.in
+++ b/configure.in
@@ -206,6 +206,9 @@ fi
AC_SUBST(iproutedir)
all_protocols="$proto_bfd bgp ospf pipe $proto_radv rip static"
+if test "$ip" = ipv6 ; then
+ all_protocols="$all_protocols babel"
+fi
all_protocols=`echo $all_protocols | sed 's/ /,/g'`
if test "$with_protocols" = all ; then
diff --git a/doc/bird.sgml b/doc/bird.sgml
index 86df045..24e3b94 100644
--- a/doc/bird.sgml
+++ b/doc/bird.sgml
@@ -1365,6 +1365,97 @@ 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: 20 seconds for wired interfaces, 4 seconds for wireless.
+
+ <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 RIP 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.
+
+ <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.
+
+ <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..997556e 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..8f46fd4
--- /dev/null
+++ b/proto/babel/babel.c
@@ -0,0 +1,1905 @@
+/* -*- c-file-style: "gnu"; indent-tabs-mode: nil; -*-
+ *
+ * The Babel protocol
+ *
+ * Copyright (c) 2015 Toke Høiland-Jørgensen
+ *
+ * Can be freely distributed and used under the terms of the GNU GPL.
+ *
+ * This file contains the main routines for handling and sending TLVs, as
+ * well as timers and interaction with the nest.
+ */
+
+/**
+ * DOC: The Babel protocol
+ *
+ * Babel (RFC6126) is a loop-avoiding distance-vector routing protocol that is
+ * robust and efficient both in ordinary wired networks and in wireless mesh
+ * networks.
+ *
+ * The Babel protocol keeps state for each neighbour in a &babel_neighbor
+ * struct, tracking received hellos and I Heard You (IHU) messages. A
+ * &babel_interface struct keeps hello and update 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; }
+
+/* Is one number larger than another mod 65535? Since diff_mod64k is always >=
+ 0, just use a simple cutoff value to determine if the difference is small
+ enough that one is really larger. Since these comparisons are only made for
+ values that should not differ by more than a few numbers, this should be
+ safe. */
+static inline u16 ge_mod64k(u16 a, u16 b)
+{
+ return ((u16) a-b) < 0xfff0;
+}
+
+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_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 (!r->neigh || 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)
+ && r->neigh /* prevent propagating out own routes back to core */
+ && babel_is_feasible(babel_find_source(e, r->router_id),
+ r->seqno, r->advert_metric))
+ cur = r;
+
+ if (cur && cur->neigh && ((!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;
+}
+
+/* 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) {
+
+ if (!ifa->up)
+ continue;
+
+ /* already triggered */
+ if (ifa->want_triggered)
+ continue;
+
+ ifa->want_triggered = now;
+ babel_iface_kick_timer(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 && r->neigh
+ && !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
+ {
+ e->updated = now;
+ ifa->want_triggered = 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))
+ {
+ e->updated = now;
+ ifa->want_triggered = 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.
+ */
+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 ?: ifa->iface->mtu;
+ uint tbsize = ifa->cf->tx_length ?: 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, p->interfaces)
+ {
+ 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;
+
+ 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 (!r->neigh)
+ {
+ 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;
+ }
+ }
+ else
+ {
+ TRACE(D_EVENTS, "Lost route from nest: %I/%d", net->n.prefix, net->n.pxlen);
+ /* route has gone away; send retraction */
+ e = babel_find_entry(p, net->n.prefix, net->n.pxlen);
+ if (e && e->selected_out && !e->selected_out->neigh)
+ {
+ /* no neighbour, so our route */
+ e->selected_out->metric = BABEL_INFINITY;
+ e->selected_out->expires = now + BABEL_HOLD_TIME;
+ e->updated = now;
+ }
+ }
+ 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..9a4bab4
--- /dev/null
+++ b/proto/babel/babel.h
@@ -0,0 +1,348 @@
+/* -*- c-file-style: "gnu"; indent-tabs-mode: nil; -*-
+ *
+ * The Babel protocol
+ *
+ * Copyright (c) 2015 Toke Høiland-Jørgensen
+ *
+ * Can be freely distributed and used under the terms of the GNU GPL.
+ *
+ * This file contains the data structures used by Babel.
+ */
+
+#include "nest/bird.h"
+#include "nest/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 20
+#define BABEL_HELLO_INTERVAL_WIRELESS 4
+#define BABEL_UPDATE_INTERVAL_FACTOR 4
+#define BABEL_IHU_INTERVAL_FACTOR 3
+#define BABEL_HELLO_EXPIRY_FACTOR 1.5
+#define BABEL_ROUTE_EXPIRY_FACTOR 3.5
+#define BABEL_ROUTE_REFRESH_INTERVAL 2 /* seconds before route expiry to send route request */
+#define BABEL_HOLD_TIME 10 /* expiry time for our own routes */
+#define BABEL_RXCOST_WIRED 96
+#define BABEL_RXCOST_WIRELESS 256
+#define BABEL_INITIAL_HOP_COUNT 255
+#define BABEL_MAX_SEND_INTERVAL 5
+#define BABEL_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))
+
+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..fb0cf8c
--- /dev/null
+++ b/proto/babel/config.Y
@@ -0,0 +1,127 @@
+/*
+ * BIRD -- Babel Configuration
+ *
+ * Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+
+
+CF_HDR
+
+#include "proto/babel/babel.h"
+#include "nest/iface.h"
+
+CF_DEFINES
+
+#define BABEL_CFG ((struct babel_config *) this_proto)
+#define BABEL_IFACE ((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..e6f33eb
--- /dev/null
+++ b/proto/babel/packet.c
@@ -0,0 +1,863 @@
+/** -*- c-file-style: "gnu"; indent-tabs-mode: nil; -*-
+ *
+ * The Babel protocol
+ *
+ * Copyright (c) 2015 Toke Høiland-Jørgensen
+ *
+ * Can be freely distributed and used under the terms of the GNU GPL.
+ *
+ * This files contains the packet and TLV handling routines for the protocol.
+ */
+
+#undef LOCAL_DEBUG
+#define LOCAL_DEBUG 1
+
+#include "babel.h"
+#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 ip_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, ip_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);
+ }
+ 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_ipa(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_ipa(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_ipa(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);
+ 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..17b29bf
--- /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 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.6.4
More information about the Bird-users
mailing list