2 * This is an implementation of the IETF SPF delay algorithm
3 * as explained in draft-ietf-rtgwg-backoff-algo-04
5 * Created: 25-01-2017 by S. Litkowski
7 * Copyright (C) 2017 Orange Labs http://www.orange.com/
8 * Copyright (C) 2017 by Christian Franke, Open Source Routing / NetDEF Inc.
10 * This file is part of FRRouting (FRR)
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
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.
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
29 #include "spf_backoff.h"
36 DEFINE_MTYPE_STATIC(LIB
, SPF_BACKOFF
, "SPF backoff");
37 DEFINE_MTYPE_STATIC(LIB
, SPF_BACKOFF_NAME
, "SPF backoff name");
39 static bool debug_spf_backoff
= false;
40 #define backoff_debug(...) \
42 if (debug_spf_backoff) \
43 zlog_debug(__VA_ARGS__); \
46 enum spf_backoff_state
{
48 SPF_BACKOFF_SHORT_WAIT
,
53 struct thread_master
*m
;
55 /* Timers as per draft */
63 enum spf_backoff_state state
;
64 struct thread
*t_holddown
;
65 struct thread
*t_timetolearn
;
69 struct timeval first_event_time
;
70 struct timeval last_event_time
;
73 static const char *spf_backoff_state2str(enum spf_backoff_state state
)
76 case SPF_BACKOFF_QUIET
:
78 case SPF_BACKOFF_SHORT_WAIT
:
80 case SPF_BACKOFF_LONG_WAIT
:
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
,
91 struct spf_backoff
*rv
;
93 rv
= XCALLOC(MTYPE_SPF_BACKOFF
, sizeof(*rv
));
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
;
102 rv
->state
= SPF_BACKOFF_QUIET
;
104 rv
->name
= XSTRDUP(MTYPE_SPF_BACKOFF_NAME
, name
);
108 void spf_backoff_free(struct spf_backoff
*backoff
)
113 thread_cancel(&backoff
->t_holddown
);
114 thread_cancel(&backoff
->t_timetolearn
);
115 XFREE(MTYPE_SPF_BACKOFF_NAME
, backoff
->name
);
117 XFREE(MTYPE_SPF_BACKOFF
, backoff
);
120 static void spf_backoff_timetolearn_elapsed(struct thread
*thread
)
122 struct spf_backoff
*backoff
= THREAD_ARG(thread
);
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
));
129 static void spf_backoff_holddown_elapsed(struct thread
*thread
)
131 struct spf_backoff
*backoff
= THREAD_ARG(thread
);
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
));
140 long spf_backoff_schedule(struct spf_backoff
*backoff
)
145 gettimeofday(&now
, NULL
);
147 backoff_debug("SPF Back-off(%s) schedule called in state %s",
148 backoff
->name
, spf_backoff_state2str(backoff
->state
));
150 backoff
->last_event_time
= now
;
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
;
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
;
173 rv
= backoff
->long_delay
;
178 "SPF Back-off(%s) changed state to %s and returned %ld delay",
179 backoff
->name
, spf_backoff_state2str(backoff
->state
), rv
);
183 static const char *timeval_format(struct timeval
*tv
)
187 static char timebuf
[256];
189 if (!tv
->tv_sec
&& !tv
->tv_usec
)
192 tm
= localtime_r(&tv
->tv_sec
, &tm_store
);
194 || strftime(timebuf
, sizeof(timebuf
), "%Z %a %Y-%m-%d %H:%M:%S", tm
)
199 size_t offset
= strlen(timebuf
);
200 snprintf(timebuf
+ offset
, sizeof(timebuf
) - offset
, ".%ld",
201 (long int)tv
->tv_usec
);
206 void spf_backoff_show(struct spf_backoff
*backoff
, struct vty
*vty
,
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
,
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",
224 (long long)remain
.tv_sec
* 1000
225 + remain
.tv_usec
/ 1000);
227 vty_out(vty
, "%s Inactive\n", prefix
);
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",
237 (long long)remain
.tv_sec
* 1000
238 + remain
.tv_usec
/ 1000);
240 vty_out(vty
, "%s Inactive\n", prefix
);
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
));
249 DEFUN(spf_backoff_debug
,
250 spf_backoff_debug_cmd
,
251 "debug spf-delay-ietf",
253 "SPF Back-off Debugging\n")
255 debug_spf_backoff
= true;
259 DEFUN(no_spf_backoff_debug
,
260 no_spf_backoff_debug_cmd
,
261 "no debug spf-delay-ietf",
264 "SPF Back-off Debugging\n")
266 debug_spf_backoff
= false;
270 int spf_backoff_write_config(struct vty
*vty
)
274 if (debug_spf_backoff
) {
275 vty_out(vty
, "debug spf-delay-ietf\n");
282 void spf_backoff_cmd_init(void)
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
);
290 long spf_backoff_init_delay(struct spf_backoff
*backoff
)
292 return backoff
->init_delay
;
295 long spf_backoff_short_delay(struct spf_backoff
*backoff
)
297 return backoff
->short_delay
;
300 long spf_backoff_long_delay(struct spf_backoff
*backoff
)
302 return backoff
->long_delay
;
305 long spf_backoff_holddown(struct spf_backoff
*backoff
)
307 return backoff
->holddown
;
310 long spf_backoff_timetolearn(struct spf_backoff
*backoff
)
312 return backoff
->timetolearn
;