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    * Cache of all peers and the first hop to them.
 132    * Indexed by PeerIdentity, contains a pointer to the PeerIdentity
 133    * of 1st hop.
 134    */
 135   struct GNUNET_CONTAINER_MultiHashMap *first_hops;
 136
 137 };
 138
 139
 140 /******************************************************************************/
 141 /*************************        FUNCTIONS       *****************************/
 142 /******************************************************************************/
 143
 144 /**
 145  * Create a new path
 146  *
 147  * @param lenght How many hops will the path have.
 148  *
 149  * @return A newly allocated path with a peer array of the specified length.
 150  */
 151 struct MeshPeerPath *
 152 path_new (unsigned int length);
 153
 154
 155 /**
 156  * Invert the path
 157  *
 158  * @param p the path to invert
 159  */
 160 void
 161 path_invert (struct MeshPeerPath *p);
 162
 163
 164 /**
 165  * Find the first peer whom to send a packet to go down this path
 166  *
 167  * @param t The tunnel tree to use
 168  * @param peer The peerinfo of the peer we are trying to reach
 169  *
 170  * @return peerinfo of the peer who is the first hop in the tunnel
 171  *         NULL on error
 172  */
 173 struct GNUNET_PeerIdentity *
 174 path_get_first_hop (struct MeshTunnelTree *t,
 175                     GNUNET_PEER_Id peer);
 176
 177
 178 /**
 179  * Get the length of a path
 180  *
 181  * @param p The path to measure, with the local peer at any point of it
 182  *
 183  * @return Number of hops to reach destination
 184  *         UINT_MAX in case the peer is not in the path
 185  */
 186 unsigned int
 187 path_get_length (struct MeshPeerPath *p);
 188
 189
 190 /**
 191  * Get the cost of the path relative to the already built tunnel tree
 192  *
 193  * @param t The tunnel tree to which compare
 194  * @param path The individual path to reach a peer
 195  *
 196  * @return Number of hops to reach destination, UINT_MAX in case the peer is not
 197  * in the path
 198  */
 199 unsigned int
 200 path_get_cost (struct MeshTunnelTree *t,
 201                struct MeshPeerPath *path);
 202
 203
 204 /**
 205  * Destroy the path and free any allocated resources linked to it
 206  *
 207  * @param p the path to destroy
 208  *
 209  * @return GNUNET_OK on success
 210  */
 211 int
 212 path_destroy (struct MeshPeerPath *p);
 213
 214
 215 /******************************************************************************/
 216
 217 /**
 218  * Method called whenever a node has been marked as disconnected.
 219  *
 220  * @param node peer identity the tunnel stopped working with
 221  */
 222 typedef void (*MeshNodeDisconnectCB) (const struct MeshTunnelTreeNode * node);
 223
 224
 225 /**
 226  * Create a new tunnel tree associated to a tunnel
 227  *
 228  * @param t Tunnel this tree will represent
 229  * @param peer A short peer id of the root of the tree
 230  *
 231  * @return A newly allocated and initialized tunnel tree
 232  */
 233 struct MeshTunnelTree *
 234 tree_new (struct MeshTunnel *t, GNUNET_PEER_Id peer);
 235
 236
 237 /**
 238  * Recursively find the given peer in the tree.
 239  *
 240  * @param parent Parent node where to start looking.
 241  * @param peer Short ID of peer to find.
 242  *
 243  * @return Pointer to the node of the peer. NULL if not found.
 244  */
 245 struct MeshTunnelTreeNode *
 246 tree_find_peer (struct MeshTunnelTreeNode *parent,
 247                 GNUNET_PEER_Id peer);
 248
 249
 250 /**
 251  * Delete the current path to the peer, including all now unused relays.
 252  * The destination peer is NOT destroyed, it is returned in order to either set
 253  * a new path to it or destroy it explicitly, taking care of it's child nodes.
 254  *
 255  * @param t Tunnel tree where to delete the path from.
 256  * @param peer Destination peer whose path we want to remove.
 257  * @param cb Callback to use to notify about which peers are going to be
 258  *           disconnected.
 259  *
 260  * @return pointer to the pathless node.
 261  *         NULL when not found
 262  */
 263 struct MeshTunnelTreeNode *
 264 tree_del_path (struct MeshTunnelTree *t,
 265                GNUNET_PEER_Id peer,
 266                MeshNodeDisconnectCB cb);
 267
 268
 269 /**
 270  * Return a newly allocated individual path to reach a peer from the local peer,
 271  * according to the path tree of some tunnel.
 272  *
 273  * @param t Tunnel from which to read the path tree
 274  * @param peer Destination peer to whom we want a path
 275  *
 276  * @return A newly allocated individual path to reach the destination peer.
 277  *         Path must be destroyed afterwards.
 278  */
 279 struct MeshPeerPath *
 280 tree_get_path_to_peer(struct MeshTunnelTree *t,
 281                       GNUNET_PEER_Id peer);
 282
 283
 284 /**
 285  * Integrate a stand alone path into the tunnel tree.
 286  *
 287  * @param t Tunnel where to add the new path.
 288  * @param p Path to be integrated.
 289  * @param cb Callback to use to notify about peers temporarily disconnecting
 290  *
 291  * @return GNUNET_OK in case of success.
 292  *         GNUNET_SYSERR in case of error.
 293  */
 294 int
 295 tree_add_path (struct MeshTunnelTree *t,
 296                const struct MeshPeerPath *p,
 297                MeshNodeDisconnectCB cb);
 298
 299
 300 /**
 301  * Print the tree on stderr
 302  *
 303  * @param t The tree
 304  */
 305 void
 306 tree_debug(struct MeshTunnelTree *t);
 307
 308
 309 /**
 310  * Destroy the whole tree and free all used memory and Peer_Ids
 311  *
 312  * @param t Tree to be destroyed
 313  */
 314 void
 315 tree_destroy (struct MeshTunnelTree *t);