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