diff options
50 files changed, 8535 insertions, 34 deletions
diff --git a/Makefile.am b/Makefile.am index ff4c3541..19a90227 100644 --- a/Makefile.am +++ b/Makefile.am @@ -1,10 +1,10 @@ ## Process this file with automake to produce Makefile.in. -SUBDIRS = lib @ZEBRA@ @BGPD@ @RIPD@ @RIPNGD@ @OSPFD@ @OSPF6D@ \ +SUBDIRS = lib @ZEBRA@ @BGPD@ @RIPD@ @RIPNGD@ @OSPFD@ @OSPF6D@ @BABELD@ \ @ISISD@ @WATCHQUAGGA@ @VTYSH@ @OSPFCLIENT@ @DOC@ m4 @pkgsrcdir@ \ redhat @SOLARIS@ -DIST_SUBDIRS = lib zebra bgpd ripd ripngd ospfd ospf6d \ +DIST_SUBDIRS = lib zebra bgpd ripd ripngd ospfd ospf6d babeld \ isisd watchquagga vtysh ospfclient doc m4 pkgsrc redhat tests \ solaris 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..5c93d13a --- /dev/null +++ b/babeld/babel_filter.c @@ -0,0 +1,188 @@ +/* + * 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_in (struct prefix *p, babel_interface_nfo *babel_ifp) +{ + struct distribute *dist; + struct access_list *alist; + struct prefix_list *plist; + + /* Input distribute-list filtering. */ + if (babel_ifp != NULL && babel_ifp->list[BABEL_FILTER_IN]) { + if (access_list_apply (babel_ifp->list[BABEL_FILTER_IN], 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 -1; + } + } + if (babel_ifp != NULL && babel_ifp->prefix[BABEL_FILTER_IN]) { + if (prefix_list_apply (babel_ifp->prefix[BABEL_FILTER_IN], 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 -1; + } + } + + /* All interface filter check. */ + dist = distribute_lookup (NULL); + if (dist) { + if (dist->list[DISTRIBUTE_IN]) { + alist = access_list_lookup (AFI_IP6, dist->list[DISTRIBUTE_IN]); + + 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 -1; + } + } + } + if (dist->prefix[DISTRIBUTE_IN]) { + plist = prefix_list_lookup (AFI_IP6, dist->prefix[DISTRIBUTE_IN]); + 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 -1; + } + } + } + } + return 0; +} + +int +babel_filter_out (struct prefix *p, babel_interface_nfo *babel_ifp) +{ + struct distribute *dist; + struct access_list *alist; + struct prefix_list *plist; + + if (babel_ifp != NULL && babel_ifp->list[BABEL_FILTER_OUT]) { + if (access_list_apply (babel_ifp->list[BABEL_FILTER_OUT], p) + == FILTER_DENY) { + debugf(BABEL_DEBUG_FILTER, "%s/%d filtered by distribute out", + p->family == AF_INET ? + inet_ntoa(p->u.prefix4) : + inet6_ntoa (p->u.prefix6), + p->prefixlen); + return -1; + } + } + if (babel_ifp != NULL && babel_ifp->prefix[BABEL_FILTER_OUT]) { + if (prefix_list_apply (babel_ifp->prefix[BABEL_FILTER_OUT], p) + == PREFIX_DENY) { + debugf(BABEL_DEBUG_FILTER, "%s/%d filtered by distribute out", + p->family == AF_INET ? + inet_ntoa(p->u.prefix4) : + inet6_ntoa (p->u.prefix6), + p->prefixlen); + return -1; + } + } + + /* All interface filter check. */ + dist = distribute_lookup (NULL); + if (dist) { + if (dist->list[DISTRIBUTE_OUT]) { + alist = access_list_lookup (AFI_IP6, dist->list[DISTRIBUTE_OUT]); + if (alist) { + if (access_list_apply (alist, p) == FILTER_DENY) { + debugf(BABEL_DEBUG_FILTER, "%s/%d filtered by distribute out", + p->family == AF_INET ? + inet_ntoa(p->u.prefix4) : + inet6_ntoa (p->u.prefix6), + p->prefixlen); + return -1; + } + } + } + if (dist->prefix[DISTRIBUTE_OUT]) { + plist = prefix_list_lookup (AFI_IP6, dist->prefix[DISTRIBUTE_OUT]); + if (plist) { + if (prefix_list_apply (plist, p) == PREFIX_DENY) { + debugf(BABEL_DEBUG_FILTER, "%s/%d filtered by distribute out", + p->family == AF_INET ? + inet_ntoa(p->u.prefix4) : + inet6_ntoa (p->u.prefix6), + p->prefixlen); + return -1; + } + } + } + } + return 0; +} + +int +babel_filter_redistribute (struct prefix *p, + babel_interface_nfo *babel_ifp) +{ + debugf(BABEL_DEBUG_FILTER, "%s/%d WARNING: no redistribute filter implemented !!!!", + p->family == AF_INET ? + inet_ntoa(p->u.prefix4) : + inet6_ntoa (p->u.prefix6), + p->prefixlen); + return 0; /* TODO: it redistributes always */ +} diff --git a/babeld/babel_filter.h b/babeld/babel_filter.h new file mode 100644 index 00000000..52b72f60 --- /dev/null +++ b/babeld/babel_filter.h @@ -0,0 +1,54 @@ +/* + * 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" + +/* filter route coming from other worlds */ +int babel_filter_in (struct prefix *, babel_interface_nfo *); +/* filter route sending to other worlds */ +int babel_filter_out (struct prefix *, babel_interface_nfo *); +/* filter route coming from our friend zebra */ +int babel_filter_redistribute + (struct prefix *, babel_interface_nfo *); + +#endif /* BABELD_BABEL_FILTER_H */ diff --git a/babeld/babel_interface.c b/babeld/babel_interface.c new file mode 100644 index 00000000..0130f26b --- /dev/null +++ b/babeld/babel_interface.c @@ -0,0 +1,778 @@ +/* + * 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 <string.h> +#include <stdio.h> +#include <stdlib.h> +#include <assert.h> +#include <sys/time.h> +#include <sys/ioctl.h> +#include <sys/socket.h> +#include <netinet/in.h> +#include <net/if.h> +#include <arpa/inet.h> + +#include <zebra.h> +#include "memory.h" +#include "log.h" +#include "command.h" +#include "prefix.h" +#include "vector.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" + + +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 (); +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); + + 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); + + 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) +{ + debugf(BABEL_DEBUG_IF, "receive a 'interface delete'"); + 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) + babel_get_if_nfo(ifp)->flags |= BABEL_IF_IS_ENABLE; + + 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) + babel_get_if_nfo(ifp)->flags &= ~BABEL_IF_IS_ENABLE; + + return 1; +} + + +/* [Babel Command] Babel enable on specified interface or matched network. */ +DEFUN (babel_network, + babel_network_cmd, + "network IF_OR_ADDR", + "Babel enable 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 + "Babel enable 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; +} + +/* [Interface Command] Tell the interface is wire. */ +DEFUN (babel_set_wired, + babel_set_wired_cmd, + "wired", + "Set this interface as wired (default: wireless).\n" + "No attributes") +{ + 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_WIRED; + return CMD_SUCCESS; +} + +/* [Interface Command] Tell the interface is wireless (default). */ +DEFUN (babel_set_wireless, + babel_set_wireless_cmd, + "wireless", + NO_STR + "Set this interface as wireless (is default).\n" + "No attributes") +{ + 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_WIRED; + return CMD_SUCCESS; +} + +/* [Interface Command] Enable split horizon. */ +DEFUN (babel_split_horizon, + babel_split_horizon_cmd, + "babel split-horizon", + IPV6_STR + "Routing Information Protocol\n" + "Perform split horizon\n") +{ + 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 + IPV6_STR + "Routing Information Protocol\n" + "Perform split horizon\n") +{ + 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, + "hello interval <5-1000000>", + "Set interface's hello interval (default: 4000).\n" + "Value in miliseconds\n") +{ + struct interface *ifp; + babel_interface_nfo *babel_ifp; + + int interval = atoi(argv[1]); + + 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_passive_interface, + babel_passive_interface_cmd, + "passive-interface", + "The daemon will only announce redistributed routes\n" + "Interface name\n") +{ + if (allow_duplicates) { + return CMD_WARNING; + } + parasitic = -1; + return CMD_SUCCESS; +} + +/* [Interface Command]. */ +DEFUN (no_babel_passive_interface, + no_babel_passive_interface_cmd, + "no passive-interface", + NO_STR + "The daemon will announce all (filtred) routes\n" + "Interface name\n") +{ + parasitic = 0; + return CMD_SUCCESS; +} + + +int +interface_idle(babel_interface_nfo *babel_ifp) +{ + return (idle_hello_interval > 0 && + babel_ifp->activity_time < babel_now.tv_sec - idle_time); +} + +/* 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; + + 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) { + fprintf(stderr, "Couldn't reallocate sendbuf.\n"); + free(tmp); + babel_ifp->bufsize = 0; + return -1; + } + tmp = NULL; + + resize_receive_buffer(mtu); + + if(!(babel_ifp->flags & BABEL_IF_WIRED)) { /* if (wired) */ + babel_ifp->cost = 96; + babel_ifp->flags &= ~BABEL_IF_LQ; + } else { + babel_ifp->cost = 256; + babel_ifp->flags |= BABEL_IF_LQ; + } + + babel_ifp->activity_time = babel_now.tv_sec; + /* Since the interface was marked as active above, the + idle_hello_interval cannot be the one being used here. */ + babel_ifp->update_interval = babel_ifp->hello_interval * 4; + + 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 network %s (%s, cost=%d%s).", + ifp->name, + (babel_ifp->flags & BABEL_IF_WIRED) ? "wired" : "wireless", + babel_ifp->cost, + babel_ifp->ipv4 ? ", IPv4" : ""); + + if(rc > 0) + send_update(ifp, 0, NULL, 0); + + /* Check and set if interface is enable. */ + if (babel_enable_if_lookup(ifp->name) >= 0) { + babel_ifp->flags |= BABEL_IF_IS_ENABLE; + } else { + babel_ifp->flags &= ~BABEL_IF_IS_ENABLE; + } + + 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); + + 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; +} + + +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_passive_interface_cmd); + install_element(INTERFACE_NODE, &no_babel_passive_interface_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; +} + +/* Configuration write function for babeld. */ +static int +interface_config_write (struct vty *vty) +{ + struct listnode *node; + struct interface *ifp; + babel_interface_nfo *babel_ifp; + int write = 0; + + for (ALL_LIST_ELEMENTS_RO (iflist, node, ifp)) { + babel_ifp = babel_get_if_nfo(ifp); + + /* Do not display the interface if there is no configuration about it */ + if (ifp->desc == NULL) + continue; + + vty_out (vty, "interface %s%s", ifp->name, + VTY_NEWLINE); + if (ifp->desc) + vty_out (vty, " description %s%s", ifp->desc, + VTY_NEWLINE); + + /* TODO: to be completed... */ + + vty_out (vty, "!%s", VTY_NEWLINE); + + write++; + } + return write; +} + +/* functions to allocate or free memory for a babel_interface_nfo, filling + needed fields */ +static babel_interface_nfo * +babel_interface_allocate () +{ + 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->activity_time = babel_now.tv_sec; + babel_ifp->bucket_time = babel_now.tv_sec; + babel_ifp->bucket = BUCKET_TOKENS_MAX; + babel_ifp->hello_seqno = (random() & 0xFFFF); + babel_ifp->hello_interval = BABELD_DEFAULT_HELLO_INTERVAL; + + 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..7a6efb93 --- /dev/null +++ b/babeld/babel_interface.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 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" + +/* babeld interface informations */ +struct babel_interface { + unsigned short flags; /* see below */ + unsigned short cost; + 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 activity_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_WIRED (1 << 1) +#define BABEL_IF_SPLIT_HORIZON (1 << 2) +#define BABEL_IF_LQ (1 << 3) +#define BABEL_IF_IS_ENABLE (1 << 4) + +static inline int +if_up(struct interface *ifp) +{ + return (if_is_up(ifp) && + ifp->connected != NULL && + (babel_get_if_nfo(ifp)->flags & BABEL_IF_IS_ENABLE)); +} + +/* 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); + +/* others functions */ +int interface_idle(babel_interface_nfo *); +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); + + +#endif diff --git a/babeld/babel_main.c b/babeld/babel_main.c new file mode 100644 index 00000000..6065b7bc --- /dev/null +++ b/babeld/babel_main.c @@ -0,0 +1,522 @@ +/* + * 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 void babel_usage (char *progname); +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_load_state_file(void); +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 = BABEL_DEBUG_COMMON; + +time_t reboot_time; +int idle_time = 320; +int link_detect = 0; +int wireless_hello_interval = -1; +int wired_hello_interval = -1; +int idle_hello_interval = -1; +char *pidfile = "/var/run/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 char *state_file = "/var/lib/babeld/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'}, + { "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; +} + +/* 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; + char *pidfile = PATH_BABELD_PID; + + /* 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: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 '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 == 0 && optarg[0] != '0'/*atoi error*/)) + 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); + break; + default: + babel_usage(progname); + 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 (); + + /* babeld inits (default options) */ + /* set default interval's values */ + if(wireless_hello_interval <= 0) + wireless_hello_interval = 4000; + wireless_hello_interval = MAX(wireless_hello_interval, 5); + + if(wired_hello_interval <= 0) + wired_hello_interval = 4000; + wired_hello_interval = MAX(wired_hello_interval, 5); + + /* an assertion */ + if(parasitic && allow_duplicates >= 0) { + /* Too difficult to get right. */ + zlog_err("Sorry, -P and -A are incompatible."); + exit(1); + } + + 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); + + myseqno = (random() & 0xFFFF); + babel_load_state_file(); + + /* 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_usage(char *progname) +{ + fprintf(stderr, + "Syntax: %s " + "[-m multicast_address] [-p port] [-S state-file]\n" + " " + "[-h hello] [-H wired_hello] [-i idle_hello]\n" + " " + "[-k metric] [-A metric] [-s] [-P] [-l] [-w] [-d level] [-g port]\n" + " " + "[-t table] [-T table] [-c file] [-C statement]\n" + " " + "[-D] [-L logfile] [-I pidfile]\n" + " " + "[id] interface...\n", + progname); + exit(1); +} + +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" + */ +static void +babel_load_state_file(void) +{ + reboot_time = babel_now.tv_sec; + 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."); + /* Convert realtime into monotonic time. */ + if(t >= 1176800000L && t <= realnow.tv_sec) + reboot_time = babel_now.tv_sec - (realnow.tv_sec - t); + } + } 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."); + babel_uninstall_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); + } +} diff --git a/babeld/babel_main.h b/babeld/babel_main.h new file mode 100644 index 00000000..2bacfabf --- /dev/null +++ b/babeld/babel_main.h @@ -0,0 +1,54 @@ +/* + * 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. +*/ + +extern struct timeval babel_now; /* current time */ +extern struct thread_master *master; /* quagga's threads handler */ +extern int debug; +extern int wireless_hello_interval, wired_hello_interval, idle_hello_interval; +extern int idle_time; +extern int link_detect; + +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; diff --git a/babeld/babel_zebra.c b/babeld/babel_zebra.c new file mode 100644 index 00000000..6d78ecc6 --- /dev/null +++ b/babeld/babel_zebra.c @@ -0,0 +1,299 @@ +/* + * 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" + +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); +/* Redistribution types */ +static struct { + int type; + int str_min_len; + const char *str; +} redist_type[] = { + {ZEBRA_ROUTE_KERNEL, 1, "kernel"}, + {ZEBRA_ROUTE_CONNECT, 1, "connected"}, + {ZEBRA_ROUTE_STATIC, 1, "static"}, + {ZEBRA_ROUTE_OSPF6, 1, "ospf6"}, + {ZEBRA_ROUTE_BGP, 1, "bgp"}, + {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; +} + +static int +babel_redistribute_unset (int type) +{ + if (! zclient->redist[type]) + return CMD_SUCCESS; + + zclient->redist[type] = 0; + + if (zclient->sock > 0) + zebra_redistribute_send (ZEBRA_REDISTRIBUTE_DELETE, zclient, type); + + /* perhaps should we remove xroutes having the same type... */ + + return CMD_SUCCESS; +} + + +/* [Babel Command] */ +DEFUN (babel_redistribute_type, + babel_redistribute_type_cmd, + "redistribute (kernel|connected|static|ospf6|bgp)", + "Redistribute information from another routing protocol\n" + "Kernel routes\n" + "Connected\n" + "Static routes\n" + "Open Shortest Path First (OSPFv3)\n" + "Border Gateway Protocol (BGP)\n") +{ + int i; + + for(i = 0; redist_type[i].str != NULL; i++) { + if (strncmp (redist_type[i].str, argv[0], + redist_type[i].str_min_len) == 0) { + zclient_redistribute (ZEBRA_REDISTRIBUTE_ADD, zclient, + redist_type[i].type); + return CMD_SUCCESS; + } + } + + vty_out(vty, "Invalid type %s%s", argv[0], VTY_NEWLINE); + + return CMD_WARNING; +} + +/* [Babel Command] */ +DEFUN (no_babel_redistribute_type, + no_babel_redistribute_type_cmd, + "no redistribute (kernel|connected|static|ospf6|bgp)", + NO_STR + "Redistribute information from another routing protocol\n" + "Kernel routes\n" + "Connected\n" + "Static routes\n" + "Open Shortest Path First (OSPFv3)\n" + "Border Gateway Protocol (BGP)\n") +{ + int i; + + for (i = 0; redist_type[i].str; i++) { + if (strncmp(redist_type[i].str, argv[0], + redist_type[i].str_min_len) == 0) { + return babel_redistribute_unset (redist_type[i].type); + } + } + + vty_out(vty, "Invalid type %s%s", argv[0], VTY_NEWLINE); + + return CMD_WARNING; +} + + +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); +} + +static int +zebra_config_write (struct vty *vty) +{ + fprintf(stderr, "\tzebra_config_write\n"); + 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..1b623f01 --- /dev/null +++ b/babeld/babel_zebra.h @@ -0,0 +1,43 @@ +/* + * 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. +*/ + + +extern struct zclient *zclient; + +void babelz_zebra_init(void); +void babel_zebra_close_connexion(void); diff --git a/babeld/babeld.c b/babeld/babeld.c new file mode 100644 index 00000000..18b4e34f --- /dev/null +++ b/babeld/babeld.c @@ -0,0 +1,766 @@ +/* + * 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" + + +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) +{ + return 0; +} + + +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) +{ + babel_get_myid(); + 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() +{ + babel_uninstall_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; + } +} + +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") +{ + 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_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") +{ + if(babel_routing_process) + babel_clean_routing_process(); + return CMD_SUCCESS; +} + +/* [Babel Command] */ +DEFUN (babel_set_protocol_group, + babel_set_protocol_group_cmd, + "protocol group ADDR", + "Set the protocol group, default is ff02::1:6.\n" + "IPv6 address") +{ + int ret; + struct prefix p; + + ret = str2prefix (argv[0], &p); + + /* Given string is: */ + if (ret) { /* an IPv4 or v6 network */ + if (p.family != AF_INET6) { + return CMD_WARNING; + } + in6addr_to_uchar(protocol_group, &p.u.prefix6); + } else { /* an interface name */ + return CMD_WARNING; + } + + if (ret < 0) { + vty_out (vty, "%s must be an ipv6 address%s", argv[0], + VTY_NEWLINE); + return CMD_WARNING; + } + + return CMD_SUCCESS; +} + +/* [Babel Command] */ +DEFUN (babel_set_protocol_port, + babel_set_protocol_port_cmd, + "protocol port <1-65535>", + "Set the protocol port (default is defined in RFC).\n" + "IPv6 address") +{ + int port = atoi(argv[0]); + protocol_port = port; + + 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); + + 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); +} + +int /* DEPRECATED: for compatibility with old babeld (configuration.{c,h})*/ +input_filter(const unsigned char *id, + const unsigned char *prefix, unsigned short plen, + const unsigned char *neigh, unsigned int ifindex) +{ + struct interface *ifp = NULL; + struct prefix p; + p.family = v4mapped(prefix) ? AF_INET : AF_INET6; + p.prefixlen = plen; + if (p.family == AF_INET) { + uchar_to_inaddr(&p.u.prefix4, prefix); + } else { + uchar_to_in6addr(&p.u.prefix6, prefix); + } + + ifp = if_lookup_by_index(ifindex); + if (ifp != NULL) { + return babel_filter_in(&p, babel_get_if_nfo(ifp)); + } + + return babel_filter_in(&p, NULL); +} + +int /* DEPRECATED: for compatibility with old babeld */ +output_filter(const unsigned char *id, const unsigned char *prefix, + unsigned short plen, unsigned int ifindex) +{ + struct interface *ifp = NULL; + struct prefix p; + p.family = v4mapped(prefix) ? AF_INET : AF_INET6; + p.prefixlen = plen; + if (p.family == AF_INET) { + uchar_to_inaddr(&p.u.prefix4, prefix); + } else { + uchar_to_in6addr(&p.u.prefix6, prefix); + } + + ifp = if_lookup_by_index(ifindex); + if (ifp != NULL) { + return babel_filter_out(&p, babel_get_if_nfo(ifp)); + } + + return babel_filter_out(&p, NULL); +} + +int /* DEPRECATED: for compatibility with old babeld */ +redistribute_filter(const unsigned char *prefix, unsigned short plen, + unsigned int ifindex, int proto) +{ + struct interface *ifp = NULL; + struct prefix p; + p.family = v4mapped(prefix) ? AF_INET : AF_INET6; + p.prefixlen = plen; + if (p.family == AF_INET) { + uchar_to_inaddr(&p.u.prefix4, prefix); + } else { + uchar_to_in6addr(&p.u.prefix6, prefix); + } + + ifp = if_lookup_by_index(ifindex); + if (ifp != NULL) { + return babel_filter_redistribute(&p,babel_get_if_nfo(ifp)); + } + + return babel_filter_redistribute(&p, NULL); +} diff --git a/babeld/babeld.conf.sample b/babeld/babeld.conf.sample new file mode 100644 index 00000000..bb2c1dbb --- /dev/null +++ b/babeld/babeld.conf.sample @@ -0,0 +1,31 @@ +# placeholder +# This is an example. See documentation for more results. +# +# let 'eth0' be an interface. +# +# Remark: '#' and '!' are comments. +# NB, just for this example: +# each line at the same indentation is only dependant of the less level +# line. BUT the quagga parser is insensitive. + + +# setup the routing for Babel. +router babel #activate the Babel routing babeld.c + network eth0 #eth0 is match interface.c + redistribute kernel #(kernel|connected|static|ospf6|bgp) babel_zebra.c + no redistribute static #... + + +# setup each interface, one by one... +Interface eth0 #Set eth0 options interface.c +! wired #with wire interface.c + wireless #without wire (défaut) interface.c +! babel split-horizon #with Split-horizon interface.c + no babel split-horizon #without (defaut) interface.c + hello interval 4096 #default = 4096 (in miliseconds) interface.c + + +# setup the log destination. +# log stdout +# log stdout debugging +log file /var/log/quagga/babeld.log
\ No newline at end of file diff --git a/babeld/babeld.h b/babeld/babeld.h new file mode 100644 index 00000000..87b4de7b --- /dev/null +++ b/babeld/babeld.h @@ -0,0 +1,136 @@ +/* + * 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> + +#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" +#define BABELD_DEFAULT_HELLO_INTERVAL 4000 /* miliseconds */ + + +/* 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..4b5bd7b2 --- /dev/null +++ b/babeld/kernel.c @@ -0,0 +1,113 @@ +/* + * 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) +{ + int rc; + static time_t offset = 0, previous = 0; + +#if defined(_POSIX_TIMERS) && _POSIX_TIMERS > 0 && defined(CLOCK_MONOTONIC) + static int have_posix_clocks = -1; + + if(UNLIKELY(have_posix_clocks < 0)) { + struct timespec ts; + rc = clock_gettime(CLOCK_MONOTONIC, &ts); + if(rc < 0) { + have_posix_clocks = 0; + } else { + have_posix_clocks = 1; + } + } + + if(have_posix_clocks) { + struct timespec ts; + int rc; + rc = clock_gettime(CLOCK_MONOTONIC, &ts); + if(rc < 0) + return rc; + tv->tv_sec = ts.tv_sec; + tv->tv_usec = ts.tv_nsec / 1000; + return rc; + } +#endif + + rc = gettimeofday(tv, NULL); + if(rc < 0) + return rc; + tv->tv_sec += offset; + if(UNLIKELY(previous > tv->tv_sec)) { + offset += previous - tv->tv_sec; + tv->tv_sec = previous; + } + previous = tv->tv_sec; + return rc; +} + +/* 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..d9d650dc --- /dev/null +++ b/babeld/kernel.h @@ -0,0 +1,82 @@ +/* + * 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 + +#define CHANGE_LINK (1 << 0) +#define CHANGE_ROUTE (1 << 1) +#define CHANGE_ADDR (1 << 2) + +extern int export_table, import_table; + +int kernel_setup(int setup); +int kernel_setup_socket(int setup); +int kernel_setup_interface(int setup, struct interface *interface); +int kernel_interface_operational(struct interface *interface); +int kernel_interface_ipv4(struct interface *interface, + unsigned char *addr_r); +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 kernel_routes(struct kernel_route *routes, int maxroutes); +int kernel_callback(int (*fn)(int, void*), void *closure); +int kernel_addresses(struct interface *interface, int ll, + struct kernel_route *routes, int maxroutes); +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..0fecb527 --- /dev/null +++ b/babeld/kernel_zebra.c @@ -0,0 +1,461 @@ +/* + * 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_add_v4(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); +static int +kernel_route_add_v6(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); +static int +kernel_route_delete_v4(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); +static int +kernel_route_delete_v6(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 export_table = -1, import_table = -1; /* just for compatibility */ + +int +kernel_setup(int setup) +{ + return 0; +} + +/* get a connection with zebra client, at all costs */ +int +kernel_setup_socket(int setup) +{ + return -1; +} + +int +kernel_setup_interface(int setup, struct interface *interface) +{ + return 1; +} + +int +kernel_interface_operational(struct interface *interface) +{ + return if_is_operative(interface); +} + +int +kernel_interface_ipv4(struct interface *interface, unsigned char *addr_r) +{ + assert(0); /* function not used */ + return -1; +} + +int +kernel_interface_mtu(struct interface *interface) +{ + return MIN(interface->mtu, interface->mtu6); +} + +int +kernel_interface_wireless(struct interface *interface) +{ + return 0; +} + +extern int +zapi_ipv6_route (u_char cmd, struct zclient *zclient, + struct prefix_ipv6 *p, struct zapi_ipv6 *api); + +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 added; + 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_add_v4(pref, plen, gate, ifindex, metric, + newgate, newifindex, newmetric): + kernel_route_add_v6(pref, plen, gate, ifindex, metric, + newgate, newifindex, newmetric); + break; + case ROUTE_FLUSH: + return ipv4 ? + kernel_route_delete_v4(pref, plen, gate, ifindex, metric, + newgate, newifindex, newmetric): + kernel_route_delete_v6(pref, plen, gate, ifindex, metric, + newgate, newifindex, newmetric); + break; + case ROUTE_MODIFY: + if(newmetric == metric && memcmp(newgate, gate, 16) == 0 && + newifindex == ifindex) + return 0; + /* It is better to add the new route before removing the old + one, to avoid losing packets. However, if the old and new + priorities are equal, this only works if the kernel supports + ECMP. So we first try the "right" order, and fall back on + the "wrong" order if it fails with EEXIST. */ + rc = ipv4 ? + kernel_route_add_v4(pref, plen, + newgate, newifindex, newmetric, + NULL, 0, 0): + kernel_route_add_v6(pref, plen, + newgate, newifindex, newmetric, + NULL, 0, 0); + if(rc < 0) { + if(errno != EEXIST) + return rc; + added = 0; + } else { + added = 1; + } + + if (ipv4) { + kernel_route_delete_v4(pref, plen, + gate, ifindex, metric, + NULL, 0, 0); + } else { + kernel_route_delete_v6(pref, plen, + gate, ifindex, metric, + NULL, 0, 0); + } + + if(!added) { + rc = ipv4 ? + kernel_route_add_v4(pref, plen, + newgate, newifindex, newmetric, + NULL, 0, 0): + kernel_route_add_v6(pref, plen, + newgate, newifindex, newmetric, + NULL, 0, 0); + if(rc < 0) { + if(errno == EEXIST) + rc = 1; + /* In principle, we should try to re-install the flushed + route on failure to preserve. However, this should + hopefully not matter much in practice. */ + } + } + + return rc; + break; + default: + zlog_err("this should never appens (false value - kernel_route)"); + assert(0); + exit(1); + break; + } +} + +static int +kernel_route_add_v4(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) +{ + unsigned int tmp_ifindex = ifindex; /* (for typing) */ + 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 comprehensive 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; + SET_FLAG(api.message, ZAPI_MESSAGE_NEXTHOP); + 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, "adding route (ipv4) to zebra"); + return zapi_ipv4_route (ZEBRA_IPV4_ROUTE_ADD, zclient, + &quagga_prefix, &api); +} + +static int +kernel_route_add_v6(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) +{ + 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 comprehensive 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; + SET_FLAG(api.message, ZAPI_MESSAGE_NEXTHOP); + 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, "adding route (ipv6) to zebra"); + return zapi_ipv6_route (ZEBRA_IPV6_ROUTE_ADD, zclient, + &quagga_prefix, &api); +} + +static int +kernel_route_delete_v4(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) +{ + unsigned int tmp_ifindex = ifindex; /* (for typing) */ + 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 comprehensive 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; + apply_mask_ipv4(&quagga_prefix); + + api.type = ZEBRA_ROUTE_BABEL; + api.flags = 0; + api.message = 0; + SET_FLAG(api.message, ZAPI_MESSAGE_NEXTHOP); + 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, "removing route (ipv4) to zebra"); + return zapi_ipv4_route (ZEBRA_IPV4_ROUTE_DELETE, zclient, + &quagga_prefix, &api); +} + +static int +kernel_route_delete_v6(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) +{ + 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 comprehensive 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; + SET_FLAG(api.message, ZAPI_MESSAGE_NEXTHOP); + api.nexthop_num = 1; + api.nexthop = &nexthop_pointer; + SET_FLAG(api.message, ZAPI_MESSAGE_IFINDEX); + api.ifindex_num = 1; + api.ifindex = &tmp_ifindex; + + debugf(BABEL_DEBUG_ROUTE, "removing route (ipv6) to zebra"); + return zapi_ipv6_route (ZEBRA_IPV6_ROUTE_DELETE, zclient, + &quagga_prefix, &api); +} + +int +kernel_routes(struct kernel_route *routes, int maxroutes) +{ + fprintf(stderr, "\tkernel_routes --- not implemented\n"); + return 0; +} + +int +kernel_callback(int (*fn)(int, void*), void *closure) +{ + struct thread thread; + fprintf(stderr, "\tkernel_callback\n"); + /* do a little work on threads */ + if (thread_fetch(master, &thread) != NULL) { + thread_call (&thread); + } + return 0; +} + +int +kernel_addresses(struct interface *interface, int ll, + struct kernel_route *routes, int maxroutes) +{ + fprintf(stderr, "\tkernel_addresses --- not implemented\n"); + return 0; +} + +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 if (len > 8) { + memcpy(eui, tmp, 8); + } else if (len > 0){ + memset(eui, 0, 8 - len); + memcpy(eui + 8 - len, tmp, len); + } else { + return -1; + } + return 0; +} diff --git a/babeld/message.c b/babeld/message.c new file mode 100644 index 00000000..bfb17625 --- /dev/null +++ b/babeld/message.c @@ -0,0 +1,1456 @@ +/* + * 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 <assert.h> +#include <sys/time.h> +#include <netinet/in.h> +#include <arpa/inet.h> + +#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 parasitic = 0; +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 }; + +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]; + + 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: 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); + 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); + 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); + break; + default: + return -1; + } + + mask_prefix(p_r, prefix, plen < 0 ? 128 : ae == 1 ? plen + 96 : plen); + return 1; +} + +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); +} + +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)) { + fprintf(stderr, "Received packet from non-local address %s.\n", + format_address(from)); + return; + } + + if(packet[0] != 42) { + fprintf(stderr, "Received malformed packet on %s from %s.\n", + ifp->name, format_address(from)); + return; + } + + if(packet[1] != 2) { + fprintf(stderr, + "Received packet with unknown version %d on %s from %s.\n", + packet[1], ifp->name, format_address(from)); + return; + } + + neigh = find_neighbour(from, ifp); + if(neigh == NULL) { + fprintf(stderr, "Couldn't allocate neighbour.\n"); + return; + } + + DO_NTOHS(bodylen, packet + 2); + + if(bodylen + 4 > packetlen) { + fprintf(stderr, "Received truncated packet (%d + 4 > %d).\n", + 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) { + fprintf(stderr, "Received truncated message.\n"); + break; + } + len = message[1]; + if(i + len > bodylen) { + fprintf(stderr, "Received truncated message.\n"); + 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); + babel_get_if_nfo(ifp)->activity_time = babel_now.tv_sec; + 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 short interval, seqno, metric; + int rc; + 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; + } + + 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) { + fprintf(stderr, "Received prefix with no router id.\n"); + 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) { + fprintf(stderr, + "Received wildcard update with finite metric.\n"); + 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; + } + + update_route(router_id, prefix, plen, seqno, metric, interval, + neigh, nh); + } 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) { + /* If a neighbour is requesting a full route dump from us, + we might as well send it an IHU. */ + send_ihu(neigh, NULL); + 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: + fprintf(stderr, "Couldn't parse packet (%d, %d) from %s on %s.\n", + 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 { + fprintf(stderr, "Warning: bucket full, dropping packet to %s.\n", + 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 { + fprintf(stderr, + "Warning: bucket full, dropping unicast packet" + "to %s if %s.\n", + 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) +{ + 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; + + 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); + 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); + end_message(ifp, MESSAGE_UPDATE, 10 + (real_plen + 7) / 8 - omit); + + 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 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++) { + unsigned short seqno; + unsigned short metric; + + /* 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); + last_prefix = xroute->prefix; + last_plen = xroute->plen; + } else if(route) { + seqno = route->seqno; + metric = route_metric(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; + really_send_update(ifp, route->src->id, + route->src->prefix, + route->src->plen, + seqno, metric); + 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); + } + } + 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); + n = MAX(babel_ifp->bufsize / 16, 4); + 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) { + 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++; +} + +void +send_update(struct interface *ifp, int urgent, + const unsigned char *prefix, unsigned char plen) +{ + babel_interface_nfo *babel_ifp = NULL; + int i; + + if(ifp == NULL) { + struct interface *ifp_aux; + struct listnode *linklist_node = NULL; + struct 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) { + if(!parasitic || find_xroute(prefix, plen)) { + debugf(BABEL_DEBUG_COMMON,"Sending update to %s for %s.", + ifp->name, format_prefix(prefix, plen)); + buffer_update(ifp, prefix, plen); + } + } else { + if(!interface_idle(babel_ifp)) { + send_self_update(ifp); + if(!parasitic) { + debugf(BABEL_DEBUG_COMMON,"Sending update to %s for any.", ifp->name); + for(i = 0; i < numroutes; i++) + if(routes[i].installed) + buffer_update(ifp, + routes[i].src->prefix, + routes[i].src->plen); + } + } + set_timeout(&babel_ifp->update_timeout, babel_ifp->update_interval); + } + schedule_update_flush(ifp, urgent); +} + +void +send_update_resend(struct interface *ifp, + const unsigned char *prefix, unsigned char plen) +{ + int delay; + + assert(prefix != NULL); + + send_update(ifp, 1, prefix, plen); + + delay = 2000; + delay = MIN(delay, wireless_hello_interval / 2); + delay = MIN(delay, wired_hello_interval / 2); + delay = MAX(delay, 10); + record_resend(RESEND_UPDATE, prefix, plen, 0, 0, NULL, 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; +} + +void +send_self_update(struct interface *ifp) +{ + int i; + + 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; + } + + if(!interface_idle(babel_get_if_nfo(ifp))) { + debugf(BABEL_DEBUG_COMMON,"Sending self update to %s.", ifp->name); + for(i = 0; i < numxroutes; i++) + send_update(ifp, 0, xroutes[i].prefix, xroutes[i].plen); + } +} + +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) +{ + babel_interface_nfo *babel_ifp = NULL; + 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; + + babel_ifp = babel_get_if_nfo(ifp); + 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) +{ + babel_interface_nfo *babel_ifp = NULL; + 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; + + babel_ifp = babel_get_if_nfo(ifp); + 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) +{ + int delay; + + if(neigh) + send_unicast_multihop_request(neigh, prefix, plen, seqno, id, 127); + else + send_multihop_request(NULL, prefix, plen, seqno, id, 127); + + delay = 2000; + delay = MIN(delay, wireless_hello_interval / 2); + delay = MIN(delay, wired_hello_interval / 2); + delay = MAX(delay, 10); + record_resend(RESEND_REQUEST, prefix, plen, seqno, id, + neigh ? neigh->ifp : NULL, 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 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 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..1626a887 --- /dev/null +++ b/babeld/message.h @@ -0,0 +1,112 @@ +/* + * 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 parasitic; +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..43da8e09 --- /dev/null +++ b/babeld/neighbour.c @@ -0,0 +1,342 @@ +/* + * 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. */ +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 * 10 * 3) + 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 * 10 * 10)) { + 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 * 10); + if(neigh->ihu_interval > 0) + msecs = MIN(msecs, neigh->ihu_interval * 10); + 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..5cb1236e --- /dev/null +++ b/babeld/net.c @@ -0,0 +1,229 @@ +/* + * 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; + + 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; + + 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, + const void *buf1, int buflen1, const void *buf2, int buflen2, + const struct sockaddr *sin, int slen) +{ + struct iovec iovec[2]; + struct msghdr msg; + int rc; + + iovec[0].iov_base = (void*)buf1; + iovec[0].iov_len = buflen1; + iovec[1].iov_base = (void*)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..e6729001 --- /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, + const void *buf1, int buflen1, const void *buf2, int buflen2, + const 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..5a786fcd --- /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 = kind == RESEND_REQUEST ? 128 : UPDATE_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 = kind == RESEND_REQUEST ? 128 : UPDATE_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..fdb57300 --- /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 UPDATE_MAX 4 + +#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..e0c9d047 --- /dev/null +++ b/babeld/route.c @@ -0,0 +1,756 @@ +/* + * 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 <string.h> +#include <stdio.h> +#include <errno.h> +#include <assert.h> +#include <sys/time.h> + +#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 route *route); + +struct route *routes = NULL; +int numroutes = 0, maxroutes = 0; +int kernel_metric = 0; +int allow_duplicates = -1; + +struct route * +find_route(const unsigned char *prefix, unsigned char plen, + struct neighbour *neigh, const unsigned char *nexthop) +{ + int i; + for(i = 0; i < numroutes; i++) { + if(routes[i].neigh == neigh && + memcmp(routes[i].nexthop, nexthop, 16) == 0 && + source_match(routes[i].src, prefix, plen)) + return &routes[i]; + } + return NULL; +} + +struct route * +find_installed_route(const unsigned char *prefix, unsigned char plen) +{ + int i; + for(i = 0; i < numroutes; i++) { + if(routes[i].installed && source_match(routes[i].src, prefix, plen)) + return &routes[i]; + } + return NULL; +} + +void +flush_route(struct route *route) +{ + int i; + struct source *src; + unsigned oldmetric; + int lost = 0; + + i = route - routes; + assert(i >= 0 && i < numroutes); + + oldmetric = route_metric(route); + + if(route->installed) { + uninstall_route(route); + lost = 1; + } + + src = route->src; + + if(i != numroutes - 1) + memcpy(routes + i, routes + numroutes - 1, sizeof(struct route)); + numroutes--; + VALGRIND_MAKE_MEM_UNDEFINED(routes + numroutes, sizeof(struct route)); + + if(numroutes == 0) { + free(routes); + routes = NULL; + maxroutes = 0; + } else if(maxroutes > 8 && numroutes < maxroutes / 4) { + struct route *new_routes; + int n = maxroutes / 2; + new_routes = realloc(routes, n * sizeof(struct route)); + if(new_routes != NULL) { + routes = new_routes; + maxroutes = n; + } + } + + if(lost) + route_lost(src, oldmetric); +} + +void +flush_neighbour_routes(struct neighbour *neigh) +{ + int i; + + i = 0; + while(i < numroutes) { + if(routes[i].neigh == neigh) { + flush_route(&routes[i]); + continue; + } + i++; + } +} + +void +flush_interface_routes(struct interface *ifp, int v4only) +{ + int i; + + i = 0; + while(i < numroutes) { + if(routes[i].neigh->ifp == ifp && + (!v4only || v4mapped(routes[i].nexthop))) { + flush_route(&routes[i]); + continue; + } + i++; + } +} + +static int +metric_to_kernel(int metric) +{ + return metric < INFINITY ? kernel_metric : KERNEL_INFINITY; +} + +void +install_route(struct route *route) +{ + int rc; + + if(route->installed) + return; + + if(!route_feasible(route)) + fprintf(stderr, "WARNING: installing unfeasible route " + "(this shouldn't happen)."); + + 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; +} + +void +uninstall_route(struct 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 route *old, struct route *new) +{ + int rc; + + if(!old) { + install_route(new); + return; + } + + if(!old->installed) + return; + + if(!route_feasible(new)) + fprintf(stderr, "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; +} + +static void +change_route_metric(struct route *route, unsigned newmetric) +{ + int old, new; + + if(route_metric(route) == newmetric) + return; + + 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->metric = newmetric; +} + +static void +retract_route(struct route *route) +{ + route->refmetric = INFINITY; + change_route_metric(route, INFINITY); +} + +int +route_feasible(struct route *route) +{ + return update_feasible(route->src, route->seqno, route->refmetric); +} + +int +route_old(struct route *route) +{ + return route->time < babel_now.tv_sec - route->hold_time * 7 / 8; +} + +int +route_expired(struct route *route) +{ + return route->time < babel_now.tv_sec - route->hold_time; +} + +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 route * +find_best_route(const unsigned char *prefix, unsigned char plen, int feasible, + struct neighbour *exclude) +{ + struct route *route = NULL; + int i; + + for(i = 0; i < numroutes; i++) { + if(!source_match(routes[i].src, prefix, plen)) + continue; + if(route_expired(&routes[i])) + continue; + if(feasible && !route_feasible(&routes[i])) + continue; + if(exclude && routes[i].neigh == exclude) + continue; + if(route && route_metric(route) <= route_metric(&routes[i])) + continue; + route = &routes[i]; + } + return route; +} + +void +update_route_metric(struct 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); + int newmetric = MIN(route->refmetric + + add_metric + + neighbour_cost(route->neigh), + INFINITY); + + if(newmetric != oldmetric) { + change_route_metric(route, newmetric); + route_changed(route, route->src, oldmetric); + } + } +} + +/* Called whenever a neighbour's cost changes, to update the metric of + all routes through that neighbour. */ +void +update_neighbour_metric(struct neighbour *neigh, int changed) +{ + if(changed) { + int i; + + i = 0; + while(i < numroutes) { + if(routes[i].neigh == neigh) + update_route_metric(&routes[i]); + i++; + } + } +} + +void +update_interface_metric(struct interface *ifp) +{ + int i; + + i = 0; + while(i < numroutes) { + if(routes[i].neigh->ifp == ifp) + update_route_metric(&routes[i]); + i++; + } +} + +/* This is called whenever we receive an update. */ +struct 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) +{ + struct 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; /* I have announced the route */ + + if(martian_prefix(prefix, plen)) { + fprintf(stderr, "Rejecting martian route to %s through %s.\n", + 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; + + src = find_source(router_id, prefix, plen, 1, seqno); + if(src == NULL) + return NULL; + + feasible = update_feasible(src, seqno, refmetric); + route = find_route(prefix, plen, neigh, nexthop); + 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 = src; + if(feasible && refmetric < INFINITY) + route->time = babel_now.tv_sec; + route->seqno = seqno; + route->refmetric = refmetric; + change_route_metric(route, 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); + } else { + if(refmetric >= INFINITY) + /* Somebody's retracting a route we never saw. */ + return NULL; + if(!feasible) { + send_unfeasible_request(neigh, 0, seqno, metric, src); + return NULL; + } + if(numroutes >= maxroutes) { + struct route *new_routes; + int n = maxroutes < 1 ? 8 : 2 * maxroutes; + new_routes = routes == NULL ? + malloc(n * sizeof(struct route)) : + realloc(routes, n * sizeof(struct route)); + if(new_routes == NULL) + return NULL; + maxroutes = n; + routes = new_routes; + } + route = &routes[numroutes]; + route->src = src; + route->refmetric = refmetric; + route->seqno = seqno; + route->metric = metric; + route->neigh = neigh; + memcpy(route->nexthop, nexthop, 16); + route->time = babel_now.tv_sec; + route->hold_time = hold_time; + route->installed = 0; + numroutes++; + 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 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 route *route) +{ + struct 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) + 192) + goto install; + + /* Avoid switching sources */ + if(installed->src != route->src) + return; + + 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; + + i = 0; + while(i < numroutes) { + if(routes[i].neigh == neigh) { + if(routes[i].refmetric != INFINITY) { + unsigned short oldmetric = route_metric(&routes[i]); + retract_route(&routes[i]); + if(oldmetric != INFINITY) + route_changed(&routes[i], routes[i].src, oldmetric); + } + } + i++; + } +} + +void +send_triggered_update(struct 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 route *route, + struct source *oldsrc, unsigned short oldmetric) +{ + if(route->installed) { + if(route_metric(route) > oldmetric) { + struct 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 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); + } +} + +void +expire_routes(void) +{ + int i; + + debugf(BABEL_DEBUG_COMMON,"Expiring old routes."); + + i = 0; + while(i < numroutes) { + struct route *route = &routes[i]; + + if(route->time > babel_now.tv_sec || /* clock stepped */ + route_old(route)) { + flush_route(route); + continue; + } + + update_route_metric(route); + + if(route->installed && route->refmetric < INFINITY) { + if(route_old(route)) + send_unicast_request(route->neigh, + route->src->prefix, route->src->plen); + } + i++; + } +} + +void +babel_uninstall_all_routes(void) +{ + while(numroutes > 0) { + uninstall_route(&routes[0]); + /* We need to flush the route so network_up won't reinstall it */ + flush_route(&routes[0]); + } +} + +struct route * +babel_route_get_by_source(struct source *src) +{ + int i; + for(i = 0; i < numroutes; i++) { + if(routes[i].src == src) + return &routes[i]; + } + return NULL; +} diff --git a/babeld/route.h b/babeld/route.h new file mode 100644 index 00000000..e36f6c34 --- /dev/null +++ b/babeld/route.h @@ -0,0 +1,104 @@ +/* + * 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 "babel_interface.h" +#include "source.h" + +struct route { + struct source *src; + unsigned short metric; + unsigned short refmetric; + unsigned short seqno; + struct neighbour *neigh; + unsigned char nexthop[16]; + time_t time; + unsigned short hold_time; /* in seconds */ + short installed; +}; + +static inline int +route_metric(const struct route *route) +{ + return route->metric; +} + +extern struct route *routes; +extern int numroutes, maxroutes; +extern int kernel_metric, allow_duplicates; + +struct route *find_route(const unsigned char *prefix, unsigned char plen, + struct neighbour *neigh, const unsigned char *nexthop); +struct route *find_installed_route(const unsigned char *prefix, + unsigned char plen); +void flush_route(struct route *route); +void flush_neighbour_routes(struct neighbour *neigh); +void flush_interface_routes(struct interface *ifp, int v4only); +void install_route(struct route *route); +void uninstall_route(struct route *route); +void switch_route(struct route *old, struct route *new); +int route_feasible(struct route *route); +int route_old(struct route *route); +int route_expired(struct route *route); +int update_feasible(struct source *src, + unsigned short seqno, unsigned short refmetric); +struct route *find_best_route(const unsigned char *prefix, unsigned char plen, + int feasible, struct neighbour *exclude); +struct 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 route *route); +struct route *update_route(const unsigned char *a, + const unsigned char *p, unsigned char plen, + unsigned short seqno, unsigned short refmetric, + unsigned short interval, struct neighbour *neigh, + const unsigned char *nexthop); +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 route *route, + struct source *oldsrc, unsigned oldmetric); +void route_changed(struct route *route, + struct source *oldsrc, unsigned short oldmetric); +void route_lost(struct source *src, unsigned oldmetric); +void expire_routes(void); + +void babel_uninstall_all_routes(void); +struct route *babel_route_get_by_source(struct source *src); diff --git a/babeld/source.c b/babeld/source.c new file mode 100644 index 00000000..cc4ed445 --- /dev/null +++ b/babeld/source.c @@ -0,0 +1,159 @@ +/* + * 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(source_match(src, p, plen)) + 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->next = srcs; + srcs = src; + return src; +} + +int +flush_source(struct source *src) +{ + /* This is absolutely horrible -- it makes expire_sources quadratic. + But it's not called very often. */ + + if (babel_route_get_by_source(src) != NULL) + 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; +} + +int +source_match(struct source *src, + const unsigned char *p, unsigned char plen) +{ + if(src->plen != plen) + return 0; + if(src->prefix[15] != p[15]) + return 0; + if(memcmp(src->prefix, p, 16) != 0) + return 0; + return 1; +} + +void +update_source(struct source *src, + unsigned short seqno, unsigned short metric) +{ + if(metric >= INFINITY) + return; + + 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; + } +} diff --git a/babeld/source.h b/babeld/source.h new file mode 100644 index 00000000..38d3c004 --- /dev/null +++ b/babeld/source.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. +*/ + +#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; + time_t time; +}; + +int source_match(struct source *src, + const unsigned char *p, unsigned char plen); +struct source *find_source(const unsigned char *id, + const unsigned char *p, + unsigned char plen, + int create, unsigned short seqno); +int flush_source(struct source *src); +void update_source(struct source *src, + unsigned short seqno, unsigned short metric); +void expire_sources(void); + + +#endif diff --git a/babeld/util.c b/babeld/util.c new file mode 100644 index 00000000..f1ac0f15 --- /dev/null +++ b/babeld/util.c @@ -0,0 +1,509 @@ +/* + * 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; +} + +void +do_debugf(const char *format, ...) +{ + va_list args; + va_start(args, format); + vfprintf(stderr, format, args); + fprintf(stderr, "\n"); + fflush(stderr); + va_end(args); +} + +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]; +} + +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_net(const char *net, unsigned char *prefix_r, unsigned char *plen_r, + int *af_r) +{ + char buf[INET6_ADDRSTRLEN]; + char *slash, *end; + unsigned char prefix[16]; + long plen; + int af; + struct in_addr ina; + struct in6_addr ina6; + int rc; + + if(strcmp(net, "default") == 0) { + memset(prefix, 0, 16); + plen = 0; + } else { + slash = strchr(net, '/'); + if(slash == NULL) { + rc = parse_address(net, prefix, &af); + if(rc < 0) + return rc; + plen = 128; + } else { + if(slash - net >= INET6_ADDRSTRLEN) + return -1; + memcpy(buf, net, slash - net); + buf[slash - net] = '\0'; + rc = inet_pton(AF_INET, buf, &ina); + if(rc > 0) { + memcpy(prefix, v4prefix, 12); + memcpy(prefix + 12, &ina, 4); + plen = strtol(slash + 1, &end, 0); + if(*end != '\0' || plen < 0 || plen > 32) + return -1; + plen += 96; + af = AF_INET; + } else { + rc = inet_pton(AF_INET6, buf, &ina6); + if(rc > 0) { + memcpy(prefix, &ina6, 16); + plen = strtol(slash + 1, &end, 0); + if(*end != '\0' || plen < 0 || plen > 128) + return -1; + af = AF_INET6; + } else { + return -1; + } + } + } + } + mask_prefix(prefix_r, prefix, plen); + *plen_r = plen; + if(af_r) *af_r = af; + return 0; +} + +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..d653b613 --- /dev/null +++ b/babeld/util.h @@ -0,0 +1,168 @@ +/* + * 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(*(unsigned short*)(_s)); } while(0) +#define DO_NTOHL(_d, _s) do { _d = ntohl(*(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)); +void do_debugf(const char *format, ...) + ATTRIBUTE ((format (printf, 1, 2))) COLD; +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); +int parse_address(const char *address, unsigned char *addr_r, int *af_r); +int parse_net(const char *ifp, unsigned char *prefix_r, unsigned char *plen_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)) do_debugf(__VA_ARGS__); \ +} while(0) +#elif defined __GNUC__ +#define debugf(level, _args...) \ +do { \ +if(UNLIKELY(debug & level)) do_debugf(_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..42f83d07 --- /dev/null +++ b/babeld/xroute.c @@ -0,0 +1,226 @@ +/* + * 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 <stdio.h> +#include <string.h> +#include <errno.h> +#include <assert.h> +#include <sys/time.h> +#include <netinet/in.h> + +#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" + +struct xroute *xroutes; +int numxroutes = 0; +int 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, 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); + 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; +} + +/* add an xroute, verifying some conditions; return 0 if there is no changes */ +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 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..c9a4f85f --- /dev/null +++ b/babeld/xroute.h @@ -0,0 +1,63 @@ +/* + * 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; +}; + +extern struct xroute *xroutes; +extern int numxroutes; + +struct xroute *find_xroute(const unsigned char *prefix, unsigned char plen); +void flush_xroute(struct xroute *xroute); +int xroute_add_new_route(unsigned char prefix[16], unsigned char plen, + unsigned short metric, unsigned int ifindex, + int proto, int send_updates); +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); diff --git a/configure.ac b/configure.ac index 61c4466b..4fe70e15 100755 --- a/configure.ac +++ b/configure.ac @@ -207,6 +207,8 @@ AC_ARG_ENABLE(ospfd, [ --disable-ospfd do not build ospfd]) AC_ARG_ENABLE(ospf6d, [ --disable-ospf6d do not build ospf6d]) +AC_ARG_ENABLE(babeld, +[ --disable-babeld do not build babeld]) AC_ARG_ENABLE(watchquagga, [ --disable-watchquagga do not build watchquagga]) AC_ARG_ENABLE(isisd, @@ -1245,6 +1247,12 @@ else OSPFD="ospfd" fi +if test "${enable_babeld}" = "no";then + BABELD="" +else + BABELD="babeld" +fi + if test "${enable_watchquagga}" = "no";then WATCHQUAGGA="" else @@ -1301,6 +1309,7 @@ AC_SUBST(RIPD) AC_SUBST(RIPNGD) AC_SUBST(OSPFD) AC_SUBST(OSPF6D) +AC_SUBST(BABELD) AC_SUBST(WATCHQUAGGA) AC_SUBST(ISISD) AC_SUBST(SOLARIS) @@ -1544,6 +1553,7 @@ AC_DEFINE_UNQUOTED(PATH_RIPNGD_PID, "$quagga_statedir/ripngd.pid",ripngd PID) AC_DEFINE_UNQUOTED(PATH_BGPD_PID, "$quagga_statedir/bgpd.pid",bgpd PID) AC_DEFINE_UNQUOTED(PATH_OSPFD_PID, "$quagga_statedir/ospfd.pid",ospfd PID) AC_DEFINE_UNQUOTED(PATH_OSPF6D_PID, "$quagga_statedir/ospf6d.pid",ospf6d PID) +AC_DEFINE_UNQUOTED(PATH_BABELD_PID, "$quagga_statedir/babeld.pid",babeld PID) AC_DEFINE_UNQUOTED(PATH_ISISD_PID, "$quagga_statedir/isisd.pid",isisd PID) AC_DEFINE_UNQUOTED(PATH_WATCHQUAGGA_PID, "$quagga_statedir/watchquagga.pid",watchquagga PID) AC_DEFINE_UNQUOTED(ZEBRA_SERV_PATH, "$quagga_statedir/zserv.api",zebra api socket) @@ -1553,6 +1563,7 @@ AC_DEFINE_UNQUOTED(RIPNG_VTYSH_PATH, "$quagga_statedir/ripngd.vty",ripng vty soc AC_DEFINE_UNQUOTED(BGP_VTYSH_PATH, "$quagga_statedir/bgpd.vty",bgpd vty socket) AC_DEFINE_UNQUOTED(OSPF_VTYSH_PATH, "$quagga_statedir/ospfd.vty",ospfd vty socket) AC_DEFINE_UNQUOTED(OSPF6_VTYSH_PATH, "$quagga_statedir/ospf6d.vty",ospf6d vty socket) +AC_DEFINE_UNQUOTED(BABEL_VTYSH_PATH, "$quagga_statedir/babeld.vty",babeld vty socket) AC_DEFINE_UNQUOTED(ISIS_VTYSH_PATH, "$quagga_statedir/isisd.vty",isisd vty socket) AC_DEFINE_UNQUOTED(DAEMON_VTY_DIR, "$quagga_statedir",daemon vty directory) @@ -1577,8 +1588,9 @@ AC_MSG_RESULT($ac_cv_htonl_works) AC_CONFIG_FILES([Makefile lib/Makefile zebra/Makefile ripd/Makefile ripngd/Makefile bgpd/Makefile ospfd/Makefile watchquagga/Makefile - ospf6d/Makefile isisd/Makefile vtysh/Makefile doc/Makefile - ospfclient/Makefile tests/Makefile m4/Makefile redhat/Makefile + ospf6d/Makefile isisd/Makefile babeld/Makefile vtysh/Makefile + doc/Makefile ospfclient/Makefile tests/Makefile m4/Makefile + redhat/Makefile pkgsrc/Makefile redhat/quagga.spec lib/version.h diff --git a/lib/command.c b/lib/command.c index 4f6d184d..e62a7a7e 100644 --- a/lib/command.c +++ b/lib/command.c @@ -2400,6 +2400,7 @@ DEFUN (config_exit, case BGP_NODE: case RIP_NODE: case RIPNG_NODE: + case BABEL_NODE: case OSPF_NODE: case OSPF6_NODE: case ISIS_NODE: @@ -2449,6 +2450,7 @@ DEFUN (config_end, case ZEBRA_NODE: case RIP_NODE: case RIPNG_NODE: + case BABEL_NODE: case BGP_NODE: case BGP_VPNV4_NODE: case BGP_IPV4_NODE: diff --git a/lib/command.h b/lib/command.h index 1275efee..2d708d8e 100644 --- a/lib/command.h +++ b/lib/command.h @@ -78,6 +78,7 @@ enum node_type TABLE_NODE, /* rtm_table selection node. */ RIP_NODE, /* RIP protocol mode node. */ RIPNG_NODE, /* RIPng protocol mode node. */ + BABEL_NODE, /* Babel protocol mode node. */ BGP_NODE, /* BGP protocol mode which includes BGP4+ */ BGP_VPNV4_NODE, /* BGP MPLS-VPN PE exchange. */ BGP_IPV4_NODE, /* BGP IPv4 unicast address family. */ diff --git a/lib/distribute.c b/lib/distribute.c index 04889030..8d6f6377 100644 --- a/lib/distribute.c +++ b/lib/distribute.c @@ -758,22 +758,25 @@ distribute_list_init (int node) (int (*) (const void *, const void *)) distribute_cmp); if(node==RIP_NODE) { - install_element (RIP_NODE, &distribute_list_all_cmd); - install_element (RIP_NODE, &no_distribute_list_all_cmd); - install_element (RIP_NODE, &distribute_list_cmd); - install_element (RIP_NODE, &no_distribute_list_cmd); - install_element (RIP_NODE, &distribute_list_prefix_all_cmd); - install_element (RIP_NODE, &no_distribute_list_prefix_all_cmd); - install_element (RIP_NODE, &distribute_list_prefix_cmd); - install_element (RIP_NODE, &no_distribute_list_prefix_cmd); - } else { - install_element (RIPNG_NODE, &ipv6_distribute_list_all_cmd); - install_element (RIPNG_NODE, &no_ipv6_distribute_list_all_cmd); - install_element (RIPNG_NODE, &ipv6_distribute_list_cmd); - install_element (RIPNG_NODE, &no_ipv6_distribute_list_cmd); - install_element (RIPNG_NODE, &ipv6_distribute_list_prefix_all_cmd); - install_element (RIPNG_NODE, &no_ipv6_distribute_list_prefix_all_cmd); - install_element (RIPNG_NODE, &ipv6_distribute_list_prefix_cmd); - install_element (RIPNG_NODE, &no_ipv6_distribute_list_prefix_cmd); + install_element (node, &distribute_list_all_cmd); + install_element (node, &no_distribute_list_all_cmd); + install_element (node, &distribute_list_cmd); + install_element (node, &no_distribute_list_cmd); + install_element (node, &distribute_list_prefix_all_cmd); + install_element (node, &no_distribute_list_prefix_all_cmd); + install_element (node, &distribute_list_prefix_cmd); + install_element (node, &no_distribute_list_prefix_cmd); + } else if (node == RIPNG_NODE || node == BABEL_NODE) { + /* WARNING: two identical commands installed do a crash, so be worry with + aliases. For this reason, and because all these commands are aliases, Babel + is not set with RIP. */ + install_element (node, &ipv6_distribute_list_all_cmd); + install_element (node, &no_ipv6_distribute_list_all_cmd); + install_element (node, &ipv6_distribute_list_cmd); + install_element (node, &no_ipv6_distribute_list_cmd); + install_element (node, &ipv6_distribute_list_prefix_all_cmd); + install_element (node, &no_ipv6_distribute_list_prefix_all_cmd); + install_element (node, &ipv6_distribute_list_prefix_cmd); + install_element (node, &no_ipv6_distribute_list_prefix_cmd); } } diff --git a/lib/distribute.h b/lib/distribute.h index a1bec03a..5072016f 100644 --- a/lib/distribute.h +++ b/lib/distribute.h @@ -22,6 +22,9 @@ #ifndef _ZEBRA_DISTRIBUTE_H #define _ZEBRA_DISTRIBUTE_H +#include <zebra.h> +#include "if.h" + /* Disctirubte list types. */ enum distribute_type { @@ -48,6 +48,7 @@ const char *zlog_proto_names[] = "BGP", "OSPF", "RIPNG", + "BABEL", "OSPF6", "ISIS", "MASC", @@ -49,7 +49,8 @@ typedef enum ZLOG_RIP, ZLOG_BGP, ZLOG_OSPF, - ZLOG_RIPNG, + ZLOG_RIPNG, + ZLOG_BABEL, ZLOG_OSPF6, ZLOG_ISIS, ZLOG_MASC diff --git a/lib/memory.c b/lib/memory.c index 4090fd90..63ec6b54 100644 --- a/lib/memory.c +++ b/lib/memory.c @@ -466,6 +466,17 @@ DEFUN (show_memory_ripng, return CMD_SUCCESS; } +DEFUN (show_memory_babel, + show_memory_babel_cmd, + "show memory babel", + SHOW_STR + "Memory statistics\n" + "Babel memory\n") +{ + show_memory_vty (vty, memory_list_babel); + return CMD_SUCCESS; +} + DEFUN (show_memory_bgp, show_memory_bgp_cmd, "show memory bgp", diff --git a/lib/memtypes.c b/lib/memtypes.c index d2bc1c62..cd39c996 100644 --- a/lib/memtypes.c +++ b/lib/memtypes.c @@ -174,6 +174,13 @@ struct memory_list memory_list_ripng[] = { -1, NULL } }; +struct memory_list memory_list_babel[] = +{ + { MTYPE_BABEL, "Babel structure" }, + { MTYPE_BABEL_IF, "Babel interface" }, + { -1, NULL } +}; + struct memory_list memory_list_ospf[] = { { MTYPE_OSPF_TOP, "OSPF top" }, diff --git a/lib/route_types.txt b/lib/route_types.txt index fde0bc8d..cebf01fc 100644 --- a/lib/route_types.txt +++ b/lib/route_types.txt @@ -58,6 +58,7 @@ ZEBRA_ROUTE_BGP, bgp, bgpd, 'B', 1, 1, "BGP" # possible). ZEBRA_ROUTE_HSLS, hsls, hslsd, 'H', 0, 0, "HSLS" ZEBRA_ROUTE_OLSR, olsr, olsrd, 'o', 0, 0, "OLSR" +ZEBRA_ROUTE_BABEL, babel, babeld, 'A', 1, 1, "Babel" ## help strings ZEBRA_ROUTE_SYSTEM, "Reserved route type, for internal use only" @@ -72,3 +73,4 @@ ZEBRA_ROUTE_ISIS, "Intermediate System to Intermediate System (IS-IS)" ZEBRA_ROUTE_BGP, "Border Gateway Protocol (BGP)" ZEBRA_ROUTE_HSLS, "Hazy-Sighted Link State Protocol (HSLS)" ZEBRA_ROUTE_OLSR, "Optimised Link State Routing (OLSR)" +ZEBRA_ROUTE_BABEL, "Babel routing protocol (Babel)" diff --git a/lib/routemap.h b/lib/routemap.h index 1402f5c8..ba64553f 100644 --- a/lib/routemap.h +++ b/lib/routemap.h @@ -43,6 +43,7 @@ typedef enum { RMAP_RIP, RMAP_RIPNG, + RMAP_BABEL, RMAP_OSPF, RMAP_OSPF6, RMAP_BGP, diff --git a/lib/thread.h b/lib/thread.h index 69bb8d6c..dfc51e28 100644 --- a/lib/thread.h +++ b/lib/thread.h @@ -23,6 +23,8 @@ #ifndef _ZEBRA_THREAD_H #define _ZEBRA_THREAD_H +#include <zebra.h> + struct rusage_t { #ifdef HAVE_RUSAGE @@ -699,6 +699,7 @@ vty_end_config (struct vty *vty) case ZEBRA_NODE: case RIP_NODE: case RIPNG_NODE: + case BABEL_NODE: case BGP_NODE: case BGP_VPNV4_NODE: case BGP_IPV4_NODE: @@ -1107,6 +1108,7 @@ vty_stop_input (struct vty *vty) case ZEBRA_NODE: case RIP_NODE: case RIPNG_NODE: + case BABEL_NODE: case BGP_NODE: case RMAP_NODE: case OSPF_NODE: diff --git a/lib/zclient.h b/lib/zclient.h index 73389ecd..a7d7b548 100644 --- a/lib/zclient.h +++ b/lib/zclient.h @@ -22,6 +22,9 @@ #ifndef _ZEBRA_ZCLIENT_H #define _ZEBRA_ZCLIENT_H +/* For struct zapi_ipv{4,6}. */ +#include "prefix.h" + /* For struct interface and struct connected. */ #include "if.h" diff --git a/zebra/client_main.c b/zebra/client_main.c index ce01231f..8b95907b 100644 --- a/zebra/client_main.c +++ b/zebra/client_main.c @@ -115,6 +115,7 @@ struct zebra_info { "static", ZEBRA_ROUTE_STATIC }, { "rip", ZEBRA_ROUTE_RIP }, { "ripng", ZEBRA_ROUTE_RIPNG }, + { "babel", ZEBRA_ROUTE_BABEL }, { "ospf", ZEBRA_ROUTE_OSPF }, { "ospf6", ZEBRA_ROUTE_OSPF6 }, { "bgp", ZEBRA_ROUTE_BGP }, diff --git a/zebra/zebra_rib.c b/zebra/zebra_rib.c index 21878aa6..f7f4d0a2 100644 --- a/zebra/zebra_rib.c +++ b/zebra/zebra_rib.c @@ -55,18 +55,19 @@ static const struct { int key; int distance; -} route_info[] = -{ - {ZEBRA_ROUTE_SYSTEM, 0}, - {ZEBRA_ROUTE_KERNEL, 0}, - {ZEBRA_ROUTE_CONNECT, 0}, - {ZEBRA_ROUTE_STATIC, 1}, - {ZEBRA_ROUTE_RIP, 120}, - {ZEBRA_ROUTE_RIPNG, 120}, - {ZEBRA_ROUTE_OSPF, 110}, - {ZEBRA_ROUTE_OSPF6, 110}, - {ZEBRA_ROUTE_ISIS, 115}, - {ZEBRA_ROUTE_BGP, 20 /* IBGP is 200. */} +} route_info[ZEBRA_ROUTE_MAX] = +{ + [ZEBRA_ROUTE_SYSTEM] = {ZEBRA_ROUTE_SYSTEM, 0}, + [ZEBRA_ROUTE_KERNEL] = {ZEBRA_ROUTE_KERNEL, 0}, + [ZEBRA_ROUTE_CONNECT] = {ZEBRA_ROUTE_CONNECT, 0}, + [ZEBRA_ROUTE_STATIC] = {ZEBRA_ROUTE_STATIC, 1}, + [ZEBRA_ROUTE_RIP] = {ZEBRA_ROUTE_RIP, 120}, + [ZEBRA_ROUTE_RIPNG] = {ZEBRA_ROUTE_RIPNG, 120}, + [ZEBRA_ROUTE_OSPF] = {ZEBRA_ROUTE_OSPF, 110}, + [ZEBRA_ROUTE_OSPF6] = {ZEBRA_ROUTE_OSPF6, 110}, + [ZEBRA_ROUTE_ISIS] = {ZEBRA_ROUTE_ISIS, 115}, + [ZEBRA_ROUTE_BGP] = {ZEBRA_ROUTE_BGP, 20 /* IBGP is 200. */}, + [ZEBRA_ROUTE_BABEL] = {ZEBRA_ROUTE_BABEL, 95}, /* no entry/default: 150 */ }; @@ -1235,6 +1236,7 @@ static const u_char meta_queue_map[ZEBRA_ROUTE_MAX] = { [ZEBRA_ROUTE_ISIS] = 2, [ZEBRA_ROUTE_BGP] = 3, [ZEBRA_ROUTE_HSLS] = 4, + [ZEBRA_ROUTE_BABEL] = 2, }; /* Look into the RN and queue it into one or more priority queues, |