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_TIMER_MSEC_ON(backoff->m, backoff->t_timetolearn,
 173                            spf_backoff_timetolearn_elapsed, backoff,
 174                            backoff->timetolearn);
 175       THREAD_TIMER_MSEC_ON(backoff->m, backoff->t_holddown,
 176                            spf_backoff_holddown_elapsed, backoff,
 177                            backoff->holddown);
 178       backoff->first_event_time = now;
 179       rv = backoff->init_delay;
 180       break;
 181     case SPF_BACKOFF_SHORT_WAIT:
 182     case SPF_BACKOFF_LONG_WAIT:
 183       THREAD_TIMER_OFF(backoff->t_holddown);
 184       THREAD_TIMER_MSEC_ON(backoff->m, backoff->t_holddown,
 185                            spf_backoff_holddown_elapsed, backoff,
 186                            backoff->holddown);
 187       if (backoff->state == SPF_BACKOFF_SHORT_WAIT)
 188         rv = backoff->short_delay;
 189       else
 190         rv = backoff->long_delay;
 191       break;
 192     default:
 193       zlog_warn("SPF Back-off(%s) in unknown state", backoff->name);
 194       rv = backoff->init_delay;
 195     }
 196
 197   backoff_debug("SPF Back-off(%s) changed state to %s and returned %ld delay",
 198                 backoff->name, spf_backoff_state2str(backoff->state), rv);
 199   return rv;
 200 }
 201
 202 static const char *
 203 timeval_format(struct timeval *tv)
 204 {
 205   struct tm tm_store;
 206   struct tm *tm;
 207   static char timebuf[256];
 208
 209   if (!tv->tv_sec && !tv->tv_usec)
 210     return "(never)";
 211
 212   tm = localtime_r(&tv->tv_sec, &tm_store);
 213   if (!tm || strftime(timebuf, sizeof(timebuf),
 214                       "%Z %a %Y-%m-%d %H:%M:%S", tm) == 0)
 215     {
 216       return "???";
 217     }
 218
 219   size_t offset = strlen(timebuf);
 220   snprintf(timebuf + offset, sizeof(timebuf) - offset, ".%ld", tv->tv_usec);
 221
 222   return timebuf;
 223 }
 224
 225 void
 226 spf_backoff_show(struct spf_backoff *backoff, struct vty *vty,
 227                  const char *prefix)
 228 {
 229   vty_out(vty, "%sCurrent state:     %s%s", prefix,
 230           spf_backoff_state2str(backoff->state), VTY_NEWLINE);
 231   vty_out(vty, "%sInit timer:        %ld msec%s", prefix,
 232           backoff->init_delay, VTY_NEWLINE);
 233   vty_out(vty, "%sShort timer:       %ld msec%s", prefix,
 234           backoff->short_delay, VTY_NEWLINE);
 235   vty_out(vty, "%sLong timer:        %ld msec%s", prefix,
 236           backoff->long_delay, VTY_NEWLINE);
 237   vty_out(vty, "%sHolddown timer:    %ld msec%s", prefix,
 238           backoff->holddown, VTY_NEWLINE);
 239   if (backoff->t_holddown)
 240     {
 241       struct timeval remain = thread_timer_remain(backoff->t_holddown);
 242       vty_out(vty, "%s                   Still runs for %ld msec%s",
 243               prefix, remain.tv_sec * 1000 + remain.tv_usec/1000, VTY_NEWLINE);
 244     }
 245   else
 246     {
 247       vty_out(vty, "%s                   Inactive%s", prefix, VTY_NEWLINE);
 248     }
 249
 250   vty_out(vty, "%sTimeToLearn timer: %ld msec%s", prefix,
 251           backoff->timetolearn, VTY_NEWLINE);
 252   if (backoff->t_timetolearn)
 253     {
 254       struct timeval remain = thread_timer_remain(backoff->t_timetolearn);
 255       vty_out(vty, "%s                   Still runs for %ld msec%s",
 256               prefix, remain.tv_sec * 1000 + remain.tv_usec/1000, VTY_NEWLINE);
 257     }
 258   else
 259     {
 260       vty_out(vty, "%s                   Inactive%s", prefix, VTY_NEWLINE);
 261     }
 262
 263   vty_out(vty, "%sFirst event:       %s%s", prefix,
 264           timeval_format(&backoff->first_event_time), VTY_NEWLINE);
 265   vty_out(vty, "%sLast event:        %s%s", prefix,
 266           timeval_format(&backoff->last_event_time), VTY_NEWLINE);
 267 }
 268
 269 DEFUN(spf_backoff_debug,
 270       spf_backoff_debug_cmd,
 271       "debug spf-delay-ietf",
 272       DEBUG_STR
 273       "SPF Back-off Debugging\n")
 274 {
 275   debug_spf_backoff = true;
 276   return CMD_SUCCESS;
 277 }
 278
 279 DEFUN(no_spf_backoff_debug,
 280       no_spf_backoff_debug_cmd,
 281       "no debug spf-delay-ietf",
 282       NO_STR
 283       DEBUG_STR
 284       "SPF Back-off Debugging\n")
 285 {
 286   debug_spf_backoff = false;
 287   return CMD_SUCCESS;
 288 }
 289
 290 int
 291 spf_backoff_write_config(struct vty *vty)
 292 {
 293   int written = 0;
 294
 295   if (debug_spf_backoff)
 296     {
 297       vty_out(vty, "debug spf-delay-ietf%s", VTY_NEWLINE);
 298       written++;
 299     }
 300
 301   return written;
 302 }
 303
 304 void
 305 spf_backoff_cmd_init(void)
 306 {
 307   install_element(ENABLE_NODE, &spf_backoff_debug_cmd);
 308   install_element(CONFIG_NODE, &spf_backoff_debug_cmd);
 309   install_element(ENABLE_NODE, &no_spf_backoff_debug_cmd);
 310   install_element(CONFIG_NODE, &no_spf_backoff_debug_cmd);
 311 }
 312
 313 long
 314 spf_backoff_init_delay(struct spf_backoff *backoff)
 315 {
 316   return backoff->init_delay;
 317 }
 318
 319 long
 320 spf_backoff_short_delay(struct spf_backoff *backoff)
 321 {
 322   return backoff->short_delay;
 323 }
 324
 325 long
 326 spf_backoff_long_delay(struct spf_backoff *backoff)
 327 {
 328   return backoff->long_delay;
 329 }
 330
 331 long
 332 spf_backoff_holddown(struct spf_backoff *backoff)
 333 {
 334   return backoff->holddown;
 335 }
 336
 337 long
 338 spf_backoff_timetolearn(struct spf_backoff *backoff)
 339 {
 340   return backoff->timetolearn;
 341 }