2 This file is part of GNUnet.
3 (C) 2001 - 2011 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 mesh/mesh_tunnel_tree.c
23 * @brief Tunnel tree handling functions
24 * @author Bartlomiej Polot
28 #include "mesh_tunnel_tree.h"
31 extern GNUNET_PEER_Id myid;
32 extern struct GNUNET_PeerIdentity my_full_id;
38 * @param p the path to invert
41 path_invert (struct MeshPeerPath *path)
46 for (i = 0; i < path->length / 2; i++)
49 path->peers[i] = path->peers[path->length - i - 1];
50 path->peers[path->length - i - 1] = aux;
56 * Destroy the path and free any allocated resources linked to it
58 * @param p the path to destroy
60 * @return GNUNET_OK on success
63 path_destroy (struct MeshPeerPath *p)
65 GNUNET_PEER_decrement_rcs (p->peers, p->length);
66 GNUNET_free (p->peers);
73 * Find the first peer whom to send a packet to go down this path
75 * @param t The tunnel to use
76 * @param peer The peerinfo of the peer we are trying to reach
78 * @return peerinfo of the peer who is the first hop in the tunnel
81 struct GNUNET_PeerIdentity *
82 path_get_first_hop (struct MeshTunnel *t, struct MeshPeerInfo *peer)
84 struct GNUNET_PeerIdentity id;
86 GNUNET_PEER_resolve (peer->id, &id);
87 return GNUNET_CONTAINER_multihashmap_get (t->tree->first_hops,
93 * Get the length of a path
95 * @param path The path to measure, with the local peer at any point of it
97 * @return Number of hops to reach destination
98 * UINT_MAX in case the peer is not in the path
101 path_get_length (struct MeshPeerPath *path)
110 * Get the cost of the path relative to the already built tunnel tree
112 * @param t The tunnel to which compare
113 * @param path The individual path to reach a peer
115 * @return Number of hops to reach destination, UINT_MAX in case the peer is not
118 * TODO: remove dummy implementation, look into the tunnel tree
121 path_get_cost (struct MeshTunnel *t, struct MeshPeerPath *path)
123 return path_get_length (path);
128 * Add the path to the peer and update the path used to reach it in case this
131 * @param peer_info Destination peer to add the path to.
132 * @param path New path to add. Last peer must be the peer in arg 1.
133 * Path will be either used of freed if already known.
135 * TODO: trim the part from origin to us? Add it as path to origin?
138 path_add_to_peer (struct MeshPeerInfo *peer_info, struct MeshPeerPath *path)
140 struct MeshPeerPath *aux;
144 if (NULL == peer_info || NULL == path)
150 l = path_get_length (path);
152 for (aux = peer_info->path_head; aux != NULL; aux = aux->next)
154 l2 = path_get_length (aux);
157 GNUNET_CONTAINER_DLL_insert_before (peer_info->path_head,
158 peer_info->path_tail, aux, path);
162 if (l2 == l && memcmp(path->peers, aux->peers, l) == 0)
169 GNUNET_CONTAINER_DLL_insert_tail (peer_info->path_head, peer_info->path_tail,
176 * Send keepalive packets for a peer
184 path_refresh (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
186 struct MeshTunnel *t = cls;
188 // struct GNUNET_PeerIdentity id;
190 if (tc->reason == GNUNET_SCHEDULER_REASON_SHUTDOWN)
194 /* FIXME implement multicast keepalive. Just an empty multicast packet? */
195 // GNUNET_PEER_resolve (path_get_first_hop (path->t, path->peer)->id, &id);
196 // GNUNET_CORE_notify_transmit_ready (core_handle, 0, 0,
197 // GNUNET_TIME_UNIT_FOREVER_REL, &id,
198 // sizeof (struct GNUNET_MESH_ManipulatePath)
200 // (path->path->length *
201 // sizeof (struct GNUNET_PeerIdentity)),
202 // &send_core_create_path,
204 t->path_refresh_task =
205 GNUNET_SCHEDULER_add_delayed (t->tree->refresh, &path_refresh, t);
212 * Recursively find the given peer in the tree.
214 * @param t Tunnel where to look for the peer.
215 * @param peer Peer to find
217 * @return Pointer to the node of the peer. NULL if not found.
219 struct MeshTunnelPathNode *
220 tunnel_find_peer (struct MeshTunnelPathNode *root, GNUNET_PEER_Id peer_id)
222 struct MeshTunnelPathNode *n;
225 if (root->peer == peer_id)
227 for (i = 0; i < root->nchildren; i++)
229 n = tunnel_find_peer (&root->children[i], peer_id);
238 * Recusively mark peer and children as disconnected, notify client
240 * @param parent Node to be clean, potentially with children
241 * @param nc Notification context to use to alert the client
244 tunnel_mark_peers_disconnected (struct MeshTunnelPathNode *parent,
245 struct GNUNET_SERVER_NotificationContext *nc)
247 struct GNUNET_MESH_PeerControl msg;
250 parent->status = MESH_PEER_RECONNECTING;
251 for (i = 0; i < parent->nchildren; i++)
253 tunnel_mark_peers_disconnected (&parent->children[i], nc);
255 if (NULL == parent->t->client)
257 msg.header.size = htons (sizeof (msg));
258 msg.header.type = htons (GNUNET_MESSAGE_TYPE_MESH_LOCAL_PEER_DEL);
259 msg.tunnel_id = htonl (parent->t->local_tid);
260 GNUNET_PEER_resolve (parent->peer, &msg.peer);
263 GNUNET_SERVER_notification_context_unicast (nc, parent->t->client->handle,
264 &msg.header, GNUNET_NO);
271 * Delete the current path to the peer, including all now unused relays.
272 * The destination peer is NOT destroyed, it is returned in order to either set
273 * a new path to it or destroy it explicitly, taking care of it's child nodes.
275 * @param t Tunnel where to delete the path from.
276 * @param peer Destination peer whose path we want to remove.
277 * @param nc Notification context to alert the client of disconnected peers.
279 * @return pointer to the pathless node, NULL on error
281 struct MeshTunnelPathNode *
282 tunnel_del_path (struct MeshTunnel *t, GNUNET_PEER_Id peer_id,
283 struct GNUNET_SERVER_NotificationContext *nc)
285 struct MeshTunnelPathNode *parent;
286 struct MeshTunnelPathNode *node;
287 struct MeshTunnelPathNode *n;
289 if (peer_id == t->tree->root->peer)
291 node = n = tunnel_find_peer (t->tree->me, peer_id);
296 while (NULL != parent && MESH_PEER_RELAY == parent->status &&
297 1 == parent->nchildren)
300 GNUNET_free (parent->children);
301 parent = parent->parent;
305 *n = parent->children[parent->nchildren - 1];
307 parent->children = GNUNET_realloc (parent->children, parent->nchildren);
309 tunnel_mark_peers_disconnected (node, nc);
316 * Return a newly allocated individual path to reach a peer from the local peer,
317 * according to the path tree of some tunnel.
319 * @param t Tunnel from which to read the path tree
320 * @param peer_info Destination peer to whom we want a path
322 * @return A newly allocated individual path to reach the destination peer.
323 * Path must be destroyed afterwards.
325 struct MeshPeerPath *
326 tunnel_get_path_to_peer(struct MeshTunnel *t, struct MeshPeerInfo *peer_info)
328 struct MeshTunnelPathNode *n;
329 struct MeshPeerPath *p;
330 GNUNET_PEER_Id myid = t->tree->me->peer;
332 n = tunnel_find_peer(t->tree->me, peer_info->id);
333 p = GNUNET_malloc(sizeof(struct MeshPeerPath));
335 /* Building the path (inverted!) */
336 while (n->peer != myid)
338 GNUNET_array_append(p->peers, p->length, n->peer);
339 GNUNET_PEER_change_rc(n->peer, 1);
341 GNUNET_assert(NULL != n);
343 GNUNET_array_append(p->peers, p->length, myid);
344 GNUNET_PEER_change_rc(myid, 1);
353 * Integrate a stand alone path into the tunnel tree.
355 * @param t Tunnel where to add the new path.
356 * @param p Path to be integrated.
357 * @param nc Notification context to alert clients of peers
358 * temporarily disconnected
360 * @return GNUNET_OK in case of success.
361 * GNUNET_SYSERR in case of error.
364 * - go backwards on path looking for each peer in the present tree
365 * - do not disconnect peers until new path is created & connected
368 tunnel_add_path (struct MeshTunnel *t, const struct MeshPeerPath *p)
370 struct MeshTunnelPathNode *parent;
371 struct MeshTunnelPathNode *oldnode;
372 struct MeshTunnelPathNode *n;
373 struct GNUNET_PeerIdentity id;
374 struct GNUNET_PeerIdentity *hop;
375 GNUNET_PEER_Id myid = t->tree->me->peer;
380 GNUNET_assert(0 != p->length);
382 if (n->peer != p->peers[0])
385 return GNUNET_SYSERR;
389 oldnode = tunnel_del_path (t, p->peers[p->length - 1], NULL);
390 /* Look for the first node that is not already present in the tree
392 * Assuming that the tree is somewhat balanced, O(log n * log N).
393 * - Length of the path is expected to be log N (size of whole network).
394 * - Each level of the tree is expected to have log n children (size of tree).
396 for (i = 0, me = -1; i < p->length; i++)
399 if (p->peers[i] == myid)
401 for (j = 0; j < n->nchildren; j++)
403 if (n->children[j].peer == p->peers[i])
409 /* If we couldn't find a child equal to path[i], we have reached the end
410 * of the common path. */
416 /* New path deviates from tree before reaching us. What happened? */
418 return GNUNET_SYSERR;
420 /* Add the rest of the path as a branch from parent. */
421 while (i < p->length)
424 parent->children = GNUNET_realloc (parent->children,
426 sizeof(struct MeshTunnelPathNode));
427 n = &parent->children[parent->nchildren - 1];
428 if (i == p->length - 1 && NULL != oldnode)
430 /* Assignation and free can be misleading, using explicit mempcy */
431 memcpy (n, oldnode, sizeof (struct MeshTunnelPathNode));
432 GNUNET_free (oldnode);
437 n->status = MESH_PEER_RELAY;
438 n->peer = p->peers[i];
445 /* Add info about first hop into hashmap. */
446 if (me < p->length - 1)
448 GNUNET_PEER_resolve (p->peers[p->length - 1], &id);
449 hop = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
450 GNUNET_PEER_resolve (p->peers[me + 1], hop);
451 GNUNET_CONTAINER_multihashmap_put (t->tree->first_hops, &id.hashPubKey,
453 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
460 * Add a peer to a tunnel, accomodating paths accordingly and initializing all
463 * @param t Tunnel we want to add a new peer to
464 * @param peer PeerInfo of the peer being added
468 tunnel_add_peer (struct MeshTunnel *t, struct MeshPeerInfo *peer)
470 struct MeshPeerPath *p;
471 struct MeshPeerPath *best_p;
472 unsigned int best_cost;
475 GNUNET_array_append (peer->tunnels, peer->ntunnels, t);
476 if (NULL == (p = peer->path_head))
480 best_cost = UINT_MAX;
483 if ((cost = path_get_cost (t, p)) < best_cost)
490 tunnel_add_path (t, best_p);
491 if (GNUNET_SCHEDULER_NO_TASK == t->path_refresh_task)
492 t->path_refresh_task =
493 GNUNET_SCHEDULER_add_delayed (t->tree->refresh, &path_refresh, t);