5 files changed, 172 insertions, 24 deletions

diff --git a/src/cadet/gnunet-service-cadet-new.h b/src/cadet/gnunet-service-cadet-new.h
index 694a5f7fd..2b68862b7 100644
--- a/src/cadet/gnunet-service-cadet-new.h
+++ b/src/cadet/gnunet-service-cadet-new.h
@@ -28,6 +28,8 @@
 #ifndef GNUNET_SERVICE_CADET_H
 #define GNUNET_SERVICE_CADET_H
 
+#include "gnunet_util_lib.h"
+
 /**
  * A client to the CADET service.
  */
@@ -77,6 +79,16 @@ struct CadetPeerPathEntry
    * Path this entry belongs to.
    */
   struct CadetPeerPath *path;
+
+  /**
+   * Path's historic score up to this point.  Basically, how often did
+   * we succeed or fail to use the path up to this entry in a
+   * connection.  Positive values indicate good experiences, negative
+   * values bad experiences.  Code updating the score must guard
+   * against overflows.
+   */
+  int score;
+
 };
 
 
diff --git a/src/cadet/gnunet-service-cadet-new_dht.h b/src/cadet/gnunet-service-cadet-new_dht.h
index 70f834de5..ff3923790 100644
--- a/src/cadet/gnunet-service-cadet-new_dht.h
+++ b/src/cadet/gnunet-service-cadet-new_dht.h
@@ -51,11 +51,11 @@ struct GCD_search_handle;
  *
  * @param cls Closure.
  * @param path An unchecked, unoptimized path to the target node.
- *             After callback will no longer be valid!
+ *             After callback will no longer be valid, unless #GCPP_acquire() is called!
  */
 typedef void
 (*GCD_search_callback) (void *cls,
-                        const struct CadetPeerPath *path);
+                        struct CadetPeerPath *path);
 
 
 /**
diff --git a/src/cadet/gnunet-service-cadet-new_paths.c b/src/cadet/gnunet-service-cadet-new_paths.c
index baffb20d2..663ce317f 100644
--- a/src/cadet/gnunet-service-cadet-new_paths.c
+++ b/src/cadet/gnunet-service-cadet-new_paths.c
@@ -26,9 +26,49 @@
  * @author Christian Grothoff
  */
 #include "platform.h"
+#include "gnunet-service-cadet-new_peer.h"
 #include "gnunet-service-cadet-new_paths.h"
 
 
+/**
+ * Information regarding a possible path to reach a peer.
+ */
+struct CadetPeerPath
+{
+
+  /**
+   * Array of all the peers on the path.  If @e hn is non-NULL, the
+   * last one is our owner.
+   */
+  struct CadetPeerPathEntry *entries;
+
+  /**
+   * Node of this path in the owner's heap.  Used to update our position
+   * in the heap whenever our @e desirability changes.
+   */
+  struct GNUNET_CONTAINER_HeapNode *hn;
+
+  /**
+   * Connections using this path, by destination peer
+   * (each hop of the path could correspond to an
+   * active connection).
+   */
+  struct GNUNET_CONTAINER_MultiPeerMap *connections;
+
+  /**
+   * Desirability of the path. How unique is it for the various peers
+   * on it?
+   */
+  GNUNET_CONTAINER_HeapCostType desirability;
+
+  /**
+   * Length of the @e entries array.
+   */
+  unsigned int entries_length;
+
+};
+
+
 
 /**
  * Return how much we like keeping the path.  This is an aggregate
@@ -44,7 +84,7 @@
  * @return desirability of the path, larger is more desirable
  */
 GNUNET_CONTAINER_HeapCostType
-GCPP_get_desirability (struct CadetPeerPath *path)
+GCPP_get_desirability (const struct CadetPeerPath *path)
 {
   GNUNET_assert (0);
   return 0;
@@ -72,23 +112,58 @@ GCPP_acquire (struct CadetPeerPath *path,
 
 
 /**
- * The given peer @a cp used to own this @a path.  However, it is no
- * longer interested in maintaining it, so the path should be
- * discarded or shortened (in case a previous peer on the path finds
- * the path desirable).
+ * The owning peer of this path is no longer interested in maintaining
+ * it, so the path should be discarded or shortened (in case a
+ * previous peer on the path finds the path desirable).
  *
  * @param path the path that is being released
- * @param cp original final destination of @a path
  */
 void
-GCPP_release (struct CadetPeerPath *path,
-              struct CadetPeer *cp)
+GCPP_release (struct CadetPeerPath *path)
 {
   GNUNET_assert (0);
 }
 
 
 /**
+ * Updates the score for an entry on the path based
+ * on our experiences with using @a path.
+ *
+ * @param path the path to update
+ * @param off offset of the entry to update
+ * @param delta change in the score to apply
+ */
+void
+GCPP_update_score (struct CadetPeerPath *path,
+                   unsigned int off,
+                   int delta)
+{
+  struct CadetPeerPathEntry *entry;
+
+  GNUNET_assert (off < path->entries_length);
+  entry = &path->entries[off];
+
+  /* Add delta, with checks for overflows */
+  if (delta >= 0)
+  {
+    if (delta + entry->score < entry->score)
+      entry->score = INT_MAX;
+    else
+      entry->score += delta;
+  }
+  else
+  {
+    if (delta + entry->score > entry->score)
+      entry->score = INT_MIN;
+    else
+      entry->score += delta;
+  }
+
+  /* FIXME: update path desirability! */
+}
+
+
+/**
  * Create a peer path based on the result of a DHT lookup.
  *
  * @param get_path path of the get request
@@ -103,6 +178,25 @@ GCPP_path_from_dht (const struct GNUNET_PeerIdentity *get_path,
                     const struct GNUNET_PeerIdentity *put_path,
                     unsigned int put_path_length)
 {
+  struct CadetPeerPath *path;
+
+  path = GNUNET_new (struct CadetPeerPath);
+  path->entries_length = get_path_length + put_path_length;
+  path->entries = GNUNET_new_array (path->entries_length,
+                                    struct CadetPeerPathEntry);
+  for (unsigned int i=0;i<get_path_length + put_path_length;i++)
+  {
+    struct CadetPeerPathEntry *entry = &path->entries[i];
+    const struct GNUNET_PeerIdentity *pid;
+
+    pid = (i < get_path_length) ? &get_path[get_path_length - i] : &put_path[path->entries_length - i];
+    entry->peer = GCP_get (pid,
+                           GNUNET_YES);
+    entry->path = path;
+    GCP_path_entry_add (entry->peer,
+                        entry,
+                        i);
+  }
   GNUNET_break (0);
   return NULL;
 }
diff --git a/src/cadet/gnunet-service-cadet-new_paths.h b/src/cadet/gnunet-service-cadet-new_paths.h
index 55e521bbf..e00b05a3d 100644
--- a/src/cadet/gnunet-service-cadet-new_paths.h
+++ b/src/cadet/gnunet-service-cadet-new_paths.h
@@ -81,7 +81,7 @@ GCPP_get_length (struct CadetPeerPath *path);
  * @return desirability of the path, larger is more desirable
  */
 GNUNET_CONTAINER_HeapCostType
-GCPP_get_desirability (struct CadetPeerPath *path);
+GCPP_get_desirability (const struct CadetPeerPath *path);
 
 
 /**
@@ -108,11 +108,9 @@ GCPP_acquire (struct CadetPeerPath *path,
  * the path desirable).
  *
  * @param path the path that is being released
- * @param cp original final destination of @a path
  */
 void
-GCPP_release (struct CadetPeerPath *path,
-              struct CadetPeer *cp);
+GCPP_release (struct CadetPeerPath *path);
 
 
 /**
diff --git a/src/cadet/gnunet-service-cadet-new_peer.c b/src/cadet/gnunet-service-cadet-new_peer.c
index 43e375c75..0ef65b7b6 100644
--- a/src/cadet/gnunet-service-cadet-new_peer.c
+++ b/src/cadet/gnunet-service-cadet-new_peer.c
@@ -37,6 +37,7 @@
 #include "gnunet-service-cadet-new.h"
 #include "gnunet-service-cadet-new_dht.h"
 #include "gnunet-service-cadet-new_peer.h"
+#include "gnunet-service-cadet-new_paths.h"
 #include "gnunet-service-cadet-new_tunnels.h"
 
 /**
@@ -45,6 +46,12 @@
 #define IDLE_PEER_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 5)
 
 /**
+ * How long do we keep paths around if we no longer care about the peer?
+ */
+#define IDLE_PATH_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
+
+
+/**
  * Struct containing all information regarding a given peer
  */
 struct CadetPeer
@@ -72,7 +79,8 @@ struct CadetPeer
   struct CadetPeerPathEntry **path_tails;
 
   /**
-   * MIN-heap of paths ending at this peer.  Ordered by desirability.
+   * MIN-heap of paths owned by this peer (they also end at this
+   * peer).  Ordered by desirability.
    */
   struct GNUNET_CONTAINER_Heap *path_heap;
 
@@ -186,8 +194,6 @@ destroy_peer (void *cls)
   }
   /* FIXME: clean up search_delayedXXX! */
 
-  GNUNET_CONTAINER_multihashmap_destroy (cp->connections);
-  GNUNET_free_non_null (cp->hello);
   if (NULL != cp->hello_offer)
   {
     GNUNET_TRANSPORT_offer_hello_cancel (cp->hello_offer);
@@ -198,6 +204,9 @@ destroy_peer (void *cls)
     GNUNET_ATS_connectivity_suggest_cancel (cp->connectivity_suggestion);
     cp->connectivity_suggestion = NULL;
   }
+  GNUNET_CONTAINER_multihashmap_destroy (cp->connections);
+  GNUNET_CONTAINER_heap_destroy (cp->path_heap);
+  GNUNET_free_non_null (cp->hello);
   GNUNET_free (cp);
 }
 
@@ -247,6 +256,34 @@ GCP_destroy_all_peers ()
  * @param cp peer to clean up
  */
 static void
+consider_peer_destroy (struct CadetPeer *cp);
+
+
+/**
+ * We really no longere care about a peer, stop hogging memory with paths to it.
+ * Afterwards, see if there is more to be cleaned up about this peer.
+ *
+ * @param cls a `struct CadetPeer`.
+ */
+static void
+drop_paths (void *cls)
+{
+  struct CadetPeer *cp = cls;
+  struct CadetPeerPath *path;
+
+  cp->destroy_task = NULL;
+  while (NULL != (path = GNUNET_CONTAINER_heap_remove_root (cp->path_heap)))
+    GCPP_release (path);
+  consider_peer_destroy (cp);
+}
+
+
+/**
+ * This peer may no longer be needed, consider cleaning it up.
+ *
+ * @param cp peer to clean up
+ */
+static void
 consider_peer_destroy (struct CadetPeer *cp)
 {
   struct GNUNET_TIME_Relative exp;
@@ -260,17 +297,24 @@ consider_peer_destroy (struct CadetPeer *cp)
     return; /* still relevant! */
   if (NULL != cp->core_mq)
     return; /* still relevant! */
-  if (0 != cp->path_dll_length)
-    return; /* still relevant! */
   if (0 != GNUNET_CONTAINER_multihashmap_size (cp->connections))
     return; /* still relevant! */
+  if (0 < GNUNET_CONTAINER_heap_get_size (cp->path_heap))
+  {
+    cp->destroy_task = GNUNET_SCHEDULER_add_delayed (IDLE_PATH_TIMEOUT,
+                                                     &drop_paths,
+                                                     cp);
+    return;
+  }
+  if (0 < cp->path_dll_length)
+    return; /* still relevant! */
   if (NULL != cp->hello)
   {
     /* relevant only until HELLO expires */
     exp = GNUNET_TIME_absolute_get_remaining (GNUNET_HELLO_get_last_expiration (cp->hello));
     cp->destroy_task = GNUNET_SCHEDULER_add_delayed (exp,
-                                                       &destroy_peer,
-                                                       cp);
+                                                     &destroy_peer,
+                                                     cp);
     return;
   }
   cp->destroy_task = GNUNET_SCHEDULER_add_delayed (IDLE_PEER_TIMEOUT,
@@ -337,7 +381,7 @@ GCP_path_entry_remove (struct CadetPeer *cp,
  */
 static void
 dht_result_cb (void *cls,
-               const struct CadetPeerPath *path)
+               struct CadetPeerPath *path)
 {
   struct CadetPeer *cp = cls;
   GNUNET_CONTAINER_HeapCostType desirability;
@@ -368,8 +412,7 @@ dht_result_cb (void *cls,
   {
     /* Now we have way too many, drop least desirable */
     root = GNUNET_CONTAINER_heap_remove_root (cp->path_heap);
-    GCPP_release (path,
-                  cp);
+    GCPP_release (path);
   }
 }
 
@@ -464,6 +507,7 @@ GCP_get (const struct GNUNET_PeerIdentity *peer_id,
   cp->pid = *peer_id;
   cp->connections = GNUNET_CONTAINER_multihashmap_create (32,
                                                           GNUNET_YES);
+  cp->path_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
   cp->search_h = NULL; // FIXME: start search immediately!?
   cp->connectivity_suggestion = NULL; // FIXME: request with ATS!?