1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * This is an implementation of the IETF SPF delay algorithm
4 * as explained in draft-ietf-rtgwg-backoff-algo-04
6 * Created: 25-01-2017 by S. Litkowski
8 * Copyright (C) 2017 Orange Labs http://www.orange.com/
9 * Copyright (C) 2017 by Christian Franke, Open Source Routing / NetDEF Inc.
11 * This file is part of FRRouting (FRR)
16 #include "spf_backoff.h"
23 DEFINE_MTYPE_STATIC(LIB
, SPF_BACKOFF
, "SPF backoff");
24 DEFINE_MTYPE_STATIC(LIB
, SPF_BACKOFF_NAME
, "SPF backoff name");
26 static bool debug_spf_backoff
= false;
27 #define backoff_debug(...) \
29 if (debug_spf_backoff) \
30 zlog_debug(__VA_ARGS__); \
33 enum spf_backoff_state
{
35 SPF_BACKOFF_SHORT_WAIT
,
40 struct thread_master
*m
;
42 /* Timers as per draft */
50 enum spf_backoff_state state
;
51 struct event
*t_holddown
;
52 struct event
*t_timetolearn
;
56 struct timeval first_event_time
;
57 struct timeval last_event_time
;
60 static const char *spf_backoff_state2str(enum spf_backoff_state state
)
63 case SPF_BACKOFF_QUIET
:
65 case SPF_BACKOFF_SHORT_WAIT
:
67 case SPF_BACKOFF_LONG_WAIT
:
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
,
78 struct spf_backoff
*rv
;
80 rv
= XCALLOC(MTYPE_SPF_BACKOFF
, sizeof(*rv
));
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
;
89 rv
->state
= SPF_BACKOFF_QUIET
;
91 rv
->name
= XSTRDUP(MTYPE_SPF_BACKOFF_NAME
, name
);
95 void spf_backoff_free(struct spf_backoff
*backoff
)
100 event_cancel(&backoff
->t_holddown
);
101 event_cancel(&backoff
->t_timetolearn
);
102 XFREE(MTYPE_SPF_BACKOFF_NAME
, backoff
->name
);
104 XFREE(MTYPE_SPF_BACKOFF
, backoff
);
107 static void spf_backoff_timetolearn_elapsed(struct event
*thread
)
109 struct spf_backoff
*backoff
= THREAD_ARG(thread
);
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
));
116 static void spf_backoff_holddown_elapsed(struct event
*thread
)
118 struct spf_backoff
*backoff
= THREAD_ARG(thread
);
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
));
127 long spf_backoff_schedule(struct spf_backoff
*backoff
)
132 gettimeofday(&now
, NULL
);
134 backoff_debug("SPF Back-off(%s) schedule called in state %s",
135 backoff
->name
, spf_backoff_state2str(backoff
->state
));
137 backoff
->last_event_time
= now
;
139 switch (backoff
->state
) {
140 case SPF_BACKOFF_QUIET
:
141 backoff
->state
= SPF_BACKOFF_SHORT_WAIT
;
142 event_add_timer_msec(
143 backoff
->m
, spf_backoff_timetolearn_elapsed
, backoff
,
144 backoff
->timetolearn
, &backoff
->t_timetolearn
);
145 event_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
;
151 case SPF_BACKOFF_SHORT_WAIT
:
152 case SPF_BACKOFF_LONG_WAIT
:
153 event_cancel(&backoff
->t_holddown
);
154 event_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
;
160 rv
= backoff
->long_delay
;
165 "SPF Back-off(%s) changed state to %s and returned %ld delay",
166 backoff
->name
, spf_backoff_state2str(backoff
->state
), rv
);
170 static const char *timeval_format(struct timeval
*tv
)
174 static char timebuf
[256];
176 if (!tv
->tv_sec
&& !tv
->tv_usec
)
179 tm
= localtime_r(&tv
->tv_sec
, &tm_store
);
181 || strftime(timebuf
, sizeof(timebuf
), "%Z %a %Y-%m-%d %H:%M:%S", tm
)
186 size_t offset
= strlen(timebuf
);
187 snprintf(timebuf
+ offset
, sizeof(timebuf
) - offset
, ".%ld",
188 (long int)tv
->tv_usec
);
193 void spf_backoff_show(struct spf_backoff
*backoff
, struct vty
*vty
,
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
,
206 if (backoff
->t_holddown
) {
207 struct timeval remain
= event_timer_remain(backoff
->t_holddown
);
208 vty_out(vty
, "%s Still runs for %lld msec\n",
210 (long long)remain
.tv_sec
* 1000
211 + remain
.tv_usec
/ 1000);
213 vty_out(vty
, "%s Inactive\n", prefix
);
216 vty_out(vty
, "%sTimeToLearn timer: %ld msec\n", prefix
,
217 backoff
->timetolearn
);
218 if (backoff
->t_timetolearn
) {
219 struct timeval remain
=
220 event_timer_remain(backoff
->t_timetolearn
);
221 vty_out(vty
, "%s Still runs for %lld msec\n",
223 (long long)remain
.tv_sec
* 1000
224 + remain
.tv_usec
/ 1000);
226 vty_out(vty
, "%s Inactive\n", prefix
);
229 vty_out(vty
, "%sFirst event: %s\n", prefix
,
230 timeval_format(&backoff
->first_event_time
));
231 vty_out(vty
, "%sLast event: %s\n", prefix
,
232 timeval_format(&backoff
->last_event_time
));
235 DEFUN(spf_backoff_debug
,
236 spf_backoff_debug_cmd
,
237 "debug spf-delay-ietf",
239 "SPF Back-off Debugging\n")
241 debug_spf_backoff
= true;
245 DEFUN(no_spf_backoff_debug
,
246 no_spf_backoff_debug_cmd
,
247 "no debug spf-delay-ietf",
250 "SPF Back-off Debugging\n")
252 debug_spf_backoff
= false;
256 int spf_backoff_write_config(struct vty
*vty
)
260 if (debug_spf_backoff
) {
261 vty_out(vty
, "debug spf-delay-ietf\n");
268 void spf_backoff_cmd_init(void)
270 install_element(ENABLE_NODE
, &spf_backoff_debug_cmd
);
271 install_element(CONFIG_NODE
, &spf_backoff_debug_cmd
);
272 install_element(ENABLE_NODE
, &no_spf_backoff_debug_cmd
);
273 install_element(CONFIG_NODE
, &no_spf_backoff_debug_cmd
);
276 long spf_backoff_init_delay(struct spf_backoff
*backoff
)
278 return backoff
->init_delay
;
281 long spf_backoff_short_delay(struct spf_backoff
*backoff
)
283 return backoff
->short_delay
;
286 long spf_backoff_long_delay(struct spf_backoff
*backoff
)
288 return backoff
->long_delay
;
291 long spf_backoff_holddown(struct spf_backoff
*backoff
)
293 return backoff
->holddown
;
296 long spf_backoff_timetolearn(struct spf_backoff
*backoff
)
298 return backoff
->timetolearn
;