remove the per tc_edge timer
authorHannes Gredler <hannes@gredler.at>
Mon, 28 Apr 2008 20:46:05 +0000 (22:46 +0200)
committerHannes Gredler <hannes@gredler.at>
Mon, 28 Apr 2008 20:46:05 +0000 (22:46 +0200)
a timer per tc_edge is a useless burning of timer resources in the system.
replace it with a garbage collection timer whcih is kicked 2s after
a TC reception. This also makes sure that multi part messages do
not cause tc_edge churn. we do a similar thing than with the rt_entry tree,
which is to keep the ansn per tc_edge and kill the outdated edges after the timer
fires. This is also a good opportunity to change the tc_entry to a clean
refcounted model which will make life easier in the future, towards a unified
link-state database.

lib/bmf/src/NetworkInterfaces.c
src/lq_route.c
src/routing_table.c
src/routing_table.h
src/tc_set.c
src/tc_set.h

index 7045dec..efbaaff 100644 (file)
@@ -896,9 +896,8 @@ void FindNeighbors(
           /* TODO: olsr_lookup_tc_edge() is not thread-safe. */
           tc_edge = olsr_lookup_tc_edge(tcLastHop, MainAddressOf(&walker->neighbor_iface_addr));
 
-          /* We are not interested in dead-end or dying edges. */
-          if (tc_edge != NULL && (tc_edge->flags & OLSR_TC_EDGE_DOWN) == 0)
-          {
+          /* We are not interested in dead-end edges. */
+          if (tc_edge) {
             olsr_linkcost tcEtx = tc_edge->cost;
 
             if (previousLinkEtx + currEtx > tcEtx)
index 01748ce..9795815 100644 (file)
@@ -212,20 +212,14 @@ olsr_spf_relax (struct avl_tree *cand_tree, struct tc_entry *tc)
     struct tc_edge_entry *tc_edge = edge_tree2tc_edge(edge_node);
 
     /*
-     * We are not interested in dead-end or dying edges.
+     * We are not interested in dead-end edges.
      */
-    if (!tc_edge->edge_inv ||
-        ((tc_edge->flags | tc_edge->edge_inv->flags) & OLSR_TC_EDGE_DOWN)) {
+    if (!tc_edge->edge_inv) {
 #ifdef DEBUG
       OLSR_PRINTF(2, "SPF:   ignoring edge %s\n",
                   olsr_ip_to_string(&buf, &tc_edge->T_dest_addr));
-      if (tc_edge->flags & OLSR_TC_EDGE_DOWN) {
-        OLSR_PRINTF(2, "SPF:     edge down\n");
-      }
       if (!tc_edge->edge_inv) {
         OLSR_PRINTF(2, "SPF:     no inverse edge\n");
-      }  else if (tc_edge->edge_inv->flags & OLSR_TC_EDGE_DOWN){
-        OLSR_PRINTF(2, "SPF:     inverse edge down\n");
       }
 #endif
       continue;
@@ -238,15 +232,15 @@ olsr_spf_relax (struct avl_tree *cand_tree, struct tc_entry *tc)
     new_cost = tc->path_cost + tc_edge->cost;
 
 #ifdef DEBUG
-      OLSR_PRINTF(2, "SPF:   exploring edge %s, cost %s\n",
-                  olsr_ip_to_string(&buf, &tc_edge->T_dest_addr),
-                  get_linkcost_text(new_cost, OLSR_TRUE, &lqbuffer));
+    OLSR_PRINTF(2, "SPF:   exploring edge %s, cost %s\n",
+                olsr_ip_to_string(&buf, &tc_edge->T_dest_addr),
+                get_linkcost_text(new_cost, OLSR_TRUE, &lqbuffer));
 #endif
 
-      /* 
-       * if it's better than the current path quality of this edge's
-       * destination node, then we've found a better path to this node.
-       */
+    /* 
+     * if it's better than the current path quality of this edge's
+     * destination node, then we've found a better path to this node.
+     */
     new_tc = tc_edge->edge_inv->tc;
 
     if (new_cost < new_tc->path_cost) {
@@ -406,13 +400,13 @@ olsr_calculate_routing_table (void *context __attribute__((unused)))
        */
       if (!tc_edge) {
         tc_edge = olsr_add_tc_edge_entry(tc_myself, &neigh->neighbor_main_addr,
-                                         0, link->vtime);
+                                         0);
       } else {
+
         /*
          * Update LQ and timers, such that the edge does not get deleted.
          */
         olsr_copylq_link_entry_2_tc_edge_entry(tc_edge, link);
-        olsr_set_tc_edge_timer(tc_edge, link->vtime*1000);
         olsr_calc_tc_edge_entry_etx(tc_edge);
       }
       if (tc_edge->edge_inv) {
index d17ca00..589be22 100644 (file)
@@ -260,6 +260,7 @@ olsr_alloc_rt_path(struct tc_entry *tc,
 
   /* insert to the tc prefix tree */
   avl_insert(&tc->prefix_tree, &rtp->rtp_prefix_tree_node, AVL_DUP_NO);
+  olsr_lock_tc_entry(tc);
 
   /* backlink to the owning tc entry */
   rtp->rtp_tc = tc;
@@ -333,8 +334,8 @@ olsr_insert_rt_path(struct rt_path *rtp, struct tc_entry *tc,
 /**
  * Unlink and free a rt_path.
  */
-static void
-olsr_free_rt_path(struct rt_path *rtp)
+void
+olsr_delete_rt_path(struct rt_path *rtp)
 {
 
   /* remove from the originator tree */
@@ -346,6 +347,7 @@ olsr_free_rt_path(struct rt_path *rtp)
   /* remove from the tc prefix tree */
   if (rtp->rtp_tc) {
     avl_delete(&rtp->rtp_tc->prefix_tree, &rtp->rtp_prefix_tree_node);
+    olsr_unlock_tc_entry(rtp->rtp_tc);
     rtp->rtp_tc = NULL;
   }
 
@@ -529,9 +531,8 @@ olsr_insert_routing_table(union olsr_ip_addr *dst, int plen,
 #endif
 
   /*
-   * For internal routes the tc_entry must already exist.
-   * For all other routes we may create it as an edgeless
-   * hookup point. If so he tc_entry has no edges it will not
+   * For all routes we use the tc_entry as an hookup point.
+   * If the tc_entry is disconnected, i.e. has no edges it will not
    * be explored during SPF run.
    */
   tc = olsr_locate_tc_entry(originator);
@@ -607,7 +608,7 @@ olsr_delete_routing_table(union olsr_ip_addr *dst, int plen,
 
   if (node) {
     rtp = rtp_prefix_tree2rtp(node);
-    olsr_free_rt_path(rtp);
+    olsr_delete_rt_path(rtp);
 
     /* overload the hna change bit for flagging a prefix change */
     changes_hna = OLSR_TRUE;
index 83159b0..8440149 100644 (file)
@@ -228,6 +228,7 @@ struct rt_path *olsr_insert_routing_table(union olsr_ip_addr *, int, union olsr_
 void olsr_delete_routing_table(union olsr_ip_addr *, int, union olsr_ip_addr *);
 void olsr_insert_rt_path(struct rt_path *, struct tc_entry *, struct link_entry *);
 void olsr_update_rt_path(struct rt_path *, struct tc_entry *, struct link_entry *);
+void olsr_delete_rt_path(struct rt_path *);
 
 struct rt_entry *
 olsr_lookup_routing_table(const union olsr_ip_addr *);
index f9fe526..21ff544 100644 (file)
@@ -50,6 +50,7 @@
 #include "lq_packet.h"
 #include "net_olsr.h"
 #include "lq_plugin.h"
+#include "olsr_cookie.h"
 
 #include <assert.h>
 
 struct avl_tree tc_tree;
 struct tc_entry *tc_myself; /* Shortcut to ourselves */
 
-/* Sven-Ola 2007-Dec: These four constants include an assumption
+/* Some cookies for stats keeping */
+struct olsr_cookie_info *tc_edge_gc_timer_cookie = NULL;
+struct olsr_cookie_info *tc_validity_timer_cookie = NULL;
+struct olsr_cookie_info *tc_edge_mem_cookie = NULL;
+struct olsr_cookie_info *tc_mem_cookie = NULL;
+
+/*
+ * Sven-Ola 2007-Dec: These four constants include an assumption
  * on how long a typical olsrd mesh memorizes (TC) messages in the
  * RAM of all nodes and how many neighbour changes between TC msgs.
  * In Berlin, we encounter hop values up to 70 which means that
@@ -130,11 +138,10 @@ olsr_add_tc_entry(union olsr_ip_addr *adr)
   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");
+  tc = olsr_cookie_malloc(tc_mem_cookie);
   if (!tc) {
     return NULL;
   }
-  memset(tc, 0, sizeof(struct tc_entry));
 
   /* Fill entry */
   tc->addr = *adr;
@@ -144,6 +151,7 @@ olsr_add_tc_entry(union olsr_ip_addr *adr)
    * Insert into the global tc tree.
    */
   avl_insert(&tc_tree, &tc->vertex_node, AVL_DUP_NO);
+  olsr_lock_tc_entry(tc);
 
   /*
    * Initialize subtrees for edges and prefixes.
@@ -171,6 +179,18 @@ olsr_init_tc(void)
 
   avl_init(&tc_tree, avl_comp_default);
 
+  /*
+   * Get some cookies for getting stats to ease troubleshooting.
+   */
+  tc_edge_gc_timer_cookie = olsr_alloc_cookie("TC edge GC", OLSR_COOKIE_TYPE_TIMER);
+  tc_validity_timer_cookie = olsr_alloc_cookie("TC validity", OLSR_COOKIE_TYPE_TIMER);
+
+  tc_edge_mem_cookie = olsr_alloc_cookie("TC edge", OLSR_COOKIE_TYPE_MEMORY);
+  olsr_cookie_set_memory_size(tc_edge_mem_cookie, sizeof(struct tc_edge_entry));
+
+  tc_mem_cookie = olsr_alloc_cookie("TC", OLSR_COOKIE_TYPE_MEMORY);
+  olsr_cookie_set_memory_size(tc_mem_cookie, sizeof(struct tc_entry));
+
   /*
    * Add a TC entry for ourselves.
    */
@@ -184,8 +204,6 @@ olsr_init_tc(void)
 void
 olsr_change_myself_tc(void)
 {
-  struct tc_edge_entry *tc_edge;
-
   if (tc_myself) {
 
     /*
@@ -196,11 +214,8 @@ olsr_change_myself_tc(void)
     }
 
     /*
-     * Flush all edges and our own tc_entry.
+     * Flush our own tc_entry.
      */
-    OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc_myself, tc_edge) {
-      olsr_delete_tc_edge_entry(tc_edge);
-    } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc_myself, tc_edge);
     olsr_delete_tc_entry(tc_myself);
   }
 
@@ -211,6 +226,31 @@ olsr_change_myself_tc(void)
   changes_topology = OLSR_TRUE;
 }
 
+/*
+ * Increment the reference counter.
+ */
+void
+olsr_lock_tc_entry(struct tc_entry *tc)
+{
+  tc->refcount++;
+}
+
+/*
+ * Unlock and free a tc_entry once all references are gone.
+ */
+void
+olsr_unlock_tc_entry(struct tc_entry *tc)
+{
+  if (--tc->refcount) {
+    return;
+  }
+
+  /*
+   * All references are gone.
+   */
+  olsr_cookie_free(tc_mem_cookie, tc);
+}
+
 /**
  * Delete a TC entry.
  *
@@ -220,6 +260,8 @@ olsr_change_myself_tc(void)
 void
 olsr_delete_tc_entry(struct tc_entry *tc)
 {
+  struct tc_edge_entry *tc_edge;
+  struct rt_path *rtp;
 #if 0
   struct ipaddr_str buf;
   OLSR_PRINTF(1, "TC: del entry %s\n", olsr_ip_to_string(&buf, &tc->addr));
@@ -231,10 +273,22 @@ olsr_delete_tc_entry(struct tc_entry *tc)
   olsr_delete_routing_table(&tc->addr, olsr_cnf->maxplen, &tc->addr);
 
   /* The edgetree and prefix tree must be empty before */
-  assert(!tc->edge_tree.count && !tc->prefix_tree.count);
+  OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+    olsr_delete_tc_edge_entry(tc_edge);
+  } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
+
+  OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp) {
+    olsr_delete_rt_path(rtp);
+  } OLSR_FOR_ALL_PREFIX_ENTRIES_END(tc, rtp);
+
+  /* Stop running timers */
+  olsr_stop_timer(tc->edge_gc_timer);
+  tc->edge_gc_timer = NULL;
+  olsr_stop_timer(tc->validity_timer);
+  tc->validity_timer = NULL;
 
   avl_delete(&tc_tree, &tc->vertex_node);
-  free(tc);
+  olsr_unlock_tc_entry(tc);
 }
 
 /**
@@ -294,29 +348,37 @@ olsr_tc_edge_to_string(struct tc_edge_entry *tc_edge)
 
 /**
  * Wrapper for the timer callback.
+ * A TC entry has not been refreshed in time.
+ * Remove it from the link-state database.
  */
 static void
-olsr_expire_tc_edge_entry(void *context)
+olsr_expire_tc_entry(void *context)
 {
-  struct tc_edge_entry *tc_edge;
+  struct tc_entry *tc;
 
-  tc_edge = (struct tc_edge_entry *)context;
-  tc_edge->edge_timer = NULL;
+  tc = (struct tc_entry *)context;
+  tc->validity_timer = NULL;
 
-  olsr_delete_tc_edge_entry(tc_edge);
+  olsr_delete_tc_entry(tc);
+  changes_topology = OLSR_TRUE;
 }
 
 /**
- * Set the TC edge expiration timer.
- *
- * all timer setting shall be done using this function.
- * The timer param is a relative timer expressed in milliseconds.
+ * Wrapper for the timer callback.
+ * Does the garbage collection of older ansn entries after no edge addition to
+ * the TC entry has happened for OLSR_TC_EDGE_GC_TIME.
  */
-void
-olsr_set_tc_edge_timer(struct tc_edge_entry *tc_edge, unsigned int rel_timer)
+static void
+olsr_expire_tc_edge_gc(void *context)
 {
-  olsr_set_timer(&tc_edge->edge_timer, rel_timer, OLSR_TC_EDGE_JITTER,
-                 OLSR_TIMER_ONESHOT, &olsr_expire_tc_edge_entry, tc_edge, 0);
+  struct tc_entry *tc;
+
+  tc = (struct tc_entry *)context;
+  tc->edge_gc_timer = NULL;
+
+  if (olsr_delete_outdated_tc_edges(tc)) {
+    changes_topology = OLSR_TRUE;
+  }
 }
 
 /*
@@ -330,6 +392,7 @@ olsr_bool
 olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *tc_edge)
 {
   olsr_linkcost old;
+
   /*
    * Some sanity check before recalculating the etx.
    */
@@ -351,7 +414,7 @@ olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *tc_edge)
  */
 struct tc_edge_entry *
 olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr,
-                       olsr_u16_t ansn, unsigned int vtime)
+                       olsr_u16_t ansn)
 {
 #if !defined(NODEBUG) && defined(DEBUG)
   struct ipaddr_str buf;
@@ -366,14 +429,14 @@ olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr,
 
   /* Fill entry */
   tc_edge->T_dest_addr = *addr;
-  olsr_set_tc_edge_timer(tc_edge, vtime*1000);
-  tc_edge->T_seq = ansn;
+  tc_edge->ansn = ansn;
   tc_edge->edge_node.key = &tc_edge->T_dest_addr;
   
   /*
    * Insert into the edge tree.
    */
   avl_insert(&tc->edge_tree, &tc_edge->edge_node, AVL_DUP_NO);
+  olsr_lock_tc_entry(tc);
 
   /*
    * Connect backpointer.
@@ -438,12 +501,7 @@ olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
 
   tc = tc_edge->tc;
   avl_delete(&tc->edge_tree, &tc_edge->edge_node);
-
-  /*
-   * Kill running timers.
-   */
-  olsr_stop_timer(tc_edge->edge_timer);
-  tc_edge->edge_timer = NULL;
+  olsr_unlock_tc_entry(tc);
 
   /*
    * Clear the backpointer of our inverse edge.
@@ -453,20 +511,6 @@ olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
     tc_edge_inv->edge_inv = NULL;
   }
 
-  /*
-   * Delete the tc_entry if the last edge and last prefix is gone.
-   */
-  if (!tc_edge->tc->edge_tree.count &&
-      !tc_edge->tc->prefix_tree.count) {
-
-    /*
-     * Only remove remote tc entries.
-     */
-    if (tc_edge->tc != tc_myself) {
-      olsr_delete_tc_entry(tc_edge->tc);
-    }
-  }
-
   free(tc_edge);
 }
 
@@ -478,31 +522,20 @@ olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
  * @param ansn the advertised neighbor set sequence number
  * @return 1 if any destinations were deleted 0 if not
  */
-static int
-olsr_delete_outdated_tc_edges(struct tc_entry *tc, olsr_u16_t ansn)
+olsr_bool
+olsr_delete_outdated_tc_edges(struct tc_entry *tc)
 {
   struct tc_edge_entry *tc_edge;
-  int retval = 0;
+  olsr_bool retval = OLSR_FALSE;
 
 #if 0
-  OLSR_PRINTF(5, "TC: deleting MPRS\n");
+  OLSR_PRINTF(5, "TC: deleting outdated TC-edge entries\n");
 #endif
 
   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
-    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.
-       * It could be that a TC message spans across multiple packets,
-       * which causes an edge delete followed by an edge add.
-       * If the edge gets refreshed in subsequent packets then we have
-       * avoided a two edge transistion.
-       * If the edge really went away then after the garbage collection
-       * timer has expired olsr_time_out_tc_set() will do the needful.
-       */
-      tc_edge->flags |= OLSR_TC_EDGE_DOWN;
-      olsr_set_tc_edge_timer(tc_edge, OLSR_TC_EDGE_GC_TIME);
-      retval = 1;
+    if (SEQNO_GREATER_THAN(tc->ansn, tc_edge->ansn)) {
+      olsr_delete_tc_edge_entry(tc_edge);
+      retval = OLSR_TRUE;
     }
   } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
 
@@ -519,7 +552,7 @@ olsr_delete_outdated_tc_edges(struct tc_entry *tc, olsr_u16_t ansn)
  * @return 1 if entries are added 0 if not
  */
 static int
-olsr_tc_update_edge(struct tc_entry *tc, unsigned int vtime_s, olsr_u16_t ansn,
+olsr_tc_update_edge(struct tc_entry *tc, olsr_u16_t ansn,
                     const unsigned char **curr)
 {
   struct tc_edge_entry *tc_edge;
@@ -546,22 +579,17 @@ olsr_tc_update_edge(struct tc_entry *tc, unsigned int vtime_s, olsr_u16_t ansn,
       return 0;
     }
 
-    tc_edge = olsr_add_tc_edge_entry(tc, &neighbor, ansn, vtime_s);
+    tc_edge = olsr_add_tc_edge_entry(tc, &neighbor, ansn);
     
     olsr_deserialize_tc_lq_pair(curr, tc_edge);
     edge_change = 1;
 
   } else {
-    /*
-     * We know this edge - Update entry.
-     */
-    olsr_set_tc_edge_timer(tc_edge, vtime_s*1000);
-    tc_edge->T_seq = ansn;
 
     /*
-     * Clear the (possibly set) down flag.
+     * We know this edge - Update entry.
      */
-    tc_edge->flags &= ~OLSR_TC_EDGE_DOWN;
+    tc_edge->ansn = ansn;
 
     /*
      * Update link quality if configured.
@@ -634,13 +662,12 @@ olsr_print_tc_table(void)
       struct ipaddr_str addrbuf, dstaddrbuf;
       struct lqtextbuffer lqbuffer1, lqbuffer2;
       
-      if (!(tc_edge->flags & OLSR_TC_EDGE_DOWN)) {
-        OLSR_PRINTF(1, "%-*s %-*s  (%-10s) %s\n",
-                    ipwidth, olsr_ip_to_string(&addrbuf, &tc->addr),
-                    ipwidth, olsr_ip_to_string(&dstaddrbuf, &tc_edge->T_dest_addr),
-                    get_tc_edge_entry_text(tc_edge, &lqbuffer1),
-                    get_linkcost_text(tc_edge->cost, OLSR_FALSE, &lqbuffer2));
-      }
+      OLSR_PRINTF(1, "%-*s %-*s  (%-10s) %s\n",
+                  ipwidth, olsr_ip_to_string(&addrbuf, &tc->addr),
+                  ipwidth, olsr_ip_to_string(&dstaddrbuf, &tc_edge->T_dest_addr),
+                  get_tc_edge_entry_text(tc_edge, &lqbuffer1),
+                  get_linkcost_text(tc_edge->cost, OLSR_FALSE, &lqbuffer2));
+      
     } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
   } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
 #endif
@@ -775,23 +802,28 @@ olsr_input_tc(union olsr_message *msg,
 
   /*
    * 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 = (unsigned char *)msg + size;
   while (curr < limit) {
-    if (olsr_tc_update_edge(tc, vtime_s, ansn, &curr)) {
+    if (olsr_tc_update_edge(tc, ansn, &curr)) {
       changes_topology = OLSR_TRUE;
     }
   }
 
   /*
-   * Do the edge garbage collection at the end in order
-   * to avoid malloc() churn.
+   * Set or change the expiration timer accordingly.
    */
-  if (olsr_delete_outdated_tc_edges(tc, ansn)) {
-    changes_topology = OLSR_TRUE;
-  }
+  olsr_set_timer(&tc->validity_timer, vtime_s * MSEC_PER_SEC,
+                 OLSR_TC_VTIME_JITTER, OLSR_TIMER_ONESHOT,
+                 &olsr_expire_tc_entry, tc, tc_validity_timer_cookie->ci_id);
+
+  /*
+   * Kick the the edge garbage collection timer. In the meantime hopefully
+   * all edges belonging to a multipart neighbor set will arrive.
+   */
+  olsr_set_timer(&tc->edge_gc_timer, OLSR_TC_EDGE_GC_TIME,
+                 OLSR_TC_EDGE_GC_JITTER, OLSR_TIMER_ONESHOT,
+                 &olsr_expire_tc_edge_gc, tc, tc_edge_gc_timer_cookie->ci_id);
 
   /*
    * Last, flood the message to our other neighbors.
index cc94a22..94eb89b 100644 (file)
@@ -51,7 +51,7 @@
 /*
  * This file holds the definitions for the link state database.
  * The lsdb consists of nodes and edges.
- * During input parsing all nodes and edges are extracted and syntesized.
+ * During input parsing all nodes and edges are extracted and synthesized.
  * The SPF calculation operates on these datasets.
  */
 
@@ -61,33 +61,26 @@ struct tc_edge_entry
   union olsr_ip_addr T_dest_addr; /* edge_node key */
   struct tc_edge_entry *edge_inv; /* shortcut, used during SPF calculation */
   struct tc_entry    *tc; /* backpointer to owning tc entry */
-  struct timer_entry *edge_timer; /* expiration timer */
-  olsr_u16_t         T_seq; /* sequence number of the advertised neighbor set */
-  olsr_u16_t         flags; /* misc flags */
   olsr_linkcost      cost; /* metric used for SPF calculation */
+  olsr_u16_t         ansn; /* ansn of this edge, used for multipart msgs */
   char               linkquality[0];
 };
 
 AVLNODE2STRUCT(edge_tree2tc_edge, struct tc_edge_entry, edge_node);
 
-#define OLSR_TC_EDGE_DOWN (1 << 0) /* this edge is down */
-#define OLSR_TC_EDGE_JITTER 5 /* percent */
-
-/*
- * Garbage collection time for downed edges
- */
-#define OLSR_TC_EDGE_GC_TIME (15*1000) /* milliseconds */
-
 struct tc_entry
 {
   struct avl_node    vertex_node; /* node keyed by ip address */
+  union olsr_ip_addr addr; /* vertex_node key */
   struct avl_node    cand_tree_node; /* SPF candidate heap, node keyed by path_etx */
+  olsr_linkcost      path_cost; /* SPF calculated distance, cand_tree_node key */
   struct list_node   path_list_node; /* SPF result list */
-  union olsr_ip_addr addr; /* vertex_node key */
   struct avl_tree    edge_tree; /* subtree for edges */
   struct avl_tree    prefix_tree; /* subtree for prefixes */
   struct link_entry  *next_hop; /* SPF calculated link to the 1st hop neighbor */
-  olsr_linkcost      path_cost; /* SPF calculated distance, cand_tree_node key */
+  struct timer_entry *edge_gc_timer; /* used for edge garbage collection */
+  struct timer_entry *validity_timer; /* tc validity time */
+  olsr_u32_t         refcount; /* reference counter */
   olsr_u16_t         msg_seq; /* sequence number of the tc message */
   olsr_u8_t          msg_hops; /* hopcount as per the tc message */
   olsr_u8_t          hops; /* SPF calculated hopcount */
@@ -97,6 +90,16 @@ struct tc_entry
   olsr_bool          err_seq_valid; /* do we have an error (unplauible seq/ansn) */
 };
 
+/*
+ * Garbage collection time for edges.
+ * This is used for multipart messages.
+ */
+#define OLSR_TC_EDGE_GC_TIME (2*1000) /* milliseconds */
+#define OLSR_TC_EDGE_GC_JITTER 5 /* percent */
+
+#define OLSR_TC_VTIME_JITTER 25 /* percent */
+
+
 AVLNODE2STRUCT(vertex_tree2tc, struct tc_entry, vertex_node);
 AVLNODE2STRUCT(cand_tree2tc, struct tc_entry, cand_tree_node);
 LISTNODE2STRUCT(pathlist2tc, struct tc_entry, path_list_node);
@@ -127,6 +130,15 @@ LISTNODE2STRUCT(pathlist2tc, struct tc_entry, path_list_node);
     tc_edge = edge_tree2tc_edge(tc_edge_node);
 #define OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge) }}
 
+#define OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp) \
+{ \
+  struct avl_node *rtp_node, *next_rtp_node; \
+  for (rtp_node = avl_walk_first(&tc->prefix_tree); \
+    rtp_node; rtp_node = next_rtp_node) { \
+    next_rtp_node = avl_walk_next(rtp_node); \
+    rtp = rtp_prefix_tree2rtp(rtp_node);
+#define OLSR_FOR_ALL_PREFIX_ENTRIES_END(tc, rtp) }}
+
 extern struct avl_tree tc_tree;
 extern struct tc_entry *tc_myself;
 
@@ -142,14 +154,16 @@ void olsr_input_tc(union olsr_message *, struct interface *,
 /* tc_entry manipulation */
 struct tc_entry *olsr_lookup_tc_entry(union olsr_ip_addr *);
 struct tc_entry *olsr_locate_tc_entry(union olsr_ip_addr *);
+void olsr_lock_tc_entry(struct tc_entry *);
+void olsr_unlock_tc_entry(struct tc_entry *);
 
 /* tc_edge_entry manipulation */
+olsr_bool olsr_delete_outdated_tc_edges(struct tc_entry *);
 char *olsr_tc_edge_to_string(struct tc_edge_entry *);
 struct tc_edge_entry *olsr_lookup_tc_edge(struct tc_entry *,
                                           union olsr_ip_addr *);
 struct tc_edge_entry *olsr_add_tc_edge_entry(struct tc_entry *,
-                                             union olsr_ip_addr *, olsr_u16_t,
-                                             unsigned int);
+                                             union olsr_ip_addr *, olsr_u16_t);
 void olsr_delete_tc_entry(struct tc_entry *);
 void olsr_delete_tc_edge_entry(struct tc_edge_entry *);
 olsr_bool olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *);