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