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    * Tunnel this node belongs to (and therefore tree)
  65    */
  66   struct MeshTunnel *t;
  67
  68   /**
  69    * Peer this node describes
  70    */
  71   GNUNET_PEER_Id peer;
  72
  73   /**
  74    * Parent node in the tree
  75    */
  76   struct MeshTunnelTreeNode *parent;
  77
  78   /**
  79    * DLL of siblings
  80    */
  81   struct MeshTunnelTreeNode *next;
  82
  83   /**
  84    * DLL of siblings
  85    */
  86   struct MeshTunnelTreeNode *prev;
  87
  88   /**
  89    * DLL of children
  90    */
  91   struct MeshTunnelTreeNode *children_head;
  92
  93   /**
  94    * DLL of children
  95    */
  96   struct MeshTunnelTreeNode *children_tail;
  97
  98     /**
  99      * Status of the peer in the tunnel
 100      */
 101   enum MeshPeerState status;
 102 };
 103
 104
 105 /**
 106  * Tree to reach all peers in the tunnel
 107  */
 108 struct MeshTunnelTree
 109 {
 110   /**
 111    * How often to refresh the path
 112    */
 113   struct GNUNET_TIME_Relative refresh;
 114
 115   /**
 116    * Tunnel this path belongs to
 117    */
 118   struct MeshTunnel *t;
 119
 120   /**
 121    * Root node of peer tree
 122    */
 123   struct MeshTunnelTreeNode *root;
 124
 125   /**
 126    * Node that represents our position in the tree (for non local tunnels)
 127    */
 128   struct MeshTunnelTreeNode *me;
 129
 130   /**
 131    * DLL of disconneted nodes
 132    */
 133   struct MeshTunnelTreeNode *disconnected_head;
 134
 135   /**
 136    * DLL of disconneted nodes
 137    */
 138   struct MeshTunnelTreeNode *disconnected_tail;
 139
 140   /**
 141    * Cache of all peers and the first hop to them.
 142    * Indexed by PeerIdentity, contains a pointer to the PeerIdentity
 143    * of 1st hop.
 144    */
 145   struct GNUNET_CONTAINER_MultiHashMap *first_hops;
 146
 147 };
 148
 149
 150 /******************************************************************************/
 151 /*************************        FUNCTIONS       *****************************/
 152 /******************************************************************************/
 153
 154 /**
 155  * Create a new path
 156  *
 157  * @param lenght How many hops will the path have.
 158  *
 159  * @return A newly allocated path with a peer array of the specified length.
 160  */
 161 struct MeshPeerPath *
 162 path_new (unsigned int length);
 163
 164
 165 /**
 166  * Invert the path
 167  *
 168  * @param p the path to invert
 169  */
 170 void
 171 path_invert (struct MeshPeerPath *p);
 172
 173
 174 /**
 175  * Find the first peer whom to send a packet to go down this path
 176  *
 177  * @param t The tunnel tree to use
 178  * @param peer The peerinfo of the peer we are trying to reach
 179  *
 180  * @return peerinfo of the peer who is the first hop in the tunnel
 181  *         NULL on error
 182  */
 183 struct GNUNET_PeerIdentity *
 184 path_get_first_hop (struct MeshTunnelTree *t,
 185                     GNUNET_PEER_Id peer);
 186
 187
 188 /**
 189  * Get the length of a path
 190  *
 191  * @param p The path to measure, with the local peer at any point of it
 192  *
 193  * @return Number of hops to reach destination
 194  *         UINT_MAX in case the peer is not in the path
 195  */
 196 unsigned int
 197 path_get_length (struct MeshPeerPath *p);
 198
 199
 200 /**
 201  * Get the cost of the path relative to the already built tunnel tree
 202  *
 203  * @param t The tunnel tree to which compare
 204  * @param path The individual path to reach a peer
 205  *
 206  * @return Number of hops to reach destination, UINT_MAX in case the peer is not
 207  * in the path
 208  */
 209 unsigned int
 210 path_get_cost (struct MeshTunnelTree *t,
 211                struct MeshPeerPath *path);
 212
 213
 214 /**
 215  * Destroy the path and free any allocated resources linked to it
 216  *
 217  * @param p the path to destroy
 218  *
 219  * @return GNUNET_OK on success
 220  */
 221 int
 222 path_destroy (struct MeshPeerPath *p);
 223
 224
 225 /******************************************************************************/
 226
 227 /**
 228  * Method called whenever a node has been marked as disconnected.
 229  *
 230  * @param node peer identity the tunnel stopped working with
 231  */
 232 typedef void (*MeshNodeDisconnectCB) (const struct MeshTunnelTreeNode * node);
 233
 234
 235 /**
 236  * Create a new tunnel tree associated to a tunnel
 237  *
 238  * @param t Tunnel this tree will represent
 239  * @param peer A short peer id of the root of the tree
 240  *
 241  * @return A newly allocated and initialized tunnel tree
 242  */
 243 struct MeshTunnelTree *
 244 tree_new (struct MeshTunnel *t, GNUNET_PEER_Id peer);
 245
 246
 247 /**
 248  * Recursively find the given peer in the tree.
 249  *
 250  * @param parent Parent node where to start looking.
 251  * @param peer Short ID of peer to find.
 252  *
 253  * @return Pointer to the node of the peer. NULL if not found.
 254  */
 255 struct MeshTunnelTreeNode *
 256 tree_find_peer (struct MeshTunnelTreeNode *parent,
 257                 GNUNET_PEER_Id peer);
 258
 259
 260 /**
 261  * Delete the current path to the peer, including all now unused relays.
 262  * The destination peer is NOT destroyed, it is returned in order to either set
 263  * a new path to it or destroy it explicitly, taking care of it's child nodes.
 264  *
 265  * @param t Tunnel tree where to delete the path from.
 266  * @param peer Destination peer whose path we want to remove.
 267  * @param cb Callback to use to notify about which peers are going to be
 268  *           disconnected.
 269  *
 270  * @return pointer to the pathless node.
 271  *         NULL when not found
 272  */
 273 struct MeshTunnelTreeNode *
 274 tree_del_path (struct MeshTunnelTree *t,
 275                GNUNET_PEER_Id peer,
 276                MeshNodeDisconnectCB cb);
 277
 278
 279 /**
 280  * Return a newly allocated individual path to reach a peer from the local peer,
 281  * according to the path tree of some tunnel.
 282  *
 283  * @param t Tunnel from which to read the path tree
 284  * @param peer Destination peer to whom we want a path
 285  *
 286  * @return A newly allocated individual path to reach the destination peer.
 287  *         Path must be destroyed afterwards.
 288  */
 289 struct MeshPeerPath *
 290 tree_get_path_to_peer(struct MeshTunnelTree *t,
 291                       GNUNET_PEER_Id peer);
 292
 293
 294 /**
 295  * Integrate a stand alone path into the tunnel tree.
 296  *
 297  * @param t Tunnel where to add the new path.
 298  * @param p Path to be integrated.
 299  * @param cb Callback to use to notify about peers temporarily disconnecting
 300  *
 301  * @return GNUNET_OK in case of success.
 302  *         GNUNET_SYSERR in case of error.
 303  */
 304 int
 305 tree_add_path (struct MeshTunnelTree *t,
 306                const struct MeshPeerPath *p,
 307                MeshNodeDisconnectCB cb);
 308
 309
 310 /**
 311  * Notifies a tree that a connection it might be using is broken.
 312  * Marks all peers down the paths as disconnected and notifies the client.
 313  *
 314  * @param t Tree to use.
 315  * @param p1 Short id of one of the peers (order unimportant)
 316  * @param p2 Short id of one of the peers (order unimportant)
 317  * @param cb Function to call for every peer that is marked as disconnected.
 318  *
 319  * @return Short ID of the first disconnected peer in the tree.
 320  */
 321 GNUNET_PEER_Id
 322 tree_notify_connection_broken (struct MeshTunnelTree *t,
 323                                GNUNET_PEER_Id p1,
 324                                GNUNET_PEER_Id p2,
 325                                MeshNodeDisconnectCB cb);
 326
 327
 328 /**
 329  * Print the tree on stderr
 330  *
 331  * @param t The tree
 332  */
 333 void
 334 tree_debug(struct MeshTunnelTree *t);
 335
 336
 337 /**
 338  * Destroy the whole tree and free all used memory and Peer_Ids
 339  *
 340  * @param t Tree to be destroyed
 341  */
 342 void
 343 tree_destroy (struct MeshTunnelTree *t);