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