]> git.proxmox.com Git - mirror_frr.git/blame - babeld/message.c
projects / mirror_frr.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Merge pull request #5793 from ton31337/fix/formatting_show_bgp_summary_failed
[mirror_frr.git] / babeld / message.c
CommitLineData
ca10883e
DS		 1/*
2Copyright (c) 2007, 2008 by Juliusz Chroboczek
3
4Permission is hereby granted, free of charge, to any person obtaining a copy
5of this software and associated documentation files (the "Software"), to deal
6in the Software without restriction, including without limitation the rights
7to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8copies of the Software, and to permit persons to whom the Software is
9furnished to do so, subject to the following conditions:
10
11The above copyright notice and this permission notice shall be included in
12all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20THE SOFTWARE.
21*/
22
23#include <zebra.h>
24#include "if.h"
25
26#include "babeld.h"
27#include "util.h"
28#include "net.h"
29#include "babel_interface.h"
30#include "source.h"
31#include "neighbour.h"
32#include "route.h"
33#include "xroute.h"
34#include "resend.h"
35#include "message.h"
36#include "kernel.h"
37#include "babel_main.h"
e33b116c 38#include "babel_errors.h"
ca10883e
DS		 39
40static unsigned char packet_header[4] = {42, 2};
41
42int split_horizon = 1;
43
44unsigned short myseqno = 0;
45
46#define UNICAST_BUFSIZE 1024
47static int unicast_buffered = 0;
48static unsigned char *unicast_buffer = NULL;
49struct neighbour *unicast_neighbour = NULL;
50struct timeval unicast_flush_timeout = {0, 0};
51
52/* Minimum TLV _body_ length for TLVs of particular types (0 = no limit). */
53static const unsigned char tlv_min_length[MESSAGE_MAX + 1] =
54{
55 [ MESSAGE_PAD1 ] = 0,
56 [ MESSAGE_PADN ] = 0,
57 [ MESSAGE_ACK_REQ ] = 6,
58 [ MESSAGE_ACK ] = 2,
59 [ MESSAGE_HELLO ] = 6,
60 [ MESSAGE_IHU ] = 6,
61 [ MESSAGE_ROUTER_ID ] = 10,
62 [ MESSAGE_NH ] = 2,
63 [ MESSAGE_UPDATE ] = 10,
64 [ MESSAGE_REQUEST ] = 2,
65 [ MESSAGE_MH_REQUEST ] = 14,
66};
67
68/* Parse a network prefix, encoded in the somewhat baroque compressed
69 representation used by Babel. Return the number of bytes parsed. */
70static int
71network_prefix(int ae, int plen, unsigned int omitted,
72 const unsigned char *p, const unsigned char *dp,
73 unsigned int len, unsigned char *p_r)
74{
75 unsigned pb;
76 unsigned char prefix[16];
77 int ret = -1;
78
79 if(plen >= 0)
80 pb = (plen + 7) / 8;
81 else if(ae == 1)
82 pb = 4;
83 else
84 pb = 16;
85
86 if(pb > 16)
87 return -1;
88
89 memset(prefix, 0, 16);
90
91 switch(ae) {
92 case 0:
93 ret = 0;
94 break;
95 case 1:
96 if(omitted > 4 || pb > 4 || (pb > omitted && len < pb - omitted))
97 return -1;
98 memcpy(prefix, v4prefix, 12);
99 if(omitted) {
100 if (dp == NULL || !v4mapped(dp)) return -1;
101 memcpy(prefix, dp, 12 + omitted);
102 }
103 if(pb > omitted) memcpy(prefix + 12 + omitted, p, pb - omitted);
104 ret = pb - omitted;
105 break;
106 case 2:
107 if(omitted > 16 || (pb > omitted && len < pb - omitted)) return -1;
108 if(omitted) {
109 if (dp == NULL || v4mapped(dp)) return -1;
110 memcpy(prefix, dp, omitted);
111 }
112 if(pb > omitted) memcpy(prefix + omitted, p, pb - omitted);
113 ret = pb - omitted;
114 break;
115 case 3:
116 if(pb > 8 && len < pb - 8) return -1;
117 prefix[0] = 0xfe;
118 prefix[1] = 0x80;
119 if(pb > 8) memcpy(prefix + 8, p, pb - 8);
120 ret = pb - 8;
121 break;
122 default:
123 return -1;
124 }
125
126 mask_prefix(p_r, prefix, plen < 0 ? 128 : ae == 1 ? plen + 96 : plen);
127 return ret;
128}
129
130static void
131parse_update_subtlv(const unsigned char *a, int alen,
132 unsigned char *channels)
133{
134 int type, len, i = 0;
135
136 while(i < alen) {
137 type = a[i];
138 if(type == SUBTLV_PAD1) {
139 i++;
140 continue;
141 }
142
143 if(i + 1 > alen) {
5b003f31 144 flog_err(EC_BABEL_PACKET, "Received truncated attributes.");
ca10883e
DS		 145 return;
146 }
147 len = a[i + 1];
148 if(i + len > alen) {
5b003f31 149 flog_err(EC_BABEL_PACKET, "Received truncated attributes.");
ca10883e
DS		 150 return;
151 }
152
153 if(type == SUBTLV_PADN) {
154 /* Nothing. */
155 } else if(type == SUBTLV_DIVERSITY) {
156 if(len > DIVERSITY_HOPS) {
5b003f31 157 flog_err(EC_BABEL_PACKET,
e33b116c
DS		 158 "Received overlong channel information (%d > %d).n",
159 len, DIVERSITY_HOPS);
ca10883e
DS		 160 len = DIVERSITY_HOPS;
161 }
162 if(memchr(a + i + 2, 0, len) != NULL) {
163 /* 0 is reserved. */
5b003f31 164 flog_err(EC_BABEL_PACKET, "Channel information contains 0!");
ca10883e
DS		 165 return;
166 }
167 memset(channels, 0, DIVERSITY_HOPS);
168 memcpy(channels, a + i + 2, len);
169 } else {
170 debugf(BABEL_DEBUG_COMMON,
171 "Received unknown route attribute %d.", type);
172 }
173
174 i += len + 2;
175 }
176}
177
178static int
179parse_hello_subtlv(const unsigned char *a, int alen,
180 unsigned int *hello_send_us)
181{
182 int type, len, i = 0, ret = 0;
183
184 while(i < alen) {
185 type = a[0];
186 if(type == SUBTLV_PAD1) {
187 i++;
188 continue;
189 }
190
191 if(i + 1 > alen) {
5b003f31 192 flog_err(EC_BABEL_PACKET,
e33b116c 193 "Received truncated sub-TLV on Hello message.");
ca10883e
DS		 194 return -1;
195 }
196 len = a[i + 1];
197 if(i + len > alen) {
5b003f31 198 flog_err(EC_BABEL_PACKET,
e33b116c 199 "Received truncated sub-TLV on Hello message.");
ca10883e
DS		 200 return -1;
201 }
202
203 if(type == SUBTLV_PADN) {
204 /* Nothing to do. */
205 } else if(type == SUBTLV_TIMESTAMP) {
206 if(len >= 4) {
207 DO_NTOHL(*hello_send_us, a + i + 2);
208 ret = 1;
209 } else {
5b003f31 210 flog_err(EC_BABEL_PACKET,
e33b116c 211 "Received incorrect RTT sub-TLV on Hello message.");
ca10883e
DS		 212 }
213 } else {
214 debugf(BABEL_DEBUG_COMMON,
215 "Received unknown Hello sub-TLV type %d.", type);
216 }
217
218 i += len + 2;
219 }
220 return ret;
221}
222
223static int
224parse_ihu_subtlv(const unsigned char *a, int alen,
225 unsigned int *hello_send_us,
226 unsigned int *hello_rtt_receive_time)
227{
228 int type, len, i = 0, ret = 0;
229
230 while(i < alen) {
231 type = a[0];
232 if(type == SUBTLV_PAD1) {
233 i++;
234 continue;
235 }
236
237 if(i + 1 > alen) {
5b003f31 238 flog_err(EC_BABEL_PACKET,
e33b116c 239 "Received truncated sub-TLV on IHU message.");
ca10883e
DS		 240 return -1;
241 }
242 len = a[i + 1];
243 if(i + len > alen) {
5b003f31 244 flog_err(EC_BABEL_PACKET,
e33b116c 245 "Received truncated sub-TLV on IHU message.");
ca10883e
DS		 246 return -1;
247 }
248
249 if(type == SUBTLV_PADN) {
250 /* Nothing to do. */
251 } else if(type == SUBTLV_TIMESTAMP) {
252 if(len >= 8) {
253 DO_NTOHL(*hello_send_us, a + i + 2);
254 DO_NTOHL(*hello_rtt_receive_time, a + i + 6);
255 ret = 1;
256 }
257 else {
5b003f31 258 flog_err(EC_BABEL_PACKET,
e33b116c 259 "Received incorrect RTT sub-TLV on IHU message.");
ca10883e
DS		 260 }
261 } else {
262 debugf(BABEL_DEBUG_COMMON,
263 "Received unknown IHU sub-TLV type %d.", type);
264 }
265
266 i += len + 2;
267 }
268 return ret;
269}
270
271static int
272network_address(int ae, const unsigned char *a, unsigned int len,
273 unsigned char *a_r)
274{
275 return network_prefix(ae, -1, 0, a, NULL, len, a_r);
276}
277
278static int
279channels_len(unsigned char *channels)
280{
281 unsigned char *p = memchr(channels, 0, DIVERSITY_HOPS);
282 return p ? (p - channels) : DIVERSITY_HOPS;
283}
284
285/* Check, that the provided frame consists of a valid Babel packet header
286 followed by a sequence of TLVs. TLVs of known types are also checked to meet
287 minimum length constraints defined for each. Return 0 for no errors. */
288static int
289babel_packet_examin(const unsigned char *packet, int packetlen)
290{
291 unsigned i = 0, bodylen;
292 const unsigned char *message;
293 unsigned char type, len;
294
295 if(packetlen < 4 || packet[0] != 42 || packet[1] != 2)
296 return 1;
297 DO_NTOHS(bodylen, packet + 2);
298 while (i < bodylen){
299 message = packet + 4 + i;
300 type = message[0];
301 if(type == MESSAGE_PAD1) {
302 i++;
303 continue;
304 }
305 if(i + 1 > bodylen) {
306 debugf(BABEL_DEBUG_COMMON,"Received truncated message.");
307 return 1;
308 }
309 len = message[1];
310 if(i + len > bodylen) {
311 debugf(BABEL_DEBUG_COMMON,"Received truncated message.");
312 return 1;
313 }
314 /* not Pad1 */
315 if(type <= MESSAGE_MAX && tlv_min_length[type] && len < tlv_min_length[type]) {
316 debugf(BABEL_DEBUG_COMMON,"Undersized %u TLV", type);
317 return 1;
318 }
319 i += len + 2;
320 }
321 return 0;
322}
323
324void
325parse_packet(const unsigned char *from, struct interface *ifp,
326 const unsigned char *packet, int packetlen)
327{
328 int i;
329 const unsigned char *message;
330 unsigned char type, len;
331 int bodylen;
332 struct neighbour *neigh;
333 int have_router_id = 0, have_v4_prefix = 0, have_v6_prefix = 0,
334 have_v4_nh = 0, have_v6_nh = 0;
335 unsigned char router_id[8], v4_prefix[16], v6_prefix[16],
336 v4_nh[16], v6_nh[16];
337 int have_hello_rtt = 0;
338 /* Content of the RTT sub-TLV on IHU messages. */
339 unsigned int hello_send_us = 0, hello_rtt_receive_time = 0;
340 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
341
342 if(babel_ifp->flags & BABEL_IF_TIMESTAMPS) {
343 /* We want to track exactly when we received this packet. */
344 gettime(&babel_now);
345 }
346
347 if(!linklocal(from)) {
5b003f31 348 flog_err(EC_BABEL_PACKET,
e33b116c
DS		 349 "Received packet from non-local address %s.",
350 format_address(from));
ca10883e
DS		 351 return;
352 }
353
354 if (babel_packet_examin (packet, packetlen)) {
5b003f31 355 flog_err(EC_BABEL_PACKET,
e33b116c
DS		 356 "Received malformed packet on %s from %s.",
357 ifp->name, format_address(from));
ca10883e
DS		 358 return;
359 }
360
361 neigh = find_neighbour(from, ifp);
362 if(neigh == NULL) {
5b003f31 363 flog_err(EC_BABEL_PACKET, "Couldn't allocate neighbour.");
ca10883e
DS		 364 return;
365 }
366
367 DO_NTOHS(bodylen, packet + 2);
368
369 if(bodylen + 4 > packetlen) {
5b003f31 370 flog_err(EC_BABEL_PACKET, "Received truncated packet (%d + 4 > %d).",
ca10883e
DS		 371 bodylen, packetlen);
372 bodylen = packetlen - 4;
373 }
374
375 i = 0;
376 while(i < bodylen) {
377 message = packet + 4 + i;
378 type = message[0];
379 if(type == MESSAGE_PAD1) {
380 debugf(BABEL_DEBUG_COMMON,"Received pad1 from %s on %s.",
381 format_address(from), ifp->name);
382 i++;
383 continue;
384 }
385 len = message[1];
386
387 if(type == MESSAGE_PADN) {
388 debugf(BABEL_DEBUG_COMMON,"Received pad%d from %s on %s.",
389 len, format_address(from), ifp->name);
390 } else if(type == MESSAGE_ACK_REQ) {
391 unsigned short nonce, interval;
392 DO_NTOHS(nonce, message + 4);
393 DO_NTOHS(interval, message + 6);
394 debugf(BABEL_DEBUG_COMMON,"Received ack-req (%04X %d) from %s on %s.",
395 nonce, interval, format_address(from), ifp->name);
396 send_ack(neigh, nonce, interval);
397 } else if(type == MESSAGE_ACK) {
398 debugf(BABEL_DEBUG_COMMON,"Received ack from %s on %s.",
399 format_address(from), ifp->name);
400 /* Nothing right now */
401 } else if(type == MESSAGE_HELLO) {
402 unsigned short seqno, interval;
403 int changed;
a97986ff 404 unsigned int timestamp = 0;
ca10883e
DS		 405 DO_NTOHS(seqno, message + 4);
406 DO_NTOHS(interval, message + 6);
407 debugf(BABEL_DEBUG_COMMON,"Received hello %d (%d) from %s on %s.",
408 seqno, interval,
409 format_address(from), ifp->name);
410 changed = update_neighbour(neigh, seqno, interval);
411 update_neighbour_metric(neigh, changed);
412 if(interval > 0)
413 /* Multiply by 3/2 to allow hellos to expire. */
414 schedule_neighbours_check(interval * 15, 0);
415 /* Sub-TLV handling. */
416 if(len > 8) {
417 if(parse_hello_subtlv(message + 8, len - 6, &timestamp) > 0) {
418 neigh->hello_send_us = timestamp;
419 neigh->hello_rtt_receive_time = babel_now;
420 have_hello_rtt = 1;
421 }
422 }
423 } else if(type == MESSAGE_IHU) {
424 unsigned short txcost, interval;
425 unsigned char address[16];
426 int rc;
427 DO_NTOHS(txcost, message + 4);
428 DO_NTOHS(interval, message + 6);
429 rc = network_address(message[2], message + 8, len - 6, address);
430 if(rc < 0) goto fail;
431 debugf(BABEL_DEBUG_COMMON,"Received ihu %d (%d) from %s on %s for %s.",
432 txcost, interval,
433 format_address(from), ifp->name,
434 format_address(address));
435 if(message[2] == 0 || is_interface_ll_address(ifp, address)) {
436 int changed = txcost != neigh->txcost;
437 neigh->txcost = txcost;
438 neigh->ihu_time = babel_now;
439 neigh->ihu_interval = interval;
440 update_neighbour_metric(neigh, changed);
441 if(interval > 0)
442 /* Multiply by 3/2 to allow neighbours to expire. */
443 schedule_neighbours_check(interval * 45, 0);
444 /* RTT sub-TLV. */
445 if(len > 10 + rc)
446 parse_ihu_subtlv(message + 8 + rc, len - 6 - rc,
447 &hello_send_us, &hello_rtt_receive_time);
448 }
449 } else if(type == MESSAGE_ROUTER_ID) {
450 memcpy(router_id, message + 4, 8);
451 have_router_id = 1;
452 debugf(BABEL_DEBUG_COMMON,"Received router-id %s from %s on %s.",
453 format_eui64(router_id), format_address(from), ifp->name);
454 } else if(type == MESSAGE_NH) {
455 unsigned char nh[16];
456 int rc;
457 rc = network_address(message[2], message + 4, len - 2,
458 nh);
459 if(rc < 0) {
460 have_v4_nh = 0;
461 have_v6_nh = 0;
462 goto fail;
463 }
464 debugf(BABEL_DEBUG_COMMON,"Received nh %s (%d) from %s on %s.",
465 format_address(nh), message[2],
466 format_address(from), ifp->name);
467 if(message[2] == 1) {
468 memcpy(v4_nh, nh, 16);
469 have_v4_nh = 1;
470 } else {
471 memcpy(v6_nh, nh, 16);
472 have_v6_nh = 1;
473 }
474 } else if(type == MESSAGE_UPDATE) {
475 unsigned char prefix[16], *nh;
476 unsigned char plen;
477 unsigned char channels[DIVERSITY_HOPS];
478 unsigned short interval, seqno, metric;
479 int rc, parsed_len;
480 DO_NTOHS(interval, message + 6);
481 DO_NTOHS(seqno, message + 8);
482 DO_NTOHS(metric, message + 10);
483 if(message[5] == 0 ||
484 (message[2] == 1 ? have_v4_prefix : have_v6_prefix))
485 rc = network_prefix(message[2], message[4], message[5],
486 message + 12,
487 message[2] == 1 ? v4_prefix : v6_prefix,
488 len - 10, prefix);
489 else
490 rc = -1;
491 if(rc < 0) {
492 if(message[3] & 0x80)
493 have_v4_prefix = have_v6_prefix = 0;
494 goto fail;
495 }
496 parsed_len = 10 + rc;
497
498 plen = message[4] + (message[2] == 1 ? 96 : 0);
499
500 if(message[3] & 0x80) {
501 if(message[2] == 1) {
502 memcpy(v4_prefix, prefix, 16);
503 have_v4_prefix = 1;
504 } else {
505 memcpy(v6_prefix, prefix, 16);
506 have_v6_prefix = 1;
507 }
508 }
509 if(message[3] & 0x40) {
510 if(message[2] == 1) {
511 memset(router_id, 0, 4);
512 memcpy(router_id + 4, prefix + 12, 4);
513 } else {
514 memcpy(router_id, prefix + 8, 8);
515 }
516 have_router_id = 1;
517 }
518 if(!have_router_id && message[2] != 0) {
5b003f31 519 flog_err(EC_BABEL_PACKET,
e33b116c 520 "Received prefix with no router id.");
ca10883e
DS		 521 goto fail;
522 }
523 debugf(BABEL_DEBUG_COMMON,"Received update%s%s for %s from %s on %s.",
524 (message[3] & 0x80) ? "/prefix" : "",
525 (message[3] & 0x40) ? "/id" : "",
526 format_prefix(prefix, plen),
527 format_address(from), ifp->name);
528
529 if(message[2] == 0) {
530 if(metric < 0xFFFF) {
5b003f31 531 flog_err(EC_BABEL_PACKET,
e33b116c 532 "Received wildcard update with finite metric.");
ca10883e
DS		 533 goto done;
534 }
535 retract_neighbour_routes(neigh);
536 goto done;
537 } else if(message[2] == 1) {
538 if(!have_v4_nh)
539 goto fail;
540 nh = v4_nh;
541 } else if(have_v6_nh) {
542 nh = v6_nh;
543 } else {
544 nh = neigh->address;
545 }
546
547 if(message[2] == 1) {
548 if(!babel_get_if_nfo(ifp)->ipv4)
549 goto done;
550 }
551
552 if((babel_get_if_nfo(ifp)->flags & BABEL_IF_FARAWAY)) {
553 channels[0] = 0;
554 } else {
555 /* This will be overwritten by parse_update_subtlv below. */
556 if(metric < 256) {
557 /* Assume non-interfering (wired) link. */
558 channels[0] = 0;
559 } else {
560 /* Assume interfering. */
561 channels[0] = BABEL_IF_CHANNEL_INTERFERING;
562 channels[1] = 0;
563 }
564
565 if(parsed_len < len)
566 parse_update_subtlv(message + 2 + parsed_len,
567 len - parsed_len, channels);
568 }
569
570 update_route(router_id, prefix, plen, seqno, metric, interval,
571 neigh, nh,
572 channels, channels_len(channels));
573 } else if(type == MESSAGE_REQUEST) {
574 unsigned char prefix[16], plen;
575 int rc;
576 rc = network_prefix(message[2], message[3], 0,
577 message + 4, NULL, len - 2, prefix);
578 if(rc < 0) goto fail;
579 plen = message[3] + (message[2] == 1 ? 96 : 0);
580 debugf(BABEL_DEBUG_COMMON,"Received request for %s from %s on %s.",
581 message[2] == 0 ? "any" : format_prefix(prefix, plen),
582 format_address(from), ifp->name);
583 if(message[2] == 0) {
584 struct babel_interface *neigh_ifp =babel_get_if_nfo(neigh->ifp);
585 /* If a neighbour is requesting a full route dump from us,
586 we might as well send it an IHU. */
587 send_ihu(neigh, NULL);
588 /* Since nodes send wildcard requests on boot, booting
589 a large number of nodes at the same time may cause an
590 update storm. Ignore a wildcard request that happens
591 shortly after we sent a full update. */
592 if(neigh_ifp->last_update_time <
593 (time_t)(babel_now.tv_sec -
594 MAX(neigh_ifp->hello_interval / 100, 1)))
595 send_update(neigh->ifp, 0, NULL, 0);
596 } else {
597 send_update(neigh->ifp, 0, prefix, plen);
598 }
599 } else if(type == MESSAGE_MH_REQUEST) {
600 unsigned char prefix[16], plen;
601 unsigned short seqno;
602 int rc;
603 DO_NTOHS(seqno, message + 4);
604 rc = network_prefix(message[2], message[3], 0,
605 message + 16, NULL, len - 14, prefix);
606 if(rc < 0) goto fail;
607 plen = message[3] + (message[2] == 1 ? 96 : 0);
608 debugf(BABEL_DEBUG_COMMON,"Received request (%d) for %s from %s on %s (%s, %d).",
609 message[6],
610 format_prefix(prefix, plen),
611 format_address(from), ifp->name,
612 format_eui64(message + 8), seqno);
613 handle_request(neigh, prefix, plen, message[6],
614 seqno, message + 8);
615 } else {
616 debugf(BABEL_DEBUG_COMMON,"Received unknown packet type %d from %s on %s.",
617 type, format_address(from), ifp->name);
618 }
619 done:
620 i += len + 2;
621 continue;
622
623 fail:
5b003f31 624 flog_err(EC_BABEL_PACKET,
e33b116c
DS		 625 "Couldn't parse packet (%d, %d) from %s on %s.",
626 message[0], message[1], format_address(from), ifp->name);
ca10883e
DS		 627 goto done;
628 }
629
630 /* We can calculate the RTT to this neighbour. */
631 if(have_hello_rtt && hello_send_us && hello_rtt_receive_time) {
632 int remote_waiting_us, local_waiting_us;
633 unsigned int rtt, smoothed_rtt;
634 unsigned int old_rttcost;
635 int changed = 0;
636 remote_waiting_us = neigh->hello_send_us - hello_rtt_receive_time;
637 local_waiting_us = time_us(neigh->hello_rtt_receive_time) -
638 hello_send_us;
639
640 /* Sanity checks (validity window of 10 minutes). */
641 if(remote_waiting_us < 0 || local_waiting_us < 0 ||
642 remote_waiting_us > 600000000 || local_waiting_us > 600000000)
643 return;
644
645 rtt = MAX(0, local_waiting_us - remote_waiting_us);
646 debugf(BABEL_DEBUG_COMMON, "RTT to %s on %s sample result: %d us.\n",
647 format_address(from), ifp->name, rtt);
648
649 old_rttcost = neighbour_rttcost(neigh);
650 if (valid_rtt(neigh)) {
651 /* Running exponential average. */
652 smoothed_rtt = (babel_ifp->rtt_decay * rtt +
653 (256 - babel_ifp->rtt_decay) * neigh->rtt);
654 /* Rounding (up or down) to get closer to the sample. */
655 neigh->rtt = (neigh->rtt >= rtt) ? smoothed_rtt / 256 :
656 (smoothed_rtt + 255) / 256;
657 } else {
658 /* We prefer to be conservative with new neighbours
659 (higher RTT) */
660 assert(rtt <= 0x7FFFFFFF);
661 neigh->rtt = 2*rtt;
662 }
663 changed = (neighbour_rttcost(neigh) == old_rttcost ? 0 : 1);
664 update_neighbour_metric(neigh, changed);
665 neigh->rtt_time = babel_now;
666 }
667 return;
668}
669
670/* Under normal circumstances, there are enough moderation mechanisms
671 elsewhere in the protocol to make sure that this last-ditch check
672 should never trigger. But I'm superstitious. */
673
674static int
675check_bucket(struct interface *ifp)
676{
677 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
d11c6941 678 if(babel_ifp->bucket == 0) {
ca10883e
DS		 679 int seconds = babel_now.tv_sec - babel_ifp->bucket_time;
680 if(seconds > 0) {
681 babel_ifp->bucket = MIN(BUCKET_TOKENS_MAX,
682 seconds * BUCKET_TOKENS_PER_SEC);
683 }
684 /* Reset bucket time unconditionally, in case clock is stepped. */
685 babel_ifp->bucket_time = babel_now.tv_sec;
686 }
687
688 if(babel_ifp->bucket > 0) {
689 babel_ifp->bucket--;
690 return 1;
691 } else {
692 return 0;
693 }
694}
695
696static int
697fill_rtt_message(struct interface *ifp)
698{
699 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
700 if((babel_ifp->flags & BABEL_IF_TIMESTAMPS) &&
701 (babel_ifp->buffered_hello >= 0)) {
702 if(babel_ifp->sendbuf[babel_ifp->buffered_hello + 8] == SUBTLV_PADN &&
703 babel_ifp->sendbuf[babel_ifp->buffered_hello + 9] == 4) {
704 unsigned int time;
705 /* Change the type of sub-TLV. */
706 babel_ifp->sendbuf[babel_ifp->buffered_hello + 8] =
707 SUBTLV_TIMESTAMP;
708 gettime(&babel_now);
709 time = time_us(babel_now);
710 DO_HTONL(babel_ifp->sendbuf + babel_ifp->buffered_hello + 10, time);
711 return 1;
712 } else {
5b003f31 713 flog_err(EC_BABEL_PACKET, "No space left for timestamp sub-TLV "
ca10883e
DS		 714 "(this shouldn't happen)");
715 return -1;
716 }
717 }
718 return 0;
719}
720
721void
722flushbuf(struct interface *ifp)
723{
724 int rc;
725 struct sockaddr_in6 sin6;
726 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
727
728 assert(babel_ifp->buffered <= babel_ifp->bufsize);
729
730 flushupdates(ifp);
731
732 if(babel_ifp->buffered > 0) {
733 debugf(BABEL_DEBUG_COMMON," (flushing %d buffered bytes on %s)",
734 babel_ifp->buffered, ifp->name);
735 if(check_bucket(ifp)) {
736 memset(&sin6, 0, sizeof(sin6));
737 sin6.sin6_family = AF_INET6;
738 memcpy(&sin6.sin6_addr, protocol_group, 16);
739 sin6.sin6_port = htons(protocol_port);
740 sin6.sin6_scope_id = ifp->ifindex;
741 DO_HTONS(packet_header + 2, babel_ifp->buffered);
742 fill_rtt_message(ifp);
743 rc = babel_send(protocol_socket,
744 packet_header, sizeof(packet_header),
745 babel_ifp->sendbuf, babel_ifp->buffered,
746 (struct sockaddr*)&sin6, sizeof(sin6));
747 if(rc < 0)
5b003f31 748 flog_err(EC_BABEL_PACKET, "send: %s", safe_strerror(errno));
ca10883e 749 } else {
5b003f31 750 flog_err(EC_BABEL_PACKET,
e33b116c
DS		 751 "Warning: bucket full, dropping packet to %s.",
752 ifp->name);
ca10883e
DS		 753 }
754 }
755 VALGRIND_MAKE_MEM_UNDEFINED(babel_ifp->sendbuf, babel_ifp->bufsize);
756 babel_ifp->buffered = 0;
757 babel_ifp->buffered_hello = -1;
758 babel_ifp->have_buffered_id = 0;
759 babel_ifp->have_buffered_nh = 0;
760 babel_ifp->have_buffered_prefix = 0;
761 babel_ifp->flush_timeout.tv_sec = 0;
762 babel_ifp->flush_timeout.tv_usec = 0;
763}
764
765static void
766schedule_flush(struct interface *ifp)
767{
768 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
769 unsigned msecs = jitter(babel_ifp, 0);
770 if(babel_ifp->flush_timeout.tv_sec != 0 &&
771 timeval_minus_msec(&babel_ifp->flush_timeout, &babel_now) < msecs)
772 return;
773 set_timeout(&babel_ifp->flush_timeout, msecs);
774}
775
776static void
777schedule_flush_now(struct interface *ifp)
778{
779 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
780 /* Almost now */
781 unsigned msecs = roughly(10);
782 if(babel_ifp->flush_timeout.tv_sec != 0 &&
783 timeval_minus_msec(&babel_ifp->flush_timeout, &babel_now) < msecs)
784 return;
785 set_timeout(&babel_ifp->flush_timeout, msecs);
786}
787
788static void
789schedule_unicast_flush(unsigned msecs)
790{
791 if(!unicast_neighbour)
792 return;
793 if(unicast_flush_timeout.tv_sec != 0 &&
794 timeval_minus_msec(&unicast_flush_timeout, &babel_now) < msecs)
795 return;
796 unicast_flush_timeout.tv_usec = (babel_now.tv_usec + msecs * 1000) %1000000;
797 unicast_flush_timeout.tv_sec =
798 babel_now.tv_sec + (babel_now.tv_usec / 1000 + msecs) / 1000;
799}
800
801static void
802ensure_space(struct interface *ifp, int space)
803{
804 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
805 if(babel_ifp->bufsize - babel_ifp->buffered < space)
806 flushbuf(ifp);
807}
808
809static void
810start_message(struct interface *ifp, int type, int len)
811{
812 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
813 if(babel_ifp->bufsize - babel_ifp->buffered < len + 2)
814 flushbuf(ifp);
815 babel_ifp->sendbuf[babel_ifp->buffered++] = type;
816 babel_ifp->sendbuf[babel_ifp->buffered++] = len;
817}
818
819static void
820end_message(struct interface *ifp, int type, int bytes)
821{
822 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
823 assert(babel_ifp->buffered >= bytes + 2 &&
824 babel_ifp->sendbuf[babel_ifp->buffered - bytes - 2] == type &&
825 babel_ifp->sendbuf[babel_ifp->buffered - bytes - 1] == bytes);
826 schedule_flush(ifp);
827}
828
829static void
830accumulate_byte(struct interface *ifp, unsigned char value)
831{
832 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
833 babel_ifp->sendbuf[babel_ifp->buffered++] = value;
834}
835
836static void
837accumulate_short(struct interface *ifp, unsigned short value)
838{
839 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
840 DO_HTONS(babel_ifp->sendbuf + babel_ifp->buffered, value);
841 babel_ifp->buffered += 2;
842}
843
844static void
845accumulate_int(struct interface *ifp, unsigned int value)
846{
847 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
848 DO_HTONL(babel_ifp->sendbuf + babel_ifp->buffered, value);
849 babel_ifp->buffered += 4;
850}
851
852static void
853accumulate_bytes(struct interface *ifp,
854 const unsigned char *value, unsigned len)
855{
856 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
857 memcpy(babel_ifp->sendbuf + babel_ifp->buffered, value, len);
858 babel_ifp->buffered += len;
859}
860
861static int
862start_unicast_message(struct neighbour *neigh, int type, int len)
863{
864 if(unicast_neighbour) {
865 if(neigh != unicast_neighbour ||
866 unicast_buffered + len + 2 >=
867 MIN(UNICAST_BUFSIZE, babel_get_if_nfo(neigh->ifp)->bufsize))
868 flush_unicast(0);
869 }
870 if(!unicast_buffer)
871 unicast_buffer = malloc(UNICAST_BUFSIZE);
872 if(!unicast_buffer) {
5b003f31 873 flog_err(EC_BABEL_MEMORY, "malloc(unicast_buffer): %s",
e33b116c 874 safe_strerror(errno));
ca10883e
DS		 875 return -1;
876 }
877
878 unicast_neighbour = neigh;
879
880 unicast_buffer[unicast_buffered++] = type;
881 unicast_buffer[unicast_buffered++] = len;
882 return 1;
883}
884
885static void
886end_unicast_message(struct neighbour *neigh, int type, int bytes)
887{
888 assert(unicast_neighbour == neigh && unicast_buffered >= bytes + 2 &&
889 unicast_buffer[unicast_buffered - bytes - 2] == type &&
890 unicast_buffer[unicast_buffered - bytes - 1] == bytes);
891 schedule_unicast_flush(jitter(babel_get_if_nfo(neigh->ifp), 0));
892}
893
894static void
895accumulate_unicast_byte(struct neighbour *neigh, unsigned char value)
896{
897 unicast_buffer[unicast_buffered++] = value;
898}
899
900static void
901accumulate_unicast_short(struct neighbour *neigh, unsigned short value)
902{
903 DO_HTONS(unicast_buffer + unicast_buffered, value);
904 unicast_buffered += 2;
905}
906
907static void
908accumulate_unicast_int(struct neighbour *neigh, unsigned int value)
909{
910 DO_HTONL(unicast_buffer + unicast_buffered, value);
911 unicast_buffered += 4;
912}
913
914static void
915accumulate_unicast_bytes(struct neighbour *neigh,
916 const unsigned char *value, unsigned len)
917{
918 memcpy(unicast_buffer + unicast_buffered, value, len);
919 unicast_buffered += len;
920}
921
922void
923send_ack(struct neighbour *neigh, unsigned short nonce, unsigned short interval)
924{
925 int rc;
926 debugf(BABEL_DEBUG_COMMON,"Sending ack (%04x) to %s on %s.",
927 nonce, format_address(neigh->address), neigh->ifp->name);
928 rc = start_unicast_message(neigh, MESSAGE_ACK, 2); if(rc < 0) return;
929 accumulate_unicast_short(neigh, nonce);
930 end_unicast_message(neigh, MESSAGE_ACK, 2);
931 /* Roughly yields a value no larger than 3/2, so this meets the deadline */
932 schedule_unicast_flush(roughly(interval * 6));
933}
934
935void
936send_hello_noupdate(struct interface *ifp, unsigned interval)
937{
938 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
939 /* This avoids sending multiple hellos in a single packet, which breaks
940 link quality estimation. */
941 if(babel_ifp->buffered_hello >= 0)
942 flushbuf(ifp);
943
944 babel_ifp->hello_seqno = seqno_plus(babel_ifp->hello_seqno, 1);
945 set_timeout(&babel_ifp->hello_timeout, babel_ifp->hello_interval);
946
947 if(!if_up(ifp))
948 return;
949
950 debugf(BABEL_DEBUG_COMMON,"Sending hello %d (%d) to %s.",
951 babel_ifp->hello_seqno, interval, ifp->name);
952
953 start_message(ifp, MESSAGE_HELLO,
954 (babel_ifp->flags & BABEL_IF_TIMESTAMPS) ? 12 : 6);
955 babel_ifp->buffered_hello = babel_ifp->buffered - 2;
956 accumulate_short(ifp, 0);
957 accumulate_short(ifp, babel_ifp->hello_seqno);
958 accumulate_short(ifp, interval > 0xFFFF ? 0xFFFF : interval);
959 if(babel_ifp->flags & BABEL_IF_TIMESTAMPS) {
960 /* Sub-TLV containing the local time of emission. We use a
961 Pad4 sub-TLV, which we'll fill just before sending. */
962 accumulate_byte(ifp, SUBTLV_PADN);
963 accumulate_byte(ifp, 4);
964 accumulate_int(ifp, 0);
965 }
966 end_message(ifp, MESSAGE_HELLO,
967 (babel_ifp->flags & BABEL_IF_TIMESTAMPS) ? 12 : 6);
968}
969
970void
971send_hello(struct interface *ifp)
972{
973 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
974 send_hello_noupdate(ifp, (babel_ifp->hello_interval + 9) / 10);
975 /* Send full IHU every 3 hellos, and marginal IHU each time */
976 if(babel_ifp->hello_seqno % 3 == 0)
977 send_ihu(NULL, ifp);
978 else
979 send_marginal_ihu(ifp);
980}
981
982void
983flush_unicast(int dofree)
984{
985 struct sockaddr_in6 sin6;
986 int rc;
987
988 if(unicast_buffered == 0)
989 goto done;
990
991 if(!if_up(unicast_neighbour->ifp))
992 goto done;
993
994 /* Preserve ordering of messages */
995 flushbuf(unicast_neighbour->ifp);
996
997 if(check_bucket(unicast_neighbour->ifp)) {
998 memset(&sin6, 0, sizeof(sin6));
999 sin6.sin6_family = AF_INET6;
1000 memcpy(&sin6.sin6_addr, unicast_neighbour->address, 16);
1001 sin6.sin6_port = htons(protocol_port);
1002 sin6.sin6_scope_id = unicast_neighbour->ifp->ifindex;
1003 DO_HTONS(packet_header + 2, unicast_buffered);
1004 fill_rtt_message(unicast_neighbour->ifp);
1005 rc = babel_send(protocol_socket,
1006 packet_header, sizeof(packet_header),
1007 unicast_buffer, unicast_buffered,
1008 (struct sockaddr*)&sin6, sizeof(sin6));
1009 if(rc < 0)
5b003f31 1010 flog_err(EC_BABEL_PACKET, "send(unicast): %s",
e33b116c 1011 safe_strerror(errno));
ca10883e 1012 } else {
5b003f31 1013 flog_err(EC_BABEL_PACKET,
e33b116c
DS		 1014 "Warning: bucket full, dropping unicast packet to %s if %s.",
1015 format_address(unicast_neighbour->address),
1016 unicast_neighbour->ifp->name);
ca10883e
DS		 1017 }
1018
1019 done:
1020 VALGRIND_MAKE_MEM_UNDEFINED(unicast_buffer, UNICAST_BUFSIZE);
1021 unicast_buffered = 0;
1022 if(dofree && unicast_buffer) {
1023 free(unicast_buffer);
1024 unicast_buffer = NULL;
1025 }
1026 unicast_neighbour = NULL;
1027 unicast_flush_timeout.tv_sec = 0;
1028 unicast_flush_timeout.tv_usec = 0;
1029}
1030
1031static void
1032really_send_update(struct interface *ifp,
1033 const unsigned char *id,
1034 const unsigned char *prefix, unsigned char plen,
1035 unsigned short seqno, unsigned short metric,
1036 unsigned char *channels, int channels_len)
1037{
1038 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
1039 int add_metric, v4, real_plen, omit = 0;
1040 const unsigned char *real_prefix;
1041 unsigned short flags = 0;
1042 int channels_size;
1043
1044 if(diversity_kind != DIVERSITY_CHANNEL)
1045 channels_len = -1;
1046
1047 channels_size = channels_len >= 0 ? channels_len + 2 : 0;
1048
1049 if(!if_up(ifp))
1050 return;
1051
1052 add_metric = output_filter(id, prefix, plen, ifp->ifindex);
1053 if(add_metric >= INFINITY)
1054 return;
1055
1056 metric = MIN(metric + add_metric, INFINITY);
1057 /* Worst case */
1058 ensure_space(ifp, 20 + 12 + 28);
1059
1060 v4 = plen >= 96 && v4mapped(prefix);
1061
1062 if(v4) {
1063 if(!babel_ifp->ipv4)
1064 return;
1065 if(!babel_ifp->have_buffered_nh ||
1066 memcmp(babel_ifp->buffered_nh, babel_ifp->ipv4, 4) != 0) {
1067 start_message(ifp, MESSAGE_NH, 6);
1068 accumulate_byte(ifp, 1);
1069 accumulate_byte(ifp, 0);
1070 accumulate_bytes(ifp, babel_ifp->ipv4, 4);
1071 end_message(ifp, MESSAGE_NH, 6);
1072 memcpy(babel_ifp->buffered_nh, babel_ifp->ipv4, 4);
1073 babel_ifp->have_buffered_nh = 1;
1074 }
1075
1076 real_prefix = prefix + 12;
1077 real_plen = plen - 96;
1078 } else {
1079 if(babel_ifp->have_buffered_prefix) {
1080 while(omit < plen / 8 &&
1081 babel_ifp->buffered_prefix[omit] == prefix[omit])
1082 omit++;
1083 }
1084 if(!babel_ifp->have_buffered_prefix || plen >= 48)
1085 flags |= 0x80;
1086 real_prefix = prefix;
1087 real_plen = plen;
1088 }
1089
1090 if(!babel_ifp->have_buffered_id
1091 || memcmp(id, babel_ifp->buffered_id, 8) != 0) {
1092 if(real_plen == 128 && memcmp(real_prefix + 8, id, 8) == 0) {
1093 flags |= 0x40;
1094 } else {
1095 start_message(ifp, MESSAGE_ROUTER_ID, 10);
1096 accumulate_short(ifp, 0);
1097 accumulate_bytes(ifp, id, 8);
1098 end_message(ifp, MESSAGE_ROUTER_ID, 10);
1099 }
01b08f09 1100 memcpy(babel_ifp->buffered_id, id, sizeof(babel_ifp->buffered_id));
ca10883e
DS		 1101 babel_ifp->have_buffered_id = 1;
1102 }
1103
1104 start_message(ifp, MESSAGE_UPDATE, 10 + (real_plen + 7) / 8 - omit +
1105 channels_size);
1106 accumulate_byte(ifp, v4 ? 1 : 2);
1107 accumulate_byte(ifp, flags);
1108 accumulate_byte(ifp, real_plen);
1109 accumulate_byte(ifp, omit);
1110 accumulate_short(ifp, (babel_ifp->update_interval + 5) / 10);
1111 accumulate_short(ifp, seqno);
1112 accumulate_short(ifp, metric);
1113 accumulate_bytes(ifp, real_prefix + omit, (real_plen + 7) / 8 - omit);
1114 /* Note that an empty channels TLV is different from no such TLV. */
1115 if(channels_len >= 0) {
1116 accumulate_byte(ifp, 2);
1117 accumulate_byte(ifp, channels_len);
fa3bf3a2
MS		 1118
1119 if (channels && channels_len > 0)
1120 accumulate_bytes(ifp, channels, channels_len);
ca10883e
DS		 1121 }
1122 end_message(ifp, MESSAGE_UPDATE, 10 + (real_plen + 7) / 8 - omit +
1123 channels_size);
1124
1125 if(flags & 0x80) {
1126 memcpy(babel_ifp->buffered_prefix, prefix, 16);
1127 babel_ifp->have_buffered_prefix = 1;
1128 }
1129}
1130
1131static int
1132compare_buffered_updates(const void *av, const void *bv)
1133{
1134 const struct buffered_update *a = av, *b = bv;
1135 int rc, v4a, v4b, ma, mb;
1136
1137 rc = memcmp(a->id, b->id, 8);
1138 if(rc != 0)
1139 return rc;
1140
1141 v4a = (a->plen >= 96 && v4mapped(a->prefix));
1142 v4b = (b->plen >= 96 && v4mapped(b->prefix));
1143
1144 if(v4a > v4b)
1145 return 1;
1146 else if(v4a < v4b)
1147 return -1;
1148
1149 ma = (!v4a && a->plen == 128 && memcmp(a->prefix + 8, a->id, 8) == 0);
1150 mb = (!v4b && b->plen == 128 && memcmp(b->prefix + 8, b->id, 8) == 0);
1151
1152 if(ma > mb)
1153 return -1;
1154 else if(mb > ma)
1155 return 1;
1156
1157 if(a->plen < b->plen)
1158 return 1;
1159 else if(a->plen > b->plen)
1160 return -1;
1161
1162 return memcmp(a->prefix, b->prefix, 16);
1163}
1164
1165void
1166flushupdates(struct interface *ifp)
1167{
1168 babel_interface_nfo *babel_ifp = NULL;
1169 struct xroute *xroute;
1170 struct babel_route *route;
1171 const unsigned char *last_prefix = NULL;
1172 unsigned char last_plen = 0xFF;
1173 int i;
1174
1175 if(ifp == NULL) {
f4e14fdb
RW		 1176 struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
1177 struct interface *ifp_aux;
1178 FOR_ALL_INTERFACES(vrf, ifp_aux)
ca10883e
DS		 1179 flushupdates(ifp_aux);
1180 return;
1181 }
1182
1183 babel_ifp = babel_get_if_nfo(ifp);
1184 if(babel_ifp->num_buffered_updates > 0) {
1185 struct buffered_update *b = babel_ifp->buffered_updates;
1186 int n = babel_ifp->num_buffered_updates;
1187
1188 babel_ifp->buffered_updates = NULL;
1189 babel_ifp->update_bufsize = 0;
1190 babel_ifp->num_buffered_updates = 0;
1191
1192 if(!if_up(ifp))
1193 goto done;
1194
1195 debugf(BABEL_DEBUG_COMMON," (flushing %d buffered updates on %s (%d))",
1196 n, ifp->name, ifp->ifindex);
1197
1198 /* In order to send fewer update messages, we want to send updates
1199 with the same router-id together, with IPv6 going out before IPv4. */
1200
1201 for(i = 0; i < n; i++) {
1202 route = find_installed_route(b[i].prefix, b[i].plen);
1203 if(route)
1204 memcpy(b[i].id, route->src->id, 8);
1205 else
1206 memcpy(b[i].id, myid, 8);
1207 }
1208
1209 qsort(b, n, sizeof(struct buffered_update), compare_buffered_updates);
1210
1211 for(i = 0; i < n; i++) {
1212 /* The same update may be scheduled multiple times before it is
1213 sent out. Since our buffer is now sorted, it is enough to
1214 compare with the previous update. */
1215
1216 if(last_prefix) {
1217 if(b[i].plen == last_plen &&
1218 memcmp(b[i].prefix, last_prefix, 16) == 0)
1219 continue;
1220 }
1221
1222 xroute = find_xroute(b[i].prefix, b[i].plen);
1223 route = find_installed_route(b[i].prefix, b[i].plen);
1224
1225 if(xroute && (!route || xroute->metric <= kernel_metric)) {
1226 really_send_update(ifp, myid,
1227 xroute->prefix, xroute->plen,
1228 myseqno, xroute->metric,
1229 NULL, 0);
1230 last_prefix = xroute->prefix;
1231 last_plen = xroute->plen;
1232 } else if(route) {
1233 unsigned char channels[DIVERSITY_HOPS];
1234 int chlen;
1235 struct interface *route_ifp = route->neigh->ifp;
1236 struct babel_interface *babel_route_ifp = NULL;
1237 unsigned short metric;
1238 unsigned short seqno;
1239
1240 seqno = route->seqno;
1241 metric =
1242 route_interferes(route, ifp) ?
1243 route_metric(route) :
1244 route_metric_noninterfering(route);
1245
1246 if(metric < INFINITY)
1247 satisfy_request(route->src->prefix, route->src->plen,
1248 seqno, route->src->id, ifp);
1249 if((babel_ifp->flags & BABEL_IF_SPLIT_HORIZON) &&
1250 route->neigh->ifp == ifp)
1251 continue;
1252
1253 babel_route_ifp = babel_get_if_nfo(route_ifp);
1254 if(babel_route_ifp->channel ==BABEL_IF_CHANNEL_NONINTERFERING) {
1255 memcpy(channels, route->channels, DIVERSITY_HOPS);
1256 } else {
1257 if(babel_route_ifp->channel == BABEL_IF_CHANNEL_UNKNOWN)
1258 channels[0] = BABEL_IF_CHANNEL_INTERFERING;
1259 else {
1260 assert(babel_route_ifp->channel > 0 &&
1261 babel_route_ifp->channel <= 255);
1262 channels[0] = babel_route_ifp->channel;
1263 }
1264 memcpy(channels + 1, route->channels, DIVERSITY_HOPS - 1);
1265 }
1266
1267 chlen = channels_len(channels);
1268 really_send_update(ifp, route->src->id,
1269 route->src->prefix,
1270 route->src->plen,
1271 seqno, metric,
1272 channels, chlen);
1273 update_source(route->src, seqno, metric);
1274 last_prefix = route->src->prefix;
1275 last_plen = route->src->plen;
1276 } else {
1277 /* There's no route for this prefix. This can happen shortly
1278 after an xroute has been retracted, so send a retraction. */
1279 really_send_update(ifp, myid, b[i].prefix, b[i].plen,
1280 myseqno, INFINITY, NULL, -1);
1281 }
1282 }
1283 schedule_flush_now(ifp);
1284 done:
1285 free(b);
1286 }
1287 babel_ifp->update_flush_timeout.tv_sec = 0;
1288 babel_ifp->update_flush_timeout.tv_usec = 0;
1289}
1290
1291static void
1292schedule_update_flush(struct interface *ifp, int urgent)
1293{
1294 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
1295 unsigned msecs;
1296 msecs = update_jitter(babel_ifp, urgent);
1297 if(babel_ifp->update_flush_timeout.tv_sec != 0 &&
1298 timeval_minus_msec(&babel_ifp->update_flush_timeout, &babel_now) < msecs)
1299 return;
1300 set_timeout(&babel_ifp->update_flush_timeout, msecs);
1301}
1302
1303static void
1304buffer_update(struct interface *ifp,
1305 const unsigned char *prefix, unsigned char plen)
1306{
1307 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
1308 if(babel_ifp->num_buffered_updates > 0 &&
1309 babel_ifp->num_buffered_updates >= babel_ifp->update_bufsize)
1310 flushupdates(ifp);
1311
1312 if(babel_ifp->update_bufsize == 0) {
1313 int n;
1314 assert(babel_ifp->buffered_updates == NULL);
1315 /* Allocate enough space to hold a full update. Since the
1316 number of installed routes will grow over time, make sure we
1317 have enough space to send a full-ish frame. */
1318 n = installed_routes_estimate() + xroutes_estimate() + 4;
1319 n = MAX(n, babel_ifp->bufsize / 16);
1320 again:
1321 babel_ifp->buffered_updates = malloc(n *sizeof(struct buffered_update));
1322 if(babel_ifp->buffered_updates == NULL) {
5b003f31 1323 flog_err(EC_BABEL_MEMORY, "malloc(buffered_updates): %s",
e33b116c 1324 safe_strerror(errno));
ca10883e
DS		 1325 if(n > 4) {
1326 /* Try again with a tiny buffer. */
1327 n = 4;
1328 goto again;
1329 }
1330 return;
1331 }
1332 babel_ifp->update_bufsize = n;
1333 babel_ifp->num_buffered_updates = 0;
1334 }
1335
1336 memcpy(babel_ifp->buffered_updates[babel_ifp->num_buffered_updates].prefix,
1337 prefix, 16);
1338 babel_ifp->buffered_updates[babel_ifp->num_buffered_updates].plen = plen;
1339 babel_ifp->num_buffered_updates++;
1340}
1341
1342void
1343send_update(struct interface *ifp, int urgent,
1344 const unsigned char *prefix, unsigned char plen)
1345{
1346 babel_interface_nfo *babel_ifp = NULL;
1347
1348 if(ifp == NULL) {
f4e14fdb
RW		 1349 struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
1350 struct interface *ifp_aux;
ca10883e 1351 struct babel_route *route;
f4e14fdb 1352 FOR_ALL_INTERFACES(vrf, ifp_aux)
ca10883e
DS		 1353 send_update(ifp_aux, urgent, prefix, plen);
1354 if(prefix) {
1355 /* Since flushupdates only deals with non-wildcard interfaces, we
1356 need to do this now. */
1357 route = find_installed_route(prefix, plen);
1358 if(route && route_metric(route) < INFINITY)
1359 satisfy_request(prefix, plen, route->src->seqno, route->src->id,
1360 NULL);
1361 }
1362 return;
1363 }
1364
1365 if(!if_up(ifp))
1366 return;
1367
1368 babel_ifp = babel_get_if_nfo(ifp);
1369 if(prefix) {
1370 debugf(BABEL_DEBUG_COMMON,"Sending update to %s for %s.",
1371 ifp->name, format_prefix(prefix, plen));
1372 buffer_update(ifp, prefix, plen);
1373 } else {
1374 struct route_stream *routes = NULL;
1375 send_self_update(ifp);
1376 debugf(BABEL_DEBUG_COMMON,"Sending update to %s for any.", ifp->name);
1377 routes = route_stream(1);
1378 if(routes) {
1379 while(1) {
1380 struct babel_route *route = route_stream_next(routes);
1381 if(route == NULL)
1382 break;
1383 buffer_update(ifp, route->src->prefix, route->src->plen);
1384 }
1385 route_stream_done(routes);
1386 } else {
5b003f31 1387 flog_err(EC_BABEL_MEMORY, "Couldn't allocate route stream.");
ca10883e
DS		 1388 }
1389 set_timeout(&babel_ifp->update_timeout, babel_ifp->update_interval);
1390 babel_ifp->last_update_time = babel_now.tv_sec;
1391 }
1392 schedule_update_flush(ifp, urgent);
1393}
1394
1395void
1396send_update_resend(struct interface *ifp,
1397 const unsigned char *prefix, unsigned char plen)
1398{
1399 assert(prefix != NULL);
1400
1401 send_update(ifp, 1, prefix, plen);
1402 record_resend(RESEND_UPDATE, prefix, plen, 0, NULL, NULL, resend_delay);
1403}
1404
1405void
1406send_wildcard_retraction(struct interface *ifp)
1407{
1408 babel_interface_nfo *babel_ifp = NULL;
1409 if(ifp == NULL) {
f4e14fdb
RW		 1410 struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
1411 struct interface *ifp_aux;
1412 FOR_ALL_INTERFACES(vrf, ifp_aux)
ca10883e
DS		 1413 send_wildcard_retraction(ifp_aux);
1414 return;
1415 }
1416
1417 if(!if_up(ifp))
1418 return;
1419
1420 babel_ifp = babel_get_if_nfo(ifp);
1421 start_message(ifp, MESSAGE_UPDATE, 10);
1422 accumulate_byte(ifp, 0);
1423 accumulate_byte(ifp, 0x40);
1424 accumulate_byte(ifp, 0);
1425 accumulate_byte(ifp, 0);
1426 accumulate_short(ifp, 0xFFFF);
1427 accumulate_short(ifp, myseqno);
1428 accumulate_short(ifp, 0xFFFF);
1429 end_message(ifp, MESSAGE_UPDATE, 10);
1430
1431 babel_ifp->have_buffered_id = 0;
1432}
1433
1434void
4d762f26 1435update_myseqno(void)
ca10883e
DS		 1436{
1437 myseqno = seqno_plus(myseqno, 1);
1438}
1439
1440void
1441send_self_update(struct interface *ifp)
1442{
1443 struct xroute_stream *xroutes;
1444 if(ifp == NULL) {
f4e14fdb
RW		 1445 struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
1446 struct interface *ifp_aux;
1447 FOR_ALL_INTERFACES(vrf, ifp_aux) {
ca10883e
DS		 1448 if(!if_up(ifp_aux))
1449 continue;
1450 send_self_update(ifp_aux);
1451 }
1452 return;
1453 }
1454
1455 debugf(BABEL_DEBUG_COMMON,"Sending self update to %s.", ifp->name);
1456 xroutes = xroute_stream();
1457 if(xroutes) {
1458 while(1) {
1459 struct xroute *xroute = xroute_stream_next(xroutes);
1460 if(xroute == NULL) break;
1461 send_update(ifp, 0, xroute->prefix, xroute->plen);
1462 }
1463 xroute_stream_done(xroutes);
1464 } else {
5b003f31 1465 flog_err(EC_BABEL_MEMORY, "Couldn't allocate xroute stream.");
ca10883e
DS		 1466 }
1467}
1468
1469void
1470send_ihu(struct neighbour *neigh, struct interface *ifp)
1471{
1472 babel_interface_nfo *babel_ifp = NULL;
1473 int rxcost, interval;
1474 int ll;
1475 int send_rtt_data;
1476 int msglen;
1477
1478 if(neigh == NULL && ifp == NULL) {
f4e14fdb 1479 struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
ca10883e 1480 struct interface *ifp_aux;
f4e14fdb 1481 FOR_ALL_INTERFACES(vrf, ifp_aux) {
ca10883e
DS		 1482 if(if_up(ifp_aux))
1483 continue;
1484 send_ihu(NULL, ifp_aux);
1485 }
1486 return;
1487 }
1488
1489 if(neigh == NULL) {
1490 struct neighbour *ngh;
1491 FOR_ALL_NEIGHBOURS(ngh) {
1492 if(ngh->ifp == ifp)
1493 send_ihu(ngh, ifp);
1494 }
1495 return;
1496 }
1497
1498
1499 if(ifp && neigh->ifp != ifp)
1500 return;
1501
1502 ifp = neigh->ifp;
1503 babel_ifp = babel_get_if_nfo(ifp);
1504 if(!if_up(ifp))
1505 return;
1506
1507 rxcost = neighbour_rxcost(neigh);
1508 interval = (babel_ifp->hello_interval * 3 + 9) / 10;
1509
1510 /* Conceptually, an IHU is a unicast message. We usually send them as
1511 multicast, since this allows aggregation into a single packet and
1512 avoids an ARP exchange. If we already have a unicast message queued
1513 for this neighbour, however, we might as well piggyback the IHU. */
1514 debugf(BABEL_DEBUG_COMMON,"Sending %sihu %d on %s to %s.",
1515 unicast_neighbour == neigh ? "unicast " : "",
1516 rxcost,
1517 neigh->ifp->name,
1518 format_address(neigh->address));
1519
1520 ll = linklocal(neigh->address);
1521
1522 if((babel_ifp->flags & BABEL_IF_TIMESTAMPS) && neigh->hello_send_us
1523 /* Checks whether the RTT data is not too old to be sent. */
1524 && timeval_minus_msec(&babel_now,
1525 &neigh->hello_rtt_receive_time) < 1000000) {
1526 send_rtt_data = 1;
1527 } else {
1528 neigh->hello_send_us = 0;
1529 send_rtt_data = 0;
1530 }
1531
1532 /* The length depends on the format of the address, and then an
1533 optional 10-bytes sub-TLV for timestamps (used to compute a RTT). */
1534 msglen = (ll ? 14 : 22) + (send_rtt_data ? 10 : 0);
1535
1536 if(unicast_neighbour != neigh) {
1537 start_message(ifp, MESSAGE_IHU, msglen);
1538 accumulate_byte(ifp, ll ? 3 : 2);
1539 accumulate_byte(ifp, 0);
1540 accumulate_short(ifp, rxcost);
1541 accumulate_short(ifp, interval);
1542 if(ll)
1543 accumulate_bytes(ifp, neigh->address + 8, 8);
1544 else
1545 accumulate_bytes(ifp, neigh->address, 16);
1546 if (send_rtt_data) {
1547 accumulate_byte(ifp, SUBTLV_TIMESTAMP);
1548 accumulate_byte(ifp, 8);
1549 accumulate_int(ifp, neigh->hello_send_us);
1550 accumulate_int(ifp, time_us(neigh->hello_rtt_receive_time));
1551 }
1552 end_message(ifp, MESSAGE_IHU, msglen);
1553 } else {
1554 int rc;
1555 rc = start_unicast_message(neigh, MESSAGE_IHU, msglen);
1556 if(rc < 0) return;
1557 accumulate_unicast_byte(neigh, ll ? 3 : 2);
1558 accumulate_unicast_byte(neigh, 0);
1559 accumulate_unicast_short(neigh, rxcost);
1560 accumulate_unicast_short(neigh, interval);
1561 if(ll)
1562 accumulate_unicast_bytes(neigh, neigh->address + 8, 8);
1563 else
1564 accumulate_unicast_bytes(neigh, neigh->address, 16);
1565 if (send_rtt_data) {
1566 accumulate_unicast_byte(neigh, SUBTLV_TIMESTAMP);
1567 accumulate_unicast_byte(neigh, 8);
1568 accumulate_unicast_int(neigh, neigh->hello_send_us);
1569 accumulate_unicast_int(neigh,
1570 time_us(neigh->hello_rtt_receive_time));
1571 }
1572 end_unicast_message(neigh, MESSAGE_IHU, msglen);
1573 }
1574}
1575
1576/* Send IHUs to all marginal neighbours */
1577void
1578send_marginal_ihu(struct interface *ifp)
1579{
1580 struct neighbour *neigh;
1581 FOR_ALL_NEIGHBOURS(neigh) {
1582 if(ifp && neigh->ifp != ifp)
1583 continue;
1584 if(neigh->txcost >= 384 || (neigh->reach & 0xF000) != 0xF000)
1585 send_ihu(neigh, ifp);
1586 }
1587}
1588
1589void
1590send_request(struct interface *ifp,
1591 const unsigned char *prefix, unsigned char plen)
1592{
1593 int v4, pb, len;
1594
1595 if(ifp == NULL) {
f4e14fdb
RW		 1596 struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
1597 struct interface *ifp_aux;
1598 FOR_ALL_INTERFACES(vrf, ifp_aux) {
ca10883e
DS		 1599 if(if_up(ifp_aux))
1600 continue;
1601 send_request(ifp_aux, prefix, plen);
1602 }
1603 return;
1604 }
1605
1606 /* make sure any buffered updates go out before this request. */
1607 flushupdates(ifp);
1608
1609 if(!if_up(ifp))
1610 return;
1611
1612 debugf(BABEL_DEBUG_COMMON,"sending request to %s for %s.",
1613 ifp->name, prefix ? format_prefix(prefix, plen) : "any");
1614 v4 = plen >= 96 && v4mapped(prefix);
1615 pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
1616 len = !prefix ? 2 : 2 + pb;
1617
1618 start_message(ifp, MESSAGE_REQUEST, len);
1619 accumulate_byte(ifp, !prefix ? 0 : v4 ? 1 : 2);
1620 accumulate_byte(ifp, !prefix ? 0 : v4 ? plen - 96 : plen);
1621 if(prefix) {
1622 if(v4)
1623 accumulate_bytes(ifp, prefix + 12, pb);
1624 else
1625 accumulate_bytes(ifp, prefix, pb);
1626 }
1627 end_message(ifp, MESSAGE_REQUEST, len);
1628}
1629
1630void
1631send_unicast_request(struct neighbour *neigh,
1632 const unsigned char *prefix, unsigned char plen)
1633{
1634 int rc, v4, pb, len;
1635
1636 /* make sure any buffered updates go out before this request. */
1637 flushupdates(neigh->ifp);
1638
1639 debugf(BABEL_DEBUG_COMMON,"sending unicast request to %s for %s.",
1640 format_address(neigh->address),
1641 prefix ? format_prefix(prefix, plen) : "any");
1642 v4 = plen >= 96 && v4mapped(prefix);
1643 pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
1644 len = !prefix ? 2 : 2 + pb;
1645
1646 rc = start_unicast_message(neigh, MESSAGE_REQUEST, len);
1647 if(rc < 0) return;
1648 accumulate_unicast_byte(neigh, !prefix ? 0 : v4 ? 1 : 2);
1649 accumulate_unicast_byte(neigh, !prefix ? 0 : v4 ? plen - 96 : plen);
1650 if(prefix) {
1651 if(v4)
1652 accumulate_unicast_bytes(neigh, prefix + 12, pb);
1653 else
1654 accumulate_unicast_bytes(neigh, prefix, pb);
1655 }
1656 end_unicast_message(neigh, MESSAGE_REQUEST, len);
1657}
1658
1659void
1660send_multihop_request(struct interface *ifp,
1661 const unsigned char *prefix, unsigned char plen,
1662 unsigned short seqno, const unsigned char *id,
1663 unsigned short hop_count)
1664{
1665 int v4, pb, len;
1666
1667 /* Make sure any buffered updates go out before this request. */
1668 flushupdates(ifp);
1669
1670 if(ifp == NULL) {
f4e14fdb
RW		 1671 struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
1672 struct interface *ifp_aux;
1673 FOR_ALL_INTERFACES(vrf, ifp_aux) {
ca10883e
DS		 1674 if(!if_up(ifp_aux))
1675 continue;
1676 send_multihop_request(ifp_aux, prefix, plen, seqno, id, hop_count);
1677 }
1678 return;
1679 }
1680
1681 if(!if_up(ifp))
1682 return;
1683
1684 debugf(BABEL_DEBUG_COMMON,"Sending request (%d) on %s for %s.",
1685 hop_count, ifp->name, format_prefix(prefix, plen));
1686 v4 = plen >= 96 && v4mapped(prefix);
1687 pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
1688 len = 6 + 8 + pb;
1689
1690 start_message(ifp, MESSAGE_MH_REQUEST, len);
1691 accumulate_byte(ifp, v4 ? 1 : 2);
1692 accumulate_byte(ifp, v4 ? plen - 96 : plen);
1693 accumulate_short(ifp, seqno);
1694 accumulate_byte(ifp, hop_count);
1695 accumulate_byte(ifp, 0);
1696 accumulate_bytes(ifp, id, 8);
1697 if(prefix) {
1698 if(v4)
1699 accumulate_bytes(ifp, prefix + 12, pb);
1700 else
1701 accumulate_bytes(ifp, prefix, pb);
1702 }
1703 end_message(ifp, MESSAGE_MH_REQUEST, len);
1704}
1705
1706void
1707send_unicast_multihop_request(struct neighbour *neigh,
1708 const unsigned char *prefix, unsigned char plen,
1709 unsigned short seqno, const unsigned char *id,
1710 unsigned short hop_count)
1711{
1712 int rc, v4, pb, len;
1713
1714 /* Make sure any buffered updates go out before this request. */
1715 flushupdates(neigh->ifp);
1716
1717 debugf(BABEL_DEBUG_COMMON,"Sending multi-hop request to %s for %s (%d hops).",
1718 format_address(neigh->address),
1719 format_prefix(prefix, plen), hop_count);
1720 v4 = plen >= 96 && v4mapped(prefix);
1721 pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
1722 len = 6 + 8 + pb;
1723
1724 rc = start_unicast_message(neigh, MESSAGE_MH_REQUEST, len);
1725 if(rc < 0) return;
1726 accumulate_unicast_byte(neigh, v4 ? 1 : 2);
1727 accumulate_unicast_byte(neigh, v4 ? plen - 96 : plen);
1728 accumulate_unicast_short(neigh, seqno);
1729 accumulate_unicast_byte(neigh, hop_count);
1730 accumulate_unicast_byte(neigh, 0);
1731 accumulate_unicast_bytes(neigh, id, 8);
1732 if(prefix) {
1733 if(v4)
1734 accumulate_unicast_bytes(neigh, prefix + 12, pb);
1735 else
1736 accumulate_unicast_bytes(neigh, prefix, pb);
1737 }
1738 end_unicast_message(neigh, MESSAGE_MH_REQUEST, len);
1739}
1740
1741void
1742send_request_resend(struct neighbour *neigh,
1743 const unsigned char *prefix, unsigned char plen,
1744 unsigned short seqno, unsigned char *id)
1745{
1746 if(neigh)
1747 send_unicast_multihop_request(neigh, prefix, plen, seqno, id, 127);
1748 else
1749 send_multihop_request(NULL, prefix, plen, seqno, id, 127);
1750
1751 record_resend(RESEND_REQUEST, prefix, plen, seqno, id,
1752 neigh ? neigh->ifp : NULL, resend_delay);
1753}
1754
1755void
1756handle_request(struct neighbour *neigh, const unsigned char *prefix,
1757 unsigned char plen, unsigned char hop_count,
1758 unsigned short seqno, const unsigned char *id)
1759{
1760 struct xroute *xroute;
1761 struct babel_route *route;
1762 struct neighbour *successor = NULL;
1763
1764 xroute = find_xroute(prefix, plen);
1765 route = find_installed_route(prefix, plen);
1766
1767 if(xroute && (!route || xroute->metric <= kernel_metric)) {
1768 if(hop_count > 0 && memcmp(id, myid, 8) == 0) {
1769 if(seqno_compare(seqno, myseqno) > 0) {
1770 if(seqno_minus(seqno, myseqno) > 100) {
1771 /* Hopelessly out-of-date request */
1772 return;
1773 }
1774 update_myseqno();
1775 }
1776 }
1777 send_update(neigh->ifp, 1, prefix, plen);
1778 return;
1779 }
1780
1781 if(route &&
1782 (memcmp(id, route->src->id, 8) != 0 ||
1783 seqno_compare(seqno, route->seqno) <= 0)) {
1784 send_update(neigh->ifp, 1, prefix, plen);
1785 return;
1786 }
1787
1788 if(hop_count <= 1)
1789 return;
1790
1791 if(route && memcmp(id, route->src->id, 8) == 0 &&
1792 seqno_minus(seqno, route->seqno) > 100) {
1793 /* Hopelessly out-of-date */
1794 return;
1795 }
1796
1797 if(request_redundant(neigh->ifp, prefix, plen, seqno, id))
1798 return;
1799
1800 /* Let's try to forward this request. */
1801 if(route && route_metric(route) < INFINITY)
1802 successor = route->neigh;
1803
1804 if(!successor || successor == neigh) {
1805 /* We were about to forward a request to its requestor. Try to
1806 find a different neighbour to forward the request to. */
1807 struct babel_route *other_route;
1808
1809 other_route = find_best_route(prefix, plen, 0, neigh);
1810 if(other_route && route_metric(other_route) < INFINITY)
1811 successor = other_route->neigh;
1812 }
1813
1814 if(!successor || successor == neigh)
1815 /* Give up */
1816 return;
1817
1818 send_unicast_multihop_request(successor, prefix, plen, seqno, id,
1819 hop_count - 1);
1820 record_resend(RESEND_REQUEST, prefix, plen, seqno, id,
1821 neigh->ifp, 0);
1822}
FRRouting mirror