]> git.proxmox.com Git - mirror_frr.git/blame - babeld/message.c
projects / mirror_frr.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Merge pull request #3051 from mitch-skiba/addpath_change_V1
[mirror_frr.git] / babeld / message.c
CommitLineData
ca10883e
DS		 1/*
2Copyright (c) 2007, 2008 by Juliusz Chroboczek
3
4Permission is hereby granted, free of charge, to any person obtaining a copy
5of this software and associated documentation files (the "Software"), to deal
6in the Software without restriction, including without limitation the rights
7to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8copies of the Software, and to permit persons to whom the Software is
9furnished to do so, subject to the following conditions:
10
11The above copyright notice and this permission notice shall be included in
12all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20THE SOFTWARE.
21*/
22
23#include <zebra.h>
24#include "if.h"
25
26#include "babeld.h"
27#include "util.h"
28#include "net.h"
29#include "babel_interface.h"
30#include "source.h"
31#include "neighbour.h"
32#include "route.h"
33#include "xroute.h"
34#include "resend.h"
35#include "message.h"
36#include "kernel.h"
37#include "babel_main.h"
e33b116c 38#include "babel_errors.h"
ca10883e
DS		 39
40static unsigned char packet_header[4] = {42, 2};
41
42int split_horizon = 1;
43
44unsigned short myseqno = 0;
45
46#define UNICAST_BUFSIZE 1024
47static int unicast_buffered = 0;
48static unsigned char *unicast_buffer = NULL;
49struct neighbour *unicast_neighbour = NULL;
50struct timeval unicast_flush_timeout = {0, 0};
51
52/* Minimum TLV _body_ length for TLVs of particular types (0 = no limit). */
53static const unsigned char tlv_min_length[MESSAGE_MAX + 1] =
54{
55 [ MESSAGE_PAD1 ] = 0,
56 [ MESSAGE_PADN ] = 0,
57 [ MESSAGE_ACK_REQ ] = 6,
58 [ MESSAGE_ACK ] = 2,
59 [ MESSAGE_HELLO ] = 6,
60 [ MESSAGE_IHU ] = 6,
61 [ MESSAGE_ROUTER_ID ] = 10,
62 [ MESSAGE_NH ] = 2,
63 [ MESSAGE_UPDATE ] = 10,
64 [ MESSAGE_REQUEST ] = 2,
65 [ MESSAGE_MH_REQUEST ] = 14,
66};
67
68/* Parse a network prefix, encoded in the somewhat baroque compressed
69 representation used by Babel. Return the number of bytes parsed. */
70static int
71network_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)
74{
75 unsigned pb;
76 unsigned char prefix[16];
77 int ret = -1;
78
79 if(plen >= 0)
80 pb = (plen + 7) / 8;
81 else if(ae == 1)
82 pb = 4;
83 else
84 pb = 16;
85
86 if(pb > 16)
87 return -1;
88
89 memset(prefix, 0, 16);
90
91 switch(ae) {
92 case 0:
93 ret = 0;
94 break;
95 case 1:
96 if(omitted > 4 || pb > 4 || (pb > omitted && len < pb - omitted))
97 return -1;
98 memcpy(prefix, v4prefix, 12);
99 if(omitted) {
100 if (dp == NULL || !v4mapped(dp)) return -1;
101 memcpy(prefix, dp, 12 + omitted);
102 }
103 if(pb > omitted) memcpy(prefix + 12 + omitted, p, pb - omitted);
104 ret = pb - omitted;
105 break;
106 case 2:
107 if(omitted > 16 || (pb > omitted && len < pb - omitted)) return -1;
108 if(omitted) {
109 if (dp == NULL || v4mapped(dp)) return -1;
110 memcpy(prefix, dp, omitted);
111 }
112 if(pb > omitted) memcpy(prefix + omitted, p, pb - omitted);
113 ret = pb - omitted;
114 break;
115 case 3:
116 if(pb > 8 && len < pb - 8) return -1;
117 prefix[0] = 0xfe;
118 prefix[1] = 0x80;
119 if(pb > 8) memcpy(prefix + 8, p, pb - 8);
120 ret = pb - 8;
121 break;
122 default:
123 return -1;
124 }
125
126 mask_prefix(p_r, prefix, plen < 0 ? 128 : ae == 1 ? plen + 96 : plen);
127 return ret;
128}
129
130static void
131parse_update_subtlv(const unsigned char *a, int alen,
132 unsigned char *channels)
133{
134 int type, len, i = 0;
135
136 while(i < alen) {
137 type = a[i];
138 if(type == SUBTLV_PAD1) {
139 i++;
140 continue;
141 }
142
143 if(i + 1 > alen) {
5b003f31 144 flog_err(EC_BABEL_PACKET, "Received truncated attributes.");
ca10883e
DS		 145 return;
146 }
147 len = a[i + 1];
148 if(i + len > alen) {
5b003f31 149 flog_err(EC_BABEL_PACKET, "Received truncated attributes.");
ca10883e
DS		 150 return;
151 }
152
153 if(type == SUBTLV_PADN) {
154 /* Nothing. */
155 } else if(type == SUBTLV_DIVERSITY) {
156 if(len > DIVERSITY_HOPS) {
5b003f31 157 flog_err(EC_BABEL_PACKET,
e33b116c
DS		 158 "Received overlong channel information (%d > %d).n",
159 len, DIVERSITY_HOPS);
ca10883e
DS		 160 len = DIVERSITY_HOPS;
161 }
162 if(memchr(a + i + 2, 0, len) != NULL) {
163 /* 0 is reserved. */
5b003f31 164 flog_err(EC_BABEL_PACKET, "Channel information contains 0!");
ca10883e
DS		 165 return;
166 }
167 memset(channels, 0, DIVERSITY_HOPS);
168 memcpy(channels, a + i + 2, len);
169 } else {
170 debugf(BABEL_DEBUG_COMMON,
171 "Received unknown route attribute %d.", type);
172 }
173
174 i += len + 2;
175 }
176}
177
178static int
179parse_hello_subtlv(const unsigned char *a, int alen,
180 unsigned int *hello_send_us)
181{
182 int type, len, i = 0, ret = 0;
183
184 while(i < alen) {
185 type = a[0];
186 if(type == SUBTLV_PAD1) {
187 i++;
188 continue;
189 }
190
191 if(i + 1 > alen) {
5b003f31 192 flog_err(EC_BABEL_PACKET,
e33b116c 193 "Received truncated sub-TLV on Hello message.");
ca10883e
DS		 194 return -1;
195 }
196 len = a[i + 1];
197 if(i + len > alen) {
5b003f31 198 flog_err(EC_BABEL_PACKET,
e33b116c 199 "Received truncated sub-TLV on Hello message.");
ca10883e
DS		 200 return -1;
201 }
202
203 if(type == SUBTLV_PADN) {
204 /* Nothing to do. */
205 } else if(type == SUBTLV_TIMESTAMP) {
206 if(len >= 4) {
207 DO_NTOHL(*hello_send_us, a + i + 2);
208 ret = 1;
209 } else {
5b003f31 210 flog_err(EC_BABEL_PACKET,
e33b116c 211 "Received incorrect RTT sub-TLV on Hello message.");
ca10883e
DS		 212 }
213 } else {
214 debugf(BABEL_DEBUG_COMMON,
215 "Received unknown Hello sub-TLV type %d.", type);
216 }
217
218 i += len + 2;
219 }
220 return ret;
221}
222
223static int
224parse_ihu_subtlv(const unsigned char *a, int alen,
225 unsigned int *hello_send_us,
226 unsigned int *hello_rtt_receive_time)
227{
228 int type, len, i = 0, ret = 0;
229
230 while(i < alen) {
231 type = a[0];
232 if(type == SUBTLV_PAD1) {
233 i++;
234 continue;
235 }
236
237 if(i + 1 > alen) {
5b003f31 238 flog_err(EC_BABEL_PACKET,
e33b116c 239 "Received truncated sub-TLV on IHU message.");
ca10883e
DS		 240 return -1;
241 }
242 len = a[i + 1];
243 if(i + len > alen) {
5b003f31 244 flog_err(EC_BABEL_PACKET,
e33b116c 245 "Received truncated sub-TLV on IHU message.");
ca10883e
DS		 246 return -1;
247 }
248
249 if(type == SUBTLV_PADN) {
250 /* Nothing to do. */
251 } else if(type == SUBTLV_TIMESTAMP) {
252 if(len >= 8) {
253 DO_NTOHL(*hello_send_us, a + i + 2);
254 DO_NTOHL(*hello_rtt_receive_time, a + i + 6);
255 ret = 1;
256 }
257 else {
5b003f31 258 flog_err(EC_BABEL_PACKET,
e33b116c 259 "Received incorrect RTT sub-TLV on IHU message.");
ca10883e
DS		 260 }
261 } else {
262 debugf(BABEL_DEBUG_COMMON,
263 "Received unknown IHU sub-TLV type %d.", type);
264 }
265
266 i += len + 2;
267 }
268 return ret;
269}
270
271static int
272network_address(int ae, const unsigned char *a, unsigned int len,
273 unsigned char *a_r)
274{
275 return network_prefix(ae, -1, 0, a, NULL, len, a_r);
276}
277
278static int
279channels_len(unsigned char *channels)
280{
281 unsigned char *p = memchr(channels, 0, DIVERSITY_HOPS);
282 return p ? (p - channels) : DIVERSITY_HOPS;
283}
284
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. */
288static int
289babel_packet_examin(const unsigned char *packet, int packetlen)
290{
291 unsigned i = 0, bodylen;
292 const unsigned char *message;
293 unsigned char type, len;
294
295 if(packetlen < 4 || packet[0] != 42 || packet[1] != 2)
296 return 1;
297 DO_NTOHS(bodylen, packet + 2);
298 while (i < bodylen){
299 message = packet + 4 + i;
300 type = message[0];
301 if(type == MESSAGE_PAD1) {
302 i++;
303 continue;
304 }
305 if(i + 1 > bodylen) {
306 debugf(BABEL_DEBUG_COMMON,"Received truncated message.");
307 return 1;
308 }
309 len = message[1];
310 if(i + len > bodylen) {
311 debugf(BABEL_DEBUG_COMMON,"Received truncated message.");
312 return 1;
313 }
314 /* not Pad1 */
315 if(type <= MESSAGE_MAX && tlv_min_length[type] && len < tlv_min_length[type]) {
316 debugf(BABEL_DEBUG_COMMON,"Undersized %u TLV", type);
317 return 1;
318 }
319 i += len + 2;
320 }
321 return 0;
322}
323
324void
325parse_packet(const unsigned char *from, struct interface *ifp,
326 const unsigned char *packet, int packetlen)
327{
328 int i;
329 const unsigned char *message;
330 unsigned char type, len;
331 int bodylen;
332 struct neighbour *neigh;
333 int have_router_id = 0, have_v4_prefix = 0, have_v6_prefix = 0,
334 have_v4_nh = 0, have_v6_nh = 0;
335 unsigned char router_id[8], v4_prefix[16], v6_prefix[16],
336 v4_nh[16], v6_nh[16];
337 int have_hello_rtt = 0;
338 /* Content of the RTT sub-TLV on IHU messages. */
339 unsigned int hello_send_us = 0, hello_rtt_receive_time = 0;
340 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
341
342 if(babel_ifp->flags & BABEL_IF_TIMESTAMPS) {
343 /* We want to track exactly when we received this packet. */
344 gettime(&babel_now);
345 }
346
347 if(!linklocal(from)) {
5b003f31 348 flog_err(EC_BABEL_PACKET,
e33b116c
DS		 349 "Received packet from non-local address %s.",
350 format_address(from));
ca10883e
DS		 351 return;
352 }
353
354 if (babel_packet_examin (packet, packetlen)) {
5b003f31 355 flog_err(EC_BABEL_PACKET,
e33b116c
DS		 356 "Received malformed packet on %s from %s.",
357 ifp->name, format_address(from));
ca10883e
DS		 358 return;
359 }
360
361 neigh = find_neighbour(from, ifp);
362 if(neigh == NULL) {
5b003f31 363 flog_err(EC_BABEL_PACKET, "Couldn't allocate neighbour.");
ca10883e
DS		 364 return;
365 }
366
367 DO_NTOHS(bodylen, packet + 2);
368
369 if(bodylen + 4 > packetlen) {
5b003f31 370 flog_err(EC_BABEL_PACKET, "Received truncated packet (%d + 4 > %d).",
ca10883e
DS		 371 bodylen, packetlen);
372 bodylen = packetlen - 4;
373 }
374
375 i = 0;
376 while(i < bodylen) {
377 message = packet + 4 + i;
378 type = message[0];
379 if(type == MESSAGE_PAD1) {
380 debugf(BABEL_DEBUG_COMMON,"Received pad1 from %s on %s.",
381 format_address(from), ifp->name);
382 i++;
383 continue;
384 }
385 len = message[1];
386
387 if(type == MESSAGE_PADN) {
388 debugf(BABEL_DEBUG_COMMON,"Received pad%d from %s on %s.",
389 len, format_address(from), ifp->name);
390 } else if(type == MESSAGE_ACK_REQ) {
391 unsigned short nonce, interval;
392 DO_NTOHS(nonce, message + 4);
393 DO_NTOHS(interval, message + 6);
394 debugf(BABEL_DEBUG_COMMON,"Received ack-req (%04X %d) from %s on %s.",
395 nonce, interval, format_address(from), ifp->name);
396 send_ack(neigh, nonce, interval);
397 } else if(type == MESSAGE_ACK) {
398 debugf(BABEL_DEBUG_COMMON,"Received ack from %s on %s.",
399 format_address(from), ifp->name);
400 /* Nothing right now */
401 } else if(type == MESSAGE_HELLO) {
402 unsigned short seqno, interval;
403 int changed;
a97986ff 404 unsigned int timestamp = 0;
ca10883e
DS		 405 DO_NTOHS(seqno, message + 4);
406 DO_NTOHS(interval, message + 6);
407 debugf(BABEL_DEBUG_COMMON,"Received hello %d (%d) from %s on %s.",
408 seqno, interval,
409 format_address(from), ifp->name);
410 changed = update_neighbour(neigh, seqno, interval);
411 update_neighbour_metric(neigh, changed);
412 if(interval > 0)
413 /* Multiply by 3/2 to allow hellos to expire. */
414 schedule_neighbours_check(interval * 15, 0);
415 /* Sub-TLV handling. */
416 if(len > 8) {
417 if(parse_hello_subtlv(message + 8, len - 6, &timestamp) > 0) {
418 neigh->hello_send_us = timestamp;
419 neigh->hello_rtt_receive_time = babel_now;
420 have_hello_rtt = 1;
421 }
422 }
423 } else if(type == MESSAGE_IHU) {
424 unsigned short txcost, interval;
425 unsigned char address[16];
426 int rc;
427 DO_NTOHS(txcost, message + 4);
428 DO_NTOHS(interval, message + 6);
429 rc = network_address(message[2], message + 8, len - 6, address);
430 if(rc < 0) goto fail;
431 debugf(BABEL_DEBUG_COMMON,"Received ihu %d (%d) from %s on %s for %s.",
432 txcost, interval,
433 format_address(from), ifp->name,
434 format_address(address));
435 if(message[2] == 0 || is_interface_ll_address(ifp, address)) {
436 int changed = txcost != neigh->txcost;
437 neigh->txcost = txcost;
438 neigh->ihu_time = babel_now;
439 neigh->ihu_interval = interval;
440 update_neighbour_metric(neigh, changed);
441 if(interval > 0)
442 /* Multiply by 3/2 to allow neighbours to expire. */
443 schedule_neighbours_check(interval * 45, 0);
444 /* RTT sub-TLV. */
445 if(len > 10 + rc)
446 parse_ihu_subtlv(message + 8 + rc, len - 6 - rc,
447 &hello_send_us, &hello_rtt_receive_time);
448 }
449 } else if(type == MESSAGE_ROUTER_ID) {
450 memcpy(router_id, message + 4, 8);
451 have_router_id = 1;
452 debugf(BABEL_DEBUG_COMMON,"Received router-id %s from %s on %s.",
453 format_eui64(router_id), format_address(from), ifp->name);
454 } else if(type == MESSAGE_NH) {
455 unsigned char nh[16];
456 int rc;
457 rc = network_address(message[2], message + 4, len - 2,
458 nh);
459 if(rc < 0) {
460 have_v4_nh = 0;
461 have_v6_nh = 0;
462 goto fail;
463 }
464 debugf(BABEL_DEBUG_COMMON,"Received nh %s (%d) from %s on %s.",
465 format_address(nh), message[2],
466 format_address(from), ifp->name);
467 if(message[2] == 1) {
468 memcpy(v4_nh, nh, 16);
469 have_v4_nh = 1;
470 } else {
471 memcpy(v6_nh, nh, 16);
472 have_v6_nh = 1;
473 }
474 } else if(type == MESSAGE_UPDATE) {
475 unsigned char prefix[16], *nh;
476 unsigned char plen;
477 unsigned char channels[DIVERSITY_HOPS];
478 unsigned short interval, seqno, metric;
479 int rc, parsed_len;
480 DO_NTOHS(interval, message + 6);
481 DO_NTOHS(seqno, message + 8);
482 DO_NTOHS(metric, message + 10);
483 if(message[5] == 0 ||
484 (message[2] == 1 ? have_v4_prefix : have_v6_prefix))
485 rc = network_prefix(message[2], message[4], message[5],
486 message + 12,
487 message[2] == 1 ? v4_prefix : v6_prefix,
488 len - 10, prefix);
489 else
490 rc = -1;
491 if(rc < 0) {
492 if(message[3] & 0x80)
493 have_v4_prefix = have_v6_prefix = 0;
494 goto fail;
495 }
496 parsed_len = 10 + rc;
497
498 plen = message[4] + (message[2] == 1 ? 96 : 0);
499
500 if(message[3] & 0x80) {
501 if(message[2] == 1) {
502 memcpy(v4_prefix, prefix, 16);
503 have_v4_prefix = 1;
504 } else {
505 memcpy(v6_prefix, prefix, 16);
506 have_v6_prefix = 1;
507 }
508 }
509 if(message[3] & 0x40) {
510 if(message[2] == 1) {
511 memset(router_id, 0, 4);
512 memcpy(router_id + 4, prefix + 12, 4);
513 } else {
514 memcpy(router_id, prefix + 8, 8);
515 }
516 have_router_id = 1;
517 }
518 if(!have_router_id && message[2] != 0) {
5b003f31 519 flog_err(EC_BABEL_PACKET,
e33b116c 520 "Received prefix with no router id.");
ca10883e
DS		 521 goto fail;
522 }
523 debugf(BABEL_DEBUG_COMMON,"Received update%s%s for %s from %s on %s.",
524 (message[3] & 0x80) ? "/prefix" : "",
525 (message[3] & 0x40) ? "/id" : "",
526 format_prefix(prefix, plen),
527 format_address(from), ifp->name);
528
529 if(message[2] == 0) {
530 if(metric < 0xFFFF) {
5b003f31 531 flog_err(EC_BABEL_PACKET,
e33b116c 532 "Received wildcard update with finite metric.");
ca10883e
DS		 533 goto done;
534 }
535 retract_neighbour_routes(neigh);
536 goto done;
537 } else if(message[2] == 1) {
538 if(!have_v4_nh)
539 goto fail;
540 nh = v4_nh;
541 } else if(have_v6_nh) {
542 nh = v6_nh;
543 } else {
544 nh = neigh->address;
545 }
546
547 if(message[2] == 1) {
548 if(!babel_get_if_nfo(ifp)->ipv4)
549 goto done;
550 }
551
552 if((babel_get_if_nfo(ifp)->flags & BABEL_IF_FARAWAY)) {
553 channels[0] = 0;
554 } else {
555 /* This will be overwritten by parse_update_subtlv below. */
556 if(metric < 256) {
557 /* Assume non-interfering (wired) link. */
558 channels[0] = 0;
559 } else {
560 /* Assume interfering. */
561 channels[0] = BABEL_IF_CHANNEL_INTERFERING;
562 channels[1] = 0;
563 }
564
565 if(parsed_len < len)
566 parse_update_subtlv(message + 2 + parsed_len,
567 len - parsed_len, channels);
568 }
569
570 update_route(router_id, prefix, plen, seqno, metric, interval,
571 neigh, nh,
572 channels, channels_len(channels));
573 } else if(type == MESSAGE_REQUEST) {
574 unsigned char prefix[16], plen;
575 int rc;
576 rc = network_prefix(message[2], message[3], 0,
577 message + 4, NULL, len - 2, prefix);
578 if(rc < 0) goto fail;
579 plen = message[3] + (message[2] == 1 ? 96 : 0);
580 debugf(BABEL_DEBUG_COMMON,"Received request for %s from %s on %s.",
581 message[2] == 0 ? "any" : format_prefix(prefix, plen),
582 format_address(from), ifp->name);
583 if(message[2] == 0) {
584 struct babel_interface *neigh_ifp =babel_get_if_nfo(neigh->ifp);
585 /* If a neighbour is requesting a full route dump from us,
586 we might as well send it an IHU. */
587 send_ihu(neigh, NULL);
588 /* Since nodes send wildcard requests on boot, booting
589 a large number of nodes at the same time may cause an
590 update storm. Ignore a wildcard request that happens
591 shortly after we sent a full update. */
592 if(neigh_ifp->last_update_time <
593 (time_t)(babel_now.tv_sec -
594 MAX(neigh_ifp->hello_interval / 100, 1)))
595 send_update(neigh->ifp, 0, NULL, 0);
596 } else {
597 send_update(neigh->ifp, 0, prefix, plen);
598 }
599 } else if(type == MESSAGE_MH_REQUEST) {
600 unsigned char prefix[16], plen;
601 unsigned short seqno;
602 int rc;
603 DO_NTOHS(seqno, message + 4);
604 rc = network_prefix(message[2], message[3], 0,
605 message + 16, NULL, len - 14, prefix);
606 if(rc < 0) goto fail;
607 plen = message[3] + (message[2] == 1 ? 96 : 0);
608 debugf(BABEL_DEBUG_COMMON,"Received request (%d) for %s from %s on %s (%s, %d).",
609 message[6],
610 format_prefix(prefix, plen),
611 format_address(from), ifp->name,
612 format_eui64(message + 8), seqno);
613 handle_request(neigh, prefix, plen, message[6],
614 seqno, message + 8);
615 } else {
616 debugf(BABEL_DEBUG_COMMON,"Received unknown packet type %d from %s on %s.",
617 type, format_address(from), ifp->name);
618 }
619 done:
620 i += len + 2;
621 continue;
622
623 fail:
5b003f31 624 flog_err(EC_BABEL_PACKET,
e33b116c
DS		 625 "Couldn't parse packet (%d, %d) from %s on %s.",
626 message[0], message[1], format_address(from), ifp->name);
ca10883e
DS		 627 goto done;
628 }
629
630 /* We can calculate the RTT to this neighbour. */
631 if(have_hello_rtt && hello_send_us && hello_rtt_receive_time) {
632 int remote_waiting_us, local_waiting_us;
633 unsigned int rtt, smoothed_rtt;
634 unsigned int old_rttcost;
635 int changed = 0;
636 remote_waiting_us = neigh->hello_send_us - hello_rtt_receive_time;
637 local_waiting_us = time_us(neigh->hello_rtt_receive_time) -
638 hello_send_us;
639
640 /* Sanity checks (validity window of 10 minutes). */
641 if(remote_waiting_us < 0 || local_waiting_us < 0 ||
642 remote_waiting_us > 600000000 || local_waiting_us > 600000000)
643 return;
644
645 rtt = MAX(0, local_waiting_us - remote_waiting_us);
646 debugf(BABEL_DEBUG_COMMON, "RTT to %s on %s sample result: %d us.\n",
647 format_address(from), ifp->name, rtt);
648
649 old_rttcost = neighbour_rttcost(neigh);
650 if (valid_rtt(neigh)) {
651 /* Running exponential average. */
652 smoothed_rtt = (babel_ifp->rtt_decay * rtt +
653 (256 - babel_ifp->rtt_decay) * neigh->rtt);
654 /* Rounding (up or down) to get closer to the sample. */
655 neigh->rtt = (neigh->rtt >= rtt) ? smoothed_rtt / 256 :
656 (smoothed_rtt + 255) / 256;
657 } else {
658 /* We prefer to be conservative with new neighbours
659 (higher RTT) */
660 assert(rtt <= 0x7FFFFFFF);
661 neigh->rtt = 2*rtt;
662 }
663 changed = (neighbour_rttcost(neigh) == old_rttcost ? 0 : 1);
664 update_neighbour_metric(neigh, changed);
665 neigh->rtt_time = babel_now;
666 }
667 return;
668}
669
670/* Under normal circumstances, there are enough moderation mechanisms
671 elsewhere in the protocol to make sure that this last-ditch check
672 should never trigger. But I'm superstitious. */
673
674static int
675check_bucket(struct interface *ifp)
676{
677 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
d11c6941 678 if(babel_ifp->bucket == 0) {
ca10883e
DS		 679 int seconds = babel_now.tv_sec - babel_ifp->bucket_time;
680 if(seconds > 0) {
681 babel_ifp->bucket = MIN(BUCKET_TOKENS_MAX,
682 seconds * BUCKET_TOKENS_PER_SEC);
683 }
684 /* Reset bucket time unconditionally, in case clock is stepped. */
685 babel_ifp->bucket_time = babel_now.tv_sec;
686 }
687
688 if(babel_ifp->bucket > 0) {
689 babel_ifp->bucket--;
690 return 1;
691 } else {
692 return 0;
693 }
694}
695
696static int
697fill_rtt_message(struct interface *ifp)
698{
699 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
700 if((babel_ifp->flags & BABEL_IF_TIMESTAMPS) &&
701 (babel_ifp->buffered_hello >= 0)) {
702 if(babel_ifp->sendbuf[babel_ifp->buffered_hello + 8] == SUBTLV_PADN &&
703 babel_ifp->sendbuf[babel_ifp->buffered_hello + 9] == 4) {
704 unsigned int time;
705 /* Change the type of sub-TLV. */
706 babel_ifp->sendbuf[babel_ifp->buffered_hello + 8] =
707 SUBTLV_TIMESTAMP;
708 gettime(&babel_now);
709 time = time_us(babel_now);
710 DO_HTONL(babel_ifp->sendbuf + babel_ifp->buffered_hello + 10, time);
711 return 1;
712 } else {
5b003f31 713 flog_err(EC_BABEL_PACKET, "No space left for timestamp sub-TLV "
ca10883e
DS		 714 "(this shouldn't happen)");
715 return -1;
716 }
717 }
718 return 0;
719}
720
721void
722flushbuf(struct interface *ifp)
723{
724 int rc;
725 struct sockaddr_in6 sin6;
726 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
727
728 assert(babel_ifp->buffered <= babel_ifp->bufsize);
729
730 flushupdates(ifp);
731
732 if(babel_ifp->buffered > 0) {
733 debugf(BABEL_DEBUG_COMMON," (flushing %d buffered bytes on %s)",
734 babel_ifp->buffered, ifp->name);
735 if(check_bucket(ifp)) {
736 memset(&sin6, 0, sizeof(sin6));
737 sin6.sin6_family = AF_INET6;
738 memcpy(&sin6.sin6_addr, protocol_group, 16);
739 sin6.sin6_port = htons(protocol_port);
740 sin6.sin6_scope_id = ifp->ifindex;
741 DO_HTONS(packet_header + 2, babel_ifp->buffered);
742 fill_rtt_message(ifp);
743 rc = babel_send(protocol_socket,
744 packet_header, sizeof(packet_header),
745 babel_ifp->sendbuf, babel_ifp->buffered,
746 (struct sockaddr*)&sin6, sizeof(sin6));
747 if(rc < 0)
5b003f31 748 flog_err(EC_BABEL_PACKET, "send: %s", safe_strerror(errno));
ca10883e 749 } else {
5b003f31 750 flog_err(EC_BABEL_PACKET,
e33b116c
DS		 751 "Warning: bucket full, dropping packet to %s.",
752 ifp->name);
ca10883e
DS		 753 }
754 }
755 VALGRIND_MAKE_MEM_UNDEFINED(babel_ifp->sendbuf, babel_ifp->bufsize);
756 babel_ifp->buffered = 0;
757 babel_ifp->buffered_hello = -1;
758 babel_ifp->have_buffered_id = 0;
759 babel_ifp->have_buffered_nh = 0;
760 babel_ifp->have_buffered_prefix = 0;
761 babel_ifp->flush_timeout.tv_sec = 0;
762 babel_ifp->flush_timeout.tv_usec = 0;
763}
764
765static void
766schedule_flush(struct interface *ifp)
767{
768 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
769 unsigned msecs = jitter(babel_ifp, 0);
770 if(babel_ifp->flush_timeout.tv_sec != 0 &&
771 timeval_minus_msec(&babel_ifp->flush_timeout, &babel_now) < msecs)
772 return;
773 set_timeout(&babel_ifp->flush_timeout, msecs);
774}
775
776static void
777schedule_flush_now(struct interface *ifp)
778{
779 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
780 /* Almost now */
781 unsigned msecs = roughly(10);
782 if(babel_ifp->flush_timeout.tv_sec != 0 &&
783 timeval_minus_msec(&babel_ifp->flush_timeout, &babel_now) < msecs)
784 return;
785 set_timeout(&babel_ifp->flush_timeout, msecs);
786}
787
788static void
789schedule_unicast_flush(unsigned msecs)
790{
791 if(!unicast_neighbour)
792 return;
793 if(unicast_flush_timeout.tv_sec != 0 &&
794 timeval_minus_msec(&unicast_flush_timeout, &babel_now) < msecs)
795 return;
796 unicast_flush_timeout.tv_usec = (babel_now.tv_usec + msecs * 1000) %1000000;
797 unicast_flush_timeout.tv_sec =
798 babel_now.tv_sec + (babel_now.tv_usec / 1000 + msecs) / 1000;
799}
800
801static void
802ensure_space(struct interface *ifp, int space)
803{
804 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
805 if(babel_ifp->bufsize - babel_ifp->buffered < space)
806 flushbuf(ifp);
807}
808
809static void
810start_message(struct interface *ifp, int type, int len)
811{
812 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
813 if(babel_ifp->bufsize - babel_ifp->buffered < len + 2)
814 flushbuf(ifp);
815 babel_ifp->sendbuf[babel_ifp->buffered++] = type;
816 babel_ifp->sendbuf[babel_ifp->buffered++] = len;
817}
818
819static void
820end_message(struct interface *ifp, int type, int bytes)
821{
822 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
823 assert(babel_ifp->buffered >= bytes + 2 &&
824 babel_ifp->sendbuf[babel_ifp->buffered - bytes - 2] == type &&
825 babel_ifp->sendbuf[babel_ifp->buffered - bytes - 1] == bytes);
826 schedule_flush(ifp);
827}
828
829static void
830accumulate_byte(struct interface *ifp, unsigned char value)
831{
832 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
833 babel_ifp->sendbuf[babel_ifp->buffered++] = value;
834}
835
836static void
837accumulate_short(struct interface *ifp, unsigned short value)
838{
839 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
840 DO_HTONS(babel_ifp->sendbuf + babel_ifp->buffered, value);
841 babel_ifp->buffered += 2;
842}
843
844static void
845accumulate_int(struct interface *ifp, unsigned int value)
846{
847 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
848 DO_HTONL(babel_ifp->sendbuf + babel_ifp->buffered, value);
849 babel_ifp->buffered += 4;
850}
851
852static void
853accumulate_bytes(struct interface *ifp,
854 const unsigned char *value, unsigned len)
855{
856 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
857 memcpy(babel_ifp->sendbuf + babel_ifp->buffered, value, len);
858 babel_ifp->buffered += len;
859}
860
861static int
862start_unicast_message(struct neighbour *neigh, int type, int len)
863{
864 if(unicast_neighbour) {
865 if(neigh != unicast_neighbour ||
866 unicast_buffered + len + 2 >=
867 MIN(UNICAST_BUFSIZE, babel_get_if_nfo(neigh->ifp)->bufsize))
868 flush_unicast(0);
869 }
870 if(!unicast_buffer)
871 unicast_buffer = malloc(UNICAST_BUFSIZE);
872 if(!unicast_buffer) {
5b003f31 873 flog_err(EC_BABEL_MEMORY, "malloc(unicast_buffer): %s",
e33b116c 874 safe_strerror(errno));
ca10883e
DS		 875 return -1;
876 }
877
878 unicast_neighbour = neigh;
879
880 unicast_buffer[unicast_buffered++] = type;
881 unicast_buffer[unicast_buffered++] = len;
882 return 1;
883}
884
885static void
886end_unicast_message(struct neighbour *neigh, int type, int bytes)
887{
888 assert(unicast_neighbour == neigh && unicast_buffered >= bytes + 2 &&
889 unicast_buffer[unicast_buffered - bytes - 2] == type &&
890 unicast_buffer[unicast_buffered - bytes - 1] == bytes);
891 schedule_unicast_flush(jitter(babel_get_if_nfo(neigh->ifp), 0));
892}
893
894static void
895accumulate_unicast_byte(struct neighbour *neigh, unsigned char value)
896{
897 unicast_buffer[unicast_buffered++] = value;
898}
899
900static void
901accumulate_unicast_short(struct neighbour *neigh, unsigned short value)
902{
903 DO_HTONS(unicast_buffer + unicast_buffered, value);
904 unicast_buffered += 2;
905}
906
907static void
908accumulate_unicast_int(struct neighbour *neigh, unsigned int value)
909{
910 DO_HTONL(unicast_buffer + unicast_buffered, value);
911 unicast_buffered += 4;
912}
913
914static void
915accumulate_unicast_bytes(struct neighbour *neigh,
916 const unsigned char *value, unsigned len)
917{
918 memcpy(unicast_buffer + unicast_buffered, value, len);
919 unicast_buffered += len;
920}
921
922void
923send_ack(struct neighbour *neigh, unsigned short nonce, unsigned short interval)
924{
925 int rc;
926 debugf(BABEL_DEBUG_COMMON,"Sending ack (%04x) to %s on %s.",
927 nonce, format_address(neigh->address), neigh->ifp->name);
928 rc = start_unicast_message(neigh, MESSAGE_ACK, 2); if(rc < 0) return;
929 accumulate_unicast_short(neigh, nonce);
930 end_unicast_message(neigh, MESSAGE_ACK, 2);
931 /* Roughly yields a value no larger than 3/2, so this meets the deadline */
932 schedule_unicast_flush(roughly(interval * 6));
933}
934
935void
936send_hello_noupdate(struct interface *ifp, unsigned interval)
937{
938 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
939 /* This avoids sending multiple hellos in a single packet, which breaks
940 link quality estimation. */
941 if(babel_ifp->buffered_hello >= 0)
942 flushbuf(ifp);
943
944 babel_ifp->hello_seqno = seqno_plus(babel_ifp->hello_seqno, 1);
945 set_timeout(&babel_ifp->hello_timeout, babel_ifp->hello_interval);
946
947 if(!if_up(ifp))
948 return;
949
950 debugf(BABEL_DEBUG_COMMON,"Sending hello %d (%d) to %s.",
951 babel_ifp->hello_seqno, interval, ifp->name);
952
953 start_message(ifp, MESSAGE_HELLO,
954 (babel_ifp->flags & BABEL_IF_TIMESTAMPS) ? 12 : 6);
955 babel_ifp->buffered_hello = babel_ifp->buffered - 2;
956 accumulate_short(ifp, 0);
957 accumulate_short(ifp, babel_ifp->hello_seqno);
958 accumulate_short(ifp, interval > 0xFFFF ? 0xFFFF : interval);
959 if(babel_ifp->flags & BABEL_IF_TIMESTAMPS) {
960 /* Sub-TLV containing the local time of emission. We use a
961 Pad4 sub-TLV, which we'll fill just before sending. */
962 accumulate_byte(ifp, SUBTLV_PADN);
963 accumulate_byte(ifp, 4);
964 accumulate_int(ifp, 0);
965 }
966 end_message(ifp, MESSAGE_HELLO,
967 (babel_ifp->flags & BABEL_IF_TIMESTAMPS) ? 12 : 6);
968}
969
970void
971send_hello(struct interface *ifp)
972{
973 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
974 send_hello_noupdate(ifp, (babel_ifp->hello_interval + 9) / 10);
975 /* Send full IHU every 3 hellos, and marginal IHU each time */
976 if(babel_ifp->hello_seqno % 3 == 0)
977 send_ihu(NULL, ifp);
978 else
979 send_marginal_ihu(ifp);
980}
981
982void
983flush_unicast(int dofree)
984{
985 struct sockaddr_in6 sin6;
986 int rc;
987
988 if(unicast_buffered == 0)
989 goto done;
990
991 if(!if_up(unicast_neighbour->ifp))
992 goto done;
993
994 /* Preserve ordering of messages */
995 flushbuf(unicast_neighbour->ifp);
996
997 if(check_bucket(unicast_neighbour->ifp)) {
998 memset(&sin6, 0, sizeof(sin6));
999 sin6.sin6_family = AF_INET6;
1000 memcpy(&sin6.sin6_addr, unicast_neighbour->address, 16);
1001 sin6.sin6_port = htons(protocol_port);
1002 sin6.sin6_scope_id = unicast_neighbour->ifp->ifindex;
1003 DO_HTONS(packet_header + 2, unicast_buffered);
1004 fill_rtt_message(unicast_neighbour->ifp);
1005 rc = babel_send(protocol_socket,
1006 packet_header, sizeof(packet_header),
1007 unicast_buffer, unicast_buffered,
1008 (struct sockaddr*)&sin6, sizeof(sin6));
1009 if(rc < 0)
5b003f31 1010 flog_err(EC_BABEL_PACKET, "send(unicast): %s",
e33b116c 1011 safe_strerror(errno));
ca10883e 1012 } else {
5b003f31 1013 flog_err(EC_BABEL_PACKET,
e33b116c
DS		 1014 "Warning: bucket full, dropping unicast packet to %s if %s.",
1015 format_address(unicast_neighbour->address),
1016 unicast_neighbour->ifp->name);
ca10883e
DS		 1017 }
1018
1019 done:
1020 VALGRIND_MAKE_MEM_UNDEFINED(unicast_buffer, UNICAST_BUFSIZE);
1021 unicast_buffered = 0;
1022 if(dofree && unicast_buffer) {
1023 free(unicast_buffer);
1024 unicast_buffer = NULL;
1025 }
1026 unicast_neighbour = NULL;
1027 unicast_flush_timeout.tv_sec = 0;
1028 unicast_flush_timeout.tv_usec = 0;
1029}
1030
1031static void
1032really_send_update(struct interface *ifp,
1033 const unsigned char *id,
1034 const unsigned char *prefix, unsigned char plen,
1035 unsigned short seqno, unsigned short metric,
1036 unsigned char *channels, int channels_len)
1037{
1038 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
1039 int add_metric, v4, real_plen, omit = 0;
1040 const unsigned char *real_prefix;
1041 unsigned short flags = 0;
1042 int channels_size;
1043
1044 if(diversity_kind != DIVERSITY_CHANNEL)
1045 channels_len = -1;
1046
1047 channels_size = channels_len >= 0 ? channels_len + 2 : 0;
1048
1049 if(!if_up(ifp))
1050 return;
1051
1052 add_metric = output_filter(id, prefix, plen, ifp->ifindex);
1053 if(add_metric >= INFINITY)
1054 return;
1055
1056 metric = MIN(metric + add_metric, INFINITY);
1057 /* Worst case */
1058 ensure_space(ifp, 20 + 12 + 28);
1059
1060 v4 = plen >= 96 && v4mapped(prefix);
1061
1062 if(v4) {
1063 if(!babel_ifp->ipv4)
1064 return;
1065 if(!babel_ifp->have_buffered_nh ||
1066 memcmp(babel_ifp->buffered_nh, babel_ifp->ipv4, 4) != 0) {
1067 start_message(ifp, MESSAGE_NH, 6);
1068 accumulate_byte(ifp, 1);
1069 accumulate_byte(ifp, 0);
1070 accumulate_bytes(ifp, babel_ifp->ipv4, 4);
1071 end_message(ifp, MESSAGE_NH, 6);
1072 memcpy(babel_ifp->buffered_nh, babel_ifp->ipv4, 4);
1073 babel_ifp->have_buffered_nh = 1;
1074 }
1075
1076 real_prefix = prefix + 12;
1077 real_plen = plen - 96;
1078 } else {
1079 if(babel_ifp->have_buffered_prefix) {
1080 while(omit < plen / 8 &&
1081 babel_ifp->buffered_prefix[omit] == prefix[omit])
1082 omit++;
1083 }
1084 if(!babel_ifp->have_buffered_prefix || plen >= 48)
1085 flags |= 0x80;
1086 real_prefix = prefix;
1087 real_plen = plen;
1088 }
1089
1090 if(!babel_ifp->have_buffered_id
1091 || memcmp(id, babel_ifp->buffered_id, 8) != 0) {
1092 if(real_plen == 128 && memcmp(real_prefix + 8, id, 8) == 0) {
1093 flags |= 0x40;
1094 } else {
1095 start_message(ifp, MESSAGE_ROUTER_ID, 10);
1096 accumulate_short(ifp, 0);
1097 accumulate_bytes(ifp, id, 8);
1098 end_message(ifp, MESSAGE_ROUTER_ID, 10);
1099 }
01b08f09 1100 memcpy(babel_ifp->buffered_id, id, sizeof(babel_ifp->buffered_id));
ca10883e
DS		 1101 babel_ifp->have_buffered_id = 1;
1102 }
1103
1104 start_message(ifp, MESSAGE_UPDATE, 10 + (real_plen + 7) / 8 - omit +
1105 channels_size);
1106 accumulate_byte(ifp, v4 ? 1 : 2);
1107 accumulate_byte(ifp, flags);
1108 accumulate_byte(ifp, real_plen);
1109 accumulate_byte(ifp, omit);
1110 accumulate_short(ifp, (babel_ifp->update_interval + 5) / 10);
1111 accumulate_short(ifp, seqno);
1112 accumulate_short(ifp, metric);
1113 accumulate_bytes(ifp, real_prefix + omit, (real_plen + 7) / 8 - omit);
1114 /* Note that an empty channels TLV is different from no such TLV. */
1115 if(channels_len >= 0) {
1116 accumulate_byte(ifp, 2);
1117 accumulate_byte(ifp, channels_len);
1118 accumulate_bytes(ifp, channels, channels_len);
1119 }
1120 end_message(ifp, MESSAGE_UPDATE, 10 + (real_plen + 7) / 8 - omit +
1121 channels_size);
1122
1123 if(flags & 0x80) {
1124 memcpy(babel_ifp->buffered_prefix, prefix, 16);
1125 babel_ifp->have_buffered_prefix = 1;
1126 }
1127}
1128
1129static int
1130compare_buffered_updates(const void *av, const void *bv)
1131{
1132 const struct buffered_update *a = av, *b = bv;
1133 int rc, v4a, v4b, ma, mb;
1134
1135 rc = memcmp(a->id, b->id, 8);
1136 if(rc != 0)
1137 return rc;
1138
1139 v4a = (a->plen >= 96 && v4mapped(a->prefix));
1140 v4b = (b->plen >= 96 && v4mapped(b->prefix));
1141
1142 if(v4a > v4b)
1143 return 1;
1144 else if(v4a < v4b)
1145 return -1;
1146
1147 ma = (!v4a && a->plen == 128 && memcmp(a->prefix + 8, a->id, 8) == 0);
1148 mb = (!v4b && b->plen == 128 && memcmp(b->prefix + 8, b->id, 8) == 0);
1149
1150 if(ma > mb)
1151 return -1;
1152 else if(mb > ma)
1153 return 1;
1154
1155 if(a->plen < b->plen)
1156 return 1;
1157 else if(a->plen > b->plen)
1158 return -1;
1159
1160 return memcmp(a->prefix, b->prefix, 16);
1161}
1162
1163void
1164flushupdates(struct interface *ifp)
1165{
1166 babel_interface_nfo *babel_ifp = NULL;
1167 struct xroute *xroute;
1168 struct babel_route *route;
1169 const unsigned char *last_prefix = NULL;
1170 unsigned char last_plen = 0xFF;
1171 int i;
1172
1173 if(ifp == NULL) {
f4e14fdb
RW		 1174 struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
1175 struct interface *ifp_aux;
1176 FOR_ALL_INTERFACES(vrf, ifp_aux)
ca10883e
DS		 1177 flushupdates(ifp_aux);
1178 return;
1179 }
1180
1181 babel_ifp = babel_get_if_nfo(ifp);
1182 if(babel_ifp->num_buffered_updates > 0) {
1183 struct buffered_update *b = babel_ifp->buffered_updates;
1184 int n = babel_ifp->num_buffered_updates;
1185
1186 babel_ifp->buffered_updates = NULL;
1187 babel_ifp->update_bufsize = 0;
1188 babel_ifp->num_buffered_updates = 0;
1189
1190 if(!if_up(ifp))
1191 goto done;
1192
1193 debugf(BABEL_DEBUG_COMMON," (flushing %d buffered updates on %s (%d))",
1194 n, ifp->name, ifp->ifindex);
1195
1196 /* In order to send fewer update messages, we want to send updates
1197 with the same router-id together, with IPv6 going out before IPv4. */
1198
1199 for(i = 0; i < n; i++) {
1200 route = find_installed_route(b[i].prefix, b[i].plen);
1201 if(route)
1202 memcpy(b[i].id, route->src->id, 8);
1203 else
1204 memcpy(b[i].id, myid, 8);
1205 }
1206
1207 qsort(b, n, sizeof(struct buffered_update), compare_buffered_updates);
1208
1209 for(i = 0; i < n; i++) {
1210 /* The same update may be scheduled multiple times before it is
1211 sent out. Since our buffer is now sorted, it is enough to
1212 compare with the previous update. */
1213
1214 if(last_prefix) {
1215 if(b[i].plen == last_plen &&
1216 memcmp(b[i].prefix, last_prefix, 16) == 0)
1217 continue;
1218 }
1219
1220 xroute = find_xroute(b[i].prefix, b[i].plen);
1221 route = find_installed_route(b[i].prefix, b[i].plen);
1222
1223 if(xroute && (!route || xroute->metric <= kernel_metric)) {
1224 really_send_update(ifp, myid,
1225 xroute->prefix, xroute->plen,
1226 myseqno, xroute->metric,
1227 NULL, 0);
1228 last_prefix = xroute->prefix;
1229 last_plen = xroute->plen;
1230 } else if(route) {
1231 unsigned char channels[DIVERSITY_HOPS];
1232 int chlen;
1233 struct interface *route_ifp = route->neigh->ifp;
1234 struct babel_interface *babel_route_ifp = NULL;
1235 unsigned short metric;
1236 unsigned short seqno;
1237
1238 seqno = route->seqno;
1239 metric =
1240 route_interferes(route, ifp) ?
1241 route_metric(route) :
1242 route_metric_noninterfering(route);
1243
1244 if(metric < INFINITY)
1245 satisfy_request(route->src->prefix, route->src->plen,
1246 seqno, route->src->id, ifp);
1247 if((babel_ifp->flags & BABEL_IF_SPLIT_HORIZON) &&
1248 route->neigh->ifp == ifp)
1249 continue;
1250
1251 babel_route_ifp = babel_get_if_nfo(route_ifp);
1252 if(babel_route_ifp->channel ==BABEL_IF_CHANNEL_NONINTERFERING) {
1253 memcpy(channels, route->channels, DIVERSITY_HOPS);
1254 } else {
1255 if(babel_route_ifp->channel == BABEL_IF_CHANNEL_UNKNOWN)
1256 channels[0] = BABEL_IF_CHANNEL_INTERFERING;
1257 else {
1258 assert(babel_route_ifp->channel > 0 &&
1259 babel_route_ifp->channel <= 255);
1260 channels[0] = babel_route_ifp->channel;
1261 }
1262 memcpy(channels + 1, route->channels, DIVERSITY_HOPS - 1);
1263 }
1264
1265 chlen = channels_len(channels);
1266 really_send_update(ifp, route->src->id,
1267 route->src->prefix,
1268 route->src->plen,
1269 seqno, metric,
1270 channels, chlen);
1271 update_source(route->src, seqno, metric);
1272 last_prefix = route->src->prefix;
1273 last_plen = route->src->plen;
1274 } else {
1275 /* There's no route for this prefix. This can happen shortly
1276 after an xroute has been retracted, so send a retraction. */
1277 really_send_update(ifp, myid, b[i].prefix, b[i].plen,
1278 myseqno, INFINITY, NULL, -1);
1279 }
1280 }
1281 schedule_flush_now(ifp);
1282 done:
1283 free(b);
1284 }
1285 babel_ifp->update_flush_timeout.tv_sec = 0;
1286 babel_ifp->update_flush_timeout.tv_usec = 0;
1287}
1288
1289static void
1290schedule_update_flush(struct interface *ifp, int urgent)
1291{
1292 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
1293 unsigned msecs;
1294 msecs = update_jitter(babel_ifp, urgent);
1295 if(babel_ifp->update_flush_timeout.tv_sec != 0 &&
1296 timeval_minus_msec(&babel_ifp->update_flush_timeout, &babel_now) < msecs)
1297 return;
1298 set_timeout(&babel_ifp->update_flush_timeout, msecs);
1299}
1300
1301static void
1302buffer_update(struct interface *ifp,
1303 const unsigned char *prefix, unsigned char plen)
1304{
1305 babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
1306 if(babel_ifp->num_buffered_updates > 0 &&
1307 babel_ifp->num_buffered_updates >= babel_ifp->update_bufsize)
1308 flushupdates(ifp);
1309
1310 if(babel_ifp->update_bufsize == 0) {
1311 int n;
1312 assert(babel_ifp->buffered_updates == NULL);
1313 /* Allocate enough space to hold a full update. Since the
1314 number of installed routes will grow over time, make sure we
1315 have enough space to send a full-ish frame. */
1316 n = installed_routes_estimate() + xroutes_estimate() + 4;
1317 n = MAX(n, babel_ifp->bufsize / 16);
1318 again:
1319 babel_ifp->buffered_updates = malloc(n *sizeof(struct buffered_update));
1320 if(babel_ifp->buffered_updates == NULL) {
5b003f31 1321 flog_err(EC_BABEL_MEMORY, "malloc(buffered_updates): %s",
e33b116c 1322 safe_strerror(errno));
ca10883e
DS		 1323 if(n > 4) {
1324 /* Try again with a tiny buffer. */
1325 n = 4;
1326 goto again;
1327 }
1328 return;
1329 }
1330 babel_ifp->update_bufsize = n;
1331 babel_ifp->num_buffered_updates = 0;
1332 }
1333
1334 memcpy(babel_ifp->buffered_updates[babel_ifp->num_buffered_updates].prefix,
1335 prefix, 16);
1336 babel_ifp->buffered_updates[babel_ifp->num_buffered_updates].plen = plen;
1337 babel_ifp->num_buffered_updates++;
1338}
1339
1340void
1341send_update(struct interface *ifp, int urgent,
1342 const unsigned char *prefix, unsigned char plen)
1343{
1344 babel_interface_nfo *babel_ifp = NULL;
1345
1346 if(ifp == NULL) {
f4e14fdb
RW		 1347 struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
1348 struct interface *ifp_aux;
ca10883e 1349 struct babel_route *route;
f4e14fdb 1350 FOR_ALL_INTERFACES(vrf, ifp_aux)
ca10883e
DS		 1351 send_update(ifp_aux, urgent, prefix, plen);
1352 if(prefix) {
1353 /* Since flushupdates only deals with non-wildcard interfaces, we
1354 need to do this now. */
1355 route = find_installed_route(prefix, plen);
1356 if(route && route_metric(route) < INFINITY)
1357 satisfy_request(prefix, plen, route->src->seqno, route->src->id,
1358 NULL);
1359 }
1360 return;
1361 }
1362
1363 if(!if_up(ifp))
1364 return;
1365
1366 babel_ifp = babel_get_if_nfo(ifp);
1367 if(prefix) {
1368 debugf(BABEL_DEBUG_COMMON,"Sending update to %s for %s.",
1369 ifp->name, format_prefix(prefix, plen));
1370 buffer_update(ifp, prefix, plen);
1371 } else {
1372 struct route_stream *routes = NULL;
1373 send_self_update(ifp);
1374 debugf(BABEL_DEBUG_COMMON,"Sending update to %s for any.", ifp->name);
1375 routes = route_stream(1);
1376 if(routes) {
1377 while(1) {
1378 struct babel_route *route = route_stream_next(routes);
1379 if(route == NULL)
1380 break;
1381 buffer_update(ifp, route->src->prefix, route->src->plen);
1382 }
1383 route_stream_done(routes);
1384 } else {
5b003f31 1385 flog_err(EC_BABEL_MEMORY, "Couldn't allocate route stream.");
ca10883e
DS		 1386 }
1387 set_timeout(&babel_ifp->update_timeout, babel_ifp->update_interval);
1388 babel_ifp->last_update_time = babel_now.tv_sec;
1389 }
1390 schedule_update_flush(ifp, urgent);
1391}
1392
1393void
1394send_update_resend(struct interface *ifp,
1395 const unsigned char *prefix, unsigned char plen)
1396{
1397 assert(prefix != NULL);
1398
1399 send_update(ifp, 1, prefix, plen);
1400 record_resend(RESEND_UPDATE, prefix, plen, 0, NULL, NULL, resend_delay);
1401}
1402
1403void
1404send_wildcard_retraction(struct interface *ifp)
1405{
1406 babel_interface_nfo *babel_ifp = NULL;
1407 if(ifp == NULL) {
f4e14fdb
RW		 1408 struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
1409 struct interface *ifp_aux;
1410 FOR_ALL_INTERFACES(vrf, ifp_aux)
ca10883e
DS		 1411 send_wildcard_retraction(ifp_aux);
1412 return;
1413 }
1414
1415 if(!if_up(ifp))
1416 return;
1417
1418 babel_ifp = babel_get_if_nfo(ifp);
1419 start_message(ifp, MESSAGE_UPDATE, 10);
1420 accumulate_byte(ifp, 0);
1421 accumulate_byte(ifp, 0x40);
1422 accumulate_byte(ifp, 0);
1423 accumulate_byte(ifp, 0);
1424 accumulate_short(ifp, 0xFFFF);
1425 accumulate_short(ifp, myseqno);
1426 accumulate_short(ifp, 0xFFFF);
1427 end_message(ifp, MESSAGE_UPDATE, 10);
1428
1429 babel_ifp->have_buffered_id = 0;
1430}
1431
1432void
1433update_myseqno()
1434{
1435 myseqno = seqno_plus(myseqno, 1);
1436}
1437
1438void
1439send_self_update(struct interface *ifp)
1440{
1441 struct xroute_stream *xroutes;
1442 if(ifp == NULL) {
f4e14fdb
RW		 1443 struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
1444 struct interface *ifp_aux;
1445 FOR_ALL_INTERFACES(vrf, ifp_aux) {
ca10883e
DS		 1446 if(!if_up(ifp_aux))
1447 continue;
1448 send_self_update(ifp_aux);
1449 }
1450 return;
1451 }
1452
1453 debugf(BABEL_DEBUG_COMMON,"Sending self update to %s.", ifp->name);
1454 xroutes = xroute_stream();
1455 if(xroutes) {
1456 while(1) {
1457 struct xroute *xroute = xroute_stream_next(xroutes);
1458 if(xroute == NULL) break;
1459 send_update(ifp, 0, xroute->prefix, xroute->plen);
1460 }
1461 xroute_stream_done(xroutes);
1462 } else {
5b003f31 1463 flog_err(EC_BABEL_MEMORY, "Couldn't allocate xroute stream.");
ca10883e
DS		 1464 }
1465}
1466
1467void
1468send_ihu(struct neighbour *neigh, struct interface *ifp)
1469{
1470 babel_interface_nfo *babel_ifp = NULL;
1471 int rxcost, interval;
1472 int ll;
1473 int send_rtt_data;
1474 int msglen;
1475
1476 if(neigh == NULL && ifp == NULL) {
f4e14fdb 1477 struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
ca10883e 1478 struct interface *ifp_aux;
f4e14fdb 1479 FOR_ALL_INTERFACES(vrf, ifp_aux) {
ca10883e
DS		 1480 if(if_up(ifp_aux))
1481 continue;
1482 send_ihu(NULL, ifp_aux);
1483 }
1484 return;
1485 }
1486
1487 if(neigh == NULL) {
1488 struct neighbour *ngh;
1489 FOR_ALL_NEIGHBOURS(ngh) {
1490 if(ngh->ifp == ifp)
1491 send_ihu(ngh, ifp);
1492 }
1493 return;
1494 }
1495
1496
1497 if(ifp && neigh->ifp != ifp)
1498 return;
1499
1500 ifp = neigh->ifp;
1501 babel_ifp = babel_get_if_nfo(ifp);
1502 if(!if_up(ifp))
1503 return;
1504
1505 rxcost = neighbour_rxcost(neigh);
1506 interval = (babel_ifp->hello_interval * 3 + 9) / 10;
1507
1508 /* Conceptually, an IHU is a unicast message. We usually send them as
1509 multicast, since this allows aggregation into a single packet and
1510 avoids an ARP exchange. If we already have a unicast message queued
1511 for this neighbour, however, we might as well piggyback the IHU. */
1512 debugf(BABEL_DEBUG_COMMON,"Sending %sihu %d on %s to %s.",
1513 unicast_neighbour == neigh ? "unicast " : "",
1514 rxcost,
1515 neigh->ifp->name,
1516 format_address(neigh->address));
1517
1518 ll = linklocal(neigh->address);
1519
1520 if((babel_ifp->flags & BABEL_IF_TIMESTAMPS) && neigh->hello_send_us
1521 /* Checks whether the RTT data is not too old to be sent. */
1522 && timeval_minus_msec(&babel_now,
1523 &neigh->hello_rtt_receive_time) < 1000000) {
1524 send_rtt_data = 1;
1525 } else {
1526 neigh->hello_send_us = 0;
1527 send_rtt_data = 0;
1528 }
1529
1530 /* The length depends on the format of the address, and then an
1531 optional 10-bytes sub-TLV for timestamps (used to compute a RTT). */
1532 msglen = (ll ? 14 : 22) + (send_rtt_data ? 10 : 0);
1533
1534 if(unicast_neighbour != neigh) {
1535 start_message(ifp, MESSAGE_IHU, msglen);
1536 accumulate_byte(ifp, ll ? 3 : 2);
1537 accumulate_byte(ifp, 0);
1538 accumulate_short(ifp, rxcost);
1539 accumulate_short(ifp, interval);
1540 if(ll)
1541 accumulate_bytes(ifp, neigh->address + 8, 8);
1542 else
1543 accumulate_bytes(ifp, neigh->address, 16);
1544 if (send_rtt_data) {
1545 accumulate_byte(ifp, SUBTLV_TIMESTAMP);
1546 accumulate_byte(ifp, 8);
1547 accumulate_int(ifp, neigh->hello_send_us);
1548 accumulate_int(ifp, time_us(neigh->hello_rtt_receive_time));
1549 }
1550 end_message(ifp, MESSAGE_IHU, msglen);
1551 } else {
1552 int rc;
1553 rc = start_unicast_message(neigh, MESSAGE_IHU, msglen);
1554 if(rc < 0) return;
1555 accumulate_unicast_byte(neigh, ll ? 3 : 2);
1556 accumulate_unicast_byte(neigh, 0);
1557 accumulate_unicast_short(neigh, rxcost);
1558 accumulate_unicast_short(neigh, interval);
1559 if(ll)
1560 accumulate_unicast_bytes(neigh, neigh->address + 8, 8);
1561 else
1562 accumulate_unicast_bytes(neigh, neigh->address, 16);
1563 if (send_rtt_data) {
1564 accumulate_unicast_byte(neigh, SUBTLV_TIMESTAMP);
1565 accumulate_unicast_byte(neigh, 8);
1566 accumulate_unicast_int(neigh, neigh->hello_send_us);
1567 accumulate_unicast_int(neigh,
1568 time_us(neigh->hello_rtt_receive_time));
1569 }
1570 end_unicast_message(neigh, MESSAGE_IHU, msglen);
1571 }
1572}
1573
1574/* Send IHUs to all marginal neighbours */
1575void
1576send_marginal_ihu(struct interface *ifp)
1577{
1578 struct neighbour *neigh;
1579 FOR_ALL_NEIGHBOURS(neigh) {
1580 if(ifp && neigh->ifp != ifp)
1581 continue;
1582 if(neigh->txcost >= 384 || (neigh->reach & 0xF000) != 0xF000)
1583 send_ihu(neigh, ifp);
1584 }
1585}
1586
1587void
1588send_request(struct interface *ifp,
1589 const unsigned char *prefix, unsigned char plen)
1590{
1591 int v4, pb, len;
1592
1593 if(ifp == NULL) {
f4e14fdb
RW		 1594 struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
1595 struct interface *ifp_aux;
1596 FOR_ALL_INTERFACES(vrf, ifp_aux) {
ca10883e
DS		 1597 if(if_up(ifp_aux))
1598 continue;
1599 send_request(ifp_aux, prefix, plen);
1600 }
1601 return;
1602 }
1603
1604 /* make sure any buffered updates go out before this request. */
1605 flushupdates(ifp);
1606
1607 if(!if_up(ifp))
1608 return;
1609
1610 debugf(BABEL_DEBUG_COMMON,"sending request to %s for %s.",
1611 ifp->name, prefix ? format_prefix(prefix, plen) : "any");
1612 v4 = plen >= 96 && v4mapped(prefix);
1613 pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
1614 len = !prefix ? 2 : 2 + pb;
1615
1616 start_message(ifp, MESSAGE_REQUEST, len);
1617 accumulate_byte(ifp, !prefix ? 0 : v4 ? 1 : 2);
1618 accumulate_byte(ifp, !prefix ? 0 : v4 ? plen - 96 : plen);
1619 if(prefix) {
1620 if(v4)
1621 accumulate_bytes(ifp, prefix + 12, pb);
1622 else
1623 accumulate_bytes(ifp, prefix, pb);
1624 }
1625 end_message(ifp, MESSAGE_REQUEST, len);
1626}
1627
1628void
1629send_unicast_request(struct neighbour *neigh,
1630 const unsigned char *prefix, unsigned char plen)
1631{
1632 int rc, v4, pb, len;
1633
1634 /* make sure any buffered updates go out before this request. */
1635 flushupdates(neigh->ifp);
1636
1637 debugf(BABEL_DEBUG_COMMON,"sending unicast request to %s for %s.",
1638 format_address(neigh->address),
1639 prefix ? format_prefix(prefix, plen) : "any");
1640 v4 = plen >= 96 && v4mapped(prefix);
1641 pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
1642 len = !prefix ? 2 : 2 + pb;
1643
1644 rc = start_unicast_message(neigh, MESSAGE_REQUEST, len);
1645 if(rc < 0) return;
1646 accumulate_unicast_byte(neigh, !prefix ? 0 : v4 ? 1 : 2);
1647 accumulate_unicast_byte(neigh, !prefix ? 0 : v4 ? plen - 96 : plen);
1648 if(prefix) {
1649 if(v4)
1650 accumulate_unicast_bytes(neigh, prefix + 12, pb);
1651 else
1652 accumulate_unicast_bytes(neigh, prefix, pb);
1653 }
1654 end_unicast_message(neigh, MESSAGE_REQUEST, len);
1655}
1656
1657void
1658send_multihop_request(struct interface *ifp,
1659 const unsigned char *prefix, unsigned char plen,
1660 unsigned short seqno, const unsigned char *id,
1661 unsigned short hop_count)
1662{
1663 int v4, pb, len;
1664
1665 /* Make sure any buffered updates go out before this request. */
1666 flushupdates(ifp);
1667
1668 if(ifp == NULL) {
f4e14fdb
RW		 1669 struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
1670 struct interface *ifp_aux;
1671 FOR_ALL_INTERFACES(vrf, ifp_aux) {
ca10883e
DS		 1672 if(!if_up(ifp_aux))
1673 continue;
1674 send_multihop_request(ifp_aux, prefix, plen, seqno, id, hop_count);
1675 }
1676 return;
1677 }
1678
1679 if(!if_up(ifp))
1680 return;
1681
1682 debugf(BABEL_DEBUG_COMMON,"Sending request (%d) on %s for %s.",
1683 hop_count, ifp->name, format_prefix(prefix, plen));
1684 v4 = plen >= 96 && v4mapped(prefix);
1685 pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
1686 len = 6 + 8 + pb;
1687
1688 start_message(ifp, MESSAGE_MH_REQUEST, len);
1689 accumulate_byte(ifp, v4 ? 1 : 2);
1690 accumulate_byte(ifp, v4 ? plen - 96 : plen);
1691 accumulate_short(ifp, seqno);
1692 accumulate_byte(ifp, hop_count);
1693 accumulate_byte(ifp, 0);
1694 accumulate_bytes(ifp, id, 8);
1695 if(prefix) {
1696 if(v4)
1697 accumulate_bytes(ifp, prefix + 12, pb);
1698 else
1699 accumulate_bytes(ifp, prefix, pb);
1700 }
1701 end_message(ifp, MESSAGE_MH_REQUEST, len);
1702}
1703
1704void
1705send_unicast_multihop_request(struct neighbour *neigh,
1706 const unsigned char *prefix, unsigned char plen,
1707 unsigned short seqno, const unsigned char *id,
1708 unsigned short hop_count)
1709{
1710 int rc, v4, pb, len;
1711
1712 /* Make sure any buffered updates go out before this request. */
1713 flushupdates(neigh->ifp);
1714
1715 debugf(BABEL_DEBUG_COMMON,"Sending multi-hop request to %s for %s (%d hops).",
1716 format_address(neigh->address),
1717 format_prefix(prefix, plen), hop_count);
1718 v4 = plen >= 96 && v4mapped(prefix);
1719 pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
1720 len = 6 + 8 + pb;
1721
1722 rc = start_unicast_message(neigh, MESSAGE_MH_REQUEST, len);
1723 if(rc < 0) return;
1724 accumulate_unicast_byte(neigh, v4 ? 1 : 2);
1725 accumulate_unicast_byte(neigh, v4 ? plen - 96 : plen);
1726 accumulate_unicast_short(neigh, seqno);
1727 accumulate_unicast_byte(neigh, hop_count);
1728 accumulate_unicast_byte(neigh, 0);
1729 accumulate_unicast_bytes(neigh, id, 8);
1730 if(prefix) {
1731 if(v4)
1732 accumulate_unicast_bytes(neigh, prefix + 12, pb);
1733 else
1734 accumulate_unicast_bytes(neigh, prefix, pb);
1735 }
1736 end_unicast_message(neigh, MESSAGE_MH_REQUEST, len);
1737}
1738
1739void
1740send_request_resend(struct neighbour *neigh,
1741 const unsigned char *prefix, unsigned char plen,
1742 unsigned short seqno, unsigned char *id)
1743{
1744 if(neigh)
1745 send_unicast_multihop_request(neigh, prefix, plen, seqno, id, 127);
1746 else
1747 send_multihop_request(NULL, prefix, plen, seqno, id, 127);
1748
1749 record_resend(RESEND_REQUEST, prefix, plen, seqno, id,
1750 neigh ? neigh->ifp : NULL, resend_delay);
1751}
1752
1753void
1754handle_request(struct neighbour *neigh, const unsigned char *prefix,
1755 unsigned char plen, unsigned char hop_count,
1756 unsigned short seqno, const unsigned char *id)
1757{
1758 struct xroute *xroute;
1759 struct babel_route *route;
1760 struct neighbour *successor = NULL;
1761
1762 xroute = find_xroute(prefix, plen);
1763 route = find_installed_route(prefix, plen);
1764
1765 if(xroute && (!route || xroute->metric <= kernel_metric)) {
1766 if(hop_count > 0 && memcmp(id, myid, 8) == 0) {
1767 if(seqno_compare(seqno, myseqno) > 0) {
1768 if(seqno_minus(seqno, myseqno) > 100) {
1769 /* Hopelessly out-of-date request */
1770 return;
1771 }
1772 update_myseqno();
1773 }
1774 }
1775 send_update(neigh->ifp, 1, prefix, plen);
1776 return;
1777 }
1778
1779 if(route &&
1780 (memcmp(id, route->src->id, 8) != 0 ||
1781 seqno_compare(seqno, route->seqno) <= 0)) {
1782 send_update(neigh->ifp, 1, prefix, plen);
1783 return;
1784 }
1785
1786 if(hop_count <= 1)
1787 return;
1788
1789 if(route && memcmp(id, route->src->id, 8) == 0 &&
1790 seqno_minus(seqno, route->seqno) > 100) {
1791 /* Hopelessly out-of-date */
1792 return;
1793 }
1794
1795 if(request_redundant(neigh->ifp, prefix, plen, seqno, id))
1796 return;
1797
1798 /* Let's try to forward this request. */
1799 if(route && route_metric(route) < INFINITY)
1800 successor = route->neigh;
1801
1802 if(!successor || successor == neigh) {
1803 /* We were about to forward a request to its requestor. Try to
1804 find a different neighbour to forward the request to. */
1805 struct babel_route *other_route;
1806
1807 other_route = find_best_route(prefix, plen, 0, neigh);
1808 if(other_route && route_metric(other_route) < INFINITY)
1809 successor = other_route->neigh;
1810 }
1811
1812 if(!successor || successor == neigh)
1813 /* Give up */
1814 return;
1815
1816 send_unicast_multihop_request(successor, prefix, plen, seqno, id,
1817 hop_count - 1);
1818 record_resend(RESEND_REQUEST, prefix, plen, seqno, id,
1819 neigh->ifp, 0);
1820}
FRRouting mirror