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