3 This file is part of GNUnet.
4 Copyright (C) 2001-2017 GNUnet e.V.
6 GNUnet is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published
8 by the Free Software Foundation; either version 3, or (at your
9 option) any later version.
11 GNUnet is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNUnet; see the file COPYING. If not, write to the
18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19 Boston, MA 02110-1301, USA.
23 * @file cadet/gnunet-service-cadet-new_paths.c
24 * @brief Information we track per path.
25 * @author Bartlomiej Polot
26 * @author Christian Grothoff
29 #include "gnunet-service-cadet-new_peer.h"
30 #include "gnunet-service-cadet-new_paths.h"
34 * Information regarding a possible path to reach a peer.
40 * Array of all the peers on the path. If @e hn is non-NULL, the
41 * last one is our owner.
43 struct CadetPeerPathEntry *entries;
46 * Node of this path in the owner's heap. Used to update our position
47 * in the heap whenever our @e desirability changes.
49 struct GNUNET_CONTAINER_HeapNode *hn;
52 * Connections using this path, by destination peer
53 * (each hop of the path could correspond to an
56 struct GNUNET_CONTAINER_MultiPeerMap *connections;
59 * Desirability of the path. How unique is it for the various peers
62 GNUNET_CONTAINER_HeapCostType desirability;
65 * Length of the @e entries array.
67 unsigned int entries_length;
74 * Return how much we like keeping the path. This is an aggregate
75 * score based on various factors, including the age of the path
76 * (older == better), and the value of this path to all of its ajacent
77 * peers. For example, long paths that end at a peer that we have no
78 * shorter way to reach are very desirable, while long paths that end
79 * at a peer for which we have a shorter way as well are much less
80 * desirable. Higher values indicate more valuable paths. The
81 * returned value should be used to decide which paths to remember.
83 * @param path path to return the length for
84 * @return desirability of the path, larger is more desirable
86 GNUNET_CONTAINER_HeapCostType
87 GCPP_get_desirability (const struct CadetPeerPath *path)
95 * The given peer @a cp used to own this @a path. However, it is no
96 * longer interested in maintaining it, so the path should be
97 * discarded or shortened (in case a previous peer on the path finds
98 * the path desirable).
100 * @param path the path that is being released
101 * @param node entry in the heap of @a cp where this path is anchored
102 * should be used for updates to the desirability of this path
105 GCPP_acquire (struct CadetPeerPath *path,
106 struct GNUNET_CONTAINER_HeapNode *node)
108 GNUNET_assert (NULL == path->hn);
114 * Return connection to @a destination using @a path, or return
115 * NULL if no such connection exists.
117 * @param path path to traverse
118 * @param destination destination node to get to, must be on path
119 * @param off offset of @a destination on @a path
120 * @return NULL if @a create is NO and we have no existing connection
121 * otherwise connection from us to @a destination via @a path
123 struct CadetConnection *
124 GCPP_get_connection (struct CadetPeerPath *path,
125 struct CadetPeer *destination,
128 struct CadetPeerPathEntry *entry;
130 GNUNET_assert (off < path->entries_length);
131 entry = &path->entries[off];
132 GNUNET_assert (entry->peer == destination);
138 * Notify @a path that it is used for connection @a cc
139 * which ends at the path's offset @a off.
141 * @param path the path to remember the @a cc
142 * @param off the offset where the @a cc ends
143 * @param cc the connection to remember
146 GCPP_add_connection (struct CadetPeerPath *path,
148 struct CadetConnection *cc)
150 struct CadetPeerPathEntry *entry;
152 GNUNET_assert (off < path->entries_length);
153 entry = &path->entries[off];
154 GNUNET_assert (NULL == entry->cc);
161 * Notify @a path that it is no longer used for connection @a cc which
162 * ended at the path's offset @a off.
164 * @param path the path to forget the @a cc
165 * @param off the offset where the @a cc ended
166 * @param cc the connection to forget
169 GCPP_del_connection (struct CadetPeerPath *path,
171 struct CadetConnection *cc)
173 struct CadetPeerPathEntry *entry;
175 GNUNET_assert (off < path->entries_length);
176 entry = &path->entries[off];
177 GNUNET_assert (cc == entry->cc);
183 * This path is no longer needed, free resources.
185 * @param path path resources to free
188 path_destroy (struct CadetPeerPath *path)
191 GNUNET_CONTAINER_multipeermap_size (path->connections));
192 GNUNET_CONTAINER_multipeermap_destroy (path->connections);
193 GNUNET_free (path->entries);
199 * The owning peer of this path is no longer interested in maintaining
200 * it, so the path should be discarded or shortened (in case a
201 * previous peer on the path finds the path desirable).
203 * @param path the path that is being released
206 GCPP_release (struct CadetPeerPath *path)
208 struct CadetPeerPathEntry *entry;
211 entry = &path->entries[path->entries_length - 1];
214 /* cut 'off' end of path, verifying it is not in use */
215 GNUNET_assert (NULL ==
216 GNUNET_CONTAINER_multipeermap_get (path->connections,
217 GCP_get_id (entry->peer)));
218 GCP_path_entry_remove (entry->peer,
220 path->entries_length - 1);
221 path->entries_length--; /* We don't bother shrinking the 'entries' array,
222 as it's probably not worth it. */
223 if (0 == path->entries_length)
226 /* see if new peer at the end likes this path any better */
227 entry = &path->entries[path->entries_length - 1];
228 path->hn = GCP_attach_path (entry->peer,
230 if (NULL != path->hn)
231 return; /* yep, got attached, we are done. */
234 /* nobody wants us, discard the path */
240 * Updates the score for an entry on the path based
241 * on our experiences with using @a path.
243 * @param path the path to update
244 * @param off offset of the entry to update
245 * @param delta change in the score to apply
248 GCPP_update_score (struct CadetPeerPath *path,
252 struct CadetPeerPathEntry *entry;
254 GNUNET_assert (off < path->entries_length);
255 entry = &path->entries[off];
257 /* Add delta, with checks for overflows */
260 if (delta + entry->score < entry->score)
261 entry->score = INT_MAX;
263 entry->score += delta;
267 if (delta + entry->score > entry->score)
268 entry->score = INT_MIN;
270 entry->score += delta;
273 /* FIXME: update path desirability! */
278 * Create a peer path based on the result of a DHT lookup.
279 * If we already know this path, or one that is longer,
280 * simply return NULL.
282 * FIXME: change API completely!
283 * Should in here create path transiently, then call
284 * callback, and then do path destroy (if applicable)
285 * without returning in the middle.
287 * FIXME: also need to nicely handle case that this path
288 * extends (lengthens!) an existing path.
290 * @param get_path path of the get request
291 * @param get_path_length lenght of @a get_path
292 * @param put_path path of the put request
293 * @param put_path_length length of the @a put_path
294 * @return a path through the network
296 struct CadetPeerPath *
297 GCPP_path_from_dht (const struct GNUNET_PeerIdentity *get_path,
298 unsigned int get_path_length,
299 const struct GNUNET_PeerIdentity *put_path,
300 unsigned int put_path_length)
302 struct CadetPeerPath *path;
304 path = GNUNET_new (struct CadetPeerPath);
305 path->entries_length = get_path_length + put_path_length;
306 path->entries = GNUNET_new_array (path->entries_length,
307 struct CadetPeerPathEntry);
308 for (unsigned int i=0;i<get_path_length + put_path_length;i++)
310 struct CadetPeerPathEntry *entry = &path->entries[i];
311 const struct GNUNET_PeerIdentity *pid;
313 pid = (i < get_path_length) ? &get_path[get_path_length - i] : &put_path[path->entries_length - i];
314 entry->peer = GCP_get (pid,
317 GCP_path_entry_add (entry->peer,
327 * Destroy a path, we no longer need it.
329 * @param p path to destroy.
332 GCPP_path_destroy (struct CadetPeerPath *path)
334 if (NULL != path->hn)
335 return; /* path was attached, to be kept! */
341 * Return the length of the path. Excludes one end of the
342 * path, so the loopback path has length 0.
344 * @param path path to return the length for
345 * @return number of peers on the path
348 GCPP_get_length (struct CadetPeerPath *path)
350 return path->entries_length;
355 * Find peer's offset on path.
357 * @param path path to search
358 * @param cp peer to look for
359 * @return offset of @a cp on @a path, or UINT_MAX if not found
362 GCPP_find_peer (struct CadetPeerPath *path,
363 struct CadetPeer *cp)
365 for (unsigned int off = 0;
366 off < path->entries_length;
368 if (cp == GCPP_get_peer_at_offset (path,
376 * Obtain the peer at offset @a off in @a path.
378 * @param path peer path to inspect
379 * @param off offset to return, must be smaller than path length
380 * @return the peer at offset @a off
383 GCPP_get_peer_at_offset (struct CadetPeerPath *path,
386 return path->entries[off].peer;
390 /* end of gnunet-service-cadet-new_paths.c */