src/testbed/testbed_api_topology.c

   1 /*
   2       This file is part of GNUnet
   3       (C) 2008--2012 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 testbed/testbed_api_topology.c
  23  * @brief topology-generation functions
  24  * @author Christian Grothoff
  25  */
  26 #include "platform.h"
  27 #include "gnunet_testbed_service.h"
  28 #include "testbed_api.h"
  29 #include "testbed_api_peers.h"
  30 #include "testbed_api_operations.h"
  31
  32 /**
  33  * Generic loggins shorthand
  34  */
  35 #define LOG(kind,...)                                           \
  36   GNUNET_log_from (kind, "testbed-api-topology", __VA_ARGS__)
  37
  38
  39 /**
  40  * Context information for topology operations
  41  */
  42 struct TopologyContext;
  43
  44
  45 /**
  46  * Representation of an overlay link
  47  */
  48 struct OverlayLink
  49 {
  50
  51   /**
  52    * An operation corresponding to this link
  53    */
  54   struct GNUNET_TESTBED_Operation *op;
  55
  56   /**
  57    * The topology context this link is a part of
  58    */
  59   struct TopologyContext *tc;
  60
  61   /**
  62    * position of peer A's handle in peers array
  63    */
  64   uint32_t A;
  65
  66   /**
  67    * position of peer B's handle in peers array
  68    */
  69   uint32_t B;
  70
  71 };
  72
  73
  74 /**
  75  * Context information for topology operations
  76  */
  77 struct TopologyContext
  78 {
  79   /**
  80    * The array of peers
  81    */
  82   struct GNUNET_TESTBED_Peer **peers;
  83
  84   /**
  85    * An array of links; this array is of size link_array_size
  86    */
  87   struct OverlayLink *link_array;
  88
  89   /**
  90    * The operation closure
  91    */
  92   void *op_cls;
  93
  94   /**
  95    * The number of peers
  96    */
  97   unsigned int num_peers;
  98
  99   /**
 100    * The size of the link array
 101    */
 102   unsigned int link_array_size;
 103
 104   /**
 105    * should the automatic retry be disabled
 106    */
 107   int disable_retry;
 108
 109 };
 110
 111
 112 /**
 113  * Callback to be called when an overlay_link operation complete
 114  *
 115  * @param cls element of the link_op array which points to the corresponding operation
 116  * @param op the operation that has been finished
 117  * @param emsg error message in case the operation has failed; will be NULL if
 118  *          operation has executed successfully.
 119  */
 120 static void
 121 overlay_link_completed (void *cls,
 122                         struct GNUNET_TESTBED_Operation *op,
 123                         const char *emsg)
 124 {
 125   struct OverlayLink *link = cls;
 126   struct TopologyContext *tc;
 127
 128   GNUNET_assert (op == link->op);
 129   GNUNET_TESTBED_operation_done (op);
 130   link->op = NULL;
 131   tc = link->tc;
 132   if ((NULL != emsg) && (GNUNET_NO == tc->disable_retry))
 133   {
 134     LOG (GNUNET_ERROR_TYPE_WARNING,
 135          "Error while establishing a link: %s -- Retrying\n", emsg);
 136     link->op =
 137         GNUNET_TESTBED_overlay_connect (tc->op_cls,
 138                                         &overlay_link_completed,
 139                                         link,
 140                                         tc->peers[link->A],
 141                                         tc->peers[link->B]);
 142     return;
 143   }
 144 }
 145
 146
 147
 148 /**
 149  * Function called when a overlay connect operation is ready
 150  *
 151  * @param cls the Topology context
 152  */
 153 static void
 154 opstart_overlay_configure_topology (void *cls)
 155 {
 156   struct TopologyContext *tc = cls;
 157   unsigned int p;
 158
 159   for (p = 0; p < tc->link_array_size; p++)
 160   {
 161     tc->link_array[p].op =
 162         GNUNET_TESTBED_overlay_connect (tc->op_cls, &overlay_link_completed,
 163                                         &tc->link_array[p],
 164                                         tc->peers[tc->link_array[p].A],
 165                                         tc->peers[tc->link_array[p].B]);
 166   }
 167 }
 168
 169
 170 /**
 171  * Callback which will be called when overlay connect operation is released
 172  *
 173  * @param cls the Topology context
 174  */
 175 static void
 176 oprelease_overlay_configure_topology (void *cls)
 177 {
 178   struct TopologyContext *tc = cls;
 179   unsigned int p;
 180
 181   if (NULL != tc->link_array)
 182   {
 183     for (p = 0; p < tc->link_array_size; p++)
 184       if (NULL != tc->link_array[p].op)
 185         GNUNET_TESTBED_operation_done (tc->link_array[p].op);
 186     GNUNET_free (tc->link_array);
 187   }
 188   GNUNET_free (tc);
 189 }
 190
 191
 192 /**
 193  * Generates line topology
 194  *
 195  * @param tc the topology context
 196  */
 197 static void
 198 gen_topo_line (struct TopologyContext *tc)
 199 {
 200   unsigned int cnt;
 201
 202   tc->link_array_size = tc->num_peers - 1;
 203   tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
 204                                   tc->link_array_size);
 205   for (cnt=0; cnt < (tc->num_peers - 1); cnt++)
 206   {
 207     tc->link_array[cnt].A = cnt;
 208     tc->link_array[cnt].B = cnt + 1;
 209     tc->link_array[cnt].tc = tc;
 210   }
 211 }
 212
 213
 214 /**
 215  * Generates ring topology
 216  *
 217  * @param tc the topology context
 218  */
 219 static void
 220 gen_topo_ring (struct TopologyContext *tc)
 221 {
 222   gen_topo_line (tc);
 223   tc->link_array_size++;
 224   tc->link_array = GNUNET_realloc (tc->link_array,
 225                                    sizeof (struct OverlayLink) *
 226                                    tc->link_array_size);
 227   tc->link_array[tc->link_array_size - 1].op = NULL;
 228   tc->link_array[tc->link_array_size - 1].tc = tc;
 229   tc->link_array[tc->link_array_size - 1].A = tc->num_peers - 1;
 230   tc->link_array[tc->link_array_size - 1].B = 0;
 231 }
 232
 233
 234 /**
 235  * Generates ring topology
 236  *
 237  * @param tc the topology context
 238  * @param links the number of random links to establish
 239  * @param append GNUNET_YES to add links to existing link array; GNUNET_NO to
 240  *          create a new link array
 241  */
 242 static void
 243 gen_topo_random (struct TopologyContext *tc, unsigned int links, int append)
 244 {
 245   unsigned int cnt;
 246   unsigned int index;
 247   uint32_t A_rand;
 248   uint32_t B_rand;
 249
 250   if (GNUNET_YES == append)
 251   {
 252     GNUNET_assert ((0 < tc->link_array_size) && (NULL != tc->link_array));
 253     index = tc->link_array_size;
 254     tc->link_array_size += links;
 255     tc->link_array = GNUNET_realloc (tc->link_array,
 256                                    sizeof (struct OverlayLink) *
 257                                      tc->link_array_size);
 258   }
 259   else
 260   {
 261     GNUNET_assert ((0 == tc->link_array_size) && (NULL == tc->link_array));
 262     index = 0;
 263     tc->link_array_size = links;
 264     tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
 265                                     tc->link_array_size);
 266   }
 267   for (cnt = 0; cnt < links; cnt++)
 268   {
 269     do {
 270       A_rand = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
 271                                          tc->num_peers);
 272       B_rand = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
 273                                          tc->num_peers);
 274     } while (A_rand == B_rand);
 275     tc->link_array[index + cnt].op = NULL;
 276     tc->link_array[index + cnt].A = A_rand;
 277     tc->link_array[index + cnt].B = B_rand;
 278     tc->link_array[index + cnt].tc = tc;
 279   }
 280 }
 281
 282
 283 /**
 284  * Configure overall network topology to have a particular shape.
 285  *
 286  * @param op_cls closure argument to give with the operation event
 287  * @param num_peers number of peers in 'peers'
 288  * @param peers array of 'num_peers' with the peers to configure
 289  * @param topo desired underlay topology to use
 290  * @param ap topology-specific options
 291  * @return handle to the operation, NULL if configuring the topology
 292  *         is not allowed at this time
 293  */
 294 struct GNUNET_TESTBED_Operation *
 295 GNUNET_TESTBED_underlay_configure_topology_va (void *op_cls,
 296                                                unsigned int num_peers,
 297                                                struct GNUNET_TESTBED_Peer
 298                                                **peers,
 299                                                enum
 300                                                GNUNET_TESTBED_TopologyOption
 301                                                topo, va_list ap)
 302 {
 303   GNUNET_break (0);
 304   return NULL;
 305 }
 306
 307
 308 /**
 309  * Configure overall network topology to have a particular shape.
 310  *
 311  * @param op_cls closure argument to give with the operation event
 312  * @param num_peers number of peers in 'peers'
 313  * @param peers array of 'num_peers' with the peers to configure
 314  * @param topo desired underlay topology to use
 315  * @param ... topology-specific options
 316  * @return handle to the operation, NULL if configuring the topology
 317  *         is not allowed at this time
 318  */
 319 struct GNUNET_TESTBED_Operation *
 320 GNUNET_TESTBED_underlay_configure_topology (void *op_cls,
 321                                             unsigned int num_peers,
 322                                             struct GNUNET_TESTBED_Peer **peers,
 323                                             enum GNUNET_TESTBED_TopologyOption
 324                                             topo, ...)
 325 {
 326   GNUNET_break (0);
 327   return NULL;
 328 }
 329
 330
 331 /**
 332  * All peers must have been started before calling this function.
 333  * This function then connects the given peers in the P2P overlay
 334  * using the given topology.
 335  *
 336  * @param op_cls closure argument to give with the operation event
 337  * @param num_peers number of peers in 'peers'
 338  * @param peers array of 'num_peers' with the peers to configure
 339  * @param topo desired underlay topology to use
 340  * @param va topology-specific options
 341  * @return handle to the operation, NULL if connecting these
 342  *         peers is fundamentally not possible at this time (peers
 343  *         not running or underlay disallows) or if num_peers is less than 2
 344  */
 345 struct GNUNET_TESTBED_Operation *
 346 GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls,
 347                                               unsigned int num_peers,
 348                                               struct GNUNET_TESTBED_Peer **peers,
 349                                               enum GNUNET_TESTBED_TopologyOption
 350                                               topo, va_list va)
 351 {
 352   struct TopologyContext *tc;
 353   struct GNUNET_TESTBED_Operation *op;
 354   struct GNUNET_TESTBED_Controller *c;
 355   enum GNUNET_TESTBED_TopologyOption secondary_option;
 356   unsigned int cnt;
 357
 358   if (num_peers < 2)
 359     return NULL;
 360   c = peers[0]->controller;
 361   tc = GNUNET_malloc (sizeof (struct TopologyContext));
 362   tc->peers = peers;
 363   tc->num_peers = num_peers;
 364   tc->op_cls = op_cls;
 365   switch (topo)
 366   {
 367   case GNUNET_TESTBED_TOPOLOGY_LINE:
 368     gen_topo_line (tc);
 369     break;
 370   case GNUNET_TESTBED_TOPOLOGY_RING:
 371     gen_topo_ring (tc);
 372     break;
 373   case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
 374     gen_topo_random (tc,
 375                      va_arg (va, unsigned int),
 376                      GNUNET_NO);
 377     break;
 378   case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
 379     gen_topo_ring (tc);
 380     gen_topo_random (tc,
 381                      va_arg (va, unsigned int),
 382                      GNUNET_YES);
 383     break;
 384   case GNUNET_TESTBED_TOPOLOGY_CLIQUE:
 385     tc->link_array_size = num_peers * (num_peers - 1);
 386     tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
 387                                     tc->link_array_size);
 388     {
 389       unsigned int offset;
 390
 391       offset = 0;
 392       for (cnt=0; cnt < num_peers; cnt++)
 393       {
 394         unsigned int neighbour;
 395
 396         for (neighbour=0; neighbour < num_peers; neighbour++)
 397         {
 398           if (neighbour == cnt)
 399             continue;
 400           tc->link_array[offset].A = cnt;
 401           tc->link_array[offset].B = neighbour;
 402           tc->link_array[offset].tc = tc;
 403           offset++;
 404         }
 405       }
 406     }
 407     break;
 408   default:
 409     GNUNET_break (0);
 410     GNUNET_free (tc);
 411     return NULL;
 412   }
 413   do
 414   {
 415     secondary_option = va_arg (va, enum GNUNET_TESTBED_TopologyOption);
 416     switch (secondary_option)
 417     {
 418     case GNUNET_TESTBED_TOPOLOGY_DISABLE_AUTO_RETRY:
 419       tc->disable_retry = GNUNET_YES;
 420       break;
 421     case GNUNET_TESTBED_TOPOLOGY_OPTION_END:
 422       break;
 423     default:
 424       GNUNET_break (0);         /* Should not use any other option apart from
 425                                    the ones handled here */
 426       GNUNET_free_non_null (tc->link_array);
 427       GNUNET_free (tc);
 428       return NULL;
 429     }
 430   } while (GNUNET_TESTBED_TOPOLOGY_OPTION_END != secondary_option);
 431   op = GNUNET_TESTBED_operation_create_ (tc,
 432                                          &opstart_overlay_configure_topology,
 433                                          &oprelease_overlay_configure_topology);
 434   GNUNET_TESTBED_operation_queue_insert_
 435       (c->opq_parallel_topology_config_operations, op);
 436   GNUNET_TESTBED_operation_begin_wait_ (op);
 437   return op;
 438 }
 439
 440
 441 /**
 442  * All peers must have been started before calling this function.
 443  * This function then connects the given peers in the P2P overlay
 444  * using the given topology.
 445  *
 446  * @param op_cls closure argument to give with the operation event
 447  * @param num_peers number of peers in 'peers'
 448  * @param peers array of 'num_peers' with the peers to configure
 449  * @param topo desired underlay topology to use
 450  * @param ... topology-specific options
 451  * @return handle to the operation, NULL if connecting these
 452  *         peers is fundamentally not possible at this time (peers
 453  *         not running or underlay disallows) or if num_peers is less than 2
 454  */
 455 struct GNUNET_TESTBED_Operation *
 456 GNUNET_TESTBED_overlay_configure_topology (void *op_cls, unsigned int num_peers,
 457                                            struct GNUNET_TESTBED_Peer **peers,
 458                                            enum GNUNET_TESTBED_TopologyOption
 459                                            topo, ...)
 460 {
 461   struct GNUNET_TESTBED_Operation *op;
 462   va_list vargs;
 463
 464   GNUNET_assert (topo < GNUNET_TESTBED_TOPOLOGY_OPTION_END);
 465   va_start (vargs, topo);
 466   op = GNUNET_TESTBED_overlay_configure_topology_va (op_cls, num_peers, peers,
 467                                                      topo, vargs);
 468   va_end (vargs);
 469   return op;
 470 }
 471
 472 /* end of testbed_api_topology.c */