2 This file is part of GNUnet.
3 Copyright (C) 2001 - 2013 GNUnet e.V.
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., 51 Franklin Street, Fifth Floor,
18 Boston, MA 02110-1301, 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 * Removes the path from the peer (except for direct paths).
41 * @param cls Closure (path to destroy).
44 path_destroy_delayed (void *cls)
46 struct CadetPeerPath *path = cls;
47 struct CadetPeer *peer;
48 const struct GNUNET_SCHEDULER_TaskContext *tc;
50 LOG (GNUNET_ERROR_TYPE_INFO, "Destroy delayed %p (%u)\n", path, path->length);
51 path->path_delete = NULL;
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)
57 if (2 >= path->length)
59 /* This is not the place to destroy direct paths, only core_disconnect
60 * should do it and never delay it.
64 peer = GCP_get_short (path->peers[path->length - 1], GNUNET_NO);
66 GCP_remove_path (peer, path);
76 * @param length How many hops will the path have.
78 * @return A newly allocated path with a peer array of the specified length.
80 struct CadetPeerPath *
81 path_new (unsigned int length)
83 struct CadetPeerPath *p;
85 p = GNUNET_new (struct CadetPeerPath);
89 p->peers = GNUNET_malloc (length * sizeof (GNUNET_PEER_Id));
91 LOG (GNUNET_ERROR_TYPE_INFO, "New path %p (%u)\n", p, p->length);
99 * @param path the path to invert
102 path_invert (struct CadetPeerPath *path)
107 for (i = 0; i < path->length / 2; i++)
109 aux = path->peers[i];
110 path->peers[i] = path->peers[path->length - i - 1];
111 path->peers[path->length - i - 1] = aux;
117 * Duplicate a path, incrementing short peer's rc.
119 * @param path The path to duplicate.
121 struct CadetPeerPath *
122 path_duplicate (const struct CadetPeerPath *path)
124 struct CadetPeerPath *aux;
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);
136 * Get the length of a path.
138 * @param path The path to measure, with the local peer at any point of it.
140 * @return Number of hops to reach destination.
141 * UINT_MAX in case the peer is not in the path.
144 path_get_length (struct CadetPeerPath *path)
154 * Mark path as invalid: keep it aroud for a while to avoid trying it in a loop.
156 * Never invalidates a two-hop (direct) path, only a core handler can do that.
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.
162 * @param p Path to invalidate.
165 path_invalidate (struct CadetPeerPath *p)
167 if (NULL != p->path_delete)
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);
177 * Builds a path from a PeerIdentity array.
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.
184 * @return Fixed and shortened path.
186 struct CadetPeerPath *
187 path_build_from_peer_ids (struct GNUNET_PeerIdentity *peers,
190 unsigned int *own_pos)
192 struct CadetPeerPath *path;
193 GNUNET_PEER_Id shortid;
199 LOG (GNUNET_ERROR_TYPE_DEBUG, " Creating path...\n");
200 path = path_new (size);
203 for (i = 0; i < size; i++)
205 LOG (GNUNET_ERROR_TYPE_DEBUG, " - %u: taking %s\n",
206 i, GNUNET_i2s (&peers[i]));
207 shortid = GNUNET_PEER_intern (&peers[i]);
209 /* Check for loops / duplicates */
210 for (j = 0; j < i - offset; j++)
212 if (path->peers[j] == shortid)
214 LOG (GNUNET_ERROR_TYPE_DEBUG, " already exists at pos %u\n", j);
216 LOG (GNUNET_ERROR_TYPE_DEBUG, " offset now %u\n", offset);
217 GNUNET_PEER_change_rc (shortid, -1);
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;
225 path->length -= offset;
227 if (path->peers[*own_pos] != myid)
229 /* create path: self not found in path through self */
240 * Test if two paths are equivalent (equal or revese of each other).
242 * @param p1 First path
243 * @param p2 Second path
245 * @return GNUNET_YES if both paths are equivalent
246 * GNUNET_NO otherwise
249 path_equivalent (const struct CadetPeerPath *p1,
250 const struct CadetPeerPath *p2)
256 if (NULL == p1 || NULL == p2)
259 if (p1->length != p2->length)
263 if (0 == memcmp (p1->peers, p2->peers, sizeof (p1->peers[0]) * l))
268 for (i = 0; i <= half; i++)
269 if (p1->peers[i] != p2->peers[l - i])
277 * Test if a path is valid (or at least not known to be invalid).
279 * @param path Path to test.
281 * @return #GNUNET_YES If the path is valid or unknown,
282 * #GNUNET_NO If the path is known to be invalid.
285 path_is_valid (const struct CadetPeerPath *path)
287 return (NULL == path->path_delete);
292 * Destroy the path and free any allocated resources linked to it
294 * @param p the path to destroy
296 * @return GNUNET_OK on success
299 path_destroy (struct CadetPeerPath *p)
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);
317 * @param p1 First path.
318 * @param p2 Second path.
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.
325 path_cmp (const struct CadetPeerPath *p1, const struct CadetPeerPath *p2)
327 if (p1->length > p2->length)
330 if (p1->length < p2->length)
333 return memcmp (p1->peers, p2->peers, sizeof (GNUNET_PEER_Id) * p1->length);
338 path_2s (struct CadetPeerPath *p)
344 old = GNUNET_strdup ("");
345 for (i = 0; i < p->length; i++)
347 GNUNET_asprintf (&s, "%s %s",
348 old, GNUNET_i2s (GNUNET_PEER_resolve2 (p->peers[i])));
349 GNUNET_free_non_null (old);
357 path_debug (struct CadetPeerPath *p)
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");