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  * Duplicate a path, incrementing short peer's rc.
 176  *
 177  * @param p The path to duplicate.
 178  */
 179 struct MeshPeerPath *
 180 path_duplicate (struct MeshPeerPath *path);
 181
 182
 183 /**
 184  * Find the first peer whom to send a packet to go down this path
 185  *
 186  * @param t The tunnel tree to use
 187  * @param peer The peerinfo of the peer we are trying to reach
 188  *
 189  * @return peerinfo of the peer who is the first hop in the tunnel
 190  *         NULL on error
 191  */
 192 struct GNUNET_PeerIdentity *
 193 path_get_first_hop (struct MeshTunnelTree *t,
 194                     GNUNET_PEER_Id peer);
 195
 196
 197 /**
 198  * Get the length of a path
 199  *
 200  * @param p The path to measure, with the local peer at any point of it
 201  *
 202  * @return Number of hops to reach destination
 203  *         UINT_MAX in case the peer is not in the path
 204  */
 205 unsigned int
 206 path_get_length (struct MeshPeerPath *p);
 207
 208
 209 /**
 210  * Get the cost of the path relative to the already built tunnel tree
 211  *
 212  * @param t The tunnel tree to which compare
 213  * @param path The individual path to reach a peer
 214  *
 215  * @return Number of hops to reach destination, UINT_MAX in case the peer is not
 216  * in the path
 217  */
 218 unsigned int
 219 path_get_cost (struct MeshTunnelTree *t,
 220                struct MeshPeerPath *path);
 221
 222
 223 /**
 224  * Destroy the path and free any allocated resources linked to it
 225  *
 226  * @param p the path to destroy
 227  *
 228  * @return GNUNET_OK on success
 229  */
 230 int
 231 path_destroy (struct MeshPeerPath *p);
 232
 233
 234 /******************************************************************************/
 235
 236 /**
 237  * Method called whenever a node has been marked as disconnected.
 238  *
 239  * @param node peer identity the tunnel stopped working with
 240  */
 241 typedef void (*MeshNodeDisconnectCB) (const struct MeshTunnelTreeNode * node);
 242
 243
 244 /**
 245  * Create a new tunnel tree associated to a tunnel
 246  *
 247  * @param t Tunnel this tree will represent
 248  * @param peer A short peer id of the root of the tree
 249  *
 250  * @return A newly allocated and initialized tunnel tree
 251  */
 252 struct MeshTunnelTree *
 253 tree_new (struct MeshTunnel *t, GNUNET_PEER_Id peer);
 254
 255
 256 /**
 257  * Recursively find the given peer in the tree.
 258  *
 259  * @param parent Parent node where to start looking.
 260  * @param peer Short ID of peer to find.
 261  *
 262  * @return Pointer to the node of the peer. NULL if not found.
 263  */
 264 struct MeshTunnelTreeNode *
 265 tree_find_peer (struct MeshTunnelTreeNode *parent,
 266                 GNUNET_PEER_Id peer);
 267
 268
 269 /**
 270  * Delete the current path to the peer, including all now unused relays.
 271  * The destination peer is NOT destroyed, it is returned in order to either set
 272  * a new path to it or destroy it explicitly, taking care of it's child nodes.
 273  *
 274  * @param t Tunnel tree where to delete the path from.
 275  * @param peer Destination peer whose path we want to remove.
 276  * @param cb Callback to use to notify about which peers are going to be
 277  *           disconnected.
 278  *
 279  * @return pointer to the pathless node.
 280  *         NULL when not found
 281  */
 282 struct MeshTunnelTreeNode *
 283 tree_del_path (struct MeshTunnelTree *t,
 284                GNUNET_PEER_Id peer,
 285                MeshNodeDisconnectCB cb);
 286
 287
 288 /**
 289  * Return a newly allocated individual path to reach a peer from the local peer,
 290  * according to the path tree of some tunnel.
 291  *
 292  * @param t Tunnel from which to read the path tree
 293  * @param peer Destination peer to whom we want a path
 294  *
 295  * @return A newly allocated individual path to reach the destination peer.
 296  *         Path must be destroyed afterwards.
 297  */
 298 struct MeshPeerPath *
 299 tree_get_path_to_peer(struct MeshTunnelTree *t,
 300                       GNUNET_PEER_Id peer);
 301
 302
 303 /**
 304  * Integrate a stand alone path into the tunnel tree.
 305  *
 306  * @param t Tunnel where to add the new path.
 307  * @param p Path to be integrated.
 308  * @param cb Callback to use to notify about peers temporarily disconnecting
 309  *
 310  * @return GNUNET_OK in case of success.
 311  *         GNUNET_SYSERR in case of error.
 312  */
 313 int
 314 tree_add_path (struct MeshTunnelTree *t,
 315                const struct MeshPeerPath *p,
 316                MeshNodeDisconnectCB cb);
 317
 318
 319 /**
 320  * Notifies a tree that a connection it might be using is broken.
 321  * Marks all peers down the paths as disconnected and notifies the client.
 322  *
 323  * @param t Tree to use.
 324  * @param p1 Short id of one of the peers (order unimportant)
 325  * @param p2 Short id of one of the peers (order unimportant)
 326  * @param cb Function to call for every peer that is marked as disconnected.
 327  *
 328  * @return Short ID of the first disconnected peer in the tree.
 329  */
 330 GNUNET_PEER_Id
 331 tree_notify_connection_broken (struct MeshTunnelTree *t,
 332                                GNUNET_PEER_Id p1,
 333                                GNUNET_PEER_Id p2,
 334                                MeshNodeDisconnectCB cb);
 335
 336
 337 /**
 338  * Print the tree on stderr
 339  *
 340  * @param t The tree
 341  */
 342 void
 343 tree_debug(struct MeshTunnelTree *t);
 344
 345
 346 /**
 347  * Destroy the whole tree and free all used memory and Peer_Ids
 348  *
 349  * @param t Tree to be destroyed
 350  */
 351 void
 352 tree_destroy (struct MeshTunnelTree *t);