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