src/cadet/cadet_path.c

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