src/cadet/cadet_tunnel_tree.h

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (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 cadet/cadet_tunnel_tree.h
  23  * @brief Tunnel tree handling functions
  24  * @author Bartlomiej Polot
  25  */
  26
  27 #include "cadet.h"
  28
  29 /******************************************************************************/
  30 /************************      DATA STRUCTURES     ****************************/
  31 /******************************************************************************/
  32
  33 /**
  34  * Information regarding a possible path to reach a single peer
  35  */
  36 struct CadetPeerPath
  37 {
  38
  39     /**
  40      * Linked list
  41      */
  42   struct CadetPeerPath *next;
  43   struct CadetPeerPath *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 CadetTunnelTreeNode;
  62
  63
  64 /**
  65  * Tree to reach all peers in the tunnel
  66  */
  67 struct CadetTunnelTree;
  68
  69
  70 /******************************************************************************/
  71 /*************************        FUNCTIONS       *****************************/
  72 /******************************************************************************/
  73
  74 /**
  75  * Create a new path.
  76  *
  77  * @param length How many hops will the path have.
  78  *
  79  * @return A newly allocated path with a peer array of the specified length.
  80  */
  81 struct CadetPeerPath *
  82 path_new (unsigned int length);
  83
  84
  85 /**
  86  * Invert the path.
  87  *
  88  * @param path The path to invert.
  89  */
  90 void
  91 path_invert (struct CadetPeerPath *path);
  92
  93
  94 /**
  95  * Duplicate a path, incrementing short peer's rc.
  96  *
  97  * @param path The path to duplicate.
  98  */
  99 struct CadetPeerPath *
 100 path_duplicate (struct CadetPeerPath *path);
 101
 102
 103 /**
 104  * Get the length of a path.
 105  *
 106  * @param path The path to measure, with the local peer at any point of it.
 107  *
 108  * @return Number of hops to reach destination.
 109  *         UINT_MAX in case the peer is not in the path.
 110  */
 111 unsigned int
 112 path_get_length (struct CadetPeerPath *path);
 113
 114
 115 /**
 116  * Destroy the path and free any allocated resources linked to it
 117  *
 118  * @param p the path to destroy
 119  *
 120  * @return GNUNET_OK on success
 121  */
 122 int
 123 path_destroy (struct CadetPeerPath *p);
 124
 125
 126 /******************************************************************************/
 127
 128 /**
 129  * Iterator over all children of a node.
 130  *
 131  * @param cls Closure.
 132  * @param peer_id Short ID of the peer.
 133  */
 134 typedef void (*CadetTreeCallback) (void *cls, GNUNET_PEER_Id peer_id);
 135
 136
 137 /**
 138  * Iterator over all nodes in a tree.
 139  *
 140  * @param cls Closure.
 141  * @param peer_id Short ID of the peer.
 142  * @param peer_id Short ID of the parent of the peer.
 143  */
 144 typedef void (*CadetWholeTreeCallback) (void *cls,
 145                                        GNUNET_PEER_Id peer_id,
 146                                        GNUNET_PEER_Id parent_id);
 147
 148 /**
 149  * Create a new tunnel tree associated to a tunnel
 150  *
 151  * @param peer A short peer id of the root of the tree
 152  *
 153  * @return A newly allocated and initialized tunnel tree
 154  */
 155 struct CadetTunnelTree *
 156 tree_new (GNUNET_PEER_Id peer);
 157
 158
 159 /**
 160  * Set the status of a node.
 161  *
 162  * @param tree Tree.
 163  * @param peer A short peer id of the node.
 164  * @param status New status to set.
 165  */
 166 void
 167 tree_set_status (struct CadetTunnelTree *tree, GNUNET_PEER_Id peer,
 168                  enum CadetPeerState status);
 169
 170
 171 /**
 172  * Get the status of a node.
 173  *
 174  * @param tree Tree whose local id we want to now.
 175  * @param peer A short peer id of the node.
 176  *
 177  * @return Short peer id of local peer.
 178  */
 179 enum CadetPeerState
 180 tree_get_status (struct CadetTunnelTree *tree, GNUNET_PEER_Id peer);
 181
 182
 183 /**
 184  * Get the id of the predecessor of the local node.
 185  *
 186  * @param tree Tree whose local id we want to now.
 187  *
 188  * @return Short peer id of local peer.
 189  */
 190 GNUNET_PEER_Id
 191 tree_get_predecessor (struct CadetTunnelTree *tree);
 192
 193
 194 /**
 195  * Find the first peer whom to send a packet to go down this path
 196  *
 197  * @param t The tunnel tree to use
 198  * @param peer The peerinfo of the peer we are trying to reach
 199  *
 200  * @return peerinfo of the peer who is the first hop in the tunnel
 201  *         NULL on error
 202  */
 203 struct GNUNET_PeerIdentity *
 204 tree_get_first_hop (struct CadetTunnelTree *t, GNUNET_PEER_Id peer);
 205
 206
 207 /**
 208  * Find the given peer in the tree.
 209  *
 210  * @param tree Tree where to look for the peer.
 211  * @param peer_id Peer to find.
 212  *
 213  * @return Pointer to the node of the peer. NULL if not found.
 214  */
 215 struct CadetTunnelTreeNode *
 216 tree_find_peer (struct CadetTunnelTree *tree, GNUNET_PEER_Id peer_id);
 217
 218
 219 /**
 220  * Iterate over all children of the local node.
 221  *
 222  * @param tree Tree to use. Must have "me" set.
 223  * @param cb Callback to call over each child.
 224  * @param cb_cls Closure for @c cb.
 225  */
 226 void
 227 tree_iterate_children (struct CadetTunnelTree *tree,
 228                        CadetTreeCallback cb,
 229                        void *cb_cls);
 230
 231
 232 /**
 233  * Iterate over all nodes in the tree.
 234  *
 235  * @param tree Tree to use..
 236  * @param cb Callback to call over each child.
 237  * @param cb_cls Closure for @c cb.
 238  *
 239  * TODO: recursive implementation? (s/heap/stack/g)
 240  */
 241 void
 242 tree_iterate_all (struct CadetTunnelTree *tree,
 243                   CadetWholeTreeCallback cb,
 244                   void *cb_cls);
 245
 246 /**
 247  * Count how many children does the local node have in the tree.
 248  *
 249  * @param tree Tree to use. Must have "me" set.
 250  */
 251 unsigned int
 252 tree_count_children (struct CadetTunnelTree *tree);
 253
 254
 255 /**
 256  * Recusively update the info about what is the first hop to reach the node
 257  *
 258  * @param tree Tree this nodes belongs to.
 259  * @param parent_id Short ID from node form which to start updating.
 260  * @param hop If known, ID of the first hop.
 261  *            If not known, NULL to find out and pass on children.
 262  */
 263 void
 264 tree_update_first_hops (struct CadetTunnelTree *tree, GNUNET_PEER_Id parent_id,
 265                         struct GNUNET_PeerIdentity *hop);
 266
 267 /**
 268  * Delete the current path to the peer, including all now unused relays.
 269  * The destination peer is NOT destroyed, it is returned in order to either set
 270  * a new path to it or destroy it explicitly, taking care of it's child nodes.
 271  *
 272  * @param t Tunnel tree where to delete the path from.
 273  * @param peer_id Short ID of the destination peer whose path we want to remove.
 274  * @param cb Callback to use to notify about which peers are going to be
 275  *           disconnected.
 276  * @param cbcls Closure for cb.
 277  *
 278  * @return pointer to the pathless node.
 279  *         NULL when not found
 280  */
 281 struct CadetTunnelTreeNode *
 282 tree_del_path (struct CadetTunnelTree *t, GNUNET_PEER_Id peer_id,
 283                CadetTreeCallback cb, void *cbcls);
 284
 285
 286 /**
 287  * Return a newly allocated individual path to reach a peer from the local peer,
 288  * according to the path tree of some tunnel.
 289  *
 290  * @param t Tunnel from which to read the path tree
 291  * @param peer Destination peer to whom we want a path
 292  *
 293  * @return A newly allocated individual path to reach the destination peer.
 294  *         Path must be destroyed afterwards.
 295  */
 296 struct CadetPeerPath *
 297 tree_get_path_to_peer (struct CadetTunnelTree *t, GNUNET_PEER_Id peer);
 298
 299
 300 /**
 301  * Integrate a stand alone path into the tunnel tree.
 302  *
 303  * @param t Tunnel where to add the new path.
 304  * @param p Path to be integrated.
 305  * @param cb Callback to use to notify about peers temporarily disconnecting.
 306  * @param cbcls Closure for cb.
 307  *
 308  * @return GNUNET_OK in case of success.
 309  *         GNUNET_SYSERR in case of error.
 310  */
 311 int
 312 tree_add_path (struct CadetTunnelTree *t, const struct CadetPeerPath *p,
 313                CadetTreeCallback cb, void *cbcls);
 314
 315
 316 /**
 317  * Notifies a tree that a connection it might be using is broken.
 318  * Marks all peers down the paths as disconnected and notifies the client.
 319  *
 320  * @param t Tree to use.
 321  * @param p1 Short id of one of the peers (order unimportant)
 322  * @param p2 Short id of one of the peers (order unimportant)
 323  * @param cb Function to call for every peer that is marked as disconnected.
 324  * @param cbcls Closure for cb.
 325  *
 326  * @return Short ID of the first disconnected peer in the tree.
 327  */
 328 GNUNET_PEER_Id
 329 tree_notify_connection_broken (struct CadetTunnelTree *t, GNUNET_PEER_Id p1,
 330                                GNUNET_PEER_Id p2, CadetTreeCallback cb,
 331                                void *cbcls);
 332
 333
 334 /**
 335  * Deletes a peer from a tunnel, liberating all unused resources on the path to
 336  * it. It shouldn't have children, if it has they will be destroyed as well.
 337  * If the tree is not local and no longer has any paths, the root node will be
 338  * destroyed and marked as NULL.
 339  *
 340  * FIXME: dont destroy the root
 341  *
 342  * @param t Tunnel tree to use.
 343  * @param peer Short ID of the peer to remove from the tunnel tree.
 344  * @param cb Callback to notify client of disconnected peers.
 345  * @param cbcls Closure for cb.
 346  *
 347  * @return GNUNET_YES if the tunnel still has nodes
 348  */
 349 int
 350 tree_del_peer (struct CadetTunnelTree *t, GNUNET_PEER_Id peer,
 351                CadetTreeCallback cb, void *cbcls);
 352
 353
 354 /**
 355  * Get the cost of the path relative to the already built tunnel tree
 356  *
 357  * @param t The tunnel tree to which compare
 358  * @param path The individual path to reach a peer
 359  *
 360  * @return Number of hops to reach destination, UINT_MAX in case the peer is not
 361  * in the path
 362  */
 363 unsigned int
 364 tree_get_path_cost (struct CadetTunnelTree *t, struct CadetPeerPath *path);
 365
 366
 367 /**
 368  * Print the tree on stderr
 369  *
 370  * @param t The tree
 371  */
 372 void
 373 tree_debug (struct CadetTunnelTree *t);
 374
 375
 376 /**
 377  * Destroy the whole tree and free all used memory and Peer_Ids
 378  *
 379  * @param t Tree to be destroyed
 380  */
 381 void
 382 tree_destroy (struct CadetTunnelTree *t);