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  */