1 /*
2 Copyright (c) 2007, 2008 by Juliusz Chroboczek
3
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:
10
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
13
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
20 THE SOFTWARE.
21 */
22
23 #include <stdlib.h>
24 #include <string.h>
25 #include <stdio.h>
26 #include <assert.h>
27 #include <sys/time.h>
28 #include <netinet/in.h>
29 #include <arpa/inet.h>
30
31 #include "babeld.h"
32 #include "util.h"
33 #include "net.h"
34 #include "interface.h"
35 #include "source.h"
36 #include "neighbour.h"
37 #include "route.h"
38 #include "kernel.h"
39 #include "xroute.h"
40 #include "resend.h"
41 #include "message.h"
42 #include "configuration.h"
43
44 unsigned char packet_header[4] = {42, 2};
45
46 int split_horizon = 1;
47
48 unsigned short myseqno = 0;
49 struct timeval seqno_time = {0, 0};
50
51 #define MAX_CHANNEL_HOPS 20
52
53 /* Checks whether an AE exists or must be silently ignored */
54 static int
known_ae(int ae)55 known_ae(int ae)
56 {
57 return ae <= 3;
58 }
59
60 /* Parse a network prefix, encoded in the somewhat baroque compressed
61 representation used by Babel. Return the number of bytes parsed. */
62 static int
network_prefix(int ae,int plen,unsigned int omitted,const unsigned char * p,const unsigned char * dp,unsigned int len,unsigned char * p_r)63 network_prefix(int ae, int plen, unsigned int omitted,
64 const unsigned char *p, const unsigned char *dp,
65 unsigned int len, unsigned char *p_r)
66 {
67 unsigned pb;
68 unsigned char prefix[16];
69 int ret = -1;
70
71 if(plen >= 0)
72 pb = (plen + 7) / 8;
73 else if(ae == 1)
74 pb = 4;
75 else
76 pb = 16;
77
78 if(pb > 16)
79 return -1;
80
81 memset(prefix, 0, 16);
82
83 switch(ae) {
84 case 0:
85 ret = 0;
86 break;
87 case 1:
88 if(omitted > 4 || pb > 4 || (pb > omitted && len < pb - omitted))
89 return -1;
90 memcpy(prefix, v4prefix, 12);
91 if(omitted) {
92 if(dp == NULL || !v4mapped(dp)) return -1;
93 memcpy(prefix, dp, 12 + omitted);
94 }
95 if(pb > omitted) memcpy(prefix + 12 + omitted, p, pb - omitted);
96 ret = pb - omitted;
97 break;
98 case 2:
99 if(omitted > 16 || (pb > omitted && len < pb - omitted)) return -1;
100 if(omitted) {
101 if(dp == NULL || v4mapped(dp)) return -1;
102 memcpy(prefix, dp, omitted);
103 }
104 if(pb > omitted) memcpy(prefix + omitted, p, pb - omitted);
105 ret = pb - omitted;
106 break;
107 case 3:
108 if(pb > 8 && len < pb - 8) return -1;
109 prefix[0] = 0xfe;
110 prefix[1] = 0x80;
111 if(pb > 8) memcpy(prefix + 8, p, pb - 8);
112 ret = pb - 8;
113 break;
114 default:
115 return -1;
116 }
117
118 normalize_prefix(p_r, prefix, plen < 0 ? 128 : ae == 1 ? plen + 96 : plen);
119 return ret;
120 }
121
122 static int
parse_update_subtlv(struct interface * ifp,int metric,int ae,const unsigned char * a,int alen,unsigned char * channels,int * channels_len_return,unsigned char * src_prefix,unsigned char * src_plen)123 parse_update_subtlv(struct interface *ifp, int metric, int ae,
124 const unsigned char *a, int alen,
125 unsigned char *channels, int *channels_len_return,
126 unsigned char *src_prefix, unsigned char *src_plen)
127 {
128 int type, len, i = 0;
129 int channels_len;
130 int have_src_prefix = 0;
131
132 /* This will be overwritten if there's a DIVERSITY_HOPS sub-TLV. */
133 if(*channels_len_return < 1 || (ifp->flags & IF_FARAWAY)) {
134 channels_len = 0;
135 } else {
136 if(metric < 256) {
137 /* Assume non-interfering (wired) link. */
138 channels_len = 0;
139 } else {
140 /* Assume interfering. */
141 channels[0] = IF_CHANNEL_INTERFERING;
142 channels_len = 1;
143 }
144 }
145
146 while(i < alen) {
147 type = a[i];
148 if(type == SUBTLV_PAD1) {
149 i++;
150 continue;
151 }
152
153 if(i + 2 > alen)
154 goto fail;
155 len = a[i + 1];
156 if(i + len + 2 > alen)
157 goto fail;
158
159 if(type == SUBTLV_PADN) {
160 /* Nothing. */
161 } else if(type == SUBTLV_DIVERSITY) {
162 memcpy(channels, a + i + 2, MIN(len, *channels_len_return));
163 channels_len = MIN(len, *channels_len_return);
164 } else if(type == SUBTLV_SOURCE_PREFIX) {
165 int rc;
166 if(len < 1)
167 goto fail;
168 if(a[i + 2] == 0) /* source prefix cannot be default */
169 goto fail;
170 if(have_src_prefix != 0) /* source prefix can only appear once */
171 goto fail;
172 rc = network_prefix(ae, a[i + 2], 0, a + i + 3, NULL,
173 len - 1, src_prefix);
174 if(rc < 0)
175 goto fail;
176 if(ae == 1)
177 *src_plen = a[i + 2] + 96;
178 else
179 *src_plen = a[i + 2];
180 have_src_prefix = 1;
181 } else {
182 debugf("Received unknown%s Update sub-TLV %d.\n",
183 (type & 0x80) != 0 ? " mandatory" : "", type);
184 if((type & 0x80) != 0)
185 return -1;
186 }
187
188 i += len + 2;
189 }
190 *channels_len_return = channels_len;
191 return 1;
192
193 fail:
194 fprintf(stderr, "Received truncated sub-TLV on Update.\n");
195 return -1;
196 }
197
198 static int
parse_hello_subtlv(const unsigned char * a,int alen,unsigned int * timestamp_return,int * have_timestamp_return)199 parse_hello_subtlv(const unsigned char *a, int alen,
200 unsigned int *timestamp_return, int *have_timestamp_return)
201 {
202 int type, len, i = 0, have_timestamp = 0;
203 unsigned int timestamp = 0;
204
205 while(i < alen) {
206 type = a[0];
207 if(type == SUBTLV_PAD1) {
208 i++;
209 continue;
210 }
211
212 if(i + 2 > alen) {
213 fprintf(stderr, "Received truncated sub-TLV on Hello.\n");
214 return -1;
215 }
216 len = a[i + 1];
217 if(i + len + 2 > alen) {
218 fprintf(stderr, "Received truncated sub-TLV on Hello.\n");
219 return -1;
220 }
221
222 if(type == SUBTLV_PADN) {
223 /* Nothing to do. */
224 } else if(type == SUBTLV_TIMESTAMP) {
225 if(len >= 4) {
226 DO_NTOHL(timestamp, a + i + 2);
227 have_timestamp = 1;
228 } else {
229 fprintf(stderr,
230 "Received incorrect RTT sub-TLV on Hello.\n");
231 /* But don't break. */
232 }
233 } else {
234 debugf("Received unknown%s Hello sub-TLV %d.\n",
235 (type & 0x80) != 0 ? " mandatory" : "", type);
236 if((type & 0x80) != 0)
237 return -1;
238 }
239
240 i += len + 2;
241 }
242 if(have_timestamp && timestamp_return)
243 *timestamp_return = timestamp;
244 if(have_timestamp_return)
245 *have_timestamp_return = have_timestamp;
246 return 1;
247 }
248
249 static int
parse_ihu_subtlv(const unsigned char * a,int alen,unsigned int * timestamp1_return,unsigned int * timestamp2_return,int * have_timestamp_return)250 parse_ihu_subtlv(const unsigned char *a, int alen,
251 unsigned int *timestamp1_return,
252 unsigned int *timestamp2_return,
253 int *have_timestamp_return)
254 {
255 int type, len, i = 0;
256 int have_timestamp = 0;
257 unsigned int timestamp1, timestamp2;
258
259 while(i < alen) {
260 type = a[0];
261 if(type == SUBTLV_PAD1) {
262 i++;
263 continue;
264 }
265
266 if(i + 2 > alen) {
267 fprintf(stderr, "Received truncated sub-TLV on IHU.\n");
268 return -1;
269 }
270
271 len = a[i + 1];
272 if(i + len + 2 > alen) {
273 fprintf(stderr, "Received truncated sub-TLV on IHU.\n");
274 return -1;
275 }
276
277 if(type == SUBTLV_PADN) {
278 /* Nothing to do. */
279 } else if(type == SUBTLV_TIMESTAMP) {
280 if(len >= 8) {
281 DO_NTOHL(timestamp1, a + i + 2);
282 DO_NTOHL(timestamp2, a + i + 6);
283 have_timestamp = 1;
284 } else {
285 fprintf(stderr,
286 "Received incorrect RTT sub-TLV on IHU.\n");
287 /* But don't break. */
288 }
289 } else {
290 debugf("Received unknown%s IHU sub-TLV %d.\n",
291 (type & 0x80) != 0 ? " mandatory" : "", type);
292 if((type & 0x80) != 0)
293 return -1;
294 }
295
296 i += len + 2;
297 }
298 if(have_timestamp && timestamp1_return && timestamp2_return) {
299 *timestamp1_return = timestamp1;
300 *timestamp2_return = timestamp2;
301 }
302 if(have_timestamp_return) {
303 *have_timestamp_return = have_timestamp;
304 }
305 return 1;
306 }
307
308 static int
parse_request_subtlv(int ae,const unsigned char * a,int alen,unsigned char * src_prefix,unsigned char * src_plen)309 parse_request_subtlv(int ae, const unsigned char *a, int alen,
310 unsigned char *src_prefix, unsigned char *src_plen)
311 {
312 int type, len, i = 0;
313 int have_src_prefix = 0;
314
315 while(i < alen) {
316 type = a[0];
317 if(type == SUBTLV_PAD1) {
318 i++;
319 continue;
320 }
321
322 if(i + 2 > alen)
323 goto fail;
324
325 len = a[i + 1];
326 if(i + 2 + len > alen)
327 goto fail;
328
329 if(type == SUBTLV_PADN) {
330 /* Nothing to do. */
331 } else if(type == SUBTLV_SOURCE_PREFIX) {
332 int rc;
333 if(len < 1)
334 goto fail;
335 if(a[i + 2] == 0)
336 goto fail;
337 if(have_src_prefix != 0)
338 goto fail;
339 rc = network_prefix(ae, a[i + 2], 0, a + i + 3, NULL,
340 len - 1, src_prefix);
341 if(rc < 0)
342 goto fail;
343 if(ae == 1)
344 *src_plen = a[i + 2] + 96;
345 else
346 *src_plen = a[i + 2];
347 have_src_prefix = 1;
348 } else {
349 debugf("Received unknown%s Route Request sub-TLV %d.\n",
350 ((type & 0x80) != 0) ? " mandatory" : "", type);
351 if((type & 0x80) != 0)
352 return -1;
353 }
354
355 i += len + 2;
356 }
357 return 1;
358
359 fail:
360 fprintf(stderr, "Received truncated sub-TLV on Route Request.\n");
361 return -1;
362 }
363
364 static int
parse_seqno_request_subtlv(int ae,const unsigned char * a,int alen,unsigned char * src_prefix,unsigned char * src_plen)365 parse_seqno_request_subtlv(int ae, const unsigned char *a, int alen,
366 unsigned char *src_prefix, unsigned char *src_plen)
367 {
368 int type, len, i = 0;
369
370 while(i < alen) {
371 type = a[0];
372 if(type == SUBTLV_PAD1) {
373 i++;
374 continue;
375 }
376
377 if(i + 2 > alen)
378 goto fail;
379 len = a[i + 1];
380 if(i + len + 2 > alen)
381 goto fail;
382
383 if(type == SUBTLV_PADN) {
384 /* Nothing to do. */
385 } else if(type == SUBTLV_SOURCE_PREFIX) {
386 int rc;
387 if(len < 1)
388 goto fail;
389 *src_plen = a[i + 2];
390 rc = network_prefix(ae, *src_plen, 0, a + i + 3, NULL,
391 len - 1, src_prefix);
392 if(rc < 0)
393 goto fail;
394 if(ae == 1)
395 (*src_plen) += 96;
396 } else {
397 debugf("Received unknown%s Route Request sub-TLV %d.\n",
398 ((type & 0x80) != 0) ? " mandatory" : "", type);
399 if((type & 0x80) != 0)
400 return -1;
401 }
402
403 i += len + 2;
404 }
405 return 1;
406 fail:
407 fprintf(stderr, "Received truncated sub-TLV on Route Request.\n");
408 return -1;
409 }
410
411 static int
parse_other_subtlv(const unsigned char * a,int alen)412 parse_other_subtlv(const unsigned char *a, int alen)
413 {
414 int type, len, i = 0;
415
416 while(i < alen) {
417 type = a[0];
418 if(type == SUBTLV_PAD1) {
419 i++;
420 continue;
421 }
422
423 if(i + 2 > alen)
424 goto fail;
425 len = a[i + 1];
426 if(i + 2 + len > alen)
427 goto fail;
428
429 if((type & 0x80) != 0) {
430 debugf("Received unknown mandatory sub-TLV %d.\n", type);
431 return -1;
432 }
433
434 i += len + 2;
435 }
436 return 1;
437 fail:
438 fprintf(stderr, "Received truncated sub-TLV.\n");
439 return -1;
440 }
441
442 static int
network_address(int ae,const unsigned char * a,unsigned int len,unsigned char * a_r)443 network_address(int ae, const unsigned char *a, unsigned int len,
444 unsigned char *a_r)
445 {
446 return network_prefix(ae, -1, 0, a, NULL, len, a_r);
447 }
448
449 void
parse_packet(const unsigned char * from,struct interface * ifp,const unsigned char * packet,int packetlen)450 parse_packet(const unsigned char *from, struct interface *ifp,
451 const unsigned char *packet, int packetlen)
452 {
453 int i;
454 const unsigned char *message;
455 unsigned char type, len;
456 int bodylen;
457 struct neighbour *neigh;
458 int have_router_id = 0, have_v4_prefix = 0, have_v6_prefix = 0,
459 have_v4_nh = 0, have_v6_nh = 0;
460 unsigned char router_id[8], v4_prefix[16], v6_prefix[16],
461 v4_nh[16], v6_nh[16];
462 int have_hello_rtt = 0;
463 /* Content of the RTT sub-TLV on IHU messages. */
464 unsigned int hello_send_us = 0, hello_rtt_receive_time = 0;
465
466 if((ifp->flags & IF_TIMESTAMPS) != 0) {
467 /* We want to track exactly when we received this packet. */
468 gettime(&now);
469 }
470
471 if(!linklocal(from)) {
472 fprintf(stderr, "Received packet from non-local address %s.\n",
473 format_address(from));
474 return;
475 }
476
477 if(packet[0] != 42) {
478 fprintf(stderr, "Received malformed packet on %s from %s.\n",
479 ifp->name, format_address(from));
480 return;
481 }
482
483 if(packet[1] != 2) {
484 fprintf(stderr,
485 "Received packet with unknown version %d on %s from %s.\n",
486 packet[1], ifp->name, format_address(from));
487 return;
488 }
489
490 DO_NTOHS(bodylen, packet + 2);
491
492 if(bodylen + 4 > packetlen) {
493 fprintf(stderr, "Received truncated packet (%d + 4 > %d).\n",
494 bodylen, packetlen);
495 bodylen = packetlen - 4;
496 }
497
498 neigh = find_neighbour(from, ifp);
499 if(neigh == NULL) {
500 fprintf(stderr, "Couldn't allocate neighbour.\n");
501 return;
502 }
503
504 i = 0;
505 while(i < bodylen) {
506 message = packet + 4 + i;
507 type = message[0];
508 if(type == MESSAGE_PAD1) {
509 debugf("Received pad1 from %s on %s.\n",
510 format_address(from), ifp->name);
511 i++;
512 continue;
513 }
514 if(i + 2 > bodylen) {
515 fprintf(stderr, "Received truncated message.\n");
516 break;
517 }
518 len = message[1];
519 if(i + len + 2 > bodylen) {
520 fprintf(stderr, "Received truncated message.\n");
521 break;
522 }
523
524 if(type == MESSAGE_PADN) {
525 debugf("Received pad%d from %s on %s.\n",
526 len, format_address(from), ifp->name);
527 } else if(type == MESSAGE_ACK_REQ) {
528 unsigned short nonce, interval;
529 int rc;
530 if(len < 6) goto fail;
531 DO_NTOHS(nonce, message + 4);
532 DO_NTOHS(interval, message + 6);
533 debugf("Received ack-req (%04X %d) from %s on %s.\n",
534 nonce, interval, format_address(from), ifp->name);
535 rc = parse_other_subtlv(message + 8, len - 6);
536 if(rc < 0)
537 goto done;
538 send_ack(neigh, nonce, interval);
539 } else if(type == MESSAGE_ACK) {
540 int rc;
541 debugf("Received ack from %s on %s.\n",
542 format_address(from), ifp->name);
543 rc = parse_other_subtlv(message + 4, len - 2);
544 if(rc < 0)
545 goto done;
546 /* Nothing right now */
547 } else if(type == MESSAGE_HELLO) {
548 unsigned short seqno, interval;
549 int unicast, changed, have_timestamp, rc;
550 unsigned int timestamp;
551 if(len < 6) goto fail;
552 unicast = !!(message[2] & 0x80);
553 DO_NTOHS(seqno, message + 4);
554 DO_NTOHS(interval, message + 6);
555 debugf("Received hello %d (%d) from %s on %s.\n",
556 seqno, interval,
557 format_address(from), ifp->name);
558 /* Sub-TLV handling. */
559 rc = parse_hello_subtlv(message + 8, len - 6,
560 ×tamp, &have_timestamp);
561 if(rc < 0)
562 goto done;
563 changed =
564 update_neighbour(neigh,
565 unicast ? &neigh->uhello : &neigh->hello,
566 unicast, seqno, interval);
567 update_neighbour_metric(neigh, changed);
568 if(interval > 0)
569 /* Multiply by 3/2 to allow hellos to expire. */
570 schedule_neighbours_check(interval * 15, 0);
571 if(have_timestamp) {
572 neigh->hello_send_us = timestamp;
573 neigh->hello_rtt_receive_time = now;
574 have_hello_rtt = 1;
575 }
576 } else if(type == MESSAGE_IHU) {
577 unsigned short txcost, interval;
578 unsigned char address[16];
579 int rc;
580 if(len < 6) goto fail;
581 if(!known_ae(message[2])) {
582 debugf("Received IHU with unknown AE %d. Ignoring.\n",
583 message[2]);
584 goto done;
585 }
586 DO_NTOHS(txcost, message + 4);
587 DO_NTOHS(interval, message + 6);
588 rc = network_address(message[2], message + 8, len - 6, address);
589 if(rc < 0) goto fail;
590 debugf("Received ihu %d (%d) from %s on %s for %s.\n",
591 txcost, interval,
592 format_address(from), ifp->name,
593 format_address(address));
594 if(message[2] == 0 || interface_ll_address(ifp, address)) {
595 int changed;
596 rc = parse_ihu_subtlv(message + 8 + rc, len - 6 - rc,
597 &hello_send_us, &hello_rtt_receive_time,
598 NULL);
599 if(rc < 0)
600 goto done;
601 changed = txcost != neigh->txcost;
602 neigh->txcost = txcost;
603 neigh->ihu_time = now;
604 neigh->ihu_interval = interval;
605 update_neighbour_metric(neigh, changed);
606 if(interval > 0)
607 /* Multiply by 3/2 to allow neighbours to expire. */
608 schedule_neighbours_check(interval * 45, 0);
609 }
610 } else if(type == MESSAGE_ROUTER_ID) {
611 int rc;
612 if(len < 10) {
613 have_router_id = 0;
614 goto fail;
615 }
616 memcpy(router_id, message + 4, 8);
617 have_router_id = 1;
618 debugf("Received router-id %s from %s on %s.\n",
619 format_eui64(router_id), format_address(from), ifp->name);
620 rc = parse_other_subtlv(message + 12, len - 10);
621 if(rc < 0)
622 goto done;
623 } else if(type == MESSAGE_NH) {
624 unsigned char nh[16];
625 int rc;
626 if(len < 2) {
627 have_v4_nh = 0;
628 have_v6_nh = 0;
629 goto fail;
630 }
631 rc = network_address(message[2], message + 4, len - 2, nh);
632 if(!known_ae(message[2])) {
633 debugf("Received NH with unknown AE %d. Ignoring.\n",
634 message[2]);
635 goto done;
636 }
637 if(message[2] == 0) {
638 debugf("Received NH with bad AE 0. Error.\n");
639 goto fail;
640 }
641 if(rc < 0) {
642 have_v4_nh = 0;
643 have_v6_nh = 0;
644 goto fail;
645 }
646 debugf("Received nh %s (%d) from %s on %s.\n",
647 format_address(nh), message[2],
648 format_address(from), ifp->name);
649 if(message[2] == 1) {
650 memcpy(v4_nh, nh, 16);
651 have_v4_nh = 1;
652 } else {
653 memcpy(v6_nh, nh, 16);
654 have_v6_nh = 1;
655 }
656 rc = parse_other_subtlv(message + 4 + rc, len - 2 - rc);
657 if(rc < 0)
658 goto done;
659 } else if(type == MESSAGE_UPDATE) {
660 unsigned char prefix[16], src_prefix[16], *nh;
661 unsigned char plen, src_plen;
662 unsigned char channels[MAX_CHANNEL_HOPS];
663 int channels_len = MAX_CHANNEL_HOPS;
664 unsigned short interval, seqno, metric;
665 int rc, parsed_len, is_ss;
666 if(len < 10) {
667 if(len < 2 || message[3] & 0x80)
668 have_v4_prefix = have_v6_prefix = 0;
669 goto fail;
670 }
671 if(!known_ae(message[2])) {
672 debugf("Received update with unknown AE %d. Ignoring.\n",
673 message[2]);
674 goto done;
675 }
676 DO_NTOHS(interval, message + 6);
677 DO_NTOHS(seqno, message + 8);
678 DO_NTOHS(metric, message + 10);
679 if(message[5] == 0 ||
680 (message[2] == 1 ? have_v4_prefix : have_v6_prefix))
681 rc = network_prefix(message[2], message[4], message[5],
682 message + 12,
683 message[2] == 1 ? v4_prefix : v6_prefix,
684 len - 10, prefix);
685 else
686 rc = -1;
687 if(message[2] == 1) {
688 v4tov6(src_prefix, zeroes);
689 src_plen = 96;
690 } else {
691 memcpy(src_prefix, zeroes, 16);
692 src_plen = 0;
693 }
694 if(rc < 0) {
695 if(message[3] & 0x80)
696 have_v4_prefix = have_v6_prefix = 0;
697 goto fail;
698 }
699 parsed_len = 10 + rc;
700
701 plen = message[4] + (message[2] == 1 ? 96 : 0);
702
703 if(message[3] & 0x80) {
704 if(message[2] == 1) {
705 memcpy(v4_prefix, prefix, 16);
706 have_v4_prefix = 1;
707 } else {
708 memcpy(v6_prefix, prefix, 16);
709 have_v6_prefix = 1;
710 }
711 }
712 if(message[3] & 0x40) {
713 if(message[2] == 1) {
714 memset(router_id, 0, 4);
715 memcpy(router_id + 4, prefix + 12, 4);
716 } else {
717 memcpy(router_id, prefix + 8, 8);
718 }
719 have_router_id = 1;
720 }
721 if(metric < INFINITY && !have_router_id && message[2] != 0) {
722 fprintf(stderr, "Received prefix with no router id.\n");
723 goto fail;
724 }
725 debugf("Received update%s%s for %s from %s on %s.\n",
726 (message[3] & 0x80) ? "/prefix" : "",
727 (message[3] & 0x40) ? "/id" : "",
728 format_prefix(prefix, plen),
729 format_address(from), ifp->name);
730 if(message[2] == 1) {
731 if(have_v4_nh) {
732 nh = v4_nh;
733 } else {
734 if(metric < INFINITY)
735 goto fail;
736 nh = NULL;
737 }
738 } else if(have_v6_nh) {
739 nh = v6_nh;
740 } else {
741 nh = neigh->address;
742 }
743
744 rc = parse_update_subtlv(ifp, metric, message[2],
745 message + 2 + parsed_len,
746 len - parsed_len, channels, &channels_len,
747 src_prefix, &src_plen);
748 if(rc < 0)
749 goto done;
750
751 if(message[2] == 0) {
752 if(metric < 0xFFFF) {
753 fprintf(stderr,
754 "Received wildcard update with finite metric.\n");
755 goto done;
756 }
757 if(src_plen > 0) {
758 fprintf(stderr,
759 "Received wildcard update with source prefix.\n");
760 goto done;
761 }
762 retract_neighbour_routes(neigh);
763 goto done;
764 }
765
766 is_ss = !is_default(src_prefix, src_plen);
767 debugf("Received update%s%s for dst %s%s%s from %s on %s.\n",
768 (message[3] & 0x80) ? "/prefix" : "",
769 (message[3] & 0x40) ? "/id" : "",
770 format_prefix(prefix, plen),
771 is_ss ? " src " : "",
772 is_ss ? format_prefix(src_prefix, src_plen) : "",
773 format_address(from), ifp->name);
774
775 if(message[2] == 1) {
776 if(!ifp->ipv4)
777 goto done;
778 }
779
780 update_route(have_router_id ? router_id : NULL,
781 prefix, plen, src_prefix, src_plen, seqno,
782 metric, interval, neigh, nh,
783 channels, channels_len);
784 } else if(type == MESSAGE_REQUEST) {
785 unsigned char prefix[16], src_prefix[16], plen, src_plen;
786 int rc, is_ss;
787 if(len < 2) goto fail;
788 if(!known_ae(message[2])) {
789 debugf("Received request with unknown AE %d. Ignoring.\n",
790 message[2]);
791 goto done;
792 }
793 rc = network_prefix(message[2], message[3], 0,
794 message + 4, NULL, len - 2, prefix);
795 if(rc < 0) goto fail;
796 plen = message[3] + (message[2] == 1 ? 96 : 0);
797 if(message[2] == 1) {
798 v4tov6(src_prefix, zeroes);
799 src_plen = 96;
800 } else {
801 memcpy(src_prefix, zeroes, 16);
802 src_plen = 0;
803 }
804 rc = parse_request_subtlv(message[2], message + 4 + rc,
805 len - 2 - rc, src_prefix, &src_plen);
806 if(rc < 0)
807 goto done;
808 is_ss = !is_default(src_prefix, src_plen);
809 if(message[2] == 0) {
810 if(is_ss) {
811 /* Wildcard requests don't carry a source prefix. */
812 fprintf(stderr,
813 "Received source-specific wildcard request.\n");
814 goto done;
815 }
816 debugf("Received request for any from %s on %s.\n",
817 format_address(from), ifp->name);
818 /* If a neighbour is requesting a full route dump from us,
819 we might as well send it an IHU. */
820 send_ihu(neigh, NULL);
821 /* Since nodes send wildcard requests on boot, booting
822 a large number of nodes at the same time may cause an
823 update storm. Ignore a wildcard request that happens
824 shortly after we sent a full update. */
825 if(neigh->ifp->last_update_time <
826 now.tv_sec - MAX(neigh->ifp->hello_interval / 100, 1)) {
827 send_update(neigh->ifp, 0, NULL, 0, NULL, 0);
828 }
829 } else {
830 debugf("Received request for dst %s%s%s from %s on %s.\n",
831 message[2] == 0 ? "" : format_prefix(prefix, plen),
832 is_ss ? " src " : "",
833 is_ss ? format_prefix(src_prefix, src_plen) : "",
834 format_address(from), ifp->name);
835 send_update(neigh->ifp, 0, prefix, plen, src_prefix, src_plen);
836 }
837 } else if(type == MESSAGE_MH_REQUEST) {
838 unsigned char prefix[16], src_prefix[16], plen, src_plen;
839 unsigned short seqno;
840 int rc, is_ss;
841 if(len < 14) goto fail;
842 if(!known_ae(message[2])) {
843 debugf("Received mh_request with unknown AE %d. Ignoring.\n",
844 message[2]);
845 goto done;
846 }
847 DO_NTOHS(seqno, message + 4);
848 rc = network_prefix(message[2], message[3], 0,
849 message + 16, NULL, len - 14, prefix);
850 if(rc < 0) goto fail;
851 if(message[2] == 1) {
852 v4tov6(src_prefix, zeroes);
853 src_plen = 96;
854 } else {
855 memcpy(src_prefix, zeroes, 16);
856 src_plen = 0;
857 }
858 rc = parse_seqno_request_subtlv(message[2], message + 16 + rc,
859 len - 14 - rc, src_prefix,
860 &src_plen);
861 if(rc < 0)
862 goto done;
863 is_ss = !is_default(src_prefix, src_plen);
864 plen = message[3] + (message[2] == 1 ? 96 : 0);
865 debugf("Received request (%d) for dst %s%s%s from %s on "
866 "%s (%s, %d).\n",
867 message[6],
868 format_prefix(prefix, plen),
869 is_ss ? " src " : "",
870 is_ss ? format_prefix(src_prefix, src_plen) : "",
871 format_address(from), ifp->name,
872 format_eui64(message + 8), seqno);
873 handle_request(neigh, prefix, plen, src_prefix, src_plen,
874 message[6], seqno, message + 8);
875 } else {
876 debugf("Received unknown packet type %d from %s on %s.\n",
877 type, format_address(from), ifp->name);
878 }
879 done:
880 i += len + 2;
881 continue;
882
883 fail:
884 fprintf(stderr, "Couldn't parse packet (%d, %d) from %s on %s.\n",
885 message[0], message[1], format_address(from), ifp->name);
886 goto done;
887 }
888
889 /* We can calculate the RTT to this neighbour. */
890 if(have_hello_rtt && hello_send_us && hello_rtt_receive_time) {
891 int remote_waiting_us, local_waiting_us;
892 unsigned int rtt, smoothed_rtt;
893 unsigned int old_rttcost;
894 int changed = 0;
895 remote_waiting_us = neigh->hello_send_us - hello_rtt_receive_time;
896 local_waiting_us = time_us(neigh->hello_rtt_receive_time) -
897 hello_send_us;
898
899 /* Sanity checks (validity window of 10 minutes). */
900 if(remote_waiting_us < 0 || local_waiting_us < 0 ||
901 remote_waiting_us > 600000000 || local_waiting_us > 600000000)
902 return;
903
904 rtt = MAX(0, local_waiting_us - remote_waiting_us);
905 debugf("RTT to %s on %s sample result: %d us.\n",
906 format_address(from), ifp->name, rtt);
907
908 old_rttcost = neighbour_rttcost(neigh);
909 if(valid_rtt(neigh)) {
910 /* Running exponential average. */
911 smoothed_rtt = (ifp->rtt_decay * rtt +
912 (256 - ifp->rtt_decay) * neigh->rtt);
913 /* Rounding (up or down) to get closer to the sample. */
914 neigh->rtt = (neigh->rtt >= rtt) ? smoothed_rtt / 256 :
915 (smoothed_rtt + 255) / 256;
916 } else {
917 /* We prefer to be conservative with new neighbours
918 (higher RTT) */
919 assert(rtt <= 0x7FFFFFFF);
920 neigh->rtt = 2*rtt;
921 }
922 changed = (neighbour_rttcost(neigh) == old_rttcost ? 0 : 1);
923 update_neighbour_metric(neigh, changed);
924 neigh->rtt_time = now;
925 }
926 return;
927 }
928
929 static int
fill_rtt_message(struct buffered * buf,struct interface * ifp)930 fill_rtt_message(struct buffered *buf, struct interface *ifp)
931 {
932 if((ifp->flags & IF_TIMESTAMPS) != 0 && (buf->hello >= 0)) {
933 if(buf->buf[buf->hello + 8] == SUBTLV_PADN &&
934 buf->buf[buf->hello + 9] == 4) {
935 unsigned int time;
936 /* Change the type of sub-TLV. */
937 buf->buf[buf->hello + 8] = SUBTLV_TIMESTAMP;
938 gettime(&now);
939 time = time_us(now);
940 DO_HTONL(buf->buf + buf->hello + 10, time);
941 return 1;
942 } else {
943 fprintf(stderr,
944 "No space left for timestamp sub-TLV "
945 "(this shouldn't happen)\n");
946 return -1;
947 }
948 }
949 return 0;
950 }
951
952 void
flushbuf(struct buffered * buf,struct interface * ifp)953 flushbuf(struct buffered *buf, struct interface *ifp)
954 {
955 int rc;
956
957 assert(buf->len <= buf->size);
958
959 if(buf->len > 0) {
960 debugf(" (flushing %d buffered bytes)\n", buf->len);
961 DO_HTONS(packet_header + 2, buf->len);
962 fill_rtt_message(buf, ifp);
963 rc = babel_send(protocol_socket,
964 packet_header, sizeof(packet_header),
965 buf->buf, buf->len,
966 (struct sockaddr*)&buf->sin6,
967 sizeof(buf->sin6));
968 if(rc < 0)
969 perror("send");
970 }
971 VALGRIND_MAKE_MEM_UNDEFINED(buf->buf, buf->size);
972 buf->len = 0;
973 buf->hello = -1;
974 buf->have_id = 0;
975 buf->have_nh = 0;
976 buf->have_prefix = 0;
977 buf->timeout.tv_sec = 0;
978 buf->timeout.tv_usec = 0;
979 }
980
981 static void
schedule_flush_ms(struct buffered * buf,int msecs)982 schedule_flush_ms(struct buffered *buf, int msecs)
983 {
984 if(buf->timeout.tv_sec != 0 &&
985 timeval_minus_msec(&buf->timeout, &now) < msecs)
986 return;
987 set_timeout(&buf->timeout, msecs);
988 }
989
990 static void
schedule_flush(struct buffered * buf)991 schedule_flush(struct buffered *buf)
992 {
993 schedule_flush_ms(buf, jitter(buf, 0));
994 }
995
996 static void
schedule_flush_now(struct buffered * buf)997 schedule_flush_now(struct buffered *buf)
998 {
999 schedule_flush_ms(buf, roughly(10));
1000 }
1001
1002 static void
ensure_space(struct buffered * buf,struct interface * ifp,int space)1003 ensure_space(struct buffered *buf, struct interface *ifp, int space)
1004 {
1005 if(buf->size - buf->len < space)
1006 flushbuf(buf, ifp);
1007 }
1008
1009 static void
start_message(struct buffered * buf,struct interface * ifp,int type,int len)1010 start_message(struct buffered *buf, struct interface *ifp, int type, int len)
1011 {
1012 if(buf->size - buf->len < len + 2)
1013 flushbuf(buf, ifp);
1014 buf->buf[buf->len++] = type;
1015 buf->buf[buf->len++] = len;
1016 }
1017
1018 static void
end_message(struct buffered * buf,int type,int bytes)1019 end_message(struct buffered *buf, int type, int bytes)
1020 {
1021 assert(buf->len >= bytes + 2 &&
1022 buf->buf[buf->len - bytes - 2] == type &&
1023 buf->buf[buf->len - bytes - 1] == bytes);
1024 schedule_flush(buf);
1025 }
1026
1027 static void
accumulate_byte(struct buffered * buf,unsigned char value)1028 accumulate_byte(struct buffered *buf, unsigned char value)
1029 {
1030 buf->buf[buf->len++] = value;
1031 }
1032
1033 static void
accumulate_short(struct buffered * buf,unsigned short value)1034 accumulate_short(struct buffered *buf, unsigned short value)
1035 {
1036 DO_HTONS(buf->buf + buf->len, value);
1037 buf->len += 2;
1038 }
1039
1040 static void
accumulate_int(struct buffered * buf,unsigned int value)1041 accumulate_int(struct buffered *buf, unsigned int value)
1042 {
1043 DO_HTONL(buf->buf + buf->len, value);
1044 buf->len += 4;
1045 }
1046
1047 static void
accumulate_bytes(struct buffered * buf,const unsigned char * value,unsigned len)1048 accumulate_bytes(struct buffered *buf,
1049 const unsigned char *value, unsigned len)
1050 {
1051 memcpy(buf->buf + buf->len, value, len);
1052 buf->len += len;
1053 }
1054
1055 void
send_ack(struct neighbour * neigh,unsigned short nonce,unsigned short interval)1056 send_ack(struct neighbour *neigh, unsigned short nonce, unsigned short interval)
1057 {
1058 debugf("Sending ack (%04x) to %s on %s.\n",
1059 nonce, format_address(neigh->address), neigh->ifp->name);
1060 start_message(&neigh->buf, neigh->ifp, MESSAGE_ACK, 2);
1061 accumulate_short(&neigh->buf, nonce);
1062 end_message(&neigh->buf, MESSAGE_ACK, 2);
1063 /* Roughly yields a value no larger than 3/2, so this meets the deadline */
1064 schedule_flush_ms(&neigh->buf, roughly(interval * 6));
1065 }
1066
1067 static void
buffer_hello(struct buffered * buf,struct interface * ifp,unsigned short seqno,unsigned interval,int unicast)1068 buffer_hello(struct buffered *buf, struct interface *ifp,
1069 unsigned short seqno, unsigned interval, int unicast)
1070 {
1071 int timestamp = !!(ifp->flags & IF_TIMESTAMPS);
1072 start_message(buf, ifp, MESSAGE_HELLO, timestamp ? 12 : 6);
1073 buf->hello = buf->len - 2;
1074 accumulate_short(buf, unicast ? 0x8000 : 0);
1075 accumulate_short(buf, seqno);
1076 accumulate_short(buf, interval > 0xFFFF ? 0xFFFF : interval);
1077 if(timestamp) {
1078 /* Sub-TLV containing the local time of emission. We use a
1079 Pad4 sub-TLV, which we'll fill just before sending. */
1080 accumulate_byte(buf, SUBTLV_PADN);
1081 accumulate_byte(buf, 4);
1082 accumulate_int(buf, 0);
1083 }
1084 end_message(buf, MESSAGE_HELLO, timestamp ? 12 : 6);
1085 }
1086
1087 void
send_multicast_hello(struct interface * ifp,unsigned interval,int force)1088 send_multicast_hello(struct interface *ifp, unsigned interval, int force)
1089 {
1090 if(!if_up(ifp))
1091 return;
1092
1093 if(interval == 0 && (ifp->flags & IF_RFC6126) != 0)
1094 /* Unscheduled hellos are incompatible with RFC 6126. */
1095 return;
1096
1097 /* This avoids sending multiple hellos in a single packet, which breaks
1098 link quality estimation. */
1099 if(ifp->buf.hello >= 0) {
1100 if(force) {
1101 flushupdates(ifp);
1102 flushbuf(&ifp->buf, ifp);
1103 } else {
1104 return;
1105 }
1106 }
1107
1108 ifp->hello_seqno = seqno_plus(ifp->hello_seqno, 1);
1109 if(interval > 0)
1110 set_timeout(&ifp->hello_timeout, ifp->hello_interval);
1111
1112 debugf("Sending hello %d (%d) to %s.\n",
1113 ifp->hello_seqno, interval, ifp->name);
1114
1115 buffer_hello(&ifp->buf, ifp, ifp->hello_seqno, interval, 0);
1116 }
1117
1118 void
send_unicast_hello(struct neighbour * neigh,unsigned interval,int force)1119 send_unicast_hello(struct neighbour *neigh, unsigned interval, int force)
1120 {
1121 if(!if_up(neigh->ifp))
1122 return;
1123
1124 if((neigh->ifp->flags & IF_RFC6126) != 0)
1125 /* Unicast hellos are incompatible with RFC 6126. */
1126 return;
1127
1128 if(neigh->buf.hello >= 0) {
1129 if(force)
1130 flushbuf(&neigh->buf, neigh->ifp);
1131 else
1132 return;
1133 }
1134
1135 neigh->hello_seqno = seqno_plus(neigh->hello_seqno, 1);
1136
1137 debugf("Sending unicast hello %d (%d) on %s.\n",
1138 neigh->hello_seqno, interval, neigh->ifp->name);
1139
1140 buffer_hello(&neigh->buf, neigh->ifp, neigh->hello_seqno, interval, 1);
1141 }
1142
1143 void
send_hello(struct interface * ifp)1144 send_hello(struct interface *ifp)
1145 {
1146 send_multicast_hello(ifp, (ifp->hello_interval + 9) / 10, 1);
1147 /* Send full IHU every 3 hellos, and marginal IHU each time */
1148 if(ifp->hello_seqno % 3 == 0)
1149 send_ihu(NULL, ifp);
1150 else
1151 send_marginal_ihu(ifp);
1152 }
1153
1154 static void
really_buffer_update(struct buffered * buf,struct interface * ifp,const unsigned char * id,const unsigned char * prefix,unsigned char plen,const unsigned char * src_prefix,unsigned char src_plen,unsigned short seqno,unsigned short metric,unsigned char * channels,int channels_len)1155 really_buffer_update(struct buffered *buf, struct interface *ifp,
1156 const unsigned char *id,
1157 const unsigned char *prefix, unsigned char plen,
1158 const unsigned char *src_prefix, unsigned char src_plen,
1159 unsigned short seqno, unsigned short metric,
1160 unsigned char *channels, int channels_len)
1161 {
1162 int add_metric, v4, real_plen, real_src_plen;
1163 int omit, spb, channels_size, len;
1164 const unsigned char *real_prefix, *real_src_prefix;
1165 unsigned short flags = 0;
1166 int is_ss = !is_default(src_prefix, src_plen);
1167
1168 if(!if_up(ifp))
1169 return;
1170
1171 if(is_ss && (ifp->flags & IF_RFC6126) != 0)
1172 return;
1173
1174 add_metric = output_filter(id, prefix, plen, src_prefix,
1175 src_plen, ifp->ifindex);
1176 if(add_metric >= INFINITY)
1177 return;
1178
1179 metric = MIN(metric + add_metric, INFINITY);
1180
1181 /* Worst case */
1182 ensure_space(buf, ifp, 20 + 12 + 28 + 18);
1183
1184 v4 = plen >= 96 && v4mapped(prefix);
1185
1186 if(v4) {
1187 if(!ifp->ipv4)
1188 return;
1189 omit = 0;
1190 if(!buf->have_nh ||
1191 memcmp(buf->nh, ifp->ipv4, 4) != 0) {
1192 start_message(buf, ifp, MESSAGE_NH, 6);
1193 accumulate_byte(buf, 1);
1194 accumulate_byte(buf, 0);
1195 accumulate_bytes(buf, ifp->ipv4, 4);
1196 end_message(buf, MESSAGE_NH, 6);
1197 memcpy(&buf->nh, ifp->ipv4, 4);
1198 buf->have_nh = 1;
1199 }
1200 real_prefix = prefix + 12;
1201 real_plen = plen - 96;
1202 real_src_prefix = src_prefix + 12;
1203 real_src_plen = src_plen - 96;
1204 } else {
1205 omit = 0;
1206 if(buf->have_prefix) {
1207 while(omit < plen / 8 &&
1208 buf->prefix[omit] == prefix[omit])
1209 omit++;
1210 }
1211 if(!buf->have_prefix || plen >= 48)
1212 flags |= 0x80;
1213 real_prefix = prefix;
1214 real_plen = plen;
1215 real_src_prefix = src_prefix;
1216 real_src_plen = src_plen;
1217 }
1218
1219 if(!buf->have_id || memcmp(id, buf->id, 8) != 0) {
1220 if(real_plen == 128 && memcmp(real_prefix + 8, id, 8) == 0) {
1221 flags |= 0x40;
1222 } else {
1223 start_message(buf, ifp, MESSAGE_ROUTER_ID, 10);
1224 accumulate_short(buf, 0);
1225 accumulate_bytes(buf, id, 8);
1226 end_message(buf, MESSAGE_ROUTER_ID, 10);
1227 }
1228 memcpy(buf->id, id, 8);
1229 buf->have_id = 1;
1230 }
1231
1232 channels_size = diversity_kind == DIVERSITY_CHANNEL && channels_len >= 0 ?
1233 channels_len + 2 : 0;
1234 len = 10 + (real_plen + 7) / 8 - omit + channels_size;
1235 spb = (real_src_plen + 7) / 8;
1236 if(is_ss)
1237 len += 3 + spb;
1238
1239 start_message(buf, ifp, MESSAGE_UPDATE, len);
1240 accumulate_byte(buf, v4 ? 1 : 2);
1241 accumulate_byte(buf, flags);
1242 accumulate_byte(buf, real_plen);
1243 accumulate_byte(buf, omit);
1244 accumulate_short(buf, (ifp->update_interval + 5) / 10);
1245 accumulate_short(buf, seqno);
1246 accumulate_short(buf, metric);
1247 accumulate_bytes(buf, real_prefix + omit, (real_plen + 7) / 8 - omit);
1248 if(is_ss) {
1249 accumulate_byte(buf, SUBTLV_SOURCE_PREFIX);
1250 accumulate_byte(buf, 1 + spb);
1251 accumulate_byte(buf, real_src_plen);
1252 accumulate_bytes(buf, real_src_prefix, spb);
1253 }
1254 /* Note that an empty channels TLV is different from no such TLV. */
1255 if(channels_size > 0) {
1256 accumulate_byte(buf, 2);
1257 accumulate_byte(buf, channels_len);
1258 if(channels_len > 0)
1259 accumulate_bytes(buf, channels, channels_len);
1260 }
1261 end_message(buf, MESSAGE_UPDATE, len);
1262 if(flags & 0x80) {
1263 memcpy(buf->prefix, prefix, 16);
1264 buf->have_prefix = 1;
1265 }
1266 }
1267
1268 static void
really_send_update(struct interface * ifp,const unsigned char * id,const unsigned char * prefix,unsigned char plen,const unsigned char * src_prefix,unsigned char src_plen,unsigned short seqno,unsigned short metric,unsigned char * channels,int channels_len)1269 really_send_update(struct interface *ifp, const unsigned char *id,
1270 const unsigned char *prefix, unsigned char plen,
1271 const unsigned char *src_prefix, unsigned char src_plen,
1272 unsigned short seqno, unsigned short metric,
1273 unsigned char *channels, int channels_len)
1274 {
1275 if(!if_up(ifp))
1276 return;
1277
1278 if((ifp->flags & IF_UNICAST) != 0) {
1279 struct neighbour *neigh;
1280 FOR_ALL_NEIGHBOURS(neigh) {
1281 if(neigh->ifp == ifp) {
1282 really_buffer_update(&neigh->buf, ifp, id,
1283 prefix, plen, src_prefix, src_plen,
1284 seqno, metric, channels, channels_len);
1285 }
1286 }
1287 } else {
1288 really_buffer_update(&ifp->buf, ifp, id,
1289 prefix, plen, src_prefix, src_plen,
1290 seqno, metric, channels, channels_len);
1291 }
1292 }
1293
1294 static int
compare_buffered_updates(const void * av,const void * bv)1295 compare_buffered_updates(const void *av, const void *bv)
1296 {
1297 const struct buffered_update *a = av, *b = bv;
1298 int rc, v4a, v4b, ma, mb;
1299
1300 rc = memcmp(a->id, b->id, 8);
1301 if(rc != 0)
1302 return rc;
1303
1304 v4a = (a->plen >= 96 && v4mapped(a->prefix));
1305 v4b = (b->plen >= 96 && v4mapped(b->prefix));
1306
1307 if(v4a > v4b)
1308 return 1;
1309 else if(v4a < v4b)
1310 return -1;
1311
1312 ma = (!v4a && a->plen == 128 && memcmp(a->prefix + 8, a->id, 8) == 0);
1313 mb = (!v4b && b->plen == 128 && memcmp(b->prefix + 8, b->id, 8) == 0);
1314
1315 if(ma > mb)
1316 return -1;
1317 else if(mb > ma)
1318 return 1;
1319
1320 if(a->plen < b->plen)
1321 return 1;
1322 else if(a->plen > b->plen)
1323 return -1;
1324
1325 rc = memcmp(a->prefix, b->prefix, 16);
1326 if(rc != 0)
1327 return rc;
1328
1329 if(a->src_plen < b->src_plen)
1330 return -1;
1331 else if(a->src_plen > b->src_plen)
1332 return 1;
1333
1334 return memcmp(a->src_prefix, b->src_prefix, 16);
1335 }
1336
1337 void
flushupdates(struct interface * ifp)1338 flushupdates(struct interface *ifp)
1339 {
1340 struct xroute *xroute;
1341 struct babel_route *route;
1342 const unsigned char *last_prefix = NULL;
1343 const unsigned char *last_src_prefix = NULL;
1344 unsigned char last_plen = 0xFF;
1345 unsigned char last_src_plen = 0xFF;
1346 int i;
1347
1348 if(ifp == NULL) {
1349 struct interface *ifp_aux;
1350 FOR_ALL_INTERFACES(ifp_aux)
1351 flushupdates(ifp_aux);
1352 return;
1353 }
1354
1355 if(ifp->num_buffered_updates > 0) {
1356 struct buffered_update *b = ifp->buffered_updates;
1357 int n = ifp->num_buffered_updates;
1358
1359 ifp->buffered_updates = NULL;
1360 ifp->update_bufsize = 0;
1361 ifp->num_buffered_updates = 0;
1362
1363 if(!if_up(ifp))
1364 goto done;
1365
1366 debugf(" (flushing %d buffered updates on %s (%d))\n",
1367 n, ifp->name, ifp->ifindex);
1368
1369 /* In order to send fewer update messages, we want to send updates
1370 with the same router-id together, with IPv6 going out before IPv4. */
1371
1372 for(i = 0; i < n; i++) {
1373 route = find_installed_route(b[i].prefix, b[i].plen,
1374 b[i].src_prefix, b[i].src_plen);
1375 if(route)
1376 memcpy(b[i].id, route->src->id, 8);
1377 else
1378 memcpy(b[i].id, myid, 8);
1379 }
1380
1381 qsort(b, n, sizeof(struct buffered_update), compare_buffered_updates);
1382
1383 for(i = 0; i < n; i++) {
1384 /* The same update may be scheduled multiple times before it is
1385 sent out. Since our buffer is now sorted, it is enough to
1386 compare with the previous update. */
1387
1388 if(last_prefix &&
1389 b[i].plen == last_plen &&
1390 b[i].src_plen == last_src_plen &&
1391 memcmp(b[i].prefix, last_prefix, 16) == 0 &&
1392 memcmp(b[i].src_prefix, last_src_prefix, 16) == 0)
1393 continue;
1394
1395 xroute = find_xroute(b[i].prefix, b[i].plen,
1396 b[i].src_prefix, b[i].src_plen);
1397 route = find_installed_route(b[i].prefix, b[i].plen,
1398 b[i].src_prefix, b[i].src_plen);
1399
1400 if(xroute && (!route || xroute->metric <= kernel_metric)) {
1401 really_send_update(ifp, myid,
1402 xroute->prefix, xroute->plen,
1403 xroute->src_prefix, xroute->src_plen,
1404 myseqno, xroute->metric,
1405 NULL, 0);
1406 last_prefix = xroute->prefix;
1407 last_plen = xroute->plen;
1408 last_src_prefix = xroute->src_prefix;
1409 last_src_plen = xroute->src_plen;
1410 } else if(route) {
1411 unsigned char channels[MAX_CHANNEL_HOPS];
1412 int chlen;
1413 struct interface *route_ifp = route->neigh->ifp;
1414 unsigned short metric;
1415 unsigned short seqno;
1416
1417 seqno = route->seqno;
1418 metric =
1419 route_interferes(route, ifp) ?
1420 route_metric(route) :
1421 route_metric_noninterfering(route);
1422
1423 if(metric < INFINITY)
1424 satisfy_request(route->src->prefix, route->src->plen,
1425 route->src->src_prefix,
1426 route->src->src_plen,
1427 seqno, route->src->id, ifp);
1428
1429 if((ifp->flags & IF_SPLIT_HORIZON) &&
1430 route->neigh->ifp == ifp)
1431 continue;
1432
1433 if(route_ifp->channel == IF_CHANNEL_NONINTERFERING) {
1434 chlen = MIN(route->channels_len, MAX_CHANNEL_HOPS);
1435 if(chlen > 0)
1436 memcpy(channels, route->channels, chlen);
1437 } else {
1438 if(route_ifp->channel == IF_CHANNEL_UNKNOWN)
1439 channels[0] = IF_CHANNEL_INTERFERING;
1440 else {
1441 assert(route_ifp->channel > 0 &&
1442 route_ifp->channel <= 255);
1443 channels[0] = route_ifp->channel;
1444 }
1445 memcpy(channels + 1, route->channels,
1446 MIN(route->channels_len, MAX_CHANNEL_HOPS - 1));
1447 chlen = 1 + MIN(route->channels_len, MAX_CHANNEL_HOPS - 1);
1448 }
1449
1450 really_send_update(ifp, route->src->id,
1451 route->src->prefix, route->src->plen,
1452 route->src->src_prefix,
1453 route->src->src_plen,
1454 seqno, metric,
1455 channels, chlen);
1456 update_source(route->src, seqno, metric);
1457 last_prefix = route->src->prefix;
1458 last_plen = route->src->plen;
1459 last_src_prefix = route->src->src_prefix;
1460 last_src_plen = route->src->src_plen;
1461 } else {
1462 /* There's no route for this prefix. This can happen shortly
1463 after an xroute has been retracted, so send a retraction. */
1464 really_send_update(ifp, myid,
1465 b[i].prefix, b[i].plen,
1466 b[i].src_prefix, b[i].src_plen,
1467 myseqno, INFINITY, NULL, -1);
1468 }
1469 }
1470
1471 if((ifp->flags & IF_UNICAST) != 0) {
1472 struct neighbour *neigh;
1473 FOR_ALL_NEIGHBOURS(neigh) {
1474 if(neigh->ifp == ifp) {
1475 schedule_flush_now(&neigh->buf);
1476 }
1477 }
1478 } else {
1479 schedule_flush_now(&ifp->buf);
1480 }
1481 done:
1482 free(b);
1483 }
1484 ifp->update_flush_timeout.tv_sec = 0;
1485 ifp->update_flush_timeout.tv_usec = 0;
1486 }
1487
1488 static void
schedule_update_flush(struct interface * ifp,int urgent)1489 schedule_update_flush(struct interface *ifp, int urgent)
1490 {
1491 unsigned msecs;
1492 msecs = update_jitter(ifp, urgent);
1493 if(ifp->update_flush_timeout.tv_sec != 0 &&
1494 timeval_minus_msec(&ifp->update_flush_timeout, &now) < msecs)
1495 return;
1496 set_timeout(&ifp->update_flush_timeout, msecs);
1497 }
1498
1499 static void
buffer_update(struct interface * ifp,const unsigned char * prefix,unsigned char plen,const unsigned char * src_prefix,unsigned char src_plen)1500 buffer_update(struct interface *ifp,
1501 const unsigned char *prefix, unsigned char plen,
1502 const unsigned char *src_prefix, unsigned char src_plen)
1503 {
1504 if(ifp->num_buffered_updates > 0 &&
1505 ifp->num_buffered_updates >= ifp->update_bufsize)
1506 flushupdates(ifp);
1507
1508 if(ifp->update_bufsize == 0) {
1509 int n;
1510 assert(ifp->buffered_updates == NULL);
1511 /* Allocate enough space to hold a full update. Since the
1512 number of installed routes will grow over time, make sure we
1513 have enough space to send a full-ish frame. */
1514 n = installed_routes_estimate() + xroutes_estimate() + 4;
1515 n = MAX(n, ifp->buf.size / 16);
1516 again:
1517 ifp->buffered_updates = malloc(n * sizeof(struct buffered_update));
1518 if(ifp->buffered_updates == NULL) {
1519 perror("malloc(buffered_updates)");
1520 if(n > 4) {
1521 /* Try again with a tiny buffer. */
1522 n = 4;
1523 goto again;
1524 }
1525 return;
1526 }
1527 ifp->update_bufsize = n;
1528 ifp->num_buffered_updates = 0;
1529 }
1530
1531 memcpy(ifp->buffered_updates[ifp->num_buffered_updates].prefix,
1532 prefix, 16);
1533 ifp->buffered_updates[ifp->num_buffered_updates].plen = plen;
1534 memcpy(ifp->buffered_updates[ifp->num_buffered_updates].src_prefix,
1535 src_prefix, 16);
1536 ifp->buffered_updates[ifp->num_buffered_updates].src_plen = src_plen;
1537 ifp->num_buffered_updates++;
1538 }
1539
1540 /* Full wildcard update with prefix == src_prefix == NULL,
1541 Standard wildcard update with prefix == NULL && src_prefix != NULL,
1542 Specific wildcard update with prefix != NULL && src_prefix == NULL. */
1543 void
send_update(struct interface * ifp,int urgent,const unsigned char * prefix,unsigned char plen,const unsigned char * src_prefix,unsigned char src_plen)1544 send_update(struct interface *ifp, int urgent,
1545 const unsigned char *prefix, unsigned char plen,
1546 const unsigned char *src_prefix, unsigned char src_plen)
1547 {
1548 if(ifp == NULL) {
1549 struct interface *ifp_aux;
1550 struct babel_route *route;
1551 FOR_ALL_INTERFACES(ifp_aux)
1552 send_update(ifp_aux, urgent, prefix, plen, src_prefix, src_plen);
1553 if(prefix) {
1554 /* Since flushupdates only deals with non-wildcard interfaces, we
1555 need to do this now. */
1556 route = find_installed_route(prefix, plen, src_prefix, src_plen);
1557 if(route && route_metric(route) < INFINITY)
1558 satisfy_request(prefix, plen, src_prefix, src_plen,
1559 route->src->seqno, route->src->id, NULL);
1560 }
1561 return;
1562 }
1563
1564 if(!if_up(ifp))
1565 return;
1566
1567 if(prefix && src_prefix) {
1568 debugf("Sending update to %s for %s from %s.\n",
1569 ifp->name, format_prefix(prefix, plen),
1570 format_prefix(src_prefix, src_plen));
1571 buffer_update(ifp, prefix, plen, src_prefix, src_plen);
1572 } else if(prefix || src_prefix) {
1573 struct route_stream *routes;
1574 send_self_update(ifp);
1575 debugf("Sending update to %s for any.\n", ifp->name);
1576 routes = route_stream(1);
1577 if(routes) {
1578 while(1) {
1579 int is_ss;
1580 struct babel_route *route = route_stream_next(routes);
1581 if(route == NULL)
1582 break;
1583 is_ss = !is_default(route->src->src_prefix,
1584 route->src->src_plen);
1585 if((src_prefix && is_ss) || (prefix && !is_ss))
1586 continue;
1587 buffer_update(ifp, route->src->prefix, route->src->plen,
1588 route->src->src_prefix, route->src->src_plen);
1589 }
1590 route_stream_done(routes);
1591 } else {
1592 fprintf(stderr, "Couldn't allocate route stream.\n");
1593 }
1594 set_timeout(&ifp->update_timeout, ifp->update_interval);
1595 ifp->last_update_time = now.tv_sec;
1596 } else {
1597 send_update(ifp, urgent, NULL, 0, zeroes, 0);
1598 send_update(ifp, urgent, zeroes, 0, NULL, 0);
1599 }
1600 schedule_update_flush(ifp, urgent);
1601 }
1602
1603 void
send_update_resend(struct interface * ifp,const unsigned char * prefix,unsigned char plen,const unsigned char * src_prefix,unsigned char src_plen)1604 send_update_resend(struct interface *ifp,
1605 const unsigned char *prefix, unsigned char plen,
1606 const unsigned char *src_prefix, unsigned char src_plen)
1607 {
1608 assert(prefix != NULL);
1609
1610 send_update(ifp, 1, prefix, plen, src_prefix, src_plen);
1611 record_resend(RESEND_UPDATE, prefix, plen, src_prefix, src_plen,
1612 0, NULL, NULL, resend_delay);
1613 }
1614
1615 void
buffer_wildcard_retraction(struct buffered * buf,struct interface * ifp)1616 buffer_wildcard_retraction(struct buffered *buf, struct interface *ifp)
1617 {
1618 start_message(buf, ifp, MESSAGE_UPDATE, 10);
1619 accumulate_byte(buf, 0);
1620 accumulate_byte(buf, 0);
1621 accumulate_byte(buf, 0);
1622 accumulate_byte(buf, 0);
1623 accumulate_short(buf, 0xFFFF);
1624 accumulate_short(buf, myseqno);
1625 accumulate_short(buf, 0xFFFF);
1626 end_message(buf, MESSAGE_UPDATE, 10);
1627
1628 buf->have_id = 0;
1629 }
1630
1631
1632 void
send_wildcard_retraction(struct interface * ifp)1633 send_wildcard_retraction(struct interface *ifp)
1634 {
1635 if(ifp == NULL) {
1636 struct interface *ifp_aux;
1637 FOR_ALL_INTERFACES(ifp_aux)
1638 send_wildcard_retraction(ifp_aux);
1639 return;
1640 }
1641
1642 if(!if_up(ifp))
1643 return;
1644
1645 if((ifp->flags & IF_UNICAST) != 0) {
1646 struct neighbour *neigh;
1647 FOR_ALL_NEIGHBOURS(neigh) {
1648 if(neigh->ifp == ifp) {
1649 buffer_wildcard_retraction(&neigh->buf, neigh->ifp);
1650 }
1651 }
1652 } else {
1653 buffer_wildcard_retraction(&ifp->buf, ifp);
1654 }
1655 }
1656
1657 void
update_myseqno()1658 update_myseqno()
1659 {
1660 myseqno = seqno_plus(myseqno, 1);
1661 seqno_time = now;
1662 }
1663
1664 void
send_self_update(struct interface * ifp)1665 send_self_update(struct interface *ifp)
1666 {
1667 struct xroute_stream *xroutes;
1668 if(ifp == NULL) {
1669 struct interface *ifp_aux;
1670 FOR_ALL_INTERFACES(ifp_aux) {
1671 if(!if_up(ifp_aux))
1672 continue;
1673 send_self_update(ifp_aux);
1674 }
1675 return;
1676 }
1677
1678 debugf("Sending self update to %s.\n", ifp->name);
1679 xroutes = xroute_stream();
1680 if(xroutes) {
1681 while(1) {
1682 struct xroute *xroute = xroute_stream_next(xroutes);
1683 if(xroute == NULL) break;
1684 send_update(ifp, 0, xroute->prefix, xroute->plen,
1685 xroute->src_prefix, xroute->src_plen);
1686 }
1687 xroute_stream_done(xroutes);
1688 } else {
1689 fprintf(stderr, "Couldn't allocate xroute stream.\n");
1690 }
1691 }
1692
1693 void
buffer_ihu(struct buffered * buf,struct interface * ifp,unsigned short rxcost,unsigned short interval,const unsigned char * address,int rtt_data,unsigned int t1,unsigned int t2)1694 buffer_ihu(struct buffered *buf, struct interface *ifp, unsigned short rxcost,
1695 unsigned short interval, const unsigned char *address,
1696 int rtt_data, unsigned int t1, unsigned int t2)
1697 {
1698 int msglen, ll;
1699
1700 ll = linklocal(address);
1701 msglen = (ll ? 14 : 22) + (rtt_data ? 10 : 0);
1702
1703 start_message(buf, ifp, MESSAGE_IHU, msglen);
1704 accumulate_byte(buf, ll ? 3 : 2);
1705 accumulate_byte(buf, 0);
1706 accumulate_short(buf, rxcost);
1707 accumulate_short(buf, interval);
1708 if(ll)
1709 accumulate_bytes(buf, address + 8, 8);
1710 else
1711 accumulate_bytes(buf, address, 16);
1712 if(rtt_data) {
1713 accumulate_byte(buf, SUBTLV_TIMESTAMP);
1714 accumulate_byte(buf, 8);
1715 accumulate_int(buf, t1);
1716 accumulate_int(buf, t2);
1717 }
1718 end_message(buf, MESSAGE_IHU, msglen);
1719 }
1720
1721
1722 void
send_ihu(struct neighbour * neigh,struct interface * ifp)1723 send_ihu(struct neighbour *neigh, struct interface *ifp)
1724 {
1725 int rxcost, interval;
1726 int send_rtt_data;
1727 int unicast;
1728
1729 if(neigh == NULL && ifp == NULL) {
1730 struct interface *ifp_aux;
1731 FOR_ALL_INTERFACES(ifp_aux) {
1732 if(if_up(ifp_aux))
1733 send_ihu(NULL, ifp_aux);
1734 }
1735 return;
1736 }
1737
1738 if(neigh == NULL) {
1739 struct neighbour *ngh;
1740 FOR_ALL_NEIGHBOURS(ngh) {
1741 if(ngh->ifp == ifp)
1742 send_ihu(ngh, ifp);
1743 }
1744 return;
1745 }
1746
1747
1748 if(ifp && neigh->ifp != ifp)
1749 return;
1750
1751 ifp = neigh->ifp;
1752 if(!if_up(ifp))
1753 return;
1754
1755 rxcost = neighbour_rxcost(neigh);
1756 interval = (ifp->hello_interval * 3 + 9) / 10;
1757
1758 debugf("Sending ihu %d on %s to %s.\n",
1759 rxcost,
1760 neigh->ifp->name,
1761 format_address(neigh->address));
1762
1763 /* If we already have unicast data buffered for this peer, piggyback
1764 the IHU. Only do that if RFC 6126 compatibility is disabled, since
1765 doing that might require sending an unscheduled unicast Hello. */
1766 unicast = !!(ifp->flags & IF_UNICAST) ||
1767 (neigh->buf.len > 0 && !(ifp->flags & IF_RFC6126));
1768
1769
1770 if(!!(ifp->flags & IF_TIMESTAMPS) != 0 && neigh->hello_send_us &&
1771 /* Checks whether the RTT data is not too old to be sent. */
1772 timeval_minus_msec(&now, &neigh->hello_rtt_receive_time) < 1000000) {
1773 send_rtt_data = 1;
1774 } else {
1775 neigh->hello_send_us = 0;
1776 send_rtt_data = 0;
1777 }
1778
1779 if(send_rtt_data) {
1780 /* Ensure that there is a Hello in the same packet. */
1781 ensure_space(unicast ? &neigh->buf : &ifp->buf, ifp, 14 + 16);
1782 if(unicast)
1783 send_unicast_hello(neigh, 0, 0);
1784 else
1785 send_multicast_hello(ifp, 0, 0);
1786 }
1787
1788 buffer_ihu(unicast ? &neigh->buf : &ifp->buf,
1789 ifp, rxcost, interval, neigh->address,
1790 send_rtt_data, neigh->hello_send_us,
1791 time_us(neigh->hello_rtt_receive_time));
1792
1793 }
1794
1795 /* Send IHUs to all marginal neighbours */
1796 void
send_marginal_ihu(struct interface * ifp)1797 send_marginal_ihu(struct interface *ifp)
1798 {
1799 struct neighbour *neigh;
1800 FOR_ALL_NEIGHBOURS(neigh) {
1801 if(ifp && neigh->ifp != ifp)
1802 continue;
1803 if(neigh->txcost >= 384 || (neigh->hello.reach & 0xF000) != 0xF000)
1804 send_ihu(neigh, ifp);
1805 }
1806 }
1807
1808 /* Standard wildcard request with prefix == NULL && src_prefix == zeroes,
1809 Specific wildcard request with prefix == zeroes && src_prefix == NULL. */
1810 static void
send_request(struct buffered * buf,struct interface * ifp,const unsigned char * prefix,unsigned char plen,const unsigned char * src_prefix,unsigned char src_plen)1811 send_request(struct buffered *buf, struct interface *ifp,
1812 const unsigned char *prefix, unsigned char plen,
1813 const unsigned char *src_prefix, unsigned char src_plen)
1814 {
1815 int v4, pb, spb, len;
1816 int is_ss = !is_default(src_prefix, src_plen);
1817
1818 if(is_ss && (ifp->flags & IF_RFC6126) != 0)
1819 return;
1820
1821 if(!prefix) {
1822 assert(!src_prefix);
1823 debugf("sending request for any.\n");
1824 start_message(buf, ifp, MESSAGE_REQUEST, 2);
1825 accumulate_byte(buf, 0);
1826 accumulate_byte(buf, 0);
1827 end_message(buf, MESSAGE_REQUEST, 2);
1828 return;
1829 }
1830
1831 debugf("sending request for %s from %s.\n",
1832 format_prefix(prefix, plen),
1833 format_prefix(src_prefix, src_plen));
1834
1835 v4 = plen >= 96 && v4mapped(prefix);
1836 pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
1837 spb = v4 ? ((src_plen - 96) + 7) / 8 : (src_plen + 7) / 8;
1838 len = 2 + pb + (is_ss ? 3 + spb : 0);
1839
1840 start_message(buf, ifp, MESSAGE_REQUEST, len);
1841 accumulate_byte(buf, v4 ? 1 : 2);
1842 accumulate_byte(buf, v4 ? plen - 96 : plen);
1843 if(v4)
1844 accumulate_bytes(buf, prefix + 12, pb);
1845 else
1846 accumulate_bytes(buf, prefix, pb);
1847 if(is_ss) {
1848 accumulate_byte(buf, SUBTLV_SOURCE_PREFIX);
1849 accumulate_byte(buf, 1 + spb);
1850 accumulate_byte(buf, v4 ? src_plen - 96 : src_plen);
1851 if(v4)
1852 accumulate_bytes(buf, src_prefix + 12, spb);
1853 else
1854 accumulate_bytes(buf, src_prefix, spb);
1855 }
1856 end_message(buf, MESSAGE_REQUEST, len);
1857 }
1858
1859 void
send_multicast_request(struct interface * ifp,const unsigned char * prefix,unsigned char plen,const unsigned char * src_prefix,unsigned char src_plen)1860 send_multicast_request(struct interface *ifp,
1861 const unsigned char *prefix, unsigned char plen,
1862 const unsigned char *src_prefix, unsigned char src_plen)
1863 {
1864 if(ifp == NULL) {
1865 struct interface *ifp_auxn;
1866 FOR_ALL_INTERFACES(ifp_auxn) {
1867 if(!if_up(ifp_auxn))
1868 continue;
1869 send_multicast_request(ifp_auxn, prefix, plen, src_prefix, src_plen);
1870 }
1871 return;
1872 }
1873
1874 if(!if_up(ifp))
1875 return;
1876
1877 /* make sure any buffered updates go out before this request. */
1878 flushupdates(ifp);
1879
1880 if((ifp->flags & IF_UNICAST) != 0) {
1881 struct neighbour *neigh;
1882 FOR_ALL_NEIGHBOURS(neigh) {
1883 if(neigh->ifp == ifp) {
1884 send_request(&neigh->buf, ifp, prefix, plen,
1885 src_prefix, src_plen);
1886 }
1887 }
1888 } else {
1889 send_request(&ifp->buf, ifp, prefix, plen, src_prefix, src_plen);
1890 }
1891 }
1892
1893 void
send_unicast_request(struct neighbour * neigh,const unsigned char * prefix,unsigned char plen,const unsigned char * src_prefix,unsigned char src_plen)1894 send_unicast_request(struct neighbour *neigh,
1895 const unsigned char *prefix, unsigned char plen,
1896 const unsigned char *src_prefix, unsigned char src_plen)
1897 {
1898 if(!if_up(neigh->ifp))
1899 return;
1900
1901 flushupdates(neigh->ifp);
1902
1903 send_request(&neigh->buf, neigh->ifp, prefix, plen, src_prefix, src_plen);
1904 }
1905
1906 static void
send_multihop_request(struct buffered * buf,struct interface * ifp,const unsigned char * prefix,unsigned char plen,const unsigned char * src_prefix,unsigned char src_plen,unsigned short seqno,const unsigned char * id,unsigned short hop_count)1907 send_multihop_request(struct buffered *buf, struct interface *ifp,
1908 const unsigned char *prefix, unsigned char plen,
1909 const unsigned char *src_prefix, unsigned char src_plen,
1910 unsigned short seqno, const unsigned char *id,
1911 unsigned short hop_count)
1912 {
1913 int v4, pb, spb, len;
1914 int is_ss = !is_default(src_prefix, src_plen);
1915
1916 if(is_ss && (ifp->flags & IF_RFC6126) != 0)
1917 return;
1918
1919 debugf("Sending request (%d) for %s.\n",
1920 hop_count, format_prefix(prefix, plen));
1921
1922 v4 = plen >= 96 && v4mapped(prefix);
1923 pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
1924 spb = v4 ? ((src_plen - 96) + 7) / 8 : (src_plen + 7) / 8;
1925 len = 6 + 8 + pb + (is_ss ? 3 + spb : 0);
1926
1927 start_message(buf, ifp, MESSAGE_MH_REQUEST, len);
1928 accumulate_byte(buf, v4 ? 1 : 2);
1929 accumulate_byte(buf, v4 ? plen - 96 : plen);
1930 accumulate_short(buf, seqno);
1931 accumulate_byte(buf, hop_count);
1932 accumulate_byte(buf, v4 ? src_plen - 96 : src_plen);
1933 accumulate_bytes(buf, id, 8);
1934 if(prefix) {
1935 if(v4)
1936 accumulate_bytes(buf, prefix + 12, pb);
1937 else
1938 accumulate_bytes(buf, prefix, pb);
1939 }
1940 if(is_ss) {
1941 accumulate_byte(buf, SUBTLV_SOURCE_PREFIX);
1942 accumulate_byte(buf, 1 + spb);
1943 accumulate_byte(buf, v4 ? src_plen - 96 : src_plen);
1944 if(v4)
1945 accumulate_bytes(buf, src_prefix + 12, spb);
1946 else
1947 accumulate_bytes(buf, src_prefix, spb);
1948 }
1949 end_message(buf, MESSAGE_MH_REQUEST, len);
1950 }
1951
1952 void
send_multicast_multihop_request(struct interface * ifp,const unsigned char * prefix,unsigned char plen,const unsigned char * src_prefix,unsigned char src_plen,unsigned short seqno,const unsigned char * id,unsigned short hop_count)1953 send_multicast_multihop_request(struct interface *ifp,
1954 const unsigned char *prefix, unsigned char plen,
1955 const unsigned char *src_prefix, unsigned char src_plen,
1956 unsigned short seqno, const unsigned char *id,
1957 unsigned short hop_count)
1958 {
1959 if(ifp == NULL) {
1960 struct interface *ifp_aux;
1961 FOR_ALL_INTERFACES(ifp_aux) {
1962 if(!if_up(ifp_aux))
1963 continue;
1964 send_multicast_multihop_request(ifp_aux,
1965 prefix, plen, src_prefix, src_plen,
1966 seqno, id, hop_count);
1967 }
1968 return;
1969 }
1970
1971 flushupdates(ifp);
1972
1973 if(!if_up(ifp))
1974 return;
1975
1976 if((ifp->flags & IF_UNICAST) != 0) {
1977 struct neighbour *neigh;
1978 FOR_ALL_NEIGHBOURS(neigh) {
1979 if(neigh->ifp == ifp) {
1980 send_multihop_request(&neigh->buf, neigh->ifp,
1981 prefix, plen,
1982 src_prefix, src_plen,
1983 seqno, id, hop_count);
1984 }
1985 }
1986 } else {
1987 send_multihop_request(&ifp->buf, ifp,
1988 prefix, plen,
1989 src_prefix, src_plen,
1990 seqno, id, hop_count);
1991 }
1992 }
1993
1994 void
send_unicast_multihop_request(struct neighbour * neigh,const unsigned char * prefix,unsigned char plen,const unsigned char * src_prefix,unsigned char src_plen,unsigned short seqno,const unsigned char * id,unsigned short hop_count)1995 send_unicast_multihop_request(struct neighbour *neigh,
1996 const unsigned char *prefix, unsigned char plen,
1997 const unsigned char *src_prefix,
1998 unsigned char src_plen,
1999 unsigned short seqno, const unsigned char *id,
2000 unsigned short hop_count)
2001 {
2002 flushupdates(neigh->ifp);
2003 send_multihop_request(&neigh->buf, neigh->ifp,
2004 prefix, plen, src_prefix, src_plen,
2005 seqno, id, hop_count);
2006 }
2007
2008 /* Send a request to a well-chosen neighbour and resend. If there is no
2009 good neighbour, send over multicast but only once. */
2010 void
send_request_resend(const unsigned char * prefix,unsigned char plen,const unsigned char * src_prefix,unsigned char src_plen,unsigned short seqno,unsigned char * id)2011 send_request_resend(const unsigned char *prefix, unsigned char plen,
2012 const unsigned char *src_prefix, unsigned char src_plen,
2013 unsigned short seqno, unsigned char *id)
2014 {
2015 struct babel_route *route;
2016
2017 route = find_best_route(prefix, plen, src_prefix, src_plen, 0, NULL);
2018
2019 if(route) {
2020 struct neighbour *neigh = route->neigh;
2021 send_unicast_multihop_request(neigh, prefix, plen, src_prefix, src_plen,
2022 seqno, id, 127);
2023 record_resend(RESEND_REQUEST, prefix, plen, src_prefix, src_plen, seqno,
2024 id, neigh->ifp, resend_delay);
2025 } else {
2026 struct interface *ifp;
2027 FOR_ALL_INTERFACES(ifp) {
2028 if(!if_up(ifp)) continue;
2029 send_multihop_request(&ifp->buf, ifp,
2030 prefix, plen, src_prefix, src_plen,
2031 seqno, id, 127);
2032 }
2033 }
2034 }
2035
2036 void
handle_request(struct neighbour * neigh,const unsigned char * prefix,unsigned char plen,const unsigned char * src_prefix,unsigned char src_plen,unsigned char hop_count,unsigned short seqno,const unsigned char * id)2037 handle_request(struct neighbour *neigh, const unsigned char *prefix,
2038 unsigned char plen,
2039 const unsigned char *src_prefix, unsigned char src_plen,
2040 unsigned char hop_count,
2041 unsigned short seqno, const unsigned char *id)
2042 {
2043 struct xroute *xroute;
2044 struct babel_route *route;
2045 struct neighbour *successor = NULL;
2046
2047 xroute = find_xroute(prefix, plen, src_prefix, src_plen);
2048 route = find_installed_route(prefix, plen, src_prefix, src_plen);
2049
2050 if(xroute && (!route || xroute->metric <= kernel_metric)) {
2051 if(hop_count > 0 && memcmp(id, myid, 8) == 0) {
2052 if(seqno_compare(seqno, myseqno) > 0) {
2053 if(seqno_minus(seqno, myseqno) > 100) {
2054 /* Hopelessly out-of-date request */
2055 return;
2056 }
2057 update_myseqno();
2058 }
2059 }
2060 send_update(neigh->ifp, 1, prefix, plen, src_prefix, src_plen);
2061 return;
2062 }
2063
2064 if(route &&
2065 (memcmp(id, route->src->id, 8) != 0 ||
2066 seqno_compare(seqno, route->seqno) <= 0)) {
2067 send_update(neigh->ifp, 1, prefix, plen, src_prefix, src_plen);
2068 return;
2069 }
2070
2071 if(hop_count <= 1)
2072 return;
2073
2074 if(route && memcmp(id, route->src->id, 8) == 0 &&
2075 seqno_minus(seqno, route->seqno) > 100) {
2076 /* Hopelessly out-of-date */
2077 return;
2078 }
2079
2080 if(request_redundant(neigh->ifp, prefix, plen, src_prefix, src_plen,
2081 seqno, id))
2082 return;
2083
2084 /* Let's try to forward this request. */
2085 if(route && route_metric(route) < INFINITY)
2086 successor = route->neigh;
2087
2088 if(!successor || successor == neigh) {
2089 /* We were about to forward a request to its requestor. Try to
2090 find a different neighbour to forward the request to. */
2091 struct babel_route *other_route;
2092
2093 other_route = find_best_route(prefix, plen, src_prefix, src_plen,
2094 0, neigh);
2095 if(other_route && route_metric(other_route) < INFINITY)
2096 successor = other_route->neigh;
2097 }
2098
2099 if(!successor || successor == neigh)
2100 /* Give up */
2101 return;
2102
2103 send_unicast_multihop_request(successor, prefix, plen, src_prefix, src_plen,
2104 seqno, id, hop_count - 1);
2105 record_resend(RESEND_REQUEST, prefix, plen, src_prefix, src_plen, seqno, id,
2106 neigh->ifp, 0);
2107 }
2108