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.");
148 if(i
+ len
+ 2 > alen
) {
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.");
197 if(i
+ len
+ 2 > alen
) {
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.");
243 if(i
+ len
+ 2 > alen
) {
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
)
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);
298 if(bodylen
+ 4 > packetlen
) {
299 debugf(BABEL_DEBUG_COMMON
, "Received truncated packet (%d + 4 > %d).",
304 message
= packet
+ 4 + i
;
306 if(type
== MESSAGE_PAD1
) {
310 if(i
+ 2 > bodylen
) {
311 debugf(BABEL_DEBUG_COMMON
,"Received truncated message.");
315 if(i
+ len
+ 2 > bodylen
) {
316 debugf(BABEL_DEBUG_COMMON
,"Received truncated message.");
320 if(type
<= MESSAGE_MAX
&& tlv_min_length
[type
] && len
< tlv_min_length
[type
]) {
321 debugf(BABEL_DEBUG_COMMON
,"Undersized %u TLV", type
);
330 parse_packet(const unsigned char *from
, struct interface
*ifp
,
331 const unsigned char *packet
, int packetlen
)
334 const unsigned char *message
;
335 unsigned char type
, len
;
337 struct neighbour
*neigh
;
338 int have_router_id
= 0, have_v4_prefix
= 0, have_v6_prefix
= 0,
339 have_v4_nh
= 0, have_v6_nh
= 0;
340 unsigned char router_id
[8], v4_prefix
[16], v6_prefix
[16],
341 v4_nh
[16], v6_nh
[16];
342 int have_hello_rtt
= 0;
343 /* Content of the RTT sub-TLV on IHU messages. */
344 unsigned int hello_send_us
= 0, hello_rtt_receive_time
= 0;
345 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
347 if(babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) {
348 /* We want to track exactly when we received this packet. */
352 if(!linklocal(from
)) {
353 flog_err(EC_BABEL_PACKET
,
354 "Received packet from non-local address %s.",
355 format_address(from
));
359 if (babel_packet_examin (packet
, packetlen
)) {
360 flog_err(EC_BABEL_PACKET
,
361 "Received malformed packet on %s from %s.",
362 ifp
->name
, format_address(from
));
366 neigh
= find_neighbour(from
, ifp
);
368 flog_err(EC_BABEL_PACKET
, "Couldn't allocate neighbour.");
372 DO_NTOHS(bodylen
, packet
+ 2);
376 message
= packet
+ 4 + i
;
378 if(type
== MESSAGE_PAD1
) {
379 debugf(BABEL_DEBUG_COMMON
,"Received pad1 from %s on %s.",
380 format_address(from
), ifp
->name
);
386 if(type
== MESSAGE_PADN
) {
387 debugf(BABEL_DEBUG_COMMON
,"Received pad%d from %s on %s.",
388 len
, format_address(from
), ifp
->name
);
389 } else if(type
== MESSAGE_ACK_REQ
) {
390 unsigned short nonce
, interval
;
391 DO_NTOHS(nonce
, message
+ 4);
392 DO_NTOHS(interval
, message
+ 6);
393 debugf(BABEL_DEBUG_COMMON
,"Received ack-req (%04X %d) from %s on %s.",
394 nonce
, interval
, format_address(from
), ifp
->name
);
395 send_ack(neigh
, nonce
, interval
);
396 } else if(type
== MESSAGE_ACK
) {
397 debugf(BABEL_DEBUG_COMMON
,"Received ack from %s on %s.",
398 format_address(from
), ifp
->name
);
399 /* Nothing right now */
400 } else if(type
== MESSAGE_HELLO
) {
401 unsigned short seqno
, interval
;
403 unsigned int timestamp
= 0;
404 DO_NTOHS(seqno
, message
+ 4);
405 DO_NTOHS(interval
, message
+ 6);
406 debugf(BABEL_DEBUG_COMMON
,"Received hello %d (%d) from %s on %s.",
408 format_address(from
), ifp
->name
);
409 changed
= update_neighbour(neigh
, seqno
, interval
);
410 update_neighbour_metric(neigh
, changed
);
412 /* Multiply by 3/2 to allow hellos to expire. */
413 schedule_neighbours_check(interval
* 15, 0);
414 /* Sub-TLV handling. */
416 if(parse_hello_subtlv(message
+ 8, len
- 6, ×tamp
) > 0) {
417 neigh
->hello_send_us
= timestamp
;
418 neigh
->hello_rtt_receive_time
= babel_now
;
422 } else if(type
== MESSAGE_IHU
) {
423 unsigned short txcost
, interval
;
424 unsigned char address
[16];
426 DO_NTOHS(txcost
, message
+ 4);
427 DO_NTOHS(interval
, message
+ 6);
428 rc
= network_address(message
[2], message
+ 8, len
- 6, address
);
429 if(rc
< 0) goto fail
;
430 debugf(BABEL_DEBUG_COMMON
,"Received ihu %d (%d) from %s on %s for %s.",
432 format_address(from
), ifp
->name
,
433 format_address(address
));
434 if(message
[2] == 0 || is_interface_ll_address(ifp
, address
)) {
435 int changed
= txcost
!= neigh
->txcost
;
436 neigh
->txcost
= txcost
;
437 neigh
->ihu_time
= babel_now
;
438 neigh
->ihu_interval
= interval
;
439 update_neighbour_metric(neigh
, changed
);
441 /* Multiply by 3/2 to allow neighbours to expire. */
442 schedule_neighbours_check(interval
* 45, 0);
445 parse_ihu_subtlv(message
+ 8 + rc
, len
- 6 - rc
,
446 &hello_send_us
, &hello_rtt_receive_time
);
448 } else if(type
== MESSAGE_ROUTER_ID
) {
449 memcpy(router_id
, message
+ 4, 8);
451 debugf(BABEL_DEBUG_COMMON
,"Received router-id %s from %s on %s.",
452 format_eui64(router_id
), format_address(from
), ifp
->name
);
453 } else if(type
== MESSAGE_NH
) {
454 unsigned char nh
[16];
456 rc
= network_address(message
[2], message
+ 4, len
- 2,
463 debugf(BABEL_DEBUG_COMMON
,"Received nh %s (%d) from %s on %s.",
464 format_address(nh
), message
[2],
465 format_address(from
), ifp
->name
);
466 if(message
[2] == 1) {
467 memcpy(v4_nh
, nh
, 16);
470 memcpy(v6_nh
, nh
, 16);
473 } else if(type
== MESSAGE_UPDATE
) {
474 unsigned char prefix
[16], *nh
;
476 unsigned char channels
[DIVERSITY_HOPS
];
477 unsigned short interval
, seqno
, metric
;
479 DO_NTOHS(interval
, message
+ 6);
480 DO_NTOHS(seqno
, message
+ 8);
481 DO_NTOHS(metric
, message
+ 10);
482 if(message
[5] == 0 ||
483 (message
[2] == 1 ? have_v4_prefix
: have_v6_prefix
))
484 rc
= network_prefix(message
[2], message
[4], message
[5],
486 message
[2] == 1 ? v4_prefix
: v6_prefix
,
491 if(message
[3] & 0x80)
492 have_v4_prefix
= have_v6_prefix
= 0;
495 parsed_len
= 10 + rc
;
497 plen
= message
[4] + (message
[2] == 1 ? 96 : 0);
499 if(message
[3] & 0x80) {
500 if(message
[2] == 1) {
501 memcpy(v4_prefix
, prefix
, 16);
504 memcpy(v6_prefix
, prefix
, 16);
508 if(message
[3] & 0x40) {
509 if(message
[2] == 1) {
510 memset(router_id
, 0, 4);
511 memcpy(router_id
+ 4, prefix
+ 12, 4);
513 memcpy(router_id
, prefix
+ 8, 8);
517 if(!have_router_id
&& message
[2] != 0) {
518 flog_err(EC_BABEL_PACKET
,
519 "Received prefix with no router id.");
522 debugf(BABEL_DEBUG_COMMON
,"Received update%s%s for %s from %s on %s.",
523 (message
[3] & 0x80) ? "/prefix" : "",
524 (message
[3] & 0x40) ? "/id" : "",
525 format_prefix(prefix
, plen
),
526 format_address(from
), ifp
->name
);
528 if(message
[2] == 0) {
529 if(metric
< 0xFFFF) {
530 flog_err(EC_BABEL_PACKET
,
531 "Received wildcard update with finite metric.");
534 retract_neighbour_routes(neigh
);
536 } else if(message
[2] == 1) {
540 } else if(have_v6_nh
) {
546 if(message
[2] == 1) {
547 if(!babel_get_if_nfo(ifp
)->ipv4
)
551 if((babel_get_if_nfo(ifp
)->flags
& BABEL_IF_FARAWAY
)) {
554 /* This will be overwritten by parse_update_subtlv below. */
556 /* Assume non-interfering (wired) link. */
559 /* Assume interfering. */
560 channels
[0] = BABEL_IF_CHANNEL_INTERFERING
;
565 parse_update_subtlv(message
+ 2 + parsed_len
,
566 len
- parsed_len
, channels
);
569 update_route(router_id
, prefix
, plen
, seqno
, metric
, interval
,
571 channels
, channels_len(channels
));
572 } else if(type
== MESSAGE_REQUEST
) {
573 unsigned char prefix
[16], plen
;
575 rc
= network_prefix(message
[2], message
[3], 0,
576 message
+ 4, NULL
, len
- 2, prefix
);
577 if(rc
< 0) goto fail
;
578 plen
= message
[3] + (message
[2] == 1 ? 96 : 0);
579 debugf(BABEL_DEBUG_COMMON
,"Received request for %s from %s on %s.",
580 message
[2] == 0 ? "any" : format_prefix(prefix
, plen
),
581 format_address(from
), ifp
->name
);
582 if(message
[2] == 0) {
583 struct babel_interface
*neigh_ifp
=babel_get_if_nfo(neigh
->ifp
);
584 /* If a neighbour is requesting a full route dump from us,
585 we might as well send it an IHU. */
586 send_ihu(neigh
, NULL
);
587 /* Since nodes send wildcard requests on boot, booting
588 a large number of nodes at the same time may cause an
589 update storm. Ignore a wildcard request that happens
590 shortly after we sent a full update. */
591 if(neigh_ifp
->last_update_time
<
592 (time_t)(babel_now
.tv_sec
-
593 MAX(neigh_ifp
->hello_interval
/ 100, 1)))
594 send_update(neigh
->ifp
, 0, NULL
, 0);
596 send_update(neigh
->ifp
, 0, prefix
, plen
);
598 } else if(type
== MESSAGE_MH_REQUEST
) {
599 unsigned char prefix
[16], plen
;
600 unsigned short seqno
;
602 DO_NTOHS(seqno
, message
+ 4);
603 rc
= network_prefix(message
[2], message
[3], 0,
604 message
+ 16, NULL
, len
- 14, prefix
);
605 if(rc
< 0) goto fail
;
606 plen
= message
[3] + (message
[2] == 1 ? 96 : 0);
607 debugf(BABEL_DEBUG_COMMON
,"Received request (%d) for %s from %s on %s (%s, %d).",
609 format_prefix(prefix
, plen
),
610 format_address(from
), ifp
->name
,
611 format_eui64(message
+ 8), seqno
);
612 handle_request(neigh
, prefix
, plen
, message
[6],
615 debugf(BABEL_DEBUG_COMMON
,"Received unknown packet type %d from %s on %s.",
616 type
, format_address(from
), ifp
->name
);
623 flog_err(EC_BABEL_PACKET
,
624 "Couldn't parse packet (%d, %d) from %s on %s.",
625 message
[0], message
[1], format_address(from
), ifp
->name
);
629 /* We can calculate the RTT to this neighbour. */
630 if(have_hello_rtt
&& hello_send_us
&& hello_rtt_receive_time
) {
631 int remote_waiting_us
, local_waiting_us
;
632 unsigned int rtt
, smoothed_rtt
;
633 unsigned int old_rttcost
;
635 remote_waiting_us
= neigh
->hello_send_us
- hello_rtt_receive_time
;
636 local_waiting_us
= time_us(neigh
->hello_rtt_receive_time
) -
639 /* Sanity checks (validity window of 10 minutes). */
640 if(remote_waiting_us
< 0 || local_waiting_us
< 0 ||
641 remote_waiting_us
> 600000000 || local_waiting_us
> 600000000)
644 rtt
= MAX(0, local_waiting_us
- remote_waiting_us
);
645 debugf(BABEL_DEBUG_COMMON
, "RTT to %s on %s sample result: %d us.",
646 format_address(from
), ifp
->name
, rtt
);
648 old_rttcost
= neighbour_rttcost(neigh
);
649 if (valid_rtt(neigh
)) {
650 /* Running exponential average. */
651 smoothed_rtt
= (babel_ifp
->rtt_decay
* rtt
+
652 (256 - babel_ifp
->rtt_decay
) * neigh
->rtt
);
653 /* Rounding (up or down) to get closer to the sample. */
654 neigh
->rtt
= (neigh
->rtt
>= rtt
) ? smoothed_rtt
/ 256 :
655 (smoothed_rtt
+ 255) / 256;
657 /* We prefer to be conservative with new neighbours
659 assert(rtt
<= 0x7FFFFFFF);
662 changed
= (neighbour_rttcost(neigh
) == old_rttcost
? 0 : 1);
663 update_neighbour_metric(neigh
, changed
);
664 neigh
->rtt_time
= babel_now
;
669 /* Under normal circumstances, there are enough moderation mechanisms
670 elsewhere in the protocol to make sure that this last-ditch check
671 should never trigger. But I'm superstitious. */
674 check_bucket(struct interface
*ifp
)
676 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
677 if(babel_ifp
->bucket
== 0) {
678 int seconds
= babel_now
.tv_sec
- babel_ifp
->bucket_time
;
680 babel_ifp
->bucket
= MIN(BUCKET_TOKENS_MAX
,
681 seconds
* BUCKET_TOKENS_PER_SEC
);
683 /* Reset bucket time unconditionally, in case clock is stepped. */
684 babel_ifp
->bucket_time
= babel_now
.tv_sec
;
687 if(babel_ifp
->bucket
> 0) {
696 fill_rtt_message(struct interface
*ifp
)
698 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
699 if((babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) &&
700 (babel_ifp
->buffered_hello
>= 0)) {
701 if(babel_ifp
->sendbuf
[babel_ifp
->buffered_hello
+ 8] == SUBTLV_PADN
&&
702 babel_ifp
->sendbuf
[babel_ifp
->buffered_hello
+ 9] == 4) {
704 /* Change the type of sub-TLV. */
705 babel_ifp
->sendbuf
[babel_ifp
->buffered_hello
+ 8] =
708 time
= time_us(babel_now
);
709 DO_HTONL(babel_ifp
->sendbuf
+ babel_ifp
->buffered_hello
+ 10, time
);
712 flog_err(EC_BABEL_PACKET
, "No space left for timestamp sub-TLV (this shouldn't happen)");
720 flushbuf(struct interface
*ifp
)
723 struct sockaddr_in6 sin6
;
724 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
726 assert(babel_ifp
->buffered
<= babel_ifp
->bufsize
);
730 if(babel_ifp
->buffered
> 0) {
731 debugf(BABEL_DEBUG_COMMON
," (flushing %d buffered bytes on %s)",
732 babel_ifp
->buffered
, ifp
->name
);
733 if(check_bucket(ifp
)) {
734 memset(&sin6
, 0, sizeof(sin6
));
735 sin6
.sin6_family
= AF_INET6
;
736 memcpy(&sin6
.sin6_addr
, protocol_group
, 16);
737 sin6
.sin6_port
= htons(protocol_port
);
738 sin6
.sin6_scope_id
= ifp
->ifindex
;
739 DO_HTONS(packet_header
+ 2, babel_ifp
->buffered
);
740 fill_rtt_message(ifp
);
741 rc
= babel_send(protocol_socket
,
742 packet_header
, sizeof(packet_header
),
743 babel_ifp
->sendbuf
, babel_ifp
->buffered
,
744 (struct sockaddr
*)&sin6
, sizeof(sin6
));
746 flog_err(EC_BABEL_PACKET
, "send: %s", safe_strerror(errno
));
748 flog_err(EC_BABEL_PACKET
, "Bucket full, dropping packet to %s.",
752 VALGRIND_MAKE_MEM_UNDEFINED(babel_ifp
->sendbuf
, babel_ifp
->bufsize
);
753 babel_ifp
->buffered
= 0;
754 babel_ifp
->buffered_hello
= -1;
755 babel_ifp
->have_buffered_id
= 0;
756 babel_ifp
->have_buffered_nh
= 0;
757 babel_ifp
->have_buffered_prefix
= 0;
758 babel_ifp
->flush_timeout
.tv_sec
= 0;
759 babel_ifp
->flush_timeout
.tv_usec
= 0;
763 schedule_flush(struct interface
*ifp
)
765 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
766 unsigned msecs
= jitter(babel_ifp
, 0);
767 if(babel_ifp
->flush_timeout
.tv_sec
!= 0 &&
768 timeval_minus_msec(&babel_ifp
->flush_timeout
, &babel_now
) < msecs
)
770 set_timeout(&babel_ifp
->flush_timeout
, msecs
);
774 schedule_flush_now(struct interface
*ifp
)
776 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
778 unsigned msecs
= roughly(10);
779 if(babel_ifp
->flush_timeout
.tv_sec
!= 0 &&
780 timeval_minus_msec(&babel_ifp
->flush_timeout
, &babel_now
) < msecs
)
782 set_timeout(&babel_ifp
->flush_timeout
, msecs
);
786 schedule_unicast_flush(unsigned msecs
)
788 if(!unicast_neighbour
)
790 if(unicast_flush_timeout
.tv_sec
!= 0 &&
791 timeval_minus_msec(&unicast_flush_timeout
, &babel_now
) < msecs
)
793 unicast_flush_timeout
.tv_usec
= (babel_now
.tv_usec
+ msecs
* 1000) %1000000;
794 unicast_flush_timeout
.tv_sec
=
795 babel_now
.tv_sec
+ (babel_now
.tv_usec
/ 1000 + msecs
) / 1000;
799 ensure_space(struct interface
*ifp
, int space
)
801 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
802 if(babel_ifp
->bufsize
- babel_ifp
->buffered
< space
)
807 start_message(struct interface
*ifp
, int type
, int len
)
809 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
810 if(babel_ifp
->bufsize
- babel_ifp
->buffered
< len
+ 2)
812 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = type
;
813 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = len
;
817 end_message(struct interface
*ifp
, int type
, int bytes
)
819 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
820 assert(babel_ifp
->buffered
>= bytes
+ 2 &&
821 babel_ifp
->sendbuf
[babel_ifp
->buffered
- bytes
- 2] == type
&&
822 babel_ifp
->sendbuf
[babel_ifp
->buffered
- bytes
- 1] == bytes
);
827 accumulate_byte(struct interface
*ifp
, unsigned char value
)
829 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
830 babel_ifp
->sendbuf
[babel_ifp
->buffered
++] = value
;
834 accumulate_short(struct interface
*ifp
, unsigned short value
)
836 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
837 DO_HTONS(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
);
838 babel_ifp
->buffered
+= 2;
842 accumulate_int(struct interface
*ifp
, unsigned int value
)
844 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
845 DO_HTONL(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
);
846 babel_ifp
->buffered
+= 4;
850 accumulate_bytes(struct interface
*ifp
,
851 const unsigned char *value
, unsigned len
)
853 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
854 memcpy(babel_ifp
->sendbuf
+ babel_ifp
->buffered
, value
, len
);
855 babel_ifp
->buffered
+= len
;
859 start_unicast_message(struct neighbour
*neigh
, int type
, int len
)
861 if(unicast_neighbour
) {
862 if(neigh
!= unicast_neighbour
||
863 unicast_buffered
+ len
+ 2 >=
864 MIN(UNICAST_BUFSIZE
, babel_get_if_nfo(neigh
->ifp
)->bufsize
))
868 unicast_buffer
= malloc(UNICAST_BUFSIZE
);
869 if(!unicast_buffer
) {
870 flog_err(EC_BABEL_MEMORY
, "malloc(unicast_buffer): %s",
871 safe_strerror(errno
));
875 unicast_neighbour
= neigh
;
877 unicast_buffer
[unicast_buffered
++] = type
;
878 unicast_buffer
[unicast_buffered
++] = len
;
883 end_unicast_message(struct neighbour
*neigh
, int type
, int bytes
)
885 assert(unicast_neighbour
== neigh
&& unicast_buffered
>= bytes
+ 2 &&
886 unicast_buffer
[unicast_buffered
- bytes
- 2] == type
&&
887 unicast_buffer
[unicast_buffered
- bytes
- 1] == bytes
);
888 schedule_unicast_flush(jitter(babel_get_if_nfo(neigh
->ifp
), 0));
892 accumulate_unicast_byte(struct neighbour
*neigh
, unsigned char value
)
894 unicast_buffer
[unicast_buffered
++] = value
;
898 accumulate_unicast_short(struct neighbour
*neigh
, unsigned short value
)
900 DO_HTONS(unicast_buffer
+ unicast_buffered
, value
);
901 unicast_buffered
+= 2;
905 accumulate_unicast_int(struct neighbour
*neigh
, unsigned int value
)
907 DO_HTONL(unicast_buffer
+ unicast_buffered
, value
);
908 unicast_buffered
+= 4;
912 accumulate_unicast_bytes(struct neighbour
*neigh
,
913 const unsigned char *value
, unsigned len
)
915 memcpy(unicast_buffer
+ unicast_buffered
, value
, len
);
916 unicast_buffered
+= len
;
920 send_ack(struct neighbour
*neigh
, unsigned short nonce
, unsigned short interval
)
923 debugf(BABEL_DEBUG_COMMON
,"Sending ack (%04x) to %s on %s.",
924 nonce
, format_address(neigh
->address
), neigh
->ifp
->name
);
925 rc
= start_unicast_message(neigh
, MESSAGE_ACK
, 2); if(rc
< 0) return;
926 accumulate_unicast_short(neigh
, nonce
);
927 end_unicast_message(neigh
, MESSAGE_ACK
, 2);
928 /* Roughly yields a value no larger than 3/2, so this meets the deadline */
929 schedule_unicast_flush(roughly(interval
* 6));
933 send_hello_noupdate(struct interface
*ifp
, unsigned interval
)
935 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
936 /* This avoids sending multiple hellos in a single packet, which breaks
937 link quality estimation. */
938 if(babel_ifp
->buffered_hello
>= 0)
941 babel_ifp
->hello_seqno
= seqno_plus(babel_ifp
->hello_seqno
, 1);
942 set_timeout(&babel_ifp
->hello_timeout
, babel_ifp
->hello_interval
);
947 debugf(BABEL_DEBUG_COMMON
,"Sending hello %d (%d) to %s.",
948 babel_ifp
->hello_seqno
, interval
, ifp
->name
);
950 start_message(ifp
, MESSAGE_HELLO
,
951 (babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) ? 12 : 6);
952 babel_ifp
->buffered_hello
= babel_ifp
->buffered
- 2;
953 accumulate_short(ifp
, 0);
954 accumulate_short(ifp
, babel_ifp
->hello_seqno
);
955 accumulate_short(ifp
, interval
> 0xFFFF ? 0xFFFF : interval
);
956 if(babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) {
957 /* Sub-TLV containing the local time of emission. We use a
958 Pad4 sub-TLV, which we'll fill just before sending. */
959 accumulate_byte(ifp
, SUBTLV_PADN
);
960 accumulate_byte(ifp
, 4);
961 accumulate_int(ifp
, 0);
963 end_message(ifp
, MESSAGE_HELLO
,
964 (babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) ? 12 : 6);
968 send_hello(struct interface
*ifp
)
970 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
971 send_hello_noupdate(ifp
, (babel_ifp
->hello_interval
+ 9) / 10);
972 /* Send full IHU every 3 hellos, and marginal IHU each time */
973 if(babel_ifp
->hello_seqno
% 3 == 0)
976 send_marginal_ihu(ifp
);
980 flush_unicast(int dofree
)
982 struct sockaddr_in6 sin6
;
985 if(unicast_buffered
== 0)
988 if(!if_up(unicast_neighbour
->ifp
))
991 /* Preserve ordering of messages */
992 flushbuf(unicast_neighbour
->ifp
);
994 if(check_bucket(unicast_neighbour
->ifp
)) {
995 memset(&sin6
, 0, sizeof(sin6
));
996 sin6
.sin6_family
= AF_INET6
;
997 memcpy(&sin6
.sin6_addr
, unicast_neighbour
->address
, 16);
998 sin6
.sin6_port
= htons(protocol_port
);
999 sin6
.sin6_scope_id
= unicast_neighbour
->ifp
->ifindex
;
1000 DO_HTONS(packet_header
+ 2, unicast_buffered
);
1001 fill_rtt_message(unicast_neighbour
->ifp
);
1002 rc
= babel_send(protocol_socket
,
1003 packet_header
, sizeof(packet_header
),
1004 unicast_buffer
, unicast_buffered
,
1005 (struct sockaddr
*)&sin6
, sizeof(sin6
));
1007 flog_err(EC_BABEL_PACKET
, "send(unicast): %s",
1008 safe_strerror(errno
));
1010 flog_err(EC_BABEL_PACKET
,
1011 "Bucket full, dropping unicast packet to %s if %s.",
1012 format_address(unicast_neighbour
->address
),
1013 unicast_neighbour
->ifp
->name
);
1017 VALGRIND_MAKE_MEM_UNDEFINED(unicast_buffer
, UNICAST_BUFSIZE
);
1018 unicast_buffered
= 0;
1019 if(dofree
&& unicast_buffer
) {
1020 free(unicast_buffer
);
1021 unicast_buffer
= NULL
;
1023 unicast_neighbour
= NULL
;
1024 unicast_flush_timeout
.tv_sec
= 0;
1025 unicast_flush_timeout
.tv_usec
= 0;
1029 really_send_update(struct interface
*ifp
,
1030 const unsigned char *id
,
1031 const unsigned char *prefix
, unsigned char plen
,
1032 unsigned short seqno
, unsigned short metric
,
1033 unsigned char *channels
, int channels_len
)
1035 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1036 int add_metric
, v4
, real_plen
, omit
= 0;
1037 const unsigned char *real_prefix
;
1038 unsigned short flags
= 0;
1041 if(diversity_kind
!= DIVERSITY_CHANNEL
)
1044 channels_size
= channels_len
>= 0 ? channels_len
+ 2 : 0;
1049 add_metric
= output_filter(id
, prefix
, plen
, ifp
->ifindex
);
1050 if(add_metric
>= INFINITY
)
1053 metric
= MIN(metric
+ add_metric
, INFINITY
);
1055 ensure_space(ifp
, 20 + 12 + 28);
1057 v4
= plen
>= 96 && v4mapped(prefix
);
1060 if(!babel_ifp
->ipv4
)
1062 if(!babel_ifp
->have_buffered_nh
||
1063 memcmp(babel_ifp
->buffered_nh
, babel_ifp
->ipv4
, 4) != 0) {
1064 start_message(ifp
, MESSAGE_NH
, 6);
1065 accumulate_byte(ifp
, 1);
1066 accumulate_byte(ifp
, 0);
1067 accumulate_bytes(ifp
, babel_ifp
->ipv4
, 4);
1068 end_message(ifp
, MESSAGE_NH
, 6);
1069 memcpy(babel_ifp
->buffered_nh
, babel_ifp
->ipv4
, 4);
1070 babel_ifp
->have_buffered_nh
= 1;
1073 real_prefix
= prefix
+ 12;
1074 real_plen
= plen
- 96;
1076 if(babel_ifp
->have_buffered_prefix
) {
1077 while(omit
< plen
/ 8 &&
1078 babel_ifp
->buffered_prefix
[omit
] == prefix
[omit
])
1081 if(!babel_ifp
->have_buffered_prefix
|| plen
>= 48)
1083 real_prefix
= prefix
;
1087 if(!babel_ifp
->have_buffered_id
1088 || memcmp(id
, babel_ifp
->buffered_id
, 8) != 0) {
1089 if(real_plen
== 128 && memcmp(real_prefix
+ 8, id
, 8) == 0) {
1092 start_message(ifp
, MESSAGE_ROUTER_ID
, 10);
1093 accumulate_short(ifp
, 0);
1094 accumulate_bytes(ifp
, id
, 8);
1095 end_message(ifp
, MESSAGE_ROUTER_ID
, 10);
1097 memcpy(babel_ifp
->buffered_id
, id
, sizeof(babel_ifp
->buffered_id
));
1098 babel_ifp
->have_buffered_id
= 1;
1101 start_message(ifp
, MESSAGE_UPDATE
, 10 + (real_plen
+ 7) / 8 - omit
+
1103 accumulate_byte(ifp
, v4
? 1 : 2);
1104 accumulate_byte(ifp
, flags
);
1105 accumulate_byte(ifp
, real_plen
);
1106 accumulate_byte(ifp
, omit
);
1107 accumulate_short(ifp
, (babel_ifp
->update_interval
+ 5) / 10);
1108 accumulate_short(ifp
, seqno
);
1109 accumulate_short(ifp
, metric
);
1110 accumulate_bytes(ifp
, real_prefix
+ omit
, (real_plen
+ 7) / 8 - omit
);
1111 /* Note that an empty channels TLV is different from no such TLV. */
1112 if(channels_len
>= 0) {
1113 accumulate_byte(ifp
, 2);
1114 accumulate_byte(ifp
, channels_len
);
1116 if (channels
&& channels_len
> 0)
1117 accumulate_bytes(ifp
, channels
, channels_len
);
1119 end_message(ifp
, MESSAGE_UPDATE
, 10 + (real_plen
+ 7) / 8 - omit
+
1123 memcpy(babel_ifp
->buffered_prefix
, prefix
, 16);
1124 babel_ifp
->have_buffered_prefix
= 1;
1129 compare_buffered_updates(const void *av
, const void *bv
)
1131 const struct buffered_update
*a
= av
, *b
= bv
;
1132 int rc
, v4a
, v4b
, ma
, mb
;
1134 rc
= memcmp(a
->id
, b
->id
, 8);
1138 v4a
= (a
->plen
>= 96 && v4mapped(a
->prefix
));
1139 v4b
= (b
->plen
>= 96 && v4mapped(b
->prefix
));
1146 ma
= (!v4a
&& a
->plen
== 128 && memcmp(a
->prefix
+ 8, a
->id
, 8) == 0);
1147 mb
= (!v4b
&& b
->plen
== 128 && memcmp(b
->prefix
+ 8, b
->id
, 8) == 0);
1154 if(a
->plen
< b
->plen
)
1156 else if(a
->plen
> b
->plen
)
1159 return memcmp(a
->prefix
, b
->prefix
, 16);
1163 flushupdates(struct interface
*ifp
)
1165 babel_interface_nfo
*babel_ifp
= NULL
;
1166 struct xroute
*xroute
;
1167 struct babel_route
*route
;
1168 const unsigned char *last_prefix
= NULL
;
1169 unsigned char last_plen
= 0xFF;
1173 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1174 struct interface
*ifp_aux
;
1175 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1176 flushupdates(ifp_aux
);
1180 babel_ifp
= babel_get_if_nfo(ifp
);
1181 if(babel_ifp
->num_buffered_updates
> 0) {
1182 struct buffered_update
*b
= babel_ifp
->buffered_updates
;
1183 int n
= babel_ifp
->num_buffered_updates
;
1185 babel_ifp
->buffered_updates
= NULL
;
1186 babel_ifp
->update_bufsize
= 0;
1187 babel_ifp
->num_buffered_updates
= 0;
1192 debugf(BABEL_DEBUG_COMMON
," (flushing %d buffered updates on %s (%d))",
1193 n
, ifp
->name
, ifp
->ifindex
);
1195 /* In order to send fewer update messages, we want to send updates
1196 with the same router-id together, with IPv6 going out before IPv4. */
1198 for(i
= 0; i
< n
; i
++) {
1199 route
= find_installed_route(b
[i
].prefix
, b
[i
].plen
);
1201 memcpy(b
[i
].id
, route
->src
->id
, 8);
1203 memcpy(b
[i
].id
, myid
, 8);
1206 qsort(b
, n
, sizeof(struct buffered_update
), compare_buffered_updates
);
1208 for(i
= 0; i
< n
; i
++) {
1209 /* The same update may be scheduled multiple times before it is
1210 sent out. Since our buffer is now sorted, it is enough to
1211 compare with the previous update. */
1214 if(b
[i
].plen
== last_plen
&&
1215 memcmp(b
[i
].prefix
, last_prefix
, 16) == 0)
1219 xroute
= find_xroute(b
[i
].prefix
, b
[i
].plen
);
1220 route
= find_installed_route(b
[i
].prefix
, b
[i
].plen
);
1222 if(xroute
&& (!route
|| xroute
->metric
<= kernel_metric
)) {
1223 really_send_update(ifp
, myid
,
1224 xroute
->prefix
, xroute
->plen
,
1225 myseqno
, xroute
->metric
,
1227 last_prefix
= xroute
->prefix
;
1228 last_plen
= xroute
->plen
;
1230 unsigned char channels
[DIVERSITY_HOPS
];
1232 struct interface
*route_ifp
= route
->neigh
->ifp
;
1233 struct babel_interface
*babel_route_ifp
= NULL
;
1234 unsigned short metric
;
1235 unsigned short seqno
;
1237 seqno
= route
->seqno
;
1239 route_interferes(route
, ifp
) ?
1240 route_metric(route
) :
1241 route_metric_noninterfering(route
);
1243 if(metric
< INFINITY
)
1244 satisfy_request(route
->src
->prefix
, route
->src
->plen
,
1245 seqno
, route
->src
->id
, ifp
);
1246 if((babel_ifp
->flags
& BABEL_IF_SPLIT_HORIZON
) &&
1247 route
->neigh
->ifp
== ifp
)
1250 babel_route_ifp
= babel_get_if_nfo(route_ifp
);
1251 if(babel_route_ifp
->channel
==BABEL_IF_CHANNEL_NONINTERFERING
) {
1252 memcpy(channels
, route
->channels
, DIVERSITY_HOPS
);
1254 if(babel_route_ifp
->channel
== BABEL_IF_CHANNEL_UNKNOWN
)
1255 channels
[0] = BABEL_IF_CHANNEL_INTERFERING
;
1257 assert(babel_route_ifp
->channel
> 0 &&
1258 babel_route_ifp
->channel
<= 255);
1259 channels
[0] = babel_route_ifp
->channel
;
1261 memcpy(channels
+ 1, route
->channels
, DIVERSITY_HOPS
- 1);
1264 chlen
= channels_len(channels
);
1265 really_send_update(ifp
, route
->src
->id
,
1270 update_source(route
->src
, seqno
, metric
);
1271 last_prefix
= route
->src
->prefix
;
1272 last_plen
= route
->src
->plen
;
1274 /* There's no route for this prefix. This can happen shortly
1275 after an xroute has been retracted, so send a retraction. */
1276 really_send_update(ifp
, myid
, b
[i
].prefix
, b
[i
].plen
,
1277 myseqno
, INFINITY
, NULL
, -1);
1280 schedule_flush_now(ifp
);
1284 babel_ifp
->update_flush_timeout
.tv_sec
= 0;
1285 babel_ifp
->update_flush_timeout
.tv_usec
= 0;
1289 schedule_update_flush(struct interface
*ifp
, int urgent
)
1291 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1293 msecs
= update_jitter(babel_ifp
, urgent
);
1294 if(babel_ifp
->update_flush_timeout
.tv_sec
!= 0 &&
1295 timeval_minus_msec(&babel_ifp
->update_flush_timeout
, &babel_now
) < msecs
)
1297 set_timeout(&babel_ifp
->update_flush_timeout
, msecs
);
1301 buffer_update(struct interface
*ifp
,
1302 const unsigned char *prefix
, unsigned char plen
)
1304 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
1305 if(babel_ifp
->num_buffered_updates
> 0 &&
1306 babel_ifp
->num_buffered_updates
>= babel_ifp
->update_bufsize
)
1309 if(babel_ifp
->update_bufsize
== 0) {
1311 assert(babel_ifp
->buffered_updates
== NULL
);
1312 /* Allocate enough space to hold a full update. Since the
1313 number of installed routes will grow over time, make sure we
1314 have enough space to send a full-ish frame. */
1315 n
= installed_routes_estimate() + xroutes_estimate() + 4;
1316 n
= MAX(n
, babel_ifp
->bufsize
/ 16);
1318 babel_ifp
->buffered_updates
= malloc(n
*sizeof(struct buffered_update
));
1319 if(babel_ifp
->buffered_updates
== NULL
) {
1320 flog_err(EC_BABEL_MEMORY
, "malloc(buffered_updates): %s",
1321 safe_strerror(errno
));
1323 /* Try again with a tiny buffer. */
1329 babel_ifp
->update_bufsize
= n
;
1330 babel_ifp
->num_buffered_updates
= 0;
1333 memcpy(babel_ifp
->buffered_updates
[babel_ifp
->num_buffered_updates
].prefix
,
1335 babel_ifp
->buffered_updates
[babel_ifp
->num_buffered_updates
].plen
= plen
;
1336 babel_ifp
->num_buffered_updates
++;
1340 send_update(struct interface
*ifp
, int urgent
,
1341 const unsigned char *prefix
, unsigned char plen
)
1343 babel_interface_nfo
*babel_ifp
= NULL
;
1346 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1347 struct interface
*ifp_aux
;
1348 struct babel_route
*route
;
1349 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1350 send_update(ifp_aux
, urgent
, prefix
, plen
);
1352 /* Since flushupdates only deals with non-wildcard interfaces, we
1353 need to do this now. */
1354 route
= find_installed_route(prefix
, plen
);
1355 if(route
&& route_metric(route
) < INFINITY
)
1356 satisfy_request(prefix
, plen
, route
->src
->seqno
, route
->src
->id
,
1365 babel_ifp
= babel_get_if_nfo(ifp
);
1367 debugf(BABEL_DEBUG_COMMON
,"Sending update to %s for %s.",
1368 ifp
->name
, format_prefix(prefix
, plen
));
1369 buffer_update(ifp
, prefix
, plen
);
1371 struct route_stream
*routes
= NULL
;
1372 send_self_update(ifp
);
1373 debugf(BABEL_DEBUG_COMMON
,"Sending update to %s for any.", ifp
->name
);
1374 routes
= route_stream(1);
1377 struct babel_route
*route
= route_stream_next(routes
);
1380 buffer_update(ifp
, route
->src
->prefix
, route
->src
->plen
);
1382 route_stream_done(routes
);
1384 flog_err(EC_BABEL_MEMORY
, "Couldn't allocate route stream.");
1386 set_timeout(&babel_ifp
->update_timeout
, babel_ifp
->update_interval
);
1387 babel_ifp
->last_update_time
= babel_now
.tv_sec
;
1389 schedule_update_flush(ifp
, urgent
);
1393 send_update_resend(struct interface
*ifp
,
1394 const unsigned char *prefix
, unsigned char plen
)
1396 assert(prefix
!= NULL
);
1398 send_update(ifp
, 1, prefix
, plen
);
1399 record_resend(RESEND_UPDATE
, prefix
, plen
, 0, NULL
, NULL
, resend_delay
);
1403 send_wildcard_retraction(struct interface
*ifp
)
1405 babel_interface_nfo
*babel_ifp
= NULL
;
1407 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1408 struct interface
*ifp_aux
;
1409 FOR_ALL_INTERFACES(vrf
, ifp_aux
)
1410 send_wildcard_retraction(ifp_aux
);
1417 babel_ifp
= babel_get_if_nfo(ifp
);
1418 start_message(ifp
, MESSAGE_UPDATE
, 10);
1419 accumulate_byte(ifp
, 0);
1420 accumulate_byte(ifp
, 0x40);
1421 accumulate_byte(ifp
, 0);
1422 accumulate_byte(ifp
, 0);
1423 accumulate_short(ifp
, 0xFFFF);
1424 accumulate_short(ifp
, myseqno
);
1425 accumulate_short(ifp
, 0xFFFF);
1426 end_message(ifp
, MESSAGE_UPDATE
, 10);
1428 babel_ifp
->have_buffered_id
= 0;
1432 update_myseqno(void)
1434 myseqno
= seqno_plus(myseqno
, 1);
1438 send_self_update(struct interface
*ifp
)
1440 struct xroute_stream
*xroutes
;
1442 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1443 struct interface
*ifp_aux
;
1444 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1447 send_self_update(ifp_aux
);
1452 debugf(BABEL_DEBUG_COMMON
,"Sending self update to %s.", ifp
->name
);
1453 xroutes
= xroute_stream();
1456 struct xroute
*xroute
= xroute_stream_next(xroutes
);
1457 if(xroute
== NULL
) break;
1458 send_update(ifp
, 0, xroute
->prefix
, xroute
->plen
);
1460 xroute_stream_done(xroutes
);
1462 flog_err(EC_BABEL_MEMORY
, "Couldn't allocate xroute stream.");
1467 send_ihu(struct neighbour
*neigh
, struct interface
*ifp
)
1469 babel_interface_nfo
*babel_ifp
= NULL
;
1470 int rxcost
, interval
;
1475 if(neigh
== NULL
&& ifp
== NULL
) {
1476 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1477 struct interface
*ifp_aux
;
1478 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1481 send_ihu(NULL
, ifp_aux
);
1487 struct neighbour
*ngh
;
1488 FOR_ALL_NEIGHBOURS(ngh
) {
1496 if(ifp
&& neigh
->ifp
!= ifp
)
1500 babel_ifp
= babel_get_if_nfo(ifp
);
1504 rxcost
= neighbour_rxcost(neigh
);
1505 interval
= (babel_ifp
->hello_interval
* 3 + 9) / 10;
1507 /* Conceptually, an IHU is a unicast message. We usually send them as
1508 multicast, since this allows aggregation into a single packet and
1509 avoids an ARP exchange. If we already have a unicast message queued
1510 for this neighbour, however, we might as well piggyback the IHU. */
1511 debugf(BABEL_DEBUG_COMMON
,"Sending %sihu %d on %s to %s.",
1512 unicast_neighbour
== neigh
? "unicast " : "",
1515 format_address(neigh
->address
));
1517 ll
= linklocal(neigh
->address
);
1519 if((babel_ifp
->flags
& BABEL_IF_TIMESTAMPS
) && neigh
->hello_send_us
1520 /* Checks whether the RTT data is not too old to be sent. */
1521 && timeval_minus_msec(&babel_now
,
1522 &neigh
->hello_rtt_receive_time
) < 1000000) {
1525 neigh
->hello_send_us
= 0;
1529 /* The length depends on the format of the address, and then an
1530 optional 10-bytes sub-TLV for timestamps (used to compute a RTT). */
1531 msglen
= (ll
? 14 : 22) + (send_rtt_data
? 10 : 0);
1533 if(unicast_neighbour
!= neigh
) {
1534 start_message(ifp
, MESSAGE_IHU
, msglen
);
1535 accumulate_byte(ifp
, ll
? 3 : 2);
1536 accumulate_byte(ifp
, 0);
1537 accumulate_short(ifp
, rxcost
);
1538 accumulate_short(ifp
, interval
);
1540 accumulate_bytes(ifp
, neigh
->address
+ 8, 8);
1542 accumulate_bytes(ifp
, neigh
->address
, 16);
1543 if (send_rtt_data
) {
1544 accumulate_byte(ifp
, SUBTLV_TIMESTAMP
);
1545 accumulate_byte(ifp
, 8);
1546 accumulate_int(ifp
, neigh
->hello_send_us
);
1547 accumulate_int(ifp
, time_us(neigh
->hello_rtt_receive_time
));
1549 end_message(ifp
, MESSAGE_IHU
, msglen
);
1552 rc
= start_unicast_message(neigh
, MESSAGE_IHU
, msglen
);
1554 accumulate_unicast_byte(neigh
, ll
? 3 : 2);
1555 accumulate_unicast_byte(neigh
, 0);
1556 accumulate_unicast_short(neigh
, rxcost
);
1557 accumulate_unicast_short(neigh
, interval
);
1559 accumulate_unicast_bytes(neigh
, neigh
->address
+ 8, 8);
1561 accumulate_unicast_bytes(neigh
, neigh
->address
, 16);
1562 if (send_rtt_data
) {
1563 accumulate_unicast_byte(neigh
, SUBTLV_TIMESTAMP
);
1564 accumulate_unicast_byte(neigh
, 8);
1565 accumulate_unicast_int(neigh
, neigh
->hello_send_us
);
1566 accumulate_unicast_int(neigh
,
1567 time_us(neigh
->hello_rtt_receive_time
));
1569 end_unicast_message(neigh
, MESSAGE_IHU
, msglen
);
1573 /* Send IHUs to all marginal neighbours */
1575 send_marginal_ihu(struct interface
*ifp
)
1577 struct neighbour
*neigh
;
1578 FOR_ALL_NEIGHBOURS(neigh
) {
1579 if(ifp
&& neigh
->ifp
!= ifp
)
1581 if(neigh
->txcost
>= 384 || (neigh
->reach
& 0xF000) != 0xF000)
1582 send_ihu(neigh
, ifp
);
1587 send_request(struct interface
*ifp
,
1588 const unsigned char *prefix
, unsigned char plen
)
1593 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1594 struct interface
*ifp_aux
;
1595 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1598 send_request(ifp_aux
, prefix
, plen
);
1603 /* make sure any buffered updates go out before this request. */
1609 debugf(BABEL_DEBUG_COMMON
,"sending request to %s for %s.",
1610 ifp
->name
, prefix
? format_prefix(prefix
, plen
) : "any");
1611 v4
= plen
>= 96 && v4mapped(prefix
);
1612 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1613 len
= !prefix
? 2 : 2 + pb
;
1615 start_message(ifp
, MESSAGE_REQUEST
, len
);
1616 accumulate_byte(ifp
, !prefix
? 0 : v4
? 1 : 2);
1617 accumulate_byte(ifp
, !prefix
? 0 : v4
? plen
- 96 : plen
);
1620 accumulate_bytes(ifp
, prefix
+ 12, pb
);
1622 accumulate_bytes(ifp
, prefix
, pb
);
1624 end_message(ifp
, MESSAGE_REQUEST
, len
);
1628 send_unicast_request(struct neighbour
*neigh
,
1629 const unsigned char *prefix
, unsigned char plen
)
1631 int rc
, v4
, pb
, len
;
1633 /* make sure any buffered updates go out before this request. */
1634 flushupdates(neigh
->ifp
);
1636 debugf(BABEL_DEBUG_COMMON
,"sending unicast request to %s for %s.",
1637 format_address(neigh
->address
),
1638 prefix
? format_prefix(prefix
, plen
) : "any");
1639 v4
= plen
>= 96 && v4mapped(prefix
);
1640 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1641 len
= !prefix
? 2 : 2 + pb
;
1643 rc
= start_unicast_message(neigh
, MESSAGE_REQUEST
, len
);
1645 accumulate_unicast_byte(neigh
, !prefix
? 0 : v4
? 1 : 2);
1646 accumulate_unicast_byte(neigh
, !prefix
? 0 : v4
? plen
- 96 : plen
);
1649 accumulate_unicast_bytes(neigh
, prefix
+ 12, pb
);
1651 accumulate_unicast_bytes(neigh
, prefix
, pb
);
1653 end_unicast_message(neigh
, MESSAGE_REQUEST
, len
);
1657 send_multihop_request(struct interface
*ifp
,
1658 const unsigned char *prefix
, unsigned char plen
,
1659 unsigned short seqno
, const unsigned char *id
,
1660 unsigned short hop_count
)
1664 /* Make sure any buffered updates go out before this request. */
1668 struct vrf
*vrf
= vrf_lookup_by_id(VRF_DEFAULT
);
1669 struct interface
*ifp_aux
;
1670 FOR_ALL_INTERFACES(vrf
, ifp_aux
) {
1673 send_multihop_request(ifp_aux
, prefix
, plen
, seqno
, id
, hop_count
);
1681 debugf(BABEL_DEBUG_COMMON
,"Sending request (%d) on %s for %s.",
1682 hop_count
, ifp
->name
, format_prefix(prefix
, plen
));
1683 v4
= plen
>= 96 && v4mapped(prefix
);
1684 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1687 start_message(ifp
, MESSAGE_MH_REQUEST
, len
);
1688 accumulate_byte(ifp
, v4
? 1 : 2);
1689 accumulate_byte(ifp
, v4
? plen
- 96 : plen
);
1690 accumulate_short(ifp
, seqno
);
1691 accumulate_byte(ifp
, hop_count
);
1692 accumulate_byte(ifp
, 0);
1693 accumulate_bytes(ifp
, id
, 8);
1696 accumulate_bytes(ifp
, prefix
+ 12, pb
);
1698 accumulate_bytes(ifp
, prefix
, pb
);
1700 end_message(ifp
, MESSAGE_MH_REQUEST
, len
);
1704 send_unicast_multihop_request(struct neighbour
*neigh
,
1705 const unsigned char *prefix
, unsigned char plen
,
1706 unsigned short seqno
, const unsigned char *id
,
1707 unsigned short hop_count
)
1709 int rc
, v4
, pb
, len
;
1711 /* Make sure any buffered updates go out before this request. */
1712 flushupdates(neigh
->ifp
);
1714 debugf(BABEL_DEBUG_COMMON
,"Sending multi-hop request to %s for %s (%d hops).",
1715 format_address(neigh
->address
),
1716 format_prefix(prefix
, plen
), hop_count
);
1717 v4
= plen
>= 96 && v4mapped(prefix
);
1718 pb
= v4
? ((plen
- 96) + 7) / 8 : (plen
+ 7) / 8;
1721 rc
= start_unicast_message(neigh
, MESSAGE_MH_REQUEST
, len
);
1723 accumulate_unicast_byte(neigh
, v4
? 1 : 2);
1724 accumulate_unicast_byte(neigh
, v4
? plen
- 96 : plen
);
1725 accumulate_unicast_short(neigh
, seqno
);
1726 accumulate_unicast_byte(neigh
, hop_count
);
1727 accumulate_unicast_byte(neigh
, 0);
1728 accumulate_unicast_bytes(neigh
, id
, 8);
1731 accumulate_unicast_bytes(neigh
, prefix
+ 12, pb
);
1733 accumulate_unicast_bytes(neigh
, prefix
, pb
);
1735 end_unicast_message(neigh
, MESSAGE_MH_REQUEST
, len
);
1739 send_request_resend(struct neighbour
*neigh
,
1740 const unsigned char *prefix
, unsigned char plen
,
1741 unsigned short seqno
, unsigned char *id
)
1744 send_unicast_multihop_request(neigh
, prefix
, plen
, seqno
, id
, 127);
1746 send_multihop_request(NULL
, prefix
, plen
, seqno
, id
, 127);
1748 record_resend(RESEND_REQUEST
, prefix
, plen
, seqno
, id
,
1749 neigh
? neigh
->ifp
: NULL
, resend_delay
);
1753 handle_request(struct neighbour
*neigh
, const unsigned char *prefix
,
1754 unsigned char plen
, unsigned char hop_count
,
1755 unsigned short seqno
, const unsigned char *id
)
1757 struct xroute
*xroute
;
1758 struct babel_route
*route
;
1759 struct neighbour
*successor
= NULL
;
1761 xroute
= find_xroute(prefix
, plen
);
1762 route
= find_installed_route(prefix
, plen
);
1764 if(xroute
&& (!route
|| xroute
->metric
<= kernel_metric
)) {
1765 if(hop_count
> 0 && memcmp(id
, myid
, 8) == 0) {
1766 if(seqno_compare(seqno
, myseqno
) > 0) {
1767 if(seqno_minus(seqno
, myseqno
) > 100) {
1768 /* Hopelessly out-of-date request */
1774 send_update(neigh
->ifp
, 1, prefix
, plen
);
1779 (memcmp(id
, route
->src
->id
, 8) != 0 ||
1780 seqno_compare(seqno
, route
->seqno
) <= 0)) {
1781 send_update(neigh
->ifp
, 1, prefix
, plen
);
1788 if(route
&& memcmp(id
, route
->src
->id
, 8) == 0 &&
1789 seqno_minus(seqno
, route
->seqno
) > 100) {
1790 /* Hopelessly out-of-date */
1794 if(request_redundant(neigh
->ifp
, prefix
, plen
, seqno
, id
))
1797 /* Let's try to forward this request. */
1798 if(route
&& route_metric(route
) < INFINITY
)
1799 successor
= route
->neigh
;
1801 if(!successor
|| successor
== neigh
) {
1802 /* We were about to forward a request to its requestor. Try to
1803 find a different neighbour to forward the request to. */
1804 struct babel_route
*other_route
;
1806 other_route
= find_best_route(prefix
, plen
, 0, neigh
);
1807 if(other_route
&& route_metric(other_route
) < INFINITY
)
1808 successor
= other_route
->neigh
;
1811 if(!successor
|| successor
== neigh
)
1815 send_unicast_multihop_request(successor
, prefix
, plen
, seqno
, id
,
1817 record_resend(RESEND_REQUEST
, prefix
, plen
, seqno
, id
,