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