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