lib/spf_backoff.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * This is an implementation of the IETF SPF delay algorithm
   4  * as explained in draft-ietf-rtgwg-backoff-algo-04
   5  *
   6  * Created: 25-01-2017 by S. Litkowski
   7  *
   8  * Copyright (C) 2017 Orange Labs http://www.orange.com/
   9  * Copyright (C) 2017 by Christian Franke, Open Source Routing / NetDEF Inc.
  10  *
  11  * This file is part of FRRouting (FRR)
  12  */
  13
  14 #include <zebra.h>
  15
  16 #include "spf_backoff.h"
  17
  18 #include "command.h"
  19 #include "memory.h"
  20 #include "thread.h"
  21 #include "vty.h"
  22
  23 DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF, "SPF backoff");
  24 DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF_NAME, "SPF backoff name");
  25
  26 static bool debug_spf_backoff = false;
  27 #define backoff_debug(...)                                                     \
  28         do {                                                                   \
  29                 if (debug_spf_backoff)                                         \
  30                         zlog_debug(__VA_ARGS__);                               \
  31         } while (0)
  32
  33 enum spf_backoff_state {
  34         SPF_BACKOFF_QUIET,
  35         SPF_BACKOFF_SHORT_WAIT,
  36         SPF_BACKOFF_LONG_WAIT
  37 };
  38
  39 struct spf_backoff {
  40         struct thread_master *m;
  41
  42         /* Timers as per draft */
  43         long init_delay;
  44         long short_delay;
  45         long long_delay;
  46         long holddown;
  47         long timetolearn;
  48
  49         /* State machine */
  50         enum spf_backoff_state state;
  51         struct thread *t_holddown;
  52         struct thread *t_timetolearn;
  53
  54         /* For debugging */
  55         char *name;
  56         struct timeval first_event_time;
  57         struct timeval last_event_time;
  58 };
  59
  60 static const char *spf_backoff_state2str(enum spf_backoff_state state)
  61 {
  62         switch (state) {
  63         case SPF_BACKOFF_QUIET:
  64                 return "QUIET";
  65         case SPF_BACKOFF_SHORT_WAIT:
  66                 return "SHORT_WAIT";
  67         case SPF_BACKOFF_LONG_WAIT:
  68                 return "LONG_WAIT";
  69         }
  70         return "???";
  71 }
  72
  73 struct spf_backoff *spf_backoff_new(struct thread_master *m, const char *name,
  74                                     long init_delay, long short_delay,
  75                                     long long_delay, long holddown,
  76                                     long timetolearn)
  77 {
  78         struct spf_backoff *rv;
  79
  80         rv = XCALLOC(MTYPE_SPF_BACKOFF, sizeof(*rv));
  81         rv->m = m;
  82
  83         rv->init_delay = init_delay;
  84         rv->short_delay = short_delay;
  85         rv->long_delay = long_delay;
  86         rv->holddown = holddown;
  87         rv->timetolearn = timetolearn;
  88
  89         rv->state = SPF_BACKOFF_QUIET;
  90
  91         rv->name = XSTRDUP(MTYPE_SPF_BACKOFF_NAME, name);
  92         return rv;
  93 }
  94
  95 void spf_backoff_free(struct spf_backoff *backoff)
  96 {
  97         if (!backoff)
  98                 return;
  99
 100         thread_cancel(&backoff->t_holddown);
 101         thread_cancel(&backoff->t_timetolearn);
 102         XFREE(MTYPE_SPF_BACKOFF_NAME, backoff->name);
 103
 104         XFREE(MTYPE_SPF_BACKOFF, backoff);
 105 }
 106
 107 static void spf_backoff_timetolearn_elapsed(struct thread *thread)
 108 {
 109         struct spf_backoff *backoff = THREAD_ARG(thread);
 110
 111         backoff->state = SPF_BACKOFF_LONG_WAIT;
 112         backoff_debug("SPF Back-off(%s) TIMETOLEARN elapsed, move to state %s",
 113                       backoff->name, spf_backoff_state2str(backoff->state));
 114 }
 115
 116 static void spf_backoff_holddown_elapsed(struct thread *thread)
 117 {
 118         struct spf_backoff *backoff = THREAD_ARG(thread);
 119
 120         THREAD_OFF(backoff->t_timetolearn);
 121         timerclear(&backoff->first_event_time);
 122         backoff->state = SPF_BACKOFF_QUIET;
 123         backoff_debug("SPF Back-off(%s) HOLDDOWN elapsed, move to state %s",
 124                       backoff->name, spf_backoff_state2str(backoff->state));
 125 }
 126
 127 long spf_backoff_schedule(struct spf_backoff *backoff)
 128 {
 129         long rv = 0;
 130         struct timeval now;
 131
 132         gettimeofday(&now, NULL);
 133
 134         backoff_debug("SPF Back-off(%s) schedule called in state %s",
 135                       backoff->name, spf_backoff_state2str(backoff->state));
 136
 137         backoff->last_event_time = now;
 138
 139         switch (backoff->state) {
 140         case SPF_BACKOFF_QUIET:
 141                 backoff->state = SPF_BACKOFF_SHORT_WAIT;
 142                 thread_add_timer_msec(
 143                         backoff->m, spf_backoff_timetolearn_elapsed, backoff,
 144                         backoff->timetolearn, &backoff->t_timetolearn);
 145                 thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed,
 146                                       backoff, backoff->holddown,
 147                                       &backoff->t_holddown);
 148                 backoff->first_event_time = now;
 149                 rv = backoff->init_delay;
 150                 break;
 151         case SPF_BACKOFF_SHORT_WAIT:
 152         case SPF_BACKOFF_LONG_WAIT:
 153                 thread_cancel(&backoff->t_holddown);
 154                 thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed,
 155                                       backoff, backoff->holddown,
 156                                       &backoff->t_holddown);
 157                 if (backoff->state == SPF_BACKOFF_SHORT_WAIT)
 158                         rv = backoff->short_delay;
 159                 else
 160                         rv = backoff->long_delay;
 161                 break;
 162         }
 163
 164         backoff_debug(
 165                 "SPF Back-off(%s) changed state to %s and returned %ld delay",
 166                 backoff->name, spf_backoff_state2str(backoff->state), rv);
 167         return rv;
 168 }
 169
 170 static const char *timeval_format(struct timeval *tv)
 171 {
 172         struct tm tm_store;
 173         struct tm *tm;
 174         static char timebuf[256];
 175
 176         if (!tv->tv_sec && !tv->tv_usec)
 177                 return "(never)";
 178
 179         tm = localtime_r(&tv->tv_sec, &tm_store);
 180         if (!tm
 181             || strftime(timebuf, sizeof(timebuf), "%Z %a %Y-%m-%d %H:%M:%S", tm)
 182                        == 0) {
 183                 return "???";
 184         }
 185
 186         size_t offset = strlen(timebuf);
 187         snprintf(timebuf + offset, sizeof(timebuf) - offset, ".%ld",
 188                  (long int)tv->tv_usec);
 189
 190         return timebuf;
 191 }
 192
 193 void spf_backoff_show(struct spf_backoff *backoff, struct vty *vty,
 194                       const char *prefix)
 195 {
 196         vty_out(vty, "%sCurrent state:     %s\n", prefix,
 197                 spf_backoff_state2str(backoff->state));
 198         vty_out(vty, "%sInit timer:        %ld msec\n", prefix,
 199                 backoff->init_delay);
 200         vty_out(vty, "%sShort timer:       %ld msec\n", prefix,
 201                 backoff->short_delay);
 202         vty_out(vty, "%sLong timer:        %ld msec\n", prefix,
 203                 backoff->long_delay);
 204         vty_out(vty, "%sHolddown timer:    %ld msec\n", prefix,
 205                 backoff->holddown);
 206         if (backoff->t_holddown) {
 207                 struct timeval remain =
 208                         thread_timer_remain(backoff->t_holddown);
 209                 vty_out(vty, "%s                   Still runs for %lld msec\n",
 210                         prefix,
 211                         (long long)remain.tv_sec * 1000
 212                                 + remain.tv_usec / 1000);
 213         } else {
 214                 vty_out(vty, "%s                   Inactive\n", prefix);
 215         }
 216
 217         vty_out(vty, "%sTimeToLearn timer: %ld msec\n", prefix,
 218                 backoff->timetolearn);
 219         if (backoff->t_timetolearn) {
 220                 struct timeval remain =
 221                         thread_timer_remain(backoff->t_timetolearn);
 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, "%sFirst event:       %s\n", prefix,
 231                 timeval_format(&backoff->first_event_time));
 232         vty_out(vty, "%sLast event:        %s\n", prefix,
 233                 timeval_format(&backoff->last_event_time));
 234 }
 235
 236 DEFUN(spf_backoff_debug,
 237       spf_backoff_debug_cmd,
 238       "debug spf-delay-ietf",
 239       DEBUG_STR
 240       "SPF Back-off Debugging\n")
 241 {
 242         debug_spf_backoff = true;
 243         return CMD_SUCCESS;
 244 }
 245
 246 DEFUN(no_spf_backoff_debug,
 247       no_spf_backoff_debug_cmd,
 248       "no debug spf-delay-ietf",
 249       NO_STR
 250       DEBUG_STR
 251       "SPF Back-off Debugging\n")
 252 {
 253         debug_spf_backoff = false;
 254         return CMD_SUCCESS;
 255 }
 256
 257 int spf_backoff_write_config(struct vty *vty)
 258 {
 259         int written = 0;
 260
 261         if (debug_spf_backoff) {
 262                 vty_out(vty, "debug spf-delay-ietf\n");
 263                 written++;
 264         }
 265
 266         return written;
 267 }
 268
 269 void spf_backoff_cmd_init(void)
 270 {
 271         install_element(ENABLE_NODE, &spf_backoff_debug_cmd);
 272         install_element(CONFIG_NODE, &spf_backoff_debug_cmd);
 273         install_element(ENABLE_NODE, &no_spf_backoff_debug_cmd);
 274         install_element(CONFIG_NODE, &no_spf_backoff_debug_cmd);
 275 }
 276
 277 long spf_backoff_init_delay(struct spf_backoff *backoff)
 278 {
 279         return backoff->init_delay;
 280 }
 281
 282 long spf_backoff_short_delay(struct spf_backoff *backoff)
 283 {
 284         return backoff->short_delay;
 285 }
 286
 287 long spf_backoff_long_delay(struct spf_backoff *backoff)
 288 {
 289         return backoff->long_delay;
 290 }
 291
 292 long spf_backoff_holddown(struct spf_backoff *backoff)
 293 {
 294         return backoff->holddown;
 295 }
 296
 297 long spf_backoff_timetolearn(struct spf_backoff *backoff)
 298 {
 299         return backoff->timetolearn;
 300 }