src/olsr.c

   1 /*
   2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   3  * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
   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 <signal.h>
  68 #include <errno.h>
  69 #include <unistd.h>
  70 #include <stdlib.h>
  71
  72
  73 olsr_bool changes_topology;
  74 olsr_bool changes_neighborhood;
  75 olsr_bool changes_hna;
  76 olsr_bool changes_force;
  77
  78 /**
  79  * Process changes functions
  80  */
  81
  82 struct pcf
  83 {
  84   int (*function)(int, int, int);
  85   struct pcf *next;
  86 };
  87
  88 static struct pcf *pcf_list;
  89
  90 static olsr_u16_t message_seqno;
  91 union olsr_ip_addr all_zero;
  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 olsr_u16_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      2 <= olsr_cnf->lq_level &&
 153      0 >= olsr_cnf->lq_dlimit)
 154     return;
 155
 156   if(!changes_neighborhood &&
 157      !changes_topology &&
 158      !changes_hna)
 159     return;
 160
 161   if (olsr_cnf->debug_level > 0 && olsr_cnf->clear_screen && isatty(1))
 162   {
 163       clear_console();
 164       printf("       *** %s (%s on %s) ***\n", olsrd_version, build_date, build_host);
 165   }
 166
 167   if (changes_neighborhood) {
 168     if (olsr_cnf->lq_level < 1) {
 169       olsr_calculate_mpr();
 170     } else {
 171       olsr_calculate_lq_mpr();
 172     }
 173   }
 174
 175   /* calculate the routing table */
 176   if (changes_neighborhood || changes_topology || changes_hna) {
 177     olsr_calculate_routing_table();
 178   }
 179
 180   if (olsr_cnf->debug_level > 0)
 181     {
 182       if (olsr_cnf->debug_level > 2)
 183         {
 184           olsr_print_mid_set();
 185
 186           if (olsr_cnf->debug_level > 3)
 187             {
 188              if (olsr_cnf->debug_level > 8)
 189                {
 190                  olsr_print_duplicate_table();
 191                }
 192               olsr_print_hna_set();
 193             }
 194         }
 195
 196 #if 1
 197       olsr_print_link_set();
 198       olsr_print_neighbor_table();
 199       olsr_print_two_hop_neighbor_table();
 200       olsr_print_tc_table();
 201 #endif
 202     }
 203
 204   for(tmp_pc_list = pcf_list;
 205       tmp_pc_list != NULL;
 206       tmp_pc_list = tmp_pc_list->next)
 207     {
 208       tmp_pc_list->function(changes_neighborhood,
 209                             changes_topology,
 210                             changes_hna);
 211     }
 212
 213   changes_neighborhood = OLSR_FALSE;
 214   changes_topology = OLSR_FALSE;
 215   changes_hna = OLSR_FALSE;
 216   changes_force = OLSR_FALSE;
 217 }
 218
 219 /*
 220  * Callback for the periodic route calculation.
 221  */
 222 void
 223 olsr_trigger_forced_update(void *unused __attribute__((unused))) {
 224
 225   changes_force = OLSR_TRUE;
 226   changes_neighborhood = OLSR_TRUE;
 227   changes_topology = OLSR_TRUE;
 228   changes_hna = OLSR_TRUE;
 229
 230   olsr_process_changes();
 231 }
 232
 233 /**
 234  *Initialize all the tables used(neighbor,
 235  *topology, MID,  HNA, MPR, dup).
 236  *Also initalizes other variables
 237  */
 238 void
 239 olsr_init_tables(void)
 240 {
 241   changes_topology = OLSR_FALSE;
 242   changes_neighborhood = OLSR_FALSE;
 243   changes_hna = OLSR_FALSE;
 244
 245   /* Set avl tree comparator */
 246   if (olsr_cnf->ipsize == 4) {
 247     avl_comp_default = avl_comp_ipv4;
 248     avl_comp_prefix_default = avl_comp_ipv4_prefix;
 249   } else {
 250     avl_comp_default = avl_comp_ipv6;
 251     avl_comp_prefix_default = avl_comp_ipv6_prefix;
 252   }
 253
 254   /* Initialize lq plugin set */
 255   init_lq_handler_tree();
 256
 257   /* Initialize link set */
 258   olsr_init_link_set();
 259
 260   /* Initialize duplicate table */
 261   olsr_init_duplicate_set();
 262
 263   /* Initialize neighbor table */
 264   olsr_init_neighbor_table();
 265
 266   /* Initialize routing table */
 267   olsr_init_routing_table();
 268
 269   /* Initialize two hop table */
 270   olsr_init_two_hop_table();
 271
 272   /* Initialize topology */
 273   olsr_init_tc();
 274
 275   /* Initialize mpr selector table */
 276   olsr_init_mprs_set();
 277
 278   /* Initialize MID set */
 279   olsr_init_mid_set();
 280
 281   /* Initialize HNA set */
 282   olsr_init_hna_set();
 283
 284 #if 0
 285   /* Initialize Layer 1/2 database */
 286   olsr_initialize_layer12();
 287 #endif
 288
 289   /* Start periodic SPF and RIB recalculation */
 290   if (olsr_cnf->lq_dinter > 0.0) {
 291     olsr_start_timer((unsigned int)(olsr_cnf->lq_dinter * MSEC_PER_SEC), 5,
 292                      OLSR_TIMER_PERIODIC, &olsr_trigger_forced_update, NULL, 0);
 293   }
 294 }
 295
 296 /**
 297  *Check if a message is to be forwarded and forward
 298  *it if necessary.
 299  *
 300  *@param m the OLSR message recieved
 301  *@param originator the originator of this message
 302  *@param seqno the seqno of the message
 303  *
 304  *@returns positive if forwarded
 305  */
 306 int
 307 olsr_forward_message(union olsr_message *m,
 308                      union olsr_ip_addr *from_addr)
 309 {
 310   union olsr_ip_addr *src;
 311   struct neighbor_entry *neighbor;
 312   int msgsize;
 313   struct interface *ifn;
 314
 315   /*
 316    * Sven-Ola: We should not flood the mesh with overdue messages. Because
 317    * of a bug in parser.c:parse_packet, we have a lot of messages because
 318    * all older olsrd's have lq_fish enabled.
 319    */
 320   if (AF_INET == olsr_cnf->ip_version)
 321   {
 322     if (2 > m->v4.ttl || 255 < (int)m->v4.hopcnt + (int)m->v4.ttl) return 0;
 323   }
 324   else
 325   {
 326     if (2 > m->v6.ttl || 255 < (int)m->v6.hopcnt + (int)m->v6.ttl) return 0;
 327   }
 328
 329   /* Lookup sender address */
 330   src = olsr_lookup_main_addr_by_alias(from_addr);
 331   if(!src)
 332     src = from_addr;
 333
 334   neighbor=olsr_lookup_neighbor_table(src);
 335   if(!neighbor)
 336     return 0;
 337
 338   if(neighbor->status != SYM)
 339     return 0;
 340
 341   /* Check MPR */
 342   if(olsr_lookup_mprs_set(src) == NULL)
 343     {
 344 #ifdef DEBUG
 345       struct ipaddr_str buf;
 346       OLSR_PRINTF(5, "Forward - sender %s not MPR selector\n", olsr_ip_to_string(&buf, src));
 347 #endif
 348       return 0;
 349     }
 350
 351   /* Treat TTL hopcnt */
 352   if(olsr_cnf->ip_version == AF_INET)
 353     {
 354       /* IPv4 */
 355       m->v4.hopcnt++;
 356       m->v4.ttl--;
 357     }
 358   else
 359     {
 360       /* IPv6 */
 361       m->v6.hopcnt++;
 362       m->v6.ttl--;
 363     }
 364
 365   /* Update packet data */
 366   msgsize = ntohs(m->v4.olsr_msgsize);
 367
 368   /* looping trough interfaces */
 369   for (ifn = ifnet; ifn ; ifn = ifn->int_next)
 370     {
 371       if(net_output_pending(ifn))
 372         {
 373           /*
 374            * Check if message is to big to be piggybacked
 375            */
 376           if(net_outbuffer_push(ifn, m, msgsize) != msgsize)
 377             {
 378               /* Send */
 379               net_output(ifn);
 380               /* Buffer message */
 381               set_buffer_timer(ifn);
 382
 383               if(net_outbuffer_push(ifn, m, msgsize) != msgsize)
 384                 {
 385                   OLSR_PRINTF(1, "Received message to big to be forwarded in %s(%d bytes)!", ifn->int_name, msgsize);
 386                   olsr_syslog(OLSR_LOG_ERR, "Received message to big to be forwarded on %s(%d bytes)!", ifn->int_name, msgsize);
 387                 }
 388             }
 389         }
 390       else
 391         {
 392           /* No forwarding pending */
 393           set_buffer_timer(ifn);
 394
 395           if(net_outbuffer_push(ifn, m, msgsize) != msgsize)
 396             {
 397               OLSR_PRINTF(1, "Received message to big to be forwarded in %s(%d bytes)!", ifn->int_name, msgsize);
 398               olsr_syslog(OLSR_LOG_ERR, "Received message to big to be forwarded on %s(%d bytes)!", ifn->int_name, msgsize);
 399             }
 400         }
 401     }
 402   return 1;
 403 }
 404
 405
 406 void
 407 set_buffer_timer(struct interface *ifn)
 408 {
 409   /* Set timer */
 410   ifn->fwdtimer = GET_TIMESTAMP(random() * olsr_cnf->max_jitter * MSEC_PER_SEC / RAND_MAX);
 411 }
 412
 413 void
 414 olsr_init_willingness(void)
 415 {
 416   if (olsr_cnf->willingness_auto) {
 417
 418     /* Run it first and then periodic. */
 419     olsr_update_willingness(NULL);
 420
 421     olsr_start_timer((unsigned int)olsr_cnf->will_int * MSEC_PER_SEC, 5,
 422                      OLSR_TIMER_PERIODIC, &olsr_update_willingness, NULL, 0);
 423   }
 424 }
 425
 426 void
 427 olsr_update_willingness(void *foo __attribute__((unused)))
 428 {
 429   int tmp_will = olsr_cnf->willingness;
 430
 431   /* Re-calculate willingness */
 432   olsr_cnf->willingness = olsr_calculate_willingness();
 433
 434   if(tmp_will != olsr_cnf->willingness)
 435     {
 436       OLSR_PRINTF(1, "Local willingness updated: old %d new %d\n", tmp_will, olsr_cnf->willingness);
 437     }
 438 }
 439
 440
 441 /**
 442  *Calculate this nodes willingness to act as a MPR
 443  *based on either a fixed value or the power status
 444  *of the node using APM
 445  *
 446  *@return a 8bit value from 0-7 representing the willingness
 447  */
 448
 449 olsr_u8_t
 450 olsr_calculate_willingness(void)
 451 {
 452   struct olsr_apm_info ainfo;
 453
 454   /* If fixed willingness */
 455   if(!olsr_cnf->willingness_auto)
 456     return olsr_cnf->willingness;
 457
 458   if(apm_read(&ainfo) < 1)
 459     return WILL_DEFAULT;
 460
 461   apm_printinfo(&ainfo);
 462
 463   /* If AC powered */
 464   if(ainfo.ac_line_status == OLSR_AC_POWERED)
 465     return 6;
 466
 467   /* If battery powered
 468    *
 469    * juice > 78% will: 3
 470    * 78% > juice > 26% will: 2
 471    * 26% > juice will: 1
 472    */
 473   return (ainfo.battery_percentage / 26);
 474 }
 475
 476 const char *
 477 olsr_msgtype_to_string(olsr_u8_t msgtype)
 478 {
 479   static char type[20];
 480
 481   switch(msgtype)
 482     {
 483     case(HELLO_MESSAGE):
 484       return "HELLO";
 485     case(TC_MESSAGE):
 486       return "TC";
 487     case(MID_MESSAGE):
 488       return "MID";
 489     case(HNA_MESSAGE):
 490       return "HNA";
 491     case(LQ_HELLO_MESSAGE):
 492       return("LQ-HELLO");
 493     case(LQ_TC_MESSAGE):
 494       return("LQ-TC");
 495     default:
 496       break;
 497     }
 498
 499   snprintf(type, sizeof(type), "UNKNOWN(%d)", msgtype);
 500   return type;
 501 }
 502
 503
 504 const char *
 505 olsr_link_to_string(olsr_u8_t linktype)
 506 {
 507   static char type[20];
 508
 509   switch(linktype)
 510     {
 511     case(UNSPEC_LINK):
 512       return "UNSPEC";
 513     case(ASYM_LINK):
 514       return "ASYM";
 515     case(SYM_LINK):
 516       return "SYM";
 517     case(LOST_LINK):
 518       return "LOST";
 519     case(HIDE_LINK):
 520       return "HIDE";
 521     default:
 522       break;
 523     }
 524
 525   snprintf(type, sizeof(type), "UNKNOWN(%d)", linktype);
 526   return type;
 527 }
 528
 529
 530 const char *
 531 olsr_status_to_string(olsr_u8_t status)
 532 {
 533   static char type[20];
 534
 535   switch(status)
 536     {
 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 msg the message to write to the syslog and possibly stdout
 557  */
 558
 559 void
 560 olsr_exit(const char *msg, int val)
 561 {
 562   OLSR_PRINTF(1, "OLSR EXIT: %s\n", msg);
 563   olsr_syslog(OLSR_LOG_ERR, "olsrd exit: %s\n", msg);
 564   fflush(stdout);
 565   olsr_cnf->exit_value = val;
 566
 567   raise(SIGTERM);
 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)
 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       const char * const err_msg = strerror(errno);
 593       OLSR_PRINTF(1, "OUT OF MEMORY: %s\n", err_msg);
 594       olsr_syslog(OLSR_LOG_ERR, "olsrd: out of memory!: %s\n", err_msg);
 595       olsr_exit(id, EXIT_FAILURE);
 596   }
 597
 598 #if 0
 599   /* useful for debugging */
 600   olsr_printf(1, "MEMORY: alloc %s %p, %u bytes\n",
 601               id, ptr, size);
 602 #endif
 603
 604   return ptr;
 605 }
 606
 607
 608 /**
 609  *Wrapper for printf that prints to a specific
 610  *debuglevel upper limit
 611  *
 612  */
 613
 614 int
 615 olsr_printf(int loglevel, const char *format, ...)
 616 {
 617   if((loglevel <= olsr_cnf->debug_level) && debug_handle)
 618     {
 619       va_list arglist;
 620       va_start(arglist, format);
 621       vfprintf(debug_handle, format, arglist);
 622       va_end(arglist);
 623     }
 624   return 0;
 625 }
 626
 627 /*
 628  * Local Variables:
 629  * c-basic-offset: 2
 630  * End:
 631  */