[GNUnet-SVN] r26428 - gnunet/src/dv

[gnunet]

Author: grothoff
Date: 2013-03-14 16:39:29 +0100 (Thu, 14 Mar 2013)
New Revision: 26428

Modified:
   gnunet/src/dv/gnunet-service-dv.c
Log:
-more DV hacking

Modified: gnunet/src/dv/gnunet-service-dv.c
===================================================================
--- gnunet/src/dv/gnunet-service-dv.c   2013-03-14 15:26:39 UTC (rev 26427)
+++ gnunet/src/dv/gnunet-service-dv.c   2013-03-14 15:39:29 UTC (rev 26428)
@@ -28,11 +28,11 @@
  * @author Nathan Evans
  *
  * TODO:
- * - routing tables are not exchanged with direct neighbors 
+ * - even _local_ flow control (send ACK only after core took our message) is
+ *   not implemented, but should be (easy fix, but needs adjustments to data
+ *   structures)
  * - distance updates are not properly communicate to US by core,
  *   and conversely we don't give distance updates properly to the plugin yet
- * - even local flow control (send ACK only after core took our message) is
- *   not implemented, but should be (easy fix)
  * - we send 'ACK' even if a message was dropped due to no route (may
  *   be harmless, but should at least be documented)
  */
@@ -45,6 +45,7 @@
 #include "gnunet_statistics_service.h"
 #include "gnunet_consensus_service.h"
 #include "dv.h"
+#include <gcrypt.h>
 
 /**
  * How often do we establish the consensu?
@@ -84,7 +85,7 @@
   struct GNUNET_PeerIdentity peer;
 
   /**
-   * How many hops (1-3) is this peer away?
+   * How many hops (1-3) is this peer away? in network byte order
    */
   uint32_t distance GNUNET_PACKED;
 
@@ -231,6 +232,11 @@
    */
   unsigned int pm_queue_size;
 
+  /**
+   * Flag set within 'check_target_removed' to trigger full global route 
refresh.
+   */
+  int target_removed;
+
 };
 
 
@@ -715,7 +721,7 @@
   i = get_consensus_slot (distance);
   route->set_offset = i;
   consensi[distance].targets[i] = route;
-  route->target.distance = distance;
+  route->target.distance = htonl (distance);
 }
 
 
@@ -727,7 +733,7 @@
 static void
 release_route (struct Route *route)
 {
-  consensi[route->target.distance].targets[route->set_offset] = NULL;
+  consensi[ntohl (route->target.distance)].targets[route->set_offset] = NULL;
   route->set_offset = UINT_MAX; /* indicate invalid slot */
 }
 
@@ -748,7 +754,7 @@
   i = get_consensus_slot (new_distance);
   route->set_offset = i;
   consensi[new_distance].targets[i] = route;     
-  route->target.distance = new_distance;
+  route->target.distance = htonl (new_distance);
 }
 
 
@@ -816,6 +822,245 @@
 
 
 /**
+ * Called for each 'target' in a neighbor table to free the associated memory.
+ *
+ * @param cls NULL
+ * @param key key of the value
+ * @param value value to free
+ * @return GNUNET_OK to continue to iterate
+ */
+static int
+free_targets (void *cls,
+             const struct GNUNET_HashCode *key,
+             void *value)
+{
+  GNUNET_free (value);
+  return GNUNET_OK;
+}
+
+
+/**
+ * Multihashmap iterator for checking if a given route is
+ * (now) useful to this peer.
+ *
+ * @param cls the direct neighbor for the given route
+ * @param key key value stored under
+ * @param value a 'struct Target' that may or may not be useful; not that
+ *        the distance in 'target' does not include the first hop yet
+ * @return GNUNET_YES to continue iteration, GNUNET_NO to stop
+ */
+static int
+check_possible_route (void *cls, const struct GNUNET_HashCode * key, void 
*value)
+{
+  struct DirectNeighbor *neighbor = cls;
+  struct Target *target = value;
+  struct Route *route;
+  
+  route = GNUNET_CONTAINER_multihashmap_get (all_routes,
+                                          key);
+  if (NULL != route)
+  {
+    if (ntohl (route->target.distance) > ntohl (target->distance) + 1)
+    {
+      /* this 'target' is cheaper than the existing route; switch to 
alternative route! */
+      move_route (route, ntohl (target->distance) + 1);
+      route->next_hop = neighbor;
+      // FIXME: notify plugin about distance update?
+    }
+    return GNUNET_YES; /* got a route to this target already */
+  }
+  route = GNUNET_malloc (sizeof (struct Route));
+  route->next_hop = neighbor;
+  route->target.distance = htonl (ntohl (target->distance) + 1);
+  route->target.peer = target->peer;
+  allocate_route (route, ntohl (route->target.distance));
+  GNUNET_assert (GNUNET_YES ==
+                GNUNET_CONTAINER_multihashmap_put (all_routes,
+                                                   
&route->target.peer.hashPubKey,
+                                                   route,
+                                                   
GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
+  send_connect_to_plugin (&route->target.peer, ntohl (target->distance));
+  return GNUNET_YES;
+}
+
+
+/**
+ * Multihashmap iterator for finding routes that were previously
+ * "hidden" due to a better route (called after a disconnect event).
+ *
+ * @param cls NULL
+ * @param key peer identity of the given direct neighbor
+ * @param value a 'struct DirectNeighbor' to check for additional routes
+ * @return GNUNET_YES to continue iteration
+ */
+static int
+refresh_routes (void *cls, const struct GNUNET_HashCode * key, void *value)
+{
+  struct DirectNeighbor *neighbor = value;
+
+  if (NULL != neighbor->neighbor_table)
+    GNUNET_CONTAINER_multihashmap_iterate (neighbor->neighbor_table,
+                                          &check_possible_route,
+                                          neighbor);
+  return GNUNET_YES;
+}
+
+
+/**
+ * Check if a target was removed from the set of the other peer; if so,
+ * if we also used it for our route, we need to remove it from our
+ * 'all_routes' set (and later check if an alternative path now exists).
+ *
+ * @param cls the 'struct DirectNeighbor'
+ * @param key peer identity for the target
+ * @param value a 'struct Target' previously reachable via the given neighbor
+ */
+static int
+check_target_removed (void *cls,
+                     const struct GNUNET_HashCode *key,
+                     void *value)
+{
+  struct DirectNeighbor *neighbor = cls;
+  struct Target *new_target;
+  struct Route *current_route;
+
+  new_target = GNUNET_CONTAINER_multihashmap_get 
(neighbor->neighbor_table_consensus,
+                                                 key);
+  if (NULL == new_target)
+  {
+    /* target was revoked, check if it was used */
+    current_route = GNUNET_CONTAINER_multihashmap_get (all_routes,
+                                                      key);
+    if ( (NULL == current_route) ||
+        (current_route->next_hop != neighbor) )
+    {
+      /* didn't matter, wasn't used */
+      return GNUNET_OK;
+    }
+    /* remove existing route */
+    GNUNET_assert (GNUNET_YES ==
+                  GNUNET_CONTAINER_multihashmap_remove (all_routes, key, 
current_route));
+    send_disconnect_to_plugin (&current_route->target.peer);
+    GNUNET_free (current_route);
+    neighbor->target_removed = GNUNET_YES;
+    return GNUNET_OK;
+  }
+  return GNUNET_OK;
+}
+
+
+/**
+ * Check if a target was added to the set of the other peer; if it
+ * was added or impoves the existing route, do the needed updates.
+ *
+ * @param cls the 'struct DirectNeighbor'
+ * @param key peer identity for the target
+ * @param value a 'struct Target' now reachable via the given neighbor
+ */
+static int
+check_target_added (void *cls,
+                     const struct GNUNET_HashCode *key,
+                     void *value)
+{
+  struct DirectNeighbor *neighbor = cls;
+  struct Target *target = value;
+  struct Route *current_route;
+
+  /* target was revoked, check if it was used */
+  current_route = GNUNET_CONTAINER_multihashmap_get (all_routes,
+                                                    key);
+  if (NULL != current_route)
+  {
+    /* route exists */
+    if (current_route->next_hop == neighbor)
+    {
+      /* we had the same route before, no change */
+      if (ntohl (target->distance) != ntohl (current_route->target.distance))
+      {
+       current_route->target.distance = target->distance;
+       // FIXME: notify about distance change...
+      }
+      return GNUNET_OK;
+    }
+    if (ntohl (current_route->target.distance) >= ntohl (target->distance))
+    {
+      /* alternative, shorter route exists, ignore */
+      return GNUNET_OK;
+    }
+    /* new route is better than the existing one, take over! */
+    /* NOTE: minor security issue: malicious peers may advertise
+       very short routes to take over longer paths; as we don't
+       check that the shorter routes actually work, a malicious
+       direct neighbor can use this to DoS our long routes */
+    current_route->next_hop = neighbor;
+    current_route->target.distance = target->distance;
+    // FIXME: notify about distance change
+    return GNUNET_OK;
+  }
+  /* new route */
+  current_route = GNUNET_malloc (sizeof (struct Route));
+  current_route->next_hop = neighbor;
+  current_route->target.peer = target->peer;
+  current_route->target.distance = htonl (ntohl (target->distance) + 1);
+  GNUNET_assert (GNUNET_YES ==
+                GNUNET_CONTAINER_multihashmap_put (all_routes,
+                                                   
&current_route->target.peer.hashPubKey,
+                                                   current_route,
+                                                   
GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
+  send_connect_to_plugin (&current_route->target.peer,
+                         ntohl (current_route->target.distance));
+  return GNUNET_OK;
+}
+
+
+
+/**
+ * The consensus has concluded, clean up and schedule the next one.
+ *
+ * @param cls the 'struct GNUNET_DirectNeighbor' with which we created the 
consensus
+ * @param group FIXME
+ */
+static void
+consensus_done_cb (void *cls,
+                  const struct GNUNET_CONSENSUS_Group *group)
+{
+  struct DirectNeighbor *neighbor = cls;
+
+  GNUNET_CONSENSUS_destroy (neighbor->consensus);
+  neighbor->consensus = NULL;
+  /* remove targets that disappeared */
+  neighbor->target_removed = GNUNET_NO;
+  GNUNET_CONTAINER_multihashmap_iterate (neighbor->neighbor_table,
+                                        &check_target_removed,
+                                        neighbor);
+  if (GNUNET_YES == neighbor->target_removed)
+  {
+    /* check if we got an alternative for the removed routes */
+    GNUNET_CONTAINER_multihashmap_iterate (direct_neighbors,
+                                          &refresh_routes,
+                                          NULL);    
+  }
+  /* add targets that appeared (and check for improved routes) */
+  GNUNET_CONTAINER_multihashmap_iterate (neighbor->neighbor_table_consensus,
+                                        &check_target_added,
+                                        neighbor);
+  if (NULL != neighbor->neighbor_table)
+  {
+    GNUNET_CONTAINER_multihashmap_iterate (neighbor->neighbor_table,
+                                          &free_targets,
+                                          NULL);
+    GNUNET_CONTAINER_multihashmap_destroy (neighbor->neighbor_table);
+    neighbor->neighbor_table = NULL;
+  }
+  neighbor->neighbor_table = neighbor->neighbor_table_consensus;
+  neighbor->neighbor_table_consensus = NULL;
+  neighbor->consensus_task = GNUNET_SCHEDULER_add_delayed 
(GNUNET_DV_CONSENSUS_FREQUENCY,
+                                                          &start_consensus,
+                                                          neighbor);
+}
+
+
+/**
  * We inserted the last element into the consensus, get ready to
  * insert the next element into the consensus or conclude if
  * we're done.
@@ -832,7 +1077,35 @@
   struct DirectNeighbor *neighbor = cls;
   struct GNUNET_CONSENSUS_Element element;
 
-  // FIXME: initialize element...
+  while ( (DEFAULT_FISHEYE_DEPTH - 1 > neighbor->consensus_insertion_distance) 
&&
+         (consensi[neighbor->consensus_insertion_distance].array_length == 
neighbor->consensus_insertion_offset) )
+  {
+    neighbor->consensus_insertion_offset = 0;
+    neighbor->consensus_insertion_distance++;
+    /* skip over NULL entries */
+    while ( (DEFAULT_FISHEYE_DEPTH - 1 > 
neighbor->consensus_insertion_distance) &&
+           (consensi[neighbor->consensus_insertion_distance].array_length < 
neighbor->consensus_insertion_offset) &&
+           (NULL == 
consensi[neighbor->consensus_insertion_distance].targets[neighbor->consensus_insertion_offset])
 )
+      neighbor->consensus_insertion_offset++;
+  }
+  if (DEFAULT_FISHEYE_DEPTH - 1 == neighbor->consensus_insertion_distance)
+  {
+    /* we're done, conclude! */
+    GNUNET_CONSENSUS_conclude (neighbor->consensus,
+                              GNUNET_DV_CONSENSUS_FREQUENCY,
+                              2 /* both peers */,
+                              &consensus_done_cb,
+                              neighbor);
+    return;
+  }
+  element.size = sizeof (struct Target);
+  element.data = 
&consensi[neighbor->consensus_insertion_distance].targets[neighbor->consensus_insertion_offset++]->target;
+
+  /* skip over NULL entries */
+  while ( (DEFAULT_FISHEYE_DEPTH - 1 > neighbor->consensus_insertion_distance) 
&&
+         (consensi[neighbor->consensus_insertion_distance].array_length < 
neighbor->consensus_insertion_offset) &&
+         (NULL == 
consensi[neighbor->consensus_insertion_distance].targets[neighbor->consensus_insertion_offset])
 )
+    neighbor->consensus_insertion_offset++;  
   GNUNET_CONSENSUS_insert (neighbor->consensus,
                           &element,
                           &insert_next_element,
@@ -853,8 +1126,27 @@
 learn_route_cb (void *cls,
                const struct GNUNET_CONSENSUS_Element *element)
 {
-  GNUNET_break (0); // FIXME
-  return GNUNET_SYSERR;
+  struct DirectNeighbor *neighbor = cls;
+  struct Target *target;
+
+  if (sizeof (struct Target) != element->size)
+  {
+    GNUNET_break_op (0);
+    return GNUNET_SYSERR;
+  }
+  target = GNUNET_malloc (sizeof (struct Target));
+  memcpy (target, element->data, sizeof (struct Target));
+  if (GNUNET_YES !=
+      GNUNET_CONTAINER_multihashmap_put (neighbor->neighbor_table_consensus,
+                                        &target->peer.hashPubKey,
+                                        target,
+                                        
GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
+  {
+    GNUNET_break_op (0);
+    GNUNET_free (target);
+    return GNUNET_SYSERR;
+  }
+  return GNUNET_OK;
 }
 
 
@@ -871,14 +1163,28 @@
 {
   struct DirectNeighbor *neighbor = cls;
   struct GNUNET_HashCode session_id;
+  struct GNUNET_HashCode real_session_id;
 
   neighbor->consensus_task = GNUNET_SCHEDULER_NO_TASK;
+  neighbor->consensus_insertion_offset = 0;
+  neighbor->consensus_insertion_distance = 0;
+  GNUNET_assert (NULL == neighbor->neighbor_table_consensus);
   GNUNET_assert (NULL == neighbor->consensus);
-  GNUNET_CRYPTO_hash_xor (&session_id, &my_identity.hashPubKey, 
&neighbor->peer.hashPubKey); // ARG order?
+  neighbor->neighbor_table_consensus = GNUNET_CONTAINER_multihashmap_create 
(1024, GNUNET_YES);
+  /* construct session ID seed as XOR of both peer's identities */
+  GNUNET_CRYPTO_hash_xor (&my_identity.hashPubKey, 
+                         &neighbor->peer.hashPubKey, 
+                         &session_id);
+  /* make sure session ID is unique across applications by salting it with 
'DV' */
+  GNUNET_CRYPTO_hkdf (&real_session_id, sizeof (real_session_id),
+                     GCRY_MD_SHA512, GCRY_MD_SHA256,
+                     "DV-SALT", 2,
+                     &session_id, sizeof (session_id),
+                     NULL, 0);
   neighbor->consensus = GNUNET_CONSENSUS_create (cfg,
                                                 1,
                                                 &neighbor->peer,
-                                                &session_id,
+                                                &real_session_id,
                                                 &learn_route_cb,
                                                 neighbor);
   if (NULL == neighbor->consensus)
@@ -944,7 +1250,7 @@
     }
     send_data_to_plugin (payload,
                         &rm->sender,
-                        route->target.distance);
+                        ntohl (route->target.distance));
     return GNUNET_OK;
   }
   route = GNUNET_CONTAINER_multihashmap_get (all_routes,
@@ -956,7 +1262,7 @@
                              1, GNUNET_NO);
     return GNUNET_OK;
   }
-  if (route->target.distance > ntohl (rm->distance) + 1)
+  if (ntohl (route->target.distance) > ntohl (rm->distance) + 1)
   {
     GNUNET_STATISTICS_update (stats,
                              "# messages discarded (target too far)",
@@ -964,7 +1270,7 @@
     return GNUNET_OK;
   }
   forward_payload (route->next_hop,
-                  route->target.distance,
+                  ntohl (route->target.distance),
                   &rm->sender,
                   payload);
   return GNUNET_OK;  
@@ -1017,7 +1323,7 @@
   // FIXME: flow control (send ACK only once message has left the queue...)
   send_ack_to_plugin (&msg->target, htonl (msg->uid));
   forward_payload (route->next_hop,
-                  route->target.distance,
+                  ntohl (route->target.distance),
                   &my_identity,
                   payload);
   GNUNET_SERVER_receive_done (client, GNUNET_OK);
@@ -1052,73 +1358,6 @@
 
 
 /**
- * Multihashmap iterator for checking if a given route is
- * (now) useful to this peer.
- *
- * @param cls the direct neighbor for the given route
- * @param key key value stored under
- * @param value a 'struct Target' that may or may not be useful; not that
- *        the distance in 'target' does not include the first hop yet
- * @return GNUNET_YES to continue iteration, GNUNET_NO to stop
- */
-static int
-check_possible_route (void *cls, const struct GNUNET_HashCode * key, void 
*value)
-{
-  struct DirectNeighbor *neighbor = cls;
-  struct Target *target = value;
-  struct Route *route;
-  
-  route = GNUNET_CONTAINER_multihashmap_get (all_routes,
-                                          key);
-  if (NULL != route)
-  {
-    if (route->target.distance > target->distance + 1)
-    {
-      /* this 'target' is cheaper than the existing route; switch to 
alternative route! */
-      move_route (route, target->distance + 1);
-      route->next_hop = neighbor;
-      // FIXME: notify plugin about distance update?
-    }
-    return GNUNET_YES; /* got a route to this target already */
-  }
-  route = GNUNET_malloc (sizeof (struct Route));
-  route->next_hop = neighbor;
-  route->target.distance = target->distance + 1;
-  route->target.peer = target->peer;
-  allocate_route (route, route->target.distance);
-  GNUNET_assert (GNUNET_YES ==
-                GNUNET_CONTAINER_multihashmap_put (all_routes,
-                                                   
&route->target.peer.hashPubKey,
-                                                   route,
-                                                   
GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
-  send_connect_to_plugin (&route->target.peer, target->distance);
-  return GNUNET_YES;
-}
-
-
-/**
- * Multihashmap iterator for finding routes that were previously
- * "hidden" due to a better route (called after a disconnect event).
- *
- * @param cls NULL
- * @param key peer identity of the given direct neighbor
- * @param value a 'struct DirectNeighbor' to check for additional routes
- * @return GNUNET_YES to continue iteration
- */
-static int
-refresh_routes (void *cls, const struct GNUNET_HashCode * key, void *value)
-{
-  struct DirectNeighbor *neighbor = value;
-
-  if (NULL != neighbor->neighbor_table)
-    GNUNET_CONTAINER_multihashmap_iterate (neighbor->neighbor_table,
-                                          &check_possible_route,
-                                          neighbor);
-  return GNUNET_YES;
-}
-
-
-/**
  * Cleanup all of the data structures associated with a given neighbor.
  *
  * @param neighbor neighbor to clean up
@@ -1144,6 +1383,22 @@
     GNUNET_CORE_notify_transmit_ready_cancel (neighbor->cth);
     neighbor->cth = NULL;
   }
+  if (NULL != neighbor->neighbor_table_consensus)
+  {
+    GNUNET_CONTAINER_multihashmap_iterate (neighbor->neighbor_table_consensus,
+                                          &free_targets,
+                                          NULL);
+    GNUNET_CONTAINER_multihashmap_destroy (neighbor->neighbor_table_consensus);
+    neighbor->neighbor_table_consensus = NULL;
+  }
+  if (NULL != neighbor->neighbor_table)
+  {
+    GNUNET_CONTAINER_multihashmap_iterate (neighbor->neighbor_table,
+                                          &free_targets,
+                                          NULL);
+    GNUNET_CONTAINER_multihashmap_destroy (neighbor->neighbor_table);
+    neighbor->neighbor_table = NULL;
+  }
   if (GNUNET_SCHEDULER_NO_TASK != neighbor->consensus_task)
   {
     GNUNET_SCHEDULER_cancel (neighbor->consensus_task);