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.\n",
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 "
714 "(this shouldn't happen)");
722 flushbuf(struct interface
*ifp
)
725 struct sockaddr_in6 sin6
;
726 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
728 assert(babel_ifp
->buffered
<= babel_ifp
->bufsize
);
732 if(babel_ifp
->buffered
> 0) {
733 debugf(BABEL_DEBUG_COMMON
," (flushing %d buffered bytes on %s)",
734 babel_ifp
->buffered
, ifp
->name
);
735 if(check_bucket(ifp
)) {
736 memset(&sin6
, 0, sizeof(sin6
));
737 sin6
.sin6_family
= AF_INET6
;
738 memcpy(&sin6
.sin6_addr
, protocol_group
, 16);
739 sin6
.sin6_port
= htons(protocol_port
);
740 sin6
.sin6_scope_id
= ifp
->ifindex
;
741 DO_HTONS(packet_header
+ 2, babel_ifp
->buffered
);
742 fill_rtt_message(ifp
);
743 rc
= babel_send(protocol_socket
,
744 packet_header
, sizeof(packet_header
),
745 babel_ifp
->sendbuf
, babel_ifp
->buffered
,
746 (struct sockaddr
*)&sin6
, sizeof(sin6
));
748 flog_err(EC_BABEL_PACKET
, "send: %s", safe_strerror(errno
));
750 flog_err(EC_BABEL_PACKET
,
751 "Warning: bucket full, dropping packet to %s.",
755 VALGRIND_MAKE_MEM_UNDEFINED(babel_ifp
->sendbuf
, babel_ifp
->bufsize
);
756 babel_ifp
->buffered
= 0;
757 babel_ifp
->buffered_hello
= -1;
758 babel_ifp
->have_buffered_id
= 0;
759 babel_ifp
->have_buffered_nh
= 0;
760 babel_ifp
->have_buffered_prefix
= 0;
761 babel_ifp
->flush_timeout
.tv_sec
= 0;
762 babel_ifp
->flush_timeout
.tv_usec
= 0;
766 schedule_flush(struct interface
*ifp
)
768 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
769 unsigned msecs
= jitter(babel_ifp
, 0);
770 if(babel_ifp
->flush_timeout
.tv_sec
!= 0 &&
771 timeval_minus_msec(&babel_ifp
->flush_timeout
, &babel_now
) < msecs
)
773 set_timeout(&babel_ifp
->flush_timeout
, msecs
);
777 schedule_flush_now(struct interface
*ifp
)
779 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
781 unsigned msecs
= roughly(10);
782 if(babel_ifp
->flush_timeout
.tv_sec
!= 0 &&
783 timeval_minus_msec(&babel_ifp
->flush_timeout
, &babel_now
) < msecs
)
785 set_timeout(&babel_ifp
->flush_timeout
, msecs
);
789 schedule_unicast_flush(unsigned msecs
)
791 if(!unicast_neighbour
)
793 if(unicast_flush_timeout
.tv_sec
!= 0 &&
794 timeval_minus_msec(&unicast_flush_timeout
, &babel_now
) < msecs
)
796 unicast_flush_timeout
.tv_usec
= (babel_now
.tv_usec
+ msecs
* 1000) %1000000;
797 unicast_flush_timeout
.tv_sec
=
798 babel_now
.tv_sec
+ (babel_now
.tv_usec
/ 1000 + msecs
) / 1000;
802 ensure_space(struct interface
*ifp
, int space
)
804 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
805 if(babel_ifp
->bufsize
- babel_ifp
->buffered
< space
)
810 start_message(struct interface
*ifp
, int type
, int len
)
812 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
813 if(babel_ifp
->bufsize
- babel_ifp
->buffered
< len
+ 2)
815 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = type
;
816 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = len
;
820 end_message(struct interface
*ifp
, int type
, int bytes
)
822 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
823 assert(babel_ifp
->buffered
>= bytes
+ 2 &&
824 babel_ifp
->sendbuf
[babel_ifp
->buffered
- bytes
- 2] == type
&&
825 babel_ifp
->sendbuf
[babel_ifp
->buffered
- bytes
- 1] == bytes
);
830 accumulate_byte(struct interface
*ifp
, unsigned char value
)
832 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
833 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = value
;
837 accumulate_short(struct interface
*ifp
, unsigned short value
)
839 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
840 DO_HTONS(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
);
841 babel_ifp
->buffered
+= 2;
845 accumulate_int(struct interface
*ifp
, unsigned int value
)
847 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
848 DO_HTONL(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
);
849 babel_ifp
->buffered
+= 4;
853 accumulate_bytes(struct interface
*ifp
,
854 const unsigned char *value
, unsigned len
)
856 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
857 memcpy(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
, len
);
858 babel_ifp
->buffered
+= len
;
862 start_unicast_message(struct neighbour
*neigh
, int type
, int len
)
864 if(unicast_neighbour
) {
865 if(neigh
!= unicast_neighbour
||
866 unicast_buffered
+ len
+ 2 >=
867 MIN(UNICAST_BUFSIZE
, babel_get_if_nfo(neigh
->ifp
)->bufsize
))
871 unicast_buffer
= malloc(UNICAST_BUFSIZE
);
872 if(!unicast_buffer
) {
873 flog_err(EC_BABEL_MEMORY
, "malloc(unicast_buffer): %s",
874 safe_strerror(errno
));
878 unicast_neighbour
= neigh
;
880 unicast_buffer
[unicast_buffered
++] = type
;
881 unicast_buffer
[unicast_buffered
++] = len
;
886 end_unicast_message(struct neighbour
*neigh
, int type
, int bytes
)
888 assert(unicast_neighbour
== neigh
&& unicast_buffered
>= bytes
+ 2 &&
889 unicast_buffer
[unicast_buffered
- bytes
- 2] == type
&&
890 unicast_buffer
[unicast_buffered
- bytes
- 1] == bytes
);
891 schedule_unicast_flush(jitter(babel_get_if_nfo(neigh
->ifp
), 0));
895 accumulate_unicast_byte(struct neighbour
*neigh
, unsigned char value
)
897 unicast_buffer
[unicast_buffered
++] = value
;
901 accumulate_unicast_short(struct neighbour
*neigh
, unsigned short value
)
903 DO_HTONS(unicast_buffer
+ unicast_buffered
, value
);
904 unicast_buffered
+= 2;
908 accumulate_unicast_int(struct neighbour
*neigh
, unsigned int value
)
910 DO_HTONL(unicast_buffer
+ unicast_buffered
, value
);
911 unicast_buffered
+= 4;
915 accumulate_unicast_bytes(struct neighbour
*neigh
,
916 const unsigned char *value
, unsigned len
)
918 memcpy(unicast_buffer
+ unicast_buffered
, value
, len
);
919 unicast_buffered
+= len
;
923 send_ack(struct neighbour
*neigh
, unsigned short nonce
, unsigned short interval
)
926 debugf(BABEL_DEBUG_COMMON
,"Sending ack (%04x) to %s on %s.",
927 nonce
, format_address(neigh
->address
), neigh
->ifp
->name
);
928 rc
= start_unicast_message(neigh
, MESSAGE_ACK
, 2); if(rc
< 0) return;
929 accumulate_unicast_short(neigh
, nonce
);
930 end_unicast_message(neigh
, MESSAGE_ACK
, 2);
931 /* Roughly yields a value no larger than 3/2, so this meets the deadline */
932 schedule_unicast_flush(roughly(interval
* 6));
936 send_hello_noupdate(struct interface
*ifp
, unsigned interval
)
938 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
939 /* This avoids sending multiple hellos in a single packet, which breaks
940 link quality estimation. */
941 if(babel_ifp
->buffered_hello
>= 0)
944 babel_ifp
->hello_seqno
= seqno_plus(babel_ifp
->hello_seqno
, 1);
945 set_timeout(&babel_ifp
->hello_timeout
, babel_ifp
->hello_interval
);
950 debugf(BABEL_DEBUG_COMMON
,"Sending hello %d (%d) to %s.",
951 babel_ifp
->hello_seqno
, interval
, ifp
->name
);
953 start_message(ifp
, MESSAGE_HELLO
,
954 (babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) ? 12 : 6);
955 babel_ifp
->buffered_hello
= babel_ifp
->buffered
- 2;
956 accumulate_short(ifp
, 0);
957 accumulate_short(ifp
, babel_ifp
->hello_seqno
);
958 accumulate_short(ifp
, interval
> 0xFFFF ? 0xFFFF : interval
);
959 if(babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) {
960 /* Sub-TLV containing the local time of emission. We use a
961 Pad4 sub-TLV, which we'll fill just before sending. */
962 accumulate_byte(ifp
, SUBTLV_PADN
);
963 accumulate_byte(ifp
, 4);
964 accumulate_int(ifp
, 0);
966 end_message(ifp
, MESSAGE_HELLO
,
967 (babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) ? 12 : 6);
971 send_hello(struct interface
*ifp
)
973 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
974 send_hello_noupdate(ifp
, (babel_ifp
->hello_interval
+ 9) / 10);
975 /* Send full IHU every 3 hellos, and marginal IHU each time */
976 if(babel_ifp
->hello_seqno
% 3 == 0)
979 send_marginal_ihu(ifp
);
983 flush_unicast(int dofree
)
985 struct sockaddr_in6 sin6
;
988 if(unicast_buffered
== 0)
991 if(!if_up(unicast_neighbour
->ifp
))
994 /* Preserve ordering of messages */
995 flushbuf(unicast_neighbour
->ifp
);
997 if(check_bucket(unicast_neighbour
->ifp
)) {
998 memset(&sin6
, 0, sizeof(sin6
));
999 sin6
.sin6_family
= AF_INET6
;
1000 memcpy(&sin6
.sin6_addr
, unicast_neighbour
->address
, 16);
1001 sin6
.sin6_port
= htons(protocol_port
);
1002 sin6
.sin6_scope_id
= unicast_neighbour
->ifp
->ifindex
;
1003 DO_HTONS(packet_header
+ 2, unicast_buffered
);
1004 fill_rtt_message(unicast_neighbour
->ifp
);
1005 rc
= babel_send(protocol_socket
,
1006 packet_header
, sizeof(packet_header
),
1007 unicast_buffer
, unicast_buffered
,
1008 (struct sockaddr
*)&sin6
, sizeof(sin6
));
1010 flog_err(EC_BABEL_PACKET
, "send(unicast): %s",
1011 safe_strerror(errno
));
1013 flog_err(EC_BABEL_PACKET
,
1014 "Warning: bucket full, dropping unicast packet to %s if %s.",
1015 format_address(unicast_neighbour
->address
),
1016 unicast_neighbour
->ifp
->name
);
1020 VALGRIND_MAKE_MEM_UNDEFINED(unicast_buffer
, UNICAST_BUFSIZE
);
1021 unicast_buffered
= 0;
1022 if(dofree
&& unicast_buffer
) {
1023 free(unicast_buffer
);
1024 unicast_buffer
= NULL
;
1026 unicast_neighbour
= NULL
;
1027 unicast_flush_timeout
.tv_sec
= 0;
1028 unicast_flush_timeout
.tv_usec
= 0;
1032 really_send_update(struct interface
*ifp
,
1033 const unsigned char *id
,
1034 const unsigned char *prefix
, unsigned char plen
,
1035 unsigned short seqno
, unsigned short metric
,
1036 unsigned char *channels
, int channels_len
)
1038 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1039 int add_metric
, v4
, real_plen
, omit
= 0;
1040 const unsigned char *real_prefix
;
1041 unsigned short flags
= 0;
1044 if(diversity_kind
!= DIVERSITY_CHANNEL
)
1047 channels_size
= channels_len
>= 0 ? channels_len
+ 2 : 0;
1052 add_metric
= output_filter(id
, prefix
, plen
, ifp
->ifindex
);
1053 if(add_metric
>= INFINITY
)
1056 metric
= MIN(metric
+ add_metric
, INFINITY
);
1058 ensure_space(ifp
, 20 + 12 + 28);
1060 v4
= plen
>= 96 && v4mapped(prefix
);
1063 if(!babel_ifp
->ipv4
)
1065 if(!babel_ifp
->have_buffered_nh
||
1066 memcmp(babel_ifp
->buffered_nh
, babel_ifp
->ipv4
, 4) != 0) {
1067 start_message(ifp
, MESSAGE_NH
, 6);
1068 accumulate_byte(ifp
, 1);
1069 accumulate_byte(ifp
, 0);
1070 accumulate_bytes(ifp
, babel_ifp
->ipv4
, 4);
1071 end_message(ifp
, MESSAGE_NH
, 6);
1072 memcpy(babel_ifp
->buffered_nh
, babel_ifp
->ipv4
, 4);
1073 babel_ifp
->have_buffered_nh
= 1;
1076 real_prefix
= prefix
+ 12;
1077 real_plen
= plen
- 96;
1079 if(babel_ifp
->have_buffered_prefix
) {
1080 while(omit
< plen
/ 8 &&
1081 babel_ifp
->buffered_prefix
[omit
] == prefix
[omit
])
1084 if(!babel_ifp
->have_buffered_prefix
|| plen
>= 48)
1086 real_prefix
= prefix
;
1090 if(!babel_ifp
->have_buffered_id
1091 || memcmp(id
, babel_ifp
->buffered_id
, 8) != 0) {
1092 if(real_plen
== 128 && memcmp(real_prefix
+ 8, id
, 8) == 0) {
1095 start_message(ifp
, MESSAGE_ROUTER_ID
, 10);
1096 accumulate_short(ifp
, 0);
1097 accumulate_bytes(ifp
, id
, 8);
1098 end_message(ifp
, MESSAGE_ROUTER_ID
, 10);
1100 memcpy(babel_ifp
->buffered_id
, id
, sizeof(babel_ifp
->buffered_id
));
1101 babel_ifp
->have_buffered_id
= 1;
1104 start_message(ifp
, MESSAGE_UPDATE
, 10 + (real_plen
+ 7) / 8 - omit
+
1106 accumulate_byte(ifp
, v4
? 1 : 2);
1107 accumulate_byte(ifp
, flags
);
1108 accumulate_byte(ifp
, real_plen
);
1109 accumulate_byte(ifp
, omit
);
1110 accumulate_short(ifp
, (babel_ifp
->update_interval
+ 5) / 10);
1111 accumulate_short(ifp
, seqno
);
1112 accumulate_short(ifp
, metric
);
1113 accumulate_bytes(ifp
, real_prefix
+ omit
, (real_plen
+ 7) / 8 - omit
);
1114 /* Note that an empty channels TLV is different from no such TLV. */
1115 if(channels_len
>= 0) {
1116 accumulate_byte(ifp
, 2);
1117 accumulate_byte(ifp
, channels_len
);
1119 if (channels
&& channels_len
> 0)
1120 accumulate_bytes(ifp
, channels
, channels_len
);
1122 end_message(ifp
, MESSAGE_UPDATE
, 10 + (real_plen
+ 7) / 8 - omit
+
1126 memcpy(babel_ifp
->buffered_prefix
, prefix
, 16);
1127 babel_ifp
->have_buffered_prefix
= 1;
1132 compare_buffered_updates(const void *av
, const void *bv
)
1134 const struct buffered_update
*a
= av
, *b
= bv
;
1135 int rc
, v4a
, v4b
, ma
, mb
;
1137 rc
= memcmp(a
->id
, b
->id
, 8);
1141 v4a
= (a
->plen
>= 96 && v4mapped(a
->prefix
));
1142 v4b
= (b
->plen
>= 96 && v4mapped(b
->prefix
));
1149 ma
= (!v4a
&& a
->plen
== 128 && memcmp(a
->prefix
+ 8, a
->id
, 8) == 0);
1150 mb
= (!v4b
&& b
->plen
== 128 && memcmp(b
->prefix
+ 8, b
->id
, 8) == 0);
1157 if(a
->plen
< b
->plen
)
1159 else if(a
->plen
> b
->plen
)
1162 return memcmp(a
->prefix
, b
->prefix
, 16);
1166 flushupdates(struct interface
*ifp
)
1168 babel_interface_nfo
*babel_ifp
= NULL
;
1169 struct xroute
*xroute
;
1170 struct babel_route
*route
;
1171 const unsigned char *last_prefix
= NULL
;
1172 unsigned char last_plen
= 0xFF;
1176 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1177 struct interface
*ifp_aux
;
1178 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1179 flushupdates(ifp_aux
);
1183 babel_ifp
= babel_get_if_nfo(ifp
);
1184 if(babel_ifp
->num_buffered_updates
> 0) {
1185 struct buffered_update
*b
= babel_ifp
->buffered_updates
;
1186 int n
= babel_ifp
->num_buffered_updates
;
1188 babel_ifp
->buffered_updates
= NULL
;
1189 babel_ifp
->update_bufsize
= 0;
1190 babel_ifp
->num_buffered_updates
= 0;
1195 debugf(BABEL_DEBUG_COMMON
," (flushing %d buffered updates on %s (%d))",
1196 n
, ifp
->name
, ifp
->ifindex
);
1198 /* In order to send fewer update messages, we want to send updates
1199 with the same router-id together, with IPv6 going out before IPv4. */
1201 for(i
= 0; i
< n
; i
++) {
1202 route
= find_installed_route(b
[i
].prefix
, b
[i
].plen
);
1204 memcpy(b
[i
].id
, route
->src
->id
, 8);
1206 memcpy(b
[i
].id
, myid
, 8);
1209 qsort(b
, n
, sizeof(struct buffered_update
), compare_buffered_updates
);
1211 for(i
= 0; i
< n
; i
++) {
1212 /* The same update may be scheduled multiple times before it is
1213 sent out. Since our buffer is now sorted, it is enough to
1214 compare with the previous update. */
1217 if(b
[i
].plen
== last_plen
&&
1218 memcmp(b
[i
].prefix
, last_prefix
, 16) == 0)
1222 xroute
= find_xroute(b
[i
].prefix
, b
[i
].plen
);
1223 route
= find_installed_route(b
[i
].prefix
, b
[i
].plen
);
1225 if(xroute
&& (!route
|| xroute
->metric
<= kernel_metric
)) {
1226 really_send_update(ifp
, myid
,
1227 xroute
->prefix
, xroute
->plen
,
1228 myseqno
, xroute
->metric
,
1230 last_prefix
= xroute
->prefix
;
1231 last_plen
= xroute
->plen
;
1233 unsigned char channels
[DIVERSITY_HOPS
];
1235 struct interface
*route_ifp
= route
->neigh
->ifp
;
1236 struct babel_interface
*babel_route_ifp
= NULL
;
1237 unsigned short metric
;
1238 unsigned short seqno
;
1240 seqno
= route
->seqno
;
1242 route_interferes(route
, ifp
) ?
1243 route_metric(route
) :
1244 route_metric_noninterfering(route
);
1246 if(metric
< INFINITY
)
1247 satisfy_request(route
->src
->prefix
, route
->src
->plen
,
1248 seqno
, route
->src
->id
, ifp
);
1249 if((babel_ifp
->flags
& BABEL_IF_SPLIT_HORIZON
) &&
1250 route
->neigh
->ifp
== ifp
)
1253 babel_route_ifp
= babel_get_if_nfo(route_ifp
);
1254 if(babel_route_ifp
->channel
==BABEL_IF_CHANNEL_NONINTERFERING
) {
1255 memcpy(channels
, route
->channels
, DIVERSITY_HOPS
);
1257 if(babel_route_ifp
->channel
== BABEL_IF_CHANNEL_UNKNOWN
)
1258 channels
[0] = BABEL_IF_CHANNEL_INTERFERING
;
1260 assert(babel_route_ifp
->channel
> 0 &&
1261 babel_route_ifp
->channel
<= 255);
1262 channels
[0] = babel_route_ifp
->channel
;
1264 memcpy(channels
+ 1, route
->channels
, DIVERSITY_HOPS
- 1);
1267 chlen
= channels_len(channels
);
1268 really_send_update(ifp
, route
->src
->id
,
1273 update_source(route
->src
, seqno
, metric
);
1274 last_prefix
= route
->src
->prefix
;
1275 last_plen
= route
->src
->plen
;
1277 /* There's no route for this prefix. This can happen shortly
1278 after an xroute has been retracted, so send a retraction. */
1279 really_send_update(ifp
, myid
, b
[i
].prefix
, b
[i
].plen
,
1280 myseqno
, INFINITY
, NULL
, -1);
1283 schedule_flush_now(ifp
);
1287 babel_ifp
->update_flush_timeout
.tv_sec
= 0;
1288 babel_ifp
->update_flush_timeout
.tv_usec
= 0;
1292 schedule_update_flush(struct interface
*ifp
, int urgent
)
1294 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1296 msecs
= update_jitter(babel_ifp
, urgent
);
1297 if(babel_ifp
->update_flush_timeout
.tv_sec
!= 0 &&
1298 timeval_minus_msec(&babel_ifp
->update_flush_timeout
, &babel_now
) < msecs
)
1300 set_timeout(&babel_ifp
->update_flush_timeout
, msecs
);
1304 buffer_update(struct interface
*ifp
,
1305 const unsigned char *prefix
, unsigned char plen
)
1307 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1308 if(babel_ifp
->num_buffered_updates
> 0 &&
1309 babel_ifp
->num_buffered_updates
>= babel_ifp
->update_bufsize
)
1312 if(babel_ifp
->update_bufsize
== 0) {
1314 assert(babel_ifp
->buffered_updates
== NULL
);
1315 /* Allocate enough space to hold a full update. Since the
1316 number of installed routes will grow over time, make sure we
1317 have enough space to send a full-ish frame. */
1318 n
= installed_routes_estimate() + xroutes_estimate() + 4;
1319 n
= MAX(n
, babel_ifp
->bufsize
/ 16);
1321 babel_ifp
->buffered_updates
= malloc(n
*sizeof(struct buffered_update
));
1322 if(babel_ifp
->buffered_updates
== NULL
) {
1323 flog_err(EC_BABEL_MEMORY
, "malloc(buffered_updates): %s",
1324 safe_strerror(errno
));
1326 /* Try again with a tiny buffer. */
1332 babel_ifp
->update_bufsize
= n
;
1333 babel_ifp
->num_buffered_updates
= 0;
1336 memcpy(babel_ifp
->buffered_updates
[babel_ifp
->num_buffered_updates
].prefix
,
1338 babel_ifp
->buffered_updates
[babel_ifp
->num_buffered_updates
].plen
= plen
;
1339 babel_ifp
->num_buffered_updates
++;
1343 send_update(struct interface
*ifp
, int urgent
,
1344 const unsigned char *prefix
, unsigned char plen
)
1346 babel_interface_nfo
*babel_ifp
= NULL
;
1349 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1350 struct interface
*ifp_aux
;
1351 struct babel_route
*route
;
1352 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1353 send_update(ifp_aux
, urgent
, prefix
, plen
);
1355 /* Since flushupdates only deals with non-wildcard interfaces, we
1356 need to do this now. */
1357 route
= find_installed_route(prefix
, plen
);
1358 if(route
&& route_metric(route
) < INFINITY
)
1359 satisfy_request(prefix
, plen
, route
->src
->seqno
, route
->src
->id
,
1368 babel_ifp
= babel_get_if_nfo(ifp
);
1370 debugf(BABEL_DEBUG_COMMON
,"Sending update to %s for %s.",
1371 ifp
->name
, format_prefix(prefix
, plen
));
1372 buffer_update(ifp
, prefix
, plen
);
1374 struct route_stream
*routes
= NULL
;
1375 send_self_update(ifp
);
1376 debugf(BABEL_DEBUG_COMMON
,"Sending update to %s for any.", ifp
->name
);
1377 routes
= route_stream(1);
1380 struct babel_route
*route
= route_stream_next(routes
);
1383 buffer_update(ifp
, route
->src
->prefix
, route
->src
->plen
);
1385 route_stream_done(routes
);
1387 flog_err(EC_BABEL_MEMORY
, "Couldn't allocate route stream.");
1389 set_timeout(&babel_ifp
->update_timeout
, babel_ifp
->update_interval
);
1390 babel_ifp
->last_update_time
= babel_now
.tv_sec
;
1392 schedule_update_flush(ifp
, urgent
);
1396 send_update_resend(struct interface
*ifp
,
1397 const unsigned char *prefix
, unsigned char plen
)
1399 assert(prefix
!= NULL
);
1401 send_update(ifp
, 1, prefix
, plen
);
1402 record_resend(RESEND_UPDATE
, prefix
, plen
, 0, NULL
, NULL
, resend_delay
);
1406 send_wildcard_retraction(struct interface
*ifp
)
1408 babel_interface_nfo
*babel_ifp
= NULL
;
1410 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1411 struct interface
*ifp_aux
;
1412 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1413 send_wildcard_retraction(ifp_aux
);
1420 babel_ifp
= babel_get_if_nfo(ifp
);
1421 start_message(ifp
, MESSAGE_UPDATE
, 10);
1422 accumulate_byte(ifp
, 0);
1423 accumulate_byte(ifp
, 0x40);
1424 accumulate_byte(ifp
, 0);
1425 accumulate_byte(ifp
, 0);
1426 accumulate_short(ifp
, 0xFFFF);
1427 accumulate_short(ifp
, myseqno
);
1428 accumulate_short(ifp
, 0xFFFF);
1429 end_message(ifp
, MESSAGE_UPDATE
, 10);
1431 babel_ifp
->have_buffered_id
= 0;
1435 update_myseqno(void)
1437 myseqno
= seqno_plus(myseqno
, 1);
1441 send_self_update(struct interface
*ifp
)
1443 struct xroute_stream
*xroutes
;
1445 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1446 struct interface
*ifp_aux
;
1447 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1450 send_self_update(ifp_aux
);
1455 debugf(BABEL_DEBUG_COMMON
,"Sending self update to %s.", ifp
->name
);
1456 xroutes
= xroute_stream();
1459 struct xroute
*xroute
= xroute_stream_next(xroutes
);
1460 if(xroute
== NULL
) break;
1461 send_update(ifp
, 0, xroute
->prefix
, xroute
->plen
);
1463 xroute_stream_done(xroutes
);
1465 flog_err(EC_BABEL_MEMORY
, "Couldn't allocate xroute stream.");
1470 send_ihu(struct neighbour
*neigh
, struct interface
*ifp
)
1472 babel_interface_nfo
*babel_ifp
= NULL
;
1473 int rxcost
, interval
;
1478 if(neigh
== NULL
&& ifp
== NULL
) {
1479 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1480 struct interface
*ifp_aux
;
1481 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1484 send_ihu(NULL
, ifp_aux
);
1490 struct neighbour
*ngh
;
1491 FOR_ALL_NEIGHBOURS(ngh
) {
1499 if(ifp
&& neigh
->ifp
!= ifp
)
1503 babel_ifp
= babel_get_if_nfo(ifp
);
1507 rxcost
= neighbour_rxcost(neigh
);
1508 interval
= (babel_ifp
->hello_interval
* 3 + 9) / 10;
1510 /* Conceptually, an IHU is a unicast message. We usually send them as
1511 multicast, since this allows aggregation into a single packet and
1512 avoids an ARP exchange. If we already have a unicast message queued
1513 for this neighbour, however, we might as well piggyback the IHU. */
1514 debugf(BABEL_DEBUG_COMMON
,"Sending %sihu %d on %s to %s.",
1515 unicast_neighbour
== neigh
? "unicast " : "",
1518 format_address(neigh
->address
));
1520 ll
= linklocal(neigh
->address
);
1522 if((babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) && neigh
->hello_send_us
1523 /* Checks whether the RTT data is not too old to be sent. */
1524 && timeval_minus_msec(&babel_now
,
1525 &neigh
->hello_rtt_receive_time
) < 1000000) {
1528 neigh
->hello_send_us
= 0;
1532 /* The length depends on the format of the address, and then an
1533 optional 10-bytes sub-TLV for timestamps (used to compute a RTT). */
1534 msglen
= (ll
? 14 : 22) + (send_rtt_data
? 10 : 0);
1536 if(unicast_neighbour
!= neigh
) {
1537 start_message(ifp
, MESSAGE_IHU
, msglen
);
1538 accumulate_byte(ifp
, ll
? 3 : 2);
1539 accumulate_byte(ifp
, 0);
1540 accumulate_short(ifp
, rxcost
);
1541 accumulate_short(ifp
, interval
);
1543 accumulate_bytes(ifp
, neigh
->address
+ 8, 8);
1545 accumulate_bytes(ifp
, neigh
->address
, 16);
1546 if (send_rtt_data
) {
1547 accumulate_byte(ifp
, SUBTLV_TIMESTAMP
);
1548 accumulate_byte(ifp
, 8);
1549 accumulate_int(ifp
, neigh
->hello_send_us
);
1550 accumulate_int(ifp
, time_us(neigh
->hello_rtt_receive_time
));
1552 end_message(ifp
, MESSAGE_IHU
, msglen
);
1555 rc
= start_unicast_message(neigh
, MESSAGE_IHU
, msglen
);
1557 accumulate_unicast_byte(neigh
, ll
? 3 : 2);
1558 accumulate_unicast_byte(neigh
, 0);
1559 accumulate_unicast_short(neigh
, rxcost
);
1560 accumulate_unicast_short(neigh
, interval
);
1562 accumulate_unicast_bytes(neigh
, neigh
->address
+ 8, 8);
1564 accumulate_unicast_bytes(neigh
, neigh
->address
, 16);
1565 if (send_rtt_data
) {
1566 accumulate_unicast_byte(neigh
, SUBTLV_TIMESTAMP
);
1567 accumulate_unicast_byte(neigh
, 8);
1568 accumulate_unicast_int(neigh
, neigh
->hello_send_us
);
1569 accumulate_unicast_int(neigh
,
1570 time_us(neigh
->hello_rtt_receive_time
));
1572 end_unicast_message(neigh
, MESSAGE_IHU
, msglen
);
1576 /* Send IHUs to all marginal neighbours */
1578 send_marginal_ihu(struct interface
*ifp
)
1580 struct neighbour
*neigh
;
1581 FOR_ALL_NEIGHBOURS(neigh
) {
1582 if(ifp
&& neigh
->ifp
!= ifp
)
1584 if(neigh
->txcost
>= 384 || (neigh
->reach
& 0xF000) != 0xF000)
1585 send_ihu(neigh
, ifp
);
1590 send_request(struct interface
*ifp
,
1591 const unsigned char *prefix
, unsigned char plen
)
1596 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1597 struct interface
*ifp_aux
;
1598 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1601 send_request(ifp_aux
, prefix
, plen
);
1606 /* make sure any buffered updates go out before this request. */
1612 debugf(BABEL_DEBUG_COMMON
,"sending request to %s for %s.",
1613 ifp
->name
, prefix
? format_prefix(prefix
, plen
) : "any");
1614 v4
= plen
>= 96 && v4mapped(prefix
);
1615 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1616 len
= !prefix
? 2 : 2 + pb
;
1618 start_message(ifp
, MESSAGE_REQUEST
, len
);
1619 accumulate_byte(ifp
, !prefix
? 0 : v4
? 1 : 2);
1620 accumulate_byte(ifp
, !prefix
? 0 : v4
? plen
- 96 : plen
);
1623 accumulate_bytes(ifp
, prefix
+ 12, pb
);
1625 accumulate_bytes(ifp
, prefix
, pb
);
1627 end_message(ifp
, MESSAGE_REQUEST
, len
);
1631 send_unicast_request(struct neighbour
*neigh
,
1632 const unsigned char *prefix
, unsigned char plen
)
1634 int rc
, v4
, pb
, len
;
1636 /* make sure any buffered updates go out before this request. */
1637 flushupdates(neigh
->ifp
);
1639 debugf(BABEL_DEBUG_COMMON
,"sending unicast request to %s for %s.",
1640 format_address(neigh
->address
),
1641 prefix
? format_prefix(prefix
, plen
) : "any");
1642 v4
= plen
>= 96 && v4mapped(prefix
);
1643 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1644 len
= !prefix
? 2 : 2 + pb
;
1646 rc
= start_unicast_message(neigh
, MESSAGE_REQUEST
, len
);
1648 accumulate_unicast_byte(neigh
, !prefix
? 0 : v4
? 1 : 2);
1649 accumulate_unicast_byte(neigh
, !prefix
? 0 : v4
? plen
- 96 : plen
);
1652 accumulate_unicast_bytes(neigh
, prefix
+ 12, pb
);
1654 accumulate_unicast_bytes(neigh
, prefix
, pb
);
1656 end_unicast_message(neigh
, MESSAGE_REQUEST
, len
);
1660 send_multihop_request(struct interface
*ifp
,
1661 const unsigned char *prefix
, unsigned char plen
,
1662 unsigned short seqno
, const unsigned char *id
,
1663 unsigned short hop_count
)
1667 /* Make sure any buffered updates go out before this request. */
1671 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1672 struct interface
*ifp_aux
;
1673 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1676 send_multihop_request(ifp_aux
, prefix
, plen
, seqno
, id
, hop_count
);
1684 debugf(BABEL_DEBUG_COMMON
,"Sending request (%d) on %s for %s.",
1685 hop_count
, ifp
->name
, format_prefix(prefix
, plen
));
1686 v4
= plen
>= 96 && v4mapped(prefix
);
1687 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1690 start_message(ifp
, MESSAGE_MH_REQUEST
, len
);
1691 accumulate_byte(ifp
, v4
? 1 : 2);
1692 accumulate_byte(ifp
, v4
? plen
- 96 : plen
);
1693 accumulate_short(ifp
, seqno
);
1694 accumulate_byte(ifp
, hop_count
);
1695 accumulate_byte(ifp
, 0);
1696 accumulate_bytes(ifp
, id
, 8);
1699 accumulate_bytes(ifp
, prefix
+ 12, pb
);
1701 accumulate_bytes(ifp
, prefix
, pb
);
1703 end_message(ifp
, MESSAGE_MH_REQUEST
, len
);
1707 send_unicast_multihop_request(struct neighbour
*neigh
,
1708 const unsigned char *prefix
, unsigned char plen
,
1709 unsigned short seqno
, const unsigned char *id
,
1710 unsigned short hop_count
)
1712 int rc
, v4
, pb
, len
;
1714 /* Make sure any buffered updates go out before this request. */
1715 flushupdates(neigh
->ifp
);
1717 debugf(BABEL_DEBUG_COMMON
,"Sending multi-hop request to %s for %s (%d hops).",
1718 format_address(neigh
->address
),
1719 format_prefix(prefix
, plen
), hop_count
);
1720 v4
= plen
>= 96 && v4mapped(prefix
);
1721 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1724 rc
= start_unicast_message(neigh
, MESSAGE_MH_REQUEST
, len
);
1726 accumulate_unicast_byte(neigh
, v4
? 1 : 2);
1727 accumulate_unicast_byte(neigh
, v4
? plen
- 96 : plen
);
1728 accumulate_unicast_short(neigh
, seqno
);
1729 accumulate_unicast_byte(neigh
, hop_count
);
1730 accumulate_unicast_byte(neigh
, 0);
1731 accumulate_unicast_bytes(neigh
, id
, 8);
1734 accumulate_unicast_bytes(neigh
, prefix
+ 12, pb
);
1736 accumulate_unicast_bytes(neigh
, prefix
, pb
);
1738 end_unicast_message(neigh
, MESSAGE_MH_REQUEST
, len
);
1742 send_request_resend(struct neighbour
*neigh
,
1743 const unsigned char *prefix
, unsigned char plen
,
1744 unsigned short seqno
, unsigned char *id
)
1747 send_unicast_multihop_request(neigh
, prefix
, plen
, seqno
, id
, 127);
1749 send_multihop_request(NULL
, prefix
, plen
, seqno
, id
, 127);
1751 record_resend(RESEND_REQUEST
, prefix
, plen
, seqno
, id
,
1752 neigh
? neigh
->ifp
: NULL
, resend_delay
);
1756 handle_request(struct neighbour
*neigh
, const unsigned char *prefix
,
1757 unsigned char plen
, unsigned char hop_count
,
1758 unsigned short seqno
, const unsigned char *id
)
1760 struct xroute
*xroute
;
1761 struct babel_route
*route
;
1762 struct neighbour
*successor
= NULL
;
1764 xroute
= find_xroute(prefix
, plen
);
1765 route
= find_installed_route(prefix
, plen
);
1767 if(xroute
&& (!route
|| xroute
->metric
<= kernel_metric
)) {
1768 if(hop_count
> 0 && memcmp(id
, myid
, 8) == 0) {
1769 if(seqno_compare(seqno
, myseqno
) > 0) {
1770 if(seqno_minus(seqno
, myseqno
) > 100) {
1771 /* Hopelessly out-of-date request */
1777 send_update(neigh
->ifp
, 1, prefix
, plen
);
1782 (memcmp(id
, route
->src
->id
, 8) != 0 ||
1783 seqno_compare(seqno
, route
->seqno
) <= 0)) {
1784 send_update(neigh
->ifp
, 1, prefix
, plen
);
1791 if(route
&& memcmp(id
, route
->src
->id
, 8) == 0 &&
1792 seqno_minus(seqno
, route
->seqno
) > 100) {
1793 /* Hopelessly out-of-date */
1797 if(request_redundant(neigh
->ifp
, prefix
, plen
, seqno
, id
))
1800 /* Let's try to forward this request. */
1801 if(route
&& route_metric(route
) < INFINITY
)
1802 successor
= route
->neigh
;
1804 if(!successor
|| successor
== neigh
) {
1805 /* We were about to forward a request to its requestor. Try to
1806 find a different neighbour to forward the request to. */
1807 struct babel_route
*other_route
;
1809 other_route
= find_best_route(prefix
, plen
, 0, neigh
);
1810 if(other_route
&& route_metric(other_route
) < INFINITY
)
1811 successor
= other_route
->neigh
;
1814 if(!successor
|| successor
== neigh
)
1818 send_unicast_multihop_request(successor
, prefix
, plen
, seqno
, id
,
1820 record_resend(RESEND_REQUEST
, prefix
, plen
, seqno
, id
,