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   links = 0;
 612   etaboff = 0;
 613   tc->link_array_size = tc->num_peers * m;
 614   tc->link_array = GNUNET_malloc_large (sizeof (struct OverlayLink) *
 615                                         tc->link_array_size);
 616   etab = GNUNET_malloc_large (sizeof (unsigned int) * 2 * tc->link_array_size);
 617   deg = GNUNET_malloc (sizeof (unsigned int) * tc->num_peers);
 618   used = GNUNET_malloc (sizeof (unsigned int) * m);
 619   /* start by connecting peer 1 to peer 0 */
 620   make_link (&tc->link_array[0], 0, 1, tc);
 621   deg[0]++;
 622   deg[1]++;
 623   etab[etaboff++] = 0;
 624   etab[etaboff++] = 1;
 625   links = 1;
 626   for (peer = 2; peer < tc->num_peers; peer++)
 627   {
 628     if (cap < deg[peer])
 629       continue;
 630     for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
 631     {
 632       redo_threshold = 0;
 633     redo:
 634       off = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, etaboff);
 635       random_peer = etab[off];
 636       if (cap < deg[random_peer])
 637       {
 638         if (++redo_threshold > GNUNET_MAX (1, cap / 2))
 639         {
 640           redo_threshold = 0;
 641           off = 0;
 642           for (cnt2 = 0; cnt2 < etaboff; cnt2++)
 643           {
 644             if (random_peer == etab[cnt2])
 645             {
 646               off++;
 647               continue;
 648             }
 649             etab[cnt2 - off] = etab[cnt2];
 650           }
 651           etaboff -= off;
 652         }
 653         goto redo;
 654       }
 655       for (cnt2 = 0; cnt2 < cnt; cnt2++)
 656         if (random_peer == used[cnt2])
 657           goto redo;
 658       make_link (&tc->link_array[links + cnt], random_peer, peer, tc);
 659       deg[random_peer]++;
 660       deg[peer]++;
 661       used[cnt] = random_peer;
 662     }
 663     for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
 664     {
 665       etab[etaboff++] = used[cnt];
 666       etab[etaboff++] = peer;
 667     }
 668     links += GNUNET_MIN (peer, m);
 669   }
 670   GNUNET_free (etab);
 671   GNUNET_free (used);
 672   GNUNET_free (deg);
 673   GNUNET_assert (links <= tc->link_array_size);
 674   tc->link_array_size = links;
 675   tc->link_array =
 676       GNUNET_realloc (tc->link_array,
 677                       sizeof (struct OverlayLink) * tc->link_array_size);
 678 }
 679
 680
 681 /**
 682  * Generates topology from the given file
 683  *
 684  * @param tc the topology context
 685  * @param filename the filename of the file containing topology data
 686  */
 687 static void
 688 gen_topo_from_file (struct TopologyContext *tc, const char *filename)
 689 {
 690   char *data;
 691   char *end;
 692   char *buf;
 693   uint64_t fs;
 694   uint64_t offset;
 695   unsigned long int peer_id;
 696   unsigned long int other_peer_id;
 697   enum ParseState
 698   {
 699
 700     /**
 701      * We read the peer index
 702      */
 703     PEER_INDEX,
 704
 705     /**
 706      * We read the other peer indices
 707      */
 708     OTHER_PEER_INDEX,
 709
 710   } state;
 711   int status;
 712
 713   status = GNUNET_SYSERR;
 714   if (GNUNET_YES != GNUNET_DISK_file_test (filename))
 715   {
 716     LOG (GNUNET_ERROR_TYPE_ERROR, _("Topology file %s not found\n"), filename);
 717     return;
 718   }
 719   if (GNUNET_OK !=
 720       GNUNET_DISK_file_size (filename, &fs, GNUNET_YES, GNUNET_YES))
 721   {
 722     LOG (GNUNET_ERROR_TYPE_ERROR, _("Topology file %s has no data\n"),
 723          filename);
 724     return;
 725   }
 726   data = GNUNET_malloc (fs);
 727   if (fs != GNUNET_DISK_fn_read (filename, data, fs))
 728   {
 729     LOG (GNUNET_ERROR_TYPE_ERROR, _("Topology file %s cannot be read\n"),
 730          filename);
 731     goto _exit;
 732   }
 733
 734   offset = 0;
 735   peer_id = 0;
 736   state = PEER_INDEX;
 737   while (offset < fs)
 738   {
 739     if (0 != isspace (data[offset]))
 740     {
 741       offset++;
 742       continue;
 743     }
 744     switch (state)
 745     {
 746     case PEER_INDEX:
 747       buf = strchr (&data[offset], ':');
 748       if (NULL == buf)
 749       {
 750         LOG (GNUNET_ERROR_TYPE_ERROR,
 751              _("Failed to read peer index from toology file: %s"), filename);
 752         goto _exit;
 753       }
 754       *buf = '\0';
 755       errno = 0;
 756       peer_id = (unsigned int) strtoul (&data[offset], &end, 10);
 757       if (0 != errno)
 758       {
 759         LOG (GNUNET_ERROR_TYPE_ERROR,
 760              _("Value in given topology file: %s out of range\n"), filename);
 761         goto _exit;
 762       }
 763       if (&data[offset] == end)
 764       {
 765         LOG (GNUNET_ERROR_TYPE_ERROR,
 766              _("Failed to read peer index from topology file: %s"), filename);
 767         goto _exit;
 768       }
 769       if (tc->num_peers <= peer_id)
 770       {
 771         LOG (GNUNET_ERROR_TYPE_ERROR,
 772              _("Topology file needs more peers than given ones\n"), filename);
 773         goto _exit;
 774       }
 775       state = OTHER_PEER_INDEX;
 776       offset += ((unsigned int) (buf - &data[offset])) + 1;
 777       break;
 778     case OTHER_PEER_INDEX:
 779       errno = 0;
 780       other_peer_id = (unsigned int) strtoul (&data[offset], &end, 10);
 781       if (0 != errno)
 782       {
 783         LOG (GNUNET_ERROR_TYPE_ERROR,
 784              _("Value in given topology file: %s out of range\n"), filename);
 785         goto _exit;
 786       }
 787       if (&data[offset] == end)
 788       {
 789         LOG (GNUNET_ERROR_TYPE_ERROR,
 790              _("Failed to read peer index from topology file: %s"), filename);
 791         goto _exit;
 792       }
 793       if (tc->num_peers <= other_peer_id)
 794       {
 795         LOG (GNUNET_ERROR_TYPE_ERROR,
 796              _("Topology file needs more peers than given ones\n"), filename);
 797         goto _exit;
 798       }
 799       if (peer_id != other_peer_id)
 800       {
 801         tc->link_array_size++;
 802         tc->link_array =
 803             GNUNET_realloc (tc->link_array,
 804                             sizeof (struct OverlayLink) * tc->link_array_size);
 805         offset += end - &data[offset];
 806         make_link (&tc->link_array[tc->link_array_size - 1], peer_id,
 807                    other_peer_id, tc);
 808       }
 809       else
 810         LOG (GNUNET_ERROR_TYPE_WARNING,
 811              _("Ignoring to connect peer %u to peer %u\n"), peer_id,
 812              other_peer_id);
 813       while (('\n' != data[offset]) && ('|' != data[offset]) && (offset < fs))
 814         offset++;
 815       if ('\n' == data[offset])
 816         state = PEER_INDEX;
 817       else if ('|' == data[offset])
 818       {
 819         state = OTHER_PEER_INDEX;
 820         offset++;
 821       }
 822       break;
 823     }
 824   }
 825   status = GNUNET_OK;
 826
 827 _exit:
 828   GNUNET_free (data);
 829   if (GNUNET_OK != status)
 830   {
 831     LOG (GNUNET_ERROR_TYPE_WARNING, "Removing link data read from the file\n");
 832     tc->link_array_size = 0;
 833     GNUNET_free_non_null (tc->link_array);
 834     tc->link_array = NULL;
 835   }
 836 }
 837
 838
 839 /**
 840  * Configure overall network topology to have a particular shape.
 841  *
 842  * @param op_cls closure argument to give with the operation event
 843  * @param num_peers number of peers in 'peers'
 844  * @param peers array of 'num_peers' with the peers to configure
 845  * @param topo desired underlay topology to use
 846  * @param ap topology-specific options
 847  * @return handle to the operation, NULL if configuring the topology
 848  *         is not allowed at this time
 849  */
 850 struct GNUNET_TESTBED_Operation *
 851 GNUNET_TESTBED_underlay_configure_topology_va (void *op_cls,
 852                                                unsigned int num_peers,
 853                                                struct GNUNET_TESTBED_Peer
 854                                                **peers,
 855                                                enum
 856                                                GNUNET_TESTBED_TopologyOption
 857                                                topo, va_list ap)
 858 {
 859   GNUNET_break (0);
 860   return NULL;
 861 }
 862
 863
 864 /**
 865  * Configure overall network topology to have a particular shape.
 866  *
 867  * @param op_cls closure argument to give with the operation event
 868  * @param num_peers number of peers in 'peers'
 869  * @param peers array of 'num_peers' with the peers to configure
 870  * @param topo desired underlay topology to use
 871  * @param ... topology-specific options
 872  * @return handle to the operation, NULL if configuring the topology
 873  *         is not allowed at this time
 874  */
 875 struct GNUNET_TESTBED_Operation *
 876 GNUNET_TESTBED_underlay_configure_topology (void *op_cls,
 877                                             unsigned int num_peers,
 878                                             struct GNUNET_TESTBED_Peer **peers,
 879                                             enum GNUNET_TESTBED_TopologyOption
 880                                             topo, ...)
 881 {
 882   GNUNET_break (0);
 883   return NULL;
 884 }
 885
 886
 887 /**
 888  * All peers must have been started before calling this function.
 889  * This function then connects the given peers in the P2P overlay
 890  * using the given topology.
 891  *
 892  * @param op_cls closure argument to give with the peer connect operation events
 893  *          generated through this function
 894  * @param num_peers number of peers in 'peers'
 895  * @param peers array of 'num_peers' with the peers to configure
 896  * @param max_connections the maximums number of overlay connections that will
 897  *          be made to achieve the given topology
 898  * @param comp_cb the completion callback to call when the topology generation
 899  *          is completed
 900  * @param comp_cb_cls closure for the above completion callback
 901  * @param topo desired underlay topology to use
 902  * @param va topology-specific options
 903  * @return handle to the operation, NULL if connecting these
 904  *         peers is fundamentally not possible at this time (peers
 905  *         not running or underlay disallows) or if num_peers is less than 2
 906  */
 907 struct GNUNET_TESTBED_Operation *
 908 GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls,
 909                                               unsigned int num_peers,
 910                                               struct GNUNET_TESTBED_Peer **peers,
 911                                               unsigned int *max_connections,
 912                                               GNUNET_TESTBED_TopologyCompletionCallback
 913                                               comp_cb,
 914                                               void *comp_cb_cls,
 915                                               enum GNUNET_TESTBED_TopologyOption topo,
 916                                               va_list va)
 917 {
 918   struct TopologyContext *tc;
 919   struct GNUNET_TESTBED_Operation *op;
 920   struct GNUNET_TESTBED_Controller *c;
 921   enum GNUNET_TESTBED_TopologyOption secondary_option;
 922   unsigned int cnt;
 923
 924   if (num_peers < 2)
 925     return NULL;
 926   c = peers[0]->controller;
 927   tc = GNUNET_malloc (sizeof (struct TopologyContext));
 928   tc->peers = peers;
 929   tc->num_peers = num_peers;
 930   tc->op_cls = op_cls;
 931   tc->retry_cnt = DEFAULT_RETRY_CNT;
 932   tc->comp_cb = comp_cb;
 933   tc->comp_cb_cls = comp_cb_cls;
 934   switch (topo)
 935   {
 936   case GNUNET_TESTBED_TOPOLOGY_LINE:
 937     gen_topo_line (tc);
 938     break;
 939   case GNUNET_TESTBED_TOPOLOGY_RING:
 940     gen_topo_ring (tc);
 941     break;
 942   case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
 943     gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_NO);
 944     break;
 945   case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
 946     gen_topo_ring (tc);
 947     gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_YES);
 948     break;
 949   case GNUNET_TESTBED_TOPOLOGY_CLIQUE:
 950     tc->link_array_size = num_peers * (num_peers - 1);
 951     tc->link_array =
 952         GNUNET_malloc (sizeof (struct OverlayLink) * tc->link_array_size);
 953     {
 954       unsigned int offset;
 955
 956       offset = 0;
 957       for (cnt = 0; cnt < num_peers; cnt++)
 958       {
 959         unsigned int neighbour;
 960
 961         for (neighbour = 0; neighbour < num_peers; neighbour++)
 962         {
 963           if (neighbour == cnt)
 964             continue;
 965           tc->link_array[offset].A = cnt;
 966           tc->link_array[offset].B = neighbour;
 967           tc->link_array[offset].tc = tc;
 968           offset++;
 969         }
 970       }
 971     }
 972     break;
 973   case GNUNET_TESTBED_TOPOLOGY_2D_TORUS:
 974     gen_topo_2dtorus (tc);
 975     break;
 976   case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD:
 977     gen_topo_2dtorus (tc);
 978     gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_YES);
 979
 980     break;
 981   case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
 982     {
 983       uint16_t cap;
 984       uint8_t m;
 985
 986       cap = (uint16_t) va_arg (va, unsigned int);
 987       m = (uint8_t) va_arg (va, unsigned int);
 988       gen_scale_free (tc, cap, m);
 989     }
 990     break;
 991   case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
 992   {
 993     const char *filename;
 994
 995     filename = va_arg (va, const char *);
 996
 997     GNUNET_assert (NULL != filename);
 998     gen_topo_from_file (tc, filename);
 999   }
1000     break;
1001   default:
1002     GNUNET_break (0);
1003     GNUNET_free (tc);
1004     return NULL;
1005   }
1006   do
1007   {
1008     secondary_option = va_arg (va, enum GNUNET_TESTBED_TopologyOption);
1009
1010     switch (secondary_option)
1011     {
1012     case GNUNET_TESTBED_TOPOLOGY_RETRY_CNT:
1013       tc->retry_cnt =  va_arg (va, unsigned int);
1014       break;
1015     case GNUNET_TESTBED_TOPOLOGY_OPTION_END:
1016       break;
1017     default:
1018       GNUNET_break (0);         /* Should not use any other option apart from
1019                                  * the ones handled here */
1020       GNUNET_free_non_null (tc->link_array);
1021       GNUNET_free (tc);
1022       return NULL;
1023     }
1024   }
1025   while (GNUNET_TESTBED_TOPOLOGY_OPTION_END != secondary_option);
1026   op = GNUNET_TESTBED_operation_create_ (tc,
1027                                          &opstart_overlay_configure_topology,
1028                                          &oprelease_overlay_configure_topology);
1029   GNUNET_TESTBED_operation_queue_insert_
1030       (c->opq_parallel_topology_config_operations, op);
1031   GNUNET_TESTBED_operation_begin_wait_ (op);
1032   LOG (GNUNET_ERROR_TYPE_DEBUG, "Generated %u connections\n",
1033        tc->link_array_size);
1034   if (NULL != max_connections)
1035     *max_connections = tc->link_array_size;
1036   return op;
1037 }
1038
1039
1040 /**
1041  * All peers must have been started before calling this function.
1042  * This function then connects the given peers in the P2P overlay
1043  * using the given topology.
1044  *
1045  * @param op_cls closure argument to give with the peer connect operation events
1046  *          generated through this function
1047  * @param num_peers number of peers in 'peers'
1048  * @param peers array of 'num_peers' with the peers to configure
1049  * @param max_connections the maximums number of overlay connections that will
1050  *          be made to achieve the given topology
1051  * @param comp_cb the completion callback to call when the topology generation
1052  *          is completed
1053  * @param comp_cb_cls closure for the above completion callback
1054  * @param topo desired underlay topology to use
1055  * @param ... topology-specific options
1056  * @return handle to the operation, NULL if connecting these
1057  *         peers is fundamentally not possible at this time (peers
1058  *         not running or underlay disallows) or if num_peers is less than 2
1059  */
1060 struct GNUNET_TESTBED_Operation *
1061 GNUNET_TESTBED_overlay_configure_topology (void *op_cls,
1062                                            unsigned int num_peers,
1063                                            struct GNUNET_TESTBED_Peer **peers,
1064                                            unsigned int *max_connections,
1065                                            GNUNET_TESTBED_TopologyCompletionCallback
1066                                            comp_cb,
1067                                            void *comp_cb_cls,
1068                                            enum GNUNET_TESTBED_TopologyOption topo,
1069                                            ...)
1070 {
1071   struct GNUNET_TESTBED_Operation *op;
1072   va_list vargs;
1073
1074   GNUNET_assert (topo < GNUNET_TESTBED_TOPOLOGY_OPTION_END);
1075   va_start (vargs, topo);
1076   op = GNUNET_TESTBED_overlay_configure_topology_va (op_cls, num_peers, peers,
1077                                                      max_connections,
1078                                                      comp_cb, comp_cb_cls,
1079                                                      topo,
1080                                                      vargs);
1081   va_end (vargs);
1082   return op;
1083 }
1084
1085
1086 /**
1087  * Get a topology from a string input.
1088  *
1089  * @param topology where to write the retrieved topology
1090  * @param topology_string The string to attempt to
1091  *        get a configuration value from
1092  * @return GNUNET_YES if topology string matched a
1093  *         known topology, GNUNET_NO if not
1094  */
1095 int
1096 GNUNET_TESTBED_topology_get_ (enum GNUNET_TESTBED_TopologyOption *topology,
1097                               const char *topology_string)
1098 {
1099   unsigned int cnt;
1100
1101   for (cnt = 0; NULL != topology_strings[cnt]; cnt++)
1102   {
1103     if (0 == strcasecmp (topology_string, topology_strings[cnt]))
1104     {
1105       if (NULL != topology)
1106         *topology = (enum GNUNET_TESTBED_TopologyOption) cnt;
1107       return GNUNET_YES;
1108     }
1109   }
1110   return GNUNET_NO;
1111 }
1112
1113
1114 /**
1115  * Returns the string corresponding to the given topology
1116  *
1117  * @param topology the topology
1118  * @return the string (freshly allocated) of given topology; NULL if topology cannot be
1119  *           expressed as a string
1120  */
1121 char *
1122 GNUNET_TESTBED_topology_to_str_ (enum GNUNET_TESTBED_TopologyOption topology)
1123 {
1124   if (GNUNET_TESTBED_TOPOLOGY_OPTION_END <= topology)
1125     return NULL;
1126   return GNUNET_strdup (topology_strings[topology]);
1127 }
1128
1129 /* end of testbed_api_topology.c */