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_cancel(&backoff->t_holddown);
 114         thread_cancel(&backoff->t_timetolearn);
 115         XFREE(MTYPE_SPF_BACKOFF_NAME, backoff->name);
 116
 117         XFREE(MTYPE_SPF_BACKOFF, backoff);
 118 }
 119
 120 static void spf_backoff_timetolearn_elapsed(struct thread *thread)
 121 {
 122         struct spf_backoff *backoff = THREAD_ARG(thread);
 123
 124         backoff->state = SPF_BACKOFF_LONG_WAIT;
 125         backoff_debug("SPF Back-off(%s) TIMETOLEARN elapsed, move to state %s",
 126                       backoff->name, spf_backoff_state2str(backoff->state));
 127 }
 128
 129 static void spf_backoff_holddown_elapsed(struct thread *thread)
 130 {
 131         struct spf_backoff *backoff = THREAD_ARG(thread);
 132
 133         THREAD_OFF(backoff->t_timetolearn);
 134         timerclear(&backoff->first_event_time);
 135         backoff->state = SPF_BACKOFF_QUIET;
 136         backoff_debug("SPF Back-off(%s) HOLDDOWN elapsed, move to state %s",
 137                       backoff->name, spf_backoff_state2str(backoff->state));
 138 }
 139
 140 long spf_backoff_schedule(struct spf_backoff *backoff)
 141 {
 142         long rv = 0;
 143         struct timeval now;
 144
 145         gettimeofday(&now, NULL);
 146
 147         backoff_debug("SPF Back-off(%s) schedule called in state %s",
 148                       backoff->name, spf_backoff_state2str(backoff->state));
 149
 150         backoff->last_event_time = now;
 151
 152         switch (backoff->state) {
 153         case SPF_BACKOFF_QUIET:
 154                 backoff->state = SPF_BACKOFF_SHORT_WAIT;
 155                 thread_add_timer_msec(
 156                         backoff->m, spf_backoff_timetolearn_elapsed, backoff,
 157                         backoff->timetolearn, &backoff->t_timetolearn);
 158                 thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed,
 159                                       backoff, backoff->holddown,
 160                                       &backoff->t_holddown);
 161                 backoff->first_event_time = now;
 162                 rv = backoff->init_delay;
 163                 break;
 164         case SPF_BACKOFF_SHORT_WAIT:
 165         case SPF_BACKOFF_LONG_WAIT:
 166                 thread_cancel(&backoff->t_holddown);
 167                 thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed,
 168                                       backoff, backoff->holddown,
 169                                       &backoff->t_holddown);
 170                 if (backoff->state == SPF_BACKOFF_SHORT_WAIT)
 171                         rv = backoff->short_delay;
 172                 else
 173                         rv = backoff->long_delay;
 174                 break;
 175         }
 176
 177         backoff_debug(
 178                 "SPF Back-off(%s) changed state to %s and returned %ld delay",
 179                 backoff->name, spf_backoff_state2str(backoff->state), rv);
 180         return rv;
 181 }
 182
 183 static const char *timeval_format(struct timeval *tv)
 184 {
 185         struct tm tm_store;
 186         struct tm *tm;
 187         static char timebuf[256];
 188
 189         if (!tv->tv_sec && !tv->tv_usec)
 190                 return "(never)";
 191
 192         tm = localtime_r(&tv->tv_sec, &tm_store);
 193         if (!tm
 194             || strftime(timebuf, sizeof(timebuf), "%Z %a %Y-%m-%d %H:%M:%S", tm)
 195                        == 0) {
 196                 return "???";
 197         }
 198
 199         size_t offset = strlen(timebuf);
 200         snprintf(timebuf + offset, sizeof(timebuf) - offset, ".%ld",
 201                  (long int)tv->tv_usec);
 202
 203         return timebuf;
 204 }
 205
 206 void spf_backoff_show(struct spf_backoff *backoff, struct vty *vty,
 207                       const char *prefix)
 208 {
 209         vty_out(vty, "%sCurrent state:     %s\n", prefix,
 210                 spf_backoff_state2str(backoff->state));
 211         vty_out(vty, "%sInit timer:        %ld msec\n", prefix,
 212                 backoff->init_delay);
 213         vty_out(vty, "%sShort timer:       %ld msec\n", prefix,
 214                 backoff->short_delay);
 215         vty_out(vty, "%sLong timer:        %ld msec\n", prefix,
 216                 backoff->long_delay);
 217         vty_out(vty, "%sHolddown timer:    %ld msec\n", prefix,
 218                 backoff->holddown);
 219         if (backoff->t_holddown) {
 220                 struct timeval remain =
 221                         thread_timer_remain(backoff->t_holddown);
 222                 vty_out(vty, "%s                   Still runs for %lld msec\n",
 223                         prefix,
 224                         (long long)remain.tv_sec * 1000
 225                                 + remain.tv_usec / 1000);
 226         } else {
 227                 vty_out(vty, "%s                   Inactive\n", prefix);
 228         }
 229
 230         vty_out(vty, "%sTimeToLearn timer: %ld msec\n", prefix,
 231                 backoff->timetolearn);
 232         if (backoff->t_timetolearn) {
 233                 struct timeval remain =
 234                         thread_timer_remain(backoff->t_timetolearn);
 235                 vty_out(vty, "%s                   Still runs for %lld msec\n",
 236                         prefix,
 237                         (long long)remain.tv_sec * 1000
 238                                 + remain.tv_usec / 1000);
 239         } else {
 240                 vty_out(vty, "%s                   Inactive\n", prefix);
 241         }
 242
 243         vty_out(vty, "%sFirst event:       %s\n", prefix,
 244                 timeval_format(&backoff->first_event_time));
 245         vty_out(vty, "%sLast event:        %s\n", prefix,
 246                 timeval_format(&backoff->last_event_time));
 247 }
 248
 249 DEFUN(spf_backoff_debug,
 250       spf_backoff_debug_cmd,
 251       "debug spf-delay-ietf",
 252       DEBUG_STR
 253       "SPF Back-off Debugging\n")
 254 {
 255         debug_spf_backoff = true;
 256         return CMD_SUCCESS;
 257 }
 258
 259 DEFUN(no_spf_backoff_debug,
 260       no_spf_backoff_debug_cmd,
 261       "no debug spf-delay-ietf",
 262       NO_STR
 263       DEBUG_STR
 264       "SPF Back-off Debugging\n")
 265 {
 266         debug_spf_backoff = false;
 267         return CMD_SUCCESS;
 268 }
 269
 270 int spf_backoff_write_config(struct vty *vty)
 271 {
 272         int written = 0;
 273
 274         if (debug_spf_backoff) {
 275                 vty_out(vty, "debug spf-delay-ietf\n");
 276                 written++;
 277         }
 278
 279         return written;
 280 }
 281
 282 void spf_backoff_cmd_init(void)
 283 {
 284         install_element(ENABLE_NODE, &spf_backoff_debug_cmd);
 285         install_element(CONFIG_NODE, &spf_backoff_debug_cmd);
 286         install_element(ENABLE_NODE, &no_spf_backoff_debug_cmd);
 287         install_element(CONFIG_NODE, &no_spf_backoff_debug_cmd);
 288 }
 289
 290 long spf_backoff_init_delay(struct spf_backoff *backoff)
 291 {
 292         return backoff->init_delay;
 293 }
 294
 295 long spf_backoff_short_delay(struct spf_backoff *backoff)
 296 {
 297         return backoff->short_delay;
 298 }
 299
 300 long spf_backoff_long_delay(struct spf_backoff *backoff)
 301 {
 302         return backoff->long_delay;
 303 }
 304
 305 long spf_backoff_holddown(struct spf_backoff *backoff)
 306 {
 307         return backoff->holddown;
 308 }
 309
 310 long spf_backoff_timetolearn(struct spf_backoff *backoff)
 311 {
 312         return backoff->timetolearn;
 313 }