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"
39 static unsigned char packet_header
[4] = {42, 2};
41 int split_horizon
= 1;
43 unsigned short myseqno
= 0;
45 #define UNICAST_BUFSIZE 1024
46 static int unicast_buffered
= 0;
47 static unsigned char *unicast_buffer
= NULL
;
48 struct neighbour
*unicast_neighbour
= NULL
;
49 struct timeval unicast_flush_timeout
= {0, 0};
51 /* Minimum TLV _body_ length for TLVs of particular types (0 = no limit). */
52 static const unsigned char tlv_min_length
[MESSAGE_MAX
+ 1] =
56 [ MESSAGE_ACK_REQ
] = 6,
58 [ MESSAGE_HELLO
] = 6,
60 [ MESSAGE_ROUTER_ID
] = 10,
62 [ MESSAGE_UPDATE
] = 10,
63 [ MESSAGE_REQUEST
] = 2,
64 [ MESSAGE_MH_REQUEST
] = 14,
67 /* Parse a network prefix, encoded in the somewhat baroque compressed
68 representation used by Babel. Return the number of bytes parsed. */
70 network_prefix(int ae
, int plen
, unsigned int omitted
,
71 const unsigned char *p
, const unsigned char *dp
,
72 unsigned int len
, unsigned char *p_r
)
75 unsigned char prefix
[16];
88 memset(prefix
, 0, 16);
95 if(omitted
> 4 || pb
> 4 || (pb
> omitted
&& len
< pb
- omitted
))
97 memcpy(prefix
, v4prefix
, 12);
99 if (dp
== NULL
|| !v4mapped(dp
)) return -1;
100 memcpy(prefix
, dp
, 12 + omitted
);
102 if(pb
> omitted
) memcpy(prefix
+ 12 + omitted
, p
, pb
- omitted
);
106 if(omitted
> 16 || (pb
> omitted
&& len
< pb
- omitted
)) return -1;
108 if (dp
== NULL
|| v4mapped(dp
)) return -1;
109 memcpy(prefix
, dp
, omitted
);
111 if(pb
> omitted
) memcpy(prefix
+ omitted
, p
, pb
- omitted
);
115 if(pb
> 8 && len
< pb
- 8) return -1;
118 if(pb
> 8) memcpy(prefix
+ 8, p
, pb
- 8);
125 mask_prefix(p_r
, prefix
, plen
< 0 ? 128 : ae
== 1 ? plen
+ 96 : plen
);
130 parse_update_subtlv(const unsigned char *a
, int alen
,
131 unsigned char *channels
)
133 int type
, len
, i
= 0;
137 if(type
== SUBTLV_PAD1
) {
143 zlog_err("Received truncated attributes.");
148 zlog_err("Received truncated attributes.");
152 if(type
== SUBTLV_PADN
) {
154 } else if(type
== SUBTLV_DIVERSITY
) {
155 if(len
> DIVERSITY_HOPS
) {
156 zlog_err("Received overlong channel information (%d > %d).n",
157 len
, DIVERSITY_HOPS
);
158 len
= DIVERSITY_HOPS
;
160 if(memchr(a
+ i
+ 2, 0, len
) != NULL
) {
162 zlog_err("Channel information contains 0!");
165 memset(channels
, 0, DIVERSITY_HOPS
);
166 memcpy(channels
, a
+ i
+ 2, len
);
168 debugf(BABEL_DEBUG_COMMON
,
169 "Received unknown route attribute %d.", type
);
177 parse_hello_subtlv(const unsigned char *a
, int alen
,
178 unsigned int *hello_send_us
)
180 int type
, len
, i
= 0, ret
= 0;
184 if(type
== SUBTLV_PAD1
) {
190 zlog_err("Received truncated sub-TLV on Hello message.");
195 zlog_err("Received truncated sub-TLV on Hello message.");
199 if(type
== SUBTLV_PADN
) {
201 } else if(type
== SUBTLV_TIMESTAMP
) {
203 DO_NTOHL(*hello_send_us
, a
+ i
+ 2);
206 zlog_err("Received incorrect RTT sub-TLV on Hello message.");
209 debugf(BABEL_DEBUG_COMMON
,
210 "Received unknown Hello sub-TLV type %d.", type
);
219 parse_ihu_subtlv(const unsigned char *a
, int alen
,
220 unsigned int *hello_send_us
,
221 unsigned int *hello_rtt_receive_time
)
223 int type
, len
, i
= 0, ret
= 0;
227 if(type
== SUBTLV_PAD1
) {
233 zlog_err("Received truncated sub-TLV on IHU message.");
238 zlog_err("Received truncated sub-TLV on IHU message.");
242 if(type
== SUBTLV_PADN
) {
244 } else if(type
== SUBTLV_TIMESTAMP
) {
246 DO_NTOHL(*hello_send_us
, a
+ i
+ 2);
247 DO_NTOHL(*hello_rtt_receive_time
, a
+ i
+ 6);
251 zlog_err("Received incorrect RTT sub-TLV on IHU message.");
254 debugf(BABEL_DEBUG_COMMON
,
255 "Received unknown IHU sub-TLV type %d.", type
);
264 network_address(int ae
, const unsigned char *a
, unsigned int len
,
267 return network_prefix(ae
, -1, 0, a
, NULL
, len
, a_r
);
271 channels_len(unsigned char *channels
)
273 unsigned char *p
= memchr(channels
, 0, DIVERSITY_HOPS
);
274 return p
? (p
- channels
) : DIVERSITY_HOPS
;
277 /* Check, that the provided frame consists of a valid Babel packet header
278 followed by a sequence of TLVs. TLVs of known types are also checked to meet
279 minimum length constraints defined for each. Return 0 for no errors. */
281 babel_packet_examin(const unsigned char *packet
, int packetlen
)
283 unsigned i
= 0, bodylen
;
284 const unsigned char *message
;
285 unsigned char type
, len
;
287 if(packetlen
< 4 || packet
[0] != 42 || packet
[1] != 2)
289 DO_NTOHS(bodylen
, packet
+ 2);
291 message
= packet
+ 4 + i
;
293 if(type
== MESSAGE_PAD1
) {
297 if(i
+ 1 > bodylen
) {
298 debugf(BABEL_DEBUG_COMMON
,"Received truncated message.");
302 if(i
+ len
> bodylen
) {
303 debugf(BABEL_DEBUG_COMMON
,"Received truncated message.");
307 if(type
<= MESSAGE_MAX
&& tlv_min_length
[type
] && len
< tlv_min_length
[type
]) {
308 debugf(BABEL_DEBUG_COMMON
,"Undersized %u TLV", type
);
317 parse_packet(const unsigned char *from
, struct interface
*ifp
,
318 const unsigned char *packet
, int packetlen
)
321 const unsigned char *message
;
322 unsigned char type
, len
;
324 struct neighbour
*neigh
;
325 int have_router_id
= 0, have_v4_prefix
= 0, have_v6_prefix
= 0,
326 have_v4_nh
= 0, have_v6_nh
= 0;
327 unsigned char router_id
[8], v4_prefix
[16], v6_prefix
[16],
328 v4_nh
[16], v6_nh
[16];
329 int have_hello_rtt
= 0;
330 /* Content of the RTT sub-TLV on IHU messages. */
331 unsigned int hello_send_us
= 0, hello_rtt_receive_time
= 0;
332 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
334 if(babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) {
335 /* We want to track exactly when we received this packet. */
339 if(!linklocal(from
)) {
340 zlog_err("Received packet from non-local address %s.",
341 format_address(from
));
345 if (babel_packet_examin (packet
, packetlen
)) {
346 zlog_err("Received malformed packet on %s from %s.",
347 ifp
->name
, format_address(from
));
351 neigh
= find_neighbour(from
, ifp
);
353 zlog_err("Couldn't allocate neighbour.");
357 DO_NTOHS(bodylen
, packet
+ 2);
359 if(bodylen
+ 4 > packetlen
) {
360 zlog_err("Received truncated packet (%d + 4 > %d).",
362 bodylen
= packetlen
- 4;
367 message
= packet
+ 4 + i
;
369 if(type
== MESSAGE_PAD1
) {
370 debugf(BABEL_DEBUG_COMMON
,"Received pad1 from %s on %s.",
371 format_address(from
), ifp
->name
);
377 if(type
== MESSAGE_PADN
) {
378 debugf(BABEL_DEBUG_COMMON
,"Received pad%d from %s on %s.",
379 len
, format_address(from
), ifp
->name
);
380 } else if(type
== MESSAGE_ACK_REQ
) {
381 unsigned short nonce
, interval
;
382 DO_NTOHS(nonce
, message
+ 4);
383 DO_NTOHS(interval
, message
+ 6);
384 debugf(BABEL_DEBUG_COMMON
,"Received ack-req (%04X %d) from %s on %s.",
385 nonce
, interval
, format_address(from
), ifp
->name
);
386 send_ack(neigh
, nonce
, interval
);
387 } else if(type
== MESSAGE_ACK
) {
388 debugf(BABEL_DEBUG_COMMON
,"Received ack from %s on %s.",
389 format_address(from
), ifp
->name
);
390 /* Nothing right now */
391 } else if(type
== MESSAGE_HELLO
) {
392 unsigned short seqno
, interval
;
394 unsigned int timestamp
;
395 DO_NTOHS(seqno
, message
+ 4);
396 DO_NTOHS(interval
, message
+ 6);
397 debugf(BABEL_DEBUG_COMMON
,"Received hello %d (%d) from %s on %s.",
399 format_address(from
), ifp
->name
);
400 changed
= update_neighbour(neigh
, seqno
, interval
);
401 update_neighbour_metric(neigh
, changed
);
403 /* Multiply by 3/2 to allow hellos to expire. */
404 schedule_neighbours_check(interval
* 15, 0);
405 /* Sub-TLV handling. */
407 if(parse_hello_subtlv(message
+ 8, len
- 6, ×tamp
) > 0) {
408 neigh
->hello_send_us
= timestamp
;
409 neigh
->hello_rtt_receive_time
= babel_now
;
413 } else if(type
== MESSAGE_IHU
) {
414 unsigned short txcost
, interval
;
415 unsigned char address
[16];
417 DO_NTOHS(txcost
, message
+ 4);
418 DO_NTOHS(interval
, message
+ 6);
419 rc
= network_address(message
[2], message
+ 8, len
- 6, address
);
420 if(rc
< 0) goto fail
;
421 debugf(BABEL_DEBUG_COMMON
,"Received ihu %d (%d) from %s on %s for %s.",
423 format_address(from
), ifp
->name
,
424 format_address(address
));
425 if(message
[2] == 0 || is_interface_ll_address(ifp
, address
)) {
426 int changed
= txcost
!= neigh
->txcost
;
427 neigh
->txcost
= txcost
;
428 neigh
->ihu_time
= babel_now
;
429 neigh
->ihu_interval
= interval
;
430 update_neighbour_metric(neigh
, changed
);
432 /* Multiply by 3/2 to allow neighbours to expire. */
433 schedule_neighbours_check(interval
* 45, 0);
436 parse_ihu_subtlv(message
+ 8 + rc
, len
- 6 - rc
,
437 &hello_send_us
, &hello_rtt_receive_time
);
439 } else if(type
== MESSAGE_ROUTER_ID
) {
440 memcpy(router_id
, message
+ 4, 8);
442 debugf(BABEL_DEBUG_COMMON
,"Received router-id %s from %s on %s.",
443 format_eui64(router_id
), format_address(from
), ifp
->name
);
444 } else if(type
== MESSAGE_NH
) {
445 unsigned char nh
[16];
447 rc
= network_address(message
[2], message
+ 4, len
- 2,
454 debugf(BABEL_DEBUG_COMMON
,"Received nh %s (%d) from %s on %s.",
455 format_address(nh
), message
[2],
456 format_address(from
), ifp
->name
);
457 if(message
[2] == 1) {
458 memcpy(v4_nh
, nh
, 16);
461 memcpy(v6_nh
, nh
, 16);
464 } else if(type
== MESSAGE_UPDATE
) {
465 unsigned char prefix
[16], *nh
;
467 unsigned char channels
[DIVERSITY_HOPS
];
468 unsigned short interval
, seqno
, metric
;
470 DO_NTOHS(interval
, message
+ 6);
471 DO_NTOHS(seqno
, message
+ 8);
472 DO_NTOHS(metric
, message
+ 10);
473 if(message
[5] == 0 ||
474 (message
[2] == 1 ? have_v4_prefix
: have_v6_prefix
))
475 rc
= network_prefix(message
[2], message
[4], message
[5],
477 message
[2] == 1 ? v4_prefix
: v6_prefix
,
482 if(message
[3] & 0x80)
483 have_v4_prefix
= have_v6_prefix
= 0;
486 parsed_len
= 10 + rc
;
488 plen
= message
[4] + (message
[2] == 1 ? 96 : 0);
490 if(message
[3] & 0x80) {
491 if(message
[2] == 1) {
492 memcpy(v4_prefix
, prefix
, 16);
495 memcpy(v6_prefix
, prefix
, 16);
499 if(message
[3] & 0x40) {
500 if(message
[2] == 1) {
501 memset(router_id
, 0, 4);
502 memcpy(router_id
+ 4, prefix
+ 12, 4);
504 memcpy(router_id
, prefix
+ 8, 8);
508 if(!have_router_id
&& message
[2] != 0) {
509 zlog_err("Received prefix with no router id.");
512 debugf(BABEL_DEBUG_COMMON
,"Received update%s%s for %s from %s on %s.",
513 (message
[3] & 0x80) ? "/prefix" : "",
514 (message
[3] & 0x40) ? "/id" : "",
515 format_prefix(prefix
, plen
),
516 format_address(from
), ifp
->name
);
518 if(message
[2] == 0) {
519 if(metric
< 0xFFFF) {
520 zlog_err("Received wildcard update with finite metric.");
523 retract_neighbour_routes(neigh
);
525 } else if(message
[2] == 1) {
529 } else if(have_v6_nh
) {
535 if(message
[2] == 1) {
536 if(!babel_get_if_nfo(ifp
)->ipv4
)
540 if((babel_get_if_nfo(ifp
)->flags
& BABEL_IF_FARAWAY
)) {
543 /* This will be overwritten by parse_update_subtlv below. */
545 /* Assume non-interfering (wired) link. */
548 /* Assume interfering. */
549 channels
[0] = BABEL_IF_CHANNEL_INTERFERING
;
554 parse_update_subtlv(message
+ 2 + parsed_len
,
555 len
- parsed_len
, channels
);
558 update_route(router_id
, prefix
, plen
, seqno
, metric
, interval
,
560 channels
, channels_len(channels
));
561 } else if(type
== MESSAGE_REQUEST
) {
562 unsigned char prefix
[16], plen
;
564 rc
= network_prefix(message
[2], message
[3], 0,
565 message
+ 4, NULL
, len
- 2, prefix
);
566 if(rc
< 0) goto fail
;
567 plen
= message
[3] + (message
[2] == 1 ? 96 : 0);
568 debugf(BABEL_DEBUG_COMMON
,"Received request for %s from %s on %s.",
569 message
[2] == 0 ? "any" : format_prefix(prefix
, plen
),
570 format_address(from
), ifp
->name
);
571 if(message
[2] == 0) {
572 struct babel_interface
*neigh_ifp
=babel_get_if_nfo(neigh
->ifp
);
573 /* If a neighbour is requesting a full route dump from us,
574 we might as well send it an IHU. */
575 send_ihu(neigh
, NULL
);
576 /* Since nodes send wildcard requests on boot, booting
577 a large number of nodes at the same time may cause an
578 update storm. Ignore a wildcard request that happens
579 shortly after we sent a full update. */
580 if(neigh_ifp
->last_update_time
<
581 (time_t)(babel_now
.tv_sec
-
582 MAX(neigh_ifp
->hello_interval
/ 100, 1)))
583 send_update(neigh
->ifp
, 0, NULL
, 0);
585 send_update(neigh
->ifp
, 0, prefix
, plen
);
587 } else if(type
== MESSAGE_MH_REQUEST
) {
588 unsigned char prefix
[16], plen
;
589 unsigned short seqno
;
591 DO_NTOHS(seqno
, message
+ 4);
592 rc
= network_prefix(message
[2], message
[3], 0,
593 message
+ 16, NULL
, len
- 14, prefix
);
594 if(rc
< 0) goto fail
;
595 plen
= message
[3] + (message
[2] == 1 ? 96 : 0);
596 debugf(BABEL_DEBUG_COMMON
,"Received request (%d) for %s from %s on %s (%s, %d).",
598 format_prefix(prefix
, plen
),
599 format_address(from
), ifp
->name
,
600 format_eui64(message
+ 8), seqno
);
601 handle_request(neigh
, prefix
, plen
, message
[6],
604 debugf(BABEL_DEBUG_COMMON
,"Received unknown packet type %d from %s on %s.",
605 type
, format_address(from
), ifp
->name
);
612 zlog_err("Couldn't parse packet (%d, %d) from %s on %s.",
613 message
[0], message
[1], format_address(from
), ifp
->name
);
617 /* We can calculate the RTT to this neighbour. */
618 if(have_hello_rtt
&& hello_send_us
&& hello_rtt_receive_time
) {
619 int remote_waiting_us
, local_waiting_us
;
620 unsigned int rtt
, smoothed_rtt
;
621 unsigned int old_rttcost
;
623 remote_waiting_us
= neigh
->hello_send_us
- hello_rtt_receive_time
;
624 local_waiting_us
= time_us(neigh
->hello_rtt_receive_time
) -
627 /* Sanity checks (validity window of 10 minutes). */
628 if(remote_waiting_us
< 0 || local_waiting_us
< 0 ||
629 remote_waiting_us
> 600000000 || local_waiting_us
> 600000000)
632 rtt
= MAX(0, local_waiting_us
- remote_waiting_us
);
633 debugf(BABEL_DEBUG_COMMON
, "RTT to %s on %s sample result: %d us.\n",
634 format_address(from
), ifp
->name
, rtt
);
636 old_rttcost
= neighbour_rttcost(neigh
);
637 if (valid_rtt(neigh
)) {
638 /* Running exponential average. */
639 smoothed_rtt
= (babel_ifp
->rtt_decay
* rtt
+
640 (256 - babel_ifp
->rtt_decay
) * neigh
->rtt
);
641 /* Rounding (up or down) to get closer to the sample. */
642 neigh
->rtt
= (neigh
->rtt
>= rtt
) ? smoothed_rtt
/ 256 :
643 (smoothed_rtt
+ 255) / 256;
645 /* We prefer to be conservative with new neighbours
647 assert(rtt
<= 0x7FFFFFFF);
650 changed
= (neighbour_rttcost(neigh
) == old_rttcost
? 0 : 1);
651 update_neighbour_metric(neigh
, changed
);
652 neigh
->rtt_time
= babel_now
;
657 /* Under normal circumstances, there are enough moderation mechanisms
658 elsewhere in the protocol to make sure that this last-ditch check
659 should never trigger. But I'm superstitious. */
662 check_bucket(struct interface
*ifp
)
664 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
665 if(babel_ifp
->bucket
<= 0) {
666 int seconds
= babel_now
.tv_sec
- babel_ifp
->bucket_time
;
668 babel_ifp
->bucket
= MIN(BUCKET_TOKENS_MAX
,
669 seconds
* BUCKET_TOKENS_PER_SEC
);
671 /* Reset bucket time unconditionally, in case clock is stepped. */
672 babel_ifp
->bucket_time
= babel_now
.tv_sec
;
675 if(babel_ifp
->bucket
> 0) {
684 fill_rtt_message(struct interface
*ifp
)
686 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
687 if((babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) &&
688 (babel_ifp
->buffered_hello
>= 0)) {
689 if(babel_ifp
->sendbuf
[babel_ifp
->buffered_hello
+ 8] == SUBTLV_PADN
&&
690 babel_ifp
->sendbuf
[babel_ifp
->buffered_hello
+ 9] == 4) {
692 /* Change the type of sub-TLV. */
693 babel_ifp
->sendbuf
[babel_ifp
->buffered_hello
+ 8] =
696 time
= time_us(babel_now
);
697 DO_HTONL(babel_ifp
->sendbuf
+ babel_ifp
->buffered_hello
+ 10, time
);
700 zlog_err("No space left for timestamp sub-TLV "
701 "(this shouldn't happen)");
709 flushbuf(struct interface
*ifp
)
712 struct sockaddr_in6 sin6
;
713 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
715 assert(babel_ifp
->buffered
<= babel_ifp
->bufsize
);
719 if(babel_ifp
->buffered
> 0) {
720 debugf(BABEL_DEBUG_COMMON
," (flushing %d buffered bytes on %s)",
721 babel_ifp
->buffered
, ifp
->name
);
722 if(check_bucket(ifp
)) {
723 memset(&sin6
, 0, sizeof(sin6
));
724 sin6
.sin6_family
= AF_INET6
;
725 memcpy(&sin6
.sin6_addr
, protocol_group
, 16);
726 sin6
.sin6_port
= htons(protocol_port
);
727 sin6
.sin6_scope_id
= ifp
->ifindex
;
728 DO_HTONS(packet_header
+ 2, babel_ifp
->buffered
);
729 fill_rtt_message(ifp
);
730 rc
= babel_send(protocol_socket
,
731 packet_header
, sizeof(packet_header
),
732 babel_ifp
->sendbuf
, babel_ifp
->buffered
,
733 (struct sockaddr
*)&sin6
, sizeof(sin6
));
735 zlog_err("send: %s", safe_strerror(errno
));
737 zlog_err("Warning: bucket full, dropping packet to %s.",
741 VALGRIND_MAKE_MEM_UNDEFINED(babel_ifp
->sendbuf
, babel_ifp
->bufsize
);
742 babel_ifp
->buffered
= 0;
743 babel_ifp
->buffered_hello
= -1;
744 babel_ifp
->have_buffered_id
= 0;
745 babel_ifp
->have_buffered_nh
= 0;
746 babel_ifp
->have_buffered_prefix
= 0;
747 babel_ifp
->flush_timeout
.tv_sec
= 0;
748 babel_ifp
->flush_timeout
.tv_usec
= 0;
752 schedule_flush(struct interface
*ifp
)
754 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
755 unsigned msecs
= jitter(babel_ifp
, 0);
756 if(babel_ifp
->flush_timeout
.tv_sec
!= 0 &&
757 timeval_minus_msec(&babel_ifp
->flush_timeout
, &babel_now
) < msecs
)
759 set_timeout(&babel_ifp
->flush_timeout
, msecs
);
763 schedule_flush_now(struct interface
*ifp
)
765 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
767 unsigned msecs
= roughly(10);
768 if(babel_ifp
->flush_timeout
.tv_sec
!= 0 &&
769 timeval_minus_msec(&babel_ifp
->flush_timeout
, &babel_now
) < msecs
)
771 set_timeout(&babel_ifp
->flush_timeout
, msecs
);
775 schedule_unicast_flush(unsigned msecs
)
777 if(!unicast_neighbour
)
779 if(unicast_flush_timeout
.tv_sec
!= 0 &&
780 timeval_minus_msec(&unicast_flush_timeout
, &babel_now
) < msecs
)
782 unicast_flush_timeout
.tv_usec
= (babel_now
.tv_usec
+ msecs
* 1000) %1000000;
783 unicast_flush_timeout
.tv_sec
=
784 babel_now
.tv_sec
+ (babel_now
.tv_usec
/ 1000 + msecs
) / 1000;
788 ensure_space(struct interface
*ifp
, int space
)
790 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
791 if(babel_ifp
->bufsize
- babel_ifp
->buffered
< space
)
796 start_message(struct interface
*ifp
, int type
, int len
)
798 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
799 if(babel_ifp
->bufsize
- babel_ifp
->buffered
< len
+ 2)
801 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = type
;
802 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = len
;
806 end_message(struct interface
*ifp
, int type
, int bytes
)
808 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
809 assert(babel_ifp
->buffered
>= bytes
+ 2 &&
810 babel_ifp
->sendbuf
[babel_ifp
->buffered
- bytes
- 2] == type
&&
811 babel_ifp
->sendbuf
[babel_ifp
->buffered
- bytes
- 1] == bytes
);
816 accumulate_byte(struct interface
*ifp
, unsigned char value
)
818 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
819 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = value
;
823 accumulate_short(struct interface
*ifp
, unsigned short value
)
825 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
826 DO_HTONS(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
);
827 babel_ifp
->buffered
+= 2;
831 accumulate_int(struct interface
*ifp
, unsigned int value
)
833 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
834 DO_HTONL(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
);
835 babel_ifp
->buffered
+= 4;
839 accumulate_bytes(struct interface
*ifp
,
840 const unsigned char *value
, unsigned len
)
842 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
843 memcpy(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
, len
);
844 babel_ifp
->buffered
+= len
;
848 start_unicast_message(struct neighbour
*neigh
, int type
, int len
)
850 if(unicast_neighbour
) {
851 if(neigh
!= unicast_neighbour
||
852 unicast_buffered
+ len
+ 2 >=
853 MIN(UNICAST_BUFSIZE
, babel_get_if_nfo(neigh
->ifp
)->bufsize
))
857 unicast_buffer
= malloc(UNICAST_BUFSIZE
);
858 if(!unicast_buffer
) {
859 zlog_err("malloc(unicast_buffer): %s", safe_strerror(errno
));
863 unicast_neighbour
= neigh
;
865 unicast_buffer
[unicast_buffered
++] = type
;
866 unicast_buffer
[unicast_buffered
++] = len
;
871 end_unicast_message(struct neighbour
*neigh
, int type
, int bytes
)
873 assert(unicast_neighbour
== neigh
&& unicast_buffered
>= bytes
+ 2 &&
874 unicast_buffer
[unicast_buffered
- bytes
- 2] == type
&&
875 unicast_buffer
[unicast_buffered
- bytes
- 1] == bytes
);
876 schedule_unicast_flush(jitter(babel_get_if_nfo(neigh
->ifp
), 0));
880 accumulate_unicast_byte(struct neighbour
*neigh
, unsigned char value
)
882 unicast_buffer
[unicast_buffered
++] = value
;
886 accumulate_unicast_short(struct neighbour
*neigh
, unsigned short value
)
888 DO_HTONS(unicast_buffer
+ unicast_buffered
, value
);
889 unicast_buffered
+= 2;
893 accumulate_unicast_int(struct neighbour
*neigh
, unsigned int value
)
895 DO_HTONL(unicast_buffer
+ unicast_buffered
, value
);
896 unicast_buffered
+= 4;
900 accumulate_unicast_bytes(struct neighbour
*neigh
,
901 const unsigned char *value
, unsigned len
)
903 memcpy(unicast_buffer
+ unicast_buffered
, value
, len
);
904 unicast_buffered
+= len
;
908 send_ack(struct neighbour
*neigh
, unsigned short nonce
, unsigned short interval
)
911 debugf(BABEL_DEBUG_COMMON
,"Sending ack (%04x) to %s on %s.",
912 nonce
, format_address(neigh
->address
), neigh
->ifp
->name
);
913 rc
= start_unicast_message(neigh
, MESSAGE_ACK
, 2); if(rc
< 0) return;
914 accumulate_unicast_short(neigh
, nonce
);
915 end_unicast_message(neigh
, MESSAGE_ACK
, 2);
916 /* Roughly yields a value no larger than 3/2, so this meets the deadline */
917 schedule_unicast_flush(roughly(interval
* 6));
921 send_hello_noupdate(struct interface
*ifp
, unsigned interval
)
923 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
924 /* This avoids sending multiple hellos in a single packet, which breaks
925 link quality estimation. */
926 if(babel_ifp
->buffered_hello
>= 0)
929 babel_ifp
->hello_seqno
= seqno_plus(babel_ifp
->hello_seqno
, 1);
930 set_timeout(&babel_ifp
->hello_timeout
, babel_ifp
->hello_interval
);
935 debugf(BABEL_DEBUG_COMMON
,"Sending hello %d (%d) to %s.",
936 babel_ifp
->hello_seqno
, interval
, ifp
->name
);
938 start_message(ifp
, MESSAGE_HELLO
,
939 (babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) ? 12 : 6);
940 babel_ifp
->buffered_hello
= babel_ifp
->buffered
- 2;
941 accumulate_short(ifp
, 0);
942 accumulate_short(ifp
, babel_ifp
->hello_seqno
);
943 accumulate_short(ifp
, interval
> 0xFFFF ? 0xFFFF : interval
);
944 if(babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) {
945 /* Sub-TLV containing the local time of emission. We use a
946 Pad4 sub-TLV, which we'll fill just before sending. */
947 accumulate_byte(ifp
, SUBTLV_PADN
);
948 accumulate_byte(ifp
, 4);
949 accumulate_int(ifp
, 0);
951 end_message(ifp
, MESSAGE_HELLO
,
952 (babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) ? 12 : 6);
956 send_hello(struct interface
*ifp
)
958 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
959 send_hello_noupdate(ifp
, (babel_ifp
->hello_interval
+ 9) / 10);
960 /* Send full IHU every 3 hellos, and marginal IHU each time */
961 if(babel_ifp
->hello_seqno
% 3 == 0)
964 send_marginal_ihu(ifp
);
968 flush_unicast(int dofree
)
970 struct sockaddr_in6 sin6
;
973 if(unicast_buffered
== 0)
976 if(!if_up(unicast_neighbour
->ifp
))
979 /* Preserve ordering of messages */
980 flushbuf(unicast_neighbour
->ifp
);
982 if(check_bucket(unicast_neighbour
->ifp
)) {
983 memset(&sin6
, 0, sizeof(sin6
));
984 sin6
.sin6_family
= AF_INET6
;
985 memcpy(&sin6
.sin6_addr
, unicast_neighbour
->address
, 16);
986 sin6
.sin6_port
= htons(protocol_port
);
987 sin6
.sin6_scope_id
= unicast_neighbour
->ifp
->ifindex
;
988 DO_HTONS(packet_header
+ 2, unicast_buffered
);
989 fill_rtt_message(unicast_neighbour
->ifp
);
990 rc
= babel_send(protocol_socket
,
991 packet_header
, sizeof(packet_header
),
992 unicast_buffer
, unicast_buffered
,
993 (struct sockaddr
*)&sin6
, sizeof(sin6
));
995 zlog_err("send(unicast): %s", safe_strerror(errno
));
997 zlog_err("Warning: bucket full, dropping unicast packet to %s if %s.",
998 format_address(unicast_neighbour
->address
),
999 unicast_neighbour
->ifp
->name
);
1003 VALGRIND_MAKE_MEM_UNDEFINED(unicast_buffer
, UNICAST_BUFSIZE
);
1004 unicast_buffered
= 0;
1005 if(dofree
&& unicast_buffer
) {
1006 free(unicast_buffer
);
1007 unicast_buffer
= NULL
;
1009 unicast_neighbour
= NULL
;
1010 unicast_flush_timeout
.tv_sec
= 0;
1011 unicast_flush_timeout
.tv_usec
= 0;
1015 really_send_update(struct interface
*ifp
,
1016 const unsigned char *id
,
1017 const unsigned char *prefix
, unsigned char plen
,
1018 unsigned short seqno
, unsigned short metric
,
1019 unsigned char *channels
, int channels_len
)
1021 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1022 int add_metric
, v4
, real_plen
, omit
= 0;
1023 const unsigned char *real_prefix
;
1024 unsigned short flags
= 0;
1027 if(diversity_kind
!= DIVERSITY_CHANNEL
)
1030 channels_size
= channels_len
>= 0 ? channels_len
+ 2 : 0;
1035 add_metric
= output_filter(id
, prefix
, plen
, ifp
->ifindex
);
1036 if(add_metric
>= INFINITY
)
1039 metric
= MIN(metric
+ add_metric
, INFINITY
);
1041 ensure_space(ifp
, 20 + 12 + 28);
1043 v4
= plen
>= 96 && v4mapped(prefix
);
1046 if(!babel_ifp
->ipv4
)
1048 if(!babel_ifp
->have_buffered_nh
||
1049 memcmp(babel_ifp
->buffered_nh
, babel_ifp
->ipv4
, 4) != 0) {
1050 start_message(ifp
, MESSAGE_NH
, 6);
1051 accumulate_byte(ifp
, 1);
1052 accumulate_byte(ifp
, 0);
1053 accumulate_bytes(ifp
, babel_ifp
->ipv4
, 4);
1054 end_message(ifp
, MESSAGE_NH
, 6);
1055 memcpy(babel_ifp
->buffered_nh
, babel_ifp
->ipv4
, 4);
1056 babel_ifp
->have_buffered_nh
= 1;
1059 real_prefix
= prefix
+ 12;
1060 real_plen
= plen
- 96;
1062 if(babel_ifp
->have_buffered_prefix
) {
1063 while(omit
< plen
/ 8 &&
1064 babel_ifp
->buffered_prefix
[omit
] == prefix
[omit
])
1067 if(!babel_ifp
->have_buffered_prefix
|| plen
>= 48)
1069 real_prefix
= prefix
;
1073 if(!babel_ifp
->have_buffered_id
1074 || memcmp(id
, babel_ifp
->buffered_id
, 8) != 0) {
1075 if(real_plen
== 128 && memcmp(real_prefix
+ 8, id
, 8) == 0) {
1078 start_message(ifp
, MESSAGE_ROUTER_ID
, 10);
1079 accumulate_short(ifp
, 0);
1080 accumulate_bytes(ifp
, id
, 8);
1081 end_message(ifp
, MESSAGE_ROUTER_ID
, 10);
1083 memcpy(babel_ifp
->buffered_id
, id
, 16);
1084 babel_ifp
->have_buffered_id
= 1;
1087 start_message(ifp
, MESSAGE_UPDATE
, 10 + (real_plen
+ 7) / 8 - omit
+
1089 accumulate_byte(ifp
, v4
? 1 : 2);
1090 accumulate_byte(ifp
, flags
);
1091 accumulate_byte(ifp
, real_plen
);
1092 accumulate_byte(ifp
, omit
);
1093 accumulate_short(ifp
, (babel_ifp
->update_interval
+ 5) / 10);
1094 accumulate_short(ifp
, seqno
);
1095 accumulate_short(ifp
, metric
);
1096 accumulate_bytes(ifp
, real_prefix
+ omit
, (real_plen
+ 7) / 8 - omit
);
1097 /* Note that an empty channels TLV is different from no such TLV. */
1098 if(channels_len
>= 0) {
1099 accumulate_byte(ifp
, 2);
1100 accumulate_byte(ifp
, channels_len
);
1101 accumulate_bytes(ifp
, channels
, channels_len
);
1103 end_message(ifp
, MESSAGE_UPDATE
, 10 + (real_plen
+ 7) / 8 - omit
+
1107 memcpy(babel_ifp
->buffered_prefix
, prefix
, 16);
1108 babel_ifp
->have_buffered_prefix
= 1;
1113 compare_buffered_updates(const void *av
, const void *bv
)
1115 const struct buffered_update
*a
= av
, *b
= bv
;
1116 int rc
, v4a
, v4b
, ma
, mb
;
1118 rc
= memcmp(a
->id
, b
->id
, 8);
1122 v4a
= (a
->plen
>= 96 && v4mapped(a
->prefix
));
1123 v4b
= (b
->plen
>= 96 && v4mapped(b
->prefix
));
1130 ma
= (!v4a
&& a
->plen
== 128 && memcmp(a
->prefix
+ 8, a
->id
, 8) == 0);
1131 mb
= (!v4b
&& b
->plen
== 128 && memcmp(b
->prefix
+ 8, b
->id
, 8) == 0);
1138 if(a
->plen
< b
->plen
)
1140 else if(a
->plen
> b
->plen
)
1143 return memcmp(a
->prefix
, b
->prefix
, 16);
1147 flushupdates(struct interface
*ifp
)
1149 babel_interface_nfo
*babel_ifp
= NULL
;
1150 struct xroute
*xroute
;
1151 struct babel_route
*route
;
1152 const unsigned char *last_prefix
= NULL
;
1153 unsigned char last_plen
= 0xFF;
1157 struct interface
*ifp_aux
;
1158 struct listnode
*linklist_node
= NULL
;
1159 FOR_ALL_INTERFACES(ifp_aux
, linklist_node
)
1160 flushupdates(ifp_aux
);
1164 babel_ifp
= babel_get_if_nfo(ifp
);
1165 if(babel_ifp
->num_buffered_updates
> 0) {
1166 struct buffered_update
*b
= babel_ifp
->buffered_updates
;
1167 int n
= babel_ifp
->num_buffered_updates
;
1169 babel_ifp
->buffered_updates
= NULL
;
1170 babel_ifp
->update_bufsize
= 0;
1171 babel_ifp
->num_buffered_updates
= 0;
1176 debugf(BABEL_DEBUG_COMMON
," (flushing %d buffered updates on %s (%d))",
1177 n
, ifp
->name
, ifp
->ifindex
);
1179 /* In order to send fewer update messages, we want to send updates
1180 with the same router-id together, with IPv6 going out before IPv4. */
1182 for(i
= 0; i
< n
; i
++) {
1183 route
= find_installed_route(b
[i
].prefix
, b
[i
].plen
);
1185 memcpy(b
[i
].id
, route
->src
->id
, 8);
1187 memcpy(b
[i
].id
, myid
, 8);
1190 qsort(b
, n
, sizeof(struct buffered_update
), compare_buffered_updates
);
1192 for(i
= 0; i
< n
; i
++) {
1193 /* The same update may be scheduled multiple times before it is
1194 sent out. Since our buffer is now sorted, it is enough to
1195 compare with the previous update. */
1198 if(b
[i
].plen
== last_plen
&&
1199 memcmp(b
[i
].prefix
, last_prefix
, 16) == 0)
1203 xroute
= find_xroute(b
[i
].prefix
, b
[i
].plen
);
1204 route
= find_installed_route(b
[i
].prefix
, b
[i
].plen
);
1206 if(xroute
&& (!route
|| xroute
->metric
<= kernel_metric
)) {
1207 really_send_update(ifp
, myid
,
1208 xroute
->prefix
, xroute
->plen
,
1209 myseqno
, xroute
->metric
,
1211 last_prefix
= xroute
->prefix
;
1212 last_plen
= xroute
->plen
;
1214 unsigned char channels
[DIVERSITY_HOPS
];
1216 struct interface
*route_ifp
= route
->neigh
->ifp
;
1217 struct babel_interface
*babel_route_ifp
= NULL
;
1218 unsigned short metric
;
1219 unsigned short seqno
;
1221 seqno
= route
->seqno
;
1223 route_interferes(route
, ifp
) ?
1224 route_metric(route
) :
1225 route_metric_noninterfering(route
);
1227 if(metric
< INFINITY
)
1228 satisfy_request(route
->src
->prefix
, route
->src
->plen
,
1229 seqno
, route
->src
->id
, ifp
);
1230 if((babel_ifp
->flags
& BABEL_IF_SPLIT_HORIZON
) &&
1231 route
->neigh
->ifp
== ifp
)
1234 babel_route_ifp
= babel_get_if_nfo(route_ifp
);
1235 if(babel_route_ifp
->channel
==BABEL_IF_CHANNEL_NONINTERFERING
) {
1236 memcpy(channels
, route
->channels
, DIVERSITY_HOPS
);
1238 if(babel_route_ifp
->channel
== BABEL_IF_CHANNEL_UNKNOWN
)
1239 channels
[0] = BABEL_IF_CHANNEL_INTERFERING
;
1241 assert(babel_route_ifp
->channel
> 0 &&
1242 babel_route_ifp
->channel
<= 255);
1243 channels
[0] = babel_route_ifp
->channel
;
1245 memcpy(channels
+ 1, route
->channels
, DIVERSITY_HOPS
- 1);
1248 chlen
= channels_len(channels
);
1249 really_send_update(ifp
, route
->src
->id
,
1254 update_source(route
->src
, seqno
, metric
);
1255 last_prefix
= route
->src
->prefix
;
1256 last_plen
= route
->src
->plen
;
1258 /* There's no route for this prefix. This can happen shortly
1259 after an xroute has been retracted, so send a retraction. */
1260 really_send_update(ifp
, myid
, b
[i
].prefix
, b
[i
].plen
,
1261 myseqno
, INFINITY
, NULL
, -1);
1264 schedule_flush_now(ifp
);
1268 babel_ifp
->update_flush_timeout
.tv_sec
= 0;
1269 babel_ifp
->update_flush_timeout
.tv_usec
= 0;
1273 schedule_update_flush(struct interface
*ifp
, int urgent
)
1275 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1277 msecs
= update_jitter(babel_ifp
, urgent
);
1278 if(babel_ifp
->update_flush_timeout
.tv_sec
!= 0 &&
1279 timeval_minus_msec(&babel_ifp
->update_flush_timeout
, &babel_now
) < msecs
)
1281 set_timeout(&babel_ifp
->update_flush_timeout
, msecs
);
1285 buffer_update(struct interface
*ifp
,
1286 const unsigned char *prefix
, unsigned char plen
)
1288 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1289 if(babel_ifp
->num_buffered_updates
> 0 &&
1290 babel_ifp
->num_buffered_updates
>= babel_ifp
->update_bufsize
)
1293 if(babel_ifp
->update_bufsize
== 0) {
1295 assert(babel_ifp
->buffered_updates
== NULL
);
1296 /* Allocate enough space to hold a full update. Since the
1297 number of installed routes will grow over time, make sure we
1298 have enough space to send a full-ish frame. */
1299 n
= installed_routes_estimate() + xroutes_estimate() + 4;
1300 n
= MAX(n
, babel_ifp
->bufsize
/ 16);
1302 babel_ifp
->buffered_updates
= malloc(n
*sizeof(struct buffered_update
));
1303 if(babel_ifp
->buffered_updates
== NULL
) {
1304 zlog_err("malloc(buffered_updates): %s", safe_strerror(errno
));
1306 /* Try again with a tiny buffer. */
1312 babel_ifp
->update_bufsize
= n
;
1313 babel_ifp
->num_buffered_updates
= 0;
1316 memcpy(babel_ifp
->buffered_updates
[babel_ifp
->num_buffered_updates
].prefix
,
1318 babel_ifp
->buffered_updates
[babel_ifp
->num_buffered_updates
].plen
= plen
;
1319 babel_ifp
->num_buffered_updates
++;
1323 send_update(struct interface
*ifp
, int urgent
,
1324 const unsigned char *prefix
, unsigned char plen
)
1326 babel_interface_nfo
*babel_ifp
= NULL
;
1329 struct interface
*ifp_aux
;
1330 struct listnode
*linklist_node
= NULL
;
1331 struct babel_route
*route
;
1332 FOR_ALL_INTERFACES(ifp_aux
, linklist_node
)
1333 send_update(ifp_aux
, urgent
, prefix
, plen
);
1335 /* Since flushupdates only deals with non-wildcard interfaces, we
1336 need to do this now. */
1337 route
= find_installed_route(prefix
, plen
);
1338 if(route
&& route_metric(route
) < INFINITY
)
1339 satisfy_request(prefix
, plen
, route
->src
->seqno
, route
->src
->id
,
1348 babel_ifp
= babel_get_if_nfo(ifp
);
1350 debugf(BABEL_DEBUG_COMMON
,"Sending update to %s for %s.",
1351 ifp
->name
, format_prefix(prefix
, plen
));
1352 buffer_update(ifp
, prefix
, plen
);
1354 struct route_stream
*routes
= NULL
;
1355 send_self_update(ifp
);
1356 debugf(BABEL_DEBUG_COMMON
,"Sending update to %s for any.", ifp
->name
);
1357 routes
= route_stream(1);
1360 struct babel_route
*route
= route_stream_next(routes
);
1363 buffer_update(ifp
, route
->src
->prefix
, route
->src
->plen
);
1365 route_stream_done(routes
);
1367 zlog_err("Couldn't allocate route stream.");
1369 set_timeout(&babel_ifp
->update_timeout
, babel_ifp
->update_interval
);
1370 babel_ifp
->last_update_time
= babel_now
.tv_sec
;
1372 schedule_update_flush(ifp
, urgent
);
1376 send_update_resend(struct interface
*ifp
,
1377 const unsigned char *prefix
, unsigned char plen
)
1379 assert(prefix
!= NULL
);
1381 send_update(ifp
, 1, prefix
, plen
);
1382 record_resend(RESEND_UPDATE
, prefix
, plen
, 0, NULL
, NULL
, resend_delay
);
1386 send_wildcard_retraction(struct interface
*ifp
)
1388 babel_interface_nfo
*babel_ifp
= NULL
;
1390 struct interface
*ifp_aux
;
1391 struct listnode
*linklist_node
= NULL
;
1392 FOR_ALL_INTERFACES(ifp_aux
, linklist_node
)
1393 send_wildcard_retraction(ifp_aux
);
1400 babel_ifp
= babel_get_if_nfo(ifp
);
1401 start_message(ifp
, MESSAGE_UPDATE
, 10);
1402 accumulate_byte(ifp
, 0);
1403 accumulate_byte(ifp
, 0x40);
1404 accumulate_byte(ifp
, 0);
1405 accumulate_byte(ifp
, 0);
1406 accumulate_short(ifp
, 0xFFFF);
1407 accumulate_short(ifp
, myseqno
);
1408 accumulate_short(ifp
, 0xFFFF);
1409 end_message(ifp
, MESSAGE_UPDATE
, 10);
1411 babel_ifp
->have_buffered_id
= 0;
1417 myseqno
= seqno_plus(myseqno
, 1);
1421 send_self_update(struct interface
*ifp
)
1423 struct xroute_stream
*xroutes
;
1425 struct interface
*ifp_aux
;
1426 struct listnode
*linklist_node
= NULL
;
1427 FOR_ALL_INTERFACES(ifp_aux
, linklist_node
) {
1430 send_self_update(ifp_aux
);
1435 debugf(BABEL_DEBUG_COMMON
,"Sending self update to %s.", ifp
->name
);
1436 xroutes
= xroute_stream();
1439 struct xroute
*xroute
= xroute_stream_next(xroutes
);
1440 if(xroute
== NULL
) break;
1441 send_update(ifp
, 0, xroute
->prefix
, xroute
->plen
);
1443 xroute_stream_done(xroutes
);
1445 zlog_err("Couldn't allocate xroute stream.");
1450 send_ihu(struct neighbour
*neigh
, struct interface
*ifp
)
1452 babel_interface_nfo
*babel_ifp
= NULL
;
1453 int rxcost
, interval
;
1458 if(neigh
== NULL
&& ifp
== NULL
) {
1459 struct interface
*ifp_aux
;
1460 struct listnode
*linklist_node
= NULL
;
1461 FOR_ALL_INTERFACES(ifp_aux
, linklist_node
) {
1464 send_ihu(NULL
, ifp_aux
);
1470 struct neighbour
*ngh
;
1471 FOR_ALL_NEIGHBOURS(ngh
) {
1479 if(ifp
&& neigh
->ifp
!= ifp
)
1483 babel_ifp
= babel_get_if_nfo(ifp
);
1487 rxcost
= neighbour_rxcost(neigh
);
1488 interval
= (babel_ifp
->hello_interval
* 3 + 9) / 10;
1490 /* Conceptually, an IHU is a unicast message. We usually send them as
1491 multicast, since this allows aggregation into a single packet and
1492 avoids an ARP exchange. If we already have a unicast message queued
1493 for this neighbour, however, we might as well piggyback the IHU. */
1494 debugf(BABEL_DEBUG_COMMON
,"Sending %sihu %d on %s to %s.",
1495 unicast_neighbour
== neigh
? "unicast " : "",
1498 format_address(neigh
->address
));
1500 ll
= linklocal(neigh
->address
);
1502 if((babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) && neigh
->hello_send_us
1503 /* Checks whether the RTT data is not too old to be sent. */
1504 && timeval_minus_msec(&babel_now
,
1505 &neigh
->hello_rtt_receive_time
) < 1000000) {
1508 neigh
->hello_send_us
= 0;
1512 /* The length depends on the format of the address, and then an
1513 optional 10-bytes sub-TLV for timestamps (used to compute a RTT). */
1514 msglen
= (ll
? 14 : 22) + (send_rtt_data
? 10 : 0);
1516 if(unicast_neighbour
!= neigh
) {
1517 start_message(ifp
, MESSAGE_IHU
, msglen
);
1518 accumulate_byte(ifp
, ll
? 3 : 2);
1519 accumulate_byte(ifp
, 0);
1520 accumulate_short(ifp
, rxcost
);
1521 accumulate_short(ifp
, interval
);
1523 accumulate_bytes(ifp
, neigh
->address
+ 8, 8);
1525 accumulate_bytes(ifp
, neigh
->address
, 16);
1526 if (send_rtt_data
) {
1527 accumulate_byte(ifp
, SUBTLV_TIMESTAMP
);
1528 accumulate_byte(ifp
, 8);
1529 accumulate_int(ifp
, neigh
->hello_send_us
);
1530 accumulate_int(ifp
, time_us(neigh
->hello_rtt_receive_time
));
1532 end_message(ifp
, MESSAGE_IHU
, msglen
);
1535 rc
= start_unicast_message(neigh
, MESSAGE_IHU
, msglen
);
1537 accumulate_unicast_byte(neigh
, ll
? 3 : 2);
1538 accumulate_unicast_byte(neigh
, 0);
1539 accumulate_unicast_short(neigh
, rxcost
);
1540 accumulate_unicast_short(neigh
, interval
);
1542 accumulate_unicast_bytes(neigh
, neigh
->address
+ 8, 8);
1544 accumulate_unicast_bytes(neigh
, neigh
->address
, 16);
1545 if (send_rtt_data
) {
1546 accumulate_unicast_byte(neigh
, SUBTLV_TIMESTAMP
);
1547 accumulate_unicast_byte(neigh
, 8);
1548 accumulate_unicast_int(neigh
, neigh
->hello_send_us
);
1549 accumulate_unicast_int(neigh
,
1550 time_us(neigh
->hello_rtt_receive_time
));
1552 end_unicast_message(neigh
, MESSAGE_IHU
, msglen
);
1556 /* Send IHUs to all marginal neighbours */
1558 send_marginal_ihu(struct interface
*ifp
)
1560 struct neighbour
*neigh
;
1561 FOR_ALL_NEIGHBOURS(neigh
) {
1562 if(ifp
&& neigh
->ifp
!= ifp
)
1564 if(neigh
->txcost
>= 384 || (neigh
->reach
& 0xF000) != 0xF000)
1565 send_ihu(neigh
, ifp
);
1570 send_request(struct interface
*ifp
,
1571 const unsigned char *prefix
, unsigned char plen
)
1576 struct interface
*ifp_aux
;
1577 struct listnode
*linklist_node
= NULL
;
1578 FOR_ALL_INTERFACES(ifp_aux
, linklist_node
) {
1581 send_request(ifp_aux
, prefix
, plen
);
1586 /* make sure any buffered updates go out before this request. */
1592 debugf(BABEL_DEBUG_COMMON
,"sending request to %s for %s.",
1593 ifp
->name
, prefix
? format_prefix(prefix
, plen
) : "any");
1594 v4
= plen
>= 96 && v4mapped(prefix
);
1595 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1596 len
= !prefix
? 2 : 2 + pb
;
1598 start_message(ifp
, MESSAGE_REQUEST
, len
);
1599 accumulate_byte(ifp
, !prefix
? 0 : v4
? 1 : 2);
1600 accumulate_byte(ifp
, !prefix
? 0 : v4
? plen
- 96 : plen
);
1603 accumulate_bytes(ifp
, prefix
+ 12, pb
);
1605 accumulate_bytes(ifp
, prefix
, pb
);
1607 end_message(ifp
, MESSAGE_REQUEST
, len
);
1611 send_unicast_request(struct neighbour
*neigh
,
1612 const unsigned char *prefix
, unsigned char plen
)
1614 int rc
, v4
, pb
, len
;
1616 /* make sure any buffered updates go out before this request. */
1617 flushupdates(neigh
->ifp
);
1619 debugf(BABEL_DEBUG_COMMON
,"sending unicast request to %s for %s.",
1620 format_address(neigh
->address
),
1621 prefix
? format_prefix(prefix
, plen
) : "any");
1622 v4
= plen
>= 96 && v4mapped(prefix
);
1623 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1624 len
= !prefix
? 2 : 2 + pb
;
1626 rc
= start_unicast_message(neigh
, MESSAGE_REQUEST
, len
);
1628 accumulate_unicast_byte(neigh
, !prefix
? 0 : v4
? 1 : 2);
1629 accumulate_unicast_byte(neigh
, !prefix
? 0 : v4
? plen
- 96 : plen
);
1632 accumulate_unicast_bytes(neigh
, prefix
+ 12, pb
);
1634 accumulate_unicast_bytes(neigh
, prefix
, pb
);
1636 end_unicast_message(neigh
, MESSAGE_REQUEST
, len
);
1640 send_multihop_request(struct interface
*ifp
,
1641 const unsigned char *prefix
, unsigned char plen
,
1642 unsigned short seqno
, const unsigned char *id
,
1643 unsigned short hop_count
)
1647 /* Make sure any buffered updates go out before this request. */
1651 struct interface
*ifp_aux
;
1652 struct listnode
*linklist_node
= NULL
;
1653 FOR_ALL_INTERFACES(ifp_aux
, linklist_node
) {
1656 send_multihop_request(ifp_aux
, prefix
, plen
, seqno
, id
, hop_count
);
1664 debugf(BABEL_DEBUG_COMMON
,"Sending request (%d) on %s for %s.",
1665 hop_count
, ifp
->name
, format_prefix(prefix
, plen
));
1666 v4
= plen
>= 96 && v4mapped(prefix
);
1667 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1670 start_message(ifp
, MESSAGE_MH_REQUEST
, len
);
1671 accumulate_byte(ifp
, v4
? 1 : 2);
1672 accumulate_byte(ifp
, v4
? plen
- 96 : plen
);
1673 accumulate_short(ifp
, seqno
);
1674 accumulate_byte(ifp
, hop_count
);
1675 accumulate_byte(ifp
, 0);
1676 accumulate_bytes(ifp
, id
, 8);
1679 accumulate_bytes(ifp
, prefix
+ 12, pb
);
1681 accumulate_bytes(ifp
, prefix
, pb
);
1683 end_message(ifp
, MESSAGE_MH_REQUEST
, len
);
1687 send_unicast_multihop_request(struct neighbour
*neigh
,
1688 const unsigned char *prefix
, unsigned char plen
,
1689 unsigned short seqno
, const unsigned char *id
,
1690 unsigned short hop_count
)
1692 int rc
, v4
, pb
, len
;
1694 /* Make sure any buffered updates go out before this request. */
1695 flushupdates(neigh
->ifp
);
1697 debugf(BABEL_DEBUG_COMMON
,"Sending multi-hop request to %s for %s (%d hops).",
1698 format_address(neigh
->address
),
1699 format_prefix(prefix
, plen
), hop_count
);
1700 v4
= plen
>= 96 && v4mapped(prefix
);
1701 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1704 rc
= start_unicast_message(neigh
, MESSAGE_MH_REQUEST
, len
);
1706 accumulate_unicast_byte(neigh
, v4
? 1 : 2);
1707 accumulate_unicast_byte(neigh
, v4
? plen
- 96 : plen
);
1708 accumulate_unicast_short(neigh
, seqno
);
1709 accumulate_unicast_byte(neigh
, hop_count
);
1710 accumulate_unicast_byte(neigh
, 0);
1711 accumulate_unicast_bytes(neigh
, id
, 8);
1714 accumulate_unicast_bytes(neigh
, prefix
+ 12, pb
);
1716 accumulate_unicast_bytes(neigh
, prefix
, pb
);
1718 end_unicast_message(neigh
, MESSAGE_MH_REQUEST
, len
);
1722 send_request_resend(struct neighbour
*neigh
,
1723 const unsigned char *prefix
, unsigned char plen
,
1724 unsigned short seqno
, unsigned char *id
)
1727 send_unicast_multihop_request(neigh
, prefix
, plen
, seqno
, id
, 127);
1729 send_multihop_request(NULL
, prefix
, plen
, seqno
, id
, 127);
1731 record_resend(RESEND_REQUEST
, prefix
, plen
, seqno
, id
,
1732 neigh
? neigh
->ifp
: NULL
, resend_delay
);
1736 handle_request(struct neighbour
*neigh
, const unsigned char *prefix
,
1737 unsigned char plen
, unsigned char hop_count
,
1738 unsigned short seqno
, const unsigned char *id
)
1740 struct xroute
*xroute
;
1741 struct babel_route
*route
;
1742 struct neighbour
*successor
= NULL
;
1744 xroute
= find_xroute(prefix
, plen
);
1745 route
= find_installed_route(prefix
, plen
);
1747 if(xroute
&& (!route
|| xroute
->metric
<= kernel_metric
)) {
1748 if(hop_count
> 0 && memcmp(id
, myid
, 8) == 0) {
1749 if(seqno_compare(seqno
, myseqno
) > 0) {
1750 if(seqno_minus(seqno
, myseqno
) > 100) {
1751 /* Hopelessly out-of-date request */
1757 send_update(neigh
->ifp
, 1, prefix
, plen
);
1762 (memcmp(id
, route
->src
->id
, 8) != 0 ||
1763 seqno_compare(seqno
, route
->seqno
) <= 0)) {
1764 send_update(neigh
->ifp
, 1, prefix
, plen
);
1771 if(route
&& memcmp(id
, route
->src
->id
, 8) == 0 &&
1772 seqno_minus(seqno
, route
->seqno
) > 100) {
1773 /* Hopelessly out-of-date */
1777 if(request_redundant(neigh
->ifp
, prefix
, plen
, seqno
, id
))
1780 /* Let's try to forward this request. */
1781 if(route
&& route_metric(route
) < INFINITY
)
1782 successor
= route
->neigh
;
1784 if(!successor
|| successor
== neigh
) {
1785 /* We were about to forward a request to its requestor. Try to
1786 find a different neighbour to forward the request to. */
1787 struct babel_route
*other_route
;
1789 other_route
= find_best_route(prefix
, plen
, 0, neigh
);
1790 if(other_route
&& route_metric(other_route
) < INFINITY
)
1791 successor
= other_route
->neigh
;
1794 if(!successor
|| successor
== neigh
)
1798 send_unicast_multihop_request(successor
, prefix
, plen
, seqno
, id
,
1800 record_resend(RESEND_REQUEST
, prefix
, plen
, seqno
, id
,