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