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