summaryrefslogtreecommitdiffstats
path: root/lib/spf_backoff.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/spf_backoff.c')
-rw-r--r--lib/spf_backoff.c313
1 files changed, 313 insertions, 0 deletions
diff --git a/lib/spf_backoff.c b/lib/spf_backoff.c
new file mode 100644
index 0000000..117b7d3
--- /dev/null
+++ b/lib/spf_backoff.c
@@ -0,0 +1,313 @@
+/*
+ * 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 FRRouting (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 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 "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_cancel(&backoff->t_holddown);
+ thread_cancel(&backoff->t_timetolearn);
+ XFREE(MTYPE_SPF_BACKOFF_NAME, backoff->name);
+
+ XFREE(MTYPE_SPF_BACKOFF, backoff);
+}
+
+static void spf_backoff_timetolearn_elapsed(struct thread *thread)
+{
+ struct spf_backoff *backoff = THREAD_ARG(thread);
+
+ 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));
+}
+
+static void spf_backoff_holddown_elapsed(struct thread *thread)
+{
+ struct spf_backoff *backoff = THREAD_ARG(thread);
+
+ THREAD_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));
+}
+
+long spf_backoff_schedule(struct spf_backoff *backoff)
+{
+ long rv = 0;
+ 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_add_timer_msec(
+ backoff->m, spf_backoff_timetolearn_elapsed, backoff,
+ backoff->timetolearn, &backoff->t_timetolearn);
+ thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed,
+ backoff, backoff->holddown,
+ &backoff->t_holddown);
+ backoff->first_event_time = now;
+ rv = backoff->init_delay;
+ break;
+ case SPF_BACKOFF_SHORT_WAIT:
+ case SPF_BACKOFF_LONG_WAIT:
+ thread_cancel(&backoff->t_holddown);
+ thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed,
+ backoff, backoff->holddown,
+ &backoff->t_holddown);
+ if (backoff->state == SPF_BACKOFF_SHORT_WAIT)
+ rv = backoff->short_delay;
+ else
+ rv = backoff->long_delay;
+ break;
+ }
+
+ 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",
+ (long int)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\n", prefix,
+ spf_backoff_state2str(backoff->state));
+ vty_out(vty, "%sInit timer: %ld msec\n", prefix,
+ backoff->init_delay);
+ vty_out(vty, "%sShort timer: %ld msec\n", prefix,
+ backoff->short_delay);
+ vty_out(vty, "%sLong timer: %ld msec\n", prefix,
+ backoff->long_delay);
+ vty_out(vty, "%sHolddown timer: %ld msec\n", prefix,
+ backoff->holddown);
+ if (backoff->t_holddown) {
+ struct timeval remain =
+ thread_timer_remain(backoff->t_holddown);
+ vty_out(vty, "%s Still runs for %lld msec\n",
+ prefix,
+ (long long)remain.tv_sec * 1000
+ + remain.tv_usec / 1000);
+ } else {
+ vty_out(vty, "%s Inactive\n", prefix);
+ }
+
+ vty_out(vty, "%sTimeToLearn timer: %ld msec\n", prefix,
+ backoff->timetolearn);
+ if (backoff->t_timetolearn) {
+ struct timeval remain =
+ thread_timer_remain(backoff->t_timetolearn);
+ vty_out(vty, "%s Still runs for %lld msec\n",
+ prefix,
+ (long long)remain.tv_sec * 1000
+ + remain.tv_usec / 1000);
+ } else {
+ vty_out(vty, "%s Inactive\n", prefix);
+ }
+
+ vty_out(vty, "%sFirst event: %s\n", prefix,
+ timeval_format(&backoff->first_event_time));
+ vty_out(vty, "%sLast event: %s\n", prefix,
+ timeval_format(&backoff->last_event_time));
+}
+
+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\n");
+ 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;
+}