lib/spf_backoff.c

   1 /*
   2  * This is an implementation of the IETF SPF delay algorithm
   3  * as explained in draft-ietf-rtgwg-backoff-algo-04
   4  *
   5  * Created: 25-01-2017 by S. Litkowski
   6  *
   7  * Copyright (C) 2017 Orange Labs http://www.orange.com/
   8  * Copyright (C) 2017 by Christian Franke, Open Source Routing / NetDEF Inc.
   9  *
  10  * This file is part of FreeRangeRouting (FRR)
  11  *
  12  * FRR is free software; you can redistribute it and/or modify it
  13  * under the terms of the GNU General Public License as published by the
  14  * Free Software Foundation; either version 2, or (at your option) any
  15  * later version.
  16  *
  17  * FRR is distributed in the hope that it will be useful, but
  18  * WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20  * General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU General Public License along
  23  * with this program; see the file COPYING; if not, write to the Free Software
  24  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  25  */
  26
  27 #include <zebra.h>
  28
  29 #include "spf_backoff.h"
  30
  31 #include "command.h"
  32 #include "memory.h"
  33 #include "thread.h"
  34 #include "vty.h"
  35
  36 DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF, "SPF backoff")
  37 DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF_NAME, "SPF backoff name")
  38
  39 static bool debug_spf_backoff = false;
  40 #define backoff_debug(...) \
  41   do \
  42     { \
  43       if (debug_spf_backoff) \
  44         zlog_debug(__VA_ARGS__); \
  45     } \
  46   while (0)
  47
  48 enum spf_backoff_state {
  49   SPF_BACKOFF_QUIET,
  50   SPF_BACKOFF_SHORT_WAIT,
  51   SPF_BACKOFF_LONG_WAIT
  52 };
  53
  54 struct spf_backoff {
  55   struct thread_master *m;
  56
  57   /* Timers as per draft */
  58   long init_delay;
  59   long short_delay;
  60   long long_delay;
  61   long holddown;
  62   long timetolearn;
  63
  64   /* State machine */
  65   enum spf_backoff_state state;
  66   struct thread *t_holddown;
  67   struct thread *t_timetolearn;
  68
  69   /* For debugging */
  70   char *name;
  71   struct timeval first_event_time;
  72   struct timeval last_event_time;
  73 };
  74
  75 static const char *
  76 spf_backoff_state2str(enum spf_backoff_state state)
  77 {
  78   switch (state)
  79     {
  80     case SPF_BACKOFF_QUIET:
  81       return "QUIET";
  82     case SPF_BACKOFF_SHORT_WAIT:
  83       return "SHORT_WAIT";
  84     case SPF_BACKOFF_LONG_WAIT:
  85       return "LONG_WAIT";
  86     }
  87   return "???";
  88 }
  89
  90 struct spf_backoff *
  91 spf_backoff_new(struct thread_master *m,
  92                 const char *name,
  93                 long init_delay,
  94                 long short_delay,
  95                 long long_delay,
  96                 long holddown,
  97                 long timetolearn)
  98 {
  99   struct spf_backoff *rv;
 100
 101   rv = XCALLOC(MTYPE_SPF_BACKOFF, sizeof(*rv));
 102   rv->m = m;
 103
 104   rv->init_delay = init_delay;
 105   rv->short_delay = short_delay;
 106   rv->long_delay = long_delay;
 107   rv->holddown = holddown;
 108   rv->timetolearn = timetolearn;
 109
 110   rv->state = SPF_BACKOFF_QUIET;
 111
 112   rv->name = XSTRDUP(MTYPE_SPF_BACKOFF_NAME, name);
 113   return rv;
 114 }
 115
 116 void
 117 spf_backoff_free(struct spf_backoff *backoff)
 118 {
 119   if (!backoff)
 120     return;
 121
 122   THREAD_TIMER_OFF(backoff->t_holddown);
 123   THREAD_TIMER_OFF(backoff->t_timetolearn);
 124   XFREE(MTYPE_SPF_BACKOFF_NAME, backoff->name);
 125
 126   XFREE(MTYPE_SPF_BACKOFF, backoff);
 127 }
 128
 129 static int
 130 spf_backoff_timetolearn_elapsed(struct thread *thread)
 131 {
 132   struct spf_backoff *backoff = THREAD_ARG(thread);
 133
 134   backoff->t_timetolearn = NULL;
 135   backoff->state = SPF_BACKOFF_LONG_WAIT;
 136   backoff_debug("SPF Back-off(%s) TIMETOLEARN elapsed, move to state %s",
 137                 backoff->name, spf_backoff_state2str(backoff->state));
 138   return 0;
 139 }
 140
 141 static int
 142 spf_backoff_holddown_elapsed(struct thread *thread)
 143 {
 144   struct spf_backoff *backoff = THREAD_ARG(thread);
 145
 146   backoff->t_holddown = NULL;
 147   THREAD_TIMER_OFF(backoff->t_timetolearn);
 148   timerclear(&backoff->first_event_time);
 149   backoff->state = SPF_BACKOFF_QUIET;
 150   backoff_debug("SPF Back-off(%s) HOLDDOWN elapsed, move to state %s",
 151                 backoff->name, spf_backoff_state2str(backoff->state));
 152   return 0;
 153 }
 154
 155 long spf_backoff_schedule(struct spf_backoff *backoff)
 156 {
 157   long rv;
 158   struct timeval now;
 159
 160   gettimeofday(&now, NULL);
 161
 162   backoff_debug("SPF Back-off(%s) schedule called in state %s",
 163                 backoff->name, spf_backoff_state2str(backoff->state));
 164
 165   backoff->last_event_time = now;
 166
 167   switch (backoff->state)
 168     {
 169     case SPF_BACKOFF_QUIET:
 170       backoff->state = SPF_BACKOFF_SHORT_WAIT;
 171       thread_add_timer_msec(backoff->m, spf_backoff_timetolearn_elapsed,
 172                             backoff, backoff->timetolearn,
 173                             &backoff->t_timetolearn);
 174       thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed, backoff,
 175                             backoff->holddown, &backoff->t_holddown);
 176       backoff->first_event_time = now;
 177       rv = backoff->init_delay;
 178       break;
 179     case SPF_BACKOFF_SHORT_WAIT:
 180     case SPF_BACKOFF_LONG_WAIT:
 181       THREAD_TIMER_OFF(backoff->t_holddown);
 182       thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed, backoff,
 183                             backoff->holddown, &backoff->t_holddown);
 184       if (backoff->state == SPF_BACKOFF_SHORT_WAIT)
 185         rv = backoff->short_delay;
 186       else
 187         rv = backoff->long_delay;
 188       break;
 189     default:
 190       zlog_warn("SPF Back-off(%s) in unknown state", backoff->name);
 191       rv = backoff->init_delay;
 192     }
 193
 194   backoff_debug("SPF Back-off(%s) changed state to %s and returned %ld delay",
 195                 backoff->name, spf_backoff_state2str(backoff->state), rv);
 196   return rv;
 197 }
 198
 199 static const char *
 200 timeval_format(struct timeval *tv)
 201 {
 202   struct tm tm_store;
 203   struct tm *tm;
 204   static char timebuf[256];
 205
 206   if (!tv->tv_sec && !tv->tv_usec)
 207     return "(never)";
 208
 209   tm = localtime_r(&tv->tv_sec, &tm_store);
 210   if (!tm || strftime(timebuf, sizeof(timebuf),
 211                       "%Z %a %Y-%m-%d %H:%M:%S", tm) == 0)
 212     {
 213       return "???";
 214     }
 215
 216   size_t offset = strlen(timebuf);
 217   snprintf(timebuf + offset, sizeof(timebuf) - offset, ".%ld", tv->tv_usec);
 218
 219   return timebuf;
 220 }
 221
 222 void
 223 spf_backoff_show(struct spf_backoff *backoff, struct vty *vty,
 224                  const char *prefix)
 225 {
 226   vty_out(vty, "%sCurrent state:     %s%s", prefix,
 227           spf_backoff_state2str(backoff->state), VTY_NEWLINE);
 228   vty_out(vty, "%sInit timer:        %ld msec%s", prefix,
 229           backoff->init_delay, VTY_NEWLINE);
 230   vty_out(vty, "%sShort timer:       %ld msec%s", prefix,
 231           backoff->short_delay, VTY_NEWLINE);
 232   vty_out(vty, "%sLong timer:        %ld msec%s", prefix,
 233           backoff->long_delay, VTY_NEWLINE);
 234   vty_out(vty, "%sHolddown timer:    %ld msec%s", prefix,
 235           backoff->holddown, VTY_NEWLINE);
 236   if (backoff->t_holddown)
 237     {
 238       struct timeval remain = thread_timer_remain(backoff->t_holddown);
 239       vty_out(vty, "%s                   Still runs for %ld msec%s",
 240               prefix, remain.tv_sec * 1000 + remain.tv_usec/1000, VTY_NEWLINE);
 241     }
 242   else
 243     {
 244       vty_out(vty, "%s                   Inactive%s", prefix, VTY_NEWLINE);
 245     }
 246
 247   vty_out(vty, "%sTimeToLearn timer: %ld msec%s", prefix,
 248           backoff->timetolearn, VTY_NEWLINE);
 249   if (backoff->t_timetolearn)
 250     {
 251       struct timeval remain = thread_timer_remain(backoff->t_timetolearn);
 252       vty_out(vty, "%s                   Still runs for %ld msec%s",
 253               prefix, remain.tv_sec * 1000 + remain.tv_usec/1000, VTY_NEWLINE);
 254     }
 255   else
 256     {
 257       vty_out(vty, "%s                   Inactive%s", prefix, VTY_NEWLINE);
 258     }
 259
 260   vty_out(vty, "%sFirst event:       %s%s", prefix,
 261           timeval_format(&backoff->first_event_time), VTY_NEWLINE);
 262   vty_out(vty, "%sLast event:        %s%s", prefix,
 263           timeval_format(&backoff->last_event_time), VTY_NEWLINE);
 264 }
 265
 266 DEFUN(spf_backoff_debug,
 267       spf_backoff_debug_cmd,
 268       "debug spf-delay-ietf",
 269       DEBUG_STR
 270       "SPF Back-off Debugging\n")
 271 {
 272   debug_spf_backoff = true;
 273   return CMD_SUCCESS;
 274 }
 275
 276 DEFUN(no_spf_backoff_debug,
 277       no_spf_backoff_debug_cmd,
 278       "no debug spf-delay-ietf",
 279       NO_STR
 280       DEBUG_STR
 281       "SPF Back-off Debugging\n")
 282 {
 283   debug_spf_backoff = false;
 284   return CMD_SUCCESS;
 285 }
 286
 287 int
 288 spf_backoff_write_config(struct vty *vty)
 289 {
 290   int written = 0;
 291
 292   if (debug_spf_backoff)
 293     {
 294       vty_out(vty, "debug spf-delay-ietf%s", VTY_NEWLINE);
 295       written++;
 296     }
 297
 298   return written;
 299 }
 300
 301 void
 302 spf_backoff_cmd_init(void)
 303 {
 304   install_element(ENABLE_NODE, &spf_backoff_debug_cmd);
 305   install_element(CONFIG_NODE, &spf_backoff_debug_cmd);
 306   install_element(ENABLE_NODE, &no_spf_backoff_debug_cmd);
 307   install_element(CONFIG_NODE, &no_spf_backoff_debug_cmd);
 308 }
 309
 310 long
 311 spf_backoff_init_delay(struct spf_backoff *backoff)
 312 {
 313   return backoff->init_delay;
 314 }
 315
 316 long
 317 spf_backoff_short_delay(struct spf_backoff *backoff)
 318 {
 319   return backoff->short_delay;
 320 }
 321
 322 long
 323 spf_backoff_long_delay(struct spf_backoff *backoff)
 324 {
 325   return backoff->long_delay;
 326 }
 327
 328 long
 329 spf_backoff_holddown(struct spf_backoff *backoff)
 330 {
 331   return backoff->holddown;
 332 }
 333
 334 long
 335 spf_backoff_timetolearn(struct spf_backoff *backoff)
 336 {
 337   return backoff->timetolearn;
 338 }