diff options
Diffstat (limited to 'babeld')
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); |