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 #include "testbed_api_topology.h"
  32
  33 /**
  34  * Generic loggins shorthand
  35  */
  36 #define LOG(kind,...)                                           \
  37   GNUNET_log_from (kind, "testbed-api-topology", __VA_ARGS__)
  38
  39
  40 /**
  41  * Context information for topology operations
  42  */
  43 struct TopologyContext;
  44
  45
  46 /**
  47  * Representation of an overlay link
  48  */
  49 struct OverlayLink
  50 {
  51
  52   /**
  53    * An operation corresponding to this link
  54    */
  55   struct GNUNET_TESTBED_Operation *op;
  56
  57   /**
  58    * The topology context this link is a part of
  59    */
  60   struct TopologyContext *tc;
  61
  62   /**
  63    * position of peer A's handle in peers array
  64    */
  65   uint32_t A;
  66
  67   /**
  68    * position of peer B's handle in peers array
  69    */
  70   uint32_t B;
  71
  72 };
  73
  74
  75 /**
  76  * Context information for topology operations
  77  */
  78 struct TopologyContext
  79 {
  80   /**
  81    * The array of peers
  82    */
  83   struct GNUNET_TESTBED_Peer **peers;
  84
  85   /**
  86    * An array of links; this array is of size link_array_size
  87    */
  88   struct OverlayLink *link_array;
  89
  90   /**
  91    * The operation closure
  92    */
  93   void *op_cls;
  94
  95   /**
  96    * The number of peers
  97    */
  98   unsigned int num_peers;
  99
 100   /**
 101    * The size of the link array
 102    */
 103   unsigned int link_array_size;
 104
 105   /**
 106    * should the automatic retry be disabled
 107    */
 108   int disable_retry;
 109
 110 };
 111
 112
 113 /**
 114  * A array of names representing topologies. Should be in sync with enum
 115  * GNUNET_TESTBED_TopologyOption
 116  */
 117 const char * topology_strings[] = {
 118
 119     /**
 120      * A clique (everyone connected to everyone else).  No options. If there are N
 121      * peers this topology results in (N * (N -1)) connections.
 122      */
 123     "CLIQUE",
 124
 125     /**
 126      * Small-world network (2d torus plus random links).  Followed
 127      * by the number of random links to add (unsigned int).
 128      */
 129     "SMALL_WORLD",
 130
 131     /**
 132      * Small-world network (ring plus random links).  Followed
 133      * by the number of random links to add (unsigned int).
 134      */
 135     "SMALL_WORLD_RING",
 136
 137     /**
 138      * Ring topology.  No options.
 139      */
 140     "RING",
 141
 142     /**
 143      * 2-d torus.  No options.
 144      */
 145     "2D_TORUS",
 146
 147     /**
 148      * Random graph.  Followed by the number of random links to be established
 149      * (unsigned int)
 150      */
 151     "RANDOM", // GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI
 152
 153     /**
 154      * Certain percentage of peers are unable to communicate directly
 155      * replicating NAT conditions.  Followed by the fraction of
 156      * NAT'ed peers (float).
 157      */
 158     "INTERNAT",
 159
 160     /**
 161      * Scale free topology. No options.
 162      */
 163     "SCALE_FREE",
 164
 165     /**
 166      * Straight line topology.  No options.
 167      */
 168     "LINE",
 169
 170     /**
 171      * Read a topology from a given file.  Followed by the name of the file (const char *).
 172      */
 173     "FROM_FILE",
 174
 175     /**
 176      * All peers are disconnected.  No options.
 177      */
 178     "NONE",
 179
 180     /**
 181      * End of strings
 182      */
 183     NULL
 184
 185   };
 186
 187
 188 /**
 189  * Callback to be called when an overlay_link operation complete
 190  *
 191  * @param cls element of the link_op array which points to the corresponding operation
 192  * @param op the operation that has been finished
 193  * @param emsg error message in case the operation has failed; will be NULL if
 194  *          operation has executed successfully.
 195  */
 196 static void
 197 overlay_link_completed (void *cls,
 198                         struct GNUNET_TESTBED_Operation *op,
 199                         const char *emsg)
 200 {
 201   struct OverlayLink *link = cls;
 202   struct TopologyContext *tc;
 203
 204   GNUNET_assert (op == link->op);
 205   GNUNET_TESTBED_operation_done (op);
 206   link->op = NULL;
 207   tc = link->tc;
 208   if ((NULL != emsg) && (GNUNET_NO == tc->disable_retry))
 209   {
 210     LOG (GNUNET_ERROR_TYPE_WARNING,
 211          "Error while establishing a link: %s -- Retrying\n", emsg);
 212     link->op =
 213         GNUNET_TESTBED_overlay_connect (tc->op_cls,
 214                                         &overlay_link_completed,
 215                                         link,
 216                                         tc->peers[link->A],
 217                                         tc->peers[link->B]);
 218     return;
 219   }
 220 }
 221
 222
 223
 224 /**
 225  * Function called when a overlay connect operation is ready
 226  *
 227  * @param cls the Topology context
 228  */
 229 static void
 230 opstart_overlay_configure_topology (void *cls)
 231 {
 232   struct TopologyContext *tc = cls;
 233   unsigned int p;
 234
 235   for (p = 0; p < tc->link_array_size; p++)
 236   {
 237     tc->link_array[p].op =
 238         GNUNET_TESTBED_overlay_connect (tc->op_cls, &overlay_link_completed,
 239                                         &tc->link_array[p],
 240                                         tc->peers[tc->link_array[p].A],
 241                                         tc->peers[tc->link_array[p].B]);
 242   }
 243 }
 244
 245
 246 /**
 247  * Callback which will be called when overlay connect operation is released
 248  *
 249  * @param cls the Topology context
 250  */
 251 static void
 252 oprelease_overlay_configure_topology (void *cls)
 253 {
 254   struct TopologyContext *tc = cls;
 255   unsigned int p;
 256
 257   if (NULL != tc->link_array)
 258   {
 259     for (p = 0; p < tc->link_array_size; p++)
 260       if (NULL != tc->link_array[p].op)
 261         GNUNET_TESTBED_operation_done (tc->link_array[p].op);
 262     GNUNET_free (tc->link_array);
 263   }
 264   GNUNET_free (tc);
 265 }
 266
 267
 268 /**
 269  * Populates the OverlayLink structure.
 270  *
 271  * @param link the OverlayLink
 272  * @param A the peer A. Should be different from B
 273  * @param B the peer B. Should be different from A
 274  * @param tc the TopologyContext
 275  * @return
 276  */
 277 static void
 278 make_link (struct OverlayLink *link,
 279            uint32_t A,
 280            uint32_t B,
 281            struct TopologyContext *tc)
 282 {
 283   GNUNET_assert (A != B);
 284   LOG (GNUNET_ERROR_TYPE_DEBUG, "Connecting peer %u to %u\n", B, A);
 285   link->A = A;
 286   link->B = B;
 287   link->op = NULL;
 288   link->tc = tc;
 289 }
 290
 291
 292 /**
 293  * Generates line topology
 294  *
 295  * @param tc the topology context
 296  */
 297 static void
 298 gen_topo_line (struct TopologyContext *tc)
 299 {
 300   unsigned int cnt;
 301
 302   tc->link_array_size = tc->num_peers - 1;
 303   tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
 304                                   tc->link_array_size);
 305   for (cnt=0; cnt < (tc->num_peers - 1); cnt++)
 306     make_link (&tc->link_array[cnt], cnt, cnt + 1, tc);
 307 }
 308
 309
 310 /**
 311  * Generates ring topology
 312  *
 313  * @param tc the topology context
 314  */
 315 static void
 316 gen_topo_ring (struct TopologyContext *tc)
 317 {
 318   gen_topo_line (tc);
 319   tc->link_array_size++;
 320   tc->link_array = GNUNET_realloc (tc->link_array,
 321                                    sizeof (struct OverlayLink) *
 322                                    tc->link_array_size);
 323   make_link (&tc->link_array[tc->link_array_size - 1],
 324              tc->num_peers - 1,
 325              0,
 326              tc);
 327 }
 328
 329
 330 /**
 331  * Returns the number of links that are required to generate a 2d torus for the
 332  * given number of peers. Also returns the arrangment (number of rows and the
 333  * length of each row)
 334  *
 335  * @param num_peers number of peers
 336  * @param rows number of rows in the 2d torus. Can be NULL
 337  * @param rows_len the length of each row. This array will be allocated
 338  *          fresh. The caller should free it. Can be NULL
 339  */
 340 unsigned int
 341 GNUNET_TESTBED_2dtorus_calc_links (unsigned int num_peers,
 342                                    unsigned int *rows,
 343                                    unsigned int **rows_len)
 344 {
 345   double sq;
 346   unsigned int sq_floor;
 347   unsigned int _rows;
 348   unsigned int *_rows_len;
 349   unsigned int x;
 350   unsigned int y;
 351   unsigned int _num_peers;
 352   unsigned int cnt;
 353
 354   sq = sqrt (num_peers);
 355   sq = floor (sq);
 356   sq_floor = (unsigned int) sq;
 357   _rows = (sq_floor + 1);
 358   _rows_len = GNUNET_malloc (sizeof (unsigned int) * _rows);
 359   for (y = 0; y < _rows - 1; y++)
 360     _rows_len[y] = sq_floor;
 361   _num_peers = sq_floor * sq_floor;
 362   cnt = 2 * _num_peers;
 363   x = 0;
 364   y = 0;
 365   while (_num_peers < num_peers)
 366   {
 367     if (x < y)
 368       _rows_len[_rows - 1] = ++x;
 369     else
 370       _rows_len[y++]++;
 371     _num_peers++;
 372   }
 373   cnt += (x < 2) ? x : 2 * x;
 374   cnt += (y < 2) ? y : 2 * y;
 375   if (0 == _rows_len[_rows - 1])
 376     _rows--;
 377   if (NULL != rows)
 378     *rows = _rows;
 379   if (NULL != rows_len)
 380     *rows_len = _rows_len;
 381   else
 382     GNUNET_free (_rows_len);
 383   return cnt;
 384 }
 385
 386
 387 /**
 388  * Generates ring topology
 389  *
 390  * @param tc the topology context
 391  */
 392 static void
 393 gen_topo_2dtorus (struct TopologyContext *tc)
 394 {
 395   unsigned int rows;
 396   unsigned int *rows_len;
 397   unsigned int x;
 398   unsigned int y;
 399   unsigned int cnt;
 400   unsigned int offset;
 401
 402   tc->link_array_size = GNUNET_TESTBED_2dtorus_calc_links (tc->num_peers, &rows,
 403                                                            &rows_len);
 404   tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
 405                                   tc->link_array_size);
 406   cnt = 0;
 407   offset = 0;
 408   for (y = 0; y < rows; y++)
 409   {
 410     for (x = 0; x < rows_len[y] - 1; x++)
 411     {
 412       make_link (&tc->link_array[cnt],
 413                  offset + x,
 414                  offset + x + 1,
 415                  tc);
 416       cnt++;
 417     }
 418     if (0 == x)
 419       break;
 420     make_link (&tc->link_array[cnt],
 421                offset + x,
 422                offset,
 423                tc);
 424     cnt++;
 425     offset += rows_len[y];
 426   }
 427   for (x = 0; x < rows_len[0]; x++)
 428   {
 429     offset = 0;
 430     for (y = 0; y < rows - 1; y++)
 431     {
 432       if (x == rows_len[y+1])
 433         break;
 434       GNUNET_assert (x < rows_len[y+1]);
 435       make_link (&tc->link_array[cnt],
 436                  offset + x,
 437                  offset + rows_len[y] + x,
 438                  tc);
 439       offset += rows_len[y];
 440       cnt++;
 441     }
 442     if (0 == offset)
 443       break;
 444     make_link (&tc->link_array[cnt],
 445                offset + x,
 446                x,
 447                tc);
 448     cnt++;
 449   }
 450   GNUNET_assert (cnt == tc->link_array_size);
 451   GNUNET_free (rows_len);
 452 }
 453
 454
 455 /**
 456  * Generates ring topology
 457  *
 458  * @param tc the topology context
 459  * @param links the number of random links to establish
 460  * @param append GNUNET_YES to add links to existing link array; GNUNET_NO to
 461  *          create a new link array
 462  */
 463 static void
 464 gen_topo_random (struct TopologyContext *tc, unsigned int links, int append)
 465 {
 466   unsigned int cnt;
 467   unsigned int index;
 468   uint32_t A_rand;
 469   uint32_t B_rand;
 470
 471   if (GNUNET_YES == append)
 472   {
 473     GNUNET_assert ((0 < tc->link_array_size) && (NULL != tc->link_array));
 474     index = tc->link_array_size;
 475     tc->link_array_size += links;
 476     tc->link_array = GNUNET_realloc (tc->link_array,
 477                                    sizeof (struct OverlayLink) *
 478                                      tc->link_array_size);
 479   }
 480   else
 481   {
 482     GNUNET_assert ((0 == tc->link_array_size) && (NULL == tc->link_array));
 483     index = 0;
 484     tc->link_array_size = links;
 485     tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
 486                                     tc->link_array_size);
 487   }
 488   for (cnt = 0; cnt < links; cnt++)
 489   {
 490     do {
 491       A_rand = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
 492                                          tc->num_peers);
 493       B_rand = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
 494                                          tc->num_peers);
 495     } while (A_rand == B_rand);
 496     make_link (&tc->link_array[index + cnt], A_rand,  B_rand, tc);
 497   }
 498 }
 499
 500
 501 /**
 502  * Generates scale free network. Its construction is described in:
 503  *
 504  * "Emergence of Scaling in Random Networks." Science 286, 509-512, 1999.
 505  *
 506  * @param tc the topology context
 507  */
 508 static void
 509 gen_scale_free (struct TopologyContext *tc)
 510 {
 511   double random;
 512   double probability;
 513   unsigned int cnt;
 514   unsigned int previous_connections;
 515   unsigned int i;
 516   uint16_t *popularity;
 517
 518   popularity = GNUNET_malloc (sizeof (uint16_t) * tc->num_peers);
 519   /* Initially connect peer 1 to peer 0 */
 520   tc->link_array_size = 1;
 521   tc->link_array =  GNUNET_malloc (sizeof (struct OverlayLink));
 522   make_link (&tc->link_array[0], 0, 1, tc);
 523   popularity[0]++;  /* increase popularity of 0 as 1 connected to it*/
 524   for (cnt = 1; cnt < tc->num_peers; cnt++)
 525   {
 526     previous_connections = tc->link_array_size;
 527     for (i = 0; i < cnt; i++)
 528     {
 529       probability = ((double) popularity[i]) / ((double) previous_connections);
 530       random = ((double)
 531            GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
 532                                      UINT64_MAX)) / ((double) UINT64_MAX);
 533       if (random < probability)
 534       {
 535         tc->link_array_size++;
 536         tc->link_array = GNUNET_realloc (tc->link_array,
 537                                          (sizeof (struct OverlayLink) *
 538                                           tc->link_array_size));
 539         make_link (&tc->link_array[tc->link_array_size - 1], cnt, i, tc);
 540         popularity[cnt]++;
 541       }
 542     }
 543   }
 544   GNUNET_free (popularity);
 545 }
 546
 547
 548 /**
 549  * Generates topology from the given file
 550  *
 551  * @param tc the topology context
 552  * @param filename the filename of the file containing topology data
 553  */
 554 static void
 555 gen_topo_from_file (struct TopologyContext *tc, const char *filename)
 556 {
 557   char *data;
 558   char *end;
 559   char *buf;
 560   uint64_t fs;
 561   uint64_t offset;
 562   unsigned long int peer_id;
 563   unsigned long int other_peer_id;
 564   enum ParseState {
 565
 566     /**
 567      * We read the peer index
 568      */
 569     PEER_INDEX,
 570
 571     /**
 572      * We read the other peer indices
 573      */
 574     OTHER_PEER_INDEX,
 575
 576   } state;
 577   int status;
 578
 579   status = GNUNET_SYSERR;
 580   if (GNUNET_YES != GNUNET_DISK_file_test (filename))
 581   {
 582     LOG (GNUNET_ERROR_TYPE_ERROR, _("Topology file %s not found\n"), filename);
 583     return;
 584   }
 585   if (GNUNET_OK !=
 586       GNUNET_DISK_file_size (filename, &fs, GNUNET_YES, GNUNET_YES))
 587   {
 588     LOG (GNUNET_ERROR_TYPE_ERROR, _("Topology file %s has no data\n"), filename);
 589     return;
 590   }
 591   data = GNUNET_malloc (fs);
 592   if (fs != GNUNET_DISK_fn_read (filename, data, fs))
 593   {
 594     LOG (GNUNET_ERROR_TYPE_ERROR, _("Topology file %s cannot be read\n"),
 595          filename);
 596     goto _exit;
 597   }
 598
 599   offset = 0;
 600   peer_id = 0;
 601   state = PEER_INDEX;
 602   buf = data;
 603   while (offset < fs)
 604   {
 605     if (0 != isspace (data[offset]))
 606     {
 607       offset++;
 608       continue;
 609     }
 610     switch (state)
 611     {
 612     case PEER_INDEX:
 613       buf = strchr (&data[offset], ':');
 614       if (NULL == buf)
 615       {
 616         LOG (GNUNET_ERROR_TYPE_ERROR,
 617              _("Failed to read peer index from toology file: %s"), filename);
 618         goto _exit;
 619       }
 620       *buf = '\0';
 621       errno = 0;
 622       peer_id = (unsigned int) strtoul (&data[offset], &end, 10);
 623       if (0 != errno)
 624       {
 625         LOG (GNUNET_ERROR_TYPE_ERROR,
 626              _("Value in given topology file: %s out of range\n"), filename);
 627         goto _exit;
 628       }
 629       if (&data[offset] == end)
 630       {
 631         LOG (GNUNET_ERROR_TYPE_ERROR,
 632              _("Failed to read peer index from topology file: %s"), filename);
 633         goto _exit;
 634       }
 635       if (tc->num_peers <= peer_id)
 636       {
 637         LOG (GNUNET_ERROR_TYPE_ERROR,
 638              _("Topology file needs more peers than given ones\n"),
 639              filename);
 640         goto _exit;
 641       }
 642       state = OTHER_PEER_INDEX;
 643       offset += ((unsigned int) (buf - &data[offset])) + 1;
 644       break;
 645     case OTHER_PEER_INDEX:
 646       errno = 0;
 647       other_peer_id = (unsigned int) strtoul (&data[offset],  &end, 10);
 648       if (0 != errno)
 649       {
 650         LOG (GNUNET_ERROR_TYPE_ERROR,
 651              _("Value in given topology file: %s out of range\n"), filename);
 652         goto _exit;
 653       }
 654       if (&data[offset] == end)
 655       {
 656         LOG (GNUNET_ERROR_TYPE_ERROR,
 657              _("Failed to read peer index from topology file: %s"), filename);
 658         goto _exit;
 659       }
 660       if (tc->num_peers <= other_peer_id)
 661       {
 662         LOG (GNUNET_ERROR_TYPE_ERROR,
 663              _("Topology file needs more peers than given ones\n"),
 664              filename);
 665         goto _exit;
 666       }
 667       if (peer_id != other_peer_id)
 668       {
 669         tc->link_array_size++;
 670         tc->link_array = GNUNET_realloc (tc->link_array,
 671                                          sizeof (struct OverlayLink) *
 672                                          tc->link_array_size);
 673         offset += end - &data[offset];
 674         make_link (&tc->link_array[tc->link_array_size - 1], peer_id,
 675                    other_peer_id, tc);
 676       }
 677       else
 678         LOG (GNUNET_ERROR_TYPE_WARNING,
 679              _("Ignoring to connect peer %u to peer %u\n"), peer_id, other_peer_id);
 680       while (('\n' != data[offset]) && ('|' != data[offset])
 681              && (offset < fs))
 682         offset++;
 683       if ('\n' == data[offset])
 684         state = PEER_INDEX;
 685       else if ('|' == data[offset])
 686       {
 687         state = OTHER_PEER_INDEX;
 688         offset++;
 689       }
 690       break;
 691     }
 692   }
 693   status = GNUNET_OK;
 694
 695  _exit:
 696   GNUNET_free (data);
 697   if (GNUNET_OK != status)
 698   {
 699     LOG (GNUNET_ERROR_TYPE_WARNING,
 700          "Removing link data read from the file\n");
 701     tc->link_array_size = 0;
 702     GNUNET_free_non_null (tc->link_array);
 703     tc->link_array = NULL;
 704   }
 705 }
 706
 707
 708 /**
 709  * Configure overall network topology to have a particular shape.
 710  *
 711  * @param op_cls closure argument to give with the operation event
 712  * @param num_peers number of peers in 'peers'
 713  * @param peers array of 'num_peers' with the peers to configure
 714  * @param topo desired underlay topology to use
 715  * @param ap topology-specific options
 716  * @return handle to the operation, NULL if configuring the topology
 717  *         is not allowed at this time
 718  */
 719 struct GNUNET_TESTBED_Operation *
 720 GNUNET_TESTBED_underlay_configure_topology_va (void *op_cls,
 721                                                unsigned int num_peers,
 722                                                struct GNUNET_TESTBED_Peer
 723                                                **peers,
 724                                                enum
 725                                                GNUNET_TESTBED_TopologyOption
 726                                                topo, va_list ap)
 727 {
 728   GNUNET_break (0);
 729   return NULL;
 730 }
 731
 732
 733 /**
 734  * Configure overall network topology to have a particular shape.
 735  *
 736  * @param op_cls closure argument to give with the operation event
 737  * @param num_peers number of peers in 'peers'
 738  * @param peers array of 'num_peers' with the peers to configure
 739  * @param topo desired underlay topology to use
 740  * @param ... topology-specific options
 741  * @return handle to the operation, NULL if configuring the topology
 742  *         is not allowed at this time
 743  */
 744 struct GNUNET_TESTBED_Operation *
 745 GNUNET_TESTBED_underlay_configure_topology (void *op_cls,
 746                                             unsigned int num_peers,
 747                                             struct GNUNET_TESTBED_Peer **peers,
 748                                             enum GNUNET_TESTBED_TopologyOption
 749                                             topo, ...)
 750 {
 751   GNUNET_break (0);
 752   return NULL;
 753 }
 754
 755
 756 /**
 757  * All peers must have been started before calling this function.
 758  * This function then connects the given peers in the P2P overlay
 759  * using the given topology.
 760  *
 761  * @param op_cls closure argument to give with the operation event
 762  * @param num_peers number of peers in 'peers'
 763  * @param peers array of 'num_peers' with the peers to configure
 764  * @param max_connections the maximums number of overlay connections that will
 765  *          be made to achieve the given topology
 766  * @param topo desired underlay topology to use
 767  * @param va topology-specific options
 768  * @return handle to the operation, NULL if connecting these
 769  *         peers is fundamentally not possible at this time (peers
 770  *         not running or underlay disallows) or if num_peers is less than 2
 771  */
 772 struct GNUNET_TESTBED_Operation *
 773 GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls,
 774                                               unsigned int num_peers,
 775                                               struct GNUNET_TESTBED_Peer **peers,
 776                                               unsigned int *max_connections,
 777                                               enum GNUNET_TESTBED_TopologyOption
 778                                               topo, va_list va)
 779 {
 780   struct TopologyContext *tc;
 781   struct GNUNET_TESTBED_Operation *op;
 782   struct GNUNET_TESTBED_Controller *c;
 783   enum GNUNET_TESTBED_TopologyOption secondary_option;
 784   unsigned int cnt;
 785
 786   if (num_peers < 2)
 787     return NULL;
 788   c = peers[0]->controller;
 789   tc = GNUNET_malloc (sizeof (struct TopologyContext));
 790   tc->peers = peers;
 791   tc->num_peers = num_peers;
 792   tc->op_cls = op_cls;
 793   switch (topo)
 794   {
 795   case GNUNET_TESTBED_TOPOLOGY_LINE:
 796     gen_topo_line (tc);
 797     break;
 798   case GNUNET_TESTBED_TOPOLOGY_RING:
 799     gen_topo_ring (tc);
 800     break;
 801   case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
 802     gen_topo_random (tc,
 803                      va_arg (va, unsigned int),
 804                      GNUNET_NO);
 805     break;
 806   case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
 807     gen_topo_ring (tc);
 808     gen_topo_random (tc,
 809                      va_arg (va, unsigned int),
 810                      GNUNET_YES);
 811     break;
 812   case GNUNET_TESTBED_TOPOLOGY_CLIQUE:
 813     tc->link_array_size = num_peers * (num_peers - 1);
 814     tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
 815                                     tc->link_array_size);
 816     {
 817       unsigned int offset;
 818
 819       offset = 0;
 820       for (cnt=0; cnt < num_peers; cnt++)
 821       {
 822         unsigned int neighbour;
 823
 824         for (neighbour=0; neighbour < num_peers; neighbour++)
 825         {
 826           if (neighbour == cnt)
 827             continue;
 828           tc->link_array[offset].A = cnt;
 829           tc->link_array[offset].B = neighbour;
 830           tc->link_array[offset].tc = tc;
 831           offset++;
 832         }
 833       }
 834     }
 835     break;
 836   case GNUNET_TESTBED_TOPOLOGY_2D_TORUS:
 837     gen_topo_2dtorus (tc);
 838     break;
 839   case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD:
 840     gen_topo_2dtorus (tc);
 841     gen_topo_random (tc,
 842                      va_arg (va, unsigned int),
 843                      GNUNET_YES);
 844     break;
 845   case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
 846     gen_scale_free (tc);
 847     break;
 848   case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
 849     {
 850       const char *filename;
 851
 852       filename = va_arg (va, const char *);
 853       GNUNET_assert (NULL != filename);
 854       gen_topo_from_file (tc, filename);
 855     }
 856     break;
 857   default:
 858     GNUNET_break (0);
 859     GNUNET_free (tc);
 860     return NULL;
 861   }
 862   do
 863   {
 864     secondary_option = va_arg (va, enum GNUNET_TESTBED_TopologyOption);
 865     switch (secondary_option)
 866     {
 867     case GNUNET_TESTBED_TOPOLOGY_DISABLE_AUTO_RETRY:
 868       tc->disable_retry = GNUNET_YES;
 869       break;
 870     case GNUNET_TESTBED_TOPOLOGY_OPTION_END:
 871       break;
 872     default:
 873       GNUNET_break (0);         /* Should not use any other option apart from
 874                                    the ones handled here */
 875       GNUNET_free_non_null (tc->link_array);
 876       GNUNET_free (tc);
 877       return NULL;
 878     }
 879   } while (GNUNET_TESTBED_TOPOLOGY_OPTION_END != secondary_option);
 880   op = GNUNET_TESTBED_operation_create_ (tc,
 881                                          &opstart_overlay_configure_topology,
 882                                          &oprelease_overlay_configure_topology);
 883   GNUNET_TESTBED_operation_queue_insert_
 884       (c->opq_parallel_topology_config_operations, op);
 885   GNUNET_TESTBED_operation_begin_wait_ (op);
 886   LOG (GNUNET_ERROR_TYPE_DEBUG,
 887        "Generated %u connections\n", tc->link_array_size);
 888   if (NULL != max_connections)
 889     *max_connections = tc->link_array_size;
 890   return op;
 891 }
 892
 893
 894 /**
 895  * All peers must have been started before calling this function.
 896  * This function then connects the given peers in the P2P overlay
 897  * using the given topology.
 898  *
 899  * @param op_cls closure argument to give with the operation event
 900  * @param num_peers number of peers in 'peers'
 901  * @param peers array of 'num_peers' with the peers to configure
 902  * @param max_connections the maximums number of overlay connections that will
 903  *          be made to achieve the given topology
 904  * @param topo desired underlay topology to use
 905  * @param ... topology-specific options
 906  * @return handle to the operation, NULL if connecting these
 907  *         peers is fundamentally not possible at this time (peers
 908  *         not running or underlay disallows) or if num_peers is less than 2
 909  */
 910 struct GNUNET_TESTBED_Operation *
 911 GNUNET_TESTBED_overlay_configure_topology (void *op_cls, unsigned int num_peers,
 912                                            struct GNUNET_TESTBED_Peer **peers,
 913                                            unsigned int *max_connections,
 914                                            enum GNUNET_TESTBED_TopologyOption
 915                                            topo, ...)
 916 {
 917   struct GNUNET_TESTBED_Operation *op;
 918   va_list vargs;
 919
 920   GNUNET_assert (topo < GNUNET_TESTBED_TOPOLOGY_OPTION_END);
 921   va_start (vargs, topo);
 922   op = GNUNET_TESTBED_overlay_configure_topology_va (op_cls, num_peers, peers,
 923                                                      max_connections,
 924                                                      topo, vargs);
 925   va_end (vargs);
 926   return op;
 927 }
 928
 929
 930 /**
 931  * Get a topology from a string input.
 932  *
 933  * @param topology where to write the retrieved topology
 934  * @param topology_string The string to attempt to
 935  *        get a configuration value from
 936  * @return GNUNET_YES if topology string matched a
 937  *         known topology, GNUNET_NO if not
 938  */
 939 int
 940 GNUNET_TESTBED_topology_get_ (enum GNUNET_TESTBED_TopologyOption *topology,
 941                               const char *topology_string)
 942 {
 943   unsigned int cnt;
 944
 945   for (cnt = 0; NULL != topology_strings[cnt]; cnt++)
 946   {
 947     if (0 == strcasecmp (topology_string, topology_strings[cnt]))
 948     {
 949       if (NULL != topology)
 950         *topology = (enum GNUNET_TESTBED_TopologyOption) cnt;
 951       return GNUNET_YES;
 952     }
 953   }
 954   return GNUNET_NO;
 955 }
 956
 957
 958 /**
 959  * Returns the string corresponding to the given topology
 960  *
 961  * @param topology the topology
 962  * @return the string (freshly allocated) of given topology; NULL if topology cannot be
 963  *           expressed as a string
 964  */
 965 char *
 966 GNUNET_TESTBED_topology_to_str_ (enum GNUNET_TESTBED_TopologyOption topology)
 967 {
 968   if (GNUNET_TESTBED_TOPOLOGY_OPTION_END <= topology)
 969     return NULL;
 970   return GNUNET_strdup (topology_strings[topology]);
 971 }
 972
 973 /* end of testbed_api_topology.c */