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_WARN(LOG_NETWORKING, "Received message to big to be forwarded in %s(%d bytes)!", ifn->int_name, msgsize);
 381                 }
 382             }
 383         }
 384       else
 385         {
 386           /* No forwarding pending */
 387           set_buffer_timer(ifn);
 388
 389           if(net_outbuffer_push(ifn, m, msgsize) != msgsize)
 390             {
 391               OLSR_WARN(LOG_NETWORKING, "Received message to big to be forwarded in %s(%d bytes)!", ifn->int_name, msgsize);
 392             }
 393         }
 394   } OLSR_FOR_ALL_INTERFACES_END(ifn);
 395
 396   return 1;
 397 }
 398
 399 /**
 400  * Wrapper for the timer callback.
 401  */
 402 static void
 403 olsr_expire_buffer_timer(void *context)
 404 {
 405   struct interface *ifn;
 406
 407   ifn = (struct interface *)context;
 408
 409   /*
 410    * Clear the pointer to indicate that this timer has
 411    * been expired and needs to be restarted in case there
 412    * will be another message queued in the future.
 413    */
 414   ifn->buffer_hold_timer = NULL;
 415
 416 #ifdef DEBUG
 417   OLSR_PRINTF(1, "Buffer Holdtimer for %s timed out\n", ifn->int_name);
 418 #endif
 419
 420   /*
 421    * Do we have something to emit ?
 422    */
 423   if (!net_output_pending(ifn)) {
 424     return;
 425   }
 426
 427   net_output(ifn);
 428 }
 429
 430 /*
 431  * set_buffer_timer
 432  *
 433  * Kick a hold-down timer which defers building of a message.
 434  * This has the desired effect that olsr messages get bigger.
 435  */
 436 void
 437 set_buffer_timer(struct interface *ifn)
 438 {
 439
 440   /*
 441    * Bail if there is already a timer running.
 442    */
 443   if (ifn->buffer_hold_timer) {
 444     return;
 445   }
 446
 447   /*
 448    * This is the first message since the last time this interface has
 449    * been drained. Flush the buffer in second or so.
 450    */
 451   ifn->buffer_hold_timer =
 452     olsr_start_timer(OLSR_BUFFER_HOLD_TIME, OLSR_BUFFER_HOLD_JITTER,
 453                      OLSR_TIMER_ONESHOT, &olsr_expire_buffer_timer, ifn,
 454                      buffer_hold_timer_cookie->ci_id);
 455 }
 456
 457 void
 458 olsr_init_willingness(void)
 459 {
 460   /* Some cookies for stats keeping */
 461   static struct olsr_cookie_info *willingness_timer_cookie = NULL;
 462
 463   if (olsr_cnf->willingness_auto) {
 464
 465     /* Run it first and then periodic. */
 466     olsr_update_willingness(NULL);
 467
 468     willingness_timer_cookie = olsr_alloc_cookie("Update Willingness",
 469                                                  OLSR_COOKIE_TYPE_TIMER);
 470     olsr_start_timer((unsigned int)olsr_cnf->will_int * MSEC_PER_SEC, 5,
 471                      OLSR_TIMER_PERIODIC, &olsr_update_willingness, NULL,
 472                      willingness_timer_cookie->ci_id);
 473   }
 474 }
 475
 476 static void
 477 olsr_update_willingness(void *foo __attribute__((unused)))
 478 {
 479   int tmp_will = olsr_cnf->willingness;
 480
 481   /* Re-calculate willingness */
 482   olsr_cnf->willingness = olsr_calculate_willingness();
 483
 484   if(tmp_will != olsr_cnf->willingness)
 485     {
 486       OLSR_PRINTF(1, "Local willingness updated: old %d new %d\n", tmp_will, olsr_cnf->willingness);
 487     }
 488 }
 489
 490
 491 /**
 492  *Calculate this nodes willingness to act as a MPR
 493  *based on either a fixed value or the power status
 494  *of the node using APM
 495  *
 496  *@return a 8bit value from 0-7 representing the willingness
 497  */
 498
 499 uint8_t
 500 olsr_calculate_willingness(void)
 501 {
 502   struct olsr_apm_info ainfo;
 503
 504   /* If fixed willingness */
 505   if(!olsr_cnf->willingness_auto)
 506     return olsr_cnf->willingness;
 507
 508   if(apm_read(&ainfo) < 1)
 509     return WILL_DEFAULT;
 510
 511   apm_printinfo(&ainfo);
 512
 513   /* If AC powered */
 514   if(ainfo.ac_line_status == OLSR_AC_POWERED)
 515     return 6;
 516
 517   /* If battery powered
 518    *
 519    * juice > 78% will: 3
 520    * 78% > juice > 26% will: 2
 521    * 26% > juice will: 1
 522    */
 523   return (ainfo.battery_percentage / 26);
 524 }
 525
 526 const char *
 527 olsr_msgtype_to_string(uint8_t msgtype)
 528 {
 529   static char type[20];
 530
 531   switch(msgtype)
 532     {
 533     case(HELLO_MESSAGE):
 534       return "HELLO";
 535     case(TC_MESSAGE):
 536       return "TC";
 537     case(MID_MESSAGE):
 538       return "MID";
 539     case(HNA_MESSAGE):
 540       return "HNA";
 541     case(LQ_HELLO_MESSAGE):
 542       return("LQ-HELLO");
 543     case(LQ_TC_MESSAGE):
 544       return("LQ-TC");
 545     default:
 546       break;
 547     }
 548
 549   snprintf(type, sizeof(type), "UNKNOWN(%d)", msgtype);
 550   return type;
 551 }
 552
 553
 554 const char *
 555 olsr_link_to_string(uint8_t linktype)
 556 {
 557   static char type[20];
 558
 559   switch(linktype)
 560     {
 561     case(UNSPEC_LINK):
 562       return "UNSPEC";
 563     case(ASYM_LINK):
 564       return "ASYM";
 565     case(SYM_LINK):
 566       return "SYM";
 567     case(LOST_LINK):
 568       return "LOST";
 569     case(HIDE_LINK):
 570       return "HIDE";
 571     default:
 572       break;
 573     }
 574
 575   snprintf(type, sizeof(type), "UNKNOWN(%d)", linktype);
 576   return type;
 577 }
 578
 579
 580 const char *
 581 olsr_status_to_string(uint8_t status)
 582 {
 583   static char type[20];
 584
 585   switch(status)
 586     {
 587     case(NOT_NEIGH):
 588       return "NOT NEIGH";
 589     case(SYM_NEIGH):
 590       return "NEIGHBOR";
 591     case(MPR_NEIGH):
 592       return "MPR";
 593     default:
 594       break;
 595     }
 596
 597   snprintf(type, sizeof(type), "UNKNOWN(%d)", status);
 598   return type;
 599 }
 600
 601
 602 /**
 603  *Termination function to be called whenever a error occures
 604  *that requires the daemon to terminate
 605  *
 606  *@param val the exit code for OLSR
 607  */
 608
 609 void
 610 olsr_exit(int val)
 611 {
 612   fflush(stdout);
 613   olsr_cnf->exit_value = val;
 614   if (app_state == STATE_INIT) {
 615     exit(val);
 616   }
 617   app_state = STATE_SHUTDOWN;
 618 }
 619
 620
 621 /**
 622  * Wrapper for malloc(3) that does error-checking
 623  *
 624  * @param size the number of bytes to allocalte
 625  * @param caller a string identifying the caller for
 626  * use in error messaging
 627  *
 628  * @return a void pointer to the memory allocated
 629  */
 630 void *
 631 olsr_malloc(size_t size, const char *id __attribute__((unused)))
 632 {
 633   void *ptr;
 634
 635   /*
 636    * Not all the callers do a proper cleaning of memory.
 637    * Clean it on behalf of those.
 638    */
 639   ptr = calloc(1, size);
 640
 641   if (!ptr) {
 642       OLSR_ERROR(LOG_MAIN, "Out of memory for id '%s': %s\n", id, strerror(errno));
 643       olsr_exit(EXIT_FAILURE);
 644   }
 645
 646 #if 0
 647   /* useful for debugging */
 648   OLSR_PRINTF(1, "MEMORY: alloc %s %p, %u bytes\n",
 649               id, ptr, size);
 650 #endif
 651
 652   return ptr;
 653 }
 654
 655 /*
 656  * Same as strdup but works with olsr_malloc
 657  */
 658 char *
 659 olsr_strdup(const char *s)
 660 {
 661   char *ret = olsr_malloc(1 + strlen(s), "olsr_strdup");
 662   strcpy(ret, s);
 663   return ret;
 664 }
 665
 666 /*
 667  * Same as strndup but works with olsr_malloc
 668  */
 669 char *
 670 olsr_strndup(const char *s, size_t n)
 671 {
 672   size_t len = n < strlen(s) ? n : strlen(s);
 673   char *ret = olsr_malloc(1 + len, "olsr_strndup");
 674   strncpy(ret, s, len);
 675   ret[len] = 0;
 676   return ret;
 677 }
 678
 679 /*
 680  * Local Variables:
 681  * c-basic-offset: 2
 682  * indent-tabs-mode: nil
 683  * End:
 684  */