1 // SPDX-License-Identifier: MIT
3 Copyright (c) 2007, 2008 by Juliusz Chroboczek
12 #include "babel_interface.h"
14 #include "neighbour.h"
20 #include "babel_main.h"
21 #include "babel_errors.h"
23 static unsigned char packet_header
[4] = {42, 2};
25 int split_horizon
= 1;
27 unsigned short myseqno
= 0;
29 #define UNICAST_BUFSIZE 1024
30 static int unicast_buffered
= 0;
31 static unsigned char *unicast_buffer
= NULL
;
32 struct neighbour
*unicast_neighbour
= NULL
;
33 struct timeval unicast_flush_timeout
= {0, 0};
35 /* Minimum TLV _body_ length for TLVs of particular types (0 = no limit). */
36 static const unsigned char tlv_min_length
[MESSAGE_MAX
+ 1] =
40 [ MESSAGE_ACK_REQ
] = 6,
42 [ MESSAGE_HELLO
] = 6,
44 [ MESSAGE_ROUTER_ID
] = 10,
46 [ MESSAGE_UPDATE
] = 10,
47 [ MESSAGE_REQUEST
] = 2,
48 [ MESSAGE_MH_REQUEST
] = 14,
51 /* Parse a network prefix, encoded in the somewhat baroque compressed
52 representation used by Babel. Return the number of bytes parsed. */
54 network_prefix(int ae
, int plen
, unsigned int omitted
,
55 const unsigned char *p
, const unsigned char *dp
,
56 unsigned int len
, unsigned char *p_r
)
59 unsigned char prefix
[16];
72 memset(prefix
, 0, 16);
79 if(omitted
> 4 || pb
> 4 || (pb
> omitted
&& len
< pb
- omitted
))
81 memcpy(prefix
, v4prefix
, 12);
83 if (dp
== NULL
|| !v4mapped(dp
)) return -1;
84 memcpy(prefix
, dp
, 12 + omitted
);
86 if(pb
> omitted
) memcpy(prefix
+ 12 + omitted
, p
, pb
- omitted
);
90 if(omitted
> 16 || (pb
> omitted
&& len
< pb
- omitted
)) return -1;
92 if (dp
== NULL
|| v4mapped(dp
)) return -1;
93 memcpy(prefix
, dp
, omitted
);
95 if(pb
> omitted
) memcpy(prefix
+ omitted
, p
, pb
- omitted
);
99 if(pb
> 8 && len
< pb
- 8) return -1;
102 if(pb
> 8) memcpy(prefix
+ 8, p
, pb
- 8);
109 mask_prefix(p_r
, prefix
, plen
< 0 ? 128 : ae
== 1 ? plen
+ 96 : plen
);
113 static bool parse_update_subtlv(const unsigned char *a
, int alen
,
114 unsigned char *channels
)
116 int type
, len
, i
= 0;
120 if(type
== SUBTLV_PAD1
) {
126 flog_err(EC_BABEL_PACKET
, "Received truncated attributes.");
130 if(i
+ len
+ 2 > alen
) {
131 flog_err(EC_BABEL_PACKET
, "Received truncated attributes.");
135 if (type
& SUBTLV_MANDATORY
) {
138 * If the mandatory bit is set, then the whole enclosing
139 * TLV MUST be silently ignored (except for updating the
140 * parser state by a Router-Id, Next Hop, or Update TLV,
141 * as described in the next section).
143 debugf(BABEL_DEBUG_COMMON
,
144 "Received Mandatory bit set but this FRR version is not prepared to handle it at this point");
146 } else if (type
== SUBTLV_PADN
) {
148 } else if (type
== SUBTLV_DIVERSITY
) {
149 if (len
> DIVERSITY_HOPS
) {
152 "Received overlong channel information (%d > %d).n",
153 len
, DIVERSITY_HOPS
);
154 len
= DIVERSITY_HOPS
;
156 if (memchr(a
+ i
+ 2, 0, len
) != NULL
) {
158 flog_err(EC_BABEL_PACKET
,
159 "Channel information contains 0!");
162 memset(channels
, 0, DIVERSITY_HOPS
);
163 memcpy(channels
, a
+ i
+ 2, len
);
165 debugf(BABEL_DEBUG_COMMON
,
166 "Received unknown route attribute %d.", type
);
175 parse_hello_subtlv(const unsigned char *a
, int alen
,
176 unsigned int *hello_send_us
)
178 int type
, len
, i
= 0, ret
= 0;
182 if(type
== SUBTLV_PAD1
) {
188 flog_err(EC_BABEL_PACKET
,
189 "Received truncated sub-TLV on Hello message.");
193 if(i
+ len
+ 2 > alen
) {
194 flog_err(EC_BABEL_PACKET
,
195 "Received truncated sub-TLV on Hello message.");
199 if (type
& SUBTLV_MANDATORY
) {
202 * If the mandatory bit is set, then the whole enclosing
203 * TLV MUST be silently ignored (except for updating the
204 * parser state by a Router-Id, Next Hop, or Update TLV, as
205 * described in the next section).
207 debugf(BABEL_DEBUG_COMMON
,
208 "Received subtlv with Mandatory bit, this version of FRR is not prepared to handle this currently");
210 } else if (type
== SUBTLV_PADN
) {
212 } else if (type
== SUBTLV_TIMESTAMP
) {
214 DO_NTOHL(*hello_send_us
, a
+ i
+ 2);
219 "Received incorrect RTT sub-TLV on Hello message.");
222 debugf(BABEL_DEBUG_COMMON
,
223 "Received unknown Hello sub-TLV type %d.", type
);
232 parse_ihu_subtlv(const unsigned char *a
, int alen
,
233 unsigned int *hello_send_us
,
234 unsigned int *hello_rtt_receive_time
)
236 int type
, len
, i
= 0, ret
= 0;
240 if(type
== SUBTLV_PAD1
) {
246 flog_err(EC_BABEL_PACKET
,
247 "Received truncated sub-TLV on IHU message.");
251 if(i
+ len
+ 2 > alen
) {
252 flog_err(EC_BABEL_PACKET
,
253 "Received truncated sub-TLV on IHU message.");
257 if(type
== SUBTLV_PADN
) {
259 } else if(type
== SUBTLV_TIMESTAMP
) {
261 DO_NTOHL(*hello_send_us
, a
+ i
+ 2);
262 DO_NTOHL(*hello_rtt_receive_time
, a
+ i
+ 6);
266 flog_err(EC_BABEL_PACKET
,
267 "Received incorrect RTT sub-TLV on IHU message.");
270 debugf(BABEL_DEBUG_COMMON
,
271 "Received unknown IHU sub-TLV type %d.", type
);
280 network_address(int ae
, const unsigned char *a
, unsigned int len
,
283 return network_prefix(ae
, -1, 0, a
, NULL
, len
, a_r
);
287 channels_len(unsigned char *channels
)
289 unsigned char *p
= memchr(channels
, 0, DIVERSITY_HOPS
);
290 return p
? (p
- channels
) : DIVERSITY_HOPS
;
293 /* Check, that the provided frame consists of a valid Babel packet header
294 followed by a sequence of TLVs. TLVs of known types are also checked to meet
295 minimum length constraints defined for each. Return 0 for no errors. */
297 babel_packet_examin(const unsigned char *packet
, int packetlen
, int *blength
)
300 const unsigned char *message
;
301 unsigned char type
, len
;
303 if(packetlen
< 4 || packet
[0] != 42 || packet
[1] != 2)
305 DO_NTOHS(bodylen
, packet
+ 2);
306 if(bodylen
+ 4 > packetlen
) {
307 debugf(BABEL_DEBUG_COMMON
, "Received truncated packet (%d + 4 > %d).",
312 message
= packet
+ 4 + i
;
314 if(type
== MESSAGE_PAD1
) {
318 if(i
+ 2 > bodylen
) {
319 debugf(BABEL_DEBUG_COMMON
,"Received truncated message.");
323 if(i
+ len
+ 2 > bodylen
) {
324 debugf(BABEL_DEBUG_COMMON
,"Received truncated message.");
328 if(type
<= MESSAGE_MAX
&& tlv_min_length
[type
] && len
< tlv_min_length
[type
]) {
329 debugf(BABEL_DEBUG_COMMON
,"Undersized %u TLV", type
);
340 parse_packet(const unsigned char *from
, struct interface
*ifp
,
341 const unsigned char *packet
, int packetlen
)
344 const unsigned char *message
;
345 unsigned char type
, len
;
347 struct neighbour
*neigh
;
348 int have_router_id
= 0, have_v4_prefix
= 0, have_v6_prefix
= 0,
349 have_v4_nh
= 0, have_v6_nh
= 0;
350 unsigned char router_id
[8], v4_prefix
[16], v6_prefix
[16],
351 v4_nh
[16], v6_nh
[16];
352 int have_hello_rtt
= 0;
353 /* Content of the RTT sub-TLV on IHU messages. */
354 unsigned int hello_send_us
= 0, hello_rtt_receive_time
= 0;
355 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
357 if(babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) {
358 /* We want to track exactly when we received this packet. */
362 if(!linklocal(from
)) {
363 flog_err(EC_BABEL_PACKET
,
364 "Received packet from non-local address %s.",
365 format_address(from
));
369 if (babel_packet_examin (packet
, packetlen
, &bodylen
)) {
370 flog_err(EC_BABEL_PACKET
,
371 "Received malformed packet on %s from %s.",
372 ifp
->name
, format_address(from
));
376 neigh
= find_neighbour(from
, ifp
);
378 flog_err(EC_BABEL_PACKET
, "Couldn't allocate neighbour.");
384 message
= packet
+ 4 + i
;
386 if(type
== MESSAGE_PAD1
) {
387 debugf(BABEL_DEBUG_COMMON
,"Received pad1 from %s on %s.",
388 format_address(from
), ifp
->name
);
394 if(type
== MESSAGE_PADN
) {
395 debugf(BABEL_DEBUG_COMMON
,"Received pad%d from %s on %s.",
396 len
, format_address(from
), ifp
->name
);
397 } else if(type
== MESSAGE_ACK_REQ
) {
398 unsigned short nonce
, interval
;
399 DO_NTOHS(nonce
, message
+ 4);
400 DO_NTOHS(interval
, message
+ 6);
401 debugf(BABEL_DEBUG_COMMON
,"Received ack-req (%04X %d) from %s on %s.",
402 nonce
, interval
, format_address(from
), ifp
->name
);
403 send_ack(neigh
, nonce
, interval
);
404 } else if(type
== MESSAGE_ACK
) {
405 debugf(BABEL_DEBUG_COMMON
,"Received ack from %s on %s.",
406 format_address(from
), ifp
->name
);
407 /* Nothing right now */
408 } else if(type
== MESSAGE_HELLO
) {
409 unsigned short seqno
, interval
, flags
;
411 unsigned int timestamp
= 0;
413 #define BABEL_UNICAST_HELLO 0x8000
414 DO_NTOHS(flags
, message
+ 2);
418 * All other bits MUST be sent as a 0 and silently
419 * ignored on reception
421 if (CHECK_FLAG(flags
, ~BABEL_UNICAST_HELLO
)) {
422 debugf(BABEL_DEBUG_COMMON
,
423 "Received Hello from %s on %s that does not have all 0's in the unused section of flags, ignoring",
424 format_address(from
), ifp
->name
);
429 * RFC 8966 Appendix F
430 * TL;DR -> Please ignore Unicast hellos until FRR's
431 * BABEL is brought up to date
433 if (CHECK_FLAG(flags
, BABEL_UNICAST_HELLO
)) {
434 debugf(BABEL_DEBUG_COMMON
,
435 "Received Unicast Hello from %s on %s that FRR is not prepared to understand yet",
436 format_address(from
), ifp
->name
);
440 DO_NTOHS(seqno
, message
+ 4);
441 DO_NTOHS(interval
, message
+ 6);
442 debugf(BABEL_DEBUG_COMMON
,
443 "Received hello %d (%d) from %s on %s.", seqno
, interval
,
444 format_address(from
), ifp
->name
);
447 * RFC 8966 Appendix F
448 * TL;DR -> Please ignore any Hello packets with the interval
452 debugf(BABEL_DEBUG_COMMON
,
453 "Received hello from %s on %s should be ignored as that this version of FRR does not know how to properly handle interval == 0",
454 format_address(from
), ifp
->name
);
458 changed
= update_neighbour(neigh
, seqno
, interval
);
459 update_neighbour_metric(neigh
, changed
);
461 /* Multiply by 3/2 to allow hellos to expire. */
462 schedule_neighbours_check(interval
* 15, 0);
463 /* Sub-TLV handling. */
465 if (parse_hello_subtlv(message
+ 8, len
- 6,
467 neigh
->hello_send_us
= timestamp
;
468 neigh
->hello_rtt_receive_time
= babel_now
;
472 } else if(type
== MESSAGE_IHU
) {
473 unsigned short txcost
, interval
;
474 unsigned char address
[16];
476 DO_NTOHS(txcost
, message
+ 4);
477 DO_NTOHS(interval
, message
+ 6);
478 rc
= network_address(message
[2], message
+ 8, len
- 6, address
);
479 if(rc
< 0) goto fail
;
480 debugf(BABEL_DEBUG_COMMON
,"Received ihu %d (%d) from %s on %s for %s.",
482 format_address(from
), ifp
->name
,
483 format_address(address
));
484 if(message
[2] == 0 || is_interface_ll_address(ifp
, address
)) {
485 int changed
= txcost
!= neigh
->txcost
;
486 neigh
->txcost
= txcost
;
487 neigh
->ihu_time
= babel_now
;
488 neigh
->ihu_interval
= interval
;
489 update_neighbour_metric(neigh
, changed
);
491 /* Multiply by 3/2 to allow neighbours to expire. */
492 schedule_neighbours_check(interval
* 45, 0);
495 parse_ihu_subtlv(message
+ 8 + rc
, len
- 6 - rc
,
496 &hello_send_us
, &hello_rtt_receive_time
);
498 } else if(type
== MESSAGE_ROUTER_ID
) {
499 memcpy(router_id
, message
+ 4, 8);
501 debugf(BABEL_DEBUG_COMMON
,"Received router-id %s from %s on %s.",
502 format_eui64(router_id
), format_address(from
), ifp
->name
);
503 } else if(type
== MESSAGE_NH
) {
504 unsigned char nh
[16];
506 rc
= network_address(message
[2], message
+ 4, len
- 2,
513 debugf(BABEL_DEBUG_COMMON
,"Received nh %s (%d) from %s on %s.",
514 format_address(nh
), message
[2],
515 format_address(from
), ifp
->name
);
516 if(message
[2] == 1) {
517 memcpy(v4_nh
, nh
, 16);
520 memcpy(v6_nh
, nh
, 16);
523 } else if(type
== MESSAGE_UPDATE
) {
524 unsigned char prefix
[16], *nh
;
526 unsigned char channels
[DIVERSITY_HOPS
];
527 unsigned short interval
, seqno
, metric
;
529 bool ignore_update
= false;
531 DO_NTOHS(interval
, message
+ 6);
532 DO_NTOHS(seqno
, message
+ 8);
533 DO_NTOHS(metric
, message
+ 10);
534 if(message
[5] == 0 ||
535 (message
[2] == 1 ? have_v4_prefix
: have_v6_prefix
))
536 rc
= network_prefix(message
[2], message
[4], message
[5],
538 message
[2] == 1 ? v4_prefix
: v6_prefix
,
543 if(message
[3] & 0x80)
544 have_v4_prefix
= have_v6_prefix
= 0;
547 parsed_len
= 10 + rc
;
549 plen
= message
[4] + (message
[2] == 1 ? 96 : 0);
551 if(message
[3] & 0x80) {
552 if(message
[2] == 1) {
553 memcpy(v4_prefix
, prefix
, 16);
556 memcpy(v6_prefix
, prefix
, 16);
560 if(message
[3] & 0x40) {
561 if(message
[2] == 1) {
562 memset(router_id
, 0, 4);
563 memcpy(router_id
+ 4, prefix
+ 12, 4);
565 memcpy(router_id
, prefix
+ 8, 8);
569 if(!have_router_id
&& message
[2] != 0) {
570 flog_err(EC_BABEL_PACKET
,
571 "Received prefix with no router id.");
574 debugf(BABEL_DEBUG_COMMON
,"Received update%s%s for %s from %s on %s.",
575 (message
[3] & 0x80) ? "/prefix" : "",
576 (message
[3] & 0x40) ? "/id" : "",
577 format_prefix(prefix
, plen
),
578 format_address(from
), ifp
->name
);
580 if(message
[2] == 0) {
581 if(metric
< 0xFFFF) {
582 flog_err(EC_BABEL_PACKET
,
583 "Received wildcard update with finite metric.");
586 retract_neighbour_routes(neigh
);
588 } else if(message
[2] == 1) {
592 } else if(have_v6_nh
) {
598 if(message
[2] == 1) {
599 if(!babel_get_if_nfo(ifp
)->ipv4
)
603 if((babel_get_if_nfo(ifp
)->flags
& BABEL_IF_FARAWAY
)) {
606 /* This will be overwritten by parse_update_subtlv below. */
608 /* Assume non-interfering (wired) link. */
611 /* Assume interfering. */
612 channels
[0] = BABEL_IF_CHANNEL_INTERFERING
;
618 parse_update_subtlv(message
+ 2 + parsed_len
,
619 len
- parsed_len
, channels
);
623 update_route(router_id
, prefix
, plen
, seqno
, metric
,
624 interval
, neigh
, nh
, channels
,
625 channels_len(channels
));
626 } else if(type
== MESSAGE_REQUEST
) {
627 unsigned char prefix
[16], plen
;
629 rc
= network_prefix(message
[2], message
[3], 0,
630 message
+ 4, NULL
, len
- 2, prefix
);
631 if(rc
< 0) goto fail
;
632 plen
= message
[3] + (message
[2] == 1 ? 96 : 0);
633 debugf(BABEL_DEBUG_COMMON
,"Received request for %s from %s on %s.",
634 message
[2] == 0 ? "any" : format_prefix(prefix
, plen
),
635 format_address(from
), ifp
->name
);
636 if(message
[2] == 0) {
637 struct babel_interface
*neigh_ifp
=babel_get_if_nfo(neigh
->ifp
);
638 /* If a neighbour is requesting a full route dump from us,
639 we might as well send it an IHU. */
640 send_ihu(neigh
, NULL
);
641 /* Since nodes send wildcard requests on boot, booting
642 a large number of nodes at the same time may cause an
643 update storm. Ignore a wildcard request that happens
644 shortly after we sent a full update. */
645 if(neigh_ifp
->last_update_time
<
646 (time_t)(babel_now
.tv_sec
-
647 MAX(neigh_ifp
->hello_interval
/ 100, 1)))
648 send_update(neigh
->ifp
, 0, NULL
, 0);
650 send_update(neigh
->ifp
, 0, prefix
, plen
);
652 } else if(type
== MESSAGE_MH_REQUEST
) {
653 unsigned char prefix
[16], plen
;
654 unsigned short seqno
;
656 DO_NTOHS(seqno
, message
+ 4);
657 rc
= network_prefix(message
[2], message
[3], 0,
658 message
+ 16, NULL
, len
- 14, prefix
);
659 if(rc
< 0) goto fail
;
660 plen
= message
[3] + (message
[2] == 1 ? 96 : 0);
661 debugf(BABEL_DEBUG_COMMON
,"Received request (%d) for %s from %s on %s (%s, %d).",
663 format_prefix(prefix
, plen
),
664 format_address(from
), ifp
->name
,
665 format_eui64(message
+ 8), seqno
);
666 handle_request(neigh
, prefix
, plen
, message
[6],
669 debugf(BABEL_DEBUG_COMMON
,"Received unknown packet type %d from %s on %s.",
670 type
, format_address(from
), ifp
->name
);
677 flog_err(EC_BABEL_PACKET
,
678 "Couldn't parse packet (%d, %d) from %s on %s.",
679 message
[0], message
[1], format_address(from
), ifp
->name
);
683 /* We can calculate the RTT to this neighbour. */
684 if(have_hello_rtt
&& hello_send_us
&& hello_rtt_receive_time
) {
685 int remote_waiting_us
, local_waiting_us
;
686 unsigned int rtt
, smoothed_rtt
;
687 unsigned int old_rttcost
;
689 remote_waiting_us
= neigh
->hello_send_us
- hello_rtt_receive_time
;
690 local_waiting_us
= time_us(neigh
->hello_rtt_receive_time
) -
693 /* Sanity checks (validity window of 10 minutes). */
694 if(remote_waiting_us
< 0 || local_waiting_us
< 0 ||
695 remote_waiting_us
> 600000000 || local_waiting_us
> 600000000)
698 rtt
= MAX(0, local_waiting_us
- remote_waiting_us
);
699 debugf(BABEL_DEBUG_COMMON
, "RTT to %s on %s sample result: %d us.",
700 format_address(from
), ifp
->name
, rtt
);
702 old_rttcost
= neighbour_rttcost(neigh
);
703 if (valid_rtt(neigh
)) {
704 /* Running exponential average. */
705 smoothed_rtt
= (babel_ifp
->rtt_decay
* rtt
+
706 (256 - babel_ifp
->rtt_decay
) * neigh
->rtt
);
707 /* Rounding (up or down) to get closer to the sample. */
708 neigh
->rtt
= (neigh
->rtt
>= rtt
) ? smoothed_rtt
/ 256 :
709 (smoothed_rtt
+ 255) / 256;
711 /* We prefer to be conservative with new neighbours
713 assert(rtt
<= 0x7FFFFFFF);
716 changed
= (neighbour_rttcost(neigh
) == old_rttcost
? 0 : 1);
717 update_neighbour_metric(neigh
, changed
);
718 neigh
->rtt_time
= babel_now
;
723 /* Under normal circumstances, there are enough moderation mechanisms
724 elsewhere in the protocol to make sure that this last-ditch check
725 should never trigger. But I'm superstitious. */
728 check_bucket(struct interface
*ifp
)
730 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
731 if(babel_ifp
->bucket
== 0) {
732 int seconds
= babel_now
.tv_sec
- babel_ifp
->bucket_time
;
734 babel_ifp
->bucket
= MIN(BUCKET_TOKENS_MAX
,
735 seconds
* BUCKET_TOKENS_PER_SEC
);
737 /* Reset bucket time unconditionally, in case clock is stepped. */
738 babel_ifp
->bucket_time
= babel_now
.tv_sec
;
741 if(babel_ifp
->bucket
> 0) {
750 fill_rtt_message(struct interface
*ifp
)
752 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
753 if((babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) &&
754 (babel_ifp
->buffered_hello
>= 0)) {
755 if(babel_ifp
->sendbuf
[babel_ifp
->buffered_hello
+ 8] == SUBTLV_PADN
&&
756 babel_ifp
->sendbuf
[babel_ifp
->buffered_hello
+ 9] == 4) {
758 /* Change the type of sub-TLV. */
759 babel_ifp
->sendbuf
[babel_ifp
->buffered_hello
+ 8] =
762 time
= time_us(babel_now
);
763 DO_HTONL(babel_ifp
->sendbuf
+ babel_ifp
->buffered_hello
+ 10, time
);
766 flog_err(EC_BABEL_PACKET
, "No space left for timestamp sub-TLV (this shouldn't happen)");
774 flushbuf(struct interface
*ifp
)
777 struct sockaddr_in6 sin6
;
778 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
780 assert(babel_ifp
->buffered
<= babel_ifp
->bufsize
);
784 if(babel_ifp
->buffered
> 0) {
785 debugf(BABEL_DEBUG_COMMON
," (flushing %d buffered bytes on %s)",
786 babel_ifp
->buffered
, ifp
->name
);
787 if(check_bucket(ifp
)) {
788 memset(&sin6
, 0, sizeof(sin6
));
789 sin6
.sin6_family
= AF_INET6
;
790 memcpy(&sin6
.sin6_addr
, protocol_group
, 16);
791 sin6
.sin6_port
= htons(protocol_port
);
792 sin6
.sin6_scope_id
= ifp
->ifindex
;
793 DO_HTONS(packet_header
+ 2, babel_ifp
->buffered
);
794 fill_rtt_message(ifp
);
795 rc
= babel_send(protocol_socket
,
796 packet_header
, sizeof(packet_header
),
797 babel_ifp
->sendbuf
, babel_ifp
->buffered
,
798 (struct sockaddr
*)&sin6
, sizeof(sin6
));
800 flog_err(EC_BABEL_PACKET
, "send: %s", safe_strerror(errno
));
802 flog_err(EC_BABEL_PACKET
, "Bucket full, dropping packet to %s.",
806 VALGRIND_MAKE_MEM_UNDEFINED(babel_ifp
->sendbuf
, babel_ifp
->bufsize
);
807 babel_ifp
->buffered
= 0;
808 babel_ifp
->buffered_hello
= -1;
809 babel_ifp
->have_buffered_id
= 0;
810 babel_ifp
->have_buffered_nh
= 0;
811 babel_ifp
->have_buffered_prefix
= 0;
812 babel_ifp
->flush_timeout
.tv_sec
= 0;
813 babel_ifp
->flush_timeout
.tv_usec
= 0;
817 schedule_flush(struct interface
*ifp
)
819 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
820 unsigned msecs
= jitter(babel_ifp
, 0);
821 if(babel_ifp
->flush_timeout
.tv_sec
!= 0 &&
822 timeval_minus_msec(&babel_ifp
->flush_timeout
, &babel_now
) < msecs
)
824 set_timeout(&babel_ifp
->flush_timeout
, msecs
);
828 schedule_flush_now(struct interface
*ifp
)
830 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
832 unsigned msecs
= roughly(10);
833 if(babel_ifp
->flush_timeout
.tv_sec
!= 0 &&
834 timeval_minus_msec(&babel_ifp
->flush_timeout
, &babel_now
) < msecs
)
836 set_timeout(&babel_ifp
->flush_timeout
, msecs
);
840 schedule_unicast_flush(unsigned msecs
)
842 if(!unicast_neighbour
)
844 if(unicast_flush_timeout
.tv_sec
!= 0 &&
845 timeval_minus_msec(&unicast_flush_timeout
, &babel_now
) < msecs
)
847 unicast_flush_timeout
.tv_usec
= (babel_now
.tv_usec
+ msecs
* 1000) %1000000;
848 unicast_flush_timeout
.tv_sec
=
849 babel_now
.tv_sec
+ (babel_now
.tv_usec
/ 1000 + msecs
) / 1000;
853 ensure_space(struct interface
*ifp
, int space
)
855 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
856 if(babel_ifp
->bufsize
- babel_ifp
->buffered
< space
)
861 start_message(struct interface
*ifp
, int type
, int len
)
863 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
864 if(babel_ifp
->bufsize
- babel_ifp
->buffered
< len
+ 2)
866 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = type
;
867 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = len
;
871 end_message(struct interface
*ifp
, int type
, int bytes
)
873 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
874 assert(babel_ifp
->buffered
>= bytes
+ 2 &&
875 babel_ifp
->sendbuf
[babel_ifp
->buffered
- bytes
- 2] == type
&&
876 babel_ifp
->sendbuf
[babel_ifp
->buffered
- bytes
- 1] == bytes
);
881 accumulate_byte(struct interface
*ifp
, unsigned char value
)
883 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
884 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = value
;
888 accumulate_short(struct interface
*ifp
, unsigned short value
)
890 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
891 DO_HTONS(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
);
892 babel_ifp
->buffered
+= 2;
896 accumulate_int(struct interface
*ifp
, unsigned int value
)
898 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
899 DO_HTONL(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
);
900 babel_ifp
->buffered
+= 4;
904 accumulate_bytes(struct interface
*ifp
,
905 const unsigned char *value
, unsigned len
)
907 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
908 memcpy(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
, len
);
909 babel_ifp
->buffered
+= len
;
913 start_unicast_message(struct neighbour
*neigh
, int type
, int len
)
915 if(unicast_neighbour
) {
916 if(neigh
!= unicast_neighbour
||
917 unicast_buffered
+ len
+ 2 >=
918 MIN(UNICAST_BUFSIZE
, babel_get_if_nfo(neigh
->ifp
)->bufsize
))
922 unicast_buffer
= malloc(UNICAST_BUFSIZE
);
923 if(!unicast_buffer
) {
924 flog_err(EC_BABEL_MEMORY
, "malloc(unicast_buffer): %s",
925 safe_strerror(errno
));
929 unicast_neighbour
= neigh
;
931 unicast_buffer
[unicast_buffered
++] = type
;
932 unicast_buffer
[unicast_buffered
++] = len
;
937 end_unicast_message(struct neighbour
*neigh
, int type
, int bytes
)
939 assert(unicast_neighbour
== neigh
&& unicast_buffered
>= bytes
+ 2 &&
940 unicast_buffer
[unicast_buffered
- bytes
- 2] == type
&&
941 unicast_buffer
[unicast_buffered
- bytes
- 1] == bytes
);
942 schedule_unicast_flush(jitter(babel_get_if_nfo(neigh
->ifp
), 0));
946 accumulate_unicast_byte(struct neighbour
*neigh
, unsigned char value
)
948 unicast_buffer
[unicast_buffered
++] = value
;
952 accumulate_unicast_short(struct neighbour
*neigh
, unsigned short value
)
954 DO_HTONS(unicast_buffer
+ unicast_buffered
, value
);
955 unicast_buffered
+= 2;
959 accumulate_unicast_int(struct neighbour
*neigh
, unsigned int value
)
961 DO_HTONL(unicast_buffer
+ unicast_buffered
, value
);
962 unicast_buffered
+= 4;
966 accumulate_unicast_bytes(struct neighbour
*neigh
,
967 const unsigned char *value
, unsigned len
)
969 memcpy(unicast_buffer
+ unicast_buffered
, value
, len
);
970 unicast_buffered
+= len
;
974 send_ack(struct neighbour
*neigh
, unsigned short nonce
, unsigned short interval
)
977 debugf(BABEL_DEBUG_COMMON
,"Sending ack (%04x) to %s on %s.",
978 nonce
, format_address(neigh
->address
), neigh
->ifp
->name
);
979 rc
= start_unicast_message(neigh
, MESSAGE_ACK
, 2); if(rc
< 0) return;
980 accumulate_unicast_short(neigh
, nonce
);
981 end_unicast_message(neigh
, MESSAGE_ACK
, 2);
982 /* Roughly yields a value no larger than 3/2, so this meets the deadline */
983 schedule_unicast_flush(roughly(interval
* 6));
987 send_hello_noupdate(struct interface
*ifp
, unsigned interval
)
989 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
990 /* This avoids sending multiple hellos in a single packet, which breaks
991 link quality estimation. */
992 if(babel_ifp
->buffered_hello
>= 0)
995 babel_ifp
->hello_seqno
= seqno_plus(babel_ifp
->hello_seqno
, 1);
996 set_timeout(&babel_ifp
->hello_timeout
, babel_ifp
->hello_interval
);
1001 debugf(BABEL_DEBUG_COMMON
,"Sending hello %d (%d) to %s.",
1002 babel_ifp
->hello_seqno
, interval
, ifp
->name
);
1004 start_message(ifp
, MESSAGE_HELLO
,
1005 (babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) ? 12 : 6);
1006 babel_ifp
->buffered_hello
= babel_ifp
->buffered
- 2;
1007 accumulate_short(ifp
, 0);
1008 accumulate_short(ifp
, babel_ifp
->hello_seqno
);
1009 accumulate_short(ifp
, interval
> 0xFFFF ? 0xFFFF : interval
);
1010 if(babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) {
1011 /* Sub-TLV containing the local time of emission. We use a
1012 Pad4 sub-TLV, which we'll fill just before sending. */
1013 accumulate_byte(ifp
, SUBTLV_PADN
);
1014 accumulate_byte(ifp
, 4);
1015 accumulate_int(ifp
, 0);
1017 end_message(ifp
, MESSAGE_HELLO
,
1018 (babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) ? 12 : 6);
1022 send_hello(struct interface
*ifp
)
1024 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1025 send_hello_noupdate(ifp
, (babel_ifp
->hello_interval
+ 9) / 10);
1026 /* Send full IHU every 3 hellos, and marginal IHU each time */
1027 if(babel_ifp
->hello_seqno
% 3 == 0)
1028 send_ihu(NULL
, ifp
);
1030 send_marginal_ihu(ifp
);
1034 flush_unicast(int dofree
)
1036 struct sockaddr_in6 sin6
;
1039 if(unicast_buffered
== 0)
1042 if(!if_up(unicast_neighbour
->ifp
))
1045 /* Preserve ordering of messages */
1046 flushbuf(unicast_neighbour
->ifp
);
1048 if(check_bucket(unicast_neighbour
->ifp
)) {
1049 memset(&sin6
, 0, sizeof(sin6
));
1050 sin6
.sin6_family
= AF_INET6
;
1051 memcpy(&sin6
.sin6_addr
, unicast_neighbour
->address
, 16);
1052 sin6
.sin6_port
= htons(protocol_port
);
1053 sin6
.sin6_scope_id
= unicast_neighbour
->ifp
->ifindex
;
1054 DO_HTONS(packet_header
+ 2, unicast_buffered
);
1055 fill_rtt_message(unicast_neighbour
->ifp
);
1056 rc
= babel_send(protocol_socket
,
1057 packet_header
, sizeof(packet_header
),
1058 unicast_buffer
, unicast_buffered
,
1059 (struct sockaddr
*)&sin6
, sizeof(sin6
));
1061 flog_err(EC_BABEL_PACKET
, "send(unicast): %s",
1062 safe_strerror(errno
));
1064 flog_err(EC_BABEL_PACKET
,
1065 "Bucket full, dropping unicast packet to %s if %s.",
1066 format_address(unicast_neighbour
->address
),
1067 unicast_neighbour
->ifp
->name
);
1071 VALGRIND_MAKE_MEM_UNDEFINED(unicast_buffer
, UNICAST_BUFSIZE
);
1072 unicast_buffered
= 0;
1073 if(dofree
&& unicast_buffer
) {
1074 free(unicast_buffer
);
1075 unicast_buffer
= NULL
;
1077 unicast_neighbour
= NULL
;
1078 unicast_flush_timeout
.tv_sec
= 0;
1079 unicast_flush_timeout
.tv_usec
= 0;
1083 really_send_update(struct interface
*ifp
,
1084 const unsigned char *id
,
1085 const unsigned char *prefix
, unsigned char plen
,
1086 unsigned short seqno
, unsigned short metric
,
1087 unsigned char *channels
, int channels_len
)
1089 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1090 int add_metric
, v4
, real_plen
, omit
= 0;
1091 const unsigned char *real_prefix
;
1092 unsigned short flags
= 0;
1095 if(diversity_kind
!= DIVERSITY_CHANNEL
)
1098 channels_size
= channels_len
>= 0 ? channels_len
+ 2 : 0;
1103 add_metric
= output_filter(id
, prefix
, plen
, ifp
->ifindex
);
1104 if(add_metric
>= INFINITY
)
1107 metric
= MIN(metric
+ add_metric
, INFINITY
);
1109 ensure_space(ifp
, 20 + 12 + 28);
1111 v4
= plen
>= 96 && v4mapped(prefix
);
1114 if(!babel_ifp
->ipv4
)
1116 if(!babel_ifp
->have_buffered_nh
||
1117 memcmp(babel_ifp
->buffered_nh
, babel_ifp
->ipv4
, 4) != 0) {
1118 start_message(ifp
, MESSAGE_NH
, 6);
1119 accumulate_byte(ifp
, 1);
1120 accumulate_byte(ifp
, 0);
1121 accumulate_bytes(ifp
, babel_ifp
->ipv4
, 4);
1122 end_message(ifp
, MESSAGE_NH
, 6);
1123 memcpy(babel_ifp
->buffered_nh
, babel_ifp
->ipv4
, 4);
1124 babel_ifp
->have_buffered_nh
= 1;
1127 real_prefix
= prefix
+ 12;
1128 real_plen
= plen
- 96;
1130 if(babel_ifp
->have_buffered_prefix
) {
1131 while(omit
< plen
/ 8 &&
1132 babel_ifp
->buffered_prefix
[omit
] == prefix
[omit
])
1135 if(!babel_ifp
->have_buffered_prefix
|| plen
>= 48)
1137 real_prefix
= prefix
;
1141 if(!babel_ifp
->have_buffered_id
1142 || memcmp(id
, babel_ifp
->buffered_id
, 8) != 0) {
1143 if(real_plen
== 128 && memcmp(real_prefix
+ 8, id
, 8) == 0) {
1146 start_message(ifp
, MESSAGE_ROUTER_ID
, 10);
1147 accumulate_short(ifp
, 0);
1148 accumulate_bytes(ifp
, id
, 8);
1149 end_message(ifp
, MESSAGE_ROUTER_ID
, 10);
1151 memcpy(babel_ifp
->buffered_id
, id
, sizeof(babel_ifp
->buffered_id
));
1152 babel_ifp
->have_buffered_id
= 1;
1155 start_message(ifp
, MESSAGE_UPDATE
, 10 + (real_plen
+ 7) / 8 - omit
+
1157 accumulate_byte(ifp
, v4
? 1 : 2);
1158 accumulate_byte(ifp
, flags
);
1159 accumulate_byte(ifp
, real_plen
);
1160 accumulate_byte(ifp
, omit
);
1161 accumulate_short(ifp
, (babel_ifp
->update_interval
+ 5) / 10);
1162 accumulate_short(ifp
, seqno
);
1163 accumulate_short(ifp
, metric
);
1164 accumulate_bytes(ifp
, real_prefix
+ omit
, (real_plen
+ 7) / 8 - omit
);
1165 /* Note that an empty channels TLV is different from no such TLV. */
1166 if(channels_len
>= 0) {
1167 accumulate_byte(ifp
, 2);
1168 accumulate_byte(ifp
, channels_len
);
1170 if (channels
&& channels_len
> 0)
1171 accumulate_bytes(ifp
, channels
, channels_len
);
1173 end_message(ifp
, MESSAGE_UPDATE
, 10 + (real_plen
+ 7) / 8 - omit
+
1177 memcpy(babel_ifp
->buffered_prefix
, prefix
, 16);
1178 babel_ifp
->have_buffered_prefix
= 1;
1183 compare_buffered_updates(const void *av
, const void *bv
)
1185 const struct buffered_update
*a
= av
, *b
= bv
;
1186 int rc
, v4a
, v4b
, ma
, mb
;
1188 rc
= memcmp(a
->id
, b
->id
, 8);
1192 v4a
= (a
->plen
>= 96 && v4mapped(a
->prefix
));
1193 v4b
= (b
->plen
>= 96 && v4mapped(b
->prefix
));
1200 ma
= (!v4a
&& a
->plen
== 128 && memcmp(a
->prefix
+ 8, a
->id
, 8) == 0);
1201 mb
= (!v4b
&& b
->plen
== 128 && memcmp(b
->prefix
+ 8, b
->id
, 8) == 0);
1208 if(a
->plen
< b
->plen
)
1210 else if(a
->plen
> b
->plen
)
1213 return memcmp(a
->prefix
, b
->prefix
, 16);
1217 flushupdates(struct interface
*ifp
)
1219 babel_interface_nfo
*babel_ifp
= NULL
;
1220 struct xroute
*xroute
;
1221 struct babel_route
*route
;
1222 const unsigned char *last_prefix
= NULL
;
1223 unsigned char last_plen
= 0xFF;
1227 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1228 struct interface
*ifp_aux
;
1229 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1230 flushupdates(ifp_aux
);
1234 babel_ifp
= babel_get_if_nfo(ifp
);
1235 if(babel_ifp
->num_buffered_updates
> 0) {
1236 struct buffered_update
*b
= babel_ifp
->buffered_updates
;
1237 int n
= babel_ifp
->num_buffered_updates
;
1239 babel_ifp
->buffered_updates
= NULL
;
1240 babel_ifp
->update_bufsize
= 0;
1241 babel_ifp
->num_buffered_updates
= 0;
1246 debugf(BABEL_DEBUG_COMMON
," (flushing %d buffered updates on %s (%d))",
1247 n
, ifp
->name
, ifp
->ifindex
);
1249 /* In order to send fewer update messages, we want to send updates
1250 with the same router-id together, with IPv6 going out before IPv4. */
1252 for(i
= 0; i
< n
; i
++) {
1253 route
= find_installed_route(b
[i
].prefix
, b
[i
].plen
);
1255 memcpy(b
[i
].id
, route
->src
->id
, 8);
1257 memcpy(b
[i
].id
, myid
, 8);
1260 qsort(b
, n
, sizeof(struct buffered_update
), compare_buffered_updates
);
1262 for(i
= 0; i
< n
; i
++) {
1263 /* The same update may be scheduled multiple times before it is
1264 sent out. Since our buffer is now sorted, it is enough to
1265 compare with the previous update. */
1268 if(b
[i
].plen
== last_plen
&&
1269 memcmp(b
[i
].prefix
, last_prefix
, 16) == 0)
1273 xroute
= find_xroute(b
[i
].prefix
, b
[i
].plen
);
1274 route
= find_installed_route(b
[i
].prefix
, b
[i
].plen
);
1276 if(xroute
&& (!route
|| xroute
->metric
<= kernel_metric
)) {
1277 really_send_update(ifp
, myid
,
1278 xroute
->prefix
, xroute
->plen
,
1279 myseqno
, xroute
->metric
,
1281 last_prefix
= xroute
->prefix
;
1282 last_plen
= xroute
->plen
;
1284 unsigned char channels
[DIVERSITY_HOPS
];
1286 struct interface
*route_ifp
= route
->neigh
->ifp
;
1287 struct babel_interface
*babel_route_ifp
= NULL
;
1288 unsigned short metric
;
1289 unsigned short seqno
;
1291 seqno
= route
->seqno
;
1293 route_interferes(route
, ifp
) ?
1294 route_metric(route
) :
1295 route_metric_noninterfering(route
);
1297 if(metric
< INFINITY
)
1298 satisfy_request(route
->src
->prefix
, route
->src
->plen
,
1299 seqno
, route
->src
->id
, ifp
);
1300 if((babel_ifp
->flags
& BABEL_IF_SPLIT_HORIZON
) &&
1301 route
->neigh
->ifp
== ifp
)
1304 babel_route_ifp
= babel_get_if_nfo(route_ifp
);
1305 if(babel_route_ifp
->channel
==BABEL_IF_CHANNEL_NONINTERFERING
) {
1306 memcpy(channels
, route
->channels
, DIVERSITY_HOPS
);
1308 if(babel_route_ifp
->channel
== BABEL_IF_CHANNEL_UNKNOWN
)
1309 channels
[0] = BABEL_IF_CHANNEL_INTERFERING
;
1311 assert(babel_route_ifp
->channel
> 0 &&
1312 babel_route_ifp
->channel
<= 255);
1313 channels
[0] = babel_route_ifp
->channel
;
1315 memcpy(channels
+ 1, route
->channels
, DIVERSITY_HOPS
- 1);
1318 chlen
= channels_len(channels
);
1319 really_send_update(ifp
, route
->src
->id
,
1324 update_source(route
->src
, seqno
, metric
);
1325 last_prefix
= route
->src
->prefix
;
1326 last_plen
= route
->src
->plen
;
1328 /* There's no route for this prefix. This can happen shortly
1329 after an xroute has been retracted, so send a retraction. */
1330 really_send_update(ifp
, myid
, b
[i
].prefix
, b
[i
].plen
,
1331 myseqno
, INFINITY
, NULL
, -1);
1334 schedule_flush_now(ifp
);
1338 babel_ifp
->update_flush_timeout
.tv_sec
= 0;
1339 babel_ifp
->update_flush_timeout
.tv_usec
= 0;
1343 schedule_update_flush(struct interface
*ifp
, int urgent
)
1345 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1347 msecs
= update_jitter(babel_ifp
, urgent
);
1348 if(babel_ifp
->update_flush_timeout
.tv_sec
!= 0 &&
1349 timeval_minus_msec(&babel_ifp
->update_flush_timeout
, &babel_now
) < msecs
)
1351 set_timeout(&babel_ifp
->update_flush_timeout
, msecs
);
1355 buffer_update(struct interface
*ifp
,
1356 const unsigned char *prefix
, unsigned char plen
)
1358 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1359 if(babel_ifp
->num_buffered_updates
> 0 &&
1360 babel_ifp
->num_buffered_updates
>= babel_ifp
->update_bufsize
)
1363 if(babel_ifp
->update_bufsize
== 0) {
1365 assert(babel_ifp
->buffered_updates
== NULL
);
1366 /* Allocate enough space to hold a full update. Since the
1367 number of installed routes will grow over time, make sure we
1368 have enough space to send a full-ish frame. */
1369 n
= installed_routes_estimate() + xroutes_estimate() + 4;
1370 n
= MAX(n
, babel_ifp
->bufsize
/ 16);
1372 babel_ifp
->buffered_updates
= malloc(n
*sizeof(struct buffered_update
));
1373 if(babel_ifp
->buffered_updates
== NULL
) {
1374 flog_err(EC_BABEL_MEMORY
, "malloc(buffered_updates): %s",
1375 safe_strerror(errno
));
1377 /* Try again with a tiny buffer. */
1383 babel_ifp
->update_bufsize
= n
;
1384 babel_ifp
->num_buffered_updates
= 0;
1387 memcpy(babel_ifp
->buffered_updates
[babel_ifp
->num_buffered_updates
].prefix
,
1389 babel_ifp
->buffered_updates
[babel_ifp
->num_buffered_updates
].plen
= plen
;
1390 babel_ifp
->num_buffered_updates
++;
1394 send_update(struct interface
*ifp
, int urgent
,
1395 const unsigned char *prefix
, unsigned char plen
)
1397 babel_interface_nfo
*babel_ifp
= NULL
;
1400 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1401 struct interface
*ifp_aux
;
1402 struct babel_route
*route
;
1403 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1404 send_update(ifp_aux
, urgent
, prefix
, plen
);
1406 /* Since flushupdates only deals with non-wildcard interfaces, we
1407 need to do this now. */
1408 route
= find_installed_route(prefix
, plen
);
1409 if(route
&& route_metric(route
) < INFINITY
)
1410 satisfy_request(prefix
, plen
, route
->src
->seqno
, route
->src
->id
,
1419 babel_ifp
= babel_get_if_nfo(ifp
);
1421 debugf(BABEL_DEBUG_COMMON
,"Sending update to %s for %s.",
1422 ifp
->name
, format_prefix(prefix
, plen
));
1423 buffer_update(ifp
, prefix
, plen
);
1425 struct route_stream
*routes
= NULL
;
1426 send_self_update(ifp
);
1427 debugf(BABEL_DEBUG_COMMON
,"Sending update to %s for any.", ifp
->name
);
1428 routes
= route_stream(1);
1431 struct babel_route
*route
= route_stream_next(routes
);
1434 buffer_update(ifp
, route
->src
->prefix
, route
->src
->plen
);
1436 route_stream_done(routes
);
1438 flog_err(EC_BABEL_MEMORY
, "Couldn't allocate route stream.");
1440 set_timeout(&babel_ifp
->update_timeout
, babel_ifp
->update_interval
);
1441 babel_ifp
->last_update_time
= babel_now
.tv_sec
;
1443 schedule_update_flush(ifp
, urgent
);
1447 send_update_resend(struct interface
*ifp
,
1448 const unsigned char *prefix
, unsigned char plen
)
1450 assert(prefix
!= NULL
);
1452 send_update(ifp
, 1, prefix
, plen
);
1453 record_resend(RESEND_UPDATE
, prefix
, plen
, 0, NULL
, NULL
, resend_delay
);
1457 send_wildcard_retraction(struct interface
*ifp
)
1459 babel_interface_nfo
*babel_ifp
= NULL
;
1461 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1462 struct interface
*ifp_aux
;
1463 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1464 send_wildcard_retraction(ifp_aux
);
1471 babel_ifp
= babel_get_if_nfo(ifp
);
1472 start_message(ifp
, MESSAGE_UPDATE
, 10);
1473 accumulate_byte(ifp
, 0);
1474 accumulate_byte(ifp
, 0x40);
1475 accumulate_byte(ifp
, 0);
1476 accumulate_byte(ifp
, 0);
1477 accumulate_short(ifp
, 0xFFFF);
1478 accumulate_short(ifp
, myseqno
);
1479 accumulate_short(ifp
, 0xFFFF);
1480 end_message(ifp
, MESSAGE_UPDATE
, 10);
1482 babel_ifp
->have_buffered_id
= 0;
1486 update_myseqno(void)
1488 myseqno
= seqno_plus(myseqno
, 1);
1492 send_self_update(struct interface
*ifp
)
1494 struct xroute_stream
*xroutes
;
1496 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1497 struct interface
*ifp_aux
;
1498 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1501 send_self_update(ifp_aux
);
1506 debugf(BABEL_DEBUG_COMMON
,"Sending self update to %s.", ifp
->name
);
1507 xroutes
= xroute_stream();
1510 struct xroute
*xroute
= xroute_stream_next(xroutes
);
1511 if(xroute
== NULL
) break;
1512 send_update(ifp
, 0, xroute
->prefix
, xroute
->plen
);
1514 xroute_stream_done(xroutes
);
1516 flog_err(EC_BABEL_MEMORY
, "Couldn't allocate xroute stream.");
1521 send_ihu(struct neighbour
*neigh
, struct interface
*ifp
)
1523 babel_interface_nfo
*babel_ifp
= NULL
;
1524 int rxcost
, interval
;
1529 if(neigh
== NULL
&& ifp
== NULL
) {
1530 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1531 struct interface
*ifp_aux
;
1532 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1535 send_ihu(NULL
, ifp_aux
);
1541 struct neighbour
*ngh
;
1542 FOR_ALL_NEIGHBOURS(ngh
) {
1550 if(ifp
&& neigh
->ifp
!= ifp
)
1554 babel_ifp
= babel_get_if_nfo(ifp
);
1558 rxcost
= neighbour_rxcost(neigh
);
1559 interval
= (babel_ifp
->hello_interval
* 3 + 9) / 10;
1561 /* Conceptually, an IHU is a unicast message. We usually send them as
1562 multicast, since this allows aggregation into a single packet and
1563 avoids an ARP exchange. If we already have a unicast message queued
1564 for this neighbour, however, we might as well piggyback the IHU. */
1565 debugf(BABEL_DEBUG_COMMON
,"Sending %sihu %d on %s to %s.",
1566 unicast_neighbour
== neigh
? "unicast " : "",
1569 format_address(neigh
->address
));
1571 ll
= linklocal(neigh
->address
);
1573 if((babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) && neigh
->hello_send_us
1574 /* Checks whether the RTT data is not too old to be sent. */
1575 && timeval_minus_msec(&babel_now
,
1576 &neigh
->hello_rtt_receive_time
) < 1000000) {
1579 neigh
->hello_send_us
= 0;
1583 /* The length depends on the format of the address, and then an
1584 optional 10-bytes sub-TLV for timestamps (used to compute a RTT). */
1585 msglen
= (ll
? 14 : 22) + (send_rtt_data
? 10 : 0);
1587 if(unicast_neighbour
!= neigh
) {
1588 start_message(ifp
, MESSAGE_IHU
, msglen
);
1589 accumulate_byte(ifp
, ll
? 3 : 2);
1590 accumulate_byte(ifp
, 0);
1591 accumulate_short(ifp
, rxcost
);
1592 accumulate_short(ifp
, interval
);
1594 accumulate_bytes(ifp
, neigh
->address
+ 8, 8);
1596 accumulate_bytes(ifp
, neigh
->address
, 16);
1597 if (send_rtt_data
) {
1598 accumulate_byte(ifp
, SUBTLV_TIMESTAMP
);
1599 accumulate_byte(ifp
, 8);
1600 accumulate_int(ifp
, neigh
->hello_send_us
);
1601 accumulate_int(ifp
, time_us(neigh
->hello_rtt_receive_time
));
1603 end_message(ifp
, MESSAGE_IHU
, msglen
);
1606 rc
= start_unicast_message(neigh
, MESSAGE_IHU
, msglen
);
1608 accumulate_unicast_byte(neigh
, ll
? 3 : 2);
1609 accumulate_unicast_byte(neigh
, 0);
1610 accumulate_unicast_short(neigh
, rxcost
);
1611 accumulate_unicast_short(neigh
, interval
);
1613 accumulate_unicast_bytes(neigh
, neigh
->address
+ 8, 8);
1615 accumulate_unicast_bytes(neigh
, neigh
->address
, 16);
1616 if (send_rtt_data
) {
1617 accumulate_unicast_byte(neigh
, SUBTLV_TIMESTAMP
);
1618 accumulate_unicast_byte(neigh
, 8);
1619 accumulate_unicast_int(neigh
, neigh
->hello_send_us
);
1620 accumulate_unicast_int(neigh
,
1621 time_us(neigh
->hello_rtt_receive_time
));
1623 end_unicast_message(neigh
, MESSAGE_IHU
, msglen
);
1627 /* Send IHUs to all marginal neighbours */
1629 send_marginal_ihu(struct interface
*ifp
)
1631 struct neighbour
*neigh
;
1632 FOR_ALL_NEIGHBOURS(neigh
) {
1633 if(ifp
&& neigh
->ifp
!= ifp
)
1635 if(neigh
->txcost
>= 384 || (neigh
->reach
& 0xF000) != 0xF000)
1636 send_ihu(neigh
, ifp
);
1641 send_request(struct interface
*ifp
,
1642 const unsigned char *prefix
, unsigned char plen
)
1647 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1648 struct interface
*ifp_aux
;
1649 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1652 send_request(ifp_aux
, prefix
, plen
);
1657 /* make sure any buffered updates go out before this request. */
1663 debugf(BABEL_DEBUG_COMMON
,"sending request to %s for %s.",
1664 ifp
->name
, prefix
? format_prefix(prefix
, plen
) : "any");
1665 v4
= plen
>= 96 && v4mapped(prefix
);
1666 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1667 len
= !prefix
? 2 : 2 + pb
;
1669 start_message(ifp
, MESSAGE_REQUEST
, len
);
1670 accumulate_byte(ifp
, !prefix
? 0 : v4
? 1 : 2);
1671 accumulate_byte(ifp
, !prefix
? 0 : v4
? plen
- 96 : plen
);
1674 accumulate_bytes(ifp
, prefix
+ 12, pb
);
1676 accumulate_bytes(ifp
, prefix
, pb
);
1678 end_message(ifp
, MESSAGE_REQUEST
, len
);
1682 send_unicast_request(struct neighbour
*neigh
,
1683 const unsigned char *prefix
, unsigned char plen
)
1685 int rc
, v4
, pb
, len
;
1687 /* make sure any buffered updates go out before this request. */
1688 flushupdates(neigh
->ifp
);
1690 debugf(BABEL_DEBUG_COMMON
,"sending unicast request to %s for %s.",
1691 format_address(neigh
->address
),
1692 prefix
? format_prefix(prefix
, plen
) : "any");
1693 v4
= plen
>= 96 && v4mapped(prefix
);
1694 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1695 len
= !prefix
? 2 : 2 + pb
;
1697 rc
= start_unicast_message(neigh
, MESSAGE_REQUEST
, len
);
1699 accumulate_unicast_byte(neigh
, !prefix
? 0 : v4
? 1 : 2);
1700 accumulate_unicast_byte(neigh
, !prefix
? 0 : v4
? plen
- 96 : plen
);
1703 accumulate_unicast_bytes(neigh
, prefix
+ 12, pb
);
1705 accumulate_unicast_bytes(neigh
, prefix
, pb
);
1707 end_unicast_message(neigh
, MESSAGE_REQUEST
, len
);
1711 send_multihop_request(struct interface
*ifp
,
1712 const unsigned char *prefix
, unsigned char plen
,
1713 unsigned short seqno
, const unsigned char *id
,
1714 unsigned short hop_count
)
1718 /* Make sure any buffered updates go out before this request. */
1722 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1723 struct interface
*ifp_aux
;
1724 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1727 send_multihop_request(ifp_aux
, prefix
, plen
, seqno
, id
, hop_count
);
1735 debugf(BABEL_DEBUG_COMMON
,"Sending request (%d) on %s for %s.",
1736 hop_count
, ifp
->name
, format_prefix(prefix
, plen
));
1737 v4
= plen
>= 96 && v4mapped(prefix
);
1738 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1741 start_message(ifp
, MESSAGE_MH_REQUEST
, len
);
1742 accumulate_byte(ifp
, v4
? 1 : 2);
1743 accumulate_byte(ifp
, v4
? plen
- 96 : plen
);
1744 accumulate_short(ifp
, seqno
);
1745 accumulate_byte(ifp
, hop_count
);
1746 accumulate_byte(ifp
, 0);
1747 accumulate_bytes(ifp
, id
, 8);
1750 accumulate_bytes(ifp
, prefix
+ 12, pb
);
1752 accumulate_bytes(ifp
, prefix
, pb
);
1754 end_message(ifp
, MESSAGE_MH_REQUEST
, len
);
1758 send_unicast_multihop_request(struct neighbour
*neigh
,
1759 const unsigned char *prefix
, unsigned char plen
,
1760 unsigned short seqno
, const unsigned char *id
,
1761 unsigned short hop_count
)
1763 int rc
, v4
, pb
, len
;
1765 /* Make sure any buffered updates go out before this request. */
1766 flushupdates(neigh
->ifp
);
1768 debugf(BABEL_DEBUG_COMMON
,"Sending multi-hop request to %s for %s (%d hops).",
1769 format_address(neigh
->address
),
1770 format_prefix(prefix
, plen
), hop_count
);
1771 v4
= plen
>= 96 && v4mapped(prefix
);
1772 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1775 rc
= start_unicast_message(neigh
, MESSAGE_MH_REQUEST
, len
);
1777 accumulate_unicast_byte(neigh
, v4
? 1 : 2);
1778 accumulate_unicast_byte(neigh
, v4
? plen
- 96 : plen
);
1779 accumulate_unicast_short(neigh
, seqno
);
1780 accumulate_unicast_byte(neigh
, hop_count
);
1781 accumulate_unicast_byte(neigh
, 0);
1782 accumulate_unicast_bytes(neigh
, id
, 8);
1785 accumulate_unicast_bytes(neigh
, prefix
+ 12, pb
);
1787 accumulate_unicast_bytes(neigh
, prefix
, pb
);
1789 end_unicast_message(neigh
, MESSAGE_MH_REQUEST
, len
);
1793 send_request_resend(struct neighbour
*neigh
,
1794 const unsigned char *prefix
, unsigned char plen
,
1795 unsigned short seqno
, unsigned char *id
)
1798 send_unicast_multihop_request(neigh
, prefix
, plen
, seqno
, id
, 127);
1800 send_multihop_request(NULL
, prefix
, plen
, seqno
, id
, 127);
1802 record_resend(RESEND_REQUEST
, prefix
, plen
, seqno
, id
,
1803 neigh
? neigh
->ifp
: NULL
, resend_delay
);
1807 handle_request(struct neighbour
*neigh
, const unsigned char *prefix
,
1808 unsigned char plen
, unsigned char hop_count
,
1809 unsigned short seqno
, const unsigned char *id
)
1811 struct xroute
*xroute
;
1812 struct babel_route
*route
;
1813 struct neighbour
*successor
= NULL
;
1815 xroute
= find_xroute(prefix
, plen
);
1816 route
= find_installed_route(prefix
, plen
);
1818 if(xroute
&& (!route
|| xroute
->metric
<= kernel_metric
)) {
1819 if(hop_count
> 0 && memcmp(id
, myid
, 8) == 0) {
1820 if(seqno_compare(seqno
, myseqno
) > 0) {
1821 if(seqno_minus(seqno
, myseqno
) > 100) {
1822 /* Hopelessly out-of-date request */
1828 send_update(neigh
->ifp
, 1, prefix
, plen
);
1833 (memcmp(id
, route
->src
->id
, 8) != 0 ||
1834 seqno_compare(seqno
, route
->seqno
) <= 0)) {
1835 send_update(neigh
->ifp
, 1, prefix
, plen
);
1842 if(route
&& memcmp(id
, route
->src
->id
, 8) == 0 &&
1843 seqno_minus(seqno
, route
->seqno
) > 100) {
1844 /* Hopelessly out-of-date */
1848 if(request_redundant(neigh
->ifp
, prefix
, plen
, seqno
, id
))
1851 /* Let's try to forward this request. */
1852 if(route
&& route_metric(route
) < INFINITY
)
1853 successor
= route
->neigh
;
1855 if(!successor
|| successor
== neigh
) {
1856 /* We were about to forward a request to its requestor. Try to
1857 find a different neighbour to forward the request to. */
1858 struct babel_route
*other_route
;
1860 other_route
= find_best_route(prefix
, plen
, 0, neigh
);
1861 if(other_route
&& route_metric(other_route
) < INFINITY
)
1862 successor
= other_route
->neigh
;
1865 if(!successor
|| successor
== neigh
)
1869 send_unicast_multihop_request(successor
, prefix
, plen
, seqno
, id
,
1871 record_resend(RESEND_REQUEST
, prefix
, plen
, seqno
, id
,