]>
Commit | Line | Data |
---|---|---|
937e75d8 OZ |
1 | /* |
2 | * BIRD -- The Babel protocol | |
3 | * | |
4 | * Copyright (c) 2015--2016 Toke Hoiland-Jorgensen | |
5 | * | |
6 | * Can be freely distributed and used under the terms of the GNU GPL. | |
7 | * | |
8 | * This file contains the main routines for handling and sending TLVs, as | |
9 | * well as timers and interaction with the nest. | |
10 | */ | |
11 | ||
12 | /** | |
13 | * DOC: The Babel protocol | |
14 | * | |
15 | * Babel (RFC6126) is a loop-avoiding distance-vector routing protocol that is | |
16 | * robust and efficient both in ordinary wired networks and in wireless mesh | |
17 | * networks. | |
18 | * | |
19 | * The Babel protocol keeps state for each neighbour in a &babel_neighbor | |
20 | * struct, tracking received Hello and I Heard You (IHU) messages. A | |
21 | * &babel_interface struct keeps hello and update times for each interface, and | |
22 | * a separate hello seqno is maintained for each interface. | |
23 | * | |
24 | * For each prefix, Babel keeps track of both the possible routes (with next hop | |
25 | * and router IDs), as well as the feasibility distance for each prefix and | |
26 | * router id. The prefix itself is tracked in a &babel_entry struct, while the | |
27 | * possible routes for the prefix are tracked as &babel_route entries and the | |
28 | * feasibility distance is maintained through &babel_source structures. | |
29 | * | |
30 | * The main route selection is done in babel_select_route(). This is called when | |
31 | * an entry is updated by receiving updates from the network or when modified by | |
32 | * internal timers. It performs feasibility checks on the available routes for | |
33 | * the prefix and selects the one with the lowest metric to be announced to the | |
34 | * core. | |
35 | */ | |
36 | ||
37 | #include <stdlib.h> | |
38 | #include "babel.h" | |
39 | ||
40 | ||
41 | #define OUR_ROUTE(r) (r->neigh == NULL) | |
42 | ||
43 | /* | |
44 | * Is one number greater or equal than another mod 2^16? This is based on the | |
45 | * definition of serial number space in RFC 1982. Note that arguments are of | |
46 | * uint type to avoid integer promotion to signed integer. | |
47 | */ | |
48 | static inline int ge_mod64k(uint a, uint b) | |
49 | { return (u16)(a - b) < 0x8000; } | |
50 | ||
51 | static void babel_dump_entry(struct babel_entry *e); | |
52 | static void babel_dump_route(struct babel_route *r); | |
53 | static void babel_select_route(struct babel_entry *e); | |
54 | static void babel_send_route_request(struct babel_entry *e, struct babel_neighbor *n); | |
55 | static void babel_send_wildcard_request(struct babel_iface *ifa); | |
56 | static int babel_cache_seqno_request(struct babel_proto *p, ip_addr prefix, u8 plen, | |
57 | u64 router_id, u16 seqno); | |
58 | static void babel_trigger_iface_update(struct babel_iface *ifa); | |
59 | static void babel_trigger_update(struct babel_proto *p); | |
60 | static void babel_send_seqno_request(struct babel_entry *e); | |
61 | static inline void babel_kick_timer(struct babel_proto *p); | |
62 | static inline void babel_iface_kick_timer(struct babel_iface *ifa); | |
63 | ||
64 | ||
65 | /* | |
66 | * Functions to maintain data structures | |
67 | */ | |
68 | ||
69 | static void | |
70 | babel_init_entry(struct fib_node *n) | |
71 | { | |
72 | struct babel_entry *e = (void *) n; | |
73 | e->proto = NULL; | |
74 | e->selected_in = NULL; | |
75 | e->selected_out = NULL; | |
76 | e->updated = now; | |
77 | init_list(&e->sources); | |
78 | init_list(&e->routes); | |
79 | } | |
80 | ||
81 | static inline struct babel_entry * | |
82 | babel_find_entry(struct babel_proto *p, ip_addr prefix, u8 plen) | |
83 | { | |
84 | return fib_find(&p->rtable, &prefix, plen); | |
85 | } | |
86 | ||
87 | static struct babel_entry * | |
88 | babel_get_entry(struct babel_proto *p, ip_addr prefix, u8 plen) | |
89 | { | |
90 | struct babel_entry *e = fib_get(&p->rtable, &prefix, plen); | |
91 | e->proto = p; | |
92 | return e; | |
93 | } | |
94 | ||
95 | static struct babel_source * | |
96 | babel_find_source(struct babel_entry *e, u64 router_id) | |
97 | { | |
98 | struct babel_source *s; | |
99 | ||
100 | WALK_LIST(s, e->sources) | |
101 | if (s->router_id == router_id) | |
102 | return s; | |
103 | ||
104 | return NULL; | |
105 | } | |
106 | ||
107 | static struct babel_source * | |
108 | babel_get_source(struct babel_entry *e, u64 router_id) | |
109 | { | |
110 | struct babel_proto *p = e->proto; | |
111 | struct babel_source *s = babel_find_source(e, router_id); | |
112 | ||
113 | if (s) | |
114 | return s; | |
115 | ||
116 | s = sl_alloc(p->source_slab); | |
117 | s->router_id = router_id; | |
118 | s->expires = now + BABEL_GARBAGE_INTERVAL; | |
119 | s->seqno = 0; | |
120 | s->metric = BABEL_INFINITY; | |
121 | add_tail(&e->sources, NODE s); | |
122 | ||
123 | return s; | |
124 | } | |
125 | ||
126 | static void | |
127 | babel_expire_sources(struct babel_entry *e) | |
128 | { | |
129 | struct babel_proto *p = e->proto; | |
130 | struct babel_source *n, *nx; | |
131 | ||
132 | WALK_LIST_DELSAFE(n, nx, e->sources) | |
133 | { | |
134 | if (n->expires && n->expires <= now) | |
135 | { | |
136 | rem_node(NODE n); | |
137 | sl_free(p->source_slab, n); | |
138 | } | |
139 | } | |
140 | } | |
141 | ||
142 | static struct babel_route * | |
143 | babel_find_route(struct babel_entry *e, struct babel_neighbor *n) | |
144 | { | |
145 | struct babel_route *r; | |
146 | ||
147 | WALK_LIST(r, e->routes) | |
148 | if (r->neigh == n) | |
149 | return r; | |
150 | ||
151 | return NULL; | |
152 | } | |
153 | ||
154 | static struct babel_route * | |
155 | babel_get_route(struct babel_entry *e, struct babel_neighbor *nbr) | |
156 | { | |
157 | struct babel_proto *p = e->proto; | |
158 | struct babel_route *r = babel_find_route(e, nbr); | |
159 | ||
160 | if (r) | |
161 | return r; | |
162 | ||
163 | r = sl_alloc(p->route_slab); | |
164 | memset(r, 0, sizeof(*r)); | |
165 | r->e = e; | |
166 | add_tail(&e->routes, NODE r); | |
167 | ||
168 | if (nbr) | |
169 | { | |
170 | r->neigh = nbr; | |
171 | r->expires = now + BABEL_GARBAGE_INTERVAL; | |
172 | add_tail(&nbr->routes, NODE &r->neigh_route); | |
173 | } | |
174 | ||
175 | return r; | |
176 | } | |
177 | ||
178 | static void | |
179 | babel_flush_route(struct babel_route *r) | |
180 | { | |
181 | struct babel_proto *p = r->e->proto; | |
182 | ||
183 | DBG("Babel: Flush route %I/%d router_id %lR neigh %I\n", | |
184 | r->e->n.prefix, r->e->n.pxlen, r->router_id, r->neigh ? r->neigh->addr : IPA_NONE); | |
185 | ||
186 | rem_node(NODE r); | |
187 | ||
188 | if (r->neigh) | |
189 | rem_node(&r->neigh_route); | |
190 | ||
191 | if (r->e->selected_in == r) | |
192 | r->e->selected_in = NULL; | |
193 | ||
194 | if (r->e->selected_out == r) | |
195 | r->e->selected_out = NULL; | |
196 | ||
197 | sl_free(p->route_slab, r); | |
198 | } | |
199 | ||
200 | static void | |
201 | babel_expire_route(struct babel_route *r) | |
202 | { | |
203 | struct babel_proto *p = r->e->proto; | |
204 | struct babel_entry *e = r->e; | |
205 | ||
206 | TRACE(D_EVENTS, "Route expiry timer for %I/%d router-id %lR fired", | |
207 | e->n.prefix, e->n.pxlen, r->router_id); | |
208 | ||
209 | if (r->metric < BABEL_INFINITY) | |
210 | { | |
211 | r->metric = BABEL_INFINITY; | |
212 | r->expires = now + r->expiry_interval; | |
213 | } | |
214 | else | |
215 | { | |
216 | babel_flush_route(r); | |
217 | } | |
218 | } | |
219 | ||
220 | static void | |
221 | babel_refresh_route(struct babel_route *r) | |
222 | { | |
223 | if (!OUR_ROUTE(r) && (r == r->e->selected_in)) | |
224 | babel_send_route_request(r->e, r->neigh); | |
225 | ||
226 | r->refresh_time = 0; | |
227 | } | |
228 | ||
229 | static void | |
230 | babel_expire_routes(struct babel_proto *p) | |
231 | { | |
232 | struct babel_entry *e; | |
233 | struct babel_route *r, *rx; | |
234 | struct fib_iterator fit; | |
235 | ||
236 | FIB_ITERATE_INIT(&fit, &p->rtable); | |
237 | ||
238 | loop: | |
239 | FIB_ITERATE_START(&p->rtable, &fit, n) | |
240 | { | |
241 | e = (struct babel_entry *) n; | |
242 | int changed = 0; | |
243 | ||
244 | WALK_LIST_DELSAFE(r, rx, e->routes) | |
245 | { | |
246 | if (r->refresh_time && r->refresh_time <= now) | |
247 | babel_refresh_route(r); | |
248 | ||
249 | if (r->expires && r->expires <= now) | |
250 | { | |
251 | babel_expire_route(r); | |
252 | changed = 1; | |
253 | } | |
254 | } | |
255 | ||
256 | if (changed) | |
257 | { | |
258 | /* | |
259 | * We have to restart the iteration because there may be a cascade of | |
260 | * synchronous events babel_select_route() -> nest table change -> | |
261 | * babel_rt_notify() -> p->rtable change, invalidating hidden variables. | |
262 | */ | |
263 | ||
264 | FIB_ITERATE_PUT(&fit, n); | |
265 | babel_select_route(e); | |
266 | goto loop; | |
267 | } | |
268 | ||
269 | babel_expire_sources(e); | |
270 | ||
271 | /* Remove empty entries */ | |
272 | if (EMPTY_LIST(e->sources) && EMPTY_LIST(e->routes)) | |
273 | { | |
274 | FIB_ITERATE_PUT(&fit, n); | |
275 | fib_delete(&p->rtable, e); | |
276 | goto loop; | |
277 | } | |
278 | } | |
279 | FIB_ITERATE_END(n); | |
280 | } | |
281 | ||
282 | static struct babel_neighbor * | |
283 | babel_find_neighbor(struct babel_iface *ifa, ip_addr addr) | |
284 | { | |
285 | struct babel_neighbor *nbr; | |
286 | ||
287 | WALK_LIST(nbr, ifa->neigh_list) | |
288 | if (ipa_equal(nbr->addr, addr)) | |
289 | return nbr; | |
290 | ||
291 | return NULL; | |
292 | } | |
293 | ||
294 | static struct babel_neighbor * | |
295 | babel_get_neighbor(struct babel_iface *ifa, ip_addr addr) | |
296 | { | |
297 | struct babel_neighbor *nbr = babel_find_neighbor(ifa, addr); | |
298 | ||
299 | if (nbr) | |
300 | return nbr; | |
301 | ||
302 | nbr = mb_allocz(ifa->pool, sizeof(struct babel_neighbor)); | |
303 | nbr->ifa = ifa; | |
304 | nbr->addr = addr; | |
305 | nbr->txcost = BABEL_INFINITY; | |
306 | init_list(&nbr->routes); | |
307 | add_tail(&ifa->neigh_list, NODE nbr); | |
308 | ||
309 | return nbr; | |
310 | } | |
311 | ||
312 | static void | |
313 | babel_flush_neighbor(struct babel_neighbor *nbr) | |
314 | { | |
315 | struct babel_proto *p = nbr->ifa->proto; | |
316 | node *n; | |
317 | ||
318 | TRACE(D_EVENTS, "Flushing neighbor %I", nbr->addr); | |
319 | ||
320 | WALK_LIST_FIRST(n, nbr->routes) | |
321 | { | |
322 | struct babel_route *r = SKIP_BACK(struct babel_route, neigh_route, n); | |
323 | struct babel_entry *e = r->e; | |
324 | int selected = (r == e->selected_in); | |
325 | ||
326 | babel_flush_route(r); | |
327 | ||
328 | if (selected) | |
329 | babel_select_route(e); | |
330 | } | |
331 | ||
332 | rem_node(NODE nbr); | |
333 | mb_free(nbr); | |
334 | } | |
335 | ||
336 | static void | |
337 | babel_expire_ihu(struct babel_neighbor *nbr) | |
338 | { | |
339 | nbr->txcost = BABEL_INFINITY; | |
340 | } | |
341 | ||
342 | static void | |
343 | babel_expire_hello(struct babel_neighbor *nbr) | |
344 | { | |
345 | nbr->hello_map <<= 1; | |
346 | ||
347 | if (nbr->hello_cnt < 16) | |
348 | nbr->hello_cnt++; | |
349 | ||
350 | if (!nbr->hello_map) | |
351 | babel_flush_neighbor(nbr); | |
352 | } | |
353 | ||
354 | static void | |
355 | babel_expire_neighbors(struct babel_proto *p) | |
356 | { | |
357 | struct babel_iface *ifa; | |
358 | struct babel_neighbor *nbr, *nbx; | |
359 | ||
360 | WALK_LIST(ifa, p->interfaces) | |
361 | { | |
362 | WALK_LIST_DELSAFE(nbr, nbx, ifa->neigh_list) | |
363 | { | |
364 | if (nbr->ihu_expiry && nbr->ihu_expiry <= now) | |
365 | babel_expire_ihu(nbr); | |
366 | ||
367 | if (nbr->hello_expiry && nbr->hello_expiry <= now) | |
368 | babel_expire_hello(nbr); | |
369 | } | |
370 | } | |
371 | } | |
372 | ||
373 | ||
374 | /* | |
375 | * Best route selection | |
376 | */ | |
377 | ||
378 | /* | |
379 | * From the RFC (section 3.5.1): | |
380 | * | |
381 | * a route advertisement carrying the quintuple (prefix, plen, router-id, seqno, | |
382 | * metric) is feasible if one of the following conditions holds: | |
383 | * | |
384 | * - metric is infinite; or | |
385 | * | |
386 | * - no entry exists in the source table indexed by (id, prefix, plen); or | |
387 | * | |
388 | * - an entry (prefix, plen, router-id, seqno', metric') exists in the source | |
389 | * table, and either | |
390 | * - seqno' < seqno or | |
391 | * - seqno = seqno' and metric < metric'. | |
392 | */ | |
393 | static inline int | |
394 | babel_is_feasible(struct babel_source *s, u16 seqno, u16 metric) | |
395 | { | |
396 | return !s || | |
397 | (metric == BABEL_INFINITY) || | |
398 | (seqno > s->seqno) || | |
399 | ((seqno == s->seqno) && (metric < s->metric)); | |
400 | } | |
401 | ||
402 | static u16 | |
403 | babel_compute_rxcost(struct babel_neighbor *n) | |
404 | { | |
405 | struct babel_iface *ifa = n->ifa; | |
406 | u8 cnt, missed; | |
407 | u16 map=n->hello_map; | |
408 | ||
409 | if (!map) return BABEL_INFINITY; | |
410 | cnt = u32_popcount(map); // number of bits set | |
411 | missed = n->hello_cnt-cnt; | |
412 | ||
413 | if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS) | |
414 | { | |
415 | /* ETX - Appendix 2.2 in the RFC. | |
416 | ||
417 | beta = prob. of successful transmission. | |
418 | rxcost = BABEL_RXCOST_WIRELESS/beta | |
419 | ||
420 | Since: beta = 1-missed/n->hello_cnt = cnt/n->hello_cnt | |
421 | Then: rxcost = BABEL_RXCOST_WIRELESS * n->hello_cnt / cnt | |
422 | */ | |
423 | if (!cnt) return BABEL_INFINITY; | |
424 | return BABEL_RXCOST_WIRELESS * n->hello_cnt / cnt; | |
425 | } | |
426 | else | |
427 | { | |
428 | /* k-out-of-j selection - Appendix 2.1 in the RFC. */ | |
429 | DBG("Babel: Missed %d hellos from %I\n", missed, n->addr); | |
430 | /* Link is bad if more than half the expected hellos were lost */ | |
431 | return (missed > n->hello_cnt/2) ? BABEL_INFINITY : ifa->cf->rxcost; | |
432 | } | |
433 | } | |
434 | ||
435 | ||
436 | static u16 | |
437 | babel_compute_cost(struct babel_neighbor *n) | |
438 | { | |
439 | struct babel_iface *ifa = n->ifa; | |
440 | u16 rxcost = babel_compute_rxcost(n); | |
441 | if (rxcost == BABEL_INFINITY) return rxcost; | |
442 | else if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS) | |
443 | { | |
444 | /* ETX - Appendix 2.2 in the RFC */ | |
445 | return (MAX(n->txcost, BABEL_RXCOST_WIRELESS) * rxcost)/BABEL_RXCOST_WIRELESS; | |
446 | } | |
447 | else | |
448 | { | |
449 | /* k-out-of-j selection - Appendix 2.1 in the RFC. */ | |
450 | return n->txcost; | |
451 | } | |
452 | } | |
453 | ||
454 | /* Simple additive metric - Appendix 3.1 in the RFC */ | |
455 | static u16 | |
456 | babel_compute_metric(struct babel_neighbor *n, uint metric) | |
457 | { | |
458 | metric += babel_compute_cost(n); | |
459 | return MIN(metric, BABEL_INFINITY); | |
460 | } | |
461 | ||
462 | ||
463 | /** | |
464 | * babel_announce_rte - announce selected route to the core | |
465 | * @p: Babel protocol instance | |
466 | * @e: Babel route entry to announce | |
467 | * | |
468 | * This function announces a Babel entry to the core if it has a selected | |
469 | * incoming path, and retracts it otherwise. If the selected entry has infinite | |
470 | * metric, the route is announced as unreachable. | |
471 | */ | |
472 | static void | |
473 | babel_announce_rte(struct babel_proto *p, struct babel_entry *e) | |
474 | { | |
475 | struct babel_route *r = e->selected_in; | |
476 | ||
477 | if (r) | |
478 | { | |
479 | net *n = net_get(p->p.table, e->n.prefix, e->n.pxlen); | |
480 | rta A = { | |
481 | .src = p->p.main_source, | |
482 | .source = RTS_BABEL, | |
483 | .scope = SCOPE_UNIVERSE, | |
484 | .cast = RTC_UNICAST, | |
485 | .dest = r->metric == BABEL_INFINITY ? RTD_UNREACHABLE : RTD_ROUTER, | |
486 | .flags = 0, | |
487 | .from = r->neigh->addr, | |
488 | .iface = r->neigh->ifa->iface, | |
489 | }; | |
490 | ||
491 | if (r->metric < BABEL_INFINITY) | |
492 | A.gw = r->next_hop; | |
493 | ||
494 | rta *a = rta_lookup(&A); | |
495 | rte *rte = rte_get_temp(a); | |
496 | rte->u.babel.metric = r->metric; | |
497 | rte->u.babel.router_id = r->router_id; | |
498 | rte->net = n; | |
499 | rte->pflags = 0; | |
500 | ||
501 | rte_update(&p->p, n, rte); | |
502 | } | |
503 | else | |
504 | { | |
505 | /* Retraction */ | |
506 | net *n = net_find(p->p.table, e->n.prefix, e->n.pxlen); | |
507 | rte_update(&p->p, n, NULL); | |
508 | } | |
509 | } | |
510 | ||
511 | /** | |
512 | * babel_select_route - select best route for given route entry | |
513 | * @e: Babel entry to select the best route for | |
514 | * | |
515 | * Select the best feasible route for a given prefix among the routes received | |
516 | * from peers, and propagate it to the nest. This just selects the feasible | |
517 | * route with the lowest metric. | |
518 | * | |
519 | * If no feasible route is available for a prefix that previously had a route | |
520 | * selected, a seqno request is sent to try to get a valid route. In the | |
521 | * meantime, the route is marked as infeasible in the nest (to blackhole packets | |
522 | * going to it, as per the RFC). | |
523 | * | |
524 | * If no feasible route is available, and no previous route is selected, the | |
525 | * route is removed from the nest entirely. | |
526 | */ | |
527 | static void | |
528 | babel_select_route(struct babel_entry *e) | |
529 | { | |
530 | struct babel_proto *p = e->proto; | |
531 | struct babel_route *r, *cur = e->selected_in; | |
532 | ||
533 | /* try to find the best feasible route */ | |
534 | WALK_LIST(r, e->routes) | |
535 | if (!OUR_ROUTE(r) && /* prevent propagating our own routes back to core */ | |
536 | (!cur || r->metric < cur->metric) && | |
537 | babel_is_feasible(babel_find_source(e, r->router_id), r->seqno, r->advert_metric)) | |
538 | cur = r; | |
539 | ||
540 | if (cur && !OUR_ROUTE(cur) && | |
541 | ((!e->selected_in && cur->metric < BABEL_INFINITY) || | |
542 | (e->selected_in && cur->metric < e->selected_in->metric))) | |
543 | { | |
544 | TRACE(D_EVENTS, "Picked new route for prefix %I/%d: router id %lR metric %d", | |
545 | e->n.prefix, e->n.pxlen, cur->router_id, cur->metric); | |
546 | ||
547 | e->selected_in = cur; | |
548 | e->updated = now; | |
549 | babel_announce_rte(p, e); | |
550 | } | |
551 | else if (!cur || cur->metric == BABEL_INFINITY) | |
552 | { | |
553 | /* Couldn't find a feasible route. If we have a selected route, that means | |
554 | it just became infeasible; so set it's metric to infinite and install it | |
555 | (as unreachable), then send a seqno request. | |
556 | ||
557 | babel_build_rte() will set the unreachable flag if the metric is BABEL_INFINITY.*/ | |
558 | if (e->selected_in) | |
559 | { | |
560 | TRACE(D_EVENTS, "Lost feasible route for prefix %I/%d", | |
561 | e->n.prefix, e->n.pxlen); | |
562 | ||
563 | e->selected_in->metric = BABEL_INFINITY; | |
564 | e->updated = now; | |
565 | ||
566 | babel_send_seqno_request(e); | |
567 | babel_announce_rte(p, e); | |
568 | } | |
569 | else | |
570 | { | |
571 | /* No route currently selected, and no new one selected; this means we | |
572 | don't have a route to this destination anymore (and were probably | |
573 | called from an expiry timer). Remove the route from the nest. */ | |
574 | TRACE(D_EVENTS, "Flushing route for prefix %I/%d", e->n.prefix, e->n.pxlen); | |
575 | ||
576 | e->selected_in = NULL; | |
577 | e->updated = now; | |
578 | babel_announce_rte(p, e); | |
579 | } | |
580 | } | |
581 | } | |
582 | ||
583 | /* | |
584 | * Functions to send replies | |
585 | */ | |
586 | ||
587 | static void | |
588 | babel_send_ack(struct babel_iface *ifa, ip_addr dest, u16 nonce) | |
589 | { | |
590 | struct babel_proto *p = ifa->proto; | |
591 | union babel_msg msg = {}; | |
592 | ||
593 | TRACE(D_PACKETS, "Sending ACK to %I with nonce %d", dest, nonce); | |
594 | ||
595 | msg.type = BABEL_TLV_ACK; | |
596 | msg.ack.nonce = nonce; | |
597 | ||
598 | babel_send_unicast(&msg, ifa, dest); | |
599 | } | |
600 | ||
601 | static void | |
602 | babel_build_ihu(union babel_msg *msg, struct babel_iface *ifa, struct babel_neighbor *n) | |
603 | { | |
604 | struct babel_proto *p = ifa->proto; | |
605 | ||
606 | msg->type = BABEL_TLV_IHU; | |
607 | msg->ihu.addr = n->addr; | |
608 | msg->ihu.rxcost = babel_compute_rxcost(n); | |
609 | msg->ihu.interval = ifa->cf->ihu_interval; | |
610 | ||
611 | TRACE(D_PACKETS, "Sending IHU for %I with rxcost %d interval %d", | |
612 | msg->ihu.addr, msg->ihu.rxcost, msg->ihu.interval); | |
613 | } | |
614 | ||
615 | static void | |
616 | babel_send_ihu(struct babel_iface *ifa, struct babel_neighbor *n) | |
617 | { | |
618 | union babel_msg msg = {}; | |
619 | babel_build_ihu(&msg, ifa, n); | |
620 | babel_send_unicast(&msg, ifa, n->addr); | |
621 | } | |
622 | ||
623 | static void | |
624 | babel_send_ihus(struct babel_iface *ifa) | |
625 | { | |
626 | struct babel_neighbor *n; | |
627 | WALK_LIST(n, ifa->neigh_list) | |
628 | { | |
629 | union babel_msg msg = {}; | |
630 | babel_build_ihu(&msg, ifa, n); | |
631 | babel_enqueue(&msg, ifa); | |
632 | } | |
633 | } | |
634 | ||
635 | static void | |
636 | babel_send_hello(struct babel_iface *ifa, u8 send_ihu) | |
637 | { | |
638 | struct babel_proto *p = ifa->proto; | |
639 | union babel_msg msg = {}; | |
640 | ||
641 | msg.type = BABEL_TLV_HELLO; | |
642 | msg.hello.seqno = ifa->hello_seqno++; | |
643 | msg.hello.interval = ifa->cf->hello_interval; | |
644 | ||
645 | TRACE(D_PACKETS, "Sending hello on %s with seqno %d interval %d", | |
646 | ifa->ifname, msg.hello.seqno, msg.hello.interval); | |
647 | ||
648 | babel_enqueue(&msg, ifa); | |
649 | ||
650 | if (send_ihu) | |
651 | babel_send_ihus(ifa); | |
652 | } | |
653 | ||
654 | static void | |
655 | babel_send_route_request(struct babel_entry *e, struct babel_neighbor *n) | |
656 | { | |
657 | struct babel_proto *p = e->proto; | |
658 | struct babel_iface *ifa = n->ifa; | |
659 | union babel_msg msg = {}; | |
660 | ||
661 | TRACE(D_PACKETS, "Sending route request for %I/%d to %I", | |
662 | e->n.prefix, e->n.pxlen, n->addr); | |
663 | ||
664 | msg.type = BABEL_TLV_ROUTE_REQUEST; | |
665 | msg.route_request.prefix = e->n.prefix; | |
666 | msg.route_request.plen = e->n.pxlen; | |
667 | ||
668 | babel_send_unicast(&msg, ifa, n->addr); | |
669 | } | |
670 | ||
671 | static void | |
672 | babel_send_wildcard_request(struct babel_iface *ifa) | |
673 | { | |
674 | struct babel_proto *p = ifa->proto; | |
675 | union babel_msg msg = {}; | |
676 | ||
677 | TRACE(D_PACKETS, "Sending wildcard route request on %s", | |
678 | ifa->ifname); | |
679 | ||
680 | msg.type = BABEL_TLV_ROUTE_REQUEST; | |
681 | msg.route_request.full = 1; | |
682 | ||
683 | babel_enqueue(&msg, ifa); | |
684 | } | |
685 | ||
686 | static void | |
687 | babel_send_seqno_request(struct babel_entry *e) | |
688 | { | |
689 | struct babel_proto *p = e->proto; | |
690 | struct babel_route *r = e->selected_in; | |
691 | struct babel_iface *ifa = NULL; | |
692 | struct babel_source *s = NULL; | |
693 | union babel_msg msg = {}; | |
694 | ||
695 | s = babel_find_source(e, r->router_id); | |
696 | if (!s || !babel_cache_seqno_request(p, e->n.prefix, e->n.pxlen, r->router_id, s->seqno + 1)) | |
697 | return; | |
698 | ||
699 | TRACE(D_PACKETS, "Sending seqno request for %I/%d router-id %lR seqno %d", | |
700 | e->n.prefix, e->n.pxlen, r->router_id, s->seqno + 1); | |
701 | ||
702 | msg.type = BABEL_TLV_SEQNO_REQUEST; | |
703 | msg.seqno_request.plen = e->n.pxlen; | |
704 | msg.seqno_request.seqno = s->seqno + 1; | |
705 | msg.seqno_request.hop_count = BABEL_INITIAL_HOP_COUNT; | |
706 | msg.seqno_request.router_id = r->router_id; | |
707 | msg.seqno_request.prefix = e->n.prefix; | |
708 | ||
709 | WALK_LIST(ifa, p->interfaces) | |
710 | babel_enqueue(&msg, ifa); | |
711 | } | |
712 | ||
713 | static void | |
714 | babel_unicast_seqno_request(struct babel_route *r) | |
715 | { | |
716 | struct babel_entry *e = r->e; | |
717 | struct babel_proto *p = e->proto; | |
718 | struct babel_iface *ifa = r->neigh->ifa; | |
719 | struct babel_source *s = NULL; | |
720 | union babel_msg msg = {}; | |
721 | ||
722 | s = babel_find_source(e, r->router_id); | |
723 | if (!s || !babel_cache_seqno_request(p, e->n.prefix, e->n.pxlen, r->router_id, s->seqno + 1)) | |
724 | return; | |
725 | ||
726 | TRACE(D_PACKETS, "Sending seqno request for %I/%d router-id %lR seqno %d", | |
727 | e->n.prefix, e->n.pxlen, r->router_id, s->seqno + 1); | |
728 | ||
729 | msg.type = BABEL_TLV_SEQNO_REQUEST; | |
730 | msg.seqno_request.plen = e->n.pxlen; | |
731 | msg.seqno_request.seqno = s->seqno + 1; | |
732 | msg.seqno_request.hop_count = BABEL_INITIAL_HOP_COUNT; | |
733 | msg.seqno_request.router_id = r->router_id; | |
734 | msg.seqno_request.prefix = e->n.prefix; | |
735 | ||
736 | babel_send_unicast(&msg, ifa, r->neigh->addr); | |
737 | } | |
738 | ||
739 | /** | |
740 | * babel_send_update - send route table updates | |
741 | * @ifa: Interface to transmit on | |
742 | * @changed: Only send entries changed since this time | |
743 | * | |
744 | * This function produces update TLVs for all entries changed since the time | |
745 | * indicated by the &changed parameter and queues them for transmission on the | |
746 | * selected interface. During the process, the feasibility distance for each | |
747 | * transmitted entry is updated. | |
748 | */ | |
749 | static void | |
750 | babel_send_update(struct babel_iface *ifa, bird_clock_t changed) | |
751 | { | |
752 | struct babel_proto *p = ifa->proto; | |
753 | ||
754 | FIB_WALK(&p->rtable, n) | |
755 | { | |
756 | struct babel_entry *e = (void *) n; | |
757 | struct babel_route *r = e->selected_out; | |
758 | ||
759 | if (!r) | |
760 | continue; | |
761 | ||
762 | /* Our own seqno might have changed, in which case we update the routes we | |
763 | originate. */ | |
764 | if ((r->router_id == p->router_id) && (r->seqno < p->update_seqno)) | |
765 | { | |
766 | r->seqno = p->update_seqno; | |
767 | e->updated = now; | |
768 | } | |
769 | ||
770 | /* Skip routes that weren't updated since 'changed' time */ | |
771 | if (e->updated < changed) | |
772 | continue; | |
773 | ||
774 | TRACE(D_PACKETS, "Sending update for %I/%d router-id %lR seqno %d metric %d", | |
775 | e->n.prefix, e->n.pxlen, r->router_id, r->seqno, r->metric); | |
776 | ||
777 | union babel_msg msg = {}; | |
778 | msg.type = BABEL_TLV_UPDATE; | |
779 | msg.update.plen = e->n.pxlen; | |
780 | msg.update.interval = ifa->cf->update_interval; | |
781 | msg.update.seqno = r->seqno; | |
782 | msg.update.metric = r->metric; | |
783 | msg.update.prefix = e->n.prefix; | |
784 | msg.update.router_id = r->router_id; | |
785 | ||
786 | /* Update feasibility distance */ | |
787 | struct babel_source *s = babel_get_source(e, r->router_id); | |
788 | s->expires = now + BABEL_GARBAGE_INTERVAL; | |
789 | if ((msg.update.seqno > s->seqno) || | |
790 | ((msg.update.seqno == s->seqno) && (msg.update.metric < s->metric))) | |
791 | { | |
792 | s->seqno = msg.update.seqno; | |
793 | s->metric = msg.update.metric; | |
794 | } | |
795 | babel_enqueue(&msg, ifa); | |
796 | } | |
797 | FIB_WALK_END; | |
798 | } | |
799 | ||
800 | static void | |
801 | babel_trigger_iface_update(struct babel_iface *ifa) | |
802 | { | |
803 | struct babel_proto *p = ifa->proto; | |
804 | ||
805 | /* Interface not active or already scheduled */ | |
806 | if (!ifa->up || ifa->want_triggered) | |
807 | return; | |
808 | ||
809 | TRACE(D_EVENTS, "Scheduling triggered updates for %s seqno %d", | |
810 | ifa->iface->name, p->update_seqno); | |
811 | ||
812 | ifa->want_triggered = now; | |
813 | babel_iface_kick_timer(ifa); | |
814 | } | |
815 | ||
816 | /* Sends and update on all interfaces. */ | |
817 | static void | |
818 | babel_trigger_update(struct babel_proto *p) | |
819 | { | |
820 | if (p->triggered) | |
821 | return; | |
822 | ||
823 | struct babel_iface *ifa; | |
824 | WALK_LIST(ifa, p->interfaces) | |
825 | babel_trigger_iface_update(ifa); | |
826 | ||
827 | p->triggered = 1; | |
828 | } | |
829 | ||
830 | /* A retraction is an update with an infinite metric */ | |
831 | static void | |
832 | babel_send_retraction(struct babel_iface *ifa, ip_addr prefix, int plen) | |
833 | { | |
834 | struct babel_proto *p = ifa->proto; | |
835 | union babel_msg msg = {}; | |
836 | ||
837 | TRACE(D_PACKETS, "Sending retraction for %I/%d router-id %lR seqno %d", | |
838 | prefix, plen, p->router_id, p->update_seqno); | |
839 | ||
840 | msg.type = BABEL_TLV_UPDATE; | |
841 | msg.update.plen = plen; | |
842 | msg.update.interval = ifa->cf->update_interval; | |
843 | msg.update.seqno = p->update_seqno; | |
844 | msg.update.metric = BABEL_INFINITY; | |
845 | msg.update.prefix = prefix; | |
846 | msg.update.router_id = p->router_id; | |
847 | ||
848 | babel_enqueue(&msg, ifa); | |
849 | } | |
850 | ||
851 | ||
852 | /* | |
853 | * TLV handler helpers | |
854 | */ | |
855 | ||
856 | /* Update hello history according to Appendix A1 of the RFC */ | |
857 | static void | |
858 | babel_update_hello_history(struct babel_neighbor *n, u16 seqno, u16 interval) | |
859 | { | |
860 | /* | |
861 | * Compute the difference between expected and received seqno (modulo 2^16). | |
862 | * If the expected and received seqnos are within 16 of each other, the modular | |
863 | * difference is going to be less than 16 for one of the directions. Otherwise, | |
864 | * the values differ too much, so just reset the state. | |
865 | */ | |
866 | ||
867 | u16 delta = ((uint) seqno - (uint) n->next_hello_seqno); | |
868 | ||
869 | if (delta == 0) | |
870 | { | |
871 | /* Do nothing */ | |
872 | } | |
873 | else if (delta <= 16) | |
874 | { | |
875 | /* Sending node decreased interval; fast-forward */ | |
876 | n->hello_map <<= delta; | |
877 | n->hello_cnt = MIN(n->hello_cnt + delta, 16); | |
878 | } | |
879 | else if (delta >= 0xfff0) | |
880 | { | |
881 | u8 diff = (0xffff - delta); | |
882 | /* Sending node increased interval; undo history */ | |
883 | n->hello_map >>= diff; | |
884 | n->hello_cnt = (diff < n->hello_cnt) ? n->hello_cnt - diff : 0; | |
885 | } | |
886 | else | |
887 | { | |
888 | /* Note state reset - flush entries */ | |
889 | n->hello_map = n->hello_cnt = 0; | |
890 | } | |
891 | ||
892 | /* Current entry */ | |
893 | n->hello_map = (n->hello_map << 1) | 1; | |
894 | n->next_hello_seqno = seqno+1; | |
895 | if (n->hello_cnt < 16) n->hello_cnt++; | |
896 | n->hello_expiry = now + BABEL_HELLO_EXPIRY_FACTOR(interval); | |
897 | } | |
898 | ||
899 | static void | |
900 | babel_expire_seqno_requests(struct babel_proto *p) | |
901 | { | |
902 | struct babel_seqno_request *n, *nx; | |
903 | WALK_LIST_DELSAFE(n, nx, p->seqno_cache) | |
904 | { | |
905 | if ((n->updated + BABEL_SEQNO_REQUEST_EXPIRY) <= now) | |
906 | { | |
907 | rem_node(NODE n); | |
908 | sl_free(p->seqno_slab, n); | |
909 | } | |
910 | } | |
911 | } | |
912 | ||
913 | /* | |
914 | * Checks the seqno request cache for a matching request and returns failure if | |
915 | * found. Otherwise, a new entry is stored in the cache. | |
916 | */ | |
917 | static int | |
918 | babel_cache_seqno_request(struct babel_proto *p, ip_addr prefix, u8 plen, | |
919 | u64 router_id, u16 seqno) | |
920 | { | |
921 | struct babel_seqno_request *r; | |
922 | ||
923 | WALK_LIST(r, p->seqno_cache) | |
924 | { | |
925 | if (ipa_equal(r->prefix, prefix) && (r->plen == plen) && | |
926 | (r->router_id == router_id) && (r->seqno == seqno)) | |
927 | return 0; | |
928 | } | |
929 | ||
930 | /* no entries found */ | |
931 | r = sl_alloc(p->seqno_slab); | |
932 | r->prefix = prefix; | |
933 | r->plen = plen; | |
934 | r->router_id = router_id; | |
935 | r->seqno = seqno; | |
936 | r->updated = now; | |
937 | add_tail(&p->seqno_cache, NODE r); | |
938 | ||
939 | return 1; | |
940 | } | |
941 | ||
942 | static void | |
943 | babel_forward_seqno_request(struct babel_entry *e, | |
944 | struct babel_msg_seqno_request *in, | |
945 | ip_addr sender) | |
946 | { | |
947 | struct babel_proto *p = e->proto; | |
948 | struct babel_route *r; | |
949 | ||
950 | TRACE(D_PACKETS, "Forwarding seqno request for %I/%d router-id %lR seqno %d", | |
951 | e->n.prefix, e->n.pxlen, in->router_id, in->seqno); | |
952 | ||
953 | WALK_LIST(r, e->routes) | |
954 | { | |
955 | if ((r->router_id == in->router_id) && | |
956 | !OUR_ROUTE(r) && | |
957 | !ipa_equal(r->neigh->addr, sender)) | |
958 | { | |
959 | if (!babel_cache_seqno_request(p, e->n.prefix, e->n.pxlen, in->router_id, in->seqno)) | |
960 | return; | |
961 | ||
962 | union babel_msg msg = {}; | |
963 | msg.type = BABEL_TLV_SEQNO_REQUEST; | |
964 | msg.seqno_request.plen = in->plen; | |
965 | msg.seqno_request.seqno = in->seqno; | |
966 | msg.seqno_request.hop_count = in->hop_count-1; | |
967 | msg.seqno_request.router_id = in->router_id; | |
968 | msg.seqno_request.prefix = e->n.prefix; | |
969 | ||
970 | babel_send_unicast(&msg, r->neigh->ifa, r->neigh->addr); | |
971 | return; | |
972 | } | |
973 | } | |
974 | } | |
975 | ||
976 | ||
977 | /* | |
978 | * TLV handlers | |
979 | */ | |
980 | ||
981 | void | |
982 | babel_handle_ack_req(union babel_msg *m, struct babel_iface *ifa) | |
983 | { | |
984 | struct babel_proto *p = ifa->proto; | |
985 | struct babel_msg_ack_req *msg = &m->ack_req; | |
986 | ||
987 | TRACE(D_PACKETS, "Handling ACK request nonce %d interval %d", | |
988 | msg->nonce, msg->interval); | |
989 | ||
990 | babel_send_ack(ifa, msg->sender, msg->nonce); | |
991 | } | |
992 | ||
993 | void | |
994 | babel_handle_hello(union babel_msg *m, struct babel_iface *ifa) | |
995 | { | |
996 | struct babel_proto *p = ifa->proto; | |
997 | struct babel_msg_hello *msg = &m->hello; | |
998 | ||
999 | TRACE(D_PACKETS, "Handling hello seqno %d interval %d", | |
1000 | msg->seqno, msg->interval); | |
1001 | ||
1002 | struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender); | |
1003 | babel_update_hello_history(n, msg->seqno, msg->interval); | |
1004 | if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS) | |
1005 | babel_send_ihu(ifa, n); | |
1006 | } | |
1007 | ||
1008 | void | |
1009 | babel_handle_ihu(union babel_msg *m, struct babel_iface *ifa) | |
1010 | { | |
1011 | struct babel_proto *p = ifa->proto; | |
1012 | struct babel_msg_ihu *msg = &m->ihu; | |
1013 | ||
1014 | /* Ignore IHUs that are not about us */ | |
1015 | if ((msg->ae != BABEL_AE_WILDCARD) && !ipa_equal(msg->addr, ifa->addr)) | |
1016 | return; | |
1017 | ||
1018 | TRACE(D_PACKETS, "Handling IHU rxcost %d interval %d", | |
1019 | msg->rxcost, msg->interval); | |
1020 | ||
1021 | struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender); | |
1022 | n->txcost = msg->rxcost; | |
1023 | n->ihu_expiry = now + BABEL_IHU_EXPIRY_FACTOR(msg->interval); | |
1024 | } | |
1025 | ||
1026 | /** | |
1027 | * babel_handle_update - handle incoming route updates | |
1028 | * @m: Incoming update TLV | |
1029 | * @ifa: Interface the update was received on | |
1030 | * | |
1031 | * This function is called as a handler for update TLVs and handles the updating | |
1032 | * and maintenance of route entries in Babel's internal routing cache. The | |
1033 | * handling follows the actions described in the Babel RFC, and at the end of | |
1034 | * each update handling, babel_select_route() is called on the affected entry to | |
1035 | * optionally update the selected routes and propagate them to the core. | |
1036 | */ | |
1037 | void | |
1038 | babel_handle_update(union babel_msg *m, struct babel_iface *ifa) | |
1039 | { | |
1040 | struct babel_proto *p = ifa->proto; | |
1041 | struct babel_msg_update *msg = &m->update; | |
1042 | ||
ecae2f43 | 1043 | struct babel_neighbor *nbr; |
937e75d8 OZ |
1044 | struct babel_entry *e; |
1045 | struct babel_source *s; | |
1046 | struct babel_route *r; | |
ecae2f43 | 1047 | node *n; |
937e75d8 OZ |
1048 | int feasible; |
1049 | ||
1050 | TRACE(D_PACKETS, "Handling update for %I/%d with seqno %d metric %d", | |
1051 | msg->prefix, msg->plen, msg->seqno, msg->metric); | |
1052 | ||
ecae2f43 OZ |
1053 | nbr = babel_find_neighbor(ifa, msg->sender); |
1054 | if (!nbr) | |
937e75d8 OZ |
1055 | { |
1056 | DBG("Babel: Haven't heard from neighbor %I; ignoring update.\n", msg->sender); | |
1057 | return; | |
1058 | } | |
1059 | ||
1060 | if (msg->router_id == p->router_id) | |
1061 | { | |
1062 | DBG("Babel: Ignoring update for our own router ID.\n"); | |
1063 | return; | |
1064 | } | |
1065 | ||
1066 | /* | |
1067 | * RFC section 3.5.4: | |
1068 | * | |
1069 | * When a Babel node receives an update (id, prefix, seqno, metric) from a | |
1070 | * neighbour neigh with a link cost value equal to cost, it checks whether it | |
1071 | * already has a routing table entry indexed by (neigh, id, prefix). | |
1072 | * | |
1073 | * If no such entry exists: | |
1074 | * | |
1075 | * o if the update is unfeasible, it is ignored; | |
1076 | * | |
1077 | * o if the metric is infinite (the update is a retraction), the update is | |
1078 | * ignored; | |
1079 | * | |
1080 | * o otherwise, a new route table entry is created, indexed by (neigh, id, | |
1081 | * prefix), with seqno equal to seqno and an advertised metric equal to the | |
1082 | * metric carried by the update. | |
1083 | * | |
1084 | * If such an entry exists: | |
1085 | * | |
1086 | * o if the entry is currently installed and the update is unfeasible, then | |
1087 | * the behaviour depends on whether the router-ids of the two entries match. | |
1088 | * If the router-ids are different, the update is treated as though it were | |
1089 | * a retraction (i.e., as though the metric were FFFF hexadecimal). If the | |
1090 | * router-ids are equal, the update is ignored; | |
1091 | * | |
1092 | * o otherwise (i.e., if either the update is feasible or the entry is not | |
1093 | * currently installed), then the entry's sequence number, advertised | |
1094 | * metric, metric, and router-id are updated and, unless the advertised | |
1095 | * metric is infinite, the route's expiry timer is reset to a small multiple | |
1096 | * of the Interval value included in the update. | |
1097 | */ | |
1098 | ||
ecae2f43 | 1099 | /* Retraction */ |
937e75d8 | 1100 | if (msg->metric == BABEL_INFINITY) |
ecae2f43 OZ |
1101 | { |
1102 | if (msg->ae == BABEL_AE_WILDCARD) | |
1103 | { | |
1104 | /* | |
1105 | * Special case: This is a retraction of all prefixes announced by this | |
1106 | * neighbour (see second-to-last paragraph of section 4.4.9 in the RFC). | |
1107 | */ | |
1108 | WALK_LIST(n, nbr->routes) | |
1109 | { | |
1110 | r = SKIP_BACK(struct babel_route, neigh_route, n); | |
1111 | r->metric = BABEL_INFINITY; | |
1112 | babel_select_route(r->e); | |
1113 | } | |
1114 | } | |
1115 | else | |
1116 | { | |
1117 | e = babel_find_entry(p, msg->prefix, msg->plen); | |
1118 | ||
1119 | if (!e) | |
1120 | return; | |
1121 | ||
1122 | /* The route entry indexed by neighbour */ | |
1123 | r = babel_find_route(e, nbr); | |
937e75d8 | 1124 | |
ecae2f43 OZ |
1125 | if (!r) |
1126 | return; | |
1127 | ||
1128 | r->metric = BABEL_INFINITY; | |
1129 | babel_select_route(e); | |
1130 | } | |
1131 | ||
1132 | /* Done with retractions */ | |
937e75d8 | 1133 | return; |
ecae2f43 | 1134 | } |
937e75d8 | 1135 | |
ecae2f43 OZ |
1136 | e = babel_get_entry(p, msg->prefix, msg->plen); |
1137 | r = babel_find_route(e, nbr); /* the route entry indexed by neighbour */ | |
937e75d8 | 1138 | s = babel_find_source(e, msg->router_id); /* for feasibility */ |
937e75d8 OZ |
1139 | feasible = babel_is_feasible(s, msg->seqno, msg->metric); |
1140 | ||
1141 | if (!r) | |
1142 | { | |
ecae2f43 | 1143 | if (!feasible) |
937e75d8 OZ |
1144 | return; |
1145 | ||
ecae2f43 | 1146 | r = babel_get_route(e, nbr); |
937e75d8 OZ |
1147 | r->advert_metric = msg->metric; |
1148 | r->router_id = msg->router_id; | |
ecae2f43 | 1149 | r->metric = babel_compute_metric(nbr, msg->metric); |
937e75d8 OZ |
1150 | r->next_hop = msg->next_hop; |
1151 | r->seqno = msg->seqno; | |
1152 | } | |
1153 | else if (r == r->e->selected_in && !feasible) | |
1154 | { | |
ecae2f43 OZ |
1155 | /* |
1156 | * Route is installed and update is infeasible - we may lose the route, | |
1157 | * so send a unicast seqno request (section 3.8.2.2 second paragraph). | |
1158 | */ | |
937e75d8 OZ |
1159 | babel_unicast_seqno_request(r); |
1160 | ||
ecae2f43 OZ |
1161 | if (msg->router_id == r->router_id) |
1162 | return; | |
1163 | ||
1164 | /* Treat as retraction */ | |
1165 | r->metric = BABEL_INFINITY; | |
937e75d8 OZ |
1166 | } |
1167 | else | |
1168 | { | |
1169 | /* Last paragraph above - update the entry */ | |
1170 | r->advert_metric = msg->metric; | |
ecae2f43 | 1171 | r->metric = babel_compute_metric(nbr, msg->metric); |
937e75d8 | 1172 | r->next_hop = msg->next_hop; |
ecae2f43 OZ |
1173 | |
1174 | r->router_id = msg->router_id; | |
937e75d8 OZ |
1175 | r->seqno = msg->seqno; |
1176 | ||
ecae2f43 OZ |
1177 | r->expiry_interval = BABEL_ROUTE_EXPIRY_FACTOR(msg->interval); |
1178 | r->expires = now + r->expiry_interval; | |
1179 | if (r->expiry_interval > BABEL_ROUTE_REFRESH_INTERVAL) | |
1180 | r->refresh_time = now + r->expiry_interval - BABEL_ROUTE_REFRESH_INTERVAL; | |
937e75d8 OZ |
1181 | |
1182 | /* If the route is not feasible at this point, it means it is from another | |
1183 | neighbour than the one currently selected; so send a unicast seqno | |
1184 | request to try to get a better route (section 3.8.2.2 last paragraph). */ | |
1185 | if (!feasible) | |
1186 | babel_unicast_seqno_request(r); | |
1187 | } | |
1188 | ||
1189 | babel_select_route(e); | |
1190 | } | |
1191 | ||
1192 | void | |
1193 | babel_handle_route_request(union babel_msg *m, struct babel_iface *ifa) | |
1194 | { | |
1195 | struct babel_proto *p = ifa->proto; | |
1196 | struct babel_msg_route_request *msg = &m->route_request; | |
1197 | ||
1198 | /* RFC 6126 3.8.1.1 */ | |
1199 | ||
1200 | /* Wildcard request - full update on the interface */ | |
1201 | if (msg->full) | |
1202 | { | |
1203 | TRACE(D_PACKETS, "Handling wildcard route request"); | |
1204 | ifa->want_triggered = 1; | |
1205 | return; | |
1206 | } | |
1207 | ||
1208 | TRACE(D_PACKETS, "Handling route request for %I/%d", msg->prefix, msg->plen); | |
1209 | ||
1210 | /* Non-wildcard request - see if we have an entry for the route. | |
1211 | If not, send a retraction, otherwise send an update. */ | |
1212 | struct babel_entry *e = babel_find_entry(p, msg->prefix, msg->plen); | |
1213 | if (!e) | |
1214 | { | |
1215 | babel_send_retraction(ifa, msg->prefix, msg->plen); | |
1216 | } | |
1217 | else | |
1218 | { | |
1219 | babel_trigger_iface_update(ifa); | |
1220 | e->updated = now; | |
1221 | } | |
1222 | } | |
1223 | ||
1224 | ||
1225 | void | |
1226 | babel_handle_seqno_request(union babel_msg *m, struct babel_iface *ifa) | |
1227 | { | |
1228 | struct babel_proto *p = ifa->proto; | |
1229 | struct babel_msg_seqno_request *msg = &m->seqno_request; | |
1230 | ||
1231 | /* RFC 6126 3.8.1.2 */ | |
1232 | ||
1233 | TRACE(D_PACKETS, "Handling seqno request for %I/%d router-id %lR seqno %d hop count %d", | |
1234 | msg->prefix, msg->plen, msg->router_id, msg->seqno, msg->hop_count); | |
1235 | ||
1236 | /* Ignore if we have no such entry or entry has infinite metric */ | |
1237 | struct babel_entry *e = babel_find_entry(p, msg->prefix, msg->plen); | |
1238 | if (!e || !e->selected_out || (e->selected_out->metric == BABEL_INFINITY)) | |
1239 | return; | |
1240 | ||
1241 | /* Trigger update on incoming interface if we have a selected route with | |
1242 | different router id or seqno no smaller than requested */ | |
1243 | struct babel_route *r = e->selected_out; | |
1244 | if ((r->router_id != msg->router_id) || ge_mod64k(r->seqno, msg->seqno)) | |
1245 | { | |
1246 | babel_trigger_iface_update(ifa); | |
1247 | e->updated = now; | |
1248 | return; | |
1249 | } | |
1250 | ||
1251 | /* Seqno is larger; check if we own the router id */ | |
1252 | if (msg->router_id == p->router_id) | |
1253 | { | |
1254 | /* Ours; update seqno and trigger global update */ | |
1255 | p->update_seqno++; | |
1256 | babel_trigger_update(p); | |
1257 | } | |
1258 | else | |
1259 | { | |
1260 | /* Not ours; forward if TTL allows it */ | |
1261 | if (msg->hop_count > 1) | |
1262 | babel_forward_seqno_request(e, msg, msg->sender); | |
1263 | } | |
1264 | } | |
1265 | ||
1266 | ||
1267 | /* | |
1268 | * Babel interfaces | |
1269 | */ | |
1270 | ||
1271 | /** | |
1272 | * babel_iface_timer - Babel interface timer handler | |
1273 | * @t: Timer | |
1274 | * | |
1275 | * This function is called by the per-interface timer and triggers sending of | |
1276 | * periodic Hello's and both triggered and periodic updates. Periodic Hello's | |
1277 | * and updates are simply handled by setting the next_{hello,regular} variables | |
1278 | * on the interface, and triggering an update (and resetting the variable) | |
1279 | * whenever 'now' exceeds that value. | |
1280 | * | |
1281 | * For triggered updates, babel_trigger_iface_update() will set the | |
1282 | * want_triggered field on the interface to a timestamp value. If this is set | |
1283 | * (and the next_triggered time has passed; this is a rate limiting mechanism), | |
1284 | * babel_send_update() will be called with this timestamp as the second | |
1285 | * parameter. This causes updates to be send consisting of only the routes that | |
1286 | * have changed since the time saved in want_triggered. | |
1287 | * | |
1288 | * Mostly when an update is triggered, the route being modified will be set to | |
1289 | * the value of 'now' at the time of the trigger; the >= comparison for | |
1290 | * selecting which routes to send in the update will make sure this is included. | |
1291 | */ | |
1292 | static void | |
1293 | babel_iface_timer(timer *t) | |
1294 | { | |
1295 | struct babel_iface *ifa = t->data; | |
1296 | struct babel_proto *p = ifa->proto; | |
1297 | bird_clock_t hello_period = ifa->cf->hello_interval; | |
1298 | bird_clock_t update_period = ifa->cf->update_interval; | |
1299 | ||
1300 | if (now >= ifa->next_hello) | |
1301 | { | |
1302 | babel_send_hello(ifa, (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS || | |
1303 | ifa->hello_seqno % BABEL_IHU_INTERVAL_FACTOR == 0)); | |
1304 | ifa->next_hello += hello_period * (1 + (now - ifa->next_hello) / hello_period); | |
1305 | } | |
1306 | ||
1307 | if (now >= ifa->next_regular) | |
1308 | { | |
1309 | TRACE(D_EVENTS, "Sending regular updates on %s", ifa->ifname); | |
1310 | babel_send_update(ifa, 0); | |
1311 | ifa->next_regular += update_period * (1 + (now - ifa->next_regular) / update_period); | |
1312 | ifa->want_triggered = 0; | |
1313 | p->triggered = 0; | |
1314 | } | |
1315 | else if (ifa->want_triggered && (now >= ifa->next_triggered)) | |
1316 | { | |
1317 | TRACE(D_EVENTS, "Sending triggered updates on %s", ifa->ifname); | |
1318 | babel_send_update(ifa, ifa->want_triggered); | |
1319 | ifa->next_triggered = now + MIN(5, update_period / 2 + 1); | |
1320 | ifa->want_triggered = 0; | |
1321 | p->triggered = 0; | |
1322 | } | |
1323 | ||
1324 | bird_clock_t next_event = MIN(ifa->next_hello, ifa->next_regular); | |
1325 | tm_start(ifa->timer, ifa->want_triggered ? 1 : (next_event - now)); | |
1326 | } | |
1327 | ||
1328 | static inline void | |
1329 | babel_iface_kick_timer(struct babel_iface *ifa) | |
1330 | { | |
1331 | if (ifa->timer->expires > (now + 1)) | |
1332 | tm_start(ifa->timer, 1); | |
1333 | } | |
1334 | ||
1335 | static void | |
1336 | babel_iface_start(struct babel_iface *ifa) | |
1337 | { | |
1338 | struct babel_proto *p = ifa->proto; | |
1339 | ||
1340 | TRACE(D_EVENTS, "Starting interface %s", ifa->ifname); | |
1341 | ||
1342 | ifa->next_hello = now + (random() % ifa->cf->hello_interval) + 1; | |
1343 | ifa->next_regular = now + (random() % ifa->cf->update_interval) + 1; | |
1344 | ifa->next_triggered = now + MIN(5, ifa->cf->update_interval / 2 + 1); | |
1345 | ifa->want_triggered = 0; /* We send an immediate update (below) */ | |
1346 | tm_start(ifa->timer, 1); | |
1347 | ifa->up = 1; | |
1348 | ||
1349 | babel_send_hello(ifa, 0); | |
1350 | babel_send_wildcard_request(ifa); | |
1351 | babel_send_update(ifa, 0); /* Full update */ | |
1352 | } | |
1353 | ||
1354 | static void | |
1355 | babel_iface_stop(struct babel_iface *ifa) | |
1356 | { | |
1357 | struct babel_proto *p = ifa->proto; | |
1358 | struct babel_neighbor *nbr; | |
1359 | struct babel_route *r; | |
1360 | node *n; | |
1361 | ||
1362 | TRACE(D_EVENTS, "Stopping interface %s", ifa->ifname); | |
1363 | ||
1364 | /* | |
1365 | * Rather than just flushing the neighbours, we set the metric of their routes | |
1366 | * to infinity. This allows us to keep the neighbour hello state for when the | |
1367 | * interface comes back up. The routes will also be kept until they expire. | |
1368 | */ | |
1369 | WALK_LIST(nbr, ifa->neigh_list) | |
1370 | { | |
1371 | WALK_LIST(n, nbr->routes) | |
1372 | { | |
1373 | r = SKIP_BACK(struct babel_route, neigh_route, n); | |
1374 | r->metric = BABEL_INFINITY; | |
1375 | r->expires = now + r->expiry_interval; | |
1376 | babel_select_route(r->e); | |
1377 | } | |
1378 | } | |
1379 | ||
1380 | tm_stop(ifa->timer); | |
1381 | ifa->up = 0; | |
1382 | } | |
1383 | ||
1384 | static inline int | |
1385 | babel_iface_link_up(struct babel_iface *ifa) | |
1386 | { | |
1387 | return !ifa->cf->check_link || (ifa->iface->flags & IF_LINK_UP); | |
1388 | } | |
1389 | ||
1390 | static void | |
1391 | babel_iface_update_state(struct babel_iface *ifa) | |
1392 | { | |
1393 | int up = ifa->sk && babel_iface_link_up(ifa); | |
1394 | ||
1395 | if (up == ifa->up) | |
1396 | return; | |
1397 | ||
1398 | if (up) | |
1399 | babel_iface_start(ifa); | |
1400 | else | |
1401 | babel_iface_stop(ifa); | |
1402 | } | |
1403 | ||
1404 | static void | |
1405 | babel_iface_update_buffers(struct babel_iface *ifa) | |
1406 | { | |
1407 | if (!ifa->sk) | |
1408 | return; | |
1409 | ||
1410 | uint mtu = MAX(BABEL_MIN_MTU, ifa->iface->mtu); | |
1411 | uint rbsize = ifa->cf->rx_buffer ?: mtu; | |
1412 | uint tbsize = ifa->cf->tx_length ?: mtu; | |
1413 | rbsize = MAX(rbsize, tbsize); | |
1414 | ||
1415 | sk_set_rbsize(ifa->sk, rbsize); | |
1416 | sk_set_tbsize(ifa->sk, tbsize); | |
1417 | ||
1418 | ifa->tx_length = tbsize - BABEL_OVERHEAD; | |
1419 | } | |
1420 | ||
1421 | static struct babel_iface* | |
1422 | babel_find_iface(struct babel_proto *p, struct iface *what) | |
1423 | { | |
1424 | struct babel_iface *ifa; | |
1425 | ||
1426 | WALK_LIST (ifa, p->interfaces) | |
1427 | if (ifa->iface == what) | |
1428 | return ifa; | |
1429 | ||
1430 | return NULL; | |
1431 | } | |
1432 | ||
1433 | static void | |
1434 | babel_iface_locked(struct object_lock *lock) | |
1435 | { | |
1436 | struct babel_iface *ifa = lock->data; | |
1437 | struct babel_proto *p = ifa->proto; | |
1438 | ||
1439 | if (!babel_open_socket(ifa)) | |
1440 | { | |
1441 | log(L_ERR "%s: Cannot open socket for %s", p->p.name, ifa->iface->name); | |
1442 | return; | |
1443 | } | |
1444 | ||
1445 | babel_iface_update_buffers(ifa); | |
1446 | babel_iface_update_state(ifa); | |
1447 | } | |
1448 | ||
1449 | static void | |
1450 | babel_add_iface(struct babel_proto *p, struct iface *new, struct babel_iface_config *ic) | |
1451 | { | |
1452 | struct babel_iface *ifa; | |
1453 | ||
1454 | TRACE(D_EVENTS, "Adding interface %s", new->name); | |
1455 | ||
1456 | pool *pool = rp_new(p->p.pool, new->name); | |
1457 | ||
1458 | ifa = mb_allocz(pool, sizeof(struct babel_iface)); | |
1459 | ifa->proto = p; | |
1460 | ifa->iface = new; | |
1461 | ifa->cf = ic; | |
1462 | ifa->pool = pool; | |
1463 | ifa->ifname = new->name; | |
1464 | ||
1465 | add_tail(&p->interfaces, NODE ifa); | |
1466 | ||
1467 | struct ifa *addr; | |
1468 | WALK_LIST(addr, new->addrs) | |
1469 | if (ipa_is_link_local(addr->ip)) | |
1470 | ifa->addr = addr->ip; | |
1471 | ||
1472 | if (ipa_zero(ifa->addr)) | |
1473 | log(L_WARN "%s: Cannot find link-local addr on %s", p->p.name, new->name); | |
1474 | ||
1475 | init_list(&ifa->neigh_list); | |
1476 | ifa->hello_seqno = 1; | |
1477 | ||
1478 | ifa->timer = tm_new_set(ifa->pool, babel_iface_timer, ifa, 0, 0); | |
1479 | ||
1480 | init_list(&ifa->msg_queue); | |
1481 | ifa->send_event = ev_new(ifa->pool); | |
1482 | ifa->send_event->hook = babel_send_queue; | |
1483 | ifa->send_event->data = ifa; | |
1484 | ||
1485 | struct object_lock *lock = olock_new(ifa->pool); | |
1486 | lock->type = OBJLOCK_UDP; | |
1487 | lock->addr = IP6_BABEL_ROUTERS; | |
1488 | lock->port = ifa->cf->port; | |
1489 | lock->iface = ifa->iface; | |
1490 | lock->hook = babel_iface_locked; | |
1491 | lock->data = ifa; | |
1492 | ||
1493 | olock_acquire(lock); | |
1494 | } | |
1495 | ||
1496 | static void | |
1497 | babel_remove_iface(struct babel_proto *p, struct babel_iface *ifa) | |
1498 | { | |
1499 | TRACE(D_EVENTS, "Removing interface %s", ifa->iface->name); | |
1500 | ||
1501 | struct babel_neighbor *n; | |
1502 | WALK_LIST_FIRST(n, ifa->neigh_list) | |
1503 | babel_flush_neighbor(n); | |
1504 | ||
1505 | rem_node(NODE ifa); | |
1506 | ||
1507 | rfree(ifa->pool); /* contains ifa itself, locks, socket, etc */ | |
1508 | } | |
1509 | ||
1510 | static void | |
1511 | babel_if_notify(struct proto *P, unsigned flags, struct iface *iface) | |
1512 | { | |
1513 | struct babel_proto *p = (void *) P; | |
1514 | struct babel_config *cf = (void *) P->cf; | |
1515 | ||
1516 | if (iface->flags & IF_IGNORE) | |
1517 | return; | |
1518 | ||
1519 | if (flags & IF_CHANGE_UP) | |
1520 | { | |
1521 | struct babel_iface_config *ic = (void *) iface_patt_find(&cf->iface_list, iface, iface->addr); | |
1522 | ||
1523 | /* we only speak multicast */ | |
1524 | if (!(iface->flags & IF_MULTICAST)) | |
1525 | return; | |
1526 | ||
1527 | if (ic) | |
1528 | babel_add_iface(p, iface, ic); | |
1529 | ||
1530 | return; | |
1531 | } | |
1532 | ||
1533 | struct babel_iface *ifa = babel_find_iface(p, iface); | |
1534 | ||
1535 | if (!ifa) | |
1536 | return; | |
1537 | ||
1538 | if (flags & IF_CHANGE_DOWN) | |
1539 | { | |
1540 | babel_remove_iface(p, ifa); | |
1541 | return; | |
1542 | } | |
1543 | ||
1544 | if (flags & IF_CHANGE_MTU) | |
1545 | babel_iface_update_buffers(ifa); | |
1546 | ||
1547 | if (flags & IF_CHANGE_LINK) | |
1548 | babel_iface_update_state(ifa); | |
1549 | } | |
1550 | ||
1551 | static int | |
1552 | babel_reconfigure_iface(struct babel_proto *p, struct babel_iface *ifa, struct babel_iface_config *new) | |
1553 | { | |
1554 | struct babel_iface_config *old = ifa->cf; | |
1555 | ||
1556 | /* Change of these options would require to reset the iface socket */ | |
1557 | if ((new->port != old->port) || | |
1558 | (new->tx_tos != old->tx_tos) || | |
1559 | (new->tx_priority != old->tx_priority)) | |
1560 | return 0; | |
1561 | ||
1562 | TRACE(D_EVENTS, "Reconfiguring interface %s", ifa->iface->name); | |
1563 | ||
1564 | ifa->cf = new; | |
1565 | ||
1566 | if (ifa->next_regular > (now + new->update_interval)) | |
1567 | ifa->next_regular = now + (random() % new->update_interval) + 1; | |
1568 | ||
1569 | if ((new->tx_length != old->tx_length) || (new->rx_buffer != old->rx_buffer)) | |
1570 | babel_iface_update_buffers(ifa); | |
1571 | ||
1572 | if (new->check_link != old->check_link) | |
1573 | babel_iface_update_state(ifa); | |
1574 | ||
1575 | if (ifa->up) | |
1576 | babel_iface_kick_timer(ifa); | |
1577 | ||
1578 | return 1; | |
1579 | } | |
1580 | ||
1581 | static void | |
1582 | babel_reconfigure_ifaces(struct babel_proto *p, struct babel_config *cf) | |
1583 | { | |
1584 | struct iface *iface; | |
1585 | ||
1586 | WALK_LIST(iface, iface_list) | |
1587 | { | |
1588 | if (! (iface->flags & IF_UP)) | |
1589 | continue; | |
1590 | ||
1591 | struct babel_iface *ifa = babel_find_iface(p, iface); | |
1592 | struct babel_iface_config *ic = (void *) iface_patt_find(&cf->iface_list, iface, NULL); | |
1593 | ||
1594 | if (ifa && ic) | |
1595 | { | |
1596 | if (babel_reconfigure_iface(p, ifa, ic)) | |
1597 | continue; | |
1598 | ||
1599 | /* Hard restart */ | |
1600 | log(L_INFO "%s: Restarting interface %s", p->p.name, ifa->iface->name); | |
1601 | babel_remove_iface(p, ifa); | |
1602 | babel_add_iface(p, iface, ic); | |
1603 | } | |
1604 | ||
1605 | if (ifa && !ic) | |
1606 | babel_remove_iface(p, ifa); | |
1607 | ||
1608 | if (!ifa && ic) | |
1609 | babel_add_iface(p, iface, ic); | |
1610 | } | |
1611 | } | |
1612 | ||
1613 | ||
1614 | /* | |
1615 | * Debugging and info output functions | |
1616 | */ | |
1617 | ||
1618 | static void | |
1619 | babel_dump_source(struct babel_source *s) | |
1620 | { | |
1621 | debug("Source router_id %lR seqno %d metric %d expires %d\n", | |
1622 | s->router_id, s->seqno, s->metric, s->expires ? s->expires-now : 0); | |
1623 | } | |
1624 | ||
1625 | static void | |
1626 | babel_dump_route(struct babel_route *r) | |
1627 | { | |
1628 | debug("Route neigh %I if %s seqno %d metric %d/%d router_id %lR expires %d\n", | |
1629 | r->neigh ? r->neigh->addr : IPA_NONE, | |
1630 | r->neigh ? r->neigh->ifa->ifname : "(none)", | |
1631 | r->seqno, r->advert_metric, r->metric, | |
1632 | r->router_id, r->expires ? r->expires-now : 0); | |
1633 | } | |
1634 | ||
1635 | static void | |
1636 | babel_dump_entry(struct babel_entry *e) | |
1637 | { | |
1638 | struct babel_source *s; | |
1639 | struct babel_route *r; | |
1640 | ||
1641 | debug("Babel: Entry %I/%d:\n", e->n.prefix, e->n.pxlen); | |
1642 | ||
1643 | WALK_LIST(s,e->sources) | |
1644 | { debug(" "); babel_dump_source(s); } | |
1645 | ||
1646 | WALK_LIST(r,e->routes) | |
1647 | { | |
1648 | debug(" "); | |
1649 | if (r == e->selected_out) debug("*"); | |
1650 | if (r == e->selected_in) debug("+"); | |
1651 | babel_dump_route(r); | |
1652 | } | |
1653 | } | |
1654 | ||
1655 | static void | |
1656 | babel_dump_neighbor(struct babel_neighbor *n) | |
1657 | { | |
1658 | debug("Neighbor %I txcost %d hello_map %x next seqno %d expires %d/%d\n", | |
1659 | n->addr, n->txcost, n->hello_map, n->next_hello_seqno, | |
1660 | n->hello_expiry ? n->hello_expiry - now : 0, | |
1661 | n->ihu_expiry ? n->ihu_expiry - now : 0); | |
1662 | } | |
1663 | ||
1664 | static void | |
1665 | babel_dump_iface(struct babel_iface *ifa) | |
1666 | { | |
1667 | struct babel_neighbor *n; | |
1668 | ||
1669 | debug("Babel: Interface %s addr %I rxcost %d type %d hello seqno %d intervals %d %d\n", | |
1670 | ifa->ifname, ifa->addr, ifa->cf->rxcost, ifa->cf->type, ifa->hello_seqno, | |
1671 | ifa->cf->hello_interval, ifa->cf->update_interval); | |
1672 | ||
1673 | WALK_LIST(n, ifa->neigh_list) | |
1674 | { debug(" "); babel_dump_neighbor(n); } | |
1675 | } | |
1676 | ||
1677 | static void | |
1678 | babel_dump(struct proto *P) | |
1679 | { | |
1680 | struct babel_proto *p = (struct babel_proto *) P; | |
1681 | struct babel_iface *ifa; | |
1682 | ||
1683 | debug("Babel: router id %lR update seqno %d\n", p->router_id, p->update_seqno); | |
1684 | ||
1685 | WALK_LIST(ifa, p->interfaces) | |
1686 | babel_dump_iface(ifa); | |
1687 | ||
1688 | FIB_WALK(&p->rtable, n) | |
1689 | { | |
1690 | babel_dump_entry((struct babel_entry *) n); | |
1691 | } | |
1692 | FIB_WALK_END; | |
1693 | } | |
1694 | ||
1695 | static void | |
1696 | babel_get_route_info(rte *rte, byte *buf, ea_list *attrs) | |
1697 | { | |
1698 | buf += bsprintf(buf, " (%d/%d) [%lR]", rte->pref, rte->u.babel.metric, rte->u.babel.router_id); | |
1699 | } | |
1700 | ||
1701 | static int | |
1702 | babel_get_attr(eattr *a, byte *buf, int buflen UNUSED) | |
1703 | { | |
1704 | switch (a->id) | |
1705 | { | |
1706 | case EA_BABEL_METRIC: | |
1707 | bsprintf(buf, "metric: %d", a->u.data); | |
1708 | return GA_FULL; | |
1709 | ||
1710 | case EA_BABEL_ROUTER_ID: | |
1711 | { | |
1712 | u64 rid = 0; | |
1713 | memcpy(&rid, a->u.ptr->data, sizeof(u64)); | |
1714 | bsprintf(buf, "router_id: %lR", rid); | |
1715 | return GA_FULL; | |
1716 | } | |
1717 | ||
1718 | default: | |
1719 | return GA_UNKNOWN; | |
1720 | } | |
1721 | } | |
1722 | ||
1723 | void | |
1724 | babel_show_interfaces(struct proto *P, char *iff) | |
1725 | { | |
1726 | struct babel_proto *p = (void *) P; | |
1727 | struct babel_iface *ifa = NULL; | |
1728 | struct babel_neighbor *nbr = NULL; | |
1729 | ||
1730 | if (p->p.proto_state != PS_UP) | |
1731 | { | |
1732 | cli_msg(-1023, "%s: is not up", p->p.name); | |
1733 | cli_msg(0, ""); | |
1734 | return; | |
1735 | } | |
1736 | ||
1737 | cli_msg(-1023, "%s:", p->p.name); | |
1738 | cli_msg(-1023, "%-10s %-6s %7s %6s %6s", | |
1739 | "Interface", "State", "RX cost", "Nbrs", "Timer"); | |
1740 | ||
1741 | WALK_LIST(ifa, p->interfaces) | |
1742 | { | |
1743 | if (iff && !patmatch(iff, ifa->iface->name)) | |
1744 | continue; | |
1745 | ||
1746 | int nbrs = 0; | |
1747 | WALK_LIST(nbr, ifa->neigh_list) | |
1748 | nbrs++; | |
1749 | ||
1750 | int timer = MIN(ifa->next_regular, ifa->next_hello) - now; | |
1751 | cli_msg(-1023, "%-10s %-6s %7u %6u %6u", | |
1752 | ifa->iface->name, (ifa->up ? "Up" : "Down"), ifa->cf->rxcost, nbrs, MAX(timer, 0)); | |
1753 | } | |
1754 | ||
1755 | cli_msg(0, ""); | |
1756 | } | |
1757 | ||
1758 | void | |
1759 | babel_show_neighbors(struct proto *P, char *iff) | |
1760 | { | |
1761 | struct babel_proto *p = (void *) P; | |
1762 | struct babel_iface *ifa = NULL; | |
1763 | struct babel_neighbor *n = NULL; | |
1764 | struct babel_route *r = NULL; | |
1765 | ||
1766 | if (p->p.proto_state != PS_UP) | |
1767 | { | |
1768 | cli_msg(-1024, "%s: is not up", p->p.name); | |
1769 | cli_msg(0, ""); | |
1770 | return; | |
1771 | } | |
1772 | ||
1773 | cli_msg(-1024, "%s:", p->p.name); | |
1774 | cli_msg(-1024, "%-25s %-10s %6s %6s %10s", | |
1775 | "IP address", "Interface", "Metric", "Routes", "Next hello"); | |
1776 | ||
1777 | WALK_LIST(ifa, p->interfaces) | |
1778 | { | |
1779 | if (iff && !patmatch(iff, ifa->iface->name)) | |
1780 | continue; | |
1781 | ||
1782 | WALK_LIST(n, ifa->neigh_list) | |
1783 | { | |
1784 | int rts = 0; | |
1785 | WALK_LIST(r, n->routes) | |
1786 | rts++; | |
1787 | ||
1788 | int timer = n->hello_expiry - now; | |
1789 | cli_msg(-1024, "%-25I %-10s %6u %6u %10u", | |
1790 | n->addr, ifa->iface->name, n->txcost, rts, MAX(timer, 0)); | |
1791 | } | |
1792 | } | |
1793 | ||
1794 | cli_msg(0, ""); | |
1795 | } | |
1796 | ||
1797 | void | |
1798 | babel_show_entries(struct proto *P) | |
1799 | { | |
1800 | struct babel_proto *p = (void *) P; | |
1801 | struct babel_entry *e = NULL; | |
1802 | struct babel_source *s = NULL; | |
1803 | struct babel_route *r = NULL; | |
1804 | ||
1805 | char ipbuf[STD_ADDRESS_P_LENGTH+5]; | |
1806 | char ridbuf[ROUTER_ID_64_LENGTH+1]; | |
1807 | ||
1808 | if (p->p.proto_state != PS_UP) | |
1809 | { | |
1810 | cli_msg(-1025, "%s: is not up", p->p.name); | |
1811 | cli_msg(0, ""); | |
1812 | return; | |
1813 | } | |
1814 | ||
1815 | cli_msg(-1025, "%s:", p->p.name); | |
1816 | cli_msg(-1025, "%-29s %-23s %6s %5s %7s %7s", | |
1817 | "Prefix", "Router ID", "Metric", "Seqno", "Expires", "Sources"); | |
1818 | ||
1819 | FIB_WALK(&p->rtable, n) | |
1820 | { | |
1821 | e = (struct babel_entry *) n; | |
1822 | r = e->selected_in ? e->selected_in : e->selected_out; | |
1823 | ||
1824 | int srcs = 0; | |
1825 | WALK_LIST(s, e->sources) | |
1826 | srcs++; | |
1827 | ||
1828 | bsprintf(ipbuf, "%I/%u", e->n.prefix, e->n.pxlen); | |
1829 | ||
1830 | if (r) | |
1831 | { | |
1832 | if (r->router_id == p->router_id) | |
1833 | bsprintf(ridbuf, "%s", "<self>"); | |
1834 | else | |
1835 | bsprintf(ridbuf, "%lR", r->router_id); | |
1836 | ||
1837 | int time = r->expires ? r->expires - now : 0; | |
1838 | cli_msg(-1025, "%-29s %-23s %6u %5u %7u %7u", | |
1839 | ipbuf, ridbuf, r->metric, r->seqno, MAX(time, 0), srcs); | |
1840 | } | |
1841 | else | |
1842 | { | |
1843 | cli_msg(-1025, "%-29s %-44s %7u", ipbuf, "<pending>", srcs); | |
1844 | } | |
1845 | } | |
1846 | FIB_WALK_END; | |
1847 | ||
1848 | cli_msg(0, ""); | |
1849 | } | |
1850 | ||
1851 | ||
1852 | /* | |
1853 | * Babel protocol glue | |
1854 | */ | |
1855 | ||
1856 | /** | |
1857 | * babel_timer - global timer hook | |
1858 | * @t: Timer | |
1859 | * | |
1860 | * This function is called by the global protocol instance timer and handles | |
1861 | * expiration of routes and neighbours as well as pruning of the seqno request | |
1862 | * cache. | |
1863 | */ | |
1864 | static void | |
1865 | babel_timer(timer *t) | |
1866 | { | |
1867 | struct babel_proto *p = t->data; | |
1868 | ||
1869 | babel_expire_routes(p); | |
1870 | babel_expire_seqno_requests(p); | |
1871 | babel_expire_neighbors(p); | |
1872 | } | |
1873 | ||
1874 | static inline void | |
1875 | babel_kick_timer(struct babel_proto *p) | |
1876 | { | |
1877 | if (p->timer->expires > (now + 1)) | |
1878 | tm_start(p->timer, 1); | |
1879 | } | |
1880 | ||
1881 | ||
1882 | static struct ea_list * | |
1883 | babel_prepare_attrs(struct linpool *pool, ea_list *next, uint metric, u64 router_id) | |
1884 | { | |
1885 | struct ea_list *l = lp_alloc(pool, sizeof(struct ea_list) + 2*sizeof(eattr)); | |
1886 | struct adata *rid = lp_alloc(pool, sizeof(struct adata) + sizeof(u64)); | |
1887 | rid->length = sizeof(u64); | |
1888 | memcpy(&rid->data, &router_id, sizeof(u64)); | |
1889 | ||
1890 | l->next = next; | |
1891 | l->flags = EALF_SORTED; | |
1892 | l->count = 2; | |
1893 | ||
1894 | l->attrs[0].id = EA_BABEL_METRIC; | |
1895 | l->attrs[0].flags = 0; | |
1896 | l->attrs[0].type = EAF_TYPE_INT | EAF_TEMP; | |
1897 | l->attrs[0].u.data = metric; | |
1898 | ||
1899 | l->attrs[1].id = EA_BABEL_ROUTER_ID; | |
1900 | l->attrs[1].flags = 0; | |
1901 | l->attrs[1].type = EAF_TYPE_OPAQUE | EAF_TEMP; | |
1902 | l->attrs[1].u.ptr = rid; | |
1903 | ||
1904 | return l; | |
1905 | } | |
1906 | ||
1907 | ||
1908 | static int | |
1909 | babel_import_control(struct proto *P, struct rte **rt, struct ea_list **attrs, struct linpool *pool) | |
1910 | { | |
1911 | struct babel_proto *p = (void *) P; | |
1912 | ||
1913 | /* Prepare attributes with initial values */ | |
1914 | if ((*rt)->attrs->source != RTS_BABEL) | |
1915 | *attrs = babel_prepare_attrs(pool, NULL, 0, p->router_id); | |
1916 | ||
1917 | return 0; | |
1918 | } | |
1919 | ||
1920 | static struct ea_list * | |
1921 | babel_make_tmp_attrs(struct rte *rt, struct linpool *pool) | |
1922 | { | |
1923 | return babel_prepare_attrs(pool, NULL, rt->u.babel.metric, rt->u.babel.router_id); | |
1924 | } | |
1925 | ||
1926 | static void | |
1927 | babel_store_tmp_attrs(struct rte *rt, struct ea_list *attrs) | |
1928 | { | |
1929 | rt->u.babel.metric = ea_get_int(attrs, EA_BABEL_METRIC, 0); | |
1930 | } | |
1931 | ||
1932 | /* | |
1933 | * babel_rt_notify - core tells us about new route (possibly our own), | |
1934 | * so store it into our data structures. | |
1935 | */ | |
1936 | static void | |
1937 | babel_rt_notify(struct proto *P, struct rtable *table UNUSED, struct network *net, | |
1938 | struct rte *new, struct rte *old, struct ea_list *attrs) | |
1939 | { | |
1940 | struct babel_proto *p = (void *) P; | |
1941 | struct babel_entry *e; | |
1942 | struct babel_route *r; | |
1943 | ||
1944 | if (new) | |
1945 | { | |
1946 | /* Update */ | |
1947 | e = babel_get_entry(p, net->n.prefix, net->n.pxlen); | |
1948 | ||
1949 | if (new->attrs->src->proto != P) | |
1950 | { | |
1951 | r = babel_get_route(e, NULL); | |
1952 | r->seqno = p->update_seqno; | |
1953 | r->router_id = p->router_id; | |
1954 | r->metric = 0; /* FIXME: should be selectable */ | |
1955 | } | |
1956 | else | |
1957 | r = e->selected_in; | |
1958 | ||
1959 | if (r != e->selected_out) | |
1960 | { | |
1961 | e->selected_out = r; | |
1962 | e->updated = now; | |
1963 | babel_trigger_update(p); | |
1964 | } | |
1965 | } | |
1966 | else | |
1967 | { | |
1968 | /* Withdraw */ | |
1969 | e = babel_find_entry(p, net->n.prefix, net->n.pxlen); | |
1970 | if (!e || !e->selected_out) | |
1971 | return; | |
1972 | ||
1973 | if (OUR_ROUTE(e->selected_out)) | |
1974 | { | |
1975 | /* | |
1976 | * We originate this route, so set its metric to infinity and set an | |
1977 | * expiry time. This causes a retraction to be sent, and later the route | |
1978 | * to be flushed once the hold time has passed. | |
1979 | */ | |
1980 | e->selected_out->metric = BABEL_INFINITY; | |
1981 | e->selected_out->expires = now + BABEL_HOLD_TIME; | |
1982 | e->updated = now; | |
1983 | babel_trigger_update(p); | |
1984 | } | |
1985 | else | |
1986 | { | |
1987 | /* | |
1988 | * This is a route originating from someone else that was lost; presumably | |
1989 | * because an export filter was updated to filter it. This means we can't | |
1990 | * set the metric to infinity (it would be overridden on subsequent | |
1991 | * updates from the peer originating the route), so just clear the | |
1992 | * exported route. | |
1993 | * | |
1994 | * This causes peers to expire the route after a while (like if we just | |
1995 | * shut down), but it's the best we can do in these circumstances; and | |
1996 | * since export filters presumably aren't updated that often this is | |
1997 | * acceptable. | |
1998 | */ | |
1999 | e->selected_out = NULL; | |
2000 | } | |
2001 | } | |
2002 | } | |
2003 | ||
2004 | static int | |
2005 | babel_rte_better(struct rte *new, struct rte *old) | |
2006 | { | |
2007 | return new->u.babel.metric < old->u.babel.metric; | |
2008 | } | |
2009 | ||
2010 | static int | |
2011 | babel_rte_same(struct rte *new, struct rte *old) | |
2012 | { | |
2013 | return ((new->u.babel.router_id == old->u.babel.router_id) && | |
2014 | (new->u.babel.metric == old->u.babel.metric)); | |
2015 | } | |
2016 | ||
2017 | ||
2018 | static struct proto * | |
2019 | babel_init(struct proto_config *cfg) | |
2020 | { | |
2021 | struct proto *P = proto_new(cfg, sizeof(struct babel_proto)); | |
2022 | ||
2023 | P->accept_ra_types = RA_OPTIMAL; | |
2024 | P->if_notify = babel_if_notify; | |
2025 | P->rt_notify = babel_rt_notify; | |
2026 | P->import_control = babel_import_control; | |
2027 | P->make_tmp_attrs = babel_make_tmp_attrs; | |
2028 | P->store_tmp_attrs = babel_store_tmp_attrs; | |
2029 | P->rte_better = babel_rte_better; | |
2030 | P->rte_same = babel_rte_same; | |
2031 | ||
2032 | return P; | |
2033 | } | |
2034 | ||
2035 | static int | |
2036 | babel_start(struct proto *P) | |
2037 | { | |
2038 | struct babel_proto *p = (void *) P; | |
2039 | struct babel_config *cf = (void *) P->cf; | |
2040 | ||
2041 | fib_init(&p->rtable, P->pool, sizeof(struct babel_entry), 0, babel_init_entry); | |
2042 | init_list(&p->interfaces); | |
2043 | p->timer = tm_new_set(P->pool, babel_timer, p, 0, 1); | |
2044 | tm_start(p->timer, 2); | |
2045 | p->update_seqno = 1; | |
2046 | p->router_id = proto_get_router_id(&cf->c); | |
2047 | ||
2048 | p->route_slab = sl_new(P->pool, sizeof(struct babel_route)); | |
2049 | p->source_slab = sl_new(P->pool, sizeof(struct babel_source)); | |
2050 | p->msg_slab = sl_new(P->pool, sizeof(struct babel_msg_node)); | |
2051 | p->seqno_slab = sl_new(P->pool, sizeof(struct babel_seqno_request)); | |
2052 | init_list(&p->seqno_cache); | |
2053 | ||
2054 | p->log_pkt_tbf = (struct tbf){ .rate = 1, .burst = 5 }; | |
2055 | ||
2056 | return PS_UP; | |
2057 | } | |
2058 | ||
2059 | static int | |
2060 | babel_reconfigure(struct proto *P, struct proto_config *c) | |
2061 | { | |
2062 | struct babel_proto *p = (void *) P; | |
2063 | struct babel_config *new = (void *) c; | |
2064 | ||
2065 | TRACE(D_EVENTS, "Reconfiguring"); | |
2066 | ||
2067 | p->p.cf = c; | |
2068 | babel_reconfigure_ifaces(p, new); | |
2069 | ||
2070 | babel_trigger_update(p); | |
2071 | babel_kick_timer(p); | |
2072 | ||
2073 | return 1; | |
2074 | } | |
2075 | ||
2076 | ||
2077 | struct protocol proto_babel = { | |
2078 | .name = "Babel", | |
2079 | .template = "babel%d", | |
2080 | .attr_class = EAP_BABEL, | |
2081 | .preference = DEF_PREF_BABEL, | |
2082 | .config_size = sizeof(struct babel_config), | |
2083 | .init = babel_init, | |
2084 | .dump = babel_dump, | |
2085 | .start = babel_start, | |
2086 | .reconfigure = babel_reconfigure, | |
2087 | .get_route_info = babel_get_route_info, | |
2088 | .get_attr = babel_get_attr | |
2089 | }; |