As requested...
[olsrd.git] / src / olsr.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * * Redistributions of source code must retain the above copyright
11  *   notice, this list of conditions and the following disclaimer.
12  * * Redistributions in binary form must reproduce the above copyright
13  *   notice, this list of conditions and the following disclaimer in
14  *   the documentation and/or other materials provided with the
15  *   distribution.
16  * * Neither the name of olsr.org, olsrd nor the names of its
17  *   contributors may be used to endorse or promote products derived
18  *   from this software without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
28  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
30  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31  * POSSIBILITY OF SUCH DAMAGE.
32  *
33  * Visit http://www.olsr.org for more information.
34  *
35  * If you find this software useful feel free to make a donation
36  * to the project. For more information see the website or contact
37  * the copyright holders.
38  *
39  */
40
41 /**
42  * All these functions are global
43  */
44
45 #include "defs.h"
46 #include "olsr.h"
47 #include "link_set.h"
48 #include "two_hop_neighbor_table.h"
49 #include "tc_set.h"
50 #include "duplicate_set.h"
51 #include "mpr_selector_set.h"
52 #include "mid_set.h"
53 #include "mpr.h"
54 #include "lq_mpr.h"
55 #include "olsr_spf.h"
56 #include "scheduler.h"
57 #include "apm.h"
58 #include "misc.h"
59 #include "neighbor_table.h"
60 #include "log.h"
61 #include "lq_packet.h"
62 #include "common/avl.h"
63 #include "net_olsr.h"
64 #include "lq_plugin.h"
65
66 #include <stdarg.h>
67 #include <errno.h>
68 #include <unistd.h>
69 #include <stdlib.h>
70
71 static void olsr_update_willingness(void *);
72 static void olsr_trigger_forced_update(void *);
73
74 bool changes_topology;
75 bool changes_neighborhood;
76 bool changes_hna;
77 bool changes_force;
78
79 /**
80  * Process changes functions
81  */
82
83 struct pcf
84 {
85   int (*function)(int, int, int);
86   struct pcf *next;
87 };
88
89 static struct pcf *pcf_list;
90
91 static uint16_t message_seqno;
92
93 /**
94  *Initialize the message sequence number as a random value
95  */
96 void
97 init_msg_seqno(void)
98 {
99   message_seqno = random() & 0xFFFF;
100 }
101
102 /**
103  * Get and increment the message sequence number
104  *
105  *@return the seqno
106  */
107 uint16_t
108 get_msg_seqno(void)
109 {
110   return message_seqno++;
111 }
112
113
114 void
115 register_pcf(int (*f)(int, int, int))
116 {
117   struct pcf *new_pcf;
118
119   OLSR_PRINTF(1, "Registering pcf function\n");
120
121   new_pcf = olsr_malloc(sizeof(struct pcf), "New PCF");
122
123   new_pcf->function = f;
124   new_pcf->next = pcf_list;
125   pcf_list = new_pcf;
126
127 }
128
129
130 /**
131  *Process changes in neighborhood or/and topology.
132  *Re-calculates the neighborhood/topology if there
133  *are any updates - then calls the right functions to
134  *update the routing table.
135  *@return 0
136  */
137 void
138 olsr_process_changes(void)
139 {
140   struct pcf *tmp_pc_list;
141
142 #ifdef DEBUG
143   if(changes_neighborhood)
144     OLSR_PRINTF(3, "CHANGES IN NEIGHBORHOOD\n");
145   if(changes_topology)
146     OLSR_PRINTF(3, "CHANGES IN TOPOLOGY\n");
147   if(changes_hna)
148     OLSR_PRINTF(3, "CHANGES IN HNA\n");
149 #endif
150
151   if(!changes_force &&
152      0 >= olsr_cnf->lq_dlimit)
153     return;
154
155   if(!changes_neighborhood &&
156      !changes_topology &&
157      !changes_hna)
158     return;
159
160   if (olsr_cnf->debug_level > 0 && olsr_cnf->clear_screen && isatty(1))
161   {
162       clear_console();
163       printf("       *** %s (%s on %s) ***\n", olsrd_version, build_date, build_host);
164   }
165
166   if (changes_neighborhood) {
167     olsr_calculate_lq_mpr();
168   }
169
170   /* calculate the routing table */
171   if (changes_neighborhood || changes_topology || changes_hna) {
172     olsr_calculate_routing_table();
173   }
174
175   if (olsr_cnf->debug_level > 0)
176     {
177       if (olsr_cnf->debug_level > 2)
178         {
179           olsr_print_mid_set();
180
181           if (olsr_cnf->debug_level > 3)
182             {
183              if (olsr_cnf->debug_level > 8)
184                {
185                  olsr_print_duplicate_table();
186                }
187               olsr_print_hna_set();
188             }
189         }
190
191 #if 1
192       olsr_print_link_set();
193       olsr_print_neighbor_table();
194       olsr_print_two_hop_neighbor_table();
195       olsr_print_tc_table();
196 #endif
197     }
198
199   for(tmp_pc_list = pcf_list;
200       tmp_pc_list != NULL;
201       tmp_pc_list = tmp_pc_list->next)
202     {
203       tmp_pc_list->function(changes_neighborhood,
204                             changes_topology,
205                             changes_hna);
206     }
207
208   changes_neighborhood = false;
209   changes_topology = false;
210   changes_hna = false;
211   changes_force = false;
212 }
213
214 /*
215  * Callback for the periodic route calculation.
216  */
217 static void
218 olsr_trigger_forced_update(void *unused __attribute__((unused))) {
219
220   changes_force = true;
221   changes_neighborhood = true;
222   changes_topology = true;
223   changes_hna = true;
224
225   olsr_process_changes();
226 }
227
228 /**
229  *Initialize all the tables used(neighbor,
230  *topology, MID,  HNA, MPR, dup).
231  *Also initalizes other variables
232  */
233 void
234 olsr_init_tables(void)
235 {
236   /* Some cookies for stats keeping */
237   static struct olsr_cookie_info *periodic_spf_timer_cookie = NULL;
238
239   changes_topology = false;
240   changes_neighborhood = false;
241   changes_hna = false;
242
243   /* Initialize link set */
244   olsr_init_link_set();
245
246   /* Initialize duplicate table */
247   olsr_init_duplicate_set();
248
249   /* Initialize neighbor table */
250   olsr_init_neighbor_table();
251
252   /* Initialize routing table */
253   olsr_init_routing_table();
254
255   /* Initialize two hop table */
256   olsr_init_two_hop_table();
257
258   /* Initialize topology */
259   olsr_init_tc();
260
261   /* Initialize MID set */
262   olsr_init_mid_set();
263
264   /* Initialize HNA set */
265   olsr_init_hna_set();
266
267   /* Initialize MPRS */
268   olsr_init_mprs();
269
270 #if 0
271   /* Initialize Layer 1/2 database */
272   olsr_initialize_layer12();
273 #endif
274
275   /* Start periodic SPF and RIB recalculation */
276   if (olsr_cnf->lq_dinter > 0.0) {
277     periodic_spf_timer_cookie = olsr_alloc_cookie("Periodic SPF",
278                                                   OLSR_COOKIE_TYPE_TIMER);
279     olsr_start_timer((unsigned int)(olsr_cnf->lq_dinter * MSEC_PER_SEC), 5,
280                      OLSR_TIMER_PERIODIC, &olsr_trigger_forced_update, NULL,
281                      periodic_spf_timer_cookie->ci_id);
282   }
283 }
284
285 /**
286  *Check if a message is to be forwarded and forward
287  *it if necessary.
288  *
289  *@param m the OLSR message recieved
290  *
291  *@returns positive if forwarded
292  */
293 int
294 olsr_forward_message(union olsr_message *m, struct interface *in_if,
295                      union olsr_ip_addr *from_addr)
296 {
297   union olsr_ip_addr *src;
298   struct neighbor_entry *neighbor;
299   int msgsize;
300   struct interface *ifn;
301
302   /*
303    * Sven-Ola: We should not flood the mesh with overdue messages. Because
304    * of a bug in parser.c:parse_packet, we have a lot of messages because
305    * all older olsrd's have lq_fish enabled.
306    */
307   if (AF_INET == olsr_cnf->ip_version)
308   {
309     if (m->v4.ttl < 2 || 255 < (int)m->v4.hopcnt + (int)m->v4.ttl) return 0;
310   }
311   else
312   {
313     if (m->v6.ttl < 2|| 255 < (int)m->v6.hopcnt + (int)m->v6.ttl) return 0;
314   }
315
316   /* Lookup sender address */
317   src = olsr_lookup_main_addr_by_alias(from_addr);
318   if(!src)
319     src = from_addr;
320
321   neighbor=olsr_lookup_neighbor_table(src);
322   if(!neighbor)
323     return 0;
324
325   if(neighbor->status != SYM)
326     return 0;
327
328   /* Check MPR */
329   if(olsr_lookup_mprs_set(src) == NULL)
330     {
331 #ifdef DEBUG
332       struct ipaddr_str buf;
333       OLSR_PRINTF(5, "Forward - sender %s not MPR selector\n", olsr_ip_to_string(&buf, src));
334 #endif
335       return 0;
336     }
337
338   /* check if we already forwarded this message */
339   if (olsr_message_is_duplicate(m)) {
340     return 0; /* it's a duplicate, forget about it */
341   }
342
343   /* Treat TTL hopcnt */
344   if(olsr_cnf->ip_version == AF_INET)
345     {
346       /* IPv4 */
347       m->v4.hopcnt++;
348       m->v4.ttl--;
349     }
350   else
351     {
352       /* IPv6 */
353       m->v6.hopcnt++;
354       m->v6.ttl--;
355     }
356
357   /* Update packet data */
358   msgsize = ntohs(m->v4.olsr_msgsize);
359
360   /* looping trough interfaces */
361   OLSR_FOR_ALL_INTERFACES(ifn) {
362       if(net_output_pending(ifn))
363         {
364     /* dont forward to incoming interface if interface is mode ether */
365     if (in_if->mode == IF_MODE_ETHER && ifn == in_if)
366       continue;
367
368           /*
369            * Check if message is to big to be piggybacked
370            */
371           if(net_outbuffer_push(ifn, m, msgsize) != msgsize)
372             {
373               /* Send */
374               net_output(ifn);
375               /* Buffer message */
376               set_buffer_timer(ifn);
377
378               if(net_outbuffer_push(ifn, m, msgsize) != msgsize)
379                 {
380                   OLSR_PRINTF(1, "Received message to big to be forwarded in %s(%d bytes)!", ifn->int_name, msgsize);
381                   olsr_syslog(OLSR_LOG_ERR, "Received message to big to be forwarded on %s(%d bytes)!", ifn->int_name, msgsize);
382                 }
383             }
384         }
385       else
386         {
387           /* No forwarding pending */
388           set_buffer_timer(ifn);
389
390           if(net_outbuffer_push(ifn, m, msgsize) != msgsize)
391             {
392               OLSR_PRINTF(1, "Received message to big to be forwarded in %s(%d bytes)!", ifn->int_name, msgsize);
393               olsr_syslog(OLSR_LOG_ERR, "Received message to big to be forwarded on %s(%d bytes)!", ifn->int_name, msgsize);
394             }
395         }
396   } OLSR_FOR_ALL_INTERFACES_END(ifn);
397
398   return 1;
399 }
400
401 /**
402  * Wrapper for the timer callback.
403  */
404 static void
405 olsr_expire_buffer_timer(void *context)
406 {
407   struct interface *ifn;
408
409   ifn = (struct interface *)context;
410
411   /*
412    * Clear the pointer to indicate that this timer has
413    * been expired and needs to be restarted in case there
414    * will be another message queued in the future.
415    */
416   ifn->buffer_hold_timer = NULL;
417
418 #ifdef DEBUG
419   OLSR_PRINTF(1, "Buffer Holdtimer for %s timed out\n", ifn->int_name);
420 #endif
421
422   /*
423    * Do we have something to emit ?
424    */
425   if (!net_output_pending(ifn)) {
426     return;
427   }
428
429   net_output(ifn);
430 }
431
432 /*
433  * set_buffer_timer
434  *
435  * Kick a hold-down timer which defers building of a message.
436  * This has the desired effect that olsr messages get bigger.
437  */
438 void
439 set_buffer_timer(struct interface *ifn)
440 {
441
442   /*
443    * Bail if there is already a timer running.
444    */
445   if (ifn->buffer_hold_timer) {
446     return;
447   }
448
449   /*
450    * This is the first message since the last time this interface has
451    * been drained. Flush the buffer in second or so.
452    */
453   ifn->buffer_hold_timer =
454     olsr_start_timer(OLSR_BUFFER_HOLD_TIME, OLSR_BUFFER_HOLD_JITTER,
455                      OLSR_TIMER_ONESHOT, &olsr_expire_buffer_timer, ifn,
456                      buffer_hold_timer_cookie->ci_id);
457 }
458
459 void
460 olsr_init_willingness(void)
461 {
462   /* Some cookies for stats keeping */
463   static struct olsr_cookie_info *willingness_timer_cookie = NULL;
464
465   if (olsr_cnf->willingness_auto) {
466
467     /* Run it first and then periodic. */
468     olsr_update_willingness(NULL);
469
470     willingness_timer_cookie = olsr_alloc_cookie("Update Willingness",
471                                                  OLSR_COOKIE_TYPE_TIMER);
472     olsr_start_timer((unsigned int)olsr_cnf->will_int * MSEC_PER_SEC, 5,
473                      OLSR_TIMER_PERIODIC, &olsr_update_willingness, NULL,
474                      willingness_timer_cookie->ci_id);
475   }
476 }
477
478 static void
479 olsr_update_willingness(void *foo __attribute__((unused)))
480 {
481   int tmp_will = olsr_cnf->willingness;
482
483   /* Re-calculate willingness */
484   olsr_cnf->willingness = olsr_calculate_willingness();
485
486   if(tmp_will != olsr_cnf->willingness)
487     {
488       OLSR_PRINTF(1, "Local willingness updated: old %d new %d\n", tmp_will, olsr_cnf->willingness);
489     }
490 }
491
492
493 /**
494  *Calculate this nodes willingness to act as a MPR
495  *based on either a fixed value or the power status
496  *of the node using APM
497  *
498  *@return a 8bit value from 0-7 representing the willingness
499  */
500
501 uint8_t
502 olsr_calculate_willingness(void)
503 {
504   struct olsr_apm_info ainfo;
505
506   /* If fixed willingness */
507   if(!olsr_cnf->willingness_auto)
508     return olsr_cnf->willingness;
509
510   if(apm_read(&ainfo) < 1)
511     return WILL_DEFAULT;
512
513   apm_printinfo(&ainfo);
514
515   /* If AC powered */
516   if(ainfo.ac_line_status == OLSR_AC_POWERED)
517     return 6;
518
519   /* If battery powered
520    *
521    * juice > 78% will: 3
522    * 78% > juice > 26% will: 2
523    * 26% > juice will: 1
524    */
525   return (ainfo.battery_percentage / 26);
526 }
527
528 const char *
529 olsr_msgtype_to_string(uint8_t msgtype)
530 {
531   static char type[20];
532
533   switch(msgtype)
534     {
535     case(HELLO_MESSAGE):
536       return "HELLO";
537     case(TC_MESSAGE):
538       return "TC";
539     case(MID_MESSAGE):
540       return "MID";
541     case(HNA_MESSAGE):
542       return "HNA";
543     case(LQ_HELLO_MESSAGE):
544       return("LQ-HELLO");
545     case(LQ_TC_MESSAGE):
546       return("LQ-TC");
547     default:
548       break;
549     }
550
551   snprintf(type, sizeof(type), "UNKNOWN(%d)", msgtype);
552   return type;
553 }
554
555
556 const char *
557 olsr_link_to_string(uint8_t linktype)
558 {
559   static char type[20];
560
561   switch(linktype)
562     {
563     case(UNSPEC_LINK):
564       return "UNSPEC";
565     case(ASYM_LINK):
566       return "ASYM";
567     case(SYM_LINK):
568       return "SYM";
569     case(LOST_LINK):
570       return "LOST";
571     case(HIDE_LINK):
572       return "HIDE";
573     default:
574       break;
575     }
576
577   snprintf(type, sizeof(type), "UNKNOWN(%d)", linktype);
578   return type;
579 }
580
581
582 const char *
583 olsr_status_to_string(uint8_t status)
584 {
585   static char type[20];
586
587   switch(status)
588     {
589     case(NOT_NEIGH):
590       return "NOT NEIGH";
591     case(SYM_NEIGH):
592       return "NEIGHBOR";
593     case(MPR_NEIGH):
594       return "MPR";
595     default:
596       break;
597     }
598
599   snprintf(type, sizeof(type), "UNKNOWN(%d)", status);
600   return type;
601 }
602
603
604 /**
605  *Termination function to be called whenever a error occures
606  *that requires the daemon to terminate
607  *
608  *@param msg the message to write to the syslog and possibly stdout
609  */
610
611 void
612 olsr_exit(const char *msg, int val)
613 {
614   OLSR_PRINTF(1, "OLSR EXIT: %s\n", msg);
615   olsr_syslog(OLSR_LOG_ERR, "olsrd exit: %s\n", msg);
616   fflush(stdout);
617   olsr_cnf->exit_value = val;
618   app_state = STATE_SHUTDOWN;
619 }
620
621
622 /**
623  * Wrapper for malloc(3) that does error-checking
624  *
625  * @param size the number of bytes to allocalte
626  * @param caller a string identifying the caller for
627  * use in error messaging
628  *
629  * @return a void pointer to the memory allocated
630  */
631 void *
632 olsr_malloc(size_t size, const char *id)
633 {
634   void *ptr;
635
636   /*
637    * Not all the callers do a proper cleaning of memory.
638    * Clean it on behalf of those.
639    */
640   ptr = calloc(1, size);
641
642   if (!ptr) {
643       const char * const err_msg = strerror(errno);
644       OLSR_PRINTF(1, "OUT OF MEMORY: %s\n", err_msg);
645       olsr_syslog(OLSR_LOG_ERR, "olsrd: out of memory!: %s\n", err_msg);
646       olsr_exit(id, EXIT_FAILURE);
647   }
648
649 #if 0
650   /* useful for debugging */
651   OLSR_PRINTF(1, "MEMORY: alloc %s %p, %u bytes\n",
652               id, ptr, size);
653 #endif
654
655   return ptr;
656 }
657
658 /*
659  * Same as strdup but works with olsr_malloc
660  */
661 char *
662 olsr_strdup(const char *s)
663 {
664   char *ret = olsr_malloc(1 + strlen(s), "olsr_strdup");
665   strcpy(ret, s);
666   return ret;
667 }
668
669 /*
670  * Same as strndup but works with olsr_malloc
671  */
672 char *
673 olsr_strndup(const char *s, size_t n)
674 {
675   size_t len = n < strlen(s) ? n : strlen(s);
676   char *ret = olsr_malloc(1 + len, "olsr_strndup");
677   strncpy(ret, s, len);
678   ret[len] = 0;
679   return ret;
680 }
681
682 /*
683  * Local Variables:
684  * c-basic-offset: 2
685  * indent-tabs-mode: nil
686  * End:
687  */