Improve runtime of MPR plugin by adding cache mechanisms
authorJonathan Kirchhoff <jonathan.kirchhoff@fkie.fraunhofer.de>
Fri, 3 Feb 2017 14:22:39 +0000 (15:22 +0100)
committerJonathan Kirchhoff <jonathan.kirchhoff@fkie.fraunhofer.de>
Fri, 3 Feb 2017 14:22:39 +0000 (15:22 +0100)
src-plugins/nhdp/mpr/mpr.c
src-plugins/nhdp/mpr/neighbor-graph-flooding.c
src-plugins/nhdp/mpr/neighbor-graph-routing.c
src-plugins/nhdp/mpr/neighbor-graph.c
src-plugins/nhdp/mpr/neighbor-graph.h
src-plugins/nhdp/mpr/selection-rfc7181.c
src-plugins/nhdp/nhdp/nhdp_db.h
src-plugins/nhdp/nhdp/nhdp_domain.c

index a5c4a7b..fa35d28 100644 (file)
@@ -294,7 +294,7 @@ _validate_mpr_set(const struct nhdp_domain *domain, struct neighbor_graph *graph
     d_y_mpr = mpr_calculate_d_of_y_s(domain, graph, n2_addr, &graph->set_mpr);
     
     OONF_DEBUG(LOG_MPR, "d_y_n1 = %u", d_y_n1);
-    OONF_DEBUG(LOG_MPR, "d_y_n1 = %u", d_y_mpr);
+    OONF_DEBUG(LOG_MPR, "d_y_mpr = %u", d_y_mpr);
 
     /*
      * Second property: For any y in N2 that does not have a defined d1(y), 
index 6d4e3ca..c6b9fb6 100644 (file)
@@ -69,12 +69,12 @@ static uint32_t _calculate_d1_x(const struct nhdp_domain *domain, struct n1_node
 static uint32_t _calculate_d2_x_y(const struct nhdp_domain *domain,
     struct n1_node *x, struct addr_node *y);
 static uint32_t _calculate_d_x_y(const struct nhdp_domain *domain,
-    struct n1_node *x, struct addr_node *y);
+    struct neighbor_graph *graph, struct n1_node *x, struct addr_node *y);
 #if 0
 static uint32_t _calculate_d1_of_y(struct mpr_flooding_data *data, struct addr_node *y);
 #endif
 static uint32_t _calculate_d1_x_of_n2_addr(const struct nhdp_domain *domain,
-    struct neighbor_graph *graph, struct netaddr *addr);
+    struct neighbor_graph *graph, struct addr_node *addr);
 static void _calculate_n1(const struct nhdp_domain *domain, struct mpr_flooding_data *data);
 static void _calculate_n2(const struct nhdp_domain *domain, struct mpr_flooding_data *data);
 
@@ -103,7 +103,7 @@ _is_reachable_link_tuple(const struct nhdp_domain *domain,
 
   linkdata = nhdp_domain_get_linkdata(domain, lnk);
   if (lnk->local_if == current_interface
-      && linkdata->metric.out != RFC7181_METRIC_INFINITE
+      && linkdata->metric.out <= RFC7181_METRIC_MAX
       && lnk->status == NHDP_LINK_SYMMETRIC) {
     return true;
   }
@@ -133,7 +133,7 @@ _is_allowed_2hop_tuple(const struct nhdp_domain *domain,
 
   twohopdata = nhdp_domain_get_l2hopdata(domain, two_hop);
   if (two_hop->link->local_if == current_interface
-      && twohopdata->metric.out != RFC7181_METRIC_INFINITE) {
+      && twohopdata->metric.out <= RFC7181_METRIC_MAX) {
     return true;
   }
   return false;
@@ -165,10 +165,37 @@ _calculate_d2_x_y(const struct nhdp_domain *domain,
 
 static uint32_t
 _calculate_d_x_y(const struct nhdp_domain *domain,
-    struct n1_node *x, struct addr_node *y) {
-  uint32_t cost = _calculate_d1_x(domain, x) + _calculate_d2_x_y(domain, x, y);
-  if (cost >= RFC7181_METRIC_INFINITE_PATH) {
-    return RFC7181_METRIC_INFINITE_PATH;
+    struct neighbor_graph *graph, struct n1_node *x, struct addr_node *y) {
+  uint32_t cost, cost1, cost2, idx;
+#ifdef OONF_LOG_DEBUG_INFO
+  struct netaddr_str nbuf1, nbuf2;
+#endif
+  
+  idx = x->table_offset + y->table_offset;
+  assert(graph->d_x_y_cache);
+  cost = graph->d_x_y_cache[idx];
+  if (!cost) {
+    cost1 = _calculate_d1_x(domain, x);
+    cost2 = _calculate_d2_x_y(domain, x, y);
+    if (cost1 > RFC7181_METRIC_MAX || cost2 > RFC7181_METRIC_MAX) {
+      cost = RFC7181_METRIC_INFINITE_PATH;
+    }
+    else {
+      cost = cost1 + cost2;
+    }
+    graph->d_x_y_cache[idx] = cost;
+    OONF_DEBUG(LOG_MPR, "d_x_y(%s,%s)=%u (%u,%u)",
+               netaddr_to_string(&nbuf1, &x->addr),
+               netaddr_to_string(&nbuf2, &y->addr),
+               cost,
+               x->table_offset, y->table_offset);
+  }
+  else {
+    OONF_DEBUG(LOG_MPR, "d_x_y(%s,%s)=%u cached(%u,%u)",
+         netaddr_to_string(&nbuf1, &x->addr),
+         netaddr_to_string(&nbuf2, &y->addr),
+         cost,
+         x->table_offset, y->table_offset);
   }
   return cost;
 }
@@ -181,7 +208,7 @@ _calculate_d_x_y(const struct nhdp_domain *domain,
  */
 uint32_t
 _calculate_d1_x_of_n2_addr(const struct nhdp_domain *domain,
-    struct neighbor_graph *graph, struct netaddr *addr) {
+    struct neighbor_graph *graph, struct addr_node *addr) {
   struct n1_node *node_n1;
   struct nhdp_naddr *naddr;
   struct nhdp_link_domaindata *linkdata;
@@ -191,7 +218,7 @@ _calculate_d1_x_of_n2_addr(const struct nhdp_domain *domain,
   avl_for_each_element(&graph->set_n1, node_n1, _avl_node) {
     /* check if the address provided corresponds to this node */
     naddr = avl_find_element(&node_n1->neigh->_neigh_addresses,
-        addr, naddr, _neigh_node);
+        &addr->addr, naddr, _neigh_node);
     if (naddr) {
       linkdata = nhdp_domain_get_linkdata(domain, node_n1->link);
       return linkdata->metric.out;
@@ -213,8 +240,11 @@ _calculate_n1(const struct nhdp_domain *domain, struct mpr_flooding_data *data)
       nhdp_interface_get_name(data->current_interface));
 
   list_for_each_element(nhdp_db_get_link_list(), lnk, _global_node) {
+    // Reset temporary selection state 
+    lnk->neigh->selection_is_mpr = false;
+    
     if (_is_allowed_link_tuple(domain, data->current_interface, lnk)) {
-      mpr_add_n1_node_to_set(&data->neigh_graph.set_n1, lnk->neigh, lnk);
+      mpr_add_n1_node_to_set(&data->neigh_graph.set_n1, lnk->neigh, lnk, 0);
     }
   }
 }
@@ -244,7 +274,7 @@ _calculate_n2(const struct nhdp_domain *domain, struct mpr_flooding_data *data)
     avl_for_each_element(&n1_neigh->link->_2hop, twohop, _link_node) {
       if (_is_allowed_2hop_tuple(domain, data->current_interface, twohop)) {
         mpr_add_addr_node_to_set(&data->neigh_graph.set_n2,
-            twohop->twohop_addr);
+            twohop->twohop_addr, 0);
       }
     }
   }
index 895a197..6cc6a85 100644 (file)
@@ -68,9 +68,9 @@
 static bool _is_allowed_link_tuple(const struct nhdp_domain *domain,
     struct nhdp_interface *current_interface, struct nhdp_link *lnk);
 static uint32_t _calculate_d1_x_of_n2_addr(const struct nhdp_domain *domain,
-    struct neighbor_graph *graph, struct netaddr *addr);
+    struct neighbor_graph *graph, struct addr_node *addr);
 static uint32_t _calculate_d_x_y(const struct nhdp_domain *domain,
-    struct n1_node *x, struct addr_node *y);
+    struct neighbor_graph *, struct n1_node *x, struct addr_node *y);
 static uint32_t _calculate_d2_x_y(const struct nhdp_domain *domain,
     struct n1_node *x, struct addr_node *y);
 static uint32_t _get_willingness_n1(const struct nhdp_domain *domain,
@@ -95,7 +95,7 @@ static struct neighbor_graph_interface _rt_api_interface = {
  */
 static bool
 _is_reachable_neighbor_tuple(struct nhdp_neighbor *neigh) {
-  if (neigh->_domaindata[0].metric.in != RFC7181_METRIC_INFINITE
+  if (neigh->_domaindata[0].metric.in <= RFC7181_METRIC_MAX
       && neigh->symmetric > 0) {
     return true;
   }
@@ -130,7 +130,7 @@ static bool
 _is_allowed_2hop_tuple(const struct nhdp_domain *domain, struct nhdp_l2hop *two_hop) {
   struct nhdp_l2hop_domaindata *neighdata;
   neighdata = nhdp_domain_get_l2hopdata(domain, two_hop);
-  if (neighdata->metric.in != RFC7181_METRIC_INFINITE) {
+  if (neighdata->metric.in <= RFC7181_METRIC_MAX) {
     return true;
   }
   return false;
@@ -175,10 +175,38 @@ _calculate_d2_x_y(const struct nhdp_domain *domain, struct n1_node *x, struct ad
 }
 
 static uint32_t
-_calculate_d_x_y(const struct nhdp_domain *domain, struct n1_node *x, struct addr_node *y) {
-  uint32_t cost = _calculate_d1_x(domain, x) + _calculate_d2_x_y(domain, x, y);
-  if (cost >= RFC7181_METRIC_INFINITE_PATH) {
-    return RFC7181_METRIC_INFINITE_PATH;
+_calculate_d_x_y(const struct nhdp_domain *domain, 
+                 struct neighbor_graph *graph, struct n1_node *x, struct addr_node *y) {
+  uint32_t cost, cost1, cost2, idx;
+#ifdef OONF_LOG_DEBUG_INFO
+  struct netaddr_str nbuf1, nbuf2;
+#endif
+  
+  idx = x->table_offset + y->table_offset;
+  assert(graph->d_x_y_cache);
+  cost = graph->d_x_y_cache[idx];
+  if (!cost) {
+    cost1 = _calculate_d1_x(domain, x);
+    cost2 = _calculate_d2_x_y(domain, x, y);
+    if (cost1 > RFC7181_METRIC_MAX || cost2 > RFC7181_METRIC_MAX) {
+      cost = RFC7181_METRIC_INFINITE_PATH;
+    }
+    else {
+      cost = cost1 + cost2;
+    }
+    graph->d_x_y_cache[idx] = cost;
+    OONF_DEBUG(LOG_MPR, "d_x_y(%s,%s)=%u (%u,%u)",
+         netaddr_to_string(&nbuf1, &x->addr),
+         netaddr_to_string(&nbuf2, &y->addr),
+         cost,
+         x->table_offset, y->table_offset);
+  }
+  else {
+        OONF_DEBUG(LOG_MPR, "d_x_y(%s,%s)=%u cached(%u,%u)",
+         netaddr_to_string(&nbuf1, &x->addr),
+         netaddr_to_string(&nbuf2, &y->addr),
+         cost,
+         x->table_offset, y->table_offset);
   }
   return cost;
 }
@@ -215,15 +243,10 @@ _calculate_d1_of_y(const struct nhdp_domain *domain,
  */
 static uint32_t
 _calculate_d1_x_of_n2_addr(const struct nhdp_domain *domain,
-    struct neighbor_graph *graph, struct netaddr *addr) {
-  struct addr_node *node;
+    struct neighbor_graph *graph, struct addr_node *addr) {
   uint32_t d1_x;
 
-  node = malloc(sizeof (struct addr_node));
-  memcpy(&node->addr, addr, sizeof (struct netaddr));
-
-  d1_x = _calculate_d1_of_y(domain, graph, node);
-  free(node);
+  d1_x = _calculate_d1_of_y(domain, graph, addr);
 
   return d1_x;
 }
@@ -236,17 +259,19 @@ static void
 _calculate_n1(const struct nhdp_domain *domain, struct neighbor_graph *graph) {
   struct nhdp_neighbor *neigh;
 
-  #ifdef OONF_LOG_DEBUG_INFO
+#ifdef OONF_LOG_DEBUG_INFO
   struct netaddr_str buf1;
-  #endif
+#endif
   
   OONF_DEBUG(LOG_MPR, "Calculate N1 for routing MPRs");
   
   list_for_each_element(nhdp_db_get_neigh_list(), neigh, _global_node) {
+    // Reset temporary selection state 
+    neigh->selection_is_mpr = false;
     if (_is_allowed_neighbor_tuple(domain, neigh)) {
       OONF_DEBUG(LOG_MPR, "Add neighbor %s in: %u", netaddr_to_string(&buf1, &neigh->originator),
                  neigh->_domaindata[0].metric.in);
-      mpr_add_n1_node_to_set(&graph->set_n1, neigh, NULL);
+      mpr_add_n1_node_to_set(&graph->set_n1, neigh, NULL, 0);
     }
   }
 }
@@ -258,8 +283,9 @@ _calculate_n2(const struct nhdp_domain *domain, struct neighbor_graph *graph) {
   struct nhdp_l2hop *twohop;
   
 #ifdef OONF_LOG_DEBUG_INFO
-  struct nhdp_l2hop_domaindata *neighdata;
-  struct netaddr_str buf1;
+  struct nhdp_l2hop_domaindata *l2data;
+  struct nhdp_neighbor_domaindata *neighdata;
+  struct netaddr_str nbuf1, nbuf2;
 #endif
   
   OONF_DEBUG(LOG_MPR, "Calculate N2 for routing MPRs");
@@ -275,16 +301,19 @@ _calculate_n2(const struct nhdp_domain *domain, struct neighbor_graph *graph) {
       list_for_each_element(&n1_neigh->neigh->_links,
           lnk, _neigh_node) {
         avl_for_each_element(&lnk->_2hop, twohop, _link_node) {
-          OONF_DEBUG(LOG_MPR, "Link status %u", lnk->neigh->symmetric);
+          // OONF_DEBUG(LOG_MPR, "Link status %u", lnk->neigh->symmetric);
           if (_is_allowed_2hop_tuple(domain, twohop)) {
 
 #ifdef OONF_LOG_DEBUG_INFO
-            neighdata = nhdp_domain_get_l2hopdata(domain, twohop);
-            OONF_DEBUG(LOG_MPR, "Add twohop addr %s in: %u out: %u",
-                    netaddr_to_string(&buf1, &twohop->twohop_addr),
-                       neighdata->metric.in, neighdata->metric.out);
+            neighdata = nhdp_domain_get_neighbordata(domain, n1_neigh->neigh);
+            l2data = nhdp_domain_get_l2hopdata(domain, twohop);
+            OONF_DEBUG(LOG_MPR, "Add twohop addr %s (over %s) in: %u out: %u (path-in: %u path-out: %u)",
+                    netaddr_to_string(&nbuf1, &twohop->twohop_addr),
+                    netaddr_to_string(&nbuf2, &n1_neigh->addr),
+                    l2data->metric.in, l2data->metric.out,
+                    l2data->metric.in + neighdata->metric.in, l2data->metric.out + neighdata->metric.out);
 #endif
-            mpr_add_addr_node_to_set(&graph->set_n2, twohop->twohop_addr);
+            mpr_add_addr_node_to_set(&graph->set_n2, twohop->twohop_addr, 0);
           }
         }
       }
index 0e05d80..35a9710 100644 (file)
 /* FIXME remove unneeded includes */
 
 void
-mpr_add_n1_node_to_set(struct avl_tree *set, struct nhdp_neighbor *neigh, struct nhdp_link *lnk) {
+mpr_add_n1_node_to_set(struct avl_tree *set, struct nhdp_neighbor *neigh, struct nhdp_link *lnk, uint32_t offset) {
   struct n1_node *tmp_n1_neigh;
   tmp_n1_neigh = avl_find_element(set, &neigh->originator, tmp_n1_neigh, _avl_node);
   if (tmp_n1_neigh) {
     return;
   }
-  tmp_n1_neigh = malloc(sizeof (struct n1_node));
+  tmp_n1_neigh = calloc(1, sizeof (struct n1_node));
   tmp_n1_neigh->addr = neigh->originator;
   tmp_n1_neigh->_avl_node.key = &tmp_n1_neigh->addr;
   tmp_n1_neigh->neigh = neigh;
   tmp_n1_neigh->link = lnk;
+  tmp_n1_neigh->table_offset = offset;
   avl_insert(set, &tmp_n1_neigh->_avl_node);
 }
 
-/**
- * Add an address node to a set
- * @param current_mpr_data
- * @param node
- */
 void
-mpr_add_addr_node_to_set(struct avl_tree *set, const struct netaddr addr) {
+mpr_add_addr_node_to_set(struct avl_tree *set, const struct netaddr addr, uint32_t offset) {
   struct addr_node *tmp_node;
   
   tmp_node = avl_find_element(set, &addr, tmp_node, _avl_node);
   if (tmp_node) {
     return;
   }
-  tmp_node = malloc(sizeof (struct addr_node));
+  tmp_node = calloc(1, sizeof (struct addr_node));
   tmp_node->addr = addr;
   tmp_node->_avl_node.key = &tmp_node->addr;
+  tmp_node->table_offset = offset;
   avl_insert(set, &tmp_node->_avl_node);
 }
 
+
 /**
  * Initialize the MPR data set
  * @param current_mpr_data
@@ -154,6 +152,10 @@ mpr_clear_neighbor_graph(struct neighbor_graph *graph) {
   mpr_clear_n1_set(&graph->set_n1);
   mpr_clear_n1_set(&graph->set_mpr);
   mpr_clear_n1_set(&graph->set_mpr_candidates);
+  
+    free(graph->d_x_y_cache);
+  graph->d_x_y_cache = NULL;
+
 }
 
 /**
@@ -179,15 +181,41 @@ mpr_calculate_minimal_d_z_y(const struct nhdp_domain *domain,
     struct neighbor_graph *graph, struct addr_node *y) {
   struct n1_node *z_node;
   uint32_t d_z_y, min_d_z_y;
-
+#ifdef OONF_LOG_DEBUG_INFO
+  struct n1_node   *remember;
+  struct netaddr_str nbuf1, nbuf2;
+#endif  
+  if (y->min_d_z_y) {
+    return y->min_d_z_y;
+  }
+  
   min_d_z_y = RFC7181_METRIC_INFINITE_PATH;
-
+#ifdef OONF_LOG_DEBUG_INFO
+  remember = NULL;
+#endif
   avl_for_each_element(&graph->set_n1, z_node, _avl_node) {
-    d_z_y = graph->methods->calculate_d_x_y(domain, z_node, y);
+    d_z_y = graph->methods->calculate_d_x_y(domain, graph, z_node, y);
     if (d_z_y < min_d_z_y) {
       min_d_z_y = d_z_y;
+#ifdef OONF_LOG_DEBUG_INFO
+      remember = z_node;
+#endif
     }
   }
+  
+#ifdef OONF_LOG_DEBUG_INFO
+  if (remember) {
+    OONF_DEBUG(LOG_MPR, "minimal d_z_y(%s) = %s (cost %u)",
+               netaddr_to_string(&nbuf1, &y->addr),
+               netaddr_to_string(&nbuf2, &remember->addr),
+               min_d_z_y);
+  }
+  else {
+    OONF_DEBUG(LOG_MPR, "minimal d_z_y(%s) = infinte",
+               netaddr_to_string(&nbuf1, &y->addr));
+  }
+#endif
+  y->min_d_z_y = min_d_z_y;
   return min_d_z_y;
 }
 
@@ -253,19 +281,19 @@ mpr_calculate_d_of_y_s(const struct nhdp_domain *domain, struct neighbor_graph *
   uint32_t d_x_y, min_cost;
   struct n1_node *node_n1;
   
-  #ifdef OONF_LOG_DEBUG_INFO
+#ifdef OONF_LOG_DEBUG_INFO
   struct netaddr_str buf1;
-  #endif
+#endif
 
   /* determine the minimum cost to y over all possible intermediate hops */
-  min_cost = graph->methods->calculate_d1_x_of_n2_addr(domain, graph, &y->addr);
-  if (min_cost == RFC7181_METRIC_INFINITE) {
+  min_cost = graph->methods->calculate_d1_x_of_n2_addr(domain, graph, y);
+  if (min_cost > RFC7181_METRIC_MAX) {
     min_cost = RFC7181_METRIC_INFINITE_PATH;
   }
   OONF_DEBUG(LOG_MPR, "mpr_calculate_d_of_y_s(%s)", netaddr_to_string(&buf1, &y->addr));
   OONF_DEBUG(LOG_MPR, "initial cost = %u", min_cost);
   avl_for_each_element(subset_s, node_n1, _avl_node) {
-    d_x_y = graph->methods->calculate_d_x_y(domain, node_n1, y);
+    d_x_y = graph->methods->calculate_d_x_y(domain, graph, node_n1, y);
     OONF_DEBUG(LOG_MPR, "cost via %s would be = %u", netaddr_to_string(&buf1, &node_n1->addr), d_x_y);
     if (d_x_y < min_cost) {
       min_cost = d_x_y;
index 596637e..21933c7 100644 (file)
@@ -59,9 +59,9 @@ struct neighbor_graph_interface {
     bool (*is_allowed_link_tuple)(const struct nhdp_domain *,
         struct nhdp_interface *current_interface, struct nhdp_link *link);
     uint32_t (*calculate_d1_x_of_n2_addr)(const struct nhdp_domain *,
-        struct neighbor_graph*, struct netaddr*);
+        struct neighbor_graph*, struct addr_node *);
     uint32_t (*calculate_d_x_y)(const struct nhdp_domain *,
-        struct n1_node*, struct addr_node*);
+        struct neighbor_graph*, struct n1_node*, struct addr_node*);
     uint32_t (*calculate_d2_x_y)(const struct nhdp_domain *,
         struct n1_node*, struct addr_node*);
     uint32_t (*get_willingness_n1)(const struct nhdp_domain *, struct n1_node*);
@@ -74,12 +74,17 @@ struct neighbor_graph {
     struct avl_tree set_mpr;
     struct avl_tree set_mpr_candidates;
     struct neighbor_graph_interface *methods;
+    
+    uint32_t *d_x_y_cache;
 };
 
 /* FIXME Find a more consistent naming and/or approach to defining the set elements */
 struct addr_node {
     struct netaddr addr;
     struct avl_node _avl_node;
+
+    uint32_t table_offset;
+    uint32_t min_d_z_y;
 };
 
 /* FIXME The link field is only used for flooding, while neigh is only used for routingt MPRs;
@@ -89,11 +94,13 @@ struct n1_node {
     struct nhdp_link *link;
     struct nhdp_neighbor *neigh;
     struct avl_node _avl_node;
+    
+    uint32_t table_offset;
 };
 
-void mpr_add_n1_node_to_set(struct avl_tree *set, struct nhdp_neighbor *neigh, struct nhdp_link *link);
+void mpr_add_n1_node_to_set(struct avl_tree *set, struct nhdp_neighbor *neigh, struct nhdp_link *link, uint32_t offset);
 
-void mpr_add_addr_node_to_set(struct avl_tree *set, const struct netaddr addr);
+void mpr_add_addr_node_to_set(struct avl_tree *set, const struct netaddr addr, uint32_t offset);
 
 void mpr_init_neighbor_graph(struct neighbor_graph *graph, struct neighbor_graph_interface *methods);
 
index e13b2fb..2dc9c5d 100644 (file)
@@ -94,7 +94,7 @@ _calculate_n(const struct nhdp_domain *domain, struct neighbor_graph *graph) {
     add_to_n = false;
 
     /* calculate the 1-hop cost to this node (which may be undefined) */
-    d1_y = graph->methods->calculate_d1_x_of_n2_addr(domain, graph, &y_node->addr);
+    d1_y = graph->methods->calculate_d1_x_of_n2_addr(domain, graph, y_node);
 
     /* if this neighbor can not be reached directly, we need to add it to N */
     if (d1_y == RFC7181_METRIC_INFINITE) {
@@ -104,7 +104,7 @@ _calculate_n(const struct nhdp_domain *domain, struct neighbor_graph *graph) {
 
       /* check if an intermediate hop would reduce the path cost */
       avl_for_each_element(&graph->set_n1, x_node, _avl_node) {
-        if (graph->methods->calculate_d_x_y(domain, x_node, y_node) < d1_y) {
+        if (graph->methods->calculate_d_x_y(domain, graph, x_node, y_node) < d1_y) {
           add_to_n = true;
           break;
         }
@@ -112,7 +112,7 @@ _calculate_n(const struct nhdp_domain *domain, struct neighbor_graph *graph) {
     }
 
     if (add_to_n) {
-      mpr_add_addr_node_to_set(&graph->set_n, y_node->addr);
+      mpr_add_addr_node_to_set(&graph->set_n, y_node->addr, y_node->table_offset);
     }
   }
 }
@@ -136,14 +136,14 @@ _calculate_r(const struct nhdp_domain *domain, struct neighbor_graph *graph,
   uint32_t r, d_x_y, min_d_z_y;
   bool already_covered;
 #ifdef OONF_LOG_DEBUG_INFO
-  struct netaddr_str buf1;
+  struct netaddr_str nbuf1, nbuf2, nbuf3;
 #endif
 
   OONF_DEBUG(LOG_MPR, "Calculate R of N1 member %s",
-      netaddr_to_string(&buf1, &x_node->addr));
+      netaddr_to_string(&nbuf1, &x_node->addr));
 
   /* if x is an MPR node already, we know the result must be 0 */
-  if (mpr_is_mpr(graph, &x_node->addr)) {
+  if (x_node->neigh->selection_is_mpr) {
     OONF_DEBUG(LOG_MPR, "X is an MPR node already, return 0");
     return 0;
   }
@@ -151,12 +151,18 @@ _calculate_r(const struct nhdp_domain *domain, struct neighbor_graph *graph,
   r = 0;
 
   avl_for_each_element(&graph->set_n, y_node, _avl_node) {
+    OONF_DEBUG(LOG_MPR, "-> Check y_node = %s", 
+               netaddr_to_string(&nbuf1, &y_node->addr));
     /* calculate the cost to reach y through x */
-    d_x_y = graph->methods->calculate_d_x_y(domain, x_node, y_node);
+    d_x_y = graph->methods->calculate_d_x_y(domain, graph, x_node, y_node);
 
     /* calculate the minimum cost to reach y through any node from N1 */
     min_d_z_y = mpr_calculate_minimal_d_z_y(domain, graph, y_node);
 
+    OONF_DEBUG(LOG_MPR, "d_x_y(%s, %s) = %u, min_d_z_y(%s) = %u", netaddr_to_string(&nbuf1, &x_node->addr),
+               netaddr_to_string(&nbuf2, &y_node->addr), d_x_y,
+               netaddr_to_string(&nbuf3, &y_node->addr), min_d_z_y);
+
     if (d_x_y > min_d_z_y) {
       continue;
     }
@@ -165,8 +171,11 @@ _calculate_r(const struct nhdp_domain *domain, struct neighbor_graph *graph,
     already_covered = false;
 
     avl_for_each_element(&graph->set_n1, z_node, _avl_node) {
-      if (graph->methods->calculate_d_x_y(domain, z_node, y_node) == min_d_z_y
-          && mpr_is_mpr(graph, &z_node->addr)) {
+      if (graph->methods->calculate_d_x_y(domain, graph, z_node, y_node) == min_d_z_y
+          && z_node->neigh->selection_is_mpr) {
+        OONF_DEBUG(LOG_MPR, "Nope, %s is already covered by %s",
+                   netaddr_to_string(&nbuf1, &y_node->addr),
+                   netaddr_to_string(&nbuf2, &z_node->addr));
         already_covered = true;
         break;
       }
@@ -203,7 +212,7 @@ _process_will_always(const struct nhdp_domain *domain, struct neighbor_graph *gr
           netaddr_to_string(&buf1, &current_n1_node->addr));
       mpr_add_n1_node_to_set(&graph->set_mpr,
           current_n1_node->link->neigh,
-          current_n1_node->link);
+          current_n1_node->link, current_n1_node->table_offset);
     }
   }
 }
@@ -231,7 +240,7 @@ _process_unique_mprs(const struct nhdp_domain *domain, struct neighbor_graph *gr
 
     avl_for_each_element(&graph->set_n1, node_n1, _avl_node) {
       if (graph->methods->calculate_d2_x_y(domain, node_n1, node_n)
-          != RFC7181_METRIC_INFINITE) {
+          <= RFC7181_METRIC_MAX) {
         /* d2(x,y) is defined for this link, so this is a possible MPR node */
         possible_mprs++; // TODO Break outer loop when this becomes > 1
         possible_mpr_node = node_n1;
@@ -248,7 +257,9 @@ _process_unique_mprs(const struct nhdp_domain *domain, struct neighbor_graph *gr
           netaddr_to_string(&buf1, &possible_mpr_node->addr));
       mpr_add_n1_node_to_set(&graph->set_mpr,
           possible_mpr_node->neigh,
-          possible_mpr_node->link);
+          possible_mpr_node->link,
+          possible_mpr_node->table_offset);
+      possible_mpr_node->neigh->selection_is_mpr = true;
     }
   }
 }
@@ -290,9 +301,12 @@ _select_greatest_by_property(const struct nhdp_domain *domain,
     n1_subset = &graph->set_n1;
 //  }
 
+    /*
+     * Workaround for performance issues; function requires a rewrite!
+     */
   avl_for_each_element(n1_subset, node_n1, _avl_node) {
     current_prop = get_property(domain, graph, node_n1);
-    if (_calculate_r(domain, graph, node_n1) > 0) {
+    if (current_prop > 0) {
       if (greatest_prop_node == NULL
           || current_prop > greatest_prop) {
         greatest_prop = current_prop;
@@ -302,13 +316,13 @@ _select_greatest_by_property(const struct nhdp_domain *domain,
         /* we have a unique candidate */
         mpr_clear_n1_set(&tmp_candidate_subset);
         mpr_add_n1_node_to_set(&tmp_candidate_subset, node_n1->neigh,
-            node_n1->link);
+            node_n1->link, node_n1->table_offset);
       }
       else if (current_prop == greatest_prop) {
         /* add node to candidate subset */
         number_of_greatest++;
         mpr_add_n1_node_to_set(&tmp_candidate_subset, node_n1->neigh,
-            node_n1->link);
+            node_n1->link, node_n1->table_offset);
       }
     }
   }
@@ -318,7 +332,7 @@ _select_greatest_by_property(const struct nhdp_domain *domain,
 
   avl_for_each_element(&tmp_candidate_subset, node_n1, _avl_node) {
     mpr_add_n1_node_to_set(&graph->set_mpr_candidates, node_n1->neigh,
-        node_n1->link);
+        node_n1->link, node_n1->table_offset);
   }
 
   /* free temporary candidate subset */
@@ -381,7 +395,8 @@ _process_remaining(const struct nhdp_domain *domain, struct neighbor_graph *grap
           node_n1, _avl_node);
       OONF_DEBUG(LOG_MPR, "Unique candidate %s",
                  netaddr_to_string(&buf1, &node_n1->addr));
-      mpr_add_n1_node_to_set(&graph->set_mpr, node_n1->neigh, node_n1->link);
+      mpr_add_n1_node_to_set(&graph->set_mpr, node_n1->neigh, node_n1->link, node_n1->table_offset);
+      node_n1->neigh->selection_is_mpr = true;
       avl_remove(&graph->set_mpr_candidates, &node_n1->_avl_node);
       free(node_n1);
 //      done = true;
@@ -393,7 +408,8 @@ _process_remaining(const struct nhdp_domain *domain, struct neighbor_graph *grap
           node_n1, _avl_node);
       OONF_DEBUG(LOG_MPR, "Multiple candidates, select %s",
                  netaddr_to_string(&buf1, &node_n1->addr));
-      mpr_add_n1_node_to_set(&graph->set_mpr, node_n1->neigh, node_n1->link);
+      mpr_add_n1_node_to_set(&graph->set_mpr, node_n1->neigh, node_n1->link, node_n1->table_offset);
+      node_n1->neigh->selection_is_mpr = true;
       avl_remove(&graph->set_mpr_candidates, &node_n1->_avl_node);
       free(node_n1);
     }
@@ -405,10 +421,31 @@ _process_remaining(const struct nhdp_domain *domain, struct neighbor_graph *grap
  */
 void
 mpr_calculate_mpr_rfc7181(const struct nhdp_domain *domain, struct neighbor_graph *graph) {
+  struct n1_node *n1;
+  struct addr_node *n2;
+  uint32_t n1_count, n2_count, i;
+  
   OONF_DEBUG(LOG_MPR, "Calculate MPR set");
+  
+  n1_count = graph->set_n1.count;
+  n2_count = graph->set_n2.count;
 
-  _calculate_n(domain, graph);
+  graph->d_x_y_cache = calloc(n1_count * n2_count, sizeof(uint32_t));
+  
+  i=0;
+  avl_for_each_element(&graph->set_n1, n1, _avl_node) {
+    n1->table_offset = i;
+    i++;
+  }
+  
+  i=0;
+  avl_for_each_element(&graph->set_n2, n2, _avl_node) {
+    n2->table_offset = i;
+    i += n1_count;
+  }
 
+  _calculate_n(domain, graph);
+  
   _process_will_always(domain, graph);
   _process_unique_mprs(domain, graph);
   _process_remaining(domain, graph);
index f18920d..5235570 100644 (file)
@@ -286,6 +286,9 @@ struct nhdp_neighbor {
 
   /*! true if the neighbor has been selected as a MPR by this router */
   bool neigh_is_flooding_mpr;
+  
+  /* ! true if the neighbor has been selected as an MPR during selection algorithm */
+  bool selection_is_mpr;
 
   /*! Willingness of neighbor for flooding data */
   uint8_t flooding_willingness;
index 0036271..74ada5c 100644 (file)
@@ -407,6 +407,7 @@ nhdp_domain_init_neighbor(struct nhdp_neighbor *neigh) {
   neigh->flooding_willingness = RFC7181_WILLINGNESS_NEVER;
   neigh->local_is_flooding_mpr = false;
   neigh->neigh_is_flooding_mpr = false;
+  neigh->selection_is_mpr = false;
 
   for (i=0; i<NHDP_MAXIMUM_DOMAINS; i++) {
     neigh->_domaindata[i].metric.in = RFC7181_METRIC_INFINITE;