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