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
,
750 "Warning: bucket full, dropping packet to %s.",
754 VALGRIND_MAKE_MEM_UNDEFINED(babel_ifp
->sendbuf
, babel_ifp
->bufsize
);
755 babel_ifp
->buffered
= 0;
756 babel_ifp
->buffered_hello
= -1;
757 babel_ifp
->have_buffered_id
= 0;
758 babel_ifp
->have_buffered_nh
= 0;
759 babel_ifp
->have_buffered_prefix
= 0;
760 babel_ifp
->flush_timeout
.tv_sec
= 0;
761 babel_ifp
->flush_timeout
.tv_usec
= 0;
765 schedule_flush(struct interface
*ifp
)
767 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
768 unsigned msecs
= jitter(babel_ifp
, 0);
769 if(babel_ifp
->flush_timeout
.tv_sec
!= 0 &&
770 timeval_minus_msec(&babel_ifp
->flush_timeout
, &babel_now
) < msecs
)
772 set_timeout(&babel_ifp
->flush_timeout
, msecs
);
776 schedule_flush_now(struct interface
*ifp
)
778 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
780 unsigned msecs
= roughly(10);
781 if(babel_ifp
->flush_timeout
.tv_sec
!= 0 &&
782 timeval_minus_msec(&babel_ifp
->flush_timeout
, &babel_now
) < msecs
)
784 set_timeout(&babel_ifp
->flush_timeout
, msecs
);
788 schedule_unicast_flush(unsigned msecs
)
790 if(!unicast_neighbour
)
792 if(unicast_flush_timeout
.tv_sec
!= 0 &&
793 timeval_minus_msec(&unicast_flush_timeout
, &babel_now
) < msecs
)
795 unicast_flush_timeout
.tv_usec
= (babel_now
.tv_usec
+ msecs
* 1000) %1000000;
796 unicast_flush_timeout
.tv_sec
=
797 babel_now
.tv_sec
+ (babel_now
.tv_usec
/ 1000 + msecs
) / 1000;
801 ensure_space(struct interface
*ifp
, int space
)
803 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
804 if(babel_ifp
->bufsize
- babel_ifp
->buffered
< space
)
809 start_message(struct interface
*ifp
, int type
, int len
)
811 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
812 if(babel_ifp
->bufsize
- babel_ifp
->buffered
< len
+ 2)
814 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = type
;
815 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = len
;
819 end_message(struct interface
*ifp
, int type
, int bytes
)
821 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
822 assert(babel_ifp
->buffered
>= bytes
+ 2 &&
823 babel_ifp
->sendbuf
[babel_ifp
->buffered
- bytes
- 2] == type
&&
824 babel_ifp
->sendbuf
[babel_ifp
->buffered
- bytes
- 1] == bytes
);
829 accumulate_byte(struct interface
*ifp
, unsigned char value
)
831 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
832 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = value
;
836 accumulate_short(struct interface
*ifp
, unsigned short value
)
838 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
839 DO_HTONS(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
);
840 babel_ifp
->buffered
+= 2;
844 accumulate_int(struct interface
*ifp
, unsigned int value
)
846 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
847 DO_HTONL(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
);
848 babel_ifp
->buffered
+= 4;
852 accumulate_bytes(struct interface
*ifp
,
853 const unsigned char *value
, unsigned len
)
855 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
856 memcpy(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
, len
);
857 babel_ifp
->buffered
+= len
;
861 start_unicast_message(struct neighbour
*neigh
, int type
, int len
)
863 if(unicast_neighbour
) {
864 if(neigh
!= unicast_neighbour
||
865 unicast_buffered
+ len
+ 2 >=
866 MIN(UNICAST_BUFSIZE
, babel_get_if_nfo(neigh
->ifp
)->bufsize
))
870 unicast_buffer
= malloc(UNICAST_BUFSIZE
);
871 if(!unicast_buffer
) {
872 flog_err(EC_BABEL_MEMORY
, "malloc(unicast_buffer): %s",
873 safe_strerror(errno
));
877 unicast_neighbour
= neigh
;
879 unicast_buffer
[unicast_buffered
++] = type
;
880 unicast_buffer
[unicast_buffered
++] = len
;
885 end_unicast_message(struct neighbour
*neigh
, int type
, int bytes
)
887 assert(unicast_neighbour
== neigh
&& unicast_buffered
>= bytes
+ 2 &&
888 unicast_buffer
[unicast_buffered
- bytes
- 2] == type
&&
889 unicast_buffer
[unicast_buffered
- bytes
- 1] == bytes
);
890 schedule_unicast_flush(jitter(babel_get_if_nfo(neigh
->ifp
), 0));
894 accumulate_unicast_byte(struct neighbour
*neigh
, unsigned char value
)
896 unicast_buffer
[unicast_buffered
++] = value
;
900 accumulate_unicast_short(struct neighbour
*neigh
, unsigned short value
)
902 DO_HTONS(unicast_buffer
+ unicast_buffered
, value
);
903 unicast_buffered
+= 2;
907 accumulate_unicast_int(struct neighbour
*neigh
, unsigned int value
)
909 DO_HTONL(unicast_buffer
+ unicast_buffered
, value
);
910 unicast_buffered
+= 4;
914 accumulate_unicast_bytes(struct neighbour
*neigh
,
915 const unsigned char *value
, unsigned len
)
917 memcpy(unicast_buffer
+ unicast_buffered
, value
, len
);
918 unicast_buffered
+= len
;
922 send_ack(struct neighbour
*neigh
, unsigned short nonce
, unsigned short interval
)
925 debugf(BABEL_DEBUG_COMMON
,"Sending ack (%04x) to %s on %s.",
926 nonce
, format_address(neigh
->address
), neigh
->ifp
->name
);
927 rc
= start_unicast_message(neigh
, MESSAGE_ACK
, 2); if(rc
< 0) return;
928 accumulate_unicast_short(neigh
, nonce
);
929 end_unicast_message(neigh
, MESSAGE_ACK
, 2);
930 /* Roughly yields a value no larger than 3/2, so this meets the deadline */
931 schedule_unicast_flush(roughly(interval
* 6));
935 send_hello_noupdate(struct interface
*ifp
, unsigned interval
)
937 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
938 /* This avoids sending multiple hellos in a single packet, which breaks
939 link quality estimation. */
940 if(babel_ifp
->buffered_hello
>= 0)
943 babel_ifp
->hello_seqno
= seqno_plus(babel_ifp
->hello_seqno
, 1);
944 set_timeout(&babel_ifp
->hello_timeout
, babel_ifp
->hello_interval
);
949 debugf(BABEL_DEBUG_COMMON
,"Sending hello %d (%d) to %s.",
950 babel_ifp
->hello_seqno
, interval
, ifp
->name
);
952 start_message(ifp
, MESSAGE_HELLO
,
953 (babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) ? 12 : 6);
954 babel_ifp
->buffered_hello
= babel_ifp
->buffered
- 2;
955 accumulate_short(ifp
, 0);
956 accumulate_short(ifp
, babel_ifp
->hello_seqno
);
957 accumulate_short(ifp
, interval
> 0xFFFF ? 0xFFFF : interval
);
958 if(babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) {
959 /* Sub-TLV containing the local time of emission. We use a
960 Pad4 sub-TLV, which we'll fill just before sending. */
961 accumulate_byte(ifp
, SUBTLV_PADN
);
962 accumulate_byte(ifp
, 4);
963 accumulate_int(ifp
, 0);
965 end_message(ifp
, MESSAGE_HELLO
,
966 (babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) ? 12 : 6);
970 send_hello(struct interface
*ifp
)
972 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
973 send_hello_noupdate(ifp
, (babel_ifp
->hello_interval
+ 9) / 10);
974 /* Send full IHU every 3 hellos, and marginal IHU each time */
975 if(babel_ifp
->hello_seqno
% 3 == 0)
978 send_marginal_ihu(ifp
);
982 flush_unicast(int dofree
)
984 struct sockaddr_in6 sin6
;
987 if(unicast_buffered
== 0)
990 if(!if_up(unicast_neighbour
->ifp
))
993 /* Preserve ordering of messages */
994 flushbuf(unicast_neighbour
->ifp
);
996 if(check_bucket(unicast_neighbour
->ifp
)) {
997 memset(&sin6
, 0, sizeof(sin6
));
998 sin6
.sin6_family
= AF_INET6
;
999 memcpy(&sin6
.sin6_addr
, unicast_neighbour
->address
, 16);
1000 sin6
.sin6_port
= htons(protocol_port
);
1001 sin6
.sin6_scope_id
= unicast_neighbour
->ifp
->ifindex
;
1002 DO_HTONS(packet_header
+ 2, unicast_buffered
);
1003 fill_rtt_message(unicast_neighbour
->ifp
);
1004 rc
= babel_send(protocol_socket
,
1005 packet_header
, sizeof(packet_header
),
1006 unicast_buffer
, unicast_buffered
,
1007 (struct sockaddr
*)&sin6
, sizeof(sin6
));
1009 flog_err(EC_BABEL_PACKET
, "send(unicast): %s",
1010 safe_strerror(errno
));
1012 flog_err(EC_BABEL_PACKET
,
1013 "Warning: bucket full, dropping unicast packet to %s if %s.",
1014 format_address(unicast_neighbour
->address
),
1015 unicast_neighbour
->ifp
->name
);
1019 VALGRIND_MAKE_MEM_UNDEFINED(unicast_buffer
, UNICAST_BUFSIZE
);
1020 unicast_buffered
= 0;
1021 if(dofree
&& unicast_buffer
) {
1022 free(unicast_buffer
);
1023 unicast_buffer
= NULL
;
1025 unicast_neighbour
= NULL
;
1026 unicast_flush_timeout
.tv_sec
= 0;
1027 unicast_flush_timeout
.tv_usec
= 0;
1031 really_send_update(struct interface
*ifp
,
1032 const unsigned char *id
,
1033 const unsigned char *prefix
, unsigned char plen
,
1034 unsigned short seqno
, unsigned short metric
,
1035 unsigned char *channels
, int channels_len
)
1037 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1038 int add_metric
, v4
, real_plen
, omit
= 0;
1039 const unsigned char *real_prefix
;
1040 unsigned short flags
= 0;
1043 if(diversity_kind
!= DIVERSITY_CHANNEL
)
1046 channels_size
= channels_len
>= 0 ? channels_len
+ 2 : 0;
1051 add_metric
= output_filter(id
, prefix
, plen
, ifp
->ifindex
);
1052 if(add_metric
>= INFINITY
)
1055 metric
= MIN(metric
+ add_metric
, INFINITY
);
1057 ensure_space(ifp
, 20 + 12 + 28);
1059 v4
= plen
>= 96 && v4mapped(prefix
);
1062 if(!babel_ifp
->ipv4
)
1064 if(!babel_ifp
->have_buffered_nh
||
1065 memcmp(babel_ifp
->buffered_nh
, babel_ifp
->ipv4
, 4) != 0) {
1066 start_message(ifp
, MESSAGE_NH
, 6);
1067 accumulate_byte(ifp
, 1);
1068 accumulate_byte(ifp
, 0);
1069 accumulate_bytes(ifp
, babel_ifp
->ipv4
, 4);
1070 end_message(ifp
, MESSAGE_NH
, 6);
1071 memcpy(babel_ifp
->buffered_nh
, babel_ifp
->ipv4
, 4);
1072 babel_ifp
->have_buffered_nh
= 1;
1075 real_prefix
= prefix
+ 12;
1076 real_plen
= plen
- 96;
1078 if(babel_ifp
->have_buffered_prefix
) {
1079 while(omit
< plen
/ 8 &&
1080 babel_ifp
->buffered_prefix
[omit
] == prefix
[omit
])
1083 if(!babel_ifp
->have_buffered_prefix
|| plen
>= 48)
1085 real_prefix
= prefix
;
1089 if(!babel_ifp
->have_buffered_id
1090 || memcmp(id
, babel_ifp
->buffered_id
, 8) != 0) {
1091 if(real_plen
== 128 && memcmp(real_prefix
+ 8, id
, 8) == 0) {
1094 start_message(ifp
, MESSAGE_ROUTER_ID
, 10);
1095 accumulate_short(ifp
, 0);
1096 accumulate_bytes(ifp
, id
, 8);
1097 end_message(ifp
, MESSAGE_ROUTER_ID
, 10);
1099 memcpy(babel_ifp
->buffered_id
, id
, sizeof(babel_ifp
->buffered_id
));
1100 babel_ifp
->have_buffered_id
= 1;
1103 start_message(ifp
, MESSAGE_UPDATE
, 10 + (real_plen
+ 7) / 8 - omit
+
1105 accumulate_byte(ifp
, v4
? 1 : 2);
1106 accumulate_byte(ifp
, flags
);
1107 accumulate_byte(ifp
, real_plen
);
1108 accumulate_byte(ifp
, omit
);
1109 accumulate_short(ifp
, (babel_ifp
->update_interval
+ 5) / 10);
1110 accumulate_short(ifp
, seqno
);
1111 accumulate_short(ifp
, metric
);
1112 accumulate_bytes(ifp
, real_prefix
+ omit
, (real_plen
+ 7) / 8 - omit
);
1113 /* Note that an empty channels TLV is different from no such TLV. */
1114 if(channels_len
>= 0) {
1115 accumulate_byte(ifp
, 2);
1116 accumulate_byte(ifp
, channels_len
);
1118 if (channels
&& channels_len
> 0)
1119 accumulate_bytes(ifp
, channels
, channels_len
);
1121 end_message(ifp
, MESSAGE_UPDATE
, 10 + (real_plen
+ 7) / 8 - omit
+
1125 memcpy(babel_ifp
->buffered_prefix
, prefix
, 16);
1126 babel_ifp
->have_buffered_prefix
= 1;
1131 compare_buffered_updates(const void *av
, const void *bv
)
1133 const struct buffered_update
*a
= av
, *b
= bv
;
1134 int rc
, v4a
, v4b
, ma
, mb
;
1136 rc
= memcmp(a
->id
, b
->id
, 8);
1140 v4a
= (a
->plen
>= 96 && v4mapped(a
->prefix
));
1141 v4b
= (b
->plen
>= 96 && v4mapped(b
->prefix
));
1148 ma
= (!v4a
&& a
->plen
== 128 && memcmp(a
->prefix
+ 8, a
->id
, 8) == 0);
1149 mb
= (!v4b
&& b
->plen
== 128 && memcmp(b
->prefix
+ 8, b
->id
, 8) == 0);
1156 if(a
->plen
< b
->plen
)
1158 else if(a
->plen
> b
->plen
)
1161 return memcmp(a
->prefix
, b
->prefix
, 16);
1165 flushupdates(struct interface
*ifp
)
1167 babel_interface_nfo
*babel_ifp
= NULL
;
1168 struct xroute
*xroute
;
1169 struct babel_route
*route
;
1170 const unsigned char *last_prefix
= NULL
;
1171 unsigned char last_plen
= 0xFF;
1175 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1176 struct interface
*ifp_aux
;
1177 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1178 flushupdates(ifp_aux
);
1182 babel_ifp
= babel_get_if_nfo(ifp
);
1183 if(babel_ifp
->num_buffered_updates
> 0) {
1184 struct buffered_update
*b
= babel_ifp
->buffered_updates
;
1185 int n
= babel_ifp
->num_buffered_updates
;
1187 babel_ifp
->buffered_updates
= NULL
;
1188 babel_ifp
->update_bufsize
= 0;
1189 babel_ifp
->num_buffered_updates
= 0;
1194 debugf(BABEL_DEBUG_COMMON
," (flushing %d buffered updates on %s (%d))",
1195 n
, ifp
->name
, ifp
->ifindex
);
1197 /* In order to send fewer update messages, we want to send updates
1198 with the same router-id together, with IPv6 going out before IPv4. */
1200 for(i
= 0; i
< n
; i
++) {
1201 route
= find_installed_route(b
[i
].prefix
, b
[i
].plen
);
1203 memcpy(b
[i
].id
, route
->src
->id
, 8);
1205 memcpy(b
[i
].id
, myid
, 8);
1208 qsort(b
, n
, sizeof(struct buffered_update
), compare_buffered_updates
);
1210 for(i
= 0; i
< n
; i
++) {
1211 /* The same update may be scheduled multiple times before it is
1212 sent out. Since our buffer is now sorted, it is enough to
1213 compare with the previous update. */
1216 if(b
[i
].plen
== last_plen
&&
1217 memcmp(b
[i
].prefix
, last_prefix
, 16) == 0)
1221 xroute
= find_xroute(b
[i
].prefix
, b
[i
].plen
);
1222 route
= find_installed_route(b
[i
].prefix
, b
[i
].plen
);
1224 if(xroute
&& (!route
|| xroute
->metric
<= kernel_metric
)) {
1225 really_send_update(ifp
, myid
,
1226 xroute
->prefix
, xroute
->plen
,
1227 myseqno
, xroute
->metric
,
1229 last_prefix
= xroute
->prefix
;
1230 last_plen
= xroute
->plen
;
1232 unsigned char channels
[DIVERSITY_HOPS
];
1234 struct interface
*route_ifp
= route
->neigh
->ifp
;
1235 struct babel_interface
*babel_route_ifp
= NULL
;
1236 unsigned short metric
;
1237 unsigned short seqno
;
1239 seqno
= route
->seqno
;
1241 route_interferes(route
, ifp
) ?
1242 route_metric(route
) :
1243 route_metric_noninterfering(route
);
1245 if(metric
< INFINITY
)
1246 satisfy_request(route
->src
->prefix
, route
->src
->plen
,
1247 seqno
, route
->src
->id
, ifp
);
1248 if((babel_ifp
->flags
& BABEL_IF_SPLIT_HORIZON
) &&
1249 route
->neigh
->ifp
== ifp
)
1252 babel_route_ifp
= babel_get_if_nfo(route_ifp
);
1253 if(babel_route_ifp
->channel
==BABEL_IF_CHANNEL_NONINTERFERING
) {
1254 memcpy(channels
, route
->channels
, DIVERSITY_HOPS
);
1256 if(babel_route_ifp
->channel
== BABEL_IF_CHANNEL_UNKNOWN
)
1257 channels
[0] = BABEL_IF_CHANNEL_INTERFERING
;
1259 assert(babel_route_ifp
->channel
> 0 &&
1260 babel_route_ifp
->channel
<= 255);
1261 channels
[0] = babel_route_ifp
->channel
;
1263 memcpy(channels
+ 1, route
->channels
, DIVERSITY_HOPS
- 1);
1266 chlen
= channels_len(channels
);
1267 really_send_update(ifp
, route
->src
->id
,
1272 update_source(route
->src
, seqno
, metric
);
1273 last_prefix
= route
->src
->prefix
;
1274 last_plen
= route
->src
->plen
;
1276 /* There's no route for this prefix. This can happen shortly
1277 after an xroute has been retracted, so send a retraction. */
1278 really_send_update(ifp
, myid
, b
[i
].prefix
, b
[i
].plen
,
1279 myseqno
, INFINITY
, NULL
, -1);
1282 schedule_flush_now(ifp
);
1286 babel_ifp
->update_flush_timeout
.tv_sec
= 0;
1287 babel_ifp
->update_flush_timeout
.tv_usec
= 0;
1291 schedule_update_flush(struct interface
*ifp
, int urgent
)
1293 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1295 msecs
= update_jitter(babel_ifp
, urgent
);
1296 if(babel_ifp
->update_flush_timeout
.tv_sec
!= 0 &&
1297 timeval_minus_msec(&babel_ifp
->update_flush_timeout
, &babel_now
) < msecs
)
1299 set_timeout(&babel_ifp
->update_flush_timeout
, msecs
);
1303 buffer_update(struct interface
*ifp
,
1304 const unsigned char *prefix
, unsigned char plen
)
1306 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1307 if(babel_ifp
->num_buffered_updates
> 0 &&
1308 babel_ifp
->num_buffered_updates
>= babel_ifp
->update_bufsize
)
1311 if(babel_ifp
->update_bufsize
== 0) {
1313 assert(babel_ifp
->buffered_updates
== NULL
);
1314 /* Allocate enough space to hold a full update. Since the
1315 number of installed routes will grow over time, make sure we
1316 have enough space to send a full-ish frame. */
1317 n
= installed_routes_estimate() + xroutes_estimate() + 4;
1318 n
= MAX(n
, babel_ifp
->bufsize
/ 16);
1320 babel_ifp
->buffered_updates
= malloc(n
*sizeof(struct buffered_update
));
1321 if(babel_ifp
->buffered_updates
== NULL
) {
1322 flog_err(EC_BABEL_MEMORY
, "malloc(buffered_updates): %s",
1323 safe_strerror(errno
));
1325 /* Try again with a tiny buffer. */
1331 babel_ifp
->update_bufsize
= n
;
1332 babel_ifp
->num_buffered_updates
= 0;
1335 memcpy(babel_ifp
->buffered_updates
[babel_ifp
->num_buffered_updates
].prefix
,
1337 babel_ifp
->buffered_updates
[babel_ifp
->num_buffered_updates
].plen
= plen
;
1338 babel_ifp
->num_buffered_updates
++;
1342 send_update(struct interface
*ifp
, int urgent
,
1343 const unsigned char *prefix
, unsigned char plen
)
1345 babel_interface_nfo
*babel_ifp
= NULL
;
1348 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1349 struct interface
*ifp_aux
;
1350 struct babel_route
*route
;
1351 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1352 send_update(ifp_aux
, urgent
, prefix
, plen
);
1354 /* Since flushupdates only deals with non-wildcard interfaces, we
1355 need to do this now. */
1356 route
= find_installed_route(prefix
, plen
);
1357 if(route
&& route_metric(route
) < INFINITY
)
1358 satisfy_request(prefix
, plen
, route
->src
->seqno
, route
->src
->id
,
1367 babel_ifp
= babel_get_if_nfo(ifp
);
1369 debugf(BABEL_DEBUG_COMMON
,"Sending update to %s for %s.",
1370 ifp
->name
, format_prefix(prefix
, plen
));
1371 buffer_update(ifp
, prefix
, plen
);
1373 struct route_stream
*routes
= NULL
;
1374 send_self_update(ifp
);
1375 debugf(BABEL_DEBUG_COMMON
,"Sending update to %s for any.", ifp
->name
);
1376 routes
= route_stream(1);
1379 struct babel_route
*route
= route_stream_next(routes
);
1382 buffer_update(ifp
, route
->src
->prefix
, route
->src
->plen
);
1384 route_stream_done(routes
);
1386 flog_err(EC_BABEL_MEMORY
, "Couldn't allocate route stream.");
1388 set_timeout(&babel_ifp
->update_timeout
, babel_ifp
->update_interval
);
1389 babel_ifp
->last_update_time
= babel_now
.tv_sec
;
1391 schedule_update_flush(ifp
, urgent
);
1395 send_update_resend(struct interface
*ifp
,
1396 const unsigned char *prefix
, unsigned char plen
)
1398 assert(prefix
!= NULL
);
1400 send_update(ifp
, 1, prefix
, plen
);
1401 record_resend(RESEND_UPDATE
, prefix
, plen
, 0, NULL
, NULL
, resend_delay
);
1405 send_wildcard_retraction(struct interface
*ifp
)
1407 babel_interface_nfo
*babel_ifp
= NULL
;
1409 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1410 struct interface
*ifp_aux
;
1411 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1412 send_wildcard_retraction(ifp_aux
);
1419 babel_ifp
= babel_get_if_nfo(ifp
);
1420 start_message(ifp
, MESSAGE_UPDATE
, 10);
1421 accumulate_byte(ifp
, 0);
1422 accumulate_byte(ifp
, 0x40);
1423 accumulate_byte(ifp
, 0);
1424 accumulate_byte(ifp
, 0);
1425 accumulate_short(ifp
, 0xFFFF);
1426 accumulate_short(ifp
, myseqno
);
1427 accumulate_short(ifp
, 0xFFFF);
1428 end_message(ifp
, MESSAGE_UPDATE
, 10);
1430 babel_ifp
->have_buffered_id
= 0;
1434 update_myseqno(void)
1436 myseqno
= seqno_plus(myseqno
, 1);
1440 send_self_update(struct interface
*ifp
)
1442 struct xroute_stream
*xroutes
;
1444 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1445 struct interface
*ifp_aux
;
1446 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1449 send_self_update(ifp_aux
);
1454 debugf(BABEL_DEBUG_COMMON
,"Sending self update to %s.", ifp
->name
);
1455 xroutes
= xroute_stream();
1458 struct xroute
*xroute
= xroute_stream_next(xroutes
);
1459 if(xroute
== NULL
) break;
1460 send_update(ifp
, 0, xroute
->prefix
, xroute
->plen
);
1462 xroute_stream_done(xroutes
);
1464 flog_err(EC_BABEL_MEMORY
, "Couldn't allocate xroute stream.");
1469 send_ihu(struct neighbour
*neigh
, struct interface
*ifp
)
1471 babel_interface_nfo
*babel_ifp
= NULL
;
1472 int rxcost
, interval
;
1477 if(neigh
== NULL
&& ifp
== NULL
) {
1478 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1479 struct interface
*ifp_aux
;
1480 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1483 send_ihu(NULL
, ifp_aux
);
1489 struct neighbour
*ngh
;
1490 FOR_ALL_NEIGHBOURS(ngh
) {
1498 if(ifp
&& neigh
->ifp
!= ifp
)
1502 babel_ifp
= babel_get_if_nfo(ifp
);
1506 rxcost
= neighbour_rxcost(neigh
);
1507 interval
= (babel_ifp
->hello_interval
* 3 + 9) / 10;
1509 /* Conceptually, an IHU is a unicast message. We usually send them as
1510 multicast, since this allows aggregation into a single packet and
1511 avoids an ARP exchange. If we already have a unicast message queued
1512 for this neighbour, however, we might as well piggyback the IHU. */
1513 debugf(BABEL_DEBUG_COMMON
,"Sending %sihu %d on %s to %s.",
1514 unicast_neighbour
== neigh
? "unicast " : "",
1517 format_address(neigh
->address
));
1519 ll
= linklocal(neigh
->address
);
1521 if((babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) && neigh
->hello_send_us
1522 /* Checks whether the RTT data is not too old to be sent. */
1523 && timeval_minus_msec(&babel_now
,
1524 &neigh
->hello_rtt_receive_time
) < 1000000) {
1527 neigh
->hello_send_us
= 0;
1531 /* The length depends on the format of the address, and then an
1532 optional 10-bytes sub-TLV for timestamps (used to compute a RTT). */
1533 msglen
= (ll
? 14 : 22) + (send_rtt_data
? 10 : 0);
1535 if(unicast_neighbour
!= neigh
) {
1536 start_message(ifp
, MESSAGE_IHU
, msglen
);
1537 accumulate_byte(ifp
, ll
? 3 : 2);
1538 accumulate_byte(ifp
, 0);
1539 accumulate_short(ifp
, rxcost
);
1540 accumulate_short(ifp
, interval
);
1542 accumulate_bytes(ifp
, neigh
->address
+ 8, 8);
1544 accumulate_bytes(ifp
, neigh
->address
, 16);
1545 if (send_rtt_data
) {
1546 accumulate_byte(ifp
, SUBTLV_TIMESTAMP
);
1547 accumulate_byte(ifp
, 8);
1548 accumulate_int(ifp
, neigh
->hello_send_us
);
1549 accumulate_int(ifp
, time_us(neigh
->hello_rtt_receive_time
));
1551 end_message(ifp
, MESSAGE_IHU
, msglen
);
1554 rc
= start_unicast_message(neigh
, MESSAGE_IHU
, msglen
);
1556 accumulate_unicast_byte(neigh
, ll
? 3 : 2);
1557 accumulate_unicast_byte(neigh
, 0);
1558 accumulate_unicast_short(neigh
, rxcost
);
1559 accumulate_unicast_short(neigh
, interval
);
1561 accumulate_unicast_bytes(neigh
, neigh
->address
+ 8, 8);
1563 accumulate_unicast_bytes(neigh
, neigh
->address
, 16);
1564 if (send_rtt_data
) {
1565 accumulate_unicast_byte(neigh
, SUBTLV_TIMESTAMP
);
1566 accumulate_unicast_byte(neigh
, 8);
1567 accumulate_unicast_int(neigh
, neigh
->hello_send_us
);
1568 accumulate_unicast_int(neigh
,
1569 time_us(neigh
->hello_rtt_receive_time
));
1571 end_unicast_message(neigh
, MESSAGE_IHU
, msglen
);
1575 /* Send IHUs to all marginal neighbours */
1577 send_marginal_ihu(struct interface
*ifp
)
1579 struct neighbour
*neigh
;
1580 FOR_ALL_NEIGHBOURS(neigh
) {
1581 if(ifp
&& neigh
->ifp
!= ifp
)
1583 if(neigh
->txcost
>= 384 || (neigh
->reach
& 0xF000) != 0xF000)
1584 send_ihu(neigh
, ifp
);
1589 send_request(struct interface
*ifp
,
1590 const unsigned char *prefix
, unsigned char plen
)
1595 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1596 struct interface
*ifp_aux
;
1597 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1600 send_request(ifp_aux
, prefix
, plen
);
1605 /* make sure any buffered updates go out before this request. */
1611 debugf(BABEL_DEBUG_COMMON
,"sending request to %s for %s.",
1612 ifp
->name
, prefix
? format_prefix(prefix
, plen
) : "any");
1613 v4
= plen
>= 96 && v4mapped(prefix
);
1614 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1615 len
= !prefix
? 2 : 2 + pb
;
1617 start_message(ifp
, MESSAGE_REQUEST
, len
);
1618 accumulate_byte(ifp
, !prefix
? 0 : v4
? 1 : 2);
1619 accumulate_byte(ifp
, !prefix
? 0 : v4
? plen
- 96 : plen
);
1622 accumulate_bytes(ifp
, prefix
+ 12, pb
);
1624 accumulate_bytes(ifp
, prefix
, pb
);
1626 end_message(ifp
, MESSAGE_REQUEST
, len
);
1630 send_unicast_request(struct neighbour
*neigh
,
1631 const unsigned char *prefix
, unsigned char plen
)
1633 int rc
, v4
, pb
, len
;
1635 /* make sure any buffered updates go out before this request. */
1636 flushupdates(neigh
->ifp
);
1638 debugf(BABEL_DEBUG_COMMON
,"sending unicast request to %s for %s.",
1639 format_address(neigh
->address
),
1640 prefix
? format_prefix(prefix
, plen
) : "any");
1641 v4
= plen
>= 96 && v4mapped(prefix
);
1642 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1643 len
= !prefix
? 2 : 2 + pb
;
1645 rc
= start_unicast_message(neigh
, MESSAGE_REQUEST
, len
);
1647 accumulate_unicast_byte(neigh
, !prefix
? 0 : v4
? 1 : 2);
1648 accumulate_unicast_byte(neigh
, !prefix
? 0 : v4
? plen
- 96 : plen
);
1651 accumulate_unicast_bytes(neigh
, prefix
+ 12, pb
);
1653 accumulate_unicast_bytes(neigh
, prefix
, pb
);
1655 end_unicast_message(neigh
, MESSAGE_REQUEST
, len
);
1659 send_multihop_request(struct interface
*ifp
,
1660 const unsigned char *prefix
, unsigned char plen
,
1661 unsigned short seqno
, const unsigned char *id
,
1662 unsigned short hop_count
)
1666 /* Make sure any buffered updates go out before this request. */
1670 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1671 struct interface
*ifp_aux
;
1672 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1675 send_multihop_request(ifp_aux
, prefix
, plen
, seqno
, id
, hop_count
);
1683 debugf(BABEL_DEBUG_COMMON
,"Sending request (%d) on %s for %s.",
1684 hop_count
, ifp
->name
, format_prefix(prefix
, plen
));
1685 v4
= plen
>= 96 && v4mapped(prefix
);
1686 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1689 start_message(ifp
, MESSAGE_MH_REQUEST
, len
);
1690 accumulate_byte(ifp
, v4
? 1 : 2);
1691 accumulate_byte(ifp
, v4
? plen
- 96 : plen
);
1692 accumulate_short(ifp
, seqno
);
1693 accumulate_byte(ifp
, hop_count
);
1694 accumulate_byte(ifp
, 0);
1695 accumulate_bytes(ifp
, id
, 8);
1698 accumulate_bytes(ifp
, prefix
+ 12, pb
);
1700 accumulate_bytes(ifp
, prefix
, pb
);
1702 end_message(ifp
, MESSAGE_MH_REQUEST
, len
);
1706 send_unicast_multihop_request(struct neighbour
*neigh
,
1707 const unsigned char *prefix
, unsigned char plen
,
1708 unsigned short seqno
, const unsigned char *id
,
1709 unsigned short hop_count
)
1711 int rc
, v4
, pb
, len
;
1713 /* Make sure any buffered updates go out before this request. */
1714 flushupdates(neigh
->ifp
);
1716 debugf(BABEL_DEBUG_COMMON
,"Sending multi-hop request to %s for %s (%d hops).",
1717 format_address(neigh
->address
),
1718 format_prefix(prefix
, plen
), hop_count
);
1719 v4
= plen
>= 96 && v4mapped(prefix
);
1720 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1723 rc
= start_unicast_message(neigh
, MESSAGE_MH_REQUEST
, len
);
1725 accumulate_unicast_byte(neigh
, v4
? 1 : 2);
1726 accumulate_unicast_byte(neigh
, v4
? plen
- 96 : plen
);
1727 accumulate_unicast_short(neigh
, seqno
);
1728 accumulate_unicast_byte(neigh
, hop_count
);
1729 accumulate_unicast_byte(neigh
, 0);
1730 accumulate_unicast_bytes(neigh
, id
, 8);
1733 accumulate_unicast_bytes(neigh
, prefix
+ 12, pb
);
1735 accumulate_unicast_bytes(neigh
, prefix
, pb
);
1737 end_unicast_message(neigh
, MESSAGE_MH_REQUEST
, len
);
1741 send_request_resend(struct neighbour
*neigh
,
1742 const unsigned char *prefix
, unsigned char plen
,
1743 unsigned short seqno
, unsigned char *id
)
1746 send_unicast_multihop_request(neigh
, prefix
, plen
, seqno
, id
, 127);
1748 send_multihop_request(NULL
, prefix
, plen
, seqno
, id
, 127);
1750 record_resend(RESEND_REQUEST
, prefix
, plen
, seqno
, id
,
1751 neigh
? neigh
->ifp
: NULL
, resend_delay
);
1755 handle_request(struct neighbour
*neigh
, const unsigned char *prefix
,
1756 unsigned char plen
, unsigned char hop_count
,
1757 unsigned short seqno
, const unsigned char *id
)
1759 struct xroute
*xroute
;
1760 struct babel_route
*route
;
1761 struct neighbour
*successor
= NULL
;
1763 xroute
= find_xroute(prefix
, plen
);
1764 route
= find_installed_route(prefix
, plen
);
1766 if(xroute
&& (!route
|| xroute
->metric
<= kernel_metric
)) {
1767 if(hop_count
> 0 && memcmp(id
, myid
, 8) == 0) {
1768 if(seqno_compare(seqno
, myseqno
) > 0) {
1769 if(seqno_minus(seqno
, myseqno
) > 100) {
1770 /* Hopelessly out-of-date request */
1776 send_update(neigh
->ifp
, 1, prefix
, plen
);
1781 (memcmp(id
, route
->src
->id
, 8) != 0 ||
1782 seqno_compare(seqno
, route
->seqno
) <= 0)) {
1783 send_update(neigh
->ifp
, 1, prefix
, plen
);
1790 if(route
&& memcmp(id
, route
->src
->id
, 8) == 0 &&
1791 seqno_minus(seqno
, route
->seqno
) > 100) {
1792 /* Hopelessly out-of-date */
1796 if(request_redundant(neigh
->ifp
, prefix
, plen
, seqno
, id
))
1799 /* Let's try to forward this request. */
1800 if(route
&& route_metric(route
) < INFINITY
)
1801 successor
= route
->neigh
;
1803 if(!successor
|| successor
== neigh
) {
1804 /* We were about to forward a request to its requestor. Try to
1805 find a different neighbour to forward the request to. */
1806 struct babel_route
*other_route
;
1808 other_route
= find_best_route(prefix
, plen
, 0, neigh
);
1809 if(other_route
&& route_metric(other_route
) < INFINITY
)
1810 successor
= other_route
->neigh
;
1813 if(!successor
|| successor
== neigh
)
1817 send_unicast_multihop_request(successor
, prefix
, plen
, seqno
, id
,
1819 record_resend(RESEND_REQUEST
, prefix
, plen
, seqno
, id
,