From Henning Rogge <rogge@fgan.de>: join LQ and non-LQ Hello execution paths
[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             neigh->link_quality = 0.0;
236             neigh->neigh_link_quality = 0.0;
237           }          
238
239           // queue the neighbour entry
240
241           neigh->next = lq_tc->neigh;
242           lq_tc->neigh = neigh;
243         }
244     }
245 }
246
247 static void
248 destroy_lq_tc(struct lq_tc_message *lq_tc)
249 {
250   struct tc_mpr_addr *walker, *aux;
251
252   // loop through the queued neighbour entries and free them
253
254   for (walker = lq_tc->neigh; walker != NULL; walker = aux)
255     {
256       aux = walker->next;
257       free(walker);
258     }
259 }
260
261 static int common_size(void)
262 {
263   // return the size of the header shared by all OLSR messages
264
265   return (olsr_cnf->ip_version == AF_INET) ?
266     sizeof (struct olsr_header_v4) : sizeof (struct olsr_header_v6);
267 }
268
269 static void serialize_common(struct olsr_common *comm)
270 {
271   if (olsr_cnf->ip_version == AF_INET)
272     {
273       // serialize an IPv4 OLSR message header
274       struct olsr_header_v4 *olsr_head_v4 = (struct olsr_header_v4 *)msg_buffer;
275
276       olsr_head_v4->type = comm->type;
277       olsr_head_v4->vtime = double_to_me(comm->vtime);
278       olsr_head_v4->size = htons(comm->size);
279
280       olsr_head_v4->orig = comm->orig.v4.s_addr;
281
282       olsr_head_v4->ttl = comm->ttl;
283       olsr_head_v4->hops = comm->hops;
284       olsr_head_v4->seqno = htons(comm->seqno);
285     }
286   else
287     {
288       // serialize an IPv6 OLSR message header
289       struct olsr_header_v6 *olsr_head_v6 = (struct olsr_header_v6 *)msg_buffer;
290
291       olsr_head_v6->type = comm->type;
292       olsr_head_v6->vtime = double_to_me(comm->vtime);
293       olsr_head_v6->size = htons(comm->size);
294
295       memcpy(&olsr_head_v6->orig, &comm->orig.v6.s6_addr, sizeof(olsr_head_v6->orig));
296
297       olsr_head_v6->ttl = comm->ttl;
298       olsr_head_v6->hops = comm->hops;
299       olsr_head_v6->seqno = htons(comm->seqno);
300     }
301 }
302
303 static void
304 serialize_lq_hello(struct lq_hello_message *lq_hello, struct interface *outif)
305 {
306   static const int LINK_ORDER[] = {SYM_LINK, UNSPEC_LINK, ASYM_LINK, LOST_LINK};
307   int rem, size, req, expected_size = 0;
308   struct lq_hello_info_header *info_head;
309   struct lq_hello_neighbor *neigh;
310   unsigned char *buff;
311   olsr_bool is_first;
312   int i;
313
314   // leave space for the OLSR header
315   int off = common_size();
316
317   // initialize the LQ_HELLO header
318
319   struct lq_hello_header *head = (struct lq_hello_header *)(msg_buffer + off);
320
321   head->reserved = 0;
322   head->htime = double_to_me(lq_hello->htime);
323   head->will = lq_hello->will; 
324
325   // 'off' is the offset of the byte following the LQ_HELLO header
326
327   off += sizeof (struct lq_hello_header);
328
329   // our work buffer starts at 'off'...
330
331   buff = msg_buffer + off;
332
333   // ... that's why we start with a 'size' of 0 and subtract 'off' from
334   // the remaining bytes in the output buffer
335
336   size = 0;
337   rem = net_outbuffer_bytes_left(outif) - off;
338
339   /*
340    * Initially, we want to put the complete lq_hello into the message.
341    * For this flush the output buffer (if there are some bytes in).
342    * This is a hack/fix, which prevents message fragementation resulting
343    * in instable links. The ugly lq/genmsg code should be reworked anyhow.
344    */
345   if (0 < net_output_pending(outif)) {
346     for (i = 0; i <= MAX_NEIGH; i++) {
347       unsigned int j;
348       for(j = 0; j < sizeof(LINK_ORDER) / sizeof(LINK_ORDER[0]); j++) {
349         is_first = OLSR_TRUE;
350         for (neigh = lq_hello->neigh; neigh != NULL; neigh = neigh->next) {
351           if (0 == i && 0 == j) expected_size += olsr_cnf->ipsize + 4;
352           if (neigh->neigh_type == i && neigh->link_type == LINK_ORDER[j]) {
353             if (is_first) {
354               expected_size += sizeof(struct lq_hello_info_header);
355               is_first = OLSR_FALSE;
356             }
357           }
358         }
359       }
360     }
361   }
362
363   if (rem < expected_size) {
364     net_output(outif);
365     rem = net_outbuffer_bytes_left(outif) - off;
366   }
367
368   info_head = NULL;
369
370   // iterate through all neighbor types ('i') and all link types ('j')
371
372   for (i = 0; i <= MAX_NEIGH; i++) 
373     {
374       unsigned int j;
375       for(j = 0; j < sizeof(LINK_ORDER) / sizeof(LINK_ORDER[0]); j++)
376         {
377           is_first = OLSR_TRUE;
378
379           // loop through neighbors
380
381           for (neigh = lq_hello->neigh; neigh != NULL; neigh = neigh->next)
382             {  
383               if (neigh->neigh_type != i || neigh->link_type != LINK_ORDER[j])
384                 continue;
385
386               // we need space for an IP address plus link quality
387               // information
388
389               req = olsr_cnf->ipsize + 4;
390
391               // no, we also need space for an info header, as this is the
392               // first neighbor with the current neighor type and link type
393
394               if (is_first)
395                 req += sizeof (struct lq_hello_info_header);
396
397               // we do not have enough space left
398
399               // force signed comparison
400
401               if ((int)(size + req) > rem)
402                 {
403                   // finalize the OLSR header
404
405                   lq_hello->comm.size = size + off;
406
407                   serialize_common(&lq_hello->comm);
408
409                   // finalize the info header
410
411                   info_head->size =
412                     ntohs(buff + size - (unsigned char *)info_head);
413                               
414                   // output packet
415
416                   net_outbuffer_push(outif, msg_buffer, size + off);
417
418                   net_output(outif);
419
420                   // move to the beginning of the buffer
421
422                   size = 0;
423                   rem = net_outbuffer_bytes_left(outif) - off;
424
425                   // we need a new info header
426
427                   is_first = OLSR_TRUE;
428                 }
429
430               // create a new info header
431
432               if (is_first)
433                 {
434                   info_head = (struct lq_hello_info_header *)(buff + size);
435                   size += sizeof (struct lq_hello_info_header);
436
437                   info_head->reserved = 0;
438                   info_head->link_code = CREATE_LINK_CODE(i, LINK_ORDER[j]);
439                 }
440
441               // add the current neighbor's IP address
442
443               genipcopy(buff + size, &neigh->addr);
444               size += olsr_cnf->ipsize;
445
446               // add the corresponding link quality
447
448               buff[size++] = (unsigned char)(neigh->link_quality * 255);
449               buff[size++] = (unsigned char)(neigh->neigh_link_quality * 255);
450
451               // pad
452
453               buff[size++] = 0;
454               buff[size++] = 0;
455
456               is_first = OLSR_FALSE;
457             }
458
459           // finalize the info header, if there are any neighbors with the
460           // current neighbor type and link type
461
462           if (!is_first)
463             info_head->size = ntohs(buff + size - (unsigned char *)info_head);
464         }
465     }
466
467   // finalize the OLSR header
468
469   lq_hello->comm.size = size + off;
470
471   serialize_common((struct olsr_common *)lq_hello);
472
473   // move the message to the output buffer
474
475   net_outbuffer_push(outif, msg_buffer, size + off);
476 }
477
478 static void
479 serialize_lq_tc(struct lq_tc_message *lq_tc, struct interface *outif)
480 {
481   int off, rem, size, expected_size = 0;
482   struct lq_tc_header *head;
483   struct tc_mpr_addr *neigh;
484   unsigned char *buff;
485
486   // leave space for the OLSR header
487
488   off = common_size();
489
490   // initialize the LQ_TC header
491
492   head = (struct lq_tc_header *)(msg_buffer + off);
493
494   head->ansn = htons(lq_tc->ansn);
495   head->reserved = 0;
496
497   // 'off' is the offset of the byte following the LQ_TC header
498
499   off += sizeof (struct lq_tc_header);
500
501   // our work buffer starts at 'off'...
502
503   buff = msg_buffer + off;
504
505   // ... that's why we start with a 'size' of 0 and subtract 'off' from
506   // the remaining bytes in the output buffer
507
508   size = 0;
509   rem = net_outbuffer_bytes_left(outif) - off;
510
511   /*
512    * Initially, we want to put the complete lq_tc into the message.
513    * For this flush the output buffer (if there are some bytes in).
514    * This is a hack/fix, which prevents message fragementation resulting
515    * in instable links. The ugly lq/genmsg code should be reworked anyhow.
516    */
517   if (0 < net_output_pending(outif)) {
518     for (neigh = lq_tc->neigh; neigh != NULL; neigh = neigh->next) {
519       expected_size += olsr_cnf->ipsize + 4;
520     }
521   }
522
523   if (rem < expected_size) {
524     net_output(outif);
525     rem = net_outbuffer_bytes_left(outif) - off;
526   }
527
528   // loop through neighbors
529
530   for (neigh = lq_tc->neigh; neigh != NULL; neigh = neigh->next)
531     {  
532       // we need space for an IP address plus link quality
533       // information
534
535       // force signed comparison
536
537       if ((int)(size + olsr_cnf->ipsize + 4) > rem)
538         {
539           // finalize the OLSR header
540
541           lq_tc->comm.size = size + off;
542
543           serialize_common((struct olsr_common *)lq_tc);
544
545           // output packet
546
547           net_outbuffer_push(outif, msg_buffer, size + off);
548
549           net_output(outif);
550
551           // move to the beginning of the buffer
552
553           size = 0;
554           rem = net_outbuffer_bytes_left(outif) - off;
555         }
556
557       // add the current neighbor's IP address
558       genipcopy(buff + size, &neigh->address);
559       size += olsr_cnf->ipsize;
560
561       // add the corresponding link quality
562       buff[size++] = (unsigned char)(neigh->link_quality * 255);
563       buff[size++] = (unsigned char)(neigh->neigh_link_quality * 255);
564
565       // pad
566       buff[size++] = 0;
567       buff[size++] = 0;
568     }
569
570   // finalize the OLSR header
571
572   lq_tc->comm.size = size + off;
573
574   serialize_common((struct olsr_common *)lq_tc);
575
576   net_outbuffer_push(outif, msg_buffer, size + off);
577 }
578
579 void
580 olsr_output_lq_hello(void *para)
581 {
582   struct lq_hello_message lq_hello;
583   struct interface *outif = para;
584
585   if (outif == NULL) {
586     return;
587   }
588
589   // create LQ_HELLO in internal format
590   create_lq_hello(&lq_hello, outif);
591
592   // convert internal format into transmission format, send it
593   serialize_lq_hello(&lq_hello, outif);
594
595   // destroy internal format
596   destroy_lq_hello(&lq_hello);
597
598   if(net_output_pending(outif) && (!outif->immediate_send_tc || TIMED_OUT(outif->fwdtimer))) {
599     net_output(outif);
600   }
601 }
602
603 void
604 olsr_output_lq_tc(void *para)
605 {
606   static int prev_empty = 1;
607   struct lq_tc_message lq_tc;
608   struct interface *outif = para;
609
610   if (outif == NULL) {
611     return;
612   }
613   // create LQ_TC in internal format
614
615   create_lq_tc(&lq_tc, outif);
616
617   // a) the message is not empty
618
619   if (lq_tc.neigh != NULL) {
620       prev_empty = 0;
621       
622       // convert internal format into transmission format, send it
623       serialize_lq_tc(&lq_tc, outif);
624
625   // b) this is the first empty message
626   } else if (prev_empty == 0) {
627       // initialize timer
628
629       set_empty_tc_timer(GET_TIMESTAMP(olsr_cnf->max_tc_vtime * 3 * 1000));
630
631       prev_empty = 1;
632
633       // convert internal format into transmission format, send it
634
635       serialize_lq_tc(&lq_tc, outif);
636
637   // c) this is not the first empty message, send if timer hasn't fired
638   } else if (!TIMED_OUT(get_empty_tc_timer())) {
639       serialize_lq_tc(&lq_tc, outif);
640   }
641   // destroy internal format
642
643   destroy_lq_tc(&lq_tc);
644
645   if(net_output_pending(outif) && (outif->immediate_send_tc || TIMED_OUT(outif->fwdtimer))) {
646     set_buffer_timer(outif);
647   }
648 }