summaryrefslogtreecommitdiff
path: root/babeld
diff options
context:
space:
mode:
authorAvneesh Sachdev <avneesh@opensourcerouting.org>2012-04-09 00:25:15 -0700
committerAvneesh Sachdev <avneesh@opensourcerouting.org>2012-04-09 00:25:15 -0700
commit3cf6c2b4e43f44a977d218c96c26250654ae333e (patch)
treee017cde2015fbf3ef6c250327428d7c6152aa8f7 /babeld
parent01d7ff0a2166a422c56bd26f04fc22832a9e690b (diff)
parente96b312150d8e376c1ef463793d1929eca3618d5 (diff)
Merge branch 'quagga' into google-bgp-multipath
Conflicts: bgpd/bgp_route.c
Diffstat (limited to 'babeld')
-rw-r--r--babeld/.gitignore7
-rw-r--r--babeld/LICENCE36
-rw-r--r--babeld/Makefile.am29
-rw-r--r--babeld/babel_filter.c124
-rw-r--r--babeld/babel_filter.h49
-rw-r--r--babeld/babel_interface.c1022
-rw-r--r--babeld/babel_interface.h152
-rw-r--r--babeld/babel_main.c532
-rw-r--r--babeld/babel_main.h57
-rw-r--r--babeld/babel_zebra.c378
-rw-r--r--babeld/babel_zebra.h50
-rw-r--r--babeld/babeld.c728
-rw-r--r--babeld/babeld.conf.sample30
-rw-r--r--babeld/babeld.h141
-rw-r--r--babeld/kernel.c76
-rw-r--r--babeld/kernel.h69
-rw-r--r--babeld/kernel_zebra.c275
-rw-r--r--babeld/message.c1561
-rw-r--r--babeld/message.h111
-rw-r--r--babeld/neighbour.c343
-rw-r--r--babeld/neighbour.h66
-rw-r--r--babeld/net.c239
-rw-r--r--babeld/net.h44
-rw-r--r--babeld/resend.c330
-rw-r--r--babeld/resend.h77
-rw-r--r--babeld/route.c1019
-rw-r--r--babeld/route.h135
-rw-r--r--babeld/source.c180
-rw-r--r--babeld/source.h67
-rw-r--r--babeld/util.c445
-rw-r--r--babeld/util.h165
-rw-r--r--babeld/xroute.c237
-rw-r--r--babeld/xroute.h59
33 files changed, 8833 insertions, 0 deletions
diff --git a/babeld/.gitignore b/babeld/.gitignore
new file mode 100644
index 00000000..8384763a
--- /dev/null
+++ b/babeld/.gitignore
@@ -0,0 +1,7 @@
+*
+!*.c
+!*.h
+!LICENCE
+!Makefile.am
+!babeld.conf.sample
+!.gitignore \ No newline at end of file
diff --git a/babeld/LICENCE b/babeld/LICENCE
new file mode 100644
index 00000000..9da569dc
--- /dev/null
+++ b/babeld/LICENCE
@@ -0,0 +1,36 @@
+Code in this directory is made available under the following licence:
+
+ ---------------------------------------------------------------------------
+ Copyright (c) 2007, 2008 by Juliusz Chroboczek
+
+ Permission is hereby granted, free of charge, to any person obtaining a copy
+ of this software and associated documentation files (the "Software"), to deal
+ in the Software without restriction, including without limitation the rights
+ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ copies of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+
+ The above copyright notice and this permission notice shall be included in
+ all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ THE SOFTWARE.
+ ---------------------------------------------------------------------------
+
+The code also makes calls to and links with the "libzebra" code of Quagga,
+in the lib/ directory of this project, which is subject to the GPL licence
+as given in the top-level COPYING file included with Quagga.
+
+Contributors to the code in babeld/ are asked to make their work available
+under the same MIT/X11 licence as given immediately above. Please indicate
+your assent to this by updating this file and appending the appropriate
+
+ Copyright <year> <Author name>, <author contact details>
+
+line to the existing copyright assertion lines in the MIT/X11 licence text
+above in this file.
diff --git a/babeld/Makefile.am b/babeld/Makefile.am
new file mode 100644
index 00000000..468b5a5f
--- /dev/null
+++ b/babeld/Makefile.am
@@ -0,0 +1,29 @@
+## Process this file with automake to produce Makefile.in.
+
+INCLUDES = @INCLUDES@ -I.. -I$(top_srcdir) -I$(top_srcdir)/lib @SNMP_INCLUDES@
+DEFS = @DEFS@ -DSYSCONFDIR=\"$(sysconfdir)/\"
+INSTALL_SDATA=@INSTALL@ -m 600
+
+AM_CFLAGS = $(PICFLAGS)
+AM_LDFLAGS = $(PILDFLAGS)
+
+noinst_LIBRARIES = libbabel.a
+sbin_PROGRAMS = babeld
+
+libbabel_a_SOURCES = \
+ babel_zebra.c net.c kernel.c util.c source.c neighbour.c \
+ route.c xroute.c message.c resend.c babel_interface.c babeld.c \
+ babel_filter.c
+
+noinst_HEADERS = \
+ babel_zebra.h net.h kernel.h util.h source.h neighbour.h \
+ route.h xroute.h message.h resend.h babel_interface.h babeld.h \
+ babel_filter.h
+
+babeld_SOURCES = \
+ babel_main.c $(libbabel_a_SOURCES)
+
+babeld_LDADD = ../lib/libzebra.la @LIBCAP@
+
+examplesdir = $(exampledir)
+dist_examples_DATA = babeld.conf.sample
diff --git a/babeld/babel_filter.c b/babeld/babel_filter.c
new file mode 100644
index 00000000..191a9f77
--- /dev/null
+++ b/babeld/babel_filter.c
@@ -0,0 +1,124 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+
+Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include "babel_filter.h"
+#include "vty.h"
+#include "filter.h"
+#include "log.h"
+#include "plist.h"
+#include "distribute.h"
+#include "util.h"
+
+int
+babel_filter(int output, const unsigned char *prefix, unsigned short plen,
+ unsigned int ifindex)
+{
+ struct interface *ifp = if_lookup_by_index(ifindex);
+ babel_interface_nfo *babel_ifp = ifp ? babel_get_if_nfo(ifp) : NULL;
+ struct prefix p;
+ struct distribute *dist;
+ struct access_list *alist;
+ struct prefix_list *plist;
+ int filter = output ? BABEL_FILTER_OUT : BABEL_FILTER_IN;
+ int distribute = output ? DISTRIBUTE_OUT : DISTRIBUTE_IN;
+
+ p.family = v4mapped(prefix) ? AF_INET : AF_INET6;
+ p.prefixlen = v4mapped(prefix) ? plen - 96 : plen;
+ if (p.family == AF_INET)
+ uchar_to_inaddr(&p.u.prefix4, prefix);
+ else
+ uchar_to_in6addr(&p.u.prefix6, prefix);
+
+ if (babel_ifp != NULL && babel_ifp->list[filter]) {
+ if (access_list_apply (babel_ifp->list[filter], &p)
+ == FILTER_DENY) {
+ debugf(BABEL_DEBUG_FILTER,
+ "%s/%d filtered by distribute in",
+ p.family == AF_INET ?
+ inet_ntoa(p.u.prefix4) :
+ inet6_ntoa (p.u.prefix6),
+ p.prefixlen);
+ return INFINITY;
+ }
+ }
+ if (babel_ifp != NULL && babel_ifp->prefix[filter]) {
+ if (prefix_list_apply (babel_ifp->prefix[filter], &p)
+ == PREFIX_DENY) {
+ debugf(BABEL_DEBUG_FILTER, "%s/%d filtered by distribute in",
+ p.family == AF_INET ?
+ inet_ntoa(p.u.prefix4) :
+ inet6_ntoa (p.u.prefix6),
+ p.prefixlen);
+ return INFINITY;
+ }
+ }
+
+ /* All interface filter check. */
+ dist = distribute_lookup (NULL);
+ if (dist) {
+ if (dist->list[distribute]) {
+ alist = access_list_lookup (AFI_IP6, dist->list[distribute]);
+
+ if (alist) {
+ if (access_list_apply (alist, &p) == FILTER_DENY) {
+ debugf(BABEL_DEBUG_FILTER, "%s/%d filtered by distribute in",
+ p.family == AF_INET ?
+ inet_ntoa(p.u.prefix4) :
+ inet6_ntoa (p.u.prefix6),
+ p.prefixlen);
+ return INFINITY;
+ }
+ }
+ }
+ if (dist->prefix[distribute]) {
+ plist = prefix_list_lookup (AFI_IP6, dist->prefix[distribute]);
+ if (plist) {
+ if (prefix_list_apply (plist, &p) == PREFIX_DENY) {
+ debugf(BABEL_DEBUG_FILTER, "%s/%d filtered by distribute in",
+ p.family == AF_INET ?
+ inet_ntoa(p.u.prefix4) :
+ inet6_ntoa (p.u.prefix6),
+ p.prefixlen);
+ return INFINITY;
+ }
+ }
+ }
+ }
+ return 0;
+}
diff --git a/babeld/babel_filter.h b/babeld/babel_filter.h
new file mode 100644
index 00000000..73722e0a
--- /dev/null
+++ b/babeld/babel_filter.h
@@ -0,0 +1,49 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#ifndef BABELD_BABEL_FILTER_H
+#define BABELD_BABEL_FILTER_H
+
+#include <zebra.h>
+#include "prefix.h"
+#include "babel_interface.h"
+
+int babel_filter(int output, const unsigned char *prefix, unsigned short plen,
+ unsigned int index);
+
+#endif /* BABELD_BABEL_FILTER_H */
diff --git a/babeld/babel_interface.c b/babeld/babel_interface.c
new file mode 100644
index 00000000..ace28127
--- /dev/null
+++ b/babeld/babel_interface.c
@@ -0,0 +1,1022 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+
+Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include <zebra.h>
+#include "memory.h"
+#include "log.h"
+#include "command.h"
+#include "prefix.h"
+#include "vector.h"
+#include "distribute.h"
+
+#include "babel_main.h"
+#include "util.h"
+#include "kernel.h"
+#include "babel_interface.h"
+#include "message.h"
+#include "route.h"
+#include "babel_zebra.h"
+#include "neighbour.h"
+#include "route.h"
+#include "xroute.h"
+
+
+#define IS_ENABLE(ifp) (babel_enable_if_lookup(ifp->name) >= 0)
+
+static int babel_enable_if_lookup (const char *ifname);
+static int babel_enable_if_add (const char *ifname);
+static int babel_enable_if_delete (const char *ifname);
+static int interface_recalculate(struct interface *ifp);
+static int interface_reset(struct interface *ifp);
+static int babel_if_new_hook (struct interface *ifp);
+static int babel_if_delete_hook (struct interface *ifp);
+static int interface_config_write (struct vty *vty);
+static babel_interface_nfo * babel_interface_allocate (void);
+static void babel_interface_free (babel_interface_nfo *bi);
+
+
+static vector babel_enable_if; /* enable interfaces (by cmd). */
+static struct cmd_node babel_interface_node = /* babeld's interface node. */
+{
+ INTERFACE_NODE,
+ "%s(config-if)# ",
+ 1 /* VTYSH */
+};
+
+
+int
+babel_interface_up (int cmd, struct zclient *client, zebra_size_t length)
+{
+ struct stream *s = NULL;
+ struct interface *ifp = NULL;
+
+ debugf(BABEL_DEBUG_IF, "receive a 'interface up'");
+
+ s = zclient->ibuf;
+ ifp = zebra_interface_state_read(s); /* it updates iflist */
+
+ if (ifp == NULL) {
+ return 0;
+ }
+
+ interface_recalculate(ifp);
+ return 0;
+}
+
+int
+babel_interface_down (int cmd, struct zclient *client, zebra_size_t length)
+{
+ struct stream *s = NULL;
+ struct interface *ifp = NULL;
+
+ debugf(BABEL_DEBUG_IF, "receive a 'interface down'");
+
+ s = zclient->ibuf;
+ ifp = zebra_interface_state_read(s); /* it updates iflist */
+
+ if (ifp == NULL) {
+ return 0;
+ }
+
+ interface_reset(ifp);
+ return 0;
+}
+
+int
+babel_interface_add (int cmd, struct zclient *client, zebra_size_t length)
+{
+ struct interface *ifp = NULL;
+
+ debugf(BABEL_DEBUG_IF, "receive a 'interface add'");
+
+ /* read and add the interface in the iflist. */
+ ifp = zebra_interface_add_read (zclient->ibuf);
+
+ if (ifp == NULL) {
+ return 0;
+ }
+
+ interface_recalculate(ifp);
+ return 0;
+}
+
+int
+babel_interface_delete (int cmd, struct zclient *client, zebra_size_t length)
+{
+ struct interface *ifp;
+ struct stream *s;
+
+ debugf(BABEL_DEBUG_IF, "receive a 'interface delete'");
+
+ s = zclient->ibuf;
+ ifp = zebra_interface_state_read(s); /* it updates iflist */
+
+ if (ifp == NULL)
+ return 0;
+
+ if (IS_ENABLE(ifp))
+ interface_reset(ifp);
+
+ /* To support pseudo interface do not free interface structure. */
+ /* if_delete(ifp); */
+ ifp->ifindex = IFINDEX_INTERNAL;
+
+ return 0;
+}
+
+int
+babel_interface_address_add (int cmd, struct zclient *client,
+ zebra_size_t length)
+{
+ babel_interface_nfo *babel_ifp;
+ struct connected *ifc;
+ struct prefix *prefix;
+
+ debugf(BABEL_DEBUG_IF, "receive a 'interface address add'");
+
+ ifc = zebra_interface_address_read (ZEBRA_INTERFACE_ADDRESS_ADD,
+ zclient->ibuf);
+
+ if (ifc == NULL)
+ return 0;
+
+ prefix = ifc->address;
+
+ if (prefix->family == AF_INET) {
+ flush_interface_routes(ifc->ifp, 0);
+ babel_ifp = babel_get_if_nfo(ifc->ifp);
+ if (babel_ifp->ipv4 == NULL) {
+ babel_ifp->ipv4 = malloc(4);
+ if (babel_ifp->ipv4 == NULL) {
+ zlog_err("not einough memory");
+ } else {
+ memcpy(babel_ifp->ipv4, &prefix->u.prefix4, 4);
+ }
+ }
+ }
+
+ send_request(ifc->ifp, NULL, 0);
+ send_update(ifc->ifp, 0, NULL, 0);
+
+ return 0;
+}
+
+int
+babel_interface_address_delete (int cmd, struct zclient *client,
+ zebra_size_t length)
+{
+ babel_interface_nfo *babel_ifp;
+ struct connected *ifc;
+ struct prefix *prefix;
+
+ debugf(BABEL_DEBUG_IF, "receive a 'interface address add'");
+
+ ifc = zebra_interface_address_read (ZEBRA_INTERFACE_ADDRESS_ADD,
+ zclient->ibuf);
+
+ if (ifc == NULL)
+ return 0;
+
+ prefix = ifc->address;
+
+ if (prefix->family == AF_INET) {
+ flush_interface_routes(ifc->ifp, 0);
+ babel_ifp = babel_get_if_nfo(ifc->ifp);
+ if (babel_ifp->ipv4 != NULL
+ && memcmp(babel_ifp->ipv4, &prefix->u.prefix4, 4) == 0) {
+ free(babel_ifp->ipv4);
+ babel_ifp->ipv4 = NULL;
+ }
+ }
+
+ send_request(ifc->ifp, NULL, 0);
+ send_update(ifc->ifp, 0, NULL, 0);
+
+ return 0;
+}
+
+/* Lookup function. */
+static int
+babel_enable_if_lookup (const char *ifname)
+{
+ unsigned int i;
+ char *str;
+
+ for (i = 0; i < vector_active (babel_enable_if); i++)
+ if ((str = vector_slot (babel_enable_if, i)) != NULL)
+ if (strcmp (str, ifname) == 0)
+ return i;
+ return -1;
+}
+
+/* Add interface to babel_enable_if. */
+static int
+babel_enable_if_add (const char *ifname)
+{
+ int ret;
+ struct interface *ifp = NULL;
+
+ ret = babel_enable_if_lookup (ifname);
+ if (ret >= 0)
+ return -1;
+
+ vector_set (babel_enable_if, strdup (ifname));
+
+ ifp = if_lookup_by_name(ifname);
+ if (ifp != NULL)
+ interface_recalculate(ifp);
+
+ return 1;
+}
+
+/* Delete interface from babel_enable_if. */
+static int
+babel_enable_if_delete (const char *ifname)
+{
+ int babel_enable_if_index;
+ char *str;
+ struct interface *ifp = NULL;
+
+ babel_enable_if_index = babel_enable_if_lookup (ifname);
+ if (babel_enable_if_index < 0)
+ return -1;
+
+ str = vector_slot (babel_enable_if, babel_enable_if_index);
+ free (str);
+ vector_unset (babel_enable_if, babel_enable_if_index);
+
+ ifp = if_lookup_by_name(ifname);
+ if (ifp != NULL)
+ interface_reset(ifp);
+
+ return 1;
+}
+
+/* [Babel Command] Babel enable on specified interface or matched network. */
+DEFUN (babel_network,
+ babel_network_cmd,
+ "network IF_OR_ADDR",
+ "Enable Babel protocol on specified interface or network.\n"
+ "Interface or address")
+{
+ int ret;
+ struct prefix p;
+
+ ret = str2prefix (argv[0], &p);
+
+ /* Given string is: */
+ if (ret) /* an IPv4 or v6 network */
+ return CMD_ERR_NO_MATCH; /* not implemented yet */
+ else /* an interface name */
+ ret = babel_enable_if_add (argv[0]);
+
+ if (ret < 0) {
+ vty_out (vty, "There is same network configuration %s%s", argv[0],
+ VTY_NEWLINE);
+ return CMD_WARNING;
+ }
+
+ return CMD_SUCCESS;
+}
+
+/* [Babel Command] Babel enable on specified interface or matched network. */
+DEFUN (no_babel_network,
+ no_babel_network_cmd,
+ "no network IF_OR_ADDR",
+ NO_STR
+ "Disable Babel protocol on specified interface or network.\n"
+ "Interface or address")
+{
+ int ret;
+ struct prefix p;
+
+ ret = str2prefix (argv[0], &p);
+
+ /* Given string is: */
+ if (ret) /* an IPv4 or v6 network */
+ return CMD_ERR_NO_MATCH; /* not implemented yet */
+ else /* an interface name */
+ ret = babel_enable_if_delete (argv[0]);
+
+ if (ret < 0) {
+ vty_out (vty, "can't find network %s%s", argv[0],
+ VTY_NEWLINE);
+ return CMD_WARNING;
+ }
+
+ return CMD_SUCCESS;
+}
+
+/* There are a number of interface parameters that must be changed when
+ an interface becomes wired/wireless. In Quagga, they cannot be
+ configured separately. */
+
+static void
+babel_set_wired_internal(babel_interface_nfo *babel_ifp, int wired)
+{
+ if(wired) {
+ babel_ifp->flags |= BABEL_IF_WIRED;
+ babel_ifp->cost = 96;
+ babel_ifp->flags &= ~BABEL_IF_LQ;
+ } else {
+ babel_ifp->flags &= ~BABEL_IF_WIRED;
+ babel_ifp->cost = 256;
+ babel_ifp->flags |= BABEL_IF_LQ;
+ }
+
+}
+
+/* [Interface Command] Tell the interface is wire. */
+DEFUN (babel_set_wired,
+ babel_set_wired_cmd,
+ "babel wired",
+ "Babel interface commands\n"
+ "Enable wired optimisations")
+{
+ struct interface *ifp;
+ babel_interface_nfo *babel_ifp;
+
+ ifp = vty->index;
+ babel_ifp = babel_get_if_nfo(ifp);
+
+ assert (babel_ifp != NULL);
+ babel_set_wired_internal(babel_ifp, 1);
+ return CMD_SUCCESS;
+}
+
+/* [Interface Command] Tell the interface is wireless (default). */
+DEFUN (babel_set_wireless,
+ babel_set_wireless_cmd,
+ "babel wireless",
+ "Babel interface commands\n"
+ "Disable wired optimiations (assume wireless)")
+{
+ struct interface *ifp;
+ babel_interface_nfo *babel_ifp;
+
+ ifp = vty->index;
+ babel_ifp = babel_get_if_nfo(ifp);
+
+ assert (babel_ifp != NULL);
+ babel_set_wired_internal(babel_ifp, 0);
+ return CMD_SUCCESS;
+}
+
+/* [Interface Command] Enable split horizon. */
+DEFUN (babel_split_horizon,
+ babel_split_horizon_cmd,
+ "babel split-horizon",
+ "Babel interface commands\n"
+ "Enable split horizon processing")
+{
+ struct interface *ifp;
+ babel_interface_nfo *babel_ifp;
+
+ ifp = vty->index;
+ babel_ifp = babel_get_if_nfo(ifp);
+
+ assert (babel_ifp != NULL);
+ babel_ifp->flags |= BABEL_IF_SPLIT_HORIZON;
+ return CMD_SUCCESS;
+}
+
+/* [Interface Command] Disable split horizon (default). */
+DEFUN (no_babel_split_horizon,
+ no_babel_split_horizon_cmd,
+ "no babel split-horizon",
+ NO_STR
+ "Babel interface commands\n"
+ "Disable split horizon processing")
+{
+ struct interface *ifp;
+ babel_interface_nfo *babel_ifp;
+
+ ifp = vty->index;
+ babel_ifp = babel_get_if_nfo(ifp);
+
+ assert (babel_ifp != NULL);
+ babel_ifp->flags &= ~BABEL_IF_SPLIT_HORIZON;
+ return CMD_SUCCESS;
+}
+
+/* [Interface Command]. */
+DEFUN (babel_set_hello_interval,
+ babel_set_hello_interval_cmd,
+ "babel hello-interval <20-655340>",
+ "Babel interface commands\n"
+ "Time between scheduled hellos\n"
+ "Milliseconds\n")
+{
+ struct interface *ifp;
+ babel_interface_nfo *babel_ifp;
+ int interval;
+
+ VTY_GET_INTEGER_RANGE("milliseconds", interval, argv[0], 20, 10 * 0xFFFE);
+
+ ifp = vty->index;
+ babel_ifp = babel_get_if_nfo(ifp);
+ assert (babel_ifp != NULL);
+
+ babel_ifp->hello_interval = interval;
+ return CMD_SUCCESS;
+}
+
+/* [Interface Command]. */
+DEFUN (babel_set_update_interval,
+ babel_set_update_interval_cmd,
+ "babel update-interval <20-655340>",
+ "Babel interface commands\n"
+ "Time between scheduled updates\n"
+ "Milliseconds\n")
+{
+ struct interface *ifp;
+ babel_interface_nfo *babel_ifp;
+ int interval;
+
+ VTY_GET_INTEGER_RANGE("milliseconds", interval, argv[0], 20, 10 * 0xFFFE);
+
+ ifp = vty->index;
+ babel_ifp = babel_get_if_nfo(ifp);
+ assert (babel_ifp != NULL);
+
+ babel_ifp->update_interval = interval;
+ return CMD_SUCCESS;
+}
+
+/* This should be no more than half the hello interval, so that hellos
+ aren't sent late. The result is in milliseconds. */
+unsigned
+jitter(babel_interface_nfo *babel_ifp, int urgent)
+{
+ unsigned interval = babel_ifp->hello_interval;
+ if(urgent)
+ interval = MIN(interval, 100);
+ else
+ interval = MIN(interval, 4000);
+ return roughly(interval) / 4;
+}
+
+unsigned
+update_jitter(babel_interface_nfo *babel_ifp, int urgent)
+{
+ unsigned interval = babel_ifp->hello_interval;
+ if(urgent)
+ interval = MIN(interval, 100);
+ else
+ interval = MIN(interval, 4000);
+ return roughly(interval);
+}
+
+/* calculate babeld's specific datas of an interface (change when the interface
+ change) */
+static int
+interface_recalculate(struct interface *ifp)
+{
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+ unsigned char *tmp = NULL;
+ int mtu, rc;
+ struct ipv6_mreq mreq;
+
+ if (!IS_ENABLE(ifp))
+ return -1;
+
+ if (!if_is_operative(ifp) || !CHECK_FLAG(ifp->flags, IFF_RUNNING)) {
+ interface_reset(ifp);
+ return -1;
+ }
+
+ babel_ifp->flags |= BABEL_IF_IS_UP;
+
+ mtu = MIN(ifp->mtu, ifp->mtu6);
+
+ /* We need to be able to fit at least two messages into a packet,
+ so MTUs below 116 require lower layer fragmentation. */
+ /* In IPv6, the minimum MTU is 1280, and every host must be able
+ to reassemble up to 1500 bytes, but I'd rather not rely on this. */
+ if(mtu < 128) {
+ debugf(BABEL_DEBUG_IF, "Suspiciously low MTU %d on interface %s (%d).",
+ mtu, ifp->name, ifp->ifindex);
+ mtu = 128;
+ }
+
+ /* 40 for IPv6 header, 8 for UDP header, 12 for good luck. */
+ babel_ifp->bufsize = mtu - sizeof(packet_header) - 60;
+ tmp = babel_ifp->sendbuf;
+ babel_ifp->sendbuf = realloc(babel_ifp->sendbuf, babel_ifp->bufsize);
+ if(babel_ifp->sendbuf == NULL) {
+ zlog_err("Couldn't reallocate sendbuf.");
+ free(tmp);
+ babel_ifp->bufsize = 0;
+ return -1;
+ }
+ tmp = NULL;
+
+ resize_receive_buffer(mtu);
+
+ memset(&mreq, 0, sizeof(mreq));
+ memcpy(&mreq.ipv6mr_multiaddr, protocol_group, 16);
+ mreq.ipv6mr_interface = ifp->ifindex;
+
+ rc = setsockopt(protocol_socket, IPPROTO_IPV6, IPV6_JOIN_GROUP,
+ (char*)&mreq, sizeof(mreq));
+ if(rc < 0) {
+ zlog_err("setsockopt(IPV6_JOIN_GROUP) on interface '%s': %s",
+ ifp->name, safe_strerror(errno));
+ /* This is probably due to a missing link-local address,
+ so down this interface, and wait until the main loop
+ tries to up it again. */
+ interface_reset(ifp);
+ return -1;
+ }
+
+ set_timeout(&babel_ifp->hello_timeout, babel_ifp->hello_interval);
+ set_timeout(&babel_ifp->update_timeout, babel_ifp->update_interval);
+ send_hello(ifp);
+ send_request(ifp, NULL, 0);
+
+ update_interface_metric(ifp);
+
+ debugf(BABEL_DEBUG_COMMON,
+ "Upped interface %s (%s, cost=%d, channel=%d%s).",
+ ifp->name,
+ (babel_ifp->flags & BABEL_IF_WIRED) ? "wired" : "wireless",
+ babel_ifp->cost,
+ babel_ifp->channel,
+ babel_ifp->ipv4 ? ", IPv4" : "");
+
+ if(rc > 0)
+ send_update(ifp, 0, NULL, 0);
+
+ return 1;
+}
+
+/* Reset the interface as it was new: it's not removed from the interface list,
+ and may be considered as a upped interface. */
+static int
+interface_reset(struct interface *ifp)
+{
+ int rc;
+ struct ipv6_mreq mreq;
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+
+ if (!(babel_ifp->flags & BABEL_IF_IS_UP))
+ return 0;
+
+ debugf(BABEL_DEBUG_IF, "interface reset: %s", ifp->name);
+ babel_ifp->flags &= ~BABEL_IF_IS_UP;
+
+ flush_interface_routes(ifp, 0);
+ babel_ifp->buffered = 0;
+ babel_ifp->bufsize = 0;
+ free(babel_ifp->sendbuf);
+ babel_ifp->num_buffered_updates = 0;
+ babel_ifp->update_bufsize = 0;
+ if(babel_ifp->buffered_updates)
+ free(babel_ifp->buffered_updates);
+ babel_ifp->buffered_updates = NULL;
+ babel_ifp->sendbuf = NULL;
+
+ if(ifp->ifindex > 0) {
+ memset(&mreq, 0, sizeof(mreq));
+ memcpy(&mreq.ipv6mr_multiaddr, protocol_group, 16);
+ mreq.ipv6mr_interface = ifp->ifindex;
+ rc = setsockopt(protocol_socket, IPPROTO_IPV6, IPV6_LEAVE_GROUP,
+ (char*)&mreq, sizeof(mreq));
+ if(rc < 0)
+ zlog_err("setsockopt(IPV6_LEAVE_GROUP) on interface '%s': %s",
+ ifp->name, safe_strerror(errno));
+ }
+
+ update_interface_metric(ifp);
+
+ debugf(BABEL_DEBUG_COMMON,"Upped network %s (%s, cost=%d%s).",
+ ifp->name,
+ (babel_ifp->flags & BABEL_IF_WIRED) ? "wired" : "wireless",
+ babel_ifp->cost,
+ babel_ifp->ipv4 ? ", IPv4" : "");
+
+ return 1;
+}
+
+/* Send retraction to all, and reset all interfaces statistics. */
+void
+babel_interface_close_all(void)
+{
+ struct interface *ifp = NULL;
+ struct listnode *linklist_node = NULL;
+
+ FOR_ALL_INTERFACES(ifp, linklist_node) {
+ if(!if_up(ifp))
+ continue;
+ send_wildcard_retraction(ifp);
+ /* Make sure that we expire quickly from our neighbours'
+ association caches. */
+ send_hello_noupdate(ifp, 10);
+ flushbuf(ifp);
+ usleep(roughly(1000));
+ gettime(&babel_now);
+ }
+ FOR_ALL_INTERFACES(ifp, linklist_node) {
+ if(!if_up(ifp))
+ continue;
+ /* Make sure they got it. */
+ send_wildcard_retraction(ifp);
+ send_hello_noupdate(ifp, 1);
+ flushbuf(ifp);
+ usleep(roughly(10000));
+ gettime(&babel_now);
+ interface_reset(ifp);
+ }
+}
+
+/* return "true" if address is one of our ipv6 addresses */
+int
+is_interface_ll_address(struct interface *ifp, const unsigned char *address)
+{
+ struct connected *connected;
+ struct listnode *node;
+
+ if(!if_up(ifp))
+ return 0;
+
+ FOR_ALL_INTERFACES_ADDRESSES(ifp, connected, node) {
+ if(connected->address->family == AF_INET6 &&
+ memcmp(&connected->address->u.prefix6, address, 16) == 0)
+ return 1;
+ }
+
+ return 0;
+}
+
+static void
+show_babel_interface_sub (struct vty *vty, struct interface *ifp)
+{
+ int is_up;
+ babel_interface_nfo *babel_ifp;
+
+ vty_out (vty, "%s is %s%s", ifp->name,
+ ((is_up = if_is_operative(ifp)) ? "up" : "down"), VTY_NEWLINE);
+ vty_out (vty, " ifindex %u, MTU %u bytes %s%s",
+ ifp->ifindex, ifp->mtu, if_flag_dump(ifp->flags), VTY_NEWLINE);
+
+ if (babel_enable_if_lookup (ifp->name) < 0)
+ {
+ vty_out (vty, " Babel protocol is not enabled on this interface%s", VTY_NEWLINE);
+ return;
+ }
+ if (!is_up)
+ {
+ vty_out (vty, " Babel protocol is enabled, but not running on this interface%s", VTY_NEWLINE);
+ return;
+ }
+ babel_ifp = babel_get_if_nfo (ifp);
+ vty_out (vty, " Babel protocol is running on this interface%s", VTY_NEWLINE);
+ vty_out (vty, " Operating mode is \"%s\"%s",
+ CHECK_FLAG (babel_ifp->flags, BABEL_IF_WIRED) ? "wired" : "wireless", VTY_NEWLINE);
+ vty_out (vty, " Split horizon mode is %s%s",
+ CHECK_FLAG (babel_ifp->flags, BABEL_IF_SPLIT_HORIZON) ? "On" : "Off", VTY_NEWLINE);
+ vty_out (vty, " Hello interval is %u ms%s", babel_ifp->hello_interval, VTY_NEWLINE);
+ vty_out (vty, " Update interval is %u ms%s", babel_ifp->update_interval, VTY_NEWLINE);
+}
+
+DEFUN (show_babel_interface,
+ show_babel_interface_cmd,
+ "show babel interface [INTERFACE]",
+ SHOW_STR
+ IP_STR
+ "Babel information\n"
+ "Interface information\n"
+ "Interface name\n")
+{
+ struct interface *ifp;
+ struct listnode *node;
+
+ if (argc == 0)
+ {
+ for (ALL_LIST_ELEMENTS_RO (iflist, node, ifp))
+ show_babel_interface_sub (vty, ifp);
+ return CMD_SUCCESS;
+ }
+ if ((ifp = if_lookup_by_name (argv[0])) == NULL)
+ {
+ vty_out (vty, "No such interface name%s", VTY_NEWLINE);
+ return CMD_WARNING;
+ }
+ show_babel_interface_sub (vty, ifp);
+ return CMD_SUCCESS;
+}
+
+static void
+show_babel_neighbour_sub (struct vty *vty, struct neighbour *neigh)
+{
+ vty_out (vty,
+ "Neighbour %s dev %s reach %04x rxcost %d txcost %d %s.%s",
+ format_address(neigh->address),
+ neigh->ifp->name,
+ neigh->reach,
+ neighbour_rxcost(neigh),
+ neigh->txcost,
+ if_up(neigh->ifp) ? "" : " (down)",
+ VTY_NEWLINE);
+}
+
+DEFUN (show_babel_neighbour,
+ show_babel_neighbour_cmd,
+ "show babel neighbour [INTERFACE]",
+ SHOW_STR
+ IP_STR
+ "Babel information\n"
+ "Print neighbours\n"
+ "Interface name\n")
+{
+ struct neighbour *neigh;
+ struct interface *ifp;
+
+ if (argc == 0) {
+ FOR_ALL_NEIGHBOURS(neigh) {
+ show_babel_neighbour_sub(vty, neigh);
+ }
+ return CMD_SUCCESS;
+ }
+ if ((ifp = if_lookup_by_name (argv[0])) == NULL)
+ {
+ vty_out (vty, "No such interface name%s", VTY_NEWLINE);
+ return CMD_WARNING;
+ }
+ FOR_ALL_NEIGHBOURS(neigh) {
+ if(ifp->ifindex == neigh->ifp->ifindex) {
+ show_babel_neighbour_sub(vty, neigh);
+ }
+ }
+ return CMD_SUCCESS;
+}
+
+static void
+show_babel_routes_sub (struct babel_route *route, void *closure)
+{
+ struct vty *vty = (struct vty*) closure;
+ const unsigned char *nexthop =
+ memcmp(route->nexthop, route->neigh->address, 16) == 0 ?
+ NULL : route->nexthop;
+ char channels[100];
+
+ if(route->channels[0] == 0)
+ channels[0] = '\0';
+ else {
+ int k, j = 0;
+ snprintf(channels, 100, " chan (");
+ j = strlen(channels);
+ for(k = 0; k < DIVERSITY_HOPS; k++) {
+ if(route->channels[k] == 0)
+ break;
+ if(k > 0)
+ channels[j++] = ',';
+ snprintf(channels + j, 100 - j, "%d", route->channels[k]);
+ j = strlen(channels);
+ }
+ snprintf(channels + j, 100 - j, ")");
+ if(k == 0)
+ channels[0] = '\0';
+ }
+
+ vty_out(vty,
+ "%s metric %d refmetric %d id %s seqno %d%s age %d "
+ "via %s neigh %s%s%s%s%s",
+ format_prefix(route->src->prefix, route->src->plen),
+ route_metric(route), route->refmetric,
+ format_eui64(route->src->id),
+ (int)route->seqno,
+ channels,
+ (int)(babel_now.tv_sec - route->time),
+ route->neigh->ifp->name,
+ format_address(route->neigh->address),
+ nexthop ? " nexthop " : "",
+ nexthop ? format_address(nexthop) : "",
+ route->installed ? " (installed)" :
+ route_feasible(route) ? " (feasible)" : "",
+ VTY_NEWLINE);
+}
+
+static void
+show_babel_xroutes_sub (struct xroute *xroute, void *closure)
+{
+ struct vty *vty = (struct vty *) closure;
+ vty_out(vty, "%s metric %d (exported)%s",
+ format_prefix(xroute->prefix, xroute->plen),
+ xroute->metric,
+ VTY_NEWLINE);
+}
+
+DEFUN (show_babel_database,
+ show_babel_database_cmd,
+ "show babel database",
+ SHOW_STR
+ IP_STR
+ "Babel information\n"
+ "Database information\n"
+ "No attributes\n")
+{
+ for_all_routes(show_babel_routes_sub, vty);
+ for_all_xroutes(show_babel_xroutes_sub, vty);
+ return CMD_SUCCESS;
+}
+
+DEFUN (show_babel_parameters,
+ show_babel_parameters_cmd,
+ "show babel parameters",
+ SHOW_STR
+ IP_STR
+ "Babel information\n"
+ "Configuration information\n"
+ "No attributes\n")
+{
+ vty_out(vty, " -- Babel running configuration --%s", VTY_NEWLINE);
+ show_babel_main_configuration(vty);
+ vty_out(vty, " -- distribution lists --%s", VTY_NEWLINE);
+ config_show_distribute(vty);
+
+ return CMD_SUCCESS;
+}
+
+void
+babel_if_init ()
+{
+ /* initialize interface list */
+ if_init();
+ if_add_hook (IF_NEW_HOOK, babel_if_new_hook);
+ if_add_hook (IF_DELETE_HOOK, babel_if_delete_hook);
+
+ babel_enable_if = vector_init (1);
+
+ /* install interface node and commands */
+ install_element (CONFIG_NODE, &interface_cmd);
+ install_element (CONFIG_NODE, &no_interface_cmd);
+ install_node (&babel_interface_node, interface_config_write);
+ install_default(INTERFACE_NODE);
+ install_element(INTERFACE_NODE, &interface_cmd);
+ install_element(INTERFACE_NODE, &no_interface_cmd);
+
+ install_element(BABEL_NODE, &babel_network_cmd);
+ install_element(BABEL_NODE, &no_babel_network_cmd);
+ install_element(INTERFACE_NODE, &babel_split_horizon_cmd);
+ install_element(INTERFACE_NODE, &no_babel_split_horizon_cmd);
+ install_element(INTERFACE_NODE, &babel_set_wired_cmd);
+ install_element(INTERFACE_NODE, &babel_set_wireless_cmd);
+ install_element(INTERFACE_NODE, &babel_set_hello_interval_cmd);
+ install_element(INTERFACE_NODE, &babel_set_update_interval_cmd);
+
+ /* "show babel ..." commands */
+ install_element(VIEW_NODE, &show_babel_interface_cmd);
+ install_element(ENABLE_NODE, &show_babel_interface_cmd);
+ install_element(VIEW_NODE, &show_babel_neighbour_cmd);
+ install_element(ENABLE_NODE, &show_babel_neighbour_cmd);
+ install_element(VIEW_NODE, &show_babel_database_cmd);
+ install_element(ENABLE_NODE, &show_babel_database_cmd);
+ install_element(VIEW_NODE, &show_babel_parameters_cmd);
+ install_element(ENABLE_NODE, &show_babel_parameters_cmd);
+}
+
+/* hooks: functions called respectively when struct interface is
+ created or deleted. */
+static int
+babel_if_new_hook (struct interface *ifp)
+{
+ ifp->info = babel_interface_allocate();
+ return 0;
+}
+
+static int
+babel_if_delete_hook (struct interface *ifp)
+{
+ babel_interface_free(ifp->info);
+ ifp->info = NULL;
+ return 0;
+}
+
+/* Output an "interface" section for each of the known interfaces with
+babeld-specific statement lines where appropriate. */
+static int
+interface_config_write (struct vty *vty)
+{
+ struct listnode *node;
+ struct interface *ifp;
+ int write = 0;
+
+ for (ALL_LIST_ELEMENTS_RO (iflist, node, ifp)) {
+ vty_out (vty, "interface %s%s", ifp->name,
+ VTY_NEWLINE);
+ if (ifp->desc)
+ vty_out (vty, " description %s%s", ifp->desc,
+ VTY_NEWLINE);
+ if (IS_ENABLE (ifp))
+ {
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo (ifp);
+ /* wireless/no split-horizon is the default */
+ if (CHECK_FLAG (babel_ifp->flags, BABEL_IF_WIRED))
+ {
+ vty_out (vty, " babel wired%s", VTY_NEWLINE);
+ write++;
+ }
+ if (CHECK_FLAG (babel_ifp->flags, BABEL_IF_SPLIT_HORIZON))
+ {
+ vty_out (vty, " babel split-horizon%s", VTY_NEWLINE);
+ write++;
+ }
+ if (babel_ifp->hello_interval != BABEL_DEFAULT_HELLO_INTERVAL)
+ {
+ vty_out (vty, " babel hello-interval %u%s", babel_ifp->hello_interval, VTY_NEWLINE);
+ write++;
+ }
+ if (babel_ifp->update_interval != BABEL_DEFAULT_UPDATE_INTERVAL)
+ {
+ vty_out (vty, " babel update-interval %u%s", babel_ifp->update_interval, VTY_NEWLINE);
+ write++;
+ }
+ }
+ vty_out (vty, "!%s", VTY_NEWLINE);
+ write++;
+ }
+ return write;
+}
+
+/* Output a "network" statement line for each of the enabled interfaces. */
+int
+babel_enable_if_config_write (struct vty * vty)
+{
+ unsigned int i, lines = 0;
+ char *str;
+
+ for (i = 0; i < vector_active (babel_enable_if); i++)
+ if ((str = vector_slot (babel_enable_if, i)) != NULL)
+ {
+ vty_out (vty, " network %s%s", str, VTY_NEWLINE);
+ lines++;
+ }
+ return lines;
+}
+
+/* functions to allocate or free memory for a babel_interface_nfo, filling
+ needed fields */
+static babel_interface_nfo *
+babel_interface_allocate (void)
+{
+ babel_interface_nfo *babel_ifp;
+ babel_ifp = XMALLOC(MTYPE_BABEL_IF, sizeof(babel_interface_nfo));
+ if(babel_ifp == NULL)
+ return NULL;
+
+ /* Here are set the default values for an interface. */
+ memset(babel_ifp, 0, sizeof(babel_interface_nfo));
+ /* All flags are unset */
+ babel_ifp->bucket_time = babel_now.tv_sec;
+ babel_ifp->bucket = BUCKET_TOKENS_MAX;
+ babel_ifp->hello_seqno = (random() & 0xFFFF);
+ babel_ifp->hello_interval = BABEL_DEFAULT_HELLO_INTERVAL;
+ babel_ifp->update_interval = BABEL_DEFAULT_UPDATE_INTERVAL;
+ babel_ifp->channel = BABEL_IF_CHANNEL_INTERFERING;
+ babel_set_wired_internal(babel_ifp, 0);
+
+ return babel_ifp;
+}
+
+static void
+babel_interface_free (babel_interface_nfo *babel_ifp)
+{
+ XFREE(MTYPE_BABEL_IF, babel_ifp);
+}
diff --git a/babeld/babel_interface.h b/babeld/babel_interface.h
new file mode 100644
index 00000000..94fd8e5d
--- /dev/null
+++ b/babeld/babel_interface.h
@@ -0,0 +1,152 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#ifndef BABEL_INTERFACE_H
+#define BABEL_INTERFACE_H
+
+#include <zebra.h>
+#include "zclient.h"
+#include "vty.h"
+
+#define CONFIG_DEFAULT 0
+#define CONFIG_NO 1
+#define CONFIG_YES 2
+
+/* babeld interface informations */
+struct babel_interface {
+ unsigned short flags; /* see below */
+ unsigned short cost;
+ int channel;
+ struct timeval hello_timeout;
+ struct timeval update_timeout;
+ struct timeval flush_timeout;
+ struct timeval update_flush_timeout;
+ unsigned char *ipv4;
+ int buffered;
+ int bufsize;
+ char have_buffered_hello;
+ char have_buffered_id;
+ char have_buffered_nh;
+ char have_buffered_prefix;
+ unsigned char buffered_id[16];
+ unsigned char buffered_nh[4];
+ unsigned char buffered_prefix[16];
+ unsigned char *sendbuf;
+ struct buffered_update *buffered_updates;
+ int num_buffered_updates;
+ int update_bufsize;
+ time_t bucket_time;
+ unsigned int bucket;
+ time_t last_update_time;
+ unsigned short hello_seqno;
+ unsigned hello_interval;
+ unsigned update_interval;
+
+ /* For filter type slot. */
+#define BABEL_FILTER_IN 0
+#define BABEL_FILTER_OUT 1
+#define BABEL_FILTER_MAX 2
+ struct access_list *list[BABEL_FILTER_MAX]; /* Access-list. */
+ struct prefix_list *prefix[BABEL_FILTER_MAX]; /* Prefix-list. */
+};
+
+typedef struct babel_interface babel_interface_nfo;
+static inline babel_interface_nfo* babel_get_if_nfo(struct interface *ifp)
+{
+ return ((babel_interface_nfo*) ifp->info);
+}
+
+/* babel_interface_nfo flags */
+#define BABEL_IF_IS_UP (1 << 0)
+#define BABEL_IF_WIRED (1 << 1)
+#define BABEL_IF_SPLIT_HORIZON (1 << 2)
+#define BABEL_IF_LQ (1 << 3)
+#define BABEL_IF_FARAWAY (1 << 4)
+
+/* Only INTERFERING can appear on the wire. */
+#define BABEL_IF_CHANNEL_UNKNOWN 0
+#define BABEL_IF_CHANNEL_INTERFERING 255
+#define BABEL_IF_CHANNEL_NONINTERFERING -2
+
+static inline int
+if_up(struct interface *ifp)
+{
+ return (if_is_operative(ifp) &&
+ ifp->connected != NULL &&
+ (babel_get_if_nfo(ifp)->flags & BABEL_IF_IS_UP));
+}
+
+/* types:
+ struct interface _ifp, struct listnode node */
+#define FOR_ALL_INTERFACES(_ifp, _node) \
+ for(ALL_LIST_ELEMENTS_RO(iflist, _node, _ifp))
+
+/* types:
+ struct interface *ifp, struct connected *_connected, struct listnode *node */
+#define FOR_ALL_INTERFACES_ADDRESSES(ifp, _connected, _node) \
+ for(ALL_LIST_ELEMENTS_RO(ifp->connected, _node, _connected))
+
+struct buffered_update {
+ unsigned char id[8];
+ unsigned char prefix[16];
+ unsigned char plen;
+ unsigned char pad[3];
+};
+
+
+/* init function */
+void babel_if_init(void);
+
+/* Callback functions for zebra client */
+int babel_interface_up (int, struct zclient *, zebra_size_t);
+int babel_interface_down (int, struct zclient *, zebra_size_t);
+int babel_interface_add (int, struct zclient *, zebra_size_t);
+int babel_interface_delete (int, struct zclient *, zebra_size_t);
+int babel_interface_address_add (int, struct zclient *, zebra_size_t);
+int babel_interface_address_delete (int, struct zclient *, zebra_size_t);
+
+unsigned jitter(babel_interface_nfo *, int);
+unsigned update_jitter(babel_interface_nfo *babel_ifp, int urgent);
+/* return "true" if "address" is one of our ipv6 addresses */
+int is_interface_ll_address(struct interface *ifp, const unsigned char *address);
+/* Send retraction to all, and reset all interfaces statistics. */
+void babel_interface_close_all(void);
+extern int babel_enable_if_config_write (struct vty *);
+
+
+#endif
diff --git a/babeld/babel_main.c b/babeld/babel_main.c
new file mode 100644
index 00000000..2f3b5552
--- /dev/null
+++ b/babeld/babel_main.c
@@ -0,0 +1,532 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+
+Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+/* include zebra library */
+#include <zebra.h>
+#include "getopt.h"
+#include "if.h"
+#include "log.h"
+#include "thread.h"
+#include "privs.h"
+#include "sigevent.h"
+#include "version.h"
+#include "command.h"
+#include "vty.h"
+#include "memory.h"
+
+#include "babel_main.h"
+#include "babeld.h"
+#include "util.h"
+#include "kernel.h"
+#include "babel_interface.h"
+#include "neighbour.h"
+#include "route.h"
+#include "xroute.h"
+#include "message.h"
+#include "resend.h"
+#include "babel_zebra.h"
+
+
+static void babel_init (int argc, char **argv);
+static char *babel_get_progname(char *argv_0);
+static void babel_fail(void);
+static void babel_init_random(void);
+static void babel_replace_by_null(int fd);
+static void babel_init_signals(void);
+static void babel_exit_properly(void);
+static void babel_save_state_file(void);
+
+
+struct thread_master *master; /* quagga's threads handler */
+struct timeval babel_now; /* current time */
+
+unsigned char myid[8]; /* unique id (mac address of an interface) */
+int debug = 0;
+
+int resend_delay = -1;
+static const char *pidfile = PATH_BABELD_PID;
+
+const unsigned char zeroes[16] = {0};
+const unsigned char ones[16] =
+ {0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
+ 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF};
+
+static const char *state_file = DAEMON_VTY_DIR "/babel-state";
+
+unsigned char protocol_group[16]; /* babel's link-local multicast address */
+int protocol_port; /* babel's port */
+int protocol_socket = -1; /* socket: communicate with others babeld */
+
+static char babel_config_default[] = SYSCONFDIR BABEL_DEFAULT_CONFIG;
+static char *babel_config_file = NULL;
+static char *babel_vty_addr = NULL;
+static int babel_vty_port = BABEL_VTY_PORT;
+
+/* Babeld options. */
+struct option longopts[] =
+{
+ { "daemon", no_argument, NULL, 'd'},
+ { "config_file", required_argument, NULL, 'f'},
+ { "pid_file", required_argument, NULL, 'i'},
+ { "socket", required_argument, NULL, 'z'},
+ { "help", no_argument, NULL, 'h'},
+ { "vty_addr", required_argument, NULL, 'A'},
+ { "vty_port", required_argument, NULL, 'P'},
+ { "user", required_argument, NULL, 'u'},
+ { "group", required_argument, NULL, 'g'},
+ { "version", no_argument, NULL, 'v'},
+ { 0 }
+};
+
+/* babeld privileges */
+static zebra_capabilities_t _caps_p [] =
+{
+ ZCAP_NET_RAW,
+ ZCAP_BIND
+};
+static struct zebra_privs_t babeld_privs =
+{
+#if defined(QUAGGA_USER)
+ .user = QUAGGA_USER,
+#endif
+#if defined QUAGGA_GROUP
+ .group = QUAGGA_GROUP,
+#endif
+#ifdef VTY_GROUP
+ .vty_group = VTY_GROUP,
+#endif
+ .caps_p = _caps_p,
+ .cap_num_p = 2,
+ .cap_num_i = 0
+};
+
+
+int
+main(int argc, char **argv)
+{
+ struct thread thread;
+ /* and print banner too */
+ babel_init(argc, argv);
+ while (thread_fetch (master, &thread)) {
+ thread_call (&thread);
+ }
+ return 0;
+}
+
+static void
+babel_usage (char *progname, int status)
+{
+ if (status != 0)
+ fprintf (stderr, "Try `%s --help' for more information.\n", progname);
+ else
+ {
+ printf ("Usage : %s [OPTION...]\n\
+Daemon which manages Babel routing protocol.\n\n\
+-d, --daemon Runs in daemon mode\n\
+-f, --config_file Set configuration file name\n\
+-i, --pid_file Set process identifier file name\n\
+-z, --socket Set path of zebra socket\n\
+-A, --vty_addr Set vty's bind address\n\
+-P, --vty_port Set vty's port number\n\
+-u, --user User to run as\n\
+-g, --group Group to run as\n\
+-v, --version Print program version\n\
+-h, --help Display this help and exit\n\
+\n\
+Report bugs to %s\n", progname, ZEBRA_BUG_ADDRESS);
+ }
+ exit (status);
+}
+
+/* make initialisations witch don't need infos about kernel(interfaces, etc.) */
+static void
+babel_init(int argc, char **argv)
+{
+ int rc, opt;
+ int do_daemonise = 0;
+ char *progname = NULL;
+
+ /* Set umask before anything for security */
+ umask (0027);
+ progname = babel_get_progname(argv[0]);
+
+ /* set default log (lib/log.h) */
+ zlog_default = openzlog(progname, ZLOG_BABEL,
+ LOG_CONS|LOG_NDELAY|LOG_PID, LOG_DAEMON);
+ /* set log destination as stdout until the config file is read */
+ zlog_set_level(NULL, ZLOG_DEST_STDOUT, LOG_WARNING);
+
+ babel_init_random();
+
+ /* set the Babel's default link-local multicast address and Babel's port */
+ parse_address("ff02:0:0:0:0:0:1:6", protocol_group, NULL);
+ protocol_port = 6696;
+
+ /* get options */
+ while(1) {
+ opt = getopt_long(argc, argv, "df:i:z:hA:P:u:g:v", longopts, 0);
+ if(opt < 0)
+ break;
+
+ switch(opt) {
+ case 0:
+ break;
+ case 'd':
+ do_daemonise = -1;
+ break;
+ case 'f':
+ babel_config_file = optarg;
+ break;
+ case 'i':
+ pidfile = optarg;
+ break;
+ case 'z':
+ zclient_serv_path_set (optarg);
+ break;
+ case 'A':
+ babel_vty_addr = optarg;
+ break;
+ case 'P':
+ babel_vty_port = atoi (optarg);
+ if (babel_vty_port <= 0 || babel_vty_port > 0xffff)
+ babel_vty_port = BABEL_VTY_PORT;
+ break;
+ case 'u':
+ babeld_privs.user = optarg;
+ break;
+ case 'g':
+ babeld_privs.group = optarg;
+ break;
+ case 'v':
+ print_version (progname);
+ exit (0);
+ break;
+ case 'h':
+ babel_usage (progname, 0);
+ break;
+ default:
+ babel_usage (progname, 1);
+ break;
+ }
+ }
+
+ /* create the threads handler */
+ master = thread_master_create ();
+
+ /* Library inits. */
+ zprivs_init (&babeld_privs);
+ babel_init_signals();
+ cmd_init (1);
+ vty_init (master);
+ memory_init ();
+
+ resend_delay = BABEL_DEFAULT_RESEND_DELAY;
+
+ babel_replace_by_null(STDIN_FILENO);
+
+ if (do_daemonise && daemonise() < 0) {
+ zlog_err("daemonise: %s", safe_strerror(errno));
+ exit (1);
+ }
+
+ /* write pid file */
+ if (pid_output(pidfile) < 0) {
+ zlog_err("error while writing pidfile");
+ exit (1);
+ };
+
+ /* init some quagga's dependencies, and babeld's commands */
+ babeld_quagga_init();
+ /* init zebra client's structure and it's commands */
+ /* this replace kernel_setup && kernel_setup_socket */
+ babelz_zebra_init ();
+
+ /* Sort all installed commands. */
+ sort_node ();
+
+ /* Get zebra configuration file. */
+ zlog_set_level (NULL, ZLOG_DEST_STDOUT, ZLOG_DISABLED);
+ vty_read_config (babel_config_file, babel_config_default);
+
+ /* Create VTY socket */
+ vty_serv_sock (babel_vty_addr, babel_vty_port, BABEL_VTYSH_PATH);
+
+ /* init buffer */
+ rc = resize_receive_buffer(1500);
+ if(rc < 0)
+ babel_fail();
+
+ schedule_neighbours_check(5000, 1);
+
+ zlog_notice ("BABELd %s starting: vty@%d", BABEL_VERSION, babel_vty_port);
+}
+
+/* return the progname (without path, example: "./x/progname" --> "progname") */
+static char *
+babel_get_progname(char *argv_0) {
+ char *p = strrchr (argv_0, '/');
+ return (p ? ++p : argv_0);
+}
+
+static void
+babel_fail(void)
+{
+ exit(1);
+}
+
+/* initialize random value, and set 'babel_now' by the way. */
+static void
+babel_init_random(void)
+{
+ gettime(&babel_now);
+ int rc;
+ unsigned int seed;
+
+ rc = read_random_bytes(&seed, sizeof(seed));
+ if(rc < 0) {
+ zlog_err("read(random): %s", safe_strerror(errno));
+ seed = 42;
+ }
+
+ seed ^= (babel_now.tv_sec ^ babel_now.tv_usec);
+ srandom(seed);
+}
+
+/*
+ close fd, and replace it by "/dev/null"
+ exit if error
+ */
+static void
+babel_replace_by_null(int fd)
+{
+ int fd_null;
+ int rc;
+
+ fd_null = open("/dev/null", O_RDONLY);
+ if(fd_null < 0) {
+ zlog_err("open(null): %s", safe_strerror(errno));
+ exit(1);
+ }
+
+ rc = dup2(fd_null, fd);
+ if(rc < 0) {
+ zlog_err("dup2(null, 0): %s", safe_strerror(errno));
+ exit(1);
+ }
+
+ close(fd_null);
+}
+
+/*
+ Load the state file: check last babeld's running state, usefull in case of
+ "/etc/init.d/babeld restart"
+ */
+void
+babel_load_state_file(void)
+{
+ int fd;
+ int rc;
+
+ fd = open(state_file, O_RDONLY);
+ if(fd < 0 && errno != ENOENT)
+ zlog_err("open(babel-state: %s)", safe_strerror(errno));
+ rc = unlink(state_file);
+ if(fd >= 0 && rc < 0) {
+ zlog_err("unlink(babel-state): %s", safe_strerror(errno));
+ /* If we couldn't unlink it, it's probably stale. */
+ close(fd);
+ fd = -1;
+ }
+ if(fd >= 0) {
+ char buf[100];
+ char buf2[100];
+ int s;
+ long t;
+ rc = read(fd, buf, 99);
+ if(rc < 0) {
+ zlog_err("read(babel-state): %s", safe_strerror(errno));
+ } else {
+ buf[rc] = '\0';
+ rc = sscanf(buf, "%99s %d %ld\n", buf2, &s, &t);
+ if(rc == 3 && s >= 0 && s <= 0xFFFF) {
+ unsigned char sid[8];
+ rc = parse_eui64(buf2, sid);
+ if(rc < 0) {
+ zlog_err("Couldn't parse babel-state.");
+ } else {
+ struct timeval realnow;
+ debugf(BABEL_DEBUG_COMMON,
+ "Got %s %d %ld from babel-state.",
+ format_eui64(sid), s, t);
+ gettimeofday(&realnow, NULL);
+ if(memcmp(sid, myid, 8) == 0)
+ myseqno = seqno_plus(s, 1);
+ else
+ zlog_err("ID mismatch in babel-state. id=%s; old=%s",
+ format_eui64(myid),
+ format_eui64(sid));
+ }
+ } else {
+ zlog_err("Couldn't parse babel-state.");
+ }
+ }
+ close(fd);
+ fd = -1;
+ }
+}
+
+static void
+babel_sigexit(void)
+{
+ zlog_notice("Terminating on signal");
+
+ babel_exit_properly();
+}
+
+static void
+babel_sigusr1 (void)
+{
+ zlog_rotate (NULL);
+}
+
+static void
+babel_init_signals(void)
+{
+ static struct quagga_signal_t babel_signals[] =
+ {
+ {
+ .signal = SIGUSR1,
+ .handler = &babel_sigusr1,
+ },
+ {
+ .signal = SIGINT,
+ .handler = &babel_sigexit,
+ },
+ {
+ .signal = SIGTERM,
+ .handler = &babel_sigexit,
+ },
+ };
+
+ signal_init (master, Q_SIGC(babel_signals), babel_signals);
+}
+
+static void
+babel_exit_properly(void)
+{
+ debugf(BABEL_DEBUG_COMMON, "Exiting...");
+ usleep(roughly(10000));
+ gettime(&babel_now);
+
+ /* Uninstall and flush all routes. */
+ debugf(BABEL_DEBUG_COMMON, "Uninstall routes.");
+ flush_all_routes();
+ babel_interface_close_all();
+ babel_zebra_close_connexion();
+ babel_save_state_file();
+ debugf(BABEL_DEBUG_COMMON, "Remove pid file.");
+ if(pidfile)
+ unlink(pidfile);
+ debugf(BABEL_DEBUG_COMMON, "Done.");
+
+ exit(0);
+}
+
+static void
+babel_save_state_file(void)
+{
+ int fd;
+ int rc;
+
+ debugf(BABEL_DEBUG_COMMON, "Save state file.");
+ fd = open(state_file, O_WRONLY | O_TRUNC | O_CREAT, 0644);
+ if(fd < 0) {
+ zlog_err("creat(babel-state): %s", safe_strerror(errno));
+ unlink(state_file);
+ } else {
+ struct timeval realnow;
+ char buf[100];
+ gettimeofday(&realnow, NULL);
+ rc = snprintf(buf, 100, "%s %d %ld\n",
+ format_eui64(myid), (int)myseqno,
+ (long)realnow.tv_sec);
+ if(rc < 0 || rc >= 100) {
+ zlog_err("write(babel-state): overflow.");
+ unlink(state_file);
+ } else {
+ rc = write(fd, buf, rc);
+ if(rc < 0) {
+ zlog_err("write(babel-state): %s", safe_strerror(errno));
+ unlink(state_file);
+ }
+ fsync(fd);
+ }
+ close(fd);
+ }
+}
+
+void
+show_babel_main_configuration (struct vty *vty)
+{
+ vty_out(vty,
+ "pid file = %s%s"
+ "state file = %s%s"
+ "configuration file = %s%s"
+ "protocol informations:%s"
+ " multicast address = %s%s"
+ " port = %d%s"
+ "vty address = %s%s"
+ "vty port = %d%s"
+ "id = %s%s"
+ "allow_duplicates = %s%s"
+ "kernel_metric = %d%s",
+ pidfile, VTY_NEWLINE,
+ state_file, VTY_NEWLINE,
+ babel_config_file ? babel_config_file : babel_config_default,
+ VTY_NEWLINE,
+ VTY_NEWLINE,
+ format_address(protocol_group), VTY_NEWLINE,
+ protocol_port, VTY_NEWLINE,
+ babel_vty_addr ? babel_vty_addr : "None",
+ VTY_NEWLINE,
+ babel_vty_port, VTY_NEWLINE,
+ format_eui64(myid), VTY_NEWLINE,
+ format_bool(allow_duplicates), VTY_NEWLINE,
+ kernel_metric, VTY_NEWLINE);
+}
diff --git a/babeld/babel_main.h b/babeld/babel_main.h
new file mode 100644
index 00000000..a4038dec
--- /dev/null
+++ b/babeld/babel_main.h
@@ -0,0 +1,57 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include "vty.h"
+
+extern struct timeval babel_now; /* current time */
+extern struct thread_master *master; /* quagga's threads handler */
+extern int debug;
+extern int resend_delay;
+
+extern unsigned char myid[8];
+
+extern const unsigned char zeroes[16], ones[16];
+
+extern int protocol_port;
+extern unsigned char protocol_group[16];
+extern int protocol_socket;
+extern int kernel_socket;
+extern int max_request_hopcount;
+
+void babel_load_state_file(void);
+void show_babel_main_configuration (struct vty *vty);
diff --git a/babeld/babel_zebra.c b/babeld/babel_zebra.c
new file mode 100644
index 00000000..75a1e6a8
--- /dev/null
+++ b/babeld/babel_zebra.c
@@ -0,0 +1,378 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+/* quagga's includes */
+#include <zebra.h>
+#include "command.h"
+#include "zclient.h"
+#include "stream.h"
+
+/* babel's includes*/
+#include "babel_zebra.h"
+#include "babel_interface.h"
+#include "xroute.h"
+#include "util.h"
+
+void babelz_zebra_init(void);
+
+
+/* we must use a pointer because of zclient.c's functions (new, free). */
+struct zclient *zclient;
+static int zebra_config_write (struct vty *vty);
+
+/* Debug types */
+static struct {
+ int type;
+ int str_min_len;
+ const char *str;
+} debug_type[] = {
+ {BABEL_DEBUG_COMMON, 1, "common"},
+ {BABEL_DEBUG_KERNEL, 1, "kernel"},
+ {BABEL_DEBUG_FILTER, 1, "filter"},
+ {BABEL_DEBUG_TIMEOUT, 1, "timeout"},
+ {BABEL_DEBUG_IF, 1, "interface"},
+ {BABEL_DEBUG_ROUTE, 1, "route"},
+ {BABEL_DEBUG_ALL, 1, "all"},
+ {0, 0, NULL}
+};
+
+/* Zebra node structure. */
+struct cmd_node zebra_node =
+{
+ ZEBRA_NODE,
+ "%s(config-router)# ",
+ 1 /* vtysh? yes */
+};
+
+
+/* Zebra route add and delete treatment (ipv6). */
+static int
+babel_zebra_read_ipv6 (int command, struct zclient *zclient,
+ zebra_size_t length)
+{
+ struct stream *s;
+ struct zapi_ipv6 api;
+ unsigned long ifindex = -1;
+ struct in6_addr nexthop;
+ struct prefix_ipv6 prefix;
+
+ s = zclient->ibuf;
+ ifindex = 0;
+ memset (&nexthop, 0, sizeof (struct in6_addr));
+ memset (&api, 0, sizeof(struct zapi_ipv6));
+ memset (&prefix, 0, sizeof (struct prefix_ipv6));
+
+ /* Type, flags, message. */
+ api.type = stream_getc (s);
+ api.flags = stream_getc (s);
+ api.message = stream_getc (s);
+
+ /* IPv6 prefix. */
+ prefix.family = AF_INET6;
+ prefix.prefixlen = stream_getc (s);
+ stream_get (&prefix.prefix, s, PSIZE (prefix.prefixlen));
+
+ /* Nexthop, ifindex, distance, metric. */
+ if (CHECK_FLAG (api.message, ZAPI_MESSAGE_NEXTHOP)) {
+ api.nexthop_num = stream_getc (s);
+ stream_get (&nexthop, s, sizeof(nexthop));
+ }
+ if (CHECK_FLAG (api.message, ZAPI_MESSAGE_IFINDEX)) {
+ api.ifindex_num = stream_getc (s);
+ ifindex = stream_getl (s);
+ }
+ if (CHECK_FLAG (api.message, ZAPI_MESSAGE_DISTANCE))
+ api.distance = stream_getc (s);
+ else
+ api.distance = 0;
+ if (CHECK_FLAG (api.message, ZAPI_MESSAGE_METRIC))
+ api.metric = stream_getl (s);
+ else
+ api.metric = 0;
+
+ if (command == ZEBRA_IPV6_ROUTE_ADD)
+ babel_ipv6_route_add(&api, &prefix, ifindex, &nexthop);
+ else
+ babel_ipv6_route_delete(&api, &prefix, ifindex);
+
+ return 0;
+}
+
+static int
+babel_zebra_read_ipv4 (int command, struct zclient *zclient,
+ zebra_size_t length)
+{
+ struct stream *s;
+ struct zapi_ipv4 api;
+ unsigned long ifindex = -1;
+ struct in_addr nexthop;
+ struct prefix_ipv4 prefix;
+
+ s = zclient->ibuf;
+ ifindex = 0;
+ memset (&nexthop, 0, sizeof (struct in_addr));
+ memset (&api, 0, sizeof(struct zapi_ipv4));
+ memset (&prefix, 0, sizeof (struct prefix_ipv4));
+
+ /* Type, flags, message. */
+ api.type = stream_getc (s);
+ api.flags = stream_getc (s);
+ api.message = stream_getc (s);
+
+ /* IPv6 prefix. */
+ prefix.family = AF_INET;
+ prefix.prefixlen = stream_getc (s);
+ stream_get (&prefix.prefix, s, PSIZE (prefix.prefixlen));
+
+ /* Nexthop, ifindex, distance, metric. */
+ if (CHECK_FLAG (api.message, ZAPI_MESSAGE_NEXTHOP)) {
+ api.nexthop_num = stream_getc (s);
+ stream_get (&nexthop, s, sizeof(nexthop));
+ }
+ if (CHECK_FLAG (api.message, ZAPI_MESSAGE_IFINDEX)) {
+ api.ifindex_num = stream_getc (s);
+ ifindex = stream_getl (s);
+ }
+ if (CHECK_FLAG (api.message, ZAPI_MESSAGE_DISTANCE))
+ api.distance = stream_getc (s);
+ else
+ api.distance = 0;
+ if (CHECK_FLAG (api.message, ZAPI_MESSAGE_METRIC))
+ api.metric = stream_getl (s);
+ else
+ api.metric = 0;
+
+ if (command == ZEBRA_IPV6_ROUTE_ADD) {
+ babel_ipv4_route_add(&api, &prefix, ifindex, &nexthop);
+ } else {
+ babel_ipv4_route_delete(&api, &prefix, ifindex);
+ }
+
+ return 0;
+}
+
+/* [Babel Command] */
+DEFUN (babel_redistribute_type,
+ babel_redistribute_type_cmd,
+ "redistribute " QUAGGA_REDIST_STR_BABELD,
+ "Redistribute\n"
+ QUAGGA_REDIST_HELP_STR_BABELD)
+{
+ int type;
+
+ type = proto_redistnum(AFI_IP6, argv[0]);
+
+ if (type < 0)
+ type = proto_redistnum(AFI_IP, argv[0]);
+
+ if (type < 0) {
+ vty_out(vty, "Invalid type %s%s", argv[0], VTY_NEWLINE);
+ return CMD_WARNING;
+ }
+
+ zclient_redistribute (ZEBRA_REDISTRIBUTE_ADD, zclient, type);
+ return CMD_SUCCESS;
+}
+
+/* [Babel Command] */
+DEFUN (no_babel_redistribute_type,
+ no_babel_redistribute_type_cmd,
+ "no redistribute " QUAGGA_REDIST_STR_BABELD,
+ NO_STR
+ "Redistribute\n"
+ QUAGGA_REDIST_HELP_STR_BABELD)
+{
+ int type;
+
+ type = proto_redistnum(AFI_IP6, argv[0]);
+
+ if (type < 0)
+ type = proto_redistnum(AFI_IP, argv[0]);
+
+ if (type < 0) {
+ vty_out(vty, "Invalid type %s%s", argv[0], VTY_NEWLINE);
+ return CMD_WARNING;
+ }
+
+ zclient_redistribute (ZEBRA_REDISTRIBUTE_DELETE, zclient, type);
+ /* perhaps should we remove xroutes having the same type... */
+ return CMD_SUCCESS;
+}
+
+#ifndef NO_DEBUG
+/* [Babel Command] */
+DEFUN (debug_babel,
+ debug_babel_cmd,
+ "debug babel (common|kernel|filter|timeout|interface|route|all)",
+ "Enable debug messages for specific or all part.\n"
+ "Babel information\n"
+ "Common messages (default)\n"
+ "Kernel messages\n"
+ "Filter messages\n"
+ "Timeout messages\n"
+ "Interface messages\n"
+ "Route messages\n"
+ "All messages\n")
+{
+ int i;
+
+ for(i = 0; debug_type[i].str != NULL; i++) {
+ if (strncmp (debug_type[i].str, argv[0],
+ debug_type[i].str_min_len) == 0) {
+ debug |= debug_type[i].type;
+ return CMD_SUCCESS;
+ }
+ }
+
+ vty_out(vty, "Invalid type %s%s", argv[0], VTY_NEWLINE);
+
+ return CMD_WARNING;
+}
+
+/* [Babel Command] */
+DEFUN (no_debug_babel,
+ no_debug_babel_cmd,
+ "no debug babel (common|kernel|filter|timeout|interface|route|all)",
+ NO_STR
+ "Disable debug messages for specific or all part.\n"
+ "Babel information\n"
+ "Common messages (default)\n"
+ "Kernel messages\n"
+ "Filter messages\n"
+ "Timeout messages\n"
+ "Interface messages\n"
+ "Route messages\n"
+ "All messages\n")
+{
+ int i;
+
+ for (i = 0; debug_type[i].str; i++) {
+ if (strncmp(debug_type[i].str, argv[0],
+ debug_type[i].str_min_len) == 0) {
+ debug &= ~debug_type[i].type;
+ return CMD_SUCCESS;
+ }
+ }
+
+ vty_out(vty, "Invalid type %s%s", argv[0], VTY_NEWLINE);
+
+ return CMD_WARNING;
+}
+#endif /* NO_DEBUG */
+
+/* Output "debug" statement lines, if necessary. */
+int
+debug_babel_config_write (struct vty * vty)
+{
+#ifdef NO_DEBUG
+ return 0;
+#else
+ int i, lines = 0;
+
+ if (debug == BABEL_DEBUG_ALL)
+ {
+ vty_out (vty, "debug babel all%s", VTY_NEWLINE);
+ lines++;
+ }
+ else
+ for (i = 0; debug_type[i].str != NULL; i++)
+ if
+ (
+ debug_type[i].type != BABEL_DEBUG_ALL
+ && CHECK_FLAG (debug, debug_type[i].type)
+ )
+ {
+ vty_out (vty, "debug babel %s%s", debug_type[i].str, VTY_NEWLINE);
+ lines++;
+ }
+ if (lines)
+ {
+ vty_out (vty, "!%s", VTY_NEWLINE);
+ lines++;
+ }
+ return lines;
+#endif /* NO_DEBUG */
+}
+
+void babelz_zebra_init(void)
+{
+ zclient = zclient_new();
+ zclient_init(zclient, ZEBRA_ROUTE_BABEL);
+
+ zclient->interface_add = babel_interface_add;
+ zclient->interface_delete = babel_interface_delete;
+ zclient->interface_up = babel_interface_up;
+ zclient->interface_down = babel_interface_down;
+ zclient->interface_address_add = babel_interface_address_add;
+ zclient->interface_address_delete = babel_interface_address_delete;
+ zclient->ipv4_route_add = babel_zebra_read_ipv4;
+ zclient->ipv4_route_delete = babel_zebra_read_ipv4;
+ zclient->ipv6_route_add = babel_zebra_read_ipv6;
+ zclient->ipv6_route_delete = babel_zebra_read_ipv6;
+
+ install_node (&zebra_node, zebra_config_write);
+ install_element(BABEL_NODE, &babel_redistribute_type_cmd);
+ install_element(BABEL_NODE, &no_babel_redistribute_type_cmd);
+ install_element(ENABLE_NODE, &debug_babel_cmd);
+ install_element(ENABLE_NODE, &no_debug_babel_cmd);
+ install_element(CONFIG_NODE, &debug_babel_cmd);
+ install_element(CONFIG_NODE, &no_debug_babel_cmd);
+}
+
+static int
+zebra_config_write (struct vty *vty)
+{
+ if (! zclient->enable)
+ {
+ vty_out (vty, "no router zebra%s", VTY_NEWLINE);
+ return 1;
+ }
+ else if (! zclient->redist[ZEBRA_ROUTE_BABEL])
+ {
+ vty_out (vty, "router zebra%s", VTY_NEWLINE);
+ vty_out (vty, " no redistribute babel%s", VTY_NEWLINE);
+ return 1;
+ }
+ return 0;
+}
+
+void
+babel_zebra_close_connexion(void)
+{
+ zclient_stop(zclient);
+}
diff --git a/babeld/babel_zebra.h b/babeld/babel_zebra.h
new file mode 100644
index 00000000..99601aa7
--- /dev/null
+++ b/babeld/babel_zebra.h
@@ -0,0 +1,50 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#ifndef BABEL_ZEBRA_H
+#define BABEL_ZEBRA_H
+
+#include "vty.h"
+
+extern struct zclient *zclient;
+
+void babelz_zebra_init(void);
+void babel_zebra_close_connexion(void);
+extern int debug_babel_config_write (struct vty *);
+
+#endif
diff --git a/babeld/babeld.c b/babeld/babeld.c
new file mode 100644
index 00000000..1ae3f042
--- /dev/null
+++ b/babeld/babeld.c
@@ -0,0 +1,728 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+
+Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include <zebra.h>
+#include "command.h"
+#include "prefix.h"
+#include "memory.h"
+#include "memtypes.h"
+#include "table.h"
+#include "distribute.h"
+#include "prefix.h"
+#include "filter.h"
+#include "plist.h"
+
+#include "babel_main.h"
+#include "babeld.h"
+#include "util.h"
+#include "net.h"
+#include "kernel.h"
+#include "babel_interface.h"
+#include "neighbour.h"
+#include "route.h"
+#include "message.h"
+#include "resend.h"
+#include "babel_filter.h"
+#include "babel_zebra.h"
+
+
+static int babel_init_routing_process(struct thread *thread);
+static void babel_get_myid(void);
+static void babel_initial_noise(void);
+static int babel_read_protocol (struct thread *thread);
+static int babel_main_loop(struct thread *thread);
+static void babel_set_timer(struct timeval *timeout);
+static void babel_fill_with_next_timeout(struct timeval *tv);
+
+
+/* Informations relative to the babel running daemon. */
+static struct babel *babel_routing_process = NULL;
+static unsigned char *receive_buffer = NULL;
+static int receive_buffer_size = 0;
+
+/* timeouts */
+struct timeval check_neighbours_timeout;
+static time_t expiry_time;
+static time_t source_expiry_time;
+
+/* Babel node structure. */
+static struct cmd_node cmd_babel_node =
+{
+ .node = BABEL_NODE,
+ .prompt = "%s(config-router)# ",
+ .vtysh = 1,
+};
+
+/* print current babel configuration on vty */
+static int
+babel_config_write (struct vty *vty)
+{
+ int lines = 0;
+ int i;
+
+ /* list enabled debug modes */
+ lines += debug_babel_config_write (vty);
+
+ if (!babel_routing_process)
+ return lines;
+ vty_out (vty, "router babel%s", VTY_NEWLINE);
+ if (resend_delay != BABEL_DEFAULT_RESEND_DELAY)
+ {
+ vty_out (vty, " babel resend-delay %u%s", resend_delay, VTY_NEWLINE);
+ lines++;
+ }
+ /* list enabled interfaces */
+ lines = 1 + babel_enable_if_config_write (vty);
+ /* list redistributed protocols */
+ for (i = 0; i < ZEBRA_ROUTE_MAX; i++)
+ if (i != zclient->redist_default && zclient->redist[i])
+ {
+ vty_out (vty, " redistribute %s%s", zebra_route_string (i), VTY_NEWLINE);
+ lines++;
+ }
+
+ return lines;
+}
+
+
+static int
+babel_create_routing_process (void)
+{
+ assert (babel_routing_process == NULL);
+
+ /* Allocaste Babel instance. */
+ babel_routing_process = XCALLOC (MTYPE_BABEL, sizeof (struct babel));
+
+ /* Initialize timeouts */
+ gettime(&babel_now);
+ expiry_time = babel_now.tv_sec + roughly(30);
+ source_expiry_time = babel_now.tv_sec + roughly(300);
+
+ /* Make socket for Babel protocol. */
+ protocol_socket = babel_socket(protocol_port);
+ if (protocol_socket < 0) {
+ zlog_err("Couldn't create link local socket: %s", safe_strerror(errno));
+ goto fail;
+ }
+
+ /* Threads. */
+ babel_routing_process->t_read =
+ thread_add_read(master, &babel_read_protocol, NULL, protocol_socket);
+ /* wait a little: zebra will announce interfaces, addresses, routes... */
+ babel_routing_process->t_update =
+ thread_add_timer_msec(master, &babel_init_routing_process, NULL, 200L);
+ return 0;
+
+fail:
+ XFREE(MTYPE_BABEL, babel_routing_process);
+ babel_routing_process = NULL;
+ return -1;
+}
+
+/* thread reading entries form others babel daemons */
+static int
+babel_read_protocol (struct thread *thread)
+{
+ int rc;
+ struct interface *ifp = NULL;
+ struct sockaddr_in6 sin6;
+ struct listnode *linklist_node = NULL;
+
+ assert(babel_routing_process != NULL);
+ assert(protocol_socket >= 0);
+
+ rc = babel_recv(protocol_socket,
+ receive_buffer, receive_buffer_size,
+ (struct sockaddr*)&sin6, sizeof(sin6));
+ if(rc < 0) {
+ if(errno != EAGAIN && errno != EINTR) {
+ zlog_err("recv: %s", safe_strerror(errno));
+ }
+ } else {
+ FOR_ALL_INTERFACES(ifp, linklist_node) {
+ if(!if_up(ifp))
+ continue;
+ if(ifp->ifindex == sin6.sin6_scope_id) {
+ parse_packet((unsigned char*)&sin6.sin6_addr, ifp,
+ receive_buffer, rc);
+ break;
+ }
+ }
+ }
+
+ /* re-add thread */
+ babel_routing_process->t_read =
+ thread_add_read(master, &babel_read_protocol, NULL, protocol_socket);
+ return 0;
+}
+
+/* Zebra will give some information, especially about interfaces. This function
+ must be call with a litte timeout wich may give zebra the time to do his job,
+ making these inits have sense. */
+static int
+babel_init_routing_process(struct thread *thread)
+{
+ myseqno = (random() & 0xFFFF);
+ babel_get_myid();
+ babel_load_state_file();
+ debugf(BABEL_DEBUG_COMMON, "My ID is : %s.", format_eui64(myid));
+ babel_initial_noise();
+ babel_main_loop(thread);/* this function self-add to the t_update thread */
+ return 0;
+}
+
+/* fill "myid" with an unique id (only if myid != {0}). */
+static void
+babel_get_myid(void)
+{
+ struct interface *ifp = NULL;
+ struct listnode *linklist_node = NULL;
+ int rc;
+ int i;
+
+ /* if we already have an id (from state file), we return. */
+ if (memcmp(myid, zeroes, 8) != 0) {
+ return;
+ }
+
+ FOR_ALL_INTERFACES(ifp, linklist_node) {
+ /* ifp->ifindex is not necessarily valid at this point */
+ int ifindex = if_nametoindex(ifp->name);
+ if(ifindex > 0) {
+ unsigned char eui[8];
+ rc = if_eui64(ifp->name, ifindex, eui);
+ if(rc < 0)
+ continue;
+ memcpy(myid, eui, 8);
+ return;
+ }
+ }
+
+ /* We failed to get a global EUI64 from the interfaces we were given.
+ Let's try to find an interface with a MAC address. */
+ for(i = 1; i < 256; i++) {
+ char buf[IF_NAMESIZE], *ifname;
+ unsigned char eui[8];
+ ifname = if_indextoname(i, buf);
+ if(ifname == NULL)
+ continue;
+ rc = if_eui64(ifname, i, eui);
+ if(rc < 0)
+ continue;
+ memcpy(myid, eui, 8);
+ return;
+ }
+
+ zlog_err("Warning: couldn't find router id -- using random value.");
+
+ rc = read_random_bytes(myid, 8);
+ if(rc < 0) {
+ zlog_err("read(random): %s (cannot assign an ID)",safe_strerror(errno));
+ exit(1);
+ }
+ /* Clear group and global bits */
+ myid[0] &= ~3;
+}
+
+/* Make some noise so that others notice us, and send retractions in
+ case we were restarted recently */
+static void
+babel_initial_noise(void)
+{
+ struct interface *ifp = NULL;
+ struct listnode *linklist_node = NULL;
+
+ FOR_ALL_INTERFACES(ifp, linklist_node) {
+ if(!if_up(ifp))
+ continue;
+ /* Apply jitter before we send the first message. */
+ usleep(roughly(10000));
+ gettime(&babel_now);
+ send_hello(ifp);
+ send_wildcard_retraction(ifp);
+ }
+
+ FOR_ALL_INTERFACES(ifp, linklist_node) {
+ if(!if_up(ifp))
+ continue;
+ usleep(roughly(10000));
+ gettime(&babel_now);
+ send_hello(ifp);
+ send_wildcard_retraction(ifp);
+ send_self_update(ifp);
+ send_request(ifp, NULL, 0);
+ flushupdates(ifp);
+ flushbuf(ifp);
+ }
+}
+
+/* Delete all the added babel routes, make babeld only speak to zebra. */
+static void
+babel_clean_routing_process()
+{
+ flush_all_routes();
+ babel_interface_close_all();
+
+ /* cancel threads */
+ if (babel_routing_process->t_read != NULL) {
+ thread_cancel(babel_routing_process->t_read);
+ }
+ if (babel_routing_process->t_update != NULL) {
+ thread_cancel(babel_routing_process->t_update);
+ }
+
+ XFREE(MTYPE_BABEL, babel_routing_process);
+ babel_routing_process = NULL;
+}
+
+/* Function used with timeout. */
+static int
+babel_main_loop(struct thread *thread)
+{
+ struct timeval tv;
+ struct interface *ifp = NULL;
+ struct listnode *linklist_node = NULL;
+
+ while(1) {
+ gettime(&babel_now);
+
+ /* timeouts --------------------------------------------------------- */
+ /* get the next timeout */
+ babel_fill_with_next_timeout(&tv);
+ /* if there is no timeout, we must wait. */
+ if(timeval_compare(&tv, &babel_now) > 0) {
+ timeval_minus(&tv, &tv, &babel_now);
+ debugf(BABEL_DEBUG_TIMEOUT, "babel main loop : timeout: %ld msecs",
+ tv.tv_sec * 1000 + tv.tv_usec / 1000);
+ /* it happens often to have less than 1 ms, it's bad. */
+ timeval_add_msec(&tv, &tv, 300);
+ babel_set_timer(&tv);
+ return 0;
+ }
+
+ gettime(&babel_now);
+
+ /* update database -------------------------------------------------- */
+ if(timeval_compare(&check_neighbours_timeout, &babel_now) < 0) {
+ int msecs;
+ msecs = check_neighbours();
+ msecs = MAX(msecs, 10);
+ schedule_neighbours_check(msecs, 1);
+ }
+
+ if(babel_now.tv_sec >= expiry_time) {
+ expire_routes();
+ expire_resend();
+ expiry_time = babel_now.tv_sec + roughly(30);
+ }
+
+ if(babel_now.tv_sec >= source_expiry_time) {
+ expire_sources();
+ source_expiry_time = babel_now.tv_sec + roughly(300);
+ }
+
+ FOR_ALL_INTERFACES(ifp, linklist_node) {
+ babel_interface_nfo *babel_ifp = NULL;
+ if(!if_up(ifp))
+ continue;
+ babel_ifp = babel_get_if_nfo(ifp);
+ if(timeval_compare(&babel_now, &babel_ifp->hello_timeout) >= 0)
+ send_hello(ifp);
+ if(timeval_compare(&babel_now, &babel_ifp->update_timeout) >= 0)
+ send_update(ifp, 0, NULL, 0);
+ if(timeval_compare(&babel_now,
+ &babel_ifp->update_flush_timeout) >= 0)
+ flushupdates(ifp);
+ }
+
+ if(resend_time.tv_sec != 0) {
+ if(timeval_compare(&babel_now, &resend_time) >= 0)
+ do_resend();
+ }
+
+ if(unicast_flush_timeout.tv_sec != 0) {
+ if(timeval_compare(&babel_now, &unicast_flush_timeout) >= 0)
+ flush_unicast(1);
+ }
+
+ FOR_ALL_INTERFACES(ifp, linklist_node) {
+ babel_interface_nfo *babel_ifp = NULL;
+ if(!if_up(ifp))
+ continue;
+ babel_ifp = babel_get_if_nfo(ifp);
+ if(babel_ifp->flush_timeout.tv_sec != 0) {
+ if(timeval_compare(&babel_now, &babel_ifp->flush_timeout) >= 0)
+ flushbuf(ifp);
+ }
+ }
+ }
+
+ assert(0); /* this line should never be reach */
+}
+
+static void
+printIfMin(struct timeval *tv, int cmd, const char *tag, const char *ifname)
+{
+ static struct timeval curr_tv;
+ static char buffer[200];
+ static const char *curr_tag = NULL;
+
+ switch (cmd) {
+ case 0: /* reset timeval */
+ curr_tv = *tv;
+ if(ifname != NULL) {
+ snprintf(buffer, 200L, "interface: %s; %s", ifname, tag);
+ curr_tag = buffer;
+ } else {
+ curr_tag = tag;
+ }
+ break;
+ case 1: /* take the min */
+ if (tv->tv_sec == 0 && tv->tv_usec == 0) { /* if (tv == ∞) */
+ break;
+ }
+ if (tv->tv_sec < curr_tv.tv_sec ||(tv->tv_sec == curr_tv.tv_sec &&
+ tv->tv_usec < curr_tv.tv_usec)) {
+ curr_tv = *tv;
+ if(ifname != NULL) {
+ snprintf(buffer, 200L, "interface: %s; %s", ifname, tag);
+ curr_tag = buffer;
+ } else {
+ curr_tag = tag;
+ }
+ }
+ break;
+ case 2: /* print message */
+ debugf(BABEL_DEBUG_TIMEOUT, "next timeout due to: %s", curr_tag);
+ break;
+ default:
+ break;
+ }
+}
+
+static void
+babel_fill_with_next_timeout(struct timeval *tv)
+{
+#if (defined NO_DEBUG)
+#define printIfMin(a,b,c,d)
+#else
+#define printIfMin(a,b,c,d) \
+ if (UNLIKELY(debug & BABEL_DEBUG_TIMEOUT)) {printIfMin(a,b,c,d);}
+
+ struct interface *ifp = NULL;
+ struct listnode *linklist_node = NULL;
+
+ *tv = check_neighbours_timeout;
+ printIfMin(tv, 0, "check_neighbours_timeout", NULL);
+ timeval_min_sec(tv, expiry_time);
+ printIfMin(tv, 1, "expiry_time", NULL);
+ timeval_min_sec(tv, source_expiry_time);
+ printIfMin(tv, 1, "source_expiry_time", NULL);
+ timeval_min(tv, &resend_time);
+ printIfMin(tv, 1, "resend_time", NULL);
+ FOR_ALL_INTERFACES(ifp, linklist_node) {
+ babel_interface_nfo *babel_ifp = NULL;
+ if(!if_up(ifp))
+ continue;
+ babel_ifp = babel_get_if_nfo(ifp);
+ timeval_min(tv, &babel_ifp->flush_timeout);
+ printIfMin(tv, 1, "flush_timeout", ifp->name);
+ timeval_min(tv, &babel_ifp->hello_timeout);
+ printIfMin(tv, 1, "hello_timeout", ifp->name);
+ timeval_min(tv, &babel_ifp->update_timeout);
+ printIfMin(tv, 1, "update_timeout", ifp->name);
+ timeval_min(tv, &babel_ifp->update_flush_timeout);
+ printIfMin(tv, 1, "update_flush_timeout",ifp->name);
+ }
+ timeval_min(tv, &unicast_flush_timeout);
+ printIfMin(tv, 1, "unicast_flush_timeout", NULL);
+ printIfMin(tv, 2, NULL, NULL);
+#undef printIfMin
+#endif
+}
+
+/* set the t_update thread of the babel routing process to be launch in
+ 'timeout' (approximate at the milisecond) */
+static void
+babel_set_timer(struct timeval *timeout)
+{
+ long msecs = timeout->tv_sec * 1000 + timeout->tv_usec / 1000;
+ if (babel_routing_process->t_update != NULL) {
+ thread_cancel(babel_routing_process->t_update);
+ }
+ babel_routing_process->t_update =
+ thread_add_timer_msec(master, &babel_main_loop, NULL, msecs);
+}
+
+/* Schedule a neighbours check after roughly 3/2 times msecs have elapsed. */
+void
+schedule_neighbours_check(int msecs, int override)
+{
+ struct timeval timeout;
+
+ timeval_add_msec(&timeout, &babel_now, roughly(msecs * 3 / 2));
+ if(override)
+ check_neighbours_timeout = timeout;
+ else
+ timeval_min(&check_neighbours_timeout, &timeout);
+}
+
+int
+resize_receive_buffer(int size)
+{
+ if(size <= receive_buffer_size)
+ return 0;
+
+ if(receive_buffer == NULL) {
+ receive_buffer = malloc(size);
+ if(receive_buffer == NULL) {
+ zlog_err("malloc(receive_buffer): %s", safe_strerror(errno));
+ return -1;
+ }
+ receive_buffer_size = size;
+ } else {
+ unsigned char *new;
+ new = realloc(receive_buffer, size);
+ if(new == NULL) {
+ zlog_err("realloc(receive_buffer): %s", safe_strerror(errno));
+ return -1;
+ }
+ receive_buffer = new;
+ receive_buffer_size = size;
+ }
+ return 1;
+}
+
+static void
+babel_distribute_update (struct distribute *dist)
+{
+ struct interface *ifp;
+ babel_interface_nfo *babel_ifp;
+ struct access_list *alist;
+ struct prefix_list *plist;
+
+ if (! dist->ifname)
+ return;
+
+ ifp = if_lookup_by_name (dist->ifname);
+ if (ifp == NULL)
+ return;
+
+ babel_ifp = babel_get_if_nfo(ifp);
+
+ if (dist->list[DISTRIBUTE_IN]) {
+ alist = access_list_lookup (AFI_IP6, dist->list[DISTRIBUTE_IN]);
+ if (alist)
+ babel_ifp->list[BABEL_FILTER_IN] = alist;
+ else
+ babel_ifp->list[BABEL_FILTER_IN] = NULL;
+ } else {
+ babel_ifp->list[BABEL_FILTER_IN] = NULL;
+ }
+
+ if (dist->list[DISTRIBUTE_OUT]) {
+ alist = access_list_lookup (AFI_IP6, dist->list[DISTRIBUTE_OUT]);
+ if (alist)
+ babel_ifp->list[BABEL_FILTER_OUT] = alist;
+ else
+ babel_ifp->list[BABEL_FILTER_OUT] = NULL;
+ } else {
+ babel_ifp->list[BABEL_FILTER_OUT] = NULL;
+ }
+
+ if (dist->prefix[DISTRIBUTE_IN]) {
+ plist = prefix_list_lookup (AFI_IP6, dist->prefix[DISTRIBUTE_IN]);
+ if (plist)
+ babel_ifp->prefix[BABEL_FILTER_IN] = plist;
+ else
+ babel_ifp->prefix[BABEL_FILTER_IN] = NULL;
+ } else {
+ babel_ifp->prefix[BABEL_FILTER_IN] = NULL;
+ }
+
+ if (dist->prefix[DISTRIBUTE_OUT]) {
+ plist = prefix_list_lookup (AFI_IP6, dist->prefix[DISTRIBUTE_OUT]);
+ if (plist)
+ babel_ifp->prefix[BABEL_FILTER_OUT] = plist;
+ else
+ babel_ifp->prefix[BABEL_FILTER_OUT] = NULL;
+ } else {
+ babel_ifp->prefix[BABEL_FILTER_OUT] = NULL;
+ }
+}
+
+static void
+babel_distribute_update_interface (struct interface *ifp)
+{
+ struct distribute *dist;
+
+ dist = distribute_lookup (ifp->name);
+ if (dist)
+ babel_distribute_update (dist);
+}
+
+/* Update all interface's distribute list. */
+static void
+babel_distribute_update_all (struct prefix_list *notused)
+{
+ struct interface *ifp;
+ struct listnode *node;
+
+ for (ALL_LIST_ELEMENTS_RO (iflist, node, ifp))
+ babel_distribute_update_interface (ifp);
+}
+
+static void
+babel_distribute_update_all_wrapper (struct access_list *notused)
+{
+ babel_distribute_update_all(NULL);
+}
+
+
+/* [Command] */
+DEFUN (router_babel,
+ router_babel_cmd,
+ "router babel",
+ "Enable a routing process\n"
+ "Make Babel instance command\n"
+ "No attributes\n")
+{
+ int ret;
+
+ vty->node = BABEL_NODE;
+
+ if (!babel_routing_process) {
+ ret = babel_create_routing_process ();
+
+ /* Notice to user we couldn't create Babel. */
+ if (ret < 0) {
+ zlog_warn ("can't create Babel");
+ return CMD_WARNING;
+ }
+ }
+
+ return CMD_SUCCESS;
+}
+
+/* [Command] */
+DEFUN (no_router_babel,
+ no_router_babel_cmd,
+ "no router babel",
+ NO_STR
+ "Disable a routing process\n"
+ "Remove Babel instance command\n"
+ "No attributes\n")
+{
+ if(babel_routing_process)
+ babel_clean_routing_process();
+ return CMD_SUCCESS;
+}
+
+/* [Babel Command] */
+DEFUN (babel_set_resend_delay,
+ babel_set_resend_delay_cmd,
+ "babel resend-delay <20-655340>",
+ "Babel commands\n"
+ "Time before resending a message\n"
+ "Milliseconds\n")
+{
+ int interval;
+
+ VTY_GET_INTEGER_RANGE("milliseconds", interval, argv[0], 20, 10 * 0xFFFE);
+
+ resend_delay = interval;
+ return CMD_SUCCESS;
+}
+
+void
+babeld_quagga_init(void)
+{
+
+ install_node(&cmd_babel_node, &babel_config_write);
+
+ install_element(CONFIG_NODE, &router_babel_cmd);
+ install_element(CONFIG_NODE, &no_router_babel_cmd);
+
+ install_default(BABEL_NODE);
+ install_element(BABEL_NODE, &babel_set_resend_delay_cmd);
+
+ babel_if_init();
+
+ /* Access list install. */
+ access_list_init ();
+ access_list_add_hook (babel_distribute_update_all_wrapper);
+ access_list_delete_hook (babel_distribute_update_all_wrapper);
+
+ /* Prefix list initialize.*/
+ prefix_list_init ();
+ prefix_list_add_hook (babel_distribute_update_all);
+ prefix_list_delete_hook (babel_distribute_update_all);
+
+ /* Distribute list install. */
+ distribute_list_init (BABEL_NODE);
+ distribute_list_add_hook (babel_distribute_update);
+ distribute_list_delete_hook (babel_distribute_update);
+}
+
+/* Stubs to adapt Babel's filtering calls to Quagga's infrastructure. */
+
+int
+input_filter(const unsigned char *id,
+ const unsigned char *prefix, unsigned short plen,
+ const unsigned char *neigh, unsigned int ifindex)
+{
+ return babel_filter(0, prefix, plen, ifindex);
+}
+
+int
+output_filter(const unsigned char *id, const unsigned char *prefix,
+ unsigned short plen, unsigned int ifindex)
+{
+ return babel_filter(1, prefix, plen, ifindex);
+}
+
+/* There's no redistribute filter in Quagga -- the zebra daemon does its
+ own filtering. */
+int
+redistribute_filter(const unsigned char *prefix, unsigned short plen,
+ unsigned int ifindex, int proto)
+{
+ return 0;
+}
+
diff --git a/babeld/babeld.conf.sample b/babeld/babeld.conf.sample
new file mode 100644
index 00000000..a4924ec7
--- /dev/null
+++ b/babeld/babeld.conf.sample
@@ -0,0 +1,30 @@
+debug babel common
+!debug babel kernel
+!debug babel filter
+!debug babel timeout
+!debug babel interface
+!debug babel route
+!debug babel all
+
+router babel
+! network wlan0
+! network eth0
+! redistribute kernel
+! no redistribute static
+
+! The defaults are fine for a wireless interface
+
+!interface wlan0
+
+! A few optimisation tweaks are optional but recommended on a wired interface
+! Disable link quality estimation, enable split horizon processing, and
+! increase the hello and update intervals.
+
+!interface eth0
+! babel wired
+! babel split-horizon
+! babel hello-interval 12000
+! babel update-interval 36000
+
+! log file /var/log/quagga/babeld.log
+log stdout
diff --git a/babeld/babeld.h b/babeld/babeld.h
new file mode 100644
index 00000000..b19ae0f2
--- /dev/null
+++ b/babeld/babeld.h
@@ -0,0 +1,141 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#ifndef BABEL_BABELD_H
+#define BABEL_BABELD_H
+
+#include <zebra.h>
+#include "vty.h"
+
+#define INFINITY ((unsigned short)(~0))
+
+#ifndef RTPROT_BABEL
+#define RTPROT_BABEL 42
+#endif
+
+#define RTPROT_BABEL_LOCAL -2
+
+#undef MAX
+#undef MIN
+
+#define MAX(x,y) ((x)<=(y)?(y):(x))
+#define MIN(x,y) ((x)<=(y)?(x):(y))
+
+#if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L
+/* nothing */
+#elif defined(__GNUC__)
+#define inline __inline
+#if (__GNUC__ >= 3)
+#define restrict __restrict
+#else
+#define restrict /**/
+#endif
+#else
+#define inline /**/
+#define restrict /**/
+#endif
+
+#if defined(__GNUC__) && (__GNUC__ >= 3)
+#define ATTRIBUTE(x) __attribute__ (x)
+#define LIKELY(_x) __builtin_expect(!!(_x), 1)
+#define UNLIKELY(_x) __builtin_expect(!!(_x), 0)
+#else
+#define ATTRIBUTE(x) /**/
+#define LIKELY(_x) !!(_x)
+#define UNLIKELY(_x) !!(_x)
+#endif
+
+#if defined(__GNUC__) && (__GNUC__ >= 4) && (__GNUC_MINOR__ >= 3)
+#define COLD __attribute__ ((cold))
+#else
+#define COLD /**/
+#endif
+
+#ifndef IF_NAMESIZE
+#include <sys/socket.h>
+#include <net/if.h>
+#endif
+
+#ifdef HAVE_VALGRIND
+#include <valgrind/memcheck.h>
+#else
+#ifndef VALGRIND_MAKE_MEM_UNDEFINED
+#define VALGRIND_MAKE_MEM_UNDEFINED(a, b) do {} while(0)
+#endif
+#ifndef VALGRIND_CHECK_MEM_IS_DEFINED
+#define VALGRIND_CHECK_MEM_IS_DEFINED(a, b) do {} while(0)
+#endif
+#endif
+
+
+#define BABEL_VTY_PORT 2609
+#define BABEL_DEFAULT_CONFIG "babeld.conf"
+#define BABEL_VERSION "0.1 for quagga"
+
+/* Values in milliseconds */
+#define BABEL_DEFAULT_HELLO_INTERVAL 4000
+#define BABEL_DEFAULT_UPDATE_INTERVAL 16000
+#define BABEL_DEFAULT_RESEND_DELAY 2000
+
+
+/* Babel socket. */
+extern int protocol_socket;
+
+/* Babel structure. */
+struct babel
+{
+ /* Babel threads. */
+ struct thread *t_read; /* on Babel protocol's socket */
+ struct thread *t_update; /* timers */
+};
+
+
+extern void babeld_quagga_init(void);
+extern int input_filter(const unsigned char *id,
+ const unsigned char *prefix, unsigned short plen,
+ const unsigned char *neigh, unsigned int ifindex);
+extern int output_filter(const unsigned char *id, const unsigned char *prefix,
+ unsigned short plen, unsigned int ifindex);
+extern int redistribute_filter(const unsigned char *prefix, unsigned short plen,
+ unsigned int ifindex, int proto);
+extern int resize_receive_buffer(int size);
+extern void schedule_neighbours_check(int msecs, int override);
+
+
+#endif /* BABEL_BABELD_H */
diff --git a/babeld/kernel.c b/babeld/kernel.c
new file mode 100644
index 00000000..c31f617b
--- /dev/null
+++ b/babeld/kernel.c
@@ -0,0 +1,76 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+
+Copyright 2007, 2008 by Grégoire Henry, Julien Cristau and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include <sys/time.h>
+#include <sys/param.h>
+#include <time.h>
+
+#include "babeld.h"
+
+#include "kernel_zebra.c"
+
+/* Like gettimeofday, but returns monotonic time. If POSIX clocks are not
+ available, falls back to gettimeofday but enforces monotonicity. */
+int
+gettime(struct timeval *tv)
+{
+ return quagga_gettime(QUAGGA_CLK_MONOTONIC, tv);
+}
+
+/* If /dev/urandom doesn't exist, this will fail with ENOENT, which the
+ caller will deal with gracefully. */
+
+int
+read_random_bytes(void *buf, size_t len)
+{
+ int fd;
+ int rc;
+
+ fd = open("/dev/urandom", O_RDONLY);
+ if(fd < 0) {
+ rc = -1;
+ } else {
+ rc = read(fd, buf, len);
+ if(rc < 0 || (unsigned) rc < len)
+ rc = -1;
+ close(fd);
+ }
+ return rc;
+}
+
diff --git a/babeld/kernel.h b/babeld/kernel.h
new file mode 100644
index 00000000..e8c8f9b7
--- /dev/null
+++ b/babeld/kernel.h
@@ -0,0 +1,69 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include <netinet/in.h>
+#include "babel_main.h"
+#include "if.h"
+
+#define KERNEL_INFINITY 0xFFFF
+
+struct kernel_route {
+ unsigned char prefix[16];
+ int plen;
+ int metric;
+ unsigned int ifindex;
+ int proto;
+ unsigned char gw[16];
+};
+
+#define ROUTE_FLUSH 0
+#define ROUTE_ADD 1
+#define ROUTE_MODIFY 2
+
+extern int export_table, import_table;
+
+int kernel_interface_operational(struct interface *interface);
+int kernel_interface_mtu(struct interface *interface);
+int kernel_interface_wireless(struct interface *interface);
+int kernel_route(int operation, const unsigned char *dest, unsigned short plen,
+ const unsigned char *gate, int ifindex, unsigned int metric,
+ const unsigned char *newgate, int newifindex,
+ unsigned int newmetric);
+int if_eui64(char *ifname, int ifindex, unsigned char *eui);
+int gettime(struct timeval *tv);
+int read_random_bytes(void *buf, size_t len);
diff --git a/babeld/kernel_zebra.c b/babeld/kernel_zebra.c
new file mode 100644
index 00000000..db7d0b39
--- /dev/null
+++ b/babeld/kernel_zebra.c
@@ -0,0 +1,275 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include <sys/types.h>
+#include <sys/socket.h>
+#include <netinet/in.h>
+#include <netdb.h>
+#include <arpa/inet.h>
+
+#include <zebra.h>
+#include "prefix.h"
+#include "zclient.h"
+#include "kernel.h"
+#include "privs.h"
+#include "command.h"
+#include "vty.h"
+#include "memory.h"
+#include "thread.h"
+
+#include "util.h"
+#include "babel_interface.h"
+#include "babel_zebra.h"
+
+
+static int
+kernel_route_v4(int add, const unsigned char *pref, unsigned short plen,
+ const unsigned char *gate, int ifindex,
+ unsigned int metric);
+static int
+kernel_route_v6(int add, const unsigned char *pref, unsigned short plen,
+ const unsigned char *gate, int ifindex,
+ unsigned int metric);
+
+int
+kernel_interface_operational(struct interface *interface)
+{
+ return if_is_operative(interface);
+}
+
+int
+kernel_interface_mtu(struct interface *interface)
+{
+ return MIN(interface->mtu, interface->mtu6);
+}
+
+int
+kernel_interface_wireless(struct interface *interface)
+{
+ return 0;
+}
+
+int
+kernel_route(int operation, const unsigned char *pref, unsigned short plen,
+ const unsigned char *gate, int ifindex, unsigned int metric,
+ const unsigned char *newgate, int newifindex,
+ unsigned int newmetric)
+{
+ int rc;
+ int ipv4;
+
+ /* Check that the protocol family is consistent. */
+ if(plen >= 96 && v4mapped(pref)) {
+ if(!v4mapped(gate)) {
+ errno = EINVAL;
+ return -1;
+ }
+ ipv4 = 1;
+ } else {
+ if(v4mapped(gate)) {
+ errno = EINVAL;
+ return -1;
+ }
+ ipv4 = 0;
+ }
+
+ switch (operation) {
+ case ROUTE_ADD:
+ return ipv4 ?
+ kernel_route_v4(1, pref, plen, gate, ifindex, metric):
+ kernel_route_v6(1, pref, plen, gate, ifindex, metric);
+ break;
+ case ROUTE_FLUSH:
+ return ipv4 ?
+ kernel_route_v4(0, pref, plen, gate, ifindex, metric):
+ kernel_route_v6(0, pref, plen, gate, ifindex, metric);
+ break;
+ case ROUTE_MODIFY:
+ if(newmetric == metric && memcmp(newgate, gate, 16) == 0 &&
+ newifindex == ifindex)
+ return 0;
+ debugf(BABEL_DEBUG_ROUTE, "Modify route: delete old; add new.");
+ rc = ipv4 ?
+ kernel_route_v4(0, pref, plen, gate, ifindex, metric):
+ kernel_route_v6(0, pref, plen, gate, ifindex, metric);
+
+ if (rc < 0)
+ return -1;
+
+ rc = ipv4 ?
+ kernel_route_v4(1, pref, plen, newgate, newifindex, newmetric):
+ kernel_route_v6(1, pref, plen, newgate, newifindex, newmetric);
+
+ return rc;
+ break;
+ default:
+ zlog_err("this should never appens (false value - kernel_route)");
+ assert(0);
+ exit(1);
+ break;
+ }
+}
+
+static int
+kernel_route_v4(int add,
+ const unsigned char *pref, unsigned short plen,
+ const unsigned char *gate, int ifindex, unsigned int metric)
+{
+ struct zapi_ipv4 api; /* quagga's communication system */
+ struct prefix_ipv4 quagga_prefix; /* quagga's prefix */
+ struct in_addr babel_prefix_addr; /* babeld's prefix addr */
+ struct in_addr nexthop; /* next router to go */
+ struct in_addr *nexthop_pointer = &nexthop; /* it's an array! */
+
+ /* convert to be understandable by quagga */
+ /* convert given addresses */
+ uchar_to_inaddr(&babel_prefix_addr, pref);
+ uchar_to_inaddr(&nexthop, gate);
+
+ /* make prefix structure */
+ memset (&quagga_prefix, 0, sizeof(quagga_prefix));
+ quagga_prefix.family = AF_INET;
+ IPV4_ADDR_COPY (&quagga_prefix.prefix, &babel_prefix_addr);
+ quagga_prefix.prefixlen = plen - 96; /* our plen is for v4mapped's addr */
+ apply_mask_ipv4(&quagga_prefix);
+
+ api.type = ZEBRA_ROUTE_BABEL;
+ api.flags = 0;
+ api.message = 0;
+ api.safi = SAFI_UNICAST;
+
+ /* Unlike the native Linux and BSD interfaces, Quagga doesn't like
+ there to be both and IPv4 nexthop and an ifindex. Omit the
+ ifindex, and assume that the connected prefixes be set up
+ correctly. */
+
+ SET_FLAG(api.message, ZAPI_MESSAGE_NEXTHOP);
+ api.ifindex_num = 0;
+ if(metric >= KERNEL_INFINITY) {
+ api.flags = ZEBRA_FLAG_BLACKHOLE;
+ api.nexthop_num = 0;
+ } else {
+ api.nexthop_num = 1;
+ api.nexthop = &nexthop_pointer;
+ SET_FLAG(api.message, ZAPI_MESSAGE_METRIC);
+ api.metric = metric;
+ }
+
+ debugf(BABEL_DEBUG_ROUTE, "%s route (ipv4) to zebra",
+ add ? "adding" : "removing" );
+ return zapi_ipv4_route (add ? ZEBRA_IPV4_ROUTE_ADD :
+ ZEBRA_IPV4_ROUTE_DELETE,
+ zclient, &quagga_prefix, &api);
+}
+
+static int
+kernel_route_v6(int add, const unsigned char *pref, unsigned short plen,
+ const unsigned char *gate, int ifindex, unsigned int metric)
+{
+ unsigned int tmp_ifindex = ifindex; /* (for typing) */
+ struct zapi_ipv6 api; /* quagga's communication system */
+ struct prefix_ipv6 quagga_prefix; /* quagga's prefix */
+ struct in6_addr babel_prefix_addr; /* babeld's prefix addr */
+ struct in6_addr nexthop; /* next router to go */
+ struct in6_addr *nexthop_pointer = &nexthop;
+
+ /* convert to be understandable by quagga */
+ /* convert given addresses */
+ uchar_to_in6addr(&babel_prefix_addr, pref);
+ uchar_to_in6addr(&nexthop, gate);
+
+ /* make prefix structure */
+ memset (&quagga_prefix, 0, sizeof(quagga_prefix));
+ quagga_prefix.family = AF_INET6;
+ IPV6_ADDR_COPY (&quagga_prefix.prefix, &babel_prefix_addr);
+ quagga_prefix.prefixlen = plen;
+ apply_mask_ipv6(&quagga_prefix);
+
+ api.type = ZEBRA_ROUTE_BABEL;
+ api.flags = 0;
+ api.message = 0;
+ api.safi = SAFI_UNICAST;
+ SET_FLAG(api.message, ZAPI_MESSAGE_NEXTHOP);
+ if(metric >= KERNEL_INFINITY) {
+ api.flags = ZEBRA_FLAG_BLACKHOLE;
+ api.nexthop_num = 0;
+ api.ifindex_num = 0;
+ } else {
+ api.nexthop_num = 1;
+ api.nexthop = &nexthop_pointer;
+ SET_FLAG(api.message, ZAPI_MESSAGE_IFINDEX);
+ api.ifindex_num = 1;
+ api.ifindex = &tmp_ifindex;
+ SET_FLAG(api.message, ZAPI_MESSAGE_METRIC);
+ api.metric = metric;
+ }
+
+ debugf(BABEL_DEBUG_ROUTE, "%s route (ipv6) to zebra",
+ add ? "adding" : "removing" );
+ return zapi_ipv6_route (add ? ZEBRA_IPV6_ROUTE_ADD :
+ ZEBRA_IPV6_ROUTE_DELETE,
+ zclient, &quagga_prefix, &api);
+}
+
+int
+if_eui64(char *ifname, int ifindex, unsigned char *eui)
+{
+ struct interface *ifp = if_lookup_by_index(ifindex);
+ if (ifp == NULL) {
+ return -1;
+ }
+#ifdef HAVE_STRUCT_SOCKADDR_DL
+ u_char len = ifp->sdl.sdl_alen;
+ char *tmp = ifp->sdl.sdl_data + ifp->sdl.sdl_nlen;
+#else
+ u_char len = (u_char) ifp->hw_addr_len;
+ char *tmp = (void*) ifp->hw_addr;
+#endif
+ if (len == 8) {
+ memcpy(eui, tmp, 8);
+ eui[0] ^= 2;
+ } else if (len == 6) {
+ memcpy(eui, tmp, 3);
+ eui[3] = 0xFF;
+ eui[4] = 0xFE;
+ memcpy(eui+5, tmp+3, 3);
+ } else {
+ return -1;
+ }
+ return 0;
+}
diff --git a/babeld/message.c b/babeld/message.c
new file mode 100644
index 00000000..9dcfc677
--- /dev/null
+++ b/babeld/message.c
@@ -0,0 +1,1561 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include <zebra.h>
+#include "if.h"
+
+#include "babeld.h"
+#include "util.h"
+#include "net.h"
+#include "babel_interface.h"
+#include "source.h"
+#include "neighbour.h"
+#include "route.h"
+#include "xroute.h"
+#include "resend.h"
+#include "message.h"
+#include "kernel.h"
+
+unsigned char packet_header[4] = {42, 2};
+
+int split_horizon = 1;
+
+unsigned short myseqno = 0;
+struct timeval seqno_time = {0, 0};
+
+#define UNICAST_BUFSIZE 1024
+int unicast_buffered = 0;
+unsigned char *unicast_buffer = NULL;
+struct neighbour *unicast_neighbour = NULL;
+struct timeval unicast_flush_timeout = {0, 0};
+
+static const unsigned char v4prefix[16] =
+ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF, 0, 0, 0, 0 };
+
+/* Parse a network prefix, encoded in the somewhat baroque compressed
+ representation used by Babel. Return the number of bytes parsed. */
+static int
+network_prefix(int ae, int plen, unsigned int omitted,
+ const unsigned char *p, const unsigned char *dp,
+ unsigned int len, unsigned char *p_r)
+{
+ unsigned pb;
+ unsigned char prefix[16];
+ int ret = -1;
+
+ if(plen >= 0)
+ pb = (plen + 7) / 8;
+ else if(ae == 1)
+ pb = 4;
+ else
+ pb = 16;
+
+ if(pb > 16)
+ return -1;
+
+ memset(prefix, 0, 16);
+
+ switch(ae) {
+ case 0:
+ ret = 0;
+ break;
+ case 1:
+ if(omitted > 4 || pb > 4 || (pb > omitted && len < pb - omitted))
+ return -1;
+ memcpy(prefix, v4prefix, 12);
+ if(omitted) {
+ if (dp == NULL || !v4mapped(dp)) return -1;
+ memcpy(prefix, dp, 12 + omitted);
+ }
+ if(pb > omitted) memcpy(prefix + 12 + omitted, p, pb - omitted);
+ ret = pb - omitted;
+ break;
+ case 2:
+ if(omitted > 16 || (pb > omitted && len < pb - omitted)) return -1;
+ if(omitted) {
+ if (dp == NULL || v4mapped(dp)) return -1;
+ memcpy(prefix, dp, omitted);
+ }
+ if(pb > omitted) memcpy(prefix + omitted, p, pb - omitted);
+ ret = pb - omitted;
+ break;
+ case 3:
+ if(pb > 8 && len < pb - 8) return -1;
+ prefix[0] = 0xfe;
+ prefix[1] = 0x80;
+ if(pb > 8) memcpy(prefix + 8, p, pb - 8);
+ ret = pb - 8;
+ break;
+ default:
+ return -1;
+ }
+
+ mask_prefix(p_r, prefix, plen < 0 ? 128 : ae == 1 ? plen + 96 : plen);
+ return ret;
+}
+
+static void
+parse_route_attributes(const unsigned char *a, int alen,
+ unsigned char *channels)
+{
+ int type, len, i = 0;
+
+ while(i < alen) {
+ type = a[i];
+ if(type == 0) {
+ i++;
+ continue;
+ }
+
+ if(i + 1 > alen) {
+ fprintf(stderr, "Received truncated attributes.\n");
+ return;
+ }
+ len = a[i + 1];
+ if(i + len > alen) {
+ fprintf(stderr, "Received truncated attributes.\n");
+ return;
+ }
+
+ if(type == 1) {
+ /* Nothing. */
+ } else if(type == 2) {
+ if(len > DIVERSITY_HOPS) {
+ fprintf(stderr,
+ "Received overlong channel information (%d > %d).\n",
+ len, DIVERSITY_HOPS);
+ len = DIVERSITY_HOPS;
+ }
+ if(memchr(a + i + 2, 0, len) != NULL) {
+ /* 0 is reserved. */
+ fprintf(stderr, "Channel information contains 0!");
+ return;
+ }
+ memset(channels, 0, DIVERSITY_HOPS);
+ memcpy(channels, a + i + 2, len);
+ } else {
+ fprintf(stderr, "Received unknown route attribute %d.\n", type);
+ }
+
+ i += len + 2;
+ }
+}
+
+static int
+network_address(int ae, const unsigned char *a, unsigned int len,
+ unsigned char *a_r)
+{
+ return network_prefix(ae, -1, 0, a, NULL, len, a_r);
+}
+
+static int
+channels_len(unsigned char *channels)
+{
+ unsigned char *p = memchr(channels, 0, DIVERSITY_HOPS);
+ return p ? (p - channels) : DIVERSITY_HOPS;
+}
+
+void
+parse_packet(const unsigned char *from, struct interface *ifp,
+ const unsigned char *packet, int packetlen)
+{
+ int i;
+ const unsigned char *message;
+ unsigned char type, len;
+ int bodylen;
+ struct neighbour *neigh;
+ int have_router_id = 0, have_v4_prefix = 0, have_v6_prefix = 0,
+ have_v4_nh = 0, have_v6_nh = 0;
+ unsigned char router_id[8], v4_prefix[16], v6_prefix[16],
+ v4_nh[16], v6_nh[16];
+
+ if(!linklocal(from)) {
+ zlog_err("Received packet from non-local address %s.",
+ format_address(from));
+ return;
+ }
+
+ if(packet[0] != 42) {
+ zlog_err("Received malformed packet on %s from %s.",
+ ifp->name, format_address(from));
+ return;
+ }
+
+ if(packet[1] != 2) {
+ zlog_err("Received packet with unknown version %d on %s from %s.",
+ packet[1], ifp->name, format_address(from));
+ return;
+ }
+
+ neigh = find_neighbour(from, ifp);
+ if(neigh == NULL) {
+ zlog_err("Couldn't allocate neighbour.");
+ return;
+ }
+
+ DO_NTOHS(bodylen, packet + 2);
+
+ if(bodylen + 4 > packetlen) {
+ zlog_err("Received truncated packet (%d + 4 > %d).",
+ bodylen, packetlen);
+ bodylen = packetlen - 4;
+ }
+
+ i = 0;
+ while(i < bodylen) {
+ message = packet + 4 + i;
+ type = message[0];
+ if(type == MESSAGE_PAD1) {
+ debugf(BABEL_DEBUG_COMMON,"Received pad1 from %s on %s.",
+ format_address(from), ifp->name);
+ i++;
+ continue;
+ }
+ if(i + 1 > bodylen) {
+ zlog_err("Received truncated message.");
+ break;
+ }
+ len = message[1];
+ if(i + len > bodylen) {
+ zlog_err("Received truncated message.");
+ break;
+ }
+
+ if(type == MESSAGE_PADN) {
+ debugf(BABEL_DEBUG_COMMON,"Received pad%d from %s on %s.",
+ len, format_address(from), ifp->name);
+ } else if(type == MESSAGE_ACK_REQ) {
+ unsigned short nonce, interval;
+ if(len < 6) goto fail;
+ DO_NTOHS(nonce, message + 4);
+ DO_NTOHS(interval, message + 6);
+ debugf(BABEL_DEBUG_COMMON,"Received ack-req (%04X %d) from %s on %s.",
+ nonce, interval, format_address(from), ifp->name);
+ send_ack(neigh, nonce, interval);
+ } else if(type == MESSAGE_ACK) {
+ debugf(BABEL_DEBUG_COMMON,"Received ack from %s on %s.",
+ format_address(from), ifp->name);
+ /* Nothing right now */
+ } else if(type == MESSAGE_HELLO) {
+ unsigned short seqno, interval;
+ int changed;
+ if(len < 6) goto fail;
+ DO_NTOHS(seqno, message + 4);
+ DO_NTOHS(interval, message + 6);
+ debugf(BABEL_DEBUG_COMMON,"Received hello %d (%d) from %s on %s.",
+ seqno, interval,
+ format_address(from), ifp->name);
+ changed = update_neighbour(neigh, seqno, interval);
+ update_neighbour_metric(neigh, changed);
+ if(interval > 0)
+ schedule_neighbours_check(interval * 10, 0);
+ } else if(type == MESSAGE_IHU) {
+ unsigned short txcost, interval;
+ unsigned char address[16];
+ int rc;
+ if(len < 6) goto fail;
+ DO_NTOHS(txcost, message + 4);
+ DO_NTOHS(interval, message + 6);
+ rc = network_address(message[2], message + 8, len - 6, address);
+ if(rc < 0) goto fail;
+ debugf(BABEL_DEBUG_COMMON,"Received ihu %d (%d) from %s on %s for %s.",
+ txcost, interval,
+ format_address(from), ifp->name,
+ format_address(address));
+ if(message[2] == 0 || is_interface_ll_address(ifp, address)) {
+ int changed = txcost != neigh->txcost;
+ neigh->txcost = txcost;
+ neigh->ihu_time = babel_now;
+ neigh->ihu_interval = interval;
+ update_neighbour_metric(neigh, changed);
+ if(interval > 0)
+ schedule_neighbours_check(interval * 10 * 3, 0);
+ }
+ } else if(type == MESSAGE_ROUTER_ID) {
+ if(len < 10) {
+ have_router_id = 0;
+ goto fail;
+ }
+ memcpy(router_id, message + 4, 8);
+ have_router_id = 1;
+ debugf(BABEL_DEBUG_COMMON,"Received router-id %s from %s on %s.",
+ format_eui64(router_id), format_address(from), ifp->name);
+ } else if(type == MESSAGE_NH) {
+ unsigned char nh[16];
+ int rc;
+ if(len < 2) {
+ have_v4_nh = 0;
+ have_v6_nh = 0;
+ goto fail;
+ }
+ rc = network_address(message[2], message + 4, len - 2,
+ nh);
+ if(rc < 0) {
+ have_v4_nh = 0;
+ have_v6_nh = 0;
+ goto fail;
+ }
+ debugf(BABEL_DEBUG_COMMON,"Received nh %s (%d) from %s on %s.",
+ format_address(nh), message[2],
+ format_address(from), ifp->name);
+ if(message[2] == 1) {
+ memcpy(v4_nh, nh, 16);
+ have_v4_nh = 1;
+ } else {
+ memcpy(v6_nh, nh, 16);
+ have_v6_nh = 1;
+ }
+ } else if(type == MESSAGE_UPDATE) {
+ unsigned char prefix[16], *nh;
+ unsigned char plen;
+ unsigned char channels[DIVERSITY_HOPS];
+ unsigned short interval, seqno, metric;
+ int rc, parsed_len;
+ if(len < 10) {
+ if(len < 2 || message[3] & 0x80)
+ have_v4_prefix = have_v6_prefix = 0;
+ goto fail;
+ }
+ DO_NTOHS(interval, message + 6);
+ DO_NTOHS(seqno, message + 8);
+ DO_NTOHS(metric, message + 10);
+ if(message[5] == 0 ||
+ (message[3] == 1 ? have_v4_prefix : have_v6_prefix))
+ rc = network_prefix(message[2], message[4], message[5],
+ message + 12,
+ message[2] == 1 ? v4_prefix : v6_prefix,
+ len - 10, prefix);
+ else
+ rc = -1;
+ if(rc < 0) {
+ if(message[3] & 0x80)
+ have_v4_prefix = have_v6_prefix = 0;
+ goto fail;
+ }
+ parsed_len = 10 + rc;
+
+ plen = message[4] + (message[2] == 1 ? 96 : 0);
+
+ if(message[3] & 0x80) {
+ if(message[2] == 1) {
+ memcpy(v4_prefix, prefix, 16);
+ have_v4_prefix = 1;
+ } else {
+ memcpy(v6_prefix, prefix, 16);
+ have_v6_prefix = 1;
+ }
+ }
+ if(message[3] & 0x40) {
+ if(message[2] == 1) {
+ memset(router_id, 0, 4);
+ memcpy(router_id + 4, prefix + 12, 4);
+ } else {
+ memcpy(router_id, prefix + 8, 8);
+ }
+ have_router_id = 1;
+ }
+ if(!have_router_id && message[2] != 0) {
+ zlog_err("Received prefix with no router id.");
+ goto fail;
+ }
+ debugf(BABEL_DEBUG_COMMON,"Received update%s%s for %s from %s on %s.",
+ (message[3] & 0x80) ? "/prefix" : "",
+ (message[3] & 0x40) ? "/id" : "",
+ format_prefix(prefix, plen),
+ format_address(from), ifp->name);
+
+ if(message[2] == 0) {
+ if(metric < 0xFFFF) {
+ zlog_err("Received wildcard update with finite metric.");
+ goto done;
+ }
+ retract_neighbour_routes(neigh);
+ goto done;
+ } else if(message[2] == 1) {
+ if(!have_v4_nh)
+ goto fail;
+ nh = v4_nh;
+ } else if(have_v6_nh) {
+ nh = v6_nh;
+ } else {
+ nh = neigh->address;
+ }
+
+ if(message[2] == 1) {
+ if(!babel_get_if_nfo(ifp)->ipv4)
+ goto done;
+ }
+
+ if((ifp->flags & BABEL_IF_FARAWAY)) {
+ channels[0] = 0;
+ } else {
+ /* This will be overwritten by parse_route_attributes below. */
+ if(metric < 256) {
+ /* Assume non-interfering (wired) link. */
+ channels[0] = 0;
+ } else {
+ /* Assume interfering. */
+ channels[0] = BABEL_IF_CHANNEL_INTERFERING;
+ channels[1] = 0;
+ }
+
+ if(parsed_len < len)
+ parse_route_attributes(message + 2 + parsed_len,
+ len - parsed_len, channels);
+ }
+
+ update_route(router_id, prefix, plen, seqno, metric, interval,
+ neigh, nh,
+ channels, channels_len(channels));
+ } else if(type == MESSAGE_REQUEST) {
+ unsigned char prefix[16], plen;
+ int rc;
+ if(len < 2) goto fail;
+ rc = network_prefix(message[2], message[3], 0,
+ message + 4, NULL, len - 2, prefix);
+ if(rc < 0) goto fail;
+ plen = message[3] + (message[2] == 1 ? 96 : 0);
+ debugf(BABEL_DEBUG_COMMON,"Received request for %s from %s on %s.",
+ message[2] == 0 ? "any" : format_prefix(prefix, plen),
+ format_address(from), ifp->name);
+ if(message[2] == 0) {
+ struct babel_interface *babel_ifp =babel_get_if_nfo(neigh->ifp);
+ /* If a neighbour is requesting a full route dump from us,
+ we might as well send it an IHU. */
+ send_ihu(neigh, NULL);
+ /* Since nodes send wildcard requests on boot, booting
+ a large number of nodes at the same time may cause an
+ update storm. Ignore a wildcard request that happens
+ shortly after we sent a full update. */
+ if(babel_ifp->last_update_time <
+ (time_t)(babel_now.tv_sec -
+ MAX(babel_ifp->hello_interval / 100, 1)))
+ send_update(neigh->ifp, 0, NULL, 0);
+ } else {
+ send_update(neigh->ifp, 0, prefix, plen);
+ }
+ } else if(type == MESSAGE_MH_REQUEST) {
+ unsigned char prefix[16], plen;
+ unsigned short seqno;
+ int rc;
+ if(len < 14) goto fail;
+ DO_NTOHS(seqno, message + 4);
+ rc = network_prefix(message[2], message[3], 0,
+ message + 16, NULL, len - 14, prefix);
+ if(rc < 0) goto fail;
+ plen = message[3] + (message[2] == 1 ? 96 : 0);
+ debugf(BABEL_DEBUG_COMMON,"Received request (%d) for %s from %s on %s (%s, %d).",
+ message[6],
+ format_prefix(prefix, plen),
+ format_address(from), ifp->name,
+ format_eui64(message + 8), seqno);
+ handle_request(neigh, prefix, plen, message[6],
+ seqno, message + 8);
+ } else {
+ debugf(BABEL_DEBUG_COMMON,"Received unknown packet type %d from %s on %s.",
+ type, format_address(from), ifp->name);
+ }
+ done:
+ i += len + 2;
+ continue;
+
+ fail:
+ zlog_err("Couldn't parse packet (%d, %d) from %s on %s.",
+ message[0], message[1], format_address(from), ifp->name);
+ goto done;
+ }
+ return;
+}
+
+/* Under normal circumstances, there are enough moderation mechanisms
+ elsewhere in the protocol to make sure that this last-ditch check
+ should never trigger. But I'm superstitious. */
+
+static int
+check_bucket(struct interface *ifp)
+{
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+ if(babel_ifp->bucket <= 0) {
+ int seconds = babel_now.tv_sec - babel_ifp->bucket_time;
+ if(seconds > 0) {
+ babel_ifp->bucket = MIN(BUCKET_TOKENS_MAX,
+ seconds * BUCKET_TOKENS_PER_SEC);
+ }
+ /* Reset bucket time unconditionally, in case clock is stepped. */
+ babel_ifp->bucket_time = babel_now.tv_sec;
+ }
+
+ if(babel_ifp->bucket > 0) {
+ babel_ifp->bucket--;
+ return 1;
+ } else {
+ return 0;
+ }
+}
+
+void
+flushbuf(struct interface *ifp)
+{
+ int rc;
+ struct sockaddr_in6 sin6;
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+
+ assert(babel_ifp->buffered <= babel_ifp->bufsize);
+
+ flushupdates(ifp);
+
+ if(babel_ifp->buffered > 0) {
+ debugf(BABEL_DEBUG_COMMON," (flushing %d buffered bytes on %s)",
+ babel_ifp->buffered, ifp->name);
+ if(check_bucket(ifp)) {
+ memset(&sin6, 0, sizeof(sin6));
+ sin6.sin6_family = AF_INET6;
+ memcpy(&sin6.sin6_addr, protocol_group, 16);
+ sin6.sin6_port = htons(protocol_port);
+ sin6.sin6_scope_id = ifp->ifindex;
+ DO_HTONS(packet_header + 2, babel_ifp->buffered);
+ rc = babel_send(protocol_socket,
+ packet_header, sizeof(packet_header),
+ babel_ifp->sendbuf, babel_ifp->buffered,
+ (struct sockaddr*)&sin6, sizeof(sin6));
+ if(rc < 0)
+ zlog_err("send: %s", safe_strerror(errno));
+ } else {
+ zlog_err("Warning: bucket full, dropping packet to %s.",
+ ifp->name);
+ }
+ }
+ VALGRIND_MAKE_MEM_UNDEFINED(babel_ifp->sendbuf, babel_ifp->bufsize);
+ babel_ifp->buffered = 0;
+ babel_ifp->have_buffered_hello = 0;
+ babel_ifp->have_buffered_id = 0;
+ babel_ifp->have_buffered_nh = 0;
+ babel_ifp->have_buffered_prefix = 0;
+ babel_ifp->flush_timeout.tv_sec = 0;
+ babel_ifp->flush_timeout.tv_usec = 0;
+}
+
+static void
+schedule_flush(struct interface *ifp)
+{
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+ unsigned msecs = jitter(babel_ifp, 0);
+ if(babel_ifp->flush_timeout.tv_sec != 0 &&
+ timeval_minus_msec(&babel_ifp->flush_timeout, &babel_now) < msecs)
+ return;
+ set_timeout(&babel_ifp->flush_timeout, msecs);
+}
+
+static void
+schedule_flush_now(struct interface *ifp)
+{
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+ /* Almost now */
+ unsigned msecs = roughly(10);
+ if(babel_ifp->flush_timeout.tv_sec != 0 &&
+ timeval_minus_msec(&babel_ifp->flush_timeout, &babel_now) < msecs)
+ return;
+ set_timeout(&babel_ifp->flush_timeout, msecs);
+}
+
+static void
+schedule_unicast_flush(unsigned msecs)
+{
+ if(!unicast_neighbour)
+ return;
+ if(unicast_flush_timeout.tv_sec != 0 &&
+ timeval_minus_msec(&unicast_flush_timeout, &babel_now) < msecs)
+ return;
+ unicast_flush_timeout.tv_usec = (babel_now.tv_usec + msecs * 1000) %1000000;
+ unicast_flush_timeout.tv_sec =
+ babel_now.tv_sec + (babel_now.tv_usec / 1000 + msecs) / 1000;
+}
+
+static void
+ensure_space(struct interface *ifp, int space)
+{
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+ if(babel_ifp->bufsize - babel_ifp->buffered < space)
+ flushbuf(ifp);
+}
+
+static void
+start_message(struct interface *ifp, int type, int len)
+{
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+ if(babel_ifp->bufsize - babel_ifp->buffered < len + 2)
+ flushbuf(ifp);
+ babel_ifp->sendbuf[babel_ifp->buffered++] = type;
+ babel_ifp->sendbuf[babel_ifp->buffered++] = len;
+}
+
+static void
+end_message(struct interface *ifp, int type, int bytes)
+{
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+ assert(babel_ifp->buffered >= bytes + 2 &&
+ babel_ifp->sendbuf[babel_ifp->buffered - bytes - 2] == type &&
+ babel_ifp->sendbuf[babel_ifp->buffered - bytes - 1] == bytes);
+ schedule_flush(ifp);
+}
+
+static void
+accumulate_byte(struct interface *ifp, unsigned char value)
+{
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+ babel_ifp->sendbuf[babel_ifp->buffered++] = value;
+}
+
+static void
+accumulate_short(struct interface *ifp, unsigned short value)
+{
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+ DO_HTONS(babel_ifp->sendbuf + babel_ifp->buffered, value);
+ babel_ifp->buffered += 2;
+}
+
+static void
+accumulate_bytes(struct interface *ifp,
+ const unsigned char *value, unsigned len)
+{
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+ memcpy(babel_ifp->sendbuf + babel_ifp->buffered, value, len);
+ babel_ifp->buffered += len;
+}
+
+static int
+start_unicast_message(struct neighbour *neigh, int type, int len)
+{
+ if(unicast_neighbour) {
+ if(neigh != unicast_neighbour ||
+ unicast_buffered + len + 2 >=
+ MIN(UNICAST_BUFSIZE, babel_get_if_nfo(neigh->ifp)->bufsize))
+ flush_unicast(0);
+ }
+ if(!unicast_buffer)
+ unicast_buffer = malloc(UNICAST_BUFSIZE);
+ if(!unicast_buffer) {
+ zlog_err("malloc(unicast_buffer): %s", safe_strerror(errno));
+ return -1;
+ }
+
+ unicast_neighbour = neigh;
+
+ unicast_buffer[unicast_buffered++] = type;
+ unicast_buffer[unicast_buffered++] = len;
+ return 1;
+}
+
+static void
+end_unicast_message(struct neighbour *neigh, int type, int bytes)
+{
+ assert(unicast_neighbour == neigh && unicast_buffered >= bytes + 2 &&
+ unicast_buffer[unicast_buffered - bytes - 2] == type &&
+ unicast_buffer[unicast_buffered - bytes - 1] == bytes);
+ schedule_unicast_flush(jitter(babel_get_if_nfo(neigh->ifp), 0));
+}
+
+static void
+accumulate_unicast_byte(struct neighbour *neigh, unsigned char value)
+{
+ unicast_buffer[unicast_buffered++] = value;
+}
+
+static void
+accumulate_unicast_short(struct neighbour *neigh, unsigned short value)
+{
+ DO_HTONS(unicast_buffer + unicast_buffered, value);
+ unicast_buffered += 2;
+}
+
+static void
+accumulate_unicast_bytes(struct neighbour *neigh,
+ const unsigned char *value, unsigned len)
+{
+ memcpy(unicast_buffer + unicast_buffered, value, len);
+ unicast_buffered += len;
+}
+
+void
+send_ack(struct neighbour *neigh, unsigned short nonce, unsigned short interval)
+{
+ int rc;
+ debugf(BABEL_DEBUG_COMMON,"Sending ack (%04x) to %s on %s.",
+ nonce, format_address(neigh->address), neigh->ifp->name);
+ rc = start_unicast_message(neigh, MESSAGE_ACK, 2); if(rc < 0) return;
+ accumulate_unicast_short(neigh, nonce);
+ end_unicast_message(neigh, MESSAGE_ACK, 2);
+ /* Roughly yields a value no larger than 3/2, so this meets the deadline */
+ schedule_unicast_flush(roughly(interval * 6));
+}
+
+void
+send_hello_noupdate(struct interface *ifp, unsigned interval)
+{
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+ /* This avoids sending multiple hellos in a single packet, which breaks
+ link quality estimation. */
+ if(babel_ifp->have_buffered_hello)
+ flushbuf(ifp);
+
+ babel_ifp->hello_seqno = seqno_plus(babel_ifp->hello_seqno, 1);
+ set_timeout(&babel_ifp->hello_timeout, babel_ifp->hello_interval);
+
+ if(!if_up(ifp))
+ return;
+
+ debugf(BABEL_DEBUG_COMMON,"Sending hello %d (%d) to %s.",
+ babel_ifp->hello_seqno, interval, ifp->name);
+
+ start_message(ifp, MESSAGE_HELLO, 6);
+ accumulate_short(ifp, 0);
+ accumulate_short(ifp, babel_ifp->hello_seqno);
+ accumulate_short(ifp, interval > 0xFFFF ? 0xFFFF : interval);
+ end_message(ifp, MESSAGE_HELLO, 6);
+ babel_ifp->have_buffered_hello = 1;
+}
+
+void
+send_hello(struct interface *ifp)
+{
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+ send_hello_noupdate(ifp, (babel_ifp->hello_interval + 9) / 10);
+ /* Send full IHU every 3 hellos, and marginal IHU each time */
+ if(babel_ifp->hello_seqno % 3 == 0)
+ send_ihu(NULL, ifp);
+ else
+ send_marginal_ihu(ifp);
+}
+
+void
+flush_unicast(int dofree)
+{
+ struct sockaddr_in6 sin6;
+ int rc;
+
+ if(unicast_buffered == 0)
+ goto done;
+
+ if(!if_up(unicast_neighbour->ifp))
+ goto done;
+
+ /* Preserve ordering of messages */
+ flushbuf(unicast_neighbour->ifp);
+
+ if(check_bucket(unicast_neighbour->ifp)) {
+ memset(&sin6, 0, sizeof(sin6));
+ sin6.sin6_family = AF_INET6;
+ memcpy(&sin6.sin6_addr, unicast_neighbour->address, 16);
+ sin6.sin6_port = htons(protocol_port);
+ sin6.sin6_scope_id = unicast_neighbour->ifp->ifindex;
+ DO_HTONS(packet_header + 2, unicast_buffered);
+ rc = babel_send(protocol_socket,
+ packet_header, sizeof(packet_header),
+ unicast_buffer, unicast_buffered,
+ (struct sockaddr*)&sin6, sizeof(sin6));
+ if(rc < 0)
+ zlog_err("send(unicast): %s", safe_strerror(errno));
+ } else {
+ zlog_err("Warning: bucket full, dropping unicast packet to %s if %s.",
+ format_address(unicast_neighbour->address),
+ unicast_neighbour->ifp->name);
+ }
+
+ done:
+ VALGRIND_MAKE_MEM_UNDEFINED(unicast_buffer, UNICAST_BUFSIZE);
+ unicast_buffered = 0;
+ if(dofree && unicast_buffer) {
+ free(unicast_buffer);
+ unicast_buffer = NULL;
+ }
+ unicast_neighbour = NULL;
+ unicast_flush_timeout.tv_sec = 0;
+ unicast_flush_timeout.tv_usec = 0;
+}
+
+static void
+really_send_update(struct interface *ifp,
+ const unsigned char *id,
+ const unsigned char *prefix, unsigned char plen,
+ unsigned short seqno, unsigned short metric,
+ unsigned char *channels, int channels_len)
+{
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+ int add_metric, v4, real_plen, omit = 0;
+ const unsigned char *real_prefix;
+ unsigned short flags = 0;
+ int channels_size;
+
+ if(diversity_kind != DIVERSITY_CHANNEL)
+ channels_len = -1;
+
+ channels_size = channels_len >= 0 ? channels_len + 2 : 0;
+
+ if(!if_up(ifp))
+ return;
+
+ add_metric = output_filter(id, prefix, plen, ifp->ifindex);
+ if(add_metric >= INFINITY)
+ return;
+
+ metric = MIN(metric + add_metric, INFINITY);
+ /* Worst case */
+ ensure_space(ifp, 20 + 12 + 28);
+
+ v4 = plen >= 96 && v4mapped(prefix);
+
+ if(v4) {
+ if(!babel_ifp->ipv4)
+ return;
+ if(!babel_ifp->have_buffered_nh ||
+ memcmp(babel_ifp->buffered_nh, babel_ifp->ipv4, 4) != 0) {
+ start_message(ifp, MESSAGE_NH, 6);
+ accumulate_byte(ifp, 1);
+ accumulate_byte(ifp, 0);
+ accumulate_bytes(ifp, babel_ifp->ipv4, 4);
+ end_message(ifp, MESSAGE_NH, 6);
+ memcpy(babel_ifp->buffered_nh, babel_ifp->ipv4, 4);
+ babel_ifp->have_buffered_nh = 1;
+ }
+
+ real_prefix = prefix + 12;
+ real_plen = plen - 96;
+ } else {
+ if(babel_ifp->have_buffered_prefix) {
+ while(omit < plen / 8 &&
+ babel_ifp->buffered_prefix[omit] == prefix[omit])
+ omit++;
+ }
+ if(!babel_ifp->have_buffered_prefix || plen >= 48)
+ flags |= 0x80;
+ real_prefix = prefix;
+ real_plen = plen;
+ }
+
+ if(!babel_ifp->have_buffered_id
+ || memcmp(id, babel_ifp->buffered_id, 8) != 0) {
+ if(real_plen == 128 && memcmp(real_prefix + 8, id, 8) == 0) {
+ flags |= 0x40;
+ } else {
+ start_message(ifp, MESSAGE_ROUTER_ID, 10);
+ accumulate_short(ifp, 0);
+ accumulate_bytes(ifp, id, 8);
+ end_message(ifp, MESSAGE_ROUTER_ID, 10);
+ }
+ memcpy(babel_ifp->buffered_id, id, 16);
+ babel_ifp->have_buffered_id = 1;
+ }
+
+ start_message(ifp, MESSAGE_UPDATE, 10 + (real_plen + 7) / 8 - omit +
+ channels_size);
+ accumulate_byte(ifp, v4 ? 1 : 2);
+ accumulate_byte(ifp, flags);
+ accumulate_byte(ifp, real_plen);
+ accumulate_byte(ifp, omit);
+ accumulate_short(ifp, (babel_ifp->update_interval + 5) / 10);
+ accumulate_short(ifp, seqno);
+ accumulate_short(ifp, metric);
+ accumulate_bytes(ifp, real_prefix + omit, (real_plen + 7) / 8 - omit);
+ /* Note that an empty channels TLV is different from no such TLV. */
+ if(channels_len >= 0) {
+ accumulate_byte(ifp, 2);
+ accumulate_byte(ifp, channels_len);
+ accumulate_bytes(ifp, channels, channels_len);
+ }
+ end_message(ifp, MESSAGE_UPDATE, 10 + (real_plen + 7) / 8 - omit +
+ channels_size);
+
+ if(flags & 0x80) {
+ memcpy(babel_ifp->buffered_prefix, prefix, 16);
+ babel_ifp->have_buffered_prefix = 1;
+ }
+}
+
+static int
+compare_buffered_updates(const void *av, const void *bv)
+{
+ const struct buffered_update *a = av, *b = bv;
+ int rc, v4a, v4b, ma, mb;
+
+ rc = memcmp(a->id, b->id, 8);
+ if(rc != 0)
+ return rc;
+
+ v4a = (a->plen >= 96 && v4mapped(a->prefix));
+ v4b = (b->plen >= 96 && v4mapped(b->prefix));
+
+ if(v4a > v4b)
+ return 1;
+ else if(v4a < v4b)
+ return -1;
+
+ ma = (!v4a && a->plen == 128 && memcmp(a->prefix + 8, a->id, 8) == 0);
+ mb = (!v4b && b->plen == 128 && memcmp(b->prefix + 8, b->id, 8) == 0);
+
+ if(ma > mb)
+ return -1;
+ else if(mb > ma)
+ return 1;
+
+ if(a->plen < b->plen)
+ return 1;
+ else if(a->plen > b->plen)
+ return -1;
+
+ return memcmp(a->prefix, b->prefix, 16);
+}
+
+void
+flushupdates(struct interface *ifp)
+{
+ babel_interface_nfo *babel_ifp = NULL;
+ struct xroute *xroute;
+ struct babel_route *route;
+ const unsigned char *last_prefix = NULL;
+ unsigned char last_plen = 0xFF;
+ int i;
+
+ if(ifp == NULL) {
+ struct interface *ifp_aux;
+ struct listnode *linklist_node = NULL;
+ FOR_ALL_INTERFACES(ifp_aux, linklist_node)
+ flushupdates(ifp_aux);
+ return;
+ }
+
+ babel_ifp = babel_get_if_nfo(ifp);
+ if(babel_ifp->num_buffered_updates > 0) {
+ struct buffered_update *b = babel_ifp->buffered_updates;
+ int n = babel_ifp->num_buffered_updates;
+
+ babel_ifp->buffered_updates = NULL;
+ babel_ifp->update_bufsize = 0;
+ babel_ifp->num_buffered_updates = 0;
+
+ if(!if_up(ifp))
+ goto done;
+
+ debugf(BABEL_DEBUG_COMMON," (flushing %d buffered updates on %s (%d))",
+ n, ifp->name, ifp->ifindex);
+
+ /* In order to send fewer update messages, we want to send updates
+ with the same router-id together, with IPv6 going out before IPv4. */
+
+ for(i = 0; i < n; i++) {
+ route = find_installed_route(b[i].prefix, b[i].plen);
+ if(route)
+ memcpy(b[i].id, route->src->id, 8);
+ else
+ memcpy(b[i].id, myid, 8);
+ }
+
+ qsort(b, n, sizeof(struct buffered_update), compare_buffered_updates);
+
+ for(i = 0; i < n; i++) {
+ /* The same update may be scheduled multiple times before it is
+ sent out. Since our buffer is now sorted, it is enough to
+ compare with the previous update. */
+
+ if(last_prefix) {
+ if(b[i].plen == last_plen &&
+ memcmp(b[i].prefix, last_prefix, 16) == 0)
+ continue;
+ }
+
+ xroute = find_xroute(b[i].prefix, b[i].plen);
+ route = find_installed_route(b[i].prefix, b[i].plen);
+
+ if(xroute && (!route || xroute->metric <= kernel_metric)) {
+ really_send_update(ifp, myid,
+ xroute->prefix, xroute->plen,
+ myseqno, xroute->metric,
+ NULL, 0);
+ last_prefix = xroute->prefix;
+ last_plen = xroute->plen;
+ } else if(route) {
+ unsigned char channels[DIVERSITY_HOPS];
+ int chlen;
+ struct interface *route_ifp = route->neigh->ifp;
+ struct babel_interface *babel_route_ifp = NULL;
+ unsigned short metric;
+ unsigned short seqno;
+
+ seqno = route->seqno;
+ metric =
+ route_interferes(route, ifp) ?
+ route_metric(route) :
+ route_metric_noninterfering(route);
+
+ if(metric < INFINITY)
+ satisfy_request(route->src->prefix, route->src->plen,
+ seqno, route->src->id, ifp);
+ if((babel_ifp->flags & BABEL_IF_SPLIT_HORIZON) &&
+ route->neigh->ifp == ifp)
+ continue;
+
+ babel_route_ifp = babel_get_if_nfo(route_ifp);
+ if(babel_route_ifp->channel ==BABEL_IF_CHANNEL_NONINTERFERING) {
+ memcpy(channels, route->channels, DIVERSITY_HOPS);
+ } else {
+ if(babel_route_ifp->channel == BABEL_IF_CHANNEL_UNKNOWN)
+ channels[0] = BABEL_IF_CHANNEL_INTERFERING;
+ else {
+ assert(babel_route_ifp->channel > 0 &&
+ babel_route_ifp->channel <= 255);
+ channels[0] = babel_route_ifp->channel;
+ }
+ memcpy(channels + 1, route->channels, DIVERSITY_HOPS - 1);
+ }
+
+ chlen = channels_len(channels);
+ really_send_update(ifp, route->src->id,
+ route->src->prefix,
+ route->src->plen,
+ seqno, metric,
+ channels, chlen);
+ update_source(route->src, seqno, metric);
+ last_prefix = route->src->prefix;
+ last_plen = route->src->plen;
+ } else {
+ /* There's no route for this prefix. This can happen shortly
+ after an xroute has been retracted, so send a retraction. */
+ really_send_update(ifp, myid, b[i].prefix, b[i].plen,
+ myseqno, INFINITY, NULL, -1);
+ }
+ }
+ schedule_flush_now(ifp);
+ done:
+ free(b);
+ }
+ babel_ifp->update_flush_timeout.tv_sec = 0;
+ babel_ifp->update_flush_timeout.tv_usec = 0;
+}
+
+static void
+schedule_update_flush(struct interface *ifp, int urgent)
+{
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+ unsigned msecs;
+ msecs = update_jitter(babel_ifp, urgent);
+ if(babel_ifp->update_flush_timeout.tv_sec != 0 &&
+ timeval_minus_msec(&babel_ifp->update_flush_timeout, &babel_now) < msecs)
+ return;
+ set_timeout(&babel_ifp->update_flush_timeout, msecs);
+}
+
+static void
+buffer_update(struct interface *ifp,
+ const unsigned char *prefix, unsigned char plen)
+{
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+ if(babel_ifp->num_buffered_updates > 0 &&
+ babel_ifp->num_buffered_updates >= babel_ifp->update_bufsize)
+ flushupdates(ifp);
+
+ if(babel_ifp->update_bufsize == 0) {
+ int n;
+ assert(babel_ifp->buffered_updates == NULL);
+ /* Allocate enough space to hold a full update. Since the
+ number of installed routes will grow over time, make sure we
+ have enough space to send a full-ish frame. */
+ n = installed_routes_estimate() + xroutes_estimate() + 4;
+ n = MAX(n, babel_ifp->bufsize / 16);
+ again:
+ babel_ifp->buffered_updates = malloc(n *sizeof(struct buffered_update));
+ if(babel_ifp->buffered_updates == NULL) {
+ zlog_err("malloc(buffered_updates): %s", safe_strerror(errno));
+ if(n > 4) {
+ /* Try again with a tiny buffer. */
+ n = 4;
+ goto again;
+ }
+ return;
+ }
+ babel_ifp->update_bufsize = n;
+ babel_ifp->num_buffered_updates = 0;
+ }
+
+ memcpy(babel_ifp->buffered_updates[babel_ifp->num_buffered_updates].prefix,
+ prefix, 16);
+ babel_ifp->buffered_updates[babel_ifp->num_buffered_updates].plen = plen;
+ babel_ifp->num_buffered_updates++;
+}
+
+static void
+buffer_update_callback(struct babel_route *route, void *closure)
+{
+ buffer_update((struct interface*)closure,
+ route->src->prefix, route->src->plen);
+}
+
+void
+send_update(struct interface *ifp, int urgent,
+ const unsigned char *prefix, unsigned char plen)
+{
+ babel_interface_nfo *babel_ifp = NULL;
+
+ if(ifp == NULL) {
+ struct interface *ifp_aux;
+ struct listnode *linklist_node = NULL;
+ struct babel_route *route;
+ FOR_ALL_INTERFACES(ifp_aux, linklist_node)
+ send_update(ifp_aux, urgent, prefix, plen);
+ if(prefix) {
+ /* Since flushupdates only deals with non-wildcard interfaces, we
+ need to do this now. */
+ route = find_installed_route(prefix, plen);
+ if(route && route_metric(route) < INFINITY)
+ satisfy_request(prefix, plen, route->src->seqno, route->src->id,
+ NULL);
+ }
+ return;
+ }
+
+ if(!if_up(ifp))
+ return;
+
+ babel_ifp = babel_get_if_nfo(ifp);
+ if(prefix) {
+ debugf(BABEL_DEBUG_COMMON,"Sending update to %s for %s.",
+ ifp->name, format_prefix(prefix, plen));
+ buffer_update(ifp, prefix, plen);
+ } else {
+ send_self_update(ifp);
+ debugf(BABEL_DEBUG_COMMON,"Sending update to %s for any.", ifp->name);
+ for_all_installed_routes(buffer_update_callback, ifp);
+ set_timeout(&babel_ifp->update_timeout, babel_ifp->update_interval);
+ babel_ifp->last_update_time = babel_now.tv_sec;
+ }
+ schedule_update_flush(ifp, urgent);
+}
+
+void
+send_update_resend(struct interface *ifp,
+ const unsigned char *prefix, unsigned char plen)
+{
+ assert(prefix != NULL);
+
+ send_update(ifp, 1, prefix, plen);
+ record_resend(RESEND_UPDATE, prefix, plen, 0, 0, NULL, resend_delay);
+}
+
+void
+send_wildcard_retraction(struct interface *ifp)
+{
+ babel_interface_nfo *babel_ifp = NULL;
+ if(ifp == NULL) {
+ struct interface *ifp_aux;
+ struct listnode *linklist_node = NULL;
+ FOR_ALL_INTERFACES(ifp_aux, linklist_node)
+ send_wildcard_retraction(ifp_aux);
+ return;
+ }
+
+ if(!if_up(ifp))
+ return;
+
+ babel_ifp = babel_get_if_nfo(ifp);
+ start_message(ifp, MESSAGE_UPDATE, 10);
+ accumulate_byte(ifp, 0);
+ accumulate_byte(ifp, 0x40);
+ accumulate_byte(ifp, 0);
+ accumulate_byte(ifp, 0);
+ accumulate_short(ifp, 0xFFFF);
+ accumulate_short(ifp, myseqno);
+ accumulate_short(ifp, 0xFFFF);
+ end_message(ifp, MESSAGE_UPDATE, 10);
+
+ babel_ifp->have_buffered_id = 0;
+}
+
+void
+update_myseqno()
+{
+ myseqno = seqno_plus(myseqno, 1);
+ seqno_time = babel_now;
+}
+
+static void
+send_xroute_update_callback(struct xroute *xroute, void *closure)
+{
+ struct interface *ifp = (struct interface*)closure;
+ send_update(ifp, 0, xroute->prefix, xroute->plen);
+}
+
+void
+send_self_update(struct interface *ifp)
+{
+ if(ifp == NULL) {
+ struct interface *ifp_aux;
+ struct listnode *linklist_node = NULL;
+ FOR_ALL_INTERFACES(ifp_aux, linklist_node) {
+ if(!if_up(ifp_aux))
+ continue;
+ send_self_update(ifp_aux);
+ }
+ return;
+ }
+
+ debugf(BABEL_DEBUG_COMMON,"Sending self update to %s.", ifp->name);
+ for_all_xroutes(send_xroute_update_callback, ifp);
+}
+
+void
+send_ihu(struct neighbour *neigh, struct interface *ifp)
+{
+ babel_interface_nfo *babel_ifp = NULL;
+ int rxcost, interval;
+ int ll;
+
+ if(neigh == NULL && ifp == NULL) {
+ struct interface *ifp_aux;
+ struct listnode *linklist_node = NULL;
+ FOR_ALL_INTERFACES(ifp_aux, linklist_node) {
+ if(if_up(ifp_aux))
+ continue;
+ send_ihu(NULL, ifp_aux);
+ }
+ return;
+ }
+
+ if(neigh == NULL) {
+ struct neighbour *ngh;
+ FOR_ALL_NEIGHBOURS(ngh) {
+ if(ngh->ifp == ifp)
+ send_ihu(ngh, ifp);
+ }
+ return;
+ }
+
+
+ if(ifp && neigh->ifp != ifp)
+ return;
+
+ ifp = neigh->ifp;
+ babel_ifp = babel_get_if_nfo(ifp);
+ if(!if_up(ifp))
+ return;
+
+ rxcost = neighbour_rxcost(neigh);
+ interval = (babel_ifp->hello_interval * 3 + 9) / 10;
+
+ /* Conceptually, an IHU is a unicast message. We usually send them as
+ multicast, since this allows aggregation into a single packet and
+ avoids an ARP exchange. If we already have a unicast message queued
+ for this neighbour, however, we might as well piggyback the IHU. */
+ debugf(BABEL_DEBUG_COMMON,"Sending %sihu %d on %s to %s.",
+ unicast_neighbour == neigh ? "unicast " : "",
+ rxcost,
+ neigh->ifp->name,
+ format_address(neigh->address));
+
+ ll = linklocal(neigh->address);
+
+ if(unicast_neighbour != neigh) {
+ start_message(ifp, MESSAGE_IHU, ll ? 14 : 22);
+ accumulate_byte(ifp, ll ? 3 : 2);
+ accumulate_byte(ifp, 0);
+ accumulate_short(ifp, rxcost);
+ accumulate_short(ifp, interval);
+ if(ll)
+ accumulate_bytes(ifp, neigh->address + 8, 8);
+ else
+ accumulate_bytes(ifp, neigh->address, 16);
+ end_message(ifp, MESSAGE_IHU, ll ? 14 : 22);
+ } else {
+ int rc;
+ rc = start_unicast_message(neigh, MESSAGE_IHU, ll ? 14 : 22);
+ if(rc < 0) return;
+ accumulate_unicast_byte(neigh, ll ? 3 : 2);
+ accumulate_unicast_byte(neigh, 0);
+ accumulate_unicast_short(neigh, rxcost);
+ accumulate_unicast_short(neigh, interval);
+ if(ll)
+ accumulate_unicast_bytes(neigh, neigh->address + 8, 8);
+ else
+ accumulate_unicast_bytes(neigh, neigh->address, 16);
+ end_unicast_message(neigh, MESSAGE_IHU, ll ? 14 : 22);
+ }
+}
+
+/* Send IHUs to all marginal neighbours */
+void
+send_marginal_ihu(struct interface *ifp)
+{
+ struct neighbour *neigh;
+ FOR_ALL_NEIGHBOURS(neigh) {
+ if(ifp && neigh->ifp != ifp)
+ continue;
+ if(neigh->txcost >= 384 || (neigh->reach & 0xF000) != 0xF000)
+ send_ihu(neigh, ifp);
+ }
+}
+
+void
+send_request(struct interface *ifp,
+ const unsigned char *prefix, unsigned char plen)
+{
+ int v4, len;
+
+ if(ifp == NULL) {
+ struct interface *ifp_aux;
+ struct listnode *linklist_node = NULL;
+ FOR_ALL_INTERFACES(ifp_aux, linklist_node) {
+ if(if_up(ifp_aux))
+ continue;
+ send_request(ifp_aux, prefix, plen);
+ }
+ return;
+ }
+
+ /* make sure any buffered updates go out before this request. */
+ flushupdates(ifp);
+
+ if(!if_up(ifp))
+ return;
+
+ debugf(BABEL_DEBUG_COMMON,"sending request to %s for %s.",
+ ifp->name, prefix ? format_prefix(prefix, plen) : "any");
+ v4 = plen >= 96 && v4mapped(prefix);
+ len = !prefix ? 2 : v4 ? 6 : 18;
+
+ start_message(ifp, MESSAGE_REQUEST, len);
+ accumulate_byte(ifp, !prefix ? 0 : v4 ? 1 : 2);
+ accumulate_byte(ifp, !prefix ? 0 : v4 ? plen - 96 : plen);
+ if(prefix) {
+ if(v4)
+ accumulate_bytes(ifp, prefix + 12, 4);
+ else
+ accumulate_bytes(ifp, prefix, 16);
+ }
+ end_message(ifp, MESSAGE_REQUEST, len);
+}
+
+void
+send_unicast_request(struct neighbour *neigh,
+ const unsigned char *prefix, unsigned char plen)
+{
+ int rc, v4, len;
+
+ /* make sure any buffered updates go out before this request. */
+ flushupdates(neigh->ifp);
+
+ debugf(BABEL_DEBUG_COMMON,"sending unicast request to %s for %s.",
+ format_address(neigh->address),
+ prefix ? format_prefix(prefix, plen) : "any");
+ v4 = plen >= 96 && v4mapped(prefix);
+ len = !prefix ? 2 : v4 ? 6 : 18;
+
+ rc = start_unicast_message(neigh, MESSAGE_REQUEST, len);
+ if(rc < 0) return;
+ accumulate_unicast_byte(neigh, !prefix ? 0 : v4 ? 1 : 2);
+ accumulate_unicast_byte(neigh, !prefix ? 0 : v4 ? plen - 96 : plen);
+ if(prefix) {
+ if(v4)
+ accumulate_unicast_bytes(neigh, prefix + 12, 4);
+ else
+ accumulate_unicast_bytes(neigh, prefix, 16);
+ }
+ end_unicast_message(neigh, MESSAGE_REQUEST, len);
+}
+
+void
+send_multihop_request(struct interface *ifp,
+ const unsigned char *prefix, unsigned char plen,
+ unsigned short seqno, const unsigned char *id,
+ unsigned short hop_count)
+{
+ int v4, pb, len;
+
+ /* Make sure any buffered updates go out before this request. */
+ flushupdates(ifp);
+
+ if(ifp == NULL) {
+ struct interface *ifp_aux;
+ struct listnode *linklist_node = NULL;
+ FOR_ALL_INTERFACES(ifp_aux, linklist_node) {
+ if(!if_up(ifp_aux))
+ continue;
+ send_multihop_request(ifp_aux, prefix, plen, seqno, id, hop_count);
+ }
+ return;
+ }
+
+ if(!if_up(ifp))
+ return;
+
+ debugf(BABEL_DEBUG_COMMON,"Sending request (%d) on %s for %s.",
+ hop_count, ifp->name, format_prefix(prefix, plen));
+ v4 = plen >= 96 && v4mapped(prefix);
+ pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
+ len = 6 + 8 + pb;
+
+ start_message(ifp, MESSAGE_MH_REQUEST, len);
+ accumulate_byte(ifp, v4 ? 1 : 2);
+ accumulate_byte(ifp, v4 ? plen - 96 : plen);
+ accumulate_short(ifp, seqno);
+ accumulate_byte(ifp, hop_count);
+ accumulate_byte(ifp, 0);
+ accumulate_bytes(ifp, id, 8);
+ if(prefix) {
+ if(v4)
+ accumulate_bytes(ifp, prefix + 12, pb);
+ else
+ accumulate_bytes(ifp, prefix, pb);
+ }
+ end_message(ifp, MESSAGE_MH_REQUEST, len);
+}
+
+void
+send_unicast_multihop_request(struct neighbour *neigh,
+ const unsigned char *prefix, unsigned char plen,
+ unsigned short seqno, const unsigned char *id,
+ unsigned short hop_count)
+{
+ int rc, v4, pb, len;
+
+ /* Make sure any buffered updates go out before this request. */
+ flushupdates(neigh->ifp);
+
+ debugf(BABEL_DEBUG_COMMON,"Sending multi-hop request to %s for %s (%d hops).",
+ format_address(neigh->address),
+ format_prefix(prefix, plen), hop_count);
+ v4 = plen >= 96 && v4mapped(prefix);
+ pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
+ len = 6 + 8 + pb;
+
+ rc = start_unicast_message(neigh, MESSAGE_MH_REQUEST, len);
+ if(rc < 0) return;
+ accumulate_unicast_byte(neigh, v4 ? 1 : 2);
+ accumulate_unicast_byte(neigh, v4 ? plen - 96 : plen);
+ accumulate_unicast_short(neigh, seqno);
+ accumulate_unicast_byte(neigh, hop_count);
+ accumulate_unicast_byte(neigh, 0);
+ accumulate_unicast_bytes(neigh, id, 8);
+ if(prefix) {
+ if(v4)
+ accumulate_unicast_bytes(neigh, prefix + 12, pb);
+ else
+ accumulate_unicast_bytes(neigh, prefix, pb);
+ }
+ end_unicast_message(neigh, MESSAGE_MH_REQUEST, len);
+}
+
+void
+send_request_resend(struct neighbour *neigh,
+ const unsigned char *prefix, unsigned char plen,
+ unsigned short seqno, unsigned char *id)
+{
+ if(neigh)
+ send_unicast_multihop_request(neigh, prefix, plen, seqno, id, 127);
+ else
+ send_multihop_request(NULL, prefix, plen, seqno, id, 127);
+
+ record_resend(RESEND_REQUEST, prefix, plen, seqno, id,
+ neigh ? neigh->ifp : NULL, resend_delay);
+}
+
+void
+handle_request(struct neighbour *neigh, const unsigned char *prefix,
+ unsigned char plen, unsigned char hop_count,
+ unsigned short seqno, const unsigned char *id)
+{
+ struct xroute *xroute;
+ struct babel_route *route;
+ struct neighbour *successor = NULL;
+
+ xroute = find_xroute(prefix, plen);
+ route = find_installed_route(prefix, plen);
+
+ if(xroute && (!route || xroute->metric <= kernel_metric)) {
+ if(hop_count > 0 && memcmp(id, myid, 8) == 0) {
+ if(seqno_compare(seqno, myseqno) > 0) {
+ if(seqno_minus(seqno, myseqno) > 100) {
+ /* Hopelessly out-of-date request */
+ return;
+ }
+ update_myseqno();
+ }
+ }
+ send_update(neigh->ifp, 1, prefix, plen);
+ return;
+ }
+
+ if(route &&
+ (memcmp(id, route->src->id, 8) != 0 ||
+ seqno_compare(seqno, route->seqno) <= 0)) {
+ send_update(neigh->ifp, 1, prefix, plen);
+ return;
+ }
+
+ if(hop_count <= 1)
+ return;
+
+ if(route && memcmp(id, route->src->id, 8) == 0 &&
+ seqno_minus(seqno, route->seqno) > 100) {
+ /* Hopelessly out-of-date */
+ return;
+ }
+
+ if(request_redundant(neigh->ifp, prefix, plen, seqno, id))
+ return;
+
+ /* Let's try to forward this request. */
+ if(route && route_metric(route) < INFINITY)
+ successor = route->neigh;
+
+ if(!successor || successor == neigh) {
+ /* We were about to forward a request to its requestor. Try to
+ find a different neighbour to forward the request to. */
+ struct babel_route *other_route;
+
+ other_route = find_best_route(prefix, plen, 0, neigh);
+ if(other_route && route_metric(other_route) < INFINITY)
+ successor = other_route->neigh;
+ }
+
+ if(!successor || successor == neigh)
+ /* Give up */
+ return;
+
+ send_unicast_multihop_request(successor, prefix, plen, seqno, id,
+ hop_count - 1);
+ record_resend(RESEND_REQUEST, prefix, plen, seqno, id,
+ neigh->ifp, 0);
+}
diff --git a/babeld/message.h b/babeld/message.h
new file mode 100644
index 00000000..6a9aa104
--- /dev/null
+++ b/babeld/message.h
@@ -0,0 +1,111 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#ifndef BABEL_MESSAGE_H
+#define BABEL_MESSAGE_H
+
+#include "babel_interface.h"
+
+#define MAX_BUFFERED_UPDATES 200
+
+#define BUCKET_TOKENS_MAX 200
+#define BUCKET_TOKENS_PER_SEC 40
+
+#define MESSAGE_PAD1 0
+#define MESSAGE_PADN 1
+#define MESSAGE_ACK_REQ 2
+#define MESSAGE_ACK 3
+#define MESSAGE_HELLO 4
+#define MESSAGE_IHU 5
+#define MESSAGE_ROUTER_ID 6
+#define MESSAGE_NH 7
+#define MESSAGE_UPDATE 8
+#define MESSAGE_REQUEST 9
+#define MESSAGE_MH_REQUEST 10
+
+
+extern unsigned short myseqno;
+extern struct timeval seqno_time;
+
+extern int broadcast_ihu;
+extern int split_horizon;
+
+extern unsigned char packet_header[4];
+
+extern struct neighbour *unicast_neighbour;
+extern struct timeval unicast_flush_timeout;
+
+void parse_packet(const unsigned char *from, struct interface *ifp,
+ const unsigned char *packet, int packetlen);
+void flushbuf(struct interface *ifp);
+void flushupdates(struct interface *ifp);
+void send_ack(struct neighbour *neigh, unsigned short nonce,
+ unsigned short interval);
+void send_hello_noupdate(struct interface *ifp, unsigned interval);
+void send_hello(struct interface *ifp);
+void flush_unicast(int dofree);
+void send_update(struct interface *ifp, int urgent,
+ const unsigned char *prefix, unsigned char plen);
+void send_update_resend(struct interface *ifp,
+ const unsigned char *prefix, unsigned char plen);
+void send_wildcard_retraction(struct interface *ifp);
+void update_myseqno(void);
+void send_self_update(struct interface *ifp);
+void send_ihu(struct neighbour *neigh, struct interface *ifp);
+void send_marginal_ihu(struct interface *ifp);
+void send_request(struct interface *ifp,
+ const unsigned char *prefix, unsigned char plen);
+void send_unicast_request(struct neighbour *neigh,
+ const unsigned char *prefix, unsigned char plen);
+void send_multihop_request(struct interface *ifp,
+ const unsigned char *prefix, unsigned char plen,
+ unsigned short seqno, const unsigned char *id,
+ unsigned short hop_count);
+void
+send_unicast_multihop_request(struct neighbour *neigh,
+ const unsigned char *prefix, unsigned char plen,
+ unsigned short seqno, const unsigned char *id,
+ unsigned short hop_count);
+void send_request_resend(struct neighbour *neigh,
+ const unsigned char *prefix, unsigned char plen,
+ unsigned short seqno, unsigned char *id);
+void handle_request(struct neighbour *neigh, const unsigned char *prefix,
+ unsigned char plen, unsigned char hop_count,
+ unsigned short seqno, const unsigned char *id);
+
+#endif
diff --git a/babeld/neighbour.c b/babeld/neighbour.c
new file mode 100644
index 00000000..5a327dfe
--- /dev/null
+++ b/babeld/neighbour.c
@@ -0,0 +1,343 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <sys/time.h>
+#include <time.h>
+
+#include <zebra.h>
+#include "if.h"
+
+#include "babel_main.h"
+#include "babeld.h"
+#include "util.h"
+#include "babel_interface.h"
+#include "neighbour.h"
+#include "source.h"
+#include "route.h"
+#include "message.h"
+#include "resend.h"
+
+struct neighbour *neighs = NULL;
+
+static struct neighbour *
+find_neighbour_nocreate(const unsigned char *address, struct interface *ifp)
+{
+ struct neighbour *neigh;
+ FOR_ALL_NEIGHBOURS(neigh) {
+ if(memcmp(address, neigh->address, 16) == 0 &&
+ neigh->ifp == ifp)
+ return neigh;
+ }
+ return NULL;
+}
+
+void
+flush_neighbour(struct neighbour *neigh)
+{
+ flush_neighbour_routes(neigh);
+ if(unicast_neighbour == neigh)
+ flush_unicast(1);
+ flush_resends(neigh);
+
+ if(neighs == neigh) {
+ neighs = neigh->next;
+ } else {
+ struct neighbour *previous = neighs;
+ while(previous->next != neigh)
+ previous = previous->next;
+ previous->next = neigh->next;
+ }
+ free(neigh);
+}
+
+struct neighbour *
+find_neighbour(const unsigned char *address, struct interface *ifp)
+{
+ struct neighbour *neigh;
+ const struct timeval zero = {0, 0};
+
+ neigh = find_neighbour_nocreate(address, ifp);
+ if(neigh)
+ return neigh;
+
+ debugf(BABEL_DEBUG_COMMON,"Creating neighbour %s on %s.",
+ format_address(address), ifp->name);
+
+ neigh = malloc(sizeof(struct neighbour));
+ if(neigh == NULL) {
+ zlog_err("malloc(neighbour): %s", safe_strerror(errno));
+ return NULL;
+ }
+
+ neigh->hello_seqno = -1;
+ memcpy(neigh->address, address, 16);
+ neigh->reach = 0;
+ neigh->txcost = INFINITY;
+ neigh->ihu_time = babel_now;
+ neigh->hello_time = zero;
+ neigh->hello_interval = 0;
+ neigh->ihu_interval = 0;
+ neigh->ifp = ifp;
+ neigh->next = neighs;
+ neighs = neigh;
+ send_hello(ifp);
+ return neigh;
+}
+
+/* Recompute a neighbour's rxcost. Return true if anything changed.
+ This does not call local_notify_neighbour, see update_neighbour_metric. */
+int
+update_neighbour(struct neighbour *neigh, int hello, int hello_interval)
+{
+ int missed_hellos;
+ int rc = 0;
+
+ if(hello < 0) {
+ if(neigh->hello_interval <= 0)
+ return rc;
+ missed_hellos =
+ ((int)timeval_minus_msec(&babel_now, &neigh->hello_time) -
+ neigh->hello_interval * 7) /
+ (neigh->hello_interval * 10);
+ if(missed_hellos <= 0)
+ return rc;
+ timeval_add_msec(&neigh->hello_time, &neigh->hello_time,
+ missed_hellos * neigh->hello_interval * 10);
+ } else {
+ if(neigh->hello_seqno >= 0 && neigh->reach > 0) {
+ missed_hellos = seqno_minus(hello, neigh->hello_seqno) - 1;
+ if(missed_hellos < -8) {
+ /* Probably a neighbour that rebooted and lost its seqno.
+ Reboot the universe. */
+ neigh->reach = 0;
+ missed_hellos = 0;
+ rc = 1;
+ } else if(missed_hellos < 0) {
+ if(hello_interval > neigh->hello_interval) {
+ /* This neighbour has increased its hello interval,
+ and we didn't notice. */
+ neigh->reach <<= -missed_hellos;
+ missed_hellos = 0;
+ } else {
+ /* Late hello. Probably due to the link layer buffering
+ packets during a link outage. Ignore it, but reset
+ the expected seqno. */
+ neigh->hello_seqno = hello;
+ hello = -1;
+ missed_hellos = 0;
+ }
+ rc = 1;
+ }
+ } else {
+ missed_hellos = 0;
+ }
+ neigh->hello_time = babel_now;
+ neigh->hello_interval = hello_interval;
+ }
+
+ if(missed_hellos > 0) {
+ neigh->reach >>= missed_hellos;
+ neigh->hello_seqno = seqno_plus(neigh->hello_seqno, missed_hellos);
+ missed_hellos = 0;
+ rc = 1;
+ }
+
+ if(hello >= 0) {
+ neigh->hello_seqno = hello;
+ neigh->reach >>= 1;
+ neigh->reach |= 0x8000;
+ if((neigh->reach & 0xFC00) != 0xFC00)
+ rc = 1;
+ }
+
+ /* Make sure to give neighbours some feedback early after association */
+ if((neigh->reach & 0xBF00) == 0x8000) {
+ /* A new neighbour */
+ send_hello(neigh->ifp);
+ } else {
+ /* Don't send hellos, in order to avoid a positive feedback loop. */
+ int a = (neigh->reach & 0xC000);
+ int b = (neigh->reach & 0x3000);
+ if((a == 0xC000 && b == 0) || (a == 0 && b == 0x3000)) {
+ /* Reachability is either 1100 or 0011 */
+ send_self_update(neigh->ifp);
+ }
+ }
+
+ if((neigh->reach & 0xFC00) == 0xC000) {
+ /* This is a newish neighbour, let's request a full route dump.
+ We ought to avoid this when the network is dense */
+ send_unicast_request(neigh, NULL, 0);
+ send_ihu(neigh, NULL);
+ }
+ return rc;
+}
+
+static int
+reset_txcost(struct neighbour *neigh)
+{
+ unsigned delay;
+
+ delay = timeval_minus_msec(&babel_now, &neigh->ihu_time);
+
+ if(neigh->ihu_interval > 0 && delay < neigh->ihu_interval * 10U * 3U)
+ return 0;
+
+ /* If we're losing a lot of packets, we probably lost an IHU too */
+ if(delay >= 180000 || (neigh->reach & 0xFFF0) == 0 ||
+ (neigh->ihu_interval > 0 &&
+ delay >= neigh->ihu_interval * 10U * 10U)) {
+ neigh->txcost = INFINITY;
+ neigh->ihu_time = babel_now;
+ return 1;
+ }
+
+ return 0;
+}
+
+unsigned
+neighbour_txcost(struct neighbour *neigh)
+{
+ return neigh->txcost;
+}
+
+unsigned
+check_neighbours()
+{
+ struct neighbour *neigh;
+ int changed, rc;
+ unsigned msecs = 50000;
+
+ debugf(BABEL_DEBUG_COMMON,"Checking neighbours.");
+
+ neigh = neighs;
+ while(neigh) {
+ changed = update_neighbour(neigh, -1, 0);
+
+ if(neigh->reach == 0 ||
+ neigh->hello_time.tv_sec > babel_now.tv_sec || /* clock stepped */
+ timeval_minus_msec(&babel_now, &neigh->hello_time) > 300000) {
+ struct neighbour *old = neigh;
+ neigh = neigh->next;
+ flush_neighbour(old);
+ continue;
+ }
+
+ rc = reset_txcost(neigh);
+ changed = changed || rc;
+
+ update_neighbour_metric(neigh, changed);
+
+ if(neigh->hello_interval > 0)
+ msecs = MIN(msecs, neigh->hello_interval * 10U);
+ if(neigh->ihu_interval > 0)
+ msecs = MIN(msecs, neigh->ihu_interval * 10U);
+ neigh = neigh->next;
+ }
+
+ return msecs;
+}
+
+unsigned
+neighbour_rxcost(struct neighbour *neigh)
+{
+ unsigned delay;
+ unsigned short reach = neigh->reach;
+
+ delay = timeval_minus_msec(&babel_now, &neigh->hello_time);
+
+ if((reach & 0xFFF0) == 0 || delay >= 180000) {
+ return INFINITY;
+ } else if(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ) {
+ int sreach =
+ ((reach & 0x8000) >> 2) +
+ ((reach & 0x4000) >> 1) +
+ (reach & 0x3FFF);
+ /* 0 <= sreach <= 0x7FFF */
+ int cost = (0x8000 * babel_get_if_nfo(neigh->ifp)->cost) / (sreach + 1);
+ /* cost >= interface->cost */
+ if(delay >= 40000)
+ cost = (cost * (delay - 20000) + 10000) / 20000;
+ return MIN(cost, INFINITY);
+ } else {
+ /* To lose one hello is a misfortune, to lose two is carelessness. */
+ if((reach & 0xC000) == 0xC000)
+ return babel_get_if_nfo(neigh->ifp)->cost;
+ else if((reach & 0xC000) == 0)
+ return INFINITY;
+ else if((reach & 0x2000))
+ return babel_get_if_nfo(neigh->ifp)->cost;
+ else
+ return INFINITY;
+ }
+}
+
+unsigned
+neighbour_cost(struct neighbour *neigh)
+{
+ unsigned a, b;
+
+ if(!if_up(neigh->ifp))
+ return INFINITY;
+
+ a = neighbour_txcost(neigh);
+
+ if(a >= INFINITY)
+ return INFINITY;
+
+ b = neighbour_rxcost(neigh);
+ if(b >= INFINITY)
+ return INFINITY;
+
+ if(!(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ)
+ || (a < 256 && b < 256)) {
+ return a;
+ } else {
+ /* a = 256/alpha, b = 256/beta, where alpha and beta are the expected
+ probabilities of a packet getting through in the direct and reverse
+ directions. */
+ a = MAX(a, 256);
+ b = MAX(b, 256);
+ /* 1/(alpha * beta), which is just plain ETX. */
+ /* Since a and b are capped to 16 bits, overflow is impossible. */
+ return (a * b + 128) >> 8;
+ }
+}
diff --git a/babeld/neighbour.h b/babeld/neighbour.h
new file mode 100644
index 00000000..cf8c0f0b
--- /dev/null
+++ b/babeld/neighbour.h
@@ -0,0 +1,66 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+struct neighbour {
+ struct neighbour *next;
+ /* This is -1 when unknown, so don't make it unsigned */
+ int hello_seqno;
+ unsigned char address[16];
+ unsigned short reach;
+ unsigned short txcost;
+ struct timeval hello_time;
+ struct timeval ihu_time;
+ unsigned short hello_interval; /* in centiseconds */
+ unsigned short ihu_interval; /* in centiseconds */
+ struct interface *ifp;
+};
+
+extern struct neighbour *neighs;
+
+#define FOR_ALL_NEIGHBOURS(_neigh) \
+ for(_neigh = neighs; _neigh; _neigh = _neigh->next)
+
+int neighbour_valid(struct neighbour *neigh);
+void flush_neighbour(struct neighbour *neigh);
+struct neighbour *find_neighbour(const unsigned char *address,
+ struct interface *ifp);
+int update_neighbour(struct neighbour *neigh, int hello, int hello_interval);
+unsigned check_neighbours(void);
+unsigned neighbour_txcost(struct neighbour *neigh);
+unsigned neighbour_rxcost(struct neighbour *neigh);
+unsigned neighbour_cost(struct neighbour *neigh);
diff --git a/babeld/net.c b/babeld/net.c
new file mode 100644
index 00000000..5e0200b0
--- /dev/null
+++ b/babeld/net.c
@@ -0,0 +1,239 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include <unistd.h>
+#include <fcntl.h>
+#include <string.h>
+#include <sys/ioctl.h>
+#include <sys/types.h>
+#include <sys/uio.h>
+#include <sys/socket.h>
+#include <netinet/in.h>
+#include <arpa/inet.h>
+#include <errno.h>
+
+#include "babeld.h"
+#include "util.h"
+#include "net.h"
+
+int
+babel_socket(int port)
+{
+ struct sockaddr_in6 sin6;
+ int s, rc;
+ int saved_errno;
+ int one = 1, zero = 0;
+ const int ds = 0xc0; /* CS6 - Network Control */
+
+ s = socket(PF_INET6, SOCK_DGRAM, 0);
+ if(s < 0)
+ return -1;
+
+ rc = setsockopt(s, IPPROTO_IPV6, IPV6_V6ONLY, &one, sizeof(one));
+ if(rc < 0)
+ goto fail;
+
+ rc = setsockopt(s, SOL_SOCKET, SO_REUSEADDR, &one, sizeof(one));
+ if(rc < 0)
+ goto fail;
+
+ rc = setsockopt(s, IPPROTO_IPV6, IPV6_MULTICAST_LOOP,
+ &zero, sizeof(zero));
+ if(rc < 0)
+ goto fail;
+
+ rc = setsockopt(s, IPPROTO_IPV6, IPV6_UNICAST_HOPS,
+ &one, sizeof(one));
+ if(rc < 0)
+ goto fail;
+
+ rc = setsockopt(s, IPPROTO_IPV6, IPV6_MULTICAST_HOPS,
+ &one, sizeof(one));
+ if(rc < 0)
+ goto fail;
+
+#ifdef IPV6_TCLASS
+ rc = setsockopt(s, IPPROTO_IPV6, IPV6_TCLASS, &ds, sizeof(ds));
+#else
+ rc = -1;
+ errno = ENOSYS;
+#endif
+ if(rc < 0)
+ perror("Couldn't set traffic class");
+
+ rc = fcntl(s, F_GETFL, 0);
+ if(rc < 0)
+ goto fail;
+
+ rc = fcntl(s, F_SETFL, (rc | O_NONBLOCK));
+ if(rc < 0)
+ goto fail;
+
+ rc = fcntl(s, F_GETFD, 0);
+ if(rc < 0)
+ goto fail;
+
+ rc = fcntl(s, F_SETFD, rc | FD_CLOEXEC);
+ if(rc < 0)
+ goto fail;
+
+ memset(&sin6, 0, sizeof(sin6));
+ sin6.sin6_family = AF_INET6;
+ sin6.sin6_port = htons(port);
+ rc = bind(s, (struct sockaddr*)&sin6, sizeof(sin6));
+ if(rc < 0)
+ goto fail;
+
+ return s;
+
+ fail:
+ saved_errno = errno;
+ close(s);
+ errno = saved_errno;
+ return -1;
+}
+
+int
+babel_recv(int s, void *buf, int buflen, struct sockaddr *sin, int slen)
+{
+ struct iovec iovec;
+ struct msghdr msg;
+ int rc;
+
+ memset(&msg, 0, sizeof(msg));
+ iovec.iov_base = buf;
+ iovec.iov_len = buflen;
+ msg.msg_name = sin;
+ msg.msg_namelen = slen;
+ msg.msg_iov = &iovec;
+ msg.msg_iovlen = 1;
+
+ rc = recvmsg(s, &msg, 0);
+ return rc;
+}
+
+int
+babel_send(int s,
+ void *buf1, int buflen1, void *buf2, int buflen2,
+ struct sockaddr *sin, int slen)
+{
+ struct iovec iovec[2];
+ struct msghdr msg;
+ int rc;
+
+ iovec[0].iov_base = buf1;
+ iovec[0].iov_len = buflen1;
+ iovec[1].iov_base = buf2;
+ iovec[1].iov_len = buflen2;
+ memset(&msg, 0, sizeof(msg));
+ msg.msg_name = (struct sockaddr*)sin;
+ msg.msg_namelen = slen;
+ msg.msg_iov = iovec;
+ msg.msg_iovlen = 2;
+
+ again:
+ rc = sendmsg(s, &msg, 0);
+ if(rc < 0) {
+ if(errno == EINTR)
+ goto again;
+ else if(errno == EAGAIN) {
+ int rc2;
+ rc2 = wait_for_fd(1, s, 5);
+ if(rc2 > 0)
+ goto again;
+ errno = EAGAIN;
+ }
+ }
+ return rc;
+}
+
+int
+tcp_server_socket(int port, int local)
+{
+ struct sockaddr_in6 sin6;
+ int s, rc, saved_errno;
+ int one = 1;
+
+ s = socket(PF_INET6, SOCK_STREAM, 0);
+ if(s < 0)
+ return -1;
+
+ rc = setsockopt(s, SOL_SOCKET, SO_REUSEADDR, &one, sizeof(one));
+ if(rc < 0)
+ goto fail;
+
+ rc = fcntl(s, F_GETFL, 0);
+ if(rc < 0)
+ goto fail;
+
+ rc = fcntl(s, F_SETFL, (rc | O_NONBLOCK));
+ if(rc < 0)
+ goto fail;
+
+ rc = fcntl(s, F_GETFD, 0);
+ if(rc < 0)
+ goto fail;
+
+ rc = fcntl(s, F_SETFD, rc | FD_CLOEXEC);
+ if(rc < 0)
+ goto fail;
+
+ memset(&sin6, 0, sizeof(sin6));
+ sin6.sin6_family = AF_INET6;
+ sin6.sin6_port = htons(port);
+ if(local) {
+ rc = inet_pton(AF_INET6, "::1", &sin6.sin6_addr);
+ if(rc < 0)
+ goto fail;
+ }
+ rc = bind(s, (struct sockaddr*)&sin6, sizeof(sin6));
+ if(rc < 0)
+ goto fail;
+
+ rc = listen(s, 2);
+ if(rc < 0)
+ goto fail;
+
+ return s;
+
+ fail:
+ saved_errno = errno;
+ close(s);
+ errno = saved_errno;
+ return -1;
+}
diff --git a/babeld/net.h b/babeld/net.h
new file mode 100644
index 00000000..4bd0f04f
--- /dev/null
+++ b/babeld/net.h
@@ -0,0 +1,44 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+int babel_socket(int port);
+int babel_recv(int s, void *buf, int buflen, struct sockaddr *sin, int slen);
+int babel_send(int s,
+ void *buf1, int buflen1, void *buf2, int buflen2,
+ struct sockaddr *sin, int slen);
+int tcp_server_socket(int port, int local);
diff --git a/babeld/resend.c b/babeld/resend.c
new file mode 100644
index 00000000..1cc6290e
--- /dev/null
+++ b/babeld/resend.c
@@ -0,0 +1,330 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include <sys/time.h>
+#include <time.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include <zebra.h>
+#include "if.h"
+
+#include "babel_main.h"
+#include "babeld.h"
+#include "util.h"
+#include "neighbour.h"
+#include "resend.h"
+#include "message.h"
+#include "babel_interface.h"
+
+struct timeval resend_time = {0, 0};
+struct resend *to_resend = NULL;
+
+static int
+resend_match(struct resend *resend,
+ int kind, const unsigned char *prefix, unsigned char plen)
+{
+ return (resend->kind == kind &&
+ resend->plen == plen && memcmp(resend->prefix, prefix, 16) == 0);
+}
+
+/* This is called by neigh.c when a neighbour is flushed */
+
+void
+flush_resends(struct neighbour *neigh)
+{
+ /* Nothing for now */
+}
+
+static struct resend *
+find_resend(int kind, const unsigned char *prefix, unsigned char plen,
+ struct resend **previous_return)
+{
+ struct resend *current, *previous;
+
+ previous = NULL;
+ current = to_resend;
+ while(current) {
+ if(resend_match(current, kind, prefix, plen)) {
+ if(previous_return)
+ *previous_return = previous;
+ return current;
+ }
+ previous = current;
+ current = current->next;
+ }
+
+ return NULL;
+}
+
+struct resend *
+find_request(const unsigned char *prefix, unsigned char plen,
+ struct resend **previous_return)
+{
+ return find_resend(RESEND_REQUEST, prefix, plen, previous_return);
+}
+
+int
+record_resend(int kind, const unsigned char *prefix, unsigned char plen,
+ unsigned short seqno, const unsigned char *id,
+ struct interface *ifp, int delay)
+{
+ struct resend *resend;
+ unsigned int ifindex = ifp ? ifp->ifindex : 0;
+
+ if((kind == RESEND_REQUEST &&
+ input_filter(NULL, prefix, plen, NULL, ifindex) >= INFINITY) ||
+ (kind == RESEND_UPDATE &&
+ output_filter(NULL, prefix, plen, ifindex) >= INFINITY))
+ return 0;
+
+ if(delay >= 0xFFFF)
+ delay = 0xFFFF;
+
+ resend = find_resend(kind, prefix, plen, NULL);
+ if(resend) {
+ if(resend->delay && delay)
+ resend->delay = MIN(resend->delay, delay);
+ else if(delay)
+ resend->delay = delay;
+ resend->time = babel_now;
+ resend->max = RESEND_MAX;
+ if(id && memcmp(resend->id, id, 8) == 0 &&
+ seqno_compare(resend->seqno, seqno) > 0) {
+ return 0;
+ }
+ if(id)
+ memcpy(resend->id, id, 8);
+ else
+ memset(resend->id, 0, 8);
+ resend->seqno = seqno;
+ if(resend->ifp != ifp)
+ resend->ifp = NULL;
+ } else {
+ resend = malloc(sizeof(struct resend));
+ if(resend == NULL)
+ return -1;
+ resend->kind = kind;
+ resend->max = RESEND_MAX;
+ resend->delay = delay;
+ memcpy(resend->prefix, prefix, 16);
+ resend->plen = plen;
+ resend->seqno = seqno;
+ if(id)
+ memcpy(resend->id, id, 8);
+ else
+ memset(resend->id, 0, 8);
+ resend->ifp = ifp;
+ resend->time = babel_now;
+ resend->next = to_resend;
+ to_resend = resend;
+ }
+
+ if(resend->delay) {
+ struct timeval timeout;
+ timeval_add_msec(&timeout, &resend->time, resend->delay);
+ timeval_min(&resend_time, &timeout);
+ }
+ return 1;
+}
+
+static int
+resend_expired(struct resend *resend)
+{
+ switch(resend->kind) {
+ case RESEND_REQUEST:
+ return timeval_minus_msec(&babel_now, &resend->time) >= REQUEST_TIMEOUT;
+ default:
+ return resend->max <= 0;
+ }
+}
+
+int
+unsatisfied_request(const unsigned char *prefix, unsigned char plen,
+ unsigned short seqno, const unsigned char *id)
+{
+ struct resend *request;
+
+ request = find_request(prefix, plen, NULL);
+ if(request == NULL || resend_expired(request))
+ return 0;
+
+ if(memcmp(request->id, id, 8) != 0 ||
+ seqno_compare(request->seqno, seqno) <= 0)
+ return 1;
+
+ return 0;
+}
+
+/* Determine whether a given request should be forwarded. */
+int
+request_redundant(struct interface *ifp,
+ const unsigned char *prefix, unsigned char plen,
+ unsigned short seqno, const unsigned char *id)
+{
+ struct resend *request;
+
+ request = find_request(prefix, plen, NULL);
+ if(request == NULL || resend_expired(request))
+ return 0;
+
+ if(memcmp(request->id, id, 8) == 0 &&
+ seqno_compare(request->seqno, seqno) > 0)
+ return 0;
+
+ if(request->ifp != NULL && request->ifp != ifp)
+ return 0;
+
+ if(request->max > 0)
+ /* Will be resent. */
+ return 1;
+
+ if(timeval_minus_msec(&babel_now, &request->time) <
+ (ifp ? MIN(babel_get_if_nfo(ifp)->hello_interval, 1000) : 1000))
+ /* Fairly recent. */
+ return 1;
+
+ return 0;
+}
+
+int
+satisfy_request(const unsigned char *prefix, unsigned char plen,
+ unsigned short seqno, const unsigned char *id,
+ struct interface *ifp)
+{
+ struct resend *request, *previous;
+
+ request = find_request(prefix, plen, &previous);
+ if(request == NULL)
+ return 0;
+
+ if(ifp != NULL && request->ifp != ifp)
+ return 0;
+
+ if(memcmp(request->id, id, 8) != 0 ||
+ seqno_compare(request->seqno, seqno) <= 0) {
+ /* We cannot remove the request, as we may be walking the list right
+ now. Mark it as expired, so that expire_resend will remove it. */
+ request->max = 0;
+ request->time.tv_sec = 0;
+ recompute_resend_time();
+ return 1;
+ }
+
+ return 0;
+}
+
+void
+expire_resend()
+{
+ struct resend *current, *previous;
+ int recompute = 0;
+
+ previous = NULL;
+ current = to_resend;
+ while(current) {
+ if(resend_expired(current)) {
+ if(previous == NULL) {
+ to_resend = current->next;
+ free(current);
+ current = to_resend;
+ } else {
+ previous->next = current->next;
+ free(current);
+ current = previous->next;
+ }
+ recompute = 1;
+ } else {
+ previous = current;
+ current = current->next;
+ }
+ }
+ if(recompute)
+ recompute_resend_time();
+}
+
+void
+recompute_resend_time()
+{
+ struct resend *request;
+ struct timeval resend = {0, 0};
+
+ request = to_resend;
+ while(request) {
+ if(!resend_expired(request) && request->delay > 0 && request->max > 0) {
+ struct timeval timeout;
+ timeval_add_msec(&timeout, &request->time, request->delay);
+ timeval_min(&resend, &timeout);
+ }
+ request = request->next;
+ }
+
+ resend_time = resend;
+}
+
+void
+do_resend()
+{
+ struct resend *resend;
+
+ resend = to_resend;
+ while(resend) {
+ if(!resend_expired(resend) && resend->delay > 0 && resend->max > 0) {
+ struct timeval timeout;
+ timeval_add_msec(&timeout, &resend->time, resend->delay);
+ if(timeval_compare(&babel_now, &timeout) >= 0) {
+ switch(resend->kind) {
+ case RESEND_REQUEST:
+ send_multihop_request(resend->ifp,
+ resend->prefix, resend->plen,
+ resend->seqno, resend->id, 127);
+ break;
+ case RESEND_UPDATE:
+ send_update(resend->ifp, 1,
+ resend->prefix, resend->plen);
+ break;
+ default: abort();
+ }
+ resend->delay = MIN(0xFFFF, resend->delay * 2);
+ resend->max--;
+ }
+ }
+ resend = resend->next;
+ }
+ recompute_resend_time();
+}
diff --git a/babeld/resend.h b/babeld/resend.h
new file mode 100644
index 00000000..a6755c0e
--- /dev/null
+++ b/babeld/resend.h
@@ -0,0 +1,77 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#define REQUEST_TIMEOUT 65000
+#define RESEND_MAX 3
+
+#define RESEND_REQUEST 1
+#define RESEND_UPDATE 2
+
+struct resend {
+ unsigned char kind;
+ unsigned char max;
+ unsigned short delay;
+ struct timeval time;
+ unsigned char prefix[16];
+ unsigned char plen;
+ unsigned short seqno;
+ unsigned char id[8];
+ struct interface *ifp;
+ struct resend *next;
+};
+
+extern struct timeval resend_time;
+
+struct resend *find_request(const unsigned char *prefix, unsigned char plen,
+ struct resend **previous_return);
+void flush_resends(struct neighbour *neigh);
+int record_resend(int kind, const unsigned char *prefix, unsigned char plen,
+ unsigned short seqno, const unsigned char *id,
+ struct interface *ifp, int delay);
+int unsatisfied_request(const unsigned char *prefix, unsigned char plen,
+ unsigned short seqno, const unsigned char *id);
+int request_redundant(struct interface *ifp,
+ const unsigned char *prefix, unsigned char plen,
+ unsigned short seqno, const unsigned char *id);
+int satisfy_request(const unsigned char *prefix, unsigned char plen,
+ unsigned short seqno, const unsigned char *id,
+ struct interface *ifp);
+
+void expire_resend(void);
+void recompute_resend_time(void);
+void do_resend(void);
diff --git a/babeld/route.c b/babeld/route.c
new file mode 100644
index 00000000..fe2b9ceb
--- /dev/null
+++ b/babeld/route.c
@@ -0,0 +1,1019 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include <zebra.h>
+#include "if.h"
+
+#include "babeld.h"
+#include "util.h"
+#include "kernel.h"
+#include "babel_interface.h"
+#include "source.h"
+#include "neighbour.h"
+#include "route.h"
+#include "xroute.h"
+#include "message.h"
+#include "resend.h"
+
+static void consider_route(struct babel_route *route);
+
+struct babel_route **routes = NULL;
+static int route_slots = 0, max_route_slots = 0;
+int kernel_metric = 0;
+int allow_duplicates = -1;
+int diversity_kind = DIVERSITY_NONE;
+int diversity_factor = 256; /* in units of 1/256 */
+int keep_unfeasible = 0;
+
+/* We maintain a list of "slots", ordered by prefix. Every slot
+ contains a linked list of the routes to this prefix, with the
+ installed route, if any, at the head of the list. */
+
+static int
+route_compare(const unsigned char *prefix, unsigned char plen,
+ struct babel_route *route)
+{
+ int i = memcmp(prefix, route->src->prefix, 16);
+ if(i != 0)
+ return i;
+
+ if(plen < route->src->plen)
+ return -1;
+ else if(plen > route->src->plen)
+ return 1;
+ else
+ return 0;
+}
+
+/* Performs binary search, returns -1 in case of failure. In the latter
+ case, new_return is the place where to insert the new element. */
+
+static int
+find_route_slot(const unsigned char *prefix, unsigned char plen,
+ int *new_return)
+{
+ int p, m, g, c;
+
+ if(route_slots < 1) {
+ if(new_return)
+ *new_return = 0;
+ return -1;
+ }
+
+ p = 0; g = route_slots - 1;
+
+ do {
+ m = (p + g) / 2;
+ c = route_compare(prefix, plen, routes[m]);
+ if(c == 0)
+ return m;
+ else if(c < 0)
+ g = m - 1;
+ else
+ p = m + 1;
+ } while(p <= g);
+
+ if(new_return)
+ *new_return = p;
+
+ return -1;
+}
+
+struct babel_route *
+find_route(const unsigned char *prefix, unsigned char plen,
+ struct neighbour *neigh, const unsigned char *nexthop)
+{
+ struct babel_route *route;
+ int i = find_route_slot(prefix, plen, NULL);
+
+ if(i < 0)
+ return NULL;
+
+ route = routes[i];
+
+ while(route) {
+ if(route->neigh == neigh && memcmp(route->nexthop, nexthop, 16) == 0)
+ return route;
+ route = route->next;
+ }
+
+ return NULL;
+}
+
+struct babel_route *
+find_installed_route(const unsigned char *prefix, unsigned char plen)
+{
+ int i = find_route_slot(prefix, plen, NULL);
+
+ if(i >= 0 && routes[i]->installed)
+ return routes[i];
+
+ return NULL;
+}
+
+/* Returns an overestimate of the number of installed routes. */
+int
+installed_routes_estimate(void)
+{
+ return route_slots;
+}
+
+static int
+resize_route_table(int new_slots)
+{
+ struct babel_route **new_routes;
+ assert(new_slots >= route_slots);
+
+ if(new_slots == 0) {
+ new_routes = NULL;
+ free(routes);
+ } else {
+ new_routes = realloc(routes, new_slots * sizeof(struct babel_route*));
+ if(new_routes == NULL)
+ return -1;
+ }
+
+ max_route_slots = new_slots;
+ routes = new_routes;
+ return 1;
+}
+
+/* Insert a route into the table. If successful, retains the route.
+ On failure, caller must free the route. */
+static struct babel_route *
+insert_route(struct babel_route *route)
+{
+ int i, n;
+
+ assert(!route->installed);
+
+ i = find_route_slot(route->src->prefix, route->src->plen, &n);
+
+ if(i < 0) {
+ if(route_slots >= max_route_slots)
+ resize_route_table(max_route_slots < 1 ? 8 : 2 * max_route_slots);
+ if(route_slots >= max_route_slots)
+ return NULL;
+ route->next = NULL;
+ if(n < route_slots)
+ memmove(routes + n + 1, routes + n,
+ (route_slots - n) * sizeof(struct babel_route*));
+ route_slots++;
+ routes[n] = route;
+ } else {
+ struct babel_route *r;
+ r = routes[i];
+ while(r->next)
+ r = r->next;
+ r->next = route;
+ route->next = NULL;
+ }
+
+ return route;
+}
+
+void
+flush_route(struct babel_route *route)
+{
+ int i;
+ struct source *src;
+ unsigned oldmetric;
+ int lost = 0;
+
+ oldmetric = route_metric(route);
+ src = route->src;
+
+ if(route->installed) {
+ uninstall_route(route);
+ lost = 1;
+ }
+
+ i = find_route_slot(route->src->prefix, route->src->plen, NULL);
+ assert(i >= 0 && i < route_slots);
+
+ if(route == routes[i]) {
+ routes[i] = route->next;
+ route->next = NULL;
+ free(route);
+
+ if(routes[i] == NULL) {
+ if(i < route_slots - 1)
+ memmove(routes + i, routes + i + 1,
+ (route_slots - i - 1) * sizeof(struct babel_route*));
+ routes[route_slots - 1] = NULL;
+ route_slots--;
+ }
+
+ if(route_slots == 0)
+ resize_route_table(0);
+ else if(max_route_slots > 8 && route_slots < max_route_slots / 4)
+ resize_route_table(max_route_slots / 2);
+ } else {
+ struct babel_route *r = routes[i];
+ while(r->next != route)
+ r = r->next;
+ r->next = route->next;
+ route->next = NULL;
+ free(route);
+ }
+
+ if(lost)
+ route_lost(src, oldmetric);
+
+ release_source(src);
+}
+
+void
+flush_all_routes()
+{
+ int i;
+
+ /* Start from the end, to avoid shifting the table. */
+ i = route_slots - 1;
+ while(i >= 0) {
+ while(i < route_slots) {
+ /* Uninstall first, to avoid calling route_lost. */
+ if(routes[i]->installed)
+ uninstall_route(routes[0]);
+ flush_route(routes[i]);
+ }
+ i--;
+ }
+
+ check_sources_released();
+}
+
+void
+flush_neighbour_routes(struct neighbour *neigh)
+{
+ int i;
+
+ i = 0;
+ while(i < route_slots) {
+ struct babel_route *r;
+ r = routes[i];
+ while(r) {
+ if(r->neigh == neigh) {
+ flush_route(r);
+ goto again;
+ }
+ r = r->next;
+ }
+ i++;
+ again:
+ ;
+ }
+}
+
+void
+flush_interface_routes(struct interface *ifp, int v4only)
+{
+ int i;
+
+ i = 0;
+ while(i < route_slots) {
+ struct babel_route *r;
+ r = routes[i];
+ while(r) {
+ if(r->neigh->ifp == ifp &&
+ (!v4only || v4mapped(r->nexthop))) {
+ flush_route(r);
+ goto again;
+ }
+ r = r->next;
+ }
+ i++;
+ again:
+ ;
+ }
+}
+
+/* Iterate a function over all routes. */
+void
+for_all_routes(void (*f)(struct babel_route*, void*), void *closure)
+{
+ int i;
+
+ for(i = 0; i < route_slots; i++) {
+ struct babel_route *r = routes[i];
+ while(r) {
+ (*f)(r, closure);
+ r = r->next;
+ }
+ }
+}
+
+void
+for_all_installed_routes(void (*f)(struct babel_route*, void*), void *closure)
+{
+ int i;
+
+ for(i = 0; i < route_slots; i++) {
+ if(routes[i]->installed)
+ (*f)(routes[i], closure);
+ }
+}
+
+static int
+metric_to_kernel(int metric)
+{
+ return metric < INFINITY ? kernel_metric : KERNEL_INFINITY;
+}
+
+/* This is used to maintain the invariant that the installed route is at
+ the head of the list. */
+static void
+move_installed_route(struct babel_route *route, int i)
+{
+ assert(i >= 0 && i < route_slots);
+ assert(route->installed);
+
+ if(route != routes[i]) {
+ struct babel_route *r = routes[i];
+ while(r->next != route)
+ r = r->next;
+ r->next = route->next;
+ route->next = routes[i];
+ routes[i] = route;
+ }
+}
+
+void
+install_route(struct babel_route *route)
+{
+ int i, rc;
+
+ if(route->installed)
+ return;
+
+ if(!route_feasible(route))
+ zlog_err("WARNING: installing unfeasible route "
+ "(this shouldn't happen).");
+
+ i = find_route_slot(route->src->prefix, route->src->plen, NULL);
+ assert(i >= 0 && i < route_slots);
+
+ if(routes[i] != route && routes[i]->installed) {
+ fprintf(stderr, "WARNING: attempting to install duplicate route "
+ "(this shouldn't happen).");
+ return;
+ }
+
+ rc = kernel_route(ROUTE_ADD, route->src->prefix, route->src->plen,
+ route->nexthop,
+ route->neigh->ifp->ifindex,
+ metric_to_kernel(route_metric(route)), NULL, 0, 0);
+ if(rc < 0) {
+ int save = errno;
+ zlog_err("kernel_route(ADD): %s", safe_strerror(errno));
+ if(save != EEXIST)
+ return;
+ }
+ route->installed = 1;
+ move_installed_route(route, i);
+
+}
+
+void
+uninstall_route(struct babel_route *route)
+{
+ int rc;
+
+ if(!route->installed)
+ return;
+
+ rc = kernel_route(ROUTE_FLUSH, route->src->prefix, route->src->plen,
+ route->nexthop,
+ route->neigh->ifp->ifindex,
+ metric_to_kernel(route_metric(route)), NULL, 0, 0);
+ if(rc < 0)
+ zlog_err("kernel_route(FLUSH): %s", safe_strerror(errno));
+
+ route->installed = 0;
+}
+
+/* This is equivalent to uninstall_route followed with install_route,
+ but without the race condition. The destination of both routes
+ must be the same. */
+
+static void
+switch_routes(struct babel_route *old, struct babel_route *new)
+{
+ int rc;
+
+ if(!old) {
+ install_route(new);
+ return;
+ }
+
+ if(!old->installed)
+ return;
+
+ if(!route_feasible(new))
+ zlog_err("WARNING: switching to unfeasible route "
+ "(this shouldn't happen).");
+
+ rc = kernel_route(ROUTE_MODIFY, old->src->prefix, old->src->plen,
+ old->nexthop, old->neigh->ifp->ifindex,
+ metric_to_kernel(route_metric(old)),
+ new->nexthop, new->neigh->ifp->ifindex,
+ metric_to_kernel(route_metric(new)));
+ if(rc < 0) {
+ zlog_err("kernel_route(MODIFY): %s", safe_strerror(errno));
+ return;
+ }
+
+ old->installed = 0;
+ new->installed = 1;
+ move_installed_route(new, find_route_slot(new->src->prefix, new->src->plen,
+ NULL));
+}
+
+static void
+change_route_metric(struct babel_route *route,
+ unsigned refmetric, unsigned cost, unsigned add)
+{
+ int old, new;
+ int newmetric = MIN(refmetric + cost + add, INFINITY);
+
+ old = metric_to_kernel(route_metric(route));
+ new = metric_to_kernel(newmetric);
+
+ if(route->installed && old != new) {
+ int rc;
+ rc = kernel_route(ROUTE_MODIFY, route->src->prefix, route->src->plen,
+ route->nexthop, route->neigh->ifp->ifindex,
+ old,
+ route->nexthop, route->neigh->ifp->ifindex,
+ new);
+ if(rc < 0) {
+ zlog_err("kernel_route(MODIFY metric): %s", safe_strerror(errno));
+ return;
+ }
+ }
+
+ route->refmetric = refmetric;
+ route->cost = cost;
+ route->add_metric = add;
+}
+
+static void
+retract_route(struct babel_route *route)
+{
+ change_route_metric(route, INFINITY, INFINITY, 0);
+}
+
+int
+route_feasible(struct babel_route *route)
+{
+ return update_feasible(route->src, route->seqno, route->refmetric);
+}
+
+int
+route_old(struct babel_route *route)
+{
+ return route->time < babel_now.tv_sec - route->hold_time * 7 / 8;
+}
+
+int
+route_expired(struct babel_route *route)
+{
+ return route->time < babel_now.tv_sec - route->hold_time;
+}
+
+static int
+channels_interfere(int ch1, int ch2)
+{
+ if(ch1 == BABEL_IF_CHANNEL_NONINTERFERING
+ || ch2 == BABEL_IF_CHANNEL_NONINTERFERING)
+ return 0;
+ if(ch1 == BABEL_IF_CHANNEL_INTERFERING
+ || ch2 == BABEL_IF_CHANNEL_INTERFERING)
+ return 1;
+ return ch1 == ch2;
+}
+
+int
+route_interferes(struct babel_route *route, struct interface *ifp)
+{
+ struct babel_interface *babel_ifp = NULL;
+ switch(diversity_kind) {
+ case DIVERSITY_NONE:
+ return 1;
+ case DIVERSITY_INTERFACE_1:
+ return route->neigh->ifp == ifp;
+ case DIVERSITY_CHANNEL_1:
+ case DIVERSITY_CHANNEL:
+ if(route->neigh->ifp == ifp)
+ return 1;
+ babel_ifp = babel_get_if_nfo(ifp);
+ if(channels_interfere(babel_ifp->channel,
+ babel_get_if_nfo(route->neigh->ifp)->channel))
+ return 1;
+ if(diversity_kind == DIVERSITY_CHANNEL) {
+ int i;
+ for(i = 0; i < DIVERSITY_HOPS; i++) {
+ if(route->channels[i] == 0)
+ break;
+ if(channels_interfere(babel_ifp->channel, route->channels[i]))
+ return 1;
+ }
+ }
+ return 0;
+ default:
+ fprintf(stderr, "Unknown kind of diversity.\n");
+ return 1;
+ }
+}
+
+int
+update_feasible(struct source *src,
+ unsigned short seqno, unsigned short refmetric)
+{
+ if(src == NULL)
+ return 1;
+
+ if(src->time < babel_now.tv_sec - SOURCE_GC_TIME)
+ /* Never mind what is probably stale data */
+ return 1;
+
+ if(refmetric >= INFINITY)
+ /* Retractions are always feasible */
+ return 1;
+
+ return (seqno_compare(seqno, src->seqno) > 0 ||
+ (src->seqno == seqno && refmetric < src->metric));
+}
+
+/* This returns the feasible route with the smallest metric. */
+struct babel_route *
+find_best_route(const unsigned char *prefix, unsigned char plen, int feasible,
+ struct neighbour *exclude)
+{
+ struct babel_route *route = NULL, *r = NULL;
+ int i = find_route_slot(prefix, plen, NULL);
+
+ if(i < 0)
+ return NULL;
+
+ route = routes[i];
+
+ r = route->next;
+ while(r) {
+ if(!route_expired(r) &&
+ (!feasible || route_feasible(r)) &&
+ (!exclude || r->neigh != exclude) &&
+ (route_metric(r) < route_metric(route)))
+ route = r;
+ r = r->next;
+ }
+ return route;
+}
+
+void
+update_route_metric(struct babel_route *route)
+{
+ int oldmetric = route_metric(route);
+
+ if(route_expired(route)) {
+ if(route->refmetric < INFINITY) {
+ route->seqno = seqno_plus(route->src->seqno, 1);
+ retract_route(route);
+ if(oldmetric < INFINITY)
+ route_changed(route, route->src, oldmetric);
+ }
+ } else {
+ struct neighbour *neigh = route->neigh;
+ int add_metric = input_filter(route->src->id,
+ route->src->prefix, route->src->plen,
+ neigh->address,
+ neigh->ifp->ifindex);
+ change_route_metric(route, route->refmetric,
+ neighbour_cost(route->neigh), add_metric);
+ if(route_metric(route) != oldmetric)
+ route_changed(route, route->src, oldmetric);
+ }
+}
+
+/* Called whenever a neighbour's cost changes, to update the metric of
+ all routes through that neighbour. Calls local_notify_neighbour. */
+void
+update_neighbour_metric(struct neighbour *neigh, int changed)
+{
+
+ if(changed) {
+ int i;
+
+ for(i = 0; i < route_slots; i++) {
+ struct babel_route *r = routes[i];
+ while(r) {
+ if(r->neigh == neigh)
+ update_route_metric(r);
+ r = r->next;
+ }
+ }
+ }
+}
+
+void
+update_interface_metric(struct interface *ifp)
+{
+ int i;
+
+ for(i = 0; i < route_slots; i++) {
+ struct babel_route *r = routes[i];
+ while(r) {
+ if(r->neigh->ifp == ifp)
+ update_route_metric(r);
+ r = r->next;
+ }
+ }
+}
+
+/* This is called whenever we receive an update. */
+struct babel_route *
+update_route(const unsigned char *router_id,
+ const unsigned char *prefix, unsigned char plen,
+ unsigned short seqno, unsigned short refmetric,
+ unsigned short interval,
+ struct neighbour *neigh, const unsigned char *nexthop,
+ const unsigned char *channels, int channels_len)
+{
+ struct babel_route *route;
+ struct source *src;
+ int metric, feasible;
+ int add_metric;
+ int hold_time = MAX((4 * interval) / 100 + interval / 50, 15);
+
+ if(memcmp(router_id, myid, 8) == 0)
+ return NULL;
+
+ if(martian_prefix(prefix, plen)) {
+ zlog_err("Rejecting martian route to %s through %s.",
+ format_prefix(prefix, plen), format_address(router_id));
+ return NULL;
+ }
+
+ add_metric = input_filter(router_id, prefix, plen,
+ neigh->address, neigh->ifp->ifindex);
+ if(add_metric >= INFINITY)
+ return NULL;
+
+ route = find_route(prefix, plen, neigh, nexthop);
+
+ if(route && memcmp(route->src->id, router_id, 8) == 0)
+ /* Avoid scanning the source table. */
+ src = route->src;
+ else
+ src = find_source(router_id, prefix, plen, 1, seqno);
+
+ if(src == NULL)
+ return NULL;
+
+ feasible = update_feasible(src, seqno, refmetric);
+ metric = MIN((int)refmetric + neighbour_cost(neigh) + add_metric, INFINITY);
+
+ if(route) {
+ struct source *oldsrc;
+ unsigned short oldmetric;
+ int lost = 0;
+
+ oldsrc = route->src;
+ oldmetric = route_metric(route);
+
+ /* If a successor switches sources, we must accept his update even
+ if it makes a route unfeasible in order to break any routing loops
+ in a timely manner. If the source remains the same, we ignore
+ the update. */
+ if(!feasible && route->installed) {
+ debugf(BABEL_DEBUG_COMMON,"Unfeasible update for installed route to %s "
+ "(%s %d %d -> %s %d %d).",
+ format_prefix(src->prefix, src->plen),
+ format_address(route->src->id),
+ route->seqno, route->refmetric,
+ format_address(src->id), seqno, refmetric);
+ if(src != route->src) {
+ uninstall_route(route);
+ lost = 1;
+ }
+ }
+
+ route->src = retain_source(src);
+ if((feasible || keep_unfeasible) && refmetric < INFINITY)
+ route->time = babel_now.tv_sec;
+ route->seqno = seqno;
+ change_route_metric(route,
+ refmetric, neighbour_cost(neigh), add_metric);
+ route->hold_time = hold_time;
+
+ route_changed(route, oldsrc, oldmetric);
+ if(lost)
+ route_lost(oldsrc, oldmetric);
+
+ if(!feasible)
+ send_unfeasible_request(neigh, route->installed && route_old(route),
+ seqno, metric, src);
+ release_source(oldsrc);
+ } else {
+ struct babel_route *new_route;
+
+ if(refmetric >= INFINITY)
+ /* Somebody's retracting a route we never saw. */
+ return NULL;
+ if(!feasible) {
+ send_unfeasible_request(neigh, 0, seqno, metric, src);
+ if(!keep_unfeasible)
+ return NULL;
+ }
+
+ route = malloc(sizeof(struct babel_route));
+ if(route == NULL) {
+ perror("malloc(route)");
+ return NULL;
+ }
+
+ route->src = retain_source(src);
+ route->refmetric = refmetric;
+ route->cost = neighbour_cost(neigh);
+ route->add_metric = add_metric;
+ route->seqno = seqno;
+ route->neigh = neigh;
+ memcpy(route->nexthop, nexthop, 16);
+ route->time = babel_now.tv_sec;
+ route->hold_time = hold_time;
+ route->installed = 0;
+ memset(&route->channels, 0, sizeof(route->channels));
+ if(channels_len > 0)
+ memcpy(&route->channels, channels,
+ MIN(channels_len, DIVERSITY_HOPS));
+ route->next = NULL;
+ new_route = insert_route(route);
+ if(new_route == NULL) {
+ fprintf(stderr, "Couldn't insert route.\n");
+ free(route);
+ return NULL;
+ }
+ consider_route(route);
+ }
+ return route;
+}
+
+/* We just received an unfeasible update. If it's any good, send
+ a request for a new seqno. */
+void
+send_unfeasible_request(struct neighbour *neigh, int force,
+ unsigned short seqno, unsigned short metric,
+ struct source *src)
+{
+ struct babel_route *route = find_installed_route(src->prefix, src->plen);
+
+ if(seqno_minus(src->seqno, seqno) > 100) {
+ /* Probably a source that lost its seqno. Let it time-out. */
+ return;
+ }
+
+ if(force || !route || route_metric(route) >= metric + 512) {
+ send_unicast_multihop_request(neigh, src->prefix, src->plen,
+ src->metric >= INFINITY ?
+ src->seqno :
+ seqno_plus(src->seqno, 1),
+ src->id, 127);
+ }
+}
+
+/* This takes a feasible route and decides whether to install it. */
+static void
+consider_route(struct babel_route *route)
+{
+ struct babel_route *installed;
+ struct xroute *xroute;
+
+ if(route->installed)
+ return;
+
+ if(!route_feasible(route))
+ return;
+
+ xroute = find_xroute(route->src->prefix, route->src->plen);
+ if(xroute && (allow_duplicates < 0 || xroute->metric >= allow_duplicates))
+ return;
+
+ installed = find_installed_route(route->src->prefix, route->src->plen);
+
+ if(installed == NULL)
+ goto install;
+
+ if(route_metric(route) >= INFINITY)
+ return;
+
+ if(route_metric(installed) >= INFINITY)
+ goto install;
+
+ if(route_metric(installed) >= route_metric(route) + 64)
+ goto install;
+
+ return;
+
+ install:
+ switch_routes(installed, route);
+ if(installed && route->installed)
+ send_triggered_update(route, installed->src, route_metric(installed));
+ else
+ send_update(NULL, 1, route->src->prefix, route->src->plen);
+ return;
+}
+
+void
+retract_neighbour_routes(struct neighbour *neigh)
+{
+ int i;
+
+ for(i = 0; i < route_slots; i++) {
+ struct babel_route *r = routes[i];
+ while(r) {
+ if(r->neigh == neigh) {
+ if(r->refmetric != INFINITY) {
+ unsigned short oldmetric = route_metric(r);
+ retract_route(r);
+ if(oldmetric != INFINITY)
+ route_changed(r, r->src, oldmetric);
+ }
+ }
+ r = r->next;
+ }
+ i++;
+ }
+}
+
+void
+send_triggered_update(struct babel_route *route, struct source *oldsrc,
+ unsigned oldmetric)
+{
+ unsigned newmetric, diff;
+ /* 1 means send speedily, 2 means resend */
+ int urgent;
+
+ if(!route->installed)
+ return;
+
+ newmetric = route_metric(route);
+ diff =
+ newmetric >= oldmetric ? newmetric - oldmetric : oldmetric - newmetric;
+
+ if(route->src != oldsrc || (oldmetric < INFINITY && newmetric >= INFINITY))
+ /* Switching sources can cause transient routing loops.
+ Retractions can cause blackholes. */
+ urgent = 2;
+ else if(newmetric > oldmetric && oldmetric < 6 * 256 && diff >= 512)
+ /* Route getting significantly worse */
+ urgent = 1;
+ else if(unsatisfied_request(route->src->prefix, route->src->plen,
+ route->seqno, route->src->id))
+ /* Make sure that requests are satisfied speedily */
+ urgent = 1;
+ else if(oldmetric >= INFINITY && newmetric < INFINITY)
+ /* New route */
+ urgent = 0;
+ else if(newmetric < oldmetric && diff < 1024)
+ /* Route getting better. This may be a transient fluctuation, so
+ don't advertise it to avoid making routes unfeasible later on. */
+ return;
+ else if(diff < 384)
+ /* Don't fret about trivialities */
+ return;
+ else
+ urgent = 0;
+
+ if(urgent >= 2)
+ send_update_resend(NULL, route->src->prefix, route->src->plen);
+ else
+ send_update(NULL, urgent, route->src->prefix, route->src->plen);
+
+ if(oldmetric < INFINITY) {
+ if(newmetric >= oldmetric + 512) {
+ send_request_resend(NULL, route->src->prefix, route->src->plen,
+ route->src->metric >= INFINITY ?
+ route->src->seqno :
+ seqno_plus(route->src->seqno, 1),
+ route->src->id);
+ } else if(newmetric >= oldmetric + 288) {
+ send_request(NULL, route->src->prefix, route->src->plen);
+ }
+ }
+}
+
+/* A route has just changed. Decide whether to switch to a different route or
+ send an update. */
+void
+route_changed(struct babel_route *route,
+ struct source *oldsrc, unsigned short oldmetric)
+{
+ if(route->installed) {
+ if(route_metric(route) > oldmetric) {
+ struct babel_route *better_route;
+ better_route =
+ find_best_route(route->src->prefix, route->src->plen, 1, NULL);
+ if(better_route &&
+ route_metric(better_route) <= route_metric(route) - 96)
+ consider_route(better_route);
+ }
+
+ if(route->installed)
+ /* We didn't change routes after all. */
+ send_triggered_update(route, oldsrc, oldmetric);
+ } else {
+ /* Reconsider routes even when their metric didn't decrease,
+ they may not have been feasible before. */
+ consider_route(route);
+ }
+}
+
+/* We just lost the installed route to a given destination. */
+void
+route_lost(struct source *src, unsigned oldmetric)
+{
+ struct babel_route *new_route;
+ new_route = find_best_route(src->prefix, src->plen, 1, NULL);
+ if(new_route) {
+ consider_route(new_route);
+ } else if(oldmetric < INFINITY) {
+ /* Complain loudly. */
+ send_update_resend(NULL, src->prefix, src->plen);
+ send_request_resend(NULL, src->prefix, src->plen,
+ src->metric >= INFINITY ?
+ src->seqno : seqno_plus(src->seqno, 1),
+ src->id);
+ }
+}
+
+/* This is called periodically to flush old routes. It will also send
+ requests for routes that are about to expire. */
+void
+expire_routes(void)
+{
+ struct babel_route *r;
+ int i;
+
+ debugf(BABEL_DEBUG_COMMON,"Expiring old routes.");
+
+ i = 0;
+ while(i < route_slots) {
+ r = routes[i];
+ while(r) {
+ /* Protect against clock being stepped. */
+ if(r->time > babel_now.tv_sec || route_old(r)) {
+ flush_route(r);
+ goto again;
+ }
+
+ update_route_metric(r);
+
+ if(r->installed && r->refmetric < INFINITY) {
+ if(route_old(r))
+ /* Route about to expire, send a request. */
+ send_unicast_request(r->neigh,
+ r->src->prefix, r->src->plen);
+ }
+ r = r->next;
+ }
+ i++;
+ again:
+ ;
+ }
+}
diff --git a/babeld/route.h b/babeld/route.h
new file mode 100644
index 00000000..b6d2d294
--- /dev/null
+++ b/babeld/route.h
@@ -0,0 +1,135 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#ifndef BABEL_ROUTE_H
+#define BABEL_ROUTE_H
+
+#include "babel_interface.h"
+#include "source.h"
+
+#define DIVERSITY_NONE 0
+#define DIVERSITY_INTERFACE_1 1
+#define DIVERSITY_CHANNEL_1 2
+#define DIVERSITY_CHANNEL 3
+
+#define DIVERSITY_HOPS 8
+
+struct babel_route {
+ struct source *src;
+ unsigned short refmetric;
+ unsigned short cost;
+ unsigned short add_metric;
+ unsigned short seqno;
+ struct neighbour *neigh;
+ unsigned char nexthop[16];
+ time_t time;
+ unsigned short hold_time; /* in seconds */
+ short installed;
+ unsigned char channels[DIVERSITY_HOPS];
+ struct babel_route *next;
+};
+
+extern struct babel_route **routes;
+extern int kernel_metric, allow_duplicates;
+extern int diversity_kind, diversity_factor;
+extern int keep_unfeasible;
+
+static inline int
+route_metric(const struct babel_route *route)
+{
+ int m = (int)route->refmetric + route->cost + route->add_metric;
+ return MIN(m, INFINITY);
+}
+
+static inline int
+route_metric_noninterfering(const struct babel_route *route)
+{
+ int m =
+ (int)route->refmetric +
+ (diversity_factor * route->cost + 128) / 256 +
+ route->add_metric;
+ m = MAX(m, route->refmetric + 1);
+ return MIN(m, INFINITY);
+}
+
+struct babel_route *find_route(const unsigned char *prefix, unsigned char plen,
+ struct neighbour *neigh, const unsigned char *nexthop);
+struct babel_route *find_installed_route(const unsigned char *prefix,
+ unsigned char plen);
+int installed_routes_estimate(void);
+void flush_route(struct babel_route *route);
+void flush_all_routes(void);
+void flush_neighbour_routes(struct neighbour *neigh);
+void flush_interface_routes(struct interface *ifp, int v4only);
+void for_all_routes(void (*f)(struct babel_route*, void*), void *closure);
+void for_all_installed_routes(void (*f)(struct babel_route*, void*), void *closure);
+void install_route(struct babel_route *route);
+void uninstall_route(struct babel_route *route);
+void switch_route(struct babel_route *old, struct babel_route *new);
+int route_feasible(struct babel_route *route);
+int route_old(struct babel_route *route);
+int route_expired(struct babel_route *route);
+int route_interferes(struct babel_route *route, struct interface *ifp);
+int update_feasible(struct source *src,
+ unsigned short seqno, unsigned short refmetric);
+struct babel_route *find_best_route(const unsigned char *prefix, unsigned char plen,
+ int feasible, struct neighbour *exclude);
+struct babel_route *install_best_route(const unsigned char prefix[16],
+ unsigned char plen);
+void update_neighbour_metric(struct neighbour *neigh, int change);
+void update_interface_metric(struct interface *ifp);
+void update_route_metric(struct babel_route *route);
+struct babel_route *update_route(const unsigned char *id,
+ const unsigned char *prefix, unsigned char plen,
+ unsigned short seqno, unsigned short refmetric,
+ unsigned short interval, struct neighbour *neigh,
+ const unsigned char *nexthop,
+ const unsigned char *channels, int channels_len);
+void retract_neighbour_routes(struct neighbour *neigh);
+void send_unfeasible_request(struct neighbour *neigh, int force,
+ unsigned short seqno, unsigned short metric,
+ struct source *src);
+void send_triggered_update(struct babel_route *route,
+ struct source *oldsrc, unsigned oldmetric);
+void route_changed(struct babel_route *route,
+ struct source *oldsrc, unsigned short oldmetric);
+void route_lost(struct source *src, unsigned oldmetric);
+void expire_routes(void);
+
+#endif
diff --git a/babeld/source.c b/babeld/source.c
new file mode 100644
index 00000000..772112d4
--- /dev/null
+++ b/babeld/source.c
@@ -0,0 +1,180 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <sys/time.h>
+
+#include "babel_main.h"
+#include "babeld.h"
+#include "util.h"
+#include "source.h"
+#include "babel_interface.h"
+#include "route.h"
+
+struct source *srcs = NULL;
+
+struct source*
+find_source(const unsigned char *id, const unsigned char *p, unsigned char plen,
+ int create, unsigned short seqno)
+{
+ struct source *src;
+
+ for(src = srcs; src; src = src->next) {
+ /* This should really be a hash table. For now, check the
+ last byte first. */
+ if(src->id[7] != id[7])
+ continue;
+ if(memcmp(src->id, id, 8) != 0)
+ continue;
+ if(src->plen != plen)
+ continue;
+ if(memcmp(src->prefix, p, 16) == 0)
+ return src;
+ }
+
+ if(!create)
+ return NULL;
+
+ src = malloc(sizeof(struct source));
+ if(src == NULL) {
+ zlog_err("malloc(source): %s", safe_strerror(errno));
+ return NULL;
+ }
+
+ memcpy(src->id, id, 8);
+ memcpy(src->prefix, p, 16);
+ src->plen = plen;
+ src->seqno = seqno;
+ src->metric = INFINITY;
+ src->time = babel_now.tv_sec;
+ src->route_count = 0;
+ src->next = srcs;
+ srcs = src;
+ return src;
+}
+
+struct source *
+retain_source(struct source *src)
+{
+ assert(src->route_count < 0xffff);
+ src->route_count++;
+ return src;
+}
+
+void
+release_source(struct source *src)
+{
+ assert(src->route_count > 0);
+ src->route_count--;
+}
+
+int
+flush_source(struct source *src)
+{
+ if(src->route_count > 0)
+ /* The source is in use by a route. */
+ return 0;
+
+ if(srcs == src) {
+ srcs = src->next;
+ } else {
+ struct source *previous = srcs;
+ while(previous->next != src)
+ previous = previous->next;
+ previous->next = src->next;
+ }
+
+ free(src);
+ return 1;
+}
+
+void
+update_source(struct source *src,
+ unsigned short seqno, unsigned short metric)
+{
+ if(metric >= INFINITY)
+ return;
+
+ /* If a source is expired, pretend that it doesn't exist and update
+ it unconditionally. This makes ensures that old data will
+ eventually be overridden, and prevents us from getting stuck if
+ a router loses its sequence number. */
+ if(src->time < babel_now.tv_sec - SOURCE_GC_TIME ||
+ seqno_compare(src->seqno, seqno) < 0 ||
+ (src->seqno == seqno && src->metric > metric)) {
+ src->seqno = seqno;
+ src->metric = metric;
+ }
+ src->time = babel_now.tv_sec;
+}
+
+void
+expire_sources()
+{
+ struct source *src;
+
+ src = srcs;
+ while(src) {
+ if(src->time > babel_now.tv_sec)
+ /* clock stepped */
+ src->time = babel_now.tv_sec;
+ if(src->time < babel_now.tv_sec - SOURCE_GC_TIME) {
+ struct source *old = src;
+ src = src->next;
+ flush_source(old);
+ continue;
+ }
+ src = src->next;
+ }
+}
+
+void
+check_sources_released(void)
+{
+ struct source *src;
+
+ for(src = srcs; src; src = src->next) {
+ if(src->route_count != 0)
+ fprintf(stderr, "Warning: source %s %s has refcount %d.\n",
+ format_eui64(src->id),
+ format_prefix(src->prefix, src->plen),
+ (int)src->route_count);
+ }
+}
diff --git a/babeld/source.h b/babeld/source.h
new file mode 100644
index 00000000..62a7e1ee
--- /dev/null
+++ b/babeld/source.h
@@ -0,0 +1,67 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#ifndef BABEL_SOURCE_H
+#define BABEL_SOURCE_H
+
+#define SOURCE_GC_TIME 200
+
+struct source {
+ struct source *next;
+ unsigned char id[8];
+ unsigned char prefix[16];
+ unsigned char plen;
+ unsigned short seqno;
+ unsigned short metric;
+ unsigned short route_count;
+ time_t time;
+};
+
+struct source *find_source(const unsigned char *id,
+ const unsigned char *p,
+ unsigned char plen,
+ int create, unsigned short seqno);
+struct source *retain_source(struct source *src);
+void release_source(struct source *src);
+int flush_source(struct source *src);
+void update_source(struct source *src,
+ unsigned short seqno, unsigned short metric);
+void expire_sources(void);
+void check_sources_released(void);
+
+#endif
diff --git a/babeld/util.c b/babeld/util.c
new file mode 100644
index 00000000..011f3824
--- /dev/null
+++ b/babeld/util.c
@@ -0,0 +1,445 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include <stdlib.h>
+#include <stdarg.h>
+#include <string.h>
+#include <sys/time.h>
+#include <time.h>
+#include <stdio.h>
+#include <unistd.h>
+
+#include <sys/types.h>
+#include <sys/socket.h>
+#include <netinet/in.h>
+#include <arpa/inet.h>
+
+#include "babel_main.h"
+#include "babeld.h"
+#include "util.h"
+
+unsigned
+roughly(unsigned value)
+{
+ return value * 3 / 4 + random() % (value / 2);
+}
+
+/* d = s1 - s2 */
+void
+timeval_minus(struct timeval *d,
+ const struct timeval *s1, const struct timeval *s2)
+{
+ if(s1->tv_usec >= s2->tv_usec) {
+ d->tv_usec = s1->tv_usec - s2->tv_usec;
+ d->tv_sec = s1->tv_sec - s2->tv_sec;
+ } else {
+ d->tv_usec = s1->tv_usec + 1000000 - s2->tv_usec;
+ d->tv_sec = s1->tv_sec - s2->tv_sec - 1;
+ }
+}
+
+unsigned
+timeval_minus_msec(const struct timeval *s1, const struct timeval *s2)
+{
+ if(s1->tv_sec < s2->tv_sec)
+ return 0;
+
+ /* Avoid overflow. */
+ if(s1->tv_sec - s2->tv_sec > 2000000)
+ return 2000000000;
+
+ if(s1->tv_sec > s2->tv_sec)
+ return
+ (unsigned)((unsigned)(s1->tv_sec - s2->tv_sec) * 1000 +
+ ((int)s1->tv_usec - s2->tv_usec) / 1000);
+
+ if(s1->tv_usec <= s2->tv_usec)
+ return 0;
+
+ return (unsigned)(s1->tv_usec - s2->tv_usec) / 1000u;
+}
+
+/* d = s + msecs */
+void
+timeval_add_msec(struct timeval *d, const struct timeval *s, const int msecs)
+{
+ int usecs;
+ d->tv_sec = s->tv_sec + msecs / 1000;
+ usecs = s->tv_usec + (msecs % 1000) * 1000;
+ if(usecs < 1000000) {
+ d->tv_usec = usecs;
+ } else {
+ d->tv_usec = usecs - 1000000;
+ d->tv_sec++;
+ }
+}
+
+void
+set_timeout(struct timeval *timeout, int msecs)
+{
+ timeval_add_msec(timeout, &babel_now, roughly(msecs));
+}
+
+/* returns <0 if "s1" < "s2", etc. */
+int
+timeval_compare(const struct timeval *s1, const struct timeval *s2)
+{
+ if(s1->tv_sec < s2->tv_sec)
+ return -1;
+ else if(s1->tv_sec > s2->tv_sec)
+ return 1;
+ else if(s1->tv_usec < s2->tv_usec)
+ return -1;
+ else if(s1->tv_usec > s2->tv_usec)
+ return 1;
+ else
+ return 0;
+}
+
+/* set d at min(d, s) */
+/* {0, 0} represents infinity */
+void
+timeval_min(struct timeval *d, const struct timeval *s)
+{
+ if(s->tv_sec == 0)
+ return;
+
+ if(d->tv_sec == 0 || timeval_compare(d, s) > 0) {
+ *d = *s;
+ }
+}
+
+/* set d to min(d, x) with x in [secs, secs+1] */
+void
+timeval_min_sec(struct timeval *d, time_t secs)
+{
+ if(d->tv_sec == 0 || d->tv_sec > secs) {
+ d->tv_sec = secs;
+ d->tv_usec = random() % 1000000;
+ }
+}
+
+/* parse a float value in second and return the corresponding mili-seconds.
+ For example:
+ parse_msec("12.342345") returns 12342 */
+int
+parse_msec(const char *string)
+{
+ unsigned int in, fl;
+ int i, j;
+
+ in = fl = 0;
+ i = 0;
+ while(string[i] == ' ' || string[i] == '\t')
+ i++;
+ while(string[i] >= '0' && string[i] <= '9') {
+ in = in * 10 + string[i] - '0';
+ i++;
+ }
+ if(string[i] == '.') {
+ i++;
+ j = 0;
+ while(string[i] >= '0' && string[i] <= '9') {
+ fl = fl * 10 + string[i] - '0';
+ i++;
+ j++;
+ }
+
+ while(j > 3) {
+ fl /= 10;
+ j--;
+ }
+ while(j < 3) {
+ fl *= 10;
+ j++;
+ }
+ }
+
+ while(string[i] == ' ' || string[i] == '\t')
+ i++;
+
+ if(string[i] == '\0')
+ return in * 1000 + fl;
+
+ return -1;
+}
+
+int
+in_prefix(const unsigned char *restrict address,
+ const unsigned char *restrict prefix, unsigned char plen)
+{
+ unsigned char m;
+
+ if(plen > 128)
+ plen = 128;
+
+ if(memcmp(address, prefix, plen / 8) != 0)
+ return 0;
+
+ if(plen % 8 == 0)
+ return 1;
+
+ m = 0xFF << (8 - (plen % 8));
+
+ return ((address[plen / 8] & m) == (prefix[plen / 8] & m));
+}
+
+unsigned char *
+mask_prefix(unsigned char *restrict ret,
+ const unsigned char *restrict prefix, unsigned char plen)
+{
+ if(plen >= 128) {
+ memcpy(ret, prefix, 16);
+ return ret;
+ }
+
+ memset(ret, 0, 16);
+ memcpy(ret, prefix, plen / 8);
+ if(plen % 8 != 0)
+ ret[plen / 8] =
+ (prefix[plen / 8] & ((0xFF << (8 - (plen % 8))) & 0xFF));
+ return ret;
+}
+
+static const unsigned char v4prefix[16] =
+ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF, 0, 0, 0, 0 };
+
+static const unsigned char llprefix[16] =
+ {0xFE, 0x80};
+
+const char *
+format_address(const unsigned char *address)
+{
+ static char buf[4][INET6_ADDRSTRLEN];
+ static int i = 0;
+ i = (i + 1) % 4;
+ if(v4mapped(address))
+ inet_ntop(AF_INET, address + 12, buf[i], INET6_ADDRSTRLEN);
+ else
+ inet_ntop(AF_INET6, address, buf[i], INET6_ADDRSTRLEN);
+ return buf[i];
+}
+
+const char *
+format_prefix(const unsigned char *prefix, unsigned char plen)
+{
+ static char buf[4][INET6_ADDRSTRLEN + 4];
+ static int i = 0;
+ int n;
+ i = (i + 1) % 4;
+ if(plen >= 96 && v4mapped(prefix)) {
+ inet_ntop(AF_INET, prefix + 12, buf[i], INET6_ADDRSTRLEN);
+ n = strlen(buf[i]);
+ snprintf(buf[i] + n, INET6_ADDRSTRLEN + 4 - n, "/%d", plen - 96);
+ } else {
+ inet_ntop(AF_INET6, prefix, buf[i], INET6_ADDRSTRLEN);
+ n = strlen(buf[i]);
+ snprintf(buf[i] + n, INET6_ADDRSTRLEN + 4 - n, "/%d", plen);
+ }
+ return buf[i];
+}
+
+const char *
+format_eui64(const unsigned char *eui)
+{
+ static char buf[4][28];
+ static int i = 0;
+ i = (i + 1) % 4;
+ snprintf(buf[i], 28, "%02x:%02x:%02x:%02x:%02x:%02x:%02x:%02x",
+ eui[0], eui[1], eui[2], eui[3],
+ eui[4], eui[5], eui[6], eui[7]);
+ return buf[i];
+}
+
+const char *format_bool(const int b) {
+ return b ? "true" : "false";
+}
+
+int
+parse_address(const char *address, unsigned char *addr_r, int *af_r)
+{
+ struct in_addr ina;
+ struct in6_addr ina6;
+ int rc;
+
+ rc = inet_pton(AF_INET, address, &ina);
+ if(rc > 0) {
+ memcpy(addr_r, v4prefix, 12);
+ memcpy(addr_r + 12, &ina, 4);
+ if(af_r) *af_r = AF_INET;
+ return 0;
+ }
+
+ rc = inet_pton(AF_INET6, address, &ina6);
+ if(rc > 0) {
+ memcpy(addr_r, &ina6, 16);
+ if(af_r) *af_r = AF_INET6;
+ return 0;
+ }
+
+ return -1;
+}
+
+int
+parse_eui64(const char *eui, unsigned char *eui_r)
+{
+ int n;
+ n = sscanf(eui, "%02hhx:%02hhx:%02hhx:%02hhx:%02hhx:%02hhx:%02hhx:%02hhx",
+ &eui_r[0], &eui_r[1], &eui_r[2], &eui_r[3],
+ &eui_r[4], &eui_r[5], &eui_r[6], &eui_r[7]);
+ if(n == 8)
+ return 0;
+
+ n = sscanf(eui, "%02hhx-%02hhx-%02hhx-%02hhx-%02hhx-%02hhx-%02hhx-%02hhx",
+ &eui_r[0], &eui_r[1], &eui_r[2], &eui_r[3],
+ &eui_r[4], &eui_r[5], &eui_r[6], &eui_r[7]);
+ if(n == 8)
+ return 0;
+
+ n = sscanf(eui, "%02hhx:%02hhx:%02hhx:%02hhx:%02hhx:%02hhx",
+ &eui_r[0], &eui_r[1], &eui_r[2],
+ &eui_r[5], &eui_r[6], &eui_r[7]);
+ if(n == 6) {
+ eui_r[3] = 0xFF;
+ eui_r[4] = 0xFE;
+ return 0;
+ }
+ return -1;
+}
+
+int
+wait_for_fd(int direction, int fd, int msecs)
+{
+ fd_set fds;
+ int rc;
+ struct timeval tv;
+
+ tv.tv_sec = msecs / 1000;
+ tv.tv_usec = (msecs % 1000) * 1000;
+
+ FD_ZERO(&fds);
+ FD_SET(fd, &fds);
+ if(direction)
+ rc = select(fd + 1, NULL, &fds, NULL, &tv);
+ else
+ rc = select(fd + 1, &fds, NULL, NULL, &tv);
+
+ return rc;
+}
+
+int
+martian_prefix(const unsigned char *prefix, int plen)
+{
+ return
+ (plen >= 8 && prefix[0] == 0xFF) ||
+ (plen >= 10 && prefix[0] == 0xFE && (prefix[1] & 0xC0) == 0x80) ||
+ (plen >= 128 && memcmp(prefix, zeroes, 15) == 0 &&
+ (prefix[15] == 0 || prefix[15] == 1)) ||
+ (plen >= 96 && v4mapped(prefix) &&
+ ((plen >= 104 && (prefix[12] == 127 || prefix[12] == 0)) ||
+ (plen >= 100 && (prefix[12] & 0xE0) == 0xE0)));
+}
+
+int
+linklocal(const unsigned char *address)
+{
+ return memcmp(address, llprefix, 8) == 0;
+}
+
+int
+v4mapped(const unsigned char *address)
+{
+ return memcmp(address, v4prefix, 12) == 0;
+}
+
+void
+v4tov6(unsigned char *dst, const unsigned char *src)
+{
+ memcpy(dst, v4prefix, 12);
+ memcpy(dst + 12, src, 4);
+}
+
+void
+inaddr_to_uchar(unsigned char *dest, const struct in_addr *src)
+{
+ memcpy(dest, v4prefix, 12);
+ memcpy(dest + 12, src, 4);
+ assert(v4mapped(dest));
+}
+
+void
+uchar_to_inaddr(struct in_addr *dest, const unsigned char *src)
+{
+ assert(v4mapped(src));
+ memcpy(dest, src + 12, 4);
+}
+
+void
+in6addr_to_uchar(unsigned char *dest, const struct in6_addr *src)
+{
+ memcpy(dest, src, 16);
+}
+
+void
+uchar_to_in6addr(struct in6_addr *dest, const unsigned char *src)
+{
+ memcpy(dest, src, 16);
+}
+
+int
+daemonise()
+{
+ int rc;
+
+ fflush(stdout);
+ fflush(stderr);
+
+ rc = fork();
+ if(rc < 0)
+ return -1;
+
+ if(rc > 0)
+ exit(0);
+
+ rc = setsid();
+ if(rc < 0)
+ return -1;
+
+ return 1;
+}
diff --git a/babeld/util.h b/babeld/util.h
new file mode 100644
index 00000000..5d9d2f5d
--- /dev/null
+++ b/babeld/util.h
@@ -0,0 +1,165 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include "babeld.h"
+#include "babel_main.h"
+#include "log.h"
+
+#if defined(i386) || defined(__mc68020__) || defined(__x86_64__)
+#define DO_NTOHS(_d, _s) do{ _d = ntohs(*(const unsigned short*)(_s)); }while(0)
+#define DO_NTOHL(_d, _s) do{ _d = ntohl(*(const unsigned*)(_s)); } while(0)
+#define DO_HTONS(_d, _s) do{ *(unsigned short*)(_d) = htons(_s); } while(0)
+#define DO_HTONL(_d, _s) do{ *(unsigned*)(_d) = htonl(_s); } while(0)
+/* Some versions of gcc seem to be buggy, and ignore the packed attribute.
+ Disable this code until the issue is clarified. */
+/* #elif defined __GNUC__*/
+#elif 0
+struct __us { unsigned short x __attribute__((packed)); };
+#define DO_NTOHS(_d, _s) \
+ do { _d = ntohs(((const struct __us*)(_s))->x); } while(0)
+#define DO_HTONS(_d, _s) \
+ do { ((struct __us*)(_d))->x = htons(_s); } while(0)
+#else
+#define DO_NTOHS(_d, _s) \
+ do { short _dd; \
+ memcpy(&(_dd), (_s), 2); \
+ _d = ntohs(_dd); } while(0)
+#define DO_HTONS(_d, _s) \
+ do { unsigned short _dd; \
+ _dd = htons(_s); \
+ memcpy((_d), &(_dd), 2); } while(0)
+#endif
+
+static inline int
+seqno_compare(unsigned short s1, unsigned short s2)
+{
+ if(s1 == s2)
+ return 0;
+ else
+ return ((s2 - s1) & 0x8000) ? 1 : -1;
+}
+
+static inline short
+seqno_minus(unsigned short s1, unsigned short s2)
+{
+ return (short)((s1 - s2) & 0xFFFF);
+}
+
+static inline unsigned short
+seqno_plus(unsigned short s, int plus)
+{
+ return ((s + plus) & 0xFFFF);
+}
+
+unsigned roughly(unsigned value);
+void timeval_minus(struct timeval *d,
+ const struct timeval *s1, const struct timeval *s2);
+unsigned timeval_minus_msec(const struct timeval *s1, const struct timeval *s2)
+ ATTRIBUTE ((pure));
+void timeval_add_msec(struct timeval *d,
+ const struct timeval *s, const int msecs);
+void set_timeout (struct timeval *timeout, int msecs);
+int timeval_compare(const struct timeval *s1, const struct timeval *s2)
+ ATTRIBUTE ((pure));
+void timeval_min(struct timeval *d, const struct timeval *s);
+void timeval_min_sec(struct timeval *d, time_t secs);
+int parse_msec(const char *string) ATTRIBUTE ((pure));
+int in_prefix(const unsigned char *restrict address,
+ const unsigned char *restrict prefix, unsigned char plen)
+ ATTRIBUTE ((pure));
+unsigned char *mask_prefix(unsigned char *restrict ret,
+ const unsigned char *restrict prefix,
+ unsigned char plen);
+const char *format_address(const unsigned char *address);
+const char *format_prefix(const unsigned char *address, unsigned char prefix);
+const char *format_eui64(const unsigned char *eui);
+const char *format_bool(const int b);
+int parse_address(const char *address, unsigned char *addr_r, int *af_r);
+int parse_eui64(const char *eui, unsigned char *eui_r);
+int wait_for_fd(int direction, int fd, int msecs);
+int martian_prefix(const unsigned char *prefix, int plen) ATTRIBUTE ((pure));
+int linklocal(const unsigned char *address) ATTRIBUTE ((pure));
+int v4mapped(const unsigned char *address) ATTRIBUTE ((pure));
+void v4tov6(unsigned char *dst, const unsigned char *src);
+void inaddr_to_uchar(unsigned char *dest, const struct in_addr *src);
+void uchar_to_inaddr(struct in_addr *dest, const unsigned char *src);
+void in6addr_to_uchar(unsigned char *dest, const struct in6_addr *src);
+void uchar_to_in6addr(struct in6_addr *dest, const unsigned char *src);
+int daemonise(void);
+
+/* If debugging is disabled, we want to avoid calling format_address
+ for every omitted debugging message. So debug is a macro. But
+ vararg macros are not portable. */
+#if defined NO_DEBUG
+
+#if defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L
+#define debugf(...) do {} while(0)
+#elif defined __GNUC__
+#define debugf(_args...) do {} while(0)
+#else
+static inline void debugf(int level, const char *format, ...) { return; }
+#endif
+
+#else /* NO_DEBUG */
+
+/* some levels */
+#define BABEL_DEBUG_COMMON (1 << 0)
+#define BABEL_DEBUG_KERNEL (1 << 1)
+#define BABEL_DEBUG_FILTER (1 << 2)
+#define BABEL_DEBUG_TIMEOUT (1 << 3)
+#define BABEL_DEBUG_IF (1 << 4)
+#define BABEL_DEBUG_ROUTE (1 << 5)
+#define BABEL_DEBUG_ALL (0xFFFF)
+
+#if defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L
+#define debugf(level, ...) \
+do { \
+if(UNLIKELY(debug & level)) zlog_debug(__VA_ARGS__); \
+} while(0)
+#elif defined __GNUC__
+#define debugf(level, _args...) \
+do { \
+if(UNLIKELY(debug & level)) zlog_debug(_args); \
+} while(0)
+#else
+static inline void debugf(int level, const char *format, ...) { return; }
+#endif
+
+#endif /* NO_DEBUG */
+
diff --git a/babeld/xroute.c b/babeld/xroute.c
new file mode 100644
index 00000000..80651671
--- /dev/null
+++ b/babeld/xroute.c
@@ -0,0 +1,237 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include <zebra.h>
+#include "if.h"
+#include "log.h"
+
+#include "babeld.h"
+#include "kernel.h"
+#include "neighbour.h"
+#include "message.h"
+#include "route.h"
+#include "xroute.h"
+#include "util.h"
+#include "babel_interface.h"
+
+static int xroute_add_new_route(unsigned char prefix[16], unsigned char plen,
+ unsigned short metric, unsigned int ifindex,
+ int proto, int send_updates);
+
+static struct xroute *xroutes;
+static int numxroutes = 0, maxxroutes = 0;
+
+/* Add redistributed route to Babel table. */
+int
+babel_ipv4_route_add (struct zapi_ipv4 *api, struct prefix_ipv4 *prefix,
+ unsigned int ifindex, struct in_addr *nexthop)
+{
+ unsigned char uchar_prefix[16];
+
+ inaddr_to_uchar(uchar_prefix, &prefix->prefix);
+ debugf(BABEL_DEBUG_ROUTE, "Adding new ipv4 route comming from Zebra.");
+ xroute_add_new_route(uchar_prefix, prefix->prefixlen + 96,
+ api->metric, ifindex, 0, 1);
+ return 0;
+}
+
+/* Remove redistributed route from Babel table. */
+int
+babel_ipv4_route_delete (struct zapi_ipv4 *api, struct prefix_ipv4 *prefix,
+ unsigned int ifindex)
+{
+ unsigned char uchar_prefix[16];
+ struct xroute *xroute = NULL;
+
+ inaddr_to_uchar(uchar_prefix, &prefix->prefix);
+ xroute = find_xroute(uchar_prefix, prefix->prefixlen + 96);
+ if (xroute != NULL) {
+ debugf(BABEL_DEBUG_ROUTE, "Removing ipv4 route (from zebra).");
+ flush_xroute(xroute);
+ }
+ return 0;
+}
+
+/* Add redistributed route to Babel table. */
+int
+babel_ipv6_route_add (struct zapi_ipv6 *api, struct prefix_ipv6 *prefix,
+ unsigned int ifindex, struct in6_addr *nexthop)
+{
+ unsigned char uchar_prefix[16];
+
+ in6addr_to_uchar(uchar_prefix, &prefix->prefix);
+ debugf(BABEL_DEBUG_ROUTE, "Adding new route comming from Zebra.");
+ xroute_add_new_route(uchar_prefix, prefix->prefixlen, api->metric, ifindex,
+ 0, 1);
+ return 0;
+}
+
+/* Remove redistributed route from Babel table. */
+int
+babel_ipv6_route_delete (struct zapi_ipv6 *api, struct prefix_ipv6 *prefix,
+ unsigned int ifindex)
+{
+ unsigned char uchar_prefix[16];
+ struct xroute *xroute = NULL;
+
+ in6addr_to_uchar(uchar_prefix, &prefix->prefix);
+ xroute = find_xroute(uchar_prefix, prefix->prefixlen);
+ if (xroute != NULL) {
+ debugf(BABEL_DEBUG_ROUTE, "Removing route (from zebra).");
+ flush_xroute(xroute);
+ }
+ return 0;
+}
+
+struct xroute *
+find_xroute(const unsigned char *prefix, unsigned char plen)
+{
+ int i;
+ for(i = 0; i < numxroutes; i++) {
+ if(xroutes[i].plen == plen &&
+ memcmp(xroutes[i].prefix, prefix, 16) == 0)
+ return &xroutes[i];
+ }
+ return NULL;
+}
+
+void
+flush_xroute(struct xroute *xroute)
+{
+ int i;
+
+ i = xroute - xroutes;
+ assert(i >= 0 && i < numxroutes);
+
+ if(i != numxroutes - 1)
+ memcpy(xroutes + i, xroutes + numxroutes - 1, sizeof(struct xroute));
+ numxroutes--;
+ VALGRIND_MAKE_MEM_UNDEFINED(xroutes + numxroutes, sizeof(struct xroute));
+
+ if(numxroutes == 0) {
+ free(xroutes);
+ xroutes = NULL;
+ maxxroutes = 0;
+ } else if(maxxroutes > 8 && numxroutes < maxxroutes / 4) {
+ struct xroute *new_xroutes;
+ int n = maxxroutes / 2;
+ new_xroutes = realloc(xroutes, n * sizeof(struct xroute));
+ if(new_xroutes == NULL)
+ return;
+ xroutes = new_xroutes;
+ maxxroutes = n;
+ }
+}
+
+static int
+add_xroute(unsigned char prefix[16], unsigned char plen,
+ unsigned short metric, unsigned int ifindex, int proto)
+{
+ struct xroute *xroute = find_xroute(prefix, plen);
+ if(xroute) {
+ if(xroute->metric <= metric)
+ return 0;
+ xroute->metric = metric;
+ return 1;
+ }
+
+ if(numxroutes >= maxxroutes) {
+ struct xroute *new_xroutes;
+ int n = maxxroutes < 1 ? 8 : 2 * maxxroutes;
+ new_xroutes = xroutes == NULL ?
+ malloc(n * sizeof(struct xroute)) :
+ realloc(xroutes, n * sizeof(struct xroute));
+ if(new_xroutes == NULL)
+ return -1;
+ maxxroutes = n;
+ xroutes = new_xroutes;
+ }
+
+ memcpy(xroutes[numxroutes].prefix, prefix, 16);
+ xroutes[numxroutes].plen = plen;
+ xroutes[numxroutes].metric = metric;
+ xroutes[numxroutes].ifindex = ifindex;
+ xroutes[numxroutes].proto = proto;
+ numxroutes++;
+ return 1;
+}
+
+/* Returns an overestimate of the number of xroutes. */
+int
+xroutes_estimate()
+{
+ return numxroutes;
+}
+
+void
+for_all_xroutes(void (*f)(struct xroute*, void*), void *closure)
+{
+ int i;
+
+ for(i = 0; i < numxroutes; i++)
+ (*f)(&xroutes[i], closure);
+}
+
+/* add an xroute, verifying some conditions; return 0 if there is no changes */
+static int
+xroute_add_new_route(unsigned char prefix[16], unsigned char plen,
+ unsigned short metric, unsigned int ifindex,
+ int proto, int send_updates)
+{
+ int rc;
+ if(martian_prefix(prefix, plen))
+ return 0;
+ metric = redistribute_filter(prefix, plen, ifindex, proto);
+ if(metric < INFINITY) {
+ rc = add_xroute(prefix, plen, metric, ifindex, proto);
+ if(rc > 0) {
+ struct babel_route *route;
+ route = find_installed_route(prefix, plen);
+ if(route) {
+ if(allow_duplicates < 0 ||
+ metric < allow_duplicates)
+ uninstall_route(route);
+ }
+ if(send_updates)
+ send_update(NULL, 0, prefix, plen);
+ return 1;
+ }
+ }
+ return 0;
+}
diff --git a/babeld/xroute.h b/babeld/xroute.h
new file mode 100644
index 00000000..4d4ab99d
--- /dev/null
+++ b/babeld/xroute.h
@@ -0,0 +1,59 @@
+/*
+ * This file is free software: you may copy, redistribute and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation, either version 2 of the License, or (at your
+ * option) any later version.
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * This file incorporates work covered by the following copyright and
+ * permission notice:
+ *
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+struct xroute {
+ unsigned char prefix[16];
+ unsigned char plen;
+ unsigned short metric;
+ unsigned int ifindex;
+ int proto;
+};
+
+struct xroute *find_xroute(const unsigned char *prefix, unsigned char plen);
+void flush_xroute(struct xroute *xroute);
+int babel_ipv4_route_add (struct zapi_ipv4 *api, struct prefix_ipv4 *prefix,
+ unsigned int ifindex, struct in_addr *nexthop);
+int babel_ipv4_route_delete (struct zapi_ipv4 *api, struct prefix_ipv4 *prefix,
+ unsigned int ifindex);
+int babel_ipv6_route_add (struct zapi_ipv6 *api, struct prefix_ipv6 *prefix,
+ unsigned int ifindex, struct in6_addr *nexthop);
+int babel_ipv6_route_delete (struct zapi_ipv6 *api, struct prefix_ipv6 *prefix,
+ unsigned int ifindex);
+int xroutes_estimate(void);
+void for_all_xroutes(void (*f)(struct xroute*, void*), void *closure);