Major Changes:
[olsrd.git] / src / tc_set.c
index e6efa45..0d0ba4e 100644 (file)
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: tc_set.c,v 1.33 2007/11/02 09:38:55 bernd67 Exp $
+ * $Id: tc_set.c,v 1.38 2007/11/29 00:49:39 bernd67 Exp $
  */
 
 #include "tc_set.h"
+#include "ipcalc.h"
+#include "mid_set.h"
+#include "link_set.h"
 #include "olsr.h"
 #include "scheduler.h"
 #include "lq_route.h"
 #include "lq_avl.h"
-#include "assert.h"
+#include "lq_packet.h"
+#include "net_olsr.h"
+
+#include <assert.h>
 
 /* Root of the link state database */
 struct avl_tree tc_tree;
@@ -55,7 +61,7 @@ struct tc_entry *tc_myself; /* Shortcut to ourselves */
  * Initialize the topology set
  *
  */
-int
+void
 olsr_init_tc(void)
 {
   OLSR_PRINTF(5, "TC: init topo\n");
@@ -68,7 +74,6 @@ olsr_init_tc(void)
    * Add a TC entry for ourselves.
    */
   tc_myself = olsr_add_tc_entry(&olsr_cnf->main_addr);
-  return 1;
 }
 
 /**
@@ -81,11 +86,10 @@ olsr_change_myself_tc(void)
   struct tc_edge_entry *tc_edge;
 
   if (tc_myself) {
-
     /*
      * Check if there was a change.
      */
-    if (COMP_IP(&tc_myself->addr, &olsr_cnf->main_addr)) {
+    if (ipequal(&tc_myself->addr, &olsr_cnf->main_addr)) {
       return;
     }
 
@@ -114,9 +118,9 @@ olsr_change_myself_tc(void)
 void
 olsr_delete_tc_entry(struct tc_entry *tc)
 {
-
 #if 0
-  OLSR_PRINTF(1, "TC: del entry %s\n", olsr_ip_to_string(&tc->addr));
+  struct ipaddr_str buf;
+  OLSR_PRINTF(1, "TC: del entry %s\n", olsr_ip_to_string(%buf, &tc->addr));
 #endif
 
   /* The edgetree must be empty before */
@@ -159,9 +163,7 @@ olsr_lookup_tc_entry(union olsr_ip_addr *adr)
 struct tc_entry *
 olsr_getnext_tc_entry(struct tc_entry *tc)
 {
-  struct avl_node *node;
-
-  node = avl_walk_next(&tc->vertex_node);
+  struct avl_node *node = avl_walk_next(&tc->vertex_node);
 
   if (node) {
     return node->data;
@@ -180,9 +182,9 @@ struct tc_entry *
 olsr_add_tc_entry(union olsr_ip_addr *adr)
 {
   struct tc_entry *tc;
-
 #if 0
-  OLSR_PRINTF(1, "TC: add entry %s\n", olsr_ip_to_string(adr));
+  struct ipaddr_str buf;
+  OLSR_PRINTF(1, "TC: add entry %s\n", olsr_ip_to_string(&buf, adr));
 #endif
 
   tc = olsr_malloc(sizeof(struct tc_entry), "add TC entry");
@@ -192,7 +194,8 @@ olsr_add_tc_entry(union olsr_ip_addr *adr)
   memset(tc, 0, sizeof(struct tc_entry));
 
   /* Fill entry */
-  COPY_IP(&tc->addr, adr);
+  //COPY_IP(&tc->addr, adr);
+  tc->addr = *adr;
   tc->vertex_node.data = tc;
   tc->vertex_node.key = &tc->addr;
 
@@ -215,20 +218,19 @@ olsr_add_tc_entry(union olsr_ip_addr *adr)
 char *
 olsr_tc_edge_to_string(struct tc_edge_entry *tc_edge)
 {
-  struct tc_entry *tc;
-  static char buff[128];
-
-  tc = tc_edge->tc;
+  static char buf[128];
+  struct ipaddr_str addrbuf, dstbuf;
+  struct tc_entry *tc = tc_edge->tc;
 
-  snprintf(buff, sizeof(buff),
+  snprintf(buf, sizeof(buf),
            "%s > %s, lq %.3f, inv-lq %.3f, etx %.3f",
-           olsr_ip_to_string(&tc->addr),
-           olsr_ip_to_string(&tc_edge->T_dest_addr),
+           olsr_ip_to_string(&addrbuf, &tc->addr),
+           olsr_ip_to_string(&dstbuf, &tc_edge->T_dest_addr),
            tc_edge->link_quality,
            tc_edge->inverse_link_quality,
            tc_edge->etx);
 
-  return buff;
+  return buf;
 }
 
 /**
@@ -252,12 +254,11 @@ olsr_set_tc_edge_timer(struct tc_edge_entry *tc_edge, unsigned int timer)
 void
 olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *tc_edge)
 {
-  if (tc_edge->link_quality >= MIN_LINK_QUALITY &&
-      tc_edge->inverse_link_quality >= MIN_LINK_QUALITY) {
-        
-    tc_edge->etx = 1.0 / (tc_edge->link_quality * tc_edge->inverse_link_quality);
-  } else {
+  if (tc_edge->link_quality < MIN_LINK_QUALITY &&
+      tc_edge->inverse_link_quality < MIN_LINK_QUALITY) {
     tc_edge->etx = INFINITE_ETX;
+  } else {
+    tc_edge->etx = 1.0 / (tc_edge->link_quality * tc_edge->inverse_link_quality);
   }
 }
 
@@ -282,17 +283,15 @@ olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr,
   memset(tc_edge, 0, sizeof(struct tc_edge_entry));
 
   /* Fill entry */
-  COPY_IP(&tc_edge->T_dest_addr, addr);
+  tc_edge->T_dest_addr = *addr;
   olsr_set_tc_edge_timer(tc_edge, vtime*1000);
   tc_edge->T_seq = ansn;
   tc_edge->edge_node.data = tc_edge;
   tc_edge->edge_node.key = &tc_edge->T_dest_addr;
 
   if (olsr_cnf->lq_level > 0) {
-
     tc_edge->link_quality = neigh_link_quality;
     tc_edge->inverse_link_quality = link_quality;
-
   } else {
 
     /*
@@ -323,7 +322,6 @@ olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr,
    */
   tc_neighbor = olsr_lookup_tc_entry(&tc_edge->T_dest_addr);
   if (tc_neighbor) {
-
 #if 0
     OLSR_PRINTF(1, "TC:   found neighbor tc_entry %s\n",
                 olsr_ip_to_string(&tc_neighbor->addr));
@@ -331,7 +329,6 @@ olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr,
 
     tc_edge_inv = olsr_lookup_tc_edge(tc_neighbor, &tc->addr);
     if (tc_edge_inv) {
-
 #if 0
       OLSR_PRINTF(1, "TC:   found inverse edge for %s\n",
                   olsr_ip_to_string(&tc_edge_inv->T_dest_addr));
@@ -400,29 +397,24 @@ olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
 
 
 /**
- * Delete all destinations that have a
- * lower ANSN than the one in the message
+ * Delete all destinations that have a lower ANSN.
  *
  * @param tc the entry to delete edges from
- * @param msg the message to fetch the ANSN from
+ * @param ansn the advertised neighbor set sequence number
  * @return 1 if any destinations were deleted 0 if not
  */
-int
-olsr_tc_delete_mprs(struct tc_entry *tc, struct tc_message *msg)
+static int
+olsr_delete_outdated_tc_edges(struct tc_entry *tc, olsr_u16_t ansn)
 {
   struct tc_edge_entry *tc_edge;
-  int retval;
+  int retval = 0;
 
 #if 0
   OLSR_PRINTF(5, "TC: deleting MPRS\n");
 #endif
 
-  retval = 0;
-
   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
-
-    if (SEQNO_GREATER_THAN(msg->ansn, tc_edge->T_seq)) {
-
+    if (SEQNO_GREATER_THAN(ansn, tc_edge->T_seq)) {
       /*
        * Do not delete the edge now, just mark the edge as down.
        * Downed edges will be ignored by the SPF computation.
@@ -465,93 +457,102 @@ olsr_etx_significant_change(float etx1, float etx2)
 }
 
 /**
- * Update the destinations registered on an entry.
- * Creates new dest-entries if not registered.
- * Bases update on a receivied TC message
+ * Update an edge registered on an entry.
+ * Creates new edge-entries if not registered.
+ * Bases update on a received TC message
  *
  * @param entry the TC entry to check
- * @msg the TC message to update by
+ * @pkt the TC edge entry in the packet
  * @return 1 if entries are added 0 if not
  */
-int
-olsr_tc_update_mprs(struct tc_entry *tc, struct tc_message *msg)
+static int
+olsr_tc_update_edge(struct tc_entry *tc, unsigned int vtime_s, olsr_u16_t ansn,
+                    olsr_u8_t type, const unsigned char **curr)
 {
-  struct tc_mpr_addr *mprs;
   struct tc_edge_entry *tc_edge;
+  double link_quality, neigh_link_quality;
+  union olsr_ip_addr neighbor;
   int edge_change;
 
-#if 0
-  OLSR_PRINTF(1, "TC: update MPRS\n");
-#endif
-
   edge_change = 0;
 
-  mprs = msg->multipoint_relay_selector_address;
-  
-  /* Add all the MPRs */
+  /*
+   * Fetch the per-edge data
+   * LQ messages also contain LQ data.
+   */
+  pkt_get_ipaddress(curr, &neighbor);
 
-  while (mprs) {
+  if (type == LQ_TC_MESSAGE) {
+    pkt_get_lq(curr, &link_quality);
+    pkt_get_lq(curr, &neigh_link_quality);
+    pkt_ignore_u16(curr);
+  } else {
+    link_quality = 1.0;
+    neigh_link_quality = 1.0;
+  }
 
-    /* First check if we know this edge */
-    tc_edge = olsr_lookup_tc_edge(tc, &mprs->address);
+  /* First check if we know this edge */
+  tc_edge = olsr_lookup_tc_edge(tc, &neighbor);
 
-    if(!tc_edge) {
+  if(!tc_edge) {
       
-      /*
-       * Yet unknown - create it.
-       */
-      olsr_add_tc_edge_entry(tc, &mprs->address, msg->ansn,
-                             (unsigned int )msg->vtime,
-                             mprs->link_quality, mprs->neigh_link_quality);
-      edge_change = 1;
+    /*
+     * Yet unknown - create it.
+     * Check if the address is allowed.
+     */
+    if (!olsr_validate_address(&neighbor)) {
+      return 0;
+    }
 
-    } else {
+    olsr_add_tc_edge_entry(tc, &neighbor, ansn, vtime_s,
+                           link_quality, neigh_link_quality);
+    edge_change = 1;
 
-      /*
-       * We know this edge - Update entry.
-       */
-      olsr_set_tc_edge_timer(tc_edge, msg->vtime*1000);
-      tc_edge->T_seq = msg->ansn;
+  } else {
 
-      /*
-       * Clear the (possibly set) down flag.
-       */
-      tc_edge->flags &= ~OLSR_TC_EDGE_DOWN;
+    /*
+     * We know this edge - Update entry.
+     */
+    olsr_set_tc_edge_timer(tc_edge, vtime_s*1000);
+    tc_edge->T_seq = ansn;
 
-      /*
-       * Determine if the etx change is meaningful enough
-       * in order to trigger a SPF calculation.
-       */
-      if (olsr_etx_significant_change(tc_edge->link_quality,
-                                      mprs->neigh_link_quality)) {
+    /*
+     * Clear the (possibly set) down flag.
+     */
+    tc_edge->flags &= ~OLSR_TC_EDGE_DOWN;
 
-        if (msg->hop_count <= olsr_cnf->lq_dlimit)
-          edge_change = 1;
-      }
-      tc_edge->link_quality = mprs->neigh_link_quality;
+    /*
+     * Determine if the etx change is meaningful enough
+     * in order to trigger a SPF calculation.
+     */
+    if (olsr_etx_significant_change(tc_edge->link_quality,
+                                    neigh_link_quality)) {
 
-      if (olsr_etx_significant_change(tc_edge->inverse_link_quality,
-                                      mprs->link_quality)) {
+      if (tc->msg_hops <= olsr_cnf->lq_dlimit)
+        edge_change = 1;
+    }
+    tc_edge->link_quality = neigh_link_quality;
 
-        if (msg->hop_count <= olsr_cnf->lq_dlimit)
-          edge_change = 1;
-      }
-      tc_edge->inverse_link_quality = mprs->link_quality;
+    if (olsr_etx_significant_change(tc_edge->inverse_link_quality,
+                                    link_quality)) {
 
-      /*
-       * Update the etx.
-       */
-      olsr_calc_tc_edge_entry_etx(tc_edge);
+      if (tc->msg_hops <= olsr_cnf->lq_dlimit)
+        edge_change = 1;
+    }
+    tc_edge->inverse_link_quality = link_quality;
+
+    /*
+     * Update the etx.
+     */
+    olsr_calc_tc_edge_entry_etx(tc_edge);
 
 #if 0
-      if (edge_change) {          
-        OLSR_PRINTF(1, "TC:   chg edge entry %s\n",
-                    olsr_tc_edge_to_string(tc_edge));
-      }
+    if (edge_change) {          
+      OLSR_PRINTF(1, "TC:   chg edge entry %s\n",
+                  olsr_tc_edge_to_string(tc_edge));
+    }
 #endif
 
-    }
-    mprs = mprs->next;
   }
 
   return edge_change;
@@ -591,68 +592,188 @@ void
 olsr_time_out_tc_set(void)
 {
   struct tc_entry *tc;
-  struct tc_edge_entry *tc_edge;
 
-  OLSR_FOR_ALL_TC_ENTRIES(tc)
+  OLSR_FOR_ALL_TC_ENTRIES(tc) {
+    struct tc_edge_entry *tc_edge;
     OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
-
-    /*
-     * Delete outdated edges.
-     */
-    if(TIMED_OUT(tc_edge->T_time)) {
-      olsr_delete_tc_edge_entry(tc_edge);
-      changes_topology = OLSR_TRUE;
-    }
-  } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
-  OLSR_FOR_ALL_TC_ENTRIES_END(tc)
+      /*
+       * Delete outdated edges.
+       */
+      if(TIMED_OUT(tc_edge->T_time)) {
+        olsr_delete_tc_edge_entry(tc_edge);
+        changes_topology = OLSR_TRUE;
+      }
+    } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
+  } OLSR_FOR_ALL_TC_ENTRIES_END(tc)
 }
 
 /**
  * Print the topology table to stdout
  */
-int
+void
 olsr_print_tc_table(void)
 {
+#ifndef NODEBUG
+  /* The whole function makes no sense without it. */
   struct tc_entry *tc;
-  struct tc_edge_entry *tc_edge;
-  char *fstr;
-  float etx;
-  
-  OLSR_PRINTF(1, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- TOPOLOGY\n\n",
-              nowtm->tm_hour,
-              nowtm->tm_min,
-              nowtm->tm_sec,
-              (int)now.tv_usec / 10000);
-
-  if (olsr_cnf->ip_version == AF_INET)
-    {
-      OLSR_PRINTF(1, "Source IP addr   Dest IP addr     LQ     ILQ    ETX\n");
-      fstr = "%-15s  %-15s  %5.3f  %5.3f  %.2f\n";
-    }
-  else
-    {
-      OLSR_PRINTF(1, "Source IP addr                Dest IP addr                    LQ     ILQ    ETX\n");
-      fstr = "%-30s%-30s  %5.3f  %5.3f  %.2f\n";
-    }
+  const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
+
+  OLSR_PRINTF(1,
+              "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- TOPOLOGY\n\n"
+              "%-*s %-*s %-5s  %-5s  %s\n",
+              nowtm->tm_hour, nowtm->tm_min, nowtm->tm_sec, (int)now.tv_usec / 10000,
+              ipwidth, "Source IP addr", ipwidth, "Dest IP addr", "LQ", "ILQ", "ETX");
 
   OLSR_FOR_ALL_TC_ENTRIES(tc) {
+    struct tc_edge_entry *tc_edge;
     OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+      struct ipaddr_str addrbuf, dstaddrbuf;
+      OLSR_PRINTF(1, "%-*s %-*s  %5.3f  %5.3f  %.2f\n",
+                  ipwidth, olsr_ip_to_string(&addrbuf, &tc->addr),
+                  ipwidth, olsr_ip_to_string(&dstaddrbuf, &tc_edge->T_dest_addr),
+                  tc_edge->link_quality,
+                  tc_edge->inverse_link_quality,
+                  olsr_calc_tc_etx(tc_edge));
+    } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
+  } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
+#endif
+}
 
-      if (tc_edge->link_quality < MIN_LINK_QUALITY ||
-          tc_edge->inverse_link_quality < MIN_LINK_QUALITY) {
-        etx = 0.0;
-      } else {
-        etx = 1.0 / (tc_edge->link_quality * tc_edge->inverse_link_quality);
-      }
+float olsr_calc_tc_etx(const struct tc_edge_entry *tc_edge)
+{
+  return tc_edge->link_quality < MIN_LINK_QUALITY ||
+         tc_edge->inverse_link_quality < MIN_LINK_QUALITY
+             ? 0.0
+             : 1.0 / (tc_edge->link_quality * tc_edge->inverse_link_quality);
+}
 
-      OLSR_PRINTF(1, fstr, olsr_ip_to_string(&tc->addr),
-                  olsr_ip_to_string(&tc_edge->T_dest_addr),
-                  tc_edge->link_quality, tc_edge->inverse_link_quality, etx);
+/*
+ * Process an incoming TC or TC_LQ message.
+ *
+ * If the message is interesting enough, update our edges for it,
+ * trigger SPF and finally flood it to all our 2way neighbors.
+ *
+ * The order for extracting data off the message does matter, 
+ * as every call to pkt_get increases the packet offset and
+ * hence the spot we are looking at.
+ */
+void
+olsr_input_tc(union olsr_message *msg, struct interface *input_if,
+              union olsr_ip_addr *from_addr)
+{
+#ifndef NODEBUG 
+  struct ipaddr_str buf;
+#endif
+  olsr_u16_t size, msg_seq, ansn;
+  olsr_u8_t type, ttl, msg_hops;
+  double vtime;
+  unsigned int vtime_s;
+  union olsr_ip_addr originator;
+  union olsr_ip_addr *main_addr;
+  const unsigned char *limit, *curr;
+  struct tc_entry *tc;
 
-    } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
-  } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
+  curr = (void *)msg;
+  if (!msg) {
+    return;
+  }
+
+  /* We are only interested in TC message types. */
+  pkt_get_u8(&curr, &type);
+  if ((type != LQ_TC_MESSAGE) && (type != TC_MESSAGE)) {
+    return;
+  }
+
+  pkt_get_double(&curr, &vtime);
+  vtime_s = (unsigned int)vtime;
+  pkt_get_u16(&curr, &size);
 
-  return 1;
+  pkt_get_ipaddress(&curr, &originator);
+
+  /* Copy header values */
+  pkt_get_u8(&curr, &ttl);
+  pkt_get_u8(&curr, &msg_hops);
+  pkt_get_u16(&curr, &msg_seq);
+  pkt_get_u16(&curr, &ansn);
+  pkt_ignore_u16(&curr);
+
+  /*
+   * Check if we know this guy and if we already know what he has to say.
+   */
+  tc = olsr_lookup_tc_entry(&originator);
+  if (tc) {
+    if (!SEQNO_GREATER_THAN(msg_seq, tc->msg_seq)) {
+      return;
+    }
+  }
+
+  /* Check the sender address. */
+  if (!olsr_validate_address(&originator)) {
+    return;
+  }
+
+  /* Check the main address. */
+  main_addr = mid_lookup_main_addr(from_addr);
+  if (!main_addr) {
+    main_addr = from_addr;
+  }
+  if (!olsr_validate_address(main_addr)) {
+    return;
+  }
+
+  /*
+   * Generate an new tc_entry in the lsdb and store the sequence number.
+   */
+  if (!tc) {
+    tc = olsr_add_tc_entry(&originator);
+    tc->msg_seq = msg_seq;
+  }
+
+  OLSR_PRINTF(1, "Processing TC from %s, seq 0x%04x\n",
+              olsr_ip_to_string(&buf, &originator), ansn);
+
+  /*
+   * If the sender interface (NB: not originator) of this message
+   * is not in the symmetric 1-hop neighborhood of this node, the
+   * message MUST be discarded.
+   */
+  if (check_neighbor_link(from_addr) != SYM_LINK) {
+    OLSR_PRINTF(2, "Received TC from NON SYM neighbor %s\n",
+                olsr_ip_to_string(&buf, from_addr));
+    return;
+  }
+
+  /*
+   * Update the tc entry.
+   */
+  tc->msg_hops = msg_hops;
+  tc->msg_seq = msg_seq;
+
+  /*
+   * Now walk the edge advertisements contained in the packet.
+   * Play some efficiency games here, like checking first
+   * if the edge exists in order to avoid address validation.
+   */
+  limit = (void *)msg + size;
+  while (curr < limit) {
+    if (olsr_tc_update_edge(tc, vtime_s, ansn, type, &curr)) {
+      changes_topology = OLSR_TRUE;
+    }
+  }
+
+  /*
+   * Do the edge garbage collection at the end in order
+   * to avoid malloc() churn.
+   */
+  if (olsr_delete_outdated_tc_edges(tc, ansn)) {
+    changes_topology = OLSR_TRUE;
+  }
+
+  /*
+   * Last, flood the message to our other neighbors.
+   */
+  olsr_forward_message(msg, &originator, msg_seq, input_if, from_addr);
+  return;
 }
 
 /*