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