Add OLSR support for NIIT (IP 4to6 tunnel device)
[olsrd.git] / src / olsr.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004, Andreas Tonnesen(andreto@olsr.org)
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 /**
43  * All these functions are global
44  */
45
46 #include "defs.h"
47 #include "olsr.h"
48 #include "link_set.h"
49 #include "two_hop_neighbor_table.h"
50 #include "tc_set.h"
51 #include "duplicate_set.h"
52 #include "mpr_selector_set.h"
53 #include "mid_set.h"
54 #include "mpr.h"
55 #include "lq_mpr.h"
56 #include "olsr_spf.h"
57 #include "scheduler.h"
58 #include "apm.h"
59 #include "misc.h"
60 #include "neighbor_table.h"
61 #include "log.h"
62 #include "lq_packet.h"
63 #include "common/avl.h"
64 #include "net_olsr.h"
65 #include "lq_plugin.h"
66 #include "duplicate_handler.h"
67
68 #include <stdarg.h>
69 #include <signal.h>
70 #include <unistd.h>
71
72 bool changes_topology;
73 bool changes_neighborhood;
74 bool changes_hna;
75 bool changes_force;
76
77 /*COLLECT startup sleeps caused by warnings*/
78
79 #ifdef OLSR_COLLECT_STARTUP_SLEEP
80 static int max_startup_sleep = 0;
81 #endif
82 static int sum_startup_sleep = 0;
83
84 void olsr_startup_sleep(int s)
85 {
86   sum_startup_sleep += s;
87 #ifdef OLSR_COLLECT_STARTUP_SLEEP
88   if (s > max_startup_sleep) max_startup_sleep=s;
89 #else
90   sleep(s);
91 #endif
92 }
93
94 void olsr_do_startup_sleep(void)
95 {
96 #ifdef OLSR_COLLECT_STARTUP_SLEEP
97   if (sum_startup_sleep > max_startup_sleep)
98     printf("OLSR encountered multiple problems on startup, which should delay startup by %i seconds.\nAs this is quite much time, OLSR will sleep only %i seconds.\nBUT YOU SHOULD FIX ABOVE PROBLEMS!\n",
99            sum_startup_sleep,max_startup_sleep);
100   sleep(max_startup_sleep);
101 #else
102   if (sum_startup_sleep > 0) 
103     printf("olsrd startup was delayed %i seconds due to various nasty error messages.\nYOU SHOULD REALLY FIX ABOVE PROBLEMS!\n",
104            sum_startup_sleep);
105 #endif
106 }
107
108 /**
109  * Process changes functions
110  */
111
112 struct pcf {
113   int (*function) (int, int, int);
114   struct pcf *next;
115 };
116
117 static struct pcf *pcf_list;
118
119 static uint16_t message_seqno;
120 union olsr_ip_addr all_zero;
121
122 /**
123  *Initialize the message sequence number as a random value
124  */
125 void
126 init_msg_seqno(void)
127 {
128   message_seqno = random() & 0xFFFF;
129 }
130
131 /**
132  * Get and increment the message sequence number
133  *
134  *@return the seqno
135  */
136 uint16_t
137 get_msg_seqno(void)
138 {
139   return message_seqno++;
140 }
141
142 bool
143 olsr_is_bad_duplicate_msg_seqno(uint16_t seqno) {
144   int32_t diff = (int32_t) seqno - (int32_t) message_seqno;
145
146   if (diff < -32768) {
147     diff += 65536;
148   }
149   else if (diff > 32767) {
150     diff -= 65536;
151   }
152   return diff > 0;
153 }
154
155 void
156 register_pcf(int (*f) (int, int, int))
157 {
158   struct pcf *new_pcf;
159
160   OLSR_PRINTF(1, "Registering pcf function\n");
161
162   new_pcf = olsr_malloc(sizeof(struct pcf), "New PCF");
163
164   new_pcf->function = f;
165   new_pcf->next = pcf_list;
166   pcf_list = new_pcf;
167
168 }
169
170 /**
171  *Process changes in neighborhood or/and topology.
172  *Re-calculates the neighborhood/topology if there
173  *are any updates - then calls the right functions to
174  *update the routing table.
175  *@return 0
176  */
177 void
178 olsr_process_changes(void)
179 {
180   struct pcf *tmp_pc_list;
181
182 #ifdef DEBUG
183   if (changes_neighborhood)
184     OLSR_PRINTF(3, "CHANGES IN NEIGHBORHOOD\n");
185   if (changes_topology)
186     OLSR_PRINTF(3, "CHANGES IN TOPOLOGY\n");
187   if (changes_hna)
188     OLSR_PRINTF(3, "CHANGES IN HNA\n");
189 #endif
190
191   if (!changes_force && 2 <= olsr_cnf->lq_level && 0 >= olsr_cnf->lq_dlimit)
192     return;
193
194   if (!changes_neighborhood && !changes_topology && !changes_hna)
195     return;
196
197   if (olsr_cnf->debug_level > 0 && olsr_cnf->clear_screen && isatty(1)) {
198     clear_console();
199     printf("       *** %s (%s on %s) ***\n", olsrd_version, build_date, build_host);
200   }
201
202   if (changes_neighborhood) {
203     if (olsr_cnf->lq_level < 1) {
204       olsr_calculate_mpr();
205     } else {
206       olsr_calculate_lq_mpr();
207     }
208   }
209
210   /* calculate the routing table */
211   if (changes_neighborhood || changes_topology || changes_hna) {
212     olsr_calculate_routing_table();
213   }
214
215   if (olsr_cnf->debug_level > 0) {
216     if (olsr_cnf->debug_level > 2) {
217       olsr_print_mid_set();
218
219       if (olsr_cnf->debug_level > 3) {
220         if (olsr_cnf->debug_level > 8) {
221           olsr_print_duplicate_table();
222         }
223         olsr_print_hna_set();
224       }
225     }
226 #if 1
227     olsr_print_link_set();
228     olsr_print_neighbor_table();
229     olsr_print_two_hop_neighbor_table();
230     olsr_print_tc_table();
231 #endif
232   }
233
234   for (tmp_pc_list = pcf_list; tmp_pc_list != NULL; tmp_pc_list = tmp_pc_list->next) {
235     tmp_pc_list->function(changes_neighborhood, changes_topology, changes_hna);
236   }
237
238   changes_neighborhood = false;
239   changes_topology = false;
240   changes_hna = false;
241   changes_force = false;
242 }
243
244 /*
245  * Callback for the periodic route calculation.
246  */
247 void
248 olsr_trigger_forced_update(void *unused __attribute__ ((unused)))
249 {
250
251   changes_force = true;
252   changes_neighborhood = true;
253   changes_topology = true;
254   changes_hna = true;
255
256   olsr_process_changes();
257 }
258
259 /**
260  *Initialize all the tables used(neighbor,
261  *topology, MID,  HNA, MPR, dup).
262  *Also initalizes other variables
263  */
264 void
265 olsr_init_tables(void)
266 {
267   changes_topology = false;
268   changes_neighborhood = false;
269   changes_hna = false;
270
271   /* Set avl tree comparator */
272   if (olsr_cnf->ipsize == 4) {
273     avl_comp_default = avl_comp_ipv4;
274     avl_comp_prefix_default = avl_comp_ipv4_prefix;
275   } else {
276     avl_comp_default = avl_comp_ipv6;
277     avl_comp_prefix_default = avl_comp_ipv6_prefix;
278   }
279
280   /* Initialize lq plugin set */
281   init_lq_handler_tree();
282
283   /* Initialize link set */
284   olsr_init_link_set();
285
286   /* Initialize duplicate table */
287   olsr_init_duplicate_set();
288
289   /* Initialize neighbor table */
290   olsr_init_neighbor_table();
291
292   /* Initialize routing table */
293   olsr_init_routing_table();
294
295   /* Initialize two hop table */
296   olsr_init_two_hop_table();
297
298   /* Initialize topology */
299   olsr_init_tc();
300
301   /* Initialize mpr selector table */
302   olsr_init_mprs_set();
303
304   /* Initialize MID set */
305   olsr_init_mid_set();
306
307   /* Initialize HNA set */
308   olsr_init_hna_set();
309
310   /* Initialize duplicate handler */
311 #ifndef NO_DUPLICATE_DETECTION_HANDLER
312   olsr_duplicate_handler_init();
313 #endif
314
315   /* Start periodic SPF and RIB recalculation */
316   if (olsr_cnf->lq_dinter > 0.0) {
317     olsr_start_timer((unsigned int)(olsr_cnf->lq_dinter * MSEC_PER_SEC), 5, OLSR_TIMER_PERIODIC, &olsr_trigger_forced_update, NULL,
318                      0);
319   }
320 }
321
322 /**
323  *Check if a message is to be forwarded and forward
324  *it if necessary.
325  *
326  *@param m the OLSR message to be forwarded
327  *@param neighbour we received message from
328  *
329  *@returns positive if forwarded
330  */
331 int
332 olsr_forward_message(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr)
333 {
334   union olsr_ip_addr *src;
335   struct neighbor_entry *neighbor;
336   int msgsize;
337   struct interface *ifn;
338
339
340   /*
341    * Sven-Ola: We should not flood the mesh with overdue messages. Because
342    * of a bug in parser.c:parse_packet, we have a lot of messages because
343    * all older olsrd's have lq_fish enabled.
344    */
345   if (AF_INET == olsr_cnf->ip_version) {
346     if (m->v4.ttl < 2 || 255 < (int)m->v4.hopcnt + (int)m->v4.ttl)
347       return 0;
348   } else {
349     if (m->v6.ttl < 2 || 255 < (int)m->v6.hopcnt + (int)m->v6.ttl)
350       return 0;
351   }
352
353   /* Lookup sender address */
354   src = mid_lookup_main_addr(from_addr);
355   if (!src)
356     src = from_addr;
357
358   neighbor = olsr_lookup_neighbor_table(src);
359   if (!neighbor)
360     return 0;
361
362   if (neighbor->status != SYM)
363     return 0;
364
365   /* Check MPR */
366   if (olsr_lookup_mprs_set(src) == NULL) {
367 #ifdef DEBUG
368     struct ipaddr_str buf;
369     OLSR_PRINTF(5, "Forward - sender %s not MPR selector\n", olsr_ip_to_string(&buf, src));
370 #endif
371     return 0;
372   }
373
374   if (olsr_message_is_duplicate(m)) {
375     return 0;
376   }
377
378   /* Treat TTL hopcnt */
379   if (olsr_cnf->ip_version == AF_INET) {
380     /* IPv4 */
381     m->v4.hopcnt++;
382     m->v4.ttl--;
383   } else {
384     /* IPv6 */
385     m->v6.hopcnt++;
386     m->v6.ttl--;
387   }
388
389   /* Update packet data */
390   msgsize = ntohs(m->v4.olsr_msgsize);
391
392   /* looping trough interfaces */
393   for (ifn = ifnet; ifn; ifn = ifn->int_next) {
394     if (net_output_pending(ifn)) {
395
396       /* dont forward to incoming interface if interface is mode ether */
397       if (in_if->mode == IF_MODE_ETHER && ifn == in_if) continue;
398
399       /*
400        * Check if message is to big to be piggybacked
401        */
402       if (net_outbuffer_push(ifn, m, msgsize) != msgsize) {
403         /* Send */
404         net_output(ifn);
405         /* Buffer message */
406         set_buffer_timer(ifn);
407
408         if (net_outbuffer_push(ifn, m, msgsize) != msgsize) {
409           OLSR_PRINTF(1, "Received message to big to be forwarded in %s(%d bytes)!", ifn->int_name, msgsize);
410           olsr_syslog(OLSR_LOG_ERR, "Received message to big to be forwarded on %s(%d bytes)!", ifn->int_name, msgsize);
411         }
412       }
413     } else {
414       /* No forwarding pending */
415       set_buffer_timer(ifn);
416
417       if (net_outbuffer_push(ifn, m, msgsize) != msgsize) {
418         OLSR_PRINTF(1, "Received message to big to be forwarded in %s(%d bytes)!", ifn->int_name, msgsize);
419         olsr_syslog(OLSR_LOG_ERR, "Received message to big to be forwarded on %s(%d bytes)!", ifn->int_name, msgsize);
420       }
421     }
422   }
423   return 1;
424 }
425
426 void
427 set_buffer_timer(struct interface *ifn)
428 {
429   /* Set timer */
430   ifn->fwdtimer = GET_TIMESTAMP(random() * olsr_cnf->max_jitter * MSEC_PER_SEC / RAND_MAX);
431 }
432
433 void
434 olsr_init_willingness(void)
435 {
436   if (olsr_cnf->willingness_auto) {
437
438     /* Run it first and then periodic. */
439     olsr_update_willingness(NULL);
440
441     olsr_start_timer((unsigned int)olsr_cnf->will_int * MSEC_PER_SEC, 5, OLSR_TIMER_PERIODIC, &olsr_update_willingness, NULL, 0);
442   }
443 }
444
445 void
446 olsr_update_willingness(void *foo __attribute__ ((unused)))
447 {
448   int tmp_will = olsr_cnf->willingness;
449
450   /* Re-calculate willingness */
451   olsr_cnf->willingness = olsr_calculate_willingness();
452
453   if (tmp_will != olsr_cnf->willingness) {
454     OLSR_PRINTF(1, "Local willingness updated: old %d new %d\n", tmp_will, olsr_cnf->willingness);
455   }
456 }
457
458 /**
459  *Calculate this nodes willingness to act as a MPR
460  *based on either a fixed value or the power status
461  *of the node using APM
462  *
463  *@return a 8bit value from 0-7 representing the willingness
464  */
465
466 uint8_t
467 olsr_calculate_willingness(void)
468 {
469   struct olsr_apm_info ainfo;
470
471   /* If fixed willingness */
472   if (!olsr_cnf->willingness_auto)
473     return olsr_cnf->willingness;
474
475   if (apm_read(&ainfo) < 1)
476     return WILL_DEFAULT;
477
478   apm_printinfo(&ainfo);
479
480   /* If AC powered */
481   if (ainfo.ac_line_status == OLSR_AC_POWERED)
482     return 6;
483
484   /* If battery powered
485    *
486    * juice > 78% will: 3
487    * 78% > juice > 26% will: 2
488    * 26% > juice will: 1
489    */
490   return (ainfo.battery_percentage / 26);
491 }
492
493 const char *
494 olsr_msgtype_to_string(uint8_t msgtype)
495 {
496   static char type[20];
497
498   switch (msgtype) {
499   case (HELLO_MESSAGE):
500     return "HELLO";
501   case (TC_MESSAGE):
502     return "TC";
503   case (MID_MESSAGE):
504     return "MID";
505   case (HNA_MESSAGE):
506     return "HNA";
507   case (LQ_HELLO_MESSAGE):
508     return ("LQ-HELLO");
509   case (LQ_TC_MESSAGE):
510     return ("LQ-TC");
511   default:
512     break;
513   }
514
515   snprintf(type, sizeof(type), "UNKNOWN(%d)", msgtype);
516   return type;
517 }
518
519 const char *
520 olsr_link_to_string(uint8_t linktype)
521 {
522   static char type[20];
523
524   switch (linktype) {
525   case (UNSPEC_LINK):
526     return "UNSPEC";
527   case (ASYM_LINK):
528     return "ASYM";
529   case (SYM_LINK):
530     return "SYM";
531   case (LOST_LINK):
532     return "LOST";
533   case (HIDE_LINK):
534     return "HIDE";
535   default:
536     break;
537   }
538
539   snprintf(type, sizeof(type), "UNKNOWN(%d)", linktype);
540   return type;
541 }
542
543 const char *
544 olsr_status_to_string(uint8_t status)
545 {
546   static char type[20];
547
548   switch (status) {
549   case (NOT_NEIGH):
550     return "NOT NEIGH";
551   case (SYM_NEIGH):
552     return "NEIGHBOR";
553   case (MPR_NEIGH):
554     return "MPR";
555   default:
556     break;
557   }
558
559   snprintf(type, sizeof(type), "UNKNOWN(%d)", status);
560   return type;
561 }
562
563 /**
564  *Termination function to be called whenever a error occures
565  *that requires the daemon to terminate
566  *
567  *@param msg the message to write to the syslog and possibly stdout
568  */
569
570 void
571 olsr_exit(const char *msg, int val)
572 {
573   OLSR_PRINTF(1, "OLSR EXIT: %s\n", msg);
574   olsr_syslog(OLSR_LOG_ERR, "olsrd exit: %s\n", msg);
575   fflush(stdout);
576   olsr_cnf->exit_value = val;
577
578   raise(SIGTERM);
579 }
580
581 /**
582  * Wrapper for malloc(3) that does error-checking
583  *
584  * @param size the number of bytes to allocalte
585  * @param caller a string identifying the caller for
586  * use in error messaging
587  *
588  * @return a void pointer to the memory allocated
589  */
590 void *
591 olsr_malloc(size_t size, const char *id)
592 {
593   void *ptr;
594
595   /*
596    * Not all the callers do a proper cleaning of memory.
597    * Clean it on behalf of those.
598    */
599   ptr = calloc(1, size);
600
601   if (!ptr) {
602     const char *const err_msg = strerror(errno);
603     OLSR_PRINTF(1, "OUT OF MEMORY: %s\n", err_msg);
604     olsr_syslog(OLSR_LOG_ERR, "olsrd: out of memory!: %s\n", err_msg);
605     olsr_exit(id, EXIT_FAILURE);
606   }
607 #if 0
608   /* useful for debugging */
609   olsr_printf(1, "MEMORY: alloc %s %p, %u bytes\n", id, ptr, size);
610 #endif
611
612   return ptr;
613 }
614
615 /**
616  *Wrapper for printf that prints to a specific
617  *debuglevel upper limit
618  *
619  */
620
621 int
622 olsr_printf(int loglevel, const char *format, ...)
623 {
624   if ((loglevel <= olsr_cnf->debug_level) && debug_handle) {
625     va_list arglist;
626     va_start(arglist, format);
627     vfprintf(debug_handle, format, arglist);
628     va_end(arglist);
629   }
630   return 0;
631 }
632
633 /*
634  * Local Variables:
635  * c-basic-offset: 2
636  * indent-tabs-mode: nil
637  * End:
638  */