diff options
Diffstat (limited to 'babeld')
34 files changed, 9367 insertions, 0 deletions
diff --git a/babeld/.gitignore b/babeld/.gitignore new file mode 100644 index 0000000..71ef678 --- /dev/null +++ b/babeld/.gitignore @@ -0,0 +1,7 @@ +* +!*.c +!*.h +!LICENCE +!Makefile +!subdir.am +!.gitignore diff --git a/babeld/LICENCE b/babeld/LICENCE new file mode 100644 index 0000000..2a340a4 --- /dev/null +++ b/babeld/LICENCE @@ -0,0 +1,19 @@ +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. diff --git a/babeld/Makefile b/babeld/Makefile new file mode 100644 index 0000000..ae125e6 --- /dev/null +++ b/babeld/Makefile @@ -0,0 +1,10 @@ +all: ALWAYS + @$(MAKE) -s -C .. babeld/babeld +%: ALWAYS + @$(MAKE) -s -C .. babeld/$@ + +Makefile: + #nothing +ALWAYS: +.PHONY: ALWAYS makefiles +.SUFFIXES: diff --git a/babeld/babel_errors.c b/babeld/babel_errors.c new file mode 100644 index 0000000..b22b1d5 --- /dev/null +++ b/babeld/babel_errors.c @@ -0,0 +1,61 @@ +/* + * Babel-specific error messages. + * Copyright (C) 2018 Cumulus Networks, Inc. + * Donald Sharp + * + * This program is free software; you can redistribute it 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 program 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; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include <zebra.h> + +#include "lib/ferr.h" +#include "babel_errors.h" + +/* clang-format off */ +static struct log_ref ferr_babel_err[] = { + { + .code = EC_BABEL_MEMORY, + .title = "BABEL Memory Errors", + .description = "Babel has failed to allocate memory, the system is about to run out of memory", + .suggestion = "Find the process that is causing memory shortages, remediate that process and restart FRR" + }, + { + .code = EC_BABEL_PACKET, + .title = "BABEL Packet Error", + .description = "Babel has detected a packet encode/decode problem", + .suggestion = "Collect relevant log files and file an Issue" + }, + { + .code = EC_BABEL_CONFIG, + .title = "BABEL Configuration Error", + .description = "Babel has detected a configuration error of some sort", + .suggestion = "Ensure that the configuration is correct" + }, + { + .code = EC_BABEL_ROUTE, + .title = "BABEL Route Error", + .description = "Babel has detected a routing error and has an inconsistent state", + .suggestion = "Gather data for filing an Issue and then restart FRR" + }, + { + .code = END_FERR, + } +}; +/* clang-format on */ + +void babel_error_init(void) +{ + log_ref_add(ferr_babel_err); +} diff --git a/babeld/babel_errors.h b/babeld/babel_errors.h new file mode 100644 index 0000000..629b660 --- /dev/null +++ b/babeld/babel_errors.h @@ -0,0 +1,35 @@ +/* + * Babel-specific error messages. + * Copyright (C) 2018 Cumulus Networks, Inc. + * Donald Sharp + * + * This program is free software; you can redistribute it 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 program 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; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#ifndef __BABEL_ERRORS_H__ +#define __BABEL_ERRORS_H__ + +#include "lib/ferr.h" + +enum babel_log_refs { + EC_BABEL_MEMORY = BABEL_FERR_START, + EC_BABEL_PACKET, + EC_BABEL_CONFIG, + EC_BABEL_ROUTE, +}; + +extern void babel_error_init(void); + +#endif diff --git a/babeld/babel_filter.c b/babeld/babel_filter.c new file mode 100644 index 0000000..f49fee8 --- /dev/null +++ b/babeld/babel_filter.c @@ -0,0 +1,107 @@ +/* +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. +*/ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include "babel_filter.h" +#include "vty.h" +#include "filter.h" +#include "log.h" +#include "plist.h" +#include "distribute.h" +#include "util.h" + +int +babel_filter(int output, const unsigned char *prefix, unsigned short plen, + unsigned int ifindex) +{ + struct interface *ifp = if_lookup_by_index(ifindex, VRF_DEFAULT); + babel_interface_nfo *babel_ifp = ifp ? babel_get_if_nfo(ifp) : NULL; + struct prefix p; + struct distribute *dist = NULL; + struct access_list *alist; + struct prefix_list *plist; + int distribute; + struct babel *babel; + afi_t family; + + p.family = v4mapped(prefix) ? AF_INET : AF_INET6; + p.prefixlen = v4mapped(prefix) ? plen - 96 : plen; + if (p.family == AF_INET) { + uchar_to_inaddr(&p.u.prefix4, prefix); + distribute = output ? DISTRIBUTE_V4_OUT : DISTRIBUTE_V4_IN; + family = AFI_IP; + } else { + uchar_to_in6addr(&p.u.prefix6, prefix); + distribute = output ? DISTRIBUTE_V6_OUT : DISTRIBUTE_V6_IN; + family = AFI_IP6; + } + + if (babel_ifp != NULL && babel_ifp->list[distribute]) { + if (access_list_apply (babel_ifp->list[distribute], &p) + == FILTER_DENY) { + debugf(BABEL_DEBUG_FILTER, + "%pFX filtered by distribute %s", + &p, output ? "out" : "in"); + return INFINITY; + } + } + if (babel_ifp != NULL && babel_ifp->prefix[distribute]) { + if (prefix_list_apply (babel_ifp->prefix[distribute], &p) + == PREFIX_DENY) { + debugf(BABEL_DEBUG_FILTER, "%pFX filtered by distribute %s", + &p, output ? "out" : "in"); + return INFINITY; + } + } + + /* All interface filter check. */ + babel = babel_lookup(); + if (babel) + dist = distribute_lookup (babel->distribute_ctx, NULL); + if (dist) { + if (dist->list[distribute]) { + alist = access_list_lookup (family, dist->list[distribute]); + + if (alist) { + if (access_list_apply (alist, &p) == FILTER_DENY) { + debugf(BABEL_DEBUG_FILTER,"%pFX filtered by distribute %s", + &p, output ? "out" : "in"); + return INFINITY; + } + } + } + if (dist->prefix[distribute]) { + plist = prefix_list_lookup (family, dist->prefix[distribute]); + if (plist) { + if (prefix_list_apply (plist, &p) == PREFIX_DENY) { + debugf(BABEL_DEBUG_FILTER,"%pFX filtered by distribute %s", + &p, output ? "out" : "in"); + return INFINITY; + } + } + } + } + return 0; +} diff --git a/babeld/babel_filter.h b/babeld/babel_filter.h new file mode 100644 index 0000000..b88b18d --- /dev/null +++ b/babeld/babel_filter.h @@ -0,0 +1,33 @@ +/* +Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. +*/ + +#ifndef BABELD_BABEL_FILTER_H +#define BABELD_BABEL_FILTER_H + +#include <zebra.h> +#include "prefix.h" +#include "babel_interface.h" + +int babel_filter(int output, const unsigned char *prefix, unsigned short plen, + unsigned int index); + +#endif /* BABELD_BABEL_FILTER_H */ diff --git a/babeld/babel_interface.c b/babeld/babel_interface.c new file mode 100644 index 0000000..00fb58e --- /dev/null +++ b/babeld/babel_interface.c @@ -0,0 +1,1421 @@ +/* +Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. +*/ + +#include <zebra.h> +#include "memory.h" +#include "log.h" +#include "command.h" +#include "prefix.h" +#include "vector.h" +#include "distribute.h" +#include "lib_errors.h" +#include "network.h" + +#include "babel_main.h" +#include "util.h" +#include "kernel.h" +#include "babel_interface.h" +#include "message.h" +#include "route.h" +#include "babel_zebra.h" +#include "neighbour.h" +#include "route.h" +#include "xroute.h" +#include "babel_errors.h" + +DEFINE_MTYPE_STATIC(BABELD, BABEL_IF, "Babel Interface"); + +#define IS_ENABLE(ifp) (babel_enable_if_lookup(ifp->name) >= 0) + +static int babel_enable_if_lookup (const char *ifname); +static int babel_enable_if_add (const char *ifname); +static int babel_enable_if_delete (const char *ifname); +static int interface_recalculate(struct interface *ifp); +static int interface_reset(struct interface *ifp); +static int babel_if_new_hook (struct interface *ifp); +static int babel_if_delete_hook (struct interface *ifp); +static int interface_config_write (struct vty *vty); +static babel_interface_nfo * babel_interface_allocate (void); +static void babel_interface_free (babel_interface_nfo *bi); + + +static vector babel_enable_if; /* enable interfaces (by cmd). */ + +int babel_ifp_up(struct interface *ifp) +{ + debugf(BABEL_DEBUG_IF, "receive a 'interface up'"); + + interface_recalculate(ifp); + return 0; +} + +int +babel_ifp_down(struct interface *ifp) +{ + debugf(BABEL_DEBUG_IF, "receive a 'interface down'"); + + if (ifp == NULL) { + return 0; + } + + interface_reset(ifp); + return 0; +} + +int babel_ifp_create (struct interface *ifp) +{ + debugf(BABEL_DEBUG_IF, "receive a 'interface add'"); + + interface_recalculate(ifp); + + return 0; + } + +int +babel_ifp_destroy(struct interface *ifp) +{ + debugf(BABEL_DEBUG_IF, "receive a 'interface delete'"); + + if (IS_ENABLE(ifp)) + interface_reset(ifp); + + return 0; +} + +int +babel_interface_address_add (ZAPI_CALLBACK_ARGS) +{ + 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, vrf_id); + + 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) { + flog_err(EC_BABEL_MEMORY, "not enough 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 (ZAPI_CALLBACK_ARGS) +{ + babel_interface_nfo *babel_ifp; + struct connected *ifc; + struct prefix *prefix; + + debugf(BABEL_DEBUG_IF, "receive a 'interface address delete'"); + + ifc = zebra_interface_address_read (ZEBRA_INTERFACE_ADDRESS_DELETE, + zclient->ibuf, vrf_id); + + 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, IPV4_MAX_BYTELEN) + == 0) { + free(babel_ifp->ipv4); + babel_ifp->ipv4 = NULL; + } + } + + send_request(ifc->ifp, NULL, 0); + send_update(ifc->ifp, 0, NULL, 0); + + connected_free(&ifc); + 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, VRF_DEFAULT); + if (ifp != NULL) + interface_recalculate(ifp); + + return 1; +} + +/* Delete interface from babel_enable_if. */ +static int +babel_enable_if_delete (const char *ifname) +{ + int babel_enable_if_index; + char *str; + struct interface *ifp = NULL; + + babel_enable_if_index = babel_enable_if_lookup (ifname); + if (babel_enable_if_index < 0) + return -1; + + str = vector_slot (babel_enable_if, babel_enable_if_index); + free (str); + vector_unset (babel_enable_if, babel_enable_if_index); + + ifp = if_lookup_by_name(ifname, VRF_DEFAULT); + if (ifp != NULL) + interface_reset(ifp); + + return 1; +} + +/* [Babel Command] Babel enable on specified interface or matched network. */ +DEFUN (babel_network, + babel_network_cmd, + "network IF_OR_ADDR", + "Enable Babel protocol on specified interface or network.\n" + "Interface or address\n") +{ + int ret; + struct prefix p; + + ret = str2prefix (argv[1]->arg, &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[1]->arg); + + if (ret < 0) { + vty_out (vty, "There is same network configuration %s\n", + argv[1]->arg); + return CMD_WARNING; + } + + return CMD_SUCCESS; +} + +/* [Babel Command] Babel enable on specified interface or matched network. */ +DEFUN (no_babel_network, + no_babel_network_cmd, + "no network IF_OR_ADDR", + NO_STR + "Disable Babel protocol on specified interface or network.\n" + "Interface or address\n") +{ + int ret; + struct prefix p; + + ret = str2prefix (argv[2]->arg, &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[2]->arg); + + if (ret < 0) { + vty_out (vty, "can't find network %s\n",argv[2]->arg); + return CMD_WARNING_CONFIG_FAILED; + } + + return CMD_SUCCESS; +} + +/* There are a number of interface parameters that must be changed when + an interface becomes wired/wireless. In Quagga, they cannot be + configured separately. */ + +static void +babel_set_wired_internal(babel_interface_nfo *babel_ifp, int wired) +{ + if(wired) { + babel_ifp->flags |= BABEL_IF_WIRED; + babel_ifp->flags |= BABEL_IF_SPLIT_HORIZON; + babel_ifp->cost = BABEL_DEFAULT_RXCOST_WIRED; + babel_ifp->channel = BABEL_IF_CHANNEL_NONINTERFERING; + babel_ifp->flags &= ~BABEL_IF_LQ; + } else { + babel_ifp->flags &= ~BABEL_IF_WIRED; + babel_ifp->flags &= ~BABEL_IF_SPLIT_HORIZON; + babel_ifp->cost = BABEL_DEFAULT_RXCOST_WIRELESS; + babel_ifp->channel = BABEL_IF_CHANNEL_INTERFERING; + babel_ifp->flags |= BABEL_IF_LQ; + } + +} + +/* [Interface Command] Tell the interface is wire. */ +DEFUN (babel_set_wired, + babel_set_wired_cmd, + "babel wired", + "Babel interface commands\n" + "Enable wired optimizations\n") +{ + VTY_DECLVAR_CONTEXT(interface, ifp); + babel_interface_nfo *babel_ifp; + + babel_ifp = babel_get_if_nfo(ifp); + + assert (babel_ifp != NULL); + babel_set_wired_internal(babel_ifp, 1); + return CMD_SUCCESS; +} + +/* [Interface Command] Tell the interface is wireless (default). */ +DEFUN (babel_set_wireless, + babel_set_wireless_cmd, + "babel wireless", + "Babel interface commands\n" + "Disable wired optimizations (assume wireless)\n") +{ + VTY_DECLVAR_CONTEXT(interface, ifp); + babel_interface_nfo *babel_ifp; + + babel_ifp = babel_get_if_nfo(ifp); + + assert (babel_ifp != NULL); + babel_set_wired_internal(babel_ifp, 0); + return CMD_SUCCESS; +} + +/* [Interface Command] Enable split horizon. */ +DEFUN (babel_split_horizon, + babel_split_horizon_cmd, + "babel split-horizon", + "Babel interface commands\n" + "Enable split horizon processing\n") +{ + VTY_DECLVAR_CONTEXT(interface, ifp); + babel_interface_nfo *babel_ifp; + + babel_ifp = babel_get_if_nfo(ifp); + + assert (babel_ifp != NULL); + babel_ifp->flags |= BABEL_IF_SPLIT_HORIZON; + return CMD_SUCCESS; +} + +/* [Interface Command] Disable split horizon (default). */ +DEFUN (no_babel_split_horizon, + no_babel_split_horizon_cmd, + "no babel split-horizon", + NO_STR + "Babel interface commands\n" + "Disable split horizon processing\n") +{ + VTY_DECLVAR_CONTEXT(interface, ifp); + babel_interface_nfo *babel_ifp; + + babel_ifp = babel_get_if_nfo(ifp); + + assert (babel_ifp != NULL); + babel_ifp->flags &= ~BABEL_IF_SPLIT_HORIZON; + return CMD_SUCCESS; +} + +/* [Interface Command]. */ +DEFUN (babel_set_hello_interval, + babel_set_hello_interval_cmd, + "babel hello-interval (20-655340)", + "Babel interface commands\n" + "Time between scheduled hellos\n" + "Milliseconds\n") +{ + VTY_DECLVAR_CONTEXT(interface, ifp); + babel_interface_nfo *babel_ifp; + int interval; + + interval = strtoul(argv[2]->arg, NULL, 10); + + babel_ifp = babel_get_if_nfo(ifp); + assert (babel_ifp != NULL); + + babel_ifp->hello_interval = interval; + return CMD_SUCCESS; +} + +/* [Interface Command]. */ +DEFUN (babel_set_update_interval, + babel_set_update_interval_cmd, + "babel update-interval (20-655340)", + "Babel interface commands\n" + "Time between scheduled updates\n" + "Milliseconds\n") +{ + VTY_DECLVAR_CONTEXT(interface, ifp); + babel_interface_nfo *babel_ifp; + int interval; + + interval = strtoul(argv[2]->arg, NULL, 10); + + babel_ifp = babel_get_if_nfo(ifp); + assert (babel_ifp != NULL); + + babel_ifp->update_interval = interval; + return CMD_SUCCESS; +} + +DEFUN (babel_set_rxcost, + babel_set_rxcost_cmd, + "babel rxcost (1-65534)", + "Babel interface commands\n" + "Rxcost multiplier\n" + "Units\n") +{ + VTY_DECLVAR_CONTEXT(interface, ifp); + babel_interface_nfo *babel_ifp; + int rxcost; + + rxcost = strtoul(argv[2]->arg, NULL, 10); + + babel_ifp = babel_get_if_nfo(ifp); + assert (babel_ifp != NULL); + + babel_ifp->cost = rxcost; + return CMD_SUCCESS; +} + +DEFUN (babel_set_rtt_decay, + babel_set_rtt_decay_cmd, + "babel rtt-decay (1-256)", + "Babel interface commands\n" + "Decay factor for exponential moving average of RTT samples\n" + "Units of 1/256\n") +{ + VTY_DECLVAR_CONTEXT(interface, ifp); + babel_interface_nfo *babel_ifp; + int decay; + + decay = strtoul(argv[2]->arg, NULL, 10); + + babel_ifp = babel_get_if_nfo(ifp); + assert (babel_ifp != NULL); + + babel_ifp->rtt_decay = decay; + return CMD_SUCCESS; +} + +DEFUN (babel_set_rtt_min, + babel_set_rtt_min_cmd, + "babel rtt-min (1-65535)", + "Babel interface commands\n" + "Minimum RTT starting for increasing cost\n" + "Milliseconds\n") +{ + VTY_DECLVAR_CONTEXT(interface, ifp); + babel_interface_nfo *babel_ifp; + int rtt; + + rtt = strtoul(argv[2]->arg, NULL, 10); + + babel_ifp = babel_get_if_nfo(ifp); + assert (babel_ifp != NULL); + + /* The value is entered in milliseconds but stored as microseconds. */ + babel_ifp->rtt_min = rtt * 1000; + return CMD_SUCCESS; +} + +DEFUN (babel_set_rtt_max, + babel_set_rtt_max_cmd, + "babel rtt-max (1-65535)", + "Babel interface commands\n" + "Maximum RTT\n" + "Milliseconds\n") +{ + VTY_DECLVAR_CONTEXT(interface, ifp); + babel_interface_nfo *babel_ifp; + int rtt; + + rtt = strtoul(argv[2]->arg, NULL, 10); + + babel_ifp = babel_get_if_nfo(ifp); + assert (babel_ifp != NULL); + + /* The value is entered in milliseconds but stored as microseconds. */ + babel_ifp->rtt_max = rtt * 1000; + return CMD_SUCCESS; +} + +DEFUN (babel_set_max_rtt_penalty, + babel_set_max_rtt_penalty_cmd, + "babel max-rtt-penalty (0-65535)", + "Babel interface commands\n" + "Maximum additional cost due to RTT\n" + "Milliseconds\n") +{ + VTY_DECLVAR_CONTEXT(interface, ifp); + babel_interface_nfo *babel_ifp; + int penalty; + + penalty = strtoul(argv[2]->arg, NULL, 10); + + babel_ifp = babel_get_if_nfo(ifp); + assert (babel_ifp != NULL); + + babel_ifp->max_rtt_penalty = penalty; + return CMD_SUCCESS; +} + +DEFUN (babel_set_enable_timestamps, + babel_set_enable_timestamps_cmd, + "babel enable-timestamps", + "Babel interface commands\n" + "Enable timestamps\n") +{ + VTY_DECLVAR_CONTEXT(interface, ifp); + babel_interface_nfo *babel_ifp; + + babel_ifp = babel_get_if_nfo(ifp); + assert (babel_ifp != NULL); + + babel_ifp->flags |= BABEL_IF_TIMESTAMPS; + return CMD_SUCCESS; +} + +DEFUN (no_babel_set_enable_timestamps, + no_babel_set_enable_timestamps_cmd, + "no babel enable-timestamps", + NO_STR + "Babel interface commands\n" + "Disable timestamps\n") +{ + VTY_DECLVAR_CONTEXT(interface, ifp); + babel_interface_nfo *babel_ifp; + + babel_ifp = babel_get_if_nfo(ifp); + assert (babel_ifp != NULL); + + babel_ifp->flags &= ~BABEL_IF_TIMESTAMPS; + return CMD_SUCCESS; +} + +DEFUN (babel_set_channel, + babel_set_channel_cmd, + "babel channel (1-254)", + "Babel interface commands\n" + "Channel number for diversity routing\n" + "Number\n") +{ + VTY_DECLVAR_CONTEXT(interface, ifp); + babel_interface_nfo *babel_ifp; + int channel; + + channel = strtoul(argv[2]->arg, NULL, 10); + + babel_ifp = babel_get_if_nfo(ifp); + assert (babel_ifp != NULL); + + babel_ifp->channel = channel; + return CMD_SUCCESS; +} + +DEFUN (babel_set_channel_interfering, + babel_set_channel_interfering_cmd, + "babel channel interfering", + "Babel interface commands\n" + "Channel number for diversity routing\n" + "Mark channel as interfering\n") +{ + VTY_DECLVAR_CONTEXT(interface, ifp); + babel_interface_nfo *babel_ifp; + + babel_ifp = babel_get_if_nfo(ifp); + assert (babel_ifp != NULL); + + babel_ifp->channel = BABEL_IF_CHANNEL_INTERFERING; + return CMD_SUCCESS; +} + +DEFUN (babel_set_channel_noninterfering, + babel_set_channel_noninterfering_cmd, + "babel channel noninterfering", + "Babel interface commands\n" + "Channel number for diversity routing\n" + "Mark channel as noninterfering\n") +{ + VTY_DECLVAR_CONTEXT(interface, ifp); + babel_interface_nfo *babel_ifp; + + babel_ifp = babel_get_if_nfo(ifp); + assert (babel_ifp != NULL); + + babel_ifp->channel = BABEL_IF_CHANNEL_NONINTERFERING; + return CMD_SUCCESS; +} + +/* This should be no more than half the hello interval, so that hellos + aren't sent late. The result is in milliseconds. */ +unsigned +jitter(babel_interface_nfo *babel_ifp, int urgent) +{ + unsigned interval = babel_ifp->hello_interval; + if(urgent) + interval = MIN(interval, 100); + else + interval = MIN(interval, 4000); + return roughly(interval) / 4; +} + +unsigned +update_jitter(babel_interface_nfo *babel_ifp, int urgent) +{ + unsigned interval = babel_ifp->hello_interval; + if(urgent) + interval = MIN(interval, 100); + else + interval = MIN(interval, 4000); + return roughly(interval); +} + +/* calculate babeld's specific datas of an interface (change when the interface + change) */ +static int +interface_recalculate(struct interface *ifp) +{ + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + unsigned char *tmp = NULL; + int mtu, rc; + struct ipv6_mreq mreq; + + if (!IS_ENABLE(ifp)) + return -1; + + if (!if_is_operative(ifp) || !CHECK_FLAG(ifp->flags, IFF_RUNNING)) { + interface_reset(ifp); + return -1; + } + + babel_ifp->flags |= BABEL_IF_IS_UP; + + mtu = MIN(ifp->mtu, ifp->mtu6); + + /* We need to be able to fit at least two messages into a packet, + so MTUs below 116 require lower layer fragmentation. */ + /* In IPv6, the minimum MTU is 1280, and every host must be able + to reassemble up to 1500 bytes, but I'd rather not rely on this. */ + if(mtu < 128) { + debugf(BABEL_DEBUG_IF, "Suspiciously low MTU %d on interface %s (%d).", + mtu, ifp->name, ifp->ifindex); + mtu = 128; + } + + /* 4 for Babel header; 40 for IPv6 header, 8 for UDP header, 12 for good luck. */ + babel_ifp->bufsize = mtu - 4 - 60; + tmp = babel_ifp->sendbuf; + babel_ifp->sendbuf = realloc(babel_ifp->sendbuf, babel_ifp->bufsize); + if(babel_ifp->sendbuf == NULL) { + flog_err(EC_BABEL_MEMORY, "Couldn't reallocate sendbuf."); + free(tmp); + babel_ifp->bufsize = 0; + return -1; + } + tmp = NULL; + + rc = resize_receive_buffer(mtu); + if(rc < 0) + zlog_warn("couldn't resize receive buffer for interface %s (%d) (%d bytes).", + ifp->name, ifp->ifindex, mtu); + + memset(&mreq, 0, sizeof(mreq)); + memcpy(&mreq.ipv6mr_multiaddr, protocol_group, 16); + mreq.ipv6mr_interface = ifp->ifindex; + + rc = setsockopt(protocol_socket, IPPROTO_IPV6, IPV6_JOIN_GROUP, + (char*)&mreq, sizeof(mreq)); + if(rc < 0) { + flog_err_sys(EC_LIB_SOCKET, + "setsockopt(IPV6_JOIN_GROUP) on interface '%s': %s", + ifp->name, safe_strerror(errno)); + /* This is probably due to a missing link-local address, + so down this interface, and wait until the main loop + tries to up it again. */ + interface_reset(ifp); + return -1; + } + + set_timeout(&babel_ifp->hello_timeout, babel_ifp->hello_interval); + set_timeout(&babel_ifp->update_timeout, babel_ifp->update_interval); + send_hello(ifp); + send_request(ifp, NULL, 0); + + update_interface_metric(ifp); + + debugf(BABEL_DEBUG_COMMON, + "Upped interface %s (%s, cost=%d, channel=%d%s).", + ifp->name, + (babel_ifp->flags & BABEL_IF_WIRED) ? "wired" : "wireless", + babel_ifp->cost, + babel_ifp->channel, + babel_ifp->ipv4 ? ", IPv4" : ""); + + if(rc > 0) + send_update(ifp, 0, NULL, 0); + + return 1; +} + +/* Reset the interface as it was new: it's not removed from the interface list, + and may be considered as a upped interface. */ +static int +interface_reset(struct interface *ifp) +{ + int rc; + struct ipv6_mreq mreq; + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + + if (!(babel_ifp->flags & BABEL_IF_IS_UP)) + return 0; + + debugf(BABEL_DEBUG_IF, "interface reset: %s", ifp->name); + babel_ifp->flags &= ~BABEL_IF_IS_UP; + + flush_interface_routes(ifp, 0); + babel_ifp->buffered = 0; + babel_ifp->bufsize = 0; + free(babel_ifp->sendbuf); + babel_ifp->num_buffered_updates = 0; + babel_ifp->update_bufsize = 0; + if(babel_ifp->buffered_updates) + free(babel_ifp->buffered_updates); + babel_ifp->buffered_updates = NULL; + babel_ifp->sendbuf = NULL; + + if(ifp->ifindex > 0) { + memset(&mreq, 0, sizeof(mreq)); + memcpy(&mreq.ipv6mr_multiaddr, protocol_group, 16); + mreq.ipv6mr_interface = ifp->ifindex; + rc = setsockopt(protocol_socket, IPPROTO_IPV6, IPV6_LEAVE_GROUP, + (char*)&mreq, sizeof(mreq)); + if(rc < 0) + flog_err_sys(EC_LIB_SOCKET, + "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 vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT); + struct interface *ifp = NULL; + + FOR_ALL_INTERFACES(vrf, ifp) { + 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(vrf, ifp) { + 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, + IPV6_MAX_BYTELEN) + == 0) + return 1; + } + + return 0; +} + +static void +show_babel_interface_sub (struct vty *vty, struct interface *ifp) +{ + int is_up; + babel_interface_nfo *babel_ifp; + + vty_out (vty, "%s is %s\n", ifp->name, + ((is_up = if_is_operative(ifp)) ? "up" : "down")); + vty_out (vty, " ifindex %u, MTU %u bytes %s\n", + ifp->ifindex, MIN(ifp->mtu, ifp->mtu6), if_flag_dump(ifp->flags)); + + if (!IS_ENABLE(ifp)) + { + vty_out (vty, " Babel protocol is not enabled on this interface\n"); + return; + } + if (!is_up) + { + vty_out (vty, + " Babel protocol is enabled, but not running on this interface\n"); + return; + } + babel_ifp = babel_get_if_nfo (ifp); + vty_out (vty, " Babel protocol is running on this interface\n"); + vty_out (vty, " Operating mode is \"%s\"\n", + CHECK_FLAG(babel_ifp->flags, BABEL_IF_WIRED) ? "wired" : "wireless"); + vty_out (vty, " Split horizon mode is %s\n", + CHECK_FLAG(babel_ifp->flags, BABEL_IF_SPLIT_HORIZON) ? "On" : "Off"); + vty_out (vty, " Hello interval is %u ms\n", babel_ifp->hello_interval); + vty_out (vty, " Update interval is %u ms\n", babel_ifp->update_interval); + vty_out (vty, " Rxcost multiplier is %u\n", babel_ifp->cost); +} + +DEFUN (show_babel_interface, + show_babel_interface_cmd, + "show babel interface [IFNAME]", + SHOW_STR + "Babel information\n" + "Interface information\n" + "Interface\n") +{ + struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT); + struct interface *ifp; + + if (argc == 3) + { + FOR_ALL_INTERFACES (vrf, ifp) + show_babel_interface_sub (vty, ifp); + return CMD_SUCCESS; + } + if ((ifp = if_lookup_by_name (argv[3]->arg, VRF_DEFAULT)) == NULL) + { + vty_out (vty, "No such interface name\n"); + return CMD_WARNING; + } + show_babel_interface_sub (vty, ifp); + return CMD_SUCCESS; +} + +static void +show_babel_neighbour_sub (struct vty *vty, struct neighbour *neigh) +{ + vty_out (vty, + "Neighbour %s dev %s reach %04x rxcost %d txcost %d rtt %s rttcost %d%s.\n", + format_address(neigh->address), + neigh->ifp->name, + neigh->reach, + neighbour_rxcost(neigh), + neigh->txcost, + format_thousands(neigh->rtt), + neighbour_rttcost(neigh), + if_up(neigh->ifp) ? "" : " (down)"); +} + +DEFUN (show_babel_neighbour, + show_babel_neighbour_cmd, + "show babel neighbor [IFNAME]", + SHOW_STR + "Babel information\n" + "Print neighbors\n" + "Interface\n") +{ + struct neighbour *neigh; + struct interface *ifp; + + if (argc == 3) { + FOR_ALL_NEIGHBOURS(neigh) { + show_babel_neighbour_sub(vty, neigh); + } + return CMD_SUCCESS; + } + if ((ifp = if_lookup_by_name (argv[3]->arg, VRF_DEFAULT)) == NULL) + { + vty_out (vty, "No such interface name\n"); + return CMD_WARNING; + } + FOR_ALL_NEIGHBOURS(neigh) { + if(ifp->ifindex == neigh->ifp->ifindex) { + show_babel_neighbour_sub(vty, neigh); + } + } + return CMD_SUCCESS; +} + +static int +babel_prefix_eq(struct prefix *prefix, unsigned char *p, int plen) +{ + if(prefix->family == AF_INET6) { + if (prefix->prefixlen != plen + || memcmp(&prefix->u.prefix6, p, IPV6_MAX_BYTELEN) != 0) + return 0; + } else if(prefix->family == AF_INET) { + if (plen < 96 || !v4mapped(p) || prefix->prefixlen != plen - 96 + || memcmp(&prefix->u.prefix4, p + 12, IPV4_MAX_BYTELEN) != 0) + return 0; + } else { + return 0; + } + + return 1; +} + +static void +show_babel_routes_sub(struct babel_route *route, struct vty *vty, + struct prefix *prefix) +{ + const unsigned char *nexthop = + memcmp(route->nexthop, route->neigh->address, IPV6_MAX_BYTELEN) + == 0 + ? NULL + : route->nexthop; + char channels[100]; + + if (prefix + && !babel_prefix_eq(prefix, route->src->prefix, route->src->plen)) + return; + + if (route->channels[0] == 0) + channels[0] = '\0'; + else { + int k, j = 0; + snprintf(channels, sizeof(channels), " chan ("); + j = strlen(channels); + for (k = 0; k < DIVERSITY_HOPS; k++) { + if (route->channels[k] == 0) + break; + if (k > 0) + channels[j++] = ','; + snprintf(channels + j, 100 - j, "%u", + route->channels[k]); + j = strlen(channels); + } + snprintf(channels + j, 100 - j, ")"); + if (k == 0) + channels[0] = '\0'; + } + + vty_out (vty, + "%s metric %d refmetric %d id %s seqno %d%s age %d via %s neigh %s%s%s%s\n", + format_prefix(route->src->prefix, route->src->plen), + route_metric(route), route->refmetric, + format_eui64(route->src->id), + (int)route->seqno, + channels, + (int)(babel_now.tv_sec - route->time), + route->neigh->ifp->name, + format_address(route->neigh->address), + nexthop ? " nexthop " : "", + nexthop ? format_address(nexthop) : "", + route->installed ? " (installed)" : route_feasible(route) ? " (feasible)" : ""); +} + +static void +show_babel_xroutes_sub (struct xroute *xroute, struct vty *vty, + struct prefix *prefix) +{ + if(prefix && !babel_prefix_eq(prefix, xroute->prefix, xroute->plen)) + return; + + vty_out (vty, "%s metric %d (exported)\n", + format_prefix(xroute->prefix, xroute->plen), + xroute->metric); +} + +DEFUN (show_babel_route, + show_babel_route_cmd, + "show babel route", + SHOW_STR + "Babel information\n" + "Babel internal routing table\n") +{ + struct route_stream *routes = NULL; + struct xroute_stream *xroutes = NULL; + routes = route_stream(0); + if(routes) { + while(1) { + struct babel_route *route = route_stream_next(routes); + if(route == NULL) + break; + show_babel_routes_sub(route, vty, NULL); + } + route_stream_done(routes); + } else { + flog_err(EC_BABEL_MEMORY, "Couldn't allocate route stream."); + } + xroutes = xroute_stream(); + if(xroutes) { + while(1) { + struct xroute *xroute = xroute_stream_next(xroutes); + if(xroute == NULL) + break; + show_babel_xroutes_sub(xroute, vty, NULL); + } + xroute_stream_done(xroutes); + } else { + flog_err(EC_BABEL_MEMORY, "Couldn't allocate route stream."); + } + return CMD_SUCCESS; +} + +DEFUN (show_babel_route_prefix, + show_babel_route_prefix_cmd, + "show babel route <A.B.C.D/M|X:X::X:X/M>", + SHOW_STR + "Babel information\n" + "Babel internal routing table\n" + "IPv4 prefix <network>/<length>\n" + "IPv6 prefix <network>/<length>\n") +{ + struct route_stream *routes = NULL; + struct xroute_stream *xroutes = NULL; + struct prefix prefix; + int ret; + + ret = str2prefix(argv[3]->arg, &prefix); + if(ret == 0) { + vty_out (vty, "%% Malformed address\n"); + return CMD_WARNING; + } + + routes = route_stream(0); + if(routes) { + while(1) { + struct babel_route *route = route_stream_next(routes); + if(route == NULL) + break; + show_babel_routes_sub(route, vty, &prefix); + } + route_stream_done(routes); + } else { + flog_err(EC_BABEL_MEMORY, "Couldn't allocate route stream."); + } + xroutes = xroute_stream(); + if(xroutes) { + while(1) { + struct xroute *xroute = xroute_stream_next(xroutes); + if(xroute == NULL) + break; + show_babel_xroutes_sub(xroute, vty, &prefix); + } + xroute_stream_done(xroutes); + } else { + flog_err(EC_BABEL_MEMORY, "Couldn't allocate route stream."); + } + return CMD_SUCCESS; +} + + +DEFUN (show_babel_route_addr, + show_babel_route_addr_cmd, + "show babel route A.B.C.D", + SHOW_STR + "Babel information\n" + "Babel internal routing table\n" + "IPv4 address <network>/<length>\n") +{ + struct in_addr addr; + char buf[INET_ADDRSTRLEN + 8]; + char buf1[INET_ADDRSTRLEN + 8]; + struct route_stream *routes = NULL; + struct xroute_stream *xroutes = NULL; + struct prefix prefix; + int ret; + + ret = inet_aton (argv[3]->arg, &addr); + if (ret <= 0) { + vty_out (vty, "%% Malformed address\n"); + return CMD_WARNING; + } + + /* Quagga has no convenient prefix constructors. */ + snprintf(buf, sizeof(buf), "%s/%d", + inet_ntop(AF_INET, &addr, buf1, sizeof(buf1)), 32); + + ret = str2prefix(buf, &prefix); + if (ret == 0) { + vty_out (vty, "%% Parse error -- this shouldn't happen\n"); + return CMD_WARNING; + } + + routes = route_stream(0); + if(routes) { + while(1) { + struct babel_route *route = route_stream_next(routes); + if(route == NULL) + break; + show_babel_routes_sub(route, vty, &prefix); + } + route_stream_done(routes); + } else { + flog_err(EC_BABEL_MEMORY, "Couldn't allocate route stream."); + } + xroutes = xroute_stream(); + if(xroutes) { + while(1) { + struct xroute *xroute = xroute_stream_next(xroutes); + if(xroute == NULL) + break; + show_babel_xroutes_sub(xroute, vty, &prefix); + } + xroute_stream_done(xroutes); + } else { + flog_err(EC_BABEL_MEMORY, "Couldn't allocate route stream."); + } + return CMD_SUCCESS; +} + +DEFUN (show_babel_route_addr6, + show_babel_route_addr6_cmd, + "show babel route X:X::X:X", + SHOW_STR + "Babel information\n" + "Babel internal routing table\n" + "IPv6 address <network>/<length>\n") +{ + struct in6_addr addr; + char buf1[INET6_ADDRSTRLEN]; + char buf[INET6_ADDRSTRLEN + 8]; + struct route_stream *routes = NULL; + struct xroute_stream *xroutes = NULL; + struct prefix prefix; + int ret; + + ret = inet_pton (AF_INET6, argv[3]->arg, &addr); + if (ret <= 0) { + vty_out (vty, "%% Malformed address\n"); + return CMD_WARNING; + } + + /* Quagga has no convenient prefix constructors. */ + snprintf(buf, sizeof(buf), "%s/%d", + inet_ntop(AF_INET6, &addr, buf1, sizeof(buf1)), 128); + + ret = str2prefix(buf, &prefix); + if (ret == 0) { + vty_out (vty, "%% Parse error -- this shouldn't happen\n"); + return CMD_WARNING; + } + + routes = route_stream(0); + if(routes) { + while(1) { + struct babel_route *route = route_stream_next(routes); + if(route == NULL) + break; + show_babel_routes_sub(route, vty, &prefix); + } + route_stream_done(routes); + } else { + flog_err(EC_BABEL_MEMORY, "Couldn't allocate route stream."); + } + xroutes = xroute_stream(); + if(xroutes) { + while(1) { + struct xroute *xroute = xroute_stream_next(xroutes); + if(xroute == NULL) + break; + show_babel_xroutes_sub(xroute, vty, &prefix); + } + xroute_stream_done(xroutes); + } else { + flog_err(EC_BABEL_MEMORY, "Couldn't allocate route stream."); + } + return CMD_SUCCESS; +} + +DEFUN (show_babel_parameters, + show_babel_parameters_cmd, + "show babel parameters", + SHOW_STR + "Babel information\n" + "Configuration information\n") +{ + struct babel *babel_ctx; + + vty_out (vty, " -- Babel running configuration --\n"); + show_babel_main_configuration(vty); + + babel_ctx = babel_lookup(); + if (babel_ctx) { + vty_out (vty, " -- distribution lists --\n"); + config_show_distribute(vty, babel_ctx->distribute_ctx); + } + return CMD_SUCCESS; +} + +void +babel_if_init(void) +{ + /* initialize interface list */ + hook_register_prio(if_add, 0, babel_if_new_hook); + hook_register_prio(if_del, 0, babel_if_delete_hook); + + babel_enable_if = vector_init (1); + + /* install interface node and commands */ + if_cmd_init(interface_config_write); + + install_element(BABEL_NODE, &babel_network_cmd); + install_element(BABEL_NODE, &no_babel_network_cmd); + install_element(INTERFACE_NODE, &babel_split_horizon_cmd); + install_element(INTERFACE_NODE, &no_babel_split_horizon_cmd); + install_element(INTERFACE_NODE, &babel_set_wired_cmd); + install_element(INTERFACE_NODE, &babel_set_wireless_cmd); + install_element(INTERFACE_NODE, &babel_set_hello_interval_cmd); + install_element(INTERFACE_NODE, &babel_set_update_interval_cmd); + install_element(INTERFACE_NODE, &babel_set_rxcost_cmd); + install_element(INTERFACE_NODE, &babel_set_channel_cmd); + install_element(INTERFACE_NODE, &babel_set_rtt_decay_cmd); + install_element(INTERFACE_NODE, &babel_set_rtt_min_cmd); + install_element(INTERFACE_NODE, &babel_set_rtt_max_cmd); + install_element(INTERFACE_NODE, &babel_set_max_rtt_penalty_cmd); + install_element(INTERFACE_NODE, &babel_set_enable_timestamps_cmd); + install_element(INTERFACE_NODE, &no_babel_set_enable_timestamps_cmd); + install_element(INTERFACE_NODE, &babel_set_channel_interfering_cmd); + install_element(INTERFACE_NODE, &babel_set_channel_noninterfering_cmd); + + /* "show babel ..." commands */ + install_element(VIEW_NODE, &show_babel_interface_cmd); + install_element(VIEW_NODE, &show_babel_neighbour_cmd); + install_element(VIEW_NODE, &show_babel_route_cmd); + install_element(VIEW_NODE, &show_babel_route_prefix_cmd); + install_element(VIEW_NODE, &show_babel_route_addr_cmd); + install_element(VIEW_NODE, &show_babel_route_addr6_cmd); + install_element(VIEW_NODE, &show_babel_parameters_cmd); +} + +/* hooks: functions called respectively when struct interface is + created or deleted. */ +static int +babel_if_new_hook (struct interface *ifp) +{ + ifp->info = babel_interface_allocate(); + return 0; +} + +static int +babel_if_delete_hook (struct interface *ifp) +{ + babel_interface_free(ifp->info); + ifp->info = NULL; + return 0; +} + +/* Output an "interface" section for each of the known interfaces with +babeld-specific statement lines where appropriate. */ +static int +interface_config_write (struct vty *vty) +{ + struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT); + struct interface *ifp; + int write = 0; + + FOR_ALL_INTERFACES (vrf, ifp) { + if_vty_config_start(vty, ifp); + if (ifp->desc) + vty_out (vty, " description %s\n",ifp->desc); + babel_interface_nfo *babel_ifp = babel_get_if_nfo (ifp); + /* wireless is the default*/ + if (CHECK_FLAG (babel_ifp->flags, BABEL_IF_WIRED)) + { + vty_out (vty, " babel wired\n"); + write++; + } + if (babel_ifp->hello_interval != BABEL_DEFAULT_HELLO_INTERVAL) + { + vty_out (vty, " babel hello-interval %u\n", + babel_ifp->hello_interval); + write++; + } + if (babel_ifp->update_interval != BABEL_DEFAULT_UPDATE_INTERVAL) + { + vty_out (vty, " babel update-interval %u\n", + babel_ifp->update_interval); + write++; + } + if (CHECK_FLAG(babel_ifp->flags, BABEL_IF_TIMESTAMPS)) { + vty_out(vty, " babel enable-timestamps\n"); + write++; + } + if (babel_ifp->max_rtt_penalty != BABEL_DEFAULT_MAX_RTT_PENALTY) { + vty_out(vty, " babel max-rtt-penalty %u\n", + babel_ifp->max_rtt_penalty); + write++; + } + if (babel_ifp->rtt_decay != BABEL_DEFAULT_RTT_DECAY) { + vty_out(vty, " babel rtt-decay %u\n", babel_ifp->rtt_decay); + write++; + } + if (babel_ifp->rtt_min != BABEL_DEFAULT_RTT_MIN) { + vty_out(vty, " babel rtt-min %u\n", babel_ifp->rtt_min / 1000); + write++; + } + if (babel_ifp->rtt_max != BABEL_DEFAULT_RTT_MAX) { + vty_out(vty, " babel rtt-max %u\n", babel_ifp->rtt_max / 1000); + write++; + } + /* Some parameters have different defaults for wired/wireless. */ + if (CHECK_FLAG (babel_ifp->flags, BABEL_IF_WIRED)) { + if (!CHECK_FLAG (babel_ifp->flags, BABEL_IF_SPLIT_HORIZON)) { + vty_out (vty, " no babel split-horizon\n"); + write++; + } + if (babel_ifp->cost != BABEL_DEFAULT_RXCOST_WIRED) { + vty_out (vty, " babel rxcost %u\n", babel_ifp->cost); + write++; + } + if (babel_ifp->channel == BABEL_IF_CHANNEL_INTERFERING) { + vty_out (vty, " babel channel interfering\n"); + write++; + } else if(babel_ifp->channel != BABEL_IF_CHANNEL_NONINTERFERING) { + vty_out (vty, " babel channel %d\n",babel_ifp->channel); + write++; + } + } else { + if (CHECK_FLAG (babel_ifp->flags, BABEL_IF_SPLIT_HORIZON)) { + vty_out (vty, " babel split-horizon\n"); + write++; + } + if (babel_ifp->cost != BABEL_DEFAULT_RXCOST_WIRELESS) { + vty_out (vty, " babel rxcost %u\n", babel_ifp->cost); + write++; + } + if (babel_ifp->channel == BABEL_IF_CHANNEL_NONINTERFERING) { + vty_out (vty, " babel channel noninterfering\n"); + write++; + } else if(babel_ifp->channel != BABEL_IF_CHANNEL_INTERFERING) { + vty_out (vty, " babel channel %d\n",babel_ifp->channel); + write++; + } + } + if_vty_config_end(vty); + write++; + } + return write; +} + +/* Output a "network" statement line for each of the enabled interfaces. */ +int +babel_enable_if_config_write (struct vty * vty) +{ + unsigned int i, lines = 0; + char *str; + + for (i = 0; i < vector_active (babel_enable_if); i++) + if ((str = vector_slot (babel_enable_if, i)) != NULL) + { + vty_out (vty, " network %s\n", str); + lines++; + } + return lines; +} + +/* functions to allocate or free memory for a babel_interface_nfo, filling + needed fields */ +static babel_interface_nfo * +babel_interface_allocate (void) +{ + babel_interface_nfo *babel_ifp; + babel_ifp = XCALLOC(MTYPE_BABEL_IF, sizeof(babel_interface_nfo)); + /* All flags are unset */ + babel_ifp->bucket_time = babel_now.tv_sec; + babel_ifp->bucket = BUCKET_TOKENS_MAX; + babel_ifp->hello_seqno = (frr_weak_random() & 0xFFFF); + babel_ifp->rtt_decay = BABEL_DEFAULT_RTT_DECAY; + babel_ifp->rtt_min = BABEL_DEFAULT_RTT_MIN; + babel_ifp->rtt_max = BABEL_DEFAULT_RTT_MAX; + babel_ifp->max_rtt_penalty = BABEL_DEFAULT_MAX_RTT_PENALTY; + babel_ifp->hello_interval = BABEL_DEFAULT_HELLO_INTERVAL; + babel_ifp->update_interval = BABEL_DEFAULT_UPDATE_INTERVAL; + babel_ifp->channel = BABEL_IF_CHANNEL_INTERFERING; + babel_set_wired_internal(babel_ifp, 0); + + return babel_ifp; +} + +static void +babel_interface_free (babel_interface_nfo *babel_ifp) +{ + XFREE(MTYPE_BABEL_IF, babel_ifp); +} diff --git a/babeld/babel_interface.h b/babeld/babel_interface.h new file mode 100644 index 0000000..9833827 --- /dev/null +++ b/babeld/babel_interface.h @@ -0,0 +1,138 @@ +/* +Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. +*/ + +#ifndef BABEL_INTERFACE_H +#define BABEL_INTERFACE_H + +#include <zebra.h> +#include "zclient.h" +#include "vty.h" +#include "distribute.h" + +#define CONFIG_DEFAULT 0 +#define CONFIG_NO 1 +#define CONFIG_YES 2 + +/* babeld interface information */ +struct babel_interface { + unsigned short flags; /* see below */ + unsigned short cost; + int channel; + struct timeval hello_timeout; + struct timeval update_timeout; + struct timeval flush_timeout; + struct timeval update_flush_timeout; + unsigned char *ipv4; + int buffered; + int bufsize; + /* Relative position of the Hello message in the send buffer, or + (-1) if there is none. */ + int buffered_hello; + char have_buffered_id; + char have_buffered_nh; + char have_buffered_prefix; + unsigned char buffered_id[8]; + unsigned char buffered_nh[4]; + unsigned char buffered_prefix[16]; + unsigned char *sendbuf; + struct buffered_update *buffered_updates; + int num_buffered_updates; + int update_bufsize; + time_t bucket_time; + unsigned int bucket; + time_t last_update_time; + unsigned short hello_seqno; + unsigned hello_interval; + unsigned update_interval; + /* A higher value means we forget old RTT samples faster. Must be + between 1 and 256, inclusive. */ + unsigned int rtt_decay; + /* Parameters for computing the cost associated to RTT. */ + unsigned int rtt_min; + unsigned int rtt_max; + unsigned int max_rtt_penalty; + + /* For filter type slot. */ + struct access_list *list[DISTRIBUTE_MAX]; /* Access-list. */ + struct prefix_list *prefix[DISTRIBUTE_MAX]; /* Prefix-list. */ +}; + +typedef struct babel_interface babel_interface_nfo; +static inline babel_interface_nfo* babel_get_if_nfo(struct interface *ifp) +{ + return ((babel_interface_nfo*) ifp->info); +} + +/* babel_interface_nfo flags */ +#define BABEL_IF_IS_UP (1 << 0) +#define BABEL_IF_WIRED (1 << 1) +#define BABEL_IF_SPLIT_HORIZON (1 << 2) +#define BABEL_IF_LQ (1 << 3) +#define BABEL_IF_FARAWAY (1 << 4) +#define BABEL_IF_TIMESTAMPS (1 << 5) + +/* Only INTERFERING can appear on the wire. */ +#define BABEL_IF_CHANNEL_UNKNOWN 0 +#define BABEL_IF_CHANNEL_INTERFERING 255 +#define BABEL_IF_CHANNEL_NONINTERFERING -2 + +static inline int +if_up(struct interface *ifp) +{ + return (if_is_operative(ifp) && + ifp->connected != NULL && + (babel_get_if_nfo(ifp)->flags & BABEL_IF_IS_UP)); +} + +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, vrf_id_t); +int babel_interface_down (int, struct zclient *, zebra_size_t, vrf_id_t); +int babel_interface_add (int, struct zclient *, zebra_size_t, vrf_id_t); +int babel_interface_delete (int, struct zclient *, zebra_size_t, vrf_id_t); +int babel_interface_address_add (int, struct zclient *, zebra_size_t, vrf_id_t); +int babel_interface_address_delete (int, struct zclient *, zebra_size_t, vrf_id_t); + +int babel_ifp_create(struct interface *ifp); +int babel_ifp_up(struct interface *ifp); +int babel_ifp_down(struct interface *ifp); +int babel_ifp_destroy(struct interface *ifp); + +unsigned jitter(babel_interface_nfo *, int); +unsigned update_jitter(babel_interface_nfo *babel_ifp, int urgent); +/* return "true" if "address" is one of our ipv6 addresses */ +int is_interface_ll_address(struct interface *ifp, const unsigned char *address); +/* Send retraction to all, and reset all interfaces statistics. */ +void babel_interface_close_all(void); +extern int babel_enable_if_config_write (struct vty *); + + +#endif diff --git a/babeld/babel_main.c b/babeld/babel_main.c new file mode 100644 index 0000000..b29374f --- /dev/null +++ b/babeld/babel_main.c @@ -0,0 +1,416 @@ +/* +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 "lib/version.h" +#include "command.h" +#include "vty.h" +#include "memory.h" +#include "libfrr.h" +#include "lib_errors.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" +#include "babel_errors.h" + +static void babel_fail(void); +static void babel_init_random(void); +static void babel_replace_by_null(int fd); +static void babel_exit_properly(void); +static void babel_save_state_file(void); + + +struct thread_master *master; /* quagga's threads handler */ +struct timeval babel_now; /* current time */ + +unsigned char myid[8]; /* unique id (mac address of an interface) */ +int debug = 0; + +int resend_delay = -1; + +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[1024]; + +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 const char babel_config_default[] = SYSCONFDIR BABEL_DEFAULT_CONFIG; +static char *babel_vty_addr = NULL; +static int babel_vty_port = BABEL_VTY_PORT; + +/* babeld privileges */ +static zebra_capabilities_t _caps_p [] = +{ + ZCAP_NET_RAW, + ZCAP_BIND +}; + +struct zebra_privs_t babeld_privs = +{ +#if defined(FRR_USER) + .user = FRR_USER, +#endif +#if defined FRR_GROUP + .group = FRR_GROUP, +#endif +#ifdef VTY_GROUP + .vty_group = VTY_GROUP, +#endif + .caps_p = _caps_p, + .cap_num_p = array_size(_caps_p), + .cap_num_i = 0 +}; + +static void +babel_sigexit(void) +{ + zlog_notice("Terminating on signal"); + + babel_exit_properly(); +} + +static void +babel_sigusr1 (void) +{ + zlog_rotate (); +} + +static struct frr_signal_t babel_signals[] = + { + { + .signal = SIGUSR1, + .handler = &babel_sigusr1, + }, + { + .signal = SIGINT, + .handler = &babel_sigexit, + }, + { + .signal = SIGTERM, + .handler = &babel_sigexit, + }, + }; + +struct option longopts[] = + { + { 0 } + }; + +static const struct frr_yang_module_info *const babeld_yang_modules[] = { + &frr_filter_info, + &frr_interface_info, + &frr_vrf_info, +}; + +FRR_DAEMON_INFO(babeld, BABELD, + .vty_port = BABEL_VTY_PORT, + .proghelp = "Implementation of the BABEL routing protocol.", + + .signals = babel_signals, + .n_signals = array_size(babel_signals), + + .privs = &babeld_privs, + + .yang_modules = babeld_yang_modules, + .n_yang_modules = array_size(babeld_yang_modules), +); + +int +main(int argc, char **argv) +{ + int rc; + + frr_preinit (&babeld_di, argc, argv); + frr_opt_add ("", longopts, ""); + + 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) { + int opt; + + opt = frr_getopt (argc, argv, NULL); + + if (opt == EOF) + break; + + switch (opt) + { + case 0: + break; + default: + frr_help_exit(1); + } + } + + snprintf(state_file, sizeof(state_file), "%s/%s", + frr_vtydir, "babel-state"); + + /* create the threads handler */ + master = frr_init (); + + /* Library inits. */ + babel_error_init(); + + resend_delay = BABEL_DEFAULT_RESEND_DELAY; + change_smoothing_half_life(BABEL_DEFAULT_SMOOTHING_HALF_LIFE); + + babel_replace_by_null(STDIN_FILENO); + + /* init some quagga's dependencies, and babeld's commands */ + if_zapi_callbacks(babel_ifp_create, babel_ifp_up, + babel_ifp_down, babel_ifp_destroy); + babeld_quagga_init(); + /* init zebra client's structure and it's commands */ + /* this replace kernel_setup && kernel_setup_socket */ + babelz_zebra_init (); + + /* init buffer */ + rc = resize_receive_buffer(1500); + if(rc < 0) + babel_fail(); + + schedule_neighbours_check(5000, 1); + + frr_config_fork(); + frr_run(master); + + return 0; +} + +static void +babel_fail(void) +{ + exit(1); +} + +/* initialize random value, and set 'babel_now' by the way. */ +static void +babel_init_random(void) +{ + gettime(&babel_now); + int rc; + unsigned int seed; + + rc = read_random_bytes(&seed, sizeof(seed)); + if(rc < 0) { + flog_err_sys(EC_LIB_SYSTEM_CALL, "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) { + flog_err_sys(EC_LIB_SYSTEM_CALL, "open(null): %s", safe_strerror(errno)); + exit(1); + } + + rc = dup2(fd_null, fd); + if(rc < 0) { + flog_err_sys(EC_LIB_SYSTEM_CALL, "dup2(null, 0): %s", + safe_strerror(errno)); + exit(1); + } + + close(fd_null); +} + +/* + Load the state file: check last babeld's running state, usefull in case of + "/etc/init.d/babeld restart" + */ +void +babel_load_state_file(void) +{ + int fd; + int rc; + + fd = open(state_file, O_RDONLY); + if(fd < 0 && errno != ENOENT) + flog_err_sys(EC_LIB_SYSTEM_CALL, "open(babel-state: %s)", + safe_strerror(errno)); + rc = unlink(state_file); + if(fd >= 0 && rc < 0) { + flog_err_sys(EC_LIB_SYSTEM_CALL, "unlink(babel-state): %s", + safe_strerror(errno)); + /* If we couldn't unlink it, it's probably stale. */ + goto fini; + } + if(fd >= 0) { + char buf[100]; + char buf2[100]; + int s; + long t; + rc = read(fd, buf, 99); + if(rc < 0) { + flog_err_sys(EC_LIB_SYSTEM_CALL, "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) { + flog_err(EC_BABEL_CONFIG, "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 + flog_err(EC_BABEL_CONFIG, + "ID mismatch in babel-state. id=%s; old=%s", + format_eui64(myid), + format_eui64(sid)); + } + } else { + flog_err(EC_BABEL_CONFIG, "Couldn't parse babel-state."); + } + } + goto fini; + } +fini: + if (fd >= 0) + close(fd); + return ; +} + +static void +babel_exit_properly(void) +{ + debugf(BABEL_DEBUG_COMMON, "Exiting..."); + usleep(roughly(10000)); + gettime(&babel_now); + + /* Uninstall and flush all routes. */ + debugf(BABEL_DEBUG_COMMON, "Uninstall routes."); + flush_all_routes(); + babel_interface_close_all(); + babel_zebra_close_connexion(); + babel_save_state_file(); + debugf(BABEL_DEBUG_COMMON, "Remove pid file."); + debugf(BABEL_DEBUG_COMMON, "Done."); + frr_fini(); + + 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) { + flog_err_sys(EC_LIB_SYSTEM_CALL, "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) { + flog_err(EC_BABEL_CONFIG, "write(babel-state): overflow."); + unlink(state_file); + } else { + rc = write(fd, buf, rc); + if(rc < 0) { + flog_err(EC_BABEL_CONFIG, "write(babel-state): %s", + safe_strerror(errno)); + unlink(state_file); + } + fsync(fd); + } + close(fd); + } +} + +void +show_babel_main_configuration (struct vty *vty) +{ + vty_out (vty, + "state file = %s\n" + "configuration file = %s\n" + "protocol information:\n" + " multicast address = %s\n" + " port = %d\n" + "vty address = %s\n" + "vty port = %d\n" + "id = %s\n" + "kernel_metric = %d\n", + state_file, + babeld_di.config_file ? babeld_di.config_file : babel_config_default, + format_address(protocol_group), + protocol_port, + babel_vty_addr ? babel_vty_addr : "None", + babel_vty_port, + format_eui64(myid), + kernel_metric); +} diff --git a/babeld/babel_main.h b/babeld/babel_main.h new file mode 100644 index 0000000..6fd27bf --- /dev/null +++ b/babeld/babel_main.h @@ -0,0 +1,46 @@ +/* +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_MAIN_H +#define BABEL_MAIN_H + +#include "vty.h" + +extern struct timeval babel_now; /* current time */ +extern struct thread_master *master; /* quagga's threads handler */ +extern int debug; +extern int resend_delay; + +extern unsigned char myid[8]; + +extern const unsigned char zeroes[16], ones[16]; + +extern int protocol_port; +extern unsigned char protocol_group[16]; +extern int protocol_socket; +extern int kernel_socket; +extern int max_request_hopcount; + +void babel_load_state_file(void); +void show_babel_main_configuration (struct vty *vty); + +#endif /* BABEL_MAIN_H */ diff --git a/babeld/babel_zebra.c b/babeld/babel_zebra.c new file mode 100644 index 0000000..d0da93e --- /dev/null +++ b/babeld/babel_zebra.c @@ -0,0 +1,266 @@ +/* +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. +*/ + +/* FRR's includes */ +#include <zebra.h> +#include "command.h" +#include "zclient.h" +#include "stream.h" + +/* babel's includes*/ +#include "babel_zebra.h" +#include "babel_interface.h" +#include "xroute.h" +#include "util.h" + +void babelz_zebra_init(void); + + +/* we must use a pointer because of zclient.c's functions (new, free). */ +struct zclient *zclient; + +/* Debug types */ +static const struct { + int type; + int str_min_len; + const char *str; +} debug_type[] = { + {BABEL_DEBUG_COMMON, 1, "common"}, + {BABEL_DEBUG_KERNEL, 1, "kernel"}, + {BABEL_DEBUG_FILTER, 1, "filter"}, + {BABEL_DEBUG_TIMEOUT, 1, "timeout"}, + {BABEL_DEBUG_IF, 1, "interface"}, + {BABEL_DEBUG_ROUTE, 1, "route"}, + {BABEL_DEBUG_ALL, 1, "all"}, + {0, 0, NULL} +}; + +/* Zebra route add and delete treatment. */ +static int +babel_zebra_read_route (ZAPI_CALLBACK_ARGS) +{ + struct zapi_route api; + + if (zapi_route_decode(zclient->ibuf, &api) < 0) + return -1; + + /* we completely ignore srcdest routes for now. */ + if (CHECK_FLAG(api.message, ZAPI_MESSAGE_SRCPFX)) + return 0; + + if (cmd == ZEBRA_REDISTRIBUTE_ROUTE_ADD) { + babel_route_add(&api); + } else { + babel_route_delete(&api); + } + + return 0; +} + +/* [Babel Command] */ +DEFUN (babel_redistribute_type, + babel_redistribute_type_cmd, + "[no] redistribute <ipv4 " FRR_IP_REDIST_STR_BABELD "|ipv6 " FRR_IP6_REDIST_STR_BABELD ">", + NO_STR + "Redistribute\n" + "Redistribute IPv4 routes\n" + FRR_IP_REDIST_HELP_STR_BABELD + "Redistribute IPv6 routes\n" + FRR_IP6_REDIST_HELP_STR_BABELD) +{ + int negate = 0; + int family; + int afi; + int type; + int idx = 0; + + if (argv_find(argv, argc, "no", &idx)) + negate = 1; + argv_find(argv, argc, "redistribute", &idx); + family = str2family(argv[idx + 1]->text); + if (family < 0) + return CMD_WARNING_CONFIG_FAILED; + + afi = family2afi(family); + if (!afi) + return CMD_WARNING_CONFIG_FAILED; + + type = proto_redistnum(afi, argv[idx + 2]->text); + if (type < 0) { + vty_out (vty, "Invalid type %s\n", argv[idx + 2]->arg); + return CMD_WARNING_CONFIG_FAILED; + } + + if (!negate) + zclient_redistribute (ZEBRA_REDISTRIBUTE_ADD, zclient, afi, type, 0, VRF_DEFAULT); + else { + zclient_redistribute (ZEBRA_REDISTRIBUTE_DELETE, zclient, afi, type, 0, VRF_DEFAULT); + /* perhaps should we remove xroutes having the same type... */ + } + return CMD_SUCCESS; +} + +#ifndef NO_DEBUG +/* [Babel Command] */ +DEFUN (debug_babel, + debug_babel_cmd, + "debug babel <common|kernel|filter|timeout|interface|route|all>", + "Enable debug messages for specific or all part.\n" + "Babel information\n" + "Common messages (default)\n" + "Kernel messages\n" + "Filter messages\n" + "Timeout messages\n" + "Interface messages\n" + "Route messages\n" + "All messages\n") +{ + int i; + + for(i = 0; debug_type[i].str != NULL; i++) { + if (strncmp (debug_type[i].str, argv[2]->arg, + debug_type[i].str_min_len) == 0) { + debug |= debug_type[i].type; + return CMD_SUCCESS; + } + } + + vty_out (vty, "Invalid type %s\n", argv[2]->arg); + + return CMD_WARNING_CONFIG_FAILED; +} + +/* [Babel Command] */ +DEFUN (no_debug_babel, + no_debug_babel_cmd, + "no debug babel <common|kernel|filter|timeout|interface|route|all>", + NO_STR + "Disable debug messages for specific or all part.\n" + "Babel information\n" + "Common messages (default)\n" + "Kernel messages\n" + "Filter messages\n" + "Timeout messages\n" + "Interface messages\n" + "Route messages\n" + "All messages\n") +{ + int i; + + for (i = 0; debug_type[i].str; i++) { + if (strncmp(debug_type[i].str, argv[3]->arg, + debug_type[i].str_min_len) == 0) { + debug &= ~debug_type[i].type; + return CMD_SUCCESS; + } + } + + vty_out (vty, "Invalid type %s\n", argv[3]->arg); + + return CMD_WARNING_CONFIG_FAILED; +} +#endif /* NO_DEBUG */ + +/* Output "debug" statement lines, if necessary. */ +int +debug_babel_config_write (struct vty * vty) +{ +#ifdef NO_DEBUG + return 0; +#else + int i, lines = 0; + + if (debug == BABEL_DEBUG_ALL) + { + vty_out (vty, "debug babel all\n"); + lines++; + } + else + for (i = 0; debug_type[i].str != NULL; i++) + if + ( + debug_type[i].type != BABEL_DEBUG_ALL + && CHECK_FLAG (debug, debug_type[i].type) + ) + { + vty_out (vty, "debug babel %s\n", debug_type[i].str); + lines++; + } + if (lines) + { + vty_out (vty, "!\n"); + lines++; + } + return lines; +#endif /* NO_DEBUG */ +} + +DEFUN_NOSH (show_debugging_babel, + show_debugging_babel_cmd, + "show debugging [babel]", + SHOW_STR + DEBUG_STR + "Babel") +{ + vty_out(vty, "BABEL debugging status\n"); + + debug_babel_config_write(vty); + + return CMD_SUCCESS; +} + +static void +babel_zebra_connected (struct zclient *zclient) +{ + zclient_send_reg_requests (zclient, VRF_DEFAULT); +} + +static zclient_handler *const babel_handlers[] = { + [ZEBRA_INTERFACE_ADDRESS_ADD] = babel_interface_address_add, + [ZEBRA_INTERFACE_ADDRESS_DELETE] = babel_interface_address_delete, + [ZEBRA_REDISTRIBUTE_ROUTE_ADD] = babel_zebra_read_route, + [ZEBRA_REDISTRIBUTE_ROUTE_DEL] = babel_zebra_read_route, +}; + +void babelz_zebra_init(void) +{ + zclient = zclient_new(master, &zclient_options_default, babel_handlers, + array_size(babel_handlers)); + zclient_init(zclient, ZEBRA_ROUTE_BABEL, 0, &babeld_privs); + + zclient->zebra_connected = babel_zebra_connected; + + install_element(BABEL_NODE, &babel_redistribute_type_cmd); + install_element(ENABLE_NODE, &debug_babel_cmd); + install_element(ENABLE_NODE, &no_debug_babel_cmd); + install_element(CONFIG_NODE, &debug_babel_cmd); + install_element(CONFIG_NODE, &no_debug_babel_cmd); + + install_element(ENABLE_NODE, &show_debugging_babel_cmd); +} + +void +babel_zebra_close_connexion(void) +{ + zclient_stop(zclient); + zclient_free(zclient); +} diff --git a/babeld/babel_zebra.h b/babeld/babel_zebra.h new file mode 100644 index 0000000..c064146 --- /dev/null +++ b/babeld/babel_zebra.h @@ -0,0 +1,34 @@ +/* +Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. +*/ + +#ifndef BABEL_ZEBRA_H +#define BABEL_ZEBRA_H + +#include "vty.h" + +extern struct zclient *zclient; + +void babelz_zebra_init(void); +void babel_zebra_close_connexion(void); +extern int debug_babel_config_write (struct vty *); + +#endif diff --git a/babeld/babeld.c b/babeld/babeld.c new file mode 100644 index 0000000..dfdc924 --- /dev/null +++ b/babeld/babeld.c @@ -0,0 +1,863 @@ +/* +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 "table.h" +#include "distribute.h" +#include "prefix.h" +#include "filter.h" +#include "plist.h" +#include "lib_errors.h" +#include "network.h" +#include "if.h" + +#include "babel_main.h" +#include "babeld.h" +#include "util.h" +#include "net.h" +#include "kernel.h" +#include "babel_interface.h" +#include "neighbour.h" +#include "route.h" +#include "message.h" +#include "resend.h" +#include "babel_filter.h" +#include "babel_zebra.h" +#include "babel_errors.h" + +DEFINE_MGROUP(BABELD, "babeld"); +DEFINE_MTYPE_STATIC(BABELD, BABEL, "Babel Structure"); + +static void babel_init_routing_process(struct thread *thread); +static void babel_get_myid(void); +static void babel_initial_noise(void); +static void babel_read_protocol(struct thread *thread); +static void babel_main_loop(struct thread *thread); +static void babel_set_timer(struct timeval *timeout); +static void babel_fill_with_next_timeout(struct timeval *tv); +static void +babel_distribute_update (struct distribute_ctx *ctx, struct distribute *dist); + +/* 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 int babel_config_write (struct vty *vty); +static struct cmd_node cmd_babel_node = +{ + .name = "babel", + .node = BABEL_NODE, + .parent_node = CONFIG_NODE, + .prompt = "%s(config-router)# ", + .config_write = babel_config_write, +}; + +/* print current babel configuration on vty */ +static int +babel_config_write (struct vty *vty) +{ + int lines = 0; + int afi; + int i; + + /* list enabled debug modes */ + lines += debug_babel_config_write (vty); + + if (!babel_routing_process) + return lines; + vty_out (vty, "router babel\n"); + if (diversity_kind != DIVERSITY_NONE) + { + vty_out (vty, " babel diversity\n"); + lines++; + } + if (diversity_factor != BABEL_DEFAULT_DIVERSITY_FACTOR) + { + vty_out (vty, " babel diversity-factor %d\n",diversity_factor); + lines++; + } + if (resend_delay != BABEL_DEFAULT_RESEND_DELAY) + { + vty_out (vty, " babel resend-delay %u\n", resend_delay); + lines++; + } + if (smoothing_half_life != BABEL_DEFAULT_SMOOTHING_HALF_LIFE) + { + vty_out (vty, " babel smoothing-half-life %u\n", + smoothing_half_life); + lines++; + } + /* list enabled interfaces */ + lines = 1 + babel_enable_if_config_write (vty); + /* list redistributed protocols */ + for (afi = AFI_IP; afi <= AFI_IP6; afi++) { + for (i = 0; i < ZEBRA_ROUTE_MAX; i++) { + if (i != zclient->redist_default && + vrf_bitmap_check (zclient->redist[afi][i], VRF_DEFAULT)) { + vty_out (vty, " redistribute %s %s\n", + (afi == AFI_IP) ? "ipv4" : "ipv6", + zebra_route_string(i)); + lines++; + } + } + } + + lines += config_write_distribute (vty, babel_routing_process->distribute_ctx); + + vty_out (vty, "exit\n"); + + return lines; +} + + +static int +babel_create_routing_process (void) +{ + assert (babel_routing_process == NULL); + + /* Allocaste Babel instance. */ + babel_routing_process = XCALLOC(MTYPE_BABEL, sizeof(struct babel)); + + /* Initialize timeouts */ + gettime(&babel_now); + expiry_time = babel_now.tv_sec + roughly(30); + source_expiry_time = babel_now.tv_sec + roughly(300); + + /* Make socket for Babel protocol. */ + protocol_socket = babel_socket(protocol_port); + if (protocol_socket < 0) { + flog_err_sys(EC_LIB_SOCKET, "Couldn't create link local socket: %s", + safe_strerror(errno)); + goto fail; + } + + /* Threads. */ + thread_add_read(master, &babel_read_protocol, NULL, protocol_socket, &babel_routing_process->t_read); + /* wait a little: zebra will announce interfaces, addresses, routes... */ + thread_add_timer_msec(master, babel_init_routing_process, NULL, 200L, &babel_routing_process->t_update); + + /* Distribute list install. */ + babel_routing_process->distribute_ctx = distribute_list_ctx_create (vrf_lookup_by_id(VRF_DEFAULT)); + distribute_list_add_hook (babel_routing_process->distribute_ctx, babel_distribute_update); + distribute_list_delete_hook (babel_routing_process->distribute_ctx, babel_distribute_update); + return 0; +fail: + XFREE(MTYPE_BABEL, babel_routing_process); + return -1; +} + +/* thread reading entries form others babel daemons */ +static void babel_read_protocol(struct thread *thread) +{ + int rc; + struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT); + struct interface *ifp = NULL; + struct sockaddr_in6 sin6; + + 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) { + flog_err_sys(EC_LIB_SOCKET, "recv: %s", safe_strerror(errno)); + } + } else { + FOR_ALL_INTERFACES(vrf, ifp) { + if(!if_up(ifp)) + continue; + if(ifp->ifindex == (ifindex_t)sin6.sin6_scope_id) { + parse_packet((unsigned char*)&sin6.sin6_addr, ifp, + receive_buffer, rc); + break; + } + } + } + + /* re-add thread */ + thread_add_read(master, &babel_read_protocol, NULL, protocol_socket, &babel_routing_process->t_read); +} + +/* 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 void babel_init_routing_process(struct thread *thread) +{ + myseqno = (frr_weak_random() & 0xFFFF); + babel_get_myid(); + babel_load_state_file(); + debugf(BABEL_DEBUG_COMMON, "My ID is : %s.", format_eui64(myid)); + babel_initial_noise(); + babel_main_loop(thread);/* this function self-add to the t_update thread */ +} + +/* fill "myid" with an unique id (only if myid != {0}). */ +static void +babel_get_myid(void) +{ + struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT); + struct interface *ifp = 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(vrf, ifp) { + /* 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(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[INTERFACE_NAMSIZ], *ifname; + unsigned char eui[8]; + ifname = if_indextoname(i, buf); + if(ifname == NULL) + continue; + rc = if_eui64(i, eui); + if(rc < 0) + continue; + memcpy(myid, eui, 8); + return; + } + + flog_err(EC_BABEL_CONFIG, "Couldn't find router id -- using random value."); + + rc = read_random_bytes(myid, 8); + if(rc < 0) { + flog_err(EC_BABEL_CONFIG, "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 vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT); + struct interface *ifp = NULL; + + FOR_ALL_INTERFACES(vrf, ifp) { + 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(vrf, ifp) { + 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(void) +{ + flush_all_routes(); + babel_interface_close_all(); + + /* cancel events */ + thread_cancel(&babel_routing_process->t_read); + thread_cancel(&babel_routing_process->t_update); + + distribute_list_delete(&babel_routing_process->distribute_ctx); + XFREE(MTYPE_BABEL, babel_routing_process); +} + +/* Function used with timeout. */ +static void babel_main_loop(struct thread *thread) +{ + struct timeval tv; + struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT); + struct interface *ifp = 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: %lld msecs", + (long long)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; + } + + gettime(&babel_now); + + /* update database -------------------------------------------------- */ + if(timeval_compare(&check_neighbours_timeout, &babel_now) < 0) { + int msecs; + msecs = check_neighbours(); + /* Multiply by 3/2 to allow neighbours to expire. */ + msecs = MAX(3 * msecs / 2, 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(vrf, ifp) { + 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(vrf, ifp) { + 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 vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT); + struct interface *ifp = 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(vrf, ifp) { + 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; + thread_cancel(&(babel_routing_process->t_update)); + thread_add_timer_msec(master, babel_main_loop, NULL, msecs, &babel_routing_process->t_update); +} + +void +schedule_neighbours_check(int msecs, int override) +{ + struct timeval timeout; + + timeval_add_msec(&timeout, &babel_now, msecs); + 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) { + flog_err(EC_BABEL_MEMORY, "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) { + flog_err(EC_BABEL_MEMORY, "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_ctx *ctx, struct distribute *dist) +{ + struct interface *ifp; + babel_interface_nfo *babel_ifp; + int type; + int family; + + if (! dist->ifname) + return; + + ifp = if_lookup_by_name (dist->ifname, VRF_DEFAULT); + if (ifp == NULL) + return; + + babel_ifp = babel_get_if_nfo(ifp); + + for (type = 0; type < DISTRIBUTE_MAX; type++) { + family = type == DISTRIBUTE_V4_IN || type == DISTRIBUTE_V4_OUT ? + AFI_IP : AFI_IP6; + if (dist->list[type]) + babel_ifp->list[type] = access_list_lookup (family, + dist->list[type]); + else + babel_ifp->list[type] = NULL; + if (dist->prefix[type]) + babel_ifp->prefix[type] = prefix_list_lookup (family, + dist->prefix[type]); + else + babel_ifp->prefix[type] = NULL; + } +} + +static void +babel_distribute_update_interface (struct interface *ifp) +{ + struct distribute *dist = NULL; + + if (babel_routing_process) + dist = distribute_lookup(babel_routing_process->distribute_ctx, ifp->name); + if (dist) + babel_distribute_update (babel_routing_process->distribute_ctx, dist); +} + +/* Update all interface's distribute list. */ +static void +babel_distribute_update_all (struct prefix_list *notused) +{ + struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT); + struct interface *ifp; + + FOR_ALL_INTERFACES (vrf, ifp) + babel_distribute_update_interface (ifp); +} + +static void +babel_distribute_update_all_wrapper (struct access_list *notused) +{ + babel_distribute_update_all(NULL); +} + + +/* [Command] */ +DEFUN_NOSH (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_WARNING; + } + } + + return CMD_SUCCESS; +} + +/* [Command] */ +DEFUN (no_router_babel, + no_router_babel_cmd, + "no router babel", + NO_STR + "Disable a routing process\n" + "Remove Babel instance command\n") +{ + if(babel_routing_process) + babel_clean_routing_process(); + return CMD_SUCCESS; +} + +/* [Babel Command] */ +DEFUN (babel_diversity, + babel_diversity_cmd, + "babel diversity", + "Babel commands\n" + "Enable diversity-aware routing.\n") +{ + diversity_kind = DIVERSITY_CHANNEL; + return CMD_SUCCESS; +} + +/* [Babel Command] */ +DEFUN (no_babel_diversity, + no_babel_diversity_cmd, + "no babel diversity", + NO_STR + "Babel commands\n" + "Disable diversity-aware routing.\n") +{ + diversity_kind = DIVERSITY_NONE; + return CMD_SUCCESS; +} + +/* [Babel Command] */ +DEFUN (babel_diversity_factor, + babel_diversity_factor_cmd, + "babel diversity-factor (1-256)", + "Babel commands\n" + "Set the diversity factor.\n" + "Factor in units of 1/256.\n") +{ + int factor; + + factor = strtoul(argv[2]->arg, NULL, 10); + + diversity_factor = factor; + return CMD_SUCCESS; +} + +/* [Babel Command] */ +DEFUN (babel_set_resend_delay, + babel_set_resend_delay_cmd, + "babel resend-delay (20-655340)", + "Babel commands\n" + "Time before resending a message\n" + "Milliseconds\n") +{ + int interval; + + interval = strtoul(argv[2]->arg, NULL, 10); + + resend_delay = interval; + return CMD_SUCCESS; +} + +/* [Babel Command] */ +DEFUN (babel_set_smoothing_half_life, + babel_set_smoothing_half_life_cmd, + "babel smoothing-half-life (0-65534)", + "Babel commands\n" + "Smoothing half-life\n" + "Seconds (0 to disable)\n") +{ + int seconds; + + seconds = strtoul(argv[2]->arg, NULL, 10); + + change_smoothing_half_life(seconds); + return CMD_SUCCESS; +} + +DEFUN (babel_distribute_list, + babel_distribute_list_cmd, + "distribute-list [prefix] ACCESSLIST4_NAME <in|out> [WORD]", + "Filter networks in routing updates\n" + "Specify a prefix\n" + "Access-list name\n" + "Filter incoming routing updates\n" + "Filter outgoing routing updates\n" + "Interface name\n") +{ + const char *ifname = NULL; + int prefix = (argv[1]->type == WORD_TKN) ? 1 : 0; + + if (argv[argc - 1]->type == VARIABLE_TKN) + ifname = argv[argc - 1]->arg; + + return distribute_list_parser(prefix, true, argv[2 + prefix]->text, + argv[1 + prefix]->arg, ifname); +} + +DEFUN (babel_no_distribute_list, + babel_no_distribute_list_cmd, + "no distribute-list [prefix] ACCESSLIST4_NAME <in|out> [WORD]", + NO_STR + "Filter networks in routing updates\n" + "Specify a prefix\n" + "Access-list name\n" + "Filter incoming routing updates\n" + "Filter outgoing routing updates\n" + "Interface name\n") +{ + const char *ifname = NULL; + int prefix = (argv[2]->type == WORD_TKN) ? 1 : 0; + + if (argv[argc - 1]->type == VARIABLE_TKN) + ifname = argv[argc - 1]->arg; + + return distribute_list_no_parser(vty, prefix, true, + argv[3 + prefix]->text, + argv[2 + prefix]->arg, ifname); +} + +DEFUN (babel_ipv6_distribute_list, + babel_ipv6_distribute_list_cmd, + "ipv6 distribute-list [prefix] ACCESSLIST6_NAME <in|out> [WORD]", + "IPv6\n" + "Filter networks in routing updates\n" + "Specify a prefix\n" + "Access-list name\n" + "Filter incoming routing updates\n" + "Filter outgoing routing updates\n" + "Interface name\n") +{ + const char *ifname = NULL; + int prefix = (argv[2]->type == WORD_TKN) ? 1 : 0; + + if (argv[argc - 1]->type == VARIABLE_TKN) + ifname = argv[argc - 1]->arg; + + return distribute_list_parser(prefix, false, argv[3 + prefix]->text, + argv[2 + prefix]->arg, ifname); +} + +DEFUN (babel_no_ipv6_distribute_list, + babel_no_ipv6_distribute_list_cmd, + "no ipv6 distribute-list [prefix] ACCESSLIST6_NAME <in|out> [WORD]", + NO_STR + "IPv6\n" + "Filter networks in routing updates\n" + "Specify a prefix\n" + "Access-list name\n" + "Filter incoming routing updates\n" + "Filter outgoing routing updates\n" + "Interface name\n") +{ + const char *ifname = NULL; + int prefix = (argv[3]->type == WORD_TKN) ? 1 : 0; + + if (argv[argc - 1]->type == VARIABLE_TKN) + ifname = argv[argc - 1]->arg; + + return distribute_list_no_parser(vty, prefix, false, + argv[4 + prefix]->text, + argv[3 + prefix]->arg, ifname); +} + +void +babeld_quagga_init(void) +{ + + install_node(&cmd_babel_node); + + install_element(CONFIG_NODE, &router_babel_cmd); + install_element(CONFIG_NODE, &no_router_babel_cmd); + + install_default(BABEL_NODE); + install_element(BABEL_NODE, &babel_diversity_cmd); + install_element(BABEL_NODE, &no_babel_diversity_cmd); + install_element(BABEL_NODE, &babel_diversity_factor_cmd); + install_element(BABEL_NODE, &babel_set_resend_delay_cmd); + install_element(BABEL_NODE, &babel_set_smoothing_half_life_cmd); + + install_element(BABEL_NODE, &babel_distribute_list_cmd); + install_element(BABEL_NODE, &babel_no_distribute_list_cmd); + install_element(BABEL_NODE, &babel_ipv6_distribute_list_cmd); + install_element(BABEL_NODE, &babel_no_ipv6_distribute_list_cmd); + + vrf_cmd_init(NULL); + + 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); +} + +/* Stubs to adapt Babel's filtering calls to Quagga's infrastructure. */ + +int +input_filter(const unsigned char *id, + const unsigned char *prefix, unsigned short plen, + const unsigned char *neigh, unsigned int ifindex) +{ + return babel_filter(0, prefix, plen, ifindex); +} + +int +output_filter(const unsigned char *id, const unsigned char *prefix, + unsigned short plen, unsigned int ifindex) +{ + return babel_filter(1, prefix, plen, ifindex); +} + +/* There's no redistribute filter in Quagga -- the zebra daemon does its + own filtering. */ +int +redistribute_filter(const unsigned char *prefix, unsigned short plen, + unsigned int ifindex, int proto) +{ + return 0; +} + +struct babel *babel_lookup(void) +{ + return babel_routing_process; +} diff --git a/babeld/babeld.h b/babeld/babeld.h new file mode 100644 index 0000000..38859f5 --- /dev/null +++ b/babeld/babeld.h @@ -0,0 +1,124 @@ +/* +Copyright (c) 2007, 2008 by Juliusz Chroboczek +Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. +*/ + +#ifndef BABEL_BABELD_H +#define BABEL_BABELD_H + +#include <zebra.h> +#include "vty.h" + +#define INFINITY ((unsigned short)(~0)) + +#ifndef RTPROT_BABEL +#define RTPROT_BABEL 42 +#endif + +#define RTPROT_BABEL_LOCAL -2 + +#undef MAX +#undef MIN + +#define MAX(x,y) ((x)<=(y)?(y):(x)) +#define MIN(x,y) ((x)<=(y)?(x):(y)) + +#if defined(__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" + +/* Values in milliseconds */ +#define BABEL_DEFAULT_HELLO_INTERVAL 4000 +#define BABEL_DEFAULT_UPDATE_INTERVAL 16000 +#define BABEL_DEFAULT_RESEND_DELAY 2000 +#define BABEL_DEFAULT_RTT_DECAY 42 + +/* Values in microseconds */ +#define BABEL_DEFAULT_RTT_MIN 10000 +#define BABEL_DEFAULT_RTT_MAX 120000 + +/* In units of seconds */ +#define BABEL_DEFAULT_SMOOTHING_HALF_LIFE 4 + +/* In units of 1/256. */ +#define BABEL_DEFAULT_DIVERSITY_FACTOR 256 + +#define BABEL_DEFAULT_RXCOST_WIRED 96 +#define BABEL_DEFAULT_RXCOST_WIRELESS 256 +#define BABEL_DEFAULT_MAX_RTT_PENALTY 150 + +/* Babel structure. */ +struct babel +{ + /* Babel threads. */ + struct thread *t_read; /* on Babel protocol's socket */ + struct thread *t_update; /* timers */ + /* distribute_ctx */ + struct distribute_ctx *distribute_ctx; +}; + +extern struct zebra_privs_t babeld_privs; + +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); +extern struct babel *babel_lookup(void); + +#endif /* BABEL_BABELD_H */ diff --git a/babeld/kernel.c b/babeld/kernel.c new file mode 100644 index 0000000..5aa01ce --- /dev/null +++ b/babeld/kernel.c @@ -0,0 +1,255 @@ +/* +Copyright 2007, 2008 by Grégoire Henry, Julien Cristau and Juliusz Chroboczek +Copyright 2011, 2012 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. +*/ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <sys/time.h> +#include <sys/param.h> +#include <time.h> + +#include "babeld.h" + + +#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 "nexthop.h" + +#include "util.h" +#include "babel_interface.h" +#include "babel_zebra.h" + + +static int +zebra_route(int add, int familt, const unsigned char *pref, unsigned short plen, + const unsigned char *gate, int ifindex, unsigned int metric); + +int +kernel_interface_operational(struct interface *interface) +{ + return if_is_operative(interface); +} + +int +kernel_interface_mtu(struct interface *interface) +{ + return MIN(interface->mtu, interface->mtu6); +} + +int +kernel_interface_wireless(struct interface *interface) +{ + return 0; +} + +int +kernel_route(enum babel_kernel_routes 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 family; + + /* Check that the protocol family is consistent. */ + if(plen >= 96 && v4mapped(pref)) { + if(!v4mapped(gate)) { + errno = EINVAL; + return -1; + } + family = AF_INET; + } else { + if(v4mapped(gate)) { + errno = EINVAL; + return -1; + } + family = AF_INET6; + } + + switch (operation) { + case ROUTE_ADD: + return zebra_route(1, family, pref, plen, gate, ifindex, metric); + case ROUTE_FLUSH: + return zebra_route(0, family, pref, plen, gate, ifindex, metric); + case ROUTE_MODIFY: + if(newmetric == metric && memcmp(newgate, gate, 16) == 0 && + newifindex == ifindex) + return 0; + debugf(BABEL_DEBUG_ROUTE, "Modify route: delete old; add new."); + rc = zebra_route(0, family, pref, plen, gate, ifindex, metric); + if (rc < 0) + return -1; + + rc = zebra_route(1, family, pref, plen, newgate, newifindex, + newmetric); + return rc; + } + + return 0; +} + +static int +zebra_route(int add, int family, const unsigned char *pref, unsigned short plen, + const unsigned char *gate, int ifindex, unsigned int metric) +{ + struct zapi_route api; /* quagga's communication system */ + struct prefix quagga_prefix; /* quagga's prefix */ + union g_addr babel_prefix_addr; /* babeld's prefix addr */ + struct zapi_nexthop *api_nh; /* next router to go - no ECMP */ + + api_nh = &api.nexthops[0]; + + /* convert to be understandable by quagga */ + /* convert given addresses */ + switch (family) { + case AF_INET: + uchar_to_inaddr(&babel_prefix_addr.ipv4, pref); + break; + case AF_INET6: + uchar_to_in6addr(&babel_prefix_addr.ipv6, pref); + break; + } + + /* make prefix structure */ + memset (&quagga_prefix, 0, sizeof(quagga_prefix)); + quagga_prefix.family = family; + switch (family) { + case AF_INET: + IPV4_ADDR_COPY (&quagga_prefix.u.prefix4, &babel_prefix_addr.ipv4); + /* our plen is for v4mapped's addr */ + quagga_prefix.prefixlen = plen - 96; + break; + case AF_INET6: + IPV6_ADDR_COPY (&quagga_prefix.u.prefix6, &babel_prefix_addr.ipv6); + quagga_prefix.prefixlen = plen; + break; + } + apply_mask(&quagga_prefix); + + memset(&api, 0, sizeof(api)); + api.type = ZEBRA_ROUTE_BABEL; + api.safi = SAFI_UNICAST; + api.vrf_id = VRF_DEFAULT; + api.prefix = quagga_prefix; + + if(metric >= KERNEL_INFINITY) { + zapi_route_set_blackhole(&api, BLACKHOLE_REJECT); + } else { + SET_FLAG(api.message, ZAPI_MESSAGE_NEXTHOP); + api.nexthop_num = 1; + api_nh->ifindex = ifindex; + api_nh->vrf_id = VRF_DEFAULT; + switch (family) { + case AF_INET: + uchar_to_inaddr(&api_nh->gate.ipv4, gate); + if (IPV4_ADDR_SAME(&api_nh->gate.ipv4, &quagga_prefix.u.prefix4) + && quagga_prefix.prefixlen == IPV4_MAX_BITLEN) { + api_nh->type = NEXTHOP_TYPE_IFINDEX; + } else { + api_nh->type = NEXTHOP_TYPE_IPV4_IFINDEX; + } + break; + case AF_INET6: + uchar_to_in6addr(&api_nh->gate.ipv6, gate); + /* difference to IPv4: always leave the linklocal as nexthop */ + api_nh->type = NEXTHOP_TYPE_IPV6_IFINDEX; + break; + } + SET_FLAG(api.message, ZAPI_MESSAGE_METRIC); + api.metric = metric; + } + + debugf(BABEL_DEBUG_ROUTE, "%s route (%s) to zebra", + add ? "adding" : "removing", + (family == AF_INET) ? "ipv4" : "ipv6"); + return zclient_route_send (add ? ZEBRA_ROUTE_ADD : ZEBRA_ROUTE_DELETE, + zclient, &api); +} + +int +if_eui64(int ifindex, unsigned char *eui) +{ + struct interface *ifp = if_lookup_by_index(ifindex, VRF_DEFAULT); + if (ifp == NULL) { + return -1; + } + + uint8_t len = (uint8_t)ifp->hw_addr_len; + char *tmp = (void*) ifp->hw_addr; + + if (len == 8) { + memcpy(eui, tmp, 8); + eui[0] ^= 2; + } else if (len == 6) { + memcpy(eui, tmp, 3); + eui[3] = 0xFF; + eui[4] = 0xFE; + memcpy(eui+5, tmp+3, 3); + } else { + return -1; + } + return 0; +} + +/* Like gettimeofday, but returns monotonic time. If POSIX clocks are not + available, falls back to gettimeofday but enforces monotonicity. */ +void +gettime(struct timeval *tv) +{ + monotime(tv); +} + +/* If /dev/urandom doesn't exist, this will fail with ENOENT, which the + caller will deal with gracefully. */ + +int +read_random_bytes(void *buf, size_t len) +{ + int fd; + int rc; + + fd = open("/dev/urandom", O_RDONLY); + if(fd < 0) { + rc = -1; + } else { + rc = read(fd, buf, len); + if(rc < 0 || (unsigned) rc < len) + rc = -1; + close(fd); + } + return rc; +} diff --git a/babeld/kernel.h b/babeld/kernel.h new file mode 100644 index 0000000..f39bc35 --- /dev/null +++ b/babeld/kernel.h @@ -0,0 +1,49 @@ +/* +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_KERNEL_H +#define BABEL_KERNEL_H + +#include <netinet/in.h> +#include "babel_main.h" +#include "if.h" + +#define KERNEL_INFINITY 0xFFFF + +enum babel_kernel_routes { + ROUTE_FLUSH, + ROUTE_ADD, + ROUTE_MODIFY, +}; + +int kernel_interface_operational(struct interface *interface); +int kernel_interface_mtu(struct interface *interface); +int kernel_interface_wireless(struct interface *interface); +int kernel_route(enum babel_kernel_routes operation, const unsigned char *dest, + unsigned short plen, const unsigned char *gate, int ifindex, + unsigned int metric, const unsigned char *newgate, + int newifindex, unsigned int newmetric); +int if_eui64(int ifindex, unsigned char *eui); +void gettime(struct timeval *tv); +int read_random_bytes(void *buf, size_t len); + +#endif /* BABEL_KERNEL_H */ diff --git a/babeld/message.c b/babeld/message.c new file mode 100644 index 0000000..7d45d91 --- /dev/null +++ b/babeld/message.c @@ -0,0 +1,1890 @@ +/* +Copyright (c) 2007, 2008 by Juliusz Chroboczek + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. +*/ + +#include <zebra.h> +#include "if.h" + +#include "babeld.h" +#include "util.h" +#include "net.h" +#include "babel_interface.h" +#include "source.h" +#include "neighbour.h" +#include "route.h" +#include "xroute.h" +#include "resend.h" +#include "message.h" +#include "kernel.h" +#include "babel_main.h" +#include "babel_errors.h" + +static unsigned char packet_header[4] = {42, 2}; + +int split_horizon = 1; + +unsigned short myseqno = 0; + +#define UNICAST_BUFSIZE 1024 +static int unicast_buffered = 0; +static unsigned char *unicast_buffer = NULL; +struct neighbour *unicast_neighbour = NULL; +struct timeval unicast_flush_timeout = {0, 0}; + +/* Minimum TLV _body_ length for TLVs of particular types (0 = no limit). */ +static const unsigned char tlv_min_length[MESSAGE_MAX + 1] = +{ + [ MESSAGE_PAD1 ] = 0, + [ MESSAGE_PADN ] = 0, + [ MESSAGE_ACK_REQ ] = 6, + [ MESSAGE_ACK ] = 2, + [ MESSAGE_HELLO ] = 6, + [ MESSAGE_IHU ] = 6, + [ MESSAGE_ROUTER_ID ] = 10, + [ MESSAGE_NH ] = 2, + [ MESSAGE_UPDATE ] = 10, + [ MESSAGE_REQUEST ] = 2, + [ MESSAGE_MH_REQUEST ] = 14, +}; + +/* Parse a network prefix, encoded in the somewhat baroque compressed + representation used by Babel. Return the number of bytes parsed. */ +static int +network_prefix(int ae, int plen, unsigned int omitted, + const unsigned char *p, const unsigned char *dp, + unsigned int len, unsigned char *p_r) +{ + unsigned pb; + unsigned char prefix[16]; + int ret = -1; + + if(plen >= 0) + pb = (plen + 7) / 8; + else if(ae == 1) + pb = 4; + else + pb = 16; + + if(pb > 16) + return -1; + + memset(prefix, 0, 16); + + switch(ae) { + case 0: + ret = 0; + break; + case 1: + if(omitted > 4 || pb > 4 || (pb > omitted && len < pb - omitted)) + return -1; + memcpy(prefix, v4prefix, 12); + if(omitted) { + if (dp == NULL || !v4mapped(dp)) return -1; + memcpy(prefix, dp, 12 + omitted); + } + if(pb > omitted) memcpy(prefix + 12 + omitted, p, pb - omitted); + ret = pb - omitted; + break; + case 2: + if(omitted > 16 || (pb > omitted && len < pb - omitted)) return -1; + if(omitted) { + if (dp == NULL || v4mapped(dp)) return -1; + memcpy(prefix, dp, omitted); + } + if(pb > omitted) memcpy(prefix + omitted, p, pb - omitted); + ret = pb - omitted; + break; + case 3: + if(pb > 8 && len < pb - 8) return -1; + prefix[0] = 0xfe; + prefix[1] = 0x80; + if(pb > 8) memcpy(prefix + 8, p, pb - 8); + ret = pb - 8; + break; + default: + return -1; + } + + mask_prefix(p_r, prefix, plen < 0 ? 128 : ae == 1 ? plen + 96 : plen); + return ret; +} + +static bool parse_update_subtlv(const unsigned char *a, int alen, + unsigned char *channels) +{ + int type, len, i = 0; + + while(i < alen) { + type = a[i]; + if(type == SUBTLV_PAD1) { + i++; + continue; + } + + if(i + 1 >= alen) { + flog_err(EC_BABEL_PACKET, "Received truncated attributes."); + return false; + } + len = a[i + 1]; + if(i + len + 2 > alen) { + flog_err(EC_BABEL_PACKET, "Received truncated attributes."); + return false; + } + + if (type & SUBTLV_MANDATORY) { + /* + * RFC 8966 - 4.4 + * If the mandatory bit is set, then the whole enclosing + * TLV MUST be silently ignored (except for updating the + * parser state by a Router-Id, Next Hop, or Update TLV, + * as described in the next section). + */ + debugf(BABEL_DEBUG_COMMON, + "Received Mandatory bit set but this FRR version is not prepared to handle it at this point"); + return true; + } else if (type == SUBTLV_PADN) { + /* Nothing. */ + } else if (type == SUBTLV_DIVERSITY) { + if (len > DIVERSITY_HOPS) { + flog_err( + EC_BABEL_PACKET, + "Received overlong channel information (%d > %d).n", + len, DIVERSITY_HOPS); + len = DIVERSITY_HOPS; + } + if (memchr(a + i + 2, 0, len) != NULL) { + /* 0 is reserved. */ + flog_err(EC_BABEL_PACKET, + "Channel information contains 0!"); + return false; + } + memset(channels, 0, DIVERSITY_HOPS); + memcpy(channels, a + i + 2, len); + } else { + debugf(BABEL_DEBUG_COMMON, + "Received unknown route attribute %d.", type); + } + + i += len + 2; + } + return false; +} + +static int +parse_hello_subtlv(const unsigned char *a, int alen, + unsigned int *hello_send_us) +{ + int type, len, i = 0, ret = 0; + + while(i < alen) { + type = a[i]; + if(type == SUBTLV_PAD1) { + i++; + continue; + } + + if(i + 1 >= alen) { + flog_err(EC_BABEL_PACKET, + "Received truncated sub-TLV on Hello message."); + return -1; + } + len = a[i + 1]; + if(i + len + 2 > alen) { + flog_err(EC_BABEL_PACKET, + "Received truncated sub-TLV on Hello message."); + return -1; + } + + if (type & SUBTLV_MANDATORY) { + /* + * RFC 8966 4.4 + * If the mandatory bit is set, then the whole enclosing + * TLV MUST be silently ignored (except for updating the + * parser state by a Router-Id, Next Hop, or Update TLV, as + * described in the next section). + */ + debugf(BABEL_DEBUG_COMMON, + "Received subtlv with Mandatory bit, this version of FRR is not prepared to handle this currently"); + return -2; + } else if (type == SUBTLV_PADN) { + /* Nothing to do. */ + } else if (type == SUBTLV_TIMESTAMP) { + if (len >= 4) { + DO_NTOHL(*hello_send_us, a + i + 2); + ret = 1; + } else { + flog_err( + EC_BABEL_PACKET, + "Received incorrect RTT sub-TLV on Hello message."); + } + } else { + debugf(BABEL_DEBUG_COMMON, + "Received unknown Hello sub-TLV type %d.", type); + } + + i += len + 2; + } + return ret; +} + +static int +parse_ihu_subtlv(const unsigned char *a, int alen, + unsigned int *hello_send_us, + unsigned int *hello_rtt_receive_time) +{ + int type, len, i = 0, ret = 0; + + while(i < alen) { + type = a[i]; + if(type == SUBTLV_PAD1) { + i++; + continue; + } + + if(i + 1 >= alen) { + flog_err(EC_BABEL_PACKET, + "Received truncated sub-TLV on IHU message."); + return -1; + } + len = a[i + 1]; + if(i + len + 2 > alen) { + flog_err(EC_BABEL_PACKET, + "Received truncated sub-TLV on IHU message."); + return -1; + } + + if(type == SUBTLV_PADN) { + /* Nothing to do. */ + } else if(type == SUBTLV_TIMESTAMP) { + if(len >= 8) { + DO_NTOHL(*hello_send_us, a + i + 2); + DO_NTOHL(*hello_rtt_receive_time, a + i + 6); + ret = 1; + } + else { + flog_err(EC_BABEL_PACKET, + "Received incorrect RTT sub-TLV on IHU message."); + } + } else { + debugf(BABEL_DEBUG_COMMON, + "Received unknown IHU sub-TLV type %d.", type); + } + + i += len + 2; + } + return ret; +} + +static int +network_address(int ae, const unsigned char *a, unsigned int len, + unsigned char *a_r) +{ + return network_prefix(ae, -1, 0, a, NULL, len, a_r); +} + +static int +channels_len(unsigned char *channels) +{ + unsigned char *p = memchr(channels, 0, DIVERSITY_HOPS); + return p ? (p - channels) : DIVERSITY_HOPS; +} + +/* Check, that the provided frame consists of a valid Babel packet header + followed by a sequence of TLVs. TLVs of known types are also checked to meet + minimum length constraints defined for each. Return 0 for no errors. */ +static int +babel_packet_examin(const unsigned char *packet, int packetlen, int *blength) +{ + int i = 0, bodylen; + const unsigned char *message; + unsigned char type, len; + + if(packetlen < 4 || packet[0] != 42 || packet[1] != 2) + return 1; + DO_NTOHS(bodylen, packet + 2); + if(bodylen + 4 > packetlen) { + debugf(BABEL_DEBUG_COMMON, "Received truncated packet (%d + 4 > %d).", + bodylen, packetlen); + return 1; + } + while (i < bodylen){ + message = packet + 4 + i; + type = message[0]; + if(type == MESSAGE_PAD1) { + i++; + continue; + } + if(i + 2 > bodylen) { + debugf(BABEL_DEBUG_COMMON,"Received truncated message."); + return 1; + } + len = message[1]; + if(i + len + 2 > bodylen) { + debugf(BABEL_DEBUG_COMMON,"Received truncated message."); + return 1; + } + /* not Pad1 */ + if(type <= MESSAGE_MAX && tlv_min_length[type] && len < tlv_min_length[type]) { + debugf(BABEL_DEBUG_COMMON,"Undersized %u TLV", type); + return 1; + } + i += len + 2; + } + + *blength = bodylen; + return 0; +} + +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]; + int have_hello_rtt = 0; + /* Content of the RTT sub-TLV on IHU messages. */ + unsigned int hello_send_us = 0, hello_rtt_receive_time = 0; + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + + if(babel_ifp->flags & BABEL_IF_TIMESTAMPS) { + /* We want to track exactly when we received this packet. */ + gettime(&babel_now); + } + + if(!linklocal(from)) { + flog_err(EC_BABEL_PACKET, + "Received packet from non-local address %s.", + format_address(from)); + return; + } + + if (babel_packet_examin (packet, packetlen, &bodylen)) { + flog_err(EC_BABEL_PACKET, + "Received malformed packet on %s from %s.", + ifp->name, format_address(from)); + return; + } + + neigh = find_neighbour(from, ifp); + if(neigh == NULL) { + flog_err(EC_BABEL_PACKET, "Couldn't allocate neighbour."); + return; + } + + 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; + } + len = message[1]; + + 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; + 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, flags; + int changed; + unsigned int timestamp = 0; + +#define BABEL_UNICAST_HELLO 0x8000 + DO_NTOHS(flags, message + 2); + + /* + * RFC 8966 4.6.5 + * All other bits MUST be sent as a 0 and silently + * ignored on reception + */ + if (CHECK_FLAG(flags, ~BABEL_UNICAST_HELLO)) { + debugf(BABEL_DEBUG_COMMON, + "Received Hello from %s on %s that does not have all 0's in the unused section of flags, ignoring", + format_address(from), ifp->name); + continue; + } + + /* + * RFC 8966 Appendix F + * TL;DR -> Please ignore Unicast hellos until FRR's + * BABEL is brought up to date + */ + if (CHECK_FLAG(flags, BABEL_UNICAST_HELLO)) { + debugf(BABEL_DEBUG_COMMON, + "Received Unicast Hello from %s on %s that FRR is not prepared to understand yet", + format_address(from), ifp->name); + continue; + } + + 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); + + /* + * RFC 8966 Appendix F + * TL;DR -> Please ignore any Hello packets with the interval + * field set to 0 + */ + if (interval == 0) { + debugf(BABEL_DEBUG_COMMON, + "Received hello from %s on %s should be ignored as that this version of FRR does not know how to properly handle interval == 0", + format_address(from), ifp->name); + continue; + } + + changed = update_neighbour(neigh, seqno, interval); + update_neighbour_metric(neigh, changed); + if (interval > 0) + /* Multiply by 3/2 to allow hellos to expire. */ + schedule_neighbours_check(interval * 15, 0); + /* Sub-TLV handling. */ + if (len > 8) { + if (parse_hello_subtlv(message + 8, len - 6, + ×tamp) > 0) { + neigh->hello_send_us = timestamp; + neigh->hello_rtt_receive_time = babel_now; + have_hello_rtt = 1; + } + } + } else if(type == MESSAGE_IHU) { + unsigned short txcost, interval; + unsigned char address[16]; + int rc; + 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) + /* Multiply by 3/2 to allow neighbours to expire. */ + schedule_neighbours_check(interval * 45, 0); + /* RTT sub-TLV. */ + if(len > 10 + rc) + parse_ihu_subtlv(message + 8 + rc, len - 6 - rc, + &hello_send_us, &hello_rtt_receive_time); + } + } else if(type == MESSAGE_ROUTER_ID) { + 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; + rc = network_address(message[2], message + 4, len - 2, + nh); + if(rc < 0) { + have_v4_nh = 0; + have_v6_nh = 0; + goto fail; + } + debugf(BABEL_DEBUG_COMMON,"Received nh %s (%d) from %s on %s.", + format_address(nh), message[2], + format_address(from), ifp->name); + if(message[2] == 1) { + memcpy(v4_nh, nh, 16); + have_v4_nh = 1; + } else { + memcpy(v6_nh, nh, 16); + have_v6_nh = 1; + } + } else if(type == MESSAGE_UPDATE) { + unsigned char prefix[16], *nh; + unsigned char plen; + unsigned char channels[DIVERSITY_HOPS]; + unsigned short interval, seqno, metric; + int rc, parsed_len; + bool ignore_update = false; + + DO_NTOHS(interval, message + 6); + DO_NTOHS(seqno, message + 8); + DO_NTOHS(metric, message + 10); + if(message[5] == 0 || + (message[2] == 1 ? have_v4_prefix : have_v6_prefix)) + rc = network_prefix(message[2], message[4], message[5], + message + 12, + message[2] == 1 ? v4_prefix : v6_prefix, + len - 10, prefix); + else + rc = -1; + if(rc < 0) { + if(message[3] & 0x80) + have_v4_prefix = have_v6_prefix = 0; + goto fail; + } + parsed_len = 10 + rc; + + plen = message[4] + (message[2] == 1 ? 96 : 0); + + if(message[3] & 0x80) { + if(message[2] == 1) { + memcpy(v4_prefix, prefix, 16); + have_v4_prefix = 1; + } else { + memcpy(v6_prefix, prefix, 16); + have_v6_prefix = 1; + } + } + if(message[3] & 0x40) { + if(message[2] == 1) { + memset(router_id, 0, 4); + memcpy(router_id + 4, prefix + 12, 4); + } else { + memcpy(router_id, prefix + 8, 8); + } + have_router_id = 1; + } + if(!have_router_id && message[2] != 0) { + flog_err(EC_BABEL_PACKET, + "Received prefix with no router id."); + goto fail; + } + debugf(BABEL_DEBUG_COMMON,"Received update%s%s for %s from %s on %s.", + (message[3] & 0x80) ? "/prefix" : "", + (message[3] & 0x40) ? "/id" : "", + format_prefix(prefix, plen), + format_address(from), ifp->name); + + if(message[2] == 0) { + if(metric < 0xFFFF) { + flog_err(EC_BABEL_PACKET, + "Received wildcard update with finite metric."); + goto done; + } + retract_neighbour_routes(neigh); + goto done; + } else if(message[2] == 1) { + if(!have_v4_nh) + goto fail; + nh = v4_nh; + } else if(have_v6_nh) { + nh = v6_nh; + } else { + nh = neigh->address; + } + + if(message[2] == 1) { + if(!babel_get_if_nfo(ifp)->ipv4) + goto done; + } + + if((babel_get_if_nfo(ifp)->flags & BABEL_IF_FARAWAY)) { + channels[0] = 0; + } else { + /* This will be overwritten by parse_update_subtlv below. */ + if(metric < 256) { + /* Assume non-interfering (wired) link. */ + channels[0] = 0; + } else { + /* Assume interfering. */ + channels[0] = BABEL_IF_CHANNEL_INTERFERING; + channels[1] = 0; + } + + if(parsed_len < len) + ignore_update = + parse_update_subtlv(message + 2 + parsed_len, + len - parsed_len, channels); + } + + if (!ignore_update) + update_route(router_id, prefix, plen, seqno, metric, + interval, neigh, nh, channels, + channels_len(channels)); + } else if(type == MESSAGE_REQUEST) { + unsigned char prefix[16], plen; + int rc; + rc = network_prefix(message[2], message[3], 0, + message + 4, NULL, len - 2, prefix); + if(rc < 0) goto fail; + plen = message[3] + (message[2] == 1 ? 96 : 0); + debugf(BABEL_DEBUG_COMMON,"Received request for %s from %s on %s.", + message[2] == 0 ? "any" : format_prefix(prefix, plen), + format_address(from), ifp->name); + if(message[2] == 0) { + struct babel_interface *neigh_ifp =babel_get_if_nfo(neigh->ifp); + /* If a neighbour is requesting a full route dump from us, + we might as well send it an IHU. */ + send_ihu(neigh, NULL); + /* Since nodes send wildcard requests on boot, booting + a large number of nodes at the same time may cause an + update storm. Ignore a wildcard request that happens + shortly after we sent a full update. */ + if(neigh_ifp->last_update_time < + (time_t)(babel_now.tv_sec - + MAX(neigh_ifp->hello_interval / 100, 1))) + send_update(neigh->ifp, 0, NULL, 0); + } else { + send_update(neigh->ifp, 0, prefix, plen); + } + } else if(type == MESSAGE_MH_REQUEST) { + unsigned char prefix[16], plen; + unsigned short seqno; + int rc; + 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: + flog_err(EC_BABEL_PACKET, + "Couldn't parse packet (%d, %d) from %s on %s.", + message[0], message[1], format_address(from), ifp->name); + goto done; + } + + /* We can calculate the RTT to this neighbour. */ + if(have_hello_rtt && hello_send_us && hello_rtt_receive_time) { + int remote_waiting_us, local_waiting_us; + unsigned int rtt, smoothed_rtt; + unsigned int old_rttcost; + int changed = 0; + remote_waiting_us = neigh->hello_send_us - hello_rtt_receive_time; + local_waiting_us = time_us(neigh->hello_rtt_receive_time) - + hello_send_us; + + /* Sanity checks (validity window of 10 minutes). */ + if(remote_waiting_us < 0 || local_waiting_us < 0 || + remote_waiting_us > 600000000 || local_waiting_us > 600000000) + return; + + rtt = MAX(0, local_waiting_us - remote_waiting_us); + debugf(BABEL_DEBUG_COMMON, "RTT to %s on %s sample result: %d us.", + format_address(from), ifp->name, rtt); + + old_rttcost = neighbour_rttcost(neigh); + if (valid_rtt(neigh)) { + /* Running exponential average. */ + smoothed_rtt = (babel_ifp->rtt_decay * rtt + + (256 - babel_ifp->rtt_decay) * neigh->rtt); + /* Rounding (up or down) to get closer to the sample. */ + neigh->rtt = (neigh->rtt >= rtt) ? smoothed_rtt / 256 : + (smoothed_rtt + 255) / 256; + } else { + /* We prefer to be conservative with new neighbours + (higher RTT) */ + assert(rtt <= 0x7FFFFFFF); + neigh->rtt = 2*rtt; + } + changed = (neighbour_rttcost(neigh) == old_rttcost ? 0 : 1); + update_neighbour_metric(neigh, changed); + neigh->rtt_time = babel_now; + } + 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; + } +} + +static int +fill_rtt_message(struct interface *ifp) +{ + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + if((babel_ifp->flags & BABEL_IF_TIMESTAMPS) && + (babel_ifp->buffered_hello >= 0)) { + if(babel_ifp->sendbuf[babel_ifp->buffered_hello + 8] == SUBTLV_PADN && + babel_ifp->sendbuf[babel_ifp->buffered_hello + 9] == 4) { + unsigned int time; + /* Change the type of sub-TLV. */ + babel_ifp->sendbuf[babel_ifp->buffered_hello + 8] = + SUBTLV_TIMESTAMP; + gettime(&babel_now); + time = time_us(babel_now); + DO_HTONL(babel_ifp->sendbuf + babel_ifp->buffered_hello + 10, time); + return 1; + } else { + flog_err(EC_BABEL_PACKET, "No space left for timestamp sub-TLV (this shouldn't happen)"); + return -1; + } + } + 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); + fill_rtt_message(ifp); + rc = babel_send(protocol_socket, + packet_header, sizeof(packet_header), + babel_ifp->sendbuf, babel_ifp->buffered, + (struct sockaddr*)&sin6, sizeof(sin6)); + if(rc < 0) + flog_err(EC_BABEL_PACKET, "send: %s", safe_strerror(errno)); + } else { + flog_err(EC_BABEL_PACKET, "Bucket full, dropping packet to %s.", + ifp->name); + } + } + VALGRIND_MAKE_MEM_UNDEFINED(babel_ifp->sendbuf, babel_ifp->bufsize); + babel_ifp->buffered = 0; + babel_ifp->buffered_hello = -1; + 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_int(struct interface *ifp, unsigned int value) +{ + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + DO_HTONL(babel_ifp->sendbuf + babel_ifp->buffered, value); + babel_ifp->buffered += 4; +} + +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) { + flog_err(EC_BABEL_MEMORY, "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_int(struct neighbour *neigh, unsigned int value) +{ + DO_HTONL(unicast_buffer + unicast_buffered, value); + unicast_buffered += 4; +} + +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->buffered_hello >= 0) + 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, + (babel_ifp->flags & BABEL_IF_TIMESTAMPS) ? 12 : 6); + babel_ifp->buffered_hello = babel_ifp->buffered - 2; + accumulate_short(ifp, 0); + accumulate_short(ifp, babel_ifp->hello_seqno); + accumulate_short(ifp, interval > 0xFFFF ? 0xFFFF : interval); + if(babel_ifp->flags & BABEL_IF_TIMESTAMPS) { + /* Sub-TLV containing the local time of emission. We use a + Pad4 sub-TLV, which we'll fill just before sending. */ + accumulate_byte(ifp, SUBTLV_PADN); + accumulate_byte(ifp, 4); + accumulate_int(ifp, 0); + } + end_message(ifp, MESSAGE_HELLO, + (babel_ifp->flags & BABEL_IF_TIMESTAMPS) ? 12 : 6); +} + +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); + fill_rtt_message(unicast_neighbour->ifp); + rc = babel_send(protocol_socket, + packet_header, sizeof(packet_header), + unicast_buffer, unicast_buffered, + (struct sockaddr*)&sin6, sizeof(sin6)); + if(rc < 0) + flog_err(EC_BABEL_PACKET, "send(unicast): %s", + safe_strerror(errno)); + } else { + flog_err(EC_BABEL_PACKET, + "Bucket full, dropping unicast packet to %s if %s.", + format_address(unicast_neighbour->address), + unicast_neighbour->ifp->name); + } + + done: + VALGRIND_MAKE_MEM_UNDEFINED(unicast_buffer, UNICAST_BUFSIZE); + unicast_buffered = 0; + if(dofree && unicast_buffer) { + free(unicast_buffer); + unicast_buffer = NULL; + } + unicast_neighbour = NULL; + unicast_flush_timeout.tv_sec = 0; + unicast_flush_timeout.tv_usec = 0; +} + +static void +really_send_update(struct interface *ifp, + const unsigned char *id, + const unsigned char *prefix, unsigned char plen, + unsigned short seqno, unsigned short metric, + unsigned char *channels, int channels_len) +{ + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + int add_metric, v4, real_plen, omit = 0; + const unsigned char *real_prefix; + unsigned short flags = 0; + int channels_size; + + if(diversity_kind != DIVERSITY_CHANNEL) + channels_len = -1; + + channels_size = channels_len >= 0 ? channels_len + 2 : 0; + + if(!if_up(ifp)) + return; + + add_metric = output_filter(id, prefix, plen, ifp->ifindex); + if(add_metric >= INFINITY) + return; + + metric = MIN(metric + add_metric, INFINITY); + /* Worst case */ + ensure_space(ifp, 20 + 12 + 28); + + v4 = plen >= 96 && v4mapped(prefix); + + if(v4) { + if(!babel_ifp->ipv4) + return; + if(!babel_ifp->have_buffered_nh || + memcmp(babel_ifp->buffered_nh, babel_ifp->ipv4, 4) != 0) { + start_message(ifp, MESSAGE_NH, 6); + accumulate_byte(ifp, 1); + accumulate_byte(ifp, 0); + accumulate_bytes(ifp, babel_ifp->ipv4, 4); + end_message(ifp, MESSAGE_NH, 6); + memcpy(babel_ifp->buffered_nh, babel_ifp->ipv4, 4); + babel_ifp->have_buffered_nh = 1; + } + + real_prefix = prefix + 12; + real_plen = plen - 96; + } else { + if(babel_ifp->have_buffered_prefix) { + while(omit < plen / 8 && + babel_ifp->buffered_prefix[omit] == prefix[omit]) + omit++; + } + if(!babel_ifp->have_buffered_prefix || plen >= 48) + flags |= 0x80; + real_prefix = prefix; + real_plen = plen; + } + + if(!babel_ifp->have_buffered_id + || memcmp(id, babel_ifp->buffered_id, 8) != 0) { + if(real_plen == 128 && memcmp(real_prefix + 8, id, 8) == 0) { + flags |= 0x40; + } else { + start_message(ifp, MESSAGE_ROUTER_ID, 10); + accumulate_short(ifp, 0); + accumulate_bytes(ifp, id, 8); + end_message(ifp, MESSAGE_ROUTER_ID, 10); + } + memcpy(babel_ifp->buffered_id, id, sizeof(babel_ifp->buffered_id)); + babel_ifp->have_buffered_id = 1; + } + + start_message(ifp, MESSAGE_UPDATE, 10 + (real_plen + 7) / 8 - omit + + channels_size); + accumulate_byte(ifp, v4 ? 1 : 2); + accumulate_byte(ifp, flags); + accumulate_byte(ifp, real_plen); + accumulate_byte(ifp, omit); + accumulate_short(ifp, (babel_ifp->update_interval + 5) / 10); + accumulate_short(ifp, seqno); + accumulate_short(ifp, metric); + accumulate_bytes(ifp, real_prefix + omit, (real_plen + 7) / 8 - omit); + /* Note that an empty channels TLV is different from no such TLV. */ + if(channels_len >= 0) { + accumulate_byte(ifp, 2); + accumulate_byte(ifp, channels_len); + + if (channels && channels_len > 0) + accumulate_bytes(ifp, channels, channels_len); + } + end_message(ifp, MESSAGE_UPDATE, 10 + (real_plen + 7) / 8 - omit + + channels_size); + + if(flags & 0x80) { + memcpy(babel_ifp->buffered_prefix, prefix, 16); + babel_ifp->have_buffered_prefix = 1; + } +} + +static int +compare_buffered_updates(const void *av, const void *bv) +{ + const struct buffered_update *a = av, *b = bv; + int rc, v4a, v4b, ma, mb; + + rc = memcmp(a->id, b->id, 8); + if(rc != 0) + return rc; + + v4a = (a->plen >= 96 && v4mapped(a->prefix)); + v4b = (b->plen >= 96 && v4mapped(b->prefix)); + + if(v4a > v4b) + return 1; + else if(v4a < v4b) + return -1; + + ma = (!v4a && a->plen == 128 && memcmp(a->prefix + 8, a->id, 8) == 0); + mb = (!v4b && b->plen == 128 && memcmp(b->prefix + 8, b->id, 8) == 0); + + if(ma > mb) + return -1; + else if(mb > ma) + return 1; + + if(a->plen < b->plen) + return 1; + else if(a->plen > b->plen) + return -1; + + return memcmp(a->prefix, b->prefix, 16); +} + +void +flushupdates(struct interface *ifp) +{ + babel_interface_nfo *babel_ifp = NULL; + struct xroute *xroute; + struct babel_route *route; + const unsigned char *last_prefix = NULL; + unsigned char last_plen = 0xFF; + int i; + + if(ifp == NULL) { + struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT); + struct interface *ifp_aux; + FOR_ALL_INTERFACES(vrf, ifp_aux) + flushupdates(ifp_aux); + return; + } + + babel_ifp = babel_get_if_nfo(ifp); + if(babel_ifp->num_buffered_updates > 0) { + struct buffered_update *b = babel_ifp->buffered_updates; + int n = babel_ifp->num_buffered_updates; + + babel_ifp->buffered_updates = NULL; + babel_ifp->update_bufsize = 0; + babel_ifp->num_buffered_updates = 0; + + if(!if_up(ifp)) + goto done; + + debugf(BABEL_DEBUG_COMMON," (flushing %d buffered updates on %s (%d))", + n, ifp->name, ifp->ifindex); + + /* In order to send fewer update messages, we want to send updates + with the same router-id together, with IPv6 going out before IPv4. */ + + for(i = 0; i < n; i++) { + route = find_installed_route(b[i].prefix, b[i].plen); + if(route) + memcpy(b[i].id, route->src->id, 8); + else + memcpy(b[i].id, myid, 8); + } + + qsort(b, n, sizeof(struct buffered_update), compare_buffered_updates); + + for(i = 0; i < n; i++) { + /* The same update may be scheduled multiple times before it is + sent out. Since our buffer is now sorted, it is enough to + compare with the previous update. */ + + if(last_prefix) { + if(b[i].plen == last_plen && + memcmp(b[i].prefix, last_prefix, 16) == 0) + continue; + } + + xroute = find_xroute(b[i].prefix, b[i].plen); + route = find_installed_route(b[i].prefix, b[i].plen); + + if(xroute && (!route || xroute->metric <= kernel_metric)) { + really_send_update(ifp, myid, + xroute->prefix, xroute->plen, + myseqno, xroute->metric, + NULL, 0); + last_prefix = xroute->prefix; + last_plen = xroute->plen; + } else if(route) { + unsigned char channels[DIVERSITY_HOPS]; + int chlen; + struct interface *route_ifp = route->neigh->ifp; + struct babel_interface *babel_route_ifp = NULL; + unsigned short metric; + unsigned short seqno; + + seqno = route->seqno; + metric = + route_interferes(route, ifp) ? + route_metric(route) : + route_metric_noninterfering(route); + + if(metric < INFINITY) + satisfy_request(route->src->prefix, route->src->plen, + seqno, route->src->id, ifp); + if((babel_ifp->flags & BABEL_IF_SPLIT_HORIZON) && + route->neigh->ifp == ifp) + continue; + + babel_route_ifp = babel_get_if_nfo(route_ifp); + if(babel_route_ifp->channel ==BABEL_IF_CHANNEL_NONINTERFERING) { + memcpy(channels, route->channels, DIVERSITY_HOPS); + } else { + if(babel_route_ifp->channel == BABEL_IF_CHANNEL_UNKNOWN) + channels[0] = BABEL_IF_CHANNEL_INTERFERING; + else { + assert(babel_route_ifp->channel > 0 && + babel_route_ifp->channel <= 255); + channels[0] = babel_route_ifp->channel; + } + memcpy(channels + 1, route->channels, DIVERSITY_HOPS - 1); + } + + chlen = channels_len(channels); + really_send_update(ifp, route->src->id, + route->src->prefix, + route->src->plen, + seqno, metric, + channels, chlen); + update_source(route->src, seqno, metric); + last_prefix = route->src->prefix; + last_plen = route->src->plen; + } else { + /* There's no route for this prefix. This can happen shortly + after an xroute has been retracted, so send a retraction. */ + really_send_update(ifp, myid, b[i].prefix, b[i].plen, + myseqno, INFINITY, NULL, -1); + } + } + schedule_flush_now(ifp); + done: + free(b); + } + babel_ifp->update_flush_timeout.tv_sec = 0; + babel_ifp->update_flush_timeout.tv_usec = 0; +} + +static void +schedule_update_flush(struct interface *ifp, int urgent) +{ + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + unsigned msecs; + msecs = update_jitter(babel_ifp, urgent); + if(babel_ifp->update_flush_timeout.tv_sec != 0 && + timeval_minus_msec(&babel_ifp->update_flush_timeout, &babel_now) < msecs) + return; + set_timeout(&babel_ifp->update_flush_timeout, msecs); +} + +static void +buffer_update(struct interface *ifp, + const unsigned char *prefix, unsigned char plen) +{ + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + if(babel_ifp->num_buffered_updates > 0 && + babel_ifp->num_buffered_updates >= babel_ifp->update_bufsize) + flushupdates(ifp); + + if(babel_ifp->update_bufsize == 0) { + int n; + assert(babel_ifp->buffered_updates == NULL); + /* Allocate enough space to hold a full update. Since the + number of installed routes will grow over time, make sure we + have enough space to send a full-ish frame. */ + n = installed_routes_estimate() + xroutes_estimate() + 4; + n = MAX(n, babel_ifp->bufsize / 16); + again: + babel_ifp->buffered_updates = malloc(n *sizeof(struct buffered_update)); + if(babel_ifp->buffered_updates == NULL) { + flog_err(EC_BABEL_MEMORY, "malloc(buffered_updates): %s", + safe_strerror(errno)); + if(n > 4) { + /* Try again with a tiny buffer. */ + n = 4; + goto again; + } + return; + } + babel_ifp->update_bufsize = n; + babel_ifp->num_buffered_updates = 0; + } + + memcpy(babel_ifp->buffered_updates[babel_ifp->num_buffered_updates].prefix, + prefix, 16); + babel_ifp->buffered_updates[babel_ifp->num_buffered_updates].plen = plen; + babel_ifp->num_buffered_updates++; +} + +void +send_update(struct interface *ifp, int urgent, + const unsigned char *prefix, unsigned char plen) +{ + babel_interface_nfo *babel_ifp = NULL; + + if(ifp == NULL) { + struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT); + struct interface *ifp_aux; + struct babel_route *route; + FOR_ALL_INTERFACES(vrf, ifp_aux) + send_update(ifp_aux, urgent, prefix, plen); + if(prefix) { + /* Since flushupdates only deals with non-wildcard interfaces, we + need to do this now. */ + route = find_installed_route(prefix, plen); + if(route && route_metric(route) < INFINITY) + satisfy_request(prefix, plen, route->src->seqno, route->src->id, + NULL); + } + return; + } + + if(!if_up(ifp)) + return; + + babel_ifp = babel_get_if_nfo(ifp); + if(prefix) { + debugf(BABEL_DEBUG_COMMON,"Sending update to %s for %s.", + ifp->name, format_prefix(prefix, plen)); + buffer_update(ifp, prefix, plen); + } else { + struct route_stream *routes = NULL; + send_self_update(ifp); + debugf(BABEL_DEBUG_COMMON,"Sending update to %s for any.", ifp->name); + routes = route_stream(1); + if(routes) { + while(1) { + struct babel_route *route = route_stream_next(routes); + if(route == NULL) + break; + buffer_update(ifp, route->src->prefix, route->src->plen); + } + route_stream_done(routes); + } else { + flog_err(EC_BABEL_MEMORY, "Couldn't allocate route stream."); + } + set_timeout(&babel_ifp->update_timeout, babel_ifp->update_interval); + babel_ifp->last_update_time = babel_now.tv_sec; + } + schedule_update_flush(ifp, urgent); +} + +void +send_update_resend(struct interface *ifp, + const unsigned char *prefix, unsigned char plen) +{ + assert(prefix != NULL); + + send_update(ifp, 1, prefix, plen); + record_resend(RESEND_UPDATE, prefix, plen, 0, NULL, NULL, resend_delay); +} + +void +send_wildcard_retraction(struct interface *ifp) +{ + babel_interface_nfo *babel_ifp = NULL; + if(ifp == NULL) { + struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT); + struct interface *ifp_aux; + FOR_ALL_INTERFACES(vrf, ifp_aux) + 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(void) +{ + myseqno = seqno_plus(myseqno, 1); +} + +void +send_self_update(struct interface *ifp) +{ + struct xroute_stream *xroutes; + if(ifp == NULL) { + struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT); + struct interface *ifp_aux; + FOR_ALL_INTERFACES(vrf, ifp_aux) { + if(!if_up(ifp_aux)) + continue; + send_self_update(ifp_aux); + } + return; + } + + debugf(BABEL_DEBUG_COMMON,"Sending self update to %s.", ifp->name); + xroutes = xroute_stream(); + if(xroutes) { + while(1) { + struct xroute *xroute = xroute_stream_next(xroutes); + if(xroute == NULL) break; + send_update(ifp, 0, xroute->prefix, xroute->plen); + } + xroute_stream_done(xroutes); + } else { + flog_err(EC_BABEL_MEMORY, "Couldn't allocate xroute stream."); + } +} + +void +send_ihu(struct neighbour *neigh, struct interface *ifp) +{ + babel_interface_nfo *babel_ifp = NULL; + int rxcost, interval; + int ll; + int send_rtt_data; + int msglen; + + if(neigh == NULL && ifp == NULL) { + struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT); + struct interface *ifp_aux; + FOR_ALL_INTERFACES(vrf, ifp_aux) { + 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((babel_ifp->flags & BABEL_IF_TIMESTAMPS) && neigh->hello_send_us + /* Checks whether the RTT data is not too old to be sent. */ + && timeval_minus_msec(&babel_now, + &neigh->hello_rtt_receive_time) < 1000000) { + send_rtt_data = 1; + } else { + neigh->hello_send_us = 0; + send_rtt_data = 0; + } + + /* The length depends on the format of the address, and then an + optional 10-bytes sub-TLV for timestamps (used to compute a RTT). */ + msglen = (ll ? 14 : 22) + (send_rtt_data ? 10 : 0); + + if(unicast_neighbour != neigh) { + start_message(ifp, MESSAGE_IHU, msglen); + 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); + if (send_rtt_data) { + accumulate_byte(ifp, SUBTLV_TIMESTAMP); + accumulate_byte(ifp, 8); + accumulate_int(ifp, neigh->hello_send_us); + accumulate_int(ifp, time_us(neigh->hello_rtt_receive_time)); + } + end_message(ifp, MESSAGE_IHU, msglen); + } else { + int rc; + rc = start_unicast_message(neigh, MESSAGE_IHU, msglen); + 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); + if (send_rtt_data) { + accumulate_unicast_byte(neigh, SUBTLV_TIMESTAMP); + accumulate_unicast_byte(neigh, 8); + accumulate_unicast_int(neigh, neigh->hello_send_us); + accumulate_unicast_int(neigh, + time_us(neigh->hello_rtt_receive_time)); + } + end_unicast_message(neigh, MESSAGE_IHU, msglen); + } +} + +/* Send IHUs to all marginal neighbours */ +void +send_marginal_ihu(struct interface *ifp) +{ + struct neighbour *neigh; + FOR_ALL_NEIGHBOURS(neigh) { + if(ifp && neigh->ifp != ifp) + continue; + if(neigh->txcost >= 384 || (neigh->reach & 0xF000) != 0xF000) + send_ihu(neigh, ifp); + } +} + +void +send_request(struct interface *ifp, + const unsigned char *prefix, unsigned char plen) +{ + int v4, pb, len; + + if(ifp == NULL) { + struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT); + struct interface *ifp_aux; + FOR_ALL_INTERFACES(vrf, ifp_aux) { + if(if_up(ifp_aux)) + continue; + send_request(ifp_aux, prefix, plen); + } + return; + } + + /* make sure any buffered updates go out before this request. */ + flushupdates(ifp); + + if(!if_up(ifp)) + return; + + debugf(BABEL_DEBUG_COMMON,"sending request to %s for %s.", + ifp->name, prefix ? format_prefix(prefix, plen) : "any"); + v4 = plen >= 96 && v4mapped(prefix); + pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8; + len = !prefix ? 2 : 2 + pb; + + 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, pb); + else + accumulate_bytes(ifp, prefix, pb); + } + end_message(ifp, MESSAGE_REQUEST, len); +} + +void +send_unicast_request(struct neighbour *neigh, + const unsigned char *prefix, unsigned char plen) +{ + int rc, v4, pb, 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); + pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8; + len = !prefix ? 2 : 2 + pb; + + 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, pb); + else + accumulate_unicast_bytes(neigh, prefix, pb); + } + end_unicast_message(neigh, MESSAGE_REQUEST, len); +} + +void +send_multihop_request(struct interface *ifp, + const unsigned char *prefix, unsigned char plen, + unsigned short seqno, const unsigned char *id, + unsigned short hop_count) +{ + int v4, pb, len; + + /* Make sure any buffered updates go out before this request. */ + flushupdates(ifp); + + if(ifp == NULL) { + struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT); + struct interface *ifp_aux; + FOR_ALL_INTERFACES(vrf, ifp_aux) { + if(!if_up(ifp_aux)) + continue; + send_multihop_request(ifp_aux, prefix, plen, seqno, id, hop_count); + } + return; + } + + if(!if_up(ifp)) + return; + + debugf(BABEL_DEBUG_COMMON,"Sending request (%d) on %s for %s.", + hop_count, ifp->name, format_prefix(prefix, plen)); + v4 = plen >= 96 && v4mapped(prefix); + pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8; + len = 6 + 8 + pb; + + start_message(ifp, MESSAGE_MH_REQUEST, len); + accumulate_byte(ifp, v4 ? 1 : 2); + accumulate_byte(ifp, v4 ? plen - 96 : plen); + accumulate_short(ifp, seqno); + accumulate_byte(ifp, hop_count); + accumulate_byte(ifp, 0); + accumulate_bytes(ifp, id, 8); + if(prefix) { + if(v4) + accumulate_bytes(ifp, prefix + 12, pb); + else + accumulate_bytes(ifp, prefix, pb); + } + end_message(ifp, MESSAGE_MH_REQUEST, len); +} + +void +send_unicast_multihop_request(struct neighbour *neigh, + const unsigned char *prefix, unsigned char plen, + unsigned short seqno, const unsigned char *id, + unsigned short hop_count) +{ + int rc, v4, pb, len; + + /* Make sure any buffered updates go out before this request. */ + flushupdates(neigh->ifp); + + debugf(BABEL_DEBUG_COMMON,"Sending multi-hop request to %s for %s (%d hops).", + format_address(neigh->address), + format_prefix(prefix, plen), hop_count); + v4 = plen >= 96 && v4mapped(prefix); + pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8; + len = 6 + 8 + pb; + + rc = start_unicast_message(neigh, MESSAGE_MH_REQUEST, len); + if(rc < 0) return; + accumulate_unicast_byte(neigh, v4 ? 1 : 2); + accumulate_unicast_byte(neigh, v4 ? plen - 96 : plen); + accumulate_unicast_short(neigh, seqno); + accumulate_unicast_byte(neigh, hop_count); + accumulate_unicast_byte(neigh, 0); + accumulate_unicast_bytes(neigh, id, 8); + if(prefix) { + if(v4) + accumulate_unicast_bytes(neigh, prefix + 12, pb); + else + accumulate_unicast_bytes(neigh, prefix, pb); + } + end_unicast_message(neigh, MESSAGE_MH_REQUEST, len); +} + +void +send_request_resend(struct neighbour *neigh, + const unsigned char *prefix, unsigned char plen, + unsigned short seqno, unsigned char *id) +{ + if(neigh) + send_unicast_multihop_request(neigh, prefix, plen, seqno, id, 127); + else + send_multihop_request(NULL, prefix, plen, seqno, id, 127); + + record_resend(RESEND_REQUEST, prefix, plen, seqno, id, + neigh ? neigh->ifp : NULL, resend_delay); +} + +void +handle_request(struct neighbour *neigh, const unsigned char *prefix, + unsigned char plen, unsigned char hop_count, + unsigned short seqno, const unsigned char *id) +{ + struct xroute *xroute; + struct babel_route *route; + struct neighbour *successor = NULL; + + xroute = find_xroute(prefix, plen); + route = find_installed_route(prefix, plen); + + if(xroute && (!route || xroute->metric <= kernel_metric)) { + if(hop_count > 0 && memcmp(id, myid, 8) == 0) { + if(seqno_compare(seqno, myseqno) > 0) { + if(seqno_minus(seqno, myseqno) > 100) { + /* Hopelessly out-of-date request */ + return; + } + update_myseqno(); + } + } + send_update(neigh->ifp, 1, prefix, plen); + return; + } + + if(route && + (memcmp(id, route->src->id, 8) != 0 || + seqno_compare(seqno, route->seqno) <= 0)) { + send_update(neigh->ifp, 1, prefix, plen); + return; + } + + if(hop_count <= 1) + return; + + if(route && memcmp(id, route->src->id, 8) == 0 && + seqno_minus(seqno, route->seqno) > 100) { + /* Hopelessly out-of-date */ + return; + } + + if(request_redundant(neigh->ifp, prefix, plen, seqno, id)) + return; + + /* Let's try to forward this request. */ + if(route && route_metric(route) < INFINITY) + successor = route->neigh; + + if(!successor || successor == neigh) { + /* We were about to forward a request to its requestor. Try to + find a different neighbour to forward the request to. */ + struct babel_route *other_route; + + other_route = find_best_route(prefix, plen, 0, neigh); + if(other_route && route_metric(other_route) < INFINITY) + successor = other_route->neigh; + } + + if(!successor || successor == neigh) + /* Give up */ + return; + + send_unicast_multihop_request(successor, prefix, plen, seqno, id, + hop_count - 1); + record_resend(RESEND_REQUEST, prefix, plen, seqno, id, + neigh->ifp, 0); +} diff --git a/babeld/message.h b/babeld/message.h new file mode 100644 index 0000000..22db35e --- /dev/null +++ b/babeld/message.h @@ -0,0 +1,102 @@ +/* +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 + +/* A registry of assigned TLV and sub-TLV types is available at + http://www.pps.univ-paris-diderot.fr/~jch/software/babel/babel-tlv-registry.text +*/ +#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 +#define MESSAGE_MAX 10 + +/* Protocol extension through sub-TLVs. */ +#define SUBTLV_PAD1 0 +#define SUBTLV_PADN 1 +#define SUBTLV_DIVERSITY 2 /* Also known as babelz. */ +#define SUBTLV_TIMESTAMP 3 /* Used to compute RTT. */ +#define SUBTLV_MANDATORY 0x80 + +extern unsigned short myseqno; + +extern int broadcast_ihu; +extern int split_horizon; + +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 0000000..d962a09 --- /dev/null +++ b/babeld/neighbour.c @@ -0,0 +1,371 @@ +/* +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. +*/ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#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" +#include "babel_errors.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) +{ + debugf(BABEL_DEBUG_COMMON,"Flushing neighbour %s (reach 0x%04x)", + format_address(neigh->address), neigh->reach); + 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) { + flog_err(EC_BABEL_MEMORY, "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->hello_send_us = 0; + neigh->hello_rtt_receive_time = zero; + neigh->rtt = 0; + neigh->rtt_time = zero; + 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); + rc = 1; + } + + if(hello >= 0) { + neigh->hello_seqno = hello; + neigh->reach >>= 1; + neigh->reach |= 0x8000; + if((neigh->reach & 0xFC00) != 0xFC00) + rc = 1; + } + + /* Make sure to give neighbours some feedback early after association */ + if((neigh->reach & 0xBF00) == 0x8000) { + /* A new neighbour */ + send_hello(neigh->ifp); + } else { + /* Don't send hellos, in order to avoid a positive feedback loop. */ + int a = (neigh->reach & 0xC000); + int b = (neigh->reach & 0x3000); + if((a == 0xC000 && b == 0) || (a == 0 && b == 0x3000)) { + /* Reachability is either 1100 or 0011 */ + send_self_update(neigh->ifp); + } + } + + if((neigh->reach & 0xFC00) == 0xC000) { + /* This is a newish neighbour, let's request a full route dump. + We ought to avoid this when the network is dense */ + send_unicast_request(neigh, NULL, 0); + send_ihu(neigh, NULL); + } + return rc; +} + +static int +reset_txcost(struct neighbour *neigh) +{ + unsigned delay; + + delay = timeval_minus_msec(&babel_now, &neigh->ihu_time); + + if(neigh->ihu_interval > 0 && delay < neigh->ihu_interval * 10U * 3U) + return 0; + + /* If we're losing a lot of packets, we probably lost an IHU too */ + if(delay >= 180000 || (neigh->reach & 0xFFF0) == 0 || + (neigh->ihu_interval > 0 && + delay >= neigh->ihu_interval * 10U * 10U)) { + neigh->txcost = INFINITY; + neigh->ihu_time = babel_now; + return 1; + } + + return 0; +} + +unsigned +neighbour_txcost(struct neighbour *neigh) +{ + return neigh->txcost; +} + +unsigned +check_neighbours(void) +{ + struct neighbour *neigh; + int changed, rc; + unsigned msecs = 50000; + + debugf(BABEL_DEBUG_COMMON,"Checking neighbours."); + + neigh = neighs; + while(neigh) { + changed = update_neighbour(neigh, -1, 0); + + if(neigh->reach == 0 || + neigh->hello_time.tv_sec > babel_now.tv_sec || /* clock stepped */ + timeval_minus_msec(&babel_now, &neigh->hello_time) > 300000) { + struct neighbour *old = neigh; + neigh = neigh->next; + flush_neighbour(old); + continue; + } + + rc = reset_txcost(neigh); + changed = changed || rc; + + update_neighbour_metric(neigh, changed); + + if(neigh->hello_interval > 0) + msecs = MIN(msecs, neigh->hello_interval * 10U); + if(neigh->ihu_interval > 0) + msecs = MIN(msecs, neigh->ihu_interval * 10U); + neigh = neigh->next; + } + + return msecs; +} + +unsigned +neighbour_rxcost(struct neighbour *neigh) +{ + unsigned delay; + unsigned short reach = neigh->reach; + + delay = timeval_minus_msec(&babel_now, &neigh->hello_time); + + if((reach & 0xFFF0) == 0 || delay >= 180000) { + return INFINITY; + } else if(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ) { + int sreach = + ((reach & 0x8000) >> 2) + + ((reach & 0x4000) >> 1) + + (reach & 0x3FFF); + /* 0 <= sreach <= 0x7FFF */ + int cost = (0x8000 * babel_get_if_nfo(neigh->ifp)->cost) / (sreach + 1); + /* cost >= interface->cost */ + if(delay >= 40000) + cost = (cost * (delay - 20000) + 10000) / 20000; + return MIN(cost, INFINITY); + } else { + /* To lose one hello is a misfortune, to lose two is carelessness. */ + if((reach & 0xC000) == 0xC000) + return babel_get_if_nfo(neigh->ifp)->cost; + else if((reach & 0xC000) == 0) + return INFINITY; + else if((reach & 0x2000)) + return babel_get_if_nfo(neigh->ifp)->cost; + else + return INFINITY; + } +} + +unsigned +neighbour_rttcost(struct neighbour *neigh) +{ + struct interface *ifp = neigh->ifp; + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + + if(!babel_ifp->max_rtt_penalty || !valid_rtt(neigh)) + return 0; + + /* Function: linear behaviour between rtt_min and rtt_max. */ + if(neigh->rtt <= babel_ifp->rtt_min) { + return 0; + } else if(neigh->rtt <= babel_ifp->rtt_max) { + unsigned long long tmp = + (unsigned long long)babel_ifp->max_rtt_penalty * + (neigh->rtt - babel_ifp->rtt_min) / + (babel_ifp->rtt_max - babel_ifp->rtt_min); + assert((tmp & 0x7FFFFFFF) == tmp); + return tmp; + } else { + return babel_ifp->max_rtt_penalty; + } +} + +unsigned +neighbour_cost(struct neighbour *neigh) +{ + unsigned a, b, cost; + + 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)) { + cost = 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. */ + cost = (a * b + 128) >> 8; + } + + cost += neighbour_rttcost(neigh); + + return MIN(cost, INFINITY); +} + +int +valid_rtt(struct neighbour *neigh) +{ + return (timeval_minus_msec(&babel_now, &neigh->rtt_time) < 180000) ? 1 : 0; +} diff --git a/babeld/neighbour.h b/babeld/neighbour.h new file mode 100644 index 0000000..39ee7e4 --- /dev/null +++ b/babeld/neighbour.h @@ -0,0 +1,64 @@ +/* +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_NEIGHBOUR_H +#define BABEL_NEIGHBOUR_H + +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 */ + /* Used for RTT estimation. */ + /* Absolute time (modulo 2^32) at which the Hello was sent, + according to remote clock. */ + unsigned int hello_send_us; + struct timeval hello_rtt_receive_time; + unsigned int rtt; + struct timeval rtt_time; + 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_rttcost(struct neighbour *neigh); +unsigned neighbour_cost(struct neighbour *neigh); +int valid_rtt(struct neighbour *neigh); + +#endif /* BABEL_NEIGHBOUR_H */ diff --git a/babeld/net.c b/babeld/net.c new file mode 100644 index 0000000..40716a7 --- /dev/null +++ b/babeld/net.c @@ -0,0 +1,222 @@ +/* +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. +*/ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#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 <netinet/in_systm.h> +#include <netinet/ip.h> +#include <arpa/inet.h> +#include <errno.h> + +#include "babeld.h" +#include "util.h" +#include "net.h" +#include "sockopt.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; + + setsockopt_ipv6_tclass (s, IPTOS_PREC_INTERNETCONTROL); + + rc = fcntl(s, F_GETFL, 0); + if(rc < 0) + goto fail; + + rc = fcntl(s, F_SETFL, (rc | O_NONBLOCK)); + if(rc < 0) + goto fail; + + rc = fcntl(s, F_GETFD, 0); + if(rc < 0) + goto fail; + + rc = fcntl(s, F_SETFD, rc | FD_CLOEXEC); + if(rc < 0) + goto fail; + + memset(&sin6, 0, sizeof(sin6)); + sin6.sin6_family = AF_INET6; + sin6.sin6_port = htons(port); + rc = bind(s, (struct sockaddr*)&sin6, sizeof(sin6)); + if(rc < 0) + goto fail; + + return s; + + fail: + saved_errno = errno; + close(s); + errno = saved_errno; + return -1; +} + +int +babel_recv(int s, void *buf, int buflen, struct sockaddr *sin, int slen) +{ + struct iovec iovec; + struct msghdr msg; + int rc; + + memset(&msg, 0, sizeof(msg)); + iovec.iov_base = buf; + iovec.iov_len = buflen; + msg.msg_name = sin; + msg.msg_namelen = slen; + msg.msg_iov = &iovec; + msg.msg_iovlen = 1; + + rc = recvmsg(s, &msg, 0); + return rc; +} + +int +babel_send(int s, + void *buf1, int buflen1, void *buf2, int buflen2, + struct sockaddr *sin, int slen) +{ + struct iovec iovec[2]; + struct msghdr msg; + int rc; + + iovec[0].iov_base = buf1; + iovec[0].iov_len = buflen1; + iovec[1].iov_base = buf2; + iovec[1].iov_len = buflen2; + memset(&msg, 0, sizeof(msg)); + msg.msg_name = 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 0000000..b3ca376 --- /dev/null +++ b/babeld/net.h @@ -0,0 +1,33 @@ +/* +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_NET_H +#define BABEL_NET_H + +int babel_socket(int port); +int babel_recv(int s, void *buf, int buflen, struct sockaddr *sin, int slen); +int babel_send(int s, + void *buf1, int buflen1, void *buf2, int buflen2, + struct sockaddr *sin, int slen); +int tcp_server_socket(int port, int local); + +#endif /* BABEL_NET_H */ diff --git a/babeld/resend.c b/babeld/resend.c new file mode 100644 index 0000000..f08897f --- /dev/null +++ b/babeld/resend.c @@ -0,0 +1,318 @@ +/* +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. +*/ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <sys/time.h> +#include <time.h> +#include <string.h> +#include <stdlib.h> + +#include <zebra.h> +#include "if.h" + +#include "babel_main.h" +#include "babeld.h" +#include "util.h" +#include "neighbour.h" +#include "resend.h" +#include "message.h" +#include "babel_interface.h" + +struct timeval resend_time = {0, 0}; +struct resend *to_resend = NULL; + +static int +resend_match(struct resend *resend, + int kind, const unsigned char *prefix, unsigned char plen) +{ + return (resend->kind == kind && + resend->plen == plen && memcmp(resend->prefix, prefix, 16) == 0); +} + +/* This is called by neigh.c when a neighbour is flushed */ + +void +flush_resends(struct neighbour *neigh) +{ + /* Nothing for now */ +} + +static struct resend * +find_resend(int kind, const unsigned char *prefix, unsigned char plen, + struct resend **previous_return) +{ + struct resend *current, *previous; + + previous = NULL; + current = to_resend; + while(current) { + if(resend_match(current, kind, prefix, plen)) { + if(previous_return) + *previous_return = previous; + return current; + } + previous = current; + current = current->next; + } + + return NULL; +} + +struct resend * +find_request(const unsigned char *prefix, unsigned char plen, + struct resend **previous_return) +{ + return find_resend(RESEND_REQUEST, prefix, plen, previous_return); +} + +int +record_resend(int kind, const unsigned char *prefix, unsigned char plen, + unsigned short seqno, const unsigned char *id, + struct interface *ifp, int delay) +{ + struct resend *resend; + unsigned int ifindex = ifp ? ifp->ifindex : 0; + + if((kind == RESEND_REQUEST && + input_filter(NULL, prefix, plen, NULL, ifindex) >= INFINITY) || + (kind == RESEND_UPDATE && + output_filter(NULL, prefix, plen, ifindex) >= INFINITY)) + return 0; + + if(delay >= 0xFFFF) + delay = 0xFFFF; + + resend = find_resend(kind, prefix, plen, NULL); + if(resend) { + if(resend->delay && delay) + resend->delay = MIN(resend->delay, delay); + else if(delay) + resend->delay = delay; + resend->time = babel_now; + resend->max = RESEND_MAX; + if(id && memcmp(resend->id, id, 8) == 0 && + seqno_compare(resend->seqno, seqno) > 0) { + return 0; + } + if(id) + memcpy(resend->id, id, 8); + else + memset(resend->id, 0, 8); + resend->seqno = seqno; + if(resend->ifp != ifp) + resend->ifp = NULL; + } else { + resend = malloc(sizeof(struct resend)); + if(resend == NULL) + return -1; + resend->kind = kind; + resend->max = RESEND_MAX; + resend->delay = delay; + memcpy(resend->prefix, prefix, 16); + resend->plen = plen; + resend->seqno = seqno; + if(id) + memcpy(resend->id, id, 8); + else + memset(resend->id, 0, 8); + resend->ifp = ifp; + resend->time = babel_now; + resend->next = to_resend; + to_resend = resend; + } + + if(resend->delay) { + struct timeval timeout; + timeval_add_msec(&timeout, &resend->time, resend->delay); + timeval_min(&resend_time, &timeout); + } + return 1; +} + +static int +resend_expired(struct resend *resend) +{ + switch(resend->kind) { + case RESEND_REQUEST: + return timeval_minus_msec(&babel_now, &resend->time) >= REQUEST_TIMEOUT; + default: + return resend->max <= 0; + } +} + +int +unsatisfied_request(const unsigned char *prefix, unsigned char plen, + unsigned short seqno, const unsigned char *id) +{ + struct resend *request; + + request = find_request(prefix, plen, NULL); + if(request == NULL || resend_expired(request)) + return 0; + + if(memcmp(request->id, id, 8) != 0 || + seqno_compare(request->seqno, seqno) <= 0) + return 1; + + return 0; +} + +/* Determine whether a given request should be forwarded. */ +int +request_redundant(struct interface *ifp, + const unsigned char *prefix, unsigned char plen, + unsigned short seqno, const unsigned char *id) +{ + struct resend *request; + + request = find_request(prefix, plen, NULL); + if(request == NULL || resend_expired(request)) + return 0; + + if(memcmp(request->id, id, 8) == 0 && + seqno_compare(request->seqno, seqno) > 0) + return 0; + + if(request->ifp != NULL && request->ifp != ifp) + return 0; + + if(request->max > 0) + /* Will be resent. */ + return 1; + + if(timeval_minus_msec(&babel_now, &request->time) < + (ifp ? MIN(babel_get_if_nfo(ifp)->hello_interval, 1000) : 1000)) + /* Fairly recent. */ + return 1; + + return 0; +} + +int +satisfy_request(const unsigned char *prefix, unsigned char plen, + unsigned short seqno, const unsigned char *id, + struct interface *ifp) +{ + struct resend *request, *previous; + + request = find_request(prefix, plen, &previous); + if(request == NULL) + return 0; + + if(ifp != NULL && request->ifp != ifp) + return 0; + + if(memcmp(request->id, id, 8) != 0 || + seqno_compare(request->seqno, seqno) <= 0) { + /* We cannot remove the request, as we may be walking the list right + now. Mark it as expired, so that expire_resend will remove it. */ + request->max = 0; + request->time.tv_sec = 0; + recompute_resend_time(); + return 1; + } + + return 0; +} + +void +expire_resend(void) +{ + 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(void) +{ + 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(void) +{ + 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 0000000..72b6986 --- /dev/null +++ b/babeld/resend.h @@ -0,0 +1,65 @@ +/* +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_RESEND_H +#define BABEL_RESEND_H + +#define REQUEST_TIMEOUT 65000 +#define RESEND_MAX 3 + +#define RESEND_REQUEST 1 +#define RESEND_UPDATE 2 + +struct resend { + unsigned char kind; + unsigned char max; + unsigned short delay; + struct timeval time; + unsigned char prefix[16]; + unsigned char plen; + unsigned short seqno; + unsigned char id[8]; + struct interface *ifp; + struct resend *next; +}; + +extern struct timeval resend_time; + +struct resend *find_request(const unsigned char *prefix, unsigned char plen, + struct resend **previous_return); +void flush_resends(struct neighbour *neigh); +int record_resend(int kind, const unsigned char *prefix, unsigned char plen, + unsigned short seqno, const unsigned char *id, + struct interface *ifp, int delay); +int unsatisfied_request(const unsigned char *prefix, unsigned char plen, + unsigned short seqno, const unsigned char *id); +int request_redundant(struct interface *ifp, + const unsigned char *prefix, unsigned char plen, + unsigned short seqno, const unsigned char *id); +int satisfy_request(const unsigned char *prefix, unsigned char plen, + unsigned short seqno, const unsigned char *id, + struct interface *ifp); + +void expire_resend(void); +void recompute_resend_time(void); +void do_resend(void); + +#endif /* BABEL_RESEND_H */ diff --git a/babeld/route.c b/babeld/route.c new file mode 100644 index 0000000..8dd1e40 --- /dev/null +++ b/babeld/route.c @@ -0,0 +1,1146 @@ +/* +Copyright (c) 2007, 2008 by Juliusz Chroboczek +Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. +*/ + +#include <zebra.h> +#include "if.h" + +#include "babeld.h" +#include "util.h" +#include "kernel.h" +#include "babel_interface.h" +#include "source.h" +#include "neighbour.h" +#include "route.h" +#include "xroute.h" +#include "message.h" +#include "resend.h" +#include "babel_errors.h" + +static void consider_route(struct babel_route *route); + +struct babel_route **routes = NULL; +static int route_slots = 0, max_route_slots = 0; +int kernel_metric = 0; +enum babel_diversity diversity_kind = DIVERSITY_NONE; +int diversity_factor = BABEL_DEFAULT_DIVERSITY_FACTOR; +int keep_unfeasible = 0; + +int smoothing_half_life = 0; +static int two_to_the_one_over_hl = 0; /* 2^(1/hl) * 0x10000 */ + +/* We maintain a list of "slots", ordered by prefix. Every slot + contains a linked list of the routes to this prefix, with the + installed route, if any, at the head of the list. */ + +static int +route_compare(const unsigned char *prefix, unsigned char plen, + struct babel_route *route) +{ + int i = memcmp(prefix, route->src->prefix, 16); + if(i != 0) + return i; + + if(plen < route->src->plen) + return -1; + else if(plen > route->src->plen) + return 1; + else + return 0; +} + +/* Performs binary search, returns -1 in case of failure. In the latter + case, new_return is the place where to insert the new element. */ + +static int +find_route_slot(const unsigned char *prefix, unsigned char plen, + int *new_return) +{ + int p, m, g, c; + + if(route_slots < 1) { + if(new_return) + *new_return = 0; + return -1; + } + + p = 0; g = route_slots - 1; + + do { + m = (p + g) / 2; + c = route_compare(prefix, plen, routes[m]); + if(c == 0) + return m; + else if(c < 0) + g = m - 1; + else + p = m + 1; + } while(p <= g); + + if(new_return) + *new_return = p; + + return -1; +} + +struct babel_route * +find_route(const unsigned char *prefix, unsigned char plen, + struct neighbour *neigh, const unsigned char *nexthop) +{ + struct babel_route *route; + int i = find_route_slot(prefix, plen, NULL); + + if(i < 0) + return NULL; + + route = routes[i]; + + while(route) { + if(route->neigh == neigh && memcmp(route->nexthop, nexthop, 16) == 0) + return route; + route = route->next; + } + + return NULL; +} + +struct babel_route * +find_installed_route(const unsigned char *prefix, unsigned char plen) +{ + int i = find_route_slot(prefix, plen, NULL); + + if(i >= 0 && routes[i]->installed) + return routes[i]; + + return NULL; +} + +/* Returns an overestimate of the number of installed routes. */ +int +installed_routes_estimate(void) +{ + return route_slots; +} + +static int +resize_route_table(int new_slots) +{ + struct babel_route **new_routes; + assert(new_slots >= route_slots); + + if(new_slots == 0) { + new_routes = NULL; + free(routes); + } else { + new_routes = realloc(routes, new_slots * sizeof(struct babel_route*)); + if(new_routes == NULL) + return -1; + } + + max_route_slots = new_slots; + routes = new_routes; + return 1; +} + +/* Insert a route into the table. If successful, retains the route. + On failure, caller must free the route. */ +static struct babel_route * +insert_route(struct babel_route *route) +{ + int i, n = 0; + + assert(!route->installed); + + i = find_route_slot(route->src->prefix, route->src->plen, &n); + + if(i < 0) { + if(route_slots >= max_route_slots) + resize_route_table(max_route_slots < 1 ? 8 : 2 * max_route_slots); + if(route_slots >= max_route_slots) + return NULL; + assert(routes); + route->next = NULL; + if(n < route_slots) + memmove(routes + n + 1, routes + n, + (route_slots - n) * sizeof(struct babel_route*)); + route_slots++; + routes[n] = route; + } else { + struct babel_route *r; + r = routes[i]; + while(r->next) + r = r->next; + r->next = route; + route->next = NULL; + } + + return route; +} + +void +flush_route(struct babel_route *route) +{ + int i; + struct source *src; + unsigned oldmetric; + int lost = 0; + + oldmetric = route_metric(route); + src = route->src; + + if(route->installed) { + uninstall_route(route); + lost = 1; + } + + i = find_route_slot(route->src->prefix, route->src->plen, NULL); + assert(i >= 0 && i < route_slots); + + if(route == routes[i]) { + routes[i] = route->next; + route->next = NULL; + free(route); + + if(routes[i] == NULL) { + if(i < route_slots - 1) + memmove(routes + i, routes + i + 1, + (route_slots - i - 1) * sizeof(struct babel_route*)); + routes[route_slots - 1] = NULL; + route_slots--; + } + + if(route_slots == 0) + resize_route_table(0); + else if(max_route_slots > 8 && route_slots < max_route_slots / 4) + resize_route_table(max_route_slots / 2); + } else { + struct babel_route *r = routes[i]; + while(r->next != route) + r = r->next; + r->next = route->next; + route->next = NULL; + free(route); + } + + if(lost) + route_lost(src, oldmetric); + + release_source(src); +} + +void +flush_all_routes(void) +{ + int i; + + /* Start from the end, to avoid shifting the table. */ + i = route_slots - 1; + while(i >= 0) { + while(i < route_slots) { + /* Uninstall first, to avoid calling route_lost. */ + if(routes[i]->installed) + uninstall_route(routes[i]); + flush_route(routes[i]); + } + i--; + } + + check_sources_released(); +} + +void +flush_neighbour_routes(struct neighbour *neigh) +{ + int i; + + i = 0; + while(i < route_slots) { + struct babel_route *r; + r = routes[i]; + while(r) { + if(r->neigh == neigh) { + flush_route(r); + goto again; + } + r = r->next; + } + i++; + again: + ; + } +} + +void +flush_interface_routes(struct interface *ifp, int v4only) +{ + int i; + + i = 0; + while(i < route_slots) { + struct babel_route *r; + r = routes[i]; + while(r) { + if(r->neigh->ifp == ifp && + (!v4only || v4mapped(r->nexthop))) { + flush_route(r); + goto again; + } + r = r->next; + } + i++; + again: + ; + } +} + +struct route_stream { + int installed; + int index; + struct babel_route *next; +}; + + +struct route_stream * +route_stream(int installed) +{ + struct route_stream *stream; + + stream = malloc(sizeof(struct route_stream)); + if(stream == NULL) + return NULL; + + stream->installed = installed; + stream->index = installed ? 0 : -1; + stream->next = NULL; + + return stream; +} + +struct babel_route * +route_stream_next(struct route_stream *stream) +{ + if(stream->installed) { + while(stream->index < route_slots && !routes[stream->index]->installed) + stream->index++; + + if(stream->index < route_slots) + return routes[stream->index++]; + else + return NULL; + } else { + struct babel_route *next; + if(!stream->next) { + stream->index++; + if(stream->index >= route_slots) + return NULL; + stream->next = routes[stream->index]; + } + next = stream->next; + stream->next = next->next; + return next; + } +} + +void +route_stream_done(struct route_stream *stream) +{ + free(stream); +} + +static int +metric_to_kernel(int metric) +{ + return metric < INFINITY ? kernel_metric : KERNEL_INFINITY; +} + +/* This is used to maintain the invariant that the installed route is at + the head of the list. */ +static void +move_installed_route(struct babel_route *route, int i) +{ + assert(i >= 0 && i < route_slots); + assert(route->installed); + + if(route != routes[i]) { + struct babel_route *r = routes[i]; + while(r->next != route) + r = r->next; + r->next = route->next; + route->next = routes[i]; + routes[i] = route; + } +} + +void +install_route(struct babel_route *route) +{ + int i, rc; + + if(route->installed) + return; + + if(!route_feasible(route)) + flog_err(EC_BABEL_ROUTE, + "Installing unfeasible route (this shouldn't happen)."); + + i = find_route_slot(route->src->prefix, route->src->plen, NULL); + assert(i >= 0 && i < route_slots); + + if(routes[i] != route && routes[i]->installed) { + flog_err( + EC_BABEL_ROUTE, + "Attempting to install duplicate route (this shouldn't happen)."); + return; + } + + rc = kernel_route(ROUTE_ADD, route->src->prefix, route->src->plen, + route->nexthop, + route->neigh->ifp->ifindex, + metric_to_kernel(route_metric(route)), NULL, 0, 0); + if(rc < 0) { + int save = errno; + flog_err(EC_BABEL_ROUTE, "kernel_route(ADD): %s", + safe_strerror(errno)); + if(save != EEXIST) + return; + } + route->installed = 1; + move_installed_route(route, i); + +} + +void +uninstall_route(struct babel_route *route) +{ + int rc; + + if(!route->installed) + return; + + rc = kernel_route(ROUTE_FLUSH, route->src->prefix, route->src->plen, + route->nexthop, + route->neigh->ifp->ifindex, + metric_to_kernel(route_metric(route)), NULL, 0, 0); + if(rc < 0) + flog_err(EC_BABEL_ROUTE, "kernel_route(FLUSH): %s", + safe_strerror(errno)); + + route->installed = 0; +} + +/* This is equivalent to uninstall_route followed with install_route, + but without the race condition. The destination of both routes + must be the same. */ + +static void +switch_routes(struct babel_route *old, struct babel_route *new) +{ + int rc; + + if(!old) { + install_route(new); + return; + } + + if(!old->installed) + return; + + if(!route_feasible(new)) + flog_err(EC_BABEL_ROUTE, + "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) { + flog_err(EC_BABEL_ROUTE, "kernel_route(MODIFY): %s", + safe_strerror(errno)); + return; + } + + old->installed = 0; + new->installed = 1; + move_installed_route(new, find_route_slot(new->src->prefix, new->src->plen, + NULL)); +} + +static void +change_route_metric(struct babel_route *route, + unsigned refmetric, unsigned cost, unsigned add) +{ + int old, new; + int newmetric = MIN(refmetric + cost + add, INFINITY); + + old = metric_to_kernel(route_metric(route)); + new = metric_to_kernel(newmetric); + + if(route->installed && old != new) { + int rc; + rc = kernel_route(ROUTE_MODIFY, route->src->prefix, route->src->plen, + route->nexthop, route->neigh->ifp->ifindex, + old, + route->nexthop, route->neigh->ifp->ifindex, + new); + if(rc < 0) { + flog_err(EC_BABEL_ROUTE, "kernel_route(MODIFY metric): %s", + safe_strerror(errno)); + return; + } + } + + /* Update route->smoothed_metric using the old metric. */ + route_smoothed_metric(route); + + route->refmetric = refmetric; + route->cost = cost; + route->add_metric = add; + + if(smoothing_half_life == 0) { + route->smoothed_metric = route_metric(route); + route->smoothed_metric_time = babel_now.tv_sec; + } +} + +static void +retract_route(struct babel_route *route) +{ + /* We cannot simply remove the route from the kernel, as that might + cause a routing loop -- see RFC 6126 Sections 2.8 and 3.5.5. */ + change_route_metric(route, INFINITY, INFINITY, 0); +} + +int +route_feasible(struct babel_route *route) +{ + return update_feasible(route->src, route->seqno, route->refmetric); +} + +int +route_old(struct babel_route *route) +{ + return route->time < babel_now.tv_sec - route->hold_time * 7 / 8; +} + +int +route_expired(struct babel_route *route) +{ + return route->time < babel_now.tv_sec - route->hold_time; +} + +static int +channels_interfere(int ch1, int ch2) +{ + if(ch1 == BABEL_IF_CHANNEL_NONINTERFERING + || ch2 == BABEL_IF_CHANNEL_NONINTERFERING) + return 0; + if(ch1 == BABEL_IF_CHANNEL_INTERFERING + || ch2 == BABEL_IF_CHANNEL_INTERFERING) + return 1; + return ch1 == ch2; +} + +int +route_interferes(struct babel_route *route, struct interface *ifp) +{ + struct babel_interface *babel_ifp = NULL; + switch(diversity_kind) { + case DIVERSITY_NONE: + return 1; + case DIVERSITY_INTERFACE_1: + return route->neigh->ifp == ifp; + case DIVERSITY_CHANNEL_1: + case DIVERSITY_CHANNEL: + if(route->neigh->ifp == ifp) + return 1; + babel_ifp = babel_get_if_nfo(ifp); + if(channels_interfere(babel_ifp->channel, + babel_get_if_nfo(route->neigh->ifp)->channel)) + return 1; + if(diversity_kind == DIVERSITY_CHANNEL) { + int i; + for(i = 0; i < DIVERSITY_HOPS; i++) { + if(route->channels[i] == 0) + break; + if(channels_interfere(babel_ifp->channel, route->channels[i])) + return 1; + } + } + return 0; + } + + return 1; +} + +int +update_feasible(struct source *src, + unsigned short seqno, unsigned short refmetric) +{ + if(src == NULL) + return 1; + + if(src->time < babel_now.tv_sec - SOURCE_GC_TIME) + /* Never mind what is probably stale data */ + return 1; + + if(refmetric >= INFINITY) + /* Retractions are always feasible */ + return 1; + + return (seqno_compare(seqno, src->seqno) > 0 || + (src->seqno == seqno && refmetric < src->metric)); +} + +void +change_smoothing_half_life(int half_life) +{ + if(half_life <= 0) { + smoothing_half_life = 0; + two_to_the_one_over_hl = 0; + return; + } + + smoothing_half_life = half_life; + switch(smoothing_half_life) { + case 1: two_to_the_one_over_hl = 131072; break; + case 2: two_to_the_one_over_hl = 92682; break; + case 3: two_to_the_one_over_hl = 82570; break; + case 4: two_to_the_one_over_hl = 77935; break; + default: + /* 2^(1/x) is 1 + log(2)/x + O(1/x^2) at infinity. */ + two_to_the_one_over_hl = 0x10000 + 45426 / half_life; + } +} + +/* Update the smoothed metric, return the new value. */ +int +route_smoothed_metric(struct babel_route *route) +{ + int metric = route_metric(route); + + if(smoothing_half_life <= 0 || /* no smoothing */ + metric >= INFINITY || /* route retracted */ + route->smoothed_metric_time > babel_now.tv_sec || /* clock stepped */ + route->smoothed_metric == metric) { /* already converged */ + route->smoothed_metric = metric; + route->smoothed_metric_time = babel_now.tv_sec; + } else { + int diff; + /* We randomise the computation, to minimise global synchronisation + and hence oscillations. */ + while(route->smoothed_metric_time <= + babel_now.tv_sec - smoothing_half_life) { + diff = metric - route->smoothed_metric; + route->smoothed_metric += roughly(diff) / 2; + route->smoothed_metric_time += smoothing_half_life; + } + while(route->smoothed_metric_time < babel_now.tv_sec) { + diff = metric - route->smoothed_metric; + route->smoothed_metric += + roughly(diff) * (two_to_the_one_over_hl - 0x10000) / 0x10000; + route->smoothed_metric_time++; + } + + diff = metric - route->smoothed_metric; + if(diff > -4 && diff < 4) + route->smoothed_metric = metric; + } + + /* change_route_metric relies on this */ + assert(route->smoothed_metric_time == babel_now.tv_sec); + return route->smoothed_metric; +} + +static int +route_acceptable(struct babel_route *route, int feasible, + struct neighbour *exclude) +{ + if(route_expired(route)) + return 0; + if(feasible && !route_feasible(route)) + return 0; + if(exclude && route->neigh == exclude) + return 0; + return 1; +} + +/* Find the best route according to the weak ordering. Any + linearisation of the strong ordering (see consider_route) will do, + we use sm <= sm'. We could probably use a lexical ordering, but + that's probably overkill. */ + +struct babel_route * +find_best_route(const unsigned char *prefix, unsigned char plen, int feasible, + struct neighbour *exclude) +{ + struct babel_route *route = NULL, *r = NULL; + int i = find_route_slot(prefix, plen, NULL); + + if(i < 0) + return NULL; + + route = routes[i]; + while(route && !route_acceptable(route, feasible, exclude)) + route = route->next; + + if(!route) + return NULL; + + r = route->next; + while(r) { + if(route_acceptable(r, feasible, exclude) && + (route_smoothed_metric(r) < route_smoothed_metric(route))) + route = r; + r = r->next; + } + + return route; +} + +void +update_route_metric(struct babel_route *route) +{ + int oldmetric = route_metric(route); + int old_smoothed_metric = route_smoothed_metric(route); + + if(route_expired(route)) { + if(route->refmetric < INFINITY) { + route->seqno = seqno_plus(route->src->seqno, 1); + retract_route(route); + if(oldmetric < INFINITY) + route_changed(route, route->src, oldmetric); + } + } else { + struct neighbour *neigh = route->neigh; + int add_metric = input_filter(route->src->id, + route->src->prefix, route->src->plen, + neigh->address, + neigh->ifp->ifindex); + change_route_metric(route, route->refmetric, + neighbour_cost(route->neigh), add_metric); + if(route_metric(route) != oldmetric || + route_smoothed_metric(route) != old_smoothed_metric) + 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; + + for(i = 0; i < route_slots; i++) { + struct babel_route *r = routes[i]; + while(r) { + if(r->neigh == neigh) + update_route_metric(r); + r = r->next; + } + } + } +} + +void +update_interface_metric(struct interface *ifp) +{ + int i; + + for(i = 0; i < route_slots; i++) { + struct babel_route *r = routes[i]; + while(r) { + if(r->neigh->ifp == ifp) + update_route_metric(r); + r = r->next; + } + } +} + +/* This is called whenever we receive an update. */ +struct babel_route * +update_route(const unsigned char *router_id, + const unsigned char *prefix, unsigned char plen, + unsigned short seqno, unsigned short refmetric, + unsigned short interval, + struct neighbour *neigh, const unsigned char *nexthop, + const unsigned char *channels, int channels_len) +{ + struct babel_route *route; + struct source *src; + int metric, feasible; + int add_metric; + int hold_time = MAX((4 * interval) / 100 + interval / 50, 15); + + if(memcmp(router_id, myid, 8) == 0) + return NULL; + + if(martian_prefix(prefix, plen)) { + flog_err(EC_BABEL_ROUTE, "Rejecting martian route to %s through %s.", + format_prefix(prefix, plen), format_address(nexthop)); + return NULL; + } + + add_metric = input_filter(router_id, prefix, plen, + neigh->address, neigh->ifp->ifindex); + if(add_metric >= INFINITY) + return NULL; + + route = find_route(prefix, plen, neigh, nexthop); + + if(route && memcmp(route->src->id, router_id, 8) == 0) + /* Avoid scanning the source table. */ + src = route->src; + else + src = find_source(router_id, prefix, plen, 1, seqno); + + if(src == NULL) + return NULL; + + feasible = update_feasible(src, seqno, refmetric); + metric = MIN((int)refmetric + neighbour_cost(neigh) + add_metric, INFINITY); + + if(route) { + struct source *oldsrc; + unsigned short oldmetric; + int lost = 0; + + oldsrc = route->src; + oldmetric = route_metric(route); + + /* If a successor switches sources, we must accept his update even + if it makes a route unfeasible in order to break any routing loops + in a timely manner. If the source remains the same, we ignore + the update. */ + if(!feasible && route->installed) { + debugf(BABEL_DEBUG_COMMON,"Unfeasible update for installed route to %s (%s %d %d -> %s %d %d).", + format_prefix(src->prefix, src->plen), + format_eui64(route->src->id), + route->seqno, route->refmetric, + format_eui64(src->id), seqno, refmetric); + if(src != route->src) { + uninstall_route(route); + lost = 1; + } + } + + route->src = retain_source(src); + if((feasible || keep_unfeasible) && refmetric < INFINITY) + route->time = babel_now.tv_sec; + route->seqno = seqno; + + memset(&route->channels, 0, sizeof(route->channels)); + if(channels_len > 0) + memcpy(&route->channels, channels, + MIN(channels_len, DIVERSITY_HOPS)); + + change_route_metric(route, + refmetric, neighbour_cost(neigh), add_metric); + route->hold_time = hold_time; + + route_changed(route, oldsrc, oldmetric); + if(lost) + route_lost(oldsrc, oldmetric); + + if(!feasible) + send_unfeasible_request(neigh, route->installed && route_old(route), + seqno, metric, src); + release_source(oldsrc); + } else { + struct babel_route *new_route; + + if(refmetric >= INFINITY) + /* Somebody's retracting a route we never saw. */ + return NULL; + if(!feasible) { + send_unfeasible_request(neigh, 0, seqno, metric, src); + if(!keep_unfeasible) + return NULL; + } + + route = malloc(sizeof(struct babel_route)); + if(route == NULL) { + perror("malloc(route)"); + return NULL; + } + + route->src = retain_source(src); + route->refmetric = refmetric; + route->cost = neighbour_cost(neigh); + route->add_metric = add_metric; + route->seqno = seqno; + route->neigh = neigh; + memcpy(route->nexthop, nexthop, 16); + route->time = babel_now.tv_sec; + route->hold_time = hold_time; + route->smoothed_metric = MAX(route_metric(route), INFINITY / 2); + route->smoothed_metric_time = babel_now.tv_sec; + route->installed = 0; + memset(&route->channels, 0, sizeof(route->channels)); + if(channels_len > 0) + memcpy(&route->channels, channels, + MIN(channels_len, DIVERSITY_HOPS)); + route->next = NULL; + new_route = insert_route(route); + if(new_route == NULL) { + flog_err(EC_BABEL_ROUTE, "Couldn't insert route."); + free(route); + return NULL; + } + consider_route(route); + } + return route; +} + +/* We just received an unfeasible update. If it's any good, send + a request for a new seqno. */ +void +send_unfeasible_request(struct neighbour *neigh, int force, + unsigned short seqno, unsigned short metric, + struct source *src) +{ + struct babel_route *route = find_installed_route(src->prefix, src->plen); + + if(seqno_minus(src->seqno, seqno) > 100) { + /* Probably a source that lost its seqno. Let it time-out. */ + return; + } + + if(force || !route || route_metric(route) >= metric + 512) { + send_unicast_multihop_request(neigh, src->prefix, src->plen, + src->metric >= INFINITY ? + src->seqno : + seqno_plus(src->seqno, 1), + src->id, 127); + } +} + +/* This takes a feasible route and decides whether to install it. + This uses the strong ordering, which is defined by sm <= sm' AND + m <= m'. This ordering is not total, which is what causes + hysteresis. */ + +static void +consider_route(struct babel_route *route) +{ + struct babel_route *installed; + struct xroute *xroute; + + if(route->installed) + return; + + if(!route_feasible(route)) + return; + + xroute = find_xroute(route->src->prefix, route->src->plen); + if(xroute) + 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) && + route_smoothed_metric(installed) > route_smoothed_metric(route)) + goto install; + + return; + + install: + switch_routes(installed, route); + if(installed && route->installed) + send_triggered_update(route, installed->src, route_metric(installed)); + else + send_update(NULL, 1, route->src->prefix, route->src->plen); + return; +} + +void +retract_neighbour_routes(struct neighbour *neigh) +{ + int i; + + for(i = 0; i < route_slots; i++) { + struct babel_route *r = routes[i]; + while(r) { + if(r->neigh == neigh) { + if(r->refmetric != INFINITY) { + unsigned short oldmetric = route_metric(r); + retract_route(r); + if(oldmetric != INFINITY) + route_changed(r, r->src, oldmetric); + } + } + r = r->next; + } + } +} + +void +send_triggered_update(struct babel_route *route, struct source *oldsrc, + unsigned oldmetric) +{ + unsigned newmetric, diff; + /* 1 means send speedily, 2 means resend */ + int urgent; + + if(!route->installed) + return; + + newmetric = route_metric(route); + diff = + newmetric >= oldmetric ? newmetric - oldmetric : oldmetric - newmetric; + + if(route->src != oldsrc || (oldmetric < INFINITY && newmetric >= INFINITY)) + /* Switching sources can cause transient routing loops. + Retractions can cause blackholes. */ + urgent = 2; + else if(newmetric > oldmetric && oldmetric < 6 * 256 && diff >= 512) + /* Route getting significantly worse */ + urgent = 1; + else if(unsatisfied_request(route->src->prefix, route->src->plen, + route->seqno, route->src->id)) + /* Make sure that requests are satisfied speedily */ + urgent = 1; + else if(oldmetric >= INFINITY && newmetric < INFINITY) + /* New route */ + urgent = 0; + else if(newmetric < oldmetric && diff < 1024) + /* Route getting better. This may be a transient fluctuation, so + don't advertise it to avoid making routes unfeasible later on. */ + return; + else if(diff < 384) + /* Don't fret about trivialities */ + return; + else + urgent = 0; + + if(urgent >= 2) + send_update_resend(NULL, route->src->prefix, route->src->plen); + else + send_update(NULL, urgent, route->src->prefix, route->src->plen); + + if(oldmetric < INFINITY) { + if(newmetric >= oldmetric + 512) { + send_request_resend(NULL, route->src->prefix, route->src->plen, + route->src->metric >= INFINITY ? + route->src->seqno : + seqno_plus(route->src->seqno, 1), + route->src->id); + } else if(newmetric >= oldmetric + 288) { + send_request(NULL, route->src->prefix, route->src->plen); + } + } +} + +/* A route has just changed. Decide whether to switch to a different route or + send an update. */ +void +route_changed(struct babel_route *route, + struct source *oldsrc, unsigned short oldmetric) +{ + if(route->installed) { + struct babel_route *better_route; + /* Do this unconditionally -- microoptimisation is not worth it. */ + better_route = + find_best_route(route->src->prefix, route->src->plen, 1, NULL); + if(better_route && route_metric(better_route) < route_metric(route)) + consider_route(better_route); + } + + if(route->installed) { + /* We didn't change routes after all. */ + send_triggered_update(route, oldsrc, oldmetric); + } else { + /* Reconsider routes even when their metric didn't decrease, + they may not have been feasible before. */ + consider_route(route); + } +} + +/* We just lost the installed route to a given destination. */ +void +route_lost(struct source *src, unsigned oldmetric) +{ + struct babel_route *new_route; + new_route = find_best_route(src->prefix, src->plen, 1, NULL); + if(new_route) { + consider_route(new_route); + } else if(oldmetric < INFINITY) { + /* Avoid creating a blackhole. */ + send_update_resend(NULL, src->prefix, src->plen); + /* If the route was usable enough, try to get an alternate one. + If it was not, we could be dealing with oscillations around + the value of INFINITY. */ + if(oldmetric <= INFINITY / 2) + send_request_resend(NULL, src->prefix, src->plen, + src->metric >= INFINITY ? + src->seqno : seqno_plus(src->seqno, 1), + src->id); + } +} + +/* This is called periodically to flush old routes. It will also send + requests for routes that are about to expire. */ +void +expire_routes(void) +{ + struct babel_route *r; + int i; + + debugf(BABEL_DEBUG_COMMON,"Expiring old routes."); + + i = 0; + while(i < route_slots) { + r = routes[i]; + while(r) { + /* Protect against clock being stepped. */ + if(r->time > babel_now.tv_sec || route_old(r)) { + flush_route(r); + goto again; + } + + update_route_metric(r); + + if(r->installed && r->refmetric < INFINITY) { + if(route_old(r)) + /* Route about to expire, send a request. */ + send_unicast_request(r->neigh, + r->src->prefix, r->src->plen); + } + r = r->next; + } + i++; + again: + ; + } +} diff --git a/babeld/route.h b/babeld/route.h new file mode 100644 index 0000000..c994d22 --- /dev/null +++ b/babeld/route.h @@ -0,0 +1,129 @@ +/* +Copyright (c) 2007, 2008 by Juliusz Chroboczek +Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. +*/ + +#ifndef BABEL_ROUTE_H +#define BABEL_ROUTE_H + +#include "babel_interface.h" +#include "source.h" + +enum babel_diversity { + DIVERSITY_NONE, + DIVERSITY_INTERFACE_1, + DIVERSITY_CHANNEL_1, + DIVERSITY_CHANNEL, +}; + +#define DIVERSITY_HOPS 8 + +struct babel_route { + struct source *src; + unsigned short refmetric; + unsigned short cost; + unsigned short add_metric; + unsigned short seqno; + struct neighbour *neigh; + unsigned char nexthop[16]; + time_t time; + unsigned short hold_time; /* in seconds */ + unsigned short smoothed_metric; /* for route selection */ + time_t smoothed_metric_time; + short installed; + unsigned char channels[DIVERSITY_HOPS]; + struct babel_route *next; +}; + +struct route_stream; + +extern struct babel_route **routes; +extern int kernel_metric; +extern enum babel_diversity diversity_kind; +extern int diversity_factor; +extern int keep_unfeasible; +extern int smoothing_half_life; + +static inline int +route_metric(const struct babel_route *route) +{ + int m = (int)route->refmetric + route->cost + route->add_metric; + return MIN(m, INFINITY); +} + +static inline int +route_metric_noninterfering(const struct babel_route *route) +{ + int m = + (int)route->refmetric + + (diversity_factor * route->cost + 128) / 256 + + route->add_metric; + m = MAX(m, route->refmetric + 1); + return MIN(m, INFINITY); +} + +struct babel_route *find_route(const unsigned char *prefix, unsigned char plen, + struct neighbour *neigh, const unsigned char *nexthop); +struct babel_route *find_installed_route(const unsigned char *prefix, + unsigned char plen); +int installed_routes_estimate(void); +void flush_route(struct babel_route *route); +void flush_all_routes(void); +void flush_neighbour_routes(struct neighbour *neigh); +void flush_interface_routes(struct interface *ifp, int v4only); +struct route_stream *route_stream(int installed); +struct babel_route *route_stream_next(struct route_stream *stream); +void route_stream_done(struct route_stream *stream); +void install_route(struct babel_route *route); +void uninstall_route(struct babel_route *route); +int route_feasible(struct babel_route *route); +int route_old(struct babel_route *route); +int route_expired(struct babel_route *route); +int route_interferes(struct babel_route *route, struct interface *ifp); +int update_feasible(struct source *src, + unsigned short seqno, unsigned short refmetric); +void change_smoothing_half_life(int half_life); +int route_smoothed_metric(struct babel_route *route); +struct babel_route *find_best_route(const unsigned char *prefix, unsigned char plen, + int feasible, struct neighbour *exclude); +struct babel_route *install_best_route(const unsigned char prefix[16], + unsigned char plen); +void update_neighbour_metric(struct neighbour *neigh, int change); +void update_interface_metric(struct interface *ifp); +void update_route_metric(struct babel_route *route); +struct babel_route *update_route(const unsigned char *id, + const unsigned char *prefix, unsigned char plen, + unsigned short seqno, unsigned short refmetric, + unsigned short interval, struct neighbour *neigh, + const unsigned char *nexthop, + const unsigned char *channels, int channels_len); +void retract_neighbour_routes(struct neighbour *neigh); +void send_unfeasible_request(struct neighbour *neigh, int force, + unsigned short seqno, unsigned short metric, + struct source *src); +void send_triggered_update(struct babel_route *route, + struct source *oldsrc, unsigned oldmetric); +void route_changed(struct babel_route *route, + struct source *oldsrc, unsigned short oldmetric); +void route_lost(struct source *src, unsigned oldmetric); +void expire_routes(void); + +#endif diff --git a/babeld/source.c b/babeld/source.c new file mode 100644 index 0000000..2c303b6 --- /dev/null +++ b/babeld/source.c @@ -0,0 +1,169 @@ +/* +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. +*/ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#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" +#include "babel_errors.h" + +struct source *srcs = NULL; + +struct source* +find_source(const unsigned char *id, const unsigned char *p, unsigned char plen, + int create, unsigned short seqno) +{ + struct source *src; + + for(src = srcs; src; src = src->next) { + /* This should really be a hash table. For now, check the + last byte first. */ + if(src->id[7] != id[7]) + continue; + if(memcmp(src->id, id, 8) != 0) + continue; + if(src->plen != plen) + continue; + if(memcmp(src->prefix, p, 16) == 0) + return src; + } + + if(!create) + return NULL; + + src = malloc(sizeof(struct source)); + if(src == NULL) { + flog_err(EC_BABEL_MEMORY, "malloc(source): %s", safe_strerror(errno)); + return NULL; + } + + memcpy(src->id, id, 8); + memcpy(src->prefix, p, 16); + src->plen = plen; + src->seqno = seqno; + src->metric = INFINITY; + src->time = babel_now.tv_sec; + src->route_count = 0; + src->next = srcs; + srcs = src; + return src; +} + +struct source * +retain_source(struct source *src) +{ + assert(src->route_count < 0xffff); + src->route_count++; + return src; +} + +void +release_source(struct source *src) +{ + assert(src->route_count > 0); + src->route_count--; +} + +int +flush_source(struct source *src) +{ + if(src->route_count > 0) + /* The source is in use by a route. */ + return 0; + + if(srcs == src) { + srcs = src->next; + } else { + struct source *previous = srcs; + while(previous->next != src) + previous = previous->next; + previous->next = src->next; + } + + free(src); + return 1; +} + +void +update_source(struct source *src, + unsigned short seqno, unsigned short metric) +{ + if(metric >= INFINITY) + return; + + /* If a source is expired, pretend that it doesn't exist and update + it unconditionally. This makes ensures that old data will + eventually be overridden, and prevents us from getting stuck if + a router loses its sequence number. */ + if(src->time < babel_now.tv_sec - SOURCE_GC_TIME || + seqno_compare(src->seqno, seqno) < 0 || + (src->seqno == seqno && src->metric > metric)) { + src->seqno = seqno; + src->metric = metric; + } + src->time = babel_now.tv_sec; +} + +void +expire_sources(void) +{ + struct source *src; + + src = srcs; + while(src) { + if(src->time > babel_now.tv_sec) + /* clock stepped */ + src->time = babel_now.tv_sec; + if(src->time < babel_now.tv_sec - SOURCE_GC_TIME) { + struct source *old = src; + src = src->next; + flush_source(old); + continue; + } + src = src->next; + } +} + +void +check_sources_released(void) +{ + struct source *src; + + for(src = srcs; src; src = src->next) { + if(src->route_count != 0) + fprintf(stderr, "Warning: source %s %s has refcount %d.\n", + format_eui64(src->id), + format_prefix(src->prefix, src->plen), + (int)src->route_count); + } +} diff --git a/babeld/source.h b/babeld/source.h new file mode 100644 index 0000000..5b0ba44 --- /dev/null +++ b/babeld/source.h @@ -0,0 +1,51 @@ +/* +Copyright (c) 2007, 2008 by Juliusz Chroboczek + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. +*/ + +#ifndef BABEL_SOURCE_H +#define BABEL_SOURCE_H + +#define SOURCE_GC_TIME 200 + +struct source { + struct source *next; + unsigned char id[8]; + unsigned char prefix[16]; + unsigned char plen; + unsigned short seqno; + unsigned short metric; + unsigned short route_count; + time_t time; +}; + +struct source *find_source(const unsigned char *id, + const unsigned char *p, + unsigned char plen, + int create, unsigned short seqno); +struct source *retain_source(struct source *src); +void release_source(struct source *src); +int flush_source(struct source *src); +void update_source(struct source *src, + unsigned short seqno, unsigned short metric); +void expire_sources(void); +void check_sources_released(void); + +#endif diff --git a/babeld/subdir.am b/babeld/subdir.am new file mode 100644 index 0000000..856cbd1 --- /dev/null +++ b/babeld/subdir.am @@ -0,0 +1,51 @@ +# +# babeld +# + +if BABELD +sbin_PROGRAMS += babeld/babeld +vtysh_scan += \ + babeld/babel_interface.c \ + babeld/babel_zebra.c \ + babeld/babeld.c \ + # end +vtysh_daemons += babeld +endif + +babeld_babeld_SOURCES = \ + babeld/babel_errors.c \ + babeld/babel_filter.c \ + babeld/babel_interface.c \ + babeld/babel_main.c \ + babeld/babel_zebra.c \ + babeld/babeld.c \ + babeld/kernel.c \ + babeld/message.c \ + babeld/neighbour.c \ + babeld/net.c \ + babeld/resend.c \ + babeld/route.c \ + babeld/source.c \ + babeld/util.c \ + babeld/xroute.c \ + # end + +noinst_HEADERS += \ + babeld/babel_errors.h \ + babeld/babel_filter.h \ + babeld/babel_interface.h \ + babeld/babel_main.h \ + babeld/babel_zebra.h \ + babeld/babeld.h \ + babeld/kernel.h \ + babeld/message.h \ + babeld/neighbour.h \ + babeld/net.h \ + babeld/resend.h \ + babeld/route.h \ + babeld/source.h \ + babeld/util.h \ + babeld/xroute.h \ + # end + +babeld_babeld_LDADD = lib/libfrr.la $(LIBCAP) diff --git a/babeld/util.c b/babeld/util.c new file mode 100644 index 0000000..e2db759 --- /dev/null +++ b/babeld/util.c @@ -0,0 +1,446 @@ +/* +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. +*/ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <stdlib.h> +#include <stdarg.h> +#include <string.h> +#include <sys/time.h> +#include <time.h> +#include <stdio.h> +#include <unistd.h> +#include <limits.h> + +#include <sys/types.h> +#include <sys/socket.h> +#include <netinet/in.h> +#include <arpa/inet.h> + +#include "lib/network.h" + +#include "babel_main.h" +#include "babeld.h" +#include "util.h" + +int +roughly(int value) +{ + if(value < 0) + return -roughly(-value); + else if(value <= 1) + return value; + else + return value * 3 / 4 + frr_weak_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, 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 = frr_weak_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; +} + +/* There's no good name for a positive int in C, call it nat. */ +int +parse_nat(const char *string) +{ + long l; + char *end; + + l = strtol(string, &end, 0); + + while(*end == ' ' || *end == '\t') + end++; + if(*end != '\0') + return -1; + + if(l < 0 || l > INT_MAX) + return -1; + + return (int)l; +} + +unsigned char * +mask_prefix(unsigned char *restrict ret, + const unsigned char *restrict prefix, unsigned char plen) +{ + if (plen >= IPV6_MAX_BITLEN) { + memcpy(ret, prefix, IPV6_MAX_BYTELEN); + 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; +} + +const unsigned char v4prefix[16] = + {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF, 0, 0, 0, 0 }; + +static const unsigned char llprefix[16] = + {0xFE, 0x80}; + +const char * +format_address(const unsigned char *address) +{ + static char buf[4][INET6_ADDRSTRLEN]; + static int i = 0; + i = (i + 1) % 4; + if(v4mapped(address)) + inet_ntop(AF_INET, address + 12, buf[i], INET6_ADDRSTRLEN); + else + inet_ntop(AF_INET6, address, buf[i], INET6_ADDRSTRLEN); + return buf[i]; +} + +const char * +format_prefix(const unsigned char *prefix, unsigned char plen) +{ + static char buf[4][INET6_ADDRSTRLEN + 4]; + static int i = 0; + int n; + i = (i + 1) % 4; + if(plen >= 96 && v4mapped(prefix)) { + inet_ntop(AF_INET, prefix + 12, buf[i], INET6_ADDRSTRLEN); + n = strlen(buf[i]); + snprintf(buf[i] + n, INET6_ADDRSTRLEN + 4 - n, "/%d", plen - 96); + } else { + inet_ntop(AF_INET6, prefix, buf[i], INET6_ADDRSTRLEN); + n = strlen(buf[i]); + snprintf(buf[i] + n, INET6_ADDRSTRLEN + 4 - n, "/%d", plen); + } + return buf[i]; +} + +const char * +format_eui64(const unsigned char *eui) +{ + static char buf[4][28]; + static int i = 0; + i = (i + 1) % 4; + snprintf(buf[i], 28, "%02x:%02x:%02x:%02x:%02x:%02x:%02x:%02x", + eui[0], eui[1], eui[2], eui[3], + eui[4], eui[5], eui[6], eui[7]); + return buf[i]; +} + +const char * +format_thousands(unsigned int value) +{ + static char buf[4][15]; + static int i = 0; + i = (i + 1) % 4; + snprintf(buf[i], 15, "%u.%.3u", value / 1000, value % 1000); + 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) { + v4tov6(addr_r, (const unsigned char *)&ina); + if(af_r) *af_r = AF_INET; + return 0; + } + + rc = inet_pton(AF_INET6, address, &ina6); + if(rc > 0) { + memcpy(addr_r, &ina6, IPV6_MAX_BYTELEN); + if (af_r) + *af_r = AF_INET6; + return 0; + } + + return -1; +} + +int +parse_eui64(const char *eui, unsigned char *eui_r) +{ + int n; + n = sscanf(eui, "%02hhx:%02hhx:%02hhx:%02hhx:%02hhx:%02hhx:%02hhx:%02hhx", + &eui_r[0], &eui_r[1], &eui_r[2], &eui_r[3], + &eui_r[4], &eui_r[5], &eui_r[6], &eui_r[7]); + if(n == 8) + return 0; + + n = sscanf(eui, "%02hhx-%02hhx-%02hhx-%02hhx-%02hhx-%02hhx-%02hhx-%02hhx", + &eui_r[0], &eui_r[1], &eui_r[2], &eui_r[3], + &eui_r[4], &eui_r[5], &eui_r[6], &eui_r[7]); + if(n == 8) + return 0; + + n = sscanf(eui, "%02hhx:%02hhx:%02hhx:%02hhx:%02hhx:%02hhx", + &eui_r[0], &eui_r[1], &eui_r[2], + &eui_r[5], &eui_r[6], &eui_r[7]); + if(n == 6) { + eui_r[3] = 0xFF; + eui_r[4] = 0xFE; + return 0; + } + return -1; +} + +int +wait_for_fd(int direction, int fd, int msecs) +{ + fd_set fds; + int rc; + struct timeval tv; + + tv.tv_sec = msecs / 1000; + tv.tv_usec = (msecs % 1000) * 1000; + + FD_ZERO(&fds); + FD_SET(fd, &fds); + if(direction) + rc = select(fd + 1, NULL, &fds, NULL, &tv); + else + rc = select(fd + 1, &fds, NULL, NULL, &tv); + + return rc; +} + +int +martian_prefix(const unsigned char *prefix, int plen) +{ + return + (plen >= 8 && prefix[0] == 0xFF) || + (plen >= 10 && prefix[0] == 0xFE && (prefix[1] & 0xC0) == 0x80) || + (plen >= 128 && memcmp(prefix, zeroes, 15) == 0 && + (prefix[15] == 0 || prefix[15] == 1)) || + (plen >= 96 && v4mapped(prefix) && + ((plen >= 104 && (prefix[12] == 127 || prefix[12] == 0)) || + (plen >= 100 && (prefix[12] & 0xE0) == 0xE0))); +} + +int +linklocal(const unsigned char *address) +{ + return memcmp(address, llprefix, 8) == 0; +} + +int +v4mapped(const unsigned char *address) +{ + return memcmp(address, v4prefix, 12) == 0; +} + +void +v4tov6(unsigned char *dst, const unsigned char *src) +{ + memcpy(dst, v4prefix, 12); + memcpy(dst + 12, src, 4); +} + +void +inaddr_to_uchar(unsigned char *dest, const struct in_addr *src) +{ + v4tov6(dest, (const unsigned char *)src); + 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, IPV6_MAX_BYTELEN); +} + +void +uchar_to_in6addr(struct in6_addr *dest, const unsigned char *src) +{ + memcpy(dest, src, IPV6_MAX_BYTELEN); +} + +int +daemonise(void) +{ + 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 0000000..ef13873 --- /dev/null +++ b/babeld/util.h @@ -0,0 +1,149 @@ +/* +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_UTIL_H +#define BABEL_UTIL_H + +#include "babeld.h" +#include "babel_main.h" +#include "log.h" +#include "memory.h" + +DECLARE_MGROUP(BABELD); + +#if defined(i386) || defined(__mc68020__) || defined(__x86_64__) +#define DO_NTOHS(_d, _s) do{ _d = ntohs(*(const unsigned short*)(_s)); }while(0) +#define DO_NTOHL(_d, _s) do{ _d = ntohl(*(const unsigned*)(_s)); } while(0) +#define DO_HTONS(_d, _s) do{ *(unsigned short*)(_d) = htons(_s); } while(0) +#define DO_HTONL(_d, _s) do{ *(unsigned*)(_d) = htonl(_s); } while(0) +/* Some versions of gcc seem to be buggy, and ignore the packed attribute. + Disable this code until the issue is clarified. */ +/* #elif defined __GNUC__*/ +#else +#define DO_NTOHS(_d, _s) \ + do { short _dd; \ + memcpy(&(_dd), (_s), 2); \ + _d = ntohs(_dd); } while(0) +#define DO_NTOHL(_d, _s) \ + do { int _dd; \ + memcpy(&(_dd), (_s), 4); \ + _d = ntohl(_dd); } while(0) +#define DO_HTONS(_d, _s) \ + do { unsigned short _dd; \ + _dd = htons(_s); \ + memcpy((_d), &(_dd), 2); } while(0) +#define DO_HTONL(_d, _s) \ + do { unsigned _dd; \ + _dd = htonl(_s); \ + memcpy((_d), &(_dd), 4); } 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); +} + +/* Returns a time in microseconds on 32 bits (thus modulo 2^32, + i.e. about 4295 seconds). */ +static inline unsigned int +time_us(const struct timeval t) +{ + return (unsigned int) (t.tv_sec * 1000000 + t.tv_usec); +} + +int roughly(int 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, 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_nat(const char *string) ATTRIBUTE ((pure)); +int parse_msec(const char *string) ATTRIBUTE ((pure)); +unsigned char *mask_prefix(unsigned char *restrict ret, + const unsigned char *restrict prefix, + unsigned char plen); +const char *format_address(const unsigned char *address); +const char *format_prefix(const unsigned char *address, unsigned char prefix); +const char *format_eui64(const unsigned char *eui); +const char *format_thousands(unsigned int value); +int parse_address(const char *address, unsigned char *addr_r, int *af_r); +int parse_eui64(const char *eui, unsigned char *eui_r); +int wait_for_fd(int direction, int fd, int msecs); +int martian_prefix(const unsigned char *prefix, int plen) ATTRIBUTE ((pure)); +int linklocal(const unsigned char *address) ATTRIBUTE ((pure)); +int v4mapped(const unsigned char *address) ATTRIBUTE ((pure)); +void v4tov6(unsigned char *dst, const unsigned char *src); +void inaddr_to_uchar(unsigned char *dest, const struct in_addr *src); +void uchar_to_inaddr(struct in_addr *dest, const unsigned char *src); +void in6addr_to_uchar(unsigned char *dest, const struct in6_addr *src); +void uchar_to_in6addr(struct in6_addr *dest, const unsigned char *src); +int daemonise(void); +extern const unsigned char v4prefix[16]; + +/* 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 + +#define debugf(...) do {} while(0) + +#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) + +#define debugf(level, ...) \ +do { \ +if(UNLIKELY(debug & level)) zlog_debug(__VA_ARGS__); \ +} while(0) + +#endif /* NO_DEBUG */ + +#endif /* BABEL_UTIL_H */ diff --git a/babeld/xroute.c b/babeld/xroute.c new file mode 100644 index 0000000..61ea5a1 --- /dev/null +++ b/babeld/xroute.c @@ -0,0 +1,231 @@ +/* +Copyright (c) 2007, 2008 by Juliusz Chroboczek +Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. +*/ + +#include <zebra.h> +#include "if.h" +#include "log.h" + +#include "babeld.h" +#include "kernel.h" +#include "neighbour.h" +#include "message.h" +#include "route.h" +#include "xroute.h" +#include "util.h" +#include "babel_interface.h" + +static int xroute_add_new_route(unsigned char prefix[16], unsigned char plen, + unsigned short metric, unsigned int ifindex, + int proto, int send_updates); + +static struct xroute *xroutes; +static int numxroutes = 0, maxxroutes = 0; + +/* Add redistributed route to Babel table. */ +int +babel_route_add (struct zapi_route *api) +{ + unsigned char uchar_prefix[16]; + + switch (api->prefix.family) { + case AF_INET: + inaddr_to_uchar(uchar_prefix, &api->prefix.u.prefix4); + debugf(BABEL_DEBUG_ROUTE, "Adding new ipv4 route coming from Zebra."); + xroute_add_new_route(uchar_prefix, api->prefix.prefixlen + 96, + api->metric, api->nexthops[0].ifindex, 0, 1); + break; + case AF_INET6: + in6addr_to_uchar(uchar_prefix, &api->prefix.u.prefix6); + debugf(BABEL_DEBUG_ROUTE, "Adding new ipv6 route coming from Zebra."); + xroute_add_new_route(uchar_prefix, api->prefix.prefixlen, + api->metric, api->nexthops[0].ifindex, 0, 1); + break; + } + + return 0; +} + +/* Remove redistributed route from Babel table. */ +int +babel_route_delete (struct zapi_route *api) +{ + unsigned char uchar_prefix[16]; + struct xroute *xroute = NULL; + + switch (api->prefix.family) { + case AF_INET: + inaddr_to_uchar(uchar_prefix, &api->prefix.u.prefix4); + xroute = find_xroute(uchar_prefix, api->prefix.prefixlen + 96); + if (xroute != NULL) { + debugf(BABEL_DEBUG_ROUTE, "Removing ipv4 route (from zebra)."); + flush_xroute(xroute); + } + break; + case AF_INET6: + in6addr_to_uchar(uchar_prefix, &api->prefix.u.prefix6); + xroute = find_xroute(uchar_prefix, api->prefix.prefixlen); + if (xroute != NULL) { + debugf(BABEL_DEBUG_ROUTE, "Removing ipv6 route (from zebra)."); + flush_xroute(xroute); + } + break; + } + + return 0; +} + +struct xroute * +find_xroute(const unsigned char *prefix, unsigned char plen) +{ + int i; + for(i = 0; i < numxroutes; i++) { + if(xroutes[i].plen == plen && + memcmp(xroutes[i].prefix, prefix, 16) == 0) + return &xroutes[i]; + } + return NULL; +} + +void +flush_xroute(struct xroute *xroute) +{ + int i; + + i = xroute - xroutes; + assert(i >= 0 && i < numxroutes); + + if(i != numxroutes - 1) + memcpy(xroutes + i, xroutes + numxroutes - 1, sizeof(struct xroute)); + numxroutes--; + VALGRIND_MAKE_MEM_UNDEFINED(xroutes + numxroutes, sizeof(struct xroute)); + + if(numxroutes == 0) { + free(xroutes); + xroutes = NULL; + maxxroutes = 0; + } else if(maxxroutes > 8 && numxroutes < maxxroutes / 4) { + struct xroute *new_xroutes; + int n = maxxroutes / 2; + new_xroutes = realloc(xroutes, n * sizeof(struct xroute)); + if(new_xroutes == NULL) + return; + xroutes = new_xroutes; + maxxroutes = n; + } +} + +static int +add_xroute(unsigned char prefix[16], unsigned char plen, + unsigned short metric, unsigned int ifindex, int proto) +{ + struct xroute *xroute = find_xroute(prefix, plen); + if(xroute) { + if(xroute->metric <= metric) + return 0; + xroute->metric = metric; + return 1; + } + + if(numxroutes >= maxxroutes) { + struct xroute *new_xroutes; + int n = maxxroutes < 1 ? 8 : 2 * maxxroutes; + new_xroutes = xroutes == NULL ? + malloc(n * sizeof(struct xroute)) : + realloc(xroutes, n * sizeof(struct xroute)); + if(new_xroutes == NULL) + return -1; + maxxroutes = n; + xroutes = new_xroutes; + } + + memcpy(xroutes[numxroutes].prefix, prefix, 16); + xroutes[numxroutes].plen = plen; + xroutes[numxroutes].metric = metric; + xroutes[numxroutes].ifindex = ifindex; + xroutes[numxroutes].proto = proto; + numxroutes++; + return 1; +} + +/* Returns an overestimate of the number of xroutes. */ +int +xroutes_estimate(void) +{ + return numxroutes; +} + +struct xroute_stream { + int index; +}; + +struct +xroute_stream * +xroute_stream(void) +{ + struct xroute_stream *stream = malloc(sizeof(struct xroute_stream)); + if(stream == NULL) + return NULL; + + stream->index = 0; + return stream; +} + +struct xroute * +xroute_stream_next(struct xroute_stream *stream) +{ + if(stream->index < numxroutes) + return &xroutes[stream->index++]; + else + return NULL; +} + +void +xroute_stream_done(struct xroute_stream *stream) +{ + free(stream); +} + +/* add an xroute, verifying some conditions; return 0 if there is no changes */ +static int +xroute_add_new_route(unsigned char prefix[16], unsigned char plen, + unsigned short metric, unsigned int ifindex, + int proto, int send_updates) +{ + int rc; + if(martian_prefix(prefix, plen)) + return 0; + metric = redistribute_filter(prefix, plen, ifindex, proto); + if(metric < INFINITY) { + rc = add_xroute(prefix, plen, metric, ifindex, proto); + if(rc > 0) { + struct babel_route *route; + route = find_installed_route(prefix, plen); + if(route) + 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 0000000..59afccb --- /dev/null +++ b/babeld/xroute.h @@ -0,0 +1,46 @@ +/* +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_XROUTE_H +#define BABEL_XROUTE_H + +struct xroute { + unsigned char prefix[16]; + unsigned char plen; + unsigned short metric; + unsigned int ifindex; + int proto; +}; + +struct xroute_stream; + +struct xroute *find_xroute(const unsigned char *prefix, unsigned char plen); +void flush_xroute(struct xroute *xroute); +int babel_route_add (struct zapi_route *api); +int babel_route_delete (struct zapi_route *api); +int xroutes_estimate(void); +struct xroute_stream *xroute_stream(void); +struct xroute *xroute_stream_next(struct xroute_stream *stream); +void xroute_stream_done(struct xroute_stream *stream); + +#endif /* BABEL_XROUTE_H */ |