From Sven-Ola Tuecke <sven-ola@gmx.de>: add support for fixedpoint math
[olsrd.git] / src / lq_packet.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2003, Andreas T√łnnesen (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
60
61 olsr_bool lq_tc_pending = OLSR_FALSE;
62
63 static unsigned char msg_buffer[MAXMESSAGESIZE - OLSR_HEADERSIZE];
64
65 static void
66 create_lq_hello(struct lq_hello_message *lq_hello, struct interface *outif)
67 {
68   struct link_entry *walker;
69
70   // initialize the static fields
71
72   lq_hello->comm.type = LQ_HELLO_MESSAGE;
73   lq_hello->comm.vtime = me_to_double(outif->valtimes.hello);
74   lq_hello->comm.size = 0;
75
76   lq_hello->comm.orig = olsr_cnf->main_addr;
77
78   lq_hello->comm.ttl = 1;
79   lq_hello->comm.hops = 0;
80   lq_hello->comm.seqno = get_msg_seqno();
81
82   lq_hello->htime = outif->hello_etime;
83   lq_hello->will = olsr_cnf->willingness;
84
85   lq_hello->neigh = NULL;
86   
87   // loop through the link set
88
89   for (walker = get_link_set(); walker != NULL; walker = walker->next)
90     {
91       // allocate a neighbour entry
92       struct lq_hello_neighbor *neigh = olsr_malloc(sizeof (struct lq_hello_neighbor), "Build LQ_HELLO");
93
94       // a) this neighbor interface IS NOT visible via the output interface
95       if(!ipequal(&walker->local_iface_addr, &outif->ip_addr))
96         neigh->link_type = UNSPEC_LINK;
97       
98       // b) this neighbor interface IS visible via the output interface
99
100       else
101         neigh->link_type = lookup_link_status(walker);
102
103       // set the entry's link quality
104
105       neigh->link_quality = walker->loss_link_quality;
106       neigh->neigh_link_quality = walker->neigh_link_quality;
107
108       // set the entry's neighbour type
109
110       if(walker->neighbor->is_mpr)
111         neigh->neigh_type = MPR_NEIGH;
112
113       else if (walker->neighbor->status == SYM)
114         neigh->neigh_type = SYM_NEIGH;
115
116       else if (walker->neighbor->status == NOT_SYM)
117         neigh->neigh_type = NOT_NEIGH;
118         
119       else {
120         OLSR_PRINTF(0, "Error: neigh_type undefined");
121         neigh->neigh_type = NOT_NEIGH;
122       }
123   
124       // set the entry's neighbour interface address
125
126       neigh->addr = walker->neighbor_iface_addr;
127       
128       // queue the neighbour entry
129
130       neigh->next = lq_hello->neigh;
131       lq_hello->neigh = neigh;
132     }
133 }
134
135 static void
136 destroy_lq_hello(struct lq_hello_message *lq_hello)
137 {
138   struct lq_hello_neighbor *walker, *aux;
139
140   // loop through the queued neighbour entries and free them
141
142   for (walker = lq_hello->neigh; walker != NULL; walker = aux)
143     {
144       aux = walker->next;
145       free(walker);
146     }
147
148   lq_hello->neigh = NULL;
149 }
150
151 static void
152 create_lq_tc(struct lq_tc_message *lq_tc, struct interface *outif)
153 {
154   int i;
155   static int ttl_list[] = { 2, 8, 2, 16, 2, 8, 2, MAX_TTL};
156
157   // remember that we have generated an LQ TC message; this is
158   // checked in net_output()
159
160   lq_tc_pending = OLSR_TRUE;
161
162   // initialize the static fields
163
164   lq_tc->comm.type = LQ_TC_MESSAGE;
165   lq_tc->comm.vtime = me_to_double(outif->valtimes.tc);
166   lq_tc->comm.size = 0;
167
168   lq_tc->comm.orig = olsr_cnf->main_addr;
169
170   if (olsr_cnf->lq_fish > 0)
171   {
172     if (outif->ttl_index >= (int)(sizeof(ttl_list) / sizeof(ttl_list[0])))
173       outif->ttl_index = 0;
174     
175     lq_tc->comm.ttl = (0 <= outif->ttl_index ? ttl_list[outif->ttl_index] : MAX_TTL);
176     outif->ttl_index++;
177
178     OLSR_PRINTF(3, "Creating LQ TC with TTL %d.\n", lq_tc->comm.ttl);
179   }
180
181   else
182     lq_tc->comm.ttl = MAX_TTL;
183
184   lq_tc->comm.hops = 0;
185   lq_tc->comm.seqno = get_msg_seqno();
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   // loop through all neighbours
194   
195   for(i = 0; i < HASHSIZE; i++)
196     {
197       struct neighbor_entry *walker;
198       struct tc_mpr_addr    *neigh;
199       for(walker = neighbortable[i].next; walker != &neighbortable[i];
200           walker = walker->next)
201         {
202           struct link_entry *lnk;
203           // only consider symmetric neighbours
204
205           if(walker->status != SYM)
206             continue;
207
208           // TC redundancy == 1: only consider MPRs and MPR selectors
209
210           if (olsr_cnf->tc_redundancy == 1 && !walker->is_mpr &&
211               olsr_lookup_mprs_set(&walker->neighbor_main_addr) == NULL)
212             continue;
213
214           // TC redundancy == 0: only consider MPR selectors
215           if (olsr_cnf->tc_redundancy == 0 &&
216               olsr_lookup_mprs_set(&walker->neighbor_main_addr) == NULL)
217             continue;
218
219           // allocate a neighbour entry          
220           neigh = olsr_malloc(sizeof (struct tc_mpr_addr), "Build LQ_TC");
221
222           // set the entry's main address
223
224           neigh->address = walker->neighbor_main_addr;
225
226           // set the entry's link quality
227           lnk = get_best_link_to_neighbor(&neigh->address);
228
229           if (lnk) {
230             neigh->link_quality = lnk->loss_link_quality;
231             neigh->neigh_link_quality = lnk->neigh_link_quality;
232           }
233           else {
234             OLSR_PRINTF(0, "Error: link_qualtiy undefined");
235 #ifdef USE_FPM
236             neigh->link_quality = itofpm(0);
237             neigh->neigh_link_quality = itofpm(0);
238 #else
239             neigh->link_quality = 0.0;
240             neigh->neigh_link_quality = 0.0;
241 #endif
242           }          
243
244           // queue the neighbour entry
245
246           neigh->next = lq_tc->neigh;
247           lq_tc->neigh = neigh;
248         }
249     }
250 }
251
252 static void
253 destroy_lq_tc(struct lq_tc_message *lq_tc)
254 {
255   struct tc_mpr_addr *walker, *aux;
256
257   // loop through the queued neighbour entries and free them
258
259   for (walker = lq_tc->neigh; walker != NULL; walker = aux)
260     {
261       aux = walker->next;
262       free(walker);
263     }
264 }
265
266 static int common_size(void)
267 {
268   // return the size of the header shared by all OLSR messages
269
270   return (olsr_cnf->ip_version == AF_INET) ?
271     sizeof (struct olsr_header_v4) : sizeof (struct olsr_header_v6);
272 }
273
274 static void serialize_common(struct olsr_common *comm)
275 {
276   if (olsr_cnf->ip_version == AF_INET)
277     {
278       // serialize an IPv4 OLSR message header
279       struct olsr_header_v4 *olsr_head_v4 = (struct olsr_header_v4 *)msg_buffer;
280
281       olsr_head_v4->type = comm->type;
282       olsr_head_v4->vtime = double_to_me(comm->vtime);
283       olsr_head_v4->size = htons(comm->size);
284
285       olsr_head_v4->orig = comm->orig.v4.s_addr;
286
287       olsr_head_v4->ttl = comm->ttl;
288       olsr_head_v4->hops = comm->hops;
289       olsr_head_v4->seqno = htons(comm->seqno);
290     }
291   else
292     {
293       // serialize an IPv6 OLSR message header
294       struct olsr_header_v6 *olsr_head_v6 = (struct olsr_header_v6 *)msg_buffer;
295
296       olsr_head_v6->type = comm->type;
297       olsr_head_v6->vtime = double_to_me(comm->vtime);
298       olsr_head_v6->size = htons(comm->size);
299
300       memcpy(&olsr_head_v6->orig, &comm->orig.v6.s6_addr, sizeof(olsr_head_v6->orig));
301
302       olsr_head_v6->ttl = comm->ttl;
303       olsr_head_v6->hops = comm->hops;
304       olsr_head_v6->seqno = htons(comm->seqno);
305     }
306 }
307
308 static void
309 serialize_lq_hello(struct lq_hello_message *lq_hello, struct interface *outif)
310 {
311   static const int LINK_ORDER[] = {SYM_LINK, UNSPEC_LINK, ASYM_LINK, LOST_LINK};
312   int rem, size, req, expected_size = 0;
313   struct lq_hello_info_header *info_head;
314   struct lq_hello_neighbor *neigh;
315   unsigned char *buff;
316   olsr_bool is_first;
317   int i;
318
319   // leave space for the OLSR header
320   int off = common_size();
321
322   // initialize the LQ_HELLO header
323
324   struct lq_hello_header *head = (struct lq_hello_header *)(msg_buffer + off);
325
326   head->reserved = 0;
327   head->htime = double_to_me(lq_hello->htime);
328   head->will = lq_hello->will; 
329
330   // 'off' is the offset of the byte following the LQ_HELLO header
331
332   off += sizeof (struct lq_hello_header);
333
334   // our work buffer starts at 'off'...
335
336   buff = msg_buffer + off;
337
338   // ... that's why we start with a 'size' of 0 and subtract 'off' from
339   // the remaining bytes in the output buffer
340
341   size = 0;
342   rem = net_outbuffer_bytes_left(outif) - off;
343
344   /*
345    * Initially, we want to put the complete lq_hello into the message.
346    * For this flush the output buffer (if there are some bytes in).
347    * This is a hack/fix, which prevents message fragementation resulting
348    * in instable links. The ugly lq/genmsg code should be reworked anyhow.
349    */
350   if (0 < net_output_pending(outif)) {
351     for (i = 0; i <= MAX_NEIGH; i++) {
352       unsigned int j;
353       for(j = 0; j < sizeof(LINK_ORDER) / sizeof(LINK_ORDER[0]); j++) {
354         is_first = OLSR_TRUE;
355         for (neigh = lq_hello->neigh; neigh != NULL; neigh = neigh->next) {
356           if (0 == i && 0 == j) expected_size += olsr_cnf->ipsize + 4;
357           if (neigh->neigh_type == i && neigh->link_type == LINK_ORDER[j]) {
358             if (is_first) {
359               expected_size += sizeof(struct lq_hello_info_header);
360               is_first = OLSR_FALSE;
361             }
362           }
363         }
364       }
365     }
366   }
367
368   if (rem < expected_size) {
369     net_output(outif);
370     rem = net_outbuffer_bytes_left(outif) - off;
371   }
372
373   info_head = NULL;
374
375   // iterate through all neighbor types ('i') and all link types ('j')
376
377   for (i = 0; i <= MAX_NEIGH; i++) 
378     {
379       unsigned int j;
380       for(j = 0; j < sizeof(LINK_ORDER) / sizeof(LINK_ORDER[0]); j++)
381         {
382           is_first = OLSR_TRUE;
383
384           // loop through neighbors
385
386           for (neigh = lq_hello->neigh; neigh != NULL; neigh = neigh->next)
387             {  
388               if (neigh->neigh_type != i || neigh->link_type != LINK_ORDER[j])
389                 continue;
390
391               // we need space for an IP address plus link quality
392               // information
393
394               req = olsr_cnf->ipsize + 4;
395
396               // no, we also need space for an info header, as this is the
397               // first neighbor with the current neighor type and link type
398
399               if (is_first)
400                 req += sizeof (struct lq_hello_info_header);
401
402               // we do not have enough space left
403
404               // force signed comparison
405
406               if ((int)(size + req) > rem)
407                 {
408                   // finalize the OLSR header
409
410                   lq_hello->comm.size = size + off;
411
412                   serialize_common(&lq_hello->comm);
413
414                   // finalize the info header
415
416                   info_head->size =
417                     ntohs(buff + size - (unsigned char *)info_head);
418                               
419                   // output packet
420
421                   net_outbuffer_push(outif, msg_buffer, size + off);
422
423                   net_output(outif);
424
425                   // move to the beginning of the buffer
426
427                   size = 0;
428                   rem = net_outbuffer_bytes_left(outif) - off;
429
430                   // we need a new info header
431
432                   is_first = OLSR_TRUE;
433                 }
434
435               // create a new info header
436
437               if (is_first)
438                 {
439                   info_head = (struct lq_hello_info_header *)(buff + size);
440                   size += sizeof (struct lq_hello_info_header);
441
442                   info_head->reserved = 0;
443                   info_head->link_code = CREATE_LINK_CODE(i, LINK_ORDER[j]);
444                 }
445
446               // add the current neighbor's IP address
447
448               genipcopy(buff + size, &neigh->addr);
449               size += olsr_cnf->ipsize;
450
451               // add the corresponding link quality
452
453 #ifdef USE_FPM
454               buff[size++] = fpmtoi(fpmmuli(neigh->link_quality, 255));
455               buff[size++] = fpmtoi(fpmmuli(neigh->neigh_link_quality, 255));
456 #else
457               buff[size++] = (unsigned char)(neigh->link_quality * 255);
458               buff[size++] = (unsigned char)(neigh->neigh_link_quality * 255);
459 #endif
460
461               // pad
462
463               buff[size++] = 0;
464               buff[size++] = 0;
465
466               is_first = OLSR_FALSE;
467             }
468
469           // finalize the info header, if there are any neighbors with the
470           // current neighbor type and link type
471
472           if (!is_first)
473             info_head->size = ntohs(buff + size - (unsigned char *)info_head);
474         }
475     }
476
477   // finalize the OLSR header
478
479   lq_hello->comm.size = size + off;
480
481   serialize_common((struct olsr_common *)lq_hello);
482
483   // move the message to the output buffer
484
485   net_outbuffer_push(outif, msg_buffer, size + off);
486 }
487
488 static void
489 serialize_lq_tc(struct lq_tc_message *lq_tc, struct interface *outif)
490 {
491   int off, rem, size, expected_size = 0;
492   struct lq_tc_header *head;
493   struct tc_mpr_addr *neigh;
494   unsigned char *buff;
495
496   // leave space for the OLSR header
497
498   off = common_size();
499
500   // initialize the LQ_TC header
501
502   head = (struct lq_tc_header *)(msg_buffer + off);
503
504   head->ansn = htons(lq_tc->ansn);
505   head->reserved = 0;
506
507   // 'off' is the offset of the byte following the LQ_TC header
508
509   off += sizeof (struct lq_tc_header);
510
511   // our work buffer starts at 'off'...
512
513   buff = msg_buffer + off;
514
515   // ... that's why we start with a 'size' of 0 and subtract 'off' from
516   // the remaining bytes in the output buffer
517
518   size = 0;
519   rem = net_outbuffer_bytes_left(outif) - off;
520
521   /*
522    * Initially, we want to put the complete lq_tc into the message.
523    * For this flush the output buffer (if there are some bytes in).
524    * This is a hack/fix, which prevents message fragementation resulting
525    * in instable links. The ugly lq/genmsg code should be reworked anyhow.
526    */
527   if (0 < net_output_pending(outif)) {
528     for (neigh = lq_tc->neigh; neigh != NULL; neigh = neigh->next) {
529       expected_size += olsr_cnf->ipsize + 4;
530     }
531   }
532
533   if (rem < expected_size) {
534     net_output(outif);
535     rem = net_outbuffer_bytes_left(outif) - off;
536   }
537
538   // loop through neighbors
539
540   for (neigh = lq_tc->neigh; neigh != NULL; neigh = neigh->next)
541     {  
542       // we need space for an IP address plus link quality
543       // information
544
545       // force signed comparison
546
547       if ((int)(size + olsr_cnf->ipsize + 4) > rem)
548         {
549           // finalize the OLSR header
550
551           lq_tc->comm.size = size + off;
552
553           serialize_common((struct olsr_common *)lq_tc);
554
555           // output packet
556
557           net_outbuffer_push(outif, msg_buffer, size + off);
558
559           net_output(outif);
560
561           // move to the beginning of the buffer
562
563           size = 0;
564           rem = net_outbuffer_bytes_left(outif) - off;
565         }
566
567       // add the current neighbor's IP address
568       genipcopy(buff + size, &neigh->address);
569       size += olsr_cnf->ipsize;
570
571       // add the corresponding link quality
572 #ifdef USE_FPM
573       buff[size++] = fpmtoi(fpmmuli(neigh->link_quality, 255));
574       buff[size++] = fpmtoi(fpmmuli(neigh->neigh_link_quality, 255));
575 #else
576       buff[size++] = (unsigned char)(neigh->link_quality * 255);
577       buff[size++] = (unsigned char)(neigh->neigh_link_quality * 255);
578 #endif
579
580       // pad
581       buff[size++] = 0;
582       buff[size++] = 0;
583     }
584
585   // finalize the OLSR header
586
587   lq_tc->comm.size = size + off;
588
589   serialize_common((struct olsr_common *)lq_tc);
590
591   net_outbuffer_push(outif, msg_buffer, size + off);
592 }
593
594 void
595 olsr_output_lq_hello(void *para)
596 {
597   struct lq_hello_message lq_hello;
598   struct interface *outif = para;
599
600   if (outif == NULL) {
601     return;
602   }
603
604   // create LQ_HELLO in internal format
605   create_lq_hello(&lq_hello, outif);
606
607   // convert internal format into transmission format, send it
608   serialize_lq_hello(&lq_hello, outif);
609
610   // destroy internal format
611   destroy_lq_hello(&lq_hello);
612
613   if(net_output_pending(outif) && (!outif->immediate_send_tc || TIMED_OUT(outif->fwdtimer))) {
614     net_output(outif);
615   }
616 }
617
618 void
619 olsr_output_lq_tc(void *para)
620 {
621   static int prev_empty = 1;
622   struct lq_tc_message lq_tc;
623   struct interface *outif = para;
624
625   if (outif == NULL) {
626     return;
627   }
628   // create LQ_TC in internal format
629
630   create_lq_tc(&lq_tc, outif);
631
632   // a) the message is not empty
633
634   if (lq_tc.neigh != NULL) {
635       prev_empty = 0;
636       
637       // convert internal format into transmission format, send it
638       serialize_lq_tc(&lq_tc, outif);
639
640   // b) this is the first empty message
641   } else if (prev_empty == 0) {
642       // initialize timer
643
644       set_empty_tc_timer(GET_TIMESTAMP(olsr_cnf->max_tc_vtime * 3 * 1000));
645
646       prev_empty = 1;
647
648       // convert internal format into transmission format, send it
649
650       serialize_lq_tc(&lq_tc, outif);
651
652   // c) this is not the first empty message, send if timer hasn't fired
653   } else if (!TIMED_OUT(get_empty_tc_timer())) {
654       serialize_lq_tc(&lq_tc, outif);
655   }
656   // destroy internal format
657
658   destroy_lq_tc(&lq_tc);
659
660   if(net_output_pending(outif) && (outif->immediate_send_tc || TIMED_OUT(outif->fwdtimer))) {
661     set_buffer_timer(outif);
662   }
663 }