TCs produce border-flags in reserved space (no handling at the moment)
[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 #include "lq_plugin.h"
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   OLSR_FOR_ALL_LINK_ENTRIES(walker) {
90
91     // allocate a neighbour entry
92     struct lq_hello_neighbor *neigh = olsr_malloc_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     olsr_copy_hello_lq(neigh, walker);
105
106     // set the entry's neighbour type
107
108     if(walker->neighbor->is_mpr)
109       neigh->neigh_type = MPR_NEIGH;
110
111     else if (walker->neighbor->status == SYM)
112       neigh->neigh_type = SYM_NEIGH;
113
114     else if (walker->neighbor->status == NOT_SYM)
115       neigh->neigh_type = NOT_NEIGH;
116         
117     else {
118       OLSR_PRINTF(0, "Error: neigh_type undefined");
119       neigh->neigh_type = NOT_NEIGH;
120     }
121   
122     // set the entry's neighbour interface address
123
124     neigh->addr = walker->neighbor_iface_addr;
125       
126     // queue the neighbour entry
127
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 = OLSR_TRUE;
162
163   // initialize the static fields
164
165   lq_tc->comm.type = LQ_TC_MESSAGE;
166   lq_tc->comm.vtime = me_to_double(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)(sizeof(ttl_list) / sizeof(ttl_list[0])))
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   lq_tc->comm.seqno = get_msg_seqno();
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 &&
211         !olsr_lookup_mprs_set(&walker->neighbor_main_addr)) {
212       continue;
213     }
214
215     /*
216      * TC redundancy 0
217      *
218      * Only consider MPR selectors
219      */
220     if (olsr_cnf->tc_redundancy == 0 &&
221         !olsr_lookup_mprs_set(&walker->neighbor_main_addr)) {
222       continue;
223     }
224
225     /* Set the entry's link quality */
226     lnk = get_best_link_to_neighbor(&walker->neighbor_main_addr);
227     if (!lnk) {
228       continue; // no link ?
229     }
230     
231     if (lnk->linkcost >= LINK_COST_BROKEN) {
232       continue; // don't advertise links with very low LQ
233     }
234     
235     /* Allocate a neighbour entry. */
236     neigh = olsr_malloc_tc_mpr_addr("Build LQ_TC");
237
238     /* Set the entry's main address. */
239     neigh->address = walker->neighbor_main_addr;
240
241     if (lnk) {
242       olsr_copylq_link_entry_2_tc_mpr_addr(neigh, lnk);
243     }
244
245     /* Queue the neighbour entry. */
246     neigh->next = lq_tc->neigh;
247     lq_tc->neigh = neigh;
248
249   } OLSR_FOR_ALL_NBR_ENTRIES_END(walker);
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               size += olsr_serialize_hello_lq_pair(&buff[size], neigh);
453
454               is_first = OLSR_FALSE;
455             }
456
457           // finalize the info header, if there are any neighbors with the
458           // current neighbor type and link type
459
460           if (!is_first)
461             info_head->size = ntohs(buff + size - (unsigned char *)info_head);
462         }
463     }
464
465   // finalize the OLSR header
466
467   lq_hello->comm.size = size + off;
468
469   serialize_common((struct olsr_common *)lq_hello);
470
471   // move the message to the output buffer
472
473   net_outbuffer_push(outif, msg_buffer, size + off);
474 }
475
476 static olsr_u8_t
477 calculate_border_flag(void *lower_border, void *higher_border) {
478         olsr_u32_t *lower = lower_border;
479         olsr_u32_t *higher = higher_border;
480         olsr_u32_t bitmask = 0x7fffffff;
481         
482         olsr_u32_t part, bitpos;
483         for (part = 0; part < olsr_cnf->ipsize/4; part ++) {
484                 if (lower[part] != higher[part]) {
485                         break;
486                 }
487         }
488         
489         if (part == olsr_cnf->ipsize/4) { // same IPs ?
490                 return 0;
491         }
492         
493         // look for first bit of difference
494         bitpos = 31;
495         for (bitpos = 31; bitpos > 0; bitpos--, bitmask >>= 1) {
496                 if ((lower[part] & bitmask) == (higher[part] & bitmask)) {
497                         break;
498                 }
499         }
500         
501         if (olsr_cnf->ipsize > 4) { // ipv6 ?
502                 bitpos += 32 * (olsr_cnf->ipsize/4 - part);
503         }
504         return bitpos + 1;
505 }
506
507 static void
508 serialize_lq_tc(struct lq_tc_message *lq_tc, struct interface *outif)
509 {
510   int off, rem, size, expected_size = 0;
511   struct lq_tc_header *head;
512   struct tc_mpr_addr *neigh;
513   unsigned char *buff;
514
515   union olsr_ip_addr *last_ip = NULL;
516   olsr_u8_t left_border_flag = 0xff;
517   
518   // leave space for the OLSR header
519
520   off = common_size();
521
522   // initialize the LQ_TC header
523
524   head = (struct lq_tc_header *)(msg_buffer + off);
525
526   head->ansn = htons(lq_tc->ansn);
527   head->lower_border = 0;
528   head->upper_border = 0;
529   
530   // 'off' is the offset of the byte following the LQ_TC header
531
532   off += sizeof (struct lq_tc_header);
533
534   // our work buffer starts at 'off'...
535
536   buff = msg_buffer + off;
537
538   // ... that's why we start with a 'size' of 0 and subtract 'off' from
539   // the remaining bytes in the output buffer
540
541   size = 0;
542   rem = net_outbuffer_bytes_left(outif) - off;
543
544   /*
545    * Initially, we want to put the complete lq_tc into the message.
546    * For this flush the output buffer (if there are some bytes in).
547    * This is a hack/fix, which prevents message fragementation resulting
548    * in instable links. The ugly lq/genmsg code should be reworked anyhow.
549    */
550   if (0 < net_output_pending(outif)) {
551     for (neigh = lq_tc->neigh; neigh != NULL; neigh = neigh->next) {
552       expected_size += olsr_cnf->ipsize + 4;
553     }
554   }
555
556   if (rem < expected_size) {
557     net_output(outif);
558     rem = net_outbuffer_bytes_left(outif) - off;
559   }
560
561   // loop through neighbors
562
563   for (neigh = lq_tc->neigh; neigh != NULL; neigh = neigh->next)
564     {  
565       // we need space for an IP address plus link quality
566       // information
567
568       // force signed comparison
569
570       if ((int)(size + olsr_cnf->ipsize + 4) > rem)
571         {
572           head->lower_border = left_border_flag;
573           head->upper_border = calculate_border_flag(last_ip, &neigh->address);
574           left_border_flag = head->upper_border;
575           
576           // finalize the OLSR header
577
578           lq_tc->comm.size = size + off;
579
580           serialize_common((struct olsr_common *)lq_tc);
581
582           // output packet
583
584           net_outbuffer_push(outif, msg_buffer, size + off);
585
586           net_output(outif);
587
588           // move to the beginning of the buffer
589
590           size = 0;
591           rem = net_outbuffer_bytes_left(outif) - off;
592         }
593
594       // add the current neighbor's IP address
595       genipcopy(buff + size, &neigh->address);
596       
597       // remember last ip
598       last_ip = (union olsr_ip_addr *)(buff+size);
599       
600       size += olsr_cnf->ipsize;
601
602       // add the corresponding link quality
603       size += olsr_serialize_tc_lq_pair(&buff[size], neigh);
604     }
605
606   // finalize the OLSR header
607
608   head->lower_border = left_border_flag;
609   head->upper_border = 0xff;
610   lq_tc->comm.size = size + off;
611
612   serialize_common((struct olsr_common *)lq_tc);
613
614   net_outbuffer_push(outif, msg_buffer, size + off);
615 }
616
617 void
618 olsr_output_lq_hello(void *para)
619 {
620   struct lq_hello_message lq_hello;
621   struct interface *outif = para;
622
623   if (outif == NULL) {
624     return;
625   }
626
627   // create LQ_HELLO in internal format
628   create_lq_hello(&lq_hello, outif);
629
630   // convert internal format into transmission format, send it
631   serialize_lq_hello(&lq_hello, outif);
632
633   // destroy internal format
634   destroy_lq_hello(&lq_hello);
635
636   if(net_output_pending(outif) && (!outif->immediate_send_tc || TIMED_OUT(outif->fwdtimer))) {
637     net_output(outif);
638   }
639 }
640
641 void
642 olsr_output_lq_tc(void *para)
643 {
644   static int prev_empty = 1;
645   struct lq_tc_message lq_tc;
646   struct interface *outif = para;
647
648   if (outif == NULL) {
649     return;
650   }
651   // create LQ_TC in internal format
652
653   create_lq_tc(&lq_tc, outif);
654
655   // a) the message is not empty
656
657   if (lq_tc.neigh != NULL) {
658       prev_empty = 0;
659       
660       // convert internal format into transmission format, send it
661       serialize_lq_tc(&lq_tc, outif);
662
663   // b) this is the first empty message
664   } else if (prev_empty == 0) {
665       // initialize timer
666
667       set_empty_tc_timer(GET_TIMESTAMP(olsr_cnf->max_tc_vtime * 3 * 1000));
668
669       prev_empty = 1;
670
671       // convert internal format into transmission format, send it
672
673       serialize_lq_tc(&lq_tc, outif);
674
675   // c) this is not the first empty message, send if timer hasn't fired
676   } else if (!TIMED_OUT(get_empty_tc_timer())) {
677       serialize_lq_tc(&lq_tc, outif);
678   }
679   // destroy internal format
680
681   destroy_lq_tc(&lq_tc);
682
683   if(net_output_pending(outif) && (outif->immediate_send_tc || TIMED_OUT(outif->fwdtimer))) {
684     set_buffer_timer(outif);
685   }
686 }
687
688 /*
689  * Local Variables:
690  * c-basic-offset: 2
691  * End:
692  */