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 /**
 146  * Method called whenever a node has been marked as disconnected.
 147  *
 148  * @param node peer identity the tunnel stopped working with
 149  */
 150 typedef void (*MeshNodeDisconnectCB) (const struct MeshTunnelTreeNode * node);
 151
 152
 153 /**
 154  * Invert the path
 155  *
 156  * @param p the path to invert
 157  */
 158 void
 159 path_invert (struct MeshPeerPath *path);
 160
 161
 162
 163 /**
 164  * Destroy the path and free any allocated resources linked to it
 165  *
 166  * @param p the path to destroy
 167  *
 168  * @return GNUNET_OK on success
 169  */
 170 int
 171 path_destroy (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 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, GNUNET_PEER_Id peer);
 185
 186
 187 /**
 188  * Get the length of a path
 189  *
 190  * @param path The path to measure, with the local peer at any point of it
 191  *
 192  * @return Number of hops to reach destination
 193  *         UINT_MAX in case the peer is not in the path
 194  */
 195 unsigned int
 196 path_get_length (struct MeshPeerPath *path);
 197
 198
 199 /**
 200  * Get the cost of the path relative to the already built tunnel tree
 201  *
 202  * @param t The tunnel tree to which compare
 203  * @param path The individual path to reach a peer
 204  *
 205  * @return Number of hops to reach destination, UINT_MAX in case the peer is not
 206  * in the path
 207  */
 208 unsigned int
 209 path_get_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path);
 210
 211
 212 /**
 213  * Recursively find the given peer in the tree.
 214  *
 215  * @param t Tunnel where to look for the peer.
 216  * @param peer Peer to find
 217  *
 218  * @return Pointer to the node of the peer. NULL if not found.
 219  */
 220 struct MeshTunnelTreeNode *
 221 tree_find_peer (struct MeshTunnelTreeNode *root, GNUNET_PEER_Id peer_id);
 222
 223
 224 /**
 225  * Delete the current path to the peer, including all now unused relays.
 226  * The destination peer is NOT destroyed, it is returned in order to either set
 227  * a new path to it or destroy it explicitly, taking care of it's child nodes.
 228  *
 229  * @param t Tunnel where to delete the path from.
 230  * @param peer Destination peer whose path we want to remove.
 231  * @param cb Callback to use to notify about disconnected peers
 232  *
 233  * @return pointer to the pathless node, NULL on error
 234  */
 235 struct MeshTunnelTreeNode *
 236 tree_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id,
 237                  MeshNodeDisconnectCB cb);
 238
 239
 240 /**
 241  * Return a newly allocated individual path to reach a peer from the local peer,
 242  * according to the path tree of some tunnel.
 243  *
 244  * @param t Tunnel from which to read the path tree
 245  * @param peer_info Destination peer to whom we want a path
 246  *
 247  * @return A newly allocated individual path to reach the destination peer.
 248  *         Path must be destroyed afterwards.
 249  */
 250 struct MeshPeerPath *
 251 tree_get_path_to_peer(struct MeshTunnelTree *t, GNUNET_PEER_Id peer);
 252
 253
 254 /**
 255  * Integrate a stand alone path into the tunnel tree.
 256  *
 257  * @param t Tunnel where to add the new path.
 258  * @param p Path to be integrated.
 259  * @param cb Callback to use to notify about peers temporarily disconnecting
 260  *
 261  * @return GNUNET_OK in case of success.
 262  *         GNUNET_SYSERR in case of error.
 263  */
 264 int
 265 tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p,
 266                  MeshNodeDisconnectCB cb);
 267
 268
 269 /**
 270  * Allocates and initializes a new node.
 271  * Sets ID and parent of the new node and inserts it in the DLL of the parent
 272  *
 273  * @param parent Node that will be the parent from the new node, NULL for root
 274  * @param id Short Id of the new node
 275  *
 276  * @return Newly allocated node
 277  */
 278 struct MeshTunnelTreeNode *
 279 tree_node_new(struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id id);
 280
 281
 282 /**
 283  * Destroy the node and all children
 284  *
 285  * @param n Parent node to be destroyed
 286  */
 287 void
 288 tree_node_destroy (struct MeshTunnelTreeNode *n);
 289
 290
 291 /**
 292  * Destroy the whole tree and free all used memory and Peer_Ids
 293  *
 294  * @param t Tree to be destroyed
 295  */
 296 void
 297 tree_destroy (struct MeshTunnelTree *t);
 298
 299
 300 void
 301 tree_debug(struct MeshTunnelTree *t);