src/mesh/mesh_tunnel_tree.h

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2001 - 2011 Christian Grothoff (and other contributing authors)
   4
   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.
   9
  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.
  14
  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.
  19 */
  20
  21 /**
  22  * @file mesh/mesh_tree_tree.h
  23  * @brief Tunnel tree handling functions
  24  * @author Bartlomiej Polot
  25  */
  26
  27 #include "mesh.h"
  28
  29 /******************************************************************************/
  30 /************************      DATA STRUCTURES     ****************************/
  31 /******************************************************************************/
  32
  33 /**
  34  * Information regarding a possible path to reach a single peer
  35  */
  36 struct MeshPeerPath
  37 {
  38
  39     /**
  40      * Linked list
  41      */
  42   struct MeshPeerPath *next;
  43   struct MeshPeerPath *prev;
  44
  45     /**
  46      * List of all the peers that form the path from origin to target.
  47      */
  48   GNUNET_PEER_Id *peers;
  49
  50     /**
  51      * Number of peers (hops) in the path
  52      */
  53   unsigned int length;
  54
  55 };
  56
  57
  58 /**
  59  * Node of path tree for a tunnel
  60  */
  61 struct MeshTunnelTreeNode;
  62
  63
  64 /**
  65  * Tree to reach all peers in the tunnel
  66  */
  67 struct MeshTunnelTree;
  68
  69
  70 /******************************************************************************/
  71 /*************************        FUNCTIONS       *****************************/
  72 /******************************************************************************/
  73
  74 /**
  75  * Create a new path
  76  *
  77  * @param lenght How many hops will the path have.
  78  *
  79  * @return A newly allocated path with a peer array of the specified length.
  80  */
  81 struct MeshPeerPath *
  82 path_new (unsigned int length);
  83
  84
  85 /**
  86  * Invert the path
  87  *
  88  * @param p the path to invert
  89  */
  90 void
  91 path_invert (struct MeshPeerPath *p);
  92
  93
  94 /**
  95  * Duplicate a path, incrementing short peer's rc.
  96  *
  97  * @param p The path to duplicate.
  98  */
  99 struct MeshPeerPath *
 100 path_duplicate (struct MeshPeerPath *path);
 101
 102
 103 /**
 104  * Find the first peer whom to send a packet to go down this path
 105  *
 106  * @param t The tunnel tree to use
 107  * @param peer The peerinfo of the peer we are trying to reach
 108  *
 109  * @return peerinfo of the peer who is the first hop in the tunnel
 110  *         NULL on error
 111  */
 112 struct GNUNET_PeerIdentity *
 113 path_get_first_hop (struct MeshTunnelTree *t, GNUNET_PEER_Id peer);
 114
 115
 116 /**
 117  * Get the length of a path
 118  *
 119  * @param p The path to measure, with the local peer at any point of it
 120  *
 121  * @return Number of hops to reach destination
 122  *         UINT_MAX in case the peer is not in the path
 123  */
 124 unsigned int
 125 path_get_length (struct MeshPeerPath *p);
 126
 127
 128 /**
 129  * Get the cost of the path relative to the already built tunnel tree
 130  *
 131  * @param t The tunnel tree to which compare
 132  * @param path The individual path to reach a peer
 133  *
 134  * @return Number of hops to reach destination, UINT_MAX in case the peer is not
 135  * in the path
 136  */
 137 unsigned int
 138 path_get_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path);
 139
 140
 141 /**
 142  * Destroy the path and free any allocated resources linked to it
 143  *
 144  * @param p the path to destroy
 145  *
 146  * @return GNUNET_OK on success
 147  */
 148 int
 149 path_destroy (struct MeshPeerPath *p);
 150
 151
 152 /******************************************************************************/
 153
 154 /**
 155  * Method called whenever a node has been marked as disconnected.
 156  *
 157  * @param cls Closure.
 158  * @param peer_id short ID of peer that is no longer reachable.
 159  */
 160 typedef void (*MeshTreeCallback) (void *cls, GNUNET_PEER_Id peer_id);
 161
 162
 163 /**
 164  * Create a new tunnel tree associated to a tunnel
 165  *
 166  * @param peer A short peer id of the root of the tree
 167  *
 168  * @return A newly allocated and initialized tunnel tree
 169  */
 170 struct MeshTunnelTree *
 171 tree_new (GNUNET_PEER_Id peer);
 172
 173
 174 /**
 175  * Set own identity in the tree
 176  *
 177  * @param tree Tree.
 178  * @param peer A short peer id of local peer.
 179  */
 180 void
 181 tree_set_me (struct MeshTunnelTree *tree, GNUNET_PEER_Id peer);
 182
 183
 184 /**
 185  * Get the id of the local id of the tree.
 186  *
 187  * @param tree Tree whose local id we want to now.
 188  *
 189  * @return Short peer id of local peer.
 190  */
 191 GNUNET_PEER_Id
 192 tree_get_me (struct MeshTunnelTree *tree);
 193
 194
 195 /**
 196  * Set the status of a node.
 197  *
 198  * @param tree Tree.
 199  * @param peer A short peer id of local peer.
 200  */
 201 void
 202 tree_set_status (struct MeshTunnelTree *tree, GNUNET_PEER_Id peer,
 203                  enum MeshPeerState status);
 204
 205
 206 /**
 207  * Get the status of a node.
 208  *
 209  * @param tree Tree whose local id we want to now.
 210  *
 211  * @return Short peer id of local peer.
 212  */
 213 enum MeshPeerState
 214 tree_get_status (struct MeshTunnelTree *tree, GNUNET_PEER_Id peer);
 215
 216
 217 /**
 218  * Get the id of the predecessor of the local node.
 219  *
 220  * @param tree Tree whose local id we want to now.
 221  *
 222  * @return Short peer id of local peer.
 223  */
 224 GNUNET_PEER_Id
 225 tree_get_predecessor (struct MeshTunnelTree *tree);
 226
 227
 228 /**
 229  * Find the given peer in the tree.
 230  *
 231  * @param tree Tree where to look for the peer.
 232  * @param peer Peer to find.
 233  *
 234  * @return Pointer to the node of the peer. NULL if not found.
 235  */
 236 struct MeshTunnelTreeNode *
 237 tree_find_peer (struct MeshTunnelTree *tree, GNUNET_PEER_Id peer_id);
 238
 239
 240 /**
 241  * Iterate over all children of the local node.
 242  *
 243  * @param tree Tree to use. Must have "me" set.
 244  * @param cb Callback to call over each child.
 245  * @param cls Closure.
 246  */
 247 void
 248 tree_iterate_children (struct MeshTunnelTree *tree, MeshTreeCallback cb,
 249                        void *cls);
 250
 251
 252 /**
 253  * Recusively update the info about what is the first hop to reach the node
 254  *
 255  * @param tree Tree this nodes belongs to.
 256  * @param parent_id Short ID from node form which to start updating.
 257  * @param hop If known, ID of the first hop.
 258  *            If not known, NULL to find out and pass on children.
 259  */
 260 void
 261 tree_update_first_hops (struct MeshTunnelTree *tree, GNUNET_PEER_Id parent_id,
 262                         struct GNUNET_PeerIdentity *hop);
 263
 264 /**
 265  * Delete the current path to the peer, including all now unused relays.
 266  * The destination peer is NOT destroyed, it is returned in order to either set
 267  * a new path to it or destroy it explicitly, taking care of it's child nodes.
 268  *
 269  * @param t Tunnel tree where to delete the path from.
 270  * @param peer Destination peer whose path we want to remove.
 271  * @param cb Callback to use to notify about which peers are going to be
 272  *           disconnected.
 273  * @param cbcls Closure for cb.
 274  *
 275  * @return pointer to the pathless node.
 276  *         NULL when not found
 277  */
 278 struct MeshTunnelTreeNode *
 279 tree_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer,
 280                MeshTreeCallback cb, void *cbcls);
 281
 282
 283 /**
 284  * Return a newly allocated individual path to reach a peer from the local peer,
 285  * according to the path tree of some tunnel.
 286  *
 287  * @param t Tunnel from which to read the path tree
 288  * @param peer Destination peer to whom we want a path
 289  *
 290  * @return A newly allocated individual path to reach the destination peer.
 291  *         Path must be destroyed afterwards.
 292  */
 293 struct MeshPeerPath *
 294 tree_get_path_to_peer (struct MeshTunnelTree *t, GNUNET_PEER_Id peer);
 295
 296
 297 /**
 298  * Integrate a stand alone path into the tunnel tree.
 299  *
 300  * @param t Tunnel where to add the new path.
 301  * @param p Path to be integrated.
 302  * @param cb Callback to use to notify about peers temporarily disconnecting.
 303  * @param cbcls Closure for cb.
 304  *
 305  * @return GNUNET_OK in case of success.
 306  *         GNUNET_SYSERR in case of error.
 307  */
 308 int
 309 tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p,
 310                MeshTreeCallback cb, void *cbcls);
 311
 312
 313 /**
 314  * Notifies a tree that a connection it might be using is broken.
 315  * Marks all peers down the paths as disconnected and notifies the client.
 316  *
 317  * @param t Tree to use.
 318  * @param p1 Short id of one of the peers (order unimportant)
 319  * @param p2 Short id of one of the peers (order unimportant)
 320  * @param cb Function to call for every peer that is marked as disconnected.
 321  * @param cbcls Closure for cb.
 322  *
 323  * @return Short ID of the first disconnected peer in the tree.
 324  */
 325 GNUNET_PEER_Id
 326 tree_notify_connection_broken (struct MeshTunnelTree *t, GNUNET_PEER_Id p1,
 327                                GNUNET_PEER_Id p2, MeshTreeCallback cb,
 328                                void *cbcls);
 329
 330
 331 /**
 332  * Deletes a peer from a tunnel, liberating all unused resources on the path to
 333  * it. It shouldn't have children, if it has they will be destroyed as well.
 334  * If the tree is not local and no longer has any paths, the root node will be
 335  * destroyed and marked as NULL.
 336  *
 337  * @param t Tunnel tree to use.
 338  * @param peer Short ID of the peer to remove from the tunnel tree.
 339  * @param cb Callback to notify client of disconnected peers.
 340  * @param cbcls Closure for cb.
 341  *
 342  * @return GNUNET_YES if the tunnel still has nodes
 343  */
 344 int
 345 tree_del_peer (struct MeshTunnelTree *t, GNUNET_PEER_Id peer,
 346                MeshTreeCallback cb, void *cbcls);
 347
 348 /**
 349  * Print the tree on stderr
 350  *
 351  * @param t The tree
 352  */
 353 void
 354 tree_debug (struct MeshTunnelTree *t);
 355
 356
 357 /**
 358  * Destroy the whole tree and free all used memory and Peer_Ids
 359  *
 360  * @param t Tree to be destroyed
 361  */
 362 void
 363 tree_destroy (struct MeshTunnelTree *t);