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