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