info: java: update workspace
[olsrd.git] / src / lq_packet.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon (olsrd)
3  *
4  * (c) by the OLSR project
5  *
6  * See our Git repository to find out who worked on this file
7  * and thus is a copyright holder on it.
8  *
9  * All rights reserved.
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  *
15  * * Redistributions of source code must retain the above copyright
16  *   notice, this list of conditions and the following disclaimer.
17  * * Redistributions in binary form must reproduce the above copyright
18  *   notice, this list of conditions and the following disclaimer in
19  *   the documentation and/or other materials provided with the
20  *   distribution.
21  * * Neither the name of olsr.org, olsrd nor the names of its
22  *   contributors may be used to endorse or promote products derived
23  *   from this software without specific prior written permission.
24  *
25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
28  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
29  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
30  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
31  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
32  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
33  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
35  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36  * POSSIBILITY OF SUCH DAMAGE.
37  *
38  * Visit http://www.olsr.org for more information.
39  *
40  * If you find this software useful feel free to make a donation
41  * to the project. For more information see the website or contact
42  * the copyright holders.
43  *
44  */
45
46 #include <assert.h>
47
48 #include "ipcalc.h"
49 #include "olsr_protocol.h"
50 #include "defs.h"
51 #include "lq_packet.h"
52 #include "interfaces.h"
53 #include "link_set.h"
54 #include "neighbor_table.h"
55 #include "mpr_selector_set.h"
56 #include "mid_set.h"
57 #include "mantissa.h"
58 #include "process_package.h"    // XXX - remove
59 #include "two_hop_neighbor_table.h"
60 #include "hysteresis.h"
61 #include "olsr.h"
62 #include "build_msg.h"
63 #include "net_olsr.h"
64 #include "lq_plugin.h"
65
66 bool lq_tc_pending = false;
67
68 static uint32_t msg_buffer_aligned[(MAXMESSAGESIZE - OLSR_HEADERSIZE) / sizeof(uint32_t) + 1];
69 static unsigned char *const msg_buffer = (unsigned char *)msg_buffer_aligned;
70
71 static struct lq_hello_neighbor *neigh_find(struct lq_hello_message *lq_hello, struct link_entry *walker) {
72   struct lq_hello_neighbor *neigh;
73
74   assert(lq_hello);
75   assert(walker);
76
77   for (neigh = lq_hello->neigh; neigh; neigh = neigh->next) {
78     if (ipequal(&neigh->addr, &walker->neighbor_iface_addr)) {
79       return neigh;
80     }
81   }
82
83   return NULL;
84 }
85
86 static void
87 create_lq_hello(struct lq_hello_message *lq_hello, struct interface_olsr *outif)
88 {
89   struct link_entry *walker;
90
91   // initialize the static fields
92
93   lq_hello->comm.type = LQ_HELLO_MESSAGE;
94   lq_hello->comm.vtime = me_to_reltime(outif->valtimes.hello);
95   lq_hello->comm.size = 0;
96
97   lq_hello->comm.orig = olsr_cnf->main_addr;
98
99   lq_hello->comm.ttl = 1;
100   lq_hello->comm.hops = 0;
101
102   lq_hello->htime = outif->hello_etime;
103   lq_hello->will = olsr_cnf->willingness;
104
105   lq_hello->neigh = NULL;
106
107   // loop through the link set
108
109   OLSR_FOR_ALL_LINK_ENTRIES(walker) {
110     struct lq_hello_neighbor *neigh;
111     bool neigh_is_new = false;
112     uint8_t link_type;
113
114     // allocate a neighbour entry
115     neigh = neigh_find(lq_hello, walker);
116     if (!neigh) {
117       neigh = olsr_malloc_lq_hello_neighbor("Build LQ_HELLO");
118       neigh_is_new = true;
119     }
120
121     // a) this neighbor interface IS NOT visible via the output interface
122     if (!ipequal(&walker->local_iface_addr, &outif->ip_addr))
123       link_type = UNSPEC_LINK;
124
125     // b) this neighbor interface IS visible via the output interface
126
127     else
128       link_type = lookup_link_status(walker);
129
130     if (neigh_is_new || ((neigh->link_type == UNSPEC_LINK) && (link_type != UNSPEC_LINK))) {
131       neigh->link_type = link_type;
132
133       // set the entry's link quality
134       olsr_copy_hello_lq(neigh, walker);
135
136       // set the entry's neighbour type
137
138       if (walker->neighbor->is_mpr)
139         neigh->neigh_type = MPR_NEIGH;
140
141       else if (walker->neighbor->status == SYM)
142         neigh->neigh_type = SYM_NEIGH;
143
144       else if (walker->neighbor->status == NOT_SYM)
145         neigh->neigh_type = NOT_NEIGH;
146
147       else {
148         OLSR_PRINTF(0, "Error: neigh_type undefined");
149         neigh->neigh_type = NOT_NEIGH;
150       }
151
152       // set the entry's neighbour interface address
153
154       neigh->addr = walker->neighbor_iface_addr;
155
156       if (neigh_is_new) {
157         // queue the neighbour entry
158         neigh->next = lq_hello->neigh;
159         lq_hello->neigh = neigh;
160
161       }
162     }
163   }
164   OLSR_FOR_ALL_LINK_ENTRIES_END(walker);
165 }
166
167 static void
168 destroy_lq_hello(struct lq_hello_message *lq_hello)
169 {
170   struct lq_hello_neighbor *walker, *aux;
171
172   // loop through the queued neighbour entries and free them
173
174   for (walker = lq_hello->neigh; walker != NULL; walker = aux) {
175     aux = walker->next;
176     free(walker);
177   }
178
179   lq_hello->neigh = NULL;
180 }
181
182 static void
183 create_lq_tc(struct lq_tc_message *lq_tc, struct interface_olsr *outif)
184 {
185   struct link_entry *lnk;
186   struct neighbor_entry *walker;
187   struct tc_mpr_addr *neigh;
188   static int ttl_list[] = { 2, 8, 2, 16, 2, 8, 2, MAX_TTL };
189
190   // remember that we have generated an LQ TC message; this is
191   // checked in net_output()
192
193   lq_tc_pending = true;
194
195   // initialize the static fields
196
197   lq_tc->comm.type = LQ_TC_MESSAGE;
198   lq_tc->comm.vtime = me_to_reltime(outif->valtimes.tc);
199   lq_tc->comm.size = 0;
200
201   lq_tc->comm.orig = olsr_cnf->main_addr;
202
203   if (olsr_cnf->lq_fish > 0) {
204     if (outif->ttl_index >= (int)(sizeof(ttl_list) / sizeof(ttl_list[0])))
205       outif->ttl_index = 0;
206
207     lq_tc->comm.ttl = (0 <= outif->ttl_index ? ttl_list[outif->ttl_index] : MAX_TTL);
208     outif->ttl_index++;
209
210     OLSR_PRINTF(3, "Creating LQ TC with TTL %d.\n", lq_tc->comm.ttl);
211   }
212
213   else
214     lq_tc->comm.ttl = MAX_TTL;
215
216   lq_tc->comm.hops = 0;
217
218   lq_tc->from = olsr_cnf->main_addr;
219
220   lq_tc->ansn = get_local_ansn();
221
222   lq_tc->neigh = NULL;
223
224   OLSR_FOR_ALL_NBR_ENTRIES(walker) {
225
226     /*
227      * TC redundancy 2
228      *
229      * Only consider symmetric neighbours.
230      */
231     if (walker->status != SYM) {
232       continue;
233     }
234
235     /*
236      * TC redundancy 1
237      *
238      * Only consider MPRs and MPR selectors
239      */
240     if (olsr_cnf->tc_redundancy == 1 && !walker->is_mpr && !olsr_lookup_mprs_set(&walker->neighbor_main_addr)) {
241       continue;
242     }
243
244     /*
245      * TC redundancy 0
246      *
247      * Only consider MPR selectors
248      */
249     if (olsr_cnf->tc_redundancy == 0 && !olsr_lookup_mprs_set(&walker->neighbor_main_addr)) {
250       continue;
251     }
252
253     /* Set the entry's link quality */
254     lnk = get_best_link_to_neighbor(&walker->neighbor_main_addr);
255     if (!lnk) {
256       continue;                 // no link ?
257     }
258
259     if (lnk->linkcost >= LINK_COST_BROKEN) {
260       continue;                 // don't advertise links with very low LQ
261     }
262
263     /* Allocate a neighbour entry. */
264     neigh = olsr_malloc_tc_mpr_addr("Build LQ_TC");
265
266     /* Set the entry's main address. */
267     neigh->address = walker->neighbor_main_addr;
268
269     if (lnk) {
270       olsr_copylq_link_entry_2_tc_mpr_addr(neigh, lnk);
271     }
272
273     /* Queue the neighbour entry. */
274
275     // TODO: ugly hack until neighbor table is ported to avl tree
276
277     if (lq_tc->neigh == NULL || avl_comp_default(&lq_tc->neigh->address, &neigh->address) > 0) {
278       neigh->next = lq_tc->neigh;
279       lq_tc->neigh = neigh;
280     } else {
281       struct tc_mpr_addr *last = lq_tc->neigh, *n = last->next;
282
283       while (n) {
284         if (avl_comp_default(&n->address, &neigh->address) > 0) {
285           break;
286         }
287         last = n;
288         n = n->next;
289       }
290       neigh->next = n;
291       last->next = neigh;
292     }
293
294     // neigh->next = lq_tc->neigh;
295     // lq_tc->neigh = neigh;
296
297   }
298   OLSR_FOR_ALL_NBR_ENTRIES_END(walker);
299 }
300
301 static void
302 destroy_lq_tc(struct lq_tc_message *lq_tc)
303 {
304   struct tc_mpr_addr *walker, *aux;
305
306   // loop through the queued neighbour entries and free them
307
308   for (walker = lq_tc->neigh; walker != NULL; walker = aux) {
309     aux = walker->next;
310     free(walker);
311   }
312 }
313
314 static int
315 common_size(void)
316 {
317   // return the size of the header shared by all OLSR messages
318
319   return (olsr_cnf->ip_version == AF_INET) ? sizeof(struct olsr_header_v4) : sizeof(struct olsr_header_v6);
320 }
321
322 static void
323 serialize_common(struct olsr_common *comm)
324 {
325   if (olsr_cnf->ip_version == AF_INET) {
326     // serialize an IPv4 OLSR message header
327     struct olsr_header_v4 *olsr_head_v4 = (struct olsr_header_v4 *)ARM_NOWARN_ALIGN(msg_buffer);
328
329     olsr_head_v4->type = comm->type;
330     olsr_head_v4->vtime = reltime_to_me(comm->vtime);
331     olsr_head_v4->size = htons(comm->size);
332
333     olsr_head_v4->orig = comm->orig.v4.s_addr;
334
335     olsr_head_v4->ttl = comm->ttl;
336     olsr_head_v4->hops = comm->hops;
337     olsr_head_v4->seqno = htons(get_msg_seqno());
338   } else {
339     // serialize an IPv6 OLSR message header
340     struct olsr_header_v6 *olsr_head_v6 = (struct olsr_header_v6 *)ARM_NOWARN_ALIGN(msg_buffer);
341
342     olsr_head_v6->type = comm->type;
343     olsr_head_v6->vtime = reltime_to_me(comm->vtime);
344     olsr_head_v6->size = htons(comm->size);
345
346     memcpy(&olsr_head_v6->orig, &comm->orig.v6.s6_addr, sizeof(olsr_head_v6->orig));
347
348     olsr_head_v6->ttl = comm->ttl;
349     olsr_head_v6->hops = comm->hops;
350     olsr_head_v6->seqno = htons(get_msg_seqno());
351   }
352 }
353
354 static void
355 serialize_lq_hello(struct lq_hello_message *lq_hello, struct interface_olsr *outif)
356 {
357   static const int LINK_ORDER[] = HELLO_LINK_ORDER_ARRAY;
358   int rem, size, req, expected_size = 0;
359   struct lq_hello_info_header *info_head;
360   struct lq_hello_neighbor *neigh;
361   unsigned char *buff;
362   bool is_first;
363   int i;
364
365   // leave space for the OLSR header
366   int off = common_size();
367
368   // initialize the LQ_HELLO header
369
370   struct lq_hello_header *head = (struct lq_hello_header *)ARM_NOWARN_ALIGN(msg_buffer + off);
371
372   head->reserved = 0;
373   head->htime = reltime_to_me(lq_hello->htime);
374   head->will = lq_hello->will;
375
376   // 'off' is the offset of the byte following the LQ_HELLO header
377
378   off += sizeof(struct lq_hello_header);
379
380   // our work buffer starts at 'off'...
381
382   buff = msg_buffer + off;
383
384   // ... that's why we start with a 'size' of 0 and subtract 'off' from
385   // the remaining bytes in the output buffer
386
387   size = 0;
388   rem = net_outbuffer_bytes_left(outif) - off;
389
390   /*
391    * Initially, we want to put the complete lq_hello into the message.
392    * For this flush the output buffer (if there are some bytes in).
393    * This is a hack/fix, which prevents message fragmentation resulting
394    * in unstable links. The ugly lq/genmsg code should be reworked anyhow.
395    */
396   if (0 < net_output_pending(outif)) {
397     for (i = 0; i <= MAX_NEIGH; i++) {
398       unsigned int j;
399       for (j = 0; j < sizeof(LINK_ORDER) / sizeof(LINK_ORDER[0]); j++) {
400         is_first = true;
401         for (neigh = lq_hello->neigh; neigh != NULL; neigh = neigh->next) {
402           if (0 == i && 0 == j)
403             expected_size += olsr_cnf->ipsize + olsr_sizeof_hello_lqdata();
404           if (neigh->neigh_type == i && neigh->link_type == LINK_ORDER[j]) {
405             if (is_first) {
406               expected_size += sizeof(struct lq_hello_info_header);
407               is_first = false;
408             }
409           }
410         }
411       }
412     }
413   }
414
415   if (rem < expected_size) {
416     net_output(outif);
417     rem = net_outbuffer_bytes_left(outif) - off;
418   }
419
420   info_head = NULL;
421
422   // iterate through all neighbor types ('i') and all link types ('j')
423
424   for (i = 0; i <= MAX_NEIGH; i++) {
425     unsigned int j;
426     for (j = 0; j < sizeof(LINK_ORDER) / sizeof(LINK_ORDER[0]); j++) {
427       is_first = true;
428
429       // loop through neighbors
430
431       for (neigh = lq_hello->neigh; neigh != NULL; neigh = neigh->next) {
432         if (neigh->neigh_type != i || neigh->link_type != LINK_ORDER[j])
433           continue;
434
435         // we need space for an IP address plus link quality
436         // information
437
438         req = olsr_cnf->ipsize + olsr_sizeof_hello_lqdata();
439
440         // no, we also need space for an info header, as this is the
441         // first neighbor with the current neighbor type and link type
442
443         if (is_first)
444           req += sizeof(struct lq_hello_info_header);
445
446         // we do not have enough space left
447
448         // force signed comparison
449
450         if ((int)(size + req) > rem) {
451           // finalize the OLSR header
452
453           lq_hello->comm.size = size + off;
454
455           serialize_common(&lq_hello->comm);
456
457           // finalize the info header
458
459           assert(info_head);
460           info_head->size = ntohs(buff + size - (unsigned char *)info_head);
461
462           // output packet
463
464           net_outbuffer_push(outif, msg_buffer, size + off);
465
466           net_output(outif);
467
468           // move to the beginning of the buffer
469
470           size = 0;
471           rem = net_outbuffer_bytes_left(outif) - off;
472
473           // we need a new info header
474
475           is_first = true;
476         }
477         // create a new info header
478
479         if (is_first) {
480           info_head = (struct lq_hello_info_header *)ARM_NOWARN_ALIGN(buff + size);
481           size += sizeof(struct lq_hello_info_header);
482
483           info_head->reserved = 0;
484           info_head->link_code = CREATE_LINK_CODE(i, LINK_ORDER[j]);
485         }
486         // add the current neighbor's IP address
487
488         genipcopy(buff + size, &neigh->addr);
489         size += olsr_cnf->ipsize;
490
491         // add the corresponding link quality
492         size += olsr_serialize_hello_lq_pair(&buff[size], neigh);
493
494         is_first = false;
495       }
496
497       // finalize the info header, if there are any neighbors with the
498       // current neighbor type and link type
499
500       if (!is_first)
501         info_head->size = ntohs(buff + size - (unsigned char *)info_head);
502     }
503   }
504
505   // finalize the OLSR header
506
507   lq_hello->comm.size = size + off;
508
509   serialize_common((struct olsr_common *)lq_hello);
510
511   // move the message to the output buffer
512
513   net_outbuffer_push(outif, msg_buffer, size + off);
514 }
515
516 static uint8_t
517 calculate_border_flag(void *lower_border, void *higher_border)
518 {
519   uint8_t *lower = lower_border;
520   uint8_t *higher = higher_border;
521   uint8_t bitmask;
522   uint8_t part, bitpos;
523
524   for (part = 0; part < olsr_cnf->ipsize; part++) {
525     if (lower[part] != higher[part]) {
526       break;
527     }
528   }
529
530   if (part == olsr_cnf->ipsize) {       // same IPs ?
531     return 0;
532   }
533   // look for first bit of difference
534   bitmask = 0xfe;
535   for (bitpos = 0; bitpos < 8; bitpos++, bitmask <<= 1) {
536     if ((lower[part] & bitmask) == (higher[part] & bitmask)) {
537       break;
538     }
539   }
540
541   bitpos += 8 * (olsr_cnf->ipsize - part - 1);
542   return bitpos + 1;
543 }
544
545 static void
546 serialize_lq_tc(struct lq_tc_message *lq_tc, struct interface_olsr *outif)
547 {
548   int off, rem, size, expected_size = 0;
549   struct lq_tc_header *head;
550   struct tc_mpr_addr *neigh;
551   unsigned char *buff;
552
553   union olsr_ip_addr *last_ip = NULL;
554   uint8_t left_border_flag = 0xff;
555
556   // leave space for the OLSR header
557
558   off = common_size();
559
560   // initialize the LQ_TC header
561
562   head = (struct lq_tc_header *)ARM_NOWARN_ALIGN(msg_buffer + off);
563
564   head->ansn = htons(lq_tc->ansn);
565   head->lower_border = 0;
566   head->upper_border = 0;
567
568   // 'off' is the offset of the byte following the LQ_TC header
569
570   off += sizeof(struct lq_tc_header);
571
572   // our work buffer starts at 'off'...
573
574   buff = msg_buffer + off;
575
576   // ... that's why we start with a 'size' of 0 and subtract 'off' from
577   // the remaining bytes in the output buffer
578
579   size = 0;
580   rem = net_outbuffer_bytes_left(outif) - off;
581
582   /*
583    * Initially, we want to put the complete lq_tc into the message.
584    * For this flush the output buffer (if there are some bytes in).
585    * This is a hack/fix, which prevents message fragmentation resulting
586    * in unstable links. The ugly lq/genmsg code should be reworked anyhow.
587    */
588   if (0 < net_output_pending(outif)) {
589     for (neigh = lq_tc->neigh; neigh != NULL; neigh = neigh->next) {
590       expected_size += olsr_cnf->ipsize + olsr_sizeof_tc_lqdata();
591     }
592   }
593
594   if (rem < expected_size) {
595     net_output(outif);
596     rem = net_outbuffer_bytes_left(outif) - off;
597   }
598   // loop through neighbors
599
600   for (neigh = lq_tc->neigh; neigh != NULL; neigh = neigh->next) {
601     // we need space for an IP address plus link quality
602     // information
603
604     // force signed comparison
605     if ((int)(size + olsr_cnf->ipsize + olsr_sizeof_tc_lqdata()) > rem) {
606       head->lower_border = left_border_flag;
607       assert(last_ip);
608       head->upper_border = calculate_border_flag(last_ip, &neigh->address);
609       left_border_flag = head->upper_border;
610
611       // finalize the OLSR header
612
613       lq_tc->comm.size = size + off;
614
615       serialize_common((struct olsr_common *)lq_tc);
616
617       // output packet
618
619       net_outbuffer_push(outif, msg_buffer, size + off);
620
621       net_output(outif);
622
623       // move to the beginning of the buffer
624
625       size = 0;
626       rem = net_outbuffer_bytes_left(outif) - off;
627     }
628     // add the current neighbor's IP address
629     genipcopy(buff + size, &neigh->address);
630
631     // remember last ip
632     last_ip = (union olsr_ip_addr *)ARM_NOWARN_ALIGN(buff + size);
633
634     size += olsr_cnf->ipsize;
635
636     // add the corresponding link quality
637     size += olsr_serialize_tc_lq_pair(&buff[size], neigh);
638   }
639
640   // finalize the OLSR header
641
642   head->lower_border = left_border_flag;
643   head->upper_border = 0xff;
644   lq_tc->comm.size = size + off;
645
646   serialize_common((struct olsr_common *)lq_tc);
647
648   net_outbuffer_push(outif, msg_buffer, size + off);
649 }
650
651 void
652 olsr_output_lq_hello(void *para)
653 {
654   struct lq_hello_message lq_hello;
655   struct interface_olsr *outif = para;
656
657   if (outif == NULL) {
658     return;
659   }
660   // create LQ_HELLO in internal format
661   create_lq_hello(&lq_hello, outif);
662
663   // convert internal format into transmission format, send it
664   serialize_lq_hello(&lq_hello, outif);
665
666   // destroy internal format
667   destroy_lq_hello(&lq_hello);
668
669   if (net_output_pending(outif)) {
670     if (outif->immediate_send_tc) {
671       if (TIMED_OUT(outif->fwdtimer))
672         set_buffer_timer(outif);
673     } else {
674       net_output(outif);
675     }
676   }
677 }
678
679 void
680 olsr_output_lq_tc(void *para)
681 {
682   static int prev_empty = 1;
683   struct lq_tc_message lq_tc;
684   struct interface_olsr *outif = para;
685
686   if (outif == NULL) {
687     return;
688   }
689   // create LQ_TC in internal format
690
691   create_lq_tc(&lq_tc, outif);
692
693   // a) the message is not empty
694
695   if (lq_tc.neigh != NULL) {
696     prev_empty = 0;
697
698     // convert internal format into transmission format, send it
699     serialize_lq_tc(&lq_tc, outif);
700
701     // b) this is the first empty message
702   } else if (prev_empty == 0) {
703     // initialize timer
704
705     set_empty_tc_timer(GET_TIMESTAMP(olsr_cnf->max_tc_vtime * 3 * MSEC_PER_SEC));
706
707     prev_empty = 1;
708
709     // convert internal format into transmission format, send it
710
711     serialize_lq_tc(&lq_tc, outif);
712
713     // c) this is not the first empty message, send if timer hasn't fired
714   } else if (!TIMED_OUT(get_empty_tc_timer())) {
715     serialize_lq_tc(&lq_tc, outif);
716   }
717   // destroy internal format
718
719   destroy_lq_tc(&lq_tc);
720
721   if (net_output_pending(outif)) {
722     if (!outif->immediate_send_tc) {
723       if (TIMED_OUT(outif->fwdtimer))
724         set_buffer_timer(outif);
725     } else {
726       net_output(outif);
727     }
728   }
729 }
730
731 /*
732  * Local Variables:
733  * c-basic-offset: 2
734  * indent-tabs-mode: nil
735  * End:
736  */