]>
Commit | Line | Data |
---|---|---|
acddc0ed | 1 | // SPDX-License-Identifier: GPL-2.0-or-later |
c1d0d21f CF |
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 | * | |
8678d638 | 11 | * This file is part of FRRouting (FRR) |
c1d0d21f CF |
12 | */ |
13 | ||
14 | #include <zebra.h> | |
15 | ||
16 | #include "spf_backoff.h" | |
17 | ||
18 | #include "command.h" | |
19 | #include "memory.h" | |
24a58196 | 20 | #include "frrevent.h" |
c1d0d21f CF |
21 | #include "vty.h" |
22 | ||
bf8d3d6a DL |
23 | DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF, "SPF backoff"); |
24 | DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF_NAME, "SPF backoff name"); | |
c1d0d21f CF |
25 | |
26 | static bool debug_spf_backoff = false; | |
d62a17ae | 27 | #define backoff_debug(...) \ |
28 | do { \ | |
29 | if (debug_spf_backoff) \ | |
30 | zlog_debug(__VA_ARGS__); \ | |
31 | } while (0) | |
c1d0d21f CF |
32 | |
33 | enum spf_backoff_state { | |
d62a17ae | 34 | SPF_BACKOFF_QUIET, |
35 | SPF_BACKOFF_SHORT_WAIT, | |
36 | SPF_BACKOFF_LONG_WAIT | |
c1d0d21f CF |
37 | }; |
38 | ||
39 | struct spf_backoff { | |
cd9d0537 | 40 | struct event_loop *m; |
d62a17ae | 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; | |
e6685141 DS |
51 | struct event *t_holddown; |
52 | struct event *t_timetolearn; | |
d62a17ae | 53 | |
54 | /* For debugging */ | |
55 | char *name; | |
56 | struct timeval first_event_time; | |
57 | struct timeval last_event_time; | |
c1d0d21f CF |
58 | }; |
59 | ||
d62a17ae | 60 | static const char *spf_backoff_state2str(enum spf_backoff_state state) |
c1d0d21f | 61 | { |
d62a17ae | 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 "???"; | |
c1d0d21f CF |
71 | } |
72 | ||
cd9d0537 | 73 | struct spf_backoff *spf_backoff_new(struct event_loop *m, const char *name, |
d62a17ae | 74 | long init_delay, long short_delay, |
75 | long long_delay, long holddown, | |
76 | long timetolearn) | |
c1d0d21f | 77 | { |
d62a17ae | 78 | struct spf_backoff *rv; |
c1d0d21f | 79 | |
d62a17ae | 80 | rv = XCALLOC(MTYPE_SPF_BACKOFF, sizeof(*rv)); |
81 | rv->m = m; | |
c1d0d21f | 82 | |
d62a17ae | 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; | |
c1d0d21f | 88 | |
d62a17ae | 89 | rv->state = SPF_BACKOFF_QUIET; |
c1d0d21f | 90 | |
d62a17ae | 91 | rv->name = XSTRDUP(MTYPE_SPF_BACKOFF_NAME, name); |
92 | return rv; | |
c1d0d21f CF |
93 | } |
94 | ||
d62a17ae | 95 | void spf_backoff_free(struct spf_backoff *backoff) |
c1d0d21f | 96 | { |
d62a17ae | 97 | if (!backoff) |
98 | return; | |
c1d0d21f | 99 | |
332beb64 DS |
100 | event_cancel(&backoff->t_holddown); |
101 | event_cancel(&backoff->t_timetolearn); | |
d62a17ae | 102 | XFREE(MTYPE_SPF_BACKOFF_NAME, backoff->name); |
c1d0d21f | 103 | |
d62a17ae | 104 | XFREE(MTYPE_SPF_BACKOFF, backoff); |
c1d0d21f CF |
105 | } |
106 | ||
e6685141 | 107 | static void spf_backoff_timetolearn_elapsed(struct event *thread) |
c1d0d21f | 108 | { |
e16d030c | 109 | struct spf_backoff *backoff = EVENT_ARG(thread); |
c1d0d21f | 110 | |
d62a17ae | 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)); | |
c1d0d21f CF |
114 | } |
115 | ||
e6685141 | 116 | static void spf_backoff_holddown_elapsed(struct event *thread) |
c1d0d21f | 117 | { |
e16d030c | 118 | struct spf_backoff *backoff = EVENT_ARG(thread); |
d62a17ae | 119 | |
e16d030c | 120 | EVENT_OFF(backoff->t_timetolearn); |
d62a17ae | 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)); | |
c1d0d21f CF |
125 | } |
126 | ||
127 | long spf_backoff_schedule(struct spf_backoff *backoff) | |
128 | { | |
496764bb | 129 | long rv = 0; |
d62a17ae | 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; | |
907a2395 | 142 | event_add_timer_msec( |
d62a17ae | 143 | backoff->m, spf_backoff_timetolearn_elapsed, backoff, |
144 | backoff->timetolearn, &backoff->t_timetolearn); | |
907a2395 DS |
145 | event_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed, |
146 | backoff, backoff->holddown, | |
147 | &backoff->t_holddown); | |
d62a17ae | 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: | |
332beb64 | 153 | event_cancel(&backoff->t_holddown); |
907a2395 DS |
154 | event_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed, |
155 | backoff, backoff->holddown, | |
156 | &backoff->t_holddown); | |
d62a17ae | 157 | if (backoff->state == SPF_BACKOFF_SHORT_WAIT) |
158 | rv = backoff->short_delay; | |
159 | else | |
160 | rv = backoff->long_delay; | |
161 | break; | |
d62a17ae | 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; | |
c1d0d21f CF |
168 | } |
169 | ||
d62a17ae | 170 | static const char *timeval_format(struct timeval *tv) |
c1d0d21f | 171 | { |
d62a17ae | 172 | struct tm tm_store; |
173 | struct tm *tm; | |
174 | static char timebuf[256]; | |
c1d0d21f | 175 | |
d62a17ae | 176 | if (!tv->tv_sec && !tv->tv_usec) |
177 | return "(never)"; | |
c1d0d21f | 178 | |
d62a17ae | 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 | } | |
c1d0d21f | 185 | |
d62a17ae | 186 | size_t offset = strlen(timebuf); |
187 | snprintf(timebuf + offset, sizeof(timebuf) - offset, ".%ld", | |
a37bd5e0 | 188 | (long int)tv->tv_usec); |
c1d0d21f | 189 | |
d62a17ae | 190 | return timebuf; |
c1d0d21f CF |
191 | } |
192 | ||
d62a17ae | 193 | void spf_backoff_show(struct spf_backoff *backoff, struct vty *vty, |
194 | const char *prefix) | |
c1d0d21f | 195 | { |
d62a17ae | 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) { | |
4f830a07 | 207 | struct timeval remain = event_timer_remain(backoff->t_holddown); |
02e701e4 | 208 | |
a97986ff | 209 | vty_out(vty, "%s Still runs for %lld msec\n", |
996c9314 LB |
210 | prefix, |
211 | (long long)remain.tv_sec * 1000 | |
a97986ff | 212 | + remain.tv_usec / 1000); |
d62a17ae | 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 = | |
4f830a07 | 221 | event_timer_remain(backoff->t_timetolearn); |
a97986ff | 222 | vty_out(vty, "%s Still runs for %lld msec\n", |
996c9314 LB |
223 | prefix, |
224 | (long long)remain.tv_sec * 1000 | |
a97986ff | 225 | + remain.tv_usec / 1000); |
d62a17ae | 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)); | |
c1d0d21f CF |
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 | { | |
d62a17ae | 242 | debug_spf_backoff = true; |
243 | return CMD_SUCCESS; | |
c1d0d21f CF |
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 | { | |
d62a17ae | 253 | debug_spf_backoff = false; |
254 | return CMD_SUCCESS; | |
c1d0d21f CF |
255 | } |
256 | ||
d62a17ae | 257 | int spf_backoff_write_config(struct vty *vty) |
c1d0d21f | 258 | { |
d62a17ae | 259 | int written = 0; |
c1d0d21f | 260 | |
d62a17ae | 261 | if (debug_spf_backoff) { |
262 | vty_out(vty, "debug spf-delay-ietf\n"); | |
263 | written++; | |
264 | } | |
c1d0d21f | 265 | |
d62a17ae | 266 | return written; |
c1d0d21f CF |
267 | } |
268 | ||
d62a17ae | 269 | void spf_backoff_cmd_init(void) |
c1d0d21f | 270 | { |
d62a17ae | 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); | |
c1d0d21f CF |
275 | } |
276 | ||
d62a17ae | 277 | long spf_backoff_init_delay(struct spf_backoff *backoff) |
c1d0d21f | 278 | { |
d62a17ae | 279 | return backoff->init_delay; |
c1d0d21f CF |
280 | } |
281 | ||
d62a17ae | 282 | long spf_backoff_short_delay(struct spf_backoff *backoff) |
c1d0d21f | 283 | { |
d62a17ae | 284 | return backoff->short_delay; |
c1d0d21f CF |
285 | } |
286 | ||
d62a17ae | 287 | long spf_backoff_long_delay(struct spf_backoff *backoff) |
c1d0d21f | 288 | { |
d62a17ae | 289 | return backoff->long_delay; |
c1d0d21f CF |
290 | } |
291 | ||
d62a17ae | 292 | long spf_backoff_holddown(struct spf_backoff *backoff) |
c1d0d21f | 293 | { |
d62a17ae | 294 | return backoff->holddown; |
c1d0d21f CF |
295 | } |
296 | ||
d62a17ae | 297 | long spf_backoff_timetolearn(struct spf_backoff *backoff) |
c1d0d21f | 298 | { |
d62a17ae | 299 | return backoff->timetolearn; |
c1d0d21f | 300 | } |