src/cadet/cadet_path.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2001 - 2013 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20
  21 /**
  22  * @file cadet/cadet_path.c
  23  * @brief Path handling functions
  24  * @author Bartlomiej Polot
  25  */
  26
  27 #include "cadet.h"
  28 #include "cadet_path.h"
  29 #include "gnunet-service-cadet_peer.h"
  30
  31 #define LOG(level, ...) GNUNET_log_from (level,"cadet-pth",__VA_ARGS__)
  32
  33
  34 /**
  35  * @brief Destroy a path after some time has past.
  36  *
  37  * If the path is returned from DHT again after a while, try again.
  38  *
  39  * Removes the path from the peer (except for direct paths).
  40  *
  41  * @param cls Closure (path to destroy).
  42  * @param tc Task context.
  43  */
  44 static void
  45 path_destroy_delayed (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
  46 {
  47   struct CadetPeerPath *path = cls;
  48   struct CadetPeer *peer;
  49
  50   LOG (GNUNET_ERROR_TYPE_INFO, "Destroy delayed %p (%u)\n", path, path->length);
  51   path->path_delete = GNUNET_SCHEDULER_NO_TASK;
  52   peer = GCP_get_short (path->peers[path->length - 1]);
  53   if (2 < path->length)
  54     GCP_remove_path (peer, path);
  55   else
  56     path_destroy (path);
  57 }
  58
  59
  60 /**
  61  * Create a new path
  62  *
  63  * @param length How many hops will the path have.
  64  *
  65  * @return A newly allocated path with a peer array of the specified length.
  66  */
  67 struct CadetPeerPath *
  68 path_new (unsigned int length)
  69 {
  70   struct CadetPeerPath *p;
  71
  72   p = GNUNET_new (struct CadetPeerPath);
  73   if (length > 0)
  74   {
  75     p->length = length;
  76     p->peers = GNUNET_malloc (length * sizeof (GNUNET_PEER_Id));
  77   }
  78   return p;
  79 }
  80
  81
  82 /**
  83  * Invert the path
  84  *
  85  * @param path the path to invert
  86  */
  87 void
  88 path_invert (struct CadetPeerPath *path)
  89 {
  90   GNUNET_PEER_Id aux;
  91   unsigned int i;
  92
  93   for (i = 0; i < path->length / 2; i++)
  94   {
  95     aux = path->peers[i];
  96     path->peers[i] = path->peers[path->length - i - 1];
  97     path->peers[path->length - i - 1] = aux;
  98   }
  99 }
 100
 101
 102 /**
 103  * Duplicate a path, incrementing short peer's rc.
 104  *
 105  * @param path The path to duplicate.
 106  */
 107 struct CadetPeerPath *
 108 path_duplicate (const struct CadetPeerPath *path)
 109 {
 110   struct CadetPeerPath *aux;
 111   unsigned int i;
 112
 113   aux = path_new (path->length);
 114   memcpy (aux->peers, path->peers, path->length * sizeof (GNUNET_PEER_Id));
 115   for (i = 0; i < aux->length; i++)
 116     GNUNET_PEER_change_rc (aux->peers[i], 1);
 117   return aux;
 118 }
 119
 120
 121 /**
 122  * Get the length of a path.
 123  *
 124  * @param path The path to measure, with the local peer at any point of it.
 125  *
 126  * @return Number of hops to reach destination.
 127  *         UINT_MAX in case the peer is not in the path.
 128  */
 129 unsigned int
 130 path_get_length (struct CadetPeerPath *path)
 131 {
 132   if (NULL == path)
 133     return UINT_MAX;
 134   return path->length;
 135 }
 136
 137
 138
 139 /**
 140  * Mark path as invalid: keep it aroud for a while to avoid trying it in a loop.
 141  *
 142  * Never invalidates a two-hop (direct) path, only a core handler can do that.
 143  *
 144  * Rationale: DHT_get sometimes returns bad cached results, for instance,
 145  * on a locally cached result where the PUT followed a path that is no longer
 146  * current. The path must remain "known and marked as invalid" for a while.
 147  *
 148  * @param p Path to invalidate.
 149  */
 150 void
 151 path_invalidate (struct CadetPeerPath *p)
 152 {
 153   if (GNUNET_SCHEDULER_NO_TASK != p->path_delete)
 154     return;
 155
 156   LOG (GNUNET_ERROR_TYPE_INFO, "Invalidating path %p (%u)\n", p, p->length);
 157   p->path_delete = GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_MINUTES,
 158                                                  &path_destroy_delayed, p);
 159 }
 160
 161
 162 /**
 163  * Builds a path from a PeerIdentity array.
 164  *
 165  * @param peers PeerIdentity array.
 166  * @param size Size of the @c peers array.
 167  * @param myid ID of local peer, to find @c own_pos.
 168  * @param own_pos Output parameter: own position in the path.
 169  *
 170  * @return Fixed and shortened path.
 171  */
 172 struct CadetPeerPath *
 173 path_build_from_peer_ids (struct GNUNET_PeerIdentity *peers,
 174                           unsigned int size,
 175                           GNUNET_PEER_Id myid,
 176                           unsigned int *own_pos)
 177 {
 178   struct CadetPeerPath *path;
 179   GNUNET_PEER_Id shortid;
 180   unsigned int i;
 181   unsigned int j;
 182   unsigned int offset;
 183
 184   /* Create path */
 185   LOG (GNUNET_ERROR_TYPE_DEBUG, "  Creating path...\n");
 186   path = path_new (size);
 187   *own_pos = 0;
 188   offset = 0;
 189   for (i = 0; i < size; i++)
 190   {
 191     LOG (GNUNET_ERROR_TYPE_DEBUG, "  - %u: taking %s\n",
 192          i, GNUNET_i2s (&peers[i]));
 193     shortid = GNUNET_PEER_intern (&peers[i]);
 194
 195     /* Check for loops / duplicates */
 196     for (j = 0; j < i - offset; j++)
 197     {
 198       if (path->peers[j] == shortid)
 199       {
 200         LOG (GNUNET_ERROR_TYPE_DEBUG, "    already exists at pos %u\n", j);
 201         offset = i - j;
 202         LOG (GNUNET_ERROR_TYPE_DEBUG, "    offset now %u\n", offset);
 203         GNUNET_PEER_change_rc (shortid, -1);
 204       }
 205     }
 206     LOG (GNUNET_ERROR_TYPE_DEBUG, "    storing at %u\n", i - offset);
 207     path->peers[i - offset] = shortid;
 208     if (path->peers[i - offset] == myid)
 209       *own_pos = i - offset;
 210   }
 211   path->length -= offset;
 212
 213   if (path->peers[*own_pos] != myid)
 214   {
 215     /* create path: self not found in path through self */
 216     GNUNET_break_op (0);
 217     path_destroy (path);
 218     return NULL;
 219   }
 220
 221   return path;
 222 }
 223
 224
 225 /**
 226  * Test if two paths are equivalent (equal or revese of each other).
 227  *
 228  * @param p1 First path
 229  * @param p2 Second path
 230  *
 231  * @return GNUNET_YES if both paths are equivalent
 232  *         GNUNET_NO otherwise
 233  */
 234 int
 235 path_equivalent (const struct CadetPeerPath *p1,
 236                  const struct CadetPeerPath *p2)
 237 {
 238   unsigned int i;
 239   unsigned int l;
 240   unsigned int half;
 241
 242   if (p1->length != p2->length)
 243     return GNUNET_NO;
 244
 245   l = p1->length;
 246   if (0 == memcmp (p1->peers, p2->peers, sizeof (p1->peers[0]) * l))
 247     return GNUNET_YES;
 248
 249   half = l / 2;
 250   l = l - 1;
 251   for (i = 0; i <= half; i++)
 252     if (p1->peers[i] != p2->peers[l - i])
 253       return GNUNET_NO;
 254
 255   return GNUNET_YES;
 256 }
 257
 258
 259 /**
 260  * Test if a path is valid (or at least not known to be invalid).
 261  *
 262  * @param path Path to test.
 263  *
 264  * @return #GNUNET_YES If the path is valid or unknown,
 265  *         #GNUNET_NO If the path is known to be invalid.
 266  */
 267 int
 268 path_is_valid (const struct CadetPeerPath *path)
 269 {
 270   return (GNUNET_SCHEDULER_NO_TASK == path->path_delete);
 271 }
 272
 273
 274 /**
 275  * Destroy the path and free any allocated resources linked to it
 276  *
 277  * @param p the path to destroy
 278  *
 279  * @return GNUNET_OK on success
 280  */
 281 int
 282 path_destroy (struct CadetPeerPath *p)
 283 {
 284   if (NULL == p)
 285     return GNUNET_OK;
 286
 287   LOG (GNUNET_ERROR_TYPE_INFO, "destroying path %p (%u)\n", p, p->length);
 288   GNUNET_PEER_decrement_rcs (p->peers, p->length);
 289   GNUNET_free_non_null (p->peers);
 290   if (GNUNET_SCHEDULER_NO_TASK != p->path_delete)
 291     GNUNET_SCHEDULER_cancel (p->path_delete);
 292   GNUNET_free (p);
 293   return GNUNET_OK;
 294 }
 295
 296
 297 char *
 298 path_2s (struct CadetPeerPath *p)
 299 {
 300   char *s;
 301   char *old;
 302   unsigned int i;
 303
 304   old = GNUNET_strdup ("");
 305   for (i = 0; i < p->length; i++)
 306   {
 307     GNUNET_asprintf (&s, "%s %s",
 308                      old, GNUNET_i2s (GNUNET_PEER_resolve2 (p->peers[i])));
 309     GNUNET_free_non_null (old);
 310     old = s;
 311   }
 312   return old;
 313 }
 314
 315
 316 void
 317 path_debug (struct CadetPeerPath *p)
 318 {
 319   unsigned int i;
 320
 321   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "PATH:\n");
 322   for (i = 0; i < p->length; i++)
 323     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  %s\n",
 324                 GNUNET_i2s (GNUNET_PEER_resolve2 (p->peers[i])));
 325   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "END\n");
 326 }