diff options
author | Christian Franke <nobody@nowhere.ws> | 2017-02-21 22:32:08 +0100 |
---|---|---|
committer | Christian Franke <nobody@nowhere.ws> | 2017-02-22 16:18:40 +0100 |
commit | c1d0d21f9895d2ee1468989e44b9eb77ab3dd46f (patch) | |
tree | bd3fe584591c236dfc1874da7dd87242b09dff98 /lib/spf_backoff.c | |
parent | Merge branch 'frr/pull/210' ("tools: frr-reload removes "ipv6 nd ra-interval"... (diff) | |
download | frr-c1d0d21f9895d2ee1468989e44b9eb77ab3dd46f.tar.xz frr-c1d0d21f9895d2ee1468989e44b9eb77ab3dd46f.zip |
lib: add SPF back-off implementation
Add an implementation of draft-ietf-rtgwg-backoff-algo-04 to
libfrr.
Diffstat (limited to 'lib/spf_backoff.c')
-rw-r--r-- | lib/spf_backoff.c | 341 |
1 files changed, 341 insertions, 0 deletions
diff --git a/lib/spf_backoff.c b/lib/spf_backoff.c new file mode 100644 index 000000000..e923f232b --- /dev/null +++ b/lib/spf_backoff.c @@ -0,0 +1,341 @@ +/* + * This is an implementation of the IETF SPF delay algorithm + * as explained in draft-ietf-rtgwg-backoff-algo-04 + * + * Created: 25-01-2017 by S. Litkowski + * + * Copyright (C) 2017 Orange Labs http://www.orange.com/ + * Copyright (C) 2017 by Christian Franke, Open Source Routing / NetDEF Inc. + * + * This file is part of FreeRangeRouting (FRR) + * + * FRR 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, or (at your option) any + * later version. + * + * FRR 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 FRR; see the file COPYING. If not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA + * 02111-1307, USA. + */ + +#include <zebra.h> + +#include "spf_backoff.h" + +#include "command.h" +#include "memory.h" +#include "thread.h" +#include "vty.h" + +DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF, "SPF backoff") +DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF_NAME, "SPF backoff name") + +static bool debug_spf_backoff = false; +#define backoff_debug(...) \ + do \ + { \ + if (debug_spf_backoff) \ + zlog_debug(__VA_ARGS__); \ + } \ + while (0) + +enum spf_backoff_state { + SPF_BACKOFF_QUIET, + SPF_BACKOFF_SHORT_WAIT, + SPF_BACKOFF_LONG_WAIT +}; + +struct spf_backoff { + struct thread_master *m; + + /* Timers as per draft */ + long init_delay; + long short_delay; + long long_delay; + long holddown; + long timetolearn; + + /* State machine */ + enum spf_backoff_state state; + struct thread *t_holddown; + struct thread *t_timetolearn; + + /* For debugging */ + char *name; + struct timeval first_event_time; + struct timeval last_event_time; +}; + +static const char * +spf_backoff_state2str(enum spf_backoff_state state) +{ + switch (state) + { + case SPF_BACKOFF_QUIET: + return "QUIET"; + case SPF_BACKOFF_SHORT_WAIT: + return "SHORT_WAIT"; + case SPF_BACKOFF_LONG_WAIT: + return "LONG_WAIT"; + } + return "???"; +} + +struct spf_backoff * +spf_backoff_new(struct thread_master *m, + const char *name, + long init_delay, + long short_delay, + long long_delay, + long holddown, + long timetolearn) +{ + struct spf_backoff *rv; + + rv = XCALLOC(MTYPE_SPF_BACKOFF, sizeof(*rv)); + rv->m = m; + + rv->init_delay = init_delay; + rv->short_delay = short_delay; + rv->long_delay = long_delay; + rv->holddown = holddown; + rv->timetolearn = timetolearn; + + rv->state = SPF_BACKOFF_QUIET; + + rv->name = XSTRDUP(MTYPE_SPF_BACKOFF_NAME, name); + return rv; +} + +void +spf_backoff_free(struct spf_backoff *backoff) +{ + if (!backoff) + return; + + THREAD_TIMER_OFF(backoff->t_holddown); + THREAD_TIMER_OFF(backoff->t_timetolearn); + XFREE(MTYPE_SPF_BACKOFF_NAME, backoff->name); + + XFREE(MTYPE_SPF_BACKOFF, backoff); +} + +static int +spf_backoff_timetolearn_elapsed(struct thread *thread) +{ + struct spf_backoff *backoff = THREAD_ARG(thread); + + backoff->t_timetolearn = NULL; + backoff->state = SPF_BACKOFF_LONG_WAIT; + backoff_debug("SPF Back-off(%s) TIMETOLEARN elapsed, move to state %s", + backoff->name, spf_backoff_state2str(backoff->state)); + return 0; +} + +static int +spf_backoff_holddown_elapsed(struct thread *thread) +{ + struct spf_backoff *backoff = THREAD_ARG(thread); + + backoff->t_holddown = NULL; + THREAD_TIMER_OFF(backoff->t_timetolearn); + timerclear(&backoff->first_event_time); + backoff->state = SPF_BACKOFF_QUIET; + backoff_debug("SPF Back-off(%s) HOLDDOWN elapsed, move to state %s", + backoff->name, spf_backoff_state2str(backoff->state)); + return 0; +} + +long spf_backoff_schedule(struct spf_backoff *backoff) +{ + long rv; + struct timeval now; + + gettimeofday(&now, NULL); + + backoff_debug("SPF Back-off(%s) schedule called in state %s", + backoff->name, spf_backoff_state2str(backoff->state)); + + backoff->last_event_time = now; + + switch (backoff->state) + { + case SPF_BACKOFF_QUIET: + backoff->state = SPF_BACKOFF_SHORT_WAIT; + THREAD_TIMER_MSEC_ON(backoff->m, backoff->t_timetolearn, + spf_backoff_timetolearn_elapsed, backoff, + backoff->timetolearn); + THREAD_TIMER_MSEC_ON(backoff->m, backoff->t_holddown, + spf_backoff_holddown_elapsed, backoff, + backoff->holddown); + backoff->first_event_time = now; + rv = backoff->init_delay; + break; + case SPF_BACKOFF_SHORT_WAIT: + case SPF_BACKOFF_LONG_WAIT: + THREAD_TIMER_OFF(backoff->t_holddown); + THREAD_TIMER_MSEC_ON(backoff->m, backoff->t_holddown, + spf_backoff_holddown_elapsed, backoff, + backoff->holddown); + if (backoff->state == SPF_BACKOFF_SHORT_WAIT) + rv = backoff->short_delay; + else + rv = backoff->long_delay; + break; + default: + zlog_warn("SPF Back-off(%s) in unknown state", backoff->name); + rv = backoff->init_delay; + } + + backoff_debug("SPF Back-off(%s) changed state to %s and returned %ld delay", + backoff->name, spf_backoff_state2str(backoff->state), rv); + return rv; +} + +static const char * +timeval_format(struct timeval *tv) +{ + struct tm tm_store; + struct tm *tm; + static char timebuf[256]; + + if (!tv->tv_sec && !tv->tv_usec) + return "(never)"; + + tm = localtime_r(&tv->tv_sec, &tm_store); + if (!tm || strftime(timebuf, sizeof(timebuf), + "%Z %a %Y-%m-%d %H:%M:%S", tm) == 0) + { + return "???"; + } + + size_t offset = strlen(timebuf); + snprintf(timebuf + offset, sizeof(timebuf) - offset, ".%ld", tv->tv_usec); + + return timebuf; +} + +void +spf_backoff_show(struct spf_backoff *backoff, struct vty *vty, + const char *prefix) +{ + vty_out(vty, "%sCurrent state: %s%s", prefix, + spf_backoff_state2str(backoff->state), VTY_NEWLINE); + vty_out(vty, "%sInit timer: %ld msec%s", prefix, + backoff->init_delay, VTY_NEWLINE); + vty_out(vty, "%sShort timer: %ld msec%s", prefix, + backoff->short_delay, VTY_NEWLINE); + vty_out(vty, "%sLong timer: %ld msec%s", prefix, + backoff->long_delay, VTY_NEWLINE); + vty_out(vty, "%sHolddown timer: %ld msec%s", prefix, + backoff->holddown, VTY_NEWLINE); + if (backoff->t_holddown) + { + struct timeval remain = thread_timer_remain(backoff->t_holddown); + vty_out(vty, "%s Still runs for %ld msec%s", + prefix, remain.tv_sec * 1000 + remain.tv_usec/1000, VTY_NEWLINE); + } + else + { + vty_out(vty, "%s Inactive%s", prefix, VTY_NEWLINE); + } + + vty_out(vty, "%sTimeToLearn timer: %ld msec%s", prefix, + backoff->timetolearn, VTY_NEWLINE); + if (backoff->t_timetolearn) + { + struct timeval remain = thread_timer_remain(backoff->t_timetolearn); + vty_out(vty, "%s Still runs for %ld msec%s", + prefix, remain.tv_sec * 1000 + remain.tv_usec/1000, VTY_NEWLINE); + } + else + { + vty_out(vty, "%s Inactive%s", prefix, VTY_NEWLINE); + } + + vty_out(vty, "%sFirst event: %s%s", prefix, + timeval_format(&backoff->first_event_time), VTY_NEWLINE); + vty_out(vty, "%sLast event: %s%s", prefix, + timeval_format(&backoff->last_event_time), VTY_NEWLINE); +} + +DEFUN(spf_backoff_debug, + spf_backoff_debug_cmd, + "debug spf-delay-ietf", + DEBUG_STR + "SPF Back-off Debugging\n") +{ + debug_spf_backoff = true; + return CMD_SUCCESS; +} + +DEFUN(no_spf_backoff_debug, + no_spf_backoff_debug_cmd, + "no debug spf-delay-ietf", + NO_STR + DEBUG_STR + "SPF Back-off Debugging\n") +{ + debug_spf_backoff = false; + return CMD_SUCCESS; +} + +int +spf_backoff_write_config(struct vty *vty) +{ + int written = 0; + + if (debug_spf_backoff) + { + vty_out(vty, "debug spf-delay-ietf%s", VTY_NEWLINE); + written++; + } + + return written; +} + +void +spf_backoff_cmd_init(void) +{ + install_element(ENABLE_NODE, &spf_backoff_debug_cmd); + install_element(CONFIG_NODE, &spf_backoff_debug_cmd); + install_element(ENABLE_NODE, &no_spf_backoff_debug_cmd); + install_element(CONFIG_NODE, &no_spf_backoff_debug_cmd); +} + +long +spf_backoff_init_delay(struct spf_backoff *backoff) +{ + return backoff->init_delay; +} + +long +spf_backoff_short_delay(struct spf_backoff *backoff) +{ + return backoff->short_delay; +} + +long +spf_backoff_long_delay(struct spf_backoff *backoff) +{ + return backoff->long_delay; +} + +long +spf_backoff_holddown(struct spf_backoff *backoff) +{ + return backoff->holddown; +} + +long +spf_backoff_timetolearn(struct spf_backoff *backoff) +{ + return backoff->timetolearn; +} |