move avl and list library into src/common
[olsrd.git] / src / olsr.c
index 032fca8..6f638c3 100644 (file)
@@ -1,25 +1,40 @@
 /*
- * OLSR ad-hoc routing table management protocol
- * Copyright (C) 2004 Andreas T√łnnesen (andreto@ifi.uio.no)
+ * The olsr.org Optimized Link-State Routing daemon(olsrd)
+ * Copyright (c) 2004, Andreas T√łnnesen(andreto@olsr.org)
+ * All rights reserved.
  *
- * This file is part of the olsr.org OLSR daemon.
+ * Redistribution and use in source and binary forms, with or without 
+ * modification, are permitted provided that the following conditions 
+ * are met:
  *
- * olsr.org is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
+ * * Redistributions of source code must retain the above copyright 
+ *   notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright 
+ *   notice, this list of conditions and the following disclaimer in 
+ *   the documentation and/or other materials provided with the 
+ *   distribution.
+ * * Neither the name of olsr.org, olsrd nor the names of its 
+ *   contributors may be used to endorse or promote products derived 
+ *   from this software without specific prior written permission.
  *
- * olsr.org is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
+ * POSSIBILITY OF SUCH DAMAGE.
  *
- * You should have received a copy of the GNU General Public License
- * along with olsr.org; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
- * 
- * 
- * $Id: olsr.c,v 1.18 2004/11/07 17:51:20 tlopatic Exp $
+ * Visit http://www.olsr.org for more information.
+ *
+ * If you find this software useful feel free to make a donation
+ * to the project. For more information see the website or contact
+ * the copyright holders.
  *
  */
 
 #include "mpr_selector_set.h"
 #include "mid_set.h"
 #include "mpr.h"
-#if defined USE_LINK_QUALITY
 #include "lq_mpr.h"
 #include "lq_route.h"
-#endif
 #include "scheduler.h"
-#include "generate_msg.h"
 #include "apm.h"
+#include "misc.h"
+#include "neighbor_table.h"
+#include "log.h"
+#include "lq_packet.h"
+#include "common/avl.h"
+#include "net_olsr.h"
 
 #include <stdarg.h>
 #include <signal.h>
 
 
-/**
- *Checks if a timer has timed out.
- */
-
+olsr_bool changes_topology;
+olsr_bool changes_neighborhood;
+olsr_bool changes_hna;
+olsr_bool changes_force;
 
 /**
- *Initiates a "timer", wich is a timeval structure,
- *with the value given in time_value.
- *@param time_value the value to initialize the timer with
- *@param hold_timer the timer itself
- *@return nada
+ * Process changes functions
  */
-inline void
-olsr_init_timer(olsr_u32_t time_value, struct timeval *hold_timer)
-{ 
-  olsr_u16_t  time_value_sec;
-  olsr_u16_t  time_value_msec;
-
-  time_value_sec = time_value/1000;
-  time_value_msec = time_value-(time_value_sec*1000);
-
-  hold_timer->tv_sec = time_value_sec;
-  hold_timer->tv_usec = time_value_msec*1000;   
-}
 
+struct pcf
+{
+  int (*function)(int, int, int);
+  struct pcf *next;
+};
 
+static struct pcf *pcf_list;
 
-
-
-/**
- *Generaties a timestamp a certain number of milliseconds
- *into the future.
- *
- *@param time_value how many milliseconds from now
- *@param hold_timer the timer itself
- *@return nada
- */
-inline void
-olsr_get_timestamp(olsr_u32_t delay, struct timeval *hold_timer)
-{ 
-  hold_timer->tv_sec = now.tv_sec + delay / 1000;
-  hold_timer->tv_usec = now.tv_usec + (delay % 1000) * 1000;
-  
-  if (hold_timer->tv_usec > 1000000)
-    {
-      hold_timer->tv_sec++;
-      hold_timer->tv_usec -= 1000000;
-    }
-}
-
-
+static olsr_u16_t message_seqno;
 
 /**
  *Initialize the message sequence number as a random value
  */
 void
-init_msg_seqno()
+init_msg_seqno(void)
 {
   message_seqno = random() & 0xFFFF;
 }
@@ -114,8 +99,8 @@ init_msg_seqno()
  *
  *@return the seqno
  */
-inline olsr_u16_t
-get_msg_seqno()
+olsr_u16_t
+get_msg_seqno(void)
 {
   return message_seqno++;
 }
@@ -126,7 +111,7 @@ register_pcf(int (*f)(int, int, int))
 {
   struct pcf *new_pcf;
 
-  olsr_printf(1, "Registering pcf function\n");
+  OLSR_PRINTF(1, "Registering pcf function\n");
 
   new_pcf = olsr_malloc(sizeof(struct pcf), "New PCF");
 
@@ -144,64 +129,73 @@ register_pcf(int (*f)(int, int, int))
  *update the routing table.
  *@return 0
  */
-inline void
-olsr_process_changes()
+void
+olsr_process_changes(void)
 {
-
   struct pcf *tmp_pc_list;
 
 #ifdef DEBUG
   if(changes_neighborhood)
-    olsr_printf(3, "CHANGES IN NEIGHBORHOOD\n");
+    OLSR_PRINTF(3, "CHANGES IN NEIGHBORHOOD\n");
   if(changes_topology)
-    olsr_printf(3, "CHANGES IN TOPOLOGY\n");
+    OLSR_PRINTF(3, "CHANGES IN TOPOLOGY\n");
   if(changes_hna)
-    olsr_printf(3, "CHANGES IN HNA\n");  
+    OLSR_PRINTF(3, "CHANGES IN HNA\n");
 #endif
-
+  
+  if(!changes_force &&
+     2 <= olsr_cnf->lq_level &&
+     0 >= olsr_cnf->lq_dlimit)
+    return;
+    
   if(!changes_neighborhood &&
      !changes_topology &&
      !changes_hna)
     return;
 
-  if(changes_neighborhood)
-    {
-      /* Calculate new mprs, HNA and routing table */
-#if !defined USE_LINK_QUALITY
+  if (olsr_cnf->debug_level > 0 && olsr_cnf->clear_screen && isatty(1))
+  {
+      clear_console();
+      printf("       *** %s (%s on %s) ***\n", olsrd_version, build_date, build_host);
+  }
+
+  if (changes_neighborhood) {
+    if (olsr_cnf->lq_level < 1) {
       olsr_calculate_mpr();
-      olsr_calculate_routing_table();
-#else
+    } else {
       olsr_calculate_lq_mpr();
-      olsr_calculate_lq_routing_table();
-#endif
-      olsr_calculate_hna_routes();
-
-      goto process_pcf;  
     }
+  }
+
+  /* calculate the routing table */
+  if (changes_neighborhood || changes_topology || changes_hna) {
+    olsr_calculate_routing_table(NULL);
+  }
   
-  if(changes_topology)
-    {
-      /* calculate the routing table and HNA */
-#if !defined USE_LINK_QUALITY
-      olsr_calculate_routing_table();
-#else
-      olsr_calculate_lq_routing_table();
+  if (olsr_cnf->debug_level > 0)
+    {      
+      if (olsr_cnf->debug_level > 2) 
+        {
+          olsr_print_mid_set();
+         
+          if (olsr_cnf->debug_level > 3)
+            {
+             if (olsr_cnf->debug_level > 8)
+               {
+                 olsr_print_duplicate_table();
+               }
+              olsr_print_hna_set();
+            }
+        }
+
+#if 1     
+      olsr_print_link_set();
+      olsr_print_neighbor_table();
+      olsr_print_two_hop_neighbor_table();
+      olsr_print_tc_table();
 #endif
-      olsr_calculate_hna_routes();
-
-      goto process_pcf;  
     }
 
-  if(changes_hna)
-    {
-      /* Update HNA routes */
-      olsr_calculate_hna_routes();
-
-      goto process_pcf;
-    }
-  
- process_pcf:
-
   for(tmp_pc_list = pcf_list; 
       tmp_pc_list != NULL;
       tmp_pc_list = tmp_pc_list->next)
@@ -214,9 +208,7 @@ olsr_process_changes()
   changes_neighborhood = OLSR_FALSE;
   changes_topology = OLSR_FALSE;
   changes_hna = OLSR_FALSE;
-
-
-  return;
+  changes_force = OLSR_FALSE;
 }
 
 
@@ -229,18 +221,26 @@ olsr_process_changes()
  *Also initalizes other variables
  */
 void
-olsr_init_tables()
-{
-  
+olsr_init_tables(void)
+{  
   changes_topology = OLSR_FALSE;
   changes_neighborhood = OLSR_FALSE;
   changes_hna = OLSR_FALSE;
 
+  /* Set avl tree comparator */
+  if (olsr_cnf->ipsize == 4) {
+    avl_comp_default = NULL;
+    avl_comp_prefix_default = avl_comp_ipv4_prefix;
+  } else {
+    avl_comp_default = avl_comp_ipv6;
+    avl_comp_prefix_default = avl_comp_ipv6_prefix;
+  }
+
   /* Initialize link set */
   olsr_init_link_set();
 
   /* Initialize duplicate table */
-  olsr_init_duplicate_table();
+  olsr_init_duplicate_set();
 
   /* Initialize neighbor table */
   olsr_init_neighbor_table();
@@ -251,9 +251,6 @@ olsr_init_tables()
   /* Initialize two hop table */
   olsr_init_two_hop_table();
 
-  /* Initialize old route table */
-  olsr_init_old_table();
-
   /* Initialize topology */
   olsr_init_tc();
 
@@ -264,18 +261,15 @@ olsr_init_tables()
   olsr_init_mid_set();
 
   /* Initialize HNA set */
-  olsr_init_hna_set();
+  olsr_init_hna_set();  
 
-  /* Initialize ProcessChanges list */
-  ptf_list = NULL;
-  
+  /* Start periodic SPF and RIB recalculation */
+  if (olsr_cnf->lq_dinter > 0.0) {
+    olsr_start_timer((unsigned int)(olsr_cnf->lq_dinter * MSEC_PER_SEC), 5,
+                     OLSR_TIMER_PERIODIC, &olsr_calculate_routing_table, NULL, 0);
+  }
 }
 
-
-
-
-
-
 /**
  *Check if a message is to be forwarded and forward
  *it if necessary.
@@ -288,9 +282,6 @@ olsr_init_tables()
  */
 int
 olsr_forward_message(union olsr_message *m, 
-                    union olsr_ip_addr *originator, 
-                    olsr_u16_t seqno,
-                    struct interface *in_if, 
                     union olsr_ip_addr *from_addr)
 {
   union olsr_ip_addr *src;
@@ -298,40 +289,44 @@ olsr_forward_message(union olsr_message *m,
   int msgsize;
   struct interface *ifn;
 
-
-  if(!olsr_check_dup_table_fwd(originator, seqno, &in_if->ip_addr))
-    {
-#ifdef DEBUG
-      olsr_printf(3, "Message already forwarded!\n");
-#endif
-      return 0;
-    }
+  /*
+   * Sven-Ola: We should not flood the mesh with overdue messages. Because
+   * of a bug in parser.c:parse_packet, we have a lot of messages because
+   * all older olsrd's have lq_fish enabled.
+   */
+  if (AF_INET == olsr_cnf->ip_version)
+  {
+    if (2 > m->v4.ttl || 255 < (int)m->v4.hopcnt + (int)m->v4.ttl) return 0;
+  }
+  else
+  {
+    if (2 > m->v6.ttl || 255 < (int)m->v6.hopcnt + (int)m->v6.ttl) return 0;
+  }
 
   /* Lookup sender address */
-  if(!(src = mid_lookup_main_addr(from_addr)))
+  src = mid_lookup_main_addr(from_addr);
+  if(!src)
     src = from_addr;
 
-
-  if(NULL == (neighbor=olsr_lookup_neighbor_table(src)))
+  neighbor=olsr_lookup_neighbor_table(src);
+  if(!neighbor)
     return 0;
 
   if(neighbor->status != SYM)
     return 0;
 
-  /* Update duplicate table interface */
-  olsr_update_dup_entry(originator, seqno, &in_if->ip_addr);
-
-  
   /* Check MPR */
   if(olsr_lookup_mprs_set(src) == NULL)
     {
 #ifdef DEBUG
-      olsr_printf(5, "Forward - sender %s not MPR selector\n", olsr_ip_to_string(src));
+#ifndef NODEBUG
+      struct ipaddr_str buf;
+#endif
+      OLSR_PRINTF(5, "Forward - sender %s not MPR selector\n", olsr_ip_to_string(&buf, src));
 #endif
       return 0;
     }
 
-
   /* Treat TTL hopcnt */
   if(olsr_cnf->ip_version == AF_INET)
     {
@@ -346,14 +341,7 @@ olsr_forward_message(union olsr_message *m,
       m->v6.ttl--; 
     }
 
-
-
-  /* Update dup forwarded */
-  olsr_set_dup_forward(originator, seqno);
-
   /* Update packet data */
-
-
   msgsize = ntohs(m->v4.olsr_msgsize);
 
   /* looping trough interfaces */
@@ -364,78 +352,67 @@ olsr_forward_message(union olsr_message *m,
          /*
           * Check if message is to big to be piggybacked
           */
-         if(net_outbuffer_push(ifn, (olsr_u8_t *)m, msgsize) != msgsize)
+         if(net_outbuffer_push(ifn, m, msgsize) != msgsize)
            {
              /* Send */
              net_output(ifn);
              /* Buffer message */
              set_buffer_timer(ifn);
              
-             if(net_outbuffer_push(ifn, (olsr_u8_t *)m, msgsize) != msgsize)
+             if(net_outbuffer_push(ifn, m, msgsize) != msgsize)
                {
-                 olsr_printf(1, "Received message to big to be forwarded in %s(%d bytes)!", ifn->int_name, msgsize);
+                 OLSR_PRINTF(1, "Received message to big to be forwarded in %s(%d bytes)!", ifn->int_name, msgsize);
                  olsr_syslog(OLSR_LOG_ERR, "Received message to big to be forwarded on %s(%d bytes)!", ifn->int_name, msgsize);
                }
-
            }
        }
-      
       else
        {
          /* No forwarding pending */
          set_buffer_timer(ifn);
          
-         if(net_outbuffer_push(ifn, (olsr_u8_t *)m, msgsize) != msgsize)
+         if(net_outbuffer_push(ifn, m, msgsize) != msgsize)
            {
-             olsr_printf(1, "Received message to big to be forwarded in %s(%d bytes)!", ifn->int_name, msgsize);
+             OLSR_PRINTF(1, "Received message to big to be forwarded in %s(%d bytes)!", ifn->int_name, msgsize);
              olsr_syslog(OLSR_LOG_ERR, "Received message to big to be forwarded on %s(%d bytes)!", ifn->int_name, msgsize);
            }
        }
     }
-
   return 1;
-
 }
 
 
 void
 set_buffer_timer(struct interface *ifn)
-{
-  float jitter;
-  struct timeval jittertimer;
-      
+{      
   /* Set timer */
-  jitter = (float) random()/RAND_MAX;
-  jitter *= max_jitter;
-
-  olsr_init_timer((olsr_u32_t) (jitter*1000), &jittertimer);
-
-  timeradd(&now, &jittertimer, &fwdtimer[ifn->if_nr]);
-
+  ifn->fwdtimer = GET_TIMESTAMP(random() * olsr_cnf->max_jitter * 1000 / RAND_MAX);
 }
 
-
-
 void
-olsr_init_willingness()
+olsr_init_willingness(void)
 {
-  if(olsr_cnf->willingness_auto)
-    olsr_register_scheduler_event(&olsr_update_willingness, NULL, will_int, will_int, NULL);
+  if (olsr_cnf->willingness_auto) {
+
+    /* Run it first and then periodic. */
+    olsr_update_willingness(NULL);
+
+    olsr_start_timer((unsigned int)olsr_cnf->will_int * MSEC_PER_SEC, 5,
+                     OLSR_TIMER_PERIODIC, &olsr_update_willingness, NULL, 0);
+  }
 }
 
 void
-olsr_update_willingness(void *foo)
+olsr_update_willingness(void *foo __attribute__((unused)))
 {
-  int tmp_will;
-
-  tmp_will = olsr_cnf->willingness;
+  int tmp_will = olsr_cnf->willingness;
 
   /* Re-calculate willingness */
   olsr_cnf->willingness = olsr_calculate_willingness();
 
   if(tmp_will != olsr_cnf->willingness)
     {
-      olsr_printf(1, "Local willingness updated: old %d new %d\n", tmp_will, olsr_cnf->willingness);
+      OLSR_PRINTF(1, "Local willingness updated: old %d new %d\n", tmp_will, olsr_cnf->willingness);
     }
 }
 
@@ -449,7 +426,7 @@ olsr_update_willingness(void *foo)
  */
 
 olsr_u8_t
-olsr_calculate_willingness()
+olsr_calculate_willingness(void)
 {
   struct olsr_apm_info ainfo;
 
@@ -457,8 +434,6 @@ olsr_calculate_willingness()
   if(!olsr_cnf->willingness_auto)
     return olsr_cnf->willingness;
 
-#warning CHANGES IN THE apm INTERFACE(0.4.8)!
-
   if(apm_read(&ainfo) < 1)
     return WILL_DEFAULT;
 
@@ -477,6 +452,80 @@ olsr_calculate_willingness()
   return (ainfo.battery_percentage / 26);
 }
 
+const char *
+olsr_msgtype_to_string(olsr_u8_t msgtype)
+{
+  static char type[20];
+
+  switch(msgtype)
+    {
+    case(HELLO_MESSAGE):
+      return "HELLO";
+    case(TC_MESSAGE):
+      return "TC";
+    case(MID_MESSAGE):
+      return "MID";
+    case(HNA_MESSAGE):
+      return "HNA";
+    case(LQ_HELLO_MESSAGE):
+      return("LQ-HELLO");
+    case(LQ_TC_MESSAGE):
+      return("LQ-TC");
+    default:
+      break;
+    }
+
+  snprintf(type, sizeof(type), "UNKNOWN(%d)", msgtype);
+  return type;
+}
+
+
+const char *
+olsr_link_to_string(olsr_u8_t linktype)
+{
+  static char type[20];
+
+  switch(linktype)
+    {
+    case(UNSPEC_LINK):
+      return "UNSPEC";
+    case(ASYM_LINK):
+      return "ASYM";
+    case(SYM_LINK):
+      return "SYM";
+    case(LOST_LINK):
+      return "LOST";
+    case(HIDE_LINK):
+      return "HIDE";
+    default:
+      break;
+    }
+
+  snprintf(type, sizeof(type), "UNKNOWN(%d)", linktype);
+  return type;
+}
+
+
+const char *
+olsr_status_to_string(olsr_u8_t status)
+{
+  static char type[20];
+
+  switch(status)
+    {
+    case(NOT_NEIGH):
+      return "NOT NEIGH";
+    case(SYM_NEIGH):
+      return "NEIGHBOR";
+    case(MPR_NEIGH):
+      return "MPR";
+    default:
+      break;
+    }
+
+  snprintf(type, sizeof(type), "UNKNOWN(%d)", status);
+  return type;
+}
 
 
 /**
@@ -489,35 +538,42 @@ olsr_calculate_willingness()
 void
 olsr_exit(const char *msg, int val)
 {
-  olsr_printf(1, "OLSR EXIT: %s\n", msg);
+  OLSR_PRINTF(1, "OLSR EXIT: %s\n", msg);
   olsr_syslog(OLSR_LOG_ERR, "olsrd exit: %s\n", msg);
   fflush(stdout);
-  exit_value = val;
+  olsr_cnf->exit_value = val;
 
   raise(SIGTERM);
 }
 
 
 /**
- *Wrapper for malloc(3) that does error-checking
+ * Wrapper for malloc(3) that does error-checking
  *
- *@param size the number of bytes to allocalte
- *@param caller a string identifying the caller for
- *use in error messaging
+ * @param size the number of bytes to allocalte
+ * @param caller a string identifying the caller for
+ * use in error messaging
  *
- *@return a void pointer to the memory allocated
+ * @return a void pointer to the memory allocated
  */
 void *
 olsr_malloc(size_t size, const char *id)
 {
   void *ptr;
 
-  if((ptr = malloc(size)) == 0) 
-    {
-      olsr_printf(1, "OUT OF MEMORY: %s\n", strerror(errno));
-      olsr_syslog(OLSR_LOG_ERR, "olsrd: out of memory!: %m\n");
-      olsr_exit((char *)id, EXIT_FAILURE);
-    }
+  /*
+   * Not all the callers do a proper cleaning of memory.
+   * Clean it on behalf of those.
+   */
+  ptr = calloc(1, size);
+
+  if (!ptr) {
+      const char * const err_msg = strerror(errno);
+      OLSR_PRINTF(1, "OUT OF MEMORY: %s\n", err_msg);
+      olsr_syslog(OLSR_LOG_ERR, "olsrd: out of memory!: %s\n", err_msg);
+      olsr_exit(id, EXIT_FAILURE);
+  }
+
   return ptr;
 }
 
@@ -528,19 +584,21 @@ olsr_malloc(size_t size, const char *id)
  *
  */
 
-inline int
-olsr_printf(int loglevel, char *format, ...)
+int
+olsr_printf(int loglevel, const char *format, ...)
 {
-  va_list arglist;
-
-  va_start(arglist, format);
-
-  if(loglevel <= olsr_cnf->debug_level)
+  if((loglevel <= olsr_cnf->debug_level) && debug_handle)
     {
-      vprintf(format, arglist);
+      va_list arglist;
+      va_start(arglist, format);
+      vfprintf(debug_handle, format, arglist);
+      va_end(arglist);
     }
-
-  va_end(arglist);
-
   return 0;
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */