2 This file is part of GNUnet.
3 (C) 2001 - 2013 Christian Grothoff (and other contributing authors)
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.
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.
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.
22 * @file cadet/cadet_path.c
23 * @brief Path handling functions
24 * @author Bartlomiej Polot
28 #include "cadet_path.h"
29 #include "gnunet-service-cadet_peer.h"
31 #define LOG(level, ...) GNUNET_log_from (level,"cadet-pth",__VA_ARGS__)
35 * @brief Destroy a path after some time has past.
37 * If the path is returned from DHT again after a while, try again.
39 * @param cls Closure (path to destroy).
40 * @param tc Task context.
43 path_destroy_delayed (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
45 struct CadetPeerPath *path = cls;
46 struct CadetPeer *peer;
48 path->path_delete = GNUNET_SCHEDULER_NO_TASK;
49 peer = GCP_get_short (path->peers[path->length - 1]);
50 GCP_remove_path (peer, path);
57 * @param length How many hops will the path have.
59 * @return A newly allocated path with a peer array of the specified length.
61 struct CadetPeerPath *
62 path_new (unsigned int length)
64 struct CadetPeerPath *p;
66 p = GNUNET_new (struct CadetPeerPath);
70 p->peers = GNUNET_malloc (length * sizeof (GNUNET_PEER_Id));
79 * @param path the path to invert
82 path_invert (struct CadetPeerPath *path)
87 for (i = 0; i < path->length / 2; i++)
90 path->peers[i] = path->peers[path->length - i - 1];
91 path->peers[path->length - i - 1] = aux;
97 * Duplicate a path, incrementing short peer's rc.
99 * @param path The path to duplicate.
101 struct CadetPeerPath *
102 path_duplicate (const struct CadetPeerPath *path)
104 struct CadetPeerPath *aux;
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);
116 * Get the length of a path.
118 * @param path The path to measure, with the local peer at any point of it.
120 * @return Number of hops to reach destination.
121 * UINT_MAX in case the peer is not in the path.
124 path_get_length (struct CadetPeerPath *path)
134 * Mark path as invalid: keep it aroud for a while to avoid trying it in a loop.
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.
139 * @param p Path to invalidate.
142 path_invalidate (struct CadetPeerPath *p)
144 if (GNUNET_SCHEDULER_NO_TASK != p->path_delete)
147 p->path_delete = GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_MINUTES,
148 &path_destroy_delayed, p);
153 * Builds a path from a PeerIdentity array.
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.
160 * @return Fixed and shortened path.
162 struct CadetPeerPath *
163 path_build_from_peer_ids (struct GNUNET_PeerIdentity *peers,
166 unsigned int *own_pos)
168 struct CadetPeerPath *path;
169 GNUNET_PEER_Id shortid;
175 LOG (GNUNET_ERROR_TYPE_DEBUG, " Creating path...\n");
176 path = path_new (size);
179 for (i = 0; i < size; i++)
181 LOG (GNUNET_ERROR_TYPE_DEBUG, " - %u: taking %s\n",
182 i, GNUNET_i2s (&peers[i]));
183 shortid = GNUNET_PEER_intern (&peers[i]);
185 /* Check for loops / duplicates */
186 for (j = 0; j < i - offset; j++)
188 if (path->peers[j] == shortid)
190 LOG (GNUNET_ERROR_TYPE_DEBUG, " already exists at pos %u\n", j);
192 LOG (GNUNET_ERROR_TYPE_DEBUG, " offset now %u\n", offset);
193 GNUNET_PEER_change_rc (shortid, -1);
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;
201 path->length -= offset;
203 if (path->peers[*own_pos] != myid)
205 /* create path: self not found in path through self */
216 * Test if a path is valid (or at least not known to be invalid).
218 * @param path Path to test.
220 * @return #GNUNET_YES If the path is valid or unknown,
221 * #GNUNET_NO If the path is known to be invalid.
224 path_is_valid (const struct CadetPeerPath *path)
226 return (GNUNET_SCHEDULER_NO_TASK == path->path_delete);
231 * Destroy the path and free any allocated resources linked to it
233 * @param p the path to destroy
235 * @return GNUNET_OK on success
238 path_destroy (struct CadetPeerPath *p)
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);
253 path_2s (struct CadetPeerPath *p)
259 old = GNUNET_strdup ("");
260 for (i = 0; i < p->length; i++)
262 GNUNET_asprintf (&s, "%s %s",
263 old, GNUNET_i2s (GNUNET_PEER_resolve2 (p->peers[i])));
264 GNUNET_free_non_null (old);
272 path_debug (struct CadetPeerPath *p)
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");