2 Copyright (c) 2007, 2008 by Juliusz Chroboczek
4 Permission is hereby granted, free of charge, to any person obtaining a copy
5 of this software and associated documentation files (the "Software"), to deal
6 in the Software without restriction, including without limitation the rights
7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 copies of the Software, and to permit persons to whom the Software is
9 furnished to do so, subject to the following conditions:
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
29 #include "babel_interface.h"
31 #include "neighbour.h"
37 #include "babel_main.h"
38 #include "babel_errors.h"
40 static unsigned char packet_header
[4] = {42, 2};
42 int split_horizon
= 1;
44 unsigned short myseqno
= 0;
46 #define UNICAST_BUFSIZE 1024
47 static int unicast_buffered
= 0;
48 static unsigned char *unicast_buffer
= NULL
;
49 struct neighbour
*unicast_neighbour
= NULL
;
50 struct timeval unicast_flush_timeout
= {0, 0};
52 /* Minimum TLV _body_ length for TLVs of particular types (0 = no limit). */
53 static const unsigned char tlv_min_length
[MESSAGE_MAX
+ 1] =
57 [ MESSAGE_ACK_REQ
] = 6,
59 [ MESSAGE_HELLO
] = 6,
61 [ MESSAGE_ROUTER_ID
] = 10,
63 [ MESSAGE_UPDATE
] = 10,
64 [ MESSAGE_REQUEST
] = 2,
65 [ MESSAGE_MH_REQUEST
] = 14,
68 /* Parse a network prefix, encoded in the somewhat baroque compressed
69 representation used by Babel. Return the number of bytes parsed. */
71 network_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
)
76 unsigned char prefix
[16];
89 memset(prefix
, 0, 16);
96 if(omitted
> 4 || pb
> 4 || (pb
> omitted
&& len
< pb
- omitted
))
98 memcpy(prefix
, v4prefix
, 12);
100 if (dp
== NULL
|| !v4mapped(dp
)) return -1;
101 memcpy(prefix
, dp
, 12 + omitted
);
103 if(pb
> omitted
) memcpy(prefix
+ 12 + omitted
, p
, pb
- omitted
);
107 if(omitted
> 16 || (pb
> omitted
&& len
< pb
- omitted
)) return -1;
109 if (dp
== NULL
|| v4mapped(dp
)) return -1;
110 memcpy(prefix
, dp
, omitted
);
112 if(pb
> omitted
) memcpy(prefix
+ omitted
, p
, pb
- omitted
);
116 if(pb
> 8 && len
< pb
- 8) return -1;
119 if(pb
> 8) memcpy(prefix
+ 8, p
, pb
- 8);
126 mask_prefix(p_r
, prefix
, plen
< 0 ? 128 : ae
== 1 ? plen
+ 96 : plen
);
130 static bool parse_update_subtlv(const unsigned char *a
, int alen
,
131 unsigned char *channels
)
133 int type
, len
, i
= 0;
137 if(type
== SUBTLV_PAD1
) {
143 flog_err(EC_BABEL_PACKET
, "Received truncated attributes.");
147 if(i
+ len
+ 2 > alen
) {
148 flog_err(EC_BABEL_PACKET
, "Received truncated attributes.");
152 if (type
& SUBTLV_MANDATORY
) {
155 * If the mandatory bit is set, then the whole enclosing
156 * TLV MUST be silently ignored (except for updating the
157 * parser state by a Router-Id, Next Hop, or Update TLV,
158 * as described in the next section).
160 debugf(BABEL_DEBUG_COMMON
,
161 "Received Mandatory bit set but this FRR version is not prepared to handle it at this point");
163 } else if (type
== SUBTLV_PADN
) {
165 } else if (type
== SUBTLV_DIVERSITY
) {
166 if (len
> DIVERSITY_HOPS
) {
169 "Received overlong channel information (%d > %d).n",
170 len
, DIVERSITY_HOPS
);
171 len
= DIVERSITY_HOPS
;
173 if (memchr(a
+ i
+ 2, 0, len
) != NULL
) {
175 flog_err(EC_BABEL_PACKET
,
176 "Channel information contains 0!");
179 memset(channels
, 0, DIVERSITY_HOPS
);
180 memcpy(channels
, a
+ i
+ 2, len
);
182 debugf(BABEL_DEBUG_COMMON
,
183 "Received unknown route attribute %d.", type
);
192 parse_hello_subtlv(const unsigned char *a
, int alen
,
193 unsigned int *hello_send_us
)
195 int type
, len
, i
= 0, ret
= 0;
199 if(type
== SUBTLV_PAD1
) {
205 flog_err(EC_BABEL_PACKET
,
206 "Received truncated sub-TLV on Hello message.");
210 if(i
+ len
+ 2 > alen
) {
211 flog_err(EC_BABEL_PACKET
,
212 "Received truncated sub-TLV on Hello message.");
216 if (type
& SUBTLV_MANDATORY
) {
219 * If the mandatory bit is set, then the whole enclosing
220 * TLV MUST be silently ignored (except for updating the
221 * parser state by a Router-Id, Next Hop, or Update TLV, as
222 * described in the next section).
224 debugf(BABEL_DEBUG_COMMON
,
225 "Received subtlv with Mandatory bit, this version of FRR is not prepared to handle this currently");
227 } else if (type
== SUBTLV_PADN
) {
229 } else if (type
== SUBTLV_TIMESTAMP
) {
231 DO_NTOHL(*hello_send_us
, a
+ i
+ 2);
236 "Received incorrect RTT sub-TLV on Hello message.");
239 debugf(BABEL_DEBUG_COMMON
,
240 "Received unknown Hello sub-TLV type %d.", type
);
249 parse_ihu_subtlv(const unsigned char *a
, int alen
,
250 unsigned int *hello_send_us
,
251 unsigned int *hello_rtt_receive_time
)
253 int type
, len
, i
= 0, ret
= 0;
257 if(type
== SUBTLV_PAD1
) {
263 flog_err(EC_BABEL_PACKET
,
264 "Received truncated sub-TLV on IHU message.");
268 if(i
+ len
+ 2 > alen
) {
269 flog_err(EC_BABEL_PACKET
,
270 "Received truncated sub-TLV on IHU message.");
274 if(type
== SUBTLV_PADN
) {
276 } else if(type
== SUBTLV_TIMESTAMP
) {
278 DO_NTOHL(*hello_send_us
, a
+ i
+ 2);
279 DO_NTOHL(*hello_rtt_receive_time
, a
+ i
+ 6);
283 flog_err(EC_BABEL_PACKET
,
284 "Received incorrect RTT sub-TLV on IHU message.");
287 debugf(BABEL_DEBUG_COMMON
,
288 "Received unknown IHU sub-TLV type %d.", type
);
297 network_address(int ae
, const unsigned char *a
, unsigned int len
,
300 return network_prefix(ae
, -1, 0, a
, NULL
, len
, a_r
);
304 channels_len(unsigned char *channels
)
306 unsigned char *p
= memchr(channels
, 0, DIVERSITY_HOPS
);
307 return p
? (p
- channels
) : DIVERSITY_HOPS
;
310 /* Check, that the provided frame consists of a valid Babel packet header
311 followed by a sequence of TLVs. TLVs of known types are also checked to meet
312 minimum length constraints defined for each. Return 0 for no errors. */
314 babel_packet_examin(const unsigned char *packet
, int packetlen
, int *blength
)
317 const unsigned char *message
;
318 unsigned char type
, len
;
320 if(packetlen
< 4 || packet
[0] != 42 || packet
[1] != 2)
322 DO_NTOHS(bodylen
, packet
+ 2);
323 if(bodylen
+ 4 > packetlen
) {
324 debugf(BABEL_DEBUG_COMMON
, "Received truncated packet (%d + 4 > %d).",
329 message
= packet
+ 4 + i
;
331 if(type
== MESSAGE_PAD1
) {
335 if(i
+ 2 > bodylen
) {
336 debugf(BABEL_DEBUG_COMMON
,"Received truncated message.");
340 if(i
+ len
+ 2 > bodylen
) {
341 debugf(BABEL_DEBUG_COMMON
,"Received truncated message.");
345 if(type
<= MESSAGE_MAX
&& tlv_min_length
[type
] && len
< tlv_min_length
[type
]) {
346 debugf(BABEL_DEBUG_COMMON
,"Undersized %u TLV", type
);
357 parse_packet(const unsigned char *from
, struct interface
*ifp
,
358 const unsigned char *packet
, int packetlen
)
361 const unsigned char *message
;
362 unsigned char type
, len
;
364 struct neighbour
*neigh
;
365 int have_router_id
= 0, have_v4_prefix
= 0, have_v6_prefix
= 0,
366 have_v4_nh
= 0, have_v6_nh
= 0;
367 unsigned char router_id
[8], v4_prefix
[16], v6_prefix
[16],
368 v4_nh
[16], v6_nh
[16];
369 int have_hello_rtt
= 0;
370 /* Content of the RTT sub-TLV on IHU messages. */
371 unsigned int hello_send_us
= 0, hello_rtt_receive_time
= 0;
372 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
374 if(babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) {
375 /* We want to track exactly when we received this packet. */
379 if(!linklocal(from
)) {
380 flog_err(EC_BABEL_PACKET
,
381 "Received packet from non-local address %s.",
382 format_address(from
));
386 if (babel_packet_examin (packet
, packetlen
, &bodylen
)) {
387 flog_err(EC_BABEL_PACKET
,
388 "Received malformed packet on %s from %s.",
389 ifp
->name
, format_address(from
));
393 neigh
= find_neighbour(from
, ifp
);
395 flog_err(EC_BABEL_PACKET
, "Couldn't allocate neighbour.");
401 message
= packet
+ 4 + i
;
403 if(type
== MESSAGE_PAD1
) {
404 debugf(BABEL_DEBUG_COMMON
,"Received pad1 from %s on %s.",
405 format_address(from
), ifp
->name
);
411 if(type
== MESSAGE_PADN
) {
412 debugf(BABEL_DEBUG_COMMON
,"Received pad%d from %s on %s.",
413 len
, format_address(from
), ifp
->name
);
414 } else if(type
== MESSAGE_ACK_REQ
) {
415 unsigned short nonce
, interval
;
416 DO_NTOHS(nonce
, message
+ 4);
417 DO_NTOHS(interval
, message
+ 6);
418 debugf(BABEL_DEBUG_COMMON
,"Received ack-req (%04X %d) from %s on %s.",
419 nonce
, interval
, format_address(from
), ifp
->name
);
420 send_ack(neigh
, nonce
, interval
);
421 } else if(type
== MESSAGE_ACK
) {
422 debugf(BABEL_DEBUG_COMMON
,"Received ack from %s on %s.",
423 format_address(from
), ifp
->name
);
424 /* Nothing right now */
425 } else if(type
== MESSAGE_HELLO
) {
426 unsigned short seqno
, interval
, flags
;
428 unsigned int timestamp
= 0;
430 #define BABEL_UNICAST_HELLO 0x8000
431 DO_NTOHS(flags
, message
+ 2);
435 * All other bits MUST be sent as a 0 and silently
436 * ignored on reception
438 if (CHECK_FLAG(flags
, ~BABEL_UNICAST_HELLO
)) {
439 debugf(BABEL_DEBUG_COMMON
,
440 "Received Hello from %s on %s that does not have all 0's in the unused section of flags, ignoring",
441 format_address(from
), ifp
->name
);
446 * RFC 8966 Appendix F
447 * TL;DR -> Please ignore Unicast hellos until FRR's
448 * BABEL is brought up to date
450 if (CHECK_FLAG(flags
, BABEL_UNICAST_HELLO
)) {
451 debugf(BABEL_DEBUG_COMMON
,
452 "Received Unicast Hello from %s on %s that FRR is not prepared to understand yet",
453 format_address(from
), ifp
->name
);
457 DO_NTOHS(seqno
, message
+ 4);
458 DO_NTOHS(interval
, message
+ 6);
459 debugf(BABEL_DEBUG_COMMON
,
460 "Received hello %d (%d) from %s on %s.", seqno
, interval
,
461 format_address(from
), ifp
->name
);
464 * RFC 8966 Appendix F
465 * TL;DR -> Please ignore any Hello packets with the interval
469 debugf(BABEL_DEBUG_COMMON
,
470 "Received hello from %s on %s should be ignored as that this version of FRR does not know how to properly handle interval == 0",
471 format_address(from
), ifp
->name
);
475 changed
= update_neighbour(neigh
, seqno
, interval
);
476 update_neighbour_metric(neigh
, changed
);
478 /* Multiply by 3/2 to allow hellos to expire. */
479 schedule_neighbours_check(interval
* 15, 0);
480 /* Sub-TLV handling. */
482 if (parse_hello_subtlv(message
+ 8, len
- 6,
484 neigh
->hello_send_us
= timestamp
;
485 neigh
->hello_rtt_receive_time
= babel_now
;
489 } else if(type
== MESSAGE_IHU
) {
490 unsigned short txcost
, interval
;
491 unsigned char address
[16];
493 DO_NTOHS(txcost
, message
+ 4);
494 DO_NTOHS(interval
, message
+ 6);
495 rc
= network_address(message
[2], message
+ 8, len
- 6, address
);
496 if(rc
< 0) goto fail
;
497 debugf(BABEL_DEBUG_COMMON
,"Received ihu %d (%d) from %s on %s for %s.",
499 format_address(from
), ifp
->name
,
500 format_address(address
));
501 if(message
[2] == 0 || is_interface_ll_address(ifp
, address
)) {
502 int changed
= txcost
!= neigh
->txcost
;
503 neigh
->txcost
= txcost
;
504 neigh
->ihu_time
= babel_now
;
505 neigh
->ihu_interval
= interval
;
506 update_neighbour_metric(neigh
, changed
);
508 /* Multiply by 3/2 to allow neighbours to expire. */
509 schedule_neighbours_check(interval
* 45, 0);
512 parse_ihu_subtlv(message
+ 8 + rc
, len
- 6 - rc
,
513 &hello_send_us
, &hello_rtt_receive_time
);
515 } else if(type
== MESSAGE_ROUTER_ID
) {
516 memcpy(router_id
, message
+ 4, 8);
518 debugf(BABEL_DEBUG_COMMON
,"Received router-id %s from %s on %s.",
519 format_eui64(router_id
), format_address(from
), ifp
->name
);
520 } else if(type
== MESSAGE_NH
) {
521 unsigned char nh
[16];
523 rc
= network_address(message
[2], message
+ 4, len
- 2,
530 debugf(BABEL_DEBUG_COMMON
,"Received nh %s (%d) from %s on %s.",
531 format_address(nh
), message
[2],
532 format_address(from
), ifp
->name
);
533 if(message
[2] == 1) {
534 memcpy(v4_nh
, nh
, 16);
537 memcpy(v6_nh
, nh
, 16);
540 } else if(type
== MESSAGE_UPDATE
) {
541 unsigned char prefix
[16], *nh
;
543 unsigned char channels
[DIVERSITY_HOPS
];
544 unsigned short interval
, seqno
, metric
;
546 bool ignore_update
= false;
548 DO_NTOHS(interval
, message
+ 6);
549 DO_NTOHS(seqno
, message
+ 8);
550 DO_NTOHS(metric
, message
+ 10);
551 if(message
[5] == 0 ||
552 (message
[2] == 1 ? have_v4_prefix
: have_v6_prefix
))
553 rc
= network_prefix(message
[2], message
[4], message
[5],
555 message
[2] == 1 ? v4_prefix
: v6_prefix
,
560 if(message
[3] & 0x80)
561 have_v4_prefix
= have_v6_prefix
= 0;
564 parsed_len
= 10 + rc
;
566 plen
= message
[4] + (message
[2] == 1 ? 96 : 0);
568 if(message
[3] & 0x80) {
569 if(message
[2] == 1) {
570 memcpy(v4_prefix
, prefix
, 16);
573 memcpy(v6_prefix
, prefix
, 16);
577 if(message
[3] & 0x40) {
578 if(message
[2] == 1) {
579 memset(router_id
, 0, 4);
580 memcpy(router_id
+ 4, prefix
+ 12, 4);
582 memcpy(router_id
, prefix
+ 8, 8);
586 if(!have_router_id
&& message
[2] != 0) {
587 flog_err(EC_BABEL_PACKET
,
588 "Received prefix with no router id.");
591 debugf(BABEL_DEBUG_COMMON
,"Received update%s%s for %s from %s on %s.",
592 (message
[3] & 0x80) ? "/prefix" : "",
593 (message
[3] & 0x40) ? "/id" : "",
594 format_prefix(prefix
, plen
),
595 format_address(from
), ifp
->name
);
597 if(message
[2] == 0) {
598 if(metric
< 0xFFFF) {
599 flog_err(EC_BABEL_PACKET
,
600 "Received wildcard update with finite metric.");
603 retract_neighbour_routes(neigh
);
605 } else if(message
[2] == 1) {
609 } else if(have_v6_nh
) {
615 if(message
[2] == 1) {
616 if(!babel_get_if_nfo(ifp
)->ipv4
)
620 if((babel_get_if_nfo(ifp
)->flags
& BABEL_IF_FARAWAY
)) {
623 /* This will be overwritten by parse_update_subtlv below. */
625 /* Assume non-interfering (wired) link. */
628 /* Assume interfering. */
629 channels
[0] = BABEL_IF_CHANNEL_INTERFERING
;
635 parse_update_subtlv(message
+ 2 + parsed_len
,
636 len
- parsed_len
, channels
);
640 update_route(router_id
, prefix
, plen
, seqno
, metric
,
641 interval
, neigh
, nh
, channels
,
642 channels_len(channels
));
643 } else if(type
== MESSAGE_REQUEST
) {
644 unsigned char prefix
[16], plen
;
646 rc
= network_prefix(message
[2], message
[3], 0,
647 message
+ 4, NULL
, len
- 2, prefix
);
648 if(rc
< 0) goto fail
;
649 plen
= message
[3] + (message
[2] == 1 ? 96 : 0);
650 debugf(BABEL_DEBUG_COMMON
,"Received request for %s from %s on %s.",
651 message
[2] == 0 ? "any" : format_prefix(prefix
, plen
),
652 format_address(from
), ifp
->name
);
653 if(message
[2] == 0) {
654 struct babel_interface
*neigh_ifp
=babel_get_if_nfo(neigh
->ifp
);
655 /* If a neighbour is requesting a full route dump from us,
656 we might as well send it an IHU. */
657 send_ihu(neigh
, NULL
);
658 /* Since nodes send wildcard requests on boot, booting
659 a large number of nodes at the same time may cause an
660 update storm. Ignore a wildcard request that happens
661 shortly after we sent a full update. */
662 if(neigh_ifp
->last_update_time
<
663 (time_t)(babel_now
.tv_sec
-
664 MAX(neigh_ifp
->hello_interval
/ 100, 1)))
665 send_update(neigh
->ifp
, 0, NULL
, 0);
667 send_update(neigh
->ifp
, 0, prefix
, plen
);
669 } else if(type
== MESSAGE_MH_REQUEST
) {
670 unsigned char prefix
[16], plen
;
671 unsigned short seqno
;
673 DO_NTOHS(seqno
, message
+ 4);
674 rc
= network_prefix(message
[2], message
[3], 0,
675 message
+ 16, NULL
, len
- 14, prefix
);
676 if(rc
< 0) goto fail
;
677 plen
= message
[3] + (message
[2] == 1 ? 96 : 0);
678 debugf(BABEL_DEBUG_COMMON
,"Received request (%d) for %s from %s on %s (%s, %d).",
680 format_prefix(prefix
, plen
),
681 format_address(from
), ifp
->name
,
682 format_eui64(message
+ 8), seqno
);
683 handle_request(neigh
, prefix
, plen
, message
[6],
686 debugf(BABEL_DEBUG_COMMON
,"Received unknown packet type %d from %s on %s.",
687 type
, format_address(from
), ifp
->name
);
694 flog_err(EC_BABEL_PACKET
,
695 "Couldn't parse packet (%d, %d) from %s on %s.",
696 message
[0], message
[1], format_address(from
), ifp
->name
);
700 /* We can calculate the RTT to this neighbour. */
701 if(have_hello_rtt
&& hello_send_us
&& hello_rtt_receive_time
) {
702 int remote_waiting_us
, local_waiting_us
;
703 unsigned int rtt
, smoothed_rtt
;
704 unsigned int old_rttcost
;
706 remote_waiting_us
= neigh
->hello_send_us
- hello_rtt_receive_time
;
707 local_waiting_us
= time_us(neigh
->hello_rtt_receive_time
) -
710 /* Sanity checks (validity window of 10 minutes). */
711 if(remote_waiting_us
< 0 || local_waiting_us
< 0 ||
712 remote_waiting_us
> 600000000 || local_waiting_us
> 600000000)
715 rtt
= MAX(0, local_waiting_us
- remote_waiting_us
);
716 debugf(BABEL_DEBUG_COMMON
, "RTT to %s on %s sample result: %d us.",
717 format_address(from
), ifp
->name
, rtt
);
719 old_rttcost
= neighbour_rttcost(neigh
);
720 if (valid_rtt(neigh
)) {
721 /* Running exponential average. */
722 smoothed_rtt
= (babel_ifp
->rtt_decay
* rtt
+
723 (256 - babel_ifp
->rtt_decay
) * neigh
->rtt
);
724 /* Rounding (up or down) to get closer to the sample. */
725 neigh
->rtt
= (neigh
->rtt
>= rtt
) ? smoothed_rtt
/ 256 :
726 (smoothed_rtt
+ 255) / 256;
728 /* We prefer to be conservative with new neighbours
730 assert(rtt
<= 0x7FFFFFFF);
733 changed
= (neighbour_rttcost(neigh
) == old_rttcost
? 0 : 1);
734 update_neighbour_metric(neigh
, changed
);
735 neigh
->rtt_time
= babel_now
;
740 /* Under normal circumstances, there are enough moderation mechanisms
741 elsewhere in the protocol to make sure that this last-ditch check
742 should never trigger. But I'm superstitious. */
745 check_bucket(struct interface
*ifp
)
747 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
748 if(babel_ifp
->bucket
== 0) {
749 int seconds
= babel_now
.tv_sec
- babel_ifp
->bucket_time
;
751 babel_ifp
->bucket
= MIN(BUCKET_TOKENS_MAX
,
752 seconds
* BUCKET_TOKENS_PER_SEC
);
754 /* Reset bucket time unconditionally, in case clock is stepped. */
755 babel_ifp
->bucket_time
= babel_now
.tv_sec
;
758 if(babel_ifp
->bucket
> 0) {
767 fill_rtt_message(struct interface
*ifp
)
769 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
770 if((babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) &&
771 (babel_ifp
->buffered_hello
>= 0)) {
772 if(babel_ifp
->sendbuf
[babel_ifp
->buffered_hello
+ 8] == SUBTLV_PADN
&&
773 babel_ifp
->sendbuf
[babel_ifp
->buffered_hello
+ 9] == 4) {
775 /* Change the type of sub-TLV. */
776 babel_ifp
->sendbuf
[babel_ifp
->buffered_hello
+ 8] =
779 time
= time_us(babel_now
);
780 DO_HTONL(babel_ifp
->sendbuf
+ babel_ifp
->buffered_hello
+ 10, time
);
783 flog_err(EC_BABEL_PACKET
, "No space left for timestamp sub-TLV (this shouldn't happen)");
791 flushbuf(struct interface
*ifp
)
794 struct sockaddr_in6 sin6
;
795 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
797 assert(babel_ifp
->buffered
<= babel_ifp
->bufsize
);
801 if(babel_ifp
->buffered
> 0) {
802 debugf(BABEL_DEBUG_COMMON
," (flushing %d buffered bytes on %s)",
803 babel_ifp
->buffered
, ifp
->name
);
804 if(check_bucket(ifp
)) {
805 memset(&sin6
, 0, sizeof(sin6
));
806 sin6
.sin6_family
= AF_INET6
;
807 memcpy(&sin6
.sin6_addr
, protocol_group
, 16);
808 sin6
.sin6_port
= htons(protocol_port
);
809 sin6
.sin6_scope_id
= ifp
->ifindex
;
810 DO_HTONS(packet_header
+ 2, babel_ifp
->buffered
);
811 fill_rtt_message(ifp
);
812 rc
= babel_send(protocol_socket
,
813 packet_header
, sizeof(packet_header
),
814 babel_ifp
->sendbuf
, babel_ifp
->buffered
,
815 (struct sockaddr
*)&sin6
, sizeof(sin6
));
817 flog_err(EC_BABEL_PACKET
, "send: %s", safe_strerror(errno
));
819 flog_err(EC_BABEL_PACKET
, "Bucket full, dropping packet to %s.",
823 VALGRIND_MAKE_MEM_UNDEFINED(babel_ifp
->sendbuf
, babel_ifp
->bufsize
);
824 babel_ifp
->buffered
= 0;
825 babel_ifp
->buffered_hello
= -1;
826 babel_ifp
->have_buffered_id
= 0;
827 babel_ifp
->have_buffered_nh
= 0;
828 babel_ifp
->have_buffered_prefix
= 0;
829 babel_ifp
->flush_timeout
.tv_sec
= 0;
830 babel_ifp
->flush_timeout
.tv_usec
= 0;
834 schedule_flush(struct interface
*ifp
)
836 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
837 unsigned msecs
= jitter(babel_ifp
, 0);
838 if(babel_ifp
->flush_timeout
.tv_sec
!= 0 &&
839 timeval_minus_msec(&babel_ifp
->flush_timeout
, &babel_now
) < msecs
)
841 set_timeout(&babel_ifp
->flush_timeout
, msecs
);
845 schedule_flush_now(struct interface
*ifp
)
847 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
849 unsigned msecs
= roughly(10);
850 if(babel_ifp
->flush_timeout
.tv_sec
!= 0 &&
851 timeval_minus_msec(&babel_ifp
->flush_timeout
, &babel_now
) < msecs
)
853 set_timeout(&babel_ifp
->flush_timeout
, msecs
);
857 schedule_unicast_flush(unsigned msecs
)
859 if(!unicast_neighbour
)
861 if(unicast_flush_timeout
.tv_sec
!= 0 &&
862 timeval_minus_msec(&unicast_flush_timeout
, &babel_now
) < msecs
)
864 unicast_flush_timeout
.tv_usec
= (babel_now
.tv_usec
+ msecs
* 1000) %1000000;
865 unicast_flush_timeout
.tv_sec
=
866 babel_now
.tv_sec
+ (babel_now
.tv_usec
/ 1000 + msecs
) / 1000;
870 ensure_space(struct interface
*ifp
, int space
)
872 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
873 if(babel_ifp
->bufsize
- babel_ifp
->buffered
< space
)
878 start_message(struct interface
*ifp
, int type
, int len
)
880 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
881 if(babel_ifp
->bufsize
- babel_ifp
->buffered
< len
+ 2)
883 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = type
;
884 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = len
;
888 end_message(struct interface
*ifp
, int type
, int bytes
)
890 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
891 assert(babel_ifp
->buffered
>= bytes
+ 2 &&
892 babel_ifp
->sendbuf
[babel_ifp
->buffered
- bytes
- 2] == type
&&
893 babel_ifp
->sendbuf
[babel_ifp
->buffered
- bytes
- 1] == bytes
);
898 accumulate_byte(struct interface
*ifp
, unsigned char value
)
900 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
901 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = value
;
905 accumulate_short(struct interface
*ifp
, unsigned short value
)
907 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
908 DO_HTONS(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
);
909 babel_ifp
->buffered
+= 2;
913 accumulate_int(struct interface
*ifp
, unsigned int value
)
915 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
916 DO_HTONL(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
);
917 babel_ifp
->buffered
+= 4;
921 accumulate_bytes(struct interface
*ifp
,
922 const unsigned char *value
, unsigned len
)
924 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
925 memcpy(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
, len
);
926 babel_ifp
->buffered
+= len
;
930 start_unicast_message(struct neighbour
*neigh
, int type
, int len
)
932 if(unicast_neighbour
) {
933 if(neigh
!= unicast_neighbour
||
934 unicast_buffered
+ len
+ 2 >=
935 MIN(UNICAST_BUFSIZE
, babel_get_if_nfo(neigh
->ifp
)->bufsize
))
939 unicast_buffer
= malloc(UNICAST_BUFSIZE
);
940 if(!unicast_buffer
) {
941 flog_err(EC_BABEL_MEMORY
, "malloc(unicast_buffer): %s",
942 safe_strerror(errno
));
946 unicast_neighbour
= neigh
;
948 unicast_buffer
[unicast_buffered
++] = type
;
949 unicast_buffer
[unicast_buffered
++] = len
;
954 end_unicast_message(struct neighbour
*neigh
, int type
, int bytes
)
956 assert(unicast_neighbour
== neigh
&& unicast_buffered
>= bytes
+ 2 &&
957 unicast_buffer
[unicast_buffered
- bytes
- 2] == type
&&
958 unicast_buffer
[unicast_buffered
- bytes
- 1] == bytes
);
959 schedule_unicast_flush(jitter(babel_get_if_nfo(neigh
->ifp
), 0));
963 accumulate_unicast_byte(struct neighbour
*neigh
, unsigned char value
)
965 unicast_buffer
[unicast_buffered
++] = value
;
969 accumulate_unicast_short(struct neighbour
*neigh
, unsigned short value
)
971 DO_HTONS(unicast_buffer
+ unicast_buffered
, value
);
972 unicast_buffered
+= 2;
976 accumulate_unicast_int(struct neighbour
*neigh
, unsigned int value
)
978 DO_HTONL(unicast_buffer
+ unicast_buffered
, value
);
979 unicast_buffered
+= 4;
983 accumulate_unicast_bytes(struct neighbour
*neigh
,
984 const unsigned char *value
, unsigned len
)
986 memcpy(unicast_buffer
+ unicast_buffered
, value
, len
);
987 unicast_buffered
+= len
;
991 send_ack(struct neighbour
*neigh
, unsigned short nonce
, unsigned short interval
)
994 debugf(BABEL_DEBUG_COMMON
,"Sending ack (%04x) to %s on %s.",
995 nonce
, format_address(neigh
->address
), neigh
->ifp
->name
);
996 rc
= start_unicast_message(neigh
, MESSAGE_ACK
, 2); if(rc
< 0) return;
997 accumulate_unicast_short(neigh
, nonce
);
998 end_unicast_message(neigh
, MESSAGE_ACK
, 2);
999 /* Roughly yields a value no larger than 3/2, so this meets the deadline */
1000 schedule_unicast_flush(roughly(interval
* 6));
1004 send_hello_noupdate(struct interface
*ifp
, unsigned interval
)
1006 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1007 /* This avoids sending multiple hellos in a single packet, which breaks
1008 link quality estimation. */
1009 if(babel_ifp
->buffered_hello
>= 0)
1012 babel_ifp
->hello_seqno
= seqno_plus(babel_ifp
->hello_seqno
, 1);
1013 set_timeout(&babel_ifp
->hello_timeout
, babel_ifp
->hello_interval
);
1018 debugf(BABEL_DEBUG_COMMON
,"Sending hello %d (%d) to %s.",
1019 babel_ifp
->hello_seqno
, interval
, ifp
->name
);
1021 start_message(ifp
, MESSAGE_HELLO
,
1022 (babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) ? 12 : 6);
1023 babel_ifp
->buffered_hello
= babel_ifp
->buffered
- 2;
1024 accumulate_short(ifp
, 0);
1025 accumulate_short(ifp
, babel_ifp
->hello_seqno
);
1026 accumulate_short(ifp
, interval
> 0xFFFF ? 0xFFFF : interval
);
1027 if(babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) {
1028 /* Sub-TLV containing the local time of emission. We use a
1029 Pad4 sub-TLV, which we'll fill just before sending. */
1030 accumulate_byte(ifp
, SUBTLV_PADN
);
1031 accumulate_byte(ifp
, 4);
1032 accumulate_int(ifp
, 0);
1034 end_message(ifp
, MESSAGE_HELLO
,
1035 (babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) ? 12 : 6);
1039 send_hello(struct interface
*ifp
)
1041 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1042 send_hello_noupdate(ifp
, (babel_ifp
->hello_interval
+ 9) / 10);
1043 /* Send full IHU every 3 hellos, and marginal IHU each time */
1044 if(babel_ifp
->hello_seqno
% 3 == 0)
1045 send_ihu(NULL
, ifp
);
1047 send_marginal_ihu(ifp
);
1051 flush_unicast(int dofree
)
1053 struct sockaddr_in6 sin6
;
1056 if(unicast_buffered
== 0)
1059 if(!if_up(unicast_neighbour
->ifp
))
1062 /* Preserve ordering of messages */
1063 flushbuf(unicast_neighbour
->ifp
);
1065 if(check_bucket(unicast_neighbour
->ifp
)) {
1066 memset(&sin6
, 0, sizeof(sin6
));
1067 sin6
.sin6_family
= AF_INET6
;
1068 memcpy(&sin6
.sin6_addr
, unicast_neighbour
->address
, 16);
1069 sin6
.sin6_port
= htons(protocol_port
);
1070 sin6
.sin6_scope_id
= unicast_neighbour
->ifp
->ifindex
;
1071 DO_HTONS(packet_header
+ 2, unicast_buffered
);
1072 fill_rtt_message(unicast_neighbour
->ifp
);
1073 rc
= babel_send(protocol_socket
,
1074 packet_header
, sizeof(packet_header
),
1075 unicast_buffer
, unicast_buffered
,
1076 (struct sockaddr
*)&sin6
, sizeof(sin6
));
1078 flog_err(EC_BABEL_PACKET
, "send(unicast): %s",
1079 safe_strerror(errno
));
1081 flog_err(EC_BABEL_PACKET
,
1082 "Bucket full, dropping unicast packet to %s if %s.",
1083 format_address(unicast_neighbour
->address
),
1084 unicast_neighbour
->ifp
->name
);
1088 VALGRIND_MAKE_MEM_UNDEFINED(unicast_buffer
, UNICAST_BUFSIZE
);
1089 unicast_buffered
= 0;
1090 if(dofree
&& unicast_buffer
) {
1091 free(unicast_buffer
);
1092 unicast_buffer
= NULL
;
1094 unicast_neighbour
= NULL
;
1095 unicast_flush_timeout
.tv_sec
= 0;
1096 unicast_flush_timeout
.tv_usec
= 0;
1100 really_send_update(struct interface
*ifp
,
1101 const unsigned char *id
,
1102 const unsigned char *prefix
, unsigned char plen
,
1103 unsigned short seqno
, unsigned short metric
,
1104 unsigned char *channels
, int channels_len
)
1106 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1107 int add_metric
, v4
, real_plen
, omit
= 0;
1108 const unsigned char *real_prefix
;
1109 unsigned short flags
= 0;
1112 if(diversity_kind
!= DIVERSITY_CHANNEL
)
1115 channels_size
= channels_len
>= 0 ? channels_len
+ 2 : 0;
1120 add_metric
= output_filter(id
, prefix
, plen
, ifp
->ifindex
);
1121 if(add_metric
>= INFINITY
)
1124 metric
= MIN(metric
+ add_metric
, INFINITY
);
1126 ensure_space(ifp
, 20 + 12 + 28);
1128 v4
= plen
>= 96 && v4mapped(prefix
);
1131 if(!babel_ifp
->ipv4
)
1133 if(!babel_ifp
->have_buffered_nh
||
1134 memcmp(babel_ifp
->buffered_nh
, babel_ifp
->ipv4
, 4) != 0) {
1135 start_message(ifp
, MESSAGE_NH
, 6);
1136 accumulate_byte(ifp
, 1);
1137 accumulate_byte(ifp
, 0);
1138 accumulate_bytes(ifp
, babel_ifp
->ipv4
, 4);
1139 end_message(ifp
, MESSAGE_NH
, 6);
1140 memcpy(babel_ifp
->buffered_nh
, babel_ifp
->ipv4
, 4);
1141 babel_ifp
->have_buffered_nh
= 1;
1144 real_prefix
= prefix
+ 12;
1145 real_plen
= plen
- 96;
1147 if(babel_ifp
->have_buffered_prefix
) {
1148 while(omit
< plen
/ 8 &&
1149 babel_ifp
->buffered_prefix
[omit
] == prefix
[omit
])
1152 if(!babel_ifp
->have_buffered_prefix
|| plen
>= 48)
1154 real_prefix
= prefix
;
1158 if(!babel_ifp
->have_buffered_id
1159 || memcmp(id
, babel_ifp
->buffered_id
, 8) != 0) {
1160 if(real_plen
== 128 && memcmp(real_prefix
+ 8, id
, 8) == 0) {
1163 start_message(ifp
, MESSAGE_ROUTER_ID
, 10);
1164 accumulate_short(ifp
, 0);
1165 accumulate_bytes(ifp
, id
, 8);
1166 end_message(ifp
, MESSAGE_ROUTER_ID
, 10);
1168 memcpy(babel_ifp
->buffered_id
, id
, sizeof(babel_ifp
->buffered_id
));
1169 babel_ifp
->have_buffered_id
= 1;
1172 start_message(ifp
, MESSAGE_UPDATE
, 10 + (real_plen
+ 7) / 8 - omit
+
1174 accumulate_byte(ifp
, v4
? 1 : 2);
1175 accumulate_byte(ifp
, flags
);
1176 accumulate_byte(ifp
, real_plen
);
1177 accumulate_byte(ifp
, omit
);
1178 accumulate_short(ifp
, (babel_ifp
->update_interval
+ 5) / 10);
1179 accumulate_short(ifp
, seqno
);
1180 accumulate_short(ifp
, metric
);
1181 accumulate_bytes(ifp
, real_prefix
+ omit
, (real_plen
+ 7) / 8 - omit
);
1182 /* Note that an empty channels TLV is different from no such TLV. */
1183 if(channels_len
>= 0) {
1184 accumulate_byte(ifp
, 2);
1185 accumulate_byte(ifp
, channels_len
);
1187 if (channels
&& channels_len
> 0)
1188 accumulate_bytes(ifp
, channels
, channels_len
);
1190 end_message(ifp
, MESSAGE_UPDATE
, 10 + (real_plen
+ 7) / 8 - omit
+
1194 memcpy(babel_ifp
->buffered_prefix
, prefix
, 16);
1195 babel_ifp
->have_buffered_prefix
= 1;
1200 compare_buffered_updates(const void *av
, const void *bv
)
1202 const struct buffered_update
*a
= av
, *b
= bv
;
1203 int rc
, v4a
, v4b
, ma
, mb
;
1205 rc
= memcmp(a
->id
, b
->id
, 8);
1209 v4a
= (a
->plen
>= 96 && v4mapped(a
->prefix
));
1210 v4b
= (b
->plen
>= 96 && v4mapped(b
->prefix
));
1217 ma
= (!v4a
&& a
->plen
== 128 && memcmp(a
->prefix
+ 8, a
->id
, 8) == 0);
1218 mb
= (!v4b
&& b
->plen
== 128 && memcmp(b
->prefix
+ 8, b
->id
, 8) == 0);
1225 if(a
->plen
< b
->plen
)
1227 else if(a
->plen
> b
->plen
)
1230 return memcmp(a
->prefix
, b
->prefix
, 16);
1234 flushupdates(struct interface
*ifp
)
1236 babel_interface_nfo
*babel_ifp
= NULL
;
1237 struct xroute
*xroute
;
1238 struct babel_route
*route
;
1239 const unsigned char *last_prefix
= NULL
;
1240 unsigned char last_plen
= 0xFF;
1244 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1245 struct interface
*ifp_aux
;
1246 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1247 flushupdates(ifp_aux
);
1251 babel_ifp
= babel_get_if_nfo(ifp
);
1252 if(babel_ifp
->num_buffered_updates
> 0) {
1253 struct buffered_update
*b
= babel_ifp
->buffered_updates
;
1254 int n
= babel_ifp
->num_buffered_updates
;
1256 babel_ifp
->buffered_updates
= NULL
;
1257 babel_ifp
->update_bufsize
= 0;
1258 babel_ifp
->num_buffered_updates
= 0;
1263 debugf(BABEL_DEBUG_COMMON
," (flushing %d buffered updates on %s (%d))",
1264 n
, ifp
->name
, ifp
->ifindex
);
1266 /* In order to send fewer update messages, we want to send updates
1267 with the same router-id together, with IPv6 going out before IPv4. */
1269 for(i
= 0; i
< n
; i
++) {
1270 route
= find_installed_route(b
[i
].prefix
, b
[i
].plen
);
1272 memcpy(b
[i
].id
, route
->src
->id
, 8);
1274 memcpy(b
[i
].id
, myid
, 8);
1277 qsort(b
, n
, sizeof(struct buffered_update
), compare_buffered_updates
);
1279 for(i
= 0; i
< n
; i
++) {
1280 /* The same update may be scheduled multiple times before it is
1281 sent out. Since our buffer is now sorted, it is enough to
1282 compare with the previous update. */
1285 if(b
[i
].plen
== last_plen
&&
1286 memcmp(b
[i
].prefix
, last_prefix
, 16) == 0)
1290 xroute
= find_xroute(b
[i
].prefix
, b
[i
].plen
);
1291 route
= find_installed_route(b
[i
].prefix
, b
[i
].plen
);
1293 if(xroute
&& (!route
|| xroute
->metric
<= kernel_metric
)) {
1294 really_send_update(ifp
, myid
,
1295 xroute
->prefix
, xroute
->plen
,
1296 myseqno
, xroute
->metric
,
1298 last_prefix
= xroute
->prefix
;
1299 last_plen
= xroute
->plen
;
1301 unsigned char channels
[DIVERSITY_HOPS
];
1303 struct interface
*route_ifp
= route
->neigh
->ifp
;
1304 struct babel_interface
*babel_route_ifp
= NULL
;
1305 unsigned short metric
;
1306 unsigned short seqno
;
1308 seqno
= route
->seqno
;
1310 route_interferes(route
, ifp
) ?
1311 route_metric(route
) :
1312 route_metric_noninterfering(route
);
1314 if(metric
< INFINITY
)
1315 satisfy_request(route
->src
->prefix
, route
->src
->plen
,
1316 seqno
, route
->src
->id
, ifp
);
1317 if((babel_ifp
->flags
& BABEL_IF_SPLIT_HORIZON
) &&
1318 route
->neigh
->ifp
== ifp
)
1321 babel_route_ifp
= babel_get_if_nfo(route_ifp
);
1322 if(babel_route_ifp
->channel
==BABEL_IF_CHANNEL_NONINTERFERING
) {
1323 memcpy(channels
, route
->channels
, DIVERSITY_HOPS
);
1325 if(babel_route_ifp
->channel
== BABEL_IF_CHANNEL_UNKNOWN
)
1326 channels
[0] = BABEL_IF_CHANNEL_INTERFERING
;
1328 assert(babel_route_ifp
->channel
> 0 &&
1329 babel_route_ifp
->channel
<= 255);
1330 channels
[0] = babel_route_ifp
->channel
;
1332 memcpy(channels
+ 1, route
->channels
, DIVERSITY_HOPS
- 1);
1335 chlen
= channels_len(channels
);
1336 really_send_update(ifp
, route
->src
->id
,
1341 update_source(route
->src
, seqno
, metric
);
1342 last_prefix
= route
->src
->prefix
;
1343 last_plen
= route
->src
->plen
;
1345 /* There's no route for this prefix. This can happen shortly
1346 after an xroute has been retracted, so send a retraction. */
1347 really_send_update(ifp
, myid
, b
[i
].prefix
, b
[i
].plen
,
1348 myseqno
, INFINITY
, NULL
, -1);
1351 schedule_flush_now(ifp
);
1355 babel_ifp
->update_flush_timeout
.tv_sec
= 0;
1356 babel_ifp
->update_flush_timeout
.tv_usec
= 0;
1360 schedule_update_flush(struct interface
*ifp
, int urgent
)
1362 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1364 msecs
= update_jitter(babel_ifp
, urgent
);
1365 if(babel_ifp
->update_flush_timeout
.tv_sec
!= 0 &&
1366 timeval_minus_msec(&babel_ifp
->update_flush_timeout
, &babel_now
) < msecs
)
1368 set_timeout(&babel_ifp
->update_flush_timeout
, msecs
);
1372 buffer_update(struct interface
*ifp
,
1373 const unsigned char *prefix
, unsigned char plen
)
1375 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1376 if(babel_ifp
->num_buffered_updates
> 0 &&
1377 babel_ifp
->num_buffered_updates
>= babel_ifp
->update_bufsize
)
1380 if(babel_ifp
->update_bufsize
== 0) {
1382 assert(babel_ifp
->buffered_updates
== NULL
);
1383 /* Allocate enough space to hold a full update. Since the
1384 number of installed routes will grow over time, make sure we
1385 have enough space to send a full-ish frame. */
1386 n
= installed_routes_estimate() + xroutes_estimate() + 4;
1387 n
= MAX(n
, babel_ifp
->bufsize
/ 16);
1389 babel_ifp
->buffered_updates
= malloc(n
*sizeof(struct buffered_update
));
1390 if(babel_ifp
->buffered_updates
== NULL
) {
1391 flog_err(EC_BABEL_MEMORY
, "malloc(buffered_updates): %s",
1392 safe_strerror(errno
));
1394 /* Try again with a tiny buffer. */
1400 babel_ifp
->update_bufsize
= n
;
1401 babel_ifp
->num_buffered_updates
= 0;
1404 memcpy(babel_ifp
->buffered_updates
[babel_ifp
->num_buffered_updates
].prefix
,
1406 babel_ifp
->buffered_updates
[babel_ifp
->num_buffered_updates
].plen
= plen
;
1407 babel_ifp
->num_buffered_updates
++;
1411 send_update(struct interface
*ifp
, int urgent
,
1412 const unsigned char *prefix
, unsigned char plen
)
1414 babel_interface_nfo
*babel_ifp
= NULL
;
1417 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1418 struct interface
*ifp_aux
;
1419 struct babel_route
*route
;
1420 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1421 send_update(ifp_aux
, urgent
, prefix
, plen
);
1423 /* Since flushupdates only deals with non-wildcard interfaces, we
1424 need to do this now. */
1425 route
= find_installed_route(prefix
, plen
);
1426 if(route
&& route_metric(route
) < INFINITY
)
1427 satisfy_request(prefix
, plen
, route
->src
->seqno
, route
->src
->id
,
1436 babel_ifp
= babel_get_if_nfo(ifp
);
1438 debugf(BABEL_DEBUG_COMMON
,"Sending update to %s for %s.",
1439 ifp
->name
, format_prefix(prefix
, plen
));
1440 buffer_update(ifp
, prefix
, plen
);
1442 struct route_stream
*routes
= NULL
;
1443 send_self_update(ifp
);
1444 debugf(BABEL_DEBUG_COMMON
,"Sending update to %s for any.", ifp
->name
);
1445 routes
= route_stream(1);
1448 struct babel_route
*route
= route_stream_next(routes
);
1451 buffer_update(ifp
, route
->src
->prefix
, route
->src
->plen
);
1453 route_stream_done(routes
);
1455 flog_err(EC_BABEL_MEMORY
, "Couldn't allocate route stream.");
1457 set_timeout(&babel_ifp
->update_timeout
, babel_ifp
->update_interval
);
1458 babel_ifp
->last_update_time
= babel_now
.tv_sec
;
1460 schedule_update_flush(ifp
, urgent
);
1464 send_update_resend(struct interface
*ifp
,
1465 const unsigned char *prefix
, unsigned char plen
)
1467 assert(prefix
!= NULL
);
1469 send_update(ifp
, 1, prefix
, plen
);
1470 record_resend(RESEND_UPDATE
, prefix
, plen
, 0, NULL
, NULL
, resend_delay
);
1474 send_wildcard_retraction(struct interface
*ifp
)
1476 babel_interface_nfo
*babel_ifp
= NULL
;
1478 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1479 struct interface
*ifp_aux
;
1480 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1481 send_wildcard_retraction(ifp_aux
);
1488 babel_ifp
= babel_get_if_nfo(ifp
);
1489 start_message(ifp
, MESSAGE_UPDATE
, 10);
1490 accumulate_byte(ifp
, 0);
1491 accumulate_byte(ifp
, 0x40);
1492 accumulate_byte(ifp
, 0);
1493 accumulate_byte(ifp
, 0);
1494 accumulate_short(ifp
, 0xFFFF);
1495 accumulate_short(ifp
, myseqno
);
1496 accumulate_short(ifp
, 0xFFFF);
1497 end_message(ifp
, MESSAGE_UPDATE
, 10);
1499 babel_ifp
->have_buffered_id
= 0;
1503 update_myseqno(void)
1505 myseqno
= seqno_plus(myseqno
, 1);
1509 send_self_update(struct interface
*ifp
)
1511 struct xroute_stream
*xroutes
;
1513 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1514 struct interface
*ifp_aux
;
1515 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1518 send_self_update(ifp_aux
);
1523 debugf(BABEL_DEBUG_COMMON
,"Sending self update to %s.", ifp
->name
);
1524 xroutes
= xroute_stream();
1527 struct xroute
*xroute
= xroute_stream_next(xroutes
);
1528 if(xroute
== NULL
) break;
1529 send_update(ifp
, 0, xroute
->prefix
, xroute
->plen
);
1531 xroute_stream_done(xroutes
);
1533 flog_err(EC_BABEL_MEMORY
, "Couldn't allocate xroute stream.");
1538 send_ihu(struct neighbour
*neigh
, struct interface
*ifp
)
1540 babel_interface_nfo
*babel_ifp
= NULL
;
1541 int rxcost
, interval
;
1546 if(neigh
== NULL
&& ifp
== NULL
) {
1547 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1548 struct interface
*ifp_aux
;
1549 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1552 send_ihu(NULL
, ifp_aux
);
1558 struct neighbour
*ngh
;
1559 FOR_ALL_NEIGHBOURS(ngh
) {
1567 if(ifp
&& neigh
->ifp
!= ifp
)
1571 babel_ifp
= babel_get_if_nfo(ifp
);
1575 rxcost
= neighbour_rxcost(neigh
);
1576 interval
= (babel_ifp
->hello_interval
* 3 + 9) / 10;
1578 /* Conceptually, an IHU is a unicast message. We usually send them as
1579 multicast, since this allows aggregation into a single packet and
1580 avoids an ARP exchange. If we already have a unicast message queued
1581 for this neighbour, however, we might as well piggyback the IHU. */
1582 debugf(BABEL_DEBUG_COMMON
,"Sending %sihu %d on %s to %s.",
1583 unicast_neighbour
== neigh
? "unicast " : "",
1586 format_address(neigh
->address
));
1588 ll
= linklocal(neigh
->address
);
1590 if((babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) && neigh
->hello_send_us
1591 /* Checks whether the RTT data is not too old to be sent. */
1592 && timeval_minus_msec(&babel_now
,
1593 &neigh
->hello_rtt_receive_time
) < 1000000) {
1596 neigh
->hello_send_us
= 0;
1600 /* The length depends on the format of the address, and then an
1601 optional 10-bytes sub-TLV for timestamps (used to compute a RTT). */
1602 msglen
= (ll
? 14 : 22) + (send_rtt_data
? 10 : 0);
1604 if(unicast_neighbour
!= neigh
) {
1605 start_message(ifp
, MESSAGE_IHU
, msglen
);
1606 accumulate_byte(ifp
, ll
? 3 : 2);
1607 accumulate_byte(ifp
, 0);
1608 accumulate_short(ifp
, rxcost
);
1609 accumulate_short(ifp
, interval
);
1611 accumulate_bytes(ifp
, neigh
->address
+ 8, 8);
1613 accumulate_bytes(ifp
, neigh
->address
, 16);
1614 if (send_rtt_data
) {
1615 accumulate_byte(ifp
, SUBTLV_TIMESTAMP
);
1616 accumulate_byte(ifp
, 8);
1617 accumulate_int(ifp
, neigh
->hello_send_us
);
1618 accumulate_int(ifp
, time_us(neigh
->hello_rtt_receive_time
));
1620 end_message(ifp
, MESSAGE_IHU
, msglen
);
1623 rc
= start_unicast_message(neigh
, MESSAGE_IHU
, msglen
);
1625 accumulate_unicast_byte(neigh
, ll
? 3 : 2);
1626 accumulate_unicast_byte(neigh
, 0);
1627 accumulate_unicast_short(neigh
, rxcost
);
1628 accumulate_unicast_short(neigh
, interval
);
1630 accumulate_unicast_bytes(neigh
, neigh
->address
+ 8, 8);
1632 accumulate_unicast_bytes(neigh
, neigh
->address
, 16);
1633 if (send_rtt_data
) {
1634 accumulate_unicast_byte(neigh
, SUBTLV_TIMESTAMP
);
1635 accumulate_unicast_byte(neigh
, 8);
1636 accumulate_unicast_int(neigh
, neigh
->hello_send_us
);
1637 accumulate_unicast_int(neigh
,
1638 time_us(neigh
->hello_rtt_receive_time
));
1640 end_unicast_message(neigh
, MESSAGE_IHU
, msglen
);
1644 /* Send IHUs to all marginal neighbours */
1646 send_marginal_ihu(struct interface
*ifp
)
1648 struct neighbour
*neigh
;
1649 FOR_ALL_NEIGHBOURS(neigh
) {
1650 if(ifp
&& neigh
->ifp
!= ifp
)
1652 if(neigh
->txcost
>= 384 || (neigh
->reach
& 0xF000) != 0xF000)
1653 send_ihu(neigh
, ifp
);
1658 send_request(struct interface
*ifp
,
1659 const unsigned char *prefix
, unsigned char plen
)
1664 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1665 struct interface
*ifp_aux
;
1666 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1669 send_request(ifp_aux
, prefix
, plen
);
1674 /* make sure any buffered updates go out before this request. */
1680 debugf(BABEL_DEBUG_COMMON
,"sending request to %s for %s.",
1681 ifp
->name
, prefix
? format_prefix(prefix
, plen
) : "any");
1682 v4
= plen
>= 96 && v4mapped(prefix
);
1683 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1684 len
= !prefix
? 2 : 2 + pb
;
1686 start_message(ifp
, MESSAGE_REQUEST
, len
);
1687 accumulate_byte(ifp
, !prefix
? 0 : v4
? 1 : 2);
1688 accumulate_byte(ifp
, !prefix
? 0 : v4
? plen
- 96 : plen
);
1691 accumulate_bytes(ifp
, prefix
+ 12, pb
);
1693 accumulate_bytes(ifp
, prefix
, pb
);
1695 end_message(ifp
, MESSAGE_REQUEST
, len
);
1699 send_unicast_request(struct neighbour
*neigh
,
1700 const unsigned char *prefix
, unsigned char plen
)
1702 int rc
, v4
, pb
, len
;
1704 /* make sure any buffered updates go out before this request. */
1705 flushupdates(neigh
->ifp
);
1707 debugf(BABEL_DEBUG_COMMON
,"sending unicast request to %s for %s.",
1708 format_address(neigh
->address
),
1709 prefix
? format_prefix(prefix
, plen
) : "any");
1710 v4
= plen
>= 96 && v4mapped(prefix
);
1711 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1712 len
= !prefix
? 2 : 2 + pb
;
1714 rc
= start_unicast_message(neigh
, MESSAGE_REQUEST
, len
);
1716 accumulate_unicast_byte(neigh
, !prefix
? 0 : v4
? 1 : 2);
1717 accumulate_unicast_byte(neigh
, !prefix
? 0 : v4
? plen
- 96 : plen
);
1720 accumulate_unicast_bytes(neigh
, prefix
+ 12, pb
);
1722 accumulate_unicast_bytes(neigh
, prefix
, pb
);
1724 end_unicast_message(neigh
, MESSAGE_REQUEST
, len
);
1728 send_multihop_request(struct interface
*ifp
,
1729 const unsigned char *prefix
, unsigned char plen
,
1730 unsigned short seqno
, const unsigned char *id
,
1731 unsigned short hop_count
)
1735 /* Make sure any buffered updates go out before this request. */
1739 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1740 struct interface
*ifp_aux
;
1741 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1744 send_multihop_request(ifp_aux
, prefix
, plen
, seqno
, id
, hop_count
);
1752 debugf(BABEL_DEBUG_COMMON
,"Sending request (%d) on %s for %s.",
1753 hop_count
, ifp
->name
, format_prefix(prefix
, plen
));
1754 v4
= plen
>= 96 && v4mapped(prefix
);
1755 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1758 start_message(ifp
, MESSAGE_MH_REQUEST
, len
);
1759 accumulate_byte(ifp
, v4
? 1 : 2);
1760 accumulate_byte(ifp
, v4
? plen
- 96 : plen
);
1761 accumulate_short(ifp
, seqno
);
1762 accumulate_byte(ifp
, hop_count
);
1763 accumulate_byte(ifp
, 0);
1764 accumulate_bytes(ifp
, id
, 8);
1767 accumulate_bytes(ifp
, prefix
+ 12, pb
);
1769 accumulate_bytes(ifp
, prefix
, pb
);
1771 end_message(ifp
, MESSAGE_MH_REQUEST
, len
);
1775 send_unicast_multihop_request(struct neighbour
*neigh
,
1776 const unsigned char *prefix
, unsigned char plen
,
1777 unsigned short seqno
, const unsigned char *id
,
1778 unsigned short hop_count
)
1780 int rc
, v4
, pb
, len
;
1782 /* Make sure any buffered updates go out before this request. */
1783 flushupdates(neigh
->ifp
);
1785 debugf(BABEL_DEBUG_COMMON
,"Sending multi-hop request to %s for %s (%d hops).",
1786 format_address(neigh
->address
),
1787 format_prefix(prefix
, plen
), hop_count
);
1788 v4
= plen
>= 96 && v4mapped(prefix
);
1789 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1792 rc
= start_unicast_message(neigh
, MESSAGE_MH_REQUEST
, len
);
1794 accumulate_unicast_byte(neigh
, v4
? 1 : 2);
1795 accumulate_unicast_byte(neigh
, v4
? plen
- 96 : plen
);
1796 accumulate_unicast_short(neigh
, seqno
);
1797 accumulate_unicast_byte(neigh
, hop_count
);
1798 accumulate_unicast_byte(neigh
, 0);
1799 accumulate_unicast_bytes(neigh
, id
, 8);
1802 accumulate_unicast_bytes(neigh
, prefix
+ 12, pb
);
1804 accumulate_unicast_bytes(neigh
, prefix
, pb
);
1806 end_unicast_message(neigh
, MESSAGE_MH_REQUEST
, len
);
1810 send_request_resend(struct neighbour
*neigh
,
1811 const unsigned char *prefix
, unsigned char plen
,
1812 unsigned short seqno
, unsigned char *id
)
1815 send_unicast_multihop_request(neigh
, prefix
, plen
, seqno
, id
, 127);
1817 send_multihop_request(NULL
, prefix
, plen
, seqno
, id
, 127);
1819 record_resend(RESEND_REQUEST
, prefix
, plen
, seqno
, id
,
1820 neigh
? neigh
->ifp
: NULL
, resend_delay
);
1824 handle_request(struct neighbour
*neigh
, const unsigned char *prefix
,
1825 unsigned char plen
, unsigned char hop_count
,
1826 unsigned short seqno
, const unsigned char *id
)
1828 struct xroute
*xroute
;
1829 struct babel_route
*route
;
1830 struct neighbour
*successor
= NULL
;
1832 xroute
= find_xroute(prefix
, plen
);
1833 route
= find_installed_route(prefix
, plen
);
1835 if(xroute
&& (!route
|| xroute
->metric
<= kernel_metric
)) {
1836 if(hop_count
> 0 && memcmp(id
, myid
, 8) == 0) {
1837 if(seqno_compare(seqno
, myseqno
) > 0) {
1838 if(seqno_minus(seqno
, myseqno
) > 100) {
1839 /* Hopelessly out-of-date request */
1845 send_update(neigh
->ifp
, 1, prefix
, plen
);
1850 (memcmp(id
, route
->src
->id
, 8) != 0 ||
1851 seqno_compare(seqno
, route
->seqno
) <= 0)) {
1852 send_update(neigh
->ifp
, 1, prefix
, plen
);
1859 if(route
&& memcmp(id
, route
->src
->id
, 8) == 0 &&
1860 seqno_minus(seqno
, route
->seqno
) > 100) {
1861 /* Hopelessly out-of-date */
1865 if(request_redundant(neigh
->ifp
, prefix
, plen
, seqno
, id
))
1868 /* Let's try to forward this request. */
1869 if(route
&& route_metric(route
) < INFINITY
)
1870 successor
= route
->neigh
;
1872 if(!successor
|| successor
== neigh
) {
1873 /* We were about to forward a request to its requestor. Try to
1874 find a different neighbour to forward the request to. */
1875 struct babel_route
*other_route
;
1877 other_route
= find_best_route(prefix
, plen
, 0, neigh
);
1878 if(other_route
&& route_metric(other_route
) < INFINITY
)
1879 successor
= other_route
->neigh
;
1882 if(!successor
|| successor
== neigh
)
1886 send_unicast_multihop_request(successor
, prefix
, plen
, seqno
, id
,
1888 record_resend(RESEND_REQUEST
, prefix
, plen
, seqno
, id
,