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"
34 * @param p the path to invert
37 path_invert (struct MeshPeerPath *path)
42 for (i = 0; i < path->length / 2; i++)
45 path->peers[i] = path->peers[path->length - i - 1];
46 path->peers[path->length - i - 1] = aux;
52 * Destroy the path and free any allocated resources linked to it
54 * @param p the path to destroy
56 * @return GNUNET_OK on success
59 path_destroy (struct MeshPeerPath *p)
61 GNUNET_PEER_decrement_rcs (p->peers, p->length);
62 GNUNET_free (p->peers);
69 * Find the first peer whom to send a packet to go down this path
71 * @param t The tunnel tree to use
72 * @param peer The peerinfo of the peer we are trying to reach
74 * @return peerinfo of the peer who is the first hop in the tunnel
77 struct GNUNET_PeerIdentity *
78 path_get_first_hop (struct MeshTunnelTree *t, GNUNET_PEER_Id peer)
80 struct GNUNET_PeerIdentity id;
82 GNUNET_PEER_resolve (peer, &id);
83 return GNUNET_CONTAINER_multihashmap_get (t->first_hops,
89 * Get the length of a path
91 * @param path The path to measure, with the local peer at any point of it
93 * @return Number of hops to reach destination
94 * UINT_MAX in case the peer is not in the path
97 path_get_length (struct MeshPeerPath *path)
106 * Get the cost of the path relative to the already built tunnel tree
108 * @param t The tunnel tree to which compare
109 * @param path The individual path to reach a peer
111 * @return Number of hops to reach destination, UINT_MAX in case the peer is not
114 * TODO: remove dummy implementation, look into the tunnel tree
117 path_get_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path)
119 return path_get_length (path);
124 * Recursively find the given peer in the tree.
126 * @param t Tunnel where to look for the peer.
127 * @param peer Peer to find
129 * @return Pointer to the node of the peer. NULL if not found.
131 struct MeshTunnelTreeNode *
132 tree_find_peer (struct MeshTunnelTreeNode *root, GNUNET_PEER_Id peer_id)
134 struct MeshTunnelTreeNode *n;
137 if (root->peer == peer_id)
139 for (i = 0; i < root->nchildren; i++)
141 n = tree_find_peer (&root->children[i], peer_id);
150 * Recusively mark peer and children as disconnected, notify client
152 * @param parent Node to be clean, potentially with children
153 * @param cb Callback to use to notify about disconnected peers.
156 tree_mark_peers_disconnected (struct MeshTunnelTreeNode *parent,
157 MeshNodeDisconnectCB cb)
161 if (MESH_PEER_READY == parent->status)
165 parent->status = MESH_PEER_RECONNECTING;
166 for (i = 0; i < parent->nchildren; i++)
168 tree_mark_peers_disconnected (&parent->children[i], cb);
170 // struct GNUNET_MESH_PeerControl msg;
171 // if (NULL == parent->t->client)
173 // msg.header.size = htons (sizeof (msg));
174 // msg.header.type = htons (GNUNET_MESSAGE_TYPE_MESH_LOCAL_PEER_DEL);
175 // msg.tunnel_id = htonl (parent->t->local_tid);
176 // GNUNET_PEER_resolve (parent->peer, &msg.peer);
179 // GNUNET_SERVER_notification_context_unicast (nc, parent->t->client->handle,
180 // &msg.header, GNUNET_NO);
187 * Delete the current path to the peer, including all now unused relays.
188 * The destination peer is NOT destroyed, it is returned in order to either set
189 * a new path to it or destroy it explicitly, taking care of it's child nodes.
191 * @param t Tunnel tree where to delete the path from.
192 * @param peer Destination peer whose path we want to remove.
193 * @param cb Callback to use to notify about disconnected peers.
195 * @return pointer to the pathless node, NULL on error
197 struct MeshTunnelTreeNode *
198 tree_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id,
199 MeshNodeDisconnectCB cb)
201 struct MeshTunnelTreeNode *parent;
202 struct MeshTunnelTreeNode *node;
203 struct MeshTunnelTreeNode *n;
205 if (peer_id == t->root->peer)
207 node = n = tree_find_peer (t->me, peer_id);
212 while (NULL != parent && MESH_PEER_RELAY == parent->status &&
213 1 == parent->nchildren)
216 GNUNET_free (parent->children);
217 parent = parent->parent;
221 *n = parent->children[parent->nchildren - 1];
223 parent->children = GNUNET_realloc (parent->children, parent->nchildren);
225 tree_mark_peers_disconnected (node, cb);
232 * Return a newly allocated individual path to reach a peer from the local peer,
233 * according to the path tree of some tunnel.
235 * @param t Tunnel from which to read the path tree
236 * @param peer_info Destination peer to whom we want a path
238 * @return A newly allocated individual path to reach the destination peer.
239 * Path must be destroyed afterwards.
241 struct MeshPeerPath *
242 tree_get_path_to_peer(struct MeshTunnelTree *t, GNUNET_PEER_Id peer)
244 struct MeshTunnelTreeNode *n;
245 struct MeshPeerPath *p;
246 GNUNET_PEER_Id myid = t->me->peer;
248 n = tree_find_peer(t->me, peer);
249 p = GNUNET_malloc(sizeof(struct MeshPeerPath));
251 /* Building the path (inverted!) */
252 while (n->peer != myid)
254 GNUNET_array_append(p->peers, p->length, n->peer);
255 GNUNET_PEER_change_rc(n->peer, 1);
257 GNUNET_assert(NULL != n);
259 GNUNET_array_append(p->peers, p->length, myid);
260 GNUNET_PEER_change_rc(myid, 1);
269 * Integrate a stand alone path into the tunnel tree.
271 * @param t Tunnel where to add the new path.
272 * @param p Path to be integrated.
273 * @param cb Callback to use to notify about peers temporarily disconnecting
275 * @return GNUNET_OK in case of success.
276 * GNUNET_SYSERR in case of error.
279 * - go backwards on path looking for each peer in the present tree
280 * - do not disconnect peers until new path is created & connected
283 tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p,
284 MeshNodeDisconnectCB cb)
286 struct MeshTunnelTreeNode *parent;
287 struct MeshTunnelTreeNode *oldnode;
288 struct MeshTunnelTreeNode *n;
289 struct GNUNET_PeerIdentity id;
290 struct GNUNET_PeerIdentity *hop;
291 GNUNET_PEER_Id myid = t->me->peer;
296 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
297 "test: Adding path [%u] towards peer %u to peer %u.\n",
299 p->peers[p->length - 1],
301 GNUNET_assert(0 != p->length);
302 parent = n = t->root;
303 if (n->peer != p->peers[0])
306 return GNUNET_SYSERR;
310 oldnode = tree_del_path (t, p->peers[p->length - 1], cb);
311 /* Look for the first node that is not already present in the tree
313 * Assuming that the tree is somewhat balanced, O(log n * log N).
314 * - Length of the path is expected to be log N (size of whole network).
315 * - Each level of the tree is expected to have log n children (size of tree).
317 me = t->root->peer == myid ? 0 : -1;
318 for (i = 1; i < p->length; i++)
320 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
321 "test: Looking for peer %u.\n",
324 if (p->peers[i] == myid)
326 for (j = 0; j < n->nchildren; j++)
328 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
329 "test: Child %u. is %u\n",
331 n->children[j].peer);
332 if (n->children[j].peer == p->peers[i])
338 /* If we couldn't find a child equal to path[i], we have reached the end
339 * of the common path. */
343 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
344 "test: All childen visited.\n");
347 /* New path deviates from tree before reaching us. What happened? */
349 return GNUNET_SYSERR;
351 /* Add the rest of the path as a branch from parent. */
352 while (i < p->length)
354 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
355 "test: Adding peer %u, to %u.\n",
359 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
360 "test: realloc %p, %u\n", parent->children,
362 sizeof(struct MeshTunnelTreeNode));
363 parent->children = GNUNET_realloc (parent->children,
365 sizeof(struct MeshTunnelTreeNode));
366 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
367 "test: done: %p\n", parent->children);
368 n = &parent->children[parent->nchildren - 1];
369 if (i == p->length - 1 && NULL != oldnode)
371 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
372 "test: Putting old note into place.\n");
373 /* Assignation and free can be misleading, using explicit mempcy */
374 memcpy (n, oldnode, sizeof (struct MeshTunnelTreeNode));
375 tree_node_destroy(oldnode);
379 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
380 "test: Creating new node.\n");
382 n->status = MESH_PEER_RELAY;
383 n->peer = p->peers[i];
391 n->status = MESH_PEER_SEARCHING;
393 /* Add info about first hop into hashmap. */
394 if (me < p->length - 1)
396 GNUNET_PEER_resolve (p->peers[p->length - 1], &id);
397 hop = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
398 GNUNET_PEER_resolve (p->peers[me + 1], hop);
399 GNUNET_CONTAINER_multihashmap_put (t->first_hops, &id.hashPubKey,
401 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
408 * Destroy the node and all children
410 * @param n Parent node to be destroyed
413 tree_node_destroy (struct MeshTunnelTreeNode *n)
417 if (n->nchildren == 0) return;
418 for (i = 0; i < n->nchildren; i++)
420 tree_node_destroy(&n->children[i]);
422 GNUNET_free(n->children);
427 * Iterator over hash map peer entries and frees all data in it.
428 * Used prior to destroying a hashmap. Makes you miss anonymous functions in C.
431 * @param key current key code (will no longer contain valid data!!)
432 * @param value value in the hash map (treated as void *)
433 * @return GNUNET_YES if we should continue to iterate, GNUNET_NO if not.
436 iterate_free (void *cls, const GNUNET_HashCode * key, void *value)
444 * Destroy the whole tree and free all used memory and Peer_Ids
446 * @param t Tree to be destroyed
449 tree_destroy (struct MeshTunnelTree *t)
451 tree_node_destroy(t->root);
452 GNUNET_free(t->root);
453 GNUNET_CONTAINER_multihashmap_iterate(t->first_hops, &iterate_free, NULL);
454 GNUNET_CONTAINER_multihashmap_destroy(t->first_hops);