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