src/testbed/testbed_api_topology.c

   1 /*
   2       This file is part of GNUnet
   3       (C) 2008--2013 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  * @return the number of links that are required to generate a 2d torus for the
 433  *           given number of peers
 434  */
 435 unsigned int
 436 GNUNET_TESTBED_2dtorus_calc_links (unsigned int num_peers, unsigned int *rows,
 437                                    unsigned int **rows_len)
 438 {
 439   double sq;
 440   unsigned int sq_floor;
 441   unsigned int _rows;
 442   unsigned int *_rows_len;
 443   unsigned int x;
 444   unsigned int y;
 445   unsigned int _num_peers;
 446   unsigned int cnt;
 447
 448   sq = sqrt (num_peers);
 449   sq = floor (sq);
 450   sq_floor = (unsigned int) sq;
 451   _rows = (sq_floor + 1);
 452   _rows_len = GNUNET_malloc (sizeof (unsigned int) * _rows);
 453   for (y = 0; y < _rows - 1; y++)
 454     _rows_len[y] = sq_floor;
 455   _num_peers = sq_floor * sq_floor;
 456   cnt = (_num_peers < 2) ? _num_peers : 2 * _num_peers;
 457   x = 0;
 458   y = 0;
 459   while (_num_peers < num_peers)
 460   {
 461     if (x < y)
 462       _rows_len[_rows - 1] = ++x;
 463     else
 464       _rows_len[y++]++;
 465     _num_peers++;
 466   }
 467   cnt += (x < 2) ? x : 2 * x;
 468   cnt += (y < 2) ? y : 2 * y;
 469   if (0 == _rows_len[_rows - 1])
 470     _rows--;
 471   if (NULL != rows)
 472     *rows = _rows;
 473   if (NULL != rows_len)
 474     *rows_len = _rows_len;
 475   else
 476     GNUNET_free (_rows_len);
 477   return cnt;
 478 }
 479
 480
 481 /**
 482  * Generates ring topology
 483  *
 484  * @param tc the topology context
 485  */
 486 static void
 487 gen_topo_2dtorus (struct TopologyContext *tc)
 488 {
 489   unsigned int rows;
 490   unsigned int *rows_len;
 491   unsigned int x;
 492   unsigned int y;
 493   unsigned int cnt;
 494   unsigned int offset;
 495
 496   tc->link_array_size =
 497       GNUNET_TESTBED_2dtorus_calc_links (tc->num_peers, &rows, &rows_len);
 498   tc->link_array =
 499       GNUNET_malloc (sizeof (struct OverlayLink) * tc->link_array_size);
 500   cnt = 0;
 501   offset = 0;
 502   for (y = 0; y < rows; y++)
 503   {
 504     for (x = 0; x < rows_len[y] - 1; x++)
 505     {
 506       make_link (&tc->link_array[cnt], offset + x, offset + x + 1, tc);
 507       cnt++;
 508     }
 509     if (0 == x)
 510       break;
 511     make_link (&tc->link_array[cnt], offset + x, offset, tc);
 512     cnt++;
 513     offset += rows_len[y];
 514   }
 515   for (x = 0; x < rows_len[0]; x++)
 516   {
 517     offset = 0;
 518     for (y = 0; y < rows - 1; y++)
 519     {
 520       if (x >= rows_len[y + 1])
 521         break;
 522       GNUNET_assert (x < rows_len[y + 1]);
 523       make_link (&tc->link_array[cnt], offset + x, offset + rows_len[y] + x,
 524                  tc);
 525       offset += rows_len[y];
 526       cnt++;
 527     }
 528     if (0 == offset)
 529       break;
 530     make_link (&tc->link_array[cnt], offset + x, x, tc);
 531     cnt++;
 532   }
 533   GNUNET_assert (cnt == tc->link_array_size);
 534   GNUNET_free (rows_len);
 535 }
 536
 537
 538 /**
 539  * Generates ring topology
 540  *
 541  * @param tc the topology context
 542  * @param links the number of random links to establish
 543  * @param append GNUNET_YES to add links to existing link array; GNUNET_NO to
 544  *          create a new link array
 545  */
 546 static void
 547 gen_topo_random (struct TopologyContext *tc, unsigned int links, int append)
 548 {
 549   unsigned int cnt;
 550   unsigned int index;
 551   uint32_t A_rand;
 552   uint32_t B_rand;
 553
 554   if (GNUNET_YES == append)
 555   {
 556     GNUNET_assert ((0 < tc->link_array_size) && (NULL != tc->link_array));
 557     index = tc->link_array_size;
 558     tc->link_array_size += links;
 559     tc->link_array =
 560         GNUNET_realloc (tc->link_array,
 561                         sizeof (struct OverlayLink) * tc->link_array_size);
 562   }
 563   else
 564   {
 565     GNUNET_assert ((0 == tc->link_array_size) && (NULL == tc->link_array));
 566     index = 0;
 567     tc->link_array_size = links;
 568     tc->link_array =
 569         GNUNET_malloc (sizeof (struct OverlayLink) * tc->link_array_size);
 570   }
 571   for (cnt = 0; cnt < links; cnt++)
 572   {
 573     do
 574     {
 575       A_rand =
 576           GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, tc->num_peers);
 577       B_rand =
 578           GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, tc->num_peers);
 579     }
 580     while (A_rand == B_rand);
 581     make_link (&tc->link_array[index + cnt], A_rand, B_rand, tc);
 582   }
 583 }
 584
 585
 586 /**
 587  * Generates scale free network. Its construction is described in:
 588  *
 589  * "Emergence of Scaling in Random Networks." Science 286, 509-512, 1999.
 590  *
 591  * @param tc the topology context
 592  * @param cap maximum allowed node degree
 593  * @param m number of edges to establish for a new node when it is added to the
 594  *   network
 595  */
 596 static void
 597 gen_scale_free (struct TopologyContext *tc, uint16_t cap, uint8_t m)
 598 {
 599   unsigned int *deg;
 600   unsigned int *etab;
 601   unsigned int *used;
 602   unsigned int etaboff;
 603   unsigned int cnt;
 604   unsigned int cnt2;
 605   unsigned int peer;
 606   unsigned int random_peer;
 607   unsigned int links;
 608   unsigned int off;
 609   unsigned int redo_threshold;
 610
 611   etaboff = 0;
 612   tc->link_array_size = tc->num_peers * m;
 613   tc->link_array = GNUNET_malloc_large (sizeof (struct OverlayLink) *
 614                                         tc->link_array_size);
 615   etab = GNUNET_malloc_large (sizeof (unsigned int) * 2 * tc->link_array_size);
 616   deg = GNUNET_malloc (sizeof (unsigned int) * tc->num_peers);
 617   used = GNUNET_malloc (sizeof (unsigned int) * m);
 618   /* start by connecting peer 1 to peer 0 */
 619   make_link (&tc->link_array[0], 0, 1, tc);
 620   deg[0]++;
 621   deg[1]++;
 622   etab[etaboff++] = 0;
 623   etab[etaboff++] = 1;
 624   links = 1;
 625   for (peer = 2; peer < tc->num_peers; peer++)
 626   {
 627     if (cap < deg[peer])
 628       continue;
 629     for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
 630     {
 631       redo_threshold = 0;
 632     redo:
 633       off = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, etaboff);
 634       random_peer = etab[off];
 635       if (cap < deg[random_peer])
 636       {
 637         if (++redo_threshold > GNUNET_MAX (1, cap / 2))
 638         {
 639           redo_threshold = 0;
 640           off = 0;
 641           for (cnt2 = 0; cnt2 < etaboff; cnt2++)
 642           {
 643             if (random_peer == etab[cnt2])
 644             {
 645               off++;
 646               continue;
 647             }
 648             etab[cnt2 - off] = etab[cnt2];
 649           }
 650           etaboff -= off;
 651         }
 652         goto redo;
 653       }
 654       for (cnt2 = 0; cnt2 < cnt; cnt2++)
 655         if (random_peer == used[cnt2])
 656           goto redo;
 657       make_link (&tc->link_array[links + cnt], random_peer, peer, tc);
 658       deg[random_peer]++;
 659       deg[peer]++;
 660       used[cnt] = random_peer;
 661     }
 662     for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
 663     {
 664       etab[etaboff++] = used[cnt];
 665       etab[etaboff++] = peer;
 666     }
 667     links += GNUNET_MIN (peer, m);
 668   }
 669   GNUNET_free (etab);
 670   GNUNET_free (used);
 671   GNUNET_free (deg);
 672   GNUNET_assert (links <= tc->link_array_size);
 673   tc->link_array_size = links;
 674   tc->link_array =
 675       GNUNET_realloc (tc->link_array,
 676                       sizeof (struct OverlayLink) * tc->link_array_size);
 677 }
 678
 679
 680 /**
 681  * Generates topology from the given file
 682  *
 683  * @param tc the topology context
 684  * @param filename the filename of the file containing topology data
 685  */
 686 static void
 687 gen_topo_from_file (struct TopologyContext *tc, const char *filename)
 688 {
 689   char *data;
 690   char *end;
 691   char *buf;
 692   uint64_t fs;
 693   uint64_t offset;
 694   unsigned long int peer_id;
 695   unsigned long int other_peer_id;
 696   enum ParseState
 697   {
 698
 699     /**
 700      * We read the peer index
 701      */
 702     PEER_INDEX,
 703
 704     /**
 705      * We read the other peer indices
 706      */
 707     OTHER_PEER_INDEX,
 708
 709   } state;
 710   int status;
 711
 712   status = GNUNET_SYSERR;
 713   if (GNUNET_YES != GNUNET_DISK_file_test (filename))
 714   {
 715     LOG (GNUNET_ERROR_TYPE_ERROR, _("Topology file %s not found\n"), filename);
 716     return;
 717   }
 718   if (GNUNET_OK !=
 719       GNUNET_DISK_file_size (filename, &fs, GNUNET_YES, GNUNET_YES))
 720   {
 721     LOG (GNUNET_ERROR_TYPE_ERROR, _("Topology file %s has no data\n"),
 722          filename);
 723     return;
 724   }
 725   data = GNUNET_malloc (fs);
 726   if (fs != GNUNET_DISK_fn_read (filename, data, fs))
 727   {
 728     LOG (GNUNET_ERROR_TYPE_ERROR, _("Topology file %s cannot be read\n"),
 729          filename);
 730     goto _exit;
 731   }
 732
 733   offset = 0;
 734   peer_id = 0;
 735   state = PEER_INDEX;
 736   while (offset < fs)
 737   {
 738     if (0 != isspace (data[offset]))
 739     {
 740       offset++;
 741       continue;
 742     }
 743     switch (state)
 744     {
 745     case PEER_INDEX:
 746       buf = strchr (&data[offset], ':');
 747       if (NULL == buf)
 748       {
 749         LOG (GNUNET_ERROR_TYPE_ERROR,
 750              _("Failed to read peer index from toology file: %s"), filename);
 751         goto _exit;
 752       }
 753       *buf = '\0';
 754       errno = 0;
 755       peer_id = (unsigned int) strtoul (&data[offset], &end, 10);
 756       if (0 != errno)
 757       {
 758         LOG (GNUNET_ERROR_TYPE_ERROR,
 759              _("Value in given topology file: %s out of range\n"), filename);
 760         goto _exit;
 761       }
 762       if (&data[offset] == end)
 763       {
 764         LOG (GNUNET_ERROR_TYPE_ERROR,
 765              _("Failed to read peer index from topology file: %s"), filename);
 766         goto _exit;
 767       }
 768       if (tc->num_peers <= peer_id)
 769       {
 770         LOG (GNUNET_ERROR_TYPE_ERROR,
 771              _("Topology file needs more peers than given ones\n"), filename);
 772         goto _exit;
 773       }
 774       state = OTHER_PEER_INDEX;
 775       offset += ((unsigned int) (buf - &data[offset])) + 1;
 776       break;
 777     case OTHER_PEER_INDEX:
 778       errno = 0;
 779       other_peer_id = (unsigned int) strtoul (&data[offset], &end, 10);
 780       if (0 != errno)
 781       {
 782         LOG (GNUNET_ERROR_TYPE_ERROR,
 783              _("Value in given topology file: %s out of range\n"), filename);
 784         goto _exit;
 785       }
 786       if (&data[offset] == end)
 787       {
 788         LOG (GNUNET_ERROR_TYPE_ERROR,
 789              _("Failed to read peer index from topology file: %s"), filename);
 790         goto _exit;
 791       }
 792       if (tc->num_peers <= other_peer_id)
 793       {
 794         LOG (GNUNET_ERROR_TYPE_ERROR,
 795              _("Topology file needs more peers than given ones\n"), filename);
 796         goto _exit;
 797       }
 798       if (peer_id != other_peer_id)
 799       {
 800         tc->link_array_size++;
 801         tc->link_array =
 802             GNUNET_realloc (tc->link_array,
 803                             sizeof (struct OverlayLink) * tc->link_array_size);
 804         offset += end - &data[offset];
 805         make_link (&tc->link_array[tc->link_array_size - 1], peer_id,
 806                    other_peer_id, tc);
 807       }
 808       else
 809         LOG (GNUNET_ERROR_TYPE_WARNING,
 810              _("Ignoring to connect peer %u to peer %u\n"), peer_id,
 811              other_peer_id);
 812       while (('\n' != data[offset]) && ('|' != data[offset]) && (offset < fs))
 813         offset++;
 814       if ('\n' == data[offset])
 815         state = PEER_INDEX;
 816       else if ('|' == data[offset])
 817       {
 818         state = OTHER_PEER_INDEX;
 819         offset++;
 820       }
 821       break;
 822     }
 823   }
 824   status = GNUNET_OK;
 825
 826 _exit:
 827   GNUNET_free (data);
 828   if (GNUNET_OK != status)
 829   {
 830     LOG (GNUNET_ERROR_TYPE_WARNING, "Removing link data read from the file\n");
 831     tc->link_array_size = 0;
 832     GNUNET_free_non_null (tc->link_array);
 833     tc->link_array = NULL;
 834   }
 835 }
 836
 837
 838 /**
 839  * Configure overall network topology to have a particular shape.
 840  *
 841  * @param op_cls closure argument to give with the operation event
 842  * @param num_peers number of peers in 'peers'
 843  * @param peers array of 'num_peers' with the peers to configure
 844  * @param topo desired underlay topology to use
 845  * @param ap topology-specific options
 846  * @return handle to the operation, NULL if configuring the topology
 847  *         is not allowed at this time
 848  */
 849 struct GNUNET_TESTBED_Operation *
 850 GNUNET_TESTBED_underlay_configure_topology_va (void *op_cls,
 851                                                unsigned int num_peers,
 852                                                struct GNUNET_TESTBED_Peer
 853                                                **peers,
 854                                                enum
 855                                                GNUNET_TESTBED_TopologyOption
 856                                                topo, va_list ap)
 857 {
 858   GNUNET_break (0);
 859   return NULL;
 860 }
 861
 862
 863 /**
 864  * Configure overall network topology to have a particular shape.
 865  *
 866  * @param op_cls closure argument to give with the operation event
 867  * @param num_peers number of peers in 'peers'
 868  * @param peers array of 'num_peers' with the peers to configure
 869  * @param topo desired underlay topology to use
 870  * @param ... topology-specific options
 871  * @return handle to the operation, NULL if configuring the topology
 872  *         is not allowed at this time
 873  */
 874 struct GNUNET_TESTBED_Operation *
 875 GNUNET_TESTBED_underlay_configure_topology (void *op_cls,
 876                                             unsigned int num_peers,
 877                                             struct GNUNET_TESTBED_Peer **peers,
 878                                             enum GNUNET_TESTBED_TopologyOption
 879                                             topo, ...)
 880 {
 881   GNUNET_break (0);
 882   return NULL;
 883 }
 884
 885
 886 /**
 887  * All peers must have been started before calling this function.
 888  * This function then connects the given peers in the P2P overlay
 889  * using the given topology.
 890  *
 891  * @param op_cls closure argument to give with the peer connect operation events
 892  *          generated through this function
 893  * @param num_peers number of peers in 'peers'
 894  * @param peers array of 'num_peers' with the peers to configure
 895  * @param max_connections the maximums number of overlay connections that will
 896  *          be made to achieve the given topology
 897  * @param comp_cb the completion callback to call when the topology generation
 898  *          is completed
 899  * @param comp_cb_cls closure for the above completion callback
 900  * @param topo desired underlay topology to use
 901  * @param va topology-specific options
 902  * @return handle to the operation, NULL if connecting these
 903  *         peers is fundamentally not possible at this time (peers
 904  *         not running or underlay disallows) or if num_peers is less than 2
 905  */
 906 struct GNUNET_TESTBED_Operation *
 907 GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls,
 908                                               unsigned int num_peers,
 909                                               struct GNUNET_TESTBED_Peer **peers,
 910                                               unsigned int *max_connections,
 911                                               GNUNET_TESTBED_TopologyCompletionCallback
 912                                               comp_cb,
 913                                               void *comp_cb_cls,
 914                                               enum GNUNET_TESTBED_TopologyOption topo,
 915                                               va_list va)
 916 {
 917   struct TopologyContext *tc;
 918   struct GNUNET_TESTBED_Operation *op;
 919   struct GNUNET_TESTBED_Controller *c;
 920   enum GNUNET_TESTBED_TopologyOption secondary_option;
 921   unsigned int cnt;
 922
 923   if (num_peers < 2)
 924     return NULL;
 925   c = peers[0]->controller;
 926   tc = GNUNET_malloc (sizeof (struct TopologyContext));
 927   tc->peers = peers;
 928   tc->num_peers = num_peers;
 929   tc->op_cls = op_cls;
 930   tc->retry_cnt = DEFAULT_RETRY_CNT;
 931   tc->comp_cb = comp_cb;
 932   tc->comp_cb_cls = comp_cb_cls;
 933   switch (topo)
 934   {
 935   case GNUNET_TESTBED_TOPOLOGY_LINE:
 936     gen_topo_line (tc);
 937     break;
 938   case GNUNET_TESTBED_TOPOLOGY_RING:
 939     gen_topo_ring (tc);
 940     break;
 941   case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
 942     gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_NO);
 943     break;
 944   case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
 945     gen_topo_ring (tc);
 946     gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_YES);
 947     break;
 948   case GNUNET_TESTBED_TOPOLOGY_CLIQUE:
 949     tc->link_array_size = num_peers * (num_peers - 1);
 950     tc->link_array =
 951         GNUNET_malloc (sizeof (struct OverlayLink) * tc->link_array_size);
 952     {
 953       unsigned int offset;
 954
 955       offset = 0;
 956       for (cnt = 0; cnt < num_peers; cnt++)
 957       {
 958         unsigned int neighbour;
 959
 960         for (neighbour = 0; neighbour < num_peers; neighbour++)
 961         {
 962           if (neighbour == cnt)
 963             continue;
 964           tc->link_array[offset].A = cnt;
 965           tc->link_array[offset].B = neighbour;
 966           tc->link_array[offset].tc = tc;
 967           offset++;
 968         }
 969       }
 970     }
 971     break;
 972   case GNUNET_TESTBED_TOPOLOGY_2D_TORUS:
 973     gen_topo_2dtorus (tc);
 974     break;
 975   case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD:
 976     gen_topo_2dtorus (tc);
 977     gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_YES);
 978
 979     break;
 980   case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
 981     {
 982       uint16_t cap;
 983       uint8_t m;
 984
 985       cap = (uint16_t) va_arg (va, unsigned int);
 986       m = (uint8_t) va_arg (va, unsigned int);
 987       gen_scale_free (tc, cap, m);
 988     }
 989     break;
 990   case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
 991   {
 992     const char *filename;
 993
 994     filename = va_arg (va, const char *);
 995
 996     GNUNET_assert (NULL != filename);
 997     gen_topo_from_file (tc, filename);
 998   }
 999     break;
1000   default:
1001     GNUNET_break (0);
1002     GNUNET_free (tc);
1003     return NULL;
1004   }
1005   do
1006   {
1007     secondary_option = va_arg (va, enum GNUNET_TESTBED_TopologyOption);
1008
1009     switch (secondary_option)
1010     {
1011     case GNUNET_TESTBED_TOPOLOGY_RETRY_CNT:
1012       tc->retry_cnt =  va_arg (va, unsigned int);
1013       break;
1014     case GNUNET_TESTBED_TOPOLOGY_OPTION_END:
1015       break;
1016     default:
1017       GNUNET_break (0);         /* Should not use any other option apart from
1018                                  * the ones handled here */
1019       GNUNET_free_non_null (tc->link_array);
1020       GNUNET_free (tc);
1021       return NULL;
1022     }
1023   }
1024   while (GNUNET_TESTBED_TOPOLOGY_OPTION_END != secondary_option);
1025   op = GNUNET_TESTBED_operation_create_ (tc,
1026                                          &opstart_overlay_configure_topology,
1027                                          &oprelease_overlay_configure_topology);
1028   GNUNET_TESTBED_operation_queue_insert_
1029       (c->opq_parallel_topology_config_operations, op);
1030   GNUNET_TESTBED_operation_begin_wait_ (op);
1031   LOG (GNUNET_ERROR_TYPE_DEBUG, "Generated %u connections\n",
1032        tc->link_array_size);
1033   if (NULL != max_connections)
1034     *max_connections = tc->link_array_size;
1035   return op;
1036 }
1037
1038
1039 /**
1040  * All peers must have been started before calling this function.
1041  * This function then connects the given peers in the P2P overlay
1042  * using the given topology.
1043  *
1044  * @param op_cls closure argument to give with the peer connect operation events
1045  *          generated through this function
1046  * @param num_peers number of peers in 'peers'
1047  * @param peers array of 'num_peers' with the peers to configure
1048  * @param max_connections the maximums number of overlay connections that will
1049  *          be made to achieve the given topology
1050  * @param comp_cb the completion callback to call when the topology generation
1051  *          is completed
1052  * @param comp_cb_cls closure for the above completion callback
1053  * @param topo desired underlay topology to use
1054  * @param ... topology-specific options
1055  * @return handle to the operation, NULL if connecting these
1056  *         peers is fundamentally not possible at this time (peers
1057  *         not running or underlay disallows) or if num_peers is less than 2
1058  */
1059 struct GNUNET_TESTBED_Operation *
1060 GNUNET_TESTBED_overlay_configure_topology (void *op_cls,
1061                                            unsigned int num_peers,
1062                                            struct GNUNET_TESTBED_Peer **peers,
1063                                            unsigned int *max_connections,
1064                                            GNUNET_TESTBED_TopologyCompletionCallback
1065                                            comp_cb,
1066                                            void *comp_cb_cls,
1067                                            enum GNUNET_TESTBED_TopologyOption topo,
1068                                            ...)
1069 {
1070   struct GNUNET_TESTBED_Operation *op;
1071   va_list vargs;
1072
1073   GNUNET_assert (topo < GNUNET_TESTBED_TOPOLOGY_OPTION_END);
1074   va_start (vargs, topo);
1075   op = GNUNET_TESTBED_overlay_configure_topology_va (op_cls, num_peers, peers,
1076                                                      max_connections,
1077                                                      comp_cb, comp_cb_cls,
1078                                                      topo,
1079                                                      vargs);
1080   va_end (vargs);
1081   return op;
1082 }
1083
1084
1085 /**
1086  * Get a topology from a string input.
1087  *
1088  * @param topology where to write the retrieved topology
1089  * @param topology_string The string to attempt to
1090  *        get a configuration value from
1091  * @return GNUNET_YES if topology string matched a
1092  *         known topology, GNUNET_NO if not
1093  */
1094 int
1095 GNUNET_TESTBED_topology_get_ (enum GNUNET_TESTBED_TopologyOption *topology,
1096                               const char *topology_string)
1097 {
1098   unsigned int cnt;
1099
1100   for (cnt = 0; NULL != topology_strings[cnt]; cnt++)
1101   {
1102     if (0 == strcasecmp (topology_string, topology_strings[cnt]))
1103     {
1104       if (NULL != topology)
1105         *topology = (enum GNUNET_TESTBED_TopologyOption) cnt;
1106       return GNUNET_YES;
1107     }
1108   }
1109   return GNUNET_NO;
1110 }
1111
1112
1113 /**
1114  * Returns the string corresponding to the given topology
1115  *
1116  * @param topology the topology
1117  * @return the string (freshly allocated) of given topology; NULL if topology cannot be
1118  *           expressed as a string
1119  */
1120 char *
1121 GNUNET_TESTBED_topology_to_str_ (enum GNUNET_TESTBED_TopologyOption topology)
1122 {
1123   if (GNUNET_TESTBED_TOPOLOGY_OPTION_END <= topology)
1124     return NULL;
1125   return GNUNET_strdup (topology_strings[topology]);
1126 }
1127
1128 /* end of testbed_api_topology.c */