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    * Array of children
  80    */
  81   struct MeshTunnelTreeNode *children;
  82
  83   /**
  84    * Number of children
  85    */
  86   unsigned int nchildren;
  87
  88     /**
  89      * Status of the peer in the tunnel
  90      */
  91   enum MeshPeerState status;
  92 };
  93
  94
  95 /**
  96  * Tree to reach all peers in the tunnel
  97  */
  98 struct MeshTunnelTree
  99 {
 100   /**
 101    * How often to refresh the path
 102    */
 103   struct GNUNET_TIME_Relative refresh;
 104
 105   /**
 106    * Tunnel this path belongs to
 107    */
 108   struct MeshTunnel *t;
 109
 110   /**
 111    * Root node of peer tree
 112    */
 113   struct MeshTunnelTreeNode *root;
 114
 115   /**
 116    * Node that represents our position in the tree (for non local tunnels)
 117    */
 118   struct MeshTunnelTreeNode *me;
 119
 120   /**
 121    * Cache of all peers and the first hop to them.
 122    * Indexed by PeerIdentity, contains a pointer to the PeerIdentity
 123    * of 1st hop.
 124    */
 125   struct GNUNET_CONTAINER_MultiHashMap *first_hops;
 126
 127 };
 128
 129
 130 /******************************************************************************/
 131 /*************************        FUNCTIONS       *****************************/
 132 /******************************************************************************/
 133
 134
 135 /**
 136  * Method called whenever a node has been marked as disconnected.
 137  *
 138  * @param node peer identity the tunnel stopped working with
 139  */
 140 typedef void (*MeshNodeDisconnectCB) (const struct MeshTunnelTreeNode * node);
 141
 142
 143 /**
 144  * Invert the path
 145  *
 146  * @param p the path to invert
 147  */
 148 void
 149 path_invert (struct MeshPeerPath *path);
 150
 151
 152
 153 /**
 154  * Destroy the path and free any allocated resources linked to it
 155  *
 156  * @param p the path to destroy
 157  *
 158  * @return GNUNET_OK on success
 159  */
 160 int
 161 path_destroy (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 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, GNUNET_PEER_Id peer);
 175
 176
 177 /**
 178  * Get the length of a path
 179  *
 180  * @param path The path to measure, with the local peer at any point of it
 181  *
 182  * @return Number of hops to reach destination
 183  *         UINT_MAX in case the peer is not in the path
 184  */
 185 unsigned int
 186 path_get_length (struct MeshPeerPath *path);
 187
 188
 189 /**
 190  * Get the cost of the path relative to the already built tunnel tree
 191  *
 192  * @param t The tunnel tree to which compare
 193  * @param path The individual path to reach a peer
 194  *
 195  * @return Number of hops to reach destination, UINT_MAX in case the peer is not
 196  * in the path
 197  */
 198 unsigned int
 199 path_get_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path);
 200
 201
 202 /**
 203  * Recursively find the given peer in the tree.
 204  *
 205  * @param t Tunnel where to look for the peer.
 206  * @param peer Peer to find
 207  *
 208  * @return Pointer to the node of the peer. NULL if not found.
 209  */
 210 struct MeshTunnelTreeNode *
 211 tree_find_peer (struct MeshTunnelTreeNode *root, GNUNET_PEER_Id peer_id);
 212
 213
 214 /**
 215  * Delete the current path to the peer, including all now unused relays.
 216  * The destination peer is NOT destroyed, it is returned in order to either set
 217  * a new path to it or destroy it explicitly, taking care of it's child nodes.
 218  *
 219  * @param t Tunnel where to delete the path from.
 220  * @param peer Destination peer whose path we want to remove.
 221  * @param cb Callback to use to notify about disconnected peers
 222  *
 223  * @return pointer to the pathless node, NULL on error
 224  */
 225 struct MeshTunnelTreeNode *
 226 tree_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id,
 227                  MeshNodeDisconnectCB cb);
 228
 229
 230 /**
 231  * Return a newly allocated individual path to reach a peer from the local peer,
 232  * according to the path tree of some tunnel.
 233  *
 234  * @param t Tunnel from which to read the path tree
 235  * @param peer_info Destination peer to whom we want a path
 236  *
 237  * @return A newly allocated individual path to reach the destination peer.
 238  *         Path must be destroyed afterwards.
 239  */
 240 struct MeshPeerPath *
 241 tree_get_path_to_peer(struct MeshTunnelTree *t, GNUNET_PEER_Id peer);
 242
 243
 244 /**
 245  * Integrate a stand alone path into the tunnel tree.
 246  *
 247  * @param t Tunnel where to add the new path.
 248  * @param p Path to be integrated.
 249  * @param cb Callback to use to notify about peers temporarily disconnecting
 250  *
 251  * @return GNUNET_OK in case of success.
 252  *         GNUNET_SYSERR in case of error.
 253  */
 254 int
 255 tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p,
 256                  MeshNodeDisconnectCB cb);
 257
 258
 259 /**
 260  * Destroy the node and all children
 261  *
 262  * @param n Parent node to be destroyed
 263  */
 264 void
 265 tree_node_destroy (struct MeshTunnelTreeNode *n);
 266
 267
 268 /**
 269  * Destroy the whole tree and free all used memory and Peer_Ids
 270  *
 271  * @param t Tree to be destroyed
 272  */
 273 void
 274 tree_destroy (struct MeshTunnelTree *t);