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
);
131 parse_update_subtlv(const unsigned char *a
, int alen
,
132 unsigned char *channels
)
134 int type
, len
, i
= 0;
138 if(type
== SUBTLV_PAD1
) {
144 flog_err(EC_BABEL_PACKET
, "Received truncated attributes.");
149 flog_err(EC_BABEL_PACKET
, "Received truncated attributes.");
153 if(type
== SUBTLV_PADN
) {
155 } else if(type
== SUBTLV_DIVERSITY
) {
156 if(len
> DIVERSITY_HOPS
) {
157 flog_err(EC_BABEL_PACKET
,
158 "Received overlong channel information (%d > %d).n",
159 len
, DIVERSITY_HOPS
);
160 len
= DIVERSITY_HOPS
;
162 if(memchr(a
+ i
+ 2, 0, len
) != NULL
) {
164 flog_err(EC_BABEL_PACKET
, "Channel information contains 0!");
167 memset(channels
, 0, DIVERSITY_HOPS
);
168 memcpy(channels
, a
+ i
+ 2, len
);
170 debugf(BABEL_DEBUG_COMMON
,
171 "Received unknown route attribute %d.", type
);
179 parse_hello_subtlv(const unsigned char *a
, int alen
,
180 unsigned int *hello_send_us
)
182 int type
, len
, i
= 0, ret
= 0;
186 if(type
== SUBTLV_PAD1
) {
192 flog_err(EC_BABEL_PACKET
,
193 "Received truncated sub-TLV on Hello message.");
198 flog_err(EC_BABEL_PACKET
,
199 "Received truncated sub-TLV on Hello message.");
203 if(type
== SUBTLV_PADN
) {
205 } else if(type
== SUBTLV_TIMESTAMP
) {
207 DO_NTOHL(*hello_send_us
, a
+ i
+ 2);
210 flog_err(EC_BABEL_PACKET
,
211 "Received incorrect RTT sub-TLV on Hello message.");
214 debugf(BABEL_DEBUG_COMMON
,
215 "Received unknown Hello sub-TLV type %d.", type
);
224 parse_ihu_subtlv(const unsigned char *a
, int alen
,
225 unsigned int *hello_send_us
,
226 unsigned int *hello_rtt_receive_time
)
228 int type
, len
, i
= 0, ret
= 0;
232 if(type
== SUBTLV_PAD1
) {
238 flog_err(EC_BABEL_PACKET
,
239 "Received truncated sub-TLV on IHU message.");
244 flog_err(EC_BABEL_PACKET
,
245 "Received truncated sub-TLV on IHU message.");
249 if(type
== SUBTLV_PADN
) {
251 } else if(type
== SUBTLV_TIMESTAMP
) {
253 DO_NTOHL(*hello_send_us
, a
+ i
+ 2);
254 DO_NTOHL(*hello_rtt_receive_time
, a
+ i
+ 6);
258 flog_err(EC_BABEL_PACKET
,
259 "Received incorrect RTT sub-TLV on IHU message.");
262 debugf(BABEL_DEBUG_COMMON
,
263 "Received unknown IHU sub-TLV type %d.", type
);
272 network_address(int ae
, const unsigned char *a
, unsigned int len
,
275 return network_prefix(ae
, -1, 0, a
, NULL
, len
, a_r
);
279 channels_len(unsigned char *channels
)
281 unsigned char *p
= memchr(channels
, 0, DIVERSITY_HOPS
);
282 return p
? (p
- channels
) : DIVERSITY_HOPS
;
285 /* Check, that the provided frame consists of a valid Babel packet header
286 followed by a sequence of TLVs. TLVs of known types are also checked to meet
287 minimum length constraints defined for each. Return 0 for no errors. */
289 babel_packet_examin(const unsigned char *packet
, int packetlen
)
291 unsigned i
= 0, bodylen
;
292 const unsigned char *message
;
293 unsigned char type
, len
;
295 if(packetlen
< 4 || packet
[0] != 42 || packet
[1] != 2)
297 DO_NTOHS(bodylen
, packet
+ 2);
299 message
= packet
+ 4 + i
;
301 if(type
== MESSAGE_PAD1
) {
305 if(i
+ 1 > bodylen
) {
306 debugf(BABEL_DEBUG_COMMON
,"Received truncated message.");
310 if(i
+ len
> bodylen
) {
311 debugf(BABEL_DEBUG_COMMON
,"Received truncated message.");
315 if(type
<= MESSAGE_MAX
&& tlv_min_length
[type
] && len
< tlv_min_length
[type
]) {
316 debugf(BABEL_DEBUG_COMMON
,"Undersized %u TLV", type
);
325 parse_packet(const unsigned char *from
, struct interface
*ifp
,
326 const unsigned char *packet
, int packetlen
)
329 const unsigned char *message
;
330 unsigned char type
, len
;
332 struct neighbour
*neigh
;
333 int have_router_id
= 0, have_v4_prefix
= 0, have_v6_prefix
= 0,
334 have_v4_nh
= 0, have_v6_nh
= 0;
335 unsigned char router_id
[8], v4_prefix
[16], v6_prefix
[16],
336 v4_nh
[16], v6_nh
[16];
337 int have_hello_rtt
= 0;
338 /* Content of the RTT sub-TLV on IHU messages. */
339 unsigned int hello_send_us
= 0, hello_rtt_receive_time
= 0;
340 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
342 if(babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) {
343 /* We want to track exactly when we received this packet. */
347 if(!linklocal(from
)) {
348 flog_err(EC_BABEL_PACKET
,
349 "Received packet from non-local address %s.",
350 format_address(from
));
354 if (babel_packet_examin (packet
, packetlen
)) {
355 flog_err(EC_BABEL_PACKET
,
356 "Received malformed packet on %s from %s.",
357 ifp
->name
, format_address(from
));
361 neigh
= find_neighbour(from
, ifp
);
363 flog_err(EC_BABEL_PACKET
, "Couldn't allocate neighbour.");
367 DO_NTOHS(bodylen
, packet
+ 2);
369 if(bodylen
+ 4 > packetlen
) {
370 flog_err(EC_BABEL_PACKET
, "Received truncated packet (%d + 4 > %d).",
372 bodylen
= packetlen
- 4;
377 message
= packet
+ 4 + i
;
379 if(type
== MESSAGE_PAD1
) {
380 debugf(BABEL_DEBUG_COMMON
,"Received pad1 from %s on %s.",
381 format_address(from
), ifp
->name
);
387 if(type
== MESSAGE_PADN
) {
388 debugf(BABEL_DEBUG_COMMON
,"Received pad%d from %s on %s.",
389 len
, format_address(from
), ifp
->name
);
390 } else if(type
== MESSAGE_ACK_REQ
) {
391 unsigned short nonce
, interval
;
392 DO_NTOHS(nonce
, message
+ 4);
393 DO_NTOHS(interval
, message
+ 6);
394 debugf(BABEL_DEBUG_COMMON
,"Received ack-req (%04X %d) from %s on %s.",
395 nonce
, interval
, format_address(from
), ifp
->name
);
396 send_ack(neigh
, nonce
, interval
);
397 } else if(type
== MESSAGE_ACK
) {
398 debugf(BABEL_DEBUG_COMMON
,"Received ack from %s on %s.",
399 format_address(from
), ifp
->name
);
400 /* Nothing right now */
401 } else if(type
== MESSAGE_HELLO
) {
402 unsigned short seqno
, interval
;
404 unsigned int timestamp
= 0;
405 DO_NTOHS(seqno
, message
+ 4);
406 DO_NTOHS(interval
, message
+ 6);
407 debugf(BABEL_DEBUG_COMMON
,"Received hello %d (%d) from %s on %s.",
409 format_address(from
), ifp
->name
);
410 changed
= update_neighbour(neigh
, seqno
, interval
);
411 update_neighbour_metric(neigh
, changed
);
413 /* Multiply by 3/2 to allow hellos to expire. */
414 schedule_neighbours_check(interval
* 15, 0);
415 /* Sub-TLV handling. */
417 if(parse_hello_subtlv(message
+ 8, len
- 6, ×tamp
) > 0) {
418 neigh
->hello_send_us
= timestamp
;
419 neigh
->hello_rtt_receive_time
= babel_now
;
423 } else if(type
== MESSAGE_IHU
) {
424 unsigned short txcost
, interval
;
425 unsigned char address
[16];
427 DO_NTOHS(txcost
, message
+ 4);
428 DO_NTOHS(interval
, message
+ 6);
429 rc
= network_address(message
[2], message
+ 8, len
- 6, address
);
430 if(rc
< 0) goto fail
;
431 debugf(BABEL_DEBUG_COMMON
,"Received ihu %d (%d) from %s on %s for %s.",
433 format_address(from
), ifp
->name
,
434 format_address(address
));
435 if(message
[2] == 0 || is_interface_ll_address(ifp
, address
)) {
436 int changed
= txcost
!= neigh
->txcost
;
437 neigh
->txcost
= txcost
;
438 neigh
->ihu_time
= babel_now
;
439 neigh
->ihu_interval
= interval
;
440 update_neighbour_metric(neigh
, changed
);
442 /* Multiply by 3/2 to allow neighbours to expire. */
443 schedule_neighbours_check(interval
* 45, 0);
446 parse_ihu_subtlv(message
+ 8 + rc
, len
- 6 - rc
,
447 &hello_send_us
, &hello_rtt_receive_time
);
449 } else if(type
== MESSAGE_ROUTER_ID
) {
450 memcpy(router_id
, message
+ 4, 8);
452 debugf(BABEL_DEBUG_COMMON
,"Received router-id %s from %s on %s.",
453 format_eui64(router_id
), format_address(from
), ifp
->name
);
454 } else if(type
== MESSAGE_NH
) {
455 unsigned char nh
[16];
457 rc
= network_address(message
[2], message
+ 4, len
- 2,
464 debugf(BABEL_DEBUG_COMMON
,"Received nh %s (%d) from %s on %s.",
465 format_address(nh
), message
[2],
466 format_address(from
), ifp
->name
);
467 if(message
[2] == 1) {
468 memcpy(v4_nh
, nh
, 16);
471 memcpy(v6_nh
, nh
, 16);
474 } else if(type
== MESSAGE_UPDATE
) {
475 unsigned char prefix
[16], *nh
;
477 unsigned char channels
[DIVERSITY_HOPS
];
478 unsigned short interval
, seqno
, metric
;
480 DO_NTOHS(interval
, message
+ 6);
481 DO_NTOHS(seqno
, message
+ 8);
482 DO_NTOHS(metric
, message
+ 10);
483 if(message
[5] == 0 ||
484 (message
[2] == 1 ? have_v4_prefix
: have_v6_prefix
))
485 rc
= network_prefix(message
[2], message
[4], message
[5],
487 message
[2] == 1 ? v4_prefix
: v6_prefix
,
492 if(message
[3] & 0x80)
493 have_v4_prefix
= have_v6_prefix
= 0;
496 parsed_len
= 10 + rc
;
498 plen
= message
[4] + (message
[2] == 1 ? 96 : 0);
500 if(message
[3] & 0x80) {
501 if(message
[2] == 1) {
502 memcpy(v4_prefix
, prefix
, 16);
505 memcpy(v6_prefix
, prefix
, 16);
509 if(message
[3] & 0x40) {
510 if(message
[2] == 1) {
511 memset(router_id
, 0, 4);
512 memcpy(router_id
+ 4, prefix
+ 12, 4);
514 memcpy(router_id
, prefix
+ 8, 8);
518 if(!have_router_id
&& message
[2] != 0) {
519 flog_err(EC_BABEL_PACKET
,
520 "Received prefix with no router id.");
523 debugf(BABEL_DEBUG_COMMON
,"Received update%s%s for %s from %s on %s.",
524 (message
[3] & 0x80) ? "/prefix" : "",
525 (message
[3] & 0x40) ? "/id" : "",
526 format_prefix(prefix
, plen
),
527 format_address(from
), ifp
->name
);
529 if(message
[2] == 0) {
530 if(metric
< 0xFFFF) {
531 flog_err(EC_BABEL_PACKET
,
532 "Received wildcard update with finite metric.");
535 retract_neighbour_routes(neigh
);
537 } else if(message
[2] == 1) {
541 } else if(have_v6_nh
) {
547 if(message
[2] == 1) {
548 if(!babel_get_if_nfo(ifp
)->ipv4
)
552 if((babel_get_if_nfo(ifp
)->flags
& BABEL_IF_FARAWAY
)) {
555 /* This will be overwritten by parse_update_subtlv below. */
557 /* Assume non-interfering (wired) link. */
560 /* Assume interfering. */
561 channels
[0] = BABEL_IF_CHANNEL_INTERFERING
;
566 parse_update_subtlv(message
+ 2 + parsed_len
,
567 len
- parsed_len
, channels
);
570 update_route(router_id
, prefix
, plen
, seqno
, metric
, interval
,
572 channels
, channels_len(channels
));
573 } else if(type
== MESSAGE_REQUEST
) {
574 unsigned char prefix
[16], plen
;
576 rc
= network_prefix(message
[2], message
[3], 0,
577 message
+ 4, NULL
, len
- 2, prefix
);
578 if(rc
< 0) goto fail
;
579 plen
= message
[3] + (message
[2] == 1 ? 96 : 0);
580 debugf(BABEL_DEBUG_COMMON
,"Received request for %s from %s on %s.",
581 message
[2] == 0 ? "any" : format_prefix(prefix
, plen
),
582 format_address(from
), ifp
->name
);
583 if(message
[2] == 0) {
584 struct babel_interface
*neigh_ifp
=babel_get_if_nfo(neigh
->ifp
);
585 /* If a neighbour is requesting a full route dump from us,
586 we might as well send it an IHU. */
587 send_ihu(neigh
, NULL
);
588 /* Since nodes send wildcard requests on boot, booting
589 a large number of nodes at the same time may cause an
590 update storm. Ignore a wildcard request that happens
591 shortly after we sent a full update. */
592 if(neigh_ifp
->last_update_time
<
593 (time_t)(babel_now
.tv_sec
-
594 MAX(neigh_ifp
->hello_interval
/ 100, 1)))
595 send_update(neigh
->ifp
, 0, NULL
, 0);
597 send_update(neigh
->ifp
, 0, prefix
, plen
);
599 } else if(type
== MESSAGE_MH_REQUEST
) {
600 unsigned char prefix
[16], plen
;
601 unsigned short seqno
;
603 DO_NTOHS(seqno
, message
+ 4);
604 rc
= network_prefix(message
[2], message
[3], 0,
605 message
+ 16, NULL
, len
- 14, prefix
);
606 if(rc
< 0) goto fail
;
607 plen
= message
[3] + (message
[2] == 1 ? 96 : 0);
608 debugf(BABEL_DEBUG_COMMON
,"Received request (%d) for %s from %s on %s (%s, %d).",
610 format_prefix(prefix
, plen
),
611 format_address(from
), ifp
->name
,
612 format_eui64(message
+ 8), seqno
);
613 handle_request(neigh
, prefix
, plen
, message
[6],
616 debugf(BABEL_DEBUG_COMMON
,"Received unknown packet type %d from %s on %s.",
617 type
, format_address(from
), ifp
->name
);
624 flog_err(EC_BABEL_PACKET
,
625 "Couldn't parse packet (%d, %d) from %s on %s.",
626 message
[0], message
[1], format_address(from
), ifp
->name
);
630 /* We can calculate the RTT to this neighbour. */
631 if(have_hello_rtt
&& hello_send_us
&& hello_rtt_receive_time
) {
632 int remote_waiting_us
, local_waiting_us
;
633 unsigned int rtt
, smoothed_rtt
;
634 unsigned int old_rttcost
;
636 remote_waiting_us
= neigh
->hello_send_us
- hello_rtt_receive_time
;
637 local_waiting_us
= time_us(neigh
->hello_rtt_receive_time
) -
640 /* Sanity checks (validity window of 10 minutes). */
641 if(remote_waiting_us
< 0 || local_waiting_us
< 0 ||
642 remote_waiting_us
> 600000000 || local_waiting_us
> 600000000)
645 rtt
= MAX(0, local_waiting_us
- remote_waiting_us
);
646 debugf(BABEL_DEBUG_COMMON
, "RTT to %s on %s sample result: %d us.",
647 format_address(from
), ifp
->name
, rtt
);
649 old_rttcost
= neighbour_rttcost(neigh
);
650 if (valid_rtt(neigh
)) {
651 /* Running exponential average. */
652 smoothed_rtt
= (babel_ifp
->rtt_decay
* rtt
+
653 (256 - babel_ifp
->rtt_decay
) * neigh
->rtt
);
654 /* Rounding (up or down) to get closer to the sample. */
655 neigh
->rtt
= (neigh
->rtt
>= rtt
) ? smoothed_rtt
/ 256 :
656 (smoothed_rtt
+ 255) / 256;
658 /* We prefer to be conservative with new neighbours
660 assert(rtt
<= 0x7FFFFFFF);
663 changed
= (neighbour_rttcost(neigh
) == old_rttcost
? 0 : 1);
664 update_neighbour_metric(neigh
, changed
);
665 neigh
->rtt_time
= babel_now
;
670 /* Under normal circumstances, there are enough moderation mechanisms
671 elsewhere in the protocol to make sure that this last-ditch check
672 should never trigger. But I'm superstitious. */
675 check_bucket(struct interface
*ifp
)
677 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
678 if(babel_ifp
->bucket
== 0) {
679 int seconds
= babel_now
.tv_sec
- babel_ifp
->bucket_time
;
681 babel_ifp
->bucket
= MIN(BUCKET_TOKENS_MAX
,
682 seconds
* BUCKET_TOKENS_PER_SEC
);
684 /* Reset bucket time unconditionally, in case clock is stepped. */
685 babel_ifp
->bucket_time
= babel_now
.tv_sec
;
688 if(babel_ifp
->bucket
> 0) {
697 fill_rtt_message(struct interface
*ifp
)
699 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
700 if((babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) &&
701 (babel_ifp
->buffered_hello
>= 0)) {
702 if(babel_ifp
->sendbuf
[babel_ifp
->buffered_hello
+ 8] == SUBTLV_PADN
&&
703 babel_ifp
->sendbuf
[babel_ifp
->buffered_hello
+ 9] == 4) {
705 /* Change the type of sub-TLV. */
706 babel_ifp
->sendbuf
[babel_ifp
->buffered_hello
+ 8] =
709 time
= time_us(babel_now
);
710 DO_HTONL(babel_ifp
->sendbuf
+ babel_ifp
->buffered_hello
+ 10, time
);
713 flog_err(EC_BABEL_PACKET
, "No space left for timestamp sub-TLV (this shouldn't happen)");
721 flushbuf(struct interface
*ifp
)
724 struct sockaddr_in6 sin6
;
725 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
727 assert(babel_ifp
->buffered
<= babel_ifp
->bufsize
);
731 if(babel_ifp
->buffered
> 0) {
732 debugf(BABEL_DEBUG_COMMON
," (flushing %d buffered bytes on %s)",
733 babel_ifp
->buffered
, ifp
->name
);
734 if(check_bucket(ifp
)) {
735 memset(&sin6
, 0, sizeof(sin6
));
736 sin6
.sin6_family
= AF_INET6
;
737 memcpy(&sin6
.sin6_addr
, protocol_group
, 16);
738 sin6
.sin6_port
= htons(protocol_port
);
739 sin6
.sin6_scope_id
= ifp
->ifindex
;
740 DO_HTONS(packet_header
+ 2, babel_ifp
->buffered
);
741 fill_rtt_message(ifp
);
742 rc
= babel_send(protocol_socket
,
743 packet_header
, sizeof(packet_header
),
744 babel_ifp
->sendbuf
, babel_ifp
->buffered
,
745 (struct sockaddr
*)&sin6
, sizeof(sin6
));
747 flog_err(EC_BABEL_PACKET
, "send: %s", safe_strerror(errno
));
749 flog_err(EC_BABEL_PACKET
, "Bucket full, dropping packet to %s.",
753 VALGRIND_MAKE_MEM_UNDEFINED(babel_ifp
->sendbuf
, babel_ifp
->bufsize
);
754 babel_ifp
->buffered
= 0;
755 babel_ifp
->buffered_hello
= -1;
756 babel_ifp
->have_buffered_id
= 0;
757 babel_ifp
->have_buffered_nh
= 0;
758 babel_ifp
->have_buffered_prefix
= 0;
759 babel_ifp
->flush_timeout
.tv_sec
= 0;
760 babel_ifp
->flush_timeout
.tv_usec
= 0;
764 schedule_flush(struct interface
*ifp
)
766 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
767 unsigned msecs
= jitter(babel_ifp
, 0);
768 if(babel_ifp
->flush_timeout
.tv_sec
!= 0 &&
769 timeval_minus_msec(&babel_ifp
->flush_timeout
, &babel_now
) < msecs
)
771 set_timeout(&babel_ifp
->flush_timeout
, msecs
);
775 schedule_flush_now(struct interface
*ifp
)
777 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
779 unsigned msecs
= roughly(10);
780 if(babel_ifp
->flush_timeout
.tv_sec
!= 0 &&
781 timeval_minus_msec(&babel_ifp
->flush_timeout
, &babel_now
) < msecs
)
783 set_timeout(&babel_ifp
->flush_timeout
, msecs
);
787 schedule_unicast_flush(unsigned msecs
)
789 if(!unicast_neighbour
)
791 if(unicast_flush_timeout
.tv_sec
!= 0 &&
792 timeval_minus_msec(&unicast_flush_timeout
, &babel_now
) < msecs
)
794 unicast_flush_timeout
.tv_usec
= (babel_now
.tv_usec
+ msecs
* 1000) %1000000;
795 unicast_flush_timeout
.tv_sec
=
796 babel_now
.tv_sec
+ (babel_now
.tv_usec
/ 1000 + msecs
) / 1000;
800 ensure_space(struct interface
*ifp
, int space
)
802 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
803 if(babel_ifp
->bufsize
- babel_ifp
->buffered
< space
)
808 start_message(struct interface
*ifp
, int type
, int len
)
810 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
811 if(babel_ifp
->bufsize
- babel_ifp
->buffered
< len
+ 2)
813 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = type
;
814 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = len
;
818 end_message(struct interface
*ifp
, int type
, int bytes
)
820 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
821 assert(babel_ifp
->buffered
>= bytes
+ 2 &&
822 babel_ifp
->sendbuf
[babel_ifp
->buffered
- bytes
- 2] == type
&&
823 babel_ifp
->sendbuf
[babel_ifp
->buffered
- bytes
- 1] == bytes
);
828 accumulate_byte(struct interface
*ifp
, unsigned char value
)
830 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
831 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = value
;
835 accumulate_short(struct interface
*ifp
, unsigned short value
)
837 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
838 DO_HTONS(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
);
839 babel_ifp
->buffered
+= 2;
843 accumulate_int(struct interface
*ifp
, unsigned int value
)
845 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
846 DO_HTONL(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
);
847 babel_ifp
->buffered
+= 4;
851 accumulate_bytes(struct interface
*ifp
,
852 const unsigned char *value
, unsigned len
)
854 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
855 memcpy(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
, len
);
856 babel_ifp
->buffered
+= len
;
860 start_unicast_message(struct neighbour
*neigh
, int type
, int len
)
862 if(unicast_neighbour
) {
863 if(neigh
!= unicast_neighbour
||
864 unicast_buffered
+ len
+ 2 >=
865 MIN(UNICAST_BUFSIZE
, babel_get_if_nfo(neigh
->ifp
)->bufsize
))
869 unicast_buffer
= malloc(UNICAST_BUFSIZE
);
870 if(!unicast_buffer
) {
871 flog_err(EC_BABEL_MEMORY
, "malloc(unicast_buffer): %s",
872 safe_strerror(errno
));
876 unicast_neighbour
= neigh
;
878 unicast_buffer
[unicast_buffered
++] = type
;
879 unicast_buffer
[unicast_buffered
++] = len
;
884 end_unicast_message(struct neighbour
*neigh
, int type
, int bytes
)
886 assert(unicast_neighbour
== neigh
&& unicast_buffered
>= bytes
+ 2 &&
887 unicast_buffer
[unicast_buffered
- bytes
- 2] == type
&&
888 unicast_buffer
[unicast_buffered
- bytes
- 1] == bytes
);
889 schedule_unicast_flush(jitter(babel_get_if_nfo(neigh
->ifp
), 0));
893 accumulate_unicast_byte(struct neighbour
*neigh
, unsigned char value
)
895 unicast_buffer
[unicast_buffered
++] = value
;
899 accumulate_unicast_short(struct neighbour
*neigh
, unsigned short value
)
901 DO_HTONS(unicast_buffer
+ unicast_buffered
, value
);
902 unicast_buffered
+= 2;
906 accumulate_unicast_int(struct neighbour
*neigh
, unsigned int value
)
908 DO_HTONL(unicast_buffer
+ unicast_buffered
, value
);
909 unicast_buffered
+= 4;
913 accumulate_unicast_bytes(struct neighbour
*neigh
,
914 const unsigned char *value
, unsigned len
)
916 memcpy(unicast_buffer
+ unicast_buffered
, value
, len
);
917 unicast_buffered
+= len
;
921 send_ack(struct neighbour
*neigh
, unsigned short nonce
, unsigned short interval
)
924 debugf(BABEL_DEBUG_COMMON
,"Sending ack (%04x) to %s on %s.",
925 nonce
, format_address(neigh
->address
), neigh
->ifp
->name
);
926 rc
= start_unicast_message(neigh
, MESSAGE_ACK
, 2); if(rc
< 0) return;
927 accumulate_unicast_short(neigh
, nonce
);
928 end_unicast_message(neigh
, MESSAGE_ACK
, 2);
929 /* Roughly yields a value no larger than 3/2, so this meets the deadline */
930 schedule_unicast_flush(roughly(interval
* 6));
934 send_hello_noupdate(struct interface
*ifp
, unsigned interval
)
936 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
937 /* This avoids sending multiple hellos in a single packet, which breaks
938 link quality estimation. */
939 if(babel_ifp
->buffered_hello
>= 0)
942 babel_ifp
->hello_seqno
= seqno_plus(babel_ifp
->hello_seqno
, 1);
943 set_timeout(&babel_ifp
->hello_timeout
, babel_ifp
->hello_interval
);
948 debugf(BABEL_DEBUG_COMMON
,"Sending hello %d (%d) to %s.",
949 babel_ifp
->hello_seqno
, interval
, ifp
->name
);
951 start_message(ifp
, MESSAGE_HELLO
,
952 (babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) ? 12 : 6);
953 babel_ifp
->buffered_hello
= babel_ifp
->buffered
- 2;
954 accumulate_short(ifp
, 0);
955 accumulate_short(ifp
, babel_ifp
->hello_seqno
);
956 accumulate_short(ifp
, interval
> 0xFFFF ? 0xFFFF : interval
);
957 if(babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) {
958 /* Sub-TLV containing the local time of emission. We use a
959 Pad4 sub-TLV, which we'll fill just before sending. */
960 accumulate_byte(ifp
, SUBTLV_PADN
);
961 accumulate_byte(ifp
, 4);
962 accumulate_int(ifp
, 0);
964 end_message(ifp
, MESSAGE_HELLO
,
965 (babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) ? 12 : 6);
969 send_hello(struct interface
*ifp
)
971 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
972 send_hello_noupdate(ifp
, (babel_ifp
->hello_interval
+ 9) / 10);
973 /* Send full IHU every 3 hellos, and marginal IHU each time */
974 if(babel_ifp
->hello_seqno
% 3 == 0)
977 send_marginal_ihu(ifp
);
981 flush_unicast(int dofree
)
983 struct sockaddr_in6 sin6
;
986 if(unicast_buffered
== 0)
989 if(!if_up(unicast_neighbour
->ifp
))
992 /* Preserve ordering of messages */
993 flushbuf(unicast_neighbour
->ifp
);
995 if(check_bucket(unicast_neighbour
->ifp
)) {
996 memset(&sin6
, 0, sizeof(sin6
));
997 sin6
.sin6_family
= AF_INET6
;
998 memcpy(&sin6
.sin6_addr
, unicast_neighbour
->address
, 16);
999 sin6
.sin6_port
= htons(protocol_port
);
1000 sin6
.sin6_scope_id
= unicast_neighbour
->ifp
->ifindex
;
1001 DO_HTONS(packet_header
+ 2, unicast_buffered
);
1002 fill_rtt_message(unicast_neighbour
->ifp
);
1003 rc
= babel_send(protocol_socket
,
1004 packet_header
, sizeof(packet_header
),
1005 unicast_buffer
, unicast_buffered
,
1006 (struct sockaddr
*)&sin6
, sizeof(sin6
));
1008 flog_err(EC_BABEL_PACKET
, "send(unicast): %s",
1009 safe_strerror(errno
));
1011 flog_err(EC_BABEL_PACKET
,
1012 "Bucket full, dropping unicast packet to %s if %s.",
1013 format_address(unicast_neighbour
->address
),
1014 unicast_neighbour
->ifp
->name
);
1018 VALGRIND_MAKE_MEM_UNDEFINED(unicast_buffer
, UNICAST_BUFSIZE
);
1019 unicast_buffered
= 0;
1020 if(dofree
&& unicast_buffer
) {
1021 free(unicast_buffer
);
1022 unicast_buffer
= NULL
;
1024 unicast_neighbour
= NULL
;
1025 unicast_flush_timeout
.tv_sec
= 0;
1026 unicast_flush_timeout
.tv_usec
= 0;
1030 really_send_update(struct interface
*ifp
,
1031 const unsigned char *id
,
1032 const unsigned char *prefix
, unsigned char plen
,
1033 unsigned short seqno
, unsigned short metric
,
1034 unsigned char *channels
, int channels_len
)
1036 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1037 int add_metric
, v4
, real_plen
, omit
= 0;
1038 const unsigned char *real_prefix
;
1039 unsigned short flags
= 0;
1042 if(diversity_kind
!= DIVERSITY_CHANNEL
)
1045 channels_size
= channels_len
>= 0 ? channels_len
+ 2 : 0;
1050 add_metric
= output_filter(id
, prefix
, plen
, ifp
->ifindex
);
1051 if(add_metric
>= INFINITY
)
1054 metric
= MIN(metric
+ add_metric
, INFINITY
);
1056 ensure_space(ifp
, 20 + 12 + 28);
1058 v4
= plen
>= 96 && v4mapped(prefix
);
1061 if(!babel_ifp
->ipv4
)
1063 if(!babel_ifp
->have_buffered_nh
||
1064 memcmp(babel_ifp
->buffered_nh
, babel_ifp
->ipv4
, 4) != 0) {
1065 start_message(ifp
, MESSAGE_NH
, 6);
1066 accumulate_byte(ifp
, 1);
1067 accumulate_byte(ifp
, 0);
1068 accumulate_bytes(ifp
, babel_ifp
->ipv4
, 4);
1069 end_message(ifp
, MESSAGE_NH
, 6);
1070 memcpy(babel_ifp
->buffered_nh
, babel_ifp
->ipv4
, 4);
1071 babel_ifp
->have_buffered_nh
= 1;
1074 real_prefix
= prefix
+ 12;
1075 real_plen
= plen
- 96;
1077 if(babel_ifp
->have_buffered_prefix
) {
1078 while(omit
< plen
/ 8 &&
1079 babel_ifp
->buffered_prefix
[omit
] == prefix
[omit
])
1082 if(!babel_ifp
->have_buffered_prefix
|| plen
>= 48)
1084 real_prefix
= prefix
;
1088 if(!babel_ifp
->have_buffered_id
1089 || memcmp(id
, babel_ifp
->buffered_id
, 8) != 0) {
1090 if(real_plen
== 128 && memcmp(real_prefix
+ 8, id
, 8) == 0) {
1093 start_message(ifp
, MESSAGE_ROUTER_ID
, 10);
1094 accumulate_short(ifp
, 0);
1095 accumulate_bytes(ifp
, id
, 8);
1096 end_message(ifp
, MESSAGE_ROUTER_ID
, 10);
1098 memcpy(babel_ifp
->buffered_id
, id
, sizeof(babel_ifp
->buffered_id
));
1099 babel_ifp
->have_buffered_id
= 1;
1102 start_message(ifp
, MESSAGE_UPDATE
, 10 + (real_plen
+ 7) / 8 - omit
+
1104 accumulate_byte(ifp
, v4
? 1 : 2);
1105 accumulate_byte(ifp
, flags
);
1106 accumulate_byte(ifp
, real_plen
);
1107 accumulate_byte(ifp
, omit
);
1108 accumulate_short(ifp
, (babel_ifp
->update_interval
+ 5) / 10);
1109 accumulate_short(ifp
, seqno
);
1110 accumulate_short(ifp
, metric
);
1111 accumulate_bytes(ifp
, real_prefix
+ omit
, (real_plen
+ 7) / 8 - omit
);
1112 /* Note that an empty channels TLV is different from no such TLV. */
1113 if(channels_len
>= 0) {
1114 accumulate_byte(ifp
, 2);
1115 accumulate_byte(ifp
, channels_len
);
1117 if (channels
&& channels_len
> 0)
1118 accumulate_bytes(ifp
, channels
, channels_len
);
1120 end_message(ifp
, MESSAGE_UPDATE
, 10 + (real_plen
+ 7) / 8 - omit
+
1124 memcpy(babel_ifp
->buffered_prefix
, prefix
, 16);
1125 babel_ifp
->have_buffered_prefix
= 1;
1130 compare_buffered_updates(const void *av
, const void *bv
)
1132 const struct buffered_update
*a
= av
, *b
= bv
;
1133 int rc
, v4a
, v4b
, ma
, mb
;
1135 rc
= memcmp(a
->id
, b
->id
, 8);
1139 v4a
= (a
->plen
>= 96 && v4mapped(a
->prefix
));
1140 v4b
= (b
->plen
>= 96 && v4mapped(b
->prefix
));
1147 ma
= (!v4a
&& a
->plen
== 128 && memcmp(a
->prefix
+ 8, a
->id
, 8) == 0);
1148 mb
= (!v4b
&& b
->plen
== 128 && memcmp(b
->prefix
+ 8, b
->id
, 8) == 0);
1155 if(a
->plen
< b
->plen
)
1157 else if(a
->plen
> b
->plen
)
1160 return memcmp(a
->prefix
, b
->prefix
, 16);
1164 flushupdates(struct interface
*ifp
)
1166 babel_interface_nfo
*babel_ifp
= NULL
;
1167 struct xroute
*xroute
;
1168 struct babel_route
*route
;
1169 const unsigned char *last_prefix
= NULL
;
1170 unsigned char last_plen
= 0xFF;
1174 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1175 struct interface
*ifp_aux
;
1176 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1177 flushupdates(ifp_aux
);
1181 babel_ifp
= babel_get_if_nfo(ifp
);
1182 if(babel_ifp
->num_buffered_updates
> 0) {
1183 struct buffered_update
*b
= babel_ifp
->buffered_updates
;
1184 int n
= babel_ifp
->num_buffered_updates
;
1186 babel_ifp
->buffered_updates
= NULL
;
1187 babel_ifp
->update_bufsize
= 0;
1188 babel_ifp
->num_buffered_updates
= 0;
1193 debugf(BABEL_DEBUG_COMMON
," (flushing %d buffered updates on %s (%d))",
1194 n
, ifp
->name
, ifp
->ifindex
);
1196 /* In order to send fewer update messages, we want to send updates
1197 with the same router-id together, with IPv6 going out before IPv4. */
1199 for(i
= 0; i
< n
; i
++) {
1200 route
= find_installed_route(b
[i
].prefix
, b
[i
].plen
);
1202 memcpy(b
[i
].id
, route
->src
->id
, 8);
1204 memcpy(b
[i
].id
, myid
, 8);
1207 qsort(b
, n
, sizeof(struct buffered_update
), compare_buffered_updates
);
1209 for(i
= 0; i
< n
; i
++) {
1210 /* The same update may be scheduled multiple times before it is
1211 sent out. Since our buffer is now sorted, it is enough to
1212 compare with the previous update. */
1215 if(b
[i
].plen
== last_plen
&&
1216 memcmp(b
[i
].prefix
, last_prefix
, 16) == 0)
1220 xroute
= find_xroute(b
[i
].prefix
, b
[i
].plen
);
1221 route
= find_installed_route(b
[i
].prefix
, b
[i
].plen
);
1223 if(xroute
&& (!route
|| xroute
->metric
<= kernel_metric
)) {
1224 really_send_update(ifp
, myid
,
1225 xroute
->prefix
, xroute
->plen
,
1226 myseqno
, xroute
->metric
,
1228 last_prefix
= xroute
->prefix
;
1229 last_plen
= xroute
->plen
;
1231 unsigned char channels
[DIVERSITY_HOPS
];
1233 struct interface
*route_ifp
= route
->neigh
->ifp
;
1234 struct babel_interface
*babel_route_ifp
= NULL
;
1235 unsigned short metric
;
1236 unsigned short seqno
;
1238 seqno
= route
->seqno
;
1240 route_interferes(route
, ifp
) ?
1241 route_metric(route
) :
1242 route_metric_noninterfering(route
);
1244 if(metric
< INFINITY
)
1245 satisfy_request(route
->src
->prefix
, route
->src
->plen
,
1246 seqno
, route
->src
->id
, ifp
);
1247 if((babel_ifp
->flags
& BABEL_IF_SPLIT_HORIZON
) &&
1248 route
->neigh
->ifp
== ifp
)
1251 babel_route_ifp
= babel_get_if_nfo(route_ifp
);
1252 if(babel_route_ifp
->channel
==BABEL_IF_CHANNEL_NONINTERFERING
) {
1253 memcpy(channels
, route
->channels
, DIVERSITY_HOPS
);
1255 if(babel_route_ifp
->channel
== BABEL_IF_CHANNEL_UNKNOWN
)
1256 channels
[0] = BABEL_IF_CHANNEL_INTERFERING
;
1258 assert(babel_route_ifp
->channel
> 0 &&
1259 babel_route_ifp
->channel
<= 255);
1260 channels
[0] = babel_route_ifp
->channel
;
1262 memcpy(channels
+ 1, route
->channels
, DIVERSITY_HOPS
- 1);
1265 chlen
= channels_len(channels
);
1266 really_send_update(ifp
, route
->src
->id
,
1271 update_source(route
->src
, seqno
, metric
);
1272 last_prefix
= route
->src
->prefix
;
1273 last_plen
= route
->src
->plen
;
1275 /* There's no route for this prefix. This can happen shortly
1276 after an xroute has been retracted, so send a retraction. */
1277 really_send_update(ifp
, myid
, b
[i
].prefix
, b
[i
].plen
,
1278 myseqno
, INFINITY
, NULL
, -1);
1281 schedule_flush_now(ifp
);
1285 babel_ifp
->update_flush_timeout
.tv_sec
= 0;
1286 babel_ifp
->update_flush_timeout
.tv_usec
= 0;
1290 schedule_update_flush(struct interface
*ifp
, int urgent
)
1292 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1294 msecs
= update_jitter(babel_ifp
, urgent
);
1295 if(babel_ifp
->update_flush_timeout
.tv_sec
!= 0 &&
1296 timeval_minus_msec(&babel_ifp
->update_flush_timeout
, &babel_now
) < msecs
)
1298 set_timeout(&babel_ifp
->update_flush_timeout
, msecs
);
1302 buffer_update(struct interface
*ifp
,
1303 const unsigned char *prefix
, unsigned char plen
)
1305 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1306 if(babel_ifp
->num_buffered_updates
> 0 &&
1307 babel_ifp
->num_buffered_updates
>= babel_ifp
->update_bufsize
)
1310 if(babel_ifp
->update_bufsize
== 0) {
1312 assert(babel_ifp
->buffered_updates
== NULL
);
1313 /* Allocate enough space to hold a full update. Since the
1314 number of installed routes will grow over time, make sure we
1315 have enough space to send a full-ish frame. */
1316 n
= installed_routes_estimate() + xroutes_estimate() + 4;
1317 n
= MAX(n
, babel_ifp
->bufsize
/ 16);
1319 babel_ifp
->buffered_updates
= malloc(n
*sizeof(struct buffered_update
));
1320 if(babel_ifp
->buffered_updates
== NULL
) {
1321 flog_err(EC_BABEL_MEMORY
, "malloc(buffered_updates): %s",
1322 safe_strerror(errno
));
1324 /* Try again with a tiny buffer. */
1330 babel_ifp
->update_bufsize
= n
;
1331 babel_ifp
->num_buffered_updates
= 0;
1334 memcpy(babel_ifp
->buffered_updates
[babel_ifp
->num_buffered_updates
].prefix
,
1336 babel_ifp
->buffered_updates
[babel_ifp
->num_buffered_updates
].plen
= plen
;
1337 babel_ifp
->num_buffered_updates
++;
1341 send_update(struct interface
*ifp
, int urgent
,
1342 const unsigned char *prefix
, unsigned char plen
)
1344 babel_interface_nfo
*babel_ifp
= NULL
;
1347 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1348 struct interface
*ifp_aux
;
1349 struct babel_route
*route
;
1350 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1351 send_update(ifp_aux
, urgent
, prefix
, plen
);
1353 /* Since flushupdates only deals with non-wildcard interfaces, we
1354 need to do this now. */
1355 route
= find_installed_route(prefix
, plen
);
1356 if(route
&& route_metric(route
) < INFINITY
)
1357 satisfy_request(prefix
, plen
, route
->src
->seqno
, route
->src
->id
,
1366 babel_ifp
= babel_get_if_nfo(ifp
);
1368 debugf(BABEL_DEBUG_COMMON
,"Sending update to %s for %s.",
1369 ifp
->name
, format_prefix(prefix
, plen
));
1370 buffer_update(ifp
, prefix
, plen
);
1372 struct route_stream
*routes
= NULL
;
1373 send_self_update(ifp
);
1374 debugf(BABEL_DEBUG_COMMON
,"Sending update to %s for any.", ifp
->name
);
1375 routes
= route_stream(1);
1378 struct babel_route
*route
= route_stream_next(routes
);
1381 buffer_update(ifp
, route
->src
->prefix
, route
->src
->plen
);
1383 route_stream_done(routes
);
1385 flog_err(EC_BABEL_MEMORY
, "Couldn't allocate route stream.");
1387 set_timeout(&babel_ifp
->update_timeout
, babel_ifp
->update_interval
);
1388 babel_ifp
->last_update_time
= babel_now
.tv_sec
;
1390 schedule_update_flush(ifp
, urgent
);
1394 send_update_resend(struct interface
*ifp
,
1395 const unsigned char *prefix
, unsigned char plen
)
1397 assert(prefix
!= NULL
);
1399 send_update(ifp
, 1, prefix
, plen
);
1400 record_resend(RESEND_UPDATE
, prefix
, plen
, 0, NULL
, NULL
, resend_delay
);
1404 send_wildcard_retraction(struct interface
*ifp
)
1406 babel_interface_nfo
*babel_ifp
= NULL
;
1408 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1409 struct interface
*ifp_aux
;
1410 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1411 send_wildcard_retraction(ifp_aux
);
1418 babel_ifp
= babel_get_if_nfo(ifp
);
1419 start_message(ifp
, MESSAGE_UPDATE
, 10);
1420 accumulate_byte(ifp
, 0);
1421 accumulate_byte(ifp
, 0x40);
1422 accumulate_byte(ifp
, 0);
1423 accumulate_byte(ifp
, 0);
1424 accumulate_short(ifp
, 0xFFFF);
1425 accumulate_short(ifp
, myseqno
);
1426 accumulate_short(ifp
, 0xFFFF);
1427 end_message(ifp
, MESSAGE_UPDATE
, 10);
1429 babel_ifp
->have_buffered_id
= 0;
1433 update_myseqno(void)
1435 myseqno
= seqno_plus(myseqno
, 1);
1439 send_self_update(struct interface
*ifp
)
1441 struct xroute_stream
*xroutes
;
1443 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1444 struct interface
*ifp_aux
;
1445 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1448 send_self_update(ifp_aux
);
1453 debugf(BABEL_DEBUG_COMMON
,"Sending self update to %s.", ifp
->name
);
1454 xroutes
= xroute_stream();
1457 struct xroute
*xroute
= xroute_stream_next(xroutes
);
1458 if(xroute
== NULL
) break;
1459 send_update(ifp
, 0, xroute
->prefix
, xroute
->plen
);
1461 xroute_stream_done(xroutes
);
1463 flog_err(EC_BABEL_MEMORY
, "Couldn't allocate xroute stream.");
1468 send_ihu(struct neighbour
*neigh
, struct interface
*ifp
)
1470 babel_interface_nfo
*babel_ifp
= NULL
;
1471 int rxcost
, interval
;
1476 if(neigh
== NULL
&& ifp
== NULL
) {
1477 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1478 struct interface
*ifp_aux
;
1479 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1482 send_ihu(NULL
, ifp_aux
);
1488 struct neighbour
*ngh
;
1489 FOR_ALL_NEIGHBOURS(ngh
) {
1497 if(ifp
&& neigh
->ifp
!= ifp
)
1501 babel_ifp
= babel_get_if_nfo(ifp
);
1505 rxcost
= neighbour_rxcost(neigh
);
1506 interval
= (babel_ifp
->hello_interval
* 3 + 9) / 10;
1508 /* Conceptually, an IHU is a unicast message. We usually send them as
1509 multicast, since this allows aggregation into a single packet and
1510 avoids an ARP exchange. If we already have a unicast message queued
1511 for this neighbour, however, we might as well piggyback the IHU. */
1512 debugf(BABEL_DEBUG_COMMON
,"Sending %sihu %d on %s to %s.",
1513 unicast_neighbour
== neigh
? "unicast " : "",
1516 format_address(neigh
->address
));
1518 ll
= linklocal(neigh
->address
);
1520 if((babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) && neigh
->hello_send_us
1521 /* Checks whether the RTT data is not too old to be sent. */
1522 && timeval_minus_msec(&babel_now
,
1523 &neigh
->hello_rtt_receive_time
) < 1000000) {
1526 neigh
->hello_send_us
= 0;
1530 /* The length depends on the format of the address, and then an
1531 optional 10-bytes sub-TLV for timestamps (used to compute a RTT). */
1532 msglen
= (ll
? 14 : 22) + (send_rtt_data
? 10 : 0);
1534 if(unicast_neighbour
!= neigh
) {
1535 start_message(ifp
, MESSAGE_IHU
, msglen
);
1536 accumulate_byte(ifp
, ll
? 3 : 2);
1537 accumulate_byte(ifp
, 0);
1538 accumulate_short(ifp
, rxcost
);
1539 accumulate_short(ifp
, interval
);
1541 accumulate_bytes(ifp
, neigh
->address
+ 8, 8);
1543 accumulate_bytes(ifp
, neigh
->address
, 16);
1544 if (send_rtt_data
) {
1545 accumulate_byte(ifp
, SUBTLV_TIMESTAMP
);
1546 accumulate_byte(ifp
, 8);
1547 accumulate_int(ifp
, neigh
->hello_send_us
);
1548 accumulate_int(ifp
, time_us(neigh
->hello_rtt_receive_time
));
1550 end_message(ifp
, MESSAGE_IHU
, msglen
);
1553 rc
= start_unicast_message(neigh
, MESSAGE_IHU
, msglen
);
1555 accumulate_unicast_byte(neigh
, ll
? 3 : 2);
1556 accumulate_unicast_byte(neigh
, 0);
1557 accumulate_unicast_short(neigh
, rxcost
);
1558 accumulate_unicast_short(neigh
, interval
);
1560 accumulate_unicast_bytes(neigh
, neigh
->address
+ 8, 8);
1562 accumulate_unicast_bytes(neigh
, neigh
->address
, 16);
1563 if (send_rtt_data
) {
1564 accumulate_unicast_byte(neigh
, SUBTLV_TIMESTAMP
);
1565 accumulate_unicast_byte(neigh
, 8);
1566 accumulate_unicast_int(neigh
, neigh
->hello_send_us
);
1567 accumulate_unicast_int(neigh
,
1568 time_us(neigh
->hello_rtt_receive_time
));
1570 end_unicast_message(neigh
, MESSAGE_IHU
, msglen
);
1574 /* Send IHUs to all marginal neighbours */
1576 send_marginal_ihu(struct interface
*ifp
)
1578 struct neighbour
*neigh
;
1579 FOR_ALL_NEIGHBOURS(neigh
) {
1580 if(ifp
&& neigh
->ifp
!= ifp
)
1582 if(neigh
->txcost
>= 384 || (neigh
->reach
& 0xF000) != 0xF000)
1583 send_ihu(neigh
, ifp
);
1588 send_request(struct interface
*ifp
,
1589 const unsigned char *prefix
, unsigned char plen
)
1594 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1595 struct interface
*ifp_aux
;
1596 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1599 send_request(ifp_aux
, prefix
, plen
);
1604 /* make sure any buffered updates go out before this request. */
1610 debugf(BABEL_DEBUG_COMMON
,"sending request to %s for %s.",
1611 ifp
->name
, prefix
? format_prefix(prefix
, plen
) : "any");
1612 v4
= plen
>= 96 && v4mapped(prefix
);
1613 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1614 len
= !prefix
? 2 : 2 + pb
;
1616 start_message(ifp
, MESSAGE_REQUEST
, len
);
1617 accumulate_byte(ifp
, !prefix
? 0 : v4
? 1 : 2);
1618 accumulate_byte(ifp
, !prefix
? 0 : v4
? plen
- 96 : plen
);
1621 accumulate_bytes(ifp
, prefix
+ 12, pb
);
1623 accumulate_bytes(ifp
, prefix
, pb
);
1625 end_message(ifp
, MESSAGE_REQUEST
, len
);
1629 send_unicast_request(struct neighbour
*neigh
,
1630 const unsigned char *prefix
, unsigned char plen
)
1632 int rc
, v4
, pb
, len
;
1634 /* make sure any buffered updates go out before this request. */
1635 flushupdates(neigh
->ifp
);
1637 debugf(BABEL_DEBUG_COMMON
,"sending unicast request to %s for %s.",
1638 format_address(neigh
->address
),
1639 prefix
? format_prefix(prefix
, plen
) : "any");
1640 v4
= plen
>= 96 && v4mapped(prefix
);
1641 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1642 len
= !prefix
? 2 : 2 + pb
;
1644 rc
= start_unicast_message(neigh
, MESSAGE_REQUEST
, len
);
1646 accumulate_unicast_byte(neigh
, !prefix
? 0 : v4
? 1 : 2);
1647 accumulate_unicast_byte(neigh
, !prefix
? 0 : v4
? plen
- 96 : plen
);
1650 accumulate_unicast_bytes(neigh
, prefix
+ 12, pb
);
1652 accumulate_unicast_bytes(neigh
, prefix
, pb
);
1654 end_unicast_message(neigh
, MESSAGE_REQUEST
, len
);
1658 send_multihop_request(struct interface
*ifp
,
1659 const unsigned char *prefix
, unsigned char plen
,
1660 unsigned short seqno
, const unsigned char *id
,
1661 unsigned short hop_count
)
1665 /* Make sure any buffered updates go out before this request. */
1669 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1670 struct interface
*ifp_aux
;
1671 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1674 send_multihop_request(ifp_aux
, prefix
, plen
, seqno
, id
, hop_count
);
1682 debugf(BABEL_DEBUG_COMMON
,"Sending request (%d) on %s for %s.",
1683 hop_count
, ifp
->name
, format_prefix(prefix
, plen
));
1684 v4
= plen
>= 96 && v4mapped(prefix
);
1685 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1688 start_message(ifp
, MESSAGE_MH_REQUEST
, len
);
1689 accumulate_byte(ifp
, v4
? 1 : 2);
1690 accumulate_byte(ifp
, v4
? plen
- 96 : plen
);
1691 accumulate_short(ifp
, seqno
);
1692 accumulate_byte(ifp
, hop_count
);
1693 accumulate_byte(ifp
, 0);
1694 accumulate_bytes(ifp
, id
, 8);
1697 accumulate_bytes(ifp
, prefix
+ 12, pb
);
1699 accumulate_bytes(ifp
, prefix
, pb
);
1701 end_message(ifp
, MESSAGE_MH_REQUEST
, len
);
1705 send_unicast_multihop_request(struct neighbour
*neigh
,
1706 const unsigned char *prefix
, unsigned char plen
,
1707 unsigned short seqno
, const unsigned char *id
,
1708 unsigned short hop_count
)
1710 int rc
, v4
, pb
, len
;
1712 /* Make sure any buffered updates go out before this request. */
1713 flushupdates(neigh
->ifp
);
1715 debugf(BABEL_DEBUG_COMMON
,"Sending multi-hop request to %s for %s (%d hops).",
1716 format_address(neigh
->address
),
1717 format_prefix(prefix
, plen
), hop_count
);
1718 v4
= plen
>= 96 && v4mapped(prefix
);
1719 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1722 rc
= start_unicast_message(neigh
, MESSAGE_MH_REQUEST
, len
);
1724 accumulate_unicast_byte(neigh
, v4
? 1 : 2);
1725 accumulate_unicast_byte(neigh
, v4
? plen
- 96 : plen
);
1726 accumulate_unicast_short(neigh
, seqno
);
1727 accumulate_unicast_byte(neigh
, hop_count
);
1728 accumulate_unicast_byte(neigh
, 0);
1729 accumulate_unicast_bytes(neigh
, id
, 8);
1732 accumulate_unicast_bytes(neigh
, prefix
+ 12, pb
);
1734 accumulate_unicast_bytes(neigh
, prefix
, pb
);
1736 end_unicast_message(neigh
, MESSAGE_MH_REQUEST
, len
);
1740 send_request_resend(struct neighbour
*neigh
,
1741 const unsigned char *prefix
, unsigned char plen
,
1742 unsigned short seqno
, unsigned char *id
)
1745 send_unicast_multihop_request(neigh
, prefix
, plen
, seqno
, id
, 127);
1747 send_multihop_request(NULL
, prefix
, plen
, seqno
, id
, 127);
1749 record_resend(RESEND_REQUEST
, prefix
, plen
, seqno
, id
,
1750 neigh
? neigh
->ifp
: NULL
, resend_delay
);
1754 handle_request(struct neighbour
*neigh
, const unsigned char *prefix
,
1755 unsigned char plen
, unsigned char hop_count
,
1756 unsigned short seqno
, const unsigned char *id
)
1758 struct xroute
*xroute
;
1759 struct babel_route
*route
;
1760 struct neighbour
*successor
= NULL
;
1762 xroute
= find_xroute(prefix
, plen
);
1763 route
= find_installed_route(prefix
, plen
);
1765 if(xroute
&& (!route
|| xroute
->metric
<= kernel_metric
)) {
1766 if(hop_count
> 0 && memcmp(id
, myid
, 8) == 0) {
1767 if(seqno_compare(seqno
, myseqno
) > 0) {
1768 if(seqno_minus(seqno
, myseqno
) > 100) {
1769 /* Hopelessly out-of-date request */
1775 send_update(neigh
->ifp
, 1, prefix
, plen
);
1780 (memcmp(id
, route
->src
->id
, 8) != 0 ||
1781 seqno_compare(seqno
, route
->seqno
) <= 0)) {
1782 send_update(neigh
->ifp
, 1, prefix
, plen
);
1789 if(route
&& memcmp(id
, route
->src
->id
, 8) == 0 &&
1790 seqno_minus(seqno
, route
->seqno
) > 100) {
1791 /* Hopelessly out-of-date */
1795 if(request_redundant(neigh
->ifp
, prefix
, plen
, seqno
, id
))
1798 /* Let's try to forward this request. */
1799 if(route
&& route_metric(route
) < INFINITY
)
1800 successor
= route
->neigh
;
1802 if(!successor
|| successor
== neigh
) {
1803 /* We were about to forward a request to its requestor. Try to
1804 find a different neighbour to forward the request to. */
1805 struct babel_route
*other_route
;
1807 other_route
= find_best_route(prefix
, plen
, 0, neigh
);
1808 if(other_route
&& route_metric(other_route
) < INFINITY
)
1809 successor
= other_route
->neigh
;
1812 if(!successor
|| successor
== neigh
)
1816 send_unicast_multihop_request(successor
, prefix
, plen
, seqno
, id
,
1818 record_resend(RESEND_REQUEST
, prefix
, plen
, seqno
, id
,