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