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