src/cadet/cadet_path.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (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   if ((GNUNET_SCHEDULER_REASON_SHUTDOWN & tc->reason) != 0)
  52     return;
  53   path->path_delete = NULL;
  54   peer = GCP_get_short (path->peers[path->length - 1]);
  55   if (2 < path->length)
  56     GCP_remove_path (peer, path);
  57   else
  58     path_destroy (path);
  59 }
  60
  61
  62 /**
  63  * Create a new path
  64  *
  65  * @param length How many hops will the path have.
  66  *
  67  * @return A newly allocated path with a peer array of the specified length.
  68  */
  69 struct CadetPeerPath *
  70 path_new (unsigned int length)
  71 {
  72   struct CadetPeerPath *p;
  73
  74   p = GNUNET_new (struct CadetPeerPath);
  75   if (length > 0)
  76   {
  77     p->length = length;
  78     p->peers = GNUNET_malloc (length * sizeof (GNUNET_PEER_Id));
  79   }
  80   LOG (GNUNET_ERROR_TYPE_INFO, "New path %p (%u)\n", p, p->length);
  81   return p;
  82 }
  83
  84
  85 /**
  86  * Invert the path
  87  *
  88  * @param path the path to invert
  89  */
  90 void
  91 path_invert (struct CadetPeerPath *path)
  92 {
  93   GNUNET_PEER_Id aux;
  94   unsigned int i;
  95
  96   for (i = 0; i < path->length / 2; i++)
  97   {
  98     aux = path->peers[i];
  99     path->peers[i] = path->peers[path->length - i - 1];
 100     path->peers[path->length - i - 1] = aux;
 101   }
 102 }
 103
 104
 105 /**
 106  * Duplicate a path, incrementing short peer's rc.
 107  *
 108  * @param path The path to duplicate.
 109  */
 110 struct CadetPeerPath *
 111 path_duplicate (const struct CadetPeerPath *path)
 112 {
 113   struct CadetPeerPath *aux;
 114   unsigned int i;
 115
 116   aux = path_new (path->length);
 117   memcpy (aux->peers, path->peers, path->length * sizeof (GNUNET_PEER_Id));
 118   for (i = 0; i < aux->length; i++)
 119     GNUNET_PEER_change_rc (aux->peers[i], 1);
 120   return aux;
 121 }
 122
 123
 124 /**
 125  * Get the length of a path.
 126  *
 127  * @param path The path to measure, with the local peer at any point of it.
 128  *
 129  * @return Number of hops to reach destination.
 130  *         UINT_MAX in case the peer is not in the path.
 131  */
 132 unsigned int
 133 path_get_length (struct CadetPeerPath *path)
 134 {
 135   if (NULL == path)
 136     return UINT_MAX;
 137   return path->length;
 138 }
 139
 140
 141
 142 /**
 143  * Mark path as invalid: keep it aroud for a while to avoid trying it in a loop.
 144  *
 145  * Never invalidates a two-hop (direct) path, only a core handler can do that.
 146  *
 147  * Rationale: DHT_get sometimes returns bad cached results, for instance,
 148  * on a locally cached result where the PUT followed a path that is no longer
 149  * current. The path must remain "known and marked as invalid" for a while.
 150  *
 151  * @param p Path to invalidate.
 152  */
 153 void
 154 path_invalidate (struct CadetPeerPath *p)
 155 {
 156   if (NULL != p->path_delete)
 157     return;
 158
 159   LOG (GNUNET_ERROR_TYPE_INFO, "Invalidating path %p (%u)\n", p, p->length);
 160   p->path_delete = GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_MINUTES,
 161                                                  &path_destroy_delayed, p);
 162 }
 163
 164
 165 /**
 166  * Builds a path from a PeerIdentity array.
 167  *
 168  * @param peers PeerIdentity array.
 169  * @param size Size of the @c peers array.
 170  * @param myid ID of local peer, to find @c own_pos.
 171  * @param own_pos Output parameter: own position in the path.
 172  *
 173  * @return Fixed and shortened path.
 174  */
 175 struct CadetPeerPath *
 176 path_build_from_peer_ids (struct GNUNET_PeerIdentity *peers,
 177                           unsigned int size,
 178                           GNUNET_PEER_Id myid,
 179                           unsigned int *own_pos)
 180 {
 181   struct CadetPeerPath *path;
 182   GNUNET_PEER_Id shortid;
 183   unsigned int i;
 184   unsigned int j;
 185   unsigned int offset;
 186
 187   /* Create path */
 188   LOG (GNUNET_ERROR_TYPE_DEBUG, "  Creating path...\n");
 189   path = path_new (size);
 190   *own_pos = 0;
 191   offset = 0;
 192   for (i = 0; i < size; i++)
 193   {
 194     LOG (GNUNET_ERROR_TYPE_DEBUG, "  - %u: taking %s\n",
 195          i, GNUNET_i2s (&peers[i]));
 196     shortid = GNUNET_PEER_intern (&peers[i]);
 197
 198     /* Check for loops / duplicates */
 199     for (j = 0; j < i - offset; j++)
 200     {
 201       if (path->peers[j] == shortid)
 202       {
 203         LOG (GNUNET_ERROR_TYPE_DEBUG, "    already exists at pos %u\n", j);
 204         offset = i - j;
 205         LOG (GNUNET_ERROR_TYPE_DEBUG, "    offset now %u\n", offset);
 206         GNUNET_PEER_change_rc (shortid, -1);
 207       }
 208     }
 209     LOG (GNUNET_ERROR_TYPE_DEBUG, "    storing at %u\n", i - offset);
 210     path->peers[i - offset] = shortid;
 211     if (path->peers[i - offset] == myid)
 212       *own_pos = i - offset;
 213   }
 214   path->length -= offset;
 215
 216   if (path->peers[*own_pos] != myid)
 217   {
 218     /* create path: self not found in path through self */
 219     GNUNET_break_op (0);
 220     path_destroy (path);
 221     return NULL;
 222   }
 223
 224   return path;
 225 }
 226
 227
 228 /**
 229  * Test if two paths are equivalent (equal or revese of each other).
 230  *
 231  * @param p1 First path
 232  * @param p2 Second path
 233  *
 234  * @return GNUNET_YES if both paths are equivalent
 235  *         GNUNET_NO otherwise
 236  */
 237 int
 238 path_equivalent (const struct CadetPeerPath *p1,
 239                  const struct CadetPeerPath *p2)
 240 {
 241   unsigned int i;
 242   unsigned int l;
 243   unsigned int half;
 244
 245   if (p1->length != p2->length)
 246     return GNUNET_NO;
 247
 248   l = p1->length;
 249   if (0 == memcmp (p1->peers, p2->peers, sizeof (p1->peers[0]) * l))
 250     return GNUNET_YES;
 251
 252   half = l / 2;
 253   l = l - 1;
 254   for (i = 0; i <= half; i++)
 255     if (p1->peers[i] != p2->peers[l - i])
 256       return GNUNET_NO;
 257
 258   return GNUNET_YES;
 259 }
 260
 261
 262 /**
 263  * Test if a path is valid (or at least not known to be invalid).
 264  *
 265  * @param path Path to test.
 266  *
 267  * @return #GNUNET_YES If the path is valid or unknown,
 268  *         #GNUNET_NO If the path is known to be invalid.
 269  */
 270 int
 271 path_is_valid (const struct CadetPeerPath *path)
 272 {
 273   return (NULL == path->path_delete);
 274 }
 275
 276
 277 /**
 278  * Destroy the path and free any allocated resources linked to it
 279  *
 280  * @param p the path to destroy
 281  *
 282  * @return GNUNET_OK on success
 283  */
 284 int
 285 path_destroy (struct CadetPeerPath *p)
 286 {
 287   if (NULL == p)
 288     return GNUNET_OK;
 289
 290   LOG (GNUNET_ERROR_TYPE_INFO, "destroying path %p (%u)\n", p, p->length);
 291   GNUNET_PEER_decrement_rcs (p->peers, p->length);
 292   GNUNET_free_non_null (p->peers);
 293   if (NULL != p->path_delete)
 294     GNUNET_SCHEDULER_cancel (p->path_delete);
 295   GNUNET_free (p);
 296   return GNUNET_OK;
 297 }
 298
 299
 300 /**
 301  * Compare two paths.
 302  *
 303  * @param p1 First path.
 304  * @param p2 Second path.
 305  *
 306  * @return > 0 if p1 is longer, or the first differing PEER_Id is higher on p1.
 307  *         < 0 if p2 is longer, or the first differing PEER_Id is higher on p2.
 308  *         0 if they are identical.
 309  */
 310 int
 311 path_cmp (const struct CadetPeerPath *p1, const struct CadetPeerPath *p2)
 312 {
 313   if (p1->length > p2->length)
 314     return 1;
 315
 316   if (p1->length < p2->length)
 317     return -1;
 318
 319   return memcmp (p1->peers, p2->peers, sizeof (GNUNET_PEER_Id) * p1->length);
 320 }
 321
 322
 323 char *
 324 path_2s (struct CadetPeerPath *p)
 325 {
 326   char *s;
 327   char *old;
 328   unsigned int i;
 329
 330   old = GNUNET_strdup ("");
 331   for (i = 0; i < p->length; i++)
 332   {
 333     GNUNET_asprintf (&s, "%s %s",
 334                      old, GNUNET_i2s (GNUNET_PEER_resolve2 (p->peers[i])));
 335     GNUNET_free_non_null (old);
 336     old = s;
 337   }
 338   return old;
 339 }
 340
 341
 342 void
 343 path_debug (struct CadetPeerPath *p)
 344 {
 345   unsigned int i;
 346
 347   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "PATH:\n");
 348   for (i = 0; i < p->length; i++)
 349     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  %s\n",
 350                 GNUNET_i2s (GNUNET_PEER_resolve2 (p->peers[i])));
 351   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "END\n");
 352 }