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