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  * @param cls Closure (path to destroy).
  40  * @param tc Task context.
  41  */
  42 static void
  43 path_destroy_delayed (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
  44 {
  45   struct CadetPeerPath *path = cls;
  46   struct CadetPeer *peer;
  47
  48   path->path_delete = GNUNET_SCHEDULER_NO_TASK;
  49   peer = GCP_get_short (path->peers[path->length - 1]);
  50   GCP_remove_path (peer, path);
  51 }
  52
  53
  54 /**
  55  * Create a new path
  56  *
  57  * @param length How many hops will the path have.
  58  *
  59  * @return A newly allocated path with a peer array of the specified length.
  60  */
  61 struct CadetPeerPath *
  62 path_new (unsigned int length)
  63 {
  64   struct CadetPeerPath *p;
  65
  66   p = GNUNET_new (struct CadetPeerPath);
  67   if (length > 0)
  68   {
  69     p->length = length;
  70     p->peers = GNUNET_malloc (length * sizeof (GNUNET_PEER_Id));
  71   }
  72   return p;
  73 }
  74
  75
  76 /**
  77  * Invert the path
  78  *
  79  * @param path the path to invert
  80  */
  81 void
  82 path_invert (struct CadetPeerPath *path)
  83 {
  84   GNUNET_PEER_Id aux;
  85   unsigned int i;
  86
  87   for (i = 0; i < path->length / 2; i++)
  88   {
  89     aux = path->peers[i];
  90     path->peers[i] = path->peers[path->length - i - 1];
  91     path->peers[path->length - i - 1] = aux;
  92   }
  93 }
  94
  95
  96 /**
  97  * Duplicate a path, incrementing short peer's rc.
  98  *
  99  * @param path The path to duplicate.
 100  */
 101 struct CadetPeerPath *
 102 path_duplicate (const struct CadetPeerPath *path)
 103 {
 104   struct CadetPeerPath *aux;
 105   unsigned int i;
 106
 107   aux = path_new (path->length);
 108   memcpy (aux->peers, path->peers, path->length * sizeof (GNUNET_PEER_Id));
 109   for (i = 0; i < aux->length; i++)
 110     GNUNET_PEER_change_rc (aux->peers[i], 1);
 111   return aux;
 112 }
 113
 114
 115 /**
 116  * Get the length of a path.
 117  *
 118  * @param path The path to measure, with the local peer at any point of it.
 119  *
 120  * @return Number of hops to reach destination.
 121  *         UINT_MAX in case the peer is not in the path.
 122  */
 123 unsigned int
 124 path_get_length (struct CadetPeerPath *path)
 125 {
 126   if (NULL == path)
 127     return UINT_MAX;
 128   return path->length;
 129 }
 130
 131
 132
 133 /**
 134  * Mark path as invalid: keep it aroud for a while to avoid trying it in a loop.
 135  *
 136  * DHT_get sometimes returns bad cached results, for instance, on a locally
 137  * cached result where the PUT followed a path that is no longer current.
 138  *
 139  * @param p Path to invalidate.
 140  */
 141 void
 142 path_invalidate (struct CadetPeerPath *p)
 143 {
 144   if (GNUNET_SCHEDULER_NO_TASK != p->path_delete)
 145     return;
 146
 147   p->path_delete = GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_MINUTES,
 148                                                  &path_destroy_delayed, p);
 149 }
 150
 151
 152 /**
 153  * Builds a path from a PeerIdentity array.
 154  *
 155  * @param peers PeerIdentity array.
 156  * @param size Size of the @c peers array.
 157  * @param myid ID of local peer, to find @c own_pos.
 158  * @param own_pos Output parameter: own position in the path.
 159  *
 160  * @return Fixed and shortened path.
 161  */
 162 struct CadetPeerPath *
 163 path_build_from_peer_ids (struct GNUNET_PeerIdentity *peers,
 164                           unsigned int size,
 165                           GNUNET_PEER_Id myid,
 166                           unsigned int *own_pos)
 167 {
 168   struct CadetPeerPath *path;
 169   GNUNET_PEER_Id shortid;
 170   unsigned int i;
 171   unsigned int j;
 172   unsigned int offset;
 173
 174   /* Create path */
 175   LOG (GNUNET_ERROR_TYPE_DEBUG, "  Creating path...\n");
 176   path = path_new (size);
 177   *own_pos = 0;
 178   offset = 0;
 179   for (i = 0; i < size; i++)
 180   {
 181     LOG (GNUNET_ERROR_TYPE_DEBUG, "  - %u: taking %s\n",
 182          i, GNUNET_i2s (&peers[i]));
 183     shortid = GNUNET_PEER_intern (&peers[i]);
 184
 185     /* Check for loops / duplicates */
 186     for (j = 0; j < i - offset; j++)
 187     {
 188       if (path->peers[j] == shortid)
 189       {
 190         LOG (GNUNET_ERROR_TYPE_DEBUG, "    already exists at pos %u\n", j);
 191         offset = i - j;
 192         LOG (GNUNET_ERROR_TYPE_DEBUG, "    offset now %u\n", offset);
 193         GNUNET_PEER_change_rc (shortid, -1);
 194       }
 195     }
 196     LOG (GNUNET_ERROR_TYPE_DEBUG, "    storing at %u\n", i - offset);
 197     path->peers[i - offset] = shortid;
 198     if (path->peers[i - offset] == myid)
 199       *own_pos = i - offset;
 200   }
 201   path->length -= offset;
 202
 203   if (path->peers[*own_pos] != myid)
 204   {
 205     /* create path: self not found in path through self */
 206     GNUNET_break_op (0);
 207     path_destroy (path);
 208     return NULL;
 209   }
 210
 211   return path;
 212 }
 213
 214
 215 /**
 216  * Test if a path is valid (or at least not known to be invalid).
 217  *
 218  * @param path Path to test.
 219  *
 220  * @return #GNUNET_YES If the path is valid or unknown,
 221  *         #GNUNET_NO If the path is known to be invalid.
 222  */
 223 int
 224 path_is_valid (const struct CadetPeerPath *path)
 225 {
 226   return (GNUNET_SCHEDULER_NO_TASK == path->path_delete);
 227 }
 228
 229
 230 /**
 231  * Destroy the path and free any allocated resources linked to it
 232  *
 233  * @param p the path to destroy
 234  *
 235  * @return GNUNET_OK on success
 236  */
 237 int
 238 path_destroy (struct CadetPeerPath *p)
 239 {
 240   if (NULL == p)
 241     return GNUNET_OK;
 242
 243   GNUNET_PEER_decrement_rcs (p->peers, p->length);
 244   GNUNET_free_non_null (p->peers);
 245   if (GNUNET_SCHEDULER_NO_TASK != p->path_delete)
 246     GNUNET_SCHEDULER_cancel (p->path_delete);
 247   GNUNET_free (p);
 248   return GNUNET_OK;
 249 }
 250
 251
 252 char *
 253 path_2s (struct CadetPeerPath *p)
 254 {
 255   char *s;
 256   char *old;
 257   unsigned int i;
 258
 259   old = GNUNET_strdup ("");
 260   for (i = 0; i < p->length; i++)
 261   {
 262     GNUNET_asprintf (&s, "%s %s",
 263                      old, GNUNET_i2s (GNUNET_PEER_resolve2 (p->peers[i])));
 264     GNUNET_free_non_null (old);
 265     old = s;
 266   }
 267   return old;
 268 }
 269
 270
 271 void
 272 path_debug (struct CadetPeerPath *p)
 273 {
 274   unsigned int i;
 275
 276   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "PATH:\n");
 277   for (i = 0; i < p->length; i++)
 278     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  %s\n",
 279                 GNUNET_i2s (GNUNET_PEER_resolve2 (p->peers[i])));
 280   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "END\n");
 281 }