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 <assert.h>
  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   /* Start periodic SPF and RIB recalculation */
 237   if (olsr_cnf->lq_dinter > 0) {
 238     periodic_spf_timer_cookie = olsr_alloc_cookie("Periodic SPF", OLSR_COOKIE_TYPE_TIMER);
 239     olsr_start_timer(olsr_cnf->lq_dinter, 5,
 240                      OLSR_TIMER_PERIODIC, &olsr_trigger_forced_update, NULL, periodic_spf_timer_cookie);
 241   }
 242 }
 243
 244 /**
 245  * Shared code to write the message header
 246  */
 247 uint8_t *olsr_put_msg_hdr(uint8_t **curr, struct olsr_message *msg)
 248 {
 249   uint8_t *sizeptr;
 250
 251   assert(msg);
 252   assert(curr);
 253
 254   pkt_put_u8(curr, msg->type);
 255   pkt_put_reltime(curr, msg->vtime);
 256   sizeptr = *curr;
 257   pkt_put_u16(curr, msg->size);
 258   pkt_put_ipaddress(curr, &msg->originator);
 259   pkt_put_u8(curr, msg->ttl);
 260   pkt_put_u8(curr, msg->hopcnt);
 261   pkt_put_u16(curr, msg->seqno);
 262
 263   return sizeptr;
 264 }
 265
 266 /**
 267  *Check if a message is to be forwarded and forward
 268  *it if necessary.
 269  *
 270  *@param m the OLSR message recieved
 271  *
 272  *@returns positive if forwarded
 273  */
 274 int
 275 olsr_forward_message(struct olsr_message *msg, uint8_t *binary, struct interface *in_if, union olsr_ip_addr *from_addr)
 276 {
 277   union olsr_ip_addr *src;
 278   struct nbr_entry *neighbor;
 279   struct interface *ifn;
 280   uint8_t *tmp;
 281 #if !defined REMOVE_LOG_DEBUG
 282   struct ipaddr_str buf;
 283 #endif
 284
 285   /* Lookup sender address */
 286   src = olsr_lookup_main_addr_by_alias(from_addr);
 287   if (!src)
 288     src = from_addr;
 289
 290   neighbor = olsr_lookup_nbr_entry(src, true);
 291   if (!neighbor) {
 292     OLSR_DEBUG(LOG_PACKET_PARSING, "Not forwarding message type %d because no nbr entry found for %s\n",
 293         msg->type, olsr_ip_to_string(&buf, src));
 294     return 0;
 295   }
 296   if (!neighbor->is_sym) {
 297     OLSR_DEBUG(LOG_PACKET_PARSING, "Not forwarding message type %d because received by non-symmetric neighbor %s\n",
 298         msg->type, olsr_ip_to_string(&buf, src));
 299     return 0;
 300   }
 301
 302   /* Check MPR */
 303   if (neighbor->mprs_count == 0) {
 304     OLSR_DEBUG(LOG_PACKET_PARSING, "Not forwarding message type %d because we are no MPR for %s\n",
 305         msg->type, olsr_ip_to_string(&buf, src));
 306     /* don't forward packages if not a MPR */
 307     return 0;
 308   }
 309
 310   /* check if we already forwarded this message */
 311   if (olsr_is_duplicate_message(msg, true, NULL)) {
 312     OLSR_DEBUG(LOG_PACKET_PARSING, "Not forwarding message type %d from %s because we already forwarded it.\n",
 313         msg->type, olsr_ip_to_string(&buf, src));
 314     return 0;                   /* it's a duplicate, forget about it */
 315   }
 316
 317   /* Treat TTL hopcnt */
 318   msg->hopcnt++;
 319   msg->ttl--;
 320   tmp = binary;
 321   olsr_put_msg_hdr(&tmp, msg);
 322
 323   if (msg->ttl == 0) {
 324     OLSR_DEBUG(LOG_PACKET_PARSING, "Not forwarding message type %d from %s because TTL is 0.\n",
 325         msg->type, olsr_ip_to_string(&buf, src));
 326     return 0;                   /* TTL 0, forget about it */
 327   }
 328   OLSR_DEBUG(LOG_PACKET_PARSING, "Forwarding message type %d from %s.\n",
 329       msg->type, olsr_ip_to_string(&buf, src));
 330
 331   /* looping trough interfaces */
 332   OLSR_FOR_ALL_INTERFACES(ifn) {
 333     if (net_output_pending(ifn)) {
 334       /* dont forward to incoming interface if interface is mode ether */
 335       if (in_if->mode == IF_MODE_ETHER && ifn == in_if)
 336         continue;
 337
 338       /*
 339        * Check if message is to big to be piggybacked
 340        */
 341       if (net_outbuffer_push(ifn, binary, msg->size) != msg->size) {
 342         /* Send */
 343         net_output(ifn);
 344         /* Buffer message */
 345         set_buffer_timer(ifn);
 346
 347         if (net_outbuffer_push(ifn, binary, msg->size) != msg->size) {
 348           OLSR_WARN(LOG_NETWORKING, "Received message to big to be forwarded in %s(%d bytes)!", ifn->int_name, msg->size);
 349         }
 350       }
 351     } else {
 352       /* No forwarding pending */
 353       set_buffer_timer(ifn);
 354
 355       if (net_outbuffer_push(ifn, binary, msg->size) != msg->size) {
 356         OLSR_WARN(LOG_NETWORKING, "Received message to big to be forwarded in %s(%d bytes)!", ifn->int_name, msg->size);
 357       }
 358     }
 359   }
 360   OLSR_FOR_ALL_INTERFACES_END(ifn);
 361
 362   return 1;
 363 }
 364
 365 /**
 366  * Wrapper for the timer callback.
 367  */
 368 static void
 369 olsr_expire_buffer_timer(void *context)
 370 {
 371   struct interface *ifn;
 372
 373   ifn = (struct interface *)context;
 374
 375   /*
 376    * Clear the pointer to indicate that this timer has
 377    * been expired and needs to be restarted in case there
 378    * will be another message queued in the future.
 379    */
 380   ifn->buffer_hold_timer = NULL;
 381
 382   /*
 383    * Do we have something to emit ?
 384    */
 385   if (!net_output_pending(ifn)) {
 386     return;
 387   }
 388
 389   OLSR_DEBUG(LOG_NETWORKING, "Buffer Holdtimer for %s timed out, sending data.\n", ifn->int_name);
 390
 391   net_output(ifn);
 392 }
 393
 394 /*
 395  * set_buffer_timer
 396  *
 397  * Kick a hold-down timer which defers building of a message.
 398  * This has the desired effect that olsr messages get bigger.
 399  */
 400 void
 401 set_buffer_timer(struct interface *ifn)
 402 {
 403
 404   /*
 405    * Bail if there is already a timer running.
 406    */
 407   if (ifn->buffer_hold_timer) {
 408     return;
 409   }
 410
 411   /*
 412    * This is the first message since the last time this interface has
 413    * been drained. Flush the buffer in second or so.
 414    */
 415   ifn->buffer_hold_timer =
 416     olsr_start_timer(OLSR_BUFFER_HOLD_TIME, OLSR_BUFFER_HOLD_JITTER,
 417                      OLSR_TIMER_ONESHOT, &olsr_expire_buffer_timer, ifn, buffer_hold_timer_cookie);
 418 }
 419
 420 void
 421 olsr_init_willingness(void)
 422 {
 423   /* Some cookies for stats keeping */
 424   static struct olsr_cookie_info *willingness_timer_cookie = NULL;
 425
 426   if (olsr_cnf->willingness_auto) {
 427     OLSR_INFO(LOG_MAIN, "Initialize automatic willingness...\n");
 428     /* Run it first and then periodic. */
 429     olsr_update_willingness(NULL);
 430
 431     willingness_timer_cookie = olsr_alloc_cookie("Update Willingness", OLSR_COOKIE_TYPE_TIMER);
 432     olsr_start_timer(olsr_cnf->will_int, 5,
 433                      OLSR_TIMER_PERIODIC, &olsr_update_willingness, NULL, willingness_timer_cookie);
 434   }
 435 }
 436
 437 static void
 438 olsr_update_willingness(void *foo __attribute__ ((unused)))
 439 {
 440   int tmp_will = olsr_cnf->willingness;
 441
 442   /* Re-calculate willingness */
 443   olsr_cnf->willingness = olsr_calculate_willingness();
 444
 445   if (tmp_will != olsr_cnf->willingness) {
 446     OLSR_INFO(LOG_MAIN, "Local willingness updated: old %d new %d\n", tmp_will, olsr_cnf->willingness);
 447   }
 448 }
 449
 450
 451 /**
 452  *Calculate this nodes willingness to act as a MPR
 453  *based on either a fixed value or the power status
 454  *of the node using APM
 455  *
 456  *@return a 8bit value from 0-7 representing the willingness
 457  */
 458
 459 uint8_t
 460 olsr_calculate_willingness(void)
 461 {
 462   struct olsr_apm_info ainfo;
 463
 464   /* If fixed willingness */
 465   if (!olsr_cnf->willingness_auto)
 466     return olsr_cnf->willingness;
 467
 468   if (apm_read(&ainfo) < 1)
 469     return WILL_DEFAULT;
 470
 471   apm_printinfo(&ainfo);
 472
 473   /* If AC powered */
 474   if (ainfo.ac_line_status == OLSR_AC_POWERED)
 475     return 6;
 476
 477   /* If battery powered
 478    *
 479    * juice > 78% will: 3
 480    * 78% > juice > 26% will: 2
 481    * 26% > juice will: 1
 482    */
 483   return (ainfo.battery_percentage / 26);
 484 }
 485
 486 const char *
 487 olsr_msgtype_to_string(uint8_t msgtype)
 488 {
 489   static char type[20];
 490
 491   switch (msgtype) {
 492   case (HELLO_MESSAGE):
 493     return "HELLO";
 494   case (TC_MESSAGE):
 495     return "TC";
 496   case (MID_MESSAGE):
 497     return "MID";
 498   case (HNA_MESSAGE):
 499     return "HNA";
 500   case (LQ_HELLO_MESSAGE):
 501     return ("LQ-HELLO");
 502   case (LQ_TC_MESSAGE):
 503     return ("LQ-TC");
 504   default:
 505     break;
 506   }
 507
 508   snprintf(type, sizeof(type), "UNKNOWN(%d)", msgtype);
 509   return type;
 510 }
 511
 512
 513 const char *
 514 olsr_link_to_string(uint8_t linktype)
 515 {
 516   static char type[20];
 517
 518   switch (linktype) {
 519   case (UNSPEC_LINK):
 520     return "UNSPEC";
 521   case (ASYM_LINK):
 522     return "ASYM";
 523   case (SYM_LINK):
 524     return "SYM";
 525   case (LOST_LINK):
 526     return "LOST";
 527   default:
 528     break;
 529   }
 530
 531   snprintf(type, sizeof(type), "UNKNOWN(%d)", linktype);
 532   return type;
 533 }
 534
 535
 536 const char *
 537 olsr_status_to_string(uint8_t status)
 538 {
 539   static char type[20];
 540
 541   switch (status) {
 542   case (NOT_NEIGH):
 543     return "NOT NEIGH";
 544   case (SYM_NEIGH):
 545     return "NEIGHBOR";
 546   case (MPR_NEIGH):
 547     return "MPR";
 548   default:
 549     break;
 550   }
 551
 552   snprintf(type, sizeof(type), "UNKNOWN(%d)", status);
 553   return type;
 554 }
 555
 556
 557 /**
 558  *Termination function to be called whenever a error occures
 559  *that requires the daemon to terminate
 560  *
 561  *@param val the exit code for OLSR
 562  */
 563
 564 void
 565 olsr_exit(int val)
 566 {
 567   fflush(stdout);
 568   olsr_cnf->exit_value = val;
 569   if (app_state == STATE_INIT) {
 570     exit(val);
 571   }
 572   app_state = STATE_SHUTDOWN;
 573 }
 574
 575
 576 /**
 577  * Wrapper for malloc(3) that does error-checking
 578  *
 579  * @param size the number of bytes to allocalte
 580  * @param caller a string identifying the caller for
 581  * use in error messaging
 582  *
 583  * @return a void pointer to the memory allocated
 584  */
 585 void *
 586 olsr_malloc(size_t size, const char *id __attribute__ ((unused)))
 587 {
 588   void *ptr;
 589
 590   /*
 591    * Not all the callers do a proper cleaning of memory.
 592    * Clean it on behalf of those.
 593    */
 594   ptr = calloc(1, size);
 595
 596   if (!ptr) {
 597     OLSR_ERROR(LOG_MAIN, "Out of memory for id '%s': %s\n", id, strerror(errno));
 598     olsr_exit(EXIT_FAILURE);
 599   }
 600   return ptr;
 601 }
 602
 603 /*
 604  * Same as strdup but works with olsr_malloc
 605  */
 606 char *
 607 olsr_strdup(const char *s)
 608 {
 609   char *ret = olsr_malloc(1 + strlen(s), "olsr_strdup");
 610   strcpy(ret, s);
 611   return ret;
 612 }
 613
 614 /*
 615  * Same as strndup but works with olsr_malloc
 616  */
 617 char *
 618 olsr_strndup(const char *s, size_t n)
 619 {
 620   size_t len = n < strlen(s) ? n : strlen(s);
 621   char *ret = olsr_malloc(1 + len, "olsr_strndup");
 622   strncpy(ret, s, len);
 623   ret[len] = 0;
 624   return ret;
 625 }
 626
 627 /*
 628  * Local Variables:
 629  * c-basic-offset: 2
 630  * indent-tabs-mode: nil
 631  * End:
 632  */