2 This file is part of GNUnet.
3 (C) 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.
23 #include "gnunet_util_lib.h"
25 #include "gnunet-service-mesh_peer.h"
26 #include "gnunet-service-mesh_dht.h"
27 #include "mesh_path.h"
29 /******************************************************************************/
30 /******************************** STRUCTS **********************************/
31 /******************************************************************************/
34 * Struct containing all information regarding a given peer
44 * Last time we heard from this peer
46 struct GNUNET_TIME_Absolute last_contact;
49 * Paths to reach the peer, ordered by ascending hop count
51 struct MeshPeerPath *path_head;
54 * Paths to reach the peer, ordered by ascending hop count
56 struct MeshPeerPath *path_tail;
59 * Handle to stop the DHT search for paths to this peer
61 struct GNUNET_DHT_GetHandle *dhtget;
64 * Tunnel to this peer, if any.
66 struct MeshTunnel2 *tunnel;
69 * Connections that go through this peer, indexed by tid;
71 struct GNUNET_CONTAINER_MultiHashMap *connections;
74 * Handle for queued transmissions
76 struct GNUNET_CORE_TransmitHandle *core_transmit;
79 * Transmission queue to core DLL head
81 struct MeshPeerQueue *queue_head;
84 * Transmission queue to core DLL tail
86 struct MeshPeerQueue *queue_tail;
89 * How many messages are in the queue to this peer.
95 /******************************************************************************/
96 /******************************* GLOBALS ***********************************/
97 /******************************************************************************/
100 * Peers known, indexed by PeerIdentity (MeshPeer).
102 static struct GNUNET_CONTAINER_MultiPeerMap *peers;
105 * How many peers do we want to remember?
107 static unsigned long long max_peers;
110 /******************************************************************************/
111 /******************************** STATIC ***********************************/
112 /******************************************************************************/
115 * Iterator over tunnel hash map entries to destroy the tunnel during shutdown.
118 * @param key current key code
119 * @param value value in the hash map
120 * @return #GNUNET_YES if we should continue to iterate,
124 shutdown_tunnel (void *cls,
125 const struct GNUNET_PeerIdentity *key,
128 struct MeshPeer *p = value;
129 struct MeshTunnel2 *t = p->tunnel;
139 * Destroy the peer_info and free any allocated resources linked to it
141 * @param peer The peer_info to destroy.
143 * @return GNUNET_OK on success
146 peer_destroy (struct MeshPeer *peer)
148 struct GNUNET_PeerIdentity id;
149 struct MeshPeerPath *p;
150 struct MeshPeerPath *nextp;
152 GNUNET_PEER_resolve (peer->id, &id);
153 GNUNET_PEER_change_rc (peer->id, -1);
156 GNUNET_CONTAINER_multipeermap_remove (peers, &id, peer))
159 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
160 "removing peer %s, not in peermap\n", GNUNET_i2s (&id));
162 if (NULL != peer->dhtget)
164 GNUNET_DHT_get_stop (peer->dhtget);
170 GNUNET_CONTAINER_DLL_remove (peer->path_head, peer->path_tail, p);
174 tunnel_destroy_empty (peer->tunnel);
181 * Returns if peer is used (has a tunnel, is neighbor).
183 * @peer Peer to check.
185 * @return GNUNET_YES if peer is in use.
188 peer_is_used (struct MeshPeer *peer)
190 struct MeshPeerPath *p;
192 if (NULL != peer->tunnel)
195 for (p = peer->path_head; NULL != p; p = p->next)
205 * Iterator over all the peers to get the oldest timestamp.
207 * @param cls Closure (unsued).
208 * @param key ID of the peer.
209 * @param value Peer_Info of the peer.
212 peer_get_oldest (void *cls,
213 const struct GNUNET_PeerIdentity *key,
216 struct MeshPeer *p = value;
217 struct GNUNET_TIME_Absolute *abs = cls;
219 /* Don't count active peers */
220 if (GNUNET_YES == peer_is_used (p))
223 if (abs->abs_value_us < p->last_contact.abs_value_us)
224 abs->abs_value_us = p->last_contact.abs_value_us;
231 * Iterator over all the peers to remove the oldest entry.
233 * @param cls Closure (unsued).
234 * @param key ID of the peer.
235 * @param value Peer_Info of the peer.
238 peer_timeout (void *cls,
239 const struct GNUNET_PeerIdentity *key,
242 struct MeshPeer *p = value;
243 struct GNUNET_TIME_Absolute *abs = cls;
245 if (p->last_contact.abs_value_us == abs->abs_value_us &&
246 GNUNET_NO == peer_is_used (p))
256 * Delete oldest unused peer.
259 peer_delete_oldest (void)
261 struct GNUNET_TIME_Absolute abs;
263 abs = GNUNET_TIME_UNIT_FOREVER_ABS;
265 GNUNET_CONTAINER_multipeermap_iterate (peers,
268 GNUNET_CONTAINER_multipeermap_iterate (peers,
275 * Retrieve the MeshPeer stucture associated with the peer, create one
276 * and insert it in the appropriate structures if the peer is not known yet.
278 * @param peer Full identity of the peer.
280 * @return Existing or newly created peer info.
282 static struct MeshPeer *
283 peer_get (const struct GNUNET_PeerIdentity *peer_id)
285 struct MeshPeer *peer;
287 peer = GNUNET_CONTAINER_multipeermap_get (peers, peer_id);
290 peer = GNUNET_new (struct MeshPeer);
291 if (GNUNET_CONTAINER_multipeermap_size (peers) > max_peers)
293 peer_delete_oldest ();
295 GNUNET_CONTAINER_multipeermap_put (peers, peer_id, peer,
296 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
297 peer->id = GNUNET_PEER_intern (peer_id);
299 peer->last_contact = GNUNET_TIME_absolute_get();
306 * Retrieve the MeshPeer stucture associated with the peer, create one
307 * and insert it in the appropriate structures if the peer is not known yet.
309 * @param peer Short identity of the peer.
311 * @return Existing or newly created peer info.
313 static struct MeshPeer *
314 peer_get_short (const GNUNET_PEER_Id peer)
316 return peer_get (GNUNET_PEER_resolve2 (peer));
321 * Get a cost of a path for a peer considering existing tunnel connections.
323 * @param peer Peer towards which the path is considered.
324 * @param path Candidate path.
326 * @return Cost of the path (path length + number of overlapping nodes)
329 peer_get_path_cost (const struct MeshPeer *peer,
330 const struct MeshPeerPath *path)
332 struct MeshConnection *c;
333 unsigned int overlap;
341 GNUNET_assert (NULL != peer->tunnel);
343 for (i = 0; i < path->length; i++)
345 for (c = peer->tunnel->connection_head; NULL != c; c = c->next)
347 for (j = 0; j < c->path->length; j++)
349 if (path->peers[i] == c->path->peers[j])
357 return (path->length + overlap) * (path->score * -1);
362 * Choose the best path towards a peer considering the tunnel properties.
364 * @param peer The destination peer.
366 * @return Best current known path towards the peer, if any.
368 static struct MeshPeerPath *
369 peer_get_best_path (const struct MeshPeer *peer)
371 struct MeshPeerPath *best_p;
372 struct MeshPeerPath *p;
373 struct MeshConnection *c;
374 unsigned int best_cost;
377 best_cost = UINT_MAX;
379 for (p = peer->path_head; NULL != p; p = p->next)
381 for (c = peer->tunnel->connection_head; NULL != c; c = c->next)
385 continue; /* If path is in use in a connection, skip it. */
387 if ((cost = peer_get_path_cost (peer, p)) < best_cost)
398 * Add the path to the peer and update the path used to reach it in case this
401 * @param peer_info Destination peer to add the path to.
402 * @param path New path to add. Last peer must be the peer in arg 1.
403 * Path will be either used of freed if already known.
404 * @param trusted Do we trust that this path is real?
407 peer_add_path (struct MeshPeer *peer_info, struct MeshPeerPath *path,
410 struct MeshPeerPath *aux;
414 if ((NULL == peer_info) || (NULL == path))
420 if (path->peers[path->length - 1] != peer_info->id)
426 if (2 >= path->length && GNUNET_NO == trusted)
428 /* Only allow CORE to tell us about direct paths */
432 for (l = 1; l < path->length; l++)
434 if (path->peers[l] == myid)
436 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "shortening path by %u\n", l);
437 for (l2 = 0; l2 < path->length - l; l2++)
439 path->peers[l2] = path->peers[l + l2];
444 GNUNET_realloc (path->peers, path->length * sizeof (GNUNET_PEER_Id));
448 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "adding path [%u] to peer %s\n",
449 path->length, peer2s (peer_info));
451 l = path_get_length (path);
458 GNUNET_assert (peer_info->id == path->peers[path->length - 1]);
459 for (aux = peer_info->path_head; aux != NULL; aux = aux->next)
461 l2 = path_get_length (aux);
464 GNUNET_CONTAINER_DLL_insert_before (peer_info->path_head,
465 peer_info->path_tail, aux, path);
470 if (l2 == l && memcmp (path->peers, aux->peers, l) == 0)
477 GNUNET_CONTAINER_DLL_insert_tail (peer_info->path_head, peer_info->path_tail,
484 * Add the path to the origin peer and update the path used to reach it in case
485 * this is the shortest.
486 * The path is given in peer_info -> destination, therefore we turn the path
489 * @param peer_info Peer to add the path to, being the origin of the path.
490 * @param path New path to add after being inversed.
491 * Path will be either used or freed.
492 * @param trusted Do we trust that this path is real?
495 peer_add_path_to_origin (struct MeshPeer *peer_info,
496 struct MeshPeerPath *path, int trusted)
501 peer_add_path (peer_info, path, trusted);
505 /******************************************************************************/
506 /******************************** API ***********************************/
507 /******************************************************************************/
510 * Initialize the peer subsystem.
512 * @param c Configuration.
515 GMP_init (const struct GNUNET_CONFIGURATION_Handle *c)
517 peers = GNUNET_CONTAINER_multipeermap_create (128, GNUNET_NO);
519 GNUNET_CONFIGURATION_get_value_number (c, "MESH", "MAX_PEERS",
522 GNUNET_log_config_invalid (GNUNET_ERROR_TYPE_WARNING,
523 "MESH", "MAX_PEERS", "USING DEFAULT");
529 * Shut down the peer subsystem.
534 GNUNET_CONTAINER_multipeermap_iterate (peers, &shutdown_tunnel, NULL);
539 * Try to establish a new connection to this peer in the given tunnel.
540 * If the peer doesn't have any path to it yet, try to get one.
541 * If the peer already has some path, send a CREATE CONNECTION towards it.
543 * @param peer PeerInfo of the peer.
546 GMP_connect (struct MeshPeer *peer)
548 struct MeshTunnel2 *t;
549 struct MeshPeerPath *p;
550 struct MeshConnection *c;
553 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
554 "peer_connect towards %s\n",
558 rerun_dhtget = GNUNET_NO;
560 if (NULL != peer->path_head)
562 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "path exists\n");
563 p = peer_get_best_path (peer);
566 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " %u hops\n", p->length);
567 c = tunnel_use_path (t, p);
570 /* This case can happen when the path includes a first hop that is
571 * not yet known to be connected.
573 * This happens quite often during testing when running mesh
574 * under valgrind: core connect notifications come very late and the
575 * DHT result has already come and created a valid path.
576 * In this case, the peer->connections hashmap will be NULL and
577 * tunnel_use_path will not be able to create a connection from that
580 * Re-running the DHT GET should give core time to callback.
583 rerun_dhtget = GNUNET_YES;
587 send_connection_create (c);
593 if (NULL != peer->dhtget && GNUNET_YES == rerun_dhtget)
595 GNUNET_DHT_get_stop (peer->dhtget);
597 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
598 " Stopping DHT GET for peer %s\n", peer2s (peer));
601 if (NULL == peer->dhtget)
603 const struct GNUNET_PeerIdentity *id;
604 struct GNUNET_HashCode phash;
606 id = GNUNET_PEER_resolve2 (peer->id);
607 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
608 " Starting DHT GET for peer %s\n", peer2s (peer));
609 GNUNET_CRYPTO_hash (&id, sizeof (struct GNUNET_PeerIdentity), &phash);
610 peer->dhtget = GNUNET_DHT_get_start (dht_handle, /* handle */
611 GNUNET_BLOCK_TYPE_MESH_PEER, /* type */
612 &phash, /* key to search */
613 dht_replication_level, /* replication level */
614 GNUNET_DHT_RO_RECORD_ROUTE |
615 GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE,
618 &dht_get_id_handler, peer);
619 if (MESH_TUNNEL_NEW == t->state)
620 tunnel_change_state (t, MESH_TUNNEL_SEARCHING);